🥮 mooncakes.io

regalloc

Target-independent register allocation algorithm

compiler
register-allocation
algorithm
moon add Milky2018/regalloc@0.7.2
Download zip
Author
Version
0.7.2
License
Apache-2.0
Repository
Last updated
2 days ago
Downloads
116
README

#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

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
}

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

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.

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

#
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

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

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

#
MachineEnv::fixed_operand_regs

source
fn MachineEnv::fixed_operand_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_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.

#
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

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

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 {
  verify : Bool
  observer : (RegallocPhase?) -> Unit?
}

#
RegallocConfig::RegallocConfig

source
fn RegallocConfig::RegallocConfig(verify? : Bool, observer? : (RegallocPhase?) -> 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 {
  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).

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

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