1use crate::fuse::{compress_dims, fuse_dims};
7use crate::inline::{InlineVec, OperandVec};
8use crate::{block, order, Exec, Result, StridedError};
9
10pub const SMALL_TENSOR_THRESHOLD: usize = 1024;
14
15#[derive(Debug)]
17pub struct KernelPlan {
18 #[cfg_attr(not(test), allow(dead_code))]
20 pub(crate) order: InlineVec<usize>, pub block: InlineVec<usize>,
22}
23
24#[cfg(test)]
32pub(crate) fn build_plan(
33 dims: &[usize],
34 strides_list: &[&[isize]],
35 dest_index: Option<usize>,
36 elem_size: usize,
37) -> KernelPlan {
38 let order = order::compute_order(dims, strides_list, dest_index);
39 let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
40 let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
41 .iter()
42 .map(|strides| order.iter().map(|&d| strides[d]).collect())
43 .collect();
44 let ordered_strides_refs: OperandVec<&[isize]> =
45 ordered_strides.iter().map(|s| s.as_slice()).collect();
46 let block = block::compute_block_sizes(&ordered_dims, &ordered_strides_refs, elem_size);
47 KernelPlan { order, block }
48}
49
50pub(crate) fn build_plan_fused(
62 dims: &[usize],
63 strides_list: &[&[isize]],
64 dest_index: Option<usize>,
65 elem_size: usize,
66) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
67 let order = order::compute_order(dims, strides_list, dest_index);
69
70 let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
72 let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
73 .iter()
74 .map(|strides| order.iter().map(|&d| strides[d]).collect())
75 .collect();
76 let ordered_strides_refs: OperandVec<&[isize]> =
77 ordered_strides.iter().map(|s| s.as_slice()).collect();
78
79 let fused_dims = fuse_dims(&ordered_dims, &ordered_strides_refs);
81
82 let (compressed_dims, compressed_strides) = compress_dims(&fused_dims, &ordered_strides_refs);
84 let compressed_strides_refs: OperandVec<&[isize]> =
85 compressed_strides.iter().map(|s| s.as_slice()).collect();
86
87 let identity: InlineVec<usize> = (0..compressed_dims.len()).collect();
89 let block = block::compute_block_sizes(&compressed_dims, &compressed_strides_refs, elem_size);
90
91 (
92 compressed_dims,
93 compressed_strides,
94 KernelPlan {
95 order: identity,
96 block,
97 },
98 )
99}
100
101pub(crate) fn build_plan_fused_small(
110 dims: &[usize],
111 strides_list: &[&[isize]],
112) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
113 let fused = fuse_dims(dims, strides_list);
115 let (fused_dims, fused_strides) = compress_dims(&fused, strides_list);
116
117 let block = fused_dims.clone();
119 let identity: InlineVec<usize> = (0..fused_dims.len()).collect();
120
121 (
122 fused_dims,
123 fused_strides,
124 KernelPlan {
125 order: identity,
126 block,
127 },
128 )
129}
130
131#[cfg(test)]
141#[inline]
142pub(crate) fn for_each_inner_block<F>(
143 dims: &[usize],
144 plan: &KernelPlan,
145 strides_list: &[&[isize]],
146 mut f: F,
147) -> Result<()>
148where
149 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
150{
151 let rank = dims.len();
152 if rank == 0 {
153 let offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
154 return f(&offsets, 1, &[]);
155 }
156
157 let ordered_dims: InlineVec<usize> = plan.order.iter().map(|&d| dims[d]).collect();
159 let ordered_blocks: InlineVec<usize> = plan.block.clone();
160
161 let mut ordered_strides: OperandVec<InlineVec<isize>> = OperandVec::new();
163 for strides in strides_list {
164 ordered_strides.push(plan.order.iter().map(|&d| strides[d]).collect());
165 }
166 let ordered_strides_refs: OperandVec<&[isize]> =
167 ordered_strides.iter().map(|s| s.as_slice()).collect();
168
169 let mut offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
171
172 match rank {
174 1 => kernel_1d_inner(
175 &ordered_dims,
176 &ordered_blocks,
177 &ordered_strides_refs,
178 &mut offsets,
179 &mut f,
180 ),
181 2 => kernel_2d_inner(
182 &ordered_dims,
183 &ordered_blocks,
184 &ordered_strides_refs,
185 &mut offsets,
186 &mut f,
187 ),
188 3 => kernel_3d_inner(
189 &ordered_dims,
190 &ordered_blocks,
191 &ordered_strides_refs,
192 &mut offsets,
193 &mut f,
194 ),
195 4 => kernel_4d_inner(
196 &ordered_dims,
197 &ordered_blocks,
198 &ordered_strides_refs,
199 &mut offsets,
200 &mut f,
201 ),
202 5 => kernel_5d_inner(
203 &ordered_dims,
204 &ordered_blocks,
205 &ordered_strides_refs,
206 &mut offsets,
207 &mut f,
208 ),
209 6 => kernel_6d_inner(
210 &ordered_dims,
211 &ordered_blocks,
212 &ordered_strides_refs,
213 &mut offsets,
214 &mut f,
215 ),
216 7 => kernel_7d_inner(
217 &ordered_dims,
218 &ordered_blocks,
219 &ordered_strides_refs,
220 &mut offsets,
221 &mut f,
222 ),
223 8 => kernel_8d_inner(
224 &ordered_dims,
225 &ordered_blocks,
226 &ordered_strides_refs,
227 &mut offsets,
228 &mut f,
229 ),
230 _ => kernel_nd_inner_iterative(
231 &ordered_dims,
232 &ordered_blocks,
233 &ordered_strides_refs,
234 &mut offsets,
235 &mut f,
236 ),
237 }
238}
239
240macro_rules! elem_loops {
259 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident; $lv:literal) => {
263 for _i in 0..$blens[$lv] {
264 $f($offsets, $blens[0], &$is)?;
265 if _i + 1 < $blens[$lv] {
266 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
267 *o += s[$lv];
268 }
269 }
270 }
271 let _back = $blens[$lv].saturating_sub(1) as isize;
272 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
273 *o -= _back * s[$lv];
274 }
275 };
276 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident;
279 $lv:literal, $next:literal $(, $rest:literal)*) => {
280 for _i in 0..$blens[$lv] {
281 elem_loops!($offsets, $strides, $f, $blens, $is; $next $(, $rest)*);
282 if _i + 1 < $blens[$lv] {
283 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
284 *o += s[$lv];
285 }
286 }
287 }
288 let _back = $blens[$lv].saturating_sub(1) as isize;
289 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
290 *o -= _back * s[$lv];
291 }
292 };
293}
294
295macro_rules! block_loop {
302 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
304 $blens:ident, $is:ident; elem=[$($el:literal),+]; $lv0:literal; top=$top:literal) => {{
305 let mut _j = 0usize;
306 let mut _advanced = 0usize;
307 while _j < $dims[$lv0] {
308 $blens[$lv0] = $blocks[$lv0].max(1).min($dims[$lv0]).min($dims[$lv0] - _j);
309 elem_loops!($offsets, $strides, $f, $blens, $is; $($el),+);
310 _j += $blens[$lv0];
311 if _j < $dims[$lv0] {
312 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
313 *o += ($blens[$lv0] as isize) * s[$lv0];
314 }
315 _advanced = _j;
316 }
317 }
318 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
319 *o -= (_advanced as isize) * s[$lv0];
320 }
321 }};
322 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
324 $blens:ident, $is:ident; elem=[$($el:literal),+];
325 $lv:literal, $next:literal $(, $rest:literal)*; top=$top:literal) => {{
326 let mut _j = 0usize;
327 let mut _advanced = 0usize;
328 while _j < $dims[$lv] {
329 $blens[$lv] = $blocks[$lv].max(1).min($dims[$lv]).min($dims[$lv] - _j);
330 block_loop!($dims, $blocks, $strides, $offsets, $f, $blens, $is;
331 elem=[$($el),+]; $next $(, $rest)*; top=$top);
332 _j += $blens[$lv];
333 if _j < $dims[$lv] {
334 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
335 *o += ($blens[$lv] as isize) * s[$lv];
336 }
337 _advanced = _j;
338 }
339 }
340 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
341 *o -= (_advanced as isize) * s[$lv];
342 }
343 }};
344}
345
346macro_rules! make_kernel {
353 ($name:ident, rank=1) => {
355 #[inline]
356 fn $name<F>(
357 dims: &[usize],
358 blocks: &[usize],
359 strides: &[&[isize]],
360 offsets: &mut [isize],
361 f: &mut F,
362 ) -> Result<()>
363 where
364 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
365 {
366 let d0 = dims[0];
367 let b0 = blocks[0].max(1).min(d0);
368 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
369
370 let mut j0 = 0usize;
371 let mut advanced = 0usize;
372 while j0 < d0 {
373 let blen0 = b0.min(d0 - j0);
374 f(offsets, blen0, &inner_strides)?;
375 j0 += blen0;
376 if j0 < d0 {
377 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
378 *o += (blen0 as isize) * s[0];
379 }
380 advanced = j0;
381 }
382 }
383 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
384 *o -= (advanced as isize) * s[0];
385 }
386 Ok(())
387 }
388 };
389 ($name:ident, rank=$rank:literal,
394 block=[$($blk:literal),+], elem=[$($el:literal),+], top=$top:literal) => {
395 #[inline]
396 fn $name<F>(
397 dims: &[usize],
398 blocks: &[usize],
399 strides: &[&[isize]],
400 offsets: &mut [isize],
401 f: &mut F,
402 ) -> Result<()>
403 where
404 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
405 {
406 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
407 let mut blens = [0usize; $rank];
408 block_loop!(dims, blocks, strides, offsets, f, blens, inner_strides;
409 elem=[$($el),+]; $($blk),+; top=$top);
410 Ok(())
411 }
412 };
413}
414
415make_kernel!(kernel_1d_inner, rank = 1);
416make_kernel!(
417 kernel_2d_inner,
418 rank = 2,
419 block = [1, 0],
420 elem = [1],
421 top = 1
422);
423make_kernel!(
424 kernel_3d_inner,
425 rank = 3,
426 block = [2, 1, 0],
427 elem = [2, 1],
428 top = 2
429);
430make_kernel!(
431 kernel_4d_inner,
432 rank = 4,
433 block = [3, 2, 1, 0],
434 elem = [3, 2, 1],
435 top = 3
436);
437make_kernel!(
438 kernel_5d_inner,
439 rank = 5,
440 block = [4, 3, 2, 1, 0],
441 elem = [4, 3, 2, 1],
442 top = 4
443);
444make_kernel!(
445 kernel_6d_inner,
446 rank = 6,
447 block = [5, 4, 3, 2, 1, 0],
448 elem = [5, 4, 3, 2, 1],
449 top = 5
450);
451make_kernel!(
452 kernel_7d_inner,
453 rank = 7,
454 block = [6, 5, 4, 3, 2, 1, 0],
455 elem = [6, 5, 4, 3, 2, 1],
456 top = 6
457);
458make_kernel!(
459 kernel_8d_inner,
460 rank = 8,
461 block = [7, 6, 5, 4, 3, 2, 1, 0],
462 elem = [7, 6, 5, 4, 3, 2, 1],
463 top = 7
464);
465
466#[inline]
471fn kernel_nd_inner_iterative<F>(
472 dims: &[usize],
473 blocks: &[usize],
474 strides: &[&[isize]],
475 offsets: &mut [isize],
476 f: &mut F,
477) -> Result<()>
478where
479 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
480{
481 let rank = dims.len();
482 debug_assert!(rank >= 9);
483
484 let d0 = dims[0];
485 let b0 = blocks[0].max(1).min(d0);
486 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
487
488 let mut idx: Vec<usize> = vec![0usize; rank];
490
491 if dims.contains(&0) {
495 return Ok(());
496 }
497 loop {
498 let mut j0 = 0usize;
500 let mut advanced = 0usize;
501 while j0 < d0 {
502 let blen0 = b0.min(d0 - j0);
503 f(offsets, blen0, &inner_strides)?;
504 j0 += blen0;
505 if j0 < d0 {
506 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
507 *offset += (blen0 as isize) * s[0];
508 }
509 advanced = j0;
510 }
511 }
512 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
513 *offset -= (advanced as isize) * s[0];
514 }
515
516 let mut level = 1usize;
518 loop {
519 if idx[level] + 1 < dims[level] {
520 idx[level] += 1;
521 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
522 *offset += s[level];
523 }
524 break;
525 }
526
527 let last = (dims[level] - 1) as isize;
528 idx[level] = 0;
529 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
530 *offset -= last * s[level];
531 }
532 level += 1;
533 if level == rank {
534 return Ok(());
535 }
536 }
537 }
538}
539
540#[inline]
560pub(crate) fn for_each_inner_block_preordered<S: AsRef<[isize]>, F>(
561 dims: &[usize],
562 blocks: &[usize],
563 strides: &[S],
564 initial_offsets: &[isize],
565 mut f: F,
566) -> Result<()>
567where
568 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
569{
570 let refs: OperandVec<&[isize]> = strides.iter().map(|s| s.as_ref()).collect();
571 preordered_dyn(dims, blocks, &refs, initial_offsets, &mut f)
572}
573
574type BlockFn<'a> = &'a mut dyn FnMut(&[isize], usize, &[isize]) -> Result<()>;
575
576#[inline(never)]
577fn preordered_dyn(
578 dims: &[usize],
579 blocks: &[usize],
580 strides: &[&[isize]],
581 initial_offsets: &[isize],
582 mut f: BlockFn<'_>,
583) -> Result<()> {
584 let rank = dims.len();
585 if rank == 0 {
586 return f(initial_offsets, 1, &[]);
587 }
588
589 let mut offsets: OperandVec<isize> = initial_offsets.iter().copied().collect();
591
592 match rank {
593 1 => kernel_1d_inner(dims, blocks, strides, &mut offsets, &mut f),
594 2 => kernel_2d_inner(dims, blocks, strides, &mut offsets, &mut f),
595 3 => kernel_3d_inner(dims, blocks, strides, &mut offsets, &mut f),
596 4 => kernel_4d_inner(dims, blocks, strides, &mut offsets, &mut f),
597 5 => kernel_5d_inner(dims, blocks, strides, &mut offsets, &mut f),
598 6 => kernel_6d_inner(dims, blocks, strides, &mut offsets, &mut f),
599 7 => kernel_7d_inner(dims, blocks, strides, &mut offsets, &mut f),
600 8 => kernel_8d_inner(dims, blocks, strides, &mut offsets, &mut f),
601 _ => kernel_nd_inner_iterative(dims, blocks, strides, &mut offsets, &mut f),
602 }
603}
604
605pub fn ensure_same_shape(a: &[usize], b: &[usize]) -> Result<()> {
624 if a.len() != b.len() {
625 return Err(crate::StridedError::RankMismatch(a.len(), b.len()));
626 }
627 if a != b {
628 return Err(crate::StridedError::ShapeMismatch(a.to_vec(), b.to_vec()));
629 }
630 Ok(())
631}
632
633#[derive(Copy, Clone, Debug, Eq, PartialEq)]
634pub(crate) enum ContiguousLayout {
635 RowMajor,
637 ColMajor,
639}
640
641pub(crate) fn contiguous_layout(dims: &[usize], strides: &[isize]) -> Option<ContiguousLayout> {
647 if dims.len() != strides.len() {
648 return None;
649 }
650 if dims.is_empty() {
651 return Some(ContiguousLayout::RowMajor);
652 }
653
654 let mut expected = 1isize;
656 let mut row_ok = true;
657 for (&dim, &stride) in dims.iter().rev().zip(strides.iter().rev()) {
658 if dim <= 1 {
659 continue;
660 }
661 if stride != expected {
662 row_ok = false;
663 break;
664 }
665 expected = expected.saturating_mul(dim as isize);
666 }
667 if row_ok {
668 return Some(ContiguousLayout::RowMajor);
669 }
670
671 let mut expected = 1isize;
673 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
674 if dim <= 1 {
675 continue;
676 }
677 if stride != expected {
678 return None;
679 }
680 expected = expected.saturating_mul(dim as isize);
681 }
682 Some(ContiguousLayout::ColMajor)
683}
684
685pub(crate) fn total_len(dims: &[usize]) -> Result<usize> {
693 if dims.contains(&0) {
694 return Ok(0);
695 }
696 dims.iter()
697 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
698 .ok_or(StridedError::OffsetOverflow)
699}
700
701#[inline]
708pub(crate) fn use_sequential_fast_path(
709 class: crate::cost::KernelClass,
710 total: usize,
711 exec: &Exec<'_>,
712) -> bool {
713 !crate::threading::is_parallel(class, total, exec)
714}
715
716#[inline]
722pub(crate) fn same_contiguous_layout(
723 dims: &[usize],
724 strides_list: &[&[isize]],
725) -> Option<ContiguousLayout> {
726 let first = contiguous_layout(dims, strides_list.first()?)?;
727 for strides in &strides_list[1..] {
728 if contiguous_layout(dims, strides)? != first {
729 return None;
730 }
731 }
732 Some(first)
733}
734
735#[inline]
744pub(crate) fn sequential_contiguous_layout(
745 class: crate::cost::KernelClass,
746 dims: &[usize],
747 strides_list: &[&[isize]],
748 exec: &Exec<'_>,
749) -> Result<Option<ContiguousLayout>> {
750 if !use_sequential_fast_path(class, total_len(dims)?, exec) {
751 return Ok(None);
752 }
753 Ok(same_contiguous_layout(dims, strides_list))
754}
755
756#[cfg(test)]
757#[path = "kernel/tests/tests.rs"]
758mod tests;