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 ${\displaystyle S_{2}}${\displaystyle S_{2}} has a control dependency on instruction ${\displaystyle S_{1}}${\displaystyle S_{1}}. However, ${\displaystyle S_{3}}${\displaystyle S_{3}} does not depend on ${\displaystyle S_{1}}${\displaystyle S_{1}} because ${\displaystyle S_{3}}${\displaystyle S_{3}} is always executed irrespective of the outcome of ${\displaystyle S_{1}}${\displaystyle 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 ${\displaystyle S_{2}}${\displaystyle S_{2}} is said to be control dependent on another statement ${\displaystyle S_{1}}${\displaystyle S_{1}} iff

• there exists a path ${\displaystyle P}${\displaystyle P} from ${\displaystyle S_{1}}${\displaystyle S_{1}} to ${\displaystyle S_{2}}${\displaystyle S_{2}} such that every statement ${\displaystyle S_{i}}${\displaystyle S_{i}} ≠ ${\displaystyle S_{1}}${\displaystyle S_{1}} within ${\displaystyle P}${\displaystyle P} will be followed by ${\displaystyle S_{2}}${\displaystyle S_{2}} in each possible path to the end of the program and
• ${\displaystyle S_{1}}${\displaystyle S_{1}} will not necessarily be followed by ${\displaystyle S_{2}}${\displaystyle S_{2}}, i.e. there is an execution path from ${\displaystyle S_{1}}${\displaystyle S_{1}} to the end of the program that does not go through ${\displaystyle S_{2}}${\displaystyle S_{2}}.

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

• ${\displaystyle S_{2}}${\displaystyle S_{2}} post-dominates all ${\displaystyle S_{i}}${\displaystyle S_{i}}
• ${\displaystyle S_{2}}${\displaystyle S_{2}} does not post-dominate ${\displaystyle S_{1}}${\displaystyle S_{1}}

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.

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

• Compilers

• Wikipedia articles that are too technical from January 2024
• All articles that are too technical