Das Beispiel der Call-Optimierung zeigt, dass auch einzelne Entwickler dem Millionen-Zeilen-Monster GCC Beine machen können. Der Autor hat indirekte Endaufrufe beschleunigt und deren Stack-Konsum eingeschränkt. Der Trick: Die gerufene Funktion recycelt den Stack-Frame der rufenden Funktion.

Die GNU Compiler Collection (GCC)[1] unterstützt viele Sprachen, Betriebssysteme und Hardwareplattformen. Besonders beim Optimieren des erzeugten Codes entwickelt sich die Übersetzersuite kontinuierlich weiter. Was das für Compileranwender und Mitentwickler in der Praxis bedeutet, zeigt dieser Artikel anhand einer neuen Erweiterung: der Optimierung indirekter Endaufrufe.

Die GCC besteht aus einem in C implementierten Kern (dem Backend), der rund eine halbe Million Codezeilen umfasst. Dazu kommen weitere fest integrierte Frontends beispielsweise für Java, Ada oder Fortran, die es zusammen auf mehrere Millionen Zeilen Code bringen. Die Anzahl unterstützter Plattformen ist ebenfalls beeindruckend. Kombiniert man die Betriebssysteme (Linux, Windows, Solaris, HP-UX …) mit den Hardware-Architekturen (i386, Alpha, Sparc …), ergeben sich über 100 Zielplattformen. Kurzum: Die GCC ist riesig und erfordert viel Entwicklungsaufwand für Experten aller Sprachen, Betriebssysteme und Prozessoren.

GCC-Interna: Kompilieren in vielen Stufen

Der Übersetzungsvorgang der GCC ist strikt in Verarbeitungsstufen unterteilt (siehe Abbildung 1). Welche Schritte innerhalb dieser Stufen tatsächlich abzuarbeiten sind, variiert allerdings je nach benutztem Frontend und je nach gewählter Optimierungsstufe. Die eigentliche Optimierungsphase kann sehr kurz ausfallen oder auch viel Zeit beanspruchen, wenn der Anwender besonders performante oder speicherschonende Programme benötigt.

Wichtig ist, dass fast alle Code-Optimierungen auf einer Zwischensprache aufbauen, der Register Transfer Language (RTL). Diese Sprache ist nahezu Hardware-unabhängig. Sie modelliert einen abstrakten Prozessor. Dieser stellt beispielsweise eine Vielzahl Pseudo-Register zur Verfügung, die das Backend am Ende seiner Arbeit auf die physische Zielplattform abbildet.

Lisp-artige Syntax zur Plattform-Beschreibung

Die Zielplattformen sind in einer Lisp-artigen Syntax beschrieben. Aus dieser Spezifikation wird der Code ganzer Teile der Compilersuite generiert – das Übersetzen des Compilers selbst läuft in mehreren Stufen ab. Dieses flexible Design hat den besonderen Vorteil, dass die GCC weitgehend sprach- und plattformunabhängig ist und sich sehr gut als Crosscompiler eignet.

Einen Crosscompiler benötigen Entwickler immer dann, wenn sie zwar auf einer bestimmten Plattform arbeiten, jedoch nativen Code für eine inkompatible Architektur erzeugen müssen. Mit der GCC steht ihnen hierbei für jede Zielplattform ein einheitlicher Compiler zur Verfügung.

Eine der Neuerungen in der GCC- Version 3.4 ist die Optimierung von indirekten Endaufrufen (Tail Calls) auf Intel-kompatiblen Systemen. Bei dieser Technik überführt der Compiler alle Funktionsaufrufe über Zeiger, die am logischen Ende eines Funktionsrumpfs stehen (siehe Listing 1), in eine Jump-Reuse-Sequenz.

Abbildung 1: Die GNU Compiler Collection übersetzt Sourcecode in mehreren Schritten. Als Zwischensprache verwendet sie die Register Transfer Language (RTL). GCC optimiert den Code beim Übergang von RTL in Maschinensprache.

Indirekte Endaufrufe per Jump-Reuse

Jump-Reuse ist im Gegensatz zu einem echten Call nur ein einfacher Sprung zur aufgerufenen Funktion, fast ohne Stack-Operationen. Der Code recycelt den Stack-Frame der aufrufenden Funktion nach dem Sprung und senkt damit das Stack-Wachstum endrekursiver Funktionen von der Ordnung O(n) auf O(1).

Der normale Weg über die Call-Anweisung erlaubt dies nicht (siehe Kasten “Stack und Frame”). Er reserviert einen neuen Stack-Frame unabhängig von der Art des Funktionsaufrufs und überlässt es der Aufrufkonvention der jeweiligen Plattform und Programmiersprache, den Speicher zu einem geeigneten Zeitpunkt wieder freizugeben sowie die Register wieder herzustellen (siehe Abbildung 2). In der Sprache C, in der auch das GCC-Backend geschrieben ist, trägt der Caller (Aufrufer) die Verantwortung für die finalen Aufräumarbeiten.

cvs login

cvs -z 9 co -rBranch-Name gcc

Stack-Overflow vermeiden

Die Endaufrufe optimieren beugt einem Stack-Überlauf vor. Das ist möglich, weil in den meisten Fällen nach einem Endaufruf der aktuelle Stack-Frame der aufrufenden Funktion semantisch nicht mehr von Bedeutung ist. Die Funktion hat zu diesem Zeitpunkt bereits zu Ende gerechnet und müsste nur noch zum Caller zurückkehren.

Dass dieser Artikel nur indirekte Funktionsaufrufe behandelt, geschieht ganz bewusst: GCC optimiert bereits seit geraumer Zeit die direkten Endaufrufe. Indirekte Endaufrufe hingegen sind ein Novum und müssen zusätzlich auf andere Plattformen portiert werden, damit sie auch auf Sparc oder Alpha funktionieren. Die Zahl der künftigen Portierungen hängt natürlich stark vom Engagement der Community ab.

Ein Kritiker könnte argumentieren, dass die meisten C- und C++-Programmierer fast ausschließlich direkte Funktionsaufrufe verwenden. Wer sich der Flexibilität von Zeigeraufrufen bewusst ist, kann auf diesem Wege aber bestimmte Anwendungen stark beschleunigen und den Ressourcenbedarf seiner Programme stabilisieren.

Abbildung 2: Der Stack eines Intel-Rechners, nachdem »f()« die Funktion »g()« und diese wiederum »h()« aufgerufen hat. Neben den lokalen Daten (blau) enthält der Frame die Argumente der gerufenen Funktion und die Verwaltungsdaten RA und BP.

01 int bar (int, int);     /* Deklaration von bar() */
02 int (*fptr) (int, int); /* Funktionszeiger */
03 
04 int foo (int arg1, int arg2)
05 {
06    /* Hier im Rumpf berechnet foo() irgendwas */
07 
08    fptr = bar;
09    return (*fptr) (arg1, arg2); /* indirekter Endaufruf */
10 }

01 // s_zero() ist eine Zustandsfunktion des Automaten
02 // (Vendingmachine). Nach einer action() des Anwenders
03 // erhält sie einen Zeiger auf den nächsten Zustand.
04 // Diesen ruft sie am Ende des Anweisungsrumpfes
05 // indirekt (über Zeiger) auf.
06 
07 void Vendingmachine::s_zero (void)
08 {
09   cur_state = &Vendingmachine::s_zero;
10   // Hier kann s_zero() irgendwas berechnen.
11   transition = action ();
12   (this->*transition) ();
13 }

01 // foo() und bar() weisen den gleichen Return-Typ auf.
02 // Die Argumente belegen auf i386 zusammen jeweils
03 // acht Byte, obwohl sie unterschiedlichen Typs sind.
04 // Einer Tail-Call-Optimierung steht nichts im Weg.
05 
06 int foo (long long a);
07 int bar (short a, short b);

01 int *global;
02 
03 float foo ()
04 {
05   int local = 5;
06 
07   global = &local;
08   // Hier passiert wieder irgendwas.
09   return bar (global);
10 }

Indirekte Endaufrufe nutzen

Ein wichtiges Beispiel ist Continuation Passing Style (CPS) in C und C++. Hier übergibt der Aufrufer einer Funktion dieser einen Zeiger auf die nächste auszuführende Funktion. Der Grundgedanke ist, dass Funktionen in CPS nie zur aufrufenden Funktion zurückkehren müssen, da sie die verbleibenden Berechnungen (also die Programmfortführung) am Ende selbst über einen Funktionszeiger delegieren. Ohne Compiler-Optimierungen wäre das nicht möglich: Funktionen, die nie ein Return ausführen, resultieren in einem Stack-Überlauf. Weitere Beispiele aus der Praxis sind:

• Übersetzen von funktionalen und Logiksprachen (etwa Haskell[2] oder Mercury[3]). GCC dient hierzu oft als portabler Assembler für viele Plattformen. Diese Klasse von Sprachen lässt sich aufgrund der rekursiven Programmstruktur sehr effizient durch CPS realisieren.
• Allgemeine Zustandsmaschinen und Automaten. Alle Einzelzustände lassen sich als Funktionen implementieren, die indirekt Übergangsfunktionen aufrufen, um den internen Zustand zu verändern.
• Virtuelle Maschinen, in denen ein Funktionszeiger stets auf die nächste Funktion zeigt, ähnlich dem allgemeinen Konzept von CPS.

Die Idee der indirekten Zustandsmaschinen ist in Listing 2 zu erkennen. Der gesamte C++-Quelltext, dem dieses kurze Beispiel entnommen ist, liegt auf dem FTP-Server des Linux-Magazins[6].

Abbildung 3: Der Standard-Unix-Stack-Frame der Intel-x86-Architekturen. Die Elemente auf dem Stack werden relativ zu Base- und Stack-Pointer adressiert. Die Register sind durch »ebp« (Base- Pointer) und »esp« (Stack-Pointer) gekennzeichnet.

Implementierung

Um bei einem Endaufruf den aktuellen Stack-Frame (siehe Abbildung 3) wiederzuverwenden, müssen bestimmte technische Voraussetzungen erfüllt sein, die das Backend des Übersetzers prüfen muss. Die wohl einschneidenste Voraussetzung für eine erfolgreiche Optimierung ist die strukturelle Typäquivalenz der beiden Funktionen: Die aufrufende Funktion muss entweder dieselbe Signatur aufweisen wie die aufgerufene oder die unterschiedlichen Typen lassen sich im Speicher auf die gleiche Weise abbilden (siehe Listing 3).

Abbildung 4: Beim optimierten Tail Call (Endaufruf) verwendet die gerufene Funktion »bar()« denselben Stack-Frame wie ihr Aufrufer »foo()«. Damit dies gelingt, müssen die Argumente beider Funktionen den gleichen Platz auf dem Stack belegen: Strukturelle Typäquivalenz nennt sich das im Fachjargon.

Kompatible Argumente

Der Grund für diese stringente Einschränkung ist in Abbildung 4 ersichtlich. Die Optimierung überschreibt die vom Caller übergebenen Argumente einfach mit den neuen. Wenn diese mehr Speicher in Anspruch nehmen würden, dann wäre die Rücksprungadresse (RA) im Weg sowie ein eventuell gespeicherter Base-Pointer (BP). Diese Zellen könnten zwar verschoben werden, doch wenn die Aufrufsequenz zu Ende ist, weiß der ursprüngliche Caller davon nichts und wird daher versuchen, eine falsche Anzahl Argumente von dem Stack zu löschen.

Im Einzelnen laufen bei einem optimierten Endaufruf folgende Schritte ab:

• Die Funktion muss die gesicherten Register des Aufrufers (so vorhanden) erneut herstellen. Gesicherte Register können nicht erst am Ende der Aufrufkette restauriert werden, sondern nur noch vor dem Sprung zur Unterfunktion.
• Sie muss die alten Argumente ihres Aufrufers mit den neuen überschreiben, die sie selbst an die gerufene Funktion übergibt.
• Eventuell muss sie den Base-Pointer (BP) erneut herstellen, wenn der Anwender dies nicht explizit durch den Compiler-Switch »-fomit-frame-pointer« unterdrückt.
• Zuletzt folgt der Sprung an die Zieladresse der gerufenen Funktion, um deren Abarbeitung in Gang zu setzen, ohne einen neuen Stack-Frame zu reservieren (Jump-Reuse).

Leider bleiben noch einige Probleme. Eine der Ursachen ist, dass die Endaufruf-Optimierung für die Oldtimer-Sprache C im Backend zu implementieren ist und nicht in die moderneren Frontends der GCC-Suite.

Schwierige Details

Ein Beispiel: Die aufrufende Funktion darf keine lokalen Variablen definieren, denn es könnte sein, dass eine globale Variable eine Referenz darauf enthält. Code, wie er in Listing 4 zu sehen ist, darf vom Compiler nicht wie oben beschrieben optimiert werden. Die aufgerufene »bar()«-Funktion benötigt auch den Stack-Frame von »foo()«, da sie über den »global«-Zeiger auf die lokale Variable »local« Zugriff hat. Sie darf den Frame also nicht recyceln.

Da C-Compiler im Regelfall keine Lebendigkeitsanalyse von Variablen durchführen, brechen sie die Tail-Call-Optimierung ab, wenn eine lokale Variable definiert ist. (Dieses Beispiel könnte vielleicht einige zur aktiven Mitarbeit an GCC einladen.) Weitere Details zur Implementierung finden sich in der Diplomarbeit[4] des Autors. Sie erörtert weitere Einschränkungen und skizziert Lösungen zu ihrer Überwindung.

Mitarbeit am GCC

Die optimierten indirekten Endaufrufe regen hoffentlich den Appetit auf die Features der neuen GCC-Versionen an (siehe Kasten “Ausblick auf GCC 3.4”). Sie sind ein Beispiel dafür, wie viel eine Einzelperson und sogar ein GCC-Neuling in diesem Projekt bewegen kann. Die GCC ist zwar kein triviales Softwarepaket, in dem man auf die Schnelle umfangreiche neue Funktionalität unterbringen könnte. Trotz akribisch genauer Code-Reviews auf den GCC-Mailinglisten entwickelt sich dieser einzigartige freie Compiler aber trotzdem in rasantem Tempo weiter. (fjl)