research-article

An intermediate representation for speculative optimizations in a dynamic compiler

Authors:

Gilles Duboscq,

Thomas Würthinger,

Christian Wimmer,

Hanspeter MössenböckAuthors Info & Claims

VMIL '13: Proceedings of the 7th ACM workshop on Virtual machines and intermediate languages

Pages 1 - 10

https://doi.org/10.1145/2542142.2542143

Published: 28 October 2013 Publication History

Abstract

We present a compiler intermediate representation (IR) that allows dynamic speculative optimizations for high-level languages. The IR is graph-based and contains nodes fixed to control flow as well as floating nodes. Side-effecting nodes include a framestate that maps values back to the original program. Guard nodes dynamically check assumptions and, on failure, deoptimize to the interpreter that continues execution. Guards implicitly use the framestate and program position of the last side-effecting node. Therefore, they can be represented as freely floating nodes in the IR. Exception edges are modeled as explicit control flow and are subject to full optimization. We use profiling and deoptimization to speculatively reduce the number of such edges. The IR is the core of a just-in-time compiler that is integrated with the Java HotSpot VM. We evaluate the design decisions of the IR using major Java benchmark suites.

References

[1]

Graal, revision 5a9d68c3a7d7. URL http://hg.openjdk.java.net/graal/graal/file/5a9d68c3a7d7.

[2]

HotSpot Express 25, build 43. URL http://hg.openjdk.java.net/hsx/hsx25/hotspot/file/hs25-b43.

[3]

B. Blanchet. Escape analysis for JavaTM: Theory and practice. ACM Transactions on Programming Languages and Systems, 25(6):713--775, Nov. 2003.

Digital Library

[4]

J.-D. Choi, D. Grove, M. Hind, and V. Sarkar. Efficient and precise modeling of exceptions for the analysis of java programs. In Proceedings of the ACMSIGPLAN-SIGSOFT work- shop on Program Analysis for Software Tools and Engineering, pages 21--31. ACM Press, 1999. ISBN 1-58113-137-2.

Digital Library

[5]

C. Click. Global code motion/global value numbering. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 246--257. ACM Press, 1995. ISBN 0-89791-697-2.

Digital Library

[6]

C. Click and M. Paleczny. A simple graph-based intermediate representation. In Papers from the ACM SIGPLAN workshop on Intermediate representations, IR '95, pages 35--49. ACM Press, 1995. ISBN 0-89791-754-5.

Digital Library

[7]

C. N. Click, Jr. Combining Analyses, Combining Optimizations. PhD thesis, Rice University, 1995.

Digital Library

[8]

R. Cytron, J. Ferrante, B. K. Rosen, M. N.Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, Oct. 1991. ISSN 0164-0925.

Digital Library

[9]

DaCapo Project. The DaCapo Benchmark Suite, 2012. URL http://dacapobench.org/.

[10]

J. C. Dehnert, B. K. Grant, J. P. Banning, R. Johnson, T. Kistler, A. Klaiber, and J. Mattson. The Transmeta Code MorphingTM software: using speculation, recovery, and adaptive retranslation to address real-life challenges. In Proceedings of the International Symposium on Code Generation and Optimization, pages 15--24. IEEE Computer Society, 2003. ISBN 0-7695-1913-X.

Digital Library

[11]

L. Djoudi, J.-T. Acquaviva, and D. Barthou. Compositional approach applied to loop specialization. Concurrency and Computation: Practice and Experience, 21(1):71--84, Jan. 2009. ISSN 1532-0626.

Digital Library

[12]

G. Duboscq, L. Stadler, T. Würthinger, D. Simon, and C. Wimmer. Graal IR: An extensible declarative intermediate representation. In Proceedings of the Asia-Pacific Programming Languages and Compilers Workshop, 2013.

[13]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 9(3):319--349, July 1987. ISSN 0164-0925.

Digital Library

[14]

S. J. Fink and F. Qian. Design, implementation and evaluation of adaptive recompilation with on-stack replacement. In Proceedings of the International Symposium on Code Generation and Optimization, pages 241--252. IEEE Computer Society, 2003. ISBN 0-7695-1913-X.

Digital Library

[15]

Google. V8 JavaScript Engine, . URL http://code.google.com/p/v8/.

[16]

Google. V8 SVN repository, . URL http://v8.googlecode.com/svn/.

[17]

U. Hölzle, C. Chambers, and D. Ungar. Debugging optimized code with dynamic deoptimization. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 32--43. ACM Press, 1992. ISBN 0-89791-475-9.

Digital Library

[18]

K. Kelsey, T. Bai, C. Ding, and C. Zhang. Fast track: A software system for speculative program optimization. In Proceedings of the International Symposium on Code Generation and Optimization, pages 157--168. IEEE Computer Society, 2009. ISBN 978-0-7695-3576-0.

Digital Library

[19]

T. Kotzmann and H. Mössenböck. Run-time support for optimizations based on escape analysis. In Proceedings of the International Symposium on Code Generation and Optimization, pages 49--60. IEEE Computer Society, 2007. ISBN 0-7695-2764-7.

Digital Library

[20]

T. Kotzmann, C. Wimmer, H. Mössenböck, T. Rodriguez, K. Russell, and D. Cox. Design of the Java HotSpotTM client compiler for Java 6. ACM Transactions on Architecture and Code Optimization, 5(1), May 2008. ISSN 1544-3566.

Digital Library

[21]

T. Lindholm and F. Yellin. The JavaTM Virtual Machine Specification. Addison-Wesley, 2nd edition, 1999.

Digital Library

[22]

R. Odaira and K. Hiraki. Sentinel pre: Hoisting beyond exception dependency with dynamic deoptimization. In Proceedings of the International Symposium on Code Generation and mOptimization, pages 328--338. IEEE Computer Society, 2005. ISBN 0-7695-2298-X.

Digital Library

[23]

OpenJDK Community. Graal Project, 2012. URL http://openjdk.java.net/projects/graal/.

[24]

M. Paleczny, C. Vick, and C. Click. The Java HotSpotTM server compiler. In Proceedings of the Symposium on Java Virtual Machine Research and Technology, pages 1--12. USENIX, 2001.

Digital Library

[25]

D. Schneider and C. F. Bolz. The efficient handling of guards in the design of RPython's tracing JIT. In Proceedings of the ACM workshop on Virtual Machines and Intermediate Languages, pages 3--12. ACM Press, 2012. ISBN 978-1-4503-1633-0.

Digital Library

[26]

J. W. Sias, S.-z. Ueng, G. A. Kent, I. M. Steiner, E. M. Nystrom, and W.-m. W. Hwu. Field-testing impact epic research results in itanium 2. In Proceedings of the International Symposium on Computer architecture, pages 26--. IEEE Computer Society, 2004. ISBN 0-7695-2143-6.

Digital Library

[27]

Standard Performance Evaluation Corporation. SPECjbb2005, . URL http://www.spec.org/jbb2005/.

[28]

Standard Performance Evaluation Corporation. SPECjvm2008, . URL http://www.spec.org/jvm2008/.

[29]

L. Su and M. H. Lipasti. Speculative optimization using hardware-monitored guarded regions for java virtual machines. pages 22--32. ACM Press, 2007. ISBN 978-1-59593-630-1.

Digital Library

[30]

V. Sundaresan, M. Stoodley, and P. Ramarao. Removing redundancy via exception check motion. In Proceedings of the International Symposium on Code Generation and Optimization, pages 134--143. ACM Press, 2008. ISBN 978-1-59593-978-4.

Digital Library

[31]

J. Whaley. Partial method compilation using dynamic profile information. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 166--179. ACM Press, 2001. ISBN 1-58113-335-9.

Digital Library

Cited By

Leißa RUllrich MMeyer JHack S(2025)MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL AgeProceedings of the ACM on Programming Languages10.1145/37048409:POPL(95-125)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704840
Nakamura HSonoyama AKamiyama TOguchi MYamaguchi S(2024)Performance Study of Kotlin and Java Programs with Bytecode AnalysisJournal of Information Processing10.2197/ipsjjip.32.38032(380-395)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.380
Pečimúth ALeopoldseder DTůma PJacob DKjolstad F(2024)An Analysis of Compiled Code Reusability in Dynamic CompilationProceedings of the 16th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3689490.3690406(43-53)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3689490.3690406
Show More Cited By

Index Terms

An intermediate representation for speculative optimizations in a dynamic compiler
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments

Recommendations

Speculation without regret: reducing deoptimization meta-data in the Graal compiler
PPPJ '14: Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java platform: Virtual machines, Languages, and Tools

Speculative optimizations are used in most Just In Time (JIT) compilers in order to take advantage of dynamic runtime feedback. These speculative optimizations usually require the compiler to produce meta-data that the Virtual Machine (VM) can use as ...
Partial Escape Analysis and Scalar Replacement for Java
CGO '14: Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization

Escape Analysis allows a compiler to determine whether an object is accessible outside the allocating method or thread. This information is used to perform optimizations such as Scalar Replacement, Stack Allocation and Lock Elision, allowing modern ...
Efficient Register Mapping and Allocation in LaTTe, an Open-Source Java Just-in-Time Compiler

Java just-in-time (JIT) compilers improve the performance of a Java virtual machine (JVM) by translating Java bytecode into native machine code on demand. One important problem in Java JIT compilation is how to map stack entries and local variables to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

VMIL '13: Proceedings of the 7th ACM workshop on Virtual machines and intermediate languages

October 2013

48 pages

ISBN:9781450326018

DOI:10.1145/2542142

General Chairs:
Christoph Bockisch
University of Twente, The Netherlands
,
Michael Haupt
Oracle Labs, Germany
,
Steve Blackburn
Australian National University, Australia
,
Hridesh Rajan
Iowa State University, USA
,
Program Chair:
Joseph Gil
Technion, Israel

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '13

Sponsor:

SIGPLAN

SPLASH '13: Conference on Systems, Programming, and Applications: Software for Humanity

October 28, 2013

Indiana, Indianapolis, USA

Acceptance Rates

VMIL '13 Paper Acceptance Rate 4 of 4 submissions, 100%;

Overall Acceptance Rate 4 of 4 submissions, 100%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
975
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)11

Reflects downloads up to 06 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Leißa RUllrich MMeyer JHack S(2025)MimIR: An Extensible and Type-Safe Intermediate Representation for the DSL AgeProceedings of the ACM on Programming Languages10.1145/37048409:POPL(95-125)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704840
Nakamura HSonoyama AKamiyama TOguchi MYamaguchi S(2024)Performance Study of Kotlin and Java Programs with Bytecode AnalysisJournal of Information Processing10.2197/ipsjjip.32.38032(380-395)Online publication date: 2024
https://doi.org/10.2197/ipsjjip.32.380
Pečimúth ALeopoldseder DTůma PJacob DKjolstad F(2024)An Analysis of Compiled Code Reusability in Dynamic CompilationProceedings of the 16th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3689490.3690406(43-53)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3689490.3690406
Burchell HLarose OMarr SErtl MKirsch C(2024)Towards Realistic Results for Instrumentation-Based Profilers for JIT-Compiled SystemsProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685058(82-89)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685058
Xu HJiang ZWang YFan SXu SXie PFu SPayer MLuo BLiao XXu JKirda ELie D(2024)Fuzzing JavaScript Engines with a Graph-based IRProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690336(3734-3748)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690336
Grulich PLepping ANugroho DPandey VDel Monte BZeuch SMarkl V(2024)Query Compilation Without RegretsProceedings of the ACM on Management of Data10.1145/36549682:3(1-28)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654968
Kohli SKharbanda SBruno RCarreira JFonseca P(2024)Pronghorn: Effective Checkpoint Orchestration for Serverless Hot-StartsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629556(298-316)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629556
Đekanović PVukasović MBojić D(2024)Model for Evaluating Points-to Analysis in GraalVM Native Image Using Instrumentation-Based ProfilingDisruptive Information Technologies for a Smart Society10.1007/978-3-031-50755-7_47(502-512)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-3-031-50755-7_47
D'Souza MYou JLhoták OProkopec A(2023)TASTyTruffle: Just-in-Time Specialization of Parametric PolymorphismProceedings of the ACM on Programming Languages10.1145/36228537:OOPSLA2(1561-1588)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622853
Pečimúth ALeopoldseder DTůma PBruno RMoss E(2023)Diagnosing Compiler Performance by Comparing Optimization DecisionsProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622994(47-61)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622994
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten