The Lifelong Code Optimization Project

Home Teaching Research Publications People

 

Participants

Michael Brukman
Cameron Buschardt
Christopher Lattner
Mehvish Nagda
Anand Shukla
Vikram Adve

The Goal

To enable modern application code to be optimized at link-time with all static library code, reoptimized at runtime with runtime information about system architecture and code behavior; and reoptimized offline in the field (i.e., between runs) using profile information gathered from production runs.  We collectively refer to the latter two as post-link reoptimization.

The Problem

The traditional approach to code optimization is to do nearly all optimization at static compile-time. This approach is becoming increasingly insufficient for several reasons:

  1. Modern programming languages (e.g., object-oriented languages and languages for mobile code) and software practices (e.g., component-based software and dynamically linked libraries) significantly limit the effectiveness of static optimization.
  2. Applications are increasingly expected to outlive multiple generations of processors, and often to run well on a wide range of processors and system configurations.
  3. Modern processor architectures (both RISC and EPIC families) increasingly rely on compiler support for achieving high performance, including extracting instruction-level parallelism, effective scheduling, and good register allocation. It is very difficult to do these effectively object-oriented and component-based codes using static analysis and code generation.

The alternatives to static optimization are link-time and runtime optimization. Unfortunately, previous approaches are severely limited by some  major challenges:

  1. The major challenge is that native object code lacks sufficient high-level information to do high-level optimizations.  This limits all the above optimizations, including link-time, runtime, and offline optimizations in the field.
  2. Dynamic optimization is fundamentally limited by its high runtime cost.

Our Approach

The Lifelong Code Optimization (LCO) Project is a broad effort to address the above challenges.  It includes a number of research efforts, as well as a novel compiler infrastructure that is key to our approach:

bulletThe LLVM Instruction Set and Compilation Strategy: LLVM (Low Level Virtual Machine) is a novel object code representation and compiler infrastructure for link-time and post-link optimization. LLVM object code uses a virtual machine instruction set that consists of low-level instructions but contains rich information about types, access methods, and dataflow information. This interface allows much more aggressive optimizations both at link-time and post-link (i.e., at runtime, and even offline after software is installed on an end-user's system).  The LLVM infrastructure includes a front-end, a link-time optimization framework, back-ends for Sparc V9 and for C, and a runtime optimization system currently under development.  The LLVM design and infrastructure are described in more detail on the LLVM home page.  LLVM is being used in all of the following research efforts.
bulletMacroscopic Data Structure Analysis and Transformations: A link-time interprocedural analysis and transformation strategy for entire logical data structures (such as individual trees or graphs). This works has led to several novel results including:
bulletData Structure Graphs: A very fast, interprocedural analysis for identifying disjoint logical data structures and their properties;
bulletAutomatic Pool Allocation: Automatically allocating individual logical data structures to separate memory pools in ordinary imperative programs (e.g., using for codes using malloc and free).
bulletPointer Compression: Automatically replacing large (e.g., 64-bit) pointers with smaller (16 or 32-bit) pointers in linked data structures, and dynamically growing them as needed.

bulletRuntime Optimization of Native Code: We are developing a novel approach to the runtime optimization of native code based on LLVM.  The key idea is to avoid maintain a detailed mapping between the final optimized LLVM code and the corresponding native machine code (generated at link-time), and use this mapping to enable high-level analysis and transformations of the native code at runtime.  The approach has two benefits: (a) it provides much high-level information, including type and dataflow information, for use in code optimization; and (b) it significantly reduces runtime optimization overhead because analysis time is greatly reduced by using the analysis information already available in LLVM.

bulletStatic Analysis for Software Security and Reliability: We are collaborating with the Reliable Real-Time Systems group (led by Prof. Lui Sha) to develop language and compiler techniques for ensuring the memory safety of embedded software (e.g., real-time control codes) through static program analysis.  LLVM provides a powerful basis for this work because it allows such analysis to be performed in a language-independent manner (since it operates on a low-level representation), and enables interprocedural analysis without sacrificing the benefits of separate compilation (since it is a link-time framework).

bulletVirtual Processor Architectures: A virtual instruction set like LLVM enables a novel approach to processor design, similar in spirit to the Transmeta Crusoe processor family, but without the performance penalties inherent in using the Intel IA-32 instruction set as the virtual machine.