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

[Richard Biener]

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.

Thanks,
Richard.

> Thanks,
> bin
>
> 2016-06-27  Bin Cheng  <bin.cheng@arm.com>
>
>         * cfgloop.h (flags): New field to loop struct.
>         (LOOP_F_INFINITE, LOOP_F_ASSUMPTIONS, LOOP_F_MUST_ROLL): New macros.
>         (loop_flag_set, loop_flag_clear, loop_flag_set_p): New functions.
>         * cfgloop.c (alloc_loop): Handle flags.
>         * 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-06-27  Bin Cheng  <bin.cheng@arm.com>
>
>         * gcc.dg/tree-ssa/loop-41.c: New test.