🥮 mooncakes.io

machv_regalloc

Target VCode adapter for the reusable register allocator

compiler
register-allocation
machv
jit
moon add Milky2018/machv_regalloc@0.6.2
Download zip
Author
Version
0.6.2
License
Apache-2.0
Repository
Last updated
2 days ago
Downloads
105

Dependencies

README

#machv_regalloc

MachV adapter for the reusable register allocator.

machv_regalloc bridges Milky2018/machv virtual-register functions to the target-independent Milky2018/regalloc algorithm. It projects MachV into the generic allocation model, applies allocation output, and keeps edge-copy and layout behavior compatible with MachV emission.

#Packages

  • Milky2018/machv_regalloc: projection, allocation entry points, application, validation, spill handling, and output construction.
  • Milky2018/machv_regalloc/layout: block layout utilities for MachV functions.

#When to use it

Use machv_regalloc when your code is already in MachV and you want to reuse the target-independent allocator. This package keeps MachV as the machine IR, invokes the allocator, and returns either a rewritten function or a Cranelift-style allocation Output that the emitter can consume without mutating the original virtual-register instructions.

#Example: allocate a MachV function

Callers provide their calling-convention data explicitly, allowing the same allocation workflow to support different ABIs and reserved-register policies.

///|
fn example_abi() -> @abi.EmbeddingABI {
  let call_conv : @abi.CallConventionLayout = {
    context_arg: { index: 27, class: Int },
    user_arg_gprs: [{ index: 0, class: Int }, { index: 1, class: Int }],
    arg_fprs: [{ index: 0, class: Float64 }, { index: 1, class: Float64 }],
    ret_gprs: [{ index: 0, class: Int }],
    ret_fprs: [{ index: 0, class: Float64 }],
  }
  EmbeddingABI(call_conv, reserve_context_role=false)
}

///|
test "allocate a MachV copy" {
  let builder = @machv.FunctionBuilder::FunctionBuilder("copy")
  let src = builder.add_param(Int)
  let dst = builder.new_vreg(Int)
  builder.append(Move, uses=[Virtual(src)], defs=[{ reg: Virtual(dst) }])
  |> ignore
  builder.terminate(Return([Virtual(dst)]))
  let allocated = allocate_registers_backtracking_with_isa(
    builder.finish(),
    AArch64,
    embedding_abi=Some(example_abi()),
  )
  inspect(allocated.blocks.length(), content="1")
  inspect(allocated.blocks[0].terminator is Some(Return(_)), content="true")
}

#Example: consume Cranelift-style output

The output API records per-operand locations and inserted edits. This is the preferred path for emitters that materialize moves while encoding instructions.

///|
test "read operand locations from regalloc output" {
  let builder = @machv.FunctionBuilder::FunctionBuilder("rewrite")
  let src = builder.add_param(Int)
  let dst = builder.new_vreg(Int)
  builder.append(Move, uses=[Virtual(src)], defs=[{ reg: Virtual(dst) }])
  |> ignore
  builder.terminate(Return([Virtual(dst)]))
  let (_func, output) = allocate_registers_backtracking_output_with_isa(
    builder.finish(),
    AArch64,
    embedding_abi=Some(example_abi()),
  )
  inspect(output.get_num_spillslots(), content="0")
  inspect(output.inst_def_loc(0, 0, false, 0) is Reg(_), content="true")
  inspect(output.inst_use_loc(0, 0, false, 0) is Reg(_), content="true")
}

#Integration

This package translates MachV functions into the regalloc input model and maps allocation results back to MachV locations and edits. Use the rewritten function API when later passes expect assigned registers, or consume Output directly while emitting instructions.

#
RegallocAlgorithm

source

Register allocation algorithm policy.

  • Backtracking: Ion-style backtracking + eviction/splitting (better codegen).
  • SinglePass: no eviction/backtracking, spills earlier (faster compile).

#
SpillSlot

source
type SpillSlot = Int

A spill slot index (8-byte slot).

#
AArch64StackFrame

source
type AArch64StackFrame

AArch64-specific stack frame configuration

#
AArch64StackFrame::AArch64StackFrame

source
fn AArch64StackFrame::AArch64StackFrame() -> AArch64StackFrame

#
AArch64StackFrame::alloc_spill

source

Allocate a spill slot

#
AArch64StackFrame::finalize

source
fn AArch64StackFrame::finalize(self : AArch64StackFrame) -> Unit

Finalize the frame

#
AArch64StackFrame::gen_epilogue

source

Generate epilogue instructions

#
AArch64StackFrame::gen_prologue

source

Generate prologue instructions

#
AArch64StackFrame::save_callee_reg

source
fn AArch64StackFrame::save_callee_reg(self : AArch64StackFrame, preg : 
PReg) -> Int

Add a callee-saved register

#
AArch64StackFrame::setup

source
fn AArch64StackFrame::setup(self : AArch64StackFrame) -> Unit

Setup the frame with FP and LR saves

#
AArch64StackFrame::size

source
fn AArch64StackFrame::size(self : AArch64StackFrame) -> Int

Get frame size

#
AllocStats

source
type AllocStats

Allocation statistics for comparison
impl Show for AllocStats

#
Allocation

source
pub enum Allocation {
  Reg(
PReg)
  Spill(Int)
  Unallocated
}

Allocation result for a LiveRange or Bundle
impl Show for Allocation

#
Bundle

source
type Bundle

A Bundle groups related LiveRanges that should ideally be allocated to the same physical register. Bundles are formed by merging LiveRanges connected by Move instructions, block arguments, or tied operands.

#
Bundle::Bundle

source
fn Bundle::Bundle(id : Int, reg_class : 
RegClass) -> Bundle

#
Bundle::contains_range

source
fn Bundle::contains_range(self : Bundle, range_id : Int) -> Bool

Check if this bundle contains a specific LiveRange

#
Bundle::crosses_call

source
fn Bundle::crosses_call(self : Bundle, ranges : LiveRangeSet) -> Bool

Check if any range in this bundle crosses a function call

#
Bundle::crosses_foreign_call

source
fn Bundle::crosses_foreign_call(self : Bundle, ranges : LiveRangeSet) -> Bool

Check if any range in this bundle crosses a foreign/helper call

#
Bundle::crosses_internal_call

source
fn Bundle::crosses_internal_call(self : Bundle, ranges : LiveRangeSet) -> Bool

Check if any range in this bundle crosses an internal call

#
Bundle::get_fixed_reg

source
fn Bundle::get_fixed_reg(self : Bundle, ranges : LiveRangeSet) -> 
PReg?

Get the fixed register if all ranges in bundle require same fixed reg

#
Bundle::has_fixed_constraint

source
fn Bundle::has_fixed_constraint(self : Bundle, ranges : LiveRangeSet) -> Bool

#
Bundle::overlaps

source
fn Bundle::overlaps(self : Bundle, other : Bundle, ranges : LiveRangeSet) -> Bool

Check if this bundle overlaps with another bundle

#
Bundle::to_string

source
fn Bundle::to_string(self : Bundle, _ranges : LiveRangeSet) -> String

#
Bundle::total_length

source
fn Bundle::total_length(self : Bundle, ranges : LiveRangeSet) -> Int

Get total length of all ranges in this bundle

#
BundleSet

source
type BundleSet

Collection of Bundles

#
BundleSet::BundleSet

source
fn BundleSet::BundleSet() -> BundleSet

#
BundleSet::get

source
fn BundleSet::get(self : BundleSet, id : Int) -> Bundle

Get bundle by ID

#
BundleSet::length

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

Get number of bundles

#
Edit

source
pub(all) enum Edit {
  Move(Loc, Loc, 
RegClass)
}

An edit produced by regalloc to be inserted at a program point.

Equivalent to regalloc2::Edit::Move in Cranelift: move between two locations.
impl Show for Edit

#
InstEdits

source
type InstEdits

Edits to insert before/after an instruction.

#
LiveInterval

source
pub struct LiveInterval {
  vreg : 
VReg
  start : ProgPoint
  end : ProgPoint
  uses : Array[ProgPoint]
  hint : 
PReg?
  assigned : 
PReg?
  spill_slot : Int?
  crosses_call : Bool
  crosses_foreign_call : Bool
}

A live interval - the range where a virtual register is live

#
LiveRange

source
type LiveRange

A LiveRange represents the liveness of a single virtual register with precise span information and use constraints.
impl Show for LiveRange

#
LiveRange::LiveRange

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

#
LiveRange::end

source
fn LiveRange::end(self : LiveRange, block_order : FixedArray[Int]) -> ProgPoint?

Get the end point (latest point in all ranges)

#
LiveRange::get_fixed_reg

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

Get the fixed register constraint if all uses require the same fixed reg

#
LiveRange::has_fixed_constraint

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

Check if this LiveRange has any fixed register constraint

#
LiveRange::overlaps

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

Check if this LiveRange overlaps with another

#
LiveRange::start

source
fn LiveRange::start(self : LiveRange, block_order : FixedArray[Int]) -> ProgPoint?

Get the start point (earliest point in all ranges)

#
LiveRange::total_length

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

Compute total length of all ranges (in instruction count)

#
LiveRangeSet

source
type LiveRangeSet

Collection of LiveRanges built from liveness analysis

#
LiveRangeSet::get

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

Get LiveRange by index

#
LiveRangeSet::get_by_vreg

source
fn LiveRangeSet::get_by_vreg(self : LiveRangeSet, vreg_id : Int) -> LiveRange?

Get LiveRange by vreg id

#
LiveRangeSet::length

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

Get number of ranges

#
LivenessResult

source
pub struct LivenessResult {
  intervals : Map[Int, LiveInterval]
  use_def : Map[Int, UseDefInfo]
  use_def_dense : Array[UseDefInfo?]
  live_in : Array[
Set[Int]]
  live_out : Array[
Set[Int]]
  live_in_dense : Array[Array[Int]]?
  live_out_dense : Array[Array[Int]]?
  block_order : FixedArray[Int]
  call_points : Array[(ProgPoint, 
CallClobberClass)]
}

Liveness analysis result

#
Loc

source
pub(all) enum Loc {
  Reg(
PReg)
  Spill(Int)
}

A location for a value at a program point: either in a register or in a spill slot.
impl Show for Loc

#
OperandConstraint

source
pub enum OperandConstraint {
  AnyReg
  FixedReg(
PReg)
}

Operand constraint for a use position

#
Output

source
pub struct Output {
  param_locs : Array[Loc]
  allocs : Array[Loc]
  operand_ranges : Array[(Int, Int, Bool, Int, Int, Int)]
  inst_operand_range_index : Array[Array[Int]]
  term_operand_range_index : Array[Int]
  edits : Array[((Int, Int, ProgPos), Edit)]
  edits_before_dense : Array[Array[Array[Edit]]]
  edits_after_dense : Array[Array[Array[Edit]]]
  used_int_pregs_any : Array[Bool]
  used_fp_pregs_any : Array[Bool]
  num_spillslots : Int
}

Regalloc output.

  • allocs is a flat array of operand allocations, aligned with operand_ranges.
  • edits is a list of edits keyed by a program point (block/inst/pos).
  • num_spillslots is used by stack-frame layout.

#
Output::Output

source
fn Output::Output() -> Output

#
Output::begin_inst_allocs

source
fn Output::begin_inst_allocs(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_count : Int, use_count : Int) -> (Int, Int)

Start recording operand allocations for one instruction/terminator. Returns (start, total) where start is the first index in allocs.

#
Output::edits_at

source
fn Output::edits_at(self : Output, block_id : Int, inst_idx : Int, pos : ProgPos) -> Array[Edit]?

#
Output::end_inst_allocs

source
fn Output::end_inst_allocs(self : Output, start : Int, total : Int) -> Unit

#
Output::finalize_edits

source
fn Output::finalize_edits(self : Output) -> Unit

#
Output::get_num_params

source
fn Output::get_num_params(self : Output) -> Int

#
Output::get_num_spillslots

source
fn Output::get_num_spillslots(self : Output) -> Int

#
Output::get_param_loc

source
fn Output::get_param_loc(self : Output, idx : Int) -> Loc

#
Output::inst_def_loc

source
fn Output::inst_def_loc(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_idx : Int) -> Loc

#
Output::inst_use_loc

source
fn Output::inst_use_loc(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, use_idx : Int) -> Loc

#
Output::iter_allocs

source
fn Output::iter_allocs(self : Output) -> Array[Loc]

#
Output::iter_edits

source
fn Output::iter_edits(self : Output) -> Array[((Int, Int, ProgPos), Edit)]

#
Output::push_edit

source
fn Output::push_edit(self : Output, block_id : Int, inst_idx : Int, pos : ProgPos, edit : Edit) -> Unit

#
Output::push_inst_alloc_loc

source
fn Output::push_inst_alloc_loc(self : Output, loc : Loc) -> Unit

#
Output::push_inst_allocs

source
fn Output::push_inst_allocs(self : Output, block_id : Int, inst_idx : Int, is_terminator : Bool, def_count : Int, use_count : Int, locs : Array[Loc]) -> Unit

Record operand allocations for one instruction/terminator. locs must have length def_count + use_count, in that order.

#
Output::push_param_loc

source
fn Output::push_param_loc(self : Output, loc : Loc) -> Unit

#
Output::rebuild_edits_index

source
fn Output::rebuild_edits_index(self : Output) -> Unit

#
Output::sort_edits

source
fn Output::sort_edits(self : Output) -> Unit

#
Output::spill_reload_stats

source
fn Output::spill_reload_stats(self : Output) -> (Int, Int, Int, Int)

Return stack-traffic counts inferred from regalloc edits: (spills, reloads, reg_moves, spill_to_spill).

#
Output::summary

source
fn Output::summary(self : Output) -> String

A compact human-readable summary for debugging (used by the CLI explore command).

#
Output::uses_preg_index_any

source
fn Output::uses_preg_index_any(self : Output, preg_idx : Int, is_int_class : Bool) -> Bool

#
Output::validate_for_isa

source
fn Output::validate_for_isa(self : Output, isa : 
ISA) -> Unit

Validate that the regalloc output only uses legal physical registers for the selected ISA.

This is a fail-fast guard: silent truncation in x86 encoders can clobber rsp/rbp if an out-of-range preg leaks into emission (e.g. x20 -> rsp).

#
ProgPoint

source
pub struct ProgPoint {
  block : Int
  inst : Int
  pos : ProgPos
} derive(Eq, Hash, 
Debug)

A program point - identifies a position in the MachV function Using #valtype for stack allocation - this struct is created/compared frequently
impl Show for ProgPoint

#
ProgPointRange

source
type ProgPointRange

A contiguous program point range (start inclusive, end exclusive)

#
ProgPointRange::contains

source
fn ProgPointRange::contains(self : ProgPointRange, point : ProgPoint, block_order : FixedArray[Int]) -> Bool

Check if a point is within this range

#
ProgPos

source
pub(all) enum ProgPos {
  Before
  After
} derive(Eq, Hash, 
Debug)

Position relative to an instruction

#
RegAllocResult

source
pub struct RegAllocResult {
  assignments : Map[Int, 
PReg]
  spill_slots : Map[Int, Int]
  num_spill_slots : Int
  inst_edits : Array[(Int, Int, InstEdits)]
}

Register allocation result

#
RegMove

source
type RegMove

A move between two locations (register or spill slot).
impl Show for RegMove

#
SpillBundle

source
type SpillBundle

A SpillBundle tracks a shared spill slot for split bundles. When a bundle is split, both parts share the same SpillBundle so they use the same stack slot.

#
SpillBundle::SpillBundle

source
fn SpillBundle::SpillBundle(id : Int, slot : Int) -> SpillBundle

#
StackFrame

source
type StackFrame

Stack frame layout for a function
impl Show for StackFrame

#
StackFrame::StackFrame

source
fn StackFrame::StackFrame(frame_align : Int) -> StackFrame

#
StackFrame::add_callee_saved

source
fn StackFrame::add_callee_saved(self : StackFrame, preg : 
PReg) -> Int

Record a callee-saved register that needs to be saved

#
StackFrame::alloc_local

source
fn StackFrame::alloc_local(self : StackFrame, local_idx : Int, size : Int, align : Int) -> Int

Allocate a slot for a local variable

#
StackFrame::alloc_outgoing_arg

source
fn StackFrame::alloc_outgoing_arg(self : StackFrame, arg_idx : Int, size : Int, align : Int) -> Int

Allocate a slot for an outgoing argument

#
StackFrame::alloc_spill_slot

source
fn StackFrame::alloc_spill_slot(self : StackFrame, vreg : 
VReg, size : Int, align : Int) -> Int

Allocate a spill slot for a virtual register

#
StackFrame::finalize

source
fn StackFrame::finalize(self : StackFrame) -> Unit

Finalize the frame layout and compute total size

#
StackFrame::get_callee_saved

source
fn StackFrame::get_callee_saved(self : StackFrame) -> Array[
PReg]

Get all callee-saved registers that were used

#
StackFrame::print

source
fn StackFrame::print(self : StackFrame) -> String

Print the frame layout

#
StackFrame::size

source
fn StackFrame::size(self : StackFrame) -> Int

Get the total frame size

#
StackSlot

source
type StackSlot

A stack slot - a location on the stack
impl Show for StackSlot

#
StackSlotKind

source
pub enum StackSlotKind {
  Spill(
VReg)
  Local(Int)
  OutgoingArg(Int)
  CalleeSaved(
PReg)
}

Kind of stack slot

#
UseDefInfo

source
type UseDefInfo

Use-def information for a single vreg

#
UseKind

source
type UseKind

Kind of use at a program point Note: For tied operands (same reg as both def and use), add a DefUse variant when Inst supports tied operand representation.
impl Show for UseKind

#
UsePosition

source
type UsePosition

A use position within a LiveRange
impl Show for UsePosition

#
allocate_registers_backtracking

source

Allocate MachV virtual registers through the production backtracking path.

machv_regalloc builds MachV liveness, register pools, and output edits; reusable allocation-loop, probe, eviction, split, and spill policies live in regalloc.

#
allocate_registers_backtracking_output

source
fn allocate_registers_backtracking_output(func : 
Function, embedding_abi? : 
EmbeddingABI?) -> (
Function, Output)

Allocate MachV virtual registers and return a Cranelift-style regalloc Output.

The returned @machv.Function is not rewritten to physical registers; the emitter consumes the returned Output to materialize edits and operand allocations on the fly.

#
allocate_registers_backtracking_output_with_isa

source

Allocate MachV virtual registers and return Output using a specific ISA policy implementation.

#
allocate_registers_backtracking_with_isa

source

Allocate registers using a specific ISA policy implementation.

#
apply_allocation

source

Apply register allocation results to a MachV function Handles spilled registers by inserting StackLoad/StackStore instructions

#
build_bundles_with_merging

source
fn build_bundles_with_merging(func : 
Function, ranges : LiveRangeSet) -> BundleSet

Build bundles with merging from Move instructions and block arguments

#
build_initial_bundles

source
fn build_initial_bundles(ranges : LiveRangeSet) -> BundleSet

Build initial bundles from LiveRanges Each LiveRange starts in its own bundle

#
build_live_ranges

source
fn build_live_ranges(func : 
Function, liveness : LivenessResult) -> LiveRangeSet

Build LiveRanges from liveness analysis result This is Phase 2 of the Ion allocator

#
build_stack_layout_aarch64

source
fn build_stack_layout_aarch64(alloc : RegAllocResult, func : 
Function) -> AArch64StackFrame

Build stack layout from register allocation result

#
compute_liveness

source
fn compute_liveness(func : 
Function) -> LivenessResult

Compute full liveness information including interval maps.

#
compute_liveness_for_regalloc

source
fn compute_liveness_for_regalloc(func : 
Function) -> LivenessResult

Compute liveness for regalloc hot path (no interval map construction).

#
compute_loop_depths

source
fn compute_loop_depths(func : 
Function) -> Array[Int]

Pre-compute per-block approximate loop depth, aligned with regalloc2's CFG heuristic (cfg.rs::approx_loop_depth): count backedge entries/exits over linear block order and maintain a small nesting stack.

#
compute_spill_weight

source
fn compute_spill_weight(bundle : Bundle, ranges : LiveRangeSet, loop_depths : Array[Int]) -> Int

Compute spill weight for a bundle using pre-computed loop depths Higher weight = more important to keep in register

#
debug_liveness

source
fn debug_liveness(liveness : LivenessResult) -> String

Debug: print liveness info

#
eliminate_dead_code

source

Eliminate dead code from a MachV function Removes instructions that define vregs which are never used

#
get_alloc_stats

source

Get allocation statistics

#
process_constraints

source
fn process_constraints(func : 
Function, alloc : RegAllocResult) -> Unit

Process operand constraints and generate RegMove edits Design: constraints are processed after allocation and moves are inserted when the allocated register doesn't match the constraint

#
rematerialize_cross_block_constants

source
fn rematerialize_cross_block_constants(func : 
Function) -> 
Function

Rematerialize cross-block cheap defs:
  • Detect vregs defined by rematerializable opcodes.
  • If such a vreg is used in a different block than its def, clone the defining opcode into each such use block and rewrite uses to a block-local vreg.

This is intentionally conservative and mirrors Cranelift’s “clone remat values into the block where used” strategy.

#
rematerialize_long_distance_constants

source
fn rematerialize_long_distance_constants(func : 
Function) -> 
Function

Clone long-distance rematerializable defs within the same block.

This mirrors Cranelift's remat intent for cheap constants: shorten very long live ranges by re-defining constants near far-away uses.

#
verify_allocation

source

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io