What is a dominator node and a dominator tree?

Question

I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node:

a node d dominates a node n if every path from the entry node to n must go through d.

I need to understand the concept of a dominator node but I do not need to go deep into graphs, so I'm trying to make sense of these definitions. I'm trying to look in the images on the article:

This is a graph:

This should be a dominator tree for the graph above:

Based on the definition above, I think

node 2 dominates node 3 because every path from 3 must go through 2. Why? To go from 3 to itself I must pass to 2. That's why 2 goes to 3 in the dominator tree.

Am I thinking right?

Can I know also why this is useful in compilers?

Answer 1

The reason you give is not exactly right; the definition of a dominator node works from a starting node ($1$ in the example). The only way to reach $3$ from $1$ is to go through $2$ as it is the sole successor node of $1$ in the given graph. Hence $2$ dominates $3$. For the same reason, the nodes $4$ through $6$ are also dominated by $2$ and further, $2$ is the immediate dominator of these nodes (as $1$ dominates $2$) and these nodes are also not dominated by any other nodes than $1$ and $2$:

• $3, 4$ and $6$ can be immediately reached from $1$ via $2$.
• $5$ can be reached from $2$ either via $3$ or $4$ and thus the only common nodes in these paths to $5$ are $1$ and $2$.

As for applying these concepts to compilers, consider a block-level control flow graph (or CFG for brevity) of a program. If some block $B$ dominates a block $B'$ in the CFG, then $B$ must have been executed by the time the program reaches $B'$. This knowledge can be used to remove redundant pieces of code: Consider the program

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

Here, the block consisting of the first two lines dominates the if-block as well as the else-block. Hence we know that by the time we jump to the if-block where we would set b to True, it is already set to True by the fist block and thus the compiler could optimize the code by deleting the assignment in the if-block.

You can also detect loops in the code by analyzing if the CFG has edges of the form $B' \to B$ where again $B$ dominates $B'$. Such a path indicates the existence of a loop where $B$ would then represent the loop header while $B'$ is (the last) part of the loop body.