[Bug tree-optimization/58915] New: [missed optimization] GCC fails to get the loop bound for some loops.

[Bug tree-optimization/58915] New: [missed optimization] GCC fails to get the loop bound for some loops.

[congh at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58915

            Bug ID: 58915
           Summary: [missed optimization] GCC fails to get the loop bound
                    for some loops.
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: congh at google dot com

Getting the correct loop upper bound is important for some optimizations. GCC
tries to get this bound by calling bound_difference() in
tree-ssa-loop-niters.c, where GCC finds all control-dependent predicates of the
loop and attempt to extract bound information from each predicate. 

However, GCC fails to get the bound for some loops. Below shows such an
example:

unsigned int i;
if (i > 0) {
   ...
   if (i < 4) {
      do {
         ...
         --i;
      } while (i > 0);
   }
}

Clearly the upper bound is 3. But GCC could not get it for this loop. The
reason is that GCC check i<4 (i could be zero) and i>0 separately and from
neither condition can the upper bound be calculated. Those two conditions may
not be combined into one as there may exist other statements between them. 

One possible solution is letting GCC collect all conditions first then merge
them before calculating the upper bound.


Any comments?

[Bug tree-optimization/58915] [missed optimization] GCC fails to get the loop bound for some loops.

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58915

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-10-30
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It should now be possible to use range information computed by VRP during
this analysis, see get_range_info ().  The predicate walking code should
be no longer needed and should be replaced with using that info.

[Bug tree-optimization/58915] [missed optimization] GCC fails to get the loop bound for some loops.

[congh at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58915

--- Comment #2 from Cong Hou <congh at google dot com> ---
I am afraid that get_range_info () has little use here. The value range we care
about may only exist under specific conditions and is hence flow sensitive. For
example, we may need the value range of n in the if body:

if (n > 0)
  if (n < 4)
    /* use of n */

However, n does not have a new name under the condition n>0 && n<4, making it
impossible to get the range (0, 4) from the SSA_NAME of n.

[Bug tree-optimization/58915] [missed optimization] GCC fails to get the loop bound for some loops.

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58915

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
True, it may still help in some cases though.

On my list of nice-things-to-have is still a generic predicate collecting
& simplification machinery similar to what we have with tree-affine.c.
That is collect || && predicates in a vector and simplify / normalize
them and solve queries against them, like in this case whether we can
derive range information from them.

[Bug tree-optimization/58915] [missed optimization] GCC fails to get the loop bound for some loops.

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED
      Known to work|                            |6.1.0, 7.1.0
   Target Milestone|---                         |6.0

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
hmm, curoll has
Loop 1 iterates at most 4 times.

int g(void);
void h(void);
int f(unsigned int i)
{
if (i > 0){
    h();
   if (i < 4)   {
      do {
         // if (i > 100)
          g();
         --i;
      } while (i > 0);
   }
}

}

r0-125361-ga895a2b8 started to export the range for i inside the loop.
And then r0-126335-g7190fdc1906cfdfee started to use the range information for
tree-ssa-loop-niter.c.


Without the VRP, GCC 6.1.0 have this fixed by r6-5389.

So closed as fully fixed for GCC 6.1.0.

[Bug tree-optimization/58915] [missed optimization] GCC fails to get the loop bound for some loops.

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> Without the VRP, GCC 6.1.0 have this fixed by r6-5389.

Or it was fixed by r6-3351 but it was some patch in GCC 6 timeframe which got
tree-ssa-loop-niter.c to work without VRP usage.