double-int.c (double_int_multiple_of): New function.

2012-06-22  Bill Schmidt  <wschmidt@linux.ibm.com>

	* double-int.c (double_int_multiple_of): New function.
	* double-int.h (double_int_multiple_of): New decl.
	* tree-ssa-loop-ivopts.c (add_cost, zero_cost): Remove undefs.
	(mbc_entry_hash): New forward decl.
	(mbc_entry_eq): Likewise.
	(zero_cost): Change to no_cost.
	(mult_costs): New static var.
	(cost_tables_exist): Likewise.
	(initialize_costs): New function.
	(finalize_costs): Likewise.
	(tree_ssa_iv_optimize_init): Call initialize_costs.
	(add_cost): Change to add_regs_cost; distinguish costs by speed.
	(multiply_regs_cost): New function.
	(add_const_cost): Likewise.
	(extend_or_trunc_reg_cost): Likewise.
	(negate_reg_cost): Likewise.
	(multiply_by_cost): Change to multiply_by_const_cost; distinguish
	costs by speed.
	(get_address_cost): Change add_cost to add_regs_cost; change
	multiply_by_cost to multiply_by_const_cost.
	(force_expr_to_var_cost): Change zero_cost to no_cost; change
	add_cost to add_regs_cost; change multiply_by_cost to
	multiply_by_const_cost.
	(split_cost): Change zero_cost to no_cost.
	(ptr_difference_cost): Likewise.
	(difference_cost): Change zero_cost to no_cost; change multiply_by_cost
	to multiply_by_const_cost.
	(get_computation_cost_at): Change add_cost to add_regs_cost; change
	multiply_by_cost to multiply_by_const_cost.
	(determine_use_iv_cost_generic): Change zero_cost to no_cost.
	(determine_iv_cost): Change add_cost to add_regs_cost.
	(iv_ca_new): Change zero_cost to no_cost.
	(tree_ssa_iv_optimize_finalize): Call finalize_costs.
	* tree-ssa-address.c (most_expensive_mult_to_index): Change
	multiply_by_cost to multiply_by_const_cost.
	* tree-flow.h (multiply_by_cost): Change to multiply_by_const_cost.
	(add_regs_cost): New decl.
	(multiply_regs_cost): Likewise.
	(add_const_cost): Likewise.
	(extend_or_trunc_reg_cost): Likewise.
	(negate_reg_cost): Likewise.

From-SVN: r188891

1 files changed, 213 insertions, 42 deletions

diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index e5b1d0a1055..6c4f83746e4 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -89,12 +89,10 @@ along with GCC; see the file COPYING3.  If not see
 #include "target.h"
 #include "tree-inline.h"
 #include "tree-ssa-propagate.h"
-
-/* FIXME: add_cost and zero_cost defined in exprmed.h conflict with local uses.
- */
 #include "expmed.h"
-#undef add_cost
-#undef zero_cost
+
+static hashval_t mbc_entry_hash (const void *);
+static int mbc_entry_eq (const void*, const void *);
 
 /* FIXME: Expressions are expanded to RTL in this pass to determine the
    cost of different addressing modes.  This should be moved to a TBD
@@ -162,7 +160,7 @@ typedef struct
 			   complex expressions and addressing modes).  */
 } comp_cost;
 
-static const comp_cost zero_cost = {0, 0};
+static const comp_cost no_cost = {0, 0};
 static const comp_cost infinite_cost = {INFTY, INFTY};
 
 /* The candidate - cost pair.  */
@@ -386,6 +384,11 @@ struct iv_ca_delta
 
 static VEC(tree,heap) *decl_rtl_to_reset;
 
+/* Cached costs for multiplies by constants, and a flag to indicate
+   when they're valid.  */
+static htab_t mult_costs[2];
+static bool cost_tables_exist = false;
+
 static comp_cost force_expr_to_var_cost (tree, bool);
 
 /* Number of uses recorded in DATA.  */
@@ -851,6 +854,26 @@ htab_inv_expr_hash (const void *ent)
   return expr->hash;
 }
 
+/* Allocate data structures for the cost model.  */
+
+static void
+initialize_costs (void)
+{
+  mult_costs[0] = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
+  mult_costs[1] = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
+  cost_tables_exist = true;
+}
+
+/* Release data structures for the cost model.  */
+
+static void
+finalize_costs (void)
+{
+  cost_tables_exist = false;
+  htab_delete (mult_costs[0]);
+  htab_delete (mult_costs[1]);
+}
+
 /* Initializes data structures used by the iv optimization pass, stored
    in DATA.  */
 
@@ -869,6 +892,8 @@ tree_ssa_iv_optimize_init (struct ivopts_data *data)
                                     htab_inv_expr_eq, free);
   data->inv_expr_id = 0;
   decl_rtl_to_reset = VEC_alloc (tree, heap, 20);
+
+  initialize_costs ();
 }
 
 /* Returns a memory object to that EXPR points.  In case we are able to
@@ -3057,15 +3082,15 @@ adjust_setup_cost (struct ivopts_data *data, unsigned cost)
 
 /* Returns cost of addition in MODE.  */
 
-static unsigned
-add_cost (enum machine_mode mode, bool speed)
+unsigned
+add_regs_cost (enum machine_mode mode, bool speed)
 {
-  static unsigned costs[NUM_MACHINE_MODES];
+  static unsigned costs[NUM_MACHINE_MODES][2];
   rtx seq;
   unsigned cost;
 
-  if (costs[mode])
-    return costs[mode];
+  if (costs[mode][speed])
+    return costs[mode][speed];
 
   start_sequence ();
   force_operand (gen_rtx_fmt_ee (PLUS, mode,
@@ -3079,7 +3104,7 @@ add_cost (enum machine_mode mode, bool speed)
   if (!cost)
     cost = 1;
 
-  costs[mode] = cost;
+  costs[mode][speed] = cost;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "Addition in %s costs %d\n",
@@ -3087,6 +3112,148 @@ add_cost (enum machine_mode mode, bool speed)
   return cost;
 }
 
+/* Returns cost of multiplication in MODE.  */
+
+unsigned
+multiply_regs_cost (enum machine_mode mode, bool speed)
+{
+  static unsigned costs[NUM_MACHINE_MODES][2];
+  rtx seq;
+  unsigned cost;
+
+  if (costs[mode][speed])
+    return costs[mode][speed];
+
+  start_sequence ();
+  force_operand (gen_rtx_fmt_ee (MULT, mode,
+				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 2)),
+		 NULL_RTX);
+  seq = get_insns ();
+  end_sequence ();
+
+  cost = seq_cost (seq, speed);
+  if (!cost)
+    cost = 1;
+
+  costs[mode][speed] = cost;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Multiplication in %s costs %d\n",
+	     GET_MODE_NAME (mode), cost);
+  return cost;
+}
+
+/* Returns cost of addition with a constant in MODE.  */
+
+unsigned
+add_const_cost (enum machine_mode mode, bool speed)
+{
+  static unsigned costs[NUM_MACHINE_MODES][2];
+  rtx seq;
+  unsigned cost;
+
+  if (costs[mode][speed])
+    return costs[mode][speed];
+
+  /* Arbitrarily generate insns for x + 2, as the exact constant
+     shouldn't matter.  */
+  start_sequence ();
+  force_operand (gen_rtx_fmt_ee (PLUS, mode,
+				 gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1),
+				 gen_int_mode (2, mode)),
+		 NULL_RTX);
+  seq = get_insns ();
+  end_sequence ();
+
+  cost = seq_cost (seq, speed);
+  if (!cost)
+    cost = 1;
+
+  costs[mode][speed] = cost;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Addition to constant in %s costs %d\n",
+	     GET_MODE_NAME (mode), cost);
+  return cost;
+}
+
+/* Returns cost of extend or truncate in MODE.  */
+
+unsigned
+extend_or_trunc_reg_cost (tree type_to, tree type_from, bool speed)
+{
+  static unsigned costs[NUM_MACHINE_MODES][NUM_MACHINE_MODES][2];
+  rtx seq;
+  unsigned cost;
+  enum machine_mode mode_to = TYPE_MODE (type_to);
+  enum machine_mode mode_from = TYPE_MODE (type_from);
+  tree size_to = TYPE_SIZE (type_to);
+  tree size_from = TYPE_SIZE (type_from);
+  enum rtx_code code;
+
+  gcc_assert (TREE_CODE (size_to) == INTEGER_CST
+	      && TREE_CODE (size_from) == INTEGER_CST);
+
+  if (costs[mode_to][mode_from][speed])
+    return costs[mode_to][mode_from][speed];
+
+  if (tree_int_cst_lt (size_to, size_from))
+    code = TRUNCATE;
+  else if (TYPE_UNSIGNED (type_to))
+    code = ZERO_EXTEND;
+  else
+    code = SIGN_EXTEND;
+
+  start_sequence ();
+  gen_rtx_fmt_e (code, mode_to,
+		 gen_raw_REG (mode_from, LAST_VIRTUAL_REGISTER + 1));
+  seq = get_insns ();
+  end_sequence ();
+
+  cost = seq_cost (seq, speed);
+  if (!cost)
+    cost = 1;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Conversion from %s to %s costs %d\n",
+	     GET_MODE_NAME (mode_to), GET_MODE_NAME (mode_from), cost);
+
+  costs[mode_to][mode_from][speed] = cost;
+  return cost;
+}
+
+/* Returns cost of negation in MODE.  */
+
+unsigned
+negate_reg_cost (enum machine_mode mode, bool speed)
+{
+  static unsigned costs[NUM_MACHINE_MODES][2];
+  rtx seq;
+  unsigned cost;
+
+  if (costs[mode][speed])
+    return costs[mode][speed];
+
+  start_sequence ();
+  force_operand (gen_rtx_fmt_e (NEG, mode,
+				gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1)),
+		 NULL_RTX);
+  seq = get_insns ();
+  end_sequence ();
+
+  cost = seq_cost (seq, speed);
+  if (!cost)
+    cost = 1;
+
+  costs[mode][speed] = cost;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Negation in %s costs %d\n",
+	     GET_MODE_NAME (mode), cost);
+  return cost;
+}
+
 /* Entry in a hashtable of already known costs for multiplication.  */
 struct mbc_entry
 {
@@ -3120,19 +3287,19 @@ mbc_entry_eq (const void *entry1, const void *entry2)
 /* Returns cost of multiplication by constant CST in MODE.  */
 
 unsigned
-multiply_by_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
+multiply_by_const_cost (HOST_WIDE_INT cst, enum machine_mode mode, bool speed)
 {
-  static htab_t costs;
   struct mbc_entry **cached, act;
   rtx seq;
   unsigned cost;
 
-  if (!costs)
-    costs = htab_create (100, mbc_entry_hash, mbc_entry_eq, free);
+  gcc_assert (cost_tables_exist);
 
   act.mode = mode;
   act.cst = cst;
-  cached = (struct mbc_entry **) htab_find_slot (costs, &act, INSERT);
+  cached = (struct mbc_entry **)
+    htab_find_slot (mult_costs[speed], &act, INSERT);
+    
   if (*cached)
     return (*cached)->cost;
 
@@ -3418,7 +3585,7 @@ get_address_cost (bool symbol_present, bool var_present,
 	 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);
+      add_c = add_regs_cost (address_mode, speed);
       for (i = 0; i < 8; i++)
 	{
 	  var_p = i & 1;
@@ -3499,10 +3666,10 @@ get_address_cost (bool symbol_present, bool var_present,
 	     && multiplier_allowed_in_address_p (ratio, mem_mode, as));
 
   if (ratio != 1 && !ratio_p)
-    cost += multiply_by_cost (ratio, address_mode, speed);
+    cost += multiply_by_const_cost (ratio, address_mode, speed);
 
   if (s_offset && !offset_p && !symbol_present)
-    cost += add_cost (address_mode, speed);
+    cost += add_regs_cost (address_mode, speed);
 
   if (may_autoinc)
     *may_autoinc = autoinc;
@@ -3601,7 +3768,7 @@ force_expr_to_var_cost (tree expr, bool speed)
   STRIP_NOPS (expr);
 
   if (SSA_VAR_P (expr))
-    return zero_cost;
+    return no_cost;
 
   if (is_gimple_min_invariant (expr))
     {
@@ -3633,12 +3800,12 @@ force_expr_to_var_cost (tree expr, bool speed)
       STRIP_NOPS (op1);
 
       if (is_gimple_val (op0))
-	cost0 = zero_cost;
+	cost0 = no_cost;
       else
 	cost0 = force_expr_to_var_cost (op0, speed);
 
       if (is_gimple_val (op1))
-	cost1 = zero_cost;
+	cost1 = no_cost;
       else
 	cost1 = force_expr_to_var_cost (op1, speed);
 
@@ -3650,11 +3817,11 @@ force_expr_to_var_cost (tree expr, bool speed)
       op1 = NULL_TREE;
 
       if (is_gimple_val (op0))
-	cost0 = zero_cost;
+	cost0 = no_cost;
       else
 	cost0 = force_expr_to_var_cost (op0, speed);
 
-      cost1 = zero_cost;
+      cost1 = no_cost;
       break;
 
     default:
@@ -3669,7 +3836,7 @@ force_expr_to_var_cost (tree expr, bool speed)
     case PLUS_EXPR:
     case MINUS_EXPR:
     case NEGATE_EXPR:
-      cost = new_cost (add_cost (mode, speed), 0);
+      cost = new_cost (add_regs_cost (mode, speed), 0);
       if (TREE_CODE (expr) != NEGATE_EXPR)
         {
           tree mult = NULL_TREE;
@@ -3689,9 +3856,11 @@ force_expr_to_var_cost (tree expr, bool speed)
 
     case MULT_EXPR:
       if (cst_and_fits_in_hwi (op0))
-	cost = new_cost (multiply_by_cost (int_cst_value (op0), mode, speed), 0);
+	cost = new_cost (multiply_by_const_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);
+	cost = new_cost (multiply_by_const_cost (int_cst_value (op1),
+						 mode, speed), 0);
       else
 	return new_cost (target_spill_cost [speed], 0);
       break;
@@ -3766,12 +3935,12 @@ split_address_cost (struct ivopts_data *data,
     {
       *symbol_present = true;
       *var_present = false;
-      return zero_cost;
+      return no_cost;
     }
 
   *symbol_present = false;
   *var_present = true;
-  return zero_cost;
+  return no_cost;
 }
 
 /* Estimates cost of expressing difference of addresses E1 - E2 as
@@ -3796,7 +3965,7 @@ ptr_difference_cost (struct ivopts_data *data,
       *offset += diff;
       *symbol_present = false;
       *var_present = false;
-      return zero_cost;
+      return no_cost;
     }
 
   if (integer_zerop (e2))
@@ -3846,7 +4015,7 @@ difference_cost (struct ivopts_data *data,
   if (operand_equal_p (e1, e2, 0))
     {
       *var_present = false;
-      return zero_cost;
+      return no_cost;
     }
 
   *var_present = true;
@@ -3857,7 +4026,7 @@ difference_cost (struct ivopts_data *data,
   if (integer_zerop (e1))
     {
       comp_cost cost = force_var_cost (data, e2, depends_on);
-      cost.cost += multiply_by_cost (-1, mode, data->speed);
+      cost.cost += multiply_by_const_cost (-1, mode, data->speed);
       return cost;
     }
 
@@ -4168,7 +4337,7 @@ get_computation_cost_at (struct ivopts_data *data,
 					 &symbol_present, &var_present,
 					 &offset, depends_on));
       cost.cost /= avg_loop_niter (data->current_loop);
-      cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
+      cost.cost += add_regs_cost (TYPE_MODE (ctype), data->speed);
     }
 
   if (inv_expr_id)
@@ -4201,7 +4370,7 @@ get_computation_cost_at (struct ivopts_data *data,
   if (!symbol_present && !var_present && !offset)
     {
       if (ratio != 1)
-	cost.cost += multiply_by_cost (ratio, TYPE_MODE (ctype), speed);
+	cost.cost += multiply_by_const_cost (ratio, TYPE_MODE (ctype), speed);
       return cost;
     }
 
@@ -4209,18 +4378,18 @@ get_computation_cost_at (struct ivopts_data *data,
       are added once to the variable, if present.  */
   if (var_present && (symbol_present || offset))
     cost.cost += adjust_setup_cost (data,
-				    add_cost (TYPE_MODE (ctype), speed));
+				    add_regs_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);
+  cost.cost += add_regs_cost (TYPE_MODE (ctype), speed);
 
   aratio = ratio > 0 ? ratio : -ratio;
   if (aratio != 1)
-    cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);
+    cost.cost += multiply_by_const_cost (aratio, TYPE_MODE (ctype), speed);
   return cost;
 
 fallback:
@@ -4277,7 +4446,7 @@ determine_use_iv_cost_generic (struct ivopts_data *data,
   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, no_cost, NULL, NULL_TREE,
                        ERROR_MARK, -1);
       return true;
     }
@@ -5066,7 +5235,7 @@ determine_iv_cost (struct ivopts_data *data, struct iv_cand *cand)
      or a const set.  */
   if (cost_base.cost == 0)
     cost_base.cost = COSTS_N_INSNS (1);
-  cost_step = add_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
+  cost_step = add_regs_cost (TYPE_MODE (TREE_TYPE (base)), data->speed);
 
   cost = cost_step + adjust_setup_cost (data, cost_base.cost);
 
@@ -5561,10 +5730,10 @@ iv_ca_new (struct ivopts_data *data)
   nw->cands = BITMAP_ALLOC (NULL);
   nw->n_cands = 0;
   nw->n_regs = 0;
-  nw->cand_use_cost = zero_cost;
+  nw->cand_use_cost = no_cost;
   nw->cand_cost = 0;
   nw->n_invariant_uses = XCNEWVEC (unsigned, data->max_inv_id + 1);
-  nw->cost = zero_cost;
+  nw->cost = no_cost;
   nw->used_inv_expr = XCNEWVEC (unsigned, data->inv_expr_id + 1);
   nw->num_used_inv_expr = 0;
 
@@ -6638,6 +6807,8 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data *data)
   VEC_free (iv_use_p, heap, data->iv_uses);
   VEC_free (iv_cand_p, heap, data->iv_candidates);
   htab_delete (data->inv_expr_tab);
+
+  finalize_costs ();
 }
 
 /* Returns true if the loop body BODY includes any function calls.  */