From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5454 invoked by alias); 17 May 2011 07:19:21 -0000 Received: (qmail 5439 invoked by uid 22791); 17 May 2011 07:19:19 -0000 X-SWARE-Spam-Status: No, hits=0.6 required=5.0 tests=AWL,BAYES_50,SUBJ_ALL_CAPS,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 17 May 2011 07:19:06 +0000 Received: (qmail 11728 invoked from network); 17 May 2011 07:19:05 -0000 Received: from unknown (HELO ?192.168.1.68?) (vries@127.0.0.2) by mail.codesourcery.com with ESMTPA; 17 May 2011 07:19:05 -0000 Message-ID: <4DD22146.7060103@codesourcery.com> Date: Tue, 17 May 2011 08:37:00 -0000 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Lightning/1.0b2 Thunderbird/3.1.10 MIME-Version: 1.0 To: Zdenek Dvorak CC: gcc-patches@gcc.gnu.org Subject: [PATCH, PR45098, 5/10] References: <4DD21F6E.4050308@codesourcery.com> In-Reply-To: <4DD21F6E.4050308@codesourcery.com> Content-Type: multipart/mixed; boundary="------------010802050202080803070608" Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org X-SW-Source: 2011-05/txt/msg01196.txt.bz2 This is a multi-part message in MIME format. --------------010802050202080803070608 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 542 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 --------------010802050202080803070608 Content-Type: text/x-patch; name="05_pr45098-bound-cost.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="05_pr45098-bound-cost.patch" Content-length: 5912 2011-05-05 Tom de Vries 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); --------------010802050202080803070608--