Donald Bren School of Information and Computer Sciences

Even though impressive progress has been made in the area of optimizing and parallelizing scientific programs with arrays, the application of similar techniques to programs with general (cyclic) pointer data structures has remained difficult. In this paper we introduce a new approach that leads to improved analysis and transformation of programs with recursively-defined pointer data structures.

Our approach is based on providing a mechanism for the abstract description of data structures (ADDS), which makes explicit the important properties, such a dimensionality, of pointer data structures. As illustrated with numerous examples, the ADDS definitions are both natural to specify, and general enough to handle both simple and complex pointer data structures.

We illustrate how an abstract data structure description can improve analysis by presenting an alias analysis approach that combines an alias analysis technique, path matrix analysis, with information available from an ADDS declaration. Given this improved alias analysis technique, we provide a concrete example of applying a software pipelining transformation to loops involving pointer data structures.