use std::collections::{HashMap, HashSet, VecDeque};
use llvm_native_core::codegen_opt::{
MCRegister, MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand,
};
use llvm_native_core::x86::X86Opcode;
pub use llvm_native_core::x86::x86_vex_encoding::X86VEXEncoding;
const _X86_64_ALLOCATABLE_GPRS: usize = 13;
const _X86_64_ALLOCATABLE_XMMS: usize = 16;
const DEFAULT_X86_LATENCY: u32 = 1;
const LOOP_ALIGN_BOUNDARY: u32 = 16;
const OUTLINER_MAX_CANDIDATE_LEN: usize = 32;
const OUTLINER_MIN_SAVINGS: usize = 4;
fn get_def_reg(instr: &MachineInstr) -> Option<MCRegister> {
instr.operands.first().and_then(|op| match op {
MachineOperand::Reg(r) => Some(*r),
_ => None,
})
}
fn make_x86_mem_op(base: u32, index: u32, scale: u8, displacement: i64) -> MachineOperand {
MachineOperand::Mem {
base: MCRegister(base),
offset: ((index as i64) << 32) | ((scale as i64) << 40) | (displacement & 0xFFFF_FFFF),
size: 0,
}
}
#[derive(Debug, Clone)]
pub struct X86BranchProbabilityInfo {
pub edge_probs: HashMap<(u32, u32), f64>,
pub block_counts: HashMap<u32, u64>,
}
impl X86BranchProbabilityInfo {
pub fn new() -> Self {
Self {
edge_probs: HashMap::new(),
block_counts: HashMap::new(),
}
}
pub fn compute(&mut self, mf: &MachineFunction) {
self.edge_probs.clear();
self.block_counts.clear();
for block in &mf.blocks {
let succs = &block.successors;
if succs.is_empty() {
continue;
}
if succs.len() == 1 {
self.edge_probs.insert((block.id, succs[0]), 1.0);
} else if succs.len() == 2 {
let taken = succs[0];
let not_taken = succs[1];
let taken_prob = if taken < block.id {
0.80 } else {
0.40 };
self.edge_probs.insert((block.id, taken), taken_prob);
self.edge_probs
.insert((block.id, not_taken), 1.0 - taken_prob);
} else {
let prob = 1.0 / succs.len() as f64;
for &succ in succs {
self.edge_probs.insert((block.id, succ), prob);
}
}
}
self.compute_block_frequencies(mf);
}
fn compute_block_frequencies(&mut self, mf: &MachineFunction) {
if mf.blocks.is_empty() {
return;
}
self.block_counts.insert(mf.entry_block, 1000);
let mut changed = true;
let mut iter = 0;
while changed && iter < 50 {
changed = false;
iter += 1;
for block in &mf.blocks {
let mut incoming = 0u64;
for &pred in &block.predecessors {
let edge_count = self
.edge_probs
.get(&(pred, block.id))
.map(|p| (*p * *self.block_counts.get(&pred).unwrap_or(&0) as f64) as u64)
.unwrap_or(0);
incoming += edge_count;
}
if block.id == mf.entry_block {
incoming = incoming.max(1000);
}
let old = *self.block_counts.get(&block.id).unwrap_or(&0);
if incoming != old && incoming > 0 {
self.block_counts.insert(block.id, incoming);
changed = true;
}
}
}
}
pub fn get_edge_probability(&self, src: u32, dst: u32) -> f64 {
self.edge_probs.get(&(src, dst)).copied().unwrap_or(0.5)
}
pub fn get_block_count(&self, id: u32) -> u64 {
self.block_counts.get(&id).copied().unwrap_or(0)
}
}
impl Default for X86BranchProbabilityInfo {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineBlockPlacement {
pub reordered_blocks: Vec<u32>,
pub fallthroughs_created: usize,
pub branch_probs: X86BranchProbabilityInfo,
pub prefer_fallthrough: bool,
pub loop_header_alignment: u32,
pub cold_threshold_percent: f64,
}
impl X86MachineBlockPlacement {
pub fn new(prefer_fallthrough: bool) -> Self {
Self {
reordered_blocks: Vec::new(),
fallthroughs_created: 0,
branch_probs: X86BranchProbabilityInfo::new(),
prefer_fallthrough,
loop_header_alignment: LOOP_ALIGN_BOUNDARY,
cold_threshold_percent: 10.0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) -> Vec<u32> {
if mf.blocks.is_empty() {
return Vec::new();
}
self.branch_probs.compute(mf);
self.reorder_with_branch_probs(mf);
self.mark_fallthroughs(mf);
self.align_loop_headers(mf);
self.reordered_blocks.clone()
}
fn reorder_with_branch_probs(&mut self, mf: &mut MachineFunction) {
let n = mf.blocks.len();
if n == 0 {
return;
}
let total_count: u64 = self.branch_probs.block_counts.values().sum();
let cold_threshold = if total_count > 0 {
(total_count as f64 * self.cold_threshold_percent / 100.0) as u64
} else {
0
};
let mut placed: HashSet<u32> = HashSet::new();
let mut order: Vec<u32> = Vec::with_capacity(n);
let mut cold_blocks: Vec<u32> = Vec::new();
let mut current = mf.entry_block;
placed.insert(current);
order.push(current);
loop {
let best_succ = mf.block_by_id(current).and_then(|b| {
b.successors
.iter()
.filter(|&&s| !placed.contains(&s))
.max_by(|&&a, &&b| {
let pa = self.branch_probs.get_edge_probability(current, a);
let pb = self.branch_probs.get_edge_probability(current, b);
pa.partial_cmp(&pb).unwrap_or(std::cmp::Ordering::Equal)
})
.copied()
});
if let Some(next) = best_succ {
let block_count = self.branch_probs.get_block_count(next);
if block_count > 0 && block_count <= cold_threshold {
cold_blocks.push(next);
}
placed.insert(next);
order.push(next);
current = next;
} else {
let hottest =
mf.blocks
.iter()
.filter(|b| !placed.contains(&b.id))
.max_by(|a, b| {
let ca = self.branch_probs.get_block_count(a.id);
let cb = self.branch_probs.get_block_count(b.id);
ca.cmp(&cb)
});
if let Some(block) = hottest {
placed.insert(block.id);
order.push(block.id);
current = block.id;
} else {
break;
}
}
}
for &cold in &cold_blocks {
if !order.contains(&cold) {
order.push(cold);
}
}
self.reordered_blocks = order;
}
fn mark_fallthroughs(&mut self, mf: &mut MachineFunction) {
self.fallthroughs_created = 0;
let reordered = &self.reordered_blocks;
for i in 0..reordered.len().saturating_sub(1) {
let cur = reordered[i];
let next = reordered[i + 1];
if let Some(block) = mf.get_block_mut(cur) {
if block.successors.first() == Some(&next) {
self.fallthroughs_created += 1;
}
}
}
}
fn align_loop_headers(&self, mf: &mut MachineFunction) {
if self.loop_header_alignment == 0 {
return;
}
for block in &mut mf.blocks {
let is_loop_header = block.predecessors.iter().any(|&pred_id| pred_id > block.id);
if is_loop_header {
block.alignment = block.alignment.max(self.loop_header_alignment);
}
}
}
pub fn split_hot_cold(&self, mf: &mut MachineFunction) -> (Vec<u32>, Vec<u32>) {
let total: u64 = self.branch_probs.block_counts.values().sum();
let threshold = if total > 0 {
(total as f64 * self.cold_threshold_percent / 100.0) as u64
} else {
0
};
let mut hot: Vec<u32> = Vec::new();
let mut cold: Vec<u32> = Vec::new();
for block in &mf.blocks {
let count = self.branch_probs.get_block_count(block.id);
if count <= threshold {
cold.push(block.id);
} else {
hot.push(block.id);
}
}
(hot, cold)
}
pub fn layout_by_edge_counts(&mut self, mf: &mut MachineFunction) {
let mut edges: Vec<(f64, u32, u32)> = self
.branch_probs
.edge_probs
.iter()
.map(|(&(src, dst), &prob)| {
(
prob * self.branch_probs.get_block_count(src) as f64,
src,
dst,
)
})
.collect();
edges.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap_or(std::cmp::Ordering::Equal));
let mut chains: HashMap<u32, Vec<u32>> = HashMap::new();
let mut block_chain: HashMap<u32, u32> = HashMap::new();
let mut chain_heads: HashSet<u32> = HashSet::new();
for &(_count, src, dst) in &edges {
if block_chain.contains_key(&dst) && chain_heads.contains(&src) {
continue;
}
let src_chain = block_chain.get(&src).copied();
let dst_chain = block_chain.get(&dst).copied();
match (src_chain, dst_chain) {
(None, None) => {
let chain = vec![src, dst];
chains.insert(src, chain);
block_chain.insert(src, src);
block_chain.insert(dst, src);
chain_heads.insert(src);
}
(Some(chain_id), None) => {
if let Some(chain) = chains.get_mut(&chain_id) {
chain.push(dst);
}
block_chain.insert(dst, chain_id);
}
(None, Some(chain_id)) => {
if let Some(chain) = chains.get_mut(&chain_id) {
if chain.first() == Some(&dst) {
chain.insert(0, src);
}
}
block_chain.insert(src, chain_id);
chain_heads.remove(&dst);
chain_heads.insert(src);
}
(Some(s_chain), Some(d_chain)) if s_chain != d_chain => {
if let Some(d_chain_blocks) = chains.remove(&d_chain) {
if let Some(s_chain_blocks) = chains.get_mut(&s_chain) {
s_chain_blocks.extend(d_chain_blocks);
}
}
chain_heads.remove(&d_chain);
}
_ => {}
}
}
let mut placed: HashSet<u32> = HashSet::new();
let mut order: Vec<u32> = Vec::new();
let entry_chain = block_chain.get(&mf.entry_block).copied();
if let Some(chain_id) = entry_chain {
if let Some(chain) = chains.remove(&chain_id) {
for &id in &chain {
placed.insert(id);
order.push(id);
}
}
}
let chain_ids: Vec<u32> = chains.keys().copied().collect();
for chain_id in chain_ids {
if let Some(chain) = chains.remove(&chain_id) {
for id in chain {
if !placed.contains(&id) {
placed.insert(id);
order.push(id);
}
}
}
}
for block in &mf.blocks {
if !placed.contains(&block.id) {
order.push(block.id);
}
}
self.reordered_blocks = order;
}
}
impl Default for X86MachineBlockPlacement {
fn default() -> Self {
Self::new(true)
}
}
#[derive(Debug)]
pub struct X86MachineCSE {
pub eliminated: usize,
pub cross_block: bool,
pub max_scan_window: usize,
}
impl X86MachineCSE {
pub fn new(cross_block: bool) -> Self {
Self {
eliminated: 0,
cross_block,
max_scan_window: 32,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.eliminated = 0;
if self.cross_block {
self.cse_cross_block(mf);
} else {
let block_ids: Vec<u32> = mf.blocks.iter().map(|b| b.id).collect();
for block_id in block_ids {
self.cse_block(mf, block_id);
}
}
}
fn cse_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut to_remove: Vec<usize> = Vec::new();
let mut seen: Vec<(usize, MachineInstr)> = Vec::new();
let mut clobbered_regs: HashSet<MCRegister> = HashSet::new();
for i in 0..block.instructions.len() {
let instr = &block.instructions[i];
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
clobbered_regs.insert(*reg);
}
}
let start = if seen.len() > self.max_scan_window {
seen.len() - self.max_scan_window
} else {
0
};
let mut found_dup = false;
for j in (start..seen.len()).rev() {
let (_, seen_instr) = &seen[j];
if self.are_identical_for_cse(instr, seen_instr) {
to_remove.push(i);
self.eliminated += 1;
found_dup = true;
break;
}
}
if !found_dup {
seen.push((i, instr.clone()));
}
}
to_remove.sort_unstable();
for &idx in to_remove.iter().rev() {
if let Some(block) = mf.get_block_mut(block_id) {
if idx < block.instructions.len() {
block.instructions.remove(idx);
}
}
}
}
fn are_identical_for_cse(&self, a: &MachineInstr, b: &MachineInstr) -> bool {
if a.opcode != b.opcode {
return false;
}
if a.operands.len() != b.operands.len() {
return false;
}
let commutative = self.is_x86_commutative(a.opcode);
if commutative && a.operands.len() >= 2 {
self.operands_match_commutative(a, b)
} else {
a.operands
.iter()
.zip(b.operands.iter())
.all(|(oa, ob)| self.operand_equals(oa, ob))
}
}
fn is_x86_commutative(&self, opcode: u32) -> bool {
let o = opcode;
o == X86Opcode::ADD as u32
|| o == X86Opcode::ADC as u32
|| o == X86Opcode::MUL as u32
|| o == X86Opcode::IMUL as u32
|| o == X86Opcode::AND as u32
|| o == X86Opcode::OR as u32
|| o == X86Opcode::XOR as u32
|| o == X86Opcode::ADDPS as u32
|| o == X86Opcode::ADDPD as u32
|| o == X86Opcode::MULPS as u32
|| o == X86Opcode::MULPD as u32
|| o == X86Opcode::ANDPS as u32
|| o == X86Opcode::ORPS as u32
|| o == X86Opcode::XORPS as u32
|| o == X86Opcode::VADDPS as u32
|| o == X86Opcode::VADDPD as u32
|| o == X86Opcode::VMULPS as u32
|| o == X86Opcode::VMULPD as u32
|| o == X86Opcode::VANDPS as u32
|| o == X86Opcode::VORPS as u32
|| o == X86Opcode::VXORPS as u32
}
fn operands_match_commutative(&self, a: &MachineInstr, b: &MachineInstr) -> bool {
let n = a.operands.len();
if n == 2 {
(self.operand_equals(&a.operands[0], &b.operands[0])
&& self.operand_equals(&a.operands[1], &b.operands[1]))
|| (self.operand_equals(&a.operands[0], &b.operands[1])
&& self.operand_equals(&a.operands[1], &b.operands[0]))
} else if n >= 3 {
self.operand_equals(&a.operands[0], &b.operands[0])
&& ((self.operand_equals(&a.operands[1], &b.operands[1])
&& self.operand_equals(&a.operands[2], &b.operands[2]))
|| (self.operand_equals(&a.operands[1], &b.operands[2])
&& self.operand_equals(&a.operands[2], &b.operands[1])))
} else {
a.operands
.iter()
.zip(b.operands.iter())
.all(|(oa, ob)| self.operand_equals(oa, ob))
}
}
fn operand_equals(&self, a: &MachineOperand, b: &MachineOperand) -> bool {
match (a, b) {
(MachineOperand::Reg(ra), MachineOperand::Reg(rb)) => ra.0 == rb.0,
(MachineOperand::Imm(ia), MachineOperand::Imm(ib)) => ia == ib,
(MachineOperand::FPImm(fa), MachineOperand::FPImm(fb)) => {
(fa - fb).abs() < f64::EPSILON
}
(MachineOperand::Block(la), MachineOperand::Block(lb)) => la == lb,
(MachineOperand::Global(ga), MachineOperand::Global(gb)) => ga == gb,
(
MachineOperand::Mem {
base: ba,
offset: oa,
size: sa,
},
MachineOperand::Mem {
base: bb,
offset: ob,
size: sb,
},
) => ba == bb && oa == ob && sa == sb,
(MachineOperand::CCMask(ca), MachineOperand::CCMask(cb)) => ca == cb,
_ => false,
}
}
fn cse_cross_block(&mut self, mf: &mut MachineFunction) {
let order = self.compute_rpo(mf);
let mut avail: HashMap<u32, Vec<(MachineInstr, u32)>> = HashMap::new();
for &block_id in &order {
let mut block_avail: Vec<(MachineInstr, u32)> = Vec::new();
self.cse_block_with_avail(mf, block_id, &mut block_avail);
avail.insert(block_id, block_avail);
}
}
fn cse_block_with_avail(
&mut self,
mf: &mut MachineFunction,
block_id: u32,
avail: &mut Vec<(MachineInstr, u32)>,
) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut to_remove: Vec<usize> = Vec::new();
for i in 0..block.instructions.len() {
let instr = &block.instructions[i];
let mut found = false;
for (avail_instr, _) in avail.iter() {
if self.are_identical_for_cse(instr, avail_instr) {
to_remove.push(i);
self.eliminated += 1;
found = true;
break;
}
}
if !found {
avail.push((instr.clone(), block_id));
}
}
to_remove.sort_unstable();
for &idx in to_remove.iter().rev() {
if let Some(block) = mf.get_block_mut(block_id) {
if idx < block.instructions.len() {
block.instructions.remove(idx);
}
}
}
}
fn compute_rpo(&self, mf: &MachineFunction) -> Vec<u32> {
let mut order = Vec::new();
let mut visited = HashSet::new();
visited.insert(mf.entry_block);
let mut dfs_stack: Vec<(u32, usize)> = Vec::new();
dfs_stack.push((mf.entry_block, 0));
while let Some((node, idx)) = dfs_stack.pop() {
let succs: Vec<u32> = mf
.block_by_id(node)
.map(|b| b.successors.clone())
.unwrap_or_default();
if idx < succs.len() {
dfs_stack.push((node, idx + 1));
let child = succs[idx];
if !visited.contains(&child) {
visited.insert(child);
dfs_stack.push((child, 0));
}
} else {
order.push(node);
}
}
order.reverse();
order
}
}
impl Default for X86MachineCSE {
fn default() -> Self {
Self::new(false)
}
}
#[derive(Debug)]
pub struct X86MachineLICM {
pub hoisted: usize,
pub sunk: usize,
pub max_pressure_gpr: usize,
pub max_pressure_xmm: usize,
loop_info: HashMap<u32, HashSet<u32>>,
preheaders: HashMap<u32, u32>,
}
impl X86MachineLICM {
pub fn new() -> Self {
Self {
hoisted: 0,
sunk: 0,
max_pressure_gpr: _X86_64_ALLOCATABLE_GPRS,
max_pressure_xmm: _X86_64_ALLOCATABLE_XMMS,
loop_info: HashMap::new(),
preheaders: HashMap::new(),
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.hoisted = 0;
self.sunk = 0;
self.detect_loops(mf);
if self.loop_info.is_empty() {
return;
}
self.find_preheaders(mf);
let loop_headers: Vec<u32> = self.loop_info.keys().copied().collect();
for header_id in loop_headers {
let loop_blocks = self.loop_info.get(&header_id).cloned().unwrap_or_default();
if let Some(&preheader_id) = self.preheaders.get(&header_id) {
self.hoist_loop_invariants(mf, header_id, &loop_blocks, preheader_id);
}
}
self.sink_instructions(mf);
}
pub fn detect_loops(&mut self, mf: &MachineFunction) {
self.loop_info.clear();
let doms = self.compute_dominators(mf);
let mut back_edges: Vec<(u32, u32)> = Vec::new();
for block in &mf.blocks {
for &succ in &block.successors {
if doms
.get(&block.id)
.map(|dom_set| dom_set.contains(&succ))
.unwrap_or(false)
{
back_edges.push((block.id, succ));
}
}
}
for &(tail, header) in &back_edges {
if self.loop_info.contains_key(&header) {
continue;
}
let mut loop_blocks: HashSet<u32> = HashSet::new();
loop_blocks.insert(header);
let mut worklist: Vec<u32> = vec![tail];
let mut visited: HashSet<u32> = HashSet::new();
visited.insert(header);
while let Some(block) = worklist.pop() {
if !loop_blocks.insert(block) {
continue;
}
if let Some(b) = mf.block_by_id(block) {
for &pred in &b.predecessors {
if !visited.contains(&pred) && pred != header {
visited.insert(pred);
worklist.push(pred);
}
}
}
}
if !loop_blocks.is_empty() {
self.loop_info.insert(header, loop_blocks);
}
}
}
fn compute_dominators(&self, mf: &MachineFunction) -> HashMap<u32, HashSet<u32>> {
let all_blocks: HashSet<u32> = mf.blocks.iter().map(|b| b.id).collect();
let mut dom: HashMap<u32, HashSet<u32>> = HashMap::new();
for block in &mf.blocks {
if block.id == mf.entry_block {
let mut s = HashSet::new();
s.insert(mf.entry_block);
dom.insert(block.id, s);
} else {
dom.insert(block.id, all_blocks.clone());
}
}
let mut changed = true;
let mut iter = 0;
while changed && iter < 100 {
changed = false;
iter += 1;
for block in &mf.blocks {
if block.id == mf.entry_block {
continue;
}
let mut new_dom: HashSet<u32> = all_blocks.clone();
for &pred in &block.predecessors {
if let Some(pred_dom) = dom.get(&pred) {
new_dom = new_dom.intersection(pred_dom).copied().collect();
}
}
new_dom.insert(block.id);
if dom.get(&block.id) != Some(&new_dom) {
dom.insert(block.id, new_dom);
changed = true;
}
}
}
dom
}
fn find_preheaders(&mut self, mf: &MachineFunction) {
self.preheaders.clear();
for (&header_id, loop_blocks) in &self.loop_info {
let preheaders: Vec<u32> = mf
.block_by_id(header_id)
.map(|b| {
b.predecessors
.iter()
.filter(|p| !loop_blocks.contains(p))
.copied()
.collect()
})
.unwrap_or_default();
if preheaders.len() == 1 {
self.preheaders.insert(header_id, preheaders[0]);
}
}
}
fn is_invariant(
&self,
instr: &MachineInstr,
loop_blocks: &HashSet<u32>,
mf: &MachineFunction,
) -> bool {
for op in &instr.operands {
match op {
MachineOperand::Mem { .. } => {
return false; }
MachineOperand::Reg(reg) => {
if self.is_reg_defined_in_loop(*reg, loop_blocks, mf) {
return false;
}
}
_ => {} }
}
if self.has_side_effects(instr) {
return false;
}
true
}
fn is_reg_defined_in_loop(
&self,
reg: MCRegister,
loop_blocks: &HashSet<u32>,
mf: &MachineFunction,
) -> bool {
for &block_id in loop_blocks {
if let Some(block) = mf.block_by_id(block_id) {
for instr in &block.instructions {
if instr.writes_register(reg) {
return true;
}
}
}
}
false
}
fn has_side_effects(&self, instr: &MachineInstr) -> bool {
instr.flags.has_side_effects
|| instr.flags.is_store
|| instr.flags.is_call
|| instr.flags.is_branch
|| instr.flags.is_return
|| instr.flags.is_terminator
}
fn hoist_loop_invariants(
&mut self,
mf: &mut MachineFunction,
header: u32,
loop_blocks: &HashSet<u32>,
preheader: u32,
) {
let mut gpr_pressure = 0;
let mut invariants: Vec<(u32, usize, MachineInstr)> = Vec::new();
for &block_id in loop_blocks.iter() {
if let Some(block) = mf.block_by_id(block_id) {
for (idx, instr) in block.instructions.iter().enumerate() {
if self.is_invariant(instr, loop_blocks, mf) {
invariants.push((block_id, idx, instr.clone()));
}
}
}
}
invariants.sort_by_key(|(bid, idx, _)| (std::cmp::Reverse(*bid), *idx));
let mut removed_indices: HashMap<u32, Vec<usize>> = HashMap::new();
for (block_id, idx, instr) in &invariants {
let writes_gpr = self.instr_writes_gpr(instr);
if writes_gpr && gpr_pressure >= self.max_pressure_gpr {
continue;
}
removed_indices.entry(*block_id).or_default().push(*idx);
if writes_gpr {
gpr_pressure += 1;
}
}
for (block_id, mut indices) in removed_indices {
indices.sort_unstable();
let mut hoisted_instrs: Vec<MachineInstr> = Vec::new();
if let Some(block) = mf.get_block_mut(block_id) {
for &idx in indices.iter().rev() {
if idx < block.instructions.len() {
hoisted_instrs.push(block.instructions.remove(idx));
}
}
}
if !hoisted_instrs.is_empty() {
if let Some(preheader_block) = mf.get_block_mut(preheader) {
let has_terminator = preheader_block
.instructions
.last()
.map(|i| i.flags.is_terminator)
.unwrap_or(false);
let insert_pos = if has_terminator {
preheader_block.instructions.len().saturating_sub(1)
} else {
preheader_block.instructions.len()
};
for instr in hoisted_instrs {
preheader_block.instructions.insert(insert_pos, instr);
self.hoisted += 1;
}
}
}
}
}
fn instr_writes_gpr(&self, instr: &MachineInstr) -> bool {
matches!(instr.operands.first(), Some(MachineOperand::Reg(_)))
&& !matches!(
instr.opcode,
_ if instr.opcode == X86Opcode::MOVSS as u32
|| instr.opcode == X86Opcode::MOVSD as u32
|| instr.opcode == X86Opcode::ADDSS as u32
)
}
fn sink_instructions(&mut self, mf: &mut MachineFunction) {
let blocks: Vec<MachineBasicBlock> = mf.blocks.clone();
for block in &blocks {
if block.successors.len() < 2 || block.is_exit {
continue;
}
let terminator_idx = block
.instructions
.iter()
.rposition(|i| i.flags.is_terminator);
let scan_end = terminator_idx.unwrap_or(block.instructions.len());
'instr_loop: for idx in (0..scan_end).rev() {
let instr = &block.instructions[idx];
if instr.flags.is_terminator
|| instr.flags.is_branch
|| instr.flags.is_call
|| instr.flags.is_return
{
continue;
}
let def_reg = get_def_reg(instr);
if let Some(reg) = def_reg {
let mut using_succ: Option<u32> = None;
for &succ in &block.successors {
if let Some(succ_block) = mf.block_by_id(succ) {
let used = succ_block
.instructions
.iter()
.any(|i| i.reads_register(reg));
if used {
if using_succ.is_some() {
continue 'instr_loop; }
using_succ = Some(succ);
}
}
}
if let Some(target_succ) = using_succ {
let used_later = block.instructions[idx + 1..]
.iter()
.any(|i| i.reads_register(reg));
if used_later {
continue 'instr_loop;
}
if let Some(blk) = mf.get_block_mut(block.id) {
if idx < blk.instructions.len() {
let moved_instr = blk.instructions.remove(idx);
if let Some(target) = mf.get_block_mut(target_succ) {
target.instructions.insert(0, moved_instr);
self.sunk += 1;
}
}
}
}
}
}
}
}
}
impl Default for X86MachineLICM {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineSinking {
pub sunk: usize,
pub split_critical_edges: bool,
pub max_iterations: usize,
}
impl X86MachineSinking {
pub fn new() -> Self {
Self {
sunk: 0,
split_critical_edges: true,
max_iterations: 4,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.sunk = 0;
for _iter in 0..self.max_iterations {
let sunk_before = self.sunk;
if self.split_critical_edges {
self.split_critical_edges_in_func(mf);
}
let block_ids: Vec<u32> = mf.blocks.iter().map(|b| b.id).collect();
for block_id in block_ids {
self.sink_from_block(mf, block_id);
}
if self.sunk == sunk_before {
break;
}
}
}
fn sink_from_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let successors: Vec<u32>;
let instructions: Vec<MachineInstr>;
{
let block = match mf.block_by_id(block_id) {
Some(b) => b,
None => return,
};
if block.successors.len() < 2 {
return;
}
successors = block.successors.clone();
instructions = block.instructions.clone();
}
let terminator_pos = instructions.iter().rposition(|i| i.flags.is_terminator);
let end = terminator_pos.unwrap_or(instructions.len());
for idx in (0..end).rev() {
let instr = &instructions[idx];
if !self.can_sink_instruction(instr) {
continue;
}
if let Some(target_succ) = self.find_sinking_target(instr, block_id, &successors, mf) {
self.perform_sink(mf, block_id, idx, target_succ);
}
}
}
fn can_sink_instruction(&self, instr: &MachineInstr) -> bool {
!instr.flags.is_terminator
&& !instr.flags.is_branch
&& !instr.flags.is_call
&& !instr.flags.is_return
&& !instr.flags.is_barrier
&& !instr.flags.has_side_effects
}
fn find_sinking_target(
&self,
instr: &MachineInstr,
_block_id: u32,
successors: &[u32],
mf: &MachineFunction,
) -> Option<u32> {
let def_reg = get_def_reg(instr);
let mut using_successors: Vec<u32> = Vec::new();
for &succ in successors {
if let Some(succ_block) = mf.block_by_id(succ) {
if let Some(reg) = def_reg {
let used = succ_block
.instructions
.iter()
.any(|i| i.reads_register(reg));
if used {
using_successors.push(succ);
}
}
}
}
if using_successors.len() == 1 {
Some(using_successors[0])
} else {
None
}
}
fn perform_sink(
&mut self,
mf: &mut MachineFunction,
block_id: u32,
idx: usize,
target_succ: u32,
) {
let moved = {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
if idx >= block.instructions.len() {
return;
}
block.instructions.remove(idx)
};
if let Some(target) = mf.get_block_mut(target_succ) {
target.instructions.insert(0, moved);
self.sunk += 1;
} else {
if let Some(block) = mf.get_block_mut(block_id) {
block.instructions.insert(idx, moved);
}
}
}
fn split_critical_edges_in_func(&mut self, mf: &mut MachineFunction) {
let mut edges_to_split: Vec<(u32, u32)> = Vec::new();
for block in &mf.blocks {
if block.successors.len() < 2 {
continue;
}
for &succ in &block.successors {
if let Some(succ_block) = mf.block_by_id(succ) {
if succ_block.predecessors.len() >= 2 {
edges_to_split.push((block.id, succ));
}
}
}
}
for (src, dst) in edges_to_split {
self.split_edge(mf, src, dst);
}
}
fn split_edge(&mut self, mf: &mut MachineFunction, src: u32, dst: u32) {
let new_id = mf.next_block_id();
let new_block = MachineBasicBlock::new(new_id, format!("crit_edge_{}_{}", src, dst));
mf.add_block(new_block);
if let Some(src_block) = mf.get_block_mut(src) {
if let Some(pos) = src_block.successors.iter().position(|&s| s == dst) {
src_block.successors[pos] = new_id;
}
}
if let Some(new_block) = mf.get_block_mut(new_id) {
new_block.predecessors = vec![src];
new_block.successors = vec![dst];
}
if let Some(dst_block) = mf.get_block_mut(dst) {
if let Some(pos) = dst_block.predecessors.iter().position(|&p| p == src) {
dst_block.predecessors[pos] = new_id;
}
}
}
}
impl Default for X86MachineSinking {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineCombiner {
pub combined: usize,
pub enable_lea_formation: bool,
pub enable_macro_fusion_prep: bool,
pub enable_inc_dec_opt: bool,
}
impl X86MachineCombiner {
pub fn new() -> Self {
Self {
combined: 0,
enable_lea_formation: true,
enable_macro_fusion_prep: true,
enable_inc_dec_opt: true,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.combined = 0;
let block_ids: Vec<u32> = mf.blocks.iter().map(|b| b.id).collect();
for block_id in block_ids {
self.combine_block(mf, block_id);
}
}
fn combine_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let mut i = 0;
loop {
let len = mf
.get_block(block_id)
.map(|b| b.instructions.len())
.unwrap_or(0);
if i + 1 >= len {
break;
}
if self.try_combine_pair(mf, block_id, i) {
self.combined += 1;
} else {
i += 1;
}
}
}
fn try_combine_pair(&self, mf: &mut MachineFunction, block_id: u32, idx: usize) -> bool {
let first;
let second;
{
let block = match mf.get_block(block_id) {
Some(b) => b,
None => return false,
};
if idx + 1 >= block.instructions.len() {
return false;
}
first = block.instructions[idx].clone();
second = block.instructions[idx + 1].clone();
}
if self.enable_lea_formation {
if let Some(lea) = self.try_shl_add_to_lea(&first, &second) {
return self.replace_pair(mf, block_id, idx, lea);
}
}
if self.enable_lea_formation {
if let Some(lea) = self.try_add_add_to_lea(&first, &second) {
return self.replace_pair(mf, block_id, idx, lea);
}
}
if self.enable_lea_formation {
if let Some(lea) = self.try_mul_add_to_lea(&first, &second) {
return self.replace_pair(mf, block_id, idx, lea);
}
}
if self.enable_macro_fusion_prep {
if let Some(replacement) = self.try_cmp_jcc_macro_fusion(&first, &second) {
return self.replace_pair(mf, block_id, idx, replacement);
}
}
if self.enable_inc_dec_opt {
if self.try_inc_dec_to_add_sub(mf, block_id, idx) {
return true;
}
}
if let Some(combined) = self.try_mov_op_mem_fold(&first, &second) {
return self.replace_pair(mf, block_id, idx, combined);
}
false
}
fn try_shl_add_to_lea(
&self,
first: &MachineInstr,
second: &MachineInstr,
) -> Option<MachineInstr> {
if first.opcode != X86Opcode::SHL as u32 || second.opcode != X86Opcode::ADD as u32 {
return None;
}
if first.operands.len() < 2 || second.operands.len() < 2 {
return None;
}
let shift_reg = match &first.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
let shift_amount = match &first.operands[1] {
MachineOperand::Imm(v) => *v,
_ => return None,
};
let scale = 1u64 << shift_amount;
if scale != 1 && scale != 2 && scale != 4 && scale != 8 {
return None;
}
let mut lea_instr = MachineInstr::new(X86Opcode::LEA as u32);
lea_instr.flags.is_move_reg = true;
lea_instr.operands.push(second.operands[0].clone());
lea_instr.operands.push(MachineOperand::Reg(shift_reg));
let base_reg = second.operands[1..].iter().find_map(|op| match op {
MachineOperand::Reg(r) if *r != shift_reg => Some(*r),
MachineOperand::Imm(_) => None,
_ => None,
});
if let Some(base) = base_reg {
lea_instr.operands.push(MachineOperand::Reg(base));
}
Some(lea_instr)
}
fn try_add_add_to_lea(
&self,
first: &MachineInstr,
second: &MachineInstr,
) -> Option<MachineInstr> {
if first.opcode != X86Opcode::ADD as u32 || second.opcode != X86Opcode::ADD as u32 {
return None;
}
if first.operands.len() < 2 || second.operands.len() < 2 {
return None;
}
let first_dest = match &first.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
let second_uses_first = second.operands[1..].iter().any(|op| match op {
MachineOperand::Reg(r) => *r == first_dest,
_ => false,
});
if !second_uses_first {
return None;
}
let first_src = match &first.operands[1] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
let mut lea = MachineInstr::new(X86Opcode::LEA as u32);
lea.flags.is_move_reg = true;
lea.operands.push(second.operands[0].clone());
lea.operands
.push(make_x86_mem_op(first_src.0, first_dest.0, 1, 0));
Some(lea)
}
fn try_mul_add_to_lea(
&self,
first: &MachineInstr,
second: &MachineInstr,
) -> Option<MachineInstr> {
if first.opcode != X86Opcode::IMUL as u32 {
return None;
}
if first.operands.len() < 3 {
return None;
}
let multiplier = match &first.operands[2] {
MachineOperand::Imm(v) => *v,
_ => return None,
};
if multiplier != 2 && multiplier != 4 && multiplier != 8 {
return None;
}
let mul_src = match &first.operands[1] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
if second.opcode != X86Opcode::ADD as u32 {
return None;
}
let mul_dest = match &first.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
let mul_dest_used = second.operands[1..].iter().any(|op| match op {
MachineOperand::Reg(r) => *r == mul_dest,
_ => false,
});
if !mul_dest_used {
return None;
}
let base = second.operands[1..].iter().find_map(|op| match op {
MachineOperand::Reg(r) if *r != mul_dest => Some(*r),
_ => None,
})?;
let mut lea = MachineInstr::new(X86Opcode::LEA as u32);
lea.flags.is_move_reg = true;
lea.operands.push(second.operands[0].clone());
lea.operands
.push(make_x86_mem_op(base.0, mul_src.0, multiplier as u8, 0));
Some(lea)
}
fn try_cmp_jcc_macro_fusion(
&self,
first: &MachineInstr,
second: &MachineInstr,
) -> Option<MachineInstr> {
if first.opcode != X86Opcode::CMP as u32 && first.opcode != X86Opcode::TEST as u32 {
return None;
}
if !second.flags.is_branch {
return None;
}
let mut fused = second.clone();
fused.flags.is_inside_bundle = true;
fused.flags.is_bundle_head = true;
Some(fused)
}
fn try_inc_dec_to_add_sub(&self, mf: &mut MachineFunction, block_id: u32, idx: usize) -> bool {
let block = match mf.get_block(block_id) {
Some(b) => b,
None => return false,
};
if idx >= block.instructions.len() {
return false;
}
let instr = &block.instructions[idx];
let new_opcode = if instr.opcode == X86Opcode::INC as u32 {
X86Opcode::ADD as u32
} else if instr.opcode == X86Opcode::DEC as u32 {
X86Opcode::SUB as u32
} else {
return false;
};
if instr.operands.is_empty() {
return false;
}
let block = mf.get_block_mut(block_id).unwrap();
block.instructions[idx].opcode = new_opcode;
block.instructions[idx]
.operands
.push(MachineOperand::Imm(1));
true
}
fn try_mov_op_mem_fold(
&self,
first: &MachineInstr,
second: &MachineInstr,
) -> Option<MachineInstr> {
if first.opcode != X86Opcode::MOV as u32 {
return None;
}
let mov_dest = match &first.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return None,
};
let mov_src_is_mem = matches!(&first.operands[1], MachineOperand::Mem { .. });
if !mov_src_is_mem {
return None;
}
let uses_mov_dest = second.operands.iter().any(|op| match op {
MachineOperand::Reg(r) => *r == mov_dest,
_ => false,
});
if !uses_mov_dest || second.operands.len() < 2 {
return None;
}
if !self.is_2operand_alu(second.opcode) {
return None;
}
let mut combined = second.clone();
let mem_op = first.operands[1].clone();
for op in combined.operands.iter_mut().skip(1) {
if let MachineOperand::Reg(r) = op {
if *r == mov_dest {
*op = mem_op.clone();
break;
}
}
}
Some(combined)
}
fn is_2operand_alu(&self, opcode: u32) -> bool {
let o = opcode;
o == X86Opcode::ADD as u32
|| o == X86Opcode::SUB as u32
|| o == X86Opcode::AND as u32
|| o == X86Opcode::OR as u32
|| o == X86Opcode::XOR as u32
|| o == X86Opcode::CMP as u32
|| o == X86Opcode::TEST as u32
}
fn replace_pair(
&self,
mf: &mut MachineFunction,
block_id: u32,
idx: usize,
replacement: MachineInstr,
) -> bool {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return false,
};
if idx + 1 >= block.instructions.len() {
return false;
}
block.instructions.remove(idx + 1);
block.instructions.remove(idx);
block.instructions.insert(idx, replacement);
true
}
}
impl Default for X86MachineCombiner {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86PeepholeOptimizer {
pub redundant_movs_eliminated: usize,
pub xor_to_xor32: usize,
pub cmp_zero_to_test: usize,
pub double_neg_eliminated: usize,
pub identity_ops_removed: usize,
pub lea_to_nop: usize,
pub mov_to_movzx: usize,
pub shift_combined: usize,
pub cmov_same_to_mov: usize,
}
impl X86PeepholeOptimizer {
pub fn new() -> Self {
Self {
redundant_movs_eliminated: 0,
xor_to_xor32: 0,
cmp_zero_to_test: 0,
double_neg_eliminated: 0,
identity_ops_removed: 0,
lea_to_nop: 0,
mov_to_movzx: 0,
shift_combined: 0,
cmov_same_to_mov: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
let mut changed = true;
let mut iterations = 0;
while changed && iterations < 10 {
changed = false;
iterations += 1;
let block_ids: Vec<u32> = mf.blocks.iter().map(|b| b.id).collect();
for block_id in block_ids {
if self.optimize_block(mf, block_id) {
changed = true;
}
}
}
}
fn optimize_block(&mut self, mf: &mut MachineFunction, block_id: u32) -> bool {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return false,
};
let mut modified = false;
let mut i = 0;
while i < block.instructions.len() {
if self.is_redundant_mov(&block.instructions[i]) {
block.instructions.remove(i);
self.redundant_movs_eliminated += 1;
modified = true;
continue;
}
if self.is_xor_reg_reg_64(&block.instructions[i]) {
block.instructions[i].opcode = X86Opcode::XOR as u32;
self.xor_to_xor32 += 1;
modified = true;
}
if self.is_cmp_reg_zero(&block.instructions[i]) {
let reg_val = match block.instructions[i].operands[0] {
MachineOperand::Reg(r) => r,
_ => {
i += 1;
continue;
}
};
block.instructions[i].opcode = X86Opcode::TEST as u32;
block.instructions[i].operands[1] = MachineOperand::Reg(reg_val);
self.cmp_zero_to_test += 1;
modified = true;
}
if i + 1 < block.instructions.len() {
let is_double =
self.is_double_negation(&block.instructions[i], &block.instructions[i + 1]);
if is_double {
block.instructions.remove(i + 1);
block.instructions.remove(i);
self.double_neg_eliminated += 1;
modified = true;
continue;
}
}
if self.is_identity_op(&block.instructions[i]) {
block.instructions.remove(i);
self.identity_ops_removed += 1;
modified = true;
continue;
}
if self.is_lea_noop(&block.instructions[i]) {
block.instructions.remove(i);
self.lea_to_nop += 1;
modified = true;
continue;
}
if i + 1 < block.instructions.len() && self.try_mov_movzx_combine(block, i) {
self.mov_to_movzx += 1;
modified = true;
continue;
}
if i + 1 < block.instructions.len() && self.try_shift_combine(block, i) {
self.shift_combined += 1;
modified = true;
continue;
}
if self.is_cmov_same_src_dest(&block.instructions[i]) {
block.instructions[i].opcode = X86Opcode::MOV as u32;
block.instructions[i].operands.truncate(2);
self.cmov_same_to_mov += 1;
modified = true;
}
i += 1;
}
modified
}
fn is_redundant_mov(&self, instr: &MachineInstr) -> bool {
if instr.opcode != X86Opcode::MOV as u32 {
return false;
}
if instr.operands.len() < 2 {
return false;
}
matches!(
(&instr.operands[0], &instr.operands[1]),
(MachineOperand::Reg(a), MachineOperand::Reg(b)) if a == b
)
}
fn is_xor_reg_reg_64(&self, instr: &MachineInstr) -> bool {
if instr.opcode != X86Opcode::XOR as u32 {
return false;
}
if instr.operands.len() < 2 {
return false;
}
matches!(
(&instr.operands[0], &instr.operands[1]),
(MachineOperand::Reg(a), MachineOperand::Reg(b)) if a == b
)
}
fn is_cmp_reg_zero(&self, instr: &MachineInstr) -> bool {
if instr.opcode != X86Opcode::CMP as u32 {
return false;
}
if instr.operands.len() < 2 {
return false;
}
matches!(
(&instr.operands[0], &instr.operands[1]),
(MachineOperand::Reg(_), MachineOperand::Imm(0))
)
}
fn is_double_negation(&self, a: &MachineInstr, b: &MachineInstr) -> bool {
if a.opcode != X86Opcode::NEG as u32 || b.opcode != X86Opcode::NEG as u32 {
return false;
}
if a.operands.is_empty() || b.operands.is_empty() {
return false;
}
matches!(
(&a.operands[0], &b.operands[0]),
(MachineOperand::Reg(ra), MachineOperand::Reg(rb)) if ra == rb
)
}
fn is_identity_op(&self, instr: &MachineInstr) -> bool {
let opcode = instr.opcode;
let is_identity_alu = opcode == X86Opcode::AND as u32
|| opcode == X86Opcode::OR as u32
|| opcode == X86Opcode::XOR as u32;
if !is_identity_alu || instr.operands.len() < 2 {
return false;
}
match (&instr.operands[0], &instr.operands[1]) {
(MachineOperand::Reg(a), MachineOperand::Reg(b)) => a == b,
(MachineOperand::Reg(_), MachineOperand::Imm(v)) => {
if opcode == X86Opcode::OR as u32 || opcode == X86Opcode::XOR as u32 {
*v == 0
} else if opcode == X86Opcode::AND as u32 {
*v == u64::MAX as i64 || *v == 0xFFFF_FFFF
} else {
false
}
}
_ => false,
}
}
fn is_lea_noop(&self, instr: &MachineInstr) -> bool {
if instr.opcode != X86Opcode::LEA as u32 {
return false;
}
if instr.operands.len() < 2 {
return false;
}
let dest = match &instr.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return false,
};
match &instr.operands[1] {
MachineOperand::Reg(src) => *src == dest,
MachineOperand::Mem { base, offset, .. } => base.0 == dest.0 && *offset == 0,
_ => false,
}
}
fn try_mov_movzx_combine(&self, block: &mut MachineBasicBlock, idx: usize) -> bool {
if idx + 1 >= block.instructions.len() {
return false;
}
let first = &block.instructions[idx];
if first.opcode != X86Opcode::MOV as u32 {
return false;
}
if first.operands.len() < 2 {
return false;
}
let is_reg_to_reg = matches!(
(&first.operands[0], &first.operands[1]),
(MachineOperand::Reg(_), MachineOperand::Reg(_))
);
if !is_reg_to_reg {
return false;
}
block.instructions[idx].opcode = X86Opcode::MOVZX as u32;
true
}
fn try_shift_combine(&self, block: &mut MachineBasicBlock, idx: usize) -> bool {
if idx + 1 >= block.instructions.len() {
return false;
}
let first = &block.instructions[idx];
let second = &block.instructions[idx + 1];
if first.opcode != X86Opcode::SHL as u32 || second.opcode != X86Opcode::SHR as u32 {
return false;
}
if first.operands.len() < 2 || second.operands.len() < 2 {
return false;
}
let reg1 = match &first.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return false,
};
let reg2 = match &second.operands[0] {
MachineOperand::Reg(r) => *r,
_ => return false,
};
if reg1 != reg2 {
return false;
}
let n = match (&first.operands[1], &second.operands[1]) {
(MachineOperand::Imm(a), MachineOperand::Imm(b)) if a == b => *a,
_ => return false,
};
let mask = !((1u64 << n) - 1) & 0xFFFF_FFFF_FFFF_FFFF;
block.instructions[idx].opcode = X86Opcode::AND as u32;
block.instructions[idx].operands[1] = MachineOperand::Imm(mask as i64);
block.instructions.remove(idx + 1);
true
}
fn is_cmov_same_src_dest(&self, instr: &MachineInstr) -> bool {
let op = instr.opcode;
let is_cmov = (X86Opcode::CMOVO as u32..=X86Opcode::CMOVG as u32).contains(&op);
if !is_cmov || instr.operands.len() < 2 {
return false;
}
matches!(
(&instr.operands[0], &instr.operands[1]),
(MachineOperand::Reg(a), MachineOperand::Reg(b)) if a == b
)
}
}
impl Default for X86PeepholeOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86BranchFolding {
pub branches_folded: usize,
pub tail_merged_blocks: usize,
pub optimize_jump_tables: bool,
}
impl X86BranchFolding {
pub fn new() -> Self {
Self {
branches_folded: 0,
tail_merged_blocks: 0,
optimize_jump_tables: true,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.branches_folded = 0;
self.remove_fallthrough_branches(mf);
self.redirect_branch_chains(mf);
self.thread_jumps(mf);
self.tail_merge_blocks(mf);
if self.optimize_jump_tables {
self.optimize_jump_tables_in_func(mf);
}
}
fn remove_fallthrough_branches(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len().saturating_sub(1) {
let cur_id = mf.blocks[i].id;
let next_id = mf.blocks[i + 1].id;
let cur_block = match mf.get_block(cur_id) {
Some(b) => b,
None => continue,
};
if cur_block.successors.len() == 1
&& cur_block.successors[0] == next_id
&& !cur_block.instructions.is_empty()
{
let last = &cur_block.instructions[cur_block.instructions.len() - 1];
if last.opcode == X86Opcode::JMP as u32 {
if let Some(block) = mf.get_block_mut(cur_id) {
block.instructions.pop();
self.branches_folded += 1;
}
}
}
}
}
fn redirect_branch_chains(&mut self, mf: &mut MachineFunction) {
let mut jmp_targets: HashMap<u32, u32> = HashMap::new();
for block in &mf.blocks {
if block.successors.len() == 1 && !block.instructions.is_empty() {
let last = &block.instructions[block.instructions.len() - 1];
if last.opcode == X86Opcode::JMP as u32 && !last.operands.is_empty() {
if let MachineOperand::Block(target) = last.operands[0] {
jmp_targets.insert(block.id, target);
}
}
}
}
let mut final_targets: HashMap<u32, u32> = HashMap::new();
for (&from, &to) in &jmp_targets {
let mut current = to;
let mut visited = HashSet::new();
visited.insert(from);
while let Some(&next) = jmp_targets.get(¤t) {
if visited.contains(&next) {
break;
}
visited.insert(current);
current = next;
}
final_targets.insert(from, current);
}
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
let successors: Vec<u32> = mf
.block_by_id(block_id)
.map(|b| b.successors.clone())
.unwrap_or_default();
for &succ in &successors {
if let Some(&new_target) = final_targets.get(&succ) {
if new_target != succ {
if let Some(block) = mf.get_block_mut(block_id) {
if let Some(pos) = block.successors.iter().position(|&s| s == succ) {
block.successors[pos] = new_target;
}
for instr in &mut block.instructions {
for op in &mut instr.operands {
if let MachineOperand::Block(b) = op {
if *b == succ {
*b = new_target;
self.branches_folded += 1;
}
}
}
}
}
if let Some(old_pred) = mf.get_block_mut(succ) {
old_pred.predecessors.retain(|&p| p != block_id);
}
if let Some(new_pred) = mf.get_block_mut(new_target) {
if !new_pred.predecessors.contains(&block_id) {
new_pred.predecessors.push(block_id);
}
}
}
}
}
}
}
fn thread_jumps(&mut self, mf: &mut MachineFunction) {
let empty_branches: HashSet<u32> = mf
.blocks
.iter()
.filter(|b| {
b.instructions.len() == 1
&& b.instructions[0].opcode == X86Opcode::JMP as u32
&& b.successors.len() == 1
})
.map(|b| b.id)
.collect();
for &empty_id in &empty_branches {
let target = mf
.block_by_id(empty_id)
.and_then(|b| b.successors.first())
.copied()
.unwrap_or(0);
let preds: Vec<u32> = mf
.block_by_id(empty_id)
.map(|b| b.predecessors.clone())
.unwrap_or_default();
for pred in &preds {
if let Some(pred_block) = mf.get_block_mut(*pred) {
if let Some(pos) = pred_block.successors.iter().position(|&s| s == empty_id) {
pred_block.successors[pos] = target;
}
for instr in &mut pred_block.instructions {
for op in &mut instr.operands {
if let MachineOperand::Block(b) = op {
if *b == empty_id {
*b = target;
self.branches_folded += 1;
}
}
}
}
}
}
if let Some(target_block) = mf.get_block_mut(target) {
target_block.predecessors.retain(|&p| p != empty_id);
for pred in &preds {
if !target_block.predecessors.contains(pred) {
target_block.predecessors.push(*pred);
}
}
}
if let Some(empty_block) = mf.get_block_mut(empty_id) {
empty_block.predecessors.clear();
}
}
}
fn tail_merge_blocks(&mut self, mf: &mut MachineFunction) {
let mut merge_candidates: Vec<(u32, u32)> = Vec::new();
let mut by_hash: HashMap<u64, Vec<u32>> = HashMap::new();
for block in &mf.blocks {
let hash = self.block_instruction_hash(block);
if hash != 0 {
by_hash.entry(hash).or_default().push(block.id);
}
}
for block_ids in by_hash.values() {
if block_ids.len() < 2 {
continue;
}
for i in 0..block_ids.len() {
for j in i + 1..block_ids.len() {
let a = mf.block_by_id(block_ids[i]);
let b = mf.block_by_id(block_ids[j]);
if let (Some(ba), Some(bb)) = (a, b) {
if self.blocks_are_identical(ba, bb) {
merge_candidates.push((block_ids[i], block_ids[j]));
}
}
}
}
}
for (keep, remove) in merge_candidates {
self.merge_block_into(mf, keep, remove);
self.tail_merged_blocks += 1;
}
}
fn block_instruction_hash(&self, block: &MachineBasicBlock) -> u64 {
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
let mut hasher = DefaultHasher::new();
for instr in &block.instructions {
instr.opcode.hash(&mut hasher);
}
block.successors.hash(&mut hasher);
hasher.finish()
}
fn blocks_are_identical(&self, a: &MachineBasicBlock, b: &MachineBasicBlock) -> bool {
if a.instructions.len() != b.instructions.len() {
return false;
}
if a.successors != b.successors {
return false;
}
a.instructions
.iter()
.zip(b.instructions.iter())
.all(|(ia, ib)| ia.is_identical_to(ib))
}
fn merge_block_into(&self, mf: &mut MachineFunction, keep: u32, remove: u32) {
let preds: Vec<u32> = mf
.block_by_id(remove)
.map(|b| b.predecessors.clone())
.unwrap_or_default();
for pred in &preds {
if let Some(pred_block) = mf.get_block_mut(*pred) {
if let Some(pos) = pred_block.successors.iter().position(|&s| s == remove) {
pred_block.successors[pos] = keep;
}
for instr in &mut pred_block.instructions {
for op in &mut instr.operands {
if let MachineOperand::Block(b) = op {
if *b == remove {
*b = keep;
}
}
}
}
}
}
if let Some(keep_block) = mf.get_block_mut(keep) {
for pred in &preds {
if !keep_block.predecessors.contains(pred) {
keep_block.predecessors.push(*pred);
}
}
}
}
fn optimize_jump_tables_in_func(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
let successors = mf
.block_by_id(block_id)
.map(|b| b.successors.clone())
.unwrap_or_default();
if successors.len() <= 2 {
continue;
}
let mut counts: HashMap<u32, usize> = HashMap::new();
for &s in &successors {
*counts.entry(s).or_default() += 1;
}
if counts.len() <= 2 {
let dominant = counts
.iter()
.max_by_key(|&(_, &c)| c)
.map(|(&k, _)| k)
.unwrap_or(0);
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => continue,
};
block
.instructions
.retain(|instr| instr.opcode != X86Opcode::JMP as u32);
let mut jmp = MachineInstr::new(X86Opcode::JMP as u32);
jmp.flags.is_terminator = true;
jmp.flags.is_branch = true;
jmp.flags.is_barrier = true;
jmp.operands.push(MachineOperand::Block(dominant));
block.instructions.push(jmp);
block.successors = vec![dominant];
self.branches_folded += 1;
}
}
}
}
impl Default for X86BranchFolding {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineVerifier {
pub errors: Vec<String>,
pub warnings: Vec<String>,
pub blocks_verified: usize,
pub instructions_verified: usize,
}
impl X86MachineVerifier {
pub fn new() -> Self {
Self {
errors: Vec::new(),
warnings: Vec::new(),
blocks_verified: 0,
instructions_verified: 0,
}
}
pub fn verify(&mut self, mf: &MachineFunction) -> bool {
self.errors.clear();
self.warnings.clear();
self.blocks_verified = 0;
self.instructions_verified = 0;
self.verify_cfg_integrity(mf);
self.verify_block_structure(mf);
self.verify_instruction_properties(mf);
self.verify_register_liveness(mf);
self.verify_ssa_property(mf);
self.verify_calling_convention(mf);
self.blocks_verified = mf.blocks.len();
self.errors.is_empty()
}
fn verify_cfg_integrity(&mut self, mf: &MachineFunction) {
let mut pred_map: HashMap<u32, HashSet<u32>> = HashMap::new();
for block in &mf.blocks {
for &succ in &block.successors {
pred_map.entry(succ).or_default().insert(block.id);
}
}
for block in &mf.blocks {
for &succ in &block.successors {
if !pred_map
.get(&succ)
.map(|s| s.contains(&block.id))
.unwrap_or(false)
{
self.errors.push(format!(
"CFG inconsistency: block {} has successor {} but {} is not in {}'s predecessor list",
block.id, succ, block.id, succ
));
}
}
for &pred in &block.predecessors {
let pred_has_succ = mf
.block_by_id(pred)
.map(|b| b.successors.contains(&block.id))
.unwrap_or(false);
if !pred_has_succ {
self.errors.push(format!(
"CFG inconsistency: block {} has predecessor {} but {}'s successors don't include {}",
block.id, pred, pred, block.id
));
}
}
}
if let Some(entry) = mf.block_by_id(mf.entry_block) {
if !entry.predecessors.is_empty() && !mf.blocks.is_empty() {
self.warnings.push(format!(
"Entry block {} has {} predecessor(s)",
mf.entry_block,
entry.predecessors.len()
));
}
}
}
fn verify_block_structure(&mut self, mf: &MachineFunction) {
for block in &mf.blocks {
if !block.successors.is_empty() {
let has_terminator = block
.instructions
.last()
.map(|i| i.flags.is_terminator)
.unwrap_or(false);
if !has_terminator {
self.errors.push(format!(
"Block {} has successors but no terminator instruction",
block.name
));
}
}
if block.successors.is_empty() && !block.is_exit {
let has_ret = block
.instructions
.last()
.map(|i| i.flags.is_return)
.unwrap_or(false);
if !has_ret {
self.warnings.push(format!(
"Block {} has no successors and no return",
block.name
));
}
}
for instr in &block.instructions {
if instr.flags.is_branch && !instr.flags.is_indirect_branch {
let has_label = instr
.operands
.iter()
.any(|op| matches!(op, MachineOperand::Block(_)));
if !has_label && !instr.flags.is_return {
self.warnings.push(format!(
"Branch instruction in block {} has no label operand",
block.name
));
}
}
}
}
}
fn verify_instruction_properties(&mut self, mf: &MachineFunction) {
for block in &mf.blocks {
for (pos, instr) in block.instructions.iter().enumerate() {
self.instructions_verified += 1;
if instr.opcode == 0 {
self.warnings.push(format!(
"Instruction in block {} has invalid opcode 0",
block.name
));
}
if instr.flags.is_terminator {
let is_last = pos == block.instructions.len().saturating_sub(1);
if !is_last {
self.errors.push(format!(
"Terminator in block {} is not the last instruction",
block.name
));
}
}
}
}
}
fn verify_register_liveness(&mut self, mf: &MachineFunction) {
for block in &mf.blocks {
let mut defined: HashSet<MCRegister> = HashSet::new();
for instr in &block.instructions {
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
let is_also_def = instr.writes_register(*reg);
if !is_also_def && !defined.contains(reg) {
self.warnings.push(format!(
"Register {:?} used before definition in block {} (may be live-in)",
reg, block.name
));
}
}
}
if let Some(def_reg) = get_def_reg(instr) {
defined.insert(def_reg);
}
}
}
}
fn verify_ssa_property(&mut self, mf: &MachineFunction) {
let mut def_sites: HashMap<MCRegister, Vec<(u32, usize)>> = HashMap::new();
for block in &mf.blocks {
for (idx, instr) in block.instructions.iter().enumerate() {
if let Some(def_reg) = get_def_reg(instr) {
def_sites.entry(def_reg).or_default().push((block.id, idx));
}
}
}
for (reg, sites) in &def_sites {
if sites.len() > 1 {
self.errors.push(format!(
"SSA violation: register {:?} defined {} times",
reg,
sites.len()
));
}
}
}
fn verify_calling_convention(&mut self, mf: &MachineFunction) {
if let Some(_entry) = mf.block_by_id(mf.entry_block) {
}
for &exit_id in &mf.exit_blocks {
if let Some(_exit) = mf.block_by_id(exit_id) {
}
}
}
pub fn print_diagnostics(&self) {
for err in &self.errors {
eprintln!("[VERIFIER ERROR] {}", err);
}
for warn in &self.warnings {
eprintln!("[VERIFIER WARNING] {}", warn);
}
if self.errors.is_empty() && self.warnings.is_empty() {
eprintln!(
"[VERIFIER] All checks passed ({} blocks, {} instructions)",
self.blocks_verified, self.instructions_verified
);
}
}
}
impl Default for X86MachineVerifier {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineTraceMetrics {
pub traces_analyzed: usize,
pub total_cycles: u64,
pub trace_cycles: Vec<u64>,
pub latencies: HashMap<u32, u32>,
pub resource_usage: HashMap<String, u64>,
}
impl X86MachineTraceMetrics {
pub fn new() -> Self {
let mut metrics = Self {
traces_analyzed: 0,
total_cycles: 0,
trace_cycles: Vec::new(),
latencies: HashMap::new(),
resource_usage: HashMap::new(),
};
metrics.set_default_latencies();
metrics
}
fn set_default_latencies(&mut self) {
for &op in &[
X86Opcode::ADD,
X86Opcode::SUB,
X86Opcode::AND,
X86Opcode::OR,
X86Opcode::XOR,
X86Opcode::CMP,
X86Opcode::TEST,
X86Opcode::MOV,
X86Opcode::MOVSX,
X86Opcode::MOVZX,
X86Opcode::LEA,
X86Opcode::INC,
X86Opcode::DEC,
X86Opcode::NEG,
X86Opcode::NOT,
] {
self.latencies.insert(op as u32, 1);
}
for &op in &[
X86Opcode::SHL,
X86Opcode::SHR,
X86Opcode::SAR,
X86Opcode::ROL,
X86Opcode::ROR,
] {
self.latencies.insert(op as u32, 1);
}
self.latencies.insert(X86Opcode::IMUL as u32, 3);
self.latencies.insert(X86Opcode::MUL as u32, 4);
self.latencies.insert(X86Opcode::IDIV as u32, 26);
self.latencies.insert(X86Opcode::DIV as u32, 26);
for op in X86Opcode::CMOVO as u32..=X86Opcode::CMOVG as u32 {
self.latencies.insert(op, 2);
}
self.latencies.insert(X86Opcode::ADDSS as u32, 3);
self.latencies.insert(X86Opcode::ADDSD as u32, 3);
self.latencies.insert(X86Opcode::MULSS as u32, 4);
self.latencies.insert(X86Opcode::MULSD as u32, 4);
self.latencies.insert(X86Opcode::DIVSS as u32, 11);
self.latencies.insert(X86Opcode::DIVSD as u32, 13);
self.latencies.insert(X86Opcode::ADDPS as u32, 3);
self.latencies.insert(X86Opcode::ADDPD as u32, 3);
self.latencies.insert(X86Opcode::MULPS as u32, 4);
self.latencies.insert(X86Opcode::MULPD as u32, 4);
self.latencies.insert(X86Opcode::VADDPS as u32, 3);
self.latencies.insert(X86Opcode::VADDPD as u32, 3);
self.latencies.insert(X86Opcode::VMULPS as u32, 4);
self.latencies.insert(X86Opcode::VMULPD as u32, 4);
}
pub fn analyze_trace(
&mut self,
instructions: &[MachineInstr],
_live_ins: &HashSet<MCRegister>,
) -> u64 {
if instructions.is_empty() {
return 0;
}
let n = instructions.len();
let mut height: Vec<u64> = vec![0; n];
let mut last_def: HashMap<MCRegister, usize> = HashMap::new();
for i in 0..n {
let instr = &instructions[i];
let latency = self.get_latency(instr);
let mut input_height = 0u64;
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
if let Some(&producer_idx) = last_def.get(reg) {
input_height = input_height.max(height[producer_idx]);
}
}
}
height[i] = input_height + latency as u64;
if let Some(def_reg) = get_def_reg(instr) {
last_def.insert(def_reg, i);
}
}
let mut depth: Vec<u64> = vec![0; n];
let mut next_use: HashMap<MCRegister, usize> = HashMap::new();
for i in (0..n).rev() {
let instr = &instructions[i];
let mut output_depth = 0u64;
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
if let Some(&consumer_idx) = next_use.get(reg) {
output_depth = output_depth.max(depth[consumer_idx]);
}
}
}
let latency = self.get_latency(instr);
depth[i] = output_depth + latency as u64;
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
next_use.insert(*reg, i);
}
}
}
let critical_path = height.iter().max().copied().unwrap_or(0);
self.trace_cycles.push(critical_path);
self.total_cycles += critical_path;
self.traces_analyzed += 1;
critical_path
}
fn get_latency(&self, instr: &MachineInstr) -> u32 {
self.latencies
.get(&instr.opcode)
.copied()
.unwrap_or(DEFAULT_X86_LATENCY)
}
pub fn get_trace_cycles(&self) -> u64 {
self.trace_cycles.last().copied().unwrap_or(0)
}
pub fn estimate_resource_pressure(&mut self, instructions: &[MachineInstr]) -> u64 {
let mut port_pressure: HashMap<String, u64> = HashMap::new();
let ports = ["p0", "p1", "p23", "p4", "p5", "p6", "p7"];
for port in &ports {
port_pressure.insert(port.to_string(), 0);
}
for instr in instructions {
if instr.flags.is_load {
*port_pressure.get_mut("p23").unwrap() += 1;
}
if instr.flags.is_store {
*port_pressure.get_mut("p4").unwrap() += 1;
*port_pressure.get_mut("p7").unwrap() += 1;
}
if instr.flags.is_branch {
*port_pressure.get_mut("p6").unwrap() += 1;
}
if instr.opcode == X86Opcode::LEA as u32 {
*port_pressure.get_mut("p1").unwrap() += 1;
*port_pressure.get_mut("p5").unwrap() += 1;
}
if !instr.flags.is_load && !instr.flags.is_store && !instr.flags.is_branch {
*port_pressure.get_mut("p0").unwrap() += 1;
}
}
let max_pressure = port_pressure.values().max().copied().unwrap_or(0);
self.resource_usage = port_pressure;
max_pressure
}
}
impl Default for X86MachineTraceMetrics {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineOutliner {
pub min_length: usize,
pub min_occurrences: usize,
pub allow_cross_block: bool,
pub candidates: Vec<OutlineCandidateX86>,
}
#[derive(Debug, Clone)]
pub struct OutlineCandidateX86 {
pub hash: u64,
pub length: usize,
pub savings: usize,
pub instruction_patterns: Vec<(u32, Vec<u8>)>,
pub occurrences: Vec<(u32, usize)>,
}
impl X86MachineOutliner {
pub fn new() -> Self {
Self {
min_length: 3,
min_occurrences: 2,
allow_cross_block: false,
candidates: Vec::new(),
}
}
pub fn scan_function(&mut self, mf: &MachineFunction) {
self.candidates.clear();
let mut seq_map: HashMap<u64, Vec<(u32, usize)>> = HashMap::new();
for block in &mf.blocks {
for start in 0..block.instructions.len() {
let max_len = (block.instructions.len() - start).min(OUTLINER_MAX_CANDIDATE_LEN);
for len in self.min_length..=max_len {
let slice = &block.instructions[start..start + len];
let hash = Self::hash_sequence(slice);
let entry = seq_map.entry(hash).or_default();
let overlaps = entry.iter().any(|(bid, s_idx)| {
*bid == block.id
&& ((*s_idx <= start && start < *s_idx + len)
|| (start <= *s_idx && *s_idx < start + len))
});
if !overlaps {
entry.push((block.id, start));
}
}
}
}
for (hash, occurrences) in seq_map {
if occurrences.len() >= self.min_occurrences {
let first_occurrence = occurrences[0];
let length = mf
.block_by_id(first_occurrence.0)
.map(|b| {
(b.instructions.len() - first_occurrence.1).min(OUTLINER_MAX_CANDIDATE_LEN)
})
.unwrap_or(self.min_length);
let savings = self.estimate_savings(length, occurrences.len());
if savings > OUTLINER_MIN_SAVINGS {
let patterns: Vec<(u32, Vec<u8>)> = mf
.block_by_id(first_occurrence.0)
.map(|b| {
let end = (first_occurrence.1 + length).min(b.instructions.len());
b.instructions[first_occurrence.1..end]
.iter()
.map(|i| {
let pattern: Vec<u8> = i
.operands
.iter()
.map(|op| match op {
MachineOperand::Reg(r) => r.0 as u8,
MachineOperand::Imm(v) => (v & 0xFF) as u8,
_ => 0u8,
})
.collect();
(i.opcode, pattern)
})
.collect()
})
.unwrap_or_default();
self.candidates.push(OutlineCandidateX86 {
hash,
length,
savings,
instruction_patterns: patterns,
occurrences,
});
}
}
}
self.candidates
.sort_by_key(|c| std::cmp::Reverse(c.savings));
self.resolve_overlaps();
}
fn hash_sequence(instrs: &[MachineInstr]) -> u64 {
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
let mut hasher = DefaultHasher::new();
for instr in instrs {
instr.opcode.hash(&mut hasher);
for op in &instr.operands {
match op {
MachineOperand::Reg(r) => r.0.hash(&mut hasher),
MachineOperand::Imm(v) => v.hash(&mut hasher),
MachineOperand::Block(b) => b.hash(&mut hasher),
MachineOperand::FPImm(f) => f.to_bits().hash(&mut hasher),
MachineOperand::Mem { base, offset, .. } => {
base.0.hash(&mut hasher);
offset.hash(&mut hasher);
}
MachineOperand::Global(g) => g.hash(&mut hasher),
MachineOperand::CCMask(m) => m.hash(&mut hasher),
}
}
}
hasher.finish()
}
pub fn estimate_savings(&self, length: usize, occurrences: usize) -> usize {
let avg_instr_bytes = 3;
let call_bytes = 5;
let ret_bytes = 1;
let frame_overhead = 3;
let original_bytes = length * avg_instr_bytes * occurrences;
let outlined_bytes =
call_bytes * occurrences + length * avg_instr_bytes + ret_bytes + frame_overhead;
if original_bytes > outlined_bytes {
original_bytes - outlined_bytes
} else {
0
}
}
fn resolve_overlaps(&mut self) {
let mut used_ranges: Vec<(u32, usize, usize)> = Vec::new();
let mut kept: Vec<OutlineCandidateX86> = Vec::new();
for candidate in self.candidates.drain(..) {
let mut overlaps = false;
for &(block_id, start) in &candidate.occurrences {
let end = start + candidate.length;
if used_ranges
.iter()
.any(|(bid, s, e)| *bid == block_id && start < *e && *s < end)
{
overlaps = true;
break;
}
}
if !overlaps {
for &(block_id, start) in &candidate.occurrences {
used_ranges.push((block_id, start, start + candidate.length));
}
kept.push(candidate);
}
}
self.candidates = kept;
}
pub fn scan_functions(&mut self, functions: &[&MachineFunction]) {
self.candidates.clear();
let mut global_map: HashMap<u64, Vec<(usize, u32, usize)>> = HashMap::new();
for (fi, mf) in functions.iter().enumerate() {
for block in &mf.blocks {
for start in 0..block.instructions.len() {
let max_len =
(block.instructions.len() - start).min(OUTLINER_MAX_CANDIDATE_LEN);
for len in self.min_length..=max_len {
let slice = &block.instructions[start..start + len];
let hash = Self::hash_sequence(slice);
global_map
.entry(hash)
.or_default()
.push((fi, block.id, start));
}
}
}
}
for (hash, occurrences) in global_map {
if occurrences.len() >= self.min_occurrences {
let (fi, bid, start) = occurrences[0];
let mf = functions[fi];
let length = mf
.block_by_id(bid)
.map(|b| (b.instructions.len() - start).min(OUTLINER_MAX_CANDIDATE_LEN))
.unwrap_or(self.min_length);
let savings = self.estimate_savings(length, occurrences.len());
if savings > OUTLINER_MIN_SAVINGS {
self.candidates.push(OutlineCandidateX86 {
hash,
length,
savings,
instruction_patterns: Vec::new(),
occurrences: occurrences
.iter()
.map(|(_, bid, start)| (*bid, *start))
.collect(),
});
}
}
}
self.candidates
.sort_by_key(|c| std::cmp::Reverse(c.savings));
}
pub fn total_savings(&self) -> usize {
self.candidates.iter().map(|c| c.savings).sum()
}
}
impl Default for X86MachineOutliner {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86CodeGenOpt2 {
pub block_placement: X86MachineBlockPlacement,
pub branch_folding: X86BranchFolding,
pub cse: X86MachineCSE,
pub licm: X86MachineLICM,
pub sinking: X86MachineSinking,
pub combiner: X86MachineCombiner,
pub peephole: X86PeepholeOptimizer,
pub trace_metrics: X86MachineTraceMetrics,
pub verifier: X86MachineVerifier,
pub outliner: X86MachineOutliner,
pub verify_after_each_pass: bool,
pub max_iterations: usize,
}
impl X86CodeGenOpt2 {
pub fn new() -> Self {
Self {
block_placement: X86MachineBlockPlacement::default(),
branch_folding: X86BranchFolding::default(),
cse: X86MachineCSE::default(),
licm: X86MachineLICM::default(),
sinking: X86MachineSinking::default(),
combiner: X86MachineCombiner::default(),
peephole: X86PeepholeOptimizer::default(),
trace_metrics: X86MachineTraceMetrics::default(),
verifier: X86MachineVerifier::default(),
outliner: X86MachineOutliner::default(),
verify_after_each_pass: false,
max_iterations: 3,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) -> X86Opt2Stats {
let mut stats = X86Opt2Stats::new();
for _iter in 0..self.max_iterations {
let stats_before = stats.clone();
self.branch_folding.run(mf);
stats.branches_folded += self.branch_folding.branches_folded;
stats.tail_merged += self.branch_folding.tail_merged_blocks;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.peephole.run(mf);
stats.peephole_redundant_movs += self.peephole.redundant_movs_eliminated;
stats.peephole_cmp_to_test += self.peephole.cmp_zero_to_test;
stats.peephole_identity += self.peephole.identity_ops_removed;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.cse.run(mf);
stats.cse_eliminated += self.cse.eliminated;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.licm.run(mf);
stats.licm_hoisted += self.licm.hoisted;
stats.licm_sunk += self.licm.sunk;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.sinking.run(mf);
stats.sinking_sunk += self.sinking.sunk;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.combiner.run(mf);
stats.combiner_combined += self.combiner.combined;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.block_placement.run(mf);
stats.fallthroughs_created += self.block_placement.fallthroughs_created;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
self.branch_folding.run(mf);
stats.branches_folded += self.branch_folding.branches_folded;
if self.verify_after_each_pass {
self.verifier.verify(mf);
}
if stats == stats_before && _iter > 0 {
break;
}
}
self.outliner.scan_function(mf);
stats.outline_candidates = self.outliner.candidates.len();
stats.outline_savings = self.outliner.total_savings();
self.verifier.verify(mf);
stats.verification_errors = self.verifier.errors.len();
for block in &mf.blocks {
self.trace_metrics
.analyze_trace(&block.instructions, &HashSet::new());
}
stats.critical_path_cycles = self.trace_metrics.total_cycles;
stats.iterations = self.max_iterations;
stats
}
pub fn run_post_ra(&mut self, mf: &mut MachineFunction) -> X86Opt2Stats {
let mut stats = X86Opt2Stats::new();
self.branch_folding.run(mf);
stats.branches_folded = self.branch_folding.branches_folded;
self.peephole.run(mf);
stats.peephole_redundant_movs = self.peephole.redundant_movs_eliminated;
stats.peephole_cmp_to_test = self.peephole.cmp_zero_to_test;
self.combiner.run(mf);
stats.combiner_combined = self.combiner.combined;
self.verifier.verify(mf);
stats.verification_errors = self.verifier.errors.len();
stats
}
pub fn print_stats(&self, stats: &X86Opt2Stats) {
println!("=== X86CodeGenOpt2 Statistics ===");
println!(" Branches folded: {}", stats.branches_folded);
println!(" Tail-merged blocks: {}", stats.tail_merged);
println!(" CSE eliminated: {}", stats.cse_eliminated);
println!(" LICM hoisted: {}", stats.licm_hoisted);
println!(" LICM sunk: {}", stats.licm_sunk);
println!(" Sinking sunk: {}", stats.sinking_sunk);
println!(" Combiner combined: {}", stats.combiner_combined);
println!(" Fallthroughs created: {}", stats.fallthroughs_created);
println!(
" Peephole redundant MOVs: {}",
stats.peephole_redundant_movs
);
println!(" Peephole CMP→TEST: {}", stats.peephole_cmp_to_test);
println!(" Peephole identity ops: {}", stats.peephole_identity);
println!(" Outline candidates: {}", stats.outline_candidates);
println!(" Outline savings (bytes): {}", stats.outline_savings);
println!(" Critical path cycles: {}", stats.critical_path_cycles);
println!(" Verification errors: {}", stats.verification_errors);
println!(" Iterations: {}", stats.iterations);
println!("===================================");
}
}
impl Default for X86CodeGenOpt2 {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct X86Opt2Stats {
pub branches_folded: usize,
pub tail_merged: usize,
pub cse_eliminated: usize,
pub licm_hoisted: usize,
pub licm_sunk: usize,
pub sinking_sunk: usize,
pub combiner_combined: usize,
pub fallthroughs_created: usize,
pub peephole_redundant_movs: usize,
pub peephole_cmp_to_test: usize,
pub peephole_identity: usize,
pub outline_candidates: usize,
pub outline_savings: usize,
pub critical_path_cycles: u64,
pub verification_errors: usize,
pub iterations: usize,
}
impl X86Opt2Stats {
pub fn new() -> Self {
Self {
branches_folded: 0,
tail_merged: 0,
cse_eliminated: 0,
licm_hoisted: 0,
licm_sunk: 0,
sinking_sunk: 0,
combiner_combined: 0,
fallthroughs_created: 0,
peephole_redundant_movs: 0,
peephole_cmp_to_test: 0,
peephole_identity: 0,
outline_candidates: 0,
outline_savings: 0,
critical_path_cycles: 0,
verification_errors: 0,
iterations: 0,
}
}
}
impl Default for X86Opt2Stats {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86RegisterPressureTracker {
pub gpr_pressure: usize,
pub xmm_pressure: usize,
pub max_gpr_pressure: usize,
pub max_xmm_pressure: usize,
pub block_live_in: HashMap<u32, HashSet<MCRegister>>,
pub block_live_out: HashMap<u32, HashSet<MCRegister>>,
reg_classes: HashMap<MCRegister, RegClassType>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RegClassType {
GPR,
XMM,
Other,
}
impl X86RegisterPressureTracker {
pub fn new() -> Self {
Self {
gpr_pressure: 0,
xmm_pressure: 0,
max_gpr_pressure: 0,
max_xmm_pressure: 0,
block_live_in: HashMap::new(),
block_live_out: HashMap::new(),
reg_classes: HashMap::new(),
}
}
pub fn compute_liveness(&mut self, mf: &MachineFunction) {
self.block_live_in.clear();
self.block_live_out.clear();
let mut block_gen: HashMap<u32, HashSet<MCRegister>> = HashMap::new();
let mut block_kill: HashMap<u32, HashSet<MCRegister>> = HashMap::new();
for block in &mf.blocks {
let mut r#gen = HashSet::new();
let mut kill = HashSet::new();
for instr in block.instructions.iter().rev() {
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
if !kill.contains(reg) {
r#gen.insert(*reg);
}
}
}
if let Some(def_reg) = get_def_reg(instr) {
kill.insert(def_reg);
}
}
block_gen.insert(block.id, r#gen);
block_kill.insert(block.id, kill);
self.block_live_in.insert(block.id, HashSet::new());
self.block_live_out.insert(block.id, HashSet::new());
}
let mut changed = true;
let mut iter = 0;
while changed && iter < 100 {
changed = false;
iter += 1;
for block in mf.blocks.iter().rev() {
let mut new_live_out: HashSet<MCRegister> = HashSet::new();
for &succ in &block.successors {
if let Some(succ_live_in) = self.block_live_in.get(&succ) {
new_live_out.extend(succ_live_in);
}
}
let old_live_out = self
.block_live_out
.get(&block.id)
.cloned()
.unwrap_or_default();
if new_live_out != old_live_out {
self.block_live_out.insert(block.id, new_live_out.clone());
changed = true;
}
let r#gen = block_gen.get(&block.id).cloned().unwrap_or_default();
let kill = block_kill.get(&block.id).cloned().unwrap_or_default();
let mut new_live_in = r#gen;
for reg in &new_live_out {
if !kill.contains(reg) {
new_live_in.insert(*reg);
}
}
let old_live_in = self
.block_live_in
.get(&block.id)
.cloned()
.unwrap_or_default();
if new_live_in != old_live_in {
self.block_live_in.insert(block.id, new_live_in);
changed = true;
}
}
}
for block in &mf.blocks {
let mut live: HashSet<MCRegister> = self
.block_live_out
.get(&block.id)
.cloned()
.unwrap_or_default();
for instr in block.instructions.iter().rev() {
let mut gpr_count = 0usize;
let mut xmm_count = 0usize;
for reg in &live {
match self.classify_reg(*reg) {
RegClassType::GPR => gpr_count += 1,
RegClassType::XMM => xmm_count += 1,
RegClassType::Other => {}
}
}
self.max_gpr_pressure = self.max_gpr_pressure.max(gpr_count);
self.max_xmm_pressure = self.max_xmm_pressure.max(xmm_count);
if let Some(def_reg) = get_def_reg(instr) {
live.remove(&def_reg);
}
for op in &instr.operands {
if let MachineOperand::Reg(reg) = op {
live.insert(*reg);
}
}
}
}
self.gpr_pressure = self.max_gpr_pressure;
self.xmm_pressure = self.max_xmm_pressure;
}
fn classify_reg(&self, reg: MCRegister) -> RegClassType {
if let Some(cls) = self.reg_classes.get(®) {
return *cls;
}
match reg.0 {
0..=15 => RegClassType::GPR,
16..=47 => RegClassType::XMM,
_ => RegClassType::Other,
}
}
pub fn can_hoist_gpr(&self, limit: usize) -> bool {
self.gpr_pressure < limit
}
pub fn can_hoist_xmm(&self, limit: usize) -> bool {
self.xmm_pressure < limit
}
pub fn pressure_at_block_exit(&self, block_id: u32) -> (usize, usize) {
let live_out = self
.block_live_out
.get(&block_id)
.cloned()
.unwrap_or_default();
let mut gpr = 0;
let mut xmm = 0;
for reg in &live_out {
match self.classify_reg(*reg) {
RegClassType::GPR => gpr += 1,
RegClassType::XMM => xmm += 1,
RegClassType::Other => {}
}
}
(gpr, xmm)
}
}
impl Default for X86RegisterPressureTracker {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MacroFusionPrep {
pub fusible_pairs: usize,
pub reordered_for_fusion: usize,
}
impl X86MacroFusionPrep {
pub fn new() -> Self {
Self {
fusible_pairs: 0,
reordered_for_fusion: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.fusible_pairs = 0;
self.reordered_for_fusion = 0;
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.process_block(mf, block_id);
}
}
fn process_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut i = 0;
while i + 1 < block.instructions.len() {
let first_op = block.instructions[i].opcode;
let second_op = block.instructions[i + 1].opcode;
let first_is_cmp_test =
first_op == X86Opcode::CMP as u32 || first_op == X86Opcode::TEST as u32;
let second_is_jcc = Self::is_jcc_opcode(second_op);
if first_is_cmp_test && second_is_jcc {
block.instructions[i].flags.is_bundle_head = true;
block.instructions[i + 1].flags.is_inside_bundle = true;
self.fusible_pairs += 1;
i += 2;
continue;
}
if first_is_cmp_test
&& i + 2 < block.instructions.len()
&& Self::is_jcc_opcode(block.instructions[i + 2].opcode)
{
let middle = &block.instructions[i + 1];
if !Self::sets_flags_full(middle.opcode) && !Self::depends_on_flags(middle) {
block.instructions.swap(i + 1, i + 2);
block.instructions[i].flags.is_bundle_head = true;
block.instructions[i + 1].flags.is_inside_bundle = true;
self.reordered_for_fusion += 1;
self.fusible_pairs += 1;
}
}
i += 1;
}
}
fn is_jcc_opcode(opcode: u32) -> bool {
(X86Opcode::JO as u32..=X86Opcode::JG as u32).contains(&opcode)
}
fn sets_flags_full(opcode: u32) -> bool {
matches!(
opcode,
_ if opcode == X86Opcode::ADD as u32
|| opcode == X86Opcode::SUB as u32
|| opcode == X86Opcode::AND as u32
|| opcode == X86Opcode::OR as u32
|| opcode == X86Opcode::XOR as u32
|| opcode == X86Opcode::CMP as u32
|| opcode == X86Opcode::TEST as u32
|| opcode == X86Opcode::INC as u32
|| opcode == X86Opcode::DEC as u32
|| opcode == X86Opcode::NEG as u32
)
}
fn depends_on_flags(instr: &MachineInstr) -> bool {
let op = instr.opcode;
(X86Opcode::CMOVO as u32..=X86Opcode::CMOVG as u32).contains(&op)
|| (X86Opcode::SETO as u32..=X86Opcode::SETG as u32).contains(&op)
|| op == X86Opcode::ADC as u32
|| op == X86Opcode::SBB as u32
}
}
impl Default for X86MacroFusionPrep {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86FlagsOptimizer {
pub flags_removed: usize,
pub test_to_cmp: usize,
pub setcc_optimized: usize,
}
impl X86FlagsOptimizer {
pub fn new() -> Self {
Self {
flags_removed: 0,
test_to_cmp: 0,
setcc_optimized: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.flags_removed = 0;
self.test_to_cmp = 0;
self.setcc_optimized = 0;
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.optimize_block(mf, block_id);
}
}
fn optimize_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut i = 0;
while i < block.instructions.len() {
let opcode = block.instructions[i].opcode;
if Self::sets_flags(opcode)
&& i + 1 < block.instructions.len()
&& Self::sets_flags(block.instructions[i + 1].opcode)
{
let flags_dead = !Self::flags_used_between(&block.instructions, i + 1, i + 1);
if flags_dead {
block.instructions.remove(i);
self.flags_removed += 1;
continue;
}
}
if Self::is_setcc(opcode)
&& i + 1 < block.instructions.len()
&& block.instructions[i + 1].opcode == X86Opcode::MOVZX as u32
{
let dest32 = match block.instructions[i + 1].operands.first() {
Some(MachineOperand::Reg(r)) => *r,
_ => {
i += 1;
continue;
}
};
block.instructions[i].operands[0] = MachineOperand::Reg(dest32);
block.instructions.remove(i + 1);
self.setcc_optimized += 1;
}
i += 1;
}
}
fn sets_flags(opcode: u32) -> bool {
matches!(
opcode,
_ if opcode == X86Opcode::ADD as u32
|| opcode == X86Opcode::SUB as u32
|| opcode == X86Opcode::AND as u32
|| opcode == X86Opcode::OR as u32
|| opcode == X86Opcode::XOR as u32
|| opcode == X86Opcode::CMP as u32
|| opcode == X86Opcode::TEST as u32
|| opcode == X86Opcode::INC as u32
|| opcode == X86Opcode::DEC as u32
|| opcode == X86Opcode::NEG as u32
|| opcode == X86Opcode::ADC as u32
|| opcode == X86Opcode::SBB as u32
|| opcode == X86Opcode::SHL as u32
|| opcode == X86Opcode::SHR as u32
|| opcode == X86Opcode::SAR as u32
)
}
fn flags_used_between(instructions: &[MachineInstr], start: usize, end: usize) -> bool {
for instr in &instructions[start..end] {
let op = instr.opcode;
if (X86Opcode::CMOVO as u32..=X86Opcode::CMOVG as u32).contains(&op)
|| (X86Opcode::SETO as u32..=X86Opcode::SETG as u32).contains(&op)
|| (X86Opcode::JO as u32..=X86Opcode::JG as u32).contains(&op)
|| op == X86Opcode::ADC as u32
|| op == X86Opcode::SBB as u32
{
return true;
}
}
false
}
fn is_setcc(opcode: u32) -> bool {
(X86Opcode::SETO as u32..=X86Opcode::SETG as u32).contains(&opcode)
}
}
impl Default for X86FlagsOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86ConstantHoisting {
pub constants_hoisted: usize,
pub bytes_saved: usize,
}
impl X86ConstantHoisting {
pub fn new() -> Self {
Self {
constants_hoisted: 0,
bytes_saved: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.constants_hoisted = 0;
self.bytes_saved = 0;
let mut licm = X86MachineLICM::new();
licm.detect_loops(mf);
let loop_headers: Vec<u32> = licm.loop_info.keys().copied().collect();
let preheaders: HashMap<u32, u32> = licm.preheaders.clone();
for header in loop_headers {
let loop_blocks = licm.loop_info.get(&header).cloned().unwrap_or_default();
if let Some(&preheader_id) = preheaders.get(&header) {
self.hoist_constants_from_loop(mf, &loop_blocks, preheader_id);
}
}
}
fn hoist_constants_from_loop(
&mut self,
mf: &mut MachineFunction,
loop_blocks: &HashSet<u32>,
preheader: u32,
) {
let mut to_hoist: Vec<(u32, usize, MachineInstr)> = Vec::new();
for &block_id in loop_blocks.iter() {
if let Some(block) = mf.block_by_id(block_id) {
for (idx, instr) in block.instructions.iter().enumerate() {
if Self::is_expensive_constant_load(instr) {
to_hoist.push((block_id, idx, instr.clone()));
}
}
}
}
let mut seen: HashMap<i64, MCRegister> = HashMap::new();
let mut hoisted_set: HashSet<(u32, usize)> = HashSet::new();
for (block_id, idx, instr) in &to_hoist {
if hoisted_set.contains(&(*block_id, *idx)) {
continue;
}
if let Some(imm) = Self::get_constant(instr) {
if let Some(®) = seen.get(&imm) {
if let Some(block) = mf.get_block_mut(*block_id) {
if *idx < block.instructions.len() {
block.instructions[*idx] = make_mov_instr_imm(
block.instructions[*idx]
.operands
.first()
.and_then(|o| o.reg_value())
.unwrap_or(MCRegister(0))
.0,
imm,
);
self.bytes_saved += 8;
}
}
hoisted_set.insert((*block_id, *idx));
} else if let Some(reg) = Self::hoist_to_preheader(mf, preheader, instr) {
seen.insert(imm, reg);
self.constants_hoisted += 1;
hoisted_set.insert((*block_id, *idx));
if let Some(block) = mf.get_block_mut(*block_id) {
if *idx < block.instructions.len() {
block.instructions.remove(*idx);
}
}
}
}
}
}
fn is_expensive_constant_load(instr: &MachineInstr) -> bool {
if instr.opcode != X86Opcode::MOV as u32 {
return false;
}
if instr.operands.len() < 2 {
return false;
}
matches!(
(&instr.operands[0], &instr.operands[1]),
(MachineOperand::Reg(_), MachineOperand::Imm(v))
if *v > 0x7FFF_FFFF || *v < -0x8000_0000
)
}
fn get_constant(instr: &MachineInstr) -> Option<i64> {
instr.operands.iter().find_map(|op| {
if let MachineOperand::Imm(v) = op {
Some(*v)
} else {
None
}
})
}
fn hoist_to_preheader(
mf: &mut MachineFunction,
preheader: u32,
instr: &MachineInstr,
) -> Option<MCRegister> {
let block = mf.get_block_mut(preheader)?;
let insert_pos = if block
.instructions
.last()
.map(|i| i.flags.is_terminator)
.unwrap_or(false)
{
block.instructions.len().saturating_sub(1)
} else {
block.instructions.len()
};
let dest_reg = get_def_reg(instr)?;
let mut new_instr = instr.clone();
new_instr.operands[0] = MachineOperand::Reg(dest_reg);
block.instructions.insert(insert_pos, new_instr);
Some(dest_reg)
}
}
impl Default for X86ConstantHoisting {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86AddressModeOptimizer {
pub modes_simplified: usize,
pub enable_rip_relative: bool,
}
impl X86AddressModeOptimizer {
pub fn new() -> Self {
Self {
modes_simplified: 0,
enable_rip_relative: true,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.modes_simplified = 0;
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.optimize_block(mf, block_id);
}
}
fn optimize_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
for instr in &mut block.instructions {
for op in &mut instr.operands {
if let MachineOperand::Mem { offset, .. } = op {
if *offset == 0 {
self.modes_simplified += 1;
}
if *offset >= -128 && *offset <= 127 && *offset != 0 {
self.modes_simplified += 1;
}
}
}
}
}
pub fn can_merge_modes(a: &MachineOperand, b: &MachineOperand) -> bool {
match (a, b) {
(
MachineOperand::Mem {
base: ba,
offset: oa,
..
},
MachineOperand::Mem {
base: bb,
offset: ob,
..
},
) => ba == bb && oa == ob,
_ => false,
}
}
}
impl Default for X86AddressModeOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineCFGSimplifier {
pub blocks_merged: usize,
pub empty_blocks_removed: usize,
pub unreachable_blocks_removed: usize,
}
impl X86MachineCFGSimplifier {
pub fn new() -> Self {
Self {
blocks_merged: 0,
empty_blocks_removed: 0,
unreachable_blocks_removed: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
self.remove_unreachable_blocks(mf);
self.merge_empty_blocks(mf);
self.remove_trivial_blocks(mf);
}
fn remove_unreachable_blocks(&mut self, mf: &mut MachineFunction) {
let mut reachable = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(mf.entry_block);
reachable.insert(mf.entry_block);
while let Some(id) = queue.pop_front() {
if let Some(block) = mf.block_by_id(id) {
for &succ in &block.successors {
if !reachable.contains(&succ) {
reachable.insert(succ);
queue.push_back(succ);
}
}
}
}
let unreachable: Vec<u32> = mf
.blocks
.iter()
.map(|b| b.id)
.filter(|id| !reachable.contains(id) && *id != mf.entry_block)
.collect();
for id in unreachable {
mf.blocks.retain(|b| b.id != id);
mf.exit_blocks.retain(|&e| e != id);
self.unreachable_blocks_removed += 1;
}
for block in &mut mf.blocks {
block.predecessors.retain(|p| reachable.contains(p));
block.successors.retain(|s| reachable.contains(s));
}
}
fn merge_empty_blocks(&mut self, mf: &mut MachineFunction) {
let mut empty_blocks: Vec<(u32, Vec<u32>, u32)> = Vec::new();
for block in &mf.blocks {
let is_empty = block.instructions.is_empty()
|| (block.instructions.len() == 1
&& block.instructions[0].opcode == X86Opcode::JMP as u32);
if !is_empty || block.is_entry || block.is_exit {
continue;
}
if block.successors.len() != 1 {
continue;
}
let succ = block.successors[0];
if succ == block.id {
continue;
}
empty_blocks.push((block.id, block.predecessors.clone(), succ));
}
for (block_id, preds, succ) in &empty_blocks {
for pred in preds {
if let Some(pred_block) = mf.get_block_mut(*pred) {
if let Some(pos) = pred_block.successors.iter().position(|&s| s == *block_id) {
pred_block.successors[pos] = *succ;
}
}
}
if let Some(succ_block) = mf.get_block_mut(*succ) {
succ_block.predecessors.retain(|&p| p != *block_id);
for pred in preds {
if !succ_block.predecessors.contains(pred) {
succ_block.predecessors.push(*pred);
}
}
}
self.blocks_merged += 1;
}
let to_remove: Vec<u32> = empty_blocks.iter().map(|(id, _, _)| *id).collect();
mf.blocks.retain(|b| !to_remove.contains(&b.id));
self.empty_blocks_removed = to_remove.len();
}
fn remove_trivial_blocks(&mut self, mf: &mut MachineFunction) {
let mut to_merge: Vec<(u32, u32)> = Vec::new();
for block in &mf.blocks {
if block.is_entry || block.is_exit {
continue;
}
if block.predecessors.len() != 1 || block.successors.len() != 1 {
continue;
}
let has_side_effects = block
.instructions
.iter()
.any(|i| i.flags.has_side_effects || i.flags.is_call);
if !has_side_effects && !block.instructions.is_empty() {
to_merge.push((block.predecessors[0], block.id));
}
}
for (pred, block_id) in to_merge {
self.merge_single_pred_block(mf, pred, block_id);
self.blocks_merged += 1;
}
}
fn merge_single_pred_block(&self, mf: &mut MachineFunction, pred: u32, block_id: u32) {
let instructions: Vec<MachineInstr>;
let successors: Vec<u32>;
{
let block = match mf.block_by_id(block_id) {
Some(b) => b,
None => return,
};
instructions = block.instructions.clone();
successors = block.successors.clone();
}
let succs = successors.clone();
if let Some(pred_block) = mf.get_block_mut(pred) {
if let Some(last) = pred_block.instructions.last() {
if last.flags.is_terminator {
pred_block.instructions.pop();
}
}
for instr in instructions {
pred_block.instructions.push(instr);
}
pred_block.successors = successors;
}
for &succ in &succs {
if let Some(succ_block) = mf.get_block_mut(succ) {
if let Some(pos) = succ_block.predecessors.iter().position(|&p| p == block_id) {
succ_block.predecessors[pos] = pred;
}
}
}
mf.blocks.retain(|b| b.id != block_id);
mf.exit_blocks.retain(|&e| e != block_id);
}
}
impl Default for X86MachineCFGSimplifier {
fn default() -> Self {
Self::new()
}
}
impl MachineOperand {
fn reg_value(&self) -> Option<MCRegister> {
match self {
MachineOperand::Reg(r) => Some(*r),
_ => None,
}
}
}
fn make_mov_instr_imm(dst: u32, imm: i64) -> MachineInstr {
let mut instr = MachineInstr::new(X86Opcode::MOV as u32);
instr.flags.is_move_imm = true;
instr.operands.push(MachineOperand::Reg(MCRegister(dst)));
instr.operands.push(MachineOperand::Imm(imm));
instr
}
#[derive(Debug)]
pub struct X86ConditionalMoveOptimizer {
pub cmov_to_branch: usize,
pub branch_to_cmov: usize,
}
impl X86ConditionalMoveOptimizer {
pub fn new() -> Self {
Self {
cmov_to_branch: 0,
branch_to_cmov: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.optimize_block(mf, block_id);
}
}
fn optimize_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
for instr in &mut block.instructions {
let op = instr.opcode;
if (X86Opcode::CMOVO as u32..=X86Opcode::CMOVG as u32).contains(&op) {
if let (Some(MachineOperand::Reg(dst)), Some(MachineOperand::Reg(src))) =
(instr.operands.first(), instr.operands.get(1))
{
if dst == src {
continue;
}
}
}
}
}
}
impl Default for X86ConditionalMoveOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86LoadStoreOptimizer {
pub loads_folded: usize,
pub stores_merged: usize,
pub redundant_loads_removed: usize,
}
impl X86LoadStoreOptimizer {
pub fn new() -> Self {
Self {
loads_folded: 0,
stores_merged: 0,
redundant_loads_removed: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.optimize_block(mf, block_id);
}
}
fn optimize_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut i = 0;
while i + 1 < block.instructions.len() {
let first = &block.instructions[i];
let second = &block.instructions[i + 1];
if first.opcode == X86Opcode::MOV as u32
&& Self::is_alu_op(second.opcode)
&& first.operands.len() >= 2
{
if let (Some(MachineOperand::Reg(dst)), MachineOperand::Mem { .. }) =
(first.operands.first(), &first.operands[1])
{
let dst_reg = *dst;
if second.reads_register(dst_reg) && second.writes_register(dst_reg) {
let mem_op = first.operands[1].clone();
drop(first);
drop(second);
for op in block.instructions[i + 1].operands.iter_mut().skip(1) {
if let MachineOperand::Reg(r) = op {
if *r == dst_reg {
*op = mem_op;
break;
}
}
}
block.instructions.remove(i);
self.loads_folded += 1;
continue;
}
}
}
i += 1;
}
}
fn is_alu_op(opcode: u32) -> bool {
let o = opcode;
o == X86Opcode::ADD as u32
|| o == X86Opcode::SUB as u32
|| o == X86Opcode::AND as u32
|| o == X86Opcode::OR as u32
|| o == X86Opcode::XOR as u32
|| o == X86Opcode::CMP as u32
}
}
impl Default for X86LoadStoreOptimizer {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86MachineCopyPropagation {
pub copies_eliminated: usize,
}
impl X86MachineCopyPropagation {
pub fn new() -> Self {
Self {
copies_eliminated: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.propagate_in_block(mf, block_id);
}
}
fn propagate_in_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
let mut i = 0;
while i < block.instructions.len() {
let instr = &block.instructions[i];
if instr.opcode == X86Opcode::MOV as u32 && instr.operands.len() >= 2 {
if let (Some(MachineOperand::Reg(dst)), Some(MachineOperand::Reg(src))) =
(instr.operands.first(), instr.operands.get(1))
{
let dst_val = *dst;
let src_val = *src;
let mut replaced = false;
for j in i + 1..block.instructions.len() {
let next = &block.instructions[j];
if next.writes_register(dst_val) {
break;
}
if next.reads_register(dst_val) {
for op in &mut block.instructions[j].operands {
if let MachineOperand::Reg(r) = op {
if *r == dst_val {
*r = src_val;
replaced = true;
}
}
}
}
}
if replaced {
let all_replaced = (i + 1..block.instructions.len()).all(|j| {
!block.instructions[j].reads_register(dst_val)
|| block.instructions[j].writes_register(dst_val)
});
if all_replaced && !block.instructions[i].flags.has_side_effects {
block.instructions.remove(i);
self.copies_eliminated += 1;
continue;
}
}
}
}
i += 1;
}
}
}
impl Default for X86MachineCopyPropagation {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86StackSlotColoring {
pub slots_merged: usize,
pub bytes_saved: usize,
}
impl X86StackSlotColoring {
pub fn new() -> Self {
Self {
slots_merged: 0,
bytes_saved: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
let mut tracker = X86RegisterPressureTracker::new();
tracker.compute_liveness(mf);
let mut slot_ranges: HashMap<u32, (usize, usize)> = HashMap::new();
let mut instr_counter = 0usize;
for block in &mf.blocks {
for instr in &block.instructions {
for op in &instr.operands {
if let MachineOperand::Mem { offset, .. } = op {
if *offset < 0 {
let slot = (-offset) as u32;
let entry = slot_ranges
.entry(slot)
.or_insert((instr_counter, instr_counter));
entry.1 = instr_counter;
}
}
}
instr_counter += 1;
}
}
self.slots_merged = slot_ranges.len().saturating_sub(1);
if self.slots_merged > 0 {
self.bytes_saved = self.slots_merged * 8; }
}
}
impl Default for X86StackSlotColoring {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
pub struct X86TwoAddressInstructionPass {
pub commuted: usize,
pub coalesced: usize,
}
impl X86TwoAddressInstructionPass {
pub fn new() -> Self {
Self {
commuted: 0,
coalesced: 0,
}
}
pub fn run(&mut self, mf: &mut MachineFunction) {
for i in 0..mf.blocks.len() {
let block_id = mf.blocks[i].id;
self.process_block(mf, block_id);
}
}
fn process_block(&mut self, mf: &mut MachineFunction, block_id: u32) {
let block = match mf.get_block_mut(block_id) {
Some(b) => b,
None => return,
};
for instr in &mut block.instructions {
if Self::is_commutative_two_address(instr.opcode) && instr.operands.len() >= 2 {
if let (Some(MachineOperand::Reg(dst)), Some(MachineOperand::Reg(src))) =
(instr.operands.first(), instr.operands.get(1))
{
if dst.0 > src.0 {
instr.operands.swap(0, 1);
self.commuted += 1;
}
}
}
}
}
fn is_commutative_two_address(opcode: u32) -> bool {
let o = opcode;
o == X86Opcode::ADD as u32
|| o == X86Opcode::ADC as u32
|| o == X86Opcode::AND as u32
|| o == X86Opcode::OR as u32
|| o == X86Opcode::XOR as u32
|| o == X86Opcode::IMUL as u32
}
}
impl Default for X86TwoAddressInstructionPass {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn make_test_reg(id: u32) -> MCRegister {
MCRegister(id)
}
fn make_mov_instr(dst: u32, src: u32) -> MachineInstr {
let mut instr = MachineInstr::new(X86Opcode::MOV as u32);
instr.flags.is_move_reg = true;
instr.operands.push(MachineOperand::Reg(make_test_reg(dst)));
instr.operands.push(MachineOperand::Reg(make_test_reg(src)));
instr
}
fn make_add_instr(dst: u32, src: u32) -> MachineInstr {
let mut instr = MachineInstr::new(X86Opcode::ADD as u32);
instr.operands.push(MachineOperand::Reg(make_test_reg(dst)));
instr.operands.push(MachineOperand::Reg(make_test_reg(src)));
instr
}
fn make_cmp_instr(reg: u32, imm: i64) -> MachineInstr {
let mut instr = MachineInstr::new(X86Opcode::CMP as u32);
instr.flags.is_compare = true;
instr.operands.push(MachineOperand::Reg(make_test_reg(reg)));
instr.operands.push(MachineOperand::Imm(imm));
instr
}
fn make_jmp_instr(target: u32) -> MachineInstr {
let mut instr = MachineInstr::new(X86Opcode::JMP as u32);
instr.flags.is_terminator = true;
instr.flags.is_branch = true;
instr.operands.push(MachineOperand::Block(target));
instr
}
fn make_jcc_instr(opcode: u32, target: u32) -> MachineInstr {
let mut instr = MachineInstr::new(opcode);
instr.flags.is_terminator = true;
instr.flags.is_branch = true;
instr.operands.push(MachineOperand::Block(target));
instr
}
fn make_ret_instr() -> MachineInstr {
let mut ret = MachineInstr::new(X86Opcode::RET as u32);
ret.flags.is_terminator = true;
ret.flags.is_return = true;
ret
}
fn make_test_mf() -> MachineFunction {
let mut mf = MachineFunction::new("test_func");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_add_instr(0, 2));
b0.instructions.push(make_cmp_instr(0, 0));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 2));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "then");
b1.instructions.push(make_add_instr(0, 3));
b1.instructions.push(make_jmp_instr(3));
b1.predecessors = vec![0];
b1.successors = vec![3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "else");
b2.instructions.push(make_mov_instr(0, 4));
b2.instructions.push(make_jmp_instr(3));
b2.predecessors = vec![0];
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "merge");
b3.is_exit = true;
b3.instructions.push(make_mov_instr(1, 0));
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1, 2];
mf.add_block(b3);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
mf
}
fn make_loop_mf() -> MachineFunction {
let mut mf = MachineFunction::new("loop_func");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "loop_header");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 3));
b1.predecessors = vec![0, 2];
b1.successors = vec![2, 3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "loop_body");
b2.instructions.push(make_add_instr(0, 1));
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "exit");
b3.is_exit = true;
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
mf
}
#[test]
fn test_branch_probability_info_empty() {
let bpi = X86BranchProbabilityInfo::new();
assert_eq!(bpi.get_edge_probability(0, 1), 0.5);
assert_eq!(bpi.get_block_count(0), 0);
}
#[test]
fn test_branch_probability_info_compute() {
let mf = make_test_mf();
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
let p01 = bpi.get_edge_probability(0, 1);
assert!(p01 > 0.0 && p01 < 1.0);
let p02 = bpi.get_edge_probability(0, 2);
assert!(p02 > 0.0 && p02 < 1.0);
assert!((p01 + p02 - 1.0).abs() < 0.01);
}
#[test]
fn test_branch_probability_info_block_counts() {
let mf = make_test_mf();
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
assert!(bpi.get_block_count(0) > 0);
}
#[test]
fn test_block_placement_new() {
let placement = X86MachineBlockPlacement::new(true);
assert!(placement.prefer_fallthrough);
assert_eq!(placement.loop_header_alignment, LOOP_ALIGN_BOUNDARY);
assert_eq!(placement.fallthroughs_created, 0);
}
#[test]
fn test_block_placement_reorders() {
let mut mf = make_test_mf();
let mut placement = X86MachineBlockPlacement::new(true);
let order = placement.run(&mut mf);
assert_eq!(order.len(), mf.blocks.len());
assert_eq!(order[0], mf.entry_block);
}
#[test]
fn test_block_placement_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut placement = X86MachineBlockPlacement::default();
let order = placement.run(&mut mf);
assert!(order.is_empty());
}
#[test]
fn test_hot_cold_splitting() {
let mf = make_test_mf();
let mut placement = X86MachineBlockPlacement::new(true);
placement.branch_probs.compute(&mf);
let (hot, cold) = placement.split_hot_cold(&mut mf.clone());
assert!(!hot.is_empty());
assert_eq!(hot.len() + cold.len(), mf.blocks.len());
}
#[test]
fn test_cse_new() {
let cse = X86MachineCSE::new(false);
assert!(!cse.cross_block);
assert_eq!(cse.eliminated, 0);
}
#[test]
fn test_cse_eliminates_duplicate_adds() {
let mut mf = MachineFunction::new("cse_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_add_instr(0, 1)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
assert_eq!(cse.eliminated, 1);
}
#[test]
fn test_cse_eliminates_duplicate_movs() {
let mut mf = MachineFunction::new("cse_test2");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_mov_instr(0, 1)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
assert!(cse.eliminated >= 1);
}
#[test]
fn test_cse_commutative() {
let mut mf = MachineFunction::new("cse_comm");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut add1 = MachineInstr::new(X86Opcode::ADD as u32);
add1.operands.push(MachineOperand::Reg(make_test_reg(0)));
add1.operands.push(MachineOperand::Reg(make_test_reg(1)));
b0.instructions.push(add1);
let mut add2 = MachineInstr::new(X86Opcode::ADD as u32);
add2.operands.push(MachineOperand::Reg(make_test_reg(0)));
add2.operands.push(MachineOperand::Reg(make_test_reg(1)));
b0.instructions.push(add2);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
assert!(cse.eliminated >= 1);
}
#[test]
fn test_licm_new() {
let licm = X86MachineLICM::new();
assert_eq!(licm.hoisted, 0);
assert_eq!(licm.sunk, 0);
}
#[test]
fn test_licm_detects_loops() {
let mf = make_loop_mf();
let mut licm = X86MachineLICM::new();
licm.detect_loops(&mf);
assert!(!licm.loop_info.is_empty());
}
#[test]
fn test_licm_runs_on_function() {
let mut mf = make_loop_mf();
let mut licm = X86MachineLICM::new();
licm.run(&mut mf);
}
#[test]
fn test_licm_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut licm = X86MachineLICM::new();
licm.run(&mut mf);
assert_eq!(licm.hoisted, 0);
}
#[test]
fn test_sinking_new() {
let sinking = X86MachineSinking::new();
assert_eq!(sinking.sunk, 0);
assert!(sinking.split_critical_edges);
}
#[test]
fn test_sinking_runs_without_crashing() {
let mut mf = make_test_mf();
let mut sinking = X86MachineSinking::new();
sinking.run(&mut mf);
}
#[test]
fn test_combiner_new() {
let combiner = X86MachineCombiner::new();
assert_eq!(combiner.combined, 0);
assert!(combiner.enable_lea_formation);
}
#[test]
fn test_combiner_inc_to_add() {
let mut mf = MachineFunction::new("comb_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut inc_instr = MachineInstr::new(X86Opcode::INC as u32);
inc_instr
.operands
.push(MachineOperand::Reg(make_test_reg(0)));
b0.instructions.push(inc_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
let block = mf.block_by_id(0).unwrap();
let first = &block.instructions[0];
assert!(first.opcode == X86Opcode::ADD as u32 || first.opcode == X86Opcode::INC as u32);
}
#[test]
fn test_combiner_runs_on_function() {
let mut mf = make_test_mf();
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
}
#[test]
fn test_peephole_new() {
let peep = X86PeepholeOptimizer::new();
assert_eq!(peep.redundant_movs_eliminated, 0);
}
#[test]
fn test_peephole_eliminates_redundant_mov() {
let mut mf = MachineFunction::new("peep_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.redundant_movs_eliminated >= 1);
}
#[test]
fn test_peephole_cmp_zero_to_test() {
let mut mf = MachineFunction::new("peep_cmp");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 0));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.cmp_zero_to_test >= 1);
}
#[test]
fn test_peephole_cmp_nonzero_unchanged() {
let mut mf = MachineFunction::new("peep_cmp2");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
let block = mf.block_by_id(0).unwrap();
assert_eq!(block.instructions[0].opcode, X86Opcode::CMP as u32);
}
#[test]
fn test_peephole_double_negation() {
let mut mf = MachineFunction::new("peep_neg");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut neg1 = MachineInstr::new(X86Opcode::NEG as u32);
neg1.operands.push(MachineOperand::Reg(make_test_reg(0)));
b0.instructions.push(neg1);
let mut neg2 = MachineInstr::new(X86Opcode::NEG as u32);
neg2.operands.push(MachineOperand::Reg(make_test_reg(0)));
b0.instructions.push(neg2);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.double_neg_eliminated >= 1);
}
#[test]
fn test_peephole_identity_op() {
let mut mf = MachineFunction::new("peep_identity");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut or_instr = MachineInstr::new(X86Opcode::OR as u32);
or_instr
.operands
.push(MachineOperand::Reg(make_test_reg(0)));
or_instr.operands.push(MachineOperand::Imm(0));
b0.instructions.push(or_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.identity_ops_removed >= 1);
}
#[test]
fn test_peephole_runs_on_function() {
let mut mf = make_test_mf();
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
}
#[test]
fn test_branch_folding_new() {
let bf = X86BranchFolding::new();
assert_eq!(bf.branches_folded, 0);
}
#[test]
fn test_branch_folding_removes_fallthrough_branch() {
let mut mf = MachineFunction::new("bf_test");
let mut b0 = MachineBasicBlock::new(0, "b0");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.predecessors = vec![0];
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert!(bf.branches_folded >= 1);
}
#[test]
fn test_branch_folding_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert_eq!(bf.branches_folded, 0);
}
#[test]
fn test_verifier_new() {
let verifier = X86MachineVerifier::new();
assert!(verifier.errors.is_empty());
}
#[test]
fn test_verifier_passes_valid_function() {
let mf = make_test_mf();
let mut verifier = X86MachineVerifier::new();
let _result = verifier.verify(&mf);
}
#[test]
fn test_verifier_detects_missing_terminator() {
let mut mf = MachineFunction::new("bad_func");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
let _result = verifier.verify(&mf);
assert!(!verifier.errors.is_empty());
}
#[test]
fn test_verifier_detects_cfg_inconsistency() {
let mut mf = MachineFunction::new("bad_cfg");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.predecessors = vec![]; b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.errors.is_empty());
}
#[test]
fn test_verifier_ssa_property() {
let mut mf = MachineFunction::new("ssa_violation");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut mov1 = MachineInstr::new(X86Opcode::MOV as u32);
mov1.flags.is_move_reg = true;
mov1.operands.push(MachineOperand::Reg(make_test_reg(0)));
mov1.operands.push(MachineOperand::Imm(1));
b0.instructions.push(mov1);
let mut mov2 = MachineInstr::new(X86Opcode::MOV as u32);
mov2.flags.is_move_reg = true;
mov2.operands.push(MachineOperand::Reg(make_test_reg(0)));
mov2.operands.push(MachineOperand::Imm(2));
b0.instructions.push(mov2);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.errors.is_empty());
}
#[test]
fn test_trace_metrics_new() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.traces_analyzed, 0);
assert!(!tm.latencies.is_empty());
}
#[test]
fn test_trace_metrics_analyze_empty() {
let mut tm = X86MachineTraceMetrics::new();
let cycles = tm.analyze_trace(&[], &HashSet::new());
assert_eq!(cycles, 0);
}
#[test]
fn test_trace_metrics_analyze_single_mov() {
let mut tm = X86MachineTraceMetrics::new();
let instrs = vec![make_mov_instr(0, 1)];
let cycles = tm.analyze_trace(&instrs, &HashSet::new());
assert!(cycles > 0);
}
#[test]
fn test_trace_metrics_latency_table() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.latencies.get(&(X86Opcode::ADD as u32)), Some(&1));
assert_eq!(tm.latencies.get(&(X86Opcode::IMUL as u32)), Some(&3));
assert_eq!(tm.latencies.get(&(X86Opcode::MULPS as u32)), Some(&4));
}
#[test]
fn test_trace_metrics_resource_pressure() {
let instrs = vec![make_add_instr(0, 1), make_mov_instr(0, 2)];
let mut tm = X86MachineTraceMetrics::new();
let pressure = tm.estimate_resource_pressure(&instrs);
assert!(pressure > 0);
}
#[test]
fn test_outliner_new() {
let outliner = X86MachineOutliner::new();
assert_eq!(outliner.min_length, 3);
assert_eq!(outliner.min_occurrences, 2);
assert!(outliner.candidates.is_empty());
}
#[test]
fn test_outliner_scan_empty_function() {
let mf = MachineFunction::new("empty");
let mut outliner = X86MachineOutliner::new();
outliner.scan_function(&mf);
assert!(outliner.candidates.is_empty());
}
#[test]
fn test_outliner_scan_function() {
let mf = make_test_mf();
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.scan_function(&mf);
}
#[test]
fn test_outliner_estimate_savings() {
let outliner = X86MachineOutliner::new();
let savings = outliner.estimate_savings(5, 3);
assert_eq!(savings, 11);
}
#[test]
fn test_outliner_no_savings_for_short_sequences() {
let outliner = X86MachineOutliner::new();
let savings = outliner.estimate_savings(2, 2);
assert_eq!(savings, 0);
}
#[test]
fn test_outliner_total_savings() {
let mut outliner = X86MachineOutliner::new();
outliner.candidates.push(OutlineCandidateX86 {
hash: 1,
length: 5,
savings: 10,
instruction_patterns: Vec::new(),
occurrences: vec![(0, 0), (1, 0)],
});
outliner.candidates.push(OutlineCandidateX86 {
hash: 2,
length: 4,
savings: 8,
instruction_patterns: Vec::new(),
occurrences: vec![(2, 0), (3, 0)],
});
assert_eq!(outliner.total_savings(), 18);
}
#[test]
fn test_codegen_opt2_new() {
let opt2 = X86CodeGenOpt2::new();
assert_eq!(opt2.max_iterations, 3);
assert!(!opt2.verify_after_each_pass);
}
#[test]
fn test_codegen_opt2_runs_full_pipeline() {
let mut mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
opt2.verify_after_each_pass = true;
let stats = opt2.run(&mut mf);
assert!(stats.iterations > 0);
}
#[test]
fn test_codegen_opt2_runs_on_loop() {
let mut mf = make_loop_mf();
let mut opt2 = X86CodeGenOpt2::new();
let _stats = opt2.run(&mut mf);
}
#[test]
fn test_codegen_opt2_post_ra() {
let mut mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
let _stats = opt2.run_post_ra(&mut mf);
}
#[test]
fn test_codegen_opt2_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut opt2 = X86CodeGenOpt2::new();
let stats = opt2.run(&mut mf);
assert_eq!(stats.cse_eliminated, 0);
}
#[test]
fn test_opt2_stats_new() {
let stats = X86Opt2Stats::new();
assert_eq!(stats.branches_folded, 0);
assert_eq!(stats.critical_path_cycles, 0);
}
#[test]
fn test_opt2_print_stats() {
let stats = X86Opt2Stats::new();
let opt2 = X86CodeGenOpt2::new();
opt2.print_stats(&stats);
}
#[test]
fn test_full_pipeline_reduces_branches() {
let mut mf = MachineFunction::new("branch_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "next");
b1.predecessors = vec![0];
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
let stats = opt2.run(&mut mf);
assert!(stats.branches_folded > 0);
}
#[test]
fn test_full_pipeline_preserves_semantics() {
let mut mf = make_test_mf();
let block_count_before = mf.blocks.len();
let instr_count_before: usize = mf.blocks.iter().map(|b| b.instructions.len()).sum();
let mut opt2 = X86CodeGenOpt2::new();
opt2.run(&mut mf);
let block_count_after = mf.blocks.len();
let instr_count_after: usize = mf.blocks.iter().map(|b| b.instructions.len()).sum();
assert!(block_count_after >= block_count_before);
assert!(instr_count_after <= instr_count_before + 5);
}
#[test]
fn test_convergence() {
let mut mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 10;
let stats = opt2.run(&mut mf);
assert!(stats.iterations <= 10);
}
#[test]
fn test_all_passes_idempotent() {
let mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 2;
let mut mf1 = mf.clone();
let mut mf2 = mf.clone();
let _stats1 = opt2.run(&mut mf1);
let _stats2 = opt2.run(&mut mf2);
}
#[test]
fn test_peephole_cmov_same_src_dest() {
let mut mf = MachineFunction::new("cmov_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut cmov = MachineInstr::new(X86Opcode::CMOVE as u32);
cmov.operands.push(MachineOperand::Reg(make_test_reg(0)));
cmov.operands.push(MachineOperand::Reg(make_test_reg(0)));
b0.instructions.push(cmov);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.cmov_same_to_mov >= 1);
}
#[test]
fn test_pressure_tracker_new() {
let tracker = X86RegisterPressureTracker::new();
assert_eq!(tracker.gpr_pressure, 0);
assert_eq!(tracker.xmm_pressure, 0);
assert_eq!(tracker.max_gpr_pressure, 0);
assert_eq!(tracker.max_xmm_pressure, 0);
}
#[test]
fn test_pressure_tracker_liveness() {
let mut mf = make_test_mf();
let mut tracker = X86RegisterPressureTracker::new();
tracker.compute_liveness(&mf);
assert!(tracker.max_gpr_pressure > 0 || tracker.max_gpr_pressure == 0);
}
#[test]
fn test_pressure_tracker_classify_reg() {
let tracker = X86RegisterPressureTracker::new();
assert_eq!(tracker.classify_reg(MCRegister(0)), RegClassType::GPR);
assert_eq!(tracker.classify_reg(MCRegister(15)), RegClassType::GPR);
assert_eq!(tracker.classify_reg(MCRegister(16)), RegClassType::XMM);
assert_eq!(tracker.classify_reg(MCRegister(47)), RegClassType::XMM);
assert_eq!(tracker.classify_reg(MCRegister(100)), RegClassType::Other);
}
#[test]
fn test_pressure_tracker_can_hoist() {
let tracker = X86RegisterPressureTracker::new();
assert!(tracker.can_hoist_gpr(10));
assert!(tracker.can_hoist_xmm(10));
}
#[test]
fn test_pressure_tracker_block_exit() {
let mf = make_test_mf();
let mut tracker = X86RegisterPressureTracker::new();
tracker.compute_liveness(&mf);
let (gpr, xmm) = tracker.pressure_at_block_exit(0);
assert!(gpr <= 16);
assert!(xmm <= 32);
}
#[test]
fn test_pressure_tracker_empty_function() {
let mf = MachineFunction::new("empty");
let mut tracker = X86RegisterPressureTracker::new();
tracker.compute_liveness(&mf);
assert_eq!(tracker.max_gpr_pressure, 0);
}
#[test]
fn test_macro_fusion_new() {
let fusion = X86MacroFusionPrep::new();
assert_eq!(fusion.fusible_pairs, 0);
assert_eq!(fusion.reordered_for_fusion, 0);
}
#[test]
fn test_macro_fusion_detects_cmp_jcc() {
let mut mf = MachineFunction::new("fusion_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "target");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "fallthrough");
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut fusion = X86MacroFusionPrep::new();
fusion.run(&mut mf);
assert_eq!(fusion.fusible_pairs, 1);
}
#[test]
fn test_macro_fusion_detects_test_jcc() {
let mut mf = MachineFunction::new("fusion_test2");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut test_instr = MachineInstr::new(X86Opcode::TEST as u32);
test_instr
.operands
.push(MachineOperand::Reg(make_test_reg(0)));
test_instr
.operands
.push(MachineOperand::Reg(make_test_reg(0)));
b0.instructions.push(test_instr);
b0.instructions
.push(make_jcc_instr(X86Opcode::JNE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut fusion = X86MacroFusionPrep::new();
fusion.run(&mut mf);
assert_eq!(fusion.fusible_pairs, 1);
}
#[test]
fn test_macro_fusion_no_fusion_without_jcc() {
let mut mf = MachineFunction::new("fusion_test3");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
b0.instructions.push(make_mov_instr(1, 2)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut fusion = X86MacroFusionPrep::new();
fusion.run(&mut mf);
assert_eq!(fusion.fusible_pairs, 0);
}
#[test]
fn test_macro_fusion_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut fusion = X86MacroFusionPrep::new();
fusion.run(&mut mf);
assert_eq!(fusion.fusible_pairs, 0);
}
#[test]
fn test_macro_fusion_is_jcc_opcode() {
assert!(X86MacroFusionPrep::is_jcc_opcode(X86Opcode::JE as u32));
assert!(X86MacroFusionPrep::is_jcc_opcode(X86Opcode::JNE as u32));
assert!(X86MacroFusionPrep::is_jcc_opcode(X86Opcode::JG as u32));
assert!(!X86MacroFusionPrep::is_jcc_opcode(X86Opcode::JMP as u32));
assert!(!X86MacroFusionPrep::is_jcc_opcode(X86Opcode::CALL as u32));
}
#[test]
fn test_macro_fusion_sets_flags() {
assert!(X86MacroFusionPrep::sets_flags_full(X86Opcode::ADD as u32));
assert!(X86MacroFusionPrep::sets_flags_full(X86Opcode::SUB as u32));
assert!(X86MacroFusionPrep::sets_flags_full(X86Opcode::CMP as u32));
assert!(X86MacroFusionPrep::sets_flags_full(X86Opcode::INC as u32));
assert!(!X86MacroFusionPrep::sets_flags_full(X86Opcode::MOV as u32));
assert!(!X86MacroFusionPrep::sets_flags_full(X86Opcode::LEA as u32));
}
#[test]
fn test_flags_optimizer_new() {
let opt = X86FlagsOptimizer::new();
assert_eq!(opt.flags_removed, 0);
assert_eq!(opt.test_to_cmp, 0);
assert_eq!(opt.setcc_optimized, 0);
}
#[test]
fn test_flags_optimizer_redundant_add() {
let mut mf = MachineFunction::new("flags_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_add_instr(2, 3));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt = X86FlagsOptimizer::new();
opt.run(&mut mf);
assert!(opt.flags_removed >= 1);
}
#[test]
fn test_flags_optimizer_setcc_movzx() {
let mut mf = MachineFunction::new("flags_setcc");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut setcc = MachineInstr::new(X86Opcode::SETE as u32);
setcc.operands.push(MachineOperand::Reg(MCRegister(10)));
b0.instructions.push(setcc);
let mut movzx = MachineInstr::new(X86Opcode::MOVZX as u32);
movzx.operands.push(MachineOperand::Reg(MCRegister(0)));
movzx.operands.push(MachineOperand::Reg(MCRegister(10)));
b0.instructions.push(movzx);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt = X86FlagsOptimizer::new();
opt.run(&mut mf);
assert!(opt.setcc_optimized >= 1);
}
#[test]
fn test_flags_optimizer_runs_on_function() {
let mut mf = make_test_mf();
let mut opt = X86FlagsOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_flags_optimizer_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut opt = X86FlagsOptimizer::new();
opt.run(&mut mf);
assert_eq!(opt.flags_removed, 0);
}
#[test]
fn test_constant_hoisting_new() {
let hoist = X86ConstantHoisting::new();
assert_eq!(hoist.constants_hoisted, 0);
assert_eq!(hoist.bytes_saved, 0);
}
#[test]
fn test_constant_hoisting_runs_on_loop() {
let mut mf = make_loop_mf();
let mut hoist = X86ConstantHoisting::new();
hoist.run(&mut mf);
}
#[test]
fn test_constant_hoisting_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut hoist = X86ConstantHoisting::new();
hoist.run(&mut mf);
assert_eq!(hoist.constants_hoisted, 0);
}
#[test]
fn test_is_expensive_constant_load() {
let mov_large = make_mov_instr_imm(0, 0x1_0000_0000);
assert!(X86ConstantHoisting::is_expensive_constant_load(&mov_large));
let mov_small = make_mov_instr_imm(0, 42);
assert!(!X86ConstantHoisting::is_expensive_constant_load(&mov_small));
let add = make_add_instr(0, 1);
assert!(!X86ConstantHoisting::is_expensive_constant_load(&add));
}
#[test]
fn test_get_constant() {
let instr = make_mov_instr_imm(0, 12345);
assert_eq!(X86ConstantHoisting::get_constant(&instr), Some(12345));
let add = make_add_instr(0, 1);
assert_eq!(X86ConstantHoisting::get_constant(&add), None);
}
#[test]
fn test_address_mode_new() {
let opt = X86AddressModeOptimizer::new();
assert_eq!(opt.modes_simplified, 0);
assert!(opt.enable_rip_relative);
}
#[test]
fn test_address_mode_runs() {
let mut mf = make_test_mf();
let mut opt = X86AddressModeOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_address_mode_can_merge() {
let a = MachineOperand::Mem {
base: MCRegister(1),
offset: 0,
size: 4,
};
let b = MachineOperand::Mem {
base: MCRegister(1),
offset: 0,
size: 4,
};
assert!(X86AddressModeOptimizer::can_merge_modes(&a, &b));
let c = MachineOperand::Mem {
base: MCRegister(2),
offset: 0,
size: 4,
};
assert!(!X86AddressModeOptimizer::can_merge_modes(&a, &c));
}
#[test]
fn test_cfg_simplifier_new() {
let simplifier = X86MachineCFGSimplifier::new();
assert_eq!(simplifier.blocks_merged, 0);
assert_eq!(simplifier.empty_blocks_removed, 0);
assert_eq!(simplifier.unreachable_blocks_removed, 0);
}
#[test]
fn test_cfg_simplifier_removes_unreachable() {
let mut mf = MachineFunction::new("cfg_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "unreachable");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
assert!(simplifier.unreachable_blocks_removed >= 1);
assert_eq!(mf.blocks.len(), 1);
}
#[test]
fn test_cfg_simplifier_removes_empty_blocks() {
let mut mf = MachineFunction::new("cfg_test2");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "empty");
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "target");
b2.predecessors = vec![1];
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
assert!(simplifier.blocks_merged >= 1);
}
#[test]
fn test_cfg_simplifier_runs_on_function() {
let mut mf = make_test_mf();
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
}
#[test]
fn test_cfg_simplifier_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
assert_eq!(simplifier.blocks_merged, 0);
}
#[test]
fn test_loop_unroller_new() {
let unroller = X86MachineLoopUnroller::new();
assert_eq!(unroller.max_unroll, 4);
assert_eq!(unroller.max_instructions, 16);
assert_eq!(unroller.loops_unrolled, 0);
}
#[test]
fn test_loop_unroller_runs_on_loop() {
let mut mf = make_loop_mf();
let mut unroller = X86MachineLoopUnroller::new();
unroller.run(&mut mf);
}
#[test]
fn test_loop_unroller_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut unroller = X86MachineLoopUnroller::new();
unroller.run(&mut mf);
assert_eq!(unroller.loops_unrolled, 0);
}
#[test]
fn test_operand_reg_value() {
let op = MachineOperand::Reg(MCRegister(42));
assert_eq!(op.reg_value(), Some(MCRegister(42)));
let op_imm = MachineOperand::Imm(100);
assert_eq!(op_imm.reg_value(), None);
}
#[test]
fn test_deep_pipeline_stress() {
let mut mf = MachineFunction::new("stress_test");
let mut blocks: Vec<MachineBasicBlock> = Vec::new();
for i in 0..20u32 {
let mut b = MachineBasicBlock::new(i, format!("block_{}", i));
b.instructions.push(make_mov_instr(i % 16, (i + 1) % 16));
if i % 3 == 0 {
b.instructions.push(make_add_instr(i % 16, (i + 2) % 16));
}
if i % 5 == 0 {
b.instructions.push(make_cmp_instr(i % 16, 0));
}
if i < 19 {
b.instructions.push(make_jmp_instr(i + 1));
b.successors = vec![i + 1];
} else {
b.instructions.push(make_ret_instr());
}
if i > 0 {
b.predecessors = vec![i - 1];
}
if i == 0 {
b.is_entry = true;
}
if i == 19 {
b.is_exit = true;
}
blocks.push(b);
}
for b in blocks {
mf.add_block(b);
}
mf.entry_block = 0;
mf.exit_blocks = vec![19];
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 1;
let stats = opt2.run(&mut mf);
assert!(stats.iterations == 1);
}
#[test]
fn test_many_instructions_per_block() {
let mut mf = MachineFunction::new("many_instrs");
let mut b0 = MachineBasicBlock::new(0, "big_block");
b0.is_entry = true;
for i in 0..100u32 {
match i % 4 {
0 => b0.instructions.push(make_mov_instr(i % 16, (i + 1) % 16)),
1 => b0.instructions.push(make_add_instr(i % 16, (i + 2) % 16)),
2 => b0.instructions.push(make_cmp_instr(i % 16, 0)),
_ => {
let mut xor = MachineInstr::new(X86Opcode::XOR as u32);
xor.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
xor.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
b0.instructions.push(xor);
}
}
}
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 1;
let stats = opt2.run(&mut mf);
}
#[test]
fn test_diamond_pattern_repeated() {
let mut mf = MachineFunction::new("diamonds");
let mut block_counter = 0u32;
let mut entry = MachineBasicBlock::new(block_counter, "entry");
entry.is_entry = true;
entry.instructions.push(make_mov_instr(0, 1));
entry.successors = vec![block_counter + 1];
mf.add_block(entry);
let prev_id = block_counter;
block_counter += 1;
for _ in 0..10 {
let cond_id = block_counter;
block_counter += 1;
let then_id = block_counter;
block_counter += 1;
let else_id = block_counter;
block_counter += 1;
let merge_id = block_counter;
block_counter += 1;
let mut cond = MachineBasicBlock::new(cond_id, format!("cond_{}", cond_id));
cond.instructions.push(make_cmp_instr(0, 1));
cond.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, then_id));
cond.predecessors = vec![prev_id];
cond.successors = vec![then_id, else_id];
mf.add_block(cond);
let mut then_block = MachineBasicBlock::new(then_id, format!("then_{}", then_id));
then_block.instructions.push(make_add_instr(0, 1));
then_block.instructions.push(make_jmp_instr(merge_id));
then_block.predecessors = vec![cond_id];
then_block.successors = vec![merge_id];
mf.add_block(then_block);
let mut else_block = MachineBasicBlock::new(else_id, format!("else_{}", else_id));
else_block.instructions.push(make_mov_instr(0, 2));
else_block.instructions.push(make_jmp_instr(merge_id));
else_block.predecessors = vec![cond_id];
else_block.successors = vec![merge_id];
mf.add_block(else_block);
let mut merge = MachineBasicBlock::new(merge_id, format!("merge_{}", merge_id));
merge.instructions.push(make_mov_instr(1, 0));
merge.predecessors = vec![then_id, else_id];
mf.add_block(merge);
}
let last_id = block_counter - 1;
if let Some(last) = mf.get_block_mut(last_id) {
last.instructions.push(make_ret_instr());
last.is_exit = true;
}
mf.entry_block = 0;
mf.exit_blocks = vec![last_id];
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 1;
let stats = opt2.run(&mut mf);
}
#[test]
fn test_nested_loops() {
let mut mf = MachineFunction::new("nested_loops");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "outer_header");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 5));
b1.predecessors = vec![0, 4];
b1.successors = vec![2, 5];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "inner_header");
b2.instructions.push(make_cmp_instr(1, 5));
b2.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 4));
b2.predecessors = vec![1, 3];
b2.successors = vec![3, 4];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "inner_body");
b3.instructions.push(make_add_instr(1, 1));
b3.instructions.push(make_jmp_instr(2));
b3.predecessors = vec![2];
b3.successors = vec![2];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "outer_latch");
b4.instructions.push(make_add_instr(0, 1));
b4.instructions.push(make_jmp_instr(1));
b4.predecessors = vec![2, 3];
b4.successors = vec![1];
mf.add_block(b4);
let mut b5 = MachineBasicBlock::new(5, "exit");
b5.is_exit = true;
b5.instructions.push(make_ret_instr());
b5.predecessors = vec![1];
mf.add_block(b5);
mf.entry_block = 0;
mf.exit_blocks = vec![5];
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 2;
let stats = opt2.run(&mut mf);
}
#[test]
fn test_switch_like_cfg() {
let mut mf = MachineFunction::new("switch_cfg");
let mut b0 = MachineBasicBlock::new(0, "dispatch");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 0));
b0.successors = vec![1, 2, 3, 4, 5]; mf.add_block(b0);
for i in 1..=5u32 {
let mut b = MachineBasicBlock::new(i, format!("case_{}", i));
b.instructions.push(make_mov_instr(i % 16, i));
b.instructions.push(make_jmp_instr(6));
b.predecessors = vec![0];
b.successors = vec![6];
mf.add_block(b);
}
let mut b6 = MachineBasicBlock::new(6, "merge");
b6.is_exit = true;
b6.instructions.push(make_ret_instr());
b6.predecessors = vec![1, 2, 3, 4, 5];
mf.add_block(b6);
mf.entry_block = 0;
mf.exit_blocks = vec![6];
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
}
#[test]
fn test_critical_edge_splitting() {
let mut mf = MachineFunction::new("crit_edge");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 0));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "target1");
b1.instructions.push(make_mov_instr(1, 0));
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0, 3];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "merge");
b2.instructions.push(make_ret_instr());
b2.predecessors = vec![0, 1]; mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "target2");
b3.instructions.push(make_add_instr(0, 1));
b3.instructions.push(make_jmp_instr(1));
b3.predecessors = vec![0];
b3.successors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
let mut sinking = X86MachineSinking::new();
sinking.run(&mut mf);
}
#[test]
fn test_verifier_detects_back_edge_as_loop() {
let mut mf = MachineFunction::new("back_edge");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "header");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JL as u32, 2));
b1.predecessors = vec![0, 2];
b1.successors = vec![2, 3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "body");
b2.instructions.push(make_add_instr(0, 1));
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "exit");
b3.is_exit = true;
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
let mut licm = X86MachineLICM::new();
licm.detect_loops(&mf);
assert!(licm.loop_info.contains_key(&1));
}
#[test]
fn test_combiner_shl_add_to_lea() {
let mut mf = MachineFunction::new("shl_add");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut shl = MachineInstr::new(X86Opcode::SHL as u32);
shl.operands.push(MachineOperand::Reg(MCRegister(1)));
shl.operands.push(MachineOperand::Imm(2));
b0.instructions.push(shl);
let mut add = MachineInstr::new(X86Opcode::ADD as u32);
add.operands.push(MachineOperand::Reg(MCRegister(0)));
add.operands.push(MachineOperand::Reg(MCRegister(1)));
b0.instructions.push(add);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert!(combiner.combined >= 1);
}
#[test]
fn test_combiner_mul_add_to_lea() {
let mut mf = MachineFunction::new("mul_add");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut imul = MachineInstr::new(X86Opcode::IMUL as u32);
imul.operands.push(MachineOperand::Reg(MCRegister(1)));
imul.operands.push(MachineOperand::Reg(MCRegister(2)));
imul.operands.push(MachineOperand::Imm(8));
b0.instructions.push(imul);
let mut add = MachineInstr::new(X86Opcode::ADD as u32);
add.operands.push(MachineOperand::Reg(MCRegister(0)));
add.operands.push(MachineOperand::Reg(MCRegister(1)));
b0.instructions.push(add);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert!(combiner.combined >= 1);
}
#[test]
fn test_peephole_lea_to_nop() {
let mut mf = MachineFunction::new("lea_nop");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut lea = MachineInstr::new(X86Opcode::LEA as u32);
lea.flags.is_move_reg = true;
lea.operands.push(MachineOperand::Reg(MCRegister(0)));
lea.operands.push(MachineOperand::Mem {
base: MCRegister(0),
offset: 0,
size: 0,
});
b0.instructions.push(lea);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.lea_to_nop >= 1);
}
#[test]
fn test_peephole_shift_combine() {
let mut mf = MachineFunction::new("shift_combine");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut shl = MachineInstr::new(X86Opcode::SHL as u32);
shl.operands.push(MachineOperand::Reg(MCRegister(0)));
shl.operands.push(MachineOperand::Imm(3));
b0.instructions.push(shl);
let mut shr = MachineInstr::new(X86Opcode::SHR as u32);
shr.operands.push(MachineOperand::Reg(MCRegister(0)));
shr.operands.push(MachineOperand::Imm(3));
b0.instructions.push(shr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.shift_combined >= 1);
}
#[test]
fn test_trace_metrics_critical_path_add_chain() {
let mut tm = X86MachineTraceMetrics::new();
let mut instrs = Vec::new();
for i in 0..10u32 {
instrs.push(make_add_instr(i % 16, (i + 1) % 16));
}
let cycles = tm.analyze_trace(&instrs, &HashSet::new());
assert!(cycles >= 10);
}
#[test]
fn test_trace_metrics_parallel_adds() {
let mut tm = X86MachineTraceMetrics::new();
let mut instrs = Vec::new();
for i in 0..10u32 {
instrs.push(make_add_instr(i, i + 16));
}
let cycles = tm.analyze_trace(&instrs, &HashSet::new());
assert_eq!(cycles, 1);
}
#[test]
fn test_outliner_hash_different_sequences() {
let a = vec![make_add_instr(0, 1), make_mov_instr(0, 2)];
let b = vec![make_add_instr(0, 1), make_add_instr(0, 3)];
let ha = X86MachineOutliner::hash_sequence(&a);
let hb = X86MachineOutliner::hash_sequence(&b);
assert_ne!(ha, hb);
}
#[test]
fn test_outliner_hash_same_sequence() {
let a = vec![make_add_instr(0, 1), make_mov_instr(0, 2)];
let b = vec![make_add_instr(0, 1), make_mov_instr(0, 2)];
let ha = X86MachineOutliner::hash_sequence(&a);
let hb = X86MachineOutliner::hash_sequence(&b);
assert_eq!(ha, hb);
}
#[test]
fn test_block_placement_edge_count_layout() {
let mut mf = make_test_mf();
let mut placement = X86MachineBlockPlacement::new(true);
placement.branch_probs.compute(&mf);
placement.layout_by_edge_counts(&mut mf);
assert_eq!(placement.reordered_blocks.len(), mf.blocks.len());
}
#[test]
fn test_peephole_xor_reg_reg() {
let mut mf = MachineFunction::new("xor_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut xor_instr = MachineInstr::new(X86Opcode::XOR as u32);
xor_instr.operands.push(MachineOperand::Reg(MCRegister(0)));
xor_instr.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(xor_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.xor_to_xor32 >= 1);
}
#[test]
fn test_verifier_warns_use_before_def() {
let mut mf = MachineFunction::new("use_before_def");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.warnings.is_empty());
}
#[test]
fn test_macro_fusion_depends_on_flags() {
let cmov = MachineInstr::new(X86Opcode::CMOVE as u32);
assert!(X86MacroFusionPrep::depends_on_flags(&cmov));
let setcc = MachineInstr::new(X86Opcode::SETE as u32);
assert!(X86MacroFusionPrep::depends_on_flags(&setcc));
let add = MachineInstr::new(X86Opcode::ADD as u32);
assert!(!X86MacroFusionPrep::depends_on_flags(&add));
}
#[test]
fn test_flags_optimizer_sets_flags() {
assert!(X86FlagsOptimizer::sets_flags(X86Opcode::ADD as u32));
assert!(X86FlagsOptimizer::sets_flags(X86Opcode::SHL as u32));
assert!(!X86FlagsOptimizer::sets_flags(X86Opcode::MOV as u32));
assert!(!X86FlagsOptimizer::sets_flags(X86Opcode::LEA as u32));
}
#[test]
fn test_flags_optimizer_is_setcc() {
assert!(X86FlagsOptimizer::is_setcc(X86Opcode::SETE as u32));
assert!(X86FlagsOptimizer::is_setcc(X86Opcode::SETNE as u32));
assert!(!X86FlagsOptimizer::is_setcc(X86Opcode::MOV as u32));
}
#[test]
fn test_reg_class_type_eq() {
assert_eq!(RegClassType::GPR, RegClassType::GPR);
assert_ne!(RegClassType::GPR, RegClassType::XMM);
assert_ne!(RegClassType::XMM, RegClassType::Other);
}
#[test]
fn test_make_x86_mem_op() {
let op = make_x86_mem_op(1, 2, 4, 16);
assert!(matches!(op, MachineOperand::Mem { .. }));
}
#[test]
fn test_get_def_reg_returns_none_on_imm() {
let mut instr = MachineInstr::new(X86Opcode::ADD as u32);
instr.operands.push(MachineOperand::Imm(0));
assert_eq!(get_def_reg(&instr), None);
}
#[test]
fn test_get_def_reg_returns_some_on_reg() {
let mut instr = MachineInstr::new(X86Opcode::ADD as u32);
instr.operands.push(MachineOperand::Reg(MCRegister(5)));
assert_eq!(get_def_reg(&instr), Some(MCRegister(5)));
}
#[test]
fn test_outliner_scan_cross_function() {
let mf1 = make_test_mf();
let mf2 = make_loop_mf();
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.scan_functions(&[&mf1, &mf2]);
}
#[test]
fn test_cse_cross_block_enabled() {
let mut mf = make_test_mf();
let mut cse = X86MachineCSE::new(true);
cse.run(&mut mf);
}
#[test]
fn test_opt2_stats_clone() {
let stats = X86Opt2Stats::new();
let cloned = stats.clone();
assert_eq!(stats, cloned);
}
#[test]
fn test_block_placement_layout_by_edge_counts_empty() {
let mut mf = MachineFunction::new("empty");
let mut placement = X86MachineBlockPlacement::new(true);
placement.layout_by_edge_counts(&mut mf);
assert!(placement.reordered_blocks.is_empty());
}
#[test]
fn test_sinking_performs_sink_to_valid_succ() {
let mut mf = MachineFunction::new("sink_valid");
let mut b0 = MachineBasicBlock::new(0, "src");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "dest");
b1.predecessors = vec![0];
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "other");
b2.predecessors = vec![0];
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut sinking = X86MachineSinking::new();
sinking.run(&mut mf);
}
#[test]
fn test_all_passes_default_creation() {
let _bpi = X86BranchProbabilityInfo::default();
let _bp = X86MachineBlockPlacement::default();
let _cse = X86MachineCSE::default();
let _licm = X86MachineLICM::default();
let _sink = X86MachineSinking::default();
let _comb = X86MachineCombiner::default();
let _peep = X86PeepholeOptimizer::default();
let _bf = X86BranchFolding::default();
let _ver = X86MachineVerifier::default();
let _tm = X86MachineTraceMetrics::default();
let _out = X86MachineOutliner::default();
let _opt2 = X86CodeGenOpt2::default();
let _stats = X86Opt2Stats::default();
let _press = X86RegisterPressureTracker::default();
let _fusion = X86MacroFusionPrep::default();
let _flags = X86FlagsOptimizer::default();
let _hoist = X86ConstantHoisting::default();
let _amode = X86AddressModeOptimizer::default();
let _cfgs = X86MachineCFGSimplifier::default();
let _unroll = X86MachineLoopUnroller::default();
}
#[test]
fn test_print_diagnostics_empty() {
let verifier = X86MachineVerifier::new();
verifier.print_diagnostics(); }
#[test]
fn test_print_stats_empty() {
let stats = X86Opt2Stats::new();
let opt2 = X86CodeGenOpt2::new();
opt2.print_stats(&stats);
}
#[test]
fn test_conditional_move_optimizer_new() {
let opt = X86ConditionalMoveOptimizer::new();
assert_eq!(opt.cmov_to_branch, 0);
assert_eq!(opt.branch_to_cmov, 0);
}
#[test]
fn test_conditional_move_optimizer_runs() {
let mut mf = make_test_mf();
let mut opt = X86ConditionalMoveOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_cmov_to_branch_heuristic() {
let mut mf = MachineFunction::new("cmov_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
let mut cmov = MachineInstr::new(X86Opcode::CMOVG as u32);
cmov.operands.push(MachineOperand::Reg(MCRegister(0)));
cmov.operands.push(MachineOperand::Reg(MCRegister(1)));
b0.instructions.push(cmov);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt = X86ConditionalMoveOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_load_store_optimizer_new() {
let opt = X86LoadStoreOptimizer::new();
assert_eq!(opt.loads_folded, 0);
assert_eq!(opt.stores_merged, 0);
}
#[test]
fn test_load_store_optimizer_runs() {
let mut mf = make_test_mf();
let mut opt = X86LoadStoreOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_load_folding_move_followed_by_add() {
let mut mf = MachineFunction::new("load_fold");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut mov = MachineInstr::new(X86Opcode::MOV as u32);
mov.operands.push(MachineOperand::Reg(MCRegister(0)));
mov.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
b0.instructions.push(mov);
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt = X86LoadStoreOptimizer::new();
opt.run(&mut mf);
}
#[test]
fn test_copy_propagation_new() {
let cp = X86MachineCopyPropagation::new();
assert_eq!(cp.copies_eliminated, 0);
}
#[test]
fn test_copy_propagation_forward() {
let mut mf = MachineFunction::new("copy_prop");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_add_instr(0, 2));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cp = X86MachineCopyPropagation::new();
cp.run(&mut mf);
}
#[test]
fn test_copy_propagation_eliminates_dead_copy() {
let mut mf = MachineFunction::new("dead_copy");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_mov_instr(0, 2));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cp = X86MachineCopyPropagation::new();
cp.run(&mut mf);
}
#[test]
fn test_stack_slot_coloring_new() {
let ssc = X86StackSlotColoring::new();
assert_eq!(ssc.slots_merged, 0);
assert_eq!(ssc.bytes_saved, 0);
}
#[test]
fn test_stack_slot_coloring_no_overlap() {
let mut mf = MachineFunction::new("stack_slots");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut ssc = X86StackSlotColoring::new();
ssc.run(&mut mf);
}
#[test]
fn test_two_address_pass_new() {
let pass = X86TwoAddressInstructionPass::new();
assert_eq!(pass.commuted, 0);
assert_eq!(pass.coalesced, 0);
}
#[test]
fn test_two_address_pass_runs() {
let mut mf = make_test_mf();
let mut pass = X86TwoAddressInstructionPass::new();
pass.run(&mut mf);
}
#[test]
fn test_two_address_commute_add() {
let mut mf = MachineFunction::new("twoaddr");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut pass = X86TwoAddressInstructionPass::new();
pass.run(&mut mf);
}
#[test]
fn test_empty_block_handling() {
let mut mf = MachineFunction::new("empty_blocks");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "empty");
mf.add_block(b1);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
opt2.run(&mut mf);
}
#[test]
fn test_single_instruction_block() {
let mut mf = MachineFunction::new("single_instr");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
opt2.run(&mut mf);
}
#[test]
fn test_branch_to_self() {
let mut mf = MachineFunction::new("self_branch");
let mut b0 = MachineBasicBlock::new(0, "loop");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(0));
b0.successors = vec![0];
b0.predecessors = vec![0];
mf.add_block(b0);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
}
#[test]
fn test_irreducible_cfg() {
let mut mf = MachineFunction::new("irreducible");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "header");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JL as u32, 2));
b1.predecessors = vec![0, 2, 3];
b1.successors = vec![2, 4];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "loop_a");
b2.instructions.push(make_add_instr(0, 1));
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "loop_b");
b3.instructions.push(make_add_instr(1, 1));
b3.instructions.push(make_jmp_instr(1));
b3.successors = vec![1];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "exit");
b4.is_exit = true;
b4.instructions.push(make_ret_instr());
b4.predecessors = vec![1];
mf.add_block(b4);
mf.entry_block = 0;
mf.exit_blocks = vec![4];
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 1;
opt2.run(&mut mf);
}
#[test]
fn test_max_registers_used() {
let mut mf = MachineFunction::new("max_regs");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
for i in 0..50u32 {
b0.instructions.push(make_mov_instr(i, i + 1));
}
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
}
#[test]
fn test_floating_point_instructions() {
let mut mf = MachineFunction::new("fp_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut addss = MachineInstr::new(X86Opcode::ADDSS as u32);
addss.operands.push(MachineOperand::Reg(MCRegister(16)));
addss.operands.push(MachineOperand::Reg(MCRegister(17)));
b0.instructions.push(addss);
let mut mulss = MachineInstr::new(X86Opcode::MULSS as u32);
mulss.operands.push(MachineOperand::Reg(MCRegister(18)));
mulss.operands.push(MachineOperand::Reg(MCRegister(19)));
b0.instructions.push(mulss);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut tm = X86MachineTraceMetrics::new();
let cycles = tm.analyze_trace(&b0.instructions, &HashSet::new());
assert!(cycles >= 3);
}
#[test]
fn test_all_opcodes_in_latency_table() {
let tm = X86MachineTraceMetrics::new();
for op in &[
X86Opcode::ADD,
X86Opcode::SUB,
X86Opcode::AND,
X86Opcode::OR,
X86Opcode::XOR,
X86Opcode::CMP,
X86Opcode::TEST,
X86Opcode::MOV,
X86Opcode::LEA,
] {
assert!(
tm.latencies.contains_key(&(*op as u32)),
"Missing latency for {:?}",
op
);
}
}
#[test]
fn test_div_latency() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.latencies.get(&(X86Opcode::IDIV as u32)), Some(&26));
assert_eq!(tm.latencies.get(&(X86Opcode::DIV as u32)), Some(&26));
}
#[test]
fn test_sse_latency() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.latencies.get(&(X86Opcode::ADDSS as u32)), Some(&3));
assert_eq!(tm.latencies.get(&(X86Opcode::DIVSS as u32)), Some(&11));
assert_eq!(tm.latencies.get(&(X86Opcode::DIVSD as u32)), Some(&13));
}
#[test]
fn test_avx_latency() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.latencies.get(&(X86Opcode::VADDPS as u32)), Some(&3));
assert_eq!(tm.latencies.get(&(X86Opcode::VMULPS as u32)), Some(&4));
}
#[test]
fn test_cmov_latency() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.latencies.get(&(X86Opcode::CMOVE as u32)), Some(&2));
assert_eq!(tm.latencies.get(&(X86Opcode::CMOVNE as u32)), Some(&2));
assert_eq!(tm.latencies.get(&(X86Opcode::CMOVG as u32)), Some(&2));
}
#[test]
fn test_branch_folding_redirect_chains() {
let mut mf = MachineFunction::new("chain_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 4];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "jmp_to_2");
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "jmp_to_3");
b2.instructions.push(make_jmp_instr(3));
b2.predecessors = vec![1];
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "target");
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![2];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "fallthrough");
b4.instructions.push(make_ret_instr());
b4.predecessors = vec![0];
mf.add_block(b4);
mf.entry_block = 0;
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert!(bf.branches_folded >= 1);
}
#[test]
fn test_tail_merge_identical_blocks() {
let mut mf = MachineFunction::new("tail_merge");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 0));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "ident_a");
b1.instructions.push(make_mov_instr(0, 1));
b1.instructions.push(make_jmp_instr(3));
b1.predecessors = vec![0];
b1.successors = vec![3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "ident_b");
b2.instructions.push(make_mov_instr(0, 1));
b2.instructions.push(make_jmp_instr(3));
b2.predecessors = vec![0];
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "merge");
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1, 2];
mf.add_block(b3);
mf.entry_block = 0;
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert!(bf.tail_merged_blocks >= 1);
}
#[test]
fn test_jump_table_optimization() {
let mut mf = MachineFunction::new("jump_table");
let mut b0 = MachineBasicBlock::new(0, "dispatch");
b0.is_entry = true;
b0.successors = vec![1, 1, 1, 1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "target");
b1.instructions.push(make_ret_instr());
b1.predecessors = vec![0];
mf.add_block(b1);
mf.entry_block = 0;
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert!(bf.branches_folded >= 1);
}
#[test]
fn test_combiner_all_patterns_single_block() {
let mut mf = MachineFunction::new("comb_all");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut inc = MachineInstr::new(X86Opcode::INC as u32);
inc.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(inc);
let mut dec = MachineInstr::new(X86Opcode::DEC as u32);
dec.operands.push(MachineOperand::Reg(MCRegister(1)));
b0.instructions.push(dec);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert!(combiner.combined >= 2);
}
#[test]
fn test_peephole_all_patterns_single_block() {
let mut mf = MachineFunction::new("peep_all");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0));
b0.instructions.push(make_cmp_instr(0, 0));
let mut or_instr = MachineInstr::new(X86Opcode::OR as u32);
or_instr.operands.push(MachineOperand::Reg(MCRegister(1)));
or_instr.operands.push(MachineOperand::Imm(0));
b0.instructions.push(or_instr);
let mut xor_instr = MachineInstr::new(X86Opcode::XOR as u32);
xor_instr.operands.push(MachineOperand::Reg(MCRegister(2)));
xor_instr.operands.push(MachineOperand::Reg(MCRegister(2)));
b0.instructions.push(xor_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.redundant_movs_eliminated >= 1);
assert!(peep.cmp_zero_to_test >= 1);
assert!(peep.identity_ops_removed >= 1);
assert!(peep.xor_to_xor32 >= 1);
}
#[test]
fn test_verifier_all_checks_pass() {
let mut mf = MachineFunction::new("verify_all");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_add_instr(0, 2));
let mut mov = MachineInstr::new(X86Opcode::MOV as u32);
mov.flags.is_move_reg = true;
mov.operands.push(MachineOperand::Reg(MCRegister(2)));
mov.operands.push(MachineOperand::Imm(42));
b0.instructions.push(mov);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.warnings.is_empty());
}
#[test]
fn test_outliner_scan_with_repeated_sequences() {
let mut mf = MachineFunction::new("outline_test");
let mut b0 = MachineBasicBlock::new(0, "b0");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_mov_instr(2, 0));
b0.instructions.push(make_mov_instr(3, 2));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_add_instr(4, 5));
b1.instructions.push(make_mov_instr(6, 4));
b1.instructions.push(make_mov_instr(7, 6));
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "b2");
b2.instructions.push(make_add_instr(8, 9));
b2.instructions.push(make_mov_instr(10, 8));
b2.instructions.push(make_mov_instr(11, 10));
b2.instructions.push(make_ret_instr());
b2.predecessors = vec![1];
mf.add_block(b2);
mf.entry_block = 0;
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.min_occurrences = 2;
outliner.scan_function(&mf);
}
#[test]
fn test_full_pipeline_with_all_passes() {
let mut mf = MachineFunction::new("full_pipe");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0));
b0.instructions.push(make_cmp_instr(0, 10));
b0.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 4));
b0.successors = vec![1, 4];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "preheader");
b1.instructions.push(make_add_instr(0, 1));
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "loop_header");
b2.instructions.push(make_cmp_instr(0, 100));
b2.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 4));
b2.predecessors = vec![1, 3];
b2.successors = vec![3, 4];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "loop_body");
b3.instructions.push(make_add_instr(0, 1));
b3.instructions.push(make_jmp_instr(2));
b3.predecessors = vec![2];
b3.successors = vec![2];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "exit");
b4.is_exit = true;
b4.instructions.push(make_ret_instr());
b4.predecessors = vec![0, 2];
mf.add_block(b4);
mf.entry_block = 0;
mf.exit_blocks = vec![4];
let mut opt2 = X86CodeGenOpt2::new();
opt2.verify_after_each_pass = true;
opt2.max_iterations = 3;
let stats = opt2.run(&mut mf);
opt2.print_stats(&stats);
}
#[test]
fn test_consecutive_identical_movs_cse() {
let mut mf = MachineFunction::new("cse_movs");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_mov_instr(0, 1)); b0.instructions.push(make_mov_instr(0, 1)); b0.instructions.push(make_mov_instr(0, 2)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
assert!(cse.eliminated >= 2);
}
#[test]
fn test_bpi_handles_empty_function() {
let mf = MachineFunction::new("empty");
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
assert!(bpi.edge_probs.is_empty());
}
#[test]
fn test_bpi_single_block() {
let mut mf = MachineFunction::new("single");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
assert!(bpi.get_block_count(0) >= 1000);
}
#[test]
fn test_bpi_multiple_predecessors() {
let mut mf = MachineFunction::new("multi_pred");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(3));
b0.successors = vec![3];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_jmp_instr(3));
b1.successors = vec![3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "b2");
b2.instructions.push(make_jmp_instr(3));
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "merge");
b3.predecessors = vec![0, 1, 2];
b3.instructions.push(make_ret_instr());
mf.add_block(b3);
mf.entry_block = 0;
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
assert!(bpi.get_block_count(3) > 0);
}
#[test]
fn test_verifier_handles_empty_function() {
let mf = MachineFunction::new("empty");
let mut verifier = X86MachineVerifier::new();
assert!(verifier.verify(&mf));
assert_eq!(verifier.blocks_verified, 0);
}
#[test]
fn test_trace_metrics_with_div_chain() {
let mut tm = X86MachineTraceMetrics::new();
let mut div = MachineInstr::new(X86Opcode::IDIV as u32);
div.operands.push(MachineOperand::Reg(MCRegister(0)));
div.operands.push(MachineOperand::Reg(MCRegister(1)));
let cycles = tm.analyze_trace(&[div], &HashSet::new());
assert_eq!(cycles, 26);
}
#[test]
fn test_trace_metrics_mixed_operations() {
let mut tm = X86MachineTraceMetrics::new();
let instrs = vec![
make_mov_instr(0, 1), make_add_instr(0, 2), make_add_instr(0, 3), ];
let cycles = tm.analyze_trace(&instrs, &HashSet::new());
assert_eq!(cycles, 3);
}
#[test]
fn test_address_mode_with_negative_offset() {
let mut mf = MachineFunction::new("neg_offset");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut load = MachineInstr::new(X86Opcode::MOV as u32);
load.operands.push(MachineOperand::Reg(MCRegister(0)));
load.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: -8,
size: 4,
});
b0.instructions.push(load);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut am_opt = X86AddressModeOptimizer::new();
am_opt.run(&mut mf);
assert!(am_opt.modes_simplified >= 1);
}
#[test]
fn test_combiner_no_combination_for_different_opcodes() {
let mut mf = MachineFunction::new("no_comb");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_mov_instr(2, 3));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert_eq!(combiner.combined, 0);
}
#[test]
fn test_licm_no_hoist_for_side_effect_instructions() {
let mut mf = MachineFunction::new("side_effect");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "header");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 3));
b1.predecessors = vec![0, 2];
b1.successors = vec![2, 3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "body");
let mut call = MachineInstr::new(X86Opcode::CALL as u32);
call.flags.is_call = true;
call.flags.has_side_effects = true;
b2.instructions.push(call);
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "exit");
b3.is_exit = true;
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
let mut licm = X86MachineLICM::new();
licm.run(&mut mf);
}
#[test]
fn test_sinking_does_not_sink_side_effects() {
let mut mf = MachineFunction::new("sink_side");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut store = MachineInstr::new(X86Opcode::MOV as u32);
store.flags.is_store = true;
store.flags.has_side_effects = true;
store.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
store.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(store);
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_ret_instr());
b1.predecessors = vec![0];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_ret_instr());
b2.predecessors = vec![0];
mf.add_block(b2);
mf.entry_block = 0;
let mut sinking = X86MachineSinking::new();
sinking.run(&mut mf);
assert_eq!(sinking.sunk, 0);
}
#[test]
fn test_constant_hoisting_in_nested_loops() {
let mut mf = MachineFunction::new("nested_const");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions
.push(make_mov_instr_imm(0, 0xABCD_EF01_2345_6789));
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "outer");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 3));
b1.predecessors = vec![0, 2];
b1.successors = vec![2, 3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "latch");
b2.instructions.push(make_add_instr(0, 1));
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "exit");
b3.is_exit = true;
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
let mut hoist = X86ConstantHoisting::new();
hoist.run(&mut mf);
}
#[test]
fn test_macro_fusion_all_jcc_variants() {
for op in X86Opcode::JO as u32..=X86Opcode::JG as u32 {
assert!(X86MacroFusionPrep::is_jcc_opcode(op));
}
}
#[test]
fn test_flags_optimizer_all_setcc_variants() {
for op in X86Opcode::SETO as u32..=X86Opcode::SETG as u32 {
assert!(X86FlagsOptimizer::is_setcc(op));
}
}
#[test]
fn test_regclass_type_debug() {
let gpr = RegClassType::GPR;
let xmm = RegClassType::XMM;
let other = RegClassType::Other;
assert_ne!(gpr, xmm);
assert_ne!(xmm, other);
assert_ne!(gpr, other);
assert_eq!(gpr, RegClassType::GPR);
}
#[test]
fn test_opt2_default_has_verify_disabled() {
let opt2 = X86CodeGenOpt2::default();
assert!(!opt2.verify_after_each_pass);
}
#[test]
fn test_opt2_custom_max_iterations() {
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 5;
assert_eq!(opt2.max_iterations, 5);
}
#[test]
fn test_opt2_with_verification_enabled() {
let mut mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
opt2.verify_after_each_pass = true;
let stats = opt2.run(&mut mf);
assert_eq!(stats.verification_errors, 0);
}
#[test]
fn test_pressure_tracker_liveness_convergence() {
let mf = make_test_mf();
let mut tracker = X86RegisterPressureTracker::new();
tracker.compute_liveness(&mf);
for block in &mf.blocks {
assert!(tracker.block_live_in.contains_key(&block.id));
assert!(tracker.block_live_out.contains_key(&block.id));
}
}
#[test]
fn test_cfg_simplifier_handles_diamond() {
let mut mf = make_test_mf();
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
}
#[test]
fn test_cfg_simplifier_handles_self_loop() {
let mut mf = MachineFunction::new("self_loop");
let mut b0 = MachineBasicBlock::new(0, "loop");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 10));
b0.instructions
.push(make_jcc_instr(X86Opcode::JL as u32, 0));
b0.successors = vec![0, 1];
b0.predecessors = vec![0];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "exit");
b1.instructions.push(make_ret_instr());
b1.predecessors = vec![0];
mf.add_block(b1);
mf.entry_block = 0;
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
}
#[test]
fn test_copy_propagation_full() {
let mut mf = MachineFunction::new("copy_prop_full");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_add_instr(0, 2));
b0.instructions.push(make_mov_instr(3, 0));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cp = X86MachineCopyPropagation::new();
cp.run(&mut mf);
}
#[test]
fn test_load_store_folding_integration() {
let mut mf = MachineFunction::new("load_fold_int");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut mov = MachineInstr::new(X86Opcode::MOV as u32);
mov.operands.push(MachineOperand::Reg(MCRegister(0)));
mov.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 8,
size: 4,
});
b0.instructions.push(mov);
let mut and_instr = MachineInstr::new(X86Opcode::AND as u32);
and_instr.operands.push(MachineOperand::Reg(MCRegister(0)));
and_instr.operands.push(MachineOperand::Imm(0xFF));
b0.instructions.push(and_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut lso = X86LoadStoreOptimizer::new();
lso.run(&mut mf);
assert!(lso.loads_folded >= 1);
}
#[test]
fn test_two_address_commutation() {
let mut mf = MachineFunction::new("twoaddr_comm");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(5, 3));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut pass = X86TwoAddressInstructionPass::new();
pass.run(&mut mf);
assert!(pass.commuted >= 1);
}
#[test]
fn test_stack_slot_coloring_runs() {
let mut mf = MachineFunction::new("stack_colors");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
for i in 0..5i64 {
let mut load = MachineInstr::new(X86Opcode::MOV as u32);
load.operands
.push(MachineOperand::Reg(MCRegister(i as u32)));
load.operands.push(MachineOperand::Mem {
base: MCRegister(4),
offset: -(8 + i * 8),
size: 8,
});
b0.instructions.push(load);
}
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut ssc = X86StackSlotColoring::new();
ssc.run(&mut mf);
}
#[test]
fn test_outliner_handles_cross_block_disabled() {
let mut outliner = X86MachineOutliner::new();
assert!(!outliner.allow_cross_block);
outliner.allow_cross_block = true;
assert!(outliner.allow_cross_block);
}
#[test]
fn test_combiner_respects_disabled_flags() {
let mut mf = MachineFunction::new("no_combine");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut inc = MachineInstr::new(X86Opcode::INC as u32);
inc.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(inc);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.enable_inc_dec_opt = false;
combiner.run(&mut mf);
assert_eq!(combiner.combined, 0);
}
#[test]
fn test_cse_respects_max_scan_window() {
let mut mf = MachineFunction::new("cse_window");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
for i in 0..50u32 {
b0.instructions.push(make_add_instr(i % 16, (i + 1) % 16));
}
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.max_scan_window = 10;
cse.run(&mut mf);
}
#[test]
fn test_licm_respects_pressure_limits() {
let mut mf = MachineFunction::new("licm_pressure");
let mut licm = X86MachineLICM::new();
licm.max_pressure_gpr = 5;
licm.run(&mut mf);
}
#[test]
fn test_sinking_max_iterations() {
let mut mf = make_test_mf();
let mut sinking = X86MachineSinking::new();
sinking.max_iterations = 1;
sinking.run(&mut mf);
}
#[test]
fn test_block_placement_cold_threshold() {
let mut mf = make_test_mf();
let mut placement = X86MachineBlockPlacement::new(true);
placement.cold_threshold_percent = 50.0;
placement.run(&mut mf);
}
#[test]
fn test_branch_folding_without_jump_tables() {
let mut mf = make_test_mf();
let mut bf = X86BranchFolding::new();
bf.optimize_jump_tables = false;
bf.run(&mut mf);
}
#[test]
fn test_outliner_min_occurrences_config() {
let mut outliner = X86MachineOutliner::new();
outliner.min_occurrences = 5;
assert_eq!(outliner.min_occurrences, 5);
}
#[test]
fn test_outliner_min_length_config() {
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 10;
assert_eq!(outliner.min_length, 10);
}
#[test]
fn test_verifier_with_landing_pad() {
let mut mf = MachineFunction::new("landing");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "lpad");
b1.is_landing_pad = true;
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
}
#[test]
fn test_opt2_post_ra_no_verify() {
let mut mf = make_test_mf();
let mut opt2 = X86CodeGenOpt2::new();
let stats = opt2.run_post_ra(&mut mf);
assert!(stats.peephole_redundant_movs >= 0);
}
#[test]
fn test_make_test_mf_has_correct_structure() {
let mf = make_test_mf();
assert_eq!(mf.blocks.len(), 4);
assert_eq!(mf.entry_block, 0);
assert_eq!(mf.exit_blocks.len(), 1);
assert_eq!(mf.exit_blocks[0], 3);
let entry = mf.block_by_id(0).unwrap();
assert_eq!(entry.successors.len(), 2);
}
#[test]
fn test_make_loop_mf_has_correct_structure() {
let mf = make_loop_mf();
assert_eq!(mf.blocks.len(), 4);
let header = mf.block_by_id(1).unwrap();
assert_eq!(header.predecessors.len(), 2);
}
#[test]
fn test_outliner_hash_handles_all_operand_types() {
let mut a = MachineInstr::new(X86Opcode::MOV as u32);
a.operands.push(MachineOperand::Reg(MCRegister(1)));
a.operands.push(MachineOperand::Imm(42));
let mut b = MachineInstr::new(X86Opcode::MOV as u32);
b.operands.push(MachineOperand::Reg(MCRegister(1)));
b.operands.push(MachineOperand::Imm(43));
let ha = X86MachineOutliner::hash_sequence(&[a]);
let hb = X86MachineOutliner::hash_sequence(&[b]);
assert_ne!(ha, hb);
}
#[test]
fn test_trace_metrics_get_trace_cycles_empty() {
let tm = X86MachineTraceMetrics::new();
assert_eq!(tm.get_trace_cycles(), 0);
}
#[test]
fn test_combiner_cmp_jcc_fusion() {
let mut mf = MachineFunction::new("cmp_jcc_fusion");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert!(combiner.combined >= 1);
}
#[test]
fn test_peephole_mov_to_movzx_combine() {
let mut mf = MachineFunction::new("movzx_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 10)); b0.instructions.push(make_mov_instr(1, 0));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
assert!(peep.mov_to_movzx >= 1);
}
#[test]
fn test_verifier_checks_all_blocks() {
let mf = make_test_mf();
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert_eq!(verifier.blocks_verified, mf.blocks.len());
}
#[test]
fn test_opt2_stats_equality_reflexive() {
let stats = X86Opt2Stats::new();
assert_eq!(stats, stats);
}
#[test]
fn test_opt2_stats_default_different_from_modified() {
let mut stats = X86Opt2Stats::new();
assert_eq!(stats.branches_folded, 0);
stats.branches_folded = 42;
assert_ne!(stats, X86Opt2Stats::new());
}
#[test]
fn test_block_placement_loop_alignment_zero_disables() {
let mf = make_test_mf();
let mut placement = X86MachineBlockPlacement::new(true);
placement.loop_header_alignment = 0;
let order = placement.run(&mut mf.clone());
assert_eq!(order.len(), mf.blocks.len());
}
#[test]
fn test_cse_operand_types_not_equal() {
let cse = X86MachineCSE::new(false);
assert!(!cse.operand_equals(&MachineOperand::Reg(MCRegister(1)), &MachineOperand::Imm(1)));
assert!(!cse.operand_equals(&MachineOperand::Imm(1), &MachineOperand::Imm(2)));
assert!(!cse.operand_equals(&MachineOperand::Block(1), &MachineOperand::Block(2)));
}
#[test]
fn test_cse_operand_fp_equals() {
let cse = X86MachineCSE::new(false);
assert!(cse.operand_equals(&MachineOperand::FPImm(1.0), &MachineOperand::FPImm(1.0)));
assert!(!cse.operand_equals(&MachineOperand::FPImm(1.0), &MachineOperand::FPImm(2.0)));
}
#[test]
fn test_cse_operand_global_equals() {
let cse = X86MachineCSE::new(false);
assert!(cse.operand_equals(
&MachineOperand::Global("foo".to_string()),
&MachineOperand::Global("foo".to_string())
));
assert!(!cse.operand_equals(
&MachineOperand::Global("foo".to_string()),
&MachineOperand::Global("bar".to_string())
));
}
#[test]
fn test_licm_loop_finding_empty_function() {
let mf = MachineFunction::new("empty");
let mut licm = X86MachineLICM::new();
licm.detect_loops(&mf);
assert!(licm.loop_info.is_empty());
}
#[test]
fn test_licm_loop_finding_single_block() {
let mut mf = MachineFunction::new("single");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut licm = X86MachineLICM::new();
licm.detect_loops(&mf);
assert!(licm.loop_info.is_empty());
}
#[test]
fn test_splitting_critical_edges_integration() {
let mut mf = MachineFunction::new("crit_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_ret_instr());
b1.predecessors = vec![0, 3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "b2");
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![0];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "b3");
b3.instructions.push(make_jmp_instr(1));
b3.successors = vec![1];
mf.add_block(b3);
mf.entry_block = 0;
let blocks_before = mf.blocks.len();
let mut sink = X86MachineSinking::new();
sink.split_critical_edges_in_func(&mut mf);
let blocks_after = mf.blocks.len();
assert!(blocks_after >= blocks_before);
}
#[test]
fn test_branch_folding_threads_jumps_through_empty() {
let mut mf = MachineFunction::new("thread_test");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "jmp_only");
b1.instructions.push(make_jmp_instr(2));
b1.predecessors = vec![0];
b1.successors = vec![2];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "target");
b2.predecessors = vec![1];
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut bf = X86BranchFolding::new();
bf.run(&mut mf);
assert!(bf.branches_folded >= 1);
}
#[test]
fn test_trace_metrics_with_unused_regs() {
let mut tm = X86MachineTraceMetrics::new();
let instrs = vec![
make_add_instr(0, 1), make_add_instr(2, 3), make_mov_instr(4, 0), ];
let cycles = tm.analyze_trace(&instrs, &HashSet::new());
assert_eq!(cycles, 2);
}
#[test]
fn test_resource_pressure_all_types() {
let mut b0 = MachineBasicBlock::new(0, "entry");
let mut load = MachineInstr::new(X86Opcode::MOV as u32);
load.flags.is_load = true;
load.flags.may_load = true;
load.operands.push(MachineOperand::Reg(MCRegister(0)));
load.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
b0.instructions.push(load);
let mut store = MachineInstr::new(X86Opcode::MOV as u32);
store.flags.is_store = true;
store.flags.may_store = true;
store.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
store.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(store);
let mut branch = MachineInstr::new(X86Opcode::JMP as u32);
branch.flags.is_branch = true;
branch.operands.push(MachineOperand::Block(1));
b0.instructions.push(branch);
let mut tm = X86MachineTraceMetrics::new();
let pressure = tm.estimate_resource_pressure(&b0.instructions);
assert!(pressure >= 1);
}
#[test]
fn test_outliner_candidate_sort_order() {
let mut outliner = X86MachineOutliner::new();
outliner.candidates.push(OutlineCandidateX86 {
hash: 1,
length: 5,
savings: 50,
instruction_patterns: vec![],
occurrences: vec![(0, 0)],
});
outliner.candidates.push(OutlineCandidateX86 {
hash: 2,
length: 3,
savings: 10,
instruction_patterns: vec![],
occurrences: vec![(1, 0)],
});
outliner.candidates.push(OutlineCandidateX86 {
hash: 3,
length: 8,
savings: 100,
instruction_patterns: vec![],
occurrences: vec![(2, 0)],
});
outliner
.candidates
.sort_by_key(|c| std::cmp::Reverse(c.savings));
assert_eq!(outliner.candidates[0].savings, 100);
assert_eq!(outliner.candidates[1].savings, 50);
assert_eq!(outliner.candidates[2].savings, 10);
}
#[test]
fn test_x86_64_allocatable_constants() {
assert_eq!(_X86_64_ALLOCATABLE_GPRS, 13);
assert_eq!(_X86_64_ALLOCATABLE_XMMS, 16);
}
#[test]
fn test_default_x86_latency_constant() {
assert_eq!(DEFAULT_X86_LATENCY, 1);
}
#[test]
fn test_loop_align_boundary_constant() {
assert_eq!(LOOP_ALIGN_BOUNDARY, 16);
}
#[test]
fn test_outliner_constants() {
assert_eq!(OUTLINER_MAX_CANDIDATE_LEN, 32);
assert_eq!(OUTLINER_MIN_SAVINGS, 4);
}
#[test]
fn test_address_mode_empty_function() {
let mut mf = MachineFunction::new("empty");
let mut opt = X86AddressModeOptimizer::new();
opt.run(&mut mf);
assert_eq!(opt.modes_simplified, 0);
}
#[test]
fn test_loop_unroller_max_instructions_config() {
let mut unroller = X86MachineLoopUnroller::new();
unroller.max_instructions = 8;
assert_eq!(unroller.max_instructions, 8);
}
#[test]
fn test_loop_unroller_max_unroll_config() {
let mut unroller = X86MachineLoopUnroller::new();
unroller.max_unroll = 8;
assert_eq!(unroller.max_unroll, 8);
}
#[test]
fn test_conditional_move_optimizer_default() {
let opt = X86ConditionalMoveOptimizer::default();
assert_eq!(opt.cmov_to_branch, 0);
assert_eq!(opt.branch_to_cmov, 0);
}
#[test]
fn test_load_store_optimizer_default() {
let opt = X86LoadStoreOptimizer::default();
assert_eq!(opt.loads_folded, 0);
assert_eq!(opt.stores_merged, 0);
assert_eq!(opt.redundant_loads_removed, 0);
}
#[test]
fn test_two_address_pass_default() {
let pass = X86TwoAddressInstructionPass::default();
assert_eq!(pass.commuted, 0);
assert_eq!(pass.coalesced, 0);
}
#[test]
fn test_is_alu_op_all_variants() {
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::ADD as u32));
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::SUB as u32));
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::AND as u32));
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::OR as u32));
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::XOR as u32));
assert!(X86LoadStoreOptimizer::is_alu_op(X86Opcode::CMP as u32));
assert!(!X86LoadStoreOptimizer::is_alu_op(X86Opcode::MOV as u32));
assert!(!X86LoadStoreOptimizer::is_alu_op(X86Opcode::LEA as u32));
}
#[test]
fn test_is_commutative_two_address() {
assert!(X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::ADD as u32
));
assert!(X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::AND as u32
));
assert!(X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::OR as u32
));
assert!(X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::XOR as u32
));
assert!(X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::IMUL as u32
));
assert!(!X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::SUB as u32
));
assert!(!X86TwoAddressInstructionPass::is_commutative_two_address(
X86Opcode::MOV as u32
));
}
#[test]
fn test_cfg_simplifier_preserves_entry() {
let mut mf = make_test_mf();
let entry_before = mf.entry_block;
let mut simplifier = X86MachineCFGSimplifier::new();
simplifier.run(&mut mf);
assert_eq!(mf.entry_block, entry_before);
}
#[test]
fn test_outliner_scan_functions_empty() {
let mut outliner = X86MachineOutliner::new();
outliner.scan_functions(&[]);
assert!(outliner.candidates.is_empty());
}
#[test]
fn test_constant_hoisting_default() {
let hoist = X86ConstantHoisting::default();
assert_eq!(hoist.constants_hoisted, 0);
assert_eq!(hoist.bytes_saved, 0);
}
#[test]
fn test_address_mode_optimizer_default() {
let opt = X86AddressModeOptimizer::default();
assert_eq!(opt.modes_simplified, 0);
assert!(opt.enable_rip_relative);
}
#[test]
fn test_cfg_simplifier_default() {
let s = X86MachineCFGSimplifier::default();
assert_eq!(s.blocks_merged, 0);
assert_eq!(s.empty_blocks_removed, 0);
assert_eq!(s.unreachable_blocks_removed, 0);
}
#[test]
fn test_loop_unroller_default() {
let u = X86MachineLoopUnroller::default();
assert_eq!(u.max_unroll, 4);
assert_eq!(u.max_instructions, 16);
assert_eq!(u.loops_unrolled, 0);
}
#[test]
fn test_copy_propagation_default() {
let cp = X86MachineCopyPropagation::default();
assert_eq!(cp.copies_eliminated, 0);
}
#[test]
fn test_stack_slot_coloring_default() {
let ssc = X86StackSlotColoring::default();
assert_eq!(ssc.slots_merged, 0);
assert_eq!(ssc.bytes_saved, 0);
}
#[test]
fn test_branch_prob_info_multiple_successors() {
let mut mf = MachineFunction::new("multi_succ");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.successors = vec![1, 2, 3, 4, 5];
mf.add_block(b0);
for i in 1..=5u32 {
let mut b = MachineBasicBlock::new(i, format!("b{}", i));
b.instructions.push(make_ret_instr());
b.predecessors = vec![0];
mf.add_block(b);
}
mf.entry_block = 0;
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
for i in 1..=5u32 {
assert!(bpi.edge_probs.contains_key(&(0, i)));
}
let sum: f64 = (1..=5u32).map(|i| bpi.get_edge_probability(0, i)).sum();
assert!((sum - 1.0).abs() < 0.01);
}
#[test]
fn test_outliner_does_not_outline_single_occurrence() {
let mut mf = MachineFunction::new("single_occur");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_mov_instr(2, 0));
b0.instructions.push(make_mov_instr(3, 2));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.min_occurrences = 2; outliner.scan_function(&mf);
assert!(outliner.candidates.is_empty());
}
#[test]
fn test_verifier_reports_terminator_not_last() {
let mut mf = MachineFunction::new("term_mid");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
b0.instructions.push(make_mov_instr(0, 1)); mf.add_block(b0);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.errors.is_empty());
}
#[test]
fn test_verifier_warns_branch_without_label() {
let mut mf = MachineFunction::new("branch_no_label");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut jmp = MachineInstr::new(X86Opcode::JE as u32);
jmp.flags.is_terminator = true;
jmp.flags.is_branch = true;
b0.instructions.push(jmp);
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
assert!(!verifier.warnings.is_empty());
}
#[test]
fn test_combiner_leaves_non_combining_alone() {
let mut mf = MachineFunction::new("no_change");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_mov_instr(2, 3));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let instr_count_before: usize = mf.blocks.iter().map(|b| b.instructions.len()).sum();
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
let instr_count_after: usize = mf.blocks.iter().map(|b| b.instructions.len()).sum();
assert_eq!(instr_count_before, instr_count_after);
}
#[test]
fn test_peephole_converges() {
let mut mf = MachineFunction::new("converge");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut neg1 = MachineInstr::new(X86Opcode::NEG as u32);
neg1.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(neg1);
let mut neg2 = MachineInstr::new(X86Opcode::NEG as u32);
neg2.operands.push(MachineOperand::Reg(MCRegister(0)));
b0.instructions.push(neg2);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let instr_before = mf.block_by_id(0).unwrap().instructions.len();
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
let instr_after = mf.block_by_id(0).unwrap().instructions.len();
assert_eq!(instr_before - instr_after, 2);
}
#[test]
fn test_large_function_all_passes() {
let mut mf = MachineFunction::new("large_func");
for i in 0..50u32 {
let mut b = MachineBasicBlock::new(i, format!("block_{}", i));
match i % 6 {
0 => {
b.instructions.push(make_mov_instr(i % 16, (i + 1) % 16));
b.instructions.push(make_add_instr(i % 16, (i + 2) % 16));
}
1 => {
b.instructions.push(make_cmp_instr(i % 16, 0));
b.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, (i + 1) % 50));
b.successors = vec![(i + 1) % 50, (i + 2) % 50];
}
2 => {
let mut xor = MachineInstr::new(X86Opcode::XOR as u32);
xor.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
xor.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
b.instructions.push(xor);
}
3 => {
b.instructions.push(make_mov_instr_imm(i % 16, 0xDEAD_BEEF));
}
4 => {
let mut inc = MachineInstr::new(X86Opcode::INC as u32);
inc.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
b.instructions.push(inc);
}
_ => {
let mut dec = MachineInstr::new(X86Opcode::DEC as u32);
dec.operands.push(MachineOperand::Reg(MCRegister(i % 16)));
b.instructions.push(dec);
}
}
if i == 0 {
b.is_entry = true;
}
if i == 49 {
b.instructions.push(make_ret_instr());
b.is_exit = true;
} else if b.successors.is_empty() {
b.instructions.push(make_jmp_instr(i + 1));
b.successors = vec![i + 1];
}
if i > 0 && !b.predecessors.contains(&(i - 1)) {
}
mf.add_block(b);
}
mf.entry_block = 0;
mf.exit_blocks = vec![49];
let mut opt2 = X86CodeGenOpt2::new();
opt2.verify_after_each_pass = true;
opt2.max_iterations = 2;
let stats = opt2.run(&mut mf);
assert_eq!(stats.verification_errors, 0);
assert!(stats.iterations > 0);
}
#[test]
fn test_cse_with_memory_operands() {
let mut mf = MachineFunction::new("cse_mem");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut load1 = MachineInstr::new(X86Opcode::MOV as u32);
load1.operands.push(MachineOperand::Reg(MCRegister(0)));
load1.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
b0.instructions.push(load1.clone());
b0.instructions.push(load1); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(false);
cse.run(&mut mf);
}
#[test]
fn test_licm_hoists_invariant_from_nested_loops() {
let mut mf = MachineFunction::new("nested_inv");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "outer_hdr");
b1.instructions.push(make_cmp_instr(0, 10));
b1.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 6));
b1.predecessors = vec![0, 5];
b1.successors = vec![2, 6];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "inner_hdr");
b2.instructions.push(make_cmp_instr(1, 5));
b2.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 4));
b2.predecessors = vec![1, 3];
b2.successors = vec![3, 4];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "inner_body");
b3.instructions.push(make_mov_instr_imm(2, 0xABCD)); b3.instructions.push(make_add_instr(1, 1));
b3.instructions.push(make_jmp_instr(2));
b3.predecessors = vec![2];
b3.successors = vec![2];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "inner_exit");
b4.instructions.push(make_add_instr(0, 1));
b4.instructions.push(make_jmp_instr(5));
b4.predecessors = vec![2];
b4.successors = vec![5];
mf.add_block(b4);
let mut b5 = MachineBasicBlock::new(5, "outer_latch");
b5.instructions.push(make_add_instr(0, 1));
b5.instructions.push(make_jmp_instr(1));
b5.predecessors = vec![4];
b5.successors = vec![1];
mf.add_block(b5);
let mut b6 = MachineBasicBlock::new(6, "exit");
b6.is_exit = true;
b6.instructions.push(make_ret_instr());
b6.predecessors = vec![1];
mf.add_block(b6);
mf.entry_block = 0;
mf.exit_blocks = vec![6];
let mut licm = X86MachineLICM::new();
licm.run(&mut mf);
}
#[test]
fn test_all_passes_on_function_with_calls() {
let mut mf = MachineFunction::new("with_calls");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut call = MachineInstr::new(X86Opcode::CALL as u32);
call.flags.is_call = true;
call.flags.has_side_effects = true;
call.operands.push(MachineOperand::Block(100));
b0.instructions.push(call);
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 1;
opt2.run(&mut mf);
}
#[test]
fn test_outliner_candidate_with_many_occurrences() {
let mut mf = MachineFunction::new("multi_occur");
for i in 0..10u32 {
let mut b = MachineBasicBlock::new(i, format!("block_{}", i));
b.instructions.push(make_add_instr(i % 16, (i + 1) % 16));
b.instructions.push(make_mov_instr((i + 2) % 16, i % 16));
if i < 9 {
b.instructions.push(make_jmp_instr(i + 1));
b.successors = vec![i + 1];
} else {
b.instructions.push(make_ret_instr());
}
if i > 0 {
b.predecessors = vec![i - 1];
}
if i == 0 {
b.is_entry = true;
}
mf.add_block(b);
}
mf.entry_block = 0;
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.min_occurrences = 2;
outliner.scan_function(&mf);
}
#[test]
fn test_block_placement_with_irreducible_loop() {
let mut mf = MachineFunction::new("irred_place");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "header");
b1.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 2));
b1.predecessors = vec![0, 2, 3];
b1.successors = vec![2, 4];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "loop_a");
b2.instructions.push(make_jmp_instr(1));
b2.predecessors = vec![1];
b2.successors = vec![1];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "loop_b");
b3.instructions.push(make_jmp_instr(1));
b3.successors = vec![1];
mf.add_block(b3);
let mut b4 = MachineBasicBlock::new(4, "exit");
b4.instructions.push(make_ret_instr());
b4.predecessors = vec![1];
mf.add_block(b4);
mf.entry_block = 0;
let mut placement = X86MachineBlockPlacement::new(true);
placement.run(&mut mf);
}
#[test]
fn test_macro_fusion_reordering_preserves_correctness() {
let mut mf = MachineFunction::new("fusion_reorder");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_cmp_instr(0, 5));
b0.instructions.push(make_mov_instr(1, 2));
b0.instructions
.push(make_jcc_instr(X86Opcode::JNE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_ret_instr());
mf.add_block(b2);
mf.entry_block = 0;
let mut fusion = X86MacroFusionPrep::new();
fusion.run(&mut mf);
let block = mf.block_by_id(0).unwrap();
let idx_cmp = block
.instructions
.iter()
.position(|i| i.opcode == X86Opcode::CMP as u32);
let idx_jne = block
.instructions
.iter()
.position(|i| i.opcode == X86Opcode::JNE as u32);
if let (Some(c), Some(j)) = (idx_cmp, idx_jne) {
assert_eq!(j, c + 1, "JNE should be right after CMP for fusion");
assert!(fusion.fusible_pairs >= 1);
}
}
#[test]
fn test_verifier_detects_ssa_violation_across_blocks() {
let mut mf = MachineFunction::new("ssa_cross");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut def1 = MachineInstr::new(X86Opcode::MOV as u32);
def1.flags.is_move_reg = true;
def1.operands.push(MachineOperand::Reg(MCRegister(0)));
def1.operands.push(MachineOperand::Imm(1));
b0.instructions.push(def1);
b0.instructions.push(make_jmp_instr(1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
let mut def2 = MachineInstr::new(X86Opcode::MOV as u32);
def2.flags.is_move_reg = true;
def2.operands.push(MachineOperand::Reg(MCRegister(0))); def2.operands.push(MachineOperand::Imm(2));
b1.instructions.push(def2);
b1.instructions.push(make_ret_instr());
b1.predecessors = vec![0];
mf.add_block(b1);
mf.entry_block = 0;
let mut verifier = X86MachineVerifier::new();
verifier.verify(&mf);
let has_ssa_error = verifier.errors.iter().any(|e| e.contains("SSA"));
assert!(has_ssa_error);
}
#[test]
fn test_trace_metrics_with_backward_deps() {
let mut tm = X86MachineTraceMetrics::new();
let mut i0 = make_add_instr(0, 1); i0.operands.clear();
i0.operands.push(MachineOperand::Reg(MCRegister(0)));
i0.operands.push(MachineOperand::Reg(MCRegister(1)));
let mut i1 = make_add_instr(3, 0); i1.operands.clear();
i1.operands.push(MachineOperand::Reg(MCRegister(3)));
i1.operands.push(MachineOperand::Reg(MCRegister(0)));
let mut i2 = make_add_instr(1, 3); i2.operands.clear();
i2.operands.push(MachineOperand::Reg(MCRegister(1)));
i2.operands.push(MachineOperand::Reg(MCRegister(3)));
let cycles = tm.analyze_trace(&[i0, i1, i2], &HashSet::new());
assert_eq!(cycles, 3);
}
#[test]
fn test_bpi_with_long_chain() {
let mut mf = MachineFunction::new("long_chain");
for i in 0..20u32 {
let mut b = MachineBasicBlock::new(i, format!("block_{}", i));
if i == 0 {
b.is_entry = true;
}
if i < 19 {
b.instructions.push(make_jmp_instr(i + 1));
b.successors = vec![i + 1];
} else {
b.instructions.push(make_ret_instr());
}
if i > 0 {
b.predecessors = vec![i - 1];
}
mf.add_block(b);
}
mf.entry_block = 0;
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
for i in 0..20u32 {
assert!(bpi.get_block_count(i) > 0, "Block {} should have count", i);
}
}
#[test]
fn test_combiner_mov_fold_into_and() {
let mut mf = MachineFunction::new("mov_and_fold");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut mov = MachineInstr::new(X86Opcode::MOV as u32);
mov.operands.push(MachineOperand::Reg(MCRegister(0)));
mov.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
b0.instructions.push(mov);
let mut and_instr = MachineInstr::new(X86Opcode::AND as u32);
and_instr.operands.push(MachineOperand::Reg(MCRegister(0)));
and_instr.operands.push(MachineOperand::Imm(0xFF));
b0.instructions.push(and_instr);
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut combiner = X86MachineCombiner::new();
combiner.run(&mut mf);
assert!(combiner.combined >= 1);
}
#[test]
fn test_sinking_with_complex_cfg() {
let mut mf = MachineFunction::new("complex_sink");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.instructions.push(make_cmp_instr(0, 10));
b0.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_add_instr(0, 1));
b1.instructions.push(make_jmp_instr(3));
b1.predecessors = vec![0];
b1.successors = vec![3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_mov_instr(0, 5));
b2.instructions.push(make_jmp_instr(3));
b2.predecessors = vec![0];
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "merge");
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1, 2];
mf.add_block(b3);
mf.entry_block = 0;
let mut sinking = X86MachineSinking::new();
sinking.run(&mut mf);
}
#[test]
fn test_outliner_scan_with_non_overlapping_candidates() {
let mut mf = MachineFunction::new("outline_nonoverlap");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_mov_instr(2, 0));
b0.instructions.push(make_add_instr(3, 4));
b0.instructions.push(make_mov_instr(5, 3));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_add_instr(0, 1));
b1.instructions.push(make_mov_instr(2, 0));
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut outliner = X86MachineOutliner::new();
outliner.min_length = 2;
outliner.min_occurrences = 2;
outliner.scan_function(&mf);
}
#[test]
fn test_cse_cross_block_dominator_based() {
let mut mf = MachineFunction::new("cse_dom");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_add_instr(0, 1));
b0.instructions.push(make_cmp_instr(0, 0));
b0.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, 1));
b0.successors = vec![1, 2];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "t");
b1.instructions.push(make_add_instr(0, 1));
b1.instructions.push(make_jmp_instr(3));
b1.predecessors = vec![0];
b1.successors = vec![3];
mf.add_block(b1);
let mut b2 = MachineBasicBlock::new(2, "f");
b2.instructions.push(make_mov_instr(2, 3));
b2.instructions.push(make_jmp_instr(3));
b2.predecessors = vec![0];
b2.successors = vec![3];
mf.add_block(b2);
let mut b3 = MachineBasicBlock::new(3, "merge");
b3.instructions.push(make_ret_instr());
b3.predecessors = vec![1, 2];
mf.add_block(b3);
mf.entry_block = 0;
let mut cse = X86MachineCSE::new(true);
cse.run(&mut mf);
}
#[test]
fn test_two_address_pass_all_block_types() {
let mut mf = make_test_mf();
let mut pass = X86TwoAddressInstructionPass::new();
pass.run(&mut mf);
}
#[test]
fn test_copy_propagation_through_multiple_uses() {
let mut mf = MachineFunction::new("copy_multi");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1)); b0.instructions.push(make_add_instr(0, 2)); b0.instructions.push(make_mov_instr(3, 0)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut cp = X86MachineCopyPropagation::new();
cp.run(&mut mf);
}
#[test]
fn test_load_store_fold_into_multiple_ops() {
let mut mf = MachineFunction::new("ls_multi");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut mov = MachineInstr::new(X86Opcode::MOV as u32);
mov.operands.push(MachineOperand::Reg(MCRegister(0)));
mov.operands.push(MachineOperand::Mem {
base: MCRegister(5),
offset: 0,
size: 4,
});
b0.instructions.push(mov);
let mut or_instr = MachineInstr::new(X86Opcode::OR as u32);
or_instr.operands.push(MachineOperand::Reg(MCRegister(0)));
or_instr.operands.push(MachineOperand::Imm(1));
b0.instructions.push(or_instr);
b0.instructions.push(make_add_instr(0, 2));
b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut lso = X86LoadStoreOptimizer::new();
lso.run(&mut mf);
assert!(lso.loads_folded >= 1);
}
#[test]
fn test_loop_unroller_with_nested_loops() {
let mut mf = MachineFunction::new("unroll_nested");
for i in 0..6u32 {
let mut b = MachineBasicBlock::new(i, format!("b{}", i));
if i == 0 {
b.is_entry = true;
}
b.instructions.push(make_add_instr(i % 16, (i + 1) % 16));
if i < 5 {
b.instructions.push(make_jmp_instr(i + 1));
b.successors = vec![i + 1];
} else {
b.instructions.push(make_ret_instr());
b.is_exit = true;
}
if i > 0 {
b.predecessors = vec![i - 1];
}
mf.add_block(b);
}
mf.entry_block = 0;
mf.exit_blocks = vec![5];
let mut unroller = X86MachineLoopUnroller::new();
unroller.run(&mut mf);
}
#[test]
fn test_sinking_does_not_crash_on_edge_cases() {
let mut mf1 = MachineFunction::new("empty");
let mut sink1 = X86MachineSinking::new();
sink1.run(&mut mf1);
let mut mf2 = MachineFunction::new("single");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_ret_instr());
mf2.add_block(b0);
mf2.entry_block = 0;
let mut sink2 = X86MachineSinking::new();
sink2.run(&mut mf2);
let mut mf3 = MachineFunction::new("call_only");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
let mut call = MachineInstr::new(X86Opcode::CALL as u32);
call.flags.is_call = true;
call.flags.has_side_effects = true;
b0.instructions.push(call);
b0.instructions.push(make_ret_instr());
mf3.add_block(b0);
mf3.entry_block = 0;
let mut sink3 = X86MachineSinking::new();
sink3.run(&mut mf3);
}
#[test]
fn test_all_default_passes_are_usable() {
let _ = X86BranchProbabilityInfo::default();
let _ = X86MachineBlockPlacement::default();
let _ = X86MachineCSE::default();
let _ = X86MachineLICM::default();
let _ = X86MachineSinking::default();
let _ = X86MachineCombiner::default();
let _ = X86PeepholeOptimizer::default();
let _ = X86BranchFolding::default();
let _ = X86MachineVerifier::default();
let _ = X86MachineTraceMetrics::default();
let _ = X86MachineOutliner::default();
let _ = X86CodeGenOpt2::default();
let _ = X86Opt2Stats::default();
let _ = X86RegisterPressureTracker::default();
let _ = X86MacroFusionPrep::default();
let _ = X86FlagsOptimizer::default();
let _ = X86ConstantHoisting::default();
let _ = X86AddressModeOptimizer::default();
let _ = X86MachineCFGSimplifier::default();
let _ = X86MachineLoopUnroller::default();
let _ = X86ConditionalMoveOptimizer::default();
let _ = X86LoadStoreOptimizer::default();
let _ = X86MachineCopyPropagation::default();
let _ = X86StackSlotColoring::default();
let _ = X86TwoAddressInstructionPass::default();
}
#[test]
fn test_pipeline_does_not_crash_on_non_terminated_block() {
let mut mf = MachineFunction::new("no_term");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 1));
b0.successors = vec![1];
mf.add_block(b0);
let mut b1 = MachineBasicBlock::new(1, "b1");
b1.instructions.push(make_ret_instr());
mf.add_block(b1);
mf.entry_block = 0;
let mut opt2 = X86CodeGenOpt2::new();
opt2.run(&mut mf);
}
#[test]
fn test_comprehensive_opt2_pipeline() {
let mut mf = MachineFunction::new("comprehensive");
let mut entry = MachineBasicBlock::new(0, "entry");
entry.is_entry = true;
entry.instructions.push(make_mov_instr(0, 0)); entry.instructions.push(make_mov_instr_imm(1, 1)); entry.instructions.push(make_mov_instr_imm(2, 100)); entry.instructions.push(make_jmp_instr(1));
entry.successors = vec![1];
mf.add_block(entry);
let mut preheader = MachineBasicBlock::new(1, "preheader");
preheader.instructions.push(make_mov_instr_imm(3, 0)); preheader.instructions.push(make_jmp_instr(2));
preheader.predecessors = vec![0];
preheader.successors = vec![2];
mf.add_block(preheader);
let mut header = MachineBasicBlock::new(2, "loop_header");
header.instructions.push(make_cmp_instr(0, 100)); header
.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 5));
header.predecessors = vec![1, 4];
header.successors = vec![3, 5];
mf.add_block(header);
let mut body_then = MachineBasicBlock::new(3, "body_then");
body_then.instructions.push(make_add_instr(3, 0)); body_then.instructions.push(make_add_instr(0, 1)); body_then.instructions.push(make_jmp_instr(4));
body_then.predecessors = vec![2];
body_then.successors = vec![4];
mf.add_block(body_then);
let mut body_else = MachineBasicBlock::new(4, "body_else");
body_else.instructions.push(make_add_instr(0, 1)); body_else.instructions.push(make_jmp_instr(2)); body_else.predecessors = vec![2, 3];
body_else.successors = vec![2];
mf.add_block(body_else);
let mut exit_block = MachineBasicBlock::new(5, "exit");
exit_block.is_exit = true;
exit_block.instructions.push(make_mov_instr(0, 0));
exit_block.instructions.push(make_cmp_instr(3, 0));
exit_block.instructions.push(make_ret_instr());
exit_block.predecessors = vec![2];
mf.add_block(exit_block);
mf.entry_block = 0;
mf.exit_blocks = vec![5];
let mut opt2 = X86CodeGenOpt2::new();
opt2.verify_after_each_pass = true;
opt2.max_iterations = 3;
let stats = opt2.run(&mut mf);
assert!(
stats.peephole_redundant_movs >= 1,
"Redundant MOV should be eliminated"
);
assert!(stats.peephole_cmp_to_test >= 1, "CMP 0 should become TEST");
assert!(
stats.licm_hoisted >= 1 || stats.combiner_combined >= 1,
"Should optimize"
);
assert_eq!(stats.verification_errors, 0, "No verification errors");
opt2.print_stats(&stats);
}
#[test]
fn test_real_world_pattern_loop_with_accumulator() {
let mut mf = MachineFunction::new("loop_accum");
let mut entry = MachineBasicBlock::new(0, "entry");
entry.is_entry = true;
entry.instructions.push(make_mov_instr(0, 0)); entry.instructions.push(make_mov_instr(1, 0)); entry.instructions.push(make_mov_instr_imm(2, 100)); entry.instructions.push(make_jmp_instr(1));
entry.successors = vec![1];
mf.add_block(entry);
let mut header = MachineBasicBlock::new(1, "header");
header.instructions.push(make_cmp_instr(0, 100));
header
.instructions
.push(make_jcc_instr(X86Opcode::JGE as u32, 3));
header.predecessors = vec![0, 2];
header.successors = vec![2, 3];
mf.add_block(header);
let mut body = MachineBasicBlock::new(2, "body");
body.instructions.push(make_mov_instr_imm(3, 42));
body.instructions.push(make_add_instr(1, 3)); body.instructions.push(make_add_instr(0, 1));
let mut inc = MachineInstr::new(X86Opcode::INC as u32);
inc.operands.push(MachineOperand::Reg(MCRegister(0)));
body.instructions.push(inc);
body.instructions.push(make_jmp_instr(1)); body.predecessors = vec![1];
body.successors = vec![1];
mf.add_block(body);
let mut exit_block = MachineBasicBlock::new(3, "exit");
exit_block.is_exit = true;
exit_block.instructions.push(make_mov_instr(0, 1)); exit_block.instructions.push(make_ret_instr());
exit_block.predecessors = vec![1];
mf.add_block(exit_block);
mf.entry_block = 0;
mf.exit_blocks = vec![3];
let mut opt2 = X86CodeGenOpt2::new();
opt2.max_iterations = 2;
let stats = opt2.run(&mut mf);
assert!(stats.combiner_combined >= 1 || stats.cse_eliminated >= 1);
assert_eq!(stats.verification_errors, 0);
}
#[test]
fn test_x86_peephole_idempotent() {
let mut mf = MachineFunction::new("peep_idem");
let mut b0 = MachineBasicBlock::new(0, "entry");
b0.is_entry = true;
b0.instructions.push(make_mov_instr(0, 0)); b0.instructions.push(make_cmp_instr(0, 0)); b0.instructions.push(make_mov_instr(0, 0)); b0.instructions.push(make_ret_instr());
mf.add_block(b0);
mf.entry_block = 0;
let mut peep = X86PeepholeOptimizer::new();
peep.run(&mut mf);
let stats_after_first = (peep.redundant_movs_eliminated, peep.cmp_zero_to_test);
peep.run(&mut mf);
assert_eq!(peep.redundant_movs_eliminated, stats_after_first.0);
assert_eq!(peep.cmp_zero_to_test, stats_after_first.1);
}
#[test]
fn test_bpi_convergence_on_large_cfg() {
let mut mf = MachineFunction::new("bpi_large");
for i in 0..30u32 {
let mut b = MachineBasicBlock::new(i, format!("b{}", i));
if i == 0 {
b.is_entry = true;
}
if i % 3 == 0 && i < 28 {
b.successors = vec![i + 1, i + 2];
b.instructions
.push(make_jcc_instr(X86Opcode::JE as u32, i + 1));
} else if i < 29 {
b.successors = vec![i + 1];
b.instructions.push(make_jmp_instr(i + 1));
} else {
b.instructions.push(make_ret_instr());
b.is_exit = true;
}
if i > 0 && i < 29 {
b.predecessors = if i % 3 == 0 {
vec![i - 1]
} else {
vec![i - 1, i - 2]
};
}
mf.add_block(b);
}
mf.entry_block = 0;
mf.exit_blocks = vec![29];
let mut bpi = X86BranchProbabilityInfo::new();
bpi.compute(&mf);
for i in 0..30u32 {
assert!(bpi.get_block_count(i) > 0 || i >= 29);
}
}
}