From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19386 invoked by alias); 20 May 2011 09:58:31 -0000 Received: (qmail 19374 invoked by uid 22791); 20 May 2011 09:58:30 -0000 X-SWARE-Spam-Status: No, hits=-1.5 required=5.0 tests=AWL,BAYES_00,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; Fri, 20 May 2011 09:58:10 +0000 Received: (qmail 7777 invoked from network); 20 May 2011 09:58:09 -0000 Received: from unknown (HELO ?192.168.1.68?) (vries@127.0.0.2) by mail.codesourcery.com with ESMTPA; 20 May 2011 09:58:09 -0000 Message-ID: <4DD63AE1.7070600@codesourcery.com> Date: Fri, 20 May 2011 12:22: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: Re: [PATCH PR45098, 7/10] Nowrap limits iterations References: <4DD21F6E.4050308@codesourcery.com> <4DD221CF.4040002@codesourcery.com> <4DD3FD79.2020804@codesourcery.com> <20110518211157.GA19788@kam.mff.cuni.cz> In-Reply-To: <20110518211157.GA19788@kam.mff.cuni.cz> Content-Type: multipart/mixed; boundary="------------030103040207090300010407" 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/msg01440.txt.bz2 This is a multi-part message in MIME format. --------------030103040207090300010407 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 2525 On 05/18/2011 11:11 PM, Zdenek Dvorak wrote: > Hi, > >> 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. > > what are the cases this handles better than the existing analysis of maximum numbers of iterations > (estimate_numbers_of_iterations)? Consider tr1: extern int pfoo (int*) __attribute__((pure)); int tr1 (int array[], unsigned int n) { int sum = 0; unsigned int i; i = 0; while (1) { sum += pfoo (&array[i]); if (!(i < n)) break; i++; } return sum; } The number of iterations is limited by &array[i]. &array[0x3fffffff] is still ok, but &array[0x40000000] wraps. So i runs maximally from 0 to 0x3fffffff, which is 0x40000000 loop iterations. Since &array[i] dominates the single loop exit, any statement in the loop is executed at most 0x40000000 times. That's also the amount registered in nb_iterations_upper_bound. Since int *p has 0x40000000 distinct values, it's ok to replace the exit test !(i < n) with p == &array[n]. On the other hand, consider tr6: int tr6 (int array[], unsigned int n) { int sum = 0; unsigned int i; for (i = 0; i < n; ++i) sum += pfoo (&array[i]); return sum; } The same holds as before, but &array[i] does not dominate the single loop exit, so any statement in the loop is executed at most 0x40000001 times. Note that the loop body is executed at most 0x40000000 times, and that only the exit test is executed at most 0x40000001 times. That's also the amount registered in nb_iterations_upper_bound. Since int *p has only 0x40000000 distinct values, it's not ok to replace the exit test in terms of p. > Would it be possible to add the handling of these cases > to estimate_numbers_of_iterations, rather than doing it just for ivopts? Yes, I did that now. Thanks, - Tom 2011-05-05 Tom de Vries PR target/45098 * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): New function. (infer_loop_bounds_from_undefined): Use new function. * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix estimated_loop_iterations comparison. --------------030103040207090300010407 Content-Type: text/x-patch; name="07_pr45098-nowrap-limits-iterations.patch" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="07_pr45098-nowrap-limits-iterations.patch" Content-length: 3227 Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 173734) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -2835,6 +2835,54 @@ infer_loop_bounds_from_array (struct loo that signed arithmetics in STMT does not overflow. */ static void +infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt) +{ + tree def, base, step, scev, type, low, high; + tree var, ptr; + + if (!is_gimple_assign (stmt) + || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) + return; + + def = gimple_assign_lhs (stmt); + if (TREE_CODE (def) != SSA_NAME) + return; + + type = TREE_TYPE (def); + if (!nowrap_type_p (type)) + return; + + ptr = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, ptr)) + return; + + var = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + return; + + scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); + if (chrec_contains_undetermined (scev)) + return; + + base = initial_condition_in_loop_num (scev, loop->num); + step = evolution_part_in_loop_num (scev, loop->num); + + if (!base || !step + || TREE_CODE (step) != INTEGER_CST + || tree_contains_chrecs (base, NULL) + || chrec_contains_symbols_defined_in_loop (base, loop->num)) + return; + + low = lower_bound_in_type (type, type); + high = upper_bound_in_type (type, type); + + record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); +} + +/* Determine information about number of iterations of a LOOP from the fact + that signed arithmetics in STMT does not overflow. */ + +static void infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt) { tree def, base, step, scev, type, low, high; @@ -2907,7 +2955,10 @@ infer_loop_bounds_from_undefined (struct infer_loop_bounds_from_array (loop, stmt, reliable); if (reliable) - infer_loop_bounds_from_signedness (loop, stmt); + { + infer_loop_bounds_from_signedness (loop, stmt); + infer_loop_bounds_from_pointer_arith (loop, stmt); + } } } Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 173734) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -4391,8 +4391,13 @@ may_eliminate_iv (struct ivopts_data *da { if (!estimated_loop_iterations (loop, true, &max_niter)) return false; - /* The loop bound is already adjusted by adding 1. */ - if (double_int_ucmp (max_niter, period_value) > 0) + /* The max iterations applies also to the number of times the loop + exit condition is executed. The number of distinct values of + the cand is period_value + 1. So, test for + 'period_value + 1 >= max_iterations'. + */ + period_value = double_int_add (period_value, double_int_one); + if (double_int_ucmp (max_niter, period_value) > 0) return false; } else --------------030103040207090300010407--