Native Backend

Overview

The native backend compiles TAC IR directly to machine code bytes. No LLVM, no intermediate assembly — tape emits raw instructions into a code buffer that the binary emitters wrap in PE/ELF/Mach-O format.

Two code generators exist:

Both produce an x64_module struct (shared output format) that the binary emitters consume.

Optimization and register allocation

Before code generation, each function goes through two TAC-to-TAC passes. tape run and the embedded VM run the same optimized TAC; -O0 and tape test’s VM run keep the TAC as lowered, and the VM/native parity tests hold every rewrite to its behaviour:

• Inlining (tac_inline.c): a small non-recursive callee returning nothing or a scalar is copied into its caller where it is called in a loop; a tiny leaf (a few instructions, no calls, no loop) at every call. A tiny leaf is not inlined into or out of a @constant_time function, and in the VM only calls in loops are inlined, so a script’s error call stack keeps its frames
• TAC optimizations (tac_opt.c): scalar replacement (a struct local whose address never escapes becomes a local per field), a range test x >= lo && x <= hi as one unsigned compare, forwarding of locals stored once, local value numbering, scalar globals kept in a register within a block and across a loop that calls nothing, loop-invariant code motion (a slice or struct parameter’s fields read once, before the loop), strength reduction, bounded remainders, a skipped block’s cheap work moved before its branch so the branch becomes a conditional move, dead-code removal

Each backend has two paths. The plain path (-O0) keeps every TAC register and local at a fixed stack slot, loaded into scratch registers before an operation and stored back after it. The optimizing path (the default) runs the passes above and then allocates registers with a linear-scan allocator (regalloc.c, shared by x86-64 and ARM64). Its variables are the function’s TAC registers and the local slots whose address is never taken. Liveness is computed over the control-flow graph; each variable gets a register or stays in its stack slot, intervals may be split at loop boundaries, and spill choice is weighted by use counts per loop depth. Planning before allocation turns constants into immediates, fuses a compare with the branch after it, folds address arithmetic into the address mode, and computes narrow integer operations at their own width.

; TAC: %r5 = add %r3, %r4    (%r3 in rbx, %r4 spilled, %r5 in r12)
mov r12, rbx
add r12, [rbp - N]

A variable without a register lives in a stack slot below the frame’s save area, and instructions read and write it there directly. On x86-64 only a variable that spends some of its life in memory gets one (a constant, a value in a register its whole life, a float in an XMM register and a vector variable need none); on ARM64 TAC register N’s slot is fixed ([x29 - S - 8*(N+1)], S the save area’s size).

x86-64 registers

ARM64 registers

Calling convention

Tape-to-tape calls pass arguments in the platform ABI’s registers, so the same assignments serve tape calls and C calls. Which registers a callee keeps across a tape call is tape’s own rule: on Windows every tape function keeps RSI and RDI, and the XMM registers are lost at a tape call on every target.

Win64

• Args 1–4: RCX, RDX, R8, R9 (positional — float args use XMM0–3 in same position)
• Args 5+: stack (right-to-left)
• 32-byte shadow space reserved by caller
• Return: RAX (or XMM0 for floats)

SysV (Linux x64, macOS x64)

• Integer args: RDI, RSI, RDX, RCX, R8, R9 (separate counter)
• Float args: XMM0–7 (separate counter)
• Args overflow: stack
• Return: RAX (or XMM0 for floats)

AAPCS64 (Linux ARM64, macOS ARM64)

• Args: x0–x7 (integer), d0–d7 (float, separate counter)
• Args overflow: stack, one 8-byte slot each (the standard AAPCS64 layout Linux uses)
• Return: x0 (or s0/d0 for floats)
• Frame pointer: x29, Link register: x30
• SP 16-byte aligned at call sites

Fixups

During code emission, forward references (branch targets, function calls, string addresses) emit placeholder bytes and record a fixup entry:

For ARM64, the same fixup kinds map to different encodings: BL (26-bit immediate) for calls, B/B.cond/CBZ (26/19-bit) for branches, ADR for function addresses, ADRP+ADD for strings and globals, and ADRP+ADD+LDR+BLR for extern calls through the GOT.

The code generators resolve the code-internal fixups (REL32, BLOCK, FN_ADDR) themselves; the binary emitters resolve the rest (EXTERN_RIP, STRING_RIP, GLOBAL_RIP) once the final layout of code, data and import tables is known.

Instruction encoding

x86-64

Direct byte emission: REX prefixes, ModR/M, SIB, displacement, immediates. A small built-in assembler provides helpers like emit_mov_reg_imm64, emit_load_slot, emit_store_slot.

ARM64

Fixed 32-bit instruction words. Helpers for MOVZ/MOVK (64-bit immediates), LDR/STR (scaled offset), ADD/SUB, ADR/ADRP, B/BL/B.cond, STP/LDP.

Output formats

Every executable’s entry stub first calls each module’s __tape_init (global initializers), then main, then exits with main’s result.

A t1/t2 program also gets a __tape_init that turns a stack overflow into the standard trap (trap: stack overflow, exit 101): a vectored exception handler plus SetThreadStackGuarantee on Windows, sigaltstack and a SIGSEGV/SIGBUS handler that checks the fault address against the stack’s range on Linux and macOS. The main thread’s stack is 8 MB on all three (the PE header asks Windows for 8 MB). String constants and const tables share the read-only string table; a table starts at a multiple of its element alignment.

PE64 (Windows) — pe64_emit / pe64_emit_dll

• Image base: 0x140000000
• .text: entry stub + user code
• .rdata: import directory, IAT, hint/name table, string constants
• .data: module globals (when there are any); .rsrc: the icon from @exeicon
• Entry stub: __tape_inits, main(), then ExitProcess via IAT
• DLL mode: adds export directory table (sorted by name)

PE32+ UEFI — pe64_emit_efi

--target uefi: the same PE32+ image, built for firmware (how a t0 kernel boots on a UEFI PC).

• Subsystem 10 (EFI application); no imports (firmware is reached only through the System Table); always a relocation directory
• Entry stub: saves the Microsoft x64 non-volatile registers, runs the __tape_inits, calls efi_main(ImageHandle, SystemTable) and returns its status
• No main; a trap stops in place unless the program defines __tape_trap

ELF64 Uusi — elf64_emit

• Virtual base: 0x100000000000
• Single LOAD segment (flat binary, no dynamic linker)
• Entry stub: __tape_inits, main, then the int 0x80 exit syscall
• Static linking only

ELF64 Uusi STO — elf64_emit_sto

• Shared object (.sto file, ET_DYN)
• Exports vtable: array of function pointers (one per pub fn)
• R_X86_64_RELATIVE relocations for the DSO loader to fixup at load time

ELF64 Linux — elf64_emit_linux

Both Linux targets, x86-64 (linux) and ARM64 (linux-arm64):

• Virtual base: 0x400000
• Dynamically linked: ET_EXEC with PT_INTERP → /lib64/ld-linux-x86-64.so.2 (x86-64) or /lib/ld-linux-aarch64.so.1 (ARM64)
• Extern functions are called through GOT slots bound at load time (R_X86_64_JUMP_SLOT / R_AARCH64_JUMP_SLOT, DF_BIND_NOW); no PLT stubs
• DT_RUNPATH $ORIGIN:/usr/lib/tape: runtime libraries are found next to the program, then where the tape .deb installs them
• Data segment (GOT, .dynamic, globals) 4 KiB-aligned on x86-64, 64 KiB-aligned on ARM64 (kernels with 64 KiB pages)
• Entry stub: __tape_inits, main, then the exit_group syscall (231 on x86-64, 94 on ARM64)
• No section headers

ELF64 shared object — elf64_emit_linux_shared

tape build --dll on both Linux targets: the runtime libraries written in tape (tapert100.so, image100.so) are built with it.

• ET_DYN linked at address 0; the code is the executable’s (RIP-relative / ADRP references only), so no text relocations
• .dynsym (imports undefined, @exports defined), .dynstr, SysV .hash, section headers for tools
• .rela.dyn: R_*_RELATIVE for const tables’ pointers and .init_array (each __tape_init), R_*_GLOB_DAT for the GOT slots extern calls go through
• DT_NEEDED per @link library, DT_SONAME (the output’s name), DT_RUNPATH $ORIGIN:/usr/lib/tape, DF_BIND_NOW
• PT_GNU_RELRO over the relocated data, .dynamic and GOT; PT_GNU_STACK not executable

ELF64 Object — elf64_emit_obj

• Relocatable object file (.o) for external linkers (--sto)
• The root module’s pub fns become global symbols, externs undefined symbols
• Module globals in .data (initial values, zeros for the rest)
• Relocations: R_X86_64_PLT32 / R_X86_64_PC32 (x86-64); ADR_GOT_PAGE + LD64_GOT_LO12_NC for extern calls and ADR_PREL_PG_HI21 + ADD_ABS_LO12_NC for strings (ARM64), the same for globals against .data

Mach-O (macOS) — macho64_emit / macho64_emit_dylib / macho64_emit_obj

Both macOS targets, x86-64 (macos) and ARM64 (macos-arm64):

• Text vmaddr: 0x100000000
• Page size: 16 KiB on ARM64, 4 KiB on x86-64
• Segments: __PAGEZERO, __TEXT (code + string constants), __DATA_CONST (GOT), __DATA (globals), __LINKEDIT
• Dyld chained fixups bind the GOT (one slot per symbol of a library, however the library is spelled); LC_MAIN entry
• LC_UUID in executables and dylibs (current dyld refuses an image without one): a hash of the image, so builds are reproducible
• Entry stub: __tape_inits, main, then the exit syscall
• LC_LOAD_DYLIB @rpath/<lib>.dylib for a library named without a path (absolute paths for the system’s), LC_RPATH @executable_path, then /usr/local/lib and /usr/lib: runtime libraries are found next to the program, whatever the working directory
• Code signature: every executable and dylib carries an ad-hoc, linker-style signature written by the emitter (SHA-256 per 4 KiB page; an executable’s marks __TEXT as the main binary’s executable segment), so it runs on Apple Silicon without codesign
• Dylib (--dll): MH_DYLIB at address 0, LC_ID_DYLIB @rpath/<name>.dylib, LC_LOAD_DYLIB @rpath/<lib>.dylib for tape-built libraries (absolute paths for the system’s), LC_RPATH @loader_path, exports trie, chained fixups (GOT binds; rebases for const tables and __mod_init_func), and an ad-hoc linker-style code signature (SHA-256 page hashes) so it loads on Apple Silicon
• Object mode (--sto): relocatable .o for other toolchains; module globals in __DATA,__data, reached by X86_64_RELOC_SIGNED against the section (x86-64) or PAGE21 + PAGEOFF12 against a local symbol per global (ARM64)

Codegen output structure

x64_module {
    code           // all function code concatenated (raw bytes)
    functions[]    // per-function: name, code_offset, code_size, frame_size, is_export
    externs[]      // extern functions: name, dll/library, fn_index
    load_libs[]    // libraries loaded with no import (a @link no extern fn binds to)
    strings[]      // string constants: data pointer + length
    str_relocs[]   // pointers inside string-table blobs (const tables holding text)
    globals[]      // module globals: size, initial value, data offset
    fixups[]       // unresolved references for emitters to patch
    target         // which platform this was generated for
    root_fn_*      // the root module's functions (what object files export)
}

Last modified: 2026-10-25 12:47:43 UTC