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

[Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com>]

-----Original Message-----
From: Bin.Cheng [mailto:amker.cheng@gmail.com] 
Sent: Tuesday, August 18, 2015 1:08 PM
To: Ajit Kumar Agarwal
Cc: Richard Biener; Bin Cheng; GCC Patches; Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala
Subject: Re: [PATCH GCC]Improve bound information in loop niter analysis

On Mon, Aug 17, 2015 at 6:49 PM, Ajit Kumar Agarwal <ajit.kumar.agarwal@xilinx.com> wrote:
> 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.

>>I don't quite follow your words here.  Could you please give a simple example about it?  Especially I don't know how post-dom helps the loop bound analysis.  >>Seems your pseudo code is collecting some comparison basic block of loop?

The Algorithm I have given above is based on Post Dominator Info. This helps to calculate the iteration branches. The iteration branches are the
Branches that determine the loop exit condition. Based on the condition it either branches to the header of the Loop, Or it may branch to the 
Block dominated by the header or exit from the loop. The above Algorithm finds out such iteration branches and thus decides on the Loop bound
Or iteration count. If such iteration branches are not at the back edge node and it may be a node inside the loop based on some conditions.
Finding out such iteration branches can be done through the post dominator info using the above algorithm.  Based on the iteration branches the 
conditions can be analyzed and that helps in finding out the iteration bound for Known cases. Know cases are the cases where the loop bound can be determined at compile time.

 One Example would be Multi-Exits Loops where the Loop exit condition can be at the back edge or it may be a block inside the Loop based on the 
IF conditions and breaks out based on the conditions. Thus having multiple exits. Such iteration branches can be found using The above Algorithm.

Thanks & Regards
Ajit 

Thanks,
bin
>
> 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.