🥮 mooncakes.io
    Sign in

    regalloc

    Target-independent register allocation algorithm

    compiler
    register-allocation
    algorithm
    Download zip
    Author
    Version
    0.1.1
    License
    Apache-2.0
    Repository
    Last updated
    3 months ago
    Downloads
    293

    No dependencies

    #regalloc

    Target-independent register allocation algorithm.

    regalloc models allocation programs, machine environments, live ranges, allocation decisions, move resolution, spill planning, and verification without depending on a concrete machine IR.

    #Package

    • Milky2018/regalloc: allocation data structures, allocator entry points, policy helpers, and verifier APIs.

    #When to use it

    Use regalloc when you have a machine-independent allocation problem: virtual registers, physical registers, instructions, use/def operands, clobbers, and a control-flow graph. It deliberately does not know about concrete IRs, frontend dialects, or target instruction formats.

    #Example: allocate an abstract program

    The smallest program has physical registers, one block, and instructions with virtual-register operands. The allocator returns locations for each virtual register and can be checked with the verifier.

    ///|
    test "allocate virtual registers to physical registers" {
      let r0 : PhysicalReg = { id: 0, class: Int }
      let r1 : PhysicalReg = { id: 1, class: Int }
      let v0 : VirtualReg = { id: 0, class: Int }
      let v1 : VirtualReg = { id: 1, class: Int }
      let program = Program::Program([r0, r1])
      let block = Block::Block(0)
      let inst = Instruction::Instruction(0)
      inst.add_operand(Operand::def(v0))
      inst.add_operand(Operand::use_reg(v1))
      block.append(inst)
      program.add_block(block)
      let allocation = allocate_linear_scan(program)
      inspect(allocation.location_of(v0) == Some(Reg(r0)), content="true")
      inspect(allocation.location_of(v1) == Some(Reg(r1)), content="true")
      inspect(verify_allocation(program, allocation), content="()")
    }

    #Example: inspect live ranges before allocation

    Live ranges are independent of the allocator choice. Compiler authors can use them to debug why a value was spilled or why two values could not share a register.

    ///|
    test "compute a live range across two instructions" {
      let r0 : PhysicalReg = { id: 0, class: Int }
      let v0 : VirtualReg = { id: 0, class: Int }
      let program = Program::Program([r0])
      let block = Block::Block(0)
      let def_inst = Instruction::Instruction(0)
      def_inst.add_operand(Operand::def(v0))
      block.append(def_inst)
      let use_inst = Instruction::Instruction(1)
      use_inst.add_operand(Operand::use_reg(v0))
      block.append(use_inst)
      program.add_block(block)
      let ranges = build_live_ranges(program)
      let range = ranges.get_by_vreg(v0).unwrap()
      inspect(range.start() == Some(ProgramPoint(0, 0)), content="true")
      inspect(range.end() == Some(ProgramPoint(0, 1)), content="true")
      inspect(range.uses.length(), content="2")
    }

    #Boundary

    This module should stay a pure algorithmic layer. Machine-IR-specific adapters belong in modules such as machv_regalloc.

    VerifyError

    source
    pub suberror VerifyError {
      Unassigned(vreg~ : VirtualReg)
      FixedConstraintViolation(vreg~ : VirtualReg, required~ : PhysicalReg, actual~ : Location)
      OverlappingAllocation(left~ : VirtualReg, right~ : VirtualReg, location~ : Location)
      RegisterClassMismatch(vreg~ : VirtualReg, preg~ : PhysicalReg)
      ClobberedRegister(vreg~ : VirtualReg, preg~ : PhysicalReg)
      TiedConstraintViolation(left~ : VirtualReg, right~ : VirtualReg, left_location~ : Location, right_location~ : Location)
      ScratchRegisterUnavailable(message~ : String)
    }

    ActiveReloadCache

    source
    pub(all) struct ActiveReloadCache {
      epoch : Array[Int]
      preg_ids : Array[Int]
    } derive(
    Debug    )

    ActiveReloadCache::ActiveReloadCache

    source
    fn ActiveReloadCache::ActiveReloadCache(slot_count : Int) -> ActiveReloadCache

    ActiveReloadCache::clear

    source
    fn ActiveReloadCache::clear(self : ActiveReloadCache, slot : Int) -> Unit

    ActiveReloadCache::get

    source
    fn ActiveReloadCache::get(self : ActiveReloadCache, slot : Int, epoch : Int) -> Int?

    ActiveReloadCache::set

    source
    fn ActiveReloadCache::set(self : ActiveReloadCache, slot : Int, preg_id : Int, epoch : Int) -> Unit

    AllocatedProgramSpan

    source
    pub(all) struct AllocatedProgramSpan {
      owner_id : Int
      span : OrderedProgramSpan
    } derive(Eq, 
    Debug    )

    Allocation

    source
    pub(all) struct Allocation {
      assignments : Array[Assignment]
      spill_count : Int
    } derive(
    Debug    )

    Allocation::Allocation

    source
    fn Allocation::Allocation() -> Allocation

    Allocation::assign

    source
    fn Allocation::assign(self : Allocation, vreg : VirtualReg, location : Location) -> Unit

    Allocation::location_of

    source
    fn Allocation::location_of(self : Allocation, vreg : VirtualReg) -> Location?

    AssignedSlot

    source
    pub(all) struct AssignedSlot[R] {
      start : Int
      spans : Array[R]
      old_slots : Array[Int]
    }

    Assignment

    source
    pub(all) struct Assignment {
      vreg : VirtualReg
      location : Location
    } derive(Eq, 
    Debug    )

    BacktrackingAllocationAttempt

    source
    pub(all) struct BacktrackingAllocationAttempt[P, Q] {
      reg : P?
      evicted_ids : Array[Int]
      split : (Q, P)?
    }

    BacktrackingAllocationLoc

    source
    pub(all) enum BacktrackingAllocationLoc[P] {
      BacktrackingReg(P)
      BacktrackingSpill(Int)
      BacktrackingUnallocated
    }

    BacktrackingAllocationResult

    source
    pub(all) struct BacktrackingAllocationResult[P] {
      assignments : Array[(Int, P)]
      spill_slots : Array[(Int, Int)]
      num_spill_slots : Int
    }

    BacktrackingConflictScanResult

    source
    pub(all) struct BacktrackingConflictScanResult[P] {
      conflict_ids : Array[Int]
      max_conflict_weight : Int
      first_conflict_point : P?
      rejected : Bool
    }

    BacktrackingConstraintInstEdits

    source
    pub(all) struct BacktrackingConstraintInstEdits[P] {
      block_index : Int
      inst_index : Int
      before : Array[BacktrackingConstraintMove[P]]
      after : Array[BacktrackingConstraintMove[P]]
    }

    BacktrackingConstraintMove

    source
    pub(all) struct BacktrackingConstraintMove[P] {
      from : BacktrackingMoveLoc[P]
      to : BacktrackingMoveLoc[P]
      class_tag : Int
    }

    BacktrackingConstraintOperand

    source
    pub(all) enum BacktrackingConstraintOperand[P] {
      BacktrackingVirtual(BacktrackingAllocationLoc[P], Int)
      BacktrackingPhysical(P, Int)
    }

    BacktrackingFixedConstraint

    source
    pub(all) struct BacktrackingFixedConstraint[P] {
      operand : BacktrackingConstraintOperand[P]
      required : P
    }

    BacktrackingFixedConstraintInst

    source
    pub(all) struct BacktrackingFixedConstraintInst[P] {
      block_index : Int
      inst_index : Int
      uses : Array[BacktrackingFixedConstraint[P]]
      defs : Array[BacktrackingFixedConstraint[P]]
    }

    BacktrackingHintCache

    source
    type BacktrackingHintCache[P]

    BacktrackingHintCache::BacktrackingHintCache

    source
    fn[P] BacktrackingHintCache::BacktrackingHintCache(bundle_count : Int) -> BacktrackingHintCache[P]

    BacktrackingHintCache::hint

    source
    fn[P] BacktrackingHintCache::hint(self : BacktrackingHintCache[P], bundle_id : Int) -> P?

    BacktrackingHintCache::is_ready

    source
    fn[P] BacktrackingHintCache::is_ready(self : BacktrackingHintCache[P], bundle_id : Int) -> Bool

    BacktrackingHintCache::push_bundle_slot

    source
    fn[P] BacktrackingHintCache::push_bundle_slot(self : BacktrackingHintCache[P]) -> Unit

    BacktrackingHintCache::set

    source
    fn[P] BacktrackingHintCache::set(self : BacktrackingHintCache[P], bundle_id : Int, hint : P?) -> Unit

    BacktrackingMoveLoc

    source
    pub(all) enum BacktrackingMoveLoc[P] {
      BacktrackingMoveReg(P)
      BacktrackingMoveSpill(Int)
    }

    BacktrackingOccupiedSpan

    source
    pub(all) struct BacktrackingOccupiedSpan[P] {
      owner_id : Int
      span : OrderedSpan[P]
      owner_weight : Int
      owner_pinned : Bool
    }

    BacktrackingQueue

    source
    type BacktrackingQueue[P]

    BacktrackingQueue::BacktrackingQueue

    source
    fn[P] BacktrackingQueue::BacktrackingQueue(bundle_count : Int) -> BacktrackingQueue[P]

    BacktrackingQueue::clear

    source
    fn[P] BacktrackingQueue::clear(self : BacktrackingQueue[P]) -> Unit

    BacktrackingQueue::length

    source
    fn[P] BacktrackingQueue::length(self : BacktrackingQueue[P]) -> Int

    BacktrackingQueue::pop

    source

    BacktrackingQueue::push

    source
    fn[P] BacktrackingQueue::push(self : BacktrackingQueue[P], bundle_id : Int, prio : Int, hint_preg : P?) -> Unit

    BacktrackingQueue::push_bundle_slot

    source
    fn[P] BacktrackingQueue::push_bundle_slot(self : BacktrackingQueue[P]) -> Unit

    BacktrackingQueueEntry

    source
    pub(all) struct BacktrackingQueueEntry[P] {
      bundle_id : Int
      prio : Int
      hint_preg : P?
      seq : Int
    }

    BacktrackingRangeResult

    source
    pub(all) struct BacktrackingRangeResult[P] {
      vreg_id : Int
      allocation : BacktrackingAllocationLoc[P]
    }

    BacktrackingSpillsetState

    source
    type BacktrackingSpillsetState[P]

    BacktrackingSpillsetState::BacktrackingSpillsetState

    source
    fn[P] BacktrackingSpillsetState::BacktrackingSpillsetState(bundle_count : Int, max_splits_per_spillset? : Int) -> BacktrackingSpillsetState[P]

    BacktrackingSpillsetState::hint

    source
    fn[P] BacktrackingSpillsetState::hint(self : BacktrackingSpillsetState[P], spillset_id : Int) -> P?

    BacktrackingSpillsetState::push_bundle_slot

    source
    fn[P] BacktrackingSpillsetState::push_bundle_slot(self : BacktrackingSpillsetState[P]) -> Unit

    BacktrackingSpillsetState::record_hint

    source
    fn[P] BacktrackingSpillsetState::record_hint(self : BacktrackingSpillsetState[P], spillset_id : Int, hint : P) -> Unit

    BacktrackingSpillsetState::record_split

    source
    fn[P] BacktrackingSpillsetState::record_split(self : BacktrackingSpillsetState[P], spillset_id : Int) -> Unit

    BacktrackingSpillsetState::split_limit_reached

    source
    fn[P] BacktrackingSpillsetState::split_limit_reached(self : BacktrackingSpillsetState[P], spillset_id : Int) -> Bool

    BacktrackingSplitPlan

    source
    pub(all) enum BacktrackingSplitPlan {
      BacktrackingSplit(Array[Int], Array[Int])
      BacktrackingMinimal
      BacktrackingSpillWhole
    } derive(
    Debug    )

    BacktrackingSplitRange

    source
    pub(all) struct BacktrackingSplitRange[P] {
      range_id : Int
      start : P?
      end : P?
    }

    Block

    source
    pub(all) struct Block {
      id : Int
      instructions : Array[Instruction]
      successors : Array[Int]
    } derive(
    Debug    )

    Block::Block

    source
    fn Block::Block(id : Int) -> Block

    Block::add_successor

    source
    fn Block::add_successor(self : Block, block_id : Int) -> Unit

    Block::append

    source
    fn Block::append(self : Block, inst : Instruction) -> Unit

    BundleMergeEdge

    source
    pub(all) struct BundleMergeEdge {
      target : Int
      source : Int
    } derive(Eq, 
    Debug    )

    BundleMergePlan

    source
    pub(all) struct BundleMergePlan[C, R] {
      range_to_bundle : Array[Int]
      bundle_roots : Array[Int]
      bundle_classes : Array[C]
      bundle_ranges : Array[Array[R]]
    } derive(
    Debug    )

    BundleMergeRange

    source
    pub(all) struct BundleMergeRange[C, P, R] {
      id : Int
      class : C
      spans : Array[MergeSpan[R]]
      fixed_reg : P?
      has_fixed_conflict : Bool
      has_fixed_def : Bool
    } derive(
    Debug    )

    BundleSplitPlan

    source
    pub(all) enum BundleSplitPlan {
      Split(Array[Int], Array[Int])
      Minimal
      SpillWhole
    } derive(
    Debug    )

    BundleSplitRange

    source
    pub(all) struct BundleSplitRange {
      range_id : Int
      start : ProgramPoint?
      end : ProgramPoint?
    } derive(Eq, 
    Debug    )

    CompactSpillSet

    source
    pub(all) struct CompactSpillSet {
      old_slot : Int
      class : RegClass
      ranges : Array[ProgramRange]
    } derive(
    Debug    )

    ConflictScanResult

    source
    pub(all) struct ConflictScanResult {
      conflict_ids : Array[Int]
      max_conflict_weight : Int
      first_conflict_point : ProgramPoint?
      rejected : Bool
    } derive(Eq, 
    Debug    )

    DenseCfgEdges

    source
    pub(all) struct DenseCfgEdges {
      preds : Array[Array[Int]]
      succs : Array[Array[Int]]
    } derive(
    Debug    )

    DenseCfgLoop

    source
    pub(all) struct DenseCfgLoop {
      header : Int
      body : Array[Int]
      latch : Int
    } derive(
    Debug    )

    DenseLiveSets

    source
    pub(all) struct DenseLiveSets {
      live_in : Array[Array[Int]]
      live_out : Array[Array[Int]]
    } derive(
    Debug    )

    FixedConstraint

    source
    pub(all) struct FixedConstraint {
      operand : FixedConstraintOperand
      required : PhysicalReg
    } derive(Eq, 
    Debug    )

    FixedConstraintInst

    source
    pub(all) struct FixedConstraintInst {
      block_index : Int
      inst_index : Int
      uses : Array[FixedConstraint]
      defs : Array[FixedConstraint]
    } derive(
    Debug    )

    FixedConstraintInstEdits

    source
    pub(all) struct FixedConstraintInstEdits {
      block_index : Int
      inst_index : Int
      before : Array[FixedConstraintMove]
      after : Array[FixedConstraintMove]
    } derive(
    Debug    )

    FixedConstraintMove

    source
    pub(all) struct FixedConstraintMove {
      from : Location
      to : Location
      class_tag : Int
    } derive(Eq, 
    Debug    )

    FixedConstraintOperand

    source
    pub(all) enum FixedConstraintOperand {
      Virtual(Location?, Int)
      Physical(PhysicalReg, Int)
    } derive(Eq, 
    Debug    )

    Instruction

    source
    pub(all) struct Instruction {
      id : Int
      operands : Array[Operand]
      clobbers : Array[PhysicalReg]
    } derive(
    Debug    )

    Instruction::Instruction

    source
    fn Instruction::Instruction(id : Int) -> Instruction

    Instruction::add_clobber

    source
    fn Instruction::add_clobber(self : Instruction, preg : PhysicalReg) -> Unit

    Instruction::add_operand

    source
    fn Instruction::add_operand(self : Instruction, operand : Operand) -> Unit

    LiveRange

    source
    pub(all) struct LiveRange {
      id : Int
      vreg : VirtualReg
      ranges : Array[ProgramRange]
      uses : Array[UsePosition]
      bundle_id : Int
      allocation : Location?
      crosses_call : Bool
    } 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::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::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

    LiveRangeSet

    source
    pub(all) struct LiveRangeSet {
      ranges : Array[LiveRange]
      block_order : Array[Int]
    } 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::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

    LiveSetUseDef

    source
    pub(all) struct LiveSetUseDef {
      vreg_id : Int
      def_point : ProgramPoint?
      is_entry_param_def : Bool
      use_points : Array[ProgramPoint]
    } derive(
    Debug    )

    Location

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

    MergeSpan

    source
    pub(all) struct MergeSpan[R] {
      span : R
      start_ord : Int
      start_before_ord : Int
      end_ord : Int
    } derive(
    Debug    )

    OccupiedProgramSpan

    source
    pub(all) struct OccupiedProgramSpan {
      owner_id : Int
      span : OrderedProgramSpan
      owner_weight : Int
      owner_pinned : Bool
    } derive(Eq, 
    Debug    )

    Operand

    source
    pub(all) struct Operand {
      vreg : VirtualReg
      role : OperandRole
      constraint : OperandConstraint
      tie_id : Int
    } 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_tie

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

    OperandConstraint

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

    OperandRole

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

    OrderedProgramSpan

    source
    pub(all) struct OrderedProgramSpan {
      start : ProgramPoint
      start_ord : Int
      end_ord : Int
    } derive(Eq, 
    Debug    )

    OrderedSpan

    source
    pub(all) struct OrderedSpan[P] {
      start : P
      start_ord : Int
      end_ord : Int
    }

    ParallelMove

    source
    pub(all) struct ParallelMove {
      from : Location
      to : Location
      class : RegClass
    } derive(Eq, 
    Debug    )

    ParamPreassignDecision

    source
    pub(all) enum ParamPreassignDecision {
      PreassignIncoming(Bool)
      HintIncoming
      Defer
    } derive(Eq, 
    Debug    )

    PhysicalReg

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

    PriorityWorkItem

    source
    pub(all) struct PriorityWorkItem {
      item_id : Int
      priority : Int
      seq : Int
    } derive(Eq, 
    Debug    )

    PriorityWorkQueue

    source
    pub struct PriorityWorkQueue {
      items : Array[PriorityWorkItem]
      next_seq : Int
    }

    PriorityWorkQueue::PriorityWorkQueue

    source
    fn PriorityWorkQueue::PriorityWorkQueue() -> PriorityWorkQueue

    PriorityWorkQueue::length

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

    PriorityWorkQueue::pop

    source

    PriorityWorkQueue::push

    source
    fn PriorityWorkQueue::push(self : PriorityWorkQueue, item_id : Int, priority : Int) -> Unit

    Program

    source
    pub(all) struct Program {
      blocks : Array[Block]
      physical_regs : Array[PhysicalReg]
    } derive(
    Debug    )

    Program::Program

    source
    fn Program::Program(physical_regs : Array[PhysicalReg]) -> Program

    Program::add_block

    source
    fn Program::add_block(self : Program, block : Block) -> Unit

    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    )

    RegallocAlgorithm

    source
    pub(all) enum RegallocAlgorithm {
      Backtracking
      SinglePass
    }

    RegallocAlgorithm::enable_backtracking

    source
    fn RegallocAlgorithm::enable_backtracking(self : RegallocAlgorithm) -> Bool

    ReloadIntervalInfo

    source
    pub(all) struct ReloadIntervalInfo {
      block_id : Int
      spill_slot : Int
      vreg : VirtualReg
      first_inst : Int
      last_inst : Int
    } derive(Eq, 
    Debug    )

    ReloadUseInfo

    source
    pub(all) struct ReloadUseInfo {
      block_id : Int
      inst_index : Int
      spill_slot : Int
      vreg : VirtualReg
    } derive(Eq, 
    Debug    )

    RematCloneInfo

    source
    pub(all) struct RematCloneInfo {
      vreg : VirtualReg
      block_id : Int
      inst_index : Int
    } derive(Eq, 
    Debug    )

    RematDefInfo

    source
    pub(all) struct RematDefInfo {
      vreg : VirtualReg
      block_id : Int
      inst_index : Int
    } derive(Eq, 
    Debug    )

    RematLocalCloneInfo

    source
    pub(all) struct RematLocalCloneInfo {
      vreg : VirtualReg
      block_id : Int
      first_inst_index : Int
    } derive(Eq, 
    Debug    )

    RematUseInfo

    source
    pub(all) struct RematUseInfo {
      vreg : VirtualReg
      block_id : Int
      inst_index : Int
    } derive(Eq, 
    Debug    )

    SpillSetInfo

    source
    pub(all) struct SpillSetInfo[C, R, P] {
      old_slot : Int
      reg_class : C
      spans : Array[R]
      start : P
    }

    SpillSlotCompaction

    source
    pub(all) struct SpillSlotCompaction {
      remaps : Array[SpillSlotRemap]
      total_slots : Int
    } derive(Eq, 
    Debug    )

    SpillSlotNoShareEdge

    source
    pub(all) struct SpillSlotNoShareEdge {
      lhs : Int
      rhs : Int
    } derive(Eq, 
    Debug    )

    SpillSlotRemap

    source
    pub(all) struct SpillSlotRemap {
      old_slot : Int
      new_slot : Int
    } derive(Eq, 
    Debug    )

    SpillSlotReservation

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

    StackFrame

    source
    pub(all) struct StackFrame {
      slots : Array[StackSlot]
      frame_size : Int
      frame_align : Int
      next_spill_offset : Int
      next_arg_offset : Int
      callee_saved_regs : Array[PhysicalReg]
    }

    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 : PhysicalReg) -> Int

    StackFrame::alloc_local

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

    StackFrame::alloc_outgoing_arg

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

    StackFrame::alloc_spill_slot

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

    StackFrame::finalize

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

    StackFrame::get_callee_saved

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

    StackFrame::print

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

    StackFrame::size

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

    StackSlot

    source
    pub(all) struct StackSlot {
      offset : Int
      size : Int
      align : Int
      kind : StackSlotKind
    } derive(Eq, 
    Debug    )

    impl Show for StackSlot

    StackSlotKind

    source
    pub(all) enum StackSlotKind {
      Spill(VirtualReg)
      Local(Int)
      OutgoingArg(Int)
      CalleeSaved(PhysicalReg)
    } derive(Eq, 
    Debug    )

    TempRegisterChoice

    source
    pub(all) struct TempRegisterChoice {
      preg : PhysicalReg
      next_cursor : Int
      save_slot : Int?
      next_spill_slot : Int
    } derive(Eq, 
    Debug    )

    ThreadArg

    source
    pub(all) enum ThreadArg {
      PhysicalArg(Int, Int)
      VirtualArg(Int, Int)
    } derive(Eq, 
    Debug    )

    ThreadBlock

    source
    pub(all) struct ThreadBlock {
      id : Int
      params : Array[Int]
      target : Int?
      target_args : Array[ThreadArg]
      is_empty : Bool
    } derive(
    Debug    )

    ThreadedJump

    source
    pub(all) struct ThreadedJump {
      target : Int
      args : Array[ThreadArg]
      changed : Bool
    } derive(
    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
      tie_id : Int
    } derive(Eq, 
    Debug    )

    UsePosition::UsePosition

    source
    fn UsePosition::UsePosition(point : ProgramPoint, kind : UseKind, constraint : OperandConstraint) -> 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_linear_scan

    source
    fn allocate_linear_scan(program : Program) -> Allocation

    Allocate virtual registers over the small abstract Program model using a linear-scan allocator.

    This is the simple allocator for examples and model-level tests. Production embedding pipelines should use the backtracking_* APIs in this package through an adapter such as machv_regalloc.

    TODO(regalloc): add interval splitting, bundle coalescing, rematerialization, and target-provided spill-cost modeling.

    allocation_iteration_limit

    source
    fn allocation_iteration_limit(bundle_count : Int) -> Int

    backtracking_queue_entry_higher

    source
    fn[P] backtracking_queue_entry_higher(a : BacktrackingQueueEntry[P], b : BacktrackingQueueEntry[P]) -> Bool

    build_backtracking_allocation_result

    source
    fn[P] build_backtracking_allocation_result(ranges : Array[BacktrackingRangeResult[P]], num_spill_slots : Int) -> BacktrackingAllocationResult[P]

    build_dense_successor_edges

    source
    fn build_dense_successor_edges(block_ids : Array[Int], block_successor_ids : Array[Array[Int]]) -> DenseCfgEdges

    build_live_ranges

    source
    fn build_live_ranges(program : Program) -> LiveRangeSet

    choose_fixed_reg_hint

    source
    fn choose_fixed_reg_hint(available_regs : Array[PhysicalReg], fixed_regs : Array[PhysicalReg]) -> PhysicalReg?

    choose_temp_register

    source
    fn choose_temp_register(class : RegClass, used_ids : Array[Int], temp_pool : Array[Int], fallback_candidates : Array[Int], reserved_ids : Array[Int], need_preserve : Bool, cursor : Int, next_spill_slot : Int) -> TempRegisterChoice

    compact_backtracking_spill_slots

    source
    fn[C, R, P] compact_backtracking_spill_slots(spillsets : Array[SpillSetInfo[C, R, P]], no_share_edges : Array[SpillSlotNoShareEdge], reserve_slot : (Int, C) -> SpillSlotReservation, ranges_overlap : (Array[R], Array[R]) -> Bool, compare_start : (P, P) -> Int) -> SpillSlotCompaction

    compact_spill_slots

    source
    fn compact_spill_slots(spillsets : Array[CompactSpillSet], no_share_edges : Array[SpillSlotNoShareEdge], block_order : Array[Int]) -> SpillSlotCompaction

    compute_approx_loop_depths

    source
    fn compute_approx_loop_depths(block_successors : Array[Array[Int]]) -> Array[Int]

    Compute an approximate loop depth for each block from a linear block order and per-block successor lists.

    This mirrors the regalloc2-style CFG heuristic used for spill weighting: a successor whose index is not greater than the current block is treated as a backedge, and depths are approximated by scanning block order while tracking entered/exited backedges.

    compute_block_point_bases

    source
    fn compute_block_point_bases(block_order : Array[Int], block_lengths : Array[Int]) -> Array[Int]

    compute_dense_live_sets

    source
    fn compute_dense_live_sets(num_blocks : Int, num_vregs : Int, cfg : DenseCfgEdges, use_defs : Array[LiveSetUseDef]) -> DenseLiveSets

    compute_dominators_from_edges

    source
    fn compute_dominators_from_edges(edges : DenseCfgEdges) -> Array[Int]

    compute_reachable_reverse_postorder_from_successors

    source
    fn compute_reachable_reverse_postorder_from_successors(block_successors : Array[Array[Int]]) -> Array[Int]

    compute_reload_intervals

    source
    fn compute_reload_intervals(uses : Array[ReloadUseInfo], allow_vector? : Bool) -> Array[ReloadIntervalInfo]

    Compute block-local reload intervals for spill slots used more than once.

    The logic is intentionally independent of any machine IR. Callers project their spilled operand uses into ReloadUseInfo, and target adapters decide later which physical registers can hold each interval.

    compute_reverse_postorder_from_successors

    source
    fn compute_reverse_postorder_from_successors(block_successors : Array[Array[Int]]) -> Array[Int]

    Compute reverse-postorder block ranks from dense successor lists.

    The returned array maps block_index -> reverse_postorder_rank.

    compute_spill_weight

    source
    fn compute_spill_weight(uses : Array[UsePosition], loop_depths : Array[Int]) -> Int

    count_sorted_ints_in_open_range

    source
    fn count_sorted_ints_in_open_range(values : Array[Int], start : Int, end : Int) -> Int

    eviction_cutoff

    source
    fn eviction_cutoff(best_conflict_cost : Int?, best_split_cost : Int?) -> Int?

    find_back_edges_from_edges

    source
    fn find_back_edges_from_edges(edges : DenseCfgEdges) -> Array[(Int, Int)]

    find_loops_from_edges

    source
    fn find_loops_from_edges(edges : DenseCfgEdges) -> Array[DenseCfgLoop]

    has_backtracking_span_conflict

    source
    fn[P] has_backtracking_span_conflict(spans : Array[OrderedSpan[P]], occupied : Array[(Int, OrderedSpan[P])]) -> Bool

    has_ordered_span_conflict

    source
    fn has_ordered_span_conflict(spans : Array[OrderedProgramSpan], occupied : Array[OrderedProgramSpan]) -> Bool

    insert_allocated_spans

    source
    fn insert_allocated_spans(occupied : Array[AllocatedProgramSpan], owner_id : Int, spans : Array[OrderedProgramSpan]) -> Array[AllocatedProgramSpan]

    lower_bound_backtracking_span_by_end

    source
    fn[P] lower_bound_backtracking_span_by_end(occupied : Array[(Int, OrderedSpan[P])], point_ord : Int) -> Int

    lower_bound_ordered_span_by_end

    source
    fn lower_bound_ordered_span_by_end(spans : Array[OrderedProgramSpan], point_ord : Int) -> Int

    lower_bound_sorted_int

    source
    fn lower_bound_sorted_int(values : Array[Int], target : Int) -> Int

    make_backtracking_alloc_table

    source
    fn[P] make_backtracking_alloc_table(cap : Int) -> Array[Array[(Int, OrderedSpan[P])]]

    make_backtracking_bool_table

    source
    fn make_backtracking_bool_table(cap : Int) -> Array[Bool]

    max_physical_reg_id

    source
    fn max_physical_reg_id(regs : Array[PhysicalReg]) -> Int

    plan_backtracking_bundle_split

    source
    fn[P] plan_backtracking_bundle_split(ranges : Array[BacktrackingSplitRange[P]], split_point : P?, split_limit_reached : Bool, end_before_or_at_split : (P, P) -> Bool, start_after_or_at_split : (P, P) -> Bool) -> BacktrackingSplitPlan

    plan_backtracking_fixed_constraint_edits

    source
    fn[P] plan_backtracking_fixed_constraint_edits(insts : Array[BacktrackingFixedConstraintInst[P]], same_reg : (P, P) -> Bool) -> Array[BacktrackingConstraintInstEdits[P]]

    plan_backtracking_probe_order

    source
    fn[P] plan_backtracking_probe_order(available_regs : Array[P], caller_saved_regs : Array[P], callee_saved_regs : Array[P], prefer_caller_saved : Bool, scan_limit : Int, offset : Int, skip_reg : P?, same_reg : (P, P) -> Bool) -> Array[P]

    plan_bundle_merges

    source
    fn[C, P, R] plan_bundle_merges(ranges : Array[BundleMergeRange[C, P, R]], edges : Array[BundleMergeEdge], class_compatible : (C, C) -> Bool, same_fixed_reg : (P, P) -> Bool) -> BundleMergePlan[C, R]

    plan_bundle_split

    source
    fn plan_bundle_split(ranges : Array[BundleSplitRange], split_point : ProgramPoint?, block_order : Array[Int], spillset_split_count : Int, max_splits_per_spillset : Int) -> BundleSplitPlan

    plan_cross_block_rematerializations

    source
    fn plan_cross_block_rematerializations(defs : Array[RematDefInfo], uses : Array[RematUseInfo]) -> Array[RematLocalCloneInfo]

    plan_fixed_constraint_edits

    source
    fn plan_fixed_constraint_edits(insts : Array[FixedConstraintInst]) -> Array[FixedConstraintInstEdits]

    plan_long_distance_rematerializations

    source
    fn plan_long_distance_rematerializations(defs : Array[RematDefInfo], uses : Array[RematUseInfo], min_distance? : Int, per_vreg_clone_cap? : Int) -> Array[RematCloneInfo]

    plan_param_preassignment

    source
    fn plan_param_preassignment(strict_precolor : Bool, is_pinned_special_param : Bool, crosses_call : Bool) -> ParamPreassignDecision

    plan_register_probe_order

    source
    fn plan_register_probe_order(available_regs : Array[PhysicalReg], caller_saved_regs : Array[PhysicalReg], callee_saved_regs : Array[PhysicalReg], prefer_caller_saved : Bool, scan_limit : Int, offset : Int, skip_reg : PhysicalReg?) -> Array[PhysicalReg]

    plan_temp_register_pool

    source
    fn plan_temp_register_pool(used : Array[Bool], scratch : Array[Int], nonpreferred : Array[Int], preferred : Array[Int]) -> Array[Int]

    raise_scratch_register_unavailable

    source
    fn raise_scratch_register_unavailable(message~ : String) -> Unit raise VerifyError

    remove_allocated_spans

    source
    fn remove_allocated_spans(occupied : Array[AllocatedProgramSpan], owner_id : Int) -> Array[AllocatedProgramSpan]

    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.

    resolve_parallel_moves

    source
    fn resolve_parallel_moves(moves : Array[ParallelMove], scratch_int : Array[PhysicalReg], scratch_float : Array[PhysicalReg]) -> Array[ParallelMove]

    resolve_threaded_jump

    source
    fn resolve_threaded_jump(blocks : Array[ThreadBlock], start_target : Int, start_args : Array[ThreadArg]) -> ThreadedJump

    Resolve a jump target through chains of empty jump-only blocks.

    A block can be threaded when it is empty, jumps to another block, and its jump arguments can be expressed as forwarding this block's parameters.

    run_backtracking_allocation_loop

    source
    fn[B, R, P] run_backtracking_allocation_loop(queue : BacktrackingQueue[R], bundle_attempts : Array[Int], bundle_retry_limit : Int, enable_backtracking : Bool, bundle_count : Int, get_bundle : (Int) -> B, bundle_done : (B) -> Bool, bundle_is_pinned : (B) -> Bool, bundle_has_fixed_constraint : (B) -> Bool, bundle_must_force_spill : (B) -> Bool, hint_for_bundle : (B, R?) -> R?, try_backtracking : (B, R?) -> (R?, (P, R)?), try_single_pass : (B, R?) -> R?, record_allocation : (B, R) -> Unit, split_bundle : (B, (P, R)?) -> Unit, force_spill : (B) -> Unit) -> Unit

    scan_backtracking_conflicts_with_cutoff

    source
    fn[P] scan_backtracking_conflicts_with_cutoff(spans : Array[OrderedSpan[P]], occupied : Array[BacktrackingOccupiedSpan[P]], current_weight : Int, max_allowable_cost : Int?) -> BacktrackingConflictScanResult[P]

    scan_conflicts_with_cutoff

    source
    fn scan_conflicts_with_cutoff(spans : Array[OrderedProgramSpan], occupied : Array[OccupiedProgramSpan], current_weight : Int, max_allowable_cost : Int?) -> ConflictScanResult

    select_available_regs_for_bundle

    source
    fn select_available_regs_for_bundle(class : RegClass, crosses_call : Bool, available_regs : Array[PhysicalReg], callee_saved_regs : Array[PhysicalReg]) -> Array[PhysicalReg]

    select_caller_saved_regs

    source
    fn select_caller_saved_regs(allocatable_regs : Array[PhysicalReg], callee_saved_regs : Array[PhysicalReg]) -> Array[PhysicalReg]

    should_force_spill_after_retry

    source
    fn should_force_spill_after_retry(attempts : Int, retry_limit : Int, is_pinned : Bool, has_fixed_constraint : Bool) -> Bool

    should_force_spill_for_class_and_call

    source
    fn should_force_spill_for_class_and_call(class : RegClass, crosses_call : Bool) -> Bool

    should_prefer_caller_saved_for_backtracking

    source
    fn should_prefer_caller_saved_for_backtracking(class : RegClass, enable_backtracking : Bool, crosses_call : Bool) -> Bool

    should_take_backtracking_split_candidate

    source
    fn[P] should_take_backtracking_split_candidate(best_split_cost : Int?, best_split_point : P?, candidate_cost : Int, candidate_point : P, compare_points : (P, P) -> Int) -> Bool

    should_take_eviction_candidate

    source
    fn should_take_eviction_candidate(best_conflict_cost : Int?, best_preg : PhysicalReg?, candidate_cost : Int, candidate_preg : PhysicalReg, hint_preg : PhysicalReg?) -> Bool

    should_take_split_candidate

    source
    fn should_take_split_candidate(best_split_cost : Int?, best_split_point : ProgramPoint?, candidate_cost : Int, candidate_point : ProgramPoint, block_order : Array[Int]) -> Bool

    try_backtracking_eviction_register

    source
    fn[P, Q] try_backtracking_eviction_register(available_regs : Array[P], caller_saved_regs : Array[P], callee_saved_regs : Array[P], spans : Array[OrderedSpan[Q]], current_weight : Int, hint_reg : P?, prefer_caller_saved : Bool, scan_limit : Int, offset : Int, same_reg : (P, P) -> Bool, to_policy_reg : (P) -> PhysicalReg, occupied_for_reg : (P) -> Array[BacktrackingOccupiedSpan[Q]], compare_points : (Q, Q) -> Int) -> BacktrackingAllocationAttempt[P, Q]

    try_backtracking_single_pass_register

    source
    fn[P, Q] try_backtracking_single_pass_register(available_regs : Array[P], caller_saved_regs : Array[P], callee_saved_regs : Array[P], spans : Array[OrderedSpan[Q]], hint_reg : P?, prefer_caller_saved : Bool, scan_limit : Int, offset : Int, same_reg : (P, P) -> Bool, has_conflict_on_reg : (P, Array[OrderedSpan[Q]]) -> Bool) -> P?

    upper_bound_sorted_int

    source
    fn upper_bound_sorted_int(values : Array[Int], target : Int) -> Int

    verify_allocation

    source
    fn verify_allocation(program : Program, allocation : Allocation) -> Unit raise VerifyError

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io