10
$\begingroup$

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.

$\endgroup$

2 Answers 2

11
$\begingroup$

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 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, 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.

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.

$\endgroup$
5
  • $\begingroup$ That's the exact line of thinking I got stuck on haha. Thanks! $\endgroup$
    – Mike Cluck
    Aug 8, 2023 at 15:31
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2023 at 8:42
  • $\begingroup$ @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. $\endgroup$
    – kaya3
    Aug 9, 2023 at 13:37
  • $\begingroup$ 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. $\endgroup$
    – kaya3
    Aug 9, 2023 at 13:45
  • $\begingroup$ @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. $\endgroup$ Aug 9, 2023 at 14:16
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – supercat
    Aug 9, 2023 at 16:57
  • $\begingroup$ 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. $\endgroup$
    – kaya3
    Aug 9, 2023 at 21:19
  • $\begingroup$ While your statement is true, it is usually extended by demanding that there actually is such a path. $\endgroup$
    – feldentm
    Aug 11, 2023 at 16:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .