Control dependency


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 has a control dependency on instruction. However, does not depend on because is always executed irrespective of the outcome of.
S1. if
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 is said to be control dependent on another statement iff
  • there exists a path from to such that every statement ≠ within will be followed by in each possible path to the end of the program and
  • will not necessarily be followed by, i.e. there is an execution path from to the end of the program that does not go through.
Expressed with the help of dominance the two conditions are equivalent to
  • post-dominates all
  • does not post-dominate

    Construction of control dependences

Control dependences are essentially the dominance frontier in the reverse graph of the control-flow graph. 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 ← ∅
for each Y ∈ Predecessors do:
if immediatePostDominator ≠ X:
then PostDominanceFrontier ← PostDominanceFrontier ∪
done
for each Z ∈ Children do:
for each Y ∈ PostDominanceFrontier do:
if immediatePostDominator ≠ X:
then PostDominanceFrontier ← PostDominanceFrontier ∪
done
done
done
Here, Children is the set of nodes in the CFG that are immediately post-dominated by, and Predecessors are the set of nodes in the CFG that directly precede in the CFG.
Note that node 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.