1
$\begingroup$

For the definition of domination [Wikipedia],

a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$.

If node $n$ is not reachable from the entry node, why are all other nodes not dominators for it? There is no path from entry node that goes to $n$, and thus in particular

  • there is no path from the entry node to $n$ that does not go through $d$.
$\endgroup$
4
  • $\begingroup$ According to the definition you posted, all nodes (including the entry node and $n$ itself) are dominators of $n$ when there is no path from the entry node to $n$. However I'm not sure if in control flow-graphs you can have nodes that are not reachable from the entry node in the first place. $\endgroup$
    – Steven
    Jul 4 at 22:46
  • $\begingroup$ @Steven, I see. Perhaps for an arbitrary graph, it would be most reasonable to define dominators if some path exists. $\endgroup$
    – AustinBest
    Jul 5 at 0:59
  • 1
    $\begingroup$ I don't expect the definitions on Wikipedia to be very precise. According to the definitions here a node always dominates itself, moreover an immediate dominator of $N$ is ``...the last dominator on all paths from entry to $N$'', which means that, for all nodes $N$ reachable from the entry node, the only immediate dominator of $N$ is $N$ itself. This is probably not what the author intended to define. $\endgroup$
    – Steven
    Jul 5 at 10:19
  • $\begingroup$ Huge thanks for your help @Steven! $\endgroup$
    – AustinBest
    Aug 19 at 1:53

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.