On Thu, Jul 14, 2016 at 12:42 PM, Richard Biener
<richard.guent...@gmail.com> wrote:
> 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.
Applied as revision 238367, failure of gcc.dg/tree-ssa/pr19210-*.c
will be handled by following patch removing
-funsafe-loop-optimizations.
Thanks,
bin
>
> 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.
