naga/compact/
mod.rs

1mod expressions;
2mod functions;
3mod handle_set_map;
4mod statements;
5mod types;
6
7use alloc::vec::Vec;
8
9use crate::{
10    arena::{self, HandleSet},
11    compact::functions::FunctionTracer,
12    ir,
13};
14use handle_set_map::HandleMap;
15
16#[cfg(test)]
17use alloc::{format, string::ToString};
18
19/// Configuration option for [`compact`]. See [`compact`] for details.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub enum KeepUnused {
22    No,
23    Yes,
24}
25
26impl From<KeepUnused> for bool {
27    fn from(keep_unused: KeepUnused) -> Self {
28        match keep_unused {
29            KeepUnused::No => false,
30            KeepUnused::Yes => true,
31        }
32    }
33}
34
35/// Remove most unused objects from `module`, which must be valid.
36///
37/// Always removes the following unused objects:
38/// - anonymous types, overrides, and constants
39/// - abstract-typed constants
40/// - expressions
41///
42/// If `keep_unused` is `Yes`, the following are never considered unused,
43/// otherwise, they will also be removed if unused:
44/// - functions
45/// - global variables
46/// - named types and overrides
47///
48/// The following are never removed:
49/// - named constants with a concrete type
50/// - special types
51/// - entry points
52/// - within an entry point or a used function:
53///     - arguments
54///     - local variables
55///     - named expressions
56///
57/// After removing items according to the rules above, all handles in the
58/// remaining objects are adjusted as necessary. When `KeepUnused` is `Yes`, the
59/// resulting module should have all the named objects (except abstract-typed
60/// constants) present in the original, and those objects should be functionally
61/// identical. When `KeepUnused` is `No`, the resulting module should have the
62/// entry points present in the original, and those entry points should be
63/// functionally identical.
64///
65/// # Panics
66///
67/// If `module` would not pass validation, this may panic.
68pub fn compact(module: &mut crate::Module, keep_unused: KeepUnused) {
69    // The trickiest part of compaction is determining what is used and what is
70    // not. Once we have computed that correctly, it's easy enough to call
71    // `retain_mut` on each arena, drop unused elements, and fix up the handles
72    // in what's left.
73    //
74    // For every compactable arena in a `Module`, whether global to the `Module`
75    // or local to a function or entry point, the `ModuleTracer` type holds a
76    // bitmap indicating which elements of that arena are used. Our task is to
77    // populate those bitmaps correctly.
78    //
79    // First, we mark everything that is considered used by definition, as
80    // described in this function's documentation.
81    //
82    // Since functions and entry points are considered used by definition, we
83    // traverse their statement trees, and mark the referents of all handles
84    // appearing in those statements as used.
85    //
86    // Once we've marked which elements of an arena are referred to directly by
87    // handles elsewhere (for example, which of a function's expressions are
88    // referred to by handles in its body statements), we can mark all the other
89    // arena elements that are used indirectly in a single pass, traversing the
90    // arena from back to front. Since Naga allows arena elements to refer only
91    // to prior elements, we know that by the time we reach an element, all
92    // other elements that could possibly refer to it have already been visited.
93    // Thus, if the present element has not been marked as used, then it is
94    // definitely unused, and compaction can remove it. Otherwise, the element
95    // is used and must be retained, so we must mark everything it refers to.
96    //
97    // The final step is to mark the global expressions and types, which must be
98    // traversed simultaneously; see `ModuleTracer::type_expression_tandem`'s
99    // documentation for details.
100    //
101    // # A definition and a rule of thumb
102    //
103    // In this module, to "trace" something is to mark everything else it refers
104    // to as used, on the assumption that the thing itself is used. For example,
105    // to trace an `Expression` is to mark its subexpressions as used, as well
106    // as any types, constants, overrides, etc. that it refers to. This is what
107    // `ExpressionTracer::trace_expression` does.
108    //
109    // Given that we we want to visit each thing only once (to keep compaction
110    // linear in the size of the module), this definition of "trace" implies
111    // that things that are not "used by definition" must be marked as used
112    // *before* we trace them.
113    //
114    // Thus, whenever you are marking something as used, it's a good idea to ask
115    // yourself how you know that thing will be traced in the future. If you're
116    // not sure, then you could be marking it too late to be noticed. The thing
117    // itself will be retained by compaction, but since it will not be traced,
118    // anything it refers to could be compacted away.
119    let mut module_tracer = ModuleTracer::new(module);
120
121    // Observe what each entry point actually uses.
122    log::trace!("tracing entry points");
123    let entry_point_maps = module
124        .entry_points
125        .iter()
126        .map(|e| {
127            log::trace!("tracing entry point {:?}", e.function.name);
128
129            if let Some(sizes) = e.workgroup_size_overrides {
130                for size in sizes.iter().filter_map(|x| *x) {
131                    module_tracer.global_expressions_used.insert(size);
132                }
133            }
134
135            let mut used = module_tracer.as_function(&e.function);
136            used.trace();
137            FunctionMap::from(used)
138        })
139        .collect::<Vec<_>>();
140
141    // Observe which types, constant expressions, constants, and expressions
142    // each function uses, and produce maps for each function from
143    // pre-compaction to post-compaction expression handles.
144    //
145    // The function tracing logic here works in conjunction with
146    // `FunctionTracer::trace_call`, which, when tracing a `Statement::Call`
147    // to a function not already identified as used, adds the called function
148    // to both `functions_used` and `functions_pending`.
149    //
150    // Called functions are required to appear before their callers in the
151    // functions arena (recursion is disallowed). We have already traced the
152    // entry point(s) and added any functions called directly by the entry
153    // point(s) to `functions_pending`. We proceed by repeatedly tracing the
154    // last function in `functions_pending`. By an inductive argument, any
155    // functions after the last function in `functions_pending` must be unused.
156    //
157    // When `KeepUnused` is active, we simply mark all functions as pending,
158    // and then trace all of them.
159    log::trace!("tracing functions");
160    let mut function_maps = HandleMap::with_capacity(module.functions.len());
161    if keep_unused.into() {
162        module_tracer.functions_used.add_all();
163        module_tracer.functions_pending.add_all();
164    }
165    while let Some(handle) = module_tracer.functions_pending.pop() {
166        let function = &module.functions[handle];
167        log::trace!("tracing function {function:?}");
168        let mut function_tracer = module_tracer.as_function(function);
169        function_tracer.trace();
170        function_maps.insert(handle, FunctionMap::from(function_tracer));
171    }
172
173    // We treat all special types as used by definition.
174    log::trace!("tracing special types");
175    module_tracer.trace_special_types(&module.special_types);
176
177    log::trace!("tracing global variables");
178    if keep_unused.into() {
179        module_tracer.global_variables_used.add_all();
180    }
181    for global in module_tracer.global_variables_used.iter() {
182        log::trace!("tracing global {:?}", module.global_variables[global].name);
183        module_tracer
184            .types_used
185            .insert(module.global_variables[global].ty);
186        if let Some(init) = module.global_variables[global].init {
187            module_tracer.global_expressions_used.insert(init);
188        }
189    }
190
191    // We treat all named constants as used by definition, unless they have an
192    // abstract type as we do not want those reaching the validator.
193    log::trace!("tracing named constants");
194    for (handle, constant) in module.constants.iter() {
195        if constant.name.is_none() || module.types[constant.ty].inner.is_abstract(&module.types) {
196            continue;
197        }
198
199        log::trace!("tracing constant {:?}", constant.name.as_ref().unwrap());
200        module_tracer.constants_used.insert(handle);
201        module_tracer.types_used.insert(constant.ty);
202        module_tracer.global_expressions_used.insert(constant.init);
203    }
204
205    if keep_unused.into() {
206        // Treat all named overrides as used.
207        for (handle, r#override) in module.overrides.iter() {
208            if r#override.name.is_some() && module_tracer.overrides_used.insert(handle) {
209                module_tracer.types_used.insert(r#override.ty);
210                if let Some(init) = r#override.init {
211                    module_tracer.global_expressions_used.insert(init);
212                }
213            }
214        }
215
216        // Treat all named types as used.
217        for (handle, ty) in module.types.iter() {
218            if ty.name.is_some() {
219                module_tracer.types_used.insert(handle);
220            }
221        }
222    }
223
224    module_tracer.type_expression_tandem();
225
226    // Now that we know what is used and what is never touched,
227    // produce maps from the `Handle`s that appear in `module` now to
228    // the corresponding `Handle`s that will refer to the same items
229    // in the compacted module.
230    let module_map = ModuleMap::from(module_tracer);
231
232    // Drop unused types from the type arena.
233    //
234    // `FastIndexSet`s don't have an underlying Vec<T> that we can
235    // steal, compact in place, and then rebuild the `FastIndexSet`
236    // from. So we have to rebuild the type arena from scratch.
237    log::trace!("compacting types");
238    let mut new_types = arena::UniqueArena::new();
239    for (old_handle, mut ty, span) in module.types.drain_all() {
240        if let Some(expected_new_handle) = module_map.types.try_adjust(old_handle) {
241            module_map.adjust_type(&mut ty);
242            let actual_new_handle = new_types.insert(ty, span);
243            assert_eq!(actual_new_handle, expected_new_handle);
244        }
245    }
246    module.types = new_types;
247    log::trace!("adjusting special types");
248    module_map.adjust_special_types(&mut module.special_types);
249
250    // Drop unused constant expressions, reusing existing storage.
251    log::trace!("adjusting constant expressions");
252    module.global_expressions.retain_mut(|handle, expr| {
253        if module_map.global_expressions.used(handle) {
254            module_map.adjust_expression(expr, &module_map.global_expressions);
255            true
256        } else {
257            false
258        }
259    });
260
261    // Drop unused constants in place, reusing existing storage.
262    log::trace!("adjusting constants");
263    module.constants.retain_mut(|handle, constant| {
264        if module_map.constants.used(handle) {
265            module_map.types.adjust(&mut constant.ty);
266            module_map.global_expressions.adjust(&mut constant.init);
267            true
268        } else {
269            false
270        }
271    });
272
273    // Drop unused overrides in place, reusing existing storage.
274    log::trace!("adjusting overrides");
275    module.overrides.retain_mut(|handle, r#override| {
276        if module_map.overrides.used(handle) {
277            module_map.types.adjust(&mut r#override.ty);
278            if let Some(ref mut init) = r#override.init {
279                module_map.global_expressions.adjust(init);
280            }
281            true
282        } else {
283            false
284        }
285    });
286
287    // Adjust workgroup_size_overrides
288    log::trace!("adjusting workgroup_size_overrides");
289    for e in module.entry_points.iter_mut() {
290        if let Some(sizes) = e.workgroup_size_overrides.as_mut() {
291            for size in sizes.iter_mut() {
292                if let Some(expr) = size.as_mut() {
293                    module_map.global_expressions.adjust(expr);
294                }
295            }
296        }
297    }
298
299    // Drop unused global variables, reusing existing storage.
300    // Adjust used global variables' types and initializers.
301    log::trace!("adjusting global variables");
302    module.global_variables.retain_mut(|handle, global| {
303        if module_map.globals.used(handle) {
304            log::trace!("retaining global variable {:?}", global.name);
305            module_map.types.adjust(&mut global.ty);
306            if let Some(ref mut init) = global.init {
307                module_map.global_expressions.adjust(init);
308            }
309            true
310        } else {
311            log::trace!("dropping global variable {:?}", global.name);
312            false
313        }
314    });
315
316    // Adjust doc comments
317    if let Some(ref mut doc_comments) = module.doc_comments {
318        module_map.adjust_doc_comments(doc_comments.as_mut());
319    }
320
321    // Temporary storage to help us reuse allocations of existing
322    // named expression tables.
323    let mut reused_named_expressions = crate::NamedExpressions::default();
324
325    // Drop unused functions. Compact and adjust used functions.
326    module.functions.retain_mut(|handle, function| {
327        if let Some(map) = function_maps.get(handle) {
328            log::trace!("retaining and compacting function {:?}", function.name);
329            map.compact(function, &module_map, &mut reused_named_expressions);
330            true
331        } else {
332            log::trace!("dropping function {:?}", function.name);
333            false
334        }
335    });
336
337    // Compact each entry point.
338    for (entry, map) in module.entry_points.iter_mut().zip(entry_point_maps.iter()) {
339        log::trace!("compacting entry point {:?}", entry.function.name);
340        map.compact(
341            &mut entry.function,
342            &module_map,
343            &mut reused_named_expressions,
344        );
345    }
346}
347
348struct ModuleTracer<'module> {
349    module: &'module crate::Module,
350
351    /// The subset of functions in `functions_used` that have not yet been
352    /// traced.
353    functions_pending: HandleSet<crate::Function>,
354
355    functions_used: HandleSet<crate::Function>,
356    types_used: HandleSet<crate::Type>,
357    global_variables_used: HandleSet<crate::GlobalVariable>,
358    constants_used: HandleSet<crate::Constant>,
359    overrides_used: HandleSet<crate::Override>,
360    global_expressions_used: HandleSet<crate::Expression>,
361}
362
363impl<'module> ModuleTracer<'module> {
364    fn new(module: &'module crate::Module) -> Self {
365        Self {
366            module,
367            functions_pending: HandleSet::for_arena(&module.functions),
368            functions_used: HandleSet::for_arena(&module.functions),
369            types_used: HandleSet::for_arena(&module.types),
370            global_variables_used: HandleSet::for_arena(&module.global_variables),
371            constants_used: HandleSet::for_arena(&module.constants),
372            overrides_used: HandleSet::for_arena(&module.overrides),
373            global_expressions_used: HandleSet::for_arena(&module.global_expressions),
374        }
375    }
376
377    fn trace_special_types(&mut self, special_types: &crate::SpecialTypes) {
378        let crate::SpecialTypes {
379            ref ray_desc,
380            ref ray_intersection,
381            ref ray_vertex_return,
382            ref predeclared_types,
383            ref external_texture_params,
384            ref external_texture_transfer_function,
385        } = *special_types;
386
387        if let Some(ray_desc) = *ray_desc {
388            self.types_used.insert(ray_desc);
389        }
390        if let Some(ray_intersection) = *ray_intersection {
391            self.types_used.insert(ray_intersection);
392        }
393        if let Some(ray_vertex_return) = *ray_vertex_return {
394            self.types_used.insert(ray_vertex_return);
395        }
396        // The `external_texture_params` type is generated purely as a
397        // convenience to the backends. While it will never actually be used in
398        // the IR, it must be marked as used so that it survives compaction.
399        if let Some(external_texture_params) = *external_texture_params {
400            self.types_used.insert(external_texture_params);
401        }
402        if let Some(external_texture_transfer_function) = *external_texture_transfer_function {
403            self.types_used.insert(external_texture_transfer_function);
404        }
405        for (_, &handle) in predeclared_types {
406            self.types_used.insert(handle);
407        }
408    }
409
410    /// Traverse types and global expressions in tandem to determine which are used.
411    ///
412    /// Assuming that all types and global expressions used by other parts of
413    /// the module have been added to [`types_used`] and
414    /// [`global_expressions_used`], expand those sets to include all types and
415    /// global expressions reachable from those.
416    ///
417    /// [`types_used`]: ModuleTracer::types_used
418    /// [`global_expressions_used`]: ModuleTracer::global_expressions_used
419    fn type_expression_tandem(&mut self) {
420        // For each type T, compute the latest global expression E that T and
421        // its predecessors refer to. Given the ordering rules on types and
422        // global expressions in valid modules, we can do this with a single
423        // forward scan of the type arena. The rules further imply that T can
424        // only be referred to by expressions after E.
425        let mut max_dep = Vec::with_capacity(self.module.types.len());
426        let mut previous = None;
427        for (_handle, ty) in self.module.types.iter() {
428            previous = core::cmp::max(
429                previous,
430                match ty.inner {
431                    crate::TypeInner::Array { size, .. }
432                    | crate::TypeInner::BindingArray { size, .. } => match size {
433                        crate::ArraySize::Constant(_) | crate::ArraySize::Dynamic => None,
434                        crate::ArraySize::Pending(handle) => self.module.overrides[handle].init,
435                    },
436                    _ => None,
437                },
438            );
439            max_dep.push(previous);
440        }
441
442        // Visit types and global expressions from youngest to oldest.
443        //
444        // The outer loop visits types. Before visiting each type, the inner
445        // loop ensures that all global expressions that could possibly refer to
446        // it have been visited. And since the inner loop stop at the latest
447        // expression that the type could possibly refer to, we know that we
448        // have previously visited any types that might refer to each expression
449        // we visit.
450        //
451        // This lets us assume that any type or expression that is *not* marked
452        // as used by the time we visit it is genuinely unused, and can be
453        // ignored.
454        let mut exprs = self.module.global_expressions.iter().rev().peekable();
455
456        for ((ty_handle, ty), dep) in self.module.types.iter().zip(max_dep).rev() {
457            while let Some((expr_handle, expr)) = exprs.next_if(|&(h, _)| Some(h) > dep) {
458                if self.global_expressions_used.contains(expr_handle) {
459                    self.as_const_expression().trace_expression(expr);
460                }
461            }
462            if self.types_used.contains(ty_handle) {
463                self.as_type().trace_type(ty);
464            }
465        }
466        // Visit any remaining expressions.
467        for (expr_handle, expr) in exprs {
468            if self.global_expressions_used.contains(expr_handle) {
469                self.as_const_expression().trace_expression(expr);
470            }
471        }
472    }
473
474    fn as_type(&mut self) -> types::TypeTracer<'_> {
475        types::TypeTracer {
476            overrides: &self.module.overrides,
477            types_used: &mut self.types_used,
478            expressions_used: &mut self.global_expressions_used,
479            overrides_used: &mut self.overrides_used,
480        }
481    }
482
483    fn as_const_expression(&mut self) -> expressions::ExpressionTracer<'_> {
484        expressions::ExpressionTracer {
485            constants: &self.module.constants,
486            overrides: &self.module.overrides,
487            expressions: &self.module.global_expressions,
488            types_used: &mut self.types_used,
489            global_variables_used: &mut self.global_variables_used,
490            constants_used: &mut self.constants_used,
491            expressions_used: &mut self.global_expressions_used,
492            overrides_used: &mut self.overrides_used,
493            global_expressions_used: None,
494        }
495    }
496
497    pub fn as_function<'tracer>(
498        &'tracer mut self,
499        function: &'tracer crate::Function,
500    ) -> FunctionTracer<'tracer> {
501        FunctionTracer {
502            function,
503            constants: &self.module.constants,
504            overrides: &self.module.overrides,
505            functions_pending: &mut self.functions_pending,
506            functions_used: &mut self.functions_used,
507            types_used: &mut self.types_used,
508            global_variables_used: &mut self.global_variables_used,
509            constants_used: &mut self.constants_used,
510            overrides_used: &mut self.overrides_used,
511            global_expressions_used: &mut self.global_expressions_used,
512            expressions_used: HandleSet::for_arena(&function.expressions),
513        }
514    }
515}
516
517struct ModuleMap {
518    functions: HandleMap<crate::Function>,
519    types: HandleMap<crate::Type>,
520    globals: HandleMap<crate::GlobalVariable>,
521    constants: HandleMap<crate::Constant>,
522    overrides: HandleMap<crate::Override>,
523    global_expressions: HandleMap<crate::Expression>,
524}
525
526impl From<ModuleTracer<'_>> for ModuleMap {
527    fn from(used: ModuleTracer) -> Self {
528        ModuleMap {
529            functions: HandleMap::from_set(used.functions_used),
530            types: HandleMap::from_set(used.types_used),
531            globals: HandleMap::from_set(used.global_variables_used),
532            constants: HandleMap::from_set(used.constants_used),
533            overrides: HandleMap::from_set(used.overrides_used),
534            global_expressions: HandleMap::from_set(used.global_expressions_used),
535        }
536    }
537}
538
539impl ModuleMap {
540    fn adjust_special_types(&self, special: &mut crate::SpecialTypes) {
541        let crate::SpecialTypes {
542            ref mut ray_desc,
543            ref mut ray_intersection,
544            ref mut ray_vertex_return,
545            ref mut predeclared_types,
546            ref mut external_texture_params,
547            ref mut external_texture_transfer_function,
548        } = *special;
549
550        if let Some(ref mut ray_desc) = *ray_desc {
551            self.types.adjust(ray_desc);
552        }
553        if let Some(ref mut ray_intersection) = *ray_intersection {
554            self.types.adjust(ray_intersection);
555        }
556
557        if let Some(ref mut ray_vertex_return) = *ray_vertex_return {
558            self.types.adjust(ray_vertex_return);
559        }
560
561        if let Some(ref mut external_texture_params) = *external_texture_params {
562            self.types.adjust(external_texture_params);
563        }
564
565        if let Some(ref mut external_texture_transfer_function) =
566            *external_texture_transfer_function
567        {
568            self.types.adjust(external_texture_transfer_function);
569        }
570
571        for handle in predeclared_types.values_mut() {
572            self.types.adjust(handle);
573        }
574    }
575
576    fn adjust_doc_comments(&self, doc_comments: &mut ir::DocComments) {
577        let crate::DocComments {
578            module: _,
579            types: ref mut doc_types,
580            struct_members: ref mut doc_struct_members,
581            entry_points: _,
582            functions: ref mut doc_functions,
583            constants: ref mut doc_constants,
584            global_variables: ref mut doc_globals,
585        } = *doc_comments;
586        log::trace!("adjusting doc comments for types");
587        for (mut ty, doc_comment) in core::mem::take(doc_types) {
588            if !self.types.used(ty) {
589                continue;
590            }
591            self.types.adjust(&mut ty);
592            doc_types.insert(ty, doc_comment);
593        }
594        log::trace!("adjusting doc comments for struct members");
595        for ((mut ty, index), doc_comment) in core::mem::take(doc_struct_members) {
596            if !self.types.used(ty) {
597                continue;
598            }
599            self.types.adjust(&mut ty);
600            doc_struct_members.insert((ty, index), doc_comment);
601        }
602        log::trace!("adjusting doc comments for functions");
603        for (mut handle, doc_comment) in core::mem::take(doc_functions) {
604            if !self.functions.used(handle) {
605                continue;
606            }
607            self.functions.adjust(&mut handle);
608            doc_functions.insert(handle, doc_comment);
609        }
610        log::trace!("adjusting doc comments for constants");
611        for (mut constant, doc_comment) in core::mem::take(doc_constants) {
612            if !self.constants.used(constant) {
613                continue;
614            }
615            self.constants.adjust(&mut constant);
616            doc_constants.insert(constant, doc_comment);
617        }
618        log::trace!("adjusting doc comments for globals");
619        for (mut handle, doc_comment) in core::mem::take(doc_globals) {
620            if !self.globals.used(handle) {
621                continue;
622            }
623            self.globals.adjust(&mut handle);
624            doc_globals.insert(handle, doc_comment);
625        }
626    }
627}
628
629struct FunctionMap {
630    expressions: HandleMap<crate::Expression>,
631}
632
633impl From<FunctionTracer<'_>> for FunctionMap {
634    fn from(used: FunctionTracer) -> Self {
635        FunctionMap {
636            expressions: HandleMap::from_set(used.expressions_used),
637        }
638    }
639}
640
641#[test]
642fn type_expression_interdependence() {
643    let mut module: crate::Module = Default::default();
644    let u32 = module.types.insert(
645        crate::Type {
646            name: None,
647            inner: crate::TypeInner::Scalar(crate::Scalar {
648                kind: crate::ScalarKind::Uint,
649                width: 4,
650            }),
651        },
652        crate::Span::default(),
653    );
654    let expr = module.global_expressions.append(
655        crate::Expression::Literal(crate::Literal::U32(0)),
656        crate::Span::default(),
657    );
658    let type_needs_expression = |module: &mut crate::Module, handle| {
659        let override_handle = module.overrides.append(
660            crate::Override {
661                name: None,
662                id: None,
663                ty: u32,
664                init: Some(handle),
665            },
666            crate::Span::default(),
667        );
668        module.types.insert(
669            crate::Type {
670                name: None,
671                inner: crate::TypeInner::Array {
672                    base: u32,
673                    size: crate::ArraySize::Pending(override_handle),
674                    stride: 4,
675                },
676            },
677            crate::Span::default(),
678        )
679    };
680    let expression_needs_type = |module: &mut crate::Module, handle| {
681        module
682            .global_expressions
683            .append(crate::Expression::ZeroValue(handle), crate::Span::default())
684    };
685    let expression_needs_expression = |module: &mut crate::Module, handle| {
686        module.global_expressions.append(
687            crate::Expression::Load { pointer: handle },
688            crate::Span::default(),
689        )
690    };
691    let type_needs_type = |module: &mut crate::Module, handle| {
692        module.types.insert(
693            crate::Type {
694                name: None,
695                inner: crate::TypeInner::Array {
696                    base: handle,
697                    size: crate::ArraySize::Dynamic,
698                    stride: 0,
699                },
700            },
701            crate::Span::default(),
702        )
703    };
704    let mut type_name_counter = 0;
705    let mut type_needed = |module: &mut crate::Module, handle| {
706        let name = Some(format!("type{type_name_counter}"));
707        type_name_counter += 1;
708        module.types.insert(
709            crate::Type {
710                name,
711                inner: crate::TypeInner::Array {
712                    base: handle,
713                    size: crate::ArraySize::Dynamic,
714                    stride: 0,
715                },
716            },
717            crate::Span::default(),
718        )
719    };
720    let mut override_name_counter = 0;
721    let mut expression_needed = |module: &mut crate::Module, handle| {
722        let name = Some(format!("override{override_name_counter}"));
723        override_name_counter += 1;
724        module.overrides.append(
725            crate::Override {
726                name,
727                id: None,
728                ty: u32,
729                init: Some(handle),
730            },
731            crate::Span::default(),
732        )
733    };
734    let cmp_modules = |mod0: &crate::Module, mod1: &crate::Module| {
735        (mod0.types.iter().collect::<Vec<_>>() == mod1.types.iter().collect::<Vec<_>>())
736            && (mod0.global_expressions.iter().collect::<Vec<_>>()
737                == mod1.global_expressions.iter().collect::<Vec<_>>())
738    };
739    // borrow checker breaks without the tmp variables as of Rust 1.83.0
740    let expr_end = type_needs_expression(&mut module, expr);
741    let ty_trace = type_needs_type(&mut module, expr_end);
742    let expr_init = expression_needs_type(&mut module, ty_trace);
743    expression_needed(&mut module, expr_init);
744    let ty_end = expression_needs_type(&mut module, u32);
745    let expr_trace = expression_needs_expression(&mut module, ty_end);
746    let ty_init = type_needs_expression(&mut module, expr_trace);
747    type_needed(&mut module, ty_init);
748    let untouched = module.clone();
749    compact(&mut module, KeepUnused::Yes);
750    assert!(cmp_modules(&module, &untouched));
751    let unused_expr = module.global_expressions.append(
752        crate::Expression::Literal(crate::Literal::U32(1)),
753        crate::Span::default(),
754    );
755    type_needs_expression(&mut module, unused_expr);
756    assert!(!cmp_modules(&module, &untouched));
757    compact(&mut module, KeepUnused::Yes);
758    assert!(cmp_modules(&module, &untouched));
759}
760
761#[test]
762fn array_length_override() {
763    let mut module: crate::Module = Default::default();
764    let ty_bool = module.types.insert(
765        crate::Type {
766            name: None,
767            inner: crate::TypeInner::Scalar(crate::Scalar::BOOL),
768        },
769        crate::Span::default(),
770    );
771    let ty_u32 = module.types.insert(
772        crate::Type {
773            name: None,
774            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
775        },
776        crate::Span::default(),
777    );
778    let one = module.global_expressions.append(
779        crate::Expression::Literal(crate::Literal::U32(1)),
780        crate::Span::default(),
781    );
782    let _unused_override = module.overrides.append(
783        crate::Override {
784            name: None,
785            id: Some(40),
786            ty: ty_u32,
787            init: None,
788        },
789        crate::Span::default(),
790    );
791    let o = module.overrides.append(
792        crate::Override {
793            name: None,
794            id: Some(42),
795            ty: ty_u32,
796            init: Some(one),
797        },
798        crate::Span::default(),
799    );
800    let _ty_array = module.types.insert(
801        crate::Type {
802            name: Some("array<bool, o>".to_string()),
803            inner: crate::TypeInner::Array {
804                base: ty_bool,
805                size: crate::ArraySize::Pending(o),
806                stride: 4,
807            },
808        },
809        crate::Span::default(),
810    );
811
812    let mut validator = super::valid::Validator::new(
813        super::valid::ValidationFlags::all(),
814        super::valid::Capabilities::all(),
815    );
816
817    assert!(validator.validate(&module).is_ok());
818    compact(&mut module, KeepUnused::Yes);
819    assert!(validator.validate(&module).is_ok());
820}
821
822/// Test mutual references between types and expressions via override
823/// lengths.
824#[test]
825fn array_length_override_mutual() {
826    use crate::Expression as Ex;
827    use crate::Scalar as Sc;
828    use crate::TypeInner as Ti;
829
830    let nowhere = crate::Span::default();
831    let mut module = crate::Module::default();
832    let ty_u32 = module.types.insert(
833        crate::Type {
834            name: None,
835            inner: Ti::Scalar(Sc::U32),
836        },
837        nowhere,
838    );
839
840    // This type is only referred to by the override's init
841    // expression, so if we visit that too early, this type will be
842    // removed incorrectly.
843    let ty_i32 = module.types.insert(
844        crate::Type {
845            name: None,
846            inner: Ti::Scalar(Sc::I32),
847        },
848        nowhere,
849    );
850
851    // An override that the other override's init can refer to.
852    let first_override = module.overrides.append(
853        crate::Override {
854            name: None, // so it is not considered used by definition
855            id: Some(41),
856            ty: ty_i32,
857            init: None,
858        },
859        nowhere,
860    );
861
862    // Initializer expression for the override:
863    //
864    //     (first_override + 0) as u32
865    //
866    // The `first_override` makes it an override expression; the `0`
867    // gets a use of `ty_i32` in there; and the `as` makes it match
868    // the type of `second_override` without actually making
869    // `second_override` point at `ty_i32` directly.
870    let first_override_expr = module
871        .global_expressions
872        .append(Ex::Override(first_override), nowhere);
873    let zero = module
874        .global_expressions
875        .append(Ex::ZeroValue(ty_i32), nowhere);
876    let sum = module.global_expressions.append(
877        Ex::Binary {
878            op: crate::BinaryOperator::Add,
879            left: first_override_expr,
880            right: zero,
881        },
882        nowhere,
883    );
884    let init = module.global_expressions.append(
885        Ex::As {
886            expr: sum,
887            kind: crate::ScalarKind::Uint,
888            convert: None,
889        },
890        nowhere,
891    );
892
893    // Override that serves as the array's length.
894    let second_override = module.overrides.append(
895        crate::Override {
896            name: None, // so it is not considered used by definition
897            id: Some(42),
898            ty: ty_u32,
899            init: Some(init),
900        },
901        nowhere,
902    );
903
904    // Array type that uses the overload as its length.
905    // Since this is named, it is considered used by definition.
906    let _ty_array = module.types.insert(
907        crate::Type {
908            name: Some("delicious_array".to_string()),
909            inner: Ti::Array {
910                base: ty_u32,
911                size: crate::ArraySize::Pending(second_override),
912                stride: 4,
913            },
914        },
915        nowhere,
916    );
917
918    let mut validator = super::valid::Validator::new(
919        super::valid::ValidationFlags::all(),
920        super::valid::Capabilities::all(),
921    );
922
923    assert!(validator.validate(&module).is_ok());
924    compact(&mut module, KeepUnused::Yes);
925    assert!(validator.validate(&module).is_ok());
926}
927
928#[test]
929fn array_length_expression() {
930    let mut module: crate::Module = Default::default();
931    let ty_u32 = module.types.insert(
932        crate::Type {
933            name: None,
934            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
935        },
936        crate::Span::default(),
937    );
938    let _unused_zero = module.global_expressions.append(
939        crate::Expression::Literal(crate::Literal::U32(0)),
940        crate::Span::default(),
941    );
942    let one = module.global_expressions.append(
943        crate::Expression::Literal(crate::Literal::U32(1)),
944        crate::Span::default(),
945    );
946    let override_one = module.overrides.append(
947        crate::Override {
948            name: None,
949            id: None,
950            ty: ty_u32,
951            init: Some(one),
952        },
953        crate::Span::default(),
954    );
955    let _ty_array = module.types.insert(
956        crate::Type {
957            name: Some("array<u32, 1>".to_string()),
958            inner: crate::TypeInner::Array {
959                base: ty_u32,
960                size: crate::ArraySize::Pending(override_one),
961                stride: 4,
962            },
963        },
964        crate::Span::default(),
965    );
966
967    let mut validator = super::valid::Validator::new(
968        super::valid::ValidationFlags::all(),
969        super::valid::Capabilities::all(),
970    );
971
972    assert!(validator.validate(&module).is_ok());
973    compact(&mut module, KeepUnused::Yes);
974    assert!(validator.validate(&module).is_ok());
975}
976
977#[test]
978fn global_expression_override() {
979    let mut module: crate::Module = Default::default();
980    let ty_u32 = module.types.insert(
981        crate::Type {
982            name: None,
983            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
984        },
985        crate::Span::default(),
986    );
987
988    // This will only be retained if we trace the initializers
989    // of overrides referred to by `Expression::Override`
990    // in global expressions.
991    let expr1 = module.global_expressions.append(
992        crate::Expression::Literal(crate::Literal::U32(1)),
993        crate::Span::default(),
994    );
995
996    // This will only be traced via a global `Expression::Override`.
997    let o = module.overrides.append(
998        crate::Override {
999            name: None,
1000            id: Some(42),
1001            ty: ty_u32,
1002            init: Some(expr1),
1003        },
1004        crate::Span::default(),
1005    );
1006
1007    // This is retained by _p.
1008    let expr2 = module
1009        .global_expressions
1010        .append(crate::Expression::Override(o), crate::Span::default());
1011
1012    // Since this is named, it will be retained.
1013    let _p = module.overrides.append(
1014        crate::Override {
1015            name: Some("p".to_string()),
1016            id: None,
1017            ty: ty_u32,
1018            init: Some(expr2),
1019        },
1020        crate::Span::default(),
1021    );
1022
1023    let mut validator = super::valid::Validator::new(
1024        super::valid::ValidationFlags::all(),
1025        super::valid::Capabilities::all(),
1026    );
1027
1028    assert!(validator.validate(&module).is_ok());
1029    compact(&mut module, KeepUnused::Yes);
1030    assert!(validator.validate(&module).is_ok());
1031}
1032
1033#[test]
1034fn local_expression_override() {
1035    let mut module: crate::Module = Default::default();
1036    let ty_u32 = module.types.insert(
1037        crate::Type {
1038            name: None,
1039            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
1040        },
1041        crate::Span::default(),
1042    );
1043
1044    // This will only be retained if we trace the initializers
1045    // of overrides referred to by `Expression::Override` in a function.
1046    let expr1 = module.global_expressions.append(
1047        crate::Expression::Literal(crate::Literal::U32(1)),
1048        crate::Span::default(),
1049    );
1050
1051    // This will be removed by compaction.
1052    let _unused_override = module.overrides.append(
1053        crate::Override {
1054            name: None,
1055            id: Some(41),
1056            ty: ty_u32,
1057            init: None,
1058        },
1059        crate::Span::default(),
1060    );
1061
1062    // This will only be traced via an `Expression::Override` in a function.
1063    let o = module.overrides.append(
1064        crate::Override {
1065            name: None,
1066            id: Some(42),
1067            ty: ty_u32,
1068            init: Some(expr1),
1069        },
1070        crate::Span::default(),
1071    );
1072
1073    let mut fun = crate::Function {
1074        result: Some(crate::FunctionResult {
1075            ty: ty_u32,
1076            binding: None,
1077        }),
1078        ..crate::Function::default()
1079    };
1080
1081    // This is used by the `Return` statement.
1082    let o_expr = fun
1083        .expressions
1084        .append(crate::Expression::Override(o), crate::Span::default());
1085    fun.body.push(
1086        crate::Statement::Return {
1087            value: Some(o_expr),
1088        },
1089        crate::Span::default(),
1090    );
1091
1092    module.functions.append(fun, crate::Span::default());
1093
1094    let mut validator = super::valid::Validator::new(
1095        super::valid::ValidationFlags::all(),
1096        super::valid::Capabilities::all(),
1097    );
1098
1099    assert!(validator.validate(&module).is_ok());
1100    compact(&mut module, KeepUnused::Yes);
1101    assert!(validator.validate(&module).is_ok());
1102}
1103
1104#[test]
1105fn unnamed_constant_type() {
1106    let mut module = crate::Module::default();
1107    let nowhere = crate::Span::default();
1108
1109    // This type is used only by the unnamed constant.
1110    let ty_u32 = module.types.insert(
1111        crate::Type {
1112            name: None,
1113            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
1114        },
1115        nowhere,
1116    );
1117
1118    // This type is used by the named constant.
1119    let ty_vec_u32 = module.types.insert(
1120        crate::Type {
1121            name: None,
1122            inner: crate::TypeInner::Vector {
1123                size: crate::VectorSize::Bi,
1124                scalar: crate::Scalar::U32,
1125            },
1126        },
1127        nowhere,
1128    );
1129
1130    let unnamed_init = module
1131        .global_expressions
1132        .append(crate::Expression::Literal(crate::Literal::U32(0)), nowhere);
1133
1134    let unnamed_constant = module.constants.append(
1135        crate::Constant {
1136            name: None,
1137            ty: ty_u32,
1138            init: unnamed_init,
1139        },
1140        nowhere,
1141    );
1142
1143    // The named constant is initialized using a Splat expression, to
1144    // give the named constant a type distinct from the unnamed
1145    // constant's.
1146    let unnamed_constant_expr = module
1147        .global_expressions
1148        .append(crate::Expression::Constant(unnamed_constant), nowhere);
1149    let named_init = module.global_expressions.append(
1150        crate::Expression::Splat {
1151            size: crate::VectorSize::Bi,
1152            value: unnamed_constant_expr,
1153        },
1154        nowhere,
1155    );
1156
1157    let _named_constant = module.constants.append(
1158        crate::Constant {
1159            name: Some("totally_named".to_string()),
1160            ty: ty_vec_u32,
1161            init: named_init,
1162        },
1163        nowhere,
1164    );
1165
1166    let mut validator = super::valid::Validator::new(
1167        super::valid::ValidationFlags::all(),
1168        super::valid::Capabilities::all(),
1169    );
1170
1171    assert!(validator.validate(&module).is_ok());
1172    compact(&mut module, KeepUnused::Yes);
1173    assert!(validator.validate(&module).is_ok());
1174}
1175
1176#[test]
1177fn unnamed_override_type() {
1178    let mut module = crate::Module::default();
1179    let nowhere = crate::Span::default();
1180
1181    // This type is used only by the unnamed override.
1182    let ty_u32 = module.types.insert(
1183        crate::Type {
1184            name: None,
1185            inner: crate::TypeInner::Scalar(crate::Scalar::U32),
1186        },
1187        nowhere,
1188    );
1189
1190    // This type is used by the named override.
1191    let ty_i32 = module.types.insert(
1192        crate::Type {
1193            name: None,
1194            inner: crate::TypeInner::Scalar(crate::Scalar::I32),
1195        },
1196        nowhere,
1197    );
1198
1199    let unnamed_init = module
1200        .global_expressions
1201        .append(crate::Expression::Literal(crate::Literal::U32(0)), nowhere);
1202
1203    let unnamed_override = module.overrides.append(
1204        crate::Override {
1205            name: None,
1206            id: Some(42),
1207            ty: ty_u32,
1208            init: Some(unnamed_init),
1209        },
1210        nowhere,
1211    );
1212
1213    // The named override is initialized using a Splat expression, to
1214    // give the named override a type distinct from the unnamed
1215    // override's.
1216    let unnamed_override_expr = module
1217        .global_expressions
1218        .append(crate::Expression::Override(unnamed_override), nowhere);
1219    let named_init = module.global_expressions.append(
1220        crate::Expression::As {
1221            expr: unnamed_override_expr,
1222            kind: crate::ScalarKind::Sint,
1223            convert: None,
1224        },
1225        nowhere,
1226    );
1227
1228    let _named_override = module.overrides.append(
1229        crate::Override {
1230            name: Some("totally_named".to_string()),
1231            id: None,
1232            ty: ty_i32,
1233            init: Some(named_init),
1234        },
1235        nowhere,
1236    );
1237
1238    let mut validator = super::valid::Validator::new(
1239        super::valid::ValidationFlags::all(),
1240        super::valid::Capabilities::all(),
1241    );
1242
1243    assert!(validator.validate(&module).is_ok());
1244    compact(&mut module, KeepUnused::Yes);
1245    assert!(validator.validate(&module).is_ok());
1246}