| Call graph construction in object-oriented languages |
| Full text |
 Pdf
(2.63 MB)
|
| Source
|
ACM SIGPLAN Notices
archive
Volume 32 , Issue 10 (October 1997)
table of contents
Pages: 108 - 124
Year of Publication: 1997
ISSN:0362-1340
Also published in ...
|
|
Authors
|
|
David Grove
|
Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington
|
|
Greg DeFouw
|
Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington
|
|
Jeffrey Dean
|
Digital Equipment Corporation, Western Research Lab, 250 University Avenue, Palo Alto, CA and Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington
|
|
Craig Chambers
|
Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 32, Downloads (12 Months): 175, Citation Count: 49
|
|
|
Warning: The download time has expired please click on the item to try again.
 ABSTRACT
Interprocedural analyses enable optimizing compilers to more precisely model the effects of non-inlined procedure calls, potentially resulting in substantial increases in application performance. Applying interprocedural analysis to programs written in object-oriented or functional languages is complicated by the difficulty of constructing an accurate program call graph. This paper presents a parameterized algorithmic framework for call graph construction in the presence of message sends and/or first class functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empirically assess these algorithms by applying them to a suite of medium-sized programs written in Cecil and Java, reporting on the relative cost of the analyses, the relative precision of the constructed call graphs, and the impact of this precision on the effectiveness of a number of interprocedural optimizations.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
Agesen 94
|
Ole Agosen. Constraint-Based Type inference and Pa/ametrie Polymorphism. In First International Static Analysis Symposium, September 1994.
|
| |
Agesen 95
|
|
| |
Agesen 96
|
|
| |
Alt & Martin 95
|
|
 |
Bacon & Sweeney 96
|
David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
|
| |
Bracha & Griswold 93
|
Gilad Bracha , David Griswold, Strongtalk: typechecking Smalltalk in a production environment, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.215-230, September 26-October 01, 1993, Washington, D.C., United States
|
| |
Callahan et. al.90
|
|
| |
Chambers & Ungar 89
|
C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
|
| |
Chambers & Ungar 90
|
|
| |
Chambers 93
|
Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report TR-93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993.
|
| |
Cooper et. al. 92
|
Keith D. Cooper, Mary W. Hall, and Ken Kennedy, Procedure Cloning. In Proceedings of 1992 IEEE lnternation, al Conference on Computer Languages, pages 96--105, Oakland, CA, April 1992.
|
| |
Cousot & Cousot 77
|
|
| |
Dean 96
|
|
| |
Dean et. al. 95
|
|
| |
Dean et. al. 96
|
Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
|
| |
DeFouw et. al. 97
|
Greg DeFouw, David Grove, and Craig Chambers. Fast Interprocedural Class Analysis. Technical Report TR-97- 07-02, Department of Computer Science and Engineering. University of Washington, July 1997.
|
| |
Deutsch & Schiffman 84
|
|
| |
Diwan et. al. 96
|
Amer Diwan , J. Eliot B. Moss , Kathryn S. McKinley, Simple and effective analysis of statically-typed object-oriented programs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, October 06-10, 1996, San Jose, California, United States
|
| |
Emami et. al. 94
|
Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
|
| |
Gosling et. al, 96
|
|
| |
Grove et. al. 95
|
David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
|
| |
Hall & Kennedy 92
|
|
| |
Hölzle & Agesen 96
|
Urs Htilzle and Ole Agesen. Dy_narnie vs. Static Optimization Techniques for Object-Oriented Languages. Theory and Practice of Object Systems, i(3), 1996._
|
| |
Hölzle & Ungar 94
|
|
| |
Jagannathan & Weeks 95
|
|
| |
Johnson 88
|
Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.18-26, September 25-30, 1988, San Diego, California, United States
|
| |
Kam & Ullman 76
|
|
| |
Kildall 73
|
|
| |
Kranz 88
|
|
| |
Lakhotia 93
|
|
| |
Landi et. al. 93
|
|
| |
Nielson & Nielson 97
|
|
| |
Odersky & Wadler 97
|
|
| |
Oxhøj et.al. 92
|
|
| |
Palsberg & Schwartzbach 91
|
Jens Palsberg , Michael I. Schwartzbach, Object-oriented type inference, Conference proceedings on Object-oriented programming systems, languages, and applications, p.146-161, October 06-11, 1991, Phoenix, Arizona, United States
|
| |
Plevyak & Chien 94
|
John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
|
| |
Plevyak & Chien 95
|
|
| |
plevyak 96
|
|
| |
Ryder 79
|
Barbara Ryder. Constructing the Call Graph of a Program. IEEETransactions on Software Engineering, 5(3):216- 225, 1979.
|
| |
Shivers 88
|
|
| |
Shivers 91a
|
|
| |
Shivers 91b
|
Olin Shivers. Data Flow Analysis and Type Recovery in Scheme. In Topics in Advanced Language Implementation. M1T Press, 1991. Edited by Peter Lee. -
|
| |
Steensgaard 94
|
Bjarne Steensgaard. A Polyvariant Closure Analysis with Dynamic Abstraction. Unpublished manuscript, 1994.
|
| |
Steensgaard 96
|
|
| |
Stefanescu & Zhou 94
|
|
| |
Wilson & Lam 95
|
|
CITED BY 49
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, ACM SIGPLAN Notices, v.35 n.10, p.264-280, Oct. 2000
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States
|
|
|
Frédéric Besson , Thomas de Grenier de Latour , Thomas Jensen, Secure calling contexts for stack inspection, Proceedings of the 4th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.76-87, October 06-08, 2002, Pittsburgh, PA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sara Porat , Bilha Mendelson , Irina Shapira, Sharpening global static analysis to cope with Java, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.19, November 30-December 03, 1998, Toronto, Ontario, Canada
|
|
|
Saurabh Sinha , Mary Jean Harrold , Gregg Rothermel, System-dependence-graph-based slicing of programs with arbitrary interprocedural control flow, Proceedings of the 21st international conference on Software engineering, p.432-441, May 16-22, 1999, Los Angeles, California, United States
|
|
|
Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
D.3