🚀 go-pugleaf

Newsgroups: gnu.gcc.bug
Path: peter
From: peter@shylock.demon.co.uk (Peter Clements)
Subject: signed/unsigned comparison bug (was Re: strength reduction bug in gcc 2.7.x)
Distribution: gnu
Organization: Shylock
Message-ID: <DL920u.662@shylock.demon.co.uk>
References: <199512040444.EAA11894@shellx.best.com> <4bcbn8$pee@work.smurf.noris.de>
Date: Tue, 16 Jan 1996 01:12:30 GMT

In article <4bcbn8$pee@work.smurf.noris.de>,
Matthias Urlichs <smurf@work.smurf.noris.de> wrote:
>The bug shows (at least, possibly) on the i386 by compilation with -O2
>versus -O2 -fno-strength-reduce, of the program below.
>
>I offer $100 to anybody who fixes that bug. Adding -fno-strength-reduce to
>the specs file isn't a bug fix.  :-/
>
>
>#include <stdio.h>
>int A[3];
>unsigned int B = 3;
>  
>void printit(void)
>{
>  int i;
>  for(i = 0; i < B; i++)
>    fprintf(stdout, "A[%d] = %d\n", i, A[i]);
>}
>  
>int main()
>{
>  int i;
>  for(i = 0; i < B; i++)
>     A[i] = i - 3;
>  printit();
>  return 0;
>}


I had a look at the assembler code generated by the above and have come the
conclusion that there it does not in fact demonstrate a bug in the strength
reduction optimisation. What it demostrates is a bug in the code generated
for the comparison of signed and unsigned numbers.


-----------> test1.c <---------------------------------------------------
#include <stdio.h>

signed int A[3] = {10,11,12};
unsigned long B = 2;

void printit() {
  signed int i;

  for (i=0; i<3; i++)
    printf("A[%d]=%d\n",i,A[i]);
}

signed int a;
int c;
int func(int j) {
  a = j + 2;

  if (a < B)
    c = 1;
  else
    c = 0;

  return c;
}

int main() {
  signed int i;

  for (i = 0; func(i - 3); i++)
    A[i] = i - 3;

  printit();

  return 0;
}
----------------------------------------------------------------------------

In main() (where the strength reduction bug was purported to be
demonstrated) I have replaced the test "i < B" with "func(i - 3)".

When compiled with "-O2 -fstrength-reduce" the following code is generated:


        movl $-3,%ebx
        .align 4
.L11:
        pushl %ebx
        call func
        addl $4,%esp
        testl %eax,%eax
        je .L12
        movl %ebx,A+12(,%ebx,4)
        incl %ebx
        jmp .L11
        .align 16
.L12:

When compiled with "-O2 -fno-strength-reduce" the following code is generated:

        xorl %ebx,%ebx
        .align 4
.L11:
        leal -3(%ebx),%esi
        pushl %esi
        call func
        addl $4,%esp
        testl %eax,%eax
        je .L12
        movl %esi,A(,%ebx,4)
        incl %ebx
        jmp .L11
        .align 16
.L12:

Strength reduction eliminates the need to use %esi to hold a temporary
value, and also reduces the loop by 1 instruction from 9 to 8.

However, when the above program is run it fails whether or not strength
reduction is or is not enabled!

The failure is taking place in "func()". Examination reveals that the first
time func() is called, j=-3, and hence a=-1, and since B=2, the comparison
that is made to set the value of c is "-1 < 2". This comparision fails, and
hence func() returns 0! The reason the comparison fails is due to the fact
that the code generated is for an *unsigned* comparison and the test is
effectively "UINT_MAX < 2".

If the comparison in func() is replaced with:

  if (a < 0 || (unsigned)a < B)
    c = 1;
  else
    c = 0;

this will always work correctly for any legal values of a and B. The cast of
a to (unsigned) is not strictly necessary.

The reason I replaced "i < B" with "func(i - 3)" is due to the fact that
strangth reduction causes i-3 to be used as the loop index instead of i, and
the comparison that is carried out in the original code is for "(i-3)<(B-3)".

I wrote another test program to examine the signed/unsigned comparison as
follows:

--------> test2.c <-----------------------------------------------------------
signed typeA A = -1;
unsigned typeB B = 1;

int C;
int main() {
  if (A < B )
    C = 0;
  else
    C = 1;

  return C;
}
-----------------------------------------------------------------------------

When this program is tested with typeA and typeB replaced with every
combination of "char", "short", "int", "long", and "long long", I obtained
the following:

                                  typeB

                    char   short  int    long   long long

       char         good   good   bad    bad    bad
       short        good   good   bad    bad    bad
typeA  int          good   good   bad    bad    bad
       long         good   good   bad    bad    bad
       long long    good   good   good   good   bad

I've had a look at the source for gcc and it would appear that the failure
is within build_binary_op() and common_type() when trying to decide what to
do with a pair of arguments when one is signed and the other is unsigned. 

When typeA and typeB are both char or short, things work correctly, because
both get promoted (by sign or zero extension) to signed long (which can
represent all possible values that typeA or typeB could take) and a signed
comparison is generated.

When typeA is int or long, and typeB is char or short, things also work
correctly with typeB being zero extended to become a signed long and a
signed comparison is generated again.

When typeA is char, short, int, or long, and typeB is int or long, things go
wrong. typeA is correctly signed extended to become a signed long, but gcc
chooses to generate code for an unsigned comparison. Unfortunatley even if
code for a signed comparison were generated, it would fail if typeB had a
value greater than INT_MAX. Promoting both typeA and typeB to signed long
long produces correct but unwieldy code.

When typeA is long long, and typeB is char, short, int, or long, it works
correctly again as typeB is zero extended and a signed comparison is
generated.

Finally, if typeB is long long, the comparison always fails due to the fact
that an unsigned comparsion is generated.

I have concluded that to ensure that correct code will always be generated,
the default promotion should be carried out on typeA, and if the resulting
type can represent all possible values of typeB then typeB should be
promoted to the same type and a signed comparison generated. If all possible
values of typeB cannot be represented then code for the following should be
generated:

(A < 0 || (unsigned)A < B).
-- 
Peter Clements              peter@shylock.demon.co.uk
                            pclements@cix.compulink.co.uk