skip to main content
10.1145/2998415.2998418acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
research-article

Improving trace-based JIT optimisation using whole-program information

Published: 31 October 2016 Publication History

Abstract

Trace-based just-in-time compilers use program analyses to optimise execution traces.
These analyses are limited in scope to the parts of the program that have been traced.
In this position paper, we conjecture that trace optimisations can benefit from extending the scope of their enabling analyses beyond these traces to the set of possible future execution states of the program.
This by incorporating a static analysis which, however, necessarily over-approximates this set.
We therefore propose to continuously refine the set of future states computed by an initial, ahead-of-time analysis using run-time information about the current execution state of the program.
Additional static analyses launched at run time could further refine the information about the future of the current and all possible states.
We expect that the resulting, hybrid program view of static and dynamic information may enable additional optimisations on collected traces and that these optimisations may overcome the computational overhead of keeping the view up-to-date.

References

[1]
B. ˚ Akerblom and T. Wrigstad. Measuring polymorphism in python programs. In Proceedings of the 11th Symposium on Dynamic Languages, DLS 2015, 2015.
[2]
B. ˚ Akerblom, J. Stendahl, M. Tumlin, and T. Wrigstad. Tracing dynamic features in python programs. In Proceedings of the 11th Working Conference on Mining Software Repositories, MSR 2014, 2014.
[3]
E. Andreasen and A. Møller. Determinacy in static analysis for jquery. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’14, 2014.
[4]
S. Arzt and E. Bodden. Reviser: Efficiently updating ide-/ifdsbased data-flow analyses in response to incremental program changes. In Proceedings of the 36th International Conference on Software Engineering, ICSE ’14, 2014.
[5]
C. F. Bolz, A. Cuni, M. Fijalkowski, and A. Rigo. Tracing the meta-level: Pypy’s tracing jit compiler. In Proc. of the 4th ICOOOLPS Workshop, 2009.
[6]
C. F. Bolz, A. Cuni, M. Fijlakowski, M. Leuschel, S. Pedroni, and A. Rigo. Runtime feedback in a meta-tracing jit for efficient dynamic languages. In Proceedings of the 6th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems, ICOOOLPS ’11, 2011.
[7]
O. Calla´u, R. Robbes, E. Tanter, and D. Röthlisberger. How developers use the dynamic features of programming languages: the case of smalltalk. In Proceedings of the International Working Conference on Mining Software Repositories, MSR’11, 2011.
[8]
C. L. Conway, K. S. Namjoshi, D. Dams, and S. A. Edwards. Incremental algorithms for inter-procedural analysis of safety properties. In K. Etessami and S. K. Rajamani, editors, Proceedings of the 17th International Conference on Computer Aided Verification, 2005.
[9]
B. Dufour, B. G. Ryder, and G. Sevitsky. Blended analysis for performance understanding of framework-based applications. In Proceedings of the 2007 International Symposium on Software Testing and Analysis, ISSTA ’07, 2007.
[10]
M. D. Ernst. Static and dynamic analysis: Synergy and duality. In WODA 2003: ICSE Workshop on Dynamic Analysis, WODA ’03, 2003.
[11]
A. Gal, B. Eich, M. Shaver, D. Anderson, D. Mandelin, M. R. Haghighat, B. Kaplan, G. Hoare, B. Zbarsky, J. Orendorff, J. Ruderman, E. W. Smith, R. Reitmaier, M. Bebenita, M. Chang, and M. Franz. Trace-based just-in-time type specialization for dynamic languages. In Proc. of the 30th ACM SIGPLAN PLDI Conf., 2009.
[12]
B. Hackett and S.-y. Guo. Fast and precise hybrid type inference for javascript. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, 2012.
[13]
A. Holkner and J. Harland. Evaluating the dynamic behaviour of python applications. In Proceedings of the Thirty-Second Australasian Conference on Computer Science - Volume 91, ACSC ’09, 2009.
[14]
H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani. A tracebased java jit compiler retrofitted from a method-based compiler. In Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’11, 2011.
[15]
M. Jenkins, L. Andersen, T. Gilray, and M. Might. Concrete and abstract interpretation: Better together. In Proceedings of the 2014 Scheme and Functional Programming Workshop, SFP ’14, 2015.
[16]
N. Lameed and L. Hendren. Staged static techniques to efficiently implement array copy semantics in a matlab jit compiler. In International Conference on Compiler Construction, CC ’11, 2011.
[17]
J. Nicolay, C. De Roover, W. De Meuter, and V. Jonckers. Automatic parallelization of side-effecting higher-order scheme programs. In Proceedings of the 11th IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM ’11, 2011.
[18]
G. Richards, S. Lebresne, B. Burg, and J. Vitek. An analysis of the dynamic behavior of javascript programs. SIGPLAN Not., 45(6), June 2010.
[19]
D. Saha and C. R. Ramakrishnan. Incremental and demanddriven points-to analysis using logic programming. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP ’05, 2005.
[20]
H. N. Santos, P. Alves, I. Costa, and F. M. Quintao Pereira. Just-in-time value specialization. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), CGO ’13, 2013.
[21]
D. Schneider and C. F. Bolz. The efficient handling of guards in the design of rpython’s tracing jit. In Proc. of the 6th ACM VMIL Workshop, 2012.
[22]
T. Sherwood, E. Perelman, G. Hamerly, and B. Calder. Automatically characterizing large scale program behavior. SIGOPS Oper. Syst. Rev., 36(5), Oct. 2002.
[23]
M. Sridharan, J. Dolby, S. Chandra, M. Schäfer, and F. Tip. Correlation tracking for points-to analysis of javascript. In European Conference on Object-Oriented Programming, 2012.
[24]
Q. Stievénart, J. Nicolay, W. De Meuter, and C. De Roover. Detecting concurrency bugs in higher-order programs through abstract interpretation. In Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming, PPDP ’15, 2015.
[25]
Q. Stievénart, M. Vandercammen, J. Nicolay, W. De Meuter, and C. De Roover. Scala-am: A modular static analysis framework. In Proceedings of the 16th IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM ’16, 2016.
[26]
D. Van Horn and M. Might. Abstracting abstract machines. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP ’10, 2010.

Cited By

View all
  • (2017)STRAF: A Scala Framework for Experiments in Trace-Based JIT CompilationGrand Timely Topics in Software Engineering10.1007/978-3-319-60074-1_10(223-234)Online publication date: 29-Jun-2017

Index Terms

  1. Improving trace-based JIT optimisation using whole-program information

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      VMIL 2016: Proceedings of the 8th International Workshop on Virtual Machines and Intermediate Languages
      October 2016
      27 pages
      ISBN:9781450346450
      DOI:10.1145/2998415
      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

      In-Cooperation

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 31 October 2016

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Hybrid Analysis
      2. Incremental Analysis
      3. JIT Compilation
      4. Static Analysis

      Qualifiers

      • Research-article

      Conference

      SPLASH '16
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 4 of 4 submissions, 100%

      Upcoming Conference

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)4
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 19 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2017)STRAF: A Scala Framework for Experiments in Trace-Based JIT CompilationGrand Timely Topics in Software Engineering10.1007/978-3-319-60074-1_10(223-234)Online publication date: 29-Jun-2017

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media