use crate::cost::KernelClass;
use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
use core::mem::MaybeUninit;
use core::num::NonZeroUsize;
use core::ops::{Add, Mul};
pub const RAW_FUSED_RANK_LIMIT: usize = 8;
pub(crate) const MAX_MOVING_AXES: usize = usize::BITS as usize;
#[derive(Clone, Copy, Debug)]
pub(crate) struct FusedAxis {
pub(crate) dim: usize,
pub(crate) dst: isize,
pub(crate) src: isize,
}
const EMPTY_AXIS: FusedAxis = FusedAxis {
dim: 1,
dst: 0,
src: 0,
};
#[derive(Clone, Copy, Debug)]
pub(crate) struct FusedPairLayout {
pub(crate) rank: usize,
pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
pub(crate) dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
pub(crate) src_strides: [isize; RAW_FUSED_RANK_LIMIT],
}
impl FusedPairLayout {
fn empty() -> Self {
Self {
rank: 0,
dims: [1; RAW_FUSED_RANK_LIMIT],
dst_strides: [0; RAW_FUSED_RANK_LIMIT],
src_strides: [0; RAW_FUSED_RANK_LIMIT],
}
}
fn from_axes(axes: &[FusedAxis]) -> Self {
debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
let mut layout = Self {
rank: axes.len(),
dims: [1; RAW_FUSED_RANK_LIMIT],
dst_strides: [0; RAW_FUSED_RANK_LIMIT],
src_strides: [0; RAW_FUSED_RANK_LIMIT],
};
for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
*slot = axis.dim;
}
for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
*slot = axis.dst;
}
for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
*slot = axis.src;
}
layout
}
}
#[derive(Clone, Debug)]
pub(crate) enum PairTraversal {
Inline(FusedPairLayout),
Spilled(Vec<FusedAxis>),
}
impl Default for FusedPairLayout {
fn default() -> Self {
Self::empty()
}
}
impl Default for PairTraversal {
fn default() -> Self {
Self::empty()
}
}
impl PairTraversal {
#[inline]
fn empty() -> Self {
Self::Inline(FusedPairLayout::empty())
}
pub(crate) fn with_route<D, S, R>(&self, f: impl FnOnce(Route<'_>) -> R) -> R {
match self {
Self::Inline(layout) => {
let tiles = pair_tiles::<D, S>(layout);
f(Route::Inline {
layout,
tiles: tiles.as_ref(),
})
}
Self::Spilled(axes) => with_spilled_route::<D, S, R>(axes, f),
}
}
#[cfg(test)]
pub(crate) fn tiles<D, S>(&self) -> Option<Tiles> {
self.with_route::<D, S, _>(|route| route.snapshot())
}
pub(crate) fn may_tile(&self) -> bool {
let (total, moving) = match self {
Self::Inline(layout) => (
fused_total(layout),
layout.dims[..layout.rank]
.iter()
.filter(|&&dim| dim != 1)
.count(),
),
Self::Spilled(axes) => (
spilled_total(axes),
axes.iter().filter(|axis| axis.dim != 1).count(),
),
};
total > 1 && moving >= 2
}
#[inline]
pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
match self {
Self::Inline(layout) => Some(layout),
Self::Spilled(_) => None,
}
}
#[cfg(test)]
pub(crate) fn rank(&self) -> usize {
match self {
Self::Inline(layout) => layout.rank,
Self::Spilled(axes) => axes.len(),
}
}
}
fn fuse_axes(
scratch: &mut [FusedAxis],
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> usize {
debug_assert!(scratch.len() >= dims.len());
let mut rank = 0usize;
for axis in 0..dims.len() {
if dims[axis] == 1 {
continue;
}
if dims[axis] == 0 {
scratch[0] = FusedAxis {
dim: 0,
dst: 0,
src: 0,
};
return 1;
}
let entry = FusedAxis {
dim: dims[axis],
dst: dst_strides[axis],
src: src_strides[axis],
};
let mut position = rank;
while position > 0 && scratch[position - 1].dst > entry.dst {
scratch[position] = scratch[position - 1];
position -= 1;
}
scratch[position] = entry;
rank += 1;
}
if rank == 0 {
scratch[0] = EMPTY_AXIS;
return 1;
}
let mut fused = 0usize;
for axis in 1..rank {
let merged = isize::try_from(scratch[fused].dim)
.ok()
.filter(|&extent| {
scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
&& scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
})
.and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
if let Some(merged) = merged {
scratch[fused].dim = merged;
} else {
fused += 1;
scratch[fused] = scratch[axis];
}
}
fused + 1
}
pub(crate) fn fuse_pair_traversal(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> PairTraversal {
if dims.len() <= RAW_FUSED_RANK_LIMIT {
let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
}
let mut scratch = vec![EMPTY_AXIS; dims.len()];
let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
scratch.truncate(rank);
if rank <= RAW_FUSED_RANK_LIMIT {
PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
} else {
PairTraversal::Spilled(scratch)
}
}
impl PairTraversal {
#[cfg(test)]
pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
with_given_route::<(), (), _>(dims, dst_strides, src_strides, |route| match route {
Route::Inline { layout, .. } => Self::Inline(*layout),
Route::Spilled { axes, .. } => Self::Spilled(axes.to_vec()),
})
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Route<'a> {
Inline {
layout: &'a FusedPairLayout,
tiles: Option<&'a PairTiles>,
},
Spilled {
axes: &'a [FusedAxis],
tiles: Option<&'a SpilledTiles>,
},
}
impl<'a> Route<'a> {
pub(crate) fn is_tiled(&self) -> bool {
match self {
Self::Inline { tiles, .. } => tiles.is_some(),
Self::Spilled { tiles, .. } => tiles.is_some(),
}
}
pub(crate) fn untiled(self) -> Self {
match self {
Self::Inline { layout, .. } => Self::Inline {
layout,
tiles: None,
},
Self::Spilled { axes, .. } => Self::Spilled { axes, tiles: None },
}
}
#[cfg(feature = "bench-hooks")]
pub(crate) fn blocks(&self) -> Option<&'a [usize]> {
match *self {
Self::Inline { tiles, .. } => tiles.map(|tiles| &tiles.blocks[..tiles.layout.rank]),
Self::Spilled { tiles, .. } => tiles.map(SpilledTiles::blocks),
}
}
#[cfg(test)]
pub(crate) fn snapshot(self) -> Option<Tiles> {
match self {
Self::Inline { tiles, .. } => tiles.copied().map(Tiles::Inline),
Self::Spilled { tiles, .. } => tiles.copied().map(Tiles::Spilled),
}
}
}
pub(crate) fn with_given_route<D, S, R>(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
f: impl FnOnce(Route<'_>) -> R,
) -> R {
debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
let rank = dims.len();
if rank > RAW_FUSED_RANK_LIMIT {
return with_wide_given_route::<D, S, R>(dims, dst_strides, src_strides, f);
}
let mut layout = FusedPairLayout::empty();
layout.rank = rank.max(1);
layout.dims[..rank].copy_from_slice(dims);
layout.dst_strides[..rank].copy_from_slice(dst_strides);
layout.src_strides[..rank].copy_from_slice(src_strides);
let tiles = pair_tiles::<D, S>(&layout);
f(Route::Inline {
layout: &layout,
tiles: tiles.as_ref(),
})
}
#[inline(never)]
fn with_wide_given_route<D, S, R>(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
f: impl FnOnce(Route<'_>) -> R,
) -> R {
let mut axes = [EMPTY_AXIS; MAX_MOVING_AXES];
let mut moving = 0;
for ((&dim, &dst), &src) in dims.iter().zip(dst_strides).zip(src_strides) {
if dim == 1 {
continue;
}
axes[moving] = FusedAxis { dim, dst, src };
moving += 1;
}
if moving <= RAW_FUSED_RANK_LIMIT {
let layout = FusedPairLayout::from_axes(if moving == 0 {
&[EMPTY_AXIS]
} else {
&axes[..moving]
});
let tiles = pair_tiles::<D, S>(&layout);
return f(Route::Inline {
layout: &layout,
tiles: tiles.as_ref(),
});
}
with_spilled_route::<D, S, R>(&axes[..moving], f)
}
#[inline(never)]
fn with_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
debug_assert!(axes.len() > RAW_FUSED_RANK_LIMIT && axes.iter().all(|axis| axis.dim >= 2));
if crate::block::exits_before_metadata(
axes.iter().map(|axis| (axis.dim, axis.dst, axis.src)),
core::mem::size_of::<D>(),
core::mem::size_of::<S>(),
) {
return f(Route::Spilled { axes, tiles: None });
}
with_modelled_spilled_route::<D, S, R>(axes, f)
}
#[inline(never)]
fn with_modelled_spilled_route<D, S, R>(axes: &[FusedAxis], f: impl FnOnce(Route<'_>) -> R) -> R {
let mut tiles = SpilledTiles::EMPTY;
let tiled = spilled_tiles::<D, S>(axes, &mut tiles);
f(Route::Spilled {
axes,
tiles: tiled.then_some(&tiles),
})
}
pub(crate) fn fuse_pair_layout(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> Option<FusedPairLayout> {
match fuse_pair_traversal(dims, dst_strides, src_strides) {
PairTraversal::Inline(layout) => Some(layout),
PairTraversal::Spilled(_) => None,
}
}
#[inline]
pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
layout.dims[..layout.rank].iter().product()
}
#[inline]
fn spilled_total(axes: &[FusedAxis]) -> usize {
axes.iter().map(|axis| axis.dim).product()
}
#[cfg(test)]
#[derive(Clone, Debug)]
#[allow(clippy::large_enum_variant)] pub(crate) enum Tiles {
Inline(PairTiles),
Spilled(SpilledTiles),
}
#[cfg(test)]
impl Tiles {
pub(crate) fn inline(&self) -> Option<&PairTiles> {
match self {
Self::Inline(tiles) => Some(tiles),
Self::Spilled(_) => None,
}
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct SpilledTiles {
rank: usize,
dims: [usize; MAX_MOVING_AXES],
dst: [isize; MAX_MOVING_AXES],
src: [isize; MAX_MOVING_AXES],
blocks: [usize; MAX_MOVING_AXES],
}
impl SpilledTiles {
const EMPTY: Self = Self {
rank: 0,
dims: [1; MAX_MOVING_AXES],
dst: [0; MAX_MOVING_AXES],
src: [0; MAX_MOVING_AXES],
blocks: [1; MAX_MOVING_AXES],
};
pub(crate) fn dims(&self) -> &[usize] {
&self.dims[..self.rank]
}
pub(crate) fn dst(&self) -> &[isize] {
&self.dst[..self.rank]
}
pub(crate) fn src(&self) -> &[isize] {
&self.src[..self.rank]
}
pub(crate) fn blocks(&self) -> &[usize] {
&self.blocks[..self.rank]
}
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct PairTiles {
pub(crate) layout: FusedPairLayout,
pub(crate) blocks: [usize; RAW_FUSED_RANK_LIMIT],
}
pub(crate) fn pair_tiles<D, S>(layout: &FusedPairLayout) -> Option<PairTiles> {
if fused_total(layout) <= 1 {
return None;
}
let moving = layout.dims[..layout.rank]
.iter()
.filter(|&&dim| dim != 1)
.count();
if moving < 2 {
return None;
}
let compressed;
let layout = if moving == layout.rank {
layout
} else {
compressed = without_unit_axes(layout);
&compressed
};
let rank = layout.rank;
let mut blocks = [1; RAW_FUSED_RANK_LIMIT];
tile_blocks::<D, S, { 2 * RAW_FUSED_RANK_LIMIT }, RAW_FUSED_RANK_LIMIT>(
&layout.dims[..rank],
&layout.dst_strides[..rank],
&layout.src_strides[..rank],
&mut blocks[..rank],
)
.then_some(PairTiles {
layout: *layout,
blocks,
})
}
fn tile_blocks<D, S, const ORDERS: usize, const AXES: usize>(
dims: &[usize],
dst: &[isize],
src: &[isize],
blocks: &mut [usize],
) -> bool {
let strides = [dst, src];
let elem_sizes = [core::mem::size_of::<D>(), core::mem::size_of::<S>()];
if crate::block::model_exits(dims, &strides, &elem_sizes) {
return false;
}
let rank = dims.len();
let mut orders = [0usize; ORDERS];
let mut costs = [0isize; AXES];
crate::block::reduced_block_sizes_into(
dims,
&strides,
&elem_sizes,
blocks,
&mut orders[..2 * rank],
&mut costs[..rank],
);
let Some(first_cut) = (0..dims.len()).find(|&axis| blocks[axis] < dims[axis]) else {
return false;
};
if blocks[first_cut + 1..].iter().all(|&block| block == 1) {
return false;
}
if crate::block::declines_tiles(dims, &strides, &elem_sizes, blocks) {
return false;
}
crate::block::fit_l1_sets(dims, &strides, &elem_sizes, 0, blocks);
true
}
fn spilled_tiles<D, S>(axes: &[FusedAxis], tiles: &mut SpilledTiles) -> bool {
let rank = axes.len();
tiles.rank = rank;
for (axis, entry) in axes.iter().enumerate() {
tiles.dims[axis] = entry.dim;
tiles.dst[axis] = entry.dst;
tiles.src[axis] = entry.src;
}
tile_blocks::<D, S, { 2 * MAX_MOVING_AXES }, MAX_MOVING_AXES>(
&tiles.dims[..rank],
&tiles.dst[..rank],
&tiles.src[..rank],
&mut tiles.blocks[..rank],
)
}
fn without_unit_axes(layout: &FusedPairLayout) -> FusedPairLayout {
let mut compressed = FusedPairLayout::empty();
let mut rank = 0;
for axis in 0..layout.rank {
if layout.dims[axis] == 1 {
continue;
}
compressed.dims[rank] = layout.dims[axis];
compressed.dst_strides[rank] = layout.dst_strides[axis];
compressed.src_strides[rank] = layout.src_strides[axis];
rank += 1;
}
compressed.rank = rank;
compressed
}
#[inline(never)]
pub(crate) unsafe fn apply_tiled_box<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
tile_box: &FusedPairLayout,
blocks: &[usize; RAW_FUSED_RANK_LIMIT],
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
let tiles = tile_count(tile_box, blocks);
unsafe {
apply_tile_range(
dst_ptr, dst_base, src_ptr, src_base, tile_box, blocks, 0, tiles, apply,
);
}
}
pub(crate) fn tile_count(
tile_box: &FusedPairLayout,
blocks: &[usize; RAW_FUSED_RANK_LIMIT],
) -> usize {
tile_box.dims[..tile_box.rank]
.iter()
.zip(blocks)
.map(|(&dim, &block)| dim.div_ceil(block))
.product()
}
#[allow(clippy::too_many_arguments)]
#[inline(never)]
pub(crate) unsafe fn apply_tile_range<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
tile_box: &FusedPairLayout,
blocks: &[usize; RAW_FUSED_RANK_LIMIT],
first: usize,
count: usize,
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
if count == 0 {
return;
}
let rank = tile_box.rank;
let mut tile = *tile_box;
let mut origin = [0usize; RAW_FUSED_RANK_LIMIT];
let mut dst_tile = dst_base;
let mut src_tile = src_base;
let mut rest = first;
for axis in 0..rank {
let along = tile_box.dims[axis].div_ceil(blocks[axis]);
origin[axis] = (rest % along) * blocks[axis];
rest /= along;
dst_tile += origin[axis] as isize * tile_box.dst_strides[axis];
src_tile += origin[axis] as isize * tile_box.src_strides[axis];
tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - origin[axis]);
}
let mut left = count;
loop {
#[cfg(test)]
crate::threading::record_tile_box();
unsafe {
apply_fused_range(
dst_ptr,
dst_tile,
src_ptr,
src_tile,
&tile,
0,
fused_total(&tile),
apply,
);
}
left -= 1;
if left == 0 {
return;
}
let mut axis = 0;
loop {
debug_assert!(axis < rank, "tile range past the end of the grid");
let next = origin[axis] + blocks[axis];
if next < tile_box.dims[axis] {
origin[axis] = next;
dst_tile += blocks[axis] as isize * tile_box.dst_strides[axis];
src_tile += blocks[axis] as isize * tile_box.src_strides[axis];
tile.dims[axis] = blocks[axis].min(tile_box.dims[axis] - next);
break;
}
dst_tile -= origin[axis] as isize * tile_box.dst_strides[axis];
src_tile -= origin[axis] as isize * tile_box.src_strides[axis];
origin[axis] = 0;
tile.dims[axis] = blocks[axis].min(tile_box.dims[axis]);
axis += 1;
}
}
}
#[allow(clippy::too_many_arguments)]
#[inline(never)]
pub(crate) unsafe fn apply_spilled_tiled_box<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
tiles: &SpilledTiles,
box_dims: &[usize],
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
let rank = box_dims.len();
let mut tile_axes = [EMPTY_AXIS; MAX_MOVING_AXES];
let tile = &mut tile_axes[..rank];
for (axis, slot) in tile.iter_mut().enumerate() {
slot.dst = tiles.dst[axis];
slot.src = tiles.src[axis];
}
let mut cursor = [0usize; MAX_MOVING_AXES];
let index = &mut cursor[..rank];
let mut origins = [0usize; MAX_MOVING_AXES];
let origin = &mut origins[..rank];
let mut dst_tile = dst_base;
let mut src_tile = src_base;
loop {
#[cfg(test)]
crate::threading::record_tile_box();
let mut count = 1usize;
for axis in 0..rank {
let dim = tiles.blocks[axis].min(box_dims[axis] - origin[axis]);
tile[axis].dim = dim;
count *= dim;
}
unsafe {
apply_spilled_range_with(
dst_ptr, dst_tile, src_ptr, src_tile, tile, 0, count, index, apply,
);
}
let mut axis = 0;
loop {
if axis == rank {
return;
}
let next = origin[axis] + tiles.blocks[axis];
if next < box_dims[axis] {
origin[axis] = next;
dst_tile += tiles.blocks[axis] as isize * tiles.dst[axis];
src_tile += tiles.blocks[axis] as isize * tiles.src[axis];
break;
}
dst_tile -= origin[axis] as isize * tiles.dst[axis];
src_tile -= origin[axis] as isize * tiles.src[axis];
origin[axis] = 0;
axis += 1;
}
}
}
pub(crate) fn apply_fused_pair<D, S, Apply>(
dst: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
layout: &FusedPairLayout,
mut apply: Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
let total = fused_total(layout);
if total == 0 {
return;
}
let src_ptr = src.data().as_ptr();
let src_base = src.offset();
let dst_base = dst.offset();
let dst_ptr = dst.data_mut().as_mut_ptr();
unsafe {
apply_fused_range(
dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &mut apply,
);
}
}
#[inline(never)]
pub(crate) fn apply_spilled_pair<D, S, Apply>(
dst: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
axes: &[FusedAxis],
mut apply: Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
let total = spilled_total(axes);
if total == 0 {
return;
}
let src_ptr = src.data().as_ptr();
let src_base = src.offset();
let dst_base = dst.offset();
let dst_ptr = dst.data_mut().as_mut_ptr();
unsafe {
apply_spilled_range(
dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &mut apply,
);
}
}
pub(crate) unsafe fn replay_route_serial<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
route: Route<'_>,
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
unsafe {
match route {
Route::Inline {
layout,
tiles: None,
} => apply_fused_range(
dst_ptr,
dst_base,
src_ptr,
src_base,
layout,
0,
fused_total(layout),
apply,
),
Route::Inline {
tiles: Some(tiles), ..
} => apply_tiled_box(
dst_ptr,
dst_base,
src_ptr,
src_base,
&tiles.layout,
&tiles.blocks,
apply,
),
Route::Spilled { axes, tiles: None } => apply_spilled_range(
dst_ptr,
dst_base,
src_ptr,
src_base,
axes,
0,
spilled_total(axes),
apply,
),
Route::Spilled {
tiles: Some(tiles), ..
} => apply_spilled_tiled_box(
dst_ptr,
dst_base,
src_ptr,
src_base,
tiles,
tiles.dims(),
apply,
),
}
}
}
#[allow(clippy::too_many_arguments)]
pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
layout: &FusedPairLayout,
start: usize,
len: usize,
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
if len == 0 {
return;
}
let rank = layout.rank;
let inner_len = layout.dims[0];
let inner_dst = layout.dst_strides[0];
let inner_src = layout.src_strides[0];
let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
let mut rest = start;
let mut dst_outer = dst_base;
let mut src_outer = src_base;
#[allow(clippy::needless_range_loop)]
for axis in 0..rank {
let dim = layout.dims[axis];
index[axis] = rest % dim;
rest /= dim;
if axis > 0 {
dst_outer += index[axis] as isize * layout.dst_strides[axis];
src_outer += index[axis] as isize * layout.src_strides[axis];
}
}
let mut inner_start = index[0];
let mut remaining = len;
loop {
let run = (inner_len - inner_start).min(remaining);
let dst_run = dst_outer + inner_start as isize * inner_dst;
let src_run = src_outer + inner_start as isize * inner_src;
unsafe {
apply_run(
dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
)
};
remaining -= run;
if remaining == 0 {
return;
}
inner_start = 0;
let mut axis = 1;
while axis < rank {
if index[axis] + 1 < layout.dims[axis] {
index[axis] += 1;
dst_outer += layout.dst_strides[axis];
src_outer += layout.src_strides[axis];
break;
}
let last = (layout.dims[axis] - 1) as isize;
dst_outer -= last * layout.dst_strides[axis];
src_outer -= last * layout.src_strides[axis];
index[axis] = 0;
axis += 1;
}
}
}
#[allow(clippy::too_many_arguments)]
#[inline(never)]
pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
axes: &[FusedAxis],
start: usize,
len: usize,
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
if len == 0 {
return;
}
let mut cursor = [0usize; MAX_MOVING_AXES];
let index = &mut cursor[..axes.len()];
unsafe {
apply_spilled_range_with(
dst_ptr, dst_base, src_ptr, src_base, axes, start, len, index, apply,
)
}
}
#[allow(clippy::too_many_arguments)]
unsafe fn apply_spilled_range_with<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
axes: &[FusedAxis],
start: usize,
len: usize,
index: &mut [usize],
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
if len == 0 {
return;
}
let rank = axes.len();
debug_assert!(index.len() >= rank);
let inner_len = axes[0].dim;
let inner_dst = axes[0].dst;
let inner_src = axes[0].src;
let mut rest = start;
let mut dst_outer = dst_base;
let mut src_outer = src_base;
for axis in 0..rank {
let dim = axes[axis].dim;
index[axis] = rest % dim;
rest /= dim;
if axis > 0 {
dst_outer += index[axis] as isize * axes[axis].dst;
src_outer += index[axis] as isize * axes[axis].src;
}
}
let mut inner_start = index[0];
let mut remaining = len;
loop {
let run = (inner_len - inner_start).min(remaining);
let dst_run = dst_outer + inner_start as isize * inner_dst;
let src_run = src_outer + inner_start as isize * inner_src;
unsafe {
apply_run(
dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
)
};
remaining -= run;
if remaining == 0 {
return;
}
inner_start = 0;
let mut axis = 1;
while axis < rank {
if index[axis] + 1 < axes[axis].dim {
index[axis] += 1;
dst_outer += axes[axis].dst;
src_outer += axes[axis].src;
break;
}
let last = (axes[axis].dim - 1) as isize;
dst_outer -= last * axes[axis].dst;
src_outer -= last * axes[axis].src;
index[axis] = 0;
axis += 1;
}
}
}
#[allow(clippy::too_many_arguments)]
#[inline(always)]
unsafe fn apply_run<D, S, Apply>(
dst_ptr: *mut D,
dst_offset: isize,
dst_stride: isize,
src_ptr: *const S,
src_offset: isize,
src_stride: isize,
len: usize,
apply: &mut Apply,
) where
D: Copy,
S: Copy,
Apply: FnMut(&mut D, S),
{
if dst_stride == 1 {
let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
if src_stride == 1 {
let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
for (dst, &value) in dst_run.iter_mut().zip(src_run) {
apply(dst, value);
}
return;
}
if src_stride == -1 {
let last = (len - 1) as isize;
let src_run =
unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
apply(dst, value);
}
return;
}
let src_start = unsafe { src_ptr.offset(src_offset) };
for (position, dst) in dst_run.iter_mut().enumerate() {
let value = unsafe { *src_start.offset(position as isize * src_stride) };
apply(dst, value);
}
return;
}
let dst_start = unsafe { dst_ptr.offset(dst_offset) };
let src_start = unsafe { src_ptr.offset(src_offset) };
for position in 0..len {
let position = position as isize;
unsafe {
let value = *src_start.offset(position * src_stride);
apply(&mut *dst_start.offset(position * dst_stride), value);
}
}
}
fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
if dst != src {
return Err(crate::StridedError::ShapeMismatch(
dst.to_vec(),
src.to_vec(),
));
}
crate::kernel::total_len(dst)?;
Ok(())
}
pub fn copy_scale_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
scale: T,
) -> Result<()>
where
T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = scale * value
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = scale * value
})
}
}
Ok(())
}
pub fn copy_scale_conj_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
scale: T,
) -> Result<()>
where
T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = scale * value.conj()
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = scale * value.conj()
})
}
}
Ok(())
}
pub fn axpy_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
alpha: T,
) -> Result<()>
where
T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = *dst + alpha * value
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = *dst + alpha * value
})
}
}
Ok(())
}
pub fn axpy_conj_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
alpha: T,
) -> Result<()>
where
T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = *dst + alpha * value.conj()
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = *dst + alpha * value.conj()
})
}
}
Ok(())
}
fn with_checked_route<D, S>(
dims: &[usize],
dst_strides: &[isize],
src_dims: &[usize],
src_strides: &[isize],
f: impl FnOnce(Route<'_>, usize, Option<bool>),
) -> Result<()> {
ensure_same_dims(dims, src_dims)?;
let total = crate::kernel::total_len(dims)?;
if total == 0 {
return Ok(());
}
with_given_route::<D, S, _>(dims, dst_strides, src_strides, |route| {
let mut route = route;
let mut proven = None;
if route.is_tiled() {
let holds = crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
proven = Some(holds);
if !holds {
route = route.untiled();
}
}
f(route, total, proven)
});
Ok(())
}
fn replay_given<D, S, Apply>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
apply: Apply,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
Apply: Fn(&mut D, S) + Sync,
{
let (dims, dst_strides) = (dest.dims(), dest.strides());
let injective = || crate::layout_check::is_injective_layout_without_alloc(dims, dst_strides);
with_checked_route::<D, S>(
dims,
dst_strides,
src.dims(),
src.strides(),
|route, total, proven| {
let exec = if route.is_tiled() {
exec
} else {
let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
if !exec.is_serial() && !proven.unwrap_or_else(injective) {
exec.limit(NonZeroUsize::MIN)
} else {
exec
}
};
unsafe {
crate::copy_plan::replay_fused(
dest,
src,
route,
apply,
KernelClass::Copy.ns_per_element(),
exec,
)
};
},
)
}
pub fn replay_copy_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Send + Sync,
{
replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
}
pub fn replay_copy_raw_uninit<T>(
dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
src: &RawStridedRef<'_, T>,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Send + Sync,
{
replay_given(
dest,
src,
|dst: &mut MaybeUninit<T>, value: T| {
dst.write(value);
},
exec,
)
}
pub fn replay_map_raw<D, S, F>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(&mut D, S) + Send + Sync,
{
replay_given(dest, src, f, exec)
}
pub fn replay_map_raw_serial<D, S, F>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
mut f: F,
) -> Result<()>
where
D: Copy,
S: Copy,
F: FnMut(&mut D, S),
{
let (dims, dst_strides) = (dest.dims(), dest.strides());
with_checked_route::<D, S>(
dims,
dst_strides,
src.dims(),
src.strides(),
|route, _, _| {
let src_ptr = src.data().as_ptr();
let src_base = src.offset();
let dst_base = dest.offset();
let dst_ptr = dest.data_mut().as_mut_ptr();
unsafe { replay_route_serial(dst_ptr, dst_base, src_ptr, src_base, route, &mut f) };
},
)
}
pub fn replay_map_raw_uninit<D, S, F>(
dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(S) -> D + Send + Sync,
{
replay_given(
dest,
src,
move |dst: &mut MaybeUninit<D>, value: S| {
dst.write(f(value));
},
exec,
)
}
pub fn replay_map_raw_fused<D, S, F>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(&mut D, S) + Send + Sync,
{
replay_fused_given(dest, src, f, exec)
}
pub fn replay_map_raw_uninit_fused<D, S, F>(
dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(S) -> D + Send + Sync,
{
replay_fused_given(
dest,
src,
move |dst: &mut MaybeUninit<D>, value: S| {
dst.write(f(value));
},
exec,
)
}
fn replay_fused_given<D, S, Apply>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
apply: Apply,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
Apply: Fn(&mut D, S) + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
if crate::kernel::total_len(dest.dims())? == 0 {
return Ok(());
}
let mut dims = [1usize; MAX_MOVING_AXES];
let mut dst_strides = [0isize; MAX_MOVING_AXES];
let mut src_strides = [0isize; MAX_MOVING_AXES];
let mut moving = 0;
for ((&dim, &dst), &src_stride) in dest.dims().iter().zip(dest.strides()).zip(src.strides()) {
if dim == 1 {
continue;
}
dims[moving] = dim;
dst_strides[moving] = dst;
src_strides[moving] = src_stride;
moving += 1;
}
let mut fused = [EMPTY_AXIS; MAX_MOVING_AXES];
let rank = fuse_axes(
&mut fused[..moving.max(1)],
&dims[..moving],
&dst_strides[..moving],
&src_strides[..moving],
);
let mut fused_dims = [1usize; MAX_MOVING_AXES];
let mut fused_dst = [0isize; MAX_MOVING_AXES];
let mut fused_src = [0isize; MAX_MOVING_AXES];
for (slot, axis) in fused[..rank].iter().enumerate() {
fused_dims[slot] = axis.dim;
fused_dst[slot] = axis.dst;
fused_src[slot] = axis.src;
}
let dst_offset = dest.offset();
let src_offset = src.offset();
let mut dest = unsafe {
RawStridedMut::new_unchecked(
dest.data_mut(),
&fused_dims[..rank],
&fused_dst[..rank],
dst_offset,
)
};
let src = unsafe {
RawStridedRef::new_unchecked(
src.data(),
&fused_dims[..rank],
&fused_src[..rank],
src_offset,
)
};
replay_given(&mut dest, &src, apply, exec)
}
#[cfg(test)]
#[path = "raw_ops/tests/tests.rs"]
mod tests;
#[cfg(test)]
#[path = "raw_ops/tests/replay_tests.rs"]
mod replay_tests;
#[cfg(test)]
#[path = "raw_ops/tests/tiled_tests.rs"]
mod tiled_tests;