Talk:Dominator (graph theory)

Untitled

The definition of immediate dominator is tautological, it uses concept of immediate dominance without explaining what it is. If I understood correctly, immediate dominator would be defined as something like:

"Node d immediately dominates node n, if it is its dominator, and there exists no dominator of n that isn't also dominator of d"

Is that correct? Mathrick 11:39, 22 Apr 2005 (UTC)

I think your definition is correct, but I added a definition in terms of strict dominators, because this seems a little easier to understand. The original "definition" was quite silly. Deco 16:55, 22 Apr 2005 (UTC)

Wrong

Removing this:

<actually this algorithm is wrong, it can't handle circles, e.g , 4 is precedors of 5, and 5 point to 6, 6 point to 7 and 8, 7 point back to 5, 8 also point back to 5, then the algorithm will never put 4 in the dominators of 5, because 7,8 can appear before 5 in the path, so the intersection can't add 4 into it, but for 7,8 Dom(7), Dom(8) all depend on Dom(6) which depends on Dom(5), which never has 4 in it, so Dom(7),Dom(8) will never have 4 in it, well, you got the idea>

because it appears to be someone's confused opinion. It would be true if Dom(n) was initialized to {}, but it is initialized to the set of all nodes. Aij 15:47, 24 October 2007 (UTC)

Suggested move

I suggest moving this article to a different title, because it's not a concept studied graph theory, although it is a property of nodes in data flow graphs. Perhaps Dominator (computer science) or Dominator (compilers). Dcoetzee 22:25, 16 February 2009 (UTC)

Post-dominance

Hi,

I've heard two competing definitions of post-dominance which are not equivalent. Could anyone comment on which is more proper or more widely accepted?

Def 1: A node n post-dominates a node m iff every path from m to the distinguished exit node passes through n. For example, Andrew Appel uses this definition in "Modern Compiler Implementation." Also, the llvm-compiler infrastructure uses this definition in their implementation of ADCE http://74.125.93.132/search?q=cache:sFD2zsFBl-4J:https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_11/lib/Transforms/Scalar/ADCE.cpp+%22post-dominance%22+infinite+loop&cd=2&hl=en&ct=clnk&gl=us&client=firefox-a

Def 2: A node n post-dominates a node m iff every path from m includes n. For example, Muchnick uses this definition in "Advanced Compiler Design and Implementation"

Def 1 requires the existence (and reachability) of an exit node (compare to start node in dominators). Thus, if there is an infinite loop, nothing post-dominates anything else. Def 2 (which is used on wikipedia) does not require an exit node, and is defined for infinite loops. This has real implications when one is trying to compute control dependences using post-dominator information.

Thanks, 128.112.139.195 (talk) —Preceding undated comment added 17:23, 5 November 2009 (UTC).

Be careful: definition 1 doesn't strictly require reachability! If the exit node is not reachable from m, then every node post-dominates m (this is a vacuous truth since the set of all paths to the exit node is empty)--141.58.62.195 (talk) 12:48, 20 December 2012 (UTC)

Clear up what "predecessor" means

Usage of the term "predecessor" among the control flow/data flow analysis related pages of Wikipedia is inconsistent. It would be nice if we always said "immediate predecessor" when we mean immediate predecessors only. I feel like only saying "predecessor" alone is slightly confusing because some may think this means "all predecessors". (e.g. A -> B -> C, where A and B are predecessors of C, but we really only want to mean B is a predecessor of C). 128.62.88.18 (talk) 00:08, 16 October 2010 (UTC)

Nodes 3 and 4 aren't dominators of 5?

According to the documented definition, it looks like nodes 3 and 4 ought to be dominators for node 5; yet the dominator matrix in the figure doesn't list 5 as a dominated node. Why? 173.11.86.22 (talk) 09:08, 14 March 2015 (UTC)

Node 3 isn't a dominator for 5 because there is a path to 5 not going through 3, viz. 1-2-4-5. Similar for node 4 (1-2-3-5). There is no notion of a node set dominating a node (like {3,4} dominating 5) defined here. - Jochen Burghardt (talk) 16:16, 14 March 2015 (UTC)