use std::sync::Arc;
use vyre::execution_plan::fusion::fuse_programs;
use vyre::ir::model::expr::{GeneratorRef, Ident};
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_libs::region::{tag_program, wrap_anonymous};
use vyre_primitives::reduce::multi_block_prefix_scan::multi_block_prefix_scan_sum_exclusive_u32;
use vyre_primitives::reduce::scatter::scatter;
use vyre_primitives::reduce::workgroup_tree::{min_u32_child, WorkgroupReductionScope};
use crate::{trap_program, Rank, TokenId};
pub const ARGMIN_OP_ID: &str = "exatok::gpu_select::segmented_argmin_leftmost";
pub const COMPACT_OP_ID: &str = "exatok::gpu_select::compact_removed";
pub const REMAP_OP_ID: &str = "exatok::gpu_select::remap_segment_starts";
pub const APPLY_ARGMIN_OP_ID: &str = "exatok::gpu_select::apply_argmin_merges";
#[cfg(feature = "multi-merge")]
pub const SELECT_OP_ID: &str = "exatok::gpu_select::select_non_overlapping";
#[cfg(feature = "multi-merge")]
pub const APPLY_MERGES_OP_ID: &str = "exatok::gpu_select::apply_merges";
pub const ARGMIN_WORDS_PER_SEGMENT: u32 = 2;
pub const ARGMIN_INDEX_SLOT: u32 = 0;
pub const ARGMIN_RANK_SLOT: u32 = 1;
pub const NO_MERGE_INDEX: u32 = u32::MAX;
pub const SEGMENT_LANES: u32 = 32;
const FLAT_LANES: u32 = 256;
const RANK_SCRATCH: &str = "__exatok_argmin_rank_scratch";
const INDEX_SCRATCH: &str = "__exatok_argmin_index_scratch";
pub const MAX_ELEMENTS: u32 = u32::MAX - 1;
#[must_use]
pub fn segmented_argmin_leftmost(
ranks: &str,
segment_starts: &str,
out: &str,
num_segments: u32,
) -> Program {
if num_segments > MAX_ELEMENTS / ARGMIN_WORDS_PER_SEGMENT {
return trap_program(
ARGMIN_OP_ID,
out,
DataType::U32,
format!(
"segmented_argmin_leftmost requires num_segments <= {}, got {num_segments}. \
Fix: shard the segment table; the output buffer is two words per segment.",
MAX_ELEMENTS / ARGMIN_WORDS_PER_SEGMENT
),
);
}
if num_segments == 0 {
return no_merge_program(ARGMIN_OP_ID, out);
}
let lane = || Expr::var("local");
let segment = || Expr::var("segment");
let in_range = || Expr::lt(segment(), Expr::u32(num_segments));
let bounds = || {
vec![
Node::let_bind("begin", Expr::load(segment_starts, segment())),
Node::let_bind(
"end",
Expr::load(segment_starts, Expr::add(segment(), Expr::u32(1))),
),
Node::let_bind(
"rounds",
Expr::div(
Expr::add(
Expr::sub(Expr::var("end"), Expr::var("begin")),
Expr::u32(SEGMENT_LANES - 1),
),
Expr::u32(SEGMENT_LANES),
),
),
]
};
let strided_index = || {
Node::let_bind(
"element",
Expr::add(
Expr::var("begin"),
Expr::add(
Expr::mul(Expr::var("round"), Expr::u32(SEGMENT_LANES)),
lane(),
),
),
)
};
let element_in_segment = || Expr::lt(Expr::var("element"), Expr::var("end"));
let mut phase_one = bounds();
phase_one.extend([
Node::let_bind("rank_acc", Expr::u32(Rank::ABSENT.0)),
Node::loop_for(
"round",
Expr::u32(0),
Expr::var("rounds"),
vec![
strided_index(),
Node::if_then(
element_in_segment(),
vec![Node::assign(
"rank_acc",
Expr::min(
Expr::var("rank_acc"),
Expr::load(ranks, Expr::var("element")),
),
)],
),
],
),
Node::store(RANK_SCRATCH, lane(), Expr::var("rank_acc")),
]);
let mut phase_two = bounds();
phase_two.extend([
Node::let_bind("min_rank", Expr::load(RANK_SCRATCH, Expr::u32(0))),
Node::let_bind("index_acc", Expr::u32(NO_MERGE_INDEX)),
Node::if_then(
Expr::ne(Expr::var("min_rank"), Expr::u32(Rank::ABSENT.0)),
vec![Node::loop_for(
"round",
Expr::u32(0),
Expr::var("rounds"),
vec![
strided_index(),
Node::if_then(
element_in_segment(),
vec![Node::if_then(
Expr::eq(
Expr::load(ranks, Expr::var("element")),
Expr::var("min_rank"),
),
vec![Node::assign(
"index_acc",
Expr::min(Expr::var("index_acc"), Expr::var("element")),
)],
)],
),
],
)],
),
Node::store(INDEX_SCRATCH, lane(), Expr::var("index_acc")),
]);
let out_base = || Expr::mul(segment(), Expr::u32(ARGMIN_WORDS_PER_SEGMENT));
let body = vec![
Node::let_bind("local", Expr::LocalId { axis: 0 }),
Node::let_bind("segment", Expr::WorkgroupId { axis: 0 }),
Node::store(RANK_SCRATCH, lane(), Expr::u32(Rank::ABSENT.0)),
Node::store(INDEX_SCRATCH, lane(), Expr::u32(NO_MERGE_INDEX)),
Node::if_then(in_range(), phase_one),
Node::barrier(),
min_u32_child(
ARGMIN_OP_ID,
SEGMENT_LANES,
RANK_SCRATCH,
WorkgroupReductionScope::EveryWorkgroup,
),
Node::if_then(in_range(), phase_two),
Node::barrier(),
min_u32_child(
ARGMIN_OP_ID,
SEGMENT_LANES,
INDEX_SCRATCH,
WorkgroupReductionScope::EveryWorkgroup,
),
Node::if_then(
Expr::and(in_range(), Expr::eq(lane(), Expr::u32(0))),
vec![
Node::store(
out,
Expr::add(out_base(), Expr::u32(ARGMIN_INDEX_SLOT)),
Expr::load(INDEX_SCRATCH, Expr::u32(0)),
),
Node::store(
out,
Expr::add(out_base(), Expr::u32(ARGMIN_RANK_SLOT)),
Expr::load(RANK_SCRATCH, Expr::u32(0)),
),
],
),
];
Program::wrapped(
vec![
BufferDecl::storage(ranks, 0, BufferAccess::ReadOnly, DataType::U32),
BufferDecl::storage(segment_starts, 1, BufferAccess::ReadOnly, DataType::U32)
.with_count(num_segments + 1),
BufferDecl::workgroup(RANK_SCRATCH, SEGMENT_LANES, DataType::U32),
BufferDecl::workgroup(INDEX_SCRATCH, SEGMENT_LANES, DataType::U32),
BufferDecl::output(out, 2, DataType::U32)
.with_count(num_segments * ARGMIN_WORDS_PER_SEGMENT),
],
[SEGMENT_LANES, 1, 1],
vec![wrap_anonymous(ARGMIN_OP_ID, body)],
)
}
fn no_merge_program(op_id: &str, out: &str) -> Program {
let body = vec![Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![
Node::store(out, Expr::u32(ARGMIN_INDEX_SLOT), Expr::u32(NO_MERGE_INDEX)),
Node::store(out, Expr::u32(ARGMIN_RANK_SLOT), Expr::u32(Rank::ABSENT.0)),
],
)];
Program::wrapped(
vec![BufferDecl::output(out, 0, DataType::U32).with_count(ARGMIN_WORDS_PER_SEGMENT)],
[1, 1, 1],
vec![wrap_anonymous(op_id, body)],
)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CompactScratch {
pub keep: String,
pub offsets: String,
pub slots: String,
}
impl CompactScratch {
#[must_use]
pub fn for_output(compacted: &str) -> Self {
Self {
keep: format!("__{compacted}_wt_keep"),
offsets: format!("__{compacted}_wt_offsets"),
slots: format!("__{compacted}_wt_slots"),
}
}
}
#[must_use]
pub fn compact_removed(
values: &str,
removed: &str,
compacted: &str,
live_count: &str,
n: u32,
) -> Program {
let scratch = CompactScratch::for_output(compacted);
compact_removed_with_scratch(values, removed, compacted, live_count, &scratch, n)
}
#[must_use]
pub fn compact_removed_with_scratch(
values: &str,
removed: &str,
compacted: &str,
live_count: &str,
scratch: &CompactScratch,
n: u32,
) -> Program {
if n > MAX_ELEMENTS {
return trap_program(
COMPACT_OP_ID,
compacted,
DataType::U32,
format!(
"compact_removed requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the array; \
n == u32::MAX leaves no out-of-range slot to suppress a dropped element's scatter."
),
);
}
if n == 0 {
return empty_count_program(COMPACT_OP_ID, live_count);
}
let flags = flat_program(
COMPACT_OP_ID,
vec![
BufferDecl::storage(removed, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(&scratch.keep, 1, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
],
n,
vec![Node::if_then_else(
Expr::eq(Expr::load(removed, Expr::gid_x()), Expr::u32(0)),
vec![Node::store(&scratch.keep, Expr::gid_x(), Expr::u32(1))],
vec![Node::store(&scratch.keep, Expr::gid_x(), Expr::u32(0))],
)],
);
let offsets_scan = composed(
COMPACT_OP_ID,
multi_block_prefix_scan_sum_exclusive_u32(&scratch.keep, &scratch.offsets, n),
);
let slots = flat_program(
COMPACT_OP_ID,
vec![
BufferDecl::storage(&scratch.keep, 0, BufferAccess::ReadOnly, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.offsets, 1, BufferAccess::ReadOnly, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.slots, 2, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
BufferDecl::storage(live_count, 3, BufferAccess::ReadWrite, DataType::U32)
.with_count(1),
],
n,
vec![
Node::let_bind("keep_flag", Expr::load(&scratch.keep, Expr::gid_x())),
Node::let_bind("offset", Expr::load(&scratch.offsets, Expr::gid_x())),
Node::if_then_else(
Expr::ne(Expr::var("keep_flag"), Expr::u32(0)),
vec![Node::store(
&scratch.slots,
Expr::gid_x(),
Expr::var("offset"),
)],
vec![Node::store(&scratch.slots, Expr::gid_x(), Expr::u32(n))],
),
Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(n - 1)),
vec![Node::store(
live_count,
Expr::u32(0),
Expr::add(Expr::var("offset"), Expr::var("keep_flag")),
)],
),
],
);
let move_survivors = composed(COMPACT_OP_ID, scatter(values, &scratch.slots, compacted, n));
fuse_or_trap(
COMPACT_OP_ID,
compacted,
&[flags, offsets_scan, slots, move_survivors],
)
}
#[must_use]
pub fn remap_segment_starts(
segment_starts: &str,
offsets: &str,
live_count: &str,
new_starts: &str,
num_segments: u32,
n: u32,
) -> Program {
if n > MAX_ELEMENTS {
return trap_program(
REMAP_OP_ID,
new_starts,
DataType::U32,
format!(
"remap_segment_starts requires n <= {MAX_ELEMENTS}, got {n}. \
Fix: shard the token array before compacting."
),
);
}
let table_words = num_segments.saturating_add(1);
let body = vec![
Node::if_then(
Expr::lt(Expr::gid_x(), Expr::u32(num_segments)),
vec![Node::store(
new_starts,
Expr::gid_x(),
Expr::load(offsets, Expr::load(segment_starts, Expr::gid_x())),
)],
),
Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(num_segments)),
vec![Node::store(
new_starts,
Expr::gid_x(),
Expr::load(live_count, Expr::u32(0)),
)],
),
];
Program::wrapped(
vec![
BufferDecl::storage(segment_starts, 0, BufferAccess::ReadOnly, DataType::U32)
.with_count(table_words),
BufferDecl::storage(offsets, 1, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(live_count, 2, BufferAccess::ReadOnly, DataType::U32).with_count(1),
BufferDecl::storage(new_starts, 3, BufferAccess::ReadWrite, DataType::U32)
.with_count(table_words),
],
[FLAT_LANES, 1, 1],
vec![wrap_anonymous(
REMAP_OP_ID,
vec![Node::if_then(
Expr::lt(Expr::gid_x(), Expr::u32(table_words)),
body,
)],
)],
)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ApplyArgminScratch {
pub staged: String,
pub removed: String,
pub compact: CompactScratch,
}
impl ApplyArgminScratch {
#[must_use]
pub fn for_output(out_tokens: &str) -> Self {
Self {
staged: format!("__{out_tokens}_wt_staged"),
removed: format!("__{out_tokens}_wt_removed"),
compact: CompactScratch::for_output(out_tokens),
}
}
}
#[must_use]
pub fn apply_argmin_merges(
tokens: &str,
merged_ids: &str,
argmin_out: &str,
out_tokens: &str,
out_len: &str,
num_segments: u32,
n: u32,
) -> Program {
let scratch = ApplyArgminScratch::for_output(out_tokens);
apply_argmin_merges_with_scratch(
tokens,
merged_ids,
argmin_out,
out_tokens,
out_len,
&scratch,
num_segments,
n,
)
}
#[must_use]
#[allow(clippy::too_many_arguments)]
pub fn apply_argmin_merges_with_scratch(
tokens: &str,
merged_ids: &str,
argmin_out: &str,
out_tokens: &str,
out_len: &str,
scratch: &ApplyArgminScratch,
num_segments: u32,
n: u32,
) -> Program {
if n > MAX_ELEMENTS {
return trap_program(
APPLY_ARGMIN_OP_ID,
out_tokens,
DataType::U32,
format!(
"apply_argmin_merges requires n <= {MAX_ELEMENTS}, got {n}. \
Fix: shard the token array; the compaction it composes cannot address u32::MAX."
),
);
}
if n == 0 || num_segments == 0 {
return empty_count_program(APPLY_ARGMIN_OP_ID, out_len);
}
let reset = flat_program(
APPLY_ARGMIN_OP_ID,
vec![
BufferDecl::storage(tokens, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(&scratch.staged, 1, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.removed, 2, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
],
n,
vec![
Node::store(
&scratch.staged,
Expr::gid_x(),
Expr::load(tokens, Expr::gid_x()),
),
Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0)),
],
);
let apply = flat_program(
APPLY_ARGMIN_OP_ID,
vec![
BufferDecl::storage(merged_ids, 0, BufferAccess::ReadOnly, DataType::U32)
.with_count(n),
BufferDecl::storage(argmin_out, 1, BufferAccess::ReadOnly, DataType::U32)
.with_count(num_segments * ARGMIN_WORDS_PER_SEGMENT),
BufferDecl::storage(&scratch.staged, 2, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.removed, 3, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
],
num_segments,
vec![
Node::let_bind(
"merge_at",
Expr::load(
argmin_out,
Expr::add(
Expr::mul(Expr::gid_x(), Expr::u32(ARGMIN_WORDS_PER_SEGMENT)),
Expr::u32(ARGMIN_INDEX_SLOT),
),
),
),
Node::if_then(
Expr::ne(Expr::var("merge_at"), Expr::u32(NO_MERGE_INDEX)),
vec![
Node::store(
&scratch.staged,
Expr::var("merge_at"),
Expr::load(merged_ids, Expr::var("merge_at")),
),
Node::store(
&scratch.removed,
Expr::add(Expr::var("merge_at"), Expr::u32(1)),
Expr::u32(1),
),
],
),
],
);
let compact = compact_removed_with_scratch(
&scratch.staged,
&scratch.removed,
out_tokens,
out_len,
&scratch.compact,
n,
);
fuse_or_trap(APPLY_ARGMIN_OP_ID, out_tokens, &[reset, apply, compact])
}
#[cfg(feature = "multi-merge")]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SelectScratch {
pub matches: String,
pub run_starts: String,
pub run_offsets: String,
pub run_start_index: String,
}
#[cfg(feature = "multi-merge")]
impl SelectScratch {
#[must_use]
pub fn for_output(selected: &str) -> Self {
Self {
matches: format!("__{selected}_wt_matches"),
run_starts: format!("__{selected}_wt_run_starts"),
run_offsets: format!("__{selected}_wt_run_offsets"),
run_start_index: format!("__{selected}_wt_run_start_index"),
}
}
}
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn select_non_overlapping(
ranks: &str,
target: &str,
target_slot: u32,
selected: &str,
n: u32,
) -> Program {
let scratch = SelectScratch::for_output(selected);
select_non_overlapping_with_scratch(ranks, target, target_slot, selected, &scratch, n)
}
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn select_non_overlapping_with_scratch(
ranks: &str,
target: &str,
target_slot: u32,
selected: &str,
scratch: &SelectScratch,
n: u32,
) -> Program {
if n > MAX_ELEMENTS {
return trap_program(
SELECT_OP_ID,
selected,
DataType::U32,
format!(
"select_non_overlapping requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the rank \
array; n == u32::MAX leaves no out-of-range slot to suppress a non-start lane's \
scatter."
),
);
}
if n == 0 {
return empty_flag_program(SELECT_OP_ID, selected);
}
let target_word = || Expr::load(target, Expr::u32(target_slot));
let is_match = || {
Expr::and(
Expr::ne(target_word(), Expr::u32(Rank::ABSENT.0)),
Expr::eq(Expr::load(ranks, Expr::gid_x()), target_word()),
)
};
let previous_matches = || {
Expr::eq(
Expr::load(ranks, Expr::sub(Expr::gid_x(), Expr::u32(1))),
target_word(),
)
};
let flags = flat_program(
SELECT_OP_ID,
vec![
BufferDecl::storage(ranks, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(target, 1, BufferAccess::ReadOnly, DataType::U32)
.with_count(target_slot + 1),
BufferDecl::storage(&scratch.matches, 2, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
BufferDecl::storage(
&scratch.run_starts,
3,
BufferAccess::ReadWrite,
DataType::U32,
)
.with_count(n),
],
n,
vec![Node::if_then_else(
is_match(),
vec![
Node::store(&scratch.matches, Expr::gid_x(), Expr::u32(1)),
Node::if_then_else(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![Node::store(
&scratch.run_starts,
Expr::gid_x(),
Expr::u32(1),
)],
vec![Node::if_then_else(
previous_matches(),
vec![Node::store(
&scratch.run_starts,
Expr::gid_x(),
Expr::u32(0),
)],
vec![Node::store(
&scratch.run_starts,
Expr::gid_x(),
Expr::u32(1),
)],
)],
),
],
vec![
Node::store(&scratch.matches, Expr::gid_x(), Expr::u32(0)),
Node::store(&scratch.run_starts, Expr::gid_x(), Expr::u32(0)),
],
)],
);
let run_scan = composed(
SELECT_OP_ID,
multi_block_prefix_scan_sum_exclusive_u32(&scratch.run_starts, &scratch.run_offsets, n),
);
let run_table = flat_program(
SELECT_OP_ID,
vec![
BufferDecl::storage(
&scratch.run_starts,
0,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(n),
BufferDecl::storage(
&scratch.run_offsets,
1,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(n),
BufferDecl::storage(
&scratch.run_start_index,
2,
BufferAccess::ReadWrite,
DataType::U32,
)
.with_count(n),
],
n,
vec![Node::if_then(
Expr::ne(Expr::load(&scratch.run_starts, Expr::gid_x()), Expr::u32(0)),
vec![Node::store(
&scratch.run_start_index,
Expr::load(&scratch.run_offsets, Expr::gid_x()),
Expr::gid_x(),
)],
)],
);
let parity = flat_program(
SELECT_OP_ID,
vec![
BufferDecl::storage(&scratch.matches, 0, BufferAccess::ReadOnly, DataType::U32)
.with_count(n),
BufferDecl::storage(
&scratch.run_starts,
1,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(n),
BufferDecl::storage(
&scratch.run_offsets,
2,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(n),
BufferDecl::storage(
&scratch.run_start_index,
3,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(n),
BufferDecl::storage(selected, 4, BufferAccess::ReadWrite, DataType::U32).with_count(n),
],
n,
vec![Node::if_then_else(
Expr::ne(Expr::load(&scratch.matches, Expr::gid_x()), Expr::u32(0)),
vec![
Node::let_bind(
"run",
Expr::sub(
Expr::add(
Expr::load(&scratch.run_offsets, Expr::gid_x()),
Expr::load(&scratch.run_starts, Expr::gid_x()),
),
Expr::u32(1),
),
),
Node::let_bind(
"run_start",
Expr::load(&scratch.run_start_index, Expr::var("run")),
),
Node::if_then_else(
Expr::eq(
Expr::bitand(
Expr::sub(Expr::gid_x(), Expr::var("run_start")),
Expr::u32(1),
),
Expr::u32(0),
),
vec![Node::store(selected, Expr::gid_x(), Expr::u32(1))],
vec![Node::store(selected, Expr::gid_x(), Expr::u32(0))],
),
],
vec![Node::store(selected, Expr::gid_x(), Expr::u32(0))],
)],
);
fuse_or_trap(SELECT_OP_ID, selected, &[flags, run_scan, run_table, parity])
}
#[cfg(feature = "multi-merge")]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ApplyMergesScratch {
pub staged: String,
pub removed: String,
pub compact: CompactScratch,
}
#[cfg(feature = "multi-merge")]
impl ApplyMergesScratch {
#[must_use]
pub fn for_output(out_tokens: &str) -> Self {
Self {
staged: format!("__{out_tokens}_wt_multi_staged"),
removed: format!("__{out_tokens}_wt_multi_removed"),
compact: CompactScratch::for_output(out_tokens),
}
}
}
#[cfg(feature = "multi-merge")]
#[must_use]
pub fn apply_merges(
tokens: &str,
selected: &str,
merged_ids: &str,
out_tokens: &str,
out_len: &str,
n: u32,
) -> Program {
let scratch = ApplyMergesScratch::for_output(out_tokens);
apply_merges_with_scratch(
tokens,
selected,
merged_ids,
out_tokens,
out_len,
&scratch,
n,
)
}
#[cfg(feature = "multi-merge")]
#[must_use]
#[allow(clippy::too_many_arguments)]
pub fn apply_merges_with_scratch(
tokens: &str,
selected: &str,
merged_ids: &str,
out_tokens: &str,
out_len: &str,
scratch: &ApplyMergesScratch,
n: u32,
) -> Program {
if n > MAX_ELEMENTS {
return trap_program(
APPLY_MERGES_OP_ID,
out_tokens,
DataType::U32,
format!(
"apply_merges requires n <= {MAX_ELEMENTS}, got {n}. Fix: split the token array; \
the compaction it composes cannot address n == u32::MAX."
),
);
}
if n == 0 {
return empty_count_program(APPLY_MERGES_OP_ID, out_len);
}
let stage = flat_program(
APPLY_MERGES_OP_ID,
vec![
BufferDecl::storage(tokens, 0, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(selected, 1, BufferAccess::ReadOnly, DataType::U32).with_count(n),
BufferDecl::storage(merged_ids, 2, BufferAccess::ReadOnly, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.staged, 3, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
BufferDecl::storage(&scratch.removed, 4, BufferAccess::ReadWrite, DataType::U32)
.with_count(n),
],
n,
vec![
Node::if_then_else(
Expr::ne(Expr::load(selected, Expr::gid_x()), Expr::u32(0)),
vec![Node::store(
&scratch.staged,
Expr::gid_x(),
Expr::load(merged_ids, Expr::gid_x()),
)],
vec![Node::store(
&scratch.staged,
Expr::gid_x(),
Expr::load(tokens, Expr::gid_x()),
)],
),
Node::if_then_else(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0))],
vec![Node::if_then_else(
Expr::ne(
Expr::load(selected, Expr::sub(Expr::gid_x(), Expr::u32(1))),
Expr::u32(0),
),
vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(1))],
vec![Node::store(&scratch.removed, Expr::gid_x(), Expr::u32(0))],
)],
),
],
);
let compact = compact_removed_with_scratch(
&scratch.staged,
&scratch.removed,
out_tokens,
out_len,
&scratch.compact,
n,
);
fuse_or_trap(APPLY_MERGES_OP_ID, out_tokens, &[stage, compact])
}
fn flat_program(op_id: &str, buffers: Vec<BufferDecl>, count: u32, body: Vec<Node>) -> Program {
Program::wrapped(
buffers,
[FLAT_LANES, 1, 1],
vec![wrap_anonymous(
op_id,
vec![Node::if_then(
Expr::lt(Expr::gid_x(), Expr::u32(count)),
body,
)],
)],
)
}
fn composed(parent_op_id: &str, program: Program) -> Program {
attribute_regions(program, parent_op_id)
}
fn attribute_regions(program: Program, op_id: &str) -> Program {
let parent = GeneratorRef {
name: op_id.to_owned(),
};
program.map_entry(|entry| attribute_nodes(entry, &parent))
}
fn attribute_nodes(nodes: Vec<Node>, parent: &GeneratorRef) -> Vec<Node> {
nodes
.into_iter()
.map(|node| match node {
Node::Region {
generator,
source_region,
body,
} => {
let anonymous = generator.as_ref() == Program::ROOT_REGION_GENERATOR;
let own = generator.as_ref().starts_with("exatok::");
Node::Region {
generator: if anonymous {
Ident::from(format!("inline::{}", parent.name))
} else {
generator
},
source_region: match source_region {
Some(existing) => Some(existing),
None if own => None,
None => Some(parent.clone()),
},
body: Arc::new(attribute_nodes(body.as_ref().clone(), parent)),
}
}
Node::Block(body) => Node::Block(attribute_nodes(body, parent)),
Node::Loop {
var,
from,
to,
body,
} => Node::Loop {
var,
from,
to,
body: attribute_nodes(body, parent),
},
Node::If {
cond,
then,
otherwise,
} => Node::If {
cond,
then: attribute_nodes(then, parent),
otherwise: attribute_nodes(otherwise, parent),
},
other => other,
})
.collect()
}
fn fuse_or_trap(op_id: &str, output: &str, arms: &[Program]) -> Program {
match fuse_programs(arms) {
Ok(program) => attribute_regions(tag_program(op_id, program), op_id),
Err(error) => trap_program(
op_id,
output,
DataType::U32,
format!(
"{op_id} could not fuse its {} arms: {error}. Fix: repair grid-sync fusion for \
multi-pass exatok selection; do not substitute an empty Program.",
arms.len()
),
),
}
}
fn empty_count_program(op_id: &str, count: &str) -> Program {
Program::wrapped(
vec![BufferDecl::output(count, 0, DataType::U32).with_count(1)],
[1, 1, 1],
vec![wrap_anonymous(
op_id,
vec![Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![Node::store(count, Expr::u32(0), Expr::u32(0))],
)],
)],
)
}
#[cfg(feature = "multi-merge")]
fn empty_flag_program(op_id: &str, flags: &str) -> Program {
Program::wrapped(
vec![BufferDecl::output(flags, 0, DataType::U32).with_count(1)],
[1, 1, 1],
vec![wrap_anonymous(
op_id,
vec![Node::if_then(
Expr::eq(Expr::gid_x(), Expr::u32(0)),
vec![Node::store(flags, Expr::u32(0), Expr::u32(0))],
)],
)],
)
}
#[must_use]
pub fn host_argmin_leftmost(ranks: &[Rank]) -> Option<(u32, Rank)> {
let mut best: Option<(u32, Rank)> = None;
for (index, &rank) in ranks.iter().enumerate() {
if !rank.is_present() {
continue;
}
let index = u32::try_from(index).ok()?;
match best {
Some((_, current)) if rank.0 >= current.0 => {}
_ => best = Some((index, rank)),
}
}
best
}
#[must_use]
pub fn host_segmented_argmin_leftmost(
ranks: &[Rank],
segment_starts: &[u32],
) -> Option<Vec<Option<(u32, Rank)>>> {
let total = u32::try_from(ranks.len()).ok()?;
if segment_starts.len() < 2 || segment_starts[0] != 0 || *segment_starts.last()? != total {
return None;
}
if segment_starts.windows(2).any(|pair| pair[0] > pair[1]) {
return None;
}
let mut out = Vec::with_capacity(segment_starts.len() - 1);
for window in segment_starts.windows(2) {
let (begin, end) = (window[0] as usize, window[1] as usize);
out.push(
host_argmin_leftmost(ranks.get(begin..end)?)
.map(|(offset, rank)| (offset + window[0], rank)),
);
}
Some(out)
}
#[must_use]
pub fn host_compact_removed(values: &[u32], removed: &[u32]) -> Option<(Vec<u32>, u32)> {
if values.len() != removed.len() {
return None;
}
let survivors: Vec<u32> = values
.iter()
.zip(removed)
.filter(|&(_, &flag)| flag == 0)
.map(|(&value, _)| value)
.collect();
let count = u32::try_from(survivors.len()).ok()?;
Some((survivors, count))
}
#[must_use]
pub fn host_remap_segment_starts(removed: &[u32], segment_starts: &[u32]) -> Option<Vec<u32>> {
let total = u32::try_from(removed.len()).ok()?;
if segment_starts.len() < 2 || segment_starts[0] != 0 || *segment_starts.last()? != total {
return None;
}
let mut survivors_before = Vec::with_capacity(removed.len() + 1);
let mut running = 0u32;
survivors_before.push(0);
for &flag in removed {
running += u32::from(flag == 0);
survivors_before.push(running);
}
Some(
segment_starts
.iter()
.map(|&start| survivors_before[start as usize])
.collect(),
)
}
#[must_use]
pub fn host_argmin_merge_pass(
tokens: &[TokenId],
ranks: &[Rank],
merged_ids: &[TokenId],
segment_starts: &[u32],
) -> Option<(Vec<TokenId>, Vec<u32>)> {
if tokens.len() != ranks.len() || tokens.len() != merged_ids.len() {
return None;
}
let selections = host_segmented_argmin_leftmost(ranks, segment_starts)?;
let mut staged: Vec<TokenId> = tokens.to_vec();
let mut removed = vec![0u32; tokens.len()];
for selection in selections.into_iter().flatten() {
let index = selection.0 as usize;
if index + 1 >= tokens.len() {
return None;
}
staged[index] = merged_ids[index];
removed[index + 1] = 1;
}
let survivors = staged
.iter()
.zip(&removed)
.filter(|&(_, &flag)| flag == 0)
.map(|(&token, _)| token)
.collect();
let new_starts = host_remap_segment_starts(&removed, segment_starts)?;
Some((survivors, new_starts))
}
#[must_use]
pub fn host_select_non_overlapping(ranks: &[Rank], target: Rank) -> Vec<u32> {
let mut flags = Vec::with_capacity(ranks.len());
let mut previous_taken = false;
for &rank in ranks {
let taken = target.is_present() && rank == target && !previous_taken;
flags.push(u32::from(taken));
previous_taken = taken;
}
flags
}
#[must_use]
pub fn host_selected_indices(ranks: &[Rank], target: Rank) -> Vec<u32> {
host_select_non_overlapping(ranks, target)
.into_iter()
.enumerate()
.filter(|&(_, flag)| flag != 0)
.filter_map(|(index, _)| u32::try_from(index).ok())
.collect()
}
#[must_use]
pub fn host_apply_merges(
tokens: &[TokenId],
selected: &[u32],
merged_ids: &[TokenId],
) -> Option<Vec<TokenId>> {
if tokens.len() != selected.len() || tokens.len() != merged_ids.len() {
return None;
}
if selected.last().is_some_and(|&flag| flag != 0) {
return None;
}
if selected.windows(2).any(|pair| pair[0] != 0 && pair[1] != 0) {
return None;
}
let mut out = Vec::with_capacity(tokens.len());
let mut position = 0usize;
while position < tokens.len() {
if selected[position] != 0 {
out.push(merged_ids[position]);
position += 2;
} else {
out.push(tokens[position]);
position += 1;
}
}
Some(out)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn host_argmin_keeps_the_first_of_a_repeated_minimum() {
let ranks = [Rank(5), Rank(2), Rank(9), Rank(2), Rank(2)];
assert_eq!(host_argmin_leftmost(&ranks), Some((1, Rank(2))));
}
#[test]
fn host_argmin_reports_none_when_every_rank_is_absent() {
let ranks = [Rank::ABSENT; 4];
assert_eq!(host_argmin_leftmost(&ranks), None);
assert_eq!(host_argmin_leftmost(&[]), None);
}
#[test]
fn host_segmented_argmin_reports_absolute_indices() {
let ranks = [
Rank(9),
Rank(4),
Rank::ABSENT,
Rank(3),
Rank(3),
Rank::ABSENT,
];
let starts = [0, 3, 6];
assert_eq!(
host_segmented_argmin_leftmost(&ranks, &starts),
Some(vec![Some((1, Rank(4))), Some((3, Rank(3)))])
);
}
#[test]
fn host_segmented_argmin_refuses_a_malformed_table() {
let ranks = [Rank(1), Rank::ABSENT];
assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0, 1]), None);
assert_eq!(host_segmented_argmin_leftmost(&ranks, &[1, 2]), None);
assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0]), None);
assert_eq!(host_segmented_argmin_leftmost(&ranks, &[0, 2, 1]), None);
}
#[test]
fn host_compact_rejects_a_length_mismatch() {
assert_eq!(host_compact_removed(&[1, 2, 3], &[0, 0]), None);
assert_eq!(
host_compact_removed(&[1, 2, 3], &[0, 1, 0]),
Some((vec![1, 3], 2))
);
}
#[test]
fn host_remap_counts_survivors_strictly_before_each_start() {
let removed = [0, 1, 0, 0, 0];
assert_eq!(
host_remap_segment_starts(&removed, &[0, 3, 5]),
Some(vec![0, 2, 4])
);
assert_eq!(
host_remap_segment_starts(&[0, 0, 1, 0, 0], &[0, 2, 5]),
Some(vec![0, 2, 4])
);
assert_eq!(host_remap_segment_starts(&removed, &[0, 3, 4]), None);
}
#[test]
fn host_argmin_pass_merges_every_segment_and_rebases() {
let tokens = [
TokenId(1),
TokenId(2),
TokenId(3),
TokenId(4),
TokenId(5),
TokenId(6),
];
let ranks = [
Rank(7),
Rank(9),
Rank::ABSENT,
Rank(8),
Rank(2),
Rank::ABSENT,
];
let merged = [
TokenId(90),
TokenId(91),
TokenId(92),
TokenId(93),
TokenId(94),
TokenId(95),
];
assert_eq!(
host_argmin_merge_pass(&tokens, &ranks, &merged, &[0, 3, 6]),
Some((
vec![TokenId(90), TokenId(3), TokenId(4), TokenId(94)],
vec![0, 2, 4]
))
);
}
#[test]
fn host_argmin_pass_leaves_a_converged_segment_alone() {
let tokens = [TokenId(1), TokenId(2), TokenId(3), TokenId(4)];
let ranks = [Rank::ABSENT, Rank::ABSENT, Rank(5), Rank::ABSENT];
let merged = [TokenId(80), TokenId(81), TokenId(82), TokenId(83)];
assert_eq!(
host_argmin_merge_pass(&tokens, &ranks, &merged, &[0, 2, 4]),
Some((vec![TokenId(1), TokenId(2), TokenId(82)], vec![0, 2, 3]))
);
}
#[test]
fn host_selection_skips_the_neighbour_of_a_taken_position() {
let ranks = [Rank(7), Rank(7), Rank(7), Rank(7)];
assert_eq!(
host_select_non_overlapping(&ranks, Rank(7)),
vec![1, 0, 1, 0]
);
assert_eq!(host_selected_indices(&ranks, Rank(7)), vec![0, 2]);
}
#[test]
fn host_selection_ignores_an_absent_target() {
let ranks = [Rank::ABSENT, Rank::ABSENT, Rank::ABSENT];
assert_eq!(
host_select_non_overlapping(&ranks, Rank::ABSENT),
vec![0, 0, 0]
);
assert!(host_selected_indices(&ranks, Rank::ABSENT).is_empty());
}
#[test]
fn host_apply_merges_refuses_overlapping_or_trailing_selection() {
let tokens = [TokenId(1), TokenId(2), TokenId(3), TokenId(4)];
let merged = [TokenId(10), TokenId(20), TokenId(30), TokenId(40)];
assert_eq!(host_apply_merges(&tokens, &[1, 1, 0, 0], &merged), None);
assert_eq!(host_apply_merges(&tokens, &[0, 0, 0, 1], &merged), None);
assert_eq!(
host_apply_merges(&tokens, &[1, 0, 1, 0], &merged),
Some(vec![TokenId(10), TokenId(30)])
);
}
#[test]
#[allow(deprecated)]
fn attribution_writes_missing_edges_without_relocating_existing_ones() {
let owned = "vyre-primitives::reduce::min_u32_child";
let unattributed =
"vyre-primitives::reduce::multi_block_prefix_scan::guarded_single_block";
let program = Program::new(
vec![BufferDecl::output("out", 0, DataType::U32).with_count(1)],
[1, 1, 1],
vec![
Node::Region {
generator: Ident::from(owned.to_owned()),
source_region: Some(GeneratorRef {
name: ARGMIN_OP_ID.to_owned(),
}),
body: Arc::new(vec![]),
},
Node::Region {
generator: Ident::from(unattributed.to_owned()),
source_region: None,
body: Arc::new(vec![]),
},
],
);
let attributed = attribute_regions(program, COMPACT_OP_ID);
let entry = attributed.entry();
assert_eq!(entry.len(), 2, "attribution must not add or drop nodes");
match (&entry[0], &entry[1]) {
(
Node::Region {
generator: kept_name,
source_region: kept_parent,
..
},
Node::Region {
generator: added_name,
source_region: added_parent,
..
},
) => {
assert_eq!(kept_name.as_ref(), owned);
assert_eq!(
kept_parent.as_ref().map(|parent| parent.name.as_str()),
Some(ARGMIN_OP_ID),
"an existing parent was relocated to the composing op"
);
assert_eq!(added_name.as_ref(), unattributed);
assert_eq!(
added_parent.as_ref().map(|parent| parent.name.as_str()),
Some(COMPACT_OP_ID),
"a missing parent was not written"
);
}
other => unreachable!("attribution changed the node shape: {other:?}"),
}
}
#[test]
#[allow(deprecated)]
fn attribution_reaches_regions_nested_in_control_flow() {
let nested = Node::Region {
generator: Ident::from("vyre-primitives::guarded".to_owned()),
source_region: None,
body: Arc::new(vec![]),
};
let program = Program::new(
vec![BufferDecl::output("out", 0, DataType::U32).with_count(1)],
[1, 1, 1],
vec![Node::If {
cond: Expr::bool(true),
then: vec![nested.clone()],
otherwise: vec![Node::Loop {
var: Ident::from("i".to_owned()),
from: Expr::u32(0),
to: Expr::u32(1),
body: vec![nested],
}],
}],
);
let attributed = attribute_regions(program, COMPACT_OP_ID);
let mut parents = Vec::new();
collect_parents(attributed.entry(), &mut parents);
assert_eq!(
parents,
vec![Some(COMPACT_OP_ID.to_owned()), Some(COMPACT_OP_ID.to_owned())]
);
}
fn collect_parents(nodes: &[Node], out: &mut Vec<Option<String>>) {
for node in nodes {
match node {
Node::Region {
source_region,
body,
..
} => {
out.push(source_region.as_ref().map(|parent| parent.name.clone()));
collect_parents(body.as_ref(), out);
}
Node::Block(body) => collect_parents(body, out),
Node::Loop { body, .. } => collect_parents(body, out),
Node::If {
then, otherwise, ..
} => {
collect_parents(then, out);
collect_parents(otherwise, out);
}
_ => {}
}
}
}
}