lib/choir/src/passes/conversion.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

   1 const std = @import("std");
   2 const alloc_observe = @import("alloc_observe");
   3 const alloc_arena = @import("alloc_arena");
   4 const alloc_phase = @import("alloc_phase");
   5 const ir = @import("../core/root.zig");
   6 const rewrite = ir.rewrite;
   7 
   8 pub const Legality = enum {
   9     legal,
  10     recursively_legal,
  11     dynamic,
  12     illegal,
  13     unknown,
  14 };
  15 
  16 pub const ConversionTarget = struct {
  17     allocator: std.mem.Allocator,
  18 
  19     legal_ops: std.StringHashMap(void),
  20 
  21     dynamic_ops: std.StringHashMap(*const fn (*ir.Operation) bool),
  22 
  23     recursively_legal_ops: std.StringHashMap(void),
  24 
  25     illegal_ops: std.StringHashMap(void),
  26 
  27     legal_dialects: std.StringHashMap(void),
  28 
  29     recursively_legal_dialects: std.StringHashMap(void),
  30 
  31     illegal_dialects: std.StringHashMap(void),
  32 
  33     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     }
  45 
  46     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     }
  55 
  56     pub fn addLegalOp(self: *ConversionTarget, op_name: []const u8) !void {
  57         try self.legal_ops.put(op_name, {});
  58     }
  59 
  60     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     }
  67 
  68     pub fn addRecursivelyLegalOp(self: *ConversionTarget, op_name: []const u8) !void {
  69         try self.recursively_legal_ops.put(op_name, {});
  70     }
  71 
  72     pub fn addIllegalOp(self: *ConversionTarget, op_name: []const u8) !void {
  73         try self.illegal_ops.put(op_name, {});
  74     }
  75 
  76     pub fn addLegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {
  77         try self.legal_dialects.put(dialect_name, {});
  78     }
  79 
  80     pub fn addRecursivelyLegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {
  81         try self.recursively_legal_dialects.put(dialect_name, {});
  82     }
  83 
  84     pub fn addIllegalDialect(self: *ConversionTarget, dialect_name: []const u8) !void {
  85         try self.illegal_dialects.put(dialect_name, {});
  86     }
  87 
  88     pub fn getOpLegality(self: *const ConversionTarget, op: *ir.Operation) Legality {
  89         const op_name = op.name.name;
  90 
  91         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         }
 103 
 104         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         }
 114 
 115         return .unknown;
 116     }
 117 
 118     pub fn isRecursivelyLegal(self: *const ConversionTarget, op: *ir.Operation) bool {
 119         return self.getOpLegality(op) == .recursively_legal;
 120     }
 121 
 122     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     }
 126 
 127     pub fn isIllegal(self: *const ConversionTarget, op: *ir.Operation) bool {
 128         return self.getOpLegality(op) == .illegal;
 129     }
 130 };
 131 
 132 pub const ConversionResult = enum {
 133     success,
 134     failure,
 135 };
 136 
 137 pub const ConversionOptions = struct {
 138     type_converter: ?*const rewrite.TypeConverter = null,
 139     allow_unknown_ops: ?bool = null,
 140     max_iterations: u32 = 100,
 141 };
 142 
 143 pub 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 }
 152 
 153 pub 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();
 164 
 165     return runConversion(&rewriter, op, target, patterns, false, options);
 166 }
 167 
 168 pub 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 }
 177 
 178 pub 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();
 189 
 190     return runConversion(&rewriter, op, target, patterns, true, options);
 191 }
 192 
 193 const OperationSnapshotFacts = struct {
 194     context_operation_count: usize,
 195 };
 196 
 197 const OperationSnapshotLimits = struct {
 198     root_op: *ir.Operation,
 199     target: ?*const ConversionTarget,
 200     facts: OperationSnapshotFacts,
 201 
 202     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 };
 215 
 216 const OperationSnapshotCapacity = struct {
 217     facts: OperationSnapshotFacts,
 218     pointer_count: usize,
 219     storage_bytes: usize,
 220 
 221     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 };
 236 
 237 pub 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     };
 315 
 316     phase: alloc_phase.capacity.Phase,
 317     capacity: OperationSnapshotCapacity,
 318     storage: []*ir.Operation,
 319     operation_count: usize,
 320 
 321     pub const Limits = OperationSnapshotLimits;
 322     pub const Capacity = OperationSnapshotCapacity;
 323 
 324     const FillContext = struct {
 325         root_context: *ir.Context,
 326         target: ?*const ConversionTarget,
 327         storage: []*ir.Operation,
 328         operation_count: usize,
 329 
 330         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     };
 352 
 353     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);
 360 
 361         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);
 373 
 374         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     }
 383 
 384     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     }
 391 
 392     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     }
 399 
 400     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     }
 413 
 414     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 };
 422 
 423 comptime {
 424     alloc_phase.capacity.requireAllocatorExactOwnerShape(OperationSnapshot);
 425 }
 426 
 427 fn 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 }
 440 
 441 const CollectNestedOpsContext = struct {
 442     allocator: std.mem.Allocator,
 443     target: ?*const ConversionTarget,
 444     worklist: *std.ArrayListUnmanaged(*ir.Operation),
 445 
 446     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 };
 454 
 455 const ConversionWorklist = struct {
 456     initial: OperationSnapshot,
 457     created: std.ArrayListUnmanaged(*ir.Operation),
 458 
 459     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     }
 474 
 475     fn deinit(
 476         self: *ConversionWorklist,
 477         allocator: std.mem.Allocator,
 478     ) void {
 479         self.created.deinit(allocator);
 480         self.initial.deinit(allocator);
 481     }
 482 
 483     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     }
 490 
 491     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     }
 500 
 501     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 };
 510 
 511 fn 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     }
 515 
 516     for (op.results.items) |*result| {
 517         if (!converter.isTypeLegal(result.type)) return false;
 518     }
 519 
 520     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     }
 528 
 529     return true;
 530 }
 531 
 532 fn resolveAllowUnknownOps(options: ConversionOptions, require_full: bool) bool {
 533     return options.allow_unknown_ops orelse !require_full;
 534 }
 535 
 536 fn 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;
 546 
 547     if (options.type_converter) |converter| {
 548         if (!opTypesLegal(op, converter)) return false;
 549     }
 550 
 551     return true;
 552 }
 553 
 554 fn 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 }
 562 
 563 fn 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);
 577 
 578     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);
 582 
 583     while (changed and iterations < max_iterations) {
 584         changed = false;
 585         iterations += 1;
 586 
 587         const initial_worklist_len = worklist.len();
 588 
 589         var i: usize = 0;
 590         while (i < initial_worklist_len) {
 591             const op = worklist.get(i);
 592 
 593             if (rewriter.isScheduledForErase(op)) {
 594                 i += 1;
 595                 continue;
 596             }
 597 
 598             if (isOpLegal(target, op, options, allow_unknown_ops)) {
 599                 i += 1;
 600                 continue;
 601             }
 602 
 603             var pattern_applied = false;
 604             for (patterns.getMatchingPatterns(op)) |pattern| {
 605                 if (pattern.matchesAfterRoot(op)) {
 606                     const created_before = rewriter.created_ops.items.len;
 607 
 608                     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;
 617 
 618                         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             }
 629 
 630             if (!pattern_applied and mustLegalizeOp(target, op, allow_unknown_ops, require_full)) {
 631                 return .failure;
 632             }
 633 
 634             i += 1;
 635         }
 636     }
 637 
 638     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     }
 647 
 648     rewriter.finalize(root_op);
 649     return .success;
 650 }
 651 
 652 pub const GreedyRewriteStrictness = enum {
 653     existing_ops,
 654     existing_and_new_ops,
 655 };
 656 
 657 pub const GreedyRewriteConfig = struct {
 658     max_iterations: u32 = 10,
 659     max_rewrites: u32 = 0,
 660     strictness: GreedyRewriteStrictness = .existing_and_new_ops,
 661 };
 662 
 663 const GreedyRewriteTermination = enum {
 664     converged,
 665     iteration_limit,
 666     rewrite_limit,
 667     invalid_context,
 668     invalid_patterns,
 669 };
 670 
 671 pub 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,
 677 
 678     pub const Termination: type = GreedyRewriteTermination;
 679 };
 680 
 681 const GreedyRewriteIterationStorage = struct {
 682     pub const inline_bytes: usize = 2 * 1024;
 683 
 684     buffer: [inline_bytes]u8 = undefined,
 685     fallback_allocator: std.mem.Allocator,
 686     stack_fallback: alloc_observe.buffer.First = undefined,
 687 
 688     fn init(fallback_allocator: std.mem.Allocator) GreedyRewriteIterationStorage {
 689         return .{ .fallback_allocator = fallback_allocator };
 690     }
 691 
 692     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 };
 697 
 698 fn 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,
 708 
 709         const Self = @This();
 710 
 711         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;
 718 
 719             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         }
 729 
 730         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         }
 734 
 735         fn assertInterrupted(self: *const Self) void {
 736             if (self.limit_reached) return;
 737             std.debug.assert(self.invalid_context);
 738         }
 739     };
 740 }
 741 
 742 pub 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 };
 750 
 751     return applyPatternsGreedilyFromSource(
 752         allocator,
 753         ir_ctx,
 754         root_op,
 755         patterns,
 756         config,
 757     );
 758 }
 759 
 760 pub 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;
 771 
 772     var result = GreedyRewriteResult{ .termination = .iteration_limit };
 773 
 774     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);
 780 
 781         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         }
 795 
 796         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         }
 808 
 809         result.changed = result.changed or walk.changed;
 810         if (!walk.changed) {
 811             result.termination = .converged;
 812             return result;
 813         }
 814     }
 815 
 816     return result;
 817 }
 818 
 819 test "conversion target" {
 820     const testing = std.testing;
 821     const allocator = testing.allocator;
 822 
 823     var target = ConversionTarget.init(allocator);
 824     defer target.deinit();
 825 
 826     try target.addLegalDialect("wasm");
 827 
 828     try target.addIllegalDialect("arith");
 829 
 830     var arena = alloc_arena.Arena.init(std.testing.allocator);
 831     defer arena.deinit();
 832 
 833     var ctx = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
 834     defer ctx.deinit(arena.allocator());
 835     try ctx.allowUnregistered();
 836 
 837     const state = ir.Operation.State.init("arith.addi", ir.Location.getUnknown());
 838     const op = try ctx.createOperation(state);
 839 
 840     try testing.expect(target.isIllegal(op));
 841 
 842     try target.addLegalOp("arith.addi");
 843     try testing.expect(target.isLegal(op));
 844 }
 845 
 846 test "conversion target recursively legal op skips nested illegal operations" {
 847     const testing = std.testing;
 848 
 849     var arena = alloc_arena.Arena.init(std.testing.allocator);
 850     defer arena.deinit();
 851     const allocator = arena.allocator();
 852 
 853     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
 854     defer ctx.deinit(allocator);
 855     try ctx.allowUnregistered();
 856 
 857     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();
 862 
 863     const child_state = ir.Operation.State.init("test.child", loc);
 864     const child = try ctx.createOperation(child_state);
 865     try block.addOperation(child);
 866 
 867     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));
 873 
 874     var patterns = rewrite.RewritePatternSet.init(allocator);
 875     defer patterns.deinit();
 876 
 877     try testing.expectEqual(
 878         ConversionResult.success,
 879         applyFullConversion(allocator, &ctx, parent, &target, &patterns),
 880     );
 881 }
 882 
 883 test "conversion modes distinguish unknown and illegal operations" {
 884     const testing = std.testing;
 885 
 886     var arena = alloc_arena.Arena.init(std.testing.allocator);
 887     defer arena.deinit();
 888     const allocator = arena.allocator();
 889 
 890     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
 891     defer ctx.deinit(allocator);
 892     try ctx.allowUnregistered();
 893 
 894     var target = ConversionTarget.init(allocator);
 895     defer target.deinit();
 896 
 897     var patterns = rewrite.RewritePatternSet.init(allocator);
 898     defer patterns.deinit();
 899 
 900     const loc = ir.Location.getUnknown();
 901 
 902     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     );
 907 
 908     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     );
 913 
 914     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     );
 926 
 927     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 }
 934 
 935 fn 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");
 944 
 945     var arena = alloc_arena.Arena.init(testing.allocator);
 946     defer arena.deinit();
 947     const allocator = arena.allocator();
 948 
 949     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
 950     defer ctx.deinit(allocator);
 951     try ctx.allowUnregistered();
 952 
 953     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     }
 964 
 965     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();
 972 
 973     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 }
 992 
 993 fn 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 }
 998 
 999 fn 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 }
1004 
1005 fn matchNever(_: *ir.Operation) bool {
1006     return false;
1007 }
1008 
1009 fn 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 }
1014 
1015 fn 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 }
1020 
1021 fn 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 }
1029 
1030 fn 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 }
1042 
1043 test "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     }
1066 
1067     const testing = std.testing;
1068     const test_dialect = @import("../dialects/fixture/root.zig");
1069 
1070     var ctx = try ir.Context.init(testing.allocator, ir.Context.Limits.testing);
1071     defer ctx.deinit(testing.allocator);
1072     try ctx.allowUnregistered();
1073 
1074     const loc = ir.Location.getUnknown();
1075     const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
1076 
1077     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1078     const module_block = module_op.getBodyBlock();
1079 
1080     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);
1082 
1083     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];
1087 
1088     const binary1_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);
1089     try func_block.addOperation(binary1_op.op);
1090 
1091     const binary2_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);
1092     try func_block.addOperation(binary2_op.op);
1093 
1094     _ = try ctx.createOperation(ir.Operation.State.init("test.detached", loc));
1095 
1096     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     );
1105 
1106     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);
1112 
1113     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);
1117 
1118     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 }
1132 
1133 test "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     }
1156 
1157     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();
1161 
1162     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     }
1179 
1180     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();
1188 
1189     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     );
1199 
1200     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 }
1209 
1210 test "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     }
1222 
1223     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();
1230 
1231     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);
1240 
1241     try std.testing.expectError(
1242         error.ForeignOperationContext,
1243         OperationSnapshot.init(
1244             std.testing.allocator,
1245             OperationSnapshotLimits.inspect(module_op.op, null),
1246         ),
1247     );
1248 }
1249 
1250 test "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     }
1262 
1263     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     );
1269 
1270     try std.testing.checkAllAllocationFailures(
1271         std.testing.allocator,
1272         checkOperationSnapshotInitFailures,
1273         .{root_op},
1274     );
1275     try checkOperationSnapshotInitFailures(std.testing.allocator, root_op);
1276 }
1277 
1278 test "applyFullConversion converts nested illegal ops" {
1279     const testing = std.testing;
1280     const test_dialect = @import("../dialects/fixture/root.zig");
1281 
1282     var arena = alloc_arena.Arena.init(std.testing.allocator);
1283     defer arena.deinit();
1284     const allocator = arena.allocator();
1285 
1286     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1287     defer ctx.deinit(allocator);
1288     try ctx.allowUnregistered();
1289 
1290     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();
1294 
1295     _ = 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];
1299 
1300     const binary_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);
1301     try module_block.addOperation(binary_op.op);
1302 
1303     var target = ConversionTarget.init(allocator);
1304     defer target.deinit();
1305     try target.addIllegalOp("test.binary");
1306     try target.addLegalDialect("test");
1307 
1308     var patterns = rewrite.RewritePatternSet.init(allocator);
1309     defer patterns.deinit();
1310 
1311     const result = applyFullConversion(allocator, &ctx, module_op.op, &target, &patterns);
1312     try testing.expectEqual(ConversionResult.failure, result);
1313 }
1314 
1315 test "applyFullConversion succeeds when nested ops converted" {
1316     const testing = std.testing;
1317     const test_dialect = @import("../dialects/fixture/root.zig");
1318 
1319     var arena = alloc_arena.Arena.init(std.testing.allocator);
1320     defer arena.deinit();
1321     const allocator = arena.allocator();
1322 
1323     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1324     defer ctx.deinit(allocator);
1325     try ctx.allowUnregistered();
1326 
1327     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();
1331 
1332     _ = 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];
1336 
1337     const binary_op = try test_dialect.TestDialect.BinaryOp.create(&ctx, loc, arg0, arg1);
1338     try module_block.addOperation(binary_op.op);
1339 
1340     var target = ConversionTarget.init(allocator);
1341     defer target.deinit();
1342     try target.addIllegalOp("test.binary");
1343     try target.addLegalDialect("test");
1344 
1345     var patterns = rewrite.RewritePatternSet.init(allocator);
1346     defer patterns.deinit();
1347     try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.binary", 1), dummyRewrite));
1348 
1349     const result = applyFullConversion(allocator, &ctx, module_op.op, &target, &patterns);
1350     try testing.expectEqual(ConversionResult.success, result);
1351 }
1352 
1353 test "applyFullConversion fails when type conversion required" {
1354     const testing = std.testing;
1355     const test_dialect = @import("../dialects/fixture/root.zig");
1356 
1357     var arena = alloc_arena.Arena.init(std.testing.allocator);
1358     defer arena.deinit();
1359     const allocator = arena.allocator();
1360 
1361     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1362     defer ctx.deinit(allocator);
1363     try ctx.allowUnregistered();
1364 
1365     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);
1368 
1369     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);
1373 
1374     var target = ConversionTarget.init(allocator);
1375     defer target.deinit();
1376     try target.addLegalDialect("test");
1377 
1378     var converter = rewrite.TypeConverter.init(allocator);
1379     defer converter.deinit();
1380     try converter.addConversion(i32_type, &.{i64_type});
1381 
1382     var patterns = rewrite.RewritePatternSet.init(allocator);
1383     defer patterns.deinit();
1384 
1385     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 }
1395 
1396 test "applyFullConversion converts types with pattern" {
1397     const testing = std.testing;
1398     const test_dialect = @import("../dialects/fixture/root.zig");
1399 
1400     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];
1408 
1409             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;
1412 
1413             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 }});
1416 
1417             _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;
1418             return .success;
1419         }
1420     };
1421 
1422     var arena = alloc_arena.Arena.init(std.testing.allocator);
1423     defer arena.deinit();
1424     const allocator = arena.allocator();
1425 
1426     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1427     defer ctx.deinit(allocator);
1428     try ctx.allowUnregistered();
1429 
1430     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);
1433 
1434     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);
1438 
1439     var target = ConversionTarget.init(allocator);
1440     defer target.deinit();
1441     try target.addLegalDialect("test");
1442 
1443     var converter = rewrite.TypeConverter.init(allocator);
1444     defer converter.deinit();
1445     try converter.addConversion(i32_type, &.{i64_type});
1446 
1447     var patterns = rewrite.RewritePatternSet.init(allocator);
1448     defer patterns.deinit();
1449     try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.constant", 1), Helpers.rewriteConstantWithConvertedType));
1450 
1451     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);
1460 
1461     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 }
1465 
1466 test "applyFullConversion respects max_iterations" {
1467     const testing = std.testing;
1468     const test_dialect = @import("../dialects/fixture/root.zig");
1469 
1470     const loc = ir.Location.getUnknown();
1471 
1472     {
1473         var arena = alloc_arena.Arena.init(std.testing.allocator);
1474         defer arena.deinit();
1475         const allocator = arena.allocator();
1476 
1477         var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1478         defer ctx.deinit(allocator);
1479         try ctx.allowUnregistered();
1480 
1481         const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1482         const module_block = module_op.getBodyBlock();
1483 
1484         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);
1488 
1489         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");
1494 
1495         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));
1499 
1500         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);
1509 
1510         const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1511         try testing.expectEqualStrings("test.b", head_op.name.name);
1512     }
1513 
1514     {
1515         var arena = alloc_arena.Arena.init(std.testing.allocator);
1516         defer arena.deinit();
1517         const allocator = arena.allocator();
1518 
1519         var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1520         defer ctx.deinit(allocator);
1521         try ctx.allowUnregistered();
1522 
1523         const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1524         const module_block = module_op.getBodyBlock();
1525 
1526         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);
1530 
1531         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");
1536 
1537         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));
1541 
1542         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);
1551 
1552         const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1553         try testing.expectEqualStrings("test.c", head_op.name.name);
1554     }
1555 }
1556 
1557 test "applyPatternsGreedily prefers higher benefit patterns" {
1558     const testing = std.testing;
1559     const test_dialect = @import("../dialects/fixture/root.zig");
1560 
1561     var arena = alloc_arena.Arena.init(std.testing.allocator);
1562     defer arena.deinit();
1563     const allocator = arena.allocator();
1564 
1565     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1566     defer ctx.deinit(allocator);
1567     try ctx.allowUnregistered();
1568 
1569     const loc = ir.Location.getUnknown();
1570     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1571     const module_block = module_op.getBodyBlock();
1572 
1573     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);
1577 
1578     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));
1582 
1583     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);
1592 
1593     const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1594     try testing.expectEqualStrings("test.high", head_op.name.name);
1595 }
1596 
1597 test "applyPatternsGreedily honors pattern match predicates" {
1598     const testing = std.testing;
1599     const test_dialect = @import("../dialects/fixture/root.zig");
1600 
1601     var arena = alloc_arena.Arena.init(std.testing.allocator);
1602     defer arena.deinit();
1603     const allocator = arena.allocator();
1604 
1605     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1606     defer ctx.deinit(allocator);
1607     try ctx.allowUnregistered();
1608 
1609     const loc = ir.Location.getUnknown();
1610     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1611     const module_block = module_op.getBodyBlock();
1612 
1613     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);
1617 
1618     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));
1622 
1623     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);
1632 
1633     const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1634     try testing.expectEqualStrings("test.low", head_op.name.name);
1635 }
1636 
1637 test "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 }
1646 
1647 test "applyPatternsGreedily default rewrite budget handles large modules" {
1648     const testing = std.testing;
1649     const test_dialect = @import("../dialects/fixture/root.zig");
1650 
1651     var arena = alloc_arena.Arena.init(std.testing.allocator);
1652     defer arena.deinit();
1653     const allocator = arena.allocator();
1654 
1655     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1656     defer ctx.deinit(allocator);
1657     try ctx.allowUnregistered();
1658 
1659     const loc = ir.Location.getUnknown();
1660     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1661     const module_block = module_op.getBodyBlock();
1662 
1663     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     }
1668 
1669     var patterns = rewrite.RewritePatternSet.init(allocator);
1670     defer patterns.deinit();
1671     try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToHigh));
1672 
1673     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);
1682 
1683     var iter = module_block.getOperations();
1684     while (iter.next()) |op| {
1685         try testing.expectEqualStrings("test.high", op.name.name);
1686     }
1687 }
1688 
1689 test "applyPatternsGreedily borrows unchanged operation traversal" {
1690     const testing = std.testing;
1691     const test_dialect = @import("../dialects/fixture/root.zig");
1692 
1693     var arena = alloc_arena.Arena.init(testing.allocator);
1694     defer arena.deinit();
1695     const allocator = arena.allocator();
1696 
1697     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1698     defer ctx.deinit(allocator);
1699     try ctx.allowUnregistered();
1700 
1701     const loc = ir.Location.getUnknown();
1702     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1703     const module_block = module_op.getBodyBlock();
1704 
1705     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     }
1710 
1711     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();
1715 
1716     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 }
1728 
1729 test "applyPatternsGreedily excludes new operations encountered ahead" {
1730     const testing = std.testing;
1731     const test_dialect = @import("../dialects/fixture/root.zig");
1732 
1733     var arena = alloc_arena.Arena.init(testing.allocator);
1734     defer arena.deinit();
1735     const allocator = arena.allocator();
1736 
1737     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1738     defer ctx.deinit(allocator);
1739     try ctx.allowUnregistered();
1740 
1741     const loc = ir.Location.getUnknown();
1742     const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1743     const module_block = module_op.getBodyBlock();
1744 
1745     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     }
1749 
1750     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));
1759 
1760     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 }
1774 
1775 test "applyPatternsGreedily rejects foreign Context nesting" {
1776     const testing = std.testing;
1777     const test_dialect = @import("../dialects/fixture/root.zig");
1778 
1779     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();
1785 
1786     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);
1800 
1801     var patterns = rewrite.RewritePatternSet.init(testing.allocator);
1802     defer patterns.deinit();
1803     try patterns.add(rewrite.RewritePattern.init(testRewriteSpec("test.source", 1), rewriteToHigh));
1804 
1805     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 }
1834 
1835 test "applyPatternsGreedily strictness controls new op processing" {
1836     const testing = std.testing;
1837     const test_dialect = @import("../dialects/fixture/root.zig");
1838 
1839     {
1840         var arena = alloc_arena.Arena.init(std.testing.allocator);
1841         defer arena.deinit();
1842         const allocator = arena.allocator();
1843 
1844         var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1845         defer ctx.deinit(allocator);
1846         try ctx.allowUnregistered();
1847 
1848         const loc = ir.Location.getUnknown();
1849         const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1850         const module_block = module_op.getBodyBlock();
1851 
1852         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);
1856 
1857         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));
1861 
1862         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);
1874 
1875         const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1876         try testing.expectEqualStrings("test.b", head_op.name.name);
1877     }
1878 
1879     {
1880         var arena = alloc_arena.Arena.init(std.testing.allocator);
1881         defer arena.deinit();
1882         const allocator = arena.allocator();
1883 
1884         var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1885         defer ctx.deinit(allocator);
1886         try ctx.allowUnregistered();
1887 
1888         const loc = ir.Location.getUnknown();
1889         const module_op = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1890         const module_block = module_op.getBodyBlock();
1891 
1892         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);
1896 
1897         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));
1901 
1902         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);
1914 
1915         const head_op: *ir.Operation = @ptrCast(@alignCast(module_block.operations.head.?));
1916         try testing.expectEqualStrings("test.c", head_op.name.name);
1917     }
1918 }
1919 
1920 fn 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 }
1923 
1924 fn dummyRewrite(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
1925     rewriter.eraseOp(op) catch return .failure;
1926     return .success;
1927 }
1928 
1929 fn 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 }
1937 
1938 test "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 }
1967 
1968 fn 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 }
2004 
2005 test "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 }