Sulekha Kulkarni
Xin Zhang
ABSTRACT
Practical programs share large modules of code. However, many program analyses are ineffective at reusing analysis results for shared code across programs. We present POLYMER, an analysis optimizer to address this problem. POLYMER runs the analysis offline on a corpus of training programs and learns analysis facts over shared code. It prunes the learnt facts to eliminate intermediate computations and then reuses these pruned facts to accelerate the analysis of other programs that share code with the training corpus. We have implemented POLYMER to accelerate analyses specified in Datalog, and apply it to optimize two analyses for Java programs: a call-graph analysis that is flow- and context-insensitive, and a points-to analysis that is flow- and context-sensitive. We evaluate the resulting analyses on ten programs from the DaCapo suite that share the JDK library. POLYMER achieves average speedups of 2.6× for the call- graph analysis and 5.2× for the points-to analysis.
- K. Ali and O. Lhoták. Application-only call graph construction. In ECOOP, 2012. Google Scholar
Digital Library
- K. Ali and O. Lhoták. Averroes: Whole-program analysis without the whole program. In ECOOP, 2013. Google ScholarDigital Library
- N. Allen, B. Scholz, and P. Krishnan. Staged points-to analysis for large code bases. In CC, 2015.Google ScholarCross Ref
- T. Ball and S. Rajamani. Bebop: a path-sensitive interprocedural dataflow engine. In PASTE, 2001. Google ScholarDigital Library
- E. Bodden. Inter-procedural data-flow analysis with IFDS/IDE and Soot. In SOAP, 2012. Google ScholarDigital Library
- M. Bravenboer and Y. Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In OOPSLA, 2009. Google ScholarDigital Library
- C. Calcagno, D. Distefano, P. O’Hearn, and H. Yang. Compositional shape analysis by means of bi-abduction. In POPL, 2009. Google ScholarDigital Library
- R. Chatterjee, B. G. Ryder, and W. Landi. Relevant context inference. In POPL, 1999. Google ScholarDigital Library
- P. Cousot and R. Cousot. Static determination of dynamic properties of recursive procedures. In E. Neuhold, editor, IFIP Conference on Formal Description of Programming Concepts. North-Holland, 1977.Google Scholar
- P. Cousot and R. Cousot. Modular static program analysis. In International Conference on Compiler Construction (CC’02), 2002. Google ScholarDigital Library
- I. Dillig, T. Dillig, A. Aiken, and M. Sagiv. Precise and compact modular procedure summaries for heap manipulating programs. In PLDI, 2011. Google ScholarDigital Library
- J. Dolby, S. Fink, and M. Sridharan. T. J. Watson Libraries for Analysis. http://wala.sourceforge. net/, 2006.Google Scholar
- P. Godefroid, A. V. Nori, S. K. Rajamani, and S. Tetali. Compositional may-must program analysis: unleashing the power of alternation. In POPL, 2010. Google ScholarDigital Library
- B. S. Gulavani, S. Chakraborty, G. Ramalingam, and A. V. Nori. Bottom-up shape analysis using LISF. ACM Trans. Program. Lang. Syst., 33(5), 2011. Google ScholarDigital Library
- G. Kastrinis and Y. Smaragdakis. Hybrid context sensitivity for points-to analysis. In PLDI, 2013. Google ScholarDigital Library
- R. Mangal, M. Naik, and H. Yang. A correspondence between two approaches to interprocedural analysis in the presence of join. In ESOP, 2014. Google ScholarDigital Library
- B. R. Murphy and M. S. Lam. Program analysis with partial transfer functions. In PEPM, 2000. Google ScholarDigital Library
- M. Naik. Chord: A versatile program analysis platform for Java bytecode. http://jchord.googlecode. com, 2006.Google Scholar
- H. Oh, H. Yang, and K. Yi. Learning a strategy for adapting a program analysis via Bayesian optimisation. In OOPSLA, 2015. Google ScholarDigital Library
- T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In POPL, 1995. Google ScholarDigital Library
- N. Rinetzky, J. Bauer, T. W. Reps, S. Sagiv, and R. Wilhelm. A semantics for procedure local heaps and its abstractions. In POPL, 2005. Google ScholarDigital Library
- A. Rountev, M. Sharp, and G. Xu. IDE dataflow analysis in the presence of large object-oriented libraries. In Compiler Construction, 2008. Google ScholarDigital Library
- M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications. Prentice-Hall, 1981.Google Scholar
- Y. Smaragdakis and M. Bravenboer. Using datalog for fast and easy program analysis. In Datalog 2.0 Workshop, 2010. Google ScholarDigital Library
- Y. Smaragdakis, G. Balatsouras, and G. Kastrinis. Setbased pre-processing for points-to analysis. In OOPSLA, 2013. Google ScholarDigital Library
- Y. Smaragdakis, M. Bravenboer, and O. Lhoták. Pick your contexts well: Understanding object-sensitivity. In POPL, 2013. Google ScholarDigital Library
- J. Whaley and M. S. Lam. Cloning-based contextsensitive pointer alias analysis using binary decision diagrams. In PLDI, 2004. Google ScholarDigital Library
- J. Whaley and M. C. Rinard. Compositional pointer and escape analysis for Java programs. In OOPSLA, 1999. Google ScholarDigital Library
- J. Whaley, D. Avots, M. Carbin, and M. Lam. Using datalog with binary decision diagrams for program analysis. In APLAS, 2005. Google ScholarDigital Library
- R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In PLDI, 1995. Google ScholarDigital Library
- D. Yan, G. Xu, and A. Rounte. Rethinking soot for summary-based whole-program analysis. In SOAP, 2012. Google ScholarDigital Library
- G. Yorsh, E. Yahav, and S. Chandra. Generating precise and concise procedure summaries. In POPL, 2008. Google ScholarDigital Library
- X. Zhang, R. Mangal, M. Naik, and H. Yang. Hybrid top-down and bottom-up interprocedural analysis. In PLDI, 2014. Google ScholarDigital Library
Index Terms
- Accelerating program analyses by cross-program training
Recommendations
Accelerating program analyses by cross-program training
OOPSLA '16Practical programs share large modules of code. However, many program analyses are ineffective at reusing analysis results for shared code across programs. We present POLYMER, an analysis optimizer to address this problem. POLYMER runs the analysis ...
Parametrizing Program Analysis
TASE '14: Proceedings of the 2014 Theoretical Aspects of Software Engineering Conference (tase 2014)A parametric analysis is an analysis whose input and output are parametrized with a number of parameters which can be instantiated to abstract properties after analysis is completed. We use Cousot and Cousot's Cardinal power domain to capture ...
Program analysis using WALA (tutorial)
ESEC/FSE 2022: Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software EngineeringStatic analysis is widely used in research and practice for multiple purposes such as fault localization, vulnerability detection, code clone identification, code refactoring, optimization, etc. Since implementing static analyzers is a non-trivial ...
Comments