use crate::content::shader::{SHADER_LOOP_BUDGET, ShaderError};
use naga::{BinaryOperator, Block, Expression, Function, Handle, Literal, Module, Statement};
use std::collections::HashMap;
pub(super) fn check(module: &Module, game: impl Fn(&str) -> bool) -> Result<(), ShaderError> {
let mut counter = Counter {
module,
counted: HashMap::new(),
};
for (handle, function) in module.functions.iter() {
let name = function.name.clone().unwrap_or_default();
if !game(&name) {
continue;
}
let iterations = counter
.function(handle)
.ok_or_else(|| ShaderError::UnboundedLoop {
function: name.clone(),
})?;
if iterations > SHADER_LOOP_BUDGET {
return Err(ShaderError::LoopBudget {
function: name,
iterations,
});
}
}
Ok(())
}
struct Counter<'a> {
module: &'a Module,
counted: HashMap<Handle<Function>, Option<u64>>,
}
impl Counter<'_> {
fn function(&mut self, handle: Handle<Function>) -> Option<u64> {
if let Some(&iterations) = self.counted.get(&handle) {
return iterations;
}
let function = &self.module.functions[handle];
let iterations = self.block(function, &function.body, false);
self.counted.insert(handle, iterations);
iterations
}
fn block(&mut self, function: &Function, block: &Block, nested: bool) -> Option<u64> {
let mut total = 0u64;
for (at, statement) in block.iter().enumerate() {
let iterations = match statement {
Statement::Block(inner) => self.block(function, inner, nested)?,
Statement::If { accept, reject, .. } => self
.block(function, accept, nested)?
.max(self.block(function, reject, nested)?),
Statement::Switch { cases, .. } => {
let mut sum = 0u64;
for case in cases {
sum = sum.saturating_add(self.block(function, &case.body, nested)?);
}
sum
}
Statement::Loop {
body,
continuing,
break_if,
} => {
let count = counted(
self.module,
function,
(block, at),
body,
continuing,
*break_if,
nested,
)?;
let inner = self
.block(function, body, true)?
.saturating_add(self.block(function, continuing, true)?);
count.saturating_mul(inner.max(1))
}
Statement::Call {
function: callee, ..
} => self.function(*callee)?,
_ => 0,
};
total = total.saturating_add(iterations);
}
Some(total)
}
}
fn constant(module: &Module, function: &Function, expression: Handle<Expression>) -> Option<i64> {
let literal = |literal: &Literal| match *literal {
Literal::I32(value) => Some(i64::from(value)),
Literal::U32(value) => Some(i64::from(value)),
Literal::AbstractInt(value) => Some(value),
_ => None,
};
match &function.expressions[expression] {
Expression::Literal(value) => literal(value),
Expression::ZeroValue(_) => Some(0),
Expression::Constant(handle) => {
match &module.global_expressions[module.constants[*handle].init] {
Expression::Literal(value) => literal(value),
Expression::ZeroValue(_) => Some(0),
_ => None,
}
}
_ => None,
}
}
fn local(function: &Function, pointer: Handle<Expression>) -> Option<Handle<naga::LocalVariable>> {
match function.expressions[pointer] {
Expression::LocalVariable(variable) => Some(variable),
_ => None,
}
}
fn loaded(
function: &Function,
expression: Handle<Expression>,
) -> Option<Handle<naga::LocalVariable>> {
match function.expressions[expression] {
Expression::Load { pointer } => local(function, pointer),
_ => None,
}
}
fn comparison(
module: &Module,
function: &Function,
test: Handle<Expression>,
) -> Option<(Handle<naga::LocalVariable>, BinaryOperator, i64)> {
let Expression::Binary { op, left, right } = function.expressions[test] else {
return None;
};
if let Some(variable) = loaded(function, left) {
return Some((variable, op, constant(module, function, right)?));
}
let variable = loaded(function, right)?;
let mirrored = match op {
BinaryOperator::Less => BinaryOperator::Greater,
BinaryOperator::LessEqual => BinaryOperator::GreaterEqual,
BinaryOperator::Greater => BinaryOperator::Less,
BinaryOperator::GreaterEqual => BinaryOperator::LessEqual,
_ => return None,
};
Some((variable, mirrored, constant(module, function, left)?))
}
fn counted(
module: &Module,
function: &Function,
(block, at): (&Block, usize),
body: &Block,
continuing: &Block,
break_if: Option<Handle<Expression>>,
nested: bool,
) -> Option<u64> {
let (variable, op, limit, before) = match break_if {
Some(test) => {
let (variable, op, limit) = comparison(module, function, test)?;
(variable, op, limit, false)
}
None => {
let at = body
.iter()
.position(|statement| !matches!(statement, Statement::Emit(_)))?;
let Statement::If {
condition,
accept,
reject,
} = &body[at]
else {
return None;
};
if !accept.is_empty() || reject.len() != 1 || !matches!(reject[0], Statement::Break) {
return None;
}
let (variable, op, limit) = comparison(module, function, *condition)?;
if !evaluated_in(function, &body[..at], *condition) {
return None;
}
(variable, op, limit, true)
}
};
let (low, high) = match module.types[function.local_variables[variable].ty].inner {
naga::TypeInner::Scalar(naga::Scalar {
kind: naga::ScalarKind::Sint,
width: 4,
}) => (i64::from(i32::MIN), i64::from(i32::MAX)),
naga::TypeInner::Scalar(naga::Scalar {
kind: naga::ScalarKind::Uint,
width: 4,
}) => (0, i64::from(u32::MAX)),
_ => return None,
};
let mut steps = continuing
.iter()
.enumerate()
.filter_map(|(at, statement)| match statement {
Statement::Store { pointer, value } if local(function, *pointer) == Some(variable) => {
Some((at, *value))
}
_ => None,
});
let ((store_at, step), None) = (steps.next()?, steps.next()) else {
return None;
};
if !evaluated_in(function, &continuing[..store_at], step)
|| break_if.is_some_and(|test| !evaluated_in(function, &continuing[store_at + 1..], test))
{
return None;
}
let Expression::Binary {
op: BinaryOperator::Add,
left,
right,
} = function.expressions[step]
else {
return None;
};
let step = if loaded(function, left) == Some(variable) {
constant(module, function, right)?
} else if loaded(function, right) == Some(variable) {
constant(module, function, left)?
} else {
return None;
};
let start_store = block[..at]
.iter()
.rev()
.find(|statement| !matches!(statement, Statement::Emit(_)))
.and_then(|statement| match statement {
Statement::Store { pointer, value } if local(function, *pointer) == Some(variable) => {
Some(*value)
}
_ => None,
});
if start_store.is_none() && !before && nested {
return None;
}
let start = match start_store {
Some(value) => constant(module, function, value)?,
None => match function.local_variables[variable].init {
Some(init) => constant(module, function, init)?,
None => 0,
},
};
if stores(function, &function.body, variable) != 1 + usize::from(start_store.is_some())
|| pointer_escapes(function, variable)
{
return None;
}
let fits = |value: i64| (low..=high).contains(&value);
if step <= 0 || !fits(start) || !fits(limit) || !fits(step) || !fits(start.max(limit) + step) {
return None;
}
let (span, step) = (limit - start, step as u64);
let ahead = u64::try_from(span).unwrap_or(0);
let iterations = match (before, op) {
(true, BinaryOperator::Less) => ahead.div_ceil(step),
(true, BinaryOperator::LessEqual) if span >= 0 => ahead / step + 1,
(true, BinaryOperator::LessEqual) => 0,
(false, BinaryOperator::GreaterEqual) => ahead.div_ceil(step).max(1),
(false, BinaryOperator::Greater) if span >= 0 => ahead / step + 1,
(false, BinaryOperator::Greater) => 1,
_ => return None,
};
Some(iterations)
}
fn evaluated_in(
function: &Function,
statements: &[Statement],
expression: Handle<Expression>,
) -> bool {
let emitted = |handle: Handle<Expression>| {
statements.iter().any(|statement| {
matches!(statement, Statement::Emit(range) if range.clone().any(|emitted| emitted == handle))
})
};
let Expression::Binary { left, right, .. } = function.expressions[expression] else {
return false;
};
emitted(expression)
&& [left, right].into_iter().all(|operand| {
!matches!(function.expressions[operand], Expression::Load { .. }) || emitted(operand)
})
}
fn stores(function: &Function, block: &Block, variable: Handle<naga::LocalVariable>) -> usize {
block
.iter()
.map(|statement| match statement {
Statement::Store { pointer, .. } => {
usize::from(local(function, *pointer) == Some(variable))
}
Statement::Block(inner) => stores(function, inner, variable),
Statement::If { accept, reject, .. } => {
stores(function, accept, variable) + stores(function, reject, variable)
}
Statement::Switch { cases, .. } => cases
.iter()
.map(|case| stores(function, &case.body, variable))
.sum(),
Statement::Loop {
body, continuing, ..
} => stores(function, body, variable) + stores(function, continuing, variable),
_ => 0,
})
.sum()
}
fn pointer_escapes(function: &Function, variable: Handle<naga::LocalVariable>) -> bool {
let names = |pointer: Handle<Expression>| local(function, pointer) == Some(variable);
let in_expressions = function
.expressions
.iter()
.any(|(_, expression)| match expression {
Expression::Access { base, .. } | Expression::AccessIndex { base, .. } => names(*base),
_ => false,
});
in_expressions || calls_with(&function.body, &names)
}
fn calls_with(block: &Block, names: &dyn Fn(Handle<Expression>) -> bool) -> bool {
block.iter().any(|statement| match statement {
Statement::Call { arguments, .. } => arguments.iter().any(|&argument| names(argument)),
Statement::Atomic { pointer, .. } => names(*pointer),
Statement::Block(inner) => calls_with(inner, names),
Statement::If { accept, reject, .. } => {
calls_with(accept, names) || calls_with(reject, names)
}
Statement::Switch { cases, .. } => cases.iter().any(|case| calls_with(&case.body, names)),
Statement::Loop {
body, continuing, ..
} => calls_with(body, names) || calls_with(continuing, names),
_ => false,
})
}