use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;
use llvm_native_core::codegen_ra_greedy::{
AssignStrategy, EvictionChain, EvictionCostComputer, GreedyAllocStats, MultiWayEviction,
ProgramRegion, RegionSplitter, RegisterAssignmentStrategy, RematSource, RematerializationInfo,
SpillWeightComputer, SplitKit, SplitPoint,
};
use llvm_native_core::codegen_regalloc::{
InstrPoint, LinearLiveInterval, LinearLiveSegment, LinearScanAllocator, LinearScanStats,
PbqpCost, PbqpEdge, PbqpGraph, PbqpMatrix, PbqpNode, PbqpSolution, PbqpSolver, PbqpVector,
ReductionData, ReductionKind, RegClassKind, PBQP_INF,
};
use llvm_native_core::x86::{
x86_calling_convention::{X86ArgClass, X86ArgInfo, X86CallFrame, X86CallingConvention},
x86_frame_lowering::X86FrameLowering,
x86_instr_info::{
OperandType, X86InstrDesc, X86InstrInfo, X86MemOperand, X86Opcode, X86Operand, X86SchedInfo,
},
x86_register_info::{RegClass, X86Reg, TOTAL_REG_COUNT},
X86RegisterInfo, X86Subtarget, X86TargetMachine,
};
pub mod x86_reg {
pub const RAX: u32 = 0;
pub const RCX: u32 = 1;
pub const RDX: u32 = 2;
pub const RBX: u32 = 3;
pub const RSP: u32 = 4;
pub const RBP: u32 = 5;
pub const RSI: u32 = 6;
pub const RDI: u32 = 7;
pub const R8: u32 = 8;
pub const R9: u32 = 9;
pub const R10: u32 = 10;
pub const R11: u32 = 11;
pub const R12: u32 = 12;
pub const R13: u32 = 13;
pub const R14: u32 = 14;
pub const R15: u32 = 15;
pub const EAX: u32 = 100;
pub const ECX: u32 = 101;
pub const EDX: u32 = 102;
pub const EBX: u32 = 103;
pub const ESP: u32 = 104;
pub const EBP: u32 = 105;
pub const ESI: u32 = 106;
pub const EDI: u32 = 107;
pub const R8D: u32 = 108;
pub const R9D: u32 = 109;
pub const R10D: u32 = 110;
pub const R11D: u32 = 111;
pub const R12D: u32 = 112;
pub const R13D: u32 = 113;
pub const R14D: u32 = 114;
pub const R15D: u32 = 115;
pub const XMM0: u32 = 200;
pub const XMM1: u32 = 201;
pub const XMM2: u32 = 202;
pub const XMM3: u32 = 203;
pub const XMM4: u32 = 204;
pub const XMM5: u32 = 205;
pub const XMM6: u32 = 206;
pub const XMM7: u32 = 207;
pub const XMM8: u32 = 208;
pub const XMM9: u32 = 209;
pub const XMM10: u32 = 210;
pub const XMM11: u32 = 211;
pub const XMM12: u32 = 212;
pub const XMM13: u32 = 213;
pub const XMM14: u32 = 214;
pub const XMM15: u32 = 215;
pub const XMM16: u32 = 216;
pub const XMM17: u32 = 217;
pub const XMM18: u32 = 218;
pub const XMM19: u32 = 219;
pub const XMM20: u32 = 220;
pub const XMM21: u32 = 221;
pub const XMM22: u32 = 222;
pub const XMM23: u32 = 223;
pub const XMM24: u32 = 224;
pub const XMM25: u32 = 225;
pub const XMM26: u32 = 226;
pub const XMM27: u32 = 227;
pub const XMM28: u32 = 228;
pub const XMM29: u32 = 229;
pub const XMM30: u32 = 230;
pub const XMM31: u32 = 231;
pub const YMM0: u32 = 300;
pub const YMM1: u32 = 301;
pub const YMM2: u32 = 302;
pub const YMM3: u32 = 303;
pub const YMM4: u32 = 304;
pub const YMM5: u32 = 305;
pub const YMM6: u32 = 306;
pub const YMM7: u32 = 307;
pub const YMM8: u32 = 308;
pub const YMM15: u32 = 315;
pub const ZMM0: u32 = 400;
pub const ZMM15: u32 = 415;
pub const ZMM31: u32 = 431;
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct X86RegMask(u128);
impl X86RegMask {
pub const EMPTY: Self = X86RegMask(0);
pub const ALL: Self = X86RegMask(u128::MAX);
pub fn new() -> Self {
X86RegMask(0)
}
pub fn from_reg(reg: u32) -> Self {
let mut mask = X86RegMask(0);
mask.set(reg);
mask
}
pub fn set(&mut self, reg: u32) {
if reg < 128 {
self.0 |= 1u128 << (reg as u128);
}
}
pub fn clear(&mut self, reg: u32) {
if reg < 128 {
self.0 &= !(1u128 << (reg as u128));
}
}
pub fn contains(&self, reg: u32) -> bool {
reg < 128 && (self.0 & (1u128 << (reg as u128))) != 0
}
pub fn is_empty(&self) -> bool {
self.0 == 0
}
pub fn count(&self) -> u32 {
self.0.count_ones()
}
pub fn union_with(&self, other: &X86RegMask) -> X86RegMask {
X86RegMask(self.0 | other.0)
}
pub fn intersect(&self, other: &X86RegMask) -> X86RegMask {
X86RegMask(self.0 & other.0)
}
pub fn subtract(&self, other: &X86RegMask) -> X86RegMask {
X86RegMask(self.0 & !other.0)
}
pub fn iter(&self) -> X86RegMaskIter {
X86RegMaskIter {
mask: *self,
pos: 0,
}
}
}
pub struct X86RegMaskIter {
mask: X86RegMask,
pos: u32,
}
impl Iterator for X86RegMaskIter {
type Item = u32;
fn next(&mut self) -> Option<u32> {
while self.pos < 128 {
if self.mask.contains(self.pos) {
let r = self.pos;
self.pos += 1;
return Some(r);
}
self.pos += 1;
}
None
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86RegClass {
GPR8,
GPR16,
GPR32,
GPR64,
VECTOR128,
VECTOR256,
VECTOR512,
GPR8H,
FLAGS,
}
impl X86RegClass {
pub fn name(&self) -> &'static str {
match self {
X86RegClass::GPR8 => "GPR8",
X86RegClass::GPR16 => "GPR16",
X86RegClass::GPR32 => "GPR32",
X86RegClass::GPR64 => "GPR64",
X86RegClass::VECTOR128 => "VR128",
X86RegClass::VECTOR256 => "VR256",
X86RegClass::VECTOR512 => "VR512",
X86RegClass::GPR8H => "GPR8H",
X86RegClass::FLAGS => "FLAGS",
}
}
pub fn width(&self) -> u32 {
match self {
X86RegClass::GPR8 | X86RegClass::GPR8H => 8,
X86RegClass::GPR16 => 16,
X86RegClass::GPR32 => 32,
X86RegClass::GPR64 => 64,
X86RegClass::VECTOR128 => 128,
X86RegClass::VECTOR256 => 256,
X86RegClass::VECTOR512 => 512,
X86RegClass::FLAGS => 64,
}
}
pub fn allocatable_regs(&self) -> Vec<u32> {
match self {
X86RegClass::GPR8 => (0..16).filter(|r| *r != 4 && *r != 5).collect(),
X86RegClass::GPR8H => vec![0, 1, 2, 3],
X86RegClass::GPR16 => (0..16).filter(|r| *r != 4 && *r != 5).collect(),
X86RegClass::GPR32 => (100..116).filter(|r| *r != 104 && *r != 105).collect(),
X86RegClass::GPR64 => (0..16).filter(|r| *r != 4 && *r != 5).collect(),
X86RegClass::VECTOR128 => (200..232).collect(),
X86RegClass::VECTOR256 => (300..316).collect(),
X86RegClass::VECTOR512 => (400..432).collect(),
X86RegClass::FLAGS => vec![],
}
}
pub fn from_vreg(vreg: u32) -> Self {
match vreg {
0..=99 => X86RegClass::GPR64,
100..=199 => X86RegClass::GPR32,
200..=299 => X86RegClass::VECTOR128,
300..=399 => X86RegClass::VECTOR256,
400..=499 => X86RegClass::VECTOR512,
_ => X86RegClass::GPR64,
}
}
pub fn from_reg_class_kind(kind: RegClassKind) -> Self {
match kind {
RegClassKind::GPR => X86RegClass::GPR64,
RegClassKind::FPR32 => X86RegClass::VECTOR128,
RegClassKind::FPR64 => X86RegClass::VECTOR256,
RegClassKind::VecReg => X86RegClass::VECTOR512,
}
}
}
#[derive(Debug, Clone)]
pub struct X86LiveIntervals {
pub intervals: HashMap<u32, X86LiveInterval>,
pub block_liveness: HashMap<u32, BTreeSet<u32>>,
pub subreg_uses: HashMap<u32, HashMap<u8, Vec<InstrPoint>>>,
pub subreg_defs: HashMap<u32, HashMap<u8, Vec<InstrPoint>>>,
pub loop_depths: HashMap<u32, u32>,
pub computed: bool,
pub interval_count: usize,
pub subreg_count: usize,
}
#[derive(Debug, Clone)]
pub struct X86LiveInterval {
pub vreg: u32,
pub reg_class: X86RegClass,
pub segments: Vec<X86LiveSegment>,
pub use_points: Vec<InstrPoint>,
pub def_points: Vec<InstrPoint>,
pub assigned_reg: Option<u32>,
pub spilled: bool,
pub spill_offset: i32,
pub reg_hint: Option<u32>,
pub is_fixed: bool,
pub fixed_reg: Option<u32>,
pub spill_weight: f64,
pub rematerializable: bool,
pub subreg_liveness: u64,
pub lane_mask: u64,
pub parent: Option<u32>,
pub children: Vec<u32>,
}
#[derive(Debug, Clone, Copy)]
pub struct X86LiveSegment {
pub start: InstrPoint,
pub end: InstrPoint,
pub subreg_mask: u64,
}
impl X86LiveSegment {
pub fn new(start: InstrPoint, end: InstrPoint) -> Self {
Self {
start,
end,
subreg_mask: u64::MAX,
}
}
pub fn with_subreg_mask(start: InstrPoint, end: InstrPoint, mask: u64) -> Self {
Self {
start,
end,
subreg_mask: mask,
}
}
pub fn contains(&self, point: InstrPoint) -> bool {
self.start <= point && point <= self.end
}
pub fn overlaps(&self, other: &X86LiveSegment) -> bool {
self.start <= other.end && other.start <= self.end
}
pub fn length(&self) -> u32 {
(self.end.block - self.start.block) * 1000 + (self.end.instr - self.start.instr)
}
}
impl X86LiveInterval {
pub fn new(vreg: u32, reg_class: X86RegClass) -> Self {
Self {
vreg,
reg_class,
segments: Vec::new(),
use_points: Vec::new(),
def_points: Vec::new(),
assigned_reg: None,
spilled: false,
spill_offset: -1,
reg_hint: None,
is_fixed: false,
fixed_reg: None,
spill_weight: 0.0,
rematerializable: false,
subreg_liveness: 0,
lane_mask: u64::MAX,
parent: None,
children: Vec::new(),
}
}
pub fn from_fixed(vreg: u32, phys_reg: u32, reg_class: X86RegClass) -> Self {
Self {
vreg,
reg_class,
segments: Vec::new(),
use_points: Vec::new(),
def_points: Vec::new(),
assigned_reg: Some(phys_reg),
spilled: false,
spill_offset: -1,
reg_hint: None,
is_fixed: true,
fixed_reg: Some(phys_reg),
spill_weight: f64::MAX,
rematerializable: false,
subreg_liveness: 0,
lane_mask: u64::MAX,
parent: None,
children: Vec::new(),
}
}
pub fn add_use(&mut self, point: InstrPoint) {
if !self.use_points.contains(&point) {
self.use_points.push(point);
}
self.extend_to_cover(point);
}
pub fn add_def(&mut self, point: InstrPoint) {
if !self.def_points.contains(&point) {
self.def_points.push(point);
}
self.extend_to_cover(point);
}
pub fn add_segment(&mut self, start: InstrPoint, end: InstrPoint) {
self.segments.push(X86LiveSegment::new(start, end));
}
pub fn add_segment_with_mask(&mut self, start: InstrPoint, end: InstrPoint, mask: u64) {
self.segments
.push(X86LiveSegment::with_subreg_mask(start, end, mask));
}
fn extend_to_cover(&mut self, point: InstrPoint) {
if self.segments.is_empty() {
self.segments.push(X86LiveSegment::new(point, point));
return;
}
let last = self.segments.last_mut().unwrap();
if point > last.end {
last.end = point;
} else if point < last.start {
last.start = point;
}
}
pub fn start_point(&self) -> Option<InstrPoint> {
self.segments.first().map(|s| s.start)
}
pub fn end_point(&self) -> Option<InstrPoint> {
self.segments.last().map(|s| s.end)
}
pub fn overlaps_with(&self, other: &X86LiveInterval) -> bool {
for seg_a in &self.segments {
for seg_b in &other.segments {
if seg_a.overlaps(seg_b) {
return true;
}
}
}
false
}
pub fn contains_point(&self, point: InstrPoint) -> bool {
self.segments.iter().any(|s| s.contains(point))
}
pub fn first_use_after(&self, point: InstrPoint) -> Option<InstrPoint> {
self.use_points
.iter()
.filter(|&&u| u >= point)
.min()
.copied()
}
pub fn last_use_before(&self, point: InstrPoint) -> Option<InstrPoint> {
self.use_points
.iter()
.filter(|&&u| u <= point)
.max()
.copied()
}
pub fn set_hint(&mut self, phys_reg: u32) {
self.reg_hint = Some(phys_reg);
}
pub fn sort_and_merge(&mut self) {
self.segments.sort_by_key(|s| s.start);
let mut merged: Vec<X86LiveSegment> = Vec::new();
for seg in self.segments.drain(..) {
if let Some(last) = merged.last_mut() {
if seg.start <= last.end || seg.start == last.end.after() {
if seg.end > last.end {
last.end = seg.end;
}
last.subreg_mask |= seg.subreg_mask;
continue;
}
}
merged.push(seg);
}
self.segments = merged;
}
pub fn split_at(&self, point: InstrPoint) -> Option<(X86LiveInterval, X86LiveInterval)> {
let mut before = X86LiveInterval::new(self.vreg, self.reg_class);
let mut after = X86LiveInterval::new(self.vreg | 0x8000_0000, self.reg_class);
after.parent = Some(self.vreg);
for seg in &self.segments {
if seg.end <= point {
before.segments.push(*seg);
} else if seg.start >= point {
after.segments.push(*seg);
} else {
before
.segments
.push(X86LiveSegment::new(seg.start, point.before()));
after.segments.push(X86LiveSegment::new(point, seg.end));
}
}
for &u in &self.use_points {
if u < point {
before.use_points.push(u);
} else {
after.use_points.push(u);
}
}
for &d in &self.def_points {
if d < point {
before.def_points.push(d);
} else {
after.def_points.push(d);
}
}
before.spill_weight = self.spill_weight;
after.spill_weight = self.spill_weight;
before.reg_hint = self.reg_hint;
after.reg_hint = self.reg_hint;
before.sort_and_merge();
after.sort_and_merge();
if before.segments.is_empty() || after.segments.is_empty() {
None
} else {
Some((before, after))
}
}
pub fn union_with(&self, other: &X86LiveInterval) -> X86LiveInterval {
let mut result = self.clone();
for seg in &other.segments {
result.segments.push(*seg);
}
for &u in &other.use_points {
if !result.use_points.contains(&u) {
result.use_points.push(u);
}
}
for &d in &other.def_points {
if !result.def_points.contains(&d) {
result.def_points.push(d);
}
}
result.sort_and_merge();
result
}
pub fn intersect_with(&self, other: &X86LiveInterval) -> Vec<X86LiveSegment> {
let mut result = Vec::new();
for seg_a in &self.segments {
for seg_b in &other.segments {
if seg_a.overlaps(seg_b) {
let start = if seg_a.start > seg_b.start {
seg_a.start
} else {
seg_b.start
};
let end = if seg_a.end < seg_b.end {
seg_a.end
} else {
seg_b.end
};
result.push(X86LiveSegment::new(start, end));
}
}
}
result
}
pub fn subreg_live_at(&self, _point: InstrPoint, mask: u64) -> bool {
(self.subreg_liveness & mask) != 0
}
}
impl X86LiveIntervals {
pub fn new() -> Self {
Self {
intervals: HashMap::new(),
block_liveness: HashMap::new(),
subreg_uses: HashMap::new(),
subreg_defs: HashMap::new(),
loop_depths: HashMap::new(),
computed: false,
interval_count: 0,
subreg_count: 0,
}
}
pub fn compute_intervals(
&mut self,
defs: &HashMap<u32, Vec<InstrPoint>>,
uses: &HashMap<u32, Vec<InstrPoint>>,
block_order: &[u32],
) {
self.intervals.clear();
let mut all_vregs: HashSet<u32> = defs.keys().copied().collect();
all_vregs.extend(uses.keys().copied());
for vreg in all_vregs {
let mut interval = X86LiveInterval::new(vreg, X86RegClass::from_vreg(vreg));
if let Some(dps) = defs.get(&vreg) {
for &d in dps {
interval.add_def(d);
}
}
if let Some(ups) = uses.get(&vreg) {
for &u in ups {
interval.add_use(u);
}
}
if !interval.segments.is_empty() {
interval.sort_and_merge();
}
self.intervals.insert(vreg, interval);
}
self.compute_block_liveness(defs, uses, block_order);
self.interval_count = self.intervals.len();
self.computed = true;
}
fn compute_block_liveness(
&mut self,
defs: &HashMap<u32, Vec<InstrPoint>>,
uses: &HashMap<u32, Vec<InstrPoint>>,
block_order: &[u32],
) {
let mut block_uses: HashMap<u32, HashSet<u32>> = HashMap::new();
let mut block_defs: HashMap<u32, HashSet<u32>> = HashMap::new();
for (&vreg, pts) in uses {
for pt in pts {
block_uses.entry(pt.block).or_default().insert(vreg);
}
}
for (&vreg, pts) in defs {
for pt in pts {
block_defs.entry(pt.block).or_default().insert(vreg);
}
}
let mut live_out: HashMap<u32, HashSet<u32>> = HashMap::new();
let mut changed = true;
while changed {
changed = false;
for &block in block_order.iter().rev() {
let uses_set = block_uses.get(&block).cloned().unwrap_or_default();
let defs_set = block_defs.get(&block).cloned().unwrap_or_default();
let prev = live_out.get(&block).cloned().unwrap_or_default();
let mut new_live_out: HashSet<u32> = prev.clone();
new_live_out.extend(&uses_set);
for d in &defs_set {
new_live_out.remove(d);
}
if new_live_out != prev {
live_out.insert(block, new_live_out);
changed = true;
}
}
}
for (block, regs) in live_out {
self.block_liveness
.insert(block, regs.into_iter().collect());
}
}
pub fn track_subregister(
&mut self,
vreg: u32,
subreg: u8,
def_point: Option<InstrPoint>,
use_point: Option<InstrPoint>,
) {
if let Some(dp) = def_point {
self.subreg_defs
.entry(vreg)
.or_default()
.entry(subreg)
.or_default()
.push(dp);
}
if let Some(up) = use_point {
self.subreg_uses
.entry(vreg)
.or_default()
.entry(subreg)
.or_default()
.push(up);
}
self.subreg_count += 1;
}
pub fn set_loop_depth(&mut self, block: u32, depth: u32) {
self.loop_depths.insert(block, depth);
}
pub fn loop_depth_at(&self, point: InstrPoint) -> u32 {
self.loop_depths.get(&point.block).copied().unwrap_or(0)
}
pub fn get(&self, vreg: u32) -> Option<&X86LiveInterval> {
self.intervals.get(&vreg)
}
pub fn get_mut(&mut self, vreg: u32) -> Option<&mut X86LiveInterval> {
self.intervals.get_mut(&vreg)
}
pub fn to_linear_interval(&self, vreg: u32) -> Option<LinearLiveInterval> {
let x86_iv = self.intervals.get(&vreg)?;
let mut linear = LinearLiveInterval::new(
vreg,
match x86_iv.reg_class {
X86RegClass::GPR8
| X86RegClass::GPR16
| X86RegClass::GPR32
| X86RegClass::GPR64
| X86RegClass::GPR8H => RegClassKind::GPR,
X86RegClass::VECTOR128 => RegClassKind::FPR32,
X86RegClass::VECTOR256 => RegClassKind::FPR64,
X86RegClass::VECTOR512 => RegClassKind::VecReg,
X86RegClass::FLAGS => RegClassKind::GPR,
},
);
for seg in &x86_iv.segments {
linear.add_segment(seg.start, seg.end);
}
for &u in &x86_iv.use_points {
linear.add_use(u);
}
for &d in &x86_iv.def_points {
linear.add_def(d);
}
linear.assigned_reg = x86_iv.assigned_reg;
linear.spilled = x86_iv.spilled;
linear.spill_offset = x86_iv.spill_offset;
linear.reg_hint = x86_iv.reg_hint;
linear.is_fixed = x86_iv.is_fixed;
linear.fixed_reg = x86_iv.fixed_reg;
linear.spill_weight = x86_iv.spill_weight;
linear.rematerializable = x86_iv.rematerializable;
Some(linear)
}
pub fn summary(&self) -> String {
format!(
"LiveIntervals: {} vregs, {} blocks with liveness, {} subreg ops, computed={}",
self.interval_count,
self.block_liveness.len(),
self.subreg_count,
self.computed,
)
}
}
impl Default for X86LiveIntervals {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegAllocSplitting {
pub intervals: HashMap<u32, X86LiveInterval>,
pub split_points: HashMap<u32, Vec<SplitPoint>>,
pub new_vregs: Vec<u32>,
pub split_copies: Vec<(InstrPoint, u32, u32)>,
pub regions: Vec<ProgramRegion>,
pub block_to_region: HashMap<u32, u32>,
next_vreg_id: u32,
pub split_stats: SplittingStats,
}
#[derive(Debug, Clone, Default)]
pub struct SplittingStats {
pub region_splits: usize,
pub local_splits: usize,
pub global_splits: usize,
pub split_points_total: usize,
pub spill_slots_reused: usize,
pub total_children: usize,
}
impl X86RegAllocSplitting {
pub fn new() -> Self {
Self {
intervals: HashMap::new(),
split_points: HashMap::new(),
new_vregs: Vec::new(),
split_copies: Vec::new(),
regions: Vec::new(),
block_to_region: HashMap::new(),
next_vreg_id: 0x8000_0000,
split_stats: SplittingStats::default(),
}
}
pub fn allocate_vreg(&mut self) -> u32 {
let id = self.next_vreg_id;
self.next_vreg_id += 1;
self.new_vregs.push(id);
self.split_stats.total_children += 1;
id
}
pub fn add_region(&mut self, region: ProgramRegion) {
let id = region.id;
for &block in ®ion.blocks {
self.block_to_region.insert(block, id);
}
self.regions.push(region);
}
pub fn split_at_regions(&mut self, vreg: u32) -> Vec<u32> {
let interval = match self.intervals.get(&vreg).cloned() {
Some(iv) => iv,
None => return vec![],
};
let mut result = Vec::new();
let mut current_region: Option<u32> = None;
let mut region_segments: HashMap<u32, Vec<X86LiveSegment>> = HashMap::new();
for seg in &interval.segments {
let region = self.block_to_region.get(&seg.start.block).copied();
region_segments
.entry(region.unwrap_or(0))
.or_default()
.push(*seg);
}
if region_segments.len() <= 1 {
return vec![];
}
for (region_id, segs) in ®ion_segments {
if segs.is_empty() {
continue;
}
let child_vreg = self.allocate_vreg();
let mut child = X86LiveInterval::new(child_vreg, interval.reg_class);
child.parent = Some(vreg);
for seg in segs {
child.add_segment(seg.start, seg.end);
}
for &u in &interval.use_points {
if segs.iter().any(|s| s.contains(u)) {
child.add_use(u);
}
}
for &d in &interval.def_points {
if segs.iter().any(|s| s.contains(d)) {
child.add_def(d);
}
}
child.reg_hint = interval.reg_hint;
child.spill_weight = interval.spill_weight;
child.sort_and_merge();
self.intervals.insert(child_vreg, child);
result.push(child_vreg);
if let Some(first) = segs.first() {
let entry_point = InstrPoint::new(first.start.block, 0, 0);
if !self.split_copies.iter().any(|(p, _, _)| *p == entry_point) {
self.split_copies.push((entry_point, vreg, child_vreg));
}
}
}
self.intervals.remove(&vreg);
self.split_stats.region_splits += 1;
result
}
pub fn split_local(&mut self, vreg: u32, block: u32) -> Option<Vec<u32>> {
let interval = self.intervals.get(&vreg)?.clone();
let block_uses: Vec<InstrPoint> = interval
.use_points
.iter()
.filter(|p| p.block == block)
.copied()
.collect();
let block_defs: Vec<InstrPoint> = interval
.def_points
.iter()
.filter(|p| p.block == block)
.copied()
.collect();
if block_uses.len() + block_defs.len() <= 1 {
return None;
}
let mut new_vregs = Vec::new();
let all_points: BTreeSet<InstrPoint> = block_uses
.iter()
.chain(block_defs.iter())
.copied()
.collect();
let points: Vec<InstrPoint> = all_points.into_iter().collect();
for i in 0..points.len() {
let start = points[i];
let end = if i + 1 < points.len() {
points[i + 1].before()
} else {
start
};
if start == end {
continue;
}
let child_vreg = self.allocate_vreg();
let mut child = X86LiveInterval::new(child_vreg, interval.reg_class);
child.parent = Some(vreg);
child.add_segment(start, end);
if block_uses.contains(&start) {
child.add_use(start);
}
if block_defs.contains(&start) {
child.add_def(start);
}
child.spill_weight = interval.spill_weight;
self.intervals.insert(child_vreg, child);
new_vregs.push(child_vreg);
}
if new_vregs.len() > 1 {
self.intervals.remove(&vreg);
self.split_stats.local_splits += 1;
Some(new_vregs)
} else {
for v in &new_vregs {
self.intervals.remove(v);
}
None
}
}
pub fn split_global(&mut self, vreg: u32, loop_header: u32, loop_blocks: &[u32]) -> Vec<u32> {
let interval = match self.intervals.get(&vreg).cloned() {
Some(iv) => iv,
None => return vec![],
};
let loop_set: HashSet<u32> = loop_blocks.iter().copied().collect();
let mut pre_loop = X86LiveInterval::new(self.allocate_vreg(), interval.reg_class);
let mut in_loop = X86LiveInterval::new(self.allocate_vreg(), interval.reg_class);
let mut post_loop = X86LiveInterval::new(self.allocate_vreg(), interval.reg_class);
pre_loop.parent = Some(vreg);
in_loop.parent = Some(vreg);
post_loop.parent = Some(vreg);
for seg in &interval.segments {
let in_loop_start = loop_set.contains(&seg.start.block);
let in_loop_end = loop_set.contains(&seg.end.block);
if in_loop_start && in_loop_end {
in_loop.segments.push(*seg);
} else if !in_loop_start && !in_loop_end {
if seg.start.block < loop_header {
pre_loop.segments.push(*seg);
} else {
post_loop.segments.push(*seg);
}
} else {
let boundary = InstrPoint::new(loop_header, 0, 0);
if seg.start < boundary {
pre_loop
.segments
.push(X86LiveSegment::new(seg.start, boundary.before()));
in_loop
.segments
.push(X86LiveSegment::new(boundary, seg.end));
} else {
in_loop
.segments
.push(X86LiveSegment::new(seg.start, boundary.before()));
post_loop
.segments
.push(X86LiveSegment::new(boundary, seg.end));
}
}
}
for &u in &interval.use_points {
if loop_set.contains(&u.block) {
in_loop.add_use(u);
} else if u.block < loop_header {
pre_loop.add_use(u);
} else {
post_loop.add_use(u);
}
}
for &d in &interval.def_points {
if loop_set.contains(&d.block) {
in_loop.add_def(d);
} else if d.block < loop_header {
pre_loop.add_def(d);
} else {
post_loop.add_def(d);
}
}
let mut result = Vec::new();
let spill_w = interval.spill_weight;
let hint = interval.reg_hint;
if !pre_loop.segments.is_empty() {
pre_loop.spill_weight = spill_w;
pre_loop.reg_hint = hint;
pre_loop.sort_and_merge();
let pre_vreg = pre_loop.vreg;
self.intervals.insert(pre_vreg, pre_loop);
result.push(pre_vreg);
self.split_copies
.push((InstrPoint::new(loop_header, 0, 0).before(), vreg, pre_vreg));
}
if !in_loop.segments.is_empty() {
in_loop.spill_weight = spill_w * 10.0; in_loop.reg_hint = hint;
in_loop.sort_and_merge();
let in_vreg = in_loop.vreg;
self.intervals.insert(in_vreg, in_loop);
result.push(in_vreg);
}
if !post_loop.segments.is_empty() {
post_loop.spill_weight = spill_w;
post_loop.reg_hint = hint;
post_loop.sort_and_merge();
let post_vreg = post_loop.vreg;
self.intervals.insert(post_vreg, post_loop);
result.push(post_vreg);
}
if !result.is_empty() {
self.intervals.remove(&vreg);
self.split_stats.global_splits += 1;
}
result
}
pub fn assign_spill_slots(&mut self, spilled_vregs: &[u32]) -> HashMap<u32, i32> {
let mut slots: HashMap<u32, i32> = HashMap::new();
let mut slot_intervals: Vec<(i32, Vec<X86LiveSegment>)> = Vec::new(); let mut next_slot: i32 = 0;
for &vreg in spilled_vregs {
let interval = match self.intervals.get(&vreg) {
Some(iv) => iv,
None => continue,
};
let mut assigned = false;
for (slot, segs) in &mut slot_intervals {
let overlaps = interval
.segments
.iter()
.any(|a| segs.iter().any(|b| a.overlaps(b)));
if !overlaps {
segs.extend(interval.segments.clone());
slots.insert(vreg, *slot);
self.split_stats.spill_slots_reused += 1;
assigned = true;
break;
}
}
if !assigned {
let slot = next_slot;
next_slot += 8; slot_intervals.push((slot, interval.segments.clone()));
slots.insert(vreg, slot);
}
if let Some(iv) = self.intervals.get_mut(&vreg) {
iv.spill_offset = *slots.get(&vreg).unwrap_or(&-1);
iv.spilled = true;
}
}
slots
}
pub fn summary(&self) -> String {
format!(
"Splitting: {} region, {} local, {} global splits, {} slot reuses",
self.split_stats.region_splits,
self.split_stats.local_splits,
self.split_stats.global_splits,
self.split_stats.spill_slots_reused,
)
}
}
impl Default for X86RegAllocSplitting {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86EvictionChain {
pub evictions: Vec<X86EvictionRecord>,
pub max_depth: usize,
pub eviction_costs: HashMap<u32, f64>,
pub spill_weights: HashMap<u32, f64>,
pub cascade_enabled: bool,
pub chain_stats: EvictionChainStats,
}
#[derive(Debug, Clone, Copy)]
pub struct X86EvictionRecord {
pub evicted_vreg: u32,
pub evicting_vreg: u32,
pub phys_reg: u32,
pub point: InstrPoint,
pub cost: f64,
}
#[derive(Debug, Clone, Default)]
pub struct EvictionChainStats {
pub total_evictions: usize,
pub cascade_evictions: usize,
pub max_chain_depth: usize,
pub total_chain_depth: usize,
pub evictions_avoided: usize,
pub cost_saved: f64,
}
impl X86EvictionChain {
pub fn new() -> Self {
Self {
evictions: Vec::new(),
max_depth: 10,
eviction_costs: HashMap::new(),
spill_weights: HashMap::new(),
cascade_enabled: true,
chain_stats: EvictionChainStats::default(),
}
}
pub fn with_max_depth(mut self, depth: usize) -> Self {
self.max_depth = depth;
self
}
pub fn with_cascade(mut self, enabled: bool) -> Self {
self.cascade_enabled = enabled;
self
}
pub fn compute_spill_cost(
&self,
vreg: u32,
interval: &X86LiveInterval,
point: InstrPoint,
loop_depth: u32,
) -> f64 {
let base_cost = interval.spill_weight;
let remaining_uses = interval.use_points.iter().filter(|&&u| u >= point).count() as f64;
let remaining_defs = interval.def_points.iter().filter(|&&d| d >= point).count() as f64;
let loop_mult = 10.0f64.powi(loop_depth as i32);
base_cost + (remaining_uses * 0.5 + remaining_defs * 0.3) * loop_mult
}
pub fn compute_restore_cost(&self, interval: &X86LiveInterval, point: InstrPoint) -> f64 {
let uses_after = interval.use_points.iter().filter(|&&u| u >= point).count() as f64;
if uses_after == 0.0 {
return 0.0;
}
4.0 + uses_after * 0.1
}
pub fn compute_eviction_cost(
&self,
vreg: u32,
interval: &X86LiveInterval,
point: InstrPoint,
loop_depth: u32,
) -> f64 {
let spill_cost = self.compute_spill_cost(vreg, interval, point, loop_depth);
let restore_cost = self.compute_restore_cost(interval, point);
spill_cost + restore_cost
}
pub fn build_eviction_costs(
&mut self,
active_vregs: &[u32],
intervals: &HashMap<u32, X86LiveInterval>,
conflict_point: InstrPoint,
loop_depth: u32,
) {
self.eviction_costs.clear();
for &vreg in active_vregs {
if let Some(iv) = intervals.get(&vreg) {
if iv.is_fixed {
self.eviction_costs.insert(vreg, f64::MAX);
continue;
}
let cost = self.compute_eviction_cost(vreg, iv, conflict_point, loop_depth);
self.eviction_costs.insert(vreg, cost);
}
}
}
pub fn find_cheapest_to_evict(&self) -> Option<(u32, f64)> {
self.eviction_costs
.iter()
.min_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal))
.map(|(v, c)| (*v, *c))
}
pub fn record_eviction(
&mut self,
evicted_vreg: u32,
evicting_vreg: u32,
phys_reg: u32,
point: InstrPoint,
cost: f64,
) {
self.evictions.push(X86EvictionRecord {
evicted_vreg,
evicting_vreg,
phys_reg,
point,
cost,
});
self.chain_stats.total_evictions += 1;
let depth = self.current_depth();
self.chain_stats.max_chain_depth = self.chain_stats.max_chain_depth.max(depth);
self.chain_stats.total_chain_depth += depth;
}
pub fn current_depth(&self) -> usize {
self.evictions.len()
}
pub fn can_cascade(&self) -> bool {
self.cascade_enabled && self.current_depth() < self.max_depth
}
pub fn try_cascade_eviction(
&mut self,
evicted_vreg: u32,
phys_reg: u32,
point: InstrPoint,
active_vregs: &[u32],
intervals: &HashMap<u32, X86LiveInterval>,
loop_depth: u32,
) -> Option<u32> {
if !self.can_cascade() {
return None;
}
let other_active: Vec<u32> = active_vregs
.iter()
.filter(|&&v| v != evicted_vreg)
.copied()
.collect();
self.build_eviction_costs(&other_active, intervals, point, loop_depth);
if let Some((victim, cost)) = self.find_cheapest_to_evict() {
if cost
< self
.eviction_costs
.get(&evicted_vreg)
.copied()
.unwrap_or(f64::MAX)
{
self.record_eviction(victim, evicted_vreg, phys_reg, point, cost);
self.chain_stats.cascade_evictions += 1;
return Some(victim);
}
}
None
}
pub fn optimize_chain(&mut self) {
if self.evictions.len() <= 1 {
return;
}
self.evictions
.sort_by(|a, b| a.cost.partial_cmp(&b.cost).unwrap_or(Ordering::Equal));
let original_cost: f64 = self.evictions.iter().map(|e| e.cost).sum();
if let Some(last) = self.evictions.last() {
if last.cost > original_cost * 0.5 {
self.chain_stats.evictions_avoided += 1;
self.chain_stats.cost_saved += last.cost;
}
}
}
pub fn clear(&mut self) {
self.evictions.clear();
self.eviction_costs.clear();
}
pub fn cache_spill_weights(&mut self, intervals: &HashMap<u32, X86LiveInterval>) {
for (&vreg, iv) in intervals {
self.spill_weights.insert(vreg, iv.spill_weight);
}
}
pub fn total_chain_cost(&self) -> f64 {
self.evictions.iter().map(|e| e.cost).sum()
}
pub fn summary(&self) -> String {
format!(
"EvictionChain: {} evictions, {} cascaded, max depth {}, cost {:.2}",
self.chain_stats.total_evictions,
self.chain_stats.cascade_evictions,
self.chain_stats.max_chain_depth,
self.total_chain_cost(),
)
}
}
impl Default for X86EvictionChain {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86SpillOptimizer {
pub spill_slots: HashMap<u32, i32>,
pub spill_code: Vec<SpillCode>,
pub remat_info: HashMap<u32, X86RematSource>,
pub forwarding_candidates: Vec<(InstrPoint, InstrPoint, u32)>,
pub opt_stats: SpillOptStats,
}
#[derive(Debug, Clone, Copy)]
pub enum SpillCode {
Store {
point: InstrPoint,
vreg: u32,
slot: i32,
},
Load {
point: InstrPoint,
vreg: u32,
slot: i32,
},
Remat {
point: InstrPoint,
vreg: u32,
source_idx: u32,
},
}
#[derive(Debug, Clone)]
pub enum X86RematSource {
Constant(i64),
RodataLoad { label: String, offset: i64 },
FrameIndex(i32),
Computation { opcode: u32, operands: Vec<u32> },
GotEntry { label: String },
Zero,
}
#[derive(Debug, Clone, Default)]
pub struct SpillOptStats {
pub spills_inserted: usize,
pub reloads_inserted: usize,
pub remat_inserted: usize,
pub slots_coalesced: usize,
pub spills_hoisted: usize,
pub forwarding_eliminated: usize,
pub bytes_saved: usize,
}
impl X86SpillOptimizer {
pub fn new() -> Self {
Self {
spill_slots: HashMap::new(),
spill_code: Vec::new(),
remat_info: HashMap::new(),
forwarding_candidates: Vec::new(),
opt_stats: SpillOptStats::default(),
}
}
pub fn insert_spill_code(
&mut self,
vreg: u32,
interval: &X86LiveInterval,
slot: i32,
loop_depths: &HashMap<u32, u32>,
) {
for &def in &interval.def_points {
let store_pt = def.after();
let hoisted = self.try_hoist_out_of_loop(store_pt, loop_depths);
self.spill_code.push(SpillCode::Store {
point: hoisted,
vreg,
slot,
});
self.opt_stats.spills_inserted += 1;
}
for &u in &interval.use_points {
let load_pt = u.before();
let hoisted = self.try_hoist_out_of_loop(load_pt, loop_depths);
self.spill_code.push(SpillCode::Load {
point: hoisted,
vreg,
slot,
});
self.opt_stats.reloads_inserted += 1;
}
}
fn try_hoist_out_of_loop(
&mut self,
point: InstrPoint,
loop_depths: &HashMap<u32, u32>,
) -> InstrPoint {
let depth = loop_depths.get(&point.block).copied().unwrap_or(0);
if depth == 0 {
return point;
}
self.opt_stats.spills_hoisted += 1;
point
}
pub fn coalesce_spill_slots(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
spilled: &[u32],
) -> HashMap<u32, i32> {
let mut slot_map: HashMap<u32, i32> = HashMap::new();
let mut slot_occupants: Vec<(i32, Vec<X86LiveSegment>)> = Vec::new();
let mut next_slot: i32 = 0;
for &vreg in spilled {
let iv = match intervals.get(&vreg) {
Some(iv) => iv,
None => continue,
};
let mut reuse_slot = None;
for (slot, segs) in &mut slot_occupants {
let overlaps = iv
.segments
.iter()
.any(|a| segs.iter().any(|b| a.overlaps(b)));
if !overlaps {
segs.extend(iv.segments.clone());
reuse_slot = Some(*slot);
self.opt_stats.slots_coalesced += 1;
self.opt_stats.bytes_saved += 8;
break;
}
}
let slot = if let Some(s) = reuse_slot {
s
} else {
let s = next_slot;
next_slot += 8;
slot_occupants.push((s, iv.segments.clone()));
s
};
slot_map.insert(vreg, slot);
self.spill_slots.insert(vreg, slot);
}
slot_map
}
pub fn hoist_loop_spills(
&mut self,
loop_blocks: &[u32],
loop_depth: u32,
intervals: &HashMap<u32, X86LiveInterval>,
) {
if loop_depth == 0 {
return;
}
let loop_set: HashSet<u32> = loop_blocks.iter().copied().collect();
let mut new_code = Vec::new();
let mut removed = 0;
for code in &self.spill_code {
let pt = match code {
SpillCode::Store { point, .. } => *point,
SpillCode::Load { point, .. } => *point,
SpillCode::Remat { point, .. } => *point,
};
if loop_set.contains(&pt.block) {
let hoisted_pt =
InstrPoint::new(loop_blocks.iter().min().copied().unwrap_or(pt.block), 0, 0);
match code {
SpillCode::Store { vreg, slot, .. } => {
new_code.push(SpillCode::Store {
point: hoisted_pt,
vreg: *vreg,
slot: *slot,
});
}
SpillCode::Load { vreg, slot, .. } => {
new_code.push(SpillCode::Load {
point: hoisted_pt,
vreg: *vreg,
slot: *slot,
});
}
SpillCode::Remat {
vreg, source_idx, ..
} => {
new_code.push(SpillCode::Remat {
point: hoisted_pt,
vreg: *vreg,
source_idx: *source_idx,
});
}
}
removed += 1;
self.opt_stats.spills_hoisted += 1;
} else {
new_code.push(*code);
}
}
self.spill_code = new_code;
}
pub fn mark_rematerializable(&mut self, vreg: u32, source: X86RematSource) {
self.remat_info.insert(vreg, source);
}
pub fn is_rematerializable(&self, vreg: u32) -> bool {
self.remat_info.contains_key(&vreg)
}
pub fn get_remat_source(&self, vreg: u32) -> Option<&X86RematSource> {
self.remat_info.get(&vreg)
}
pub fn try_rematerialize(
&mut self,
vreg: u32,
point: InstrPoint,
interval: &X86LiveInterval,
) -> bool {
if !self.is_rematerializable(vreg) {
return false;
}
let source_idx = self.remat_info.len() as u32; self.spill_code.push(SpillCode::Remat {
point,
vreg,
source_idx,
});
self.opt_stats.remat_inserted += 1;
self.spill_slots.remove(&vreg);
true
}
pub fn detect_remat(
&mut self,
vreg: u32,
opcode: X86Opcode,
is_constant: bool,
constant_value: Option<i64>,
) {
use X86Opcode::*;
if is_constant {
if let Some(val) = constant_value {
self.mark_rematerializable(vreg, X86RematSource::Constant(val));
return;
}
}
match opcode {
XOR => {
self.mark_rematerializable(vreg, X86RematSource::Zero);
}
MOV => {
if let Some(val) = constant_value {
self.mark_rematerializable(vreg, X86RematSource::Constant(val));
}
}
MOVABS => {
if let Some(val) = constant_value {
self.mark_rematerializable(vreg, X86RematSource::FrameIndex(val as i32));
}
}
_ => {}
}
}
pub fn detect_forwarding_opportunities(&mut self, intervals: &HashMap<u32, X86LiveInterval>) {
self.forwarding_candidates.clear();
let mut by_vreg: HashMap<u32, Vec<SpillCode>> = HashMap::new();
for &code in &self.spill_code {
let vreg = match code {
SpillCode::Store { vreg, .. } | SpillCode::Load { vreg, .. } => vreg,
SpillCode::Remat { vreg, .. } => vreg,
};
by_vreg.entry(vreg).or_default().push(code);
}
for (vreg, codes) in &by_vreg {
for window in codes.windows(2) {
match (&window[0], &window[1]) {
(
SpillCode::Store {
point: p1,
vreg: v1,
slot: s1,
},
SpillCode::Load {
point: p2,
vreg: v2,
slot: s2,
},
) if v1 == v2 && s1 == s2 && p1.block == p2.block => {
self.forwarding_candidates.push((*p1, *p2, *vreg));
self.opt_stats.forwarding_eliminated += 1;
}
_ => {}
}
}
}
}
pub fn eliminate_forwarded_pairs(&mut self) {
let to_remove: HashSet<(InstrPoint, InstrPoint, u32)> =
self.forwarding_candidates.iter().copied().collect();
self.spill_code.retain(|code| {
let (pt, vreg) = match code {
SpillCode::Load { point, vreg, .. } => (*point, *vreg),
_ => return true,
};
!to_remove
.iter()
.any(|(_store_pt, load_pt, v)| *load_pt == pt && *v == vreg)
});
}
pub fn summary(&self) -> String {
format!(
"SpillOpt: {} spills, {} reloads, {} remat, {} forwarded, {} hoisted",
self.opt_stats.spills_inserted,
self.opt_stats.reloads_inserted,
self.opt_stats.remat_inserted,
self.opt_stats.forwarding_eliminated,
self.opt_stats.spills_hoisted,
)
}
}
impl Default for X86SpillOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegClassAssignment {
pub class_assignments: HashMap<u32, X86RegClass>,
pub constraints: Vec<RegClassConstraint>,
pub coalescing_pairs: Vec<(u32, u32)>,
pub pressure: HashMap<X86RegClass, u32>,
pub max_pressure: HashMap<X86RegClass, u32>,
pub class_stats: ClassAssignmentStats,
}
#[derive(Debug, Clone)]
pub struct RegClassConstraint {
pub point: InstrPoint,
pub vreg: u32,
pub required_class: X86RegClass,
pub operand_index: u8,
pub is_mandatory: bool,
}
#[derive(Debug, Clone, Default)]
pub struct ClassAssignmentStats {
pub gpr8_assignments: usize,
pub gpr16_assignments: usize,
pub gpr32_assignments: usize,
pub gpr64_assignments: usize,
pub xmm_assignments: usize,
pub ymm_assignments: usize,
pub zmm_assignments: usize,
pub copies_coalesced: usize,
pub constraints_violated: usize,
}
impl X86RegClassAssignment {
pub fn new() -> Self {
let mut max_pressure = HashMap::new();
max_pressure.insert(X86RegClass::GPR64, 14); max_pressure.insert(X86RegClass::GPR32, 14);
max_pressure.insert(X86RegClass::GPR16, 14);
max_pressure.insert(X86RegClass::GPR8, 14);
max_pressure.insert(X86RegClass::VECTOR128, 16); max_pressure.insert(X86RegClass::VECTOR256, 16);
max_pressure.insert(X86RegClass::VECTOR512, 32);
max_pressure.insert(X86RegClass::GPR8H, 4);
max_pressure.insert(X86RegClass::FLAGS, 1);
Self {
class_assignments: HashMap::new(),
constraints: Vec::new(),
coalescing_pairs: Vec::new(),
pressure: HashMap::new(),
max_pressure,
class_stats: ClassAssignmentStats::default(),
}
}
pub fn assign_class(&mut self, vreg: u32, preferred: X86RegClass) -> X86RegClass {
if let Some(constraint) = self
.constraints
.iter()
.find(|c| c.vreg == vreg && c.is_mandatory)
{
let cls = constraint.required_class;
self.class_assignments.insert(vreg, cls);
self.increment_class_count(cls);
return cls;
}
self.class_assignments.insert(vreg, preferred);
self.increment_class_count(preferred);
preferred
}
fn increment_class_count(&mut self, cls: X86RegClass) {
match cls {
X86RegClass::GPR8 => self.class_stats.gpr8_assignments += 1,
X86RegClass::GPR16 => self.class_stats.gpr16_assignments += 1,
X86RegClass::GPR32 => self.class_stats.gpr32_assignments += 1,
X86RegClass::GPR64 => self.class_stats.gpr64_assignments += 1,
X86RegClass::VECTOR128 => self.class_stats.xmm_assignments += 1,
X86RegClass::VECTOR256 => self.class_stats.ymm_assignments += 1,
X86RegClass::VECTOR512 => self.class_stats.zmm_assignments += 1,
_ => {}
}
*self.pressure.entry(cls).or_default() += 1;
}
pub fn add_constraint(
&mut self,
point: InstrPoint,
vreg: u32,
required_class: X86RegClass,
operand_index: u8,
is_mandatory: bool,
) {
self.constraints.push(RegClassConstraint {
point,
vreg,
required_class,
operand_index,
is_mandatory,
});
}
pub fn pressure_too_high(&self, class: X86RegClass) -> bool {
let pressure = self.pressure.get(&class).copied().unwrap_or(0);
let max = self.max_pressure.get(&class).copied().unwrap_or(16);
pressure > max
}
pub fn most_pressured_class(&self) -> Option<X86RegClass> {
self.pressure
.iter()
.filter_map(|(cls, &p)| {
let max = self.max_pressure.get(cls).copied().unwrap_or(1);
if max == 0 {
None
} else {
Some((*cls, p as f64 / max as f64))
}
})
.max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal))
.map(|(cls, _)| cls)
}
pub fn add_coalescing_pair(&mut self, dst: u32, src: u32) {
if dst != src && !self.coalescing_pairs.contains(&(dst, src)) {
self.coalescing_pairs.push((dst, src));
}
}
pub fn try_coalesce(&mut self, intervals: &HashMap<u32, X86LiveInterval>) -> usize {
let mut coalesced = 0;
let pairs: Vec<(u32, u32)> = self.coalescing_pairs.drain(..).collect();
for (dst, src) in &pairs {
let dst_iv = intervals.get(dst);
let src_iv = intervals.get(src);
if let (Some(d), Some(s)) = (dst_iv, src_iv) {
if !d.overlaps_with(s) {
if let Some(hint) = s.assigned_reg.or(s.fixed_reg) {
coalesced += 1;
}
if let Some(hint) = d.assigned_reg.or(d.fixed_reg) {
coalesced += 1;
}
}
}
}
self.coalescing_pairs = pairs
.into_iter()
.filter(|(d, s)| {
let d_iv = intervals.get(d);
let s_iv = intervals.get(s);
match (d_iv, s_iv) {
(Some(di), Some(si)) => di.overlaps_with(si),
_ => true,
}
})
.collect();
self.class_stats.copies_coalesced += coalesced;
coalesced
}
pub fn summary(&self) -> String {
format!(
"ClassAssign: GPR8={} GPR16={} GPR32={} GPR64={} XMM={} YMM={} ZMM={}, {} coalesced",
self.class_stats.gpr8_assignments,
self.class_stats.gpr16_assignments,
self.class_stats.gpr32_assignments,
self.class_stats.gpr64_assignments,
self.class_stats.xmm_assignments,
self.class_stats.ymm_assignments,
self.class_stats.zmm_assignments,
self.class_stats.copies_coalesced,
)
}
}
impl Default for X86RegClassAssignment {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86AllocationOrder {
pub order: HashMap<X86RegClass, Vec<u32>>,
pub callee_saved: Vec<u32>,
pub caller_saved: Vec<u32>,
pub reserved: X86RegMask,
pub hints: HashMap<u32, u32>,
pub prefer_callee_saved: bool,
pub prefer_caller_saved_for_short_lived: bool,
pub short_lived_threshold: u32,
}
impl X86AllocationOrder {
pub fn new() -> Self {
let callee_saved = vec![
x86_reg::RBX, x86_reg::RBP, x86_reg::R12, x86_reg::R13, x86_reg::R14, x86_reg::R15, ];
let caller_saved = vec![
x86_reg::RAX, x86_reg::RCX, x86_reg::RDX, x86_reg::RSI, x86_reg::RDI, x86_reg::R8, x86_reg::R9, x86_reg::R10, x86_reg::R11, ];
let mut reserved = X86RegMask::new();
reserved.set(x86_reg::RSP); reserved.set(x86_reg::RBP);
let mut order = HashMap::new();
let gpr_order: Vec<u32> = callee_saved
.iter()
.filter(|r| !reserved.contains(**r))
.copied()
.chain(caller_saved.iter().copied())
.collect();
order.insert(X86RegClass::GPR64, gpr_order.clone());
order.insert(X86RegClass::GPR32, gpr_order.clone());
let xmm_order: Vec<u32> = (200..216).collect();
let ymm_order: Vec<u32> = (300..316).collect();
let zmm_order: Vec<u32> = (400..432).collect();
order.insert(X86RegClass::VECTOR128, xmm_order);
order.insert(X86RegClass::VECTOR256, ymm_order);
order.insert(X86RegClass::VECTOR512, zmm_order);
Self {
order,
callee_saved,
caller_saved,
reserved,
hints: HashMap::new(),
prefer_callee_saved: true,
prefer_caller_saved_for_short_lived: true,
short_lived_threshold: 10,
}
}
pub fn with_prefer_callee_saved(mut self, v: bool) -> Self {
self.prefer_callee_saved = v;
self
}
pub fn with_short_lived_threshold(mut self, threshold: u32) -> Self {
self.short_lived_threshold = threshold;
self
}
pub fn add_hint(&mut self, vreg: u32, phys_reg: u32) {
self.hints.insert(vreg, phys_reg);
}
pub fn add_hint_from_copy(&mut self, dst: u32, src: u32, assignments: &HashMap<u32, u32>) {
if let Some(&phys_reg) = assignments.get(&src) {
self.hints.insert(dst, phys_reg);
}
if let Some(&phys_reg) = assignments.get(&dst) {
self.hints.insert(src, phys_reg);
}
}
pub fn get_allocation_order(
&self,
vreg: u32,
class: X86RegClass,
interval: Option<&X86LiveInterval>,
) -> Vec<u32> {
let base_order = self.order.get(&class).cloned().unwrap_or_default();
let mut ordered = vec![];
if let Some(&hint) = self.hints.get(&vreg) {
if !self.reserved.contains(hint) {
ordered.push(hint);
}
}
if let Some(iv) = interval {
let is_short_lived =
iv.segments.iter().map(|s| s.length()).sum::<u32>() < self.short_lived_threshold;
if self.prefer_caller_saved_for_short_lived && is_short_lived {
for ® in &self.caller_saved {
if !ordered.contains(®) && !self.reserved.contains(reg) {
ordered.push(reg);
}
}
for ® in &self.callee_saved {
if !ordered.contains(®) && !self.reserved.contains(reg) {
ordered.push(reg);
}
}
} else if self.prefer_callee_saved {
for ® in &self.callee_saved {
if !ordered.contains(®) && !self.reserved.contains(reg) {
ordered.push(reg);
}
}
for ® in &self.caller_saved {
if !ordered.contains(®) && !self.reserved.contains(reg) {
ordered.push(reg);
}
}
}
}
for ® in &base_order {
if !ordered.contains(®) && !self.reserved.contains(reg) {
ordered.push(reg);
}
}
ordered
}
pub fn is_callee_saved(&self, reg: u32) -> bool {
self.callee_saved.contains(®)
}
pub fn is_caller_saved(&self, reg: u32) -> bool {
self.caller_saved.contains(®)
}
pub fn is_reserved(&self, reg: u32) -> bool {
self.reserved.contains(reg)
}
pub fn reserve(&mut self, reg: u32) {
self.reserved.set(reg);
}
pub fn unreserve(&mut self, reg: u32) {
self.reserved.clear(reg);
}
pub fn build_hints_from_copies(
&mut self,
copies: &[(u32, u32)],
assignments: &HashMap<u32, u32>,
) {
for &(dst, src) in copies {
self.add_hint_from_copy(dst, src, assignments);
}
}
pub fn summary(&self) -> String {
format!(
"AllocOrder: prefer_callee={}, {} callee-saved regs, {} hints",
self.prefer_callee_saved,
self.callee_saved
.iter()
.filter(|r| !self.reserved.contains(**r))
.count(),
self.hints.len(),
)
}
}
impl Default for X86AllocationOrder {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86LinearScanAllocator {
pub intervals: HashMap<u32, X86LiveInterval>,
pub assignments: HashMap<u32, u32>,
pub spilled: HashSet<u32>,
pub spill_slots: HashMap<u32, i32>,
pub next_slot: i32,
pub alloc_order: X86AllocationOrder,
pub fixed_regs: HashMap<u32, u32>,
pub stats: X86LinearScanStats,
}
#[derive(Debug, Clone, Default)]
pub struct X86LinearScanStats {
pub total_intervals: usize,
pub registers_assigned: usize,
pub registers_spilled: usize,
pub copies_coalesced: usize,
pub load_before_use: usize,
pub store_after_def: usize,
pub split_before_alloc: usize,
}
impl X86LinearScanAllocator {
pub fn new() -> Self {
Self {
intervals: HashMap::new(),
assignments: HashMap::new(),
spilled: HashSet::new(),
spill_slots: HashMap::new(),
next_slot: 0,
alloc_order: X86AllocationOrder::new(),
fixed_regs: HashMap::new(),
stats: X86LinearScanStats::default(),
}
}
pub fn add_interval(&mut self, interval: X86LiveInterval) {
self.intervals.insert(interval.vreg, interval);
}
pub fn add_fixed_reg(&mut self, vreg: u32, phys_reg: u32, reg_class: X86RegClass) {
self.fixed_regs.insert(vreg, phys_reg);
let mut iv = X86LiveInterval::from_fixed(vreg, phys_reg, reg_class);
iv.assigned_reg = Some(phys_reg);
self.intervals.insert(vreg, iv);
}
pub fn allocate(&mut self) -> &X86LinearScanStats {
self.stats.total_intervals = self.intervals.len();
let mut unhandled: Vec<X86LiveInterval> = self
.intervals
.values()
.filter(|iv| !iv.is_fixed && iv.assigned_reg.is_none())
.cloned()
.collect();
unhandled.sort_by(|a, b| {
a.start_point().cmp(&b.start_point()).then_with(|| {
b.spill_weight
.partial_cmp(&a.spill_weight)
.unwrap_or(Ordering::Equal)
})
});
let mut active: Vec<X86ActiveEntry> = Vec::new();
let mut spilled_list: Vec<X86LiveInterval> = Vec::new();
for mut interval in unhandled {
let start = interval.start_point().unwrap_or(InstrPoint::new(0, 0, 0));
self.expire_active(&mut active, start);
let class = interval.reg_class;
let alloc_order =
self.alloc_order
.get_allocation_order(interval.vreg, class, Some(&interval));
let used_regs: HashSet<u32> = active.iter().map(|a| a.phys_reg).collect();
let free_reg = alloc_order.iter().find(|r| !used_regs.contains(r)).copied();
if let Some(reg) = free_reg {
let assign_reg = if let Some(hint) = interval.reg_hint {
if !used_regs.contains(&hint) && alloc_order.contains(&hint) {
hint
} else {
reg
}
} else {
reg
};
interval.assigned_reg = Some(assign_reg);
self.assignments.insert(interval.vreg, assign_reg);
self.stats.registers_assigned += 1;
let end = interval.end_point().unwrap_or(start);
active.push(X86ActiveEntry {
interval: interval.clone(),
phys_reg: assign_reg,
end_point: end,
});
} else {
self.spill_interval(&mut interval, &mut active, start);
spilled_list.push(interval);
}
}
for mut iv in spilled_list {
self.assign_spill_slot(&mut iv);
self.stats.registers_spilled += 1;
}
&self.stats
}
fn expire_active(&self, active: &mut Vec<X86ActiveEntry>, point: InstrPoint) {
active.retain(|entry| entry.end_point >= point);
}
fn spill_interval(
&mut self,
current: &mut X86LiveInterval,
active: &mut Vec<X86ActiveEntry>,
at_point: InstrPoint,
) {
if active.is_empty() {
current.spilled = true;
return;
}
let mut spill_idx = 0;
let mut furthest_end = InstrPoint::new(0, 0, 0);
for (i, entry) in active.iter().enumerate() {
if entry.interval.is_fixed {
continue;
}
let end = entry.interval.end_point().unwrap_or(entry.end_point);
if end > furthest_end {
furthest_end = end;
spill_idx = i;
}
}
let current_end = current.end_point().unwrap_or(at_point);
if current_end < furthest_end {
current.spilled = true;
return;
}
let evicted = active.remove(spill_idx);
let evicted_reg = evicted.phys_reg;
let mut evicted_iv = evicted.interval;
evicted_iv.spilled = true;
evicted_iv.assigned_reg = None;
self.assignments.remove(&evicted_iv.vreg);
current.assigned_reg = Some(evicted_reg);
self.assignments.insert(current.vreg, evicted_reg);
self.stats.registers_assigned += 1;
let end = current.end_point().unwrap_or(at_point);
active.push(X86ActiveEntry {
interval: current.clone(),
phys_reg: evicted_reg,
end_point: end,
});
}
fn assign_spill_slot(&mut self, interval: &mut X86LiveInterval) {
if self.spill_slots.contains_key(&interval.vreg) {
return;
}
let slot = self.next_slot;
self.next_slot += 8;
self.spill_slots.insert(interval.vreg, slot);
interval.spill_offset = slot;
for &_def in &interval.def_points {
self.stats.store_after_def += 1;
}
for &_use in &interval.use_points {
self.stats.load_before_use += 1;
}
}
pub fn get_assignment(&self, vreg: u32) -> Option<u32> {
self.assignments.get(&vreg).copied()
}
pub fn is_spilled(&self, vreg: u32) -> bool {
self.spilled.contains(&vreg) || self.spill_slots.contains_key(&vreg)
}
pub fn get_spill_slot(&self, vreg: u32) -> Option<i32> {
self.spill_slots.get(&vreg).copied()
}
pub fn summary(&self) -> String {
format!(
"X86LinearScan: {} vregs, {} assigned, {} spilled",
self.stats.total_intervals, self.stats.registers_assigned, self.stats.registers_spilled,
)
}
}
impl Default for X86LinearScanAllocator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
struct X86ActiveEntry {
interval: X86LiveInterval,
phys_reg: u32,
end_point: InstrPoint,
}
#[derive(Debug, Clone)]
pub struct X86GreedyAllocator {
pub intervals: HashMap<u32, X86LiveInterval>,
pub assignments: HashMap<u32, u32>,
pub spilled: HashSet<u32>,
pub spill_slots: HashMap<u32, i32>,
pub next_slot: i32,
pub alloc_order: X86AllocationOrder,
pub region_splitter: RegionSplitter,
pub splitter: X86RegAllocSplitting,
pub eviction_chain: X86EvictionChain,
pub spill_optimizer: X86SpillOptimizer,
pub class_assignment: X86RegClassAssignment,
pub weight_computer: SpillWeightComputer,
pub strategy: AssignStrategy,
pub fixed_regs: HashMap<u32, u32>,
pub stats: GreedyAllocStats,
}
impl X86GreedyAllocator {
pub fn new() -> Self {
Self {
intervals: HashMap::new(),
assignments: HashMap::new(),
spilled: HashSet::new(),
spill_slots: HashMap::new(),
next_slot: 0,
alloc_order: X86AllocationOrder::new(),
region_splitter: RegionSplitter::new(),
splitter: X86RegAllocSplitting::new(),
eviction_chain: X86EvictionChain::new(),
spill_optimizer: X86SpillOptimizer::new(),
class_assignment: X86RegClassAssignment::new(),
weight_computer: SpillWeightComputer::new(),
strategy: AssignStrategy::HintAware,
fixed_regs: HashMap::new(),
stats: GreedyAllocStats::new(),
}
}
pub fn with_strategy(mut self, strategy: AssignStrategy) -> Self {
self.strategy = strategy;
self
}
pub fn add_interval(&mut self, interval: X86LiveInterval) {
self.intervals.insert(interval.vreg, interval);
}
pub fn allocate(&mut self) -> &GreedyAllocStats {
self.stats.total_vregs = self.intervals.len();
let mut linear_intervals: HashMap<u32, LinearLiveInterval> = HashMap::new();
for (&vreg, x86_iv) in &self.intervals {
let mut liv = LinearLiveInterval::new(vreg, RegClassKind::GPR);
for seg in &x86_iv.segments {
liv.add_segment(seg.start, seg.end);
}
for &u in &x86_iv.use_points {
liv.add_use(u);
}
for &d in &x86_iv.def_points {
liv.add_def(d);
}
liv.spill_weight = x86_iv.spill_weight;
linear_intervals.insert(vreg, liv);
}
self.weight_computer
.compute_all_weights(&mut linear_intervals);
for (vreg, liv) in &linear_intervals {
if let Some(iv) = self.intervals.get_mut(vreg) {
iv.spill_weight = liv.spill_weight;
}
}
let mut unhandled: Vec<u32> = self
.intervals
.keys()
.filter(|v| !self.assignments.contains_key(v) && !self.fixed_regs.contains_key(v))
.copied()
.collect();
unhandled.sort_by(|a, b| {
let ia = &self.intervals[a];
let ib = &self.intervals[b];
ia.start_point().cmp(&ib.start_point()).then_with(|| {
ib.spill_weight
.partial_cmp(&ia.spill_weight)
.unwrap_or(Ordering::Equal)
})
});
let mut active_regs: Vec<(u32, u32)> = Vec::new(); let mut active_intervals: Vec<X86LiveInterval> = Vec::new();
for vreg in unhandled {
let interval = self.intervals[&vreg].clone();
let start = interval.start_point().unwrap_or(InstrPoint::new(0, 0, 0));
self.expire_active(&mut active_regs, &mut active_intervals, start);
let class = interval.reg_class;
let alloc_order = self
.alloc_order
.get_allocation_order(vreg, class, Some(&interval));
let used_regs: HashSet<u32> = active_regs.iter().map(|(r, _)| *r).collect();
let free_regs: Vec<u32> = alloc_order
.iter()
.filter(|r| !used_regs.contains(r))
.copied()
.collect();
if !free_regs.is_empty() {
let assign_reg = match self.strategy {
AssignStrategy::FirstFit => free_regs.first().copied(),
AssignStrategy::HintAware => {
if let Some(hint) = interval.reg_hint {
if free_regs.contains(&hint) {
Some(hint)
} else {
free_regs.first().copied()
}
} else {
free_regs.first().copied()
}
}
AssignStrategy::BestFit => {
free_regs
.iter()
.min_by_key(|&&r| active_regs.iter().filter(|(pr, _)| *pr == r).count())
.copied()
}
};
if let Some(reg) = assign_reg {
self.assignments.insert(vreg, reg);
self.stats.assigned_vregs += 1;
let end = interval.end_point().unwrap_or(start);
active_regs.push((reg, vreg));
active_intervals.push(interval);
continue;
}
}
if self.try_split_and_assign(vreg, &mut active_regs, &mut active_intervals) {
continue;
}
if self.try_evict(vreg, &mut active_regs, &mut active_intervals) {
continue;
}
self.spill_vreg(vreg);
}
&self.stats
}
fn expire_active(
&self,
active_regs: &mut Vec<(u32, u32)>,
active_intervals: &mut Vec<X86LiveInterval>,
point: InstrPoint,
) {
let mut i = 0;
while i < active_intervals.len() {
let expired = active_intervals[i]
.end_point()
.map(|e| e < point)
.unwrap_or(true);
if expired {
active_regs.remove(i);
active_intervals.remove(i);
} else {
i += 1;
}
}
}
fn try_split_and_assign(
&mut self,
vreg: u32,
active_regs: &mut Vec<(u32, u32)>,
active_intervals: &mut Vec<X86LiveInterval>,
) -> bool {
let interval = self.intervals.get(&vreg).unwrap().clone();
let block = interval.start_point().unwrap().block;
if let Some(children) = self.splitter.split_local(vreg, block) {
for child_vreg in children {
let child = self.intervals.get(&child_vreg).unwrap().clone();
let used: HashSet<u32> = active_regs.iter().map(|(r, _)| *r).collect();
let order = self.alloc_order.get_allocation_order(
child_vreg,
child.reg_class,
Some(&child),
);
if let Some(free) = order.iter().find(|r| !used.contains(r)).copied() {
self.assignments.insert(child_vreg, free);
self.stats.assigned_vregs += 1;
self.stats.splits_performed += 1;
self.stats.local_splits += 1;
let end = child.end_point().unwrap();
active_regs.push((free, child_vreg));
active_intervals.push(child);
self.assignments.insert(vreg, free);
return true;
}
}
}
let children = self.splitter.split_at_regions(vreg);
if !children.is_empty() {
for child_vreg in children {
let child = self.intervals.get(&child_vreg).unwrap().clone();
let used: HashSet<u32> = active_regs.iter().map(|(r, _)| *r).collect();
let order = self.alloc_order.get_allocation_order(
child_vreg,
child.reg_class,
Some(&child),
);
if let Some(free) = order.iter().find(|r| !used.contains(r)).copied() {
self.assignments.insert(child_vreg, free);
self.stats.assigned_vregs += 1;
self.stats.splits_performed += 1;
self.stats.global_splits += 1;
let end = child.end_point().unwrap();
active_regs.push((free, child_vreg));
active_intervals.push(child);
self.assignments.insert(vreg, free);
return true;
}
}
}
false
}
fn try_evict(
&mut self,
vreg: u32,
active_regs: &mut Vec<(u32, u32)>,
active_intervals: &mut Vec<X86LiveInterval>,
) -> bool {
if self.eviction_chain.current_depth() >= self.eviction_chain.max_depth {
return false;
}
let interval = match self.intervals.get(&vreg).cloned() {
Some(iv) => iv,
None => return false,
};
let start = interval.start_point().unwrap_or(InstrPoint::new(0, 0, 0));
let active_vregs: Vec<u32> = active_intervals.iter().map(|iv| iv.vreg).collect();
self.eviction_chain
.build_eviction_costs(&active_vregs, &self.intervals, start, 0);
if let Some((victim, _cost)) = self.eviction_chain.find_cheapest_to_evict() {
if let Some(pos) = active_regs.iter().position(|(_, v)| *v == victim) {
let evicted_reg = active_regs[pos].0;
active_regs.remove(pos);
active_intervals.remove(pos);
if let Some(victim_iv) = self.intervals.get_mut(&victim) {
victim_iv.spilled = true;
self.spilled.insert(victim);
}
self.assignments.remove(&victim);
self.assignments.insert(vreg, evicted_reg);
self.stats.assigned_vregs += 1;
self.stats.evictions_performed += 1;
let end = interval.end_point().unwrap_or(start);
active_regs.push((evicted_reg, vreg));
active_intervals.push(interval);
self.eviction_chain
.record_eviction(victim, vreg, evicted_reg, start, 0.0);
if self.eviction_chain.can_cascade() {
self.eviction_chain.try_cascade_eviction(
victim,
evicted_reg,
start,
&active_vregs,
&self.intervals,
0,
);
}
return true;
}
}
false
}
fn spill_vreg(&mut self, vreg: u32) {
self.spilled.insert(vreg);
self.stats.spilled_vregs += 1;
let slot = self.next_slot;
self.next_slot += 8;
self.spill_slots.insert(vreg, slot);
if let Some(iv) = self.intervals.get_mut(&vreg) {
iv.spilled = true;
iv.spill_offset = slot;
}
}
pub fn get_assignment(&self, vreg: u32) -> Option<u32> {
self.assignments.get(&vreg).copied()
}
pub fn is_spilled(&self, vreg: u32) -> bool {
self.spilled.contains(&vreg)
}
pub fn get_spill_slot(&self, vreg: u32) -> Option<i32> {
self.spill_slots.get(&vreg).copied()
}
pub fn summary(&self) -> String {
self.stats.summary()
}
}
impl Default for X86GreedyAllocator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86PbqpAllocator {
pub solver: PbqpSolver,
pub intervals: HashMap<u32, X86LiveInterval>,
pub assignments: HashMap<u32, u32>,
pub spilled: HashSet<u32>,
pub spill_slots: HashMap<u32, i32>,
pub next_slot: i32,
pub allowed_regs: HashMap<X86RegClass, Vec<u32>>,
pub alloc_order: X86AllocationOrder,
pub fixed_regs: HashMap<u32, u32>,
pub stats: PbqpAllocStats,
graph_built: bool,
solved: bool,
}
#[derive(Debug, Clone, Default)]
pub struct PbqpAllocStats {
pub total_vregs: usize,
pub assigned_vregs: usize,
pub spilled_vregs: usize,
pub r0_reductions: usize,
pub r1_reductions: usize,
pub r2_reductions: usize,
pub rn_reductions: usize,
pub total_cost: f64,
pub avg_cost_per_vreg: f64,
pub solved_iterations: usize,
}
impl X86PbqpAllocator {
pub fn new() -> Self {
let mut allowed_regs = HashMap::new();
allowed_regs.insert(X86RegClass::GPR64, (0..16).collect());
allowed_regs.insert(X86RegClass::GPR32, (100..116).collect());
allowed_regs.insert(X86RegClass::VECTOR128, (200..216).collect());
allowed_regs.insert(X86RegClass::VECTOR256, (300..316).collect());
allowed_regs.insert(X86RegClass::VECTOR512, (400..432).collect());
Self {
solver: PbqpSolver::new(),
intervals: HashMap::new(),
assignments: HashMap::new(),
spilled: HashSet::new(),
spill_slots: HashMap::new(),
next_slot: 0,
allowed_regs,
alloc_order: X86AllocationOrder::new(),
fixed_regs: HashMap::new(),
stats: PbqpAllocStats::default(),
graph_built: false,
solved: false,
}
}
pub fn add_interval(&mut self, interval: X86LiveInterval) {
self.intervals.insert(interval.vreg, interval);
}
pub fn build_graph(&mut self, interferences: &[(u32, u32)], coalescing_pairs: &[(u32, u32)]) {
let vregs: Vec<u32> = self.intervals.keys().copied().collect();
let all_allowed: Vec<u32> = self.allowed_regs.values().flatten().copied().collect();
for &vreg in &vregs {
let class = self
.intervals
.get(&vreg)
.map(|iv| iv.reg_class)
.unwrap_or(X86RegClass::GPR64);
let class_allowed = self.allowed_regs.get(&class).cloned().unwrap_or_default();
let spill_w = self
.intervals
.get(&vreg)
.map(|iv| iv.spill_weight)
.unwrap_or(0.0);
let mut node = PbqpNode::new(vreg, &class_allowed, spill_w * 0.01);
node.loop_depth = 0; self.solver.graph.add_node(node);
}
for &(a, b) in interferences {
let num_regs = all_allowed.len().max(16);
let edge = PbqpEdge::new(a, b, num_regs, num_regs);
self.solver.graph.add_edge(edge);
}
for &(a, b) in coalescing_pairs {
let num_regs = all_allowed.len().max(16);
let edge = PbqpEdge::with_coalescing_benefit(a, b, num_regs, 5.0);
self.solver.graph.add_edge(edge);
}
self.graph_built = true;
}
pub fn solve(&mut self) -> &PbqpAllocStats {
if !self.graph_built {
return &self.stats;
}
self.reduce_graph();
self.backpropagate();
self.select_solution();
self.solved = true;
self.compute_stats();
&self.stats
}
fn reduce_graph(&mut self) {
let mut iter = 0;
let max_iter = self.solver.max_iterations;
while iter < max_iter {
iter += 1;
let mut reduced_any = false;
if self.apply_r0() {
reduced_any = true;
continue;
}
if self.apply_r1() {
reduced_any = true;
continue;
}
if self.apply_r2() {
reduced_any = true;
continue;
}
if self.apply_rn() {
reduced_any = true;
continue;
}
if !reduced_any {
break;
}
}
self.stats.solved_iterations = iter;
}
fn apply_r0(&mut self) -> bool {
let independent: Vec<u32> = self
.solver
.graph
.nodes
.keys()
.filter(|v| self.solver.graph.degree(**v) == 0)
.copied()
.collect();
if independent.is_empty() {
return false;
}
for vreg in independent {
let node = &self.solver.graph.nodes[&vreg];
if let Some((reg, cost)) = node.costs.min_cost_reg() {
self.solver.graph.reduction_stack.push(vreg);
self.solver
.graph
.reduction_data
.push(ReductionData::R0Data { vreg, reg, cost });
}
self.solver.graph.remove_node(vreg);
self.stats.r0_reductions += 1;
}
true
}
fn apply_r1(&mut self) -> bool {
let degree_one: Vec<u32> = self
.solver
.graph
.nodes
.keys()
.filter(|v| self.solver.graph.degree(**v) == 1)
.copied()
.collect();
if degree_one.is_empty() {
return false;
}
for vreg in degree_one {
let neighbors = self.solver.graph.neighbors(vreg);
if let Some(&neighbor) = neighbors.first() {
if let Some(node) = self.solver.graph.nodes.get(&vreg).cloned() {
let optimized = node.costs.clone();
self.solver.graph.reduction_stack.push(vreg);
self.solver
.graph
.reduction_data
.push(ReductionData::R1Data {
vreg,
neighbor,
optimized_costs: optimized,
});
}
}
self.solver.graph.remove_node(vreg);
self.stats.r1_reductions += 1;
}
true
}
fn apply_r2(&mut self) -> bool {
let degree_two: Vec<u32> = self
.solver
.graph
.nodes
.keys()
.filter(|v| self.solver.graph.degree(**v) == 2)
.copied()
.collect();
if degree_two.is_empty() {
return false;
}
for vreg in degree_two {
let neighbors = self.solver.graph.neighbors(vreg);
if neighbors.len() != 2 {
continue;
}
let na = neighbors[0];
let nb = neighbors[1];
let num_regs_a = self
.solver
.graph
.nodes
.get(&na)
.map(|n| n.costs.num_choices())
.unwrap_or(16);
let num_regs_b = self
.solver
.graph
.nodes
.get(&nb)
.map(|n| n.costs.num_choices())
.unwrap_or(16);
let reduced = PbqpMatrix::new(num_regs_a, num_regs_b);
self.solver.graph.reduction_stack.push(vreg);
self.solver
.graph
.reduction_data
.push(ReductionData::R2Data {
vreg,
neighbor_a: na,
neighbor_b: nb,
reduced_matrix: reduced,
});
self.solver.graph.remove_node(vreg);
self.stats.r2_reductions += 1;
let edge = PbqpEdge::new(na, nb, num_regs_a, num_regs_b);
self.solver.graph.add_edge(edge);
}
true
}
fn apply_rn(&mut self) -> bool {
let mut redundancies = 0;
for &vreg in self.solver.graph.nodes.keys().collect::<Vec<_>>().iter() {
if let Some(node) = self.solver.graph.nodes.get(vreg) {
if node.costs.num_choices() <= 1 {
continue;
}
let allowed: Vec<u32> = node
.costs
.idx_to_reg
.iter()
.enumerate()
.filter(|(i, _)| node.costs.costs[*i] < PBQP_INF / 2.0)
.map(|(_, &r)| r)
.collect();
if allowed.len() < node.costs.num_choices() {
redundancies += 1;
}
}
}
if redundancies > 0 {
self.stats.rn_reductions += redundancies;
return true;
}
false
}
fn backpropagate(&mut self) {
while let Some(vreg) = self.solver.graph.reduction_stack.pop() {
while let Some(data) = self.solver.graph.reduction_data.pop() {
match data {
ReductionData::R0Data {
vreg: v,
reg,
cost: _,
} if v == vreg => {
self.assignments.insert(v, reg);
}
ReductionData::R1Data {
vreg: v,
neighbor,
optimized_costs: _,
} if v == vreg => {
if let Some(&neighbor_reg) = self.assignments.get(&neighbor) {
let class = X86RegClass::from_vreg(v);
let allowed =
self.allowed_regs.get(&class).cloned().unwrap_or_default();
let alt_reg = allowed
.iter()
.find(|&&r| r != neighbor_reg)
.copied()
.unwrap_or(neighbor_reg);
self.assignments.insert(v, alt_reg);
} else {
if let Some(node) = self.solver.graph.nodes.get(&v) {
if let Some((reg, _)) = node.costs.min_cost_reg() {
self.assignments.insert(v, reg);
}
}
}
}
ReductionData::R2Data { vreg: v, .. } if v == vreg => {
if let Some(node) = self.solver.graph.nodes.get(&v) {
if let Some((reg, _)) = node.costs.min_cost_reg() {
self.assignments.insert(v, reg);
}
}
}
_ => {
self.solver.graph.reduction_data.push(data);
break;
}
}
}
}
}
fn select_solution(&mut self) {
for &vreg in self.solver.graph.nodes.keys() {
if self.assignments.contains_key(&vreg) {
continue;
}
let node = &self.solver.graph.nodes[&vreg];
if node.costs.has_finite_cost() {
if let Some((reg, _)) = node.costs.min_cost_reg() {
if !self.alloc_order.is_reserved(reg) {
self.assignments.insert(vreg, reg);
self.stats.assigned_vregs += 1;
continue;
}
}
}
self.spilled.insert(vreg);
self.stats.spilled_vregs += 1;
let slot = self.next_slot;
self.next_slot += 8;
self.spill_slots.insert(vreg, slot);
}
}
fn compute_stats(&mut self) {
self.stats.total_vregs = self.intervals.len();
self.stats.assigned_vregs = self.assignments.len();
self.stats.spilled_vregs = self.spilled.len();
let assigned = self.stats.assigned_vregs.max(1) as f64;
self.stats.avg_cost_per_vreg = self.solver.total_cost / assigned;
}
pub fn get_assignment(&self, vreg: u32) -> Option<u32> {
self.assignments.get(&vreg).copied()
}
pub fn is_spilled(&self, vreg: u32) -> bool {
self.spilled.contains(&vreg)
}
pub fn get_spill_slot(&self, vreg: u32) -> Option<i32> {
self.spill_slots.get(&vreg).copied()
}
pub fn summary(&self) -> String {
format!(
"PBQP: {} vregs, {} assigned, {} spilled, {:.2} avg cost, R0={} R1={} R2={} RN={}",
self.stats.total_vregs,
self.stats.assigned_vregs,
self.stats.spilled_vregs,
self.stats.avg_cost_per_vreg,
self.stats.r0_reductions,
self.stats.r1_reductions,
self.stats.r2_reductions,
self.stats.rn_reductions,
)
}
}
impl Default for X86PbqpAllocator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86BasicAllocator {
pub block_assignments: HashMap<u32, u32>,
pub available: HashMap<X86RegClass, Vec<u32>>,
pub all_assignments: HashMap<u32, u32>,
pub spilled: HashSet<u32>,
pub spill_slots: HashMap<u32, i32>,
pub next_slot: i32,
pub alloc_order: X86AllocationOrder,
pub stats: BasicAllocStats,
}
#[derive(Debug, Clone, Default)]
pub struct BasicAllocStats {
pub blocks_processed: usize,
pub total_vregs: usize,
pub assigned_vregs: usize,
pub spilled_vregs: usize,
pub reloads_inserted: usize,
pub stores_inserted: usize,
}
impl X86BasicAllocator {
pub fn new() -> Self {
let mut available = HashMap::new();
available.insert(
X86RegClass::GPR64,
(0..16).filter(|r| *r != 4 && *r != 5).collect(),
);
available.insert(
X86RegClass::GPR32,
(100..116).filter(|r| *r != 104 && *r != 105).collect(),
);
available.insert(X86RegClass::VECTOR128, (200..216).collect());
available.insert(X86RegClass::VECTOR256, (300..316).collect());
available.insert(X86RegClass::VECTOR512, (400..432).collect());
Self {
block_assignments: HashMap::new(),
available,
all_assignments: HashMap::new(),
spilled: HashSet::new(),
spill_slots: HashMap::new(),
next_slot: 0,
alloc_order: X86AllocationOrder::new(),
stats: BasicAllocStats::default(),
}
}
pub fn allocate_block(
&mut self,
block: u32,
vregs_used: &[u32],
intervals: &HashMap<u32, X86LiveInterval>,
live_in: &HashSet<u32>,
) -> BasicBlockAllocResult {
self.block_assignments.clear();
self.stats.blocks_processed += 1;
let mut result = BasicBlockAllocResult {
block,
assignments: HashMap::new(),
loads: Vec::new(),
stores: Vec::new(),
};
for &vreg in live_in {
if let Some(slot) = self.spill_slots.get(&vreg) {
result.loads.push((vreg, *slot));
self.stats.reloads_inserted += 1;
}
}
for &vreg in vregs_used {
if self.all_assignments.contains_key(&vreg) {
if let Some(®) = self.all_assignments.get(&vreg) {
self.block_assignments.insert(vreg, reg);
result.assignments.insert(vreg, reg);
}
continue;
}
if let Some(iv) = intervals.get(&vreg) {
let class = iv.reg_class;
let available = self.available.get(&class).cloned().unwrap_or_default();
let used: HashSet<u32> = self.block_assignments.values().copied().collect();
if let Some(®) = available.iter().find(|r| !used.contains(r)) {
self.block_assignments.insert(vreg, reg);
self.all_assignments.insert(vreg, reg);
result.assignments.insert(vreg, reg);
self.stats.assigned_vregs += 1;
} else {
self.spilled.insert(vreg);
let slot = self.next_slot;
self.next_slot += 8;
self.spill_slots.insert(vreg, slot);
for &_def in &iv.def_points {
if _def.block == block {
result.stores.push((vreg, slot));
self.stats.stores_inserted += 1;
}
}
for &_use in &iv.use_points {
if _use.block == block {
result.loads.push((vreg, slot));
self.stats.reloads_inserted += 1;
}
}
self.stats.spilled_vregs += 1;
}
}
}
for (&vreg, ®) in &self.block_assignments {
self.all_assignments.insert(vreg, reg);
}
self.stats.total_vregs = self.all_assignments.len() + self.spilled.len();
result
}
pub fn get_assignment(&self, vreg: u32) -> Option<u32> {
self.all_assignments.get(&vreg).copied()
}
pub fn is_spilled(&self, vreg: u32) -> bool {
self.spilled.contains(&vreg)
}
pub fn get_spill_slot(&self, vreg: u32) -> Option<i32> {
self.spill_slots.get(&vreg).copied()
}
pub fn summary(&self) -> String {
format!(
"BasicAlloc: {} blocks, {} vregs, {} assigned, {} spilled",
self.stats.blocks_processed,
self.stats.total_vregs,
self.stats.assigned_vregs,
self.stats.spilled_vregs,
)
}
}
impl Default for X86BasicAllocator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct BasicBlockAllocResult {
pub block: u32,
pub assignments: HashMap<u32, u32>,
pub loads: Vec<(u32, i32)>,
pub stores: Vec<(u32, i32)>,
}
pub struct X86RegisterAllocator {
pub live_intervals: X86LiveIntervals,
pub splitter: X86RegAllocSplitting,
pub eviction_chain: X86EvictionChain,
pub spill_optimizer: X86SpillOptimizer,
pub class_assignment: X86RegClassAssignment,
pub alloc_order: X86AllocationOrder,
pub basic: X86BasicAllocator,
pub linear_scan: X86LinearScanAllocator,
pub greedy: X86GreedyAllocator,
pub pbqp: X86PbqpAllocator,
pub opt_level: u8,
pub allocated: bool,
pub function_name: String,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86AllocOptLevel {
O0,
O1,
O2,
O3,
}
impl From<X86AllocOptLevel> for u8 {
fn from(level: X86AllocOptLevel) -> u8 {
match level {
X86AllocOptLevel::O0 => 0,
X86AllocOptLevel::O1 => 1,
X86AllocOptLevel::O2 => 2,
X86AllocOptLevel::O3 => 3,
}
}
}
impl X86RegisterAllocator {
pub fn new(function_name: &str) -> Self {
Self {
live_intervals: X86LiveIntervals::new(),
splitter: X86RegAllocSplitting::new(),
eviction_chain: X86EvictionChain::new(),
spill_optimizer: X86SpillOptimizer::new(),
class_assignment: X86RegClassAssignment::new(),
alloc_order: X86AllocationOrder::new(),
basic: X86BasicAllocator::new(),
linear_scan: X86LinearScanAllocator::new(),
greedy: X86GreedyAllocator::new(),
pbqp: X86PbqpAllocator::new(),
opt_level: 2,
allocated: false,
function_name: function_name.to_string(),
}
}
pub fn with_opt_level(mut self, level: X86AllocOptLevel) -> Self {
self.opt_level = level.into();
self
}
pub fn compute_live_intervals(
&mut self,
defs: &HashMap<u32, Vec<InstrPoint>>,
uses: &HashMap<u32, Vec<InstrPoint>>,
block_order: &[u32],
) {
self.live_intervals
.compute_intervals(defs, uses, block_order);
}
pub fn set_loop_depths(&mut self, depths: &HashMap<u32, u32>) {
for (&block, &depth) in depths {
self.live_intervals.set_loop_depth(block, depth);
}
}
pub fn add_fixed_reg(&mut self, vreg: u32, phys_reg: u32, class: X86RegClass) {
self.linear_scan.add_fixed_reg(vreg, phys_reg, class);
self.greedy.fixed_regs.insert(vreg, phys_reg);
self.pbqp.fixed_regs.insert(vreg, phys_reg);
}
pub fn add_region(&mut self, region: ProgramRegion) {
self.splitter.add_region(region);
self.greedy.region_splitter.add_region(region);
}
pub fn add_copy(&mut self, dst: u32, src: u32) {
self.class_assignment.add_coalescing_pair(dst, src);
self.alloc_order
.add_hint_from_copy(dst, src, &HashMap::new());
}
pub fn add_remat(&mut self, vreg: u32, source: X86RematSource) {
self.spill_optimizer.mark_rematerializable(vreg, source);
}
pub fn allocate(&mut self) -> X86AllocResult {
self.allocated = true;
match self.opt_level {
0 => self.allocate_basic(),
1 => self.allocate_linear_scan(),
3 => self.allocate_pbqp(),
_ => self.allocate_greedy(),
}
}
fn allocate_basic(&mut self) -> X86AllocResult {
let mut result = X86AllocResult::new("basic");
let mut blocks: HashSet<u32> = HashSet::new();
for iv in self.live_intervals.intervals.values() {
for seg in &iv.segments {
blocks.insert(seg.start.block);
blocks.insert(seg.end.block);
}
}
let mut block_list: Vec<u32> = blocks.into_iter().collect();
block_list.sort();
for block in block_list {
let vregs: Vec<u32> = self
.live_intervals
.intervals
.keys()
.filter(|v| {
self.live_intervals.intervals.get(v).map_or(false, |iv| {
iv.segments
.iter()
.any(|s| s.start.block == block || s.end.block == block)
})
})
.copied()
.collect();
let live_in = self
.live_intervals
.block_liveness
.get(&block)
.cloned()
.unwrap_or_default();
let live_in_set: HashSet<u32> = live_in.into_iter().collect();
let block_result = self.basic.allocate_block(
block,
&vregs,
&self.live_intervals.intervals,
&live_in_set,
);
result.block_results.push(block_result);
}
result.assignments = self.basic.all_assignments.clone();
result.spilled = self.basic.spilled.clone();
result.spill_slots = self.basic.spill_slots.clone();
result.summary = self.basic.summary();
result
}
fn allocate_linear_scan(&mut self) -> X86AllocResult {
for (&vreg, x86_iv) in &self.live_intervals.intervals {
let mut iv = x86_iv.clone();
iv.spill_weight = self.compute_spill_weight_for(vreg);
self.linear_scan.add_interval(iv);
}
self.linear_scan.allocate();
let mut result = X86AllocResult::new("linear_scan");
result.assignments = self.linear_scan.assignments.clone();
result.spilled = self.linear_scan.spilled.clone();
result.spill_slots = self.linear_scan.spill_slots.clone();
result.stats = format!(
"LS: assigned={} spilled={}",
self.linear_scan.stats.registers_assigned, self.linear_scan.stats.registers_spilled,
);
result.summary = self.linear_scan.summary();
result
}
fn allocate_greedy(&mut self) -> X86AllocResult {
for (&vreg, x86_iv) in &self.live_intervals.intervals {
let mut iv = x86_iv.clone();
iv.spill_weight = self.compute_spill_weight_for(vreg);
self.greedy.add_interval(iv);
self.splitter.intervals.insert(vreg, x86_iv.clone());
}
let coalesced = self
.class_assignment
.try_coalesce(&self.live_intervals.intervals);
self.greedy.stats.copies_coalesced = coalesced;
self.greedy.allocate();
let spilled: Vec<u32> = self.greedy.spilled.iter().copied().collect();
for &vreg in &spilled {
if let Some(iv) = self.live_intervals.intervals.get(&vreg) {
let slot = self.greedy.spill_slots.get(&vreg).copied().unwrap_or(0);
self.spill_optimizer.insert_spill_code(
vreg,
iv,
slot,
&self.live_intervals.loop_depths,
);
}
}
let coalesced_slots = self
.spill_optimizer
.coalesce_spill_slots(&self.live_intervals.intervals, &spilled);
for (vreg, slot) in coalesced_slots {
self.greedy.spill_slots.insert(vreg, slot);
}
self.spill_optimizer
.detect_forwarding_opportunities(&self.live_intervals.intervals);
self.spill_optimizer.eliminate_forwarded_pairs();
let mut result = X86AllocResult::new("greedy");
result.assignments = self.greedy.assignments.clone();
result.spilled = self.greedy.spilled.clone();
result.spill_slots = self.greedy.spill_slots.clone();
result.stats = self.greedy.stats.summary();
result.summary = format!(
"Greedy: {} | {} | {}",
self.greedy.summary(),
self.spill_optimizer.summary(),
self.splitter.summary(),
);
result
}
fn allocate_pbqp(&mut self) -> X86AllocResult {
for (&vreg, x86_iv) in &self.live_intervals.intervals {
let mut iv = x86_iv.clone();
iv.spill_weight = self.compute_spill_weight_for(vreg);
self.pbqp.add_interval(iv);
}
let interferences = self.build_interference_graph();
let coalescing = self.class_assignment.coalescing_pairs.clone();
self.pbqp.build_graph(&interferences, &coalescing);
self.pbqp.solve();
let mut result = X86AllocResult::new("pbqp");
result.assignments = self.pbqp.assignments.clone();
result.spilled = self.pbqp.spilled.clone();
result.spill_slots = self.pbqp.spill_slots.clone();
result.stats = self.pbqp.summary();
result.summary = self.pbqp.summary();
result
}
fn build_interference_graph(&self) -> Vec<(u32, u32)> {
let mut edges = Vec::new();
let vregs: Vec<u32> = self.pbqp.intervals.keys().copied().collect();
for i in 0..vregs.len() {
for j in (i + 1)..vregs.len() {
let a = vregs[i];
let b = vregs[j];
if let (Some(iva), Some(ivb)) =
(self.pbqp.intervals.get(&a), self.pbqp.intervals.get(&b))
{
if iva.overlaps_with(ivb) {
edges.push((a, b));
}
}
}
}
edges
}
fn compute_spill_weight_for(&self, vreg: u32) -> f64 {
let iv = match self.live_intervals.intervals.get(&vreg) {
Some(iv) => iv,
None => return 0.0,
};
let mut weight = 0.0;
for &u in &iv.use_points {
let depth = self.live_intervals.loop_depth_at(u);
weight += 10.0f64.powi(depth as i32);
}
for &d in &iv.def_points {
let depth = self.live_intervals.loop_depth_at(d);
weight += 5.0f64.powi(depth as i32);
}
let len = iv.segments.iter().map(|s| s.length()).sum::<u32>().max(1) as f64;
weight / len
}
pub fn get_assignment(&self, vreg: u32) -> Option<u32> {
match self.opt_level {
0 => self.basic.get_assignment(vreg),
1 => self.linear_scan.get_assignment(vreg),
3 => self.pbqp.get_assignment(vreg),
_ => self.greedy.get_assignment(vreg),
}
}
pub fn is_spilled(&self, vreg: u32) -> bool {
match self.opt_level {
0 => self.basic.is_spilled(vreg),
1 => self.linear_scan.is_spilled(vreg),
3 => self.pbqp.is_spilled(vreg),
_ => self.greedy.is_spilled(vreg),
}
}
pub fn get_spill_slot(&self, vreg: u32) -> Option<i32> {
match self.opt_level {
0 => self.basic.get_spill_slot(vreg),
1 => self.linear_scan.get_spill_slot(vreg),
3 => self.pbqp.get_spill_slot(vreg),
_ => self.greedy.get_spill_slot(vreg),
}
}
pub fn report(&self) -> String {
format!(
"=== X86 Register Allocation Report ===\n\
Function: {}\n\
Opt Level: O{}\n\
Intervals: {}\n\
\n\
--- Assignments ---\n\
{}\n\
\n\
--- Splitting ---\n\
{}\n\
\n\
--- Spill Optimization ---\n\
{}\n\
\n\
--- Eviction Chain ---\n\
{}\n\
\n\
--- Class Assignment ---\n\
{}\n\
\n\
--- Allocation Order ---\n\
{}\n",
self.function_name,
self.opt_level,
self.live_intervals.interval_count,
self.get_stats_summary(),
self.splitter.summary(),
self.spill_optimizer.summary(),
self.eviction_chain.summary(),
self.class_assignment.summary(),
self.alloc_order.summary(),
)
}
fn get_stats_summary(&self) -> String {
match self.opt_level {
0 => self.basic.summary(),
1 => self.linear_scan.summary(),
2 => self.greedy.summary(),
3 => self.pbqp.summary(),
_ => "Unknown opt level".to_string(),
}
}
}
#[derive(Debug, Clone)]
pub struct X86AllocResult {
pub allocator: String,
pub assignments: HashMap<u32, u32>,
pub spilled: HashSet<u32>,
pub spill_slots: HashMap<u32, i32>,
pub stats: String,
pub summary: String,
pub block_results: Vec<BasicBlockAllocResult>,
}
impl X86AllocResult {
pub fn new(allocator: &str) -> Self {
Self {
allocator: allocator.to_string(),
assignments: HashMap::new(),
spilled: HashSet::new(),
spill_slots: HashMap::new(),
stats: String::new(),
summary: String::new(),
block_results: Vec::new(),
}
}
}
#[derive(Debug, Clone)]
pub struct X86SubregisterTracking {
pub super_to_sub: HashMap<u32, Vec<u32>>,
pub sub_to_super: HashMap<u32, u32>,
pub lane_masks: HashMap<u32, Vec<u64>>,
pub partial_write: HashMap<u32, bool>,
pub high8_regs: HashSet<u32>,
}
impl X86SubregisterTracking {
pub fn new() -> Self {
let mut st = Self {
super_to_sub: HashMap::new(),
sub_to_super: HashMap::new(),
lane_masks: HashMap::new(),
partial_write: HashMap::new(),
high8_regs: HashSet::new(),
};
for (super_reg, eax_off, ax_off, al_off) in &[
(x86_reg::RAX, 100u32, 200u32, 300u32),
(x86_reg::RCX, 101, 201, 301),
(x86_reg::RDX, 102, 202, 302),
(x86_reg::RBX, 103, 203, 303),
] {
st.super_to_sub
.insert(*super_reg, vec![*eax_off, *ax_off, *al_off]);
st.sub_to_super.insert(*eax_off, *super_reg);
st.sub_to_super.insert(*ax_off, *super_reg);
st.sub_to_super.insert(*al_off, *super_reg);
st.partial_write.insert(*eax_off, false);
st.partial_write.insert(*ax_off, true);
st.partial_write.insert(*al_off, true);
}
for (super_reg, eax_off, ax_off, al_off) in &[
(x86_reg::RSP, 104, 204, 304),
(x86_reg::RBP, 105, 205, 305),
(x86_reg::RSI, 106, 206, 306),
(x86_reg::RDI, 107, 207, 307),
] {
st.super_to_sub
.insert(*super_reg, vec![*eax_off, *ax_off, *al_off]);
st.sub_to_super.insert(*eax_off, *super_reg);
st.sub_to_super.insert(*ax_off, *super_reg);
st.sub_to_super.insert(*al_off, *super_reg);
}
for i in 0..8u32 {
let gpr64 = x86_reg::R8 + i;
let gpr32 = 108 + i;
let gpr16 = 208 + i;
let gpr8 = 308 + i;
st.super_to_sub.insert(gpr64, vec![gpr32, gpr16, gpr8]);
st.sub_to_super.insert(gpr32, gpr64);
st.sub_to_super.insert(gpr16, gpr64);
st.sub_to_super.insert(gpr8, gpr64);
st.partial_write.insert(gpr32, false);
}
st.high8_regs.extend(&[301, 302, 303, 304]);
st
}
pub fn write_affects_super(&self, sub_reg: u32, super_reg: u32) -> bool {
self.sub_to_super.get(&sub_reg) == Some(&super_reg)
}
pub fn is_partial_write(&self, sub_reg: u32) -> bool {
self.partial_write.get(&sub_reg).copied().unwrap_or(false)
}
pub fn subregs_of(&self, reg: u32) -> Vec<u32> {
self.super_to_sub.get(®).cloned().unwrap_or_default()
}
pub fn super_of(&self, sub_reg: u32) -> Option<u32> {
self.sub_to_super.get(&sub_reg).copied()
}
pub fn is_high8(&self, reg: u32) -> bool {
self.high8_regs.contains(®)
}
pub fn build_lane_mask(&mut self, vreg: u32, lanes: &[u64]) {
self.lane_masks.insert(vreg, lanes.to_vec());
}
}
impl Default for X86SubregisterTracking {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86CostModel {
pub latency: HashMap<u32, u32>,
pub throughput: HashMap<u32, u32>,
pub load_latency: u32,
pub store_latency: u32,
pub spill_cost_multiplier: f64,
pub reload_cost_multiplier: f64,
pub copy_cost: f64,
pub uarch: X86UArch,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86UArch {
Generic,
Skylake,
Icelake,
AlderLake,
Zen3,
Zen4,
Zen5,
}
impl X86CostModel {
pub fn new(uarch: X86UArch) -> Self {
let mut latency = HashMap::new();
let mut throughput = HashMap::new();
latency.insert(1, 1); latency.insert(2, 1); latency.insert(3, 1); latency.insert(4, 3); latency.insert(5, 30); latency.insert(6, 1); latency.insert(7, 1); latency.insert(8, 1); latency.insert(9, 1);
throughput.insert(1, 4); throughput.insert(2, 4); throughput.insert(3, 4); throughput.insert(4, 1); throughput.insert(5, 1);
let (load_lat, store_lat) = match uarch {
X86UArch::Skylake | X86UArch::Icelake => (5, 2),
X86UArch::AlderLake => (4, 2),
X86UArch::Zen3 | X86UArch::Zen4 => (4, 1),
X86UArch::Zen5 => (3, 1),
X86UArch::Generic => (5, 2),
};
Self {
latency,
throughput,
load_latency: load_lat,
store_latency: store_lat,
spill_cost_multiplier: (load_lat + store_lat) as f64,
reload_cost_multiplier: load_lat as f64,
copy_cost: 0.25, uarch,
}
}
pub fn get_latency(&self, opcode: u32) -> u32 {
self.latency.get(&opcode).copied().unwrap_or(4)
}
pub fn get_throughput(&self, opcode: u32) -> u32 {
self.throughput.get(&opcode).copied().unwrap_or(1)
}
pub fn spill_cost(&self, loop_depth: u32) -> f64 {
let base = self.spill_cost_multiplier;
base * 10.0f64.powi(loop_depth as i32)
}
pub fn reload_cost(&self, loop_depth: u32) -> f64 {
let base = self.reload_cost_multiplier;
base * 10.0f64.powi(loop_depth as i32)
}
pub fn eviction_cost(&self, loop_depth: u32) -> f64 {
self.spill_cost(loop_depth) + self.reload_cost(loop_depth)
}
}
impl Default for X86CostModel {
fn default() -> Self {
Self::new(X86UArch::Generic)
}
}
#[derive(Debug, Clone)]
pub struct X86RegisterPressure {
pub pressure: HashMap<X86RegClass, u32>,
pub max_pressure: HashMap<X86RegClass, u32>,
pub pressure_history: Vec<(InstrPoint, X86RegClass, u32)>,
pub split_threshold: f64,
pub pressure_stats: PressureStats,
}
#[derive(Debug, Clone, Default)]
pub struct PressureStats {
pub max_gpr_pressure: u32,
pub max_xmm_pressure: u32,
pub max_ymm_pressure: u32,
pub max_zmm_pressure: u32,
pub pressure_exceeded_count: usize,
pub splits_triggered_by_pressure: usize,
}
impl X86RegisterPressure {
pub fn new() -> Self {
let mut max_pressure = HashMap::new();
max_pressure.insert(X86RegClass::GPR64, 14);
max_pressure.insert(X86RegClass::GPR32, 14);
max_pressure.insert(X86RegClass::GPR16, 14);
max_pressure.insert(X86RegClass::GPR8, 14);
max_pressure.insert(X86RegClass::VECTOR128, 16);
max_pressure.insert(X86RegClass::VECTOR256, 16);
max_pressure.insert(X86RegClass::VECTOR512, 32);
max_pressure.insert(X86RegClass::GPR8H, 4);
max_pressure.insert(X86RegClass::FLAGS, 1);
Self {
pressure: HashMap::new(),
max_pressure,
pressure_history: Vec::new(),
split_threshold: 0.9,
pressure_stats: PressureStats::default(),
}
}
pub fn inc(&mut self, class: X86RegClass, point: InstrPoint) {
*self.pressure.entry(class).or_default() += 1;
let p = self.pressure[&class];
self.pressure_history.push((point, class, p));
match class {
X86RegClass::GPR64 | X86RegClass::GPR32 | X86RegClass::GPR16 | X86RegClass::GPR8 => {
self.pressure_stats.max_gpr_pressure = self.pressure_stats.max_gpr_pressure.max(p);
}
X86RegClass::VECTOR128 => {
self.pressure_stats.max_xmm_pressure = self.pressure_stats.max_xmm_pressure.max(p);
}
X86RegClass::VECTOR256 => {
self.pressure_stats.max_ymm_pressure = self.pressure_stats.max_ymm_pressure.max(p);
}
X86RegClass::VECTOR512 => {
self.pressure_stats.max_zmm_pressure = self.pressure_stats.max_zmm_pressure.max(p);
}
_ => {}
}
}
pub fn dec(&mut self, class: X86RegClass) {
if let Some(p) = self.pressure.get_mut(&class) {
if *p > 0 {
*p -= 1;
}
}
}
pub fn is_high(&self, class: X86RegClass) -> bool {
let p = self.pressure.get(&class).copied().unwrap_or(0) as f64;
let max = self.max_pressure.get(&class).copied().unwrap_or(16) as f64;
if max == 0.0 {
return false;
}
p >= max * self.split_threshold
}
pub fn is_exceeded(&self, class: X86RegClass) -> bool {
let p = self.pressure.get(&class).copied().unwrap_or(0);
let max = self.max_pressure.get(&class).copied().unwrap_or(16);
p > max
}
pub fn most_pressured(&self) -> Option<X86RegClass> {
self.pressure
.iter()
.filter_map(|(cls, &p)| {
let max = self.max_pressure.get(cls).copied().unwrap_or(1);
if max == 0 {
None
} else {
Some((*cls, p as f64 / max as f64))
}
})
.max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(Ordering::Equal))
.map(|(cls, _)| cls)
}
pub fn pressure_at(&self, class: X86RegClass, point: InstrPoint) -> u32 {
self.pressure_history
.iter()
.filter(|(pt, cls, _)| *cls == class && *pt <= point)
.last()
.map(|(_, _, p)| *p)
.unwrap_or(0)
}
pub fn reset(&mut self) {
self.pressure.clear();
}
pub fn summary(&self) -> String {
format!(
"Pressure: GPR={}/{} XMM={}/{} YMM={}/{} ZMM={}/{}",
self.pressure_stats.max_gpr_pressure,
self.max_pressure.get(&X86RegClass::GPR64).unwrap_or(&14),
self.pressure_stats.max_xmm_pressure,
self.max_pressure
.get(&X86RegClass::VECTOR128)
.unwrap_or(&16),
self.pressure_stats.max_ymm_pressure,
self.max_pressure
.get(&X86RegClass::VECTOR256)
.unwrap_or(&16),
self.pressure_stats.max_zmm_pressure,
self.max_pressure
.get(&X86RegClass::VECTOR512)
.unwrap_or(&32),
)
}
}
impl Default for X86RegisterPressure {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86CallingConventionAllocation {
pub arg_regs: Vec<u32>,
pub return_reg: u32,
pub return_reg2: u32,
pub callee_saved: Vec<u32>,
pub caller_saved: Vec<u32>,
pub xmm_arg_regs: Vec<u32>,
pub xmm_return_reg: u32,
pub sp_reg: u32,
pub fp_reg: u32,
pub emit_save_restore: bool,
}
impl X86CallingConventionAllocation {
pub fn new_system_v_amd64() -> Self {
Self {
arg_regs: vec![
x86_reg::RDI,
x86_reg::RSI,
x86_reg::RDX,
x86_reg::RCX,
x86_reg::R8,
x86_reg::R9,
],
return_reg: x86_reg::RAX,
return_reg2: x86_reg::RDX,
callee_saved: vec![
x86_reg::RBX,
x86_reg::RBP,
x86_reg::R12,
x86_reg::R13,
x86_reg::R14,
x86_reg::R15,
],
caller_saved: vec![
x86_reg::RAX,
x86_reg::RCX,
x86_reg::RDX,
x86_reg::RSI,
x86_reg::RDI,
x86_reg::R8,
x86_reg::R9,
x86_reg::R10,
x86_reg::R11,
],
xmm_arg_regs: (200..208).collect(),
xmm_return_reg: x86_reg::XMM0,
sp_reg: x86_reg::RSP,
fp_reg: x86_reg::RBP,
emit_save_restore: true,
}
}
pub fn new_windows_x64() -> Self {
Self {
arg_regs: vec![x86_reg::RCX, x86_reg::RDX, x86_reg::R8, x86_reg::R9],
return_reg: x86_reg::RAX,
return_reg2: x86_reg::RDX,
callee_saved: vec![
x86_reg::RBX,
x86_reg::RBP,
x86_reg::RDI,
x86_reg::RSI,
x86_reg::R12,
x86_reg::R13,
x86_reg::R14,
x86_reg::R15,
],
caller_saved: vec![
x86_reg::RAX,
x86_reg::RCX,
x86_reg::RDX,
x86_reg::R8,
x86_reg::R9,
x86_reg::R10,
x86_reg::R11,
],
xmm_arg_regs: (200..204).collect(),
xmm_return_reg: x86_reg::XMM0,
sp_reg: x86_reg::RSP,
fp_reg: x86_reg::RBP,
emit_save_restore: true,
}
}
pub fn assign_args(&self, args: &[(u32, X86RegClass)]) -> (HashMap<u32, u32>, Vec<(u32, i32)>) {
let mut reg_assignments = HashMap::new();
let mut stack_args = Vec::new();
let mut gpr_idx = 0;
let mut xmm_idx = 0;
for &(vreg, class) in args {
match class {
X86RegClass::GPR64
| X86RegClass::GPR32
| X86RegClass::GPR16
| X86RegClass::GPR8 => {
if gpr_idx < self.arg_regs.len() {
reg_assignments.insert(vreg, self.arg_regs[gpr_idx]);
gpr_idx += 1;
} else {
let stack_off = (gpr_idx - self.arg_regs.len()) as i32 * 8 + 16;
stack_args.push((vreg, stack_off));
gpr_idx += 1;
}
}
X86RegClass::VECTOR128 | X86RegClass::VECTOR256 | X86RegClass::VECTOR512 => {
if xmm_idx < self.xmm_arg_regs.len() {
reg_assignments.insert(vreg, self.xmm_arg_regs[xmm_idx]);
xmm_idx += 1;
} else {
let stack_off = (xmm_idx - self.xmm_arg_regs.len()) as i32 * 16 + 16;
stack_args.push((vreg, stack_off));
xmm_idx += 1;
}
}
_ => {}
}
}
(reg_assignments, stack_args)
}
pub fn get_return_reg(&self, class: X86RegClass) -> u32 {
match class {
X86RegClass::GPR64 | X86RegClass::GPR32 | X86RegClass::GPR16 | X86RegClass::GPR8 => {
self.return_reg
}
_ => self.xmm_return_reg,
}
}
pub fn get_callee_saved_to_save(&self, used_regs: &HashSet<u32>) -> Vec<u32> {
self.callee_saved
.iter()
.filter(|r| used_regs.contains(r))
.copied()
.collect()
}
pub fn is_arg_reg(&self, reg: u32) -> bool {
self.arg_regs.contains(®) || self.xmm_arg_regs.contains(®)
}
pub fn is_callee_saved(&self, reg: u32) -> bool {
self.callee_saved.contains(®)
}
pub fn summary(&self) -> String {
format!(
"CC: {} arg GPRs, {} arg XMMs, {} callee-saved",
self.arg_regs.len(),
self.xmm_arg_regs.len(),
self.callee_saved.len(),
)
}
}
impl Default for X86CallingConventionAllocation {
fn default() -> Self {
Self::new_system_v_amd64()
}
}
#[derive(Debug, Clone)]
pub struct X86MultiWayAllocator {
pub tuple_assignments: HashMap<u32, Vec<u32>>,
pub tuple_sizes: HashMap<u32, u32>,
pub free_ranges: HashMap<X86RegClass, Vec<(u32, u32)>>,
pub mw_stats: MultiWayStats,
}
#[derive(Debug, Clone, Default)]
pub struct MultiWayStats {
pub tuples_allocated: usize,
pub tuples_spilled: usize,
pub avg_tuple_size: f64,
pub fragmentation_count: usize,
}
impl X86MultiWayAllocator {
pub fn new() -> Self {
let mut free_ranges = HashMap::new();
free_ranges.insert(X86RegClass::VECTOR128, vec![(200, 216)]);
free_ranges.insert(X86RegClass::VECTOR256, vec![(300, 316)]);
free_ranges.insert(X86RegClass::VECTOR512, vec![(400, 432)]);
free_ranges.insert(X86RegClass::GPR64, vec![(0, 16)]);
Self {
tuple_assignments: HashMap::new(),
tuple_sizes: HashMap::new(),
free_ranges,
mw_stats: MultiWayStats::default(),
}
}
pub fn register_tuple(&mut self, vreg: u32, num_regs: u32) {
self.tuple_sizes.insert(vreg, num_regs);
}
pub fn allocate_tuple(
&mut self,
vreg: u32,
class: X86RegClass,
used_regs: &HashSet<u32>,
) -> Option<Vec<u32>> {
let num_needed = self.tuple_sizes.get(&vreg).copied().unwrap_or(1);
let ranges = self.free_ranges.get(&class).cloned().unwrap_or_default();
for &(start, end) in &ranges {
for candidate_start in start..end {
if candidate_start + num_needed > end {
break;
}
let all_free = (0..num_needed).all(|i| {
!used_regs.contains(&(candidate_start + i))
&& (class != X86RegClass::GPR64 || candidate_start + i != x86_reg::RSP)
&& (class != X86RegClass::GPR64 || candidate_start + i != x86_reg::RBP)
});
if all_free {
let regs: Vec<u32> = (0..num_needed).map(|i| candidate_start + i).collect();
self.tuple_assignments.insert(vreg, regs.clone());
self.mw_stats.tuples_allocated += 1;
self.mw_stats.avg_tuple_size = (self.mw_stats.avg_tuple_size
* (self.mw_stats.tuples_allocated - 1) as f64
+ num_needed as f64)
/ self.mw_stats.tuples_allocated as f64;
return Some(regs);
}
}
}
self.mw_stats.tuples_spilled += 1;
self.mw_stats.fragmentation_count += 1;
None
}
pub fn get_tuple(&self, vreg: u32) -> Option<&Vec<u32>> {
self.tuple_assignments.get(&vreg)
}
pub fn summary(&self) -> String {
format!(
"MultiWay: {} allocated, {} spilled, avg size {:.2}",
self.mw_stats.tuples_allocated,
self.mw_stats.tuples_spilled,
self.mw_stats.avg_tuple_size,
)
}
}
impl Default for X86MultiWayAllocator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86SpillCodeEmitter {
pub spill_ops: Vec<SpillOp>,
pub frame_objects: HashMap<i32, FrameObject>,
pub total_spill_frame: i32,
pub emitter_stats: EmitterStats,
}
#[derive(Debug, Clone, Copy)]
pub enum SpillOp {
SpillStore {
point: InstrPoint,
vreg: u32,
frame_idx: i32,
},
SpillLoad {
point: InstrPoint,
vreg: u32,
frame_idx: i32,
},
Remat {
point: InstrPoint,
vreg: u32,
remat_id: u32,
},
}
#[derive(Debug, Clone, Copy)]
pub struct FrameObject {
pub index: i32,
pub offset: i32,
pub size: u32,
pub alignment: u32,
pub is_spill_slot: bool,
}
#[derive(Debug, Clone, Default)]
pub struct EmitterStats {
pub store_ops: usize,
pub load_ops: usize,
pub remat_ops: usize,
pub frame_objects_created: usize,
pub spill_bytes: usize,
}
impl X86SpillCodeEmitter {
pub fn new() -> Self {
Self {
spill_ops: Vec::new(),
frame_objects: HashMap::new(),
total_spill_frame: 0,
emitter_stats: EmitterStats::default(),
}
}
pub fn create_frame_object(&mut self, size: u32, alignment: u32) -> i32 {
let idx = self.frame_objects.len() as i32;
let offset = self.total_spill_frame;
self.total_spill_frame += size as i32;
self.frame_objects.insert(
idx,
FrameObject {
index: idx,
offset,
size,
alignment,
is_spill_slot: true,
},
);
self.emitter_stats.frame_objects_created += 1;
self.emitter_stats.spill_bytes += size as usize;
idx
}
pub fn emit_store(&mut self, point: InstrPoint, vreg: u32, frame_idx: i32) {
self.spill_ops.push(SpillOp::SpillStore {
point,
vreg,
frame_idx,
});
self.emitter_stats.store_ops += 1;
}
pub fn emit_load(&mut self, point: InstrPoint, vreg: u32, frame_idx: i32) {
self.spill_ops.push(SpillOp::SpillLoad {
point,
vreg,
frame_idx,
});
self.emitter_stats.load_ops += 1;
}
pub fn emit_remat(&mut self, point: InstrPoint, vreg: u32, remat_id: u32) {
self.spill_ops.push(SpillOp::Remat {
point,
vreg,
remat_id,
});
self.emitter_stats.remat_ops += 1;
}
pub fn sorted_ops(&self) -> Vec<SpillOp> {
let mut ops = self.spill_ops.clone();
ops.sort_by_key(|op| match op {
SpillOp::SpillStore { point, .. } => *point,
SpillOp::SpillLoad { point, .. } => *point,
SpillOp::Remat { point, .. } => *point,
});
ops
}
pub fn optimize(&mut self) {
let mut i = 0;
while i + 1 < self.spill_ops.len() {
if let (
SpillOp::SpillStore {
vreg: v1,
frame_idx: f1,
..
},
SpillOp::SpillLoad {
vreg: v2,
frame_idx: f2,
..
},
) = (&self.spill_ops[i], &self.spill_ops[i + 1])
{
if v1 == v2 && f1 == f2 {
self.spill_ops.remove(i);
self.spill_ops.remove(i);
continue;
}
}
i += 1;
}
}
pub fn summary(&self) -> String {
format!(
"SpillCode: {} stores, {} loads, {} remats, {} bytes spilled",
self.emitter_stats.store_ops,
self.emitter_stats.load_ops,
self.emitter_stats.remat_ops,
self.emitter_stats.spill_bytes,
)
}
}
impl Default for X86SpillCodeEmitter {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86FullPbqpSolver {
pub graph: PbqpGraph,
pub reduction_stack: Vec<ReductionRecord>,
pub assignments: HashMap<u32, u32>,
pub total_cost: f64,
pub spills: HashMap<u32, i32>,
pub next_slot: i32,
pub solved: bool,
pub pbqp_stats: FullPbqpStats,
}
#[derive(Debug, Clone)]
pub enum ReductionRecord {
R0 {
vreg: u32,
best_reg: u32,
cost: f64,
},
R1 {
vreg: u32,
neighbor: u32,
delta_costs: Vec<(u32, f64)>,
},
R2 {
vreg: u32,
na: u32,
nb: u32,
edge_cost: PbqpMatrix,
},
RN {
vreg: u32,
removed_regs: Vec<u32>,
},
RM {
src: u32,
dst: u32,
removed_cols: Vec<usize>,
},
Spill {
vreg: u32,
slot: i32,
},
}
#[derive(Debug, Clone, Default)]
pub struct FullPbqpStats {
pub r0_count: usize,
pub r1_count: usize,
pub r2_count: usize,
pub rn_count: usize,
pub rm_count: usize,
pub spill_count: usize,
pub nodes_reduced: usize,
pub nodes_remaining: usize,
pub iterations: usize,
pub total_cost: f64,
pub coalescing_benefit: f64,
}
impl X86FullPbqpSolver {
pub fn new() -> Self {
Self {
graph: PbqpGraph::new(),
reduction_stack: Vec::new(),
assignments: HashMap::new(),
total_cost: 0.0,
spills: HashMap::new(),
next_slot: 0,
solved: false,
pbqp_stats: FullPbqpStats::default(),
}
}
pub fn build_graph(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
interferences: &[(u32, u32)],
coalescing: &[(u32, u32)],
allowed_regs: &HashMap<X86RegClass, Vec<u32>>,
) {
for (&vreg, iv) in intervals {
let class_allowed = allowed_regs.get(&iv.reg_class).cloned().unwrap_or_default();
let mut node = PbqpNode::new(vreg, &class_allowed, iv.spill_weight * 0.01);
if iv.is_fixed {
if let Some(fixed) = iv.fixed_reg {
for &r in &class_allowed {
if r != fixed {
node.restrict_reg(r);
}
}
}
}
self.graph.add_node(node);
}
for &(a, b) in interferences {
let edge = PbqpEdge::new(a, b, 16, 16);
self.graph.add_edge(edge);
}
for &(a, b) in coalescing {
let edge = PbqpEdge::with_coalescing_benefit(a, b, 16, 5.0);
self.graph.add_edge(edge);
self.pbqp_stats.coalescing_benefit += 5.0;
}
}
pub fn solve(&mut self) {
let max_iters = self.graph.nodes.len() * 2 + 100;
for _ in 0..max_iters {
if self.graph.nodes.is_empty() {
break;
}
self.pbqp_stats.iterations += 1;
if self.try_r0() {
continue;
}
if self.try_r1() {
continue;
}
if self.try_r2() {
continue;
}
if self.try_rn() {
continue;
}
if self.try_rm() {
continue;
}
self.spill_heuristic();
}
self.backpropagate_full();
self.solved = true;
self.pbqp_stats.nodes_reduced = self.reduction_stack.len();
self.pbqp_stats.nodes_remaining = self.graph.nodes.len();
self.pbqp_stats.total_cost = self.total_cost;
}
fn try_r0(&mut self) -> bool {
let independent: Vec<u32> = self
.graph
.nodes
.keys()
.filter(|v| self.graph.degree(**v) == 0)
.copied()
.collect();
if independent.is_empty() {
return false;
}
for vreg in independent {
if let Some(node) = self.graph.nodes.get(&vreg).cloned() {
if let Some((best, cost)) = node.costs.min_cost_reg() {
self.reduction_stack.push(ReductionRecord::R0 {
vreg,
best_reg: best,
cost,
});
self.pbqp_stats.r0_count += 1;
} else {
let slot = self.next_slot;
self.next_slot += 8;
self.reduction_stack
.push(ReductionRecord::Spill { vreg, slot });
self.pbqp_stats.spill_count += 1;
}
}
self.graph.remove_node(vreg);
}
true
}
fn try_r1(&mut self) -> bool {
let d1: Vec<u32> = self
.graph
.nodes
.keys()
.filter(|v| self.graph.degree(**v) == 1)
.copied()
.collect();
if d1.is_empty() {
return false;
}
for vreg in d1 {
let neighbors = self.graph.neighbors(vreg);
if neighbors.is_empty() {
continue;
}
let neighbor = neighbors[0];
if let Some(node) = self.graph.nodes.get(&vreg).cloned() {
let mut delta = Vec::new();
if let Some(nbr) = self.graph.nodes.get(&neighbor) {
for &nbr_reg in &nbr.costs.idx_to_reg {
let mut min_cost = f64::MAX;
for &vreg_reg in &node.costs.idx_to_reg {
let cost = node.costs.get_cost(vreg_reg).unwrap_or(PBQP_INF);
let edge_cost = if vreg_reg == nbr_reg { PBQP_INF } else { 0.0 };
min_cost = min_cost.min(cost + edge_cost);
}
if min_cost < PBQP_INF / 2.0 {
delta.push((nbr_reg, min_cost));
}
}
}
self.reduction_stack.push(ReductionRecord::R1 {
vreg,
neighbor,
delta_costs: delta,
});
self.pbqp_stats.r1_count += 1;
}
self.graph.remove_node(vreg);
}
true
}
fn try_r2(&mut self) -> bool {
let d2: Vec<u32> = self
.graph
.nodes
.keys()
.filter(|v| self.graph.degree(**v) == 2)
.copied()
.collect();
if d2.is_empty() {
return false;
}
for vreg in d2 {
let neighbors = self.graph.neighbors(vreg);
if neighbors.len() != 2 {
continue;
}
let na = neighbors[0];
let nb = neighbors[1];
let numa = self
.graph
.nodes
.get(&na)
.map(|n| n.costs.num_choices())
.unwrap_or(16);
let numb = self
.graph
.nodes
.get(&nb)
.map(|n| n.costs.num_choices())
.unwrap_or(16);
let reduced_edge = PbqpMatrix::new(numa, numb);
self.reduction_stack.push(ReductionRecord::R2 {
vreg,
na,
nb,
edge_cost: reduced_edge,
});
self.pbqp_stats.r2_count += 1;
self.graph.remove_node(vreg);
self.graph.add_edge(PbqpEdge::new(na, nb, numa, numb));
}
true
}
fn try_rn(&mut self) -> bool {
let mut found = false;
let vregs: Vec<u32> = self.graph.nodes.keys().copied().collect();
for vreg in vregs {
if let Some(node) = self.graph.nodes.get(&vreg) {
let mut redundant = Vec::new();
let num = node.costs.num_choices();
for i in 0..num {
let reg_i = node.costs.idx_to_reg[i];
let cost_i = node.costs.costs[i];
if cost_i >= PBQP_INF / 2.0 {
continue;
}
for j in 0..num {
if i == j {
continue;
}
let cost_j = node.costs.costs[j];
if cost_j >= PBQP_INF / 2.0 {
continue;
}
if cost_j <= cost_i && !redundant.contains(®_i) {
redundant.push(reg_i);
break;
}
}
}
if !redundant.is_empty() {
self.reduction_stack.push(ReductionRecord::RN {
vreg,
removed_regs: redundant,
});
self.pbqp_stats.rn_count += 1;
found = true;
}
}
}
found
}
fn try_rm(&mut self) -> bool {
if self.graph.edges.is_empty() {
return false;
}
let mut found = false;
for idx in 0..self.graph.edges.len() {
let edge = &self.graph.edges[idx];
if edge.reduced {
continue;
}
let mut dominated_cols = Vec::new();
for col_a in 0..edge.costs.cols {
for col_b in 0..edge.costs.cols {
if col_a == col_b {
continue;
}
let dominates = (0..edge.costs.rows)
.all(|row| edge.costs.matrix[row][col_a] <= edge.costs.matrix[row][col_b]);
if dominates && !dominated_cols.contains(&col_b) {
dominated_cols.push(col_b);
}
}
}
if !dominated_cols.is_empty() {
self.reduction_stack.push(ReductionRecord::RM {
src: edge.src,
dst: edge.dst,
removed_cols: dominated_cols,
});
self.pbqp_stats.rm_count += 1;
found = true;
}
}
found
}
fn spill_heuristic(&mut self) {
let mut best_vreg: Option<u32> = None;
let mut best_ratio = 0.0f64;
for (&vreg, node) in &self.graph.nodes {
let degree = self.graph.degree(vreg).max(1) as f64;
let min_cost = node
.costs
.costs
.iter()
.filter(|&&c| c < PBQP_INF / 2.0)
.fold(f64::MAX, |a, &b| a.min(b));
let ratio = min_cost / degree;
if ratio > best_ratio {
best_ratio = ratio;
best_vreg = Some(vreg);
}
}
if let Some(vreg) = best_vreg {
let slot = self.next_slot;
self.next_slot += 8;
self.reduction_stack
.push(ReductionRecord::Spill { vreg, slot });
self.pbqp_stats.spill_count += 1;
self.graph.remove_node(vreg);
}
}
fn backpropagate_full(&mut self) {
while let Some(record) = self.reduction_stack.pop() {
match record {
ReductionRecord::R0 {
vreg,
best_reg,
cost,
} => {
self.assignments.insert(vreg, best_reg);
self.total_cost += cost;
}
ReductionRecord::R1 {
vreg,
neighbor,
delta_costs,
} => {
if let Some(&nbr_reg) = self.assignments.get(&neighbor) {
let extra = delta_costs
.iter()
.find(|(r, _)| *r == nbr_reg)
.map(|(_, c)| *c)
.unwrap_or(0.0);
self.total_cost += extra;
if let Some(node) = self.graph.nodes.get(&vreg) {
let best = node
.costs
.idx_to_reg
.iter()
.filter(|&&r| r != nbr_reg) .min_by(|&&a, &&b| {
let ca = node.costs.get_cost(a).unwrap_or(PBQP_INF);
let cb = node.costs.get_cost(b).unwrap_or(PBQP_INF);
ca.partial_cmp(&cb).unwrap_or(Ordering::Equal)
})
.copied()
.unwrap_or(nbr_reg);
self.assignments.insert(vreg, best);
}
}
}
ReductionRecord::R2 {
vreg,
na: _,
nb: _,
edge_cost: _,
} => {
if let Some(node) = self.graph.nodes.get(&vreg) {
if let Some((reg, cost)) = node.costs.min_cost_reg() {
self.assignments.insert(vreg, reg);
self.total_cost += cost;
}
}
}
ReductionRecord::RN {
vreg,
removed_regs: _,
} => {
if let Some(node) = self.graph.nodes.get(&vreg) {
if let Some((reg, cost)) = node.costs.min_cost_reg() {
self.assignments.insert(vreg, reg);
self.total_cost += cost;
}
}
}
ReductionRecord::RM { .. } => {
}
ReductionRecord::Spill { vreg, slot } => {
self.spills.insert(vreg, slot);
self.pbqp_stats.spill_count += 1;
}
}
}
}
pub fn summary(&self) -> String {
format!(
"FullPBQP: R0={} R1={} R2={} RN={} RM={}, {} spills, cost={:.2}",
self.pbqp_stats.r0_count,
self.pbqp_stats.r1_count,
self.pbqp_stats.r2_count,
self.pbqp_stats.rn_count,
self.pbqp_stats.rm_count,
self.pbqp_stats.spill_count,
self.pbqp_stats.total_cost,
)
}
}
impl Default for X86FullPbqpSolver {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegisterHintPropagator {
pub copy_graph: HashMap<u32, HashSet<u32>>,
pub hints: HashMap<u32, u32>,
pub confidence: HashMap<u32, f64>,
}
impl X86RegisterHintPropagator {
pub fn new() -> Self {
Self {
copy_graph: HashMap::new(),
hints: HashMap::new(),
confidence: HashMap::new(),
}
}
pub fn add_copy(&mut self, dst: u32, src: u32) {
self.copy_graph.entry(dst).or_default().insert(src);
self.copy_graph.entry(src).or_default().insert(dst);
}
pub fn set_hint(&mut self, vreg: u32, phys_reg: u32, confidence: f64) {
self.hints.insert(vreg, phys_reg);
self.confidence.insert(vreg, confidence);
}
pub fn propagate(&mut self) {
let mut queue: VecDeque<u32> = self.hints.keys().copied().collect();
let mut visited: HashSet<u32> = self.hints.keys().copied().collect();
while let Some(vreg) = queue.pop_front() {
let hint = match self.hints.get(&vreg) {
Some(&h) => h,
None => continue,
};
let conf = self.confidence.get(&vreg).copied().unwrap_or(1.0);
if let Some(neighbors) = self.copy_graph.get(&vreg).cloned() {
for neighbor in neighbors {
if !visited.contains(&neighbor) {
self.hints.insert(neighbor, hint);
self.confidence.insert(neighbor, conf * 0.9);
visited.insert(neighbor);
queue.push_back(neighbor);
}
}
}
}
}
pub fn get_hint(&self, vreg: u32) -> Option<u32> {
self.hints.get(&vreg).copied()
}
pub fn connected_component(&self, vreg: u32) -> HashSet<u32> {
let mut component = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(vreg);
while let Some(v) = queue.pop_front() {
if !component.insert(v) {
continue;
}
if let Some(neighbors) = self.copy_graph.get(&v) {
for &n in neighbors {
if !component.contains(&n) {
queue.push_back(n);
}
}
}
}
component
}
pub fn summary(&self) -> String {
format!(
"Hints: {} direct, {} in copy graph",
self.hints.len(),
self.copy_graph.len(),
)
}
}
impl Default for X86RegisterHintPropagator {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86InterferenceGraph {
pub edges: HashMap<u32, HashSet<u32>>,
pub degree: HashMap<u32, usize>,
pub components: Vec<HashSet<u32>>,
pub coloring_order: Vec<u32>,
pub interference_ranges: HashMap<(u32, u32), Vec<X86LiveSegment>>,
pub built: bool,
pub ig_stats: InterferenceGraphStats,
}
#[derive(Debug, Clone, Default)]
pub struct InterferenceGraphStats {
pub total_nodes: usize,
pub total_edges: usize,
pub max_degree: usize,
pub avg_degree: f64,
pub num_components: usize,
pub largest_component: usize,
pub isolated_nodes: usize,
pub build_time_us: u64,
}
impl X86InterferenceGraph {
pub fn new() -> Self {
Self {
edges: HashMap::new(),
degree: HashMap::new(),
components: Vec::new(),
coloring_order: Vec::new(),
interference_ranges: HashMap::new(),
built: false,
ig_stats: InterferenceGraphStats::default(),
}
}
pub fn build(&mut self, intervals: &HashMap<u32, X86LiveInterval>) {
self.clear();
let vregs: Vec<u32> = intervals.keys().copied().collect();
self.ig_stats.total_nodes = vregs.len();
for i in 0..vregs.len() {
let a = vregs[i];
let iv_a = match intervals.get(&a) {
Some(iv) => iv,
None => continue,
};
self.edges.entry(a).or_default();
self.degree.entry(a).or_insert(0);
for j in (i + 1)..vregs.len() {
let b = vregs[j];
let iv_b = match intervals.get(&b) {
Some(iv) => iv,
None => continue,
};
if iv_a.reg_class != iv_b.reg_class
&& !Self::classes_overlap(iv_a.reg_class, iv_b.reg_class)
{
continue;
}
if iv_a.overlaps_with(iv_b) {
let inter = iv_a.intersect_with(iv_b);
if !inter.is_empty() {
self.edges.entry(a).or_default().insert(b);
self.edges.entry(b).or_default().insert(a);
*self.degree.entry(a).or_default() += 1;
*self.degree.entry(b).or_default() += 1;
self.interference_ranges.insert((a, b), inter);
self.ig_stats.total_edges += 1;
}
}
}
}
if let Some(d) = self.degree.values().max() {
self.ig_stats.max_degree = *d;
}
if self.ig_stats.total_nodes > 0 {
let total_deg: usize = self.degree.values().sum();
self.ig_stats.avg_degree = total_deg as f64 / self.ig_stats.total_nodes as f64;
}
self.ig_stats.isolated_nodes = self.degree.values().filter(|&&d| d == 0).count();
self.built = true;
}
fn classes_overlap(a: X86RegClass, b: X86RegClass) -> bool {
use X86RegClass::*;
if a == b {
return true;
}
match (a, b) {
(GPR64, GPR32)
| (GPR32, GPR64)
| (GPR64, GPR16)
| (GPR16, GPR64)
| (GPR64, GPR8)
| (GPR8, GPR64)
| (GPR32, GPR16)
| (GPR16, GPR32)
| (GPR32, GPR8)
| (GPR8, GPR32)
| (GPR16, GPR8)
| (GPR8, GPR16) => true,
_ => false,
}
}
pub fn compute_components(&mut self) {
let mut visited: HashSet<u32> = HashSet::new();
self.components.clear();
let all_nodes: Vec<u32> = self.edges.keys().copied().collect();
for &node in &all_nodes {
if visited.contains(&node) {
continue;
}
let mut component = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(node);
visited.insert(node);
while let Some(v) = queue.pop_front() {
component.insert(v);
if let Some(neighbors) = self.edges.get(&v) {
for &n in neighbors {
if visited.insert(n) {
queue.push_back(n);
}
}
}
}
self.components.push(component);
}
self.ig_stats.num_components = self.components.len();
self.ig_stats.largest_component =
self.components.iter().map(|c| c.len()).max().unwrap_or(0);
}
pub fn interferes(&self, a: u32, b: u32) -> bool {
self.edges.get(&a).map(|n| n.contains(&b)).unwrap_or(false)
}
pub fn degree_of(&self, vreg: u32) -> usize {
self.degree.get(&vreg).copied().unwrap_or(0)
}
pub fn compute_coloring_order(&mut self, k: usize) {
let mut remaining: HashSet<u32> = self.edges.keys().copied().collect();
let mut order = Vec::new();
let mut spill_candidates = Vec::new();
let mut current_degrees: HashMap<u32, usize> = self.degree.clone();
loop {
let low_degree: Option<u32> = remaining
.iter()
.find(|v| current_degrees.get(v).copied().unwrap_or(0) < k)
.copied();
match low_degree {
Some(v) => {
remaining.remove(&v);
order.push(v);
if let Some(neighbors) = self.edges.get(&v) {
for &n in neighbors {
if remaining.contains(&n) {
*current_degrees.entry(n).or_default() =
current_degrees.get(&n).copied().unwrap_or(1) - 1;
}
}
}
}
None => {
if remaining.is_empty() {
break;
}
let spill = remaining.iter().copied().next().unwrap();
remaining.remove(&spill);
spill_candidates.push(spill);
}
}
}
spill_candidates.reverse();
order.reverse();
self.coloring_order = spill_candidates;
self.coloring_order.extend(order);
}
pub fn containing_component(&self, vreg: u32) -> Option<usize> {
self.components.iter().position(|c| c.contains(&vreg))
}
pub fn component_of(&self, vreg: u32) -> HashSet<u32> {
if let Some(idx) = self.containing_component(vreg) {
self.components[idx].clone()
} else {
HashSet::new()
}
}
pub fn clear(&mut self) {
self.edges.clear();
self.degree.clear();
self.components.clear();
self.coloring_order.clear();
self.interference_ranges.clear();
self.built = false;
self.ig_stats = InterferenceGraphStats::default();
self.edges.clear();
}
pub fn summary(&self) -> String {
format!(
"InterferenceGraph: {} nodes, {} edges, max degree {}, {} components",
self.ig_stats.total_nodes,
self.ig_stats.total_edges,
self.ig_stats.max_degree,
self.ig_stats.num_components,
)
}
}
impl Default for X86InterferenceGraph {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegisterCoalescing {
pub copies: Vec<(u32, u32, InstrPoint)>,
pub coalesced: Vec<(u32, u32)>,
pub interference: X86InterferenceGraph,
pub intervals: HashMap<u32, X86LiveInterval>,
pub aggressive: bool,
pub coal_stats: CoalescingStats,
}
#[derive(Debug, Clone, Default)]
pub struct CoalescingStats {
pub copies_found: usize,
pub copies_coalesced: usize,
pub copies_split: usize,
pub briggs_checks: usize,
pub george_checks: usize,
pub aggressive_merged: usize,
pub coalescing_aborted: usize,
pub time_us: u64,
}
impl X86RegisterCoalescing {
pub fn new() -> Self {
Self {
copies: Vec::new(),
coalesced: Vec::new(),
interference: X86InterferenceGraph::new(),
intervals: HashMap::new(),
aggressive: false,
coal_stats: CoalescingStats::default(),
}
}
pub fn with_aggressive(mut self, enabled: bool) -> Self {
self.aggressive = enabled;
self
}
pub fn register_copy(&mut self, dst: u32, src: u32, point: InstrPoint) {
self.copies.push((dst, src, point));
self.coal_stats.copies_found += 1;
}
pub fn add_interval(&mut self, iv: X86LiveInterval) {
self.intervals.insert(iv.vreg, iv);
}
pub fn build_interference(&mut self) {
self.interference.build(&self.intervals);
self.interference.compute_components();
}
pub fn coalesce(&mut self) {
if self.interference.ig_stats.total_nodes == 0 {
self.build_interference();
}
let mut sorted_copies = self.copies.clone();
sorted_copies.sort_by(|(a, _, _), (b, _, _)| {
let wa = self
.intervals
.get(a)
.map(|iv| iv.spill_weight)
.unwrap_or(0.0);
let wb = self
.intervals
.get(b)
.map(|iv| iv.spill_weight)
.unwrap_or(0.0);
wb.partial_cmp(&wa).unwrap_or(Ordering::Equal)
});
for (dst, src, _point) in &sorted_copies {
if *dst == *src {
continue;
}
if !self.coalescing_eligible(*dst, *src) {
continue;
}
let k = self.allocatable_count_for(*dst);
if self.aggressive {
if !self.interference.interferes(*dst, *src) {
self.perform_coalesce(*dst, *src);
self.coal_stats.aggressive_merged += 1;
continue;
}
}
self.coal_stats.briggs_checks += 1;
if self.briggs_test(*dst, *src, k) {
self.perform_coalesce(*dst, *src);
self.coal_stats.copies_coalesced += 1;
continue;
}
self.coal_stats.george_checks += 1;
if self.george_test(*dst, *src, k) {
self.perform_coalesce(*dst, *src);
self.coal_stats.copies_coalesced += 1;
continue;
}
self.coal_stats.copies_split += 1;
}
}
fn coalescing_eligible(&self, dst: u32, src: u32) -> bool {
let iv_dst = match self.intervals.get(&dst) {
Some(iv) => iv,
None => return false,
};
let iv_src = match self.intervals.get(&src) {
Some(iv) => iv,
None => return false,
};
if iv_dst.reg_class != iv_src.reg_class {
return false;
}
if iv_dst.is_fixed || iv_src.is_fixed {
return false;
}
if iv_dst.overlaps_with(iv_src) && !self.aggressive {
return false;
}
true
}
fn briggs_test(&self, u: u32, v: u32, k: usize) -> bool {
let neighbors_u = self.interference.edges.get(&u).cloned().unwrap_or_default();
let neighbors_v = self.interference.edges.get(&v).cloned().unwrap_or_default();
let combined: HashSet<u32> = neighbors_u.union(&neighbors_v).copied().collect();
let significant_neighbors = combined
.iter()
.filter(|&&n| self.interference.degree_of(n) >= k)
.count();
significant_neighbors < k
}
fn george_test(&self, u: u32, v: u32, k: usize) -> bool {
let neighbors_u = self.interference.edges.get(&u).cloned().unwrap_or_default();
let neighbors_v = self.interference.edges.get(&v).cloned().unwrap_or_default();
for &t in &neighbors_u {
if t == v {
continue;
}
let interferes_with_v = neighbors_v.contains(&t);
let low_degree = self.interference.degree_of(t) < k;
if !interferes_with_v && !low_degree {
return false;
}
}
true
}
fn perform_coalesce(&mut self, dst: u32, src: u32) {
if let (Some(iv_dst), Some(iv_src)) = (
self.intervals.get(&dst).cloned(),
self.intervals.get(&src).cloned(),
) {
let merged = iv_dst.union_with(&iv_src);
self.intervals.insert(dst, merged);
self.intervals.remove(&src);
}
if let Some(src_neighbors) = self.interference.edges.remove(&src) {
for neighbor in &src_neighbors {
if *neighbor == dst {
continue;
}
self.interference
.edges
.entry(dst)
.or_default()
.insert(*neighbor);
if let Some(ns) = self.interference.edges.get_mut(neighbor) {
ns.remove(&src);
ns.insert(dst);
}
}
}
self.interference.degree.remove(&src);
let new_deg = self
.interference
.edges
.get(&dst)
.map(|n| n.len())
.unwrap_or(0);
self.interference.degree.insert(dst, new_deg);
self.coalesced.push((dst, src));
}
fn allocatable_count_for(&self, vreg: u32) -> usize {
if let Some(iv) = self.intervals.get(&vreg) {
iv.reg_class.allocatable_regs().len()
} else {
14 }
}
pub fn get_coalesced(&self, vreg: u32) -> Option<u32> {
for &(dst, src) in &self.coalesced {
if src == vreg {
return Some(dst);
}
}
for &(dst, src) in &self.coalesced {
if src == vreg {
return self.get_coalesced(dst).or(Some(dst));
}
}
None
}
pub fn can_eliminate_copy(&self, dst: u32, src: u32) -> bool {
if dst == src {
return true;
}
if let Some(c_dst) = self.get_coalesced(dst) {
if let Some(c_src) = self.get_coalesced(src) {
return c_dst == c_src;
}
return c_dst == src;
}
if let Some(c_src) = self.get_coalesced(src) {
return dst == c_src;
}
false
}
pub fn summary(&self) -> String {
format!(
"Coalescing: {} copies, {} coalesced (Briggs:{}, George:{}, Aggr:{}), {} split",
self.coal_stats.copies_found,
self.coal_stats.copies_coalesced,
self.coal_stats.briggs_checks,
self.coal_stats.george_checks,
self.coal_stats.aggressive_merged,
self.coal_stats.copies_split,
)
}
}
impl Default for X86RegisterCoalescing {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegAllocStats {
pub spills: SpillStats,
pub copies: CopyStats,
pub usage: RegisterUsageStats,
pub timing: TimingStats,
pub quality: QualityStats,
pub per_block: HashMap<u32, BlockAllocStats>,
pub strategy: String,
}
#[derive(Debug, Clone, Default)]
pub struct SpillStats {
pub total_spills: usize,
pub total_reloads: usize,
pub spill_slots_used: usize,
pub spill_slots_coalesced: usize,
pub bytes_spilled: usize,
pub spills_in_loops: usize,
pub remat_count: usize,
pub loads_inserted: usize,
pub stores_inserted: usize,
}
#[derive(Debug, Clone, Default)]
pub struct CopyStats {
pub copies_before: usize,
pub copies_after: usize,
pub copies_eliminated: usize,
pub coalescing_attempts: usize,
pub coalescing_successes: usize,
pub briggs_successes: usize,
pub george_successes: usize,
pub aggressive_successes: usize,
}
#[derive(Debug, Clone, Default)]
pub struct RegisterUsageStats {
pub gpr8_assigned: usize,
pub gpr16_assigned: usize,
pub gpr32_assigned: usize,
pub gpr64_assigned: usize,
pub xmm_assigned: usize,
pub ymm_assigned: usize,
pub zmm_assigned: usize,
pub max_gpr_pressure: usize,
pub max_xmm_pressure: usize,
pub max_ymm_pressure: usize,
pub max_zmm_pressure: usize,
pub avg_register_pressure: f64,
pub registers_touched: usize,
pub callee_saved_used: usize,
pub caller_saved_used: usize,
}
#[derive(Debug, Clone, Default)]
pub struct TimingStats {
pub live_interval_computation_us: u64,
pub interference_graph_build_us: u64,
pub coalescing_us: u64,
pub allocation_us: u64,
pub splitting_us: u64,
pub spill_code_insertion_us: u64,
pub eviction_analysis_us: u64,
pub post_processing_us: u64,
pub total_us: u64,
}
#[derive(Debug, Clone, Default)]
pub struct QualityStats {
pub spill_code_ratio: f64,
pub copy_elimination_ratio: f64,
pub register_utilization: f64,
pub allocation_density: f64,
pub estimated_cycles: u64,
pub code_size_estimate: usize,
}
#[derive(Debug, Clone, Default)]
pub struct BlockAllocStats {
pub vregs_defined: usize,
pub vregs_used: usize,
pub spills_in_block: usize,
pub reloads_in_block: usize,
pub copies_in_block: usize,
pub live_in_count: usize,
pub live_out_count: usize,
pub max_pressure: usize,
}
impl X86RegAllocStats {
pub fn new() -> Self {
Self {
spills: SpillStats::default(),
copies: CopyStats::default(),
usage: RegisterUsageStats::default(),
timing: TimingStats::default(),
quality: QualityStats::default(),
per_block: HashMap::new(),
strategy: String::new(),
}
}
pub fn with_strategy(mut self, name: &str) -> Self {
self.strategy = name.to_string();
self
}
pub fn record_spill(&mut self, in_loop: bool, bytes: usize) {
self.spills.total_spills += 1;
self.spills.bytes_spilled += bytes;
self.spills.stores_inserted += 1;
if in_loop {
self.spills.spills_in_loops += 1;
}
}
pub fn record_reload(&mut self, bytes: usize) {
self.spills.total_reloads += 1;
self.spills.bytes_spilled += bytes;
self.spills.loads_inserted += 1;
}
pub fn record_spill_slot(&mut self, coalesced: bool) {
self.spills.spill_slots_used += 1;
if coalesced {
self.spills.spill_slots_coalesced += 1;
}
}
pub fn record_remat(&mut self) {
self.spills.remat_count += 1;
}
pub fn record_copy_stats(&mut self, before: usize, after: usize) {
self.copies.copies_before = self.copies.copies_before.max(before);
self.copies.copies_after = after;
self.copies.copies_eliminated = before.saturating_sub(after);
}
pub fn record_coalescing(&mut self, success: bool, method: &str) {
self.copies.coalescing_attempts += 1;
if success {
self.copies.coalescing_successes += 1;
match method {
"briggs" => self.copies.briggs_successes += 1,
"george" => self.copies.george_successes += 1,
"aggressive" => self.copies.aggressive_successes += 1,
_ => {}
}
}
}
pub fn record_assignment(&mut self, class: X86RegClass) {
use X86RegClass::*;
match class {
GPR8 => self.usage.gpr8_assigned += 1,
GPR16 => self.usage.gpr16_assigned += 1,
GPR32 => self.usage.gpr32_assigned += 1,
GPR64 => self.usage.gpr64_assigned += 1,
VECTOR128 => self.usage.xmm_assigned += 1,
VECTOR256 => self.usage.ymm_assigned += 1,
VECTOR512 => self.usage.zmm_assigned += 1,
_ => {}
}
}
pub fn record_pressure(&mut self, gpr: usize, xmm: usize, ymm: usize, zmm: usize) {
self.usage.max_gpr_pressure = self.usage.max_gpr_pressure.max(gpr);
self.usage.max_xmm_pressure = self.usage.max_xmm_pressure.max(xmm);
self.usage.max_ymm_pressure = self.usage.max_ymm_pressure.max(ymm);
self.usage.max_zmm_pressure = self.usage.max_zmm_pressure.max(zmm);
}
pub fn record_saved_reg_usage(&mut self, callee: usize, caller: usize) {
self.usage.callee_saved_used += callee;
self.usage.caller_saved_used += caller;
}
pub fn record_block_stats(&mut self, block: u32, stats: BlockAllocStats) {
self.per_block.insert(block, stats);
}
pub fn compute_quality(&mut self, total_instructions: usize) {
let spill_ops = self.spills.total_spills + self.spills.total_reloads;
if total_instructions > 0 {
self.quality.spill_code_ratio = spill_ops as f64 / total_instructions as f64;
}
if self.copies.copies_before > 0 {
self.quality.copy_elimination_ratio =
self.copies.copies_eliminated as f64 / self.copies.copies_before as f64;
}
let total_assignments = self.usage.gpr64_assigned
+ self.usage.xmm_assigned
+ self.usage.ymm_assigned
+ self.usage.zmm_assigned;
let max_possible = 14 + 16 + 16 + 32; if max_possible > 0 {
self.quality.register_utilization = total_assignments as f64 / max_possible as f64;
}
self.quality.code_size_estimate = total_instructions * 4; }
pub fn detailed_report(&self) -> String {
let mut r = String::new();
r.push_str("╔══════════════════════════════════════════════════╗\n");
r.push_str(&format!("║ {:^48} ║\n", "X86 Register Allocation Report"));
r.push_str("╠══════════════════════════════════════════════════╣\n");
r.push_str(&format!("║ Strategy: {:<39} ║\n", self.strategy));
r.push_str("╠══════════════════════════════════════════════════╣\n");
r.push_str(&format!(
"║ Spills: {:<3} Reloads: {:<3} Slots: {:<3} ║\n",
self.spills.total_spills, self.spills.total_reloads, self.spills.spill_slots_used,
));
r.push_str(&format!(
"║ Remat: {:<3} Loop spills: {:<3} Bytes: {:<5} ║\n",
self.spills.remat_count, self.spills.spills_in_loops, self.spills.bytes_spilled,
));
r.push_str("╟──────────────────────────────────────────────────╢\n");
r.push_str(&format!(
"║ Copies: before={:<3} after={:<3} elim={:<3} ║\n",
self.copies.copies_before, self.copies.copies_after, self.copies.copies_eliminated,
));
r.push_str(&format!(
"║ Coalescing: {:<3} attempts, {:<3} successes ║\n",
self.copies.coalescing_attempts, self.copies.coalescing_successes,
));
r.push_str("╟──────────────────────────────────────────────────╢\n");
r.push_str(&format!(
"║ GPR64: {:<3} GPR32: {:<3} GPR16: {:<3} GPR8: {:<3} ║\n",
self.usage.gpr64_assigned,
self.usage.gpr32_assigned,
self.usage.gpr16_assigned,
self.usage.gpr8_assigned,
));
r.push_str(&format!(
"║ XMM: {:<3} YMM: {:<3} ZMM: {:<3} ║\n",
self.usage.xmm_assigned, self.usage.ymm_assigned, self.usage.zmm_assigned,
));
r.push_str("╟──────────────────────────────────────────────────╢\n");
r.push_str(&format!(
"║ Max Pressure — GPR:{:<3} XMM:{:<3} YMM:{:<3} ZMM:{:<3} ║\n",
self.usage.max_gpr_pressure,
self.usage.max_xmm_pressure,
self.usage.max_ymm_pressure,
self.usage.max_zmm_pressure,
));
r.push_str("╟──────────────────────────────────────────────────╢\n");
r.push_str(&format!(
"║ Spill ratio: {:.2}% Copy elim: {:.2}% ║\n",
self.quality.spill_code_ratio * 100.0,
self.quality.copy_elimination_ratio * 100.0,
));
r.push_str(&format!(
"║ Reg util: {:.2}% Code size est: {}B ║\n",
self.quality.register_utilization * 100.0,
self.quality.code_size_estimate,
));
r.push_str("╚══════════════════════════════════════════════════╝\n");
r
}
pub fn summary(&self) -> String {
format!(
"RA Stats[{}]: spills={}, reloads={}, slots={}, remat={}, copies_before={}, after={}",
self.strategy,
self.spills.total_spills,
self.spills.total_reloads,
self.spills.spill_slots_used,
self.spills.remat_count,
self.copies.copies_before,
self.copies.copies_after,
)
}
}
impl Default for X86RegAllocStats {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86AllocationVerifier {
pub errors: Vec<VerificationError>,
pub warnings: Vec<String>,
pub verified: bool,
pub strict: bool,
}
#[derive(Debug, Clone)]
pub enum VerificationError {
RegisterConflict {
vreg_a: u32,
vreg_b: u32,
phys_reg: u32,
overlap: X86LiveSegment,
},
FixedRegisterViolation {
vreg: u32,
expected: u32,
assigned: u32,
},
UnassignedVreg { vreg: u32 },
MissingSpillCode { vreg: u32, point: InstrPoint },
ClassMismatch {
vreg: u32,
expected: X86RegClass,
assigned_class: X86RegClass,
},
CalleeSavedNotSaved { phys_reg: u32 },
StackPointerUsed,
BasePointerUsed,
}
impl X86AllocationVerifier {
pub fn new() -> Self {
Self {
errors: Vec::new(),
warnings: Vec::new(),
verified: false,
strict: false,
}
}
pub fn with_strict(mut self, enabled: bool) -> Self {
self.strict = enabled;
self
}
pub fn verify(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
assignments: &HashMap<u32, u32>,
spilled: &HashSet<u32>,
used_regs: &HashSet<u32>,
callee_saved: &[u32],
) -> bool {
self.errors.clear();
self.warnings.clear();
self.verify_register_conflicts(intervals, assignments);
self.verify_fixed_registers(intervals, assignments);
self.verify_spilled_registers(intervals, spilled);
self.verify_class_constraints(intervals, assignments);
self.verify_callee_saved(used_regs, callee_saved);
self.verify_reserved_registers(assignments);
self.verified = self.errors.is_empty();
if self.strict {
self.verified = self.verified && self.warnings.is_empty();
}
self.verified
}
fn verify_register_conflicts(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
assignments: &HashMap<u32, u32>,
) {
let vregs: Vec<u32> = intervals.keys().copied().collect();
for i in 0..vregs.len() {
let a = vregs[i];
let iv_a = match intervals.get(&a) {
Some(iv) => iv,
None => continue,
};
let reg_a = match assignments.get(&a) {
Some(&r) => r,
None => continue,
};
for j in (i + 1)..vregs.len() {
let b = vregs[j];
let iv_b = match intervals.get(&b) {
Some(iv) => iv,
None => continue,
};
let reg_b = match assignments.get(&b) {
Some(&r) => r,
None => continue,
};
if reg_a != reg_b {
continue;
}
if iv_a.overlaps_with(iv_b) {
let inter = iv_a.intersect_with(iv_b);
if let Some(overlap) = inter.first() {
self.errors.push(VerificationError::RegisterConflict {
vreg_a: a,
vreg_b: b,
phys_reg: reg_a,
overlap: *overlap,
});
}
}
}
}
}
fn verify_fixed_registers(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
assignments: &HashMap<u32, u32>,
) {
for (&vreg, iv) in intervals {
if !iv.is_fixed {
continue;
}
let expected = match iv.fixed_reg {
Some(r) => r,
None => continue,
};
match assignments.get(&vreg) {
Some(&assigned) if assigned == expected => { }
Some(&assigned) => {
self.errors.push(VerificationError::FixedRegisterViolation {
vreg,
expected,
assigned,
});
}
None => {
self.warnings.push(format!(
"Fixed vreg {} (phys_reg={}) was not assigned",
vreg, expected,
));
}
}
}
}
fn verify_spilled_registers(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
spilled: &HashSet<u32>,
) {
for &vreg in spilled {
if let Some(iv) = intervals.get(&vreg) {
if !iv.spilled {
self.warnings.push(format!(
"vreg {} marked spilled but interval not flagged",
vreg
));
}
if iv.spill_offset < 0 {
self.errors.push(VerificationError::MissingSpillCode {
vreg,
point: iv.start_point().unwrap_or(InstrPoint::new(0, 0, 0)),
});
}
}
}
}
fn verify_class_constraints(
&mut self,
intervals: &HashMap<u32, X86LiveInterval>,
assignments: &HashMap<u32, u32>,
) {
for (&vreg, iv) in intervals {
if let Some(&phys_reg) = assignments.get(&vreg) {
let assigned_class = X86RegClass::from_reg_class_kind(RegClassKind::GPR);
if assigned_class != iv.reg_class {
let is_gpr_alias = matches!(
iv.reg_class,
X86RegClass::GPR64
| X86RegClass::GPR32
| X86RegClass::GPR16
| X86RegClass::GPR8
) && matches!(
assigned_class,
X86RegClass::GPR64
| X86RegClass::GPR32
| X86RegClass::GPR16
| X86RegClass::GPR8
);
let is_vector_alias = matches!(
iv.reg_class,
X86RegClass::VECTOR128 | X86RegClass::VECTOR256 | X86RegClass::VECTOR512
) && matches!(
assigned_class,
X86RegClass::VECTOR128 | X86RegClass::VECTOR256 | X86RegClass::VECTOR512
);
if !is_gpr_alias && !is_vector_alias {
self.warnings.push(format!(
"vreg {} class {:?} but assigned to reg {} (class {:?})",
vreg, iv.reg_class, phys_reg, assigned_class,
));
}
}
}
}
}
fn verify_callee_saved(&mut self, used_regs: &HashSet<u32>, callee_saved: &[u32]) {
for &cs in callee_saved {
if used_regs.contains(&cs) {
self.warnings.push(format!(
"Callee-saved register {} is used; ensure save/restore",
cs
));
}
}
}
fn verify_reserved_registers(&mut self, assignments: &HashMap<u32, u32>) {
for (&vreg, &phys_reg) in assignments {
if phys_reg == x86_reg::RSP {
self.errors.push(VerificationError::StackPointerUsed);
}
if phys_reg == x86_reg::RBP {
self.warnings.push(format!("vreg {} assigned to RBP", vreg));
}
}
}
pub fn report_errors(&self) -> String {
let mut r = String::new();
if self.errors.is_empty() && self.warnings.is_empty() {
r.push_str("Verification: PASSED\n");
} else {
if !self.errors.is_empty() {
r.push_str(&format!("Verification ERRORS ({}):\n", self.errors.len()));
for (i, e) in self.errors.iter().enumerate() {
r.push_str(&format!(" {}. {:?}\n", i + 1, e));
}
}
if !self.warnings.is_empty() {
r.push_str(&format!(
"Verification WARNINGS ({}):\n",
self.warnings.len()
));
for (i, w) in self.warnings.iter().enumerate() {
r.push_str(&format!(" {}. {}\n", i + 1, w));
}
}
}
r
}
pub fn summary(&self) -> String {
if self.verified {
"Verification: PASSED".to_string()
} else {
format!(
"Verification: {} errors, {} warnings",
self.errors.len(),
self.warnings.len()
)
}
}
}
impl Default for X86AllocationVerifier {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegisterColoring {
pub graph: X86InterferenceGraph,
pub allowed_colors: HashMap<u32, Vec<u32>>,
pub color_bias: HashMap<u32, u32>,
pub coloring: HashMap<u32, u32>,
pub spills: HashSet<u32>,
pub color_stats: ColoringStats,
}
#[derive(Debug, Clone, Default)]
pub struct ColoringStats {
pub nodes_colored: usize,
pub nodes_spilled: usize,
pub colors_used: usize,
pub bias_satisfied: usize,
pub bias_attempted: usize,
pub color_attempts: usize,
pub backtrack_count: usize,
}
impl X86RegisterColoring {
pub fn new() -> Self {
Self {
graph: X86InterferenceGraph::new(),
allowed_colors: HashMap::new(),
color_bias: HashMap::new(),
coloring: HashMap::new(),
spills: HashSet::new(),
color_stats: ColoringStats::default(),
}
}
pub fn with_graph(mut self, graph: X86InterferenceGraph) -> Self {
self.graph = graph;
self
}
pub fn set_allowed_colors(&mut self, vreg: u32, colors: Vec<u32>) {
self.allowed_colors.insert(vreg, colors);
}
pub fn set_bias(&mut self, vreg: u32, reg: u32) {
self.color_bias.insert(vreg, reg);
self.color_stats.bias_attempted += 1;
}
pub fn color(&mut self) {
self.coloring.clear();
self.spills.clear();
let k = self.estimate_k();
self.graph.compute_coloring_order(k);
for &vreg in &self.graph.coloring_order {
let neighbors = self.graph.edges.get(&vreg).cloned().unwrap_or_default();
let mut used_colors: HashSet<u32> = HashSet::new();
for &neighbor in &neighbors {
if let Some(&color) = self.coloring.get(&neighbor) {
used_colors.insert(color);
}
}
let allowed = self.allowed_colors.get(&vreg).cloned().unwrap_or_else(|| {
(0u32..16).collect()
});
let bias = self.color_bias.get(&vreg).copied();
if let Some(b) = bias {
if allowed.contains(&b) && !used_colors.contains(&b) {
self.coloring.insert(vreg, b);
self.color_stats.bias_satisfied += 1;
self.color_stats.nodes_colored += 1;
continue;
}
}
let mut assigned = false;
for &color in &allowed {
self.color_stats.color_attempts += 1;
if !used_colors.contains(&color) {
self.coloring.insert(vreg, color);
self.color_stats.nodes_colored += 1;
assigned = true;
break;
}
}
if !assigned {
if self.try_recolor(vreg, &neighbors, &allowed) {
self.color_stats.backtrack_count += 1;
self.color_stats.nodes_colored += 1;
} else {
self.spills.insert(vreg);
self.color_stats.nodes_spilled += 1;
}
}
}
let unique_colors: HashSet<u32> = self.coloring.values().copied().collect();
self.color_stats.colors_used = unique_colors.len();
}
fn estimate_k(&self) -> usize {
if let Some(colors) = self.allowed_colors.values().next() {
colors.len()
} else {
14 }
}
fn try_recolor(&mut self, vreg: u32, neighbors: &HashSet<u32>, allowed: &[u32]) -> bool {
for &color in allowed {
let blocking: Option<u32> = neighbors
.iter()
.find(|&&n| self.coloring.get(&n) == Some(&color))
.copied();
if let Some(blocker) = blocking {
let blocker_neighbors = self.graph.edges.get(&blocker).cloned().unwrap_or_default();
let mut blocker_used: HashSet<u32> = blocker_neighbors
.iter()
.filter_map(|&n| self.coloring.get(&n).copied())
.collect();
let blocker_allowed = self
.allowed_colors
.get(&blocker)
.cloned()
.unwrap_or_else(|| (0u32..16).collect());
for &new_color in &blocker_allowed {
if new_color != color && !blocker_used.contains(&new_color) {
self.coloring.insert(blocker, new_color);
self.coloring.insert(vreg, color);
return true;
}
}
}
}
false
}
pub fn get_color(&self, vreg: u32) -> Option<u32> {
self.coloring.get(&vreg).copied()
}
pub fn summary(&self) -> String {
format!(
"Coloring: {} colored, {} spilled, {} colors, {} bias ({} attempts)",
self.color_stats.nodes_colored,
self.color_stats.nodes_spilled,
self.color_stats.colors_used,
self.color_stats.bias_satisfied,
self.color_stats.bias_attempted,
)
}
}
impl Default for X86RegisterColoring {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86RegisterBundling {
pub bundles: HashMap<u32, u32>,
pub bundle_contents: HashMap<u32, HashSet<u32>>,
pub bundle_intervals: HashMap<u32, X86LiveInterval>,
next_bundle_id: u32,
pub bundle_stats: BundlingStats,
}
#[derive(Debug, Clone, Default)]
pub struct BundlingStats {
pub bundles_created: usize,
pub vregs_bundled: usize,
pub avg_bundle_size: f64,
pub largest_bundle: usize,
pub allocation_conflicts_resolved: usize,
}
impl X86RegisterBundling {
pub fn new() -> Self {
Self {
bundles: HashMap::new(),
bundle_contents: HashMap::new(),
bundle_intervals: HashMap::new(),
next_bundle_id: 1,
bundle_stats: BundlingStats::default(),
}
}
pub fn create_bundle(&mut self, vregs: &[u32]) -> u32 {
let bundle_id = self.next_bundle_id;
self.next_bundle_id += 1;
let mut members = HashSet::new();
for &vreg in vregs {
self.bundles.insert(vreg, bundle_id);
members.insert(vreg);
}
self.bundle_contents.insert(bundle_id, members);
self.bundle_stats.bundles_created += 1;
self.bundle_stats.vregs_bundled += vregs.len();
let sz = vregs.len();
self.bundle_stats.largest_bundle = self.bundle_stats.largest_bundle.max(sz);
bundle_id
}
pub fn add_to_bundle(&mut self, vreg: u32, bundle_id: u32) {
self.bundles.insert(vreg, bundle_id);
self.bundle_contents
.entry(bundle_id)
.or_default()
.insert(vreg);
self.bundle_stats.vregs_bundled += 1;
}
pub fn compute_bundle_interval(
&mut self,
bundle_id: u32,
intervals: &HashMap<u32, X86LiveInterval>,
) {
let members = match self.bundle_contents.get(&bundle_id) {
Some(m) => m.clone(),
None => return,
};
if members.is_empty() {
return;
}
let mut first = true;
let mut bundle_iv = X86LiveInterval::new(bundle_id, X86RegClass::GPR64);
for &vreg in &members {
if let Some(iv) = intervals.get(&vreg) {
if first {
bundle_iv = iv.clone();
bundle_iv.vreg = bundle_id;
first = false;
} else {
bundle_iv = bundle_iv.union_with(iv);
}
}
}
if !first {
self.bundle_intervals.insert(bundle_id, bundle_iv);
}
}
pub fn same_bundle(&self, a: u32, b: u32) -> bool {
match (self.bundles.get(&a), self.bundles.get(&b)) {
(Some(ba), Some(bb)) => ba == bb,
_ => false,
}
}
pub fn bundled_with(&self, vreg: u32) -> HashSet<u32> {
if let Some(&bundle_id) = self.bundles.get(&vreg) {
self.bundle_contents
.get(&bundle_id)
.cloned()
.unwrap_or_default()
} else {
let mut s = HashSet::new();
s.insert(vreg);
s
}
}
pub fn update_stats(&mut self) {
if self.bundle_stats.bundles_created > 0 {
self.bundle_stats.avg_bundle_size =
self.bundle_stats.vregs_bundled as f64 / self.bundle_stats.bundles_created as f64;
}
}
pub fn summary(&self) -> String {
format!(
"Bundling: {} bundles, {} vregs, avg size {:.1}, largest {}",
self.bundle_stats.bundles_created,
self.bundle_stats.vregs_bundled,
self.bundle_stats.avg_bundle_size,
self.bundle_stats.largest_bundle,
)
}
}
impl Default for X86RegisterBundling {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone)]
pub struct X86SpillCostModel {
pub loop_depths: HashMap<u32, u32>,
pub block_frequency: HashMap<u32, f64>,
pub pressure: HashMap<X86RegClass, f64>,
pub pressure_sensitivity: f64,
pub store_cost: f64,
pub load_cost: f64,
pub remat_discount: f64,
pub base_multiplier: f64,
}
impl X86SpillCostModel {
pub fn new() -> Self {
Self {
loop_depths: HashMap::new(),
block_frequency: HashMap::new(),
pressure: HashMap::new(),
pressure_sensitivity: 1.5,
store_cost: 4.0,
load_cost: 4.0,
remat_discount: 0.1,
base_multiplier: 1.0,
}
}
pub fn set_loop_depth(&mut self, block: u32, depth: u32) {
self.loop_depths.insert(block, depth);
}
pub fn set_block_frequency(&mut self, block: u32, freq: f64) {
self.block_frequency.insert(block, freq);
}
pub fn compute_spill_weight(&self, interval: &X86LiveInterval) -> f64 {
let mut weight = 0.0;
for &use_pt in &interval.use_points {
let loop_depth = self.loop_depths.get(&use_pt.block).copied().unwrap_or(0);
let freq = self
.block_frequency
.get(&use_pt.block)
.copied()
.unwrap_or(1.0);
let loop_factor = 10.0f64.powi(loop_depth as i32);
weight += freq * loop_factor;
}
for &def_pt in &interval.def_points {
let loop_depth = self.loop_depths.get(&def_pt.block).copied().unwrap_or(0);
let freq = self
.block_frequency
.get(&def_pt.block)
.copied()
.unwrap_or(1.0);
let loop_factor = 10.0f64.powi(loop_depth as i32);
weight += freq * loop_factor * 0.5;
}
let pressure_factor = self
.pressure
.get(&interval.reg_class)
.copied()
.unwrap_or(1.0);
weight *= pressure_factor.powf(self.pressure_sensitivity);
if interval.rematerializable {
weight *= self.remat_discount;
}
weight * self.base_multiplier
}
pub fn spill_at_point(&self, interval: &X86LiveInterval, point: InstrPoint) -> f64 {
let loop_depth = self.loop_depths.get(&point.block).copied().unwrap_or(0);
let freq = self
.block_frequency
.get(&point.block)
.copied()
.unwrap_or(1.0);
let loop_factor = 10.0f64.powi(loop_depth as i32);
let remaining_uses = interval.use_points.iter().filter(|&&u| u >= point).count() as f64;
let remaining_defs = interval.def_points.iter().filter(|&&d| d >= point).count() as f64;
if interval.rematerializable {
remaining_uses * self.load_cost * self.remat_discount * freq * loop_factor
} else {
let store_cost = self.store_cost * freq * loop_factor;
let reload_cost = remaining_uses * self.load_cost * freq * loop_factor;
let def_spill_cost = remaining_defs * self.store_cost * freq * loop_factor;
store_cost + reload_cost + def_spill_cost
}
}
pub fn update_pressure(&mut self, class: X86RegClass, count: usize, total_available: usize) {
let pressure = if total_available > 0 {
count as f64 / total_available as f64
} else {
0.0
};
self.pressure.insert(class, pressure.max(1.0));
}
pub fn summary(&self) -> String {
format!(
"SpillCost: {} blocks with depth info, store={:.1}, load={:.1}, remat_disc={:.2}",
self.loop_depths.len(),
self.store_cost,
self.load_cost,
self.remat_discount,
)
}
}
impl Default for X86SpillCostModel {
fn default() -> Self {
Self::new()
}
}
pub struct X86AllocationPassManager {
pub live_intervals: X86LiveIntervals,
pub allocator: X86RegisterAllocator,
pub coalescing: X86RegisterCoalescing,
pub interference_graph: X86InterferenceGraph,
pub coloring: X86RegisterColoring,
pub cost_model: X86SpillCostModel,
pub verifier: X86AllocationVerifier,
pub stats: X86RegAllocStats,
pub config: AllocationPipelineConfig,
}
impl fmt::Debug for X86AllocationPassManager {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("X86AllocationPassManager")
.field("config", &self.config)
.finish()
}
}
#[derive(Debug, Clone)]
pub struct AllocationPipelineConfig {
pub enable_coalescing: bool,
pub enable_interference_graph: bool,
pub enable_verification: bool,
pub enable_coloring: bool,
pub enable_spill_optimization: bool,
pub debug_trace: bool,
pub max_spill_weight: f64,
pub min_split_length: u32,
}
impl Default for AllocationPipelineConfig {
fn default() -> Self {
Self {
enable_coalescing: true,
enable_interference_graph: false,
enable_verification: true,
enable_coloring: false,
enable_spill_optimization: true,
debug_trace: false,
max_spill_weight: f64::MAX,
min_split_length: 10,
}
}
}
impl X86AllocationPassManager {
pub fn new(name: &str, opt_level: X86AllocOptLevel) -> Self {
Self {
live_intervals: X86LiveIntervals::new(),
allocator: X86RegisterAllocator::new(name).with_opt_level(opt_level),
coalescing: X86RegisterCoalescing::new(),
interference_graph: X86InterferenceGraph::new(),
coloring: X86RegisterColoring::new(),
cost_model: X86SpillCostModel::new(),
verifier: X86AllocationVerifier::new(),
stats: X86RegAllocStats::new().with_strategy(&format!("{:?}", opt_level)),
config: AllocationPipelineConfig::default(),
}
}
pub fn run(
&mut self,
defs: &HashMap<u32, Vec<InstrPoint>>,
uses: &HashMap<u32, Vec<InstrPoint>>,
block_order: &[u32],
) -> X86AllocResult {
self.live_intervals
.compute_intervals(defs, uses, block_order);
if self.config.enable_coalescing {
for (&vreg, iv) in &self.live_intervals.intervals {
self.coalescing.add_interval(iv.clone());
}
self.coalescing.coalesce();
for &(dst, src) in &self.coalescing.coalesced {
if let Some(mut merged) = self.live_intervals.intervals.remove(&dst) {
if let Some(src_iv) = self.live_intervals.intervals.remove(&src) {
merged = merged.union_with(&src_iv);
}
self.live_intervals.intervals.insert(dst, merged);
}
}
}
if self.config.enable_interference_graph {
self.interference_graph
.build(&self.live_intervals.intervals);
self.interference_graph.compute_components();
}
for (&vreg, iv) in &self.live_intervals.intervals {
self.allocator
.live_intervals
.intervals
.insert(vreg, iv.clone());
}
let result = self.allocator.allocate();
self.stats.strategy = result.allocator.clone();
if self.config.enable_verification {
self.verifier.verify(
&self.live_intervals.intervals,
&result.assignments,
&result.spilled,
&HashSet::new(),
&[],
);
}
result
}
pub fn run_debug(
&mut self,
defs: &HashMap<u32, Vec<InstrPoint>>,
uses: &HashMap<u32, Vec<InstrPoint>>,
block_order: &[u32],
) -> (X86AllocResult, String) {
let result = self.run(defs, uses, block_order);
let mut trace = String::new();
trace.push_str("=== Allocation Pipeline Trace ===\n");
trace.push_str(&format!("Function: {}\n", self.allocator.function_name));
trace.push_str(&format!("Opt level: {}\n", self.allocator.opt_level));
trace.push_str(&format!(
"Intervals: {} computed\n",
self.live_intervals.interval_count
));
trace.push_str(&self.coalescing.summary());
trace.push('\n');
trace.push_str(&self.interference_graph.summary());
trace.push('\n');
trace.push_str(&self.stats.summary());
trace.push('\n');
trace.push_str(&self.verifier.report_errors());
trace.push_str("\nAssignments:\n");
for (&vreg, &phys_reg) in &result.assignments {
trace.push_str(&format!(" v{} -> r{}\n", vreg, phys_reg));
}
if !result.spilled.is_empty() {
trace.push_str("Spilled:\n");
for &vreg in &result.spilled {
let slot = result.spill_slots.get(&vreg).copied().unwrap_or(-1);
trace.push_str(&format!(" v{} -> [sp+{}]\n", vreg, slot));
}
}
(result, trace)
}
pub fn report(&self) -> String {
let mut r = String::new();
r.push_str("=== X86 Allocation Pipeline Report ===\n");
r.push_str(&format!(
"Config: coalescing={}, igraph={}, verify={}, coloring={}\n",
self.config.enable_coalescing,
self.config.enable_interference_graph,
self.config.enable_verification,
self.config.enable_coloring,
));
r.push_str(&self.live_intervals.summary());
r.push('\n');
r.push_str(&self.coalescing.summary());
r.push('\n');
r.push_str(&self.interference_graph.summary());
r.push('\n');
r.push_str(&self.cost_model.summary());
r.push('\n');
r.push_str(&self.verifier.summary());
r
}
}
#[cfg(test)]
mod tests {
use super::*;
fn pt(block: u32, instr: u32) -> InstrPoint {
InstrPoint::new(block, instr, 0)
}
fn make_interval(
vreg: u32,
class: X86RegClass,
start: InstrPoint,
end: InstrPoint,
) -> X86LiveInterval {
let mut iv = X86LiveInterval::new(vreg, class);
iv.add_segment(start, end);
iv
}
#[test]
fn test_live_interval_creation() {
let iv = X86LiveInterval::new(10, X86RegClass::GPR64);
assert_eq!(iv.vreg, 10);
assert_eq!(iv.reg_class, X86RegClass::GPR64);
assert!(!iv.is_fixed);
assert!(!iv.spilled);
assert!(!iv.rematerializable);
}
#[test]
fn test_live_interval_segments() {
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
iv.add_segment(pt(0, 20), pt(0, 30));
assert_eq!(iv.segments.len(), 2);
assert!(iv.segments[0].contains(pt(0, 5)));
assert!(!iv.segments[0].contains(pt(0, 15)));
assert!(iv.segments[1].contains(pt(0, 25)));
}
#[test]
fn test_live_interval_sort_and_merge() {
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 20), pt(0, 30));
iv.add_segment(pt(0, 0), pt(0, 10));
iv.add_segment(pt(0, 10), pt(0, 20));
iv.sort_and_merge();
assert_eq!(iv.segments.len(), 1);
assert_eq!(iv.segments[0].start, pt(0, 0));
assert_eq!(iv.segments[0].end, pt(0, 30));
}
#[test]
fn test_live_interval_overlap() {
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 5), pt(0, 15));
assert!(a.overlaps_with(&b));
let mut c = X86LiveInterval::new(3, X86RegClass::GPR64);
c.add_segment(pt(0, 20), pt(0, 30));
assert!(!a.overlaps_with(&c));
}
#[test]
fn test_live_interval_split() {
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 100));
iv.add_use(pt(0, 10));
iv.add_use(pt(0, 50));
iv.add_use(pt(0, 90));
iv.add_def(pt(0, 0));
let (before, after) = iv.split_at(pt(0, 50)).expect("Should split successfully");
assert!(before.segments.iter().all(|s| s.end <= pt(0, 50)));
assert!(after.segments.iter().all(|s| s.start >= pt(0, 50)));
assert!(after.parent == Some(1));
}
#[test]
fn test_subregister_tracking() {
let mut liv = X86LiveIntervals::new();
liv.track_subregister(10, 0, Some(pt(0, 0)), Some(pt(0, 5)));
liv.track_subregister(10, 1, None, Some(pt(0, 3)));
assert!(liv.subreg_defs.contains_key(&10));
assert!(liv.subreg_uses.contains_key(&10));
assert_eq!(liv.subreg_count, 2);
}
#[test]
fn test_block_liveness() {
let mut liv = X86LiveIntervals::new();
let mut defs: HashMap<u32, Vec<InstrPoint>> = HashMap::new();
let mut uses: HashMap<u32, Vec<InstrPoint>> = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(1, 5)]);
liv.compute_intervals(&defs, &uses, &[0, 1]);
assert!(liv.computed);
assert!(liv.interval_count >= 1);
}
#[test]
fn test_region_splitting() {
let mut splitter = X86RegAllocSplitting::new();
let mut region = ProgramRegion::new(1, 0);
region.add_block(0);
region.add_block(1);
region.set_entry(0);
splitter.add_region(region);
let mut region2 = ProgramRegion::new(2, 0);
region2.add_block(2);
region2.add_block(3);
region2.set_entry(2);
splitter.add_region(region2);
let mut iv = X86LiveInterval::new(10, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(2, 10));
iv.add_use(pt(0, 5));
iv.add_use(pt(1, 5));
iv.add_use(pt(2, 5));
iv.add_def(pt(0, 0));
splitter.intervals.insert(10, iv);
let children = splitter.split_at_regions(10);
assert!(children.len() >= 1 || !children.is_empty() || children.len() == 0);
}
#[test]
fn test_local_splitting() {
let mut splitter = X86RegAllocSplitting::new();
let mut iv = X86LiveInterval::new(10, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 30));
iv.add_use(pt(0, 5));
iv.add_use(pt(0, 15));
iv.add_use(pt(0, 25));
iv.add_def(pt(0, 0));
splitter.intervals.insert(10, iv);
let children = splitter.split_local(10, 0);
if let Some(c) = children {
assert!(c.len() >= 1);
assert!(splitter.split_stats.local_splits >= 1);
}
}
#[test]
fn test_global_splitting() {
let mut splitter = X86RegAllocSplitting::new();
let mut iv = X86LiveInterval::new(10, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(3, 10));
iv.add_use(pt(0, 5));
iv.add_use(pt(1, 5)); iv.add_use(pt(2, 5)); iv.add_use(pt(3, 5));
iv.add_def(pt(0, 0));
splitter.intervals.insert(10, iv);
let children = splitter.split_global(10, 1, &[1, 2]);
assert!(children.len() >= 1);
assert!(splitter.split_stats.global_splits >= 1);
}
#[test]
fn test_spill_slot_reuse() {
let mut splitter = X86RegAllocSplitting::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
splitter.intervals.insert(1, a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 20), pt(0, 30)); splitter.intervals.insert(2, b);
let slots = splitter.assign_spill_slots(&[1, 2]);
assert_eq!(slots.len(), 2);
assert!(splitter.split_stats.spill_slots_reused >= 1);
}
#[test]
fn test_eviction_cost_computation() {
let mut chain = X86EvictionChain::new();
let iv = X86LiveInterval::new(1, X86RegClass::GPR64);
let cost = chain.compute_spill_cost(1, &iv, pt(0, 0), 0);
assert!(cost >= 0.0);
let eviction_cost = chain.compute_eviction_cost(1, &iv, pt(0, 0), 0);
assert!(eviction_cost >= 0.0);
}
#[test]
fn test_build_eviction_costs() {
let mut chain = X86EvictionChain::new();
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.spill_weight = 1.0;
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.spill_weight = 10.0;
intervals.insert(2, iv2);
chain.build_eviction_costs(&[1, 2], &intervals, pt(0, 0), 0);
let cheapest = chain.find_cheapest_to_evict();
assert!(cheapest.is_some());
assert_eq!(cheapest.unwrap().0, 1);
}
#[test]
fn test_eviction_chain_recording() {
let mut chain = X86EvictionChain::new();
chain.record_eviction(1, 2, x86_reg::RAX, pt(0, 5), 1.5);
chain.record_eviction(2, 3, x86_reg::RAX, pt(0, 6), 2.0);
assert_eq!(chain.current_depth(), 2);
assert_eq!(chain.chain_stats.total_evictions, 2);
assert!(chain.total_chain_cost() >= 3.5);
}
#[test]
fn test_cascade_eviction() {
let mut chain = X86EvictionChain::new().with_max_depth(5);
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.spill_weight = 0.5;
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.spill_weight = 0.3;
intervals.insert(2, iv2);
assert!(chain.can_cascade());
let result = chain.try_cascade_eviction(1, x86_reg::RAX, pt(0, 0), &[2], &intervals, 0);
assert!(chain.current_depth() <= 2);
}
#[test]
fn test_eviction_chain_max_depth() {
let mut chain = X86EvictionChain::new().with_max_depth(3);
chain.record_eviction(1, 2, 10, pt(0, 0), 1.0);
chain.record_eviction(3, 1, 11, pt(0, 0), 1.0);
chain.record_eviction(4, 3, 12, pt(0, 0), 1.0);
assert!(!chain.can_cascade()); assert!(chain.current_depth() == 3);
}
#[test]
fn test_spill_code_insertion() {
let mut opt = X86SpillOptimizer::new();
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_def(pt(0, 0));
iv.add_use(pt(0, 5));
iv.add_use(pt(0, 10));
iv.add_def(pt(0, 20));
let loop_depths = HashMap::new();
opt.insert_spill_code(1, &iv, 8, &loop_depths);
assert!(opt.opt_stats.spills_inserted >= 2); assert!(opt.opt_stats.reloads_inserted >= 2); }
#[test]
fn test_spill_slot_coalescing() {
let mut opt = X86SpillOptimizer::new();
let mut intervals = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 20), pt(0, 30)); intervals.insert(2, b);
let slots = opt.coalesce_spill_slots(&intervals, &[1, 2]);
assert_eq!(slots.len(), 2);
assert!(opt.opt_stats.slots_coalesced >= 1);
}
#[test]
fn test_rematerialization_detection() {
let mut opt = X86SpillOptimizer::new();
opt.detect_remat(1, X86Opcode::XOR, false, None);
assert!(opt.is_rematerializable(1));
opt.detect_remat(2, X86Opcode::MOV, true, Some(42));
assert!(opt.is_rematerializable(2));
}
#[test]
fn test_rematerialization_avoids_spill() {
let mut opt = X86SpillOptimizer::new();
opt.mark_rematerializable(1, X86RematSource::Constant(42));
let iv = X86LiveInterval::new(1, X86RegClass::GPR64);
let result = opt.try_rematerialize(1, pt(0, 0), &iv);
assert!(result);
assert!(opt.opt_stats.remat_inserted >= 1);
}
#[test]
fn test_load_store_forwarding() {
let mut opt = X86SpillOptimizer::new();
let mut intervals = HashMap::new();
let iv = X86LiveInterval::new(1, X86RegClass::GPR64);
intervals.insert(1, iv);
opt.spill_code.push(SpillCode::Store {
point: pt(0, 5),
vreg: 1,
slot: 0,
});
opt.spill_code.push(SpillCode::Load {
point: pt(0, 6),
vreg: 1,
slot: 0,
});
opt.detect_forwarding_opportunities(&intervals);
assert!(opt.opt_stats.forwarding_eliminated >= 1);
opt.eliminate_forwarded_pairs();
let has_store_load_pair = opt.spill_code.iter().any(|c| {
matches!(
c,
SpillCode::Load {
vreg: 1,
slot: 0,
..
}
)
});
assert!(!has_store_load_pair);
}
#[test]
fn test_spill_hoisting() {
let mut opt = X86SpillOptimizer::new();
let mut intervals = HashMap::new();
intervals.insert(1, X86LiveInterval::new(1, X86RegClass::GPR64));
opt.spill_code.push(SpillCode::Store {
point: pt(1, 5),
vreg: 1,
slot: 0,
});
opt.spill_code.push(SpillCode::Load {
point: pt(2, 3),
vreg: 1,
slot: 0,
});
opt.hoist_loop_spills(&[1, 2], 1, &intervals);
assert!(opt.opt_stats.spills_hoisted >= 1);
let all_hoisted = opt.spill_code.iter().all(|c| {
let pt = match c {
SpillCode::Store { point, .. }
| SpillCode::Load { point, .. }
| SpillCode::Remat { point, .. } => *point,
};
pt.block == 1
});
assert!(all_hoisted);
}
#[test]
fn test_allocation_order_hints() {
let mut order = X86AllocationOrder::new();
order.add_hint(10, x86_reg::R12);
let iv = X86LiveInterval::new(10, X86RegClass::GPR64);
let alloc_order = order.get_allocation_order(10, X86RegClass::GPR64, Some(&iv));
assert_eq!(alloc_order.first(), Some(&x86_reg::R12));
}
#[test]
fn test_allocation_order_callee_saved_preference() {
let order = X86AllocationOrder::new();
let mut iv = X86LiveInterval::new(10, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 1000));
let alloc_order = order.get_allocation_order(10, X86RegClass::GPR64, Some(&iv));
let callee_pos = alloc_order.iter().position(|&r| order.is_callee_saved(r));
let caller_pos = alloc_order.iter().position(|&r| order.is_caller_saved(r));
if let (Some(cp), Some(clp)) = (callee_pos, caller_pos) {
assert!(
cp < clp,
"Callee-saved should come before caller-saved for long-lived intervals"
);
}
}
#[test]
fn test_allocation_order_short_lived() {
let mut order = X86AllocationOrder::new().with_short_lived_threshold(5);
let mut iv = X86LiveInterval::new(10, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 1));
let alloc_order = order.get_allocation_order(10, X86RegClass::GPR64, Some(&iv));
let callee_pos = alloc_order.iter().position(|&r| order.is_callee_saved(r));
let caller_pos = alloc_order.iter().position(|&r| order.is_caller_saved(r));
if let (Some(cp), Some(clp)) = (callee_pos, caller_pos) {
assert!(
clp < cp,
"Caller-saved should come before callee-saved for short-lived intervals"
);
}
}
#[test]
fn test_allocation_order_reserved() {
let mut order = X86AllocationOrder::new();
assert!(order.is_reserved(x86_reg::RSP));
assert!(order.is_reserved(x86_reg::RBP));
let iv = X86LiveInterval::new(10, X86RegClass::GPR64);
let alloc_order = order.get_allocation_order(10, X86RegClass::GPR64, Some(&iv));
assert!(!alloc_order.contains(&x86_reg::RSP));
assert!(!alloc_order.contains(&x86_reg::RBP));
}
#[test]
fn test_class_assignment_basic() {
let mut ca = X86RegClassAssignment::new();
let cls = ca.assign_class(1, X86RegClass::GPR64);
assert_eq!(cls, X86RegClass::GPR64);
assert_eq!(ca.class_stats.gpr64_assignments, 1);
}
#[test]
fn test_class_assignment_constraint() {
let mut ca = X86RegClassAssignment::new();
ca.add_constraint(pt(0, 0), 1, X86RegClass::VECTOR128, 0, true);
let cls = ca.assign_class(1, X86RegClass::GPR64);
assert_eq!(cls, X86RegClass::VECTOR128);
assert_eq!(ca.class_stats.xmm_assignments, 1);
}
#[test]
fn test_class_pressure() {
let mut ca = X86RegClassAssignment::new();
for i in 0..15 {
ca.assign_class(i, X86RegClass::GPR64);
}
assert!(ca.pressure_too_high(X86RegClass::GPR64));
}
#[test]
fn test_copy_coalescing() {
let mut ca = X86RegClassAssignment::new();
ca.add_coalescing_pair(1, 2);
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 5));
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 6), pt(0, 10)); intervals.insert(2, iv2);
let coalesced = ca.try_coalesce(&intervals);
assert!(coalesced >= 0);
}
#[test]
fn test_copy_coalescing_overlapping() {
let mut ca = X86RegClassAssignment::new();
ca.add_coalescing_pair(1, 2);
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 5), pt(0, 15)); intervals.insert(2, iv2);
let coalesced = ca.try_coalesce(&intervals);
assert_eq!(coalesced, 0);
}
#[test]
fn test_linear_scan_basic() {
let mut alloc = X86LinearScanAllocator::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 5));
iv1.add_use(pt(0, 2));
iv1.add_def(pt(0, 0));
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 6), pt(0, 10));
iv2.add_use(pt(0, 7));
iv2.add_def(pt(0, 6));
alloc.add_interval(iv1);
alloc.add_interval(iv2);
alloc.allocate();
assert!(alloc.stats.registers_assigned >= 1);
}
#[test]
fn test_linear_scan_overlapping() {
let mut alloc = X86LinearScanAllocator::new();
alloc.alloc_order.reserve(x86_reg::R12);
alloc.alloc_order.reserve(x86_reg::R13);
alloc.alloc_order.reserve(x86_reg::R14);
alloc.alloc_order.reserve(x86_reg::R15);
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 10));
iv1.add_use(pt(0, 2));
iv1.add_def(pt(0, 0));
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 5), pt(0, 15));
iv2.add_use(pt(0, 7));
iv2.add_def(pt(0, 5));
alloc.add_interval(iv1);
alloc.add_interval(iv2);
alloc.allocate();
let total_spilled = alloc.stats.registers_spilled;
assert!(
total_spilled >= 1,
"Expected spills with overlapping intervals"
);
}
#[test]
fn test_linear_scan_with_hint() {
let mut alloc = X86LinearScanAllocator::new();
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 5));
iv.set_hint(x86_reg::R12);
alloc.add_interval(iv);
alloc.allocate();
assert!(alloc.stats.registers_assigned >= 1);
}
#[test]
fn test_linear_scan_fixed_reg() {
let mut alloc = X86LinearScanAllocator::new();
alloc.add_fixed_reg(1, x86_reg::RAX, X86RegClass::GPR64);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 0), pt(0, 5));
iv2.add_use(pt(0, 2));
iv2.add_def(pt(0, 0));
alloc.add_interval(iv2);
alloc.allocate();
if let Some(reg) = alloc.get_assignment(2) {
assert_ne!(reg, x86_reg::RAX);
}
}
#[test]
fn test_greedy_basic() {
let mut alloc = X86GreedyAllocator::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 5));
iv1.add_use(pt(0, 2));
iv1.add_def(pt(0, 0));
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 6), pt(0, 10));
iv2.add_use(pt(0, 7));
iv2.add_def(pt(0, 6));
alloc.add_interval(iv1);
alloc.add_interval(iv2);
alloc.allocate();
assert!(alloc.stats.assigned_vregs >= 0);
let summary = alloc.summary();
assert!(summary.contains("RA Stats"));
}
#[test]
fn test_greedy_different_classes() {
let mut alloc = X86GreedyAllocator::new();
let mut iv_gpr = X86LiveInterval::new(1, X86RegClass::GPR64);
iv_gpr.add_segment(pt(0, 0), pt(0, 5));
iv_gpr.add_use(pt(0, 2));
iv_gpr.add_def(pt(0, 0));
let mut iv_xmm = X86LiveInterval::new(200, X86RegClass::VECTOR128);
iv_xmm.add_segment(pt(0, 0), pt(0, 5));
iv_xmm.add_use(pt(0, 2));
iv_xmm.add_def(pt(0, 0));
alloc.add_interval(iv_gpr);
alloc.add_interval(iv_xmm);
alloc.allocate();
assert!(alloc.stats.assigned_vregs >= 2);
}
#[test]
fn test_greedy_with_strategies() {
for strategy in &[
AssignStrategy::FirstFit,
AssignStrategy::BestFit,
AssignStrategy::HintAware,
] {
let mut alloc = X86GreedyAllocator::new().with_strategy(*strategy);
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 5));
iv.add_use(pt(0, 2));
iv.add_def(pt(0, 0));
alloc.add_interval(iv);
alloc.allocate();
assert!(alloc.stats.assigned_vregs >= 0);
}
}
#[test]
fn test_greedy_eviction() {
let mut alloc = X86GreedyAllocator::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 100));
iv1.add_use(pt(0, 50));
iv1.add_def(pt(0, 0));
iv1.spill_weight = 1.0;
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 50), pt(0, 150));
iv2.add_use(pt(0, 100));
iv2.add_def(pt(0, 50));
iv2.spill_weight = 10.0;
alloc.add_interval(iv1);
alloc.add_interval(iv2);
alloc.allocate();
assert!(alloc.stats.evictions_performed + alloc.stats.spilled_vregs >= 0);
}
#[test]
fn test_greedy_rematerialization() {
let mut alloc = X86GreedyAllocator::new();
alloc
.spill_optimizer
.mark_rematerializable(1, X86RematSource::Constant(0));
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 5));
iv.add_use(pt(0, 2));
iv.add_def(pt(0, 0));
iv.rematerializable = true;
alloc.add_interval(iv);
alloc.allocate();
assert!(alloc.stats.rematerialized_count >= 0);
}
#[test]
fn test_pbqp_build_graph() {
let mut alloc = X86PbqpAllocator::new();
let iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
let iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
alloc.add_interval(iv1);
alloc.add_interval(iv2);
alloc.build_graph(&[(1, 2)], &[(1, 2)]);
assert!(alloc.graph_built);
}
#[test]
fn test_pbqp_solve_basic() {
let mut alloc = X86PbqpAllocator::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 5));
alloc.add_interval(iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 6), pt(0, 10));
alloc.add_interval(iv2);
alloc.build_graph(&[], &[]);
alloc.solve();
assert!(alloc.solved);
assert!(alloc.stats.assigned_vregs >= 1);
assert!(alloc.stats.r0_reductions >= 0);
}
#[test]
fn test_pbqp_with_interference() {
let mut alloc = X86PbqpAllocator::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 10));
alloc.add_interval(iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_segment(pt(0, 5), pt(0, 15));
alloc.add_interval(iv2);
alloc.build_graph(&[(1, 2)], &[]);
alloc.solve();
assert!(alloc.solved);
assert!(alloc.stats.total_vregs >= 1);
}
#[test]
fn test_pbqp_r0_reduction() {
let mut alloc = X86PbqpAllocator::new();
let iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
alloc.add_interval(iv1);
alloc.build_graph(&[], &[]);
alloc.solve();
assert!(alloc.stats.r0_reductions >= 1 || alloc.stats.r1_reductions >= 1);
}
#[test]
fn test_pbqp_reduction_ordering() {
let mut alloc = X86PbqpAllocator::new();
for i in 0..5 {
let iv = X86LiveInterval::new(i, X86RegClass::GPR64);
alloc.add_interval(iv);
}
let interferences = vec![(0, 1), (1, 2), (2, 3), (3, 4)];
alloc.build_graph(&interferences, &[]);
alloc.solve();
assert!(alloc.solved);
assert!(alloc.stats.r1_reductions >= 1 || alloc.stats.r2_reductions >= 1);
}
#[test]
fn test_basic_allocator_block() {
let mut alloc = X86BasicAllocator::new();
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_def(pt(0, 0));
iv1.add_use(pt(0, 2));
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.add_def(pt(0, 3));
iv2.add_use(pt(0, 5));
intervals.insert(2, iv2);
let live_in = HashSet::new();
let result = alloc.allocate_block(0, &[1, 2], &intervals, &live_in);
assert_eq!(result.block, 0);
assert_eq!(result.assignments.len(), 2);
assert_eq!(alloc.stats.blocks_processed, 1);
assert_eq!(alloc.stats.assigned_vregs, 2);
}
#[test]
fn test_basic_allocator_spill() {
let mut alloc = X86BasicAllocator::new();
let mut intervals = HashMap::new();
alloc
.available
.insert(X86RegClass::GPR64, vec![x86_reg::RAX]);
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_def(pt(0, i));
iv.add_use(pt(0, i + 1));
intervals.insert(i, iv);
}
let live_in = HashSet::new();
let result = alloc.allocate_block(0, &[0, 1, 2], &intervals, &live_in);
assert!(alloc.stats.spilled_vregs >= 2);
assert!(result.loads.len() + result.stores.len() >= 1);
}
#[test]
fn test_full_allocator_basic() {
let mut alloc = X86RegisterAllocator::new("test_func").with_opt_level(X86AllocOptLevel::O0);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 5)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
let result = alloc.allocate();
assert_eq!(result.allocator, "basic");
assert!(result.assignments.len() >= 0);
}
#[test]
fn test_full_allocator_linear_scan() {
let mut alloc = X86RegisterAllocator::new("test_ls").with_opt_level(X86AllocOptLevel::O1);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
let result = alloc.allocate();
assert_eq!(result.allocator, "linear_scan");
}
#[test]
fn test_full_allocator_greedy() {
let mut alloc =
X86RegisterAllocator::new("test_greedy").with_opt_level(X86AllocOptLevel::O2);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0), pt(1, 0)]);
uses.insert(1, vec![pt(0, 10), pt(1, 10)]);
defs.insert(2, vec![pt(0, 5)]);
uses.insert(2, vec![pt(0, 15)]);
alloc.compute_live_intervals(&defs, &uses, &[0, 1]);
let result = alloc.allocate();
assert_eq!(result.allocator, "greedy");
assert!(result.summary.contains("Greedy"));
}
#[test]
fn test_full_allocator_pbqp() {
let mut alloc = X86RegisterAllocator::new("test_pbqp").with_opt_level(X86AllocOptLevel::O3);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
defs.insert(2, vec![pt(0, 5)]);
uses.insert(2, vec![pt(0, 15)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
let result = alloc.allocate();
assert_eq!(result.allocator, "pbqp");
}
#[test]
fn test_full_allocator_report() {
let mut alloc =
X86RegisterAllocator::new("report_test").with_opt_level(X86AllocOptLevel::O2);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
alloc.allocate();
let report = alloc.report();
assert!(report.contains("X86 Register Allocation Report"));
assert!(report.contains("report_test"));
assert!(report.contains("Splitting"));
assert!(report.contains("Spill Optimization"));
assert!(report.contains("Eviction Chain"));
assert!(report.contains("Class Assignment"));
assert!(report.contains("Allocation Order"));
}
#[test]
fn test_full_allocator_all_levels() {
for level in &[
X86AllocOptLevel::O0,
X86AllocOptLevel::O1,
X86AllocOptLevel::O2,
X86AllocOptLevel::O3,
] {
let mut alloc = X86RegisterAllocator::new(&format!("func_O{}", u8::from(*level)))
.with_opt_level(*level);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
for i in 0..3 {
alloc.set_loop_depths(&HashMap::from([(i, i as u32)]));
}
let result = alloc.allocate();
assert!(
result.summary.len() > 0,
"Level {:?} produced no summary",
level
);
}
}
#[test]
fn test_full_allocator_with_regions() {
let mut alloc =
X86RegisterAllocator::new("region_test").with_opt_level(X86AllocOptLevel::O2);
let mut region = ProgramRegion::new(1, 0);
region.add_block(0);
region.add_block(1);
region.set_entry(0);
alloc.add_region(region);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0), pt(1, 0)]);
uses.insert(1, vec![pt(0, 10), pt(1, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0, 1]);
alloc.allocate();
assert!(alloc.splitter.regions.len() >= 1);
}
#[test]
fn test_full_allocator_with_copy_coalescing() {
let mut alloc = X86RegisterAllocator::new("copy_test").with_opt_level(X86AllocOptLevel::O2);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
defs.insert(2, vec![pt(1, 0)]);
uses.insert(1, vec![pt(0, 5)]);
uses.insert(2, vec![pt(1, 5)]);
alloc.compute_live_intervals(&defs, &uses, &[0, 1]);
alloc.add_copy(2, 1);
alloc.allocate();
assert!(alloc.class_assignment.coalescing_pairs.len() <= 1);
}
#[test]
fn test_full_allocator_with_remat() {
let mut alloc =
X86RegisterAllocator::new("remat_test").with_opt_level(X86AllocOptLevel::O2);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
alloc.add_remat(1, X86RematSource::Constant(42));
alloc.allocate();
}
#[test]
fn test_full_allocator_fixed_regs() {
let mut alloc =
X86RegisterAllocator::new("fixed_test").with_opt_level(X86AllocOptLevel::O2);
alloc.add_fixed_reg(1, x86_reg::RAX, X86RegClass::GPR64);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(2, vec![pt(0, 0)]);
uses.insert(2, vec![pt(0, 10)]);
alloc.compute_live_intervals(&defs, &uses, &[0]);
let result = alloc.allocate();
if let Some(®) = result.assignments.get(&2) {
assert_ne!(reg, x86_reg::RAX);
}
}
#[test]
fn test_spill_weight_computation() {
let mut alloc = X86RegisterAllocator::new("weight_test");
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_use(pt(0, 5));
iv.add_use(pt(0, 10));
iv.add_def(pt(0, 0));
iv.add_segment(pt(0, 0), pt(0, 10));
alloc.live_intervals.intervals.insert(1, iv);
let weight = alloc.compute_spill_weight_for(1);
assert!(weight > 0.0);
}
#[test]
fn test_spill_weight_loop_depth() {
let mut alloc = X86RegisterAllocator::new("weight_loop_test");
let mut iv_shallow = X86LiveInterval::new(1, X86RegClass::GPR64);
iv_shallow.add_use(pt(0, 5));
iv_shallow.add_def(pt(0, 0));
iv_shallow.add_segment(pt(0, 0), pt(0, 10));
alloc.live_intervals.intervals.insert(1, iv_shallow);
let mut iv_deep = X86LiveInterval::new(2, X86RegClass::GPR64);
iv_deep.add_use(pt(1, 5));
iv_deep.add_def(pt(1, 0));
iv_deep.add_segment(pt(1, 0), pt(1, 10));
alloc.live_intervals.intervals.insert(2, iv_deep);
alloc.set_loop_depths(&HashMap::from([(0, 0), (1, 3)]));
let w_shallow = alloc.compute_spill_weight_for(1);
let w_deep = alloc.compute_spill_weight_for(2);
assert!(
w_deep > w_shallow,
"Deep loop should have higher spill weight"
);
}
#[test]
fn test_reg_mask_operations() {
let mut mask = X86RegMask::new();
mask.set(x86_reg::RAX);
mask.set(x86_reg::RBX);
assert!(mask.contains(x86_reg::RAX));
assert!(mask.contains(x86_reg::RBX));
assert!(!mask.contains(x86_reg::RCX));
assert_eq!(mask.count(), 2);
mask.clear(x86_reg::RAX);
assert!(!mask.contains(x86_reg::RAX));
assert_eq!(mask.count(), 1);
}
#[test]
fn test_reg_mask_iter() {
let mut mask = X86RegMask::new();
mask.set(5);
mask.set(10);
let regs: Vec<u32> = mask.iter().collect();
assert_eq!(regs.len(), 2);
assert!(regs.contains(&5));
assert!(regs.contains(&10));
}
#[test]
fn test_reg_mask_union_intersect() {
let mut a = X86RegMask::new();
a.set(1);
a.set(2);
a.set(3);
let mut b = X86RegMask::new();
b.set(3);
b.set(4);
b.set(5);
let union = a.union_with(&b);
assert_eq!(union.count(), 5);
let inter = a.intersect(&b);
assert_eq!(inter.count(), 1);
assert!(inter.contains(3));
let diff = a.subtract(&b);
assert_eq!(diff.count(), 2);
assert!(diff.contains(1));
assert!(diff.contains(2));
}
#[test]
fn test_x86_reg_class_widths() {
assert_eq!(X86RegClass::GPR8.width(), 8);
assert_eq!(X86RegClass::GPR16.width(), 16);
assert_eq!(X86RegClass::GPR32.width(), 32);
assert_eq!(X86RegClass::GPR64.width(), 64);
assert_eq!(X86RegClass::VECTOR128.width(), 128);
assert_eq!(X86RegClass::VECTOR256.width(), 256);
assert_eq!(X86RegClass::VECTOR512.width(), 512);
}
#[test]
fn test_x86_reg_class_allocatable() {
let gpr_regs = X86RegClass::GPR64.allocatable_regs();
assert!(!gpr_regs.contains(&x86_reg::RSP));
assert!(!gpr_regs.contains(&x86_reg::RBP));
assert!(gpr_regs.contains(&x86_reg::RAX));
let xmm_regs = X86RegClass::VECTOR128.allocatable_regs();
assert!(xmm_regs.len() >= 16);
}
#[test]
fn test_live_segment_overlap() {
let a = X86LiveSegment::new(pt(0, 0), pt(0, 10));
let b = X86LiveSegment::new(pt(0, 5), pt(0, 15));
assert!(a.overlaps(&b));
let c = X86LiveSegment::new(pt(0, 20), pt(0, 30));
assert!(!a.overlaps(&c));
}
#[test]
fn test_interval_union() {
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
a.add_use(pt(0, 5));
let mut b = X86LiveInterval::new(1, X86RegClass::GPR64);
b.add_segment(pt(0, 15), pt(0, 25));
b.add_use(pt(0, 20));
let union = a.union_with(&b);
assert_eq!(union.segments.len(), 2);
assert_eq!(union.use_points.len(), 2);
}
#[test]
fn test_interval_intersection() {
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 20));
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 10), pt(0, 30));
let inter = a.intersect_with(&b);
assert_eq!(inter.len(), 1);
assert_eq!(inter[0].start, pt(0, 10));
assert_eq!(inter[0].end, pt(0, 20));
}
#[test]
fn test_eviction_chain_optimize() {
let mut chain = X86EvictionChain::new();
chain.record_eviction(1, 2, 10, pt(0, 0), 5.0);
chain.record_eviction(2, 3, 11, pt(0, 0), 1.0);
chain.record_eviction(3, 4, 12, pt(0, 0), 8.0);
chain.optimize_chain();
assert!(chain.chain_stats.cost_saved >= 0.0);
}
#[test]
fn test_spill_optimizer_no_forwarding_when_different_slots() {
let mut opt = X86SpillOptimizer::new();
let mut intervals = HashMap::new();
intervals.insert(1, X86LiveInterval::new(1, X86RegClass::GPR64));
opt.spill_code.push(SpillCode::Store {
point: pt(0, 5),
vreg: 1,
slot: 0,
});
opt.spill_code.push(SpillCode::Load {
point: pt(0, 6),
vreg: 1,
slot: 8,
});
opt.detect_forwarding_opportunities(&intervals);
assert_eq!(opt.opt_stats.forwarding_eliminated, 0);
}
#[test]
fn test_class_assignment_multiple_classes() {
let mut ca = X86RegClassAssignment::new();
ca.assign_class(1, X86RegClass::GPR64);
ca.assign_class(2, X86RegClass::GPR32);
ca.assign_class(3, X86RegClass::VECTOR128);
ca.assign_class(4, X86RegClass::VECTOR256);
ca.assign_class(5, X86RegClass::VECTOR512);
assert_eq!(ca.class_stats.gpr64_assignments, 1);
assert_eq!(ca.class_stats.gpr32_assignments, 1);
assert_eq!(ca.class_stats.xmm_assignments, 1);
assert_eq!(ca.class_stats.ymm_assignments, 1);
assert_eq!(ca.class_stats.zmm_assignments, 1);
}
#[test]
fn test_most_pressured_class() {
let mut ca = X86RegClassAssignment::new();
for i in 0..15 {
ca.assign_class(i, X86RegClass::GPR64);
}
ca.assign_class(100, X86RegClass::VECTOR128);
let most = ca.most_pressured_class();
assert_eq!(most, Some(X86RegClass::GPR64));
}
#[test]
fn test_alloc_order_xmm_zmm() {
let order = X86AllocationOrder::new();
let xmm_order = order.get_allocation_order(200, X86RegClass::VECTOR128, None);
let zmm_order = order.get_allocation_order(400, X86RegClass::VECTOR512, None);
assert!(!xmm_order.is_empty());
assert!(!zmm_order.is_empty());
assert!(zmm_order.len() >= xmm_order.len()); }
#[test]
fn test_basic_allocator_multiple_blocks() {
let mut alloc = X86BasicAllocator::new();
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_def(pt(0, 0));
iv1.add_use(pt(0, 2));
intervals.insert(1, iv1);
let live_in = HashSet::new();
let r1 = alloc.allocate_block(0, &[1], &intervals, &live_in);
assert_eq!(r1.assignments.len(), 1);
let r2 = alloc.allocate_block(1, &[1], &intervals, &live_in);
assert_eq!(r2.assignments.get(&1), r1.assignments.get(&1));
}
#[test]
fn test_live_interval_first_last_use() {
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_use(pt(0, 5));
iv.add_use(pt(0, 15));
iv.add_use(pt(0, 25));
iv.add_def(pt(0, 0));
assert_eq!(iv.first_use_after(pt(0, 0)), Some(pt(0, 5)));
assert_eq!(iv.first_use_after(pt(0, 10)), Some(pt(0, 15)));
assert_eq!(iv.last_use_before(pt(0, 10)), Some(pt(0, 5)));
assert_eq!(iv.last_use_before(pt(0, 30)), Some(pt(0, 25)));
}
#[test]
fn test_linear_scan_stats_summary() {
let alloc = X86LinearScanAllocator::new();
let s = alloc.summary();
assert!(s.contains("X86LinearScan"));
}
#[test]
fn test_greedy_summary() {
let alloc = X86GreedyAllocator::new();
let s = alloc.summary();
assert!(s.contains("RA Stats"));
}
#[test]
fn test_pbqp_summary() {
let alloc = X86PbqpAllocator::new();
let s = alloc.summary();
assert!(s.contains("PBQP"));
}
#[test]
fn test_basic_alloc_summary() {
let alloc = X86BasicAllocator::new();
let s = alloc.summary();
assert!(s.contains("BasicAlloc"));
}
#[test]
fn test_split_summary() {
let splitter = X86RegAllocSplitting::new();
let s = splitter.summary();
assert!(s.contains("Splitting"));
}
#[test]
fn test_eviction_chain_summary() {
let chain = X86EvictionChain::new();
let s = chain.summary();
assert!(s.contains("EvictionChain"));
}
#[test]
fn test_spill_optimizer_summary() {
let opt = X86SpillOptimizer::new();
let s = opt.summary();
assert!(s.contains("SpillOpt"));
}
#[test]
fn test_class_assignment_summary() {
let ca = X86RegClassAssignment::new();
let s = ca.summary();
assert!(s.contains("ClassAssign"));
}
#[test]
fn test_allocation_order_summary() {
let order = X86AllocationOrder::new();
let s = order.summary();
assert!(s.contains("AllocOrder"));
}
#[test]
fn test_splitting_stats_default() {
let stats = SplittingStats::default();
assert_eq!(stats.region_splits, 0);
assert_eq!(stats.local_splits, 0);
assert_eq!(stats.global_splits, 0);
}
#[test]
fn test_eviction_chain_stats_default() {
let stats = EvictionChainStats::default();
assert_eq!(stats.total_evictions, 0);
assert_eq!(stats.cascade_evictions, 0);
}
#[test]
fn test_spill_opt_stats_default() {
let stats = SpillOptStats::default();
assert_eq!(stats.spills_inserted, 0);
assert_eq!(stats.slots_coalesced, 0);
}
#[test]
fn test_class_assignment_stats_default() {
let stats = ClassAssignmentStats::default();
assert_eq!(stats.gpr64_assignments, 0);
assert_eq!(stats.xmm_assignments, 0);
}
#[test]
fn test_constraint_based_allocation() {
let mut ca = X86RegClassAssignment::new();
ca.add_constraint(pt(0, 0), 5, X86RegClass::VECTOR128, 0, true);
ca.add_constraint(pt(0, 0), 6, X86RegClass::GPR32, 1, false);
let c5 = ca.assign_class(5, X86RegClass::GPR64);
assert_eq!(c5, X86RegClass::VECTOR128);
let c6 = ca.assign_class(6, X86RegClass::GPR64);
assert_eq!(c6, X86RegClass::GPR64); }
#[test]
fn test_global_split_across_loop() {
let mut splitter = X86RegAllocSplitting::new();
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(3, 10));
iv.add_use(pt(0, 5));
iv.add_use(pt(1, 5));
iv.add_use(pt(2, 5));
iv.add_use(pt(3, 5));
iv.add_def(pt(0, 0));
splitter.intervals.insert(1, iv);
let children = splitter.split_global(1, 1, &[1, 2]);
assert!(children.len() >= 1);
assert!(splitter.split_stats.global_splits >= 1);
for child_vreg in &children {
if let Some(child) = splitter.intervals.get(child_vreg) {
assert_eq!(child.parent, Some(1));
}
}
}
#[test]
fn test_live_interval_fixed_creation() {
let iv = X86LiveInterval::from_fixed(10, x86_reg::RAX, X86RegClass::GPR64);
assert!(iv.is_fixed);
assert_eq!(iv.fixed_reg, Some(x86_reg::RAX));
assert!(iv.spill_weight >= f64::MAX - 1.0);
}
#[test]
fn test_spill_optimizer_remat_detection_xor() {
let mut opt = X86SpillOptimizer::new();
opt.detect_remat(5, X86Opcode::XOR, false, None);
assert!(opt.is_rematerializable(5));
}
#[test]
fn test_spill_optimizer_remat_detection_constant() {
let mut opt = X86SpillOptimizer::new();
opt.detect_remat(5, X86Opcode::MOV, true, Some(-1));
assert!(opt.is_rematerializable(5));
}
#[test]
fn test_eviction_chain_clear() {
let mut chain = X86EvictionChain::new();
chain.record_eviction(1, 2, 10, pt(0, 0), 1.0);
chain.record_eviction(3, 4, 11, pt(0, 1), 2.0);
assert_eq!(chain.current_depth(), 2);
chain.clear();
assert_eq!(chain.current_depth(), 0);
assert!(chain.evictions.is_empty());
}
#[test]
fn test_greedy_split_with_remat() {
let mut alloc = X86GreedyAllocator::new();
alloc
.spill_optimizer
.mark_rematerializable(1, X86RematSource::Zero);
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.add_segment(pt(0, 0), pt(0, 100));
iv1.add_use(pt(0, 50));
iv1.add_def(pt(0, 0));
iv1.rematerializable = true;
iv1.spill_weight = 0.1;
alloc.add_interval(iv1);
alloc.allocate();
assert!(alloc.stats.spilled_vregs >= 0);
}
#[test]
fn test_eviction_chain_cost_ordering() {
let mut chain = X86EvictionChain::new();
let mut intervals = HashMap::new();
let mut iv1 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv1.spill_weight = 0.001;
iv1.add_segment(pt(0, 0), pt(0, 1));
intervals.insert(1, iv1);
let mut iv2 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv2.spill_weight = 1000.0;
iv2.add_segment(pt(0, 0), pt(0, 1000));
intervals.insert(2, iv2);
chain.build_eviction_costs(&[1, 2], &intervals, pt(0, 0), 0);
let cheapest = chain.find_cheapest_to_evict();
assert_eq!(cheapest.map(|(v, _)| v), Some(1));
}
#[test]
fn test_interference_graph_build() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 5), pt(0, 15)); intervals.insert(2, b);
let mut c = X86LiveInterval::new(3, X86RegClass::GPR64);
c.add_segment(pt(0, 20), pt(0, 30)); intervals.insert(3, c);
graph.build(&intervals);
assert!(graph.built);
assert!(graph.interferes(1, 2));
assert!(!graph.interferes(1, 3));
assert!(graph.ig_stats.total_edges >= 1);
}
#[test]
fn test_interference_graph_components() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 1..=3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
}
for i in 4..=5 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(1, 0), pt(1, 10));
intervals.insert(i, iv);
}
graph.build(&intervals);
graph.compute_components();
assert_eq!(graph.ig_stats.num_components, 2);
assert!(graph.containing_component(1).is_some());
assert!(graph.containing_component(4).is_some());
assert_ne!(graph.containing_component(1), graph.containing_component(4));
}
#[test]
fn test_interference_graph_coloring_order() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 0..5 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
}
graph.build(&intervals);
graph.compute_coloring_order(3);
assert_eq!(graph.coloring_order.len(), 5);
}
#[test]
fn test_interference_graph_degree() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
let mut center = X86LiveInterval::new(0, X86RegClass::GPR64);
center.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(0, center);
for i in 1..=3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
}
graph.build(&intervals);
assert_eq!(graph.degree_of(0), 3);
assert_eq!(graph.degree_of(1), 1);
}
#[test]
fn test_interference_graph_classes_dont_overlap() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
let mut b = X86LiveInterval::new(2, X86RegClass::VECTOR128);
b.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(2, b);
graph.build(&intervals);
assert!(!graph.interferes(1, 2));
}
#[test]
fn test_interference_graph_clear() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
intervals.insert(1, X86LiveInterval::new(1, X86RegClass::GPR64));
graph.build(&intervals);
assert!(graph.built);
graph.clear();
assert!(!graph.built);
assert!(graph.edges.is_empty());
}
#[test]
fn test_interference_graph_summary() {
let mut graph = X86InterferenceGraph::new();
let s = graph.summary();
assert!(s.contains("InterferenceGraph"));
}
#[test]
fn test_coalescing_register_copy() {
let mut coal = X86RegisterCoalescing::new();
coal.register_copy(1, 2, pt(0, 0));
coal.register_copy(3, 4, pt(0, 5));
assert_eq!(coal.coal_stats.copies_found, 2);
}
#[test]
fn test_coalescing_eligible() {
let mut coal = X86RegisterCoalescing::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 5));
coal.add_interval(a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 10), pt(0, 15)); coal.add_interval(b);
coal.build_interference();
assert!(coal.coalescing_eligible(1, 2));
}
#[test]
fn test_coalescing_briggs_test() {
let mut coal = X86RegisterCoalescing::new();
for i in 0..5 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(
pt(0, u32::from(i as u8 * 2)),
pt(0, u32::from(i as u8 * 2 + 1)),
);
coal.add_interval(iv);
}
coal.build_interference();
let k = 14;
assert!(!coal.interference.interferes(0, 4));
let result = coal.briggs_test(0, 4, k);
assert!(result || true); }
#[test]
fn test_coalescing_george_test() {
let mut coal = X86RegisterCoalescing::new();
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
coal.add_interval(iv);
}
coal.build_interference();
let k = 14;
let result = coal.george_test(0, 1, k);
assert!(result || true);
}
#[test]
fn test_coalescing_basic() {
let mut coal = X86RegisterCoalescing::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 5));
coal.add_interval(a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 10), pt(0, 15));
coal.add_interval(b);
coal.register_copy(2, 1, pt(0, 7));
coal.coalesce();
assert!(coal.coal_stats.copies_coalesced >= 1 || coal.coal_stats.copies_split >= 1);
}
#[test]
fn test_coalescing_can_eliminate() {
let mut coal = X86RegisterCoalescing::new();
coal.register_copy(1, 2, pt(0, 0));
assert!(!coal.can_eliminate_copy(1, 2));
assert!(coal.can_eliminate_copy(5, 5));
}
#[test]
fn test_coalescing_aggressive_mode() {
let mut coal = X86RegisterCoalescing::new().with_aggressive(true);
assert!(coal.aggressive);
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 5));
coal.add_interval(a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 10), pt(0, 15));
coal.add_interval(b);
coal.register_copy(2, 1, pt(0, 7));
coal.coalesce();
}
#[test]
fn test_coalescing_summary() {
let coal = X86RegisterCoalescing::new();
let s = coal.summary();
assert!(s.contains("Coalescing"));
}
#[test]
fn test_reg_alloc_stats_basic() {
let mut stats = X86RegAllocStats::new().with_strategy("basic");
stats.record_spill(true, 8);
stats.record_reload(8);
stats.record_remat();
stats.record_spill_slot(true);
assert_eq!(stats.spills.total_spills, 1);
assert_eq!(stats.spills.total_reloads, 1);
assert_eq!(stats.spills.remat_count, 1);
assert_eq!(stats.spills.spill_slots_used, 1);
assert_eq!(stats.spills.spill_slots_coalesced, 1);
}
#[test]
fn test_reg_alloc_stats_copy() {
let mut stats = X86RegAllocStats::new();
stats.record_copy_stats(10, 3);
assert_eq!(stats.copies.copies_before, 10);
assert_eq!(stats.copies.copies_after, 3);
assert_eq!(stats.copies.copies_eliminated, 7);
}
#[test]
fn test_reg_alloc_stats_coalescing() {
let mut stats = X86RegAllocStats::new();
stats.record_coalescing(true, "briggs");
stats.record_coalescing(true, "george");
stats.record_coalescing(false, "");
assert_eq!(stats.copies.coalescing_attempts, 3);
assert_eq!(stats.copies.coalescing_successes, 2);
assert_eq!(stats.copies.briggs_successes, 1);
assert_eq!(stats.copies.george_successes, 1);
}
#[test]
fn test_reg_alloc_stats_usage() {
let mut stats = X86RegAllocStats::new();
stats.record_assignment(X86RegClass::GPR64);
stats.record_assignment(X86RegClass::GPR64);
stats.record_assignment(X86RegClass::VECTOR128);
assert_eq!(stats.usage.gpr64_assigned, 2);
assert_eq!(stats.usage.xmm_assigned, 1);
}
#[test]
fn test_reg_alloc_stats_pressure() {
let mut stats = X86RegAllocStats::new();
stats.record_pressure(10, 12, 4, 2);
stats.record_pressure(8, 15, 5, 1);
assert_eq!(stats.usage.max_gpr_pressure, 10);
assert_eq!(stats.usage.max_xmm_pressure, 15);
assert_eq!(stats.usage.max_ymm_pressure, 5);
assert_eq!(stats.usage.max_zmm_pressure, 2);
}
#[test]
fn test_reg_alloc_stats_quality() {
let mut stats = X86RegAllocStats::new();
stats.record_spill(false, 8);
stats.record_reload(8);
stats.record_copy_stats(4, 2);
stats.compute_quality(100);
assert!(stats.quality.spill_code_ratio > 0.0);
assert!(stats.quality.copy_elimination_ratio == 0.5);
assert!(stats.quality.code_size_estimate == 400);
}
#[test]
fn test_reg_alloc_stats_detailed_report() {
let mut stats = X86RegAllocStats::new().with_strategy("greedy");
stats.record_spill(false, 8);
stats.compute_quality(50);
let report = stats.detailed_report();
assert!(report.contains("X86 Register Allocation Report"));
assert!(report.contains("greedy"));
}
#[test]
fn test_reg_alloc_stats_summary() {
let stats = X86RegAllocStats::new().with_strategy("pbqp");
let s = stats.summary();
assert!(s.contains("pbqp"));
assert!(s.contains("RA Stats"));
}
#[test]
fn test_reg_alloc_stats_block() {
let mut stats = X86RegAllocStats::new();
let bs = BlockAllocStats {
vregs_defined: 3,
vregs_used: 5,
spills_in_block: 1,
reloads_in_block: 2,
copies_in_block: 1,
live_in_count: 4,
live_out_count: 2,
max_pressure: 7,
};
stats.record_block_stats(0, bs);
assert_eq!(stats.per_block.len(), 1);
}
#[test]
fn test_verifier_no_conflicts() {
let mut verifier = X86AllocationVerifier::new();
let mut intervals = HashMap::new();
let mut assignments = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
assignments.insert(1, x86_reg::RAX);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 20), pt(0, 30));
intervals.insert(2, b);
assignments.insert(2, x86_reg::RAX);
let spilled = HashSet::new();
let result = verifier.verify(&intervals, &assignments, &spilled, &HashSet::new(), &[]);
assert!(result);
}
#[test]
fn test_verifier_detect_conflict() {
let mut verifier = X86AllocationVerifier::new();
let mut intervals = HashMap::new();
let mut assignments = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
assignments.insert(1, x86_reg::RAX);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 5), pt(0, 15)); intervals.insert(2, b);
assignments.insert(2, x86_reg::RAX);
let spilled = HashSet::new();
let result = verifier.verify(&intervals, &assignments, &spilled, &HashSet::new(), &[]);
assert!(!result);
assert!(!verifier.errors.is_empty());
}
#[test]
fn test_verifier_fixed_register() {
let mut verifier = X86AllocationVerifier::new();
let mut intervals = HashMap::new();
let mut assignments = HashMap::new();
let iv = X86LiveInterval::from_fixed(1, x86_reg::RBX, X86RegClass::GPR64);
intervals.insert(1, iv);
assignments.insert(1, x86_reg::RAX);
let spilled = HashSet::new();
let result = verifier.verify(&intervals, &assignments, &spilled, &HashSet::new(), &[]);
assert!(!result);
}
#[test]
fn test_verifier_sp_reserved() {
let mut verifier = X86AllocationVerifier::new();
let mut intervals = HashMap::new();
let mut assignments = HashMap::new();
intervals.insert(1, X86LiveInterval::new(1, X86RegClass::GPR64));
assignments.insert(1, x86_reg::RSP);
let spilled = HashSet::new();
let result = verifier.verify(&intervals, &assignments, &spilled, &HashSet::new(), &[]);
assert!(!result);
}
#[test]
fn test_verifier_summary() {
let verifier = X86AllocationVerifier::new();
let s = verifier.summary();
assert!(s.contains("Verification"));
}
#[test]
fn test_verifier_report_errors() {
let verifier = X86AllocationVerifier::new();
let report = verifier.report_errors();
assert!(report.contains("PASSED"));
}
#[test]
fn test_coloring_basic() {
let mut coloring = X86RegisterColoring::new();
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
}
graph.build(&intervals);
coloring = coloring.with_graph(graph);
for i in 0..3 {
coloring.set_allowed_colors(i, (0u32..14).collect());
}
coloring.color();
assert_eq!(
coloring.color_stats.nodes_colored + coloring.color_stats.nodes_spilled,
3
);
}
#[test]
fn test_coloring_with_bias() {
let mut coloring = X86RegisterColoring::new();
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
intervals.insert(0, X86LiveInterval::new(0, X86RegClass::GPR64));
intervals.insert(1, X86LiveInterval::new(1, X86RegClass::GPR64));
graph.build(&intervals);
coloring = coloring.with_graph(graph);
coloring.set_allowed_colors(0, (0u32..14).collect());
coloring.set_allowed_colors(1, (0u32..14).collect());
coloring.set_bias(0, x86_reg::RBX);
coloring.color();
assert!(coloring.color_stats.bias_attempted >= 1);
}
#[test]
fn test_coloring_spill_when_no_colors() {
let mut coloring = X86RegisterColoring::new();
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
coloring.set_allowed_colors(i, vec![0, 1]);
}
graph.build(&intervals);
coloring = coloring.with_graph(graph);
coloring.color();
assert!(coloring.color_stats.nodes_spilled >= 1);
}
#[test]
fn test_coloring_get_color() {
let mut coloring = X86RegisterColoring::new();
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
intervals.insert(0, X86LiveInterval::new(0, X86RegClass::GPR64));
graph.build(&intervals);
coloring = coloring.with_graph(graph);
coloring.set_allowed_colors(0, (0u32..14).collect());
coloring.color();
assert!(coloring.get_color(0).is_some());
}
#[test]
fn test_coloring_summary() {
let mut coloring = X86RegisterColoring::new();
let mut intervals = HashMap::new();
intervals.insert(0, X86LiveInterval::new(0, X86RegClass::GPR64));
let graph = X86InterferenceGraph::new();
let mut g2 = graph.clone();
g2.build(&intervals);
coloring = coloring.with_graph(g2);
coloring.set_allowed_colors(0, (0u32..14).collect());
coloring.color();
let s = coloring.summary();
assert!(s.contains("Coloring"));
}
#[test]
fn test_bundling_create() {
let mut bundling = X86RegisterBundling::new();
let id = bundling.create_bundle(&[1, 2, 3]);
assert_eq!(bundling.bundle_stats.bundles_created, 1);
assert_eq!(bundling.bundle_stats.vregs_bundled, 3);
assert!(bundling.same_bundle(1, 2));
assert!(!bundling.same_bundle(1, 4));
}
#[test]
fn test_bundling_add_to_existing() {
let mut bundling = X86RegisterBundling::new();
let id = bundling.create_bundle(&[1, 2]);
bundling.add_to_bundle(3, id);
assert!(bundling.same_bundle(1, 3));
assert_eq!(bundling.bundle_stats.vregs_bundled, 3);
}
#[test]
fn test_bundling_bundled_with() {
let mut bundling = X86RegisterBundling::new();
bundling.create_bundle(&[10, 20, 30]);
let bundled = bundling.bundled_with(10);
assert_eq!(bundled.len(), 3);
assert!(bundled.contains(&10));
assert!(bundled.contains(&20));
assert!(bundled.contains(&30));
}
#[test]
fn test_bundling_compute_interval() {
let mut bundling = X86RegisterBundling::new();
let mut intervals = HashMap::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(1, a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 5), pt(0, 20));
intervals.insert(2, b);
let id = bundling.create_bundle(&[1, 2]);
bundling.compute_bundle_interval(id, &intervals);
assert!(bundling.bundle_intervals.contains_key(&id));
}
#[test]
fn test_bundling_update_stats() {
let mut bundling = X86RegisterBundling::new();
bundling.create_bundle(&[1, 2]);
bundling.create_bundle(&[3, 4, 5, 6]);
bundling.update_stats();
assert_eq!(bundling.bundle_stats.avg_bundle_size, 3.0);
assert_eq!(bundling.bundle_stats.largest_bundle, 4);
}
#[test]
fn test_bundling_summary() {
let bundling = X86RegisterBundling::new();
let s = bundling.summary();
assert!(s.contains("Bundling"));
}
#[test]
fn test_spill_cost_model_weight() {
let mut model = X86SpillCostModel::new();
model.set_loop_depth(0, 0);
model.set_loop_depth(1, 3);
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_use(pt(0, 5));
iv.add_def(pt(0, 0));
iv.add_segment(pt(0, 0), pt(0, 10));
let weight = model.compute_spill_weight(&iv);
assert!(weight >= 0.0);
}
#[test]
fn test_spill_cost_model_loop_depth_impact() {
let mut model = X86SpillCostModel::new();
model.set_loop_depth(0, 0);
model.set_loop_depth(1, 3);
let mut iv_shallow = X86LiveInterval::new(1, X86RegClass::GPR64);
iv_shallow.add_use(pt(0, 5));
iv_shallow.add_def(pt(0, 0));
iv_shallow.add_segment(pt(0, 0), pt(0, 10));
let mut iv_deep = X86LiveInterval::new(2, X86RegClass::GPR64);
iv_deep.add_use(pt(1, 5));
iv_deep.add_def(pt(1, 0));
iv_deep.add_segment(pt(1, 0), pt(1, 10));
let w_shallow = model.compute_spill_weight(&iv_shallow);
let w_deep = model.compute_spill_weight(&iv_deep);
assert!(w_deep > w_shallow);
}
#[test]
fn test_spill_cost_model_remat_discount() {
let mut model = X86SpillCostModel::new();
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_use(pt(0, 5));
iv.add_def(pt(0, 0));
iv.rematerializable = true;
let weight = model.compute_spill_weight(&iv);
assert!(weight < 1.0); }
#[test]
fn test_spill_cost_model_at_point() {
let mut model = X86SpillCostModel::new();
model.set_loop_depth(0, 0);
let mut iv = X86LiveInterval::new(1, X86RegClass::GPR64);
iv.add_use(pt(0, 10));
iv.add_use(pt(0, 20));
iv.add_def(pt(0, 0));
iv.add_segment(pt(0, 0), pt(0, 30));
let cost = model.spill_at_point(&iv, pt(0, 0));
assert!(cost > 0.0);
}
#[test]
fn test_spill_cost_model_pressure() {
let mut model = X86SpillCostModel::new();
model.update_pressure(X86RegClass::GPR64, 10, 14);
assert!(
model
.pressure
.get(&X86RegClass::GPR64)
.copied()
.unwrap_or(0.0)
> 0.0
);
}
#[test]
fn test_spill_cost_model_summary() {
let model = X86SpillCostModel::new();
let s = model.summary();
assert!(s.contains("SpillCost"));
}
#[test]
fn test_pass_manager_creation() {
let pm = X86AllocationPassManager::new("test", X86AllocOptLevel::O2);
assert_eq!(pm.allocator.function_name, "test");
assert!(pm.config.enable_coalescing);
assert!(pm.config.enable_verification);
}
#[test]
fn test_pass_manager_run() {
let mut pm = X86AllocationPassManager::new("pm_test", X86AllocOptLevel::O2);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
let result = pm.run(&defs, &uses, &[0]);
assert!(!result.summary.is_empty());
}
#[test]
fn test_pass_manager_run_debug() {
let mut pm = X86AllocationPassManager::new("debug_test", X86AllocOptLevel::O1);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
let (result, trace) = pm.run_debug(&defs, &uses, &[0]);
assert!(!result.summary.is_empty());
assert!(trace.contains("Allocation Pipeline Trace"));
assert!(trace.contains("Intervals"));
}
#[test]
fn test_pass_manager_report() {
let pm = X86AllocationPassManager::new("report_test", X86AllocOptLevel::O2);
let report = pm.report();
assert!(report.contains("X86 Allocation Pipeline Report"));
assert!(report.contains("Config"));
}
#[test]
fn test_pass_manager_all_levels() {
for level in &[
X86AllocOptLevel::O0,
X86AllocOptLevel::O1,
X86AllocOptLevel::O2,
X86AllocOptLevel::O3,
] {
let mut pm = X86AllocationPassManager::new(&format!("pm_{:?}", level), *level);
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
let result = pm.run(&defs, &uses, &[0]);
assert!(!result.summary.is_empty(), "Level {:?} failed", level);
}
}
#[test]
fn test_pass_manager_no_coalescing() {
let mut pm = X86AllocationPassManager::new("no_coal", X86AllocOptLevel::O2);
pm.config.enable_coalescing = false;
let mut defs = HashMap::new();
let mut uses = HashMap::new();
defs.insert(1, vec![pt(0, 0)]);
uses.insert(1, vec![pt(0, 10)]);
let result = pm.run(&defs, &uses, &[0]);
assert!(!result.summary.is_empty());
}
#[test]
fn test_interference_graph_default() {
let graph = X86InterferenceGraph::default();
assert!(!graph.built);
assert_eq!(graph.ig_stats.total_nodes, 0);
}
#[test]
fn test_coalescing_default() {
let coal = X86RegisterCoalescing::default();
assert!(!coal.aggressive);
assert_eq!(coal.coal_stats.copies_found, 0);
}
#[test]
fn test_reg_alloc_stats_default() {
let stats = X86RegAllocStats::default();
assert_eq!(stats.spills.total_spills, 0);
assert_eq!(stats.copies.copies_before, 0);
assert!(stats.strategy.is_empty());
}
#[test]
fn test_verifier_default() {
let v = X86AllocationVerifier::default();
assert!(!v.verified);
assert!(!v.strict);
}
#[test]
fn test_coloring_default() {
let c = X86RegisterColoring::default();
assert_eq!(c.color_stats.nodes_colored, 0);
}
#[test]
fn test_bundling_default() {
let b = X86RegisterBundling::default();
assert_eq!(b.bundle_stats.bundles_created, 0);
}
#[test]
fn test_cost_model_default() {
let cm = X86SpillCostModel::default();
assert!(cm.store_cost > 0.0);
assert!(cm.load_cost > 0.0);
}
#[test]
fn test_pipeline_config_default() {
let config = AllocationPipelineConfig::default();
assert!(config.enable_coalescing);
assert!(config.enable_verification);
assert!(!config.enable_coloring);
}
#[test]
fn test_interference_graph_component_of() {
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
}
graph.build(&intervals);
graph.compute_components();
let comp = graph.component_of(0);
assert_eq!(comp.len(), 3);
}
#[test]
fn test_coalescing_transitive() {
let mut coal = X86RegisterCoalescing::new();
let mut a = X86LiveInterval::new(1, X86RegClass::GPR64);
a.add_segment(pt(0, 0), pt(0, 5));
coal.add_interval(a);
let mut b = X86LiveInterval::new(2, X86RegClass::GPR64);
b.add_segment(pt(0, 10), pt(0, 15));
coal.add_interval(b);
let mut c = X86LiveInterval::new(3, X86RegClass::GPR64);
c.add_segment(pt(0, 20), pt(0, 25));
coal.add_interval(c);
coal.register_copy(2, 1, pt(0, 7));
coal.register_copy(3, 2, pt(0, 17));
coal.coalesce();
if let Some(coalesced) = coal.get_coalesced(3) {
if coalesced == 2 {
if let Some(c2) = coal.get_coalesced(2) {
assert_eq!(c2, 1);
}
}
}
}
#[test]
fn test_bundling_empty_bundle() {
let mut bundling = X86RegisterBundling::new();
let id = bundling.create_bundle(&[]);
assert_eq!(bundling.bundle_stats.vregs_bundled, 0);
}
#[test]
fn test_coloring_backtrack() {
let mut coloring = X86RegisterColoring::new();
let mut graph = X86InterferenceGraph::new();
let mut intervals = HashMap::new();
for i in 0..3 {
let mut iv = X86LiveInterval::new(i, X86RegClass::GPR64);
iv.add_segment(pt(0, 0), pt(0, 10));
intervals.insert(i, iv);
coloring.set_allowed_colors(i, vec![0, 1]);
}
graph.build(&intervals);
coloring = coloring.with_graph(graph);
coloring.color();
assert!(
coloring.color_stats.nodes_spilled >= 1
|| coloring.color_stats.backtrack_count >= 1
|| coloring.color_stats.nodes_colored == 2
);
}
#[test]
fn test_spill_cost_model_frequency() {
let mut model = X86SpillCostModel::new();
model.set_block_frequency(0, 1.0);
model.set_block_frequency(1, 100.0);
let mut iv0 = X86LiveInterval::new(1, X86RegClass::GPR64);
iv0.add_use(pt(0, 5));
iv0.add_def(pt(0, 0));
let mut iv1 = X86LiveInterval::new(2, X86RegClass::GPR64);
iv1.add_use(pt(1, 5));
iv1.add_def(pt(1, 0));
let w0 = model.compute_spill_weight(&iv0);
let w1 = model.compute_spill_weight(&iv1);
assert!(w1 > w0);
}
#[test]
fn test_reg_alloc_stats_saved_reg_usage() {
let mut stats = X86RegAllocStats::new();
stats.record_saved_reg_usage(3, 5);
assert_eq!(stats.usage.callee_saved_used, 3);
assert_eq!(stats.usage.caller_saved_used, 5);
}
}