CbC/CbC_gcc: gcc/tree-if-conv.c comparison

comparison gcc/tree-if-conv.c @ 63:b7f97abdc517 gcc-4.6-20100522

update gcc from gcc-4.5.0 to gcc-4.6

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Mon, 24 May 2010 12:47:05 +0900
parents	77e2b8dfacca
children	f6334be47118

comparison

equal deleted inserted replaced

-:3c8a44c06a95
+:b7f97abdc517
 /* If-conversion for vectorizer.
-Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
 Free Software Foundation, Inc.
 Contributed by Devang Patel <dpatel@apple.com>
 This file is part of GCC.
 You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
-/* This pass implements tree level if-conversion transformation of loops.
+/* This pass implements a tree level if-conversion of loops.  Its
-Initial goal is to help vectorizer vectorize loops with conditions.
+initial goal is to help the vectorizer to vectorize loops with
+conditions.
 A short description of if-conversion:
 o Decide if a loop is if-convertible or not.
 o Walk all loop basic blocks in breadth first order (BFS order).
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
 #include "flags.h"
 #include "timevar.h"
-#include "varray.h"
-#include "rtl.h"
 #include "basic-block.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.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 unsigned int main_tree_if_conversion (void);
-static tree tree_if_convert_stmt (struct loop *loop, gimple, tree,
-				  gimple_stmt_iterator *);
-static void tree_if_convert_cond_stmt (struct loop *, gimple, tree,
-				       gimple_stmt_iterator *);
-static bool if_convertible_phi_p (struct loop *, basic_block, gimple);
-static bool if_convertible_gimple_assign_stmt_p (struct loop *, basic_block,
-						 gimple);
-static bool if_convertible_stmt_p (struct loop *, basic_block, gimple);
-static bool if_convertible_bb_p (struct loop *, basic_block, basic_block);
-static bool if_convertible_loop_p (struct loop *, bool);
-static void add_to_predicate_list (basic_block, tree);
-static tree add_to_dst_predicate_list (struct loop * loop, edge,
-				       tree, tree,
-				       gimple_stmt_iterator *);
-static void clean_predicate_lists (struct loop *loop);
-static basic_block find_phi_replacement_condition (struct loop *loop,
-						   basic_block, tree *,
-						   gimple_stmt_iterator *);
-static void replace_phi_with_cond_gimple_assign_stmt (gimple, tree,
-						      basic_block,
-						      gimple_stmt_iterator *);
-static void process_phi_nodes (struct loop *);
-static void combine_blocks (struct loop *);
-static gimple 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 (struct loop *, basic_block);
 /* List of basic blocks in if-conversion-suitable order.  */
 static basic_block *ifc_bbs;
-/* Main entry point.
+/* Create a new temp variable of type TYPE.  Add GIMPLE_ASSIGN to assign EXP
-Apply if-conversion to the LOOP. Return true if successful otherwise return
+to the new variable.  */
-false. If false is returned then loop remains unchanged.
-FOR_VECTORIZER is a boolean flag. It indicates whether if-conversion is used
+static gimple
-for vectorizer or not. If it is used for vectorizer, additional checks are
+ifc_temp_var (tree type, tree exp)
-used. (Vectorization checks are not yet implemented).  */
+{
+const char *name = "_ifc_";
+tree var, new_name;
+gimple stmt;
+/* Create new temporary variable.  */
+var = create_tmp_var (type, name);
+add_referenced_var (var);
+/* Build new statement to assign EXP to new variable.  */
+stmt = gimple_build_assign (var, exp);
+/* Get SSA name for the new variable and set make new statement
+its definition statement.  */
+new_name = make_ssa_name (var, stmt);
+gimple_assign_set_lhs (stmt, new_name);
+SSA_NAME_DEF_STMT (new_name) = stmt;
+update_stmt (stmt);
+return stmt;
+}
+/* Add condition NEW_COND to the predicate list of basic block BB.  */
+static void
+add_to_predicate_list (basic_block bb, tree new_cond)
+{
+tree cond = (tree) bb->aux;
+if (cond)
+cond = fold_build2_loc (EXPR_LOCATION (cond),
+			    TRUTH_OR_EXPR, boolean_type_node,
+			    unshare_expr (cond), new_cond);
+else
+cond = 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.  */
+static tree
+add_to_dst_predicate_list (struct loop *loop, edge e,
+			   tree prev_cond, tree cond,
+			   gimple_stmt_iterator *gsi)
+{
+tree new_cond = NULL_TREE;
+if (!flow_bb_inside_loop_p (loop, e->dest))
+return NULL_TREE;
+if (prev_cond == boolean_true_node || !prev_cond)
+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);
+}
+add_to_predicate_list (e->dest, new_cond);
+return new_cond;
+}
+/* Return true if one of the successor edges of BB exits LOOP.  */
 static bool
-tree_if_conversion (struct loop *loop, bool for_vectorizer)
+bb_with_exit_edge_p (struct loop *loop, basic_block bb)
 {
-basic_block bb;
+edge e;
-gimple_stmt_iterator itr;
+edge_iterator ei;
-unsigned int i;
+FOR_EACH_EDGE (e, ei, bb->succs)
-ifc_bbs = NULL;
+if (loop_exit_edge_p (loop, e))
+return true;
-/* if-conversion is not appropriate for all loops. First, check if loop  is
-if-convertible or not.  */
+return false;
-if (!if_convertible_loop_p (loop, for_vectorizer))
+}
-{
-if (dump_file && (dump_flags & TDF_DETAILS))
+/* STMT is a GIMPLE_COND.  Update two destination's predicate list.
-	fprintf (dump_file,"-------------------------\n");
+Remove COND_EXPR, if it is not the exit condition of LOOP.
-if (ifc_bbs)
+Otherwise update the exit condition of LOOP appropriately.  GSI
-	{
+points to the statement STMT.  */
-	  free (ifc_bbs);
-	  ifc_bbs = NULL;
+static void
-	}
+tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
-free_dominance_info (CDI_POST_DOMINATORS);
+			   gimple_stmt_iterator *gsi)
-return false;
+{
-}
+tree c2;
+edge true_edge, false_edge;
-/* Do actual work now.  */
+location_t loc = gimple_location (stmt);
-for (i = 0; i < loop->num_nodes; i++)
+tree c = fold_build2_loc (loc, gimple_cond_code (stmt), boolean_type_node,
-{
+			    gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
-tree cond;
+extract_true_false_edges_from_block (gimple_bb (stmt),
-bb = ifc_bbs [i];
+				       &true_edge, &false_edge);
-/* Update condition using predicate list.  */
+/* Add new condition into destination's predicate list.  */
-cond = (tree) bb->aux;
+/* If C is true, then TRUE_EDGE is taken.  */
-/* Process all statements in this basic block.
+add_to_dst_predicate_list (loop, true_edge, cond, c, gsi);
-	 Remove conditional expression, if any, and annotate
-	 destination basic block(s) appropriately.  */
+/* If C is false, then FALSE_EDGE is taken.  */
-for (itr = gsi_start_bb (bb); !gsi_end_p (itr); /* empty */)
+c2 = invert_truthvalue_loc (loc, unshare_expr (c));
-	{
+add_to_dst_predicate_list (loop, false_edge, cond, c2, gsi);
-	  gimple t = gsi_stmt (itr);
-	  cond = tree_if_convert_stmt (loop, t, cond, &itr);
+/* Now this conditional statement is redundant.  Remove it.  But, do
-	  if (!gsi_end_p (itr))
+not remove the exit condition!  Update the exit condition using
-	    gsi_next (&itr);
+the new condition.  */
-	}
+if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
+{
-/* If current bb has only one successor, then consider it as an
+gsi_remove (gsi, true);
-	 unconditional goto.  */
+cond = NULL_TREE;
-if (single_succ_p (bb))
+}
-	{
+}
-	  basic_block bb_n = single_succ (bb);
+/* If-convert stmt T which is part of LOOP.
-	  /* Successor bb inherits predicate of its predecessor. If there
-	     is no predicate in predecessor bb, then consider successor bb
+If T is a GIMPLE_ASSIGN then it is converted into a conditional
-	     as always executed.  */
+modify expression using COND.  For conditional expressions, add
-	  if (cond == NULL_TREE)
+a condition in the destination basic block's predicate list and
-	    cond = boolean_true_node;
+remove the conditional expression itself.  GSI points to the
+statement T.  */
-	  add_to_predicate_list (bb_n, cond);
-	}
-}
-/* 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;
-return true;
-}
-/* if-convert stmt T which is part of LOOP.
-If T is a GIMPLE_ASSIGN then 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, gimple t, tree cond,
+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");
 	  update_stmt (gsi_stmt (*gsi));
 	}
 break;
 case GIMPLE_ASSIGN:
-/* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate
+/* This GIMPLE_ASSIGN is killing previous value of LHS.  Appropriate
-	 value will be selected by PHI node based on condition. It is possible
+	 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
+	 value and now it will use this new value.  This is OK because it does
-	 not change validity the program.  */
+	 not change the validity of the program.  */
 break;
 case GIMPLE_COND:
 /* Update destination blocks' predicate list and remove this
 	 condition expression.  */
 break;
 default:
 gcc_unreachable ();
 }
 return cond;
 }
-/* STMT is a GIMPLE_COND. Update two destination's predicate list.
+/* Return true when PHI is if-convertible.  PHI is part of loop LOOP
-Remove COND_EXPR, if it is not the loop exit condition. Otherwise
-update loop exit condition appropriately.  GSI is the iterator
-used to traverse statement list. STMT is part of loop LOOP.  */
-static void
-tree_if_convert_cond_stmt (struct loop *loop, gimple stmt, tree cond,
-			   gimple_stmt_iterator *gsi)
-{
-tree c, c2;
-edge true_edge, false_edge;
-location_t loc = gimple_location (stmt);
-gcc_assert (gimple_code (stmt) == GIMPLE_COND);
-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);
-/* Now this conditional statement is redundant. Remove it.
-But, do not remove exit condition! Update exit condition
-using new condition.  */
-if (!bb_with_exit_edge_p (loop, gimple_bb (stmt)))
-{
-gsi_remove (gsi, true);
-cond = NULL_TREE;
-}
-return;
-}
-/* Return true, iff PHI is if-convertible. PHI is part of loop LOOP
 and it belongs to basic block BB.
-PHI is not if-convertible
-- if it has more than 2 arguments.
+PHI is not if-convertible if:
-- Virtual PHI is immediately used in another PHI node.
+- it has more than 2 arguments,
-- Virtual PHI on BB other than header.  */
+- virtual PHI is immediately used in another PHI node,
+- virtual PHI on BB other than header.  */
 static bool
 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
 {
 if (dump_file && (dump_flags & TDF_DETAILS))
 }
 return true;
 }
-/* Return true, if STMT is if-convertible.
+/* Return true when STMT is if-convertible.
 GIMPLE_ASSIGN statement is not if-convertible if,
-- It is not movable.
+- it is not movable,
-- It could trap.
+- it could trap,
 - LHS is not var decl.
-GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
+GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP.  */
 static bool
 if_convertible_gimple_assign_stmt_p (struct loop *loop, basic_block bb,
 				     gimple stmt)
 {
-tree lhs;
+tree lhs = gimple_assign_lhs (stmt);
-if (!is_gimple_assign (stmt))
-return false;
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 fprintf (dump_file, "-------------------------\n");
 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
 }
-lhs = gimple_assign_lhs (stmt);
 /* Some of these constrains might be too conservative.  */
 if (stmt_ends_bb_p (stmt)
 || gimple_has_volatile_ops (stmt)
 || (TREE_CODE (lhs) == SSA_NAME
 }
 return true;
 }
-/* Return true, iff STMT is if-convertible.
+/* Return true when STMT is if-convertible.
-Statement is if-convertible if,
-- It is if-convertible GIMPLE_ASSGIN
+A statement is if-convertible if:
-- It is GIMPLE_LABEL or GIMPLE_COND.
+- it is an if-convertible GIMPLE_ASSGIN,
-STMT is inside block BB, which is inside loop LOOP.  */
+- it is a GIMPLE_LABEL or a GIMPLE_COND.
+STMT is inside BB, which is inside loop LOOP.  */
 static bool
 if_convertible_stmt_p (struct loop *loop, basic_block bb, gimple stmt)
 {
 switch (gimple_code (stmt))
 {
 case GIMPLE_LABEL:
-break;
 case GIMPLE_DEBUG:
-break;
+case GIMPLE_COND:
+return true;
 case GIMPLE_ASSIGN:
-if (!if_convertible_gimple_assign_stmt_p (loop, bb, stmt))
+return if_convertible_gimple_assign_stmt_p (loop, bb, stmt);
-	return false;
-break;
-case GIMPLE_COND:
-break;
 default:
 /* Don't know what to do with 'em so don't do anything.  */
 if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 }
 return true;
 }
-/* Return true, iff BB is if-convertible.
+/* Return true when BB is if-convertible.  This routine does not check
-Note: This routine does _not_ check basic block statements and phis.
+basic block's statements and phis.
-Basic block is not if-convertible if,
-- Basic block is non-empty and it is after exit block (in BFS order).
+A basic block is not if-convertible if:
-- Basic block is after exit block but before latch.
+- it is non-empty and it is after the exit block (in BFS order),
-- Basic block edge(s) is not normal.
+- it is after the exit block but before the latch,
-EXIT_BB_SEEN is true if basic block with exit edge is already seen.
+- its edges are not normal.
-BB is inside loop LOOP.  */
+EXIT_BB is the basic block containing the exit of the LOOP.  BB is
+inside LOOP.  */
 static bool
 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
 {
 edge e;
 FOR_EACH_EDGE (e, ei, bb->succs)
 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");
+	  fprintf (dump_file, "Difficult to handle edges\n");
 	return false;
 }
 return true;
 }
-/* Return true, iff LOOP is if-convertible.
+/* Return true when all predecessor blocks of BB are visited.  The
-LOOP is if-convertible if,
+VISITED bitmap keeps track of the visited blocks.  */
-- 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 convertible. 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_convertible_loop_p (struct loop *loop, bool for_vectorizer ATTRIBUTE_UNUSED)
+pred_blocks_visited_p (basic_block bb, bitmap *visited)
+{
+edge e;
+edge_iterator ei;
+FOR_EACH_EDGE (e, ei, bb->preds)
+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, breadth first sort (BFS) order
+with an additional constraint: select a block only if all its
+predecessors 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;
+gcc_assert (loop->num_nodes);
+gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+blocks = XCNEWVEC (basic_block, loop->num_nodes);
+visited = BITMAP_ALLOC (NULL);
+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_FREE (visited);
+return blocks;
+}
+/* Return true when LOOP is if-convertible.
+LOOP is if-convertible 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 convertible.  */
+static bool
+if_convertible_loop_p (struct loop *loop)
 {
 basic_block bb;
 gimple_stmt_iterator itr;
 unsigned int i;
 edge e;
 bb = ifc_bbs[i];
 if (!if_convertible_bb_p (loop, bb, exit_bb))
 	return false;
-/* Check statements.  */
 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;
-/* ??? Check data dependency for vectorizer.  */
-/* What about phi nodes ? */
 itr = gsi_start_phis (bb);
-/* Clear aux field of incoming edges to a bb with a phi node.  */
 if (!gsi_end_p (itr))
 	FOR_EACH_EDGE (e, ei, bb->preds)
 	  e->aux = NULL;
-/* Check statements.  */
 for (; !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;
 }
-/* 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.  */
+/* During if-conversion, the bb->aux field is used to hold a predicate
+list.  This function cleans for all the basic blocks in the given
-static void
+LOOP their predicate list.  It also cleans up the e->aux field of
-add_to_predicate_list (basic_block bb, tree new_cond)
+all the successor edges: e->aux is used to hold the true and false
-{
+conditions for conditional expressions.  */
-tree cond = (tree) bb->aux;
-if (cond)
-cond = fold_build2_loc (EXPR_LOCATION (cond),
-			TRUTH_OR_EXPR, boolean_type_node,
-			unshare_expr (cond), new_cond);
-else
-cond = new_cond;
-bb->aux = cond;
-}
-/* Add condition COND into BB's predicate list.  PREV_COND is
-existing condition.  */
-static tree
-add_to_dst_predicate_list (struct loop * loop, edge e,
-			   tree prev_cond, tree cond,
-			   gimple_stmt_iterator *gsi)
-{
-tree new_cond = NULL_TREE;
-if (!flow_bb_inside_loop_p (loop, e->dest))
-return NULL_TREE;
-if (prev_cond == boolean_true_node || !prev_cond)
-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 to aux field of the edge.  In case edge
-	 destination is a PHI node, this condition will be ANDed with
-	 block predicate to construct complete condition.  */
-e->aux = cond;
-/* new_cond == prev_cond AND 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);
-}
-add_to_predicate_list (e->dest, new_cond);
-return new_cond;
-}
-/* During if-conversion aux field from basic block structure is used to hold
-predicate list. Clean each basic block's predicate list for the given LOOP.
-Also clean aux field of successor edges, used to hold true and false
-condition from conditional expression.  */
 static void
 clean_predicate_lists (struct loop *loop)
 {
 basic_block *bb;
 	e->aux = NULL;
 }
 free (bb);
 }
-/* Basic block BB has two predecessors. Using predecessor's aux field, set
+/* Basic block BB has two predecessors.  Using predecessor's bb->aux
-appropriate condition COND for the PHI node replacement. Return true block
+field, set appropriate condition COND for the PHI node replacement.
-whose phi arguments are selected when cond is true.  */
+Return true block whose phi arguments are selected when cond is
+true.  LOOP is the loop containing the if-converted region, GSI is
+the place to insert the code for the if-conversion.  */
 static basic_block
 find_phi_replacement_condition (struct loop *loop,
 				basic_block bb, tree *cond,
 gimple_stmt_iterator *gsi)
 || dominated_by_p (CDI_DOMINATORS,
 			 second_edge->src, first_edge->src))
 {
 *cond = (tree) (second_edge->src)->aux;
-/* If there is a condition on an incoming edge,
+/* If there is a condition on an incoming edge, add it to the
-	 AND it with the incoming bb predicate.  */
+	 incoming bb predicate.  */
 if (second_edge->aux)
 	*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 			*cond, (tree) second_edge->aux);
 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
-	/* We can be smart here and choose inverted
-	   condition without switching bbs.  */
 	*cond = invert_truthvalue (*cond);
 else
 	/* Select non loop header bb.  */
 	first_edge = second_edge;
 }
 else
 {
-/* FIRST_BB is not loop header */
 *cond = (tree) (first_edge->src)->aux;
-/* If there is a condition on an incoming edge,
+/* If there is a condition on an incoming edge, add it to the
-	 AND it with the incoming bb predicate.  */
+	 incoming bb predicate.  */
 if (first_edge->aux)
 	*cond = build2 (TRUTH_AND_EXPR, boolean_type_node,
 			*cond, (tree) first_edge->aux);
 }
-/* Create temp. for the condition. Vectorizer prefers to have gimple
+/* Gimplify the condition: the vectorizer prefers to have gimple
-value as condition. Various targets use different means to communicate
+values as conditions.  Various targets use different means to
-condition in vector compare operation. Using gimple value allows
+communicate conditions in vector compare operations.  Using a
-compiler to emit vector compare and select RTL without exposing
+gimple value allows the compiler to emit vector compare and
-compare's result.  */
+select RTL without exposing compare's result.  */
 *cond = force_gimple_operand_gsi (gsi, unshare_expr (*cond),
 				    false, NULL_TREE,
 				    true, GSI_SAME_STMT);
 if (!is_gimple_reg (*cond) && !is_gimple_condexpr (*cond))
 {
 gcc_assert (*cond);
 return first_edge->src;
 }
+/* Replace PHI node with conditional modify expr using COND.  This
-/* Replace PHI node with conditional modify expr using COND.
+routine does not handle PHI nodes with more than two arguments.
-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.
-When COND is true, phi arg from TRUE_BB is selected.
+The generated code is inserted at GSI that points to the top of
-*/
+basic block's statement list.  When COND is true, phi arg from
+TRUE_BB is selected.  */
 static void
 replace_phi_with_cond_gimple_assign_stmt (gimple phi, tree cond,
 					  basic_block true_bb,
 	  gimple_stmt_iterator *gsi)
 gimple new_stmt;
 basic_block bb;
 tree rhs;
 tree arg_0, arg_1;
-gcc_assert (gimple_code (phi) == GIMPLE_PHI);
+gcc_assert (gimple_code (phi) == GIMPLE_PHI
+	      && gimple_phi_num_args (phi) == 2);
-/* If this is not filtered earlier, then now it is too late.  */
-gcc_assert (gimple_phi_num_args (phi) == 2);
-/* Find basic block and initialize iterator.  */
 bb = gimple_bb (phi);
 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
 if (EDGE_PRED (bb, 1)->src == true_bb)
 {
 /* Build new RHS using selected condition and arguments.  */
 rhs = build3 (COND_EXPR, TREE_TYPE (PHI_RESULT (phi)),
 	        unshare_expr (cond), unshare_expr (arg_0),
 	        unshare_expr (arg_1));
-/* Create new GIMPLE_ASSIGN statement using RHS.  */
 new_stmt = gimple_build_assign (unshare_expr (PHI_RESULT (phi)), rhs);
-/* Make new statement definition of the original phi result.  */
 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
-/* Insert using iterator.  */
 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
 update_stmt (new_stmt);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 fprintf (dump_file, "new phi replacement stmt\n");
 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
 }
 }
-/* Process phi nodes for the given  LOOP.  Replace phi nodes with cond
+/* Process phi nodes for the given LOOP.  Replace phi nodes with
-modify expr.  */
+conditional modify expressions.  */
 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++)
 {
 gimple phi;
 tree cond = NULL_TREE;
 gimple_stmt_iterator gsi, phi_gsi;
 	continue;
 phi_gsi = gsi_start_phis (bb);
 gsi = gsi_after_labels (bb);
-/* BB has two predecessors. Using predecessor's aux field, set
+/* BB has two predecessors.  Using predecessor's aux field, set
 	 appropriate condition for the PHI node replacement.  */
 if (!gsi_end_p (phi_gsi))
 	true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
 while (!gsi_end_p (phi_gsi))
 	  release_phi_node (phi);
 	  gsi_next (&phi_gsi);
 	}
 set_phi_nodes (bb, NULL);
 }
-return;
+}
-}
+/* Combine all the basic blocks from LOOP into one or two super basic
-/* Combine all basic block from the given LOOP into one or two super
+blocks.  Replace PHI nodes with conditional modify expressions.  */
-basic block.  Replace PHI nodes with conditional modify expression.  */
 static void
 combine_blocks (struct loop *loop)
 {
 basic_block bb, exit_bb, merge_target_bb;
 edge_iterator ei;
 /* Process phi nodes to prepare blocks for merge.  */
 process_phi_nodes (loop);
-/* Merge basic blocks.  First remove all the edges in the loop, except
+/* Merge basic blocks: first remove all the edges in the loop,
-for those from the exit block.  */
+except for those from the exit block.  */
 exit_bb = NULL;
 for (i = 0; i < orig_loop_num_nodes; i++)
 {
 bb = ifc_bbs[i];
 if (bb_with_exit_edge_p (loop, bb))
 if (exit_bb != NULL)
 {
 if (exit_bb != loop->header)
 	{
-	  /* Connect this node with loop header.  */
+	  /* Connect this node to loop header.  */
 	  make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
 	  set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
 	}
 /* Redirect non-exit edges to loop->latch.  */
 	}
 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
 }
 else
 {
-/* If the loop does not have exit then reconnect header and latch.  */
+/* If the loop does not have an exit, reconnect header and latch.  */
 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
 }
 merge_target_bb = loop->header;
 set_bb_seq (bb, NULL);
 delete_basic_block (bb);
 }
-/* Now if possible, merge loop header and block with exit edge.
+/* If possible, merge loop header to the block with the exit edge.
-This reduces number of basic blocks to 2. Auto vectorizer addresses
+This reduces the number of basic blocks to two, to please the
-loops with two nodes only.  FIXME: Use cleanup_tree_cfg().  */
+vectorizer that handles only loops with two nodes.
+FIXME: Call cleanup_tree_cfg.  */
 if (exit_bb
 && exit_bb != loop->header
 && can_merge_blocks_p (loop->header, exit_bb))
 merge_blocks (loop->header, exit_bb);
 }
-/* Make a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
+/* Main entry point: return true when LOOP is if-converted, otherwise
-to the new variable.  */
+the loop remains unchanged.  */
-static gimple
-ifc_temp_var (tree type, tree exp)
-{
-const char *name = "_ifc_";
-tree var, new_name;
-gimple stmt;
-/* Create new temporary variable.  */
-var = create_tmp_var (type, name);
-add_referenced_var (var);
-/* Build new statement to assign EXP to new variable.  */
-stmt = gimple_build_assign (var, exp);
-/* Get SSA name for the new variable and set make new statement
-its definition statement.  */
-new_name = make_ssa_name (var, stmt);
-gimple_assign_set_lhs (stmt, new_name);
-SSA_NAME_DEF_STMT (new_name) = stmt;
-update_stmt (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)
+tree_if_conversion (struct loop *loop)
 {
-edge e;
+gimple_stmt_iterator itr;
-edge_iterator ei;
+unsigned int i;
-FOR_EACH_EDGE (e, ei, bb->preds)
-if (!bitmap_bit_p (*visited, e->src->index))
+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;
+	}
+free_dominance_info (CDI_POST_DOMINATORS);
 return false;
+}
+for (i = 0; i < loop->num_nodes; i++)
+{
+basic_block bb = ifc_bbs [i];
+tree cond = (tree) bb->aux;
+/* Process all the statements in this basic block.
+	 Remove conditional expression, if any, and annotate
+	 destination basic block(s) appropriately.  */
+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;
+	  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.  */
+combine_blocks (loop);
+/* clean up */
+clean_predicate_lists (loop);
+free (ifc_bbs);
+ifc_bbs = NULL;
 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;
-gcc_assert (loop->num_nodes);
-gcc_assert (loop->latch != EXIT_BLOCK_PTR);
-blocks = XCNEWVEC (basic_block, loop->num_nodes);
-visited = BITMAP_ALLOC (NULL);
-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_FREE (visited);
-return blocks;
-}
-/* Return true if one of the basic block BB edge is exit of LOOP.  */
-static bool
-bb_with_exit_edge_p (struct loop *loop, basic_block bb)
-{
-edge e;
-edge_iterator ei;
-bool exit_edge_found = false;
-FOR_EACH_EDGE (e, ei, bb->succs)
-if (loop_exit_edge_p (loop, e))
-{
-	exit_edge_found = true;
-	break;
-}
-return exit_edge_found;
 }
 /* Tree if-conversion pass management.  */
 static unsigned int
 if (number_of_loops () <= 1)
 return 0;
 FOR_EACH_LOOP (li, loop, 0)
-{
+tree_if_conversion (loop);
-tree_if_conversion (loop, true);
-}
 return 0;
 }
 static bool
 gate_tree_if_conversion (void)
 TV_NONE,				/* tv_id */
 PROP_cfg | PROP_ssa,			/* properties_required */
 0,					/* properties_provided */
 0,					/* properties_destroyed */
 0,					/* todo_flags_start */
-TODO_dump_func | TODO_verify_loops | TODO_verify_stmts | TODO_verify_flow
+TODO_dump_func | TODO_verify_stmts | TODO_verify_flow
 /* todo_flags_finish */
 }
 };

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-if-conv.c @ 63:b7f97abdc517 gcc-4.6-20100522