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
2011-05-05 Tom de Vries <t...@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.
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);
