This is the mail archive of the gcc-bugs@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]