Dependence analysis

In compiler theory, '''dependence analysis''' produces execution-order constraints between statements/instructions. Broadly speaking, a statement ''S2'' depends on ''S1'' if ''S1'' must be executed before ''S2''. Broadly, there are two classes of dependencies--'''control dependencies''' and '''data dependencies'''.

Dependence analysis determines whether it is safe to '''reorder''' or '''parallelize''' statements.

== Control dependencies == {{Main|Control dependency}} Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.

A statement ''S2'' is ''control dependent'' on ''S1'' (written <math>S1\ \delta^c\ S2</math>) if and only if ''S2'''s execution is conditionally guarded by ''S1''. ''S2'' is ''control dependent'' on ''S1'' if and only if <math>S1 \in PDF(S2)</math> where <math>PDF(S)</math> is the post dominance frontier of statement <math>S</math>. The following is an example of such a control dependence:

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

Here, ''S2'' only runs if the predicate in ''S1'' is false. == Data dependencies == {{Main|Data dependency}} A data dependence arises from two statements which access or modify the same resource.

=== Flow(True) dependence ===

A statement ''S2'' is '''flow dependent''' on ''S1'' (written <math>S1\ \delta^f\ S2</math>) if and only if ''S1'' modifies a resource that ''S2'' reads and ''S1'' precedes ''S2'' in execution. The following is an example of a flow dependence (RAW: Read After Write):

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

=== Antidependence ===

A statement ''S2'' is '''antidependent''' on ''S1'' (written <math>S1\ \delta^a\ S2</math>) if and only if ''S2'' modifies a resource that ''S1'' reads and ''S1'' precedes ''S2'' in execution. The following is an example of an antidependence (WAR: Write After Read):

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

Here, ''S2'' sets the value of <code>y</code> but ''S1'' reads a prior value of <code>y</code>.

=== Output dependence ===

A statement ''S2'' is '''output dependent''' on ''S1'' (written <math>S1\ \delta^o\ S2</math>) if and only if ''S1'' and ''S2'' modify the same resource and ''S1'' precedes ''S2'' in execution. The following is an example of an output dependence (WAW: Write After Write):

S1 x := 10 S2 x := 20

Here, ''S2'' and ''S1'' both set the variable <code>x</code>.

=== Input dependence ===

A statement ''S2'' is '''input dependent''' on ''S1'' (written <math>S1\ \delta^i\ S2</math>) if and only if ''S1'' and ''S2'' read the same resource and ''S1'' precedes ''S2'' in execution. The following is an example of an input dependence (RAR: Read-After-Read):

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

Here, ''S2'' and ''S1'' both access the variable <code>x</code>. This dependence does not prohibit reordering.

== Loop dependencies ==

The problem of computing dependencies within loops, which is a significant and nontrivial problem, is tackled by loop dependence analysis, which extends the dependence framework given here.

== Further reading == * {{cite book |author1=Cooper, Keith D. |author2=Torczon, Linda. | title=Engineering a Compiler | publisher=Morgan Kaufmann | year=2005 | isbn=1-55860-698-X}} * {{cite book |author1=Kennedy, Ken |author2=Allen, Randy. | title=Optimizing Compilers for Modern Architectures: A Dependence-based Approach | publisher=Morgan Kaufmann | year=2001 | isbn=1-55860-286-0}} * {{cite book | author=Muchnick, Steven S. | title=Advanced Compiler Design and Implementation | publisher=Morgan Kaufmann | year=1997 | isbn=1-55860-320-4 | url-access=registration | url=https://archive.org/details/advancedcompiler00much }}

{{Program analysis}} Category:Static program analysis