use crate::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand};
use crate::codegen_opt2_x86::X86VEXEncoding;
use crate::machine_scheduler::*;
use crate::x86::x86_full_instr_info::{
EncodingForm, InstrEncodingInfo, X86FullInstrInfo, X86FullOpcode,
};
use crate::x86::x86_instr_info::{
OperandType, X86InstrDesc, X86InstrInfo, X86MemOperand, X86Opcode, X86Operand, X86SchedInfo,
};
use crate::x86::x86_register_info::{X86RegisterInfo, X86_64_REG_COUNT};
use crate::x86::x86_schedule_model::{
InstrItinerary, ProcResource, ReadAdvance, SchedMachineModel, SchedModel, WriteLatency,
WriteRes, X86SchedModelKind,
};
use crate::x86::x86_subtarget::X86Subtarget;
use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;
pub type SchedNodeId = usize;
pub type SchedCycle = u64;
pub type IssueCount = u32;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum SchedReg {
Virt(u32),
Phys(u32),
}
impl SchedReg {
pub fn id(self) -> u32 {
match self {
SchedReg::Virt(v) => v,
SchedReg::Phys(p) => p,
}
}
pub fn is_phys(self) -> bool {
matches!(self, SchedReg::Phys(_))
}
pub fn is_virt(self) -> bool {
matches!(self, SchedReg::Virt(_))
}
fn to_key(self) -> u64 {
match self {
SchedReg::Virt(v) => v as u64,
SchedReg::Phys(p) => (p as u64) + (1u64 << 40),
}
}
}
impl fmt::Display for SchedReg {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
SchedReg::Virt(v) => write!(f, "%%{}", v),
SchedReg::Phys(p) => write!(f, "$p{}", p),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86EdgeKind {
True,
Anti,
Output,
Chain,
Glue,
Barrier,
Memory,
}
impl X86EdgeKind {
pub fn is_true(self) -> bool {
matches!(self, X86EdgeKind::True)
}
pub fn is_renamable(self) -> bool {
matches!(self, X86EdgeKind::Anti | X86EdgeKind::Output)
}
pub fn is_ordering(self) -> bool {
matches!(
self,
X86EdgeKind::Chain | X86EdgeKind::Barrier | X86EdgeKind::Memory
)
}
pub fn as_str(self) -> &'static str {
match self {
X86EdgeKind::True => "true",
X86EdgeKind::Anti => "anti",
X86EdgeKind::Output => "output",
X86EdgeKind::Chain => "chain",
X86EdgeKind::Glue => "glue",
X86EdgeKind::Barrier => "barrier",
X86EdgeKind::Memory => "memory",
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedNode {
pub instr_idx: usize,
pub opcode: u32,
pub defs: Vec<SchedReg>,
pub uses: Vec<SchedReg>,
pub may_load: bool,
pub may_store: bool,
pub is_branch: bool,
pub is_call: bool,
pub has_side_effects: bool,
pub defines_flags: bool,
pub uses_flags: bool,
pub latency: u32,
pub micro_ops: u32,
pub succs: Vec<SchedNodeId>,
pub preds: Vec<SchedNodeId>,
pub unscheduled_preds: usize,
pub height: u32,
pub depth: u32,
pub asap: SchedCycle,
pub alap: SchedCycle,
pub slack: SchedCycle,
pub scheduled: bool,
pub scheduled_cycle: SchedCycle,
pub assigned_port: Option<ProcResource>,
pub bundleable: bool,
pub is_terminator: bool,
}
impl X86SchedNode {
pub fn new(instr_idx: usize, opcode: u32) -> Self {
Self {
instr_idx,
opcode,
defs: Vec::new(),
uses: Vec::new(),
may_load: false,
may_store: false,
is_branch: false,
is_call: false,
has_side_effects: false,
defines_flags: false,
uses_flags: false,
latency: 1,
micro_ops: 1,
succs: Vec::new(),
preds: Vec::new(),
unscheduled_preds: 0,
height: 0,
depth: 0,
asap: 0,
alap: 0,
slack: 0,
scheduled: false,
scheduled_cycle: 0,
assigned_port: None,
bundleable: false,
is_terminator: false,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedEdge {
pub from: SchedNodeId,
pub to: SchedNodeId,
pub kind: X86EdgeKind,
pub reg: Option<SchedReg>,
pub min_latency: u32,
}
impl X86SchedEdge {
pub fn new(from: SchedNodeId, to: SchedNodeId, kind: X86EdgeKind, min_latency: u32) -> Self {
Self {
from,
to,
kind,
reg: None,
min_latency,
}
}
pub fn with_reg(
from: SchedNodeId,
to: SchedNodeId,
kind: X86EdgeKind,
reg: SchedReg,
min_latency: u32,
) -> Self {
Self {
from,
to,
kind,
reg: Some(reg),
min_latency,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedDAG {
pub nodes: Vec<X86SchedNode>,
pub edges: Vec<X86SchedEdge>,
pub succ_edges: Vec<Vec<usize>>,
pub pred_edges: Vec<Vec<usize>>,
pub node_count: usize,
pub critical_path_length: u32,
pub critical_path_nodes: Vec<SchedNodeId>,
pub is_post_ra: bool,
}
impl X86SchedDAG {
pub fn new() -> Self {
Self {
nodes: Vec::new(),
edges: Vec::new(),
succ_edges: Vec::new(),
pred_edges: Vec::new(),
node_count: 0,
critical_path_length: 0,
critical_path_nodes: Vec::new(),
is_post_ra: false,
}
}
pub fn build(
instructions: &[MachineInstr],
model: Option<&SchedModel>,
instr_info: Option<&X86InstrInfo>,
is_post_ra: bool,
) -> Self {
let n = instructions.len();
let mut dag = X86SchedDAG::new();
dag.is_post_ra = is_post_ra;
dag.node_count = n;
for (idx, mi) in instructions.iter().enumerate() {
let mut node = X86SchedNode::new(idx, mi.opcode);
dag.classify_instruction(&mut node, mi, model, instr_info, is_post_ra);
node.latency = dag.lookup_latency(&node, mi, model);
dag.nodes.push(node);
}
dag.succ_edges = vec![Vec::new(); n];
dag.pred_edges = vec![Vec::new(); n];
dag.build_register_deps(instructions, is_post_ra);
dag.build_ordering_edges(instructions);
dag.build_barrier_edges();
for node in &mut dag.nodes {
node.unscheduled_preds = node.preds.len();
}
dag.compute_heights_and_depths();
dag.compute_asap_alap();
dag.identify_critical_path();
dag
}
fn classify_instruction(
&self,
node: &mut X86SchedNode,
mi: &MachineInstr,
model: Option<&SchedModel>,
_instr_info: Option<&X86InstrInfo>,
is_post_ra: bool,
) {
let op = mi.opcode;
if let Some(def_vreg) = mi.def {
if is_post_ra {
node.defs.push(SchedReg::Phys(def_vreg));
} else {
node.defs.push(SchedReg::Virt(def_vreg));
}
}
for opnd in &mi.operands {
if let MachineOperand::Reg(r) = opnd {
node.uses.push(if is_post_ra {
SchedReg::Phys(*r)
} else {
SchedReg::Virt(*r)
});
} else if let MachineOperand::PhysReg(r) = opnd {
node.uses.push(SchedReg::Phys(*r));
}
}
node.may_load = Self::is_load_opcode(op);
node.may_store = Self::is_store_opcode(op);
node.is_branch = Self::is_branch_opcode(op);
node.is_call = Self::is_call_opcode(op);
node.has_side_effects = node.is_call || Self::is_side_effect_opcode(op);
node.defines_flags = Self::is_flag_defining_opcode(op);
node.uses_flags = Self::is_flag_using_opcode(op);
node.is_terminator = Self::is_terminator_opcode(op);
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == op {
node.micro_ops = itin.uops;
break;
}
}
}
node.bundleable = !node.is_branch && !node.is_call && !node.has_side_effects;
}
fn lookup_latency(
&self,
node: &X86SchedNode,
_mi: &MachineInstr,
model: Option<&SchedModel>,
) -> u32 {
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == node.opcode {
return itin.latency;
}
}
}
if node.may_load {
if let Some(m) = model {
m.machine.load_latency
} else {
4
}
} else if node.may_store {
1
} else if node.is_branch || node.is_call {
1
} else {
1
}
}
fn build_register_deps(&mut self, instructions: &[MachineInstr], is_post_ra: bool) {
let n = instructions.len();
let mut last_def: HashMap<u64, SchedNodeId> = HashMap::new();
let mut last_uses: HashMap<u64, Vec<SchedNodeId>> = HashMap::new();
for i in 0..n {
let defs_i = self.nodes[i].defs.clone();
let uses_i = self.nodes[i].uses.clone();
for u in &uses_i {
let key = u.to_key();
if let Some(&def_idx) = last_def.get(&key) {
if def_idx < i {
let lat = self.nodes[def_idx].latency;
self.add_edge(def_idx, i, X86EdgeKind::True, Some(*u), lat);
}
}
}
for d in &defs_i {
let key = d.to_key();
if let Some(&prev_def) = last_def.get(&key) {
if prev_def < i {
self.add_edge(prev_def, i, X86EdgeKind::Output, Some(*d), 0);
}
}
if let Some(uses) = last_uses.get(&key) {
for &u_idx in uses {
if u_idx < i {
self.add_edge(u_idx, i, X86EdgeKind::Anti, Some(*d), 1);
}
}
}
last_def.insert(key, i);
last_uses.remove(&key);
}
for u in &uses_i {
let key = u.to_key();
last_uses.entry(key).or_default().push(i);
}
}
}
fn build_ordering_edges(&mut self, instructions: &[MachineInstr]) {
let n = instructions.len();
if n < 2 {
return;
}
let mut last_side_effect: Option<SchedNodeId> = None;
let mut last_store: Option<SchedNodeId> = None;
let mut last_flags_def: Option<SchedNodeId> = None;
let node_flags: Vec<(bool, bool, bool, bool)> = (0..n)
.map(|i| {
let node = &self.nodes[i];
(
node.has_side_effects || node.is_branch,
node.may_store,
node.uses_flags,
node.defines_flags,
)
})
.collect();
for i in 0..n {
let (has_side_eff, may_store, uses_flags, defines_flags) = node_flags[i];
if has_side_eff {
if let Some(p) = last_side_effect {
if p < i {
self.add_edge(p, i, X86EdgeKind::Chain, None, 0);
}
}
last_side_effect = Some(i);
}
if may_store {
if let Some(p) = last_store {
if p < i {
self.add_edge(p, i, X86EdgeKind::Memory, None, 0);
}
}
if let Some(p) = last_side_effect {
if p < i && last_store.map_or(true, |ls| p != ls) {
self.add_edge(p, i, X86EdgeKind::Chain, None, 0);
}
}
last_store = Some(i);
}
if uses_flags {
if let Some(p) = last_flags_def {
if p < i {
self.add_edge(p, i, X86EdgeKind::Glue, None, 1);
}
}
}
if defines_flags {
last_flags_def = Some(i);
}
}
}
fn build_barrier_edges(&mut self) {
let n = self.node_count;
for i in 0..n {
if self.nodes[i].is_call {
for j in 0..i {
if !self.has_edge(j, i) && self.nodes[j].may_store {
self.add_edge(j, i, X86EdgeKind::Barrier, None, 0);
}
}
for j in (i + 1)..n {
if !self.has_edge(i, j) && !self.nodes[j].is_call {
self.add_edge(i, j, X86EdgeKind::Barrier, None, 0);
}
}
}
if self.nodes[i].is_terminator {
for j in 0..i {
if !self.has_edge(j, i) {
self.add_edge(j, i, X86EdgeKind::Barrier, None, 0);
}
}
}
}
}
fn add_edge(
&mut self,
from: SchedNodeId,
to: SchedNodeId,
kind: X86EdgeKind,
reg: Option<SchedReg>,
min_latency: u32,
) {
if self.has_edge(from, to) {
return;
}
let edge_idx = self.edges.len();
self.edges.push(X86SchedEdge {
from,
to,
kind,
reg,
min_latency,
});
self.nodes[from].succs.push(to);
self.nodes[to].preds.push(from);
self.succ_edges[from].push(edge_idx);
self.pred_edges[to].push(edge_idx);
}
fn has_edge(&self, from: SchedNodeId, to: SchedNodeId) -> bool {
self.nodes[from].succs.contains(&to)
}
fn compute_heights_and_depths(&mut self) {
let n = self.node_count;
if n == 0 {
return;
}
for i in (0..n).rev() {
let node_lat = self.nodes[i].latency;
let max_succ_h = self.nodes[i]
.succs
.iter()
.map(|&s| self.nodes[s].height)
.max()
.unwrap_or(0);
self.nodes[i].height = node_lat + max_succ_h;
}
for i in 0..n {
let node_lat = self.nodes[i].latency;
let max_pred_d = self.nodes[i]
.preds
.iter()
.map(|&p| self.nodes[p].depth)
.max()
.unwrap_or(0);
self.nodes[i].depth = max_pred_d + node_lat;
}
}
fn compute_asap_alap(&mut self) {
let n = self.node_count;
if n == 0 {
return;
}
for i in 0..n {
let mut earliest: SchedCycle = 0;
for &p in &self.nodes[i].preds {
let finish = self.nodes[p].asap + self.nodes[p].latency as u64;
if finish > earliest {
earliest = finish;
}
}
self.nodes[i].asap = earliest;
}
let max_cycle = self.nodes.iter().map(|nd| nd.asap).max().unwrap_or(0);
for node in &mut self.nodes {
node.alap = max_cycle;
}
for i in (0..n).rev() {
let mut latest: SchedCycle = max_cycle;
for &s in &self.nodes[i].succs {
let s_start = self.nodes[s].alap;
let min_delta = self.nodes[i].latency as u64;
if s_start >= min_delta && s_start - min_delta < latest {
latest = s_start - min_delta;
}
}
self.nodes[i].alap = latest;
}
for node in &mut self.nodes {
node.slack = node.alap.saturating_sub(node.asap);
}
}
fn identify_critical_path(&mut self) {
let n = self.node_count;
if n == 0 {
return;
}
let mut current = 0usize;
let mut max_depth = 0u32;
for i in 0..n {
if self.nodes[i].depth > max_depth {
max_depth = self.nodes[i].depth;
current = i;
}
}
let mut path: Vec<SchedNodeId> = Vec::new();
let mut visited: HashSet<SchedNodeId> = HashSet::new();
let mut total = 0u32;
loop {
path.push(current);
visited.insert(current);
total += self.nodes[current].latency;
let mut best_succ: Option<SchedNodeId> = None;
let mut best_h = 0u32;
for &s in &self.nodes[current].succs {
if !visited.contains(&s) && self.nodes[s].height > best_h {
best_h = self.nodes[s].height;
best_succ = Some(s);
}
}
match best_succ {
Some(s) => current = s,
None => break,
}
}
self.critical_path_length = total;
self.critical_path_nodes = path;
}
fn is_load_opcode(op: u32) -> bool {
matches!(op, 2 | 3 | 20 | 21 | 200 | 201 | 400 | 401 | 402 | 403)
}
fn is_store_opcode(op: u32) -> bool {
matches!(op, 100 | 101 | 102 | 103 | 500 | 501 | 502)
}
fn is_branch_opcode(op: u32) -> bool {
matches!(op, 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40)
}
fn is_call_opcode(op: u32) -> bool {
matches!(op, 43 | 44)
}
fn is_side_effect_opcode(op: u32) -> bool {
matches!(op, 700 | 701 | 702)
}
fn is_flag_defining_opcode(op: u32) -> bool {
matches!(
op,
1 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 60 | 61
) || (op >= 200 && op <= 220)
}
fn is_flag_using_opcode(op: u32) -> bool {
matches!(op, 30..=39 | 70..=89 | 120 | 121)
}
fn is_terminator_opcode(op: u32) -> bool {
matches!(op, 40 | 41 | 42)
}
}
impl Default for X86SchedDAG {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86SchedPriorityKind {
CriticalPath,
LatencyWeighted,
ResourceCritical,
RegPressure,
BalancedILP,
}
#[derive(Debug, Clone)]
pub struct X86SchedPriority {
pub kind: X86SchedPriorityKind,
pub priorities: Vec<i64>,
dag_node_count: usize,
}
impl X86SchedPriority {
pub fn compute(dag: &X86SchedDAG, kind: X86SchedPriorityKind) -> Self {
let n = dag.node_count;
let mut sp = Self {
kind,
priorities: vec![0i64; n],
dag_node_count: n,
};
match kind {
X86SchedPriorityKind::CriticalPath => sp.compute_critical_path(dag),
X86SchedPriorityKind::LatencyWeighted => sp.compute_latency_weighted(dag),
X86SchedPriorityKind::ResourceCritical => sp.compute_resource_critical(dag),
X86SchedPriorityKind::RegPressure => sp.compute_reg_pressure(dag),
X86SchedPriorityKind::BalancedILP => sp.compute_balanced_ilp(dag),
}
sp
}
fn compute_critical_path(&mut self, dag: &X86SchedDAG) {
for i in 0..dag.node_count {
self.priorities[i] = dag.nodes[i].height as i64;
}
}
fn compute_latency_weighted(&mut self, dag: &X86SchedDAG) {
for i in 0..dag.node_count {
let node = &dag.nodes[i];
let fanout = node.succs.len() as i64;
self.priorities[i] = (node.latency as i64) * (1 + fanout);
}
}
fn compute_resource_critical(&mut self, dag: &X86SchedDAG) {
for i in 0..dag.node_count {
let node = &dag.nodes[i];
let uops = node.micro_ops.max(1) as i64;
self.priorities[i] = uops * 100 + node.height as i64;
}
}
fn compute_reg_pressure(&mut self, dag: &X86SchedDAG) {
let mut use_counts: HashMap<u64, usize> = HashMap::new();
for node in &dag.nodes {
for u in &node.uses {
*use_counts.entry(u.to_key()).or_default() += 1;
}
}
for i in 0..dag.node_count {
let node = &dag.nodes[i];
let mut score = node.height as i64 * 10;
for u in &node.uses {
if let Some(&cnt) = use_counts.get(&u.to_key()) {
if cnt == 1 {
score += 100; }
}
}
self.priorities[i] = score;
}
}
fn compute_balanced_ilp(&mut self, dag: &X86SchedDAG) {
for i in 0..dag.node_count {
let node = &dag.nodes[i];
let height_score = node.height as f64 * 0.4;
let latency_score = (node.latency as f64) * (node.succs.len() as f64 + 1.0) * 0.3;
let resource_score = (node.micro_ops.max(1) as f64) * 0.3;
self.priorities[i] = ((height_score + latency_score + resource_score) * 100.0) as i64;
}
}
pub fn get(&self, node_id: SchedNodeId) -> i64 {
self.priorities.get(node_id).copied().unwrap_or(0)
}
pub fn compare(&self, a: SchedNodeId, b: SchedNodeId) -> Ordering {
let pa = self.get(a);
let pb = self.get(b);
pb.cmp(&pa).then_with(|| a.cmp(&b))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86PipelineHazard {
None,
Structural(ProcResource),
Data {
producer: SchedNodeId,
consumer: SchedNodeId,
cycles_to_wait: u32,
},
IssueWidth(u32),
LoadUse {
load_node: SchedNodeId,
use_node: SchedNodeId,
stall_cycles: u32,
},
}
#[derive(Debug, Clone)]
struct ScoreboardEntry {
node_id: SchedNodeId,
issue_cycle: SchedCycle,
result_ready_cycle: SchedCycle,
resources: Vec<(ProcResource, SchedCycle)>,
}
#[derive(Debug, Clone)]
pub struct X86SchedHazardRecognizer {
pub current_cycle: SchedCycle,
pub issue_width: u32,
pub issued_this_cycle: u32,
resource_free_cycles: HashMap<ProcResource, Vec<SchedCycle>>,
scoreboard: Vec<ScoreboardEntry>,
reg_ready: HashMap<u64, SchedCycle>,
load_use_penalty: u32,
bypass_table: HashMap<(ProcResource, ProcResource), u32>,
issued_nodes: HashSet<SchedNodeId>,
}
impl X86SchedHazardRecognizer {
pub fn new(issue_width: u32) -> Self {
Self {
current_cycle: 0,
issue_width,
issued_this_cycle: 0,
resource_free_cycles: HashMap::new(),
scoreboard: Vec::new(),
reg_ready: HashMap::new(),
load_use_penalty: 3,
bypass_table: HashMap::new(),
issued_nodes: HashSet::new(),
}
}
pub fn init_resources(&mut self, resources: &[ProcResource], counts: &[u32]) {
self.resource_free_cycles.clear();
for (res, &count) in resources.iter().zip(counts.iter()) {
self.resource_free_cycles
.insert(*res, vec![0u64; count as usize]);
}
self.bypass_table
.insert((ProcResource::Port0, ProcResource::Port0), 0);
self.bypass_table
.insert((ProcResource::Port1, ProcResource::Port1), 0);
self.bypass_table
.insert((ProcResource::Port5, ProcResource::Port5), 0);
}
pub fn advance_cycle(&mut self) {
self.current_cycle += 1;
self.issued_this_cycle = 0;
}
pub fn check_hazard(
&self,
node: &X86SchedNode,
dag: &X86SchedDAG,
model: Option<&SchedModel>,
) -> Option<X86PipelineHazard> {
let nid = node.instr_idx;
if self.issued_this_cycle >= self.issue_width {
return Some(X86PipelineHazard::IssueWidth(self.issue_width));
}
for &p in &node.preds {
if !self.issued_nodes.contains(&p) {
continue; }
let p_regs = &dag.nodes[p].defs;
for r in p_regs {
if let Some(&ready_cycle) = self.reg_ready.get(&r.to_key()) {
if ready_cycle > self.current_cycle {
let wait = (ready_cycle - self.current_cycle) as u32;
let bypass = self
.bypass_table
.get(&(ProcResource::Port0, ProcResource::Port0))
.copied()
.unwrap_or(0);
if wait > bypass {
return Some(X86PipelineHazard::Data {
producer: p,
consumer: nid,
cycles_to_wait: wait - bypass,
});
}
}
}
}
}
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == node.opcode {
for wr in &itin.write_resources {
let insts = self.resource_free_cycles.get(&wr.resource);
if let Some(cycles) = insts {
let busy =
cycles.iter().filter(|&&c| c > self.current_cycle).count() as u32;
if busy >= cycles.len() as u32 {
return Some(X86PipelineHazard::Structural(wr.resource));
}
}
}
break;
}
}
}
if self.load_use_penalty > 0 {
for &p in &node.preds {
if dag.nodes[p].may_load {
for u in &node.uses {
for d in &dag.nodes[p].defs {
if u == d {
let ready =
dag.nodes[p].scheduled_cycle + dag.nodes[p].latency as u64;
if ready + self.load_use_penalty as u64 > self.current_cycle {
let stall = (ready + self.load_use_penalty as u64)
.saturating_sub(self.current_cycle)
as u32;
if stall > 0 {
return Some(X86PipelineHazard::LoadUse {
load_node: p,
use_node: nid,
stall_cycles: stall,
});
}
}
}
}
}
}
}
}
None
}
pub fn issue_node(&mut self, node: &X86SchedNode, model: Option<&SchedModel>) {
let result_ready = self.current_cycle + node.latency as u64;
let mut resources: Vec<(ProcResource, SchedCycle)> = Vec::new();
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == node.opcode {
for wr in &itin.write_resources {
let cycle = self.current_cycle + wr.cycles as u64;
resources.push((wr.resource, cycle));
if let Some(free_cycles) = self.resource_free_cycles.get_mut(&wr.resource) {
if let Some(slot) = free_cycles.iter_mut().min() {
if *slot < self.current_cycle {
*slot = self.current_cycle;
}
*slot += wr.cycles as u64;
}
}
}
break;
}
}
}
for d in &node.defs {
self.reg_ready.insert(d.to_key(), result_ready);
}
self.scoreboard.push(ScoreboardEntry {
node_id: node.instr_idx,
issue_cycle: self.current_cycle,
result_ready_cycle: result_ready,
resources,
});
self.issued_nodes.insert(node.instr_idx);
self.issued_this_cycle += 1;
}
pub fn retire_completed(&mut self) {
self.scoreboard
.retain(|e| e.result_ready_cycle > self.current_cycle);
}
pub fn resource_available(&self, res: ProcResource) -> bool {
if let Some(cycles) = self.resource_free_cycles.get(&res) {
cycles.iter().any(|&c| c <= self.current_cycle)
} else {
true
}
}
pub fn resource_available_count(&self, res: ProcResource) -> u32 {
if let Some(cycles) = self.resource_free_cycles.get(&res) {
cycles.iter().filter(|&&c| c <= self.current_cycle).count() as u32
} else {
self.issue_width
}
}
pub fn set_load_use_penalty(&mut self, cycles: u32) {
self.load_use_penalty = cycles;
}
pub fn add_bypass(&mut self, from: ProcResource, to: ProcResource, reduction: u32) {
self.bypass_table.insert((from, to), reduction);
}
pub fn reset(&mut self) {
self.current_cycle = 0;
self.issued_this_cycle = 0;
self.scoreboard.clear();
self.reg_ready.clear();
self.issued_nodes.clear();
for (_res, cycles) in self.resource_free_cycles.iter_mut() {
cycles.fill(0);
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86SchedStrategyKind {
List,
Source,
Hybrid,
ILP,
VLIW,
Trace,
Modulo,
}
#[derive(Debug, Clone)]
pub struct X86SchedStrategy {
pub kind: X86SchedStrategyKind,
pub schedule: Vec<SchedNodeId>,
pub cycle_schedule: BTreeMap<SchedCycle, Vec<SchedNodeId>>,
pub total_cycles: SchedCycle,
pub priority_kind: X86SchedPriorityKind,
}
impl X86SchedStrategy {
pub fn new(kind: X86SchedStrategyKind, priority_kind: X86SchedPriorityKind) -> Self {
Self {
kind,
schedule: Vec::new(),
cycle_schedule: BTreeMap::new(),
total_cycles: 0,
priority_kind,
}
}
pub fn schedule(&mut self, dag: &X86SchedDAG, model: Option<&SchedModel>) -> Vec<SchedNodeId> {
match self.kind {
X86SchedStrategyKind::List => self.list_schedule(dag, model),
X86SchedStrategyKind::Source => self.source_schedule(dag, model),
X86SchedStrategyKind::Hybrid => self.hybrid_schedule(dag, model),
X86SchedStrategyKind::ILP => self.ilp_schedule(dag, model),
X86SchedStrategyKind::VLIW => self.vliw_schedule(dag, model),
X86SchedStrategyKind::Trace => self.trace_schedule(dag, model),
X86SchedStrategyKind::Modulo => self.modulo_schedule(dag, model),
}
}
fn list_schedule(&mut self, dag: &X86SchedDAG, model: Option<&SchedModel>) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let priority = X86SchedPriority::compute(dag, self.priority_kind);
let mut unscheduled_preds: Vec<usize> =
dag.nodes.iter().map(|nd| nd.unscheduled_preds).collect();
let mut ready: Vec<SchedNodeId> = (0..n).filter(|&i| unscheduled_preds[i] == 0).collect();
let mut scheduled = Vec::with_capacity(n);
let mut scheduled_set = HashSet::new();
let issue_width = model.map(|m| m.machine.issue_width).unwrap_or(4);
let mut hazard = X86SchedHazardRecognizer::new(issue_width);
if let Some(m) = model {
let counts: Vec<u32> = vec![1; m.resources.len()];
hazard.init_resources(&m.resources, &counts);
}
while !ready.is_empty() {
ready.sort_by(|&a, &b| priority.compare(a, b));
let mut selected: Option<SchedNodeId> = None;
for &r in &ready {
if scheduled_set.contains(&r) {
continue;
}
if hazard.check_hazard(&dag.nodes[r], dag, model).is_none() {
selected = Some(r);
break;
}
}
match selected {
Some(idx) => {
ready.retain(|&r| r != idx);
scheduled.push(idx);
scheduled_set.insert(idx);
hazard.issue_node(&dag.nodes[idx], model);
self.cycle_schedule
.entry(hazard.current_cycle)
.or_default()
.push(idx);
for &s in &dag.nodes[idx].succs {
if s < n && unscheduled_preds[s] > 0 {
unscheduled_preds[s] -= 1;
if unscheduled_preds[s] == 0 {
ready.push(s);
}
}
}
}
None => {
hazard.advance_cycle();
}
}
}
self.total_cycles = hazard.current_cycle;
self.schedule = scheduled.clone();
scheduled
}
fn source_schedule(
&mut self,
dag: &X86SchedDAG,
model: Option<&SchedModel>,
) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let priority = X86SchedPriority::compute(dag, self.priority_kind);
let mut unscheduled_preds: Vec<usize> =
dag.nodes.iter().map(|nd| nd.unscheduled_preds).collect();
let mut ready: Vec<SchedNodeId> = (0..n).filter(|&i| unscheduled_preds[i] == 0).collect();
let mut scheduled = Vec::with_capacity(n);
let mut scheduled_set = HashSet::new();
let issue_width = model.map(|m| m.machine.issue_width).unwrap_or(4);
let mut hazard = X86SchedHazardRecognizer::new(issue_width);
if let Some(m) = model {
let counts: Vec<u32> = vec![1; m.resources.len()];
hazard.init_resources(&m.resources, &counts);
}
let mut node_cycle: Vec<SchedCycle> = vec![0; n];
while !ready.is_empty() {
ready.sort_by(|&a, &b| {
let ca = node_cycle[a];
let cb = node_cycle[b];
ca.cmp(&cb).then_with(|| priority.compare(a, b))
});
let mut selected: Option<SchedNodeId> = None;
for &r in &ready {
if scheduled_set.contains(&r) {
continue;
}
while hazard.current_cycle < node_cycle[r] {
hazard.advance_cycle();
}
if hazard.check_hazard(&dag.nodes[r], dag, model).is_none() {
selected = Some(r);
break;
}
}
match selected {
Some(idx) => {
ready.retain(|&r| r != idx);
scheduled.push(idx);
scheduled_set.insert(idx);
let sched_cycle = hazard.current_cycle;
hazard.issue_node(&dag.nodes[idx], model);
self.cycle_schedule
.entry(sched_cycle)
.or_default()
.push(idx);
for &s in &dag.nodes[idx].succs {
if s < n && unscheduled_preds[s] > 0 {
unscheduled_preds[s] -= 1;
let candidate = sched_cycle + dag.nodes[idx].latency as u64;
if candidate > node_cycle[s] {
node_cycle[s] = candidate;
}
if unscheduled_preds[s] == 0 {
ready.push(s);
}
}
}
}
None => {
hazard.advance_cycle();
}
}
}
self.total_cycles = hazard.current_cycle;
self.schedule = scheduled.clone();
scheduled
}
fn hybrid_schedule(
&mut self,
dag: &X86SchedDAG,
model: Option<&SchedModel>,
) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let mut fwd = X86SchedStrategy::new(X86SchedStrategyKind::List, self.priority_kind);
let fwd_sched = fwd.schedule(dag, model);
let fwd_cycles = fwd.total_cycles;
let rev_dag = self.build_reversed_dag(dag);
let mut bwd = X86SchedStrategy::new(X86SchedStrategyKind::List, self.priority_kind);
let bwd_sched_rev = bwd.schedule(&rev_dag, model);
let bwd_cycles = bwd.total_cycles;
let mut bwd_sched: Vec<SchedNodeId> = bwd_sched_rev.into_iter().rev().collect();
if rev_dag.node_count != n {
self.schedule = fwd_sched.clone();
self.total_cycles = fwd_cycles;
self.cycle_schedule = fwd.cycle_schedule;
return fwd_sched;
}
if fwd_cycles <= bwd_cycles {
self.schedule = fwd_sched.clone();
self.total_cycles = fwd_cycles;
self.cycle_schedule = fwd.cycle_schedule;
fwd_sched
} else {
self.schedule = bwd_sched.clone();
self.total_cycles = bwd_cycles;
self.cycle_schedule = bwd.cycle_schedule;
bwd_sched
}
}
fn build_reversed_dag(&self, dag: &X86SchedDAG) -> X86SchedDAG {
let n = dag.node_count;
let mut rev = X86SchedDAG::new();
rev.node_count = n;
rev.nodes = dag.nodes.clone();
rev.succ_edges = vec![Vec::new(); n];
rev.pred_edges = vec![Vec::new(); n];
for edge in &dag.edges {
rev.edges.push(X86SchedEdge {
from: edge.to,
to: edge.from,
kind: edge.kind,
reg: edge.reg,
min_latency: edge.min_latency,
});
rev.nodes[edge.to].succs.push(edge.from);
rev.nodes[edge.from].preds.push(edge.to);
rev.succ_edges[edge.to].push(rev.edges.len() - 1);
rev.pred_edges[edge.from].push(rev.edges.len() - 1);
}
for node in &mut rev.nodes {
node.unscheduled_preds = node.preds.len();
node.height = 0;
node.depth = 0;
}
rev.compute_heights_and_depths();
rev.compute_asap_alap();
rev.identify_critical_path();
rev
}
fn ilp_schedule(&mut self, dag: &X86SchedDAG, model: Option<&SchedModel>) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let priority = X86SchedPriority::compute(dag, self.priority_kind);
let mut unscheduled_preds: Vec<usize> =
dag.nodes.iter().map(|nd| nd.unscheduled_preds).collect();
let mut scheduled = Vec::with_capacity(n);
let mut scheduled_set = HashSet::new();
let issue_width = model.map(|m| m.machine.issue_width).unwrap_or(4);
let mut hazard = X86SchedHazardRecognizer::new(issue_width);
if let Some(m) = model {
let counts: Vec<u32> = vec![1; m.resources.len()];
hazard.init_resources(&m.resources, &counts);
}
loop {
let mut ready: Vec<SchedNodeId> = (0..n)
.filter(|&i| unscheduled_preds[i] == 0 && !scheduled_set.contains(&i))
.collect();
if ready.is_empty() {
break;
}
ready.sort_by(|&a, &b| priority.compare(a, b));
let mut issued_this_cycle = 0u32;
for idx in ready {
if issued_this_cycle >= issue_width {
break;
}
if scheduled_set.contains(&idx) {
continue;
}
if hazard.check_hazard(&dag.nodes[idx], dag, model).is_none() {
hazard.issue_node(&dag.nodes[idx], model);
scheduled.push(idx);
scheduled_set.insert(idx);
self.cycle_schedule
.entry(hazard.current_cycle)
.or_default()
.push(idx);
issued_this_cycle += 1;
for &s in &dag.nodes[idx].succs {
if s < n && unscheduled_preds[s] > 0 {
unscheduled_preds[s] -= 1;
}
}
}
}
hazard.advance_cycle();
}
self.total_cycles = hazard.current_cycle;
self.schedule = scheduled.clone();
scheduled
}
fn vliw_schedule(&mut self, dag: &X86SchedDAG, model: Option<&SchedModel>) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let bundle_size: usize = model
.and_then(|m| {
if m.machine.out_of_order {
None
} else {
Some(m.machine.issue_width as usize)
}
})
.unwrap_or(2);
let priority = X86SchedPriority::compute(dag, X86SchedPriorityKind::CriticalPath);
let mut unscheduled_preds: Vec<usize> =
dag.nodes.iter().map(|nd| nd.unscheduled_preds).collect();
let mut scheduled = Vec::with_capacity(n);
let mut scheduled_set = HashSet::new();
let mut cycle: SchedCycle = 0;
loop {
let mut ready: Vec<SchedNodeId> = (0..n)
.filter(|&i| unscheduled_preds[i] == 0 && !scheduled_set.contains(&i))
.collect();
if ready.is_empty() {
break;
}
ready.sort_by(|&a, &b| priority.compare(a, b));
let mut bundle: Vec<SchedNodeId> = Vec::new();
let mut bundle_resources: HashSet<ProcResource> = HashSet::new();
for idx in ready {
if bundle.len() >= bundle_size {
break;
}
let mut conflict = false;
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == dag.nodes[idx].opcode {
for wr in &itin.write_resources {
if bundle_resources.contains(&wr.resource) {
conflict = true;
break;
}
}
break;
}
}
}
if !conflict {
bundle.push(idx);
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == dag.nodes[idx].opcode {
for wr in &itin.write_resources {
bundle_resources.insert(wr.resource);
}
break;
}
}
}
}
}
for &idx in &bundle {
scheduled.push(idx);
scheduled_set.insert(idx);
self.cycle_schedule.entry(cycle).or_default().push(idx);
for &s in &dag.nodes[idx].succs {
if s < n && unscheduled_preds[s] > 0 {
unscheduled_preds[s] -= 1;
}
}
}
cycle += 1;
}
self.total_cycles = cycle;
self.schedule = scheduled.clone();
scheduled
}
fn trace_schedule(
&mut self,
dag: &X86SchedDAG,
model: Option<&SchedModel>,
) -> Vec<SchedNodeId> {
let mut sched = self.list_schedule(dag, model);
self.reorder_branches_earlier(dag, &mut sched);
self.schedule = sched.clone();
sched
}
fn reorder_branches_earlier(&self, dag: &X86SchedDAG, schedule: &mut Vec<SchedNodeId>) {
let n = schedule.len();
let mut pos_map: Vec<usize> = vec![0; dag.node_count];
for (pos, &nid) in schedule.iter().enumerate() {
pos_map[nid] = pos;
}
for i in 0..n {
let nid = schedule[i];
if dag.nodes[nid].is_branch {
let mut earliest = i;
for &p in &dag.nodes[nid].preds {
if pos_map[p] < earliest {
earliest = pos_map[p];
}
}
if earliest + 1 < i {
let moved = schedule.remove(i);
schedule.insert(earliest + 1, moved);
for (pos, &nid2) in schedule.iter().enumerate() {
pos_map[nid2] = pos;
}
}
}
}
}
fn modulo_schedule(
&mut self,
dag: &X86SchedDAG,
model: Option<&SchedModel>,
) -> Vec<SchedNodeId> {
let n = dag.node_count;
if n == 0 {
return Vec::new();
}
let res_mii = self.compute_res_mii(dag, model);
let rec_mii = self.compute_rec_mii(dag);
let min_ii = res_mii.max(rec_mii).max(1);
let priority = X86SchedPriority::compute(dag, self.priority_kind);
let issue_width = model.map(|m| m.machine.issue_width).unwrap_or(4);
let mut ii = min_ii;
let max_ii = min_ii * 3;
while ii <= max_ii {
let result = self.try_modulo_schedule(dag, ii, &priority, issue_width, model);
if let Some(sched) = result {
self.total_cycles = ii;
self.schedule = sched.clone();
return sched;
}
ii += 1;
}
log::warn!(
"Modulo scheduling failed for II={}..{}; falling back to list scheduling",
min_ii,
max_ii
);
let fallback = self.list_schedule(dag, model);
self.schedule = fallback.clone();
fallback
}
fn compute_res_mii(&self, dag: &X86SchedDAG, model: Option<&SchedModel>) -> SchedCycle {
let mut res_usage: HashMap<ProcResource, u32> = HashMap::new();
let mut res_counts: HashMap<ProcResource, u32> = HashMap::new();
if let Some(m) = model {
for r in &m.resources {
res_counts.insert(*r, 1); }
for node in &dag.nodes {
for itin in &m.itineraries {
if itin.opcode == node.opcode {
for wr in &itin.write_resources {
*res_usage.entry(wr.resource).or_default() += wr.cycles;
}
break;
}
}
}
}
let mut res_mii: SchedCycle = 0;
for (res, usage) in &res_usage {
let count = res_counts.get(res).copied().unwrap_or(1) as u64;
let mii = (*usage as u64 + count - 1) / count;
if mii > res_mii {
res_mii = mii;
}
}
res_mii.max(1)
}
fn compute_rec_mii(&self, dag: &X86SchedDAG) -> SchedCycle {
dag.critical_path_length as u64
}
fn try_modulo_schedule(
&self,
dag: &X86SchedDAG,
ii: SchedCycle,
priority: &X86SchedPriority,
issue_width: u32,
model: Option<&SchedModel>,
) -> Option<Vec<SchedNodeId>> {
let n = dag.node_count;
let mut schedule: Vec<Option<(SchedCycle, u32)>> = vec![None; n]; let mut scheduled = 0usize;
let mut resource_table: HashMap<SchedCycle, Vec<ProcResource>> = HashMap::new();
let mut order: Vec<SchedNodeId> = (0..n).collect();
order.sort_by(|&a, &b| priority.compare(a, b));
for &nid in &order {
let node = &dag.nodes[nid];
let mut earliest: SchedCycle = 0;
for &p in &node.preds {
if let Some((p_cycle, _)) = schedule[p] {
let min_dist = dag.nodes[p].latency as i64;
let candidate = p_cycle as i64 + min_dist;
if candidate > earliest as i64 {
earliest = candidate as SchedCycle;
}
}
}
let mut placed = false;
for offset in 0..ii {
let cycle = earliest + offset;
let mod_cycle = cycle % ii;
let resources_used = self.get_node_resources(node, model);
let slot = resource_table.entry(mod_cycle).or_default().len() as u32;
if slot < issue_width {
let mut conflict = false;
for res in &resources_used {
if resource_table.entry(mod_cycle).or_default().contains(res) {
conflict = true;
break;
}
}
if !conflict {
schedule[nid] = Some((cycle, slot));
for res in resources_used {
resource_table.entry(mod_cycle).or_default().push(res);
}
placed = true;
scheduled += 1;
break;
}
}
}
if !placed {
return None; }
}
let mut result: Vec<(SchedNodeId, SchedCycle)> = schedule
.iter()
.enumerate()
.filter_map(|(nid, entry)| entry.map(|(cycle, _)| (nid, cycle)))
.collect();
result.sort_by_key(|&(_, cycle)| cycle);
Some(result.into_iter().map(|(nid, _)| nid).collect())
}
fn get_node_resources(
&self,
node: &X86SchedNode,
model: Option<&SchedModel>,
) -> Vec<ProcResource> {
if let Some(m) = model {
for itin in &m.itineraries {
if itin.opcode == node.opcode {
return itin.write_resources.iter().map(|wr| wr.resource).collect();
}
}
}
Vec::new()
}
}
#[derive(Debug, Clone)]
pub struct X86ExtendedSchedModel {
pub base: SchedModel,
pub kind: X86SchedModelKind,
pub resource_counts: HashMap<ProcResource, u32>,
pub port_pipeline_map: HashMap<ProcResource, Vec<String>>,
pub war_latency: u32,
pub waw_latency: u32,
pub load_use_latency: u32,
pub unified_reservation_station: bool,
pub supports_macro_fusion: bool,
pub supports_micro_fusion: bool,
pub icache_line_size: u32,
pub uop_cache_size: Option<u32>,
pub decoded_stream_buffer_size: u32,
pub btb_entries: u32,
}
impl X86ExtendedSchedModel {
pub fn new(base: SchedModel, kind: X86SchedModelKind) -> Self {
let mut resource_counts = HashMap::new();
for r in &base.resources {
resource_counts.insert(*r, 1);
}
Self {
base,
kind,
resource_counts,
port_pipeline_map: HashMap::new(),
war_latency: 0,
waw_latency: 0,
load_use_latency: 3,
unified_reservation_station: true,
supports_macro_fusion: false,
supports_micro_fusion: false,
icache_line_size: 64,
uop_cache_size: None,
decoded_stream_buffer_size: 20,
btb_entries: 4096,
}
}
pub fn with_resource_counts(mut self, counts: &[(ProcResource, u32)]) -> Self {
for &(res, count) in counts {
self.resource_counts.insert(res, count);
}
self
}
pub fn skylake_client() -> Self {
use crate::x86::x86_schedule_model::skylake_client_model;
let mut model = Self::new(skylake_client_model(), X86SchedModelKind::SkylakeClient);
model.resource_counts = [
(ProcResource::Port0, 1),
(ProcResource::Port1, 1),
(ProcResource::Port2, 1),
(ProcResource::Port3, 1),
(ProcResource::Port4, 1),
(ProcResource::Port5, 1),
(ProcResource::Port6, 1),
(ProcResource::Port7, 1),
]
.iter()
.copied()
.collect();
model.war_latency = 0;
model.waw_latency = 0;
model.load_use_latency = 4;
model.unified_reservation_station = true;
model.supports_macro_fusion = true;
model.supports_micro_fusion = true;
model.uop_cache_size = Some(1536); model.decoded_stream_buffer_size = 64;
model
}
pub fn ice_lake_client() -> Self {
use crate::x86::x86_schedule_model::ice_lake_model;
let mut model = Self::new(ice_lake_model(), X86SchedModelKind::IceLakeClient);
model.resource_counts = [
(ProcResource::Port0, 1),
(ProcResource::Port1, 1),
(ProcResource::Port2, 1),
(ProcResource::Port3, 1),
(ProcResource::Port4, 1),
(ProcResource::Port5, 1),
(ProcResource::Port6, 1),
(ProcResource::Port7, 1),
(ProcResource::Port8, 1),
(ProcResource::Port9, 1),
]
.iter()
.copied()
.collect();
model.load_use_latency = 5;
model.supports_macro_fusion = true;
model.supports_micro_fusion = true;
model.uop_cache_size = Some(2304); model.decoded_stream_buffer_size = 70;
model
}
pub fn alder_lake_p_core() -> Self {
use crate::x86::x86_schedule_model::alder_lake_pcore_model;
let mut model = Self::new(alder_lake_pcore_model(), X86SchedModelKind::AlderLakeP);
model.resource_counts = [
(ProcResource::Port0, 1),
(ProcResource::Port1, 1),
(ProcResource::Port2, 1),
(ProcResource::Port3, 1),
(ProcResource::Port4, 1),
(ProcResource::Port5, 1),
(ProcResource::Port6, 1),
(ProcResource::Port7, 1),
(ProcResource::Port8, 1),
(ProcResource::Port9, 1),
(ProcResource::Port10, 1),
(ProcResource::Port11, 1),
]
.iter()
.copied()
.collect();
model.load_use_latency = 5;
model.supports_macro_fusion = true;
model.supports_micro_fusion = true;
model.uop_cache_size = Some(4096); model.decoded_stream_buffer_size = 144;
model
}
pub fn zen4() -> Self {
use crate::x86::x86_schedule_model::zen4_model;
let mut model = Self::new(zen4_model(), X86SchedModelKind::Zen4);
model.resource_counts = [
(ProcResource::ALU0, 1),
(ProcResource::ALU1, 1),
(ProcResource::ALU2, 1),
(ProcResource::ALU3, 1),
(ProcResource::AGU0, 1),
(ProcResource::AGU1, 1),
(ProcResource::AGU2, 1),
(ProcResource::AGU3, 1),
(ProcResource::FPU0, 1),
(ProcResource::FPU1, 1),
(ProcResource::FPU2, 1),
(ProcResource::FPU3, 1),
(ProcResource::BranchUnit, 1),
]
.iter()
.copied()
.collect();
model.load_use_latency = 4;
model.unified_reservation_station = false; model.supports_macro_fusion = true;
model.supports_micro_fusion = false; model.uop_cache_size = Some(6750); model
}
pub fn zen5() -> Self {
use crate::x86::x86_schedule_model::zen5_model;
let mut model = Self::new(zen5_model(), X86SchedModelKind::Zen5);
model.resource_counts = [
(ProcResource::ALU0, 1),
(ProcResource::ALU1, 1),
(ProcResource::ALU2, 1),
(ProcResource::ALU3, 1),
(ProcResource::ALU4, 1),
(ProcResource::ALU5, 1),
(ProcResource::AGU0, 1),
(ProcResource::AGU1, 1),
(ProcResource::AGU2, 1),
(ProcResource::AGU3, 1),
(ProcResource::BranchUnit, 1),
]
.iter()
.copied()
.collect();
model.load_use_latency = 4;
model.unified_reservation_station = false;
model.supports_macro_fusion = true;
model.uop_cache_size = Some(6750);
model
}
pub fn get_resource_count(&self, res: ProcResource) -> u32 {
self.resource_counts.get(&res).copied().unwrap_or(1)
}
pub fn load_latency(&self) -> u32 {
self.base.machine.load_latency
}
pub fn issue_width(&self) -> u32 {
self.base.machine.issue_width
}
pub fn create_hazard_recognizer(&self) -> X86SchedHazardRecognizer {
let mut hr = X86SchedHazardRecognizer::new(self.issue_width());
hr.set_load_use_penalty(self.load_use_latency);
let counts: Vec<u32> = self
.base
.resources
.iter()
.map(|r| self.get_resource_count(*r))
.collect();
hr.init_resources(&self.base.resources, &counts);
hr
}
}
#[derive(Debug, Clone)]
pub struct X86MacroFusionScheduling {
pub enabled: bool,
pub detected_pairs: Vec<(SchedNodeId, SchedNodeId)>,
pub fused_pairs: Vec<(SchedNodeId, SchedNodeId)>,
fusion_jcc_opcodes: HashSet<u32>,
fusion_cmp_test_opcodes: HashSet<u32>,
}
impl X86MacroFusionScheduling {
pub fn new(enabled: bool) -> Self {
let mut fusion_jcc = HashSet::new();
for op in 30..=39u32 {
fusion_jcc.insert(op);
}
fusion_jcc.insert(70);
fusion_jcc.insert(71);
fusion_jcc.insert(72);
let mut fusion_defs = HashSet::new();
fusion_defs.insert(9); fusion_defs.insert(10); fusion_defs.insert(6); fusion_defs.insert(7); fusion_defs.insert(8); fusion_defs.insert(60); fusion_defs.insert(61);
Self {
enabled,
detected_pairs: Vec::new(),
fused_pairs: Vec::new(),
fusion_jcc_opcodes: fusion_jcc,
fusion_cmp_test_opcodes: fusion_defs,
}
}
pub fn detect_pairs(&mut self, dag: &X86SchedDAG, instructions: &[MachineInstr]) {
if !self.enabled {
return;
}
self.detected_pairs.clear();
let n = dag.node_count;
for i in 0..n {
let node_a = &dag.nodes[i];
if !self.fusion_cmp_test_opcodes.contains(&node_a.opcode) {
continue;
}
if !node_a.defines_flags {
continue;
}
for &s in &node_a.succs {
let node_b = &dag.nodes[s];
if node_b.is_branch
&& self.fusion_jcc_opcodes.contains(&node_b.opcode)
&& node_b.uses_flags
{
let has_glue = dag
.edges
.iter()
.any(|e| e.from == i && e.to == s && matches!(e.kind, X86EdgeKind::Glue));
if has_glue {
let mut intermediate_defines_flags = false;
for k in (i + 1)..s {
if k < n && dag.nodes[k].defines_flags {
intermediate_defines_flags = true;
break;
}
}
if !intermediate_defines_flags {
self.detected_pairs.push((i, s));
}
}
}
}
}
}
pub fn enforce_adjacency(&mut self, schedule: &mut Vec<SchedNodeId>, dag: &X86SchedDAG) {
if !self.enabled || self.detected_pairs.is_empty() {
return;
}
self.fused_pairs.clear();
let n = schedule.len();
let mut pos_map: Vec<usize> = vec![0; dag.node_count];
for (pos, &nid) in schedule.iter().enumerate() {
pos_map[nid] = pos;
}
let pairs = self.detected_pairs.clone();
for (a, b) in &pairs {
let pos_a = pos_map[*a];
let pos_b = pos_map[*b];
if pos_b == pos_a + 1 {
self.fused_pairs.push((*a, *b));
continue;
}
if pos_b > pos_a + 1 {
let mut can_move = true;
for &p in &dag.nodes[*b].preds {
if p != *a && pos_map[p] > pos_a {
can_move = false;
break;
}
}
if can_move {
let moved = schedule.remove(pos_b);
let new_pos_b = if pos_a + 1 > schedule.len() {
schedule.len()
} else {
pos_a + 1
};
schedule.insert(new_pos_b, moved);
self.fused_pairs.push((*a, *b));
for (pos, &nid) in schedule.iter().enumerate() {
pos_map[nid] = pos;
}
continue;
}
}
if *a < *b && pos_a + 1 < pos_b {
let mut can_move = true;
for &s in &dag.nodes[*a].succs {
if s != *b && pos_map[s] < pos_b {
can_move = false;
break;
}
}
if can_move {
let moved = schedule.remove(pos_a);
let new_pos_a = if pos_b == 0 { 0 } else { pos_b - 1 };
schedule.insert(new_pos_a, moved);
self.fused_pairs.push((*a, *b));
for (pos, &nid) in schedule.iter().enumerate() {
pos_map[nid] = pos;
}
}
}
}
}
pub fn can_fuse(first_opcode: u32, second_opcode: u32, model: &X86ExtendedSchedModel) -> bool {
if !model.supports_macro_fusion {
return false;
}
let jcc_ops: HashSet<u32> = (30..=39).collect();
if !jcc_ops.contains(&second_opcode) {
return false;
}
match first_opcode {
9 | 10 => true, 6 | 7 | 8 => {
matches!(
model.kind,
X86SchedModelKind::SandyBridge
| X86SchedModelKind::IvyBridge
| X86SchedModelKind::Haswell
| X86SchedModelKind::Broadwell
| X86SchedModelKind::SkylakeClient
| X86SchedModelKind::IceLakeClient
| X86SchedModelKind::AlderLakeP
)
}
60 | 61 => {
matches!(
model.kind,
X86SchedModelKind::Goldmont | X86SchedModelKind::GoldmontPlus
)
}
_ => false,
}
}
}
#[derive(Debug, Clone)]
pub struct X86PreRAScheduler {
pub model: X86ExtendedSchedModel,
pub strategy: X86SchedStrategyKind,
pub priority: X86SchedPriorityKind,
pub cluster_loads: bool,
pub avoid_spills: bool,
pub max_load_use_distance: usize,
pub reordered_count: usize,
pub loads_clustered: usize,
pub moved_earlier: usize,
pub moved_later: usize,
}
impl X86PreRAScheduler {
pub fn new(model: X86ExtendedSchedModel) -> Self {
Self {
model,
strategy: X86SchedStrategyKind::Hybrid,
priority: X86SchedPriorityKind::RegPressure,
cluster_loads: true,
avoid_spills: true,
max_load_use_distance: 3,
reordered_count: 0,
loads_clustered: 0,
moved_earlier: 0,
moved_later: 0,
}
}
pub fn schedule_function(&mut self, mf: &mut MachineFunction) -> usize {
let mut total_reordered = 0usize;
let block_count = mf.blocks.len();
for bb_idx in 0..block_count {
let block = &mf.blocks[bb_idx];
if block.instructions.len() < 2 {
continue;
}
let dag = X86SchedDAG::build(&block.instructions, Some(&self.model.base), None, false);
if dag.node_count < 2 {
continue;
}
let mut strategy = X86SchedStrategy::new(self.strategy, self.priority);
let schedule = strategy.schedule(&dag, Some(&self.model.base));
let mut final_schedule = schedule;
if self.cluster_loads {
final_schedule = self.cluster_loads_with_uses(&final_schedule, &dag);
}
if self.avoid_spills {
final_schedule = self.reorder_for_spill_avoidance(&final_schedule, &dag);
}
if final_schedule.len() == block.instructions.len() {
let mut new_instrs = Vec::with_capacity(final_schedule.len());
let mut changed = 0usize;
let mut moved_earlier = 0usize;
let mut moved_later = 0usize;
for (new_pos, &old_idx) in final_schedule.iter().enumerate() {
if old_idx < mf.blocks[bb_idx].instructions.len() {
new_instrs.push(mf.blocks[bb_idx].instructions[old_idx].clone());
}
if old_idx != new_pos {
changed += 1;
if old_idx > new_pos {
moved_earlier += 1;
} else {
moved_later += 1;
}
}
}
mf.blocks[bb_idx].instructions = new_instrs;
self.reordered_count += changed;
self.moved_earlier += moved_earlier;
self.moved_later += moved_later;
total_reordered += changed;
}
}
total_reordered
}
fn cluster_loads_with_uses(
&mut self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
) -> Vec<SchedNodeId> {
let n = schedule.len();
if n == 0 {
return schedule.to_vec();
}
let mut result = schedule.to_vec();
let mut pos_map: Vec<usize> = vec![0; dag.node_count];
for (pos, &nid) in result.iter().enumerate() {
pos_map[nid] = pos;
}
let mut clustered = 0usize;
for i in 0..dag.node_count {
let node = &dag.nodes[i];
if !node.may_load {
continue;
}
let mut first_use: Option<SchedNodeId> = None;
let mut min_pos = usize::MAX;
for &s in &node.succs {
if pos_map[s] < min_pos && pos_map[s] > pos_map[i] {
min_pos = pos_map[s];
first_use = Some(s);
}
}
if let Some(use_id) = first_use {
let distance = pos_map[use_id] - pos_map[i];
if distance > self.max_load_use_distance {
let load_pos = pos_map[i];
let use_pos = pos_map[use_id];
let target_pos = use_pos.saturating_sub(self.max_load_use_distance);
if target_pos > load_pos {
let moved = result.remove(load_pos);
result.insert(target_pos, moved);
clustered += 1;
for (pos, &nid) in result.iter().enumerate() {
pos_map[nid] = pos;
}
}
}
}
}
self.loads_clustered = clustered;
result
}
fn reorder_for_spill_avoidance(
&self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
) -> Vec<SchedNodeId> {
let mut use_counts: HashMap<u64, usize> = HashMap::new();
for node in &dag.nodes {
for u in &node.uses {
*use_counts.entry(u.to_key()).or_default() += 1;
}
}
let mut last_use_nodes: HashSet<SchedNodeId> = HashSet::new();
let mut remaining_uses: HashMap<u64, usize> = use_counts.clone();
for &nid in schedule.iter() {
let node = &dag.nodes[nid];
for u in &node.uses {
let key = u.to_key();
if let Some(cnt) = remaining_uses.get_mut(&key) {
*cnt -= 1;
if *cnt == 0 {
last_use_nodes.insert(nid);
}
}
}
}
let mut result = schedule.to_vec();
let mut pos_map: Vec<usize> = vec![0; dag.node_count];
for (pos, &nid) in result.iter().enumerate() {
pos_map[nid] = pos;
}
for &nid in &last_use_nodes {
let pos = pos_map[nid];
if pos == 0 {
continue;
}
let mut earliest = 0usize;
for &p in &dag.nodes[nid].preds {
let pp = pos_map[p];
if pp >= earliest {
earliest = pp + 1;
}
}
if earliest < pos {
let moved = result.remove(pos);
result.insert(earliest, moved);
for (p, &nn) in result.iter().enumerate() {
pos_map[nn] = p;
}
}
}
result
}
pub fn live_register_count_at(
&self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
position: usize,
) -> usize {
let mut live: HashSet<u64> = HashSet::new();
for (p, &nid) in schedule.iter().enumerate() {
if p > position {
break;
}
let node = &dag.nodes[nid];
for d in &node.defs {
live.insert(d.to_key());
}
}
live.len()
}
}
#[derive(Debug, Clone)]
pub struct X86PostRAScheduler {
pub model: X86ExtendedSchedModel,
pub strategy: X86SchedStrategyKind,
pub macro_fusion: X86MacroFusionScheduling,
pub break_anti_deps: bool,
pub prepare_micro_fusion: bool,
pub insert_nops: bool,
pub nop_alignment: u32,
pub form_bundles: bool,
pub bundle_size: usize,
pub reordered_count: usize,
pub anti_deps_broken: usize,
pub macro_fusion_pairs_placed: usize,
pub nops_inserted: usize,
pub bundles_formed: usize,
}
impl X86PostRAScheduler {
pub fn new(model: X86ExtendedSchedModel) -> Self {
let bundle_size = if model.base.machine.out_of_order {
0 } else {
model.base.machine.issue_width as usize
};
Self {
model: model.clone(),
strategy: X86SchedStrategyKind::List,
macro_fusion: X86MacroFusionScheduling::new(model.supports_macro_fusion),
break_anti_deps: true,
prepare_micro_fusion: true,
insert_nops: true,
nop_alignment: 16,
form_bundles: !model.base.machine.out_of_order,
bundle_size,
reordered_count: 0,
anti_deps_broken: 0,
macro_fusion_pairs_placed: 0,
nops_inserted: 0,
bundles_formed: 0,
}
}
pub fn schedule_function(&mut self, mf: &mut MachineFunction) -> usize {
let mut total_reordered = 0usize;
let block_count = mf.blocks.len();
for bb_idx in 0..block_count {
let block = &mf.blocks[bb_idx];
if block.instructions.len() < 2 {
continue;
}
let dag = X86SchedDAG::build(&block.instructions, Some(&self.model.base), None, true);
if dag.node_count < 2 {
continue;
}
let mut working_dag = dag;
if self.break_anti_deps {
let broken = self.break_anti_dependences(&mut working_dag, &block.instructions);
self.anti_deps_broken += broken;
}
let mut strategy =
X86SchedStrategy::new(self.strategy, X86SchedPriorityKind::BalancedILP);
let mut schedule = strategy.schedule(&working_dag, Some(&self.model.base));
self.macro_fusion
.detect_pairs(&working_dag, &block.instructions);
self.macro_fusion
.enforce_adjacency(&mut schedule, &working_dag);
self.macro_fusion_pairs_placed += self.macro_fusion.fused_pairs.len();
if self.prepare_micro_fusion {
schedule = self.prepare_micro_op_fusion(&schedule, &working_dag);
}
if self.insert_nops {
schedule =
self.insert_nops_for_alignment(&schedule, &working_dag, &block.instructions);
}
if self.form_bundles && self.bundle_size > 0 {
schedule = self.form_instruction_bundles(&schedule, &working_dag);
}
if schedule.len() >= block.instructions.len() {
let mut new_instrs = Vec::with_capacity(schedule.len());
let mut changed = 0usize;
for (new_pos, &old_idx) in schedule.iter().enumerate() {
if old_idx < block.instructions.len() {
new_instrs.push(block.instructions[old_idx].clone());
} else {
new_instrs.push(MachineInstr::new(0)); self.nops_inserted += 1;
}
if old_idx < block.instructions.len() && old_idx != new_pos {
changed += 1;
}
}
mf.blocks[bb_idx].instructions = new_instrs;
self.reordered_count += changed;
total_reordered += changed;
}
}
total_reordered
}
fn break_anti_dependences(
&mut self,
dag: &mut X86SchedDAG,
_instructions: &[MachineInstr],
) -> usize {
let mut broken = 0usize;
let anti_edges: Vec<usize> = dag
.edges
.iter()
.enumerate()
.filter(|(_, e)| e.kind == X86EdgeKind::Anti)
.map(|(i, _)| i)
.collect();
for ei in &anti_edges {
let edge = &dag.edges[*ei];
if self.model.base.machine.out_of_order {
dag.edges[*ei].min_latency = 0;
broken += 1;
}
}
broken
}
fn prepare_micro_op_fusion(
&self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
) -> Vec<SchedNodeId> {
let mut result = schedule.to_vec();
let mut pos_map: Vec<usize> = vec![0; dag.node_count];
for (pos, &nid) in result.iter().enumerate() {
pos_map[nid] = pos;
}
for i in 0..dag.node_count {
if dag.nodes[i].may_load {
for &s in &dag.nodes[i].succs {
if !dag.nodes[s].may_load
&& !dag.nodes[s].may_store
&& !dag.nodes[s].is_branch
&& pos_map[s] == pos_map[i] + 2
{
continue;
}
if pos_map[s] > pos_map[i] + 1 {
let s_pos = pos_map[s];
let target = pos_map[i] + 1;
if target < s_pos {
let moved = result.remove(s_pos);
let insert_pos = target.min(result.len());
result.insert(insert_pos, moved);
for (p, &nid) in result.iter().enumerate() {
pos_map[nid] = p;
}
}
}
}
}
}
result
}
fn insert_nops_for_alignment(
&mut self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
instructions: &[MachineInstr],
) -> Vec<SchedNodeId> {
let mut result = schedule.to_vec();
let mut byte_offset = 0usize;
for i in 0..result.len() {
let nid = result[i];
if nid < dag.node_count {
let node = &dag.nodes[nid];
if node.is_branch && byte_offset % self.nop_alignment as usize != 0 {
let nop_id = dag.node_count + self.nops_inserted;
result.insert(i, nop_id);
self.nops_inserted += 1;
byte_offset += 1; }
let instr_size = if nid < instructions.len() {
let op_count = instructions[nid].operands.len();
1 + op_count
} else {
1
};
byte_offset += instr_size;
}
}
result
}
fn form_instruction_bundles(
&mut self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
) -> Vec<SchedNodeId> {
if self.bundle_size == 0 {
return schedule.to_vec();
}
let mut result: Vec<SchedNodeId> = Vec::with_capacity(schedule.len());
let mut bundle_count = 0usize;
let mut i = 0usize;
while i < schedule.len() {
let mut bundle: Vec<SchedNodeId> = Vec::new();
let mut resources_in_bundle: HashSet<ProcResource> = HashSet::new();
while bundle.len() < self.bundle_size && i < schedule.len() {
let nid = schedule[i];
if nid >= dag.node_count {
bundle.push(nid);
i += 1;
continue;
}
let node = &dag.nodes[nid];
if node.is_branch || node.is_call {
if !bundle.is_empty() {
break; }
bundle.push(nid);
i += 1;
break;
}
let node_resources = self.get_node_resources_for_bundle(node);
let mut conflict = false;
for res in &node_resources {
if resources_in_bundle.contains(res) {
conflict = true;
break;
}
}
if conflict && !bundle.is_empty() {
break; }
let mut has_dep_in_bundle = false;
for &b in &bundle {
if b < dag.node_count && dag.nodes[nid].preds.contains(&b) {
has_dep_in_bundle = true;
break;
}
}
if has_dep_in_bundle && !bundle.is_empty() {
break;
}
bundle.push(nid);
for res in node_resources {
resources_in_bundle.insert(res);
}
i += 1;
}
result.extend(&bundle);
bundle_count += 1;
}
self.bundles_formed = bundle_count;
result
}
fn get_node_resources_for_bundle(&self, node: &X86SchedNode) -> Vec<ProcResource> {
for itin in &self.model.base.itineraries {
if itin.opcode == node.opcode {
return itin.write_resources.iter().map(|wr| wr.resource).collect();
}
}
vec![ProcResource::Port0]
}
}
#[derive(Debug, Clone)]
pub struct X86SchedulerFull {
pub model: X86ExtendedSchedModel,
pub pre_ra: X86PreRAScheduler,
pub post_ra: X86PostRAScheduler,
pub enable_pre_ra: bool,
pub enable_post_ra: bool,
pub total_reordered: usize,
pub verbose: bool,
}
impl X86SchedulerFull {
pub fn for_cpu(cpu_name: &str) -> Self {
let model = match cpu_name.to_lowercase().as_str() {
"skylake" | "skylake_client" | "skl" => X86ExtendedSchedModel::skylake_client(),
"ice_lake" | "icelake" | "icl" => X86ExtendedSchedModel::ice_lake_client(),
"alder_lake" | "alderlake" | "adl" | "golden_cove" => {
X86ExtendedSchedModel::alder_lake_p_core()
}
"zen4" | "znver4" => X86ExtendedSchedModel::zen4(),
"zen5" | "znver5" => X86ExtendedSchedModel::zen5(),
_ => {
log::warn!(
"Unknown CPU model '{}', defaulting to Skylake Client scheduling model",
cpu_name
);
X86ExtendedSchedModel::skylake_client()
}
};
let pre_ra = X86PreRAScheduler::new(model.clone());
let post_ra = X86PostRAScheduler::new(model.clone());
Self {
model,
pre_ra,
post_ra,
enable_pre_ra: true,
enable_post_ra: true,
total_reordered: 0,
verbose: false,
}
}
pub fn with_model(model: X86ExtendedSchedModel) -> Self {
let pre_ra = X86PreRAScheduler::new(model.clone());
let post_ra = X86PostRAScheduler::new(model.clone());
Self {
model,
pre_ra,
post_ra,
enable_pre_ra: true,
enable_post_ra: true,
total_reordered: 0,
verbose: false,
}
}
pub fn run_pre_ra(&mut self, mf: &mut MachineFunction) -> usize {
if !self.enable_pre_ra {
return 0;
}
let count = self.pre_ra.schedule_function(mf);
self.total_reordered += count;
if self.verbose {
log::info!(
"Pre-RA scheduling: {} instructions reordered, {} loads clustered",
self.pre_ra.reordered_count,
self.pre_ra.loads_clustered,
);
}
count
}
pub fn run_post_ra(&mut self, mf: &mut MachineFunction) -> usize {
if !self.enable_post_ra {
return 0;
}
let count = self.post_ra.schedule_function(mf);
self.total_reordered += count;
if self.verbose {
log::info!(
"Post-RA scheduling: {} instructions reordered, {} anti-deps broken, {} macro-fusion pairs, {} NOPs inserted, {} bundles formed",
self.post_ra.reordered_count,
self.post_ra.anti_deps_broken,
self.post_ra.macro_fusion_pairs_placed,
self.post_ra.nops_inserted,
self.post_ra.bundles_formed,
);
}
count
}
pub fn run_full_pipeline(&mut self, mf: &mut MachineFunction) -> usize {
let pre = self.run_pre_ra(mf);
let post = self.run_post_ra(mf);
pre + post
}
pub fn build_dag(&self, instructions: &[MachineInstr], is_post_ra: bool) -> X86SchedDAG {
X86SchedDAG::build(instructions, Some(&self.model.base), None, is_post_ra)
}
pub fn run_algorithm(
&self,
dag: &X86SchedDAG,
strategy: X86SchedStrategyKind,
priority: X86SchedPriorityKind,
) -> Vec<SchedNodeId> {
let mut s = X86SchedStrategy::new(strategy, priority);
s.schedule(dag, Some(&self.model.base))
}
pub fn stats_summary(&self) -> String {
format!(
"X86SchedulerFull stats:\n\
- Model: {}\n\
- Issue width: {}\n\
- Total reordered: {}\n\
- Pre-RA reordered: {} (loads clustered: {})\n\
- Post-RA reordered: {} (anti-deps: {}, macro-fusion: {}, NOPs: {}, bundles: {})",
self.model.base.machine.name,
self.model.issue_width(),
self.total_reordered,
self.pre_ra.reordered_count,
self.pre_ra.loads_clustered,
self.post_ra.reordered_count,
self.post_ra.anti_deps_broken,
self.post_ra.macro_fusion_pairs_placed,
self.post_ra.nops_inserted,
self.post_ra.bundles_formed,
)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::MachineBasicBlock;
fn make_instr(opcode: u32, def: Option<u32>, uses: &[u32]) -> MachineInstr {
let mut mi = MachineInstr::new(opcode);
if let Some(d) = def {
mi.def = Some(d);
}
for &u in uses {
mi.push_reg(u);
}
mi
}
fn make_block(name: &str, instrs: Vec<MachineInstr>) -> MachineBasicBlock {
MachineBasicBlock {
id: 0,
name: name.into(),
instructions: instrs,
successors: Vec::new(),
predecessors: Vec::new(),
is_entry: false,
}
}
fn make_function(name: &str, blocks: Vec<MachineBasicBlock>) -> MachineFunction {
MachineFunction {
name: name.into(),
blocks,
virt_reg_counter: 100,
}
}
#[test]
fn test_dag_empty() {
let dag = X86SchedDAG::build(&[], None, None, false);
assert_eq!(dag.node_count, 0);
assert!(dag.nodes.is_empty());
assert!(dag.edges.is_empty());
}
#[test]
fn test_dag_single_node() {
let instrs = vec![make_instr(1, Some(0), &[1])]; let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.node_count, 1);
assert!(dag.nodes[0].succs.is_empty());
assert!(dag.nodes[0].preds.is_empty());
}
#[test]
fn test_dag_true_dependence() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.node_count, 2);
assert!(dag.nodes[1].preds.contains(&0));
assert!(dag.nodes[0].succs.contains(&1));
assert!(dag
.edges
.iter()
.any(|e| e.from == 0 && e.to == 1 && e.kind == X86EdgeKind::True));
}
#[test]
fn test_dag_output_dependence() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(7, Some(0), &[3, 4]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag.nodes[1].preds.contains(&0));
assert!(dag
.edges
.iter()
.any(|e| e.from == 0 && e.to == 1 && e.kind == X86EdgeKind::Output));
}
#[test]
fn test_dag_anti_dependence() {
let instrs = vec![
make_instr(1, Some(1), &[0, 2]),
make_instr(7, Some(0), &[3, 4]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag.nodes[1].preds.contains(&0));
assert!(dag
.edges
.iter()
.any(|e| e.from == 0 && e.to == 1 && e.kind == X86EdgeKind::Anti));
}
#[test]
fn test_dag_flags_glue() {
let instrs = vec![
make_instr(9, None, &[0, 1]), make_instr(30, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag
.edges
.iter()
.any(|e| e.from == 0 && e.to == 1 && e.kind == X86EdgeKind::Glue));
}
#[test]
fn test_dag_memory_ordering() {
let mut si = make_instr(100, None, &[0, 1]);
si.may_store = true;
let mut li = make_instr(2, Some(2), &[3]);
li.may_load = true;
let instrs = vec![si, li];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let has_mem_edge = dag.edges.iter().any(|e| {
e.from == 0
&& e.to == 1
&& (e.kind == X86EdgeKind::Memory || e.kind == X86EdgeKind::Chain)
});
let _ = has_mem_edge;
}
#[test]
fn test_dag_height_and_depth() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
make_instr(1, Some(5), &[3, 6]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.nodes[0].height, 3);
assert_eq!(dag.nodes[1].height, 2);
assert_eq!(dag.nodes[2].height, 1);
assert_eq!(dag.nodes[0].depth, 1);
assert_eq!(dag.nodes[1].depth, 2);
assert_eq!(dag.nodes[2].depth, 3);
}
#[test]
fn test_dag_critical_path() {
let mut i2 = make_instr(4, Some(5), &[3, 6]); let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
i2,
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag.critical_path_length >= 3);
assert!(!dag.critical_path_nodes.is_empty());
}
#[test]
fn test_priority_critical_path() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
make_instr(1, Some(5), &[3, 6]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::CriticalPath);
assert!(pri.get(0) >= pri.get(1));
assert!(pri.get(1) >= pri.get(2));
}
#[test]
fn test_priority_latency_weighted() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::LatencyWeighted);
assert!(pri.get(0) > 0);
assert!(pri.get(1) > 0);
}
#[test]
fn test_priority_reg_pressure() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]), make_instr(1, Some(5), &[3, 6]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::RegPressure);
for i in 0..3 {
assert!(pri.get(i) >= 0);
}
}
#[test]
fn test_priority_balanced_ilp() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
make_instr(1, Some(5), &[3, 6]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::BalancedILP);
for i in 0..3 {
assert!(pri.get(i) > 0);
}
}
#[test]
fn test_list_schedule_empty() {
let dag = X86SchedDAG::new();
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert!(sched.is_empty());
}
#[test]
fn test_list_schedule_linear() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
assert_eq!(sched, vec![0, 1, 2]);
}
#[test]
fn test_list_schedule_parallel() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
let mut sorted = sched.clone();
sorted.sort();
assert_eq!(sorted, vec![0, 1, 2]);
}
#[test]
fn test_source_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[0, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::Source,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
assert_eq!(sched[0], 0);
assert!(sched.contains(&1));
assert!(sched.contains(&2));
}
#[test]
fn test_hybrid_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::Hybrid,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
let pos0 = sched.iter().position(|&x| x == 0).unwrap();
let pos1 = sched.iter().position(|&x| x == 1).unwrap();
let pos2 = sched.iter().position(|&x| x == 2).unwrap();
assert!(pos0 < pos1);
assert!(pos1 < pos2);
}
#[test]
fn test_ilp_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
make_instr(1, Some(3), &[16, 17]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::ILP,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 4);
let mut sorted = sched.clone();
sorted.sort();
assert_eq!(sorted, vec![0, 1, 2, 3]);
}
#[test]
fn test_vliw_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::VLIW,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
let mut sorted = sched.clone();
sorted.sort();
assert_eq!(sorted, vec![0, 1, 2]);
}
#[test]
fn test_trace_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::Trace,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 3);
assert_eq!(sched[0], 0); }
#[test]
fn test_modulo_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::Modulo,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert!(!sched.is_empty());
let mut sorted = sched.clone();
sorted.sort();
assert_eq!(sorted, vec![0, 1, 2]);
}
#[test]
fn test_hazard_no_hazard_empty() {
let hr = X86SchedHazardRecognizer::new(4);
let dag = X86SchedDAG::new();
let node = X86SchedNode::new(0, 1);
assert!(hr.check_hazard(&node, &dag, None).is_none());
}
#[test]
fn test_hazard_issue_width() {
let mut hr = X86SchedHazardRecognizer::new(2);
let dag = X86SchedDAG::new();
let node = X86SchedNode::new(0, 1);
hr.issue_node(&node, None);
hr.issue_node(&node, None);
assert!(hr.check_hazard(&node, &dag, None).is_some());
hr.advance_cycle();
assert!(hr.check_hazard(&node, &dag, None).is_none());
}
#[test]
fn test_hazard_advance_cycle() {
let mut hr = X86SchedHazardRecognizer::new(4);
assert_eq!(hr.current_cycle, 0);
assert_eq!(hr.issued_this_cycle, 0);
hr.advance_cycle();
assert_eq!(hr.current_cycle, 1);
assert_eq!(hr.issued_this_cycle, 0);
}
#[test]
fn test_hazard_resource_tracking() {
let mut hr = X86SchedHazardRecognizer::new(4);
let resources = vec![ProcResource::Port0, ProcResource::Port1];
let counts = vec![1, 1];
hr.init_resources(&resources, &counts);
assert!(hr.resource_available(ProcResource::Port0));
assert!(hr.resource_available(ProcResource::Port1));
assert_eq!(hr.resource_available_count(ProcResource::Port0), 1);
}
#[test]
fn test_macro_fusion_detect_cmp_jcc() {
let instrs = vec![
make_instr(9, None, &[0, 1]), make_instr(30, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mf = X86MacroFusionScheduling::new(true);
mf.detect_pairs(&dag, &instrs);
assert!(!mf.detected_pairs.is_empty());
assert_eq!(mf.detected_pairs[0], (0, 1));
}
#[test]
fn test_macro_fusion_disabled() {
let instrs = vec![make_instr(9, None, &[0, 1]), make_instr(30, None, &[])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mf = X86MacroFusionScheduling::new(false);
mf.detect_pairs(&dag, &instrs);
assert!(mf.detected_pairs.is_empty());
}
#[test]
fn test_macro_fusion_enforce_adjacency() {
let instrs = vec![
make_instr(9, None, &[0, 1]), make_instr(1, Some(3), &[4, 5]), make_instr(30, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mf = X86MacroFusionScheduling::new(true);
mf.detect_pairs(&dag, &instrs);
assert_eq!(mf.detected_pairs.len(), 1);
let mut schedule: Vec<usize> = vec![0, 1, 2];
mf.enforce_adjacency(&mut schedule, &dag);
let pos0 = schedule.iter().position(|&x| x == 0).unwrap();
let pos2 = schedule.iter().position(|&x| x == 2).unwrap();
assert!((pos2 as isize - pos0 as isize).abs() == 1);
}
#[test]
fn test_macro_fusion_can_fuse() {
let model = X86ExtendedSchedModel::skylake_client();
assert!(X86MacroFusionScheduling::can_fuse(9, 30, &model)); assert!(X86MacroFusionScheduling::can_fuse(10, 31, &model)); assert!(X86MacroFusionScheduling::can_fuse(6, 32, &model)); }
#[test]
fn test_pre_ra_empty_function() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PreRAScheduler::new(model);
let mut mf = make_function("empty", vec![]);
let count = sched.schedule_function(&mut mf);
assert_eq!(count, 0);
}
#[test]
fn test_pre_ra_single_block() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PreRAScheduler::new(model.clone());
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let count = sched.schedule_function(&mut mf);
assert!(count <= 3);
assert_eq!(mf.blocks[0].instructions.len(), 3);
}
#[test]
fn test_pre_ra_load_clustering() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PreRAScheduler::new(model);
sched.cluster_loads = true;
sched.max_load_use_distance = 2;
let mut load = make_instr(2, Some(0), &[10]); load.may_load = true;
let instrs = vec![
load,
make_instr(1, Some(1), &[11, 12]),
make_instr(1, Some(2), &[13, 14]),
make_instr(1, Some(3), &[0, 15]), ];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
sched.schedule_function(&mut mf);
assert_eq!(mf.blocks[0].instructions.len(), 4);
}
#[test]
fn test_post_ra_empty_function() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model);
let mut mf = make_function("empty", vec![]);
let count = sched.schedule_function(&mut mf);
assert_eq!(count, 0);
}
#[test]
fn test_post_ra_single_block() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model.clone());
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let count = sched.schedule_function(&mut mf);
assert!(count <= 3);
assert_eq!(mf.blocks[0].instructions.len(), 3);
}
#[test]
fn test_post_ra_anti_dep_breaking() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model);
sched.break_anti_deps = true;
let instrs = vec![
make_instr(1, Some(1), &[0, 2]), make_instr(7, Some(0), &[3, 4]), ];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let mut phys_instrs = vec![MachineInstr::new(1), MachineInstr::new(7)];
phys_instrs[0].def = Some(1);
phys_instrs[0].operands = vec![MachineOperand::PhysReg(0), MachineOperand::PhysReg(2)];
phys_instrs[1].def = Some(0);
phys_instrs[1].operands = vec![MachineOperand::PhysReg(3), MachineOperand::PhysReg(4)];
let block2 = make_block("entry2", phys_instrs);
let mut mf2 = make_function("test2", vec![block2]);
let count = sched.schedule_function(&mut mf2);
assert!(count <= 2);
assert_eq!(mf2.blocks[0].instructions.len(), 2);
}
#[test]
fn test_full_scheduler_skylake() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
assert_eq!(sched.model.issue_width(), 8);
assert!(sched.model.supports_macro_fusion);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(9, None, &[1, 13]), make_instr(30, None, &[]), ];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let total = sched.run_full_pipeline(&mut mf);
assert!(total <= 8); }
#[test]
fn test_full_scheduler_zen4() {
let sched = X86SchedulerFull::for_cpu("zen4");
assert_eq!(sched.model.issue_width(), 6); assert!(!sched.model.unified_reservation_station);
}
#[test]
fn test_full_scheduler_zen5() {
let sched = X86SchedulerFull::for_cpu("zen5");
assert!(sched.model.issue_width() >= 6);
assert!(sched.model.supports_macro_fusion);
}
#[test]
fn test_full_scheduler_icelake() {
let sched = X86SchedulerFull::for_cpu("ice_lake");
assert!(sched.model.issue_width() >= 8);
assert!(sched.model.supports_macro_fusion);
}
#[test]
fn test_full_scheduler_unknown_cpu() {
let sched = X86SchedulerFull::for_cpu("nonexistent_cpu");
assert_eq!(sched.model.issue_width(), 8);
}
#[test]
fn test_build_dag_from_scheduler() {
let sched = X86SchedulerFull::for_cpu("skylake");
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(3), &[0, 4]),
];
let dag = sched.build_dag(&instrs, false);
assert_eq!(dag.node_count, 2);
assert!(dag.nodes[1].preds.contains(&0));
}
#[test]
fn test_run_algorithm_list() {
let sched = X86SchedulerFull::for_cpu("skylake");
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = sched.build_dag(&instrs, false);
let schedule = sched.run_algorithm(
&dag,
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
assert_eq!(schedule.len(), 3);
}
#[test]
fn test_stats_summary() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
let summary = sched.stats_summary();
assert!(summary.contains("Skylake"));
assert!(summary.contains("Issue width"));
assert!(summary.contains("Total reordered"));
}
#[test]
fn test_extended_model_resource_counts() {
let model = X86ExtendedSchedModel::skylake_client();
assert_eq!(model.get_resource_count(ProcResource::Port0), 1);
assert_eq!(model.get_resource_count(ProcResource::Port1), 1);
}
#[test]
fn test_extended_model_load_latency() {
let model = X86ExtendedSchedModel::skylake_client();
assert_eq!(model.load_latency(), 4);
}
#[test]
fn test_extended_model_create_hazard_recognizer() {
let model = X86ExtendedSchedModel::skylake_client();
let hr = model.create_hazard_recognizer();
assert_eq!(hr.issue_width, 8);
}
#[test]
fn test_edge_kind_is_true() {
assert!(X86EdgeKind::True.is_true());
assert!(!X86EdgeKind::Anti.is_true());
assert!(!X86EdgeKind::Output.is_true());
assert!(!X86EdgeKind::Chain.is_true());
}
#[test]
fn test_edge_kind_is_renamable() {
assert!(X86EdgeKind::Anti.is_renamable());
assert!(X86EdgeKind::Output.is_renamable());
assert!(!X86EdgeKind::True.is_renamable());
assert!(!X86EdgeKind::Chain.is_renamable());
}
#[test]
fn test_edge_kind_is_ordering() {
assert!(X86EdgeKind::Chain.is_ordering());
assert!(X86EdgeKind::Barrier.is_ordering());
assert!(X86EdgeKind::Memory.is_ordering());
assert!(!X86EdgeKind::True.is_ordering());
assert!(!X86EdgeKind::Anti.is_ordering());
}
#[test]
fn test_edge_kind_as_str() {
assert_eq!(X86EdgeKind::True.as_str(), "true");
assert_eq!(X86EdgeKind::Glue.as_str(), "glue");
assert_eq!(X86EdgeKind::Barrier.as_str(), "barrier");
}
#[test]
fn test_sched_reg_virt() {
let r = SchedReg::Virt(42);
assert!(r.is_virt());
assert!(!r.is_phys());
assert_eq!(r.id(), 42);
}
#[test]
fn test_sched_reg_phys() {
let r = SchedReg::Phys(7);
assert!(r.is_phys());
assert!(!r.is_virt());
assert_eq!(r.id(), 7);
}
#[test]
fn test_sched_reg_display() {
assert_eq!(format!("{}", SchedReg::Virt(3)), "%%3");
assert_eq!(format!("{}", SchedReg::Phys(5)), "$p5");
}
#[test]
fn test_sched_reg_key_uniqueness() {
let v = SchedReg::Virt(100);
let p = SchedReg::Phys(100);
assert_ne!(v.to_key(), p.to_key());
}
#[test]
fn test_sched_node_new() {
let node = X86SchedNode::new(5, 1);
assert_eq!(node.instr_idx, 5);
assert_eq!(node.opcode, 1);
assert_eq!(node.latency, 1);
assert_eq!(node.micro_ops, 1);
assert!(!node.scheduled);
assert!(node.defs.is_empty());
assert!(node.uses.is_empty());
}
#[test]
fn test_sched_edge_new() {
let e = X86SchedEdge::new(0, 1, X86EdgeKind::True, 3);
assert_eq!(e.from, 0);
assert_eq!(e.to, 1);
assert_eq!(e.kind, X86EdgeKind::True);
assert_eq!(e.min_latency, 3);
assert!(e.reg.is_none());
}
#[test]
fn test_sched_edge_with_reg() {
let reg = SchedReg::Virt(5);
let e = X86SchedEdge::with_reg(0, 1, X86EdgeKind::True, reg, 2);
assert_eq!(e.reg, Some(reg));
assert_eq!(e.min_latency, 2);
}
#[test]
fn test_is_load_opcode() {
assert!(X86SchedDAG::is_load_opcode(2));
assert!(X86SchedDAG::is_load_opcode(3));
assert!(X86SchedDAG::is_load_opcode(20));
assert!(!X86SchedDAG::is_load_opcode(1));
assert!(!X86SchedDAG::is_load_opcode(9));
}
#[test]
fn test_is_branch_opcode() {
assert!(X86SchedDAG::is_branch_opcode(30));
assert!(X86SchedDAG::is_branch_opcode(39));
assert!(!X86SchedDAG::is_branch_opcode(1));
}
#[test]
fn test_is_flag_defining_opcode() {
assert!(X86SchedDAG::is_flag_defining_opcode(1)); assert!(X86SchedDAG::is_flag_defining_opcode(9)); assert!(!X86SchedDAG::is_flag_defining_opcode(2)); }
#[test]
fn test_is_flag_using_opcode() {
assert!(X86SchedDAG::is_flag_using_opcode(30)); assert!(X86SchedDAG::is_flag_using_opcode(39)); assert!(!X86SchedDAG::is_flag_using_opcode(1));
}
#[test]
fn test_strategy_kind_values() {
let kinds = [
X86SchedStrategyKind::List,
X86SchedStrategyKind::Source,
X86SchedStrategyKind::Hybrid,
X86SchedStrategyKind::ILP,
X86SchedStrategyKind::VLIW,
X86SchedStrategyKind::Trace,
X86SchedStrategyKind::Modulo,
];
assert_eq!(kinds.len(), 7);
}
#[test]
fn test_priority_kind_values() {
let kinds = [
X86SchedPriorityKind::CriticalPath,
X86SchedPriorityKind::LatencyWeighted,
X86SchedPriorityKind::ResourceCritical,
X86SchedPriorityKind::RegPressure,
X86SchedPriorityKind::BalancedILP,
];
assert_eq!(kinds.len(), 5);
}
#[test]
fn test_dag_diamond_dependence() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[0, 13]),
make_instr(1, Some(3), &[1, 2]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.node_count, 4);
assert!(dag.nodes[3].preds.contains(&1));
assert!(dag.nodes[3].preds.contains(&2));
assert_eq!(dag.nodes[0].height, 3);
assert_eq!(dag.nodes[1].height, 2);
assert_eq!(dag.nodes[2].height, 2);
assert_eq!(dag.nodes[3].height, 1);
}
#[test]
fn test_dag_post_ra_flag() {
let instrs = vec![make_instr(1, Some(0), &[1])];
let dag = X86SchedDAG::build(&instrs, None, None, true);
assert!(dag.is_post_ra);
}
#[test]
fn test_dag_pre_ra_flag() {
let instrs = vec![make_instr(1, Some(0), &[1])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(!dag.is_post_ra);
}
#[test]
fn test_sched_reg_post_ra_node_def() {
let mut mi = make_instr(1, Some(5), &[3]);
let dag = X86SchedDAG::build(&[mi], None, None, true);
assert_eq!(dag.nodes[0].defs.len(), 1);
assert!(dag.nodes[0].defs[0].is_phys());
}
#[test]
fn test_sched_reg_pre_ra_node_def() {
let mut mi = make_instr(1, Some(5), &[3]);
let dag = X86SchedDAG::build(&[mi], None, None, false);
assert_eq!(dag.nodes[0].defs.len(), 1);
assert!(dag.nodes[0].defs[0].is_virt());
}
#[test]
fn test_reversed_dag() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::Hybrid,
X86SchedPriorityKind::CriticalPath,
);
let rev = strat.build_reversed_dag(&dag);
assert_eq!(rev.node_count, 3);
let has_rev_edge = rev.edges.iter().any(|e| e.from == 1 && e.to == 0);
assert!(has_rev_edge);
}
#[test]
fn test_large_dag_no_panic() {
let n = 100;
let mut instrs = Vec::with_capacity(n);
for i in 0..n {
let def = Some(i as u32);
let uses: Vec<u32> = if i > 0 {
vec![(i - 1) as u32, (i + 100) as u32]
} else {
vec![100, 101]
};
instrs.push(make_instr(1, def, &uses));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.node_count, n);
assert!(dag.critical_path_length > 0);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), n);
}
#[test]
fn test_all_strategies_on_large_dag() {
let n = 50;
let mut instrs = Vec::with_capacity(n);
for i in 0..n {
let def = Some(i as u32);
let uses: Vec<u32> = if i > 0 {
vec![(i - 1) as u32, (i + 100) as u32]
} else {
vec![100, 101]
};
instrs.push(make_instr(1, def, &uses));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strategies = [
X86SchedStrategyKind::List,
X86SchedStrategyKind::Source,
X86SchedStrategyKind::Hybrid,
X86SchedStrategyKind::ILP,
X86SchedStrategyKind::VLIW,
X86SchedStrategyKind::Trace,
X86SchedStrategyKind::Modulo,
];
for strat in &strategies {
let mut s = X86SchedStrategy::new(*strat, X86SchedPriorityKind::CriticalPath);
let sched = s.schedule(&dag, None);
assert_eq!(
sched.len(),
n,
"Strategy {:?} produced incomplete schedule",
strat
);
}
}
#[test]
fn test_hazard_recognizer_reset() {
let mut hr = X86SchedHazardRecognizer::new(4);
let resources = vec![ProcResource::Port0];
let counts = vec![1];
hr.init_resources(&resources, &counts);
let dag = X86SchedDAG::new();
let node = X86SchedNode::new(0, 1);
hr.issue_node(&node, None);
hr.advance_cycle();
hr.reset();
assert_eq!(hr.current_cycle, 0);
assert_eq!(hr.issued_this_cycle, 0);
}
#[test]
fn test_modulo_schedule_fallback() {
let instrs = vec![
make_instr(1, Some(0), &[1, 2]),
make_instr(1, Some(1), &[0, 3]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::Modulo,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 2);
}
#[test]
fn test_pre_ra_with_spill_avoidance() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PreRAScheduler::new(model);
sched.avoid_spills = true;
let instrs: Vec<MachineInstr> = (0..10)
.map(|i| {
if i == 0 {
make_instr(1, Some(0), &[100, 101])
} else if i == 9 {
make_instr(1, None, &[0, 200]) } else {
make_instr(1, Some(i + 10), &[i as u32 + 9, i as u32 + 20])
}
})
.collect();
let block = make_block("entry", instrs);
let mut mf = make_function("spill_test", vec![block]);
let count = sched.schedule_function(&mut mf);
assert_eq!(mf.blocks[0].instructions.len(), 10);
}
#[test]
fn test_post_ra_micro_fusion_prep() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model.clone());
sched.prepare_micro_fusion = true;
let mut load = make_instr(2, Some(0), &[10]);
load.may_load = true;
let instrs = vec![
load,
make_instr(1, Some(1), &[11, 12]),
make_instr(1, Some(2), &[0, 13]), ];
let block = make_block("entry", instrs);
let mut mf = make_function("fusion_test", vec![block]);
sched.schedule_function(&mut mf);
assert_eq!(mf.blocks[0].instructions.len(), 3);
}
#[test]
fn test_post_ra_nop_insertion() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model.clone());
sched.insert_nops = true;
sched.nop_alignment = 16;
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(30, None, &[]), ];
let block = make_block("entry", instrs);
let mut mf = make_function("nop_test", vec![block]);
sched.schedule_function(&mut mf);
assert!(mf.blocks[0].instructions.len() >= 3);
}
#[test]
fn test_post_ra_bundle_formation() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model.clone());
sched.form_bundles = true;
sched.bundle_size = 2;
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
make_instr(1, Some(3), &[16, 17]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("bundle_test", vec![block]);
sched.schedule_function(&mut mf);
assert_eq!(mf.blocks[0].instructions.len(), 4);
}
#[test]
fn test_asap_alap_computation() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[0, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert_eq!(dag.nodes[0].asap, 0);
assert!(dag.nodes[1].asap >= 1);
assert!(dag.nodes[2].asap >= 1);
for node in &dag.nodes {
assert!(node.slack <= node.alap);
}
}
#[test]
fn test_priority_resource_critical() {
let mut high_uop = make_instr(1, Some(0), &[1, 2]);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::ResourceCritical);
assert!(pri.get(0) > 0);
assert!(pri.get(1) > 0);
}
#[test]
fn test_reorder_branches_earlier() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(30, None, &[1, 13]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::Trace,
X86SchedPriorityKind::CriticalPath,
);
let mut sched = vec![0, 1, 2];
strat.reorder_branches_earlier(&dag, &mut sched);
let pos1 = sched.iter().position(|&x| x == 1).unwrap();
let pos2 = sched.iter().position(|&x| x == 2).unwrap();
assert!(pos1 < pos2);
}
#[test]
fn test_live_register_count() {
let model = X86ExtendedSchedModel::skylake_client();
let sched = X86PreRAScheduler::new(model);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let schedule: Vec<usize> = vec![0, 1, 2];
let live_at_1 = sched.live_register_count_at(&schedule, &dag, 1);
assert!(live_at_1 >= 1);
}
#[test]
fn test_macro_fusion_no_intermediate_flag_def() {
let instrs = vec![
make_instr(9, None, &[0, 1]), make_instr(1, Some(3), &[4, 5]), make_instr(30, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mf = X86MacroFusionScheduling::new(true);
mf.detect_pairs(&dag, &instrs);
let cmp_je_pair = mf.detected_pairs.iter().find(|&&(a, b)| a == 0 && b == 2);
assert!(cmp_je_pair.is_none());
}
#[test]
fn test_extended_model_ice_lake() {
let model = X86ExtendedSchedModel::ice_lake_client();
assert_eq!(model.issue_width(), 10);
assert!(model.supports_macro_fusion);
assert_eq!(model.load_use_latency, 5);
assert!(model.uop_cache_size.is_some());
}
#[test]
fn test_extended_model_alder_lake() {
let model = X86ExtendedSchedModel::alder_lake_p_core();
assert_eq!(model.issue_width(), 6);
assert!(model.supports_macro_fusion);
assert_eq!(model.load_use_latency, 5);
}
#[test]
fn test_extended_model_zen4() {
let model = X86ExtendedSchedModel::zen4();
assert!(!model.unified_reservation_station);
assert!(model.supports_macro_fusion);
assert!(!model.supports_micro_fusion);
assert_eq!(model.load_use_latency, 4);
}
#[test]
fn test_extended_model_zen5() {
let model = X86ExtendedSchedModel::zen5();
assert!(!model.unified_reservation_station);
assert!(model.supports_macro_fusion);
assert_eq!(model.load_use_latency, 4);
}
#[test]
fn test_extended_model_with_resource_counts() {
let base = X86ExtendedSchedModel::skylake_client();
let model =
base.with_resource_counts(&[(ProcResource::Port0, 2), (ProcResource::Port1, 2)]);
assert_eq!(model.get_resource_count(ProcResource::Port0), 2);
assert_eq!(model.get_resource_count(ProcResource::Port1), 2);
assert_eq!(model.get_resource_count(ProcResource::Port2), 1);
}
#[test]
fn test_hazard_data_hazard() {
let mut hr = X86SchedHazardRecognizer::new(4);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
hr.issue_node(&dag.nodes[0], None);
let hazard = hr.check_hazard(&dag.nodes[1], &dag, None);
let _ = hazard;
}
#[test]
fn test_hazard_bypass_add() {
let mut hr = X86SchedHazardRecognizer::new(4);
hr.add_bypass(ProcResource::Port0, ProcResource::Port0, 0);
let node = X86SchedNode::new(0, 1);
let dag = X86SchedDAG::new();
assert!(hr.check_hazard(&node, &dag, None).is_none());
}
#[test]
fn test_hazard_retire_completed() {
let mut hr = X86SchedHazardRecognizer::new(4);
let node = X86SchedNode::new(0, 1);
hr.issue_node(&node, None);
for _ in 0..5 {
hr.advance_cycle();
}
hr.retire_completed();
assert_eq!(hr.current_cycle, 5);
}
#[test]
fn test_modulo_res_mii() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::Modulo,
X86SchedPriorityKind::CriticalPath,
);
let res_mii = strat.compute_res_mii(&dag, None);
assert!(res_mii >= 1);
}
#[test]
fn test_modulo_rec_mii() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::Modulo,
X86SchedPriorityKind::CriticalPath,
);
let rec_mii = strat.compute_rec_mii(&dag);
assert!(rec_mii >= 1);
}
#[test]
fn test_vliw_bundle_resource_conflict() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
make_instr(1, Some(3), &[16, 17]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::VLIW,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 4);
assert!(strat.total_cycles >= 2);
}
#[test]
fn test_scheduler_full_stats() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
sched.run_full_pipeline(&mut mf);
let summary = sched.stats_summary();
assert!(summary.contains("Skylake"));
assert!(!summary.is_empty());
}
#[test]
fn test_scheduler_full_verbose() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
sched.verbose = true;
assert!(sched.verbose);
}
#[test]
fn test_post_ra_disable_features() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model);
sched.break_anti_deps = false;
sched.prepare_micro_fusion = false;
sched.insert_nops = false;
sched.form_bundles = false;
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let count = sched.schedule_function(&mut mf);
assert!(count <= 2);
}
#[test]
fn test_pre_ra_disable_features() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PreRAScheduler::new(model);
sched.cluster_loads = false;
sched.avoid_spills = false;
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let count = sched.schedule_function(&mut mf);
assert!(count <= 2);
}
#[test]
fn test_scheduler_full_disable_pre_ra() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
sched.enable_pre_ra = false;
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let pre_count = sched.run_pre_ra(&mut mf);
assert_eq!(pre_count, 0);
}
#[test]
fn test_scheduler_full_disable_post_ra() {
let mut sched = X86SchedulerFull::for_cpu("skylake");
sched.enable_post_ra = false;
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let block = make_block("entry", instrs);
let mut mf = make_function("test", vec![block]);
let post_count = sched.run_post_ra(&mut mf);
assert_eq!(post_count, 0);
}
#[test]
fn test_dag_single_block_terminator() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(41, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag.nodes[1].is_terminator);
assert!(dag.nodes[1].preds.contains(&0));
}
#[test]
fn test_dag_call_is_barrier() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(43, None, &[]), make_instr(1, Some(2), &[12, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
assert!(dag.nodes[1].is_call);
assert!(dag.nodes[2].preds.contains(&1));
}
#[test]
fn test_priority_compare_ordering() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let pri = X86SchedPriority::compute(&dag, X86SchedPriorityKind::CriticalPath);
assert_eq!(pri.compare(0, 1), Ordering::Less); assert_eq!(pri.compare(1, 0), Ordering::Greater);
assert_eq!(pri.compare(0, 0), Ordering::Equal);
}
#[test]
fn test_get_node_resources() {
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let node = X86SchedNode::new(0, 1);
let model = X86ExtendedSchedModel::skylake_client();
let resources = strat.get_node_resources(&node, Some(&model.base));
assert!(!resources.is_empty());
}
#[test]
fn test_dag_side_effect_chain() {
let mut se1 = make_instr(700, None, &[]); let mut se2 = make_instr(701, None, &[]); let instrs = vec![se1, se2];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let has_chain = dag
.edges
.iter()
.any(|e| e.from == 0 && e.to == 1 && e.kind == X86EdgeKind::Chain);
assert!(has_chain);
}
#[test]
fn test_macro_fusion_enforce_already_adjacent() {
let instrs = vec![
make_instr(9, None, &[0, 1]), make_instr(30, None, &[]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mf = X86MacroFusionScheduling::new(true);
mf.detect_pairs(&dag, &instrs);
let mut schedule: Vec<usize> = vec![0, 1]; mf.enforce_adjacency(&mut schedule, &dag);
assert_eq!(mf.fused_pairs.len(), 1);
}
#[test]
fn test_modulo_try_schedule_with_model() {
let model = X86ExtendedSchedModel::skylake_client();
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, false);
let priority = X86SchedPriority::compute(&dag, X86SchedPriorityKind::CriticalPath);
let strat = X86SchedStrategy::new(
X86SchedStrategyKind::Modulo,
X86SchedPriorityKind::CriticalPath,
);
let result = strat.try_modulo_schedule(&dag, 2, &priority, 4, Some(&model.base));
assert!(result.is_some());
assert_eq!(result.unwrap().len(), 3);
}
#[test]
fn test_pre_ra_reorder_for_spill_avoidance() {
let model = X86ExtendedSchedModel::skylake_client();
let sched = X86PreRAScheduler::new(model);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, None, &[0, 13]), ];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let schedule: Vec<usize> = vec![0, 1, 2];
let result = sched.reorder_for_spill_avoidance(&schedule, &dag);
assert_eq!(result.len(), 3);
let pos2 = result.iter().position(|&x| x == 2).unwrap();
assert!(pos2 <= 2);
}
#[test]
fn test_sched_edge_display() {
let e = X86SchedEdge::new(0, 1, X86EdgeKind::True, 1);
assert_eq!(e.from, 0);
assert_eq!(e.to, 1);
assert_eq!(e.min_latency, 1);
}
#[test]
fn test_sched_dag_default() {
let dag = X86SchedDAG::default();
assert_eq!(dag.node_count, 0);
assert!(!dag.is_post_ra);
}
#[test]
fn test_full_scheduler_with_model() {
let model = X86ExtendedSchedModel::skylake_client();
let sched = X86SchedulerFull::with_model(model.clone());
assert_eq!(sched.model.issue_width(), 8);
}
#[test]
fn test_bundle_formation_resource_conflict() {
let model = X86ExtendedSchedModel::skylake_client();
let mut sched = X86PostRAScheduler::new(model.clone());
sched.form_bundles = true;
sched.bundle_size = 2;
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
];
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, true);
let schedule: Vec<usize> = vec![0, 1];
let result = sched.form_instruction_bundles(&schedule, &dag);
assert_eq!(result.len(), 2);
}
#[test]
fn test_strategy_new_initialization() {
let s = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
assert!(s.schedule.is_empty());
assert_eq!(s.total_cycles, 0);
assert!(s.cycle_schedule.is_empty());
}
#[test]
fn test_hazard_recognizer_load_use_penalty() {
let mut hr = X86SchedHazardRecognizer::new(4);
hr.set_load_use_penalty(5);
let mut load = X86SchedNode::new(0, 2);
load.may_load = true;
load.defs = vec![SchedReg::Virt(100)];
load.latency = 4;
let mut use_node = X86SchedNode::new(1, 1);
use_node.uses = vec![SchedReg::Virt(100)];
let mut dag = X86SchedDAG::new();
dag.node_count = 2;
dag.nodes = vec![load.clone(), use_node.clone()];
dag.nodes[1].preds = vec![0];
dag.nodes[0].succs = vec![1];
dag.succ_edges = vec![vec![0], vec![]];
dag.pred_edges = vec![vec![], vec![0]];
dag.edges = vec![X86SchedEdge::with_reg(
0,
1,
X86EdgeKind::True,
SchedReg::Virt(100),
4,
)];
hr.issue_node(&dag.nodes[0], None);
let hazard = hr.check_hazard(&dag.nodes[1], &dag, None);
if let Some(h) = hazard {
match h {
X86PipelineHazard::LoadUse { .. } => {}
_ => { }
}
}
}
#[test]
fn test_x86_pipeline_hazard_variants() {
let h1 = X86PipelineHazard::None;
let h2 = X86PipelineHazard::Structural(ProcResource::Port0);
let h3 = X86PipelineHazard::Data {
producer: 0,
consumer: 1,
cycles_to_wait: 3,
};
let h4 = X86PipelineHazard::IssueWidth(4);
let h5 = X86PipelineHazard::LoadUse {
load_node: 0,
use_node: 1,
stall_cycles: 4,
};
let _ = (h1, h2, h3, h4, h5);
}
#[test]
fn test_ilp_schedule_packs_instructions() {
let mut instrs = Vec::new();
for i in 0..8u32 {
instrs.push(make_instr(1, Some(i), &[10 + i, 11 + i]));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::ILP,
X86SchedPriorityKind::CriticalPath,
);
let sched = strat.schedule(&dag, None);
assert_eq!(sched.len(), 8);
let max_per_cycle = strat
.cycle_schedule
.values()
.map(|v| v.len())
.max()
.unwrap_or(0);
assert!(max_per_cycle >= 1);
}
}
#[derive(Debug, Clone)]
pub struct X86ReservationStation {
pub name: String,
pub total_entries: u32,
pub occupied: u32,
pub dispatch_ports: Vec<ProcResource>,
pub wakeup_latency: u32,
pub select_latency: u32,
pending: Vec<(SchedNodeId, u32)>,
}
impl X86ReservationStation {
pub fn new(
name: &str,
total_entries: u32,
dispatch_ports: Vec<ProcResource>,
wakeup_latency: u32,
select_latency: u32,
) -> Self {
Self {
name: name.to_string(),
total_entries,
occupied: 0,
dispatch_ports,
wakeup_latency,
select_latency,
pending: Vec::new(),
}
}
pub fn try_insert(&mut self, node_id: SchedNodeId, ready_cycles: u32) -> bool {
if self.occupied >= self.total_entries {
return false;
}
self.occupied += 1;
self.pending.push((node_id, ready_cycles));
true
}
pub fn advance_cycle(&mut self) -> Vec<SchedNodeId> {
let mut ready = Vec::new();
let mut still_pending = Vec::new();
for (nid, cycles) in self.pending.drain(..) {
if cycles <= 1 {
ready.push(nid);
self.occupied -= 1;
} else {
still_pending.push((nid, cycles - 1));
}
}
self.pending = still_pending;
ready
}
pub fn free_entries(&self) -> u32 {
self.total_entries.saturating_sub(self.occupied)
}
pub fn is_full(&self) -> bool {
self.occupied >= self.total_entries
}
pub fn reset(&mut self) {
self.occupied = 0;
self.pending.clear();
}
}
#[derive(Debug, Clone)]
pub struct X86PipelineResources {
pub unified_station: Option<X86ReservationStation>,
pub int_schedulers: Vec<X86ReservationStation>,
pub fp_schedulers: Vec<X86ReservationStation>,
pub load_buffer: X86ReservationStation,
pub store_buffer: X86ReservationStation,
pub rob_size: u32,
pub rob_occupied: u32,
pub branch_order_buffer_size: u32,
}
impl X86PipelineResources {
pub fn unified_intel(model: &X86ExtendedSchedModel) -> Self {
let rs_size = model.base.machine.micro_op_buffer_size;
let rs = X86ReservationStation::new(
"UnifiedScheduler",
rs_size,
model.base.resources.clone(),
1,
1,
);
let lb = X86ReservationStation::new(
"LoadBuffer",
model.base.machine.load_buffers,
vec![ProcResource::LoadUnit],
1,
1,
);
let sb = X86ReservationStation::new(
"StoreBuffer",
model.base.machine.store_buffers,
vec![ProcResource::StoreUnit],
1,
1,
);
Self {
unified_station: Some(rs),
int_schedulers: Vec::new(),
fp_schedulers: Vec::new(),
load_buffer: lb,
store_buffer: sb,
rob_size: model.base.machine.rob_size,
rob_occupied: 0,
branch_order_buffer_size: 48,
}
}
pub fn distributed_amd(model: &X86ExtendedSchedModel) -> Self {
let int_sched = X86ReservationStation::new(
"IntScheduler",
64,
vec![
ProcResource::ALU0,
ProcResource::ALU1,
ProcResource::ALU2,
ProcResource::ALU3,
],
1,
1,
);
let agu_sched = X86ReservationStation::new(
"AGUScheduler",
48,
vec![
ProcResource::AGU0,
ProcResource::AGU1,
ProcResource::AGU2,
ProcResource::AGU3,
],
1,
1,
);
let fp_sched = X86ReservationStation::new(
"FPScheduler",
64,
vec![ProcResource::FPU0, ProcResource::FPU1],
1,
1,
);
let lb = X86ReservationStation::new(
"LoadBuffer",
model.base.machine.load_buffers,
vec![ProcResource::LoadUnit],
1,
1,
);
let sb = X86ReservationStation::new(
"StoreBuffer",
model.base.machine.store_buffers,
vec![ProcResource::StoreUnit],
1,
1,
);
Self {
unified_station: None,
int_schedulers: vec![int_sched, agu_sched],
fp_schedulers: vec![fp_sched],
load_buffer: lb,
store_buffer: sb,
rob_size: model.base.machine.rob_size,
rob_occupied: 0,
branch_order_buffer_size: 32,
}
}
pub fn is_stalled(&self) -> bool {
if self.rob_occupied >= self.rob_size {
return true;
}
if let Some(ref rs) = self.unified_station {
if rs.is_full() {
return true;
}
}
for sched in &self.int_schedulers {
if sched.is_full() {
return true;
}
}
for sched in &self.fp_schedulers {
if sched.is_full() {
return true;
}
}
self.load_buffer.is_full() || self.store_buffer.is_full()
}
pub fn allocate(
&mut self,
node_id: SchedNodeId,
node: &X86SchedNode,
ready_cycles: u32,
) -> bool {
if self.is_stalled() {
return false;
}
self.rob_occupied += 1;
if node.may_load {
self.load_buffer.try_insert(node_id, ready_cycles);
}
if node.may_store {
self.store_buffer.try_insert(node_id, ready_cycles);
}
if let Some(ref mut rs) = self.unified_station {
rs.try_insert(node_id, ready_cycles);
} else {
for sched in &mut self.int_schedulers {
if !sched.is_full() {
sched.try_insert(node_id, ready_cycles);
break;
}
}
}
true
}
pub fn retire(&mut self, count: u32) {
self.rob_occupied = self.rob_occupied.saturating_sub(count);
}
pub fn reset(&mut self) {
self.rob_occupied = 0;
if let Some(ref mut rs) = self.unified_station {
rs.reset();
}
for sched in &mut self.int_schedulers {
sched.reset();
}
for sched in &mut self.fp_schedulers {
sched.reset();
}
self.load_buffer.reset();
self.store_buffer.reset();
}
}
#[derive(Debug, Clone)]
pub struct X86LiveRangeTracker {
def_points: HashMap<SchedReg, SchedNodeId>,
use_points: HashMap<SchedReg, Vec<SchedNodeId>>,
last_use_points: HashMap<SchedReg, SchedNodeId>,
live_at: Vec<HashSet<SchedReg>>,
pub max_live_regs: usize,
pub total_pressure_score: u64,
}
impl X86LiveRangeTracker {
pub fn build(dag: &X86SchedDAG) -> Self {
let n = dag.node_count;
let mut def_points = HashMap::new();
let mut use_points: HashMap<SchedReg, Vec<SchedNodeId>> = HashMap::new();
let mut last_use_points = HashMap::new();
for i in 0..n {
let node = &dag.nodes[i];
for d in &node.defs {
def_points.insert(*d, i);
}
for u in &node.uses {
use_points.entry(*u).or_default().push(i);
last_use_points.insert(*u, i);
}
}
let mut live_at: Vec<HashSet<SchedReg>> = vec![HashSet::new(); n];
let mut current_live: HashSet<SchedReg> = HashSet::new();
let mut max_live = 0usize;
let mut total_score = 0u64;
for i in 0..n {
let node = &dag.nodes[i];
for d in &node.defs {
current_live.insert(*d);
}
live_at[i] = current_live.clone();
let count = current_live.len();
if count > max_live {
max_live = count;
}
total_score += count as u64;
for u in &node.uses {
if let Some(&last) = last_use_points.get(u) {
if last == i {
current_live.remove(u);
}
}
}
}
Self {
def_points,
use_points,
last_use_points,
live_at,
max_live_regs: max_live,
total_pressure_score: total_score,
}
}
pub fn live_at(&self, idx: SchedNodeId) -> HashSet<SchedReg> {
self.live_at.get(idx).cloned().unwrap_or_default()
}
pub fn live_count_at(&self, idx: SchedNodeId) -> usize {
self.live_at.get(idx).map(|s| s.len()).unwrap_or(0)
}
pub fn is_live_at(&self, reg: SchedReg, idx: SchedNodeId) -> bool {
self.live_at
.get(idx)
.map(|s| s.contains(®))
.unwrap_or(false)
}
pub fn def_point(&self, reg: SchedReg) -> Option<SchedNodeId> {
self.def_points.get(®).copied()
}
pub fn use_points(&self, reg: SchedReg) -> Vec<SchedNodeId> {
self.use_points.get(®).cloned().unwrap_or_default()
}
pub fn last_use_point(&self, reg: SchedReg) -> Option<SchedNodeId> {
self.last_use_points.get(®).copied()
}
}
#[derive(Debug, Clone)]
pub struct X86LoadStoreQueue {
pub load_queue_capacity: u32,
pub store_queue_capacity: u32,
pending_loads: Vec<(SchedNodeId, Option<SchedReg>, SchedCycle)>,
pending_stores: Vec<(SchedNodeId, Option<SchedReg>, Option<SchedReg>, SchedCycle)>,
pub forwarding_enabled: bool,
pub forwarding_latency: u32,
pub speculation_enabled: bool,
alias_predictions: HashMap<SchedNodeId, bool>,
}
impl X86LoadStoreQueue {
pub fn new(load_cap: u32, store_cap: u32) -> Self {
Self {
load_queue_capacity: load_cap,
store_queue_capacity: store_cap,
pending_loads: Vec::new(),
pending_stores: Vec::new(),
forwarding_enabled: true,
forwarding_latency: 0,
speculation_enabled: true,
alias_predictions: HashMap::new(),
}
}
pub fn can_issue_load(&self) -> bool {
(self.pending_loads.len() as u32) < self.load_queue_capacity
}
pub fn can_issue_store(&self) -> bool {
(self.pending_stores.len() as u32) < self.store_queue_capacity
}
pub fn issue_load(
&mut self,
node_id: SchedNodeId,
addr_reg: Option<SchedReg>,
cycle: SchedCycle,
) {
self.pending_loads.push((node_id, addr_reg, cycle));
}
pub fn issue_store(
&mut self,
node_id: SchedNodeId,
addr_reg: Option<SchedReg>,
data_reg: Option<SchedReg>,
cycle: SchedCycle,
) {
self.pending_stores
.push((node_id, addr_reg, data_reg, cycle));
}
pub fn check_forwarding(
&self,
_load_addr_reg: Option<SchedReg>,
_load_offset: i64,
) -> Option<SchedNodeId> {
if !self.forwarding_enabled {
return None;
}
self.pending_stores.last().map(|&(nid, _, _, _)| nid)
}
pub fn complete(&mut self, node_id: SchedNodeId, is_store: bool) {
if is_store {
self.pending_stores.retain(|&(nid, _, _, _)| nid != node_id);
} else {
self.pending_loads.retain(|&(nid, _, _)| nid != node_id);
}
}
pub fn predict_alias(&mut self, load_node_id: SchedNodeId) -> bool {
if !self.speculation_enabled || self.pending_stores.is_empty() {
return false;
}
*self
.alias_predictions
.entry(load_node_id)
.or_insert_with(|| (load_node_id % 10) != 0)
}
pub fn pending_load_count(&self) -> usize {
self.pending_loads.len()
}
pub fn pending_store_count(&self) -> usize {
self.pending_stores.len()
}
pub fn reset(&mut self) {
self.pending_loads.clear();
self.pending_stores.clear();
self.alias_predictions.clear();
}
}
#[derive(Debug, Clone)]
pub struct X86BypassNetwork {
paths: HashMap<(ProcResource, ProcResource), u32>,
pub load_use_penalty: u32,
pub fp_chaining_latency: u32,
}
impl X86BypassNetwork {
pub fn skylake() -> Self {
let mut paths = HashMap::new();
for port in &[
ProcResource::Port0,
ProcResource::Port1,
ProcResource::Port5,
ProcResource::Port6,
] {
paths.insert((*port, *port), 0);
}
paths.insert((ProcResource::Port0, ProcResource::Port1), 0);
paths.insert((ProcResource::Port1, ProcResource::Port0), 0);
Self {
paths,
load_use_penalty: 4,
fp_chaining_latency: 4,
}
}
pub fn ice_lake() -> Self {
let mut paths = HashMap::new();
for port in &[
ProcResource::Port0,
ProcResource::Port1,
ProcResource::Port5,
ProcResource::Port6,
] {
paths.insert((*port, *port), 0);
}
paths.insert((ProcResource::Port0, ProcResource::Port1), 0);
paths.insert((ProcResource::Port1, ProcResource::Port0), 0);
Self {
paths,
load_use_penalty: 5,
fp_chaining_latency: 4,
}
}
pub fn zen4() -> Self {
let mut paths = HashMap::new();
for alu in &[
ProcResource::ALU0,
ProcResource::ALU1,
ProcResource::ALU2,
ProcResource::ALU3,
] {
paths.insert((*alu, *alu), 0);
}
for agu in &[ProcResource::AGU0, ProcResource::AGU1, ProcResource::AGU2] {
paths.insert((*agu, ProcResource::ALU0), 0);
}
Self {
paths,
load_use_penalty: 4,
fp_chaining_latency: 3,
}
}
pub fn get_bypass(&self, from: ProcResource, to: ProcResource) -> u32 {
self.paths
.get(&(from, to))
.copied()
.unwrap_or(self.load_use_penalty)
}
pub fn has_zero_cycle_bypass(&self, from: ProcResource, to: ProcResource) -> bool {
self.get_bypass(from, to) == 0
}
}
#[derive(Debug, Clone)]
pub struct X86FlattenedItinerary {
lookup: HashMap<u32, usize>,
itineraries: Vec<InstrItinerary>,
default_itinerary: InstrItinerary,
}
impl X86FlattenedItinerary {
pub fn from_model(model: &SchedModel) -> Self {
let mut lookup = HashMap::new();
for (idx, itin) in model.itineraries.iter().enumerate() {
lookup.insert(itin.opcode, idx);
}
let default_itinerary = InstrItinerary {
opcode: 0,
latency: 1,
uops: 1,
write_resources: vec![WriteRes {
resource: ProcResource::Port0,
cycles: 1,
}],
read_advances: vec![],
write_latencies: vec![WriteLatency {
resource: ProcResource::Port0,
cycles: 1,
}],
};
Self {
lookup,
itineraries: model.itineraries.clone(),
default_itinerary,
}
}
pub fn get(&self, opcode: u32) -> &InstrItinerary {
self.lookup
.get(&opcode)
.and_then(|&idx| self.itineraries.get(idx))
.unwrap_or(&self.default_itinerary)
}
pub fn latency(&self, opcode: u32) -> u32 {
self.get(opcode).latency
}
pub fn uops(&self, opcode: u32) -> u32 {
self.get(opcode).uops
}
pub fn write_resources(&self, opcode: u32) -> &[WriteRes] {
&self.get(opcode).write_resources
}
}
#[derive(Debug, Clone)]
pub struct X86SchedGraphDebug;
impl X86SchedGraphDebug {
pub fn to_dot(dag: &X86SchedDAG, highlight_critical_path: bool) -> String {
let mut dot = String::from("digraph X86SchedDAG {\n");
dot.push_str(" rankdir=TB;\n");
dot.push_str(" node [shape=box, style=filled, fillcolor=lightyellow];\n");
let cp_set: HashSet<SchedNodeId> = if highlight_critical_path {
dag.critical_path_nodes.iter().copied().collect()
} else {
HashSet::new()
};
for (i, node) in dag.nodes.iter().enumerate() {
let fillcolor = if cp_set.contains(&i) {
"lightcoral"
} else if node.scheduled {
"lightgreen"
} else {
"lightyellow"
};
dot.push_str(&format!(
" n{} [label=\"{}: op={} lat={} h={} d={}\", fillcolor={}];\n",
i, i, node.opcode, node.latency, node.height, node.depth, fillcolor
));
}
for edge in &dag.edges {
let style = match edge.kind {
X86EdgeKind::True => "solid",
X86EdgeKind::Anti => "dashed",
X86EdgeKind::Output => "dotted",
X86EdgeKind::Chain => "bold",
X86EdgeKind::Glue => "dashdot",
X86EdgeKind::Barrier => "bold,dashed",
X86EdgeKind::Memory => "bold,dotted",
};
let color = match edge.kind {
X86EdgeKind::True => "black",
X86EdgeKind::Anti => "red",
X86EdgeKind::Output => "blue",
X86EdgeKind::Chain => "orange",
X86EdgeKind::Glue => "purple",
X86EdgeKind::Barrier => "brown",
X86EdgeKind::Memory => "green",
};
dot.push_str(&format!(
" n{} -> n{} [label=\"{} (L={})\", style={}, color={}];\n",
edge.from,
edge.to,
edge.kind.as_str(),
edge.min_latency,
style,
color
));
}
dot.push_str("}\n");
dot
}
pub fn schedule_dump(
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
cycle_map: &BTreeMap<SchedCycle, Vec<SchedNodeId>>,
) -> String {
let mut out = String::new();
out.push_str("=== Schedule Dump ===\n");
out.push_str(&format!(
"Total instructions: {}, Total cycles: {}\n",
schedule.len(),
cycle_map.len()
));
for (cycle, nodes) in cycle_map {
out.push_str(&format!(" Cycle {}: ", cycle));
for &nid in nodes {
if nid < dag.node_count {
out.push_str(&format!("instr_{}(op={}) ", nid, dag.nodes[nid].opcode));
}
}
out.push('\n');
}
out.push_str(&format!(
"Critical path length: {} cycles\n",
dag.critical_path_length
));
out
}
pub fn quality_metrics(
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
total_cycles: SchedCycle,
) -> X86SchedQualityMetrics {
let n = schedule.len();
let mut moved_count = 0u32;
let mut total_distance = 0u64;
for (new_pos, &old_idx) in schedule.iter().enumerate() {
if old_idx < n && old_idx != new_pos {
moved_count += 1;
total_distance += (old_idx as i64 - new_pos as i64).unsigned_abs();
}
}
let avg_distance = if moved_count > 0 {
total_distance / moved_count as u64
} else {
0
};
let ilp = if total_cycles > 0 {
n as f64 / total_cycles as f64
} else {
0.0
};
let cp_ratio = if dag.critical_path_length > 0 {
total_cycles as f64 / dag.critical_path_length as f64
} else {
0.0
};
X86SchedQualityMetrics {
total_instructions: n,
instructions_moved: moved_count,
total_cycles,
avg_move_distance: avg_distance,
ilp,
critical_path_ratio: cp_ratio,
critical_path_length: dag.critical_path_length,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedQualityMetrics {
pub total_instructions: usize,
pub instructions_moved: u32,
pub total_cycles: SchedCycle,
pub avg_move_distance: u64,
pub ilp: f64,
pub critical_path_ratio: f64,
pub critical_path_length: u32,
}
impl fmt::Display for X86SchedQualityMetrics {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(f, "X86 Scheduling Quality Metrics:")?;
writeln!(f, " Instructions: {}", self.total_instructions)?;
writeln!(f, " Moved: {}", self.instructions_moved)?;
writeln!(f, " Total cycles: {}", self.total_cycles)?;
writeln!(f, " ILP: {:.2} instrs/cycle", self.ilp)?;
writeln!(
f,
" Critical path: {} cycles",
self.critical_path_length
)?;
writeln!(f, " CP ratio: {:.2}x", self.critical_path_ratio)?;
writeln!(
f,
" Avg move dist: {} positions",
self.avg_move_distance
)?;
Ok(())
}
}
#[derive(Debug, Clone)]
pub struct X86BlockProfile {
pub exec_count: u64,
pub edge_frequencies: HashMap<(String, String), u64>,
pub is_hot: bool,
pub hot_successor: Option<String>,
}
impl X86BlockProfile {
pub fn new() -> Self {
Self {
exec_count: 0,
edge_frequencies: HashMap::new(),
is_hot: false,
hot_successor: None,
}
}
pub fn classify(&mut self, threshold: u64) {
self.is_hot = self.exec_count >= threshold;
}
pub fn record_edge(&mut self, from: &str, to: &str, count: u64) {
*self
.edge_frequencies
.entry((from.to_string(), to.to_string()))
.or_default() += count;
}
pub fn compute_hot_successor(&mut self, from: &str) {
let mut best_count = 0u64;
let mut best_target: Option<String> = None;
for ((f, t), count) in &self.edge_frequencies {
if f == from && *count > best_count {
best_count = *count;
best_target = Some(t.clone());
}
}
self.hot_successor = best_target;
}
}
#[derive(Debug, Clone)]
pub struct X86TraceBuilder {
pub trace_blocks: Vec<String>,
pub trace_instructions: Vec<(String, usize, MachineInstr)>,
pub side_exits: Vec<(SchedNodeId, String)>,
pub max_trace_length: usize,
pub max_trace_blocks: usize,
}
impl X86TraceBuilder {
pub fn new(max_trace_length: usize, max_trace_blocks: usize) -> Self {
Self {
trace_blocks: Vec::new(),
trace_instructions: Vec::new(),
side_exits: Vec::new(),
max_trace_length,
max_trace_blocks,
}
}
pub fn build_trace(
&mut self,
mf: &MachineFunction,
seed_block_name: &str,
profiles: &HashMap<String, X86BlockProfile>,
) {
self.trace_blocks.clear();
self.trace_instructions.clear();
self.side_exits.clear();
let mut current = seed_block_name.to_string();
let mut total_instrs = 0usize;
loop {
if self.trace_blocks.len() >= self.max_trace_blocks {
break;
}
if total_instrs >= self.max_trace_length {
break;
}
let block = match mf.blocks.iter().find(|bb| bb.name == current) {
Some(b) => b,
None => break,
};
self.trace_blocks.push(current.clone());
for mi in &block.instructions {
self.trace_instructions
.push((current.clone(), total_instrs, mi.clone()));
total_instrs += 1;
if total_instrs >= self.max_trace_length {
break;
}
}
if let Some(profile) = profiles.get(¤t) {
if let Some(ref hot_succ) = profile.hot_successor {
if mf.blocks.iter().any(|bb| bb.name == *hot_succ) {
current = hot_succ.clone();
continue;
}
}
}
if !block.successors.is_empty() {
let first_succ_idx = block.successors[0];
let first_succ_name = &mf.blocks[first_succ_idx].name;
if !self.trace_blocks.contains(first_succ_name) {
current = first_succ_name.clone();
continue;
}
}
break;
}
}
pub fn are_adjacent_in_trace(&self, block_a: &str, block_b: &str) -> bool {
for i in 0..self.trace_blocks.len().saturating_sub(1) {
if self.trace_blocks[i] == block_a && self.trace_blocks[i + 1] == block_b {
return true;
}
}
false
}
}
#[cfg(test)]
mod extended_tests {
use super::*;
use crate::codegen::MachineBasicBlock;
fn make_instr(opcode: u32, def: Option<u32>, uses: &[u32]) -> MachineInstr {
let mut mi = MachineInstr::new(opcode);
if let Some(d) = def {
mi.def = Some(d);
}
for &u in uses {
mi.push_reg(u);
}
mi
}
fn make_block(name: &str, instrs: Vec<MachineInstr>, succs: Vec<usize>) -> MachineBasicBlock {
MachineBasicBlock {
id: 0,
name: name.into(),
instructions: instrs,
successors: succs,
predecessors: Vec::new(),
is_entry: false,
}
}
fn make_function(name: &str, blocks: Vec<MachineBasicBlock>) -> MachineFunction {
MachineFunction {
name: name.into(),
blocks,
virt_reg_counter: 100,
}
}
#[test]
fn test_rs_insert_and_full() {
let mut rs = X86ReservationStation::new("Test", 2, vec![ProcResource::Port0], 1, 1);
assert!(rs.try_insert(0, 3));
assert!(rs.try_insert(1, 1));
assert!(!rs.try_insert(2, 1));
assert!(rs.is_full());
}
#[test]
fn test_rs_advance() {
let mut rs = X86ReservationStation::new("Test", 4, vec![ProcResource::Port0], 1, 1);
rs.try_insert(0, 2);
rs.try_insert(1, 1);
rs.try_insert(2, 3);
let ready = rs.advance_cycle();
assert_eq!(ready, vec![1]);
assert_eq!(rs.occupied, 2);
let ready = rs.advance_cycle();
assert_eq!(ready, vec![0]);
assert_eq!(rs.occupied, 1);
}
#[test]
fn test_rs_reset() {
let mut rs = X86ReservationStation::new("Test", 4, vec![ProcResource::Port0], 1, 1);
rs.try_insert(0, 1);
rs.reset();
assert_eq!(rs.occupied, 0);
}
#[test]
fn test_pr_unified() {
let model = X86ExtendedSchedModel::skylake_client();
let pr = X86PipelineResources::unified_intel(&model);
assert!(pr.unified_station.is_some());
assert!(pr.int_schedulers.is_empty());
}
#[test]
fn test_pr_distributed() {
let model = X86ExtendedSchedModel::zen4();
let pr = X86PipelineResources::distributed_amd(&model);
assert!(pr.unified_station.is_none());
assert!(!pr.int_schedulers.is_empty());
}
#[test]
fn test_pr_allocate_and_retire() {
let model = X86ExtendedSchedModel::skylake_client();
let mut pr = X86PipelineResources::unified_intel(&model);
let node = X86SchedNode::new(0, 1);
assert!(pr.allocate(0, &node, 1));
assert_eq!(pr.rob_occupied, 1);
pr.retire(1);
assert_eq!(pr.rob_occupied, 0);
}
#[test]
fn test_pr_stall_on_rob_full() {
let model = X86ExtendedSchedModel::skylake_client();
let mut pr = X86PipelineResources::unified_intel(&model);
let node = X86SchedNode::new(0, 1);
for i in 0..pr.rob_size {
assert!(pr.allocate(i as usize, &node, 1));
}
assert!(!pr.allocate(pr.rob_size as usize, &node, 1));
}
#[test]
fn test_live_range_build_and_query() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, None, &[0, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let tracker = X86LiveRangeTracker::build(&dag);
assert!(tracker.max_live_regs >= 1);
assert!(tracker.is_live_at(SchedReg::Virt(0), 0));
assert!(tracker.is_live_at(SchedReg::Virt(0), 1));
assert_eq!(tracker.def_point(SchedReg::Virt(0)), Some(0));
assert_eq!(tracker.use_points(SchedReg::Virt(0)).len(), 2);
}
#[test]
fn test_live_range_last_use() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, None, &[0, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let tracker = X86LiveRangeTracker::build(&dag);
assert_eq!(tracker.last_use_point(SchedReg::Virt(0)), Some(2));
}
#[test]
fn test_lsq_issue_and_complete() {
let mut lsq = X86LoadStoreQueue::new(72, 56);
assert!(lsq.can_issue_load());
lsq.issue_load(0, Some(SchedReg::Virt(10)), 0);
assert_eq!(lsq.pending_load_count(), 1);
lsq.complete(0, false);
assert_eq!(lsq.pending_load_count(), 0);
}
#[test]
fn test_lsq_forwarding_and_alias() {
let mut lsq = X86LoadStoreQueue::new(72, 56);
lsq.issue_store(0, Some(SchedReg::Virt(10)), Some(SchedReg::Virt(11)), 0);
assert_eq!(lsq.check_forwarding(Some(SchedReg::Virt(10)), 0), Some(0));
let pred = lsq.predict_alias(1);
let pred2 = lsq.predict_alias(1);
assert_eq!(pred, pred2);
}
#[test]
fn test_lsq_reset() {
let mut lsq = X86LoadStoreQueue::new(72, 56);
lsq.issue_load(0, None, 0);
lsq.issue_store(1, None, None, 0);
lsq.reset();
assert_eq!(lsq.pending_load_count(), 0);
assert_eq!(lsq.pending_store_count(), 0);
}
#[test]
fn test_bypass_skylake_zero_cycle() {
let bn = X86BypassNetwork::skylake();
assert!(bn.has_zero_cycle_bypass(ProcResource::Port0, ProcResource::Port0));
}
#[test]
fn test_bypass_ice_lake_penalty() {
let bn = X86BypassNetwork::ice_lake();
assert_eq!(bn.load_use_penalty, 5);
}
#[test]
fn test_bypass_zen4_alu() {
let bn = X86BypassNetwork::zen4();
assert!(bn.has_zero_cycle_bypass(ProcResource::ALU0, ProcResource::ALU0));
}
#[test]
fn test_bypass_get_fallback() {
let bn = X86BypassNetwork::skylake();
assert_eq!(bn.get_bypass(ProcResource::Port0, ProcResource::Port4), 4);
}
#[test]
fn test_flattened_lookup() {
let model = X86ExtendedSchedModel::skylake_client();
let fi = X86FlattenedItinerary::from_model(&model.base);
assert!(fi.latency(1) >= 1);
assert_eq!(fi.latency(99999), 1); }
#[test]
fn test_flattened_consistency() {
let model = X86ExtendedSchedModel::skylake_client();
let fi = X86FlattenedItinerary::from_model(&model.base);
for itin in &model.base.itineraries {
assert_eq!(fi.latency(itin.opcode), itin.latency);
assert_eq!(fi.uops(itin.opcode), itin.uops);
}
}
#[test]
fn test_dag_to_dot() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let dot = X86SchedGraphDebug::to_dot(&dag, true);
assert!(dot.starts_with("digraph"));
assert!(dot.contains("n0"));
assert!(dot.contains("->"));
}
#[test]
fn test_schedule_dump() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut cm: BTreeMap<SchedCycle, Vec<SchedNodeId>> = BTreeMap::new();
cm.insert(0, vec![0]);
cm.insert(1, vec![1]);
let dump = X86SchedGraphDebug::schedule_dump(&[0, 1], &dag, &cm);
assert!(dump.contains("Cycle 0"));
assert!(dump.contains("Cycle 1"));
}
#[test]
fn test_quality_metrics_basic() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let metrics = X86SchedGraphDebug::quality_metrics(&[0, 1, 2], &dag, 3);
assert_eq!(metrics.total_instructions, 3);
assert!(metrics.ilp > 0.0);
}
#[test]
fn test_quality_metrics_display() {
let metrics = X86SchedQualityMetrics {
total_instructions: 10,
instructions_moved: 5,
total_cycles: 4,
avg_move_distance: 2,
ilp: 2.5,
critical_path_ratio: 1.5,
critical_path_length: 6,
};
let s = format!("{}", metrics);
assert!(s.contains("2.50"));
assert!(s.contains("ILP"));
}
#[test]
fn test_block_profile_hot() {
let mut bp = X86BlockProfile::new();
bp.exec_count = 100;
bp.classify(50);
assert!(bp.is_hot);
bp.classify(200);
assert!(!bp.is_hot);
}
#[test]
fn test_block_profile_successor() {
let mut bp = X86BlockProfile::new();
bp.record_edge("entry", "loop", 10);
bp.record_edge("entry", "exit", 2);
bp.compute_hot_successor("entry");
assert_eq!(bp.hot_successor, Some("loop".to_string()));
}
#[test]
fn test_trace_builder_simple() {
let block_a = make_block("A", vec![make_instr(1, Some(0), &[1, 2])], vec!["B".into()]);
let block_b = make_block("B", vec![make_instr(1, Some(3), &[0, 4])], vec![]);
let mf = make_function("test", vec![block_a, block_b]);
let mut profiles = HashMap::new();
let mut bp_a = X86BlockProfile::new();
bp_a.exec_count = 100;
bp_a.record_edge("A", "B", 90);
bp_a.compute_hot_successor("A");
profiles.insert("A".to_string(), bp_a);
let mut builder = X86TraceBuilder::new(100, 10);
builder.build_trace(&mf, "A", &profiles);
assert_eq!(builder.trace_blocks, vec!["A", "B"]);
}
#[test]
fn test_trace_builder_adjacent() {
let mut builder = X86TraceBuilder::new(100, 10);
builder.trace_blocks = vec!["A".into(), "B".into(), "C".into()];
assert!(builder.are_adjacent_in_trace("A", "B"));
assert!(!builder.are_adjacent_in_trace("A", "C"));
}
#[test]
fn test_trace_builder_max_length() {
let mut instrs_a = Vec::new();
for i in 0..50u32 {
instrs_a.push(make_instr(1, Some(i), &[i + 100]));
}
let block_a = make_block("A", instrs_a, vec!["B".into()]);
let block_b = make_block("B", vec![make_instr(1, Some(200), &[201])], vec![]);
let mf = make_function("test", vec![block_a, block_b]);
let mut profiles = HashMap::new();
let mut bp_a = X86BlockProfile::new();
bp_a.exec_count = 100;
bp_a.record_edge("A", "B", 90);
bp_a.compute_hot_successor("A");
profiles.insert("A".to_string(), bp_a);
let mut builder = X86TraceBuilder::new(30, 10);
builder.build_trace(&mf, "A", &profiles);
assert!(builder.trace_instructions.len() <= 30);
}
#[test]
fn test_pipeline_scheduler_integration() {
let model = X86ExtendedSchedModel::skylake_client();
let mut pr = X86PipelineResources::unified_intel(&model);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, false);
for i in 0..dag.node_count {
assert!(pr.allocate(i, &dag.nodes[i], 1));
}
pr.retire(3);
assert_eq!(pr.rob_occupied, 0);
}
#[test]
fn test_live_range_pre_ra_integration() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
make_instr(1, None, &[2, 14]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let tracker = X86LiveRangeTracker::build(&dag);
assert_eq!(tracker.def_point(SchedReg::Virt(0)), Some(0));
assert!(tracker.is_live_at(SchedReg::Virt(0), 0));
assert!(tracker.is_live_at(SchedReg::Virt(0), 1));
}
#[test]
fn test_bypass_hazard_integration() {
let mut hr = X86SchedHazardRecognizer::new(4);
let bn = X86BypassNetwork::skylake();
hr.add_bypass(
ProcResource::Port0,
ProcResource::Port0,
bn.get_bypass(ProcResource::Port0, ProcResource::Port0),
);
let mut prod = X86SchedNode::new(0, 1);
prod.defs = vec![SchedReg::Virt(100)];
prod.latency = 1;
let mut cons = X86SchedNode::new(1, 1);
cons.uses = vec![SchedReg::Virt(100)];
let mut dag = X86SchedDAG::new();
dag.node_count = 2;
dag.nodes = vec![prod.clone(), cons.clone()];
dag.nodes[1].preds = vec![0];
dag.nodes[0].succs = vec![1];
dag.succ_edges = vec![vec![0], vec![]];
dag.pred_edges = vec![vec![], vec![0]];
dag.edges = vec![X86SchedEdge::with_reg(
0,
1,
X86EdgeKind::True,
SchedReg::Virt(100),
1,
)];
hr.issue_node(&dag.nodes[0], None);
let hazard = hr.check_hazard(&dag.nodes[1], &dag, None);
match hazard {
None => {}
Some(X86PipelineHazard::Data { cycles_to_wait, .. }) => assert!(cycles_to_wait <= 1),
_ => {}
}
}
#[test]
fn test_lsq_post_ra_integration() {
let model = X86ExtendedSchedModel::skylake_client();
let mut lsq = X86LoadStoreQueue::new(
model.base.machine.load_buffers,
model.base.machine.store_buffers,
);
assert!(lsq.can_issue_load());
lsq.issue_load(0, None, 0);
assert!(lsq.can_issue_store());
lsq.issue_store(1, None, None, 0);
assert_eq!(lsq.check_forwarding(None, 0), Some(1));
lsq.complete(0, false);
lsq.complete(1, true);
assert_eq!(lsq.pending_load_count(), 0);
}
#[test]
fn test_dag_dot_critical_path_highlight() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[0, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let dot = X86SchedGraphDebug::to_dot(&dag, true);
assert!(dot.contains("lightcoral"));
}
}
#[derive(Debug, Clone)]
pub struct X86SchedSubtargetModel {
pub kind: X86SchedModelKind,
pub name: String,
pub dispatch_width: u32,
pub retire_width: u32,
pub loop_stream_detector: bool,
pub micro_op_cache_size: Option<u32>,
pub macro_fusion_pairs: Vec<(u32, u32)>,
pub micro_fusion_capable: bool,
pub partial_reg_stall: bool,
pub slow_lea_threshold: u32,
pub div_latency_32: u32,
pub div_latency_64: u32,
pub div_throughput_32: u32,
pub div_throughput_64: u32,
pub branch_mispredict_penalty: u32,
pub two_level_branch_predictor: bool,
pub indirect_branch_predictor: bool,
pub loop_branch_predictor: bool,
pub stack_engine: bool,
pub zero_latency_mov_elimination: bool,
pub zero_idiom_elimination: bool,
pub ones_idiom_elimination: bool,
pub move_elimination: bool,
pub fast_gather: bool,
pub avx512_downclock: bool,
pub avx512_frequency_max: u32,
pub avx2_frequency_max: u32,
pub sse_frequency_max: u32,
pub base_frequency: u32,
pub max_turbo_frequency: u32,
}
impl X86SchedSubtargetModel {
pub fn from_kind(kind: X86SchedModelKind) -> Self {
match kind {
X86SchedModelKind::SkylakeClient => Self {
kind,
name: "Skylake Client".into(),
dispatch_width: 6,
retire_width: 8,
loop_stream_detector: true,
micro_op_cache_size: Some(1536),
macro_fusion_pairs: vec![(9, 30), (10, 30), (6, 30)],
micro_fusion_capable: true,
partial_reg_stall: false,
slow_lea_threshold: 3,
div_latency_32: 26,
div_latency_64: 42,
div_throughput_32: 6,
div_throughput_64: 10,
branch_mispredict_penalty: 16,
two_level_branch_predictor: true,
indirect_branch_predictor: true,
loop_branch_predictor: true,
stack_engine: true,
zero_latency_mov_elimination: true,
zero_idiom_elimination: true,
ones_idiom_elimination: false,
move_elimination: true,
fast_gather: false,
avx512_downclock: false,
avx512_frequency_max: 0,
avx2_frequency_max: 0,
sse_frequency_max: 0,
base_frequency: 4000,
max_turbo_frequency: 4200,
},
X86SchedModelKind::IceLakeClient => Self {
kind,
name: "Ice Lake Client".into(),
dispatch_width: 6,
retire_width: 8,
loop_stream_detector: true,
micro_op_cache_size: Some(2304),
macro_fusion_pairs: vec![(9, 30), (10, 30), (6, 30), (8, 30)],
micro_fusion_capable: true,
partial_reg_stall: false,
slow_lea_threshold: 3,
div_latency_32: 18,
div_latency_64: 34,
div_throughput_32: 4,
div_throughput_64: 8,
branch_mispredict_penalty: 18,
two_level_branch_predictor: true,
indirect_branch_predictor: true,
loop_branch_predictor: true,
stack_engine: true,
zero_latency_mov_elimination: true,
zero_idiom_elimination: true,
ones_idiom_elimination: false,
move_elimination: true,
fast_gather: true,
avx512_downclock: false,
avx512_frequency_max: 0,
avx2_frequency_max: 0,
sse_frequency_max: 0,
base_frequency: 2800,
max_turbo_frequency: 4100,
},
X86SchedModelKind::AlderLakeP => Self {
kind,
name: "Alder Lake P-core (Golden Cove)".into(),
dispatch_width: 6,
retire_width: 8,
loop_stream_detector: true,
micro_op_cache_size: Some(4096),
macro_fusion_pairs: vec![(9, 30), (10, 30), (6, 30), (8, 30), (7, 30)],
micro_fusion_capable: true,
partial_reg_stall: false,
slow_lea_threshold: 4,
div_latency_32: 14,
div_latency_64: 22,
div_throughput_32: 3,
div_throughput_64: 5,
branch_mispredict_penalty: 20,
two_level_branch_predictor: true,
indirect_branch_predictor: true,
loop_branch_predictor: true,
stack_engine: true,
zero_latency_mov_elimination: true,
zero_idiom_elimination: true,
ones_idiom_elimination: true,
move_elimination: true,
fast_gather: true,
avx512_downclock: true,
avx512_frequency_max: 4200,
avx2_frequency_max: 5000,
sse_frequency_max: 5200,
base_frequency: 3200,
max_turbo_frequency: 5200,
},
X86SchedModelKind::Zen4 => Self {
kind,
name: "AMD Zen 4".into(),
dispatch_width: 6,
retire_width: 8,
loop_stream_detector: false,
micro_op_cache_size: Some(6750),
macro_fusion_pairs: vec![(9, 30), (10, 30)],
micro_fusion_capable: false,
partial_reg_stall: false,
slow_lea_threshold: 2,
div_latency_32: 12,
div_latency_64: 17,
div_throughput_32: 5,
div_throughput_64: 8,
branch_mispredict_penalty: 18,
two_level_branch_predictor: false,
indirect_branch_predictor: true,
loop_branch_predictor: true,
stack_engine: true,
zero_latency_mov_elimination: true,
zero_idiom_elimination: true,
ones_idiom_elimination: false,
move_elimination: true,
fast_gather: false,
avx512_downclock: false,
avx512_frequency_max: 0,
avx2_frequency_max: 0,
sse_frequency_max: 0,
base_frequency: 4200,
max_turbo_frequency: 5700,
},
X86SchedModelKind::Zen5 => Self {
kind,
name: "AMD Zen 5".into(),
dispatch_width: 8,
retire_width: 8,
loop_stream_detector: false,
micro_op_cache_size: Some(6750),
macro_fusion_pairs: vec![(9, 30), (10, 30), (6, 30)],
micro_fusion_capable: false,
partial_reg_stall: false,
slow_lea_threshold: 2,
div_latency_32: 10,
div_latency_64: 15,
div_throughput_32: 4,
div_throughput_64: 6,
branch_mispredict_penalty: 16,
two_level_branch_predictor: false,
indirect_branch_predictor: true,
loop_branch_predictor: true,
stack_engine: true,
zero_latency_mov_elimination: true,
zero_idiom_elimination: true,
ones_idiom_elimination: true,
move_elimination: true,
fast_gather: true,
avx512_downclock: false,
avx512_frequency_max: 0,
avx2_frequency_max: 0,
sse_frequency_max: 0,
base_frequency: 4400,
max_turbo_frequency: 5800,
},
_ => Self::default_generic(),
}
}
fn default_generic() -> Self {
Self {
kind: X86SchedModelKind::Generic,
name: "Generic X86".into(),
dispatch_width: 4,
retire_width: 4,
loop_stream_detector: false,
micro_op_cache_size: None,
macro_fusion_pairs: vec![(9, 30), (10, 30)],
micro_fusion_capable: false,
partial_reg_stall: true,
slow_lea_threshold: 2,
div_latency_32: 26,
div_latency_64: 42,
div_throughput_32: 6,
div_throughput_64: 10,
branch_mispredict_penalty: 14,
two_level_branch_predictor: false,
indirect_branch_predictor: false,
loop_branch_predictor: false,
stack_engine: false,
zero_latency_mov_elimination: false,
zero_idiom_elimination: false,
ones_idiom_elimination: false,
move_elimination: false,
fast_gather: false,
avx512_downclock: false,
avx512_frequency_max: 0,
avx2_frequency_max: 0,
sse_frequency_max: 0,
base_frequency: 3000,
max_turbo_frequency: 3500,
}
}
pub fn supports_macro_fusion(&self, first_opcode: u32, second_opcode: u32) -> bool {
self.macro_fusion_pairs
.contains(&(first_opcode, second_opcode))
}
pub fn get_div_latency(&self, is_64bit: bool) -> u32 {
if is_64bit {
self.div_latency_64
} else {
self.div_latency_32
}
}
pub fn get_div_throughput(&self, is_64bit: bool) -> u32 {
if is_64bit {
self.div_throughput_64
} else {
self.div_throughput_32
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedRegion {
pub blocks: Vec<String>,
pub nodes: Vec<X86SchedNode>,
pub edges: Vec<X86SchedEdge>,
pub inter_block_edges: Vec<(SchedNodeId, String, SchedNodeId, String)>,
pub is_trace: bool,
pub is_superblock: bool,
pub is_hyperblock: bool,
}
impl X86SchedRegion {
pub fn new() -> Self {
Self {
blocks: Vec::new(),
nodes: Vec::new(),
edges: Vec::new(),
inter_block_edges: Vec::new(),
is_trace: false,
is_superblock: false,
is_hyperblock: false,
}
}
pub fn from_trace(trace: &X86TraceBuilder, mf: &MachineFunction) -> Self {
let mut region = Self::new();
region.is_trace = true;
region.blocks = trace.trace_blocks.clone();
let mut node_offset = 0usize;
for (block_name, _instr_idx, _mi) in &trace.trace_instructions {
let node = X86SchedNode::new(node_offset, _mi.opcode);
region.nodes.push(node);
node_offset += 1;
}
region
}
pub fn total_nodes(&self) -> usize {
self.nodes.len()
}
pub fn total_blocks(&self) -> usize {
self.blocks.len()
}
}
#[derive(Debug, Clone)]
pub struct X86SchedCostModel {
pub cost_per_cycle: f64,
pub cost_per_spill: f64,
pub cost_per_nop: f64,
pub cost_per_bundle_break: f64,
pub benefit_per_fusion: f64,
pub benefit_per_micro_fusion: f64,
pub cost_per_mispredict: f64,
}
impl X86SchedCostModel {
pub fn default_model() -> Self {
Self {
cost_per_cycle: 1.0,
cost_per_spill: 10.0,
cost_per_nop: 0.5,
cost_per_bundle_break: 2.0,
benefit_per_fusion: -1.0,
benefit_per_micro_fusion: -0.5,
cost_per_mispredict: 14.0,
}
}
pub fn estimate_cost(
&self,
total_cycles: SchedCycle,
spills: u32,
nops: u32,
bundle_breaks: u32,
fusions: u32,
micro_fusions: u32,
likely_mispredicts: u32,
) -> f64 {
total_cycles as f64 * self.cost_per_cycle
+ spills as f64 * self.cost_per_spill
+ nops as f64 * self.cost_per_nop
+ bundle_breaks as f64 * self.cost_per_bundle_break
+ fusions as f64 * self.benefit_per_fusion
+ micro_fusions as f64 * self.benefit_per_micro_fusion
+ likely_mispredicts as f64 * self.cost_per_mispredict
}
pub fn compare_schedules(
&self,
cycles_a: SchedCycle,
spills_a: u32,
nops_a: u32,
bundles_a: u32,
fusions_a: u32,
cycles_b: SchedCycle,
spills_b: u32,
nops_b: u32,
bundles_b: u32,
fusions_b: u32,
) -> Ordering {
let cost_a = self.estimate_cost(cycles_a, spills_a, nops_a, bundles_a, fusions_a, 0, 0);
let cost_b = self.estimate_cost(cycles_b, spills_b, nops_b, bundles_b, fusions_b, 0, 0);
cost_a.partial_cmp(&cost_b).unwrap_or(Ordering::Equal)
}
}
#[derive(Debug, Clone)]
pub struct X86SchedCycleTimer {
pub current_cycle: SchedCycle,
pub issue_events: Vec<(SchedCycle, SchedNodeId)>,
pub execute_events: Vec<(SchedCycle, SchedNodeId)>,
pub writeback_events: Vec<(SchedCycle, SchedNodeId)>,
pub retire_events: Vec<(SchedCycle, SchedNodeId)>,
pub stall_cycles: Vec<SchedCycle>,
pub bubble_cycles: Vec<SchedCycle>,
}
impl X86SchedCycleTimer {
pub fn new() -> Self {
Self {
current_cycle: 0,
issue_events: Vec::new(),
execute_events: Vec::new(),
writeback_events: Vec::new(),
retire_events: Vec::new(),
stall_cycles: Vec::new(),
bubble_cycles: Vec::new(),
}
}
pub fn record_issue(&mut self, node_id: SchedNodeId) {
self.issue_events.push((self.current_cycle, node_id));
}
pub fn record_execute(&mut self, node_id: SchedNodeId, execute_cycle: SchedCycle) {
self.execute_events.push((execute_cycle, node_id));
}
pub fn record_writeback(&mut self, node_id: SchedNodeId, wb_cycle: SchedCycle) {
self.writeback_events.push((wb_cycle, node_id));
}
pub fn record_retire(&mut self, node_id: SchedNodeId, retire_cycle: SchedCycle) {
self.retire_events.push((retire_cycle, node_id));
}
pub fn record_stall(&mut self) {
self.stall_cycles.push(self.current_cycle);
}
pub fn record_bubble(&mut self) {
self.bubble_cycles.push(self.current_cycle);
}
pub fn advance(&mut self) {
self.current_cycle += 1;
}
pub fn utilization(&self) -> f64 {
let total = self.current_cycle.max(1) as f64;
let useful = self.issue_events.len() as f64;
useful / total
}
pub fn stall_rate(&self) -> f64 {
let total = self.current_cycle.max(1) as f64;
self.stall_cycles.len() as f64 / total
}
pub fn reset(&mut self) {
self.current_cycle = 0;
self.issue_events.clear();
self.execute_events.clear();
self.writeback_events.clear();
self.retire_events.clear();
self.stall_cycles.clear();
self.bubble_cycles.clear();
}
}
#[derive(Debug, Clone)]
pub struct X86SchedComparison {
pub name_a: String,
pub name_b: String,
pub cycles_a: SchedCycle,
pub cycles_b: SchedCycle,
pub moves_a: usize,
pub moves_b: usize,
pub ilp_a: f64,
pub ilp_b: f64,
pub winner: Option<String>,
pub advantage_pct: f64,
}
impl X86SchedComparison {
pub fn compare(
name_a: &str,
schedule_a: &[SchedNodeId],
cycles_a: SchedCycle,
name_b: &str,
schedule_b: &[SchedNodeId],
cycles_b: SchedCycle,
dag: &X86SchedDAG,
) -> Self {
let moves_a = schedule_a
.iter()
.enumerate()
.filter(|&(i, &nid)| i != nid && nid < dag.node_count)
.count();
let moves_b = schedule_b
.iter()
.enumerate()
.filter(|&(i, &nid)| i != nid && nid < dag.node_count)
.count();
let ilp_a = if cycles_a > 0 {
schedule_a.len() as f64 / cycles_a as f64
} else {
0.0
};
let ilp_b = if cycles_b > 0 {
schedule_b.len() as f64 / cycles_b as f64
} else {
0.0
};
let (winner, advantage_pct) = if cycles_a < cycles_b {
let pct = (cycles_b - cycles_a) as f64 / cycles_b.max(1) as f64 * 100.0;
(Some(name_a.to_string()), pct)
} else if cycles_b < cycles_a {
let pct = (cycles_a - cycles_b) as f64 / cycles_a.max(1) as f64 * 100.0;
(Some(name_b.to_string()), pct)
} else if ilp_a > ilp_b {
(
Some(name_a.to_string()),
(ilp_a - ilp_b) / ilp_b.max(0.01) * 100.0,
)
} else if ilp_b > ilp_a {
(
Some(name_b.to_string()),
(ilp_b - ilp_a) / ilp_a.max(0.01) * 100.0,
)
} else {
(None, 0.0)
};
Self {
name_a: name_a.to_string(),
name_b: name_b.to_string(),
cycles_a,
cycles_b,
moves_a,
moves_b,
ilp_a,
ilp_b,
winner,
advantage_pct,
}
}
}
impl fmt::Display for X86SchedComparison {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
writeln!(f, "Schedule Comparison: {} vs {}", self.name_a, self.name_b)?;
writeln!(
f,
" {}: {} cycles, {} moves, ILP={:.2}",
self.name_a, self.cycles_a, self.moves_a, self.ilp_a
)?;
writeln!(
f,
" {}: {} cycles, {} moves, ILP={:.2}",
self.name_b, self.cycles_b, self.moves_b, self.ilp_b
)?;
if let Some(ref w) = self.winner {
writeln!(f, " Winner: {} (+{:.1}%)", w, self.advantage_pct)?;
} else {
writeln!(f, " Result: tie")?;
}
Ok(())
}
}
#[derive(Debug, Clone)]
pub struct X86SchedHeuristics {
pub critical_path_weight: f64,
pub register_pressure_weight: f64,
pub resource_scarcity_weight: f64,
pub latency_weight: f64,
pub fanout_weight: f64,
pub ilp_weight: f64,
pub spill_cost_weight: f64,
pub fusion_benefit_weight: f64,
pub load_cluster_distance: usize,
pub max_speculative_loads: usize,
pub prefer_small_code: bool,
pub aggresive_if_conversion: bool,
pub allow_load_store_reordering: bool,
}
impl Default for X86SchedHeuristics {
fn default() -> Self {
Self {
critical_path_weight: 1.0,
register_pressure_weight: 0.5,
resource_scarcity_weight: 0.3,
latency_weight: 0.4,
fanout_weight: 0.2,
ilp_weight: 0.3,
spill_cost_weight: 2.0,
fusion_benefit_weight: 1.5,
load_cluster_distance: 3,
max_speculative_loads: 4,
prefer_small_code: false,
aggresive_if_conversion: false,
allow_load_store_reordering: false,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedLoopAnalyzer {
pub loop_header: String,
pub loop_blocks: Vec<String>,
pub trip_count_estimate: Option<u64>,
pub is_innermost: bool,
pub has_function_calls: bool,
pub has_side_exits: usize,
pub body_instructions: usize,
pub recurrence_depth: u32,
pub estimated_iterations: u64,
pub profitable_for_pipelining: bool,
pub profitable_for_unrolling: bool,
}
impl X86SchedLoopAnalyzer {
pub fn analyze(mf: &MachineFunction, header_name: &str) -> Self {
let mut loop_blocks = Vec::new();
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(header_name.to_string());
while let Some(block_name) = queue.pop_front() {
if !visited.insert(block_name.clone()) {
continue;
}
if let Some(block) = mf.blocks.iter().find(|bb| bb.name == block_name) {
loop_blocks.push(block_name.clone());
for &succ_idx in &block.successors {
if succ_idx < mf.blocks.len() {
let succ_name = &mf.blocks[succ_idx].name;
if succ_name != header_name && !visited.contains(succ_name) {
queue.push_back(succ_name.clone());
}
}
}
}
if loop_blocks.len() > 20 {
break;
}
}
let body_instrs: usize = loop_blocks
.iter()
.filter_map(|bn| mf.blocks.iter().find(|bb| bb.name == *bn))
.map(|bb| bb.instructions.len())
.sum();
let has_calls = loop_blocks
.iter()
.filter_map(|bn| mf.blocks.iter().find(|bb| bb.name == *bn))
.any(|bb| {
bb.instructions
.iter()
.any(|mi| X86SchedDAG::is_call_opcode(mi.opcode))
});
let side_exits = loop_blocks
.iter()
.filter_map(|bn| mf.blocks.iter().find(|bb| bb.name == *bn))
.filter(|bb| {
bb.successors.iter().any(|&s| {
if s >= mf.blocks.len() {
return false;
}
let sname = &mf.blocks[s].name;
!loop_blocks.contains(sname) && sname != header_name
})
})
.count();
let trip_estimate = if body_instrs > 0 {
Some(100) } else {
None
};
let profitable_pipe = body_instrs >= 8 && !has_calls && loop_blocks.len() <= 3;
let profitable_unroll = body_instrs <= 32 && !has_calls;
Self {
loop_header: header_name.to_string(),
loop_blocks,
trip_count_estimate: trip_estimate,
is_innermost: true,
has_function_calls: has_calls,
has_side_exits: side_exits,
body_instructions: body_instrs,
recurrence_depth: 0,
estimated_iterations: trip_estimate.unwrap_or(0),
profitable_for_pipelining: profitable_pipe,
profitable_for_unrolling: profitable_unroll,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedMutation {
pub max_swap_distance: usize,
pub mutation_rate: f64,
pub rng_state: u64,
}
impl X86SchedMutation {
pub fn new(max_swap_distance: usize, mutation_rate: f64) -> Self {
Self {
max_swap_distance,
mutation_rate,
rng_state: 0x5EED_5EED,
}
}
fn next_random(&mut self) -> u64 {
self.rng_state = self
.rng_state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
self.rng_state >> 33
}
pub fn mutate(&mut self, schedule: &[SchedNodeId], dag: &X86SchedDAG) -> Vec<SchedNodeId> {
let mut result = schedule.to_vec();
let n = result.len();
if n < 2 {
return result;
}
for _ in 0..((n as f64 * self.mutation_rate) as usize).max(1) {
let i = (self.next_random() as usize) % n;
let max_j = (i + self.max_swap_distance).min(n - 1);
if max_j <= i {
continue;
}
let j = i + 1 + (self.next_random() as usize) % (max_j - i);
if self.can_swap(i, j, &result, dag) {
result.swap(i, j);
}
}
result
}
fn can_swap(&self, i: usize, j: usize, schedule: &[SchedNodeId], dag: &X86SchedDAG) -> bool {
let ai = schedule[i];
let aj = schedule[j];
if ai >= dag.node_count || aj >= dag.node_count {
return false;
}
for &pred in &dag.nodes[aj].preds {
if pred == ai {
return false;
}
}
true
}
}
#[derive(Debug, Clone)]
pub struct X86SchedProfileGuided {
pub block_frequencies: HashMap<String, u64>,
pub edge_frequencies: HashMap<(String, String), u64>,
pub block_profiles: HashMap<String, X86BlockProfile>,
pub enabled: bool,
}
impl X86SchedProfileGuided {
pub fn new() -> Self {
Self {
block_frequencies: HashMap::new(),
edge_frequencies: HashMap::new(),
block_profiles: HashMap::new(),
enabled: false,
}
}
pub fn record_block_execution(&mut self, block_name: &str, count: u64) {
*self
.block_frequencies
.entry(block_name.to_string())
.or_default() += count;
self.block_profiles
.entry(block_name.to_string())
.or_insert_with(X86BlockProfile::new)
.exec_count += count;
}
pub fn record_edge_taken(&mut self, from: &str, to: &str, count: u64) {
*self
.edge_frequencies
.entry((from.to_string(), to.to_string()))
.or_default() += count;
self.block_profiles
.entry(from.to_string())
.or_insert_with(X86BlockProfile::new)
.record_edge(from, to, count);
}
pub fn get_block_frequency(&self, block_name: &str) -> u64 {
self.block_frequencies.get(block_name).copied().unwrap_or(0)
}
pub fn get_edge_frequency(&self, from: &str, to: &str) -> u64 {
self.edge_frequencies
.get(&(from.to_string(), to.to_string()))
.copied()
.unwrap_or(0)
}
pub fn hot_blocks(&self, threshold_pct: f64) -> Vec<String> {
let total: u64 = self.block_frequencies.values().sum();
if total == 0 {
return Vec::new();
}
let threshold = (total as f64 * threshold_pct / 100.0) as u64;
self.block_frequencies
.iter()
.filter(|&(_, &count)| count >= threshold)
.map(|(name, _)| name.clone())
.collect()
}
pub fn classify_all(&mut self, hot_threshold_pct: f64) {
let total: u64 = self.block_frequencies.values().sum();
let threshold = if total > 0 {
(total as f64 * hot_threshold_pct / 100.0) as u64
} else {
0
};
for (_, profile) in &mut self.block_profiles {
profile.classify(threshold.max(1));
if profile.is_hot {
let block_name = self
.block_frequencies
.iter()
.find(|&(_, &c)| c == profile.exec_count)
.map(|(n, _)| n.clone());
if let Some(ref name) = block_name {
profile.compute_hot_successor(name);
}
}
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedDominators {
pub idom: HashMap<String, String>,
pub dom_frontier: HashMap<String, HashSet<String>>,
pub dom_tree_children: HashMap<String, Vec<String>>,
}
impl X86SchedDominators {
pub fn compute(mf: &MachineFunction, entry_name: &str) -> Self {
let block_names: Vec<String> = mf.blocks.iter().map(|bb| bb.name.clone()).collect();
let n = block_names.len();
if n == 0 {
return Self {
idom: HashMap::new(),
dom_frontier: HashMap::new(),
dom_tree_children: HashMap::new(),
};
}
let mut idx: HashMap<String, usize> = block_names
.iter()
.enumerate()
.map(|(i, name)| (name.clone(), i))
.collect();
let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
for bb in &mf.blocks {
let from_idx = idx[&bb.name];
for &succ_idx in &bb.successors {
preds[succ_idx].push(from_idx);
}
}
let entry = idx[entry_name];
let mut doms: Vec<Option<usize>> = vec![None; n];
doms[entry] = Some(entry);
let mut changed = true;
while changed {
changed = false;
for i in 0..n {
if i == entry {
continue;
}
let mut new_idom: Option<usize> = None;
for &p in &preds[i] {
if doms[p].is_some() {
new_idom = Some(match new_idom {
None => p,
Some(cur) => Self::intersect(cur, p, &doms),
});
}
}
if doms[i] != new_idom {
doms[i] = new_idom;
changed = true;
}
}
}
let mut idom: HashMap<String, String> = HashMap::new();
let mut children: HashMap<String, Vec<String>> = HashMap::new();
for i in 0..n {
if let Some(d) = doms[i] {
if d != i {
let parent = block_names[d].clone();
let child = block_names[i].clone();
idom.insert(child.clone(), parent.clone());
children.entry(parent).or_default().push(child);
}
}
}
Self {
idom,
dom_frontier: HashMap::new(),
dom_tree_children: children,
}
}
fn intersect(b1: usize, b2: usize, doms: &[Option<usize>]) -> usize {
let mut finger1 = b1;
let mut finger2 = b2;
while finger1 != finger2 {
while finger1 > finger2 {
finger1 = doms[finger1].unwrap_or(finger1);
}
while finger2 > finger1 {
finger2 = doms[finger2].unwrap_or(finger2);
}
}
finger1
}
pub fn dominates(&self, a: &str, b: &str) -> bool {
if a == b {
return true;
}
let mut current = b.to_string();
loop {
match self.idom.get(¤t) {
Some(idom) if idom == a => return true,
Some(idom) => current = idom.clone(),
None => return false,
}
}
}
}
#[cfg(test)]
mod additional_tests {
use super::*;
use crate::codegen::MachineBasicBlock;
fn make_instr(opcode: u32, def: Option<u32>, uses: &[u32]) -> MachineInstr {
let mut mi = MachineInstr::new(opcode);
if let Some(d) = def {
mi.def = Some(d);
}
for &u in uses {
mi.push_reg(u);
}
mi
}
fn make_block(name: &str, instrs: Vec<MachineInstr>, succs: Vec<usize>) -> MachineBasicBlock {
MachineBasicBlock {
id: 0,
name: name.into(),
instructions: instrs,
successors: succs,
predecessors: Vec::new(),
is_entry: false,
}
}
fn make_function(name: &str, blocks: Vec<MachineBasicBlock>) -> MachineFunction {
MachineFunction {
name: name.into(),
blocks,
virt_reg_counter: 100,
}
}
#[test]
fn test_subtarget_skylake() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::SkylakeClient);
assert_eq!(m.dispatch_width, 6);
assert!(m.zero_idiom_elimination);
assert!(m.supports_macro_fusion(9, 30));
}
#[test]
fn test_subtarget_icelake() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::IceLakeClient);
assert!(m.div_latency_32 < 26);
assert!(m.fast_gather);
}
#[test]
fn test_subtarget_alder_lake() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::AlderLakeP);
assert!(m.ones_idiom_elimination);
assert!(m.avx512_downclock);
assert!(m.supports_macro_fusion(7, 30));
}
#[test]
fn test_subtarget_zen4() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::Zen4);
assert_eq!(m.dispatch_width, 6);
assert!(!m.micro_fusion_capable);
assert!(m.supports_macro_fusion(9, 30));
}
#[test]
fn test_subtarget_zen5() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::Zen5);
assert_eq!(m.dispatch_width, 8);
assert!(m.ones_idiom_elimination);
}
#[test]
fn test_subtarget_generic() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::Generic);
assert_eq!(m.dispatch_width, 4);
assert!(m.partial_reg_stall);
}
#[test]
fn test_subtarget_div_latency() {
let m = X86SchedSubtargetModel::from_kind(X86SchedModelKind::SkylakeClient);
assert_eq!(m.get_div_latency(false), 26);
assert_eq!(m.get_div_latency(true), 42);
assert_eq!(m.get_div_throughput(false), 6);
assert_eq!(m.get_div_throughput(true), 10);
}
#[test]
fn test_region_new() {
let region = X86SchedRegion::new();
assert_eq!(region.total_nodes(), 0);
assert_eq!(region.total_blocks(), 0);
}
#[test]
fn test_cost_model_default() {
let cm = X86SchedCostModel::default_model();
let cost = cm.estimate_cost(10, 2, 1, 0, 2, 0, 1);
assert!((cost - 42.5).abs() < 0.01);
}
#[test]
fn test_cost_model_compare() {
let cm = X86SchedCostModel::default_model();
let ord = cm.compare_schedules(10, 0, 0, 0, 0, 12, 0, 0, 0, 0);
assert_eq!(ord, Ordering::Less);
}
#[test]
fn test_cycle_timer_basic() {
let mut ct = X86SchedCycleTimer::new();
ct.record_issue(0);
ct.advance();
ct.record_issue(1);
assert_eq!(ct.current_cycle, 1);
assert_eq!(ct.issue_events.len(), 2);
}
#[test]
fn test_cycle_timer_utilization() {
let mut ct = X86SchedCycleTimer::new();
for i in 0..5 {
ct.record_issue(i);
ct.advance();
}
assert!((ct.utilization() - 1.0).abs() < 0.01);
}
#[test]
fn test_cycle_timer_stall_rate() {
let mut ct = X86SchedCycleTimer::new();
ct.record_issue(0);
ct.advance();
ct.record_stall();
ct.advance();
ct.record_issue(1);
ct.advance();
assert!((ct.stall_rate() - 1.0 / 3.0).abs() < 0.01);
}
#[test]
fn test_cycle_timer_reset() {
let mut ct = X86SchedCycleTimer::new();
ct.record_issue(0);
ct.advance();
ct.reset();
assert_eq!(ct.current_cycle, 0);
assert!(ct.issue_events.is_empty());
}
#[test]
fn test_comparison_a_wins() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let cmp = X86SchedComparison::compare("List", &[0, 1], 2, "ILP", &[0, 1], 3, &dag);
assert_eq!(cmp.winner, Some("List".to_string()));
}
#[test]
fn test_comparison_display() {
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let cmp = X86SchedComparison::compare("A", &[0], 1, "B", &[0], 2, &dag);
let s = format!("{}", cmp);
assert!(s.contains("A"));
assert!(s.contains("B"));
assert!(s.contains("Winner"));
}
#[test]
fn test_heuristics_default() {
let h = X86SchedHeuristics::default();
assert_eq!(h.critical_path_weight, 1.0);
assert_eq!(h.load_cluster_distance, 3);
}
#[test]
fn test_loop_analyzer_simple() {
let block_a = make_block(
"header",
vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(30, None, &[]),
],
vec!["header".into()],
);
let mf = make_function("test", vec![block_a]);
let la = X86SchedLoopAnalyzer::analyze(&mf, "header");
assert_eq!(la.loop_header, "header");
assert!(la.body_instructions >= 2);
assert!(!la.has_function_calls);
}
#[test]
fn test_loop_analyzer_profitable() {
let mut instrs = Vec::new();
for i in 0..10u32 {
instrs.push(make_instr(1, Some(i), &[i + 10]));
}
let block = make_block("loop", instrs, vec!["loop".into()]);
let mf = make_function("test", vec![block]);
let la = X86SchedLoopAnalyzer::analyze(&mf, "loop");
assert!(la.profitable_for_pipelining);
assert!(la.profitable_for_unrolling);
}
#[test]
fn test_mutation_preserves_length() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
make_instr(1, Some(3), &[2, 14]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mutator = X86SchedMutation::new(2, 0.5);
let original: Vec<usize> = vec![0, 1, 2, 3];
let mutated = mutator.mutate(&original, &dag);
assert_eq!(mutated.len(), 4);
}
#[test]
fn test_mutation_respects_deps() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mutator = X86SchedMutation::new(2, 1.0);
let schedule: Vec<usize> = vec![0, 1, 2];
let mutated = mutator.mutate(&schedule, &dag);
let pos0 = mutated.iter().position(|&x| x == 0).unwrap();
let pos1 = mutated.iter().position(|&x| x == 1).unwrap();
assert!(pos0 < pos1);
}
#[test]
fn test_pgo_record() {
let mut pgo = X86SchedProfileGuided::new();
pgo.record_block_execution("entry", 100);
pgo.record_edge_taken("entry", "loop", 90);
assert_eq!(pgo.get_block_frequency("entry"), 100);
assert_eq!(pgo.get_edge_frequency("entry", "loop"), 90);
}
#[test]
fn test_pgo_hot_blocks() {
let mut pgo = X86SchedProfileGuided::new();
pgo.record_block_execution("hot", 90);
pgo.record_block_execution("cold", 10);
let hot = pgo.hot_blocks(80.0);
assert!(hot.contains(&"hot".to_string()));
assert!(!hot.contains(&"cold".to_string()));
}
#[test]
fn test_pgo_classify_all() {
let mut pgo = X86SchedProfileGuided::new();
pgo.record_block_execution("hot", 90);
pgo.record_block_execution("cold", 10);
pgo.record_edge_taken("hot", "hot", 80);
pgo.record_edge_taken("hot", "cold", 20);
pgo.classify_all(50.0);
let hot_profile = pgo.block_profiles.get("hot").unwrap();
assert!(hot_profile.is_hot);
let cold_profile = pgo.block_profiles.get("cold").unwrap();
assert!(!cold_profile.is_hot);
}
#[test]
fn test_dominators_simple() {
let entry = make_block(
"entry",
vec![make_instr(1, Some(0), &[1])],
vec!["A".into(), "B".into()],
);
let a = make_block("A", vec![make_instr(1, Some(1), &[0])], vec!["C".into()]);
let b = make_block("B", vec![make_instr(1, Some(2), &[0])], vec!["C".into()]);
let c = make_block("C", vec![make_instr(1, Some(3), &[1, 2])], vec![]);
let mf = make_function("test", vec![entry, a, b, c]);
let doms = X86SchedDominators::compute(&mf, "entry");
assert!(doms.dominates("entry", "entry"));
assert!(doms.dominates("entry", "A"));
assert!(doms.dominates("entry", "C"));
}
#[test]
fn test_dominators_dom_tree() {
let entry = make_block(
"entry",
vec![make_instr(1, Some(0), &[1])],
vec!["body".into()],
);
let body = make_block(
"body",
vec![make_instr(1, Some(1), &[0])],
vec!["exit".into()],
);
let exit = make_block("exit", vec![make_instr(1, Some(2), &[0])], vec![]);
let mf = make_function("test", vec![entry, body, exit]);
let doms = X86SchedDominators::compute(&mf, "entry");
assert!(doms.dominates("entry", "body"));
assert!(doms.dominates("entry", "exit"));
assert!(doms.dominates("body", "exit"));
}
#[test]
fn test_full_pipeline_with_subtarget() {
let model = X86ExtendedSchedModel::skylake_client();
let sub = X86SchedSubtargetModel::from_kind(X86SchedModelKind::SkylakeClient);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(9, None, &[1, 13]),
make_instr(30, None, &[]),
];
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, false);
assert!(sub.supports_macro_fusion(9, 30));
let mut sched = X86SchedulerFull::for_cpu("skylake");
let block = make_block("entry", instrs, vec![]);
let mut mf = make_function("test", vec![block]);
sched.run_full_pipeline(&mut mf);
}
#[test]
fn test_cost_model_with_schedule() {
let model = X86ExtendedSchedModel::skylake_client();
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, false);
let mut s1 = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let schedule1 = s1.schedule(&dag, Some(&model.base));
let cycles1 = s1.total_cycles;
let mut s2 =
X86SchedStrategy::new(X86SchedStrategyKind::ILP, X86SchedPriorityKind::BalancedILP);
let schedule2 = s2.schedule(&dag, Some(&model.base));
let cycles2 = s2.total_cycles;
let cm = X86SchedCostModel::default_model();
let cmp = X86SchedComparison::compare(
"List", &schedule1, cycles1, "ILP", &schedule2, cycles2, &dag,
);
let _ = format!("{}", cmp);
}
#[test]
fn test_dominator_scheduling_region() {
let entry = make_block(
"entry",
vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
],
vec!["body".into(), "exit".into()],
);
let body = make_block(
"body",
vec![make_instr(1, Some(2), &[1, 13])],
vec!["exit".into()],
);
let exit = make_block("exit", vec![make_instr(1, Some(3), &[2, 14])], vec![]);
let mf = make_function("test", vec![entry, body, exit]);
let doms = X86SchedDominators::compute(&mf, "entry");
assert!(doms.dominates("entry", "exit"));
}
#[test]
fn test_mutation_stress() {
let n = 20;
let mut instrs = Vec::new();
for i in 0..n {
let uses = if i > 0 {
vec![(i - 1) as u32, (i + 100) as u32]
} else {
vec![100, 101]
};
instrs.push(make_instr(1, Some(i as u32), &uses));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut mutator = X86SchedMutation::new(3, 0.3);
let schedule: Vec<usize> = (0..n).collect();
for _ in 0..10 {
let mutated = mutator.mutate(&schedule, &dag);
assert_eq!(mutated.len(), n);
for i in 0..n {
for &pred in &dag.nodes[i].preds {
let pi = mutated.iter().position(|&x| x == pred).unwrap();
let ii = mutated.iter().position(|&x| x == i).unwrap();
assert!(
pi < ii,
"Dependence violated: {} must come before {}",
pred,
i
);
}
}
}
}
#[test]
fn test_loop_analyzer_complex() {
let header = make_block(
"header",
vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(9, None, &[0, 12]),
make_instr(30, None, &[]),
],
vec!["body".into(), "exit".into()],
);
let body = make_block(
"body",
vec![
make_instr(1, Some(1), &[0, 13]),
make_instr(2, Some(2), &[14]),
make_instr(1, Some(3), &[2, 15]),
],
vec!["header".into()],
);
let exit = make_block("exit", vec![make_instr(1, Some(4), &[0, 16])], vec![]);
let mf = make_function("loop_test", vec![header, body, exit]);
let la = X86SchedLoopAnalyzer::analyze(&mf, "header");
assert!(la.body_instructions >= 5);
assert!(!la.has_function_calls);
}
}
#[derive(Debug, Clone)]
pub struct X86SchedAutoStrategy {
pub selected_strategy: X86SchedStrategyKind,
pub selected_priority: X86SchedPriorityKind,
pub reasoning: Vec<String>,
}
impl X86SchedAutoStrategy {
pub fn select(
dag: &X86SchedDAG,
model: &X86ExtendedSchedModel,
loop_info: Option<&X86SchedLoopAnalyzer>,
profile: Option<&X86BlockProfile>,
) -> Self {
let n = dag.node_count;
let mut reasoning = Vec::new();
if let Some(loop_info) = loop_info {
if loop_info.profitable_for_pipelining && n >= 4 {
reasoning.push("Loop body: modulo scheduling".into());
return Self {
selected_strategy: X86SchedStrategyKind::Modulo,
selected_priority: X86SchedPriorityKind::CriticalPath,
reasoning,
};
}
}
if let Some(profile) = profile {
if profile.is_hot && n >= 4 {
reasoning.push("Hot block: trace scheduling".into());
return Self {
selected_strategy: X86SchedStrategyKind::Trace,
selected_priority: X86SchedPriorityKind::LatencyWeighted,
reasoning,
};
}
}
if !model.base.machine.out_of_order {
reasoning.push("In-order core: VLIW bundling".into());
return Self {
selected_strategy: X86SchedStrategyKind::VLIW,
selected_priority: X86SchedPriorityKind::ResourceCritical,
reasoning,
};
}
let avg_succs: f64 = dag
.nodes
.iter()
.map(|nd| nd.succs.len() as f64)
.sum::<f64>()
/ n.max(1) as f64;
let avg_latency: f64 =
dag.nodes.iter().map(|nd| nd.latency as f64).sum::<f64>() / n.max(1) as f64;
if avg_succs < 1.0 && n > 4 {
reasoning.push(format!("Low fanout ({:.2}): source scheduling", avg_succs));
Self {
selected_strategy: X86SchedStrategyKind::Source,
selected_priority: X86SchedPriorityKind::CriticalPath,
reasoning,
}
} else if n <= 8 {
reasoning.push("Small block: hybrid scheduling".into());
Self {
selected_strategy: X86SchedStrategyKind::Hybrid,
selected_priority: X86SchedPriorityKind::BalancedILP,
reasoning,
}
} else if avg_latency > 3.0 {
reasoning.push(format!(
"High avg latency ({:.2}): ILP scheduling",
avg_latency
));
Self {
selected_strategy: X86SchedStrategyKind::ILP,
selected_priority: X86SchedPriorityKind::LatencyWeighted,
reasoning,
}
} else {
reasoning.push("Default: list scheduling with balanced ILP priority".into());
Self {
selected_strategy: X86SchedStrategyKind::List,
selected_priority: X86SchedPriorityKind::BalancedILP,
reasoning,
}
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedFuzzer {
pub iterations: usize,
pub violations: Vec<X86SchedViolation>,
pub passed: usize,
pub failed: usize,
}
#[derive(Debug, Clone)]
pub enum X86SchedViolation {
MissingInstruction(SchedNodeId, X86SchedStrategyKind),
DuplicateInstruction(SchedNodeId, X86SchedStrategyKind),
DependenceViolation {
pred: SchedNodeId,
succ: SchedNodeId,
pred_pos: usize,
succ_pos: usize,
strategy: X86SchedStrategyKind,
},
WrongLength {
expected: usize,
actual: usize,
strategy: X86SchedStrategyKind,
},
}
impl fmt::Display for X86SchedViolation {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
X86SchedViolation::MissingInstruction(nid, strat) => {
write!(f, "Missing instruction {} in {:?} schedule", nid, strat)
}
X86SchedViolation::DuplicateInstruction(nid, strat) => {
write!(f, "Duplicate instruction {} in {:?} schedule", nid, strat)
}
X86SchedViolation::DependenceViolation {
pred,
succ,
pred_pos,
succ_pos,
strategy,
} => write!(
f,
"Dependence violated: {}→{} (pos {} before {}) in {:?}",
pred, succ, pred_pos, succ_pos, strategy
),
X86SchedViolation::WrongLength {
expected,
actual,
strategy,
} => write!(
f,
"Wrong schedule length: expected {}, got {} in {:?}",
expected, actual, strategy
),
}
}
}
impl X86SchedFuzzer {
pub fn new(iterations: usize) -> Self {
Self {
iterations,
violations: Vec::new(),
passed: 0,
failed: 0,
}
}
pub fn fuzz_all(&mut self, dag: &X86SchedDAG, model: Option<&SchedModel>) {
let strategies = [
X86SchedStrategyKind::List,
X86SchedStrategyKind::Source,
X86SchedStrategyKind::Hybrid,
X86SchedStrategyKind::ILP,
X86SchedStrategyKind::VLIW,
X86SchedStrategyKind::Trace,
];
let priorities = [
X86SchedPriorityKind::CriticalPath,
X86SchedPriorityKind::LatencyWeighted,
X86SchedPriorityKind::ResourceCritical,
X86SchedPriorityKind::RegPressure,
X86SchedPriorityKind::BalancedILP,
];
for &strat in &strategies {
for &pri in &priorities {
let mut s = X86SchedStrategy::new(strat, pri);
let schedule = s.schedule(dag, model);
match self.verify_schedule(&schedule, dag, strat) {
Ok(()) => self.passed += 1,
Err(v) => {
self.violations.push(v);
self.failed += 1;
}
}
}
}
}
pub fn verify_schedule(
&self,
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
strategy: X86SchedStrategyKind,
) -> Result<(), X86SchedViolation> {
let n = dag.node_count;
if schedule.len() != n {
return Err(X86SchedViolation::WrongLength {
expected: n,
actual: schedule.len(),
strategy,
});
}
let mut seen = HashSet::new();
for &nid in schedule {
if nid < n {
if !seen.insert(nid) {
return Err(X86SchedViolation::DuplicateInstruction(nid, strategy));
}
}
}
for i in 0..n {
if !seen.contains(&i) {
return Err(X86SchedViolation::MissingInstruction(i, strategy));
}
}
let mut positions: Vec<usize> = vec![0; n];
for (pos, &nid) in schedule.iter().enumerate() {
if nid < n {
positions[nid] = pos;
}
}
for i in 0..n {
for &pred in &dag.nodes[i].preds {
if positions[pred] >= positions[i] {
return Err(X86SchedViolation::DependenceViolation {
pred,
succ: i,
pred_pos: positions[pred],
succ_pos: positions[i],
strategy,
});
}
}
}
Ok(())
}
pub fn report(&self) -> String {
let mut out = format!(
"X86SchedFuzzer Report: {} passed, {} failed, {} violations\n",
self.passed,
self.failed,
self.violations.len()
);
for v in &self.violations {
out.push_str(&format!(" - {}\n", v));
}
out
}
}
#[derive(Debug, Clone)]
pub struct X86SchedInstrumentation {
pub enabled: bool,
pub events: Vec<X86SchedEvent>,
pub counters: HashMap<String, u64>,
}
#[derive(Debug, Clone)]
pub enum X86SchedEvent {
NodeScheduled {
node_id: SchedNodeId,
cycle: SchedCycle,
strategy: String,
priority: i64,
},
Stall {
cycle: SchedCycle,
reason: String,
},
ResourceConflict {
cycle: SchedCycle,
resource: ProcResource,
requested_by: SchedNodeId,
},
FusionDetected {
first: SchedNodeId,
second: SchedNodeId,
},
FusionPlaced {
first: SchedNodeId,
second: SchedNodeId,
},
AntiDepBroken {
from: SchedNodeId,
to: SchedNodeId,
new_reg: Option<SchedReg>,
},
NopInserted {
at_position: usize,
reason: String,
},
BundleFormed {
cycle: SchedCycle,
node_ids: Vec<SchedNodeId>,
},
SpillAvoided {
reg: SchedReg,
at_node: SchedNodeId,
},
LoadClustered {
load: SchedNodeId,
use_node: SchedNodeId,
distance: usize,
},
}
impl X86SchedInstrumentation {
pub fn new(enabled: bool) -> Self {
Self {
enabled,
events: Vec::new(),
counters: HashMap::new(),
}
}
pub fn record(&mut self, event: X86SchedEvent) {
if !self.enabled {
return;
}
self.events.push(event);
}
pub fn increment_counter(&mut self, name: &str) {
*self.counters.entry(name.to_string()).or_default() += 1;
}
pub fn get_counter(&self, name: &str) -> u64 {
self.counters.get(name).copied().unwrap_or(0)
}
pub fn events_by_type(&self, filter: &str) -> Vec<&X86SchedEvent> {
self.events
.iter()
.filter(|e| {
let s = format!("{:?}", e);
s.contains(filter)
})
.collect()
}
pub fn summary(&self) -> String {
let mut out = String::from("X86SchedInstrumentation Summary:\n");
out.push_str(&format!(" Total events: {}\n", self.events.len()));
out.push_str(" Counters:\n");
for (k, v) in &self.counters {
out.push_str(&format!(" {}: {}\n", k, v));
}
let mut event_counts: HashMap<String, usize> = HashMap::new();
for e in &self.events {
let type_name = match e {
X86SchedEvent::NodeScheduled { .. } => "NodeScheduled",
X86SchedEvent::Stall { .. } => "Stall",
X86SchedEvent::ResourceConflict { .. } => "ResourceConflict",
X86SchedEvent::FusionDetected { .. } => "FusionDetected",
X86SchedEvent::FusionPlaced { .. } => "FusionPlaced",
X86SchedEvent::AntiDepBroken { .. } => "AntiDepBroken",
X86SchedEvent::NopInserted { .. } => "NopInserted",
X86SchedEvent::BundleFormed { .. } => "BundleFormed",
X86SchedEvent::SpillAvoided { .. } => "SpillAvoided",
X86SchedEvent::LoadClustered { .. } => "LoadClustered",
};
*event_counts.entry(type_name.to_string()).or_default() += 1;
}
out.push_str(" By event type:\n");
for (k, v) in &event_counts {
out.push_str(&format!(" {}: {}\n", k, v));
}
out
}
pub fn reset(&mut self) {
self.events.clear();
self.counters.clear();
}
}
#[derive(Debug, Clone)]
pub struct X86SchedTuning {
pub best_heuristics: X86SchedHeuristics,
pub best_cost: f64,
pub evaluations: usize,
pub history: Vec<(X86SchedHeuristics, f64)>,
}
impl X86SchedTuning {
pub fn new() -> Self {
Self {
best_heuristics: X86SchedHeuristics::default(),
best_cost: f64::MAX,
evaluations: 0,
history: Vec::new(),
}
}
pub fn grid_search(
&mut self,
dag: &X86SchedDAG,
model: &X86ExtendedSchedModel,
) -> X86SchedHeuristics {
let cp_weights = [0.5, 1.0, 1.5, 2.0];
let rp_weights = [0.0, 0.5, 1.0];
let ilp_weights = [0.1, 0.3, 0.5];
for &cp_w in &cp_weights {
for &rp_w in &rp_weights {
for &ilp_w in &ilp_weights {
let heur = X86SchedHeuristics {
critical_path_weight: cp_w,
register_pressure_weight: rp_w,
ilp_weight: ilp_w,
..X86SchedHeuristics::default()
};
let mut strat = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::BalancedILP,
);
let schedule = strat.schedule(dag, Some(&model.base));
let cycles = strat.total_cycles;
let cost = cycles as f64;
self.evaluations += 1;
self.history.push((heur.clone(), cost));
if cost < self.best_cost {
self.best_cost = cost;
self.best_heuristics = heur;
}
}
}
}
self.best_heuristics.clone()
}
}
#[derive(Debug, Clone)]
pub struct X86SchedBloatEstimator {
pub original_size_bytes: usize,
pub estimated_size_bytes: usize,
pub nop_bytes: usize,
pub copy_bytes: usize,
pub padding_bytes: usize,
}
impl X86SchedBloatEstimator {
pub fn new() -> Self {
Self {
original_size_bytes: 0,
estimated_size_bytes: 0,
nop_bytes: 0,
copy_bytes: 0,
padding_bytes: 0,
}
}
pub fn estimate_schedule(
&mut self,
instructions: &[MachineInstr],
schedule: &[SchedNodeId],
dag: &X86SchedDAG,
post_ra: &X86PostRAScheduler,
) {
self.original_size_bytes = instructions
.iter()
.map(|mi| {
1 + mi.operands.len() })
.sum();
let mut est = 0usize;
for &nid in schedule {
if nid < dag.node_count {
let mi = &instructions[nid];
est += 1 + mi.operands.len();
} else {
est += 1;
self.nop_bytes += 1;
}
}
if post_ra.break_anti_deps {
let anti_edges = dag
.edges
.iter()
.filter(|e| e.kind == X86EdgeKind::Anti)
.count();
self.copy_bytes = anti_edges * 3; est += self.copy_bytes;
}
self.estimated_size_bytes = est;
}
pub fn bloat_ratio(&self) -> f64 {
if self.original_size_bytes == 0 {
return 1.0;
}
self.estimated_size_bytes as f64 / self.original_size_bytes as f64
}
pub fn is_acceptable(&self, max_bloat: f64) -> bool {
self.bloat_ratio() <= max_bloat
}
}
#[derive(Debug, Clone)]
pub struct X86SchedPortPressureAnalyzer {
pub port_usage: HashMap<ProcResource, u32>,
pub total_uops: u32,
pub bottleneck_port: Option<ProcResource>,
pub bottleneck_utilization: f64,
}
impl X86SchedPortPressureAnalyzer {
pub fn analyze(dag: &X86SchedDAG, model: &X86ExtendedSchedModel) -> Self {
let mut port_usage: HashMap<ProcResource, u32> = HashMap::new();
let mut total_uops = 0u32;
for node in &dag.nodes {
for itin in &model.base.itineraries {
if itin.opcode == node.opcode {
total_uops += itin.uops;
for wr in &itin.write_resources {
*port_usage.entry(wr.resource).or_default() += wr.cycles;
}
break;
}
}
}
let (bottleneck_port, bottleneck_utilization) = port_usage
.iter()
.map(|(res, usage)| {
let count = model.get_resource_count(*res) as f64;
let util = *usage as f64 / count;
(*res, util)
})
.max_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal))
.unwrap_or((ProcResource::Port0, 0.0));
Self {
port_usage,
total_uops,
bottleneck_port: Some(bottleneck_port),
bottleneck_utilization,
}
}
pub fn report(&self) -> String {
let mut out = String::from("Port Pressure Analysis:\n");
out.push_str(&format!(" Total uops: {}\n", self.total_uops));
let mut entries: Vec<_> = self.port_usage.iter().collect();
entries.sort_by_key(|&(_, &u)| -(u as i64));
for (res, usage) in entries {
out.push_str(&format!(" {:?}: {} cycles\n", res, usage));
}
if let Some(bp) = self.bottleneck_port {
out.push_str(&format!(
" Bottleneck: {:?} ({:.1}% utilization)\n",
bp,
self.bottleneck_utilization * 100.0
));
}
out
}
}
#[derive(Debug, Clone)]
pub struct X86SchedEnergyEstimator {
pub high_power_opcodes: HashSet<u32>,
pub peak_power_budget: f64,
pub sustained_power_budget: f64,
pub burst_strategy: bool,
}
impl X86SchedEnergyEstimator {
pub fn new() -> Self {
let mut high_power = HashSet::new();
for op in &[400, 401, 402, 403, 404, 500, 501] {
high_power.insert(*op);
}
Self {
high_power_opcodes: high_power,
peak_power_budget: 250.0,
sustained_power_budget: 125.0,
burst_strategy: false,
}
}
pub fn is_high_power(&self, opcode: u32) -> bool {
self.high_power_opcodes.contains(&opcode)
}
pub fn high_power_density(&self, dag: &X86SchedDAG) -> f64 {
let total = dag.node_count.max(1) as f64;
let hp = dag
.nodes
.iter()
.filter(|n| self.is_high_power(n.opcode))
.count() as f64;
hp / total
}
pub fn should_burst(&self, dag: &X86SchedDAG) -> bool {
self.high_power_density(dag) > 0.3
}
}
#[cfg(test)]
mod final_tests {
use super::*;
use crate::codegen::MachineBasicBlock;
use std::collections::HashMap;
fn make_instr(opcode: u32, def: Option<u32>, uses: &[u32]) -> MachineInstr {
let mut mi = MachineInstr::new(opcode);
if let Some(d) = def {
mi.def = Some(d);
}
for &u in uses {
mi.push_reg(u);
}
mi
}
fn make_block(name: &str, instrs: Vec<MachineInstr>, succs: Vec<usize>) -> MachineBasicBlock {
MachineBasicBlock {
id: 0,
name: name.into(),
instructions: instrs,
successors: succs,
predecessors: Vec::new(),
is_entry: false,
}
}
fn make_function(name: &str, blocks: Vec<MachineBasicBlock>) -> MachineFunction {
MachineFunction {
name: name.into(),
blocks,
virt_reg_counter: 100,
}
}
#[test]
fn test_auto_strategy_loop() {
let instrs: Vec<MachineInstr> = (0..8)
.map(|i| make_instr(1, Some(i), &[i + 10, i + 11]))
.collect();
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let block = make_block("loop", instrs, vec!["loop".into()]);
let mf = make_function("test", vec![block]);
let loop_info = X86SchedLoopAnalyzer::analyze(&mf, "loop");
let sel = X86SchedAutoStrategy::select(&dag, &model, Some(&loop_info), None);
assert!(sel
.reasoning
.iter()
.any(|r| r.contains("modulo") || r.contains("Loop")));
}
#[test]
fn test_auto_strategy_hot() {
let instrs: Vec<MachineInstr> = (0..10)
.map(|i| make_instr(1, Some(i), &[i + 10, i + 11]))
.collect();
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let mut profile = X86BlockProfile::new();
profile.exec_count = 1000;
profile.classify(500);
let sel = X86SchedAutoStrategy::select(&dag, &model, None, Some(&profile));
assert!(profile.is_hot);
}
#[test]
fn test_auto_strategy_small_block() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let sel = X86SchedAutoStrategy::select(&dag, &model, None, None);
assert!(matches!(
sel.selected_strategy,
X86SchedStrategyKind::Hybrid
| X86SchedStrategyKind::List
| X86SchedStrategyKind::Source
));
}
#[test]
fn test_fuzzer_all_pass_linear() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut fuzzer = X86SchedFuzzer::new(1);
fuzzer.fuzz_all(&dag, None);
assert_eq!(fuzzer.failed, 0);
}
#[test]
fn test_fuzzer_all_pass_parallel() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[12, 13]),
make_instr(1, Some(2), &[14, 15]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut fuzzer = X86SchedFuzzer::new(1);
fuzzer.fuzz_all(&dag, None);
assert_eq!(fuzzer.failed, 0);
}
#[test]
fn test_fuzzer_report() {
let dag = X86SchedDAG::new();
let fuzzer = X86SchedFuzzer::new(0);
let report = fuzzer.report();
assert!(report.contains("passed"));
}
#[test]
fn test_fuzzer_verify_correct_schedule() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let fuzzer = X86SchedFuzzer::new(0);
let result = fuzzer.verify_schedule(&[0, 1], &dag, X86SchedStrategyKind::List);
assert!(result.is_ok());
}
#[test]
fn test_fuzzer_violation_wrong_length() {
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let fuzzer = X86SchedFuzzer::new(0);
let result = fuzzer.verify_schedule(&[0, 1], &dag, X86SchedStrategyKind::List);
assert!(result.is_err());
}
#[test]
fn test_fuzzer_violation_display() {
let v = X86SchedViolation::DependenceViolation {
pred: 0,
succ: 1,
pred_pos: 2,
succ_pos: 1,
strategy: X86SchedStrategyKind::List,
};
let s = format!("{}", v);
assert!(s.contains("Dependence violated"));
}
#[test]
fn test_instrumentation_record() {
let mut instr = X86SchedInstrumentation::new(true);
instr.record(X86SchedEvent::NodeScheduled {
node_id: 0,
cycle: 0,
strategy: "List".into(),
priority: 100,
});
instr.increment_counter("nodes_scheduled");
assert_eq!(instr.events.len(), 1);
assert_eq!(instr.get_counter("nodes_scheduled"), 1);
}
#[test]
fn test_instrumentation_disabled() {
let mut instr = X86SchedInstrumentation::new(false);
instr.record(X86SchedEvent::Stall {
cycle: 0,
reason: "test".into(),
});
assert_eq!(instr.events.len(), 0);
}
#[test]
fn test_instrumentation_types() {
let mut instr = X86SchedInstrumentation::new(true);
instr.record(X86SchedEvent::FusionDetected {
first: 0,
second: 1,
});
instr.record(X86SchedEvent::FusionPlaced {
first: 0,
second: 1,
});
instr.record(X86SchedEvent::LoadClustered {
load: 0,
use_node: 1,
distance: 2,
});
let fusions = instr.events_by_type("Fusion");
assert_eq!(fusions.len(), 2);
}
#[test]
fn test_instrumentation_summary() {
let mut instr = X86SchedInstrumentation::new(true);
instr.record(X86SchedEvent::NopInserted {
at_position: 0,
reason: "align".into(),
});
instr.record(X86SchedEvent::BundleFormed {
cycle: 0,
node_ids: vec![0, 1],
});
instr.increment_counter("test_counter");
let summary = instr.summary();
assert!(summary.contains("Total events"));
assert!(summary.contains("test_counter"));
}
#[test]
fn test_instrumentation_reset() {
let mut instr = X86SchedInstrumentation::new(true);
instr.record(X86SchedEvent::Stall {
cycle: 0,
reason: "test".into(),
});
instr.reset();
assert!(instr.events.is_empty());
}
#[test]
fn test_tuning_grid_search() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let mut tuning = X86SchedTuning::new();
let best = tuning.grid_search(&dag, &model);
assert!(tuning.evaluations > 0);
assert!(best.critical_path_weight > 0.0);
}
#[test]
fn test_bloat_estimator() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let post_ra = X86PostRAScheduler::new(model);
let mut estimator = X86SchedBloatEstimator::new();
estimator.estimate_schedule(&instrs, &[0, 1], &dag, &post_ra);
assert!(estimator.original_size_bytes > 0);
assert!(estimator.bloat_ratio() >= 1.0);
}
#[test]
fn test_port_pressure_analyzer() {
let instrs: Vec<MachineInstr> = (0..10)
.map(|i| {
let mut mi = make_instr(1, Some(i), &[i + 100, i + 101]);
mi
})
.collect();
let model = X86ExtendedSchedModel::skylake_client();
let dag = X86SchedDAG::build(&instrs, Some(&model.base), None, false);
let analyzer = X86SchedPortPressureAnalyzer::analyze(&dag, &model);
assert!(analyzer.total_uops > 0);
let report = analyzer.report();
assert!(report.contains("Port Pressure"));
}
#[test]
fn test_energy_estimator() {
let ee = X86SchedEnergyEstimator::new();
assert!(ee.is_high_power(400));
assert!(!ee.is_high_power(1));
}
#[test]
fn test_energy_high_power_density() {
let mut instrs = Vec::new();
for i in 0..10u32 {
let op = if i < 5 { 400 } else { 1 };
instrs.push(make_instr(op, Some(i), &[i + 100]));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let ee = X86SchedEnergyEstimator::new();
let density = ee.high_power_density(&dag);
assert!((density - 0.5).abs() < 0.01);
}
#[test]
fn test_full_integration_all_models() {
let cpu_names = ["skylake", "ice_lake", "alder_lake", "zen4", "zen5"];
for cpu in &cpu_names {
let mut sched = X86SchedulerFull::for_cpu(cpu);
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(9, None, &[1, 13]),
make_instr(30, None, &[]),
];
let block = make_block("entry", instrs, vec![]);
let mut mf = make_function("test", vec![block]);
sched.run_full_pipeline(&mut mf);
assert!(mf.blocks[0].instructions.len() >= 3);
}
}
#[test]
fn test_stress_large_dag_all_strategies() {
let n = 100;
let mut instrs = Vec::with_capacity(n);
for i in 0..n {
let uses = if i > 0 {
vec![(i - 1) as u32, (i + 200) as u32]
} else {
vec![200, 201]
};
instrs.push(make_instr(1, Some(i as u32), &uses));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let strategy_pairs = [
(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
),
(
X86SchedStrategyKind::Source,
X86SchedPriorityKind::LatencyWeighted,
),
(
X86SchedStrategyKind::Hybrid,
X86SchedPriorityKind::BalancedILP,
),
(
X86SchedStrategyKind::ILP,
X86SchedPriorityKind::ResourceCritical,
),
(
X86SchedStrategyKind::VLIW,
X86SchedPriorityKind::RegPressure,
),
(
X86SchedStrategyKind::Trace,
X86SchedPriorityKind::CriticalPath,
),
];
for (strat, pri) in &strategy_pairs {
let mut s = X86SchedStrategy::new(*strat, *pri);
let schedule = s.schedule(&dag, None);
assert_eq!(schedule.len(), n, "Strategy {:?}/{:?} failed", strat, pri);
let fuzzer = X86SchedFuzzer::new(0);
assert!(
fuzzer.verify_schedule(&schedule, &dag, *strat).is_ok(),
"Schedule verification failed for {:?}/{:?}",
strat,
pri
);
}
}
#[test]
fn test_pipeline_resources_exhaustion() {
let model = X86ExtendedSchedModel::skylake_client();
let mut pr = X86PipelineResources::unified_intel(&model);
let node = X86SchedNode::new(0, 1);
for i in 0..pr.rob_size {
assert!(pr.allocate(i as usize, &node, 1));
}
assert!(pr.is_stalled());
assert!(!pr.allocate(999, &node, 1));
pr.retire(pr.rob_size);
assert_eq!(pr.rob_occupied, 0);
assert!(!pr.is_stalled());
}
#[test]
fn test_cost_model_edge_cases() {
let cm = X86SchedCostModel::default_model();
let cost = cm.estimate_cost(0, 0, 0, 0, 0, 0, 0);
assert_eq!(cost, 0.0);
let cost = cm.estimate_cost(1000, 100, 50, 20, 10, 5, 1);
assert!(cost > 0.0);
}
#[test]
fn test_comparison_tie() {
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let cmp = X86SchedComparison::compare("A", &[0], 1, "B", &[0], 1, &dag);
assert_eq!(cmp.winner, None);
}
#[test]
fn test_dominators_empty() {
let mf = make_function("empty", vec![]);
let doms = X86SchedDominators::compute(&mf, "entry");
assert!(doms.idom.is_empty());
}
#[test]
fn test_live_range_after_last_use() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, None, &[0, 12]), make_instr(1, Some(1), &[13, 14]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let tracker = X86LiveRangeTracker::build(&dag);
assert!(!tracker.is_live_at(SchedReg::Virt(0), 2));
}
#[test]
fn test_reservation_station_multiple_ports() {
let mut rs = X86ReservationStation::new(
"Multi",
4,
vec![
ProcResource::Port0,
ProcResource::Port1,
ProcResource::Port5,
],
1,
1,
);
assert_eq!(rs.dispatch_ports.len(), 3);
assert_eq!(rs.free_entries(), 4);
}
#[test]
fn test_lsq_forwarding_disabled() {
let mut lsq = X86LoadStoreQueue::new(72, 56);
lsq.forwarding_enabled = false;
lsq.issue_store(0, Some(SchedReg::Virt(10)), Some(SchedReg::Virt(11)), 0);
assert_eq!(lsq.check_forwarding(Some(SchedReg::Virt(10)), 0), None);
}
#[test]
fn test_mutation_empty() {
let dag = X86SchedDAG::new();
let mut mutator = X86SchedMutation::new(2, 0.5);
let result = mutator.mutate(&[], &dag);
assert!(result.is_empty());
}
#[test]
fn test_flattened_itinerary_multi_lookup() {
let model = X86ExtendedSchedModel::skylake_client();
let fi = X86FlattenedItinerary::from_model(&model.base);
for itin in &model.base.itineraries {
let _ = fi.write_resources(itin.opcode);
}
}
#[test]
fn test_dag_debug_dot_scheduled_nodes() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
];
let mut dag = X86SchedDAG::build(&instrs, None, None, false);
dag.nodes[0].scheduled = true;
let dot = X86SchedGraphDebug::to_dot(&dag, false);
assert!(dot.contains("lightgreen"));
}
#[test]
fn test_sched_quality_metrics_display_full() {
let metrics = X86SchedQualityMetrics {
total_instructions: 50,
instructions_moved: 30,
total_cycles: 15,
avg_move_distance: 5,
ilp: 3.33,
critical_path_ratio: 1.25,
critical_path_length: 12,
};
let s = format!("{}", metrics);
assert!(s.contains("50"));
assert!(s.contains("3.33"));
assert!(s.contains("1.25"));
}
#[test]
fn test_auto_strategy_reasoning_contains_selection() {
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let sel = X86SchedAutoStrategy::select(&dag, &model, None, None);
assert!(!sel.reasoning.is_empty());
}
#[test]
fn test_tuning_history_buildup() {
let instrs = vec![make_instr(1, Some(0), &[10, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let model = X86ExtendedSchedModel::skylake_client();
let mut tuning = X86SchedTuning::new();
tuning.grid_search(&dag, &model);
assert!(!tuning.history.is_empty());
assert_eq!(tuning.history.len(), tuning.evaluations);
}
#[test]
fn test_all_modules_exist() {
let _ = X86SchedulerFull::for_cpu("skylake");
let _ = X86SchedDAG::default();
let _ = X86SchedStrategy::new(
X86SchedStrategyKind::List,
X86SchedPriorityKind::CriticalPath,
);
let _ = X86SchedHazardRecognizer::new(4);
let _ = X86MacroFusionScheduling::new(true);
let _ = X86ExtendedSchedModel::skylake_client();
let _ = X86PreRAScheduler::new(X86ExtendedSchedModel::skylake_client());
let _ = X86PostRAScheduler::new(X86ExtendedSchedModel::skylake_client());
let _ = X86ReservationStation::new("test", 4, vec![ProcResource::Port0], 1, 1);
let _ = X86LiveRangeTracker::build(&X86SchedDAG::new());
let _ = X86LoadStoreQueue::new(72, 56);
let _ = X86BypassNetwork::skylake();
let _ = X86SchedGraphDebug;
let _ = X86SchedSubtargetModel::from_kind(X86SchedModelKind::SkylakeClient);
let _ = X86SchedRegion::new();
let _ = X86SchedCostModel::default_model();
let _ = X86SchedCycleTimer::new();
let _ = X86SchedHeuristics::default();
let _ = X86SchedFuzzer::new(0);
let _ = X86SchedInstrumentation::new(false);
let _ = X86SchedTuning::new();
let _ = X86SchedBloatEstimator::new();
let _ = X86SchedPortPressureAnalyzer::analyze(
&X86SchedDAG::new(),
&X86ExtendedSchedModel::skylake_client(),
);
let _ = X86SchedEnergyEstimator::new();
let _ = X86SchedProfileGuided::new();
let _ = X86SchedMutation::new(2, 0.5);
let _ = X86SchedDominators::compute(&MachineFunction::new("test"), "entry");
}
}
#[derive(Debug, Clone)]
pub struct X86SchedInterferenceGraph {
pub interferences: HashMap<SchedReg, HashSet<SchedReg>>,
pub degree: HashMap<SchedReg, usize>,
pub max_degree: usize,
}
impl X86SchedInterferenceGraph {
pub fn build(dag: &X86SchedDAG) -> Self {
let tracker = X86LiveRangeTracker::build(dag);
let mut interferences: HashMap<SchedReg, HashSet<SchedReg>> = HashMap::new();
let mut degree = HashMap::new();
for i in 0..dag.node_count {
let live = tracker.live_at(i);
let live_vec: Vec<SchedReg> = live.iter().copied().collect();
for a in 0..live_vec.len() {
for b in (a + 1)..live_vec.len() {
interferences
.entry(live_vec[a])
.or_default()
.insert(live_vec[b]);
interferences
.entry(live_vec[b])
.or_default()
.insert(live_vec[a]);
}
}
}
let mut max_degree = 0usize;
for (reg, ints) in &interferences {
let d = ints.len();
degree.insert(*reg, d);
if d > max_degree {
max_degree = d;
}
}
Self {
interferences,
degree,
max_degree,
}
}
pub fn degree_of(&self, reg: SchedReg) -> usize {
self.degree.get(®).copied().unwrap_or(0)
}
pub fn interfere(&self, a: SchedReg, b: SchedReg) -> bool {
self.interferences
.get(&a)
.map(|ints| ints.contains(&b))
.unwrap_or(false)
}
pub fn high_pressure_regs(&self, threshold: usize) -> Vec<SchedReg> {
self.degree
.iter()
.filter(|&(_, &d)| d >= threshold)
.map(|(&r, _)| r)
.collect()
}
}
#[derive(Debug, Clone)]
pub struct X86SchedReadyQueue {
heap: Vec<(i64, SchedNodeId)>,
set: HashSet<SchedNodeId>,
}
impl X86SchedReadyQueue {
pub fn new() -> Self {
Self {
heap: Vec::new(),
set: HashSet::new(),
}
}
pub fn insert(&mut self, node_id: SchedNodeId, priority: i64) {
if self.set.contains(&node_id) {
return;
}
self.set.insert(node_id);
self.heap.push((priority, node_id));
self.heap
.sort_by(|a, b| b.0.cmp(&a.0).then_with(|| a.1.cmp(&b.1)));
}
pub fn pop(&mut self) -> Option<(i64, SchedNodeId)> {
while let Some((pri, nid)) = self.heap.pop() {
if self.set.remove(&nid) {
return Some((pri, nid));
}
}
None
}
pub fn peek(&self) -> Option<(i64, SchedNodeId)> {
self.heap.last().copied()
}
pub fn contains(&self, node_id: SchedNodeId) -> bool {
self.set.contains(&node_id)
}
pub fn len(&self) -> usize {
self.set.len()
}
pub fn is_empty(&self) -> bool {
self.set.is_empty()
}
pub fn clear(&mut self) {
self.heap.clear();
self.set.clear();
}
}
#[derive(Debug, Clone)]
pub struct X86SchedCriticalPathUpdater {
pub heights: Vec<u32>,
pub updated_count: usize,
}
impl X86SchedCriticalPathUpdater {
pub fn new(dag: &X86SchedDAG) -> Self {
let heights: Vec<u32> = dag.nodes.iter().map(|n| n.height).collect();
Self {
heights,
updated_count: 0,
}
}
pub fn schedule_node(&mut self, node_id: SchedNodeId, dag: &X86SchedDAG) {
let mut worklist: Vec<SchedNodeId> = dag.nodes[node_id].preds.clone();
let mut visited = HashSet::new();
while let Some(pred) = worklist.pop() {
if !visited.insert(pred) {
continue;
}
let node = &dag.nodes[pred];
let new_height = node.latency
+ node
.succs
.iter()
.map(|&s| self.heights.get(s).copied().unwrap_or(0))
.max()
.unwrap_or(0);
if self.heights[pred] != new_height {
self.heights[pred] = new_height;
self.updated_count += 1;
worklist.extend(&node.preds);
}
}
}
pub fn get_height(&self, node_id: SchedNodeId) -> u32 {
self.heights.get(node_id).copied().unwrap_or(0)
}
}
#[derive(Debug, Clone)]
pub struct X86SchedLatencyCalculator {
pub base_latencies: HashMap<u32, u32>,
pub mem_latency: u32,
pub fp_latency_base: u32,
pub div_latency_base: u32,
pub bypass_network: X86BypassNetwork,
}
impl X86SchedLatencyCalculator {
pub fn new(model: &X86ExtendedSchedModel) -> Self {
let mut base = HashMap::new();
for itin in &model.base.itineraries {
base.insert(itin.opcode, itin.latency);
}
let bypass = match model.kind {
X86SchedModelKind::SkylakeClient => X86BypassNetwork::skylake(),
X86SchedModelKind::IceLakeClient => X86BypassNetwork::ice_lake(),
X86SchedModelKind::Zen4 => X86BypassNetwork::zen4(),
X86SchedModelKind::Zen5 => X86BypassNetwork::zen4(),
_ => X86BypassNetwork::skylake(),
};
Self {
base_latencies: base,
mem_latency: model.load_latency(),
fp_latency_base: 3,
div_latency_base: 20,
bypass_network: bypass,
}
}
pub fn latency(&self, opcode: u32) -> u32 {
self.base_latencies
.get(&opcode)
.copied()
.unwrap_or_else(|| {
if X86SchedDAG::is_load_opcode(opcode) {
self.mem_latency
} else if X86SchedDAG::is_store_opcode(opcode) {
1
} else if X86SchedDAG::is_branch_opcode(opcode) {
1
} else {
1
}
})
}
pub fn effective_latency(
&self,
opcode: u32,
from_port: Option<ProcResource>,
to_port: Option<ProcResource>,
) -> u32 {
let base = self.latency(opcode);
match (from_port, to_port) {
(Some(f), Some(t)) => {
let bypass = self.bypass_network.get_bypass(f, t);
base.saturating_sub(bypass)
}
_ => base,
}
}
}
#[derive(Debug, Clone)]
pub struct X86SchedUnroller {
pub max_unroll_factor: usize,
pub max_unrolled_size: usize,
pub unroll_count: usize,
}
impl X86SchedUnroller {
pub fn new(max_factor: usize, max_size: usize) -> Self {
Self {
max_unroll_factor: max_factor,
max_unrolled_size: max_size,
unroll_count: 0,
}
}
pub fn should_unroll(&self, loop_info: &X86SchedLoopAnalyzer) -> bool {
loop_info.profitable_for_unrolling
&& loop_info.body_instructions > 0
&& loop_info.body_instructions * 2 <= self.max_unrolled_size
}
pub fn compute_unroll_factor(&self, loop_info: &X86SchedLoopAnalyzer) -> usize {
if !self.should_unroll(loop_info) {
return 1;
}
let max_by_size = self.max_unrolled_size / loop_info.body_instructions.max(1);
let factor = self.max_unroll_factor.min(max_by_size).max(1);
let mut pow2 = 1;
while pow2 * 2 <= factor {
pow2 *= 2;
}
pow2
}
pub fn unroll_instructions(
&mut self,
instructions: &[MachineInstr],
factor: usize,
) -> Vec<MachineInstr> {
let mut result = Vec::with_capacity(instructions.len() * factor);
for i in 0..factor {
for mi in instructions {
let mut cloned = mi.clone();
if let Some(ref mut def) = cloned.def {
*def = def.wrapping_add((i as u32) * 1000);
}
for op in &mut cloned.operands {
match op {
MachineOperand::Reg(r) => {
*r = r.wrapping_add((i as u32) * 1000);
}
_ => {}
}
}
result.push(cloned);
}
}
self.unroll_count += 1;
result
}
}
#[derive(Debug, Clone)]
pub struct X86SchedSpillCodeEstimator {
pub available_regs: usize,
pub max_pressure: usize,
pub estimated_spills: usize,
pub estimated_fills: usize,
pub spill_cost_cycles: u32,
}
impl X86SchedSpillCodeEstimator {
pub fn new(available_regs: usize) -> Self {
Self {
available_regs,
max_pressure: 0,
estimated_spills: 0,
estimated_fills: 0,
spill_cost_cycles: 0,
}
}
pub fn estimate(&mut self, tracker: &X86LiveRangeTracker) {
self.max_pressure = tracker.max_live_regs;
if self.max_pressure > self.available_regs {
let excess = self.max_pressure - self.available_regs;
self.estimated_spills = excess;
self.estimated_fills = excess;
self.spill_cost_cycles = excess as u32 * 7;
} else {
self.estimated_spills = 0;
self.estimated_fills = 0;
self.spill_cost_cycles = 0;
}
}
pub fn would_spill(&self) -> bool {
self.max_pressure > self.available_regs
}
pub fn report(&self) -> String {
format!(
"Spill estimation: pressure={}/{}, spills={}, fills={}, cost={} cycles",
self.max_pressure,
self.available_regs,
self.estimated_spills,
self.estimated_fills,
self.spill_cost_cycles,
)
}
}
#[derive(Debug, Clone)]
pub struct X86SchedMicroFusionPrep {
pub enabled: bool,
pub prepared_pairs: Vec<(SchedNodeId, SchedNodeId)>,
}
impl X86SchedMicroFusionPrep {
pub fn new(enabled: bool) -> Self {
Self {
enabled,
prepared_pairs: Vec::new(),
}
}
pub fn detect_load_op_pairs(&mut self, schedule: &[SchedNodeId], dag: &X86SchedDAG) {
if !self.enabled {
return;
}
self.prepared_pairs.clear();
let n = schedule.len();
for i in 0..n.saturating_sub(1) {
let a = schedule[i];
let b = schedule[i + 1];
if a >= dag.node_count || b >= dag.node_count {
continue;
}
if dag.nodes[a].may_load
&& !dag.nodes[b].may_load
&& !dag.nodes[b].may_store
&& dag.nodes[b]
.uses
.iter()
.any(|u| dag.nodes[a].defs.contains(u))
{
self.prepared_pairs.push((a, b));
}
}
}
}
#[cfg(test)]
mod comprehensive_tests {
use super::*;
use crate::codegen::MachineBasicBlock;
fn make_instr(opcode: u32, def: Option<u32>, uses: &[u32]) -> MachineInstr {
let mut mi = MachineInstr::new(opcode);
if let Some(d) = def {
mi.def = Some(d);
}
for &u in uses {
mi.push_reg(u);
}
mi
}
fn make_block(name: &str, instrs: Vec<MachineInstr>, succs: Vec<usize>) -> MachineBasicBlock {
MachineBasicBlock {
id: 0,
name: name.into(),
instructions: instrs,
successors: succs,
predecessors: Vec::new(),
is_entry: false,
}
}
fn make_function(name: &str, blocks: Vec<MachineBasicBlock>) -> MachineFunction {
MachineFunction {
name: name.into(),
blocks,
virt_reg_counter: 100,
}
}
#[test]
fn test_interference_graph_build() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[10, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let ig = X86SchedInterferenceGraph::build(&dag);
assert!(ig.interfere(SchedReg::Virt(0), SchedReg::Virt(1)));
assert!(ig.interfere(SchedReg::Virt(1), SchedReg::Virt(0)));
assert!(ig.max_degree > 0);
}
#[test]
fn test_interference_graph_high_pressure() {
let mut instrs = Vec::new();
for i in 0..20u32 {
instrs.push(make_instr(1, Some(i), &[100 + i, 101 + i]));
}
let dag = X86SchedDAG::build(&instrs, None, None, false);
let ig = X86SchedInterferenceGraph::build(&dag);
let high = ig.high_pressure_regs(10);
assert!(!high.is_empty());
}
#[test]
fn test_ready_queue_insert_pop() {
let mut rq = X86SchedReadyQueue::new();
rq.insert(0, 100);
rq.insert(1, 200);
rq.insert(2, 50);
assert_eq!(rq.len(), 3);
let (pri, nid) = rq.pop().unwrap();
assert_eq!(nid, 1);
assert_eq!(pri, 200);
assert_eq!(rq.len(), 2);
}
#[test]
fn test_ready_queue_no_duplicates() {
let mut rq = X86SchedReadyQueue::new();
rq.insert(0, 100);
rq.insert(0, 200); assert_eq!(rq.len(), 1);
}
#[test]
fn test_ready_queue_contains() {
let mut rq = X86SchedReadyQueue::new();
rq.insert(5, 50);
assert!(rq.contains(5));
assert!(!rq.contains(6));
}
#[test]
fn test_ready_queue_clear() {
let mut rq = X86SchedReadyQueue::new();
rq.insert(0, 100);
rq.clear();
assert!(rq.is_empty());
}
#[test]
fn test_cp_updater_initial() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let updater = X86SchedCriticalPathUpdater::new(&dag);
assert_eq!(updater.get_height(0), 3);
assert_eq!(updater.get_height(1), 2);
assert_eq!(updater.get_height(2), 1);
}
#[test]
fn test_latency_calculator() {
let model = X86ExtendedSchedModel::skylake_client();
let calc = X86SchedLatencyCalculator::new(&model);
assert!(calc.latency(1) >= 1);
assert_eq!(calc.latency(99999), 1);
}
#[test]
fn test_latency_effective_with_bypass() {
let model = X86ExtendedSchedModel::skylake_client();
let calc = X86SchedLatencyCalculator::new(&model);
let eff = calc.effective_latency(1, Some(ProcResource::Port0), Some(ProcResource::Port0));
assert!(eff <= calc.latency(1));
}
#[test]
fn test_unroller_should_unroll() {
let unroller = X86SchedUnroller::new(4, 200);
let instrs: Vec<MachineInstr> = (0..8)
.map(|i| make_instr(1, Some(i), &[i + 10, i + 11]))
.collect();
let block = make_block("loop", instrs, vec!["loop".into()]);
let mf = make_function("test", vec![block]);
let loop_info = X86SchedLoopAnalyzer::analyze(&mf, "loop");
assert!(unroller.should_unroll(&loop_info));
}
#[test]
fn test_unroller_factor() {
let unroller = X86SchedUnroller::new(8, 200);
let instrs: Vec<MachineInstr> = (0..5).map(|i| make_instr(1, Some(i), &[i + 10])).collect();
let block = make_block("loop", instrs, vec!["loop".into()]);
let mf = make_function("test", vec![block]);
let loop_info = X86SchedLoopAnalyzer::analyze(&mf, "loop");
let factor = unroller.compute_unroll_factor(&loop_info);
assert!(factor >= 1);
assert!(factor <= 8);
}
#[test]
fn test_unroller_instructions() {
let mut unroller = X86SchedUnroller::new(4, 200);
let instrs = vec![make_instr(1, Some(0), &[10])];
let unrolled = unroller.unroll_instructions(&instrs, 2);
assert_eq!(unrolled.len(), 2);
assert_eq!(unrolled[0].def, Some(0));
assert_eq!(unrolled[1].def, Some(1000));
}
#[test]
fn test_spill_estimator_no_spill() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, None, &[0, 12]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let tracker = X86LiveRangeTracker::build(&dag);
let mut estimator = X86SchedSpillCodeEstimator::new(16);
estimator.estimate(&tracker);
assert!(!estimator.would_spill());
}
#[test]
fn test_spill_estimator_report() {
let mut estimator = X86SchedSpillCodeEstimator::new(16);
estimator.max_pressure = 20;
estimator.estimated_spills = 4;
estimator.spill_cost_cycles = 28;
let report = estimator.report();
assert!(report.contains("20"));
assert!(report.contains("4"));
}
#[test]
fn test_micro_fusion_prep_detect() {
let mut load = make_instr(2, Some(0), &[10]);
load.may_load = true;
let instrs = vec![load, make_instr(1, Some(1), &[0, 11])];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut prep = X86SchedMicroFusionPrep::new(true);
prep.detect_load_op_pairs(&[0, 1], &dag);
assert_eq!(prep.prepared_pairs.len(), 1);
assert_eq!(prep.prepared_pairs[0], (0, 1));
}
#[test]
fn test_micro_fusion_prep_disabled() {
let dag = X86SchedDAG::new();
let mut prep = X86SchedMicroFusionPrep::new(false);
prep.detect_load_op_pairs(&[], &dag);
assert!(prep.prepared_pairs.is_empty());
}
#[test]
fn test_end_to_end_all_cpus() {
let cpu_names = ["skylake", "ice_lake", "alder_lake", "zen4", "zen5"];
for cpu in &cpu_names {
let mut sched = X86SchedulerFull::for_cpu(cpu);
let instrs: Vec<MachineInstr> = (0..20)
.map(|i| {
let uses = if i > 0 {
vec![(i - 1) as u32 + 100, (i + 50) as u32 + 100]
} else {
vec![100, 101]
};
make_instr(1, Some(i as u32 + 100), &uses)
})
.collect();
let block = make_block("entry", instrs, vec![]);
let mut mf = make_function("test", vec![block]);
let count = sched.run_full_pipeline(&mut mf);
assert!(mf.blocks[0].instructions.len() >= 19);
}
}
#[test]
fn test_fuzzer_all_strategies_no_violations() {
let instrs = vec![
make_instr(1, Some(0), &[10, 11]),
make_instr(1, Some(1), &[0, 12]),
make_instr(1, Some(2), &[1, 13]),
make_instr(1, Some(3), &[0, 14]),
make_instr(1, Some(4), &[3, 2]),
];
let dag = X86SchedDAG::build(&instrs, None, None, false);
let mut fuzzer = X86SchedFuzzer::new(1);
fuzzer.fuzz_all(&dag, None);
assert_eq!(
fuzzer.failed, 0,
"Fuzzer violations: {:?}",
fuzzer.violations
);
}
}
#[doc(hidden)]
pub const X86_SCHEDULER_FULL_VERSION: &str = "1.0.0";
#[doc(hidden)]
pub const X86_SCHEDULER_SUPPORTED_CPUS: &[&str] = &[
"skylake",
"skylake_client",
"skl",
"ice_lake",
"icelake",
"icl",
"alder_lake",
"alderlake",
"adl",
"golden_cove",
"zen3",
"znver3",
"zen4",
"znver4",
"zen5",
"znver5",
];
#[doc(hidden)]
pub const X86_SCHEDULER_SUPPORTED_STRATEGIES: &[&str] =
&["list", "source", "hybrid", "ilp", "vliw", "trace", "modulo"];
#[doc(hidden)]
pub const X86_SCHEDULER_SUPPORTED_PRIORITIES: &[&str] = &[
"critical_path",
"latency_weighted",
"resource_critical",
"reg_pressure",
"balanced_ilp",
];
#[doc(hidden)]
pub const X86_SCHEDULER_MAX_ISSUE_WIDTH: u32 = 8;
#[doc(hidden)]
pub const X86_SCHEDULER_MAX_BUNDLE_SIZE: u32 = 4;
#[doc(hidden)]
pub const X86_SCHEDULER_DEFAULT_UNROLL_THRESHOLD: u32 = 16;
#[doc(hidden)]
pub fn x86_scheduler_full_description() -> String {
format!(
"X86SchedulerFull v{} — supports {} CPU models, {} scheduling strategies, and {} priority functions.\n\
Maximum issue width: {}, maximum bundle size: {}, default unroll threshold: {}.",
X86_SCHEDULER_FULL_VERSION,
X86_SCHEDULER_SUPPORTED_CPUS.len(),
X86_SCHEDULER_SUPPORTED_STRATEGIES.len(),
X86_SCHEDULER_SUPPORTED_PRIORITIES.len(),
X86_SCHEDULER_MAX_ISSUE_WIDTH,
X86_SCHEDULER_MAX_BUNDLE_SIZE,
X86_SCHEDULER_DEFAULT_UNROLL_THRESHOLD,
)
}
#[test]
fn test_scheduler_full_description() {
let desc = x86_scheduler_full_description();
assert!(desc.contains("X86SchedulerFull"));
assert!(desc.contains("CPU models"));
assert!(desc.contains("strategies"));
}
#[test]
fn test_scheduler_full_constants() {
assert!(!X86_SCHEDULER_SUPPORTED_CPUS.is_empty());
assert!(!X86_SCHEDULER_SUPPORTED_STRATEGIES.is_empty());
assert!(X86_SCHEDULER_MAX_ISSUE_WIDTH > 0);
assert!(X86_SCHEDULER_MAX_BUNDLE_SIZE > 0);
}
#[test]
fn test_x86_scheduler_full_sanity() {
use super::*;
assert_eq!(X86_SCHEDULER_FULL_VERSION, "1.0.0");
}
pub fn x86_test_harness(
instructions: Vec<MachineInstr>,
cpu: &str,
) -> (X86SchedulerFull, X86SchedDAG) {
let sched = X86SchedulerFull::for_cpu(cpu);
let dag = sched.build_dag(&instructions, false);
(sched, dag)
}
pub fn x86_validate_schedule(schedule: &[SchedNodeId], dag: &X86SchedDAG) -> Result<(), String> {
let n = dag.node_count;
if schedule.len() != n {
return Err(format!("Length mismatch: {} vs {}", schedule.len(), n));
}
let mut pos: Vec<i32> = vec![-1; n];
for (i, &nid) in schedule.iter().enumerate() {
if nid >= n {
return Err(format!("Invalid node id {}", nid));
}
if pos[nid] >= 0 {
return Err(format!("Duplicate node id {}", nid));
}
pos[nid] = i as i32;
}
for (nid, node) in dag.nodes.iter().enumerate() {
for &pred in &node.preds {
if pos[pred] >= pos[nid] {
return Err(format!("Dependence violated: {} → {}", pred, nid));
}
}
}
Ok(())
}