Compiler-Techniken für superskalare Prozessoren
Kompilierung für Instruction Level Parallelism: Basiskonzepte
Eine kurze Routine, die in Schleifenform einem Array b[] neue Werte in Abhängigkeit eines Arrays a[] zuweist, soll einige der Konzepte zeigen. Der Übersetzung in den Assembler-Code liegt ein Pseudocode zu Grunde, der nach dem Schema <OpCode> <DestReg>, <SourceReg1>, <SourceReg2> aufgebaut ist. Ferner sind den Assembler-Befehlen in der Schleife Nummern zugeteilt, um deren Position nach einer Optimierung identifizieren zu können. Für die Bestimmung der Laufzeit einer Schleife gelten folgende Regeln:
Es können prinzipiell beliebig viele Assembler-Befehle parallel zueinander zur Ausführung gelangen. Eine Out-of-Order-Execution wird aber nicht betrachtet.
Die Hardware des Prozessors löst sämtliche virtuellen Hazards wie WAW und WAR auf.
Jeder Speicherzugriff hat einen Zeitbedarf von zwei Takten, alle anderen Befehle von einem Takt.
Falsche Sprungvorhersagen und ihre nötige Korrektur treten im Beispiel nicht auf, der Prozessor durchläuft die Schleifen immer korrekt.
Das Assembler-Listing zeigt unter diesen Umständen folgende Struktur für das Beispielprogramm: Innerhalb der Schleife entstehen vier Basisblöcke, mit L1 bis L4 bezeichnet. Folgendes Bild stellt den Kontrollflussgraphen dar, wie ihn der IF- und der ELSE-Zweig durchlaufen. Pfeile verbinden im Kontrollflussgraph die Basisblöcke, wenn ein entsprechender Übergang möglich ist.