Control dependency explained

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

S _{2} has a control dependency on instruction S _{1} . However, S _{3} does not depend on S _{1} because S _{3} is always executed irrespective of the outcome of S _{1} .

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

S _{2} is said to be control dependent on another statement S _{1} iff

• there exists a path

P from S _{1} to S _{2} such that every statement S _{i} ≠ S _{1} within P will be followed by S _{2} in each possible path to the end of the program andS _{1} will not necessarily be followed by S _{2} , i.e. there is an execution path from S _{1} to the end of the program that does not go through S _{2} .

Expressed with the help of (post-)dominance the two conditions are equivalent to

S _{2} post-dominates all S _{i} S _{2} does not post-dominate S _{1}

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) ∪ done for each Z ∈ Children(X) do: for each Y ∈ PostDominanceFrontier(Z) do: if immediatePostDominator(Y) ≠ X: then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ done done done

Here, Children(X) is the set of nodes in the CFG that are immediately post-dominated by, and Predecessors(X) 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.

See also

• Dependence analysis
• Data dependency
• Loop dependence analysis § Control dependence

Notes and References

1. Book: ACM. 1989-01-01. New York, NY, USA. 0897912942. 25–35. 10.1145/75277.75280. R.. Cytron. J.. Ferrante. B. K.. Rosen. M. N.. Wegman. F. K.. Zadeck. Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 . An efficient method of computing static single assignment form . 8301431 .