Tree level if-conversion for vectorizer.

        * Makefile.in (OBJS-common): Add tree-if-conv.o
        (tree-if-conv.o): New rule.
        * cfgloop.c (flow_loop_exit_edges_find): Set EDGE_LOOP_EXIT flag.
        (get_loop_body_in_bfs_order): New.
        * cfgloop.h (get_loop_body_in_bfs_order): New.
        * tree-flow.h (enum move_pos): Move here from ..
        * tree-ssa-loop-im.c (enum move_pos): here.
        (movement_possibility): Make externally visible.
        * tree-optimize.c (init_tree_optimization_passes): New entry for
        if conversion pass.
        * tree-pass.h (pass_if_conversion): New.
        * tree-ssa-operands.c (get_expr_operands): Handle COND_EXPR.
        * tree-if-conv.c: New file.
        * doc/passes.texi: Document tree if-conversion pass.
        * doc/tree-ssa.texi: Same.

        testsuite:

        * gcc.dg/tree-ssa/ifc-20040816-1.c: New test.
        * gcc.dg/tree-ssa/ifc-20040816-2.c: New test.

From-SVN: r87073

1 files changed, 58 insertions, 1 deletions

diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index b5553d2..892b70d 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -315,7 +315,10 @@ flow_loop_exit_edges_find (struct loop *loop)
 	  basic_block dest = e->dest;
 
 	  if (!flow_bb_inside_loop_p (loop, dest))
-	    loop->exit_edges[num_exits++] = e;
+	    {
+	      e->flags |= EDGE_LOOP_EXIT;
+	      loop->exit_edges[num_exits++] = e;
+	    }
       }
     }
   free (bbs);
@@ -1085,6 +1088,60 @@ get_loop_body_in_dom_order (const struct loop *loop)
   return tovisit;
 }
 
+/* Get body of a LOOP in breadth first sort order.  */
+
+basic_block *
+get_loop_body_in_bfs_order (const struct loop *loop)
+{
+  basic_block *blocks;
+  basic_block bb;
+  bitmap visited;
+  unsigned int i = 0;
+  unsigned int vc = 1;
+
+  if (!loop->num_nodes)
+    abort ();
+
+  if (loop->latch == EXIT_BLOCK_PTR)
+    abort ();
+
+  blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
+  visited = BITMAP_XMALLOC ();
+
+  bb = loop->header;
+  while (i < loop->num_nodes)
+    {
+      edge e;
+      
+      if (!bitmap_bit_p (visited, bb->index))
+        { 
+          /* This basic block is now visited */
+          bitmap_set_bit (visited, bb->index);
+          blocks[i++] = bb;
+        }
+      
+      for (e = bb->succ; e; e = e->succ_next)
+        { 
+          if (flow_bb_inside_loop_p (loop, e->dest))
+            { 
+              if (!bitmap_bit_p (visited, e->dest->index))
+                { 
+                  bitmap_set_bit (visited, e->dest->index);
+                  blocks[i++] = e->dest;
+                }
+            }
+        }
+      
+      if (i < vc)
+        abort ();
+      
+      bb = blocks[vc++];
+    }
+  
+  BITMAP_XFREE (visited);
+  return blocks;
+}
+
 /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
 edge *
 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)