Ich suche nach einer Möglichkeit, lokale Variablen Registern zuzuweisen. Ich kenne ein paar ernsthafte Methoden dafür (nämlich die genannten)auf Wikipedia), aber ich stecke fest, wie "Verschütten" erreicht wird. Auch die einschlägige Literatur ist ziemlich einschüchternd. Ich hoffe, dass es etwas Einfacheres gibt, das meine Prioritäten erfüllt:

Korrektheit - Ein Algorithmus, der unabhängig von der Anzahl der lokalen Variablen den richtigen Code generiert.Einfachheit - etwas, das ich verstehen kann, ohne zu viel Literatur lesen zu müssen.Effizienz - Es muss besser sein als die derzeitige Methode:

Übersetzen Sie eine Operationx = y # z zu:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Während ich Intel 386 anvisiere, sind einige relevante Einschränkungen:

Binäre Operationen benötigen zwei Argumente, von denen eines eine Quelle und ein Ziel ist. Unäre Operationen haben ein einziges Argument.Operationen können nur auf einen Speicherort zugreifen; Binäre Operationen benötigen daher mindestens ein Argument in einem Register.Es stehen maximal sechs Register zur Verfügung:%eax %ebx %ecx %edx %esi %edi. (%ebp könnte auch als letztes Mittel aufgenommen werden.)Es gibt spezielle Fälle, wie zum Beispiel für ganzzahlige Divisions- und Rückgaberegister, aber ich kann sie vorerst ignorieren.

Der Compiler durchläuft derzeit drei Schritte:

i386ification: Alle Operationen werden in ein Formular konvertierta = a # b (odera = #a für unäre Operationen).Lebendigkeitsanalyse: Die Sätze von Live-Variablen vor und nach jeder Operation werden bestimmt.Registerzuordnung: Ein Interferenzgraph wird erstellt und eingefärbt.

Und dann wirft der Compiler seine Buntstifte in die Luft und weiß nicht, was als nächstes zu tun ist.

Beispiel

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Hier ist das hübsche Interferenzdiagramm für die Funktion und das CFG mit Informationen zur Lebendigkeit. Das CFG-Bild erfordert leider ein vertikales Scrollen.

Interferenzgraph für eine Funktion auf 14 VariablenKontrollflussdiagramm für eine Funktion mit Aktivitätsinformationen

Sieben Farben wurden verwendet. Ich möchte eine davon (oder den Variablensatz, dem diese Farbe zugewiesen wurde) verschütten. Die Art der Auswahl ist nicht allzu wichtig. Was schwierig wird, ist der Umgang mit verschütteten Variablen.

Nehmen wir an, ich verschütte "pink", was die Menge der Variablen istt, $t4, $t7. Dies bedeutet, dass die Operationen, die auf eine dieser Variablen verweisen, nicht über ein Register, sondern von ihrer Position im Stapelrahmen aus darauf zugreifen. Dies sollte für dieses Beispiel funktionieren.

Was aber, wenn das Programm war:

...
a = a + b
...

und beidea undb musste verschüttet werden? Ich kann keine Anweisung erteilenaddl b, a mit zwei Speicheradressen. Ich würde ein anderes Ersatzregister benötigen, um vorübergehend einen der Operanden zu halten, und das bedeutet, eine andere Farbe zu verschütten. Dies legt eine allgemeine Methode nahe:

Wenn alle Variablen mit eingefärbt werden könnenr Farben, toll!Verschütten Sie andernfalls einige Farben und die zugehörigen Variablen.Wenn eine Operation vorhanden ist, die auf zwei verschüttete Variablen zugreift, verschütten Sie eine andere Farbe und verwenden Sie das Ersatzregister für die temporäre Speicherung für alle diese Operationen.

An diesem Punkt würde ich vermuten, dass viel mehr Dinge verschüttet werden als nötig, und ich frage mich, ob es eine intelligentere Möglichkeit gibt, Dinge zu verschütten, beispielsweise einen Teil der Lebensdauer einer Variablen, anstatt die gesamte Variable selbst. Gibt es einige einfache (ish) Techniken, die ich hier anwenden könnte? Auch hier ziele ich nicht besonders hoch - schon gar nicht hoch genug, um etwas zu tief zu lesen. ;-)

Spezifische Probleme

Das Hauptproblem ist: Wie wirkt sich dies auf die generierten Anweisungen aus, wenn eine Variable verschüttet wird? Müssen alle Anweisungen, die diese Variable verwenden, direkt im Speicher darauf zugreifen (von der Stapelposition aus)? Wie funktioniert das, wenn eine Operation zwei verschüttete Variablen verwendet? (Die Architektur erlaubt Anweisungen nicht, auf zwei unterschiedliche Speicherorte zuzugreifen.)

Sekundäre Probleme sind:

Wie bestimme ich, wo Lade- / Speicheranweisungen eingefügt werden müssen, um die Richtigkeit (und vor allem die Effizienz) zu gewährleisten?Kann ich eine Variable nur für diesen Teil ihrer Lebensdauer verschütten, wenn sie nicht sofort verwendet wird, und sie später wieder entfernen? Damit wirken alle Anweisungen auf nicht übersetzte Register. Eine Variable kann zu verschiedenen Zeiten in verschiedenen Registern gespeichert sein.Kann ich in besonderen Fällen etwas effizienter sein? Zum Beispiel,%eax wird für den Rückgabewert verwendet, daher wäre es schön, wenn die zurückzugebende Variable diesem Register zum Zeitpunkt des Auftretens der Rückgabe zugewiesen würde. In ähnlicher Weise sind einige Register "callee-save". Wenn also zum Zeitpunkt eines Funktionsaufrufs weniger Variablen aktiv waren, würde die Zuordnung zu nicht callee-save-Registern bedeuten, dass ich das Speichern dieser Register vermeiden kann.Würde SSA-Formular (wenn überhaupt) viel helfen? In der Lage zu sein, häufige Unterausdrücke zu eliminieren und Konstanten auszuwerten, könnte den Registerdruck verringern (?), Aber sonst würde es irgendeinen Effekt haben?

Die Aspekte, um die ich mich (gerade) nicht kümmere, sind:

Stapelzuordnung und -optimierung: Sie ist bereits naiv implementiert und kann bei Bedarf mithilfe des Interferenzgraphen optimiert werden.Effizienz bei der Kompilierung, solange es beendet ist. (NP-Vollständigkeit bedeutet nicht, dass ein bestimmter Algorithmus vermieden werden sollte.)Aktualisieren

Entschuldigung für die Ausfallzeit - ich habe über die gegebenen Antworten nachgedacht und versucht, einen einfachen Ansatz zu finden, mit dem ich beginnen kann, einige der Ideen umzusetzen. Um ehrlich zu sein, ich habe zögern ...: - \ Ich fand die sehr schöne Präsentation (PPT, leider):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Welche beantwortet die Frage, wie mit bestimmten Vorgangsanforderungen umgegangen werden soll (z. B. Verwendung desselben Registers für Quelle und Ziel oder Verwendung eines bestimmten Registers für einige Vorgänge). Was ich nicht sicher bin, ist, ob der Zyklus Lebendigkeit-Färbung-Zuordnung endet.

Ich werde versuchen, bald einige tatsächliche Arbeiten zu erledigen und die Frage hoffentlich schließen.

Sie haben Recht: Sie verschütten Register, die derzeit nicht verwendet werden, um Platz für diejenigen zu schaffen, die verwendet werden. Dann können sich alle Operationen in Registern befinden. Um dies zu lösen und einige Operationen direkt an verschütteten Registern durchzuführen, ändern Sie Ihren Registerzuweisungsalgorithmus so, dass höchstens ein Register während der Register-zu-Register-Anweisungen verschüttet bleibt. Dies ist jedoch nicht erforderlich.