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 [math]\displaystyle{ S_2 }[/math] has a control dependency on instruction [math]\displaystyle{ S_1 }[/math]. However, [math]\displaystyle{ S_3 }[/math] does not depend on [math]\displaystyle{ S_1 }[/math] because [math]\displaystyle{ S_3 }[/math] is always executed irrespective of the outcome of [math]\displaystyle{ S_1 }[/math].

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 [math]\displaystyle{ S_2 }[/math] is said to be control dependent on another statement [math]\displaystyle{ S_1 }[/math] iff

* there exists a path [math]\displaystyle{ P }[/math] from [math]\displaystyle{ S_1 }[/math] to [math]\displaystyle{ S_2 }[/math] such that every statement [math]\displaystyle{ S_i }[/math] ≠ [math]\displaystyle{ S_1 }[/math] within [math]\displaystyle{ P }[/math] will be followed by [math]\displaystyle{ S_2 }[/math] in each possible path to the end of the program and
* [math]\displaystyle{ S_1 }[/math] will not necessarily be followed by [math]\displaystyle{ S_2 }[/math], i.e. there is an execution path from [math]\displaystyle{ S_1 }[/math] to the end of the program that does not go through [math]\displaystyle{ S_2 }[/math].

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

* [math]\displaystyle{ S_2 }[/math] post-dominates all [math]\displaystyle{ S_i }[/math]
* [math]\displaystyle{ S_2 }[/math] does not post-dominate [math]\displaystyle{ S_1 }[/math]

## 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) ∪ {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.

## See also

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

## References

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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Control dependency. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Control_dependency&oldid=3371233"