Just in Time: Assumptions and Speculations

Olivier Flückiger
August 2022

Submitted in partial fulfillment of the requirements
for the degree of Doctor of Philosophy

Khoury College of Computer Sciences
Northeastern University
Boston, MA

©2022 Olivier Flückiger — o@o1o.ch

This work is licensed under a Creative Commons Attribution- ShareAlike 4.0 License. To view a copy of this license visit:

https://creativecommons.org/licenses/by/4.0/legalcode.

PIC

SVG-Viewer needed.

Abstract

The success of just-in-time compilers is based on their ability to specialize code at run time. It allows them to dynamically observe the execution of a program and optimize code for properties of the current program state. Just-in-time compilation is the blackest of arts in language implementation; the initiation rituals include brutal debugging sessions and an oath to pierce all abstractions. While I enjoy flipping bits, I still believe that at least some of the suffering is avoidable and building just-in-time compilers could be a topic as precisely documented as any. Hence, a main motivation for writing this dissertation is to digest some of this black magic and capture it in simple and precise terms. This includes the following contributions:

This dissertation consists of two parts. First, the models and theoretical findings are presented. The goal of that part is to explain how and why dynamic optimizations work, how dynamic information can be used for optimizations, and how assumptions interact in with static compiler optimizations. Additionally, it is discussed how the models combine and how complete they are with regards to a full-blown language implementation. Secondly, Ř is described and evaluated. Ř is an implementation of the R language, following the recipes introduced by the first part. This allows us to connect and evaluate the designs with a realistic implementation.

Acknowledgments

Along the way many, many people helped me shape raw curiosity into a useful tool and empowered me to write this dissertation.

Most importantly, my heartfelt thanks for the unconditional support go to my adviser, Jan Vitek. I will truly miss the joy of working with you.

Many thanks to my plentiful and awesome co-authors and co-conspirators, including Aurèle Barrière, Guido Chari, Aviral Goel, Jakob Hain, Jan Ječmen, Filip Křikava, Sebastián Krynski, Paley Li, Petr Maj, Gabriel Scherer, Andreas Wälchli, Ming-Ho Yee.

Without the encouragement and patience of many mentors I would not have started this endeavor. Most prominently, thank you Toon Verwaest and Oscar Nierstrasz for sending me down this rabbit-hole. Thanks for teaching me everything about compilers and VMs to Daniel Clifford, Tomas Kalibera, Ben Titzer.

I also thank the PLISS attendees, who shall remain anonymous, for openly sharing that every PhD comes with its fair share of doubt and resignation.

Last but not least I am very grateful to my committee for engaging with my work and helping me better understand and explain it. Thank you Amal Ahmed, Mathias Felleisen, Filip Pizlo, and Steve Blackburn. In particular Matthias for your dedication.

Thank you to all the people I love for everything we have and still will experience. See you in the streets.

Olivier Flückiger
August 2022

Contents

Introduction
 1.1 Motivation
 1.2 Thesis
Assume: Speculation with Deoptimization
 2.1 On-Stack Replacement
 2.2 Contributions and Limitations
 2.3 Related Work
 2.4 Speculation in a Nutshell
 2.5 Optimizations
 2.6 Assume Formalized
 2.7 Discussion
 2.8 CoreJIT: Towards a Verified JIT
Context Dispatch: Splitting on Dynamic State
 3.1 Related Work
 3.2 Context Dispatch in a Nutshell
 3.3 An Illustrated Example
 3.4 Deoptless: Context Dispatched OSR
 3.5 Discussion
Ř : Implementation
 4.1 Background
 4.2 Architecture
 4.3 Related Work
 4.4 PIR
 4.5 Scope Resolution
 4.6 Discussion
 4.7 Assumptions in PIR
 4.8 Context Dispatch
 4.9 Deoptless
Performance Evaluation
 5.1 Methodology
 5.2 Baseline
 5.3 Speculation
 5.4 Context Dispatch
 5.5 Deoptless
Conclusions
 6.1 Future Work
Bibliography
List of Figures

Chapter 1
Introduction

Just-in-time compilers are omnipresent in today’s technology stacks. The performance of the code they generate is central to the growing adoption of languages with dynamic features such as code loading, extensible objects, monkey-patching, introspection, or eval. These kind of features render precise static analysis impossible and lead to a wide range of possible behaviors, even in seemingly benign programs. To resolve this issue compilers specialize programs at run-time according to observed behaviors — they identify likely invariants and optimize1 assuming the invariants hold. For instance,

Most optimizations in just-in-time compilers are based in some way on the premise that, from the vast range of possible behaviors only some will be exercised by any particular execution of a program. Specializing code to those particular behaviors has been fundamental in making dynamic languages practical in large applications. These kind of optimizations involve forming assumptions about likely behaviors, that are expected to hold true at run-time. Typically the assumptions are based on profiling data, gathered either from the current process or from previous invocations. This is a common practice, even utilized in ahead-of-time compilers, where it is known as profile guided optimizations. The advantage in a just-in-time scenario is that specialization can be explored lazily, generating only code that is actually needed, in contrast to the ahead-of-time case, where the generated code must handle all possible behaviors all the time. A fundamental problem in just-in-time compilation is therefore how to leverage dynamic analysis, i.e., an incomplete recording of the past behavior, for optimizations? In particular, how to speculate and specialize code for likely invariants, while still safely and efficiently handling the case where they turn out not to hold. The implementation thereof is often scattered around different components of the language implementation; for instance, devirtualization in a language with class loading relies on the interplay of collecting a dynamic call-graph in the runtime, optimizing under the assumption that it is stable and retiring code invalidated by the class loader, while handling the cases where the invalidated code is still being executed.

1.1 Motivation

In this area of run-time optimizations, there is a lack of well-documented and re-usable techniques. Specialization is typically ad-hoc, tied to peculiarities of the language or implementation, and often even distinct for different properties in the same system. For instance the specialization approach taken by Julia [Bezanson, Karpinski, Shah, and Edelman2012] requires a language with multi-method dispatch, the one by Truffle [Würthinger, Wimmer, Wöß, Stadler, Duboscq, Humer, Richards, Simon, and Wolczko2013] relies on their language implementation style using self-specializing AST interpreters. Speculative optimizations in particular are poorly documented and mistaken for an implementation detail on how to rewrite stack frames. This gap in the literature leads to island-solutions for each language and a reluctance by some language implementers to include speculation in their compiler. The reluctance is the result of a poor understanding of the underlying program transformations and missing off-the shelf techniques.

Speculation in particular is iconic for just-in-time compilation. Having a compiler available at run-time allows for multiple attempts at producing optimal code. This allows for aggressive optimization strategies, where code is expected to be wrongly optimized sometimes, but then subsequently and transparently replaced by updated and fixed code. Speculative optimizations stand out from other techniques by their ability to — at arbitrary program locations — exclude some parts of the source code from the code being optimized. This is achieved by guarding against unexpected behaviors with run-time checks and bailing out of the optimized code, back to the source code, if these guards fail. It follows that speculative optimizations allow us to trim down the vast range of possible behaviors and instead optimize and even analyze just for the expected ones. It also means, that some form of recovery action is necessary in the unexpected case. We refer to that action as deoptimization and it relies on some form of execution state rewriting by the underlying runtime, such as on-stack-replacement or stack-switching.

A non-speculating specialization on the other hand involves upfront splitting of the control-flow on a property. I will refer to them as contextual optimizations, as they specialize code to certain predicates over the program state. Often contextual optimizations result in the duplication of the code being optimized. Real-world examples include multi-method dispatching on argument types in Julia, where each function signature discovered through dispatch leads to a new function being compiled and optimized. Or, optimizations involving tail-duplication, such as message splitting in SELF, where the control-flow within a function is split on the type of a result of a message send to produce optimized continuations for expected dynamic types.

As a concrete example, consider a code fragment S, which is part of a lager program, and shall be specialized to a certain runtime context. For instance the fragment S could have a free variable x and the goal is to provide a particularly fast implementation for, say, the cases where x is 42. A fragment could be a function body, but also a smaller or bigger piece of code. Let’s assume S is the following expression:

if (!is.numeric(x) || x == 0) 
  error() 
else 
  1/x

For a simple non-speculating optimization we start with a transformation to duplicate the fragment into if (x == 42) then S else S. This allows us to optimize each clone of S independently under the contextual information whether x == 42 holds. Within the then branch, the compiler can assume x == 42 to be part of the static optimization context, and conversely within the else branch x != 42.

Now let us contrast this approach with a speculative optimization. In that case we simply state assert(x == 42); S. For expressions dominated by the assertion, the fact x == 42 is again part of the static optimization context. The case where that assumption does not hold, is not part of the code emitted by such a compiler.

In summary, a speculative optimization means that the compiler can simply assume a likely invariant at a certain program location, and the unexpected case falls outside the compilation unit. Under speculative optimizations we also allow instructions being executed optimistically and work being done that has to be discarded or even reverted if the assumption fails. A non-speculative optimization on the other hand produces code that cannot be invalidated. It is still possible to optimize for dynamic properties, though the properties are used in a non-speculative way.

Example

Consider the following vector access function in R

at <- function(x, y) 
        x[[as.numeric(y)]]

which converts the y argument to a number and then uses that number as an index into argument x. Assume we call the function with three different kinds of arguments as follows:

1vec <- c(1,2,3) 
2# index is a scalar number 
3at(vec, 1) 
4# index is string 
5at(vec, "1") 
6# index type unknown at call-site 
7pos <- function() sample(1:3, 1) 
8at(vec, pos())

In the first two cases the type of the argument is known at the call site. This does not hold for the third case, because R evaluates arguments by need; pos() is only invoked, when the y argument is accessed for the first time, which happens during the execution of at. If we were to clone the function at and optimize it for different types of arguments, we can specialize it for three distinct cases: number[n] × number for the call-site at line 3, number[n] × string at line 5, and number[n] × any at line 8. The first two signatures directly lead to well optimized versions — at the source level they would look like:

at_1 <- function(x, y) { 
  if (1 <= y && y <= num_vec_len(x)) 
    num_vec_at(x, y) 
  else error(...) 
}
at_2 <- function(x, y) { 
  y <- as.numeric(y) 
  if (is.na(y)) 
    NA 
  else 
    at_1(x, y) 
}

The third case does not lend itself to any useful optimizations, since at the call-site it is unclear what the expression pos() eventually returns (excluding inter-procedural analysis for now). This is where speculation comes into play, and type-feedback from previous runs can be employed to narrow down the behavior to what we expect from the past. To make lazy evaluation specific, we’ll mark the position where arguments are evaluated with force. After forcing the argument expression, we can then speculate on its type and shape:

at_3 <- function(x, y) { 
  y <- force(y) 
  assume(scalar_int(y), in_bounds(x, y)) 
  num_vec_at(x, y) 
}

In case our assumptions are wrong, the assume instruction is supposed to fall back to the source version of this function. It allows us to ignore unlikely cases, i.e., in this case most of the implementation of vector access, which would have to deal with different vector types, indexing modes and possible errors. Of course for that to actually work, assume is more complicated than an assertion and more meta-data is required than is shown here.

Questions

An efficient implementation of a dynamic language must use information only available at run-time to optimize code. In particular this information is incomplete and changes over time. There are fundamentally two approaches to this problem, one is to speculate on likely properties and fall-back otherwise, the other is to somehow split control-flow on properties, which are checked up-front. Both of these approaches present problems and open questions.

Speculation

The goal of speculation is, that a compiler can base optimizations not only on static facts, but also on likely invariants. Should a speculation turn out to be incorrect for a particular execution, then the optimized code is discarded and the execution switches back to unoptimized code on-the-fly. But, what does it entail to bail out of wrongly optimized code that is currently being executed, i.e., to deoptimize code with active stack frames? Program counters must be updated, optimized execution state rewritten into corresponding unoptimized state, potentially switching from native to interpreted code, and some parts of the unoptimized state might not even exist and have to be synthesized and materialized. The mechanism is typically relegated to implementation details that are neither clearly abstracted nor documented, and scattered around different levels of the implementation. Is there a formal and transferable way to model speculation? How can compiler correctness be stated in the presence of speculation? When are two versions compiled under different assumptions equivalent? How do traditional optimizations have to be adapted? Does deoptimization inhibit optimizations?

Specialization

There are situations where it is beneficial to optimize code by specializing it to multiple scenarios. For instance if profile data suggests that a particular variable alternatively holds one of two unrelated dynamic types, then it makes sense to split control on that type and optimize for the two continuations separately. In other words, the aim of specialization is to split code, such that contextual information about the current program state can be used for optimizations. Many existing splitting and customization techniques fall under this category and implementations use different approaches to generate code specialized to certain properties of the program state. Given such a fragmented space, is there a unified or unifying technique to describe and implement specialization? How can a language implementation be structured to benefit from specialization? Can specialized code be shared between compatible uses and contexts? What does it mean for contexts to be compatible? How does specialization interact with speculation? How can the generation of specialized code be deferred as much as possible, such that more dynamic information can be considered.

1.2 Thesis

This dissertation presents a framework for soundly injecting assumptions into the optimizer of a just-in-time compiler. First, speculative optimizations with deoptimization as fallback mechanism are formalized in the sourir model. Sourir’s assume instruction enables optimizations based on arbitrary assumptions at any point. Second, context dispatch provides a generic approach for splitting on properties checked at run-time. Context dispatch allows to optimize functions lazily, up to the actually encountered contexts of assumptions, which act like static optimization contexts in an ahead-of-time compiler. I will defend the thesis that

Assume and context dispatch provide the basis for optimizations based on run-time assumptions in a competitive just-in-time compiler.

To understand that statement I will briefly introduce the two models, summarize their contributions, and explicit the claims.

Sourir

The sourir model of speculation, presented in

chapter 2

, is a simple abstraction for speculative optimizations that allows for formal reasoning on speculation at the IR level. It makes the following contributions:

Context Dispatch

Specialization by context dispatch, introduced in

chapter 3

, unifies how a runtime system can exploit contextual information and provides a simple approach to structure a just-in-time compiler around code specialization. It allows a compiler to specialize fragments of code up to a context of assumptions, and the specialized fragments to be shared between compatible contexts. The contributions are how to

Sourir and context dispatch complement each other. I will also introduce a combined deoptless deoptimization strategy using context dispatch.

Claims

This thesis presents Ř, a bug-compatible implementation of the R language with a JIT compiler. R’s dynamic nature and lazy evaluation strategy requires the optimizer to be able to optimistically speculate and specialize. The implementation effort is presented in

chapter 4

, which also covers those particularities of the R language that make it particularly resilient to optimizations. Ř uses a context dispatch system, and the optimizing compiler in Ř has an IR that is based closely on sourir. Ř shows that these two pieces of theory provide blueprints for building a language implementation with competitive performance. In particular in Ř the following claims are validated:

Non-Claims

I want to stress upfront that sourir and context dispatch do not cover the entirety of the implementation. This dissertation focuses on the optimizing compiler. In particular the main focus is on the middle-end of a JIT and optimizations on its IR as enabled by dynamic information. Other details are important for a good implementation, such as efficient profile collection, a fast garbage collector, a native backend, or a good interpreter. Sourir and context dispatch co-evolved with Ř and were instrumental in my own understanding of key aspects of JIT compilation. The actual implementation goes beyond these building blocks — on the one hand it features extensions for practical reasons, and on the other hand many more parts are necessary for a complete language implementation. These extensions are discussed less formally, when presenting the implementation. A complete model and potentially a verified JIT implementation remain future work.

Structure

This thesis is structured as follows. The two main contributions are presented in chapter 2 and chapter 3. The former presents a formalization of speculative optimizations and discusses the relationship of the model with implementations. The latter focuses on specialization using context dispatch and related applications. To validate my claims chapter 4 presents how these contributions are usable in a real-world implementation called Ř and chapter 5 shows that Ř is competitive. chapter 6 concludes and presents future work.

Publications

The Ř virtual machine is available and developed as free software at ř-vm.net.

The text of this dissertation is based or borrows from the following peer-reviewed publications:

The experimental setup for various performance results can be reproduced by the following artifacts:

Chapter 2
Assume: Speculation with Deoptimization

Many just-in-time compilers support some form of speculative optimization to avoid generating code for unlikely control-flow paths. For instance the prevalent polymorphism in a dynamic language causes even the simplest code to have non-trivial control flow. Consider the JavaScript snippet (example by Bebenita, Brandner, Fahndrich, Logozzo, Schulte, Tillmann, and Venter [2010]):

for (var i = 0; i < a.length-1; i++) { 
  var t  = a[i]; 
  a[i]   = a[i+1]; 
  a[i+1] = t; 
}
Listing 2.1:Shift in JavaScript

Without optimization one iteration of the loop executes 210 instructions; all arithmetic operations are dispatched and their results boxed. If the compiler is allowed to make the assumption it is operating on integers, the body of the loop shrinks down to 13 instructions. As another example, most Java implementations assume that non-final methods are not overridden. Speculating on this fact allows compilers to avoid emitting dispatch code [Ishizaki, Kawahito, Yasue, Komatsu, and Nakatani2000]. Newly loaded classes are monitored, and any time a method is overridden, the virtual machine invalidates code that contains devirtualized calls to that method. The validity of speculations is expressed as a predicate on the program state. If some program action, like loading a new class, falsifies that predicate, the generated code must be discarded. To undo an assumption, an implementation must ensure that functions compiled under that assumption are retired. This entails replacing affected code with a version that does not depend on the invalid predicate and, if a function currently being executed is found to contain invalid code, that function needs to be replaced on the fly. In such a case, it is necessary to transfer control to a different version of the function, and in the process, it may be necessary to materialize portions of the state that were optimized away and perform other recovery actions. In particular, if the invalidated function was inlined into another function, it is necessary to synthesize a new stack frame for the caller. This is referred to as deoptimization, or on-stack-replacement, and is found in most industrial-strength compilers.

Speculative optimization gives rise to a large and multi-dimensional design space that lies mostly unexplored. First, compiler writers must decide how to obtain information about program state. This can be done ahead-of-time by profiling, just-in-time by sampling or instrumenting code. Second, they must select which facts to record. This can range from information about the program, its class hierarchy, which packages were loaded, to information about the value of a particular mutable location in the heap. Finally, they must decide how to efficiently monitor the validity of speculations. While some points in this space have been explored empirically, existing systems have done it in an ad hoc manner that is often both language- and implementation-specific, and thus difficult to transfer.

The model shown here has a focused goal. The aim is to demystify the interaction between compiler transformations and deoptimization. When are two versions compiled under different assumptions equivalent? How should traditional optimizations be adapted when operating on code containing deoptimization points? In what ways does deoptimization inhibit optimizations? The assume model gives compiler writers the formal tools they need to reason about speculative optimizations. To do this in a way that is independent of the specific language being targeted and of implementation details relative to a particular compiler infrastructure, we have designed a high-level compiler intermediate representation (IR), named sourir, that is adequate for many dynamic languages without being tied to any one in particular.

A sourir program is made up of functions, and each function can have multiple versions. We equip the IR with a single instruction, named assume, specific to speculative optimization. This instruction has the role of describing what assumptions are being used to perform speculative optimization and what information must be preserved for deoptimization. It tests if those assumptions hold, and in case they do not, transfers control to another, less optimized version of the code. Reifying assumptions in the IR makes the interaction with compiler transformations explicit and simplifies reasoning. The assume instruction is more than a branch: when deoptimizing it replaces the current stack frame with a stack frame that has the variables and values expected by the target version, and, in case the function was inlined, it synthesizes missing stack frames. Furthermore, unlike a branch, its deoptimization target is not considered by the compiler during analysis and optimization. The code executed in case of deoptimization is invisible to the optimizer. This simplifies optimizations and reduces compile time as

rot ()
 Vnative
 |      ...
 |      call type =  typeof (a )
 |
 |      assume  type =  NumArray  else rot.V base.Lt []
 | Lt   branch  i < limit  Lo Lrt
 | Lo   var  t = a [ i ]
 |      assume  t ⁄=  HL  else rot.V base.Ls [ i = i , j = i + 1 ]
 |      a [ i ] ← a [ i + 1 ]
 |      a [ i + 1 ] ← t
 |      i ←  i +  1
 |      goto Lt
 |
 | Lrt   ...
V|base
 |      ...
 | Lt   branch  i < limit  Lo Lrt
 | Lo   call j =  add ( i , 1)
 | Ls   call t1 =  get ( a , i)
 |      call t2 =  get ( a , j)
 |
 |      call t3 =  store (a , i , t2)
 |      call t4 =  store (a , j , t1)
 |      i ←  j
 |      goto Lt
 | Lrt   ...

Figure 2.1:Compiled function from Listing 2.1

the analysis remains local to the version being optimized and the deoptimization metadata is considered to be a stand-in for the target version.

As an example consider the loop from Listing 2.1. A possible translation to sourir is shown in Figure 2.1 (less relevant code elided). V base contains the original version. Helper functions Get and store implement JavaScript (JS) array semantics, and the function add implement JS addition. Version V native contains only primitive sourir instructions. This version is optimized under the assumption that the variable a is an array of primitive numbers, which is represented by the first assume instruction. Further, JS arrays can be sparse and contain holes, in which case access might need to be delegated to a getter function. For this example HL denotes such a hole. The second assume instruction reifies the compiler’s speculation that the array has no holes, by asserting the predicate t HL . It also contains the associated deoptimization metadata. In case the predicate does not hold, we deoptimize to a related position in the base version by recreating the variables in the target scope. As can be seen in the second assume, local variables are mapped as given by the so called varmap [ i  =  i , j =  i  + 1 ]; the current value of  i  is carried over into the target frame’s  i , whereas variable j has to be recomputed.

To visualize the approach let us consider an abstract graph of the execution. The speculative optimization appears as shown in Figure 2.2, gray boxes representing function versions.

PIC

Figure 2.2:Speculation

Calling the function invokes the speculatively optimized version. If a dynamic guard fails, then a deoptimization happens, we transfer execution to the target version, into the middle of the function at deopt, discarding the optimized code.

2.1 On-Stack Replacement

Before going into details about how to correctly create and use the assume instruction in the compiler IR, this section takes a step back and presents the underlying implementation techniques and identifies the different pieces in a real-world deoptimization. This includes a preview of how to eventually lower an assume instruction to something a CPU can execute. In general the relevant implementation technique is known as on-stack replacement. OSR refers to an exceptional transfer of control between two versions of a function. It is employed by just-in-time compilers in situations where a function can or has to be replaced at once, without waiting for it to exit normally. To the user, this exchange is not observable, the new function transparently picks up where the old one stopped. On-stack refers to the fact that the involved functions have active stack frames that need to be rewritten. OSR is an umbrella term used in literature and practice to describe exceptional transfer of control for different reasons and using different kind of mappings between stack frames or program states. The term deoptimization and on-stack replacement are often used interchangeably. Although their meanings overlap, we should be more precise in their use.1 The term deoptimization highlights the fact, that optimizations are being undone. A deoptimization transfers control from a speculatively optimized version with a failing assumption, to a less speculatively optimized version, undoing the failing assumption. On the other hand, the term OSR focuses on the implementation technique, whereby stack-frames are rewritten. OSR can be used for other applications, such as implementing exceptions, or tiering-up, i.e., changing from a less to a more optimized version. Similarly, deoptimization can be implemented without OSR, for instance by relying on a execution environment with support for stack-switching, or simply using tail-calls and lazy replacement. The latter strategy is employed by Ř.

As shown in the previous section, speculative optimizations and in particular deoptimization, needs a way of exiting and entering functions in the middle of execution, with low performance impact on the case where the guards hold. When the guard fails, then instead of continuing normally, the function is exceptionally terminated and replaced with the unoptimized baseline function, as visualized in Figure 2.2. A correct deoptimization requires the system to extract the state of the optimized function, transform it into a corresponding unoptimized state and then materialize it to continue the execution.

Definitions

We call functions that should be exited origins and their replacements targets. Each function has an execution state, or stack frame, that is dependent on the code format but typically consists of at least the position in the code and the values of local variables. The format of origin and target can be vastly different if, for instance, one of them is interpreted and the other runs natively. A mapping between states captures the steps needed to rewrite origin states to target states. Since both origin and target are derived from the same source code, we sometimes use the term source to refer to the common ancestry of various compiled code fragments.

Figure 2.3

shows an idealized OSR that (a) extracts the state of the origin, (b) maps it to the source, (c) maps it to the target, and finally (d) materializes the target state.

PIC

Figure 2.3:Parts of an OSR event

Origin and target do not need to be constrained to a single stack frame and a single function. For example when exiting an inlined function, one origin function maps to multiple target functions. In other words, the stack frame of the origin needs to be split into multiple target stack frames.

OSR has been described as black magic due to the non-conventional control-flow that it introduces. A significant part of the complexity comes from the fact that most implementations do not provide clean abstractions for OSR. For example, extracting and rewriting the program state, i.e., steps (a) and (b) in Figure 2.3, are often not separated cleanly. Both of these two steps provide challenges, but for different reasons. Extracting the program state is challenging due to low-level concerns. We need very fine grained access to the internal state of the computation at the OSR points. This access has to be provided by the backend of our compiler, e.g., by exposing how the execution state is mapped to the hardware or the interpreter. On the other hand, mapping the extracted program state to a target state, i.e., creating a correct varmap, relies on the optimizer providing the required information.

Simplifications

In practice, many implementations follow a simplified design combining (b) and (c) into one mapping that translates directly from one state to another. This works particularly well, if the compiler of one end of the OSR uses the code of the other end of the OSR as source code. For instance a typical implementation uses the bytecode of the first tier interpreter as the source code of the optimizing native compiler:
pict

In this architecture, there is only one compiler and one compilation direction between the two ends of the OSR. In other words, the origin code is the source code of this compiler, therefore the mapping takes just one step, from native to bytecode (BC). On the other hand, in the case where both ends of the OSR are compiled from some common source code, the mapping of execution states has two steps, as it needs to pass through the original source. Given the following two compilation tiers:

pict

the second compilation mandates a mapping that lifts the state from an origin (native) state to a source state, the first compilation a mapping that lowers it to a target (BC) state. Therefore, the generic model is important in cases where OSR transitions from optimized to optimized code.

In sourir, the origin and target state of a deoptimization have the same representation. In other words the varmap corresponds to (c), the mapping (b) is the identity, since source and origin are identical. Furthermore (a) and (d) are trivial, since our execution states are semantic states of the sourir IR. This simplification was made to focus on the main problem of creating and maintaining a correct mapping for deoptimization.

Directions

If OSR jumps from optimized to unoptimized code, we call it OSR-out, or deoptimization, when it is used to bail out of failing speculative optimizations. As a simple example, if the user debugs optimized code with constant-folding applied to, then deoptimization can be used to restore the constant values. If OSR jumps from unoptimized to optimized code, we call it OSR-in or tiering up. This is useful, for instance, when the program is stuck in a long-running loop. In the general case where it jumps from optimized to optimized code, both apply and we simply call it OSR. Typically OSR cannot happen at arbitrary locations; we call the possible locations OSR exit or OSR entry points. OSR is general as it allows to undo arbitrary transformations. When OSR is used to transition between different optimization levels, it must be transparent, i.e., deoptimization becomes part of the correctness argument for optimizations. In turn, deoptimization enables compiler transformations that would otherwise be unsound.

Implementation Choices for OSR-out

The lowest overhead to peak performance for OSR exit points can be achieved by extracting the execution state by an external mechanism. Typically, at a defined location execution is conditionally stopped and control transferred to an OSR-out implementation, e.g., by tail-calling it. The OSR-out implementation needs metadata produced by the compiler that describes how the execution state can be retrieved from the registers and native run-time stack. This is only possible with fine-grained control over the code layout produced by the native backend. For efficiency, certain implementations will go to great lengths to implement the conditional guard of assume instructions such that it has the lowest overhead on the fast-case. This can go as far as compiling it to a nop, that will be patched inline, in case some external condition is invalidated. A simpler alternative implementation is to pass all the required state as arguments to a dedicated OSR-out primitive function. This approach generates more code, as the state extraction is effectively embedded into the emitted code but is easy to implement and efficient in case deoptimization triggers.

Simplified OSR-in

Whereas OSR-out relies on the ability to extract the source execution state at many locations, OSR-in is simpler. While one could arrange for OSR-in to enter optimized code in the middle of a function, these entry points would limit optimizations and would not be easy to implement, in particular if using an off-the-shelf code generator such as LLVM. Instead, one can compile a continuation starting from the current program location to the end of the current function. This continuation is executed once and on the next invocation the function is compiled a second time from the beginning of the function. This approach simplifies the mapping of execution states, as there is only one concrete state that needs to be mapped instead of multiple abstract states at every potential entry point. The current state is simply passed as an argument to the continuation. This is a popular implementation choice.

2.2 Contributions and Limitations

We now turn our attention back to the optimizations. From now on this chapter stays at the abstraction level of a compiler intermediate representation. In that representation we develop notions and techniques to correctly produce and maintain the mapping (c) from Figure 2.3. We prove the correctness of a selection of traditional compiler optimizations in the presence of speculation; these are constant propagation, unreachable code elimination, and function inlining. The main challenge for correctness is that the transformations operate on one version in isolation and therefore only see a subset of all possible control flows. We show how to split the work to prove correctness between the pass that establishes a version-to-version correspondence and the actual optimizations. Furthermore, we introduce and prove the correctness of three optimizations specific to speculation, namely unrestricted deoptimization, predicate hoisting, and assume composition.

Our work makes several simplifying assumptions. We ignore the issue of generation of versions: we study optimizations operating on a program at a certain point in time, on a set of versions created before that time. We do not model the low-level details of code generation. Sourir is not designed for implementation, but about reasoning support for existing or new JIT implementations.

Most importantly, in sourir the origin and target state of a deoptimization have the same representation. This simplification was made to focus on the main problem of mapping the states. For an actual implementation the target state most likely has a different representation. For instance in Ř, and similarly in Java, the target is the bytecode interpreter. In other words deoptimization materializes program states of an interpreter — the deoptimization target is a bytecode offset, the target values are placed on the operand stack of the interpreter, and so on. We refer to chapter 4 for an example of how to bridge this gap. If we compare the varmaps of this implementation with the sourir model, then what changes are the left-hand sides of the mapping. Instead of creating a sourir environment of local variables, the target state for instance consists of an operand stack. For instance, instead of [ i  =  i , j =  i  + 1 ], the varmap might be [ stack  = i , i  + 1 ]. Since the optimizer operates only on the right-hand sides of the varmaps, the changes affect only the front-end of the full compiler and do not affect the results from this chapter.

Finally, the assume IR might be lowered to some more optimized execution format, say a native binary. Lowering assume instructions is outside the scope of this chapter. The issues in doing so are similar to lowering a call instruction, but often great additional care is taken for the instruction to have as little overhead as possible if the guarding condition holds, as we expect this to be the default case. How the proofs can be extended to include native code is future work.

2.3 Related Work

OSR for deoptimization was pioneered in SELF by Hölzle, Chambers, and Ungar [1992]. At first, the idea was simply to deoptimize code to provide a source-level debugging experience. In that sense, it was a speculative optimization on the assumption that debugging is not used. Soon the idea was applied to speculatively optimize for all kinds of assumptions, from the stability of class hierarchies [Paleczny et al.2001] to unlikely behavior in general [Burke, Choi, Fink, Grove, Hind, Sarkar, Serrano, Sreedhar, Srinivasan, and Whaley1999], and providing more and more flexibility to the optimizer in the presence of deoptimization [Soman and Krintz2006]. We are reaching the point where deoptimization is an off-the-shelf technique that more and more compilers are relying on for diverse purposes [Odaira and Hiraki2005Schneider and Bolz2012Duboscq, Würthinger, and Mössenböck2014Stadler, Welc, Humer, and Jordan2016Ap and Rohou2017Qunaibit, Brunthaler, Na, Volckaert, and Franz2018Pizlo2014]. The common idea is that deoptimization leads the control-flow back to less optimized code. Most modern just-in-time compilers rely on speculative compilation to generate code for a subset of the possible behaviors of a function. The drawback of speculation is that it does not scale well with very dynamic behavior, as the speculation applies indiscriminately. Another drawback of speculation is that deoptimization is costly, as the compiler needs to add and maintain safe-points which inhibit some optimizations.

OSR-in (i.e., using OSR to transition from a less to a more optimized version) was first described by Hölzle and Ungar [1994a] in their recompilation strategy. When a small function is invoked often, they rather recompile the caller and replace it using OSR-in. SELF, being an interactive system, was concerned with compilation pauses. Especially with splitting-based optimizations that could lead to an explosion of code size. Chambers and Ungar [1991] address this issue by identifying uncommon source-level control-flows and deferring their compilation. Suganuma, Yasue, and Nakatani [2003] describe the natural extension of this idea where the deferred compilation is implemented by means of OSR. The Jikes RVM extensively relied on OSR-in for profile-driven deferred compilation as described by Fink and Qian [2003]. Deferred compilation can be understood as a speculative optimization that assumes an unlikely source-level branch is not taken.

Several works discuss implementation challenges and ease of use with regards to OSR. Duboscq, Würthinger, Stadler, Wimmer, Simon, and Mössenböck [2013] present how deoptimization points and metadata are implemented in the Graal compiler IR. Lameed and Hendren [2013], Kedlaya, Robatmili, Cas caval, and Hardekopf [2014], D’Elia and Demetrescu [2016] provide frameworks for supporting OSR in LLVM.

Most compilers use an architecture, where OSR transitions are only possible between versions linked by one compilation step. A notable exception are Wimmer, Jovanovic, Eckstein, and Würthinger [2017] who present OSR from optimized to optimized code. The goal is to use an optimizing compiler as the baseline compiler. They note that it requires “a two-way matching of two scope descriptors describing the same abstract frame.” In terms of our definitions in the previous section, this corresponds to an origin and a target state, which are related through a corresponding source state.

On the other hand, the one-step architecture is sometimes further simplified by the optimizer having the same source and target language. For example Béra, Miranda, Denker, and Ducasse [2016] advocate a VM architecture that uses a bytecode-to-bytecode optimizer, or Essertel, Tahboub, and Rompf [2021] implement OSR as source-to-source transformation. Wang, Blackburn, Hosking, and Norrish [2018] argue for a common low-level code format for all optimization levels and a low-level virtual machine, the Mu micro VM [Wang, Lin, Blackburn, Norrish, and Hosking2015], to efficiently execute this code. OSR as a mechanism is provided by the virtual machine, e.g.,, by means of a swapstack primitive operation. A similar argument is made by Desharnais and Brunthaler [2021]. As a result OSR is trivial to implement on top of such an architecture, since all the implementation complexity has to be handled already by the lower layer. Note however, that such a one-language approach, while simplifying the implementation, does not simplify the creation of a correct mapping for undoing optimizations. The problem of keeping two versions’ execution states synchronized across optimization passes still applies. That’s why the assume model in this dissertation also makes this one-language simplifying assumption, because it aims to solve the problem of correct mappings in isolation.

Some dynamic languages go to great lengths to avoid introducing speculation and deoptimization at all [Belyakova, Chung, Gelinas, Nash, Tate, and Vitek2020].

JIT Correctness

Previous work has made in-roads in demystifying JIT compilation. Myreen [2010] presents a verified JIT compiler from a stack-based bytecode to x86. The work focuses on self-modifying code, which modern JITs typically do not use anymore. The reasons are that for security reasons memory cannot be writable and executable at the same time, plus invalidating instruction caches is an expensive operation. What is not covered by Myreen are compiler optimizations and any kind of speculation, deoptimization, or specialization.

Guo and Palsberg [2011] discussed the soundness of trace-based compilers. When optimizing a trace, the rest of the program is not known to the optimizer, so optimizations such as dead-store elimination are unsound: a store might seem useless in the trace itself, but actually impacts the semantics of the rest of the program. On the other hand, free variables of the trace can be considered constant for the entire trace.

D’Elia and Demetrescu [2018] present an LLVM extension with OSR exit and entry points, and their interaction with optimization passes. Béra et al. [2016] present a verifier for a bytecode-to-bytecode optimizer. By symbolically executing optimized and unoptimized code, they verify that the deoptimization metadata produced by their optimizer correctly maps the symbolic values of the former to the latter at all deoptimization points.

There is a rich literature on formalizing compiler optimizations. The CompCert project [Leroy and Blazy2008] for example implements many optimizations, and contains detailed proof arguments for a data-flow optimization used for constant folding that is similar to ours. In fact, sourir is close to CompCert’s RTL language but comes with versions and assumptions. There are formalizations for tracing compilers [Guo and Palsberg2011Dissegna, Logozzo, and Ranzato2014], but we are unaware of any other formalization effort for speculative optimizations in general.

2.4 Speculation in a Nutshell

This section introduces our IR and its design principles. We first present the structure of programs and the assume instruction. Then, the following subsections explain how sourir maintains multiple equivalent versions of the same function, each with a different set of assumptions to enable speculative optimizations. All concepts introduced in this and the next section are formalized in section 2.6.

     var n = nil
     readn
     array t [n ]

     var k =  0
     goto L1
L1   branch  k < n  L2 L3
L2   t [ k ] ← k
     k  ←  k +  1
     goto L1
L3   drop k
     stop

Figure 2.4:Example sourir code

Sourir is an untyped language with lexically scoped mutable variables and first-class functions. As an example the function in Figure 2.4 queries a number n from the user and initializes an array with values from 0 to n-1. By design, sourir is a cross between a compiler representation and a high-level language. We have equipped it with sufficient expressive power so that it is possible to write interesting programs in a style reminiscent of dynamic languages.2 The only features that are critical to our result are versions and assumptions. Versions are the counterpart of dynamically generated code fragments. Assumptions, represented by the assume instruction, support dynamic deoptimization of speculatively compiled code. The syntax of sourir instructions is shown in Figure 2.5.

Sourir supports defining a local variable, removing a variable from scope, variable assignment, creating arrays, array assignment, (unstructured) control flow, input and output, function calls and returns, assumptions, and terminating execution. Control-flow instructions take explicit labels, which are compiler-generated symbols but we sometimes give them meaningful names for clarity of exposition. Literals are integers, Booleans, and nil. Together with variables and function references, they form simple expressions. Finally, an expression is either a simple expression or an operation: array access, array length, or primitive operation (arithmetic, comparison, and logic operation). Expressions are not nested—this is common in intermediate representations such as A-normal form [Sabry and Felleisen1992]. We do allow bounded nesting in instructions for brevity.

i ::=                   instructions
   |  var x = e        variable declaration
   |  drop x            drop a variable from scope
   |  x ← e            assignment
   |  array x[e]        array allocation
   |  array x = [e∗]     array creation
   |  x[e1] ← e2         array assignment
   |  branch e L1L2     conditional branch
   |  goto L            unconditional branch
   |  printe             print
   |  readx             read
   |  call x = e(e∗)     function call
   |  returne           return
   |  assume e∗ else ξ ˜ξ∗ assume instruction
   |  stop              terminate execution


   e  ::=                  expression
       |  se               simple expression
       |  x[se]            array access
       |  length(se)        array length
       |  primop (se∗)      primitive operation

   se ::=                  simple expressions
       |  lit              literals
       |  F               function reference
       |  x               variables

   lit ::=                  literals
       |  ...,− 1,0,1,...   numbers
       |  nil | true | false others



  ξ˜   ::=   F.V.L VA           target and varmap
  ξ   ::=   F.V.L x VA         extra continuation
  VA  ::=   [x1 = e1,..,xn = en]  varmap
Figure 2.5:The syntax of sourir

A program P is a set of function declarations. The body of a function is a list of versions indexed by a version label, where each version is an instruction sequence. The first instruction sequence in the list (the active version) is executed when the function is called. F ranges over function names, V over version labels, and L over instruction labels. An absolute reference to an instruction is thus a triple F.V.L. Every instruction is labeled, but for brevity we omit unused labels.

Versions model the speculative optimizations performed by the compiler. The only instruction that explicitly references versions is assume. It has the form assume e else ξ ξ with a list of predicates (e) and deoptimization metadata ξ and ξ . When executed, assume evaluates its predicates; if they hold execution skips to the next instruction. Otherwise, deoptimization occurs according to the metadata. The format of ξ is F.V.L [x1 = e1,..,xn = en], which contains a target F.V.L and a varmap [x1 = e1,..,xn = en]. To deoptimize, a fresh environment for the target is created according to the varmap. Each expression ei is evaluated in the old environment and bound to xi in the new environment. The environment specified by ξ replaces the current one. Deoptimization might also need to create additional continuations, if assume occurs in an inlined function. In this case multiple ξ of the form F.V.L x [x1 = e1,..,xn = en] can be appended. Each one synthesizes a continuation with an environment constructed according to the varmap, a return target F.V.L, and the name x to hold the returned result—this situation and inlining are discussed in 2.5. The purpose of deoptimization metadata is twofold. First, it provides the necessary information for jumping to the target version. Second, its presence in the instruction stream allows the optimizer to keep the mapping between different versions up-to-date.

For simplicity, assumptions are modeled as guard expressions which are always checked at the point of the assume instructions. This is not a limitation and still allows us to have remote dependencies using a global dependency array to store their state. See section 2.7 for details.

Example

size ( x )
V o
|
|  assume  x  ⁄= nil else size.V b.L2 [ el = 32 , x =  x ]
|  var l = x [ 0 ]
|  return l ∗ 32
V b
|
L1 var el = 32
L2 branch x = nil L4 L3
L3 var l = x [ 0 ]
|  return l ∗ el
L4 return 0
Figure 2.6:Speculation on x

Consider the function  size in Figure 2.6 which computes the size of a vector x . In version V b, x is either nil or an array with its length stored at index 0. The optimized version V o expects that the input is never nil. Classical compiler optimizations can leverage this fact: unreachable code removal prunes the unused branch. Constant propagation replaces the use of el with its value and updates the varmap so that it restores the deleted variable upon deoptimization to the base version V b.

Deoptimization Invariants

show ( x )
V o
|
|  assume  x  =  42 else show.V b.L1  [ x = x ]
|  print 42
V w
|  assume  true else show.V b.L1  [ x = 42 ]
|
|  print x
V b
L1 print x
|
Figure 2.7:The version w violates the deoptimization invariant

A version is the unit of optimization and deoptimization. Thus we expect that each function will have one original version and possibly many optimized versions. Versions are constructed such that they preserve two crucial invariants: (1) version equivalence and (2) assumption transparency. By the first invariant all versions of a function are observationally equivalent. The second invariant ensures that even if the assumption predicates do hold, deoptimizing to the target should be correct. Thus one could execute an optimized version and its base in lockstep; at every assume the varmap provides a complete mapping from the new version to the base. This simulation relation between versions is our correctness argument. The transparency invariant allows us to add assumption predicates without fear of altering program semantics. Consider a function show in Figure 2.7, which prints its argument  x . Version V o respects both invariants: any value for x will result in the same behavior as the base version and deoptimizing is always possible. On the other hand, V w, which is equivalent because it will never deoptimize, violates the second invariant: if it were to deoptimize, the value of x would be set to 42, which is almost always incorrect. We present a formal treatment of the invariants and the correctness proofs in section 2.6.

Creating Fresh Versions

We expect that versions are chained. A compiler will create a new version, say V 1 , from an existing version V 0 by copying all instructions from the original version and chaining their

fun ()
V 2
|
L0 assume  true else fun .V 1 .L0  []
|  var x =  1
L1 assume  e else fun.V 1 .L1 [ x = x ]
L2 print x + 2
V 1
|
L0 var x =  1
L1 assume  e else fun.V 0 .L1 [ g = x ]
L2 assume  true else fun .V 0 .L2  [ g = x , h =  x +  1 ]
|  print x + 2
V 0
|
L0 var g =  1
L1 var h =  g +  1
L2 print h +  1
Figure 2.8:Chained assume instructions: Version 1 was created from 0, then optimized. Version 2 is a fresh copy of 1.

deoptimization targets. The latter is done by updating the target and varmap of assume instructions such that all targets refer to V 0 at the same label as the current instruction. As the new version starts out as a copy, the varmap is the identity function. For instance, if the target contains the variables x and y , then the varmap is [ x = x , z = z ]. Additional assume instructions can be added; assume instructions that bear no predicates (i.e.,, the predicate list is either empty or just tautologies) can be removed while preserving equivalence. As an example in Figure 2.8, the new version V 2 is a copy of V 1 ; the instruction at L0 was added, the instruction at L1 was updated, and the one at L2 was removed.

size ( x )
V dup
|
L1 assume  true else size.Vb.L1 [ x =  x ]
|  var el = 32
L2 assume  true else size.Vb.L2 [ el = el , x = x ]
|  branch x = nil L4 L3
L3 var l = x [ 0 ]
|  return l ∗ el
|
L4 return 0
 V b  
Figure 2.9:A fresh copy of the base version of size

Updating assume instructions is not required for correctness. But the idea behind a new version is that it captures a set of assumptions that can be undone independently from the previously existing assumptions. Thus, we want to be able to undo one version at a time. In an implementation, versions might, for example, correspond to optimization tiers.3 This approach can lead to a cascade of deoptimizations if an inherited assumption fails; we discuss this in 2.5. In the following sections we use the base version V b of Figure 2.6 as our running example. As a first step, we generate the new version V dup with two fresh assume instructions shown in Figure 2.9. Initially the predicates are true and the assume instructions never fire. Version V b stays unchanged.

Injecting Assumptions

We advocate an approach where the compiler first injects assumption predicates, and then uses them for optimizations. In contrast, earlier work would apply an unsound optimization and then recover by adding a guard (see, for example, Duboscq et al. [2013]). While the end result is the same, the different perspective helps with reasoning about correctness. Assumptions are Boolean predicates, similar to user-provided assertions. For example, to speculate on a branch target, the assumption is the branch condition or its negation. It is therefore correct for the compiler to expect that the predicate holds immediately following an assume. Injecting predicates is done after establishing the correspondence between two versions with assume instructions, as presented above. Inserting a fresh assume into a function is difficult in general, as one must determine where to transfer control to or how to reconstruct the target environment. On the other hand, it is always correct to add a predicate to an existing assume . Thanks to the assumption transparency invariant it is always safe to deoptimize more often. For instance, in assume   x nil, x > 10  else  the predicate x nil was narrowed down to x > 10 .

2.5 Optimizations

In the previous section we introduced our approach for establishing a fresh version of a function that lends itself to speculative optimizations. Next, we introduce classical compiler optimizations that are exemplary of our approach. Then we give additional transformations for the assume instruction and conclude with a case study. All transformations introduced in this section are proved correct in section 2.6.

Constant Propagation

Consider a simple constant propagation pass that finds constant variables and then updates all uses. This pass maintains a map from variable names to constant expressions or unknown. The map is computed for every position in the instruction stream using a data-flow analysis. Following the approach by Kildall [1973], the analysis has an update function to add and remove constants to the map. For example analyzing var   x = 2 or x 2 adds the mapping x 2. The instruction var  y = x + 1 adds y 3 to the previous map. Finally, drop  x removes a mapping. Control-flow merges rely on a join function for intersecting two maps; mappings which agree are preserved, while others are set to unknown. In a second step, expressions that can be evaluated to values are replaced and unused variables are removed. No additional care needs to be taken to make this pass correct in the presence of assumptions. This is because in sourir, the expressions needed to reconstruct environments appear in the varmap of the assume and are thus visible to the constant propagation pass. Additionally, the pass can update them, for example, in assume  true else F .V .L [ x = y + z ], the variables y and z are treated the same as in call  h = foo ( y + z ). They can be replaced and will not artificially keep constant variables alive.

Constant propagation can become speculative. After the instruction assume  x = 0  else , the variable x is 0. Therefore, x 0 is added to the state map. This is the only extension required for speculative constant propagation. As an example, in the case where we speculate on a nil check

     ...
L2   assume  x ⁄= nil else size.Vb.L2 [ el = el , x = x ]

     branch x =  nil L4 L3
     ...

the map is x →¬nil after L2 . Evaluating the branch condition under this context yields ¬nil == nil, and a further optimization opportunity presents itself.

Unreachable Code Elimination

size ( x )
V pruned
|
L1 assume  true else size.Vb.L1 [ x =  x ]
|  var el = 32
L2 assume  x  ⁄= nil else size.V b.L2 [ el = el , x = x ]
|  var l = x [ 0 ]
|  return l ∗ el
 V b  
Figure 2.10:A speculation that the argument is not nil

As shown above, an assumption coupled with constant folding leads to branches becoming deterministic. Unreachable code elimination benefits from that. We consider a two step algorithm: the first pass replaces branch e  L1 L2 with goto L1 if e is a tautology and with goto L2 if it is a contradiction. The second pass removes unreachable instructions. In our running example from Figure 2.9, we add the predicate x nil to the empty assume at L2 . Constant propagation shows that the branch always goes to L3 , and unreachable code elimination removes the dead statement at L4 and branch. This creates the version shown in Figure 2.10. Additionally, constant propagation can replace el by 32. By also replacing its mention in the varmap of the assume at L2 , el becomes unused and can be removed from the optimized version. This yields version V o in Figure 2.6 at the top.

Function Inlining

main()
V inl
|
array  pl = [ 1 , 2 , 3 , 4 ]
array  vec = [length( pl ), pl ]
var s = nil
var x =  vec
assume  x ⁄= nil else  size.Vb.L2 [ el = 32 , x =  x ]
|                   main.V b.Lret s [ pl = pl , vec = vec ]
var l =  x [ 0 ]
|s ←  l ∗ 32
|
drop l
drop x
print s
stop
V b
|
|   array  pl = [ 1 , 2 , 3 , 4 ]
|   array  vec  = [length( pl ), pl ]
|   call s =  size (vec)
Lretprint s
|   stop
|
size ( x )
V o
|
L2  assume  x ⁄= nil else size.V b.L2 [ el = 32 , x = x ]
|   var l =  x [ 0 ]
|   return l ∗ 32
 V b  
Figure 2.11:An inlining of size into a main

Function inlining is our most involved optimization, since assume instructions inherited from the inlinee need to remain correct. The inlining itself is standard. Name mangling is used to separate the caller and callee environments. As an example Figure 2.11 shows the inlining of size into a function main. Naïvely inlining without updating the metadata of the assume at L2 will result in an incorrect deoptimization, as execution would transfer to size.V b.L2 with no way to return to the main function. Also, main’s part of the environment is discarded in the transfer and permanently lost. The solution is to synthesize a new stack frame. As shown in the figure, the assume at in the optimized main is thus extended with main .V b.Lret   s  [ pl = pl , vec = vec ].This creates an additional stack frame that returns to the base version of main, and stores the result in s with the entire caller portion of the environment reconstructed. It is always possible to compute the continuation, since the original call site must have a label and the scope at this label is known. Overall, after deoptimization, it appears as if version V b of main had called version V b of size . Note, it would be erroneous to create a continuation that returns to the optimized version of the caller V inl . If deoptimization from the inlined code occurs, it is precisely because some of its assumptions are invalid. Multiple continuations can be appended for further levels of inlining. The inlining needs to be applied bottom up: for the next level of inlining, e.g.,, to inline V inl into an outer caller, renamings must also be applied to the expressions in the extra continuations, since they refer to local variables in V inl .

Unrestricted Deoptimization

The assume instructions are expensive: they create dependencies on live variables and are barriers for moving instructions. Hoisting a side-effecting instruction over an assume is invalid, because if we deoptimize the effect happens twice. Removing a local variable is also not possible if its value is needed to reconstruct the target environment. Thus it makes sense to insert as few assume instructions as possible. On the other hand it is desirable to be able to “deoptimize everywhere”—checking assumptions in the basic block in which they are used can avoid unnecessary deoptimization—so there is a tension between speculation and optimization. Reaching an assume marks a stable state in the execution of the program that we can fall back to, similar to a transaction. Implementations like the one by Duboscq et al. [2013] separate deoptimization points and the associated guards into two separate instructions to be able to deoptimize more freely. As long as the effects of instructions performed since the last deoptimization point are not observable, it is valid to throw away intermediate results and resume control from there. Effectively, in sourir this corresponds to moving an assume instruction forward in the instruction stream, while keeping its deoptimization target fixed.

An assume can be moved over another instruction if that instruction:

  1. has no side-effects and is not a call instruction,
  2. does not interfere with the varmap or predicates, and
  3. has the assume as its only predecessor instruction.

The first condition prevents side-effects from happening twice. The second condition can be enabled by copying the affected variables at the original assume instruction location (i.e.,, taking a snapshot of the required part of the environment).4 The last condition prevents capturing traces incoming from other basic blocks where (1) and (2) do not hold for all intermediate instructions since the original location. This is not the weakest condition, but a reasonable, sufficient one.

size ( x )
V any
|  assume  true else size.Vb.L1 [ x =  x ]
|  var el = 32
|
|  branch x = nil L4 L3
L3 x  ←  x [ 0 ]
|  return x ∗ el
L4 ...
 V b  

Figure 2.12:Snippet with empty assume and a branch
size ( x )
V any
|  var x0 =  x
|  var el = 32
|
|  branch x = nil L4 L3
L4 x  ←  x [ 0 ]
|  assume  x  =  1 else size.Vb.L1  [ x = x0 ]
|  return 1 ∗ el
L3 ...
 V b  

Figure 2.13:Moving an assume from Figure 2.12 forward in the instruction stream

Let us consider a modified version of our running example in Figure 2.12. Again, we have an assume before the branch. However, now we would like to place a guard only inside one of the branches. There is an interfering instruction at L4 that modifies x . By creating a temporary variable to hold the value of x at the original assume location, so it is possible to resolve the interference. As shown in Figure 2.13 the assume can now move inside the branch and a predicate can be added on the updated x . Note that the target is unchanged. This approach allows for the (logical) separation between the deoptimization point and the position of assumption predicates. In the transformed example a stable deoptimization point is established at the beginning of the function by storing the value of x , but then the assumption is checked only in one branch. The intermediate states are ephemeral and can be safely discarded when deoptimizing. For example the variable el is not mentioned in the varmap here, so it is not captured by the assume. Instead it is recomputed by the original code at the deoptimization target size.V b.L1 . To be able to deoptimize from any position it is sufficient to have an assume after every side-effecting instruction, call, and control-flow merge.

Predicate Hoisting

Moving an assume backwards in the code would require replaying the moved-over instructions in the case of deoptimization. Hoisting assume  true else  size.V b.L2  [ el = el ,] above var  el = 32 is allowed if the varmap is changed to [ el = 32 ,] to compensate for the lost definition. However this approach is tricky and does not work for instructions with multiple predecessors as it could lead to conflicting compensation code. But a simple alternative to hoisting assume is to hoist a predicate from one assume to a previous one. To understand why, let us decompose the approach into two steps. Given an assume at L1 that dominates a second one at L2 , we copy a predicate from the latter to the former. This is valid because the assumption transparency invariant allows strengthening predicates. A data-flow analysis can determine if the copied predicate from L1 is available at L2 , in which case it can be removed from the original instruction. In our running example, version V pruned in Figure 2.10 has two assume instructions and one predicate. It is trivial to hoist x nil, since there are no interfering instructions. This allows us to remove the assume with the larger scope. More interestingly, in the case of a loop-invariant assumption, predicates can be hoisted out of the loop.

Assume Composition

As we have argued in 2.4, it is beneficial to undo as few assumptions as possible. On the other hand, deoptimizing an assumption added in an early version cascades through all the later versions. To be able to remove chained assume instructions, we show that assumptions are composable. If an assume in version V 3 transfers control to a target V 2 .La that is itself an assumption with V 1 .Lb as target, then we can combine the metadata to take both steps at once. By the assumption transparency invariant, the pre- and post-deoptimization states are equivalent: even if the assumptions are not the same, it is correct to conservatively trigger the second deoptimization. For example, consider the instruction assume e else F .V 2 .La  [ x = 1 ] that jumps to assume e else F .V 0 .Lb  [ y = x ]. They can be combined into assume e,e else F .V 0 .Lb  [ y = 1 ]. This new unified assume skips the intermediate version V 2 and goes to V 0 directly. This could be an interesting approach for multi-tier JITs: after the system stabilizes, intermediate versions are rarely used and may be discarded.

Case Study

div ( tagx , x , tagy , y )
V base
|
L1   branch tagx ⁄=  NUM    Lslow L2
L2   branch tagy ⁄=  NUM    Lslow L3
L3   branch x  = 0   LerrorL4
L4   return y ∕ x
Lslow ...

(a)
 
assume  tagx = NUM , tagy = NUM  else div.V b.L1  []
branch  x = 0   LerrorL4
L4
return y x

(b)
 
assume  tagx = NUM , x 0  else div.V b.L1  []
branch  tagy NUM   LslowL4
L4
return y x

(c)
 
assume  tagx = NUM , tagy = NUM , x 0  else div.V b.L1  []
return y x

(d)
Figure 2.14:Case study

We conclude with an example. In dynamic languages code is often dispatched on runtime types. If types were known, code could be specialized, resulting in faster code with fewer checks and branches. Consider Figure 2.14(a) which implements a generic binary division function that expects two values and their type tags. No static information is available; the arguments could be any type. Therefore, multiple checks are needed before the division; for example the slow branch will require even more checks on the exact value of the type tag. Suppose there is profiling information that indicates numbers can be expected. The function is specialized by speculatively pruning the branches as shown in Figure 2.14(b). In certain cases, sourir’s transformations can make it appear as though checks have been reordered. Consider a variation of the previous example, that speculates on x , but not y as shown in Figure 2.14(c). In this version, both checks on x are performed first and then the ones on y , whereas in the unoptimized version they are interleaved. By ruling out an exception early, it is possible to perform the checks in a more efficient order. The fully speculated-on version contains only the integer division and the required assumptions (Figure 2.14(d)). This version has no more branches and is a candidate for inlining.

Limitations

A limitation of the assume model is that the varmap contains only silent expressions. Implementations may try to defer some instructions to occur only when deoptimizing. As an example consider an optimization to elide array allocation, e.g., rewriting the definition ‘array  x = [ 3 ]’ to ‘var  x = 3 ’. If x was captured by an assume instruction, then deoptimization would have to be able to convert the scalar 3 into a singleton array, which is not possible with an expressions. For this reason Ř allows for arbitrary instructions to be deferred and only executed when a guard fails.

Further, unrestricted deoptimization as shown above requires moving the assume instruction and therefore prevents speculation at its original location. Also, before inlining we need to preserve a copy of the current caller version. Both of these limitations are overcome by Barrière et al. [2021].

2.6 Assume Formalized

A sourir program contains several functions, each of which can have multiple versions. This high-level structure is described in Figure 2.15. The first version is considered the currently active version and will be executed by a call instruction. Each version consists of a stream of labeled instructions. We use an indentation-based syntax that directly reflects this structure and omit unreferenced instruction labels.

P
::=

   ∗
F(x )
 V|
  |L  i

indentation-based syntax

P
::=
F(x) : DF,...
a program is a list of named functions
DF
::=
V : I,...
a function is a list of instruction streams
I
::=
L : i,...
an instruction stream with labeled instructions

Figure 2.15:Program syntax

Besides grammatical and scoping validity, we impose the following well-formedness requirements to ease analysis and reasoning. We require all guard expressions e in assume e else ξ ξ to be statically known to produce a value. In practice this is not a limitation since partial functions can be extended to evaluate to false. The last instruction of each version of the main function is stop. Two variable declarations for the same name cannot occur in the same instruction stream. This simplifies reasoning by letting us use variable names to unambiguously track information depending on the declaration site. Different versions have separate scopes and can have names in common. If a function reference F is used, that function F must exist. Origin and target of control-flow transitions must have the same set of declared variables. This eases determining the environment at any point. To jump to a label L, all variables not in scope at L must be dropped (drop  x ).

Operational Semantics

Expressions

Figure 2.16

and

Figure 2.17

give the semantics of expressions. Evaluation e returns a value v, which may be a literal lit, a function, or an address a. Arrays are represented by addresses into heap M. The heap is a map from addresses to blocks of values [v

1

,

..

,v

n

]. An environment E is a mapping from variables to values. Evaluation is defined by a relation M E e v: under M and environment E, e evaluates to v. This definition in turn relies on a relation E se v defining evaluation of simple expressions se, which does not access arrays. The notation [[primop]] to denote, for each primitive operation primop, a partial function on values. Arithmetic operators and arithmetic comparison operators are only defined when their arguments are numbers. Equality and inequality are defined for all values. The relation M E e v, when seen as a function from M, E, e to v, is partial: it is not defined on all inputs. For example, there is no v such that the relation M E  x [se] v holds if E( x ) is not an address a, if a is not bound in M, if se does not reduce to a number n, or if n is out of bounds.

v ::=     values
   |  lit             addr ::= a             addresses
   |  F              M  ::= (a → [v1,..,vn])∗  heap
   |  a              E ::= ( x → v)∗        environment

[Literal]
 
E--lit ⇀-lit
[Funref]
 
E-F-⇀-F--
[Lookup]
 
E--x ⇀-E(x)

[SimpleExp]
 
E se ⇀ v
M--E-se →-v
[Primop]
 
E--se1-⇀-v1--..--E-sen-⇀-vn----------------
M  E primop(se1,..,sen) → [[primop ]](v1,..,vn)
Figure 2.16:Evaluation M  E e → v  of expressions

[VecLen]
 
E--se-⇀-a--M-(a) =-[v1,..,vn]
     M E length(se) → n
[VecAccess]
 
a d=efE (x) M (a) = [v0,..,vm ]
E--se-⇀-n--0-≤-n-≤-m--------
       M E  x[se] → vn
Figure 2.17:Evaluation E se ⇀ v  of simple expressions

Instructions and Programs

We define a small-step, labeled operational semantics with a notion of machine state, or configuration, that represents the dynamic state of a program being executed, and a transition relation between configurations. A configuration is a six-component tuple P

I

L

K

M

Edescribed in

Figure 2.18

. Continuations K are tuples of the form I L x E, storing the information needed to correctly return to a caller function. On a call call   x = e(e

1

,

..

,e

n

), the continuation pushed on the stack contains the current instruction stream I (to be restored on return), the label L of the next instruction after the call (the return label), the variable x to name the returned result, and environment E. For details, see the reduction rules for call and return in

Figure 2.20

.

                   (
                      P                   program
                   ||  I                   instructions
C ::= ⟨PILK ∗M E⟩   ||  L                   next label
   configuration      ||  K∗  ::=   (K1, ..,Kn )  call stack
                   (  M                   heap
                      E                   environment
                   (
                      I      code of calling function
K ::= ⟨I L x E⟩     ||  L      return label
 continuation       (  x      return variable
                      E      environment at call site
Figure 2.18:Abstract machine state

A  ::=          I/O action
    |  print lit                 T  ::=       action trace
    |  read lit                     |        (empty trace)
    |  stop                        |  A
                                   |  Aτ
Aτ ::=                              |  T A
    |  A                           |  T Aτ
    |  τ       silent label

[Refl]
 
---------
C  −→ ∗ C
[SilentCons]
 
   T           τ
C--−→-∗ C-′-C-′−→-C-′′-
      C −T→∗ C′′
[ActionCons]
 
   T  ∗  ′   ′ A   ′′
C--−→--C---C--−→-C---
      C T− A→∗ C′′
Figure 2.19:Actions and traces

The relation C−Aτ→C specifies that executing the next instruction may result in the configuration C. The action Aτ indicates whether this reduction is observable: it is either the silent action, written τ, an I/O action read lit or print lit, or stop. We write C−T→ ∗ C when there are zero or more steps from C to C. The trace T is a list of non-silent actions in the order in which they appeared. Actions are defined in Figure 2.19, and the full reduction relation is given in Figure 2.20.

                                        [Decl ]
         -I(L-) =-var-x =-e-M--E-e →-v----------
         ⟨PI LK ∗M E⟩−τ→ ⟨PI(L+1 )K∗M E [x ← v]⟩

                                       [Drop ]

          -I(L) =-drop-xτ---------------------
          ⟨PI LK ∗M E⟩− → ⟨PI(L+1 )K∗M E ∖{x}⟩


                                           [ArrayDef ]
  I(L ) = array x = [e1,..,en] M E e1 → v1 .. M  E en → vn
  a ∕∈ dom (M ) M ′ d=efM [a ← [v ,..,v ]]
---------------------τ-----1----n---------------------
        ⟨PILK ∗M E⟩ −→ ⟨PI(L +1)K ∗M ′E[x ←  a]⟩

                                   [ArrayDecl  ]
         I(L) = array x[e] M E e → n
         a∈∕dom (M ) M ′ d=efM [a ← [nil1,..,niln]]
        ------∗------τ------------∗-′----------
        ⟨PILK  M E⟩ −→ ⟨PI(L +1)K M  E[x ←  a]⟩


                                      [Update ]
        -I(L)-=-x-←-eτ--x-∈-dom(E)--M--E-e →-v
         ⟨PI LK ∗M E⟩− → ⟨PI(L+1 )K∗M E [x ← v]⟩

                                      [ArrayUpdate  ]
             ′        def            ′
   I(L) = x[e] ← e  a = E (x) M  E e → n  M  E e → v
   M (ad)ef = [v0,..,vm] 0 ≤ n ≤ m
  -M-′=-M-[a-←-[v0,..,vm]{vn∕v}]-----------------------
           ⟨PILK  ∗M E ⟩−τ→  ⟨PI (L+1 )K ∗M ′E⟩


                                          [Read ]
         I(L) = readx
        ------------read lit----------------------
        ⟨PILK  ∗M E ⟩ −→  ⟨PI(L +1)K ∗M E[x ← lit]⟩

                                [Print]
      -I(L) =-printe--M--E-e →-lit--------
            ∗    print lit         ∗
      ⟨PI LK  M E⟩ − →  ⟨PI(L+1 )K M E ⟩


                              [BranchT  ]
     -I(L) =-branch-e-L1L2--M--E-e →-true-
        ⟨PILK ∗M E ⟩−τ→  ⟨PI L1K ∗M E⟩

                              [BranchF  ]
      I(L) = branch e L1L2  M  E e → false
     ---------∗------τ---------∗--------
        ⟨PILK  M E ⟩−→  ⟨PI L2K  M E⟩


                              [Goto ]
        --I(L-) =-goto-L′-------------
        ⟨PI LK ∗ME ⟩−τ→  ⟨PIL′K ∗M E ⟩


                              [Stop ]
          I(L) = stop
         ------------stop------------
         ⟨PI LK ∗M E⟩ −→ ⟨P𝜀LK ∗M E ⟩


                                      [Call]
  I(L ) = call x = e(e1,..,en)
  M E e → F
  P(F) = F(x1,..,xn) : DF I′ d=efP(F,active)
   ′ def     ′                          ′
 -L-=-start(I)τ-M-E[x1 =-e1,..,xn =-en] ⇝-E----
 ⟨PI LK ∗M E⟩−→  ⟨PI′L′(K ∗,⟨I (L+1 ) x E⟩)M E′⟩

                                      [Return ]
-I(L) =-returne-M--E-e-→-v----------------------
       ∗  ′  ′   ′       τ    ′ ′  ∗   ′
⟨PI L(K  ,⟨I L  x E ⟩)M E⟩ −→ ⟨PI L K M E [x ← v]⟩

                                    [AssumePass ]
      -I(L) =-assume-e∗-else ξ-˜ξ∗-∀m,-M-E-em-→-true-
                  ∗     τ            ∗
            ⟨PI LK  M E⟩− → ⟨PI(L+1 )K M E ⟩
                                    [AssumeDeopt  ]
                    ∗      ˜∗
    --I(L-) =-assume-eτ-else-ξξ---¬(∀m,-M-E-em-→--true)
      ⟨PI LK ∗M E⟩−→  deoptimize(⟨PILK ∗M E ⟩,ξ, ˜ξ∗)


                                                [DeoptimizeConf ]
            ′  ′ def  ′  ′
 M EVA  ⇝ E   I =  P(F ,V )
 ∀q∈ 1˜,..,r,
     ξq = Fq.Vq.Lq xq VAqdef          def
-----M-EVAq--⇝-Eq--Iq=--P(Fq,Vq)-Kq--=-⟨Iq-Lq-xq-Eq⟩---------------
deoptimize(⟨PILK  ∗M E ⟩,F ′.V′.L′ VA, ˜ξ1,..,ξ ˜r) de=f⟨PI′L′(K ∗,K1,..,Kr)M E′⟩

                                       [EvalEnv ]
         M  E e1 → v1 .. M  E en → vn
        M-E-[x-=-e-,..,x-=-e-] ⇝-[x--→-v-,..,x--→-v-]
             1   1    n   n     1    1   n    n
Figure 2.20:Reduction relation    τ    ′
C −→  C (incl. previous 2 pages)

Most rules get the current instruction, I(L), perform an operation, and advance to the next label, referred to by the shorthand (L+1 )  . The read lit and print lit actions represent observable I/O operations. They are emitted by Read and Print in Figure 2.20. The action read lit on the read x transition may be any literal value. This is the only reduction rule that is non-deterministic. Note that the relation C−→ ∗ C, containing only sequences of silent reductions, is deterministic.

The stop reduction emits the stop transition, and also produces a configuration with no instructions, 𝜀. This is a technical device to ensure that the resulting configuration does not reduce further. A program with a silent loop has a different trace from a program that halts.

                       [StartConf  ]

    -I-d=efP-(main,active)-L-d=efstart(I)
          start(P) de=f⟨PIL∅∅∅⟩

             def                   T
reachable(P ) =  {C | ∃T , start(P) −→ ∗ C }
Given a program P, let start(P) be its starting configuration, and reachable (P) be the set of configurations reachable from it; they are all the states that may be encountered during a valid run of P.

Equivalence of Configurations: Bisimulation

We use weak bisimulation to prove equivalence between configurations. The idea is to define, for each program transformation, a correspondence relation R between configurations over the original and transformed programs. We show that related configurations have the same observable behavior, and reducing them results in configurations that are themselves related. Two programs are equivalent if their starting configurations are related.

Definition 1 (Weak Bisimulation). Given programs P1 and P2 and relation R between the configurations of P1 and P2, R is a weak simulation if for any related states (C1,C2) R and any reduction C1−Aτ→C1 over P1, there exists a reduction C2−A→τ∗ C2 over P2 such that (C1,C2) are themselves related by R. Reduction over P2 is allowed to take zero or more steps, but not to change the trace. In other words, the diagram on the left below can always be completed into the diagram on the right. PIC R is a weak bisimulation if it is a weak simulation and the symmetric relation R1 also is—a reduction from C2 can be matched by C1. Finally, two configurations are weakly bisimilar if there exists a weak bisimulation R that relates them.

In the remainder, the adjective weak is always implied. The following result is standard, and essential to compose the correctness proof of subsequent transformation passes.

Lemma 1 (Transitivity). If R12 is a weak bisimulation between P1 and P2, and R23 is a weak bisimulation between P2 and P3 , then the composed relation R13 d=ef (R12;R23) is a weak bisimulation between P1 and P3.

Definition 2 (Version bisimilarity). Let V1, V2 be two versions of a function F in P, and let I1 def
= P(F,V1) and I2 def
 = P(F,V2). V1 and V2 are weakly bisimilar if the configurations PI1start(I1)KMEand PI2start(I2)KMEare weakly bisimilar for all K, M, E.

Definition 3 (Equivalence). P1, P2 are equivalent if start(P1), start (P2) are weakly bisimilar.

Deoptimization Invariants

We can now give a formal definition of the invariants from 2.4: Version Equivalence holds if any pair of versions (V1,V2) of a function F are bisimilar; Assumption Transparency holds if for any configuration C, at an assume e else ξ ξ, C, is bisimilar to deoptimize(C,ξ,ξ), as defined in Figure 2.20, DeoptimizeConf.

Creating Fresh Versions and Injecting Assumptions

Configuration C is over location F.V.L if it is PP(F,V)LKME. Let C[F.V.L F .V .L] be PP(F,V)LKME. More generally, C[X Y ] replaces various components of C. For example, C[P1 P2] updates the program in C; if only the versions change between two locations F.V.L and F.V .L, write C[V V] instead of repeating the locations, etc.

Theorem 1. Creating a new copy of the currently active version of a function, possibly adding empty assume instructions, returns an equivalent program.

Proof. Consider P1 with a function F with active version V1. Adding a version yields P2 with new active version V2 of F such that

Let us write I1 and I2 for the instructions of V1 and V2 respectively. Stack K2 is a replacement of K1 if it is obtained from K1 by replacing continuations of the form I1 L x Eby I2 L x E. Replacement is a device used in the proof and does not correspond to any of the reduction rules. We define a relation R as the smallest relation such that :

  1. For any configuration C1 over P1, R relates C1 to C1 [P1 P2].
  2. For any configuration C1 over a F.V1 .L such that L in V2 is not an added assume, R relates C1 to C1 [P1 P2][V1 V2].
  3. For any configuration C1 over a F.V1 .L such that at L in V2 is a newly added assume followed by label L, R relates C1 to both (a) C1[F.V1 .L F.V2 .L] and (b) C1 [F.V1 .L F.V2 .L].
  4. For any related pair (C1,C2) R, where K1 is the call stack of C2, for any replacement K2, the pair (C1,C2[K1 K2]) is in R.

The proof proceeds by showing that R is a bisimulation. If a related pair (C1,C2) R comes from the cases (1), (2) or (3) of the definition of R, we say that it is a base pair. A pair (C1,C2) in case (4) is defined from another pair (C1,C2) R, such that the call stack of C2 is a replacement of the stack of C2. If (C1,C2) R is a base pair, we say that it is the base pair of (C1,C2). Otherwise, we say that the base pair of (C1,C2) is the base pair of (C1,C2).

Bisimulation proof: generalities To prove that R is a bisimulation, consider all related pairs (C1,C2) R and show that a reduction from C1 can be matched by C2 and conversely. Without loss of generality, assume that C2 is not a newly added assume instruction – that the base pair of (C1,C2) is not in the case (3,b) of the definition of R. Indeed, the proof of the case (3,b) follows from proof of the case (3,a). In the case (3,b), C2 is a newly added assume instruction assume true else  at L followed by L . C2 can only reduce silently into C2 d=ef C2[L L], which is related to C1 by the case (3,a). The empty reduction sequence from C1 matches this reduction from C2. Conversely, assume the result in the case (3,a), then any reduction of C1 can be matched from C2, and thus matched from C2 by prepending the silent reduction C2−τ→C2 to the matching reduction sequence. Finally, if (C1,C2) comes from case (4) and has a base pair (C1,C2) from (3,b), and C2 has label L followed by L, then the bisimulation property for (C1,C2) R comes from the one of (C1,C2[L L]) R by the same reasoning. Bisimulation proof: easy cases The easy cases of the proof are the reductions C1 Aτ
−→C1 where neither C1 nor C1 are over V1, and the reductions C2A τ
−→C2 where neither C2 nor C2 are over V2. For C1 Aτ
−→C1, define C2 as C1[P1 P2], and both C2 Aτ
−→ C2 and (C1,C2) R hold. The C2 Aτ
−→ C2 case is symmetric, defining C1 as C2 [P2 P1]. Bisimulation proof: harder cases The harder cases are split in two categories: version-change reductions (deoptimizations, functions call and returns), and same-version reductions within V1 in P1 or V2 in P2 respectively.

We consider same-version reductions first. Without loss of generality, assume that the pair (C1,C2) R is a base pair, that is a pair related by the cases (2) or (3) of the definition of R, but not (4) – the case that changes the call stack of the configuration. Indeed, if pair (C1,C2) R comes from (4), the only difference between this pair and its base pair (C1,C2) R is in the call stack of C2 and C2. This means that C2 and C2 have the exact same reduction behavior for non-version-change reductions. As long as the proof that the related configurations C1 and C2 match each other does not use version-change reductions (a property that holds for the proofs of the non-version-change cases below), it also applies to C1 and C2. For a reduction C2Aτ
−→ C2 that is not a version-change reduction (deoptimization, call or return), prove that it can be matched from C1 by distinguishing whether C2 or C2 are assume instructions, coming from V1 or newly added.

The reasoning for transitions C1 Aτ
− →C1 that have to be matched from C2 and are not version-change transitions (deoptimization, function calls or return) is similar. C2 cannot be a new assume, so we have C2 Aτ
− →C2, and either C2 is not a new assume and matches C1 by case (2) of the definition of R, or it is a new assume and it matches it by the case (3,a).

Bisimulation proof: final cases The cases that remain are the hard cases of version-change reductions: function call, return and deoptimization. If C1A τ
−→C1 is a deoptimization reduction, then C1 is over a location F.V1 .L in P1, and its instruction is assume e else ξ ξ, and C1 is deoptimize(C1,ξ,ξ). C2 is over the copied instruction assume e else F.V1 .L Id and Id is the identity. C2 also deoptimizes, given that the tests yield the same results in the same environment, so we have C2 τ
−→ C2 for C2 de=f deoptimize (C2,F.V.L1 Id,). C2 is over F.V1 .L, that is the same assume instruction as C1, so it also deoptimizes, to C′′2 def
= deoptimize (C2,ξ,ξ). We show that C1 and C′′2 are related by R:

Conversely, if C2−A→τC2 is a deoptimization instruction then, by the same reasoning as in the proof of matching a deoptimization of C1, C2 is identical to C1 (modulo replaced stacks). This means that the empty reduction sequence from C1 matches the reduction of C2 .

If C1A τ
−→C1 is a function call transition,

P1I1LK1ME  τ
− →P 1I1L(K,I 1 (L+1)  x  E)ME

C2 is on the same call with the same arguments, so it takes a transition C2−τ→C2 of the form

P2I2LK2ME  τ
− →P 2I2L(K,I 2 (L+1)  x  E)ME

The stack of C2 is a replacement of the stack of C1: assuming that K2 is a replacement of K1, the difference in the new continuation is precisely the definition of stack replacement — note that it is precisely this reasoning step that required the addition of case (4) in the definition of R. Also, the new instruction streams I1 and I2 are either identical (if the function is not F itself) or equal to I1 and I2 respectively, so we do have (C1,C2) R as expected. The proof of the symmetric case, matching a function call from C2, is identical.

If C1A−→τC1 is a function return transition

P1I1L(K,I 1 L x E)ME τ
−→P1I1LK1ME[x v]

then C2−Aτ→C2 is also a function return transition

P2I2L(K,I 2 L x E)ME−τ→P2I2LK2ME[x v]

We have to show that C1 and C2 are related by R. The environments and heaps of the two configurations are identical. We know that the stack of C2 is a replacement of the stack of C1, which means that K2 a replacement of K1, and that either I1 and I2 are identical or they are respectively equal to I1 and I2. In either case, C1 and C2 are related by R. The proof of the symmetric case, matching a function return from C2, is identical. We have established that R is a bisimulation.

Finally, remark that our choice of R also proves that the new version respects the assumption transparency invariant. A new assume at L in V2 is of the form assume true else F.V1 .L Id, with Id the identity environment. Any configuration C over F.V2 .L is related by R1 to C[F.V2 .L F.V1 .L], which is equal to the configuration deoptimize(C,F.V1 .L Id,). These two configurations are related by the bisimulation R1, so they are bisimilar. □

Lemma 2. Adding a new Boolean predicate e to an existing assume instruction assume e else ξ ξ of P1 returns an equivalent program P2.

Proof. This is a consequence of the invariant of assumption transparency. Let RP1 be the bisimilarity relation for configurations over P1, and F.V.L be the location of the modified assume. Let us define the relation R between P1 and P2 by

(C1,C2) R (C1,C2[P2 P1]) RP1

We show that R is a bisimulation. Consider (C1,C2) R. If C2 is not over F.V.L, the reductions of C2 (in P2) and C2 [P2 P1] (in P1) are identical, and the latter configuration is, by assumption, bisimilar to C1, so it is immediate that any reduction from C1 can be matched by C2 and conversely. If C2 is over F.V.L, we can compare its reduction behavior (in P2) with the one of C2[P2 P1] (in P1). The first configuration deoptimizes when one of the e,e is not true in the environment of C2, while the second deoptimizes when one of the e is not true — in the same environment. If C2 gives the same Boolean value to both series of test, then the two configurations have the same reduction behavior, and (C1,C2) match each other by the same reasoning as in the previous paragraph. The only interesting case is the configurations C2 that pass all the tests in e, but fail e. Let us show that, even in that case, the reductions of C1 and C2 match each other. The following diagram will be useful to follow the proof below: PICLet us first show that the reductions of C2 can be matched by C1. The only possible reduction from C2 , given our assumptions, is C2−τ→ deoptimize(C2,ξ,ξ). We claim that the empty reduction sequence from C1 matches it, that is, that (C1,deoptimize(C2,ξ,ξ)) R. By definition of R, this goal means that C1 and the configuration deoptimize(C2,ξ,ξ)[P2 P1] are bisimilar in P1. But the latter configuration is the same as in deoptimize (C2[P2 P1],ξ,ξ), which is bisimilar to C2 by the invariant of assumption transparency, and thus to C1 by transitivity. Conversely, we show that the reductions of C1 can be matched by C2. Suppose a reduction C1 Aτ
− → C1. deoptimize(C2,ξ,ξ)[P2 P1] is bisimilar to C1 (same reasoning as in the previous paragraph), so there is a matching state C′′1 such that deoptimize(C2,ξ,ξ)[P2 P1]A τ
−→ C′′1 in P1 with (C1,C′′1) RP1. We can transpose this reduction in P2: deoptimize(C2,ξ,ξ)−A→τC′′1[P1 P2] in P2, and thus C2  Aτ
−→ ∗ C′′1[P1 P2]. This matches the reduction of C1, given that our assumption (C1,C′′1) RP1 exactly means that (C1,C′′1[P1 P2]) R. □

Optimization Correctness

The proofs of the optimizations from section 2.5 are easier than the proofs for deoptimization invariants in the previous section (although, as program transformations, they seem more elaborate). This follows from the fact that the classical optimizations rewrite an existing version and interact little with deoptimization.

Constant Propagation

We say that given a version V, a static environment SE for label L maps a subset of the variables in scope at L to values. A static environment is valid, written SE L, if for any configuration C over L reachable from the start of V, SE is a subset of the lexical environment E. Constant propagation can use a classic work-queue data-flow algorithm to compute a valid static environment SE at each label L. It then replaces, in the instruction at L, each expression or simple expression that can be evaluated in SE by its value. This is speculative since assumption predicates of the form x = lit populate the static environment with the binding x lit.

Lemma 3. For any version V1, let V2 be the result of constant propagation. V1 and V2 are bisimilar.

Proof. The relation R to use here for bisimulation is the one that relates each reachable C1 in reachable(P1) to the corresponding state C2 def
= C1[V1 V2] in reachable(P2). Consider two related C1,C2 over L, and SE be the valid static environment at L inferred by our constant propagation algorithm. Reducing the next instruction of C1 and C2 will produce the same result, given that they only differ by substitutions of subexpressions by values that are valid under the static environment SE, and thus under E. If C1 Aτ
− → C1 then C2 Aτ
− →C2, and conversely. □

The restriction of our bisimulation R to reachable configurations introduced is crucial for the proof to work. Indeed, a configuration that is not reachable may not respect the static environment SE. Consider the following example, with V 1 on the left and V 2 on the right.

 L1  var x  = 1            L1  var x =  1
L2   print x + x          L2   print 2
     return 3                   return 3
Now consider a pair of configurations at L1 with the binding x 0 in the environment.
   def               ∗
C1  = ⟨PP (F,V1 )L2K  M [ x →  0 ]⟩

C2 de=f⟨PP (F,V2 )L2K ∗M [ x →  0 ]⟩
They would be related by the relation R used by the proof, yet they are not bisimilar: we have C

1

print 0
 −→

C

1

as the only transition of C

1

in V

1

, and C

2

pri−nt→ 2

C

2

as the only transition of C

2

in V

2

.
Unreachable Code Elimination

The following two lemmas are trivial: the simple version-change mapping between configurations on the two version is clearly a bisimulation. In the first case, this comes from the case that branch  true  L1L2 and goto L1 reduce in the example same way. In the second case, unreachable configurations are not even considered by the proof.

Lemma 4. Replacing branch true  L1L2 by goto L1 or branch false  L1L2 by goto L2 results in an equivalent program.

Lemma 5. Removing an unreachable label results in an equivalent program.

Function Inlining

Assume that the function F has active version V callee . If the new version contains a call to F, call  res = F(e1,..,en ) with return label Lret (the label after the call), inlining removes the call and instead:

Theorem 2. The inlining transformation presented returns a version equivalent to the caller version.

Proof. The key idea of the proof is that any environment E in the inlined instruction stream can be split into two disjoint parts: an environment corresponding to the caller function, Ecaller, and an environment corresponding to the callee, Ecallee. To build the bisimulation, we relate the inlined version, on one hand, with the callee on the other hand, when the callee was called by the caller at the inlined call point. This takes two forms:

To check that this relation is a bisimulation, there are three interesting cases:

Unrestricted Deoptimization

Consider P1 containing an assume at L1, followed by im at L2 def
= (L1+1). Let im be such it has a unique successor, is the unique predecessor of L1, and is not a function call, has no side-effect, does not modify the heap (array write or creation), and does not modify the variables mentioned in the assume. Under these conditions, we can move the assume immediately after the successor of im. Let us name P2 the program modified in this way.

Lemma 6. Given a program P1, and P2 obtained by permuting an assume instruction L1 after im at L2 under the conditions above, P1 and P2 are bisimilar.

Proof. The applicability restrictions are specific enough that we can reason precisely about the structure of reductions around the permuted instructions. Consider a configuration C1 over the assume at L1 in P1, and the corresponding configuration C2 def
= C1 [P1 P2][L1 L2] over L2 in P2. Instruction im has a single successor, so there is only one possible reduction rule. Since im is not an I/O instruction, it must be a silent action. Hence there is a unique C2 such that C2 Aτ
− →C2 holds, and furthermore Aτ is τ. Configurations C1 and C2 are over the same assume. Let E1 and E2 be environments of C1 and C2 respectively, and E be their common sub-environment that contain only the variables mentioned in the assume (im does not modify its variables). If all tests in the assume instruction are true under E, then C1 and C2 silently reduce to C1 and C′′2. C1 is over im at L2, so it reduces C1  τ
−→ C′′1; notice that C′′1 and C′′2 are over the labels (L2 +1) in P1 and (L1 +1) in P2, which are equal. If not all tests of the assume are true under E, then both C1 and C2 deoptimize. The deoptimized configurations are the same

Let us call C0 the configuration resulting from either deoptimization transitions.

We establish bisimilarity by defining a relation R and proving it is a bisimulation. The following diagrams are useful to follow the definition of R and the proofs. PIC

We define R as the smallest relation such that:

  1. For any C1 and C2 as above, C1 and C1 are related to C2 .
  2. For any C1 and C2 as above such that C1 passes the assume tests (does not deoptimize), both C2 and C′′2 are related to C′′1.
  3. For any C over P1 that is over neither L1 nor L2, the configurations C and C[P1 P2] are related.

We now prove that R is a bisimulation. Any pair of configurations that are not over either L1 or L2 come from the case (3), so they are identical and it is immediate that they match each other. The interesting cases are for matching pairs of configurations over L1 or L2 .

In the case where no deoptimization happens, the reductions in P2 are either C2−τ→C2, where both configurations are related to C1 , or C2 τ
−→ C′′2 which is matched by C1 τ
−→ C1. The reductions in P1 are either C1 τ
−→C1, which is matched by C2 − τ→ C2−τ→ C′′2 and C2− τ→C′′2, or C1−τ→C′′1, which are both related to C′′2.

In the case where a deoptimization happens, the only reduction in P1 is C1 τ
−→C0, which is matched by C2  τ
− →C2 τ
−→C0 and C2  τ
−→ C0. The reductions in P2 are C2 τ
−→C2, which are matched by the empty reduction on C1 and C2−τ→ C0 are matched by C1 τ
−→C0.

Finally, we show preservation of the assumption transparency invariant. We have to establish the invariant for P2, assuming the invariant for P2. We have to show that C0 and C2 are bisimilar. C0 is bisimilar to C1 (this is the transparency invariant on P1), and C1 and C2 are bisimilar because they are related by the bisimulation R. □

Predicate Hoisting

Hoisting predicates takes a version V1, an expression e, and two labels L1,L2, such that the instruction at L1,L2 are both assume instructions and e is a part of the predicate list at L1. The pass copies e from L1 to L2, if all variables mentioned in e are in scope at L2. If, after this step the e can be constant folded to true at L1 by the optimization from 2.5, then it is removed from L1, otherwise the whole version stays unchanged.

Lemma 7. Let V2 be the result of hoisting e from L1 to L2 in V1 . V1 and V2 are bisimilar.

Proof. Copying is bisimilar due to the assumption transparency invariant and to the fact that the constant-folded version is bisimilar due to Lemma 3. □

Assume Composition

Let V1,V2,V3 be three versions of a function F with instruction streams I1,I2,I3, and labels L1,L2,L3, such that there are two instructions I1(L1) = assume e1 else F.V2 .L2 VA1 and I2 (L2) = assume e2 else F.V3 .L3 VA2. The composition pass creates a new program P2 from P1 identical but the assume P2 (F.V1.L1) is replaced by assume e1,e2 else F.V3 .L3 VA2 VA1 where the composition ([x1 = e1,..,xn = en] VA) is defined as [x1 = e1{VA(y)
  yy VA},..,xn = en{VA(y)-
 yy VA}].

Lemma 8. Let P2 be the result of composing assume instructions at L1 and L2. P1 and P2 are bisimilar.

Proof. For C1−τ→ C1, C2−τ→ C2 over L1 in P1, P2, we distinguish four cases:

  1. If e1 and e2 both hold, the assume does not deoptimize in P1 and P2 and they behave identically.
  2. If e1 and e2 both fail, the original program deoptimizes twice; the modified P2 only once. Assuming deoptimizing under the combined varmap MEVA2 VA1 E′′ produces an environment equivalent to MEVA1 E and MEVA2 E′′ the final configuration is identical. Since the extra intermediate step is silent, both programs are bisimilar.
  3. If e1 fails and e2 holds, we deoptimize to V3 in P2 , but to V2 in P1. As shown in case (2) the deoptimized configuration C2 over L3 is equivalent to a post-deoptimization configuration of C1, which, due to assumption transparency is bisimilar to C1 itself.
  4. If e1 holds and e2 fails, deoptimize to V3 in P2 but not in P1. Again C2 is equivalent to a post-deoptimization state, which is, transitively, bisimilar to C1.

Since a well-formed assume has only unique names in the deoptimization metadata, it is simple to show the assumption in (2) with a substitution lemma. □

2.7 Discussion

Our formalization raises new questions and makes apparent certain design choices. In this section, we present insights into the design space for JIT implementations.

 Lloop
branch  z 0   LbodyLdone
Lbody
call  x = dostuff ()
var  y = x + 13
assume e elseF.V.L [ x = x , y = x + 13 ]
drop  y
goto Lloop
Ldone
Figure 2.21:Deoptimization keeps variables alive

The Cost of Assuming

Assumptions restrict optimizations. Variables needed for deoptimization must be kept alive. Consider

Figure 2.21

, where an assume is at the end of a loop. As y is not modified, it can be removed. There is enough information to reconstruct it if needed. On the other hand, x cannot be synthesized out of thin air because it is computed by another function. Additionally, assume restricts code motion in two cases. First, side-effecting code cannot be moved over an assume. Second, assume instructions cannot be hoisted over instructions that interfere with variables mentioned in metadata. It is possible to move assume forward, since data dependencies can be resolved by taking a snapshot of the environment at the original location. For the inverse effect, we support hoisting the predicate from one assume to another (see

2.5

). Moving assume instructions up is tricky and also unnecessary, since in combination the two primitives allow moving checks to any position. In the above example, if e is invariant in the loop body and there is an assume before Lloop, the predicate can be hoisted out of the loop. If the assume is only relevant for a subset of the instructions after the current location, it can be moved down as a whole.

Lazy Deoptimization

The runtime cost of an assume is the cost of monitoring the predicates. Suppose we speculate that the contents of an array remain unchanged throughout a loop. An implementation would have to check every single element of the array. An eager strategy where predicates are checked at every iteration is wasteful. It is more efficient to associate checks with operations that may invalidate the predicates, such as array writes, to invalidate the assumption, a strategy sometimes known as lazy deoptimization. We could implement dependencies by separating

stuck ()
V base
|
|    call debug =  debug ()
Lh   branch x  < 1000000   Lo Lrt
Lo   branch debug   Lslow Lfast
Lslow ...
Lfast ...
|    goto Lh
Lrt  ...
|
Figure 2.22:Long running execution
cont ( x )
V opt
|
Lh   branch  x <  1000000  LfastLrt
Lfast...
|    goto Lh
|
Lrt  ...
Figure 2.23:Switching to optimized code
undo ()
V s123
|
L0 assume  e1,e2,e3 else undo.Vs12.L0 [...]
V s12
|
L0 assume  e1,e2 else undo .V s1.L0 [...]
V s1
|
L0 assume  e1 else undo .V base.L0 [...]
Figure 2.24:Undoing an isolated predicate

assumptions from runtime checks. Specifically, let GUARDS [ 13 ] = true be the runtime check, where the global array GUARDS is a collection of all remote assumptions that can be invalidated by an operation, such as an array assignment. In terms of correctness, both eager and lazy deoptimization are similar; however, we would need to prove correctness of the dependency mechanism that modifies the global array.

Jumping Into Optimized Code

We have shown how to transfer control out of optimized code. The inverse transition, jumping into optimized code, is interesting as well. Consider executing the long running loop of

Figure 2.22

. The value of debug is constant in the loop, yet execution is stuck in the long running function and must branch on each iteration. A JIT can compile an optimized version that speculates on debug , but it may only use it on the next invocation. Ideally, the JIT would jump into the newly optimized code from the slow loop; this is known as OSR-in (for on-stack-replacement) or hot loop transfer. Specifically, the next time Lo is reached, control is transferred to an equivalent location in the optimized version. To do so, continuation-passing style can be used to compile a staged continuation function from the beginning of the loop where debug is known to be false. The optimized continuation might look like cont in

Figure 2.23

. In some sense, this is easier than deoptimization because it strengthens assumptions rather than weakening them and all the values needed to construct the state at the target version are readily available.

Fine-Grained Deoptimization

Instead of blindly removing all assumptions on deoptimization, it is possible to undo only failing assumptions while preserving the rest. As shown in

Figure 2.24

, if e

2

fails in version V s123 , one can jump to the last version that did not rely on this predicate. By deoptimizing to version V s1, assumption e

3

must be discarded. However, e

1

,e

3

still hold, so we would like to preserve optimizations based on those assumptions. Using the technique mentioned above, execution can be transferred to a version Ls13 that reintroduces e

3

. The overall effect is that we remove only the invalidated assumption and its optimizations. We are not aware of an existing implementation that explores such a strategy. The main problem is that such an approach requires us to keep all intermediate versions live and produces a fresh version for every assumption.

section 3.4

presents an alternative with a smaller overhead.

 
Lloop
branch e  LbodyLdone
Lbody
x 0
goto Lloop
Ldone
Figure 2.25:Loop with a dead store

Simulating a Tracing JIT

A tracing JIT [

Bala, Duesterwald, and Banerjia

2000

Gal, Eich, Shaver, Anderson, Mandelin, Haghighat, Kaplan, Hoare, Zbarsky, Orendorff, Ruderman, Smith, Reitmaier, Bebenita, Chang, and Franz

2009

] records instructions that are executed in a trace. Branches and redundant checks can be discarded from the trace. Typically, a trace corresponds to a path through a hot loop. On subsequent runs the trace is executed directly. The JIT ensures that execution follows the same path, otherwise it deoptimizes back to the original program. In this context

Guo and Palsberg

 [

2011

] develop a framework for reasoning about optimizations applied to traces. One of their results is that dead store elimination is unsound, because the trace is only a partial view of the entire program. For example, a variable x might be assigned to within a trace, but never used. However, it is unsound to remove the assignment, because x might be used outside the trace. We can simulate their tracing formalism in sourir. Consider a variant of their running example shown in

Figure 2.25

, a trace of the loop

while

e(x 0;) embedded in a larger context. Instead of a JIT that records instructions, assume only branch targets are recorded. For this example, suppose the two targets Lbody and Ldone are recorded, which means the loop body executed once and then exited. In other words, the loop condition e was true the first time and false the second time. The compiler could unroll the loop twice and assert e for the first iteration and ¬e for the second iteration.
 
assume e elseF .V base .Lloop [ x = x ,]
branch e  Lbody0Ldone
Lbody0
x 0
assume ¬e elseF .V base .Lloop [ x = x ,]
branch e  Lbody 1Ldone
Lbody1
x 0
goto Lloop
Ldone

Then unreachable code elimination yields the following code, resembling a trace.

 
assume e elseF .V base .Lloop [ x = x ,]
x 0
assume ¬e elseF .V base .Lloop [ x = x ,]

Say x is not accessed after the store in this optimized version. In sourir, it is obvious why dead store elimination of x would be unsound: the deoptimization metadata indicates that x is needed for deoptimization and the store operation can only be removed it can be replayed. In this specific example, a constant propagation pass could update the metadata to materialize the write of 0, only when deoptimizing at the second assume. But, before the code can be reduced, loop unrolling might result in intermediate versions that are much larger than the original program. In contrast, tracing JITs can handle this case without the drastic expansion in code size [Gal et al.2009], but lose more information about instructions outside of the trace.

Relation to Real-World Systems

Modern virtual machines have all incorporated some degree of speculation and support for deoptimization. These include implementations of Java (HotSpot, Jikes RVM), JavaScript (WebKit Core, Chromium V8, Truffle/JS, Firefox), Ruby (Truffle/Ruby), and R (FastR), among others. Anecdotal evidence suggests that the representation adopted in this work is representative of the instructions found in the IR of production VMs: the TurboFan IR from V8 [

Chromium

2022

] represents assume with three distinct nodes. First a checkpoint, holding the deoptimization target, marks a stable point, to where execution can be rolled back. In sourir this corresponds to the original location of an assume. A framestate node records the layout of, and changes to, the local frame, roughly the varmap in sourir. Assumption predicates are guarded by conditional deoptimization nodes, such as deoptimizeIf. Graal [

Duboscq et al.

2013

] also has an explicit representation for assumptions and associated metadata as guard and framestate nodes in their high-level IR. In both cases guards are associated with the closest dominating checkpoint. The relation between Ř’s IR and sourir is discussed later.

2.8 CoreJIT: Towards a Verified JIT

Eventually the building blocks presented in this thesis could be the foundation for writing an end-to-end verified JIT compiler. First steps were already made by Barrière et al. [2021]. The main differences with the formalization presented so far are that CoreJIT also models the creation of optimized code at run-time, that the formalization is mechanized, and that the deoptimization invariant was made more precise, by splitting Assume into two instructions Anchor and Assume. This section summarizes our findings from that paper, with the focus on the comparison to the sourir model.

CoreIR is inspired by CompCert’s RTL Leroy [2009]. As a simplification over sourir, CoreIR only features two versions per function, an optimized and a baseline one. Two CoreIR instructions are related to speculation, Anchor and Assume. Together they look and behave very similar to assume from sourir. The split was made to better describe the dynamics of the optimization process. The Anchor instruction represents a potential deoptimization point, i.e., a location in an optimized function where the correspondence with its baseline version is known to the compiler and thus deoptimization can occur. For instance, in Anchor F.l [r = r+1] the target F.l specifies the function (F) and label (l) to jump to, the mapping [r = r+1] is the varmap.

Anchors are inserted first in the optimization pipeline, before any changes are made to the program. Choosing where to insert them is important as they determine where speculation can happen. Speculation itself is performed by inserting Assume instructions. An assume based on the previous anchor is for instance Assume x=1 F.l [r = r’+1], which expresses the expectation that register x has value 1. This instruction behaves like the assume instruction in sourir. Unlike anchors, assumes can be inserted at any time during compilation.

The role of anchors is subtle. As already shown it is possible to move an assume instructions to support deoptimization at any location. To make this more practical, the Anchor stays at its original location, without tying it to additional data-dependencies by guard expressions. To add an Assume, the compiler finds the dominating Anchor and copies its deoptimization metadata. If there is no anchor, then the assumption cannot be made.

For the proofs, anchors have yet another role. They justify the insertion of Assume instructions. For this, the Anchor instructions have a non-deterministic semantics, an anchor can randomly choose to deoptimize. Crucially, deoptimization is always semantically correct, nothing is lost by returning to the baseline code eagerly other than performance. An inserted Assume is thus correct if it follows an Anchor and the observable behavior of the program is unchanged regardless which instruction deoptimizes.

PIC

Figure 2.26:The relation for delayed Assume insertion

Let’s consider the example in Figure 2.26. On the left is the version before inserting an assume, on the right after. In this case there is an Anchor followed by a conditional Branch and we insert the Assume instruction only in one of the branches. As mentioned, Anchor has a non-deterministic semantic, it can either continue or deoptimize. Therefore, the respective states must be matched for all its successor instructions, i.e., for both the case where it falls through (solid lines), as well as when it deoptimizes (via dashed lines). To that end the states between Anchor and Assume are matched both to a fall-through Anchor and a deoptimizing Anchor trace. In other words the assumption insertion pass codifies the assumption transparency invariant. The benefit of having anchors is that the assumes they dominate can be placed further down the instruction stream. The compiler must make sure that the intervening instructions do not affect deoptimization. This separation is important in practice as it allows a single Anchor to justify speculation at a range of different program points. All Anchor instructions are removed in the last step of the optimization pipeline. Initially the varmap of an Assume instruction will be identical to its dominating Anchor, but, as the following example shows, this can change through subsequent program transformations.

Illustrative Example

Assume that, for the program in

Listing 2.2

, a profiler detected that at
Function F(x,y,z): 
Version Base: 
     d  1 
 l1: a  x*y 
     Branch (z == 7) l2 l3 
 l2: b  x*x 
     c  z*y 
     Return b+c+d 
 l3: Return a
Listing 2.2:Baseline

label l2 of function F registers z and x always have values 7 and 75. Function F can thus be specialized. Listing 2.3 adds an Opt version to F where an anchor has been added at l4.

Function F(x,y,z): 
Version Base: 
     ... 
 
Version Opt: 
 l4: Anchor F.l1 [x,y,z,d=1] 
     Assume z=7 [x,y,z,d=1] 
     c  7*y 
     Assume x=75 [x,y,z=7,d=1] 
     Return 5626+c
Listing 2.3:Optimized

In order to deoptimize to the baseline, the anchor must capture all of the arguments of the function (x, y, z) as well as the local register d. The compiler is able to constant propagate d, so the anchor remembers its value. The speculation is done by e.g., Assume z=7 ... which specifies what is expected from the state of the program and the dominating anchor. The optimized version has eliminated dead code and propagated constants. If the speculation holds, then this version is equivalent to Base. Despite the overhead of checking validity of the speculation, the new version should be faster: the irrelevant computation of a has been removed and x*x is speculatively constant folded. If the speculation fails, then the execution should return to Base, at label l1 where the closest Anchor is available, and reconstruct the original environment. This involves for instance materializing the constant folded variable d. As we see here, Assume does not have to be placed right after an Anchor instruction. This will cause deoptimization to appear to jump back in time and some instructions will be executed twice. It is up to the compiler to ensure these re-executed instructions are idempotent. As can be seen in the example, different Assume instructions originating from the same Anchor, can end up with different varmaps.

Chapter 3
Context Dispatch: Splitting on Dynamic State

After discussing the assume model for speculation and deoptimization, we turn our attention to specialization by splitting. In our experience, to achieve performance for dynamic languages, a compiler needs information about the calling context of a function. This can be information about the type and shape of the function’s arguments, or any other predicates about program state that hold when the function is invoked. We have observed that for instance inlining and speculation work well together to expose that contextual information to the optimizer. Inlining allows to optimize the body of a function together with its arguments and speculation is needed to enable inlining for dynamic calls. The drawbacks of this approach are that inlining grows the size of compilation units, that speculation may fail causing the compiled code to be discarded, and that the caller needs to be recompiled to support a new dynamic context.

This chapter presents an approach to structure a just-in-time compiler to better leverage information available at run time. Our starting point is a compiler for a dynamic language geared to perform run-time specialization: it uses speculative optimizations, guesses about potential invariants, and deoptimizes functions if any of their assumptions fails to hold. Our goal is to extend this baseline compiler with a new technique called context dispatch that provides contextual information by specializing functions for different calling contexts. For every call, one of the best versions given the current state of the system is invoked. A key property of context dispatch is that it allows us to combine static and dynamic analysis for optimizations.

PIC

Figure 3.1:Specialization

When specializing to contextual information at the call-site, we get a graph as shown in Figure 3.1. At the call-site differently optimized versions can be selected. The choice happens at the time of the call. In contrast to Figure 2.2, where the speculatively optimized version is always called and when the guard fails it is discarded.1 At this abstract level we already observe one of the main trade-offs between the two approaches. Specialization implies code duplication. If we insert multiple splits, or additionally perform tail-duplication, this quickly leads to a path explosion problem, as can be observed for instance in tracing JITs. This is not an issue with speculative optimizations. Typically the optimized code is orders of magnitude smaller than the source, since all the unlikely behavior can be trimmed. As we have seen, the drawback of speculation is that it can be costly, because the optimized code needs to be discarded and then re-compiled again, possibly several times, until all assumptions are stable. Also it does not allow us to narrowly specialize to two different contexts at the same time.

The inspiration for the approach in this chapter comes from customized compilation, pioneered by Chambers and Ungar [1989], an optimization that systematically specializes functions to the dynamic type of their arguments. We extend this approach by specializing functions to arbitrary contexts and dynamically selecting optimized versions of a specialized function depending on the run-time state of the program. We refer to the proposed approach as context dispatch, since at its heart, it describes how to efficiently select a specialized version of a code fragment, given a particular program state as context.

As an illustration, consider Listing 3.1 written in R. The semantics

max <- function(a, b=a, warning=F) { 
  if (warning && any(is.na(c(a,b)))) 
    warn("NA Value") 
  if (a < b) b else a 
} 
max(x) + max(y,0)
Listing 3.1:max function

of R is complex: functions can be invoked with optionally named arguments that can be reordered and omitted. Furthermore, arguments are lazy and their evaluation (when the value is needed) can modify any value, including function definitions. In the above example, the max function is expected to return the largest of its first two parameters, mindful of the presence of missing values (denoted NA in R). The third, optional, parameter is used to decide whether to print a warning in case a missing value is observed. If max is passed a single argument, it behaves as the identity function. Since R is a vectorized language, the arguments of max can be vectors of any of the base numeric types of the language. Consequently, compiling this function for all possible calling contexts is likely to yield inefficient code.

Context dispatch is motivated by the observation that, for any execution of a program, there are only a limited, and often small, number of different calling contexts for any given function. For example, if max(y,0) and max(x) are the only calls to max, then we may generate two versions of that function: one optimized for a single argument and the other for two. Further specialization can happen on the type and shape of the first argument, this may either be a scalar or a vector of one of the numeric types. This shows that part of a context can be determined statically, e.g., the number of arguments, but other elements are only known at run time, e.g., the type and shape of arguments. Context dispatch thus, in general, requires run-time selection of an applicable call target.

We define a context to be a predicate on the program state, chosen such that there exists an efficiently computable partial order between contexts and a distinguished maximal element. Context dispatch provides a framework on how to incorporate dynamic information. Which properties make up a context and how they are represented or implemented is up to the concrete implementation. We will present a number of options here and also detail Ř’s implementation in chapter 4. The contexts have to be efficiently comparable, since the comparison is used for dispatching.

A version of a function is an instance of that function compiled under the assumption that a given context holds at entry. The idea is for the compiler to be able to use predicates from the context for optimizations. For instance if the context declares that it is Thursday and the compiler can prove that the function terminates within 24 hours, then a call to isWeekend() can be replaced by false.

To leverage versions the compiler emits a dispatch sequence that computes the call site context and invokes a version of the target function that most closely matches the calling context. The dispatch, which can use a combination of static and dynamic information, ensures that a good candidate version is invoked, given the current program state. The unoptimized baseline version of the function is associated to the maximal context and is the default version that will be called when no other applies.

We evaluated context dispatch in the context of Ř and, as will be discussed extensively later, found it to significantly improve the performance of several benchmark programs with negligible regressions. We consider R an interesting host to study compiler optimizations because of the challenges it presents to language implementers. However, context dispatch is not specific to R. We believe that the approach carries over to other dynamic languages such as JavaScript or Python. In more static languages context dispatch could be employed to propagate inter-procedural information, such as a dynamic escape analysis. Moreover, we emphasize that context dispatch is not a replacement for other optimization techniques; instead, it is synergistic.

Compared to Other Techniques

With context dispatch we provide the means to keep several differently specialized function versions and then dynamically select a good candidate, given the dynamic context at the call-site. To gain some intuition, let us revisit the example of Listing 3.1 and contrast speculation, inlining and context dispatch. Figure 3.2 shows idealized compilation of that code. On the left we observe the two call-sites to the max function. In the first case, since both callers omit the warning parameter, a compiler could speculatively optimize it away, by leaving an assume to catch calls that pass the third argument. However any unrelated call-site in the program could invalidate this assumption and undo the speculative optimization for all callers simultaneously. Second, inlining allows us to specialize the max function for each call site independently. In R, inlining is generally unsound as functions can be redefined by reflection. Therefore the assumption of a static target for the inlined call-site is a speculative optimization. Also, inlining increases code size, reduces sharing and is limited to specialize on statically known information. For instance in max(deserialize(readline()), 1), the argument type is dynamic and inlining does not allow us to specialize for it.

PIC

Figure 3.2:Speculation, Inlining and Context dispatch

In contrast, as depicted in the last example in Figure 3.2, context dispatch allows the compiler to create two additional versions of the target function, one for each calling context. At run-time the dispatch mechanism compares the information available at the call-site with the required contexts of each available version and dynamically dispatches to one of them. The types and length of x and y can generally not be inferred from the source code, but can be checked at run-time. Context dispatch consists of first approximating a current context C. For instance if x is a scalar integer, then at the call-site max(x), where just one argument is passed, a current context Integer[1], representing these facts, is established at runtime. Given C, a target version with a compatible context Cis invoked. In our example the context Eager,Missing,Missing is chosen. If no compatible specialized version is available, then we dispatch to the original version of the function. Compatibility is expressed in terms of ordering: contexts form a partial order, such that any smaller context logically entails the bigger one. Intuitively, a larger context matches more program states. In other words, a function version can be invoked if its context is bigger than the current one, i.e., C < C.

The target might not be unique. There might be several optimal compatible versions, as we will discuss later. In our implementation a context is an actual data structure with an efficient representation and comparison. For each call-site the compiler infers a static approximation for the upper bound of the current context. Additional dynamic checks further concretize the approximation and create a smaller current context. This dynamically inferred context has two uses. First, as described, it serves as the lower bound when searching for a target version of a particular function. Secondly, if no good approximation is found, then the current context serves as the assumption context to compile a fresh version to be added to the function.

PIC

Figure 3.3:Splitting

Context dispatch shares some similarities with splitting, as depicted in Figure 3.3. Specialized clones of functions are created, for instance here max2 is a copy of max which takes two arguments. Additionally, if there are multiple static candidates, then those are disambiguated at runtime by rewriting the call-site into a fixed sequence of branches. In this example we test for the length and in case of 1 call the copy max2s, specialized to receiving two scalar arguments. However, the specialization happens at compile-time and cannot be extended without recompilation. All those four techniques can be easily combined. For instance the performance of inlining can be improved by inlining an already optimized version using a static approximation of context dispatch. Or statically known candidates of likely contexts can be used statically by splitting on contexts.

3.1 Related Work

There is an abundance of code specialization techniques, besides speculation. The common theme here is that the compiler tries to identify common contexts, which can include dynamic types of arguments, values of local variables, but also meta-properties, such as whether an object escaped from a thread, and so on. Then a piece of code, often a whole function, is cloned and optimized for that context. Overall, keeping specialized copies of the same function is a well-known optimization technique. Existing approaches perform the selection by, either, piggy-backing onto existing dispatching mechanisms in the VM, by implementing an ad-hoc and fragmented approach, or by statically splitting at each call site.

Inlining

This powerful optimization has been used in static languages for over forty years [

Scheifler

1977

]. Replacing a call to a function with its body has several benefits: it exposes the calling context thus allowing the compiler to optimize the inlined function, it enables optimizations in the caller, and it removes the function call overhead. In dynamic languages, function calls are usually expensive, so inlining is particularly beneficial. The limitations of inlining are related to code growth: compilation time increases and cache locality may be negatively impacted.

Customization

Chambers and Ungar

 [

1989

] describe customized compilation as the compilation of several copies of a method, each customized for one receiver type. Method dispatch ensures that the correct version is invoked. This idea of keeping several customized versions of a function is generalized in the Jalapeño VM, which specializes methods to the types and values of arguments, static fields, and object fields [

Whaley

1999

]. Some specialization is enabled by static analysis, some by dynamic checks. The Julia compiler specializes functions on all argument types and uses multimethod dispatch to ensure the proper version is invoked [

Bezanson et al.

2018

]. In that sense the dispatching is used in two different settings, once user-facing, allowing users to override functions for particular signatures, with different behavior, but then also by the compiler for specializing the same function to different signatures. An interesting generalization of multimethod dispatch is proposed by

Ernst, Kaplan, and Chambers

 [

1998

], who generalize multimethod dispatch to arbitrary Boolean properties. But the focus lies on exposing the dispatching to users, thus statically ensuring that method selection is unambiguous and complete.

Kennedy and Syme [2001] present dynamic specialization for parametrized types in the intermediate representation of the .NET virtual machine; similarly for Java by Cartwright and Steele Jr [1998], or using user-guidance by Dragos and Odersky [2009]. Costa, Alves, Santos, and Pereira [2013] specialize on arbitrary values for JavaScript functions with a singular calling context and Hackett and Guo [2012] introduce a type-based customization which combines dynamic and static information. Liu, Millstein, and Musuvathi [2019] propose to specialize methods under a dynamic thread-escaping analysis to have lock-free versions of methods for thread-local receivers. Hosking, Eliot, and Moss [1990] argue for customized compilation of persistent programs to specialize code based on assumptions about the residency of their arguments.

For ahead-of-time compilers, Hall [1991] introduces method cloning, for instance to support inter-procedural constant propagation. Many similar context-sensitive optimization approaches follow, e.g., by Cooper, Hall, and Kennedy [1993]. Plevyak and Chien [1995] use a static technique to partition instances and calling contexts, such that more specialized methods can be compiled and then dynamically invoked. Ap and Rohou [2017] present dynamic specialization to concrete arguments using dynamic binary rewriting. Poesia and Pereira [2020] introduce technique to reduce the number of clones, when applying context-sensitive optimizations in the presence of longer call strings. Dean, Chambers, and Grove [1995] propose to limit overspecialization by specializing to sets of types. Overall, keeping customized copies of the same function is a well-known optimization technique. In contrast to existing techniques, the contribution of context dispatch is to provide a unified framework for implementing all customization needs in a JIT, and support sharing of compatible versions among different contexts.

Splitting

Whereas customization duplicates methods,

Chambers and Ungar

 [

1989

] also introduce splitting to duplicate call-sites. Control flow is split on the receiver, causing each branch to contain a statically resolved call-site. This transformation effectively pulls the target method selection out of the dispatch sequence and embeds it into the caller, thereby exposing it to the optimizer, which leads to further optimization opportunities. For instance the combination with tail-duplication allows SELF to statically resolve repeated calls to the same receivers. Splitting is a common optimization in ahead-of-time compilers, for instance LLVM [

Lattner and Adve

2004

] has a pass to split call-sites to specialize for non-null arguments. In a dynamic language splitting can be thought of as the frozen version of a polymorphic inline cache [

Hölzle et al.

1991

]. Both, inline caches and splitting, are orthogonal to context dispatch. Ř uses (external) caches for the targets of context dispatch and we could use splitting to split call-sites for statically specializing to the most commonly observed contexts.

Only few approaches besides trivial tail-duplication perform specialization at a lower granularity than a whole function. A noteworthy exception is the work by Chevalier-Boisvert and Feeley [2015], where dispatch happens at the basic block level. The approach was later adopted in the HHVM compiler Ottoni [2018]. In trace based approaches there is a related problem of stitching traces, where identical regions of different traces are to be identified and de-duplicated [Gal et al.2009Ardö, Bolz, and FijaBkowski2012].

3.2 Context Dispatch in a Nutshell

This section provides a precise definition of contexts and context dispatch. Then, we present a more detailed account on the performance trade-offs. The actual instance of context dispatch as implemented in Ř is detailed in chapter 4. We envision a number of possible implementations of context dispatch. The following provides a general framework for the approach and defines key concepts.

Context

Contexts C are predicates over program states S, with an efficiently computable, reflexive partial order defined as C

1

< C

2

 iff S : C

1

(S) C

2

(S), i.e., C

1

entails C

2

. For instance given C

I

type(arg0)==int and C

N

type(arg0)==num, then C

I

< C

N

since every integer is also a number. Let be the context that is always true; it follows that C < for all contexts C.

Current Context

A context is called current with respect to a state S if C(S) holds. For instance if currently arg0 contains the integer 3, then C

I

, C

N

, and are all current.

Version

C,V is called a version, where V is code optimized under the assumption that C holds at entry. A function is a set of versions including ⟨⊤,V

u

, where V

u

is the baseline version, i.e., compiled without contextual assumptions.

Dispatch

To invoke a function F in state S, the implementation chooses any current context C(with respect to S) and a version C,V ⟩∈ F such that C< C and transfers control to V . For instance if the current context is C

N

type(arg0)==num, then C

N

,V is reachable by dispatch, but C

I

,V where C

I

type(arg0)==int not. A simple strategy for efficient dispatching is to sort versions according to a compatible complete order (for instance using the binary representation when elements are incomparable) and then using a linear search for the first compatible context.

The above definitions imply a notion of correctness for an implementation.

Theorem 3. Dispatching to version C,V ⟩ ∈ F from a state S and a current context Cimplies C(S).

This follows immediately from the definition of the order relation. It means that dispatch transfers control to a version of the function compiled with assumptions that hold at entry.

Applying Context Dispatch

The above definitions may not necessarily lead to performance improvements; indeed, an implementation may choose to systematically dispatch to ⟨⊤,V u. This is a correct choice as the version is larger than any current context but it also provides no benefits. The definition allows for imprecision from both sides. First, we can choose an arbitrary loose current context. Second, given a current context we can choose an arbitrarily bigger target version. Both of these imprecisions are by design, as they are in fact implementation trade-offs. An implementation could try to always compute a smallest current context, as such a context captures the most information about the program state at the call site. On the other hand, increased precision might be costly, and thus an approximation may be warranted — a less precise current context is cheaper to compute and prevents over-specialization. Dispatching to a larger than necessary target version again prevents compiling too many versions and enables fast dispatching implementations.

An implementation may also compute the current context by combining static and dynamic information. For that we might want to require contexts be closed under conjunction. The benefits are that a unique smallest current context exists and the intersection of two current contexts is a more precise current context. In other words two independent measurements of the current state can be combined for a more precise context. For instance, one may be able to determine statically that C type(arg0)==int holds, perhaps

PIC

Figure 3.4:Versions and current program state

because that argument appears as a constant, whereas C′≡type(arg1)==string must be established by a run-time check. Given C Cexists, it is a more precise current context. Thus the compiler can emit a check for only C, but then dispatch on C C.

Similarly, dispatch can select any version that is larger than the current context. Typically, one would prefer the smallest version larger than the current context, as it is optimized with the most information. But this choice can be ambiguous, as illustrated in Figure 3.4. There are four versions of the binary function F: V u can always be invoked, V SS assumes two strings as arguments, V I? assumes the first argument is an integer, and V ?I assumes the second is an integer. Given F is invoked with two integers, i.e., in state S, the smallest current context CI? C?I = CII is not available as a version to invoke. The implementation can dispatch to either CI? or C?I; however, neither is smaller than the other (V u is also reachable, V SS is not).

Of course a JIT compiler can compile a fresh version CII,V II to invoke. This is how we envision an implementation to gradually populate the dispatch tables. An implementation must decide when to add (or remove) versions. Each dispatch where the current context is strictly smaller than the context of the version dispatched to is potentially sub-optimal. The implementation can rely on heuristics for when to compile a new version that more closely matches the current context. For instance for every dispatch we count the sub-optimal ones and then lazily compile new versions for contexts that occur frequently.

The efficiency of context dispatch depends only on the cost of computing a current context and the order relation. This allows for arbitrary complex properties in contexts, if these particular properties do not have to be checked at run-time. For instance “the first argument does not diverge” is a possible context. Given a call site f(while(a){}), we can establish this context using the conjunction of “if a==FALSE then while(a){} does not diverge” and “a==FALSE.” The former is static, and the latter is a simple dynamic check.

The compiler may replace context dispatch with a direct call to a version under a static current context. This has the benefit of removing the dispatch overhead, or even allows inlining of context dispatched versions. The drawback is that the static context might be less precise than the dynamic one and it forces the implementation to commit to a version early. A better strategy is to speed up the dynamic dispatch using an inline cache to avoid repeating the dispatch for every call. However, conversely to a traditional inline cache, if the target version is sub-optimal, we should re-check from time to time, if the dispatch table contains a better version by now.

To make matters concrete, we detail two examples of ad-hoc contextual specialization schemes and how they can be encoded in the context dispatch framework:

Customized Compilation

This technique introduced in SELF specializes methods to concrete receiver types by duplicating them down the delegation tree. The technique can be understood as an instance of context dispatch. The contexts are type tests of the method receiver C

A

typeof(self ) == A. The order of contexts is defined as C

A

< C

B

 iff A <: B. It follows that if the receiver is of class A, and A is a subtype of B, dispatch can invoke a version compiled for B. In the Julia language, this strategy is extended to the types of all arguments.

Splitting

It is possible to customize functions to certain contexts by splitting the call-site. For instance an optimization in LLVM involves converting the call f(x) with a potential null pointer argument to if (x != NULL) fNonnull(x) else f(x), to support an optimized version that can assume the argument to not be NULL. In terms of context dispatch this could be implemented using contexts to check for certain values, e.g., C

x,v

x==v and

C

x,v

x!=v. This optimization would then be available under the context

C

x,NULL

. Compared to splitting, the advantage is that the target versions do not need to be decided upon statically, in other words the splitting happens dynamically, only if actually needed, and we could still decide to add other value based specializations later.

Global Assumptions

Contexts can capture predicates about the values of global variables, e.g., C debug == true or C′≡display == headless. If we allow such contexts to be combined, we get a natural order from C C< C, i.e., a smaller context is one that tests more variables. The smallest current context is the conjunction of all current singleton contexts. An interesting application is shown by

Liu et al.

 [

2019

], where a dynamic analysis detects thread-local objects. The property is then used to dispatch to versions of their methods that elide locks.

3.3 An Illustrated Example

To illustrate the trade-offs when specializing functions consider Listing 3.2, a map-reduce kernel written in R. The reduce function takes a vector or list x and iteratively applies map. The map function has two optional arguments, op which defaults to "m", and b, which defaults to 1 when op is "m". map is called twice from reduce: the first call passes a single argument and the second call passes two arguments. The type of the result depends on the type of x and the argument y. As a driver, we invoke reduce ten times with a vector of a million integers, once with a list of tuples, and again ten times with an integer vector. This example exposes the impact of polymorphism on the performance.

map <- function(a, 
                b = if(op=="m") 1, 
                op= "m") { 
       if (op=="m")  a * b 
  else if (op=="a")  a + b 
  else error("unsupported") 
} 
reduce <- function(x, y=3, res=0) { 
  for (i in x) 
    res <- res + map(i) + map(i, y) 
  res 
} 
for (i in 1:10) 
  system.time(reduce(1L:1000000L)) 
reduce(list(c(1L,1L), c(2L,2L))) 
for (i in 1:10) 
  system.time(reduce(1L:1000000L))
Listing 3.2:An example program

PIC

Figure 3.5:Optimization strategies for Listing 3.2

Figure 3.5 illustrates the execution time of each of the twenty measurements in seconds (smaller is better). The red line describes the results with inlining and speculation enabled. In this case, map is inlined twice. The point marked with (1) shows optimal performance after the compiler has finished generating code. However, the call to reduce with a list of tuples leads to deoptimization and recompilation (2). Performance stabilizes again (3), but it does not return to the optimal, as the code remains compiled with support for both integers and tuples. The green line shows the results with inlining of the map function manually disabled. After performance stabilizes (4), the performance gain is small. This can be attributed to the high cost of function calls in R. Again, we observe deoptimization (5) and re-optimization (6). The curve mirrors inlining, but with smaller speedups. Finally, the blue line exposes the results when we enable context dispatch (without inlining). The first iteration (7) is fast because reduce can benefit from the compiled version of map earlier, thanks to context dispatch of calls. Performance improves further when the reduce function is optimized (8). We see a compilation event at (9). Finally, we return to the previous level of performance (10), in contrast to the two previous experiments, where the deoptimization impacted peak performance. The reason is that the version of map used to process integer arguments is not polluted by information about the tuples, since they are handled by a different version.

3.4 Deoptless: Context Dispatched OSR

An interesting combination of context dispatch with speculation is to avoid deoptimization. A problem of speculative optimizations is that when speculations fail, the optimized code is discarded and eventually replaced with a more generic version, which might be slower. To illustrate, consider a function that operates on a list of numbers. At run-time, the system observes the type of the values stored in the list. After a number of calls, if the compiler determines that the list holds only integers, it will speculate that this will remain true and generate code optimized for integer arithmetic. If, at some later point, floating point numbers appear instead, a deoptimization will be triggered. As shown in Figure 3.6, deoptimization makes it possible to swap the optimized code in-place with the baseline version of the function. In subsequent calls to the function the compiler refines its profiling information to indicate that the function can operate on lists of integers and floating point numbers. Eventually, the function will be recompiled to a new version that is slightly more general. That version will not need to deoptimize for floating point values, but likely will not be as efficient as the previously optimized one.

PIC

Figure 3.6:Deoptimization: OSR-out, profile, recompile

Speculative compilation can cause hard to predict performance pathologies. Failed speculations lead to two kinds of issues. First, deoptimization causes execution to suddenly slow down as the new code being executed does not benefit from the same level of optimization as before. Second, to avoid repeated deoptimizations, the program eventually converges to code that is more generic, i.e., that can handle the common denominator of all observed executions. From a user’s point of view, the program speeds up again, but it does not regain its previous performance.

Deoptless is a strategy for avoiding deoptimization to a slower tier. The idea is to handle failing assumptions with an optimized-to-optimized transfer of control. At each deoptimization point, the compiler maintains multiple optimized continuations, each specialized under different assumptions. When OSR is triggered, a continuation that best fits the current state of execution is selected. The function that triggered OSR is not retired with deoptless (as would occur in the normal case), rather it is retained in the hope that it can be used again.

PIC

Figure 3.7:Deoptless: dispatched OSR to specialization

Figure 3.7 illustrates what happens when speculation fails with deoptless. Instead of going to the baseline, the compiler generates code for the continuation, and execution continues there. This can result in orders-of-magnitude faster recovery from failed speculation. Furthermore, deoptless not only avoids tiering down, it also gives the compiler an opportunity to generate code that is specific to the current execution context. As we later demonstrate, this can significantly increase the peak performance of generated code. For instance, if an assumption fails, as above, because a list holds floating point numbers rather than integers, then the continuation can be specialized to handle floats. In subsequent executions, if the same OSR point is reached, the continuation to invoke will be selected by using context dispatch. If no previously compiled continuation matches the execution context, then a new one will be compiled. Of course, the number of continuations is bounded, and when that bound is reached deoptless will deoptimize.

Example

Deoptless is a compilation strategy that explores the idea of having a polymorphic OSR-out as a backup for failed speculation, while retaining the version of the function that triggered deoptimization. Consider the sum function of Listing 3.3, which

sum <- function() { 
  total <- 0 
  for (i in 1:length) total <- total + data[[i]] 
  total 
}
Listing 3.3:Summing vectors

naively adds up all the elements in the data vector. Assume the function is called in situations where the values of data change from float to integer to complex numbers and back to float. As a preview, we run this code in our implementation. Figure 3.8 shows both normal executions and executions with deoptless. We see the warmup time spent in the interpreter and compilation to faster native code in the first phase with 5 iterations. Each of the following 3 phases (also with 5 iterations each) correspond to a different type of data vector. In the normal environment each change of the dynamic type results in deoptimization, followed by slower execution. In deoptless, there is a slowdown in the first iteration, as the continuation must be compiled, then code is fast again. Complex numbers are slow in both versions as their behavior is more involved. Finally, when the function deals with floats again, deoptless is as fast as the first time, whereas the original version is stuck with slow code. We show this example here to motivate the technique and give an intuition for our goals and the expected gains. This graph effectively illustrates many of the trade-offs with deoptless that we are aware of, and we’ll discuss it again in detail at the end of the section.

PIC

Figure 3.8:Performance comparison (log scale)

Approach

Conceptually, deoptless performs OSR-out and OSR-in in one step, to achieve an optimized-to-optimized and native-to-native handling of failing speculation.

PIC

Figure 3.9:Deoptless combines OSR-out with OSR-in

As can be seen in Figure 3.9 this is realized by following an OSR-out immediately with an OSR-in. By performing this transition directly, it is possible to never leave optimized code. For deoptless, the OSR-in must be implemented by compiling an optimized continuation, specifically for that particular OSR exit point. The key idea is that we can compile multiple specialized continuations, depending on the failing speculation — and in general, depending on the current state of the execution. The continuations are placed in a dispatch table to be reused in future deoptimizations with compatible execution states.

We effectively turn deopt points into assumption-polymorphic dispatch sites for optimized continuations. If the same deoptimization exit point is taken for different reasons, then, depending on the reason, differently specialized continuations are invoked. Going back to Listing 3.3, the failing assumption is a typecheck. Given earlier runs, the compiler speculates that data is a vector of floats. This assumption allows us to access the vector as efficiently as a native array. Additionally, based on that assumption, the total variable is inferred to be a float scalar value and can be unboxed. When the variable becomes an integer, this speculation fails. Normally we would deoptimize the function and continue in the most generic version, e.g., in the baseline interpreter. Deoptless allows us to split out an alternate universe where we speculate differently and jump to a continuation optimized for that case.

We keep all deoptless continuations of a function in a common dispatch table. At a minimum the continuation we want to invoke has to be compiled for the same target program location. But we can go further and use the current program state, that we extracted from the origin function for OSR, to have many specialized continuations for the same exit. In order to deduce which continuations are compatible with the current program state we employ a context dispatching mechanism. To choose a continuation, we take the current state at the OSR exit point, we compute a current context C for it, and then select a continuation compiled for a context C, such that C < C. If there is no such continuation available, or we find the available ones to be too generic given the current context, we can choose to compile a new continuation and add it to the dispatch table.

In our implementation we add an abstract description of the deoptimization reason, such as ”typecheck failed, actual type was an integer vector”, to the context. Our source states are expressed in terms of the state of the bytecode interpreter. Therefore, the deoptimization context additionally contains the program counter of the deoptimization point, the names and types of local variables, and the types of the variables on the bytecode stack. Deoptimization contexts are only comparable if they have the same deoptimization target, the same names of local variables, the same number of values on the operand stack, and a compatible deoptimization reason. This means, for instance, that a deoptimization on a failing typecheck is not comparable with a deoptimization on a failing dynamic inlining, and thus we can’t reuse the respective continuation. Or, if there is an additional local variable that does not exist in the continuation context. Comparable contexts are then sorted by the degree of specialization. For instance, they are ordered by the subtype relation of the types of variables and operands. If the continuation is compiled for a state where sum is a number, then it can for example be called when the variable sum holds an integer or a floating-point number. Or, if we have a continuation for a typecheck, where we observed a float vector instead of some other type, then this continuation will be compatible when we observe a scalar float instead, as in R scalars are just vectors of length one.

Dispatching is based on the execution states of the source code of the optimizer, e.g., in our case states of a bytecode interpreter. This does not mean that deoptless requires these states to be materialized. For instance when dispatching on the type of values that would be on the operand stack of the interpreter at the deoptimization point, they are not actually pushed on the stack. Instead their type is tested where they currently are in the native state.

Potential and Limitations

Deoptless does not add much additional complexity over OSR-out and OSR-in to an implementation. There are some considerations that will be discussed when we present our prototype in the next section. Most prominently, OSR-out needs to be more efficient than when it is used only for deoptimization, because we expect to trigger OSR more frequently when dispatching to optimized continuations. Currently our proof-of-concept implementation is limited to handle deoptimizations where the origin and target have one stack frame, i.e., we do not handle inlined functions. This is not a limitation of the technique, but rather follows from the fact that also the OSR-in implementation currently has the same limitation. We can therefore not answer how well deoptless would perform in the case of inlined functions.

There are also a number of particular trade-offs, which are already visible in the simple example in Figure 3.8. Going through the four phases of the example, we can observe the following. In the first phase both implementations warm up equally fast. There is no difference, as there is also no deoptimization event up to this point. In the second phase, when the type changes to float, the normal implementation triggers a deoptimization, we fall back to the interpreter and it takes some time for the code to be recompiled. This replacement code is more generic as it can handle floats and integers at the same time and it is much slower than the float-only case. The effect is inflated here due to the fact that our particular compiler supports unboxing only if the types are static. This can be seen in the first phase of the deoptless variant, where a specialized continuation for floats is compiled and executed very efficiently. We see a small overhead over the integer case, that is due to the dispatch overhead of deoptless. Next, in the third phase, yet another specialized continuation is compiled, this time for the data vector being a generic R object. While we avoid going back to the interpreter yet again, this continuation is slower at peak performance than the generic version from the normal execution. This is not a fundamental limitation, but does exemplify a difficulty with deoptless that we will get back to: deoptless operates on partial type-feedback from the lower tier. Because the remainder of the sum function has never been executed with the new type, we cannot fully trust the type-feedback when compiling the continuation, as it is likely stale to some extent. We address the problem with a selective type-feedback cleanup and inference pass, which can, as in this case, lead to less optimal code. In the final phase of the benchmark deoptless greatly outperforms the normal implementation. That is because in deoptless we are running the same code again as in the first phase, as this code was never discarded. On the other hand in the normal case we replaced the sum function in-place and it is now much more generic and slow.

Speculative optimizations are key for the performance of just-in-time compilers. Deoptless presents a way of dealing with failing speculations that does not tier down, i.e., does not have to continue in a slower tier. Instead of having functions become gradually more and more generic on every deoptimization, we take this opportunity for splitting and compile functions which become more and more specialized. Our preliminary evaluation shows the big potential of the technique. As we will show, when presented with randomly failing assumptions, deoptless is able to execute benchmarks up to 9.1× faster than with normal deoptimization, with most benchmarks being at least 1.9× faster and none slower. As with every forward escape strategy, there is a danger of committing follow-up mistakes. Deoptless struggles with cases where it is hard to infer from the failing speculation how the remainder of the function will be affected, before actually running it. We approach this problem by incorporating information from the current state of the execution at the OSR exit point. Additionally, we use type-inference on the type-feedback to override stale profile data. Our evaluation shows that this strategy is robust and able to produce good code for the continuations.

3.5 Discussion

In conclusion, context dispatch allows the compiler to manage multiple specialized versions of a function, and to select the most appropriate version dynamically based on information available at the call site. The difference with inlining and speculation is that context dispatch allows a different version of a function to be chosen at each and every invocation of that function with modest dispatching overhead. Whereas inlining requires the compiler to commit to one particular version, and speculation requires the compiler to deoptimize the function each time a different version is needed. We envision context dispatch to allow just-in-time compilers to rely more on inter-procedural optimizations for performance in the future.

Like inlining, context dispatch allows to specialize a function to its calling context. Unlike inlining, the specialized function can be shared across multiple call sites. While speculation needs deoptimization to undo wrong assumptions, context dispatch does not. Context dispatch applies at call boundaries, while speculation can happen anywhere in a function. Finally, let us repeat that these mechanisms are not mutually exclusive: the implementation of Ř supports all of them and we look forward to studying potential synergies in future work.

The key design choice for an implementation of this approach is to pick contexts that have an efficiently computable partial ordering. We envision compilers for different languages defining their own specific contexts. The choice of context is also driven by the cost of deriving them from current program state, and the feasibility of approximation strategies.

The context dispatch framework was initially designed to select versions at the function level. But, as we have shown with deoptless, it is also possible to apply it for dispatching code fragments at a finer granularity.

Chapter 4
Ř: Implementation

This chapter provides an in-depth look at Ř1. This implementation of the R language [R Core Team2022] is the main case-study and it co-evolved with the models and implementation recipes presented so far. It will be used in the evaluation in the next chapter 5.

The explanation starts with a primer on the R language in Listing 4.1 with a particular focus on the main obstacles for a compiler. Even to readers familiar with the R language it might hold some surprises. In particular it introduces the problems which arise from the late-bound variable scope of closures, which can be reflectively altered at run-time. Then section 4.2 describes the architecture of Ř and how it is built on top of the reference implementation GNU R. Then we turn our attention to the protagonist; to the optimizing compiler of the Ř implementation. In section 4.4 its intermediate representation PIR is introduced. The distinguishing features of the representation, next to speculation and contextual optimizations, are its first-class support for R environments (i.e., late bound variable scopes) and promises (i.e., thunks for lazy evaluation). Finally, the remaining three sections detail the implementation of the main contributions from chapter 2 and chapter 3. The section 4.7 describes how sourir is implemented in PIR and used for speculative optimizations, section 4.8 presents the context dispatch implementation, and section 4.9 deoptless.

4.1 Background

The R language presents interesting challenges for implementers. R is a dynamic imperative language with vectorized operations, copy-on-write of shared data, a call-by-need evaluation strategy, context-sensitive lookup rules, multiple dispatch, and first-class closures. A rich reflective interface and a permissive native interface allow programs to inspect and modify most of R’s runtime structures. This section focuses on the interplay of first-class, mutable environments and lazy evaluation. In particular, we focus on their impact on compiler optimizations.

One might see the presence of eval as the biggest obstacle for static reasoning. With eval, text can be turned to code and perform arbitrary effects. However, the expressive power of eval can be constrained by careful language design. Julia, for instance, has a reflective interface that does not hamper efficient compilation. Even an unconstrained eval is bound by what the language allows; for example, most programming languages do not allow code to delete a variable. Not so in R. Consider one of the most straightforward expressions in any language, variable lookup:

f <- function(x) x

In most languages, it is compiled to a memory or register access. From the point of view of a static analyzer, this expression usually leaves the program state intact. Not so in R. Consider a function doubling its argument:

g <- function(x) x+x

In most languages, a compiler can assume it is equivalent to 2*x and generate whichever code is most efficient. At the very least, one could expect that both lookups of x resolve to the same variable. Not so in R.

Difficulties come from two directions at once. R variables are bound in environments, which are first-class values that can be modified. In addition, arguments are evaluated lazily; whenever an argument is accessed for the first time, it may trigger a side-effecting computation – which could modify any environment. Consequently, to optimize the body of a function, a compiler must reason about effects of the functions that it calls, as well as the effects from evaluating its arguments. In the above example, + could walk up the call stack and delete the binding for variable x. One could also call g with an expression that deletes x and causes the second lookup of x to fail. While unlikely, a compiler must be ready for it. Considering these examples in combination with eval, it is impossible to statically resolve the binding structure of R programs.

Ř’s optimizing compiler has a custom intermediate representation for R, called PIR. This IR is in single-static assignment form [Rosen, Wegman, and Zadeck1988] and has explicit support for environments and lazy evaluation. In our experience, some of the most impactful optimizations are high-level ones that require understanding how values are used across function boundaries. We found that the GNU R bytecode was too high level; it left too many of the operations implicit. In contrast, we found LLVM’s IR too low level for easily expressing some of our target optimizations.

Environments in R

Inspired by Scheme and departing from its predecessor S, R adopted a lexical scoping discipline [Gentleman and Ihaka2000]. Variables are looked up in a list of environments. Consider this snippet:

g <- function(a) { 
    f <- function() x+y 
    if (a) x <- 2 
    f() 
} 
y <- 1

The evaluation of x+y requires finding x in the enclosing environment of the closure f, and y at the top level. It is worth pointing out that, while R is lexically scoped, the scope of a free variable cannot be resolved statically. For instance, x will only be in scope in g if the argument a evaluates to true.

R uses a single namespace for functions and variables. Environments are used to hold symbols like +. While primarily used for variables, environments can also be created explicitly, e.g., to be used as hashmaps. Libraries are loaded by the attach() function that adds an environment to the list of environments. A number of operations allow interaction with environments: environment() accesses the current environment; ls(...) lists bound variables; assign(...) adds or modifies a binding; and rm(...) removes variables from an environment. R has functions to walk the environment chain: parent.frame() returns the environment associated with the caller’s call frame and sys.frame(...) provides access to the environment of any frame on the call stack. In R, frames represent function invocations and they have references to environments. Consider this code:

f <- function() get("x", envir=parent.frame()) 
g <- function() {x <- "secret"; f()}

Function f uses reflection to indirectly access g’s environment. This illustrates that any callee may access (and change) the caller environment.

Laziness in R

Since its inception, R has adopted a call-by-need evaluation strategy (also called lazy evaluation). Each expression passed as argument to a function is wrapped in a promise, a thunk that packages the expression, its environment, and a slot to memoize the result of evaluating the expression. A promise is only evaluated when its value is needed. Consider a function that branches on its second argument:

f <- function(a, b) if(b) a

A call f(x<-TRUE,x) creates two promises, one for the assignment x<-TRUE, and one to read x. One could expect this call to return TRUE, but this is not so. The condition is evaluated before variable x is defined, causing an error to be reported. Combined with promises, the sys.frame function allows non-local access to environments during promise evaluation:

f <- function() sys.frame(-1) 
g <- function(x) x 
g(f())

Here g receives promise f() as argument. When the promise is forced, there will be three frames on the stack: frame 0 is the global scope, frame 1 is g’s, and frame 2 is f’s frame.

PIC

During promise evaluation, parent.frame refers to the frame where the promise was created (frame 0 in this example, as promise f() occurs at the top level). But, sys.frame(-1) accesses a frame by index, ignoring lexical nesting, thus extracting the environment of the forcing context, i.e., the local environment of g at frame 1.

We leave the reader with a rather amusing brain twister. R has context-sensitive lookup rules for variables in call position. Variables that are not bound to functions are skipped:

f <- function(c) {c(1, 2) + c} 
f(3)

The lookup of c in c(1,2) skips the argument c, since it is not a function. Instead, primitive c() is called to construct a vector. The second read of c is not in call position, thus it returns argument c, 3 in this case. The result is the vector [4,5] as addition is vectorized. Now, consider the following variation:

bad <- function() 
  rm(list="c", envir=sys.frame(-1)) 
f(bad())

This time, evaluation ends with an error as we try to add a vector and a function. Evaluation of c(1,2) succeeds and returns a vector. But, during the lookup of c for that call, R first encounters the argument c. In order to check if c is bound to a closure, it evaluates the promise, causing bad() to delete the argument from the environment. On the second use of c, the argument has been removed and a function object, c, is returned.

Obstacles for Optimizers

A realistic language implementation helps to test models against reality. We can assess the interplay of optimizations and if they work in a language with complex features. The R language presents interesting challenges for implementers. R’s rich reflective interface and a permissive native interface allow programs to inspect and modify most of R’s runtime structures. A particular challenge comes from the interplay of first-class, mutable environments and lazy evaluation. The list of challenges for optimizing R is too long to detail. We restrict the presentation to seven headaches.

  1. Out of order: A function can be called with a named list of arguments, thus the call to add(y=1,x=2) is valid, even if arguments x and y are out of order. Impact: To deal with this, GNU R reorders its linked list of arguments on every call.
  2. Missing: A function can be called with fewer arguments than it defines parameters. For example, if function add(x, y) is called with one argument, add(1), it will have a trailing missing argument. While the calls add(,2) and add(y=2) have an explicitly missing argument for x. These calls are all valid. Impact: If the missing parameters have default values, those will be inserted. Otherwise, the implementation must report an error at the point a missing parameter is accessed.
  3. Overflow: A function can be called with more arguments than it defines parameters. Impact: The call sequence must include a check and report an error.
  4. Promises: Any argument to a function may be a thunk (promise in R jargon) that will be evaluated on first access. Promises may contain arbitrary side-effecting operations. Impact: A compiler must not perform optimizations that depend on program state that may be affected by promises.
  5. Reflection: Any expression may perform reflective operations such as accessing the local variables of any function on the call stack. Impact: The combination of promises and reflection requires implementations to be able to provide a first-class representation of environments.
  6. Vectors: The most widely used data types in R are vectorized. Scalar values are vectors of length one. Impact: Unless it can prove otherwise, the implementation must assume that values are boxed and operations are vectorized.
  7. Objects: Any value, even an integer constant, can have attributes. Attributes tag values with key-value pairs which are used, among other things, to implement object dispatch. Impact: The implementation must check if values have a class attribute, and, if so, dispatch operations to the methods defined to handle them.

It is noteworthy that none of the above obstacles can be definitely ruled out at compile time. Even with the help of static program analysis, these properties depend on the program state at the point a function is called. This should come as no surprise after having discussed reflective environment access. There are however much more mundane parts of the language with an equally surprising dynamic behavior. To illustrate this, consider the number of arguments passed to a function. The following code calls add() twice, once with a statically known number of arguments and the second time with the result of expanding the varargs parameter:

g <- function(...) add(1,3) + add(...)

The triple dots expand at run time to the list of arguments passed into g. Thus, to know the number of arguments of add requires knowing the number of arguments of g. The following are all legal invocations:

g(); g(1); g(,1); g(1,2,3); g(b=1, a=2); 
g(..., a=1);

Further, implementations of the add function can exert the full name-based argument matching facilities, having arguments dynamically matched based on the names of arguments passed to g.

4.2 Architecture

Ř is a just-in-time compiler that plugs into the GNU R environment and is fully compliant with the language’s semantics. It passes all GNU R regression tests as well as those of recommended packages with only minor modifications.2 Ř follows R’s native API which exposes a large part of the language run-time to user-defined code. It is also binary compatible in terms of data structure layout, even though this is costly as GNU R’s implementation of environments is not efficient.

PIC

Figure 4.1:Ř compilation pipeline

As shown in Figure 4.1, Ř features a two-tier optimization pipeline with a bytecode called RIR, an optimizing compiler with a custom, SSA based intermediate representation called PIR, and an LLVM based native backend. For some unsupported operation the VM can also fall back to the GNU R AST interpreter.

Source code is translated to RIR, which is then interpreted. For hot functions, RIR is translated PIR. Optimizations such as global value numbering, dead store and load removal, hoisting, escape analysis, and inlining are all performed on PIR code. It is noteworthy that many of the optimizations in Ř are also provided by LLVM. However, in PIR they can be be applied at a higher level. For instance, function inlining is complex due to first-class environments and therefore impossible without specific support for them. There are also R specific optimizations, such as scope resolution, which lowers local variables in first-class environments to PIR registers; promise inlining; or optimizations for eager functions.

Ř relies on speculative optimizations. Profiling information from previous runs is used to speculate on types, on shapes (scalars vs. vectors), on the absence of attributes, and so on. The RIR interpreter gathers type feedback that is later used for optimization decisions. To that end there are several recording bytecodes that can be used to track values, types, call targets and branch targets. This profiling information is then used to annotate PIR values in the optimizer, and consumed by speculative optimization passes. Ř also performs speculative dead code elimination, speculative escape analysis to avoid materializing environments, and speculative inlining of closures and builtins. Speculation is orthogonal to context dispatch; every version of a function can have its own additional speculative optimizations. When speculation fails, a deoptimization mechanism transfers execution back to the RIR interpreter. The design of speculative optimizations is based on sourir. As a novel feature, PIR allows scheduling of arbitrary instructions, such as allocations, only on deoptimization.

4.3 Related Work

The R language is an imperative language for statistical computing with vectorized operations, copy-on-write of shared data, a call-by-need evaluation strategy, multiple dispatch, first-class closures, and reflective access to the call stack [R Core Team2022]. R has one reference implementation, GNU R, and several alternative implementations. GNU R includes a bytecode compiler with a number of carefully tuned optimizations [Tierney2019]. Unlike Ř, GNU R’s bytecode implicitly assumes the presence of an environment for every function application. Variable lookup, in the worst case, requires inspecting all bindings of each environment in scope. To mitigate the lookup cost, GNU R caches bindings when safe.

FastR’s first version featured a type-specializing tree interpreter that outperformed GNU R [Kalibera, Maj, Morandat, and Vitek2014]. It split environments into a statically known part (represented by arrays with constant-time accesses) and extensions that could grow and shrink at runtime. Environments were marked dirty whenever a reflective operation modified them. The second version of FastR uses Truffle for specialization and Graal for code generation Stadler et al. [2016]. FastR speculatively specializes the code based on profile-driven global assumptions. For instance, functions exhibiting a runtime stable binding structure are compiled under that assumption. The compiler elides environments and stores variables on the stack. Code is added to detect violation of assumptions and trigger deoptimization.

Type specialization was also used in the ORBIT project, an attempt at extending GNU R with a type specializing bytecode interpreter [Wang, Wu, and Padua2014]. On the other hand, the Riposte compiler tried to speed up R by recording execution traces for vector operations [Talbot, DeVito, and Hanrahan2012]. Riposte performed liveness analysis on the recorded traces to avoid unnecessary vector creations and parallelize code. None of these alternatives provides any special treatment for environment bindings. Of these systems, only GNU R and Oracle’s FastR are maintained as of this writing.

Ř departs from all these efforts in that we provide explicit support for environments and promises in the compiler IR. This allows us to combine static reasoning (when feasible) with speculative optimizations (when needed).

Other languages have some of the same features R has but, usually, are more amenable to compilation. MIT Scheme [Hanson and Team2020] has first-class environments, but they are immutable. Julia resembles R in that it is dynamically typed, reflective, and targets scientific computing. But, as shown by Bezanson et al. [2018], it exhibits much better performance. This is due to a combination of careful language design and an implementation strategy that focuses on type specialization, inlining, and unboxing. Julia does not have lazy evaluation, it restricts eval to execute at the top level, and limits reflection. Another example is JavaScript. While it is also dynamic, the only way to add variables to a scope is using eval, which can only do so locally. Serrano [2018] performs static reasoning on JavaScript by relying on type specialization and occurrence typing [Tobin-Hochstadt and Felleisen2010], as well as rapid atomic type analysis [Logozzo and Venter2010]. Whenever types cannot be statically determined, the compiler assumes the most likely structures ahead of time and relies on speculative guards for soundness. Smalltalk also features first-class contexts, although adding bindings at runtime is not supported. The Cog VM by Miranda [2011] maps context objects to the native stack and materializes contexts on demand when they are reflectively accessed.

4.4 PIR

One main design goal for the intermediate representation of the Ř optimizer is to model R variables and lazy evaluation. We distinguish between source-level R variables, which we call variables, and PIR local variables, called registers. Variables are stored in environments while the implementation of registers is left up to the compiler, and reflective access is not provided.

We start with an example to illustrate how R variables are modeled, and if possible lowered to registers. We use the following simple function definition:

function() { 
  answer <- 42 
  answer 
}

The function defines a local variable and returns its value. It translates to the following PIR instructions:

%0
=
MkEnv (  : G)
%1
=
LdConst  42
StVar ( answer , %1 , %0 )
%3
=
LdVar ( answer , %0 )
%4
=
Force (%3 ) %0
Return (%4 )

First, MkEnv creates an empty environment nested in G, the global environment. As all values are vectorized, 42 is loaded as a vector of length 1. StVar updates environment %0 with a binding for variable answer. Then, LdVar loads variable answer again. As the examples in Listing 4.1 have conveyed, the compiler cannot assume much about the loaded value. Because returns are strict in R, the compiler inserts a Force instruction to evaluate promises. It refers to environment %0 because a promise could reflectively access it. We record this fact as a data dependency. In general, we use a notation where actual arguments are inside parentheses and data dependencies outside. When Force is passed a value, rather than a promise, it does nothing.

After translation, the compiler runs a scope resolution pass to lower variables to registers. This requires combining an analysis and a transformation step. The analysis computes the reaching stores at each program point. Its results are then used to remove loads. In the previous example, the analysis proves that the value referenced by variable answer in instruction %3 originates from StVar ( answer , %1 , %0 ). Thus, %3 can be substituted with %1 . In case of multiple dominating stores, we insert a Phi instruction to combine them into a single register. Once this load is resolved, the environment is not used anymore, except for a dead store. Standard compiler optimizations, such as escape analysis of the environment and dead store elimination, can now transform this function into:

%1
=
LdConst  42
Return (%1 )

This version has no loads, stores, or environment and does not require speculation.

Promise Elision

Promises consume heap memory and hinder analysis, since they might have side effects. Therefore, we statically elide them when possible with the following three steps: first, inline the callee; next, identify where the promise is evaluated; and last, inline the body of the promise at that location. To preserve observable behavior, inlining must ensure that side effects happen in the correct order. Consider the following code snippet:
f <- function(b) b 
f(x)

This snippet translates to the following PIR instructions. First we show the creation of closure f and its invocation with a promise argument x:

pr0
%1
=
MkClosure ( f , G)
%2
=
MkArg ( pr0 , G)
%3
=
Call %1  (%2 ) G
%4
=
LdVar ( x , G)
%5
=
Force (%4 ) G
Return (%5 )

The closure is explicitly created by MkClosure. Similarly, the promise %2 is created by MkArg from pr0. Analogous to Force, Call has a data dependency on the environment because the callee can potentially access it. The translation of pr0 does not optimize the read of x as this would require the equivalent to an interprocedural analysis. Then, the function f translates to the following PIR:

f
%6
=
LdArg (0)
%7
=
MkEnv ( b = %6   : G)
%8
=
Force (%6 ) %7
Return (%8 )

The translation of f illustrates the calling convention chosen for PIR: it requires environments to be callee-created, i.e., callees initialize environments with arguments. Accordingly, the LdArg in f loads an argument by position and MkEnv binds it to variable b.

We now walk through promise inlining. First, the callee must be inlined. Performing inlining at the source level in R is not sound as this would mix variables defined in different environments. However, this is not an issue in PIR; since environments are modeled explicitly, the inlinee keeps its local environment as MkEnv is also inlined. Therefore, after inlining f, we get:

   inlinee
%2
=
MkArg ( pr0 , G)
%7
=
MkEnv ( b = %2   : G)
%8
=
Force (%2 ) %7

The next step is to elide the promise by inlining it where it is evaluated. We identify the Force instruction which dominates all other uses of a MkArg instruction. If such a dominating Force exists, it follows that the promise must be evaluated at that position. We inline pr0 to replace %8 :

   inlinee
   inlined promise
%2
=
MkArg ( pr0 , G)
%6
=
MkEnv ( b = %2   : G)
%4
=
LdVar ( x , G)
%5
=
Force (%4 ) G

We have succeeded in tracking a variable captured by a promise through a call and evaluation of that promise. The %2 and %6 instructions are dead code and can be removed, leaving only the load and force of x.

Syntax and Semantics

F    ::=  
   |    id : V1,..,Vn   
V    ::=  
Function
   |    C : BP    context body and promises
P    ::=  
Promise
   |    id : B   
B   ::=  
Basic Block
   |   L : st   
L    ::=  
Basic Block Label
   |    BBn   
st    ::=  
Statements
   |    T  %n = instr    non-void instruction
   |    instr    void instruction
Figure 4.2:Programs, Functions, Versions, Statements
T    ::=  
   |    t   
   |    t1|t2    union
   |    Tm1...mn    with flags
t    ::=  
Base Types
   |    any   
   |    int   
   |    real   
   |    lgl   
   |   cls   
   |   env   
   |    stub    Environment stub
   |    cp    Checkpoint
   |    fs    Framestate
   |    bool    native bool
   |      
m    ::=  
Type Modifiers
   |    $    scalar
   |       eager
   |    +    might have attributes
Figure 4.3:Types
v ::=
ve environment
vp promise
vc closure
lit literal
v e ::=
(x : v) : ve variables + enclosing env.
vp ::=
< P,ve, _ > unevaluated promise
< P,ve,v > evaluated promise
vc ::=
< F,ve > closure
Figure 4.4:Values
instr    ::=  
   |    Binop (a1, a2) env    binary op.
   |    Jump L    jump
   |    Branch (a, L1, L2)    branch
   |    Call a0 (a) env    apply closure
   |    Checkpoint L    deoptimization safepoint
   |    Assume (a) a0    assumption, a0 : cp
   |    IsT(a)    typecheck
   |    Framestate (id,a,env = env,next = a0)    framestate, a0 : fs
   |    Deopt (a)    deoptimization, a : fs
   |    Force (a) env    force promise
   |    LdArg (n)    load argument
   |    LdConst lit    load constant
   |    LdFun (x, env)    load function
   |    LdVar (x, env)    load variable
   |    MkArg (id, env)   
   |    MkArg (id, env, lit)    create promise
   |   MkEnv ((x = a)  : env)   create environment, env : envir
   |   MkClosure (id, env)   create closure
   |    Phi ((L : v))    ϕ function
   |    Return (a)    return
   |    StVar (x, a, env)    store variable
a    ::=  
Arguments
   |    %n    register
   |    lit    literal
Binop    ::=  
   |    Add   
   |    Eq   
   |    ...   
lit    ::=  
Literals
   |    G    global env.
   |    missing    missing argument
   |    nil    nil
   |    true    true
   |    [n1,...,nm]    vector
   |    ...   
Figure 4.5:Instructions

Figure 4.2 shows the structure of programs. As in sourir, each function is versioned. The versions are compiled with different contextual assumptions and have different levels of optimization applied. The assumptions are recorded in a context C and dispatched using context dispatch. A program is thus a set of functions, each with one or more versions with a function body and the promises it creates. Promise and function bodies are sets of basic blocks. Functions, promises, and basic blocks are labeled by names. All labels (id) are unique. Promises and functions in Figure 4.2 should not be confused with values that represent closures and promises; those are shown in Figure 4.4. A closure is a pair with a function and its environment, while a promise value is a triple with code, its environment, and a result. An environment is a sequence of bindings from variables to values.

Figure 4.5 shows the remainder of the PIR grammar. PIR is in SSA form: each statement (st) is constructed such that its result is assigned to a unique register. While there is only one kind of register in PIR, to help readability, our convention is to use (%n) for registers that hold environments (or environment literals) and (%n) for everything else. PIR has instructions for the following operations: performing arithmetic; branching; deoptimizing a function; applying a closure; jumping to a basic block; loading arguments, constants, functions, and variables; creating promises, environments, and closures; forcing a promise; phi merges; returning values; and storing variables. Most of the instructions are unsurprising (and some have been elided for brevity). We focus our explanation here on MkEnv, MkArg, MkClosure, and Force. And later, when we explain speculation, Assume, Deopt, Framestate, and Checkpoint .

MkEnv.

This instruction takes initial variables and a parent environment as arguments:
MkEnv  ((x = a)  : env)

The resulting environment contains the bindings (x = a) and is scoped inside env. By default functions start out with an environment that contains all their declared arguments. Thus, a function defined at the top level with an argument called a has the following body:

%0
=
LdArg (0)
%1
=
MkEnv ( a = %0   : G)
...

Variables can be added or updated with StVar and read with LdVar . The latter returns the value of the first binding for the variable in the stack of environments. That value can be a promise and may or may not be evaluated. When searching for a function, LdFun is used instead. The instruction evaluates promises and skips over non-function bindings. An optimization pass converts LdFun into LdVar when possible.

MkArg.

This instruction creates a promise from an expression in the source program and an environment:
MkArg  (id, env)

The instruction is mainly used to create promises for function arguments. A call such as f(a+b) translates to a load of a function f, the creation of a promise with body p1 and a call. Assuming the environment is called %n, we get the following code:

p1
%0
=
LdFun ( f , %n)
%1
=
MkArg ( p1 , %n)
%2
=
Call %0  (%1 ) %n
%0
=
LdVar ( a , %n)
%1
=
LdVar ( b , %n)
%2
=
Force (%0 ) %n
%3
=
Force (%1 ) %n
%4
=
Add (%2 , %3 ) %n
Return (%4 )

The body of the promise contains two reads for a and b whose results get forced, a binary addition, and a return. The code is known statically, while the environment in which it is evaluated is a runtime value.

Force.

This instruction takes any value as input. In case the input is a promise it is evaluated (recursively if needed) and the resulting value is returned. In case it is not a promise the value is returned unchanged:
Force  (a) env

Note that env is a synthetic argument that is not needed for evaluation but describes a data dependency. The promise could access the current environment using reflective operations. If a is not a promise then a is returned intact. If a =< P,ve, _ >, then P is evaluated in ve, and the result is stored in the data structure and returned. Otherwise, if a =< P,ve,v >, then v is returned.

Typed Instructions.

PIR instructions are typed, which allows more precise register types. The types include environments, vectors, scalars, closures, lists, etc. The type system also distinguishes between values and both evaluated and unevaluated promises. We omit additional details as the types are not relevant for the optimizations presented here.

4.5 Scope Resolution

Scope resolution is an abstract interpretation over stores. The transformation draws inspiration from the mem2reg pass in LLVM. Ř first compiles variables to environment loads and stores and later lowers them to registers. The domain s of the analysis consists of sequences of abstract environments. Assume that we have environments %1 ,,%n and variables x1xm. Then, an abstract state s is a n m vector of sets of locations. A location is either a program point l or 𝜖 if the variable is undefined. We write si,j to denote the abstract value of variable xj in the environment accessed through register %i. The value denotes the set of all locations—it represents the case where we do not know anything about a particular variable. The bottom value is represented by a vector where each element is the empty set. The analysis is defined by a transition function over statements and a merge function over states.

Transition Function.

The transition function takes three arguments: a program point l, a statement st, and an abstract state s. The result is a new abstract state s. We discuss the three interesting cases. Let st be the creation of a new environment stored in register %i with some values for variables x

1

,,x

j

:
% i = MkEnv (x1 = a1,...,xj = aj  : %k)

Then, the resulting state sis initialized with location l for variables x1,,xj in the environment %i. Other variables in that environment are set to 𝜖 to denote that they are undefined.

(s)p,q = (
||{ {l}   p = i,xq ∈ x1,...,xj
  {𝜖}   p = i,xq ∕∈ x1,...,xj
||( s    otherwise
   p,q

For the second interesting case let st be the store instruction which defines or updates variable xi to a value held in register %j for environment %k:

StVar  (xi, %j, %k)

This operation simply overwrites the state for that variable xi with the current location.

(s)p,q = {
 {l}   p = k, xq = xi
 sp,q  otherwise

The last case we describe is when an instruction taints the environment, i.e., any instruction that may perform reflective manipulation; this includes Call, Force, and LdFun. For example, let st be a call instruction:

Call  a0 (a1,..,an) %k

To be safe, the defined parts of the abstract state are set to , i.e., we know nothing after this point.

(s)p,q = {
  ⊤   sp,q ⁄= ∅

  ∅   otherwise

We can improve precision by tracking parent relations between environments to avoid tainting them all. Also, the analysis can be extended to be interprocedural across Call or Force instructions. The state of a scope resolution in progress can be queried to resolve the target of a Call or Force instruction. Other mitigations to avoid tainting the state, such as speculative stub environments or special treatment for non-reflective promises, are discussed later.

Merge.

States are merged at control-flow joins. The merge operation is pointwise set union.

Transformation.

Scope resolution computes the reachable stores. Based on its results, some LdVar instructions can be removed. Given a load instruction %i = LdVar (

x

j

, %k) with an abstract state s, there are three possible cases. First, when s

k,j

= {l}, i.e., the only observable modification to x

j

is by the instruction at l, we can simply replace %i with the register stored by the instruction at that location. The second case is s

k,j

= {l

1

,,l

n

}, i.e., depending on the flow of control any one of the n instructions could have caused the last store. We use an SSA construction algorithm [

Cytron, Ferrante, Rosen, Wegman, and Zadeck

1991

] to combine all stored registers in a phi congruence class. We replace %i with the Phi instruction produced by the SSA construction. Finally, the third case occurs if s

k,j

= or 𝜖 s

k,j

, i.e., the load cannot be resolved and no optimization is applied.

Example.

We conclude with an example with flow-dependent stores:
function () { 
  if (...)  x <- 1 
  else      x <- 2 
  x 
}

The translation starts by creating an empty environment. After some branching condition either 1 or 2 is stored in x. Finally, the value of x is loaded, forced, and returned.

BB0 :
%1
=
MkEnv (  : G)
%2
=
...
Branch (%2 , BB1, BB2)
BB1 :
%4
=
LdConst  1
StVar ( x , %4 , %1 )
Jump BB3
BB2 :
%7
=
LdConst  2
StVar ( x , %7 , %1 )
Jump BB3
BB3 :
%10
=
LdVar ( x , %1 )
%11
=
Force (%10 ) %1
Return (%11 )

This function has one environment (%1 ) and one variable (x), thus it is represented as vector of length one, starting empty ⟨{}⟩. The scope analysis derives an abstract state ⟨{5,8}⟩ (where 5 and 8 are the locations of both stores). Therefore we place a Phi instruction in BB3 to join those two writes. We can replace the load %10 with this phi.

BB0 :
%1
=
...
Branch (%2 , BB1, BB2)
BB1 :
%4
=
LdConst  1
Jump BB3
BB2 :
%7
=
LdConst  2
Jump BB3
BB3 :
%10
=
Phi (BB1 : %4 ,BB2 : %7 )
Return (%10 )

Since the load is statically resolved, dead store elimination is able to remove both StVar instructions. Combined with an escape analysis, the environment is also elided. The Force instruction is removed, since we know that the value is either of the two constants and not a promise.

Promise Inlining

The analysis needed for promise inlining is a simple dataflow analysis. The values of interest are promises created by MkArg. The analysis uses a lattice for the state of a promise that starts at bottom, , and can either be forced at program point l or leaked (), and tops at . There is one such state per promise-creating instruction, thus the abstract state is a vector of length n where n is the number of MkArg instructions in the function. We present the abstract interpretation by discussing the transition function that takes a statement and an abstract state, and returns a new abstract state, and the merge function that combines two states.

Transition Function.

The abstract state is initialized to

. There are three interesting cases.

First, given an instruction Force (%i) %j at location l, where % i is a MkArg instruction, we update the abstract state of the promise %i as follows: if the state is , then it is set to l, indicating that this is the dominating Force. If the state is the result is , otherwise it stays unchanged. Second, given an instruction MkEnv (x1 = a1,...,xj = aj  : %p), for any input a1,,aj that refers to a promise, the state of that promise is set to leaked () if it is , otherwise it stays unchanged. Third, given any instruction which could evaluate promises, such as Call, Force , or LdFun, all escaped () promises are updated to .

Therefore, promises used first in a MkEnv and then in a Force instructions will end up at and not be inlined. If we were to inline such a promise it would cause the result slots of the promise in the environment to be out of sync with the result of the inlined expression. It is possible to support some of those edge cases with an instruction to update the result slot of a promise.

Merge.

When merging abstract states, identical states remain and disagreeing states become . The latter can happen for example in

Listing 4.1

.
1function(a) { 
2  if(...)  a 
3  a 
4}
Listing 4.1:conditional declaration

Where a is forced depends on a condition; it could be either line 1 or 2. While it would be possible to track those cases more accurately, we did not need it in practice yet.

Code Transformation.

The promise inlining pass uses the analysis to inject promises at their dominating force instruction. As a precondition, we need a MkArg and the corresponding Force instruction to be in the same function. This only happens after inlining, since initially creation and evaluation of promises is always separated by a call. The promise inliner will inline the promise body at the location of the dominating force, update all uses with the result of the inlinee, and remove both the MkArg and the Force .

If this promise originates from a LdArg instruction, then the promise originates from an argument passed to the current function. We do not know its code and therefore cannot inline it. On the other hand we can still replace all uses of the dominated Force instruction with the dominating Force instruction.

Example.

We now present an example that combines scope resolution and promise inlining, shown in

Figure 4.6

.
g <- function() { 
  a <- 1 
  f <- function(b) b+a 
  f(2) 
}
Figure 4.6:An example with promises to be inlined.

An inner closure f is called with 2 as an argument. f captures the binding of a from its parent environment. This translates (after scope resolution) to the PIR code shown in Figure 4.7. The parent environment O denotes the environment supplied by MkClosure. Since f is an inner function, it needs to be closed over the environment at its definition.

g
pr0
f
%7
=
LdConst  1
%8
=
MkEnv ( a = %7   : G)
%9
=
MkClosure ( f , %8 )
%10
=
MkArg ( pr0 , %8 )
%11
=
Call %9  (%10 ) %8
%12
=
Force (%11 ) %8
Return (%12 )
%13
=
LdConst  2
Return (%13 )
%1
=
LdArg (0)
%2
=
MkEnv ( b = %1   : O)
%3
=
Force (%1 ) %2
%4
=
LdVar ( a , %2 )
%5
=
Force (%4 ) %2
%6
=
Add (%3 , %5 ) %2
Return (%6 )

Figure 4.7:PIR translation of the function from Figure 4.6.
g
   inlinee begins
   inlinee ends
%7
=
LdConst  1
%8
=
MkEnv ( a = %7   : G)
%10
=
MkArg ( pr0 , %8 )
%2
=
MkEnv ( b = %10   : %8 )
%3
=
Force (%10 ) %2
%4
=
LdVar ( a , %2 )
%5
=
Force (%4 ) %2
%6
=
Add (%3 , %5 ) %2
%12
=
Force (%6 ) %8
Return (%12 )

Figure 4.8:After inlining function f in Figure 4.7.

The first step necessary to get the promise creation and evaluation into the same PIR function, is to inline the inner function f. After this transformation we obtain the code in Listing 4.8. The open environment O is replaced with %8 . And the argument LdArg (0) of the callee is replaced by the MkArg  ( pr0 , %8 ) instruction of the caller.

g
   inlinee begins
   inlined promise begins
   inlined promise ends
   inlinee ends
%7
=
LdConst  1
%8
=
MkEnv ( a = %7   : G)
%10
=
MkArg ( pr0 , %8 )
%2
=
MkEnv ( b = %10   : %8 )
%13
=
LdConst  2
%6
=
Add (%13 , %7 ) %2
Return (%6 )

Figure 4.9:After inlining promise p r0 in Listing 4.8.

Now, we can identify the dominating Force instruction at %3 . Therefore, the promise inliner replaces the Force instruction with the body of the promise, yielding the result in Listing 4.9 (after another scope resolution pass).

Only after these steps finish can traditional compiler optimizations, such as escape analysis on the environment, dead code elimination, and constant folding, reduce the code to a single LdConst instruction.

4.6 Discussion

Designing an intermediate representation for R has been a surprisingly difficult endeavor. Our goal was to arrive at a code format that captures the intricacies of the language while enabling compiler optimizations. Our explicit goals were to distinguish between arguments that need lazy evaluation and ones that do not, to distinguish between variables that are truly local and can be optimized and variables that must be allocated in environments and may be exposed through reflection, to allow for elision of environments when they are known to not be needed.

To achieve this, we designed PIR, the intermediate representation of the Ř compiler. It has explicit instructions for creating environments, creating promises, and evaluating promises. Explicit modeling of constructs that are to be optimized away is a key design ingredient. For example, explicit environments allow functions to be inlined without fully resolving all R variables upfront.

The challenge presented by R is that it requires solving many problems at once. To get rid of laziness, one must track the flow of arguments and understand where they may be forced. To track arguments, one has to reason about environments and how they are manipulated. To discover if environments change, one has to analyze promises. The approach presented so far provides the basic tools, but often does not allow us to break these circular dependencies in the optimizer. Therefore more optimistic assumption based optimization strategies are required, which are discussed next.

4.7 Assumptions in PIR

PIR features speculative optimizations using the Assume instruction. In sourir the assume instruction combines speculation, deoptimization metadata and OSR-exit point. It provides a clean and simple abstraction for reasoning about speculation at a high level. In contrast to sourir, in Ř OSR transitions from native code to bytecode for deoptimization and from bytecode to native code for OSR-in. For now we describe the transition at the PIR level, the lowering to LLVM and thus the mapping to native code are shown later.

In practice, deoptimization always returns to the baseline and not some intermediate version, because providing an entry point for deoptimization in optimized code would severely restrict its optimizations. However, this is not an inherent theoretical limitation and the assume model allows for this possibility.

For the implementation we decided to split the different responsibilities of the sourir assume instruction into different PIR instructions.

Framestate

This instruction describes one interpreter frame. For instance
Framestate  ( pc ,%1 ,%2 ,%3 ,env = %4 ,next = nil)

represents one frame of the bytecode interpreter, where the program counter register contains pc, the operand stack %1 ,%2 ,%3 , and the R environment is %4 . Framestates can be joined to represent inlined frames, in which case next points to the parent frame. Semantically they are nops and could also be represented as a value instead of an instruction. We chose this representation for ease of implementation.

Framestates are inserted by the first pass of the compiler, that translates from RIR bytecode to PIR instructions. As such the creation is straight-forward, since this pass already has to maintain an abstract representation of the interpreter’s operand stack for the translation. Framestates are attached to calls for inlining, to forces for inlining promises, and to checkpoints.

Checkpoint

This instruction marks the OSR-exit point in PIR. It points to a code block to perform the deoptimization. This code block ends in a Deopt instruction that points to the corresponding RIR OSR-entry point.

Deopt

This instruction is a terminator instruction, like Return, but instead it unconditionally deoptimizes. It refers to a Framestate for the deoptimization metadata. For instance Deopt (

%1 ) uses the information from a %1 = Framestate

to synthesize the required interpreter frames.

Assume

Finally, the speculating instruction, that dynamically checks assumptions and points back to a Checkpoint. It must be the case that there is no observable effect between this instruction and its checkpoint.

As an example consider the PIR code in Figure 4.10 with a complete deoptimization point and speculative optimizations.

BB0 :
...
cp
%1
=
Checkpoint BB1
...
%2
=
LdVar ( data , G)
bool
%3
=
Isreal(%2 )
Assume (%3 ) %1
...
Return (%2 )
BB1 :
fs
%10
=
Framestate ( pc1 ,%j,env = G,next = nil)
env
%11
=
MkEnv ( foo = %k  : G)
fs
%12
=
Framestate ( pc2 ,%p,%q,env = %11 ,next = %10 )
Deopt (%12 )

Figure 4.10:OSR exit point in PIR

In this example we see a speculative optimization on the type of a variable called data. The deferred instructions at label BB1 represent the materialization of the environment and describe the framestates required to exit from this checkpoint. They describes an Ř bytecode execution context with two frames. In general, Framestate instructions can be chained to describe the states of multiple inlined functions. The basic block BB1 can contain arbitrary deferred instructions that are only executed upon deoptimization, such as in this example the creation of an environment. This is used frequently to defer computations which are not needed in the optimized code. As an example, R has a call-by-need semantics, and function arguments are passed as thunks, so-called promises. After inlining, the actual structure to hold the delayed computation typically only has to be created on deoptimization, and the instructions for creating promises can be delayed into deoptimization branches.

Let us compare Checkpoint, Framestate, Deopt, Assume with

assume  e else ξ ξ

from sourir. A Framestate corresponds to ξ, the linked additional framestates to ξ. A Checkpoint corresponds to a fresh assume instruction inserted by the initial fresh version pass, where the deoptimization metadata is pushed into a deferred code block. This code block referred to by the Checkpoint is a novel PIR feature. In sourir the metadata ξ contains only silent expressions and no deferred code is supported. The Deopt instruction is needed to terminate the deferred code. Finally the Assume instruction corresponds to the injecting assumptions transformation in sourir, where a new guard is added to an existing OSR-exit point. The fact that there can be additional silent instructions between Checkpoint and Assume corresponds to the unrestricted deoptimization transformation in sourir. Instead of copying and moving an assume instruction forward, like in sourir, here we only add the guard and refer back to the Checkpoint .

Delaying Environments

To avoid creating an environment at runtime whenever a compiled function performs any kind of speculative optimization, creation of environments should be delayed as much as possible. Optimizations are allowed to move MkEnv instructions into branches and even over writes to that environment. When that happens, the StVar is removed and the value is added to the initialization list. When an environment is used by multiple deoptimization points, then this is not sufficient, since each deoptimization branch will require the environment in a different state.

Partial escape analysis [Stadler, Würthinger, and Mössenböck2014] intends to delay an allocation to only those branches where the object escapes. Similarly, in PIR we aim to materialize an up-to-date environment in each deoptimization branch, allowing us to elide the environment in the main path. This requires replaying stores between the original environment creation and the Deopt instruction. We use the output of scope analysis to determine the state of the environment in the deoptimization branch. A sufficient condition is that at the Deopt instruction none of the variables in the abstract state s (see sec. 4.2) is .

Assume there is an StVar ( bar , %j, %1 ) instruction somewhere between MkEnv and Deopt in the following example.

BB0 :
%1
=
MkEnv ( foo = %i  : %0 )
...
Checkpoint BB1
BB1 :
fs
%3
=
Framestate ( pc ,%1,,%n,env = %1 ,next = nil)
Deopt (%3 )

We now proceed to assemble a synthetic environment to replace %1 in the deoptimization branch. In this case the abstract environment %1 according to scope resolution is such that foo is defined by the MkEnv instruction and bar is defined by the StVar instruction. In section 4.5 we presented our technique to replace a LdVar instruction with a PIR register. We now reuse the same technique to capture the current values of foo and bar as registers and then include them in a fresh MkEnv instruction:

BB0 :
%1
=
MkEnv ( foo = %i  : %0 )
...
StVar ( bar , %j, %1 )
...
Checkpoint BB1
BB 1 :
%3
=
MkEnv ( foo = %i, bar = %j  : %0 )
fs
%4
=
Framestate ( pc ,%1,,%n,env = %3 ,next = nil)
Deopt (%4 )

Assuming we are able to materialize a copy of the environment in every deoptimization branch, it is then possible to remove the original MkEnv. This transformation can duplicate variables for each deoptimization branch. They can be cleaned up later using some form of redundancy elimination, such as global value numbering.

Contrary to replacing LdVars, it is possible to materialize environments even when the analysis results contain 𝜖. For those cases a runtime marker is used to indicate the absence of a binding. MkEnv will simply skip a particular binding if its input value is equal to this marker value.

Stub Environments

If an environment is locally resolved, but could be tainted during a call using reflection, then we speculatively elide that environment and replace it by a stub. At runtime a stub environment has the same structure as a normal environment shown in

Figure 4.4

, but a more compact representation, since it does not need to support adding or removing variables. If the stub environment is modified then it is transparently converted into a full environment. In PIR, stub environments are created by a structurally identical variant of the MkEnv instruction. After a call we check if the stub was materialized, in which case we deoptimize the current function. Consequently, analyses on PIR can assume stub environments to not experience any non-local modifications.

Lowering to LLVM

Ř has an OSR-out implementation to transition from native code to the interpreter in case of mis-speculation. It is realized by lowering the deoptimization points from the previous section to LLVM. We use the same approach for all different kinds of speculations, be they on the stability of call targets, the declared local variables of closures, uncommon branches, primitive types, and loops over integer sequences.

Ř also features an OSR-in implementation, a direct side-product of our work to implement deoptless. It can be used to tier-up from the interpreter to optimized code, and is triggered in long-running loops. Supporting OSR-in adds little complexity to the compiler. The relevant patch adds 300 and changes 600 lines of code. Mainly, the bytecode to IR translation has to support starting at an offset, and the current values on the interpreter’s operand stack need to be passed into the optimized continuation.

OSR-out

In Ř, OSR exits are not performed by externally rewriting stack frames. Instead, an OSR exit point is realized as a function call. Let us consider the OSR exit point in Figure 4.10. The backend of the Ř compiler generates code using LLVM. As can be seen in Listing 4.2, the Assume is lowered to a conditional branch and the OSR exit is lowered to a tail-call.

       br %isType, cont, osr 
osr: 
       ... 
  %f = alloca FrameState 
  %r = alloca Reason 
     ; store current function, 
     ; frame contents, and more 
     ; metadata into %f and %r 
  %a = tail call Value @deopt(%f, %r) 
       ret %a 
cont:
Listing 4.2:OSR exit from Figure 4.10 in LLVM

The osr block executes all the deferred instructions, notably it populates buffers for the local variables captured by the framestate and the deoptimization reason. Finally, a deopt function is called. This primitive performs the actual deoptimization, i.e., it invokes the interpreter, or, in the case of deoptless, dispatches to an optimized continuation.

The deopt primitive is able to recreate multiple interpreter contexts as we can see in the pseudocode in Listing 4.3.

Value deopt(FrameState* fs, Reason* r) { 
  logDeoptimization(r); 
  pushInterpreterState(fs); 
  if (fs->next) 
    push(deopt(fs->next, r)); 
  return interpret(fs->pc, fs->env); 
}
Listing 4.3:Pseudocode for deoptimization implementation

First, the outer interpreter context is synthesized, i.e., the necessary values pushed to the interpreter’s operand stack. Then, the inner frames are recursively evaluated, their results also pushed to the operand stack, as expected by the outer frame. Finally, the outermost code is executed, and the result returned to the deoptimized native code, which directly returns it to its caller.

The osr basic block in Figure 4.10, as well as the deopt call, are marked cold in LLVM. This causes LLVM optimization passes and code generation to layout the function in such a way that the impact of the osr code on the performance of the rest of the function is minimal. However, the mere presence of the additional branch might interfere with LLVM optimizations, and other OSR implementers therefore chose to use the LLVM statepoint primitive. The statepoint API provides access to metadata describing the stack layout of the generated function. This stack layout allows an external deoptimization mechanism to read out the local state without explicitly capturing it in LLVM code. This is a trade-off, and the impact is in our opinion limited. For example, in the concrete case of Listing 3.3, we were not able to measure any effect on peak performance. In fact, when we unsoundly dropped all deoptimization exit points in the backend, the performance was unchanged. There was, however, an effect on code size with an overhead of 30% more LLVM instructions. The implementation strategy of using explicit calls to deopt for Ř was chosen for ease of implementation long before deoptless was added. In a lucky coincidence, this strategy is very efficient in extracting the internal state of optimized code compared to an external deoptimization mechanism, and therefore very well suited for deoptless.

OSR-in

OSR-in allows for a transition from long-running loops in the bytecode interpreter to native code. To that end, a special continuation function is compiled, starting from the current bytecode, which is used only once for the OSR-in. The full function is compiled again from the beginning the next time it is called. This avoids the overhead of introducing multiple entry-points into optimized code, for the price of compiling these functions twice. Since OSR-in is not a very frequent event, the trade-off is reasonable.

The mechanism is triggered by counting the number of backward jumps in the interpreter. When a certain number of loop iterations is reached, the remainder of the function is compiled using the same compiler infrastructure that is used to compile whole functions. The only difference is that we choose the current program counter value as an entry point for the translation from bytecode to IR. Additionally, we pre-seed the abstract stack used by the frontend of the Ř compiler with all values on the interpreter’s operand stack. In other words, the resulting native code will receive the current contents of the operand stack as call arguments. OSR adds the lines, shown in Listing 4.4, to the implementation of the branch bytecode.

case Opcode::branch: { 
  auto offset = readImmediate(); 
  if (offset < 0 && OSRCondition()) { 
    if (auto fun = OSRCompile(pc, ...)) { 
      auto res = fun(...); 
      clearStack(); 
      return res; 
    } 
  } 
  ... 
}
Listing 4.4:Pseudocode for OSR-in implementation

An interesting anecdote from adding OSR-in to Ř is that out of all the optimization passes of the normal optimizer, only dead-store elimination was unsound for OSR-in continuations. The reason is that objects can already escape before the OSR continuation begins, and thus escape analysis would mistakenly mark them as local.

4.8 Context Dispatch

One particular problem with scope analysis presented earlier is that, because of R’s semantics, any instruction that evaluates potentially effectful code taints the abstract environment. There are two kinds of non-local effects: callees may affect functions upwards the call stack by accessing the caller’s environment, and callers pass promises that may affect functions downwards the call stack, when those functions force the promises. To make scope resolution useful in practice, the impact of these non-local effects should be somewhat mitigated. For instance, we rely on inlining to reduce the number of Call and Force instructions. There is also the possibility to speculatively assume calls do not change the environment using stub environments.

However, promises are a main source of imprecision when Ř tries to analyze R code. When a function argument is accessed for the first time the optimizer must be able to rule out non-local effects to the current function. To that end we compile versions of functions under the assumption that already evaluated values, or at least non-reflective promises are passed to it. This specialization, among many others, is implemented using context dispatch. Given the complexity of function calls in R, our design focuses on properties that can optimize the function call sequence and allow the compiler to generate better code within the function.

Contexts

The goal of context dispatch is to drive optimizations. Accordingly, we design contexts in Ř mainly driven by the seven headaches for optimizing R introduced in 4.1. Contexts are represented by the Context structure presented in Listing 4.5, which consists of two bit vectors (argFlags and flags) and a byte (missing). The whole structure fits within 64 bits, with two bytes (unused) reserved for future use. The EnumSet class is a set whose values are chosen from an enumeration.

enum class ArgAssumption { 
  Arg0Eager,     ..., Arg7Eager, 
  Arg0NotObj,     ..., Arg7NotObj, 
  Arg0SimpleInt, ..., Arg7SimpleInt, 
  Arg0SimpleReal, ..., Arg7SimpleReal, 
}; 
enum class Assumption { 
  NoExplicitlyMissingArgs, CorrectArgOrder, NotTooManyArgs, NoReflectiveArg, 
}; 
struct Context { 
  EnumSet<ArgAssumption, uint32_t> argFlags; 
  EnumSet<Assumption, uint8_t> flags; 
  uint8_t missing = 0; 
  int16_t unused = 0; 
};
Listing 4.5:Context data structure

More specifically, argFlags is the conjunction of argument predicates (ArgAssumption) for the first eight arguments of a function. For each argument position N < 8, we store whether the argument has already been evaluated (ArgNEager), whether the argument is not an object, i.e., it does not have a class attribute (ArgNNotObj), whether the value is a scalar integer with no attributes (ArgNSimpleInt), and whether the value is a scalar double with no attributes (ArgNSimpleReal). Any subsequent arguments will not be specialized for. The limit is informed by data obtained by Morandat, Hill, Osvald, and Vitek [2012], suggesting that the majority of frequently called functions have no more than three arguments and that most arguments are passed by position.

The flags field is a set of Assumption values that summarize information about the whole invocation. The majority of the predicates are related to argument matching. In R, the process of determining which actual argument matches with formal parameters is surprisingly complex. The GNU R interpreter does this by performing three traversals of a linked list for each function call. The Ř compiler tries to do this at compile time, but some of the gnarly corners of R get in the way. For this reason, contexts encode information about the order of arguments at the call site. Thus flags has a predicate, NoExplicitlyMissingArgs, to assert whether any of the arguments is explicitly missing. This matches in three cases: when an argument is explicitly omitted (add(,2)), when an argument is skipped by matching (add(y=2)), and when a call site has more missing arguments than expected in the compiled code. CorrectArgOrder holds if the arguments are passed in the order expected by the callee. NotTooManyArgs holds if the number of arguments passed is less than or equal to the number of parameters of the called function. NoReflectiveArg holds if none of the arguments invoke reflective functions. Finally, missing arguments that occur at the end of an argument list are treated specially; missing records the number of trailing missing arguments (up to 255).

Ordering

Recall that contexts have a computable partial order, which is used to determine if a function version can be invoked at a particular program state. For example, let Cbe the current context of program state S, F be a function invoked at S, and C,V be a version in F. Then the implementation can dispatch to C,V if C< C.

In Ř, the order between contexts, C< C , is defined mainly by set inclusion of both assumption sets. For trailing missing arguments, there are two cases that need to be considered. First, if C assumes NotTooManyArgs, then Cmust have at least as many trailing missing arguments as C. Otherwise, this implies Chas more arguments than C expects, contradicting NotTooManyArgs. Second, if context C allows any argument to be missing, then it entails a context Cwith fewer trailing missing arguments (i.e., more arguments). The reason is that missing arguments can be passed as explicitly missing arguments, reified by an explicit marker value for missing arguments. If we invert that property, it means that a context with NoExplicitlyMissingArgs does not accept more trailing missing arguments.

bool Context::smaller(const Context& other) const { 
  // argdiff positive = "more than expected", 
  //         negative = "less than" 
  int argdiff = (int)other.missing - (int)missing; 
  if (argdiff > 0 && 
      other.flags.contains(Assumption::NotTooManyArgs)) 
    return false; 
  if (argdiff < 0 && 
      other.flags.contains(Assumption::NoExplicitlyMissingArgs)) 
    return false; 
  return flags.includes(other.flags) && 
         typeFlags.includes(other.typeFlags); 
}
Listing 4.6:Implementation of Context ordering

PIC

Figure 4.11:An example for the order of some Contexts

Some example contexts with their order relation (increasing from left to right) are shown in Figure 4.11. Contexts with more flags are smaller, contexts with a greater missing value are smaller, and contexts with NoExplicitlyMissingArgs require the same number of missing arguments to be comparable. The comparison is implemented by the code of Listing 4.6. Excluding mov and nop instructions, the smaller comparison is compiled to fewer than 20 x86 instructions by GCC 8.4.

Evaluating Contexts

For every call the current context is needed, which is partially computed statically and completed dynamically. The Ř optimizer enables static approximation of many of the assumptions. For example, laziness and whether values