tiny.accy.executable.plan

1const std = @import("std");2const gpu = @import("gpu");3const choir_abi = @import("choir_abi");4const choir = @import("choir");5const accy_root = @import("../root.zig");6const artifact_product = @import("../artifact/root.zig");7const tuning_mod = @import("tuning.zig");89pub const product_name = "accy.exec";1011pub const LaunchOptions = struct {12    stream: ?gpu.StreamHandle = null,13    wait_events: []const gpu.EventHandle = &.{},14    signal_event: ?gpu.EventHandle = null,15    tuning: LaunchTuning = .{},16    runtime_scalar_arguments: []const choir_abi.ScalarArgument = &.{},17};1819pub const LaunchGraphNode = struct {20    kernel_index: usize,21    stream: ?gpu.StreamHandle = null,22    wait_events: []const gpu.EventHandle = &.{},23    signal_event: ?gpu.EventHandle = null,24    tuning: LaunchTuning = .{},25    runtime_scalar_arguments: []const choir_abi.ScalarArgument = &.{},26};2728pub const LaunchGraphDependency = struct {29    producer_node_index: usize,30    consumer_node_index: usize,31    slot_id: usize,32};3334pub const LaunchGraphLoopCarry = struct {35    initial_slot_id: usize,36    input_slot_id: usize,37    output_slot_id: usize,38    final_slot_id: usize,39};4041pub const LaunchGraphLoop = struct {42    first_node_index: usize,43    node_count: usize,44    trip_count: u64,45    carries: []const LaunchGraphLoopCarry = &.{},46};4748pub fn launchGraphLoopCarryFinalSlot(carry: LaunchGraphLoopCarry, trip_count: u64) usize {49    if (trip_count % 2 == 0) return carry.initial_slot_id;50    return carry.output_slot_id;51}5253pub const LaunchGraphPlan = struct {54    nodes: []const LaunchGraphNode,55    dependencies: []const LaunchGraphDependency = &.{},56    loops: []const LaunchGraphLoop = &.{},57    validated: bool = false,58};5960pub const OwnedLaunchGraphPlan = struct {61    allocator: std.mem.Allocator,62    nodes: []LaunchGraphNode,63    dependencies: []LaunchGraphDependency,64    loops: []LaunchGraphLoop = &.{},65    tuning_selections: []LaunchTuningSelection = &.{},66    validated: bool = false,6768    pub fn deinit(self: *OwnedLaunchGraphPlan) void {69        if (self.nodes.len != 0) self.allocator.free(self.nodes);70        if (self.dependencies.len != 0) self.allocator.free(self.dependencies);71        for (self.loops) |loop| {72            if (loop.carries.len != 0) self.allocator.free(@constCast(loop.carries));73        }74        if (self.loops.len != 0) self.allocator.free(self.loops);75        if (self.tuning_selections.len != 0) self.allocator.free(self.tuning_selections);76        self.* = undefined;77    }7879    pub fn plan(self: *const OwnedLaunchGraphPlan) LaunchGraphPlan {80        return .{81            .nodes = self.nodes,82            .dependencies = self.dependencies,83            .loops = self.loops,84            .validated = self.validated,85        };86    }8788    pub fn copyWithLaunchOptions(89        self: *const OwnedLaunchGraphPlan,90        allocator: std.mem.Allocator,91        launch_options: LaunchOptions,92    ) gpu.BackendError!OwnedLaunchGraphPlan {93        const nodes = allocator.alloc(LaunchGraphNode, self.nodes.len) catch return error.OutOfMemory;94        errdefer allocator.free(nodes);9596        for (nodes, 0..) |*node, index| {97            node.* = self.nodes[index];98            node.stream = launch_options.stream;99            node.wait_events = if (index == 0) launch_options.wait_events else &.{};100            node.signal_event = if (index + 1 == nodes.len) launch_options.signal_event else null;101            node.tuning = launch_options.tuning;102            node.runtime_scalar_arguments = launch_options.runtime_scalar_arguments;103        }104105        var dependencies: []LaunchGraphDependency = &.{};106        if (self.dependencies.len != 0) {107            dependencies = allocator.dupe(LaunchGraphDependency, self.dependencies) catch return error.OutOfMemory;108        }109        errdefer if (dependencies.len != 0) allocator.free(dependencies);110111        var loops: []LaunchGraphLoop = &.{};112        if (self.loops.len != 0) {113            loops = allocator.alloc(LaunchGraphLoop, self.loops.len) catch return error.OutOfMemory;114            var copied_loops: usize = 0;115            errdefer {116                for (loops[0..copied_loops]) |loop| {117                    if (loop.carries.len != 0) allocator.free(@constCast(loop.carries));118                }119                allocator.free(loops);120            }121            for (self.loops, 0..) |loop, index| {122                var carries: []LaunchGraphLoopCarry = &.{};123                if (loop.carries.len != 0) {124                    carries = allocator.dupe(LaunchGraphLoopCarry, loop.carries) catch return error.OutOfMemory;125                }126                loops[index] = .{127                    .first_node_index = loop.first_node_index,128                    .node_count = loop.node_count,129                    .trip_count = loop.trip_count,130                    .carries = carries,131                };132                copied_loops += 1;133            }134        }135136        return .{137            .allocator = allocator,138            .nodes = nodes,139            .dependencies = dependencies,140            .loops = loops,141        };142    }143144    pub fn applyMeasuredLaunchTuning(145        self: *OwnedLaunchGraphPlan,146        artifact_plan: *const artifact_product.BackendArtifactPlan,147        measurements: []const LaunchCandidateMeasurement,148    ) gpu.BackendError!void {149        if (self.nodes.len != artifact_plan.kernels.items.len) return error.InvalidArtifact;150151        var selection_count: usize = 0;152        for (self.nodes) |node| {153            if (node.kernel_index >= artifact_plan.kernels.items.len) return error.InvalidArtifact;154            const planned = artifact_plan.kernels.items[node.kernel_index];155            if (try selectedLaunchMeasurement(planned, measurements)) |_| selection_count += 1;156        }157158        var new_selections: []LaunchTuningSelection = &.{};159        if (selection_count != 0) {160            new_selections = self.allocator.alloc(LaunchTuningSelection, selection_count) catch return error.OutOfMemory;161        }162        errdefer if (new_selections.len != 0) self.allocator.free(new_selections);163164        var selection_index: usize = 0;165        for (self.nodes) |node| {166            const planned = artifact_plan.kernels.items[node.kernel_index];167            if (try selectedLaunchMeasurement(planned, measurements)) |measurement| {168                new_selections[selection_index] = .{169                    .kernel_id = measurement.kernel_id,170                    .candidate_index = measurement.candidate_index,171                    .median_ns = measurement.median_ns,172                    .sample_count = measurement.sample_count,173                };174                selection_index += 1;175            }176        }177178        self.installLaunchTuningSelections(artifact_plan, new_selections);179    }180181    pub fn applyCachedLaunchTuning(182        self: *OwnedLaunchGraphPlan,183        caps: gpu.BackendCapabilities,184        artifact_plan: *const artifact_product.BackendArtifactPlan,185        cache: *const LaunchTuningCache,186    ) gpu.BackendError!void {187        if (self.nodes.len != artifact_plan.kernels.items.len) return error.InvalidArtifact;188189        var selection_count: usize = 0;190        for (self.nodes) |node| {191            if (node.kernel_index >= artifact_plan.kernels.items.len) return error.InvalidArtifact;192            const planned = artifact_plan.kernels.items[node.kernel_index];193            if (try cache.selectionForKernel(caps, planned)) |_| selection_count += 1;194        }195196        var new_selections: []LaunchTuningSelection = &.{};197        if (selection_count != 0) {198            new_selections = self.allocator.alloc(LaunchTuningSelection, selection_count) catch return error.OutOfMemory;199        }200        errdefer if (new_selections.len != 0) self.allocator.free(new_selections);201202        var selection_index: usize = 0;203        for (self.nodes) |node| {204            const planned = artifact_plan.kernels.items[node.kernel_index];205            if (try cache.selectionForKernel(caps, planned)) |selection| {206                new_selections[selection_index] = selection;207                selection_index += 1;208            }209        }210211        self.installLaunchTuningSelections(artifact_plan, new_selections);212    }213214    fn installLaunchTuningSelections(215        self: *OwnedLaunchGraphPlan,216        artifact_plan: *const artifact_product.BackendArtifactPlan,217        new_selections: []LaunchTuningSelection,218    ) void {219        if (self.tuning_selections.len != 0) self.allocator.free(self.tuning_selections);220        self.tuning_selections = new_selections;221        var selection_index: usize = 0;222        for (self.nodes) |*node| {223            node.tuning = .{};224            const planned = artifact_plan.kernels.items[node.kernel_index];225            if (selection_index < self.tuning_selections.len and self.tuning_selections[selection_index].kernel_id == planned.kernel_id) {226                node.tuning.selections = self.tuning_selections[selection_index .. selection_index + 1];227                selection_index += 1;228            }229        }230    }231};232233const CompiledFragmentState = struct {234    allocator: std.mem.Allocator,235    artifact_plan: artifact_product.BackendArtifactPlan,236    artifact_fingerprint: u64,237    launch_plan: OwnedLaunchGraphPlan,238    fingerprint_value: u64,239240    fn deinit(self: *CompiledFragmentState) void {241        self.launch_plan.deinit();242        self.artifact_plan.deinit();243        self.* = undefined;244    }245};246247pub const CompiledFragment = opaque {248    fn stateConst(self: *const CompiledFragment) *const CompiledFragmentState {249        return @ptrCast(@alignCast(self));250    }251252    fn stateMut(self: *CompiledFragment) *CompiledFragmentState {253        return @ptrCast(@alignCast(self));254    }255256    pub fn init(257        allocator: std.mem.Allocator,258        artifact_module: *artifact_product.ArtifactJob,259    ) !*CompiledFragment {260        var artifact_plan = try artifact_module.copyArtifactPlan(allocator);261        errdefer artifact_plan.deinit();262263        var launch_plan = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});264        errdefer launch_plan.deinit();265266        const artifact_fingerprint = artifact_module.fingerprint();267        const product_stamp = fragmentProductStamp(268            artifact_fingerprint,269            launchGraphFingerprint(launch_plan.plan()),270        );271272        const state = allocator.create(CompiledFragmentState) catch return error.OutOfMemory;273        errdefer allocator.destroy(state);274        state.* = .{275            .allocator = allocator,276            .artifact_plan = artifact_plan,277            .artifact_fingerprint = artifact_fingerprint,278            .launch_plan = launch_plan,279            .fingerprint_value = product_stamp.fingerprint,280        };281        const fragment: *CompiledFragment = @ptrCast(state);282        try fragment.verify();283        return fragment;284    }285286    pub fn initWithLaunchPlan(287        allocator: std.mem.Allocator,288        artifact_module: *artifact_product.ArtifactJob,289        launch_plan: OwnedLaunchGraphPlan,290    ) !*CompiledFragment {291        var owned_launch_plan = launch_plan;292        errdefer owned_launch_plan.deinit();293294        var artifact_plan = try artifact_module.copyArtifactPlan(allocator);295        errdefer artifact_plan.deinit();296297        const artifact_fingerprint = artifact_module.fingerprint();298        const product_stamp = fragmentProductStamp(299            artifact_fingerprint,300            launchGraphFingerprint(owned_launch_plan.plan()),301        );302303        const state = allocator.create(CompiledFragmentState) catch return error.OutOfMemory;304        errdefer allocator.destroy(state);305        state.* = .{306            .allocator = allocator,307            .artifact_plan = artifact_plan,308            .artifact_fingerprint = artifact_fingerprint,309            .launch_plan = owned_launch_plan,310            .fingerprint_value = product_stamp.fingerprint,311        };312        const fragment: *CompiledFragment = @ptrCast(state);313        try fragment.verify();314        return fragment;315    }316317    pub fn deinit(self: *CompiledFragment) void {318        const state = self.stateMut();319        const allocator = state.allocator;320        state.deinit();321        allocator.destroy(state);322    }323324    pub fn verify(self: *const CompiledFragment) !void {325        const state = self.stateConst();326        try validateLaunchGraph(327            state.allocator,328            &state.artifact_plan,329            state.launch_plan.plan(),330            false,331        );332    }333334    pub fn fingerprint(self: *const CompiledFragment) u64 {335        return self.stateConst().fingerprint_value;336    }337338    pub fn artifactFingerprint(self: *const CompiledFragment) u64 {339        return self.stateConst().artifact_fingerprint;340    }341342    pub fn productStamp(self: *const CompiledFragment) choir.product.incremental.ProductStamp {343        return choir.product.incremental.productStamp(product_name, self.fingerprint());344    }345346    pub fn artifactPlan(self: *const CompiledFragment) *const artifact_product.BackendArtifactPlan {347        return &self.stateConst().artifact_plan;348    }349350    pub fn launchPlan(self: *const CompiledFragment) LaunchGraphPlan {351        return self.stateConst().launch_plan.plan();352    }353354    pub fn kernelCount(self: *const CompiledFragment) usize {355        return self.artifactPlan().kernelCount();356    }357358    pub fn createLaunchGraphPlan(359        self: *const CompiledFragment,360        allocator: std.mem.Allocator,361        launch_options: LaunchOptions,362    ) gpu.BackendError!OwnedLaunchGraphPlan {363        const state = self.stateConst();364        var graph = try state.launch_plan.copyWithLaunchOptions(allocator, launch_options);365        errdefer graph.deinit();366        const view = graph.plan();367        try validateLaunchGraph(allocator, self.artifactPlan(), view, launchGraphNeedsDependencyEvents(view));368        graph.validated = true;369        return graph;370    }371};372373pub fn compileFragmentFromArtifactJob(374    allocator: std.mem.Allocator,375    artifact_module: *artifact_product.ArtifactJob,376) !*CompiledFragment {377    return try CompiledFragment.init(allocator, artifact_module);378}379380pub fn compileFragmentFromArtifactJobWithLaunchPlan(381    allocator: std.mem.Allocator,382    artifact_module: *artifact_product.ArtifactJob,383    launch_plan: OwnedLaunchGraphPlan,384) !*CompiledFragment {385    return try CompiledFragment.initWithLaunchPlan(allocator, artifact_module, launch_plan);386}387388pub fn createDataflowLaunchGraphPlan(389    allocator: std.mem.Allocator,390    artifact_plan: *const artifact_product.BackendArtifactPlan,391    launch_options: LaunchOptions,392) gpu.BackendError!OwnedLaunchGraphPlan {393    const kernel_count = artifact_plan.kernels.items.len;394    const nodes = allocator.alloc(LaunchGraphNode, kernel_count) catch return error.OutOfMemory;395    errdefer allocator.free(nodes);396397    const scheduled = allocator.alloc(bool, kernel_count) catch return error.OutOfMemory;398    defer allocator.free(scheduled);399    @memset(scheduled, false);400401    const kernel_to_node = allocator.alloc(usize, kernel_count) catch return error.OutOfMemory;402    defer allocator.free(kernel_to_node);403    @memset(kernel_to_node, std.math.maxInt(usize));404405    for (nodes, 0..) |*node, node_index| {406        const kernel_index = nextReadyKernelIndex(artifact_plan, scheduled) orelse return error.InvalidArtifact;407        scheduled[kernel_index] = true;408        kernel_to_node[kernel_index] = node_index;409        node.* = .{410            .kernel_index = kernel_index,411            .stream = launch_options.stream,412            .wait_events = if (node_index == 0) launch_options.wait_events else &.{},413            .signal_event = if (node_index + 1 == kernel_count) launch_options.signal_event else null,414            .tuning = launch_options.tuning,415            .runtime_scalar_arguments = launch_options.runtime_scalar_arguments,416        };417    }418419    var dependencies: std.ArrayListUnmanaged(LaunchGraphDependency) = .empty;420    errdefer dependencies.deinit(allocator);421422    for (nodes, 0..) |consumer_node, consumer_node_index| {423        const consumer = artifact_plan.kernels.items[consumer_node.kernel_index];424        for (consumer.input_slot_ids) |slot_id| {425            const producer_index = producerKernelIndexForConsumedSlot(426                artifact_plan,427                slot_id,428                consumer_node.kernel_index,429            ) orelse continue;430            if (producer_index == consumer_node.kernel_index) continue;431            const producer_node_index = kernel_to_node[producer_index];432            if (producer_node_index == std.math.maxInt(usize)) return error.InvalidArtifact;433            const dependency = LaunchGraphDependency{434                .producer_node_index = producer_node_index,435                .consumer_node_index = consumer_node_index,436                .slot_id = slot_id,437            };438            if (dependencyExists(dependencies.items, dependency.producer_node_index, dependency.consumer_node_index, dependency.slot_id)) continue;439            dependencies.append(allocator, dependency) catch return error.OutOfMemory;440        }441    }442443    return .{444        .allocator = allocator,445        .nodes = nodes,446        .dependencies = dependencies.toOwnedSlice(allocator) catch return error.OutOfMemory,447    };448}449450pub fn launchGraphFingerprint(graph: LaunchGraphPlan) u64 {451    var hasher = choir.product.incremental.FingerprintBuilder{};452    hasher.updateBytes("accy.exec.launch_graph");453    hashU64(&hasher, graph.nodes.len);454    for (graph.nodes) |node| {455        hashU64(&hasher, node.kernel_index);456    }457    hashU64(&hasher, graph.dependencies.len);458    for (graph.dependencies) |dependency| {459        hashU64(&hasher, dependency.producer_node_index);460        hashU64(&hasher, dependency.consumer_node_index);461        hashU64(&hasher, dependency.slot_id);462    }463    hashU64(&hasher, graph.loops.len);464    for (graph.loops) |loop| {465        hashU64(&hasher, loop.first_node_index);466        hashU64(&hasher, loop.node_count);467        hashU64(&hasher, loop.trip_count);468        hashU64(&hasher, loop.carries.len);469        for (loop.carries) |carry| {470            hashU64(&hasher, carry.initial_slot_id);471            hashU64(&hasher, carry.input_slot_id);472            hashU64(&hasher, carry.output_slot_id);473            hashU64(&hasher, carry.final_slot_id);474        }475    }476    return hasher.finish();477}478479pub fn validateLaunchGraph(480    scratch: std.mem.Allocator,481    artifact_plan: *const artifact_product.BackendArtifactPlan,482    graph: LaunchGraphPlan,483    dependency_events: bool,484) gpu.BackendError!void {485    if (graph.nodes.len != artifact_plan.kernels.items.len) return error.InvalidArtifact;486    const seen = scratch.alloc(bool, artifact_plan.kernels.items.len) catch return error.OutOfMemory;487    defer scratch.free(seen);488    @memset(seen, false);489    for (graph.nodes) |node| {490        if (node.kernel_index >= artifact_plan.kernels.items.len) return error.InvalidArtifact;491        if (seen[node.kernel_index]) return error.InvalidArtifact;492        seen[node.kernel_index] = true;493    }494    for (graph.dependencies, 0..) |dependency, dependency_index| {495        if (dependency.producer_node_index >= graph.nodes.len) return error.InvalidArtifact;496        if (dependency.consumer_node_index >= graph.nodes.len) return error.InvalidArtifact;497        if (dependency.producer_node_index == dependency.consumer_node_index) return error.InvalidArtifact;498        if (dependency.producer_node_index >= dependency.consumer_node_index) return error.InvalidArtifact;499        if (dependencyExists(graph.dependencies[0..dependency_index], dependency.producer_node_index, dependency.consumer_node_index, dependency.slot_id)) {500            return error.InvalidArtifact;501        }502        const producer = graph.nodes[dependency.producer_node_index];503        const consumer = graph.nodes[dependency.consumer_node_index];504        if (dependency_events and producer.stream == null) return error.LaunchArgumentMismatch;505        if (artifact_plan.kernels.items[producer.kernel_index].output_slot_id != dependency.slot_id) return error.InvalidArtifact;506        if (!kernelConsumesSlot(artifact_plan.kernels.items[consumer.kernel_index], dependency.slot_id)) return error.InvalidArtifact;507    }508    try validateLaunchGraphDependencyClosure(artifact_plan, graph);509    try validateLaunchGraphLoops(scratch, artifact_plan, graph);510}511512pub fn launchGraphNeedsDependencyEvents(graph: LaunchGraphPlan) bool {513    for (graph.dependencies) |dependency| {514        if (dependency.producer_node_index >= graph.nodes.len) return false;515        if (dependency.consumer_node_index >= graph.nodes.len) return false;516        const producer = graph.nodes[dependency.producer_node_index];517        const consumer = graph.nodes[dependency.consumer_node_index];518        if (!sameLaunchStream(producer.stream, consumer.stream)) return true;519    }520    return false;521}522523pub fn incomingDependencyCount(graph: LaunchGraphPlan, node_index: usize) usize {524    var count: usize = 0;525    for (graph.dependencies) |dependency| {526        if (dependency.consumer_node_index == node_index) count += 1;527    }528    return count;529}530531fn sameLaunchStream(lhs: ?gpu.StreamHandle, rhs: ?gpu.StreamHandle) bool {532    if (lhs == null and rhs == null) return true;533    if (lhs == null or rhs == null) return false;534    return lhs.?.id == rhs.?.id and lhs.?.backend == rhs.?.backend;535}536537fn producerKernelIndexForConsumedSlot(538    artifact_plan: *const artifact_product.BackendArtifactPlan,539    slot_id: usize,540    consumer_kernel_index: usize,541) ?usize {542    var preceding_producer: ?usize = null;543    for (artifact_plan.kernels.items[0..consumer_kernel_index], 0..) |kernel, index| {544        if (kernel.output_slot_id == slot_id) preceding_producer = index;545    }546    if (preceding_producer) |producer| return producer;547548    var unique_producer: ?usize = null;549    for (artifact_plan.kernels.items, 0..) |kernel, index| {550        if (kernel.output_slot_id != slot_id) continue;551        if (unique_producer != null) return null;552        unique_producer = index;553    }554    if (unique_producer) |producer| {555        if (producer != consumer_kernel_index) return producer;556    }557    return null;558}559560fn nextReadyKernelIndex(561    artifact_plan: *const artifact_product.BackendArtifactPlan,562    scheduled: []const bool,563) ?usize {564    for (artifact_plan.kernels.items, 0..) |_, kernel_index| {565        if (scheduled[kernel_index]) continue;566        if (kernelDependenciesScheduled(artifact_plan, scheduled, kernel_index)) return kernel_index;567    }568    return null;569}570571fn kernelDependenciesScheduled(572    artifact_plan: *const artifact_product.BackendArtifactPlan,573    scheduled: []const bool,574    consumer_kernel_index: usize,575) bool {576    const consumer = artifact_plan.kernels.items[consumer_kernel_index];577    for (consumer.input_slot_ids) |slot_id| {578        const producer_index = producerKernelIndexForConsumedSlot(579            artifact_plan,580            slot_id,581            consumer_kernel_index,582        ) orelse continue;583        if (producer_index == consumer_kernel_index) continue;584        if (!scheduled[producer_index]) return false;585    }586    return true;587}588589fn validateLaunchGraphDependencyClosure(590    artifact_plan: *const artifact_product.BackendArtifactPlan,591    graph: LaunchGraphPlan,592) gpu.BackendError!void {593    for (graph.nodes, 0..) |consumer_node, consumer_node_index| {594        const consumer = artifact_plan.kernels.items[consumer_node.kernel_index];595        for (consumer.input_slot_ids) |slot_id| {596            const producer_node_index = producerNodeIndexForConsumedSlot(597                artifact_plan,598                graph,599                slot_id,600                consumer_node.kernel_index,601            ) orelse continue;602            if (producer_node_index == consumer_node_index) continue;603            if (producer_node_index >= consumer_node_index) return error.InvalidArtifact;604            if (!dependencyExists(graph.dependencies, producer_node_index, consumer_node_index, slot_id)) {605                return error.InvalidArtifact;606            }607        }608    }609}610611fn validateLaunchGraphLoops(612    scratch: std.mem.Allocator,613    artifact_plan: *const artifact_product.BackendArtifactPlan,614    graph: LaunchGraphPlan,615) gpu.BackendError!void {616    if (graph.loops.len == 0) return;617    const loop_node = scratch.alloc(bool, graph.nodes.len) catch return error.OutOfMemory;618    defer scratch.free(loop_node);619    @memset(loop_node, false);620621    for (graph.loops) |loop| {622        if (loop.node_count == 0) return error.InvalidArtifact;623        const last_node_index = std.math.add(usize, loop.first_node_index, loop.node_count) catch return error.InvalidArtifact;624        if (last_node_index > graph.nodes.len) return error.InvalidArtifact;625        for (loop_node[loop.first_node_index..last_node_index]) |*seen| {626            if (seen.*) return error.InvalidArtifact;627            seen.* = true;628        }629        for (loop.carries) |carry| {630            if (carry.input_slot_id == carry.output_slot_id) return error.InvalidArtifact;631            if (loop.trip_count != 0 and carry.initial_slot_id == carry.output_slot_id) return error.InvalidArtifact;632            if (launchGraphLoopCarryFinalSlot(carry, loop.trip_count) != carry.final_slot_id) return error.InvalidArtifact;633            if (!loopConsumesSlot(artifact_plan, graph, loop, carry.input_slot_id)) return error.InvalidArtifact;634            if (!loopProducesSlot(artifact_plan, graph, loop, carry.output_slot_id)) return error.InvalidArtifact;635        }636    }637}638639fn loopConsumesSlot(640    artifact_plan: *const artifact_product.BackendArtifactPlan,641    graph: LaunchGraphPlan,642    loop: LaunchGraphLoop,643    slot_id: usize,644) bool {645    const end = loop.first_node_index + loop.node_count;646    for (graph.nodes[loop.first_node_index..end]) |node| {647        if (kernelConsumesSlot(artifact_plan.kernels.items[node.kernel_index], slot_id)) return true;648    }649    return false;650}651652fn loopProducesSlot(653    artifact_plan: *const artifact_product.BackendArtifactPlan,654    graph: LaunchGraphPlan,655    loop: LaunchGraphLoop,656    slot_id: usize,657) bool {658    const end = loop.first_node_index + loop.node_count;659    for (graph.nodes[loop.first_node_index..end]) |node| {660        if (artifact_plan.kernels.items[node.kernel_index].output_slot_id == slot_id) return true;661    }662    return false;663}664665fn producerNodeIndexForConsumedSlot(666    artifact_plan: *const artifact_product.BackendArtifactPlan,667    graph: LaunchGraphPlan,668    slot_id: usize,669    consumer_kernel_index: usize,670) ?usize {671    const producer_kernel_index = producerKernelIndexForConsumedSlot(672        artifact_plan,673        slot_id,674        consumer_kernel_index,675    ) orelse return null;676    for (graph.nodes, 0..) |node, node_index| {677        if (node.kernel_index == producer_kernel_index) return node_index;678    }679    return null;680}681682fn dependencyExists(683    dependencies: []const LaunchGraphDependency,684    producer_node_index: usize,685    consumer_node_index: usize,686    slot_id: usize,687) bool {688    for (dependencies) |dependency| {689        if (dependency.producer_node_index != producer_node_index) continue;690        if (dependency.consumer_node_index != consumer_node_index) continue;691        if (dependency.slot_id != slot_id) continue;692        return true;693    }694    return false;695}696697fn kernelConsumesSlot(kernel: artifact_product.PlannedKernel, slot_id: usize) bool {698    for (kernel.input_slot_ids) |input_slot_id| {699        if (input_slot_id == slot_id) return true;700    }701    return false;702}703704pub fn fragmentProductStamp(705    artifact_fingerprint: u64,706    launch_graph_fingerprint: u64,707) choir.product.incremental.ProductStamp {708    const artifact_stamp = choir.product.incremental.productStamp(709        artifact_product.product_name,710        artifact_fingerprint,711    );712    return choir.product.incremental.derivedProductStamp(713        product_name,714        &.{artifact_stamp},715        launch_graph_fingerprint,716    );717}718719fn hashU64(hasher: *choir.product.incremental.FingerprintBuilder, value: u64) void {720    hasher.updateU64(value);721}722723const LaunchCandidateMeasurement = tuning_mod.LaunchCandidateMeasurement;724const LaunchTuningSelection = tuning_mod.LaunchTuningSelection;725const LaunchTuningCache = tuning_mod.LaunchTuningCache;726const LaunchTuning = tuning_mod.LaunchTuning;727const selectedLaunchMeasurement = tuning_mod.selectedLaunchMeasurement;728729fn appendTestKernel(730    allocator: std.mem.Allocator,731    artifact_plan: *artifact_product.BackendArtifactPlan,732    kernel_id: usize,733    output_slot_id: usize,734    input_slot_ids: []const usize,735) !void {736    const inputs = try allocator.dupe(usize, input_slot_ids);737    errdefer allocator.free(inputs);738739    const entry_name = if (kernel_id == 0) "kernel0" else "kernel1";740    const compile_entry_name = try allocator.dupe(u8, entry_name);741    var compile_entry_owned = true;742    errdefer if (compile_entry_owned) allocator.free(compile_entry_name);743744    var artifact = try gpu.KernelArtifact.init(allocator, .{745        .backend = .cuda,746        .format = .cuda_ptx,747        .entry_name = entry_name,748        .argument_count = 0,749    });750    errdefer artifact.deinit();751752    try artifact_plan.kernels.append(allocator, .{753        .compile = .{754            .source = .tensor,755            .launch = .generic,756            .format = .cuda_ptx,757            .entry_name = compile_entry_name,758            .argument_count = 0,759            .required_dtypes = gpu.DTypeSet.init(&.{.f32}),760            .payload = .none,761            .payload_byte_count = 0,762        },763        .kernel_id = kernel_id,764        .work_item_id = kernel_id,765        .output_slot_id = output_slot_id,766        .input_slot_ids = inputs,767        .output_layout_fingerprint = 0,768        .input_layout_fingerprint = 0,769        .element_count = 1,770        .op_count = 1,771        .resources = .{772            .element_count = 1,773            .element_size = 4,774            .op_count = 1,775        },776        .artifact = artifact,777        .launch_resources = .{778            .format = .cuda_ptx,779            .element_count = 1,780            .geometry = .{781                .grid = .{ 1, 1, 1 },782                .threadgroup = .{ 1, 1, 1 },783            },784        },785        .element_count_argument = .none,786        .element_count_argument_value = 0,787        .runtime_scalar_argument_count = 0,788        .runtime_scalar_defaults = &.{},789        .static_arguments = &.{},790    });791    compile_entry_owned = false;792}793794test "compiled fragment copies artifact job plan" {795    const allocator = std.testing.allocator;796797    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{798        .backend_kind = .cuda,799        .artifact_format = .cuda_ptx,800        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,801    });802    var plan_owned = true;803    errdefer if (plan_owned) artifact_plan.deinit();804805    const artifact_module = try artifact_product.ArtifactJob.init(806        allocator,807        artifact_plan,808    );809    plan_owned = false;810    var artifact_owned = true;811    errdefer if (artifact_owned) artifact_module.deinit();812813    const artifact_fingerprint = artifact_module.fingerprint();814    var first = try CompiledFragment.init(allocator, artifact_module);815    errdefer first.deinit();816    var second = try CompiledFragment.init(allocator, artifact_module);817    errdefer second.deinit();818819    artifact_module.deinit();820    artifact_owned = false;821    defer second.deinit();822    defer first.deinit();823824    try std.testing.expectEqualStrings(product_name, "accy.exec");825    try first.verify();826    try second.verify();827    const expected_stamp = choir.product.incremental.derivedProductStamp(828        product_name,829        &.{choir.product.incremental.productStamp(artifact_product.product_name, artifact_fingerprint)},830        launchGraphFingerprint(first.launchPlan()),831    );832    try std.testing.expectEqualStrings(product_name, expected_stamp.name);833    try std.testing.expectEqual(expected_stamp.fingerprint, first.fingerprint());834    try std.testing.expectEqual(first.fingerprint(), second.fingerprint());835    try std.testing.expectEqualStrings(product_name, first.productStamp().name);836    try std.testing.expectEqual(first.fingerprint(), first.productStamp().fingerprint);837    try std.testing.expectEqual(artifact_fingerprint, first.artifactFingerprint());838    try std.testing.expectEqual(@as(usize, 0), first.kernelCount());839    try std.testing.expectEqual(@as(usize, 0), first.launchPlan().nodes.len);840}841842test "failed compiled fragment init leaves artifact ownership with caller" {843    const allocator = std.testing.allocator;844845    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{846        .backend_kind = .cuda,847        .artifact_format = .cuda_ptx,848        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,849    });850    var plan_owned = true;851    errdefer if (plan_owned) artifact_plan.deinit();852853    try appendTestKernel(allocator, &artifact_plan, 0, 2, &.{3});854    try appendTestKernel(allocator, &artifact_plan, 1, 3, &.{2});855856    const artifact_module = try artifact_product.ArtifactJob.init(857        allocator,858        artifact_plan,859    );860    plan_owned = false;861    defer artifact_module.deinit();862863    try std.testing.expectError(864        error.InvalidArtifact,865        CompiledFragment.init(allocator, artifact_module),866    );867}868869test "executable dataflow launch graph records slot dependencies" {870    const allocator = std.testing.allocator;871872    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{873        .backend_kind = .cuda,874        .artifact_format = .cuda_ptx,875        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,876    });877    defer artifact_plan.deinit();878    try appendTestKernel(allocator, &artifact_plan, 0, 2, &.{0});879    try appendTestKernel(allocator, &artifact_plan, 1, 3, &.{2});880881    var graph = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});882    defer graph.deinit();883884    try std.testing.expectEqual(@as(usize, 2), graph.nodes.len);885    try std.testing.expectEqual(@as(usize, 0), graph.nodes[0].kernel_index);886    try std.testing.expectEqual(@as(usize, 1), graph.nodes[1].kernel_index);887    try std.testing.expectEqual(@as(usize, 1), graph.dependencies.len);888    try std.testing.expectEqual(@as(usize, 0), graph.dependencies[0].producer_node_index);889    try std.testing.expectEqual(@as(usize, 1), graph.dependencies[0].consumer_node_index);890    try std.testing.expectEqual(@as(usize, 2), graph.dependencies[0].slot_id);891    try validateLaunchGraph(allocator, &artifact_plan, graph.plan(), false);892}893894test "executable dataflow launch graph links repeated in-place slot updates" {895    const allocator = std.testing.allocator;896897    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{898        .backend_kind = .cuda,899        .artifact_format = .cuda_ptx,900        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,901    });902    defer artifact_plan.deinit();903    try appendTestKernel(allocator, &artifact_plan, 0, 0, &.{0});904    try appendTestKernel(allocator, &artifact_plan, 1, 0, &.{0});905    try appendTestKernel(allocator, &artifact_plan, 2, 1, &.{0});906907    var graph = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});908    defer graph.deinit();909910    try std.testing.expectEqual(@as(usize, 3), graph.nodes.len);911    try std.testing.expectEqual(@as(usize, 0), graph.nodes[0].kernel_index);912    try std.testing.expectEqual(@as(usize, 1), graph.nodes[1].kernel_index);913    try std.testing.expectEqual(@as(usize, 2), graph.nodes[2].kernel_index);914    try std.testing.expectEqual(@as(usize, 2), graph.dependencies.len);915    try std.testing.expectEqual(@as(usize, 0), graph.dependencies[0].producer_node_index);916    try std.testing.expectEqual(@as(usize, 1), graph.dependencies[0].consumer_node_index);917    try std.testing.expectEqual(@as(usize, 0), graph.dependencies[0].slot_id);918    try std.testing.expectEqual(@as(usize, 1), graph.dependencies[1].producer_node_index);919    try std.testing.expectEqual(@as(usize, 2), graph.dependencies[1].consumer_node_index);920    try std.testing.expectEqual(@as(usize, 0), graph.dependencies[1].slot_id);921    try validateLaunchGraph(allocator, &artifact_plan, graph.plan(), false);922}923924test "executable dataflow launch graph orders producers before consumers" {925    const allocator = std.testing.allocator;926927    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{928        .backend_kind = .cuda,929        .artifact_format = .cuda_ptx,930        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,931    });932    defer artifact_plan.deinit();933    try appendTestKernel(allocator, &artifact_plan, 0, 3, &.{2});934    try appendTestKernel(allocator, &artifact_plan, 1, 2, &.{0});935936    var graph = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});937    defer graph.deinit();938939    try std.testing.expectEqual(@as(usize, 2), graph.nodes.len);940    try std.testing.expectEqual(@as(usize, 1), graph.nodes[0].kernel_index);941    try std.testing.expectEqual(@as(usize, 0), graph.nodes[1].kernel_index);942    try std.testing.expectEqual(@as(usize, 1), graph.dependencies.len);943    try std.testing.expectEqual(@as(usize, 0), graph.dependencies[0].producer_node_index);944    try std.testing.expectEqual(@as(usize, 1), graph.dependencies[0].consumer_node_index);945    try std.testing.expectEqual(@as(usize, 2), graph.dependencies[0].slot_id);946    try validateLaunchGraph(allocator, &artifact_plan, graph.plan(), false);947}948949test "executable launch graph fingerprint includes schedule order" {950    const first_nodes = [_]LaunchGraphNode{951        .{ .kernel_index = 0 },952        .{ .kernel_index = 1 },953    };954    const second_nodes = [_]LaunchGraphNode{955        .{ .kernel_index = 1 },956        .{ .kernel_index = 0 },957    };958    const dependencies = [_]LaunchGraphDependency{.{959        .producer_node_index = 0,960        .consumer_node_index = 1,961        .slot_id = 2,962    }};963964    try std.testing.expect(launchGraphFingerprint(.{965        .nodes = &first_nodes,966        .dependencies = &dependencies,967    }) != launchGraphFingerprint(.{968        .nodes = &second_nodes,969        .dependencies = &dependencies,970    }));971}972973test "executable launch graph fingerprint includes loop structure" {974    const nodes = [_]LaunchGraphNode{975        .{ .kernel_index = 0 },976        .{ .kernel_index = 1 },977    };978    const carry = [_]LaunchGraphLoopCarry{.{979        .initial_slot_id = 0,980        .input_slot_id = 0,981        .output_slot_id = 2,982        .final_slot_id = 0,983    }};984    const first_loops = [_]LaunchGraphLoop{.{985        .first_node_index = 0,986        .node_count = 2,987        .trip_count = 4,988        .carries = &carry,989    }};990    const second_loops = [_]LaunchGraphLoop{.{991        .first_node_index = 0,992        .node_count = 2,993        .trip_count = 5,994        .carries = &carry,995    }};996997    try std.testing.expect(launchGraphFingerprint(.{998        .nodes = &nodes,999        .loops = &first_loops,1000    }) != launchGraphFingerprint(.{1001        .nodes = &nodes,1002        .loops = &second_loops,1003    }));1004}10051006test "executable launch graph validates loop carry body slots" {1007    const allocator = std.testing.allocator;10081009    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{1010        .backend_kind = .cuda,1011        .artifact_format = .cuda_ptx,1012        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,1013    });1014    defer artifact_plan.deinit();1015    try appendTestKernel(allocator, &artifact_plan, 0, 1, &.{0});1016    try appendTestKernel(allocator, &artifact_plan, 1, 2, &.{1});10171018    var graph = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});1019    defer graph.deinit();10201021    const carry = [_]LaunchGraphLoopCarry{.{1022        .initial_slot_id = 0,1023        .input_slot_id = 0,1024        .output_slot_id = 2,1025        .final_slot_id = 0,1026    }};1027    const loops = [_]LaunchGraphLoop{.{1028        .first_node_index = 0,1029        .node_count = 2,1030        .trip_count = 4,1031        .carries = &carry,1032    }};10331034    try validateLaunchGraph(allocator, &artifact_plan, .{1035        .nodes = graph.nodes,1036        .dependencies = graph.dependencies,1037        .loops = &loops,1038    }, false);1039}10401041test "executable launch graph rejects invalid loop ranges and carries" {1042    const allocator = std.testing.allocator;10431044    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{1045        .backend_kind = .cuda,1046        .artifact_format = .cuda_ptx,1047        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,1048    });1049    defer artifact_plan.deinit();1050    try appendTestKernel(allocator, &artifact_plan, 0, 1, &.{0});1051    try appendTestKernel(allocator, &artifact_plan, 1, 2, &.{1});10521053    var graph = try createDataflowLaunchGraphPlan(allocator, &artifact_plan, .{});1054    defer graph.deinit();10551056    const valid_carry = [_]LaunchGraphLoopCarry{.{1057        .initial_slot_id = 0,1058        .input_slot_id = 0,1059        .output_slot_id = 2,1060        .final_slot_id = 0,1061    }};1062    const missing_input = [_]LaunchGraphLoopCarry{.{1063        .initial_slot_id = 0,1064        .input_slot_id = 99,1065        .output_slot_id = 2,1066        .final_slot_id = 0,1067    }};1068    const missing_output = [_]LaunchGraphLoopCarry{.{1069        .initial_slot_id = 0,1070        .input_slot_id = 0,1071        .output_slot_id = 99,1072        .final_slot_id = 0,1073    }};1074    const bad_final = [_]LaunchGraphLoopCarry{.{1075        .initial_slot_id = 0,1076        .input_slot_id = 0,1077        .output_slot_id = 2,1078        .final_slot_id = 3,1079    }};10801081    const empty_loop = [_]LaunchGraphLoop{.{1082        .first_node_index = 0,1083        .node_count = 0,1084        .trip_count = 4,1085        .carries = &valid_carry,1086    }};1087    try std.testing.expectError(error.InvalidArtifact, validateLaunchGraph(allocator, &artifact_plan, .{1088        .nodes = graph.nodes,1089        .dependencies = graph.dependencies,1090        .loops = &empty_loop,1091    }, false));10921093    const out_of_range = [_]LaunchGraphLoop{.{1094        .first_node_index = 1,1095        .node_count = 2,1096        .trip_count = 4,1097        .carries = &valid_carry,1098    }};1099    try std.testing.expectError(error.InvalidArtifact, validateLaunchGraph(allocator, &artifact_plan, .{1100        .nodes = graph.nodes,1101        .dependencies = graph.dependencies,1102        .loops = &out_of_range,1103    }, false));11041105    const bad_input = [_]LaunchGraphLoop{.{1106        .first_node_index = 0,1107        .node_count = 2,1108        .trip_count = 4,1109        .carries = &missing_input,1110    }};1111    try std.testing.expectError(error.InvalidArtifact, validateLaunchGraph(allocator, &artifact_plan, .{1112        .nodes = graph.nodes,1113        .dependencies = graph.dependencies,1114        .loops = &bad_input,1115    }, false));11161117    const bad_output = [_]LaunchGraphLoop{.{1118        .first_node_index = 0,1119        .node_count = 2,1120        .trip_count = 4,1121        .carries = &missing_output,1122    }};1123    try std.testing.expectError(error.InvalidArtifact, validateLaunchGraph(allocator, &artifact_plan, .{1124        .nodes = graph.nodes,1125        .dependencies = graph.dependencies,1126        .loops = &bad_output,1127    }, false));11281129    const invalid_final = [_]LaunchGraphLoop{.{1130        .first_node_index = 0,1131        .node_count = 2,1132        .trip_count = 4,1133        .carries = &bad_final,1134    }};1135    try std.testing.expectError(error.InvalidArtifact, validateLaunchGraph(allocator, &artifact_plan, .{1136        .nodes = graph.nodes,1137        .dependencies = graph.dependencies,1138        .loops = &invalid_final,1139    }, false));1140}11411142test "executable launch graph rejects missing slot dependencies" {1143    const allocator = std.testing.allocator;11441145    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{1146        .backend_kind = .cuda,1147        .artifact_format = .cuda_ptx,1148        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,1149    });1150    defer artifact_plan.deinit();1151    try appendTestKernel(allocator, &artifact_plan, 0, 2, &.{0});1152    try appendTestKernel(allocator, &artifact_plan, 1, 3, &.{2});11531154    const nodes = [_]LaunchGraphNode{1155        .{ .kernel_index = 0 },1156        .{ .kernel_index = 1 },1157    };11581159    try std.testing.expectError(1160        error.InvalidArtifact,1161        validateLaunchGraph(allocator, &artifact_plan, .{ .nodes = &nodes }, false),1162    );1163}11641165test "executable launch graph rejects duplicate slot dependencies" {1166    const allocator = std.testing.allocator;11671168    var artifact_plan = artifact_product.BackendArtifactPlan.init(allocator, .{1169        .backend_kind = .cuda,1170        .artifact_format = .cuda_ptx,1171        .dtype_bits = gpu.DTypeSet.init(&.{.f32}).bits,1172    });1173    defer artifact_plan.deinit();1174    try appendTestKernel(allocator, &artifact_plan, 0, 2, &.{0});1175    try appendTestKernel(allocator, &artifact_plan, 1, 3, &.{2});11761177    const nodes = [_]LaunchGraphNode{1178        .{ .kernel_index = 0 },1179        .{ .kernel_index = 1 },1180    };1181    const dependencies = [_]LaunchGraphDependency{1182        .{1183            .producer_node_index = 0,1184            .consumer_node_index = 1,1185            .slot_id = 2,1186        },1187        .{1188            .producer_node_index = 0,1189            .consumer_node_index = 1,1190            .slot_id = 2,1191        },1192    };11931194    try std.testing.expectError(1195        error.InvalidArtifact,1196        validateLaunchGraph(1197            allocator,1198            &artifact_plan,1199            .{1200                .nodes = &nodes,1201                .dependencies = &dependencies,1202            },1203            false,1204        ),1205    );1206}

1pub const plan = @import("plan.zig");