strided_basic/erased.rs
1use crate::cost::KernelClass;
2use crate::erased_common::*;
3use crate::*;
4use core::mem::MaybeUninit;
5use num_complex::{Complex32, Complex64};
6use num_traits::{One, Zero};
7mod arg_reduce;
8mod line;
9mod norm;
10mod reduce_kernel;
11mod scan;
12
13pub use arg_reduce::{ArgReduceOp, ErasedArgReducePlan};
14pub use norm::{ErasedNormPlan, NormKind, NormSpec};
15pub use scan::{ErasedScanPlan, ScanOp, ScanOptions};
16
17use reduce_kernel::{
18 reduce_axes_range, reduce_full_range, AxesRange, FullTraversal, MaxKernel, MinKernel,
19 ReassociatedProductKernel, ReduceKernel, StableProductKernel, StableProductScalar, SumKernel,
20 SumSquaresKernel,
21};
22
23trait ReduceWriter<T> {
24 fn offset(&self) -> isize;
25 /// # Safety
26 /// The pointer may only be used within the validated destination extent.
27 unsafe fn ptr(&mut self) -> *mut T;
28 fn extent(&self) -> usize;
29 /// # Safety
30 /// The offset must be an in-bounds logical reduction destination offset.
31 unsafe fn write_at(&mut self, offset: isize, value: T) {
32 debug_assert!(offset >= 0 && (offset as usize) < self.extent());
33 // SAFETY: reduction layout validation proves the logical offset.
34 unsafe { self.ptr().offset(offset).write(value) }
35 }
36}
37
38struct RawReduceWriter<'a, T> {
39 ptr: *mut T,
40 extent: usize,
41 offset: isize,
42 _marker: core::marker::PhantomData<&'a mut [MaybeUninit<T>]>,
43}
44
45impl<'a, T> ReduceWriter<T> for RawReduceWriter<'a, T> {
46 fn offset(&self) -> isize {
47 self.offset
48 }
49 unsafe fn ptr(&mut self) -> *mut T {
50 self.ptr
51 }
52 fn extent(&self) -> usize {
53 self.extent
54 }
55}
56
57/// Dtype-erased wrapper around [`CopyPlan`].
58#[derive(Clone, Debug)]
59pub struct ErasedCopyPlan {
60 dtype: KernelDType,
61 plan: CopyPlan,
62}
63
64/// Dtype-erased concatenate wrapper.
65#[derive(Clone, Debug)]
66pub struct ErasedConcatenatePlan {
67 dtype: KernelDType,
68 plan: ConcatenatePlan,
69}
70
71impl ErasedCopyPlan {
72 /// Compile a copy plan for one dtype and layout pair.
73 ///
74 /// # Errors
75 ///
76 /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
77 /// `dst_strides`, and `src_strides` do not all have the same length,
78 /// [`StridedError::OffsetOverflow`] when the element count does not fit
79 /// `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
80 /// destination layout cannot be proven injective (aliasing elements, or a
81 /// span the check cannot represent). The dtype
82 /// is only stored here; [`execute`](Self::execute) checks it.
83 pub fn compile(
84 dtype: KernelDType,
85 dims: &[usize],
86 dst_strides: &[isize],
87 src_strides: &[isize],
88 ) -> Result<Self> {
89 Ok(Self {
90 dtype,
91 plan: CopyPlan::compile(dims, dst_strides, src_strides)?,
92 })
93 }
94
95 #[inline]
96 pub fn dtype(&self) -> KernelDType {
97 self.dtype
98 }
99
100 /// `dest = src` through a non-generic dtype-erased replay boundary.
101 ///
102 /// # Errors
103 ///
104 /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
105 /// different dtype than the plan, and
106 /// [`StridedError::PlanLayoutMismatch`] when a view does not carry the
107 /// compiled extents and strides. Nothing is written unless every check
108 /// succeeds.
109 pub fn execute(
110 &self,
111 dest: &mut ErasedRawStridedMut<'_>,
112 src: &ErasedRawStridedRef<'_>,
113 exec: Exec<'_>,
114 ) -> Result<()> {
115 self.check_dtype(dest.dtype())?;
116 self.check_dtype(src.dtype())?;
117
118 match self.dtype {
119 KernelDType::F32 => execute_copy::<f32>(&self.plan, dest, src, exec),
120 KernelDType::F64 => execute_copy::<f64>(&self.plan, dest, src, exec),
121 KernelDType::I32 => execute_copy::<i32>(&self.plan, dest, src, exec),
122 KernelDType::I64 => execute_copy::<i64>(&self.plan, dest, src, exec),
123 KernelDType::Bool => execute_copy::<bool>(&self.plan, dest, src, exec),
124 KernelDType::C32 => execute_copy::<Complex32>(&self.plan, dest, src, exec),
125 KernelDType::C64 => execute_copy::<Complex64>(&self.plan, dest, src, exec),
126 _ => Err(StridedError::UnsupportedDType {
127 dtype: self.dtype.label(),
128 }),
129 }
130 }
131
132 fn check_dtype(&self, actual: KernelDType) -> Result<()> {
133 if actual != self.dtype {
134 return Err(StridedError::DTypeMismatch {
135 expected: self.dtype.label(),
136 actual: actual.label(),
137 });
138 }
139 Ok(())
140 }
141}
142
143impl ErasedConcatenatePlan {
144 /// Validate and store a concatenate plan for one dtype and fixed layout set.
145 ///
146 /// # Errors
147 ///
148 /// Returns [`StridedError::UnsupportedArity`] when no input is given,
149 /// [`StridedError::RankMismatch`] when
150 /// `input_dims` and `input_strides` list different numbers of layouts or
151 /// an input rank differs from the first input's rank,
152 /// [`StridedError::StrideLengthMismatch`] when a stride list does not
153 /// match its dimension list, [`StridedError::InvalidAxis`] when `axis` is
154 /// outside the rank, [`StridedError::ShapeMismatch`] when a
155 /// non-concatenated extent differs or the destination is not the
156 /// concatenation of the inputs,
157 /// [`StridedError::NonInjectiveOutputLayout`] when the destination layout
158 /// maps two logical indices onto one offset, and
159 /// [`StridedError::OffsetOverflow`] when a segment length or base offset
160 /// cannot be represented.
161 pub fn compile(
162 dtype: KernelDType,
163 input_dims: &[&[usize]],
164 input_strides: &[&[isize]],
165 dest_dims: &[usize],
166 dest_strides: &[isize],
167 axis: usize,
168 ) -> Result<Self> {
169 check_static_indexing_dtype(dtype)?;
170 Ok(Self {
171 dtype,
172 plan: ConcatenatePlan::compile(
173 input_dims,
174 input_strides,
175 dest_dims,
176 dest_strides,
177 axis,
178 )?,
179 })
180 }
181
182 #[inline]
183 pub fn dtype(&self) -> KernelDType {
184 self.dtype
185 }
186
187 #[inline]
188 pub fn plan(&self) -> &ConcatenatePlan {
189 &self.plan
190 }
191
192 /// Execute concatenate into an erased output descriptor.
193 ///
194 /// # Errors
195 ///
196 /// Returns [`StridedError::DTypeMismatch`] when the destination or any
197 /// input carries a different dtype than the plan,
198 /// [`StridedError::RankMismatch`] when the number of inputs differs from
199 /// the compiled one, [`StridedError::PlanLayoutMismatch`] when the
200 /// destination or an input does not carry its compiled extents and
201 /// strides, and [`StridedError::OffsetOverflow`] when a segment's
202 /// destination offset cannot be expressed in `isize`. Every check runs
203 /// before the first segment is written.
204 pub fn execute(
205 &self,
206 dest: &mut ErasedRawStridedMut<'_>,
207 inputs: &[ErasedRawStridedRef<'_>],
208 exec: Exec<'_>,
209 ) -> Result<()> {
210 check_dtype(self.dtype, dest.dtype())?;
211 for input in inputs {
212 check_dtype(self.dtype, input.dtype())?;
213 }
214
215 match self.dtype {
216 KernelDType::F32 => execute_concatenate::<f32>(&self.plan, dest, inputs, exec),
217 KernelDType::F64 => execute_concatenate::<f64>(&self.plan, dest, inputs, exec),
218 KernelDType::I32 => execute_concatenate::<i32>(&self.plan, dest, inputs, exec),
219 KernelDType::I64 => execute_concatenate::<i64>(&self.plan, dest, inputs, exec),
220 KernelDType::Bool => execute_concatenate::<bool>(&self.plan, dest, inputs, exec),
221 KernelDType::C32 => execute_concatenate::<Complex32>(&self.plan, dest, inputs, exec),
222 KernelDType::C64 => execute_concatenate::<Complex64>(&self.plan, dest, inputs, exec),
223 _ => Err(StridedError::UnsupportedDType {
224 dtype: self.dtype.label(),
225 }),
226 }
227 }
228
229 /// Execute concatenate as a full overwrite of uninitialized output storage.
230 /// On success, every reachable destination slot is fully overwritten;
231 /// unreachable holes are neither read nor initialized. Validation errors
232 /// are returned before any destination write. A panic during execution
233 /// may leave a partially initialized `MaybeUninit` destination, which is
234 /// still safely droppable; no readable value is promised for unwritten
235 /// reachable slots.
236 ///
237 /// # Errors
238 ///
239 /// Returns [`StridedError::DTypeMismatch`] when the destination or any
240 /// input carries a different dtype than the plan,
241 /// [`StridedError::RankMismatch`] when the number of inputs differs from
242 /// the compiled one, [`StridedError::OverlappingInputOutput`] when an
243 /// input allocation overlaps the destination,
244 /// [`StridedError::InvalidBoolByte`] when `bool` input bytes are not 0 or
245 /// 1, [`StridedError::PlanLayoutMismatch`] when the destination or an
246 /// input does not carry its compiled extents and strides, and
247 /// [`StridedError::OffsetOverflow`] when a segment's destination offset
248 /// cannot be expressed in `isize`. Everything above is returned before any
249 /// destination write.
250 pub fn execute_uninit(
251 &self,
252 dest: &mut ErasedRawStridedUninitMut<'_>,
253 inputs: &[ErasedRawStridedPtr<'_>],
254 exec: Exec<'_>,
255 ) -> Result<()> {
256 check_dtype(self.dtype, dest.dtype())?;
257 if inputs.len() != self.plan.input_count() {
258 return Err(StridedError::RankMismatch(
259 inputs.len(),
260 self.plan.input_count(),
261 ));
262 }
263 for input in inputs {
264 check_dtype(self.dtype, input.dtype())?;
265 }
266 for (position, input) in inputs.iter().enumerate() {
267 validate_uninit_no_overlap(dest, input, position)?;
268 }
269 for input in inputs {
270 // SAFETY: input/output overlap was rejected before forming references.
271 unsafe { input.try_as_ref_after_no_overlap() }?;
272 }
273
274 match self.dtype {
275 KernelDType::F32 => execute_concatenate_uninit::<f32>(&self.plan, dest, inputs, exec),
276 KernelDType::F64 => execute_concatenate_uninit::<f64>(&self.plan, dest, inputs, exec),
277 KernelDType::I32 => execute_concatenate_uninit::<i32>(&self.plan, dest, inputs, exec),
278 KernelDType::I64 => execute_concatenate_uninit::<i64>(&self.plan, dest, inputs, exec),
279 KernelDType::Bool => execute_concatenate_uninit::<bool>(&self.plan, dest, inputs, exec),
280 KernelDType::C32 => {
281 execute_concatenate_uninit::<Complex32>(&self.plan, dest, inputs, exec)
282 }
283 KernelDType::C64 => {
284 execute_concatenate_uninit::<Complex64>(&self.plan, dest, inputs, exec)
285 }
286 _ => Err(StridedError::UnsupportedDType {
287 dtype: self.dtype.label(),
288 }),
289 }
290 }
291}
292
293/// Runtime reduction operation for dtype-erased full reductions.
294#[non_exhaustive]
295#[derive(Clone, Copy, Debug, Eq, PartialEq)]
296pub enum ReduceOp {
297 Sum,
298 Product,
299 /// Reassociated, overflow/underflow-safe product.
300 ///
301 /// Tracks a signed mantissa and an exact integer exponent per lane, so
302 /// factors outside the dtype range do not overflow or underflow a partial.
303 /// The reduction is reassociated and threaded like [`Self::Sum`].
304 ///
305 /// A zero, subnormal, infinite or NaN input cannot be represented by the
306 /// exponent-tracked accumulator; the affected output is then recomputed in
307 /// source order, keeping IEEE propagation (`0 * inf = NaN`, a zero or an
308 /// infinity result) identical to the sequential fold. For integers this is
309 /// the reassociated wrapping product and for complex dtypes the
310 /// source-order product.
311 StableProduct,
312 /// Sum of same-dtype rounded squares.
313 ///
314 /// Each input is first multiplied by itself without FMA contraction, then
315 /// accumulated under the same association policy as [`Self::Sum`].
316 SumSquares,
317 /// NaN-propagating maximum for `f32`/`f64`, ordered maximum for
318 /// `i32`/`i64`.
319 ///
320 /// Any NaN operand makes the result the canonical NaN of the dtype. The
321 /// identity written for an empty reduction is `-inf` for floats and the
322 /// dtype minimum for integers. Complex and `bool` dtypes are rejected.
323 /// When the reduced values contain both `-0.0` and `+0.0`, which zero is
324 /// returned is unspecified.
325 Max,
326 /// NaN-propagating minimum for `f32`/`f64`, ordered minimum for
327 /// `i32`/`i64`.
328 ///
329 /// Any NaN operand makes the result the canonical NaN of the dtype. The
330 /// identity written for an empty reduction is `+inf` for floats and the
331 /// dtype maximum for integers. Complex and `bool` dtypes are rejected.
332 /// When the reduced values contain both `-0.0` and `+0.0`, which zero is
333 /// returned is unspecified.
334 Min,
335}
336
337/// Dtype-erased reduction wrapper.
338///
339/// This is the erased replay boundary for full-tensor scalar reductions and
340/// axis reductions with a fixed output layout. It supports only operations with
341/// an unambiguous identity value in the selected dtype.
342///
343/// # Evaluation order
344///
345/// The op is matched once per execution; every loop runs a kernel
346/// specialized for one `(dtype, op)` pair. Integer results are exact
347/// (wrapping) and [`ReduceOp::Max`] / [`ReduceOp::Min`] do not depend on
348/// order, so the rules below only affect the rounding of floating point and
349/// complex [`ReduceOp::Sum`], [`ReduceOp::Product`], [`ReduceOp::StableProduct`]
350/// and [`ReduceOp::SumSquares`]. Two details of float max and min follow the
351/// visit order: a NaN input makes the result NaN, but which NaN (payload and
352/// sign) is returned is unspecified, and when the extremum is a zero its sign
353/// is unspecified if both `+0.0` and `-0.0` occur.
354///
355/// [`ReduceOp::Product`] is the reassociated product, matching PyTorch: it
356/// splits each run into lanes, uses the SIMD product where available, threads a
357/// full reduction, and combines the partials in a fixed tree. It is fast and
358/// never recomputes an output, but reassociating can overflow a lane to `inf`
359/// and underflow another to `0`, whose `inf * 0` combine is `NaN`; an
360/// alternating `2.0`/`0.5` input at `2^600`/`2^-600` scale can therefore give
361/// `NaN` where the source-order product is representable (tenferro-rs#2150).
362///
363/// [`ReduceOp::StableProduct`] avoids that. For `f32`/`f64` it tracks a signed
364/// mantissa and an exact integer exponent per lane and across runs and workers,
365/// so a partial cannot overflow or underflow; the final value is scaled with a
366/// correctly rounded `ldexp`. An input that is zero, subnormal, infinite or NaN
367/// cannot be represented this way, so an output that saw one is recomputed in
368/// source order, preserving IEEE propagation. It is reassociated and threaded
369/// like [`ReduceOp::Product`] otherwise. For integers it is the reassociated
370/// wrapping product and for complex dtypes the source-order product.
371///
372/// * Full reductions (from [`Self::compile`], or [`Self::compile_axes`]
373/// with every axis reduced) visit the source in a layout derived order:
374/// extent one axes are dropped, the rest are ordered by increasing
375/// absolute stride and contiguous axes are fused into runs. Each run is
376/// reduced by the SIMD kernel (unit stride, `simd` feature), a sixteen
377/// lane kernel (other unit stride runs) or an eight lane kernel (strided
378/// runs), and runs are combined left to right. A dense column major
379/// source therefore reduces exactly like one contiguous slice.
380/// * With a budget above one and a region whose serial time (the `Reduce`
381/// class of `execution::KernelClass`) repays the sections of a tree split, a
382/// full reduction splits the traversal into one deterministic range per
383/// task. Each range runs the same run kernel as the serial path and
384/// the partials are combined in a fixed tree. The result is bitwise
385/// repeatable for a fixed layout and budget, but may differ between
386/// budgets and from the serial result.
387/// * Axis reductions with kept axes compute every output independently, so
388/// the result never depends on the token or its budget. Each output
389/// folds its reduced elements sequentially in caller reduced axis order,
390/// except that a unit stride leading reduced run (after fusing adjacent
391/// reduced axes) of length at least 16 is reduced by the contiguous run
392/// kernel, with runs folded in order. When instead the leading kept axis
393/// has unit stride, adjacent outputs are accumulated as a block from one
394/// contiguous source run per reduced element; each output still folds in
395/// caller reduced axis order.
396#[derive(Clone, Debug)]
397pub struct ErasedReducePlan {
398 dtype: KernelDType,
399 op: ReduceOp,
400 layout: ReduceLayout,
401}
402
403// Private plan enum: `Axes` carries the per-axis tables inline on purpose, so the
404// reduce hot path reads them without a second indirection.
405#[allow(clippy::large_enum_variant)]
406#[derive(Clone, Debug)]
407enum ReduceLayout {
408 Full {
409 dims: crate::inline::InlineVec<usize>,
410 src_strides: crate::inline::InlineVec<isize>,
411 traversal: FullTraversal,
412 },
413 Axes {
414 src_dims: crate::inline::InlineVec<usize>,
415 src_strides: crate::inline::InlineVec<isize>,
416 dest_dims: crate::inline::InlineVec<usize>,
417 dest_strides: crate::inline::InlineVec<isize>,
418 outer_axes: crate::inline::InlineVec<ReduceOuterAxis>,
419 inner_axes: crate::inline::InlineVec<ReduceInnerAxis>,
420 dest_total: usize,
421 reduce_total: usize,
422 /// Set when every source axis is reduced; the plan then runs the
423 /// full-reduction traversal.
424 full: Option<FullTraversal>,
425 },
426}
427
428#[derive(Clone, Copy, Debug, Default)]
429struct ReduceOuterAxis {
430 extent: usize,
431 source_step: isize,
432 source_reset: isize,
433 dest_step: isize,
434 dest_reset: isize,
435}
436#[derive(Clone, Copy, Debug, Default)]
437struct ReduceInnerAxis {
438 extent: usize,
439 source_step: isize,
440 source_reset: isize,
441}
442impl ReduceLayout {
443 fn src_dims(&self) -> &[usize] {
444 match self {
445 Self::Full { dims, .. } => dims,
446 Self::Axes { src_dims, .. } => src_dims,
447 }
448 }
449
450 fn src_strides(&self) -> &[isize] {
451 match self {
452 Self::Full { src_strides, .. } | Self::Axes { src_strides, .. } => src_strides,
453 }
454 }
455
456 fn check_src_layout(&self, src: &ErasedRawStridedRef<'_>) -> Result<()> {
457 if src.dims() != self.src_dims() || src.strides() != self.src_strides() {
458 return Err(StridedError::PlanLayoutMismatch);
459 }
460 Ok(())
461 }
462}
463
464#[derive(Clone, Copy, Debug)]
465struct AxesLayout<'a> {
466 outer_axes: &'a [ReduceOuterAxis],
467 inner_axes: &'a [ReduceInnerAxis],
468 dest_total: usize,
469 reduce_total: usize,
470}
471
472impl ErasedReducePlan {
473 /// Validate and store a full-reduction plan for one dtype and source layout.
474 ///
475 /// # Errors
476 ///
477 /// Returns [`StridedError::UnsupportedDType`] when `op` has no identity
478 /// in `dtype`: [`ReduceOp::SumSquares`] outside `f32`/`f64`,
479 /// [`ReduceOp::Max`] or [`ReduceOp::Min`] for a complex or `bool` dtype,
480 /// and every op for `bool`. Returns
481 /// [`StridedError::StrideLengthMismatch`] when `dims` and `src_strides`
482 /// have different lengths, and [`StridedError::OffsetOverflow`] when the
483 /// element count overflows `usize` or the fused traversal arithmetic
484 /// (extents, steps, and negated resets) does not fit `isize`.
485 pub fn compile(
486 dtype: KernelDType,
487 op: ReduceOp,
488 dims: &[usize],
489 src_strides: &[isize],
490 ) -> Result<Self> {
491 check_reduce_op_dtype(dtype, op)?;
492 if dims.len() != src_strides.len() {
493 return Err(StridedError::StrideLengthMismatch);
494 }
495 checked_total_len(dims)?;
496 let traversal = FullTraversal::compile(dims, src_strides)?;
497 Ok(Self {
498 dtype,
499 op,
500 layout: ReduceLayout::Full {
501 dims: dims.into(),
502 src_strides: src_strides.into(),
503 traversal,
504 },
505 })
506 }
507
508 /// Validate and store an axis-reduction plan for one dtype and fixed source/output layouts.
509 ///
510 /// `axes` names the source axes reduced away. Output dimensions must be the
511 /// remaining source dimensions in source-axis order. When all axes are
512 /// reduced, any output layout with exactly one reachable element is accepted.
513 ///
514 /// # Errors
515 ///
516 /// Returns [`StridedError::UnsupportedDType`] when `op` has no identity
517 /// in `dtype` (see [`Self::compile`]),
518 /// [`StridedError::StrideLengthMismatch`] when a stride list does not
519 /// match its dimension list, [`StridedError::OffsetOverflow`] when an
520 /// element count, a layout span, a reset or a fused extent does not fit
521 /// `usize`/`isize`, [`StridedError::NonInjectiveOutputLayout`] when the
522 /// destination layout cannot be proven injective (aliasing elements, or a
523 /// span the check cannot represent),
524 /// [`StridedError::InvalidAxis`] when `axes` repeats an axis or names one
525 /// outside the source rank, and [`StridedError::ShapeMismatch`] when
526 /// `dest_dims` is not the kept source extents in source-axis order (or,
527 /// when every axis is reduced, does not hold exactly one element).
528 // Inert: `compile_axes` takes 7 arguments and clippy's `too_many_arguments`
529 // fires only above 7, so this allow suppresses nothing; it is left in place.
530 #[allow(clippy::too_many_arguments)]
531 pub fn compile_axes(
532 dtype: KernelDType,
533 op: ReduceOp,
534 src_dims: &[usize],
535 src_strides: &[isize],
536 dest_dims: &[usize],
537 dest_strides: &[isize],
538 axes: &[usize],
539 ) -> Result<Self> {
540 check_reduce_op_dtype(dtype, op)?;
541 if src_dims.len() != src_strides.len() || dest_dims.len() != dest_strides.len() {
542 return Err(StridedError::StrideLengthMismatch);
543 }
544 checked_total_len(src_dims)?;
545 check_reduce_layout_offset_arithmetic(src_dims, src_strides)?;
546 let dest_total = checked_total_len(dest_dims)?;
547 check_reduce_layout_offset_arithmetic(dest_dims, dest_strides)?;
548 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
549 return Err(StridedError::NonInjectiveOutputLayout);
550 }
551 validate_unique_axes(axes, src_dims.len())?;
552
553 let kept_axes: crate::inline::InlineVec<usize> = (0..src_dims.len())
554 .filter(|axis| !axes.contains(axis))
555 .collect();
556 let expected_dest_dims: crate::inline::InlineVec<usize> =
557 kept_axes.iter().map(|&axis| src_dims[axis]).collect();
558 if expected_dest_dims.is_empty() {
559 if dest_total != 1 {
560 return Err(StridedError::ShapeMismatch(
561 dest_dims.to_vec(),
562 expected_dest_dims.to_vec(),
563 ));
564 }
565 } else if dest_dims != expected_dest_dims.as_slice() {
566 return Err(StridedError::ShapeMismatch(
567 dest_dims.to_vec(),
568 expected_dest_dims.to_vec(),
569 ));
570 }
571
572 let reduce_total = axes
573 .iter()
574 .try_fold(1usize, |total, &axis| total.checked_mul(src_dims[axis]))
575 .ok_or(StridedError::OffsetOverflow)?;
576 let outer_axes = compress_reduce_outer_axes(
577 kept_axes
578 .iter()
579 .enumerate()
580 .map(|(dest_axis, &src_axis)| {
581 let extent = src_dims[src_axis];
582 Ok(ReduceOuterAxis {
583 extent,
584 source_step: src_strides[src_axis],
585 source_reset: checked_reduce_reset(extent, src_strides[src_axis])?,
586 dest_step: dest_strides[dest_axis],
587 dest_reset: checked_reduce_reset(extent, dest_strides[dest_axis])?,
588 })
589 })
590 .collect::<Result<crate::inline::InlineVec<_>>>()?,
591 )?;
592 let inner_axes = compress_reduce_inner_axes(
593 axes.iter()
594 .map(|&src_axis| {
595 let extent = src_dims[src_axis];
596 Ok(ReduceInnerAxis {
597 extent,
598 source_step: src_strides[src_axis],
599 source_reset: checked_reduce_reset(extent, src_strides[src_axis])?,
600 })
601 })
602 .collect::<Result<crate::inline::InlineVec<_>>>()?,
603 )?;
604 let full = if kept_axes.is_empty() {
605 Some(FullTraversal::compile(src_dims, src_strides)?)
606 } else {
607 None
608 };
609 Ok(Self {
610 dtype,
611 op,
612 layout: ReduceLayout::Axes {
613 src_dims: src_dims.into(),
614 src_strides: src_strides.into(),
615 dest_dims: dest_dims.into(),
616 dest_strides: dest_strides.into(),
617 outer_axes,
618 inner_axes,
619 dest_total,
620 reduce_total,
621 full,
622 },
623 })
624 }
625
626 #[inline]
627 pub fn dtype(&self) -> KernelDType {
628 self.dtype
629 }
630
631 #[inline]
632 pub fn op(&self) -> ReduceOp {
633 self.op
634 }
635
636 /// Execute the reduction into an erased output descriptor.
637 ///
638 /// # Errors
639 ///
640 /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
641 /// different dtype than the plan,
642 /// [`StridedError::PlanLayoutMismatch`] when the source layout or the
643 /// axis-reduction destination layout does not match the compiled one,
644 /// [`StridedError::RankMismatch`] when a full reduction gets a
645 /// destination that does not hold exactly one element,
646 /// [`StridedError::OffsetOverflow`] when that destination's extents
647 /// multiply beyond `usize`. All are returned before the first destination
648 /// write.
649 pub fn execute(
650 &self,
651 dest: &mut ErasedRawStridedMut<'_>,
652 src: &ErasedRawStridedRef<'_>,
653 exec: Exec<'_>,
654 ) -> Result<()> {
655 check_dtype(self.dtype, dest.dtype())?;
656 check_dtype(self.dtype, src.dtype())?;
657 self.layout.check_src_layout(src)?;
658 match &self.layout {
659 ReduceLayout::Full { .. } => {
660 let dest_len = checked_total_len(dest.dims())?;
661 if dest_len != 1 {
662 return Err(StridedError::RankMismatch(dest_len, 1));
663 }
664 }
665 ReduceLayout::Axes {
666 dest_dims,
667 dest_strides,
668 ..
669 } => {
670 if dest.dims() != dest_dims.as_slice() || dest.strides() != dest_strides.as_slice()
671 {
672 return Err(StridedError::PlanLayoutMismatch);
673 }
674 }
675 }
676
677 let result = match self.dtype {
678 KernelDType::F32 => {
679 let mut writer = reduce_writer::<f32>(dest)?;
680 dispatch_reduce::<f32, _>(self.op, &self.layout, &mut writer, src, exec)
681 }
682 KernelDType::F64 => {
683 let mut writer = reduce_writer::<f64>(dest)?;
684 dispatch_reduce::<f64, _>(self.op, &self.layout, &mut writer, src, exec)
685 }
686 KernelDType::I32 => {
687 let mut writer = reduce_writer::<i32>(dest)?;
688 dispatch_reduce::<i32, _>(self.op, &self.layout, &mut writer, src, exec)
689 }
690 KernelDType::I64 => {
691 let mut writer = reduce_writer::<i64>(dest)?;
692 dispatch_reduce::<i64, _>(self.op, &self.layout, &mut writer, src, exec)
693 }
694 KernelDType::C32 => {
695 let mut writer = reduce_writer::<Complex32>(dest)?;
696 dispatch_reduce::<Complex32, _>(self.op, &self.layout, &mut writer, src, exec)
697 }
698 KernelDType::C64 => {
699 let mut writer = reduce_writer::<Complex64>(dest)?;
700 dispatch_reduce::<Complex64, _>(self.op, &self.layout, &mut writer, src, exec)
701 }
702 _ => Err(StridedError::UnsupportedDType {
703 dtype: self.dtype.label(),
704 }),
705 };
706 result
707 }
708
709 /// On success, every reachable destination slot is fully overwritten;
710 /// unreachable holes are neither read nor initialized. Validation errors
711 /// are returned before any destination write. A panic during execution
712 /// may leave a partially initialized `MaybeUninit` destination, which is
713 /// still safely droppable; no readable value is promised for unwritten
714 /// reachable slots.
715 ///
716 /// # Errors
717 ///
718 /// Returns [`StridedError::DTypeMismatch`] when `dest` or `src` carries a
719 /// different dtype than the plan,
720 /// [`StridedError::OverlappingInputOutput`] when the source allocation
721 /// overlaps the destination, [`StridedError::PlanLayoutMismatch`],
722 /// [`StridedError::RankMismatch`], and [`StridedError::OffsetOverflow`]
723 /// exactly as [`Self::execute`] does. All are returned before the first
724 /// destination write.
725 pub fn execute_uninit(
726 &self,
727 dest: &mut ErasedRawStridedUninitMut<'_>,
728 src: &ErasedRawStridedPtr<'_>,
729 exec: Exec<'_>,
730 ) -> Result<()> {
731 check_dtype(self.dtype, dest.dtype())?;
732 check_dtype(self.dtype, src.dtype())?;
733 validate_uninit_no_overlap(dest, src, 0)?;
734 // SAFETY: the owning erased entry rejected all input/output overlap before conversion.
735 let src = unsafe { src.try_as_ref_after_no_overlap() }?;
736 self.layout.check_src_layout(&src)?;
737 match &self.layout {
738 ReduceLayout::Full { .. } => {
739 let total = checked_total_len(dest.dims())?;
740 if total != 1 {
741 return Err(StridedError::RankMismatch(total, 1));
742 }
743 }
744 ReduceLayout::Axes {
745 dest_dims,
746 dest_strides,
747 ..
748 } => {
749 if dest.dims() != dest_dims.as_slice() || dest.strides() != dest_strides.as_slice()
750 {
751 return Err(StridedError::PlanLayoutMismatch);
752 }
753 }
754 }
755 macro_rules! run {
756 ($ty:ty) => {{
757 let mut writer = reduce_uninit_writer::<$ty>(dest)?;
758 dispatch_reduce::<$ty, _>(self.op, &self.layout, &mut writer, &src, exec)
759 }};
760 }
761 match self.dtype {
762 KernelDType::F32 => run!(f32),
763 KernelDType::F64 => run!(f64),
764 KernelDType::I32 => run!(i32),
765 KernelDType::I64 => run!(i64),
766 KernelDType::C32 => run!(Complex32),
767 KernelDType::C64 => run!(Complex64),
768 _ => Err(StridedError::UnsupportedDType {
769 dtype: self.dtype.label(),
770 }),
771 }
772 }
773}
774
775fn reduce_writer<'a, T>(dest: &'a mut ErasedRawStridedMut<'_>) -> Result<RawReduceWriter<'a, T>>
776where
777 T: KernelStorageElement,
778{
779 let offset = dest.offset();
780 let data = dest.data_as_mut::<T>()?;
781 let ptr = data.as_mut_ptr();
782 let extent = data.len();
783 Ok(RawReduceWriter {
784 ptr,
785 extent,
786 offset,
787 _marker: core::marker::PhantomData,
788 })
789}
790
791fn reduce_uninit_writer<'a, T>(
792 dest: &'a mut ErasedRawStridedUninitMut<'_>,
793) -> Result<RawReduceWriter<'a, T>>
794where
795 T: KernelStorageElement,
796{
797 let offset = dest.offset();
798 let data = dest.data_as_uninit_mut::<T>()?;
799 let ptr = data.as_mut_ptr().cast::<T>();
800 let extent = data.len();
801 Ok(RawReduceWriter {
802 ptr,
803 extent,
804 offset,
805 _marker: core::marker::PhantomData,
806 })
807}
808
809fn check_reduce_dtype(dtype: KernelDType) -> Result<()> {
810 match dtype {
811 KernelDType::F32
812 | KernelDType::F64
813 | KernelDType::I32
814 | KernelDType::I64
815 | KernelDType::C32
816 | KernelDType::C64 => Ok(()),
817 _ => Err(StridedError::UnsupportedDType {
818 dtype: dtype.label(),
819 }),
820 }
821}
822
823fn check_reduce_op_dtype(dtype: KernelDType, op: ReduceOp) -> Result<()> {
824 if op == ReduceOp::SumSquares && !matches!(dtype, KernelDType::F32 | KernelDType::F64) {
825 return Err(StridedError::UnsupportedDType {
826 dtype: dtype.label(),
827 });
828 }
829 if matches!(op, ReduceOp::Max | ReduceOp::Min)
830 && !matches!(
831 dtype,
832 KernelDType::F32 | KernelDType::F64 | KernelDType::I32 | KernelDType::I64
833 )
834 {
835 return Err(StridedError::UnsupportedDType {
836 dtype: dtype.label(),
837 });
838 }
839 check_reduce_dtype(dtype)
840}
841
842fn checked_total_len(dims: &[usize]) -> Result<usize> {
843 if dims.is_empty() {
844 return Ok(1);
845 }
846 dims.iter()
847 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
848 .ok_or(StridedError::OffsetOverflow)
849}
850
851fn execute_copy<T>(
852 plan: &CopyPlan,
853 dest: &mut ErasedRawStridedMut<'_>,
854 src: &ErasedRawStridedRef<'_>,
855 exec: Exec<'_>,
856) -> Result<()>
857where
858 T: Copy + Send + Sync + KernelStorageElement,
859{
860 let source_data = src.data_as::<T>()?;
861 let dest_dims = dest.dims();
862 let dest_strides = dest.strides();
863 let dest_offset = dest.offset();
864 let dest_data = dest.data_as_mut::<T>()?;
865 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
866 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
867 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
868 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
869 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
870 // every reachable offset is inside the buffer it hands to `new_unchecked`.
871 let source = unsafe {
872 RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
873 };
874 // SAFETY: `dest` is an erased descriptor built only by checked
875 // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
876 // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
877 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
878 // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
879 // and the `&mut` borrow keeps the storage unaliased for this call.
880 let mut dest =
881 unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
882 plan.execute(&mut dest, &source, exec)
883}
884
885fn execute_concatenate<T>(
886 plan: &ConcatenatePlan,
887 dest: &mut ErasedRawStridedMut<'_>,
888 inputs: &[ErasedRawStridedRef<'_>],
889 mut exec: Exec<'_>,
890) -> Result<()>
891where
892 T: Copy + Send + Sync + KernelStorageElement,
893{
894 if inputs.len() != plan.input_count() {
895 return Err(StridedError::RankMismatch(inputs.len(), plan.input_count()));
896 }
897 let dest_dims = dest.dims();
898 let dest_strides = dest.strides();
899 let dest_offset = dest.offset();
900 let dest_data = dest.data_as_mut::<T>()?;
901 // SAFETY: `dest` is an erased descriptor built only by checked
902 // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
903 // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
904 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
905 // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
906 // and the `&mut` borrow keeps the storage unaliased for this call.
907 let mut dest_ref =
908 unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
909 plan.check_dest_layout(&dest_ref)?;
910
911 for (position, input) in inputs.iter().enumerate() {
912 let input_data = input.data_as::<T>()?;
913 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
914 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
915 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
916 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
917 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
918 // every reachable offset is inside the buffer it hands to `new_unchecked`.
919 let input_ref = unsafe {
920 RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
921 };
922 plan.check_input_layout(position, &input_ref)?;
923 plan.segment_offset(position, dest_offset)?;
924 }
925 if plan.prefers_whole_plan(&exec)
926 && !inputs.is_empty()
927 && inputs.len() <= crate::inline::OPERAND_CAP
928 {
929 // Build the typed descriptors on the stack: `RawStridedRef` is `Copy`,
930 // so this stays allocation-free within the operand bound. The
931 // whole-plan entry then splits the concatenated space and the typed
932 // `try_execute_parallel` reads each segment straight from the plan.
933 let first_data = inputs[0].data_as::<T>()?;
934 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
935 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
936 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
937 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
938 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
939 // every reachable offset is inside the buffer it hands to `new_unchecked`.
940 let first = unsafe {
941 RawStridedRef::new_unchecked(
942 first_data,
943 inputs[0].dims(),
944 inputs[0].strides(),
945 inputs[0].offset(),
946 )
947 };
948 let mut input_refs = [first; crate::inline::OPERAND_CAP];
949 for (slot, input) in input_refs.iter_mut().zip(inputs) {
950 let input_data = input.data_as::<T>()?;
951 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
952 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
953 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
954 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
955 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
956 // every reachable offset is inside the buffer it hands to `new_unchecked`.
957 *slot = unsafe {
958 RawStridedRef::new_unchecked(
959 input_data,
960 input.dims(),
961 input.strides(),
962 input.offset(),
963 )
964 };
965 }
966 return plan.execute(&mut dest_ref, &input_refs[..inputs.len()], exec);
967 }
968 for (position, input) in inputs.iter().enumerate() {
969 let input_data = input.data_as::<T>()?;
970 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
971 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
972 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
973 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
974 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
975 // every reachable offset is inside the buffer it hands to `new_unchecked`.
976 let input_ref = unsafe {
977 RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
978 };
979 plan.execute_segment(position, &mut dest_ref, &input_ref, exec.reborrow())?;
980 }
981 Ok(())
982}
983
984fn execute_concatenate_uninit<T>(
985 plan: &ConcatenatePlan,
986 dest: &mut ErasedRawStridedUninitMut<'_>,
987 inputs: &[ErasedRawStridedPtr<'_>],
988 mut exec: Exec<'_>,
989) -> Result<()>
990where
991 T: Copy + Send + Sync + KernelStorageElement,
992{
993 let dest_dims = dest.dims();
994 let dest_strides = dest.strides();
995 let dest_offset = dest.offset();
996 let dest_data = dest.data_as_uninit_mut::<T>()?;
997 // SAFETY: `dest` is an erased descriptor built only by checked
998 // constructors (`ErasedRawStridedUninitMut::from_uninit_slice`/
999 // `from_raw_parts`, strided-view/src/raw.rs:745/:801), which ran
1000 // `validate_bounds` (strided-view/src/view.rs:187) on exactly these
1001 // dims/strides/offset; `data_as_uninit_mut::<T>` (raw.rs:828) re-checks the
1002 // dtype at that element count, writes go through `MaybeUninit`, and the
1003 // `&mut` borrow keeps the storage unaliased.
1004 let mut dest_ref =
1005 unsafe { RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset) };
1006 plan.check_dest_layout(&dest_ref)?;
1007
1008 for (position, input) in inputs.iter().enumerate() {
1009 // SAFETY: input/output overlap was rejected before forming references.
1010 let input = unsafe { input.try_as_ref_after_no_overlap() }?;
1011 let input_data = input.data_as::<T>()?;
1012 // SAFETY: this input reached `RawStridedRef` through
1013 // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1014 // re-ran the erased reference's raw constructor (`from_raw_parts`,
1015 // strided-view/src/raw.rs:449) → `validate_bounds`
1016 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset, and
1017 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1018 let input_ref = unsafe {
1019 RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
1020 };
1021 plan.check_input_layout(position, &input_ref)?;
1022 plan.segment_offset(position, dest_offset)?;
1023 }
1024 if plan.prefers_whole_plan(&exec)
1025 && !inputs.is_empty()
1026 && inputs.len() <= crate::inline::OPERAND_CAP
1027 {
1028 // SAFETY: input/output overlap was rejected before forming references.
1029 let first_erased = unsafe { inputs[0].try_as_ref_after_no_overlap() }?;
1030 let mut erased_refs = [first_erased; crate::inline::OPERAND_CAP];
1031 for (slot, input) in erased_refs.iter_mut().zip(inputs) {
1032 // SAFETY: input/output overlap was rejected before forming references.
1033 *slot = unsafe { input.try_as_ref_after_no_overlap() }?;
1034 }
1035 let first_data = erased_refs[0].data_as::<T>()?;
1036 // SAFETY: this input reached `RawStridedRef` through
1037 // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1038 // re-ran the erased reference's raw constructor (`from_raw_parts`,
1039 // strided-view/src/raw.rs:449) → `validate_bounds`
1040 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset, and
1041 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1042 let first = unsafe {
1043 RawStridedRef::new_unchecked(
1044 first_data,
1045 erased_refs[0].dims(),
1046 erased_refs[0].strides(),
1047 erased_refs[0].offset(),
1048 )
1049 };
1050 let mut input_refs = [first; crate::inline::OPERAND_CAP];
1051 for (slot, erased) in input_refs.iter_mut().zip(&erased_refs) {
1052 let input_data = erased.data_as::<T>()?;
1053 // SAFETY: this input reached `RawStridedRef` through
1054 // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1055 // re-ran the erased reference's raw constructor (`from_raw_parts`,
1056 // strided-view/src/raw.rs:449) → `validate_bounds`
1057 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset, and
1058 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1059 *slot = unsafe {
1060 RawStridedRef::new_unchecked(
1061 input_data,
1062 erased.dims(),
1063 erased.strides(),
1064 erased.offset(),
1065 )
1066 };
1067 }
1068 return plan.execute_uninit(&mut dest_ref, &input_refs[..inputs.len()], exec);
1069 }
1070 for (position, input) in inputs.iter().enumerate() {
1071 // SAFETY: input/output overlap was rejected before forming references.
1072 let input = unsafe { input.try_as_ref_after_no_overlap() }?;
1073 let input_data = input.data_as::<T>()?;
1074 // SAFETY: this input reached `RawStridedRef` through
1075 // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1076 // re-ran the erased reference's raw constructor (`from_raw_parts`,
1077 // strided-view/src/raw.rs:449) → `validate_bounds`
1078 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset, and
1079 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1080 let input_ref = unsafe {
1081 RawStridedRef::new_unchecked(input_data, input.dims(), input.strides(), input.offset())
1082 };
1083 plan.execute_segment_uninit(position, &mut dest_ref, &input_ref, exec.reborrow())?;
1084 }
1085 Ok(())
1086}
1087
1088/// Runtime unary operation applied to the source of an [`ErasedUpdatePlan`].
1089///
1090/// The real dtypes have only [`Self::Identity`]; the complex dtypes also have
1091/// [`Self::Conj`], matching the `ElementOp` choices a beta accumulator uses.
1092#[non_exhaustive]
1093#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1094pub enum UpdateOp {
1095 /// `op(x) = x`.
1096 Identity,
1097 /// `op(x) = conj(x)`.
1098 Conj,
1099}
1100
1101/// Dtype-erased wrapper around [`UpdatePlan`].
1102///
1103/// The layout traversal is compiled once and stored without a scalar type;
1104/// each [`execute`](Self::execute) names the concrete scalar type, resolves the
1105/// runtime element op once per call, and then replays monomorphized loops.
1106#[derive(Clone, Debug)]
1107pub struct ErasedUpdatePlan {
1108 dtype: KernelDType,
1109 plan: UpdatePlan,
1110}
1111
1112impl ErasedUpdatePlan {
1113 /// Compile an update plan for one dtype and layout pair.
1114 ///
1115 /// # Errors
1116 ///
1117 /// Returns [`StridedError::StrideLengthMismatch`] when `dims`,
1118 /// `dst_strides`, and `src_strides` do not all have the same length,
1119 /// [`StridedError::OffsetOverflow`] when the element count does not fit
1120 /// `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
1121 /// destination layout cannot be proven injective (aliasing elements, or a
1122 /// span the check cannot represent).
1123 pub fn compile(
1124 dtype: KernelDType,
1125 dims: &[usize],
1126 dst_strides: &[isize],
1127 src_strides: &[isize],
1128 ) -> Result<Self> {
1129 check_static_indexing_dtype(dtype)?;
1130 Ok(Self {
1131 dtype,
1132 plan: UpdatePlan::compile(dims, dst_strides, src_strides)?,
1133 })
1134 }
1135
1136 #[inline]
1137 pub fn dtype(&self) -> KernelDType {
1138 self.dtype
1139 }
1140
1141 /// The compiled typed traversal.
1142 #[inline]
1143 pub fn plan(&self) -> &UpdatePlan {
1144 &self.plan
1145 }
1146
1147 /// `dest = alpha * op(src) + beta * dest` into an erased destination.
1148 ///
1149 /// `alpha`, `beta`, and `op` are resolved once per call; the layout check
1150 /// and replay are the same allocation-free [`UpdatePlan`] path.
1151 ///
1152 /// # Errors
1153 ///
1154 /// Returns [`StridedError::DTypeMismatch`] when `dest`, `src`, or the
1155 /// scalar type `T` carries a different dtype than the plan, and
1156 /// [`StridedError::PlanLayoutMismatch`] when a view does not carry the
1157 /// compiled extents and strides. Both are returned before any destination
1158 /// write.
1159 ///
1160 /// # Examples
1161 ///
1162 /// ```
1163 /// use strided_basic::{
1164 /// ErasedRawStridedMut, ErasedRawStridedRef, ErasedUpdatePlan, Exec, KernelDType,
1165 /// UpdateOp,
1166 /// };
1167 ///
1168 /// let plan = ErasedUpdatePlan::compile(KernelDType::F64, &[2], &[1], &[1]).unwrap();
1169 /// let src_data = [1.0_f64, 2.0];
1170 /// let mut dst_data = [10.0_f64, 20.0];
1171 /// let src = ErasedRawStridedRef::from_slice(&src_data, &[2], &[1], 0).unwrap();
1172 /// let mut dst = ErasedRawStridedMut::from_slice_mut(&mut dst_data, &[2], &[1], 0).unwrap();
1173 /// // dst = 2 * src + 3 * dst
1174 /// plan.execute(&mut dst, &src, 2.0, 3.0, UpdateOp::Identity, Exec::serial())
1175 /// .unwrap();
1176 /// drop(dst);
1177 /// assert_eq!(dst_data, [32.0, 64.0]);
1178 /// ```
1179 pub fn execute<T>(
1180 &self,
1181 dest: &mut ErasedRawStridedMut<'_>,
1182 src: &ErasedRawStridedRef<'_>,
1183 alpha: T,
1184 beta: T,
1185 op: UpdateOp,
1186 exec: Exec<'_>,
1187 ) -> Result<()>
1188 where
1189 T: Copy
1190 + Send
1191 + Sync
1192 + KernelStorageElement
1193 + core::ops::Add<Output = T>
1194 + core::ops::Mul<Output = T>
1195 + Zero
1196 + One
1197 + PartialEq
1198 + ElementOpApply,
1199 {
1200 check_dtype(self.dtype, dest.dtype())?;
1201 check_dtype(self.dtype, src.dtype())?;
1202 let source_data = src.data_as::<T>()?;
1203 let dest_dims = dest.dims();
1204 let dest_strides = dest.strides();
1205 let dest_offset = dest.offset();
1206 let dest_data = dest.data_as_mut::<T>()?;
1207 // SAFETY: the source (`src`/`input`) is an erased descriptor built only by checked
1208 // constructors (`ErasedRawStridedRef::from_slice`/`from_raw_parts`,
1209 // strided-view/src/raw.rs:396/:449), which ran `validate_bounds`
1210 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
1211 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count, so
1212 // every reachable offset is inside the buffer it hands to `new_unchecked`.
1213 let source = unsafe {
1214 RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
1215 };
1216 // SAFETY: `dest` is an erased descriptor built only by checked
1217 // constructors (`ErasedRawStridedMut::from_slice_mut`/`from_raw_parts`,
1218 // strided-view/src/raw.rs:555/:610), which ran `validate_bounds`
1219 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset;
1220 // `data_as_mut::<T>` (raw.rs:663) re-checks the dtype at that element count,
1221 // and the `&mut` borrow keeps the storage unaliased for this call.
1222 let mut dest_ref = unsafe {
1223 RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset)
1224 };
1225 match op {
1226 UpdateOp::Identity => {
1227 self.plan
1228 .execute(&mut dest_ref, &source, alpha, beta, |x| x, exec)
1229 }
1230 UpdateOp::Conj => {
1231 self.plan
1232 .execute(&mut dest_ref, &source, alpha, beta, |x| x.conj(), exec)
1233 }
1234 }
1235 }
1236
1237 /// `dest = alpha * op(src)` into an uninitialized erased destination.
1238 ///
1239 /// This is [`execute`](Self::execute) with `beta = 0`: the destination is
1240 /// never read, so a NaN-filled or uninitialized output cannot contaminate
1241 /// the result. On success every reachable destination element is written;
1242 /// validation errors are returned before any write. A panic during
1243 /// execution may leave a partially initialized `MaybeUninit` destination,
1244 /// which is still safely droppable; no readable value is promised for
1245 /// unwritten reachable slots.
1246 ///
1247 /// # Examples
1248 ///
1249 /// ```
1250 /// use core::mem::MaybeUninit;
1251 /// use strided_basic::{
1252 /// ErasedRawStridedPtr, ErasedRawStridedRef, ErasedRawStridedUninitMut, ErasedUpdatePlan,
1253 /// Exec, KernelDType, UpdateOp,
1254 /// };
1255 ///
1256 /// let plan = ErasedUpdatePlan::compile(KernelDType::F64, &[2], &[1], &[1]).unwrap();
1257 /// let src_data = [1.0_f64, 2.0];
1258 /// let mut dst_data = [MaybeUninit::<f64>::uninit(); 2];
1259 /// let src = ErasedRawStridedRef::from_slice(&src_data, &[2], &[1], 0).unwrap();
1260 /// let src_ptr = ErasedRawStridedPtr::from_ref(&src);
1261 /// let mut dst =
1262 /// ErasedRawStridedUninitMut::from_uninit_slice(&mut dst_data, &[2], &[1], 0).unwrap();
1263 /// // dst = 2 * src
1264 /// plan.execute_uninit(&mut dst, &src_ptr, 2.0, UpdateOp::Identity, Exec::serial())
1265 /// .unwrap();
1266 /// let values: Vec<f64> = dst_data.iter().map(|v| unsafe { v.assume_init() }).collect();
1267 /// assert_eq!(values, [2.0, 4.0]);
1268 /// ```
1269 ///
1270 /// # Errors
1271 ///
1272 /// Returns `DTypeMismatch` or `PlanLayoutMismatch` when a descriptor does
1273 /// not match the plan, and `OverlappingInputOutput` when the source
1274 /// overlaps the destination allocation, all before any destination write.
1275 pub fn execute_uninit<T>(
1276 &self,
1277 dest: &mut ErasedRawStridedUninitMut<'_>,
1278 src: &ErasedRawStridedPtr<'_>,
1279 alpha: T,
1280 op: UpdateOp,
1281 exec: Exec<'_>,
1282 ) -> Result<()>
1283 where
1284 T: Copy
1285 + Send
1286 + Sync
1287 + KernelStorageElement
1288 + core::ops::Mul<Output = T>
1289 + One
1290 + PartialEq
1291 + ElementOpApply,
1292 {
1293 check_dtype(self.dtype, dest.dtype())?;
1294 check_dtype(self.dtype, src.dtype())?;
1295 validate_uninit_no_overlap(dest, src, 0)?;
1296 // SAFETY: the owning erased entry rejected all input/output overlap before conversion.
1297 let src = unsafe { src.try_as_ref_after_no_overlap() }?;
1298 let source_data = src.data_as::<T>()?;
1299 let dest_dims = dest.dims();
1300 let dest_strides = dest.strides();
1301 let dest_offset = dest.offset();
1302 let dest_data = dest.data_as_uninit_mut::<T>()?;
1303 // SAFETY: this input reached `RawStridedRef` through
1304 // `ErasedRawStridedPtr::try_as_ref_after_no_overlap` (raw.rs:288), which
1305 // re-ran the erased reference's raw constructor (`from_raw_parts`,
1306 // strided-view/src/raw.rs:449) → `validate_bounds`
1307 // (strided-view/src/view.rs:187) on exactly these dims/strides/offset, and
1308 // `data_as::<T>` (raw.rs:475) re-checks the dtype at that element count.
1309 let source = unsafe {
1310 RawStridedRef::new_unchecked(source_data, src.dims(), src.strides(), src.offset())
1311 };
1312 // SAFETY: `dest` is an erased descriptor built only by checked
1313 // constructors (`ErasedRawStridedUninitMut::from_uninit_slice`/
1314 // `from_raw_parts`, strided-view/src/raw.rs:745/:801), which ran
1315 // `validate_bounds` (strided-view/src/view.rs:187) on exactly these
1316 // dims/strides/offset; `data_as_uninit_mut::<T>` (raw.rs:828) re-checks the
1317 // dtype at that element count, writes go through `MaybeUninit`, and the
1318 // `&mut` borrow keeps the storage unaliased.
1319 let mut dest_ref = unsafe {
1320 RawStridedMut::new_unchecked(dest_data, dest_dims, dest_strides, dest_offset)
1321 };
1322 match op {
1323 UpdateOp::Identity => {
1324 self.plan
1325 .execute_uninit(&mut dest_ref, &source, alpha, |x| x, exec)
1326 }
1327 UpdateOp::Conj => {
1328 self.plan
1329 .execute_uninit(&mut dest_ref, &source, alpha, |x| x.conj(), exec)
1330 }
1331 }
1332 }
1333}
1334
1335fn execute_reduce_full<T, W, K>(
1336 dest: &mut W,
1337 src: &ErasedRawStridedRef<'_>,
1338 traversal: &FullTraversal,
1339 exec: Exec<'_>,
1340) -> Result<bool>
1341where
1342 T: ErasedReduceScalar,
1343 W: ReduceWriter<T>,
1344 K: ReduceKernel<T>,
1345{
1346 let source = src.data_as::<T>()?;
1347 let total = traversal.total();
1348 if total == 0 {
1349 // SAFETY: validated rank-zero destination layout proves the offset.
1350 unsafe { dest.write_at(dest.offset(), K::finish(K::identity())) };
1351 return Ok(false);
1352 }
1353 let acc = reduce_full_split::<T, K>(source, src.offset(), traversal, exec)?;
1354
1355 if K::needs_ordered_fallback(&acc) {
1356 // The caller re-runs this layout with `K::Fallback`; the destination is
1357 // left untouched so nothing observable is written twice.
1358 return Ok(true);
1359 }
1360 // SAFETY: validated rank-zero destination layout proves the offset.
1361 unsafe { dest.write_at(dest.offset(), K::finish(acc)) };
1362 Ok(false)
1363}
1364
1365/// Full reduction of `source` over the traversal, split across the budget of
1366/// `exec` above the repository threshold.
1367///
1368/// Splitting reassociates one output element's factors across ranges, so only
1369/// a kernel that may be reassociated takes it (tenferro-rs#2150). A stable
1370/// accumulator that detects an unrepresentable factor sets the fallback flag,
1371/// and the caller then recomputes the whole output in source order.
1372fn reduce_full_split<T, K>(
1373 source: &[T],
1374 source_base: isize,
1375 traversal: &FullTraversal,
1376 exec: Exec<'_>,
1377) -> Result<K::Acc>
1378where
1379 T: ErasedReduceScalar,
1380 K: ReduceKernel<T>,
1381{
1382 let total = traversal.total();
1383 // INVARIANT: (1) FullTraversal::compile checked every step/reset of the
1384 // source layout; (2) the raw source descriptor validated every reachable
1385 // offset; (3) execute checked exact plan-layout equality.
1386 if !K::reassociable() {
1387 // SAFETY: the three-link invariant proves every traversal offset is
1388 // readable.
1389 return unsafe {
1390 reduce_full_range::<T, K>(source.as_ptr(), source_base, traversal, 0..total)
1391 };
1392 }
1393 let source_ptr = crate::threading::SendPtr(source.as_ptr() as *mut T);
1394 crate::threading::parallel_map_reduce(
1395 0..total,
1396 crate::cost::for_len_tree(exec, KernelClass::Reduce, total),
1397 &|range| {
1398 // SAFETY: same three-link invariant as above; each range is
1399 // non-empty.
1400 unsafe {
1401 reduce_full_range::<T, K>(source_ptr.as_const(), source_base, traversal, range)
1402 }
1403 },
1404 &|left, right| Ok(K::combine(left?, right?)),
1405 )
1406}
1407
1408fn dispatch_reduce<T, W>(
1409 op: ReduceOp,
1410 layout: &ReduceLayout,
1411 dest: &mut W,
1412 src: &ErasedRawStridedRef<'_>,
1413 exec: Exec<'_>,
1414) -> Result<()>
1415where
1416 T: ErasedReduceScalar,
1417 W: ReduceWriter<T>,
1418{
1419 // The op is matched once per execution; every loop below is generic over
1420 // the selected kernel type.
1421 match op {
1422 ReduceOp::Sum => dispatch_reduce_kernel::<T, W, SumKernel>(layout, dest, src, exec),
1423 ReduceOp::Product => {
1424 dispatch_reduce_kernel::<T, W, ReassociatedProductKernel>(layout, dest, src, exec)
1425 }
1426 ReduceOp::StableProduct => {
1427 dispatch_reduce_kernel::<T, W, StableProductKernel>(layout, dest, src, exec)
1428 }
1429 ReduceOp::SumSquares => {
1430 dispatch_reduce_kernel::<T, W, SumSquaresKernel>(layout, dest, src, exec)
1431 }
1432 ReduceOp::Max => dispatch_reduce_kernel::<T, W, MaxKernel>(layout, dest, src, exec),
1433 ReduceOp::Min => dispatch_reduce_kernel::<T, W, MinKernel>(layout, dest, src, exec),
1434 }
1435}
1436
1437fn dispatch_reduce_kernel<T, W, K>(
1438 layout: &ReduceLayout,
1439 dest: &mut W,
1440 src: &ErasedRawStridedRef<'_>,
1441 mut exec: Exec<'_>,
1442) -> Result<()>
1443where
1444 T: ErasedReduceScalar,
1445 W: ReduceWriter<T>,
1446 K: ReduceKernel<T>,
1447{
1448 let fallback = match layout {
1449 ReduceLayout::Full { traversal, .. } => {
1450 execute_reduce_full::<T, W, K>(dest, src, traversal, exec.reborrow())?
1451 }
1452 ReduceLayout::Axes {
1453 outer_axes,
1454 inner_axes,
1455 dest_total,
1456 reduce_total,
1457 full,
1458 ..
1459 } => {
1460 let axes = AxesLayout {
1461 outer_axes,
1462 inner_axes,
1463 dest_total: *dest_total,
1464 reduce_total: *reduce_total,
1465 };
1466 match full {
1467 Some(traversal) => {
1468 execute_reduce_full::<T, W, K>(dest, src, traversal, exec.reborrow())?
1469 }
1470 None => {
1471 // An axis reduction falls back per output inside
1472 // `reduce_axes_range`; it never asks for a layout-wide
1473 // recompute.
1474 execute_reduce_axes::<T, W, K>(dest, src, axes, exec.reborrow())?;
1475 false
1476 }
1477 }
1478 }
1479 };
1480 if fallback {
1481 // Only a full reduction (one output) requests the layout-wide
1482 // recompute; `K::Fallback` must not itself request a fallback, so this
1483 // recurses at most once. Scalar kernels use `Fallback = Self` and never
1484 // set the flag, so the branch is unreachable for them.
1485 return dispatch_reduce_kernel::<T, W, K::Fallback>(layout, dest, src, exec);
1486 }
1487 Ok(())
1488}
1489
1490fn execute_reduce_axes<T, W, K>(
1491 dest: &mut W,
1492 src: &ErasedRawStridedRef<'_>,
1493 layout: AxesLayout<'_>,
1494 exec: Exec<'_>,
1495) -> Result<()>
1496where
1497 T: ErasedReduceScalar,
1498 W: ReduceWriter<T>,
1499 K: ReduceKernel<T>,
1500{
1501 if layout.dest_total == 0 {
1502 return Ok(());
1503 }
1504
1505 if layout.reduce_total == 0 {
1506 execute_reduce_axes_identity::<T, W, K>(dest, layout, exec)
1507 } else {
1508 execute_reduce_axes_split::<T, W, K>(dest, src, layout, exec)
1509 }
1510}
1511
1512fn execute_reduce_axes_split<T, W, K>(
1513 dest: &mut W,
1514 src: &ErasedRawStridedRef<'_>,
1515 layout: AxesLayout<'_>,
1516 exec: Exec<'_>,
1517) -> Result<()>
1518where
1519 T: ErasedReduceScalar,
1520 W: ReduceWriter<T>,
1521 K: ReduceKernel<T>,
1522{
1523 let source_data = src.data_as::<T>()?;
1524 let source_base = src.offset();
1525 let dest_base = dest.offset();
1526 // SAFETY: the validated reduction writer owns the destination allocation.
1527 let dest_ptr = unsafe { dest.ptr() };
1528 // The threshold counts source elements read (outputs times reduced
1529 // elements), as documented in docs/design/erased-execution-policy.md,
1530 // so a few thousand outputs with long reductions still split. Ranges
1531 // partition the independent outputs; with the output block kernel this
1532 // splits along the contiguous kept axis.
1533 let work = layout.dest_total.saturating_mul(layout.reduce_total);
1534 let exec = crate::cost::for_len_tree(exec, KernelClass::Reduce, work).limit(
1535 core::num::NonZeroUsize::new(layout.dest_total).unwrap_or(core::num::NonZeroUsize::MIN),
1536 );
1537 if !exec.is_serial() {
1538 let dest_ptr = crate::threading::SendPtr(dest_ptr);
1539 let source_ptr = crate::threading::SendPtr(source_data.as_ptr() as *mut T);
1540 return crate::threading::parallel_map_reduce(
1541 0..layout.dest_total,
1542 exec,
1543 &|range| {
1544 let parts = AxesRange {
1545 source: source_ptr.as_const(),
1546 source_base,
1547 dest: dest_ptr.as_ptr(),
1548 dest_base,
1549 outer_axes: layout.outer_axes,
1550 inner_axes: layout.inner_axes,
1551 reduce_total: layout.reduce_total,
1552 };
1553 // SAFETY: see `execute_reduce_axes_split` serial call.
1554 unsafe { reduce_axes_range::<T, K>(parts, range) }
1555 },
1556 &|left, right| left.and(right),
1557 );
1558 }
1559
1560 let parts = AxesRange {
1561 source: source_data.as_ptr(),
1562 source_base,
1563 dest: dest_ptr,
1564 dest_base,
1565 outer_axes: layout.outer_axes,
1566 inner_axes: layout.inner_axes,
1567 reduce_total: layout.reduce_total,
1568 };
1569 // INVARIANT: (1) compile_axes checked signed source/destination spans and
1570 // every cursor step/reset; (2) raw input and output descriptors validated
1571 // every reachable offset; (3) execute checked exact plan-layout equality
1572 // before dispatch. Output ranges are disjoint, and the initialized entry
1573 // holds distinct borrows while the uninit entry rejected overlap.
1574 // SAFETY: the three-link invariant above; `reduce_total` is nonzero.
1575 unsafe { reduce_axes_range::<T, K>(parts, 0..layout.dest_total) }
1576}
1577
1578fn execute_reduce_axes_identity_serial<T, W, K>(dest: &mut W, layout: AxesLayout<'_>) -> Result<()>
1579where
1580 T: ErasedReduceScalar,
1581 W: ReduceWriter<T>,
1582 K: ReduceKernel<T>,
1583{
1584 let mut outer = ReduceOuterCursor::decode(0, 0, dest.offset(), layout.outer_axes)?;
1585 for output in 0..layout.dest_total {
1586 // INVARIANT: (1) compile_axes checked the destination span and every
1587 // destination step/reset, including -(extent-1)*stride; (2) the raw
1588 // destination descriptor validated every reachable offset; (3) execute
1589 // checked exact plan-layout equality before dispatch.
1590 // SAFETY: the three-link layout invariant proves this destination
1591 // cursor offset is in bounds; the source pointer is intentionally never
1592 // formed for an empty reduction domain.
1593 unsafe { dest.write_at(outer.dest_offset, K::finish(K::identity())) };
1594 if output + 1 < layout.dest_total {
1595 outer.advance();
1596 }
1597 }
1598 Ok(())
1599}
1600fn execute_reduce_axes_identity<T, W, K>(
1601 dest: &mut W,
1602 layout: AxesLayout<'_>,
1603 exec: Exec<'_>,
1604) -> Result<()>
1605where
1606 T: ErasedReduceScalar,
1607 W: ReduceWriter<T>,
1608 K: ReduceKernel<T>,
1609{
1610 let exec = crate::cost::for_len_tree(exec, KernelClass::Reduce, layout.dest_total);
1611 if !exec.is_serial() {
1612 return execute_reduce_axes_identity_parallel::<T, W, K>(dest, layout, exec);
1613 }
1614 execute_reduce_axes_identity_serial::<T, W, K>(dest, layout)
1615}
1616
1617fn execute_reduce_axes_identity_parallel<T, W, K>(
1618 dest: &mut W,
1619 layout: AxesLayout<'_>,
1620 exec: Exec<'_>,
1621) -> Result<()>
1622where
1623 T: ErasedReduceScalar,
1624 W: ReduceWriter<T>,
1625 K: ReduceKernel<T>,
1626{
1627 // SAFETY: the validated reduction writer owns the destination allocation.
1628 let dest_ptr = crate::threading::SendPtr(unsafe { dest.ptr() });
1629 let dest_offset_base = dest.offset();
1630 crate::threading::parallel_map_reduce(
1631 0..layout.dest_total,
1632 exec,
1633 &|range| {
1634 let range_end = range.end;
1635 let mut outer =
1636 ReduceOuterCursor::decode(range.start, 0, dest_offset_base, layout.outer_axes)?;
1637 let dest_ptr = dest_ptr.as_ptr();
1638 for output in range {
1639 // INVARIANT: (1) compile_axes checked the destination span and
1640 // every destination step/reset, including
1641 // -(extent-1)*stride; (2) the raw destination descriptor
1642 // validated every reachable pointer offset; (3) execute checked
1643 // exact plan-layout equality before dispatch.
1644 // SAFETY: the three-link layout invariant proves this
1645 // destination offset is in bounds; no source pointer is formed.
1646 unsafe {
1647 dest_ptr
1648 .offset(outer.dest_offset)
1649 .write(K::finish(K::identity()))
1650 };
1651 if output + 1 < range_end {
1652 outer.advance();
1653 }
1654 }
1655 Ok(())
1656 },
1657 &|left, right| left.and(right),
1658 )
1659}
1660
1661trait ErasedReduceScalar:
1662 KernelStorageElement
1663 + Copy
1664 + One
1665 + Zero
1666 + Send
1667 + Sync
1668 + crate::simd::MaybeSimdOps
1669 + crate::simd::MaybeSimdProduct
1670 + crate::simd::MaybeSimdSumSquares
1671 + crate::simd::MaybeSimdBlockFold
1672 + StableProductScalar
1673{
1674 fn reduce_sum(lhs: Self, rhs: Self) -> Self;
1675 fn reduce_product(lhs: Self, rhs: Self) -> Self;
1676 /// Identity of [`ReduceOp::Max`]; unreachable for dtypes the plan rejects.
1677 fn max_identity() -> Self;
1678 /// Identity of [`ReduceOp::Min`]; unreachable for dtypes the plan rejects.
1679 fn min_identity() -> Self;
1680 fn reduce_max(lhs: Self, rhs: Self) -> Self;
1681 fn reduce_min(lhs: Self, rhs: Self) -> Self;
1682}
1683
1684macro_rules! impl_float_erased_reduce_scalar {
1685 ($($ty:ty),* $(,)?) => {
1686 $(
1687 impl ErasedReduceScalar for $ty {
1688 #[inline(always)]
1689 fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1690 lhs + rhs
1691 }
1692
1693 #[inline(always)]
1694 fn reduce_product(lhs: Self, rhs: Self) -> Self {
1695 lhs * rhs
1696 }
1697
1698 #[inline(always)]
1699 fn max_identity() -> Self {
1700 <$ty>::NEG_INFINITY
1701 }
1702
1703 #[inline(always)]
1704 fn min_identity() -> Self {
1705 <$ty>::INFINITY
1706 }
1707
1708 #[inline(always)]
1709 fn reduce_max(lhs: Self, rhs: Self) -> Self {
1710 // Select form: both sides are evaluated and the NaN test
1711 // picks the result, so lane loops lower to compare and
1712 // blend instead of a data dependent branch.
1713 // A NaN `lhs` is kept by the second test and a NaN
1714 // `rhs` fails the comparison, so NaN propagates from
1715 // either side. Equal values (including +0.0 and -0.0)
1716 // return `rhs`.
1717 if (lhs > rhs) | lhs.is_nan() {
1718 lhs
1719 } else {
1720 rhs
1721 }
1722 }
1723
1724 #[inline(always)]
1725 fn reduce_min(lhs: Self, rhs: Self) -> Self {
1726 // Select form: both sides are evaluated and the NaN test
1727 // picks the result, so lane loops lower to compare and
1728 // blend instead of a data dependent branch.
1729 // A NaN `lhs` is kept by the second test and a NaN
1730 // `rhs` fails the comparison, so NaN propagates from
1731 // either side. Equal values (including +0.0 and -0.0)
1732 // return `rhs`.
1733 if (lhs < rhs) | lhs.is_nan() {
1734 lhs
1735 } else {
1736 rhs
1737 }
1738 }
1739 }
1740 )*
1741 };
1742}
1743
1744macro_rules! impl_complex_erased_reduce_scalar {
1745 ($($ty:ty),* $(,)?) => {
1746 $(
1747 impl ErasedReduceScalar for $ty {
1748 #[inline(always)]
1749 fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1750 lhs + rhs
1751 }
1752
1753 #[inline(always)]
1754 fn reduce_product(lhs: Self, rhs: Self) -> Self {
1755 lhs * rhs
1756 }
1757
1758 fn max_identity() -> Self {
1759 // INVARIANT: check_reduce_op_dtype rejects complex Max at compile time.
1760 unreachable!("complex max reduction is rejected at plan compile")
1761 }
1762
1763 fn min_identity() -> Self {
1764 // INVARIANT: check_reduce_op_dtype rejects complex Min at compile time.
1765 unreachable!("complex min reduction is rejected at plan compile")
1766 }
1767
1768 fn reduce_max(_lhs: Self, _rhs: Self) -> Self {
1769 // INVARIANT: check_reduce_op_dtype rejects complex Max at compile time.
1770 unreachable!("complex max reduction is rejected at plan compile")
1771 }
1772
1773 fn reduce_min(_lhs: Self, _rhs: Self) -> Self {
1774 // INVARIANT: check_reduce_op_dtype rejects complex Min at compile time.
1775 unreachable!("complex min reduction is rejected at plan compile")
1776 }
1777 }
1778 )*
1779 };
1780}
1781
1782macro_rules! impl_wrapping_erased_reduce_scalar {
1783 ($($ty:ty),* $(,)?) => {
1784 $(
1785 impl ErasedReduceScalar for $ty {
1786 #[inline(always)]
1787 fn reduce_sum(lhs: Self, rhs: Self) -> Self {
1788 lhs.wrapping_add(rhs)
1789 }
1790
1791 #[inline(always)]
1792 fn reduce_product(lhs: Self, rhs: Self) -> Self {
1793 lhs.wrapping_mul(rhs)
1794 }
1795
1796 #[inline(always)]
1797 fn max_identity() -> Self {
1798 <$ty>::MIN
1799 }
1800
1801 #[inline(always)]
1802 fn min_identity() -> Self {
1803 <$ty>::MAX
1804 }
1805
1806 #[inline(always)]
1807 fn reduce_max(lhs: Self, rhs: Self) -> Self {
1808 lhs.max(rhs)
1809 }
1810
1811 #[inline(always)]
1812 fn reduce_min(lhs: Self, rhs: Self) -> Self {
1813 lhs.min(rhs)
1814 }
1815 }
1816 )*
1817 };
1818}
1819
1820impl_float_erased_reduce_scalar!(f32, f64);
1821
1822impl_complex_erased_reduce_scalar!(Complex32, Complex64);
1823
1824impl_wrapping_erased_reduce_scalar!(i32, i64);
1825
1826fn validate_unique_axes(axes: &[usize], rank: usize) -> Result<()> {
1827 // Inline for the rank bound (P4); above it the spill may allocate.
1828 let mut inline = [false; strided_view::INLINE_RANK];
1829 let mut spill: Vec<bool> = Vec::new();
1830 let seen: &mut [bool] = if rank <= strided_view::INLINE_RANK {
1831 &mut inline[..rank]
1832 } else {
1833 spill.resize(rank, false);
1834 &mut spill
1835 };
1836 for &axis in axes {
1837 if axis >= rank {
1838 return Err(StridedError::InvalidAxis { axis, rank });
1839 }
1840 if seen[axis] {
1841 return Err(StridedError::InvalidAxis { axis, rank });
1842 }
1843 seen[axis] = true;
1844 }
1845 Ok(())
1846}
1847
1848struct ReduceOuterCursor<'a> {
1849 axes: &'a [ReduceOuterAxis],
1850 coords: CoordScratch,
1851 source_offset: isize,
1852 dest_offset: isize,
1853}
1854impl<'a> ReduceOuterCursor<'a> {
1855 fn decode(
1856 mut linear: usize,
1857 source_base: isize,
1858 dest_base: isize,
1859 axes: &'a [ReduceOuterAxis],
1860 ) -> Result<Self> {
1861 let mut coords = CoordScratch::new(axes.len());
1862 let mut source_offset = source_base;
1863 let mut dest_offset = dest_base;
1864 for (coord, axis) in coords.as_mut_slice().iter_mut().zip(axes) {
1865 // INVARIANT: a non-empty destination domain implies every outer
1866 // extent is nonzero before decode; compile-time span checks make
1867 // these one-time checked additions represent valid layout offsets.
1868 debug_assert!(axis.extent != 0);
1869 *coord = linear % axis.extent;
1870 linear /= axis.extent;
1871 source_offset = checked_offset_add(source_offset, axis.source_step, *coord)?;
1872 dest_offset = checked_offset_add(dest_offset, axis.dest_step, *coord)?;
1873 }
1874 Ok(Self {
1875 axes,
1876 coords,
1877 source_offset,
1878 dest_offset,
1879 })
1880 }
1881
1882 /// Coordinate along the first (fastest) compressed outer axis.
1883 #[inline]
1884 fn leading_coord(&self) -> usize {
1885 self.coords.first()
1886 }
1887
1888 #[inline]
1889 fn advance(&mut self) {
1890 // INVARIANT: compile_axes checked every signed step and reset delta;
1891 // descriptor validation plus exact layout equality proves each cursor
1892 // state is a reachable source/destination offset.
1893 for (coord, axis) in self.coords.as_mut_slice().iter_mut().zip(self.axes) {
1894 let next = *coord + 1;
1895 if next < axis.extent {
1896 *coord = next;
1897 self.source_offset += axis.source_step;
1898 self.dest_offset += axis.dest_step;
1899 return;
1900 }
1901 *coord = 0;
1902 self.source_offset += axis.source_reset;
1903 self.dest_offset += axis.dest_reset;
1904 }
1905 }
1906}
1907struct ReduceInnerCursor<'a> {
1908 axes: &'a [ReduceInnerAxis],
1909 coords: CoordScratch,
1910 source_offset: isize,
1911}
1912impl<'a> ReduceInnerCursor<'a> {
1913 fn new(source_base: isize, axes: &'a [ReduceInnerAxis]) -> Self {
1914 Self {
1915 axes,
1916 coords: CoordScratch::new(axes.len()),
1917 source_offset: source_base,
1918 }
1919 }
1920
1921 #[inline]
1922 fn reset(&mut self, source_base: isize) {
1923 self.coords.as_mut_slice().fill(0);
1924 self.source_offset = source_base;
1925 }
1926
1927 #[inline]
1928 fn advance(&mut self) {
1929 // INVARIANT: compile_axes checked every signed source step and reset
1930 // delta, and the validated descriptor/layout chain proves each value
1931 // offset is reachable from the current outer source base.
1932 for (coord, axis) in self.coords.as_mut_slice().iter_mut().zip(self.axes) {
1933 let next = *coord + 1;
1934 if next < axis.extent {
1935 *coord = next;
1936 self.source_offset += axis.source_step;
1937 return;
1938 }
1939 *coord = 0;
1940 self.source_offset += axis.source_reset;
1941 }
1942 }
1943}
1944fn check_reduce_layout_offset_arithmetic(dims: &[usize], strides: &[isize]) -> Result<()> {
1945 if dims.len() != strides.len() {
1946 return Err(StridedError::StrideLengthMismatch);
1947 }
1948 let mut min_offset = 0isize;
1949 let mut max_offset = 0isize;
1950 for (&dim, &stride) in dims.iter().zip(strides) {
1951 let last =
1952 isize::try_from(dim.saturating_sub(1)).map_err(|_| StridedError::OffsetOverflow)?;
1953 let extent = stride
1954 .checked_mul(last)
1955 .ok_or(StridedError::OffsetOverflow)?;
1956 if extent < 0 {
1957 min_offset = min_offset
1958 .checked_add(extent)
1959 .ok_or(StridedError::OffsetOverflow)?;
1960 } else {
1961 max_offset = max_offset
1962 .checked_add(extent)
1963 .ok_or(StridedError::OffsetOverflow)?;
1964 }
1965 }
1966 let _ = (min_offset, max_offset);
1967 Ok(())
1968}
1969fn compress_reduce_outer_axes(
1970 axes: crate::inline::InlineVec<ReduceOuterAxis>,
1971) -> Result<crate::inline::InlineVec<ReduceOuterAxis>> {
1972 let mut compressed: crate::inline::InlineVec<ReduceOuterAxis> =
1973 crate::inline::InlineVec::with_capacity(axes.len());
1974 for axis in axes {
1975 if let Some(previous) = compressed.last_mut() {
1976 let previous_extent =
1977 isize::try_from(previous.extent).map_err(|_| StridedError::OffsetOverflow)?;
1978 let expected_source = previous
1979 .source_step
1980 .checked_mul(previous_extent)
1981 .ok_or(StridedError::OffsetOverflow)?;
1982 let expected_dest = previous
1983 .dest_step
1984 .checked_mul(previous_extent)
1985 .ok_or(StridedError::OffsetOverflow)?;
1986 if axis.source_step == expected_source && axis.dest_step == expected_dest {
1987 let fused_extent = previous
1988 .extent
1989 .checked_mul(axis.extent)
1990 .ok_or(StridedError::OffsetOverflow)?;
1991 previous.extent = fused_extent;
1992 previous.source_reset = checked_reduce_reset(fused_extent, previous.source_step)?;
1993 previous.dest_reset = checked_reduce_reset(fused_extent, previous.dest_step)?;
1994 continue;
1995 }
1996 }
1997 compressed.push(axis);
1998 }
1999 Ok(compressed)
2000}
2001fn compress_reduce_inner_axes(
2002 axes: crate::inline::InlineVec<ReduceInnerAxis>,
2003) -> Result<crate::inline::InlineVec<ReduceInnerAxis>> {
2004 let mut compressed: crate::inline::InlineVec<ReduceInnerAxis> =
2005 crate::inline::InlineVec::with_capacity(axes.len());
2006 for axis in axes {
2007 if let Some(previous) = compressed.last_mut() {
2008 let previous_extent =
2009 isize::try_from(previous.extent).map_err(|_| StridedError::OffsetOverflow)?;
2010 let expected_source = previous
2011 .source_step
2012 .checked_mul(previous_extent)
2013 .ok_or(StridedError::OffsetOverflow)?;
2014 if axis.source_step == expected_source {
2015 let fused_extent = previous
2016 .extent
2017 .checked_mul(axis.extent)
2018 .ok_or(StridedError::OffsetOverflow)?;
2019 previous.extent = fused_extent;
2020 previous.source_reset = checked_reduce_reset(fused_extent, previous.source_step)?;
2021 continue;
2022 }
2023 }
2024 compressed.push(axis);
2025 }
2026 Ok(compressed)
2027}
2028fn checked_reduce_reset(extent: usize, stride: isize) -> Result<isize> {
2029 if extent == 0 {
2030 return Ok(0);
2031 }
2032 let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2033 stride
2034 .checked_mul(last)
2035 .and_then(isize::checked_neg)
2036 .ok_or(StridedError::OffsetOverflow)
2037}
2038fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2039 let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2040 let scaled = stride
2041 .checked_mul(coord)
2042 .ok_or(StridedError::OffsetOverflow)?;
2043 base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2044}
2045
2046struct CoordScratch {
2047 inline: [usize; RAW_FUSED_RANK_LIMIT],
2048 heap: Option<Vec<usize>>,
2049 len: usize,
2050}
2051
2052impl CoordScratch {
2053 fn new(len: usize) -> Self {
2054 if len <= RAW_FUSED_RANK_LIMIT {
2055 Self {
2056 inline: [0; RAW_FUSED_RANK_LIMIT],
2057 heap: None,
2058 len,
2059 }
2060 } else {
2061 Self {
2062 inline: [0; RAW_FUSED_RANK_LIMIT],
2063 heap: Some(vec![0; len]),
2064 len,
2065 }
2066 }
2067 }
2068
2069 #[inline]
2070 fn first(&self) -> usize {
2071 match &self.heap {
2072 Some(heap) => heap.first().copied().unwrap_or(0),
2073 None => self.inline[0],
2074 }
2075 }
2076
2077 fn as_mut_slice(&mut self) -> &mut [usize] {
2078 match &mut self.heap {
2079 Some(heap) => heap,
2080 None => &mut self.inline[..self.len],
2081 }
2082 }
2083}