buggy optimization levels...

[Erik Trulsson]

On Sat, Aug 02, 2003 at 03:52:25PM -0400, Chuck Swiger wrote:
> Erik Trulsson wrote:
> [ ... ]
> >A somewhat contrived example that behaves differently when compiled
> >with -O3 or when compiled with -O2 or lower optimization follows:
> >
> >static int f(int a)
> >    {
> >    return a/0;
> >    }
> >int main(void)
> >    {
> >    int x;
> >    x = f(5);
> >    return 0;
> >    }
> 
> Contrived, but interesting and useful nonetheless; thanks for the response.

Real world examples tend to be a bit more complicated and difficult to
detect, but this was the best I could come up with on short notice, and
it should not be too different in kind from bugs that can actually occur.


> 
> [ ... ]
> >>Even if the code contains a bug, "cc -O" and "cc -O -fgcse" should 
> >>produce the same results.  Excluding certain well-defined exceptions 
> >>(-ffast-math comes to mind), compiler optimizations likes -fgcse are not 
> >>allowed to change the meaning of compiled code, do we agree?
> >
> >Not quite.  Compiler optimization flags (with a few exceptions like
> >-ffast-math) are not allowed to change the semantics of the compiled
> >code.
> 
> I really don't want to debate the use of "meaning" versus "semantics".  :-)

That wasn't my real point anyway. I was trying to refute your statement
that "Even if the code contains a bug, "cc -O" and "cc -O -fgcse"
should produce the same results."

I claim that if the code has a bug that results in undefined behaviour
then the compiler is allowed to produce different results when invoked
with different optimization flags.


> 
> >For buggy code that invokes undefined behaviour (divison by
> >zero, accessing unallocated memory, etc.) there is no semantics to
> >preserve and therefore the compiled code may well produce different
> >results when compiled with different flags.
> 
> C code that permits a divide-by-zero condition will result in a runtime 
> error, but I disagree that this has "no semantics to preserve".  If the 

It hasn't any semantics to preserve. There is no guarantee that a
division-by-zero will result in a runtime error. The C standard defines
what the semantics (or meaning if you prefer) of a C programs is. For
code that executes an integer division-by-zero it is not defined what
the program should do. Therefore *any* result that occurs from running
the code is conforming to the standard.

If you believe differently please tell me what that program *should* do
when run. (Without making any assumptions about which compiler, OS or
hardware is being used.)

> code was using floating point, IEEE 754 defines semantics for 
> divide-by-zero one could also have an 'Infinity' result, but that's not 
> available with ints; your code results in a SIGFPE being generated.

My code results in a SIGFPE when compiled with gcc on FreeBSD using a
certain set of flags. I am sure that if you try it with other
compilers, or on other operating systems you will see different
results.
(If you were to run it under AmigaOS, for example, you would probably
get a system crash with an error code indicating an integer
division-by-zero.  Other systems might well just ignore such a division.)

Programs that have undefined behaviour will very often behave
differently when compiled with different compilers, so the fact that
one compiler invoked with different flags will give different results
is not surprising.

> 
> >(Undefined behaviour in the context of the C standard means the
> >compiler is allowed to do whatever it damn well pleases, including, but
> >not limited to, doing what you wanted and expected it to do, formatting
> >your harddisk or making demons fly out of your nose.
> 
> Sure.  I see and acknowledge the validity of your point: it's possible for 
> a programmer to write code which has different behavior depending on (say) 
> -finline-functions.
> 
> However, that being said, the fact that the C standard says such-and-such 
> gives "undefined behavior" does not preclude the implementation from 
> defining the behavior for such-and-such.

Of course it doesn't preclude that, but few implementations actually
does define what the behaviour will be for such cases, and code
depending on such implementation-specific behaviour is highly
non-portable anyway.

> 
> >>If there exists any lexically correct input source code (ie, which parses 
> >>validly) where compiling with -fgcse results in different behavior, that 
> >>optimization is unsafe and should not be enabled by -O2 in any 
> >>circumstance.
> >
> >With that definition just about *all* optimizations would be unsafe.
> >
> >(And optimization is actually *supposed* to give different behaviour. 
> >The running time of a program is part of its behaviour and
> >optimization is generally supposed to reduce the running time, thereby
> >giving different behaviour.)
> 
> What you say is so obviously correct that one should instead conclude that 
> my use of the term 'behavior' with regard to compiler optimizations has a 
> more specific meaning.

Generally yes. (Of course people involved with hard real-time systems
will probably be very interested in how optimizations interact with
running time and will regard changes in that aspect of the programs
behaviour to be crucial.)

> 
> Page 586 of _Compilers: Principles, Techniques, and Tools_ states:
> 
> First, a transformation must preserve the meaning of programs.  That is, an 
> "optimization" must not change the output produced by a program for a given 
> input, or cause an error, such as a division by zero, that was not present 
> in the original program.  The influence of this criterion prevades this 
> chapter; at all times we take the "safe" approach of missing an opportunity 
> to apply a transformation rather than risk changing what the program does.
> 
> 	--
> 
> Like your divide-by-zero example above, or this paragraph about "semantics" 
> vs "meaning", I'm not going to disagree if you want to state that the 
> running time of a program is part of the "behavior".  However, using the 
> terms in such a fashion precludes you from understanding the intended 
> meaning in this particular context.

I understand the intended meaning. I just don't agree completely with
your reasoning.   I would say that the compiler is not allowed to
*introduce* errors, or to change the meaning of *correct* programs.
(Correct here essentially meaning programs that do not invoke undefined
behaviour.)  For programs that do not have a defined 'meaning' the
compiler is free to do anyting.

If a compiler was not allowed to change the result of running a program
having undefined behaviour when compiled with different optimization
flags, then this would preclude doing just about any optimization.

I am fairly certain that for *all* the specific optimizations available
in gcc it is possible to find *some* program that will give different
results depending on if that optimization ws used or not.

If one were to accept your claims that the compiler should not perform
any optimizations that could change the behaviour any program, then it
would not be able to do any optimization at all, which is clearly not a
desirable situation.


The reason why the C standard does not define the behaviour of certain
constructions or code sequences, and why compilers give different
results when compiling such code, is that doing so allows compilers to
perform more aggressive optimizations on correct code.



Anyway, the point I was originally trying to make is that if programs
exhibit buggy behaviour when compiled with higher optimization levels
it is more often due to a bug in that program than due to a bug in the
compiler (even though the latter also can occur).
Therefore trying to remove various optimizations from the set of
optimizations used under -O2 (e.g.) is often a case of "throwing out
the baby with the bathwater" in that the bug probably wasn't in the
compiler in the first place and disabling the optimization just meant
that a lot of other code will not be optimized as well.
(And turning off optimizations can actually trigger some bug in some
other program that previously had been hidden by that same
optimization.)



-- 
<Insert your favourite quote here.>
Erik Trulsson
ertr1013 at student.uu.se