Skip to main content

naga/back/msl/
hoist.rs

1/*!
2Finding temporaries that must be declared outside a loop.
3
4Naga IR's [`Loop`] statement runs its `continuing` block after its `body`, but
5MSL has no equivalent construct, so [`Writer::put_block`] emits the `continuing`
6block at the *top* of a `while` loop, skipped on the first iteration:
7
8```ignore
9bool loop_init = true;
10while(true) {
11    if (!loop_init) {
12        <continuing>
13        if (<break_if>) { break; }
14    }
15    loop_init = false;
16    <body>
17}
18```
19
20Expressions emitted in `body` are in scope in `continuing`, but the temporaries
21holding their values are declared *below* the generated `continuing` code, so
22they can't be named there. Re-evaluating such an expression in place would use
23the state at the end of the loop iteration, which may have changed from the
24state at the original position.
25
26So when a loop has a `continuing` block, we declare the temporaries the
27`continuing` block needs ahead of the `while` loop, and have the body merely
28assign to them.
29
30[`Loop`]: crate::Statement::Loop
31[`Writer::put_block`]: super::writer::Writer::put_block
32*/
33
34use core::fmt::Write;
35
36use super::{writer::StatementContext, BackendResult, Writer};
37use crate::{
38    arena::{Arena, Handle, HandleSet},
39    back,
40    compact::ModuleTracer,
41    proc::TypeResolution,
42};
43
44impl<W: Write> Writer<W> {
45    /// Declare the temporaries that a loop's `continuing` block needs ahead of
46    /// the loop.
47    ///
48    /// Record them in [`Self::hoisted_loop_expressions`], so that `continuing` can
49    /// name them and the body assigns to them rather than declaring them. Each
50    /// entry is moved to [`Self::named_expressions`] when the body writes the
51    /// expression's definition, which it always does, since every candidate
52    /// comes from a statement in `body`.
53    ///
54    /// See [the module documentation](self) for why this is needed.
55    pub(super) fn hoist_continuing_dependencies(
56        &mut self,
57        level: back::Level,
58        body: &crate::Block,
59        continuing: &crate::Block,
60        break_if: Option<Handle<crate::Expression>>,
61        context: &StatementContext,
62    ) -> BackendResult {
63        let context = &context.expression;
64        let expressions = &context.function.expressions;
65
66        // The candidates are the definitions that get a temporary at all.
67        //
68        // Skipping the rest is deliberate: `continuing` re-evaluates those in
69        // place, and that is sound, because every expression whose value
70        // depends on *when* it is evaluated already gets a temporary. Loads,
71        // samples and derivatives have a `bake_ref_count` of one, so any use at
72        // all bakes them, and statement results have no inline form. What's
73        // left to re-evaluate is arithmetic and address computation.
74
75        let mut candidates = HandleSet::for_arena(expressions);
76        for handle in definitions(expressions, body).iter() {
77            if self.bakes_expression(handle, context) {
78                assert!(fits_in_temporary(context.module, context.info, handle));
79                candidates.insert(handle);
80            }
81        }
82        if candidates.is_empty() {
83            return Ok(());
84        }
85
86        let used = expressions_used(
87            context.module,
88            context.function,
89            continuing,
90            break_if,
91            &candidates,
92        );
93
94        for handle in candidates.iter() {
95            if !used.contains(handle) {
96                continue;
97            }
98            let Some(name) = self.baked_name(handle, context) else {
99                continue;
100            };
101
102            write!(self.out, "{level}")?;
103            self.put_baked_type(handle, context)?;
104            writeln!(self.out, " {name} = {{}};")?;
105
106            self.hoisted_loop_expressions.insert(handle, name);
107        }
108
109        Ok(())
110    }
111}
112
113/// Return the expressions that `block` itself computes values for, in
114/// increasing handle order.
115fn definitions(
116    expressions: &Arena<crate::Expression>,
117    block: &crate::Block,
118) -> HandleSet<crate::Expression> {
119    use crate::Statement as St;
120
121    let mut defined = HandleSet::for_arena(expressions);
122    for statement in block.iter() {
123        match *statement {
124            St::Emit(ref range) => defined.insert_iter(range.clone()),
125            St::Atomic {
126                result: Some(result),
127                ..
128            }
129            | St::Call {
130                result: Some(result),
131                ..
132            }
133            | St::RayQuery {
134                fun: crate::RayQueryFunction::Proceed { result },
135                ..
136            }
137            | St::WorkGroupUniformLoad { result, .. }
138            | St::SubgroupBallot { result, .. }
139            | St::SubgroupBallotFindBit { result, .. }
140            | St::SubgroupGather { result, .. }
141            | St::SubgroupCollectiveOperation { result, .. } => {
142                defined.insert(result);
143            }
144
145            St::Atomic { result: None, .. }
146            | St::Call { result: None, .. }
147            | St::RayQuery {
148                fun:
149                    crate::RayQueryFunction::Initialize { .. }
150                    | crate::RayQueryFunction::GenerateIntersection { .. }
151                    | crate::RayQueryFunction::ConfirmIntersection
152                    | crate::RayQueryFunction::Terminate
153                    | crate::RayQueryFunction::Begin,
154                ..
155            }
156            | St::Block(_)
157            | St::If { .. }
158            | St::Switch { .. }
159            | St::Loop { .. }
160            | St::Break
161            | St::Continue
162            | St::Return { .. }
163            | St::Kill
164            | St::ControlBarrier(_)
165            | St::MemoryBarrier(_)
166            | St::Store { .. }
167            | St::ImageStore { .. }
168            | St::ImageAtomic { .. }
169            | St::RayPipelineFunction(_)
170            | St::HitObject { .. }
171            | St::CooperativeStore { .. }
172            | St::DebugPrintf { .. } => {}
173        }
174    }
175    defined
176}
177
178/// Return the expressions of `function` that the code generated for `block`
179/// and `extra_roots` will refer to, directly or indirectly.
180///
181/// This is wider than what `block` needs the values of, because we do no dead
182/// code elimination: [`Writer::put_block`] writes out a definition for every
183/// expression it bakes, whether or not anything reads it, and that definition
184/// refers to the expression's operands. Hence
185/// [`trace_block_including_emits`] rather than [`trace_block`]. Miss those and
186/// a dead definition would leave its operands un-hoisted, and `continuing`
187/// would re-evaluate them in place - or, for a statement result, reach the
188/// `unreachable!` in [`Writer::put_expression`], which has no inline form to
189/// fall back on.
190///
191/// The search does not continue past an expression in `stop_at`: such an
192/// expression is marked if something refers to it, but the search does not
193/// follow it to its operands. Anything reachable only through it is therefore
194/// left out.
195///
196/// [`trace_block_including_emits`]: crate::compact::functions::FunctionTracer::trace_block_including_emits
197/// [`trace_block`]: crate::compact::functions::FunctionTracer::trace_block
198/// [`Writer::put_block`]: super::writer::Writer::put_block
199/// [`Writer::put_expression`]: super::writer::Writer::put_expression
200fn expressions_used(
201    module: &crate::Module,
202    function: &crate::Function,
203    block: &crate::Block,
204    extra_roots: impl IntoIterator<Item = Handle<crate::Expression>>,
205    stop_at: &HandleSet<crate::Expression>,
206) -> HandleSet<crate::Expression> {
207    let mut module_tracer = ModuleTracer::new(module);
208
209    let mut function_tracer = module_tracer.as_function(function);
210    function_tracer.trace_block_including_emits(block);
211    function_tracer.expressions_used.insert_iter(extra_roots);
212
213    let mut expression_tracer = function_tracer.as_expression();
214    for (handle, expression) in function.expressions.iter().rev() {
215        if expression_tracer.expressions_used.contains(handle) && !stop_at.contains(handle) {
216            expression_tracer.trace_expression(expression);
217        }
218    }
219
220    function_tracer.expressions_used
221}
222
223/// Whether `expression` is the result of a statement.
224///
225/// There is no way to write these inline, so the statement that produces one
226/// always stores it in a temporary, whether or not anything asked for one.
227pub(super) const fn is_statement_result(expression: &crate::Expression) -> bool {
228    use crate::Expression as Ex;
229    match *expression {
230        Ex::CallResult(_)
231        | Ex::AtomicResult { .. }
232        | Ex::WorkGroupUniformLoadResult { .. }
233        | Ex::SubgroupBallotResult
234        | Ex::SubgroupOperationResult { .. }
235        | Ex::RayQueryProceedResult => true,
236
237        Ex::Literal(_)
238        | Ex::Constant(_)
239        | Ex::Override(_)
240        | Ex::ZeroValue(_)
241        | Ex::Compose { .. }
242        | Ex::Access { .. }
243        | Ex::AccessIndex { .. }
244        | Ex::Splat { .. }
245        | Ex::Swizzle { .. }
246        | Ex::FunctionArgument(_)
247        | Ex::GlobalVariable(_)
248        | Ex::LocalVariable(_)
249        | Ex::Load { .. }
250        | Ex::ImageSample { .. }
251        | Ex::ImageLoad { .. }
252        | Ex::ImageQuery { .. }
253        | Ex::Unary { .. }
254        | Ex::Binary { .. }
255        | Ex::Select { .. }
256        | Ex::Derivative { .. }
257        | Ex::Relational { .. }
258        | Ex::Math { .. }
259        | Ex::As { .. }
260        | Ex::Bitcast { .. }
261        | Ex::ArrayLength(_)
262        | Ex::RayQueryVertexPositions { .. }
263        | Ex::RayQueryGetIntersection { .. }
264        | Ex::HitObjectQuery { .. }
265        | Ex::CooperativeLoad { .. }
266        | Ex::CooperativeMultiplyAdd { .. } => false,
267    }
268}
269
270/// Whether a value of `handle`'s type can be held in a default-initialized
271/// local temporary.
272fn fits_in_temporary(
273    module: &crate::Module,
274    info: &crate::valid::FunctionInfo,
275    handle: Handle<crate::Expression>,
276) -> bool {
277    use crate::TypeInner as Ti;
278    match info[handle].ty {
279        TypeResolution::Handle(ty) => matches!(
280            module.types[ty].inner,
281            Ti::Scalar(_)
282                | Ti::Vector { .. }
283                | Ti::Matrix { .. }
284                | Ti::Array {
285                    size: crate::ArraySize::Constant(_),
286                    ..
287                }
288                | Ti::Struct { .. }
289                | Ti::CooperativeMatrix { .. }
290        ),
291        TypeResolution::Value(
292            Ti::Scalar(_) | Ti::Vector { .. } | Ti::Matrix { .. } | Ti::CooperativeMatrix { .. },
293        ) => true,
294        TypeResolution::Value(_) => false,
295    }
296}