Partielle Auswertung einer imperativen Sprache


[Inhalt]Inhaltsverzeichnis [-]1 Einleitung und Grundbegriffe [+]3 Partielle Auswertung und Compilierung

2 Programmspezialisierung


2.1 Allgemeines

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:

  1. Bei gegebenen Werten eines Teils der Eingabe eines Programms wird eine Beschreibung aller Berechnungszustände, die erreichbar sind, wenn das Programm für alle möglichen Eingabewerte läuft, bestimmt.
  2. Die Programmkontrolle wird redefiniert, indem Teile der Datenzustandsinformation in den Kontrollzustand eingearbeitet werden. Unter Umständen ergeben sich daraus keine, eine oder mehrere spezialisierte Versionen jedes Kontrollpunkts des Programms. Daher wird dieser Programmspezialisierungsansatz auch polyvariante Spezialisierung bzw. polyvariante gemischte Berechnung genannt. Daneben gibt es auch andere Ansätze wie z.B. Supercompilierung.
  3. Das resultierende Programm enthält üblicherweise viele triviale Übergänge. Es wird daher mit herkömmlichen Techniken optimiert. Daraus ergibt sich das spezialisierte bzw. residuale Programm.

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.

[Top]

2.2 Zustände, Programmpunkte und Einteilungen

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
begin
  valuelist := tl(valuelist);
  namelist := tl(namelist)
end;
value := hd(valuelist);

[Top]

2.3 Programmpunktspezialisierung

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);
namelist := tl(namelist);
goto search;
  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.

[Top]

2.4 Codeerzeugung

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:

  1. eval(exp,vs)
  2. reduce(exp,vs)

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)

[Top]

2.5 Berechnung von poly

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) };
while poly enthält ein nicht markiertes Paar (pp,vs) do
begin
  markiere (pp,vs);
  generiere Code für den Basisblock, der mit pp beginnt
    (unter Benutzung der Werte in vs)
  poly := poly È successors (pp,vs)
end

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

[Top]

2.6 Übergangskomprimierung

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.

[Top]

2.7 Einteilung (der Variablen)

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.

[Top]

2.8 Bindezeitanalyse

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:

  1. Konstruktion der anfänglichen Einteilung B = (b1, ... bn, S, ... S)
  2. Enthält das Programm eine Zuweisung
      Xk := exp
    wobei Variable Xj in exp vorkommt und bj = D in B gilt, dann wird bk = D in B gesetzt.
  3. Wiederholung von Schritt 2, solange bis sich B nicht mehr ändert. Der Algorithmus endet dann mit einer kongruenten Einteilung B.

[Top]

2.9 Algorithmus für den Programmspezialisierer mix

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:

Eingabe
Ein Subjektprogramm, eine Einteilung seiner Variablen in statische und dynamische und ein Teil der Eingabedaten
Ausgabe
Ein residuales Programm
Algorithmus

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:

 
    (* program  - Subjektprogramm *)
    (* division - Einteilung der Variablen *)
    (* vs0      - Anfangswert des Variablenspeichers *)
    read(program,division,vs0);
      pending := { (pp0,vs0) }; (* pp0 ist der Anfangsprogrammpunkt *)
      (* pending = Menge spez. Programmpunkte, Code noch nicht erzeugt *)
      marked := { };
      (* marked = Menge spez. Programmpunkte, Code schon erzeugt *)
      while pending ¹ { } do begin
        Wähle Element (pp,vs) aus pending und entferne es;
        marked := marked È { (pp,vs) };
        bb := lookup(pp,program); (* Mit pp markierten Basisblock in *)
                      (* program finden *)
        code := initial_code(pp,vs); (* Leerer Basisblock mit Markierung *)
                       (* (pp,vs) *)
        while bb is not empty do begin
        command := first_command(bb);
        bb := rest(bb);
        case command of
          X :=exp:
            if X is classified as static by division
              then vs := vs [X a eval(exp,vs)]; (* Statische Zuweisung *)
              else code := extend(code, X := reduce(exp,vs));
                                          (* Dynamische Zuweisung *)
          goto pp':
            bb := lookup(pp',program); (* Übergangskomprimierung *)
          if exp then goto pp'; else pp'':
            if exp is static by division
              then begin (* Statische Bedingung *)
                if eval(exp,vs) = true
                  then bb := lookup(pp',program); (* Komprimierung *)
                  else bb := lookup(pp'',program); (* Komprimierung *)
              end
              else begin (* Dynamische Bedingung *)
                pending := pending È ( { (pp',vs) } \ marked );
                pending := pending È ( { (pp'',vs) } \ marked );
                code := extend(code, if reduce(exp,vs)
                               goto (pp',vs)
                               else (pp'',vs));
              end;
          return exp:
            code := extend(code, return reduce(exp,vs));
          otherwise error;
       end; (* while bb is not empty *)
       residual := extend(residual,code); (* Neuen Basisblock anfügen *)
     end (* while pending ¹ { } *)

Der besseren Übersichtlichkeit halber fehlt die Umbenennung der Label der spezialisierten Programmpunkte (pp, vs).

[Top] [+]3 Partielle Auswertung und Compilierung


Copyright © 1998 Ulrich Telle - Letzte Änderung: 1. Februar 1998