doloop.c fix for PR 6984
Alan Modra
amodra@bigpond.net.au
Sat Jun 22 03:09:00 GMT 2002
On Fri, Jun 21, 2002 at 03:52:39PM -0700, Richard Henderson wrote:
> On Tue, Jun 18, 2002 at 09:02:00PM +0930, Alan Modra wrote:
> > - /* abs (final - initial) / (abs_inc * unroll_number) */
> > - /* abs (final - initial) % (abs_inc * unroll_number) */
> > - /* If (abs (final - initial) % (abs_inc * unroll_number)
> > - <= abs_inc * (unroll - 1)),
> > - jump past following increment instruction. */
> > + /* (abs (final - initial) + abs_inc - 1) / (abs_inc * unroll_number) */
>
> Are you absolutely certain that the original form of this
> expression was not done to avoid overflow in edge conditions?
> It sure looks like it.
Oh no. I was looking at the comment and saying to myself "abs (x)
can't be bigger than maxint+1, so it won't overflow". Wrong. This
"abs" can. But I may have been accidentally correct. ;)
When you look a little deeper, I'm fairly sure the cases where
overflow occurs don't matter. After all, abs_inc is the absolute
value of the loop increment, so I think I can claim that if
"abs (final - initial) + abs_inc - 1" overflows, then the loop
won't terminate. An example is something like
unsigned int f (unsigned int end)
{
unsigned int i, x;
for (i = 0, x = 0; i < end; i += 0x40000000)
x++;
return x;
}
where f(n), 0xC0000001 <= n should never return, assuming 32 bit ints.
Considering the case for a positive increment, my reasoning goes like
this:
inc is greater than one (doloop_modify_runtime)
inc is a power of two, 2**k say (precondition_loop_p)
the loop terminates with <, >, <= or >= test (doloop_valid_p)
final == initial + j * inc, for some integer j
so final - initial == j * inc
assume j * inc doesn't overflow (otherwise loop won't terminate)
and given width of iterator type is n bits
then j < 2**n / 2**k, or jmax is 2**(n-k) - 1
jmax * inc + inc - 1 == 2**(n-k) - 1) * 2**k + 2**k - 1
== 2**n - 1
--
Alan Modra
IBM OzLabs - Linux Technology Centre
More information about the Gcc-patches
mailing list