From patchwork Wed May 18 17:10:17 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 96198 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 8A0281007D8 for ; Thu, 19 May 2011 03:11:35 +1000 (EST) Received: (qmail 12448 invoked by alias); 18 May 2011 17:11:31 -0000 Received: (qmail 12394 invoked by uid 22791); 18 May 2011 17:11:29 -0000 X-SWARE-Spam-Status: No, hits=-1.4 required=5.0 tests=AWL, BAYES_00, TW_TM, 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; Wed, 18 May 2011 17:11:14 +0000 Received: (qmail 24032 invoked from network); 18 May 2011 17:11:13 -0000 Received: from unknown (HELO ?192.168.1.68?) (vries@127.0.0.2) by mail.codesourcery.com with ESMTPA; 18 May 2011 17:11:13 -0000 Message-ID: <4DD3FD79.2020804@codesourcery.com> Date: Wed, 18 May 2011 19:10:17 +0200 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, 7/10] Nowrap limits iterations References: <4DD21F6E.4050308@codesourcery.com> <4DD221CF.4040002@codesourcery.com> In-Reply-To: <4DD221CF.4040002@codesourcery.com> Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On 05/17/2011 09:20 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 patch attemps to estimate the number of iterations of the loop based on nonwrapping arithmetic in the loop body. 2011-05-05 Tom de Vries PR target/45098 * tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields max_iterations_p and max_iterations. (is_nonwrap_use, max_loop_iterations, set_max_iterations): New function. (may_eliminate_iv): Use max_iterations_p and max_iterations. (tree_ssa_iv_optimize_loop): Use set_max_iterations. Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 173355) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -291,6 +291,12 @@ struct ivopts_data /* Whether the loop body includes any function calls. */ bool body_includes_call; + + /* Whether max_iterations is valid. */ + bool max_iterations_p; + + /* Maximum number of iterations of current_loop. */ + double_int max_iterations; }; /* An assignment of iv candidates to uses. */ @@ -4319,6 +4325,108 @@ iv_elimination_compare (struct ivopts_da return (exit->flags & EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR); } +/* Determine if USE contains non-wrapping arithmetic. */ + +static bool +is_nonwrap_use (struct ivopts_data *data, struct iv_use *use) +{ + gimple stmt = use->stmt; + tree var, ptr, ptr_type; + + if (!is_gimple_assign (stmt)) + return false; + + switch (gimple_assign_rhs_code (stmt)) + { + case POINTER_PLUS_EXPR: + ptr = gimple_assign_rhs1 (stmt); + ptr_type = TREE_TYPE (ptr); + var = gimple_assign_rhs2 (stmt); + if (!expr_invariant_in_loop_p (data->current_loop, ptr)) + return false; + break; + case ARRAY_REF: + ptr = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 0); + ptr_type = build_pointer_type (TREE_TYPE (gimple_assign_rhs1 (stmt))); + var = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 1); + break; + default: + return false; + } + + if (!nowrap_type_p (ptr_type)) + return false; + + if (TYPE_PRECISION (ptr_type) != TYPE_PRECISION (TREE_TYPE (var))) + return false; + + return true; +} + +/* Attempt to infer maximum number of loop iterations of DATA->current_loop + from uses in loop containing non-wrapping arithmetic. If successful, + return true, and return maximum iterations in MAX_NITER. */ + +static bool +max_loop_iterations (struct ivopts_data *data, double_int *max_niter) +{ + struct iv_use *use; + struct iv *iv; + bool found = false; + double_int period; + gimple stmt; + unsigned i; + + for (i = 0; i < n_iv_uses (data); i++) + { + use = iv_use (data, i); + + stmt = use->stmt; + if (!just_once_each_iteration_p (data->current_loop, gimple_bb (stmt))) + continue; + + if (!is_nonwrap_use (data, use)) + continue; + + iv = use->iv; + if (iv->step == NULL_TREE || TREE_CODE (iv->step) != INTEGER_CST) + continue; + period = tree_to_double_int (iv_period (iv)); + + if (found) + *max_niter = double_int_umin (*max_niter, period); + else + { + found = true; + *max_niter = period; + } + } + + return found; +} + +/* Initializes DATA->max_iterations and DATA->max_iterations_p. */ + +static void +set_max_iterations (struct ivopts_data *data) +{ + double_int max_niter, max_niter2; + bool estimate1, estimate2; + + data->max_iterations_p = false; + estimate1 = estimated_loop_iterations (data->current_loop, true, &max_niter); + estimate2 = max_loop_iterations (data, &max_niter2); + if (!(estimate1 || estimate2)) + return; + if (estimate1 && estimate2) + data->max_iterations = double_int_umin (max_niter, max_niter2); + else if (estimate1) + data->max_iterations = max_niter; + else + data->max_iterations = max_niter2; + data->max_iterations_p = true; +} + /* Check whether it is possible to express the condition in USE by comparison of candidate CAND. If so, store the value compared with to BOUND. */ @@ -4391,10 +4499,10 @@ may_eliminate_iv (struct ivopts_data *da /* See if we can take advantage of infered loop bound information. */ if (loop_only_exit_p (loop, exit)) { - if (!estimated_loop_iterations (loop, true, &max_niter)) + if (!data->max_iterations_p) return false; /* The loop bound is already adjusted by adding 1. */ - if (double_int_ucmp (max_niter, period_value) > 0) + if (double_int_ucmp (data->max_iterations, period_value) > 0) return false; } else @@ -6390,6 +6498,8 @@ tree_ssa_iv_optimize_loop (struct ivopts /* Finds candidates for the induction variables (item 2). */ find_iv_candidates (data); + set_max_iterations (data); + /* Calculates the costs (item 3, part 1). */ determine_iv_costs (data); determine_use_iv_costs (data);