RE: [PATCH GCC]Improve bound information in loop niter analysis

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

All:

Does the Logic to calculate the Loop bound information through Value Range Analyis uses the post dominator and
Dominator info. The iteration branches instead of Loop exit condition can be calculated through post dominator info.
If the node in the Loop has two successors and post dominates the two successors then the iteration branch can be
The same node. 

For All the nodes L in the Loop B
If (L1, L2  belongs to successors of (L) && L1,L2 belongs to PosDom(Header of Loop))
{
  I = I union L1
}

Thus "I" will have all set of iteration branches. This will handle more cases of Loop bound information that 
Will be accurate through the exact iteration count that are known cases along with Value Range Information
Where the condition is instead not the Loop exits but other nodes in the Loop.

Thanks & Regards
Ajit
 

-----Original Message-----
From: gcc-patches-owner@gcc.gnu.org [mailto:gcc-patches-owner@gcc.gnu.org] On Behalf Of Bin.Cheng
Sent: Monday, August 17, 2015 3:32 PM
To: Richard Biener
Cc: Bin Cheng; GCC Patches
Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis

Thanks for all your reviews.

On Fri, Aug 14, 2015 at 4:17 PM, Richard Biener <richard.guenther@gmail.com> wrote:
> On Tue, Jul 28, 2015 at 11:36 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> Loop niter computes inaccurate bound information for different loops.  
>> This patch is to improve it by using loop initial condition in 
>> determine_value_range.  Generally, loop niter is computed by 
>> subtracting start var from end var in loop exit condition.  Moreover, 
>> loop bound is computed using value range information of both start and end variables.
>> Basic idea of this patch is to check if loop initial condition 
>> implies more range information for both start/end variables.  If yes, 
>> we refine range information and use that to compute loop bound.
>> With this improvement, more accurate loop bound information is 
>> computed for test cases added by this patch.
>
> +      c0 = fold_convert (type, c0);
> +      c1 = fold_convert (type, c1);
> +
> +      if (operand_equal_p (var, c0, 0))
>
> I believe if c0 is not already of type type operand-equal_p will never succeed.
It's quite specific case targeting comparison between var and it's range bounds.  Given c0 is in form of "var + offc0", then the comparison "var + offc0 != range bounds" doesn't have any useful information.  Maybe useless type conversion can be handled here though, it might be even corner case.

>
> (side-note: we should get rid of the GMP use, that's expensive and now 
> we have wide-int available which should do the trick as well)
>
> +         /* Case of comparing with the bounds of the type.  */
> +         if (TYPE_MIN_VALUE (type)
> +             && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
> +           cmp = GT_EXPR;
> +         if (TYPE_MAX_VALUE (type)
> +             && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
> +           cmp = LT_EXPR;
>
> don't use TYPE_MIN/MAX_VALUE.  Instead use the types precision and all 
> wide_int operations (see match.pd wi::max_value use).
Done.

>
> +  else if (!operand_equal_p (var, varc0, 0))
> +    goto end_2;
>
> ick - goto.  We need sth like a auto_mpz class with a destructor.
Label end_2 removed.

>
> struct auto_mpz
> {
>   auto_mpz () { mpz_init (m_val); }
>   ~auto_mpz () { mpz_clear (m_val); }
>   mpz& operator() { return m_val; }
>   mpz m_val;
> };
>
>> Is it OK?
>
> I see the code follows existing practice in niter analysis even though 
> my overall plan was to transition its copying of value-range related 
> optimizations to use VRP infrastructure.
Yes, I think it's easy to push it to VRP infrastructure.  Actually from the name of the function, it's more vrp related.  For now, the function is called only by bound_difference, not so many as vrp queries.  We need cache facility in vrp otherwise it would be expensive.

>
> I'm still ok with improving the existing code on the basis that I 
> won't get to that for GCC 6.
>
> So - ok with the TYPE_MIN/MAX_VALUE change suggested above.
>
> Refactoring with auto_mpz welcome.
That will be an independent patch, so I skipped it in this one.

New version attached.  Bootstrap and test on x86_64.

Thanks,
bin
>
> Thanks,
> RIchard.
>
>> Thanks,
>> bin
>>
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * tree-ssa-loop-niter.c (refine_value_range_using_guard): New.
>>         (determine_value_range): Call refine_value_range_using_guard for
>>         each loop initial condition to improve value range.
>>
>> gcc/testsuite/ChangeLog
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * gcc.dg/tree-ssa/loop-bound-1.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-3.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-5.c: New test.