RE: gcc 3.3 / i386 / -O2 question

RE: gcc 3.3 / i386 / -O2 question

[Beschorner Daniel]

Thanks a lot for your effort to all who tested this code with me!
There is some evidence for a SuSE linux specific problem in my GCC 3.3.3,
cause all others could compile it fine even with -O2.

Daniel

RE: gcc 3.3 / i386 / -O2 question

[Gerald Pfeifer]

On Tue, 16 Nov 2004, Beschorner Daniel wrote:
> Thanks a lot for your effort to all who tested this code with me!
> There is some evidence for a SuSE linux specific problem in my GCC 3.3.3,
> cause all others could compile it fine even with -O2.

Fixed in the SUSE LINUX 9.2 system compiler:

  % gcc -v
  Reading specs from /usr/lib/gcc-lib/i586-suse-linux/3.3.4/specs
  Configured with: ../configure --enable-threads=posix --prefix=/usr 
  --with-local-prefix=/usr/local --infodir=/usr/share/info 
  --mandir=/usr/share/man --enable-languages=c,c++,f77,objc,java,ada 
  --disable-checking --libdir=/usr/lib --enable-libgcj 
  --with-gxx-include-dir=/usr/include/g++ --with-slibdir=/lib 
  --with-system-zlib --enable-shared --enable-__cxa_atexit i586-suse-linux
  Thread model: posix
  gcc version 3.3.4 (pre 3.3.5 20040809)
  % gcc x.c -O ; ./a.out
  -1343238496
  % gcc x.c -O2 ; ./a.out
  -1343238496

Gerald

RE: gcc 3.3 / i386 / -O2 question

[Dave Korn]

> -----Original Message-----
> From: gcc-owner On Behalf Of Gerald Pfeifer
> Sent: 17 November 2004 01:01

> On Tue, 16 Nov 2004, Beschorner Daniel wrote:
> > Thanks a lot for your effort to all who tested this code with me!
> > There is some evidence for a SuSE linux specific problem in 
> my GCC 3.3.3,
> > cause all others could compile it fine even with -O2.
> 
> Fixed in the SUSE LINUX 9.2 system compiler:
> 
>   % gcc -v
>   Reading specs from /usr/lib/gcc-lib/i586-suse-linux/3.3.4/specs
>   Configured with: ../configure --enable-threads=posix --prefix=/usr 
>   --with-local-prefix=/usr/local --infodir=/usr/share/info 
>   --mandir=/usr/share/man --enable-languages=c,c++,f77,objc,java,ada 
>   --disable-checking --libdir=/usr/lib --enable-libgcj 
>   --with-gxx-include-dir=/usr/include/g++ --with-slibdir=/lib 
>   --with-system-zlib --enable-shared --enable-__cxa_atexit 
> i586-suse-linux
>   Thread model: posix
>   gcc version 3.3.4 (pre 3.3.5 20040809)
>   % gcc x.c -O ; ./a.out
>   -1343238496
>   % gcc x.c -O2 ; ./a.out
>   -1343238496


  Excuse me for butting in, but I don't understand what makes anyone think this
code _ought_ to produce the same results at different -O levels[*].  The C
language spec is explicit that this is undefined behaviour.  I really can't
understand why people are insisting that multiplying lots of positive numbers
together is somehow *supposed* to produce a negative result and the compiler is
somehow "doing something wrong" if it doesn't.

  The C language spec is completely explicit on this.  The compiler is entitled
to generate code that is only valid under the assumption that the C code being
compiled is valid.  Undefined behaviour means exactly that; the compiler is a
data-processing tool, and if the data you feed it with (the C source) is
garbage, you get GIGO.

int H(int X, int Y)
{
        return X*Y;
}
int main()
{
        A=B=C=100000;
        A+=H(B,C);

  Could _anyone_ who thinks there is a real issue here _please_ tell me what
they think the *correct* value of A should be after this statement, and why?
And whether they think it should do the same on a system that uses an underlying
ones-complement integer representation?

  Now what would be more interesting would be to repeat the test with unsigned
ints.  They _are_ supposed to have well-defined overflow behaviour.


    cheers, 
      DaveK

[*] Or even at the same -O level after different compilations.  Or even on
successive runs of the generated executable.  Or whether it should necessarily
produce any results at all.  Or anything.
-- 
Can't think of a witty .sigline today....

Re: gcc 3.3 / i386 / -O2 question

[Luca Benini]

Dave Korn wrote:
>   Excuse me for butting in, but I don't understand what makes anyone think this
> code _ought_ to produce the same results at different -O levels[*].  The C
> language spec is explicit that this is undefined behaviour.

As every software that do data-processing you need it will reproduce the 
same behavior with any not-altering-semantic-option.
Well if you put garbage in you will obtain garbage out, but the problem 
can raise if the garbage generation is not deterministic.

If the code is syntattical garbage ===> compiler don't compile it
if the code is semantical garbage ===> same compiler must generate the 
same output (in .s or in .o) ==> you must obtain the same result.

or not?


Luca Benini

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Luca Benini wrote:

> If the code is syntattical garbage ===> compiler don't compile it
> if the code is semantical garbage ===> same compiler must generate the 
> same output (in .s or in .o) ==> you must obtain the same result.
> 
> or not?

not!

Languages like C define an entire class of programs which are syntactically
correct, but whose semantics are undefined. Undefined means undefined. Your
assumption that such undefined behavior is deterministic, and should be
independent of optimization level is just wrong.

Let me give a simple example. It's the case that we find is most common
when people report a "bug" in the compiler after observing different
behavior when optimization is turned on.

If you have an uninitialized variable, and you access this uninitialized
value, the value that you get is undefined.

Now with optimization off, you are often lucky, the value is stored in
memory, which happens to be zero, or some other "ok" value.

When you optimize, the compiler may choose to place the value in a register,
and suddently you get a garbage value that was whatever was previously in
that register (which might well be a non-deterministic value, e.g. if
you just read the value of the time of data into that register).

Actually things can get a whole lot worse. Compilers are entitled,
as David noted, to assume a program is correct. Consider:

	int num_password_attempts;   /* oops forgot to initialize to zero */

         .. read password

         if (password == magic_value) { ... delete system disk ...}
         else {
            num_password_attempts++;
            .. try again
	}

A compiler can assume that password == magic_value without doing the
test. Why? Because the value of the variable is undefined, which means
that if it is incremented, it may overflow and anything might happen,
including doing whatever you do when the condition is true, so why not
just assume it is true.

Of course that's a pathology, but the general principle is that the
optimizer can assume your program is correct, and if it is not, all
sorts of horrible things can happen.

To enforce the kind of restriction you have in mind (deterministic
behavior + no change in behavior on optimization) would significantly
degrade the efficiency that can be achieved in generating good code.

Note that this is not a potshot at C. Even Ada, designed to be a safe
language, has such cases, since Ada compilers are expected to be able
to generate highly efficient code. It is true that Ada is better than
C in this respect (e.g. an overflow causes well defined deterministic
behavior in raising an exception). But to go all the way has a real
cost. Java does go all the way here to defined deterministic semantics,
and indeed a significant price is paid for this decision.

Note that it would be possible to have a C or Ada compiler that did
make the decision to provide totally determinstic well defined
results at the expense of efficiency. You can get some of these
effects now. For instance, in GNAT, if you use the pragma
Initialize_Scalars, you can eliminate all non-determinism that
comes from uninitialized variables.

There is of course a trade off in compiler implementation between
following the standard on the one hand, and minimizing surprises
on the other, and sometimes, we do make the decision to degrade
the code to avoid suprises.

For example, IBM compilers for the Power architecture decide that
when you are optimizing single precision fpt stuff, they should not
put stuff in registers and silently provide extra precision when
optimizing, even though languages like Fortran allow enough
freedom in fpt semantics to permit this. It is simply too
worrisome for people to get different results when they
optimize. Of course if this happens, and the differences are
significant, it means that the algorithms are suspicious, but
people prefer repeatable results in this case, even if they
are wrong :-)

Re: gcc 3.3 / i386 / -O2 question

[Sriharsha Vedurmudi]

When I run this program:

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

int H(int X, int Y)
{
         return X*Y;
}
int main()
{
	int A,B,C;
         A=B=C=100000;
         A+=H(B,C);
	printf("\nA = %d\n",A);

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

I always get: 1410165408, irrespective of whether I use O0 or O2.

I am using:
------------------------------------------------------------
bash-2.05b$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix 
--disable-checking --host=i386-redhat-linux --with-system-zlib --enable-__cxa_atexit
Thread model: posix
gcc version 3.2 20020903 (Red Hat Linux 8.0 3.2-7)
bash-2.05b$
------------------------------------------------------------

So, I am not able to reproduce the original complaint itself....


Sriharsha.


-- 
  *****************************
  * Sriharsha Vedurmudi			
  * Software Engineer		
  *
  * Redpine Signals Inc.	
  * Gate #395, Plot 87,88			
  * Sagar Society, Road #2,
  * Banjara Hills,		
  * Hyderabad - 500 034			
  * www.redpinesignals.com	
  *							
  * +91-40-23559911  (Office)
  * +91-9849133133   (Mobile)
  *****************************

Re: gcc 3.3 / i386 / -O2 question

[Luca Benini]

Robert Dewar wrote:

> not!

Now I see the light.


But in this case the asm produced are not the same.




Luca Benini

RE: gcc 3.3 / i386 / -O2 question

[Dave Korn]

> -----Original Message-----
> From: Luca Benini [mailto:lbenini@csr.unibo.it] 
> Sent: 17 November 2004 11:41

> Robert Dewar wrote:
> 
> > not!
> 
> Now I see the light.
> 
> 
> But in this case the asm produced are not the same.


  If the compiler had to produce the exact same asm at -O0 and -O2, how on earth
could one be optimised more than the other?


    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....

RE: gcc 3.3 / i386 / -O2 question

[Dave Korn]

> -----Original Message-----
> From: gcc-owner On Behalf Of Dave Korn
> Sent: 17 November 2004 11:58

  Just to enlarge slightly on my own response:

> > -----Original Message-----
> > From: Luca Benini 
> > Sent: 17 November 2004 11:41
> 
> > Robert Dewar wrote:
> > 
> > > not!
> > 
> > Now I see the light.
> > 
> > 
> > But in this case the asm produced are not the same.
> 
> 
>   If the compiler had to produce the exact same asm at -O0 
> and -O2, how on earth
> could one be optimised more than the other?


   More than that: we all agree that the compiler is entitled to make
assumptions that the input code is valid, and that if those assumptions are
wrong the output code the compiler produces will be wrong.

  Now if you add increasing amounts of optimisations to the compilation (as when
you go from -O0 to -O2), each of those extra optimisations makes further
assumptions about the validity of the code.  So when the code is invalid, more
assumptions are violated at -O2 than at -O0; so it is only to be expected that
the output code will be invalid in more and different ways.

  It might perhaps be possible to rewrite the optimisers so the code they
generated always failed in the same way when the compiler was fed with bad
input, but it would 1) cost a large amount of man-hours of work, and 2) involve
not allowing the optimisers to make (as many of) those assumptions, which would
in turn lead to 3) far less identifiable opportunities for optimisations when
the compiler was fed with good code.

  So it would comprehensively not be worth the effort to make gcc give code that
produced the same results when fed with this bad code.

  However as I mentioned, the behaviour of unsigned integers in overflow
conditions IS well defined, and so if the compiler produced code that behaved
differently at -O0 and -O2 when you took that example code and changed "int" to
"unsigned int" everywhere, that *would* be a genuine compiler bug, and one that
would need fixing.



    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....

Re: gcc 3.3 / i386 / -O2 question

[Steven Bosscher]

On Nov 17, 2004 12:13 PM, Luca Benini <lbenini@csr.unibo.it> wrote:

> Dave Korn wrote:
> >   Excuse me for butting in, but I don't understand what makes
> > anyone think this code _ought_ to produce the same results at
> > different -O levels[*].  The C
> > language spec is explicit that this is undefined behaviour.
> 
> As every software that do data-processing you need it will
> reproduce the 
> same behavior with any not-altering-semantic-option.

Hah, but there you are.  Define "non-altering-semantic-option"
for something that according to the standard does not *have* 
semantics.


> If the code is syntattical garbage ===> compiler don't compile it

Right.


> if the code is semantical garbage ===> same compiler must generate the 
> same output (in .s or in .o) ==> you must obtain the same result.

Wrong, IMHO.

Remember, "Undefined behavior" is not the same thing as "Unspecified
behavior".  In the latter case, perhaps you're right.  Unspecified
behavior should be consistent independent of the compiler options
(and this behavior should be documented).  But for undefined behavior
you shouldn't expect anything.

Gr.
Steven

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Luca Benini wrote:

> But in this case the asm produced are not the same.

Can you say what you mean here, certainly you expect
optimization to change the "asm produced"

Re: gcc 3.3 / i386 / -O2 question

[Joseph S. Myers]

On Wed, 17 Nov 2004, Steven Bosscher wrote:

> Remember, "Undefined behavior" is not the same thing as "Unspecified
> behavior".  In the latter case, perhaps you're right.  Unspecified
> behavior should be consistent independent of the compiler options
> (and this behavior should be documented).  But for undefined behavior
> you shouldn't expect anything.

No, it's implementation-defined behavior that is documented.  Unspecified 
behavior has bounds of variation but need not be documented.  For example, 
in evaluating "x = f() + g()", the order in which f() and g() are 
evaluated is unspecified and could vary with compiler options, but their 
evaluation is not interleaved.

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Dave Korn wrote:

>   However as I mentioned, the behaviour of unsigned integers in overflow
> conditions IS well defined, and so if the compiler produced code that behaved
> differently at -O0 and -O2 when you took that example code and changed "int" to
> "unsigned int" everywhere, that *would* be a genuine compiler bug, and one that
> would need fixing.

Indeed! In fact I would not even use the term overflow in conjunction with
unsigned, the unsigned semantics is modular, and there is no overlow :-)

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Steven Bosscher wrote:

> Hah, but there you are.  Define "non-altering-semantic-option"
> for something that according to the standard does not *have* 
> semantics. 

Reminds me of a famous exchange in the discussion of Algol-68
semantics at one meeting. Someone asked Charles Lindsay what
undefined meant. He replied that it could mean anything, up
to and including "unimaginable chaos". Geerhardt Goos then
enquired (in a rather emphatic manner) "But how can I implement
unimaginable chaos in my compiler?") :-)

One interesting paragraph in the Algol-68 report specifies that
at any point in the execution of the program, further elaboration
of the program can be "interrupted", and that if such an
interrupt occurs, further semantics are undefined.

Sounds a bit drastic, until you learn that the paragraph derived
from a discussion of what the situation was if an earthquake
occurred during the execution of a program, causing the
computer to be destroyed. Operating in a formal mode, the
committee decided that they could not have a specification
that would require conforming compilers to ensure against
the possibility of earthquakes :-)

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Joseph S. Myers wrote:
> On Wed, 17 Nov 2004, Steven Bosscher wrote:
> 
> 
>>Remember, "Undefined behavior" is not the same thing as "Unspecified
>>behavior".  In the latter case, perhaps you're right.  Unspecified
>>behavior should be consistent independent of the compiler options
>>(and this behavior should be documented).  But for undefined behavior
>>you shouldn't expect anything.
> 
> 
> No, it's implementation-defined behavior that is documented.  Unspecified 
> behavior has bounds of variation but need not be documented.  For example, 
> in evaluating "x = f() + g()", the order in which f() and g() are 
> evaluated is unspecified and could  vary with compiler options, but their
> evaluation is not interleaved.

Requiring something to be documented does not necessarily constrain
the possible semantics, although the idea here is that it is embarrassing
to have documentation that defines the effect as completely undefined :-)

RE: gcc 3.3 / i386 / -O2 question

[Michael Matz]

Hi,

On Wed, 17 Nov 2004, Dave Korn wrote:

>   Excuse me for butting in, but I don't understand what makes anyone
> think this code _ought_ to produce the same results at different -O
> levels[*].

While it's true that with signed arithmetic we are allowed to simply
break, such behaviour can (and in this case indeed does) point out a real
problem in the optimizers, so its often a bit too hasty to ignore a
problem just because the source code is not totally conformant.  With
unsigned int a similar thing happens, namely that the second call to
H(B,C) is deleted.  The SuSE compiler has unit-at-a-time, hence determines
that H is in fact a const function.  Somehow it misses that C is modified
between the two calls, ergo it thinks that both calls give the same 
results, and deletes the latter.


Ciao,
Michael.

Re: gcc 3.3 / i386 / -O2 question

[Luca Benini]

Dave Korn wrote:
>   If the compiler had to produce the exact same asm at -O0 and -O2, how on earth
> could one be optimised more than the other?

Sorry, but i wasn't clear:
If i compile with a compiler 3.x.y (vanilla) a file i obtain a file.
If i compile with a compiler 3.x.y (suse patch) a file i obtain a file.
in the case that start this thread some compiler version (one vanilla 
and other SUSE) generate 2 distinct file as output.


Luca Benini


P.S.
Sorry 4 my english...

Luca

Re: gcc 3.3 / i386 / -O2 question

[Robert Dewar]

Michael Matz wrote:

> While it's true that with signed arithmetic we are allowed to simply
> break, such behaviour can (and in this case indeed does) point out a real
> problem in the optimizers, so its often a bit too hasty to ignore a
> problem just because the source code is not totally conformant.

Interesting, though to be fair, David a couple of times said that it would
be a good idea to try this code again with unsigned :-)