This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [4.5] Find more autoinc addressing for induction variables


Zdenek Dvorak wrote:
yes, this certainly looks like an approach that plays well with
the rest of ivopts.  Of course, assuming that it actually will
work (and will not be prohibitively expensive on compile time) ;-)

Here's a new patch. Major changes from the previous one: * We actually do need to give a cost bonus in certain situations; otherwise we might decide to use an autoinc candidate, but not at the use where we're incrementing it. It's simpler than before since we know exactly which cand/use pair can get a bonus, so we no longer need code in iv_ca_recount_cost. Instead, I subtract the cost_step from the cost at the corresponding cost_pair. Cost is now an integer since it can be negative in these cases. * The new patch makes an attempt to detect if the original iv can be used for autoinc, and gives it a bonus as well.

On the Blackfin, this is almost too aggressive now; we run into slight problems with irregularities in the machine's addressing modes and have to reload autoinc addressing modes more often than I'd like. I have ideas how to fix this, however (e.g. running auto-inc-dec after reload instead of before).

Regression tested on bfin-elf. I've bootstrapped a variant patch on i686-linux, after disabling the part that requires autoinc addressing modes. Without that, testing on i686 is relatively meaningless. The bootstrap showed the need not to insert statements after a memory reference that may throw.


Bernd -- This footer brought to you by insane German lawmakers. Analog Devices GmbH Wilhelm-Wagenfeld-Str. 6 80807 Muenchen Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368 Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif
	* tree-ssa-loop-ivopts.c (comp_cost): Make COST an integeer.
	(struct cost_pair): New member CAN_AUTOINC.
	(enum iv_position): Add IP_AT_USE.
	(struct iv_cand): New members COST_STEP and AINC_USE.
	(dump_cand): Handle IP_AT_USE.
	(stmt_after_increment): Likewise.
	(stmt_after_inc_pos): Renamed from stmt_after_ip_original_pos.  All
	callers changed.  Use gimple_uid comparison instead of scanning.
	(add_candidate_1): When looking for identical candidates, take
	AINC_USE into account.  Set it for new candidates.
	(force_expr_to_var_cost): Cast target_spill_cost to int.
	(set_use_iv_cost): New argument CAN_AUTOINC, used to initialize the
	corresponding member in the cost_pair; all callers changed.
	(get_address_cost): New arguments STMT_AFTER_INC and MAY_AUTOINC.
	All callers changed.  Check for availability of autoinc addressing
	modes, both in general for a given mode, and in the specific use
	case.
	(get_computation_cost_at): New argument CAN_AUTOINC.  All callers
	changed.
	(get_computation_cost): Likewise.
	(autoinc_possible_for_pair, maybe_allocate_autoinc_cand,
	add_autoinc_candidates): New static functions.
	(finish_iv_candidates): Call add_autoinc_candidates.
	(determine_use_iv_cost_address): If we have an autoinc candidate at
	the matching use, subtract the cost of the candidate's step from the
	cost.
	(determine_iv_cost): Record the cost of the increment in the COST_STEP
	member of the candidate.
	(tree_ssa_iv_optimize_loop): Swap the calls to determine_iv_costs and
	determine_use_iv_costs.  Call renumber_gimple_stmt_uids.

testsuite/
	* gcc.target/bfin/loop-autoinc.c: New file.

Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 147846)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -135,7 +135,7 @@ enum use_type
 /* Cost of a computation.  */
 typedef struct
 {
-  unsigned cost;	/* The runtime cost.  */
+  int cost;		/* The runtime cost.  */
   unsigned complexity;	/* The estimate of the complexity of the code for
 			   the computation (in no concrete units --
 			   complexity field should be larger for more
@@ -155,6 +155,8 @@ struct cost_pair
   tree value;		/* For final value elimination, the expression for
 			   the final value of the iv.  For iv elimination,
 			   the new bound to compare with.  */
+  bool can_autoinc;	/* True if we think we can use autoincrement for
+			   this candidate/use pair.  */
 };
 
 /* Use.  */
@@ -181,6 +183,7 @@ enum iv_position
 {
   IP_NORMAL,		/* At the end, just before the exit condition.  */
   IP_END,		/* At the end of the latch block.  */
+  IP_AT_USE,		/* After a specific use.  */
   IP_ORIGINAL		/* The original biv.  */
 };
 
@@ -200,6 +203,9 @@ struct iv_cand
 			   to replace the final value of an iv by direct
 			   computation of the value.  */
   unsigned cost;	/* Cost of the candidate.  */
+  unsigned cost_step;	/* Cost of the candidate's increment operation.  */
+  struct iv_use *ainc_use; /* For IP_AT_USE candidates, the place where it is
+			      incremented.  */
   bitmap depends_on;	/* The list of invariants that are used in step of the
 			   biv.  */
 };
@@ -515,6 +521,10 @@ dump_cand (FILE *file, struct iv_cand *c
       fprintf (file, "  incremented before exit test\n");
       break;
 
+    case IP_AT_USE:
+      fprintf (file, "  incremented at use %d\n", cand->ainc_use->id);
+      break;
+
     case IP_END:
       fprintf (file, "  incremented at end\n");
       break;
@@ -566,11 +576,10 @@ stmt_after_ip_normal_pos (struct loop *l
    variable CAND is incremented.  */
 
 static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, gimple stmt)
+stmt_after_inc_pos (struct iv_cand *cand, gimple stmt)
 {
   basic_block cand_bb = gimple_bb (cand->incremented_at);
   basic_block stmt_bb = gimple_bb (stmt);
-  gimple_stmt_iterator bsi;
 
   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
     return false;
@@ -578,15 +587,7 @@ stmt_after_ip_original_pos (struct iv_ca
   if (stmt_bb != cand_bb)
     return true;
 
-  /* Scan the block from the end, since the original ivs are usually
-     incremented at the end of the loop body.  */
-  for (bsi = gsi_last_bb (stmt_bb); ; gsi_prev (&bsi))
-    {
-      if (gsi_stmt (bsi) == cand->incremented_at)
-	return false;
-      if (gsi_stmt (bsi) == stmt)
-	return true;
-    }
+  return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
 }
 
 /* Returns true if STMT if after the place where the induction variable
@@ -604,7 +605,8 @@ stmt_after_increment (struct loop *loop,
       return stmt_after_ip_normal_pos (loop, stmt);
 
     case IP_ORIGINAL:
-      return stmt_after_ip_original_pos (cand, stmt);
+    case IP_AT_USE:
+      return stmt_after_inc_pos (cand, stmt);
 
     default:
       gcc_unreachable ();
@@ -2085,7 +2087,8 @@ add_candidate_1 (struct ivopts_data *dat
       if (cand->pos != pos)
 	continue;
 
-      if (cand->incremented_at != incremented_at)
+      if (cand->incremented_at != incremented_at
+	  || (pos == IP_AT_USE && cand->ainc_use != use))
 	continue;
 
       if (!cand->iv)
@@ -2131,6 +2134,11 @@ add_candidate_1 (struct ivopts_data *dat
 	  walk_tree (&step, find_depends, &cand->depends_on, NULL);
 	}
 
+      if (pos == IP_AT_USE)
+	cand->ainc_use = use;
+      else
+	cand->ainc_use = NULL;
+
       if (dump_file && (dump_flags & TDF_DETAILS))
 	dump_cand (dump_file, cand);
     }
@@ -2360,24 +2368,6 @@ record_important_candidates (struct ivop
     }
 }
 
-/* Finds the candidates for the induction variables.  */
-
-static void
-find_iv_candidates (struct ivopts_data *data)
-{
-  /* Add commonly used ivs.  */
-  add_standard_iv_candidates (data);
-
-  /* Add old induction variables.  */
-  add_old_ivs_candidates (data);
-
-  /* Add induction variables derived from uses.  */
-  add_derived_ivs_candidates (data);
-
-  /* Record the important candidates.  */
-  record_important_candidates (data);
-}
-
 /* Allocates the data structure mapping the (use, candidate) pairs to costs.
    If consider_all_candidates is true, we use a two-dimensional array, otherwise
    we allocate a simple list to every use.  */
@@ -2474,7 +2464,8 @@ infinite_cost_p (comp_cost cost)
 static void
 set_use_iv_cost (struct ivopts_data *data,
 		 struct iv_use *use, struct iv_cand *cand,
-		 comp_cost cost, bitmap depends_on, tree value)
+		 comp_cost cost, bitmap depends_on, tree value,
+		 bool can_autoinc)
 {
   unsigned i, s;
 
@@ -2490,6 +2481,7 @@ set_use_iv_cost (struct ivopts_data *dat
       use->cost_map[cand->id].cost = cost;
       use->cost_map[cand->id].depends_on = depends_on;
       use->cost_map[cand->id].value = value;
+      use->cost_map[cand->id].can_autoinc = can_autoinc;
       return;
     }
 
@@ -2509,6 +2501,7 @@ found:
   use->cost_map[i].cost = cost;
   use->cost_map[i].depends_on = depends_on;
   use->cost_map[i].value = value;
+  use->cost_map[i].can_autoinc = can_autoinc;
 }
 
 /* Gets cost of (USE, CANDIDATE) pair.  */
@@ -2993,21 +2986,30 @@ multiplier_allowed_in_address_p (HOST_WI
    variable is omitted.  Compute the cost for a memory reference that accesses
    a memory location of mode MEM_MODE.
 
+   MAY_AUTOINC is set to true if the autoincrement (increasing index by
+   size of MEM_MODE / RATIO) is available.  To make this determination, we
+   look at the size of the increment to be made, which is given in CSTEP.
+   CSTEP may be zero if the step is unknown.
+   STMT_AFTER_INC is true iff the statement we're looking at is after the
+   increment of the original biv.
+
    TODO -- there must be some better way.  This all is quite crude.  */
 
 static comp_cost
 get_address_cost (bool symbol_present, bool var_present,
 		  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
-		  enum machine_mode mem_mode,
-		  bool speed)
+		  HOST_WIDE_INT cstep, enum machine_mode mem_mode, bool speed,
+		  bool stmt_after_inc, bool *may_autoinc)
 {
   static bool initialized[MAX_MACHINE_MODE];
   static HOST_WIDE_INT rat[MAX_MACHINE_MODE], off[MAX_MACHINE_MODE];
   static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
   static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
+  static bool has_preinc[MAX_MACHINE_MODE], has_postinc[MAX_MACHINE_MODE];
+  static bool has_predec[MAX_MACHINE_MODE], has_postdec[MAX_MACHINE_MODE];
   unsigned cost, acost, complexity;
-  bool offset_p, ratio_p;
-  HOST_WIDE_INT s_offset;
+  bool offset_p, ratio_p, autoinc;
+  HOST_WIDE_INT s_offset, autoinc_offset, msize;
   unsigned HOST_WIDE_INT mask;
   unsigned bits;
 
@@ -3066,6 +3068,26 @@ get_address_cost (bool symbol_present, b
       reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
       reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
 
+      if (HAVE_PRE_DECREMENT)
+	{
+	  addr = gen_rtx_PRE_DEC (Pmode, reg0);
+	  has_predec[mem_mode] = memory_address_p (mem_mode, addr);
+	}
+      if (HAVE_POST_DECREMENT)
+	{
+	  addr = gen_rtx_POST_DEC (Pmode, reg0);
+	  has_postdec[mem_mode] = memory_address_p (mem_mode, addr);
+	}
+      if (HAVE_PRE_INCREMENT)
+	{
+	  addr = gen_rtx_PRE_INC (Pmode, reg0);
+	  has_preinc[mem_mode] = memory_address_p (mem_mode, addr);
+	}
+      if (HAVE_POST_INCREMENT)
+	{
+	  addr = gen_rtx_POST_INC (Pmode, reg0);
+	  has_postinc[mem_mode] = memory_address_p (mem_mode, addr);
+	}
       for (i = 0; i < 16; i++)
 	{
 	  sym_p = i & 1;
@@ -3104,7 +3126,7 @@ get_address_cost (bool symbol_present, b
     
 	  if (base)
 	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, base);
-  
+
 	  start_sequence ();
 	  /* To avoid splitting addressing modes, pretend that no cse will
 	     follow.  */
@@ -3149,7 +3171,7 @@ get_address_cost (bool symbol_present, b
 	  if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
 	    costs[mem_mode][1][var_p][off_p][rat_p] = acost;
 	}
-  
+
       if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "Address costs:\n");
@@ -3174,6 +3196,9 @@ get_address_cost (bool symbol_present, b
 	      acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
 	      fprintf (dump_file, "index costs %d\n", acost);
 	    }
+	  if (has_predec[mem_mode] || has_postdec[mem_mode]
+	      || has_preinc[mem_mode] || has_postinc[mem_mode])
+	    fprintf (dump_file, "  May include autoinc/dec\n");
 	  fprintf (dump_file, "\n");
 	}
     }
@@ -3185,6 +3210,23 @@ get_address_cost (bool symbol_present, b
     offset |= ~mask;
   s_offset = offset;
 
+  autoinc = false;
+  msize = GET_MODE_SIZE (mem_mode);
+  autoinc_offset = offset;
+  if (stmt_after_inc)
+    autoinc_offset += ratio * cstep;
+  if (symbol_present || var_present || ratio != 1)
+    autoinc = false;
+  else if ((has_postinc[mem_mode] && autoinc_offset == 0
+	       && msize == cstep)
+	   || (has_postdec[mem_mode] && autoinc_offset == 0
+	       && msize == -cstep)
+	   || (has_preinc[mem_mode] && autoinc_offset == msize
+	       && msize == cstep)
+	   || (has_predec[mem_mode] && autoinc_offset == -msize
+	       && msize == -cstep))
+    autoinc = true;
+
   cost = 0;
   offset_p = (s_offset != 0
 	      && min_offset[mem_mode] <= s_offset
@@ -3198,6 +3240,8 @@ get_address_cost (bool symbol_present, b
   if (s_offset && !offset_p && !symbol_present)
     cost += add_cost (Pmode, speed);
 
+  if (may_autoinc)
+    *may_autoinc = autoinc;
   acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
   complexity = (symbol_present != 0) + (var_present != 0) + offset_p + ratio_p;
   return new_cost (cost + acost, complexity);
@@ -3336,7 +3380,7 @@ force_expr_to_var_cost (tree expr, bool 
      computations often are either loop invariant or at least can
      be shared between several iv uses, so letting this grow without
      limits would not give reasonable results.  */
-  if (cost.cost > target_spill_cost [speed])
+  if (cost.cost > (int)target_spill_cost [speed])
     cost.cost = target_spill_cost [speed];
 
   return cost;
@@ -3502,14 +3546,15 @@ difference_cost (struct ivopts_data *dat
 static comp_cost
 get_computation_cost_at (struct ivopts_data *data,
 			 struct iv_use *use, struct iv_cand *cand,
-			 bool address_p, bitmap *depends_on, gimple at)
+			 bool address_p, bitmap *depends_on, gimple at,
+			 bool *can_autoinc)
 {
   tree ubase = use->iv->base, ustep = use->iv->step;
   tree cbase, cstep;
   tree utype = TREE_TYPE (ubase), ctype;
   unsigned HOST_WIDE_INT cstepi, offset = 0;
   HOST_WIDE_INT ratio, aratio;
-  bool var_present, symbol_present;
+  bool var_present, symbol_present, stmt_is_after_inc;
   comp_cost cost;
   unsigned n_sums;
   double_int rat;
@@ -3604,16 +3649,20 @@ get_computation_cost_at (struct ivopts_d
 
   /* If we are after the increment, the value of the candidate is higher by
      one iteration.  */
-  if (stmt_after_increment (data->current_loop, cand, at))
+  stmt_is_after_inc = stmt_after_increment (data->current_loop, cand, at);
+  if (stmt_is_after_inc)
     offset -= ratio * cstepi;
 
   /* Now the computation is in shape symbol + var1 + const + ratio * var2.
      (symbol/var/const parts may be omitted).  If we are looking for an address,
      find the cost of addressing this.  */
   if (address_p)
-    return add_costs (cost, get_address_cost (symbol_present, var_present,
-				offset, ratio,
-				TYPE_MODE (TREE_TYPE (*use->op_p)), speed));
+    return add_costs (cost,
+		      get_address_cost (symbol_present, var_present,
+					offset, ratio, cstepi,
+					TYPE_MODE (TREE_TYPE (*use->op_p)),
+					speed, stmt_is_after_inc,
+					can_autoinc));
 
   /* Otherwise estimate the costs for computing the expression.  */
   aratio = ratio > 0 ? ratio : -ratio;
@@ -3644,6 +3693,9 @@ get_computation_cost_at (struct ivopts_d
 
 fallback:
   {
+    if (can_autoinc)
+      *can_autoinc = false;
+
     /* Just get the expression, expand it and measure the cost.  */
     tree comp = get_computation_at (data->current_loop, use, cand, at);
 
@@ -3666,10 +3718,11 @@ fallback:
 static comp_cost
 get_computation_cost (struct ivopts_data *data,
 		      struct iv_use *use, struct iv_cand *cand,
-		      bool address_p, bitmap *depends_on)
+		      bool address_p, bitmap *depends_on, bool *can_autoinc)
 {
   return get_computation_cost_at (data,
-				  use, cand, address_p, depends_on, use->stmt);
+				  use, cand, address_p, depends_on, use->stmt,
+				  can_autoinc);
 }
 
 /* Determines cost of basing replacement of USE on CAND in a generic
@@ -3689,12 +3742,12 @@ determine_use_iv_cost_generic (struct iv
   if (cand->pos == IP_ORIGINAL
       && cand->incremented_at == use->stmt)
     {
-      set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
+      set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE, false);
       return true;
     }
 
-  cost = get_computation_cost (data, use, cand, false, &depends_on);
-  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
+  cost = get_computation_cost (data, use, cand, false, &depends_on, NULL);
+  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, false);
 
   return !infinite_cost_p (cost);
 }
@@ -3706,9 +3759,16 @@ determine_use_iv_cost_address (struct iv
 			       struct iv_use *use, struct iv_cand *cand)
 {
   bitmap depends_on;
-  comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on);
+  bool can_autoinc;
+  comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
+					 &can_autoinc);
 
-  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
+  if (cand->ainc_use == use)
+    {
+      gcc_assert (can_autoinc);
+      cost.cost -= cand->cost_step;
+    }
+  set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, can_autoinc);
 
   return !infinite_cost_p (cost);
 }
@@ -3866,7 +3926,7 @@ determine_use_iv_cost_condition (struct 
   /* Only consider real candidates.  */
   if (!cand->iv)
     {
-      set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE);
+      set_use_iv_cost (data, use, cand, infinite_cost, NULL, NULL_TREE, false);
       return false;
     }
 
@@ -3887,7 +3947,7 @@ determine_use_iv_cost_condition (struct 
   gcc_assert (ok);
 
   express_cost = get_computation_cost (data, use, cand, false,
-				       &depends_on_express);
+				       &depends_on_express, NULL);
   fd_ivopts_data = data;
   walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
 
@@ -3906,7 +3966,7 @@ determine_use_iv_cost_condition (struct 
       bound = NULL_TREE;
     }
 
-  set_use_iv_cost (data, use, cand, cost, depends_on, bound);
+  set_use_iv_cost (data, use, cand, cost, depends_on, bound, false);
 
   if (depends_on_elim)
     BITMAP_FREE (depends_on_elim);
@@ -3939,6 +3999,135 @@ determine_use_iv_cost (struct ivopts_dat
     }
 }
 
+/* Return true if get_computation_cost indicates that autoincrement is
+   a possibility for the pair of USE and CAND, false otherwise.  */
+
+static bool
+autoinc_possible_for_pair (struct ivopts_data *data, struct iv_use *use,
+			   struct iv_cand *cand)
+{
+  bitmap depends_on;
+  bool can_autoinc;
+  comp_cost cost;
+
+  if (use->type != USE_ADDRESS)
+    return false;
+
+  cost = get_computation_cost (data, use, cand, true, &depends_on,
+			       &can_autoinc);
+
+  BITMAP_FREE (depends_on);
+
+  return !infinite_cost_p (cost) && can_autoinc;
+}
+
+/* Examine candidate CAND to see if autoinc is possible at use USE, which
+   is known to be a memory reference.  If so, allocate a new IP_AT_USE
+   candidate for the pair.  */
+static void
+maybe_allocate_autoinc_cand (struct ivopts_data *data, struct iv_use *use,
+			     struct iv_cand *cand)
+{
+  if ((cand->pos != IP_NORMAL
+       && (ip_normal_pos (data->current_loop) || cand->pos != IP_END))
+      || stmt_after_increment (data->current_loop, cand, use->stmt)
+      || !autoinc_possible_for_pair (data, use, cand))
+    return;
+
+  add_candidate_1 (data, cand->iv->base, cand->iv->step, cand->important,
+		   IP_AT_USE, use, use->stmt);
+}
+
+/* Examine all the use/candidate pairs to see if we find autoincrement
+   opportunities, and create new IP_AT_USE candidates as appropriate.
+   Also, examine IP_ORIGINAL candidates to see if they are incremented
+   next to a use that allows autoincrement, and set their AINC_USE if
+   possible.  */
+
+static void
+add_autoinc_candidates (struct ivopts_data *data)
+{
+  unsigned i, j;
+  struct iv_cand *cand;
+  struct loop *loop = data->current_loop;
+
+  for (i = 0; i < n_iv_uses (data); i++)
+    {
+      struct iv_use *use = iv_use (data, i);
+      basic_block use_bb = gimple_bb (use->stmt);
+
+      if (use->type != USE_ADDRESS
+	  /* If we insert the increment in any position other than the standard
+	     ones, we must ensure that it is incremented once per iteration.
+	     It must not be in an inner nested loop, or one side of an if
+	     statement.  This is ensured by the following two conditions.  */
+	  || use_bb->loop_father != loop
+	  || !dominated_by_p (CDI_DOMINATORS, loop->latch, use_bb)
+	  || stmt_could_throw_p (use->stmt))
+	continue;
+
+      if (data->consider_all_candidates)
+	{
+	  for (j = 0; j < n_iv_cands (data); j++)
+	    {
+	      cand = iv_cand (data, j);
+	      maybe_allocate_autoinc_cand (data, use, cand);
+	    }
+	}
+      else
+	{
+	  bitmap_iterator bi;
+
+	  EXECUTE_IF_SET_IN_BITMAP (use->related_cands, 0, j, bi)
+	    {
+	      cand = iv_cand (data, j);
+	      maybe_allocate_autoinc_cand (data, use, cand);
+	    }
+	}
+    }
+
+  for (i = 0; i < n_iv_cands (data); i++)
+    {
+      struct iv_cand *cand = iv_cand (data, i);
+      struct iv_use *closest = NULL;
+      if (cand->pos != IP_ORIGINAL)
+	continue;
+      for (j = 0; j < n_iv_uses (data); j++)
+	{
+	  struct iv_use *use = iv_use (data, j);
+	  unsigned uid = gimple_uid (use->stmt);
+	  if (gimple_bb (use->stmt) != gimple_bb (cand->incremented_at)
+	      || uid > gimple_uid (cand->incremented_at))
+	    continue;
+	  if (closest == NULL || uid > gimple_uid (closest->stmt))
+	    closest = use;
+	}
+      if (closest == NULL || !autoinc_possible_for_pair (data, closest, cand))
+	continue;
+      cand->ainc_use = closest;
+    }
+}
+
+/* Finds the candidates for the induction variables.  */
+
+static void
+find_iv_candidates (struct ivopts_data *data)
+{
+  /* Add commonly used ivs.  */
+  add_standard_iv_candidates (data);
+
+  /* Add old induction variables.  */
+  add_old_ivs_candidates (data);
+
+  /* Add induction variables derived from uses.  */
+  add_derived_ivs_candidates (data);
+
+  add_autoinc_candidates (data);
+
+  /* Record the important candidates.  */
+  record_important_candidates (data);
+}
+
 /* Determines costs of basing the use of the iv on an iv candidate.  */
 
 static void
@@ -4036,8 +4225,8 @@ determine_iv_cost (struct ivopts_data *d
 
   base = cand->iv->base;
   cost_base = force_var_cost (data, base, NULL);
-  cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
 
+  cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
   cost = cost_step + cost_base.cost / AVG_LOOP_NITER (current_loop);
 
   /* Prefer the original ivs unless we may gain something by replacing it.
@@ -4054,6 +4243,7 @@ determine_iv_cost (struct ivopts_data *d
     cost++;
 
   cand->cost = cost;
+  cand->cost_step = cost_step;
 }
 
 /* Determines costs of computation of the candidates.  */
@@ -4305,6 +4495,7 @@ iv_ca_set_cp (struct ivopts_data *data, 
       ivs->bad_uses--;
       ivs->cand_for_use[uid] = cp;
       ivs->n_cand_uses[cid]++;
+      
       if (ivs->n_cand_uses[cid] == 1)
 	{
 	  bitmap_set_bit (ivs->cands, cid);
@@ -4316,7 +4507,7 @@ iv_ca_set_cp (struct ivopts_data *data, 
 
 	  iv_ca_set_add_invariants (ivs, cp->cand->depends_on);
 	}
-
+  
       ivs->cand_use_cost = add_costs (ivs->cand_use_cost, cp->cost);
       iv_ca_set_add_invariants (ivs, cp->depends_on);
       iv_ca_recount_cost (data, ivs);
@@ -5000,6 +5191,11 @@ create_new_iv (struct ivopts_data *data,
       after = true;
       break;
 
+    case IP_AT_USE:
+      incr_pos = gsi_for_stmt (cand->incremented_at);
+      after = true;
+      break;
+
     case IP_ORIGINAL:
       /* Mark that the iv is preserved.  */
       name_info (data, cand->var_before)->preserve_biv = true;
@@ -5492,12 +5688,14 @@ tree_ssa_iv_optimize_loop (struct ivopts
   if (n_iv_uses (data) > MAX_CONSIDERED_USES)
     goto finish;
 
+  renumber_gimple_stmt_uids ();
+
   /* Finds candidates for the induction variables (item 2).  */
   find_iv_candidates (data);
 
   /* Calculates the costs (item 3, part 1).  */
-  determine_use_iv_costs (data);
   determine_iv_costs (data);
+  determine_use_iv_costs (data);
   determine_set_costs (data);
 
   /* Find the optimal set of induction variables (item 3, part 2).  */
Index: testsuite/gcc.target/bfin/loop-autoinc.c
===================================================================
--- testsuite/gcc.target/bfin/loop-autoinc.c	(revision 0)
+++ testsuite/gcc.target/bfin/loop-autoinc.c	(revision 0)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+/* { dg-final { scan-assembler " = \\\[\[PI\].\\+\\+\\\];" } } */
+extern int x[];
+extern void bar();
+int foo ()
+{
+  int i;
+  int sum = 0;
+  for (i = 0; i < 100; i++) {
+    sum += x[i];
+    if (sum & 1)
+      sum *= sum;
+  }
+  return sum;
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]