use std::collections::BTreeMap;
use super::*;
use crate::decompiler::cfg::ssa::{
DominanceInfo, SsaBlock, SsaExpr, SsaForm, SsaStmt, SsaVariable,
};
use crate::decompiler::cfg::{BlockId, Cfg};
use crate::decompiler::ir::{BinOp, Literal};
fn v(base: &str, ver: usize) -> SsaVariable {
SsaVariable::new(base.to_string(), ver)
}
fn assign_str(target: SsaVariable, value: SsaExpr) -> SsaStmt {
SsaStmt::assign(target, value)
}
fn rebuild_test_form(
cfg: Cfg,
dominance: super::super::dominance::DominanceInfo,
blocks: BTreeMap<BlockId, SsaBlock>,
) -> SsaForm {
let mut ssa = SsaForm::new(cfg, dominance);
for (id, block) in blocks {
ssa.add_block(id, block);
}
let mut tmp = SsaForm {
cfg: ssa.cfg.clone(),
dominance: ssa.dominance.clone(),
blocks: ssa.blocks.clone(),
definitions: BTreeMap::new(),
uses: BTreeMap::new(),
};
rebuild_indexes(&mut tmp);
tmp
}
#[test]
fn does_not_propagate_constant_through_a_slot_variable() {
let mut block = SsaBlock::new();
block.add_stmt(assign_str(v("loc0", 0), SsaExpr::lit(Literal::Int(0))));
block.add_stmt(assign_str(
v("t", 0),
SsaExpr::binary(
BinOp::Lt,
SsaExpr::var(v("loc0", 0)),
SsaExpr::lit(Literal::Int(3)),
),
));
block.add_stmt(assign_str(
v("t", 1),
SsaExpr::call("use".to_string(), vec![SsaExpr::var(v("t", 0))]),
));
let mut blocks = BTreeMap::new();
blocks.insert(BlockId(0), block);
let mut ssa = rebuild_test_form(Cfg::new(), DominanceInfo::new(), blocks);
optimize(&mut ssa);
let b0 = ssa.block(BlockId(0)).unwrap();
let cmp_stmt = b0
.stmts
.iter()
.find(|s| matches!(s, SsaStmt::Assign { target, .. } if target == &v("t", 0)))
.expect("t_0 def should survive");
let SsaStmt::Assign { value, .. } = cmp_stmt else {
panic!();
};
let SsaExpr::Binary { left, .. } = value else {
panic!("expected the comparison to survive, got {value:?}");
};
assert!(
matches!(left.as_ref(), SsaExpr::Variable(var) if var == &v("loc0", 0)),
"loc0_0 should stay symbolic in `loc0 < 3`, not be replaced by 0; got {value:?}"
);
}
#[test]
fn folds_constant_binary_and_propagates() {
let mut block = SsaBlock::new();
block.add_stmt(assign_str(v("b0", 0), SsaExpr::lit(Literal::Int(1))));
block.add_stmt(assign_str(v("b0", 1), SsaExpr::lit(Literal::Int(2))));
block.add_stmt(assign_str(
v("b0", 2),
SsaExpr::binary(
BinOp::Add,
SsaExpr::var(v("b0", 0)),
SsaExpr::var(v("b0", 1)),
),
));
block.add_stmt(assign_str(
v("b0", 3),
SsaExpr::call("use".to_string(), vec![SsaExpr::var(v("b0", 2))]),
));
let mut blocks = BTreeMap::new();
blocks.insert(BlockId(0), block);
let mut ssa = rebuild_test_form(Cfg::new(), DominanceInfo::new(), blocks);
let rounds = optimize(&mut ssa);
assert!(rounds >= 1, "expected at least one optimization round");
let b0 = ssa.block(BlockId(0)).unwrap();
let use_stmt = b0.stmts.last().unwrap();
let SsaStmt::Assign { value, .. } = use_stmt else {
panic!();
};
let SsaExpr::Call { args, .. } = value else {
panic!("expected the use call, got {value:?}");
};
assert!(
matches!(args[0], SsaExpr::Literal(Literal::Int(3))),
"constant (1+2) should propagate as 3 into the use, got {:?}",
args[0]
);
}
#[test]
fn propagates_copy_chains() {
let mut block = SsaBlock::new();
block.add_stmt(assign_str(v("b0", 0), SsaExpr::lit(Literal::Int(7))));
block.add_stmt(assign_str(v("b0", 1), SsaExpr::var(v("b0", 0))));
block.add_stmt(assign_str(
v("b0", 2),
SsaExpr::call("use".to_string(), vec![SsaExpr::var(v("b0", 1))]),
));
let mut blocks = BTreeMap::new();
blocks.insert(BlockId(0), block);
let mut ssa = rebuild_test_form(Cfg::new(), DominanceInfo::new(), blocks);
optimize(&mut ssa);
let b0 = ssa.block(BlockId(0)).unwrap();
let SsaStmt::Assign { value, .. } = b0.stmts.last().unwrap() else {
panic!();
};
let SsaExpr::Call { args, .. } = value else {
panic!();
};
assert!(
matches!(args[0], SsaExpr::Literal(Literal::Int(7))),
"copy chain should resolve to 7, got {:?}",
args[0]
);
}
#[test]
fn eliminates_trivial_phi() {
use crate::decompiler::cfg::ssa::PhiNode;
let mut block = SsaBlock::new();
let mut phi = PhiNode::new(v("p0", 0));
phi.add_operand(BlockId(1), v("b1", 0));
block.add_phi(phi);
let mut pred = SsaBlock::new();
pred.add_stmt(assign_str(v("b1", 0), SsaExpr::lit(Literal::Int(5))));
block.add_stmt(assign_str(
v("b0", 0),
SsaExpr::call("use".to_string(), vec![SsaExpr::var(v("p0", 0))]),
));
let mut blocks = BTreeMap::new();
blocks.insert(BlockId(0), block);
blocks.insert(BlockId(1), pred);
let mut ssa = rebuild_test_form(Cfg::new(), DominanceInfo::new(), blocks);
optimize(&mut ssa);
let b0 = ssa.block(BlockId(0)).unwrap();
let SsaStmt::Assign { value, .. } = b0.stmts.last().unwrap() else {
panic!();
};
let SsaExpr::Call { args, .. } = value else {
panic!();
};
assert!(
matches!(args[0], SsaExpr::Literal(Literal::Int(5))),
"trivial phi should resolve through to 5, got {:?}",
args[0]
);
}
#[test]
fn eliminates_dead_constant_def() {
let mut block = SsaBlock::new();
block.add_stmt(assign_str(v("b0", 0), SsaExpr::lit(Literal::Int(7))));
block.add_stmt(assign_str(
v("b0", 1),
SsaExpr::call("use".to_string(), vec![SsaExpr::lit(Literal::Int(1))]),
));
let mut blocks = BTreeMap::new();
blocks.insert(BlockId(0), block);
let mut ssa = rebuild_test_form(Cfg::new(), DominanceInfo::new(), blocks);
let before = ssa.block(BlockId(0)).unwrap().stmt_count();
optimize(&mut ssa);
let after = ssa.block(BlockId(0)).unwrap().stmt_count();
assert!(after < before, "dead constant def b0#0 should be removed");
assert!(!ssa.definitions.contains_key(&v("b0", 0)));
}