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

(1) Data Structure Analysis (DSA): a fast, context-sensitive analysis with some novel features, which extracts key properties of data structure instances; and

(2) 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.

Short Bio: Vikram Adve is an Associate 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 widely distributed and novel compiler framework for 'lifelong' optimization of programs. 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, Best Paper Awards at PLDI 2005 and PADS 2001, 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).