LLVM: A compilation framework for lifelong program analysis & transformation

TLDR

No existing compilation approach provides all the capabilities that LLVM offers. We describe LLVM, a compiler framework designed to support transparent, lifelong program analysis and transformation for arbitrary programs, and evaluate its design in terms of representation size and effectiveness, compiler performance, and illustrative examples. LLVM defines a common, low‑level code representation in SSA form with a language‑independent type system, typed address arithmetic, and a uniform exception‑handling mechanism, enabling transparent analysis and transformation at compile‑time, link‑time, run‑time, and idle time. The LLVM framework and representation provide key capabilities essential for practical lifelong analysis and transformation of programs, as demonstrated by its representation size, performance on interprocedural problems, and benefits for challenging compiler tasks.

Abstract

We describe LLVM (low level virtual machine), a compiler framework designed to support transparent, lifelong program analysis and transformation for arbitrary programs, by providing high-level information to compiler transformations at compile-time, link-time, run-time, and in idle time between runs. LLVM defines a common, low-level code representation in static single assignment (SSA) form, with several novel features: a simple, language-independent type-system that exposes the primitives commonly used to implement high-level language features; an instruction for typed address arithmetic; and a simple mechanism that can be used to implement the exception handling features of high-level languages (and setjmp/longjmp in C) uniformly and efficiently. The LLVM compiler framework and code representation together provide a combination of key capabilities that are important for practical, lifelong analysis and transformation of programs. To our knowledge, no existing compilation approach provides all these capabilities. We describe the design of the LLVM representation and compiler framework, and evaluate the design in three ways: (a) the size and effectiveness of the representation, including the type information it provides; (b) compiler performance for several interprocedural problems; and (c) illustrative examples of the benefits LLVM provides for several challenging compiler problems.