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_sizes: &[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_sizes);
47 KernelPlan { order, block }
48}
49
50pub(crate) fn pointwise_plan(
54 dims: &[usize],
55 strides_list: &[&[isize]],
56 dest_index: Option<usize>,
57 elem_sizes: &[usize],
58 total: usize,
59) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
60 debug_assert_eq!(strides_list.len(), elem_sizes.len());
61 if total <= SMALL_TENSOR_THRESHOLD {
62 build_plan_fused_small(dims, strides_list)
63 } else {
64 build_plan_fused(dims, strides_list, dest_index, elem_sizes)
65 }
66}
67
68pub(crate) fn build_plan_fused(
83 dims: &[usize],
84 strides_list: &[&[isize]],
85 dest_index: Option<usize>,
86 elem_sizes: &[usize],
87) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
88 plan_fused(dims, strides_list, dest_index, elem_sizes, dest_index)
89}
90
91pub(crate) fn fold_plan(
96 dims: &[usize],
97 strides_list: &[&[isize]],
98 order_by: usize,
99 elem_sizes: &[usize],
100 total: usize,
101) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
102 debug_assert_eq!(strides_list.len(), elem_sizes.len());
103 if total <= SMALL_TENSOR_THRESHOLD {
104 build_plan_fused_small(dims, strides_list)
105 } else {
106 plan_fused(dims, strides_list, Some(order_by), elem_sizes, None)
107 }
108}
109
110fn plan_fused(
113 dims: &[usize],
114 strides_list: &[&[isize]],
115 dest_index: Option<usize>,
116 elem_sizes: &[usize],
117 fit_dest: Option<usize>,
118) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
119 let order = order::compute_order(dims, strides_list, dest_index);
121
122 let ordered_dims: InlineVec<usize> = order.iter().map(|&d| dims[d]).collect();
124 let ordered_strides: OperandVec<InlineVec<isize>> = strides_list
125 .iter()
126 .map(|strides| order.iter().map(|&d| strides[d]).collect())
127 .collect();
128 let ordered_strides_refs: OperandVec<&[isize]> =
129 ordered_strides.iter().map(|s| s.as_slice()).collect();
130
131 let fused_dims = fuse_dims(&ordered_dims, &ordered_strides_refs);
133
134 let (compressed_dims, compressed_strides) = compress_dims(&fused_dims, &ordered_strides_refs);
136 let compressed_strides_refs: OperandVec<&[isize]> =
137 compressed_strides.iter().map(|s| s.as_slice()).collect();
138
139 let identity: InlineVec<usize> = (0..compressed_dims.len()).collect();
143 let block = match fit_dest {
144 Some(dest) => block::destination_block_sizes(
145 &compressed_dims,
146 &compressed_strides_refs,
147 elem_sizes,
148 dest,
149 ),
150 None => block::compute_block_sizes(&compressed_dims, &compressed_strides_refs, elem_sizes),
151 };
152 #[cfg(feature = "bench-hooks")]
153 let block = {
154 let forced = crate::bench_hooks::FORCED_TILES.lock().unwrap();
155 if fit_dest.is_some() && forced.len() == block.len() {
156 InlineVec::from(forced.as_slice())
157 } else {
158 block
159 }
160 };
161
162 (
163 compressed_dims,
164 compressed_strides,
165 KernelPlan {
166 order: identity,
167 block,
168 },
169 )
170}
171
172pub(crate) fn build_plan_fused_small(
181 dims: &[usize],
182 strides_list: &[&[isize]],
183) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>, KernelPlan) {
184 let fused = fuse_dims(dims, strides_list);
186 let (fused_dims, fused_strides) = compress_dims(&fused, strides_list);
187
188 let block = fused_dims.clone();
190 let identity: InlineVec<usize> = (0..fused_dims.len()).collect();
191
192 (
193 fused_dims,
194 fused_strides,
195 KernelPlan {
196 order: identity,
197 block,
198 },
199 )
200}
201
202#[cfg(test)]
212#[inline]
213pub(crate) fn for_each_inner_block<F>(
214 dims: &[usize],
215 plan: &KernelPlan,
216 strides_list: &[&[isize]],
217 mut f: F,
218) -> Result<()>
219where
220 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
221{
222 let rank = dims.len();
223 if rank == 0 {
224 let offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
225 return f(&offsets, 1, &[]);
226 }
227
228 let ordered_dims: InlineVec<usize> = plan.order.iter().map(|&d| dims[d]).collect();
230 let ordered_blocks: InlineVec<usize> = plan.block.clone();
231
232 let mut ordered_strides: OperandVec<InlineVec<isize>> = OperandVec::new();
234 for strides in strides_list {
235 ordered_strides.push(plan.order.iter().map(|&d| strides[d]).collect());
236 }
237 let ordered_strides_refs: OperandVec<&[isize]> =
238 ordered_strides.iter().map(|s| s.as_slice()).collect();
239
240 let mut offsets: OperandVec<isize> = strides_list.iter().map(|_| 0isize).collect();
242
243 match rank {
245 1 => kernel_1d_inner(
246 &ordered_dims,
247 &ordered_blocks,
248 &ordered_strides_refs,
249 &mut offsets,
250 &mut f,
251 ),
252 2 => kernel_2d_inner(
253 &ordered_dims,
254 &ordered_blocks,
255 &ordered_strides_refs,
256 &mut offsets,
257 &mut f,
258 ),
259 3 => kernel_3d_inner(
260 &ordered_dims,
261 &ordered_blocks,
262 &ordered_strides_refs,
263 &mut offsets,
264 &mut f,
265 ),
266 4 => kernel_4d_inner(
267 &ordered_dims,
268 &ordered_blocks,
269 &ordered_strides_refs,
270 &mut offsets,
271 &mut f,
272 ),
273 5 => kernel_5d_inner(
274 &ordered_dims,
275 &ordered_blocks,
276 &ordered_strides_refs,
277 &mut offsets,
278 &mut f,
279 ),
280 6 => kernel_6d_inner(
281 &ordered_dims,
282 &ordered_blocks,
283 &ordered_strides_refs,
284 &mut offsets,
285 &mut f,
286 ),
287 7 => kernel_7d_inner(
288 &ordered_dims,
289 &ordered_blocks,
290 &ordered_strides_refs,
291 &mut offsets,
292 &mut f,
293 ),
294 8 => kernel_8d_inner(
295 &ordered_dims,
296 &ordered_blocks,
297 &ordered_strides_refs,
298 &mut offsets,
299 &mut f,
300 ),
301 _ => kernel_nd_inner_iterative(
302 &ordered_dims,
303 &ordered_blocks,
304 &ordered_strides_refs,
305 &mut offsets,
306 &mut f,
307 ),
308 }
309}
310
311macro_rules! elem_loops {
330 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident; $lv:literal) => {
334 for _i in 0..$blens[$lv] {
335 $f($offsets, $blens[0], &$is)?;
336 if _i + 1 < $blens[$lv] {
337 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
338 *o += s[$lv];
339 }
340 }
341 }
342 let _back = $blens[$lv].saturating_sub(1) as isize;
343 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
344 *o -= _back * s[$lv];
345 }
346 };
347 ($offsets:ident, $strides:ident, $f:ident, $blens:ident, $is:ident;
350 $lv:literal, $next:literal $(, $rest:literal)*) => {
351 for _i in 0..$blens[$lv] {
352 elem_loops!($offsets, $strides, $f, $blens, $is; $next $(, $rest)*);
353 if _i + 1 < $blens[$lv] {
354 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
355 *o += s[$lv];
356 }
357 }
358 }
359 let _back = $blens[$lv].saturating_sub(1) as isize;
360 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
361 *o -= _back * s[$lv];
362 }
363 };
364}
365
366macro_rules! block_loop {
373 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
375 $blens:ident, $is:ident; elem=[$($el:literal),+]; $lv0:literal; top=$top:literal) => {{
376 let mut _j = 0usize;
377 let mut _advanced = 0usize;
378 while _j < $dims[$lv0] {
379 $blens[$lv0] = $blocks[$lv0].max(1).min($dims[$lv0]).min($dims[$lv0] - _j);
380 elem_loops!($offsets, $strides, $f, $blens, $is; $($el),+);
381 _j += $blens[$lv0];
382 if _j < $dims[$lv0] {
383 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
384 *o += ($blens[$lv0] as isize) * s[$lv0];
385 }
386 _advanced = _j;
387 }
388 }
389 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
390 *o -= (_advanced as isize) * s[$lv0];
391 }
392 }};
393 ($dims:ident, $blocks:ident, $strides:ident, $offsets:ident, $f:ident,
395 $blens:ident, $is:ident; elem=[$($el:literal),+];
396 $lv:literal, $next:literal $(, $rest:literal)*; top=$top:literal) => {{
397 let mut _j = 0usize;
398 let mut _advanced = 0usize;
399 while _j < $dims[$lv] {
400 $blens[$lv] = $blocks[$lv].max(1).min($dims[$lv]).min($dims[$lv] - _j);
401 block_loop!($dims, $blocks, $strides, $offsets, $f, $blens, $is;
402 elem=[$($el),+]; $next $(, $rest)*; top=$top);
403 _j += $blens[$lv];
404 if _j < $dims[$lv] {
405 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
406 *o += ($blens[$lv] as isize) * s[$lv];
407 }
408 _advanced = _j;
409 }
410 }
411 for (o, s) in $offsets.iter_mut().zip($strides.iter()) {
412 *o -= (_advanced as isize) * s[$lv];
413 }
414 }};
415}
416
417macro_rules! make_kernel {
424 ($name:ident, rank=1) => {
426 #[inline]
427 fn $name<F>(
428 dims: &[usize],
429 blocks: &[usize],
430 strides: &[&[isize]],
431 offsets: &mut [isize],
432 f: &mut F,
433 ) -> Result<()>
434 where
435 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
436 {
437 let d0 = dims[0];
438 let b0 = blocks[0].max(1).min(d0);
439 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
440
441 let mut j0 = 0usize;
442 let mut advanced = 0usize;
443 while j0 < d0 {
444 let blen0 = b0.min(d0 - j0);
445 f(offsets, blen0, &inner_strides)?;
446 j0 += blen0;
447 if j0 < d0 {
448 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
449 *o += (blen0 as isize) * s[0];
450 }
451 advanced = j0;
452 }
453 }
454 for (o, s) in offsets.iter_mut().zip(strides.iter()) {
455 *o -= (advanced as isize) * s[0];
456 }
457 Ok(())
458 }
459 };
460 ($name:ident, rank=$rank:literal,
465 block=[$($blk:literal),+], elem=[$($el:literal),+], top=$top:literal) => {
466 #[inline]
467 fn $name<F>(
468 dims: &[usize],
469 blocks: &[usize],
470 strides: &[&[isize]],
471 offsets: &mut [isize],
472 f: &mut F,
473 ) -> Result<()>
474 where
475 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
476 {
477 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
478 let mut blens = [0usize; $rank];
479 block_loop!(dims, blocks, strides, offsets, f, blens, inner_strides;
480 elem=[$($el),+]; $($blk),+; top=$top);
481 Ok(())
482 }
483 };
484}
485
486make_kernel!(kernel_1d_inner, rank = 1);
487make_kernel!(
488 kernel_2d_inner,
489 rank = 2,
490 block = [1, 0],
491 elem = [1],
492 top = 1
493);
494make_kernel!(
495 kernel_3d_inner,
496 rank = 3,
497 block = [2, 1, 0],
498 elem = [2, 1],
499 top = 2
500);
501make_kernel!(
502 kernel_4d_inner,
503 rank = 4,
504 block = [3, 2, 1, 0],
505 elem = [3, 2, 1],
506 top = 3
507);
508make_kernel!(
509 kernel_5d_inner,
510 rank = 5,
511 block = [4, 3, 2, 1, 0],
512 elem = [4, 3, 2, 1],
513 top = 4
514);
515make_kernel!(
516 kernel_6d_inner,
517 rank = 6,
518 block = [5, 4, 3, 2, 1, 0],
519 elem = [5, 4, 3, 2, 1],
520 top = 5
521);
522make_kernel!(
523 kernel_7d_inner,
524 rank = 7,
525 block = [6, 5, 4, 3, 2, 1, 0],
526 elem = [6, 5, 4, 3, 2, 1],
527 top = 6
528);
529make_kernel!(
530 kernel_8d_inner,
531 rank = 8,
532 block = [7, 6, 5, 4, 3, 2, 1, 0],
533 elem = [7, 6, 5, 4, 3, 2, 1],
534 top = 7
535);
536
537#[inline]
542fn kernel_nd_inner_iterative<F>(
543 dims: &[usize],
544 blocks: &[usize],
545 strides: &[&[isize]],
546 offsets: &mut [isize],
547 f: &mut F,
548) -> Result<()>
549where
550 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
551{
552 let rank = dims.len();
553 debug_assert!(rank >= 9);
554
555 let d0 = dims[0];
556 let b0 = blocks[0].max(1).min(d0);
557 let inner_strides: OperandVec<isize> = strides.iter().map(|s| s[0]).collect();
558
559 let mut idx: Vec<usize> = vec![0usize; rank];
561
562 if dims.contains(&0) {
566 return Ok(());
567 }
568 loop {
569 let mut j0 = 0usize;
571 let mut advanced = 0usize;
572 while j0 < d0 {
573 let blen0 = b0.min(d0 - j0);
574 f(offsets, blen0, &inner_strides)?;
575 j0 += blen0;
576 if j0 < d0 {
577 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
578 *offset += (blen0 as isize) * s[0];
579 }
580 advanced = j0;
581 }
582 }
583 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
584 *offset -= (advanced as isize) * s[0];
585 }
586
587 let mut level = 1usize;
589 loop {
590 if idx[level] + 1 < dims[level] {
591 idx[level] += 1;
592 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
593 *offset += s[level];
594 }
595 break;
596 }
597
598 let last = (dims[level] - 1) as isize;
599 idx[level] = 0;
600 for (offset, s) in offsets.iter_mut().zip(strides.iter()) {
601 *offset -= last * s[level];
602 }
603 level += 1;
604 if level == rank {
605 return Ok(());
606 }
607 }
608 }
609}
610
611#[inline]
631pub(crate) fn for_each_inner_block_preordered<S: AsRef<[isize]>, F>(
632 dims: &[usize],
633 blocks: &[usize],
634 strides: &[S],
635 initial_offsets: &[isize],
636 mut f: F,
637) -> Result<()>
638where
639 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
640{
641 let refs: OperandVec<&[isize]> = strides.iter().map(|s| s.as_ref()).collect();
642 preordered_dyn(dims, blocks, &refs, initial_offsets, &mut f)
643}
644
645type BlockFn<'a> = &'a mut dyn FnMut(&[isize], usize, &[isize]) -> Result<()>;
646
647#[inline(never)]
648fn preordered_dyn(
649 dims: &[usize],
650 blocks: &[usize],
651 strides: &[&[isize]],
652 initial_offsets: &[isize],
653 mut f: BlockFn<'_>,
654) -> Result<()> {
655 let rank = dims.len();
656 if rank == 0 {
657 return f(initial_offsets, 1, &[]);
658 }
659
660 let mut offsets: OperandVec<isize> = initial_offsets.iter().copied().collect();
662
663 match rank {
664 1 => kernel_1d_inner(dims, blocks, strides, &mut offsets, &mut f),
665 2 => kernel_2d_inner(dims, blocks, strides, &mut offsets, &mut f),
666 3 => kernel_3d_inner(dims, blocks, strides, &mut offsets, &mut f),
667 4 => kernel_4d_inner(dims, blocks, strides, &mut offsets, &mut f),
668 5 => kernel_5d_inner(dims, blocks, strides, &mut offsets, &mut f),
669 6 => kernel_6d_inner(dims, blocks, strides, &mut offsets, &mut f),
670 7 => kernel_7d_inner(dims, blocks, strides, &mut offsets, &mut f),
671 8 => kernel_8d_inner(dims, blocks, strides, &mut offsets, &mut f),
672 _ => kernel_nd_inner_iterative(dims, blocks, strides, &mut offsets, &mut f),
673 }
674}
675
676pub fn ensure_same_shape(a: &[usize], b: &[usize]) -> Result<()> {
695 if a.len() != b.len() {
696 return Err(crate::StridedError::RankMismatch(a.len(), b.len()));
697 }
698 if a != b {
699 return Err(crate::StridedError::ShapeMismatch(a.to_vec(), b.to_vec()));
700 }
701 Ok(())
702}
703
704#[derive(Copy, Clone, Debug, Eq, PartialEq)]
705pub(crate) enum ContiguousLayout {
706 RowMajor,
708 ColMajor,
710}
711
712pub(crate) fn contiguous_layout(dims: &[usize], strides: &[isize]) -> Option<ContiguousLayout> {
718 if dims.len() != strides.len() {
719 return None;
720 }
721 if dims.is_empty() {
722 return Some(ContiguousLayout::RowMajor);
723 }
724
725 let mut expected = 1isize;
727 let mut row_ok = true;
728 for (&dim, &stride) in dims.iter().rev().zip(strides.iter().rev()) {
729 if dim <= 1 {
730 continue;
731 }
732 if stride != expected {
733 row_ok = false;
734 break;
735 }
736 expected = expected.saturating_mul(dim as isize);
737 }
738 if row_ok {
739 return Some(ContiguousLayout::RowMajor);
740 }
741
742 let mut expected = 1isize;
744 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
745 if dim <= 1 {
746 continue;
747 }
748 if stride != expected {
749 return None;
750 }
751 expected = expected.saturating_mul(dim as isize);
752 }
753 Some(ContiguousLayout::ColMajor)
754}
755
756pub(crate) fn total_len(dims: &[usize]) -> Result<usize> {
764 if dims.contains(&0) {
765 return Ok(0);
766 }
767 dims.iter()
768 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
769 .ok_or(StridedError::OffsetOverflow)
770}
771
772#[inline]
779pub(crate) fn use_sequential_fast_path(
780 class: crate::cost::KernelClass,
781 total: usize,
782 exec: &Exec<'_>,
783) -> bool {
784 !crate::threading::is_parallel(class, total, exec)
785}
786
787#[inline]
793pub(crate) fn same_contiguous_layout(
794 dims: &[usize],
795 strides_list: &[&[isize]],
796) -> Option<ContiguousLayout> {
797 let first = contiguous_layout(dims, strides_list.first()?)?;
798 for strides in &strides_list[1..] {
799 if contiguous_layout(dims, strides)? != first {
800 return None;
801 }
802 }
803 Some(first)
804}
805
806#[inline]
815pub(crate) fn sequential_contiguous_layout(
816 class: crate::cost::KernelClass,
817 dims: &[usize],
818 strides_list: &[&[isize]],
819 exec: &Exec<'_>,
820) -> Result<Option<ContiguousLayout>> {
821 if !use_sequential_fast_path(class, total_len(dims)?, exec) {
822 return Ok(None);
823 }
824 Ok(same_contiguous_layout(dims, strides_list))
825}
826
827#[cfg(test)]
828#[path = "kernel/tests/tests.rs"]
829mod tests;