1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
+++
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
|
