use std::collections::{HashMap, HashSet};
use crate::codegen::ir::{
BlockId, LocalId, MirBlock, MirPlace, MirRValue, MirStmtKind, MirTerminator, MirValue,
PlaceProjection,
};
pub(crate) fn callee_name(func: &MirValue) -> Option<&str> {
match func {
MirValue::Function(n) | MirValue::Global(n) => Some(n.as_ref()),
_ => None,
}
}
pub(crate) fn move_source_chain(id: LocalId, blocks: &[MirBlock]) -> Vec<LocalId> {
let mut chain = Vec::new();
let mut cur = id;
loop {
let mut next = None;
for block in blocks {
for stmt in &block.stmts {
if let MirStmtKind::Assign {
dest,
value: MirRValue::Use(MirValue::Local(src)),
} = &stmt.kind
{
if *dest == cur {
next = Some(*src);
}
}
}
}
match next {
Some(s) if !chain.contains(&s) && s != id => {
chain.push(s);
cur = s;
}
_ => break,
}
}
chain
}
pub(crate) fn stmt_uses_local(kind: &MirStmtKind, x: LocalId) -> bool {
match kind {
MirStmtKind::Assign { value, .. } => rvalue_mentions(value, x),
MirStmtKind::DerefAssign { ptr, value } => *ptr == x || rvalue_mentions(value, x),
MirStmtKind::FieldDerefAssign { ptr, value, .. } => *ptr == x || rvalue_mentions(value, x),
MirStmtKind::FieldAssign { base, value, .. } => *base == x || rvalue_mentions(value, x),
MirStmtKind::IndexStore {
base, index, value, ..
} => {
matches!(base, MirValue::Local(l) if *l == x)
|| matches!(index, MirValue::Local(l) if *l == x)
|| rvalue_mentions(value, x)
}
MirStmtKind::GlobalStore { value, .. } => rvalue_mentions(value, x),
MirStmtKind::StorageLive(_)
| MirStmtKind::StorageDead(_)
| MirStmtKind::Nop
| MirStmtKind::WorkgroupBarrier => false,
}
}
pub(crate) fn terminator_uses_local(term: &Option<MirTerminator>, x: LocalId) -> bool {
let is = |v: &MirValue| matches!(v, MirValue::Local(l) if *l == x);
match term {
Some(MirTerminator::If { cond, .. }) => is(cond),
Some(MirTerminator::Switch { value, .. }) => is(value),
Some(MirTerminator::Call { func, args, .. }) => is(func) || args.iter().any(is),
Some(MirTerminator::Return(Some(v))) => is(v),
Some(MirTerminator::Assert { cond, .. }) => is(cond),
Some(MirTerminator::Drop { place, .. }) => {
place.local == x
|| place
.projections
.iter()
.any(|p| matches!(p, PlaceProjection::Index(l) if *l == x))
}
_ => false,
}
}
pub(crate) fn reachable_blocks(blocks: &[MirBlock]) -> Vec<bool> {
let id_to_index = block_id_index(blocks);
let entry = id_to_index.get(&0).copied().unwrap_or(0);
let mut seen = vec![false; blocks.len()];
let mut stack = vec![entry];
while let Some(i) = stack.pop() {
if i >= blocks.len() || seen[i] {
continue;
}
seen[i] = true;
for s in terminator_successors(&blocks[i].terminator, &id_to_index) {
stack.push(s);
}
}
seen
}
pub(crate) fn block_id_index(blocks: &[MirBlock]) -> HashMap<u32, usize> {
blocks
.iter()
.enumerate()
.map(|(i, b)| (b.id.0, i))
.collect()
}
pub(crate) fn terminator_successors(
term: &Option<MirTerminator>,
id_to_index: &HashMap<u32, usize>,
) -> Vec<usize> {
let resolve = |b: &BlockId| id_to_index.get(&b.0).copied();
let mut out = Vec::new();
match term {
Some(MirTerminator::Goto(t)) => out.extend(resolve(t)),
Some(MirTerminator::If {
then_block,
else_block,
..
}) => {
out.extend(resolve(then_block));
out.extend(resolve(else_block));
}
Some(MirTerminator::Switch {
targets, default, ..
}) => {
for (_, t) in targets {
out.extend(resolve(t));
}
out.extend(resolve(default));
}
Some(MirTerminator::Call { target, unwind, .. }) => {
out.extend(target.as_ref().and_then(&resolve));
out.extend(unwind.as_ref().and_then(&resolve));
}
Some(MirTerminator::Drop { target, unwind, .. }) => {
out.extend(resolve(target));
out.extend(unwind.as_ref().and_then(&resolve));
}
Some(MirTerminator::Assert { target, unwind, .. }) => {
out.extend(resolve(target));
out.extend(unwind.as_ref().and_then(&resolve));
}
_ => {}
}
out
}
pub(crate) fn compute_dominators(blocks: &[MirBlock]) -> Vec<HashSet<usize>> {
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 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) {
preds[s].push(i);
}
}
let all: HashSet<usize> = (0..n).collect();
let mut dom: Vec<HashSet<usize>> = vec![all; n];
dom[entry] = std::iter::once(entry).collect();
let mut changed = true;
while changed {
changed = false;
for i in 0..n {
if i == entry || !reachable[i] {
continue;
}
let mut new_set: Option<HashSet<usize>> = None;
for &p in &preds[i] {
new_set = Some(match new_set {
None => dom[p].clone(),
Some(acc) => acc.intersection(&dom[p]).copied().collect(),
});
}
let mut new_set = new_set.unwrap_or_default();
new_set.insert(i);
if new_set != dom[i] {
dom[i] = new_set;
changed = true;
}
}
}
dom
}
pub(crate) fn rvalue_mentions(r: &MirRValue, id: LocalId) -> bool {
let v = |val: &MirValue| matches!(val, MirValue::Local(l) if *l == id);
let p = |pl: &MirPlace| {
pl.local == id
|| pl
.projections
.iter()
.any(|pr| matches!(pr, PlaceProjection::Index(l) if *l == id))
};
match r {
MirRValue::Use(x) => v(x),
MirRValue::BinaryOp { left, right, .. } => v(left) || v(right),
MirRValue::UnaryOp { operand, .. } => v(operand),
MirRValue::Ref { place, .. } | MirRValue::AddressOf { place, .. } => p(place),
MirRValue::Cast { value, .. } => v(value),
MirRValue::Aggregate { operands, .. } => operands.iter().any(v),
MirRValue::Repeat { value, .. } => v(value),
MirRValue::Discriminant(place) | MirRValue::Len(place) => p(place),
MirRValue::NullaryOp(..) | MirRValue::AddressOfGlobal { .. } => false,
MirRValue::FieldAccess { base, .. } => v(base),
MirRValue::VariantField { base, .. } => v(base),
MirRValue::IndexAccess { base, index, .. } => v(base) || v(index),
MirRValue::Deref { ptr, .. } => v(ptr),
MirRValue::TextureSample {
texture,
sampler,
coords,
} => v(texture) || v(sampler) || v(coords),
}
}