summaryrefslogtreecommitdiffstats
path: root/third_party/rust/naga/src/compact
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/naga/src/compact')
-rw-r--r--third_party/rust/naga/src/compact/expressions.rs389
-rw-r--r--third_party/rust/naga/src/compact/functions.rs106
-rw-r--r--third_party/rust/naga/src/compact/handle_set_map.rs170
-rw-r--r--third_party/rust/naga/src/compact/mod.rs307
-rw-r--r--third_party/rust/naga/src/compact/statements.rs300
-rw-r--r--third_party/rust/naga/src/compact/types.rs102
6 files changed, 1374 insertions, 0 deletions
diff --git a/third_party/rust/naga/src/compact/expressions.rs b/third_party/rust/naga/src/compact/expressions.rs
new file mode 100644
index 0000000000..301bbe3240
--- /dev/null
+++ b/third_party/rust/naga/src/compact/expressions.rs
@@ -0,0 +1,389 @@
+use super::{HandleMap, HandleSet, ModuleMap};
+use crate::arena::{Arena, Handle};
+
+pub struct ExpressionTracer<'tracer> {
+ pub constants: &'tracer Arena<crate::Constant>,
+
+ /// The arena in which we are currently tracing expressions.
+ pub expressions: &'tracer Arena<crate::Expression>,
+
+ /// The used map for `types`.
+ pub types_used: &'tracer mut HandleSet<crate::Type>,
+
+ /// The used map for `constants`.
+ pub constants_used: &'tracer mut HandleSet<crate::Constant>,
+
+ /// The used set for `arena`.
+ ///
+ /// This points to whatever arena holds the expressions we are
+ /// currently tracing: either a function's expression arena, or
+ /// the module's constant expression arena.
+ pub expressions_used: &'tracer mut HandleSet<crate::Expression>,
+
+ /// The used set for the module's `const_expressions` arena.
+ ///
+ /// If `None`, we are already tracing the constant expressions,
+ /// and `expressions_used` already refers to their handle set.
+ pub const_expressions_used: Option<&'tracer mut HandleSet<crate::Expression>>,
+}
+
+impl<'tracer> ExpressionTracer<'tracer> {
+ /// Propagate usage through `self.expressions`, starting with `self.expressions_used`.
+ ///
+ /// Treat `self.expressions_used` as the initial set of "known
+ /// live" expressions, and follow through to identify all
+ /// transitively used expressions.
+ ///
+ /// Mark types, constants, and constant expressions used directly
+ /// by `self.expressions` as used. Items used indirectly are not
+ /// marked.
+ ///
+ /// [fe]: crate::Function::expressions
+ /// [ce]: crate::Module::const_expressions
+ pub fn trace_expressions(&mut self) {
+ log::trace!(
+ "entering trace_expression of {}",
+ if self.const_expressions_used.is_some() {
+ "function expressions"
+ } else {
+ "const expressions"
+ }
+ );
+
+ // We don't need recursion or a work list. Because an
+ // expression may only refer to other expressions that precede
+ // it in the arena, it suffices to make a single pass over the
+ // arena from back to front, marking the referents of used
+ // expressions as used themselves.
+ for (handle, expr) in self.expressions.iter().rev() {
+ // If this expression isn't used, it doesn't matter what it uses.
+ if !self.expressions_used.contains(handle) {
+ continue;
+ }
+
+ log::trace!("tracing new expression {:?}", expr);
+
+ use crate::Expression as Ex;
+ match *expr {
+ // Expressions that do not contain handles that need to be traced.
+ Ex::Literal(_)
+ | Ex::FunctionArgument(_)
+ | Ex::GlobalVariable(_)
+ | Ex::LocalVariable(_)
+ | Ex::CallResult(_)
+ | Ex::RayQueryProceedResult => {}
+
+ Ex::Constant(handle) => {
+ self.constants_used.insert(handle);
+ // Constants and expressions are mutually recursive, which
+ // complicates our nice one-pass algorithm. However, since
+ // constants don't refer to each other, we can get around
+ // this by looking *through* each constant and marking its
+ // initializer as used. Since `expr` refers to the constant,
+ // and the constant refers to the initializer, it must
+ // precede `expr` in the arena.
+ let init = self.constants[handle].init;
+ match self.const_expressions_used {
+ Some(ref mut used) => used.insert(init),
+ None => self.expressions_used.insert(init),
+ }
+ }
+ Ex::ZeroValue(ty) => self.types_used.insert(ty),
+ Ex::Compose { ty, ref components } => {
+ self.types_used.insert(ty);
+ self.expressions_used
+ .insert_iter(components.iter().cloned());
+ }
+ Ex::Access { base, index } => self.expressions_used.insert_iter([base, index]),
+ Ex::AccessIndex { base, index: _ } => self.expressions_used.insert(base),
+ Ex::Splat { size: _, value } => self.expressions_used.insert(value),
+ Ex::Swizzle {
+ size: _,
+ vector,
+ pattern: _,
+ } => self.expressions_used.insert(vector),
+ Ex::Load { pointer } => self.expressions_used.insert(pointer),
+ Ex::ImageSample {
+ image,
+ sampler,
+ gather: _,
+ coordinate,
+ array_index,
+ offset,
+ ref level,
+ depth_ref,
+ } => {
+ self.expressions_used
+ .insert_iter([image, sampler, coordinate]);
+ self.expressions_used.insert_iter(array_index);
+ match self.const_expressions_used {
+ Some(ref mut used) => used.insert_iter(offset),
+ None => self.expressions_used.insert_iter(offset),
+ }
+ use crate::SampleLevel as Sl;
+ match *level {
+ Sl::Auto | Sl::Zero => {}
+ Sl::Exact(expr) | Sl::Bias(expr) => self.expressions_used.insert(expr),
+ Sl::Gradient { x, y } => self.expressions_used.insert_iter([x, y]),
+ }
+ self.expressions_used.insert_iter(depth_ref);
+ }
+ Ex::ImageLoad {
+ image,
+ coordinate,
+ array_index,
+ sample,
+ level,
+ } => {
+ self.expressions_used.insert(image);
+ self.expressions_used.insert(coordinate);
+ self.expressions_used.insert_iter(array_index);
+ self.expressions_used.insert_iter(sample);
+ self.expressions_used.insert_iter(level);
+ }
+ Ex::ImageQuery { image, ref query } => {
+ self.expressions_used.insert(image);
+ use crate::ImageQuery as Iq;
+ match *query {
+ Iq::Size { level } => self.expressions_used.insert_iter(level),
+ Iq::NumLevels | Iq::NumLayers | Iq::NumSamples => {}
+ }
+ }
+ Ex::Unary { op: _, expr } => self.expressions_used.insert(expr),
+ Ex::Binary { op: _, left, right } => {
+ self.expressions_used.insert_iter([left, right]);
+ }
+ Ex::Select {
+ condition,
+ accept,
+ reject,
+ } => self
+ .expressions_used
+ .insert_iter([condition, accept, reject]),
+ Ex::Derivative {
+ axis: _,
+ ctrl: _,
+ expr,
+ } => self.expressions_used.insert(expr),
+ Ex::Relational { fun: _, argument } => self.expressions_used.insert(argument),
+ Ex::Math {
+ fun: _,
+ arg,
+ arg1,
+ arg2,
+ arg3,
+ } => {
+ self.expressions_used.insert(arg);
+ self.expressions_used.insert_iter(arg1);
+ self.expressions_used.insert_iter(arg2);
+ self.expressions_used.insert_iter(arg3);
+ }
+ Ex::As {
+ expr,
+ kind: _,
+ convert: _,
+ } => self.expressions_used.insert(expr),
+ Ex::AtomicResult { ty, comparison: _ } => self.types_used.insert(ty),
+ Ex::WorkGroupUniformLoadResult { ty } => self.types_used.insert(ty),
+ Ex::ArrayLength(expr) => self.expressions_used.insert(expr),
+ Ex::RayQueryGetIntersection {
+ query,
+ committed: _,
+ } => self.expressions_used.insert(query),
+ }
+ }
+ }
+}
+
+impl ModuleMap {
+ /// Fix up all handles in `expr`.
+ ///
+ /// Use the expression handle remappings in `operand_map`, and all
+ /// other mappings from `self`.
+ pub fn adjust_expression(
+ &self,
+ expr: &mut crate::Expression,
+ operand_map: &HandleMap<crate::Expression>,
+ ) {
+ let adjust = |expr: &mut Handle<crate::Expression>| {
+ operand_map.adjust(expr);
+ };
+
+ use crate::Expression as Ex;
+ match *expr {
+ // Expressions that do not contain handles that need to be adjusted.
+ Ex::Literal(_)
+ | Ex::FunctionArgument(_)
+ | Ex::GlobalVariable(_)
+ | Ex::LocalVariable(_)
+ | Ex::CallResult(_)
+ | Ex::RayQueryProceedResult => {}
+
+ // Expressions that contain handles that need to be adjusted.
+ Ex::Constant(ref mut constant) => self.constants.adjust(constant),
+ Ex::ZeroValue(ref mut ty) => self.types.adjust(ty),
+ Ex::Compose {
+ ref mut ty,
+ ref mut components,
+ } => {
+ self.types.adjust(ty);
+ for component in components {
+ adjust(component);
+ }
+ }
+ Ex::Access {
+ ref mut base,
+ ref mut index,
+ } => {
+ adjust(base);
+ adjust(index);
+ }
+ Ex::AccessIndex {
+ ref mut base,
+ index: _,
+ } => adjust(base),
+ Ex::Splat {
+ size: _,
+ ref mut value,
+ } => adjust(value),
+ Ex::Swizzle {
+ size: _,
+ ref mut vector,
+ pattern: _,
+ } => adjust(vector),
+ Ex::Load { ref mut pointer } => adjust(pointer),
+ Ex::ImageSample {
+ ref mut image,
+ ref mut sampler,
+ gather: _,
+ ref mut coordinate,
+ ref mut array_index,
+ ref mut offset,
+ ref mut level,
+ ref mut depth_ref,
+ } => {
+ adjust(image);
+ adjust(sampler);
+ adjust(coordinate);
+ operand_map.adjust_option(array_index);
+ if let Some(ref mut offset) = *offset {
+ self.const_expressions.adjust(offset);
+ }
+ self.adjust_sample_level(level, operand_map);
+ operand_map.adjust_option(depth_ref);
+ }
+ Ex::ImageLoad {
+ ref mut image,
+ ref mut coordinate,
+ ref mut array_index,
+ ref mut sample,
+ ref mut level,
+ } => {
+ adjust(image);
+ adjust(coordinate);
+ operand_map.adjust_option(array_index);
+ operand_map.adjust_option(sample);
+ operand_map.adjust_option(level);
+ }
+ Ex::ImageQuery {
+ ref mut image,
+ ref mut query,
+ } => {
+ adjust(image);
+ self.adjust_image_query(query, operand_map);
+ }
+ Ex::Unary {
+ op: _,
+ ref mut expr,
+ } => adjust(expr),
+ Ex::Binary {
+ op: _,
+ ref mut left,
+ ref mut right,
+ } => {
+ adjust(left);
+ adjust(right);
+ }
+ Ex::Select {
+ ref mut condition,
+ ref mut accept,
+ ref mut reject,
+ } => {
+ adjust(condition);
+ adjust(accept);
+ adjust(reject);
+ }
+ Ex::Derivative {
+ axis: _,
+ ctrl: _,
+ ref mut expr,
+ } => adjust(expr),
+ Ex::Relational {
+ fun: _,
+ ref mut argument,
+ } => adjust(argument),
+ Ex::Math {
+ fun: _,
+ ref mut arg,
+ ref mut arg1,
+ ref mut arg2,
+ ref mut arg3,
+ } => {
+ adjust(arg);
+ operand_map.adjust_option(arg1);
+ operand_map.adjust_option(arg2);
+ operand_map.adjust_option(arg3);
+ }
+ Ex::As {
+ ref mut expr,
+ kind: _,
+ convert: _,
+ } => adjust(expr),
+ Ex::AtomicResult {
+ ref mut ty,
+ comparison: _,
+ } => self.types.adjust(ty),
+ Ex::WorkGroupUniformLoadResult { ref mut ty } => self.types.adjust(ty),
+ Ex::ArrayLength(ref mut expr) => adjust(expr),
+ Ex::RayQueryGetIntersection {
+ ref mut query,
+ committed: _,
+ } => adjust(query),
+ }
+ }
+
+ fn adjust_sample_level(
+ &self,
+ level: &mut crate::SampleLevel,
+ operand_map: &HandleMap<crate::Expression>,
+ ) {
+ let adjust = |expr: &mut Handle<crate::Expression>| operand_map.adjust(expr);
+
+ use crate::SampleLevel as Sl;
+ match *level {
+ Sl::Auto | Sl::Zero => {}
+ Sl::Exact(ref mut expr) => adjust(expr),
+ Sl::Bias(ref mut expr) => adjust(expr),
+ Sl::Gradient {
+ ref mut x,
+ ref mut y,
+ } => {
+ adjust(x);
+ adjust(y);
+ }
+ }
+ }
+
+ fn adjust_image_query(
+ &self,
+ query: &mut crate::ImageQuery,
+ operand_map: &HandleMap<crate::Expression>,
+ ) {
+ use crate::ImageQuery as Iq;
+
+ match *query {
+ Iq::Size { ref mut level } => operand_map.adjust_option(level),
+ Iq::NumLevels | Iq::NumLayers | Iq::NumSamples => {}
+ }
+ }
+}
diff --git a/third_party/rust/naga/src/compact/functions.rs b/third_party/rust/naga/src/compact/functions.rs
new file mode 100644
index 0000000000..b0d08c7e96
--- /dev/null
+++ b/third_party/rust/naga/src/compact/functions.rs
@@ -0,0 +1,106 @@
+use super::handle_set_map::HandleSet;
+use super::{FunctionMap, ModuleMap};
+
+pub struct FunctionTracer<'a> {
+ pub function: &'a crate::Function,
+ pub constants: &'a crate::Arena<crate::Constant>,
+
+ pub types_used: &'a mut HandleSet<crate::Type>,
+ pub constants_used: &'a mut HandleSet<crate::Constant>,
+ pub const_expressions_used: &'a mut HandleSet<crate::Expression>,
+
+ /// Function-local expressions used.
+ pub expressions_used: HandleSet<crate::Expression>,
+}
+
+impl<'a> FunctionTracer<'a> {
+ pub fn trace(&mut self) {
+ for argument in self.function.arguments.iter() {
+ self.types_used.insert(argument.ty);
+ }
+
+ if let Some(ref result) = self.function.result {
+ self.types_used.insert(result.ty);
+ }
+
+ for (_, local) in self.function.local_variables.iter() {
+ self.types_used.insert(local.ty);
+ if let Some(init) = local.init {
+ self.expressions_used.insert(init);
+ }
+ }
+
+ // Treat named expressions as alive, for the sake of our test suite,
+ // which uses `let blah = expr;` to exercise lots of things.
+ for (&value, _name) in &self.function.named_expressions {
+ self.expressions_used.insert(value);
+ }
+
+ self.trace_block(&self.function.body);
+
+ // Given that `trace_block` has marked the expressions used
+ // directly by statements, walk the arena to find all
+ // expressions used, directly or indirectly.
+ self.as_expression().trace_expressions();
+ }
+
+ fn as_expression(&mut self) -> super::expressions::ExpressionTracer {
+ super::expressions::ExpressionTracer {
+ constants: self.constants,
+ expressions: &self.function.expressions,
+
+ types_used: self.types_used,
+ constants_used: self.constants_used,
+ expressions_used: &mut self.expressions_used,
+ const_expressions_used: Some(&mut self.const_expressions_used),
+ }
+ }
+}
+
+impl FunctionMap {
+ pub fn compact(
+ &self,
+ function: &mut crate::Function,
+ module_map: &ModuleMap,
+ reuse: &mut crate::NamedExpressions,
+ ) {
+ assert!(reuse.is_empty());
+
+ for argument in function.arguments.iter_mut() {
+ module_map.types.adjust(&mut argument.ty);
+ }
+
+ if let Some(ref mut result) = function.result {
+ module_map.types.adjust(&mut result.ty);
+ }
+
+ for (_, local) in function.local_variables.iter_mut() {
+ log::trace!("adjusting local variable {:?}", local.name);
+ module_map.types.adjust(&mut local.ty);
+ if let Some(ref mut init) = local.init {
+ self.expressions.adjust(init);
+ }
+ }
+
+ // Drop unused expressions, reusing existing storage.
+ function.expressions.retain_mut(|handle, expr| {
+ if self.expressions.used(handle) {
+ module_map.adjust_expression(expr, &self.expressions);
+ true
+ } else {
+ false
+ }
+ });
+
+ // Adjust named expressions.
+ for (mut handle, name) in function.named_expressions.drain(..) {
+ self.expressions.adjust(&mut handle);
+ reuse.insert(handle, name);
+ }
+ std::mem::swap(&mut function.named_expressions, reuse);
+ assert!(reuse.is_empty());
+
+ // Adjust statements.
+ self.adjust_body(function);
+ }
+}
diff --git a/third_party/rust/naga/src/compact/handle_set_map.rs b/third_party/rust/naga/src/compact/handle_set_map.rs
new file mode 100644
index 0000000000..c716ca8294
--- /dev/null
+++ b/third_party/rust/naga/src/compact/handle_set_map.rs
@@ -0,0 +1,170 @@
+use crate::arena::{Arena, Handle, Range, UniqueArena};
+
+type Index = std::num::NonZeroU32;
+
+/// A set of `Handle<T>` values.
+pub struct HandleSet<T> {
+ /// Bound on zero-based indexes of handles stored in this set.
+ len: usize,
+
+ /// `members[i]` is true if the handle with zero-based index `i`
+ /// is a member.
+ members: bit_set::BitSet,
+
+ /// This type is indexed by values of type `T`.
+ as_keys: std::marker::PhantomData<T>,
+}
+
+impl<T> HandleSet<T> {
+ pub fn for_arena(arena: &impl ArenaType<T>) -> Self {
+ let len = arena.len();
+ Self {
+ len,
+ members: bit_set::BitSet::with_capacity(len),
+ as_keys: std::marker::PhantomData,
+ }
+ }
+
+ /// Add `handle` to the set.
+ pub fn insert(&mut self, handle: Handle<T>) {
+ // Note that, oddly, `Handle::index` does not return a 1-based
+ // `Index`, but rather a zero-based `usize`.
+ self.members.insert(handle.index());
+ }
+
+ /// Add handles from `iter` to the set.
+ pub fn insert_iter(&mut self, iter: impl IntoIterator<Item = Handle<T>>) {
+ for handle in iter {
+ self.insert(handle);
+ }
+ }
+
+ pub fn contains(&self, handle: Handle<T>) -> bool {
+ // Note that, oddly, `Handle::index` does not return a 1-based
+ // `Index`, but rather a zero-based `usize`.
+ self.members.contains(handle.index())
+ }
+}
+
+pub trait ArenaType<T> {
+ fn len(&self) -> usize;
+}
+
+impl<T> ArenaType<T> for Arena<T> {
+ fn len(&self) -> usize {
+ self.len()
+ }
+}
+
+impl<T: std::hash::Hash + Eq> ArenaType<T> for UniqueArena<T> {
+ fn len(&self) -> usize {
+ self.len()
+ }
+}
+
+/// A map from old handle indices to new, compressed handle indices.
+pub struct HandleMap<T> {
+ /// The indices assigned to handles in the compacted module.
+ ///
+ /// If `new_index[i]` is `Some(n)`, then `n` is the 1-based
+ /// `Index` of the compacted `Handle` corresponding to the
+ /// pre-compacted `Handle` whose zero-based index is `i`. ("Clear
+ /// as mud.")
+ new_index: Vec<Option<Index>>,
+
+ /// This type is indexed by values of type `T`.
+ as_keys: std::marker::PhantomData<T>,
+}
+
+impl<T: 'static> HandleMap<T> {
+ pub fn from_set(set: HandleSet<T>) -> Self {
+ let mut next_index = Index::new(1).unwrap();
+ Self {
+ new_index: (0..set.len)
+ .map(|zero_based_index| {
+ if set.members.contains(zero_based_index) {
+ // This handle will be retained in the compacted version,
+ // so assign it a new index.
+ let this = next_index;
+ next_index = next_index.checked_add(1).unwrap();
+ Some(this)
+ } else {
+ // This handle will be omitted in the compacted version.
+ None
+ }
+ })
+ .collect(),
+ as_keys: std::marker::PhantomData,
+ }
+ }
+
+ /// Return true if `old` is used in the compacted module.
+ pub fn used(&self, old: Handle<T>) -> bool {
+ self.new_index[old.index()].is_some()
+ }
+
+ /// Return the counterpart to `old` in the compacted module.
+ ///
+ /// If we thought `old` wouldn't be used in the compacted module, return
+ /// `None`.
+ pub fn try_adjust(&self, old: Handle<T>) -> Option<Handle<T>> {
+ log::trace!(
+ "adjusting {} handle [{}] -> [{:?}]",
+ std::any::type_name::<T>(),
+ old.index() + 1,
+ self.new_index[old.index()]
+ );
+ // Note that `Handle::index` returns a zero-based index,
+ // but `Handle::new` accepts a 1-based `Index`.
+ self.new_index[old.index()].map(Handle::new)
+ }
+
+ /// Return the counterpart to `old` in the compacted module.
+ ///
+ /// If we thought `old` wouldn't be used in the compacted module, panic.
+ pub fn adjust(&self, handle: &mut Handle<T>) {
+ *handle = self.try_adjust(*handle).unwrap();
+ }
+
+ /// Like `adjust`, but for optional handles.
+ pub fn adjust_option(&self, handle: &mut Option<Handle<T>>) {
+ if let Some(ref mut handle) = *handle {
+ self.adjust(handle);
+ }
+ }
+
+ /// Shrink `range` to include only used handles.
+ ///
+ /// Fortunately, compaction doesn't arbitrarily scramble the expressions
+ /// in the arena, but instead preserves the order of the elements while
+ /// squeezing out unused ones. That means that a contiguous range in the
+ /// pre-compacted arena always maps to a contiguous range in the
+ /// post-compacted arena. So we just need to adjust the endpoints.
+ ///
+ /// Compaction may have eliminated the endpoints themselves.
+ ///
+ /// Use `compacted_arena` to bounds-check the result.
+ pub fn adjust_range(&self, range: &mut Range<T>, compacted_arena: &Arena<T>) {
+ let mut index_range = range.zero_based_index_range();
+ let compacted;
+ // Remember that the indices we retrieve from `new_index` are 1-based
+ // compacted indices, but the index range we're computing is zero-based
+ // compacted indices.
+ if let Some(first1) = index_range.find_map(|i| self.new_index[i as usize]) {
+ // The first call to `find_map` mutated `index_range` to hold the
+ // remainder of original range, which is exactly the range we need
+ // to search for the new last handle.
+ if let Some(last1) = index_range.rev().find_map(|i| self.new_index[i as usize]) {
+ // Build a zero-based end-exclusive range, given one-based handle indices.
+ compacted = first1.get() - 1..last1.get();
+ } else {
+ // The range contains only a single live handle, which
+ // we identified with the first `find_map` call.
+ compacted = first1.get() - 1..first1.get();
+ }
+ } else {
+ compacted = 0..0;
+ };
+ *range = Range::from_zero_based_index_range(compacted, compacted_arena);
+ }
+}
diff --git a/third_party/rust/naga/src/compact/mod.rs b/third_party/rust/naga/src/compact/mod.rs
new file mode 100644
index 0000000000..b4e57ed5c9
--- /dev/null
+++ b/third_party/rust/naga/src/compact/mod.rs
@@ -0,0 +1,307 @@
+mod expressions;
+mod functions;
+mod handle_set_map;
+mod statements;
+mod types;
+
+use crate::{arena, compact::functions::FunctionTracer};
+use handle_set_map::{HandleMap, HandleSet};
+
+/// Remove unused types, expressions, and constants from `module`.
+///
+/// Assuming that all globals, named constants, special types,
+/// functions and entry points in `module` are used, determine which
+/// types, constants, and expressions (both function-local and global
+/// constant expressions) are actually used, and remove the rest,
+/// adjusting all handles as necessary. The result should be a module
+/// functionally identical to the original.
+///
+/// This may be useful to apply to modules generated in the snapshot
+/// tests. Our backends often generate temporary names based on handle
+/// indices, which means that adding or removing unused arena entries
+/// can affect the output even though they have no semantic effect.
+/// Such meaningless changes add noise to snapshot diffs, making
+/// accurate patch review difficult. Compacting the modules before
+/// generating snapshots makes the output independent of unused arena
+/// entries.
+///
+/// # Panics
+///
+/// If `module` has not passed validation, this may panic.
+pub fn compact(module: &mut crate::Module) {
+ let mut module_tracer = ModuleTracer::new(module);
+
+ // We treat all globals as used by definition.
+ log::trace!("tracing global variables");
+ {
+ for (_, global) in module.global_variables.iter() {
+ log::trace!("tracing global {:?}", global.name);
+ module_tracer.types_used.insert(global.ty);
+ if let Some(init) = global.init {
+ module_tracer.const_expressions_used.insert(init);
+ }
+ }
+ }
+
+ // We treat all special types as used by definition.
+ module_tracer.trace_special_types(&module.special_types);
+
+ // We treat all named constants as used by definition.
+ for (handle, constant) in module.constants.iter() {
+ if constant.name.is_some() {
+ module_tracer.constants_used.insert(handle);
+ module_tracer.const_expressions_used.insert(constant.init);
+ }
+ }
+
+ // We assume that all functions are used.
+ //
+ // Observe which types, constant expressions, constants, and
+ // expressions each function uses, and produce maps for each
+ // function from pre-compaction to post-compaction expression
+ // handles.
+ log::trace!("tracing functions");
+ let function_maps: Vec<FunctionMap> = module
+ .functions
+ .iter()
+ .map(|(_, f)| {
+ log::trace!("tracing function {:?}", f.name);
+ let mut function_tracer = module_tracer.as_function(f);
+ function_tracer.trace();
+ FunctionMap::from(function_tracer)
+ })
+ .collect();
+
+ // Similarly, observe what each entry point actually uses.
+ log::trace!("tracing entry points");
+ let entry_point_maps: Vec<FunctionMap> = module
+ .entry_points
+ .iter()
+ .map(|e| {
+ log::trace!("tracing entry point {:?}", e.function.name);
+ let mut used = module_tracer.as_function(&e.function);
+ used.trace();
+ FunctionMap::from(used)
+ })
+ .collect();
+
+ // Given that the above steps have marked all the constant
+ // expressions used directly by globals, constants, functions, and
+ // entry points, walk the constant expression arena to find all
+ // constant expressions used, directly or indirectly.
+ module_tracer.as_const_expression().trace_expressions();
+
+ // Constants' initializers are taken care of already, because
+ // expression tracing sees through constants. But we still need to
+ // note type usage.
+ for (handle, constant) in module.constants.iter() {
+ if module_tracer.constants_used.contains(handle) {
+ module_tracer.types_used.insert(constant.ty);
+ }
+ }
+
+ // Treat all named types as used.
+ for (handle, ty) in module.types.iter() {
+ log::trace!("tracing type {:?}, name {:?}", handle, ty.name);
+ if ty.name.is_some() {
+ module_tracer.types_used.insert(handle);
+ }
+ }
+
+ // Propagate usage through types.
+ module_tracer.as_type().trace_types();
+
+ // Now that we know what is used and what is never touched,
+ // produce maps from the `Handle`s that appear in `module` now to
+ // the corresponding `Handle`s that will refer to the same items
+ // in the compacted module.
+ let module_map = ModuleMap::from(module_tracer);
+
+ // Drop unused types from the type arena.
+ //
+ // `FastIndexSet`s don't have an underlying Vec<T> that we can
+ // steal, compact in place, and then rebuild the `FastIndexSet`
+ // from. So we have to rebuild the type arena from scratch.
+ log::trace!("compacting types");
+ let mut new_types = arena::UniqueArena::new();
+ for (old_handle, mut ty, span) in module.types.drain_all() {
+ if let Some(expected_new_handle) = module_map.types.try_adjust(old_handle) {
+ module_map.adjust_type(&mut ty);
+ let actual_new_handle = new_types.insert(ty, span);
+ assert_eq!(actual_new_handle, expected_new_handle);
+ }
+ }
+ module.types = new_types;
+ log::trace!("adjusting special types");
+ module_map.adjust_special_types(&mut module.special_types);
+
+ // Drop unused constant expressions, reusing existing storage.
+ log::trace!("adjusting constant expressions");
+ module.const_expressions.retain_mut(|handle, expr| {
+ if module_map.const_expressions.used(handle) {
+ module_map.adjust_expression(expr, &module_map.const_expressions);
+ true
+ } else {
+ false
+ }
+ });
+
+ // Drop unused constants in place, reusing existing storage.
+ log::trace!("adjusting constants");
+ module.constants.retain_mut(|handle, constant| {
+ if module_map.constants.used(handle) {
+ module_map.types.adjust(&mut constant.ty);
+ module_map.const_expressions.adjust(&mut constant.init);
+ true
+ } else {
+ false
+ }
+ });
+
+ // Adjust global variables' types and initializers.
+ log::trace!("adjusting global variables");
+ for (_, global) in module.global_variables.iter_mut() {
+ log::trace!("adjusting global {:?}", global.name);
+ module_map.types.adjust(&mut global.ty);
+ if let Some(ref mut init) = global.init {
+ module_map.const_expressions.adjust(init);
+ }
+ }
+
+ // Temporary storage to help us reuse allocations of existing
+ // named expression tables.
+ let mut reused_named_expressions = crate::NamedExpressions::default();
+
+ // Compact each function.
+ for ((_, function), map) in module.functions.iter_mut().zip(function_maps.iter()) {
+ log::trace!("compacting function {:?}", function.name);
+ map.compact(function, &module_map, &mut reused_named_expressions);
+ }
+
+ // Compact each entry point.
+ for (entry, map) in module.entry_points.iter_mut().zip(entry_point_maps.iter()) {
+ log::trace!("compacting entry point {:?}", entry.function.name);
+ map.compact(
+ &mut entry.function,
+ &module_map,
+ &mut reused_named_expressions,
+ );
+ }
+}
+
+struct ModuleTracer<'module> {
+ module: &'module crate::Module,
+ types_used: HandleSet<crate::Type>,
+ constants_used: HandleSet<crate::Constant>,
+ const_expressions_used: HandleSet<crate::Expression>,
+}
+
+impl<'module> ModuleTracer<'module> {
+ fn new(module: &'module crate::Module) -> Self {
+ Self {
+ module,
+ types_used: HandleSet::for_arena(&module.types),
+ constants_used: HandleSet::for_arena(&module.constants),
+ const_expressions_used: HandleSet::for_arena(&module.const_expressions),
+ }
+ }
+
+ fn trace_special_types(&mut self, special_types: &crate::SpecialTypes) {
+ let crate::SpecialTypes {
+ ref ray_desc,
+ ref ray_intersection,
+ ref predeclared_types,
+ } = *special_types;
+
+ if let Some(ray_desc) = *ray_desc {
+ self.types_used.insert(ray_desc);
+ }
+ if let Some(ray_intersection) = *ray_intersection {
+ self.types_used.insert(ray_intersection);
+ }
+ for (_, &handle) in predeclared_types {
+ self.types_used.insert(handle);
+ }
+ }
+
+ fn as_type(&mut self) -> types::TypeTracer {
+ types::TypeTracer {
+ types: &self.module.types,
+ types_used: &mut self.types_used,
+ }
+ }
+
+ fn as_const_expression(&mut self) -> expressions::ExpressionTracer {
+ expressions::ExpressionTracer {
+ expressions: &self.module.const_expressions,
+ constants: &self.module.constants,
+ types_used: &mut self.types_used,
+ constants_used: &mut self.constants_used,
+ expressions_used: &mut self.const_expressions_used,
+ const_expressions_used: None,
+ }
+ }
+
+ pub fn as_function<'tracer>(
+ &'tracer mut self,
+ function: &'tracer crate::Function,
+ ) -> FunctionTracer<'tracer> {
+ FunctionTracer {
+ function,
+ constants: &self.module.constants,
+ types_used: &mut self.types_used,
+ constants_used: &mut self.constants_used,
+ const_expressions_used: &mut self.const_expressions_used,
+ expressions_used: HandleSet::for_arena(&function.expressions),
+ }
+ }
+}
+
+struct ModuleMap {
+ types: HandleMap<crate::Type>,
+ constants: HandleMap<crate::Constant>,
+ const_expressions: HandleMap<crate::Expression>,
+}
+
+impl From<ModuleTracer<'_>> for ModuleMap {
+ fn from(used: ModuleTracer) -> Self {
+ ModuleMap {
+ types: HandleMap::from_set(used.types_used),
+ constants: HandleMap::from_set(used.constants_used),
+ const_expressions: HandleMap::from_set(used.const_expressions_used),
+ }
+ }
+}
+
+impl ModuleMap {
+ fn adjust_special_types(&self, special: &mut crate::SpecialTypes) {
+ let crate::SpecialTypes {
+ ref mut ray_desc,
+ ref mut ray_intersection,
+ ref mut predeclared_types,
+ } = *special;
+
+ if let Some(ref mut ray_desc) = *ray_desc {
+ self.types.adjust(ray_desc);
+ }
+ if let Some(ref mut ray_intersection) = *ray_intersection {
+ self.types.adjust(ray_intersection);
+ }
+
+ for handle in predeclared_types.values_mut() {
+ self.types.adjust(handle);
+ }
+ }
+}
+
+struct FunctionMap {
+ expressions: HandleMap<crate::Expression>,
+}
+
+impl From<FunctionTracer<'_>> for FunctionMap {
+ fn from(used: FunctionTracer) -> Self {
+ FunctionMap {
+ expressions: HandleMap::from_set(used.expressions_used),
+ }
+ }
+}
diff --git a/third_party/rust/naga/src/compact/statements.rs b/third_party/rust/naga/src/compact/statements.rs
new file mode 100644
index 0000000000..0698b57258
--- /dev/null
+++ b/third_party/rust/naga/src/compact/statements.rs
@@ -0,0 +1,300 @@
+use super::functions::FunctionTracer;
+use super::FunctionMap;
+use crate::arena::Handle;
+
+impl FunctionTracer<'_> {
+ pub fn trace_block(&mut self, block: &[crate::Statement]) {
+ let mut worklist: Vec<&[crate::Statement]> = vec![block];
+ while let Some(last) = worklist.pop() {
+ for stmt in last {
+ use crate::Statement as St;
+ match *stmt {
+ St::Emit(ref _range) => {
+ // If we come across a statement that actually uses an
+ // expression in this range, it'll get traced from
+ // there. But since evaluating expressions has no
+ // effect, we don't need to assume that everything
+ // emitted is live.
+ }
+ St::Block(ref block) => worklist.push(block),
+ St::If {
+ condition,
+ ref accept,
+ ref reject,
+ } => {
+ self.expressions_used.insert(condition);
+ worklist.push(accept);
+ worklist.push(reject);
+ }
+ St::Switch {
+ selector,
+ ref cases,
+ } => {
+ self.expressions_used.insert(selector);
+ for case in cases {
+ worklist.push(&case.body);
+ }
+ }
+ St::Loop {
+ ref body,
+ ref continuing,
+ break_if,
+ } => {
+ if let Some(break_if) = break_if {
+ self.expressions_used.insert(break_if);
+ }
+ worklist.push(body);
+ worklist.push(continuing);
+ }
+ St::Return { value: Some(value) } => {
+ self.expressions_used.insert(value);
+ }
+ St::Store { pointer, value } => {
+ self.expressions_used.insert(pointer);
+ self.expressions_used.insert(value);
+ }
+ St::ImageStore {
+ image,
+ coordinate,
+ array_index,
+ value,
+ } => {
+ self.expressions_used.insert(image);
+ self.expressions_used.insert(coordinate);
+ if let Some(array_index) = array_index {
+ self.expressions_used.insert(array_index);
+ }
+ self.expressions_used.insert(value);
+ }
+ St::Atomic {
+ pointer,
+ ref fun,
+ value,
+ result,
+ } => {
+ self.expressions_used.insert(pointer);
+ self.trace_atomic_function(fun);
+ self.expressions_used.insert(value);
+ self.expressions_used.insert(result);
+ }
+ St::WorkGroupUniformLoad { pointer, result } => {
+ self.expressions_used.insert(pointer);
+ self.expressions_used.insert(result);
+ }
+ St::Call {
+ function: _,
+ ref arguments,
+ result,
+ } => {
+ for expr in arguments {
+ self.expressions_used.insert(*expr);
+ }
+ if let Some(result) = result {
+ self.expressions_used.insert(result);
+ }
+ }
+ St::RayQuery { query, ref fun } => {
+ self.expressions_used.insert(query);
+ self.trace_ray_query_function(fun);
+ }
+
+ // Trivial statements.
+ St::Break
+ | St::Continue
+ | St::Kill
+ | St::Barrier(_)
+ | St::Return { value: None } => {}
+ }
+ }
+ }
+ }
+
+ fn trace_atomic_function(&mut self, fun: &crate::AtomicFunction) {
+ use crate::AtomicFunction as Af;
+ match *fun {
+ Af::Exchange {
+ compare: Some(expr),
+ } => {
+ self.expressions_used.insert(expr);
+ }
+ Af::Exchange { compare: None }
+ | Af::Add
+ | Af::Subtract
+ | Af::And
+ | Af::ExclusiveOr
+ | Af::InclusiveOr
+ | Af::Min
+ | Af::Max => {}
+ }
+ }
+
+ fn trace_ray_query_function(&mut self, fun: &crate::RayQueryFunction) {
+ use crate::RayQueryFunction as Qf;
+ match *fun {
+ Qf::Initialize {
+ acceleration_structure,
+ descriptor,
+ } => {
+ self.expressions_used.insert(acceleration_structure);
+ self.expressions_used.insert(descriptor);
+ }
+ Qf::Proceed { result } => {
+ self.expressions_used.insert(result);
+ }
+ Qf::Terminate => {}
+ }
+ }
+}
+
+impl FunctionMap {
+ pub fn adjust_body(&self, function: &mut crate::Function) {
+ let block = &mut function.body;
+ let mut worklist: Vec<&mut [crate::Statement]> = vec![block];
+ let adjust = |handle: &mut Handle<crate::Expression>| {
+ self.expressions.adjust(handle);
+ };
+ while let Some(last) = worklist.pop() {
+ for stmt in last {
+ use crate::Statement as St;
+ match *stmt {
+ St::Emit(ref mut range) => {
+ self.expressions.adjust_range(range, &function.expressions);
+ }
+ St::Block(ref mut block) => worklist.push(block),
+ St::If {
+ ref mut condition,
+ ref mut accept,
+ ref mut reject,
+ } => {
+ adjust(condition);
+ worklist.push(accept);
+ worklist.push(reject);
+ }
+ St::Switch {
+ ref mut selector,
+ ref mut cases,
+ } => {
+ adjust(selector);
+ for case in cases {
+ worklist.push(&mut case.body);
+ }
+ }
+ St::Loop {
+ ref mut body,
+ ref mut continuing,
+ ref mut break_if,
+ } => {
+ if let Some(ref mut break_if) = *break_if {
+ adjust(break_if);
+ }
+ worklist.push(body);
+ worklist.push(continuing);
+ }
+ St::Return {
+ value: Some(ref mut value),
+ } => adjust(value),
+ St::Store {
+ ref mut pointer,
+ ref mut value,
+ } => {
+ adjust(pointer);
+ adjust(value);
+ }
+ St::ImageStore {
+ ref mut image,
+ ref mut coordinate,
+ ref mut array_index,
+ ref mut value,
+ } => {
+ adjust(image);
+ adjust(coordinate);
+ if let Some(ref mut array_index) = *array_index {
+ adjust(array_index);
+ }
+ adjust(value);
+ }
+ St::Atomic {
+ ref mut pointer,
+ ref mut fun,
+ ref mut value,
+ ref mut result,
+ } => {
+ adjust(pointer);
+ self.adjust_atomic_function(fun);
+ adjust(value);
+ adjust(result);
+ }
+ St::WorkGroupUniformLoad {
+ ref mut pointer,
+ ref mut result,
+ } => {
+ adjust(pointer);
+ adjust(result);
+ }
+ St::Call {
+ function: _,
+ ref mut arguments,
+ ref mut result,
+ } => {
+ for expr in arguments {
+ adjust(expr);
+ }
+ if let Some(ref mut result) = *result {
+ adjust(result);
+ }
+ }
+ St::RayQuery {
+ ref mut query,
+ ref mut fun,
+ } => {
+ adjust(query);
+ self.adjust_ray_query_function(fun);
+ }
+
+ // Trivial statements.
+ St::Break
+ | St::Continue
+ | St::Kill
+ | St::Barrier(_)
+ | St::Return { value: None } => {}
+ }
+ }
+ }
+ }
+
+ fn adjust_atomic_function(&self, fun: &mut crate::AtomicFunction) {
+ use crate::AtomicFunction as Af;
+ match *fun {
+ Af::Exchange {
+ compare: Some(ref mut expr),
+ } => {
+ self.expressions.adjust(expr);
+ }
+ Af::Exchange { compare: None }
+ | Af::Add
+ | Af::Subtract
+ | Af::And
+ | Af::ExclusiveOr
+ | Af::InclusiveOr
+ | Af::Min
+ | Af::Max => {}
+ }
+ }
+
+ fn adjust_ray_query_function(&self, fun: &mut crate::RayQueryFunction) {
+ use crate::RayQueryFunction as Qf;
+ match *fun {
+ Qf::Initialize {
+ ref mut acceleration_structure,
+ ref mut descriptor,
+ } => {
+ self.expressions.adjust(acceleration_structure);
+ self.expressions.adjust(descriptor);
+ }
+ Qf::Proceed { ref mut result } => {
+ self.expressions.adjust(result);
+ }
+ Qf::Terminate => {}
+ }
+ }
+}
diff --git a/third_party/rust/naga/src/compact/types.rs b/third_party/rust/naga/src/compact/types.rs
new file mode 100644
index 0000000000..b78619d9a8
--- /dev/null
+++ b/third_party/rust/naga/src/compact/types.rs
@@ -0,0 +1,102 @@
+use super::{HandleSet, ModuleMap};
+use crate::{Handle, UniqueArena};
+
+pub struct TypeTracer<'a> {
+ pub types: &'a UniqueArena<crate::Type>,
+ pub types_used: &'a mut HandleSet<crate::Type>,
+}
+
+impl<'a> TypeTracer<'a> {
+ /// Propagate usage through `self.types`, starting with `self.types_used`.
+ ///
+ /// Treat `self.types_used` as the initial set of "known
+ /// live" types, and follow through to identify all
+ /// transitively used types.
+ pub fn trace_types(&mut self) {
+ // We don't need recursion or a work list. Because an
+ // expression may only refer to other expressions that precede
+ // it in the arena, it suffices to make a single pass over the
+ // arena from back to front, marking the referents of used
+ // expressions as used themselves.
+ for (handle, ty) in self.types.iter().rev() {
+ // If this type isn't used, it doesn't matter what it uses.
+ if !self.types_used.contains(handle) {
+ continue;
+ }
+
+ use crate::TypeInner as Ti;
+ match ty.inner {
+ // Types that do not contain handles.
+ Ti::Scalar { .. }
+ | Ti::Vector { .. }
+ | Ti::Matrix { .. }
+ | Ti::Atomic { .. }
+ | Ti::ValuePointer { .. }
+ | Ti::Image { .. }
+ | Ti::Sampler { .. }
+ | Ti::AccelerationStructure
+ | Ti::RayQuery => {}
+
+ // Types that do contain handles.
+ Ti::Pointer { base, space: _ }
+ | Ti::Array {
+ base,
+ size: _,
+ stride: _,
+ }
+ | Ti::BindingArray { base, size: _ } => self.types_used.insert(base),
+ Ti::Struct {
+ ref members,
+ span: _,
+ } => {
+ self.types_used.insert_iter(members.iter().map(|m| m.ty));
+ }
+ }
+ }
+ }
+}
+
+impl ModuleMap {
+ pub fn adjust_type(&self, ty: &mut crate::Type) {
+ let adjust = |ty: &mut Handle<crate::Type>| self.types.adjust(ty);
+
+ use crate::TypeInner as Ti;
+ match ty.inner {
+ // Types that do not contain handles.
+ Ti::Scalar(_)
+ | Ti::Vector { .. }
+ | Ti::Matrix { .. }
+ | Ti::Atomic(_)
+ | Ti::ValuePointer { .. }
+ | Ti::Image { .. }
+ | Ti::Sampler { .. }
+ | Ti::AccelerationStructure
+ | Ti::RayQuery => {}
+
+ // Types that do contain handles.
+ Ti::Pointer {
+ ref mut base,
+ space: _,
+ } => adjust(base),
+ Ti::Array {
+ ref mut base,
+ size: _,
+ stride: _,
+ } => adjust(base),
+ Ti::Struct {
+ ref mut members,
+ span: _,
+ } => {
+ for member in members {
+ self.types.adjust(&mut member.ty);
+ }
+ }
+ Ti::BindingArray {
+ ref mut base,
+ size: _,
+ } => {
+ adjust(base);
+ }
+ };
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-02 06:26:17 +0000