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

comparison gcc/tree-ssa-loop-ivopts.c @ 55:77e2b8dfacca gcc-4.4.5

update it from 4.4.3 to 4.5.0

author	ryoma <e075725@ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 23:39:51 +0900
parents	a06113de4d67
children	b7f97abdc517

comparison

equal deleted inserted replaced

-:c156f1bd5cd9
+:77e2b8dfacca
 /* Induction variable optimizations.
 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
 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
 Free Software Foundation; either version 3, or (at your option) any
 later version.
 GCC is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
 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 tries to find the optimal set of induction variables for the loop.
 All the costs are defined in a machine-specific way, using the target
 hooks and machine descriptions to determine them.
 4) The trees are transformed to use the new variables, the dead code is
 removed.
 All of this is done loop by loop.  Doing it globally is theoretically
 possible, it might give a better performance and it might enable us
 to decide costs more precisely, but getting all the interactions right
 would be complicated.  */
 };
 /* 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
 			   complex expressions and addressing modes).  */
 } comp_cost;
 /* The position where the iv is computed.  */
 enum iv_position
 {
 IP_NORMAL,		/* At the end, just before the exit condition.  */
 IP_END,		/* At the end of the latch block.  */
+IP_BEFORE_USE,	/* Immediately before a specific use.  */
+IP_AFTER_USE,		/* Immediately after a specific use.  */
 IP_ORIGINAL		/* The original biv.  */
 };
 /* The induction variable candidate.  */
 struct iv_cand
 struct iv *iv;	/* The value of the candidate.  NULL for
 			   "pseudocandidate" used to indicate the possibility
 			   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_{BEFORE,AFTER}_USE candidates, the place
+			      where it is incremented.  */
 bitmap depends_on;	/* The list of invariants that are used in step of the
 			   biv.  */
 };
 /* The data used by the induction variable optimizations.  */
 {
 case IP_NORMAL:
 fprintf (file, "  incremented before exit test\n");
 break;
+case IP_BEFORE_USE:
+fprintf (file, "  incremented before use %d\n", cand->ainc_use->id);
+break;
+case IP_AFTER_USE:
+fprintf (file, "  incremented after use %d\n", cand->ainc_use->id);
+break;
 case IP_END:
 fprintf (file, "  incremented at end\n");
 break;
 case IP_ORIGINAL:
 return stmt == last_stmt (bb);
 }
 /* Returns true if STMT if after the place where the original induction
-variable CAND is incremented.  */
+variable CAND is incremented.  If TRUE_IF_EQUAL is set, we return true
+if the positions are identical.  */
 static bool
-stmt_after_ip_original_pos (struct iv_cand *cand, gimple stmt)
+stmt_after_inc_pos (struct iv_cand *cand, gimple stmt, bool true_if_equal)
 {
 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;
 if (stmt_bb != cand_bb)
 return true;
-/* Scan the block from the end, since the original ivs are usually
+if (true_if_equal
-incremented at the end of the loop body.  */
+&& gimple_uid (stmt) == gimple_uid (cand->incremented_at))
-for (bsi = gsi_last_bb (stmt_bb); ; gsi_prev (&bsi))
+return true;
-{
+return gimple_uid (stmt) > gimple_uid (cand->incremented_at);
-if (gsi_stmt (bsi) == cand->incremented_at)
-	return false;
-if (gsi_stmt (bsi) == stmt)
-	return true;
-}
 }
 /* Returns true if STMT if after the place where the induction variable
 CAND is incremented in LOOP.  */
 case IP_NORMAL:
 return stmt_after_ip_normal_pos (loop, stmt);
 case IP_ORIGINAL:
-return stmt_after_ip_original_pos (cand, stmt);
+case IP_AFTER_USE:
+return stmt_after_inc_pos (cand, stmt, false);
+case IP_BEFORE_USE:
+return stmt_after_inc_pos (cand, stmt, true);
 default:
 gcc_unreachable ();
 }
 }
 	{
 	  fprintf (dump_file, "  number of iterations ");
 	  print_generic_expr (dump_file, niter, TDF_SLIM);
 	  fprintf (dump_file, "\n\n");
 	};
 fprintf (dump_file, "Induction variables:\n\n");
 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
 	{
 	  if (ver_info (data, i)->iv)
 return NULL;
 iv = get_iv (data, op);
 if (!iv)
 return NULL;
 if (iv->have_use_for)
 {
 use = iv_use (data, iv->use_id);
 gcc_assert (use->type == USE_NONLINEAR_EXPR);
 if (base_align < GET_MODE_ALIGNMENT (mode)
 	  || bitpos % GET_MODE_ALIGNMENT (mode) != 0
 	  || bitpos % BITS_PER_UNIT != 0)
 	return true;
 if (!constant_multiple_of (step, al, &mul))
 	return true;
 }
 return false;
 	  find_interesting_uses_outside (data, e);
 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 	find_interesting_uses_stmt (data, gsi_stmt (bsi));
 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	find_interesting_uses_stmt (data, gsi_stmt (bsi));
+	if (!is_gimple_debug (gsi_stmt (bsi)))
+	  find_interesting_uses_stmt (data, gsi_stmt (bsi));
 }
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 bitmap_iterator bi;
 else
 	expr = fold_build2 (code, type, op0, op1);
 return fold_convert (orig_type, expr);
+case MULT_EXPR:
+op1 = TREE_OPERAND (expr, 1);
+if (!cst_and_fits_in_hwi (op1))
+	return orig_expr;
+op0 = TREE_OPERAND (expr, 0);
+op0 = strip_offset_1 (op0, false, false, &off0);
+if (op0 == TREE_OPERAND (expr, 0))
+	return orig_expr;
+*offset = off0 * int_cst_value (op1);
+if (integer_zerop (op0))
+	expr = op0;
+else
+	expr = fold_build2 (MULT_EXPR, type, op0, op1);
+return fold_convert (orig_type, expr);
 case ARRAY_REF:
 case ARRAY_RANGE_REF:
 if (!inside_addr)
 	return orig_expr;
 		 struct iv_use *use, gimple incremented_at)
 {
 unsigned i;
 struct iv_cand *cand = NULL;
 tree type, orig_type;
 if (base)
 {
 orig_type = TREE_TYPE (base);
 type = generic_type_for (orig_type);
 if (type != orig_type)
 cand = iv_cand (data, i);
 if (cand->pos != pos)
 	continue;
-if (cand->incremented_at != incremented_at)
+if (cand->incremented_at != incremented_at
+	  || ((pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+	      && cand->ainc_use != use))
 	continue;
 if (!cand->iv)
 	{
 	  if (!base && !step)
 	{
 	  fd_ivopts_data = data;
 	  walk_tree (&step, find_depends, &cand->depends_on, NULL);
 	}
+if (pos == IP_AFTER_USE || pos == IP_BEFORE_USE)
+	cand->ainc_use = use;
+else
+	cand->ainc_use = NULL;
 if (dump_file && (dump_flags & TDF_DETAILS))
 	dump_cand (dump_file, cand);
 }
 if (important && !cand->important)
 return true;
 return false;
 }
+/* If possible, adds autoincrement candidates BASE + STEP * i based on use USE.
+Important field is set to IMPORTANT.  */
+static void
+add_autoinc_candidates (struct ivopts_data *data, tree base, tree step,
+			bool important, struct iv_use *use)
+{
+basic_block use_bb = gimple_bb (use->stmt);
+enum machine_mode mem_mode;
+unsigned HOST_WIDE_INT cstepi;
+/* 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.  */
+if (use_bb->loop_father != data->current_loop
+|| !dominated_by_p (CDI_DOMINATORS, data->current_loop->latch, use_bb)
+|| stmt_could_throw_p (use->stmt)
+|| !cst_and_fits_in_hwi (step))
+return;
+cstepi = int_cst_value (step);
+mem_mode = TYPE_MODE (TREE_TYPE (*use->op_p));
+if ((HAVE_PRE_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+|| (HAVE_PRE_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+{
+enum tree_code code = MINUS_EXPR;
+tree new_base;
+tree new_step = step;
+if (POINTER_TYPE_P (TREE_TYPE (base)))
+	{
+	  new_step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
+	  code = POINTER_PLUS_EXPR;
+	}
+else
+	new_step = fold_convert (TREE_TYPE (base), new_step);
+new_base = fold_build2 (code, TREE_TYPE (base), base, new_step);
+add_candidate_1 (data, new_base, step, important, IP_BEFORE_USE, use,
+		       use->stmt);
+}
+if ((HAVE_POST_INCREMENT && GET_MODE_SIZE (mem_mode) == cstepi)
+|| (HAVE_POST_DECREMENT && GET_MODE_SIZE (mem_mode) == -cstepi))
+{
+add_candidate_1 (data, base, step, important, IP_AFTER_USE, use,
+		       use->stmt);
+}
+}
 /* Adds a candidate BASE + STEP * i.  Important field is set to IMPORTANT and
 position to POS.  If USE is not NULL, the candidate is set as related to
 it.  The candidate computation is scheduled on all available positions.  */
 static void
 add_candidate (struct ivopts_data *data,
 	       tree base, tree step, bool important, struct iv_use *use)
 {
 if (ip_normal_pos (data->current_loop))
 add_candidate_1 (data, base, step, important, IP_NORMAL, use, NULL);
 if (ip_end_pos (data->current_loop)
 && allow_ip_end_pos_p (data->current_loop))
 add_candidate_1 (data, base, step, important, IP_END, use, NULL);
+if (use != NULL && use->type == USE_ADDRESS)
+add_autoinc_candidates (data, base, step, important, use);
 }
 /* Add a standard "0 + 1 * iteration" iv candidate for a
 type with SIZE bits.  */
 /* Add important candidates to the related_cands bitmaps.  */
 for (i = 0; i < n_iv_uses (data); i++)
 	bitmap_ior_into (iv_use (data, i)->related_cands,
 			 data->important_candidates);
 }
-}
-/* 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.  */
 return cost.cost == INFTY;
 }
 /* Sets cost of (USE, CANDIDATE) pair to COST and record that it depends
 on invariants DEPENDS_ON and that the value used in expressing it
-is VALUE.*/
+is VALUE.  */
 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)
 if (!ret->cand)
 	return NULL;
 return ret;
 }
 /* n_map_members is a power of two, so this computes modulo.  */
 s = cand->id & (use->n_map_members - 1);
 for (i = s; i < use->n_map_members; i++)
 if (use->cost_map[i].cand == cand)
 return use->cost_map + i;
 /* Produce DECL_RTL for object obj so it looks like it is stored in memory.  */
 static rtx
 produce_memory_decl_rtl (tree obj, int *regno)
 {
+addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (obj));
+enum machine_mode address_mode = targetm.addr_space.address_mode (as);
 rtx x;
 gcc_assert (obj);
 if (TREE_STATIC (obj) || DECL_EXTERNAL (obj))
 {
 const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj));
-x = gen_rtx_SYMBOL_REF (Pmode, name);
+x = gen_rtx_SYMBOL_REF (address_mode, name);
 SET_SYMBOL_REF_DECL (x, obj);
 x = gen_rtx_MEM (DECL_MODE (obj), x);
+set_mem_addr_space (x, as);
 targetm.encode_section_info (obj, x, true);
 }
 else
 {
-x = gen_raw_REG (Pmode, (*regno)++);
+x = gen_raw_REG (address_mode, (*regno)++);
 x = gen_rtx_MEM (DECL_MODE (obj), x);
+set_mem_addr_space (x, as);
 }
 return x;
 }
 default_rtl_profile ();
 cfun->function_frequency = real_frequency;
 cost = seq_cost (seq, speed);
 if (MEM_P (rslt))
-cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type), speed);
+cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type),
+			  TYPE_ADDR_SPACE (type), speed);
 return cost;
 }
 /* Returns variable containing the value of candidate CAND at statement AT.  */
 /* We need to shift the value if we are after the increment.  */
 if (stmt_after_increment (loop, cand, at))
 {
 aff_tree cstep_aff;
 if (common_type != uutype)
 	cstep_common = fold_convert (common_type, cstep);
 else
 	cstep_common = cstep;
 cost = seq_cost (seq, speed);
 if (!cost)
 cost = 1;
 costs[mode] = cost;
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "Addition in %s costs %d\n",
 	     GET_MODE_NAME (mode), cost);
 return cost;
 }
 start_sequence ();
 expand_mult (mode, gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
 	       gen_int_mode (cst, mode), NULL_RTX, 0);
 seq = get_insns ();
 end_sequence ();
 cost = seq_cost (seq, speed);
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "Multiplication by %d in %s costs %d\n",
 	     (int) cst, GET_MODE_NAME (mode), cost);
 return cost;
 }
 /* Returns true if multiplying by RATIO is allowed in an address.  Test the
-validity for a memory reference accessing memory of mode MODE.  */
+validity for a memory reference accessing memory of mode MODE in
+address space AS.  */
+DEF_VEC_P (sbitmap);
+DEF_VEC_ALLOC_P (sbitmap, heap);
 bool
-multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode)
+multiplier_allowed_in_address_p (HOST_WIDE_INT ratio, enum machine_mode mode,
+				 addr_space_t as)
 {
 #define MAX_RATIO 128
-static sbitmap valid_mult[MAX_MACHINE_MODE];
+unsigned int data_index = (int) as * MAX_MACHINE_MODE + (int) mode;
+static VEC (sbitmap, heap) *valid_mult_list;
-if (!valid_mult[mode])
+sbitmap valid_mult;
-{
-rtx reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+if (data_index >= VEC_length (sbitmap, valid_mult_list))
+VEC_safe_grow_cleared (sbitmap, heap, valid_mult_list, data_index + 1);
+valid_mult = VEC_index (sbitmap, valid_mult_list, data_index);
+if (!valid_mult)
+{
+enum machine_mode address_mode = targetm.addr_space.address_mode (as);
+rtx reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
 rtx addr;
 HOST_WIDE_INT i;
-valid_mult[mode] = sbitmap_alloc (2 * MAX_RATIO + 1);
+valid_mult = sbitmap_alloc (2 * MAX_RATIO + 1);
-sbitmap_zero (valid_mult[mode]);
+sbitmap_zero (valid_mult);
-addr = gen_rtx_fmt_ee (MULT, Pmode, reg1, NULL_RTX);
+addr = gen_rtx_fmt_ee (MULT, address_mode, reg1, NULL_RTX);
 for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
 	{
-	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
+	  XEXP (addr, 1) = gen_int_mode (i, address_mode);
-	  if (memory_address_p (mode, addr))
+	  if (memory_address_addr_space_p (mode, addr, as))
-	    SET_BIT (valid_mult[mode], i + MAX_RATIO);
+	    SET_BIT (valid_mult, i + MAX_RATIO);
 	}
 if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "  allowed multipliers:");
 	  for (i = -MAX_RATIO; i <= MAX_RATIO; i++)
-	    if (TEST_BIT (valid_mult[mode], i + MAX_RATIO))
+	    if (TEST_BIT (valid_mult, i + MAX_RATIO))
 	      fprintf (dump_file, " %d", (int) i);
 	  fprintf (dump_file, "\n");
 	  fprintf (dump_file, "\n");
 	}
+VEC_replace (sbitmap, valid_mult_list, data_index, valid_mult);
 }
 if (ratio > MAX_RATIO || ratio < -MAX_RATIO)
 return false;
-return TEST_BIT (valid_mult[mode], ratio + MAX_RATIO);
+return TEST_BIT (valid_mult, ratio + MAX_RATIO);
 }
 /* Returns cost of address in shape symbol + var + OFFSET + RATIO * index.
 If SYMBOL_PRESENT is false, symbol is omitted.  If VAR_PRESENT is false,
 variable is omitted.  Compute the cost for a memory reference that accesses
-a memory location of mode MEM_MODE.
+a memory location of mode MEM_MODE in address space AS.
+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.  */
+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);
 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,
+		  HOST_WIDE_INT cstep, enum machine_mode mem_mode,
-		  bool speed)
+		  addr_space_t as, 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];
+enum machine_mode address_mode = targetm.addr_space.address_mode (as);
-static HOST_WIDE_INT min_offset[MAX_MACHINE_MODE], max_offset[MAX_MACHINE_MODE];
+static VEC(address_cost_data, heap) *address_cost_data_list;
-static unsigned costs[MAX_MACHINE_MODE][2][2][2][2];
+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;
+bool offset_p, ratio_p, autoinc;
-HOST_WIDE_INT s_offset;
+HOST_WIDE_INT s_offset, autoinc_offset, msize;
 unsigned HOST_WIDE_INT mask;
 unsigned bits;
-if (!initialized[mem_mode])
+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 start = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
+HOST_WIDE_INT rat, off;
 int old_cse_not_expected;
 unsigned sym_p, var_p, off_p, rat_p, add_c;
 rtx seq, addr, base;
 rtx reg0, reg1;
-initialized[mem_mode] = true;
+data = (address_cost_data) xcalloc (1, sizeof (*data));
-reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-addr = gen_rtx_fmt_ee (PLUS, Pmode, reg1, NULL_RTX);
+addr = gen_rtx_fmt_ee (PLUS, address_mode, reg1, NULL_RTX);
 for (i = start; i <= 1 << 20; i <<= 1)
 	{
-	  XEXP (addr, 1) = gen_int_mode (i, Pmode);
+	  XEXP (addr, 1) = gen_int_mode (i, address_mode);
-	  if (!memory_address_p (mem_mode, addr))
+	  if (!memory_address_addr_space_p (mem_mode, addr, as))
 	    break;
 	}
-max_offset[mem_mode] = i == start ? 0 : i >> 1;
+data->max_offset = i == start ? 0 : i >> 1;
-off[mem_mode] = max_offset[mem_mode];
+off = data->max_offset;
 for (i = start; i <= 1 << 20; i <<= 1)
 	{
-	  XEXP (addr, 1) = gen_int_mode (-i, Pmode);
+	  XEXP (addr, 1) = gen_int_mode (-i, address_mode);
-	  if (!memory_address_p (mem_mode, addr))
+	  if (!memory_address_addr_space_p (mem_mode, addr, as))
 	    break;
 	}
-min_offset[mem_mode] = i == start ? 0 : -(i >> 1);
+data->min_offset = i == start ? 0 : -(i >> 1);
 if (dump_file && (dump_flags & TDF_DETAILS))
 	{
 	  fprintf (dump_file, "get_address_cost:\n");
 	  fprintf (dump_file, "  min offset %s %d\n",
 		   GET_MODE_NAME (mem_mode),
-		   (int) min_offset[mem_mode]);
+		   (int) data->min_offset);
 	  fprintf (dump_file, "  max offset %s %d\n",
 		   GET_MODE_NAME (mem_mode),
-		   (int) max_offset[mem_mode]);
+		   (int) data->max_offset);
 	}
-rat[mem_mode] = 1;
+rat = 1;
 for (i = 2; i <= MAX_RATIO; i++)
-	if (multiplier_allowed_in_address_p (i, mem_mode))
+	if (multiplier_allowed_in_address_p (i, mem_mode, as))
 	  {
-	    rat[mem_mode] = i;
+	    rat = i;
 	    break;
 	  }
 /* Compute the cost of various addressing modes.  */
 acost = 0;
-reg0 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 1);
+reg0 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 1);
-reg1 = gen_raw_REG (Pmode, LAST_VIRTUAL_REGISTER + 2);
+reg1 = gen_raw_REG (address_mode, LAST_VIRTUAL_REGISTER + 2);
+if (HAVE_PRE_DECREMENT)
+	{
+	  addr = gen_rtx_PRE_DEC (address_mode, reg0);
+	  has_predec[mem_mode]
+	    = memory_address_addr_space_p (mem_mode, addr, as);
+	}
+if (HAVE_POST_DECREMENT)
+	{
+	  addr = gen_rtx_POST_DEC (address_mode, reg0);
+	  has_postdec[mem_mode]
+	    = memory_address_addr_space_p (mem_mode, addr, as);
+	}
+if (HAVE_PRE_INCREMENT)
+	{
+	  addr = gen_rtx_PRE_INC (address_mode, reg0);
+	  has_preinc[mem_mode]
+	    = memory_address_addr_space_p (mem_mode, addr, as);
+	}
+if (HAVE_POST_INCREMENT)
+	{
+	  addr = gen_rtx_POST_INC (address_mode, reg0);
+	  has_postinc[mem_mode]
+	    = memory_address_addr_space_p (mem_mode, addr, as);
+	}
 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;
 	  addr = reg0;
 	  if (rat_p)
-	    addr = gen_rtx_fmt_ee (MULT, Pmode, addr,
+	    addr = gen_rtx_fmt_ee (MULT, address_mode, addr,
-				   gen_int_mode (rat[mem_mode], Pmode));
+				   gen_int_mode (rat, address_mode));
 	  if (var_p)
-	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, reg1);
+	    addr = gen_rtx_fmt_ee (PLUS, address_mode, addr, reg1);
 	  if (sym_p)
 	    {
-	      base = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (""));
+	      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, Pmode,
+		base = gen_rtx_fmt_e (CONST, address_mode,
-				      gen_rtx_fmt_ee (PLUS, Pmode,
+				      gen_rtx_fmt_ee
-						      base,
+					(PLUS, address_mode, base,
-						      gen_int_mode (off[mem_mode],
+					 gen_int_mode (off, address_mode)));
-								    Pmode)));
 	    }
 	  else if (off_p)
-	    base = gen_int_mode (off[mem_mode], Pmode);
+	    base = gen_int_mode (off, address_mode);
 	  else
 	    base = NULL_RTX;
 	  if (base)
-	    addr = gen_rtx_fmt_ee (PLUS, Pmode, addr, 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 (mem_mode, addr);
+	  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, speed);
+	  acost += address_cost (addr, mem_mode, as, speed);
 	  if (!acost)
 	    acost = 1;
-	  costs[mem_mode][sym_p][var_p][off_p][rat_p] = acost;
+	  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
 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 (Pmode, speed);
+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 = costs[mem_mode][0][1][off_p][rat_p] + 1;
+	  acost = data->costs[0][1][off_p][rat_p] + 1;
 	  if (var_p)
 	    acost += add_c;
-	  if (acost < costs[mem_mode][1][var_p][off_p][rat_p])
+	  if (acost < data->costs[1][var_p][off_p][rat_p])
-	    costs[mem_mode][1][var_p][off_p][rat_p] = acost;
+	    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++)
 	    {
 	      sym_p = i & 1;
 	      var_p = (i >> 1) & 1;
 	      off_p = (i >> 2) & 1;
 	      if (off_p)
 		fprintf (dump_file, "cst + ");
 	      if (rat_p)
 		fprintf (dump_file, "rat * ");
-	      acost = costs[mem_mode][sym_p][var_p][off_p][rat_p];
+	      acost = data->costs[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");
 	}
-}
+VEC_replace (address_cost_data, address_cost_data_list,
-bits = GET_MODE_BITSIZE (Pmode);
+		   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
-	      && min_offset[mem_mode] <= s_offset
+	      && data->min_offset <= s_offset
-	      && s_offset <= max_offset[mem_mode]);
+	      && s_offset <= data->max_offset);
 ratio_p = (ratio != 1
-	     && multiplier_allowed_in_address_p (ratio, mem_mode));
+	     && multiplier_allowed_in_address_p (ratio, mem_mode, as));
 if (ratio != 1 && !ratio_p)
-cost += multiply_by_cost (ratio, Pmode, speed);
+cost += multiply_by_cost (ratio, address_mode, speed);
 if (s_offset && !offset_p && !symbol_present)
-cost += add_cost (Pmode, speed);
+cost += add_cost (address_mode, speed);
-acost = costs[mem_mode][symbol_present][var_present][offset_p][ratio_p];
+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);
 }
 /* Estimates cost of forcing expression EXPR into a variable.  */
 else
 	cost1 = force_expr_to_var_cost (op1, speed);
 break;
+case NEGATE_EXPR:
+op0 = TREE_OPERAND (expr, 0);
+STRIP_NOPS (op0);
+op1 = NULL_TREE;
+if (is_gimple_val (op0))
+	cost0 = zero_cost;
+else
+	cost0 = force_expr_to_var_cost (op0, speed);
+cost1 = zero_cost;
+break;
 default:
 /* Just an arbitrary value, FIXME.  */
 return new_cost (target_spill_cost[speed], 0);
 }
 switch (TREE_CODE (expr))
 {
 case POINTER_PLUS_EXPR:
 case PLUS_EXPR:
 case MINUS_EXPR:
+case NEGATE_EXPR:
 cost = new_cost (add_cost (mode, speed), 0);
 break;
 case MULT_EXPR:
 if (cst_and_fits_in_hwi (op0))
 	cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
 else if (cst_and_fits_in_hwi (op1))
 	cost = new_cost (multiply_by_cost (int_cst_value (op1), mode, speed), 0);
 else
 	return new_cost (target_spill_cost [speed], 0);
 break;
 /* Bound the cost by target_spill_cost.  The parts of complicated
 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;
 }
 HOST_WIDE_INT bitsize;
 HOST_WIDE_INT bitpos;
 tree toffset;
 enum machine_mode mode;
 int unsignedp, volatilep;
 core = get_inner_reference (addr, &bitsize, &bitpos, &toffset, &mode,
 			      &unsignedp, &volatilep, false);
 if (toffset != 0
 || bitpos % BITS_PER_UNIT != 0
 {
 *symbol_present = true;
 *var_present = false;
 return zero_cost;
 }
 *symbol_present = false;
 *var_present = true;
 return zero_cost;
 }
 ptr_difference_cost (struct ivopts_data *data,
 		     tree e1, tree e2, bool *symbol_present, bool *var_present,
 		     unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
 {
 HOST_WIDE_INT diff = 0;
-comp_cost cost;
+aff_tree aff_e1, aff_e2;
-bool speed = optimize_loop_for_speed_p (data->current_loop);
+tree type;
 gcc_assert (TREE_CODE (e1) == ADDR_EXPR);
 if (ptr_difference_const (e1, e2, &diff))
 {
 return split_address_cost (data, TREE_OPERAND (e1, 0),
 			       symbol_present, var_present, offset, depends_on);
 *symbol_present = false;
 *var_present = true;
-cost = force_var_cost (data, e1, depends_on);
+type = signed_type_for (TREE_TYPE (e1));
-cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+tree_to_aff_combination (e1, type, &aff_e1);
-cost.cost += add_cost (Pmode, speed);
+tree_to_aff_combination (e2, type, &aff_e2);
+aff_combination_scale (&aff_e2, double_int_minus_one);
-return cost;
+aff_combination_add (&aff_e1, &aff_e2);
+return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
 }
 /* Estimates cost of expressing difference E1 - E2 as
 var + symbol + offset.  The value of offset is added to OFFSET,
 SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding
 static comp_cost
 difference_cost (struct ivopts_data *data,
 		 tree e1, tree e2, bool *symbol_present, bool *var_present,
 		 unsigned HOST_WIDE_INT *offset, bitmap *depends_on)
 {
-comp_cost cost;
 enum machine_mode mode = TYPE_MODE (TREE_TYPE (e1));
 unsigned HOST_WIDE_INT off1, off2;
+aff_tree aff_e1, aff_e2;
+tree type;
 e1 = strip_offset (e1, &off1);
 e2 = strip_offset (e2, &off2);
 *offset += off1 - off2;
 STRIP_NOPS (e1);
 STRIP_NOPS (e2);
 if (TREE_CODE (e1) == ADDR_EXPR)
-return ptr_difference_cost (data, e1, e2, symbol_present, var_present, offset,
+return ptr_difference_cost (data, e1, e2, symbol_present, var_present,
-				depends_on);
+				offset, depends_on);
 *symbol_present = false;
 if (operand_equal_p (e1, e2, 0))
 {
 *var_present = false;
 return zero_cost;
 }
 *var_present = true;
 if (integer_zerop (e2))
 return force_var_cost (data, e1, depends_on);
 if (integer_zerop (e1))
 {
-cost = force_var_cost (data, e2, depends_on);
+comp_cost cost = force_var_cost (data, e2, depends_on);
 cost.cost += multiply_by_cost (-1, mode, data->speed);
 return cost;
 }
-cost = force_var_cost (data, e1, depends_on);
+type = signed_type_for (TREE_TYPE (e1));
-cost = add_costs (cost, force_var_cost (data, e2, depends_on));
+tree_to_aff_combination (e1, type, &aff_e1);
-cost.cost += add_cost (mode, data->speed);
+tree_to_aff_combination (e2, type, &aff_e2);
+aff_combination_scale (&aff_e2, double_int_minus_one);
-return cost;
+aff_combination_add (&aff_e1, &aff_e2);
+return force_var_cost (data, aff_combination_to_tree (&aff_e1), depends_on);
 }
 /* Determines the cost of the computation by that USE is expressed
 from induction variable CAND.  If ADDRESS_P is true, we just need
 to create an address from it, otherwise we want to get it into
 register.  A set of invariants we depend on is stored in
-DEPENDS_ON.  AT is the statement at that the value is computed.  */
+DEPENDS_ON.  AT is the statement at that the value is computed.
+If CAN_AUTOINC is nonnull, use it to record whether autoinc
+addressing is likely.  */
 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;
 bool speed = optimize_bb_for_speed_p (gimple_bb (at));
 *depends_on = NULL;
 	  && cand->iv->base_object
 	  && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
 	return infinite_cost;
 }
-if (TYPE_PRECISION (utype) != TYPE_PRECISION (ctype))
+if (TYPE_PRECISION (utype) < TYPE_PRECISION (ctype))
 {
 /* TODO -- add direct handling of this case.  */
 goto fallback;
 }
 else
 cstepi = 0;
 if (!constant_multiple_of (ustep, cstep, &rat))
 return infinite_cost;
 if (double_int_fits_in_shwi_p (rat))
 ratio = double_int_to_shwi (rat);
 else
 return infinite_cost;
+STRIP_NOPS (cbase);
+ctype = TREE_TYPE (cbase);
 /* use = ubase + ratio * (var - cbase).  If either cbase is a constant
 or ratio == 1, it is better to handle this like
 ubase - ratio * cbase + ratio * var
 (also holds in the case ratio == -1, TODO.  */
 if (cst_and_fits_in_hwi (cbase))
 {
 offset = - ratio * int_cst_value (cbase);
 cost = difference_cost (data,
 			      ubase, build_int_cst (utype, 0),
 			      &symbol_present, &var_present, &offset,
 			      depends_on);
 }
 else if (ratio == 1)
 {
+cost = difference_cost (data,
+			      ubase, cbase,
+			      &symbol_present, &var_present, &offset,
+			      depends_on);
+}
+else if (address_p
+	   && !POINTER_TYPE_P (ctype)
+	   && multiplier_allowed_in_address_p
+		(ratio, TYPE_MODE (TREE_TYPE (utype)),
+			TYPE_ADDR_SPACE (TREE_TYPE (utype))))
+{
+cbase
+	= fold_build2 (MULT_EXPR, ctype, cbase, build_int_cst (ctype, ratio));
 cost = difference_cost (data,
 			      ubase, cbase,
 			      &symbol_present, &var_present, &offset,
 			      depends_on);
 }
 					 &offset, depends_on));
 }
 /* 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,
+(symbol/var1/const parts may be omitted).  If we are looking for an
-find the cost of addressing this.  */
+address, find the cost of addressing this.  */
 if (address_p)
-return add_costs (cost, get_address_cost (symbol_present, var_present,
+return add_costs (cost,
-				offset, ratio,
+		      get_address_cost (symbol_present, var_present,
-				TYPE_MODE (TREE_TYPE (*use->op_p)), speed));
+					offset, ratio, cstepi,
+					TYPE_MODE (TREE_TYPE (utype)),
+					TYPE_ADDR_SPACE (TREE_TYPE (utype)),
+					speed, stmt_is_after_inc,
+					can_autoinc));
 /* Otherwise estimate the costs for computing the expression.  */
-aratio = ratio > 0 ? ratio : -ratio;
 if (!symbol_present && !var_present && !offset)
 {
 if (ratio != 1)
 	cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
 return cost;
 }
-if (aratio != 1)
+/* Symbol + offset should be compile-time computable so consider that they
-cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
+are added once to the variable, if present.  */
+if (var_present && (symbol_present || offset))
-n_sums = 1;
+cost.cost += add_cost (TYPE_MODE (ctype), speed)
-if (var_present
+		 / AVG_LOOP_NITER (data->current_loop);
-/* Symbol + offset should be compile-time computable.  */
-&& (symbol_present || offset))
-n_sums++;
 /* Having offset does not affect runtime cost in case it is added to
 symbol, but it increases complexity.  */
 if (offset)
 cost.complexity++;
-cost.cost += n_sums * add_cost (TYPE_MODE (ctype), speed);
+cost.cost += add_cost (TYPE_MODE (ctype), speed);
-return cost;
+aratio = ratio > 0 ? ratio : -ratio;
+if (aratio != 1)
+cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
 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);
 if (!comp)
 /* Determines the cost of the computation by that USE is expressed
 from induction variable CAND.  If ADDRESS_P is true, we just need
 to create an address from it, otherwise we want to get it into
 register.  A set of invariants we depend on is stored in
-DEPENDS_ON.  */
+DEPENDS_ON.  If CAN_AUTOINC is nonnull, use it to record whether
+autoinc addressing is likely.  */
 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
 expression.  */
 {
 set_use_iv_cost (data, use, cand, zero_cost, NULL, NULL_TREE);
 return true;
 }
-cost = get_computation_cost (data, use, cand, false, &depends_on);
+cost = get_computation_cost (data, use, cand, false, &depends_on, NULL);
 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
 return !infinite_cost_p (cost);
 }
 static bool
 determine_use_iv_cost_address (struct ivopts_data *data,
 			       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);
+if (cand->ainc_use == use)
+{
+if (can_autoinc)
+	cost.cost -= cand->cost_step;
+/* If we generated the candidate solely for exploiting autoincrement
+	 opportunities, and it turns out it can't be used, set the cost to
+	 infinity to make sure we ignore it.  */
+else if (cand->pos == IP_AFTER_USE || cand->pos == IP_BEFORE_USE)
+	cost = infinite_cost;
+}
 set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE);
 return !infinite_cost_p (cost);
 }
 note that we cannot get rid of it.  */
 ok = extract_cond_operands (data, use->stmt, NULL, NULL, NULL, &cmp_iv);
 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);
 /* Choose the better approach, preferring the eliminated IV. */
 if (compare_costs (elim_cost, express_cost) <= 0)
 return determine_use_iv_cost_condition (data, use, cand);
 default:
 gcc_unreachable ();
 }
+}
+/* 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 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
+set_autoinc_for_original_candidates (struct ivopts_data *data)
+{
+unsigned i, j;
+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);
+set_autoinc_for_original_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
 The reason is to make debugging simpler; so this is not relevant for
 artificial ivs created by other optimization passes.  */
 if (cand->pos != IP_ORIGINAL
 || DECL_ARTIFICIAL (SSA_NAME_VAR (cand->var_before)))
 cost++;
 /* Prefer not to insert statements into latch unless there are some
 already (so that we do not create unnecessary jumps).  */
 if (cand->pos == IP_END
 && empty_block_p (ip_end_pos (data->current_loop)))
 cost++;
 cand->cost = cost;
+cand->cost_step = cost_step;
 }
 /* Determines costs of computation of the candidates.  */
 static void
 determine_iv_cost (data, cand);
 if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "  %d\t%d\n", i, cand->cost);
 }
 if (dump_file && (dump_flags & TDF_DETAILS))
 fprintf (dump_file, "\n");
 }
 /* Calculates cost for having SIZE induction variables.  */
 We set a reserve R (free regs that are used for temporary computations,
 etc.).  For now the reserve is a constant 3.
 Let I be the number of induction variables.
 -- if U + I + R <= A, the cost is I * SMALL_COST (just not to encourage
 	make a lot of ivs without a reason).
 -- if A - R < U + I <= A, the cost is I * PRES_COST
 -- if U + I > A, the cost is I * PRES_COST and
 number of uses * SPILL_COST * (U + I - A) / (U + I) is added.  */
 if (!new_cp)
 	continue;
 if (!iv_ca_has_deps (ivs, new_cp))
 	continue;
 if (!cheaper_cost_pair (new_cp, old_cp))
 	continue;
 *delta = iv_ca_delta_add (use, old_cp, new_cp, *delta);
 }
 	      cp = get_use_iv_cost (data, use, cnd);
 	      if (!cp)
 		continue;
 	      if (!iv_ca_has_deps (ivs, cp))
 		continue;
 	      if (!cheaper_cost_pair (cp, new_cp))
 		continue;
 	      new_cp = cp;
 	    }
 	      cp = get_use_iv_cost (data, use, cnd);
 	      if (!cp)
 		continue;
 	      if (!iv_ca_has_deps (ivs, cp))
 		continue;
 	      if (!cheaper_cost_pair (cp, new_cp))
 		continue;
 	      new_cp = cp;
 	    }
 	    continue;
 	  /* Already tried this.  */
 	  if (cand->important && cand->iv->base_object == NULL_TREE)
 	    continue;
 	  if (iv_ca_cand_used_p (ivs, cand))
 	    continue;
 	  act_delta = NULL;
 	  iv_ca_set_cp (data, ivs, use, cp);
 /* Try extending the set of induction variables by one.  */
 for (i = 0; i < n_iv_cands (data); i++)
 {
 cand = iv_cand (data, i);
 if (iv_ca_cand_used_p (ivs, cand))
 	continue;
 acost = iv_ca_extend (data, ivs, cand, &act_delta, &n_ivs);
 if (!act_delta)
 case IP_END:
 incr_pos = gsi_last_bb (ip_end_pos (data->current_loop));
 after = true;
 break;
+case IP_AFTER_USE:
+after = true;
+/* fall through */
+case IP_BEFORE_USE:
+incr_pos = gsi_for_stmt (cand->incremented_at);
+break;
 case IP_ORIGINAL:
 /* Mark that the iv is preserved.  */
 name_info (data, cand->var_before)->preserve_biv = true;
 name_info (data, cand->var_after)->preserve_biv = true;
 /* Rewrite the increment so that it uses var_before directly.  */
 find_interesting_uses_op (data, cand->var_after)->selected = cand;
 return;
 }
 gimple_add_tmp_var (cand->var_before);
 add_referenced_var (cand->var_before);
 base = unshare_expr (cand->iv->base);
 cand = iv_cand (data, i);
 create_new_iv (data, cand);
 }
 }
-/* Returns the phi-node in BB with result RESULT.  */
-static gimple
-get_phi_with_result (basic_block bb, tree result)
-{
-gimple_stmt_iterator i = gsi_start_phis (bb);
-for (; !gsi_end_p (i); gsi_next (&i))
-if (gimple_phi_result (gsi_stmt (i)) == result)
-return gsi_stmt (i);
-gcc_unreachable ();
-return NULL;
-}
-/* Removes statement STMT (real or a phi node).  If INCLUDING_DEFINED_NAME
-is true, remove also the ssa name defined by the statement.  */
-static void
-remove_statement (gimple stmt, bool including_defined_name)
-{
-if (gimple_code (stmt) == GIMPLE_PHI)
-{
-gimple bb_phi = get_phi_with_result (gimple_bb (stmt),
-					 gimple_phi_result (stmt));
-gimple_stmt_iterator bsi = gsi_for_stmt (bb_phi);
-remove_phi_node (&bsi, including_defined_name);
-}
-else
-{
-gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
-gsi_remove (&bsi, true);
-release_defs (stmt);
-}
-}
 /* Rewrites USE (definition of iv used in a nonlinear expression)
 using candidate CAND.  */
 static void
 if (gimple_code (use->stmt) == GIMPLE_PHI)
 {
 ass = gimple_build_assign (tgt, op);
 gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
-remove_statement (use->stmt, false);
+bsi = gsi_for_stmt (use->stmt);
+remove_phi_node (&bsi, false);
 }
 else
 {
 gimple_assign_set_rhs_from_tree (&bsi, op);
 use->stmt = gsi_stmt (bsi);
 for_each_index (&ref, idx_remove_ssa_names, NULL);
 return ref;
 }
-/* Extract the alias analysis info for the memory reference REF.  There are
-several ways how this information may be stored and what precisely is
-its semantics depending on the type of the reference, but there always is
-somewhere hidden one _DECL node that is used to determine the set of
-virtual operands for the reference.  The code below deciphers this jungle
-and extracts this single useful piece of information.  */
-static tree
-get_ref_tag (tree ref, tree orig)
-{
-tree var = get_base_address (ref);
-tree aref = NULL_TREE, tag, sv;
-HOST_WIDE_INT offset, size, maxsize;
-for (sv = orig; handled_component_p (sv); sv = TREE_OPERAND (sv, 0))
-{
-aref = get_ref_base_and_extent (sv, &offset, &size, &maxsize);
-if (ref)
-	break;
-}
-if (!var)
-return NULL_TREE;
-if (TREE_CODE (var) == INDIRECT_REF)
-{
-/* If the base is a dereference of a pointer, first check its name memory
-	 tag.  If it does not have one, use its symbol memory tag.  */
-var = TREE_OPERAND (var, 0);
-if (TREE_CODE (var) != SSA_NAME)
-	return NULL_TREE;
-if (SSA_NAME_PTR_INFO (var))
-	{
-	  tag = SSA_NAME_PTR_INFO (var)->name_mem_tag;
-	  if (tag)
-	    return tag;
-	}
-var = SSA_NAME_VAR (var);
-tag = symbol_mem_tag (var);
-gcc_assert (tag != NULL_TREE);
-return tag;
-}
-else
-{
-if (!DECL_P (var))
-	return NULL_TREE;
-tag = symbol_mem_tag (var);
-if (tag)
-	return tag;
-return var;
-}
-}
 /* Copies the reference information from OLD_REF to NEW_REF.  */
 static void
 copy_ref_info (tree new_ref, tree old_ref)
 {
 if (TREE_CODE (old_ref) == TARGET_MEM_REF)
 copy_mem_ref_info (new_ref, old_ref);
 else
-{
+TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
-TMR_ORIGINAL (new_ref) = unshare_and_remove_ssa_names (old_ref);
-TMR_TAG (new_ref) = get_ref_tag (old_ref, TMR_ORIGINAL (new_ref));
-}
 }
 /* Rewrites USE (address that is an iv) using candidate CAND.  */
 static void
 rewrite_use_address (struct ivopts_data *data,
 		     struct iv_use *use, struct iv_cand *cand)
 {
 aff_tree aff;
 gimple_stmt_iterator bsi = gsi_for_stmt (use->stmt);
+tree base_hint = NULL_TREE;
 tree ref;
 bool ok;
 ok = get_computation_aff (data->current_loop, use, cand, use->stmt, &aff);
 gcc_assert (ok);
 unshare_aff_combination (&aff);
-ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, data->speed);
+/* To avoid undefined overflow problems, all IV candidates use unsigned
+integer types.  The drawback is that this makes it impossible for
+create_mem_ref to distinguish an IV that is based on a memory object
+from one that represents simply an offset.
+To work around this problem, we pass a hint to create_mem_ref that
+indicates which variable (if any) in aff is an IV based on a memory
+object.  Note that we only consider the candidate.  If this is not
+based on an object, the base of the reference is in some subexpression
+of the use -- but these will use pointer types, so they are recognized
+by the create_mem_ref heuristics anyway.  */
+if (cand->iv->base_object)
+base_hint = var_at_stmt (data->current_loop, cand, use->stmt);
+ref = create_mem_ref (&bsi, TREE_TYPE (*use->op_p), &aff, base_hint,
+			data->speed);
 copy_ref_info (ref, *use->op_p);
 *use->op_p = ref;
 }
 /* Rewrites USE (the condition such that one of the arguments is an iv) using
 /* Rewrites USE using candidate CAND.  */
 static void
 rewrite_use (struct ivopts_data *data, struct iv_use *use, struct iv_cand *cand)
 {
-push_stmt_changes (&use->stmt);
 switch (use->type)
 {
 case USE_NONLINEAR_EXPR:
 	rewrite_use_nonlinear_expr (data, use, cand);
 	break;
 default:
 	gcc_unreachable ();
 }
-pop_stmt_changes (&use->stmt);
+update_stmt (use->stmt);
 }
 /* Rewrite the uses using the selected induction variables.  */
 static void
 static void
 remove_unused_ivs (struct ivopts_data *data)
 {
 unsigned j;
 bitmap_iterator bi;
+bitmap toremove = BITMAP_ALLOC (NULL);
+/* Figure out an order in which to release SSA DEFs so that we don't
+release something that we'd have to propagate into a debug stmt
+afterwards.  */
 EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, j, bi)
 {
 struct version_info *info;
 info = ver_info (data, j);
 if (info->iv
 	  && !integer_zerop (info->iv->step)
 	  && !info->inv_id
 	  && !info->iv->have_use_for
 	  && !info->preserve_biv)
-	remove_statement (SSA_NAME_DEF_STMT (info->iv->ssa_name), true);
+	bitmap_set_bit (toremove, SSA_NAME_VERSION (info->iv->ssa_name));
 }
+release_defs_bitset (toremove);
+BITMAP_FREE (toremove);
 }
 /* Frees data allocated by the optimization of a single loop.  */
 static void
 tree_ssa_iv_optimize_loop (struct ivopts_data *data, struct loop *loop)
 {
 bool changed = false;
 struct iv_ca *iv_ca;
 edge exit;
+basic_block *body;
 gcc_assert (!data->niters);
 data->current_loop = loop;
 data->speed = optimize_loop_for_speed_p (loop);
 if (dump_file && (dump_flags & TDF_DETAILS))
 {
 fprintf (dump_file, "Processing loop %d\n", loop->num);
 exit = single_dom_exit (loop);
 if (exit)
 	{
 	  fprintf (dump_file, "  single exit %d -> %d, exit condition ",
 		   exit->src->index, exit->dest->index);
 	}
 fprintf (dump_file, "\n");
 }
+body = get_loop_body (loop);
+renumber_gimple_stmt_uids_in_blocks (body, loop->num_nodes);
+free (body);
 /* For each ssa name determines whether it behaves as an induction variable
 in some loop.  */
 if (!find_induction_variables (data))
 goto finish;
 /* Finds candidates for the induction variables (item 2).  */
 find_iv_candidates (data);
 /* Calculates the costs (item 3, part 1).  */
+determine_iv_costs (data);
 determine_use_iv_costs (data);
-determine_iv_costs (data);
 determine_set_costs (data);
 /* Find the optimal set of induction variables (item 3, part 2).  */
 iv_ca = find_optimal_iv_set (data);
 if (!iv_ca)
 changed = true;
 /* Create the new induction variables (item 4, part 1).  */
 create_new_ivs (data, iv_ca);
 iv_ca_free (&iv_ca);
 /* Rewrite the uses (item 4, part 2).  */
 rewrite_uses (data);
 /* Remove the ivs that are unused after rewriting.  */
 remove_unused_ivs (data);

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-loop-ivopts.c @ 55:77e2b8dfacca gcc-4.4.5