Chris Lattner: Revolutionizing the C++ World

Maybe almost all C++ developers know the LLVM infrastructure and the Clang compiler. But how many know that Chris Lattner is their creator, and that he was only 25 years old at the time? How is that possible? I remember that when I was 25, I spent my time trying to understand the C++ basics :)

The story begins with a thesis

In late 2000, Lattner joined the University of Illinois at Urbana-Champaign as a research assistant and M.Sc. student. While working with Vikram Adve, he designed and began implementing LLVM, an innovative infrastructure for optimizing compilers, which was the subject of his 2002 M.Sc. thesis. He completed his Ph.D. in 2005, researching new techniques for optimizing pointer-intensive programs and adding them to LLVM.

Here’s the motivation behind the LLVM design, from his thesis abstract:

Modern programming languages and software engineering principles are causing increasing problems for compiler systems. Traditional approaches, which use a simple compile-link-execute model, are unable to provide adequate application performance under the demands of the new conditions. Traditional approaches to interprocedural and profile-driven compilation can provide the application performance needed, but require infeasible amounts of compilation time to build the application.This thesis presents LLVM, a design and implementation of a compiler infrastructure which supports a unique multi-stage optimization system. This system is designed to support extensive interprocedural and profile-driven optimizations, while being efficient enough for use in commercial compiler systems.The LLVM virtual instruction set is the glue that holds the system together. It is a low-level representation, but with high-level type information. This provides the benefits of a low-level representation (compact representation, wide variety of available transformations, etc.) as well as providing high-level information to support aggressive interprocedural optimizations at link- and post-link time. In particular, this system is designed to support optimization in the field, both at run-time and during otherwise unused idle time on the machine.

To sum up, the idea behind LLVM is to use the LLVM Intermediate Representation (IR); it’s like bytecode for Java or IL for .NET.

LLVM IR is designed to host mid-level analyses and transformations that you find in the optimizer section of a compiler. It was designed with many specific goals in mind, including supporting lightweight runtime optimizations, cross-function/interprocedural optimizations, whole program analysis, and aggressive restructuring transformations, etc. The most important aspect of it, though, is that it is itself defined as a first class language with well-defined semantics.

Let’s consider a relatively straightforward function that takes three integer parameters and returns an arithmetic combination of them.

int mul_add(int x, int y, int z) {
  return x * y + z;
}

The LLVM IR for this function will look like:

define i32 @mul_add(i32 %x, i32 %y, i32 %z) {
entry:
  %tmp = mul i32 %x, %y
  %tmp2 = add i32 %tmp, %z
  ret i32 %tmp2
}

Back to the goal of this thesis, which focuses on optimization. To explain this compiler phase, I can’t say it better than Chris Lattner, the father of LLVM, in this post:

“To give some intuition for how optimizations work, it is useful to walk through some examples. There are lots of different kinds of compiler optimizations, so it is hard to provide a recipe for how to solve an arbitrary problem. That said, most optimizations follow a simple three-part structure:

Look for a pattern to be transformed.
Verify that the transformation is safe/correct for the matched instance.
Do the transformation, updating the code.

The optimizer reads LLVM IR in, chews on it a bit, then emits LLVM IR, which hopefully will execute faster. In LLVM (as in many other compilers) the optimizer is organized as a pipeline of distinct optimization passes each of which is run on the input and has a chance to do something. Common examples of passes are the inliner (which substitutes the body of a function into call sites), expression reassociation, loop invariant code motion, etc. Depending on the optimization level, different passes are run: for example at -O0 (no optimization) the Clang compiler runs no passes, at -O3 it runs a series of 67 passes in its optimizer (as of LLVM 2.8).

LLVM and Clang as infrastructure to build tools

A major design concept for Clang is its use of a library-based architecture. In this design, various parts of the front-end can be cleanly divided into separate libraries which can then be mixed up for different needs and uses. In addition, the library-based approach encourages good interfaces and makes it easier for new developers to get involved (because they only need to understand small pieces of the big picture).

The design of LLVM/Clang makes it an infrastructure for building tools, thanks to its library-based architecture, which makes the reuse and integration of new features more flexible and easier to integrate into other projects.

Many tools are based on LLVM and Clang; we can name clang-tidy, clang-query, CppDepend and more.

Clang always up to date with the new standards

Clang is always compliant with any new standard; furthermore, it always provides experimental support for upcoming new features. The current version has experimental support for some proposed features of the C++ standard following C++17, provisionally named C++2a. Note that support for these features may change or be removed without notice, as the draft C++2a standard evolves.

You can use Clang in C++2a mode with the -std=c++2a option.

Language Feature	C++2a Proposal	Available in Clang?
Default member initializers for bit-fields	P0683R1	Clang 6
`const&`-qualified pointers to members	P0704R1	Clang 6
Allow lambda-capture `[=, this]`	P0409R2	Clang 6
`__VA_OPT__` for preprocessor comma elision	P0306R4	Clang 6
Designated initializers	P0329R4	Partial (extension)
Initializer list constructors in class template argument deduction	P0702R1	Clang 6
Access checking on specializations	P0692R1	Partial

Clang is now adopted by many big companies, including Google, Microsoft and of course Apple, which has used it from the beginning.

The LLVM infrastructure can be used to implement compilers for many programming languages and interpreters. For example, PostgreSQL now uses the LLVM JIT to optimize query execution, as specified here:

Currently, PostgreSQL executes SQL queries using the interpreter, which is quite slow. However, significant speedup can be achieved by compiling query "on-the-fly" with LLVM JIT: this way it's possible for given SQL query to generate more effective code, which is specialized using the information known at run time, and then additionally optimize it with LLVM. This approach is especially important for complex queries, where performance is CPU-bound.

Thanks to all the LLVM/Clang developers, and special thanks to Chris Lattner, who initiated the revolution and gave us a powerful infrastructure for developing meaningful tools.

Finally, a message to young developers: be the next Chris Lattner and start a revolution in the programming world :)