# What is a dominator node and a dominator tree?

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?

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.