Donald Bren School of Information and Computer Sciences

Even though impressive progress has been made in the area of optimizing and parallelizing array-based programs, the application of similar techniques to programs using pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties, pointers can be used to implement a wide variety of structures which exhibit a much larger set of properties. The diversity of these structures implies that programs with pointer data structures cannot be effectively analyzed by traditional optimizing and parallelizing compilers.

In this paper we present a new approach that leads to the improved analysis and transformation of programs with recursively-defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS). ADDS is a simple extension to existing imperative languages (such as C) that allows the programmer to explicitly describe the important properties of a large class of data structures. These abstract descriptions may be used by the compiler to achieve more accurate program analysis in the presence of pointers, which in turn enables and improves the application of numerous optimizing and parallelizing transformations.

We present ADDS by describing various data structures, we discuss how such descriptions can be used to improve analysis and debugging, and we supply three important transformations enabled by ADDS.