HOME

TheInfoList



OR:

In
compiler theory In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs th ...
, 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 A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is c ...
. Dependence analysis determines whether it is safe to reorder or parallelize statements.


Control dependencies

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 S1\ \delta^c\ S2) if and only if ''S2s execution is conditionally guarded by ''S1''. ''S2'' is ''control dependent'' on ''S1'' if and only if S1 \in PDF(S2) where PDF(S) is the post dominance frontier of statement S. 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. See
data dependencies A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is c ...
for more details.


Data dependencies

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 S1\ \delta^f\ S2) 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 S1\ \delta^a\ S2) 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 y but ''S1'' reads a prior value of y.


Output dependence

A statement ''S2'' is output dependent on ''S1'' (written S1\ \delta^o\ S2) 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 x.


Input dependence

A statement ''S2'' is input dependent on ''S1'' (written S1\ \delta^i\ S2) 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 x. 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 In computer science, loop dependence analysis is a process which can be used to find dependencies within iterations of a loop with the goal of determining different relationships between statements. These dependent relationships are tied to the o ...
, which extends the dependence framework given here.


See also

*
Program analysis (computer science) In computer science, program analysis is the process of automatically analyzing the behavior of computer programs regarding a property such as correctness, robustness, safety and liveness. Program analysis focuses on two major areas: program o ...
*
Automatic parallelization Automatic may refer to: Music Bands * Automatic (band), Australian rock band * Automatic (American band), American rock band * The Automatic, a Welsh alternative rock band Albums * ''Automatic'' (Jack Bruce album), a 1983 electronic roc ...
*
Automatic vectorization Automatic vectorization, in parallel computing, is a special case of automatic parallelization, where a computer program is converted from a scalar implementation, which processes a single pair of operands at a time, to a vector implementation, ...
*
Loop dependence analysis In computer science, loop dependence analysis is a process which can be used to find dependencies within iterations of a loop with the goal of determining different relationships between statements. These dependent relationships are tied to the o ...
*
Frameworks supporting the polyhedral model Use of the polyhedral model (also called the polytope model) within a compiler requires software to represent the objects of this framework (sets of integer-valued points in regions of various spaces) and perform operations upon them (e.g., testing ...
* Hazard (computer architecture) *
Program slicing In computer programming, program slicing is the computation of the set of program statements, the program slice, that may affect the values at some point of interest, referred to as a slicing criterion. Program slicing can be used in debugging ...
*
Dead code elimination In compiler theory, dead-code elimination (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove code which does not affect the program results. Removing such code has several benefit ...


Further reading

* * * {{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 Static program analysis