use alloc::{borrow::Cow, format, string::String, vec::Vec};
use core::ops::{BitAnd, BitOr, BitXor};
use naga::{
valid::{Capabilities, FunctionInfo, ModuleInfo, ValidationFlags, Validator},
Arena, BinaryOperator, Block, Expression, Function, Handle, Literal, MathFunction, Module,
ScalarKind, Statement, SwitchCase, TypeInner, UnaryOperator,
};
#[inline(never)]
pub fn prune_decided_branches<'a>(
module: Cow<'a, Module>,
info: Cow<'a, ModuleInfo>,
) -> Result<(Cow<'a, Module>, Cow<'a, ModuleInfo>), String> {
let decided: Vec<Option<Decided>> = {
let mut lookup = Lookup {
module: &module,
info: &info,
returns: Vec::with_capacity(module.functions.len()),
};
let infos = module
.functions
.iter()
.map(|(handle, _)| &info[handle])
.chain((0..module.entry_points.len()).map(|index| info.get_entry_point(index)));
functions(&module)
.zip(infos)
.map(|(function, function_info)| {
let values = lookup.decide(function, function_info, &[]);
lookup.returns.push(values.returned(&function.body));
values.decides(&function.body).then_some(values)
})
.collect()
};
if decided.iter().all(Option::is_none) {
return Ok((module, info));
}
let mut module = module.into_owned();
let Module {
functions,
entry_points,
..
} = &mut module;
let pruned = functions
.iter_mut()
.map(|(_, function)| function)
.chain(entry_points.iter_mut().map(|entry| &mut entry.function));
for (function, values) in pruned.zip(&decided) {
let Some(values) = values else {
continue;
};
let mut dropped = alloc::vec![false; function.expressions.len()];
values.prune(&mut function.body, &mut dropped);
function
.named_expressions
.retain(|handle, _| !dropped[handle.index()]);
}
naga::compact::compact(&mut module, naga::compact::KeepUnused::No);
let info = Validator::new(ValidationFlags::all(), Capabilities::all())
.validate_resolved_overrides(&module)
.map_err(|error| format!("{error}"))?;
Ok((Cow::Owned(module), Cow::Owned(info)))
}
fn functions(module: &Module) -> impl Iterator<Item = &Function> {
module
.functions
.iter()
.map(|(_, function)| function)
.chain(module.entry_points.iter().map(|entry| &entry.function))
}
struct Lookup<'m> {
module: &'m Module,
info: &'m ModuleInfo,
returns: Vec<Option<Value>>,
}
const SMALL_CALLEE: usize = 16;
impl Lookup<'_> {
fn decide(
&self,
function: &Function,
function_info: &FunctionInfo,
arguments: &[Option<Value>],
) -> Decided {
let body = BodyFacts::of(function);
let mut values = Vec::with_capacity(function.expressions.len());
for (handle, expression) in function.expressions.iter() {
let scalar = matches!(
function_info[handle].ty.inner_with(&self.module.types),
TypeInner::Scalar(_)
);
let value = scalar
.then(|| self.value(function, &body, handle, expression, &values, arguments))
.flatten();
values.push(value);
}
Decided(values)
}
fn value(
&self,
function: &Function,
body: &BodyFacts,
handle: Handle<Expression>,
expression: &Expression,
before: &[Option<Value>],
arguments: &[Option<Value>],
) -> Option<Value> {
let operand = |handle| decided_at(before, handle);
match *expression {
Expression::Literal(literal) => Value::of(literal),
Expression::Constant(constant) => {
match self.module.global_expressions[self.module.constants[constant].init] {
Expression::Literal(literal) => Value::of(literal),
_ => None,
}
}
Expression::FunctionArgument(index) => {
arguments.get(index as usize).copied().flatten()
}
Expression::CallResult(callee) => decided_at(&self.returns, callee)
.or_else(|| self.call(callee, body.calls[handle.index()]?, before)),
Expression::Load { pointer } => match function.expressions[pointer] {
Expression::LocalVariable(variable) => {
body.temporaries[variable.index()]?.value(before)
}
_ => None,
},
Expression::Unary { op, expr } => operand(expr).and_then(|value| unary(op, value)),
Expression::Binary { op, left, right } => binary(op, operand(left), operand(right)),
Expression::Select {
condition,
accept,
reject,
} => match operand(condition) {
Some(Value::Bool(taken)) => operand(if taken { accept } else { reject }),
_ => None,
},
Expression::Math {
fun,
arg,
arg1,
arg2,
..
} => math(
fun,
operand(arg)?,
arg1.and_then(operand),
arg2.and_then(operand),
),
Expression::As {
expr,
kind,
convert: Some(4),
} => operand(expr).and_then(|value| value.cast(kind)),
_ => None,
}
}
fn call(
&self,
callee: Handle<Function>,
arguments: &[Handle<Expression>],
before: &[Option<Value>],
) -> Option<Value> {
let function = &self.module.functions[callee];
if function.expressions.len() > SMALL_CALLEE {
return None;
}
let values: Vec<Option<Value>> = arguments
.iter()
.map(|&argument| decided_at(before, argument))
.collect();
if values.iter().all(Option::is_none) {
return None;
}
self.decide(function, &self.info[callee], &values)
.returned(&function.body)
}
}
struct BodyFacts<'f> {
calls: Vec<Option<&'f [Handle<Expression>]>>,
temporaries: Vec<Option<Temporary>>,
}
impl<'f> BodyFacts<'f> {
fn of(function: &'f Function) -> Self {
let mut stores = alloc::vec![0u32; function.local_variables.len()];
count_stores(&function.body, &function.expressions, &mut stores);
let mut facts = Self {
calls: alloc::vec![None; function.expressions.len()],
temporaries: alloc::vec![None; function.local_variables.len()],
};
facts.note(&function.body, function, &stores);
facts
}
fn note(&mut self, block: &'f Block, function: &Function, stores: &[u32]) {
for statement in block.iter() {
match *statement {
Statement::Call {
result: Some(result),
ref arguments,
..
} => self.calls[result.index()] = Some(arguments),
Statement::If {
condition,
ref accept,
ref reject,
} => {
let stored = |block: &Block| match block.last() {
Some(&Statement::Store { pointer, value }) => {
match function.expressions[pointer] {
Expression::LocalVariable(variable) => Some((variable, value)),
_ => None,
}
}
_ => None,
};
if let (Some((variable, accept)), Some((other, reject))) =
(stored(accept), stored(reject))
{
let local = &function.local_variables[variable];
if variable == other
&& stores[variable.index()] == 2
&& local.name.is_none()
&& local.init.is_none()
{
self.temporaries[variable.index()] = Some(Temporary {
condition,
accept,
reject,
});
}
}
}
_ => {}
}
for inner in nested(statement) {
self.note(inner, function, stores);
}
}
}
}
fn count_stores(block: &Block, expressions: &Arena<Expression>, stores: &mut [u32]) {
for statement in block.iter() {
if let Statement::Store { pointer, .. } = *statement {
if let Expression::LocalVariable(variable) = expressions[pointer] {
stores[variable.index()] += 1;
}
}
for inner in nested(statement) {
count_stores(inner, expressions, stores);
}
}
}
#[derive(Clone, Copy)]
struct Temporary {
condition: Handle<Expression>,
accept: Handle<Expression>,
reject: Handle<Expression>,
}
impl Temporary {
fn value(self, before: &[Option<Value>]) -> Option<Value> {
match decided_at(before, self.condition) {
Some(Value::Bool(taken)) => decided_at(before, if taken { self.accept } else { self.reject }),
_ => {
let accept = decided_at(before, self.accept)?;
(decided_at(before, self.reject) == Some(accept)).then_some(accept)
}
}
}
}
fn decided_at<T>(values: &[Option<Value>], handle: Handle<T>) -> Option<Value> {
values.get(handle.index()).copied().flatten()
}
#[derive(Clone, Copy, PartialEq)]
enum Value {
Bool(bool),
U32(u32),
I32(i32),
F32(f32),
}
impl Value {
fn of(literal: Literal) -> Option<Self> {
match literal {
Literal::Bool(value) => Some(Self::Bool(value)),
Literal::U32(value) => Some(Self::U32(value)),
Literal::I32(value) => Some(Self::I32(value)),
Literal::F32(value) => Some(Self::F32(value)),
_ => None,
}
}
fn cast(self, kind: ScalarKind) -> Option<Self> {
Some(match (self, kind) {
(Self::F32(value), ScalarKind::Float) => Self::F32(value),
(Self::F32(value), ScalarKind::Uint) => Self::U32(value as u32),
(Self::F32(value), ScalarKind::Sint) => Self::I32(value as i32),
(Self::U32(value), ScalarKind::Float) => Self::F32(value as f32),
(Self::I32(value), ScalarKind::Float) => Self::F32(value as f32),
(Self::Bool(value), ScalarKind::Float) => Self::F32(f32::from(u8::from(value))),
(Self::Bool(value), ScalarKind::Uint) => Self::U32(u32::from(value)),
(Self::Bool(value), ScalarKind::Sint) => Self::I32(i32::from(value)),
(Self::U32(value), ScalarKind::Uint) => Self::U32(value),
(Self::I32(value), ScalarKind::Sint) => Self::I32(value),
_ => return None,
})
}
}
fn math(fun: MathFunction, arg: Value, arg1: Option<Value>, arg2: Option<Value>) -> Option<Value> {
use MathFunction as Fun;
let float = |value: Option<Value>| match value {
Some(Value::F32(value)) => Some(value),
_ => None,
};
let value = float(Some(arg))?;
Some(Value::F32(match fun {
Fun::Abs => value.abs(),
Fun::Saturate => value.max(0.0).min(1.0),
Fun::Max => value.max(float(arg1)?),
Fun::Min => value.min(float(arg1)?),
Fun::Clamp => value.max(float(arg1)?).min(float(arg2)?),
_ => return None,
}))
}
fn unary(op: UnaryOperator, value: Value) -> Option<Value> {
match (op, value) {
(UnaryOperator::LogicalNot, Value::Bool(value)) => Some(Value::Bool(!value)),
(UnaryOperator::BitwiseNot, Value::U32(value)) => Some(Value::U32(!value)),
(UnaryOperator::BitwiseNot, Value::I32(value)) => Some(Value::I32(!value)),
(UnaryOperator::Negate, Value::I32(value)) => Some(Value::I32(value.wrapping_neg())),
(UnaryOperator::Negate, Value::F32(value)) => Some(Value::F32(-value)),
_ => None,
}
}
fn binary(op: BinaryOperator, left: Option<Value>, right: Option<Value>) -> Option<Value> {
use BinaryOperator as Op;
match (op, left, right) {
(Op::LogicalAnd | Op::And, Some(Value::Bool(false)), _)
| (Op::LogicalAnd | Op::And, _, Some(Value::Bool(false))) => Some(Value::Bool(false)),
(Op::LogicalOr | Op::InclusiveOr, Some(Value::Bool(true)), _)
| (Op::LogicalOr | Op::InclusiveOr, _, Some(Value::Bool(true))) => Some(Value::Bool(true)),
(Op::Multiply, Some(Value::F32(zero)), _) | (Op::Multiply, _, Some(Value::F32(zero)))
if zero == 0.0 =>
{
Some(Value::F32(0.0))
}
(_, Some(left), Some(right)) => both(op, left, right),
_ => None,
}
}
fn both(op: BinaryOperator, left: Value, right: Value) -> Option<Value> {
use BinaryOperator as Op;
if let (Op::ShiftLeft | Op::ShiftRight, Value::U32(amount)) = (op, right) {
let leftward = op == Op::ShiftLeft;
return match left {
Value::U32(value) if leftward => Some(Value::U32(value.wrapping_shl(amount))),
Value::U32(value) => Some(Value::U32(value.wrapping_shr(amount))),
Value::I32(value) if leftward => Some(Value::I32(value.wrapping_shl(amount))),
Value::I32(value) => Some(Value::I32(value.wrapping_shr(amount))),
Value::Bool(_) | Value::F32(_) => None,
};
}
match (left, right) {
(Value::Bool(left), Value::Bool(right)) => match op {
Op::LogicalAnd | Op::And => Some(Value::Bool(left & right)),
Op::LogicalOr | Op::InclusiveOr => Some(Value::Bool(left | right)),
Op::Equal => Some(Value::Bool(left == right)),
Op::NotEqual | Op::ExclusiveOr => Some(Value::Bool(left != right)),
_ => None,
},
(Value::U32(left), Value::U32(right)) => integer(op, left, right, Value::U32),
(Value::I32(left), Value::I32(right)) => integer(op, left, right, Value::I32),
(Value::F32(left), Value::F32(right)) => float(op, left, right),
_ => None,
}
}
fn float(op: BinaryOperator, left: f32, right: f32) -> Option<Value> {
use BinaryOperator as Op;
Some(match op {
Op::Add => Value::F32(left + right),
Op::Subtract => Value::F32(left - right),
Op::Multiply => Value::F32(left * right),
Op::Divide if right != 0.0 => Value::F32(left / right),
Op::Equal => Value::Bool(left == right),
Op::NotEqual => Value::Bool(left != right),
Op::Less => Value::Bool(left < right),
Op::LessEqual => Value::Bool(left <= right),
Op::Greater => Value::Bool(left > right),
Op::GreaterEqual => Value::Bool(left >= right),
_ => return None,
})
}
fn integer<T>(op: BinaryOperator, left: T, right: T, wrap: fn(T) -> Value) -> Option<Value>
where
T: Copy + PartialOrd + BitAnd<Output = T> + BitOr<Output = T> + BitXor<Output = T>,
{
use BinaryOperator as Op;
Some(match op {
Op::Equal => Value::Bool(left == right),
Op::NotEqual => Value::Bool(left != right),
Op::Less => Value::Bool(left < right),
Op::LessEqual => Value::Bool(left <= right),
Op::Greater => Value::Bool(left > right),
Op::GreaterEqual => Value::Bool(left >= right),
Op::And => wrap(left & right),
Op::InclusiveOr => wrap(left | right),
Op::ExclusiveOr => wrap(left ^ right),
_ => return None,
})
}
struct Decided(Vec<Option<Value>>);
impl Decided {
fn branch(&self, condition: Handle<Expression>) -> Option<bool> {
match decided_at(&self.0, condition) {
Some(Value::Bool(value)) => Some(value),
_ => None,
}
}
fn returned(&self, body: &Block) -> Option<Value> {
match *body.iter().find(|statement| !matches!(statement, Statement::Emit(_)))? {
Statement::Return { value: Some(value) } => decided_at(&self.0, value),
_ => None,
}
}
fn decides(&self, block: &Block) -> bool {
block.iter().any(|statement| {
let decided = match *statement {
Statement::If { condition, .. } => self.branch(condition).is_some(),
_ => false,
};
decided || nested(statement).any(|inner| self.decides(inner))
})
}
fn prune(&self, block: &mut Block, dropped: &mut [bool]) {
let statements = core::mem::take(block);
for (mut statement, span) in statements.span_into_iter() {
if let Statement::If {
condition,
ref mut accept,
ref mut reject,
} = statement
{
if let Some(value) = self.branch(condition) {
let (taken, other) = if value { (accept, reject) } else { (reject, accept) };
mark_defined(other, dropped);
let mut taken = core::mem::take(taken);
self.prune(&mut taken, dropped);
block.push(Statement::Block(taken), span);
continue;
}
}
for inner in nested_mut(&mut statement) {
self.prune(inner, dropped);
}
block.push(statement, span);
}
}
}
fn mark_defined(block: &Block, defined: &mut [bool]) {
for statement in block.iter() {
match *statement {
Statement::Emit(ref range) => {
for handle in range.clone() {
defined[handle.index()] = true;
}
}
Statement::Call {
result: Some(result),
..
} => defined[result.index()] = true,
_ => {}
}
for inner in nested(statement) {
mark_defined(inner, defined);
}
}
}
fn nested(statement: &Statement) -> impl Iterator<Item = &Block> {
let (pair, cases): ([Option<&Block>; 2], &[SwitchCase]) = match *statement {
Statement::If {
ref accept,
ref reject,
..
} => ([Some(accept), Some(reject)], &[]),
Statement::Block(ref inner) => ([Some(inner), None], &[]),
Statement::Loop {
ref body,
ref continuing,
..
} => ([Some(body), Some(continuing)], &[]),
Statement::Switch { ref cases, .. } => ([None, None], cases),
_ => ([None, None], &[]),
};
pair.into_iter()
.flatten()
.chain(cases.iter().map(|case| &case.body))
}
fn nested_mut(statement: &mut Statement) -> impl Iterator<Item = &mut Block> {
let (pair, cases): ([Option<&mut Block>; 2], &mut [SwitchCase]) = match *statement {
Statement::If {
ref mut accept,
ref mut reject,
..
} => ([Some(accept), Some(reject)], &mut []),
Statement::Block(ref mut inner) => ([Some(inner), None], &mut []),
Statement::Loop {
ref mut body,
ref mut continuing,
..
} => ([Some(body), Some(continuing)], &mut []),
Statement::Switch { ref mut cases, .. } => ([None, None], cases),
_ => ([None, None], &mut []),
};
pair.into_iter()
.flatten()
.chain(cases.iter_mut().map(|case| &mut case.body))
}