Frank Tip
ABSTRACT
Propagation-based call graph construction algorithms have been studied intensively in the 199Os, and differ primarily in the number of sets that are used to approximate run-time values of expressions. In practice, algorithms such as RTA that use a single set for the whole program scale well. The scalability of algorithms such as 0-CFA that use one set per expression remains doubtful.In this paper, we investigate the design space between RTA and 0-CFA. We have implemented various novel algorithms in the context of Jax, an application extractor for Java, and shown that they all scale to a 325,000-line program. A key property of these algorithms is that they do not analyze values on the run-time stack, which makes them efficient and easy to implement. Surprisingly, for detecting unreachable methods, the inexpensive RTA algorithm does almost as well as the seemingly more powerful algorithms. However, for determining call sites with a single target, one of our new algorithms obtains the current best tradeoff between speed and precision.
- 1.AGESEN, O. Constraint-based type inference and parametric polymorphism. Proceedings of the First International Static Analysis Symposium (SAS'94) (September 1994), 78-100. Springer-Verlag LNCS vol. 864.Google Scholar
Cross Ref
- 2.AGESEN, O. Concrete Type Inference: Delivering Object-Oriented Applications. PhD thesis, Stanford University, December 1995. Appeared as Sun Microsystems Laboratories Technical Report SMLI TR-96-52. Google ScholarDigital Library
- 3.ANDERSEN, L. O. Self-applicable C program specialization. In Proceedings of PEPM'92, Workshop on Partial Evaluation and Semantics-Based Program Manipulation (June 1992), pp. 54-61. (Technical Report YALEU/DCS/RR-909, Yale University).Google Scholar
- 4.ASHLEY, J. M. A practical and flexible flow analysis for higher-order languages. In Proceedings of POPL '96, 23nd Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1996), pp. 184-194. Google ScholarDigital Library
- 5.BACON, D. F. Fast and Effective Optimization of Statically Typed Object-Oriented Languages. PhD thesis, Computer Science Division, University of California, Berkeley, Dec. 1997. Report No. UCB/CSD-98-1017. Google ScholarDigital Library
- 6.BACON, D. F., AND SWEENEY, P. F. Fast static analysis of C++ virtual function calls. In Proceedings of the Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'96) (San Jose, CA, 1996), pp. 324-341. SIGPLAN Notices 31(10). Google ScholarDigital Library
- 7.CALDER, B., AND GRUNWALD, D. Reducing indirect function call overhead in C++ programs. Conference Record of the Twenty-First A CM Symposium on Principles of Programming Languages (January 1994), 397-408. Google ScholarDigital Library
- 8.CONSEL, C. A tour of Schism: A partial evaluation system for higher-order applicative languages. In Proceedings of PEPM'93, Second ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (1993), pp. 145-154. Google ScholarDigital Library
- 9.DEAN, J., AND CHAMBERS, C. Optimization of object-oriented programs using static class hierarchy analysis. Tech. Rep. 94-12-01, Department of Computer Science, University of Washington at Seattle, December 1994.Google ScholarDigital Library
- 10.DEAN, J., GROVE, D., AND CHAMBERS, C. Optimization of object-oriented programs using static class hierarchy analysis. In Proceedings of the Ninth European Conference on Object-Oriented Programming (ECOOP'95) (Aarhus, Denmark, Aug. 1995), W. Olthoff, Bd., Springer-Verlag, pp. 77-101. Google ScholarDigital Library
- 11.DEFouw, G., GROVE, D., AND CHAMBERS, C. Fast interprocedural class analysis. In Conference Record of the Twenty-Fifth ACM Symposium on Principles of Programming Languages (San Diego, CA, January 1998), pp. 222-236. Google ScholarDigital Library
- 12.EMhm, M., GHIYA, R., AND HENDREN, L. J. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation (1994), pp. 242-256. Google ScholarDigital Library
- 13.FAHNDRICH, M., AND AIKBN, A. Program analysis using mixed term and set constraints. In Proceedings of SAS'97, International Static Analysis Symposium (1997), Springer-Verlag (LNCS), pp. 114-126. Google ScholarDigital Library
- 14.FAHNDRICH, M., FOSTER, J. S., Su, Z., AND AIKEN, A. Partial online cycle elimination in inclusion constraint graphs. In Proceedings of ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (1998), pp. 85-96. Google ScholarDigital Library
- 15.FOSTER, J. S., FAHNDRICH, M., AND AIKBN, A. Polymorphic versus monomorphic flow-insensitive points-to analysis for C. In Proceedings of SAS 2000, 7th Static Analysis Symposium (2000), J. Palsberg, Ed., pp. 175-198. Google ScholarDigital Library
- 16.COLDBBRG, A., AND ROBSON, D. Smalltalk-80--The Language and its Implementation. Addison-Wesley, 1983. Google ScholarDigital Library
- 17.GROVE, D., DEFouw, G., DEAN, J., AND CHAMBERS, C. Call graph construction in object-oriented languages. In Proceedings of the Twelfth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97) (Atlanta, GA, 1997), pp. 108-124. SIGPLAN Notices 32(10). Google ScholarDigital Library
- 18.GROVE, D., DEFouw, G., DEAN, J., AND CHAMBERS, C. Call graph construction in object-oriented languages. In Proceedings of OOPSLA'97, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (1997), pp. 108-124. SIGPLAN Notices 32(10). Google ScholarDigital Library
- 19.HBINTZB, N. Set-based analysis of ML programs. In Proceedings of ACM Conference on LISP and Functional Programming (1994), pp. 306-317. Google ScholarDigital Library
- 20.HBNGLBIN, F. Dynamic typing. In Proceedings of ESOP'9$, European Symposium on Programming (1992), Springer-Verlag (LNCS 582), pp. 233-253. Google ScholarDigital Library
- 21.ISHIZAKI, i., KAWAHITO, M., YASUB, T., KOMATSU, H., AND NAKATANI, T. A study of devirtualization techniques for a Java just-in-time compiler. In Proceedings of the Fifteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '00) (Minneapolis, Minnesota), 2000). Google ScholarDigital Library
- 22.ISHIZAKI, K., KAWAHITO, M., YASUB, T., TAKBUCHI, M., OGASAWARA, T., SUGANUMA, T., ONODBRA, T., KOMATSU, H., AND NAKATANI, T. Design, implementation, and evaluation of optimizations in a just-in-time compiler. In Proceedings of the ACM SIGPLAN JavaGrande Conference (San Francisco, CA, June 1999). Google ScholarDigital Library
- 23.JAGANNATHAN, S., AND WEEKS, S. A unified treatment of flow analysis in higher-order languages. In Proceedings of POPL'95, and Annual SIGPLAN-SIGA CT Symposium on Principles of Programming Languages (1995), pp. 393-407. Google ScholarDigital Library
- 24.JAGANNATHAN, S., AND WRIGHT, A. Effective flow analysis for avoiding run-time checks. In Proceedings of SAS'95, International Static Analysis Symposium (Glasgow, Scotland, September 1995), Springer-Verlag (LNCS 983). Google ScholarDigital Library
- 25.JONES, N., AND MUCHNICK, S. A flexible approach to interprocedural data flow analysis of programs with recursive data structures. In Ninth Symposium on Principles of Programming Languages (1982), pp. 66-74. Google ScholarDigital Library
- 26.NIELSON, F., AND NIBLSON, H. R. Infinitary control flow analysis: A collecting semantics for closure analysis. In Proceedings of POPL'97, 24th Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages (1997), pp. 332-345. Google ScholarDigital Library
- 27.OXHOJ, N., PALSBERG, J., AND SCHVVARTZBACH, M. I. Making type inference practical. In Proceedings of ECOOP'92, Sixth European Conference on Object-Oriented Programming (Utrecht, The Netherlands, July 1992), Springer-Verlag (LNCS 615), pp. 329-349. Google ScholarDigital Library
- 28.PALSBBRG, J., AND SCHWARTZBACH, M. Object-Oriented Type Systems. John Wiley & Sons, 1993. Google ScholarDigital Library
- 29.PALSBERG, J., AND SCHWARTZBACH, M. I. Object-oriented type inference. In Proceedings of OOPSLA '91, ACM SIGPLAN Sixth Annual Conference on Object-Oriented Programming Systems, Languages and Applications (Phoenix, Arizona, October 1991), pp. 146-161. Google ScholarDigital Library
- 30.SOHMIDT, D. Natural-semantics-based abstract interpretation. In Proceedings of SAS'95, International Static Analysis Symposium (Glasgow, Scotland, September 1995), Springer-Verlag (LNCS 983). Google ScholarDigital Library
- 31.SHAPIRO, M., AND HORWITZ, S. Fast and accurate flow-insensitive points-to analysis. In Conference Record of the Twenty-Fourth ACM Symposium on Principles of Programming Languages (Paris, France, 1997), pp. 1-14. Google ScholarDigital Library
- 32.SHARIR, M., AND PNUELI, A. Two approaches to interprocedural data flow analysis. In Program Flow Analysis, Theory and Applications, S. Muchnick and N. Jones, Eds. 1981.Google Scholar
- 33.SHIVERS, O. Control-Flow Analysis of Higher-Order Languages. PhD thesis, CMU, May 1991. CMU-CS-91-145. Google ScholarDigital Library
- 34.SRIVASTAVA, A. Unreachable procedures in object oriented programming. A CM Letters on Programming Languages and Systems 1, 4 (December 1992), 355-364. Google ScholarDigital Library
- 35.STBBNSGAARD, S. Points-to analysis in almost linear time. In Proceedings of the Twenty-Third ACM Symposium on Principles of Programming Languages (St. Petersburg, FL, January 1996), pp. 32-41. Google ScholarDigital Library
- 36.STEFANESCU, D., AND ZHOU, Y. An equational framework for flow analysis of higher-order functional programs. In Proceedings of ACM Conference on LISP and Functional Programming (1994), pp. 318-327. Google ScholarDigital Library
- 37.Su, Z., FAHNDRICH, M., AND AIKEN, A. Projection merging: Reducing redundancies in inclusion constraint graphs. In Proceedings of POPL '00, and Annual SIGPLAN-SIGACT Symposium on Principles of Programming Languages (2000), pp. 81-95. Google ScholarDigital Library
- 38.SUNDARBSAN, V., HBNDRBN, L., RAZAFIMAHBFA, C., VALLBE-RAI, R., LAM, P., CAGNON, E., AND CODIN, C. Practical virtual method call resolution for Java. In Proceedings of the Fifteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '00) (Minneapolis, Minnesota), 2000). Google ScholarDigital Library
- 39.SWBBNBY, P. F., AND TIP, F. Extracting library-based object-oriented applications. In Proceedings of the Eighth International Symposium on the Foundations of Software Engineering (FSE-8) (November 2000). To appear. A previous version of this paper appeared as IBM Research Report RC 21596, November 1999. Google ScholarDigital Library
- 40.TIP, F., LAB'FRA, C., SWBBNBY, P. F., AND STRBBTBR, D. Practical experience with an application extractor for Java. In Proceedings of the Fourteenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99) (Denver, CO), 1999), pp. 292-305. SIGPLAN Notices 34(10). Google ScholarDigital Library
- 41.VALLE,-RAI, R., CAGNON, E., HBNDRBN, L., LAM, P., POMINVILLE, P., AND SUNDARESAN, V. Optimizing java hytecode using the soot framework: Is it feasible? In Proceedings of CC'00, International Conference on Compiler Construction (2000), Springer-Verlag (LNCS).Google Scholar
- 42.VITBK, J., HORSPOOL, R. N., AND KRALL, A. Efficient type inclusion tests. In Proceedings of OOPSLA '97, A CM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (1997), pp. 142-157. SIGPLAN Notices 32(10). Google ScholarDigital Library
Index Terms
- Scalable propagation-based call graph construction algorithms
Recommendations
Scalable propagation-based call graph construction algorithms
Propagation-based call graph construction algorithms have been studied intensively in the 199Os, and differ primarily in the number of sets that are used to approximate run-time values of expressions. In practice, algorithms such as RTA that use a ...
A framework for call graph construction algorithms
A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for ...
Join-graph propagation algorithms
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the ...
Comments