Übungsblatt 7

In dieser Übung soll eine statische Analyse entsprechend der Vorlesung vom 11.12 durchgeführt werden. Alle Begrifflichkeiten beziehen sich auf diese Vorlesung.

Aufgabe 1: Kontrollfluss

Ermitteln Sie für folgendes Programm die Mengen \(init\), \(final\) und \(flow\):

1if (x < y) {
2  a := y;
3  y := x;
4  x := a;
};
5a := x;
6b := y;
7while (x != y) {
8  a := y;
9  while (x > y) {
10    x := x - y;
  };
11  b := y;
12  y := x;
13  x := a;
};

\(init = \,\)

\(final =\{\)\(\}\)

\(\begin{array}{ll} blocks = \{&[x < y]^1, [a := y]^2, [y := x]^3, [x := a]^4,\\ & [a := x]^5, [b := y]^6, [x != y]^7, [a := y]^8,\\ &[x > y]^9, [x := x - y]^{10}, [b := y]^{11}, [y := x]^{12},\\ &[x := a]^{13} \} \end{array} \)

\(flow =\{\)\(\}\)

\(flow^r = \{\}\)

Aufgabe 2: Statische Analyse

Führen Sie eine Live Variable Analyse durch indem sie die folgenden Tabellen vervollständigen: (Für die leere Menge \(\varnothing\) lassen sie die entsprechenden Felder einfach frei)

\(l\)\(kill(l)\)\(gen(l)\)
\(1\) \(\{\)\(\}\) \(\{\)\(\}\)
\(2\) \(\{\)\(\}\) \(\{\)\(\}\)
\(3\) \(\{\)\(\}\) \(\{\)\(\}\)
\(4\) \(\{\)\(\}\) \(\{\)\(\}\)
\(5\) \(\{\)\(\}\) \(\{\)\(\}\)
\(6\) \(\{\)\(\}\) \(\{\)\(\}\)
\(7\) \(\{\)\(\}\) \(\{\)\(\}\)
\(8\) \(\{\)\(\}\) \(\{\)\(\}\)
\(9\) \(\{\)\(\}\) \(\{\)\(\}\)
\(10\) \(\{\)\(\}\) \(\{\)\(\}\)
\(11\) \(\{\)\(\}\) \(\{\)\(\}\)
\(12\) \(\{\)\(\}\) \(\{\)\(\}\)
\(13\) \(\{\)\(\}\) \(\{\)\(\}\)

\(l\)\(LV_{in}\)\(LV_{out}\)
\(1\) \(\{\)\(\}\) \(\{\)\(\}\)
\(2\) \(\{\)\(\}\) \(\{\)\(\}\)
\(3\) \(\{\)\(\}\) \(\{\)\(\}\)
\(4\) \(\{\)\(\}\) \(\{\)\(\}\)
\(5\) \(\{\)\(\}\) \(\{\)\(\}\)
\(6\) \(\{\)\(\}\) \(\{\)\(\}\)
\(7\) \(\{\)\(\}\) \(\{\)\(\}\)
\(8\) \(\{\)\(\}\) \(\{\)\(\}\)
\(9\) \(\{\)\(\}\) \(\{\)\(\}\)
\(10\) \(\{\)\(\}\) \(\{\)\(\}\)
\(11\) \(\{\)\(\}\) \(\{\)\(\}\)
\(12\) \(\{\)\(\}\) \(\{\)\(\}\)
\(13\) \(\{\)\(\}\) \(\{\)\(\}\)

Aufgabe 3: Optimierung

Welche elementaren Blöcke können nach den Erkenntnissen der Live Variable Analyse aus dem Programm entfernt werden ohne die Semantik zu verändern?

1if (x < y) {
 2  a := y;
 3  y := x;
 4  x := a;
 };
 5a := x;
 6b := y;
 7while (x != y) {
 8  a := y;
 9  while (x > y) {
 10    x := x - y;
   };
 11  b := y;
 12  y := x;
 13  x := a;
 };

Autoren
Name Matrikelnummer E-Mail
1.
2.
3.

Es werden keine Daten übertragen. Per Klick auf "Ergebnis speichern" kann eine Datei gespeichert werden, welche die eingegebenen Ergebnisse enthält. Diese Datei sendet ihr bitte rechtzeitig bis Dienstag 23:59:59 an martin (punkt) ring (klammeraffe) dfki (punkt) de. Ihr könnt eure Abgabe später auch wieder laden und ansehen indem ihr auf "Ergebnis laden" klickt.

Ergebnis speichern | Ergebnis laden: