Academic
Publications
Scalable Context-Sensitive Points-to Analysis Using Multidimensional Bloom Filters

Scalable Context-Sensitive Points-to Analysis Using Multidimensional Bloom Filters,10.1007/978-3-642-10672-9_6,Rupesh Nasre,Kaushik Rajan,Ramaswamy Go

Scalable Context-Sensitive Points-to Analysis Using Multidimensional Bloom Filters   (Citations: 2)
BibTex | RIS | RefWorks Download
Context-sensitive points-to analysis is critical for several pro- gram optimizations. However, as the number of contexts grows exponen- tially, storage requirements for the analysis increase tremendously for large programs, making the analysis non-scalable. We propose a scal- able flow-insensitive context-sensitive inclusion-based points-to analysis that uses a specially designed multi-dimensional bloom filter to store the points-to information. Two key observations motivate our proposal: (i) points-to information (between pointer-object and between pointer- pointer) is sparse, and (ii) moving from an exact to an approximate representation of points-to information only leads to reduced precision without affecting correctness of the (may-points-to) analysis. By using an approximate representation a multi-dimensional bloom filter can sig- nificantly reduce the memory requirements with a probabilistic bound on loss in precision. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that with an average storage requirement of 4MB, our approach achieves almost the same precision (98.6%) as the exact implementation. By increasing the average mem- ory to 27MB, it achieves precision upto 99.7% for these benchmarks. Using Mod/Ref analysis as the client, we find that the client analysis is not affected that often even when there is some loss of precision in the points-to representation. We find that the NoModRef percentage is within 2% of the exact analysis while requiring 4MB (maximum 15MB) memory and less than 4 minutes on average for the points-to analysis. Another major advantage of our technique is that it allows to trade off precision for memory usage of the analysis.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...∙ We show the effectiveness of our approach by applying it on top of the state-of-the-art algorithms (Andersen’s analysis [1], BDD-based Lazy Cycle Detection [10], Deep Propagation [7] and Bloom Filters [11]) for SPEC 2000 benchmarks and five large open source programs (httpd, sendmail, gdb, wine-server and ghostscript) (Section V). Our experimental evaluation shows a significant improvement in the analysis times: 33% in Andersen’s ...
    • ...For our experiments, we use the medium configuration [11] which results in less than 2% precision loss for the chosen benchmarks...
    • ...scalability. Das [3] proposed one level flow, Lattner et al. [25] unified contexts, while Nasre et al. [11] hashed contexts to alleviate the need to store the complete context information...

    Rupesh Nasreet al. Prioritizing constraint evaluation for efficient points-to analysis

    • ...For our experiments, we use the medium configuration [23] which results in roughly 2% of precision loss for the chosen benchmarks...
    • ...It should be noted here that bloom has 2% precision loss in these applications [23] compared to anders, bdd and linear...
    • ...[5] proposed one level flow, [20] unified contexts, while [23] hashed contexts to alleviate the need to store complete context information...

    Rupesh Nasreet al. Points-to Analysis as a System of Linear Equations

Sort by: