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
