Английская Википедия:Control dependency
Шаблон:Technical Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.
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> 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 dominance frontier in the reverse graph of the control-flow graph (CFG).[1] 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.
See also
References
