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