x86 failure on loop reversal

x86 failure on loop reversal

[Joern Rennecke]

The appended tests fails for egcs at -O2.  This is a synthetic test to
demonstrate a bug I found while looking for some possible improvements
to check_dbra_loop: when the initial value is normalized, an overflow
can occur.
I suggest that if we did a normalisation that results in a negative initial
value, we change the comparison into an unsigned one.
Actually, we could do this change always when we erverse the loop, and then
we could do away with the NONNEG note.  However, changing a signed compare
into an unsigned compare might fail sometimes (depending on how well we
can grok the RTL and what the target accepts), so it is better not to have
to rely on this.

int
f()
{
  int j = 1;
  int i;
  for (i = -0x80000000; i < 0x60000000; i += 0x10000000) j <<= 1;
  return j;
}

int
main ()
{
  if (f () != 16384)
    abort ();
  return 0;
}

Re: x86 failure on loop reversal

[Jim Wilson]

The existing test is (FOO >= 0).  Changing that to an unsigned test doesn't
look very useful, as it will be always true.  I suggest we just avoid
reversing the loop in this case.  This is rare enough, and tricky enough,
that I don't think we need to handle it.

How about something like this?  If this is OK, I will add the testcase and
check in the patch at the same time.

Mon Apr  6 20:08:43 1998  Jim Wilson  <wilson@cygnus.com>

	* loop.c (check_dbra_loop): When normalize comparison_val, add check
	to verify it is non-negative.

Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.37
diff -p -r1.37 loop.c
*** loop.c	1998/03/25 10:32:36	1.37
--- loop.c	1998/04/07 03:06:43
*************** check_dbra_loop (loop_end, insn_count, l
*** 6281,6287 ****
  		  && GET_CODE (initial_value) == CONST_INT)
  		{
  		  comparison_val = comparison_val - INTVAL (bl->initial_value);
! 		  initial_value = const0_rtx;
  		}
  
  	      /* If the initial value is not zero, or if the comparison
--- 6281,6290 ----
  		  && GET_CODE (initial_value) == CONST_INT)
  		{
  		  comparison_val = comparison_val - INTVAL (bl->initial_value);
! 		  /* Check for overflow.  If comparison_val ends up as a
! 		     negative value, then we can't reverse the loop.  */
! 		  if (comparison_val >= 0)
! 		    initial_value = const0_rtx;
  		}
  
  	      /* If the initial value is not zero, or if the comparison

Re: x86 failure on loop reversal

[Jeffrey A Law]

  In message < 199804070310.UAA12087@rtl.cygnus.com >you write:
  > The existing test is (FOO >= 0).  Changing that to an unsigned test doesn't
  > look very useful, as it will be always true.  I suggest we just avoid
  > reversing the loop in this case.  This is rare enough, and tricky enough,
  > that I don't think we need to handle it.
  > 
  > How about something like this?  If this is OK, I will add the testcase and
  > check in the patch at the same time.
  > 
  > Mon Apr  6 20:08:43 1998  Jim Wilson  <wilson@cygnus.com>
  > 
  > 	* loop.c (check_dbra_loop): When normalize comparison_val, add check
  > 	to verify it is non-negative.
I was going to suggest the same basic change; this is probably the
simplest/easiest way to fix the problem.

jeff

Re: x86 failure on loop reversal

[Joern Rennecke]

> The existing test is (FOO >= 0).  Changing that to an unsigned test doesn't
> look very useful, as it will be always true.  I suggest we just avoid
> reversing the loop in this case.  This is rare enough, and tricky enough,
> that I don't think we need to handle it.
> 
> How about something like this?  If this is OK, I will add the testcase and
> check in the patch at the same time.
> 
> Mon Apr  6 20:08:43 1998  Jim Wilson  <wilson@cygnus.com>
> 
> 	* loop.c (check_dbra_loop): When normalize comparison_val, add check
> 	to verify it is non-negative.

Yes, this works.  I set out to do a more elaborate change that adds new
optimization, but it turned out to be somewhat more complex that I first
thought.  So it's probably best to install your bug fix first, then we
can talk about my optimization patch.

Here is a version of the testcase that avoids the -0x80000000 problem:

int
f()
{
  int j = 1;
  long i;
  for (i = -0x70000000L; i < 0x60000000L; i += 0x10000000L) j <<= 1;
  return j;
}

int
main ()
{
  if (f () != 8192)
    abort ();
  return 0;
}

Re: x86 failure on loop reversal

[Jeffrey A Law]

  In message < 199804071327.OAA09064@phal.cygnus.co.uk >you write:
  > Here is a version of the testcase that avoids the -0x80000000 problem:
  > 
  > int
  > f()
  > {
  >   int j = 1;
  >   long i;
  >   for (i = -0x70000000L; i < 0x60000000L; i += 0x10000000L) j <<= 1;
  >   return j;
  > }
  > 
  > int
  > main ()
  > {
  >   if (f () != 8192)
  >     abort ();
  >   return 0;
  > }
I added this test to the testsuite.

jeff

Re: x86 failure on loop reversal

[Jim Wilson]

	I added this test to the testsuite.

So did I.  I removed my copy of the test.

Jim

RE: x86 failure on loop reversal

[Kaz Kylheku]

On Thursday, April 02, 1998 5:13 PM, Joern Rennecke 
[SMTP:amylaar@cygnus.co.uk] wrote:
> The appended tests fails for egcs at -O2.  This is a synthetic test to
> demonstrate a bug I found while looking for some possible improvements
> to check_dbra_loop: when the initial value is normalized, an overflow
> can occur.
> I suggest that if we did a normalisation that results in a negative initial
> value, we change the comparison into an unsigned one.
> Actually, we could do this change always when we erverse the loop, and then
> we could do away with the NONNEG note.  However, changing a signed compare
> into an unsigned compare might fail sometimes (depending on how well we
> can grok the RTL and what the target accepts), so it is better not to have
> to rely on this.
>
> int
> f()
> {
>   int j = 1;
>   int i;
>   for (i = -0x80000000; i < 0x60000000; i += 0x10000000) j <<= 1;
>   return j;
> }

Could you explain in more detail what you are trying to demonstrate?

Assuming 32 bit, two's complement longs, the constant 0x80000000 is simply out
of the range of the long type, which is -0x80000000 to 0x7FFFFFFF. The sign is
not part of the integral constant, what you have is an out-of-range positive 
constant
that is negated. I don't have my copy of the C standard handy today, but I 
would
guess that the effect of writing an out-of-range integral constant is 
undefined.

To create a constant expression which evaluates to the most negative long
value (assuming, again, 32 bit, two's complement), you must write:

	-0x7FFFFFFF - 1

This value has no additive inverse that is representable in a long, and so 
cannot
be formed by negating a positive constant.

Re: x86 failure on loop reversal

[Joern Rennecke]

> To create a constant expression which evaluates to the most negative long
> value (assuming, again, 32 bit, two's complement), you must write:
> 
> 	-0x7FFFFFFF - 1

Point taken; it should be -0x7fffffff - 1 in the testcase.
However, gcc doesn't really care; the problem is actually in check_dbra_loop.