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) struct FlagFrees {
pub owners: Vec<LocalId>,
pub block_frees: HashMap<u32, Vec<LocalId>>,
}
pub(crate) fn split_frontier_flag_frees(
func: &MirFunction,
candidates: &[(LocalId, usize)],
claimed: &HashSet<LocalId>,
) -> FlagFrees {
let mut owners: Vec<LocalId> = Vec::new();
let mut block_frees: HashMap<u32, Vec<LocalId>> = HashMap::new();
let blocks = match &func.blocks {
Some(b) if !b.is_empty() => b.as_slice(),
_ => {
return FlagFrees {
owners,
block_frees,
}
}
};
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 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 claimed.contains(&owner) {
continue; }
owners.push(owner);
let live = liveness::compute(func);
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();
for s in 0..n {
if !reachable[s] || s == entry || preds[s].is_empty() {
continue;
}
if buf_in[s] {
continue; }
if !preds[s].iter().any(|&p| terminal[p]) {
continue; }
if preds[s].iter().any(|&p| dom[p].contains(&s)) {
continue;
}
block_frees.entry(blocks[s].id.0).or_default().push(owner);
}
}
owners.sort_by_key(|id| id.0);
for v in block_frees.values_mut() {
v.sort_by_key(|id| id.0);
}
FlagFrees {
owners,
block_frees,
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::ir::{
BlockId, LocalId, MirBlock, MirFnSig, MirFunction, MirLocal, MirRValue, MirStmt,
MirTerminator, MirType, MirValue,
};
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 split_frontier_func() -> MirFunction {
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]);
func
}
#[test]
fn enrolls_split_frontier_and_places_join_site() {
let func = split_frontier_func();
let candidates = vec![(LocalId(0), 0usize)];
let claimed = HashSet::new();
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert_eq!(
frees.owners,
vec![LocalId(0)],
"the split-frontier owner must be enrolled: {:?}",
frees.owners
);
assert_eq!(
frees.block_frees.get(&3).map(|v| v.as_slice()),
Some(&[LocalId(0)][..]),
"exactly one guarded site at the join bb3: {:?}",
frees.block_frees
);
assert_eq!(
frees.block_frees.len(),
1,
"no site anywhere else: {:?}",
frees.block_frees
);
let extra = super::super::drops::multi_block_freeable(
&func,
&candidates,
&HashSet::new(),
&HashSet::new(),
);
assert!(
extra.is_empty(),
"increment 4 must still decline this split frontier: {extra:?}"
);
}
fn conditional_alloc_func() -> MirFunction {
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::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(1),
else_block: BlockId(2),
});
let mut b1 = MirBlock::new(BlockId(1));
b1.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 b1b = MirBlock::new(BlockId(4));
b1b.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b1b.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, b1, b1b, b2, b3]);
func
}
#[test]
fn conditional_alloc_enrolls_with_no_dominance() {
let func = conditional_alloc_func();
let candidates = vec![(LocalId(0), 1usize)];
let dom = compute_dominators(func.blocks.as_ref().unwrap());
let id_to_index = block_id_index(func.blocks.as_ref().unwrap());
let join_idx = id_to_index[&3];
let def_idx = 1usize;
assert!(
!dom[join_idx].contains(&def_idx),
"precondition: def block must NOT dominate the join, or this test proves nothing"
);
let claimed = HashSet::new();
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert_eq!(frees.owners, vec![LocalId(0)], "owner must be enrolled");
assert_eq!(
frees.block_frees.get(&3).map(|v| v.as_slice()),
Some(&[LocalId(0)][..]),
"site at the join despite non-dominating def: {:?}",
frees.block_frees
);
}
fn live_join_func() -> MirFunction {
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"));
func.locals.push(i64_local(2, "_2"));
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.stmts.push(MirStmt::assign(
LocalId(2),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
b3.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("printf")),
args: vec![MirValue::Local(LocalId(2))],
dest: None,
target: Some(BlockId(5)),
unwind: None,
});
let mut b5 = MirBlock::new(BlockId(5));
b5.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b0b, b1, b2, b3, b5]);
func
}
#[test]
fn uaf_shape_declines_live_join() {
let func = live_join_func();
let candidates = vec![(LocalId(0), 0usize)];
let claimed = HashSet::new();
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert!(
frees.owners.contains(&LocalId(0)),
"owner is still a candidate (claimed is empty): {:?}",
frees.owners
);
assert!(
!frees.block_frees.contains_key(&3),
"the join bb3 still USES the buffer (buf_in true): must not be a site: {:?}",
frees.block_frees
);
assert_eq!(
frees.block_frees.get(&5).map(|v| v.as_slice()),
Some(&[LocalId(0)][..]),
"the only site is past the join's own last use, at bb5: {:?}",
frees.block_frees
);
}
#[test]
fn declines_reentrant_site() {
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 claimed = HashSet::new();
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert!(
frees.owners.contains(&LocalId(0)),
"owner still enrolled: the Return backstop alone reclaims it: {:?}",
frees.owners
);
assert!(
frees.block_frees.is_empty(),
"the only candidate site (bb2, the loop header) is re-entrant: must decline: {:?}",
frees.block_frees
);
let mut func2 = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func2.locals.push(bs(0, "_0"));
func2.locals.push(i64_local(1, "_1"));
func2.locals.push(i64_local(9, "cond"));
let mut c0 = MirBlock::new(BlockId(0));
c0.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 c1 = MirBlock::new(BlockId(1));
c1.stmts.push(MirStmt::assign(
LocalId(1),
MirRValue::FieldAccess {
base: MirValue::Local(LocalId(0)),
field_name: Arc::from("ptr"),
field_ty: MirType::i64(),
},
));
c1.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 c2 = MirBlock::new(BlockId(2));
c2.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(9)),
then_block: BlockId(2),
else_block: BlockId(3),
});
let mut c3 = MirBlock::new(BlockId(3));
c3.terminator = Some(MirTerminator::Return(None));
func2.blocks = Some(vec![c0, c1, c2, c3]);
let frees2 = split_frontier_flag_frees(&func2, &candidates, &claimed);
assert!(
frees2.owners.contains(&LocalId(0)),
"self-loop shape: owner still enrolled: {:?}",
frees2.owners
);
assert!(
frees2.block_frees.is_empty(),
"self-loop shape: bb2 is re-entrant (dom[bb2] contains bb2 trivially): must decline: {:?}",
frees2.block_frees
);
}
#[test]
fn claimed_owner_not_enrolled() {
let func = split_frontier_func();
let candidates = vec![(LocalId(0), 0usize)];
let mut claimed = HashSet::new();
claimed.insert(LocalId(0));
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert!(
frees.owners.is_empty(),
"disjointness: a claimed owner must not be enrolled: {:?}",
frees.owners
);
assert!(
frees.block_frees.is_empty(),
"disjointness: a claimed owner gets no sites: {:?}",
frees.block_frees
);
}
#[test]
fn no_site_without_terminal_pred() {
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::Goto(BlockId(3)));
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Goto(BlockId(4)));
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 claimed = HashSet::new();
let frees = split_frontier_flag_frees(&func, &candidates, &claimed);
assert_eq!(
frees.block_frees.get(&2).map(|v| v.as_slice()),
Some(&[LocalId(0)][..]),
"bb2 is the one real death frontier (terminal pred bb1): {:?}",
frees.block_frees
);
assert!(
!frees.block_frees.contains_key(&3) && !frees.block_frees.contains_key(&4),
"clean blocks downstream of a non-terminal predecessor must not re-qualify: {:?}",
frees.block_frees
);
assert_eq!(
frees.block_frees.len(),
1,
"exactly one site total: {:?}",
frees.block_frees
);
}
}