From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12430 invoked by alias); 28 May 2011 15:15:52 -0000 Received: (qmail 12418 invoked by uid 22791); 28 May 2011 15:15:51 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_FAIL X-Spam-Check-By: sourceware.org Received: from smtp-vbr15.xs4all.nl (HELO smtp-vbr15.xs4all.nl) (194.109.24.35) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 28 May 2011 15:15:32 +0000 Received: from [192.168.1.68] (teejay.xs4all.nl [213.84.119.160]) (authenticated bits=0) by smtp-vbr15.xs4all.nl (8.13.8/8.13.8) with ESMTP id p4SFFSnp060051 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 28 May 2011 17:15:30 +0200 (CEST) (envelope-from vries@codesourcery.com) Message-ID: <4DE110D3.8080904@codesourcery.com> Date: Sat, 28 May 2011 17:58: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> <4DD63AE1.7070600@codesourcery.com> <20110521122407.GA22860@kam.mff.cuni.cz> <4DD7FD8F.20909@codesourcery.com> In-Reply-To: <4DD7FD8F.20909@codesourcery.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 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/msg02242.txt.bz2 Hi Zdenek, On 05/21/2011 07:59 PM, Tom de Vries wrote: > On 05/21/2011 02:24 PM, Zdenek Dvorak wrote: >>> * tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix >>> estimated_loop_iterations comparison. >> >> I don't think this part is correct, though: >> >>> 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 >> > >> max_niter is the upper bound on the number of iterations of the loop, i.e., the number >> of executions of its latch edge. > > max_niter is set from estimated_loop_iterations, meaning from > loop->nb_iterations_upper_bound. > > consider: > ... > void f(int *a) > { > int i; > > for (i = 0; i < 10; ++i) > a[i] = 0; > } > ... > > at ivopts, it looks like this (compiled with -Os -fno-tree-vrp > -fno-tree-dominator-opts -fno-tree-loop-ivcanon, to get a source-like > representation) > ... > f (int * a) > { > int i; > int * D.2009; > unsigned int D.2008; > unsigned int i.0; > > : > goto ; > > : > i.0_3 = (unsigned int) i_1; > D.2008_4 = i.0_3 * 4; > D.2009_6 = a_5(D) + D.2008_4; > *D.2009_6 = 0; > i_7 = i_1 + 1; > > : > # i_1 = PHI <0(2), i_7(3)> > if (i_1 <= 9) > goto ; > else > goto ; > > : > return; > > } > ... > > > The header block of the loop is bb 4, the latch block is bb 3: > ... > (gdb) p loop.header.index > $4 = 4 > (gdb) p loop.latch.index > $5 = 3 > ... > > The number of times the latch edge is executed, is 10. > > But loop->nb_iterations_upper_bound, or max_niter is 11: > ... > (gdb) p *loop > $1 = {num = 1, ninsns = 0, header = 0xf7dc2440, latch = 0xf7dc2400, lpt_decision > = {decision = LPT_NONE, times = 0}, av_ninsns = 0, num_nodes = 2, superloops = > 0xf7db6ee8, inner = 0x0, next = 0x0, > aux = 0x0, nb_iterations = 0xf7d3d540, nb_iterations_upper_bound = {low = 11, > high = 0}, nb_iterations_estimate = {low = 11, high = 0}, any_upper_bound = 1 > '\001', any_estimate = 1 '\001', > can_be_parallel = 0 '\000', estimate_state = EST_AVAILABLE, bounds = > 0xf7d3da2c, exits = 0xf7dc3d70} > ... > >> Therefore, the control induction variable of the loop >> will (at the exit statement) achieve at most max_niter + 1 different values. > > Based on what I observe, I'd say the control induction variable of the loop will > achieve at most max_niter different values. > Any thoughts on my observations above? Thanks, - Tom