Reorganize the analysis of basic block predication.

2010-05-26  Sebastian Pop  <sebastian.pop@amd.com>

	* tree-if-conv.c (add_to_dst_predicate_list): Do not pass a statemet
	iterator in parameter.  Do not generate code during the analysis.
	(tree_if_convert_cond_stmt): Removed.
	(tree_if_convert_stmt): Removed.
	(predicate_bbs): New.
	(if_convertible_loop_p): Call predicate_bbs.
	(tree_if_conversion): Simplify the top-level logic as predicate_bbs
	now contains all the analysis part.

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

1 files changed, 150 insertions, 163 deletions

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index 60033e25fc6..da6b1cde27a 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -147,15 +147,13 @@ add_to_predicate_list (basic_block bb, tree new_cond)
   bb->aux = cond;
 }
 
-/* Add the condition COND to the previous condition PREV_COND, and add this
-   to the predicate list of the destination of edge E.  GSI is the
-   place where the gimplification of the resulting condition should
-   output code.  LOOP is the loop to be if-converted.  */
+/* Add the condition COND to the previous condition PREV_COND, and add
+   this to the predicate list of the destination of edge E.  LOOP is
+   the loop to be if-converted.  */
 
 static tree
 add_to_dst_predicate_list (struct loop *loop, edge e,
-			   tree prev_cond, tree cond,
-			   gimple_stmt_iterator *gsi)
+			   tree prev_cond, tree cond)
 {
   tree new_cond = NULL_TREE;
 
@@ -166,25 +164,13 @@ add_to_dst_predicate_list (struct loop *loop, edge e,
     new_cond = unshare_expr (cond);
   else
     {
-      tree tmp;
-      gimple tmp_stmt = NULL;
-
-      prev_cond = force_gimple_operand_gsi (gsi, unshare_expr (prev_cond),
-					    true, NULL, true, GSI_SAME_STMT);
-
-      cond = force_gimple_operand_gsi (gsi, unshare_expr (cond),
-				       true, NULL, true, GSI_SAME_STMT);
-
       /* Add the condition COND to the e->aux field.  In case the edge
 	 destination is a PHI node, this condition will be added to
 	 the block predicate to construct a complete condition.  */
       e->aux = cond;
 
-      tmp = build2 (TRUTH_AND_EXPR, boolean_type_node,
-		    unshare_expr (prev_cond), cond);
-      tmp_stmt = ifc_temp_var (boolean_type_node, tmp);
-      gsi_insert_before (gsi, tmp_stmt, GSI_SAME_STMT);
-      new_cond = gimple_assign_lhs (tmp_stmt);
+      new_cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+			      unshare_expr (prev_cond), cond);
     }
 
   add_to_predicate_list (e->dest, new_cond);
@@ -206,84 +192,6 @@ bb_with_exit_edge_p (struct loop *loop, basic_block bb)
   return false;
 }
 
-/* STMT is a GIMPLE_COND.  Update two destination's predicate list.
-   Otherwise update the exit condition of LOOP appropriately.  GSI
-   points to the statement STMT.  */
-
-static void
-tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
-			   gimple_stmt_iterator *gsi)
-{
-  tree c2;
-  edge true_edge, false_edge;
-  location_t loc = gimple_location (stmt);
-  tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
-			    gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
-
-  extract_true_false_edges_from_block (gimple_bb (stmt),
- 				       &true_edge, &false_edge);
-
-  /* Add new condition into destination's predicate list.  */
-
-  /* If C is true, then TRUE_EDGE is taken.  */
-  add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
-
-  /* If C is false, then FALSE_EDGE is taken.  */
-  c2 = invert_truthvalue_loc (loc, unshare_expr (c));
-  add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
-}
-
-/* If-convert stmt T which is part of LOOP.
-
-   For conditional expressions, add a condition in the destination
-   basic block's predicate list.  GSI points to the statement T.  */
-
-static tree
-tree_if_convert_stmt (struct loop *loop, gimple t, tree cond,
-		      gimple_stmt_iterator *gsi)
-{
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      fprintf (dump_file, "------if-convert stmt\n");
-      print_gimple_stmt (dump_file, t, 0, TDF_SLIM);
-      print_generic_stmt (dump_file, cond, TDF_SLIM);
-    }
-
-  switch (gimple_code (t))
-    {
-      /* Labels are harmless here.  */
-    case GIMPLE_LABEL:
-      break;
-
-    case GIMPLE_DEBUG:
-      /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
-      if (gimple_debug_bind_p (gsi_stmt (*gsi)))
-	{
-	  gimple_debug_bind_reset_value (gsi_stmt (*gsi));
-	  update_stmt (gsi_stmt (*gsi));
-	}
-      break;
-
-    case GIMPLE_ASSIGN:
-      /* This GIMPLE_ASSIGN 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 the validity of the program.  */
-      break;
-
-    case GIMPLE_COND:
-      tree_if_convert_cond_stmt (loop, t, cond, gsi);
-      cond = NULL_TREE;
-      break;
-
-    default:
-      gcc_unreachable ();
-    }
-
-  return cond;
-}
-
 /* Return true when PHI is if-convertible.  PHI is part of loop LOOP
    and it belongs to basic block BB.
 
@@ -560,6 +468,126 @@ get_loop_body_in_if_conv_order (const struct loop *loop)
   return blocks;
 }
 
+/* Returns true when the analysis of the predicates for all the basic
+   blocks in LOOP succeeded.
+
+   predicate_bbs first clears the ->aux fields of the edges and basic
+   blocks.  These fields are then initialized with the tree
+   expressions representing the predicates under which a basic block
+   is executed in the LOOP.  As the loop->header is executed at each
+   iteration, it has the "true" predicate.  Other statements executed
+   under a condition are predicated with that condition, for example
+
+   | if (x)
+   |   S1;
+   | else
+   |   S2;
+
+   S1 will be predicated with "x", and S2 will be predicated with
+   "!x".  */
+
+static bool
+predicate_bbs (loop_p loop)
+{
+  unsigned int i;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      edge e;
+      edge_iterator ei;
+      basic_block bb = ifc_bbs [i];
+      gimple_stmt_iterator itr = gsi_start_phis (bb);
+
+      if (!gsi_end_p (itr))
+	FOR_EACH_EDGE (e, ei, bb->preds)
+	  e->aux = NULL;
+
+      bb->aux = NULL;
+    }
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = ifc_bbs [i];
+      tree cond = (tree) bb->aux;
+      gimple_stmt_iterator itr;
+
+      for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+	{
+	  gimple stmt = gsi_stmt (itr);
+
+	  switch (gimple_code (stmt))
+	    {
+	    case GIMPLE_LABEL:
+	    case GIMPLE_ASSIGN:
+	    case GIMPLE_CALL:
+	      break;
+
+	    case GIMPLE_DEBUG:
+	      /* ??? Should there be conditional GIMPLE_DEBUG_BINDs?  */
+	      if (gimple_debug_bind_p (gsi_stmt (itr)))
+		{
+		  gimple_debug_bind_reset_value (gsi_stmt (itr));
+		  update_stmt (gsi_stmt (itr));
+		}
+	      break;
+
+	    case GIMPLE_COND:
+	      {
+		tree c2;
+		edge true_edge, false_edge;
+		location_t loc = gimple_location (stmt);
+		tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
+					  boolean_type_node,
+					  gimple_cond_lhs (stmt),
+					  gimple_cond_rhs (stmt));
+
+		extract_true_false_edges_from_block (gimple_bb (stmt),
+						     &true_edge, &false_edge);
+
+		/* Add new condition into destination's predicate list.  */
+
+		/* If C is true, then TRUE_EDGE is taken.  */
+		add_to_dst_predicate_list (loop, true_edge, cond, c);
+
+		/* If C is false, then FALSE_EDGE is taken.  */
+		c2 = invert_truthvalue_loc (loc, unshare_expr (c));
+		add_to_dst_predicate_list (loop, false_edge, cond, c2);
+
+		cond = NULL_TREE;
+		break;
+	      }
+
+	    case GIMPLE_SWITCH:
+	      /* Not handled yet in if-conversion.  */
+	      return false;
+
+	    default:
+	      gcc_unreachable ();
+	    }
+	}
+
+      /* If current bb has only one successor, then consider it as an
+	 unconditional goto.  */
+      if (single_succ_p (bb))
+	{
+	  basic_block bb_n = single_succ (bb);
+
+	  /* The successor bb inherits the predicate of its
+	     predecessor.  If there is no predicate in the predecessor
+	     bb, then consider the successor bb as always executed.  */
+	  if (cond == NULL_TREE)
+	    cond = boolean_true_node;
+
+	  add_to_predicate_list (bb_n, cond);
+	}
+    }
+
+  /* The loop header is always executed.  */
+  loop->header->aux = boolean_true_node;
+
+  return true;
+}
+
 /* Return true when LOOP is if-convertible.
    LOOP is if-convertible if:
    - it is innermost,
@@ -571,8 +599,6 @@ get_loop_body_in_if_conv_order (const struct loop *loop)
 static bool
 if_convertible_loop_p (struct loop *loop)
 {
-  basic_block bb;
-  gimple_stmt_iterator itr;
   unsigned int i;
   edge e;
   edge_iterator ei;
@@ -639,27 +665,30 @@ if_convertible_loop_p (struct loop *loop)
 
   for (i = 0; i < loop->num_nodes; i++)
     {
-      bb = ifc_bbs[i];
+      basic_block bb = ifc_bbs[i];
 
       if (!if_convertible_bb_p (loop, bb, exit_bb))
 	return false;
 
+      if (bb_with_exit_edge_p (loop, bb))
+	exit_bb = bb;
+    }
+
+  if (!predicate_bbs (loop))
+    return false;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      basic_block bb = ifc_bbs[i];
+      gimple_stmt_iterator itr;
+
       for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
 	if (!if_convertible_stmt_p (loop, bb, gsi_stmt (itr)))
 	  return false;
 
-      itr = gsi_start_phis (bb);
-
-      if (!gsi_end_p (itr))
-	FOR_EACH_EDGE (e, ei, bb->preds)
-	  e->aux = NULL;
-
-      for (; !gsi_end_p (itr); gsi_next (&itr))
+      for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
 	if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 	  return false;
-
-      if (bb_with_exit_edge_p (loop, bb))
-	exit_bb = bb;
     }
 
   if (dump_file)
@@ -1030,65 +1059,23 @@ combine_blocks (struct loop *loop)
 static void
 tree_if_conversion (struct loop *loop)
 {
-  gimple_stmt_iterator itr;
-  unsigned int i;
-
   ifc_bbs = NULL;
 
-  /* If-conversion is not appropriate for all loops.  First, check if
-     the loop is if-convertible.  */
   if (!if_convertible_loop_p (loop))
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "-------------------------\n");
-      if (ifc_bbs)
-	{
-	  free (ifc_bbs);
-	  ifc_bbs = NULL;
-	}
-      return;
-    }
-
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      basic_block bb = ifc_bbs [i];
-      tree cond = (tree) bb->aux;
-
-      /* Predicate basic block(s) with the condition expressions
-	 leading to their execution.  */
-      for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
-	{
-	  gimple t = gsi_stmt (itr);
-	  cond = tree_if_convert_stmt (loop, t, cond, &itr);
-	  if (!gsi_end_p (itr))
-	    gsi_next (&itr);
-	}
-
-      /* If current bb has only one successor, then consider it as an
-	 unconditional goto.  */
-      if (single_succ_p (bb))
-	{
-	  basic_block bb_n = single_succ (bb);
-
-	  /* The successor bb inherits the predicate of its
-	     predecessor.  If there is no predicate in the predecessor
-	     bb, then consider the successor bb as always executed.  */
-	  if (cond == NULL_TREE)
-	    cond = boolean_true_node;
+    goto cleanup;
 
-	  add_to_predicate_list (bb_n, cond);
-	}
-    }
-
-  /* Now, all statements are if-converted and basic blocks are
-     annotated appropriately.  Combine all the basic blocks into one
-     huge basic block.  */
+  /* Now all statements are if-convertible.  Combine all the basic
+     blocks into one huge basic block doing the if-conversion
+     on-the-fly.  */
   combine_blocks (loop);
 
-  /* clean up */
+ cleanup:
   clean_predicate_lists (loop);
-  free (ifc_bbs);
-  ifc_bbs = NULL;
+  if (ifc_bbs)
+    {
+      free (ifc_bbs);
+      ifc_bbs = NULL;
+    }
 }
 
 /* Tree if-conversion pass management.  */