use crate::inline::{InlineVec, OperandVec};
pub fn fuse_dims(dims: &[usize], all_strides: &[&[isize]]) -> InlineVec<usize> {
let n = dims.len();
if n <= 1 || all_strides.is_empty() {
return dims.iter().copied().collect();
}
let mut result: InlineVec<usize> = dims.iter().copied().collect();
for i in (1..n).rev() {
let mut can_merge = true;
for strides in all_strides {
if strides[i - 1] == 0 && strides[i] == 0 {
continue;
}
let expected = isize::try_from(result[i - 1])
.ok()
.and_then(|dim| dim.checked_mul(strides[i - 1]));
if expected != Some(strides[i]) {
can_merge = false;
break;
}
}
if can_merge {
if let Some(merged) = result[i - 1].checked_mul(result[i]) {
result[i - 1] = merged;
result[i] = 1;
}
}
}
result
}
pub fn compress_dims<S: AsRef<[isize]>>(
dims: &[usize],
all_strides: &[S],
) -> (InlineVec<usize>, OperandVec<InlineVec<isize>>) {
let kept: InlineVec<usize> = (0..dims.len()).filter(|&i| dims[i] != 1).collect();
if kept.is_empty() {
if dims.is_empty() {
let strides = all_strides
.iter()
.map(|s| s.as_ref().iter().copied().collect())
.collect();
return (InlineVec::new(), strides);
}
let new_strides = all_strides
.iter()
.map(|s| {
let mut v = InlineVec::new();
v.push(s.as_ref()[0]);
v
})
.collect();
let mut dims_out = InlineVec::new();
dims_out.push(1);
return (dims_out, new_strides);
}
let new_dims: InlineVec<usize> = kept.iter().map(|&i| dims[i]).collect();
let new_strides: OperandVec<InlineVec<isize>> = all_strides
.iter()
.map(|s| kept.iter().map(|&i| s.as_ref()[i]).collect())
.collect();
(new_dims, new_strides)
}
pub fn compute_importance<I: AsRef<[usize]>>(
dims: &[usize],
all_strides: &[&[isize]],
index_orders: &[I],
) -> InlineVec<u64> {
let n = dims.len();
let m = all_strides.len();
if n == 0 || m == 0 {
return InlineVec::new();
}
let g = (64 - (m as u64 + 1).leading_zeros()) as u64;
let weights = |bits: u64, level_cap: u64| -> Option<InlineVec<u64>> {
let term = |k: usize, i: usize| -> Option<u64> {
let level = (n - index_orders[k].as_ref()[i]) as u64;
let shift = level.min(level_cap).checked_mul(bits)?;
1u64.checked_shl(u32::try_from(shift).ok()?)
};
let output_weight = 1u64.checked_shl((bits + 1) as u32)?;
let mut weights: InlineVec<u64> = (0..n).map(|_| 0u64).collect();
for i in 0..n {
if dims[i] <= 1 {
continue;
}
if all_strides[0][i] != 0 {
weights[i] = term(0, i)?.checked_mul(output_weight)?;
}
for (k, strides) in all_strides.iter().enumerate().skip(1) {
if strides[i] != 0 {
weights[i] = weights[i].checked_add(term(k, i)?)?;
}
}
}
Some(weights)
};
let mut bits = g;
let mut packed = weights(bits, u64::MAX);
while packed.is_none() && bits > 1 {
bits -= 1;
packed = weights(bits, u64::MAX);
}
packed
.or_else(|| {
(1..=63u64)
.rev()
.find_map(|level_cap| weights(1, level_cap))
})
.unwrap_or_else(|| (0..n).map(|_| 0u64).collect())
}
pub fn sort_by_importance(importance: &[u64]) -> InlineVec<usize> {
let mut indices: InlineVec<usize> = (0..importance.len()).collect();
indices.sort_by(|&a, &b| importance[b].cmp(&importance[a]));
indices
}
pub(crate) fn compute_costs<S: AsRef<[isize]>>(all_strides: &[S]) -> InlineVec<isize> {
let Some(first) = all_strides.first() else {
return InlineVec::new();
};
let n = first.as_ref().len();
if n <= strided_view::INLINE_RANK {
let mut costs = [0isize; strided_view::INLINE_RANK];
compute_costs_into(all_strides, &mut costs[..n]);
return InlineVec::from_array_len(costs, n);
}
let mut costs = vec![0isize; n];
compute_costs_into(all_strides, &mut costs);
InlineVec::Heap(costs)
}
pub(crate) fn compute_costs_into<S: AsRef<[isize]>>(all_strides: &[S], costs: &mut [isize]) {
for (axis, slot) in costs.iter_mut().enumerate() {
let min = all_strides
.iter()
.map(|strides| strides.as_ref()[axis].checked_abs().unwrap_or(isize::MAX))
.min()
.unwrap_or(isize::MAX);
*slot = if min == 0 { 1 } else { min.saturating_mul(2) };
}
}
#[cfg(test)]
#[path = "fuse/tests/tests.rs"]
mod tests;