use crate::ShaderDiagnostics;
use crate::call_budget::{declarations, declared_names, loops};
use crate::loop_bound::{MAX_LOOP_ITERATIONS, header_parts, is_identifier_byte, proven_count};
pub(crate) const FETCH_UNITS: u64 = 4;
pub(crate) const TRANSCENDENTAL_UNITS: u64 = 2;
pub(crate) const ARITHMETIC_UNITS: u64 = 1;
pub(crate) const MAX_INVOCATION_COST: u64 = 1_048_576;
const TRANSCENDENTALS: [&str; 17] = [
"sin",
"cos",
"tan",
"asin",
"acos",
"atan",
"atan2",
"sinh",
"cosh",
"tanh",
"exp",
"exp2",
"log",
"log2",
"pow",
"sqrt",
"inverseSqrt",
];
const KEYWORDS: [&str; 6] = ["if", "for", "while", "switch", "return", "loop"];
#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct EffectCost {
pub(crate) fetches: u64,
pub(crate) transcendentals: u64,
pub(crate) arithmetic: u64,
}
impl EffectCost {
pub(crate) const fn fixed(fetches: u64, transcendentals: u64) -> Self {
Self {
fetches,
transcendentals,
arithmetic: 4 * (fetches + transcendentals),
}
}
pub(crate) const fn units(self) -> u64 {
self.fetches
.saturating_mul(FETCH_UNITS)
.saturating_add(self.transcendentals.saturating_mul(TRANSCENDENTAL_UNITS))
.saturating_add(self.arithmetic.saturating_mul(ARITHMETIC_UNITS))
}
const fn plus(self, other: Self) -> Self {
Self {
fetches: self.fetches.saturating_add(other.fetches),
transcendentals: self.transcendentals.saturating_add(other.transcendentals),
arithmetic: self.arithmetic.saturating_add(other.arithmetic),
}
}
pub(crate) const fn times(self, count: u64) -> Self {
Self {
fetches: self.fetches.saturating_mul(count),
transcendentals: self.transcendentals.saturating_mul(count),
arithmetic: self.arithmetic.saturating_mul(count),
}
}
fn costlier(self, other: Self) -> Self {
if other.units() > self.units() {
other
} else {
self
}
}
}
#[derive(Copy, Clone)]
enum Item {
Cost(EffectCost),
Call(usize),
}
struct Walked {
straight: Vec<Item>,
loops: Vec<Loop>,
}
struct Loop {
items: Vec<Item>,
count: Option<u64>,
}
pub(crate) fn invocation_cost(code: &str) -> EffectCost {
let declared = declarations(code);
let names = declared_names(&declared);
let arrays = array_types(code);
let copies = array_names(code, &arrays);
let walked = declared
.iter()
.map(|(_, body)| walk(code, body.clone(), &names, &arrays, &copies))
.collect::<Vec<_>>();
let module_arrays = arrays
.iter()
.filter(|array| {
!declared
.iter()
.any(|(_, body)| body.contains(&array.span.start))
})
.fold(0_u64, |total, array| {
total.saturating_add(array.slots.unwrap_or(0))
});
let straight = straight_costs(&walked);
let calls = straight_calls(&walked, &roots(&walked));
let resolve = |items: &[Item]| {
items.iter().fold(EffectCost::default(), |total, item| {
total.plus(match *item {
Item::Cost(cost) => cost,
Item::Call(callee) => straight[callee],
})
})
};
let roots = roots(&walked);
let entry = straight
.iter()
.zip(&roots)
.filter(|(_, root)| **root)
.fold(EffectCost::default(), |worst, (&cost, _)| {
worst.costlier(cost)
});
let mut iterations = walked
.iter()
.zip(&calls)
.flat_map(|(function, calls)| {
function.loops.iter().map(move |body| {
let most = match (body.count, calls) {
(Some(count), Some(calls)) => count.saturating_mul(*calls),
_ => u64::MAX,
};
(resolve(&body.items), most)
})
})
.collect::<Vec<_>>();
iterations.sort_by_key(|(cost, _)| std::cmp::Reverse(cost.units()));
let mut budget = u64::from(MAX_LOOP_ITERATIONS);
let mut total = entry.plus(EffectCost {
arithmetic: module_arrays,
..EffectCost::default()
});
for (cost, most) in iterations {
let spent = budget.min(most);
total = total.plus(cost.times(spent));
budget -= spent;
}
total
}
fn roots(walked: &[Walked]) -> Vec<bool> {
let mut called = vec![false; walked.len()];
for function in walked {
let items = function
.straight
.iter()
.chain(function.loops.iter().flat_map(|body| body.items.iter()));
for item in items {
if let Item::Call(callee) = item {
called[*callee] = true;
}
}
}
if called.iter().all(|called| *called) {
return vec![true; walked.len()];
}
called.into_iter().map(|called| !called).collect()
}
fn straight_calls(walked: &[Walked], roots: &[bool]) -> Vec<Option<u64>> {
let mut in_loop = vec![false; walked.len()];
for function in walked {
for body in &function.loops {
for item in &body.items {
if let Item::Call(callee) = item {
in_loop[*callee] = true;
}
}
}
}
let mut changed = true;
while changed {
changed = false;
for (caller, function) in walked.iter().enumerate() {
if !in_loop[caller] {
continue;
}
for item in &function.straight {
if let Item::Call(callee) = item
&& !in_loop[*callee]
{
in_loop[*callee] = true;
changed = true;
}
}
}
}
let base = roots
.iter()
.map(|root| u64::from(*root))
.collect::<Vec<_>>();
let mut runs = base.clone();
for _ in 0..walked.len() {
let mut next = base.clone();
for (caller, function) in walked.iter().enumerate() {
for item in &function.straight {
if let Item::Call(callee) = item {
next[*callee] = next[*callee].saturating_add(runs[caller]);
}
}
}
if next == runs {
break;
}
runs = next;
}
runs.into_iter()
.zip(in_loop)
.map(|(runs, in_loop)| (!in_loop).then_some(runs))
.collect()
}
pub(crate) fn check_invocation_cost(code: &str) -> Result<EffectCost, ShaderDiagnostics> {
let cost = invocation_cost(code);
let units = cost.units();
if units > MAX_INVOCATION_COST {
return Err(ShaderDiagnostics::error(format!(
"the effect may spend {} texture reads and {} transcendental calls per pixel \
({units} units), above the {MAX_INVOCATION_COST} a runtime effect may; read fewer \
taps per loop iteration or loop fewer times",
cost.fetches, cost.transcendentals
)));
}
Ok(cost)
}
fn straight_costs(walked: &[Walked]) -> Vec<EffectCost> {
let mut cost: Vec<Option<EffectCost>> = vec![None; walked.len()];
let mut open = vec![false; walked.len()];
let calls = |function: usize| {
walked[function]
.straight
.iter()
.filter_map(|item| match item {
Item::Call(callee) => Some(*callee),
Item::Cost(_) => None,
})
.collect::<Vec<_>>()
};
for root in 0..walked.len() {
if cost[root].is_some() {
continue;
}
let mut stack = vec![(root, calls(root), 0_usize)];
open[root] = true;
while let Some((function, callees, next)) = stack.last_mut() {
if let Some(&callee) = callees.get(*next) {
*next += 1;
if cost[callee].is_none() && !open[callee] {
open[callee] = true;
let callee_calls = calls(callee);
stack.push((callee, callee_calls, 0));
}
continue;
}
let function = *function;
let total =
walked[function]
.straight
.iter()
.fold(EffectCost::default(), |total, item| {
total.plus(match *item {
Item::Cost(cost) => cost,
Item::Call(callee) => cost[callee].unwrap_or_default(),
})
});
cost[function] = Some(total);
open[function] = false;
stack.pop();
}
}
cost.into_iter().map(Option::unwrap_or_default).collect()
}
fn walk(
code: &str,
body: std::ops::Range<usize>,
names: &std::collections::HashMap<&str, usize>,
arrays: &[ArrayType],
copies: &std::collections::HashMap<&str, u64>,
) -> Walked {
let spans = loops(code, body.clone());
let mut walked = Walked {
straight: Vec::new(),
loops: spans
.iter()
.map(|span| Loop {
items: Vec::new(),
count: (!spans
.iter()
.any(|outer| outer.start < span.start && outer.contains(&span.start)))
.then(|| literal_count(code, span.clone()))
.flatten(),
})
.collect(),
};
let bytes = code.as_bytes();
let mut push = |at: usize, item: Item| {
let innermost = spans
.iter()
.enumerate()
.filter(|(_, span)| span.contains(&at))
.max_by_key(|(_, span)| span.start)
.map(|(index, _)| index);
match innermost {
Some(index) => walked.loops[index].items.push(item),
None => walked.straight.push(item),
}
};
let charge = |slots: u64| {
Item::Cost(EffectCost {
arithmetic: slots,
..EffectCost::default()
})
};
let mut index = body.start;
while index < body.end {
let byte = bytes[index];
if is_identifier_byte(byte) {
let end = index
+ code[index..body.end]
.bytes()
.take_while(|&byte| is_identifier_byte(byte))
.count();
let word = &code[index..end];
if let Some(array) = arrays.iter().find(|array| array.span.start == index) {
push(index, charge(array.slots.unwrap_or(0)));
index = array.span.end.min(body.end);
continue;
}
if let Some(&slots) = copies.get(word)
&& !code[end..body.end].trim_start().starts_with(['[', ':'])
{
push(index, charge(slots));
}
let called = code[end..body.end].trim_start().starts_with('(');
if called && !KEYWORDS.contains(&word) && !byte.is_ascii_digit() {
push(
index,
names
.get(word)
.map_or_else(|| Item::Cost(call_cost(word)), |&callee| Item::Call(callee)),
);
}
index = end;
} else if is_operator(byte) {
let end = index
+ code[index..body.end]
.bytes()
.take_while(|&byte| is_operator(byte))
.count();
if &code[index..end] != "=" {
push(
index,
Item::Cost(EffectCost {
arithmetic: 1,
..EffectCost::default()
}),
);
}
index = end;
} else {
index += 1;
}
}
walked
}
fn literal_count(code: &str, span: std::ops::Range<usize>) -> Option<u64> {
let open = span.start + code[span.clone()].find('(')?;
let close = crate::loop_bound::matching(code, open).ok()?;
let [init, condition, update] = header_parts(&code[open + 1..close])?;
let body = &code[close + 1..span.end];
proven_count(init, condition, update, body.trim_start())
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct ArrayType {
pub(crate) span: std::ops::Range<usize>,
pub(crate) slots: Option<u64>,
pub(crate) templated: bool,
}
pub(crate) fn array_types(code: &str) -> Vec<ArrayType> {
let mut found = Vec::new();
let mut from = 0;
while let Some(start) = crate::loop_bound::find_keyword(code, from, "array") {
from = start + "array".len();
let open = from + (code[from..].len() - code[from..].trim_start().len());
if code.as_bytes().get(open) != Some(&b'<') {
found.push(ArrayType {
span: start..from,
slots: None,
templated: false,
});
continue;
}
let Some(close) = template_end(code, open) else {
found.push(ArrayType {
span: start..code.len(),
slots: None,
templated: true,
});
continue;
};
found.push(ArrayType {
span: start..close + 1,
slots: array_slots(&code[open + 1..close]),
templated: true,
});
}
found
}
fn template_end(code: &str, open: usize) -> Option<usize> {
let mut depth = 0_usize;
for (index, byte) in code.bytes().enumerate().skip(open) {
match byte {
b'<' => depth += 1,
b'>' => {
depth -= 1;
if depth == 0 {
return Some(index);
}
}
b';' | b'{' | b'}' => return None,
_ => {}
}
}
None
}
fn array_slots(template: &str) -> Option<u64> {
let mut depth = 0_usize;
let comma = template.bytes().enumerate().find_map(|(index, byte)| {
match byte {
b'<' | b'(' => depth += 1,
b'>' | b')' => depth = depth.saturating_sub(1),
b',' if depth == 0 => return Some(index),
_ => {}
}
None
})?;
let element = template[..comma].trim();
let count = template[comma + 1..].trim();
let count = count.strip_suffix(['u', 'i']).unwrap_or(count);
if count.is_empty() || !count.bytes().all(|byte| byte.is_ascii_digit()) {
return None;
}
count
.parse::<u64>()
.ok()?
.checked_mul(element_slots(element)?)
}
fn element_slots(element: &str) -> Option<u64> {
if let Some(rest) = element.strip_prefix("array") {
let open = element.len() - rest.trim_start().len();
let close = template_end(element, open)?;
return (close + 1 == element.len())
.then(|| array_slots(&element[open + 1..close]))
.flatten();
}
let name = element.split('<').next().unwrap_or_default().trim();
if matches!(name, "f32" | "f16" | "i32" | "u32" | "bool")
|| ["vec2", "vec3", "vec4"].iter().any(|vector| {
name.strip_prefix(vector)
.is_some_and(|suffix| matches!(suffix, "" | "f" | "h" | "i" | "u"))
})
{
return Some(1);
}
let columns = name.strip_prefix("mat")?.bytes().next()?;
let shape = &name[3..];
let valid = shape.len() >= 3
&& matches!(shape.as_bytes()[1], b'x')
&& matches!(shape.as_bytes()[2], b'2'..=b'4')
&& matches!(&shape[3..], "" | "f" | "h");
(valid && matches!(columns, b'2'..=b'4')).then(|| u64::from(columns - b'0'))
}
fn array_names<'a>(code: &'a str, arrays: &[ArrayType]) -> std::collections::HashMap<&'a str, u64> {
let mut names = std::collections::HashMap::new();
for array in arrays {
let Some(slots) = array.slots else { continue };
let before = code[..array.span.start].trim_end();
let Some(before) = before.strip_suffix(':').or_else(|| {
before
.strip_suffix('=')
.filter(|rest| !rest.ends_with(['=', '!', '<', '>']))
}) else {
continue;
};
let before = before.trim_end();
let name_start = before
.bytes()
.rposition(|byte| !is_identifier_byte(byte))
.map_or(0, |index| index + 1);
let name = &before[name_start..];
if !name.is_empty() {
let held = names.entry(name).or_insert(0);
*held = slots.max(*held);
}
}
names
}
fn call_cost(name: &str) -> EffectCost {
let fetch = name.starts_with("sample_")
|| name.starts_with("textureSample")
|| name.starts_with("textureGather")
|| matches!(name, "from_color" | "to_color" | "textureLoad");
if fetch {
EffectCost {
fetches: 1,
..EffectCost::default()
}
} else if TRANSCENDENTALS.contains(&name) {
EffectCost {
transcendentals: 1,
..EffectCost::default()
}
} else {
EffectCost {
arithmetic: 1,
..EffectCost::default()
}
}
}
const fn is_operator(byte: u8) -> bool {
matches!(
byte,
b'+' | b'-' | b'*' | b'/' | b'%' | b'&' | b'|' | b'^' | b'!' | b'<' | b'>' | b'=' | b'~'
)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::loop_bound::blank_comments;
fn cost(body: &str) -> EffectCost {
invocation_cost(&blank_comments(body))
}
#[test]
fn loop_budget_bounds_the_costliest_iteration() {
let body = "fn effect(uv: vec2f, src: vec4f) -> vec4f {\n\
var a = src;\n\
for (var i = 0u; i < n; i++) { a = a * sample_src(uv); }\n\
for (var j = 0u; j < n; j++) { a = sin(a); }\n\
return a; }";
let worst = cost(body);
assert_eq!(
worst,
EffectCost {
fetches: 1024,
transcendentals: 0,
arithmetic: 3 * 1024,
}
);
assert_eq!(worst.units(), 1024 * (4 + 3));
}
#[test]
fn nested_loops_share_the_budget() {
let body = "fn effect(uv: vec2f, src: vec4f) -> vec4f {\n\
var a = 0.0;\n\
for (var i = 0u; i < 32u; i++) {\n\
a += 1.0;\n\
for (var j = 0u; j < 32u; j++) { a += cos(a) + sample_src(uv).r; }\n\
}\n\
return vec4f(a); }";
let worst = cost(body);
assert_eq!(
worst,
EffectCost {
fetches: 1024,
transcendentals: 1024,
arithmetic: 4 * 1024 + 1,
}
);
}
#[test]
fn a_literal_count_caps_its_loop_and_leaves_the_budget_to_others() {
let body = "fn effect(uv: vec2f, src: vec4f) -> vec4f {\n\
var a = src;\n\
for (var i = 0u; i < 64u; i++) { a = a * sample_src(uv); }\n\
for (var j = 0; j < n; j++) { a = a + 1.0; }\n\
return a; }";
let worst = cost(body);
assert_eq!(worst.fetches, 64);
assert_eq!(worst.arithmetic, 64 * 3 + 960 * 3);
for body in [
"fn effect(uv: vec2f, src: vec4f) -> vec4f { var a = src; \
for (var i = 0u; i < 64u; i++) { a = sample_src(uv); i = 0u; } return a; }",
"fn effect(uv: vec2f, src: vec4f) -> vec4f { var a = src; \
for (var k = 0u; k < n; k++) { \
for (var i = 0u; i < 4u; i++) { a = sample_src(uv); } } return a; }",
"fn taps(uv: vec2f) -> vec4f { var a = vec4f(0.0); \
for (var i = 0u; i < 4u; i++) { a = sample_src(uv); } return a; }\n\
fn effect(uv: vec2f, src: vec4f) -> vec4f { var a = src; \
for (var k = 0u; k < n; k++) { a = taps(uv); } return a; }",
] {
assert_eq!(cost(body).fetches, 1024, "{body}");
}
let twice = "fn taps(uv: vec2f) -> vec4f { var a = vec4f(0.0); \
for (var i = 0u; i <= 9u; i++) { a = sample_src(uv); } return a; }\n\
fn effect(uv: vec2f, src: vec4f) -> vec4f { return taps(uv) + taps(uv); }";
assert_eq!(cost(twice).fetches, 20);
}
#[test]
fn a_counted_loop_is_priced_at_its_literal_count_however_its_counter_is_written() {
for (header, write, count) in [
("var i = 0u; i < 8u; i++", "(i)--;", 8),
("var i = 0u; i < 8u; i++", "(i) -= 1u;", 8),
("var i = 0u; i < 2u; i++", "(i) = 0u;", 2),
("var i = 0u; i < 2u; i++", "*(&(i)) = 0u;", 2),
("var i = 0u; i < 2u; i++", "let p = &(i); *p = 0u;", 2),
("var i = 4294967295u; i <= 4294967295u; i++", "", 1),
("var i = 2147483647; i <= 2147483647; i++", "", 1),
] {
let body = format!(
"fn effect(uv: vec2f, src: vec4f) -> vec4f {{ var a = src; \
for ({header}) {{ {write} a = a * sample_src(uv); }} return a; }}"
);
assert_eq!(cost(&body).fetches, count, "{body}");
}
}
#[test]
fn declaring_and_copying_a_whole_array_costs_its_elements() {
let copy = "fn effect(uv: vec2f, src: vec4f) -> vec4f { \
var a: array<vec4f, 100>; var b: array<vec4f, 100>; \
for (var i = 0u; i < n; i++) { b = a; } return b[0]; }";
let worst = cost(copy);
assert!(worst.arithmetic >= 200 + 1024 * 200, "{worst:?}");
let private = "var<private> big: array<vec4f, 100>;\n\
fn effect(uv: vec2f, src: vec4f) -> vec4f { return big[0] + src; }";
assert!(cost(private).arithmetic >= 100);
let indexed = "fn effect(uv: vec2f, src: vec4f) -> vec4f { \
var a: array<vec4f, 100>; return a[1]; }";
assert!(cost(indexed).arithmetic < 110, "{:?}", cost(indexed));
}
#[test]
fn helpers_count_as_fetches() {
let body = "fn helper(uv: vec2f) -> vec4f { return sample_src(uv) + from_color(uv); }\n\
fn effect(uv: vec2f, src: vec4f) -> vec4f {\n\
let t = to_color(uv) + sample_mask(uv) + textureLoad(x, vec2i(0), 0);\n\
return helper(uv) * exp(t); }";
let worst = cost(body);
assert_eq!(worst.fetches, 5);
assert_eq!(worst.transcendentals, 1);
assert_eq!(worst.arithmetic, 5);
}
#[test]
fn a_call_in_a_loop_is_inlined_into_the_iteration() {
let body = "fn tap(uv: vec2f) -> vec4f { return sample_src(uv) * 2.0; }\n\
fn effect(uv: vec2f, src: vec4f) -> vec4f {\n\
var a = vec4f(0.0);\n\
for (var i = 0u; i < n; i++) { a += tap(uv); }\n\
return a; }";
let worst = cost(body);
assert_eq!(worst.fetches, 1024);
assert_eq!(worst.arithmetic, 4 * 1024 + 1);
}
#[test]
fn every_built_in_fits_the_cost_cap_with_room() {
let mut definitions = crate::builtins::internal_effect_definitions();
definitions.extend(crate::builtin_effect_definitions());
definitions.extend(crate::builtin_transition_definitions());
let (units, id) = definitions
.iter()
.map(|definition| {
let units = invocation_cost(&blank_comments(&definition.wgsl_body)).units();
(units, definition.id.clone())
})
.max()
.expect("built-ins");
assert!(
units.saturating_mul(4) <= MAX_INVOCATION_COST,
"{id} costs {units} units"
);
}
#[test]
fn the_max_fixture_is_refused_with_a_diagnostic_naming_its_cost() {
let fixture = std::fs::read_to_string(concat!(
env!("CARGO_MANIFEST_DIR"),
"/../../tests/cases/gpu-watchdog/max-effects.json"
))
.expect("the max fixture");
let effects: serde_json::Value = serde_json::from_str(&fixture).expect("JSON");
let body = effects[0]["wgslBody"].as_str().expect("a WGSL body");
let error = check_invocation_cost(&blank_comments(body)).expect_err("refused");
let message = format!("{error:?}");
let cost = invocation_cost(&blank_comments(body));
assert!(
message.contains(&format!("{} texture reads", cost.fetches))
&& message.contains(&format!("{} transcendental calls", cost.transcendentals))
&& message.contains(&format!("({} units)", cost.units())),
"{message}"
);
}
}