Use portable JIT compilation for accelerating RISC-V emulation

[jserv]

rv8 demonstrates how RISC-V instruction emulation can benefit from JIT compilation and aggressive optimizations. However, it is dedicated to x86-64 and hard to support other host architectures, such as Apple M1 (Aarch64). SFUZZ is a high performance fuzzer using RISC-V to x86 binary translations with modern fuzzing techniques. RVVM is another example to implement tracing JIT.

The goal of this task to utilize existing JIT framework as a new abstraction layer while we accelerate RISC-V instruction executions. In particular, we would

1. Avoid direct machine code generation. Instead, most operations are enforced in intermediate representation (IR) level.
2. Perform common optimization techniques such as peephole optimization. ria-jit performs excellent work in regards to such optimization. See src/gen/instr/patterns.c and MEMZERO and MEMCOPY instructions proposal
3. Use high-level but still efficient IR. MIR is an interesting implementation, which allows using subset of C11 for IR. SFUZZ's note Code Generation is worth reading. ETISS (Extendable Translating Instruction Set Simulator) translates binary instructions into C code and appends translated code into a block, which will be compiled and executed at runtime. As aforementioned, it is Extendable, thus it supports myriad level of customization by adopting the technique of plug-ins.
4. Ensure shorter startup-time. It can be achieved by means of lightweight JIT framework and AOT compilation.

The JIT compilation's high level operation can be summed up as follows:

• Look in a hash map for a code block matching the current PC
• if a block is found
  • execute this block
• if a block is not found
  • allocate a new block
  • invoke the translator for this block
  • insert it into the hash map
  • execute this block

Every block will come to an end after a branch instruction has been translated since translation occurs at the basic block level. Then, there is room for further optimization passes performed on the generated code.

We gain speed by using the technique for the reasons listed below:

• No instruction fetch
• No instruction decode
• Immediate values are baked into translated instructions
  • Values of 0 can be optimized
• register x0 can be optimized
  • No lookup required
  • Writes are discarded
• Reduced emulation loop overhead
• Blocks can be chained based on previous branch pattern for faster lookup

Reference:

• Banshee: A Fast LLVM-Based RISC-V Binary Translator
• rv8: a high performance RISC-V to x86 binary translator / slides
• Dynamic Binary Translation for RISC-V code on x86-64 / slides / cm2 branch
• R2VM / Accelerate Cycle-Level Multi-Core RISC-V Simulation with Binary Translation
• Dynamic Binary Translator for RISC-V / riscv-dbt
• High-Performance RISC-V Emulation: LLVM-based Static Binary Translation (SBT)
• Hybrid-DBT: Hardware/Software Dynamic Binary Translation Targeting VLIW / slides / HybridDBT / translationCache
• Adaptive simulation with Virtual Prototypes in an open-source RISC-V evaluation platform
• Code specialization for the MIR lightweight JIT compiler
• A Faster CRuby interpreter with dynamically specialized IR
• HIFIVE1-VP
• RISC-V static binary translator targeting AArch64 / discussion
• A Journey to the Absolute Limit: CKB-VM's LLVM AOT engine
• libriscv: RISC-V Binary Translation
• Explaining JavaScript VMs in JavaScript - Inline Caches / code: inline-cache
• Just-In-Time Compilation on ARM—A Closer Look at Call-Site Code Consistency
• LuaJIT Remake: the interpreter and the JIT tiers are automatically generated from a semantical description of the bytecodes. / Building the fastest Lua interpreter.. automatically!
• Crafting Interpreters
• How I developed a faster Ruby interpreter
• Parsing Protobuf at 2+GB/s: How I Learned To Love Tail Calls in C
• WasmNow: Fast WebAssembly Baseline Compiler
• A fast in-place interpreter for WebAssembly / wizard-engine
• Kilite: a complete example for using C2MIR
• DarkSwordVM: JIT compilation for LLVM IR
• pydrofoil: Fast RISC-V Sail emulation using PyPy/RPython's JIT compiler
• Compiling SQLite queries to native code with LLVM / LLVMSQLite
• QEMU Tiny-Code Threaded Interpreter
• MINRES: DBT-RISE: Dynamic Binary Translation (DBT) based environment to implement instruction set simulator (ISS)

[jserv]

Think about whether we want to load a 64-bit immediate under the present RISC-V specification. Despite memory access being substantially slower, it is simpler to just load a constant from memory since it requires less instructions.

In RISC-V

    lui r1, 0x01234
    lui r2, 0x89ABC
    addi r1, 0x567
    addi r2, 0xDEF
    shl r1, 32
    or r1, r2

24-bytes, 6 instruction cycles and 2 registers.

In x86_64:

    movabs rax, 0x0123456789ABCDEF

11-bytes, 1 instruction cycle, 1 register.

[Ma-Y]

it's not so apparent where the starting and ending position of a particular code block is . does this mean hard coding pseudo pattern(common code block pattern) for the binary to match on?

[jserv]

blink is a virtual machine for running x86-64-linux programs on different operating systems and hardware architectures. Recently, it implements a JIT. Quote from blink/jit.c:

This file implements an abstraction for assembling executable code at runtime. This is intended to be used in cases where it's desirable to have fast "threaded" pathways, between existing functions, which were compiled statically. We need this because virtual machine dispatching isn't very fast, when it's implemented by loops or indirect branches.
Modern CPUs go much faster if glue code without branches is outputted to memory at runtime, i.e. a small function that calls the functions.

[jserv]

wasm3 is a fast WebAssembly interpreter without JIT. In general, its strategy seems capable of executing code around 4-15x slower than compiled code on a modern x86 processor.

• Reduce bytecode decoding overhead
  • Bytecode/opcodes are translated into more efficient "operations" during a compilation pass, generating pages of meta-machine code
  • wasm3 trades some space for time. Opcodes map to up to 3 different operations depending on the number of source operands and commutative-ness.
  • Commonly occurring sequences of operations can also be optimized into a "fused" operation. This sometimes results in improved performance.
  • In wasm3, the stack machine model is translated into a more direct and efficient "register file" approach.
• Tightly Chained Operations

Tails is a minimal, fast Forth-like interpreter core. It uses no assembly code, only C++, but an elegant tail-recursion technique inspired by Wasm3 makes it nearly as efficient as hand-written assembly.

[jserv]

Benchmark results of rv8: (RV32 only, smaller is better)

-	interpreter	JIT	qemu-user	native-x86
primes	34.33	1.75	1.55	1.00
miniz	40.19	1.95	2.68	1.00
SHA-512	76.23	3.40	3.78	1.00
AES	88.02	2.57	4.08	1.00
qsort	28.82	1.86	7.50	1.00
dhrystone	128.97	2.72	12.04	1.00

[qwe661234]

Our strategy to develop JIT is utilizing Clang to generate optimized target code. The JIT compiler design is shown in Figure 1.
When a block's usage frequency exceeds a predetermined threshold, we trace its taken and untaken branches and use a code generator to convert the instruction sequence into C code. We then compile the C code using Clang and store the resulting target machine code as a function in the code cache for future use.

An example instruction sequence that is a hot spot in Mandelbrot is shown in Figure 2, along with the corresponding EBB. The generated code for this EBB is shown as below.

• Figure1
  
• Figure2
  
• Instruction Sequence in Mandelbrot

10750: lw  a5,128(sp)
10754: beq a5,s10,0x10760
10758: add s1,s1,a0
1075c: j   0x10728
10760: mv  s8,a0
10764: sub s9,s1,s7
10768: bne s1,s7,0x10a0c
...

• Generated Code

insn_10750:
  ...
  goto insn_10754;
insn_10754:
  ...
  if (...)
    goto insn_10760;
  goto insn_10758;
...

[qwe661234]

The commit 36f304c implements the JIT strategy described above. The benchmark results, as shown in the statistics below, demonstrate that the JIT has a positive effect on benchmarks with long execution times. However, in the case of Mandelbrot, its short execution time means that the overhead of the JIT outweighs its benefits.

Test	rv32emu (interpreter)	rv32emu (JIT)	Speedup
CoreMark	1155.174 (Iterations/Sec)	1796.483 (Iterations/Sec)	+55.5％
dhrystone	1282 DMIPS	2521 DMIPS	+96.64%
nqueens	7766.80 msec	3893.81 msec	+99.47%
mandelbrot	32.28 msec	77.34 msec	-139.59%

[qwe661234]

We experiment the same JIT strategy based on different compiler clang and mir.

clang

Metric	Interpreter-Only	Just-in-time Compiler	Speedup
CoreMark	1155.174 (Iterations/Sec)	1796.483 (Iterations/Sec)	+55.5％
Dhrystone	1282 DMIPS	2521 DMIPS	+96.64%

mir

Metric	Interpreter-Only	Just-in-time Compiler	Speedup
CoreMark	1155.174 (Iterations/Sec)	2194.907 (Iterations/Sec)	+90％
Dhrystone	1282 DMIPS	2522 DMIPS	+96.7%

The issue with Clang is that we need to fork a Clang process, which results in a significant overhead. However, its ability to optimize code is strong. In contrast, launching mir has a relatively small overhead, but its ability to optimize code is relatively weak and we cannot determine the code size of the machine code compiled by mir. This limitation prevents us from using a code cache to manage machine code effectively.

[jserv]

The issue with Clang is that we need to fork a Clang process, which results in a significant overhead. However, its ability to optimize code is strong. In contrast, launching mir has a relatively small overhead, but its ability to optimize code is relatively weak and we cannot determine the code size of the machine code compiled by mir. This limitation prevents us from using a code cache to manage machine code effectively.

The preliminary baseline JIT compiler has been landed in wip/jit branch. Meanwhile, it comes with some known issues, including Arm64 breakage. The design principle of baseline JIT is to stick to C2MIR approach where we can improve macro operation fusion and/or RISC-V oriented optimizations.

[qwe661234]

Ongoing

• As Utilize dominators for constructing extended basic blocks #142, the related experiment of using a dominator tree to detect loops has been preliminarily implemented on the branch detect_loop.
• Improving memory I/O.
• Fix the known issue that JIT does not work on macOS on Apple Silicon. JIT compilation works on GNU/Linux for both x86-64 and Arm64.