We use compilers on a daily basis as if their correctness is a given, but compilers are programs too, and can potentially contain bugs. I always wondered about this infallible robustness. Have you ever encountered a bug in the compiler itself? What was it and how did you realize the problem was in the compiler itself?
...and how do they make compilers so reliable?
They get tested thoroughly via usage by thousands or even millions of developers over time.
Also, the problem to be solved is well defined (by a very detailed technical specification). And the nature of the task lends itself easily to unit / system tests. I.e. it is basically translating textual input in a very specific format to output in another kind of well defined format (some sort of bytecode or machine code). So it is easy to create and verify test cases.
Moreover, usually the bugs are easy to reproduce too: apart from the exact platform and compiler version info, usually all you need is a piece of input code. Not to mention that the compiler users (being developers themselves) tend to give far more precise and detailed bug reports than any average computer user :-)
In addition to all the great answers so far:
You have an "observer bias". You don't observe bugs, and therefore you assume that there aren't any.
I used to think like you do. Then I started writing compilers professionally, and let me tell you, there are lots of bugs in there!
You don't see the bugs because you write code that is just like 99.999% of all the rest of the code that people write. You probably write perfectly normal, straightforward, clearly correct code that calls methods and runs loops and doesn't do anything fancy or weird, because you're a normal developer solving normal business problems.
You don't see any compiler bugs because the compiler bugs aren't in the easy-to-analyze straightforward normal code scenarios; the bugs are in the analysis of weird code that you don't write.
I on the other hand have the opposite observer bias. I see crazy code all day every day, and so to me the compilers seems to be chock full of bugs.
If you sat down with the language specification of any language, and took any compiler implementation for that language, and really tried hard to determine whether the compiler exactly implemented the spec or not, concentrating on obscure corner cases, pretty soon you'd be finding compiler bugs quite frequently. Let me give you an example, here's a C# compiler bug I found literally five minutes ago.
static void N(ref int x){}
...
N(ref 123);
The compiler gives three errors.
Obviously the first error message is correct and the third one is a bug. The error generation algorithm is trying to figure out why the first argument was invalid, it looks at it, sees that it is a constant, and does not go back to the source code to check whether it was marked as "ref"; rather, it assumes that no one would be foolish enough to mark a constant as ref, and decides that the ref must be missing.
It's not clear what the correct third error message is, but this isn't it. In fact, it is not clear if the second error message is correct either. Should overload resolution fail, or should "ref 123" be treated as a ref argument of the correct type? I'll now have to give it some thought and talk it over with the triage team so that we can determine what the correct behaviour is.
You've never seen this bug because you would probably never do something so silly as to try to pass 123 by ref. And if you did, you probably wouldn't even notice that the third error message is nonsensical, since the first one is correct and sufficient to diagnose the problem. But I do try to do stuff like that, because I'm trying to break the compiler. If you tried, you'd see the bugs too.
Are you kidding me? Compilers have bugs too, loads really.
GCC is probably the most celebrated of open source compilers in the planet and take a look at its bug database: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=---
Between GCC 3.2 and GCC 3.2.3 take a look at how many bugs got fixed: http://gcc.gnu.org/gcc-3.2/changes.html
As for others like Visual C++, I don't even want to begin.
How do you make compilers reliable? Well for a start they have loads and loads of unit tests. And the whole planet uses them so no dearth of testers.
Seriously though, compiler developers I like to believe are superior programmers and while they are not infallible they do pack in quite a punch.
I've encountered two or three in my day. The only real way to detect one is to look at the assembly code.
Although compilers are highly reliable for reasons other posters have pointed out, I think compiler reliability is often a self-fulfilling assessment. Programmers tend to view the compiler as the standard. When something goes wrong, you assume its your fault (because 99.999% of the time it is), and change your code to work around the compiler problem rather than the other way around. For example, code crashing under a high optimization setting is definitely a compiler bug, but most people just set it a little lower and move on without reporting the bug.
Compilers have several properties which lead to their correctness:
We use compilers on a daily basis
...and how do they make compilers so reliable?
They don't. We do. Because everybody uses them all the time, bugs are found quickly.
It's a numbers game. Because compilers get used so pervasively, it is highly likely that any bug will be triggered by someone, but because there's such a large number of users, it is highly unlikely that that someone will be you specifically.
So, it depends on your viewpoint: across all users, compilers are buggy. But it is very likely that someone else will have compiled a similar piece of code before you did, so if their was a bug, it would have hit them, not you, so from your individual point of view, it looks like the bug was never there.
Of course, on top of that, you can add all the other answers here: compilers are well researched, well understood. There is this myth that they are hard to write, which means that only very smart, very good programmers actually attempt to write one, and are extra careful when they do. They are generally easy to test, and easy to stress test or fuzz test. Compiler users tend to be expert programmers themselves, leading to high quality bug reports. And the other way around: compiler writers tend to be users of their own compiler.
In addition to all the answers already, I'd like to add:
I believe a lot of times, the vendors are eating their own dog food. Meaning, they are writing the compilers in themselves.
I've run into compiler bugs often.
You can find them in the darker corners where there are fewer testers. For example, to find bugs in GCC you should try:
Several reasons:
They are usually very good at -O0. In fact if we suspect a compiler bug, we compare -O0 versus whatever level we are trying to use. Higher optimization levels go with greater risk. Some are even deliberately so, and labeled as such in the documentation. I've encountered a great many (at least a hundred during my time), but they are becoming much rarer recently. Nevertheless in pursuit of good specmark numbers (or other benchmarks important to marketing), the temptation to push the limits is great. We had problems a few years back where a vendor (to go unnamed) decided to make violation of parenthesis default -rather than some special clearly labeled compile option.
It can be hard to diagnose a compiler error versus say a stray memory reference, a recompile with different options may simply scramble the relative positioning of data objects within memory, so you don't know if it is your source code's Heisenbug, or a buggy compiler. Also many optimizations make legitimate changes in the order of operations, or even algebraic simplifications to your algebra, and these will have different properties with respect to floating point rounding and under/overflow. It is hard to disentangle these effects from REAL bugs. Hard core floating point computing is tough for this reason, because bugs and numerical sensitivty are often not easy to disentangle.
Compiler bugs aren't all that rare. The most common case is for a compiler to report an error on code that should be accepted, or for a compiler to accept code that should have been rejected.
Have you ever encountered a bug in the compiler itself? What was it and how did you realize the problem was in the compiler itself?
Yup!
The two most memorable were the first two I ever ran across. They were both in the Lightspeed C compiler for 680x0 Macs back about 1985-7.
The first one was where, in some circumstances, the integer postincrement operator did nothing - in other words, in a particular piece of code, "i++" simply didn't do anything to "i". I was pulling my hair out until I looked at a disassembly. Then I just did the increment a different way, and submitted a bug report.
The second was a bit more complicated, and was a really an ill-considered "feature" that went awry. The early Macs had a complicated system for doing low-level disk operations. For some reason I never understood - probably having to do with creating smaller executables - rather than the compiler just generating the disk operation instructions in-place in the object code, the Lightspeed compiler would call an internal function, which at runtime generated the disk operation instructions on the stack and jumped there.
That worked great on 68000 CPUs, but when you ran the same code on a 68020 CPU, it would often do weird things. It turned out that a new feature of the 68020 was a primitive instruction 256-byte instruction cache. This being early days with CPU caches, it had no notion of the cache being "dirty" and needing to be refilled; I guess the CPU designers at Motorola didn't think about self-modifying code. So if you did two disk operations close enough together in your execution sequence, and the Lightspeed runtime built the actual instructions at the same location on the stack, the CPU would erroneously think it had an instruction cache hit and run the first disk operation twice.
Again, figuring that out took some digging around with a disassembler, and a lot of single-stepping in a low-level debugger. My workaround was to prefix every disk operation with a call to a function that did 256 "NOP" instructions, which flooded (and thus cleared) the instruction cache.
Over the 25-ish years since then, I've seen fewer and fewer compiler bugs over time. I think there are a couple of reasons for that:
Found a glaring error in Turbo Pascal 5.5 years ago. An error present in neither the previous (5.0) nor the next (6.0) version of the compiler. And one that should have been easy to test, as it wasn't a cornercase at all (just a call that's not that commonly used).
In general, certainly the commercial compiler builders (rather than hobby projects) will have very extensive QA and testing procedures in place. They know their compilers are their flagship projects and that flaws will look very bad on them, worse than they'd look on other companies making most other products. Software developers are an unforgiving bunch, our tool suppliers let us down we're likely to go look for alternatives rather than wait for a fix from the supplier, and we're very likely to communicate that fact to our peers who might well follow our example. In many other industries that's not the case, so the potential loss to a compiler maker as a result of a serious bug is far greater than that to say a maker of video editing software.
Yep, I encountered a bug in the ASP.NET compiler just yesterday:
When you use strongly typed models in views there is a limit to how many parameters templates can contain. Obviously it can't take more than 4 template parameters, so that both examples below make it too much for the compiler to handle:
ViewUserControl<System.Tuple<type1, type2, type3, type4, type5>>
Would not compile as is but will if type5 is removed.
ViewUserControl<System.Tuple<MyModel, System.Func<type1, type2, type3, type4>>>
Would compile if type4 is removed.
Note that System.Tuple has many overloads and can take up to 16 parameters (it's crazy I know).
Compiler bugs happen, but you tend to find them in odd corners...
There was a weird bug in the Digital Equipment Corporation VAX VMS C compiler in the 1990's
( I was wearing an onion on my belt, as was the fashion at the time)
An extraneous semicolon anywhere preceding a for loop would be compiled as the body of the for loop.
f(){...}
;
g(){...}
void test(){
int i;
for ( i=0; i < 10; i++){
puts("hello");
}
}
On the compiler in question, the loop executes only once.
it sees
f(){...}
g(){...}
void test(){
int i;
for ( i=0; i < 10; i++) ; /* empty statement for fun */
{
puts("hello");
}
}
That cost me lots of time.
The older version of the PIC C compiler we (used to) inflict on work experience students couldn't generate code that used the the high priority interrupt correctly. You had to wait 2-3 years and upgrade.
The MSVC 6 compiler had a nifty bug in the linker, it would segmentation fault and die from time to time for no reason. A clean build generally fixed it ( but sigh not always).
When the behaviour of your software is different when compiled with -O0 and with -O2, then you have found a compiler bug.
When the behaviour of your software is just different from what you expect, then chances are that the bug is in your code.
I've seen several compiler bugs, reported a few myself (specifically, in F#).
That said, I think compiler bugs are rare because people who write compilers are generally very comfortable with the rigorous concepts of computer science that make them really conscious about the mathematical implications of code.
Most of them are presumably very familiar with things like lambda calculus, formal verification, denotational semantics etc. -- stuff that an average programmer like me can only barely comprehend.
Also, there's usually a fairly straightforward mapping from input to output in compilers, so debugging a programming language is probably a lot easier than debugging, say, a blog engine.
I found a bug in the C# compiler not too long ago, you can see how Eric Lippert (who is on the C# design team) figured out what the bug was here.
In addition to the answers already given, I'd like to add a few more things. Compiler designers are often extremely good programmers. Compilers are very important: most programming is done using compilers, so it's imperative the compiler is of high quality. It's therefore in the best interest of companies making compilers to put their best people on it (or at least, very good ones: the best ones might not like compiler design). Microsoft would very much like their C and C++ compilers to work properly, or the rest of the company can't do their jobs.
Also, if you're building a really complex compiler, you can't just hack it together. The logic behind compilers is both highly complex and easy to formalize. Hence, these programs will often be built in a very 'robust' and generic way, which tends to result in less bugs.
In some domains, such as avionics software, there are extremely high certification requirements, on the code and hardware, as well as on the compiler. About this last part, there is a project which aims at creating a formally-verified C compiler, called Compcert. In theory, this kind of compiler is as reliable as they come.