{"article":{"slug":"an-ode-to-livelyness-analysis-ssa-to-registers","title":"An ode to livelyness analysis; SSA to registers","subtitle":null,"summary":"xnacly walks through liveness analysis on a block-local SSA IR and the register allocation built on it, for both the register-based bytecode VM and the x86 JIT of the purple-garden programming language.","content_type":"blog_post","language":"en","canonical_url":"https://xnacly.me/posts/2026/an-ode-to-livelyness-analysis/","author":{"name":"xnacly","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"xnacly","url":"https://xnacly.me/","listing_slug":null,"listing":null},"topics":[{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"rust","slug":"rust","url":"https://listedarticles.com/topics/rust"},{"name":"systems-programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":3091,"reading_minutes":13,"published_at":"2026-11-07T00:00:00.000Z","added_at":"2026-11-09T23:10:48.402Z","updated_at":"2026-11-09T23:10:48.402Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/an-ode-to-livelyness-analysis-ssa-to-registers","markdown_url":"https://listedarticles.com/articles/an-ode-to-livelyness-analysis-ssa-to-registers.md","example":false,"citation":"xnacly, xnacly. \"An ode to livelyness analysis; SSA to registers.\" 7 Nov 2026. https://xnacly.me/posts/2026/an-ode-to-livelyness-analysis/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://xnacly.me/posts/2026/an-ode-to-livelyness-analysis/"},"body_markdown":"# An ode to livelyness analysis; SSA to registers\n\n- Nov 7, 2026\n- 3225 Words\n- 16 Minute read\n\nTags:\n\n- [Rust](https://xnacly.me/tags/rust/)\n- [Pldev](https://xnacly.me/tags/pldev/)\n\n---\n\n> Or a loveletter? Read this while listening to Ode to Joy, also look at this awesome pixelart i did just for this article:\n>\n> ![livelyness analysis](https://xnacly.me/livelyness/icon.png)\n> *its analyzing a life* 🤓\n\nI am currently working on register allocation for both my register based\nbytecode virtual machine and my x86 just in time compiler, both for my\nprogramming language [purple-garden](https://github.com/xnacly/purple-garden).\n\nRegister allocation is assigning the unlimited amount of virtual registers to\nthe limited set of storage resources hardware has, specifically the gprs\n(general purpose registers), the fprs (floating point registers) and the stack\n(see [CPU Registers x86](https://wiki.osdev.org/CPU_Registers_x86) for an\nexamplary overview). The first step in this odeal is livelyness analsis.\n\n# A garden(ing) example\n\nTHe simplest, yet somewhat non trivial example would be:\n\nGARDEN\n\n```\n1fn f(a:Int n:Int acc:Int) Int {\n2    match {\n3        n < 1 { a + acc }\n4        { f(a n-1 acc*n) }\n5    }\n6}\n```\n\nThis is equiv to the following c code, which i “disassembled”\nfrom the very well written [Linear scan register allocation on\nSSA](https://bernsteinbear.com/blog/linear-scan/) article by Max\nBernstein[1](#fn:1), in which i didnt really understand the\nIR display, before translating it to c and then to my own\nlanguage (purple garden does not have loops 🤓 so this is only\nequiv when called with `f(a n 1)`):\n\nC\n\n```\n1long f(long a, long n) {\n2    long acc = 1;\n3    while (n >= 1) {\n4        acc = acc * n;\n5        n = n - 1;\n6    }\n7    return a + acc;\n8}\n```\n\nFeeding `f(a,n,acc: Int): Int` into purple gardens pipeline\nproduces the following, optimised immediate representation\n(using `-I`), this means some values were dead and thus removed [2](#fn:2):\n\nLLVM\n\n```\n 1fn f1(%v0:Int, %v1:Int, %v2:Int) -> Int {\n 2        b0(%v0, %v1, %v2):\n 3                %v4:Bool = ILt %v1, 1\n 4                br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2)\n 5        b1(%v5, %v6, %v7):\n 6                %v8:Int = IAdd %v5, %v7\n 7                ret %v8\n 8        b2(%v9, %v10, %v11):\n 9                %v13:Int = ISub %v10, 1\n10                %v14:Int = IMul %v11, %v10\n11                tail f1(%v9, %v13, %v14)\n12}\n```\n\n# PUrple garden IR structure and notation\n\nPurple gardens immediate representation is [static single assigment\n(SSA)](https://en.wikipedia.org/wiki/Static_single-assignment_form) form based,\nmeaning each value / virtual register is assigned exactly once and all are\nimmutable. They are notated with `%vN`, for virtual register or value, whatever\nyou (the reader) like more.\n\nCompared to many other ssa irs, pgir does not use phi nodes. I opted for block\nparams and terminators instead. It is made up of blocks, where each block has a\nlist of parameters, a terminator and a body of instructions, where each\ninstruction is in ssa form. All values are block local and the only\ninterblock dataflow is facilitated via block params and block terminators.\n\nLLVM\n\n```\n 1; block with id N\n 2; |\n 3; v\n 4  b2(%v0, %v1, %v2):\n 5;    ^^^^^^^^^^^^^ parameters 0..2\n 6\n 7;     value / virtual reg def\n 8;      |        instr kind\n 9;      |        |\n10;      v        v\n11      %v7:Int = ISub %v1, 1 ; <-- imm value\n12;         ^           ^ argument\n13;         |\n14;         instr result type\n15\n16;     terminator with params\n17      tail f1(%v0, %v7, %v8)\n```\n\nOr in rust terms:\n\nRUST\n\n```\n 1pub struct Block<'b, A: Allocator = Global> {\n 2    pub id: Id,\n 3    pub instructions: Vec<Instr<'b>, A>,\n 4    pub params: ParamsId,\n 5    pub term: Option<Terminator>,\n 6    // [...]\n 7}\n 8\n 9pub enum Instr<'i> {\n10    BinImm {\n11        op: BinOp,\n12        dst: TypeId<'i>,\n13        lhs: Id,\n14        imm: i32,\n15    },\n16    // [...]\n17    Noop,\n18}\n19\n20pub enum Terminator {\n21    Return {\n22        value: Option<Id>,\n23    },\n24    // [...]\n25    Tail {\n26        func: Id,\n27        args: ParamsId,\n28    },\n29    // [...]\n30}\n```\n\nPretty easy right?\n\n# Virtual registers / Values and their lifetimes\n\nLEts look at the previous IR example, but this time with virtual register\nlifetime annotations (when the cli is invoked with `-II`):\n\nLLVM\n\n```\n 1fn f1(%v0:Int, %v1:Int, %v2:Int) -> Int {             %v0 %v1 %v2 %v4 %v5 %v7 %v8 %v9 %v10 %v11 %v13 %v14\n 2    b0(%v0, %v1, %v2):                                |   |   |\n 3        %v4:Bool = ILt %v1, 1                         |   |   |   |\n 4        br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2)  |   |   |   |\n 5    b1(%v5, %v6, %v7):                                                |   |\n 6        %v8:Int = IAdd %v5, %v7                                       |   |   |\n 7        ret %v8                                                               |\n 8    b2(%v9, %v10, %v11):                                                          |   |    |\n 9        %v13:Int = ISub %v10, 1                                                   |   |    |    |\n10        %v14:Int = IMul %v11, %v10                                                |   |    |    |    |\n11        tail f1(%v9, %v13, %v14)                                                  |             |    |\n12}\n```\n\nThis display enables a visual understanding of the livetimes of\neach value, encoded as lo for start, and hi for last, the\nfollowing enables a non visual understanding: (The positions are\nlinearised: block params are at the block base, block instructions are\nat block base+1+instr pos and terminators are at block base+instr count+1)\n\n| value | lo | hi |\n| --- | --- | --- |\n| %v0 | 0 | 2 |\n| %v1 | 0 | 2 |\n| %v2 | 0 | 2 |\n| %v4 | 1 | 2 |\n| %v5 | 3 | 4 |\n| %v7 | 3 | 4 |\n| %v8 | 4 | 5 |\n| %v9 | 6 | 9 |\n| %v10 | 6 | 8 |\n| %v11 | 6 | 8 |\n| %v13 | 7 | 9 |\n| %v14 | 8 | 9 |\n\n# A short but sweet implementation:\n\nWith that out of the way the algorithm amounts to a simple:\n\n1. walk blocks\n2. visit terminator, observe all virtual register usages\n3. visit instructions in reverse, observe all virtual register definition and usages\n4. visit parameters to block, observe each\n\n## Observing\n\nWhere observing is defined as:\n\n- with tuple `(lo,hi)` and `pos`\n- if `hi==0`; set `hi=pos`\n- `lo=pos`\n\nIn oxidised terms:\n\nRUST\n\n```\n1/// observer Id := (lo,hi), always updates lo, only fills hi, if previously unset\n2fn observe<V: Allocator>(out: &mut Vec<(u32, u32), V>, id: Id, pos: u32) {\n3    let idx = id.0 as usize;\n4    let e = &mut out[idx];\n5    if e.1 == 0 {\n6        e.1 = pos;\n7    }\n8    e.0 = pos;\n9}\n```\n\n## Helpers to help with defs and usages:\n\nAsking for defs and uses in instructions and terminators:\n\n### Extracting definitions\n\nWhat it says, `Func::def_of` returns a definition of a virtual register, if\n`instr` has one:\n\nRUST\n\n```\n 1impl Func<'_> {\n 2    #[must_use]\n 3    pub fn def_of(instr: &Instr<'_>) -> Option<Id> {\n 4        match instr {\n 5            Instr::Alloc { dst, .. }\n 6            | Instr::Load { dst, .. }\n 7            | Instr::AddrOf { dst, .. }\n 8            | Instr::Bin { dst, .. }\n 9            | Instr::BinImm { dst, .. }\n10            | Instr::LoadConst { dst, .. }\n11            | Instr::Call { dst, .. }\n12            | Instr::Sys { dst, .. }\n13            | Instr::Cast { dst, .. }\n14            | Instr::Lookup { dst, .. }\n15            | Instr::Assert { dst, .. } => Some(dst.id),\n16            Instr::Store { .. } | Instr::Noop => None,\n17        }\n18    }\n19}\n```\n\n### Calling f for each usage of value in an instruction\n\nWhat it says, calling f for each value usage in an instruction\n\nRUST\n\n```\n 1pub fn for_each_use_of_instr(&self, instr: &Instr<'_>, mut f: impl FnMut(Id)) {\n 2    match instr {\n 3        Instr::Bin { lhs, rhs, .. } => {\n 4            f(*lhs);\n 5            f(*rhs);\n 6        }\n 7        Instr::BinImm { lhs, .. } => f(*lhs),\n 8        Instr::Call { args, .. } | Instr::Sys { args, .. } => {\n 9            for &a in self.params(*args) {\n10                f(a);\n11            }\n12        }\n13        Instr::Cast { from, .. } => f(from.id),\n14        Instr::Lookup { subject, .. } => f(*subject),\n15        Instr::Store { src, base, .. } => {\n16            f(*src);\n17            f(*base);\n18        }\n19        Instr::Assert { cond, .. } => f(*cond),\n20        Instr::Load { base, .. } | Instr::AddrOf { base, .. } => f(*base),\n21        Instr::LoadConst { .. } | Instr::Noop | Instr::Alloc { .. } => {}\n22    }\n23}\n```\n\n### Calling f for each usage of value in a terminator\n\nWhat it says, calling f for each value usage in a terminator\n\nRUST\n\n```\n 1pub fn for_each_use_of_term(&self, term: &Terminator, mut f: impl FnMut(Id)) {\n 2    match term {\n 3        Terminator::Return {\n 4            value: Some(id), ..\n 5        } => f(*id),\n 6        Terminator::Return { value: None, .. } => {}\n 7        Terminator::Jump { params, .. } => {\n 8            for &p in self.params(*params) {\n 9                f(p);\n10            }\n11        }\n12        Terminator::Tail { args, .. } => {\n13            for &a in self.params(*args) {\n14                f(a);\n15            }\n16        }\n17        Terminator::Switch {\n18            subject,\n19            cases,\n20            default: (_, default_params),\n21            ..\n22        } => {\n23            f(*subject);\n24            for case in self.cases(*cases) {\n25                for &p in self.params(case.target.1) {\n26                    f(p);\n27                }\n28            }\n29            for &p in self.params(*default_params) {\n30                f(p);\n31            }\n32        }\n33        Terminator::Branch {\n34            cond,\n35            yes: (_, yes_params),\n36            no: (_, no_params),\n37            ..\n38        } => {\n39            f(*cond);\n40            for &p in self.params(*yes_params) {\n41                f(p);\n42            }\n43            for &p in self.params(*no_params) {\n44                f(p);\n45            }\n46        }\n47        Terminator::BranchCmpImm {\n48            lhs,\n49            yes: (_, yes_params),\n50            no: (_, no_params),\n51            ..\n52        }\n53        | Terminator::BranchCmp {\n54            lhs,\n55            yes: (_, yes_params),\n56            no: (_, no_params),\n57            ..\n58        } => {\n59            f(*lhs);\n60            if let Terminator::BranchCmp { rhs, .. } = term {\n61                f(*rhs);\n62            }\n63            for &p in self.params(*yes_params) {\n64                f(p);\n65            }\n66            for &p in self.params(*no_params) {\n67                f(p);\n68            }\n69        }\n70    }\n71}\n```\n\n## Fully rusted together:\n\nA few quick context injectors:\n\n- out is a reusable Vec allocated in the V allocator, thats why its reset and resized\n- UNSET is used as the default empty value\n- Func::next\\_id() returns the highest id defined in the function (self)+1\n\nRUST\n\n```\n 1impl<A: Allocator> Func<'_, A> {\n 2    pub fn live_set_into<V: Allocator>(&self, out: &mut Vec<(u32, u32), V>) {\n 3        const UNSET: (u32, u32) = (u32::MAX, 0u32);\n 4\n 5        out.clear();\n 6        out.resize(self.next_id() as usize, UNSET);\n 7\n 8        // observe defined as before\n 9\n10        let mut base = 0;\n11        for block in self.blocks.iter().filter(|b| !b.tombstone) {\n12            let block_offset = block.instructions.len();\n13            let offset = base;\n14            if let Some(term) = &block.term {\n15                self.for_each_use_of_term(term, |id| {\n16                    // term is instruction count +1\n17                    observe(out, id, (offset + block_offset + 1) as u32)\n18                });\n19            }\n20\n21            for (i, instr) in block.instructions.iter().enumerate().rev() {\n22                // +1, so it cant start at 0, since thats where the params start :)\n23                let pos = (base + 1 + i) as u32;\n24                self.for_each_use_of_instr(instr, |id| observe(out, id, pos));\n25                if let Some(def) = Func::def_of(instr) {\n26                    observe(out, def, pos)\n27                }\n28            }\n29\n30            for &p in self.params(block.params) {\n31                observe(out, p, base as u32);\n32            }\n33\n34            // params + instructions + terminator\n35            base += block_offset + 2;\n36        }\n37    }\n38}\n```\n\n# Wiring liveset analysis into register allocation for the bytecode backend\n\nSince we now know where what value is alive and where it is to be considered\ndead we can pass this information to the register allocator and ask it for the\nregister or stack slot of any value we have to fit into hardware or virtual\nmachine constraints.\n\n## Prep and register allocation prepass\n\nWhen compiling the IR to bytecode for the purple garden vm, the first step is\nto compute the liveset, with the algorithm introduced before and then\nperforming the preallocation pass with the `Cc::prealloc` method:\n\nRUST\n\n```\n 1impl<'cc, S: Allocator + Clone, A: Allocator + Clone> Cc<'cc, S, A> {\n 2    fn cc<F: Allocator>(\n 3        &mut self,\n 4        fun: &'cc Func<'cc, F>,\n 5        native: Option<&mut purple_garden_jit::CodeArena<impl Pages>>,\n 6    ) {\n 7        // [...]\n 8\n 9        // compute liveset\n10        fun.live_set_into(&mut self.live_set);\n11\n12        // walk the IR once before lowering, after this its just a simple\n13        // lookup\n14        self.prealloc(fun);\n15\n16        // [...] iterate blocks\n17\n18            // [...] iterate instructions\n19\n20                // secret postprocessing of instructions which dst points to the stack\n21                if let Some(Location::Stack(slot)) =\n22                    Func::def_of(instruction).and_then(|dst| self.regalloc.location(dst))\n23                {\n24                    self.emit(Op::StoreSlot { slot, src: TMP });\n25                }\n26    }\n27}\n```\n\n## Lowering Bin ir ops\n\nBin is the baseline operator. The BinImm ops we see in our example (`ISub %v10, 1`) are optimisations (one less dispatch, less memory interactions) compiled in\nthe same way, just with an immediate rhs:\n\nRUST\n\n```\n 1impl<'cc, S: Allocator + Clone, A: Allocator + Clone> Cc<'cc, S, A> {\n 2    fn instr<F: Allocator>(&mut self, owner: &'cc Func<'cc, F>, i: &'cc ir::Instr<'cc>) {\n 3        match i {\n 4            // [...] all the other IR instructions\n 5            ir::Instr::Bin {\n 6                op, dst, lhs, rhs, ..\n 7            } => {\n 8                // interacting with the register alloc prepass\n 9                let dst = self.def_register(dst.id);\n10                let lhs = self.ensure_register(*lhs);\n11                let rhs = self.ensure_register(*rhs);\n12\n13                macro_rules! emit_bins {\n14                    ($($name:ident),*) => {\n15                        match op {\n16                            $(\n17                                ir::BinOp::$name => {\n18                                    Op::$name {\n19                                        dst,\n20                                        lhs,\n21                                        rhs,\n22                                    }\n23                                },\n24                            )*\n25                        }\n26                    };\n27                }\n28\n29                self.emit(emit_bins! {\n30                    IAdd, ISub, IMul, IDiv, IMod, IAnd, ILt, IGt, IEq,\n31                    DAdd, DSub, DMul, DDiv, DLt, DGt,\n32                    BEq, SEq\n33                });\n34            }\n35            ir::Instr::BinImm {\n36                op, dst, lhs, imm, ..\n37            } => {\n38                let dst = self.def_register(dst.id);\n39                let lhs = self.ensure_register(*lhs);\n40                let imm = *imm;\n41\n42                macro_rules! emit_bin_imms {\n43                    ($($ir:ident => $op:ident),* $(,)?) => {\n44                        match op {\n45                            $(ir::BinOp::$ir => Op::$op { dst, lhs, imm },)*\n46                            _ => unreachable!(\"only integer immediate binops are represented as BinImm\"),\n47                        }\n48                    };\n49                }\n50\n51                self.emit(emit_bin_imms! {\n52                    IAdd => IAddI,\n53                    ISub => ISubI,\n54                    IMul => IMulI,\n55                    IDiv => IDivI,\n56                    IMod => IModI,\n57                    IAnd => IAndI,\n58                    IEq  => IEqI,\n59                    IGt  => IGtI,\n60                    ILt  => ILtI,\n61                });\n62            }\n63        }\n64    }\n65}\n```\n\nThis is so clean and a nice use of rust macros, i love this, dont @me; lowering\nall binary and binary with immediate value operations in 57 lines is where its\nat.\n\n## Ensuring and definining a register\n\nTwo helpers for making sure a requested virtual register is accessible to a\npoint where operations can be applied on it, the first one being ensure\\_register:\n\nRUST\n\n```\n 1/// Translate virtual register into vm register, abstracts spilling, restoring and register\n 2/// allocation in general away\n 3fn ensure_register(&mut self, id: Id) -> u8 {\n 4    match self.regalloc.location(id) {\n 5        Some(Location::Reg(r)) => return r.num(),\n 6        // requested value lives on the stack, we need to restore it and we use a temp\n 7        // register\n 8        Some(Location::Stack(slot)) => {\n 9            let dst = self.next_tmp();\n10            self.emit(Op::LoadSlot { dst, slot });\n11            dst\n12        }\n13        None => unreachable!(\"%v{} has no location\", id.0),\n14    }\n15}\n16\n17fn next_tmp(&self) -> u8 {\n18    match self.buf.last() {\n19        Some(Op::LoadSlot { dst: SCRATCH, .. }) => TMP,\n20        _ => SCRATCH,\n21    }\n22}\n```\n\nThis means if a value is requested and:\n\n- the prepass assigned it to a register, thats perfect and we can simply use it\n- or if its on the stack we have to ask the compiler state for a temporary\n  register and materialise the value into it\n\n> Temporary registers in the virtual machine are defined as `SCRATCH` and `TMP`, respectively in the preamble of the virtual machines source code:\n>\n> RUST\n>\n> ```\n>  1pub const REGISTER_COUNT: usize = 32;\n>  2const SCRATCH: u8 = REGISTER_COUNT as u8 - 1;\n>  3const TMP: u8 = SCRATCH - 1;\n>  4\n>  5/// Every vm register but [`SCRATCH`] and [`TMP`], r0 last since xralloc2 hands\n>  6/// out the lowest free one first, which also puts the caller-saved registers\n>  7/// before the callee-saved ones.\n>  8const POOL: [u8; TMP as usize] = {\n>  9    let mut pool = [0; TMP as usize];\n> 10    let mut i = 0;\n> 11    while i < TMP as usize {\n> 12        pool[i] = (TMP as usize - 1 - i) as u8;\n> 13        i += 1;\n> 14    }\n> 15    pool\n> 16};\n> ```\n\nThusfar ensure is simple to understand, the other helper is def\\_register, which\nmeans we, again, take the registers number, if it has one, otherwise we take\nTMP, which our previously introduced (and probably not noticed by anyone)\nsnipped at the end of the codeblock in [Prep and register allocation prepass](#prep-and-register-allocation-prepass)then “spills” into its slot on the\nstack with the respective bytecode instruction.\n\nRUST\n\n```\n1/// The register an op writes `id` into, [`TMP`] if `id` lives in a slot: the block loop stores\n2/// it there after the op.\n3fn def_register(&self, id: Id) -> u8 {\n4    match self.regalloc.location(id) {\n5        Some(Location::Reg(r)) => r.num(),\n6        Some(Location::Stack(_)) => TMP,\n7        None => unreachable!(\"%v{} has no location\", id.0),\n8    }\n9}\n```\n\n## All the bytes and the codes together:\n\nSwapping `-I` for `-D` (with `--no-jit`, otherwise we would get machinecode 🤓), results in the following\nvirtual machine registers assigned to the ssa values:\n\nASM\n\n```\n 100000000 <f>:\n 2  0000:    ilt_imm r3, r1, #1        ; 4: n < 1 { a + acc }\n 3  0001:    jmpf r3, 0004 <f.bb_0004>\n 4  0002:    iadd r0, r0, r2\n 5  0003:    ret\n 600000004 <f.bb_0004>:\n 7  0004:    isub_imm r3, r1, #1       ; 5: { f(a n-1 acc*n) }\n 8  0005:    imul r2, r2, r1\n 9  0006:    mov r1, r3\n10  0007:    tail 0000 <f>\n```\n\n## JIT :O\n\nFor the crazy hackermans, here is the same example with the jit on, jit and bc\nshare IR, liveness analysis, register allocation and standard libary, aint that\nfun?\n\nASM\n\n```\n 10000000000000000 <jit_f>:\n 2   0:   48 81 fa 01 00 00 00    cmp    $0x1,%rdx\n 3   7:   49 c7 c0 00 00 00 00    mov    $0x0,%r8\n 4   e:   41 0f 9c c0             setl   %r8b\n 5  12:   4d 85 c0                test   %r8,%r8\n 6  15:   0f 84 0b 00 00 00       je     26 <jit_f+0x26>\n 7  1b:   48 01 ce                add    %rcx,%rsi\n 8  1e:   48 89 f0                mov    %rsi,%rax\n 9  21:   c3                      ret\n10  22:   cc                      int3\n11  23:   cc                      int3\n12  24:   cc                      int3\n13  25:   cc                      int3\n14  26:   49 89 d0                mov    %rdx,%r8\n15  29:   49 81 e8 01 00 00 00    sub    $0x1,%r8\n16  30:   49 89 c9                mov    %rcx,%r9\n17  33:   4c 0f af ca             imul   %rdx,%r9\n18  37:   4c 89 c2                mov    %r8,%rdx\n19  3a:   4c 89 c9                mov    %r9,%rcx\n20  3d:   e9 be ff ff ff          jmp    0 <jit_f>\n21  42:   c3                      ret\n```\n\n> Dont be mean to the x86 output, i know this could be shorter, the compare and\n> jmp could be a single instr and there is a lot of dead code and long\n> encodings, but this is my first jit and im glad it works at all :)\n\n# Future work\n\nThe attentive reader may have figured out how i have described the inputs and\nouputs of the register allocator, respectively the liveset (and the pool of\nregs) and assignment of virtual to physical register, but have not actually\nshown or introduced the register allocator itself, or the results of the IR\ndesign which forces the regalloc to treat all block transitions (jumps,\nentries, returns) as edge moves and has to do extra work to resolve these.\n\nIf my motivation holds up i will write a follow up article about these topics,\nbut right now i am still in the process of “perfecting” the interactions\nbetween my ir, my regalloc and my backends, so maybe stay tuned? I have an rss\nfeed if anyone is actually at the end of the abyss im screaming my incohesive\nblabbering into.\n\n---\n\n1. Thats the [Z|Y]JIT guy btw, absolutely insane articles, everyone interested in anything compiler related should have read at least twice [↩︎](#fnref:1)\n2. Optimised here means: inline immediates for comparisons and\n   arithmetics, tailcalls and removed blocks just used for indirect returns [↩︎](#fnref:2)\n","body_html":"<h1 id=\"an-ode-to-livelyness-analysis-ssa-to-registers\">An ode to livelyness analysis; SSA to registers</h1>\n<ul><li>Nov 7, 2026</li><li>3225 Words</li><li>16 Minute read</li></ul>\n<p>Tags:</p>\n<ul><li><a href=\"https://xnacly.me/tags/rust/\" rel=\"nofollow ugc noopener\">Rust</a></li><li><a href=\"https://xnacly.me/tags/pldev/\" rel=\"nofollow ugc noopener\">Pldev</a></li></ul>\n<hr />\n<blockquote><p>Or a loveletter? Read this while listening to Ode to Joy, also look at this awesome pixelart i did just for this article:</p>\n<figure><img src=\"https://xnacly.me/livelyness/icon.png\" alt=\"livelyness analysis\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p><em>its analyzing a life</em> 🤓</p></blockquote>\n<p>I am currently working on register allocation for both my register based\nbytecode virtual machine and my x86 just in time compiler, both for my\nprogramming language <a href=\"https://github.com/xnacly/purple-garden\" rel=\"nofollow ugc noopener\">purple-garden</a>.</p>\n<p>Register allocation is assigning the unlimited amount of virtual registers to\nthe limited set of storage resources hardware has, specifically the gprs\n(general purpose registers), the fprs (floating point registers) and the stack\n(see <a href=\"https://wiki.osdev.org/CPU_Registers_x86\" rel=\"nofollow ugc noopener\">CPU Registers x86</a> for an\nexamplary overview). The first step in this odeal is livelyness analsis.</p>\n<h1 id=\"a-garden-ing-example\">A garden(ing) example</h1>\n<p>THe simplest, yet somewhat non trivial example would be:</p>\n<p>GARDEN</p>\n<pre><code>1fn f(a:Int n:Int acc:Int) Int {\n2    match {\n3        n &lt; 1 { a + acc }\n4        { f(a n-1 acc*n) }\n5    }\n6}</code></pre>\n<p>This is equiv to the following c code, which i “disassembled”\nfrom the very well written <a href=\"https://bernsteinbear.com/blog/linear-scan/\" rel=\"nofollow ugc noopener\">Linear scan register allocation on\nSSA</a> article by Max\nBernstein<a href=\"#fn:1\">1</a>, in which i didnt really understand the\nIR display, before translating it to c and then to my own\nlanguage (purple garden does not have loops 🤓 so this is only\nequiv when called with <code>f(a n 1)</code>):</p>\n<p>C</p>\n<pre><code>1long f(long a, long n) {\n2    long acc = 1;\n3    while (n &gt;= 1) {\n4        acc = acc * n;\n5        n = n - 1;\n6    }\n7    return a + acc;\n8}</code></pre>\n<p>Feeding <code>f(a,n,acc: Int): Int</code> into purple gardens pipeline\nproduces the following, optimised immediate representation\n(using <code>-I</code>), this means some values were dead and thus removed <a href=\"#fn:2\">2</a>:</p>\n<p>LLVM</p>\n<pre><code> 1fn f1(%v0:Int, %v1:Int, %v2:Int) -&gt; Int {\n 2        b0(%v0, %v1, %v2):\n 3                %v4:Bool = ILt %v1, 1\n 4                br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2)\n 5        b1(%v5, %v6, %v7):\n 6                %v8:Int = IAdd %v5, %v7\n 7                ret %v8\n 8        b2(%v9, %v10, %v11):\n 9                %v13:Int = ISub %v10, 1\n10                %v14:Int = IMul %v11, %v10\n11                tail f1(%v9, %v13, %v14)\n12}</code></pre>\n<h1 id=\"purple-garden-ir-structure-and-notation\">PUrple garden IR structure and notation</h1>\n<p>Purple gardens immediate representation is <a href=\"https://en.wikipedia.org/wiki/Static_single-assignment_form\" rel=\"nofollow ugc noopener\">static single assigment\n(SSA)</a> form based,\nmeaning each value / virtual register is assigned exactly once and all are\nimmutable. They are notated with <code>%vN</code>, for virtual register or value, whatever\nyou (the reader) like more.</p>\n<p>Compared to many other ssa irs, pgir does not use phi nodes. I opted for block\nparams and terminators instead. It is made up of blocks, where each block has a\nlist of parameters, a terminator and a body of instructions, where each\ninstruction is in ssa form. All values are block local and the only\ninterblock dataflow is facilitated via block params and block terminators.</p>\n<p>LLVM</p>\n<pre><code> 1; block with id N\n 2; |\n 3; v\n 4  b2(%v0, %v1, %v2):\n 5;    ^^^^^^^^^^^^^ parameters 0..2\n 6\n 7;     value / virtual reg def\n 8;      |        instr kind\n 9;      |        |\n10;      v        v\n11      %v7:Int = ISub %v1, 1 ; &lt;-- imm value\n12;         ^           ^ argument\n13;         |\n14;         instr result type\n15\n16;     terminator with params\n17      tail f1(%v0, %v7, %v8)</code></pre>\n<p>Or in rust terms:</p>\n<p>RUST</p>\n<pre><code> 1pub struct Block&lt;&#39;b, A: Allocator = Global&gt; {\n 2    pub id: Id,\n 3    pub instructions: Vec&lt;Instr&lt;&#39;b&gt;, A&gt;,\n 4    pub params: ParamsId,\n 5    pub term: Option&lt;Terminator&gt;,\n 6    // [...]\n 7}\n 8\n 9pub enum Instr&lt;&#39;i&gt; {\n10    BinImm {\n11        op: BinOp,\n12        dst: TypeId&lt;&#39;i&gt;,\n13        lhs: Id,\n14        imm: i32,\n15    },\n16    // [...]\n17    Noop,\n18}\n19\n20pub enum Terminator {\n21    Return {\n22        value: Option&lt;Id&gt;,\n23    },\n24    // [...]\n25    Tail {\n26        func: Id,\n27        args: ParamsId,\n28    },\n29    // [...]\n30}</code></pre>\n<p>Pretty easy right?</p>\n<h1 id=\"virtual-registers-values-and-their-lifetimes\">Virtual registers / Values and their lifetimes</h1>\n<p>LEts look at the previous IR example, but this time with virtual register\nlifetime annotations (when the cli is invoked with <code>-II</code>):</p>\n<p>LLVM</p>\n<pre><code> 1fn f1(%v0:Int, %v1:Int, %v2:Int) -&gt; Int {             %v0 %v1 %v2 %v4 %v5 %v7 %v8 %v9 %v10 %v11 %v13 %v14\n 2    b0(%v0, %v1, %v2):                                |   |   |\n 3        %v4:Bool = ILt %v1, 1                         |   |   |   |\n 4        br %v4, b1(%v0, %v1, %v2), b2(%v0, %v1, %v2)  |   |   |   |\n 5    b1(%v5, %v6, %v7):                                                |   |\n 6        %v8:Int = IAdd %v5, %v7                                       |   |   |\n 7        ret %v8                                                               |\n 8    b2(%v9, %v10, %v11):                                                          |   |    |\n 9        %v13:Int = ISub %v10, 1                                                   |   |    |    |\n10        %v14:Int = IMul %v11, %v10                                                |   |    |    |    |\n11        tail f1(%v9, %v13, %v14)                                                  |             |    |\n12}</code></pre>\n<p>This display enables a visual understanding of the livetimes of\neach value, encoded as lo for start, and hi for last, the\nfollowing enables a non visual understanding: (The positions are\nlinearised: block params are at the block base, block instructions are\nat block base+1+instr pos and terminators are at block base+instr count+1)</p>\n<div class=\"table-wrap\"><table><thead><tr><th>value</th><th>lo</th><th>hi</th></tr></thead><tbody><tr><td>%v0</td><td>0</td><td>2</td></tr><tr><td>%v1</td><td>0</td><td>2</td></tr><tr><td>%v2</td><td>0</td><td>2</td></tr><tr><td>%v4</td><td>1</td><td>2</td></tr><tr><td>%v5</td><td>3</td><td>4</td></tr><tr><td>%v7</td><td>3</td><td>4</td></tr><tr><td>%v8</td><td>4</td><td>5</td></tr><tr><td>%v9</td><td>6</td><td>9</td></tr><tr><td>%v10</td><td>6</td><td>8</td></tr><tr><td>%v11</td><td>6</td><td>8</td></tr><tr><td>%v13</td><td>7</td><td>9</td></tr><tr><td>%v14</td><td>8</td><td>9</td></tr></tbody></table></div>\n<h1 id=\"a-short-but-sweet-implementation\">A short but sweet implementation:</h1>\n<p>With that out of the way the algorithm amounts to a simple:</p>\n<ol><li>walk blocks</li><li>visit terminator, observe all virtual register usages</li><li>visit instructions in reverse, observe all virtual register definition and usages</li><li>visit parameters to block, observe each</li></ol>\n<h2 id=\"observing\">Observing</h2>\n<p>Where observing is defined as:</p>\n<ul><li>with tuple <code>(lo,hi)</code> and <code>pos</code></li><li>if <code>hi==0</code>; set <code>hi=pos</code></li><li><code>lo=pos</code></li></ul>\n<p>In oxidised terms:</p>\n<p>RUST</p>\n<pre><code>1/// observer Id := (lo,hi), always updates lo, only fills hi, if previously unset\n2fn observe&lt;V: Allocator&gt;(out: &amp;mut Vec&lt;(u32, u32), V&gt;, id: Id, pos: u32) {\n3    let idx = id.0 as usize;\n4    let e = &amp;mut out[idx];\n5    if e.1 == 0 {\n6        e.1 = pos;\n7    }\n8    e.0 = pos;\n9}</code></pre>\n<h2 id=\"helpers-to-help-with-defs-and-usages\">Helpers to help with defs and usages:</h2>\n<p>Asking for defs and uses in instructions and terminators:</p>\n<h3 id=\"extracting-definitions\">Extracting definitions</h3>\n<p>What it says, <code>Func::def_of</code> returns a definition of a virtual register, if\n<code>instr</code> has one:</p>\n<p>RUST</p>\n<pre><code> 1impl Func&lt;&#39;_&gt; {\n 2    #[must_use]\n 3    pub fn def_of(instr: &amp;Instr&lt;&#39;_&gt;) -&gt; Option&lt;Id&gt; {\n 4        match instr {\n 5            Instr::Alloc { dst, .. }\n 6            | Instr::Load { dst, .. }\n 7            | Instr::AddrOf { dst, .. }\n 8            | Instr::Bin { dst, .. }\n 9            | Instr::BinImm { dst, .. }\n10            | Instr::LoadConst { dst, .. }\n11            | Instr::Call { dst, .. }\n12            | Instr::Sys { dst, .. }\n13            | Instr::Cast { dst, .. }\n14            | Instr::Lookup { dst, .. }\n15            | Instr::Assert { dst, .. } =&gt; Some(dst.id),\n16            Instr::Store { .. } | Instr::Noop =&gt; None,\n17        }\n18    }\n19}</code></pre>\n<h3 id=\"calling-f-for-each-usage-of-value-in-an-instruction\">Calling f for each usage of value in an instruction</h3>\n<p>What it says, calling f for each value usage in an instruction</p>\n<p>RUST</p>\n<pre><code> 1pub fn for_each_use_of_instr(&amp;self, instr: &amp;Instr&lt;&#39;_&gt;, mut f: impl FnMut(Id)) {\n 2    match instr {\n 3        Instr::Bin { lhs, rhs, .. } =&gt; {\n 4            f(*lhs);\n 5            f(*rhs);\n 6        }\n 7        Instr::BinImm { lhs, .. } =&gt; f(*lhs),\n 8        Instr::Call { args, .. } | Instr::Sys { args, .. } =&gt; {\n 9            for &amp;a in self.params(*args) {\n10                f(a);\n11            }\n12        }\n13        Instr::Cast { from, .. } =&gt; f(from.id),\n14        Instr::Lookup { subject, .. } =&gt; f(*subject),\n15        Instr::Store { src, base, .. } =&gt; {\n16            f(*src);\n17            f(*base);\n18        }\n19        Instr::Assert { cond, .. } =&gt; f(*cond),\n20        Instr::Load { base, .. } | Instr::AddrOf { base, .. } =&gt; f(*base),\n21        Instr::LoadConst { .. } | Instr::Noop | Instr::Alloc { .. } =&gt; {}\n22    }\n23}</code></pre>\n<h3 id=\"calling-f-for-each-usage-of-value-in-a-terminator\">Calling f for each usage of value in a terminator</h3>\n<p>What it says, calling f for each value usage in a terminator</p>\n<p>RUST</p>\n<pre><code> 1pub fn for_each_use_of_term(&amp;self, term: &amp;Terminator, mut f: impl FnMut(Id)) {\n 2    match term {\n 3        Terminator::Return {\n 4            value: Some(id), ..\n 5        } =&gt; f(*id),\n 6        Terminator::Return { value: None, .. } =&gt; {}\n 7        Terminator::Jump { params, .. } =&gt; {\n 8            for &amp;p in self.params(*params) {\n 9                f(p);\n10            }\n11        }\n12        Terminator::Tail { args, .. } =&gt; {\n13            for &amp;a in self.params(*args) {\n14                f(a);\n15            }\n16        }\n17        Terminator::Switch {\n18            subject,\n19            cases,\n20            default: (_, default_params),\n21            ..\n22        } =&gt; {\n23            f(*subject);\n24            for case in self.cases(*cases) {\n25                for &amp;p in self.params(case.target.1) {\n26                    f(p);\n27                }\n28            }\n29            for &amp;p in self.params(*default_params) {\n30                f(p);\n31            }\n32        }\n33        Terminator::Branch {\n34            cond,\n35            yes: (_, yes_params),\n36            no: (_, no_params),\n37            ..\n38        } =&gt; {\n39            f(*cond);\n40            for &amp;p in self.params(*yes_params) {\n41                f(p);\n42            }\n43            for &amp;p in self.params(*no_params) {\n44                f(p);\n45            }\n46        }\n47        Terminator::BranchCmpImm {\n48            lhs,\n49            yes: (_, yes_params),\n50            no: (_, no_params),\n51            ..\n52        }\n53        | Terminator::BranchCmp {\n54            lhs,\n55            yes: (_, yes_params),\n56            no: (_, no_params),\n57            ..\n58        } =&gt; {\n59            f(*lhs);\n60            if let Terminator::BranchCmp { rhs, .. } = term {\n61                f(*rhs);\n62            }\n63            for &amp;p in self.params(*yes_params) {\n64                f(p);\n65            }\n66            for &amp;p in self.params(*no_params) {\n67                f(p);\n68            }\n69        }\n70    }\n71}</code></pre>\n<h2 id=\"fully-rusted-together\">Fully rusted together:</h2>\n<p>A few quick context injectors:</p>\n<ul><li>out is a reusable Vec allocated in the V allocator, thats why its reset and resized</li><li>UNSET is used as the default empty value</li><li>Func::next_id() returns the highest id defined in the function (self)+1</li></ul>\n<p>RUST</p>\n<pre><code> 1impl&lt;A: Allocator&gt; Func&lt;&#39;_, A&gt; {\n 2    pub fn live_set_into&lt;V: Allocator&gt;(&amp;self, out: &amp;mut Vec&lt;(u32, u32), V&gt;) {\n 3        const UNSET: (u32, u32) = (u32::MAX, 0u32);\n 4\n 5        out.clear();\n 6        out.resize(self.next_id() as usize, UNSET);\n 7\n 8        // observe defined as before\n 9\n10        let mut base = 0;\n11        for block in self.blocks.iter().filter(|b| !b.tombstone) {\n12            let block_offset = block.instructions.len();\n13            let offset = base;\n14            if let Some(term) = &amp;block.term {\n15                self.for_each_use_of_term(term, |id| {\n16                    // term is instruction count +1\n17                    observe(out, id, (offset + block_offset + 1) as u32)\n18                });\n19            }\n20\n21            for (i, instr) in block.instructions.iter().enumerate().rev() {\n22                // +1, so it cant start at 0, since thats where the params start :)\n23                let pos = (base + 1 + i) as u32;\n24                self.for_each_use_of_instr(instr, |id| observe(out, id, pos));\n25                if let Some(def) = Func::def_of(instr) {\n26                    observe(out, def, pos)\n27                }\n28            }\n29\n30            for &amp;p in self.params(block.params) {\n31                observe(out, p, base as u32);\n32            }\n33\n34            // params + instructions + terminator\n35            base += block_offset + 2;\n36        }\n37    }\n38}</code></pre>\n<h1 id=\"wiring-liveset-analysis-into-register-allocation-for-the-bytecod\">Wiring liveset analysis into register allocation for the bytecode backend</h1>\n<p>Since we now know where what value is alive and where it is to be considered\ndead we can pass this information to the register allocator and ask it for the\nregister or stack slot of any value we have to fit into hardware or virtual\nmachine constraints.</p>\n<h2 id=\"prep-and-register-allocation-prepass\">Prep and register allocation prepass</h2>\n<p>When compiling the IR to bytecode for the purple garden vm, the first step is\nto compute the liveset, with the algorithm introduced before and then\nperforming the preallocation pass with the <code>Cc::prealloc</code> method:</p>\n<p>RUST</p>\n<pre><code> 1impl&lt;&#39;cc, S: Allocator + Clone, A: Allocator + Clone&gt; Cc&lt;&#39;cc, S, A&gt; {\n 2    fn cc&lt;F: Allocator&gt;(\n 3        &amp;mut self,\n 4        fun: &amp;&#39;cc Func&lt;&#39;cc, F&gt;,\n 5        native: Option&lt;&amp;mut purple_garden_jit::CodeArena&lt;impl Pages&gt;&gt;,\n 6    ) {\n 7        // [...]\n 8\n 9        // compute liveset\n10        fun.live_set_into(&amp;mut self.live_set);\n11\n12        // walk the IR once before lowering, after this its just a simple\n13        // lookup\n14        self.prealloc(fun);\n15\n16        // [...] iterate blocks\n17\n18            // [...] iterate instructions\n19\n20                // secret postprocessing of instructions which dst points to the stack\n21                if let Some(Location::Stack(slot)) =\n22                    Func::def_of(instruction).and_then(|dst| self.regalloc.location(dst))\n23                {\n24                    self.emit(Op::StoreSlot { slot, src: TMP });\n25                }\n26    }\n27}</code></pre>\n<h2 id=\"lowering-bin-ir-ops\">Lowering Bin ir ops</h2>\n<p>Bin is the baseline operator. The BinImm ops we see in our example (<code>ISub %v10, 1</code>) are optimisations (one less dispatch, less memory interactions) compiled in\nthe same way, just with an immediate rhs:</p>\n<p>RUST</p>\n<pre><code> 1impl&lt;&#39;cc, S: Allocator + Clone, A: Allocator + Clone&gt; Cc&lt;&#39;cc, S, A&gt; {\n 2    fn instr&lt;F: Allocator&gt;(&amp;mut self, owner: &amp;&#39;cc Func&lt;&#39;cc, F&gt;, i: &amp;&#39;cc ir::Instr&lt;&#39;cc&gt;) {\n 3        match i {\n 4            // [...] all the other IR instructions\n 5            ir::Instr::Bin {\n 6                op, dst, lhs, rhs, ..\n 7            } =&gt; {\n 8                // interacting with the register alloc prepass\n 9                let dst = self.def_register(dst.id);\n10                let lhs = self.ensure_register(*lhs);\n11                let rhs = self.ensure_register(*rhs);\n12\n13                macro_rules! emit_bins {\n14                    ($($name:ident),*) =&gt; {\n15                        match op {\n16                            $(\n17                                ir::BinOp::$name =&gt; {\n18                                    Op::$name {\n19                                        dst,\n20                                        lhs,\n21                                        rhs,\n22                                    }\n23                                },\n24                            )*\n25                        }\n26                    };\n27                }\n28\n29                self.emit(emit_bins! {\n30                    IAdd, ISub, IMul, IDiv, IMod, IAnd, ILt, IGt, IEq,\n31                    DAdd, DSub, DMul, DDiv, DLt, DGt,\n32                    BEq, SEq\n33                });\n34            }\n35            ir::Instr::BinImm {\n36                op, dst, lhs, imm, ..\n37            } =&gt; {\n38                let dst = self.def_register(dst.id);\n39                let lhs = self.ensure_register(*lhs);\n40                let imm = *imm;\n41\n42                macro_rules! emit_bin_imms {\n43                    ($($ir:ident =&gt; $op:ident),* $(,)?) =&gt; {\n44                        match op {\n45                            $(ir::BinOp::$ir =&gt; Op::$op { dst, lhs, imm },)*\n46                            _ =&gt; unreachable!(&quot;only integer immediate binops are represented as BinImm&quot;),\n47                        }\n48                    };\n49                }\n50\n51                self.emit(emit_bin_imms! {\n52                    IAdd =&gt; IAddI,\n53                    ISub =&gt; ISubI,\n54                    IMul =&gt; IMulI,\n55                    IDiv =&gt; IDivI,\n56                    IMod =&gt; IModI,\n57                    IAnd =&gt; IAndI,\n58                    IEq  =&gt; IEqI,\n59                    IGt  =&gt; IGtI,\n60                    ILt  =&gt; ILtI,\n61                });\n62            }\n63        }\n64    }\n65}</code></pre>\n<p>This is so clean and a nice use of rust macros, i love this, dont @me; lowering\nall binary and binary with immediate value operations in 57 lines is where its\nat.</p>\n<h2 id=\"ensuring-and-definining-a-register\">Ensuring and definining a register</h2>\n<p>Two helpers for making sure a requested virtual register is accessible to a\npoint where operations can be applied on it, the first one being ensure_register:</p>\n<p>RUST</p>\n<pre><code> 1/// Translate virtual register into vm register, abstracts spilling, restoring and register\n 2/// allocation in general away\n 3fn ensure_register(&amp;mut self, id: Id) -&gt; u8 {\n 4    match self.regalloc.location(id) {\n 5        Some(Location::Reg(r)) =&gt; return r.num(),\n 6        // requested value lives on the stack, we need to restore it and we use a temp\n 7        // register\n 8        Some(Location::Stack(slot)) =&gt; {\n 9            let dst = self.next_tmp();\n10            self.emit(Op::LoadSlot { dst, slot });\n11            dst\n12        }\n13        None =&gt; unreachable!(&quot;%v{} has no location&quot;, id.0),\n14    }\n15}\n16\n17fn next_tmp(&amp;self) -&gt; u8 {\n18    match self.buf.last() {\n19        Some(Op::LoadSlot { dst: SCRATCH, .. }) =&gt; TMP,\n20        _ =&gt; SCRATCH,\n21    }\n22}</code></pre>\n<p>This means if a value is requested and:</p>\n<ul><li>the prepass assigned it to a register, thats perfect and we can simply use it</li><li><p>or if its on the stack we have to ask the compiler state for a temporary</p><p>register and materialise the value into it</p></li></ul>\n<blockquote><p>Temporary registers in the virtual machine are defined as <code>SCRATCH</code> and <code>TMP</code>, respectively in the preamble of the virtual machines source code:</p>\n<p>RUST</p>\n<pre><code> 1pub const REGISTER_COUNT: usize = 32;\n 2const SCRATCH: u8 = REGISTER_COUNT as u8 - 1;\n 3const TMP: u8 = SCRATCH - 1;\n 4\n 5/// Every vm register but [`SCRATCH`] and [`TMP`], r0 last since xralloc2 hands\n 6/// out the lowest free one first, which also puts the caller-saved registers\n 7/// before the callee-saved ones.\n 8const POOL: [u8; TMP as usize] = {\n 9    let mut pool = [0; TMP as usize];\n10    let mut i = 0;\n11    while i &lt; TMP as usize {\n12        pool[i] = (TMP as usize - 1 - i) as u8;\n13        i += 1;\n14    }\n15    pool\n16};</code></pre></blockquote>\n<p>Thusfar ensure is simple to understand, the other helper is def_register, which\nmeans we, again, take the registers number, if it has one, otherwise we take\nTMP, which our previously introduced (and probably not noticed by anyone)\nsnipped at the end of the codeblock in <a href=\"#prep-and-register-allocation-prepass\">Prep and register allocation prepass</a>then “spills” into its slot on the\nstack with the respective bytecode instruction.</p>\n<p>RUST</p>\n<pre><code>1/// The register an op writes `id` into, [`TMP`] if `id` lives in a slot: the block loop stores\n2/// it there after the op.\n3fn def_register(&amp;self, id: Id) -&gt; u8 {\n4    match self.regalloc.location(id) {\n5        Some(Location::Reg(r)) =&gt; r.num(),\n6        Some(Location::Stack(_)) =&gt; TMP,\n7        None =&gt; unreachable!(&quot;%v{} has no location&quot;, id.0),\n8    }\n9}</code></pre>\n<h2 id=\"all-the-bytes-and-the-codes-together\">All the bytes and the codes together:</h2>\n<p>Swapping <code>-I</code> for <code>-D</code> (with <code>--no-jit</code>, otherwise we would get machinecode 🤓), results in the following\nvirtual machine registers assigned to the ssa values:</p>\n<p>ASM</p>\n<pre><code> 100000000 &lt;f&gt;:\n 2  0000:    ilt_imm r3, r1, #1        ; 4: n &lt; 1 { a + acc }\n 3  0001:    jmpf r3, 0004 &lt;f.bb_0004&gt;\n 4  0002:    iadd r0, r0, r2\n 5  0003:    ret\n 600000004 &lt;f.bb_0004&gt;:\n 7  0004:    isub_imm r3, r1, #1       ; 5: { f(a n-1 acc*n) }\n 8  0005:    imul r2, r2, r1\n 9  0006:    mov r1, r3\n10  0007:    tail 0000 &lt;f&gt;</code></pre>\n<h2 id=\"jit-o\">JIT :O</h2>\n<p>For the crazy hackermans, here is the same example with the jit on, jit and bc\nshare IR, liveness analysis, register allocation and standard libary, aint that\nfun?</p>\n<p>ASM</p>\n<pre><code> 10000000000000000 &lt;jit_f&gt;:\n 2   0:   48 81 fa 01 00 00 00    cmp    $0x1,%rdx\n 3   7:   49 c7 c0 00 00 00 00    mov    $0x0,%r8\n 4   e:   41 0f 9c c0             setl   %r8b\n 5  12:   4d 85 c0                test   %r8,%r8\n 6  15:   0f 84 0b 00 00 00       je     26 &lt;jit_f+0x26&gt;\n 7  1b:   48 01 ce                add    %rcx,%rsi\n 8  1e:   48 89 f0                mov    %rsi,%rax\n 9  21:   c3                      ret\n10  22:   cc                      int3\n11  23:   cc                      int3\n12  24:   cc                      int3\n13  25:   cc                      int3\n14  26:   49 89 d0                mov    %rdx,%r8\n15  29:   49 81 e8 01 00 00 00    sub    $0x1,%r8\n16  30:   49 89 c9                mov    %rcx,%r9\n17  33:   4c 0f af ca             imul   %rdx,%r9\n18  37:   4c 89 c2                mov    %r8,%rdx\n19  3a:   4c 89 c9                mov    %r9,%rcx\n20  3d:   e9 be ff ff ff          jmp    0 &lt;jit_f&gt;\n21  42:   c3                      ret</code></pre>\n<blockquote><p>Dont be mean to the x86 output, i know this could be shorter, the compare and\njmp could be a single instr and there is a lot of dead code and long\nencodings, but this is my first jit and im glad it works at all :)</p></blockquote>\n<h1 id=\"future-work\">Future work</h1>\n<p>The attentive reader may have figured out how i have described the inputs and\nouputs of the register allocator, respectively the liveset (and the pool of\nregs) and assignment of virtual to physical register, but have not actually\nshown or introduced the register allocator itself, or the results of the IR\ndesign which forces the regalloc to treat all block transitions (jumps,\nentries, returns) as edge moves and has to do extra work to resolve these.</p>\n<p>If my motivation holds up i will write a follow up article about these topics,\nbut right now i am still in the process of “perfecting” the interactions\nbetween my ir, my regalloc and my backends, so maybe stay tuned? I have an rss\nfeed if anyone is actually at the end of the abyss im screaming my incohesive\nblabbering into.</p>\n<hr />\n<ol><li>Thats the [Z|Y]JIT guy btw, absolutely insane articles, everyone interested in anything compiler related should have read at least twice <a href=\"#fnref:1\">↩︎</a></li><li><p>Optimised here means: inline immediates for comparisons and</p><p> arithmetics, tailcalls and removed blocks just used for indirect returns <a href=\"#fnref:2\">↩︎</a></p></li></ol>","headings":[{"level":1,"text":"An ode to livelyness analysis; SSA to registers","id":"an-ode-to-livelyness-analysis-ssa-to-registers"},{"level":1,"text":"A garden(ing) example","id":"a-garden-ing-example"},{"level":1,"text":"PUrple garden IR structure and notation","id":"purple-garden-ir-structure-and-notation"},{"level":1,"text":"Virtual registers / Values and their lifetimes","id":"virtual-registers-values-and-their-lifetimes"},{"level":1,"text":"A short but sweet implementation:","id":"a-short-but-sweet-implementation"},{"level":2,"text":"Observing","id":"observing"},{"level":2,"text":"Helpers to help with defs and usages:","id":"helpers-to-help-with-defs-and-usages"},{"level":3,"text":"Extracting definitions","id":"extracting-definitions"},{"level":3,"text":"Calling f for each usage of value in an instruction","id":"calling-f-for-each-usage-of-value-in-an-instruction"},{"level":3,"text":"Calling f for each usage of value in a terminator","id":"calling-f-for-each-usage-of-value-in-a-terminator"},{"level":2,"text":"Fully rusted together:","id":"fully-rusted-together"},{"level":1,"text":"Wiring liveset analysis into register allocation for the bytecode backend","id":"wiring-liveset-analysis-into-register-allocation-for-the-bytecod"},{"level":2,"text":"Prep and register allocation prepass","id":"prep-and-register-allocation-prepass"},{"level":2,"text":"Lowering Bin ir ops","id":"lowering-bin-ir-ops"},{"level":2,"text":"Ensuring and definining a register","id":"ensuring-and-definining-a-register"},{"level":2,"text":"All the bytes and the codes together:","id":"all-the-bytes-and-the-codes-together"},{"level":2,"text":"JIT :O","id":"jit-o"},{"level":1,"text":"Future work","id":"future-work"}]}}