🥮 mooncakes.io
    Sign in

    regalloc

    Target-independent register allocation algorithm

    compiler
    register-allocation
    algorithm
    Download zip
    Author
    Version
    0.3.0
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    293

    No dependencies

    #regalloc

    regalloc is a target-independent register allocator for machine IRs. It reads a function through a narrow, read-only FunctionView and returns an AllocationPlan; it does not copy the client's instruction or CFG objects.

    The plan contains:

    • a stable home for every value;
    • a location for every instruction operand;
    • before/after edits for reloads, spills, fixed registers, and tied operands;
    • edge edits for block arguments;
    • reusable spill-slot layouts.

    Operand constraints and placement preferences are separate contracts. A fixed register is a hard correctness requirement and may require an insertion edit. A physical-register preference only orders otherwise legal allocation choices; it is ignored rather than causing an extra spill, split, move, or failure when the preferred register cannot hold the live range.

    #Allocation strategies

    Backtracking is the default production strategy. It builds allocation bundles from compatible SSA edge affinities, allocates each bundle atomically, splits bundles when pressure requires it, evicts cheaper residents, and reuses compatible non-overlapping spill slots. Fixed-register, soft-register, and cross-fragment hints all feed this one production implementation.

    SinglePass is an explicit low-compile-latency strategy. It uses the same fragmented plan and verification contract but does not evict an existing fragment to make room for a more valuable one, so it may spill earlier. Callers should select it only when compile latency matters more than generated code quality.

    ///|
    test "select the low-latency allocator explicitly" {
      let config = RegallocConfig::RegallocConfig(strategy=SinglePass)
      inspect(config.strategy(), content="SinglePass")
    }

    #Integrating a machine IR

    Implement FunctionView over the machine IR and provide a MachineEnv with allocatable and scratch registers. Block arguments passed to CFG methods are dense layout indices; block_id_at maps them back to the machine IR's stable block id for edge edits.

    Scratch registers have two distinct roles. scratch_regs are always available to resolve allocator edits such as spill reloads and parallel moves. By default they may also hold instruction operands when all allocatable registers are occupied. A target whose emitter reserves those registers for instruction-local expansion must call with_operand_scratch_regs([]) (or provide the safe subset), while leaving the edit scratch set intact.

    The view also distinguishes function entry values from block parameters and defines spill size, alignment, and slot-sharing compatibility. Operand timing uses Early and Late points, allowing an early input and late output to share a register safely across one instruction.

    Call allocate_function(view, environment, config?). With verification enabled (the default), the allocator symbolically checks operand values, clobbers, instruction edits, CFG joins, and block-argument transfers before returning the plan.

    Milky2018/machv_regalloc is the reference adapter. AArch64 and x64 both use this path before target emission.

    #Production integration

    Wasmoon's AArch64 and x64 JIT pipelines lower semantic MachV to target-owned VCode, expose that VCode directly through FunctionView, and explicitly select Backtracking. The adapter materializes the returned plan into Target VCode's separate Allocation side tables. The aggregate target pipeline verifies selected VCode before allocation and independently verifies the materialized VCode allocation afterward, without repeating the generic plan verifier's whole-function analysis. Production compilation does not fall back to SinglePass.

    The production integration is complete. CI validates allocation correctness on both native targets; retired allocators and backends are not rebuilt as performance or code-size acceptance baselines.

    #Expert packages

    • Milky2018/regalloc/planning provides standalone CFG, spill-slot, edit, and frame-planning utilities. Allocation queues, bundle merging, eviction, and splitting remain private to the root production allocator so there is only one maintained allocation policy.

    FunctionView

    source
    pub(open) trait FunctionView {
      fn value_count(Self) -> Int
      fn value_class(Self, Int) -> RegClass
      fn value_spill_size(Self, Int) -> Int
      fn value_spill_alignment(Self, Int) -> Int
      fn values_share_spill_slot(Self, Int, Int) -> Bool
      fn entry_values(Self) -> Array[VirtualReg]
      fn block_count(Self) -> Int
      fn block_id_at(Self, Int) -> Int
      fn block_parameters(Self, Int) -> Array[VirtualReg]
      fn block_instructions(Self, Int) -> Array[Int]
      fn block_successors(Self, Int) -> Array[Int]
      fn edge_arguments(Self, Int, Int) -> Array[VirtualReg]
      fn instruction_operands(Self, Int) -> Array[Operand]
      fn instruction_clobbers(Self, Int) -> Array[PhysicalReg]
    }

    Read-only machine-function input consumed by register allocation.

    Values and instructions have stable dense ids. Blocks passed to CFG methods are dense layout indices; block_id_at maps them to the embedding's stable block id for diagnostics and edge edits. The allocator may retain derived liveness data, but does not retain the view.

    VerifyError

    source
    pub suberror VerifyError {
      Unassigned(vreg~ : VirtualReg)
      FixedConstraintViolation(vreg~ : VirtualReg, required~ : PhysicalReg, actual~ : Location)
      InvalidPreference(vreg~ : VirtualReg, preferred~ : PhysicalReg)
      IncorrectValue(vreg~ : VirtualReg, location~ : Location)
      ScratchRegisterUnavailable(message~ : String)
      InvalidPlan(message~ : String)
    } derive(
    Debug    )

    AllocationEdit

    source
    pub(all) struct AllocationEdit {
      value : VirtualReg
      from : Location
      to : Location
      position : EditPosition
    } derive(Eq, 
    Debug    )

    AllocationPlan

    source
    pub struct AllocationPlan {
      // private fields
    } derive(
    Debug    )

    AllocationPlan::edits

    source

    AllocationPlan::operand_assignments

    source
    fn AllocationPlan::operand_assignments(self : AllocationPlan) -> Array[OperandAssignment]

    AllocationPlan::operand_location

    source
    fn AllocationPlan::operand_location(self : AllocationPlan, instruction : Int, operand : Int) -> Location?

    AllocationPlan::spill_count

    source
    fn AllocationPlan::spill_count(self : AllocationPlan) -> Int

    AllocationPlan::spill_slot

    source
    fn AllocationPlan::spill_slot(self : AllocationPlan, index : Int) -> SpillSlotSpec?

    AllocationPlan::value_location

    source
    fn AllocationPlan::value_location(self : AllocationPlan, value : Int) -> Location?

    AllocatorStrategy

    source
    pub(all) enum AllocatorStrategy {
      Backtracking
      SinglePass
    } derive(Eq, 
    Debug    )

    DenseCfgEdges

    source
    type DenseCfgEdges derive(
    Debug    )

    DenseLiveSets

    source
    type DenseLiveSets derive(
    Debug    )

    EditPosition

    source
    pub(all) enum EditPosition {
      Before(Int)
      After(Int)
      Edge(source_block~ : Int, successor_index~ : Int)
    } derive(Eq, 
    Debug    )

    LiveRange

    source
    type LiveRange derive(
    Debug    )

    LiveRange::LiveRange

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

    LiveRange::add_range

    source
    fn LiveRange::add_range(self : LiveRange, range : ProgramRange) -> Unit

    LiveRange::add_use

    source
    fn LiveRange::add_use(self : LiveRange, use_pos : UsePosition) -> Unit

    LiveRange::end

    source
    fn LiveRange::end(self : LiveRange) -> ProgramPoint?

    LiveRange::get_fixed_reg

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

    LiveRange::has_fixed_constraint

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

    LiveRange::has_tie_at

    source
    fn LiveRange::has_tie_at(self : LiveRange, other : LiveRange, point : ProgramPoint) -> Bool

    LiveRange::id

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

    LiveRange::is_live_across

    source
    fn LiveRange::is_live_across(self : LiveRange, point : ProgramPoint, block_order : Array[Int]) -> Bool

    LiveRange::overlap_allowed_by_tie

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

    LiveRange::overlaps

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

    LiveRange::range_at

    source
    fn LiveRange::range_at(self : LiveRange, index : Int) -> ProgramRange?

    LiveRange::range_count

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

    LiveRange::start

    source
    fn LiveRange::start(self : LiveRange) -> ProgramPoint?

    LiveRange::total_length

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

    LiveRange::touch

    source
    fn LiveRange::touch(self : LiveRange, point : ProgramPoint) -> Unit

    LiveRange::touch_with_order

    source
    fn LiveRange::touch_with_order(self : LiveRange, point : ProgramPoint, block_order : Array[Int]) -> Unit

    LiveRange::use_at

    source
    fn LiveRange::use_at(self : LiveRange, index : Int) -> UsePosition?

    LiveRange::use_count

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

    LiveRange::vreg

    source
    fn LiveRange::vreg(self : LiveRange) -> VirtualReg

    LiveRangeSet

    source
    type LiveRangeSet derive(
    Debug    )

    LiveRangeSet::LiveRangeSet

    source
    fn LiveRangeSet::LiveRangeSet(block_order : Array[Int]) -> LiveRangeSet

    LiveRangeSet::add_range

    source
    fn LiveRangeSet::add_range(self : LiveRangeSet, range : LiveRange) -> Unit

    LiveRangeSet::block_order

    source
    fn LiveRangeSet::block_order(self : LiveRangeSet) -> Array[Int]

    LiveRangeSet::block_order_at

    source
    fn LiveRangeSet::block_order_at(self : LiveRangeSet, index : Int) -> Int?

    LiveRangeSet::block_order_count

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

    LiveRangeSet::get

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

    LiveRangeSet::get_by_vreg

    source
    fn LiveRangeSet::get_by_vreg(self : LiveRangeSet, vreg : VirtualReg) -> LiveRange?

    LiveRangeSet::length

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

    LiveSetUseDef

    source
    type LiveSetUseDef derive(
    Debug    )

    Location

    source
    pub(all) enum Location {
      Reg(PhysicalReg)
      Spill(Int)
    } derive(Eq, 
    Debug    )

    MachineEnv

    source
    pub struct MachineEnv {
      allocatable_regs : Array[PhysicalReg]
      scratch_regs : Array[PhysicalReg]
      operand_scratch_regs : Array[PhysicalReg]
    }

    Physical-register policy supplied by the embedding target.

    scratch_regs resolve allocator-inserted edits. The operand scratch subset may additionally hold instruction operands; targets may restrict that subset when their emitter reserves scratch registers for local expansion.

    MachineEnv::allocatable_regs

    source
    fn MachineEnv::allocatable_regs(self : MachineEnv) -> Array[PhysicalReg]

    MachineEnv::new

    source
    fn MachineEnv::new(allocatable_regs : Array[PhysicalReg], scratch_regs : Array[PhysicalReg]) -> MachineEnv

    MachineEnv::operand_scratch_regs

    source
    fn MachineEnv::operand_scratch_regs(self : MachineEnv) -> Array[PhysicalReg]

    MachineEnv::scratch_regs

    source
    fn MachineEnv::scratch_regs(self : MachineEnv) -> Array[PhysicalReg]

    MachineEnv::with_operand_scratch_regs

    source
    fn MachineEnv::with_operand_scratch_regs(self : MachineEnv, operand_scratch_regs : Array[PhysicalReg]) -> MachineEnv

    Select the reserved scratch registers that may hold instruction operands. Edit resolution continues to use the full scratch-register set.

    Operand

    source
    pub(all) struct Operand {
      vreg : VirtualReg
      role : OperandRole
      constraint : OperandConstraint
      preference : PhysicalReg?
      tie_id : Int
      timing : OperandTiming
    } derive(Eq, 
    Debug    )

    Operand::def

    source
    fn Operand::def(vreg : VirtualReg) -> Operand

    Operand::use_reg

    source
    fn Operand::use_reg(vreg : VirtualReg) -> Operand

    Operand::with_constraint

    source
    fn Operand::with_constraint(self : Operand, constraint : OperandConstraint) -> Operand

    Operand::with_preference

    source
    fn Operand::with_preference(self : Operand, preference : PhysicalReg) -> Operand

    Prefer a physical register without making it a correctness constraint. Allocation may ignore the preference when that register is unavailable.

    Operand::with_tie

    source
    fn Operand::with_tie(self : Operand, tie_id : Int) -> Operand

    Operand::with_timing

    source
    fn Operand::with_timing(self : Operand, timing : OperandTiming) -> Operand

    OperandAssignment

    source
    pub struct OperandAssignment {
      instruction : Int
      operand : Int
      location : Location
    } derive(Eq, 
    Debug    )

    OperandConstraint

    source
    pub(all) enum OperandConstraint {
      AnyReg
      AnyLocation
      FixedReg(PhysicalReg)
    } derive(Eq, 
    Debug    )

    OperandRole

    source
    pub(all) enum OperandRole {
      Use
      Def
      UseDef
    } derive(Eq, 
    Debug    )

    OperandTiming

    source
    pub(all) enum OperandTiming {
      Early
      Late
    } derive(Eq, 
    Debug    )

    PhysicalReg

    source
    pub(all) struct PhysicalReg {
      id : Int
      class : RegClass
    } derive(Eq, 
    Debug    )

    ProgramPoint

    source
    pub(all) struct ProgramPoint {
      block : Int
      inst : Int
    } derive(Eq, 
    Debug    )

    ProgramPoint::ProgramPoint

    source
    fn ProgramPoint::ProgramPoint(block : Int, inst : Int) -> ProgramPoint

    ProgramPoint::compare_with_order

    source
    fn ProgramPoint::compare_with_order(self : ProgramPoint, other : ProgramPoint, block_order : Array[Int]) -> Int

    ProgramRange

    source
    pub(all) struct ProgramRange {
      start : ProgramPoint
      end : ProgramPoint
    } derive(Eq, 
    Debug    )

    ProgramRange::ProgramRange

    source
    fn ProgramRange::ProgramRange(start : ProgramPoint, end : ProgramPoint) -> ProgramRange

    ProgramRange::contains

    source
    fn ProgramRange::contains(self : ProgramRange, point : ProgramPoint, block_order : Array[Int]) -> Bool

    ProgramRange::overlaps

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

    RegClass

    source
    pub(all) enum RegClass {
      Int
      Float
      Vector
    } derive(Eq, 
    Debug    )

    RegallocConfig

    source
    pub struct RegallocConfig {
      strategy : AllocatorStrategy
      verify : Bool
    } derive(Eq, 
    Debug    )

    RegallocConfig::RegallocConfig

    source
    fn RegallocConfig::RegallocConfig(strategy? : AllocatorStrategy, verify? : Bool) -> RegallocConfig

    RegallocConfig::strategy

    source

    RegallocConfig::verify

    source
    fn RegallocConfig::verify(self : RegallocConfig) -> Bool

    SpillSlotReservation

    source
    pub(all) struct SpillSlotReservation {
      slot : Int
      next_slot : Int
      slots_used : Int
    } derive(Eq, 
    Debug    )

    SpillSlotSpec

    source
    pub struct SpillSlotSpec {
      size : Int
      alignment : Int
    } derive(Eq, 
    Debug    )

    UseKind

    source
    pub(all) enum UseKind {
      LiveDef
      LiveUse
      LiveUseDef
    } derive(Eq, 
    Debug    )

    UsePosition

    source
    pub(all) struct UsePosition {
      point : ProgramPoint
      kind : UseKind
      constraint : OperandConstraint
      preference : PhysicalReg?
      tie_id : Int
    } derive(Eq, 
    Debug    )

    UsePosition::UsePosition

    source
    fn UsePosition::UsePosition(point : ProgramPoint, kind : UseKind, constraint : OperandConstraint) -> UsePosition

    UsePosition::with_preference

    source
    fn UsePosition::with_preference(self : UsePosition, preference : PhysicalReg?) -> UsePosition

    UsePosition::with_tie

    source
    fn UsePosition::with_tie(self : UsePosition, tie_id : Int) -> UsePosition

    VirtualReg

    source
    pub(all) struct VirtualReg {
      id : Int
      class : RegClass
    } derive(Eq, 
    Debug    )

    allocate_function

    source
    fn[F : FunctionView] allocate_function(function : F, environment : MachineEnv, config? : RegallocConfig) -> AllocationPlan raise VerifyError

    Allocate directly from a read-only machine-function view.

    reserve_spill_slot

    source
    fn reserve_spill_slot(next_slot : Int, class : RegClass) -> SpillSlotReservation

    Reserve spill slots in 8-byte units.

    Vector values require a 16-byte-aligned slot and occupy two 8-byte units.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io