6 ms·

Question for any low-level optimizing compiler engineers here: I obviously realize these are all important, but in your judgment, how much of making an error-fr

Question for any low-level optimizing compiler engineers here: I obviously realize these are all important, but in your judgment, how much of making an error-free compiler would you say is about having a comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews, vs. something else? Put another way, if you were to lose one of these, which ones do you think would have the most/least negative impact (or be the easiest/hardest to make up for with other things) in terms of the correctness of the final product?

neeeeees 6y ago
The test suite is ultra important. Even in the unlikely case that you have an engineer who thoroughly understands the machine and language specs, you have a ton of existing, useful, programs that rely on under-defined behaviour in one or both of them.
- mehrdadn 6y ago
  Ah, I might have to tease out my question here. By correctness I'm only referring to the implementation being true to the language specification, not to "not breaking existing programs". So if a program relies on undefined behavior and then gets broken in the next version of the compiler because of that behavior, I don't consider that a correctness problem in the compiler for the purposes of this question. (Which is not to suggest keeping it working isn't a worthwhile goal. I'm saying that's not the aspect of it that I'm asking about.)
  - pjmlp 6y ago
    The problem is that many don't learn C and C++ properly, they have read some language introduction book and assume "how my compiler does it" is the right way and probably never touched a copy of ISO. So plenty of programs rely on UB even without realizing it.
    - fit2rule 6y ago
      More to the point, anyone doing compiler validation work would a) always have a full test suite as their first line of attack, b) always have a well understood developer pipeline in place, to ensure a consistent understanding - coding rules, code review processes, etc. and c) always looks at what the compiler is actually doing, compared to what they think its doing - i.e. is able to navigate code -> assembly and all the stages in between, with competence. Anything less is asking for trouble.
      - joosters 6y ago
        A ‘full’ test suite? I’m not sure that one of those has ever existed for any large program, let alone one under active development. We have to work in the real world here!
        fit2rule 6y ago
        Yes, a full test suite. 100% code coverage is a thing, even in compiler validation. Also, every test that was ever written for a compiler is still out there, being run, somewhere. And, for the record, the real world is pretty big.
        andrewaylett 6y ago
        But 100% code coverage isn't necessarily a useful thing in this context, as different code (and different options) mean different interactions between passes. And you're never going to cover all the different paths through the compiler. Back when I worked on a commercial compiler, we had a smoke test which we ran before committing. It would take ~30 minutes to run. We had a longer, roughly eight hour, set of tests which we ran daily. And we had machines running tests 24/7, which managed to clock up roughly 20 million distinct test cases (combinations of code and options) over the course of a year. Every single compiler bug we'd ever seen was present (in a reduced form) in the conformance tests we'd run before release. That took about a week.
        6y ago
  - perlgeek 6y ago
    Then the test suite is still hugely important -- you just have to design it to reflect what you consider "true to the language specification". Or phrased differently, the test suite is (or should be) the machine-readable language specification.
  - barrkel 6y ago
    That is only theoretical correctness, not useful correctness.
tannhaeuser 6y ago
The OpenBSD project used to verify gcc (back when it was at 4.2 or so) as compiler for their O/S. Don't know if they still do; I'd imagine it's a lot of effort, and both clang and gcc have churned out yearly releases with ever-growing complexity since. C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, and one for which writing a compiler is relatively straightforward and takes no longer than a year. This went out of the window with clang, and with gcc (and glibc!) being based on C++. Though of course optimizing out-of-order execution on modern CPUs is much more complex than your olde microcontroller-like CPU.
- jabl 6y ago
  > C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, That might have been K&R's original intention, but that went out the window pretty early on when optimizing compilers arrived on the scene. And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule).
  - gwd 6y ago
    > And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule). The ironic thing about that is that when they wrote C89, they said they were trying to standardize existing practice. I don't think they had any idea that they were effectively declaring 90% of all programs buggy.
    - jfkebwjsbx 6y ago
      And then retroactively declare that code broken and not conforming. Good times!
      - jabl 6y ago
        In defense of whoever was involved in the C89 process, I think they had an impossible task. At the same time they wanted to standardize the "portable macro-assembler" as well as allowing optimizations. With such constraints they could not but fail. With hindsight, maybe K&R should have consulted with PL experts and researchers and designed a "proper" language with a better emphasis on soundness and safety. I'm not saying they could have invented something like Rust back in the 1970'ies, but even then the state of the art was far ahead of K&R C.
jfoutz 6y ago
I'm not quite the class of people you're asking, I worked on an interpreter for an old language for a long time. Tests are fantastic for defined behavior. but running actual real world gigantic battle tested programs is where I found bugs. It _seems_ like you can just define the behavior. In my experience, the interpreter would mostly do what I wanted, unless like 4 complicated factors were in play. Often, it's so confusing, the user of your language is just trying to make something work. They're under a deadline, they find a way, and they make it work. They're not morons, hell, you have to be pretty sophisticated to find that weird edge to exploit. I was super new, but I thought of a lot of my coworkers as surgeons. They'd see the problem, and find the smallest possible change to fix a bug. They were very careful. I dunno. it's super hard. I made some optimizations where I had a choice, I could break a working program (but relying on undefined behavior) in one way or another. Seemed like with those big projects, the optimization is totally worth it. But you have to pick. If you choose the semantics to mean 'a' then X breaks, if you choose 'b' then Y breaks. Our users had been around the block a few times. They were sympathetic, and we held a pretty firm line on undefined behavior. I dunno. I think rust probably handles this the best, recompiling and retesting against every crate ever. But here's the thing, if you're relying on some weird edge case, the test probably is as well. So you don't actually detect the change in behavior. I think it's a hard problem, and there's no silver bullet. Write tests. Have careful engineers. Run big programs. In spite of all that, you're going to have to go to your users hat in hand occasionally, because when you build big systems there are lots of subtle edge cases. Shit's hard man.
g_airborne 6y ago
Somewhat unrelated but I read somewhere that the Rust team test their releases by compiling the entirety of crates.io and all Rust GitHub repositories to find regressions. The tool is called Crater. Source: https://www.pietroalbini.org/blog/shipping-a-compiler-every-six-weeks/ https://www.pietroalbini.org/blog/shipping-a-compiler-every-...
- grenoire 6y ago
  No longer the entirety but still a sizeable chunk of it; it helps with regression detection for them. World's biggest test suite?
  - jfkebwjsbx 6y ago
    It is very common for compilers to be tested using client code. It is a practice that goes back decades. Nowadays with so many open source projects and so much distributed computer power, it is even easier.
    - pornel 6y ago
      What makes it easy and powerful for Rust is that ~all Rust projects use Cargo as the build system and test runner, so Crater can really test every Rust project in existence, not just code samples hand-picked into compiler's test suite.
      - jfkebwjsbx 6y ago
        Only open source projects, which will not be the majority if Rust ends up taking up speed.
- twic 6y ago
  I was reading the docs of some library the other day, and they had a list of projects using that library. It was an impressive list: long, and with some serious projects on there. Then i saw that they try building those projects against their library as part of their test pipeline. If you want to add your project to the list, you can submit a pull request. No wonder the list is so substantial - it gets you free testing! Highly ingenious!
mehrdada 6y ago
Not a compiler author, but have some experience with finding bugs in compilers. If I had to venture a guess, I'd pick the testsuite (and other tools like fuzzing and mass user base), since the complexity is quite high. In our experience with the EMI project (https://web.cs.ucdavis.edu/~su/publications/emi.pdf https://web.cs.ucdavis.edu/~su/publications/emi.pdf), some of the miscompilations were caused by one pass of the compiler emitting code that was considered to have contained undefined behavior by the next pass (see Figure 1(b)). I'd say the code reviewer will catch issues within a single pass, but the interaction between them are less likely to be caught by a human reviewer as the complexity grows.
- mehrdadn 6y ago
  Good thoughts, thanks!
  - saagarjha 6y ago
    Completely off topic but reading this thread (without glasses in preparation to go to bed) was a bit confusing until I realized that your usernames differed by a single letter…
    - mehrdadn 6y ago
      Haha, glad you cleared it up so that you can sleep easily now :-)
fluffything 6y ago
They all have a critical impact. If you look at Rust, you cannot commit to master: - without the resulting master merge passing the whole test suite, which would probably take a day or more to run locally, and - without a review of someone that knows the part of the code you modified well, or somebody they delegate to, and often, of a group of multiple people that know that part of the code well. These people verify that the code is correct, commented, tested, appropriate, etc. Often, a design team in charge of that part of the code that makes sure that the change goes in a direction that aligns with the project strategy/goals (i.e. that this is a change we want to make). Even the best of the best software developers: - don't always test that their code compiles before committing: for Rust, they really can't to, they'd need to cross-compile the compiler dozens of times, run these compilers under qemu on different hardware, and verify that they work - too much work for any single human - don't always test that their code passes the test suite: the test suite is _huge_. Its impossible for anybody to test anything locally, takes too much time. - don't always benchmark the compiler after a change on reasonable applications, takes too much time. - etc. point being, you cannot trust the best of the best, much less anyone else. As a Rust compiler dev, the first person that you should not trust is _you_. The whole point of the process is identifying all possible sources of errors, and making them impossible, or at worst, extremely unlikely to happen. Most of these errors are only quite unlikely to happen, e.g., because all the automated tooling that exists to prevent them is also written by humans that make mistakes. But every time a new source of error is identified, there is at least a discussion about how to make it impossible to happen in the future. Having a test suite, having reviewers, are just two things you have to do to avoid a large set of errors (see a comment below about how each release of Rust is required to succesfully compile all existing public Rust source code and run all their tests succesfully). They are not barely enough. And even if your process makes errors extremely unlikely, Rust and LLVM have hundreds of PRs on flight and hundreds of developers working on the source code regularly. Throw enough developers at a project, and unlikely events become a daily thing.
acqq 6y ago
> comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews, vs. something else In practice, you need all, for various reasons. > in terms of the correctness of the final product What is there "correctness"? Ah, I see in your later post: > I'm only referring to the implementation being true to the language specification The answer is: even checking for that is not something which can put the humans out of the loop. But humans alone (as in "extremely thorough code reviews" or "very careful software engineers") are provably not enough as the "space" that has to be tested is too big to be useful without "a comprehensive test suite." Still I'm not aware that a complete "comprehensive test suite" which would be "enough" for any non-trivial language can exist. In my experience, non-trivial goals are simply bigger than any "simple" or "single" "solution." So in that sense, any project eventually fails due to the human factor. It's the humans that will use anything else as the tools to achieve the goal. It's the quality of humans that are in charge that is the precondition for everything else. So the answer is always: prioritize for having good people, anything else will be taken care of by them: they will maintain the tests, be careful, do the reviews etc. Don't expect you can "save" on something.
chandlerc1024 6y ago
Test suite, without a doubt. Asking humans to be careful at scale (whether authoring or reviewing) just won't work. Keep in mind that you need loooooots of test suites, not just one.
hedora 6y ago
> having a comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews I’ll be a contrarian, and say the careful software engineers are the most important. They’ll stop feature work to recreate the test suite. On the other hand, nothing can save a good test suite from being selectively disabled or regressed by sloppy engineers. Similarly, having a process that dictates careful code reviews just slows everyone down. The careful engineers would have done the code reviews properly without the policy. The sloppy ones will spend more time to produce comparably bad (or even worse) code reviews.
lanza 6y ago
llvm has a very thorough test suite and it's main test suite is exactly for this purpose. The error witnessed here by sqlite will be turned into a test case that takes the C code and compiles it and hand checks whether the output was miscompiled or not. Here's a test from 2007 that tests a similar error in the instruction selector: https://github.com/llvm-project/llvm/blob/master/test/CodeGen/X86/2007-02-23-DAGCombine-Miscompile.ll https://github.com/llvm-project/llvm/blob/master/test/CodeGe... Evidently the error that caused this test to be rewritten reordered the `ret` instruction before the `mov $1, $eax` instruction that sets the return value. This tests assures that the bug will never happen again.

neeeeees 6y ago

The test suite is ultra important. Even in the unlikely case that you have an engineer who thoroughly understands the machine and language specs, you have a ton of existing, useful, programs that rely on under-defined behaviour in one or both of them.

mehrdadn 6y ago
Ah, I might have to tease out my question here. By correctness I'm only referring to the implementation being true to the language specification, not to "not breaking existing programs". So if a program relies on undefined behavior and then gets broken in the next version of the compiler because of that behavior, I don't consider that a correctness problem in the compiler for the purposes of this question. (Which is not to suggest keeping it working isn't a worthwhile goal. I'm saying that's not the aspect of it that I'm asking about.)
- pjmlp 6y ago
  The problem is that many don't learn C and C++ properly, they have read some language introduction book and assume "how my compiler does it" is the right way and probably never touched a copy of ISO. So plenty of programs rely on UB even without realizing it.
  - fit2rule 6y ago
    More to the point, anyone doing compiler validation work would a) always have a full test suite as their first line of attack, b) always have a well understood developer pipeline in place, to ensure a consistent understanding - coding rules, code review processes, etc. and c) always looks at what the compiler is actually doing, compared to what they think its doing - i.e. is able to navigate code -> assembly and all the stages in between, with competence. Anything less is asking for trouble.
    - joosters 6y ago
      A ‘full’ test suite? I’m not sure that one of those has ever existed for any large program, let alone one under active development. We have to work in the real world here!
      - fit2rule 6y ago
        Yes, a full test suite. 100% code coverage is a thing, even in compiler validation. Also, every test that was ever written for a compiler is still out there, being run, somewhere. And, for the record, the real world is pretty big.
        andrewaylett 6y ago
        But 100% code coverage isn't necessarily a useful thing in this context, as different code (and different options) mean different interactions between passes. And you're never going to cover all the different paths through the compiler. Back when I worked on a commercial compiler, we had a smoke test which we ran before committing. It would take ~30 minutes to run. We had a longer, roughly eight hour, set of tests which we ran daily. And we had machines running tests 24/7, which managed to clock up roughly 20 million distinct test cases (combinations of code and options) over the course of a year. Every single compiler bug we'd ever seen was present (in a reduced form) in the conformance tests we'd run before release. That took about a week.
        6y ago
- perlgeek 6y ago
  Then the test suite is still hugely important -- you just have to design it to reflect what you consider "true to the language specification". Or phrased differently, the test suite is (or should be) the machine-readable language specification.
- barrkel 6y ago
  That is only theoretical correctness, not useful correctness.

tannhaeuser 6y ago

The OpenBSD project used to verify gcc (back when it was at 4.2 or so) as compiler for their O/S. Don't know if they still do; I'd imagine it's a lot of effort, and both clang and gcc have churned out yearly releases with ever-growing complexity since. C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, and one for which writing a compiler is relatively straightforward and takes no longer than a year. This went out of the window with clang, and with gcc (and glibc!) being based on C++. Though of course optimizing out-of-order execution on modern CPUs is much more complex than your olde microcontroller-like CPU.

jabl 6y ago
> C was once supposed to be a simple language closer to a portable macro assembler than a high-level language, That might have been K&R's original intention, but that went out the window pretty early on when optimizing compilers arrived on the scene. And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule).
- gwd 6y ago
  > And eventually when the ANSI spec was written, it was explicitly written to allow all kinds of optimizations (the "as-if" rule). The ironic thing about that is that when they wrote C89, they said they were trying to standardize existing practice. I don't think they had any idea that they were effectively declaring 90% of all programs buggy.
  - jfkebwjsbx 6y ago
    And then retroactively declare that code broken and not conforming. Good times!
    - jabl 6y ago
      In defense of whoever was involved in the C89 process, I think they had an impossible task. At the same time they wanted to standardize the "portable macro-assembler" as well as allowing optimizations. With such constraints they could not but fail. With hindsight, maybe K&R should have consulted with PL experts and researchers and designed a "proper" language with a better emphasis on soundness and safety. I'm not saying they could have invented something like Rust back in the 1970'ies, but even then the state of the art was far ahead of K&R C.

jfoutz 6y ago

I'm not quite the class of people you're asking, I worked on an interpreter for an old language for a long time. Tests are fantastic for defined behavior. but running actual real world gigantic battle tested programs is where I found bugs. It _seems_ like you can just define the behavior. In my experience, the interpreter would mostly do what I wanted, unless like 4 complicated factors were in play. Often, it's so confusing, the user of your language is just trying to make something work. They're under a deadline, they find a way, and they make it work. They're not morons, hell, you have to be pretty sophisticated to find that weird edge to exploit. I was super new, but I thought of a lot of my coworkers as surgeons. They'd see the problem, and find the smallest possible change to fix a bug. They were very careful. I dunno. it's super hard. I made some optimizations where I had a choice, I could break a working program (but relying on undefined behavior) in one way or another. Seemed like with those big projects, the optimization is totally worth it. But you have to pick. If you choose the semantics to mean 'a' then X breaks, if you choose 'b' then Y breaks. Our users had been around the block a few times. They were sympathetic, and we held a pretty firm line on undefined behavior. I dunno. I think rust probably handles this the best, recompiling and retesting against every crate ever. But here's the thing, if you're relying on some weird edge case, the test probably is as well. So you don't actually detect the change in behavior. I think it's a hard problem, and there's no silver bullet. Write tests. Have careful engineers. Run big programs. In spite of all that, you're going to have to go to your users hat in hand occasionally, because when you build big systems there are lots of subtle edge cases. Shit's hard man.

g_airborne 6y ago

Somewhat unrelated but I read somewhere that the Rust team test their releases by compiling the entirety of crates.io and all Rust GitHub repositories to find regressions. The tool is called Crater. Source: https://www.pietroalbini.org/blog/shipping-a-compiler-every-six-weeks/ https://www.pietroalbini.org/blog/shipping-a-compiler-every-...

grenoire 6y ago
No longer the entirety but still a sizeable chunk of it; it helps with regression detection for them. World's biggest test suite?
- jfkebwjsbx 6y ago
  It is very common for compilers to be tested using client code. It is a practice that goes back decades. Nowadays with so many open source projects and so much distributed computer power, it is even easier.
  - pornel 6y ago
    What makes it easy and powerful for Rust is that ~all Rust projects use Cargo as the build system and test runner, so Crater can really test every Rust project in existence, not just code samples hand-picked into compiler's test suite.
    - jfkebwjsbx 6y ago
      Only open source projects, which will not be the majority if Rust ends up taking up speed.
twic 6y ago
I was reading the docs of some library the other day, and they had a list of projects using that library. It was an impressive list: long, and with some serious projects on there. Then i saw that they try building those projects against their library as part of their test pipeline. If you want to add your project to the list, you can submit a pull request. No wonder the list is so substantial - it gets you free testing! Highly ingenious!

mehrdada 6y ago

Not a compiler author, but have some experience with finding bugs in compilers. If I had to venture a guess, I'd pick the testsuite (and other tools like fuzzing and mass user base), since the complexity is quite high. In our experience with the EMI project (https://web.cs.ucdavis.edu/~su/publications/emi.pdf https://web.cs.ucdavis.edu/~su/publications/emi.pdf), some of the miscompilations were caused by one pass of the compiler emitting code that was considered to have contained undefined behavior by the next pass (see Figure 1(b)). I'd say the code reviewer will catch issues within a single pass, but the interaction between them are less likely to be caught by a human reviewer as the complexity grows.

mehrdadn 6y ago
Good thoughts, thanks!
- saagarjha 6y ago
  Completely off topic but reading this thread (without glasses in preparation to go to bed) was a bit confusing until I realized that your usernames differed by a single letter…
  - mehrdadn 6y ago
    Haha, glad you cleared it up so that you can sleep easily now :-)

fluffything 6y ago

They all have a critical impact. If you look at Rust, you cannot commit to master: - without the resulting master merge passing the whole test suite, which would probably take a day or more to run locally, and - without a review of someone that knows the part of the code you modified well, or somebody they delegate to, and often, of a group of multiple people that know that part of the code well. These people verify that the code is correct, commented, tested, appropriate, etc. Often, a design team in charge of that part of the code that makes sure that the change goes in a direction that aligns with the project strategy/goals (i.e. that this is a change we want to make). Even the best of the best software developers: - don't always test that their code compiles before committing: for Rust, they really can't to, they'd need to cross-compile the compiler dozens of times, run these compilers under qemu on different hardware, and verify that they work - too much work for any single human - don't always test that their code passes the test suite: the test suite is _huge_. Its impossible for anybody to test anything locally, takes too much time. - don't always benchmark the compiler after a change on reasonable applications, takes too much time. - etc. point being, you cannot trust the best of the best, much less anyone else. As a Rust compiler dev, the first person that you should not trust is _you_. The whole point of the process is identifying all possible sources of errors, and making them impossible, or at worst, extremely unlikely to happen. Most of these errors are only quite unlikely to happen, e.g., because all the automated tooling that exists to prevent them is also written by humans that make mistakes. But every time a new source of error is identified, there is at least a discussion about how to make it impossible to happen in the future. Having a test suite, having reviewers, are just two things you have to do to avoid a large set of errors (see a comment below about how each release of Rust is required to succesfully compile all existing public Rust source code and run all their tests succesfully). They are not barely enough. And even if your process makes errors extremely unlikely, Rust and LLVM have hundreds of PRs on flight and hundreds of developers working on the source code regularly. Throw enough developers at a project, and unlikely events become a daily thing.

acqq 6y ago

> comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews, vs. something else In practice, you need all, for various reasons. > in terms of the correctness of the final product What is there "correctness"? Ah, I see in your later post: > I'm only referring to the implementation being true to the language specification The answer is: even checking for that is not something which can put the humans out of the loop. But humans alone (as in "extremely thorough code reviews" or "very careful software engineers") are provably not enough as the "space" that has to be tested is too big to be useful without "a comprehensive test suite." Still I'm not aware that a complete "comprehensive test suite" which would be "enough" for any non-trivial language can exist. In my experience, non-trivial goals are simply bigger than any "simple" or "single" "solution." So in that sense, any project eventually fails due to the human factor. It's the humans that will use anything else as the tools to achieve the goal. It's the quality of humans that are in charge that is the precondition for everything else. So the answer is always: prioritize for having good people, anything else will be taken care of by them: they will maintain the tests, be careful, do the reviews etc. Don't expect you can "save" on something.

chandlerc1024 6y ago

Test suite, without a doubt. Asking humans to be careful at scale (whether authoring or reviewing) just won't work. Keep in mind that you need loooooots of test suites, not just one.

hedora 6y ago

> having a comprehensive test suite, vs. having very careful software engineers, vs. having extremely thorough code reviews I’ll be a contrarian, and say the careful software engineers are the most important. They’ll stop feature work to recreate the test suite. On the other hand, nothing can save a good test suite from being selectively disabled or regressed by sloppy engineers. Similarly, having a process that dictates careful code reviews just slows everyone down. The careful engineers would have done the code reviews properly without the policy. The sloppy ones will spend more time to produce comparably bad (or even worse) code reviews.

lanza 6y ago

llvm has a very thorough test suite and it's main test suite is exactly for this purpose. The error witnessed here by sqlite will be turned into a test case that takes the C code and compiles it and hand checks whether the output was miscompiled or not. Here's a test from 2007 that tests a similar error in the instruction selector: https://github.com/llvm-project/llvm/blob/master/test/CodeGen/X86/2007-02-23-DAGCombine-Miscompile.ll https://github.com/llvm-project/llvm/blob/master/test/CodeGe... Evidently the error that caused this test to be rewritten reordered the `ret` instruction before the `mov $1, $eax` instruction that sets the return value. This tests assures that the bug will never happen again.