Bárány, G. (2015). Integrated code motion and register allocation [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2015.29461
Code Motion und Registerallokation sind wichtige, aber fundamental gegensätzliche Programmtransformationen in optimierenden Übersetzern. Globale Code Motion platziert Befehle in weniger oft ausgeführten Programmblöcken, während die Befehlsanordnung in Blöcken oder Regionen (hier kollektiv "Code Motion") Anweisungen so anordnet, dass unabhängige Berechnungen parallel ausgeführt werden können. Diese Optimierungen erhöhen oft den Abstand zwischen den Definitionen und Verwendungen von Werten, was zu mehr Überlappungen zwischen den Live Ranges führt. Im Allgemeinen bewirken mehr Überlappungen einen höheren Registerdruck und die Erzeugung von mehr Code für die Auslagerung von Werten. Aggressive Code Motion vor der Registerallokation kann daher zu einer insgesamt verringerten Performance führen. Andererseits werden durch Registerallokation vor der Code Motion voneinander unabhängige Werte an gemeinsame Prozessorregister zugewiesen, wodurch falsche Abhängigkeiten zwischen Berechnungen entstehen. Diese Abhängigkeiten verhindern Code-Motion-Transformationen, die vor der Zuweisung noch zulässig gewesen wären. Das ist eine Instanz des Phase-Ordering-Problems: Keine der Reihenfolgen dieser Phasen der Codeerzeugung garantiert optimale Ergebnisse. Eine Möglichkeit, dieses Problem zu umgehen, ist die gleichzeitige Lösung beider Probleme mit einem integrierten Verfahren. In dieser Arbeit wird ein integriertes Verfahren für globale Code Motion und Registerallokation entwickelt. Das Ergebnis ist ein Algorithmus, der eine Anordnung von Befehlen bestimmt, die zu minimaler Auslagerung von Werten führt, während gleichzeitig so viel globale Code Motion und lokale Befehlsanordnung für Parallelität wie möglich angewandt wird. Basierend auf einer Überlappungsanalyse, die alle möglichen Konflikte zwischen Live Ranges in allen möglichen Anordnungen von Befehlen beachtet, konstruiert der Algorithmus ein Registerallokationsproblem, dessen Lösung auch Code-Motion-Informationen für die Sicherstellung der Zulässigkeit der Allokation beinhaltet. Eine Phase der Kandidatenauswahl entscheidet, welche Paare von Live Ranges für die Wiederverwendung von Prozessorregistern in Frage kommen sollen. Das Auswahlverfahren hat einen Parameter, über den die Balance zwischen Code Motion und Registerallokation gesteuert werden kann, und wird entweder heuristisch oder optimal durchgeführt. Die Ergebnisse zeigen, dass im Allgemeinen globale Code Motion den Registerdruck genau beachten sollte. Außer in einigen seltenen Fällen mit geringem Registerdruck sollten Übersetzer Code so anordnen, dass die Auslagerung von Werten in den Speicher minimiert wird.
de
Code motion and register allocation are important but fundamentally conflicting program transformations in optimizing compiler back-ends. Global code motion aims to place instructions in less frequently executed basic blocks, while instruction scheduling within blocks or regions (all subsumed here under "code motion") arranges instructions such that independent computations can be performed in parallel. These optimizations tend to increase the distances between the definitions and uses of values, leading to more overlaps of live ranges. In general, more overlaps lead to higher register pressure and insertion of more expensive register spill and reload instructions in the program. Eager code motion performed before register allocation can thus lead to an overall performance decrease. On the other hand, register allocation before code motion will assign unrelated values to the same physical register, introducing false dependences between computations. These dependences block opportunities for code motion that may have been legal before assignment of registers. This is an instance of the phase ordering problem: Neither ordering of these phases of code generation provides optimal results. A common way to sidestep this problem is by solving both problems at once in an integrated fashion. This thesis develops a fully integrated approach to global code motion and register allocation. The result is an algorithm that determines an arrangement of instructions that leads to minimal spill code while performing as much global code motion and scheduling for parallelism as possible. Based on an overlap analysis that determines all the possible interferences between live ranges when taking all possible arrangements of instructions into account, the algorithm constructs a register allocation problem such that the solution encodes code motion information to ensure a legal allocation. A candidate selection pass determines which live ranges should be considered for reuse of a processor register. The selection process includes a tuning parameter to study the trade-off between global code motion and spilling, and can be performed in a heuristic or an optimal way. The results show that in general, global code motion should be careful to take register pressure into account. Except for rare cases where register use is low, compilers should focus on arranging code such that minimal spilling is required.