regalloc

    Target-independent register allocation algorithm

    compiler
    register-allocation
    algorithm
    Download zip
    Author
    Version
    0.12.6
    License
    Apache-2.0
    Last updated
    24 days ago
    Downloads
    218

    #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

    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.

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

    FunctionView

    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

    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

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

    AllocationEdit::equal

    AllocationEdit::not_equal

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

    AllocationPlan

    pub struct AllocationPlan {
    // private fields
    }

    AllocationPlan::edits

    AllocationPlan::operand_assignments

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

    AllocationPlan::operand_location

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

    AllocationPlan::output

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

    AllocationPlan::spill_count

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

    AllocationPlan::spill_slot

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

    AllocationPlan::to_repr

    AllocationPlan::to_string

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

    AllocationPlan::value_location

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

    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.

    BundleAllocationStatistics

    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

    BundleAllocationStatistics::conflicts

    BundleAllocationStatistics::equal

    BundleAllocationStatistics::evictions

    BundleAllocationStatistics::max_queue_length

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

    BundleAllocationStatistics::not_equal

    BundleAllocationStatistics::occupied_segments_scanned

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

    BundleAllocationStatistics::queue_pops

    BundleAllocationStatistics::register_probes

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

    BundleAllocationStatistics::second_chance_attempts

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

    DenseCfgEdges

    type DenseCfgEdges derive(
    Debug
    )

    DenseLiveSets

    type DenseLiveSets derive(
    Debug
    )

    EditPosition

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

    EditPosition::equal

    EditPosition::hash

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

    EditPosition::hash_combine

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

    EditPosition::not_equal

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

    LiveRange

    type LiveRange derive(
    Debug
    )

    LiveRange::LiveRange

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

    LiveRange::add_range

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

    LiveRange::add_use

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

    LiveRange::end

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

    LiveRange::get_fixed_reg

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

    LiveRange::has_fixed_constraint

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

    LiveRange::has_tie_at

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

    LiveRange::id

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

    LiveRange::is_live_across

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

    LiveRange::overlap_allowed_by_tie

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

    LiveRange::overlaps

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

    LiveRange::range_at

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

    LiveRange::range_count

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

    LiveRange::start

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

    LiveRange::total_length

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

    LiveRange::touch

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

    LiveRange::touch_with_order

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

    LiveRange::use_at

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

    LiveRange::use_count

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

    LiveRange::vreg

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

    LiveRangeSet

    type LiveRangeSet derive(
    Debug
    )

    LiveRangeSet::LiveRangeSet

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

    LiveRangeSet::add_range

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

    LiveRangeSet::block_order

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

    LiveRangeSet::block_order_at

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

    LiveRangeSet::block_order_count

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

    LiveRangeSet::get

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

    LiveRangeSet::get_by_vreg

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

    LiveRangeSet::length

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

    Location

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

    Location::equal

    fn Location::equal(Location, Location) -> Bool

    Location::not_equal

    fn Location::not_equal(x : Location, y : Location) -> Bool

    Location::to_repr

    MachineEnv

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

    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

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

    MachineEnv::fixed_operand_regs

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

    MachineEnv::new

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

    MachineEnv::operand_scratch_regs

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

    MachineEnv::scratch_regs

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

    MachineEnv::with_fixed_operand_regs

    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

    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

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

    Operand::def

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

    Operand::equal

    fn Operand::equal(Operand, Operand) -> Bool

    Operand::not_equal

    fn Operand::not_equal(x : Operand, y : Operand) -> Bool

    Operand::to_repr

    Operand::use_reg

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

    Operand::with_constraint

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

    Operand::with_preference

    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

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

    Tie operands in one instruction by a shared nonnegative label. Labels are opaque and need not be contiguous or bounded by operand count.

    Operand::with_timing

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

    OperandAssignment

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

    OperandAssignment::equal

    OperandAssignment::not_equal

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

    OperandConstraint

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

    OperandConstraint::equal

    OperandConstraint::not_equal

    fn OperandConstraint::not_equal(x : OperandConstraint, y : OperandConstraint) -> Bool

    OperandRole

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

    OperandRole::equal

    fn OperandRole::equal(OperandRole, OperandRole) -> Bool

    OperandRole::not_equal

    fn OperandRole::not_equal(x : OperandRole, y : OperandRole) -> Bool

    OperandTiming

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

    OperandTiming::equal

    OperandTiming::not_equal

    fn OperandTiming::not_equal(x : OperandTiming, y : OperandTiming) -> Bool

    PhysicalReg

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

    PhysicalReg::equal

    fn PhysicalReg::equal(PhysicalReg, PhysicalReg) -> Bool

    PhysicalReg::not_equal

    fn PhysicalReg::not_equal(x : PhysicalReg, y : PhysicalReg) -> Bool

    ProgramPoint

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

    ProgramPoint::ProgramPoint

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

    ProgramPoint::compare_with_order

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

    ProgramPoint::equal

    ProgramPoint::not_equal

    fn ProgramPoint::not_equal(x : ProgramPoint, y : ProgramPoint) -> Bool

    ProgramRange

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

    ProgramRange::ProgramRange

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

    ProgramRange::contains

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

    ProgramRange::equal

    ProgramRange::not_equal

    fn ProgramRange::not_equal(x : ProgramRange, y : ProgramRange) -> Bool

    ProgramRange::overlaps

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

    RegClass

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

    RegClass::equal

    fn RegClass::equal(RegClass, RegClass) -> Bool

    RegClass::not_equal

    fn RegClass::not_equal(x : RegClass, y : RegClass) -> Bool

    RegClass::to_repr

    RegallocConfig

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

    RegallocConfig::RegallocConfig

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

    RegallocConfig::enter_phase

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

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

    RegallocConfig::verify

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

    RegallocPhase

    pub(all) enum RegallocPhase {
    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

    RegallocPhase::not_equal

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

    RegallocPhase::output

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

    RegallocPhase::to_string

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

    SpillSlotReservation

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

    SpillSlotReservation::equal

    SpillSlotReservation::not_equal

    SpillSlotSpec

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

    SpillSlotSpec::equal

    SpillSlotSpec::not_equal

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

    UseKind

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

    UseKind::equal

    fn UseKind::equal(UseKind, UseKind) -> Bool

    UseKind::not_equal

    fn UseKind::not_equal(x : UseKind, y : UseKind) -> Bool

    UseKind::to_repr

    UsePosition

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

    UsePosition::UsePosition

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

    UsePosition::equal

    fn UsePosition::equal(UsePosition, UsePosition) -> Bool

    UsePosition::not_equal

    fn UsePosition::not_equal(x : UsePosition, y : UsePosition) -> Bool

    UsePosition::with_preference

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

    UsePosition::with_tie

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

    VirtualReg

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

    VirtualReg::equal

    fn VirtualReg::equal(VirtualReg, VirtualReg) -> Bool

    VirtualReg::not_equal

    fn VirtualReg::not_equal(x : VirtualReg, y : VirtualReg) -> Bool

    allocate_function

    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.

    reserve_spill_slot

    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.