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

15 files changed, 1299 insertions, 14 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 743aad8..30a50be 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,21 @@
+2004-09-03  Devang Patel  <dpatel@apple.com>
+
+	* 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.	
+
 2004-09-03  H.J. Lu  <hongjiu.lu@intel.com>
 
 	PR target/14925:
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5990d2a..887b30f 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -887,7 +887,6 @@ C_AND_OBJC_OBJS = attribs.o c-errors.o c-lex.o c-pragma.o c-decl.o c-typeck.o \
 C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS)
 
 # Language-independent object files.
-
 OBJS-common = \
  tree-chrec.o tree-scalar-evolution.o tree-data-ref.o			   \
  tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
@@ -900,6 +899,7 @@ OBJS-common = \
  tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
  tree-ssa-loop-niter.o tree-ssa-loop-manip.o tree-ssa-threadupdate.o	   \
  tree-vectorizer.o tree-ssa-loop-ivcanon.o tree-ssa-propagate.o	 	   \
+ tree-if-conv.o	 	                                                   \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
  cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
  cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
@@ -1688,6 +1688,10 @@ tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
 tree-nested.o: tree-nested.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) \
    $(RTL_H) $(TM_P_H) function.h tree-dump.h tree-inline.h tree-iterator.h \
    tree-gimple.h cgraph.h $(EXPR_H) langhooks.h $(GGC_H) gt-tree-nested.h
+tree-if-conv.o: tree-if-conv.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
+   $(TREE_H) flags.h $(TIMEVAR_H) varray.h $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
+   cfgloop.h $(RTL_H) c-common.h tree-chrec.h tree-data-ref.h \
+   tree-scalar-evolution.h tree-pass.h 
 tree-iterator.o : tree-iterator.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \
    coretypes.h $(GGC_H) tree-iterator.h tree-gimple.h gt-tree-iterator.h
 tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
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)
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 3dce20a..60c80ce 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -272,6 +272,7 @@ extern unsigned get_loop_level (const struct loop *);
 /* Loops & cfg manipulation.  */
 extern basic_block *get_loop_body (const struct loop *);
 extern basic_block *get_loop_body_in_dom_order (const struct loop *);
+extern basic_block *get_loop_body_in_bfs_order (const struct loop *);
 extern edge *get_loop_exit_edges (const struct loop *, unsigned *);
 extern unsigned num_loop_branches (const struct loop *);
 
diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi
index 9af3659..16de6ea 100644
--- a/gcc/doc/passes.texi
+++ b/gcc/doc/passes.texi
@@ -385,6 +385,15 @@ The optimizations also use various utility functions contained in
 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
 @file{cfgloopmanip.c}.
 
+@item Tree level if-conversion for vectorizer
+
+This pass applies if-conversion to simple loops to help vectorizer.
+We identify if convertable loops, if-convert statements and merge
+basic blocks in one big block. The idea is to present loop in such
+form so that vectorizer can have one to one mapping between statements
+and available vector operations. This patch re-introduces COND_EXPR
+at GIMPLE level. This pass is located in @file{tree-if-conv.c}.
+
 @item Conditional constant propagation
 
 This pass relaxes a lattice of values in order to identify those
diff --git a/gcc/doc/tree-ssa.texi b/gcc/doc/tree-ssa.texi
index e54383a..1c88e9f 100644
--- a/gcc/doc/tree-ssa.texi
+++ b/gcc/doc/tree-ssa.texi
@@ -260,6 +260,9 @@ becomes
   a = T1;
 @end smallexample
 
+Tree level if-conversion pass re-introduces @code{?:} expression, if appropriate.
+It is used to vectorize loops with conditions using vector conditional operations.
+
 Note that in GIMPLE, @code{if} statements are also represented using
 @code{COND_EXPR}, as described below.
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 8cae9a8..276c31d 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2004-09-03  Devang Patel  <dpatel@apple.com>
+	
+	* gcc.dg/tree-ssa/ifc-20040816-1.c: New test.
+	* gcc.dg/tree-ssa/ifc-20040816-2.c: New test.
+	
 2004-09-03  Jan Beulich  <jbeulich@novell.com>
 
 	* g++.dg/abi/bitfield5.C: Use -mno-ms-bitfields.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c
new file mode 100644
index 0000000..2290563
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-1.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -fdump-tree-ifcvt-stats" { target *-*-* } } */
+
+#include <stdarg.h>
+#include <signal.h>
+
+#define N 16
+#define MAX 42
+
+extern void abort(void); 
+
+int main1 ()
+{  
+  int A[N] = {36,39,42,45,43,32,21,12,23,34,45,56,67,78,89,11};
+
+  int i, j;
+
+  for (i = 0; i < N; i++)
+    {
+      j = A[i];
+      A[i] = ( j >= MAX ? MAX : 0); 
+    }
+
+  /* check results:  */
+  for (i = 0; i < N; i++)
+    {
+      if (A[i] > MAX)
+	abort ();
+    }
+
+  return 0;
+}
+
+
+
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c
new file mode 100644
index 0000000..47ac652
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-20040816-2.c
@@ -0,0 +1,37 @@
+/* { dg-do compile } */
+/* { dg-options "-c -O2 -fdump-tree-ifcvt-stats" { target *-*-* } } */
+
+typedef float afloat __attribute__ ((__aligned__(16)));
+void foo(const afloat * __restrict__ zr_in,
+		const afloat * __restrict__ zi_in,
+		const afloat * __restrict__ zk_in,
+		afloat * __restrict__ zr_out,
+		afloat * __restrict__ zi_out,
+		afloat * __restrict__ zk_out,
+		float cr, float ci)
+{
+  unsigned int pi;
+  float tmp_r, tmp_i, tmp_k;
+  for (pi = 0; pi < (512)*(512); pi++) {
+    float zr = zr_in[pi];
+    float zi = zi_in[pi];
+    float zk = zk_in[pi];
+    
+    if (zr*zr + zi*zi >= 4.0f) {
+      tmp_r = zr;
+      tmp_i = zi;
+      tmp_k = zk;
+    } else {
+      tmp_r = (zr*zr - zi*zi + cr);
+      tmp_i = (2 * zr * zi + ci);
+      tmp_k = zk + 1.0f;
+    }
+    zr_out[pi] = tmp_r;
+    zi_out[pi] = tmp_i;
+    zk_out[pi] = tmp_k;
+  }
+}
+
+
+/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */
+
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index a82c90b..19d0b14 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -654,6 +654,22 @@ bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
 void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
 		tree *, tree *);
 
+/* In tree-ssa-loop-im.c  */
+/* The possibilities of statement movement.  */
+
+enum move_pos
+  {
+    MOVE_IMPOSSIBLE,		/* No movement -- side effect expression.  */
+    MOVE_PRESERVE_EXECUTION,	/* Must not cause the non-executed statement
+				   become executed -- memory accesses, ... */
+    MOVE_POSSIBLE		/* Unlimited movement.  */
+  };
+extern enum move_pos movement_possibility (tree);
+
+/* In tree-if-conv.c  */
+bool tree_if_conversion (struct loop *, bool);
+
+
 /* In tree-flow-inline.h  */
 static inline int phi_arg_from_edge (tree, edge);
 static inline bool is_call_clobbered (tree);
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
new file mode 100644
index 0000000..e435512
--- /dev/null
+++ b/gcc/tree-if-conv.c
@@ -0,0 +1,1102 @@
+/* If-conversion for vectorizer.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+   Contributed by Devang Patel <dpatel@apple.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+/* This pass implements tree level if-conversion transformation of loops. 
+   Initial goal is to help vectorizer vectorize loops with conditions.
+
+   A short description of if-conversion:
+
+     o Decide if a loop is if-convertable or not.
+     o Walk all loop basic blocks in breadth first order (BFS order).
+       o Remove conditional statements (at the end of basic block)
+         and propogate condition into destination basic blcoks'
+	 predicate list.
+       o Replace modify expression with conditional modify expression
+         using current basic block's condition.
+     o Merge all basic blocks
+       o Replace phi nodes with conditional modify expr
+       o Merge all basic blocks into header
+
+     Sample transformation:
+
+     INPUT
+     -----
+
+     # i_23 = PHI <0(0), i_18(10)>;
+     <L0>:;
+     j_15 = A[i_23];
+     if (j_15 > 41) goto <L1>; else goto <L17>;
+
+     <L17>:;
+     goto <bb 3> (<L3>);
+
+     <L1>:;
+
+     # iftmp.2_4 = PHI <0(8), 42(2)>;
+     <L3>:;
+     A[i_23] = iftmp.2_4;
+     i_18 = i_23 + 1;
+     if (i_18 <= 15) goto <L19>; else goto <L18>;
+
+     <L19>:;
+     goto <bb 1> (<L0>);
+
+     <L18>:;
+
+     OUTPUT
+     ------
+
+     # i_23 = PHI <0(0), i_18(10)>;
+     <L0>:;
+     j_15 = A[i_23];
+     
+     <L3>:;
+     iftmp.2_4 = j_15 > 41 ? 42 : 0;
+     A[i_23] = iftmp.2_4;
+     i_18 = i_23 + 1;
+     if (i_18 <= 15) goto <L19>; else goto <L18>;
+     
+     <L19>:;
+     goto <bb 1> (<L0>);
+
+     <L18>:;
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "tree.h"
+#include "c-common.h"
+#include "flags.h"
+#include "timevar.h"
+#include "varray.h"
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "target.h"
+
+/* local function prototypes */
+static void main_tree_if_conversion (void);
+static tree tree_if_convert_stmt (struct loop *loop, tree, tree, 
+				  block_stmt_iterator *);
+static void tree_if_convert_cond_expr (struct loop *, tree, tree, 
+				       block_stmt_iterator *);
+static bool if_convertable_phi_p (struct loop *, basic_block, tree);
+static bool if_convertable_modify_expr_p (struct loop *, basic_block, tree);
+static bool if_convertable_stmt_p (struct loop *, basic_block, tree);
+static bool if_convertable_bb_p (struct loop *, basic_block, bool);
+static bool if_convertable_loop_p (struct loop *, bool);
+static void add_to_predicate_list (basic_block, tree);
+static tree add_to_dst_predicate_list (struct loop * loop, tree, tree, tree,
+				       block_stmt_iterator *);
+static void clean_predicate_lists (struct loop *loop);
+static bool find_phi_replacement_condition (basic_block, tree *,
+                                            block_stmt_iterator *);
+static void replace_phi_with_cond_modify_expr (tree, tree, bool,
+                                               block_stmt_iterator *);
+static void process_phi_nodes (struct loop *);
+static void combine_blocks (struct loop *);
+static tree ifc_temp_var (tree, tree);
+static bool pred_blocks_visited_p (basic_block, bitmap *);
+static basic_block * get_loop_body_in_if_conv_order (const struct loop *loop);
+static bool bb_with_exit_edge_p (basic_block);
+
+/* List of basic blocks in if-conversion-suitable order.  */
+static basic_block *ifc_bbs;
+
+/* Main entry point.
+   Apply if-conversion to the LOOP. Return true if successful otherwise return
+   false. If false is returned then loop remains unchanged.  
+   FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
+   for vectorizer or not. If it is used for vectorizer, additional checks are
+   used. (Vectorization checks are not yet imlemented).  */
+
+bool
+tree_if_conversion (struct loop *loop, bool for_vectorizer)
+{
+  basic_block bb;
+  block_stmt_iterator itr;
+  tree cond;
+  unsigned int i;
+
+  ifc_bbs = NULL;
+
+  /* if-conversion is not appropriate for all loops. First, check if loop  is
+     if-convertable or not.  */
+  if (!if_convertable_loop_p (loop, for_vectorizer))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,"-------------------------\n");
+      if (ifc_bbs)
+	{
+	  free (ifc_bbs);
+	  ifc_bbs = NULL;
+	}
+      free_dominance_info (CDI_POST_DOMINATORS);
+      free_df ();
+      return false;
+    }
+
+  cond = NULL_TREE;
+  
+  /* Do actual work now.  */
+  for (i = 0; i < loop->num_nodes; i++)  
+    {
+      bb = ifc_bbs [i];
+
+      /* Update condition using predicate list.  */
+      cond = bb->aux;
+
+      /* Process all statements in this basic block.
+	 Remove conditional expresion, if any, and annotate
+	 destination basic block(s) appropriately.  */
+      for (itr = bsi_start (bb); !bsi_end_p (itr); /* empty */)
+	{
+	  tree t = bsi_stmt (itr);
+	  cond = tree_if_convert_stmt (loop, t, cond, &itr);
+	  if (!bsi_end_p (itr))
+	    bsi_next (&itr);
+	}
+
+      /* If current bb has only one successor, then consider it as an 
+	 unconditional goto.  */
+      if (bb->succ && !bb->succ->succ_next)
+	{
+	  basic_block bb_n = bb->succ->dest;
+	  if (cond != NULL_TREE)
+	    add_to_predicate_list (bb_n, cond);
+	  cond = NULL_TREE;
+	}
+    }
+
+  /* Now, all statements are if-converted and basic blocks are
+     annotated appropriately. Combine all basic block into one huge
+     basic block.  */
+  combine_blocks (loop);
+
+  /* clean up */
+  clean_predicate_lists (loop);
+  free (ifc_bbs);
+  ifc_bbs = NULL;
+  free_df ();
+
+  return true;
+}
+
+/* if-convert stmt T which is part of LOOP. 
+   If T is a MODIFY_EXPR than it is converted into conditional modify 
+   expression using COND.  For conditional expressions, add condition in the 
+   destination basic block's predicate list and remove conditional 
+   expression itself. BSI is the iterator used to traverse statements of 
+   loop. It is used here when it is required to delete current statement.  */
+
+static tree
+tree_if_convert_stmt (struct loop *  loop, tree t, tree cond, 
+		      block_stmt_iterator *bsi)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "------if-convert stmt\n");
+      print_generic_stmt (dump_file, t, TDF_SLIM);
+      print_generic_stmt (dump_file, cond, TDF_SLIM);
+    }
+
+  switch (TREE_CODE (t))
+    {
+      /* Labels are harmless here.  */
+    case LABEL_EXPR:
+      break;
+
+    case MODIFY_EXPR:
+      /* This modify_expr is killing previous value of LHS. Appropriate value will
+	 be selected by PHI node based on condition. It is possible that before
+	 this transformation, PHI nodes was selecting default value and now it will
+	 use this new value. This is OK because it does not change validity the 
+	 program.  */
+      break;
+
+    case GOTO_EXPR:
+      /* Unconditional goto */
+      add_to_predicate_list (bb_for_stmt (TREE_OPERAND (t, 1)), cond);
+      bsi_remove (bsi);
+      cond = NULL_TREE;
+      break;
+
+    case COND_EXPR:
+      /* Update destination blocks' predicate list and remove this
+	 condition expression.  */
+      tree_if_convert_cond_expr (loop, t, cond, bsi);
+      cond = NULL_TREE; 
+      break;
+	
+    default:    
+      abort ();
+      break;
+    }
+  return cond;
+}
+
+/* STMT is COND_EXPR. Update two destination's predicate list.
+   Remove COND_EXPR, if it is not the loop exit condition. Otherwise
+   update loop exit condition appropriatly.  BSI is the iterator
+   used to traverse statement list. STMT is part of loop LOOP.  */
+
+static void
+tree_if_convert_cond_expr (struct loop *loop, tree stmt, tree cond, 
+			   block_stmt_iterator *bsi)
+{
+  tree then_clause, else_clause, c, new_cond;
+  new_cond = NULL_TREE;
+
+#ifdef ENABLE_CHECKING
+  if (TREE_CODE (stmt) != COND_EXPR)
+    abort ();
+#endif
+
+  c = TREE_OPERAND (stmt, 0);
+  then_clause = TREE_OPERAND (stmt, 1);
+  else_clause = TREE_OPERAND (stmt, 2);
+  
+  /* Create temp. for condition.  */
+  if (!is_gimple_reg (c))
+    {
+      tree new_stmt;
+      new_stmt = ifc_temp_var (TREE_TYPE (c), unshare_expr (c));
+      bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
+      c = TREE_OPERAND (new_stmt, 0);
+    }
+	
+  /* Add new condition into destination's predicate list.  */
+  if (then_clause)
+    /* if 'c' is true then then_clause is reached.  */
+    new_cond = add_to_dst_predicate_list (loop, then_clause, cond, c, bsi);
+  
+  if (else_clause)
+    {
+      /* if 'c' is false then else_clause is reached.  */
+      tree c2 = build1 (TRUTH_NOT_EXPR, 
+			boolean_type_node, 
+			unshare_expr (c));
+      add_to_dst_predicate_list (loop, else_clause, cond, c2, bsi);
+    }
+
+  /* Now this conditional statement is redundent. Remove it.
+     But, do not remove exit condition! Update exit condition
+     using new condition.  */
+  if (!bb_with_exit_edge_p (bb_for_stmt (stmt)))
+    {
+      bsi_remove (bsi);
+      cond = NULL_TREE;
+    }
+  else if (new_cond != NULL_TREE)
+    {
+      TREE_OPERAND (stmt, 0) = new_cond;
+      modify_stmt (stmt);
+    }
+  return;
+}
+
+/* Return true, iff PHI is if-convertable. PHI is part of loop LOOP
+   and it belongs to basic block BB.
+   PHI is not if-convertable 
+   - if it has more than 2 arguments.
+   - Virtual PHI is immediately used in another PHI node.  */
+
+static bool
+if_convertable_phi_p (struct loop *loop, basic_block bb, tree phi)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "-------------------------\n");
+      print_generic_stmt (dump_file, phi, TDF_SLIM);
+    }
+  
+  if (bb != loop->header && PHI_NUM_ARGS (phi) != 2)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "More than two phi node args.\n");
+      return false;
+    }
+  
+  if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
+    {
+      int j;
+      dataflow_t df = get_immediate_uses (phi);
+      int num_uses = num_immediate_uses (df);
+      for (j = 0; j < num_uses; j++)
+	{
+	  tree use = immediate_use (df, j);
+	  if (TREE_CODE (use) == PHI_NODE)
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "Difficult to handle this virtual phi.\n");
+	      return false;
+	    }
+	}
+    }
+
+  return true;
+}
+
+/* Return true, if M_EXPR is if-convertable.  
+   MODIFY_EXPR is not if-convertable if,
+   - It is not movable.
+   - It could trap.
+   - LHS is not var decl.
+  MODIFY_EXPR is part of block BB, which is inside loop LOOP.
+*/
+
+static bool
+if_convertable_modify_expr_p (struct loop *loop, basic_block bb, tree m_expr)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "-------------------------\n");
+      print_generic_stmt (dump_file, m_expr, TDF_SLIM);
+    }
+  
+  /* Be conservative and do not handle immovable expressions.  */
+  if (movement_possibility (m_expr) == MOVE_IMPOSSIBLE)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "stmt is movable. Don't take risk\n");
+      return false;
+    }
+
+  /* See if it needs speculative loading or not.  */
+  if (bb != loop->header 
+      && tree_could_trap_p (TREE_OPERAND (m_expr, 1)))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "tree could trap...\n");
+      return false;
+    }
+
+  if (TREE_CODE (TREE_OPERAND (m_expr, 1)) == CALL_EXPR)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "CALL_EXPR \n");
+      return false;
+    }
+
+  if (TREE_CODE (TREE_OPERAND (m_expr, 0)) != SSA_NAME
+      && bb != loop->header
+      && !bb_with_exit_edge_p (bb))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "LHS is not var\n");
+	  print_generic_stmt (dump_file, m_expr, TDF_SLIM);
+	}
+      return false;
+    }
+
+
+  return true;
+}
+
+/* Return true, iff STMT is if-convertable.  
+   Statement is if-convertable if,
+   - It is if-converatable MODIFY_EXPR
+   - IT is LABEL_EXPR, GOTO_EXPR or COND_EXPR.  
+   STMT is inside block BB, which is inside loop LOOP.  */
+
+static bool
+if_convertable_stmt_p (struct loop *loop, basic_block bb, tree stmt)
+{
+  switch (TREE_CODE (stmt))
+    {
+    case LABEL_EXPR:
+      break;
+      
+    case MODIFY_EXPR:
+      
+      if (!if_convertable_modify_expr_p (loop, bb, stmt))
+	return false;
+      break;
+      
+    case GOTO_EXPR:
+    case COND_EXPR:
+      break;
+      
+    default:
+      /* Don't know what to do with 'em so don't do anything.  */
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "don't know what to do\n");
+	  print_generic_stmt (dump_file, stmt, TDF_SLIM);
+	}
+      return false;
+      break;
+    }
+
+  return true;
+}
+
+/* Return true, iff BB is if-convertable. 
+   Note: This routine does _not_ check basic block statements and phis.
+   Basic block is not if-converatable if,
+   - Basic block is non-empty and it is after exit block (in BFS order).  
+   - Basic block is after exit block but before latch.
+   - Basic block edge(s) is not normal.  
+   EXIT_BB_SEEN is true if basic block with exit edge is already seen.
+   BB is inside loop LOOP. */
+
+static bool 
+if_convertable_bb_p (struct loop *loop, basic_block bb, bool exit_bb_seen)
+{
+  edge e;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "----------[%d]-------------\n", bb->index);
+  
+  if (exit_bb_seen)
+    {
+      if (bb != loop->latch)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "basic block after exit bb but before latch\n");
+	  return false;
+	}
+      else if (!empty_block_p (bb))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "non empty basic block after exit bb\n");
+	  return false;
+	}
+    }
+  
+  /* Be less adveturous and handle only normal edges.  */
+  for (e = bb->succ; e; e = e->succ_next)
+    if (e->flags & 
+	(EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
+      {
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  fprintf (dump_file,"Difficult to handle edges\n");
+	return false;
+      }
+
+  return true;
+}
+
+/* Return true, iff LOOP is if-convertable. 
+   LOOP is if-convertable if,
+   - It is innermost.
+   - It has two or more basic blocks.
+   - It has only one exit.
+   - Loop header is not the exit edge. 
+   - If its basic blocks and phi nodes are if convertable. See above for 
+     more info.   
+   FOR_VECTORIZER enables vectorizer specific checks. For example, support
+   for vector conditions, data dependency checks etc.. (Not implemented yet).  */
+
+static bool
+if_convertable_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
+{
+  tree phi;
+  basic_block bb;
+  block_stmt_iterator itr;
+  unsigned int i;
+  edge e;
+  bool exit_bb_seen = false;
+
+  /* Handle only inner most loop.  */
+  if (!loop || loop->inner)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "not inner most loop\n");
+      return false;
+    }
+  
+  flow_loop_scan (loop, LOOP_ALL);
+
+  /* If only one block, no need for if-conversion.  */
+  if (loop->num_nodes <= 2)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "less thant 2 basic blocks\n");
+      return false;
+    }
+  
+  /* More than one loop exit is too much to handle.  */
+  if (loop->num_exits > 1)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "multiple exits\n");
+      return false;
+    }
+
+  /* ??? Check target's vector conditional operation support for vectorizer.  */
+
+  /* If one of the loop header's edge is exit edge then do not apply
+     if-conversion.  */
+  for (e = loop->header->succ; e; e = e->succ_next)
+    if ( e->flags & EDGE_LOOP_EXIT)
+      return false;
+
+  compute_immediate_uses (TDFA_USE_OPS|TDFA_USE_VOPS, NULL);
+
+  calculate_dominance_info (CDI_DOMINATORS);
+  calculate_dominance_info (CDI_POST_DOMINATORS);
+
+  /* Allow statements that can be handled during if-conversion.  */
+  ifc_bbs = get_loop_body_in_if_conv_order (loop);
+  if (!ifc_bbs)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,"Irreducible loop\n");
+      free_dominance_info (CDI_POST_DOMINATORS);
+      return false;
+    }
+    
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      bb = ifc_bbs[i];
+
+      if (!if_convertable_bb_p (loop, bb, exit_bb_seen))
+	return false;
+
+      /* Check statements.  */
+      for (itr = bsi_start (bb); !bsi_end_p (itr); bsi_next (&itr))
+	if (!if_convertable_stmt_p (loop, bb, bsi_stmt (itr)))
+	  return false;
+      /* ??? Check data dependency for vectorizer.  */
+
+      /* What about phi nodes ? */
+      for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+	if (!if_convertable_phi_p (loop, bb, phi))
+	  return false;
+
+      if (bb_with_exit_edge_p (bb))
+	exit_bb_seen = true;
+    }
+
+  /* OK. Did not find any potential issues so go ahead in if-convert
+     this loop. Now there is no looking back.  */
+  if (dump_file)
+    fprintf (dump_file,"Applying if-conversion\n");
+
+  free_dominance_info (CDI_POST_DOMINATORS);
+  return true;
+}
+
+/* Add condition COND into predicate list of basic block BB.  */
+
+static void
+add_to_predicate_list (basic_block bb, tree new_cond)
+{
+  tree cond = bb->aux;
+  
+  if (cond)
+    cond = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+			unshare_expr (cond), new_cond));
+  else
+    cond = new_cond;
+
+  bb->aux = cond;
+}
+
+/* Add condition COND into DST's predicate list.  PREV_COND is
+   existing condition.  */
+
+static tree
+add_to_dst_predicate_list (struct loop * loop, tree dst, 
+			   tree prev_cond, tree cond,
+			   block_stmt_iterator *bsi)
+{
+  basic_block bb;
+  tree new_cond = NULL_TREE;
+
+#ifdef ENABLE_CHECKING
+  if (TREE_CODE (dst) != GOTO_EXPR)
+    abort ();
+#endif
+  bb = label_to_block (TREE_OPERAND (dst, 0));
+  if (!flow_bb_inside_loop_p (loop, bb))
+    return NULL_TREE;
+
+  if (prev_cond == boolean_true_node || !prev_cond)
+    new_cond = unshare_expr (cond);
+  else
+    {
+      tree tmp_stmt;
+      /* new_cond == prev_cond AND cond */
+      tree tmp = build (TRUTH_AND_EXPR, boolean_type_node,
+			unshare_expr (prev_cond), cond);
+      tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
+      bsi_insert_before (bsi, tmp_stmt, BSI_SAME_STMT);
+      new_cond = TREE_OPERAND (tmp_stmt, 0);
+    }
+  add_to_predicate_list (bb, new_cond);
+  return new_cond;
+}
+
+/* During if-conversion aux field from basic block is used to hold predicate
+   list. Clean each basic block's predicate list for the given LOOP.  */
+
+static void
+clean_predicate_lists (struct loop *loop)
+{
+  unsigned int i;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    ifc_bbs[i]->aux = NULL;
+}
+
+/* Basic block BB has two predecessors. Using predecessor's aux field, set
+   appropriate condition COND for the PHI node replacement. Return true if
+   phi arguments are condition is selected from second predecessor.  */
+
+static bool
+find_phi_replacement_condition (basic_block bb, tree *cond,
+                                block_stmt_iterator *bsi)
+{
+  edge e;
+  basic_block p1 = NULL;
+  basic_block p2 = NULL;
+  bool switch_args = false;
+  tree tmp_cond;
+
+  for (e = bb->pred; e; e = e->pred_next)
+    {
+      if (p1 == NULL)
+	  p1 = e->src;
+      else if (p2 == NULL)
+	p2 = e->src;
+      else
+	/* More than two predecessors. This is not expected.  */
+	abort ();
+    }
+
+  /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
+  tmp_cond = p1->aux;
+  if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
+    {
+      *cond  = p2->aux;
+      switch_args = true;
+    }
+  else
+    {
+      *cond  = p1->aux;
+      switch_args = false;
+    }
+    
+  /* Create temp. for the condition. Vectorizier prefers to have gimple 
+     value as condition. Various targets use different means to communicate 
+     condition in vector compare operation. Using gimple value allows compiler 
+     to emit vector compare and select RTL without exposing compare's result.  */
+  if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
+    {
+      tree new_stmt;
+
+      new_stmt = ifc_temp_var (TREE_TYPE (*cond), unshare_expr (*cond));
+      bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
+      bsi_next (bsi);
+      *cond = TREE_OPERAND (new_stmt, 0);
+    }
+
+#ifdef ENABLE_CHECKING
+  if (*cond == NULL_TREE)
+    abort ();
+#endif
+
+  return switch_args;
+}
+
+
+/* Replace PHI node with conditional modify expr using COND.  
+   This routine does not handle PHI nodes with more than two arguments. 
+   For example,
+     S1: A = PHI <x1(1), x2(5)
+   is converted into,
+     S2: A = cond ? x1 : x2;
+   S2 is inserted at the top of basic block's statement list.
+   PHI arguments are switched if SWITCH_ARGS is true.
+*/
+
+static void
+replace_phi_with_cond_modify_expr (tree phi, tree cond, bool switch_args,
+                                   block_stmt_iterator *bsi)
+{
+  tree new_stmt;
+  basic_block bb;
+  tree rhs;
+  tree arg_0, arg_1;
+
+#ifdef ENABLE_CHECKING
+  if (TREE_CODE (phi) != PHI_NODE)
+    abort ();
+
+  /* If this is not filtered earlier, then now it is too late.  */
+  if (PHI_NUM_ARGS (phi) != 2)
+     abort ();
+#endif
+
+  /* Find basic block and initialize iterator.  */
+  bb = bb_for_stmt (phi);
+
+  new_stmt = NULL_TREE;
+  arg_0 = NULL_TREE;
+  arg_1 = NULL_TREE;
+  
+  /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
+  if (switch_args)
+    {
+      arg_0 = PHI_ARG_DEF (phi, 1);
+      arg_1 = PHI_ARG_DEF (phi, 0);
+    }
+  else
+    {
+      arg_0 = PHI_ARG_DEF (phi, 0);
+      arg_1 = PHI_ARG_DEF (phi, 1);
+    }
+
+  /* Build new RHS using selected condtion and arguments.  */
+  rhs = build (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+	       unshare_expr (cond), unshare_expr (arg_0),
+	       unshare_expr (arg_1));
+
+  /* Create new MODIFY expresstion using RHS.  */
+  new_stmt = build (MODIFY_EXPR, TREE_TYPE (PHI_RESULT (phi)),
+		    unshare_expr (PHI_RESULT (phi)), rhs);
+
+  /* Make new statement definition of the original phi result.  */
+  SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = new_stmt;
+
+  /* Set basic block and insert using iterator.  */
+  set_bb_for_stmt (new_stmt, bb);
+
+  bsi_insert_after (bsi, new_stmt, BSI_SAME_STMT);
+  bsi_next (bsi);
+
+  modify_stmt (new_stmt);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "new phi replacement stmt\n");
+      print_generic_stmt (dump_file, new_stmt, TDF_SLIM);
+    }
+}
+
+/* Process phi nodes for the given  LOOP.  Replace phi nodes with cond 
+   modify expr.  */
+
+static void
+process_phi_nodes (struct loop *loop)
+{
+  basic_block bb;
+  unsigned int orig_loop_num_nodes = loop->num_nodes;
+  unsigned int i;
+
+  /* Replace phi nodes with cond. modify expr.  */
+  for (i = 1; i < orig_loop_num_nodes; i++)
+    {
+      tree phi, cond;
+      block_stmt_iterator bsi;
+      bool switch_args = false;
+      bb = ifc_bbs[i];
+      
+      if (bb == loop->header || bb == loop->latch)
+	continue;
+
+      phi = phi_nodes (bb);
+      bsi = bsi_start (bb);
+
+      /* BB has two predecessors. Using predecessor's aux field, set
+	 appropriate condition for the PHI node replacement.  */
+      if (phi)
+	switch_args = find_phi_replacement_condition (bb, &cond, &bsi);
+
+      while (phi)
+	{
+	  tree next = TREE_CHAIN (phi);
+	  replace_phi_with_cond_modify_expr (phi, cond, switch_args, &bsi);
+	  release_phi_node (phi);
+	  phi = next;
+	}
+      bb_ann (bb)->phi_nodes = NULL;
+    }
+  return;
+}
+
+/* Combine all basic block from the given LOOP into one or two super 
+   basic block.  Replace PHI nodes with conditional modify expression. */
+
+static void
+combine_blocks (struct loop *loop)
+{
+  basic_block bb, exit_bb, merge_target_bb;
+  unsigned int orig_loop_num_nodes = loop->num_nodes;
+  unsigned int i;
+
+  /* Process phi nodes to prepare blocks for merge.  */
+  process_phi_nodes (loop);
+
+  exit_bb = NULL;
+
+  /* Merge basic blocks */
+  merge_target_bb = loop->header;
+  for (i = 1; i < orig_loop_num_nodes; i++)
+    {
+      edge e;
+      block_stmt_iterator bsi;
+      tree_stmt_iterator last;
+
+      bb = ifc_bbs[i];
+
+      if (bb == loop->latch)
+	continue;
+
+      if (!exit_bb && bb_with_exit_edge_p (bb))
+	  exit_bb = bb;
+
+      if (bb == exit_bb)
+	{
+	  edge new_e;
+
+	  /* Connect this node with loop header.  */
+	  new_e = make_edge (ifc_bbs[0], bb, EDGE_FALLTHRU);
+	  set_immediate_dominator (CDI_DOMINATORS, bb, ifc_bbs[0]);
+
+	  if (exit_bb != loop->latch)
+	    {
+	      /* Redirect non-exit edge to loop->latch.  */
+	      for (e = bb->succ; e; e = e->succ_next)
+		if (!(e->flags & EDGE_LOOP_EXIT))
+		  {
+		    redirect_edge_and_branch (e, loop->latch);
+		    set_immediate_dominator (CDI_DOMINATORS, loop->latch, bb);
+		  }
+	    }
+	  continue;
+	}
+
+      /* It is time to remove this basic block.	 First remove edges.  */
+      while (bb->succ != NULL)
+	ssa_remove_edge (bb->succ);
+      while (bb->pred != NULL)
+	ssa_remove_edge (bb->pred);
+
+      /* Remove labels and make stmts member of loop->header.  */
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
+	{
+	  if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
+	    bsi_remove (&bsi);
+	  else
+	    {
+	      set_bb_for_stmt (bsi_stmt (bsi), merge_target_bb);
+	      bsi_next (&bsi);
+	    }
+	}
+
+      /* Update stmt list.  */
+      last = tsi_last (merge_target_bb->stmt_list);
+      tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
+      bb->stmt_list = NULL;
+
+      /* Update dominator info.  */
+      if (dom_computed[CDI_DOMINATORS])
+	delete_from_dominance_info (CDI_DOMINATORS, bb);
+      if (dom_computed[CDI_POST_DOMINATORS])
+	delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
+      
+      /* Remove basic block.  */
+      remove_bb_from_loops (bb);
+      expunge_block (bb);
+    }
+}
+
+/* Make new  temp variable of type TYPE. Add MODIFY_EXPR to assign EXP 
+   to the new variable.  */
+
+static tree
+ifc_temp_var (tree type, tree exp)
+{
+  const char *name = "_ifc_";
+  tree var, stmt, new_name;
+
+  if (is_gimple_reg (exp))
+    return exp;
+
+  /* Create new temporary variable.  */
+  var = create_tmp_var (type, name);
+  add_referenced_tmp_var (var);
+
+  /* Build new statement to assigne EXP to new variable.  */
+  stmt = build (MODIFY_EXPR, type, var, exp);
+  
+  /* Get SSA name for the new variable and set make new statement
+     its definition statment.  */
+  new_name = make_ssa_name (var, stmt);
+  TREE_OPERAND (stmt, 0) = new_name;
+  SSA_NAME_DEF_STMT (new_name) = stmt;
+
+  return stmt;
+}
+
+
+/* Return TRUE iff, all pred blocks of BB are visited.
+   Bitmap VISITED keeps history of visited blocks.  */
+
+static bool
+pred_blocks_visited_p (basic_block bb, bitmap *visited)
+{
+  edge e;
+  for (e = bb->pred; e; e = e->pred_next)
+    if (!bitmap_bit_p (*visited, e->src->index))
+      return false;
+  
+  return true;
+}
+
+/* Get body of a LOOP in suitable order for if-conversion.
+   It is caller's responsibility to deallocate basic block
+   list.  If-conversion suitable order is, BFS order with one
+   additional constraint. Select block in BFS block, if all
+   pred are already selected.  */
+
+static basic_block * 
+get_loop_body_in_if_conv_order (const struct loop *loop)
+{
+  basic_block *blocks, *blocks_in_bfs_order;
+  basic_block bb;
+  bitmap visited;
+  unsigned int index = 0;
+  unsigned int visited_count = 0;
+
+  if (!loop->num_nodes)
+    abort ();
+  
+  if (loop->latch == EXIT_BLOCK_PTR)
+    abort ();
+
+  blocks = xcalloc (loop->num_nodes, sizeof (basic_block));
+  visited = BITMAP_XMALLOC ();
+
+  blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
+
+  index = 0;
+  while (index < loop->num_nodes)
+    {
+      bb = blocks_in_bfs_order [index];
+      
+      if (bb->flags & BB_IRREDUCIBLE_LOOP)
+	{
+	  free (blocks_in_bfs_order);
+	  BITMAP_FREE (visited);
+	  free (blocks);
+	  return NULL;
+	}
+      if (!bitmap_bit_p (visited, bb->index))
+	{
+	  if (pred_blocks_visited_p (bb, &visited)
+	      || bb == loop->header)
+	    {
+	      /* This block is now visited.  */
+	      bitmap_set_bit (visited, bb->index);
+	      blocks[visited_count++] = bb;
+	    }
+	}
+      index++;
+      if (index == loop->num_nodes
+	  && visited_count != loop->num_nodes)
+	{
+	  /* Not done yet.  */
+	  index = 0;
+	}
+    }
+  free (blocks_in_bfs_order);
+  BITMAP_XFREE (visited);
+  return blocks;
+}
+
+/* Return true if one of the basic block BB edge is loop exit.  */
+
+static bool
+bb_with_exit_edge_p (basic_block bb)
+{
+  edge e;
+  bool exit_edge_found = false;
+
+  for (e = bb->succ; e && !exit_edge_found ; e = e->succ_next)
+    if (e->flags & EDGE_LOOP_EXIT)
+      exit_edge_found = true;
+
+  return exit_edge_found;
+}
+
+/* Tree if-conversion pass management.  */
+
+static void
+main_tree_if_conversion (void)
+{
+  unsigned i, loop_num;
+  struct loop *loop;
+
+  if (!current_loops)
+    return;
+
+  loop_num = current_loops->num;
+  for (i = 0; i < loop_num; i++)
+    {
+      loop =  current_loops->parray[i];
+      if (!loop)
+      continue;
+
+      tree_if_conversion (loop, true);
+    }
+
+}
+
+static bool
+gate_tree_if_conversion (void)
+{
+  return true;
+}
+
+struct tree_opt_pass pass_if_conversion =
+{
+  "ifcvt",                           /* name */
+  gate_tree_if_conversion,           /* gate */
+  main_tree_if_conversion,           /* execute */
+  NULL,                              /* sub */
+  NULL,                              /* next */
+  0,                                 /* static_pass_number */
+  0,                                 /* tv_id */
+  PROP_cfg | PROP_ssa | PROP_alias,  /* properties_required */
+  0,                                 /* properties_provided */
+  0,                                 /* properties_destroyed */
+  TODO_dump_func,                    /* todo_flags_start */
+  TODO_dump_func 
+    | TODO_verify_ssa
+    | TODO_verify_stmts 
+    | TODO_verify_flow               /* todo_flags_finish */
+};
+
diff --git a/gcc/tree-optimize.c b/gcc/tree-optimize.c
index f14f1b0..e3dcc95 100644
--- a/gcc/tree-optimize.c
+++ b/gcc/tree-optimize.c
@@ -368,6 +368,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_loop_init);
   NEXT_PASS (pass_lim);
   NEXT_PASS (pass_iv_canon);
+  NEXT_PASS (pass_if_conversion);
   NEXT_PASS (pass_vectorize);
   NEXT_PASS (pass_complete_unroll);
   NEXT_PASS (pass_loop_done);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 0609adc..0712a4e 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -110,6 +110,7 @@ extern struct tree_opt_pass pass_loop;
 extern struct tree_opt_pass pass_loop_init;
 extern struct tree_opt_pass pass_lim;
 extern struct tree_opt_pass pass_iv_canon;
+extern struct tree_opt_pass pass_if_conversion;
 extern struct tree_opt_pass pass_vectorize;
 extern struct tree_opt_pass pass_complete_unroll;
 extern struct tree_opt_pass pass_loop_done;
diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c
index c5de645..6aad731 100644
--- a/gcc/tree-ssa-loop-im.c
+++ b/gcc/tree-ssa-loop-im.c
@@ -47,16 +47,6 @@ struct depend
   struct depend *next;
 };
 
-/* The possibilities of statement movement.  */
-
-enum move_pos
-{
-  MOVE_IMPOSSIBLE,		/* No movement -- side effect expression.  */
-  MOVE_PRESERVE_EXECUTION,	/* Must not cause the non-executed statement
-				   become executed -- memory accesses, ... */
-  MOVE_POSSIBLE			/* Unlimited movement.  */
-};
-
 /* The auxiliary data kept for each statement.  */
 
 struct lim_aux_data
@@ -170,7 +160,7 @@ for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
    because it may trap), return MOVE_PRESERVE_EXECUTION.
    Otherwise return MOVE_IMPOSSIBLE.  */
 
-static enum move_pos
+enum move_pos
 movement_possibility (tree stmt)
 {
   tree lhs, rhs;
diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c
index a87d845..200f4b5 100644
--- a/gcc/tree-ssa-operands.c
+++ b/gcc/tree-ssa-operands.c
@@ -625,7 +625,6 @@ finalize_ssa_vuses (vuse_optype *old_ops_p)
   return vuse_ops;
 }
 
-
 /* Return a new v_must_def operand vector for STMT, comparing to OLD_OPS_P.  */
 
 static v_must_def_optype
@@ -1081,6 +1080,12 @@ get_expr_operands (tree stmt, tree *expr_p, int flags)
       get_call_expr_operands (stmt, expr);
       return;
 
+    case COND_EXPR:
+      get_expr_operands (stmt, &COND_EXPR_COND (expr), opf_none);
+      get_expr_operands (stmt, &TREE_OPERAND (expr, 1), opf_none);
+      get_expr_operands (stmt, &TREE_OPERAND (expr, 2), opf_none);
+      return;
+
     case MODIFY_EXPR:
       {
 	int subflags;