WikiDer > Registrierungszuordnung

Registerallocatie

Registrierungszuweisung ist Teil von kompilieren des Quellcode von a Computer Programm. Während der Registerzuweisungsphase bestimmt der Compiler, wie die registriert im Endprogramm verwendet werden.

Denn für a Prozessor Der Zugriff auf eine Registry ist relativ schnell im Vergleich zum Zugriff auf die Erinnerung es ist vorzuziehen, während der Programmausführung die Daten, die bearbeitet werden, in Registern statt im Speicher so weit wie möglich zu haben. Allerdings ist die Anzahl der Register auf einem Prozessor begrenzt (ältere Prozessoren hatten manchmal nur 4 oder 8 Register für ein Programm zur Verfügung).

Der Zweck der Registerzuordnung besteht darin, eine möglichst effiziente Verwendung von Registern im kompilierten Programm auf Basis von Daten über das zu kompilierende Programm zu realisieren.

Im Compiler platzieren

Die Registrierungszuordnung erfolgt, nachdem der Compiler das Quellprogramm in a . übersetzt hat interne Vertretung (Zwischendarstellung, oder IR). Diese IR kann eine Art abstrakt sein Monteur oder ein Syntaxbaum sein. Obwohl die verwendete IR von Compiler zu Compiler unterschiedlich ist, haben sie alle gemeinsam, dass die einzelnen Anweisungen (die Knoten im Fall eines Syntaxbaums) haben eine nahezu Eins-zu-Eins-Beziehung zu den Maschinenanweisungen des Prozessors, für den kompiliert wird.

Dank dieser Ähnlichkeit zwischen der IR und den zu generierenden Anweisungen hat der Compiler bereits eine gute Vorstellung davon, wie das fertige Programm aussehen wird. Dies ist für eine erfolgreiche Allokationsstrategie notwendig.

Der IR verwendet eine im Grunde unendlich viele temporäre Register: Jedes Mal, wenn ein neues Register für eine Berechnung benötigt wird, wird ein neues temporäres Register verwendet. Bei der Registerzuordnung wird jedem dieser temporären Register eines der (realen) Maschinenregister zugeordnet.

Tore

Der Compiler versucht bei der Registerzuordnung folgende Bedingungen zu erfüllen:

  • Solange ein Register Daten enthält, die verwendet werden (wohnen), wird dieses Register nicht für andere Daten verwendet. In diesem Fall müssten die alten Daten zunächst in ein anderes Register oder einen anderen Speicher geschrieben werden, was zusätzliche Anweisungen und Zeit kostet.
  • Wenn Daten im IR von einem temporären Register in ein anderes verschoben werden, wird beiden temporären Registern nach Möglichkeit das gleiche Maschinenregister zugewiesen. In einem solchen Fall kann die Bewegungsanweisung einfach weggelassen werden.

Methode

Um zu einer guten Registerzuordnung zu gelangen, führt der Compiler a Lebendigkeitsanalyse von. Wenn zwei temporäre Register ein und b werden nicht gleichzeitig verwendet (wohnen sind), können sie dieselbe Registrierung verwenden. Glücklicherweise wird zu jeder Zeit in einem Programm nur eine begrenzte Anzahl von Variablen (temporäre Register sind die Variablen des IR) verwendet. Wenn zu irgendeinem Zeitpunkt mehr Variablen aktiv sind als Maschinenregister verfügbar sind, werden die verbleibenden Variablen im Speicher gehalten (dies ist verschütten erwähnt).

Zu einer Lebendigkeitsanalyse zum Ausführen läuft der Compiler zuerst a KontrollflussAnalyse. Das bedeutet, dass der Compiler alle möglichen Pfade durch das IR-Programm ermittelt. In einem Programm ohne bedingte Anweisungen gibt es nur eine, aber die meisten Programme haben eine große Anzahl von bedingten Anweisungen und damit eine große Anzahl möglicher Pfade. Nachdem der Compiler alle möglichen Pfade berechnet hat, kann dann bestimmt werden, welche Variablen nie gleichzeitig vorkommen wohnen dürfen dieselbe Registry verwenden. Dann um ein Semioptimum zu bekommen[1] Um eine Registerzuordnung zu erhalten, verwendet ein Compiler normalerweise eine Form von Diagrammfärbung (Diagrammfärbung).

Sobald dies geschehen ist, wird jedem temporären Register (Variable) im IR ein Maschinenregister zugewiesen und der Compiler kann dann Maschinencode generieren (Codegenerierung).

Siehe auch