On Wed, Jul 13, 2016 at 6:09 PM, Bin.Cheng <amker.ch...@gmail.com> wrote:
> On Fri, Jul 1, 2016 at 11:33 AM, Richard Biener
> <richard.guent...@gmail.com> wrote:
>> On Tue, Jun 28, 2016 at 8:18 AM, Bin Cheng <bin.ch...@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?
Ok.
Thanks,
Richard.
> Thanks,
> bin
>
> 2016-07-13 Bin Cheng <bin.ch...@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.ch...@arm.com>
>
> * gcc.dg/tree-ssa/loop-41.c: New test.
