Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

Beispiel eines optimierenden RISC-Compilers

Der XL-Compiler für das RISC-System 6000 von Big Blue

28.09.1990

Daß durch den Einsatz eines Optimierers beim Übersetzen eines Quellprogramms ein schneller ablaufendes Programm erzeugt werden kann, ist bekannt. Welche Techniken verwendet werden, ist schon weniger bekannt. Welche "Geheimnisse" sich hinter den optimierenden RISC- Compilern verbergen, wissen nur Experten.

Optimierungstechniken lassen sich in zwei Kategorien einteilen: hardwareunabhängige und hardwareabhängige. Die von der Maschinenarihitektur unabhängigen sind schon lange, zumindest in der Theorie, bekannt und in den meisten Optimierern implementiert. Hierzu gehören zum Beispiel Techniken wie das Eliminieren gemeinsamer Teilausdrücke, die Optimierung von Schleifen durch Verschieben sogenannter schleifeninvarianter, das heißt bei den Schleifendurchläufen nicht veränderter, Berechnungen aus Schleifen heraus und die Eliminierung nicht erreichbaren Codes.

Auf Grund ihrer für den Compilerbauer relativ einfachen Struktur bieten CISC-Prozessoren wenig Möglichkeiten, durch geeignete Optimierungen die Stärken eines Prozessors besonders auszunutzen. Einzig eine effiziente Nutzung der Register kann hier erreicht werden.

RISC-Architekturen zeichnen sich dagegen durch eine Reihe von Hardware-Eigenschaften aus, die die Entwicklung neuer Optimierungstechniken notwendig machte. Als Beispiel der 2. Generation von RISC-Prozessoren sollen die Architektur des IBM RISC Systems 6000 und die darauf zugeschnittenen Optimierungen erläutert werden.

Die Architektur des RISC Systems 6000 zeichnet sich durch drei kooperierende Prozessoren aus, die echt parallel arbeiten können: eine Branch Unit (ICU), eine Fixed Point (FXU) Unit und eine Floating Point Unit (FPU). Die ICU enthält das Condition Code Register, in dem mehrere Condition Codes abgelegt werden können.

Eine neue Compilergeneration, die XL-Compiler für die Sprachen C, Fortran und Pascal wurde entwickelt, um auf die Erfordernisse der neuen Hardware eingehen zu können. Alle drei Compiler erzeugen Zwischencode in einer gemeinsamen Zwischensprache. Das hat den Vorteil, daß eine gemeinsame Optimierung für alle drei Sprachen durchgeführt werden kann.

Die Übersetzung erfolgt in vier Phasen

Die Übersetzung durch die XL-Compiler wird in vier Phasen durchgeführt:

- Syntaxanalyse und Generierung des Zwischencodes,

- Optimierung für eine Maschine mit unendlich vielen Registern,

- Registerzuordnung und Umwandlung des Codes für eine Maschine mit endlich vielen Registern und

- Codegenerierung.

Zu den in der 7-Seiten-Phase durchgeführten Optimierungen zählen:

- "strength reduction".

Hierbei wird versucht, die Multiplikation von sogenannten Induktionsvariablen in Schleifen durch einfachere Operationen zu ersetzen. Normalerweise wird dies durch zusätzliche Additionen erreicht. Auf der RS/6000 können die meisten solcher Additionen durch einen besonderen update-Mechanismus zusammen mit einer loadbeziehungsweise store-Instruktion durchgeführt werden.

- "reassociation"

Hier werden ganzzahlige Ausdrücke so umgeordnet, daß weitere Optimierungstechniken angewendet werden können. Vor allem sollen Ausdrücke, die Adressen berechnen, vereinfacht werden, um so die load- und store-Operationen, die die einzigen sind, die auf den Speicher zugreifen, zu optimieren.

- Eine weitere, eng mit den schon beschriebenen Techniken zusammenhängende, optimiert Schleifendurchläufe, wenn die Anzahl der Durchläufe vor Eintritt in die Schleife bekannt ist. Durch die Verwendung der branch on count-Instruktion, die von der ICU ausgeführt und somit parallel zu FPU- beziehungsweise FXU-Instruktionen ausgeführt werden kann, wird sehr häufig ein zusätzlicher Zyklus gespart.

- Eine andere, allerdings hardwareunabhängige Technik, ist das "procedure inlining." Kurze, nicht rekursive Prozedurrümpfe werden an die aufrufende Stelle kopiert. Die zwei Vorteile sind: das Vermeiden des Overheads von Prozeduraufrufen und die Möglichkeit, auf dem neu entstandenen Code weitergehende Optimierungen durchzufahren.

- Ähnliches kann durch das "loop unrolling" erreicht werden. Ist die Anzahl der Schleifendurchläufe vor Eintritt in die Schleife bekannt, kann der Schleifenrumpf mehrfach kopiert werden, damit er anschließend sequentiell durchlaufen werden kann. Auch hier entstehen auf dem neuen Code in der Regel weitergehende Optimierungsmöglichkeiten.

- Die Möglichkeit, mehrere Condition Codes in der ICU zur Verfügung zu stellen, befreit den Code Generator von der Notwendigkeit, das Ergebnis bestimmter Instruktionen auszugeben; sofort nach deren Ausführung der Instruktionen kann hier "ohne Rücksicht" auf alte Condition Codes eine bessere Parallelität erreicht werden.

- Diese Technik, das "instruction scheduling", ist eine der wesentlichen Optimierungstechniken für Superskalararchitekturen. Das erste Ziel des Optimierers ist es, einen möglichst gleichmäßigen Durchsatz durch die drei Prozessoren zu erreichen. Zum Beispiel entsteht zwischen dem Laden eines Registers (einer FXU-Operation) und der Verwendung des geladenen Werts eine Verzögerung von einem Zyklus.

Verzögerung läßt sich vermeiden

Kann durch Einfügen einer anderen FXU-Instruktion dieser Zyklus genutzt werden, kann die Verzögerung vermieden werden. Da auch Floating-point-Werte durch die FXU geladen, anschließend aber von der FPU verarbeitet werden, entstehen hier in der Regel keine Verzögerungen.

Die hier vorgestellten Techniken sind nur ein kleiner Einblick in die Möglichkeiten der Optimierung für RISC-Architekturen. Bei anderen RISC-Prozessoren, die zum Beispiel eine sehr große Zahl von Registern unterstützen, sind wieder andere Techniken notwendig. +