7 ms·

When you see a heisenbug in C, suspect your compiler’s optimizer

40 points by rglovejoy 17y ago

antirez 17y ago
Switching off the compiler optimizer may just "hide" the bug because memory accesses are reordered in a way that makes the bug (for instance a memory corruption or some allocation problem) less likely to trigger a segmentation fault. To think that every time you have a bug that is suppressed switching off the optimizer you found a compiler bug is not a good idea. 99.99999% of the times the problem is in your code. Experienced programmers usually will continue to think the bug is in their own code unless they can prove otherwise.
- dkersten 17y ago
  Exactly. Select is probably not broken. If the program works in some compiler optimization levels and not others, then think about what the optimizer is doing and how this may change the circumstances that the bug may appear. I agree that it is probably a memory corruption issue and that by turning off optimizations, you are hiding the sympton and not fixing the bug. I think there should be a law that states: if you use a language like C or C++, you must ensure it compiles cleanly with all warnings turned on AND runs without error under a tool like Valgrind. There are simply too many places where bugs may creep in to leave it to chance. The tools exist - use them!
  - imurray 17y ago
    Very good advice. I assume my C code does have memory blunders until I have run extensively through valgrind, after which I might begin to believe any other analysis I have done that suggests the code is correct. I also tend to test a build linked with gcc’s mudflap: gcc -g -fmudflap -lmudflap Your program will run much faster than under valgrind. I have had bugs that have been missed by valgrind but caught with mudflap and vice-versa. Don’t try to link with mudflap and run under valgrind at the same time though, valgrind won’t work.
    - bd_at_rivenhill 17y ago
      Many thanks, I've used valgrind a lot, but never heard of mudflap, I'll give it a try.
      - imurray 17y ago
        Depending on your distribution it may not be installed automatically with gcc. The package you need is called libmudflap0-4.4-dev in Ubuntu 9.10.
  - alttab 17y ago
    I worked at a shop where I wrote C for almost 2 years and we ran into this case twice. It was a compiler bug in the optimizer, and only happened when it tried to also optimize the way specific structures were laid out in memory. Using the zero-index array at the end of a struct to get a pointer to the following buffer in this case caused the offset to be wrong and we were over running our buffer. This was xlC though.
- ssp 17y ago
  Very true. It doesn't prove anything that -O0 works while -O3 doesn't. It's still almost certainly a bug in your code. I don't think the percentage is 99.99999% though. Compiler bugs do exist. I have seen several more than four in 12 years of C programming.
  - tetha 17y ago
    Well, the percentage is a way of saying: You do not encounter a compiler bug in day-to-day-programming. 'four compiler bugs in 12 years' is just another way of saying: You do not encounter a compiler bug in day-to-day-programming. (Note the 'day-to-day'. Day-to-day-programming and 'all programming you do in x*10 years of C-programming' are very different sets of code written)
- j_baker 17y ago
  Especially if it involves multithreading. Altering the timing of things means everything.
  - prodigal_erik 17y ago
    Turning off the optimizer can also hide memory barriers you forgot you'd need, by doing extra loads or stores rather than keeping an outdated value in a register. That said, I have seen exactly one optimizer bug that I know of. Back in 1993, Borland C++ completely omitted one of my inline destructors from the binary. I had to review the assembly to convince myself I wasn't imagining things.
    - pmjordan 17y ago
      I've seen my fair share of compiler (and even assembler) bugs, but they were almost all in customised, proprietary compilers for game consoles. Those get nowhere near the number of eyeballs that GCC does. 99 times out of a 100, weird bugs are my own stupid fault. The ratio is even higher for multithreaded code.
- Estragon 17y ago
  Experienced programmers usually will continue to think the bug is in their own code unless they can prove otherwise. s/Experienced/Mature/ Because ESR has plenty of experience. The kind of reasoning in the OP comes from arrogance and the narcissism of valuing one's self-concept as a competent individual over getting the job done efficiently.
  - sketerpot 17y ago
    If someone other than ESR had written this article, would you have reacted the same way?
    - pmjordan 17y ago
      Actually, that's pretty much accurate. I initially didn't even realise this was written by ESR and just assumed the author was very inexperienced. ESR however should know better, though to be honest I don't even know if the guy still writes code. I hate to stoop to ad hominem attacks, but re-reading it knowing that it's him I get the impression this was a petty reaction to some feud with a GCC dev. In any case I'd love to know who the hell is upvoting this "story".
      - kelnos 17y ago
        Yes, when I started reading, my first thought was, "wow, sounds like someone pretty inexperienced." After I noticed it was written by ESR, that changed to, "wow, sounds like someone pretty arrogant." The fact of the matter is that a compiler like gcc is used by thousands (tens of thousands? more?) of people almost daily. Usually you have to be doing some pretty crazy stuff to find a bug in it. Bugs that go away when you turn off optimizations are usually either race-condition or memory-access related.
        pmjordan 17y ago
        Or uninitialised local variables, which are affected by the difference in register allocation, but really you should be enabling the corresponding warning.
- argv_empty 17y ago
  As an example... I once wrote some MPI code for class. It ran properly at -O0, though the compiler warned of a variable that was declared but never used. Compiling at a level other than -O0 or removing that variable declaration from the source code caused the program to segfault immediately. It turned out to be a memory error somewhere else in the program (I forget exactly what, but it was over my misunderstanding of some part of the message passing calls).
- varjag 17y ago
  While it's not an everyday occurrence, it happens a lot more often than you would believe. In Linux kernel, there is actually official list of compiler versions that produce faulty code.
- cdavid 17y ago
  It depends on the context as well. It is much more likely to find a bug in gfortran for solaris sparc than gcc on x86 linux, for example. The only time I keep the compiler bug in mind is when working with gcc 4.x compiler on windows. I don't have the experience of ESR, but I find the advice a bit dangerous if taken as a general one. Especially, the idea that a heisenbug is often caused by a compiler: most likely, the heisenbug is not a heisenbug at all, but just less visible depending on the compiler flags. That was the case for the vast majority of "heisenbugs" I have encountered in C.
- jmaynard 17y ago
  FWIW, I do tend to think the problem's in my code until proven otherwise. That's why I spent a week tearing my hair out trying to find the problem. And, for the naysayers, Hercules is built with -W -Wall.
Vivtek 17y ago
I found an optimizer bug once. I can't remember the exact circumstances, but it had to do with some fancy inline incrementing I was doing. The very concept that I'd found a bug in somebody else's code floored me. I was young.
nkurz 17y ago
My experience goes in a different direction: when you see different behavior when compiled with and without optimization, suspect a memory allocation error or overrun. While compiler optimization bugs do exist, I've more often found that the problem is real. If you are working with your own code and care if it works: 1) Turn on all compiler warnings 2) Change your code so it compiles clean 3) Run under Valgrind (or equivalent). 4) Address all reported errors, specifically whitelisting them if necessary. 5) If you find a bug, don't stop until you've found the cause. You're done when you understand what caused the bug to appear, not when the symptoms go away. 6) Use open source tools, since otherwise you'll be tempted to blame some unspecified 'bug in the compiler'. (not that ESR would be using any other) 7) If it is a compiler bug, report it, along with the smallest test case you can generate.
- wheels 17y ago
  This is definitely along the right path. One proviso that I'd note: Most of the time in my own debugging when I've run into something that goes away at a different level of optimization it's uninitialized variables / memory. Valgrind is the shizzle.
tptacek 17y ago
-O3 isn't "riskier". It's just harder to debug under.
- callahad 17y ago
  I know little about C compilers, but if -O3 resulted in segfaults while other settings did not, how is it not riskier? Are the different optimization levels independent such that this bug could have appeared anywhere, but just happened to be in one of the strategies used by -O3?
  - tptacek 17y ago
    Because, like a number of other people have pointed out upthread, it can make the impact of memory corruption problems more immediate.
  - wingo 17y ago
    There is also the possibility that if your program has an aliasing bug, the bug may only cause failure at -O2 but not at -O0 or -O1. See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35653 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35653, for example.
- regehr 17y ago
  -O3 is indeed riskier. All experienced embedded systems developers know this: embedded compilers tend to be much buggier than compilers for desktop platforms. But desktop compilers are buggy too. Over the last couple years my group has reported 190 bugs to compiler development teams. A lot of these bugs turn up only at higher optimization levels. If you search on my email address "regehr@cs.utah.edu" as bug reporter in either GCC or LLVM's bugzilla, you can see plenty of examples.
  - tptacek 17y ago
    I defer to the gentleman with the University research project dedicated to finding compiler bugs. :)
liuliu 17y ago
Except multi-thread programming, I didn't find any compiler's optimizer related bugs. The truth is, most heisenbugs I found are somewhat related to memory access. It is just too risky to assume it is a compiler bug. I always think in the other way: unless you can prove (by generating assembly code and a possible scenario), the bug is in your code.
jgrahamc 17y ago
It's seems strange me to instantly suspect that your compiler's optimizer is at fault. Which is more likely: you've found a bug in a compiler used the world over, or you've screwed up memory access? Since C makes it easy to overrun memory, it's pretty easy to make horrible mistakes and have those have seemingly random consequences. The fact that the bug changes when you change optimizer settings, add trace statements, or add debug code would make me suspect memory corruption first. In fact, I think it's a good assumption to always begin suspecting your own code.
ja27 17y ago
It's not quite the same as the 'heisenbug' but I've seen a couple of cases over the years where a mysterious problem was resolved by moving to the latest update of the C/C++ runtime. It's weird how many enterprises are fine with running years behind on maintenance on that.
sreque 17y ago
I have an example of a bug I found that looked like an optimization bug but was really a user bug. Someone had the bright idea of sprintf-ing to a string and using the string itself as one of the format arguments to the sprintf call. When compiled with gcc the code would still run fine, but when compiling with -O1 the string would end up garbled. The problem (and advantage, performance-wise) of C is that most of the time you do something wrong, the behavior is undefined, whereas most higher-level languages will spend the CPU cycles to protect you from yourself. Another example I can't remember the details of, but it was related to the fact that gcc adds code to zero-initialize your stack on first access unless optimizations are turned on. Code that checked for null pointers worked fine until optimizations were turned on, at which point it was discovered that a variable was being used uninitialized.
losethos 17y ago
Ba ha--You guys have never worked with your own company's compilers. At Ticketmaster my boss wrote our PASCAL compiler and I would find bugs. I wrote my C+ compiler for LoseThos and I find bugs. http://www.losethos.com http://www.losethos.com Generally, you should suspect your own code before the compiler, but it depends on how much of a work-out the compiler has been put through. Even with me, though, I sometimes doubt my own compiler wrongly.
WalterBright 17y ago
Optimizer and code gen problems are pretty hard for users to diagnose correctly, so most compiler vendors put a high priority on fixing them.
jmaynard 17y ago
I didn't expect a kind of Spanish inquisition... The terminally curious may download a file containing the assembler output, and the C source, of the offending file from http://www.hercules-390.org/esamebug.zip http://www.hercules-390.org/esamebug.zip . This corresponds to revision 5627 of the Hercules emulator as found in the Subversion repository at svn://svn.hercules-390.org/hercules/trunk . The emulator itself is at http://www.hercules-390.org http://www.hercules-390.org . The routine is in the generated assembler as z900_load_multiple_long.
- jgrahamc 17y ago
  Can you also give us a test case?
  - jmaynard 17y ago
    I might be able to build one to be executed under Hercules...let me work on that. My current test case is under NDA.
    - jmaynard 17y ago
      Done. You can get it at http://www.hercules-390.org/lmg-test.zip http://www.hercules-390.org/lmg-test.zip .
      - jgrahamc 17y ago
        Cool. Any particular things I need to know? e.g. which platform should I try this on? Also, have you run valgrind against the test?
        jmaynard 17y ago
        The test has only been shown to fail on Mac OS X Snow Leopard with gcc 4.2.1. I haven't been able to make it fail on any other platform. Because of the code involved, I suspect it won't fail at all on anything but 32-bit Intel. I've never run valgrind...it'll be interesting to see just what it does to Hercules execution speed. mudflap, too. Getting that built into the code might get even more interesting.
ivan_w 17y ago
I found the bug (I think).. It's not "really" an optimizer bug per-se (although it is CLEARLY triggered by the optimizer). Always treat __asm with caution ! --Ivan

40 points by rglovejoy 17y ago

Switching off the compiler optimizer may just "hide" the bug because memory accesses are reordered in a way that makes the bug (for instance a memory corruption or some allocation problem) less likely to trigger a segmentation fault. To think that every time you have a bug that is suppressed switching off the optimizer you found a compiler bug is not a good idea. 99.99999% of the times the problem is in your code. Experienced programmers usually will continue to think the bug is in their own code unless they can prove otherwise.

dkersten 17y ago
Exactly. Select is probably not broken. If the program works in some compiler optimization levels and not others, then think about what the optimizer is doing and how this may change the circumstances that the bug may appear. I agree that it is probably a memory corruption issue and that by turning off optimizations, you are hiding the sympton and not fixing the bug. I think there should be a law that states: if you use a language like C or C++, you must ensure it compiles cleanly with all warnings turned on AND runs without error under a tool like Valgrind. There are simply too many places where bugs may creep in to leave it to chance. The tools exist - use them!
- imurray 17y ago
  Very good advice. I assume my C code does have memory blunders until I have run extensively through valgrind, after which I might begin to believe any other analysis I have done that suggests the code is correct. I also tend to test a build linked with gcc’s mudflap: gcc -g -fmudflap -lmudflap Your program will run much faster than under valgrind. I have had bugs that have been missed by valgrind but caught with mudflap and vice-versa. Don’t try to link with mudflap and run under valgrind at the same time though, valgrind won’t work.
  - bd_at_rivenhill 17y ago
    Many thanks, I've used valgrind a lot, but never heard of mudflap, I'll give it a try.
    - imurray 17y ago
      Depending on your distribution it may not be installed automatically with gcc. The package you need is called libmudflap0-4.4-dev in Ubuntu 9.10.
- alttab 17y ago
  I worked at a shop where I wrote C for almost 2 years and we ran into this case twice. It was a compiler bug in the optimizer, and only happened when it tried to also optimize the way specific structures were laid out in memory. Using the zero-index array at the end of a struct to get a pointer to the following buffer in this case caused the offset to be wrong and we were over running our buffer. This was xlC though.
ssp 17y ago
Very true. It doesn't prove anything that -O0 works while -O3 doesn't. It's still almost certainly a bug in your code. I don't think the percentage is 99.99999% though. Compiler bugs do exist. I have seen several more than four in 12 years of C programming.
- tetha 17y ago
  Well, the percentage is a way of saying: You do not encounter a compiler bug in day-to-day-programming. 'four compiler bugs in 12 years' is just another way of saying: You do not encounter a compiler bug in day-to-day-programming. (Note the 'day-to-day'. Day-to-day-programming and 'all programming you do in x*10 years of C-programming' are very different sets of code written)
j_baker 17y ago
Especially if it involves multithreading. Altering the timing of things means everything.
- prodigal_erik 17y ago
  Turning off the optimizer can also hide memory barriers you forgot you'd need, by doing extra loads or stores rather than keeping an outdated value in a register. That said, I have seen exactly one optimizer bug that I know of. Back in 1993, Borland C++ completely omitted one of my inline destructors from the binary. I had to review the assembly to convince myself I wasn't imagining things.
  - pmjordan 17y ago
    I've seen my fair share of compiler (and even assembler) bugs, but they were almost all in customised, proprietary compilers for game consoles. Those get nowhere near the number of eyeballs that GCC does. 99 times out of a 100, weird bugs are my own stupid fault. The ratio is even higher for multithreaded code.
Estragon 17y ago
Experienced programmers usually will continue to think the bug is in their own code unless they can prove otherwise. s/Experienced/Mature/ Because ESR has plenty of experience. The kind of reasoning in the OP comes from arrogance and the narcissism of valuing one's self-concept as a competent individual over getting the job done efficiently.
- sketerpot 17y ago
  If someone other than ESR had written this article, would you have reacted the same way?
  - pmjordan 17y ago
    Actually, that's pretty much accurate. I initially didn't even realise this was written by ESR and just assumed the author was very inexperienced. ESR however should know better, though to be honest I don't even know if the guy still writes code. I hate to stoop to ad hominem attacks, but re-reading it knowing that it's him I get the impression this was a petty reaction to some feud with a GCC dev. In any case I'd love to know who the hell is upvoting this "story".
    - kelnos 17y ago
      Yes, when I started reading, my first thought was, "wow, sounds like someone pretty inexperienced." After I noticed it was written by ESR, that changed to, "wow, sounds like someone pretty arrogant." The fact of the matter is that a compiler like gcc is used by thousands (tens of thousands? more?) of people almost daily. Usually you have to be doing some pretty crazy stuff to find a bug in it. Bugs that go away when you turn off optimizations are usually either race-condition or memory-access related.
      - pmjordan 17y ago
        Or uninitialised local variables, which are affected by the difference in register allocation, but really you should be enabling the corresponding warning.
argv_empty 17y ago
As an example... I once wrote some MPI code for class. It ran properly at -O0, though the compiler warned of a variable that was declared but never used. Compiling at a level other than -O0 or removing that variable declaration from the source code caused the program to segfault immediately. It turned out to be a memory error somewhere else in the program (I forget exactly what, but it was over my misunderstanding of some part of the message passing calls).
varjag 17y ago
While it's not an everyday occurrence, it happens a lot more often than you would believe. In Linux kernel, there is actually official list of compiler versions that produce faulty code.
cdavid 17y ago
It depends on the context as well. It is much more likely to find a bug in gfortran for solaris sparc than gcc on x86 linux, for example. The only time I keep the compiler bug in mind is when working with gcc 4.x compiler on windows. I don't have the experience of ESR, but I find the advice a bit dangerous if taken as a general one. Especially, the idea that a heisenbug is often caused by a compiler: most likely, the heisenbug is not a heisenbug at all, but just less visible depending on the compiler flags. That was the case for the vast majority of "heisenbugs" I have encountered in C.
jmaynard 17y ago
FWIW, I do tend to think the problem's in my code until proven otherwise. That's why I spent a week tearing my hair out trying to find the problem. And, for the naysayers, Hercules is built with -W -Wall.

Vivtek 17y ago

I found an optimizer bug once. I can't remember the exact circumstances, but it had to do with some fancy inline incrementing I was doing. The very concept that I'd found a bug in somebody else's code floored me. I was young.

nkurz 17y ago

My experience goes in a different direction: when you see different behavior when compiled with and without optimization, suspect a memory allocation error or overrun. While compiler optimization bugs do exist, I've more often found that the problem is real. If you are working with your own code and care if it works: 1) Turn on all compiler warnings 2) Change your code so it compiles clean 3) Run under Valgrind (or equivalent). 4) Address all reported errors, specifically whitelisting them if necessary. 5) If you find a bug, don't stop until you've found the cause. You're done when you understand what caused the bug to appear, not when the symptoms go away. 6) Use open source tools, since otherwise you'll be tempted to blame some unspecified 'bug in the compiler'. (not that ESR would be using any other) 7) If it is a compiler bug, report it, along with the smallest test case you can generate.

wheels 17y ago
This is definitely along the right path. One proviso that I'd note: Most of the time in my own debugging when I've run into something that goes away at a different level of optimization it's uninitialized variables / memory. Valgrind is the shizzle.

tptacek 17y ago

-O3 isn't "riskier". It's just harder to debug under.

callahad 17y ago
I know little about C compilers, but if -O3 resulted in segfaults while other settings did not, how is it not riskier? Are the different optimization levels independent such that this bug could have appeared anywhere, but just happened to be in one of the strategies used by -O3?
- tptacek 17y ago
  Because, like a number of other people have pointed out upthread, it can make the impact of memory corruption problems more immediate.
- wingo 17y ago
  There is also the possibility that if your program has an aliasing bug, the bug may only cause failure at -O2 but not at -O0 or -O1. See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35653 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35653, for example.
regehr 17y ago
-O3 is indeed riskier. All experienced embedded systems developers know this: embedded compilers tend to be much buggier than compilers for desktop platforms. But desktop compilers are buggy too. Over the last couple years my group has reported 190 bugs to compiler development teams. A lot of these bugs turn up only at higher optimization levels. If you search on my email address "regehr@cs.utah.edu" as bug reporter in either GCC or LLVM's bugzilla, you can see plenty of examples.
- tptacek 17y ago
  I defer to the gentleman with the University research project dedicated to finding compiler bugs. :)

liuliu 17y ago

Except multi-thread programming, I didn't find any compiler's optimizer related bugs. The truth is, most heisenbugs I found are somewhat related to memory access. It is just too risky to assume it is a compiler bug. I always think in the other way: unless you can prove (by generating assembly code and a possible scenario), the bug is in your code.

jgrahamc 17y ago

It's seems strange me to instantly suspect that your compiler's optimizer is at fault. Which is more likely: you've found a bug in a compiler used the world over, or you've screwed up memory access? Since C makes it easy to overrun memory, it's pretty easy to make horrible mistakes and have those have seemingly random consequences. The fact that the bug changes when you change optimizer settings, add trace statements, or add debug code would make me suspect memory corruption first. In fact, I think it's a good assumption to always begin suspecting your own code.

ja27 17y ago

It's not quite the same as the 'heisenbug' but I've seen a couple of cases over the years where a mysterious problem was resolved by moving to the latest update of the C/C++ runtime. It's weird how many enterprises are fine with running years behind on maintenance on that.

sreque 17y ago

I have an example of a bug I found that looked like an optimization bug but was really a user bug. Someone had the bright idea of sprintf-ing to a string and using the string itself as one of the format arguments to the sprintf call. When compiled with gcc the code would still run fine, but when compiling with -O1 the string would end up garbled. The problem (and advantage, performance-wise) of C is that most of the time you do something wrong, the behavior is undefined, whereas most higher-level languages will spend the CPU cycles to protect you from yourself. Another example I can't remember the details of, but it was related to the fact that gcc adds code to zero-initialize your stack on first access unless optimizations are turned on. Code that checked for null pointers worked fine until optimizations were turned on, at which point it was discovered that a variable was being used uninitialized.

losethos 17y ago

Ba ha--You guys have never worked with your own company's compilers. At Ticketmaster my boss wrote our PASCAL compiler and I would find bugs. I wrote my C+ compiler for LoseThos and I find bugs. http://www.losethos.com http://www.losethos.com Generally, you should suspect your own code before the compiler, but it depends on how much of a work-out the compiler has been put through. Even with me, though, I sometimes doubt my own compiler wrongly.

WalterBright 17y ago

Optimizer and code gen problems are pretty hard for users to diagnose correctly, so most compiler vendors put a high priority on fixing them.

jmaynard 17y ago

I didn't expect a kind of Spanish inquisition... The terminally curious may download a file containing the assembler output, and the C source, of the offending file from http://www.hercules-390.org/esamebug.zip http://www.hercules-390.org/esamebug.zip . This corresponds to revision 5627 of the Hercules emulator as found in the Subversion repository at svn://svn.hercules-390.org/hercules/trunk . The emulator itself is at http://www.hercules-390.org http://www.hercules-390.org . The routine is in the generated assembler as z900_load_multiple_long.

jgrahamc 17y ago
Can you also give us a test case?
- jmaynard 17y ago
  I might be able to build one to be executed under Hercules...let me work on that. My current test case is under NDA.
  - jmaynard 17y ago
    Done. You can get it at http://www.hercules-390.org/lmg-test.zip http://www.hercules-390.org/lmg-test.zip .
    - jgrahamc 17y ago
      Cool. Any particular things I need to know? e.g. which platform should I try this on? Also, have you run valgrind against the test?
      - jmaynard 17y ago
        The test has only been shown to fail on Mac OS X Snow Leopard with gcc 4.2.1. I haven't been able to make it fail on any other platform. Because of the code involved, I suspect it won't fail at all on anything but 32-bit Intel. I've never run valgrind...it'll be interesting to see just what it does to Hercules execution speed. mudflap, too. Getting that built into the code might get even more interesting.

ivan_w 17y ago

I found the bug (I think).. It's not "really" an optimizer bug per-se (although it is CLEARLY triggered by the optimizer). Always treat __asm with caution ! --Ivan