tiny.choir.passes.cse

1pub const Table = struct {2    slots: []CseSlot,3    insertion_slots: []usize,4    insertion_count: *usize,5    log_start: usize,67    pub fn candidates(self: Table, key: u64) CandidateIterator {8        return CandidateIterator.init(self.slots, key);9    }1011    pub fn add(self: Table, key: u64, op: *ir.Operation) error{CapacityExceeded}!void {12        if (self.insertion_count.* >= self.insertion_slots.len) {13            return error.CapacityExceeded;14        }15        if (self.slots.len == 0) return error.CapacityExceeded;16        var index = cseSlotIndex(key, self.slots.len);17        var remaining = self.slots.len;18        while (remaining > 0) : (remaining -= 1) {19            const slot = &self.slots[index];20            if (slot.op == null) {21                slot.* = .{22                    .key = key,23                    .op = op,24                };25                self.insertion_slots[self.insertion_count.*] = index;26                self.insertion_count.* += 1;27                return;28            }29            index = (index + 1) & (self.slots.len - 1);30        }31        return error.CapacityExceeded;32    }3334    fn clear(self: *Table) void {35        std.debug.assert(self.insertion_count.* >= self.log_start);36        while (self.insertion_count.* > self.log_start) {37            self.insertion_count.* -= 1;38            const index = self.insertion_slots[self.insertion_count.*];39            std.debug.assert(self.slots[index].op != null);40            self.slots[index] = .{};41        }42    }43};

1pub const Workspace = struct {2    pub const claim: alloc_phase.capacity.Declaration = .{3        .source = .{4            .id = "choir.cse_workspace",5            .kind = .phase_static,6            .limit_source = .caller,7            .storage = .{8                .covered = &.{9                    .{10                        .id = "effect_records_bounded_by_declared_contract_capacity",11                        .lifetime = .steady,12                        .detail = "reused fact buffer bounded by arity-derived contract capacity",13                    },14                    .{15                        .id = "scoped_cse_hash_slots_bounded_by_peak_active_candidate_shapes",16                        .lifetime = .steady,17                        .detail = "scoped CSE hash slots bounded by peak active candidate shapes",18                    },19                    .{20                        .id = "lifo_insertion_indices_bounded_by_peak_active_candidate_shapes",21                        .lifetime = .steady,22                        .detail = "LIFO insertion indices bounded by peak active candidate shapes",23                    },24                },25                .excluded = &.{26                    "borrowed IR and dominance analysis",27                },28            },29            .capacity = .{30                .inputs = &.{31                    alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),32                    alloc_phase.capacity.bindInput(Limits, "facts_peak_candidate_count", "facts.peak_candidate_count"),33                    alloc_phase.capacity.bindInput(34                        Limits,35                        "facts_peak_effect_records",36                        "facts.peak_effect_records",37                    ),38                },39                .type_selectors = &.{},40                .nodes = &.{41                    .{ .input = 0 },42                    .{ .input = 1 },43                    .{ .add = .{ .left = 0, .right = 1 } },44                    .{ .input = 2 },45                    .{ .add = .{ .left = 2, .right = 3 } },46                },47                .assertions = &.{.{48                    .scope = .closure_total,49                    .measure = .retained,50                    .relation = .upper_bound,51                    .expression = 4,52                }},53            },54            .overload = .{55                .kind = .reject_before_seal,56                .detail = "nesting, count arithmetic, capacity arithmetic, or fallback OOM rejects before CSE traversal",57            },58            .risks = .{59                .transitive = .{60                    .status = .witnessed,61                    .detail = "CSE equivalence, result remapping, duplicate erasure, and scoped table mutation use only admitted storage after activation",62                },63                .foreign = .{64                    .status = .open,65                    .detail = "the workspace has no visible foreign edge, but foreign-edge closure lacks a machine-checked certificate",66                },67            },68            .obligations = &.{69                .{ .key = "cse_inline_boundary", .role = .overload },70                .{ .key = "cse_capacity", .role = .capacity_model },71                .{ .key = "cse_sealed_reuse_overload", .role = .overload },72                .{ .key = "cse_sealed_reuse_foreign_risk", .role = .foreign_risk },73                .{ .key = "cse_oom_retry", .role = .overload },74                .{ .key = "cse_steady_no_alloc", .role = .transitive_risk },75            },76        },77        .bindings = .{78            .owner = @This(),79            .seal = .{80                .family = alloc_phase.capacity.selector(@This().activate),81                .premise = .{82                    .class = .checked_semantic_fact,83                    .authority = .checker,84                },85            },86            .teardown = .{87                .family = alloc_phase.capacity.selector(@This().deinit),88                .premise = .{89                    .class = .checked_semantic_fact,90                    .authority = .checker,91                },92            },93        },94    };9596    phase: alloc_phase.capacity.Phase,97    capacity: CseCapacity,98    bytes: []align(cse_storage_alignment) u8,99    slots: []CseSlot,100    insertion_slots: []usize,101    effect_records: []effects.Fact,102    insertion_count: usize,103    active_scope_count: usize,104105    pub const Limits = CseLimits;106    pub const Capacity = CseCapacity;107108    pub fn initForRoot(allocator: Allocator, root: *ir.Operation) !Workspace {109        return init(allocator, try Limits.inspect(root));110    }111112    pub fn init(allocator: Allocator, limits: Limits) !Workspace {113        const capacity = try Capacity.derive(limits);114        const bytes = try allocator.alignedAlloc(115            u8,116            .fromByteUnits(cse_storage_alignment),117            capacity.working_bytes,118        );119        const slots = cseTypedSlice(120            CseSlot,121            bytes,122            0,123            capacity.slot_count,124        );125        @memset(slots, .{});126        return .{127            .phase = .initialization,128            .capacity = capacity,129            .bytes = bytes,130            .slots = slots,131            .insertion_slots = cseTypedSlice(132                usize,133                bytes,134                capacity.insertion_offset,135                capacity.facts.peak_candidate_count,136            ),137            .insertion_count = 0,138            .active_scope_count = 0,139            .effect_records = cseTypedSlice(140                effects.Fact,141                bytes,142                capacity.effect_offset,143                capacity.facts.peak_effect_records,144            ),145        };146    }147148    pub fn activate(self: *Workspace) error{AlreadyActive}!void {149        if (self.phase != .initialization) return error.AlreadyActive;150        self.phase = .steady;151    }152153    pub fn requiresDominance(self: *const Workspace) bool {154        if (self.phase != .initialization) {155            @panic("CSE dominance admission checked outside initialization");156        }157        return self.capacity.facts.requires_dominance;158    }159160    pub fn acquire(self: *Workspace) Table {161        self.requireSteady();162        self.active_scope_count = std.math.add(163            usize,164            self.active_scope_count,165            1,166        ) catch @panic("CSE active scope count overflow after activation");167        return .{168            .slots = self.slots,169            .insertion_slots = self.insertion_slots,170            .insertion_count = &self.insertion_count,171            .log_start = self.insertion_count,172        };173    }174175    pub fn release(self: *Workspace, table: Table) void {176        self.requireSteady();177        std.debug.assert(table.slots.ptr == self.slots.ptr);178        std.debug.assert(table.insertion_slots.ptr == self.insertion_slots.ptr);179        std.debug.assert(table.insertion_count == &self.insertion_count);180        var scope = table;181        scope.clear();182        std.debug.assert(self.active_scope_count > 0);183        self.active_scope_count -= 1;184    }185186    pub fn deinit(self: *Workspace, allocator: Allocator) void {187        if (self.phase == .teardown) @panic("CSE workspace teardown is terminal");188        std.debug.assert(self.insertion_count == 0);189        std.debug.assert(self.active_scope_count == 0);190        self.phase = .teardown;191        allocator.free(self.bytes);192        self.bytes = undefined;193        self.slots = undefined;194        self.insertion_slots = undefined;195        self.insertion_count = undefined;196        self.active_scope_count = undefined;197    }198199    fn requireSteady(self: *const Workspace) void {200        if (self.phase != .steady) {201            @panic("CSE workspace used outside its steady phase");202        }203    }204};

1pub const common_subexpression_elimination_pass_description =2    "Common subexpression elimination for pure operations";

1pub const common_subexpression_elimination_pass_name = "choir-cse";

1pub const common_subexpression_elimination_pass_registration = registry_mod.PassRegistration{2    .name = common_subexpression_elimination_pass_name,3    .description = common_subexpression_elimination_pass_description,4    .pass = createCommonSubexpressionEliminationPass(),5};

1pub fn createCommonSubexpressionEliminationPass() Pass {2    return .{3        .name = common_subexpression_elimination_pass_name,4        .description = common_subexpression_elimination_pass_description,5        .run_fn = run,6        .mutation_scope = .isolated,7        .rerun_policy = .skip_if_unchanged,8    };9}

1pub fn run(ctx: *PassContext) PassResult {2    var stack_buffer: [cse.inline_workspace_bytes]u8 = undefined;3    var stack_fallback = alloc_observe.buffer.First.init(&stack_buffer, ctx.allocator);4    const workspace_allocator = stack_fallback.allocator();5    var workspace = Workspace.initForRoot(workspace_allocator, ctx.op) catch6        return .failure;7    defer workspace.deinit(workspace_allocator);8    const dominance: ?*const control_flow.DominanceAnalysis = if (workspace.requiresDominance())9        control_flow.getDominanceAnalysis(ctx, ctx.op) catch return .failure10    else11        null;12    workspace.activate() catch return .failure;1314    var modified = false;15    var replacements: u64 = 0;16    cseOnOp(17        ctx.op,18        dominance,19        &workspace,20        &modified,21        &replacements,22    );23    std.debug.assert(workspace.insertion_count == 0);24    std.debug.assert(workspace.active_scope_count == 0);2526    if (replacements != 0) {27        ctx.addStatistic("replacements", "redundant operations replaced", replacements);28    }2930    if (modified) {31        ctx.preserveAnalysisSet(control_flow.analysis_ids);32        ctx.markModified();33    } else {34        ctx.preserveAllAnalyses();35    }36    return .success;37}

1pub fn hasCandidateShape(op: *ir.Operation) bool {2    return op.regions.items.len == 0 and3        op.successors.items.len == 0 and4        op.result_types.len != 0;5}

1pub const inline_workspace_bytes: usize = 8 * 1024;

1const implementation = @import("pass.zig");2const storage = @import("storage.zig");34pub const common_subexpression_elimination_pass_name =5    implementation.common_subexpression_elimination_pass_name;6pub const common_subexpression_elimination_pass_description =7    implementation.common_subexpression_elimination_pass_description;8pub const common_subexpression_elimination_pass_registration =9    implementation.common_subexpression_elimination_pass_registration;10pub const createCommonSubexpressionEliminationPass =11    implementation.createCommonSubexpressionEliminationPass;12pub const run = implementation.run;13pub const hasCandidateShape = storage.hasCandidateShape;14pub const inline_workspace_bytes = storage.inline_workspace_bytes;15pub const Table = storage.Table;16pub const Workspace = storage.Workspace;

1pub const cse = @import("cse/root.zig");