Outsmarting the Compiler

By Matt Keeter

In the current era of software development, the prevailing wisdom is that writing raw assembly is a fool's errand a waste of time. We assume that because compilers are the product of countless engineer-years, they possess a far more intimate knowledge of the processor than any single human could.

However, if you dig into ancient tomes, listen to the whispers in quiet watering holes, or read the graffiti on the walls of forgotten temples, a different narrative emerges. The legend suggests that compilers are surprisingly inept at optimizing code for interpreters, and that a human writing in assembly can still outperform them.

The Project: A Uxn Interpreter

To test this, I developed a high-performance interpreter for the Uxn CPU. For those unfamiliar, Uxn is a stack-based architecture featuring 256 distinct opcodes.

The core of the interpreter is a straightforward loop: it fetches a byte from RAM and then dispatches the corresponding instruction.

impl Uxn {
    /// Executes the VM from a specific address until a termination signal is reached.
    #[inline] 
    pub fn run<D: Device>(mut self, mut dev: mut D, mut pc: u16) {
        loop {
            let op = self.ram[usize::from(pc)];
            pc = pc.wrapping_add(1);
            
            // Dispatch to the opcode handler
            let Some(next) = self.op(op, dev, pc) else { 
                break; 
            };
            pc = next;
        }
    }

    /// Handles the execution of a single opcode
    #[inline] 
    fn op<D: Device>(mut self, op: u8, dev: mut D, pc: u16) -> Option<u16> {
        match op {
            0x00 => op::brk(self, dev, pc),
            0x01 => op::inc::0b000(self, dev, pc),
            0x02 => op::pop::0b000(self, dev, pc),
            0x03 => op::nip::0b000(self, dev, pc),
            0x04 => op::swp::0b000(self, dev, pc),
            0x05 => op::rot::0b000(self, dev, pc),
            0x06 => op::dup::0b000(self, dev, pc),
            0x07 => op::ovr::0b000(self, dev, pc),
            0x08 => op::equ::0b000(self, dev, pc),
            0x09 => op::neq::0b000(self, dev, pc),
            0x0a => op::gth::0b000(self, dev, pc),
            0x0b => op::lth::0b000(self, dev, pc),
            0x0c => op::jmp::0b000(self, dev, pc),
            0x0d => op::jcn::0b000(self, dev, pc),
            0x0e => op::jsr::0b000(self, dev, pc),
            // ... and so on
            _ => None,
        }
    }
}

Because the opcode implementations are monomorphized and inlined into Uxn::run, the compiler manages to keep several critical values in registers. This results in a respectable performance boost—roughly 10-20% faster than the reference implementation.

But can we do better? Let's dive into the assembly.

Architectural Context

To understand the assembly, we first need to map the Uxn CPU's memory layout:

The execution cycle is simple: load a byte from RAM $\rightarrow$ execute opcode. Since opcodes can modify RAM, the system supports self-modifying code.

Reverse-Engineering the Registers

By analyzing the generated assembly, I was able to determine how the compiler mapped the VM state to hardware registers.

Take the INC operation (which increments the top value of the data stack):

Assembly for INC: 0x100002d4c: ldrb w8, [x25] $\leftarrow$ Fetch data stack index 0x100002d50: ldrb w9, [x24, x8] $\leftarrow$ Fetch value at that index 0x100002d54: add w9, w9, #1 $\leftarrow$ Increment value 0x100002d58: strb w9, [x24, x8] $\leftarrow$ Store value back 0x100002d5c: b 0x100002d1c $\leftarrow$ Return to dispatch

From this, we can deduce the register mapping:

The Dispatch Loop

The most critical part of the interpreter is the dispatch loop. Here is how the compiler implemented it:

Dispatch Assembly: 0x100002d1c: and x10, x27, #0xffff $\leftarrow$ Mask PC to 16-bit 0x100002d20: ldr x8, [x20, #256] $\leftarrow$ Load RAM base address 0x100002d24: ldrb w10, [x8, x10] $\leftarrow$ Fetch opcode from RAM 0x100002d28: add w27, w27, #1 $\leftarrow$ Increment PC 0x100002d2c: adr x11, #-96 $\leftarrow$ Load jump table base 0x100002d30: ldrh w12, [x27, x10, lsl #1] $\leftarrow$ Load 2-byte offset 0x100002d34: add x11, x11, x12, lsl #2 $\leftarrow$ Calculate final address 0x100002d38: br x11 $\leftarrow$ Indirect branch to opcode

The compiler created a jump table consisting of 256 two-byte offsets. The target address is calculated as: $\text{Target} = \text{Base} + (\text{Offset} \times 4)$

I verified this by dumping the jump table using lldb:

(lldb) reg read x27
x27 = 0x0000000100170b10
(lldb) memory read -s2 -fu -c256 0x0000000100170b10
0x100170b10: 2923 0x100170b12: 31 0x100170b14: 36 ...

Identifying the Bottlenecks

After analyzing the assembly and profiling the execution, two major inefficiencies became apparent:

• Memory Indirection: Several vital values (like the RAM base and stack indices) are stored in memory. This forces the CPU to perform extra ldr operations (e.g., in the INC opcode) instead of keeping them in registers.
• Dispatch Overhead: The dispatch loop relies on a single indirect branch.

Profiling reveals that the ldrh instruction (loading the offset from the jump table) is a massive bottleneck, accounting for over 33% of the total runtime.

(Note: I suspect the profiler might be slightly misattributing some time, but the trend is clear.)