QEMU Tiny-Code Threaded Interpreter (AArch64)

April 7, 2021 · View on GitHub

A TCG backend that chains together JOP/ROP-ish gadgets to massively reduce interpreter overhead vs TCI. Platform-dependent; but usable when JIT isn't available; e.g. on platforms that lack WX mappings. The general idea squish the addresses of a gadget sequence into a "queue" and then write each gadget so it ends in a "dequeue-jump".

Execution occurs by jumping into the first gadget, and letting it just play back some linear-overhead native code sequences for a while.

Since TCG-TCI is optimized for sets of 16 GP registers and aarch64 has 30, we could easily keep JIT/QEMU and guest state separate, and since 16*16 is reasonably small we could actually have a set of reasonable gadgets for each combination of operands.

Register Convention

Regs	Use
x1-x15	Guest Registers
x24	TCTI temporary
x25	saved IP during call
x26	TCTI temporary
x27	TCTI temporary
x28	Thread-stream pointer
x30	Link register
SP	Stack Pointer, host
PC	Program Counter, host

In pseudocode:

Symbol	Meaning
Rd	stand-in for destination register
Rn	stand-in for first source register
Rm	stand-in for second source register

Gadget Structure

End of gadget

Each gadget ends by advancing our bytecode pointer, and then executing from thew new location.

# Load our next gadget address from our bytecode stream, advancing it, and jump to the next gadget.

ldr x27, [x28], #8\n
br x27

Calling into QEMU's C codebase

When calling into C, we lose control over which registers are used. Accordingly, we'll need to save registers relevant to TCTI:

str x25,      [sp, #-16]!
stp x14, x15, [sp, #-16]!
stp x12, x13, [sp, #-16]!
stp x10, x11, [sp, #-16]!
stp x8,  x9,  [sp, #-16]!
stp x6,  x7,  [sp, #-16]!
stp x4,  x5,  [sp, #-16]!
stp x2,  x3,  [sp, #-16]!
stp x0,  x1,  [sp, #-16]!
stp x28, lr,  [sp, #-16]!

Upon returning to the gadget stream, we'll then restore them.

ldp x28, lr, [sp], #16
ldp x0,  x1, [sp], #16
ldp x2,  x3, [sp], #16
ldp x4,  x5, [sp], #16
ldp x6,  x7, [sp], #16
ldp x8,  x9, [sp], #16
ldp x10, x11, [sp], #16
ldp x12, x13, [sp], #16
ldp x14, x15, [sp], #16
ldr x25,      [sp], #16

TCG Operations

Each operation needs an implementation for every platform; and probably a set of gadgets for each possible set of operands.

At 14 GP registers, that means that

1 operand => 16 gadgets 2 operands => 256 gadgets 3 operands => 4096 gadgets

call

Calls a helper function by address.

IR Format: br <ptr address>
Gadget type: single

    # Get our C runtime function's location as a pointer-sized immediate...
    "ldr x27, [x28], #8",

    # Store our TB return address for our helper. This is necessary so the GETPC()
    # macro works correctly as used in helper functions.
    "str x28, [x25]",

    # Prepare ourselves to call into our C runtime...
    *C_CALL_PROLOGUE,

    # ... perform the call itself ...
    "blr x27",

    # Save the result of our call for later.
    "mov x27, x0",

    # ... and restore our environment.
    *C_CALL_EPILOGUE,

    # Restore our return value.
    "mov x0, x27"

br

Branches to a given immediate address. Branches are

IR Format: br <ptr address>
Gadget type: single

# Use our immediate argument as our new bytecode-pointer location.
ldr x28, [x28]

setcond_i32

Performs a comparison between two 32-bit operands.

IR Format: setcond32 <cond>, Rd, Rn, Rm
Gadget type: treated as 10 operations with variants for every Rd/Rn/Rm (40,960)

subs Wd, Wn, Wm
cset Wd, <cond>

QEMU Cond	AArch64 Cond
EQ	EQ
NE	NE
LT	LT
GE	GE
LE	LE
GT	GT
LTU	LO
GEU	HS
LEU	LS
GTU	HI

setcond_i64

Performs a comparison between two 32-bit operands.

IR Format: setcond64 <cond>, Rd, Rn, Rm
Gadget type: treated as 10 operations with variants for every Rd/Rn/Rm (40,960)

subs Xd, Xn, Xm
cset Xd, <cond>

Comparison chart is the same as the _i32 variant.

brcond_i32

Compares two 32-bit numbers, and branches if the comparison is true.

IR Format: brcond Rn, Rm, <cond>
Gadget type: treated as 10 operations with variants for every Rn/Rm (2560)

# Perform our comparison and conditional branch.
subs Wrz, Wn, Wm
br<cond> taken

    # Consume the branch target, without using it.
    add x28, x28, #8

    # Perform our end-of-instruction epilogue.
    <epilogue here>

taken:

    # Update our bytecode pointer to take the label.
    ldr x28, [x28]

Comparison chart is the same as in setcond_i32 .

brcond_i64

Compares two 64-bit numbers, and branches if the comparison is true.

IR Format: brcond Rn, Rm, <cond>
Gadget type: treated as 10 operations with variants for every Rn/Rm (2560)

# Perform our comparison and conditional branch.
subs Xrz, Xn, Xm
br<cond> taken

    # Consume the branch target, without using it.
    add x28, x28, #8

    # Perform our end-of-instruction epilogue.
    <epilogue here>

taken:

    # Update our bytecode pointer to take the label.
    ldr x28, [x28]

Comparison chart is the same as in setcond_i32 .

mov_i32

Moves a value from a register to another register.

IR Format: mov Rd, Rn
Gadget type: gadget per Rd + Rn combo (256)

mov Rd, Rn

mov_i64

Moves a value from a register to another register.

IR Format: mov Rd, Rn
Gadget type: gadget per Rd + Rn combo (256)

mov Xd, Xn

tci_movi_i32

Moves an 32b immediate into a register.

IR Format: mov Rd, #imm32
Gadget type: gadget per Rd (16)

ldr w27, [x28], #4
mov Wd, w27

tci_movi_i64

Moves an 64b immediate into a register.

IR Format: mov Rd, #imm64
Gadget type: gadget per Rd (16)

ldr x27, [x28], #4
mov Xd, x27