[Bug tree-optimization/96615] New: Failure to optimize out loop that eventually ends but has no side effects

[Bug tree-optimization/96615] New: Failure to optimize out loop that eventually ends but has no side effects

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96615

            Bug ID: 96615
           Summary: Failure to optimize out loop that eventually ends but
                    has no side effects
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

void f(int bytes)
{
    bytes = (int)((unsigned int)bytes - 64);
    if (bytes > 0)
        f(bytes);
    return;
}

This can be optimized to doing nothing. LLVM does this transformation, but GCC
does not.

[Bug tree-optimization/96615] Failure to optimize out loop that eventually ends but has no side effects involving decrease of loop counter using an unsigned operation and the loop being done through recursivity

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96615

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/96615] Failure to optimize out loop that eventually ends but has no side effects involving decrease of loop counter using an unsigned operation and the loop being done through recursivity

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96615

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2020-08-25
                 CC|                            |amker at gcc dot gnu.org,
                   |                            |hubicka at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Even not with -ffinite-loops.  The reason is that finiteness of loops is
determined by frontends now and recorded in loop->finite_p but the loop
only appears after tail-recursion optimization.  I guess tailr could
unconditionally set loop->finite_p since the stack is bounded
but it relies on loop discovery and thus there's no easy way to do this
(not sure if the loop is always natural).

Of course niter analysis might do a better job on this kind of loop
to prove finiteness ...

One reason for the failure is of course that we compute

Analyzing # of iterations of loop 1
  exit condition 0 < [(int) ((unsigned int) bytes_7(D) + 4294967232), + , -64]
  bounds on difference of bases: -2147483648 ... 2147483647
  result:
    under assumptions (int) ((unsigned int) bytes_7(D) + 4294967232) <=
2147483584
    zero if (int) ((unsigned int) bytes_7(D) + 4294967295) < 0
    # of iterations ((unsigned int) bytes_7(D) + 4294967295) / 64, bounded by
33554432
  (set_nb_iterations_in_loop = scev_not_known))

which we throw away, not using it for loop estimates / max number of iterations
computation.

[Bug tree-optimization/96615] Failure to optimize out loop that eventually ends but has no side effects involving decrease of loop counter using an unsigned operation and the loop being done through recursivity

[hubicka at ucw dot cz]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96615

--- Comment #2 from Jan Hubicka <hubicka at ucw dot cz> ---
> Even not with -ffinite-loops.  The reason is that finiteness of loops is
> determined by frontends now and recorded in loop->finite_p but the loop
> only appears after tail-recursion optimization.  I guess tailr could
> unconditionally set loop->finite_p since the stack is bounded
> but it relies on loop discovery and thus there's no easy way to do this
> (not sure if the loop is always natural).

We used to have discussions about this.  We also consider function
possibily infinite if it is self recrusive even though it self-recurses
finitely many times.  I think relying on finiteness of stack is safe
assumption and in both cases we should mark loops as finite, but there
was some concerns from the C++ developers (Mark Mitchell
https://gcc.gnu.org/legacy-ml/gcc/1999-08/msg00700.html)
I think we could indeed in both cases (pure-const and tail recursion)
assume finiteness based on finiteness of the stack.

Honza
> 
> Of course niter analysis might do a better job on this kind of loop
> to prove finiteness ...
> 
> One reason for the failure is of course that we compute
> 
> Analyzing # of iterations of loop 1
>   exit condition 0 < [(int) ((unsigned int) bytes_7(D) + 4294967232), + , -64]
>   bounds on difference of bases: -2147483648 ... 2147483647
>   result:
>     under assumptions (int) ((unsigned int) bytes_7(D) + 4294967232) <=
> 2147483584
>     zero if (int) ((unsigned int) bytes_7(D) + 4294967295) < 0
>     # of iterations ((unsigned int) bytes_7(D) + 4294967295) / 64, bounded by
> 33554432
>   (set_nb_iterations_in_loop = scev_not_known))
> 
> which we throw away, not using it for loop estimates / max number of iterations
> computation.
> 
> -- 
> You are receiving this mail because:
> You are on the CC list for the bug.

[Bug tree-optimization/96615] Failure to optimize out loop that eventually ends but has no side effects involving decrease of loop counter using an unsigned operation and the loop being done through recursivity

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96615

--- Comment #3 from Gabriel Ravier <gabravier at gmail dot com> ---
It seems to be optimized into nothing as of right now