Constructing a baseline JIT for Lua mechanically |

That is the Half 2 of a sequence. Be at liberty to learn the prequel for extra context: Building the fastest Lua interpreter automatically

Constructing VM for a dynamic language takes a ton of engineering. The perfect-performing VMs (e.g., JavaScriptCore, V8, SpiderMonkey) make use of no less than 3 VM tiers (interpreter, baseline JIT and optimizing JIT), and pervasively use hand-coded meeting in each VM tier. Optimizations resembling inline caching and sort hypothesis are required to get excessive efficiency, however they require excessive experience and introduce extra engineering complexity.

Deegen is my analysis meta-compiler to make high-performance VMs simpler to put in writing. Deegen takes in a semantic description of the VM bytecodes in C++, and use it as the one supply of fact to mechanically generate a high-performance VM at construct time, as illustrated under.

In a prior post, we used Deegen to mechanically generate the quickest Lua 5.1 interpreter so far, outperforming LuaJIT’s interpreter by a median of 34% throughout a wide range of Lua benchmarks. The VM was named LuaJIT Remake, though it had no JIT tiers at the moment.

Immediately, after months of extra work, LuaJIT Remake is lastly a JIT-capable VM. It’s now geared up with a state-of-the-art baseline JIT compiler, additionally mechanically generated by Deegen. The baseline JIT options:

• Extraordinarily quick compilation pace.
• Excessive-quality machine code (underneath the design constraints of a baseline JIT).
• Automated name inline caching (IC) with two modes (direct/closure name).
• Automated generic inline caching (IC) driven by Deegen API.
• Self-modifying-code-based IC implementation for finest efficiency.
• Sizzling-cold-splitted JIT code for much less branches and higher code locality.

It is very important be aware that the baseline JIT is generated from the identical bytecode semantic description that Deegen makes use of to generate the interpreter. Subsequently, for a language implementer, the baseline JIT comes free of charge:

• No must have any meeting data.
• No must manually engineer the JIT.
• No must manually preserve the JIT up to date with new language options.

As a result of Deegen does all of the work mechanically!

After all, that is no straightforward feat. So as to generate the baseline JIT mechanically, a sophiscated build-time pipeline is employed, as illustrated under.

As a facet be aware, LLVM is barely used at construct time to generate the JIT. The generated baseline JIT is self-contained, and doesn’t use LLVM at runtime.

At runtime, the generated baseline JIT generates machine code utilizing Copy-and-Patch (we’ll cowl it in a minute). Besides that, it closely follows the design of the baseline JIT in JavaScriptCore, and has employed most of their optimizations. As such, we declare that our baseline JIT qualifies as a state-of-the-art.

In the remainder of the publish, we’ll discover the internals of how Deegen generates the baseline JIT in additional element. It’s organized as follows:

• A delicate introduction of the relavent backgrounds (VM, JIT, IC, and many others.).
• An outline of the Copy-and-Patch approach, the core software employed by the generated JIT to generate machine code at runtime.
• How Deegen additional extends Copy-and-Patch to completely automate the method and match it for the domain-specific use instances of dynamic languages.
• An end-to-end instance of the machine code generated by the baseline JIT.
• Efficiency analysis and conclusion ideas.

Background

The right way to Generate Machine Code?

A typical resolution utilized by many (JSC, V8, LuaJIT, and many others) is a hand-coded assembler. The assembler gives APIs (e.g., EmitMovRegReg64) to the JIT, which the JIT makes use of to emit meeting directions as machine code one after the other.

Nevertheless, such an method is clearly infeasible for a meta-compiler like Deegen, as our enter is expressed as C++ bytecode semantics.

So can we use LLVM straight at runtime to generate code? Sadly that is additionally impractical, as LLVM’s compilation pace is too slow even for a heavyweight optimizing JIT, to not point out a baseline JIT the place quick compilation is a high concern.

Copy-and-Patch: the Artwork of Repurposing Current Instruments

The answer is a paper I wrote years in the past: Copy-and-Patch Compilation.

In a single sentence, Copy-and-Patch is a trick that enables one to generate code with out realizing something about generate code.

How is that even attainable? Whereas the paper is lengthy, the trick is definitely very simple, which I’ll clarify right here.

Think about the next C++ perform:

1
2
3
4
5

int evaluate_lhs();
int evaluate_rhs();
int evaluate_add() {
  return evaluate_lhs() + evaluate_rhs();
}

When the C++ compiler compiles the above code, it is aware of nothing in regards to the definition of evaluate_lhs and evaluate_rhs. However it may possibly one way or the other produce an object file, and the linker can hyperlink the item file to any definition of evaluate_lhs and evaluate_rhs, and the ultimate executable would simply work.

Relocation = Code Era

What does it imply? The item file should include structured info on hyperlink evaluate_add in opposition to any definition of evaluate_lhs and evaluate_rhs. So if we parse the item file to get that data, at runtime, we will act because the linker, and “hyperlink” evaluate_add in opposition to any runtime-known evaluate_lhs and evaluate_rhs of our option to carry out an add. That is successfully a JIT!

After all, the “structured info” has its formal identify: linker relocation data. However the identify just isn’t essential. The essential factor is so long as we parsed out these info, we will use them at runtime to emit executable code. And this course of is extraordinarily low-cost: all it takes is a memcpy adopted by a couple of scalar additions, thus the identify “Copy-and-Patch”.

For instance, the evaluate_add we simply noticed will produce an object file with the next contents:

1
2

evaluate_add:
  53 e8 00 00 00 00 89 c3 e8 00 00 00 00 01 d8 5b c3 

with the next linker relocation file:

1
2

offset = 2, sort = R_X86_64_PLT32, sym = evaluate_lhs, addend = -4
offset = 9, sort = R_X86_64_PLT32, sym = evaluate_rhs, addend = -4

Then, the next copy-and-patch logic would enable one to JIT this perform at any handle with any desired evaluate_lhs and evaluate_rhs targets:

1
2
3
4
5
6
7
8
9
10
11

void codegen(uint8_t* dst, uint8_t* lhsFn, uint8_t* rhsFn) {
  
  constexpr uint8_t code[] = { 
    0x53, 0xe8, 0x00, 0x00, 0x00, 0x00, 0x89, 0xc3, 
    0xe8, 0x00, 0x00, 0x00, 0x00, 0x01, 0xd8, 0x5b, 0xc3 };
  
  memcpy(dst, code, sizeof(code));
  
  *(uint32_t*)(dst + 2) = (uint32_t)(lhsFn - (dst + 2) - 4);
  *(uint32_t*)(dst + 9) = (uint32_t)(rhsFn - (dst + 9) - 4);
}

Sure, that’s the entire core trick of Copy-and-Patch: at construct time, compile the logic items we wish to JIT into object file, and parse the item file to acquire the unrelocated code and relocation data (a stencil within the paper’s terminology). At runtime, code era is just wiring up the stencils and materializing them into executable code by a copy (memcpy) and some patches (scalar additions).

Continuation-Passing Type = Department

The generated code above works, however the code high quality is depressing. Every little thing is executed by a name to a different perform, which is a number of overhead.

Nevertheless, what if one rewrites the code to continuation-passing style?

1
2
3
4
5

void continuation(int consequence);
void evaluate_add(int lhs, int rhs) {
  int consequence = lhs + rhs;
  [[clang::musttail]] return continuation(consequence);
}

Now, the calls are gone. Moreover, the perform will finish with a jmp instruction to perform continuation (because the name is a tail call). Since we’ve management over the place to place every perform at, if we put continuation proper after evaluate_add, then we will even remove the jmp to a fallthrough altogether.

After using this trick, it’s pretty straightforward to show that the generated code won’t include pointless jmp directions: all of the branches should correspond to precise management stream edges within the generated logic.

One of many fundamental causes that interpreters are sluggish is the unpredictable oblique dispatch. At this stage, our generated code has no oblique dispatch, in reality, no pointless branches in any respect. That is already an enormous speedup over an interpreter.

Tackle of Exterior Image = Runtime Fixed

One other essential cause that JITs are sooner than interpreters is the power of JIT to burn runtime constants (bytecode operands, and many others) into the instruction stream. Can we help it as effectively?

After all! The trick is straightforward:

1
2
3
4
5
6
7

extern char x;  
void continuation(uint64_t worth)
void pointer_dereference_at_fixed_offset(void* ptr) {
  
  uint64_t consequence = *(uint64_t*)((uint64_t)ptr + (uint64_t)&x);
  [[clang::musttail]] return continuation(consequence);
}

All it takes is to outline an exterior image, and use its handle because the runtime fixed we wish to use. Since by definition an exterior image is exterior, the compiler can’t assume something about the place it resides at. This provides us a solution to characterize an opaque fixed worth.

After all, the linker is aware of patch the code to make the exterior image level to the best location. Thus, we will patch it at runtime to make it characterize any runtime fixed as effectively 🙂

Operate Prototype = Register Allocation / Combinatorial Explosion = Instruction Choice

Lastly, there are two most important codegen-level optimizations: register allocation and instruction choice. Can we help them as effectively? The reply is sure. Nevertheless, these optimizations are primarily solely helpful for the static language use instances the place every bytecode solely implements quite simple logic. So to maintain this publish targeted, I cannot go into particulars.

Copy-and-Patch: Wrapping up

I wouldn’t thoughts in any respect if you happen to view Copy-and-Patch as an enormous hack: as a result of it’s! Nevertheless it works! And it really works properly!

As proven in the paper, one can use Copy-and-Patch to assemble extraordinarily quick baseline JIT that considerably outperforms the present state-of-the-arts:

Moreover, Copy-and-Patch completely fits Deegen’s wants for a JIT:

1. It doesn’t know or care about what’s being JIT’ed. The logic we wish to JIT is straight compiled by a C++ compiler into an object file at construct time. C&P merely parses the item file to supply the stencils, which might then be used to JIT code at runtime.
2. The code era at runtime is extraordinarily quick, which completely matches the requirement of a baseline JIT. Observe that we’re doing a number of costly preprocessing work, however all of them occur at construct time.

Deegen: the Artwork of Repurposing Current Instruments, Continued

Whereas Copy-and-Patch is a pleasant approach, its vanilla kind as described above remains to be not sufficient to meet Deegen’s use case. Particularly, the vanilla Copy-and-Patch nonetheless requires fairly a little bit of guide work to implement the stencils and the runtime logic, whereas in Deegen, all should be absolutely computerized.

Because it seems, absolutely automating Copy-and-Patch requires important design-level enhancements to the unique approach, which we’ll cowl on this part.

To make issues simpler to know, we’ll use the next hypothetical Add bytecode as instance (see prior post for an in depth rationalization of the code):

1
2
3
4
5
6
7
8

void Add(TValue lhs, TValue rhs) {
  if (!lhs.Is<tDouble>() || !rhs.Is<tDouble>()) {
    ThrowError("Cannot add!");
  } else {
    double res = lhs.As<tDouble>() + rhs.As<tDouble>();
    Return(TValue::Create<tDouble>(res));
  }
}

Figuring out the Runtime Constants

To get good efficiency, it’s nearly mandetory for a JIT to have the ability to burn runtime constants (bytecode operands, and many others.) into the instruction stream. In vanilla Copy-and-Patch, the programmer is required to declare the runtime constants by particular macros. So our first enchancment is to make this step computerized.

Happily that is pretty straightforward. In our case, the runtime constants are the bytecode operands, and for the IC, every part within the IC state. Since Deegen is already chargeable for producing the bytecode decoding logic and the encoding / decoding of the IC state, all we have to do is to not emit the decoding logic, however a magic perform name, in order that the later processing levels is aware of that the worth is a runtime fixed.

For instance, for Add, we all know that the bytecode slot ordinal of lhs, rhs and the output slot are runtime constants. So the bytecode semantic perform can be lowered to LLVM IR that conceptually resembles the next C logic:

1
2
3
4
5
6
7
8
9
10
11
12
13

size_t lhs_slot = __runtime_constant_lhs_slot();
size_t rhs_slot = __runtime_constant_rhs_slot();
TValue lhs = stack[lhs_slot];
TValue rhs = stack[rhs_slot];
if (!lhs.Is<tDouble>() || !rhs.Is<tDouble>()) {
  ThrowError("Cannot add!");
} else {
  double res = lhs.As<tDouble>() + rhs.As<tDouble>();
  
  size_t output_slot = __runtime_constant_output_slot();
  stack[output_slot] = TValue::Create<tDouble>(res);
  __dispatch_to_next_bytecode();
}

Correspondingly, at runtime, to ensure that the generated JIT to generate code, it must decode the bytecode struct to retrieve all of the operand values and use these values to materialize the copy-and-patch stencils: we’ll showcase the concrete generated implementation of the __codegen_Add perform (which emits machine code for Add at runtime) later within the publish.

Propagating the Runtime Constants

Acute readers might have observed that the C logic above can’t end in optimum code. Think about line 3: TValue lhs = stack[lhs_slot]. What really occurs on this line is that we’re decoding handle (uint64_t)stack + lhs_slot * 8 (since every TValue is 8 bytes). If we solely make lhs_slot a runtime fixed (as we’re doing proper now), there isn’t any means for LLVM to fold lhs_slot * 8 into a relentless (recall that at LLVM degree, a runtime fixed is basically the handle of an exterior image). Because of this, it’s going to generate less-optimal code like mov $XXXX, %rax; shl 3, %rax.

Subsequently, we’d like a custom-made LLVM fixed propagation move to establish all of the fixed expressions derived from the “root” runtime constants. Then, we should always make every fixed expression a runtime fixed. After all, this additionally implies that at runtime, to be able to populate these derived runtime constants with concrete values, the codegen perform must replay the computation of the expression utilizing the concrete values of the basis runtime constants.

After this rework, the LLVM IR of our Add instance would resemble the next C logic:

1
2
3
4
5
6
7
8
9
10
11
12
13

size_t tmp1 = __derived_runtime_constant_1();
size_t tmp2 = __derived_runtime_constant_2();
TValue lhs = *(TValue*)((uint64_t)stack + tmp1);
TValue rhs = *(TValue*)((uint64_t)stack + tmp2);
if (!lhs.Is<tDouble>() || !rhs.Is<tDouble>()) {
  ThrowError("Cannot add!");
} else {
  double res = lhs.As<tDouble>() + rhs.As<tDouble>();
  
  size_t tmp3 = __derived_runtime_constant_3();
  *(TValue*)((uint64_t)stack+tmp3) = TValue::Create<tDouble>(res);
  __dispatch_to_next_bytecode();
}

the place the derived runtime constants __derived_runtime_constant_1/2/3 are outlined as observe:

1
2
3

__derived_runtime_constant_1 := lhs_slot * 8
__derived_runtime_constant_2 := rhs_slot * 8
__derived_runtime_constant_3 := output_slot * 8

Fixing the Image Vary Assumption

As we already defined, in Copy-and-Patch, a runtime fixed is expressed by the handle of an exterior image.

Whereas it’s a neat trick that’s essential for high-quality code, it might break down and trigger miscompilation in edge instances. For instance, take into account the code under:

1
2
3
4
5
6
7

extern char x;
void f() {
  uint64_t val = (uint64_t)&x;
  if (val == 0) {
    
  }
}

LLVM would deduce that the val == 0 test is trivially false, and “optimize away” the entire if-clause. Why? As a result of val is the handle of variable x, and naturally the handle of a variable is rarely 0, good recreation.

In vanilla Copy-and-Patch, the programmer is chargeable for avoiding such nook instances. However in Deegen, the place stencils are mechanically generated, we should discover a systematic and provably-correct resolution.

So what’s the problem? You would possibly assume the problem is “image should not be null”. That’s what I initially believed as effectively, however I later realized it’s only the symptom of a a lot bigger situation.

Because it seems, in line with x86-64 ABI, each image will reside in handle vary [1, 2^31 - 2^24). This is also exactly the assumption held by LLVM, and used by LLVM to do optimizations (e.g., in the example above, it deduces that the address of a symbol must not equal 0). So the “val == 0 check” example is not the only buggy case. LLVM can, for example, do a zero extension instead of a sign extension, as it believes that the address of the symbol must have bit 31 being 0 thus a ZExt is equivalent to a SExt, causing buggy code if the runtime constant were to represent a negative value.

One might think the [1, 2^31 - 2^24) range assumption is artificial, but it isn’t. This range assumption is actually important to generate correct code. For a simple example, the code movq sym+100(%rax), %rax would not work correctly due to an int32_t overflow in the imm32 addressing mode field of the instruction, if sym were to have value 2^31 - 50.

Therefore, for a provably correct solution, we must make sure that whenever we use an external symbol to represent a runtime constant, the runtime constant we want to express must fit in [1, 2^31 - 2^24).

In Deegen, this is accomplished by a customized Constant Range Analysis pass to track the range of every constant expression based on the runtime constants. Of course, we also need to know the possible range for the “root” runtime constants – the bytecode operands, and the values captured by the IC state. Fortunately, for most of them, the range is implicit (for example, a bytecode slot is known to be a small non-negative integer, and an operand with type uint16_t obviously fits in [0, 65535]) and requires no person intervention. For the remainder, a brand new Deegen API is added so the person can inform us the vary assumption of the worth.

As soon as we discovered the confirmed vary of every runtime fixed expression, we will retrofit it into our goal vary [1, 2^31 - 2^24) by simple transformation. To explain how it works, let’s revisit our Add example:

• lhs_slot is a root runtime constant. Since it represents a bytecode slot ordinal, it is known to be a small non-negative integer, say [0, 10000].
• And we’ve a derived runtime fixed lhs_slot * 8, which is thought to slot in [0, 80000] by vary evaluation.
• The vary [0, 80000] doesn’t slot in [1, 2^31 - 2^24).
• However, if we define a new expression new_expr := lhs_slot * 8 + 1, the new expression would have range [1, 80001] and match the belief.
• Subsequently, we use an exterior image sym to characterize lhs_slot * 8 + 1, and rewrite the LLVM IR to substitute lhs * 8 with sym - 1.

Now, we’re assured appropriate code because the image vary assumption is met.

Lastly, if the vary of an expression is simply too giant to slot in [1, 2^31 - 2^24), we simply give up. This means the expression will be evaluated at runtime, but this is rare, and is only a minor performance issue, not a correctness issue.

After this transformation, the conceptual logic of the Add example would look like something below:

1
2
3
4
5
6
7
8
9
10
11
12
13

size_t tmp1 = __derived_runtime_constant_1() - 1;
size_t tmp2 = __derived_runtime_constant_2() - 1;
TValue lhs = *(TValue*)((uint64_t)stack + tmp1);
TValue rhs = *(TValue*)((uint64_t)stack + tmp2);
if (!lhs.Is<tDouble>() || !rhs.Is<tDouble>()) {
  ThrowError("Can't add!");
} else {
  double res = lhs.As<tDouble>() + rhs.As<tDouble>();
  
  size_t tmp3 = __derived_runtime_constant_3() - 1;
  *(TValue*)((uint64_t)stack+tmp3) = TValue::Create<tDouble>(res);
  __dispatch_to_next_bytecode();
}

where the derived runtime constants __derived_runtime_constant_1/2/3 are defined as follow:

1
2
3

__derived_runtime_constant_1 := lhs_slot * 8 + 1
__derived_runtime_constant_2 := rhs_slot * 8 + 1
__derived_runtime_constant_3 := output_slot * 8 + 1

Note that in normal cases, those +1 / -1 adjustments will not end up as machine instructions in the resulting JIT code, as normally all of those computation ends up being an imm32 field of an instruction, as we’ll see in the example below.

Example: Generated Code for the AddVV Bytecode

For a concrete example, the figure below demonstrates the disassembly of the actual JIT code generated for the Lua AddVV bytecode, which performs a Lua add on the given two bytecode values. The C++ bytecode semantic that Deegen takes as input is here.

The blue boxes indicates the runtime constants that gets burnt into the instruction stream, with their value definitions shown on the right.

Note that the code contains two separated parts: fast_path and slow_path. We will explain this in detail in the next section: for now focus on fast_path only.

As one can see, the code quality has no problem rivalling a hand-written baseline JIT. It loads the two operands from the stack frame, and checks if any of them is NaN, which means either double NaN or a non-double value (which will exhibit as NaN in our NaN-boxing scheme). If so, it branches to slow_path. Otherwise, it performs a double addition and stores the result back to the output_slot in the stack frame. Finally, the control implicitly fallthroughs to the next bytecode.

The implementation of the JIT compiler logic that generates the above code at runtime will be showcased in the next section.

Design of the Baseline JIT

Having covered the core of the JIT code generation system, we are finally ready to explore the design of the JIT itself and the supporting components.

For a quick overview, the following figure illustrates the high-level architecture of the baseline JIT (except inline caching, which is complex enough that deserves its own section):

The AOT Slow Path

A distinctive “feature” of dynamic languages is the pervasive existence of slow paths. For example, if you call a boolean value like true (why would anyone do that?), it could trigger some complicated metamethod lookup in Lua, ending up with a function to call or an error. In Deegen, a slow path can be created by both automatic type-based quickening and explicit user annotation (the EnterSlowPath API). But for the JIT, there are some extra complexity in implementing them.

Obviously, the slow path logic should be AOT-compiled, not JIT’ed. However, this introduces two problems:

1. How the JIT’ed code could transfer control to the AOT slow path.
2. How the AOT slow path could transfer control back to the JIT’ed code.

Let’s look at the second problem first. The bytecode stream does not contain any information about the JIT’ed code. Also, the slow path could make branches to other bytecodes and calls to other functions, so it’s not as easy as letting the JIT’ed code pass the JIT address of the next bytecode to the slow path.

Deegen’s solution is a dedicated SlowPathData stream. The SlowPathData stream is similar to the bytecode stream, except that it is intended to be used by the AOT slow path of the JIT tier, instead of the interpreter. A SlowPathData contains all the information needed by the slow path, such as bytecode operands, JIT address for this bytecode, JIT address of the conditional branch target of this bytecode, etc. When the JIT’ed code wants to transfer control to the slow path, it would pass the SlowPathData pointer corresponding to the current bytecode to the AOT slow path. The AOT slow path can then have access to all the data it needs to complete the execution and transfer control back to JIT’ed code.

Of course, the SlowPathData stream has to be generated. Fortunately, since Deegen understands the bytecode stream, it is not hard to generate logic that transcribes the bytecode stream to the SlowPathData stream. Specifically, the generated JIT compiler will generate the SlowPathData stream alongside the executable code.

Now let’s look at the first problem. Transferring control from JIT’ed code to the AOT slow path requires some set up logic, for example, to correctly set up the SlowPathData pointer. However, these logic are rarely executed, as slow paths are, of course, rarely used. If no special handling is taken, the resulted code would have cold logic and hot logic mixed together, resulting in unnecessary additional branches and worse code locality. Of course, this is not a correctness problem, but ideally we want to handle it without sacrificing compilation time.

Deegen employs the solution used in JavaScriptCore: hot-cold code splitting, except that Deegen must accomplish it automatically. Specifically, every stencil will be split into a hot part and a cold part. The JIT will generate two streams of executable code, one holding all the hot path logic, and one holding all the slow path logic. The hot-cold splitting is accomplished by an ASM transformation pass, which we will elaborate in the next section.

The Baseline JIT Algorithm

We now have all the pretexts to understand how the baseline JIT itself works.

In addition to the logic that actually generates machine code, Deegen also generates a bytecode trait table that contains various info about the generated code for each bytecode, e.g., the length of the JIT’ed code’s hot part and cold part, the length and alignment of the data section accompanying the JIT’ed code, the length of the SlowPathData for this bytecode, etc. This allows the baseline JIT to precompute all the buffer sizes in advance.

The baseline JIT compiler works in two passes.

In the first pass, we iterates through the bytecode stream, and use the bytecode trait table to compute various buffer sizes of the generated code and data. All the buffers are then allocated in advance, knowing that a buffer overrun will never happen when we actually fill contents (code, data, etc.) into the buffers. This pass is very cheap because no indirect dispatch is needed.

In the second pass, we iterates through the bytecode stream again, and generate everything (executable code, the accompanying data, the SlowPathData, etc.) for each bytecode by populating the pre-allocated buffers. This step conceptually works similar to an interpreter. We have a pre-built dispatch table storing the codegen functions for each bytecode kind. Control is first transferred to the codegen function for the first bytecode. The function would generate everything needed for the first bytecode, advance buffer pointers accordingly, and then transfer control to the codegen function for the next bytecode. This process repeats until the end of the bytecode stream is reached.

Thanks to Copy-and-Patch, each codegen function is completely branchless, except the tail dispatch that transfers control to the next codegen function, as we shall see in the Add example below. This allows a modern CPU to utilize its Instruction-Level Paralleism (ILP) capabilities to the utmost, yielding an extremely fast compilation process.

Finally, due to the nature of one-pass code generation, bytecodes that can branch to other bytecodes would not know their branch destination address at the time their own code is being generated. To solve this issue, those bytecodes would push information about how the branch destination address shall be fixed up into a late-patch buffer. After all code generation is done, we need to iterate through the late-patch buffer and fix up all the branch targets.

Example: Code Generation Function for the AddVV Bytecode

Below is the actual code-generation logic generated by Deegen that generates code for the Lua AddVV bytecode. The machine code generated by the logic is demonstrated in the right half of the figure for cross-reference.

As one can see, the code-generation logic is just what we have explained in the previous subsection. It first decodes the bytecode, then performs a copy-and-patch to generate the JIT fast path and the JIT slow path logic. The expression that defines each runtime constant is replayed to compute the patch value in the instruction stream. Besides the machine code, it also generates the SlowPathData stream and other minor support data. Finally, it advances pointers and dispatch to the next codegen function to codegen the next bytecode. The whole process is completely branchless (except the tail dispatch) by design.

Supporting Inline Caching: the Art of Repurposing Existing Tools, Evermore

Due to inherent design constraints of a baseline JIT (e.g., compilation must be fast, no OSR-exit is allowed), inline caching (IC) is the only high-level optimization tool available to the baseline JIT.

And inline caching is powerful: on benchmarks that extensively work with Lua tables, a baseline JIT with IC can often be more than 100% faster than the same baseline JIT without IC.

In this section, we will elaborate how Deegen supports inline caching.

How IC works in Deegen: a Step-by-Step Example of Call IC

For a beginner’s introduction to what IC is, please read the background section. However, to understand how IC actually works in Deegen’s baseline JIT, the easiest way is to walk through an assembly example. Here, we will use a simplified Call bytecode, which performs a call with no arguments and discards all return values, to demonstrate how call IC works.

The C++ bytecode semantic description is very simple:

1
2
3
4
5
6
7
8
9
10
11
12
13

void ReturnContinuation(TValue* ) { Return(); }
void Call(TValue* base) {
  TValue func = *base;
  if (likely(func.Is<tFunction>())) {
    TValue* newStackFrame = base + x_numSlotsForStackFrameHeader;
    MakeInPlaceCall(func.As<tFunction>(), 
                    newStackFrame, 
                    0 , 
                    ReturnContinuation);
  } else {
    EnterSlowPath<CheckMetatableSlowPath>();
  }
}

It checks if the callee is a function object. If so, it uses Deegen’s MakeInPlaceCall API to make a call, and the return continuation simply discards all return values and transfer control to the next bytecode. Otherwise, it enters the outlined slow path function (omitted) that checks for a metatable call.

Deegen would generate the following JIT code for this bytecode:

Note that runtime constants are marked in purple in the form of ${X}.

Let’s pretend for now that the codegen_call_ic thing doesn’t exist, and look at the naive implementation. If you stare at the assembly code a little bit, you will notice that the logic involves:

1. Two branches to check that func is a function object.
2. Two dependent memory loads: one loads the function prototype proto from func, and one loads the actual entry point address from proto.
3. One indirect branch to branch to the entry point.

Unfortunately, dependent memory loads and unpredictable indirect branchs are exactly the two things modern CPUs hate the most. Even predictable branches can be slow, if there are too many of them so that the BTB is overwhelmed.

So how does IC speeds up this code?

As one might have expected, codegen_call_ic will be called on the first time this code is executed. What codegen_call_ic does is that it will emit a piece of IC code snippet, and chain it to the main logic by repatching the self-modifying-code (SMC) region, as shown below:

As one can see, the next time the same function is called, thanks to the SMC region, the IC will hit, and the optimized logic will be executed. The optimized logic does not check that func is a function object (because we already checked it last time), has no memory loads, and the branch is direct.

This process can be repeated to chain any number of IC entries into a chain:

• SMC region branches to IC #N
• IC #N branches to IC #(N-1) if the cached value does not hit
• … etc …
• IC #1 branches to the IC miss slow path, which will create a new IC snippet #(N+1) and chain it at the head of the chain.

Of course, at a certain point the overhead from the check chain would cancel out the benefit of the optimized code, and we will stop chaining more cases.

Call IC’s Direct Call Mode vs Closure Call Mode

While the above approach works well if a Lua function is used like a C function (monomorphism) or a C++ virtual method (class-like polymorphism), it would work very poorly for the function factory design pattern. For example, consider the following Lua snippet:

1
2
3
4
5
6
7
8
9
10

createCounter = function() 
  local value = 0
  return function() 
    value = value + 1
    return value
  end
end
incrementCounter = function(counter)
  return counter()
end

In this example, the call in line 9 is likely to see a lot of different function objects, even though all of them share the same prototype (the counter lambda in line 3). Since our current call IC strategy caches on the function object, not the function prototype, it is completely ineffective for this use pattern.

Again, we employ the solution used in JavaScriptCore. Our call IC supports two modes: direct call mode and closure call mode. A call IC site always starts in direct call mode, in which it caches on function objects, as we have shown above.

See Also

Doc Edge Detection for Picture Processing

But when a call IC site first sees a IC miss that has the same function prototype as one of the already-cached function objects, it will transition the IC to closure-call mode. To do this, it rewrites the self-modifying code region and invalidates all existing ICs at this site, and from now on, this IC site will instead cache on the function prototypes. This is demonstrated by the figure below:

As one can see, the SMC region is repatched to completely different logic: it checks if func is a heap object (which is required for us to load its hidden class), then load the hidden class of the heap object and branch to the first IC case.

Each closure call IC case caches on a function prototype. So it compares if the hidden class matches the cached prototype. If yes, it knows that func must be a function object with the cached prototype, so it can perform an optimized call similar to before.

Of course, one can also chain up as many IC cases in closure call as desired, until the chained check overhead overwhelms the perf gain from the optimized code.

As one can see, closure call mode is less efficient than direct call mode as it performs one extra check and one extra memory load, but it works effectively for the function factory design pattern. This is why a call IC site always starts in direct call mode, and only transitions to closure call mode when it actually observes a closure call pattern.

So, How to Automatically Generate All of These?

Having understood how IC works in Deegen (we only demonstrated Call IC, but the case for Deegen’s Generic IC API is similar), the next question is: how could Deegen generate all of these automatically?

However, as you can already see, what we want to do is something totally outside the operating envelope of LLVM. LLVM is simply not designed to generate a function that can dynamically patch itself at runtime to append a dynamic chain of parametrizable code snippets.

As before, our solution is to repurpose existing tools to trick LLVM into helping us without its knowledge. And as it turns out, the core of the trick is to repurpose a completely-irrelevant little-known GCC feature in the dark corner.

Thank you, GCC ASM-goto!

GCC supports a little-known extension feature called ASM-goto, which basically allows one to write inline assembly that branches from assembler code to C labels. And LLVM, aiming for compatibility with GCC, has also supported this feature a few years ago by a special CallBr IR instruction.

I just want to say a big thank you to the GCC developers who designed this feature and the LLVM developers who added support for it! Without this feature, it’s very likely Deegen couldn’t support inline caching at all.

So how does ASM-goto have anything to do with inline caching?

As you might have seen from the assembly example above, the hard part of IC is that each IC case is a piece of machine code that directly “clings” to the main logic. It cannot be implemented by a separate function due to the call overhead and the requirements of Lua’s stackful coroutine. It must work directly using the context (e.g., which register holds which value) of the main logic, and could transfer control to different destinations in the main logic.

ASM-goto (and its underlying CallBr LLVM IR) provided exactly the semantics we want. Since it is an InlineAsm, LLVM is required to treat its contents as opaque. All LLVM knows is that after executing the InlineAsm, control will be transferred to one of the destinations specified in the CallBr.

In other words, we repurpose CallBr as a way to model “a control flow transfer in an unspecified manner”. At runtime, we are building up a dynamic chain of IC cases; but if one views the chain-check logic as a black box, then it can be characterized as: after the black box is executed, control is transferred to either an IC hit case specialized to the cached values, or the IC miss slowpath. This is exactly the semantics CallBr provided, so we can safely model it using CallBr.

But this is still far from enough. Now we have a way to model the control flow of the dynamic IC chain in LLVM IR, but it’s still unclear how we can extract the IC logic from the main function, implement the IC check chain, and do all the self-modifying code stuff.

This is where the last piece of the puzzle comes in: ASM transformation.

ASM Transformation: the Last Piece of the Puzzle

I know this might scare off people, as directly messing with assembly sounds like an extremely fragile approach.

But it really isn’t. Deegen treats most of the assembly instructions as opaque and will not modify any of them. The ASM transformation is limited to reordering and extracting ASM blocks.

As a result, Deegen’s assembly knowledge is extremely limited. All it knows is that:

• A jmp does a direct jump.
• A jmpq does an indirect jump.
• Any other instruction starting with j does a conditional jump.

However, as it turns out, with some clever tricks and cooperation from LLVM IR, doing only ASM block rearrangements is already sufficient to achieve a lot: we can support all the inline caching stuffs, among other things.

The full trick is the following. Recall that we are only using CallBr as a device to express an opaque control flow, and the InlineAsm inside CallBr does not matter. So we will use this InlineAsm to carry down information to the textual assembly level, as shown below.

As one can see, the previledged instruction hlt is used as a magic to allows us to identify the CallBr in the textual assembly. Then, the fake branches following the hlt allows us to know the assembly labels that implements each logic case.

Having parsed these information, we no longer need the CallBr payload, so we remove it from assembly, and make it branch to the slow path directly.

Next, we perform a CFG analysis of the assembly. The only hard part about the CFG analysis is to know the possible destinations of the indirect branches. This ideally should be implemented as a LLVM backend pass, but I haven’t figured out how to do it due to limited documentation about LLVM backend. So currently, the indirect branch target analysis is done via some hacks that map the indirect branch back to LLVM IR by debug info.

Now we have the CFG of the assembly, we can then figure out the ASM blocks only reachable from the function entry, and only reachable from each IC logic kind, as shown below.

Note that the logic entry of each IC kind must not be reachable from the function entry, because they are only reachable by the CallBr, but we have removed those control flow edges as the CallBr has been removed by us.

Finally, we can separate out the IC logic from the main function logic. For the main function, we only retain ASM blocks reachable from the function entry. And for each IC kind, we only retain ASM blocks reachable from its logic entry but not the main function entry. Each piece of extracted assembly is then compiled to object file and extracted to a Copy-and-Patch stencil, so we can JIT it at runtime.

There are still some minor issues that we haven’t covered, such as how we build up the dynamic IC check chain, and how exactly the self-modifying code region is constructed. But the idea is similar to how we supported inline caching: most of the heavy-lifting of actually building up the logic is done at LLVM, and InlineAsm is repurposed as a tool to pass down information to assembly. Then at assembly level, Deegen can piece everything together by very simple transformations that requires little to no assembly knowledge.

The Inline Slab Optimization

Deegen employed one additional optimization for IC: the Inline Slab optimization (again, the terminology is a JavaScriptCore jargon).

Conceptually, the idea is very simple: currently, each IC case is an outlined piece of JIT code. As a result, control has to branch from main logic to the IC case, and then from the IC case back to the main logic in the end. So why not use the SMC region to hold one IC case? Now, the “blessed” IC case sitting directly inside the SMC region can be executed directly, saving one or two jumps.

Of course, it is harder to do than said. One has to decide a good size for the inline slab (i.e., the SMC region), as only IC whose size is less than the inline slab size can sit in the inline slab. And updating the patchable jump in the SMC region is more complicated, as the location of the jump is different depending on whether the inline slab exists. Finally, the inline slab version of the IC has slightly different logic from the normal version: the tail branch could potentially be eliminated, and one must pad NOPs to exactly the size of the inline slab.

As a result, even in JavaScriptCore, the inline slab optimization requires quite some engineering efforts, e.g., more hand-rolled assembly, manual book-keeping of the inline slab sizes that has to be updated whenever the generated assembly changes, etc.

Fortunately, in Deegen, the inline slab optimization is employed fully automatically. So for a language implementer, the additional ~4% performance on average (and occasionally 10+% on IC intensive workloads) from inline slab comes for free!

Runtime Support, and IC Design Summary

Finally, the VM runtime needs to manage the IC. For example, it needs to reclaim the JIT code memory when the IC is invalidated, and upon tiering-up, it needs to update all the call IC cases to point to the new entry point.

Therefore, in additional to the actual JIT’ed code, we also need to allocate a piece of metadata to manage each IC. The metadata are chained into a linked list at the use site of the IC (the ICSite), which resides in the SlowPathData stream.

Putting everything about Deegen’s IC design together into one figure:

Full Example for Deegen’s Generic IC: TableGetById Bytecode

To conclude our discussions on inline caching, we will present a full example for the TableGetById (aka., TGETS in LuaJIT) bytecode.

The bytecode takes two operands: base and index, where index is a constant string, and returns base[index]. Any Lua string property entry, for instance, worker.identify or animal.weight, would generate this bytecode.

In LuaJIT Remake, a Lua desk just isn’t applied by a plain hash desk with an array half, however employs hidden class for higher efficiency, utilizing a design mostly mirroring JavaScriptCore’s. Deegen helps generic IC API to permit straightforward deployment of IC by way of intelligent use of C++ lambdas. The precise implementation of the C++ bytecode semantic for TableGetById may be found here.

The determine under is the disassembly of the particular machine code generated by the baseline JIT, alongside the JIT’ed code for all 6 sorts of IC stubs, in addition to their inline-slab variations. As earlier than, the runtime constants burnt into the instruction stream are proven in purple textual content.

As you’ll be able to see above, within the good case of an inline-slab IC hit for a desk with out metatable (which is quite common), a TableGetById may be achieved with no taken branches and in lower than 10 directions. This is the reason IC might drastically pace up desk operations.

Then again, as you may also see above, implementing IC by hand requires a deep understanding of meeting and a big quantity of engineering. That is precisely the place Deegen is available in. With Deegen’s generic IC API that makes all of those occur mechanically, a language implementer can get pleasure from the advantages of IC with out the excessive engineering value.

The Sizzling-Chilly Splitting Go and Leap-to-Fallthrough Go

Lastly, since we have already got an ASM transformation infrastructure, why not use it for extra good?

The Sizzling-Chilly Splitting Go works by reordering ASM blocks and transfer chilly blocks to a separated textual content part, which reduces some pointless branches and improves code locality. After all, the stencil extraction logic that generates the copy-and-patch stencil from the item file must be made conscious of this and extract each sections, however this isn’t exhausting to do. To determine which blocks are chilly, ideally, one ought to write a LLVM backend move. Nevertheless, as defined earlier than, I nonetheless haven’t discovered write a LLVM backend move, so at present that is achieved by injecting debug data to map meeting blocks again to LLVM IR blocks, and use LLVM IR’s block frequency infrastructure to find out the chilly blocks.

The Leap-to-Fallthrough transformation move makes an attempt to maneuver the dispatch to the following bytecode to the final instruction, in order that the leap might be eradicated to a fallthrough, decreasing an pointless department. That is wanted as a result of at LLVM IR degree, a dispatch is a tail name, and LLVM just isn’t conscious of the truth that a dispatch to the following bytecode might doubtlessly be applied by a fallthrough if it have been the final instruction. Deegen applied a easy move to deal with this situation, which makes an attempt to make the fallthrough attainable by reordering ASM blocks and doing very restricted rewrites like flipping department circumstances.

An Finish-to-Finish Instance

To display how the precise end-to-end JIT’ed code generated by the baseline JIT appears to be like like, we’ll use the next Lua instance that computes a factorial:

1
2
3
4
5
6
7
8
9

reality = perform(n)
  if (n < 1) then
    return 1
  finish 
  return reality(n-1) * n
finish

Whereas it’s a easy instance, it demonstrates nearly all of the essential issues in a baseline JIT: primary operations resembling arithmetic and comparability, management stream, perform calls, name inline caching (mechanically offered as a part of Deegen) and desk inline caching (implement utilizing Deegen’s generic IC API).

The above Lua perform leads to 8 bytecodes:

• (Bytecode #0) BranchIfNotLessThan {Slot(0), Double(1)} → #3
• (Bytecode #1) ConstInt16 {1} → Slot(1)
• (Bytecode #2) Return {SlotRange [1, 2)}
• (Bytecode #3) GlobalGet {String("fact")} → Slot(1)
• (Bytecode #4) ArithmeticSub {Slot(0), Double(1)} → Slot(5)
• (Bytecode #5) Call { Frame: Slot(1), #arg: 1, #ret: 1 }
• (Bytecode #6) ArithmeticMul {Slot(1),Slot(0)} → Slot(1)
• (Bytecode #7) Return {SlotRange [1, 2)}

For clarity, we demonstrate the code after the function has been executed, so all the self-modifying code regions (including inline slabs) have been repatched, and outlined IC stubs have been created.

I manually grabbed the JIT’ed code using GDB and hand-remapped all the labels, so please pardon me if I made an mistake. The disassembly is as follows:

Note that under normal circumstances (i.e., a number is passed in as parameter to fact), the GlobalGet and Call slow path will be executed once to create the IC. After that, none of the slow path logic will ever be executed, and none of the self-modifying code region in the fast path will get repatched further.

Tiering-up Logic

The last bit of complexity is the tiering-up logic. In a multi-tier VM, the user program starts execution in the interpreter tier, and hot functions are eventually tiered up to the baseline JIT tier (and potentially further to the optimizing JIT tier, but that’s future work).

To support tiering-up, we have two problems to solve. First, how hot functions could be identified. Second, how future calls to the tiered-up function could get redirected to the JIT’ed version.

Let’s look at the second problem first. While seemingly trivial (just change the entry point stored in the function prototype), it is actually not that trivial due to the existence of call IC. When a function gets tiered-up, every call IC that caches on the function must be updated and redirected to the new entry point. To achieve this, all the call IC are chained into a circular doubly-linked list on the function prototype that it caches on. In addition, Deegen generates information on how one can update the JIT’ed code of a call IC to change the function entry point it branches to. Then, whenever a function is tiered up, one can iterate through all the call ICs caching on the function using the doubly-linked list, and update each of them to point to the new entry.

For the first problem, the idea is to increment a per-function counter whenever the interpreter reaches a loop bytecode or a function return bytecode. When the counter reaches a threshold, we trigger JIT compilation and redirect control to the JIT’ed code. Unfortunately, the engineering of this part has not been finished. I have to publish this post now, because this post is used as the reading material for a talk a couple of days later 🙁

This also means that currently we cannot tier-up from interpreter to baseline JIT, so for the benchmarks, everything is directly compiled by the baseline JIT and executed in baseline JIT tier.

Performance Evaluation

In this section, we will analyze the performance of LuaJIT Remake (LJR)’s baseline JIT on 44 synthetic benchmarks from Are-we-fast-yet, CLBG, LuaJIT Benchmarks and Lua Benchmarks.

Disclaimer: synthetic benchmarks are well-known to be misleading and unable to reflect real workloads (see [1,2,3,4]). The only real goal of this part is to place our outcomes throughout the context of the present works, to provide a tough sense on the efficiency of our baseline JIT.

Compilation Throughput

The highest precedence of a baseline JIT is to generate machine code as quick as attainable. Subsequently, our first analysis is the compilation throughput.

We measured the compilation throughput of our baseline JIT by timing the primary compilation perform, which performs the end-to-end work of compiling a enter Lua bytecode stream to machine code. We additionally recorded the whole variety of Lua bytecodes processed by the baseline JIT, and the whole measurement of the generated machine code.

The typical consequence over all 44 benchmarks is as follows:

• When it comes to Lua bytecodes processed per second, LJR’s baseline JIT can compile 19.1 million Lua bytecodes per second.
• When it comes to machine code generated per second, LJR’s baseline JIT can generate 1.62GB of machine code per second.

To display what 19.1 million Lua bytecodes means, the 44 Lua benchmark applications (254KB complete) accommodates 17197 Lua bytecodes in complete. So our baseline JIT generated machine code for all 44 benchmarks in lower than one millisecond complete.

As such, we declare that the compilation throughput of our baseline JIT is extraordinarily quick, to the purpose that the beginning delay may be thought-about negligible.

Generated Code Efficiency

Whereas the baseline JIT is designed to generate code quick, producing quick code remains to be a second precedence.

On this part, we’ll consider the execution efficiency of the machine code generated by LJR’s baseline JIT by evaluating with LuaJIT and PUC Lua.

LJR and LuaJIT have drastically totally different high-level structure, mid-level design and low-level implementation selections. For the obvious half, a baseline JIT performs few optimizations by design, whereas the tracing JIT in LuaJIT does a number of optimizations. Subsequently, the only goal of the benchmark is to place the top efficiency of LJR’s baseline JIT throughout the context of the present works, as proven within the determine under:

As one can see, LuaJIT’s optimizing tracing JIT typically works higher than our baseline JIT, which isn’t any shock.

Nevertheless, it’s value noting that with IC as the one high-level optimization, we’re already outperforming LuaJIT on 13 of the 44 benchmarks. On geometric common, we’re about 34% slower than LuaJIT, and 4.6x sooner than PUC Lua.

For my part, it’s truthful to say that Deegen is now on a really secure floor. With its wonderful interpreter and baseline JIT that may already obtain fairly good execution efficiency at a negligble startup delay, the optimizing JIT (to come back sooner or later) would have a lot much less strain in doing costly optimizations.

Conclusion Ideas and Future Works

This publish demonstrated the second section of the Deegen undertaking – to construct a high-performance baseline JIT compiler mechanically from the bytecode semantic.

After all, that is removed from the top. Our subsequent step is to mechanically generate an optimizing compiler, which is able to possible observe the design of JavaScriptCore’s DFG light-weight JIT compiler. You probably have any feedback, options or ideas, please don’t hesitate to shoot me an email 🙂

Acknowledgements

I thank Fredrik Kjolstad and Saam Barati for his or her feedback and discussions on the draft model of this publish. Fredrik additionally did the picture modifying work for the Add bytecode determine.