Towards a practical shape analysis for recursive data structures

Pointers are variables that store addresses of other variables. Pointer analysis determines what addresses can be stored in pointer variables. Many compiler optimizations need to check if different operations may access the same memory location. The presence of pointers makes this task difficult, because they allow different accesses to reference same location. Variables have types and some types contain other variables called fields. Shape analysis is a specialized pointer analysis that determines structural properties of data structures connected by pointer fields. Recursive data structures, such as linked lists and binary trees, are created by objects of self-referential types—types that contain fields pointing to variables of the same type. Many shape analysis algorithms are based on graphical abstractions. They use node summarization algorithms, based on predefined patterns between neighboring objects, to summarize unknown-size data structures. An object can be part of only a single pattern. These algorithms do not scale well for self-referential types with many pointer fields; where objects do not have perfect matching patterns, some fields end up being represented inaccurately. To overcome this problem, we present an abstraction based on path aliasing information, called alias relationships. An object can be part of multiple alias relationships. We present a systematic way of defining alias relationships and a shape analysis algorithm based on these relationships. Our results are promising, showing improved accuracy compared to state-of-the-art alternatives on multiple programs using recursive data structures with many pointer fields. We also provide an overview of another contribution, the Cetus compiler infrastructure which we developed to facilitate various compiler research. Our algorithm is implemented using Cetus