Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Christian Ehrhardt]

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7799

Hi,

this PR is about the following code snippet that is miscompiled with -Os

void fill (int* p, int* q[10])
{
        int i;
        for (i = 0; i < 10; i++)
                *q++ = &p[i];
}

The asm-Code is this:

        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        movl    12(%ebp), %edx
        leal    36(%eax), %ecx
.L6:
        movl    %eax, (%edx)
        addl    $4, %eax
        addl    $4, %edx
        cmpl    %ecx, %eax
        jle     .L6
        popl    %ebp
        ret

This code roughly corresponds to the following C-Code:

void fill (int * p, int *q[10])
{
	int ecx = (int)p + 9;
	do {
		*q = p; p++; q++;
	} while ((int)p <= ecx);
}

This transformation is IMHO illegal because there is no way to make the
comparison in general equivialent to that in the original for loop.
If p is initially 0x7ffffffc the comparison must be treated as unsigned,
however, if p is initially 0xfffffffc the comparison must be treated as
signed.

    regards   Christian

-- 
THAT'S ALL FOLKS!

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Eric Botcazou]

> This transformation is IMHO illegal because there is no way to make the
> comparison in general equivialent to that in the original for loop.
> If p is initially 0x7ffffffc the comparison must be treated as unsigned,
> however, if p is initially 0xfffffffc the comparison must be treated as
> signed.

Well-known deficiency of the strength reduction pass (see the testcase 
testsuite/gcc.c-torture/execute/loop-2e.c which is XFAILed on x86 at -Os).

-- 
Eric Botcazou

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Christian Ehrhardt]

On Fri, Dec 13, 2002 at 02:49:01PM +0100, Eric Botcazou wrote:
> > This transformation is IMHO illegal because there is no way to make the
> > comparison in general equivialent to that in the original for loop.
> > If p is initially 0x7ffffffc the comparison must be treated as unsigned,
> > however, if p is initially 0xfffffffc the comparison must be treated as
> > signed.
> 
> Well-known deficiency of the strength reduction pass (see the testcase 
> testsuite/gcc.c-torture/execute/loop-2e.c which is XFAILed on x86 at -Os).

Thanks for the clarification. This means that we can close the report?
I can confirm that using -fno-strength-reduce fixes the problem.

    regards  Christian

-- 
THAT'S ALL FOLKS!

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Eric Botcazou]

> Thanks for the clarification. This means that we can close the report?

'Suspended' is probably better.

> I can confirm that using -fno-strength-reduce fixes the problem.

The culprit is actually not the strength reduction pass per se, but the 
induction variable elimination pass that is bundled with it.

-- 
Eric Botcazou

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Andrew Haley]

Christian Ehrhardt writes:
 > 
 > http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=7799
 > 
 > Hi,
 > 
 > this PR is about the following code snippet that is miscompiled with -Os
 > 
 > void fill (int* p, int* q[10])
 > {
 >         int i;
 >         for (i = 0; i < 10; i++)
 >                 *q++ = &p[i];
 > }
 > If p is initially 0x7ffffffc the comparison must be treated as unsigned,
 > however, if p is initially 0xfffffffc the comparison must be treated as
 > signed.

How can p be initially 0xfffffffc ?  On an x86 you'd wrap around zero
and the next &p[i] would return a null pointer.  

malloc() won't return a block of memory that includes address zero.
The only way you could get such an address is to cast an int to a
pointer, in which case it's your responsibility to make sure the
address is valid.

Andrew.

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Christian Ehrhardt]

On Fri, Dec 13, 2002 at 01:57:56PM +0000, Andrew Haley wrote:
> Christian Ehrhardt writes:
>  > void fill (int* p, int* q[10])
>  > [ ... ]
>  > If p is initially 0x7ffffffc the comparison must be treated as unsigned,
>  > however, if p is initially 0xfffffffc the comparison must be treated as
>  > signed.
> 
> How can p be initially 0xfffffffc ?

By calling fill ((int*) 0xffffffc, q);

> The only way you could get such an address is to cast an int to a
> pointer, in which case it's your responsibility to make sure the
> address is valid.

I think you missed the point. The memory pointed to by p is never
accessed.

       regards   Christian

-- 
THAT'S ALL FOLKS!

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Andreas Schwab]

"Christian Ehrhardt" <ehrhardt@mathematik.uni-ulm.de> writes:

|> On Fri, Dec 13, 2002 at 01:57:56PM +0000, Andrew Haley wrote:
|> > Christian Ehrhardt writes:
|> >  > void fill (int* p, int* q[10])
|> >  > [ ... ]
|> >  > If p is initially 0x7ffffffc the comparison must be treated as unsigned,
|> >  > however, if p is initially 0xfffffffc the comparison must be treated as
|> >  > signed.
|> > 
|> > How can p be initially 0xfffffffc ?
|> 
|> By calling fill ((int*) 0xffffffc, q);

Undefined behaviour.

|> > The only way you could get such an address is to cast an int to a
|> > pointer, in which case it's your responsibility to make sure the
|> > address is valid.
|> 
|> I think you missed the point. The memory pointed to by p is never
|> accessed.

The pointer itself must be valid, independent of how you use it.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Segher Boessenkool]

Christian Ehrhardt wrote:
> 
> void fill (int* p, int* q[10])
> {
>         int i;
>         for (i = 0; i < 10; i++)
>                 *q++ = &p[i];
> }
> 
> The asm-Code is this:
> 
>         pushl   %ebp
>         movl    %esp, %ebp
>         movl    8(%ebp), %eax
>         movl    12(%ebp), %edx
>         leal    36(%eax), %ecx
> .L6:
>         movl    %eax, (%edx)
>         addl    $4, %eax
>         addl    $4, %edx
>         cmpl    %ecx, %eax
>         jle     .L6
>         popl    %ebp
>         ret

[SNIP]

> This transformation is IMHO illegal because there is no way to make the
> comparison in general equivialent to that in the original for loop.
> If p is initially 0x7ffffffc the comparison must be treated as unsigned,
> however, if p is initially 0xfffffffc the comparison must be treated as
> signed.


From C99 final draft (I wish I had the final version of the standard):

6.5.2.1.2

	A postfix expression followed by an expression in square brackets []
	is a subscripted designation of an element of an array object. ...

So  p[i]  refers to an array element.


6.2.5.19:
	... An array type describes a contiguously allocated nonempty set of
	objects with a particular member object type, called the element
	type. ...

So an array can not wrap around address 0.


6.5.6.8

	When an expression that has integer type is added to or subtracted from
	a pointer, the result has the type of the pointer operand. ...

	... If both the pointer operand and the result point to elements of the
	same array object, or one past the last element of the array object, the
	evaluation shall not produce an overflow; otherwise, the behavior is
	undefined. ...

So, if  p == 0xfffffffc  , the behaviour is undefined, as, for example,  &p[9]
doesn't point to the same array as  p  .

The comparison should always be unsigned; I don't remember the x86 ISA well
enough to know if  jle  is unsigned, but I believe so.

What am I missing / does C90 behave otherwise?


Regards,

Segher

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Christian Ehrhardt]

On Thu, Dec 19, 2002 at 05:33:49PM +0100, Segher Boessenkool wrote:
> > This transformation is IMHO illegal because there is no way to make the
> > comparison in general equivialent to that in the original for loop.
> > If p is initially 0x7ffffffc the comparison must be treated as unsigned,
> > however, if p is initially 0xfffffffc the comparison must be treated as
> > signed.
> 
> >From C99 final draft (I wish I had the final version of the standard):
> > [ arrays can't wrap around address 0 ]

Thanks. Others pointed this out as well.

> The comparison should always be unsigned; I don't remember the x86 ISA well
> enough to know if  jle  is unsigned, but I believe so.

That's the point: jle is signed. jbe is unsigned. The signedness of the
comparison is derived from the type of i which is wrong after elimination
of the loop variable.

    regards   Christian

-- 
THAT'S ALL FOLKS!

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Joern Rennecke]

> 6.2.5.19:
>         ... An array type describes a contiguously allocated nonempty set of
>         objects with a particular member object type, called the element
>         type. ...
>
> So an array can not wrap around address 0.

It can't wrap around there, but if pointers are signed, it might straddle 0
nonetheless.  This requires, of course, for an aligned start address
that the address 0 is not the same as NULL, which AFAICR is something gcc
doesn't currently support.

OTOH, if the start address is not aligned to a multiple of the types size,
you can have the array straddle address 0 without it ever being a valid
address.  Well, that is if character pointers have a different
representation ;-)

Re: optimization/7799: [3.2/3.3 regression] Loop bug with optimization flag -Os in gcc

[Robert Dewar]

> It can't wrap around there, but if pointers are signed, it might straddle 0
> nonetheless.  This requires, of course, for an aligned start address
> that the address 0 is not the same as NULL, which AFAICR is something gcc
> doesn't currently support.

Note that addresses *are* considered signed on the INMOS Transputer as a
proof of existence :-)