Zusammenfassung

  • Frances E. Allen entwickelte Optimierung von einer Sammlung schneller Tricks zu einer strukturierten Analyse von Kontrollwegen, Definitionen und Verwendungen.
  • Intervalle, erreichende Definitionen und Lebendigkeit liefern bedingte statische Fakten; sie sind weder Ausführungsspuren noch Garantien gegen undefiniertes Verhalten, Datenrennen oder numerische Instabilität.
  • Allens Führungsleistung steht neben den dokumentierten Beiträgen von John Cocke, Reese T. Prosser, E. S. Lowry, C. W. Medlock, Kenneth Kennedy sowie den Stretch-, Harvest- und ACS-Teams.

Soll eine Operation aus einer Schleife herausgezogen werden, braucht der Optimierer mehr als eine Ähnlichkeit im Quelltext. Er muss wissen, welche Definitionen ankommen können, ob eine Zuweisung dazwischenliegt, ob der Wert später noch gebraucht wird und ob sich Ausnahmen oder beobachtbare Reihenfolgen ändern.

Frances E. Allen half, aus diesem Urteil eine berechenbare und überprüfbare Aussage zu machen. Laut IBM kam sie 1957 ins Unternehmen, zunächst um neuen Wissenschaftlern FORTRAN beizubringen. Später arbeitete sie an Stretch–Harvest und am experimentellen Advanced Computing Systems Project. Die ACM würdigte 2006 ihre grundlegenden Beiträge zur Theorie und Praxis optimierender Compiler mit dem Turing Award; sie war die erste Frau, die ihn erhielt.

Die verkürzte Aussage, Allen habe Compileroptimierung erfunden, verfehlt die wichtigste Einsicht. Ihre Methoden gaben dem Compiler eine Sprache dafür, was er unter festgelegten Voraussetzungen tatsächlich weiß.

Ein Graph möglicher Abläufe

In Control Flow Analysis von 1970 werden Basisblöcke zu Knoten und mögliche Kontrollübergänge zu gerichteten Kanten. Ein Basisblock ist im Modell eine lineare Folge mit einem Eintritt und einem Austritt.

Die Kante ist kein Laufzeitprotokoll. Sie bezeichnet eine Möglichkeit, nicht ein eingetretenes Ereignis. Damit ist die erste Beweisgrenze gesetzt.

Allen ordnet den Graphen mit Intervallen. Ein Intervall mit Kopf h ist ein maximaler Teilgraph mit einem Eintritt, in dem jeder geschlossene Pfad h enthält. Ein Knoten wird aufgenommen, wenn alle unmittelbaren Vorgänger bereits im Intervall liegen. Durch wiederholte Reduktion entsteht eine Hierarchie, mit der Schleifen ohne Aufzählung sämtlicher Wege analysiert werden können.

Der Text hält die Vorgeschichte fest. Reese T. Prosser wird für frühe Konnektivitätsmatrizen und die Einführung der Dominanz genannt; E. S. Lowry und C. W. Medlock für deren Ausbau; John Cocke für das Intervallkonzept. Allens Leistung liegt nicht im Löschen dieser Herkunft, sondern in der systematischen Verknüpfung.

Erreichen können heißt nicht ausgeführt worden sein

Allen und Cocke beschreiben 1976 in A Program Data Flow Analysis Procedure, wie zur Übersetzungszeit erreichende Definitionen an Knoten und lebendige Definitionen an Kanten berechnet werden.

Eine Definition erreicht einen späteren Block, wenn sie am Ausgangspunkt verfügbar ist und mindestens ein Weg ohne erneute Definition desselben Datenelements existiert. „Mindestens ein Weg“ macht die Aussage zu einer May-Analyse. Sie deckt konservativ ab, was geschehen könnte, nicht welchen Weg ein konkreter Lauf nahm.

Lebendigkeit beantwortet ebenfalls eine eng umrissene Frage: Kann eine ankommende Definition später von einer exponierten Verwendung gebraucht werden? Das hilft bei Registerbelegung und der Entfernung toter Arbeit. Es beweist weder die Gültigkeit des Werts noch eine sichere Verwendung in jedem Lauf.

Das Verfahren nutzt intervallgeordnete Kanten und Bitvektoren und behandelt reduzierbare wie irreduzierbare Graphen in einem Rahmen. Kenneth Kennedy wird für den Lebendigkeitsalgorithmus, Richard Stasko für Datenstrukturideen genannt; Ullman, Hecht, Kildall, Schaefer, Schwartz und weitere werden als wesentliche Mitwirkende gewürdigt.

Ein Katalog ist kein globaler Optimalitätsbeweis

Der Catalogue of Optimizing Transformations von Allen und Cocke systematisierte gemeinsame Teilausdrücke, Codebewegung, Stärkeverminderung und die Beseitigung redundanter Operationen. Die Autoren nennen den Katalog nicht vollständig und „Optimierung“ irreführend, solange ein allgemeines Optimum nicht definiert ist. Im Mittelpunkt stehen Laufzeit und in geringerem Maß Speicherplatz.

Eine semantisch erlaubte Transformation verbessert deshalb nicht jede Systemeigenschaft. Das Umgruppieren von Gleitkommaoperationen kann Rundungen verändern. Ein scheinbar wiederholtes Lesen darf nicht entfernt werden, wenn die Stelle volatil, geteilt, für ein Gerät sichtbar oder mit einer Ausnahme verbunden ist.

Neben der Graphform benötigt der Optimierer Auswertungsregeln, Aliasmodell, Ausnahmeverhalten und Arithmetikvertrag. Nebenläufigkeit fügt Speichermodell und Synchronisationsordnung hinzu. Eine Zwischendarstellung kann diese Bedingungen ausdrücken, aber nicht aufheben.

Semantiktreue ist keine vollständige Korrektheitsgarantie

Selbst eine perfekt begründete Transformation lässt weitere Fragen offen. Das Quellprogramm kann bei bestimmten Eingaben undefiniertes Verhalten zeigen, ein Datenrennen enthalten, Rundungsfehler verstärken oder eine falsche Anforderung implementieren. Der Compilerbeweis zertifiziert diese Ebenen nicht automatisch mit.

Diese Begrenzung ist eine Stärke. Eine brauchbare Analyse kann genau sagen: Für diesen Graphen, diese Definitionen und Verwendungen und diese semantischen Bedingungen gilt die Beziehung. Das institutionelle Problem beginnt, wenn daraus nur ein grünes Feld „korrekt“ wird.

Auch Allens Geschichte braucht diese Genauigkeit. IBM beschreibt sie als Gestalterin und Sprachvermittlerin bei Stretch–Harvest und zentrale Figur der ACS-Compilerarbeit. Das IEEE-Computer-Society-Profil verbindet den Bericht Program Optimization von 1966, die Intervalle und den Transformationskatalog. Das ACM-Profil von John Cocke bewahrt seinen eigenen Anteil. Hardware-, Sprach- und Compilerteams machten die Abstraktionen einsatzfähig.

Allens Vermächtnis ist kein allwissender Compiler. Es ist ein Compiler, der präzise angeben kann, was er bewiesen hat.

Quellen