Partielle Auswertung einer imperativen Sprache
Eine Programmspezialisierung kann in drei Schritten vollzogen werden. Alle drei Schritte sind im wesentlichen unabhängig von der speziellen Programmiersprache, die transformiert wird. Es wird davon ausgegangen, daß jedes Programm eine Menge von Programmpunkten besitzt. Damit sind zum Beispiel Label in einer Flußdiagrammsprache, Funktionsnamen in einer funktionalen Sprache oder Prozedurnamen (Prädikate) in einer logischen Programmiersprache gemeint. Die drei Schritte im Algorithmus der Programmspezialisierung sind:
Damit der Programmspezialisierer mix so einfach und lesbar wie möglich bleibt, wird die Existenz von Bibliotheksfunktionen vorausgesetzt, die lästige Arbeiten erledigen, die für die Konzepte der partiellen Auswertung jedoch nicht entscheidend sind.
Für jeden beliebigen Zeitpunkt während der Ausführung eines Programms wird ein Berechnungszustand als Paar (pp, store) geschrieben. Dabei bezeichnet pp den Programmpunkt, der den aktuellen Kontrollpunkt markiert, und store den aktuellen Inhalt aller Programmvariablen. Ein Speicher, der die aktuellen Werte der Variablen X1, ... Xn enthält, wird durch eine Liste der Form (v1, ... vn) dargestellt. Wenn eine Zuweisung ausgeführt wird, wird der Speicher store aktualisiert und pp auf den nächsten Programmpunkt gesetzt; wenn eine Bedingung ausgewertet oder ein goto ausgeführt wird, wird nur der Kontrollpunkt aktualisiert.
Ist nur ein Teil der Eingabedaten gegeben, so kann das Programm zwar nicht ausgeführt werden, aber es kann in Bezug auf die bekannten Eingabedaten spezialisiert werden. In diesem Fall sind zu Beginn und während der Spezialisierung die Werte einiger Variablen unbekannt; Der Speicherzustand kann daher zu Beginn und später nur unvollständig beschrieben werden. Daraus ergibt sich, daß zur Spezialisierungszeit in der Regel nicht alle Ausdrücke des Subjektprogramms ausgewertet werden können.
Eine einfache Methode, einen solchen unvollständigen Speicher zu beschreiben, ist, jede Variable als statisch zu klassifizieren, wenn ihre Werte zur Programmspezialisierungszeit bestimmt werden können, und als dynamisch, wenn sie nicht statisch ist. Ein partieller Berechnungszustand kann dann als Paar der Form (pp, vs) notiert werden, wobei vs eine Liste der Werte der statischen Variablen ist. Die Werte der dynamischen Variablen sind unbekannt.
Eine solche Klassifikation der Variablen als statisch oder dynamisch wird Einteilung (englisch division) genannt. Sofern nicht explizit etwas anderes angegeben wird, wird im folgenden angenommen, daß dieselbe Einteilung für alle Programmpunkte Gültigkeit hat. Eine solche Einteilung wird uniform genannt. Diese Annahme vereinfacht die Betrachtungen und trifft in der Praxis häufig zu.
Bei der Programmspezialisierung ist eine (uniform) kongruente Einteilung eine wesentliche Voraussetzung. Damit ist gemeint, daß bei jedem Übergang von einem Zustand (pp, store) zu einem Zustand (pp', store') die Werte der statischen Variablen im Programmpunkt pp' aus den Werten der statischen Variablen im Programmpunkt pp berechenbar sein müssen. Anders ausgedrückt muß jede Variable, die von einer dynamischen Variablen abhängt, selbst dynamisch sein.
Ein Ausdruck wird statisch genannt, wenn er ausschließlich Konstanten und statische Variablen enthält, und dynamisch, wenn er dynamische Variablen enthält. Ist in folgender Zuweisung eines Subjektprogramms
X := exp
|
der Ausdruck exp dynamisch, dann muß auch die Variable X wegen der Kongruenzbedingung dynamisch sein.
Unter der Annahme, daß in dem Programmfragment aus Abschnitt 1.6 die Variablen name und namelist statisch und die Variablen value und valuelist dynamisch sind, wird in keiner der Zuweisungen die Kongruenzbedingung verletzt:
while name ¹ hd(namelist) do
|
Wird zur Programmspezialisierungszeit während der Berechnung ein Programmpunkt pp mit Werten der statischen Variablen vs erreicht, werden die Werte der statischen Variablen in den Programmpunkt eingearbeitet, indem das Paar (pp, vs) zu einem Programmpunkt des residualen Programms gemacht wird. Das Paar (pp, vs) wird auch als spezialisierter Programmpunkt bezeichnet. Der Code, den (pp, vs) im residualen Programm markiert, ist eine optimierte Version des Codes an der Stelle pp des Subjektprogramms, da die Werte der statischen Variablen bekannt sind. Ein und derselbe Programmpunkt pp kann in unterschiedlichen Varianten mit jeweils anderen Werten für die statischen Variablen im residualen Programm auftreten.
Diese Vorgehensweise wird Programmpunktspezialisierung genannt und soll an dem aus den vorangegangenen Abschnitten bekannten Programmfragment verdeutlicht werden. Allerdings muß nun auf die Verwendung Pascal-ähnlicher Kontrollstrukturen verzichtet werden, um zu explizit benannten Programmpunkten zu gelangen:
search: | if name = hd(namelist) goto found else
cont; | |
cont: | valuelist := tl(valuelist); | |
found: | value := hd(valuelist); |
Zu Beginn habe die Variable name den Wert z und die Variable namelist den Wert (x y z). Wird nun die Spezialisierung im Programmpunkt search begonnen, dann ist der Anfangswert von vs im Spezialisierer das Paar:
vs = (z,(x y z))
|
Bei der Ausführung des Programms kann die Liste vs im Programmpunkt search drei verschiedene Wert annehmen, nämlich (z,(x y z)), (z,(y z)) und (z,(z)). Im Programmpunkt cont kann vs die ersten beiden der aufgeführten Werte annehmen und im Programmpunkt found hat vs als einzigen Wert (z,(z)).
Im residualen Programm ist der Wert von vs in den spezialisierten Programmpunkt (pp, vs) eingebaut. Die Menge aller spezialisierten Programmpunkte (pp, vs), die während der Ausführung des Subjektprogramms erreichbar sind, werden poly genannt. Poly repräsentiert daher die Menge der Programmpunkte im residualen Programm. In obigem Beispiel ergibt sich:
poly = | { (search, (z,(x y z))), (search, (z,(y z))), (search, (z,(z))), (cont, (z,(x y z))), (cont, (z,(y z))), (found, (z,(z))) } |
Bevor gezeigt wird, wie die Berechnung von poly erfolgen kann, wird zunächst die Codeerzeugung für das residuale Programm beschrieben.
Im Subjektprogramm markiert der Label pp des betrachteten, spezialisierten Programmpunkts (pp, vs) einen Basisblock, der aus einer Folge von Befehlen besteht. Der generierte Code für einen Basisblock ist die Aneinanderreihung des Codes, der für diese Befehle generiert wird.
Für die eigentliche Codeerzeugung wird die Existenz von zwei Bibliotheksfunktionen vorausgesetzt:
wobei exp ein Ausdruck und vs eine Werteliste der statischen Variablen des Programms ist. Die Funktion eval gibt den Wert des statischen Ausdrucks exp zurück, während die Funktion reduce eine Konstantenfaltung des statischen Teils des dynamischen Ausdrucks durchführt. Wenn vs z.B. besagt, daß b = 2 gilt, dann kann der Ausdruck b * b + a ersetzt werden durch 4 + a. Für einen statischen Ausdruck exp liefert die Funktion reduce den Wert des Ausdrucks, eval(exp,vs), als konstanten Ausdruck zurück.
In der nachfolgenden Tabelle wird für jede gültige Anweisung der imperativen Sprache die zur Spezialisierungszeit durchzuführende Berechnung sowie der daraus resultierende erzeugte Code angegeben:
Befehl im Subjektprogramm | Zur Spezialisierungszeit | Erzeugter Code |
X := exp (X dynamisch) | reduced_exp := reduce(exp,vs) | X := reduced_exp |
X := exp (X statisch) |
val := eval(exp,vs); vs := vs [X a val] |
|
return exp | reduced_exp := reduce(exp,vs) | return reduced_exp |
goto pp' | goto (pp',vs) | |
Code für if exp goto pp'; else pp'' | ||
(wenn exp dynamisch) | reduced_exp := reduce(exp,vs) |
if reduced_exp goto (pp', vs) else (pp'', vs) |
(wenn exp statisch und val=true) | val := eval (exp, vs) | goto (pp', vs) |
(wenn exp statisch und val=false) | val := eval (exp, vs) | goto (pp'',vs) |
Wenn der erste Label im Programm mit pp0 und die Anfangswerte der statischen Daten mit vs0 bezeichnet werden, dann muß selbstverständlich (pp0, vs0) in poly enthalten sein. Ist darüber hinaus irgendein Programmpunkt (pp, vs) in poly enthalten, so müssen alle spezialisierten Programmpunkte, die von (pp, vs) erreichbar sind, ebenfalls enthalten sein. Die Menge poly ist somit der Abschluß von vs0 unter der Relation 'erreichbar von'.
Der Label pp eines spezialisierten Programmpunkts (pp, vs) markiert einen Basisblock des Subjektprogramms. Ein Basisblock besteht aus einer Sequenz von Zuweisungen und wird durch eine 'Kontrollübergabe' beendet. Einige Zuweisungen mögen statische Variablen verändern. Das zieht zwangsläufig eine Aktualisierung der Einträge in der Werteliste vs der statischen Variablen nach sich, so daß ein neuer spezialisierter Programmpunkt die Form (pp', vs') hat. Die Menge der Nachfolger hängt natürlich von der Form der Kontrollübergabe ab. Die Menge der möglichen Nachfolger wird mit successors(pp,vs) bezeichnet. Sie hat zwei Elemente für eine dynamische Bedingung, keines für ein return und sonst eines. Für das Beispiel aus Abschnitt 1.6 ergibt sich daraus:
successors (search, (z,(x y z))) successors (search, (z,(z))) successors (cont, (z,(x y z))) |
= = = |
{ (cont, (z,(x y z))) } { (found, (z,(z))) } { (search, (z,(y z))) } |
usw.
Aus der Kombination der Codeerzeugung mit der Berechnung von poly ergibt sich eine erste Annäherung an die allgemeine Struktur des Programmspezialisierers mix:
poly := { (pp0,vs0) };
|
In der nachfolgenden Tabelle sind die Regeln für die Berechnung der Nachfolger angegeben:
Kontrollkomponente von pp |
successors (pp, vs) | Bemerkung |
return |
{ } |
|
goto pp' | { (pp', vs') } | |
if exp goto pp' else pp'' |
{ (pp', vs') } { (pp'', vs') } { (pp', vs'), (pp'', vs') } |
wenn exp true ist wenn exp false ist wenn exp dynamisch ist |
Wenn das Beispielsubjektprogramm ganz genau nach dem oben gegebenen Algorithmus spezialisiert wird, ergibt sich folgendes residuales Programm:
(search, (z,(x y z))): | goto (cont, (z,(x y z))); | |
(cont, (z,(x y z))): | valuelist := tl(valuelist); goto (search, (z,(y z))); |
|
(search, (z,(y z))): | goto (cont, (z,(y z))); | |
(cont, (z,(y z))): | valuelist := tl(valuelist); goto (search, (z,(z))); |
|
(search, (z,(z))): | goto (found, (z,(z))); | |
(found, (z,(z))): | value := hd(valuelist); |
Das Ergebnis ist zwar korrekt, aber nicht sehr befriedigend, da es eine Reihe überflüssiger goto's enthält. Eine Möglichkeit, überflüssige goto's zu beseitigen, besteht darin, Anweisungen der Form goto pp durch Kopien des Basisblocks mit dem Label pp zu ersetzen. Diese Technik wird Übergangskomprimierung genannt.
Mit Hilfe der Übergangskomprimierung ergibt sich für das Beispiel das folgende residuale Programm:
(search, (z,(x y z))): | valuelist := tl(valuelist); | |
valuelist := tl(valuelist); | ||
value := hd(valuelist); |
Die Vorteile der Komprimierung sind offensichtlich: der Code wird klarer und effizienter. Zusammengesetzte Label sollten noch durch einen einfachen Identifizierer, eine Zahl oder einen Namen, ersetzt werden.
Die unkritische Verwendung der Übergangskomprimierung birgt allerdings zwei Fallen: Codeduplizierung und unendliche Komprimierung.
Codeduplizierung kann auftreten, wenn mehrere unterschiedliche Übergänge zum gleichen Programmpunkt komprimiert werden. Enthält das residuale Programm eine Schleife, kann die Komprimierung sogar unendlich sein.
Führt man die Übergangskomprimierung als separate Phase nach der Generierung des residualen Programms durch, können die oben genannten Probleme leicht vermieden werden. Es kann ein Programmflußplan erzeugt und analysiert werden, um festzustellen, welche Übergänge sicher komprimiert werden können. In der Praxis ist es allerdings wünschenswert, die Komprimierung während der Codeerzeugung durchzuführen, da es effizienter ist, erst gar keine überflüssigen goto's, die anschließend nur wieder entfernt werden müssen, zu erzeugen. Die begleitende Komprimierung erschwert allerdings die Gewährleistung einer sicheren Komprimierung. In Kapitel 5 von [1] wird diese Problematik genauer untersucht.
An dieser Stelle wird eine einfache Strategie verwendet: Alle Übergänge, die nicht Teil einer residualen Bedingung sind, werden komprimiert. Residuale Bedingungen sind Bedingungen, die dynamische Variablen enthalten. Diese Strategie bewirkt einige Codeduplizierungen, aber die Erfahrung zeigt, daß dies kaum ein Problem darstellt. Wichtiger ist, daß diese Strategie keine Endlosschleifen verursacht, außer wenn das Subjektprogramm selbst eine potentielle Endlosschleife enthält, d.h., daß allein die statischen Daten, unabhängig von den dynamsichen Daten, eine Endlosschleife bewirken können.
Die Aufgabe, Variablen als statisch oder dynamisch zu klassifizieren, ist schwieriger als es zunächst scheint. Eine naheliegende Strategie wäre es, alle Variablen, denen aus Konstanten und statischen Eingabedaten berechnete Werte zugewiesen werden, als statisch zu bezeichnen. Wie sich jedoch an einem einfachen Beispiel zeigen läßt, kann diese Strategie dazu führen, daß der Programmspezialisierer in eine Endlosschleife gerät:
Iterate: | if Y ¹ 0 then begin X := X + 1; Y := Y - 1; goto iterate; end; |
Dieses unscheinbare Programm enthält zwei Variablen, X und Y. Wenn der Anfangswert von X bekannt - z.B. 0 - und der von Y unbekannt ist, erscheint es plausibel, X als statisch und Y als dynamisch zu klassifizieren, da der Wert des Ausdrucks X+1 zur Spezialisierungszeit berechnet werden kann. Leider funktioniert das nicht.
Zu Beginn enthält poly den spezialisierten Programmpunkt (iterate, 0). Mischt man wie in der Praxis üblich die Berechnung von poly mit der Codeerzeugung, so ergibt sich:
(iterate, 0): | if Y ¹ 0 then begin Y := Y - 1; goto (iterate, 1); end; |
Daraus folgt unmittelbar, daß (iterate, 1) zu poly hinzugefügt werden muß. Also muß dem residualen Programm der Code
(iterate, 1): | if Y ¹ 0 then begin Y := Y - 1; goto (iterate, 2); end; |
hinzugefügt werden. Und so geht es bis in alle Ewigkeit weiter. Die Menge poly wird also unendlich:
poly = { (iterate, 0), (iterate, 1), (iterate, 2), ... } |
Das Problem entsteht dadurch, daß der Wert der Variablen X zwar bekannt ist, aber unter dynamischer Kontrolle berechnet wird. Daher müssen solche Variablen ebenfalls als dynamisch klassifiziert werden. Eine Einteilung, die die Endlichkeit von poly garantiert, wird selbst endlich genannt.
Der Prozeß, eine Variable X als dynamisch zu klassifizieren, auch wenn die Kongruenz eine Klassifizierung als statisch zugelassen hätte, wird Generalisierung genannt. Generalisierung kann zur Verhinderung nicht-terminierender partieller Auswertung erforderlich sein.
Läßt man die Endlichkeitsproblematik außer acht und nimmt zudem an, daß dieselbe Einteilung der Variablen für jeden Programmpunkt anwendbar ist, so läßt sich die Einteilung aller Programmvariablen bei gegebener Einteilung der Eingabevariablen auf einfache Weise berechnen. Dieser Prozeß wird Bindezeitanalyse genannt, da er feststellt, zu welcher Zeit der Wert einer Variablen berechnet werden kann, d.h., wann der Wert an die Variable gebunden werden kann.
Seien X1, X2, ... XN alle Programmvariablen und X1, X2, ... Xn die Eingabevariablen, wobei 0 £ n £ N gilt, und sei eine Anfangseinteilung b1, ... bn der Eingabevariablen gegeben, wobei jedes bj entweder den Wert S (statisch) oder D (dynamisch) hat.
Eine kongruente Einteilung B = (b1, b2, ... bN) aller Programmvariablen läßt sich dann wie folgt berechnen:
Nachdem nun alle für die Programmspezialisierung benötigten Techniken beschrieben wurden, kann eine mögliche Struktur eines Algorithmus für einen Programmspezialisierer, der diese Techniken aufeinanderfolgend anwendet, angegeben werden:
Diese Struktur spiegelt die Prinzipien der Programmspezialisierung gut wider, ist aber in der Praxis ineffizient, da zunächst ein großes residuales Programm erzeugt und erst in einem folgenden Schritt die reduzierte endgültige Fassung erzeugt wird.
Einen effizienteren Algorithmus für den Programmspezialisierer mix erhält man, wenn die Phasen vermischt werden:
|
Der besseren Übersichtlichkeit halber fehlt die Umbenennung der Label der spezialisierten Programmpunkte (pp, vs).
3 Partielle Auswertung und Compilierung