🥮 mooncakes.io

    regalloc

    Target-independent register allocation algorithm

    compiler
    register-allocation
    algorithm
    Download zip
    Author
    Version
    0.19.0
    License
    Apache-2.0
    Repository
    Last updated
    3 days ago
    Downloads
    1K

    #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.

    Allocation tables stay private. Consumers use checked location queries, spill-slot layouts, and edit snapshots; allocator embeddings write through AllocationSink.

    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. PreservedHome is reserved for metadata operands that must remain at a canonical register or spill home that survives the instruction's clobbers, without temporary materialization. Safepoint roots use this constraint so stack maps never point at an ephemeral call-transfer location.

    #Allocation

    The allocator 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 implementation. There is no alternate allocation strategy; compile-time work belongs in the same verified allocator rather than a lower-quality fallback.

    #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. Collection queries return non-owning, read-only ArrayView spans. Implementations must keep their backing storage alive for the allocation call and should not allocate a collection per query.

    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.

    fixed_operand_regs are a third, narrower role. They are excluded from value homes and allocator-chosen scratches, but an instruction may name one explicitly with FixedReg; operand materialization can then move the value into that named register at the instruction boundary. This models reserved ISA operands such as an x64 instruction-local temporary without granting the allocator general scratch authority over that register.

    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/vcode_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 MilkIR directly to target-owned VCode and expose that VCode directly through FunctionView. 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.

    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.

    #Retired live-range utilities

    Live ranges, use positions, and their program-point/range representation are private allocator state. Integrations use FunctionView, AllocationSink, and AllocationPlan; they do not construct or inspect liveness internals.

    Ties remain on the source operands consumed by allocation. Liveness no longer copies unused tie ids. Unused range-inspection helpers and UnionFind::get_all_sets are retired; allocation and tie verification are unchanged.

    Location

    source

    A packed allocation result location within one allocation session.

    Spill indices are session-local and must be translated at ownership boundaries before they are exposed as product-facing stack-slot handles.

    Operand

    source

    The canonical allocation facts for one instruction operand.

    OperandConstraint

    source
    using @Milky2018/vcode/allocation_types { type AllocationConstraint as OperandConstraint }

    A normalized register-allocation constraint.

    Operand ties are represented separately by a shared nonnegative tie label, so this type contains only location constraints.

    OperandRole

    source

    Whether an allocation operand reads, writes, or both reads and writes its virtual register.

    SSA VCode producers use Use and Def. UseDef remains available to standalone register-allocation clients that model in-place updates.

    OperandTiming

    source

    The point within an instruction where an allocation operand is read or written.

    PhysicalReg

    source

    A target physical register identified within one register class.

    RegClass

    source

    Target-neutral register-class identity shared by VCode and register allocation.

    FpVector preserves targets whose scalar floating-point and vector values occupy one physical register bank. Float and Vector remain available to standalone allocator embeddings that model distinct banks.

    VirtualReg

    source

    A dense virtual-register identity within one allocation session.

    AllocationSink

    source
    pub(open) trait AllocationSink {
      fn assign_value(Self, 
    VirtualReg    , 
    AllocationLocation    ) -> Unit
      fn assign_operand(Self, Int, Int, 
    AllocationLocation    ) -> Unit
      fn create_spill_slot(Self, Int, Int, Int) -> Int
      fn value_location(Self, Int) -> 
    AllocationLocation    ?
      fn operand_location(Self, Int, Int) -> 
    AllocationLocation    ?
      fn spill_slot(Self, Int) -> SpillSlotSpec?
      fn add_edit(Self, AllocationEdit) -> Unit
      fn edits(Self) -> Array[AllocationEdit]
    }

    Final allocation storage supplied by an embedding. Writes are statically dispatched; the allocator retains only unresolved parallel edits. Implementations must start empty, use dense spill ids, and preserve writes for location queries. edits is needed only when verification is enabled.

    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_value_count(Self) -> Int
      fn entry_value_at(Self, Int) -> 
    VirtualReg
      fn block_count(Self) -> Int
      fn block_id_at(Self, Int) -> Int
      fn block_parameter_count(Self, Int) -> Int
      fn block_parameter_at(Self, Int, Int) -> 
    VirtualReg
      fn block_instruction_count(Self, Int) -> Int
      fn block_instruction_at(Self, Int, Int) -> Int
      fn block_successor_count(Self, Int) -> Int
      fn block_successor_at(Self, Int, Int) -> Int
      fn edge_argument_count(Self, Int, Int) -> Int
      fn edge_argument_at(Self, Int, Int, Int) -> 
    VirtualReg
      fn instruction_operands(Self, Int) -> ArrayView[
    AllocationOperand    ]
      fn instruction_clobbers(Self, Int) -> ArrayView[
    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

    AllocationEdit

    source

    AllocationEdit::equal

    source

    AllocationEdit::not_equal

    source
    fn AllocationEdit::not_equal(x : AllocationEdit, y : AllocationEdit) -> Bool

    AllocationEdit::to_repr

    source

    AllocationPlan

    source
    pub struct AllocationPlan {
      // private fields
    }

    AllocationPlan::edit_count

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

    AllocationPlan::edits

    source

    AllocationPlan::instruction_operand_count

    source
    fn AllocationPlan::instruction_operand_count(self : AllocationPlan, instruction : Int) -> Int

    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) -> 
    AllocationLocation    ?

    AllocationPlan::output

    source
    fn AllocationPlan::output(self : AllocationPlan, logger : &Logger) -> Unit

    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::to_repr

    source

    AllocationPlan::to_string

    source
    fn AllocationPlan::to_string(self : AllocationPlan) -> String

    AllocationPlan::value_location

    source

    Return the value's default transfer home.

    Segment-specific operand assignments and edits may keep the newest value elsewhere until a transition returns it here.

    AllocationSession

    source
    pub struct AllocationSession {
      // private fields
    }

    Reusable storage for a serial sequence of register-allocation jobs.

    A session is intentionally not thread-safe. Independent compilation jobs must own independent sessions; callers compiling functions serially may reuse one session to retain scratch capacity between functions.

    AllocationSession::allocate_function

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

    Allocate one function while retaining scratch capacity for the next serial call on this session.

    AllocationSession::allocate_into

    source
    fn[F : FunctionView, S : AllocationSink] AllocationSession::allocate_into(self : AllocationSession, function : F, environment : MachineEnv, sink : S, config? : RegallocConfig) -> Unit raise VerifyError

    Allocate into fresh embedding-owned output storage. On failure, discard the partially written sink. Verification queries the same output that is returned.

    AllocationSession::new

    source

    BundleAllocationStatistics

    source
    pub struct BundleAllocationStatistics {
      queue_pops : Int
      register_probes : Int
      occupied_segments_scanned : Int
      conflicts : Int
      evictions : Int
      bundle_splits : Int
      second_chance_attempts : Int
      max_queue_length : Int
    } derive(Eq, 
    Debug    )

    Deterministic work counters for the backtracking bundle loop.

    These count allocator decisions rather than elapsed time, so callers can compare runs without making this reusable module own a clock.

    BundleAllocationStatistics::bundle_splits

    source

    BundleAllocationStatistics::conflicts

    source

    BundleAllocationStatistics::equal

    source

    BundleAllocationStatistics::evictions

    source

    BundleAllocationStatistics::max_queue_length

    source
    fn BundleAllocationStatistics::max_queue_length(self : BundleAllocationStatistics) -> Int

    BundleAllocationStatistics::not_equal

    source

    BundleAllocationStatistics::occupied_segments_scanned

    source
    fn BundleAllocationStatistics::occupied_segments_scanned(self : BundleAllocationStatistics) -> Int

    BundleAllocationStatistics::queue_pops

    source

    BundleAllocationStatistics::register_probes

    source
    fn BundleAllocationStatistics::register_probes(self : BundleAllocationStatistics) -> Int

    BundleAllocationStatistics::second_chance_attempts

    source
    fn BundleAllocationStatistics::second_chance_attempts(self : BundleAllocationStatistics) -> Int

    BundleAllocationStatistics::to_repr

    source

    EditPosition

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

    EditPosition::equal

    source

    EditPosition::hash

    source
    fn EditPosition::hash(self : EditPosition) -> Int

    EditPosition::hash_combine

    source
    fn EditPosition::hash_combine(EditPosition, Hasher) -> Unit

    EditPosition::not_equal

    source
    fn EditPosition::not_equal(x : EditPosition, y : EditPosition) -> Bool

    EditPosition::to_repr

    source

    MachineEnv

    source

    Physical-register policy supplied by the embedding target.

    scratch_regs resolve allocator-inserted edits. The operand scratch subset may additionally hold unconstrained instruction operands; targets may restrict that subset when their emitter reserves scratch registers for local expansion. Fixed-operand registers are reserved from both scratch roles and become legal only when an instruction explicitly names one with FixedReg.

    MachineEnv::allocatable_regs

    source

    MachineEnv::fixed_operand_regs

    source

    MachineEnv::new

    source

    MachineEnv::operand_scratch_regs

    source

    MachineEnv::scratch_regs

    source

    MachineEnv::with_fixed_operand_regs

    source
    fn MachineEnv::with_fixed_operand_regs(self : MachineEnv, fixed_operand_regs : Array[
    PhysicalReg    ]) -> MachineEnv

    Declare reserved registers that may be used only by matching FixedReg instruction operands.

    These registers are not value homes or allocator-chosen scratches. A fixed operand may still require an explicit edit that moves its value into the named register at the instruction boundary.

    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.

    OperandAssignment

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

    OperandAssignment::equal

    source

    OperandAssignment::not_equal

    source
    fn OperandAssignment::not_equal(x : OperandAssignment, y : OperandAssignment) -> Bool

    OperandAssignment::to_repr

    source

    RegallocConfig

    source
    pub struct RegallocConfig {
      verify : Bool
      observer : (RegallocPhase?) -> Unit?
      statistics_observer : (BundleAllocationStatistics) -> Unit?
    }

    RegallocConfig::RegallocConfig

    source
    fn RegallocConfig::RegallocConfig(verify? : Bool, observer? : (RegallocPhase?) -> Unit?, statistics_observer? : (BundleAllocationStatistics) -> Unit?) -> RegallocConfig

    RegallocConfig::enter_phase

    source
    fn RegallocConfig::enter_phase(self : RegallocConfig, phase : RegallocPhase?) -> Unit

    Announce that phase is starting, or that the last one has finished.

    RegallocConfig::verify

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

    RegallocPhase

    source
    pub(all) enum RegallocPhase {
      InputValidation
      LiveRanges
      SegmentConstruction
      BundleFormation
      BundleAllocation
      HomeAssignment
      OperandAssignment
      EdgeTransfers
      EditResolution
      Verification
    } derive(Eq, 
    Debug    )

    The allocator's internal phases, in the order they run.

    Reported through RegallocConfig::observer so a caller that owns a clock can attribute compile time per phase. This module stays clock-free: it only says which phase it is entering (ISS-371).

    RegallocPhase::equal

    source

    RegallocPhase::not_equal

    source
    fn RegallocPhase::not_equal(x : RegallocPhase, y : RegallocPhase) -> Bool

    RegallocPhase::output

    source
    fn RegallocPhase::output(self : RegallocPhase, logger : &Logger) -> Unit

    RegallocPhase::to_repr

    source

    RegallocPhase::to_string

    source
    fn RegallocPhase::to_string(self : RegallocPhase) -> String

    SpillSlotSpec

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

    SpillSlotSpec::equal

    source

    SpillSlotSpec::new

    source
    fn SpillSlotSpec::new(size : Int, alignment : Int) -> SpillSlotSpec

    SpillSlotSpec::not_equal

    source
    fn SpillSlotSpec::not_equal(x : SpillSlotSpec, y : SpillSlotSpec) -> Bool

    SpillSlotSpec::to_repr

    source

    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.

    The observer sees Some(phase) as each phase begins and exactly one None once the last one ends, including when allocation fails. A raise used to skip that None, leaving whoever was measuring with a phase that never ended — Verification most often, since verifying the finished plan is both the likeliest raise and the last phase to open.

    Source Files