[PATCH PR45098, 5/10] Bound cost

[Tom de Vries <vries@codesourcery.com>]

[-- Attachment #1: Type: text/plain, Size: 1494 bytes --]

On 05/17/2011 09:18 AM, Tom de Vries wrote:
> On 05/17/2011 09:10 AM, Tom de Vries wrote:
>> Hi Zdenek,
>>
>> I have a patch set for for PR45098.
>>
>> 01_object-size-target.patch
>> 02_pr45098-rtx-cost-set.patch
>> 03_pr45098-computation-cost.patch
>> 04_pr45098-iv-init-cost.patch
>> 05_pr45098-bound-cost.patch
>> 06_pr45098-bound-cost.test.patch
>> 07_pr45098-nowrap-limits-iterations.patch
>> 08_pr45098-nowrap-limits-iterations.test.patch
>> 09_pr45098-shift-add-cost.patch
>> 10_pr45098-shift-add-cost.test.patch
>>
>> I will sent out the patches individually.
>>
> 
> OK for trunk?
> 
> Thanks,
> - Tom

Resubmitting with comment.

This improves the estimation of cost of bound calculation:
- It tries to estimate whether an ssa_name can be used in the loop
  at zero cost, or whether a regcopy is needed to keep the ssa_name
  alive during the loop, and counts the cost of the regcopy.
- It adjusts the cost of a complex loop bound: if a complex loop bound
  uses more that 1 invariant, it is counted as a new single invariant.
- It estimates the cost of an int bound at zero.

2011-05-05  Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* tree-ssa-loop-ivopts.c (get_expr_id): Factored new function out of
	get_loop_invariant_expr_id.
	(get_loop_invariant_expr_id): Use get_expr_id.
	(parm_decl_cost): New function.
	(determine_use_iv_cost_condition): Use get_expr_id and parm_decl_cost.
	Improve bound cost estimation.  Use different inv_expr_id for elim and
	express cases.

[-- Attachment #2: 05_pr45098-bound-cost.patch --]
[-- Type: text/x-patch, Size: 5504 bytes --]

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 173380)
+++ gcc/tree-ssa-loop-ivopts.c	(working copy)
@@ -3835,6 +3835,28 @@ compare_aff_trees (aff_tree *aff1, aff_t
   return true;
 }
 
+/* Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id.  */
+
+static int
+get_expr_id (struct ivopts_data *data, tree expr)
+{
+  struct iv_inv_expr_ent ent;
+  struct iv_inv_expr_ent **slot;
+
+  ent.expr = expr;
+  ent.hash = iterative_hash_expr (expr, 0);
+  slot = (struct iv_inv_expr_ent **) htab_find_slot (data->inv_expr_tab,
+                                                     &ent, INSERT);
+  if (*slot)
+    return (*slot)->id;
+
+  *slot = XNEW (struct iv_inv_expr_ent);
+  (*slot)->expr = expr;
+  (*slot)->hash = ent.hash;
+  (*slot)->id = data->inv_expr_id++;
+  return (*slot)->id;
+}
+
 /* Returns the pseudo expr id if expression UBASE - RATIO * CBASE
    requires a new compiler generated temporary.  Returns -1 otherwise.
    ADDRESS_P is a flag indicating if the expression is for address
@@ -3847,8 +3869,6 @@ get_loop_invariant_expr_id (struct ivopt
 {
   aff_tree ubase_aff, cbase_aff;
   tree expr, ub, cb;
-  struct iv_inv_expr_ent ent;
-  struct iv_inv_expr_ent **slot;
 
   STRIP_NOPS (ubase);
   STRIP_NOPS (cbase);
@@ -3936,18 +3956,7 @@ get_loop_invariant_expr_id (struct ivopt
   aff_combination_scale (&cbase_aff, shwi_to_double_int (-1 * ratio));
   aff_combination_add (&ubase_aff, &cbase_aff);
   expr = aff_combination_to_tree (&ubase_aff);
-  ent.expr = expr;
-  ent.hash = iterative_hash_expr (expr, 0);
-  slot = (struct iv_inv_expr_ent **) htab_find_slot (data->inv_expr_tab,
-                                                     &ent, INSERT);
-  if (*slot)
-    return (*slot)->id;
-
-  *slot = XNEW (struct iv_inv_expr_ent);
-  (*slot)->expr = expr;
-  (*slot)->hash = ent.hash;
-  (*slot)->id = data->inv_expr_id++;
-  return  (*slot)->id;
+  return get_expr_id (data, expr);
 }
 
 
@@ -4412,6 +4421,23 @@ may_eliminate_iv (struct ivopts_data *da
   return true;
 }
 
+ /* Calculates the cost of BOUND, if it is a PARM_DECL.  A PARM_DECL must
+    be copied, if is is used in the loop body and DATA->body_includes_call.  */
+
+static int
+parm_decl_cost (struct ivopts_data *data, tree bound)
+{
+  tree sbound = bound;
+  STRIP_NOPS (sbound);
+
+  if (TREE_CODE (sbound) == SSA_NAME
+      && TREE_CODE (SSA_NAME_VAR (sbound)) == PARM_DECL
+      && gimple_nop_p (SSA_NAME_DEF_STMT (sbound))
+      && data->body_includes_call)
+    return COSTS_N_INSNS (1);
+
+  return 0;
+}
 
 /* Determines cost of basing replacement of USE on CAND in a condition.  */
 
@@ -4422,9 +4448,9 @@ determine_use_iv_cost_condition (struct 
   tree bound = NULL_TREE;
   struct iv *cmp_iv;
   bitmap depends_on_elim = NULL, depends_on_express = NULL, depends_on;
-  comp_cost elim_cost, express_cost, cost;
+  comp_cost elim_cost, express_cost, cost, bound_cost;
   bool ok;
-  int inv_expr_id = -1;
+  int elim_inv_expr_id = -1, express_inv_expr_id = -1, inv_expr_id;
   tree *control_var, *bound_cst;
 
   /* Only consider real candidates.  */
@@ -4438,6 +4464,21 @@ determine_use_iv_cost_condition (struct 
   if (may_eliminate_iv (data, use, cand, &bound))
     {
       elim_cost = force_var_cost (data, bound, &depends_on_elim);
+      if (elim_cost.cost == 0)
+        elim_cost.cost = parm_decl_cost (data, bound);
+      else if (TREE_CODE (bound) == INTEGER_CST)
+        elim_cost.cost = 0;
+      /* If we replace a loop condition 'i < n' with 'p < base + n',
+	 depends_on_elim will have 'base' and 'n' set, which implies
+	 that both 'base' and 'n' will be live during the loop.	 More likely,
+	 'base + n' will be loop invariant, resulting in only one live value
+	 during the loop.  So in that case we clear depends_on_elim and set
+        elim_inv_expr_id instead.  */
+      if (depends_on_elim && bitmap_count_bits (depends_on_elim) > 1)
+	{
+	  elim_inv_expr_id = get_expr_id (data, bound);
+	  bitmap_clear (depends_on_elim);
+	}
       /* The bound is a loop invariant, so it will be only computed
 	 once.  */
       elim_cost.cost = adjust_setup_cost (data, elim_cost.cost);
@@ -4465,16 +4506,25 @@ determine_use_iv_cost_condition (struct 
 
   express_cost = get_computation_cost (data, use, cand, false,
 				       &depends_on_express, NULL,
-                                       &inv_expr_id);
+                                       &express_inv_expr_id);
   fd_ivopts_data = data;
   walk_tree (&cmp_iv->base, find_depends, &depends_on_express, NULL);
 
+  /* Count the cost of the original bound as well.  */
+  bound_cost = force_var_cost (data, *bound_cst, NULL);
+  if (bound_cost.cost == 0)
+    bound_cost.cost = parm_decl_cost (data, *bound_cst);
+  else if (TREE_CODE (*bound_cst) == INTEGER_CST)
+    bound_cost.cost = 0;
+  express_cost.cost += bound_cost.cost;
+
   /* Choose the better approach, preferring the eliminated IV. */
   if (compare_costs (elim_cost, express_cost) <= 0)
     {
       cost = elim_cost;
       depends_on = depends_on_elim;
       depends_on_elim = NULL;
+      inv_expr_id = elim_inv_expr_id;
     }
   else
     {
@@ -4482,6 +4532,7 @@ determine_use_iv_cost_condition (struct 
       depends_on = depends_on_express;
       depends_on_express = NULL;
       bound = NULL_TREE;
+      inv_expr_id = express_inv_expr_id;
     }
 
   set_use_iv_cost (data, use, cand, cost, depends_on, bound, inv_expr_id);