Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Multi-level Deduplication Engine (MDE), a novel mechanism for improving the efficiency of pointer analysis by recursively deduplicating data and memoizing operations. MDE assigns unique identifiers to values, eliminating redundancy and trivializing operations, thereby reducing memory usage and runtime. Evaluation on SPEC benchmarks demonstrates significant improvements, with up to 18.10x reduction in peak memory usage and 8.15x reduction in runtime, highlighting the potential for representation design to enhance static analysis.
Pointer analysis gets a massive speed and memory boost by recursively deduplicating redundant data and operations, achieving up to 18x memory reduction and 8x speedup.
Precise pointer analysis is a foundational component of many client analyses and optimizations. Scaling flow- and context-sensitive pointer analysis has been a long-standing challenge, suffering from combinatorial growth in both memory usage and runtime. Existing approaches address this primarily by reducing the amount of information tracked often, at the cost of precision and soundness. In our experience a significant proportion of this cost comes from propagation of duplicate data and low-level data structure operations being repeated a large number of times. Our measurements on SPEC benchmarks show that more than 90% of all set-union operations performed can be redundant. We present Multi-level Deduplication Engine (MDE), a mechanism that recursively augments the representation of data through de-duplication and the assignment of unique identifiers to values to eliminate redundancy. This allows MDE to trivialize many operations, and memoize operations enabling their future reuse. MDE's recursive structure allows it to represent de-duplicated values that themselves are constructed from other de-deuplicated values, capturing structural redundancy not easily possible with non-recursive techniques. We provide a full C++ implementation of MDE as a library and integrate it into an existing implementation of a flow- and context-sensitive pointer analysis. Evaluation on selected SPEC benchmarks shows a reduction up to 18.10x in peak memory usage and 8.15x in runtime. More notably, MDE exhibits an upward trend of effectiveness with the increase in benchmark size. Besides performance improvements, this work highlights the importance of representation design and suggests new opportunities for bringing efficiency to future analyses.