tiny.choir.ir.rewrite

1pub const PatternIndex = struct {2    pub const claim: alloc_phase.capacity.Declaration = .{3        .source = .{4            .id = "choir.rewrite_pattern_index",5            .kind = .phase_static,6            .limit_source = .caller,7            .storage = .{8                .covered = &.{9                    .{10                        .id = "load_bounded_rewrite_root_slots_and_exact_sealed_pattern_groups",11                        .lifetime = .steady,12                        .detail = "load-bounded rewrite-root slots and exact sealed pattern groups",13                    },14                },15                .excluded = &.{16                    "geometrically grown rewrite-pattern builder storage",17                    "borrowed root names, rewrite callbacks, IR, and pattern-rewriter state",18                },19            },20            .capacity = .{21                .inputs = &.{22                    alloc_phase.capacity.bindInput(Limits, "patterns", "patterns"),23                },24                .type_selectors = &.{25                    alloc_phase.capacity.bindType(PatternRootSlot, "rootslot"),26                    alloc_phase.capacity.bindType(RewritePattern, "rewritepattern"),27                },28                .nodes = &.{29                    .{ .collection = .{ .length = 0 } },30                    .{ .constant = 2 },31                    .{ .scale = .{ .node = 1, .coefficient = .{ .size_of_concrete_type = 0 } } },32                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 1 } } },33                    .{ .add = .{ .left = 2, .right = 3 } },34                },35                .assertions = &.{.{36                    .scope = .closure_total,37                    .measure = .retained,38                    .relation = .exact,39                    .expression = 4,40                }},41            },42            .overload = .{43                .kind = .reject_before_seal,44                .detail = "pattern-count, unique-root count, placement arithmetic, or OOM failure leaves the pattern set unsealed and retryable",45            },46            .risks = .{47                .transitive = .{48                    .status = .open,49                    .detail = "benefit sorting and root-name hashing use standard-library helpers without a transitive allocation-closure certificate",50                },51                .foreign = .{52                    .status = .excluded,53                    .detail = "pattern indexing is process-local and invokes no callback or operating-system boundary",54                },55            },56            .obligations = &.{57                .{ .key = "pattern_index_capacity", .role = .capacity_model },58                .{ .key = "pattern_index_sealed_reuse_overload", .role = .overload },59                .{ .key = "pattern_index_sealed_reuse_transitive_risk", .role = .transitive_risk },60                .{ .key = "pattern_index_sealed_reuse_foreign_risk", .role = .foreign_risk },61                .{ .key = "pattern_index_oom_retry", .role = .overload },62            },63        },64        .bindings = .{65            .owner = @This(),66            .seal = .{67                .family = alloc_phase.capacity.selector(@This().activate),68                .premise = .{69                    .class = .checked_semantic_fact,70                    .authority = .checker,71                },72            },73            .teardown = .{74                .family = alloc_phase.capacity.selector(@This().deinit),75                .premise = .{76                    .class = .checked_semantic_fact,77                    .authority = .checker,78                },79            },80        },81    };8283    phase: alloc_phase.capacity.Phase,84    capacity: PatternIndexCapacity,85    source_patterns: ?[]const RewritePattern,86    bytes: []align(pattern_index_alignment) u8,87    slots: []PatternRootSlot,88    grouped_patterns: []RewritePattern,89    root_count: usize,9091    pub const Limits = PatternIndexLimits;92    pub const Capacity = PatternIndexCapacity;9394    pub fn init(allocator: std.mem.Allocator, limits: PatternIndexLimits) !PatternIndex {95        const capacity = try PatternIndexCapacity.derive(limits);96        const bytes = try allocator.alignedAlloc(97            u8,98            .fromByteUnits(pattern_index_alignment),99            capacity.working_bytes,100        );101        errdefer allocator.free(bytes);102        const slots = patternIndexSlice(103            PatternRootSlot,104            bytes,105            capacity.slots_offset,106            capacity.slot_count,107        );108        @memset(slots, .{});109        const grouped_patterns = patternIndexSlice(110            RewritePattern,111            bytes,112            capacity.patterns_offset,113            capacity.facts.pattern_count,114        );115116        var root_count: usize = 0;117        for (limits.patterns) |pattern| {118            const insertion = getOrInsertPatternRoot(slots, pattern.spec.root_op_name);119            root_count += @intFromBool(insertion.inserted);120            slots[insertion.index].len = std.math.add(121                PatternOrdinal,122                slots[insertion.index].len,123                1,124            ) catch unreachable;125        }126        setPatternRootStarts(slots, grouped_patterns.len);127        var source_index = limits.patterns.len;128        while (source_index > 0) {129            source_index -= 1;130            const pattern = limits.patterns[source_index];131            const slot_index = findPatternRootSlotIndex(132                slots,133                pattern.spec.root_op_name,134            ).?;135            std.debug.assert(slots[slot_index].len > 0);136            slots[slot_index].len -= 1;137            const grouped_index = @as(usize, slots[slot_index].start) +138                @as(usize, slots[slot_index].len);139            std.debug.assert(grouped_index < grouped_patterns.len);140            grouped_patterns[grouped_index] = pattern;141        }142        restorePatternRootLengths(slots, grouped_patterns.len);143144        const index = PatternIndex{145            .phase = .initialization,146            .capacity = capacity,147            .source_patterns = limits.patterns,148            .bytes = bytes,149            .slots = slots,150            .grouped_patterns = grouped_patterns,151            .root_count = root_count,152        };153        index.assertInvariant();154        return index;155    }156157    pub fn activate(self: *PatternIndex) error{ AlreadyActive, InputChanged }!void {158        if (self.phase != .initialization) return error.AlreadyActive;159        if (self.source_patterns == null) return error.InputChanged;160        self.source_patterns = null;161        self.phase = .steady;162        self.assertInvariant();163    }164165    pub fn deinit(self: *PatternIndex, allocator: std.mem.Allocator) void {166        if (self.phase == .teardown) @panic("rewrite pattern index teardown is terminal");167        self.assertInvariant();168        self.phase = .teardown;169        allocator.free(self.bytes);170        self.source_patterns = undefined;171        self.bytes = undefined;172        self.slots = undefined;173        self.grouped_patterns = undefined;174        self.root_count = undefined;175    }176177    pub fn matching(self: *const PatternIndex, root_name: []const u8) []const RewritePattern {178        self.requireSteady();179        std.debug.assert(self.grouped_patterns.len == self.capacity.facts.pattern_count);180        std.debug.assert(self.slots.len == self.capacity.slot_count);181        const range = self.findRoot(root_name) orelse return &.{};182        const start: usize = @intCast(range.start);183        const len: usize = @intCast(range.len);184        std.debug.assert(start <= self.grouped_patterns.len);185        std.debug.assert(len <= self.grouped_patterns.len - start);186        return self.grouped_patterns[start..][0..len];187    }188189    fn findRoot(self: *const PatternIndex, root_name: []const u8) ?PatternRootSlot {190        const slot_index = findPatternRootSlotIndex(self.slots, root_name) orelse191            return null;192        return self.slots[slot_index];193    }194195    fn requireSteady(self: *const PatternIndex) void {196        if (self.phase != .steady) @panic("rewrite pattern index is not active");197    }198199    fn assertInvariant(self: *const PatternIndex) void {200        std.debug.assert(self.phase != .teardown);201        std.debug.assert(self.bytes.len == self.capacity.working_bytes);202        if (self.phase == .initialization) {203            std.debug.assert(self.source_patterns != null);204            std.debug.assert(self.source_patterns.?.len == self.capacity.facts.pattern_count);205        } else {206            std.debug.assert(self.source_patterns == null);207        }208        std.debug.assert(self.slots.len == self.capacity.slot_count);209        std.debug.assert(self.grouped_patterns.len == self.capacity.facts.pattern_count);210        var root_count: usize = 0;211        var pattern_count: usize = 0;212        for (self.slots) |slot| {213            const name = slot.name orelse continue;214            root_count += 1;215            std.debug.assert(slot.len > 0);216            const start: usize = @intCast(slot.start);217            const len: usize = @intCast(slot.len);218            std.debug.assert(start <= self.grouped_patterns.len);219            std.debug.assert(len <= self.grouped_patterns.len - start);220            pattern_count = std.math.add(usize, pattern_count, len) catch unreachable;221            std.debug.assert(pattern_count <= self.grouped_patterns.len);222            const found = self.findRoot(name).?;223            std.debug.assert(found.start == slot.start);224            std.debug.assert(found.len == slot.len);225        }226        std.debug.assert(root_count == self.root_count);227        std.debug.assert(pattern_count == self.grouped_patterns.len);228        for (self.grouped_patterns, 0..) |_, pattern_index| {229            var containing_ranges: usize = 0;230            for (self.slots) |slot| {231                if (slot.name == null) continue;232                const start: usize = @intCast(slot.start);233                const len: usize = @intCast(slot.len);234                if (pattern_index >= start and pattern_index - start < len) {235                    containing_ranges += 1;236                }237            }238            std.debug.assert(containing_ranges == 1);239        }240    }241242    fn matchesPatterns(self: *const PatternIndex) bool {243        if (self.grouped_patterns.len != self.capacity.facts.pattern_count) return false;244        for (self.slots) |slot| {245            const root_name = slot.name orelse continue;246            const start: usize = @intCast(slot.start);247            const len: usize = @intCast(slot.len);248            for (self.grouped_patterns[start..][0..len], 0..) |pattern, group_index| {249                if (!std.mem.eql(250                    u8,251                    root_name,252                    pattern.spec.root_op_name,253                )) return false;254                if (group_index > 0 and RewritePattern.lessThan(255                    {},256                    pattern,257                    self.grouped_patterns[start + group_index - 1],258                )) return false;259            }260        }261        return true;262    }263};

1pub const PatternResult = enum {2    success,3    failure,4};

1pub const RewritePattern = struct {2    spec: RewritePatternSpec,34    rewrite_fn: *const fn (5        op: *ir.Operation,6        rewriter: *PatternRewriter,7    ) PatternResult,89    match_fn: ?*const fn (op: *ir.Operation) bool,1011    order: usize,1213    pub fn init(14        spec: RewritePatternSpec,15        rewrite_fn: *const fn (*ir.Operation, *PatternRewriter) PatternResult,16    ) RewritePattern {17        return .{18            .spec = spec,19            .rewrite_fn = rewrite_fn,20            .match_fn = null,21            .order = 0,22        };23    }2425    pub fn initWithMatch(26        spec: RewritePatternSpec,27        match_fn: *const fn (*ir.Operation) bool,28        rewrite_fn: *const fn (*ir.Operation, *PatternRewriter) PatternResult,29    ) RewritePattern {30        return .{31            .spec = spec,32            .rewrite_fn = rewrite_fn,33            .match_fn = match_fn,34            .order = 0,35        };36    }3738    pub fn matches(self: *const RewritePattern, op: *ir.Operation) bool {39        if (!std.mem.eql(u8, op.name.name, self.spec.root_op_name)) {40            return false;41        }42        return self.matchesAfterRoot(op);43    }4445    pub fn matchesAfterRoot(self: *const RewritePattern, op: *ir.Operation) bool {46        if (self.match_fn) |match| {47            return match(op);48        }49        return true;50    }5152    pub fn apply(self: *const RewritePattern, op: *ir.Operation, rewriter: *PatternRewriter) PatternResult {53        return self.rewrite_fn(op, rewriter);54    }5556    pub fn matchAndRewrite(self: *const RewritePattern, op: *ir.Operation, rewriter: *PatternRewriter) PatternResult {57        if (!self.matches(op)) return .failure;58        return self.apply(op, rewriter);59    }6061    pub fn lessThan(_: void, a: RewritePattern, b: RewritePattern) bool {62        if (a.spec.benefit != b.spec.benefit) return a.spec.benefit > b.spec.benefit;63        return a.order < b.order;64    }65};

1pub const RewritePatternKind = enum {2    rewrite,3    fold,4};

1pub const RewritePatternProducts = union(enum) {2    unknown,3    none,4    operations: []const []const u8,5};

1pub const RewritePatternSpec = struct {2    name: []const u8,3    root_op_name: []const u8,4    benefit: PatternBenefit = 1,5    kind: RewritePatternKind = .rewrite,6    products: RewritePatternProducts = .unknown,7};

1pub const PatternRewriteAttempt = struct {2    rewriter: *PatternRewriter,3    created_before: usize,4    guard: PatternRewriter.InsertionGuard,56    pub inline fn init(op: *ir.Operation, rewriter: *PatternRewriter) PatternRewriteAttempt {7        const attempt = PatternRewriteAttempt{8            .rewriter = rewriter,9            .created_before = rewriter.created_ops.items.len,10            .guard = rewriter.insertionGuard(),11        };12        rewriter.setInsertionPointBefore(op);13        return attempt;14    }1516    pub inline fn finish(self: *PatternRewriteAttempt, result: PatternResult) bool {17        if (result == .failure and self.rewriter.created_ops.items.len != self.created_before) {18            self.rewriter.created_ops.items.len = self.created_before;19        }20        self.guard.deinit();21        self.* = undefined;22        return result == .success;23    }24};

1pub const PatternRewriter = struct {2    pub const ReplacementMode = enum {3        immediate,4        deferred,5    };67    allocator: std.mem.Allocator,8    ir_ctx: *ir.Context,9    type_converter: ?*const TypeConverter,10    replacement_mode: ReplacementMode,1112    created_ops: std.ArrayListUnmanaged(*ir.Operation),1314    ops_to_erase: std.ArrayListUnmanaged(*ir.Operation),1516    replacements: std.AutoHashMap(*ir.Value, *ir.Value),1718    builder: ir.OperationBuilder,1920    listener: ?Listener,2122    pub const InsertPoint: type = ir.OperationBuilder.InsertPoint;23    pub const InsertionGuard: type = ir.OperationBuilder.InsertionGuard;2425    pub const OperationReplacement = struct {26        op: *ir.Operation,27        new_values: []const *ir.Value,28    };2930    pub const DetachedOperation = struct {31        op: *ir.Operation,32        block: *ir.Block,33        next: ?*ir.Operation,34    };3536    pub const RewriteEvent = union(enum) {37        modified: *ir.Operation,38        replaced: OperationReplacement,39        erased: *ir.Operation,40    };4142    pub const Listener = struct {43        context: ?*anyopaque = null,44        notify_event: ?*const fn (?*anyopaque, RewriteEvent) void = null,4546        pub fn bind(target: anytype) Listener {47            const TargetPtr = @TypeOf(target);48            comptime {49                const pointer_info = switch (@typeInfo(TargetPtr)) {50                    .pointer => |info| info,51                    else => @compileError("PatternRewriter.Listener.bind expects a mutable pointer"),52                };53                if (pointer_info.size != .one) {54                    @compileError("PatternRewriter.Listener.bind expects a single-item pointer");55                }56                if (pointer_info.attrs.@"const") {57                    @compileError("PatternRewriter.Listener.bind expects a mutable pointer");58                }59                if (!@hasDecl(pointer_info.child, "notifyRewriteEvent")) {60                    @compileError("PatternRewriter listener target must define notifyRewriteEvent");61                }62            }6364            return .{65                .context = target,66                .notify_event = rewrite_listener_target(TargetPtr).notify_event,67            };68        }6970        pub fn notify(self: Listener, event: RewriteEvent) void {71            if (self.notify_event) |notify_event| notify_event(self.context, event);72        }73    };7475    pub fn init(allocator: std.mem.Allocator, ir_ctx: *ir.Context) PatternRewriter {76        return initWithMode(allocator, ir_ctx, .immediate);77    }7879    pub fn initDeferred(allocator: std.mem.Allocator, ir_ctx: *ir.Context) PatternRewriter {80        return initWithMode(allocator, ir_ctx, .deferred);81    }8283    fn initWithMode(84        allocator: std.mem.Allocator,85        ir_ctx: *ir.Context,86        replacement_mode: ReplacementMode,87    ) PatternRewriter {88        return .{89            .allocator = allocator,90            .ir_ctx = ir_ctx,91            .type_converter = null,92            .replacement_mode = replacement_mode,93            .created_ops = .empty,94            .ops_to_erase = .empty,95            .replacements = std.AutoHashMap(*ir.Value, *ir.Value).init(allocator),96            .builder = ir.OperationBuilder.init(ir_ctx),97            .listener = null,98        };99    }100101    pub fn initWithTypeConverter(102        allocator: std.mem.Allocator,103        ir_ctx: *ir.Context,104        type_converter: ?*const TypeConverter,105    ) PatternRewriter {106        var rewriter = PatternRewriter.init(allocator, ir_ctx);107        rewriter.type_converter = type_converter;108        return rewriter;109    }110111    pub fn deinit(self: *PatternRewriter) void {112        self.created_ops.deinit(self.allocator);113        self.ops_to_erase.deinit(self.allocator);114        self.replacements.deinit();115    }116117    pub fn setTypeConverter(self: *PatternRewriter, type_converter: ?*const TypeConverter) void {118        self.type_converter = type_converter;119    }120121    pub fn getTypeConverter(self: *const PatternRewriter) ?*const TypeConverter {122        return self.type_converter;123    }124125    pub fn setListener(self: *PatternRewriter, listener: ?Listener) void {126        self.listener = listener;127    }128129    pub fn getListener(self: *const PatternRewriter) ?Listener {130        return self.listener;131    }132133    pub fn materializeConversion(self: *PatternRewriter, value: *ir.Value, target_type: ir.Type) ?*ir.Value {134        const converter = self.type_converter orelse return null;135        return converter.materialize(self, value, target_type);136    }137138    pub fn clearInsertionPoint(self: *PatternRewriter) void {139        self.builder.clearInsertionPoint();140    }141142    pub fn hasInsertionPoint(self: *const PatternRewriter) bool {143        return self.builder.hasInsertionPoint();144    }145146    pub fn saveInsertionPoint(self: *const PatternRewriter) InsertPoint {147        return self.builder.saveInsertionPoint();148    }149150    pub fn restoreInsertionPoint(self: *PatternRewriter, insert_point: InsertPoint) void {151        self.builder.restoreInsertionPoint(insert_point);152    }153154    pub fn insertionGuard(self: *PatternRewriter) InsertionGuard {155        return self.builder.insertionGuard();156    }157158    pub fn setInsertionPoint(self: *PatternRewriter, block: *ir.Block) void {159        self.builder.setInsertionPoint(block);160    }161162    pub fn setInsertionPointBefore(self: *PatternRewriter, op: *ir.Operation) void {163        self.builder.setInsertionPointBefore(op);164    }165166    pub fn setInsertionPointAfter(self: *PatternRewriter, op: *ir.Operation) void {167        self.builder.setInsertionPointAfter(op);168    }169170    fn ensureBuilderListener(self: *PatternRewriter) void {171        self.builder.setListener(.{172            .context = self,173            .notify_operation_inserted = recordInsertedOperation,174        });175    }176177    fn recordInsertedOperation(context: ?*anyopaque, op: *ir.Operation, previous: ir.OperationBuilder.InsertPoint) !void {178        _ = previous;179        const self: *PatternRewriter = @ptrCast(@alignCast(context.?));180        try self.created_ops.append(self.allocator, op);181    }182183    pub fn insert(self: *PatternRewriter, op: *ir.Operation) !*ir.Operation {184        self.ensureBuilderListener();185        return try self.builder.insert(op);186    }187188    pub fn create(self: *PatternRewriter, state: ir.Operation.State) !*ir.Operation {189        self.ensureBuilderListener();190        return try self.builder.create(state);191    }192193    fn notifyRewriteEvent(self: *const PatternRewriter, event: RewriteEvent) void {194        if (self.listener) |listener| listener.notify(event);195    }196197    fn replaceUsesImmediately(self: *PatternRewriter, old_value: *ir.Value, new_value: *ir.Value) void {198        if (old_value == new_value) return;199        var uses = old_value.useIterator();200        while (uses.next()) |operand| {201            operand.setValue(new_value);202            const owner: *ir.Operation = @ptrCast(@alignCast(operand.owner));203            self.notifyRewriteEvent(.{ .modified = owner });204        }205    }206207    fn ensureReplacementCapacity(self: *PatternRewriter, count: usize) !void {208        if (self.replacement_mode == .deferred) {209            try self.replacements.ensureUnusedCapacity(@intCast(count));210        }211    }212213    fn ensureEraseCapacity(self: *PatternRewriter) !void {214        try self.ops_to_erase.ensureUnusedCapacity(self.allocator, 1);215    }216217    pub fn setOperandValue(self: *PatternRewriter, op: *ir.Operation, index: usize, new_value: *ir.Value) void {218        op.setOperandValue(index, new_value);219        self.notifyRewriteEvent(.{ .modified = op });220    }221222    pub fn setAttr(self: *PatternRewriter, op: *ir.Operation, attr_name: []const u8, value: ir.Attribute) !void {223        try op.setAttr(attr_name, value);224        self.notifyRewriteEvent(.{ .modified = op });225    }226227    pub fn replaceAllUsesWith(self: *PatternRewriter, old_value: *ir.Value, new_value: *ir.Value) !void {228        switch (self.replacement_mode) {229            .immediate => self.replaceUsesImmediately(old_value, new_value),230            .deferred => try self.replacements.put(old_value, new_value),231        }232    }233234    pub fn replaceAllOpUsesWith(self: *PatternRewriter, op: *ir.Operation, new_values: []const *ir.Value) !void {235        if (new_values.len != op.getNumResults()) return error.ReplacementResultCountMismatch;236        try self.ensureReplacementCapacity(new_values.len);237        self.notifyRewriteEvent(.{ .replaced = .{ .op = op, .new_values = new_values } });238        switch (self.replacement_mode) {239            .immediate => for (op.results.items, new_values) |*result, new_value| {240                self.replaceUsesImmediately(result, new_value);241            },242            .deferred => for (op.results.items, new_values) |*result, new_value| {243                self.replacements.putAssumeCapacity(result, new_value);244            },245        }246    }247248    pub fn replaceAllOpUsesWithOperation(self: *PatternRewriter, op: *ir.Operation, replacement: *ir.Operation) !void {249        const result_count = op.getNumResults();250        if (replacement.getNumResults() != result_count) return error.ReplacementResultCountMismatch;251        if (result_count == 0) {252            try self.replaceAllOpUsesWith(op, &.{});253            return;254        }255        if (result_count == 1) {256            const value = replacement.getResult(0) orelse return error.ReplacementResultCountMismatch;257            try self.replaceAllOpUsesWith(op, &.{value});258            return;259        }260261        const values = try self.allocator.alloc(*ir.Value, result_count);262        defer self.allocator.free(values);263        for (values, 0..) |*value, index| {264            value.* = replacement.getResult(index) orelse return error.ReplacementResultCountMismatch;265        }266267        try self.replaceAllOpUsesWith(op, values);268    }269270    pub fn replaceOp(self: *PatternRewriter, op: *ir.Operation, new_values: []const *ir.Value) !void {271        if (new_values.len != op.getNumResults()) return error.ReplacementResultCountMismatch;272        try self.ensureEraseCapacity();273        try self.replaceAllOpUsesWith(op, new_values);274        self.ops_to_erase.appendAssumeCapacity(op);275    }276277    pub fn replaceOpWithOperation(self: *PatternRewriter, op: *ir.Operation, replacement: *ir.Operation) !void {278        if (replacement.getNumResults() != op.getNumResults()) return error.ReplacementResultCountMismatch;279        try self.ensureEraseCapacity();280        try self.replaceAllOpUsesWithOperation(op, replacement);281        self.ops_to_erase.appendAssumeCapacity(op);282    }283284    pub fn replaceOpWithNewOp(self: *PatternRewriter, op: *ir.Operation, state: ir.Operation.State) !*ir.Operation {285        const result_count = op.getNumResults();286        if (state.result_types.len != result_count) return error.ReplacementResultCountMismatch;287        try self.ensureEraseCapacity();288        try self.ensureReplacementCapacity(result_count);289290        const new_op = try self.create(state);291        try self.replaceOpWithOperation(op, new_op);292        return new_op;293    }294295    pub fn replaceOpWithValue(self: *PatternRewriter, op: *ir.Operation, new_value: *ir.Value) !void {296        try self.replaceOp(op, &.{new_value});297    }298299    pub fn eraseOp(self: *PatternRewriter, op: *ir.Operation) !void {300        try self.ops_to_erase.append(self.allocator, op);301    }302303    pub fn isScheduledForErase(self: *const PatternRewriter, op: *const ir.Operation) bool {304        for (self.ops_to_erase.items) |erased_op| {305            if (erased_op == op) return true;306        }307        return false;308    }309310    pub fn getRemappedValue(self: *const PatternRewriter, value: *ir.Value) *ir.Value {311        if (self.replacement_mode == .immediate) return value;312        var current = value;313        while (self.replacements.get(current)) |replacement| {314            current = replacement;315        }316        return current;317    }318319    pub fn finalize(self: *PatternRewriter, root_op: *ir.Operation) void {320        self.applyPendingReplacements(root_op);321322        for (self.ops_to_erase.items) |op| {323            self.notifyRewriteEvent(.{ .erased = op });324            op.erase();325        }326    }327328    pub fn applyPendingReplacements(self: *PatternRewriter, root_op: *ir.Operation) void {329        if (self.replacement_mode == .immediate) return;330        if (self.replacements.count() != 0) self.applyReplacementsToOp(root_op);331    }332333    pub fn detachScheduledOperations(334        self: *PatternRewriter,335        storage: []DetachedOperation,336    ) []DetachedOperation {337        std.debug.assert(storage.len >= self.ops_to_erase.items.len);338        for (self.ops_to_erase.items, 0..) |op, index| {339            const block = op.getBlock() orelse @panic("scheduled erased operation is detached");340            storage[index] = .{341                .op = op,342                .block = block,343                .next = op.next_op,344            };345            self.notifyRewriteEvent(.{ .erased = op });346            block.detachOperation(op);347        }348        return storage[0..self.ops_to_erase.items.len];349    }350351    pub fn restoreDetachedOperations(detached: []const DetachedOperation) void {352        var index = detached.len;353        while (index > 0) {354            index -= 1;355            const entry = detached[index];356            if (entry.next) |next| {357                entry.block.insertBefore(entry.op, next) catch unreachable;358            } else {359                entry.block.addOperation(entry.op) catch unreachable;360            }361        }362    }363364    pub fn destroyDetachedOperations(detached: []const DetachedOperation) void {365        for (detached) |entry| entry.op.dropAllReferences();366        var index = detached.len;367        while (index > 0) {368            index -= 1;369            detached[index].op.erase();370        }371    }372373    pub fn rollbackCreatedOperations(self: *PatternRewriter) void {374        var index = self.created_ops.items.len;375        while (index > 0) {376            index -= 1;377            self.created_ops.items[index].erase();378        }379        self.created_ops.clearRetainingCapacity();380    }381382    fn applyReplacementsToOp(self: *PatternRewriter, op: *ir.Operation) void {383        var context = ReplacementWalk{ .rewriter = self };384        _ = op.walk(.{ .order = .pre_order }, &context, ReplacementWalk.visit) catch unreachable;385    }386};

1pub const RewritePatternSet = struct {2    allocator: std.mem.Allocator,3    patterns: std.ArrayListUnmanaged(RewritePattern),4    index: ?PatternIndex,56    pub fn init(allocator: std.mem.Allocator) RewritePatternSet {7        return .{8            .allocator = allocator,9            .patterns = .empty,10            .index = null,11        };12    }1314    pub fn deinit(self: *RewritePatternSet) void {15        if (self.index) |*index| index.deinit(self.allocator);16        self.patterns.deinit(self.allocator);17        self.* = undefined;18    }1920    pub fn add(self: *RewritePatternSet, pattern: RewritePattern) !void {21        if (self.index != null) return error.PatternSetSealed;22        var ordered = pattern;23        ordered.order = self.patterns.items.len;24        try self.patterns.append(self.allocator, ordered);25    }2627    pub fn ensureUnusedCapacity(self: *RewritePatternSet, additional_count: usize) !void {28        if (self.index != null) return error.PatternSetSealed;29        const required_count = std.math.add(30            usize,31            self.patterns.items.len,32            additional_count,33        ) catch return error.CapacityOverflow;34        try self.patterns.ensureTotalCapacity(self.allocator, required_count);35    }3637    pub fn addPattern(38        self: *RewritePatternSet,39        op_name: []const u8,40        rewrite_fn: *const fn (*ir.Operation, *PatternRewriter) PatternResult,41    ) !void {42        try self.add(RewritePattern.init(.{43            .name = op_name,44            .root_op_name = op_name,45        }, rewrite_fn));46    }4748    pub fn count(self: *const RewritePatternSet) usize {49        if (self.index) |index| return index.capacity.facts.pattern_count;50        return self.patterns.items.len;51    }5253    pub fn seal(self: *RewritePatternSet) !void {54        if (self.index != null) return;55        std.mem.sort(RewritePattern, self.patterns.items, {}, RewritePattern.lessThan);56        const limits = try PatternIndex.Limits.inspect(self.patterns.items);57        var index = try PatternIndex.init(self.allocator, limits);58        errdefer index.deinit(self.allocator);59        try index.activate();60        self.patterns.deinit(self.allocator);61        self.patterns = .empty;62        self.index = index;63    }6465    pub fn getMatchingPatterns(self: *const RewritePatternSet, op: *ir.Operation) []const RewritePattern {66        if (self.index) |*index| {67            return index.matching(op.name.name);68        }69        @panic("rewrite pattern set is not sealed");70    }7172    pub fn applyFirstMatchingPattern(73        self: *const RewritePatternSet,74        op: *ir.Operation,75        rewriter: *PatternRewriter,76    ) bool {77        for (self.getMatchingPatterns(op)) |*pattern| {78            if (tryApplyRewritePattern(pattern, op, rewriter)) return true;79        }80        return false;81    }82};

1pub const TypeConverter = struct {2    allocator: std.mem.Allocator,34    conversions: std.HashMap(TypeKey, TypeConversionResult, TypeKeyContext, std.hash_map.default_max_load_percentage),5    materialize_fn: ?MaterializeFn,67    const TypeKey = struct {8        name: []const u8,9        param_key: []const u8,10    };1112    const TypeKeyContext = struct {13        pub fn hash(_: TypeKeyContext, key: TypeKey) u64 {14            var hasher = std.hash.Wyhash.init(0);15            hasher.update(key.name);16            hasher.update(&[_]u8{0});17            hasher.update(key.param_key);18            return hasher.final();19        }2021        pub fn eql(_: TypeKeyContext, a: TypeKey, b: TypeKey) bool {22            return std.mem.eql(u8, a.name, b.name) and std.mem.eql(u8, a.param_key, b.param_key);23        }24    };2526    pub const TypeConversionResult = struct {27        types: []ir.Type,28    };2930    pub const MaterializeFn = *const fn (31        rewriter: *PatternRewriter,32        value: *ir.Value,33        target_type: ir.Type,34    ) ?*ir.Value;3536    fn dupeTypes(allocator: std.mem.Allocator, target_types: []const ir.Type) ![]ir.Type {37        if (target_types.len == 0) {38            return try allocator.alloc(ir.Type, 0);39        }40        const duped = try allocator.alloc(ir.Type, target_types.len);41        @memcpy(duped, target_types);42        return duped;43    }4445    pub fn init(allocator: std.mem.Allocator) TypeConverter {46        return .{47            .allocator = allocator,48            .conversions = std.HashMap(TypeKey, TypeConversionResult, TypeKeyContext, std.hash_map.default_max_load_percentage).init(allocator),49            .materialize_fn = null,50        };51    }5253    pub fn deinit(self: *TypeConverter) void {54        var iter = self.conversions.iterator();55        while (iter.next()) |entry| {56            const key = entry.key_ptr.*;57            self.allocator.free(key.name);58            if (key.param_key.len > 0) {59                self.allocator.free(key.param_key);60            }61            const types = entry.value_ptr.types;62            self.allocator.free(types);63        }64        self.conversions.deinit();65    }6667    pub fn addConversion(self: *TypeConverter, source_type: ir.Type, target_types: []const ir.Type) !void {68        const storage = source_type.getDialectStorage() orelse return error.InvalidType;69        const lookup_key = TypeKey{ .name = storage.name, .param_key = storage.param_key };70        if (self.conversions.getPtr(lookup_key)) |result| {71            const types_copy = try dupeTypes(self.allocator, target_types);72            errdefer self.allocator.free(types_copy);73            self.allocator.free(result.types);74            result.types = types_copy;75            return;76        }77        const name_copy = try self.allocator.dupe(u8, storage.name);78        errdefer self.allocator.free(name_copy);79        const key_copy = if (storage.param_key.len > 0)80            try self.allocator.dupe(u8, storage.param_key)81        else82            "";83        errdefer if (key_copy.len > 0) self.allocator.free(key_copy);8485        const types_copy = try dupeTypes(self.allocator, target_types);86        errdefer self.allocator.free(types_copy);8788        try self.conversions.put(.{ .name = name_copy, .param_key = key_copy }, TypeConversionResult{ .types = types_copy });89    }9091    pub fn setMaterialization(self: *TypeConverter, materialize_fn: MaterializeFn) void {92        self.materialize_fn = materialize_fn;93    }9495    pub fn materialize(self: *const TypeConverter, rewriter: *PatternRewriter, value: *ir.Value, target_type: ir.Type) ?*ir.Value {96        const func = self.materialize_fn orelse return null;97        return func(rewriter, value, target_type);98    }99100    pub fn convertType(self: *const TypeConverter, source_type: ir.Type) ?[]const ir.Type {101        if (source_type.getDialectStorage()) |storage| {102            const key = TypeKey{ .name = storage.name, .param_key = storage.param_key };103            if (self.conversions.get(key)) |result| {104                return result.types;105            }106        }107        return null;108    }109110    pub fn convertTypesAlloc(self: *const TypeConverter, allocator: std.mem.Allocator, source_types: []const ir.Type) ![]ir.Type {111        var out: std.ArrayListUnmanaged(ir.Type) = .empty;112        errdefer out.deinit(allocator);113114        for (source_types) |source_type| {115            if (self.convertType(source_type)) |converted| {116                try out.appendSlice(allocator, converted);117            } else {118                try out.append(allocator, source_type);119            }120        }121122        return out.toOwnedSlice(allocator);123    }124125    pub fn isTypeLegal(self: *const TypeConverter, t: ir.Type) bool {126        return self.convertType(t) == null;127    }128};

1pub const builtin_pattern_benefit: rewrite.PatternBenefit = 10;

1pub const fold_pattern_benefit: rewrite.PatternBenefit = 100;

1pub const PatternBenefit = u16;

1pub inline fn tryApplyRewritePattern(2    pattern: *const RewritePattern,3    op: *ir.Operation,4    rewriter: *PatternRewriter,5) bool {6    if (!pattern.matchesAfterRoot(op)) return false;7    var attempt = PatternRewriteAttempt.init(op, rewriter);8    return attempt.finish(pattern.apply(op, rewriter));9}

1const pattern_mod = @import("pattern.zig");2pub const PatternBenefit = pattern_mod.PatternBenefit;3pub const RewritePatternKind = pattern_mod.RewritePatternKind;4pub const RewritePatternProducts = pattern_mod.RewritePatternProducts;5pub const RewritePatternSpec = pattern_mod.RewritePatternSpec;6pub const RewritePattern = pattern_mod.RewritePattern;7pub const PatternResult = pattern_mod.PatternResult;89const rewriter_mod = @import("rewriter.zig");10pub const PatternRewriter = rewriter_mod.PatternRewriter;11pub const PatternRewriteAttempt = rewriter_mod.PatternRewriteAttempt;12pub const tryApplyRewritePattern = rewriter_mod.tryApplyRewritePattern;1314const set_mod = @import("set.zig");15pub const RewritePatternSet = set_mod.RewritePatternSet;1617const index_mod = @import("index.zig");18pub const PatternIndex = index_mod.PatternIndex;1920const type_mod = @import("type.zig");21pub const TypeConverter = type_mod.TypeConverter;2223const canonicalization_mod = @import("canonicalization.zig");24pub const DialectCanonicalizationInterface = canonicalization_mod.DialectCanonicalizationInterface;25pub const builtin_pattern_benefit = canonicalization_mod.builtin_pattern_benefit;26pub const fold_pattern_benefit = canonicalization_mod.fold_pattern_benefit;

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