Codegenerierung und -optimierung

Codegenerierung und -optimierung übersetzen Zwischenrepräsentationen in effizienten Zielcode und transformieren Programme, um schneller zu laufen oder weniger Ressourcen zu verbrauchen, während ihre Bedeutung erhalten bleibt.

Definition

Codegenerierung ist die Erzeugung von Zielinstruktionen (Maschinen- oder Bytecode) aus einer Zwischenrepräsentation, und Optimierung ist die Anwendung von semantikerhaltenden Transformationen, die die Geschwindigkeit, Größe oder Ressourcennutzung eines Programms verbessern.

Scope

Dieses Thema behandelt das Compiler-Backend und -Middle-End: Zwischenrepräsentationen wie die Static Single Assignment (SSA)-Form, Datenflussanalyse, klassische Optimierungen (Konstantenpropagation, Eliminierung gemeinsamer Teilausdrücke, Schleifenoptimierungen), Instruktionsauswahl, Instruktionsplanung und Registerallokation. Es wird untersucht, wie Transformationen die Programmsemantik erhalten und gleichzeitig die Leistung verbessern.

Core questions

• Wie können Programmtransformationen die Leistung verbessern, ohne das Verhalten zu ändern?
• Welche Zwischenrepräsentationen machen die Optimierungsanalyse effizient?
• Wie werden begrenzte Maschinenregister vielen Programmwerten zugewiesen?
• Wie werden Korrektheit und Leistung bei aggressiver Optimierung abgewogen?

Key theories

Static Single Assignment Form

Cytron und Kollegen entwickelten einen effizienten Algorithmus zur Umwandlung von Programmen in die SSA-Form, bei der jede Variable nur einmal zugewiesen wird, was viele datenflussbasierte Optimierungen erheblich vereinfacht.

Registerallokation durch Graphfärbung

Chaitin modellierte die Registerallokation als Graphfärbung eines Interferenzgraphen und lieferte damit den grundlegenden Ansatz zur Zuweisung von Programmwerten zu einer begrenzten Menge von Maschinenregistern.

Datenflussbasierte Optimierung

Muchnick und das Dragon Book formalisieren die Datenflussanalyse als den Rahmen, der klassischen Optimierungen zugrunde liegt, indem sie Programmeigenschaften berechnen, die zur Rechtfertigung sicherer Transformationen erforderlich sind.

Clinical relevance

Die Optimierung der Codegenerierung bestimmt, wie effizient Programme Prozessoren und Speicher nutzen, mit weitreichenden Auswirkungen auf Energieverbrauch und Kosten im großen Maßstab. Die SSA-Form und die Registerallokation mittels Graphfärbung bleiben zentrale Bestandteile von Produktionscompilern und Just-in-Time-Systemen.

History

Die Optimierung begann mit dem Fortran-Compiler und reifte durch Allens und Cockes Datenflussanalyse in den 1970er Jahren. Chaitins Registerallokation mittels Graphfärbung von 1981-82 und Cytron et al.s effiziente SSA-Konstruktion von 1991 wurden zu Eckpfeilern moderner Compiler und ermöglichten die ausgeklügelten Optimierungspipelines, die heute in Toolchains verwendet werden.

Debates

Aggressivität der Optimierung versus Korrektheit und Vorhersagbarkeit

Compiler-Designer diskutieren, wie aggressiv optimiert werden sollte, da die Ausnutzung undefinierten Verhaltens und die Neuordnung zwar Geschwindigkeit bringen, aber überraschende oder unsichere Ergebnisse hervorrufen können, was das Interesse an verifizierter und vorhersagbarer Optimierung weckt.

Key figures

• Frances Allen
• Gregory Chaitin
• Ron Cytron
• Steven Muchnick
• Alfred Aho

Seminal works

• cytron1991
• chaitin1982
• muchnick1997
• aho2006

Frequently asked questions

Was ist die SSA-Form?

Die Static Single Assignment Form ist eine Zwischenrepräsentation, bei der jede Variable genau einmal zugewiesen wird und Verwendungen mit einer einzigen Definition verknüpft sind, was viele Compiler-Optimierungen vereinfacht und verstärkt.

Warum ist die Registerallokation schwierig?

Programme verwenden typischerweise weit mehr Werte als Maschinenregister vorhanden sind, daher muss der Compiler entscheiden, welche Werte sich Register teilen und welche in den Speicher ausgelagert werden; das Kernproblem ist äquivalent zur Graphfärbung, die im Allgemeinen rechnerisch schwierig ist.