Implementing a global register allocator for TCC

Abstract

Registerzuteilung (engl. register allocation) ist eines der ältesten Forschungsthemen in der Informatik, welches im Laufe der letzten Jahrzehnte ausgiebig untersucht wurde. Das Ziel besteht darin, bei der Übersetzung von Programmen eine theoretisch unendliche Anzahl an Programmvariablen einer endlichen, kleinen Menge an verfügbaren Prozessor-Registern zuzuordnen. Auch wenn mit Hilfe von Caches die Kluft zwischen Register- und Speicherzugriffszeit überbrückt wird, so ist es doch wichtig, so viele Werte wie möglich so lange wie möglich in Registern zu halten, um eine gute Leistung zu erzielen. Somit wird Registerzuteilung nach wie vor als eine der wichtigsten Compileroptimierungen angesehen. Die vorliegende Diplomarbeit beschreibt den Vorgang der Implementierung eines Registerallokators für TCC, einem kleinen Ein-Pass C-Compiler, der selbst auch in C geschrieben ist2 . TCC ist sehr schnell (bis zu zehnmal schneller als gcc -O0 für die x86-Architektur), erzeugt jedoch sehr ineffizienten Code - eine sehr einfache Art der Registerzuteilung wird nur auf Basis von Anweisungen gemacht. Unser Ziel, Registerzuweisung auf Basis von ganzen Funktionen zu implementieren (d.h. einen globalen Registerallokator), sollte somit einen deutlichen Geschwindigkeitszuwachs bringen. Als Voraussetzung für einen Registerallokator in TCC muss ein passender Zwischencode (engl. IR, Intermediate Representation) in einem ersten Durchlauf erzeugt werden. Auf Basis dieser internen Repräsentation können dann die Lebensdaueranalyse der Variablen, Registerzuteilung und letztendlich die Codeerzeugung durchgeführt werden. Wir bestimmen die Lebensdauerintervalle der Variablen mit einem außergewöhnlich einfachen Algorithmus, der die üblichen Techniken der Datenflussanalyse vermeidet - die Genauigkeit der ermittelten Intervalle wird zugunsten einer höheren Ausführungsgeschwindigkeit geopfert. Für die Registerzuteilung benutzen wir Linear Scan, eine Strategie welche das Problem nicht auf Graphenfärbung reduziert, sondern mit einer sehr einfachen Vorgangsweise arbeitet, welche lediglich einen sequentiellen Durchlauf von den aktiven Intervallen (engl. live intervals) der Variablen benötigt. Obwohl die Strategie sehr schnell ist, wird angegeben dass der erzeugte Code beinahe so effizient ist wie jener von Graphenfärbungs-Algorithmen. Aufgrund dieser Tatsache ist Linear Scan sehr beliebt für JIT Compiler. Als Zielarchitektur wird ARM gewählt, eine klassische RISC-Architektur, die mittlerweile weitverbreitet in Mobiltelefonen als auch in vielen anderen eingebetteten Systemen ist. Da in dieser Load/Store-Architektur die Operanden bei Datenverarbeitungsoperationen nicht im Speicher liegen dürfen, ist Registerzuteilung hier besonders wichtig. Wir ermitteln den Geschwindigkeitszuwachs der Implementierung mit verschiedensten Testprogrammen, die vorwiegend von der Benchmark-Sammlung MiBench stammen. Zusätzlich vergleichen wir sowohl die Übersetzungs-Zeit- als auch die Laufzeit-Leistung mit dem weitverbreiteten Compiler gcc. Unsere Implementierung erzeugt Code der im Durchschnitt um ca. 32% schneller ist (verglichen mit dem originalen TCC), wobei sich die Übersetzungs-Zeit nur marginal erhöht und immer noch über zehn Mal niedriger ist als für gcc ohne jegliche Optimierung. Somit ist unsere Implementierung des Registerallokators ein guter Kompromiss für dynamische Codeerzeugung mit TCC.

Register allocation is a long-standing research topic of computer science that has been studied extensively over the last decades. Its goal is to map a theoretically infinite number of program variables onto a finite, small set of CPU registers during compilation. Even though caches try to bridge the gap between register and memory access time, keeping as many values in registers as long as possible is crucial for good performance. Hence register allocation is still considered to be one of the most important compiler optimizations. The present diploma thesis describes the process of implementing a register allocator for TCC, a small single-pass C compiler written in C1 . While TCC is very fast (up to a magnitude faster than gcc -O0 for the x86 architecture), it produces code that is quite inefficient - some naive kind of register allocation is done only on the basis of statements. Our goal of implementing register allocation done on the basis of whole functions, that is, global register allocation, should hence result in a notable performance increase. As prerequesite for register allocation in TCC, a proper IR (Intermediate Representation) needs to be generated in a first pass. On top of this internal representation, live variable analysis, register allocation and finally the code generation is then performed. We determine the variable live intervals with an extraordinarily simple approach that avoids the usual costly data-flow analysis techniques - it trades off the accuracy of the calculated intervals for higher execution speed. For the register allocation we use Linear Scan, a strategy that doesn't abstract the problem to graph coloring, but rather takes a simple approach involving the linear traversal of variable live intervals. While linear scan is very fast, it is stated that the generated code is almost as efficient as with graph coloring, making it a popular choice for JIT compilers. As target machine, ARM, a classical RISC architecture, now widespread especially in mobile phones and in many other embedded systems, is chosen. Since data processing operands must not reside in memory in this Load/Store architecture, register allocation is even more important. We determine the performance gain with various test applications, predominantly from the benchmark suite MiBench. Additionally, we compare compile-time as well as run-time performance with the widespread compiler gcc. The execution time speedup of code generated by our implementation is about 32% on average (compared to the original TCC), while the compile-time is increased only marginally and is still an order of magnitude lower than for gcc without any optimization. Consequently, our register allocator implementation is an attractive trade-off for dynamic code generation with TCC.