Dependence analysis

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 or not it is safe to reorder or parallelize statements.

Contents

Control dependencies

Control dependence is a situation in which a program’s 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 S2's execution is conditionally guarded by S1. 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

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 is not a dependence in the same line as the others, as it does not prohibit reordering instructions. Some compiler optimizations still find this definition useful, however.

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.

See also

Further reading

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

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • 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… …   Deutsch Wikipedia

  • Loop dependence analysis — In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, almost always with respect to array access and modification. For a normalized loop: for i1 from l1 to u1 do for i2… …   Wikipedia

  • analysis — /euh nal euh sis/, n., pl. analyses / seez /. 1. the separating of any material or abstract entity into its constituent elements (opposed to synthesis). 2. this process as a method of studying the nature of something or of determining its… …   Universalium

  • Analysis of variance — In statistics, analysis of variance (ANOVA) is a collection of statistical models, and their associated procedures, in which the observed variance in a particular variable is partitioned into components attributable to different sources of… …   Wikipedia

  • Correlation and dependence — This article is about correlation and dependence in statistical data. For other uses, see correlation (disambiguation). In statistics, dependence refers to any statistical relationship between two random variables or two sets of data. Correlation …   Wikipedia

  • Substance dependence — Substance dependency Classification and external resources ICD 10 F10.2 F19.2 ICD 9 …   Wikipedia

  • Spatial dependence — In mathematical statistics, spatial dependence is a measure for the degree of associative dependence between independently measured values in a temporally or in situ ordered set, determined in samples selected at positions with different… …   Wikipedia

  • Path dependence — explains how the set of decisions one faces for any given circumstance is limited by the decisions one has made in the past, even though past circumstances may no longer be relevant. [Definition from [http://poopthebook.com/blog/?p=20 Our Love Of …   Wikipedia

  • Cocaine dependence — Classification and external resources ICD 10 F14.2 ICD 9 304.2 …   Wikipedia

  • Statistical coupling analysis — or SCA is a technique used in bioinformatics to measure covariation between pairs of amino acids in a protein multiple sequence alignment (MSA). More specifically, it quantifies how much the amino acid distribution at some position i changes upon …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”