More Web Proxy on the site http://driver.im/

Article

Evaluating a Demand Driven Technique for Call Graph Construction

Authors:

Qi SuAuthors Info & Claims

CC '02: Proceedings of the 11th International Conference on Compiler Construction

Pages 29 - 45

Published: 08 April 2002 Publication History

Abstract

With the increasing importance of just-in-time or dynamic compilation and the use of program analysis as part of software development environments, there is a need for techniques for demand driven construction of a call graph. We have developed a technique for demand driven call graph construction which handles dynamic calls due to polymorphism in object-oriented languages. Our demand driven technique has the same accuracy as the corresponding exhaustive technique. The reduction in the graph construction time depends upon the ratio of the cardinality of the set of influencing nodes and the total number of nodes in the entire program.This paper presents a detailed experimental evaluation of the benefits of the demand driven technique over the exhaustive one. We consider a number of scenarios, including resolving a single call site, resolving all call sites in a method, resolving all call sites within all methods in a class and computing reaching definitions of all actual parameters inside a method. We compare the analysis time, the number of methods analyzed and the number of nodes in the working set for the demand driven and exhaustive analyses.We use SPECJVM programs as benchmarks for our experiments. Our experiments show for the larger SPECJVM programs, javac, mpegaudio and jack, demand driven analysis on the average takes nearly an order of magnitude less time than exhaustive analysis.

References

[1]

Gagan Agrawal. Simultaneous demand-driven data-flow and call graph analysis. In Proceedings of International Conference on Software Maintainance (ICSM) , September 1999.

[2]

Gagan Agrawal. Demand-drive call graph construction. In Proceedings of the Compiler Construction (CC) Conference , March 2000.

[3]

David Bacon and Peter F. Sweeney. Fast static analysis of c++ virtual function calls. In Eleventh Annual Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '96) , pages 324-341, October 1996.

[4]

Brad Calder and Dirk Grunwald. Reducing indirect function call overhead in C++ programs. In Conference Record of POPL '94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages , pages 397-408, Portland, Oregon, January 1994.

[5]

D. Callahan. The program summary graph and flow-sensitive interprocedural data flow analysis. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation , Atlanta, GA, June 1988.

[6]

R. Chatterjee, B. G. Ryder and W. A. Landi. Relevant Context Inference. In Proceedings of the Conference on Principles of Programming Languages (POPL) , pages 133-146, January 1999.

[7]

Jeffrey Dean, Craig Chambers and David Grove. Selective specialization for object-oriented languages. In Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation (PLDI) , pages 93-102, La Jolla, California, 18-21 June 1995. SIGPLAN Notices 30(6), June 1995.

[8]

Greg DeFouw, David Grove, and Craig Chambers. Fast interprocedural class analysis. In Proceedings of the POPL'98 Conference , 1998.

[9]

A. Diwan, K. S. McKinley and J. E. B. Moss. Using Types to Analyze and Optimize Object-Oriented Programs. ACM Transactions on Programming Languages and Systems , 23(1):30-72, January 2001.

[10]

E. Duesterwald, R. Gupta and M. L. Soffa. A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis. ACM Transactions on Programming Languages and Systems , 19(6):992-1030, November 1997.

[11]

David Grove, Greg DeFouw, Jeffrey Deanx and Craig Chambers. Call graph construction in object-oriented languages. In Proceedings of the Conference on Object Oriented Programming Systems, Languages and Applications , 1997.

[12]

S. Horwitz, T. Reps and M. Sagiv. Demand interprocedural dataflow analysis. In In SIGSOFT '95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering , pages 104-115, 1995.

[13]

Jens Palsberg and Patrick O'Keefe. A type system equivalent to flow analysis. In Conference Record of POPL '95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages , pages 367-378, San Francisco, California, January 1995.

[14]

Hemant Pande and Barbara Ryder. Data-flow-based virtual function resolution. In Proceedings of the Third International Static Analysis Symposium , 1996.

[15]

M. Porat, M. Biberstein, L. Koved and M. Mendelson. Automatic detection of immutable fields in Java. In Proceedings of CASCON , 2000.

[16]

Gregg Rothermel and M. J. Harrold. Analyzing regression test selection. IEEE Transactions on Software Engineering , 1996.

[17]

Atanas Routnev, Barbara G. Ryder and William Landi. Data-Flow Analysis of Program Fragments. In Proceedings of the Conference on Foundations of Software Engineering (FSE) , pages 235-253, September 1999.

[18]

O. Shivers. The semantics of Scheme control-flow analysis. In Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation , volume 26, pages 190-198, New Haven, CN, June 1991.

[19]

V. C. Sreedhar, M. Burke and J. D. Choi. A Framework for Interprocedural Optimization in the Presence of Dynamic Class Loading. In Proceedings of ACM SIG-PLAN Conference on Programming Language Design and Implementation (PLDI) , 2000.

[20]

Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallee-Rai, Patrick Lam, Etienne Gagnon and Charles Godin. Practical virtual method call resolution for Java. In Fifteenth Annual Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '2000) , pages 264-280. ACM Press, October 2000.

[21]

Frank Tip and Jens Palsberg. Scalable propagation-based call graph construction algorithms. In Fifteenth Annual Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '2000) , pages 281-293. ACM Press, October 2000.

[22]

Raja Vallee-Rai. Soot: A Java ByteCode Optimization Framework. Master's thesis, McGill University, 1999.

[23]

Mark Weiser. Program slicing. IEEE Transactions on Software Engineering , 10:352-357, 1984.

[24]

A. Zaks, V. Feldman and N. Aizikowitz. Sealed calls in java packages. In Proceedings of Conference on Object Oriented Programming Systems and Languages (OOPSLA) , pages 83-92. ACM Press, October 2000.

Cited By

Feng YWang XDillig ILin C(2015)EXPLORER : query- and demand-driven exploration of interprocedural control flow propertiesACM SIGPLAN Notices10.1145/2858965.281428450:10(520-534)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814284
Feng YWang XDillig ILin CAldrich JEugster P(2015)EXPLORER : query- and demand-driven exploration of interprocedural control flow propertiesProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814284(520-534)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814284
Ali KLhoták O(2013)AverroesProceedings of the 27th European conference on Object-Oriented Programming10.1007/978-3-642-39038-8_16(378-400)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39038-8_16
Show More Cited By

Evaluating a Demand Driven Technique for Call Graph Construction
1. Theory of computation
  1. Semantics and reasoning

Recommendations

Demand-Driven Construction of Call Graphs
CC '00: Proceedings of the 9th International Conference on Compiler Construction

Call graph construction has been an important area of research within the compilers and programming languages community. However, all existingt echniques focus on exhaustive analysis of all the call-sites in the program. With increasing importance of ...
Simultaneous Demand-Driven Data-Flow and Call Graph Analysis
ICSM '99: Proceedings of the IEEE International Conference on Software Maintenance

Recently, there has been much interest in performing demand-driven data-flow analysis in software development environments. Demand-driven analysis techniques compute data-flow fact(s) for a particular program point, rather than computing data-flow ...
Demand-driven pointer analysis

Known algorithms for pointer analysis are “global” in the sense that they perform an exhaustive analysis of a program or program component. In this paper we introduce a demand-driven approach for pointer analysis. Specifically, we describe a demand-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC '02: Proceedings of the 11th International Conference on Compiler Construction

April 2002

343 pages

ISBN:3540433694

Editor:
R. Nigel Horspool

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 April 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng YWang XDillig ILin C(2015)EXPLORER : query- and demand-driven exploration of interprocedural control flow propertiesACM SIGPLAN Notices10.1145/2858965.281428450:10(520-534)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814284
Feng YWang XDillig ILin CAldrich JEugster P(2015)EXPLORER : query- and demand-driven exploration of interprocedural control flow propertiesProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814284(520-534)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814284
Ali KLhoták O(2013)AverroesProceedings of the 27th European conference on Object-Oriented Programming10.1007/978-3-642-39038-8_16(378-400)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39038-8_16
Ali KLhoták O(2012)Application-Only call graph constructionProceedings of the 26th European conference on Object-Oriented Programming10.1007/978-3-642-31057-7_30(688-712)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-31057-7_30
Hirzel MDincklage DDiwan AHind M(2007)Fast online pointer analysisACM Transactions on Programming Languages and Systems10.1145/1216374.121637929:2(11-es)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1145/1216374.1216379
Saha DRamakrishnan CBarahona PFelty A(2005)Incremental and demand-driven points-to analysis using logic programmingProceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1069774.1069785(117-128)Online publication date: 11-Jul-2005
https://dl.acm.org/doi/10.1145/1069774.1069785
Livshits BWhaley JLam M(2005)Reflection analysis for javaProceedings of the Third Asian conference on Programming Languages and Systems10.1007/11575467_11(139-160)Online publication date: 2-Nov-2005
https://dl.acm.org/doi/10.1007/11575467_11

View Options

View options

Media

Figures

Other

Tables

View Table of Contents