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]\displaystyle{ S_2 }[/math] has a control dependency on instruction [math]\displaystyle{ S_1 }[/math]. However, [math]\displaystyle{ S_3 }[/math] does not depend on [math]\displaystyle{ S_1 }[/math] because [math]\displaystyle{ S_3 }[/math] is always executed irrespective of the outcome of [math]\displaystyle{ 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
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]\displaystyle{ S_2 }[/math] is said to be control dependent on another statement [math]\displaystyle{ S_1 }[/math] iff
Expressed with the help of (post-)dominance the two conditions are equivalent to
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.
Original source: https://en.wikipedia.org/wiki/Control dependency.
Read more |