An optimizing, ahead-of-time compiler is usually structured as: A frontend that converts source code into an intermediate representation (IR). A target-independent optimization pipeline: a sequence of passes that successively rewrite the IR to eliminate inefficiencies and forms that cannot be readily translated into machine code. Sometimes called the “middle end.” A target-dependent backend that generates […]
Category Archives: Compilers
How Clang Compiles a Function
I’ve been planning on writing a post about how LLVM optimizes a function, but it seems necessary to first write about how Clang translates C or C++ into LLVM. This is going to be fairly high-level: rather than looking at Clang’s internals, I’m going to focus on how Clang’s output relates to its input we’re […]
Some Goals for High-impact Verified Compiler Research
I believe that translation validation, a branch of formal methods, is just about ready for widespread use. Translation validation means proving that a particular execution of a compiler did the right thing, as opposed to proving once and for all that every execution of a compiler will do the right thing. These are very different. […]
Undefined Behavior in 2017
This post is jointly authored by Pascal Cuoq and John Regehr. Recently we’ve heard a few people imply that problems stemming from undefined behaviors (UB) in C and C++ are largely solved due to ubiquitous availability of dynamic checking tools such as ASan, UBSan, MSan, and TSan. We are here to state the obvious — […]
Pointer Overflow Checking is in LLVM
Production-grade memory safety for legacy C and C++ code has proven to be a frustratingly elusive goal: plenty of research solutions exist but none of them appear to be deployable as-is. So instead, we have a patchwork of partial solutions such as CFI, ASLR, stack canaries, hardened allocators, and NX. Today’s quick post is about […]
Compiler Optimizations are Awesome
This piece, which I hadn’t gotten around to writing until now since I thought it was all pretty obvious, explains why Daniel J. Bernstein’s talk, The death of optimizing compilers (audio) is wrong, and in fact compiler optimizations are extremely wonderful and aren’t going anywhere. First, the thesis of the talk is that almost all […]
Translation Validation of Bounded Exhaustive Test Cases
This piece is jointly authored by Nuno Lopes and John Regehr. Compilers should be correct, but it is not straightforward to formally verify a production-quality compiler implementation. It is just too difficult to recover the high-level algorithms by looking at an enormous mess of arithmetic, loops, and memory side effects. One solution is to write […]
Taming Undefined Behavior in LLVM
Earlier I wrote that Undefined Behavior != Unsafe Programming, a piece intended to convince you that there’s nothing inherently wrong with undefined behavior as long as it isn’t in developer-facing parts of the system. Today I want to talk about a new paper about undefined behavior in LLVM that’s going to be presented in June […]
Do Expressive Programming Languages Always Have Undefined Behavior?
In the Hacker News comments on one of my previous posts about undefined behavior, someone said this: AFAIK Gödel’s incompleteness theorems imply that _any_ language will have at least some undefined behaviour. Let’s take a quick look at this statement, keeping in mind that incompleteness and undecidability can be remarkably tricky topics. Some years ago […]
Undefined Behavior != Unsafe Programming
Undefined behavior (UB) in C and C++ is a clear and present danger to developers, especially when they are writing code that will execute near a trust boundary. A less well-known kind of undefined behavior exists in the intermediate representation (IR) for most optimizing, ahead-of-time compilers. For example, LLVM IR has undef and poison in […]