Data dependency: Difference between revisions

Revision as of 16:35, 8 April 2021

Revision as of 09:19, 23 June 2021

Line 76:

<ref name="architecture"/>

==Control Dependencydependency==

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

Line 99:

* <math>S_2</math> does not post-dominate <math>S_1</math>

=== Construction of Controlcontrol Dependencesdependences ===

Control dependences are essentially the [[Dominator (graph theory)|dominance frontier]] in the reverse graph of the [[control-flow graph]] (CFG).<ref>{{Cite journal|title = An Efficient Method of Computing Static Single Assignment Form|publisher = ACM|journal = Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|date = 1989-01-01|___location = New York, NY, USA|isbn = 0897912942|pages = 25–35|series = POPL '89|doi = 10.1145/75277.75280|first = R.|last = Cytron|first2 = J.|last2 = Ferrante|first3 = B. K.|last3 = Rosen|first4 = M. N.|last4 = Wegman|first5 = F. K.|last5 = Zadeck}}</ref> 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

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.