tiny.choir.passes.conversion

1const std = @import("std");2const alloc_observe = @import("alloc_observe");3const alloc_arena = @import("alloc_arena");4const alloc_phase = @import("alloc_phase");5const ir = @import("../core/root.zig");6const rewrite = ir.rewrite;78pub const Legality = enum {9    legal,10    recursively_legal,11    dynamic,12    illegal,13    unknown,14};1516pub const ConversionTarget = struct {17    allocator: std.mem.Allocator,1819    legal_ops: std.StringHashMap(void),2021    dynamic_ops: std.StringHashMap(*const fn (*ir.Operation) bool),2223    recursively_legal_ops: std.StringHashMap(void),2425    illegal_ops: std.StringHashMap(void),2627    legal_dialects: std.StringHashMap(void),2829    recursively_legal_dialects: std.StringHashMap(void),3031    illegal_dialects: std.StringHashMap(void),3233    pub fn init(allocator: std.mem.Allocator) ConversionTarget {34        return .{35            .allocator = allocator,36            .legal_ops = std.StringHashMap(void).init(allocator),37            .dynamic_ops = std.StringHashMap(*const fn (*ir.Operation) bool).init(allocator),38            .recursively_legal_ops = std.StringHashMap(void).init(allocator),39            .illegal_ops = std.StringHashMap(void).init(allocator),40            .legal_dialects = std.StringHashMap(void).init(allocator),41            .recursively_legal_dialects = std.StringHashMap(void).init(allocator),42            .illegal_dialects = std.StringHashMap(void).init(allocator),43        };44    }4546    pub fn deinit(self: *ConversionTarget) void {47        self.legal_ops.deinit();48        self.dynamic_ops.deinit();49        self.recursively_legal_ops.deinit();50        self.illegal_ops.deinit();51        self.legal_dialects.deinit();52        self.recursively_legal_dialects.deinit();53        self.illegal_dialects.deinit();54    }5556    pub fn addLegalOp(self: *ConversionTarget, op_name: []const u8) !void {57        try self.legal_ops.put(op_name, {});58    }5960    pub fn addDynamicallyLegalOp(61        self: *ConversionTarget,62        op_name: []const u8,63        predicate: *const fn (*ir.Operation) bool,64    ) !void {65        try self.dynamic_ops.put(op_name, predicate);66    }6768    pub fn addRecursivelyLegalOp(self: *ConversionTarget, op_name: []const u8) !void {69        try self.recursively_legal_ops.put(op_name, {});70    }7172    pub fn addIllegalOp(self: *ConversionTarget, op_name: []const u8) !void {73        try self.illegal_ops.put(op_name, {});74    }7576    pub fn addLegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {77        try self.legal_dialects.put(dialect_name, {});78    }7980    pub fn addRecursivelyLegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {81        try self.recursively_legal_dialects.put(dialect_name, {});82    }8384    pub fn addIllegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {85        try self.illegal_dialects.put(dialect_name, {});86    }8788    pub fn getOpLegality(self: *const ConversionTarget, op: *ir.Operation) Legality {89        const op_name = op.name.name;9091        if (self.illegal_ops.contains(op_name)) {92            return .illegal;93        }94        if (self.legal_ops.contains(op_name)) {95            return .legal;96        }97        if (self.recursively_legal_ops.contains(op_name)) {98            return .recursively_legal;99        }100        if (self.dynamic_ops.get(op_name)) |predicate| {101            return if (predicate(op)) .legal else .illegal;102        }103104        const dialect_name = op.name.getDialectNamespace();105        if (self.illegal_dialects.contains(dialect_name)) {106            return .illegal;107        }108        if (self.legal_dialects.contains(dialect_name)) {109            return .legal;110        }111        if (self.recursively_legal_dialects.contains(dialect_name)) {112            return .recursively_legal;113        }114115        return .unknown;116    }117118    pub fn isRecursivelyLegal(self: *const ConversionTarget, op: *ir.Operation) bool {119        return self.getOpLegality(op) == .recursively_legal;120    }121122    pub fn isLegal(self: *const ConversionTarget, op: *ir.Operation) bool {123        const legality = self.getOpLegality(op);124        return legality == .legal or legality == .recursively_legal or legality == .unknown;125    }126127    pub fn isIllegal(self: *const ConversionTarget, op: *ir.Operation) bool {128        return self.getOpLegality(op) == .illegal;129    }130};131132pub const ConversionResult = enum {133    success,134    failure,135};136137pub const ConversionOptions = struct {138    type_converter: ?*const rewrite.TypeConverter = null,139    allow_unknown_ops: ?bool = null,140    max_iterations: u32 = 100,141};142143pub fn applyPartialConversion(144    allocator: std.mem.Allocator,145    ir_ctx: *ir.Context,146    op: *ir.Operation,147    target: *const ConversionTarget,148    patterns: *rewrite.RewritePatternSet,149) ConversionResult {150    return applyPartialConversionWithOptions(allocator, ir_ctx, op, target, patterns, .{});151}152153pub fn applyPartialConversionWithOptions(154    allocator: std.mem.Allocator,155    ir_ctx: *ir.Context,156    op: *ir.Operation,157    target: *const ConversionTarget,158    patterns: *rewrite.RewritePatternSet,159    options: ConversionOptions,160) ConversionResult {161    patterns.seal() catch return .failure;162    var rewriter = rewrite.PatternRewriter.initWithTypeConverter(allocator, ir_ctx, options.type_converter);163    defer rewriter.deinit();164165    return runConversion(&rewriter, op, target, patterns, false, options);166}167168pub fn applyFullConversion(169    allocator: std.mem.Allocator,170    ir_ctx: *ir.Context,171    op: *ir.Operation,172    target: *const ConversionTarget,173    patterns: *rewrite.RewritePatternSet,174) ConversionResult {175    return applyFullConversionWithOptions(allocator, ir_ctx, op, target, patterns, .{});176}177178pub fn applyFullConversionWithOptions(179    allocator: std.mem.Allocator,180    ir_ctx: *ir.Context,181    op: *ir.Operation,182    target: *const ConversionTarget,183    patterns: *rewrite.RewritePatternSet,184    options: ConversionOptions,185) ConversionResult {186    patterns.seal() catch return .failure;187    var rewriter = rewrite.PatternRewriter.initWithTypeConverter(allocator, ir_ctx, options.type_converter);188    defer rewriter.deinit();189190    return runConversion(&rewriter, op, target, patterns, true, options);191}192193const OperationSnapshotFacts = struct {194    context_operation_count: usize,195};196197const OperationSnapshotLimits = struct {198    root_op: *ir.Operation,199    target: ?*const ConversionTarget,200    facts: OperationSnapshotFacts,201202    fn inspect(203        root_op: *ir.Operation,204        target: ?*const ConversionTarget,205    ) OperationSnapshotLimits {206        return .{207            .root_op = root_op,208            .target = target,209            .facts = .{210                .context_operation_count = root_op.getContext().operationCount(),211            },212        };213    }214};215216const OperationSnapshotCapacity = struct {217    facts: OperationSnapshotFacts,218    pointer_count: usize,219    storage_bytes: usize,220221    pub fn derive(222        limits: OperationSnapshotLimits,223    ) error{CapacityOverflow}!OperationSnapshotCapacity {224        const storage_bytes = std.math.mul(225            usize,226            limits.facts.context_operation_count,227            @sizeOf(*ir.Operation),228        ) catch return error.CapacityOverflow;229        return .{230            .facts = limits.facts,231            .pointer_count = limits.facts.context_operation_count,232            .storage_bytes = storage_bytes,233        };234    }235};236237pub const OperationSnapshot = struct {238    pub const claim: alloc_phase.capacity.Declaration = .{239        .source = .{240            .id = "choir.conversion_initial_snapshot",241            .kind = .phase_static,242            .limit_source = .caller,243            .storage = .{244                .covered = &.{245                    .{246                        .id = "one_pointer_slot_per_operation_tracked_by_the_root_166d4a84fb6a",247                        .lifetime = .steady,248                        .detail = "one pointer slot per operation tracked by the root Context at snapshot admission",249                    },250                },251                .excluded = &.{252                    "rewrite-created operation extension storage and pattern-rewriter state",253                    "borrowed IR, conversion targets, callbacks, and Context registry storage",254                },255            },256            .capacity = .{257                .inputs = &.{258                    alloc_phase.capacity.bindInput(Limits, "facts_context_operation_count", "facts.context_operation_count"),259                },260                .type_selectors = &.{261                    alloc_phase.capacity.bindType(*ir.Operation, "operation"),262                },263                .nodes = &.{264                    .{ .input = 0 },265                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },266                },267                .assertions = &.{.{268                    .scope = .closure_total,269                    .measure = .retained,270                    .relation = .exact,271                    .expression = 1,272                }},273            },274            .overload = .{275                .kind = .reject_before_seal,276                .detail = "byte overflow, OOM, foreign-Context nesting, or snapshot capacity exhaustion rejects before conversion mutation and leaves admission retryable",277            },278            .risks = .{279                .transitive = .{280                    .status = .open,281                    .detail = "recursive Operation.walk has no machine-closed call-graph or nesting certificate",282                },283                .foreign = .{284                    .status = .open,285                    .detail = "recursive-legality lookup may invoke a caller-provided dynamic legality predicate",286                },287            },288            .obligations = &.{289                .{ .key = "conversion_snapshot_capacity_capacity_model", .role = .capacity_model },290                .{ .key = "conversion_snapshot_capacity_overload", .role = .overload },291                .{ .key = "conversion_snapshot_sealed_reuse_transitive_risk", .role = .transitive_risk },292                .{ .key = "conversion_snapshot_sealed_reuse_foreign_risk", .role = .foreign_risk },293                .{ .key = "conversion_snapshot_context", .role = .overload },294                .{ .key = "conversion_snapshot_oom_retry", .role = .overload },295            },296        },297        .bindings = .{298            .owner = @This(),299            .seal = .{300                .family = alloc_phase.capacity.selector(@This().activate),301                .premise = .{302                    .class = .checked_semantic_fact,303                    .authority = .checker,304                },305            },306            .teardown = .{307                .family = alloc_phase.capacity.selector(@This().deinit),308                .premise = .{309                    .class = .checked_semantic_fact,310                    .authority = .checker,311                },312            },313        },314    };315316    phase: alloc_phase.capacity.Phase,317    capacity: OperationSnapshotCapacity,318    storage: []*ir.Operation,319    operation_count: usize,320321    pub const Limits = OperationSnapshotLimits;322    pub const Capacity = OperationSnapshotCapacity;323324    const FillContext = struct {325        root_context: *ir.Context,326        target: ?*const ConversionTarget,327        storage: []*ir.Operation,328        operation_count: usize,329330        fn visit(331            self: *FillContext,332            op: *ir.Operation,333        ) error{ SnapshotCapacityExceeded, ForeignOperationContext }!ir.WalkResult {334            if (op.getContext() != self.root_context) {335                return error.ForeignOperationContext;336            }337            if (self.operation_count >= self.storage.len) {338                return error.SnapshotCapacityExceeded;339            }340            self.storage[self.operation_count] = op;341            self.operation_count = std.math.add(342                usize,343                self.operation_count,344                1,345            ) catch unreachable;346            if (self.target) |target| {347                if (target.isRecursivelyLegal(op)) return .skip;348            }349            return .advance;350        }351    };352353    pub fn init(354        allocator: std.mem.Allocator,355        limits: OperationSnapshotLimits,356    ) !OperationSnapshot {357        const capacity = try OperationSnapshotCapacity.derive(limits);358        const storage = try allocator.alloc(*ir.Operation, capacity.pointer_count);359        errdefer allocator.free(storage);360361        var fill = FillContext{362            .root_context = limits.root_op.getContext(),363            .target = limits.target,364            .storage = storage,365            .operation_count = 0,366        };367        const result = try limits.root_op.walk(368            .{ .order = .pre_order },369            &fill,370            FillContext.visit,371        );372        std.debug.assert(result == .advance);373374        const snapshot = OperationSnapshot{375            .phase = .initialization,376            .capacity = capacity,377            .storage = storage,378            .operation_count = fill.operation_count,379        };380        snapshot.assertInvariant();381        return snapshot;382    }383384    pub fn activate(self: *OperationSnapshot) void {385        if (self.phase != .initialization) {386            @panic("conversion operation snapshot activation is one-way");387        }388        self.phase = .steady;389        self.assertInvariant();390    }391392    fn operations(self: *const OperationSnapshot) []const *ir.Operation {393        if (self.phase != .steady) {394            @panic("conversion operation snapshot is not active");395        }396        self.assertInvariant();397        return self.storage[0..self.operation_count];398    }399400    pub fn deinit(401        self: *OperationSnapshot,402        allocator: std.mem.Allocator,403    ) void {404        if (self.phase == .teardown) {405            @panic("conversion operation snapshot teardown is terminal");406        }407        self.assertInvariant();408        self.phase = .teardown;409        allocator.free(self.storage);410        self.storage = undefined;411        self.operation_count = undefined;412    }413414    fn assertInvariant(self: *const OperationSnapshot) void {415        std.debug.assert(self.phase != .teardown);416        std.debug.assert(self.storage.len == self.capacity.pointer_count);417        std.debug.assert(self.capacity.storage_bytes ==418            self.capacity.pointer_count * @sizeOf(*ir.Operation));419        std.debug.assert(self.operation_count <= self.storage.len);420    }421};422423comptime {424    alloc_phase.capacity.requireAllocatorExactOwnerShape(OperationSnapshot);425}426427fn collectNestedOps(428    allocator: std.mem.Allocator,429    op: *ir.Operation,430    target: ?*const ConversionTarget,431    worklist: *std.ArrayListUnmanaged(*ir.Operation),432) !void {433    var context = CollectNestedOpsContext{434        .allocator = allocator,435        .target = target,436        .worklist = worklist,437    };438    _ = try op.walk(.{ .order = .pre_order }, &context, CollectNestedOpsContext.visit);439}440441const CollectNestedOpsContext = struct {442    allocator: std.mem.Allocator,443    target: ?*const ConversionTarget,444    worklist: *std.ArrayListUnmanaged(*ir.Operation),445446    fn visit(self: *CollectNestedOpsContext, op: *ir.Operation) !ir.WalkResult {447        try self.worklist.append(self.allocator, op);448        if (self.target) |target| {449            if (target.isRecursivelyLegal(op)) return .skip;450        }451        return .advance;452    }453};454455const ConversionWorklist = struct {456    initial: OperationSnapshot,457    created: std.ArrayListUnmanaged(*ir.Operation),458459    fn init(460        allocator: std.mem.Allocator,461        root_op: *ir.Operation,462        target: ?*const ConversionTarget,463    ) !ConversionWorklist {464        var initial = try OperationSnapshot.init(465            allocator,466            OperationSnapshotLimits.inspect(root_op, target),467        );468        initial.activate();469        return .{470            .initial = initial,471            .created = .empty,472        };473    }474475    fn deinit(476        self: *ConversionWorklist,477        allocator: std.mem.Allocator,478    ) void {479        self.created.deinit(allocator);480        self.initial.deinit(allocator);481    }482483    fn len(self: *const ConversionWorklist) usize {484        return std.math.add(485            usize,486            self.initial.operations().len,487            self.created.items.len,488        ) catch unreachable;489    }490491    fn get(492        self: *const ConversionWorklist,493        index: usize,494    ) *ir.Operation {495        const initial = self.initial.operations();496        std.debug.assert(index < self.len());497        if (index < initial.len) return initial[index];498        return self.created.items[index - initial.len];499    }500501    fn appendNested(502        self: *ConversionWorklist,503        allocator: std.mem.Allocator,504        op: *ir.Operation,505        target: ?*const ConversionTarget,506    ) !void {507        try collectNestedOps(allocator, op, target, &self.created);508    }509};510511fn opTypesLegal(op: *ir.Operation, converter: *const rewrite.TypeConverter) bool {512    for (op.operands.items) |operand| {513        if (!converter.isTypeLegal(operand.value.type)) return false;514    }515516    for (op.results.items) |*result| {517        if (!converter.isTypeLegal(result.type)) return false;518    }519520    for (op.regions.items) |*region| {521        var block_iter = region.getBlocks();522        while (block_iter.next()) |block| {523            for (block.arguments.items) |arg| {524                if (!converter.isTypeLegal(arg.type)) return false;525            }526        }527    }528529    return true;530}531532fn resolveAllowUnknownOps(options: ConversionOptions, require_full: bool) bool {533    return options.allow_unknown_ops orelse !require_full;534}535536fn isOpLegal(target: *const ConversionTarget, op: *ir.Operation, options: ConversionOptions, allow_unknown_ops: bool) bool {537    const legality = target.getOpLegality(op);538    const base_legal = switch (legality) {539        .legal => true,540        .recursively_legal => true,541        .illegal => false,542        .unknown => allow_unknown_ops,543        .dynamic => allow_unknown_ops,544    };545    if (!base_legal) return false;546547    if (options.type_converter) |converter| {548        if (!opTypesLegal(op, converter)) return false;549    }550551    return true;552}553554fn mustLegalizeOp(target: *const ConversionTarget, op: *ir.Operation, allow_unknown_ops: bool, require_full: bool) bool {555    if (require_full) return true;556    return switch (target.getOpLegality(op)) {557        .illegal => true,558        .unknown, .dynamic => !allow_unknown_ops,559        .legal, .recursively_legal => false,560    };561}562563fn runConversion(564    rewriter: *rewrite.PatternRewriter,565    root_op: *ir.Operation,566    target: *const ConversionTarget,567    patterns: *const rewrite.RewritePatternSet,568    require_full: bool,569    options: ConversionOptions,570) ConversionResult {571    var worklist = ConversionWorklist.init(572        rewriter.allocator,573        root_op,574        target,575    ) catch return .failure;576    defer worklist.deinit(rewriter.allocator);577578    var changed = true;579    var iterations: u32 = 0;580    const max_iterations: u32 = if (options.max_iterations == 0) std.math.maxInt(u32) else options.max_iterations;581    const allow_unknown_ops = resolveAllowUnknownOps(options, require_full);582583    while (changed and iterations < max_iterations) {584        changed = false;585        iterations += 1;586587        const initial_worklist_len = worklist.len();588589        var i: usize = 0;590        while (i < initial_worklist_len) {591            const op = worklist.get(i);592593            if (rewriter.isScheduledForErase(op)) {594                i += 1;595                continue;596            }597598            if (isOpLegal(target, op, options, allow_unknown_ops)) {599                i += 1;600                continue;601            }602603            var pattern_applied = false;604            for (patterns.getMatchingPatterns(op)) |pattern| {605                if (pattern.matchesAfterRoot(op)) {606                    const created_before = rewriter.created_ops.items.len;607608                    const result = blk: {609                        var guard = rewriter.insertionGuard();610                        defer guard.deinit();611                        rewriter.setInsertionPointBefore(op);612                        break :blk pattern.apply(op, rewriter);613                    };614                    if (result == .success) {615                        pattern_applied = true;616                        changed = true;617618                        for (rewriter.created_ops.items[created_before..]) |new_op| {619                            worklist.appendNested(620                                rewriter.allocator,621                                new_op,622                                target,623                            ) catch return .failure;624                        }625                        break;626                    }627                }628            }629630            if (!pattern_applied and mustLegalizeOp(target, op, allow_unknown_ops, require_full)) {631                return .failure;632            }633634            i += 1;635        }636    }637638    const hit_iteration_limit = changed and iterations >= max_iterations;639    if (require_full and hit_iteration_limit) {640        var work_index: usize = 0;641        while (work_index < worklist.len()) : (work_index += 1) {642            const work_op = worklist.get(work_index);643            if (rewriter.isScheduledForErase(work_op)) continue;644            if (!isOpLegal(target, work_op, options, allow_unknown_ops)) return .failure;645        }646    }647648    rewriter.finalize(root_op);649    return .success;650}651652pub const GreedyRewriteStrictness = enum {653    existing_ops,654    existing_and_new_ops,655};656657pub const GreedyRewriteConfig = struct {658    max_iterations: u32 = 10,659    max_rewrites: u32 = 0,660    strictness: GreedyRewriteStrictness = .existing_and_new_ops,661};662663const GreedyRewriteTermination = enum {664    converged,665    iteration_limit,666    rewrite_limit,667    invalid_context,668    invalid_patterns,669};670671pub const GreedyRewriteResult = struct {672    termination: Termination,673    changed: bool = false,674    /// Traversals begun, including the converging or interrupted traversal.675    iterations: u32 = 0,676    rewrites: u32 = 0,677678    pub const Termination: type = GreedyRewriteTermination;679};680681const GreedyRewriteIterationStorage = struct {682    pub const inline_bytes: usize = 2 * 1024;683684    buffer: [inline_bytes]u8 = undefined,685    fallback_allocator: std.mem.Allocator,686    stack_fallback: alloc_observe.buffer.First = undefined,687688    fn init(fallback_allocator: std.mem.Allocator) GreedyRewriteIterationStorage {689        return .{ .fallback_allocator = fallback_allocator };690    }691692    fn allocator(self: *GreedyRewriteIterationStorage) std.mem.Allocator {693        self.stack_fallback = .init(&self.buffer, self.fallback_allocator);694        return self.stack_fallback.allocator();695    }696};697698fn GreedyRewriteWalk(comptime PatternSource: type) type {699    return struct {700        source: *PatternSource,701        rewriter: *rewrite.PatternRewriter,702        creation_boundary: u31,703        rewrite_limit: u32,704        rewrites: *u32,705        changed: bool = false,706        limit_reached: bool = false,707        invalid_context: bool = false,708709        const Self = @This();710711        fn visit(self: *Self, op: *ir.Operation) ir.WalkResult {712            if (op.getContext() != self.rewriter.ir_ctx) {713                self.invalid_context = true;714                return .interrupt;715            }716            if (!op.createdBefore(self.creation_boundary)) return .skip;717            if (self.rewriter.isScheduledForErase(op)) return .advance;718719            if (self.source.applyFirstMatchingPattern(op, self.rewriter)) {720                self.changed = true;721                self.rewrites.* += 1;722                if (self.rewrites.* >= self.rewrite_limit) {723                    self.limit_reached = true;724                    return .interrupt;725                }726            }727            return .advance;728        }729730        fn apply(self: *Self, op: *ir.Operation) bool {731            const result = op.walk(.{ .order = .pre_order }, self, visit) catch unreachable;732            return result == .advance;733        }734735        fn assertInterrupted(self: *const Self) void {736            if (self.limit_reached) return;737            std.debug.assert(self.invalid_context);738        }739    };740}741742pub fn applyPatternsGreedily(743    allocator: std.mem.Allocator,744    ir_ctx: *ir.Context,745    root_op: *ir.Operation,746    patterns: *rewrite.RewritePatternSet,747    config: GreedyRewriteConfig,748) GreedyRewriteResult {749    patterns.seal() catch return .{ .termination = .invalid_patterns };750751    return applyPatternsGreedilyFromSource(752        allocator,753        ir_ctx,754        root_op,755        patterns,756        config,757    );758}759760pub fn applyPatternsGreedilyFromSource(761    allocator: std.mem.Allocator,762    ir_ctx: *ir.Context,763    root_op: *ir.Operation,764    source: anytype,765    config: GreedyRewriteConfig,766) GreedyRewriteResult {767    const PatternSource = @TypeOf(source.*);768    const Walk = GreedyRewriteWalk(PatternSource);769    const iteration_limit = if (config.max_iterations == 0) std.math.maxInt(u32) else config.max_iterations;770    const rewrite_limit = if (config.max_rewrites == 0) std.math.maxInt(u32) else config.max_rewrites;771772    var result = GreedyRewriteResult{ .termination = .iteration_limit };773774    while (result.iterations < iteration_limit) {775        result.iterations += 1;776        var rewrite_storage = GreedyRewriteIterationStorage.init(allocator);777        var rewriter = rewrite.PatternRewriter.init(rewrite_storage.allocator(), ir_ctx);778        defer rewriter.deinit();779        defer rewriter.finalize(root_op);780781        const process_new_ops = config.strictness == .existing_and_new_ops;782        var walk = Walk{783            .source = source,784            .rewriter = &rewriter,785            .creation_boundary = ir_ctx.operationCreationBoundary(),786            .rewrite_limit = rewrite_limit,787            .rewrites = &result.rewrites,788        };789        if (!walk.apply(root_op)) {790            walk.assertInterrupted();791            result.changed = result.changed or walk.changed;792            result.termination = if (walk.limit_reached) .rewrite_limit else .invalid_context;793            return result;794        }795796        if (process_new_ops) {797            var created_index: usize = 0;798            while (created_index < rewriter.created_ops.items.len) : (created_index += 1) {799                walk.creation_boundary = ir_ctx.operationCreationBoundary();800                if (!walk.apply(rewriter.created_ops.items[created_index])) {801                    walk.assertInterrupted();802                    result.changed = result.changed or walk.changed;803                    result.termination = if (walk.limit_reached) .rewrite_limit else .invalid_context;804                    return result;805                }806            }807        }808809        result.changed = result.changed or walk.changed;810        if (!walk.changed) {811            result.termination = .converged;812            return result;813        }814    }815816    return result;817}818819test "conversion target" {820    const testing = std.testing;821    const allocator = testing.allocator;822823    var target = ConversionTarget.init(allocator);824    defer target.deinit();825826    try target.addLegalDialect("wasm");827828    try target.addIllegalDialect("arith");829830    var arena = alloc_arena.Arena.init(std.testing.allocator);831    defer arena.deinit();832833    var ctx = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);834    defer ctx.deinit(arena.allocator());835    try ctx.allowUnregistered();836837    const state = ir.Operation.State.init("arith.addi", ir.Location.getUnknown());838    const op = try ctx.createOperation(state);839840    try testing.expect(target.isIllegal(op));841842    try target.addLegalOp("arith.addi");843    try testing.expect(target.isLegal(op));844}845846test "conversion target recursively legal op skips nested illegal operations" {847    const testing = std.testing;848849    var arena = alloc_arena.Arena.init(std.testing.allocator);850    defer arena.deinit();851    const allocator = arena.allocator();852853    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);854    defer ctx.deinit(allocator);855    try ctx.allowUnregistered();856857    const loc = ir.Location.getUnknown();858    var parent_state = ir.Operation.State.init("test.container", loc);859    parent_state.addRegion();860    const parent = try ctx.createOperation(parent_state);861    const block = try (parent.getRegion(0) orelse return error.TestExpectedRegion).addBlock();862863    const child_state = ir.Operation.State.init("test.child", loc);864    const child = try ctx.createOperation(child_state);865    try block.addOperation(child);866867    var target = ConversionTarget.init(allocator);868    defer target.deinit();869    try target.addRecursivelyLegalOp("test.container");870    try target.addIllegalOp("test.child");871    try testing.expect(target.isRecursivelyLegal(parent));872    try testing.expect(target.isIllegal(child));873874    var patterns = rewrite.RewritePatternSet.init(allocator);875    defer patterns.deinit();876877    try testing.expectEqual(878        ConversionResult.success,879        applyFullConversion(allocator, &ctx, parent, &target, &patterns),880    );881}882883test "conversion modes distinguish unknown and illegal operations" {884    const testing = std.testing;885886    var arena = alloc_arena.Arena.init(std.testing.allocator);887    defer arena.deinit();888    const allocator = arena.allocator();889890    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);891    defer ctx.deinit(allocator);892    try ctx.allowUnregistered();893894    var target = ConversionTarget.init(allocator);895    defer target.deinit();896897    var patterns = rewrite.RewritePatternSet.init(allocator);898    defer patterns.deinit();899900    const loc = ir.Location.getUnknown();901902    const partial_unknown = try ctx.createOperation(ir.Operation.State.init("test.unknown", loc));903    try testing.expectEqual(904        ConversionResult.success,905        applyPartialConversion(allocator, &ctx, partial_unknown, &target, &patterns),906    );907908    const full_unknown = try ctx.createOperation(ir.Operation.State.init("test.unknown", loc));909    try testing.expectEqual(910        ConversionResult.failure,911        applyFullConversion(allocator, &ctx, full_unknown, &target, &patterns),912    );913914    const explicitly_allowed = try ctx.createOperation(ir.Operation.State.init("test.unknown", loc));915    try testing.expectEqual(916        ConversionResult.success,917        applyFullConversionWithOptions(918            allocator,919            &ctx,920            explicitly_allowed,921            &target,922            &patterns,923            .{ .allow_unknown_ops = true },924        ),925    );926927    try target.addIllegalOp("test.illegal");928    const partial_illegal = try ctx.createOperation(ir.Operation.State.init("test.illegal", loc));929    try testing.expectEqual(930        ConversionResult.failure,931        applyPartialConversion(allocator, &ctx, partial_illegal, &target, &patterns),932    );933}934935fn checkGreedyEraseIterationStorage(936    operation_count: usize,937    fail_index: usize,938    expected_allocations: usize,939    expected_allocated_bytes: usize,940    expected_failure: bool,941) !void {942    const testing = std.testing;943    const test_dialect = @import("../dialects/fixture/root.zig");944945    var arena = alloc_arena.Arena.init(testing.allocator);946    defer arena.deinit();947    const allocator = arena.allocator();948949    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);950    defer ctx.deinit(allocator);951    try ctx.allowUnregistered();952953    const module_op = try test_dialect.TestDialect.ModuleOp.create(954        &ctx,955        .unknown,956    );957    const module_block = module_op.getBodyBlock();958    var builder = ir.OperationBuilder.init(&ctx);959    for (0..operation_count) |_| {960        try module_block.addOperation(try builder.create(961            ir.Operation.State.init("test.source", .unknown),962        ));963    }964965    var patterns = rewrite.RewritePatternSet.init(testing.allocator);966    defer patterns.deinit();967    try patterns.add(rewrite.RewritePattern.init(968        testRewriteSpec("test.source", 1),969        dummyRewrite,970    ));971    try patterns.seal();972973    var failing = testing.FailingAllocator.init(974        testing.allocator,975        .{ .fail_index = fail_index },976    );977    const result = applyPatternsGreedily(978        failing.allocator(),979        &ctx,980        module_op.op,981        &patterns,982        .{},983    );984    try testing.expectEqual(.converged, result.termination);985    try testing.expect(result.changed);986    try testing.expectEqual(expected_allocations, failing.alloc_index);987    try testing.expectEqual(expected_allocated_bytes, failing.allocated_bytes);988    try testing.expectEqual(expected_failure, failing.has_induced_failure);989    var remaining = module_block.getOperations();990    try testing.expect(remaining.next() == null);991}992993fn rewriteToLow(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {994    const state = ir.Operation.State.init("test.low", op.location);995    _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;996    return .success;997}998999fn rewriteToHigh(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1000    const state = ir.Operation.State.init("test.high", op.location);1001    _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;1002    return .success;1003}10041005fn matchNever(_: *ir.Operation) bool {1006    return false;1007}10081009fn rewriteAToB(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1010    const state = ir.Operation.State.init("test.b", op.location);1011    _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;1012    return .success;1013}10141015fn rewriteBToC(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1016    const state = ir.Operation.State.init("test.c", op.location);1017    _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;1018    return .success;1019}10201021fn rewriteInsertBeforeFutureOp(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1022    const middle = op.next_op orelse return .failure;1023    const future = middle.next_op orelse return .failure;1024    rewriter.setInsertionPointBefore(future);1025    _ = rewriter.create(ir.Operation.State.init("test.new", op.location)) catch return .failure;1026    rewriter.eraseOp(op) catch return .failure;1027    return .success;1028}10291030fn checkOperationSnapshotInitFailures(1031    allocator: std.mem.Allocator,1032    root_op: *ir.Operation,1033) !void {1034    var snapshot = try OperationSnapshot.init(1035        allocator,1036        OperationSnapshotLimits.inspect(root_op, null),1037    );1038    defer snapshot.deinit(allocator);1039    snapshot.activate();1040    try std.testing.expect(snapshot.operations().len > 0);1041}10421043test "conversion snapshot derives pointer capacity from the authoritative Context registry" {1044    comptime {1045        @stardustClaim(1046            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_capacity_capacity_model"),1047            null,1048            null,1049            null,1050            null,1051            null,1052            null,1053        );1054    }1055    comptime {1056        @stardustClaim(1057            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_capacity_overload"),1058            null,1059            null,1060            null,1061            null,1062            null,1063            null,1064        );1065    }10661067    const testing = std.testing;1068    const test_dialect = @import("../dialects/fixture/root.zig");10691070    var ctx = try ir.Context.init(testing.allocator, ir.Context.Limits.testing);1071    defer ctx.deinit(testing.allocator);1072    try ctx.allowUnregistered();10731074    const loc = ir.Location.getUnknown();1075    const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);10761077    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1078    const module_block = module_op.getBodyBlock();10791080    const func_op = try test_dialect.TestDialect.FuncOp.create(&ctx, loc, "nested_ops", &.{ i32_type, i32_type });1081    try module_block.addOperation(func_op.op);10821083    const func_block = func_op.getEntryBlock();1084    const func_args = func_op.getArguments();1085    const arg0 = func_args[0];1086    const arg1 = func_args[1];10871088    const binary1_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);1089    try func_block.addOperation(binary1_op.op);10901091    const binary2_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);1092    try func_block.addOperation(binary2_op.op);10931094    _ = try ctx.createOperation(ir.Operation.State.init("test.detached", loc));10951096    const limits = OperationSnapshotLimits.inspect(module_op.op, null);1097    try testing.expectEqual(ctx.operationCount(), limits.facts.context_operation_count);1098    try testing.expectEqual(@as(usize, 5), limits.facts.context_operation_count);1099    const capacity = try OperationSnapshotCapacity.derive(limits);1100    try testing.expectEqual(@as(usize, 5), capacity.pointer_count);1101    try testing.expectEqual(1102        capacity.pointer_count * @sizeOf(*ir.Operation),1103        capacity.storage_bytes,1104    );11051106    var snapshot = try OperationSnapshot.init(testing.allocator, limits);1107    defer snapshot.deinit(testing.allocator);1108    snapshot.activate();1109    const operations = snapshot.operations();1110    try testing.expectEqual(@as(usize, 4), operations.len);1111    try testing.expectEqual(@as(usize, 5), snapshot.storage.len);11121113    try testing.expectEqualStrings("test.module", operations[0].name.name);1114    try testing.expectEqualStrings("test.func", operations[1].name.name);1115    try testing.expectEqualStrings("test.binary", operations[2].name.name);1116    try testing.expectEqualStrings("test.binary", operations[3].name.name);11171118    const maximum_pointer_count = std.math.maxInt(usize) / @sizeOf(*ir.Operation);1119    var boundary_limits = limits;1120    boundary_limits.facts.context_operation_count = maximum_pointer_count;1121    const maximum = try OperationSnapshotCapacity.derive(boundary_limits);1122    try testing.expectEqual(1123        maximum_pointer_count * @sizeOf(*ir.Operation),1124        maximum.storage_bytes,1125    );1126    boundary_limits.facts.context_operation_count = maximum_pointer_count + 1;1127    try testing.expectError(1128        error.CapacityOverflow,1129        OperationSnapshotCapacity.derive(boundary_limits),1130    );1131}11321133test "conversion snapshot reuses fixed backing throughout steady traversal" {1134    comptime {1135        @stardustClaim(1136            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_sealed_reuse_transitive_risk"),1137            null,1138            null,1139            null,1140            null,1141            null,1142            null,1143        );1144    }1145    comptime {1146        @stardustClaim(1147            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_sealed_reuse_foreign_risk"),1148            null,1149            null,1150            null,1151            null,1152            null,1153            null,1154        );1155    }11561157    const testing = std.testing;1158    var ctx = try ir.Context.init(testing.allocator, ir.Context.Limits.testing);1159    defer ctx.deinit(testing.allocator);1160    try ctx.allowUnregistered();11611162    const root_op = try ctx.createOperation(1163        ir.Operation.State.init("test.snapshot", .unknown),1164    );1165    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(testing.allocator);1166    var maybe_snapshot: ?OperationSnapshot = null;1167    errdefer {1168        if (phase_allocator.phase() == .initialization) {1169            phase_allocator.abortInitialization();1170        }1171        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();1172        if (maybe_snapshot) |*snapshot| {1173            if (snapshot.phase != .teardown) {1174                snapshot.deinit(phase_allocator.teardownAllocator());1175            }1176        }1177        if (phase_allocator.phase() == .teardown) phase_allocator.deinit();1178    }11791180    maybe_snapshot = try OperationSnapshot.init(1181        phase_allocator.initializationAllocator(),1182        OperationSnapshotLimits.inspect(root_op, null),1183    );1184    const snapshot = &maybe_snapshot.?;1185    const storage_pointer = snapshot.storage.ptr;1186    phase_allocator.seal();1187    snapshot.activate();11881189    for (0..64) |_| {1190        const operations = snapshot.operations();1191        try testing.expectEqual(@as(usize, 1), operations.len);1192        try testing.expectEqual(root_op, operations[0]);1193        try testing.expectEqual(storage_pointer, operations.ptr);1194    }1195    try testing.expectEqual(1196        alloc_phase.PhaseViolations{},1197        phase_allocator.violations(),1198    );11991200    phase_allocator.beginTeardown();1201    snapshot.deinit(phase_allocator.teardownAllocator());1202    maybe_snapshot = null;1203    try testing.expectEqual(1204        alloc_phase.PhaseViolations{},1205        phase_allocator.violations(),1206    );1207    phase_allocator.deinit();1208}12091210test "conversion snapshot rejects foreign Context nesting before activation" {1211    comptime {1212        @stardustClaim(1213            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_context"),1214            null,1215            null,1216            null,1217            null,1218            null,1219            null,1220        );1221    }12221223    const test_dialect = @import("../dialects/fixture/root.zig");1224    var root_context = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);1225    defer root_context.deinit(std.testing.allocator);1226    try root_context.allowUnregistered();1227    var foreign_context = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);1228    defer foreign_context.deinit(std.testing.allocator);1229    try foreign_context.allowUnregistered();12301231    const module_op = try test_dialect.TestDialect.ModuleOp.create(1232        &root_context,1233        .unknown,1234    );1235    const foreign_op = try foreign_context.createOperation(1236        ir.Operation.State.init("test.foreign", .unknown),1237    );1238    try module_op.getBodyBlock().addOperation(foreign_op);1239    defer module_op.getBodyBlock().detachOperation(foreign_op);12401241    try std.testing.expectError(1242        error.ForeignOperationContext,1243        OperationSnapshot.init(1244            std.testing.allocator,1245            OperationSnapshotLimits.inspect(module_op.op, null),1246        ),1247    );1248}12491250test "conversion snapshot initialization survives every allocation failure" {1251    comptime {1252        @stardustClaim(1253            @import("alloc_phase").capacity.witness(OperationSnapshot, "conversion_snapshot_oom_retry"),1254            null,1255            null,1256            null,1257            null,1258            null,1259            null,1260        );1261    }12621263    var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);1264    defer ctx.deinit(std.testing.allocator);1265    try ctx.allowUnregistered();1266    const root_op = try ctx.createOperation(1267        ir.Operation.State.init("test.snapshot", .unknown),1268    );12691270    try std.testing.checkAllAllocationFailures(1271        std.testing.allocator,1272        checkOperationSnapshotInitFailures,1273        .{root_op},1274    );1275    try checkOperationSnapshotInitFailures(std.testing.allocator, root_op);1276}12771278test "applyFullConversion converts nested illegal ops" {1279    const testing = std.testing;1280    const test_dialect = @import("../dialects/fixture/root.zig");12811282    var arena = alloc_arena.Arena.init(std.testing.allocator);1283    defer arena.deinit();1284    const allocator = arena.allocator();12851286    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1287    defer ctx.deinit(allocator);1288    try ctx.allowUnregistered();12891290    const loc = ir.Location.getUnknown();1291    const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);1292    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1293    const module_block = module_op.getBodyBlock();12941295    _ = try module_block.addArgument(i32_type, loc);1296    _ = try module_block.addArgument(i32_type, loc);1297    const arg0 = module_block.arguments.items[0];1298    const arg1 = module_block.arguments.items[1];12991300    const binary_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);1301    try module_block.addOperation(binary_op.op);13021303    var target = ConversionTarget.init(allocator);1304    defer target.deinit();1305    try target.addIllegalOp("test.binary");1306    try target.addLegalDialect("test");13071308    var patterns = rewrite.RewritePatternSet.init(allocator);1309    defer patterns.deinit();13101311    const result = applyFullConversion(allocator, &ctx, module_op.op, &target, &patterns);1312    try testing.expectEqual(ConversionResult.failure, result);1313}13141315test "applyFullConversion succeeds when nested ops converted" {1316    const testing = std.testing;1317    const test_dialect = @import("../dialects/fixture/root.zig");13181319    var arena = alloc_arena.Arena.init(std.testing.allocator);1320    defer arena.deinit();1321    const allocator = arena.allocator();13221323    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1324    defer ctx.deinit(allocator);1325    try ctx.allowUnregistered();13261327    const loc = ir.Location.getUnknown();1328    const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);1329    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1330    const module_block = module_op.getBodyBlock();13311332    _ = try module_block.addArgument(i32_type, loc);1333    _ = try module_block.addArgument(i32_type, loc);1334    const arg0 = module_block.arguments.items[0];1335    const arg1 = module_block.arguments.items[1];13361337    const binary_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);1338    try module_block.addOperation(binary_op.op);13391340    var target = ConversionTarget.init(allocator);1341    defer target.deinit();1342    try target.addIllegalOp("test.binary");1343    try target.addLegalDialect("test");13441345    var patterns = rewrite.RewritePatternSet.init(allocator);1346    defer patterns.deinit();1347    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.binary", 1), dummyRewrite));13481349    const result = applyFullConversion(allocator, &ctx, module_op.op, &target, &patterns);1350    try testing.expectEqual(ConversionResult.success, result);1351}13521353test "applyFullConversion fails when type conversion required" {1354    const testing = std.testing;1355    const test_dialect = @import("../dialects/fixture/root.zig");13561357    var arena = alloc_arena.Arena.init(std.testing.allocator);1358    defer arena.deinit();1359    const allocator = arena.allocator();13601361    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1362    defer ctx.deinit(allocator);1363    try ctx.allowUnregistered();13641365    const loc = ir.Location.getUnknown();1366    const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);1367    const i64_type = try test_dialect.TestDialect.getI64Type(&ctx);13681369    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1370    const module_block = module_op.getBodyBlock();1371    const const_op = try test_dialect.TestDialect.ConstantOp.create(&ctx, loc, i32_type, 7);1372    try module_block.addOperation(const_op.op);13731374    var target = ConversionTarget.init(allocator);1375    defer target.deinit();1376    try target.addLegalDialect("test");13771378    var converter = rewrite.TypeConverter.init(allocator);1379    defer converter.deinit();1380    try converter.addConversion(i32_type, &.{i64_type});13811382    var patterns = rewrite.RewritePatternSet.init(allocator);1383    defer patterns.deinit();13841385    const result = applyFullConversionWithOptions(1386        allocator,1387        &ctx,1388        module_op.op,1389        &target,1390        &patterns,1391        .{ .type_converter = &converter },1392    );1393    try testing.expectEqual(ConversionResult.failure, result);1394}13951396test "applyFullConversion converts types with pattern" {1397    const testing = std.testing;1398    const test_dialect = @import("../dialects/fixture/root.zig");13991400    const Helpers = struct {1401        fn rewriteConstantWithConvertedType(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1402            const td = @import("../dialects/fixture/root.zig");1403            const converter = rewriter.getTypeConverter() orelse return .failure;1404            const result = op.getResult(0) orelse return .failure;1405            const converted_types = converter.convertType(result.type) orelse return .failure;1406            if (converted_types.len != 1) return .failure;1407            const new_type = converted_types[0];14081409            const const_op = td.TestDialect.ConstantOp{ .op = op };1410            const value = const_op.getValue() orelse return .failure;1411            const value_attr = td.TestDialect.getIntegerAttr(rewriter.ir_ctx, value) catch return .failure;14121413            var state = ir.Operation.State.init(td.TestDialect.ConstantOp.operation_name, op.location);1414            state.addTypes(&.{new_type});1415            state.addAttributes(&.{.{ .name = "value", .value = value_attr }});14161417            _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;1418            return .success;1419        }1420    };14211422    var arena = alloc_arena.Arena.init(std.testing.allocator);1423    defer arena.deinit();1424    const allocator = arena.allocator();14251426    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1427    defer ctx.deinit(allocator);1428    try ctx.allowUnregistered();14291430    const loc = ir.Location.getUnknown();1431    const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);1432    const i64_type = try test_dialect.TestDialect.getI64Type(&ctx);14331434    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1435    const module_block = module_op.getBodyBlock();1436    const const_op = try test_dialect.TestDialect.ConstantOp.create(&ctx, loc, i32_type, 11);1437    try module_block.addOperation(const_op.op);14381439    var target = ConversionTarget.init(allocator);1440    defer target.deinit();1441    try target.addLegalDialect("test");14421443    var converter = rewrite.TypeConverter.init(allocator);1444    defer converter.deinit();1445    try converter.addConversion(i32_type, &.{i64_type});14461447    var patterns = rewrite.RewritePatternSet.init(allocator);1448    defer patterns.deinit();1449    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.constant", 1), Helpers.rewriteConstantWithConvertedType));14501451    const result = applyFullConversionWithOptions(1452        allocator,1453        &ctx,1454        module_op.op,1455        &target,1456        &patterns,1457        .{ .type_converter = &converter },1458    );1459    try testing.expectEqual(ConversionResult.success, result);14601461    const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1462    const result_type = head_op.getResult(0).?.type;1463    try testing.expect(result_type.eql(i64_type));1464}14651466test "applyFullConversion respects max_iterations" {1467    const testing = std.testing;1468    const test_dialect = @import("../dialects/fixture/root.zig");14691470    const loc = ir.Location.getUnknown();14711472    {1473        var arena = alloc_arena.Arena.init(std.testing.allocator);1474        defer arena.deinit();1475        const allocator = arena.allocator();14761477        var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1478        defer ctx.deinit(allocator);1479        try ctx.allowUnregistered();14801481        const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1482        const module_block = module_op.getBodyBlock();14831484        var builder = ir.OperationBuilder.init(&ctx);1485        const state = ir.Operation.State.init("test.a", loc);1486        const op = try builder.create(state);1487        try module_block.addOperation(op);14881489        var target = ConversionTarget.init(allocator);1490        defer target.deinit();1491        try target.addLegalDialect("test");1492        try target.addIllegalOp("test.a");1493        try target.addIllegalOp("test.b");14941495        var patterns = rewrite.RewritePatternSet.init(allocator);1496        defer patterns.deinit();1497        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));1498        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.b", 1), rewriteBToC));14991500        const result = applyFullConversionWithOptions(1501            allocator,1502            &ctx,1503            module_op.op,1504            &target,1505            &patterns,1506            .{ .max_iterations = 1 },1507        );1508        try testing.expectEqual(ConversionResult.failure, result);15091510        const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1511        try testing.expectEqualStrings("test.b", head_op.name.name);1512    }15131514    {1515        var arena = alloc_arena.Arena.init(std.testing.allocator);1516        defer arena.deinit();1517        const allocator = arena.allocator();15181519        var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1520        defer ctx.deinit(allocator);1521        try ctx.allowUnregistered();15221523        const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1524        const module_block = module_op.getBodyBlock();15251526        var builder = ir.OperationBuilder.init(&ctx);1527        const state = ir.Operation.State.init("test.a", loc);1528        const op = try builder.create(state);1529        try module_block.addOperation(op);15301531        var target = ConversionTarget.init(allocator);1532        defer target.deinit();1533        try target.addLegalDialect("test");1534        try target.addIllegalOp("test.a");1535        try target.addIllegalOp("test.b");15361537        var patterns = rewrite.RewritePatternSet.init(allocator);1538        defer patterns.deinit();1539        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));1540        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.b", 1), rewriteBToC));15411542        const result = applyFullConversionWithOptions(1543            allocator,1544            &ctx,1545            module_op.op,1546            &target,1547            &patterns,1548            .{ .max_iterations = 2 },1549        );1550        try testing.expectEqual(ConversionResult.success, result);15511552        const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1553        try testing.expectEqualStrings("test.c", head_op.name.name);1554    }1555}15561557test "applyPatternsGreedily prefers higher benefit patterns" {1558    const testing = std.testing;1559    const test_dialect = @import("../dialects/fixture/root.zig");15601561    var arena = alloc_arena.Arena.init(std.testing.allocator);1562    defer arena.deinit();1563    const allocator = arena.allocator();15641565    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1566    defer ctx.deinit(allocator);1567    try ctx.allowUnregistered();15681569    const loc = ir.Location.getUnknown();1570    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1571    const module_block = module_op.getBodyBlock();15721573    var builder = ir.OperationBuilder.init(&ctx);1574    const state = ir.Operation.State.init("test.source", loc);1575    const op = try builder.create(state);1576    try module_block.addOperation(op);15771578    var patterns = rewrite.RewritePatternSet.init(allocator);1579    defer patterns.deinit();1580    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToLow));1581    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 10), rewriteToHigh));15821583    const result = applyPatternsGreedily(1584        allocator,1585        &ctx,1586        module_op.op,1587        &patterns,1588        .{},1589    );1590    try testing.expectEqual(.converged, result.termination);1591    try testing.expect(result.changed);15921593    const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1594    try testing.expectEqualStrings("test.high", head_op.name.name);1595}15961597test "applyPatternsGreedily honors pattern match predicates" {1598    const testing = std.testing;1599    const test_dialect = @import("../dialects/fixture/root.zig");16001601    var arena = alloc_arena.Arena.init(std.testing.allocator);1602    defer arena.deinit();1603    const allocator = arena.allocator();16041605    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1606    defer ctx.deinit(allocator);1607    try ctx.allowUnregistered();16081609    const loc = ir.Location.getUnknown();1610    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1611    const module_block = module_op.getBodyBlock();16121613    var builder = ir.OperationBuilder.init(&ctx);1614    const state = ir.Operation.State.init("test.source", loc);1615    const op = try builder.create(state);1616    try module_block.addOperation(op);16171618    var patterns = rewrite.RewritePatternSet.init(allocator);1619    defer patterns.deinit();1620    try patterns.add(rewrite.RewritePattern.initWithMatch(testRewriteSpec("test.source", 10), matchNever, rewriteToHigh));1621    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToLow));16221623    const result = applyPatternsGreedily(1624        allocator,1625        &ctx,1626        module_op.op,1627        &patterns,1628        .{},1629    );1630    try testing.expectEqual(.converged, result.termination);1631    try testing.expect(result.changed);16321633    const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1634    try testing.expectEqualStrings("test.low", head_op.name.name);1635}16361637test "greedy rewrite iteration storage has an exact erase boundary and fallback" {1638    try std.testing.expectEqual(1639        @as(usize, 2 * 1024),1640        GreedyRewriteIterationStorage.inline_bytes,1641    );1642    try checkGreedyEraseIterationStorage(227, 0, 0, 0, false);1643    try checkGreedyEraseIterationStorage(228, 1, 1, 2_864, false);1644    try checkGreedyEraseIterationStorage(228, 0, 0, 0, true);1645}16461647test "applyPatternsGreedily default rewrite budget handles large modules" {1648    const testing = std.testing;1649    const test_dialect = @import("../dialects/fixture/root.zig");16501651    var arena = alloc_arena.Arena.init(std.testing.allocator);1652    defer arena.deinit();1653    const allocator = arena.allocator();16541655    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1656    defer ctx.deinit(allocator);1657    try ctx.allowUnregistered();16581659    const loc = ir.Location.getUnknown();1660    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1661    const module_block = module_op.getBodyBlock();16621663    var builder = ir.OperationBuilder.init(&ctx);1664    for (0..1024) |_| {1665        const op = try builder.create(ir.Operation.State.init("test.source", loc));1666        try module_block.addOperation(op);1667    }16681669    var patterns = rewrite.RewritePatternSet.init(allocator);1670    defer patterns.deinit();1671    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToHigh));16721673    const result = applyPatternsGreedily(1674        allocator,1675        &ctx,1676        module_op.op,1677        &patterns,1678        .{},1679    );1680    try testing.expectEqual(.converged, result.termination);1681    try testing.expect(result.changed);16821683    var iter = module_block.getOperations();1684    while (iter.next()) |op| {1685        try testing.expectEqualStrings("test.high", op.name.name);1686    }1687}16881689test "applyPatternsGreedily borrows unchanged operation traversal" {1690    const testing = std.testing;1691    const test_dialect = @import("../dialects/fixture/root.zig");16921693    var arena = alloc_arena.Arena.init(testing.allocator);1694    defer arena.deinit();1695    const allocator = arena.allocator();16961697    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1698    defer ctx.deinit(allocator);1699    try ctx.allowUnregistered();17001701    const loc = ir.Location.getUnknown();1702    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1703    const module_block = module_op.getBodyBlock();17041705    var builder = ir.OperationBuilder.init(&ctx);1706    for (0..128) |_| {1707        const op = try builder.create(ir.Operation.State.init("test.source", loc));1708        try module_block.addOperation(op);1709    }17101711    var patterns = rewrite.RewritePatternSet.init(allocator);1712    defer patterns.deinit();1713    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.other", 1), dummyRewrite));1714    try patterns.seal();17151716    var failing = std.testing.FailingAllocator.init(testing.allocator, .{ .fail_index = 0 });1717    const result = applyPatternsGreedily(1718        failing.allocator(),1719        &ctx,1720        module_op.op,1721        &patterns,1722        .{},1723    );1724    try testing.expectEqual(.converged, result.termination);1725    try testing.expect(!result.changed);1726    try testing.expectEqual(@as(usize, 0), failing.alloc_index);1727}17281729test "applyPatternsGreedily excludes new operations encountered ahead" {1730    const testing = std.testing;1731    const test_dialect = @import("../dialects/fixture/root.zig");17321733    var arena = alloc_arena.Arena.init(testing.allocator);1734    defer arena.deinit();1735    const allocator = arena.allocator();17361737    var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1738    defer ctx.deinit(allocator);1739    try ctx.allowUnregistered();17401741    const loc = ir.Location.getUnknown();1742    const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1743    const module_block = module_op.getBodyBlock();17441745    var builder = ir.OperationBuilder.init(&ctx);1746    inline for (&.{ "test.seed", "test.middle", "test.future" }) |name| {1747        try module_block.addOperation(try builder.create(ir.Operation.State.init(name, loc)));1748    }17491750    var patterns = rewrite.RewritePatternSet.init(allocator);1751    defer patterns.deinit();1752    try patterns.add(rewrite.RewritePattern.init(1753        testRewriteSpec("test.seed", 1),1754        rewriteInsertBeforeFutureOp,1755    ));1756    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.new", 1), rewriteToHigh));1757    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.middle", 1), rewriteToHigh));1758    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.future", 1), rewriteToHigh));17591760    const result = applyPatternsGreedily(1761        allocator,1762        &ctx,1763        module_op.op,1764        &patterns,1765        .{1766            .max_iterations = 1,1767            .strictness = .existing_ops,1768        },1769    );1770    try testing.expectEqual(.iteration_limit, result.termination);1771    try testing.expect(result.changed);1772    try expectRewriterBlockNames(module_block, &.{ "test.high", "test.new", "test.high" });1773}17741775test "applyPatternsGreedily rejects foreign Context nesting" {1776    const testing = std.testing;1777    const test_dialect = @import("../dialects/fixture/root.zig");17781779    var root_context = try ir.Context.init(testing.allocator, ir.Context.Limits.testing);1780    defer root_context.deinit(testing.allocator);1781    try root_context.allowUnregistered();1782    var foreign_context = try ir.Context.init(testing.allocator, ir.Context.Limits.testing);1783    defer foreign_context.deinit(testing.allocator);1784    try foreign_context.allowUnregistered();17851786    const module_op = try test_dialect.TestDialect.ModuleOp.create(1787        &root_context,1788        .unknown,1789    );1790    const module_block = module_op.getBodyBlock();1791    const foreign_op = try foreign_context.createOperation(1792        ir.Operation.State.init("test.foreign", .unknown),1793    );1794    try module_block.addOperation(foreign_op);1795    defer module_block.detachOperation(foreign_op);1796    const source_op = try root_context.createOperation(1797        ir.Operation.State.init("test.source", .unknown),1798    );1799    try module_block.addOperation(source_op);18001801    var patterns = rewrite.RewritePatternSet.init(testing.allocator);1802    defer patterns.deinit();1803    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToHigh));18041805    const result = applyPatternsGreedily(1806        testing.allocator,1807        &root_context,1808        module_op.op,1809        &patterns,1810        .{},1811    );1812    try testing.expectEqual(.invalid_context, result.termination);1813    try testing.expect(!result.changed);1814    try testing.expectEqual(1, result.iterations);1815    try testing.expectEqual(0, result.rewrites);1816    try expectRewriterBlockNames(module_block, &.{ "test.foreign", "test.source" });1817    module_block.detachOperation(foreign_op);1818    try module_block.addOperation(foreign_op);1819    const after_mutation = applyPatternsGreedily(1820        testing.allocator,1821        &root_context,1822        module_op.op,1823        &patterns,1824        .{},1825    );1826    try testing.expectEqualDeep(GreedyRewriteResult{1827        .termination = .invalid_context,1828        .changed = true,1829        .iterations = 1,1830        .rewrites = 1,1831    }, after_mutation);1832    try expectRewriterBlockNames(module_block, &.{ "test.high", "test.foreign" });1833}18341835test "applyPatternsGreedily strictness controls new op processing" {1836    const testing = std.testing;1837    const test_dialect = @import("../dialects/fixture/root.zig");18381839    {1840        var arena = alloc_arena.Arena.init(std.testing.allocator);1841        defer arena.deinit();1842        const allocator = arena.allocator();18431844        var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1845        defer ctx.deinit(allocator);1846        try ctx.allowUnregistered();18471848        const loc = ir.Location.getUnknown();1849        const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1850        const module_block = module_op.getBodyBlock();18511852        var builder = ir.OperationBuilder.init(&ctx);1853        const state = ir.Operation.State.init("test.a", loc);1854        const op = try builder.create(state);1855        try module_block.addOperation(op);18561857        var patterns = rewrite.RewritePatternSet.init(allocator);1858        defer patterns.deinit();1859        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));1860        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.b", 1), rewriteBToC));18611862        const result = applyPatternsGreedily(1863            allocator,1864            &ctx,1865            module_op.op,1866            &patterns,1867            .{1868                .max_iterations = 1,1869                .strictness = .existing_ops,1870            },1871        );1872        try testing.expectEqual(.iteration_limit, result.termination);1873        try testing.expect(result.changed);18741875        const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1876        try testing.expectEqualStrings("test.b", head_op.name.name);1877    }18781879    {1880        var arena = alloc_arena.Arena.init(std.testing.allocator);1881        defer arena.deinit();1882        const allocator = arena.allocator();18831884        var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);1885        defer ctx.deinit(allocator);1886        try ctx.allowUnregistered();18871888        const loc = ir.Location.getUnknown();1889        const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);1890        const module_block = module_op.getBodyBlock();18911892        var builder = ir.OperationBuilder.init(&ctx);1893        const state = ir.Operation.State.init("test.a", loc);1894        const op = try builder.create(state);1895        try module_block.addOperation(op);18961897        var patterns = rewrite.RewritePatternSet.init(allocator);1898        defer patterns.deinit();1899        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));1900        try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.b", 1), rewriteBToC));19011902        const result = applyPatternsGreedily(1903            allocator,1904            &ctx,1905            module_op.op,1906            &patterns,1907            .{1908                .max_iterations = 1,1909                .strictness = .existing_and_new_ops,1910            },1911        );1912        try testing.expectEqual(.iteration_limit, result.termination);1913        try testing.expect(result.changed);19141915        const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));1916        try testing.expectEqualStrings("test.c", head_op.name.name);1917    }1918}19191920fn testRewriteSpec(root_op_name: []const u8, benefit: rewrite.PatternBenefit) rewrite.RewritePatternSpec {1921    return .{ .name = root_op_name, .root_op_name = root_op_name, .benefit = benefit };1922}19231924fn dummyRewrite(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {1925    rewriter.eraseOp(op) catch return .failure;1926    return .success;1927}19281929fn expectRewriterBlockNames(block: *ir.Block, expected: []const []const u8) !void {1930    var iter = block.getOperations();1931    for (expected) |name| {1932        const op = iter.next() orelse return error.TestExpectedOperation;1933        try std.testing.expectEqualStrings(name, op.name.name);1934    }1935    try std.testing.expect(iter.next() == null);1936}19371938test "applyPatternsGreedily reports exact iteration and rewrite termination" {1939    try checkGreedyTermination(1940        .{ .max_iterations = 1, .strictness = .existing_ops },1941        .iteration_limit,1942        1,1943        1,1944    );1945    try checkGreedyTermination(1946        .{ .max_iterations = 2, .strictness = .existing_ops },1947        .iteration_limit,1948        2,1949        2,1950    );1951    try checkGreedyTermination(1952        .{ .max_iterations = 3, .strictness = .existing_ops },1953        .converged,1954        3,1955        2,1956    );1957    try checkGreedyTermination(1958        .{ .max_iterations = 0, .strictness = .existing_ops },1959        .converged,1960        3,1961        2,1962    );1963    try checkGreedyTermination(.{ .max_rewrites = 1 }, .rewrite_limit, 1, 1);1964    try checkGreedyTermination(.{ .max_rewrites = 2 }, .rewrite_limit, 1, 2);1965    try checkGreedyTermination(.{ .max_rewrites = 3 }, .converged, 2, 2);1966}19671968fn checkGreedyTermination(1969    config: GreedyRewriteConfig,1970    termination: GreedyRewriteResult.Termination,1971    iterations: u32,1972    rewrites: u32,1973) !void {1974    const expected = GreedyRewriteResult{1975        .termination = termination,1976        .changed = true,1977        .iterations = iterations,1978        .rewrites = rewrites,1979    };1980    const fixture = @import("../dialects/fixture/root.zig");1981    const allocator = std.testing.allocator;1982    var context = try ir.Context.init(allocator, ir.Context.Limits.testing);1983    defer context.deinit(allocator);1984    try context.allowUnregistered();1985    const module = try fixture.TestDialect.ModuleOp.create(&context, .unknown);1986    const block = module.getBodyBlock();1987    const source = try context.createOperation(ir.Operation.State.init("test.a", .unknown));1988    try block.addOperation(source);1989    var patterns = rewrite.RewritePatternSet.init(allocator);1990    defer patterns.deinit();1991    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));1992    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.b", 1), rewriteBToC));1993    const result = applyPatternsGreedily(allocator, &context, module.op, &patterns, config);1994    try std.testing.expectEqualDeep(expected, result);1995    try expectRewriterBlockNames(block, if (expected.rewrites == 1) &.{"test.b"} else &.{"test.c"});1996    const settled = applyPatternsGreedily(allocator, &context, module.op, &patterns, .{});1997    try std.testing.expectEqualDeep(GreedyRewriteResult{1998        .termination = .converged,1999        .changed = expected.rewrites == 1,2000        .iterations = if (expected.rewrites == 1) 2 else 1,2001        .rewrites = if (expected.rewrites == 1) 1 else 0,2002    }, settled);2003}20042005test "applyPatternsGreedily reports pattern admission refusal before traversal" {2006    const fixture = @import("../dialects/fixture/root.zig");2007    const allocator = std.testing.allocator;2008    var context = try ir.Context.init(allocator, ir.Context.Limits.testing);2009    defer context.deinit(allocator);2010    const module = try fixture.TestDialect.ModuleOp.create(&context, .unknown);2011    var failing = std.testing.FailingAllocator.init(allocator, .{});2012    var patterns = rewrite.RewritePatternSet.init(failing.allocator());2013    defer patterns.deinit();2014    try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.a", 1), rewriteAToB));2015    failing.fail_index = failing.alloc_index;2016    const result = applyPatternsGreedily(allocator, &context, module.op, &patterns, .{});2017    const refused = GreedyRewriteResult{ .termination = .invalid_patterns };2018    try std.testing.expectEqualDeep(refused, result);2019    try std.testing.expect(failing.has_induced_failure);2020    failing.fail_index = std.math.maxInt(usize);2021    const retried = applyPatternsGreedily(allocator, &context, module.op, &patterns, .{});2022    try std.testing.expectEqualDeep(GreedyRewriteResult{2023        .termination = .converged,2024        .iterations = 1,2025    }, retried);2026}