Control dependency

<h2 id="construction-of-control-dependences">Construction of control dependences</h2>
<p>Control dependences are essentially the <a href="/facts/Dominator_(graph_theory)/PILJwzWc">dominance frontier</a> in the reverse graph of the <a href="/facts/Control-flow_graph/BLsvNzcP">control-flow graph</a> (CFG).<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> 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.
</p><p>The following is a pseudo-code for constructing the post-dominance frontier:
</p>
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

<p>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.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Dependence_analysis/4d0geS3g">Dependence analysis</a></li>
<li><a href="/facts/Data_dependency/pkzwvqCf">Data dependency</a></li>
<li><a href="/facts/Loop_dependence_analysis/mkxmPv4x">Loop dependence analysis § Control dependence</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. S2CID 8301431. <a href="0897912942" target="_blank">0897912942</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Control dependency open-in-new

Control dependency