Program decomposition for pointer aliasing

Abstract

Pointer aliasing analysis is crucial to compile-time analyses for languages with general-purpose pointer usage (such as C), but many aliasing methods have proven quite costly. We present a technique that partitions the statements of a program to allow separate, and therefore possibly different, pointer aliasing analysis methods to be used on independent parts of the program. This decomposition enables exploration of tradeoff between algorithm efficiency and precision. We also present a new, efficient flow-insensitive pointer aliasing algorithm, which is used together with an existing flow-sensitive aliasing algorithm in our experiments. We demonstrate our technique in the context of determining side effects and variable fetches through names containing pointer dereferences (Thru-deref MOD/REF). Initial empirical results using a combination of a flow-sensitive and a flow-insensitive aliasing analysis on the same program, demonstrate that the resulting analysis is much faster than solely using the flow-sensitive method, and obtains similar precision for the Thru-deref MOD/REF problems.