Dominators
12 May, 2026
Dominators
Figure 1: Flow graph
# We say node 𝑑 of a flow graph dominates node 𝑛 (written as 𝑑 DOM 𝑛), if every path from the
initial node to the flow graph to 𝑛 goes through 𝑑.
# In the above example:
- The initial node dominates every node.
- Node 2 dominates only itself.
- Node 3 dominates all but 1 and 2.
- Node 4 dominates all but 1, 2 and 3.
- Node 5 and 3 dominate only themselves.
- Node 7 dominates 7, 8, 9 and 10.
- Node 8 dominates 8, 9 and 10.
- Node 9 and 10 dominate only themselves.
# Dominance is reflexive, i.e. 𝑎 DOM 𝑎 holds.
# Dominance is also transitive, i.e. 𝑎 DOM 𝑏 ∧ 𝑏 DOM 𝑐 ⇒ 𝑎 DOM 𝑐.
# Dominance is anti-symmetric, i.e. 𝑎 DOM 𝑏 ∧ 𝑏 DOM 𝑎 ⇒ 𝑎 = 𝑏
# Dominance is a reflexive partial order. The dominance of each node are heirarchically ordered by
DOM relation.
# E.g. The dominators of 9 are 1, 3, 4, 7, 8 and 9. It can be found that
1 DOM 3 DOM 4 DOM 7 DOM 8 DOM 9. 8 is called the immediate dominator of 9.
1
Back edges
# We can search for edges in the flow graph whose heads dominate their tails. If 𝐴 → 𝐵 is an edge,
𝐵 is the head and 𝐴 is the tail. We call such edges - back edges.
# Example: There is an edge 7 → 4 and 4 DOM 7. Similarly, 10 → 7 is an edge and 7 DOM 10.
Note that these are exactly the edges that can be seen as forming loop in the flow graph.
Natural loops
# Given a back edge 𝑛 → 𝑑, we define the natural loop of the edge to be 𝑑 +
set of nodes that can reach 𝑛 without going through 𝑑, node 𝑑 is the header of the loop.
# Example: The natural loop containing 7, 8 and 10 since 8 and 10 are all those nodes that cannot
reach 10 without going through 7. The natural loop of 9 → 1 is the entire flow graph.
Reducible flow graph
# A flow graph is reducible if and only if we can partition the edges into two disjoint groups often
called the forward edges and back edges with the following two properties:
1. The forward edges form an acyclic graph in which every node can be reached from the initial
node of 𝐺.
2. The back edges consist only of edges whose heads dominate their tails.
Data flow analysis
# It is a process of collecting information about the variables that are used in the program.
# The information collected at various points can be related using simple set equations.
# A typical equation has the form:
out[𝑠] = gen[𝑠] ∪ (in[𝑠] − kill[𝑠])
and can be read as the information at the end of a statement is either generated within the statement
or enters at the beginning of the statement and is not killed as control flows through the statement.
Points
# By a point in a program, we mean the position before or after any statement. We say control
reaches the point just before a statement when the statement is about to be executed and the point
after when the statement has been executed.
Paths
# A path from 𝑝1 to 𝑝𝑛 is a sequence of points 𝑝1 , 𝑝2 , …, 𝑝𝑛 such that for each 𝑖 between 1 and 𝑛 −
1 either:
i. 𝑝𝑖 is the point immediately preceding a statement and 𝑝𝑖+1 is the point immediately following
the statement in the same block.
ii. 𝑝𝑖 is the end of some block and 𝑝𝑖+1 is the beginning of the successor block.
Define
# A definition of a variable 𝑥 is a statement that assigns or may assign a value to 𝑥.
2
Reach
# A definition 𝑑 is said to reach a point 𝑝 if there is a path from the point immediately following 𝑑
to 𝑝 such that 𝑑 is not killed along the path.
Kill
# We kill a definition of a variable 𝑎 if between two points along the path there is a definition of 𝑎
Gen[s]
# We define gen[𝑠] as a set of definitions generated by 𝑠.
# We say definition 𝑑 is in gen[𝑠] if 𝑑 reaches the end of 𝑠 independent of whether it reaches the
beginning of 𝑠, i.e. 𝑑 must appear in 𝑠 and reach the end of 𝑠 via a path that does not go outside 𝑠.
Kill[s]
# We say kill[𝑠] is a set of definitions that never reaches the end of 𝑠 even if they reach the
beginning, i.e. in order for definition 𝑑 to be in kill[𝑠], every path from the beginning to the end of
𝑠 must have an unambiguous definition of the same variable defined by 𝑑 and if 𝑑 appears in 𝑠,
then following every occurrence of 𝑑 along any path must be another definition of the same
variable.
Figure 2: Definition of a statement
# The assignment is a definition of 𝑎, say defintion 𝑑. Then 𝑑 is the only definition sure to reach the
end of the statement regardless of whether it reaches the beginning.
gen[𝑠] = {𝑑}
𝑑 kills all other definitions, so we write
kill[𝑠] = 𝐷𝑎 − {𝑑}
where 𝐷𝑎 is the set of all definitions in the program for variable 𝑎.
3
Figure 3: Definition of consecutive statements
# We next consider a consecutive set of statements 𝑠1 and 𝑠2 . Consider the definition 𝑑, if it is
generated by 𝑠2 then it is surely generated by 𝑠. If 𝑑 is generated by 𝑠1 , it will reach the end of 𝑠
provided it is not killed by 𝑠2 . Then we write:
gen[𝑠] = gen[𝑠2 ] ∪ (gen[𝑠1 ] − kill[𝑠2 ])
kill[𝑠] = kill[𝑠2 ] ∪ (kill[𝑠1 ] − gen[𝑠2 ])
Figure 4: Definition of if statement
# For the if statment, if either branch of the if generates a statement, then that definition reaches the
end of the statemnt. Thus, to kill definition 𝑑, it must be killed along either branch so that
gen[𝑠] = gen[𝑠1 ] ∪ gen[𝑠2 ]
kill[𝑠] = kill[𝑠1 ] ∩ kill[𝑠2 ]
# If defintion 𝑑 is generated wuntin 𝑠1 , then it reaches both the end of 𝑠1 and 𝑠. Conversely, if 𝑑 is
generated within 𝑠, it can be generated within 𝑠1 . We conclude
gen[𝑠] = gen[𝑠1 ]
by a similar set of arguments, we can say
kill[𝑠] = kill[𝑠1 ]