1 //! Definitions for index bounds checking.
2
3 use super::ProcError;
4 use crate::valid;
5 use crate::{Handle, UniqueArena};
6 use bit_set::BitSet;
7
8 /// How should code generated by Naga do bounds checks?
9 ///
10 /// When a vector, matrix, or array index is out of bounds—either negative, or
11 /// greater than or equal to the number of elements in the type—WGSL requires
12 /// that some other index of the implementation's choice that is in bounds is
13 /// used instead. (There are no types with zero elements.)
14 ///
15 /// Similarly, when out-of-bounds coordinates, array indices, or sample indices
16 /// are presented to the WGSL `textureLoad` and `textureStore` operations, the
17 /// operation is redirected to do something safe.
18 ///
19 /// Different users of Naga will prefer different defaults:
20 ///
21 /// - When used as part of a WebGPU implementation, the WGSL specification
22 /// requires the `Restrict` behavior for array, vector, and matrix accesses,
23 /// and either the `Restrict` or `ReadZeroSkipWrite` behaviors for texture
24 /// accesses.
25 ///
26 /// - When used by the `wgpu` crate for native development, `wgpu` selects
27 /// `ReadZeroSkipWrite` as its default.
28 ///
29 /// - Naga's own default is `Unchecked`, so that shader translations
30 /// are as faithful to the original as possible.
31 ///
32 /// Sometimes the underlying hardware and drivers can perform bounds checks
33 /// themselves, in a way that performs better than the checks Naga would inject.
34 /// If you're using native checks like this, then having Naga inject its own
35 /// checks as well would be redundant, and the `Unchecked` policy is
36 /// appropriate.
37 #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
38 #[cfg_attr(feature = "serialize", derive(serde::Serialize))]
39 #[cfg_attr(feature = "deserialize", derive(serde::Deserialize))]
40 pub enum BoundsCheckPolicy {
41 /// Replace out-of-bounds indexes with some arbitrary in-bounds index.
42 ///
43 /// (This does not necessarily mean clamping. For example, interpreting the
44 /// index as unsigned and taking the minimum with the largest valid index
45 /// would also be a valid implementation. That would map negative indices to
46 /// the last element, not the first.)
47 Restrict,
48
49 /// Out-of-bounds reads return zero, and writes have no effect.
50 ///
51 /// When applied to a chain of accesses, like `a[i][j].b[k]`, all index
52 /// expressions are evaluated, regardless of whether prior or later index
53 /// expressions were in bounds. But all the accesses per se are skipped
54 /// if any index is out of bounds.
55 ReadZeroSkipWrite,
56
57 /// Naga adds no checks to indexing operations. Generate the fastest code
58 /// possible. This is the default for Naga, as a translator, but consumers
59 /// should consider defaulting to a safer behavior.
60 Unchecked,
61 }
62
63 /// Policies for injecting bounds checks during code generation.
64 #[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
65 #[cfg_attr(feature = "serialize", derive(serde::Serialize))]
66 #[cfg_attr(feature = "deserialize", derive(serde::Deserialize))]
67 pub struct BoundsCheckPolicies {
68 /// How should the generated code handle array, vector, or matrix indices
69 /// that are out of range?
70 #[cfg_attr(feature = "deserialize", serde(default))]
71 pub index: BoundsCheckPolicy,
72
73 /// How should the generated code handle array, vector, or matrix indices
74 /// that are out of range, when those values live in a [`GlobalVariable`] in
75 /// the [`Storage`] or [`Uniform`] storage classes?
76 ///
77 /// Some graphics hardware provides "robust buffer access", a feature that
78 /// ensures that using a pointer cannot access memory outside the 'buffer'
79 /// that it was derived from. In Naga terms, this means that the hardware
80 /// ensures that pointers computed by applying [`Access`] and
81 /// [`AccessIndex`] expressions to a [`GlobalVariable`] whose [`class`] is
82 /// [`Storage`] or [`Uniform`] will never read or write memory outside that
83 /// global variable.
84 ///
85 /// When hardware offers such a feature, it is probably undesirable to have
86 /// Naga inject bounds checking code for such accesses, since the hardware
87 /// can probably provide the same protection more efficiently. However,
88 /// bounds checks are still needed on accesses to indexable values that do
89 /// not live in buffers, like local variables.
90 ///
91 /// So, this option provides a separate policy that applies only to accesses
92 /// to storage and uniform globals. When depending on hardware bounds
93 /// checking, this policy can be `Unchecked` to avoid unnecessary overhead.
94 ///
95 /// When special hardware support is not available, this should probably be
96 /// the same as `index_bounds_check_policy`.
97 ///
98 /// [`GlobalVariable`]: crate::GlobalVariable
99 /// [`class`]: crate::GlobalVariable::class
100 /// [`Restrict`]: crate::back::BoundsCheckPolicy::Restrict
101 /// [`ReadZeroSkipWrite`]: crate::back::BoundsCheckPolicy::ReadZeroSkipWrite
102 /// [`Access`]: crate::Expression::Access
103 /// [`AccessIndex`]: crate::Expression::AccessIndex
104 /// [`Storage`]: crate::StorageClass::Storage
105 /// [`Uniform`]: crate::StorageClass::Uniform
106 #[cfg_attr(feature = "deserialize", serde(default))]
107 pub buffer: BoundsCheckPolicy,
108
109 /// How should the generated code handle image texel references that are out
110 /// of range?
111 ///
112 /// This controls the behavior of [`ImageLoad`] expressions and
113 /// [`ImageStore`] statements when a coordinate, texture array index, level
114 /// of detail, or multisampled sample number is out of range.
115 ///
116 /// [`ImageLoad`]: crate::Expression::ImageLoad
117 /// [`ImageStore`]: crate::Statement::ImageStore
118 #[cfg_attr(feature = "deserialize", serde(default))]
119 pub image: BoundsCheckPolicy,
120 }
121
122 /// The default `BoundsCheckPolicy` is `Unchecked`.
123 impl Default for BoundsCheckPolicy {
default() -> Self124 fn default() -> Self {
125 BoundsCheckPolicy::Unchecked
126 }
127 }
128
129 impl BoundsCheckPolicies {
130 /// Determine which policy applies to `access`.
131 ///
132 /// `access` is a subtree of `Access` and `AccessIndex` expressions,
133 /// operating either on a pointer to a value, or on a value directly.
134 ///
135 /// See the documentation for [`BoundsCheckPolicy`] for details about
136 /// when each policy applies.
choose_policy( &self, access: Handle<crate::Expression>, types: &UniqueArena<crate::Type>, info: &valid::FunctionInfo, ) -> BoundsCheckPolicy137 pub fn choose_policy(
138 &self,
139 access: Handle<crate::Expression>,
140 types: &UniqueArena<crate::Type>,
141 info: &valid::FunctionInfo,
142 ) -> BoundsCheckPolicy {
143 match info[access].ty.inner_with(types).pointer_class() {
144 Some(crate::StorageClass::Storage { access: _ })
145 | Some(crate::StorageClass::Uniform) => self.buffer,
146 // This covers other storage classes, but also accessing vectors and
147 // matrices by value, where no pointer is involved.
148 _ => self.index,
149 }
150 }
151
152 /// Return `true` if any of `self`'s policies are `policy`.
contains(&self, policy: BoundsCheckPolicy) -> bool153 pub fn contains(&self, policy: BoundsCheckPolicy) -> bool {
154 self.index == policy || self.buffer == policy || self.image == policy
155 }
156 }
157
158 /// An index that may be statically known, or may need to be computed at runtime.
159 ///
160 /// This enum lets us handle both [`Access`] and [`AccessIndex`] expressions
161 /// with the same code.
162 ///
163 /// [`Access`]: crate::Expression::Access
164 /// [`AccessIndex`]: crate::Expression::AccessIndex
165 #[derive(Clone, Copy, Debug)]
166 pub enum GuardedIndex {
167 Known(u32),
168 Expression(Handle<crate::Expression>),
169 }
170
171 /// Build a set of expressions used as indices, to cache in temporary variables when
172 /// emitted.
173 ///
174 /// Given the bounds-check policies `policies`, construct a `BitSet` containing the handle
175 /// indices of all the expressions in `function` that are ever used as guarded indices
176 /// under the [`ReadZeroSkipWrite`] policy. The `module` argument must be the module to
177 /// which `function` belongs, and `info` should be that function's analysis results.
178 ///
179 /// Such index expressions will be used twice in the generated code: first for the
180 /// comparison to see if the index is in bounds, and then for the access itself, should
181 /// the comparison succeed. To avoid computing the expressions twice, they should be
182 /// cached in temporary variables.
183 ///
184 /// Why do we need to build such a set before processing a function's statements? Whether
185 /// an expression needs to be cached depends on whether it appears as the [`index`]
186 /// operand of any [`Access`] expression, and on the index bounds check policies that
187 /// apply to those accesses. But [`Emit`] statements just identify a range of expressions
188 /// by index; there's no good way to tell what an expression is used for. The only way to
189 /// do it is to just iterate over all the expressions looking for relevant `Access`
190 /// expressions --- which is what this function does.
191 ///
192 /// Simple expressions like variable loads and constants don't make sense to cache: it's
193 /// no better than just re-evaluating them. But constants are not covered by `Emit`
194 /// statements, and `Load`s are always cached to ensure they occur at the right time, so
195 /// we don't bother filtering them out from this set.
196 ///
197 /// [`ReadZeroSkipWrite`]: BoundsCheckPolicy::ReadZeroSkipWrite
198 /// [`index`]: crate::Expression::Access::index
199 /// [`Access`]: crate::Expression::Access
200 /// [`Emit`]: crate::Statement::Emit
find_checked_indexes( module: &crate::Module, function: &crate::Function, info: &crate::valid::FunctionInfo, policies: BoundsCheckPolicies, ) -> BitSet201 pub fn find_checked_indexes(
202 module: &crate::Module,
203 function: &crate::Function,
204 info: &crate::valid::FunctionInfo,
205 policies: BoundsCheckPolicies,
206 ) -> BitSet {
207 use crate::Expression as Ex;
208
209 let mut guarded_indices = BitSet::new();
210
211 // Don't bother scanning if we never need `ReadZeroSkipWrite`.
212 if policies.contains(BoundsCheckPolicy::ReadZeroSkipWrite) {
213 for (_handle, expr) in function.expressions.iter() {
214 // There's no need to handle `AccessIndex` expressions, as their
215 // indices never need to be cached.
216 if let Ex::Access { base, index } = *expr {
217 if policies.choose_policy(base, &module.types, info)
218 == BoundsCheckPolicy::ReadZeroSkipWrite
219 && access_needs_check(
220 base,
221 GuardedIndex::Expression(index),
222 module,
223 function,
224 info,
225 )
226 .is_some()
227 {
228 guarded_indices.insert(index.index());
229 }
230 }
231 }
232 }
233
234 guarded_indices
235 }
236
237 /// Determine whether `index` is statically known to be in bounds for `base`.
238 ///
239 /// If we can't be sure that the index is in bounds, return the limit within
240 /// which valid indices must fall.
241 ///
242 /// The return value is one of the following:
243 ///
244 /// - `Some(Known(n))` indicates that `n` is the largest valid index.
245 ///
246 /// - `Some(Computed(global))` indicates that the largest valid index is one
247 /// less than the length of the array that is the last member of the
248 /// struct held in `global`.
249 ///
250 /// - `None` indicates that the index need not be checked, either because it
251 /// is statically known to be in bounds, or because the applicable policy
252 /// is `Unchecked`.
253 ///
254 /// This function only handles subscriptable types: arrays, vectors, and
255 /// matrices. It does not handle struct member indices; those never require
256 /// run-time checks, so it's best to deal with them further up the call
257 /// chain.
access_needs_check( base: Handle<crate::Expression>, mut index: GuardedIndex, module: &crate::Module, function: &crate::Function, info: &crate::valid::FunctionInfo, ) -> Option<IndexableLength>258 pub fn access_needs_check(
259 base: Handle<crate::Expression>,
260 mut index: GuardedIndex,
261 module: &crate::Module,
262 function: &crate::Function,
263 info: &crate::valid::FunctionInfo,
264 ) -> Option<IndexableLength> {
265 let base_inner = info[base].ty.inner_with(&module.types);
266 // Unwrap safety: `Err` here indicates unindexable base types and invalid
267 // length constants, but `access_needs_check` is only used by back ends, so
268 // validation should have caught those problems.
269 let length = base_inner.indexable_length(module).unwrap();
270 index.try_resolve_to_constant(function, module);
271 if let (&GuardedIndex::Known(index), &IndexableLength::Known(length)) = (&index, &length) {
272 if index < length {
273 // Index is statically known to be in bounds, no check needed.
274 return None;
275 }
276 };
277
278 Some(length)
279 }
280
281 impl GuardedIndex {
282 /// Make A `GuardedIndex::Known` from a `GuardedIndex::Expression` if possible.
283 ///
284 /// If the expression is a [`Constant`] whose value is a non-specialized, scalar
285 /// integer constant that can be converted to a `u32`, do so and return a
286 /// `GuardedIndex::Known`. Otherwise, return the `GuardedIndex::Expression`
287 /// unchanged.
288 ///
289 /// Return values that are already `Known` unchanged.
290 ///
291 /// [`Constant`]: crate::Expression::Constant
try_resolve_to_constant(&mut self, function: &crate::Function, module: &crate::Module)292 fn try_resolve_to_constant(&mut self, function: &crate::Function, module: &crate::Module) {
293 if let GuardedIndex::Expression(expr) = *self {
294 if let crate::Expression::Constant(handle) = function.expressions[expr] {
295 if let Some(value) = module.constants[handle].to_array_length() {
296 *self = GuardedIndex::Known(value);
297 }
298 }
299 }
300 }
301 }
302
303 impl crate::TypeInner {
304 /// Return the length of a subscriptable type.
305 ///
306 /// The `self` parameter should be a handle to a vector, matrix, or array
307 /// type, a pointer to one of those, or a value pointer. Arrays may be
308 /// fixed-size, dynamically sized, or sized by a specializable constant.
309 /// This function does not handle struct member references, as with
310 /// `AccessIndex`.
311 ///
312 /// The value returned is appropriate for bounds checks on subscripting.
313 ///
314 /// Return an error if `self` does not describe a subscriptable type at all.
indexable_length(&self, module: &crate::Module) -> Result<IndexableLength, ProcError>315 pub fn indexable_length(&self, module: &crate::Module) -> Result<IndexableLength, ProcError> {
316 use crate::TypeInner as Ti;
317 let known_length = match *self {
318 Ti::Vector { size, .. } => size as _,
319 Ti::Matrix { columns, .. } => columns as _,
320 Ti::Array { size, .. } => {
321 return size.to_indexable_length(module);
322 }
323 Ti::ValuePointer {
324 size: Some(size), ..
325 } => size as _,
326 Ti::Pointer { base, .. } => {
327 // When assigning types to expressions, ResolveContext::Resolve
328 // does a separate sub-match here instead of a full recursion,
329 // so we'll do the same.
330 let base_inner = &module.types[base].inner;
331 match *base_inner {
332 Ti::Vector { size, .. } => size as _,
333 Ti::Matrix { columns, .. } => columns as _,
334 Ti::Array { size, .. } => return size.to_indexable_length(module),
335 _ => return Err(ProcError::TypeNotIndexable),
336 }
337 }
338 _ => return Err(ProcError::TypeNotIndexable),
339 };
340 Ok(IndexableLength::Known(known_length))
341 }
342 }
343
344 /// The number of elements in an indexable type.
345 ///
346 /// This summarizes the length of vectors, matrices, and arrays in a way that is
347 /// convenient for indexing and bounds-checking code.
348 #[derive(Debug)]
349 pub enum IndexableLength {
350 /// Values of this type always have the given number of elements.
351 Known(u32),
352
353 /// The number of elements is determined at runtime.
354 Dynamic,
355 }
356
357 impl crate::ArraySize {
to_indexable_length(self, module: &crate::Module) -> Result<IndexableLength, ProcError>358 pub fn to_indexable_length(self, module: &crate::Module) -> Result<IndexableLength, ProcError> {
359 use crate::Constant as K;
360 Ok(match self {
361 Self::Constant(k) => match module.constants[k] {
362 K {
363 specialization: Some(_),
364 ..
365 } => {
366 // Specializable constants are not supported as array lengths.
367 // See valid::TypeError::UnsupportedSpecializedArrayLength.
368 return Err(ProcError::InvalidArraySizeConstant(k));
369 }
370 ref unspecialized => {
371 let length = unspecialized
372 .to_array_length()
373 .ok_or(ProcError::InvalidArraySizeConstant(k))?;
374 IndexableLength::Known(length)
375 }
376 },
377 Self::Dynamic => IndexableLength::Dynamic,
378 })
379 }
380 }
381