Vortex

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Vortex: an optimizing compiler for object-oriented languages

Full text

Pdf (2.45 MB)

Source

Conference on Object Oriented Programming Systems Languages and Applications archive
Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications table of contents

San Jose, California, United States

Pages: 83 - 100

Year of Publication: 1996

ISBN:0-89791-788-X

Also published in ...

Authors

Jeffrey Dean	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
David Grove	Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington
Vassily Litvinov	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

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 27, Citation Count: 49

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/236337.236344 What is a DOI?

ABSTRACT

Previously, techniques such as class hierarchy analysis and profile-guided receiver class prediction have been demonstrated to greatly improve the performance of applications written in pure object-oriented languages, but the degree to which these results are transferable to applications written in hybrid languages has been unclear. In part to answer this question, we have developed the Vortex compiler infrastructure, a language-independent optimizing compiler for object-oriented languages, with front-ends for Cecil, C++, Java, and Modula-3. In this paper, we describe the Vortex compiler's intermediate language, internal structure, and optimization suite, and then we report the results of experiments assessing the effectiveness of different combinations of optimizations on sizable applications across these four languages. We characterize the benchmark programs in terms of a collection of static and dynamic metrics, intended to quantify aspects of the "object-orientedness" of a program.

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 & Hölzle 95	Ole Agesen , Urs Hölzle, Type feedback vs. concrete type inference: a comparison of optimization techniques for object-oriented languages, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.91-107, October 15-19, 1995, Austin, Texas, United States
	Agesen & Hölzle 96	Urs Hölzle , Ole Agesen, Dynamic versus static optimization techniques for object-oriented languages, Theory and Practice of Object Systems, v.1 n.3, p.167-188, Fall 1995
	Agesen 95	Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
	Aho et al. 86	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	Aigner & Hölzle 96	Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
	AK et al. 89	Hassan Aït-Kaci , Robert Boyer , Patrick Lincoln , Roger Nasr, Efficient implementation of lattice operations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.115-146, Jan. 1989 [doi>10.1145/59287.59293]
	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
	Bieman & Zhao 95	James M. Bieman , Josephine Xia Zhao, Reuse through inheritance: a quantitative study of C++ software, Proceedings of the 1995 Symposium on Software reusability, p.47-52, April 29-30, 1995, Seattle, Washington, United States
	Bobrow et al. 88	Daniel G. Bobrow , Linda G. DeMichiel , Richard P. Gabriel , Sonya E. Keene , Gregor Kiczales , David A. Moon, Common Lisp Object System specification, ACM SIGPLAN Notices, v.23 n.SI, p.1-142, September 1988 [doi>10.1145/885631.885632]
	Calder & Grunwald 94	Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
	Chambers & Ungar 89	C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, ACM SIGPLAN Notices, v.24 n.7, p.146-160, July 1989
	Chambers & Ungar 90	Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, ACM SIGPLAN Notices, v.25 n.6, p.150-164, Jun. 1990
	Chambers 92	Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
	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.
	Chambers et al. 95	Craig Chambers , Jeffrey Dean , David Grove, A framework for selective recompilation in the presence of complex intermodule dependencies, Proceedings of the 17th international conference on Software engineering, p.221-230, April 24-28, 1995, Seattle, Washington, United States [doi>10.1145/225014.225035]
	Chambers et al. 96	Craig Chambers, Jeffrey Dean, and David Grove. Whole-Program Optimization of Object-Oriented Languages. Technical Report TR-96-06-02, Department of Computer Science and Engineering. University of Washington, June 1996.
	Chien 93	Andrew A. Chien, Concurrent aggregates: supporting modularity in massively parallel programs, MIT Press, Cambridge, MA, 1993
	Click & Cooper 95	Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
	Dean et al. 95a	Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, ACM SIGPLAN Notices, v.30 n.6, p.93-102, June 1995
	Dean et al. 95b	Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
	Deutsch & Schiffman 84	L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
	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
	EDG	C++ Front End 2.28. Provided by Edison Design Group, Inc. http://www.edg.com.
	Fernandez 95	Mary F. Fernández, Simple and effective link-time optimization of Modula-3 programs, ACM SIGPLAN Notices, v.30 n.6, p.103-115, June 1995
	Goldberg & Robson 83	Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	Gosling et al. 96	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	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
	Hölzle & Ungar 94	Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
	Hölzle et al. 91	Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
	JDK	Java Development Kit. Sun Microsystems Inc. http://java.sun.com/.
	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
	Lea 90	Doug Lea. Customization in C++. In Proceedings of the 1990 Usenix C++ Conference, San Francisco, CA, April 1990.
	Nelson 91	Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	Pande & Ryder 94	Hemant D. Pande and Barbara G. Ryder. Static Type Determination for C++. In Proceedings of Sixth USENIX C+ + Technical Conference, 1994.
	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
	Schaffert et al. 85	Craig Schaffert, Topher Cooper, and Carrie Wilpolt. Trellis Object-Based Environment, Language Reference Manual. Technical Report DEC-TR-372, Digital Equipment Corporation, November 1985.
	Shao & Appel 95	Zhong Shao , Andrew W. Appel, A type-based compiler for standard ML, ACM SIGPLAN Notices, v.30 n.6, p.116-129, June 1995
	SRC	DEC SRC Modula-3 Implementation. Digital Equipment Corporation Systems Research Center. http://www.research, di gi t al. co m/SRC/mo dula- 3/html/home.html.
	Stroustrup 87	Bjarne Stroustrup. Multiple Inheritance for C++. In In Proceedings of the European Unix Users Group Conference '87, pages 189-207, Helsinki, Finland, May 1987.
	Stroustrup 91	Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	Tarditi et al. 96	D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, ACM SIGPLAN Notices, v.31 n.5, p.181-192, May 1996
	Tjiang & Hennessy 92	Steven W. K. Tjiang , John L. Hennessy, Sharlit—a tool for building optimizers, ACM SIGPLAN Notices, v.27 n.7, p.82-93, July 1992
	Ungar & Smith 87	David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States

CITED BY 49

	Jongwook Woo , Isabelle Attali , Denis Caromel , Jean-Luc Gaudiot , Andrew L. Wendelborn, Alias analysis on type inference for class hierarchy in Java, Australian Computer Science Communications, v.23 n.1, p.206-214, January-February 2001
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
	Olivier Zendra , Dominique Colnet , Suzanne Collin, Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler, ACM SIGPLAN Notices, v.32 n.10, p.125-141, Oct. 1997
	Craig Chambers, Staged compilation, ACM SIGPLAN Notices, v.37 n.3, March 2002
	Vassily Litvinov, Contraint-based polymorphism in Cecil: towards a practical and static type system, ACM SIGPLAN Notices, v.33 n.10, p.388-411, Oct. 1998
	Karel Driesen , Urs Hölzle, Accurate indirect branch prediction, ACM SIGARCH Computer Architecture News, v.26 n.3, p.167-178, June 1998
	Brendon Cahoon , Kathryn S. McKinley, Simple and effective array prefetching in Java, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.86-95, November 03-05, 2002, Seattle, Washington, USA
	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
	Sorin Lerner , David Grove , Craig Chambers, Composing dataflow analyses and transformations, ACM SIGPLAN Notices, v.37 n.1, p.270-282, Jan. 2002
	Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, ACM SIGPLAN Notices, v.33 n.5, p.324-332, May 1998
	David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, ACM SIGPLAN Notices, v.32 n.10, p.108-124, Oct. 1997
	Iffat H. Kazi , Howard H. Chen , Berdenia Stanley , David J. Lilja, Techniques for obtaining high performance in Java programs, ACM Computing Surveys (CSUR), v.32 n.3, p.213-240, Sept. 2000
	Matthai Philipose , Craig Chambers , Susan J. Eggers, Towards automatic construction of staged compilers, ACM SIGPLAN Notices, v.37 n.1, p.113-125, Jan. 2002
	Craig Chambers , Weimin Chen, Efficient multiple and predicated dispatching, ACM SIGPLAN Notices, v.34 n.10, p.238-255, Oct. 1999
	Jong-Deok Choi , David Grove , Michael Hind , Vivek Sarkar, Efficient and precise modeling of exceptions for the analysis of Java programs, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.21-31, Sept. 1999
	Jan Vitek , R. Nigel Horspool , Andreas Krall, Efficient type inclusion tests, ACM SIGPLAN Notices, v.32 n.10, p.142-157, Oct. 1997
	Norman Ramsey , Mary F. Fernández, Specifying representations of machine instructions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.492-524, May 1997
	Frederick Smith , Greg Morrisett, Comparing mostly-copying and mark-sweep conservative collection, ACM SIGPLAN Notices, v.34 n.3, p.68-78, March 1999
	Christopher League , Zhong Shao , Valery Trifonov, Representing Java classes in a typed intermediate language, ACM SIGPLAN Notices, v.34 n.9, p.183-196, Sept. 1999
	Craig Chambers, Towards reusable, extensible components, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	Sorin Lerner , Todd Millstein , Craig Chambers, Automatically proving the correctness of compiler optimizations, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Jonathan Aldrich , Emin Gün Sirer , Craig Chambers , Susan J. Eggers, Comprehensive synchronization elimination for Java, Science of Computer Programming, v.47 n.2-3, p.91-120, May 2003
	Todd Millstein , Mark Reay , Craig Chambers, Relaxed MultiJava: balancing extensibility and modular typechecking, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, A study of exception handling and its dynamic optimization in Java, ACM SIGPLAN Notices, v.36 n.11, p.83-95, 11/01/2001
	Norman Ramsey , Simon Peyton Jones, A single intermediate language that supports multiple implementations of exceptions, ACM SIGPLAN Notices, v.35 n.5, p.285-298, May 2000
	V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States
	Matthew Arnold , Michael Hsiao , Ulrich Kremer , Barbara G. Ryder, Exploring the Interaction between Java's Implicitly Thrown Exceptions and Instruction Scheduling, International Journal of Parallel Programming, v.29 n.2, p.111-137, April 2001
	Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, EDO: Exception-directed optimization in java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.70-105, January 2006
	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
	Sorin Lerner , Todd Millstein , Erika Rice , Craig Chambers, Automated soundness proofs for dataflow analyses and transformations via local rules, ACM SIGPLAN Notices, v.40 n.1, p.364-377, January 2005
	David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001
	Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Remi Forax , Etienne Duris , Gilles Roussel, A Reflective Implementation of Java Multi-Methods, IEEE Transactions on Software Engineering, v.30 n.12, p.1055-1071, December 2004
	Jongwook Woo , Jean-Luc Gaudiot , Andrew L. Wendelborn, Alias analysis in Java with reference-set representation for high-performance computing, International Journal of Parallel Programming, v.32 n.1, p.39-76, February 2004
	S. Baskiyar, Efficient execution of pure object-oriented programs by follow-up compilation, Computing, v.69 n.4, p.273-289, December 2002
	Tao Li , Ravi Bhargava , Lizy Kurian John, Adapting branch-target buffer to improve the target predictability of java code, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.109-130, June 2005
	Yanhong A. Liu , Scott D. Stoller , Michael Gorbovitski , Tom Rothamel , Yanni Ellen Liu, Incrementalization across object abstraction, ACM SIGPLAN Notices, v.40 n.10, October 2005
	Dominic Duggan , John Ophel, Open and closed scopes for constrained genericity, Theoretical Computer Science, v.275 n.1-2, p.215-258, March 28 2002
	Gilles Muller , Bárbara Moura , Fabrice Bellard , Charles Consel, Harissa: a flexible and efficient java environment mixing bytecode and compiled code, Proceedings of the 3rd conference on USENIX Conference on Object-Oriented Technologies (COOTS), p.1-1, June 16-20, 1997, Portland, Oregon
	Todd A. Proebsting , Gregg Townsend , Patrick Bridges , John H. Hartman , Tim Newsham , Scott A. Watterson, Toba: java for applications a way ahead of time (WAT) compiler, Proceedings of the 3rd conference on USENIX Conference on Object-Oriented Technologies (COOTS), p.3-3, June 16-20, 1997, Portland, Oregon
	Zhong Shao, Typed common intermediate format, Proceedings of the Conference on Domain-Specific Languages on Conference on Domain-Specific Languages (DSL), 1997, p.8-8, October 15-17, 1997, Santa Barbara, California
	Olivier Zendra , Karel Driesen, Stress-testing Control Structures for Dynamic Dispatch in Java, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.105-118, August 01-02, 2002
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
	Mark Stoodley , Vijay Sundaresan, Automatically Reducing Repetitive Synchronization with a Just-in-Time Compiler for Java, Proceedings of the international symposium on Code generation and optimization, p.27-36, March 20-23, 2005
	Ankush Varma , Shuvra S. Bhattacharyya, Java-through-C Compilation: An Enabling Technology for Java in Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30161, February 16-20, 2004
	Norman Ramsey, Pragmatic aspects of reusable program generators, Journal of Functional Programming, v.13 n.3, p.601-646, May 2003
	Joshua Auerbach , David F. Bacon , Bob Blainey , Perry Cheng , Michael Dawson , Mike Fulton , David Grove , Darren Hart , Mark Stoodley, Design and implementation of a comprehensive real-time java virtual machine, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30-October 03, 2007, Salzburg, Austria