An Efficient Tunable Selective Points-to Analysis for Large Codebases
Points-to analysis is a fundamental static program analysis technique for tools including compilers and bug-checkers. Although object-based context sensitivity is known to improve precision of points-to analysis, scaling it for large Java codebases remains a challenge.
In this work, we develop a tunable, client-independent, object-sensitive points-to analysis framework where heap cloning is applied selectively. This approach is aimed at large codebases where standard analysis is typically expensive. Our design includes a pre-analysis that determines program points that contribute to the cost of an object-sensitive points-to analysis. A subsequent analysis then determines the context depth for each allocation site. While our framework can run standalone, it is also possible to tune it – the user of the framework can use the knowledge of the codebase being analysed to influence the selection of expensive program points as well as the process to differentiate the required context-depth. Overall, the approach determines where the cloning is beneficial and where the cloning is unlikely to be beneficial.
We have implemented our approach using Soufflé (a Datalog compiler) and an extension of the DOOP framework. Our experiments on large programs, including OpenJDK, show that our technique is efficient and precise. For the OpenJDK, our analysis reduces 27% of runtime and 18% of memory usage in comparison with 2O1H points-to analysis for a negligible loss of precision, while for Jython from the DaCapo benchmark suite, the same analysis reduces 91% of runtime for no loss of precision.
Sun 18 JunDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
09:30 - 10:30
Points-to AnalysisSOAP at Vertex WS216
Jihyeok Park KAIST, South Korea, Xavier Rival INRIA/CNRS/ENS Paris, Sukyoung Ryu KAISTDOI File Attached
|A Datalog Model of Must-Alias Analysis|
George Balatsouras University of Athens, Kostas Ferles University of Texas at Austin, USA, George Kastrinis University of Athens, Yannis Smaragdakis University of AthensDOI File Attached
|An Efficient Tunable Selective Points-to Analysis for Large Codebases|
Behnaz Hassanshahi Oracle Labs, Australia, Raghavendra Kagalavadi Oracle Labs, Australia, Paddy Krishnan , Bernhard Scholz University of Sydney, Australia, Yi Lu OracleDOI File Attached