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 when he was only 25 years old. How it’s possible? I remember when I was 25 years I spend my time 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 from his thesis abstract the motivation behind the LLVM design:

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 resume the idea behind LLVM is to use the LLVM Intermediate Representation (IR), it’s like the 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 the optimization. To explain this compiler phase I can’t say 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 to build 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 enumerate clang-tidy, clang-query, CppDepend and more.

Clang always  up to date with the new standards