compiler bugs
Sid Touati
well known verification techniques ?
I am afraid that many bugs are hidden inside compiler activated with
sophisticated optimisation options, and few people can detect them: when
a user program does not work, we usually think that the problem comes
from the program itself, not from the compiler nor from the processor.
On the other hand, when a compilation flag is on and the program
crashes, we usually think that the bug comes from the compiler not from
the program...
Hans-Peter Diettrich
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
The most general method:
Reduce the code, where you observed an possible compiler bug, until you
have a small program to reproduce the error. Then give that program to
the compiler writers.
The most sophisticated method:
Use an decompiler to re-create the source code from the executable, and
search for differences. A decompiler may find erroneous machine code
itself, when the code is not reducible to high-level statements and
expressions.
There exist many other methods in between, like inspecting the
disassembled source code for obvious errors. This is what a decompiler
will do automatically.
A simple method is using another compiler, or other optimization
options, to find out different behaviour of the executables. But this is
a weak method, sensitive to uninitialized variables, wild pokes and
other coding errors.
DoDi
Jeremy J Starcher
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ? ...
Since you didn't say what language or compiler you are using, I can only
answer in very general terms.
In some circumstances, optimizers are known to break code. Sometimes by
optimizing away side effects. Sometimes causing heisen-bugs by changing
the order of evaluations and sometimes by tripping over "clever" code.
That said, when I come across a problem, I always assume the bug is in my
code until I can provide a test case that clearly demonstrates that the
compiler itself is at fault. Then I have someone else review my code to
make sure I'm not being an idiot.
Louis Krupp
Identifying compiler bugs is usually a lot of work. Start with a
program that fails somewhere in its thousands of lines of code, and
spend the next few hours removing pieces until you have a minimal
program that reproduces the problem (or at least a problem -- there
could be more than one). In the early 90's, I spent a few years as a
contractor porting C++ code from one buggy compiler to another, so I
saw a lot of these. In one case, a C compiler generated bad code when
the program used a pointer to a function that took a float argument.
A later version of the compiler would have worked, but the customer
was too cheap to upgrade. I think I spent about 12 straight hours on
that one.
You'll need to be able to read compiler-generated assembly code.
Ironically, you won't need to be an expert in the compiled language; I
used the Annotated Reference Manual a lot, but by the time I got a C++
file down to the 20 lines or so needed to demonstrate the problem, it
was pretty obvious that there was a bug.
It's all worth it when you can send a description of the problem and
some sample code to the vendor, and it gets fixed.
(This was all a *lot* more fun years ago when I worked on Burroughs
Large Systems and they shipped the source code and I could fix some of
these in the field and report the problem to Mission Viejo along with
my suggested patch.)
Louis
Jonathan Thornburg
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
There are some useful ideas in
Flash Sheridan
"Practical testing of a C99 compiler using output comparison"
Software--Practice and Experience volume 37 (2007), pages1475--1488
ciao,
--
-- "Jonathan Thornburg [remove -animal to reply]" <jth...@astro.indiana-zebra.edu>
Dept of Astronomy, Indiana University, Bloomington, Indiana, USA
"C++ is to programming as sex is to reproduction. Better ways might
technically exist but they're not nearly as much fun." -- Nikolai Irgens
[Too bad SPE now costs $3278/yr. -John]
j...@cix.compulink.co.uk
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
If there is, I don't know it. Compiler writers generally test their
compilers quite hard - there are various test suites of source code
available, and all serious compiler writing organisations will develop
test sets of their own and expand them as they fix bugs - but there is
no simple and all-embracing method.
> I am afraid that many bugs are hidden inside compiler activated with
> sophisticated optimisation options, and few people can detect them:
> when a user program does not work, we usually think that the problem
> comes from the program itself, not from the compiler nor from the
> processor.
>
> On the other hand, when a compilation flag is on and the program
> crashes, we usually think that the bug comes from the compiler not
> from the program...
I take it you mean that when you change some compilation option and
the program crashes, you suspect the compiler. At that point, the
compiler is a target for suspicion, but not the only one. There can be
a code bugs that fail to show up under the conditions where the
program was developed, but will do so under different conditions.
A classic C example is declaring an array in function scope, and
accessing off the end. If the memory you access isn't used for
anything else, the program may well work. A different compiler or
different optimisation may well arrange the variables of the function
differently, so that now the off-the-end access tramples some other
variable in a way that shows. The bug was much older than the change
of compiler, and it's not the compiler's fault at all.
I've had a fair amount of experience of digging out compiler bugs,
because my employment consists largely of porting a large and
complicated piece of software that can be tested quite
thoroughly. Every time we use a new or updated compiler, we expect to
find a few code bugs that never showed up before, and a few compiler
bugs too. Modern compilers seem much more reliable than those of 20
years ago, but they are not perfect, and eventual perfection seems
most unlikely. We try quite hard to report the compiler bugs we find,
in a usable way, and this may have a lot to do with the apparent
increase in reliability that we see.
The basic process is easy to describe, but much harder to carry
out. I'm going to assume C or C++ below, because they're what I'm used
to doing:
First, find out what's actually going wrong. This doesn't mean "Test
Foo-bar-2345 crashes when file mad_algorithm_17.cpp is compiled at -O3
or higher", although that may well be a step towards finding out
what's going on. It means finding out which variables or expressions
are going bad. This involves a load of painstaking debugging, which
has to be done very, very carefully. It is likely to involve the
discovery of workarounds along the way, such as reducing optimisation
level or re-arranging code, but this is only likely, not
certain. Everything that follows depends on doing this right. Expect
it to take several days, not half an hour, although it gets quicker
with practice.
Second, you need to be able to reproduce the problem in a completely
standalone piece of code that is not part of your project. The
preferred way to do it is a simple standalone program that uses only
system headers (or equivalent for other languages) and demonstrates
the problem. Submit this with /everything/ needed to recreate the
compilation. This includes all the compiler and linker options (I
prefer to write a shell script or batch file that does the job,
because that's more explicit than an IDE project file usually is), the
precise version of the compiler that you're using, the exact operating
system that you are running on, and so on.
If you can't make a standalone program, there is another way to do it,
but it requires learning the assembly language for the platform. If
you can read the assembler generated by the compile and figure out
what's wrong in the generated code, submitting a heavily annotated
assembly listing explaining the problem, along with the source file
that you compile to create it, and all the supporting details, usually
seems to be acceptable. MS, Intel, HP and Sun have taken them from me
and fixed the bugs, anyway.
This is not easy work. If you can do it, without being driven mad in
the process, it is very worthwhile. Compiler manufacturers become fond
of you, because you report bugs that they can actually find and fix,
as opposed to most of what they get. But it is a job where half-
measures are pointless. You have to make absolutely everything totally
and unambiguously explicit. You have to nail things down so thoroughly
so that a team of US lawyers being paid millions couldn't pick holes
in it. Someone who programs by grabbing examples and pasting them
together, and gets bored if he can't solve a bug in half an hour
should not take up this game.
One compiler manufacturer whose product I'd given up using because it
had too many bugs asked for a set of source and basic tests, and gave
it to one of their engineers to nail down the compiler bugs. From the
reports I got, he simply found out each source file that was causing a
problem, and handed them over to the compiler team with the
explanation "something goes wrong in here". That is no use to anyone,
and the compiler team just ignored him.
John
Quinn Tyler Jackson
> That said, when I come across a problem, I always assume the bug is in my
> code until I can provide a test case that clearly demonstrates that the
> compiler itself is at fault.
I can count on one hand the number of genuine compiler bugs I've been able
to isolate and reproduce well enough to report as official bugs. (Even the
so-called optimization bugs turned out to be my violation of some contract
with the compiler, such as aliasing when I oughtn't have.)
That said, I couldn't count in all the bits of a gigabyte how many times
I've heard programmers (including myself) say: "The *($@&&^ compiler is
buggy!"
--
Quinn Tyler Jackson
George Peter Staplin
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
Most assembly code that I know about is not proven correct by any sort
of formal method, or verification technique. There was a research
project that implemented a provably correct assembler, but the code I
looked at was quite strange, and the assembler itself was for an
architecture I don't use IIRC.
> I am afraid that many bugs are hidden inside compiler activated with
> sophisticated optimisation options, and few people can detect them:
> when a user program does not work, we usually think that the problem
> comes from the program itself, not from the compiler nor from the
> processor.
Yes, indeed that's a problem. In some ways rigorous testing may help,
and in other ways it may hinder future changes. You definitely need a
test suite anyway for your compiler to verify the correctness of the
code produced, but as you might expect with languages like assembly,
some things may work unexpectedly due to state not changing that you
didn't expect. If and when you have multiple CPUs to support the
complexity increases.
Consider for example that a register has a value due to a specific
instruction that came before another code pattern that depends on that
value, but didn't explicitly set that value. This kind of bug happens
too often. It may even pass in many cases a torture test.
> On the other hand, when a compilation flag is on and the program
> crashes, we usually think that the bug comes from the compiler not
> from the program...
I agree, and understand. That's why you need great test coverage. My
compilers have been rather simple for the most part, but the tests end
up almost being as large as the compiler itself, when I do it right.
I think in some ways having a more structured design with hypertext,
and multiple layers would help a great deal to express and structure
solutions for the complex problems we face, as NLS has proven. The
NLS system was implemented in the 1960's and they had good ideas. My
belief however about NLS is something that most people don't share in
the computing industry. I have been going forward in my spare time on
a project. My project is focusing on enabling hypertext, layers, and
code constraints applied in a visual way. In fact the constraints
have to be visual to work in any sort of sane and expressable manner.
NLS had MOL (machine-oriented language) as its base. NLS was a very
powerful and interesting system to me, and without it we might not
have the computer mouse. The system allowed managing complexity in
ways I don't think we can do in general now, without more indirection.
-George
Marco van de Voort
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
>
> I am afraid that many bugs are hidden inside compiler activated with
> sophisticated optimisation options, and few people can detect them: when
> a user program does not work, we usually think that the problem comes
> from the program itself, not from the compiler nor from the processor.
Usually it is that way, program bugs are more numerous than compiler
bugs, if only because the compiler is vetted by a multitude of users.
It can be simply that turning on the optimization changes memory
layout that can causes hidden program bugs that mutilate memory
suddenly to become critical.
In general the best idea is to first do usual debugging stuff, like
using fencing heap allocators, turn on options that your compilers
might have (like randomized initialization of variables, range checks,
stack integrity cheching etc), as well as running in tools that can
detect certain classes of errors (like valgrind)
If that doesn't help, you can quickly inspect the assembler if you
have a feeling where the bug might be, and then (as the others already
advised) start narrowing down.
> On the other hand, when a compilation flag is on and the program
> crashes, we usually think that the bug comes from the compiler not
> from the program...
It might be simply that the pointer bugs that surface without
optimization have been fixed during normal development. And the ones
WITH optimization only close to the release point, giving the
impression that the optimizer is very bugged.
Torben Ægidius Mogensen
> How can a simple programmer detect a bug in a compiler ? is there some
> well known verification techniques ?
There have been research projects about verifying the correctness of
compilers, but they have (to my knowledge) all been for fairly simple
compilers. You will, basically, have to build the compiler with
verification in mind to have any chance of doing this.
Another approach is to make a verifying compiler: One that checks the
correctness of each compiled program. This way, you don't prove that
the compiler is correct, but you catch "bad" programs.
These techniques are, however, sot for "simple programmers" (whatever
that means). Also, these techniques need formal specifications of
both the source language and the target machine. And it is often the
case that such formal specifications themselves have bugs, so you just
move the problem to a higher level of abstraction, unless you define
the language by it formal semantics.
> I am afraid that many bugs are hidden inside compiler activated with
> sophisticated optimisation options, and few people can detect them: when
> a user program does not work, we usually think that the problem comes
> from the program itself, not from the compiler nor from the processor.
And that is also the most likely case.
> On the other hand, when a compilation flag is on and the program
> crashes, we usually think that the bug comes from the compiler not from
> the program...
Even if your program changes behaviour when you turn on optimisation
flags, this may not imply faults in the compiler, just that the
language has a weak specification that leaves, say, the order of
evaluating function arguments up to the compiler. The non-optimising
compiler may just evaluate in order, while an optimising compiler may
rearrange the order for better scheduling or such. If some of the
arguments have side effects, this can change program behaviour.
If you use floating point computations and the language definition is
not specific about evaluation order and precision, optimisation may
change the precision of your calculations which may cause subsequent
program behaviour to diverge (two values that test equal without
optimisation may test not equal afterwards, or vice-versa).
That said, compilers are very large and complex pieces of software and
incredibly difficult to test, since you can't normally validate the
correctness of the output -- the best you can do is to test the
output, so your tests are more indirect than if you test, say, a
sorting functin where you can fairly easily verify that the output is
a sorted permutation of the input.
So, it is not unlikely that there are errors in your compiler. The
unlikely part is that you will be the first to notice the errors. Not
only are compilers tested rather thoroughly, but if a compiler is in
wide usage, most bugs are bound to show up fairly quickly. It is
normally only when you program in a very unusual style or push the
limits of the language that you find new bugs.
If you are convinced that the problem is not in your program, you
should (as other posters have said) reduce your program to the
smallest possible that still shows the problem and only then report
the problem to the compiler vendor. If the vendor agrees that it is,
indeed, a bug in the compiler, they are likely to ask to add your
program to their test suite, so subsequent versions of the compiler
test for this problem.
Torben
Tony Finch
>
>How can a simple programmer detect a bug in a compiler ? is there some
>well known verification techniques ?
There's a brillant paper by Eric Eide and John Regehr from the University
of Utah where they use a clever variant of fuzz testing to find bugs in
the way compilers implement C's volatile storage qualifier. They use
a code generator to create random programs, and they instrument their
execution to find out their memory access patterns. They detect compiler
bugs by compiling the programs with different optimisation levels and
seeing when the access patterns differ.
http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
Tony.
--
f.anthony.n.finch <d...@dotat.at> http://dotat.at/
Derek M. Jones
>> How can a simple programmer detect a bug in a compiler ? is there some
>> well known verification techniques ?
>
> If there is, I don't know it. Compiler writers generally test their
> compilers quite hard - there are various test suites of source code
> available, and all serious compiler writing organisations will develop
> test sets of their own and expand them as they fix bugs - but there is
> no simple and all-embracing method.
The part of the test suites (eg, Perennial) that compiler writers
uses is often only the part that checks the syntax and semantics.
While code generation stress testers might be included they are
used less frequently.
See
http://shape-of-code.coding-guidelines.com/2009/03/volatile-handling-sometimes-overly-volatile/
for a discussion of one area where compiler correctness seems to be
suspect.
glen herrmannsfeldt
>> How can a simple programmer detect a bug in a compiler ? is there some
>> well known verification techniques ?
> If there is, I don't know it.
Best is to find the smallest program that demonstrates the bug, and
that you can verify satisfies the appropriate language standard.
> Compiler writers generally test their compilers quite hard - there
> are various test suites of source code available, and all serious
> compiler writing organisations will develop test sets of their own
> and expand them as they fix bugs - but there is no simple and
> all-embracing method.
I can only think of a few that I have seen over the years, that I
could reduce down and demonstrate with a small program. One was a C
compiler that miscompiled x++ in the case where x was (double). While
legal, presumably it didn't come up in the testing that was done. (If
I remember it right, it compiled as ++x.) I have somewhat of a
tendency to try things that I know are supposed to work, but are less
obvious than others.
-- glen
Jeremy J Starcher
> Jeremy J Starcher said:
>
>> That said, when I come across a problem, I always assume the bug is in
>> my code until I can provide a test case that clearly demonstrates that
>> the compiler itself is at fault.
>
> I can count on one hand the number of genuine compiler bugs I've been
> able to isolate and reproduce well enough to report as official bugs.
> (Even the so-called optimization bugs turned out to be my violation of
> some contract with the compiler, such as aliasing when I oughtn't have.)
For large "well-known" compilers, that is true for me as well.
Back when I was using ZBASIC (A cross-platform compiled basic) I had the
development team on speed-dial and they ended up using our test suite
before sending us anything.
> That said, I couldn't count in all the bits of a gigabyte how many times
> I've heard programmers (including myself) say: "The *($@&&^ compiler is
> buggy!"
Around here I usually hear "The *($@&&^ library is junk. I have to write
my own!"
Walter Banks
> I can count on one hand the number of genuine compiler bugs I've been able
> to isolate and reproduce well enough to report as official bugs. (Even the
> so-called optimization bugs turned out to be my violation of some contract
> with the compiler, such as aliasing when I oughtn't have.)
Good test software is incredibly hard to write often taking more
resources than the compiler function it was meant to test.
It is difficult in many cases to create a simple example of a compiler
bug due to the kind of optimization that is found in many
compilers. It is common that code generation for syntactically
identical sequences to generate substantially different code due to
some overall application consideration. Two simple examples are
spilled registers and even simple instruction addressing modes. (This
alone should be enough to do testing at the optimization level of code
for the final product)
Compiler bugs are a function of the degree of optimization that is in
the compiler. As soon as alternative code generation sequences are
added testing becomes much more complex and the probability of a
customer encountering a compiler bug is higher.
We use both random testing and syntax directed testing with our
compilers because the payoff to effort is high. Both of these
techniques are a single tool in a very large toolbox.
Eric Eide and John Regehr are to be commended for their work on
Volatiles. The success of their work was careful planning on the
design of the random tests and some very good analysis work. Their
paper illustrates just how difficult a simple language feature is to
both implement and validate.
Application specific testing tends to have a high payoff. Using
reference designs and customer application code as part of the
regression tests while tracking compiler generated metrics will tend
to uncover induced bugs as the compiler evolves and will focus effort
to the compiler area's that customers actually will be using.
Regards,
--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com
Chris F Clark
> Sid Touati <SidT...@inria.fr> writes:
>
>> How can a simple programmer detect a bug in a compiler ? is there some
>> well known verification techniques ?
...
> So, it is not unlikely that there are errors in your compiler. The
> unlikely part is that you will be the first to notice the errors.
I would like to amplify this point. At some level, compilers aren't
that different from other programs written by other programmers. So,
think of the kind of bugs you experience.
1) most bugs occur in new code
sometimes the new code stresses old code, but there is an
exponential decay in the numbers of bugs founds per block of
code over time and you can compute things like half-lives to
guess at the number of unfound bugs. (Most compiler code is
also "old", so the number of remaining bugs is diminishing.)
2) most bugs actually cause spectacular failures (or are off-
by-ones); very few bugs give you subtly wrong output
How often do you write code and msake a small error (say
multiplying by 7 when you mean 8, or xor'ing when you mean to
and) that affects everything, but only by a little and is
subtle? It is more likely, you write errors where you
sometimes go 1 place to far or short in a loop or you forget
to initialize something, or you depend on something else
about some other code which just isn't true. Compiler
writers make the same kinds of mistakes.
Thus, if you are to find a bug in the compiler, the most
likely effect is that the compiler will crash. If it doesn't
crash, the code for the common cases (+, -, *, araays, and so
forth) is probably correct. Even the code for most uncommon
cases have probably been explored by someone other than you,
unless you are using a new feature of a compiler.
2) many of the subtle bugs come from using grey-areas, where the
semantics themselves are subtle and one gets them wrong.
For example, I've just been fixing some code of mine where I
was filling up 64 bit structures (on a 32 bit machine) using
bit shifts--the bugs weren't in the compiler, the bugs were
in my using the wrong assumptions about the promotion rules.
People who mention aliasing problems are talking about a
similar effect. Now, these bugs would have been in this
compiler I'm writing, except that they showed up in my unit
testing, and I ensured that I went over all of the relevant
places and fixed them. Is it possible that I left a hole,
yes, but unlikely, and much more unlikely by the time that
even my initial customers see this compiler.
And, this brings up another point, most of the code I've
worked on in most compilers is pretty vanilla. Sure compiler
writer's are geeks and write some code that is too-clever,
but a lot of compiler code just uses arrays and pointer based
data structures (e.g. trees, dags) and integer and boolean
arithmetic. Thus, most the errors tend to be vanilla also.
We have pretty good techniques for catching and preventing
such errors. Most of the compiler code I write checks and
asserts each pointer access (or array bound). This tends to
increase the ratio of spectacular to hidden failures, but
helps me catch more bugs earlier.
And, yes, this list ended without a specific point.
Hope this helps,
-Chris
*****************************************************************************
Chris Clark Internet: christoph...@compiler-resources.com
Compiler Resources, Inc. or: com...@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
-----------------------------------------------------------------------------
Anton Ertl
>Sid Touati <SidT...@inria.fr> writes:
>> crashes, we usually think that the bug comes from the compiler not from
>> the program...
>
>Even if your program changes behaviour when you turn on optimisation
>flags, this may not imply faults in the compiler, just that the
>language has a weak specification that leaves, say, the order of
>evaluating function arguments up to the compiler. The non-optimising
>compiler may just evaluate in order, while an optimising compiler may
>rearrange the order for better scheduling or such. If some of the
>arguments have side effects, this can change program behaviour.
An optimizer that breaks a program is a bad idea. There are
apologists (of program-breaking optimizers) that claim that the
program was already broken without the optimizer, because it does not
conform to some language standard. But actually the program does
conform with the language as it is implemented by the compiler without
optimization and it behaves as intended by the programmer, so it is
correct.
That the program does not conform to some other language specification
should be irrelevant to the optimizer, because the optimizer should
preserve the behaviour of the non-optimizing compiler. Ok, in some
cases this costs a little (e.g., to preserve the order of potential
side effects in the example above), and in some cases it's not
practically possible and would buy very little (e.g., preserving the
exact values of return addresses so an out-of-bounds array read may
get the same value), but in general that's how optimizer writers
should approach the issue.
Otherwise we will soon be back to the bad old days when everybody just
considered turning on the optimizer too risky because it tends to
break programs; and the rhetoric of the apologists won't help, because
at least for languages like C most (all?) substantial programs don't
conform to the language standard, and there is no cost-effective way
to turn such programs into standard-conforming programs. So if the
optimizer feels free to break such programs, programmers just will
not use the optimizer.
If an optimizer writer also wants to excel on benchmarks by weakening
the semantic guarantees to the lowest common denominator (i.e., the
language standard plus the stuff used in the benchmarks), they can add
special flags for that, say, -Ospec.
- anton
--
M. Anton Ertl
an...@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
Gene
This is an interesting question. Invariably compiler bugs are
discovered at the end of a long _program_ debugging process, when all
the possibilities for bad code have been eliminated.
In my experience, assuming code improvement passes are inherently
buggy is a bit dangerous. One of the 3 or 4 true compiler bugs I've
seen in too many years of code hacking occurred only with all code
improvement options _turned off_.
One moral is that when developing code, unless your debugging and
production build options are exactly alike, you should maintain and
test with both continuously. Don't test with the debugging build,
then think that you'll get away with making a final production build
and shipping. That way lay dragons.
Gene
Christopher Glaeser
> apologists (of program-breaking optimizers) that claim that the
> program was already broken without the optimizer, because it does not
> conform to some language standard. But actually the program does
> conform with the language as it is implemented by the compiler without
> optimization and it behaves as intended by the programmer, so it is
> correct.
Can you please provide us with the list of optimizations that will not
affect the behavior of any program that uses language features that are
defined by the language standard to have undefined behavior?
Best,
Christopher
[I read an interesting article about the IBM Fortran X compiler, an improved
version of the classic Fortran H compiler. The guy who did it made sure that
the new optimized results were always bit identical to what the old compiler
produced. But I don't know whether he extended that to programs that weren't
valid Fortran, e.g., with aliased arrays. -John]
Anton Ertl
>> An optimizer that breaks a program is a bad idea. There are
>> apologists (of program-breaking optimizers) that claim that the
>> program was already broken without the optimizer, because it does not
>> conform to some language standard. But actually the program does
>> conform with the language as it is implemented by the compiler without
>> optimization and it behaves as intended by the programmer, so it is
>> correct.
>
>Can you please provide us with the list of optimizations that will not
>affect the behavior of any program that uses language features that are
>defined by the language standard to have undefined behavior?
*The* list, for all languages? Please contact me for my consultancy
rates:-). Actually, you could make identifying such program-breaking
behaviour an additional service of your business.
Anyway, to give some examples: many forms of constant folding, copy
propagation and common subexpression elimination; but typically a
particular optimization can be performed in a behaviour-preserving way
or in a program-breaking way. E.g., evaluating a constant expression
may result in an exception (e.g., consider "1/0"); proper constant
folding has to preserve that visible behaviour (giving a warning about
the expression may also be a good idea) instead of compiling just
anything because the language standard does not cover this case.
glen herrmannsfeldt
> [I read an interesting article about the IBM Fortran X compiler, an improved
> version of the classic Fortran H compiler. The guy who did it made sure that
> the new optimized results were always bit identical to what the old compiler
> produced. But I don't know whether he extended that to programs that weren't
> valid Fortran, e.g., with aliased arrays. -John]
I don't know about Fortran X, but the successor to the original H
was H extended, sometimes called HX. As well as I know it,
H was free but HX was a "program product" (licensed and charged for).
One extension was the REAL*16 and COMPLEX*32, extended precision
floating point data types and corresponding library functions.
One example from the "IBM Fortran IV H Extended Compiler
Programmers Guide": SC28-6852-1_OS_FORTRAN_H_Pgmr_Jun72.pdf
DO 11 I=1,10
DO 12 J=1,10
9 IF(B(I).LT.0) GO TO 11
12 C(J)=SQRT(B(I))
11 CONTINUE
that the compiler (presumably both H and HX) moves the SQRT
out of the J loop, but not the IF statement. That is legal
Fortran that fails, and that IBM knows fails. (As they suggest,
the programmer should move the IF out of the loop, too.)
-- glen
[Yup, HX, same program. I gather HX has the same broken optimizations
that H did. In its defense, Fortran H did have to invent a lot of the
analysis techniques it used, and run on a 128K (for the young folks, yes,
that's a K) machine. -John]
glen herrmannsfeldt
> (John wrote)
> [Yup, HX, same program. I gather HX has the same broken optimizations
> that H did. In its defense, Fortran H did have to invent a lot of the
> analysis techniques it used, and run on a 128K (for the young folks, yes,
> that's a K) machine. -John]
If it generates bit compatible output, it would have to have
the same broken optimizations.
I believe, though, that would be 256K, though people I knew
gave it 300K.
IBM uses a binary system similar to roman numerals, where a lower
value to the right is added, and to the left is subtracted.
F is 64K, G is 128K, H is 256K, such that a 192K machine would be
indicated by GF and a 7MB machine by JM. The numbering doesn't work
quite as well for programs, but PL/I (F) was designed to run in 44K on
a 64K machine, leaving 20K for the OS. (That might result in the
symbol table residing on disk. At the end of every run, PL/I (F)
would indicate the smallest region that would keep the symbol table in
main memory.)
As virtual memory became more popular, one common thing to do was to
remove the overlay structure from Fortran H. Load it into the linker
without any OVERLAY control cards, and then write it out again.
-- glen
[Darn those off by one bugs. You're right, it needed a 256K machine
rather than 128K. And like pretty much every other OS program it
ran a lot faster if you had enough storage to undo the origami and
get rid of the overlays. -John]
Christopher Glaeser
> propagation and common subexpression elimination; but typically a
> particular optimization can be performed in a behaviour-preserving
> way or in a program-breaking way.
Apparently I don't fully understand your postion. Your previously stated
contraint on the optimizer, including and especially for programs with
undefined behavior, was ...
> the optimizer should preserve the behaviour of the non-optimizing
> compiler.
In a language like C, the behavior of programs that reference
uninitialized variables can be affected by the slightest change to
register assignments. Given that optimizations like copy propagation
and common subexpression elimination can potentially change register
assignments, and thus change the behavior of these programs, why would
you include these optimizations in your list of permissible
optimizations?
Best,
Christopher
Anton Ertl
[Anton Ertl:]
>> the optimizer should preserve the behaviour of the non-optimizing
>> compiler.
>
>In a language like C, the behavior of programs that reference
>uninitialized variables can be affected by the slightest change to
>register assignments.
Not if the unoptimizing compiler initializes all variables to some
known value.
>Given that optimizations like copy propagation and common
>subexpression elimination can potentially change register
>assignments, and thus change the behavior of these programs, why
>would you include these optimizations in your list of permissible
>optimizations?
As you can see, in this case this is easy to solve. It has the nice
side effect of making even the unoptimized behaviour more stable,
which programmers also like, because it makes, e.g., debugging easier.
Chris F Clark
necessarily practical, at least not in all cases.
an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> "Christopher Glaeser" <c...@nullstone.com> writes:
> [Anton Ertl:]
>>> the optimizer should preserve the behaviour of the non-optimizing
>>> compiler.
>>
>>In a language like C, the behavior of programs that reference
>>uninitialized variables can be affected by the slightest change to
>>register assignments.
>
> Not if the unoptimizing compiler initializes all variables to some
> known value.
The problem with this solution is that there is at least 1 well-known
algorithmic trick that doesn't work in this case. It is a way to
initialize a large unbounded array efficiently, when you only use a
portion of the array in your algorithhm. However, it depends upon
being able to not actually initialize the array for the unused
sections. You find a way to map the array such that you can track the
"highest" element used and when accessing the array, you compare the
element you are about to use with the highest element initialized so
far, and if it is beyond the bound, you initialize enough elements to
cover the element you are accessing and update your tracker.
I don't know of any optimizers that will insert that kind of trick in
ones code. I don't know of optimizers that will replace bubble-sort
with quick-sort either.
So, if you have an algorithm that needs a trick like the above to meet
its performance promises, then the unoptimizing compiler breaks your
algorithm (and we don't have a well-known optimization technique that
fixes that breakage).
Now, your point about stability is well taken. Most programmers would
prefer that they can be blindly cavalier about memory usage and
uninitialized values would simply always be zero. It makes a lot of
off-by-one errors benign. However, that freedom comes at a price, one
that is often unacceptable. Yes, you can zero stack frames on every
procedure entry, but if someone starts putting large auotmatic arrays
on the stack, the performance can drop steeply.
I don't know of (nor believe there even is) a general solution to the
problem. That's why we have both C and SML and Lisp and ..., which
are all very different solutions to the problem, with different
tradeoffs.
Yes, one can design a language that is safe, but every attempt to do
so, has restricted the language such that certain short-cuts that may
be generally unsafe, but can be safe in certain instances, are
prohibited. The question then is whether those short-cuts are
required in ones application.
-Chris
******************************************************************************
Barry Kelly
> > Not if the unoptimizing compiler initializes all variables to some
> > known value.
>
> So, if you have an algorithm that needs a trick like the above to meet
> its performance promises, then the unoptimizing compiler breaks your
> algorithm (and we don't have a well-known optimization technique that
> fixes that breakage).
I'm partial to the C# approach myself. The safe subset of the language
is capable, and for the particular case in question, all locals are
zeroed out by the compiler by default, even though the language requires
definite assignment before use. (So the optimizing JIT won't pay
performance-wise here, as it can eliminate the redundant
initialization.)
However, if tricks are required to meet performance goals, there is the
escape valve of unsafe code, wherein one can fall back to C-level
semantics.
> Yes, one can design a language that is safe, but every attempt to do
> so, has restricted the language such that certain short-cuts that may
> be generally unsafe, but can be safe in certain instances, are
> prohibited. The question then is whether those short-cuts are
> required in ones application.
I think the dichotomy apparently in question, to be safe or not to be
safe, is false. If the safe subset is strongly encouraged (and in the
case of C# and .NET etc., often mandated for business reasons when using
e.g. third-party application servers), yet an "out" is possible, is this
not all that is needed?
-- Barry
Anton Ertl
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> "Christopher Glaeser" <c...@nullstone.com> writes:
>> [Anton Ertl:]
>>>> the optimizer should preserve the behaviour of the non-optimizing
>>>> compiler.
>>>
>>>In a language like C, the behavior of programs that reference
>>>uninitialized variables can be affected by the slightest change to
>>>register assignments.
>>
>> Not if the unoptimizing compiler initializes all variables to some
>> known value.
>
>The problem with this solution is that there is at least 1 well-known
>algorithmic trick that doesn't work in this case. It is a way to
>initialize a large unbounded array efficiently, when you only use a
>portion of the array in your algorithhm.
The issue under discussions was that the optimizations I mentioned
would change the register allocation, and that would result in changed
values for uninitialized variables and thus altered behaviour. To fix
that one actually does not need to initialize all variables (unlike
what I wrote), only variables that may be born in registers,
i.e. scalars. I don't think that's impractical.
>However, it depends upon being able to not actually initialize the
>array for the unused sections. You find a way to map the array such
>that you can track the "highest" element used and when accessing the
>array, you compare the element you are about to use with the highest
>element initialized so far, and if it is beyond the bound, you
>initialize enough elements to cover the element you are accessing and
>update your tracker.
>I don't know of any optimizers that will insert that kind of trick in
>ones code.
That should be easy to implement, though. The hard part is deciding
when to use that vs. when to initialize everything up-front and avoid
the run-time overhead of checking the bound.
There is an even more extreme case where you don't even need (and
want) initialization when you access it, because you have another way
of validating the contents [briggs&torczon93]. However, AFAIK at that
data structure has not been used much (at least for this purpose),
because there are good alternatives that are less wasteful of memory.
Anyway, at least for the optimizations I mentioned it is not necessary
to initialize arrays.
And yes, as I mentioned, there are certain cases (like out-of-bounds
array accesses) where preservation of behaviour in all cases is
impractical, and the benefits derived from it are vanishingly small.
But still, that's a good ideal for optimizer writers to strive for,
even if they cannot achieve it in all cases.
>So, if you have an algorithm that needs a trick like the above to meet
>its performance promises, then the unoptimizing compiler breaks your
>algorithm (and we don't have a well-known optimization technique that
>fixes that breakage).
For the case you mention, always performing the on-demand
initialization in the compiler would preserve the asymptotic
complexity, but is probably impossible in general in a language like C
that has arbitrary pointer arithmetic.
If the array is really large, a good approach is to just allocate it
with mmap (the run-time system of the language could do this by
itself, if the programmer does not do it explicitly). Then the OS
will perform the on-demand initialization.
- anton
@Article{briggs&torczon93,
author = "Preston Briggs and Linda Torczon",
title = "An Efficient Representation for Sparse Sets",
journal = "ACM Letters on Programming Languages and Systems",
year = "1993",
volume = "2",
number = "1--4",
pages = "59--69",
annote = "Describes a set representation that is
asymptotically more
time-efficient than the classical bit-vector for
operations like \emph{clear-set} and \emph{forall},
but needs much more memory. The paper also presents
empirical data from micro-benchmarks that shows that
the \emph{member}, \emph{add-member} and
\emph{delete-member} operations are about three
times slower on an RS/6000 with the new
representation than with the bit-vector
representation. It also presents empirical data from
compilations of several routines, that shows that
the new representation significantly reduces the
register allocation time for these routines."
Christopher Glaeser
> would change the register allocation, and that would result in changed
> values for uninitialized variables and thus altered behaviour. To fix
> that one actually does not need to initialize all variables (unlike
> what I wrote), only variables that may be born in registers,
> i.e. scalars. I don't think that's impractical.
The back flips needed to define undefined behavior in a language like
C is pretty far reaching. I only mentioned register allocation
because I didn't know you were advocating that the compiler needs to
initialize local scalar variables. Optimizations like copy
propagation and common subexpression elimination can also affect stack
allocation, which in turn, can affect the values of uninitialized
local arrays. Even a simple bug fix to a new release in a compiler
can affect the behavior of C programs that have undefined behavior.
It's not clear where pulling on this thread would end? Do you
advocate initializing local arrays too, and if not, why not?
> And yes, as I mentioned, there are certain cases (like out-of-bounds
> array accesses) where preservation of behaviour in all cases is
> impractical, and the benefits derived from it are vanishingly small.
> But still, that's a good ideal for optimizer writers to strive for,
> even if they cannot achieve it in all cases.
Given that you have tossed out-of-bounds array access into the
too-hard pile, are you also tossing undefined pointer use into the
too-hard pile as well? Given that pointers are so pervasive in C,
doesn't this miss one of the more common reasons why incorrect
programs can change behavior when optimized?
More to the point, I still don't understand your basic position. In
your original post, you accussed some compiler writers of being
"apologists" becuase they designed the optimizer to the lanauge
standard and you asserted that they should be designing the optimizer
to maintain the behavior of programs that use undefined behavior, and
then made some room for ignoring behavior like out-of-bound arrays.
This exception seems a bit arbitrary. How is a compiler writer to
know if they are an apologist?
Best,
Christopher
Anton Ertl
>Even a simple bug fix to a new release in a compiler
>can affect the behavior of C programs that have undefined behavior.
Different releases are a different issue than turning optimization on,
although changing behaviour between releases is not desirable, either.
>It's not clear where pulling on this thread would end? Do you
>advocate initializing local arrays too, and if not, why not?
If you want to implement an optimization that needs initialized local
arrays to preserve the behaviour, it's certainly worth considering.
Or you may find a different way to preserve the behaviour.
>Given that you have tossed out-of-bounds array access into the
>too-hard pile,
The specific case I was thinking about was reading a specific value of
a function return address through an out-of-bounds access; this is
both hard to preserve and not worthwhile, because the programmer will
experience this as a problem even in the non-optimizing compiler
during development and will avoid that.
>are you also tossing undefined pointer use into the
>too-hard pile as well?
"Undefined pointer use" sounds like something from a standards
document, i.e., something out of the vocabulary of an apologist. I
don't know exactly what you mean by that (it's probably many different
things, at least in their effect on behaviour-preserving
optimization), and therefore cannot answer the question.
>Given that pointers are so pervasive in C, doesn't this miss one of
>the more common reasons why incorrect programs can change behavior
>when optimized?
"Incorrect programs"? Definitively apologist lingo in this context.
>More to the point, I still don't understand your basic position. In
>your original post, you accussed some compiler writers of being
>"apologists" becuase they designed the optimizer to the lanauge
>standard and you asserted that they should be designing the optimizer
>to maintain the behavior of programs that use undefined behavior, and
>then made some room for ignoring behavior like out-of-bound arrays.
>This exception seems a bit arbitrary. How is a compiler writer to
>know if they are an apologist?
The test is pretty simple: What happens if you get a bug report that
shows that your optimizer changes the behaviour of the program?
* Do you analyse the program to see if it is actually
standard-conformant? If it isn't, do you consider the program to be
incorrect, the optimizer to be correct, and do you mark the bug
report as invalid? Then you are an apologist. If you don't write
optimizers, but think that this attitude is ok, then you are also an
apologist.
* Do you consider the behaviour change as an optimizer bug, and think
about how it can be fixed, and suggest workarounds to the programmer
for the meantime? Then you are no apologist. The cases where you
cannot fix the optimizer bug should be the exception, not the rule,
and these should all be cases where the programmer considers his
program buggy himself anyway once you make him aware of why the
optimizer changed the behaviour (without you citing the standard or
anything).
- anton
Diego Novillo
<an...@mips.complang.tuwien.ac.at> wrote:
> * Do you analyse the program to see if it is actually
> standard-conformant? If it isn't, do you consider the program to be
> incorrect, the optimizer to be correct, and do you mark the bug
> report as invalid? Then you are an apologist. [ ... ]
>
> * Do you consider the behaviour change as an optimizer bug, and think
> about how it can be fixed, and suggest workarounds to the programmer
> for the meantime? Then you are no apologist. [ ... ]
GCC typically falls in between these two. Mostly due to lack of resources.
The governing principle in GCC is to strictly follow the standard,
except where massive user pressure wins and engineering resources are
available. We try to suggest fixes to user code, with varying degrees
of success.
The standard has the advantage of being a more rigorous specification,
making it easier to implement than the often subjective user
expectations. That is not to say that standards are always rigorous
or easy to implement, of course.
Diego.
Christopher Glaeser
> arrays to preserve the behaviour, it's certainly worth considering.
> Or you may find a different way to preserve the behaviour.
Initialize to what?
Suppose you are responsible for maintaining a C compiler and you
receive a defect report with a program that works fine without
optimization but generates a divide by zero exception with
optimization. You analyze the program and determine that the divide
by zero is in a function that references an uninitialized local array
element. Without optimization, the array element has a value of 1 due
to the more-or-less random state of the stack on entry to the
function. With optimization, changes to register and stack
assignments cause changes to the state of the stack on entry to the
function, and now the uninitialized local array element has the value
0, which causes the divide by zero exception.
How would you respond to this defect report?
Best,
Christopher
Nathaniel McIntosh
| apologists (of program-breaking optimizers) that claim that the
| program was already broken without the optimizer, because it does not
| conform to some language standard. But actually the program does
| conform with the language as it is implemented by the compiler without
| optimization and it behaves as intended by the programmer, so it is
| correct.
Anecdote from my own personal experience as a compiler writer: at one
point while working on an optimization to improve data cache behavior
for C/C++ programs, I ran into an application (let's call it
"Application T") containing the following code (greatly simplified):
foo.c bar.c
----- -----
... ...
double x; int x = 0;
... int garbage;
...
Most C compilers will compile these two modules without complaint;
when you link foo.o and bar.o into an executable, the "strong"
definition of "x" from bar.o is favored over the "weak" definition in
foo.o, and you wind up with a final "x" entity that is 4 bytes in size
(assuming an ILP32 compilation model), not 8 bytes.
In spite of the fact that foo.c contains functions that store 8-byte
values to "x", the program works without optimization because the
variable "garbage" (unused as it turned out) happens to be allocated
just after "x" in memory. If the optimizer plays with the storage
allocation such that some other critical variable appears just after
"x", then the application fails.
This is certainly a case where optimization perturbs program behavior,
and I can think of many other similar cases regarding variable
allocation, use of stack frames, etc. In this example, it is possible
for me to imagine designing/implementing the compiler so that there
would be no behavior change due to storage layout diffs. For example,
you could simply pick a specific recipe for laying out all
global/static variables in the program (ex: alphabetical order, or
perhaps order in which the variables appear in the source file) and
hold religiously to that order, even if it causes extra padding to be
introduced between variables, and even if it eliminates any
possibility of storage layout optimizations.
I would in fact argue, however, that the compiler is doing the
programmer a favor by causing the program to crash when compiled with
optimization. My reasoning: while there is some pain up front for the
application writer (e.g. he/she has to track down the reason for the
crash when optimization is turned on), the good news is that the
programming error is caught early (e.g. in the lab, during the
compiler evaluation process), as opposed to "lurking" in the code and
turning up only later at some much less pleasant time. The point here
being that programming errors of this sort can just as easily be
converted from latent problems to actual crashes by source code
modifications as opposed to optimization.
For example, suppose that the "Application T" developers are using a
compiler that slavishly sticks to the same variable layout regardless
of optimization level, so as to avoid "behavior changes" as a result
of optimization. The buggy code doesn't cause a failure, so
"Application T" is run through QC testing and is shipped out to
customers. Months later a critical bug is filed by an important
customer; programmers rush to make a fix. An engineer determines that
the problem is in routine "bar.c", and so makes a change to the module
that happens to slightly reorder the variables (including our bad
variable "x"). The test suite is run to verify the bugfix, and lo and
behold, the application fails in some mysterious way that seems to
have nothing to do with the change. Now the hapless engineer has to
track down the (totally unrelated) bug while the clock ticks and
everyone waits for the critical fix. Would things not have been much
better if the engineer had learned about the bug many months ago when
optimization was turned on? :-)
I think most programmers given a choice would prefer to find out about
programming errors such as these as soon as possible-- having a
compiler that covers them up (in some sense) only postpones the pain,
it doesn't eliminate it.
NM
[I'd rather use a linker that diagnoses type mismatches. It's not
exactly a new idea; I know one that did that in 1976. -John]
Pertti Kellomaki
> * Do you analyse the program to see if it is actually
> standard-conformant? If it isn't, do you consider the program to be
> incorrect, the optimizer to be correct, and do you mark the bug
> report as invalid? Then you are an apologist. If you don't write
> optimizers, but think that this attitude is ok, then you are also an
> apologist.
Or a formalist. For example, the Scheme specification does not specify
the order in which function arguments are evaluated. As far as I am
concerned, an implementation would be free to evaluate arguments left
to right on weekdays and right to left on weekends. If my code relies
on something that is not explicitly promised by the language, that's
my fault, not the compiler's.
--
Pertti
glen herrmannsfeldt
(snip)
< Anecdote from my own personal experience as a compiler writer: at one
< point while working on an optimization to improve data cache behavior
< for C/C++ programs, I ran into an application (let's call it
< "Application T") containing the following code (greatly simplified):
< foo.c bar.c
< ----- -----
< ... ...
< double x; int x = 0;
< ... int garbage;
< ...
< Most C compilers will compile these two modules without complaint;
< when you link foo.o and bar.o into an executable, the "strong"
< definition of "x" from bar.o is favored over the "weak" definition in
< foo.o, and you wind up with a final "x" entity that is 4 bytes in size
< (assuming an ILP32 compilation model), not 8 bytes.
I am not so sure what you mean by "strong" and "weak" (*), but yes
many linkers treat initialized data different from uninitialized
data. Among others, that is the reason for BLOCK DATA in Fortran.
The OS/360 (and successor) linker does take initialized (CSECT)
over uninitialized (COM), but requires that the CSECT be at
least as large as the COM. I believe that there is an error
message for it, though I am not sure that I ever tried it.
(big snip)
< I think most programmers given a choice would prefer to find out about
< programming errors such as these as soon as possible-- having a
< compiler that covers them up (in some sense) only postpones the pain,
< it doesn't eliminate it.
That has always been one of the reasons I use for promoting big-endian
byte ordering. If you pass the address of a little endian value of
the wrong size, it has a good chance of working for many values. A
wrong sized big-endian value passed by address has a much smaller
chance of working.
(*) The OS/360 linker, and I believe others, have a weak external
reference that won't pull something in from a library if it isn't
otherwise needed, but will generate the proper reference if it is
otherwise loaded. (EXTRN vs WXTRN)
< [I'd rather use a linker that diagnoses type mismatches. It's not
< exactly a new idea; I know one that did that in 1976. -John]
Well, type would be nice, but it should at least check size. Type
will be a problem for union (C) and EQUIVALENCE (Fortran), though I
suppose you could turn off type checking only for those cases.
-- glen
Torben Ægidius Mogensen
> Suppose you are responsible for maintaining a C compiler and you
> receive a defect report with a program that works fine without
> optimization but generates a divide by zero exception with
> optimization. You analyze the program and determine that the divide
> by zero is in a function that references an uninitialized local array
> element. Without optimization, the array element has a value of 1 due
> to the more-or-less random state of the stack on entry to the
> function. With optimization, changes to register and stack
> assignments cause changes to the state of the stack on entry to the
> function, and now the uninitialized local array element has the value
> 0, which causes the divide by zero exception.
>
> How would you respond to this defect report?
I would tell the programmer what the problem is and, if time allows,
add an analysis that detects potential uses of uninitialised variables
or array elements and issue warnings if such occur. I would also make
sure the policy for bug reports will only accept programs where the
compiler does not issue warnings.
But for a language like C, it is a futile job. There are so many
unspecified behaviours that you can't realistically preserve all or
issue warnings where you don't.
And, to a degree, preserving unspecified behaviour at optimisation is
not doing the programmer any favours: If the same compiler does not
preserve this behaviour across optimisation levels, it is very
unlikely that it will be preserved if you change compiler (or even
target architecture).
Torben
Torben Ægidius Mogensen
I agree. But I also think that it is a problem for a language to
leave visible behaviour unspecified, except for indirectly visible
behaviour such as resource use. So, you should only leave order of
evaluation unspecified if the order can not directly influence the
result of the program, i.e., when there are no side effects. This
does not mean that the language shold be free of side effects, but
only that the language definition guarantees that side-effecting
computations are in the same standardized order regardless of which
compiler, optimisation level or target machine you use.
Why rely on the programmer to ensure that his code is independent of
evaluation order? A compiler can usually do this more reliably than an
average programmer.
Torben
[The traditional Fortran answer is that the more latitude you give the
compiler, the faster code it can generate. I agree this makes it harder
to write reliable code since you have to defend against all the
transformations it might do. -John]
George Neuner
<mcin...@cup.hp.com> wrote:
>
> foo.c bar.c
> ----- -----
> ... ...
> double x; int x = 0;
> ... int garbage;
>
>Most C compilers will compile these two modules without complaint;
>when you link foo.o and bar.o into an executable, the "strong"
>definition of "x" from bar.o is favored over the "weak" definition in
>foo.o, and you wind up with a final "x" entity that is 4 bytes in size
>(assuming an ILP32 compilation model), not 8 bytes.
>
>In spite of the fact that foo.c contains functions that store 8-byte
>values to "x", the program works without optimization because the
>variable "garbage" (unused as it turned out) happens to be allocated
>just after "x" in memory. If the optimizer plays with the storage
>allocation such that some other critical variable appears just after
>"x", then the application fails.
No. Your example will work regardless. Assuming those definitions
were global in the source files, the result will be 2 different
variables named 'x' - an integer in bar.o and a double real in foo.o.
If, OTOH, the code was:
foo.c bar.c
----- -----
... ...
extern double x; int x = 0;
... int garbage;
...
then the compiler/linker would create only the integer "x" and any
functions in foo that accessed "x" as a double real would do so in
error.
Apart from being a programming mistake and semantically wrong, there
might make no noticeable error on a machine with a 64-bit "int" type.
>I would in fact argue, however, that the compiler is doing the
>programmer a favor by causing the program to crash when compiled with
>optimization.
On this point I agree with you. I don't ever want a customer to see a
program crash or even misbehave. I want the incorrect program to be
correct before it is shipped.
I used to work in RT industrial QA/QC systems where the application
runs 24/7 and the computers are normally inaccessible to production
workers. A software crash in the field typically means the customer
is losing money by the second until a supervisor arrives to restart
the application. A crash on 3rd shift with supervisors home in bed
might result in an hour or more of down time. For some of the
customers whose systems I worked on, a 1 hour outage on a single
production line could mean millions of dollars in lost sales
opportunities.
George
Robert A Duff
> "Christopher Glaeser" <c...@nullstone.com> writes:
>>Even a simple bug fix to a new release in a compiler
>>can affect the behavior of C programs that have undefined behavior.
>
> Different releases are a different issue than turning optimization on,
> although changing behaviour between releases is not desirable, either.
What about portability to a completely different compiler on a
completely different machine? Do you expect your program to behave
the same?
I think you're attacking the wrong folks, here. If optimizers can
affect the behavior of programs, that's primarily the fault of the
language designer, not the compiler writer.
Language designers ought to minimize such cases. Ada has fewer cases of
undefined behavior than C. Java has even fewer.
- Bob
Robert A Duff
> [I'd rather use a linker that diagnoses type mismatches. It's not
> exactly a new idea; I know one that did that in 1976. -John]
I'd rather use a language that catches such problems at compile time.
It doesn't really need to be done by the linker. Ada, Modula-2, and
many others come to mind...
- Bob
Anton Ertl
"Christopher Glaeser" <c...@nullstone.com> writes:
>> If you want to implement an optimization that needs initialized local
>> arrays to preserve the behaviour, it's certainly worth considering.
>> Or you may find a different way to preserve the behaviour.
>
>Initialize to what?
It does not matter for preserving behaviour, as long as the
initialization is the same with and without optimization.
Of course, if you are already initializing, you might just as well
initialize to a defined value that also survives, e.g., program
changes. Initializing to 0 can be relatively cheap (e.g., on the PPC
architecture with the dcbz instruction). It can actually be cheaper
to initialize an array by using such cache-manipulation instructions
first and storing there only afterwards (but it depends on the
concrete usage whether this is cheaper or not).
>Suppose you are responsible for maintaining a C compiler and you
>receive a defect report with a program that works fine without
>optimization but generates a divide by zero exception with
>optimization. You analyze the program and determine that the divide
>by zero is in a function that references an uninitialized local array
>element. Without optimization, the array element has a value of 1
>due to the more-or-less random state of the stack on entry to the
>function. With optimization, changes to register and stack
>assignments cause changes to the state of the stack on entry to the
>function, and now the uninitialized local array element has the value
>0, which causes the divide by zero exception. How would you respond
>to this defect report?
I would think about how to fix the bug in the optimizer. Within a few
minutes I came up with the following approaches:
* Initialize the array (possibly on-demand as discussed in an earlier
message).
* Make sure that the stack state left by earlier uses of the stack is
the same with and without optimization. This could be done by
performing stores that might otherwise seem superfluous, but it's
probably cheaper to just clear the stuff that might have a different
value on exit from the function (and on architectures where the
return address is read directly from the stack on returning, clear
the return address after returning, if necessary).
* Disable the optimizations that cause the differences in the stack
contents.
Anton Ertl
>> Or a formalist. For example, the Scheme specification does not specify
>> the order in which function arguments are evaluated. As far as I am
>> concerned, an implementation would be free to evaluate arguments left
>> to right on weekdays and right to left on weekends. If my code relies
>> on something that is not explicitly promised by the language, that's
>> my fault, not the compiler's.
If you are talking about your own code, it's certainly your right to
think this way. But if you write an optimizer, it's your business to
optimize the working program, not to break it.
>I agree. But I also think that it is a problem for a language to
>leave visible behaviour unspecified, except for indirectly visible
>behaviour such as resource use. So, you should only leave order of
>evaluation unspecified if the order can not directly influence the
>result of the program, i.e., when there are no side effects. This
>does not mean that the language shold be free of side effects, but
>only that the language definition guarantees that side-effecting
>computations are in the same standardized order regardless of which
>compiler, optimisation level or target machine you use.
Yes, that's a good idea. But if the language standard does not do it,
at least the compiler should do it.
The funny thing is that such weaknesses in language standards
typically come around because two different implementations do it
differently. And since the implementors know that the existing
programs for their compilers rely on the order, they won't change the
way their compilers work, and as a compromise this particular aspect
is not standardized. Then a few years down the road the apologists
(or, if you want, formalists, or language lawyers) say that programs
that rely on the order like the ones that were the reason for the
weakness are not just non-standard, but "incorrect" and ignore any
bugs in the optimizer that occur in these programs. (I don't know if
that's what happened in Scheme).
Anton Ertl
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>
>> "Christopher Glaeser" <c...@nullstone.com> writes:
>>>Even a simple bug fix to a new release in a compiler
>>>can affect the behavior of C programs that have undefined behavior.
>>
>> Different releases are a different issue than turning optimization on,
>> although changing behaviour between releases is not desirable, either.
>
>What about portability to a completely different compiler on a
>completely different machine? Do you expect your program to behave
>the same?
No. Porting can uncover portability bugs. But turning on an
optimizer is different from porting a program. Many programmers avoid
porting programs to a different compiler or platform, or incur a large
amount of extra effort when they do. Do you think that they should
treat optimization the same way? Then they will avoid the optimizer
just like they avoid porting. Then the optimizer will just be a
benchmarketing exercise.
>I think you're attacking the wrong folks, here. If optimizers can
>affect the behavior of programs, that's primarily the fault of the
>language designer, not the compiler writer.
The language specifiers [1] do not force optimizers to break working
(albeit non-standard) programs; if the optimizer does that, the
optimizer writer is to blame, nobody else.
Yes, stronger language specifications are a good idea, because they
make porting easier. But that has little to do with optimization.
[1] Whether the specification comes from a designer or design group,
or as the result of a standardization effort.
Anton Ertl
[double definition of a symbol in two different files]
>I would in fact argue, however, that the compiler is doing the
>programmer a favor by causing the program to crash when compiled with
>optimization. My reasoning: while there is some pain up front for the
>application writer (e.g. he/she has to track down the reason for the
>crash when optimization is turned on), the good news is that the
>programming error is caught early (e.g. in the lab, during the
>compiler evaluation process), as opposed to "lurking" in the code and
>turning up only later at some much less pleasant time. The point here
>being that programming errors of this sort can just as easily be
>converted from latent problems to actual crashes by source code
>modifications as opposed to optimization.
Well, in that case, if the test suite produces a crash when the
optimizer modifies the behaviour, it will most likely also produce a
crash when the source code is changed in a way that affects this.
OTOH, if the test suite does not catch this when the source code is
changed, it will probably not catch it when the optimizer changes
behaviour either; and as a result the optimizer bug may unveil itself
later at some much less pleasant time without any source code change
being involved. That's exactly the reason why optimizers should not
change the behaviour of working programs.
>I think most programmers given a choice would prefer to find out about
>programming errors such as these as soon as possible-- having a
>compiler that covers them up (in some sense) only postpones the pain,
>it doesn't eliminate it.
Right, but the optimizer is not the right tool for that purpose; and
it's certainly not as soon as possible. The linker is a much better
place for this particular case, as others have suggested. And indeed,
with your example GNU ld 2.15 on IA-32 says:
[b3:~/tmp:21583] gcc foo.o bar.o
/usr/bin/ld: Warning: alignment 4 of symbol `x' in bar.o is smaller than 8 in foo.o
/usr/bin/ld: Warning: size of symbol `x' changed from 8 in foo.o to 4 in bar.o
Ray
> The funny thing is that such weaknesses in language standards
> typically come around because two different implementations do it
> differently. And since the implementors know that the existing
> programs for their compilers rely on the order, they won't change the
> way their compilers work, and as a compromise this particular aspect
> is not standardized. Then a few years down the road the apologists
> (or, if you want, formalists, or language lawyers) say that programs
> that rely on the order like the ones that were the reason for the
> weakness are not just non-standard, but "incorrect" and ignore any
> bugs in the optimizer that occur in these programs. (I don't know if
> that's what happened in Scheme).
In fact, different implementations do it differently. But that's not
the reason why order of evaluation was left unspecified. I was the
coordinator of the committee that made the last IEEE standard for
Scheme, and I remember the arguments.
The fact is that side effects other than I/O are hardly ever actually
necessary in a scheme program, and using them is widely regarded as
bad style anyway. All variables are allocated in an initialized
state, so the condition of the stack or choice of register assignments
never affect variable contents. The vast majority of Scheme programs,
including programs written for implementations that have a constant
evaluation order, run just fine if the evaluation order is changed.
The order of evaluation was left unspecified mainly because academic
papers showed, and practical implemented systems demonstrated, that an
optimizing compiler, by picking an order of evaluation to minimize
register usage and the need to store intermediate results, could add
about ten percent to the speed of compiled programs.
Since the scheme community regards side-effects as mostly bad style
anyway, and existing systems had all kinds of evaluation orders, and
most code was portable between those systems anyway, and specifying an
evaluation order would have broken semantics on which some very good
optimizing compilers relied upon for their performance, we left
argument order unspecified. There were passionate partisans on both
sides of the question - some of whom felt as you do.
But - I think you are wrong about what an optimizer is for. An
optimizer is supposed to make programs run as fast as possible while
consuming the least other resources possible, within the language
spec. Programs that rely on something the language doesn't specify
already have varying behavior on different systems and an optimizer
has to regard *all* of those behaviors as correct. Picking one over
another is something it does (and _MUST_ do) for performance reasons.
Bear
Jan Vorbrüggen
> leave visible behaviour unspecified, except for indirectly visible
> behaviour such as resource use. So, you should only leave order of
> evaluation unspecified if the order can not directly influence the
> result of the program, i.e., when there are no side effects.
Agreed so far.
> This does not mean that the language shold be free of side effects,
> but only that the language definition guarantees that side-effecting
> computations are in the same standardized order regardless of which
> compiler, optimisation level or target machine you use.
Alternatively (e.g., Fortran), the standard requires (only) that set
of computations to be free of such side-effects as might make the
result indeterministic.
> Why rely on the programmer to ensure that his code is independent of
> evaluation order? A compiler can usually do this more reliably than
> an average programmer.
While I agree, this is unfortunately academic - most people, and in
particular that subset raised on C/C++ - seem to be unable to accept
(or sometimes even grasp) the concept of the compiler being their
"nanny".
And technically, it isn't easy to do. Even a very restrictive language
such as occam2 made it impossible to use, in a practical program, the
alias and usage checker because of its implementation
deficencies. Yes, that implementation could have been improved, in
particular in its handling of arrays and array slices, and
Fortran-like slice notation would have made its life easier as
well...but doing this without getting in the way of legitmate cases is
very hard. Perhaps the Ada way (be strict in the compiler, but accept
the programmer's explicit instructions to not perform a check here or
there) is the right way to go.
> [The traditional Fortran answer is that the more latitude you give
> the compiler, the faster code it can generate. I agree this makes
> it harder to write reliable code since you have to defend against
> all the transformations it might do. -John]
See above. I don't think it makes it really that much harder...in
fact, given the pitfalls that are present in other languages that you
can avoid in this way, the bottom line is very likely that your coding
is faster and easier.
Jan
[The particular Fortran problem is that the standard allows the compiler
to make rearrangements that are mathematically equivalent but not
floating point computationally equivalent. -John]
George Neuner
Nathaniel asked me privately what compilers I know of that act as I
described above. He cited a few compilers that act as he described. I
was going to reply privately, but in checking compilers I discovered
something that, I think, dovetails nicely with this thread.
YMMV.
I have access to more than a dozen ANSI C compilers - some C89 and
some C99 . I have multiple versions of GCC (for x86 Linux, Windows
and QNX, and for 68K VxWorks), of MS VisualC(++), and of TurboC. I
also have available to me a Sparc5 C/C++ compiler, 68K Macintosh MPW
C, and a late model extended DOS version of x86 Watcom (the old
for-profit Watcom).
I tested them by compiling the following code (in 32-bits) in both
debug and optimized versions.
==== test.c ====
extern void DoStuffWithIntX( void );
extern void DoStuffWithDblX( void );
int main(int argc, char* argv[])
{
DoStuffWithDblX( );
DoStuffWithIntX( );
return 0;
}
==== foo.c ====
#include <stdio.h>
double x;
void DoStuffWithDblX( void )
{
printf( "double X is at %p\n", &x );
}
==== bar.c ====
#include <stdio.h>
int x;
int garbage;
void DoStuffWithIntX( void )
{
printf( "integer X is at %p\n", &x );
}
and I varied which of the variables 'x' was explicitly initialized (to
zero) at the top level. I had the compilers produce map files to
check whether and where the names had storage allocated. I discovered
that some of the compilers behaved very differently depending on
whether one or both of the variables was initialized. Some of them
also behaved differently depending on whether the compilation was
debug or optimized. I won't bother with extensive reporting of which
compiler did what - suffice to say that depending on the compiler and
its settings, I was able to achieve allocation of 1 variable, 2
variables, and _NO_ variables. Except in the cases where no storage
was allocated, I was able to run the resultant executables and see the
address(es) of the variables.
I was intrigued by the wide variation in behavior, so I investigated
further. After some careful reading of the ANSI C standards - both
the original C89 and the new C99 - I discovered that there is a
unresolved ambiguity pertaining to multiple top level variable
definitions (as in Nathaniel's code above) that do not specify a
storage class.
C does not allow either duplicate definitions or multiple definitions
of the same named object in any name overloading class (of which the
"top level", ie. global names, is one). You can have duplicated
_declarations_, but not duplicated _definitions_.
"extern double x;" is a declaration. No storage is allocated
for the variable, its name is a reference
to a definition elsewhere.
"double x = 0.0;" is a definition. This allocates storage
for the variable. Because it is initialized,
this is considered a "strong" definition.
"double x;" is a definition if there is a preceeding
declaration, else it is both. Because it
is _not_ initialized, this is considered
a "weak" definition.
"static double x;" is a declaration if there is a subsequent
strong definition, else it is both. This
allocates storage for the variable.
A problem occurs when there are multiple definitions in separate
files. Technically, by the standards, there can be only 1 definition
of a name at top level ... all other references to the name, including
any forward references to the name in the same file, *must* be
"extern" declarations.
However, the requirement for specifying "extern" is routinely relaxed
for forward references to functions and to recursive structures. For
such declarations, compilers implicitly assume "extern". It appears
that some compilers also assume "extern" in the case of weak variable
definitions.
Now the problem with assuming "extern" for weak definitions is that it
in conflict with the assumption of file scope visibility. Judging by
the C standard, a top level variable definition (strong or weak) is
not meant to name an external object, but rather to introduce a
variable with file scope ... a separate "extern" declaration is needed
to "import" the name into a different scope. In keeping with the
principle of least surprise, it would be better to assume a weak
variable definition is "conditionally static" rather than "extern",
conditionally allocate storage for it and have the linker resolve the
references. Some of the compilers actually did something like this
and created 2 separate variables.
Every compiler complained about multiple definitions of 'x' when all
the definitions were strong - ie. when 'x' was initialized in both
files. However, if either definition was weak, I was able to build an
executable. When both definitions were weak, however, some of the
compilers produced optimized executables with NO storage at all
allocated for the name 'x'.
I know this isn't a C forum and nobody (including me) cares much to
debate what is right or wrong about C. But for the sake of a
discussion about compilers, how would you handle the situation if it
were up to you?
George
Hans-Peter Diettrich
> A problem occurs when there are multiple definitions in separate
> files. Technically, by the standards, there can be only 1 definition
> of a name at top level ... all other references to the name, including
> any forward references to the name in the same file, *must* be
> "extern" declarations.
[...]
> Every compiler complained about multiple definitions of 'x' when all
> the definitions were strong - ie. when 'x' was initialized in both
> files.
5B
How does a compiler know about other files?
I assume that the definitions were in the same compilation unit, i.e. in
the header files included by both source files. Otherwise it's a matter
of object file formats and linkers, what will happen with multiple
definitions of the same symbol in multiple object files.
> However, if either definition was weak, I was able to build an
> executable. When both definitions were weak, however, some of the
> compilers produced optimized executables with NO storage at all
> allocated for the name 'x'.
What's "NO" storage? A NULL address output by printf?
> I know this isn't a C forum and nobody (including me) cares much to
> debate what is right or wrong about C. But for the sake of a
> discussion about compilers, how would you handle the situation if it
> were up to you?
IMO this topic is an excellent exercise in the semantics of programming
languages. When an executable file can be linked from multiple
compilation units, the language specification also should include the
expected behaviour of the linker. When no type information is stored in
the object files, a linker only can overlay multiple definitions of the
same symbol, with the maximum allocation request.
I dunno about specific C++ specs, but when there also the names of
variables are mangled, the symbol definitions for variables of different
type would look different to the linker. Also namespace names should be
preserved, somehow.
In Delphi (OPL) or other languages a (public) symbol can have an
qualified name, consisting of the unit name and identifier, and the
compiler will only produce accordingly qualified references to external
symbols.
DoDi
Anton Ertl
>C does not allow either duplicate definitions or multiple definitions
>of the same named object in any name overloading class (of which the
>"top level", ie. global names, is one). You can have duplicated
>_declarations_, but not duplicated _definitions_.
>But for the sake of a discussion about compilers, how would you
>handle the situation if it were up to you?
What I expected is that the linker complains about duplicate symbols
(irrespective of optimization level). I was very surprised that GNU
ld produced only warnings for the example given, and that linking
succeeded. I wonder why this does not happen; two explanations come
to mind:
* There are important programs around that use definition syntax
(i.e., no extern) for global variable declarations and C compiler
writers want their compilers to work on these programs.
* There is no good way to let the linker work the way I expect it;
maybe you cannot have strong symbols in the bss segment or something
(although I would find that surprising).
- anton
--
M. Anton Ertl
an...@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[I think it's a historical artifact. The early linkage behavior of C
was based on Fortran COMMON statements, where you could have multiple
uninitialized versions and optionally one initialized (BLOCK DATA)
version. -John]
Ian Lance Taylor
> What I expected is that the linker complains about duplicate symbols
> (irrespective of optimization level). I was very surprised that GNU
> ld produced only warnings for the example given, and that linking
> succeeded.
The linker is acting correctly. When GCC sees an uninitialized
definition, it emits a common symbol. As our esteemed moderator says,
that is a historical artifact. GCC supports the -fno-common option,
q.v., to change this behaviour.
Ian
George Neuner
<DrDiet...@aol.com> wrote:
>George Neuner schrieb:
>
>> A problem occurs when there are multiple definitions in separate
>> files. Technically, by the standards, there can be only 1 definition
>> of a name at top level ... all other references to the name, including
>> any forward references to the name in the same file, *must* be
>> "extern" declarations.
>[...]
>> Every compiler complained about multiple definitions of 'x' when all
>> the definitions were strong - ie. when 'x' was initialized in both
>> files.
>
>How does a compiler know about other files?
It doesn't.
>I assume that the definitions were in the same compilation unit, i.e. in
>the header files included by both source files. Otherwise it's a matter
>of object file formats and linkers, what will happen with multiple
>definitions of the same symbol in multiple object files.
No. The definitions were in separate source files. You snipped the
source with which I tested.
I tested 4 ways: with two weak definitions of 'x' (no initialization),
two strong definitions (with initialization), and with one strong and
one weak definition (both ways). The definition of the variable
'garbage' was left weak in all cases.
>> However, if either definition was weak, I was able to build an
>> executable. When both definitions were weak, however, some of the
>> compilers produced optimized executables with NO storage at all
>> allocated for the name 'x'.
>
>What's "NO" storage? A NULL address output by printf?
With two weak definitions of 'x' and a weak definition of 'garbage',
the compiler did not allocate any storage in the data segment. The
linker did not object to having no global data (why should it?) and
produced an executable that crashed with an illegal address reference
because the system loader didn't assign any pages to the empty data
segment. I checked the linker's map file to verify that no storage
had been allocated for variables.
This happened with 4 different compilers under high optimization.
George
Hans-Peter Diettrich
> With two weak definitions of 'x' and a weak definition of 'garbage',
> the compiler did not allocate any storage in the data segment. The
> linker did not object to having no global data (why should it?) and
> produced an executable that crashed with an illegal address
> reference because the system loader didn't assign any pages to the
> empty data segment.
An allocation is not required, because your code doesn't contain
memory reads from the segment. Nonetheless even an empty segment
should have a valid address at runtime.
> I checked the linker's map file to verify that no storage had been
> allocated for variables.
Did the data segment occur in that list at all?
A zero size were perfectly valid, but no segment definition at all would
be illegal.
IMO there must exist a reason, why the loader cannot patch the stored
'&x' offset with the address of the data segment. Most probably it
could not find the according segment symbol in it's load map, because
the linker failed to emit the *definition* of that segment (symbol),
while *referencing* it in the fixup table.
Otherwise, when the segment (symbol) could be found in the load map,
it would be harmless if it's address were unassigned or
illegal. Patching the '&x' offset with an invalid base address would
end up in garbage in the printf() output, but never in an read access
to that address.
> This happened with 4 different compilers under high optimization.
Again an indication of an buggy linker.
DoDi
David Thompson
<gneu...@comcast.net> wrote:
> On Tue, 19 May 2009 14:42:40 -0400, George Neuner
> <gneu...@comcast.net> wrote:
>
> >On Sat, 16 May 2009 08:39:28 +0100, Nathaniel McIntosh
> ><mcin...@cup.hp.com> wrote:
> >
> >>
> >> foo.c bar.c
> >> ----- -----
> >> ... ...
> >> double x; int x = 0;
> >> ... int garbage;
> >>
> >>Most C compilers will compile these two modules without complaint;
> >>when you link foo.o and bar.o into an executable, the "strong"
> >>definition of "x" from bar.o is favored over the "weak" definition in
> >>foo.o, and you wind up with a final "x" entity that is 4 bytes in size
> >>(assuming an ILP32 compilation model), not 8 bytes.
> >>
> >>In spite of the fact that foo.c contains functions that store 8-byte
> >>values to "x", the program works without optimization because the
> >>variable "garbage" (unused as it turned out) happens to be allocated
> >>just after "x" in memory. If the optimizer plays with the storage
> >>allocation such that some other critical variable appears just after
> >>"x", then the application fails.
> >
> >No. Your example will work regardless. Assuming those definitions
> >were global in the source files, the result will be 2 different
> >variables named 'x' - an integer in bar.o and a double real in foo.o.
> >
Not so. There are indeed two different definitions of objects named x,
(both) with external linkage, meaning they should be the same object.
The C standard does not specify what happens, and I don't know of any
implementation that allocates two (although that wouldn't violate the
non-specification). I've seen some give an error, some take the first
encountered, some take the 'strong' (initialized) one as PP said, some
take the nonzero-initialized one if any (none in this example).
If both (or at least one) declaration had 'static', then they would
(definitively) be separate, and accesses to each correct; see below.
> >If, OTOH, the code was:
> >
> > foo.c bar.c
> > ----- -----
> > ... ...
> > extern double x; int x = 0;
> > ... int garbage;
> > ...
> >
> >then the compiler/linker would create only the integer "x" and any
> >functions in foo that accessed "x" as a double real would do so in
> >error. ...
> I tested them by compiling the following code (in 32-bits) in both
> debug and optimized versions.
>
> ==== test.c ====
> extern void DoStuffWithIntX( void );
> extern void DoStuffWithDblX( void );
>
> int main(int argc, char* argv[])
> {
> DoStuffWithDblX( );
> DoStuffWithIntX( );
> return 0;
> }
>
> ==== foo.c ====
> #include <stdio.h>
> double x;
>
> void DoStuffWithDblX( void )
> {
> printf( "double X is at %p\n", &x );
> }
>
> ==== bar.c ====
> #include <stdio.h>
> int x;
> int garbage;
>
> void DoStuffWithIntX( void )
> {
> printf( "integer X is at %p\n", &x );
> }
Nit: %p is specified to work for void*. The C standard allows
different pointer types to have different representations including
sizes, and then this needs a cast. There have been such machines in
the past, but nowadays practically all machines -- at least ones with
hosted C and thus stdio -- are byte addressed and at least all object
(data) pointers are the same and this 'happens' to work.
> ...
> C does not allow either duplicate definitions or multiple definitions
> of the same named object in any name overloading class (of which the
> "top level", ie. global names, is one). You can have duplicated
> _declarations_, but not duplicated _definitions_.
You can't have multiple definitions in the same scope. You can have
multiple declarations for static duration objects, which includes all
at file-scope aka top-level. (Global is ambiguous; people sometimes
use it to mean throughout a translation unit, sometimes over the whole
program.) Any declaration of an automatic variable is a definition (so
there can be only one). Any declaration of a typedef is like a
definition (although the standard doesn't call it that) so ditto in C;
but in C++ you can 'benignly' redeclare/define a typedef. You can have
only one declaration of the contents of a given struct or union type.
And discussion can be confused by the fact that the _syntactic_
construct 'declaration' is used for both declarations and definitions
of objects, declarations of types (there are no definitions), and
declarations of functions (definitions use a different syntax).
(Definitions and declarations of _objects of_ struct or union type
follow the rules for objects in general; this constrains whether you
can syntactically combine the declarations for types and objects.)
Remaining examples assume file-scope; block-scope is mostly different.
> "extern double x;" is a declaration. No storage is allocated
> for the variable, its name is a reference
> to a definition elsewhere.
Right.
> "double x = 0.0;" is a definition. This allocates storage
> for the variable. Because it is initialized,
> this is considered a "strong" definition.
Right, except that there is no 'strong' or 'weak' in the standard.
Some implementations distinguish them, and may distinguish initializer
explicit or not (see below), or nonzero or zero. And note that extern
double x = 0.0; is also a definition.
> "double x;" is a definition if there is a preceeding
> declaration, else it is both. Because it
> is _not_ initialized, this is considered
> a "weak" definition.
>
Not really. This is a 'tentative definition'; if and only if there is
no with-initializer definition elsehwere in the translation unit ~
source file, the compiler synthesizes one with an initializer of zero.
(Which in C means integer zero, floating zero, or null pointer, as
applicable.) That synthesized definition may well be 'weak'.
> "static double x;" is a declaration if there is a subsequent
> strong definition, else it is both. This
> allocates storage for the variable.
This is also a tentative definition, but in addition it gives the name
'internal linkage'; that means this name is not accessible to other
translation units. If another t.u. has a reference 'extern T x;' that
ISN'T resolved to this x. (The object itself, however, is accessible
if this t.u. returns or otherwise makes available a pointer to it.)
In implementation terms, this allocates space with no linker name,
usually as a single anonymous block for the whole t.u. It may have an
info/debugging-only name something like module$x or #nomatch.x.
Again a tentative definition turns into a definition with value zero
if there is not a with-initializer one in the same t.u.
Or to lay out the cases:
static double x = 0; is a definition with internal linkage; there
can be no other definition of x at file-scope in this t.u., but there
can be a *distinct* internal='static' x in every other t.u. and an
external=global='extern' one in some (one) other t.u.
static double x; is a tentative definition; if there is not a
definition with initializer elsewhere in this t.u., there is
implicitly one with value zero. And all else as just above.
> A problem occurs when there are multiple definitions in separate
> files. Technically, by the standards, there can be only 1 definition
> of a name at top level ... all other references to the name, including
> any forward references to the name in the same file, *must* be
> "extern" declarations.
Only one _with external linkage_. Which is what people often, but
definitely not always, mean when they say 'global'.
> However, the requirement for specifying "extern" is routinely relaxed
> for forward references to functions and to recursive structures. For
> such declarations, compilers implicitly assume "extern". It appears
> that some compilers also assume "extern" in the case of weak variable
> definitions.
Functions use a syntactic distinction.
/*extern*/ int foo (whatever) /* no initializer possible */ ;
is a declaration and references a definition elsewhere.
/*extern*/ int foo (whatever) { body } is a definition
that can be referenced. 'extern' is optional=default.
static int foo (whatever) ; and
static int foo (whatever) { body }
have internal linkage; this foo is not accessible by name elsewhere.
(Again a pointer could be provided by other, explicit means.)
Types don't exist at runtime at all. You can write the same typedef
and struct, union and enum declarations in multiple translation units
(typically by #include'ing the same .h file) but you formally get
separate _compatible_ types, not the same types.
> Now the problem with assuming "extern" for weak definitions is that it
> in conflict with the assumption of file scope visibility. Judging by
> the C standard, a top level variable definition (strong or weak) is
> not meant to name an external object, but rather to introduce a
> variable with file scope ... a separate "extern" declaration is needed
> to "import" the name into a different scope. In keeping with the
> principle of least surprise, it would be better to assume a weak
> variable definition is "conditionally static" rather than "extern",
> conditionally allocate storage for it and have the linker resolve the
> references. Some of the compilers actually did something like this
> and created 2 separate variables.
I'm not sure quite what you wanted/preferred here, but the irregular
and implementation-dependent specification in standard C is because
there were already variations across implementations before C89 that
had to be accommodated or there would have been no standard at all,
and now we're basically stuck with their designs. Quite a few of them
were originally designed to coexist with or even share FORTRAN COMMON,
which allowed _zero or_ one definition. C++ eliminated the 'tentative
definition' crock, but kept (all?) the rest, and added namespaces.
(And overloading, but that just gives finer granularity as to which
functions are 'the same' and doesn't affect objects.)
Hint: if your compiler/linker docs/whatever mention 'common', it's
likely that multiple t.u.s with tentative->synthesized definitions,
and possible with explicit-to-zero ones, will 'merge'. For gcc in
particular, at least some versions on some targets, -fno-common will
make a big difference.