Anweisungsauswahl - Instruction selection
In der Informatik , Befehlsauswahl ist die Stufe eines Compilers Backend , das seine mittlere Ebene transformiert Zwischendarstellung (IR) in einen Low-Level - IR. In einem typischen Compiler geht die Befehlsauswahl sowohl der Befehlsplanung als auch der Registerzuweisung voraus . Daher hat sein Ausgangs-IR einen unendlichen Satz von Pseudoregistern (oft als temporäre Register bezeichnet ) und kann immer noch einer Gucklochoptimierung unterliegen - und ist dies typischerweise auch . Andernfalls ähnelt es stark dem Code , dem Bytecode oder der Assemblersprache des Zielcomputers .
Zum Beispiel für die folgende Sequenz von IR-Code der mittleren Ebene
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
Eine gute Befehlssequenz für die x86-Architektur ist
MOV EAX, a
XCHG EAX, b
ADD a, EAX
Eine umfassende Übersicht zur Anweisungsauswahl finden Sie unter.
Makroerweiterung
Der einfachste Ansatz zur Befehlsauswahl ist als Makroerweiterung oder interpretative Codegenerierung bekannt . Ein Makro-expandierender Befehlswähler arbeitet durch Abgleichen von Vorlagen über dem IR der mittleren Ebene. Bei einer Übereinstimmung wird das entsprechende Makro ausgeführt, wobei der übereinstimmende Teil des IR als Eingabe verwendet wird, der die entsprechenden Zielbefehle ausgibt. Die Makroerweiterung kann entweder direkt in der Textdarstellung des IR der mittleren Ebene erfolgen, oder das IR kann zuerst in eine grafische Darstellung umgewandelt werden, die dann zuerst in der Tiefe durchlaufen wird. In letzterem Fall entspricht eine Vorlage einem oder mehreren benachbarten Knoten im Diagramm.
Wenn der Zielcomputer nicht sehr einfach ist, generiert die isolierte Makroerweiterung normalerweise ineffizienten Code. Um diese Einschränkung zu verringern, kombinieren Compiler, die diesen Ansatz anwenden, ihn normalerweise mit einer Gucklochoptimierung , um Kombinationen einfacher Anweisungen durch komplexere Entsprechungen zu ersetzen, die die Leistung erhöhen und die Codegröße verringern. Dies ist als Davidson-Fraser-Ansatz bekannt und wird derzeit in GCC angewendet .
Grafikabdeckung
Ein anderer Ansatz besteht darin, zuerst das IR der mittleren Ebene in eine grafische Darstellung umzuwandeln und dann das Diagramm mit Mustern abzudecken . Ein Muster ist eine Vorlage, die mit einem Teil des Diagramms übereinstimmt und mit einer einzelnen Anweisung implementiert werden kann, die von der Zielmaschine bereitgestellt wird. Das Ziel besteht darin, den Graphen so abzudecken, dass die Gesamtkosten der ausgewählten Muster minimiert werden, wobei die Kosten typischerweise die Anzahl der Zyklen darstellen, die zur Ausführung des Befehls erforderlich sind. Bei baumförmigen Graphen kann die kostengünstigste Abdeckung in linearer Zeit mithilfe dynamischer Programmierung gefunden werden. Bei DAGs und vollwertigen Graphen wird das Problem jedoch NP-vollständig und wird daher meistens entweder mit gierigen Algorithmen oder mit Methoden aus der kombinatorischen Optimierung gelöst .
Strategie mit dem niedrigsten gemeinsamen Nenner
Die Strategie mit dem kleinsten gemeinsamen Nenner ist eine Befehlsauswahltechnik, die auf Plattformen verwendet wird, auf denen prozessorergänzende Befehle vorhanden sind, um ausführbare Programme auf eine Vielzahl von Computern portierbar zu machen. Bei einer Strategie mit dem kleinsten gemeinsamen Nenner besteht das Standardverhalten des Compilers darin, für die Architektur mit dem niedrigsten gemeinsamen Nenner zu erstellen. Die Verwendung einer verfügbaren Prozessorerweiterung ist standardmäßig deaktiviert, sofern dies nicht ausdrücklich über Befehlszeilenschalter aktiviert wird.
Die Verwendung einer Strategie mit dem kleinsten gemeinsamen Nenner bedeutet, dass Anweisungen und Funktionen , die den Prozessor ergänzen, nicht standardmäßig verwendet werden.