From 6a11f5f62f80d1a142a53585c2cbff33c499d83f Mon Sep 17 00:00:00 2001 From: dberlin Date: Wed, 4 Jan 2006 02:03:19 +0000 Subject: [PATCH] 2006-01-03 Daniel Berlin * 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 --- gcc/ChangeLog | 5 ++++ gcc/dominance.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d2e57ce..eb0cd80 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2006-01-03 Daniel Berlin + + * dominance.c: Add comment about why we use DFS numbering + of dominance tree. + 2006-01-03 Jakub Jelinek Richard Henderson diff --git a/gcc/dominance.c b/gcc/dominance.c index f89b6f6..c7e39b5 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 -- 2.7.4