[Bug tree-optimization/58686] New: [BUG] vect_get_loop_niters() cound not get the correct result for some loops.

[Bug tree-optimization/58686] New: [BUG] vect_get_loop_niters() cound not get the correct result for some loops.

[congh at google dot com]

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

            Bug ID: 58686
           Summary: [BUG] vect_get_loop_niters() cound not get the correct
                    result 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

Look at the following loop:


  unsigned int t = ...;
  do {
    ...
    t -= 4;
  } while (t >= 5);


When I tried to get the iteration number of this loop as an expression using
vect_get_loop_niters(), it gave me the result "scev_not_known". If I changed
the type of t into signed int, then I can get the result as below: 


t > 4 ? ((unsigned int) t + 4294967291) / 4 : 0


But even when t is unsigned, we should still get the result as:


t != 4 ? (t + 4294967291) / 4 : 0


I spent some time on tracking the reason why it failed to do so, and then
reached the function assert_loop_rolls_lt(), in which the assumptions are built
to make sure we can get the iteration number from the following formula:


(iv1->base - iv0->base + step - 1) / step


In the example above, iv1->base is t-4, iv0->base is 4 (t>=5 is t>4), and step
is 4. This formula works only if


-step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1

(MAX is the maximum value of the unsigned variant of type of t, and in this
formula we don't have to take care of overflow.)


I think when (iv1->base - iv0->base) < -step + 1, then we can assume the number
of times the back edge is taken is 0, and that is how niter->may_be_zero is
built in this function. And niter->assumptions is built based on (iv1->base -
iv0->base) <= MAX - step + 1. Note that we can only get the iteration number of
the loop if niter->assumptions is always evaluated as true.

However, I found that the build of niter->assumptions does not involve both
iv1->base and iv0->base, but only one of them. I think this is possibly a
potential bug.

Further, the reason why we can get the iteration number if t is of unsigned int
type is that niter->assumptions built here t-4 < MAX-3 is evaluated to true, by
taking advantage of the fact that the overflow on signed int is undefined (so
t-4 < MAX-3 can be converted to t < MAX+1, where MAX+1 is assumed to not
overflow). But this is not working for unsigned int.

One more problem is the way how niter->may_be_zero is built. For the loop
above, niter->may_be_zero I got is 4 > t - 4 - (-4 + 1), but we should make
sure t-4 here does not overflow. Otherwise niter->may_be_zero is invalid. I
think the function assert_loop_rolls_lt() should take care more of unsigned int
types.

With this issue we cannot vectorize this loop as its iteration number is
unknown.


Thank you!

Cong

[Bug tree-optimization/58686] vect_get_loop_niters() fails for some loops

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
                 CC|                            |rakdver at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org
             Blocks|                            |53947
            Summary|[BUG]                       |vect_get_loop_niters()
                   |vect_get_loop_niters()      |fails for some loops
                   |cound not get the correct   |
                   |result for some loops.      |

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
You mention several things that sound like they may lead to wrong code.  Based
on your analysis, can you construct testcases that show a miscompile?  Easiest
would be to trick niter analysis to think a loop runs just once so it is
peeled completely.

Best have different bugreports for the (possible) wrong-code issues as this
bug starts about a missed optimization.  [versioning for niter may be
a possible solution, in case we can build proper conditions in
niter->assumptions]

[Bug tree-optimization/58686] vect_get_loop_niters() fails for some loops

[congh at google dot com]

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

--- Comment #2 from Cong Hou <congh at google dot com> ---
I think this issue is more like a missed optimization. 

If the iteration number can be calculated as a constant value at compile time,
then the function assert_loop_rolls_lt() won't be called due to an early exit
(specifically in the function number_of_iterations_lt() at the call to
number_of_iterations_lt_to_ne()). That is why I could not craft a testcase
showing miscompile.

A better test case is shown below:


#define N 4
void foo(int* a, unsigned int i)
{
  int j = 0;
  do
  {
    a[j++] = 0;
    i -= 4;
  }
  while (i >= N);
}


Compile it with -O3 and the produced result is using __builtin_memset() as the
niter can be calculated. But if the value of N is replaced by others like 3 or
5, GCC won't optimize this loop into __builtin_memset() any more.

[Bug tree-optimization/58686] vect_get_loop_niters() fails for some loops

[rguenther at suse dot de]

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

--- Comment #3 from rguenther at suse dot de <rguenther at suse dot de> ---
congh at google dot com <gcc-bugzilla@gcc.gnu.org> wrote:
>http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58686
>
>--- Comment #2 from Cong Hou <congh at google dot com> ---
>I think this issue is more like a missed optimization. 
>
>If the iteration number can be calculated as a constant value at
>compile time,
>then the function assert_loop_rolls_lt() won't be called due to an
>early exit
>(specifically in the function number_of_iterations_lt() at the call to
>number_of_iterations_lt_to_ne()). That is why I could not craft a
>testcase
>showing miscompile.
>
>A better test case is shown below:
>
>
>#define N 4
>void foo(int* a, unsigned int i)
>{
>  int j = 0;
>  do
>  {
>    a[j++] = 0;
>    i -= 4;
>  }
>  while (i >= N);
>}
>
>
>Compile it with -O3 and the produced result is using __builtin_memset()
>as the
>niter can be calculated. But if the value of N is replaced by others
>like 3 or
>5, GCC won't optimize this loop into __builtin_memset() any more.

Yeah, the issue in general is finding a condition that ensures the loop will
terminate and a formula that computes the number of iterations if that holds
true. In case of wrapping arithmetic this is non-trivial and likely not all
cases are implemented.

Richard.

[Bug tree-optimization/58686] vect_get_loop_niters() fails for some loops

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-12-12

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.

#define N 5
void foo(int* a, unsigned int i)
{
  int j = 0;
  do
  {
    a[j++] = 0;
    i -= 4;
  }
  while (i >= N);
}

---- CUT ---
LLVM can convert the above loop into a memset while GCC does not.

[Bug tree-optimization/58686] vect_get_loop_niters() fails for some loops

[pinskia at gcc dot gnu.org]

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

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

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