Article

Inlining of Virtual Methods

Authors:

Ole AgesenAuthors Info & Claims

ECOOP '99: Proceedings of the 13th European Conference on Object-Oriented Programming

Pages 258 - 278

Published: 14 June 1999 Publication History

Abstract

We discuss aspects of inlining of virtual method invocations. First, we introduce a new method test to guard inlinings of such invocations, with a different set of tradeoffs from the class-equality tests proposed previously in the literature. Second, we consider the problem of inlining virtual methods directly, with no guarding test, in dynamic languages such as Self or the Java^™ programming language, whose semantics prohibit a static identification of the complete set of modules that comprise a program. In non-dynamic languages, a whole-program analysis might prove the correctness of a direct virtual inlining. In dynamic languages, however, such analyses can be invalidated by later class loading, and must therefore be treated as assumptions whose later violation must cause recompilation. In the past, such systems have required an on-stack replacement mechanism to update currently-executing invocations of methods containing invalidated inlinings. This paper presents analyses that allow some virtual calls to be inlined directly, while ensuring that invocations in progress may complete safely even if class loading invalidates the inlining for future invocations. This provides the benefits of direct inlining without the need for on-stack replacement, which can be complicated and require space-consuming data structures.

References

[1]

Craig Chambers, David Grove, Greg DeFouw, and Jeffrey Dean. Call graph construction in object-oriented languages. ACM SIGPLAN Notices, 32(10):108-124, October 1997.

[2]

Craig Chambers and David Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In Bruce Knobe, editor, Proceedings of the SIGPLAN 1989 Conference on Programming Language Design and Implementation, pages 146-160, Portland, OR, USA, June 1989. ACM Press.

[3]

Ole-Johan Dahl, Bjørn Myrhaug, and Kristen Nygaard. Simula common base language. Technical Report S-22, Norwegian Computing Center, Oslo, Norway, 1970.

[4]

Jeffrey Dean. Whole-Program Optimization of Object-Oriented Languages. PhD thesis, University of Washington, Seattle, Washington, 1996.

[5]

Jeffrey Dean, Craig Chambers, and David Grove. Selective specialization for object-oriented languages. ACM SIGPLAN Notices, 30(6):93-102, June 1995.

[6]

Jeffrey Dean, Greg DeFouw, David Grove, Vassily Livinov, and Craig Chambers. Vortex: an optimizing compiler for object-oriented languages. ACM SIGPLAN Notices, 31(10):83-100, October 1996.

[7]

Jeffrey Dean, David Grove, and Craig Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In Walter G. Olthoff, editor, Proceedings of the Ninth European Conference on Object-Oriented Programming, volume 952 of Lecture Notes in Computer Science, pages 77-101, Århus, Denmark, 7-11 August 1995. Springer-Verlag.

[8]

L. Peter Deutsch and Allan Schiffman. Efficient implementation of a Smalltalk-80 system. In Proceedings of the 11th Symposium on the Principles of Programming Languages, pages 297-302, Salt Lake City, 1984. ACM SIGPLAN.

[9]

Amer Diwan, J. Eliot B. Moss, and Kathryn S. McKinley. Simple and effective analysis of statically-typed object-oriented programs. In Proceedings of the 1996 Conference on Object-Oriented Programs, Systems, Languages, and Applications, pages 292-305. ACM SIGPLAN, October 1996.

[10]

Karel Driesen and Urs Hölzle. Accurate indirect branch prediction. In Proceedings of the 25th Annual International Symposium on Computer Architecture (ISCA- 98), volume 26, 3 of ACM Computer Architecture News, pages 167-178, New York, June 27-July 1 1998. ACM Press.

[11]

Neal Feinberg, Sonya E. Keene, Robert O. Mathews, and P. Tucker Withington. The Dylan Programming Book. Addison-Wesley Longman, Reading, Mass., 1997.

[12]

Mary F. Fernandez. Simple and effective link-time optimization of Modula-3 programs. ACM SIGPLAN Notices, 30(6):103-115, June 1995.

[13]

Richard Gabriel, Jon White, and Daniel Bobrow. CLOS: Integrating object-oriented and functional programming. CACM: Communications of the ACM, 34, 1991.

[14]

Adele Goldberg and David Robson. Smalltalk-80: The Language and its Implementation. Addison-Wesley, Reading, MA, 1983.

[15]

James Gosling, Bill Joy, and Guy Steele. The Java^™ Language Specification. The Java Series. Addison-Wesley, 1.0 edition, August 1996.

[16]

Urs Hölzle. Adaptive optimization for SELF: Reconciling high performance with exploratory programming. Ph.D. Thesis CS-TR-94-1520, Stanford University, Department of Computer Science, August 1994.

[17]

Urs Hölzle, Craig Chambers, and David Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In P. America, editor, Proceedings of the 1991 European Conference on Object-oriented Programming, LNCS 512, pages 21-38, Geneva, Switzerland, July 1991. Springer-Verlag.

[18]

Urs Hölzle, Craig Chambers, and David Ungar. Debugging optimized code with dynamic deoptimization. In Christopher W. Fraser, editor, Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 32-43, San Francisco, CA, June 1992. ACM Press.

[19]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. The Java Series. Addison-Wesley, 1996.

[20]

Volano LLC. Volanomark benchmark. http://www.volano.com/benchmarks.html, Mar. 1999.

[21]

Bertrand Meyer. Eiffel: The Language. Prentice Hall, 1992.

[22]

Greg Nelson, editor. Systems Programming in Modula-3. Prentice-Hall, Englewood Cliffs, NJ, 1991.

[23]

John Plevyak and Andrew A. Chien. Precise concrete type inference for object-oriented languages. In Proceedings of the Ninth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 324-324, October 1994.

[24]

Craig Schaffert, Topher Cooper, and Carrie Wilpolt. Trellis object-based environment language reference manual. DEC-TR 372, Digital Equipment Corp., Object-Based Systems Group, Hudson, Massachusetts, Nov. 1985.

[25]

SPEC. SPECjvm98 benchmarks. http://www.spec.org/osg/jvm98, August 1998.

[26]

Bjarne Stroustrup. The C++ Programming Language: Second Edition. Addison-Wesley, Reading, Massachusetts, 1991.

[27]

Jan Vitek, Nigel R. Horspool, and Andreas Krall. Efficient type inclusion tests. In Proceedings of the 1997 Conference on Object-Oriented Programming Systems, Languages, and Applications, Atlanta, GA, October 1997. ACM Press.

Cited By

Zhang MAlawneh ARogers TSherwood TBerger EKozyrakis C(2021)Judging a type by its pointer: optimizing GPU virtual functionsProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446734(241-254)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446734
Belyakova JChung BGelinas JNash JTate RVitek J(2020)World age in Julia: optimizing method dispatch in the presence of evalProceedings of the ACM on Programming Languages10.1145/34282754:OOPSLA(1-26)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428275
Prokopec ADuboscq GLeopoldseder DWürthinger TKandemir MJimborean AMoseley T(2019)An optimization-driven incremental inline substitution algorithm for just-in-time compilersProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314893(164-179)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314893
Show More Cited By

Inlining of Virtual Methods
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

Flow-directed inlining
PLDI '96: Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation

A flow-directed inlining strategy uses information derived from control-flow analysis to specialize and inline procedures for functional and object-oriented languages. Since it uses control-flow analysis to identify candidate call sites, flow-directed ...
Flow-directed inlining

A flow-directed inlining strategy uses information derived from control-flow analysis to specialize and inline procedures for functional and object-oriented languages. Since it uses control-flow analysis to identify candidate call sites, flow-directed ...
Towards better inlining decisions using inlining trials

Inlining trials are a general mechanism for making better automatic decisions about whether a routine is profitable to inline. Unlike standard source-level inlining heuristics, an inlining trial captures the effects of optimizations applied to the body ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECOOP '99: Proceedings of the 13th European Conference on Object-Oriented Programming

June 1999

528 pages

ISBN:3540661565

Editor:
Rachid Guerraoui

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 14 June 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

75
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang MAlawneh ARogers TSherwood TBerger EKozyrakis C(2021)Judging a type by its pointer: optimizing GPU virtual functionsProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446734(241-254)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446734
Belyakova JChung BGelinas JNash JTate RVitek J(2020)World age in Julia: optimizing method dispatch in the presence of evalProceedings of the ACM on Programming Languages10.1145/34282754:OOPSLA(1-26)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428275
Prokopec ADuboscq GLeopoldseder DWürthinger TKandemir MJimborean AMoseley T(2019)An optimization-driven incremental inline substitution algorithm for just-in-time compilersProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314893(164-179)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314893
Shabalin DOdersky MErdweg SOliveira B(2018)Interflow: interprocedural flow-sensitive type inference and method duplicationProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241660(61-71)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241660
Ducournau RPagès JPrivat JZheng YBinder WTůma P(2016)Preexistence and concrete type analysis in the context of multiple inheritanceProceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools10.1145/2972206.2972207(1-12)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.1145/2972206.2972207
Zheng YBulej LBinder W(2015)Accurate profiling in the presence of dynamic compilationACM SIGPLAN Notices10.1145/2858965.281428150:10(433-450)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814281
Ducournau RPagès JVidal CPrivat JMorandat FZendra O(2015)Preexistence revisitedProceedings of the 10th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems10.1145/2843915.2843923(1-1)Online publication date: 4-Jul-2015
https://dl.acm.org/doi/10.1145/2843915.2843923
Zheng YBulej LBinder WAldrich JEugster P(2015)Accurate profiling in the presence of dynamic compilationProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814281(433-450)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814281
Hartmann TNoll AGross TKolodziej JChilders B(2014)Efficient code management for dynamic multi-tiered compilation systemsProceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools10.1145/2647508.2647513(51-62)Online publication date: 23-Sep-2014
https://dl.acm.org/doi/10.1145/2647508.2647513
Sarimbekov APodzimek ABulej LZheng YRicci NBinder WBockisch CHaupt MBlackburn SRajan HGil J(2013)Characteristics of dynamic JVM languagesProceedings of the 7th ACM workshop on Virtual machines and intermediate languages10.1145/2542142.2542144(11-20)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1145/2542142.2542144
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents