* config/soft-fp: New directory. From glibc.

[pf3gnuchains/gcc-fork.git] / gcc / dominance.c

diff --git a/gcc/dominance.c b/gcc/dominance.c
index f89b6f6..c5c0810 100644 (file)
--- a/gcc/dominance.c
+++ b/gcc/dominance.c
@@ -132,10 +132,10 @@ static unsigned n_bbs_in_dom_tree[2];
     {                                                          \
       unsigned int i = 1;    /* Catch content == i.  */                \
       if (! (content))                                         \
-       (var) = xcalloc ((num), sizeof (type));                 \
+       (var) = XCNEWVEC (type, num);                           \
       else                                                     \
        {                                                       \
-         (var) = xmalloc ((num) * sizeof (type));              \
+         (var) = XNEWVEC (type, (num));                        \
          for (i = 0; i < num; i++)                             \
            (var)[i] = (content);                               \
        }                                                       \
@@ -213,7 +213,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb,
   /* Ending block.  */
   basic_block ex_block;
 
-  stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
+  stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
   sp = 0;
 
   /* Initialize our border blocks, and the first edge.  */
@@ -722,7 +722,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
     n++;
 
-  *bbs = xmalloc (n * sizeof (basic_block));
+  *bbs = XNEWVEC (basic_block, n);
   (*bbs)[0] = son->data;
   for (ason = son->right, n = 1; ason != son; ason = ason->right)
     (*bbs)[n++] = ason->data;
@@ -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 A)
+   
+   
+     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