2010-05-06 Richard Guenther <rguenther@suse.de>

	PR tree-optimization/43571
	* domwalk.c (walk_dominator_tree): Walk the dominator
	sons in more optimal order.

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

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 5051ece..aacaefe 100644 (file)
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,11 @@
 2010-05-06  Richard Guenther  <rguenther@suse.de>
 
+       PR tree-optimization/43571
+       * domwalk.c (walk_dominator_tree): Walk the dominator
+       sons in more optimal order.
+
+2010-05-06  Richard Guenther  <rguenther@suse.de>
+
        PR tree-optimization/43934
        * tree-ssa-loop-im.c (movement_possibility): Handle PHI nodes.
        (stmt_cost): Likewise.

diff --git a/gcc/domwalk.c b/gcc/domwalk.c
index 07764eb..4f0e919 100644 (file)
--- a/gcc/domwalk.c
+++ b/gcc/domwalk.c
@@ -144,6 +144,9 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
   basic_block dest;
   basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2);
   int sp = 0;
+  sbitmap visited = sbitmap_alloc (last_basic_block + 1);
+  sbitmap_zero (visited);
+  SET_BIT (visited, ENTRY_BLOCK_PTR->index);
 
   while (true)
     {
@@ -184,6 +187,8 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
          if (walk_data->before_dom_children)
            (*walk_data->before_dom_children) (walk_data, bb);
 
+         SET_BIT (visited, bb->index);
+
          /* Mark the current BB to be popped out of the recursion stack
             once children are processed.  */
          worklist[sp++] = bb;
@@ -213,11 +218,44 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb)
            }
        }
       if (sp)
-       bb = worklist[--sp];
+       {
+         int spp;
+         spp = sp - 1;
+         if (walk_data->dom_direction == CDI_DOMINATORS)
+           /* Find the dominator son that has all its predecessors
+              visited and continue with that.  */
+           while (1)
+             {
+               edge_iterator ei;
+               edge e;
+               bool found = true;
+               bb = worklist[spp];
+               FOR_EACH_EDGE (e, ei, bb->preds)
+                 {
+                   if (!dominated_by_p (CDI_DOMINATORS, e->src, e->dest)
+                       && !TEST_BIT (visited, e->src->index))
+                     {
+                       found = false;
+                       break;
+                     }
+                 }
+               if (found)
+                 break;
+               /* If we didn't find a dom child with all visited
+                  predecessors just use the candidate we were checking.
+                  This happens for candidates in irreducible loops.  */
+               if (!worklist[spp - 1])
+                 break;
+               --spp;
+             }
+         bb = worklist[spp];
+         worklist[spp] = worklist[--sp];
+       }
       else
        break;
     }
   free (worklist);
+  sbitmap_free (visited);
 }
 
 void