File size: 2,916 Bytes
9425aed | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | ; compiler.lli — the toolchain describes itself
; Sovereign LLI Self-Hosting Compiler Specification
; Ahmad Ali Parr · SnapKitty · 2026
; LLI Self-Description (Artifact 2 from spec)
∀ S . shape(parse(S)) = Stmt*
⇒ shape(extract(Stmt*)) = Requires*
⇒ shape(allocate(Requires*)) = AllocMap
⇒ shape(encode(Stmt*, AllocMap)) = Instr*
⇒ shape(prove(Instr*, Requires*)) = Proof*
⇒ shape(certify(Instr*, Proof*)) = (Binary, Cert)
⇒ verify(certify(·)) = ⊤
; Layer 8: DFA Parser (Finite State Transducer)
; Input: bit stream from WORM log / register file
; Output: lli_statement(Addr, Op, Args) facts → Scratch region
; Implementation: 256-state DFA, jump table in first 1KB of Weight memory
; Layer 9: Constraint Extractor (Pure Function)
; Reads lli_statement facts
; Looks up shape_rule/3 from compile-time constant table
; Writes requires_shape/3 facts
; Zero branching: table lookup only
; Layer 10: Linear Register Allocator
; Single forward pass over addresses 0..N-1
; live_range(Var, Start, End) from use-def chains (single backward scan)
; choose_min_reg: lowest free register at each step
; Free list: 16-bit bitmap in r15
; Complexity: O(N × 16)
; Layer 11: Instruction Encoder
; For each lli_statement in address order:
; 1. Fetch opcode from constant table
; 2. Fetch allocated registers for dst, src1, src2
; 3. Encode immediate
; 4. Write 32-bit instruction to Code memory region
; Emits emitted_instr/6 facts for verification
; Layer 12: Shape Prover (Compile-Time)
; Iterates all emitted_instr facts
; Checks requires_shape against reg_shape (propagated from allocation)
; reg_shape(Dst, OutShape) :- emitted_instr(Addr,Op,Dst,Src,_,_),
; requires_shape(Op,InShape,OutShape), reg_shape(Src,InShape).
; Fixed-point in ≤ N steps (monotone, finite lattice)
; Compilation fails if any :- emitted_instr(Addr,...), not shape_ok(Addr). triggers
; Layer 13: Certificate Assembler
; Collects shape_ok/1 derivations
; Collects allocation proofs (allocated/3)
; Collects bound proofs (length(Program) ≤ B_code)
; Hashes program binary (SHA-256 in ALU microcode)
; Signs with Ed25519 private key (Plasma Gate, Layer 0)
; Writes certificate to Receipts region of WORM log
; Layer 14: Binary Layout (Fixed, Verified)
; 0x0000_0000 - 0x0000_FFFF : Boot ROM (immutable, contains verifier)
; 0x0001_0000 - 0x000F_FFFF : Weight Region (read-only, signed manifest)
; 0x0010_0000 - 0x001F_FFFF : Code Region (this binary, max 1MB)
; 0x0020_0000 - 0x00FF_FFFF : KV Cache Region (dynamic, managed by scheduler)
; 0x0100_0000 - 0x01FF_FFFF : Activation Scratch (bounded by B_act)
; 0x0200_0000 - 0x02FF_FFFF : WORM Log (append-only, max 16MB)
; 0x0300_0000 - 0x0300_0FFF : Register File (memory-mapped)
; 0x0300_1000 - 0x0300_10FF : Control Unit State
; 0x0300_2000 - 0x0300_2FFF : Receipts / Certificates
|