Login
Login

Control dependency

{{technical|date=January 2024}}

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 and
  • S_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).{{Cite book|publisher = ACM|date = 1989-01-01|location = New York, NY, USA|isbn = 0897912942|pages = 25–35|doi = 10.1145/75277.75280|first1 = R.|last1 = Cytron|first2 = J.|last2 = Ferrante|first3 = B. K.|last3 = Rosen|first4 = M. N.|last4 = Wegman|first5 = F. K.|last5 = Zadeck| title=Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '89 | chapter=An efficient method of computing static single assignment form | s2cid=8301431 }} 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 {{Var|X}}, and Predecessors(X) are the set of nodes in the CFG that directly precede {{Var|X}} in the CFG.

Note that node {{Var|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.

See also

References

{{reflist}}

Category:Compilers