Repository navigation
dialect-cute: verify_cute_semantics takes cubic time on a function with no CuTe operation #1647
Description
verify_cute_semantics runs on every module. For a function with no CuTe operation it still builds the provenance facts of each story. The fixpoint loop calls OrdinaryFacts::entries, a scan of the whole fact map, for every block argument in every round. So the time is cubic in the block count.
A chain of N blocks, one u32 block argument each, no CuTe operation (debug, 9df9e7c):
| N | verify |
|---|---|
| 100 | 0.52 s |
| 200 | 3.99 s |
| 400 | 32.2 s |
| 800 | 248 s |
A crate of large SIMT kernels builds in 388 s at 0143af5 (the parent of the #1598 commit) and did not finish in 1700 s at 9df9e7c.
A fix: skip a scope with no CuTe semantic operation. With it, N=800 takes 0.005 s, the crate builds in 483 s, and the dialect-cute suite passes (89). I can open a PR.
Patch
--- a/cuda-oxide/cute-rs-preview/dialect-cute/src/verify/ghosts.rs
+++ b/cuda-oxide/cute-rs-preview/dialect-cute/src/verify/ghosts.rs
@@ -150,7 +150,7 @@
}
/// Collect the closed set of operations allowed to carry semantic ghosts or metadata.
-fn all_high_level_semantic_ids() -> Vec<OpId> {
+pub(super) fn all_high_level_semantic_ids() -> Vec<OpId> {
let mut ids = tensor_semantic_ids().to_vec();
ids.push(crate::ops::copy::CuteStoreGlobalNoAllocateOp::get_opid_static());
ids.extend(gemv_semantic_ids());
--- a/cuda-oxide/cute-rs-preview/dialect-cute/src/verify/mod.rs
+++ b/cuda-oxide/cute-rs-preview/dialect-cute/src/verify/mod.rs
@@ -52,7 +52,7 @@
use cfg::operations_by_scope;
use epilogue::verify_epilogue_story;
use gemv::verify_gemv_story;
-use ghosts::audit_cute_ghosts;
+use ghosts::{all_high_level_semantic_ids, audit_cute_ghosts};
pub use ghosts::type_contains_cute_ghost;
use mma::verify_smem_mma_story;
use pipeline::verify_pipeline_story;
@@ -297,7 +297,17 @@
verify_local_op(ctx, *operation)?;
}
audit_cute_ghosts(ctx, &all_ops)?;
+ let semantic_ids = all_high_level_semantic_ids();
for scope in operations_by_scope(ctx, module, &all_ops) {
+ // A scope with no CuTe semantic operation has no story to verify. Each story builds provenance
+ // facts, and `OrdinaryFacts::entries` scans the whole fact map for every store, so a large SIMT
+ // kernel would take a long time for nothing.
+ if !scope
+ .iter()
+ .any(|operation| semantic_ids.contains(&Operation::get_opid(*operation, ctx)))
+ {
+ continue;
+ }
verify_scheduler_story(ctx, &scope)?;
verify_pipeline_story(ctx, &scope)?;
verify_tma_story(ctx, &scope)?;Timing test (uses the helpers of verify's test module)
/// Time `verify_cute_semantics` on a function that holds no CuTe operation: a chain of `blocks` blocks, each with one
/// 32-bit block argument forwarded to the next.
fn time_verify_of_a_block_chain(blocks: usize) -> std::time::Duration {
let mut ctx = Context::new();
let (module, module_block) = module_top(&mut ctx);
let function_type = FunctionType::get(&mut ctx, vec![], vec![]);
let function = Operation::new(
&mut ctx,
MirFuncOp::get_concrete_op_info(),
vec![],
vec![],
vec![],
1,
);
let function_op = MirFuncOp::new(&mut ctx, function, TypeAttr::new(function_type.into()));
function_op.set_symbol_name(&mut ctx, "chain".try_into().unwrap());
function.insert_at_back(module_block, &ctx);
let region = function.deref(&ctx).get_region(0);
let u32_ty: TypeHandle = IntegerType::get(&ctx, 32, Signedness::Unsigned).into();
let entry = BasicBlock::new(&mut ctx, None, vec![]);
entry.insert_at_back(region, &ctx);
let mut value = undef(&mut ctx, entry, u32_ty);
let mut previous = entry;
for _ in 0..blocks {
let next = BasicBlock::new(&mut ctx, None, vec![u32_ty]);
next.insert_at_back(region, &ctx);
goto(&mut ctx, previous, next, vec![value]);
value = next.deref(&ctx).get_argument(0);
previous = next;
}
Operation::new(
&mut ctx,
MirReturnOp::get_concrete_op_info(),
vec![],
vec![],
vec![],
0,
)
.insert_at_back(previous, &ctx);
let start = std::time::Instant::now();
verify_cute_semantics(&ctx, module).expect("a chain of blocks with no CuTe operation verifies");
start.elapsed()
}
/// Timing probe: the time grows with the block count although the function holds no CuTe operation. Run with `cargo test -p dialect-cute --lib verify_time -- --ignored --nocapture`.
#[test]
#[ignore = "timing probe"]
fn verify_time_of_a_scope_with_no_cute_operation() {
for blocks in [100, 200, 400, 800] {
let took = time_verify_of_a_block_chain(blocks);
eprintln!("blocks={blocks} verify={:.3} s", took.as_secs_f64());
}
}AI use: found and measured with Claude Code.
Activity