use std::collections::HashSet;
use crate::codegen::ir::{LocalId, MirFunction, MirRValue, MirStmtKind, MirTerminator, MirValue};
use super::cfg::{
block_id_index, move_source_chain, stmt_uses_local, terminator_successors,
terminator_uses_local,
};
pub(crate) struct Liveness {
pub live_in: Vec<HashSet<LocalId>>,
pub live_out: Vec<HashSet<LocalId>>,
}
pub(crate) fn compute(func: &MirFunction) -> Liveness {
let blocks = match &func.blocks {
Some(b) => b.as_slice(),
None => {
return Liveness {
live_in: Vec::new(),
live_out: Vec::new(),
}
}
};
let n = blocks.len();
let id_to_index = block_id_index(blocks);
let all_locals: Vec<LocalId> = func.locals.iter().map(|l| l.id).collect();
let mut live_in: Vec<HashSet<LocalId>> = vec![HashSet::new(); n];
let mut live_out: Vec<HashSet<LocalId>> = vec![HashSet::new(); n];
let mut changed = true;
while changed {
changed = false;
for i in (0..n).rev() {
let mut new_out: HashSet<LocalId> = HashSet::new();
for s in terminator_successors(&blocks[i].terminator, &id_to_index) {
if let Some(sin) = live_in.get(s) {
for l in sin {
new_out.insert(*l);
}
}
}
let mut live = new_out.clone();
if let Some(MirTerminator::Call { dest: Some(d), .. }) = &blocks[i].terminator {
live.remove(d);
}
for x in &all_locals {
if terminator_uses_local(&blocks[i].terminator, *x) {
live.insert(*x);
}
}
for stmt in blocks[i].stmts.iter().rev() {
if let MirStmtKind::Assign { dest, .. } = &stmt.kind {
live.remove(dest);
}
for x in &all_locals {
if stmt_uses_local(&stmt.kind, *x) {
live.insert(*x);
}
}
}
if new_out != live_out[i] {
live_out[i] = new_out;
changed = true;
}
if live != live_in[i] {
live_in[i] = live;
changed = true;
}
}
}
Liveness { live_in, live_out }
}
fn buffer_aliases(func: &MirFunction, owner: LocalId) -> Vec<LocalId> {
let blocks = func.blocks.as_deref().unwrap_or(&[]);
let mut aliases = vec![owner];
aliases.extend(move_source_chain(owner, blocks));
let mut borrows = Vec::new();
for block in blocks {
for stmt in &block.stmts {
if let MirStmtKind::Assign {
dest,
value:
MirRValue::FieldAccess {
base: MirValue::Local(b),
..
},
} = &stmt.kind
{
if aliases.contains(b) {
borrows.push(*dest);
}
}
}
}
aliases.extend(borrows);
aliases
}
fn buffer_live(sets: &[HashSet<LocalId>], aliases: &[LocalId]) -> Vec<bool> {
sets.iter()
.map(|s| aliases.iter().any(|a| s.contains(a)))
.collect()
}
pub(crate) fn buffer_live_in(func: &MirFunction, live: &Liveness, owner: LocalId) -> Vec<bool> {
buffer_live(&live.live_in, &buffer_aliases(func, owner))
}
pub(crate) fn buffer_live_out(func: &MirFunction, live: &Liveness, owner: LocalId) -> Vec<bool> {
buffer_live(&live.live_out, &buffer_aliases(func, owner))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::codegen::ir::{
BlockId, LocalId, MirBlock, MirFnSig, MirFunction, MirRValue, MirStmt, MirTerminator,
MirType, MirValue,
};
use std::sync::Arc;
fn i64_local(id: u32, name: &str) -> crate::codegen::ir::MirLocal {
crate::codegen::ir::MirLocal {
id: LocalId(id),
name: Some(Arc::from(name)),
ty: MirType::i64(),
is_mut: false,
is_param: false,
annotations: Vec::new(),
}
}
#[test]
fn straight_line_live_ranges() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(i64_local(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("f")),
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::Use(MirValue::Local(LocalId(0))),
));
b1.terminator = Some(MirTerminator::Return(Some(MirValue::Local(LocalId(1)))));
func.blocks = Some(vec![b0, b1]);
let live = compute(&func);
assert!(live.live_out[0].contains(&LocalId(0)));
assert!(live.live_in[1].contains(&LocalId(0)));
assert!(!live.live_out[1].contains(&LocalId(0)));
assert!(live.live_out[1].is_empty());
assert!(!live.live_in[1].contains(&LocalId(1)));
}
#[test]
fn loop_body_local_dead_across_back_edge() {
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(i64_local(0, "cond"));
func.locals.push(i64_local(2, "_2"));
func.locals.push(i64_local(3, "_3"));
let mut b0 = MirBlock::new(BlockId(0));
b0.terminator = Some(MirTerminator::Goto(BlockId(1)));
let mut b1 = MirBlock::new(BlockId(1));
b1.terminator = Some(MirTerminator::If {
cond: MirValue::Local(LocalId(0)),
then_block: BlockId(2),
else_block: BlockId(3),
});
let mut b2 = MirBlock::new(BlockId(2));
b2.terminator = Some(MirTerminator::Call {
func: MirValue::Function(Arc::from("g")),
args: vec![MirValue::Local(LocalId(3))], dest: Some(LocalId(2)),
target: Some(BlockId(1)),
unwind: None,
});
let mut b3 = MirBlock::new(BlockId(3));
b3.terminator = Some(MirTerminator::Return(None));
func.blocks = Some(vec![b0, b1, b2, b3]);
let live = compute(&func);
assert!(!live.live_out[2].contains(&LocalId(2)));
assert!(!live.live_in[1].contains(&LocalId(2)));
}
#[test]
fn buffer_stays_live_through_ptr_borrow() {
use crate::codegen::ir::MirLocal;
let mut func = MirFunction::new("f", MirFnSig::new(vec![], MirType::Void));
func.locals.push(MirLocal {
id: LocalId(0),
name: Some(Arc::from("_0")),
ty: MirType::Struct(Arc::from("BuildString")),
is_mut: false,
is_param: false,
annotations: Vec::new(),
});
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]);
let live = compute(&func);
let bin = buffer_live_in(&func, &live, LocalId(0));
let bout = buffer_live_out(&func, &live, LocalId(0));
assert!(bout[0], "buffer live out of bb0");
assert!(bin[1], "buffer live into bb1 via _0 or its .ptr borrow");
assert!(
!bin[2],
"buffer dead at bb2 entry (borrow consumed by bb1 printf)"
);
}
}