Register-Allokation und verschütten,, der einfache Weg?

https://stackoverflow.com/questions/1960888

21-09-2019
|

Frage

Ich bin auf der Suche nach einem Weg zu reservieren, lokale Variablen zu Registern.Ich bin mir bewusst ein paar ernsthafte Methoden, es zu tun (nämlich derjenigen, die auf Wikipedia), aber ich bin stecken, wie "spilling" erreicht wird.Auch die einschlägige Literatur ist ziemlich einschüchternd.Ich bin der Hoffnung, es etwas einfacher, dass wird befriedigen meine Prioritäten:

Fehlerfreiheit-ein Algorithmus zur Generierung von richtigen code, unabhängig davon, wie viele lokale Variablen es gibt.
Einfachheit-etwas, das ich verstehen kann, ohne Lesen zu viel Literatur.
Effizienz -- es muss besser sein als die aktuelle Methode, die ist:

Übersetzen einer operation x = y # z zu:

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

Wie ich bin-targeting Intel 386, einige relevante Einschränkungen sind:

Binäre Operationen nehmen zwei Argumente, von denen einer Quelle und einem Ziel.Unäre Operationen take a single argument.
Operationen können nur auf eine memory location;binäre Operationen müssen daher mindestens ein argument in a register.
Es gibt ein maximum von sechs verfügbaren Register: %eax %ebx %ecx %edx %esi %edi. (%ebp könnte auch enthalten als letzten Ausweg.)
Es gibt spezielle Fälle, wie für ganzzahlige division und zurück registriert, aber ich kann ignorieren Sie Sie jetzt.

Es gibt drei Schritte, die der compiler erhält durch an den moment:

i386ification:alle Vorgänge werden in einer form a = a # b (oder a = #a für unäre Operationen).
Ausführen, um liveness-Analyse:die sets von live Variablen vor und nach jeder operation bestimmt werden.
Register-Zuordnung:ein Interferenz-Grafik ist gebaut und gefärbt.

Und dann gibt der compiler seine buntstifte in der 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 eher ziemlich Störungen graph für die Funktion und die CFG mit ausführen, um liveness Informationen.Die CFG-Bild erfordert einige vertikales scrollen, leider.

Sieben Farben verwendet wurden.Ich möchte spill einer von Ihnen (oder der Gruppe von Variablen zugewiesen, die der Farbe).Die Methode der Wahl, welches ist nicht wichtig.Was schwierig wird, ist, wie zu deal mit die verschüttete Variablen.

Sagen wir, ich spill "rosa", das ist der Satz der Variablen t, $t4, $t7.Dies bedeutet, dass diese Operationen Bezugnahme auf diese Variablen zugreifen, es von seiner position auf dem stack frame, anstatt über ein register.Diese Arbeit sollte für dieses Beispiel.

Aber was ist, wenn das Programm war:

...
a = a + b
...

und beide a und b musste vergossen werden?Ich kann nicht emittieren eine Anleitung addl b, a mit zwei Speicher-Adressen.Ich würde benötigen Sie ein anderes Ersatzteil registrieren Sie sich, um vorübergehend halten einer der Operanden, und das bedeutet, dass das verschütten einer anderen Farbe.Dies deutet auf eine Allgemeine Methode:

Wenn alle Variablen, die eingefärbt werden können r Farben, ideal!
Sonst verschütten Sie einige Farben und Ihre zugehörigen Variablen.
Wenn eine operation vorhanden ist, wird auf zwei verschüttete Variablen, spill anderen Farbe und nutzen die freie register für die temporäre Speicherung für all diese Vorgänge.

An diesem Punkt würde ich vermuten, dass viel mehr Zeug wird verschüttet, als notwendig, und Frage mich, ob es etwas intelligentere Art und Weise zu verschütten Dinge, wie verschütten Teil eine variable Lebensdauer, sondern als das ganze variable selbst.Gibt es einige einfache(ish) Techniken, die ich verwenden könnte, hier?Wieder bin ich nicht dem Ziel besonders hoch-mit Sicherheit nicht hoch genug, dass das Lesen etwas zu tief.;-)

Spezifische Probleme

Das Haupt-problem ist:wenn eine variable ist verschüttet, wie wirkt sich diese auf die generierten Anweisungen?Tun Sie allen Anweisungen verwenden, die variable zugreifen zu können, müssen Sie es direkt im Speicher (von der stack-position) ?Wie soll das funktionieren, wenn eine operation mit zwei verschüttete Variablen?(Die Architektur nicht zulassen Anleitungen für den Zugriff auf zwei verschiedene Speicherplätze.)

Sekundäre Probleme sind:

Wie kann ich bestimmen, wo zum einfügen load/store Instruktionen, für die Richtigkeit (und weniger wichtiger, Effizienz) ?
Kann versinke ich eine variable für die nur der Teil seines Lebens, wenn es nicht sofort verwenden, und unspill es später?So, dass Sie alle Anweisungen handeln auf unspilled registriert.Einer Variablen können sich in verschiedenen Registern zu unterschiedlichen Zeiten.
Kann ich ein wenig mehr effizient mit den speziellen Fällen.Für Beispiel, %eax verwendet wird für die Rückkehr Wert, so wäre es schön, wenn die variable zurückgegeben werden zufällig zugeteilt werden, die die Registrierung durch die Zeit der Rückkehr aufgetreten.Ebenso werden einige Register "aufgerufene speichern", so dass, wenn weniger Variablen passiert ist, um sein Leben zu der Zeit eine Funktion aufrufen, nachdem Sie zugewiesen non-aufgerufene-Register retten würde bedeuten, dass ich vermeiden kann die Speicherung von diesen Registern.
Würde SSA form viel helfen (wenn überhaupt) ?Lage sein, zu beseitigen gemeinsamen Teilausdrücke und bewerten Konstanten reduzieren könnte(?) registrieren Druck, aber sonst würde es haben jede Wirkung an?

Die Aspekte, die ich bin nicht besorgt über die (jetzt) sind:

Stack-Zuweisung und-Optimierung:es ist naiv implementiert bereits, und kann optimiert werden, die Störung Diagramm, wenn benötigen werden.
Compile-Zeit-Effizienz, nur so lange, wie es endet.(NP-Vollständigkeit bedeutet nicht einen bestimmten Algorithmus sollte vermieden werden.)

Update

Sorry für die downtime hat -- ich habe nachgedacht über die gegebenen Antworten und versuchen zu finden, einen einfachen Ansatz zu übernehmen, um mit der Umsetzung beginnen, einige der Ideen.Um ehrlich zu sein, habe ich procrastinating...:-\

Ich fand die sehr schöne Präsentation (PPT, leider):

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

Die Antwort auf die Frage über den Umgang mit konkreten Betrieb muss (wie mit dem dieselben register für die Quell-und Ziel;oder müssen eine bestimmte registrieren für einige Operationen).Was ich nicht sicher bin, ob die ausführen, um liveness-Färbung-Allocation-Zyklus beendet.

Ich werde versuchen zu tun, einige aktuelle Arbeit bald und hoffentlich die Frage schließen.

Lösung

Ich habe einen gierigen Ansatz in einer JVM-Zuweisung einmal, das funktionierte ziemlich gut.Im Grunde beginnen Sie oben in einer basic-block, bei der alle Werte auf dem stack gespeichert werden.Dann Scannen Sie einfach den Anweisungen vorwärts, Aufrechterhaltung eine Liste der Register, die einen Wert enthalten, und ob der Wert ist verschmutzt (Bedürfnisse zu werden zurück geschrieben).Wenn ein Befehl verwendet, ein Wert, der nicht in einem register (oder nicht im richtigen register), Heft eine Last (oder verschieben), um es in einem gratis registrieren, bevor Sie die Anweisung.Wenn ein Befehl schreibt einen Wert, gewährleisten es ist in einem register und markieren schmutzig nach der Anleitung.

Wenn Sie jemals brauchen, ein register, verschüttet verwendet, die Registrierung durch freigeben der Wert von es, und das schreiben auf den Stapel, wenn es ist schmutzig und Leben.Am Ende des basic-block, write-back keine schmutzigen und live-Register.

Diese Regelung macht es klar, wo genau all das lädt/speichert, gehen Sie generieren, wie Sie gehen.Es ist leicht anpassbar an die Anweisungen, die einen Wert im Speicher, oder welche entweder von zwei Argumente in Erinnerung, aber nicht beide.

Wenn Sie OK mit, dass alle Daten auf dem stack an jedem basic-block-Grenze, das System funktioniert ziemlich gut.Sollte es geben, die Ergebnisse ähnlich wie linear-Scans innerhalb eines basic-block, wie es im Grunde genommen sehr ähnliche Dinge.

Sie bekommen können beliebig kompliziert darüber, wie zu entscheiden, welche Werte zu verschütten und die Register zu reservieren.Einige lookahead kann nützlich sein, zum Beispiel durch Kennzeichnung jeder Wert mit einem bestimmten registrieren, es muss irgendwann in den grundlegenden blockieren (z.B.eax für eine Rückkehr Wert, oder ecx-für ein shift-Betrag) und die Bevorzugung, die registrieren, wenn der Wert ist zunächst reserviert (und zu vermeiden, dass ein register für andere Zuweisungen).Aber es ist einfach zu trennen die Korrektheit des Algorithmus von der Verbesserung der Heuristik.

Ich habe diese Zuweisung in eine SSA-compiler, YMMV.

Andere Tipps

Erste:Es ist kein intelligenter Weg, es zu tun.Das problem ist NP-vollständig ;-)

Wie verschütten ist getan:

Sie führen Ihre register allocation-Algorithmus und eine Liste der Variablen, die Sie haben zu verschütten.Jetzt können Sie reservieren etwas Platz auf dem Stapel am Anfang Ihrer Funktion.Link jede verschüttete variable auch einen Platz auf dem stack.Wenn Sie wollen intelligent sein, coalesce-Speicher mit nicht-überlappenden Leben reicht.Wenn Sie spill ein register speichern Sie es im Speicher und laden Sie es, wenn es wieder benötigt.

Wie behandeln eax:

Markieren Sie das register ausgefüllt, aber nicht gespeichert wird jede variable in it (pre-allocation).Dadurch wird der code-generator klar, dass sich registrieren.Smart zu sein speichern Sie den Wert in einem anderen register, wenn vorteilhaft.

Einfache und korrekte Weise zu verarbeiten verschütten:

Nur verschüttet alles.Diese vermuten, dass jede variable ist der live-Bereich ist das ganze Programm.Dies kann ergänzt werden durch die Verwendung Sachen wie LRU oder Verwendungshäufigkeit zu wählen, die registriert werden sollten, freigegeben.

Die nächste beste Sache zu tun ist wahrscheinlich linear scan register allocation.Es sollte ziemlich einfach zu implementieren, auch wenn Sie mit pre-allocation.Ich schlage vor, Sie schauen in das verlinkte Papier.

Konkrete Antworten

Was bedeutet Korrektheit bedeutet das für Sie?Selbst einfache Zuordnungen algorithmen korrekt sind, wenn Sie nicht machen einen Fehler bei der Programmierung.Proof (mathematische) Richtigkeit ist viel schwieriger.Beide lädt und speichert die eingegeben werden muss, bevor der Wert/ - register ist wieder benötigt werden.Beide müssen eingefügt werden, nachdem der Wert wird gespeichert/erstellt.
Ja.Wenn Sie das Programm das es so ist.Wenn Ihr Algorithmus verarbeiten kann, einen Wert in mehreren Registern während seiner livetime Sie können diese Optimierungen.
Es ist wieder bei Ihnen, zur Durchführung bestimmter Verbesserungen.Eine Möglichkeit wäre es, nur block eax, wenn Sie gebraucht wird, nicht für die ganze Programm.
Unter bestimmten Bedingungen SSA hilft.Inferenz Graphen der SSA-code immer chordal, was bedeutet, dass es keinen Zyklus mit mehr als 3 Knoten.Dies ist ein Spezialfall der graph coloring, in dem eine minimale Färbung kann gefunden werden in polynomieller Zeit.Konvertieren SSA, bedeutet nicht unbedingt mehr oder weniger registrieren Druck.Während der SSA-form hat in der Regel mehrere Variablen, werden diese in der Regel auch kleinere livetimes.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow