Dependence analysis

Dependence analysis bzw. die Abhängigkeitsanalyse stellt im Compilerbau die Abhängigkeit zwischen Anweisungen fest. Daraus wird ermittelt wann es sicher ist die Ausführungsreihenfolge von Programmen zu verändern bzw. zu parallelisieren. Allgemein hängt eine Anweisung S2 von S1 ab, wenn S1 vor S2 ausgeführt werden muss. Es gibt zwei Klassen von Abhängigkeiten: Kontrollflussabhängigkeit (control dependence) und Datenabhängigkeit (data dependence).

Kontrollflussabhängigkeit

Kontrollflussabhängigkeit liegt vor im Falle, dass eine Programmanweisung ausgeführt wird, wenn die Auswertung der vorangegangenen Anweisung dies erlaubt. Eine Anweisung S2 ist kontrollflussabhängig von S1 ($S1\ \delta^c\ S2$), genau dann, wenn die Ausführung von S2 von S1 bedingt geschützt ist. Das folgende Beispiel zeigt eine solche Abhängigkeit:

S1       if x > 2 goto L1
S2       y := 3
S3   L1: z := y + 1

S1 bis S3 sind Zeilenbeschriftungen. L1 ist eine Sprungmarke. Hierbei wird S2 nur ausgeführt, wenn die Auswertung bei S1 'True' ergibt.

Datenabhängigkeit

Datenabhängigkeit entsteht bei zwei Anweisungen, die auf dieselben Ressourcen lesen oder schreiben.

Echte Datenabhängigkeit (flow dependence)

Eine Anweisung S2 ist von S1 flow dependent ($S1\ \delta^f\ S2$), genau dann wenn S1 eine Ressource verändert, die von S2 gelesen wird und S1 vor S2 ausgeführt wird. Nachfolgend ein Beispiel für Flow dependence (RAW: Read After Write):

S1       x := 10
S2       y := x + c

Gegenabhängigkeit (antidependence)

Eine Anweisung S2 ist von S1 antidependent ($S1\ \delta^a\ S2$), genau dann wenn S2 eine Ressource verändert, die von S1 gelesen wird und S1 vor S2 ausgeführt wird. Nachfolgend ein Beispiel für Antidependence (WAR: Write After Read):

S1       x := y + c
S2       y := 10

Hierbei schreibt S2 einen Wert in y, aber S1 liest einen vorherigen Wert von y.

Ausgabeabhängigkeit (output dependence)

Eine Anweisung S2 ist von S1 output dependent ($S1\ \delta^o\ S2$), genau dann wenn S1 und S2 dieselbe Ressource verändern und S1 vor S2 ausgeführt wird. Nachfolgend ein Beispiel für Output dependence (WAW: Write After Write):

S1       x := 10
S2       x := 20

Hierbei schreibt sowohl S1 als auch S2 die Variable x.

Eingabeabhängigkeit (input "dependence")

Eine Anweisung S2 ist von S1 input dependent ($S1\ \delta^i\ S2$), genau dann wenn S1 und S2 dieselbe Ressource lesen und S1 vor S2 ausgeführt wird. Nachfolgend ein Beispiel für Input dependence:

S1       y := x + 3
S2       z := x + 5

Hier lesen S1 und S2 die Variable x. Dies ist keine Abhängigkeit im Sinne der anderen, dass eine Änderung der Anweisungsreihenfolge verhindert wird. Einige Compiler jedoch können mit Hilfe dieser Definition Optimierungen finden.

Loop dependence

Das Problem, Abhängigkeiten innerhalb von Schleifen zu berechnen, ist bedeutend und nicht trivial. Es wird in der Schleifenparallelisierung (Loop dependence analysis) verfolgt.

Literatur

• Cooper, Keith D.; & Torczon, Linda.: Engineering a Compiler. Morgan Kaufman Publ Inc, 2005, ISBN 978-1558606982. 
• Kennedy, Ken; & Allen, Randy.: Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufman Publ Inc, 2001, ISBN 1-55860-286-0. 
• Muchnick, Steven S.: Advanced Compiler Design and Implementation. Morgan Kaufmann Publ Inc, 1997, ISBN 1-55860-320-4.