ABSTRACT
As a classical data-flow analysis, reaching definitions analysis is the corner stone of various techniques, such as code optimization and program slicing. The built-in data-flow analysis framework in Soot has been implemented in the traditional iterative style. While being able to meet general requirements for implementation of data flow analyses, the framework may be less efficient for a certain type of analyses in which the complete data-flow solution is unnecessary.
In this paper, we introduce our Soot-based implementation of an inter-procedural demand-driven reaching definitions analysis. For a demand for reaching definitions facts, the analysis only explores relevant program points and variables, saving a considerable amount of computation. Preliminary results show that the implementation can be much more efficient than its traditional counterpart in several scenarios. The Soot framework has greatly facilitated the implementation by providing abundant basic analysis results via well designed APIs.
- A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: principles, techniques, and tools. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1986. Google ScholarDigital Library
- E. Duesterwald. A demand-driven approach for efficient interprocedural data flow analysis. PhD thesis, Pittsburgh, PA, USA, 1996. AAI9727844. Google ScholarDigital Library
- E. Duesterwald, R. Gupta, and M. L. Soffa. A practical framework for demand-driven interprocedural data flow analysis. ACM Trans. Program. Lang. Syst., 19(6):992--1030, Nov. 1997. Google ScholarDigital Library
- P. Lam, E. Bodden, O. Lhoták, and L. Hendren. The soot framework for java program analysis: a retrospective. In Cetus Users and Compiler Infrastructure Workshop, Galveston Island, TX, October 2011.Google Scholar
- O. Lhotak. Spark: A flexible points-to analysis framework for java. Master's thesis, McGill University, December 2002.Google Scholar
Index Terms
- Soot-based implementation of a demand-driven reaching definitions analysis
Recommendations
Inter-procedural data-flow analysis with IFDS/IDE and Soot
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysisThe IFDS and IDE frameworks by Reps, Horwitz and Sagiv are two general frameworks for the inter-procedural analysis of data-flow problems with distributive flow functions over finite domains. Many data-flow problems do have distributive flow functions ...
Demand-driven context-sensitive alias analysis for Java
ISSTA '11: Proceedings of the 2011 International Symposium on Software Testing and AnalysisSoftware tools for program understanding, transformation, verification, and testing often require an efficient yet highly-precise alias analysis. Typically this is done by computing points-to information, from which alias queries can be answered. This ...
Demand-driven refinement of points-to analysis
ICSE '19: Proceedings of the 41st International Conference on Software Engineering: Companion ProceedingsWe present DynaSens, a demand-driven approach to points-to analysis that uses slicing to automatically adjust the analysis' context-sensitivity. Within a points-to analysis, heap-carried data flows are composed of loads and stores, and these heap-...
Comments