Seite 1 von 1

Programmier-Tipp DVNT / Copy-Propagation

Verfasst: 2. Jul 2008 18:26
von koch
Wie einige von Ihnen bereits herausgefunden haben, kann man die für die vierte Aufgabe wichtigsten Teile der Copy-Propagation (zum Erzeugen der kritischen SSA-Fälle) auch schon im DVNT erschlagen. Die dazu nötige kleine Erweiterung ist im Paper ``Value Numbering'' (ebenfalls unter Beteiligung von Herr Briggs, diesmal aber ohne größere Fehler ;-)) beschrieben (Seiten 5-8) und im Algorithmus aus Abbildung 4 (auf Seite 6) umgesetzt.

Speziell geht es hier darum, die Wertetabellen eines Blockes auch in die auf ihn folgenden Phi-Funktionen zu propagieren. Obwohl das klassische DVNT (aus der Vorlesung) ja seine aktuelle Wertetabelle vergisst, wenn es auf einen Join-Block trifft (da wird ja die des Dominators verwendet!), ist die aktuelle Wertetabelle natürlich genau für das diesem Block entsprechende Argument der Phi-Funktion noch gültig. Auf diese Art und Weise können Werte (Kopien) aus den Vorgängerblöcken in die Phi-Funktionen propagiert werden, ohne dass eine echte Copy-Propagation erforderlich ist.

Wenn Ihnen also die Copy Propagation noch Schwierigkeiten macht, können Sie diese weglassen (ohne negativen Einfluss auf die Note ;-)) und stattdessen Ihr DVNT wie bei Briggs beschrieben leicht erweitern.