Heap Analysis Design: An Empirical Approach

Despite extensive research the construction of a precise and scalable static heap analysis for object-oriented programs remains an open problem. This paper argues that much of the difficulty is the result of empirically unvalidated and inappropriate design decisions. We examine three of them and determine that in practice: (1) strong updates are not necessary for obtaining precise results (2) fixed naming schemes for defining abstract memory locations are fundamentally limiting and are not required for efficiency, and (3) shape/sharing in the heap is generally simple and can be described using a simple abstract heap model. Using these results we construct a new heap analysis and experimentally demonstrate that it is both precise, capable of supporting program optimizations/tools which require sophisticated information on the structure of the heap, and scalable, allowing the analysis to be run on real world programs such as luindex/lusearch from DaCapo.