use super::*;
use crate::middleend::mir::{AggregateKind, BasicBlock, CastKind, FieldIdx, LocalDecl, Mutability, Type};
fn create_test_function(name: &str, params: Vec<Local>, return_ty: Type) -> Function {
Function {
name: name.to_string(),
params,
return_ty,
locals: Vec::new(),
blocks: Vec::new(),
entry_block: BlockId(0),
}
}
fn create_local_decl(id: Local, ty: Type, name: Option<&str>) -> LocalDecl {
LocalDecl {
id,
ty,
mutable: false,
name: name.map(std::string::ToString::to_string),
}
}
fn create_basic_block(
id: BlockId,
statements: Vec<Statement>,
terminator: Terminator,
) -> BasicBlock {
BasicBlock {
id,
statements,
terminator,
}
}
#[test]
fn test_dce_new_creates_empty_sets() {
let dce = DeadCodeElimination::new();
assert_eq!(dce.live_locals.len(), 0, "live_locals should start empty");
assert_eq!(dce.live_blocks.len(), 0, "live_blocks should start empty");
}
#[test]
fn test_dce_preserves_entry_block() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(BlockId(0), vec![], Terminator::Return(None));
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.blocks.len(), 1, "Entry block should be preserved");
assert_eq!(func.blocks[0].id, BlockId(0));
}
#[test]
fn test_dce_preserves_function_parameters() {
let param0 = Local(0);
let param1 = Local(1);
let mut func = create_test_function("test", vec![param0, param1], Type::I32);
func.locals
.push(create_local_decl(param0, Type::I32, Some("x")));
func.locals
.push(create_local_decl(param1, Type::I32, Some("y")));
let entry_block = create_basic_block(
BlockId(0),
vec![],
Terminator::Return(Some(Operand::Copy(Place::Local(param0)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 2, "All parameters should be preserved");
}
#[test]
fn test_dce_removes_unused_local() {
let mut func = create_test_function("test", vec![], Type::Unit);
let unused_local = Local(0);
func.locals
.push(create_local_decl(unused_local, Type::I32, Some("unused")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(unused_local),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
)],
Terminator::Return(None),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 1, "DCE preserves locals conservatively");
assert_eq!(
func.blocks[0].statements.len(),
1,
"DCE preserves statements conservatively"
);
}
#[test]
fn test_dce_preserves_used_local() {
let mut func = create_test_function("test", vec![], Type::I32);
let local = Local(0);
func.locals
.push(create_local_decl(local, Type::I32, Some("used")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(local),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
)],
Terminator::Return(Some(Operand::Copy(Place::Local(local)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 1, "Used local should be preserved");
assert_eq!(
func.blocks[0].statements.len(),
1,
"Assignment to used local should be preserved"
);
}
#[test]
fn test_dce_removes_unreachable_block() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(BlockId(0), vec![], Terminator::Return(None));
let unreachable_block = create_basic_block(BlockId(1), vec![], Terminator::Return(None));
func.blocks.push(entry_block);
func.blocks.push(unreachable_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.blocks.len(), 1, "Unreachable block should be removed");
assert_eq!(func.blocks[0].id, BlockId(0), "Entry block should remain");
}
#[test]
fn test_dce_preserves_reachable_blocks() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(BlockId(0), vec![], Terminator::Goto(BlockId(1)));
let reachable_block = create_basic_block(BlockId(1), vec![], Terminator::Return(None));
func.blocks.push(entry_block);
func.blocks.push(reachable_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
2,
"Both reachable blocks should be preserved"
);
}
#[test]
fn test_dce_handles_empty_function() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(BlockId(0), vec![], Terminator::Return(None));
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
1,
"Empty function should have entry block"
);
assert_eq!(func.locals.len(), 0, "Empty function should have no locals");
}
#[test]
fn test_dce_removes_nop_statements() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Nop, Statement::Nop, Statement::Nop],
Terminator::Return(None),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks[0].statements.len(),
0,
"All Nop statements should be removed"
);
}
#[test]
fn test_dce_handles_if_terminator() {
let mut func = create_test_function("test", vec![], Type::I32);
let condition_local = Local(0);
func.locals
.push(create_local_decl(condition_local, Type::Bool, Some("cond")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(condition_local),
Rvalue::Use(Operand::Constant(Constant::Bool(true))),
)],
Terminator::If {
condition: Operand::Copy(Place::Local(condition_local)),
then_block: BlockId(1),
else_block: BlockId(2),
},
);
let then_block = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(1, Type::I32)))),
);
let else_block = create_basic_block(
BlockId(2),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(2, Type::I32)))),
);
func.blocks.push(entry_block);
func.blocks.push(then_block);
func.blocks.push(else_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
3,
"All three blocks should be preserved (all reachable)"
);
assert_eq!(func.locals.len(), 1, "Condition local should be preserved");
}
#[test]
fn test_dce_is_place_live_handles_local() {
let mut dce = DeadCodeElimination::new();
let live_local = Local(0);
let dead_local = Local(1);
dce.live_locals.insert(live_local);
assert!(
dce.is_place_live(&Place::Local(live_local)),
"Live local should be detected"
);
assert!(
!dce.is_place_live(&Place::Local(dead_local)),
"Dead local should be detected"
);
}
#[test]
fn test_dce_is_place_live_handles_field() {
let mut dce = DeadCodeElimination::new();
let live_local = Local(0);
dce.live_locals.insert(live_local);
let field_place = Place::Field(Box::new(Place::Local(live_local)), FieldIdx(0));
assert!(
dce.is_place_live(&field_place),
"Field of live local should be live"
);
}
#[test]
fn test_dce_is_place_live_handles_deref() {
let mut dce = DeadCodeElimination::new();
let live_local = Local(0);
dce.live_locals.insert(live_local);
let deref_place = Place::Deref(Box::new(Place::Local(live_local)));
assert!(
dce.is_place_live(&deref_place),
"Deref of live local should be live"
);
}
#[test]
fn test_dce_is_place_live_handles_index() {
let mut dce = DeadCodeElimination::new();
let base_local = Local(0);
let index_local = Local(1);
dce.live_locals.insert(base_local);
dce.live_locals.insert(index_local);
let index_place = Place::Index(
Box::new(Place::Local(base_local)),
Box::new(Place::Local(index_local)),
);
assert!(
dce.is_place_live(&index_place),
"Index with both live should be live"
);
}
#[test]
fn test_const_prop_new_creates_empty_map() {
let const_prop = ConstantPropagation::new();
assert_eq!(
const_prop.constants.len(),
0,
"constants map should start empty"
);
}
#[test]
fn test_const_prop_propagates_integer_constant() {
let mut func = create_test_function("test", vec![], Type::I32);
let const_local = Local(0);
let result_local = Local(1);
func.locals
.push(create_local_decl(const_local, Type::I32, Some("const_val")));
func.locals
.push(create_local_decl(result_local, Type::I32, Some("result")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(const_local),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
),
Statement::Assign(
Place::Local(result_local),
Rvalue::Use(Operand::Copy(Place::Local(const_local))),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(result_local)))),
);
func.blocks.push(entry_block);
let mut const_prop = ConstantPropagation::new();
const_prop.run(&mut func);
if let Statement::Assign(_, rvalue) = &func.blocks[0].statements[1] {
if let Rvalue::Use(Operand::Constant(Constant::Int(val, _))) = rvalue {
assert_eq!(*val, 42, "Constant should be propagated");
} else {
panic!("Expected constant operand after propagation");
}
} else {
panic!("Expected Assign statement");
}
}
#[test]
fn test_const_prop_folds_binary_add() {
let mut func = create_test_function("test", vec![], Type::I32);
let const_a = Local(0);
let const_b = Local(1);
let sum_local = Local(2);
func.locals
.push(create_local_decl(const_a, Type::I32, None));
func.locals
.push(create_local_decl(const_b, Type::I32, None));
func.locals
.push(create_local_decl(sum_local, Type::I32, None));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(const_a),
Rvalue::Use(Operand::Constant(Constant::Int(2, Type::I32))),
),
Statement::Assign(
Place::Local(const_b),
Rvalue::Use(Operand::Constant(Constant::Int(3, Type::I32))),
),
Statement::Assign(
Place::Local(sum_local),
Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(const_a)),
Operand::Copy(Place::Local(const_b)),
),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(sum_local)))),
);
func.blocks.push(entry_block);
let mut const_prop = ConstantPropagation::new();
const_prop.run(&mut func);
if let Statement::Assign(_, rvalue) = &func.blocks[0].statements[2] {
if let Rvalue::BinaryOp(_, left, right) = rvalue {
assert!(
matches!(left, Operand::Constant(_)),
"Left operand should be constant"
);
assert!(
matches!(right, Operand::Constant(_)),
"Right operand should be constant"
);
}
}
}
#[test]
fn test_const_prop_folds_binary_sub() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Sub,
&Operand::Constant(Constant::Int(5, Type::I32)),
&Operand::Constant(Constant::Int(2, Type::I32)),
);
assert!(result.is_some(), "Sub should be evaluated");
if let Some(Constant::Int(val, _)) = result {
assert_eq!(val, 3, "5 - 2 should equal 3");
}
}
#[test]
fn test_const_prop_folds_binary_mul() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Mul,
&Operand::Constant(Constant::Int(3, Type::I32)),
&Operand::Constant(Constant::Int(4, Type::I32)),
);
assert!(result.is_some(), "Mul should be evaluated");
if let Some(Constant::Int(val, _)) = result {
assert_eq!(val, 12, "3 * 4 should equal 12");
}
}
#[test]
fn test_const_prop_folds_binary_eq() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Eq,
&Operand::Constant(Constant::Int(5, Type::I32)),
&Operand::Constant(Constant::Int(5, Type::I32)),
);
assert!(result.is_some(), "Eq should be evaluated");
if let Some(Constant::Bool(val)) = result {
assert!(val, "5 == 5 should be true");
}
}
#[test]
fn test_const_prop_folds_binary_lt() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Lt,
&Operand::Constant(Constant::Int(3, Type::I32)),
&Operand::Constant(Constant::Int(5, Type::I32)),
);
assert!(result.is_some(), "Lt should be evaluated");
if let Some(Constant::Bool(val)) = result {
assert!(val, "3 < 5 should be true");
}
}
#[test]
fn test_const_prop_folds_binary_and() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::And,
&Operand::Constant(Constant::Bool(true)),
&Operand::Constant(Constant::Bool(false)),
);
assert!(result.is_some(), "And should be evaluated");
if let Some(Constant::Bool(val)) = result {
assert!(!val, "true && false should be false");
}
}
#[test]
fn test_const_prop_folds_binary_or() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Or,
&Operand::Constant(Constant::Bool(true)),
&Operand::Constant(Constant::Bool(false)),
);
assert!(result.is_some(), "Or should be evaluated");
if let Some(Constant::Bool(val)) = result {
assert!(val, "true || false should be true");
}
}
#[test]
fn test_const_prop_folds_unary_neg() {
let const_prop = ConstantPropagation::new();
let result =
const_prop.eval_unary_op(UnOp::Neg, &Operand::Constant(Constant::Int(5, Type::I32)));
assert!(result.is_some(), "Neg should be evaluated");
if let Some(Constant::Int(val, _)) = result {
assert_eq!(val, -5, "-5 should equal -5");
}
}
#[test]
fn test_const_prop_folds_unary_not() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_unary_op(UnOp::Not, &Operand::Constant(Constant::Bool(true)));
assert!(result.is_some(), "Not should be evaluated");
if let Some(Constant::Bool(val)) = result {
assert!(!val, "!true should be false");
}
}
#[test]
fn test_const_prop_returns_none_for_non_constant() {
let const_prop = ConstantPropagation::new();
let result = const_prop.eval_binary_op(
BinOp::Add,
&Operand::Copy(Place::Local(Local(0))),
&Operand::Constant(Constant::Int(5, Type::I32)),
);
assert!(
result.is_none(),
"Should return None for non-constant operand"
);
}
#[test]
fn test_cse_new_creates_empty_map() {
let cse = CommonSubexpressionElimination::new();
assert_eq!(
cse.expressions.len(),
0,
"expressions map should start empty"
);
}
#[test]
fn test_cse_eliminates_duplicate_binary_op() {
let mut func = create_test_function("test", vec![], Type::I32);
let x = Local(0);
let y = Local(1);
let z = Local(2);
let w = Local(3);
func.locals.push(create_local_decl(x, Type::I32, Some("x")));
func.locals.push(create_local_decl(y, Type::I32, Some("y")));
func.locals.push(create_local_decl(z, Type::I32, Some("z")));
func.locals.push(create_local_decl(w, Type::I32, Some("w")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(x),
Rvalue::Use(Operand::Constant(Constant::Int(2, Type::I32))),
),
Statement::Assign(
Place::Local(y),
Rvalue::Use(Operand::Constant(Constant::Int(3, Type::I32))),
),
Statement::Assign(
Place::Local(z),
Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(x)),
Operand::Copy(Place::Local(y)),
),
),
Statement::Assign(
Place::Local(w),
Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(x)),
Operand::Copy(Place::Local(y)),
),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(w)))),
);
func.blocks.push(entry_block);
let mut cse = CommonSubexpressionElimination::new();
cse.run(&mut func);
if let Statement::Assign(_, rvalue) = &func.blocks[0].statements[3] {
match rvalue {
Rvalue::Use(Operand::Copy(Place::Local(local))) => {
assert_eq!(
*local, z,
"Duplicate expression should reuse previous result"
);
}
_ => panic!("Expected duplicate expression to be replaced with Copy"),
}
}
}
#[test]
fn test_cse_generates_same_key_for_identical_expressions() {
let cse = CommonSubexpressionElimination::new();
let expr1 = Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(Local(0))),
Operand::Copy(Place::Local(Local(1))),
);
let expr2 = Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(Local(0))),
Operand::Copy(Place::Local(Local(1))),
);
let key1 = cse.rvalue_key(&expr1);
let key2 = cse.rvalue_key(&expr2);
assert_eq!(key1, key2, "Identical expressions should generate same key");
}
#[test]
fn test_cse_generates_different_keys_for_different_expressions() {
let cse = CommonSubexpressionElimination::new();
let expr1 = Rvalue::BinaryOp(
BinOp::Add,
Operand::Copy(Place::Local(Local(0))),
Operand::Copy(Place::Local(Local(1))),
);
let expr2 = Rvalue::BinaryOp(
BinOp::Sub,
Operand::Copy(Place::Local(Local(0))),
Operand::Copy(Place::Local(Local(1))),
);
let key1 = cse.rvalue_key(&expr1);
let key2 = cse.rvalue_key(&expr2);
assert_ne!(
key1, key2,
"Different expressions should generate different keys"
);
}
#[test]
fn test_optimize_function_runs_all_passes() {
let mut func = create_test_function("test", vec![], Type::I32);
let const_local = Local(0);
let unused_local = Local(1);
let result_local = Local(2);
func.locals
.push(create_local_decl(const_local, Type::I32, None));
func.locals
.push(create_local_decl(unused_local, Type::I32, None));
func.locals
.push(create_local_decl(result_local, Type::I32, None));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(const_local),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
),
Statement::Assign(
Place::Local(unused_local),
Rvalue::Use(Operand::Constant(Constant::Int(99, Type::I32))),
),
Statement::Assign(
Place::Local(result_local),
Rvalue::Use(Operand::Copy(Place::Local(const_local))),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(result_local)))),
);
func.blocks.push(entry_block);
let original_stmt_count = func.blocks[0].statements.len();
optimize_function(&mut func);
assert!(
func.blocks[0].statements.len() <= original_stmt_count,
"Optimization should reduce or maintain statement count"
);
}
#[test]
fn test_optimize_function_handles_empty_function() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(BlockId(0), vec![], Terminator::Return(None));
func.blocks.push(entry_block);
optimize_function(&mut func);
assert_eq!(
func.blocks.len(),
1,
"Empty function should still have entry block"
);
}
#[test]
fn test_optimize_program_handles_multiple_functions() {
let mut program = Program {
functions: HashMap::new(),
entry: "main".to_string(),
};
let func1 = create_test_function("func1", vec![], Type::Unit);
let func2 = create_test_function("func2", vec![], Type::I32);
program.functions.insert("func1".to_string(), func1);
program.functions.insert("func2".to_string(), func2);
optimize_program(&mut program);
assert_eq!(
program.functions.len(),
2,
"All functions should be optimized"
);
}
#[test]
fn test_dce_handles_switch_terminator() {
let mut func = create_test_function("test", vec![], Type::I32);
let disc_local = Local(0);
func.locals
.push(create_local_decl(disc_local, Type::I32, Some("disc")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(disc_local),
Rvalue::Use(Operand::Constant(Constant::Int(1, Type::I32))),
)],
Terminator::Switch {
discriminant: Operand::Copy(Place::Local(disc_local)),
targets: vec![
(Constant::Int(0, Type::I32), BlockId(1)),
(Constant::Int(1, Type::I32), BlockId(2)),
],
default: Some(BlockId(3)),
},
);
let block1 = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(10, Type::I32)))),
);
let block2 = create_basic_block(
BlockId(2),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(20, Type::I32)))),
);
let block3 = create_basic_block(
BlockId(3),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(30, Type::I32)))),
);
func.blocks.push(entry_block);
func.blocks.push(block1);
func.blocks.push(block2);
func.blocks.push(block3);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
4,
"All switch target blocks should be preserved"
);
assert!(dce.live_locals.contains(&disc_local), "Discriminant local should be live");
}
#[test]
fn test_dce_handles_switch_without_default() {
let mut func = create_test_function("test", vec![], Type::I32);
let disc_local = Local(0);
func.locals
.push(create_local_decl(disc_local, Type::I32, Some("disc")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(disc_local),
Rvalue::Use(Operand::Constant(Constant::Int(0, Type::I32))),
)],
Terminator::Switch {
discriminant: Operand::Copy(Place::Local(disc_local)),
targets: vec![(Constant::Int(0, Type::I32), BlockId(1))],
default: None,
},
);
let target_block = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(42, Type::I32)))),
);
func.blocks.push(entry_block);
func.blocks.push(target_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
2,
"Switch target block should be reachable"
);
}
#[test]
fn test_dce_handles_call_terminator() {
let mut func = create_test_function("test", vec![], Type::I32);
let func_local = Local(0);
let arg_local = Local(1);
let dest_local = Local(2);
func.locals
.push(create_local_decl(func_local, Type::I32, Some("func")));
func.locals
.push(create_local_decl(arg_local, Type::I32, Some("arg")));
func.locals
.push(create_local_decl(dest_local, Type::I32, Some("dest")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(func_local),
Rvalue::Use(Operand::Constant(Constant::Int(0, Type::I32))),
),
Statement::Assign(
Place::Local(arg_local),
Rvalue::Use(Operand::Constant(Constant::Int(5, Type::I32))),
),
],
Terminator::Call {
func: Operand::Copy(Place::Local(func_local)),
args: vec![Operand::Copy(Place::Local(arg_local))],
destination: Some((Place::Local(dest_local), BlockId(1))),
},
);
let continuation = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(Some(Operand::Copy(Place::Local(dest_local)))),
);
func.blocks.push(entry_block);
func.blocks.push(continuation);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
2,
"Call continuation block should be reachable"
);
assert!(dce.live_locals.contains(&func_local), "Call func should be live");
assert!(dce.live_locals.contains(&arg_local), "Call arg should be live");
assert!(dce.live_locals.contains(&dest_local), "Call dest should be live");
}
#[test]
fn test_dce_handles_call_terminator_no_destination() {
let mut func = create_test_function("test", vec![], Type::Unit);
let func_local = Local(0);
func.locals
.push(create_local_decl(func_local, Type::I32, Some("func")));
let entry_block = create_basic_block(
BlockId(0),
vec![],
Terminator::Call {
func: Operand::Copy(Place::Local(func_local)),
args: vec![],
destination: None,
},
);
let unreachable_block = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(None),
);
func.blocks.push(entry_block);
func.blocks.push(unreachable_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
1,
"Block after Call with no destination is unreachable"
);
}
#[test]
fn test_dce_handles_unreachable_terminator() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(
BlockId(0),
vec![],
Terminator::Unreachable,
);
let dead_block = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(None),
);
func.blocks.push(entry_block);
func.blocks.push(dead_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(
func.blocks.len(),
1,
"Block after Unreachable is dead code"
);
assert_eq!(func.blocks[0].id, BlockId(0));
}
#[test]
fn test_dce_return_with_none_marks_no_operand() {
let mut func = create_test_function("test", vec![], Type::Unit);
let entry_block = create_basic_block(
BlockId(0),
vec![],
Terminator::Return(None),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert!(dce.live_locals.is_empty(), "Return(None) should not mark any local live");
}
#[test]
fn test_dce_switch_with_multiple_targets_to_same_block() {
let mut func = create_test_function("test", vec![], Type::I32);
let disc_local = Local(0);
func.locals
.push(create_local_decl(disc_local, Type::I32, Some("disc")));
let entry_block = create_basic_block(
BlockId(0),
vec![Statement::Assign(
Place::Local(disc_local),
Rvalue::Use(Operand::Constant(Constant::Int(0, Type::I32))),
)],
Terminator::Switch {
discriminant: Operand::Copy(Place::Local(disc_local)),
targets: vec![
(Constant::Int(0, Type::I32), BlockId(1)),
(Constant::Int(1, Type::I32), BlockId(1)), (Constant::Int(2, Type::I32), BlockId(1)), ],
default: Some(BlockId(1)),
},
);
let target_block = create_basic_block(
BlockId(1),
vec![],
Terminator::Return(Some(Operand::Constant(Constant::Int(99, Type::I32)))),
);
func.blocks.push(entry_block);
func.blocks.push(target_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.blocks.len(), 2, "Both blocks should be live");
}
#[test]
fn test_mark_rvalue_live_ref() {
let mut func = create_test_function("test", vec![], Type::Unit);
let local0 = Local(0);
let local1 = Local(1);
func.locals.push(create_local_decl(local0, Type::I32, Some("x")));
func.locals.push(create_local_decl(local1, Type::I32, Some("ref_x")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(local0),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
),
Statement::Assign(
Place::Local(local1),
Rvalue::Ref(Mutability::Immutable, Place::Local(local0)),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(local1)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 2, "Ref rvalue should mark referenced local live");
}
#[test]
fn test_mark_rvalue_live_ref_mutable() {
let mut func = create_test_function("test", vec![], Type::Unit);
let local0 = Local(0);
let local1 = Local(1);
func.locals.push(create_local_decl(local0, Type::I32, Some("x")));
func.locals.push(create_local_decl(local1, Type::I32, Some("mut_ref_x")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(local0),
Rvalue::Use(Operand::Constant(Constant::Int(10, Type::I32))),
),
Statement::Assign(
Place::Local(local1),
Rvalue::Ref(Mutability::Mutable, Place::Local(local0)),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(local1)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 2, "Mutable ref should mark referenced local live");
}
#[test]
fn test_mark_rvalue_live_aggregate() {
let mut func = create_test_function("test", vec![], Type::Unit);
let local0 = Local(0);
let local1 = Local(1);
let local2 = Local(2);
func.locals.push(create_local_decl(local0, Type::I32, Some("a")));
func.locals.push(create_local_decl(local1, Type::I32, Some("b")));
func.locals.push(create_local_decl(local2, Type::I32, Some("tuple")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(local0),
Rvalue::Use(Operand::Constant(Constant::Int(1, Type::I32))),
),
Statement::Assign(
Place::Local(local1),
Rvalue::Use(Operand::Constant(Constant::Int(2, Type::I32))),
),
Statement::Assign(
Place::Local(local2),
Rvalue::Aggregate(
AggregateKind::Tuple,
vec![
Operand::Copy(Place::Local(local0)),
Operand::Copy(Place::Local(local1)),
],
),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(local2)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 3, "Aggregate should mark all operand locals live");
}
#[test]
fn test_mark_rvalue_live_call() {
let mut func = create_test_function("test", vec![], Type::I32);
let func_local = Local(0);
let arg_local = Local(1);
let result_local = Local(2);
func.locals.push(create_local_decl(func_local, Type::I32, Some("f")));
func.locals.push(create_local_decl(arg_local, Type::I32, Some("arg")));
func.locals.push(create_local_decl(result_local, Type::I32, Some("result")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(arg_local),
Rvalue::Use(Operand::Constant(Constant::Int(5, Type::I32))),
),
Statement::Assign(
Place::Local(result_local),
Rvalue::Call(
Operand::Copy(Place::Local(func_local)),
vec![Operand::Copy(Place::Local(arg_local))],
),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(result_local)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 3, "Call should mark func and args live");
}
#[test]
fn test_mark_rvalue_live_cast() {
let mut func = create_test_function("test", vec![], Type::F64);
let int_local = Local(0);
let float_local = Local(1);
func.locals.push(create_local_decl(int_local, Type::I32, Some("n")));
func.locals.push(create_local_decl(float_local, Type::F64, Some("f")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(int_local),
Rvalue::Use(Operand::Constant(Constant::Int(42, Type::I32))),
),
Statement::Assign(
Place::Local(float_local),
Rvalue::Cast(CastKind::Numeric, Operand::Copy(Place::Local(int_local)), Type::F64),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(float_local)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 2, "Cast should mark the source operand live");
}
#[test]
fn test_mark_rvalue_live_unary_op() {
let mut func = create_test_function("test", vec![], Type::I32);
let local0 = Local(0);
let local1 = Local(1);
func.locals.push(create_local_decl(local0, Type::I32, Some("x")));
func.locals.push(create_local_decl(local1, Type::I32, Some("neg_x")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(local0),
Rvalue::Use(Operand::Constant(Constant::Int(10, Type::I32))),
),
Statement::Assign(
Place::Local(local1),
Rvalue::UnaryOp(UnOp::Neg, Operand::Copy(Place::Local(local0))),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(local1)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 2, "UnaryOp should mark operand live");
}
#[test]
fn test_mark_rvalue_live_aggregate_empty() {
let mut func = create_test_function("test", vec![], Type::Unit);
let result_local = Local(0);
func.locals.push(create_local_decl(result_local, Type::Unit, Some("empty_tuple")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(result_local),
Rvalue::Aggregate(AggregateKind::Tuple, vec![]),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(result_local)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 1, "Empty aggregate should still preserve result local");
}
#[test]
fn test_mark_rvalue_live_call_multiple_args() {
let mut func = create_test_function("test", vec![], Type::I32);
let arg0 = Local(0);
let arg1 = Local(1);
let arg2 = Local(2);
let result = Local(3);
func.locals.push(create_local_decl(arg0, Type::I32, Some("a")));
func.locals.push(create_local_decl(arg1, Type::I32, Some("b")));
func.locals.push(create_local_decl(arg2, Type::I32, Some("c")));
func.locals.push(create_local_decl(result, Type::I32, Some("r")));
let entry_block = create_basic_block(
BlockId(0),
vec![
Statement::Assign(
Place::Local(arg0),
Rvalue::Use(Operand::Constant(Constant::Int(1, Type::I32))),
),
Statement::Assign(
Place::Local(arg1),
Rvalue::Use(Operand::Constant(Constant::Int(2, Type::I32))),
),
Statement::Assign(
Place::Local(arg2),
Rvalue::Use(Operand::Constant(Constant::Int(3, Type::I32))),
),
Statement::Assign(
Place::Local(result),
Rvalue::Call(
Operand::Constant(Constant::Int(0, Type::I32)), vec![
Operand::Copy(Place::Local(arg0)),
Operand::Copy(Place::Local(arg1)),
Operand::Move(Place::Local(arg2)),
],
),
),
],
Terminator::Return(Some(Operand::Copy(Place::Local(result)))),
);
func.blocks.push(entry_block);
let mut dce = DeadCodeElimination::new();
dce.run(&mut func);
assert_eq!(func.locals.len(), 4, "Call with multiple args should mark all args live");
}