Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 188110)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -157,10 +157,10 @@ enum use_type
 typedef struct
 {
   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
-			   complex expressions and addressing modes).  */
+  int complexity;	/* The estimate of the complexity of the code for
+			   addressing modes in the computation (in no
+			   concrete units -- complexity field should be
+			   larger for more complex addressing modes).  */
 } comp_cost;
 
 static const comp_cost zero_cost = {0, 0};
@@ -2621,7 +2621,7 @@ alloc_use_cost_map (struct ivopts_data *
    cost is RUNTIME and complexity corresponds to COMPLEXITY.  */
 
 static comp_cost
-new_cost (unsigned runtime, unsigned complexity)
+new_cost (int runtime, int complexity)
 {
   comp_cost cost;
 
@@ -2659,7 +2659,7 @@ static int
 compare_costs (comp_cost cost1, comp_cost cost2)
 {
   if (cost1.cost == cost2.cost)
-    return cost1.complexity - cost2.complexity;
+    return cost2.complexity - cost1.complexity;
 
   return cost1.cost - cost2.cost;
 }
@@ -3182,15 +3182,23 @@ multiplier_allowed_in_address_p (HOST_WI
     {
       enum machine_mode address_mode = targetm.addr_space.address_mode (as);
       rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-      rtx addr;
+      rtx reg2 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
+      rtx addr, mult;
       HOST_WIDE_INT i;
 
       valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
       sbitmap_zero (valid_mult);
-      addr = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
+      /* Use an expression of the form (PLUS (MULT reg1 constant) reg2)
+	 to test the validity of various constants.  Plain (MULT reg1 constant)
+	 is less likely to be a valid address RTX on many targets, and
+	 probably (PLUS (MULT reg1 constant) symbol) likewise.  Note that
+	 we're assuming the set of valid multipliers is the same for any/all
+	 of the three address RTX forms that allow them.  */
+      mult = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
+      addr = gen_rtx_fmt_ee (PLUS, address_mode, mult, reg2);
       for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
 	{
-	  XEXP (addr, 1) = gen_int_mode (i, address_mode);
+	  XEXP (mult, 1) = gen_int_mode (i, address_mode);
 	  if (memory_address_addr_space_p (mode, addr, as))
 	    SET_BIT (valid_mult, i + MAX_RATIO);
 	}
@@ -3224,292 +3232,136 @@ multiplier_allowed_in_address_p (HOST_WI
    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.  */
-
-typedef struct
-{
-  HOST_WIDE_INT min_offset, max_offset;
-  unsigned costs[2][2][2][2];
-} *address_cost_data;
-
-DEF_VEC_P (address_cost_data);
-DEF_VEC_ALLOC_P (address_cost_data, heap);
+   increment of the original biv.  */
 
 static comp_cost
 get_address_cost (bool symbol_present, bool var_present,
 		  unsigned HOST_WIDE_INT offset, HOST_WIDE_INT ratio,
 		  HOST_WIDE_INT cstep, enum machine_mode mem_mode,
 		  addr_space_t as, bool speed,
-		  bool stmt_after_inc, bool *may_autoinc)
+		  bool stmt_after_inc, bool *may_autoinc,
+		  struct ivopts_data *data)
 {
   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
-  static VEC(address_cost_data, heap) *address_cost_data_list;
-  unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mem_mode;
-  address_cost_data data;
-  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, autoinc;
-  HOST_WIDE_INT s_offset, autoinc_offset, msize;
-  unsigned HOST_WIDE_INT mask;
-  unsigned bits;
-
-  if (data_index >= VEC_length (address_cost_data, address_cost_data_list))
-    VEC_safe_grow_cleared (address_cost_data, heap, address_cost_data_list,
-			   data_index + 1);
-
-  data = VEC_index (address_cost_data, address_cost_data_list, data_index);
-  if (!data)
-    {
-      HOST_WIDE_INT i;
-      HOST_WIDE_INT rat, off = 0;
-      int old_cse_not_expected, width;
-      unsigned sym_p, var_p, off_p, rat_p, add_c;
-      rtx seq, addr, base;
-      rtx reg0, reg1;
-
-      data = (address_cost_data) xcalloc (1, sizeof (*data));
-
-      reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-
-      width = GET_MODE_BITSIZE (address_mode) - 1;
-      if (width > (HOST_BITS_PER_WIDE_INT - 1))
-	width = HOST_BITS_PER_WIDE_INT - 1;
-      addr = gen_rtx_fmt_ee (PLUS, address_mode, reg1, NULL_RTX);
-
-      for (i = width; i >= 0; i--)
-	{
-	  off = -((HOST_WIDE_INT) 1 << i);
-	  XEXP (addr, 1) = gen_int_mode (off, address_mode);
-	  if (memory_address_addr_space_p (mem_mode, addr, as))
-	    break;
-	}
-      data->min_offset = (i == -1? 0 : off);
-
-      for (i = width; i >= 0; i--)
-	{
-	  off = ((HOST_WIDE_INT) 1 << i) - 1;
-	  XEXP (addr, 1) = gen_int_mode (off, address_mode);
-	  if (memory_address_addr_space_p (mem_mode, addr, as))
-	    break;
-	}
-      if (i == -1)
-        off = 0;
-      data->max_offset = off;
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "get_address_cost:\n");
-	  fprintf (dump_file, "  min offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
-		   GET_MODE_NAME (mem_mode),
-		   data->min_offset);
-	  fprintf (dump_file, "  max offset %s " HOST_WIDE_INT_PRINT_DEC "\n",
-		   GET_MODE_NAME (mem_mode),
-		   data->max_offset);
-	}
-
-      rat = 1;
-      for (i = 2; i <= MAX_RATIO; i++)
-	if (multiplier_allowed_in_address_p (i, mem_mode, as))
-	  {
-	    rat = i;
-	    break;
-	  }
-
-      /* Compute the cost of various addressing modes.  */
-      acost = 0;
-      reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-      reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
-
-      if (USE_LOAD_PRE_DECREMENT (mem_mode) 
-	  || USE_STORE_PRE_DECREMENT (mem_mode))
-	{
-	  addr = gen_rtx_PRE_DEC (address_mode, reg0);
-	  has_predec[mem_mode]
-	    = memory_address_addr_space_p (mem_mode, addr, as);
-	}
-      if (USE_LOAD_POST_DECREMENT (mem_mode) 
-	  || USE_STORE_POST_DECREMENT (mem_mode))
-	{
-	  addr = gen_rtx_POST_DEC (address_mode, reg0);
-	  has_postdec[mem_mode]
-	    = memory_address_addr_space_p (mem_mode, addr, as);
-	}
-      if (USE_LOAD_PRE_INCREMENT (mem_mode) 
-	  || USE_STORE_PRE_DECREMENT (mem_mode))
-	{
-	  addr = gen_rtx_PRE_INC (address_mode, reg0);
-	  has_preinc[mem_mode]
-	    = memory_address_addr_space_p (mem_mode, addr, as);
-	}
-      if (USE_LOAD_POST_INCREMENT (mem_mode) 
-	  || USE_STORE_POST_INCREMENT (mem_mode))
-	{
-	  addr = gen_rtx_POST_INC (address_mode, reg0);
-	  has_postinc[mem_mode]
-	    = memory_address_addr_space_p (mem_mode, addr, as);
+  rtx reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
+  rtx addr = NULL_RTX;
+  rtx base = NULL_RTX;
+  int cost, complexity;
+
+  if (may_autoinc && *may_autoinc
+      && !symbol_present && !var_present && ratio == 1)
+    {
+      HOST_WIDE_INT msize = GET_MODE_SIZE (mem_mode);
+      HOST_WIDE_INT autoinc_offset = stmt_after_inc ? offset + cstep : offset;
+      if ((USE_LOAD_POST_INCREMENT (mem_mode)
+	   || USE_STORE_POST_INCREMENT (mem_mode))
+	  && autoinc_offset == 0 && msize == cstep)
+	addr = gen_rtx_POST_INC (address_mode, reg0);
+      else if ((USE_LOAD_POST_DECREMENT (mem_mode)
+		|| USE_STORE_POST_DECREMENT (mem_mode))
+	       && autoinc_offset == 0 && msize == -cstep)
+	addr = gen_rtx_POST_DEC (address_mode, reg0);
+      else if ((USE_LOAD_PRE_INCREMENT (mem_mode)
+		|| USE_STORE_PRE_INCREMENT (mem_mode))
+	       && autoinc_offset == msize && msize == cstep)
+	addr = gen_rtx_PRE_INC (address_mode, reg0);
+      else if ((USE_LOAD_PRE_DECREMENT (mem_mode)
+		|| USE_STORE_PRE_DECREMENT (mem_mode))
+	       && autoinc_offset == -msize && msize == -cstep)
+	addr = gen_rtx_PRE_DEC (address_mode, reg0);
+      if (addr && memory_address_addr_space_p (mem_mode, addr, as))
+	{
+	  *may_autoinc = true;
+	  /* Favor autoinc modes in case of a cost tie.  */
+	  return new_cost (address_cost (addr, mem_mode, as, speed), 5);
 	}
-      for (i = 0; i < 16; i++)
-	{
-	  sym_p = i & 1;
-	  var_p = (i >> 1) & 1;
-	  off_p = (i >> 2) & 1;
-	  rat_p = (i >> 3) & 1;
+    }
+  if (may_autoinc)
+    *may_autoinc = false;
 
-	  addr = reg0;
-	  if (rat_p)
-	    addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
-				   gen_int_mode (rat, address_mode));
+  addr = reg0;
+  if (ratio != 1)
+    addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
+			   gen_int_mode (ratio, address_mode));
+  if (var_present)
+    addr = gen_rtx_fmt_ee (PLUS, address_mode, addr,
+			   gen_raw_REG (address_mode,
+					LAST_VIRTUAL_REGISTER + 2));
+
+  if (offset != 0)
+    base = gen_int_mode (offset, address_mode);
+
+  if (symbol_present)
+    {
+      rtx sym = gen_rtx_SYMBOL_REF (address_mode, ggc_strdup (""));
+      /* ??? We can run into trouble with some backends by presenting
+	 it with symbols which haven't been properly passed through
+	 targetm.encode_section_info.  By setting the local bit, we
+	 enhance the probability of things working.  */
+      SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
+
+      if (base)
+	base = gen_rtx_fmt_e (CONST, address_mode,
+			      gen_rtx_fmt_ee (PLUS, address_mode, sym, base));
+      else
+	base = sym;
+    }
 
-	  if (var_p)
-	    addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, reg1);
+  if (base)
+    addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
 
-	  if (sym_p)
-	    {
-	      base = gen_rtx_SYMBOL_REF (address_mode, ggc_strdup (""));
-	      /* ??? We can run into trouble with some backends by presenting
-		 it with symbols which haven't been properly passed through
-		 targetm.encode_section_info.  By setting the local bit, we
-		 enhance the probability of things working.  */
-	      SYMBOL_REF_FLAGS (base) = SYMBOL_FLAG_LOCAL;
-
-	      if (off_p)
-		base = gen_rtx_fmt_e (CONST, address_mode,
-				      gen_rtx_fmt_ee
-					(PLUS, address_mode, base,
-					 gen_int_mode (off, address_mode)));
-	    }
-	  else if (off_p)
-	    base = gen_int_mode (off, address_mode);
+  if (memory_address_addr_space_p (mem_mode, addr, as))
+    {
+      cost = address_cost (addr, mem_mode, as, speed);
+      complexity = ((symbol_present != 0) + (var_present != 0)
+		    + (offset != 0) + (ratio != 1));
+    }
+  else
+    {
+      int old_cse_not_expected = cse_not_expected;
+      rtx seq, addr2;
+      
+      start_sequence ();
+      /* To avoid splitting addressing modes, pretend that no cse will
+	 follow.  */
+      cse_not_expected = true;
+      addr2 = memory_address_addr_space (mem_mode, addr, as);
+      cse_not_expected = old_cse_not_expected;
+      seq = get_insns ();
+      end_sequence ();
+      cost = seq_cost (seq, speed) + address_cost (addr2, mem_mode, as, speed);
+      complexity = 0;
+
+      /* If we ended up with a illegitimate address form involving a symbol,
+	 see if we can do better by converting the sym to a var and
+	 amortizing the load or addition cost over the iterations.
+	 Only allow this cost substituion if the address form is not
+	 legitimate as-is, because otherwise subsequent optimizations
+	 always seem to prefer leaving the symbol in the address RTX no
+	 matter how expensive it is.  Note also that hoisting the symbol
+	 load outside the loop requires an additional register that is live
+	 throughout the whole loop, and this additional register pressure
+	 cost is not otherwise accounted for in the ivopts cost model.  */
+      if (symbol_present)
+	{
+	  comp_cost alt = get_address_cost (false, true, 0,
+					    ratio, cstep, mem_mode, as, speed,
+					    stmt_after_inc, NULL, data);
+	  int altcost = alt.cost;
+	  if (var_present)
+	    altcost += adjust_setup_cost (data, add_cost (address_mode, speed));
 	  else
-	    base = NULL_RTX;
-
-	  if (base)
-	    addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, base);
-
-	  start_sequence ();
-	  /* To avoid splitting addressing modes, pretend that no cse will
-	     follow.  */
-	  old_cse_not_expected = cse_not_expected;
-	  cse_not_expected = true;
-	  addr = memory_address_addr_space (mem_mode, addr, as);
-	  cse_not_expected = old_cse_not_expected;
-	  seq = get_insns ();
-	  end_sequence ();
-
-	  acost = seq_cost (seq, speed);
-	  acost += address_cost (addr, mem_mode, as, speed);
-
-	  if (!acost)
-	    acost = 1;
-	  data->costs[sym_p][var_p][off_p][rat_p] = acost;
-	}
-
-      /* On some targets, it is quite expensive to load symbol to a register,
-	 which makes addresses that contain symbols look much more expensive.
-	 However, the symbol will have to be loaded in any case before the
-	 loop (and quite likely we have it in register already), so it does not
-	 make much sense to penalize them too heavily.  So make some final
-         tweaks for the SYMBOL_PRESENT modes:
-
-         If VAR_PRESENT is false, and the mode obtained by changing symbol to
-	 var is cheaper, use this mode with small penalty.
-	 If VAR_PRESENT is true, try whether the mode with
-	 SYMBOL_PRESENT = false is cheaper even with cost of addition, and
-	 if this is the case, use it.  */
-      add_c = add_cost (address_mode, speed);
-      for (i = 0; i < 8; i++)
-	{
-	  var_p = i & 1;
-	  off_p = (i >> 1) & 1;
-	  rat_p = (i >> 2) & 1;
-
-	  acost = data->costs[0][1][off_p][rat_p] + 1;
-	  if (var_p)
-	    acost += add_c;
-
-	  if (acost < data->costs[1][var_p][off_p][rat_p])
-	    data->costs[1][var_p][off_p][rat_p] = acost;
-	}
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "Address costs:\n");
-
-	  for (i = 0; i < 16; i++)
+	    altcost += 1;  /* Small penalty for additional register use.  */
+	  if (altcost < cost
+	      || (altcost == cost && alt.complexity > complexity))
 	    {
-	      sym_p = i & 1;
-	      var_p = (i >> 1) & 1;
-	      off_p = (i >> 2) & 1;
-	      rat_p = (i >> 3) & 1;
-
-	      fprintf (dump_file, "  ");
-	      if (sym_p)
-		fprintf (dump_file, "sym + ");
-	      if (var_p)
-		fprintf (dump_file, "var + ");
-	      if (off_p)
-		fprintf (dump_file, "cst + ");
-	      if (rat_p)
-		fprintf (dump_file, "rat * ");
-
-	      acost = data->costs[sym_p][var_p][off_p][rat_p];
-	      fprintf (dump_file, "index costs %d\n", acost);
+	      cost = altcost;
+	      complexity = alt.complexity;
 	    }
-	  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");
 	}
-
-      VEC_replace (address_cost_data, address_cost_data_list,
-		   data_index, data);
     }
 
-  bits = GET_MODE_BITSIZE (address_mode);
-  mask = ~(~(unsigned HOST_WIDE_INT) 0 << (bits - 1) << 1);
-  offset &= mask;
-  if ((offset >> (bits - 1) & 1))
-    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
-	      && data->min_offset <= s_offset
-	      && s_offset <= data->max_offset);
-  ratio_p = (ratio != 1
-	     && multiplier_allowed_in_address_p (ratio, mem_mode, as));
-
-  if (ratio != 1 && !ratio_p)
-    cost += multiply_by_cost (ratio, address_mode, speed);
-
-  if (s_offset && !offset_p && !symbol_present)
-    cost += add_cost (address_mode, speed);
-
-  if (may_autoinc)
-    *may_autoinc = autoinc;
-  acost = data->costs[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);
+  return new_cost (cost, complexity);
 }
 
  /* Calculate the SPEED or size cost of shiftadd EXPR in MODE.  MULT is the
@@ -4196,7 +4048,7 @@ get_computation_cost_at (struct ivopts_d
 					TYPE_MODE (TREE_TYPE (utype)),
 					TYPE_ADDR_SPACE (TREE_TYPE (utype)),
 					speed, stmt_is_after_inc,
-					can_autoinc));
+					can_autoinc, data));
 
   /* Otherwise estimate the costs for computing the expression.  */
   if (!symbol_present && !var_present && !offset)
@@ -4212,11 +4064,6 @@ get_computation_cost_at (struct ivopts_d
     cost.cost += adjust_setup_cost (data,
 				    add_cost (TYPE_MODE (ctype), speed));
 
-  /* Having offset does not affect runtime cost in case it is added to
-     symbol, but it increases complexity.  */
-  if (offset)
-    cost.complexity++;
-
   cost.cost += add_cost (TYPE_MODE (ctype), speed);
 
   aratio = ratio > 0 ? ratio : -ratio;
@@ -4299,7 +4146,7 @@ determine_use_iv_cost_address (struct iv
 			       struct iv_use *use, struct iv_cand *cand)
 {
   bitmap depends_on;
-  bool can_autoinc;
+  bool can_autoinc = (cand->ainc_use == use);
   int inv_expr_id = -1;
   comp_cost cost = get_computation_cost (data, use, cand, true, &depends_on,
 					 &can_autoinc, &inv_expr_id);
@@ -4899,7 +4746,7 @@ autoinc_possible_for_pair (struct ivopts
 			   struct iv_cand *cand)
 {
   bitmap depends_on;
-  bool can_autoinc;
+  bool can_autoinc = true;
   comp_cost cost;
 
   if (use->type != USE_ADDRESS)
