[Bug tree-optimization/64183] New: [5.0 Regression] Complete unroll doesn't happen for a while-loop

[Bug tree-optimization/64183] New: [5.0 Regression] Complete unroll doesn't happen for a while-loop

[enkovich.gnu at gmail dot com]

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

            Bug ID: 64183
           Summary: [5.0 Regression] Complete unroll doesn't happen for a
                    while-loop
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: enkovich.gnu at gmail dot com

Created attachment 34189
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34189&action=edit
Reproducer

There is a performance regression in DENMark after r218142.  Regression happens
because complete unroll computes max number of iterations for a while-loop in a
different way.

Reduced reproducer:

int bits;
unsigned int size;
int max_code;

void
test ()
{
 int code = 0;

 while (code < max_code)
   code |= ((unsigned int) (size >> (--bits)));

 while (bits < (unsigned int)25)
   bits += 8;
}

Compilation string:

gcc -std=c90 -m32 -O3 test.c -c -fdump-tree-cunroll-details

Dump before r218142:

Analyzing # of iterations of loop 2
  exit condition [(unsigned int) (prephitmp_33 + 8), + , 8] <= 24
  bounds on difference of bases: -4294967271 ... 24
...
Loop 2 iterates at most 4 times.

Dump after r218142:

Analyzing # of iterations of loop 2
  exit condition [(unsigned int) (prephitmp_36 + 8), + , 8] <= 24
  bounds on difference of bases: -4294967271 ... 24
...
Loop 2 iterates at most 536870911 times.

While-loop condition has signed/unsigned comparison.  But I believe the
original estimation of 4 iterations is correct.

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Priority|P3                          |P1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-12-04
   Target Milestone|---                         |5.0
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
It works correctly for

int bits;

void
test ()
{
  while (bits < (unsigned int)25)
    bits += 8;
}

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[enkovich.gnu at gmail dot com]

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

--- Comment #2 from Ilya Enkovich <enkovich.gnu at gmail dot com> ---
(In reply to Richard Biener from comment #1)
> It works correctly for
> 
> int bits;
> 
> void
> test ()
> {
>   while (bits < (unsigned int)25)
>     bits += 8;
> }

Right.  But shift operator in the attached testcase somehow breaks it after
r218142 adds a conversion to unsigned type for a second shift operand.

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Which is

(instantiate_scev
  (instantiate_below = 10)
  (evolution_loop = 2)
  (chrec = (24 - (unsigned int) prephitmp_36) / 8)
  (res = (24 - (unsigned int) prephitmp_36) / 8))
  (set_nb_iterations_in_loop = scev_not_known))

vs.

(instantiate_scev
  (instantiate_below = 4)
  (evolution_loop = 1)
  (chrec = (24 - (unsigned int) bits.0_8) / 8)
  (res = (24 - (unsigned int) bits.0_8) / 8))
  (set_nb_iterations_in_loop = (unsigned int) bits.0_8 + 1 <= 25 ? (24 -
(unsigned int) bits.0_8) / 8 : 0))

with otherwise exactly the same scalar evolution analysis...

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Just thinking out loud - if the type is already int then there is no need to
promote or shorten it further, thus we could just leave it alone...

That is, only apply the extra conversion if it would shorten the shift
operand.

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |mpolacek at gcc dot gnu.org

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Mine then.

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[mpolacek at gcc dot gnu.org]

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

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Author: mpolacek
Date: Sat Dec  6 13:10:31 2014
New Revision: 218447

URL: https://gcc.gnu.org/viewcvs?rev=218447&root=gcc&view=rev
Log:
    PR tree-optimization/64183
    * c-gimplify.c (c_gimplify_expr): Don't convert the RHS of a
    shift-expression if it is integer_type_node.  Use types_compatible_p.

    * gcc.dg/tree-ssa/pr64183.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr64183.c
Modified:
    trunk/gcc/c-family/ChangeLog
    trunk/gcc/c-family/c-gimplify.c
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/64183] [5.0 Regression] Complete unroll doesn't happen for a while-loop

[mpolacek at gcc dot gnu.org]

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

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #7 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed.