This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH GCC]Improve loop-niter to handle possible infinite loop.


On Fri, Jul 1, 2016 at 11:33 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jun 28, 2016 at 8:18 AM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> At the moment, loop niter analyzer depends on simple_iv to understand control induction variable in order to do further niter analysis.  For cases reported in PR57558 (comment #4), the control variable is not an SCEV because it's converted from an smaller type and that type could overflow/wrap.  As a result, niter information for such loops won't be analyzed because number_of_iterations_exit exits immediately once simple_iv fails.  As a matter of fact, niter analyzer can be improved by computing an additional assumption under which the loop won't be infinite (or the corresponding iv doesn't overflow).  This patch does so by changing both scev and niter analyzer.  It introduces a new interface simple_iv_with_niters which is used in niter analyzer.  The new interface returns an IV as well as a possible niter expression, the expression indicates the maximum number the IV can iterate before the returned simple_iv becoming invalid.  Given below example:
>>
>>   short unsigned int i;
>>   int _1;
>>
>>   <bb 2>:
>>   goto <bb 4>;
>>
>>   <bb 3>:
>>   arr[_1] = -1;
>>   i_6 = i_2 + 1;
>>
>>   <bb 4>:
>>   # i_2 = PHI <1(2), i_6(3)>
>>   _1 = (int) i_2;
>>   if (_1 != 199)
>>     goto <bb 3>;
>>   else
>>     goto <bb 5>;
>>
>>   <bb 5>:
>>   return;
>>
>> When analyzing variable "_1", the old interface simple_iv returns false, while the new interface returns <{1, 1}_loop, 65534>.  It means "_1" is a valid SCEV as long as it doesn't iterate more than 65534 times.
>> This patch also introduces a new interface in niter analyzer number_of_iterations_exit_assumptions.  The new interface further derives assumption from the result of simple_iv_with_niters, and the assumption can be used by other optimizers.  As for this loop, it's an unexpected gain because assumption (198 < 65534) is naturally TRUE.
>> For loops that could be infinite, the assumption will be an expression.  This improvement is still good, for example, the next patch to will vectorize such loops with help of this patch.
>>
>> This patch also changes how assumptions is handled in niter analyzer.  At the moment, (non-true) assumptions are not supported unless -funsafe-loop-optimizations are specified, after this patch, the new interface exposes assumptions to niter user and let them make their own decision.  In effect, this patch discards -funsafe-loop-optimizations on GIMPLE level, which we think is not a very useful option anyway.  Next patch will xfails tests for this option.  Well, the option is not totally discarded because it requires RTL changes too.  I will follow up that after gimple part change.
>>
>> Bootstrap and test on x86_64 and AArch64.  Is it OK?
>
> Please make simple_iv_with_niters accept NULL as iv_niters and pass
> NULL from simple_iv to avoid useless work.
>
> You have chosen to make the flags per loop instead of say, flags on
> the global loop state.  The patch itself doesn't set the flag
> on any loop thus it doesn't really belong into this patch IMHO, so
> maybe you can split it out.  We do already have a plethora
> of "flags" (badly packed) in struct loop and while I see the interface
> is sth very specific adding another 4 bytes doesn't look
> too nice here (but maybe we don't care, struct loop isn't allocated
> that much hopefully).  I'd like to see a better comment
> before the flags part in cfgloop.h though noting that those are not
> flags computed by the compiler but flags that are set
> by the consumer that affect semantics of certain (document which)
> APIs.  And that consumers are expected to re-set
> flags back!  (failing to do that might be a source of hard to track down bugs?)
>
> Anyway, the _assumtions part of the patch is ok with the suggested change.
>
Hi Richard,
According to your suggestion, I split the original patch into two, and
this is the first part.  It improves scalar evolution and loop niter
analyzer so that (possible) infinite loop can be handled.  As a bonus
point, it also picks up normal loops which were missed before, for
example, loop in the added test.

Bootstrap and test on x86_64 ongoing, Is it OK?

Thanks,
bin

2016-07-13  Bin Cheng  <bin.cheng@arm.com>

    * tree-scalar-evolution.c (simple_iv_with_niters): New funcion.
    (derive_simple_iv_with_niters): New function.
    (simple_iv): Rewrite using simple_iv_with_niters.
    * tree-scalar-evolution.h (simple_iv_with_niters): New decl.
    * tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions): New
    function.
    (number_of_iterations_exit): Rewrite using above function.
    * tree-ssa-loop-niter.h (number_of_iterations_exit_assumptions): New
    Decl.

gcc/testsuite/ChangeLog
2016-07-13  Bin Cheng  <bin.cheng@arm.com>

    * gcc.dg/tree-ssa/loop-41.c: New test.

Attachment: niter-for-possible-inifinte-loops-20160711.txt
Description: Text document


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]