2006-01-03 Daniel Berlin <dberlin@dberlin.org>

	* dominance.c: Add comment about why we use DFS numbering
	of dominance tree.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@109308 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 74 insertions, 0 deletions

diff --git a/gcc/dominance.c b/gcc/dominance.c
index f89b6f61887..c7e39b50ca5 100644
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -814,6 +814,80 @@ nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
   return dom;
 }
 
+/*  Given a dominator tree, we can determine whether one thing
+    dominates another in constant time by using two DFS numbers:
+
+    1. The number for when we visit a node on the way down the tree
+    2. The number for when we visit a node on the way back up the tree
+
+    You can view these as bounds for the range of dfs numbers the
+    nodes in the subtree of the dominator tree rooted at that node
+    will contain.
+    
+    The dominator tree is always a simple acyclic tree, so there are
+    only three possible relations two nodes in the dominator tree have
+    to each other:
+    
+    1. Node A is above Node B (and thus, Node A dominates node B)
+
+     A
+     |
+     C
+    / \
+   B   D
+
+
+   In the above case, DFS_Number_In of A will be <= DFS_Number_In of
+   B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
+   because we must hit A in the dominator tree *before* B on the walk
+   down, and we will hit A *after* B on the walk back up
+   
+   2. Node A is below node B (and thus, node B dominates node B)
+   
+   
+     B
+     |
+     A
+    / \
+   C   D
+
+   In the above case, DFS_Number_In of A will be >= DFS_Number_In of
+   B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
+   
+   This is because we must hit A in the dominator tree *after* B on
+   the walk down, and we will hit A *before* B on the walk back up
+   
+   3. Node A and B are siblings (and thus, neither dominates the other)
+
+     C
+     |
+     D
+    / \
+   A   B
+
+   In the above case, DFS_Number_In of A will *always* be <=
+   DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
+   DFS_Number_Out of B.  This is because we will always finish the dfs
+   walk of one of the subtrees before the other, and thus, the dfs
+   numbers for one subtree can't intersect with the range of dfs
+   numbers for the other subtree.  If you swap A and B's position in
+   the dominator tree, the comparison changes direction, but the point
+   is that both comparisons will always go the same way if there is no
+   dominance relationship.
+
+   Thus, it is sufficient to write
+
+   A_Dominates_B (node A, node B)
+   {
+     return DFS_Number_In(A) <= DFS_Number_In(B) 
+            && DFS_Number_Out (A) >= DFS_Number_Out(B);
+   }
+
+   A_Dominated_by_B (node A, node B)
+   {
+     return DFS_Number_In(A) >= DFS_Number_In(A)
+            && DFS_Number_Out (A) <= DFS_Number_Out(B);
+   }  */
 
 /* Return TRUE in case BB1 is dominated by BB2.  */
 bool