|
A commonly used naming convention for data dependencies is the following: Read-after-Write or RAW (flow dependency), Write-After-Read or WAR (anti-dependency), or Write-after-Write or WAW (output dependency).
<ref name="architecture"/>
An instruction B has a control dependency on a preceding instruction A if the outcome of A determines whether B should be executed or not. In the following example, the instruction <math>S_2</math> has a control dependency on instruction <math>S_1</math>. However, <math>S_3</math> does not depend on <math>S_1</math> because <math>S_3</math> is always executed irrespective of the outcome of <math>S_1</math>.
S1. if (a == b)
S2. a = a + b
S3. b = a + b
Intuitively, there is control dependence between two statements A and B if
* B could be possibly executed after A
* The outcome of the execution of A will determine whether B will be executed or not.
A typical example is that there are control dependences between the condition part of an if statement and the statements in its true/false bodies.
A formal definition of control dependence can be presented as follows:
A statement <math>S_2</math> is said to be control dependent on another statement <math>S_1</math> [[If and only if|iff]]
* there exists a path <math>P</math> from <math>S_1</math> to <math>S_2</math> such that every statement <math>S_i</math> ≠ <math>S_1</math> within <math>P</math> will be followed by <math>S_2</math> in each possible path to the end of the program and
* <math>S_1</math> will not necessarily be followed by <math>S_2</math>, i.e. there is an execution path from <math>S_1</math> to the end of the program that does not go through <math>S_2</math>.
Expressed with the help of (post-)dominance the two conditions are equivalent to
* <math>S_2</math> post-dominates all <math>S_i</math>
* <math>S_2</math> does not post-dominate <math>S_1</math>
=== Construction of control dependences ===
Control dependences are essentially the [[Dominator (graph theory)|dominance frontier]] in the reverse graph of the [[control-flow graph]] (CFG).<ref>{{Cite book|publisher = ACM|date = 1989-01-01|___location = New York, NY, USA|isbn = 0897912942|pages = 25–35|doi = 10.1145/75277.75280|first1 = R.|last1 = Cytron|first2 = J.|last2 = Ferrante|first3 = B. K.|last3 = Rosen|first4 = M. N.|last4 = Wegman|first5 = F. K.|last5 = Zadeck| title=Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 | chapter=An efficient method of computing static single assignment form | s2cid=8301431 }}</ref> Thus, one way of constructing them, would be to construct the post-dominance frontier of the CFG, and then reversing it to obtain a control dependence graph.
The following is a pseudo-code for constructing the post-dominance frontier:
for each X in a bottom-up traversal of the post-dominator tree do:
PostDominanceFrontier(X) ← ∅
for each Y ∈ Predecessors(X) do:
if immediatePostDominator(Y) ≠ X:
then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
done
for each Z ∈ Children(X) do:
for each Y ∈ PostDominanceFrontier(Z) do:
if immediatePostDominator(Y) ≠ X:
then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
done
done
done
Here, Children(X) is the set of nodes in the CFG that are immediately post-dominated by X, and Predecessors(X) are the set of nodes in the CFG that directly precede X in the CFG.
Note that node X shall be processed only after all its Children have been processed.
Once the post-dominance frontier map is computed, reversing it will result in a map from the nodes in the CFG to the nodes that have a control dependence on them.
==Implications==
However, dependencies among statements or instructions may hinder parallelism — parallel execution of multiple instructions, either by a parallelizing compiler or by a processor exploiting [[instruction-level parallelism]]. Recklessly executing multiple instructions without considering related dependences may cause danger of getting wrong results, namely [[Hazard (computer architecture)|hazards]].
==See also==
* [[Dependency analysis]]
▲==* [[Control dependency ==]]
==References==
| 