Automatic Pool Allocation: Compile-Time Control over Complete Pointer-Based Data Structures
Vikram Adve
University of Illinois - Urbana/Champagne
Monday, June 14, 2004
10:30am - SENSQ 5317
Refreshments at 10am in SENSQ 5319
Abstract
Traditional compiler techniques for pointer-intensive programs focus on disambiguating, reordering, or optimizing individual loads and stores, data elements, and data types. We describe an alternative approach we call "Macroscopic Data Structure Transformations," which are program analyses and transformations that operate at the level of _entire_ recursive data structures. The foundations of this approach are
- Data Structure Analysis (DSA): a fast, context-sensitive analysis with some novel features, which extracts key properties of data structure instances; and
- Automatic Pool Allocation: a new program transformation that gives the compiler partial control over data structure layout in the heap.
Automatic Pool Allocation itself improves performance significantly for heap-intensive programs but, more importantly, gives the compiler data layout information that enables other analyses and transformations that were not possible before. We describe several novel examples of "macroscopic" optimization techniques enabled by Automatic Pool Allocation. We have also used DSA and Pool Allocation to enforce memory safety without garbage collection in imperative programs, and we are building a secure, language-independent programming platform called SAFECode based on these techniques. These diverse applications provide evidence that the macroscopic data structure approach opens up a broad new class of compiler techniques for pointer-intensive programs.
Bio
Vikram Adve is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign. His research interests include compilers, computer architecture, and performance evaluation. His research group has developed the LLVM Compiler Infrastructure, a novel, publicly distributed, compiler framework for "lifelong" optimization of programs in arbitrary languages. The group is using LLVM for several broad research projects, including macroscopic data structure transformations, static analyses for enforcing program safety, and a new class of processor architectures we call Virtual Instruction Set Computers (VISC), which define a rich virtual instruction set implemented via a truly cooperative hardware/software microarchitecture.
Adve received a B.Tech. from I.I.T. Bombay in 1987, a Ph.D. in Computer Science from the University of Wisconsin in 1993, and was a Research Scientist at Rice University before joining the University of Illinois. He has received the NSF CAREER award, the Best Paper Award at the 2001 Workshop on Parallel and Distributed Simulation, and the UIUC Computer Science Department's Outstanding Junior Faculty Award. He is an Associate Editor of the ACM Transactions on Programming Languages and Systems (TOPLAS).