doloop.c fix for PR 6984

[Alan Modra]

On Sun, Jun 23, 2002 at 02:58:38PM -0700, Richard Henderson wrote:
> On Sat, Jun 22, 2002 at 06:04:06PM +0930, Alan Modra wrote:
> >   final == initial + j * inc, for some integer j
> >   so final - initial == j * inc
> 
> I don't see this part of the setup.  Seems to me that
> 
>     final == initial + j * inc + c
>     for c < inc.

I was sloppy, and there's a missing step or two.

Let's try again, for positive increment.
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)
in fact, it must be < or <=			(doloop_optimize)
assume the loop terminates			(**)
then actual_final == initial + j * inc for some positive integer j
actual_final == test_final + c, 0 <= c < inc for < test, 0 < c <= inc for <=
so test_final - initial == j * inc - c

if the loop terminates, then initial + j * inc can't overflow.	(*)
so j * inc can't overflow.
and given width of iterator type is n bits
then j < 2**n / 2**k, or jmax is 2**(n-k) - 1

so test_final - initial + inc - 1 <= jmax * inc - c + inc - 1
                                  == (2**(n-k) - 1) * 2**k - c + 2**k - 1
                                  == 2**n - c - 1

which doesn't overflow.

*) There are a few steps to reach this conclusion too, the first being
that if the expression does overflow, then inc being a power of two
guarantees that when the iterator overflows it repeats the same
values.  This doesn't hold for a weird loop like

unsigned int i;
for (i = 1; i < 0xFFFFFFFF; i += 3)

where i overflows a number of times before finally reaching 0xFFFFFFFF.

**) Assuming the loop terminates is really bad, but see the comment
near the end of doloop_valid_p

> However, I wasn't able to construct an example for which
> the original wasn't a non-terminating loop.  So I guess
> the patch is ok.

Thanks.  May I add these comment corrections too?

	* doloop.c (doloop_valid_p): Correct comment.
	(doloop_modify_runtime): Likewise.

Index: gcc/doloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doloop.c,v
retrieving revision 1.19
diff -u -p -r1.19 doloop.c
--- gcc/doloop.c	17 Jun 2002 22:45:44 -0000	1.19
+++ gcc/doloop.c	24 Jun 2002 01:33:36 -0000
@@ -361,8 +361,8 @@ doloop_valid_p (loop, jump_insn)
     {
       /* If the comparison is LEU and the comparison value is UINT_MAX
 	 then the loop will not terminate.  Similarly, if the
-	 comparison code is GEU and the initial value is 0, the loop
-	 will not terminate.
+	 comparison code is GEU and the comparison value is 0, the
+	 loop will not terminate.
 
 	 If the absolute increment is not 1, the loop can be infinite
 	 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
@@ -591,6 +591,10 @@ doloop_modify_runtime (loop, iterations_
        n = abs (final - initial) / abs_inc;
        n += (abs (final - initial) % abs_inc) != 0;
 
+     But when abs_inc is a power of two, the summation won't overflow
+     except in cases where the loop never terminates.  So we don't
+     need to use this more costly calculation.
+
      If the loop has been unrolled, then the loop body has been
      preconditioned to iterate a multiple of unroll_number times.  If
      abs_inc is != 1, the full calculation is

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre