use std::collections::{HashMap, HashSet};
use crate::codegen::ir::{LocalId, MirFunction};
use super::cfg::{block_id_index, compute_dominators, reachable_blocks, terminator_successors};
use super::liveness::{self, buffer_live_in, buffer_live_out};
pub(crate) fn multi_block_freeable(
func: &MirFunction,
candidates: &[(LocalId, usize)],
fn_exit: &HashSet<LocalId>,
block_scoped: &HashSet<LocalId>,
) -> HashMap<u32, Vec<LocalId>> {
let mut map: HashMap<u32, Vec<LocalId>> = HashMap::new();
let blocks = match &func.blocks {
Some(b) if !b.is_empty() => b.as_slice(),
_ => return map,
};
let n = blocks.len();
let id_to_index = block_id_index(blocks);
let entry = id_to_index.get(&0).copied().unwrap_or(0);
let reachable = reachable_blocks(blocks);
let dom = compute_dominators(blocks);
let live = liveness::compute(func);
let mut preds: Vec<Vec<usize>> = vec![Vec::new(); n];
for (i, b) in blocks.iter().enumerate() {
if !reachable[i] {
continue;
}
for s in terminator_successors(&b.terminator, &id_to_index) {
if s < n {
preds[s].push(i);
}
}
}
for &(owner, def_bi) in candidates {
if fn_exit.contains(&owner) || block_scoped.contains(&owner) {
continue; }
let buf_in = buffer_live_in(func, &live, owner);
let buf_out = buffer_live_out(func, &live, owner);
let terminal: Vec<bool> = (0..n).map(|b| buf_in[b] && !buf_out[b]).collect();
let clean: Vec<bool> = (0..n).map(|b| !buf_in[b] && !buf_out[b]).collect();
fn clean_chain_ok(
b: usize,
preds: &[Vec<usize>],
terminal: &[bool],
clean: &[bool],
def_bi: usize,
dom: &[HashSet<usize>],
visited: &mut HashSet<usize>,
) -> bool {
if !visited.insert(b) {
return true; }
if b == def_bi {
return false;
}
if preds[b].is_empty() {
return false; }
for &p in &preds[b] {
if terminal[p] {
continue; }
if clean[p] && dom[b].contains(&def_bi) {
if !clean_chain_ok(p, preds, terminal, clean, def_bi, dom, visited) {
return false;
}
continue;
}
return false; }
true
}
let mut death_blocks: Vec<usize> = Vec::new();
for s in 0..n {
if !reachable[s] || s == entry || buf_in[s] || preds[s].is_empty() {
continue;
}
if !dom[s].contains(&def_bi) {
continue; }
if preds[s].iter().any(|&p| dom[p].contains(&s)) {
continue;
}
if !preds[s].iter().any(|&p| terminal[p]) {
continue; }
let mut visited = HashSet::new();
let ok = preds[s].iter().all(|&p| {
terminal[p]
|| (clean[p]
&& clean_chain_ok(p, &preds, &terminal, &clean, def_bi, &dom, &mut visited))
});
if !ok {
continue; }
death_blocks.push(s);
}
if death_blocks.len() != 1 {
continue; }
map.entry(blocks[death_blocks[0]].id.0)
.or_default()
.push(owner);
}
for v in map.values_mut() {
v.sort_by_key(|id| id.0);
}
map
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::ir::{
BlockId, LocalId, MirBlock, MirFnSig, MirFunction, MirLocal, MirRValue, MirStmt,
MirTerminator, MirType, MirValue,
};
use std::collections::HashSet;
use std::sync::Arc;
fn bs(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::Struct(Arc::from("BuildString")),
is_mut: false,
is_param: false,
annotations: Vec::new(),
}
}
fn i64_local(id: u32, name: &str) -> MirLocal {
MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::i64(),
is_mut: false,
is_param: false,
annotations: Vec::new(),
}
}
fn multi_block_owner_func() -> MirFunction {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(bs(0, "_0"));
func.locals.push(i64_local(1, "_1"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("build_string_concat")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b1.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("printf")),
args: vec![MirValue::Local(LocalId(1))],
dest: None,
target: Some(BlockId(2)),
unwind: None,
});
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2]);
func
}
#[test]
fn frees_multi_block_owner_at_death_block_start() {
let func = multi_block_owner_func();
let candidates = vec![(LocalId(0), 0usize)];
let map = multi_block_freeable(&func, &candidates, &HashSet::new(), &HashSet::new());
assert_eq!(
map.get(&2).map(|v| v.as_slice()),
Some(&[LocalId(0)][..]),
"owner must be freed at the start of bb2 (the buffer's death block): {map:?}"
);
}
#[test]
fn skips_owner_already_claimed_by_fn_exit() {
let func = multi_block_owner_func();
let candidates = vec![(LocalId(0), 0usize)];
let mut fn_exit = HashSet::new();
fn_exit.insert(LocalId(0));
let map = multi_block_freeable(&func, &candidates, &fn_exit, &HashSet::new());
assert!(
map.is_empty(),
"disjointness: fn_exit owner must not be re-freed"
);
}
#[test]
fn skips_owner_already_claimed_by_block_scoped() {
let func = multi_block_owner_func();
let candidates = vec![(LocalId(0), 0usize)];
let mut bscoped = HashSet::new();
bscoped.insert(LocalId(0));
let map = multi_block_freeable(&func, &candidates, &HashSet::new(), &bscoped);
assert!(
map.is_empty(),
"disjointness: block-scoped owner must not be re-freed"
);
}
#[test]
fn declines_split_death_frontier() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(i64_local(9, "cond"));
func.locals.push(bs(0, "_0"));
func.locals.push(i64_local(1, "_1"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("build_string_concat")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(4)),
unwind: None,
});
let mut b0b = MirBlock::new(BlockId(4));
b0b.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(1),
else_block: BlockId(2),
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b1.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("printf")),
args: vec![MirValue::Local(LocalId(1))],
dest: None,
target: Some(BlockId(3)),
unwind: None,
});
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::Goto(BlockId(3)));
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b0b, b1, b2, b3]);
let candidates = vec![(LocalId(0), 0usize)];
let map = multi_block_freeable(&func, &candidates, &HashSet::new(), &HashSet::new());
assert!(
map.is_empty(),
"split death frontier needs a drop flag; must decline (leak, safe): {map:?}"
);
}
#[test]
fn declines_loop_header_death_block() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(bs(0, "_0"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(9, "cond"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("build_string_concat")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b1.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("printf")),
args: vec![MirValue::Local(LocalId(1))],
dest: None,
target: Some(BlockId(2)),
unwind: None,
});
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(3),
else_block: BlockId(4),
});
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Goto(BlockId(2)));
let mut b4 = MirBlock::new(BlockId(4));
b4.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2, b3, b4]);
let candidates = vec![(LocalId(0), 0usize)];
let map = multi_block_freeable(&func, &candidates, &HashSet::new(), &HashSet::new());
assert!(
map.get(&2).is_none(),
"bb2 is a loop header; freeing there double-frees per iteration — must decline: {map:?}"
);
assert!(
map.is_empty(),
"no valid free site for a buffer that dies before a loop header: {map:?}"
);
}
#[test]
fn declines_self_loop_death_block() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(bs(0, "_0"));
func.locals.push(i64_local(1, "_1"));
func.locals.push(i64_local(9, "cond"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("build_string_concat")),
args: Vec::new(),
dest: Some(LocalId(0)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b1 = MirBlock::new(BlockId(1));
b1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b1.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("printf")),
args: vec![MirValue::Local(LocalId(1))],
dest: None,
target: Some(BlockId(2)),
unwind: None,
});
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(2),
else_block: BlockId(3),
});
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2, b3]);
let candidates = vec![(LocalId(0), 0usize)];
let map = multi_block_freeable(&func, &candidates, &HashSet::new(), &HashSet::new());
assert!(
map.get(&2).is_none(),
"bb2 self-loops; freeing there double-frees per iteration — must decline: {map:?}"
);
}
}