🥮 mooncakes.io

regalloc

Target-independent register allocation algorithm

compiler
register-allocation
algorithm
Download zip
Author
Version
0.14.0
License
Apache-2.0
Repository
Last updated
16 hours ago
Downloads
184

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

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.

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_at

source
fn AllocationPlan::edit_at(self : AllocationPlan, index : Int) -> AllocationEdit?

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_instruction_count

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

AllocationPlan::operand_location

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

AllocationPlan::operand_location_storage

source

Shares the allocator's finalized dense operand-location tables with an embedding. seal_operand_storage establishes the source function's exact instruction and operand shape before allocation returns.

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

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

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.

AllocationPlan::value_location_storage

source

Shares the allocator's finalized dense value-location table with an embedding. The plan must not be mutated after this table is adopted.

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

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, 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

LiveRange

source
type LiveRange derive(
Debug)

LiveRange::LiveRange

source

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

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

source

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

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

LiveRangeSet::length

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

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

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

ProgramPoint::equal

source

ProgramPoint::not_equal

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

ProgramPoint::to_repr

source

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

source

ProgramRange::not_equal

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

ProgramRange::overlaps

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

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

SpillSlotReservation

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

SpillSlotReservation::equal

source

SpillSlotReservation::not_equal

source

SpillSlotReservation::to_repr

source

SpillSlotSpec

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

SpillSlotSpec::equal

source

SpillSlotSpec::not_equal

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

SpillSlotSpec::to_repr

source

UseKind

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

UseKind::equal

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

UseKind::not_equal

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

UseKind::to_repr

source

UsePosition

source

UsePosition::UsePosition

source

UsePosition::equal

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

UsePosition::not_equal

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

UsePosition::to_repr

source

UsePosition::with_preference

source

UsePosition::with_tie

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

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.

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