LLVM: A compilation Framework for Lifelong Program Analysis & Transformation

Introduction

• What?
  • Low Level Virtual Machine
    • an open source Compiler framework
    • supports analysis & optimization anytime
      • i.e. compile time, link time, run time
• Why?
  • Existing Open Source C Compilers have stagnated
    • based on decades old codegen technology
    • no modern techniques like
      • cross-file optimization
      • JIT codegen
    • difficult to learn, hard to change substantially
  • JVM weaknesses
    • must use all of JVM or none of it
    • forced to Java object model, no flexibility in choosing the language
    • huge mem footprint & start-up time
• How?
  • Build a set of modular compiler components
    • implement aggressive & modern techniques
    • integrate well with each other
    • have few dependencies on each other
    • are language- & target-independent where possible
    • integrate closely with existing tools where possible

Program Representation

• The code representation is one of the key factors of LLVM
  • provide high-level information about programs to support sophisticated analyses & transformation
    • language-independent Type Information
  • low-level enough to represent arbitrary programs
    • low-level assembly-like code: LLVM IR/bytecode

Compiler Architecture

• Goal
  • to enable sophisticated transformations @ link-time, install-time, run-time & idle-time
  • to use LLVM representation @ all stages
• Compile-Time
  • Externel static LLVM compilers = front-ends
    • source-language programs -> LLVM virtual instruction set
    • 3 key tasks
      • language-specific optimization
      • translate source programs to LLVM code
        • synthesizing as much useful LLVM type information as possible
          • pointers, structures, arrays...
      • Invoke LLVM passes for global/inter-procedural optimizations @ the module level
• Linker & Inter-procedural Optimizer
  • 1st phase where most of the program is available for analysis & transformation
  • Link-time optimizations operate directly on the LLVM representation
  • The LLVM representation goes through several optimization passes (each of which is a module of LLVM)
• Offline native Code Generation vs. JIT
  • 2 options for generating code for execution: Offline or JIT
    • Offline
      • Code gen is run statically @ link time or install time
      • Generate high performance native code for the app
      • Use expensive code gen techniques
      • Also possible to use the post-link (runtime (online) & offline) optimizers
        • a copy of LLVM bytecode is included into the executable itself
        • a light-weight instrumentation is inserted into the program
          • to identify frequently executed regions of code
    • JIT
      • invokes the appropriate code gen @ runtime
      • translates 1 function at a time for execution
        • if no native code gen is available, use the portable LLVM interpreter
      • can insert the same instrumentation as the offline code gen does
• Runtime Path Profiling & Re-optimization
  • when running, the most frequently executed paths of a program are identified through offline & online instrumentation
    • offline instrumentation was inserted by the native code gen
      • identifies frequently executed loop regions in the code
    • online instrumentation identifies frequently-executed paths within the detected hot loop regions
    • when hot paths are identified
      • duplicate the original LLVM code into a trace
      • perform LLVM optimizations
      • re-gen native code into a SW-managed trace cache
      • insert branches between the original code & new native code
• Offline Re-optimization with End-user profile Information
  • offline optimization during idle-time on an end-user's system is possible
    • because the LLVM representation is always preserved
  • idle-time optimizer
    • is a modified version of the link-time IP optimizer
    • has greater emphasis on profile-driven & target-specific optimizations