Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.
A formal definition of control dependence can be presented as follows: A statement
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: 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.
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.