+++
title = "Dominance relations"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["1a2"]
forwardlinks = ["1a4", "1a3a"]
zettelid = "1a3"
+++

Dominance analysis is important to figure out the control flow in a
program an analyse it, so that it can be optimised. For example, it can
be used to generate phi functions correctly for a minimal SSA form \[1\]
or it can also be used to generate the data dependency graph to then
perform modulo scheduling on \[2\].

Dominance relations are present in a control-flow graph (CFG) ([\#1a4]).
A node $i$ dominates another node $j$ if every path from the entry point
of the CFG to $j$ contains $i$. In addition to that, the relation is
strict if $i \ne j$.

<div id="refs" class="references csl-bib-body" markdown="1">

<div id="ref-barthe14_formal_verif_ssa_based_middl_end_compc"
class="csl-entry" markdown="1">

<span class="csl-left-margin">\[1\]
</span><span class="csl-right-inline">G. Barthe, D. Demange, and D.
Pichardie, “Formal verification of an SSA-based middle-end for
CompCert,” *ACM Trans. Program. Lang. Syst.*, vol. 36, no. 1, Mar. 2014,
doi: [10.1145/2579080].</span>

</div>

<div id="ref-tristan10_simpl_verif_valid_softw_pipel" class="csl-entry"
markdown="1">

<span class="csl-left-margin">\[2\]
</span><span class="csl-right-inline">J.-B. Tristan and X. Leroy, “A
simple, verified validator for software pipelining,” in *Proceedings of
the 37th annual ACM SIGPLAN-SIGACT symposium on principles of
programming languages*, in POPL ’10. Madrid, Spain: Association for
Computing Machinery, 2010, pp. 83–92. doi:
[10.1145/1706299.1706311].</span>

</div>

</div>

  [\#1a4]: /zettel/1a4
  [10.1145/2579080]: https://doi.org/10.1145/2579080
  [10.1145/1706299.1706311]: https://doi.org/10.1145/1706299.1706311