CbC/CbC_gcc: gcc/tree-ssa-loop-im.c comparison

comparison gcc/tree-ssa-loop-im.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
 /* Loop invariant motion.
-Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
+Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
-Foundation, Inc.
+Free Software Foundation, Inc.
 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
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
-#include "rtl.h"
 #include "tm_p.h"
-#include "hard-reg-set.h"
 #include "basic-block.h"
 #include "output.h"
 #include "diagnostic.h"
+#include "gimple-pretty-print.h"
+#include "tree-pretty-print.h"
 #include "tree-flow.h"
 #include "tree-dump.h"
 #include "timevar.h"
 #include "cfgloop.h"
 #include "domwalk.h"
 #include "params.h"
 #include "tree-pass.h"
 #include "flags.h"
-#include "real.h"
 #include "hashtab.h"
 #include "tree-affine.h"
 #include "pointer-set.h"
 #include "tree-ssa-propagate.h"
 /* If we perform unswitching, force the operands of the invariant
 	 condition to be moved out of the loop.  */
 return MOVE_POSSIBLE;
 }
+if (gimple_code (stmt) == GIMPLE_PHI
+&& gimple_phi_num_args (stmt) <= 2
+&& is_gimple_reg (gimple_phi_result (stmt))
+&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
+return MOVE_POSSIBLE;
 if (gimple_get_lhs (stmt) == NULL_TREE)
 return MOVE_IMPOSSIBLE;
 if (gimple_vdef (stmt))
 return MOVE_IMPOSSIBLE;
 {
 tree fndecl;
 unsigned cost = 1;
 /* Always try to create possibilities for unswitching.  */
-if (gimple_code (stmt) == GIMPLE_COND)
+if (gimple_code (stmt) == GIMPLE_COND
+|| gimple_code (stmt) == GIMPLE_PHI)
 return LIM_EXPENSIVE;
 /* Hoisting memory references out should almost surely be a win.  */
 if (gimple_references_memory_p (stmt))
 cost += 20;
 gcc_assert (ref != NULL);
 return ref;
 }
+/* From a controlling predicate in DOM determine the arguments from
+the PHI node PHI that are chosen if the predicate evaluates to
+true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
+they are non-NULL.  Returns true if the arguments can be determined,
+else return false.  */
+static bool
+extract_true_false_args_from_phi (basic_block dom, gimple phi,
+				  tree *true_arg_p, tree *false_arg_p)
+{
+basic_block bb = gimple_bb (phi);
+edge true_edge, false_edge, tem;
+tree arg0 = NULL_TREE, arg1 = NULL_TREE;
+/* We have to verify that one edge into the PHI node is dominated
+by the true edge of the predicate block and the other edge
+dominated by the false edge.  This ensures that the PHI argument
+we are going to take is completely determined by the path we
+take from the predicate block.  */
+extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+tem = EDGE_PRED (bb, 0);
+if (tem == true_edge
+|| tem->src == true_edge->dest
+|| dominated_by_p (CDI_DOMINATORS,
+			 tem->src, true_edge->dest))
+arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+else if (tem == false_edge
+	   || tem->src == false_edge->dest
+	   || dominated_by_p (CDI_DOMINATORS,
+			      tem->src, false_edge->dest))
+arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+else
+return false;
+tem = EDGE_PRED (bb, 1);
+if (tem == true_edge
+|| tem->src == true_edge->dest
+|| dominated_by_p (CDI_DOMINATORS,
+			 tem->src, true_edge->dest))
+arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+else if (tem == false_edge
+	   || tem->src == false_edge->dest
+	   || dominated_by_p (CDI_DOMINATORS,
+			      tem->src, false_edge->dest))
+arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+else
+return false;
+if (!arg0 || !arg1)
+return false;
+if (true_arg_p)
+*true_arg_p = arg0;
+if (false_arg_p)
+*false_arg_p = arg1;
+return true;
+}
 /* Determine the outermost loop to that it is possible to hoist a statement
 STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
 the outermost loop in that the value computed by STMT is invariant.
 If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
 we preserve the fact whether STMT is executed.  It also fills other related
 level = ALWAYS_EXECUTED_IN (bb);
 else
 level = superloop_at_depth (loop, 1);
 lim_data->max_loop = level;
-FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
+if (gimple_code (stmt) == GIMPLE_PHI)
-if (!add_dependency (val, lim_data, loop, true))
+{
-return false;
+use_operand_p use_p;
+unsigned min_cost = UINT_MAX;
+unsigned total_cost = 0;
+struct lim_aux_data *def_data;
+/* We will end up promoting dependencies to be unconditionally
+	 evaluated.  For this reason the PHI cost (and thus the
+	 cost we remove from the loop by doing the invariant motion)
+	 is that of the cheapest PHI argument dependency chain.  */
+FOR_EACH_PHI_ARG (use_p, stmt, iter, SSA_OP_USE)
+	{
+	  val = USE_FROM_PTR (use_p);
+	  if (TREE_CODE (val) != SSA_NAME)
+	    continue;
+	  if (!add_dependency (val, lim_data, loop, false))
+	    return false;
+	  def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
+	  if (def_data)
+	    {
+	      min_cost = MIN (min_cost, def_data->cost);
+	      total_cost += def_data->cost;
+	    }
+	}
+lim_data->cost += min_cost;
+if (gimple_phi_num_args (stmt) > 1)
+	{
+	  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+	  gimple cond;
+	  if (gsi_end_p (gsi_last_bb (dom)))
+	    return false;
+	  cond = gsi_stmt (gsi_last_bb (dom));
+	  if (gimple_code (cond) != GIMPLE_COND)
+	    return false;
+	  /* Verify that this is an extended form of a diamond and
+	     the PHI arguments are completely controlled by the
+	     predicate in DOM.  */
+	  if (!extract_true_false_args_from_phi (dom, stmt, NULL, NULL))
+	    return false;
+	  /* Fold in dependencies and cost of the condition.  */
+	  FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
+	    {
+	      if (!add_dependency (val, lim_data, loop, false))
+		return false;
+	      def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
+	      if (def_data)
+		total_cost += def_data->cost;
+	    }
+	  /* We want to avoid unconditionally executing very expensive
+	     operations.  As costs for our dependencies cannot be
+	     negative just claim we are not invariand for this case.
+	     We also are not sure whether the control-flow inside the
+	     loop will vanish.  */
+	  if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
+	      && !(min_cost != 0
+		   && total_cost / min_cost <= 2))
+	    return false;
+	  /* Assume that the control-flow in the loop will vanish.
+	     ???  We should verify this and not artificially increase
+	     the cost if that is not the case.  */
+	  lim_data->cost += stmt_cost (stmt);
+	}
+return true;
+}
+else
+FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
+if (!add_dependency (val, lim_data, loop, true))
+	return false;
 if (gimple_vuse (stmt))
 {
 mem_ref_p ref = mem_ref_in_stmt (stmt);
 return;
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
 	     bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
+/* Look at PHI nodes, but only if there is at most two.
+???  We could relax this further by post-processing the inserted
+code and transforming adjacent cond-exprs with the same predicate
+to control flow again.  */
+bsi = gsi_start_phis (bb);
+if (!gsi_end_p (bsi)
+&& ((gsi_next (&bsi), gsi_end_p (bsi))
+	  || (gsi_next (&bsi), gsi_end_p (bsi))))
+for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+{
+	stmt = gsi_stmt (bsi);
+	pos = movement_possibility (stmt);
+	if (pos == MOVE_IMPOSSIBLE)
+	  continue;
+	lim_data = init_lim_data (stmt);
+	lim_data->always_executed_in = outermost;
+	if (!determine_max_movement (stmt, false))
+	  {
+	    lim_data->max_loop = NULL;
+	    continue;
+	  }
+	if (dump_file && (dump_flags & TDF_DETAILS))
+	  {
+	    print_gimple_stmt (dump_file, stmt, 2, 0);
+	    fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
+		     loop_depth (lim_data->max_loop),
+		     lim_data->cost);
+	  }
+	if (lim_data->cost >= LIM_EXPENSIVE)
+	  set_profitable_level (stmt);
+}
 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 {
 stmt = gsi_stmt (bsi);
 /* Hoist the statements in basic block BB out of the loops prescribed by
 data stored in LIM_DATA structures associated with each statement.  Callback
 for walk_dominator_tree.  */
 static void
-move_computations_stmt (struct dom_walk_data *dw_data ATTRIBUTE_UNUSED,
+move_computations_stmt (struct dom_walk_data *dw_data,
 			basic_block bb)
 {
 struct loop *level;
 gimple_stmt_iterator bsi;
 gimple stmt;
 unsigned cost = 0;
 struct lim_aux_data *lim_data;
 if (!loop_outer (bb->loop_father))
 return;
+for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
+{
+gimple new_stmt;
+stmt = gsi_stmt (bsi);
+lim_data = get_lim_data (stmt);
+if (lim_data == NULL)
+	{
+	  gsi_next (&bsi);
+	  continue;
+	}
+cost = lim_data->cost;
+level = lim_data->tgt_loop;
+clear_lim_data (stmt);
+if (!level)
+	{
+	  gsi_next (&bsi);
+	  continue;
+	}
+if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Moving PHI node\n");
+	  print_gimple_stmt (dump_file, stmt, 0, 0);
+	  fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
+		   cost, level->num);
+	}
+if (gimple_phi_num_args (stmt) == 1)
+	{
+	  tree arg = PHI_ARG_DEF (stmt, 0);
+	  new_stmt = gimple_build_assign_with_ops (TREE_CODE (arg),
+						   gimple_phi_result (stmt),
+						   arg, NULL_TREE);
+	  SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
+	}
+else
+	{
+	  basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+	  gimple cond = gsi_stmt (gsi_last_bb (dom));
+	  tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
+	  /* Get the PHI arguments corresponding to the true and false
+	     edges of COND.  */
+	  extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
+	  gcc_assert (arg0 && arg1);
+	  t = build2 (gimple_cond_code (cond), boolean_type_node,
+		      gimple_cond_lhs (cond), gimple_cond_rhs (cond));
+	  t = build3 (COND_EXPR, TREE_TYPE (gimple_phi_result (stmt)),
+		      t, arg0, arg1);
+	  new_stmt = gimple_build_assign_with_ops (COND_EXPR,
+						   gimple_phi_result (stmt),
+						   t, NULL_TREE);
+	  SSA_NAME_DEF_STMT (gimple_phi_result (stmt)) = new_stmt;
+	  *((unsigned int *)(dw_data->global_data)) |= TODO_cleanup_cfg;
+	}
+gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
+remove_phi_node (&bsi, false);
+}
 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
 {
 stmt = gsi_stmt (bsi);
 }
 /* Hoist the statements out of the loops prescribed by data stored in
 LIM_DATA structures associated with each statement.*/
-static void
+static unsigned int
 move_computations (void)
 {
 struct dom_walk_data walk_data;
+unsigned int todo = 0;
 memset (&walk_data, 0, sizeof (struct dom_walk_data));
+walk_data.global_data = &todo;
 walk_data.dom_direction = CDI_DOMINATORS;
 walk_data.before_dom_children = move_computations_stmt;
 init_walk_dominator_tree (&walk_data);
 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 fini_walk_dominator_tree (&walk_data);
 gsi_commit_edge_inserts ();
 if (need_ssa_update_p (cfun))
 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
+return todo;
 }
 /* Checks whether the statement defining variable *INDEX can be hoisted
 out of the loop passed in DATA.  Callback for for_each_index.  */
 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 lsm_tmp_name_add ("_");
 name = get_name (TREE_OPERAND (ref, 1));
 if (!name)
 	name = "F";
-lsm_tmp_name_add ("_");
 lsm_tmp_name_add (name);
+break;
 case ARRAY_REF:
 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
 lsm_tmp_name_add ("_I");
 break;
 ref = VEC_index (mem_ref_p, memory_accesses.refs_list, i);
 execute_sm (loop, exits, ref);
 }
 }
-/* Returns true if REF is always accessed in LOOP.  */
+/* Returns true if REF is always accessed in LOOP.  If STORED_P is true
+make sure REF is always stored to in LOOP.  */
 static bool
-ref_always_accessed_p (struct loop *loop, mem_ref_p ref)
+ref_always_accessed_p (struct loop *loop, mem_ref_p ref, bool stored_p)
 {
 VEC (mem_ref_loc_p, heap) *locs = NULL;
 unsigned i;
 mem_ref_loc_p loc;
 bool ret = false;
 struct loop *must_exec;
+tree base;
+base = get_base_address (ref->mem);
+if (INDIRECT_REF_P (base))
+base = TREE_OPERAND (base, 0);
 get_all_locs_in_loop (loop, ref, &locs);
 for (i = 0; VEC_iterate (mem_ref_loc_p, locs, i, loc); i++)
 {
 if (!get_lim_data (loc->stmt))
 	continue;
+/* If we require an always executed store make sure the statement
+stores to the reference.  */
+if (stored_p)
+	{
+	  tree lhs;
+	  if (!gimple_get_lhs (loc->stmt))
+	    continue;
+	  lhs = get_base_address (gimple_get_lhs (loc->stmt));
+	  if (!lhs)
+	    continue;
+	  if (INDIRECT_REF_P (lhs))
+	    lhs = TREE_OPERAND (lhs, 0);
+	  if (lhs != base)
+	    continue;
+	}
 must_exec = get_lim_data (loc->stmt)->always_executed_in;
 if (!must_exec)
 	continue;
 /* Returns true if we can perform store motion of REF from LOOP.  */
 static bool
 can_sm_ref_p (struct loop *loop, mem_ref_p ref)
 {
+tree base;
 /* Unless the reference is stored in the loop, there is nothing to do.  */
 if (!bitmap_bit_p (ref->stored, loop->num))
 return false;
 /* It should be movable.  */
 if (!is_gimple_reg_type (TREE_TYPE (ref->mem))
 || TREE_THIS_VOLATILE (ref->mem)
 || !for_each_index (&ref->mem, may_move_till, loop))
 return false;
-/* If it can trap, it must be always executed in LOOP.  */
+/* If it can trap, it must be always executed in LOOP.
-if (tree_could_trap_p (ref->mem)
+Readonly memory locations may trap when storing to them, but
-&& !ref_always_accessed_p (loop, ref))
+tree_could_trap_p is a predicate for rvalues, so check that
+explicitly.  */
+base = get_base_address (ref->mem);
+if ((tree_could_trap_p (ref->mem)
+|| (DECL_P (base) && TREE_READONLY (base)))
+&& !ref_always_accessed_p (loop, ref, true))
 return false;
 /* And it must be independent on all other memory references
 in LOOP.  */
 if (!ref_indep_loop_p (loop, ref))
 }
 /* Moves invariants from loops.  Only "expensive" invariants are moved out --
 i.e. those that are likely to be win regardless of the register pressure.  */
-void
+unsigned int
 tree_ssa_lim (void)
 {
+unsigned int todo;
 tree_ssa_lim_initialize ();
 /* Gathers information about memory accesses in the loops.  */
 analyze_memory_references ();
 /* Execute store motion.  Force the necessary invariants to be moved
 out of the loops as well.  */
 store_motion ();
 /* Move the expressions that are expensive enough.  */
-move_computations ();
+todo = move_computations ();
 tree_ssa_lim_finalize ();
-}
+return todo;
+}

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-loop-im.c @ 63:b7f97abdc517 gcc-4.6-20100522