<p>I'm reading <a href="https://link.springer.com/book/10.1007/978-3-030-80515-9" rel="noreferrer">SSA-driven Compiler Design</a> and I'm having trouble understanding this section from Chapter 2:</p>
<blockquote>
<p>The immediate dominator or “idom” of a node N is the unique node that strictly dominates N but does not
strictly dominate any other node that strictly dominates N. All nodes but the entry node have immediate dominators.</p>
</blockquote>
<p>My understanding of dominance says that some node <code>A</code> dominates <code>B</code> if all paths through the program to <code>B</code> include <code>A</code>. Strict dominance merely removes reflexivity (<code>A</code> != <code>B</code>).</p>
<p>Now assume we've got some basic branching CFG like the following:</p>
<pre><code>    -----
    | A |
    -----
   /     \
-----   -----
| B |   | C |
-----   -----
   \      /
    -----
    | D |
    -----
</code></pre>
<p><code>A</code> is the immediate dominator for both <code>B</code> and <code>C</code> since you must pass through <code>A</code> to get to either of them. However, isn't it right that <code>D</code> has no immediate dominator? One path to <code>D</code> requires <code>B</code> and another path to <code>D</code> requires <code>C</code> which means that neither of its immediate predecessors strictly dominate it.</p>

<static-single-assignment><control-flow-graph>
Do all nodes (except for the entry) in SSA have an immediate dominator?
<p>Only for connected graphs. If one of your transformations makes blocks unreachable, the recomputation of the dominators would cause them not to be dominated by the root.</p>
<p>However, all nodes not dominated by the root should be removed in almost all cases. And all other nodes have idoms that are paths to the root node.</p>

CC BY-SA 4.0
2023-08-09T16:05:13.777Z
2023-08-09T16:05:13.777Z
feldentm
CC BY-SA 4.0
2023-08-09T16:57:07.423Z
Unless a toolset will be used exclusively for tasks that don't involve processing untrustworthy inputs, code which is considering removing unreachable nodes should ensure that no downstream code relies upon post-conditions those nodes would have established.  Unfortunately, people writing optimizers often fail to realize that optimizations that may be useful for programs which receive exclusively trustworthy input may be worse than useless elsewhere.
supercat
CC BY-SA 4.0
2023-08-09T21:19:57.733Z
This is not really correct. If a node N is unreachable, then it is vacuously true that all paths reaching N go via the entry, because there are no such paths. So even unreachable nodes are strictly dominated by the entry, and the same argument even shows that they are strictly dominated by all other nodes.
kaya3
CC BY-SA 4.0
2023-08-11T16:43:02.590Z
While your statement is true, it is usually extended by demanding that there actually is such a path.
feldentm
<blockquote>
<p>The immediate dominator or “idom” of a node N is the unique node that strictly dominates N but does not strictly dominate any other node that strictly dominates N. All nodes but the entry node have immediate dominators.</p>
</blockquote>
<p>As you note in your question, A strictly dominates D, and neither B nor C strictly dominate D. Therefore by the definition provided, A is the immediate dominator of D, since</p>
<ul>
<li>A strictly dominates D, and</li>
<li>There is no other node which strictly dominates D, and hence there is no such other node strictly dominated by A.</li>
</ul>
<p>Perhaps you were confused by thinking that the word &quot;immediate&quot; must mean the node must be connected by a single edge, making it an immediate neighbour. However, the definition provided does not require the immediate dominator to be a neighbour.</p>
<hr />
<h2>Proof</h2>
<p>To prove that all nodes except for the entry node have a unique immediate dominator, we'll start with a few lemmas. The symbol <span class="math-container">$\gg$</span> means &quot;strictly dominates&quot;.</p>
<p><strong>Lemma 1.</strong> If <span class="math-container">$u \gg v$</span>, then <span class="math-container">$v \not\gg u$</span>.</p>
<p>Proof: let <span class="math-container">$P$</span> be a shortest path from the entry to <span class="math-container">$v$</span>. Since <span class="math-container">$u \gg v$</span> we must have <span class="math-container">$u \in P$</span>. Then <span class="math-container">$P$</span> can be truncated giving a path to <span class="math-container">$u$</span> which does not contain <span class="math-container">$v$</span>, hence <span class="math-container">$v \not\gg u$</span>.</p>
<p><strong>Lemma 2.</strong> If <span class="math-container">$u \gg v$</span> and <span class="math-container">$v \gg w$</span>, then <span class="math-container">$u \gg w$</span>.</p>
<p>Proof: let <span class="math-container">$P$</span> be any path from the entry to <span class="math-container">$w$</span>. Since <span class="math-container">$v \gg w$</span>, we know <span class="math-container">$v \in P$</span>. Since <span class="math-container">$u \gg v$</span>, the truncation of <span class="math-container">$P$</span> from the entry to <span class="math-container">$v$</span> must contain <span class="math-container">$u$</span>. Therefore <span class="math-container">$u \in P$</span>.</p>
<p>By lemma 1, we also have <span class="math-container">$u \ne w$</span>.</p>
<p><strong>Lemma 3.</strong> If <span class="math-container">$u \gg w$</span> and <span class="math-container">$v \gg w$</span> and <span class="math-container">$u \ne v$</span>, then either <span class="math-container">$u \gg v$</span> or <span class="math-container">$v \gg u$</span>.</p>
<p>Proof: suppose neither <span class="math-container">$u \gg v$</span> nor <span class="math-container">$v \gg u$</span>. Then there is a path <span class="math-container">$P$</span> from the entry to <span class="math-container">$u$</span> for which <span class="math-container">$v \notin P$</span>, and there is another path <span class="math-container">$Q$</span> from the entry to <span class="math-container">$v$</span> for which <span class="math-container">$u \notin Q$</span>.</p>
<p>Let <span class="math-container">$R$</span> be a shortest path from <span class="math-container">$u$</span> to <span class="math-container">$w$</span>. (Such a path exists as a suffix of a path from the entry to <span class="math-container">$w$</span>.) The composed path <span class="math-container">$P+R$</span> goes from the entry to <span class="math-container">$w$</span>; this path contains <span class="math-container">$v$</span> because <span class="math-container">$v \gg w$</span>. But <span class="math-container">$v \notin P$</span>, therefore <span class="math-container">$v \in R$</span>.</p>
<p>Let <span class="math-container">$R'$</span> be the suffix of <span class="math-container">$R$</span> starting from <span class="math-container">$v$</span>. The composed path <span class="math-container">$Q+R'$</span> goes from the entry to <span class="math-container">$w$</span>; this path contains <span class="math-container">$u$</span> because <span class="math-container">$u \gg w$</span>. But <span class="math-container">$u \notin Q$</span>, therefore <span class="math-container">$u \in R'$</span>.</p>
<p>This contradicts that <span class="math-container">$R$</span> was a shortest path from <span class="math-container">$u$</span> to <span class="math-container">$w$</span>, since it has a shorter suffix containing <span class="math-container">$u$</span>. Therefore the initial supposition was false, and either <span class="math-container">$u \gg v$</span> or <span class="math-container">$v \gg u$</span>.</p>
<p><strong>Theorem:</strong> every node except for the entry has a unique immediate dominator.</p>
<p>Proof: Let <span class="math-container">$u$</span> be a node which is not the entry node, and let <span class="math-container">$S$</span> be the set of nodes which strictly dominate <span class="math-container">$u$</span>. The &quot;strictly dominates&quot; relation restricted to the set <span class="math-container">$S$</span> is irreflexive (by definition), asymmetric (by lemma 1), transitive (by lemma 2) and connected (by lemma 3); i.e. it defines a <a href="https://en.wikipedia.org/wiki/Total_order" rel="nofollow noreferrer">strict total order</a> on <span class="math-container">$S$</span>. We also know that <span class="math-container">$S$</span> contains the entry node.</p>
<p>So <span class="math-container">$S$</span> is a non-empty and finite total order, and hence it has a minimum element <span class="math-container">$m$</span>, which does not strictly dominate any other node in <span class="math-container">$S$</span>. It follows that <span class="math-container">$m$</span> is an immediate dominator of <span class="math-container">$u$</span>, and any other <span class="math-container">$m' \in S$</span> is not an immediate dominator of <span class="math-container">$u$</span> because <span class="math-container">$m' \gg m$</span>.</p>
<hr />
<h2>A note about disconnected graphs</h2>
<p>Note that the shortest paths required in lemmas 1 and 3 only exist if the node is reachable, so the conclusion does not hold for unreachable nodes. (Lemma 2 also fails for disconnected graphs, because U and W might be the same node.) However, the claim in <a href="https://langdev.stackexchange.com/a/2685/89">this other answer</a>, that unreachable nodes are not dominated by the entry, is false; in fact, unreachable nodes are dominated by <em>every</em> node, since if U is unreachable then the statement <em>&quot;every path from the entry to U ...&quot;</em> is <a href="https://en.wikipedia.org/wiki/Vacuous_truth" rel="nofollow noreferrer">vacuously true</a>.</p>
<p>Nonetheless, the original claim from the question ─ that all non-entry nodes have immediate dominators ─ is false in general for disconnected graphs. So there is an assumption in the book that the control-flow graph must be connected; this assumption is unstated in the question but may be stated elsewhere in the book.</p>
<p>Consider a disconnected graph with an entry A, and three isolated nodes B, C and D. We will show that D has no immediate dominator:</p>
<ul>
<li>Vacuously, A, B and C each strictly dominate D.</li>
<li>Vacuously, A strictly dominates B and C, so A is not an immediate dominator of D.</li>
<li>Vacuously, B and C strictly dominate each other, so neither are immediate dominators of D.</li>
</ul>
<p>However, if we delete C from the graph then strangely, B becomes the immediate dominator of D: without C, there is no other node strictly dominated by B. (Likewise, D becomes the immediate dominator of B!) This shows that the provided definition for an &quot;immediate dominator&quot; really doesn't make much sense in a disconnected graph.</p>

CC BY-SA 4.0
2023-08-08T15:20:57.163Z
2023-08-10T23:17:50.223Z
2023-08-10T23:17:50.223Z
kaya3
CC BY-SA 4.0
2023-08-08T15:31:12.043Z
That's the exact line of thinking I got stuck on haha. Thanks!
Mike Cluck
CC BY-SA 4.0
2023-08-09T08:42:34.013Z
There is a slight omission in the theorem proof, it seems. While you identify that all nodes but M have an immediate dominator, you do not "tie the note" and prove that this M must be the entry node, leaving room for a _random_ node in S to have no immediate dominator. Also... W appears magically in there.
Matthieu M.
CC BY-SA 4.0
2023-08-09T13:37:44.867Z
@MatthieuM. M is *not* the entry node ─ or rather, it can be, but isn't necessarily. It is the minimum element of the total order defined by the "strictly dominates" relation on the set S, which makes it the immediate dominator of N; and N is taken to be a node which is not the entry node. For example in a simple path A → B → C, if A is the entry and C is the non-entry node under consideration, the set S is {A, B}, and B is the minimum element of S (and hence, the immediate dominator of C) because A strictly dominates B.
kaya3
CC BY-SA 4.0
2023-08-09T13:45:53.483Z
To be clear, the entry node is the *maximum* element of S, because it strictly dominates every other element of S (indeed, it strictly dominates every other node in the whole graph), so M is only the entry node when S is a singleton set, i.e. when N is strictly dominated by no nodes other than the entry.
kaya3
CC BY-SA 4.0
2023-08-09T14:16:13.967Z
@kaya3-supportthestrike: Ah! I see. Your answer is clearer now with N instead of W. It may also be even clearer if S was "parameterized" by N, ie S<sub>N</sub>, as I didn't immediately realize that S was not the same for all N.
Matthieu M.
# Do all nodes (except for the entry) in SSA have an immediate dominator?
Posted by: username_0 on 2023-08-08
I'm reading SSA-driven Compiler Design and I'm having trouble understanding this section from Chapter 2:

The immediate dominator or “idom” of a node N is the unique node that strictly dominates N but does not
strictly dominate any other node that strictly dominates N. All nodes but the entry node have immediate dominators.

My understanding of dominance says that some node A dominates B if all paths through the program to B include A. Strict dominance merely removes reflexivity (A != B).
Now assume we've got some basic branching CFG like the following:
    -----
    | A |
    -----
   /     \
-----   -----
| B |   | C |
-----   -----
   \      /
    -----
    | D |
    -----

A is the immediate dominator for both B and C since you must pass through A to get to either of them. However, isn't it right that D has no immediate dominator? One path to D requires B and another path to D requires C which means that neither of its immediate predecessors strictly dominate it.
**Tags:** static-single-assignment control-flow-graph
---
## 2 answers
### Answer by username_3 on 2023-08-08. Score: 11 | Accepted answer
> The immediate dominator or “idom” of a node N is the unique node that strictly dominates N but does not strictly dominate any other node that strictly dominates N. All nodes but the entry node have immediate dominators.

As you note in your question, A strictly dominates D, and neither B nor C strictly dominate D. Therefore by the definition provided, A is the immediate dominator of D, since

* A strictly dominates D, and
* There is no other node which strictly dominates D, and hence there is no such other node strictly dominated by A.

Perhaps you were confused by thinking that the word "immediate" must mean the node must be connected by a single edge, making it an immediate neighbour. However, the definition provided does not require the immediate dominator to be a neighbour.

---

## Proof

To prove that all nodes except for the entry node have a unique immediate dominator, we'll start with a few lemmas. The symbol $\gg$ means "strictly dominates".

**Lemma 1.** If $u \gg v$, then $v \not\gg u$.

Proof: let $P$ be a shortest path from the entry to $v$. Since $u \gg v$ we must have $u \in P$. Then $P$ can be truncated giving a path to $u$ which does not contain $v$, hence $v \not\gg u$.

**Lemma 2.** If $u \gg v$ and $v \gg w$, then $u \gg w$.

Proof: let $P$ be any path from the entry to $w$. Since $v \gg w$, we know $v \in P$. Since $u \gg v$, the truncation of $P$ from the entry to $v$ must contain $u$. Therefore $u \in P$.

By lemma 1, we also have $u \ne w$.

**Lemma 3.** If $u \gg w$ and $v \gg w$ and $u \ne v$, then either $u \gg v$ or $v \gg u$.

Proof: suppose neither $u \gg v$ nor $v \gg u$. Then there is a path $P$ from the entry to $u$ for which $v \notin P$, and there is another path $Q$ from the entry to $v$ for which $u \notin Q$.

Let $R$ be a shortest path from $u$ to $w$. (Such a path exists as a suffix of a path from the entry to $w$.) The composed path $P+R$ goes from the entry to $w$; this path contains $v$ because $v \gg w$. But $v \notin P$, therefore $v \in R$.

Let $R'$ be the suffix of $R$ starting from $v$. The composed path $Q+R'$ goes from the entry to $w$; this path contains $u$ because $u \gg w$. But $u \notin Q$, therefore $u \in R'$.

This contradicts that $R$ was a shortest path from $u$ to $w$, since it has a shorter suffix containing $u$. Therefore the initial supposition was false, and either $u \gg v$ or $v \gg u$.

**Theorem:** every node except for the entry has a unique immediate dominator.

Proof: Let $u$ be a node which is not the entry node, and let $S$ be the set of nodes which strictly dominate $u$. The "strictly dominates" relation restricted to the set $S$ is irreflexive (by definition), asymmetric (by lemma 1), transitive (by lemma 2) and connected (by lemma 3); i.e. it defines a [strict total order](https://en.wikipedia.org/wiki/Total_order) on $S$. We also know that $S$ contains the entry node.

So $S$ is a non-empty and finite total order, and hence it has a minimum element $m$, which does not strictly dominate any other node in $S$. It follows that $m$ is an immediate dominator of $u$, and any other $m' \in S$ is not an immediate dominator of $u$ because $m' \gg m$.

---

## A note about disconnected graphs

Note that the shortest paths required in lemmas 1 and 3 only exist if the node is reachable, so the conclusion does not hold for unreachable nodes. (Lemma 2 also fails for disconnected graphs, because U and W might be the same node.) However, the claim in [this other answer](https://langdev.stackexchange.com/a/2685/89), that unreachable nodes are not dominated by the entry, is false; in fact, unreachable nodes are dominated by *every* node, since if U is unreachable then the statement *"every path from the entry to U ..."* is [vacuously true](https://en.wikipedia.org/wiki/Vacuous_truth).

Nonetheless, the original claim from the question ─ that all non-entry nodes have immediate dominators ─ is false in general for disconnected graphs. So there is an assumption in the book that the control-flow graph must be connected; this assumption is unstated in the question but may be stated elsewhere in the book.

Consider a disconnected graph with an entry A, and three isolated nodes B, C and D. We will show that D has no immediate dominator:

* Vacuously, A, B and C each strictly dominate D.
* Vacuously, A strictly dominates B and C, so A is not an immediate dominator of D.
* Vacuously, B and C strictly dominate each other, so neither are immediate dominators of D.

However, if we delete C from the graph then strangely, B becomes the immediate dominator of D: without C, there is no other node strictly dominated by B. (Likewise, D becomes the immediate dominator of B!) This shows that the provided definition for an "immediate dominator" really doesn't make much sense in a disconnected graph.
> **Comments:**
> **username_0** (2023-08-08): That's the exact line of thinking I got stuck on haha. Thanks!  
> **username_4** (2023-08-09): There is a slight omission in the theorem proof, it seems. While you identify that all nodes but M have an immediate dominator, you do not "tie the note" and prove that this M must be the entry node, leaving room for a _random_ node in S to have no immediate dominator. Also... W appears magically in there.  
> **username_3** (2023-08-09): @MatthieuM. M is *not* the entry node ─ or rather, it can be, but isn't necessarily. It is the minimum element of the total order defined by the "strictly dominates" relation on the set S, which makes it the immediate dominator of N; and N is taken to be a node which is not the entry node. For example in a simple path A → B → C, if A is the entry and C is the non-entry node under consideration, the set S is {A, B}, and B is the minimum element of S (and hence, the immediate dominator of C) because A strictly dominates B.  
> **username_3** (2023-08-09): To be clear, the entry node is the *maximum* element of S, because it strictly dominates every other element of S (indeed, it strictly dominates every other node in the whole graph), so M is only the entry node when S is a singleton set, i.e. when N is strictly dominated by no nodes other than the entry.  
> **username_4** (2023-08-09): @kaya3-supportthestrike: Ah! I see. Your answer is clearer now with N instead of W. It may also be even clearer if S was "parameterized" by N, ie S<sub>N</sub>, as I didn't immediately realize that S was not the same for all N.  
---
### Answer by username_1 on 2023-08-09. Score: 1
Only for connected graphs. If one of your transformations makes blocks unreachable, the recomputation of the dominators would cause them not to be dominated by the root.

However, all nodes not dominated by the root should be removed in almost all cases. And all other nodes have idoms that are paths to the root node.
> **Comments:**
> **username_2** (2023-08-09): Unless a toolset will be used exclusively for tasks that don't involve processing untrustworthy inputs, code which is considering removing unreachable nodes should ensure that no downstream code relies upon post-conditions those nodes would have established.  Unfortunately, people writing optimizers often fail to realize that optimizations that may be useful for programs which receive exclusively trustworthy input may be worse than useless elsewhere.  
> **username_3** (2023-08-09): This is not really correct. If a node N is unreachable, then it is vacuously true that all paths reaching N go via the entry, because there are no such paths. So even unreachable nodes are strictly dominated by the entry, and the same argument even shows that they are strictly dominated by all other nodes.  
> **username_1** (2023-08-11): While your statement is true, it is usually extended by demanding that there actually is such a path.  
---
