🥮 mooncakes.io
    Sign in

    machv_regalloc

    MachV adapter for the reusable register allocator

    compiler
    register-allocation
    machv
    jit
    Download zip
    Author
    Version
    0.2.1
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    191

    #machv_regalloc

    MachV adapter for the reusable register allocator.

    machv_regalloc bridges Milky2018/machv virtual-register functions to the target-independent Milky2018/regalloc algorithm. It projects MachV into the generic allocation model, applies allocation output, and keeps edge-copy and layout behavior compatible with MachV emission.

    #Packages

    • Milky2018/machv_regalloc: projection, allocation entry points, application, validation, spill handling, and output construction.
    • Milky2018/machv_regalloc/layout: block layout utilities for MachV functions.

    #When to use it

    Use machv_regalloc when your code is already in MachV and you want to reuse the target-independent allocator. This package keeps MachV as the machine IR, invokes the allocator, and returns either a rewritten function or a Cranelift-style allocation Output that the emitter can consume without mutating the original virtual-register instructions.

    #Example: allocate a MachV function

    Embedders provide their calling-convention data explicitly; MachV and machv_regalloc do not know Wasmoon-specific runtime layouts.

    ///|
    fn example_abi() -> @abi.EmbeddingABI {
      let call_conv : @abi.CallConventionLayout = {
        context_arg: { index: 27, class: Int },
        user_arg_gprs: [{ index: 0, class: Int }, { index: 1, class: Int }],
        arg_fprs: [{ index: 0, class: Float64 }, { index: 1, class: Float64 }],
        ret_gprs: [{ index: 0, class: Int }],
        ret_fprs: [{ index: 0, class: Float64 }],
      }
      EmbeddingABI(call_conv, reserve_context_role=false)
    }

    ///|
    test "allocate a canonical MachV copy" {
      let builder = @machv.FunctionBuilder::FunctionBuilder("copy")
      let src = builder.add_param(Int)
      let dst = builder.new_vreg(Int)
      builder.append(Move, uses=[Virtual(src)], defs=[{ reg: Virtual(dst) }])
      |> ignore
      builder.terminate(Return([Virtual(dst)]))
      let allocated = allocate_registers_backtracking_with_isa(
        builder.finish(),
        AArch64,
        embedding_abi=Some(example_abi()),
      )
      inspect(allocated.blocks.length(), content="1")
      inspect(allocated.blocks[0].terminator is Some(Return(_)), content="true")
    }

    #Example: consume Cranelift-style output

    The output API records per-operand locations and inserted edits. This is the preferred path for emitters that materialize moves while encoding instructions.

    ///|
    test "read operand locations from regalloc output" {
      let builder = @machv.FunctionBuilder::FunctionBuilder("rewrite")
      let src = builder.add_param(Int)
      let dst = builder.new_vreg(Int)
      builder.append(Move, uses=[Virtual(src)], defs=[{ reg: Virtual(dst) }])
      |> ignore
      builder.terminate(Return([Virtual(dst)]))
      let (_func, output) = allocate_registers_backtracking_output_with_isa(
        builder.finish(),
        AArch64,
        embedding_abi=Some(example_abi()),
      )
      inspect(output.get_num_spillslots(), content="0")
      inspect(output.inst_def_loc(0, 0, false, 0) is Reg(_), content="true")
      inspect(output.inst_use_loc(0, 0, false, 0) is Reg(_), content="true")
    }

    #Boundary

    This module may depend on MachV and regalloc, but should not depend on product runtime packages or native embedding details.

    RegallocAlgorithm

    source

    Register allocation algorithm policy.

    • Backtracking: Ion-style backtracking + eviction/splitting (better codegen).
    • SinglePass: no eviction/backtracking, spills earlier (faster compile).

    SpillSlot

    source
    type SpillSlot = Int

    A spill slot index (8-byte slot).

    AArch64StackFrame

    source
    type AArch64StackFrame

    AArch64-specific stack frame configuration

    AArch64StackFrame::AArch64StackFrame

    source
    fn AArch64StackFrame::AArch64StackFrame() -> AArch64StackFrame

    AArch64StackFrame::alloc_spill

    source

    Allocate a spill slot

    AArch64StackFrame::finalize

    source
    fn AArch64StackFrame::finalize(self : AArch64StackFrame) -> Unit

    Finalize the frame

    AArch64StackFrame::gen_epilogue

    source

    Generate epilogue instructions

    AArch64StackFrame::gen_prologue

    source

    Generate prologue instructions

    AArch64StackFrame::save_callee_reg

    source
    fn AArch64StackFrame::save_callee_reg(self : AArch64StackFrame, preg : 
    PReg    ) -> Int

    Add a callee-saved register

    AArch64StackFrame::setup

    source
    fn AArch64StackFrame::setup(self : AArch64StackFrame) -> Unit

    Setup the frame with FP and LR saves

    AArch64StackFrame::size

    source
    fn AArch64StackFrame::size(self : AArch64StackFrame) -> Int

    Get frame size

    AllocStats

    source
    type AllocStats

    Allocation statistics for comparison
    impl Show for AllocStats

    Allocation

    source
    pub enum Allocation {
      Reg(
    PReg    )
      Spill(Int)
      Unallocated
    }

    Allocation result for a LiveRange or Bundle
    impl Show for Allocation

    Bundle

    source
    type Bundle

    A Bundle groups related LiveRanges that should ideally be allocated to the same physical register. Bundles are formed by merging LiveRanges connected by Move instructions, block arguments, or tied operands.

    Bundle::Bundle

    source
    fn Bundle::Bundle(id : Int, reg_class : 
    RegClass    ) -> Bundle

    Bundle::contains_range

    source
    fn Bundle::contains_range(self : Bundle, range_id : Int) -> Bool

    Check if this bundle contains a specific LiveRange

    Bundle::crosses_call

    source
    fn Bundle::crosses_call(self : Bundle, ranges : LiveRangeSet) -> Bool

    Check if any range in this bundle crosses a function call

    Bundle::crosses_foreign_call

    source
    fn Bundle::crosses_foreign_call(self : Bundle, ranges : LiveRangeSet) -> Bool

    Check if any range in this bundle crosses a foreign/helper call

    Bundle::crosses_internal_call

    source
    fn Bundle::crosses_internal_call(self : Bundle, ranges : LiveRangeSet) -> Bool

    Check if any range in this bundle crosses an internal call

    Bundle::get_fixed_reg

    source
    fn Bundle::get_fixed_reg(self : Bundle, ranges : LiveRangeSet) -> 
    PReg    ?

    Get the fixed register if all ranges in bundle require same fixed reg

    Bundle::has_fixed_constraint

    source
    fn Bundle::has_fixed_constraint(self : Bundle, ranges : LiveRangeSet) -> Bool

    Bundle::overlaps

    source
    fn Bundle::overlaps(self : Bundle, other : Bundle, ranges : LiveRangeSet) -> Bool

    Check if this bundle overlaps with another bundle

    Bundle::to_string

    source
    fn Bundle::to_string(self : Bundle, _ranges : LiveRangeSet) -> String

    Bundle::total_length

    source
    fn Bundle::total_length(self : Bundle, ranges : LiveRangeSet) -> Int

    Get total length of all ranges in this bundle

    BundleSet

    source
    type BundleSet

    Collection of Bundles

    BundleSet::BundleSet

    source
    fn BundleSet::BundleSet() -> BundleSet

    BundleSet::get

    source
    fn BundleSet::get(self : BundleSet, id : Int) -> Bundle

    Get bundle by ID

    BundleSet::length

    source
    fn BundleSet::length(self : BundleSet) -> Int

    Get number of bundles

    Edit

    source
    pub(all) enum Edit {
      Move(Loc, Loc, 
    RegClass    )
    }

    An edit produced by regalloc to be inserted at a program point.

    Equivalent to regalloc2::Edit::Move in Cranelift: move between two locations.
    impl Show for Edit

    InstEdits

    source
    type InstEdits

    Edits to insert before/after an instruction.

    LiveInterval

    source
    pub struct LiveInterval {
      vreg : 
    VReg
      start : ProgPoint
      end : ProgPoint
      uses : Array[ProgPoint]
      hint : 
    PReg    ?
      assigned : 
    PReg    ?
      spill_slot : Int?
      crosses_call : Bool
      crosses_foreign_call : Bool
    }

    A live interval - the range where a virtual register is live

    LiveRange

    source
    type LiveRange

    A LiveRange represents the liveness of a single virtual register with precise span information and use constraints.
    impl Show for LiveRange

    LiveRange::LiveRange

    source
    fn LiveRange::LiveRange(id : Int, vreg : 
    VReg    ) -> LiveRange

    LiveRange::end

    source
    fn LiveRange::end(self : LiveRange, block_order : FixedArray[Int]) -> ProgPoint?

    Get the end point (latest point in all ranges)

    LiveRange::get_fixed_reg

    source
    fn LiveRange::get_fixed_reg(self : LiveRange) -> 
    PReg    ?

    Get the fixed register constraint if all uses require the same fixed reg

    LiveRange::has_fixed_constraint

    source
    fn LiveRange::has_fixed_constraint(self : LiveRange) -> Bool

    Check if this LiveRange has any fixed register constraint

    LiveRange::overlaps

    source
    fn LiveRange::overlaps(self : LiveRange, other : LiveRange, block_order : FixedArray[Int]) -> Bool

    Check if this LiveRange overlaps with another

    LiveRange::start

    source
    fn LiveRange::start(self : LiveRange, block_order : FixedArray[Int]) -> ProgPoint?

    Get the start point (earliest point in all ranges)

    LiveRange::total_length

    source
    fn LiveRange::total_length(self : LiveRange) -> Int

    Compute total length of all ranges (in instruction count)

    LiveRangeSet

    source
    type LiveRangeSet

    Collection of LiveRanges built from liveness analysis

    LiveRangeSet::get

    source
    fn LiveRangeSet::get(self : LiveRangeSet, idx : Int) -> LiveRange

    Get LiveRange by index

    LiveRangeSet::get_by_vreg

    source
    fn LiveRangeSet::get_by_vreg(self : LiveRangeSet, vreg_id : Int) -> LiveRange?

    Get LiveRange by vreg id

    LiveRangeSet::length

    source
    fn LiveRangeSet::length(self : LiveRangeSet) -> Int

    Get number of ranges

    LivenessResult

    source
    pub struct LivenessResult {
      intervals : Map[Int, LiveInterval]
      use_def : Map[Int, UseDefInfo]
      use_def_dense : Array[UseDefInfo?]
      live_in : Array[
    Set    [Int]]
      live_out : Array[
    Set    [Int]]
      live_in_dense : Array[Array[Int]]?
      live_out_dense : Array[Array[Int]]?
      block_order : FixedArray[Int]
      call_points : Array[(ProgPoint, 
    CallClobberClass    )]
    }

    Liveness analysis result

    Loc

    source
    pub(all) enum Loc {
      Reg(
    PReg    )
      Spill(Int)
    }

    A location for a value at a program point: either in a register or in a spill slot.
    impl Show for Loc

    OperandConstraint

    source
    pub enum OperandConstraint {
      AnyReg
      FixedReg(
    PReg    )
    }

    Operand constraint for a use position

    Output

    source
    pub struct Output {
      param_locs : Array[Loc]
      allocs : Array[Loc]
      operand_ranges : Array[(Int, Int, Bool, Int, Int, Int)]
      inst_operand_range_index : Array[Array[Int]]
      term_operand_range_index : Array[Int]
      edits : Array[((Int, Int, ProgPos), Edit)]
      edits_before_dense : Array[Array[Array[Edit]]]
      edits_after_dense : Array[Array[Array[Edit]]]
      used_int_pregs_any : Array[Bool]
      used_fp_pregs_any : Array[Bool]
      num_spillslots : Int
    }

    Regalloc output.

    • allocs is a flat array of operand allocations, aligned with operand_ranges.
    • edits is a list of edits keyed by a program point (block/inst/pos).
    • num_spillslots is used by stack-frame layout.

    Output::Output

    source
    fn Output::Output() -> Output

    Output::begin_inst_allocs

    source
    fn Output::begin_inst_allocs(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_count : Int, use_count : Int) -> (Int, Int)

    Start recording operand allocations for one instruction/terminator. Returns (start, total) where start is the first index in allocs.

    Output::edits_at

    source
    fn Output::edits_at(self : Output, block_id : Int, inst_idx : Int, pos : ProgPos) -> Array[Edit]?

    Output::end_inst_allocs

    source
    fn Output::end_inst_allocs(self : Output, start : Int, total : Int) -> Unit

    Output::finalize_edits

    source
    fn Output::finalize_edits(self : Output) -> Unit

    Output::get_num_params

    source
    fn Output::get_num_params(self : Output) -> Int

    Output::get_num_spillslots

    source
    fn Output::get_num_spillslots(self : Output) -> Int

    Output::get_param_loc

    source
    fn Output::get_param_loc(self : Output, idx : Int) -> Loc

    Output::inst_def_loc

    source
    fn Output::inst_def_loc(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_idx : Int) -> Loc

    Output::inst_use_loc

    source
    fn Output::inst_use_loc(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, use_idx : Int) -> Loc

    Output::iter_allocs

    source
    fn Output::iter_allocs(self : Output) -> Array[Loc]

    Output::iter_edits

    source
    fn Output::iter_edits(self : Output) -> Array[((Int, Int, ProgPos), Edit)]

    Output::push_edit

    source
    fn Output::push_edit(self : Output, block_id : Int, inst_idx : Int, pos : ProgPos, edit : Edit) -> Unit

    Output::push_inst_alloc_loc

    source
    fn Output::push_inst_alloc_loc(self : Output, loc : Loc) -> Unit

    Output::push_inst_allocs

    source
    fn Output::push_inst_allocs(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_count : Int, use_count : Int, locs : Array[Loc]) -> Unit

    Record operand allocations for one instruction/terminator. locs must have length def_count + use_count, in that order.

    Output::push_param_loc

    source
    fn Output::push_param_loc(self : Output, loc : Loc) -> Unit

    Output::rebuild_edits_index

    source
    fn Output::rebuild_edits_index(self : Output) -> Unit

    Output::sort_edits

    source
    fn Output::sort_edits(self : Output) -> Unit

    Output::spill_reload_stats

    source
    fn Output::spill_reload_stats(self : Output) -> (Int, Int, Int, Int)

    Return stack-traffic counts inferred from regalloc edits: (spills, reloads, reg_moves, spill_to_spill).

    Output::summary

    source
    fn Output::summary(self : Output) -> String

    A compact human-readable summary for debugging (used by the CLI explore command).

    Output::uses_preg_index_any

    source
    fn Output::uses_preg_index_any(self : Output, preg_idx : Int, is_int_class : Bool) -> Bool

    Output::validate_for_isa

    source
    fn Output::validate_for_isa(self : Output, isa : 
    ISA    ) -> Unit

    Validate that the regalloc output only uses legal physical registers for the selected ISA.

    This is a fail-fast guard: silent truncation in x86 encoders can clobber rsp/rbp if an out-of-range preg leaks into emission (e.g. x20 -> rsp).

    ProgPoint

    source
    pub struct ProgPoint {
      block : Int
      inst : Int
      pos : ProgPos
    } derive(Eq, Hash, 
    Debug    )

    A program point - identifies a position in the MachV function Using #valtype for stack allocation - this struct is created/compared frequently
    impl Show for ProgPoint

    ProgPointRange

    source
    type ProgPointRange

    A contiguous program point range (start inclusive, end exclusive)

    ProgPointRange::contains

    source
    fn ProgPointRange::contains(self : ProgPointRange, point : ProgPoint, block_order : FixedArray[Int]) -> Bool

    Check if a point is within this range

    ProgPos

    source
    pub(all) enum ProgPos {
      Before
      After
    } derive(Eq, Hash, 
    Debug    )

    Position relative to an instruction

    RegAllocResult

    source
    pub struct RegAllocResult {
      assignments : Map[Int, 
    PReg    ]
      spill_slots : Map[Int, Int]
      num_spill_slots : Int
      inst_edits : Array[(Int, Int, InstEdits)]
    }

    Register allocation result

    RegMove

    source
    type RegMove

    A move between two locations (register or spill slot).
    impl Show for RegMove

    SpillBundle

    source
    type SpillBundle

    A SpillBundle tracks a shared spill slot for split bundles. When a bundle is split, both parts share the same SpillBundle so they use the same stack slot.

    SpillBundle::SpillBundle

    source
    fn SpillBundle::SpillBundle(id : Int, slot : Int) -> SpillBundle

    StackFrame

    source
    type StackFrame

    Stack frame layout for a function
    impl Show for StackFrame

    StackFrame::StackFrame

    source
    fn StackFrame::StackFrame(frame_align : Int) -> StackFrame

    StackFrame::add_callee_saved

    source
    fn StackFrame::add_callee_saved(self : StackFrame, preg : 
    PReg    ) -> Int

    Record a callee-saved register that needs to be saved

    StackFrame::alloc_local

    source
    fn StackFrame::alloc_local(self : StackFrame, local_idx : Int, size : Int, align : Int) -> Int

    Allocate a slot for a local variable

    StackFrame::alloc_outgoing_arg

    source
    fn StackFrame::alloc_outgoing_arg(self : StackFrame, arg_idx : Int, size : Int, align : Int) -> Int

    Allocate a slot for an outgoing argument

    StackFrame::alloc_spill_slot

    source
    fn StackFrame::alloc_spill_slot(self : StackFrame, vreg : 
    VReg    , size : Int, align : Int) -> Int

    Allocate a spill slot for a virtual register

    StackFrame::finalize

    source
    fn StackFrame::finalize(self : StackFrame) -> Unit

    Finalize the frame layout and compute total size

    StackFrame::get_callee_saved

    source
    fn StackFrame::get_callee_saved(self : StackFrame) -> Array[
    PReg    ]

    Get all callee-saved registers that were used

    StackFrame::print

    source
    fn StackFrame::print(self : StackFrame) -> String

    Print the frame layout

    StackFrame::size

    source
    fn StackFrame::size(self : StackFrame) -> Int

    Get the total frame size

    StackSlot

    source
    type StackSlot

    A stack slot - a location on the stack
    impl Show for StackSlot

    StackSlotKind

    source
    pub enum StackSlotKind {
      Spill(
    VReg    )
      Local(Int)
      OutgoingArg(Int)
      CalleeSaved(
    PReg    )
    }

    Kind of stack slot

    UseDefInfo

    source
    type UseDefInfo

    Use-def information for a single vreg

    UseKind

    source
    type UseKind

    Kind of use at a program point Note: For tied operands (same reg as both def and use), add a DefUse variant when Inst supports tied operand representation.
    impl Show for UseKind

    UsePosition

    source
    type UsePosition

    A use position within a LiveRange
    impl Show for UsePosition

    allocate_registers_backtracking

    source

    Allocate MachV virtual registers through the production backtracking path.

    machv_regalloc builds MachV liveness, register pools, and output edits; reusable allocation-loop, probe, eviction, split, and spill policies live in regalloc.

    allocate_registers_backtracking_output

    source
    fn allocate_registers_backtracking_output(func : 
    Function    , embedding_abi? : 
    EmbeddingABI    ?) -> (
    Function    , Output)

    Allocate MachV virtual registers and return a Cranelift-style regalloc Output.

    The returned @machv.Function is not rewritten to physical registers; the emitter consumes the returned Output to materialize edits and operand allocations on the fly.

    allocate_registers_backtracking_output_with_isa

    source

    Allocate MachV virtual registers and return Output using a specific ISA policy implementation.

    allocate_registers_backtracking_with_isa

    source

    Allocate registers using a specific ISA policy implementation.

    apply_allocation

    source

    Apply register allocation results to a MachV function Handles spilled registers by inserting StackLoad/StackStore instructions

    build_bundles_with_merging

    source
    fn build_bundles_with_merging(func : 
    Function    , ranges : LiveRangeSet) -> BundleSet

    Build bundles with merging from Move instructions and block arguments

    build_initial_bundles

    source
    fn build_initial_bundles(ranges : LiveRangeSet) -> BundleSet

    Build initial bundles from LiveRanges Each LiveRange starts in its own bundle

    build_live_ranges

    source
    fn build_live_ranges(func : 
    Function    , liveness : LivenessResult) -> LiveRangeSet

    Build LiveRanges from liveness analysis result This is Phase 2 of the Ion allocator

    build_stack_layout_aarch64

    source
    fn build_stack_layout_aarch64(alloc : RegAllocResult, func : 
    Function    ) -> AArch64StackFrame

    Build stack layout from register allocation result

    compute_liveness

    source
    fn compute_liveness(func : 
    Function    ) -> LivenessResult

    Compute full liveness information including interval maps.

    compute_liveness_for_regalloc

    source
    fn compute_liveness_for_regalloc(func : 
    Function    ) -> LivenessResult

    Compute liveness for regalloc hot path (no interval map construction).

    compute_loop_depths

    source
    fn compute_loop_depths(func : 
    Function    ) -> Array[Int]

    Pre-compute per-block approximate loop depth, aligned with regalloc2's CFG heuristic (cfg.rs::approx_loop_depth): count backedge entries/exits over linear block order and maintain a small nesting stack.

    compute_spill_weight

    source
    fn compute_spill_weight(bundle : Bundle, ranges : LiveRangeSet, loop_depths : Array[Int]) -> Int

    Compute spill weight for a bundle using pre-computed loop depths Higher weight = more important to keep in register

    debug_liveness

    source
    fn debug_liveness(liveness : LivenessResult) -> String

    Debug: print liveness info

    eliminate_dead_code

    source

    Eliminate dead code from a MachV function Removes instructions that define vregs which are never used

    get_alloc_stats

    source

    Get allocation statistics

    process_constraints

    source
    fn process_constraints(func : 
    Function    , alloc : RegAllocResult) -> Unit

    Process operand constraints and generate RegMove edits Design: constraints are processed after allocation and moves are inserted when the allocated register doesn't match the constraint

    rematerialize_cross_block_constants

    source
    fn rematerialize_cross_block_constants(func : 
    Function    ) -> 
    Function

    Rematerialize cross-block cheap defs:
    • Detect vregs defined by rematerializable opcodes.
    • If such a vreg is used in a different block than its def, clone the defining opcode into each such use block and rewrite uses to a block-local vreg.

    This is intentionally conservative and mirrors Cranelift’s “clone remat values into the block where used” strategy.

    rematerialize_long_distance_constants

    source
    fn rematerialize_long_distance_constants(func : 
    Function    ) -> 
    Function

    Clone long-distance rematerializable defs within the same block.

    This mirrors Cranelift's remat intent for cheap constants: shorten very long live ranges by re-defining constants near far-away uses.

    verify_allocation

    source

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io