lib/choir/src/passes/optimizations.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

   1 const std = @import("std");
   2 const ir = @import("../core/root.zig");
   3 const rewrite = ir.rewrite;
   4 const pass_mod = @import("pass/root.zig");
   5 const registry_mod = @import("pipeline.zig");
   6 const textual_pipeline = @import("textual.zig");
   7 const canonicalization = @import("canonicalization.zig");
   8 const control_flow = @import("control.zig");
   9 const cse = @import("cse/root.zig");
  10 const effects = @import("effects.zig");
  11 const dialects = @import("../dialects/root.zig");
  12 
  13 const PatternRewriter = rewrite.PatternRewriter;
  14 const Pass = pass_mod.Pass;
  15 const PassContext = pass_mod.PassContext;
  16 const PassResult = pass_mod.PassResult;
  17 
  18 const arith = dialects.ArithDialect;
  19 const memref = dialects.MemrefDialect;
  20 const scf = dialects.ScfDialect;
  21 
  22 const maximum_sccp_operation_depth: usize = 256;
  23 
  24 pub const dead_code_elimination_pass_name = "choir-dce";
  25 pub const dead_code_elimination_pass_description =
  26     "Dead code elimination for trivially dead operations";
  27 pub const common_subexpression_elimination_pass_name = cse.common_subexpression_elimination_pass_name;
  28 pub const common_subexpression_elimination_pass_description = cse.common_subexpression_elimination_pass_description;
  29 pub const constant_folding_pass_name = "choir-const-fold";
  30 pub const constant_folding_pass_description =
  31     "Constant folding for scalar arith operations";
  32 pub const sparse_conditional_constant_propagation_pass_name = "choir-sccp";
  33 pub const sparse_conditional_constant_propagation_pass_description =
  34     "Sparse conditional constant propagation for scalar values";
  35 pub const load_store_forwarding_pass_name = "choir-load-store-forward";
  36 pub const load_store_forwarding_pass_description =
  37     "Load/store forwarding for simple memref patterns";
  38 pub const dead_store_elimination_pass_name = "choir-dse";
  39 pub const dead_store_elimination_pass_description =
  40     "Dead store elimination for simple block-local memref overwrites";
  41 pub const loop_invariant_code_motion_pass_name = "choir-licm";
  42 pub const loop_invariant_code_motion_pass_description =
  43     "Loop-invariant code motion for scf.for";
  44 pub const equality_saturation_pass_name = "choir-eqsat-arith";
  45 pub const equality_saturation_pass_description =
  46     "Equality saturation over pure scalar arith operations";
  47 pub const default_optimization_pipeline_name = "choir-cleanup";
  48 pub const default_optimization_pipeline_description =
  49     "Run the standard Choir canonicalization and cleanup optimization pipeline";
  50 
  51 pub fn createDeadCodeEliminationPass() Pass {
  52     return .{
  53         .name = dead_code_elimination_pass_name,
  54         .description = dead_code_elimination_pass_description,
  55         .run_fn = runDeadCodeElimination,
  56         .mutation_scope = .isolated,
  57     };
  58 }
  59 
  60 pub const createCommonSubexpressionEliminationPass = cse.createCommonSubexpressionEliminationPass;
  61 
  62 const promotion = @import("promotion.zig");
  63 pub const createMemoryPromotionPass = promotion.createMemoryPromotionPass;
  64 pub const memory_promotion_pass_name = promotion.memory_promotion_pass_name;
  65 
  66 pub fn createConstantFoldingPass() Pass {
  67     return .{
  68         .name = constant_folding_pass_name,
  69         .description = constant_folding_pass_description,
  70         .run_fn = runConstantFolding,
  71         .mutation_scope = .isolated,
  72     };
  73 }
  74 
  75 pub fn createSparseConditionalConstantPropagationPass() Pass {
  76     return .{
  77         .name = sparse_conditional_constant_propagation_pass_name,
  78         .description = sparse_conditional_constant_propagation_pass_description,
  79         .run_fn = runSparseConditionalConstantPropagation,
  80         .mutation_scope = .isolated,
  81     };
  82 }
  83 
  84 pub fn createLoadStoreForwardingPass() Pass {
  85     return .{
  86         .name = load_store_forwarding_pass_name,
  87         .description = load_store_forwarding_pass_description,
  88         .run_fn = runLoadStoreForwarding,
  89         .mutation_scope = .isolated,
  90     };
  91 }
  92 
  93 pub fn createDeadStoreEliminationPass() Pass {
  94     return .{
  95         .name = dead_store_elimination_pass_name,
  96         .description = dead_store_elimination_pass_description,
  97         .run_fn = runDeadStoreElimination,
  98         .mutation_scope = .isolated,
  99     };
 100 }
 101 
 102 pub fn createLoopInvariantCodeMotionPass() Pass {
 103     return .{
 104         .name = loop_invariant_code_motion_pass_name,
 105         .description = loop_invariant_code_motion_pass_description,
 106         .run_fn = runLoopInvariantCodeMotion,
 107         .mutation_scope = .whole_module,
 108     };
 109 }
 110 
 111 pub const dead_code_elimination_pass_registration = registry_mod.PassRegistration{
 112     .name = dead_code_elimination_pass_name,
 113     .description = dead_code_elimination_pass_description,
 114     .pass = createDeadCodeEliminationPass(),
 115 };
 116 
 117 pub const common_subexpression_elimination_pass_registration = cse.common_subexpression_elimination_pass_registration;
 118 
 119 pub const constant_folding_pass_registration = registry_mod.PassRegistration{
 120     .name = constant_folding_pass_name,
 121     .description = constant_folding_pass_description,
 122     .pass = createConstantFoldingPass(),
 123 };
 124 
 125 pub const sparse_conditional_constant_propagation_pass_registration = registry_mod.PassRegistration{
 126     .name = sparse_conditional_constant_propagation_pass_name,
 127     .description = sparse_conditional_constant_propagation_pass_description,
 128     .pass = createSparseConditionalConstantPropagationPass(),
 129 };
 130 
 131 pub const load_store_forwarding_pass_registration = registry_mod.PassRegistration{
 132     .name = load_store_forwarding_pass_name,
 133     .description = load_store_forwarding_pass_description,
 134     .pass = createLoadStoreForwardingPass(),
 135 };
 136 
 137 pub const dead_store_elimination_pass_registration = registry_mod.PassRegistration{
 138     .name = dead_store_elimination_pass_name,
 139     .description = dead_store_elimination_pass_description,
 140     .pass = createDeadStoreEliminationPass(),
 141 };
 142 
 143 pub const loop_invariant_code_motion_pass_registration = registry_mod.PassRegistration{
 144     .name = loop_invariant_code_motion_pass_name,
 145     .description = loop_invariant_code_motion_pass_description,
 146     .pass = createLoopInvariantCodeMotionPass(),
 147 };
 148 
 149 const ArithEqualitySaturationPass = @import("root.zig").EGraphPass(.{
 150     .name = equality_saturation_pass_name,
 151     .description = equality_saturation_pass_description,
 152     .populate_rules = dialects.arith.populateEGraphRules,
 153 });
 154 
 155 pub fn createEqualitySaturationPass() Pass {
 156     return ArithEqualitySaturationPass.create();
 157 }
 158 
 159 pub const equality_saturation_pass_registration = registry_mod.PassRegistration{
 160     .name = equality_saturation_pass_name,
 161     .description = equality_saturation_pass_description,
 162     .pass = createEqualitySaturationPass(),
 163 };
 164 
 165 pub const optimization_pass_registrations = [_]registry_mod.PassRegistration{
 166     canonicalization.canonicalization_pass_registration,
 167     constant_folding_pass_registration,
 168     sparse_conditional_constant_propagation_pass_registration,
 169     common_subexpression_elimination_pass_registration,
 170     load_store_forwarding_pass_registration,
 171     dead_store_elimination_pass_registration,
 172     loop_invariant_code_motion_pass_registration,
 173     promotion.memory_promotion_pass_registration,
 174     equality_saturation_pass_registration,
 175     dead_code_elimination_pass_registration,
 176 };
 177 
 178 pub const default_optimization_pipeline_registration = registry_mod.PipelineRegistration{
 179     .name = default_optimization_pipeline_name,
 180     .description = default_optimization_pipeline_description,
 181     .build = buildDefaultOptimizationPipeline,
 182 };
 183 
 184 pub const optimization_pipeline_registrations = [_]registry_mod.PipelineRegistration{
 185     default_optimization_pipeline_registration,
 186 };
 187 
 188 pub fn addDefaultOptimizationPipeline(pm: *pass_mod.PassManager) !void {
 189     try default_optimization_pipeline_registration.addTo(&pm.root);
 190 }
 191 
 192 pub fn buildDefaultOptimizationPipeline(pm: *pass_mod.OpPassManager) anyerror!void {
 193     try pm.addPass(promotion.createMemoryPromotionPass());
 194     try pm.addPass(canonicalization.createCanonicalizationPass());
 195     try pm.addPass(createConstantFoldingPass());
 196     try pm.addPass(createSparseConditionalConstantPropagationPass());
 197     try pm.addPass(canonicalization.createCanonicalizationPass());
 198     try pm.addPass(createCommonSubexpressionEliminationPass());
 199     try pm.addPass(createLoadStoreForwardingPass());
 200     try pm.addPass(createDeadStoreEliminationPass());
 201     try pm.addPass(createLoopInvariantCodeMotionPass());
 202     try pm.addPass(createCommonSubexpressionEliminationPass());
 203     try pm.addPass(createDeadCodeEliminationPass());
 204 }
 205 
 206 pub fn registerOptimizationPassEntries(registry: *registry_mod.PassRegistry) !void {
 207     for (optimization_pass_registrations) |registration| {
 208         try registry.registerPass(registration);
 209     }
 210     for (optimization_pipeline_registrations) |registration| {
 211         try registry.registerPipeline(registration);
 212     }
 213 }
 214 
 215 test "optimization pass mutation scopes classify cleanup locality" {
 216     try std.testing.expect(createDeadCodeEliminationPass().isolatedMutation());
 217     const cse_pass = createCommonSubexpressionEliminationPass();
 218     try std.testing.expect(cse_pass.isolatedMutation());
 219     try std.testing.expectEqual(pass_mod.PassRerunPolicy.skip_if_unchanged, cse_pass.rerun_policy);
 220     try std.testing.expect(cse_pass.validRerunContract());
 221     try std.testing.expect(createConstantFoldingPass().isolatedMutation());
 222     try std.testing.expect(createSparseConditionalConstantPropagationPass().isolatedMutation());
 223     try std.testing.expect(createLoadStoreForwardingPass().isolatedMutation());
 224     try std.testing.expect(createDeadStoreEliminationPass().isolatedMutation());
 225     try std.testing.expect(createLoopInvariantCodeMotionPass().wholeModuleMutation());
 226 }
 227 
 228 const CleanupRunFn = *const fn (*PassContext) PassResult;
 229 
 230 fn expectUnmodifiedCleanupPreservesAll(run_fn: CleanupRunFn) !void {
 231     const allocator = std.testing.allocator;
 232 
 233     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
 234     defer ctx.deinit(allocator);
 235 
 236     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, ir.Location.getUnknown());
 237 
 238     var cache = pass_mod.AnalysisCache.init(allocator, null);
 239     defer cache.deinit();
 240 
 241     var pass_ctx = PassContext.init(module.op, &ctx, allocator, &cache);
 242     defer pass_ctx.deinit();
 243 
 244     try std.testing.expectEqual(PassResult.success, run_fn(&pass_ctx));
 245     try std.testing.expect(!pass_ctx.modified);
 246     try std.testing.expect(pass_ctx.preserved.preserve_all);
 247 }
 248 
 249 test "unmodified cleanup passes preserve all analyses" {
 250     try expectUnmodifiedCleanupPreservesAll(cse.run);
 251     try expectUnmodifiedCleanupPreservesAll(runConstantFolding);
 252     try expectUnmodifiedCleanupPreservesAll(runLoadStoreForwarding);
 253     try expectUnmodifiedCleanupPreservesAll(runDeadStoreElimination);
 254     try expectUnmodifiedCleanupPreservesAll(runLoopInvariantCodeMotion);
 255 }
 256 
 257 fn runDeadCodeElimination(ctx: *PassContext) PassResult {
 258     const modified = canonicalization.eliminateDeadOps(ctx);
 259     if (modified) {
 260         ctx.markModified();
 261     } else {
 262         ctx.preserveAllAnalyses();
 263     }
 264     return .success;
 265 }
 266 
 267 fn runConstantFolding(ctx: *PassContext) PassResult {
 268     var rewriter = PatternRewriter.init(ctx.allocator, ctx.ir_ctx);
 269     defer rewriter.deinit();
 270 
 271     var modified = false;
 272     constantFoldOnOp(ctx.op, ctx.ir_ctx, &rewriter, &modified);
 273     rewriter.finalize(ctx.op);
 274 
 275     if (modified) {
 276         ctx.markModified();
 277     } else {
 278         ctx.preserveAllAnalyses();
 279     }
 280     return .success;
 281 }
 282 
 283 fn constantFoldOnOp(
 284     op: *ir.Operation,
 285     ir_ctx: *ir.Context,
 286     rewriter: *PatternRewriter,
 287     modified: *bool,
 288 ) void {
 289     for (op.regions.items) |*region| {
 290         var block_iter = region.getBlocks();
 291         while (block_iter.next()) |block| {
 292             var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
 293             while (current) |current_op| {
 294                 const next = current_op.next_op;
 295 
 296                 if (current_op.regions.items.len > 0) {
 297                     constantFoldOnOp(current_op, ir_ctx, rewriter, modified);
 298                 }
 299 
 300                 if (tryFoldEvaluatableOp(current_op, ir_ctx, rewriter)) {
 301                     modified.* = true;
 302                 } else if (tryFoldRegisteredAttributeOp(current_op, ir_ctx, rewriter)) {
 303                     modified.* = true;
 304                 }
 305 
 306                 current = next;
 307             }
 308         }
 309     }
 310 }
 311 
 312 fn runSparseConditionalConstantPropagation(ctx: *PassContext) PassResult {
 313     var rewriter = PatternRewriter.init(ctx.allocator, ctx.ir_ctx);
 314     defer rewriter.deinit();
 315 
 316     var modified = false;
 317     sccpOnOp(ctx.op, ctx.ir_ctx, &rewriter, &modified) catch return .failure;
 318     rewriter.finalize(ctx.op);
 319 
 320     if (modified) {
 321         ctx.preserveAnalysisSet(control_flow.analysis_ids);
 322         ctx.markModified();
 323     } else {
 324         ctx.preserveAllAnalyses();
 325     }
 326     return .success;
 327 }
 328 
 329 const SccpOperationTarget = struct {
 330     op: *ir.Operation,
 331     visit: bool,
 332 };
 333 
 334 const SccpTarget = union(enum) {
 335     operation: SccpOperationTarget,
 336     region: *ir.Region,
 337     block: *ir.Block,
 338 };
 339 
 340 fn sccpOnOp(
 341     op: *ir.Operation,
 342     ir_ctx: *ir.Context,
 343     rewriter: *PatternRewriter,
 344     modified: *bool,
 345 ) anyerror!void {
 346     try sccpWalk(.{ .operation = .{ .op = op, .visit = false } }, 1, ir_ctx, rewriter, modified);
 347 }
 348 
 349 fn sccpWalk(
 350     target: SccpTarget,
 351     operation_depth: usize,
 352     ir_ctx: *ir.Context,
 353     rewriter: *PatternRewriter,
 354     modified: *bool,
 355 ) anyerror!void {
 356     std.debug.assert(operation_depth > 0);
 357     switch (target) {
 358         .operation => |operation| {
 359             if (operation_depth > maximum_sccp_operation_depth) return error.NestingLimitExceeded;
 360             const child_depth = operation_depth + 1;
 361             const op = operation.op;
 362             if (operation.visit and std.mem.eql(u8, op.name.name, scf.IfOp.operation_name)) {
 363                 const if_op = scf.IfOp{ .op = op };
 364                 const condition = constantFromValue(if_op.getCondition());
 365                 if (condition) |constant| {
 366                     if (constBool(constant)) |known_condition| {
 367                         if (selectedSccpIfBlock(if_op, known_condition)) |selected| {
 368                             try sccpWalk(.{ .block = selected }, child_depth, ir_ctx, rewriter, modified);
 369                             try propagateSelectedIfConstants(if_op, selected, ir_ctx, rewriter, modified);
 370                         }
 371                         return;
 372                     }
 373                 }
 374 
 375                 try sccpWalk(.{ .block = if_op.getThenBlock() }, child_depth, ir_ctx, rewriter, modified);
 376                 if (if_op.getElseBlock()) |else_block| {
 377                     try sccpWalk(.{ .block = else_block }, child_depth, ir_ctx, rewriter, modified);
 378                 }
 379                 return;
 380             }
 381 
 382             for (op.regions.items) |*region| {
 383                 try sccpWalk(.{ .region = region }, child_depth, ir_ctx, rewriter, modified);
 384             }
 385 
 386             if (!operation.visit) return;
 387             if (!effects.permitsRepeatableExpression(op)) return;
 388 
 389             const folded = inferConstant(op) orelse return;
 390             const result = op.getResult(0) orelse return;
 391             try recordSccpConstant(ir_ctx, rewriter, op, result, folded, modified);
 392         },
 393         .region => |region| {
 394             var block_iter = region.getBlocks();
 395             while (block_iter.next()) |block| {
 396                 try sccpWalk(.{ .block = block }, operation_depth, ir_ctx, rewriter, modified);
 397             }
 398         },
 399         .block => |block| {
 400             var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
 401             while (current) |current_op| {
 402                 const next = current_op.next_op;
 403                 try sccpWalk(.{ .operation = .{ .op = current_op, .visit = true } }, operation_depth, ir_ctx, rewriter, modified);
 404                 current = next;
 405             }
 406         },
 407     }
 408 }
 409 
 410 fn selectedSccpIfBlock(if_op: scf.IfOp, condition: bool) ?*ir.Block {
 411     if (condition) return if_op.getThenBlock();
 412     return if_op.getElseBlock();
 413 }
 414 
 415 fn propagateSelectedIfConstants(
 416     if_op: scf.IfOp,
 417     selected: *ir.Block,
 418     ir_ctx: *ir.Context,
 419     rewriter: *PatternRewriter,
 420     modified: *bool,
 421 ) anyerror!void {
 422     const yield = sccpYieldTerminator(selected) orelse return;
 423     if (yield.operands.items.len != if_op.op.getNumResults()) return;
 424 
 425     for (yield.operands.items, 0..) |operand, index| {
 426         const constant = constantFromValue(operand.value) orelse continue;
 427         const result = if_op.op.getResult(index) orelse continue;
 428         try recordSccpConstant(ir_ctx, rewriter, if_op.op, result, constant, modified);
 429     }
 430 }
 431 
 432 fn sccpYieldTerminator(block: *ir.Block) ?*ir.Operation {
 433     const tail = block.operations.tail orelse return null;
 434     const op: *ir.Operation = @ptrCast(@alignCast(tail));
 435     if (!std.mem.eql(u8, op.name.name, scf.YieldOp.operation_name)) return null;
 436     return op;
 437 }
 438 
 439 fn recordSccpConstant(
 440     ir_ctx: *ir.Context,
 441     rewriter: *PatternRewriter,
 442     before: *ir.Operation,
 443     value: *ir.Value,
 444     constant: ConstValue,
 445     modified: *bool,
 446 ) anyerror!void {
 447     if (value.hasNoUses()) return;
 448     if (try materializeSccpConstant(ir_ctx, rewriter, before, value, constant)) {
 449         modified.* = true;
 450     }
 451 }
 452 
 453 fn materializeSccpConstant(
 454     ir_ctx: *ir.Context,
 455     rewriter: *PatternRewriter,
 456     before: *ir.Operation,
 457     value: *ir.Value,
 458     constant: ConstValue,
 459 ) anyerror!bool {
 460     const attr = constantAttrForType(ir_ctx, value.type, constant) catch return false;
 461     rewriter.setInsertionPointBefore(before);
 462     var state = ir.Operation.State.init(arith.ConstantOp.operation_name, before.location);
 463     state.addTypes(&.{value.type});
 464     const uses_properties = try state.setPropertiesAttrIfRegistered(ir_ctx, attr);
 465     const const_op = try rewriter.create(state);
 466     if (!uses_properties) try const_op.setAttr("value", attr);
 467     const result = const_op.getResult(0) orelse return false;
 468     try rewriter.replaceAllUsesWith(value, result);
 469     return true;
 470 }
 471 
 472 fn runLoadStoreForwarding(ctx: *PassContext) PassResult {
 473     var rewriter = PatternRewriter.init(ctx.allocator, ctx.ir_ctx);
 474     defer rewriter.deinit();
 475 
 476     var modified = false;
 477     forwardOnOp(ctx.op, ctx.allocator, &rewriter, &modified);
 478     rewriter.finalize(ctx.op);
 479 
 480     if (modified) {
 481         ctx.markModified();
 482     } else {
 483         ctx.preserveAllAnalyses();
 484     }
 485     return .success;
 486 }
 487 
 488 const StoreInfo = struct {
 489     value: *ir.Value,
 490 };
 491 
 492 const MemoryLocation = struct {
 493     memref: *ir.Value,
 494     index: *ir.Value,
 495 };
 496 
 497 const MemoryLocationContext = struct {
 498     pub fn hash(_: MemoryLocationContext, key: MemoryLocation) u64 {
 499         var hasher = std.hash.Wyhash.init(0);
 500         const memref_id = @intFromPtr(key.memref);
 501         const index_id = @intFromPtr(key.index);
 502         hasher.update(std.mem.asBytes(&memref_id));
 503         hasher.update(std.mem.asBytes(&index_id));
 504         return hasher.final();
 505     }
 506 
 507     pub fn eql(_: MemoryLocationContext, lhs: MemoryLocation, rhs: MemoryLocation) bool {
 508         return lhs.memref == rhs.memref and lhs.index == rhs.index;
 509     }
 510 };
 511 
 512 const StoreInfoMap = std.HashMap(MemoryLocation, StoreInfo, MemoryLocationContext, std.hash_map.default_max_load_percentage);
 513 const StoreOpMap = std.HashMap(MemoryLocation, *ir.Operation, MemoryLocationContext, std.hash_map.default_max_load_percentage);
 514 
 515 fn forwardOnOp(
 516     op: *ir.Operation,
 517     allocator: std.mem.Allocator,
 518     rewriter: *PatternRewriter,
 519     modified: *bool,
 520 ) void {
 521     for (op.regions.items) |*region| {
 522         var block_iter = region.getBlocks();
 523         while (block_iter.next()) |block| {
 524             var stores = StoreInfoMap.init(allocator);
 525             defer stores.deinit();
 526 
 527             var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
 528             while (current) |current_op| {
 529                 const next = current_op.next_op;
 530 
 531                 if (current_op.regions.items.len > 0) {
 532                     forwardOnOp(current_op, allocator, rewriter, modified);
 533                     stores.clearRetainingCapacity();
 534                     current = next;
 535                     continue;
 536                 }
 537 
 538                 forwardOperation(current_op, &stores, rewriter, modified);
 539                 current = next;
 540             }
 541         }
 542     }
 543 }
 544 
 545 fn forwardOperation(
 546     current_op: *ir.Operation,
 547     stores: *StoreInfoMap,
 548     rewriter: *PatternRewriter,
 549     modified: *bool,
 550 ) void {
 551     if (isMemrefStore(current_op)) {
 552         if (!effects.permitsDiscard(current_op)) {
 553             stores.clearRetainingCapacity();
 554             return;
 555         }
 556         const location = memrefStoreLocation(current_op) orelse {
 557             stores.clearRetainingCapacity();
 558             return;
 559         };
 560         const stored_val = current_op.operands.items[0].value;
 561         _ = stores.put(location, .{ .value = stored_val }) catch {};
 562         return;
 563     }
 564 
 565     if (isMemrefLoad(current_op)) {
 566         if (!effects.permitsDiscard(current_op)) {
 567             stores.clearRetainingCapacity();
 568             return;
 569         }
 570         const location = memrefLoadLocation(current_op) orelse {
 571             stores.clearRetainingCapacity();
 572             return;
 573         };
 574         if (stores.get(location)) |info| {
 575             rewriter.replaceOpWithValue(current_op, info.value) catch {};
 576             modified.* = true;
 577         }
 578         return;
 579     }
 580 
 581     if (invalidatesStores(current_op)) {
 582         stores.clearRetainingCapacity();
 583     }
 584 }
 585 
 586 fn runDeadStoreElimination(ctx: *PassContext) PassResult {
 587     var rewriter = PatternRewriter.init(ctx.allocator, ctx.ir_ctx);
 588     defer rewriter.deinit();
 589 
 590     var modified = false;
 591     eliminateDeadStoresOnOp(ctx.op, ctx.allocator, &rewriter, &modified);
 592     rewriter.finalize(ctx.op);
 593 
 594     if (modified) {
 595         ctx.markModified();
 596     } else {
 597         ctx.preserveAllAnalyses();
 598     }
 599     return .success;
 600 }
 601 
 602 fn eliminateDeadStoresOnOp(
 603     op: *ir.Operation,
 604     allocator: std.mem.Allocator,
 605     rewriter: *PatternRewriter,
 606     modified: *bool,
 607 ) void {
 608     for (op.regions.items) |*region| {
 609         var block_iter = region.getBlocks();
 610         while (block_iter.next()) |block| {
 611             var stores = StoreOpMap.init(allocator);
 612             defer stores.deinit();
 613 
 614             var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
 615             while (current) |current_op| {
 616                 const next = current_op.next_op;
 617 
 618                 if (current_op.regions.items.len > 0) {
 619                     eliminateDeadStoresOnOp(current_op, allocator, rewriter, modified);
 620                     stores.clearRetainingCapacity();
 621                     current = next;
 622                     continue;
 623                 }
 624 
 625                 eliminateDeadStoreOperation(current_op, &stores, rewriter, modified);
 626                 current = next;
 627             }
 628         }
 629     }
 630 }
 631 
 632 fn eliminateDeadStoreOperation(
 633     current_op: *ir.Operation,
 634     stores: *StoreOpMap,
 635     rewriter: *PatternRewriter,
 636     modified: *bool,
 637 ) void {
 638     if (isMemrefStore(current_op)) {
 639         if (!effects.permitsDiscard(current_op)) {
 640             stores.clearRetainingCapacity();
 641             return;
 642         }
 643         const location = memrefStoreLocation(current_op) orelse {
 644             stores.clearRetainingCapacity();
 645             return;
 646         };
 647         if (stores.get(location)) |previous| {
 648             rewriter.eraseOp(previous) catch {
 649                 _ = stores.put(location, current_op) catch {};
 650                 return;
 651             };
 652             modified.* = true;
 653         }
 654         _ = stores.put(location, current_op) catch {};
 655         return;
 656     }
 657 
 658     if (isMemrefLoad(current_op)) {
 659         if (!effects.permitsDiscard(current_op)) {
 660             stores.clearRetainingCapacity();
 661             return;
 662         }
 663         if (memrefLoadLocation(current_op)) |location| {
 664             _ = stores.remove(location);
 665         } else {
 666             stores.clearRetainingCapacity();
 667         }
 668         return;
 669     }
 670 
 671     if (observesOrInvalidatesStores(current_op)) {
 672         stores.clearRetainingCapacity();
 673     }
 674 }
 675 
 676 fn runLoopInvariantCodeMotion(ctx: *PassContext) PassResult {
 677     var modified = false;
 678     licmOnOp(ctx.op, &modified);
 679     if (modified) {
 680         ctx.markModified();
 681     } else {
 682         ctx.preserveAllAnalyses();
 683     }
 684     return .success;
 685 }
 686 
 687 fn licmOnOp(op: *ir.Operation, modified: *bool) void {
 688     for (op.regions.items) |*region| {
 689         var block_iter = region.getBlocks();
 690         while (block_iter.next()) |block| {
 691             var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
 692             while (current) |current_op| {
 693                 const next = current_op.next_op;
 694                 licmOnOp(current_op, modified);
 695                 current = next;
 696             }
 697         }
 698     }
 699 
 700     if (std.mem.eql(u8, op.name.name, scf.ForOp.operation_name)) {
 701         if (hoistLoopInvariants(op)) {
 702             modified.* = true;
 703         }
 704     }
 705 }
 706 
 707 fn hoistLoopInvariants(for_op: *ir.Operation) bool {
 708     const loop = scf.ForOp{ .op = for_op };
 709     const body_block = loop.getBodyBlock();
 710     if (for_op.getBlock() == null) return false;
 711 
 712     var modified = false;
 713     var progress = true;
 714     while (progress) {
 715         progress = false;
 716         var current: ?*ir.Operation = @ptrCast(@alignCast(body_block.operations.head));
 717         while (current) |current_op| {
 718             const next = current_op.next_op;
 719 
 720             if (std.mem.eql(u8, current_op.name.name, scf.YieldOp.operation_name)) {
 721                 current = next;
 722                 continue;
 723             }
 724 
 725             if (isLoopInvariantCandidate(current_op) and canMoveToLoopEntry(current_op, for_op)) {
 726                 current_op.moveBefore(for_op) catch {
 727                     current = next;
 728                     continue;
 729                 };
 730 
 731                 modified = true;
 732                 progress = true;
 733             }
 734 
 735             current = next;
 736         }
 737     }
 738 
 739     return modified;
 740 }
 741 
 742 fn canMoveToLoopEntry(op: *ir.Operation, loop_op: *ir.Operation) bool {
 743     if (!operandsInvariant(op, loop_op)) return false;
 744     var summary = effects.EffectSummary.init(op.allocator, op) catch return false;
 745     defer summary.deinit();
 746     if (!summary.speculate(true) or !summary.duplicate(.{})) return false;
 747     var previous = op.prev_op;
 748     while (previous) |crossed| : (previous = crossed.prev_op) {
 749         var crossing = effects.EffectSummary.init(op.allocator, crossed) catch return false;
 750         defer crossing.deinit();
 751         if (!summary.reorder(&crossing)) return false;
 752     }
 753     return true;
 754 }
 755 
 756 fn operandsInvariant(
 757     op: *ir.Operation,
 758     loop_op: *ir.Operation,
 759 ) bool {
 760     for (op.operands.items) |operand| {
 761         if (!valueInvariant(operand.value, loop_op)) return false;
 762         if (!valueAvailableBefore(operand.value, loop_op)) return false;
 763     }
 764     return true;
 765 }
 766 
 767 fn valueAvailableBefore(value: *ir.Value, destination: *ir.Operation) bool {
 768     var current: ?*ir.Operation = destination;
 769     while (current) |placement| : (current = placement.getParentOp()) {
 770         if (value.getDefiningOp()) |definition| {
 771             const op: *ir.Operation = @ptrCast(@alignCast(definition));
 772             if (op.getBlock() == placement.getBlock()) return op.isBeforeInBlock(placement);
 773         } else if (value.getOwnerBlock()) |owner| {
 774             if (owner == @as(?*anyopaque, @ptrCast(placement.getBlock()))) return true;
 775         }
 776     }
 777     return false;
 778 }
 779 
 780 fn valueInvariant(
 781     value: *ir.Value,
 782     loop_op: *ir.Operation,
 783 ) bool {
 784     if (value.getDefiningOp()) |def_any| {
 785         const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
 786         return !loop_op.isAncestor(def_op);
 787     }
 788 
 789     if (value.getOwnerBlock()) |block_any| {
 790         const block: *ir.Block = @ptrCast(@alignCast(block_any));
 791         const parent_op = block.getParentOperation() orelse return true;
 792         return !loop_op.isAncestor(parent_op);
 793     }
 794 
 795     return true;
 796 }
 797 
 798 fn isLoopInvariantCandidate(op: *ir.Operation) bool {
 799     if (op.regions.items.len > 0) return false;
 800     if (op.getNumResults() == 0) return false;
 801     if (op.getNumSuccessors() != 0) return false;
 802     if (op.hasTrait("is_terminator")) return false;
 803     return effects.permitsRepeatableExpression(op);
 804 }
 805 
 806 fn isMemrefLoad(op: *ir.Operation) bool {
 807     return std.mem.eql(u8, op.name.name, memref.LoadOp.operation_name);
 808 }
 809 
 810 fn isMemrefStore(op: *ir.Operation) bool {
 811     return std.mem.eql(u8, op.name.name, memref.StoreOp.operation_name);
 812 }
 813 
 814 fn memrefLoadLocation(op: *ir.Operation) ?MemoryLocation {
 815     if (!isMemrefLoad(op)) return null;
 816     if (op.operands.items.len != 2) return null;
 817     return .{
 818         .memref = op.operands.items[0].value,
 819         .index = op.operands.items[1].value,
 820     };
 821 }
 822 
 823 fn memrefStoreLocation(op: *ir.Operation) ?MemoryLocation {
 824     if (!isMemrefStore(op)) return null;
 825     if (op.operands.items.len != 3) return null;
 826     return .{
 827         .memref = op.operands.items[1].value,
 828         .index = op.operands.items[2].value,
 829     };
 830 }
 831 
 832 fn invalidatesStores(op: *ir.Operation) bool {
 833     if (op.hasTrait("is_terminator")) return true;
 834     var summary = effects.EffectSummary.init(op.allocator, op) catch return true;
 835     defer summary.deinit();
 836     return summary.invalidatesStores();
 837 }
 838 
 839 fn observesOrInvalidatesStores(op: *ir.Operation) bool {
 840     if (op.hasTrait("is_terminator")) return true;
 841     var summary = effects.EffectSummary.init(op.allocator, op) catch return true;
 842     defer summary.deinit();
 843     return summary.observesStores();
 844 }
 845 
 846 const ConstValue = union(enum) {
 847     int: i64,
 848     float: f64,
 849     bool: bool,
 850 };
 851 
 852 const ScalarKind = enum {
 853     int,
 854     float,
 855     bool,
 856     other,
 857 };
 858 
 859 fn constInt(value: ConstValue) ?i64 {
 860     return switch (value) {
 861         .int => |v| v,
 862         else => null,
 863     };
 864 }
 865 
 866 fn constBool(value: ConstValue) ?bool {
 867     return switch (value) {
 868         .bool => |v| v,
 869         else => null,
 870     };
 871 }
 872 
 873 fn classifyType(ty: ir.Type) ScalarKind {
 874     const kind = dialects.arith.scalarKindFromType(ty) orelse return .other;
 875     return switch (kind) {
 876         .bool => .bool,
 877         .f16, .bf16, .f32, .f64 => .float,
 878         .i8, .i16, .i32, .i64, .u8, .u16, .u32, .u64, .index => .int,
 879     };
 880 }
 881 
 882 fn constantFromValue(value: *ir.Value) ?ConstValue {
 883     const def_any = value.getDefiningOp() orelse return null;
 884     const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
 885     if (!std.mem.eql(u8, def_op.name.name, arith.ConstantOp.operation_name)) return null;
 886 
 887     if (def_op.getAttrAs(ir.Attribute.IntegerAttr, "value")) |int_attr| {
 888         return .{ .int = int_attr.getValue() };
 889     }
 890     if (def_op.getAttrAs(ir.Attribute.FloatAttr, "value")) |float_attr| {
 891         return .{ .float = float_attr.getValue() };
 892     }
 893     if (def_op.getAttrAs(ir.Attribute.BoolAttr, "value")) |bool_attr| {
 894         return .{ .bool = bool_attr.getValue() };
 895     }
 896     return null;
 897 }
 898 
 899 fn constantFromAttribute(attr: ir.Attribute) ?ConstValue {
 900     if (arith.getIntValue(attr)) |int_val| return .{ .int = int_val };
 901     if (arith.getFloatValue(attr)) |float_val| return .{ .float = float_val };
 902     if (arith.getBoolValue(attr)) |bool_val| return .{ .bool = bool_val };
 903     return null;
 904 }
 905 
 906 fn inferConstant(op: *ir.Operation) ?ConstValue {
 907     if (std.mem.eql(u8, op.name.name, arith.ConstantOp.operation_name)) return null;
 908     if (op.getNumResults() != 1) return null;
 909     if (!effects.permitsRepeatableExpression(op)) return null;
 910     const iface = op.interface(ir.interfaces.Evaluatable) orelse return null;
 911     if (!iface.call(.canEval, .{})) return null;
 912     var evaluator = @import("../eval/root.zig").Evaluator.init(op.allocator, op.getContext());
 913     defer evaluator.deinit();
 914     for (op.getOperandValues()) |operand| {
 915         const value = constantFromValue(operand) orelse return null;
 916         const attr = constantAttrForType(op.getContext(), operand.type, value) catch return null;
 917         evaluator.setValue(operand, attr) catch return null;
 918     }
 919     const result = evaluator.evaluate(op) catch return null;
 920     return constantFromAttribute(result);
 921 }
 922 
 923 fn tryFoldEvaluatableOp(op: *ir.Operation, ir_ctx: *ir.Context, rewriter: *PatternRewriter) bool {
 924     if (!effects.permitsRepeatableExpression(op)) return false;
 925     const folded = inferConstant(op) orelse return false;
 926     return replaceWithConstant(op, ir_ctx, rewriter, folded);
 927 }
 928 
 929 fn tryFoldRegisteredAttributeOp(op: *ir.Operation, ir_ctx: *ir.Context, rewriter: *PatternRewriter) bool {
 930     if (!effects.permitsRepeatableExpression(op)) return false;
 931     const iface = op.interface(ir.interfaces.FoldOpInterface) orelse return false;
 932 
 933     const result_count = op.getNumResults();
 934     var inline_results: [1]ir.interfaces.FoldResult = undefined;
 935     const result_storage = if (result_count <= inline_results.len)
 936         inline_results[0..result_count]
 937     else
 938         rewriter.allocator.alloc(ir.interfaces.FoldResult, result_count) catch return false;
 939     defer if (result_count > inline_results.len) rewriter.allocator.free(result_storage);
 940 
 941     var folded = ir.interfaces.FoldResults.init(result_storage);
 942     iface.call(.fold, .{&folded}) catch return false;
 943     const folded_results = folded.slice();
 944 
 945     if (folded_results.len == 0) return false;
 946     if (folded_results.len != result_count) return false;
 947 
 948     var inline_values: [1]*ir.Value = undefined;
 949     const values = if (result_count <= inline_values.len)
 950         inline_values[0..result_count]
 951     else
 952         rewriter.allocator.alloc(*ir.Value, result_count) catch return false;
 953     defer if (result_count > inline_values.len) rewriter.allocator.free(values);
 954 
 955     for (folded_results, 0..) |folded_result, index| {
 956         const op_result = op.getResult(index) orelse return false;
 957         const constant = switch (folded_result) {
 958             .attribute => |attr| constantFromAttribute(attr) orelse return false,
 959             .value => return false,
 960         };
 961         values[index] = createConstantValue(ir_ctx, rewriter, op, op_result.type, constant) orelse return false;
 962     }
 963 
 964     rewriter.replaceOp(op, values) catch return false;
 965     return true;
 966 }
 967 
 968 fn replaceWithConstant(
 969     op: *ir.Operation,
 970     ir_ctx: *ir.Context,
 971     rewriter: *PatternRewriter,
 972     value: ConstValue,
 973 ) bool {
 974     const result_type = op.getResultTypes()[0];
 975     const result = createConstantValue(ir_ctx, rewriter, op, result_type, value) orelse return false;
 976     rewriter.replaceOpWithValue(op, result) catch return false;
 977     return true;
 978 }
 979 
 980 fn createConstantValue(
 981     ir_ctx: *ir.Context,
 982     rewriter: *PatternRewriter,
 983     before: *ir.Operation,
 984     result_type: ir.Type,
 985     value: ConstValue,
 986 ) ?*ir.Value {
 987     const attr = constantAttrForType(ir_ctx, result_type, value) catch return null;
 988 
 989     rewriter.setInsertionPointBefore(before);
 990     var state = ir.Operation.State.init(arith.ConstantOp.operation_name, before.location);
 991     state.addTypes(&.{result_type});
 992     const uses_properties = state.setPropertiesAttrIfRegistered(ir_ctx, attr) catch return null;
 993     const const_op = rewriter.create(state) catch return null;
 994     if (!uses_properties) const_op.setAttr("value", attr) catch return null;
 995     return const_op.getResult(0);
 996 }
 997 
 998 fn constantAttrForType(
 999     ir_ctx: *ir.Context,
1000     ty: ir.Type,
1001     value: ConstValue,
1002 ) !ir.Attribute {
1003     return switch (classifyType(ty)) {
1004         .int => switch (value) {
1005             .int => |v| try arith.getIntAttr(ir_ctx, v),
1006             else => error.InvalidConstant,
1007         },
1008         .float => switch (value) {
1009             .float => |v| try arith.getFloatAttr(ir_ctx, v),
1010             else => error.InvalidConstant,
1011         },
1012         .bool => switch (value) {
1013             .bool => |v| try arith.getBoolAttr(ir_ctx, v),
1014             else => error.InvalidConstant,
1015         },
1016         else => error.InvalidConstant,
1017     };
1018 }
1019 
1020 const testing = std.testing;
1021 const test_dialect = @import("../dialects/fixture/root.zig");
1022 
1023 fn buildTestContext(allocator: std.mem.Allocator) !ir.Context {
1024     var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1025     errdefer ctx.deinit(allocator);
1026     try test_dialect.registerTestDialect(&ctx);
1027     return ctx;
1028 }
1029 
1030 fn runDcePass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1031     var pm = pass_mod.PassManager.init(allocator);
1032     errdefer pm.deinit();
1033     try pm.addPass(createDeadCodeEliminationPass());
1034     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1035     return pm;
1036 }
1037 
1038 fn runConstantFoldingPass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1039     var pm = pass_mod.PassManager.init(allocator);
1040     errdefer pm.deinit();
1041     try pm.addPass(createConstantFoldingPass());
1042     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1043     return pm;
1044 }
1045 
1046 fn runSccpPass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1047     var pm = pass_mod.PassManager.init(allocator);
1048     errdefer pm.deinit();
1049     try pm.addPass(createSparseConditionalConstantPropagationPass());
1050     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1051     return pm;
1052 }
1053 
1054 fn runLicmPass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1055     var pm = pass_mod.PassManager.init(allocator);
1056     errdefer pm.deinit();
1057     try pm.addPass(createLoopInvariantCodeMotionPass());
1058     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1059     return pm;
1060 }
1061 
1062 fn runLoadStoreForwardingPass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1063     var pm = pass_mod.PassManager.init(allocator);
1064     errdefer pm.deinit();
1065     try pm.addPass(createLoadStoreForwardingPass());
1066     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1067     return pm;
1068 }
1069 
1070 fn runDeadStoreEliminationPass(allocator: std.mem.Allocator, module: *ir.Operation, ctx: *ir.Context) !pass_mod.PassManager {
1071     var pm = pass_mod.PassManager.init(allocator);
1072     errdefer pm.deinit();
1073     try pm.addPass(createDeadStoreEliminationPass());
1074     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1075     return pm;
1076 }
1077 
1078 fn createReturn(ctx: *ir.Context, block: *ir.Block, operands: []const *ir.Value) !test_dialect.TestDialect.ReturnOp {
1079     const op = try test_dialect.TestDialect.ReturnOp.create(ctx, ir.Location.getUnknown(), operands);
1080     try block.addOperation(op.op);
1081     return op;
1082 }
1083 
1084 fn createResultOp(ctx: *ir.Context, block: *ir.Block, name: []const u8, result_type: ir.Type) !*ir.Operation {
1085     var builder = ir.OperationBuilder.init(ctx);
1086     var state = ir.Operation.State.init(name, ir.Location.getUnknown());
1087     state.addTypes(&.{result_type});
1088     const op = try builder.create(state);
1089     try block.addOperation(op);
1090     return op;
1091 }
1092 
1093 fn createOperandResultOp(
1094     ctx: *ir.Context,
1095     block: *ir.Block,
1096     name: []const u8,
1097     operand: *ir.Value,
1098     result_type: ir.Type,
1099 ) !*ir.Operation {
1100     var builder = ir.OperationBuilder.init(ctx);
1101     var state = ir.Operation.State.init(name, ir.Location.getUnknown());
1102     state.addOperands(&.{operand});
1103     state.addTypes(&.{result_type});
1104     const op = try builder.create(state);
1105     try block.addOperation(op);
1106     return op;
1107 }
1108 
1109 fn foldFalseForConstantFolding(
1110     op_ptr: *const anyopaque,
1111     results: *ir.interfaces.FoldResults,
1112 ) anyerror!void {
1113     const op: *const ir.Operation = @ptrCast(@alignCast(op_ptr));
1114     const attr = try arith.getBoolAttr(op.getContext(), false);
1115     try results.append(.{ .attribute = attr });
1116 }
1117 
1118 test "Choir optimization passes register for textual pipelines" {
1119     const allocator = testing.allocator;
1120 
1121     var registry = registry_mod.PassRegistry.init(allocator);
1122     defer registry.deinit();
1123     try registerOptimizationPassEntries(&registry);
1124 
1125     try testing.expectEqual(
1126         @as(usize, optimization_pass_registrations.len),
1127         registry.passes.items.len,
1128     );
1129     inline for (optimization_pass_registrations) |registration| {
1130         try testing.expect(registry.lookupPass(registration.name) != null);
1131     }
1132     try testing.expect(registry.lookupPipeline(default_optimization_pipeline_name) != null);
1133 
1134     var manager = pass_mod.PassManager.init(allocator);
1135     defer manager.deinit();
1136     try textual_pipeline.parsePassPipeline(
1137         &registry,
1138         canonicalization.canonicalization_pass_name ++ "," ++ common_subexpression_elimination_pass_name,
1139         &manager,
1140     );
1141 
1142     try testing.expectEqual(@as(usize, 2), manager.root.pipeline.items.len);
1143 
1144     const text = try textual_pipeline.formatPassManagerPipelineAlloc(allocator, &manager);
1145     defer allocator.free(text);
1146     try testing.expectEqualStrings(
1147         canonicalization.canonicalization_pass_name ++ "," ++ common_subexpression_elimination_pass_name,
1148         text,
1149     );
1150 }
1151 
1152 test "Choir cleanup pipeline materializes from textual registry" {
1153     const allocator = testing.allocator;
1154 
1155     var registry = registry_mod.PassRegistry.init(allocator);
1156     defer registry.deinit();
1157     try registerOptimizationPassEntries(&registry);
1158 
1159     var manager = pass_mod.PassManager.init(allocator);
1160     defer manager.deinit();
1161     try textual_pipeline.parsePassPipeline(&registry, default_optimization_pipeline_name, &manager);
1162 
1163     try testing.expectEqual(@as(usize, 11), manager.root.pipeline.items.len);
1164 
1165     const text = try textual_pipeline.formatPassManagerPipelineAlloc(allocator, &manager);
1166     defer allocator.free(text);
1167     try testing.expectEqualStrings(
1168         promotion.memory_promotion_pass_name ++ "," ++
1169             canonicalization.canonicalization_pass_name ++ "," ++
1170             constant_folding_pass_name ++ "," ++
1171             sparse_conditional_constant_propagation_pass_name ++ "," ++
1172             canonicalization.canonicalization_pass_name ++ "," ++
1173             common_subexpression_elimination_pass_name ++ "," ++
1174             load_store_forwarding_pass_name ++ "," ++
1175             dead_store_elimination_pass_name ++ "," ++
1176             loop_invariant_code_motion_pass_name ++ "," ++
1177             common_subexpression_elimination_pass_name ++ "," ++
1178             dead_code_elimination_pass_name,
1179         text,
1180     );
1181 }
1182 
1183 test "addDefaultOptimizationPipeline uses Choir cleanup registration" {
1184     const allocator = testing.allocator;
1185 
1186     var manager = pass_mod.PassManager.init(allocator);
1187     defer manager.deinit();
1188     try addDefaultOptimizationPipeline(&manager);
1189 
1190     try testing.expectEqual(@as(usize, 11), manager.root.pipeline.items.len);
1191 
1192     const text = try textual_pipeline.formatPassManagerPipelineAlloc(allocator, &manager);
1193     defer allocator.free(text);
1194     try testing.expectEqualStrings(
1195         promotion.memory_promotion_pass_name ++ "," ++
1196             canonicalization.canonicalization_pass_name ++ "," ++
1197             constant_folding_pass_name ++ "," ++
1198             sparse_conditional_constant_propagation_pass_name ++ "," ++
1199             canonicalization.canonicalization_pass_name ++ "," ++
1200             common_subexpression_elimination_pass_name ++ "," ++
1201             load_store_forwarding_pass_name ++ "," ++
1202             dead_store_elimination_pass_name ++ "," ++
1203             loop_invariant_code_motion_pass_name ++ "," ++
1204             common_subexpression_elimination_pass_name ++ "," ++
1205             dead_code_elimination_pass_name,
1206         text,
1207     );
1208 }
1209 
1210 test "Choir cleanup skips unchanged second CSE" {
1211     const allocator = testing.allocator;
1212 
1213     var ctx = try buildTestContext(allocator);
1214     defer ctx.deinit(allocator);
1215     try dialects.registerAllDialects(&ctx);
1216 
1217     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, ir.Location.getUnknown());
1218 
1219     var manager = pass_mod.PassManager.init(allocator);
1220     defer manager.deinit();
1221     try addDefaultOptimizationPipeline(&manager);
1222     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
1223 
1224     try testing.expectEqual(@as(u64, 10), manager.stats.pass_runs);
1225     try testing.expectEqual(@as(u64, 1), manager.stats.passes_skipped);
1226 }
1227 
1228 test "Choir cleanup pipeline CSEs values exposed by LICM" {
1229     const allocator = testing.allocator;
1230 
1231     var ctx = try buildTestContext(allocator);
1232     defer ctx.deinit(allocator);
1233     try dialects.registerAllDialects(&ctx);
1234     try registerObservation(&ctx);
1235     _ = try ctx.registerOperation("test.loop_pure", .{});
1236     try ctx.registerOperationInterface(
1237         "test.loop_write",
1238         ir.interfaces.EffectOpInterface.entryFor(.{}),
1239     );
1240 
1241     const loc = ir.Location.getUnknown();
1242     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1243     const outer_block = module.getBodyBlock();
1244     const index_type = try arith.getIndexType(&ctx);
1245 
1246     const first = (try arith.ConstantOp.createInt(&ctx, loc, index_type, 42)).op;
1247     try outer_block.addOperation(first);
1248     try observeValues(&ctx, outer_block, &.{first.getResult(0).?});
1249 
1250     var lower = try arith.ConstantOp.createInt(&ctx, loc, index_type, 0);
1251     var upper = try arith.ConstantOp.createInt(&ctx, loc, index_type, 4);
1252     var step = try arith.ConstantOp.createInt(&ctx, loc, index_type, 1);
1253     try outer_block.addOperation(lower.op);
1254     try outer_block.addOperation(upper.op);
1255     try outer_block.addOperation(step.op);
1256 
1257     var for_op = try scf.ForOp.create(&ctx, loc, lower.getResult(), upper.getResult(), step.getResult(), &.{}, &.{});
1258     try outer_block.addOperation(for_op.op);
1259 
1260     const body_block = for_op.getBodyBlock();
1261     const inner_pure = (try arith.ConstantOp.createInt(&ctx, loc, index_type, 42)).op;
1262     try body_block.addOperation(inner_pure);
1263     var write_state = ir.Operation.State.init("test.loop_write", loc);
1264     write_state.addOperands(&.{inner_pure.getResult(0).?});
1265     var builder = ir.OperationBuilder.init(&ctx);
1266     const write = try builder.create(write_state);
1267     try body_block.addOperation(write);
1268     const yield = try scf.YieldOp.create(&ctx, loc, &.{});
1269     try body_block.addOperation(yield.op);
1270 
1271     var manager = pass_mod.PassManager.init(allocator);
1272     defer manager.deinit();
1273     try addDefaultOptimizationPipeline(&manager);
1274     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
1275 
1276     try testing.expect(write.getOperand(0).? == first.getResult(0).?);
1277     const survivor_any = write.getOperand(0).?.getDefiningOp() orelse return error.ExpectedCseSurvivor;
1278     const survivor: *ir.Operation = @ptrCast(@alignCast(survivor_any));
1279     try testing.expectEqualStrings("arith.constant", survivor.name.name);
1280     try testing.expect(survivor.parent_block == outer_block);
1281     try testing.expectEqual(@as(u64, 11), manager.stats.pass_runs);
1282     try testing.expectEqual(@as(u64, 0), manager.stats.passes_skipped);
1283 }
1284 
1285 test "F10a retains unqualified registered attribute folds" {
1286     const allocator = testing.allocator;
1287 
1288     var ctx = try buildTestContext(allocator);
1289     defer ctx.deinit(allocator);
1290 
1291     _ = try ctx.registerOperation("test.fold_false", .{});
1292     try ctx.registerOperationInterface(
1293         "test.fold_false",
1294         ir.interfaces.FoldOpInterface.entryFor(foldFalseForConstantFolding),
1295     );
1296 
1297     const loc = ir.Location.getUnknown();
1298     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1299     const block = module.getBodyBlock();
1300     const bool_type = try arith.getScalarType(&ctx, .bool);
1301 
1302     const folded = try createResultOp(&ctx, block, "test.fold_false", bool_type);
1303     _ = try createReturn(&ctx, block, &.{folded.getResult(0).?});
1304 
1305     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1306     defer allocator.free(before_ir);
1307     var pm = try runConstantFoldingPass(allocator, module.op, &ctx);
1308     defer pm.deinit();
1309     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1310     defer allocator.free(after_ir);
1311     try testing.expectEqualStrings(before_ir, after_ir);
1312 }
1313 
1314 test "Precision1 Choir cleanup pipeline simplifies computed constant scf.if" {
1315     const allocator = testing.allocator;
1316 
1317     var ctx = try buildTestContext(allocator);
1318     defer ctx.deinit(allocator);
1319     try dialects.registerAllDialects(&ctx);
1320 
1321     const loc = ir.Location.getUnknown();
1322     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1323     const block = module.getBodyBlock();
1324     const i32_type = try arith.getScalarType(&ctx, .i32);
1325 
1326     var one = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 1);
1327     try block.addOperation(one.op);
1328 
1329     var cmp = try arith.CmpOp.create(&ctx, loc, .eq, one.getResult(), one.getResult());
1330     try block.addOperation(cmp.op);
1331 
1332     const if_op = try scf.IfOp.createWithoutElse(&ctx, loc, cmp.getResult());
1333     try block.addOperation(if_op.op);
1334 
1335     var manager = pass_mod.PassManager.init(allocator);
1336     defer manager.deinit();
1337     try addDefaultOptimizationPipeline(&manager);
1338     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
1339 
1340     try testing.expectEqual(@as(usize, 0), ir.inspection.countOperationsNamed(module.op, scf.IfOp.operation_name));
1341 }
1342 
1343 test "F10a retains unqualified generic unused operations during DCE" {
1344     const allocator = testing.allocator;
1345 
1346     var ctx = try buildTestContext(allocator);
1347     defer ctx.deinit(allocator);
1348     try dialects.registerAllDialects(&ctx);
1349     _ = try ctx.registerOperation("test.dead", .{});
1350     try ctx.registerOperationInterface(
1351         "test.read_value",
1352         ir.interfaces.EffectOpInterface.entryFor(.{}),
1353     );
1354     try ctx.registerOperationInterface(
1355         "test.write_value",
1356         ir.interfaces.EffectOpInterface.entryFor(.{}),
1357     );
1358 
1359     const loc = ir.Location.getUnknown();
1360     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1361     const block = module.getBodyBlock();
1362     const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
1363     const f32_type = try arith.getScalarType(&ctx, .f32);
1364     const index_type = try arith.getIndexType(&ctx);
1365     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1366     const memref_arg = try block.addArgument(memref_type, loc);
1367     const index_arg = try block.addArgument(index_type, loc);
1368 
1369     _ = try createResultOp(&ctx, block, "test.dead", i32_type);
1370     _ = try createResultOp(&ctx, block, "test.read_value", i32_type);
1371     _ = try createResultOp(&ctx, block, "test.write_value", i32_type);
1372     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, index_arg, f32_type);
1373     try block.addOperation(load.op);
1374 
1375     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1376     defer allocator.free(before_ir);
1377     var pm = try runDcePass(allocator, module.op, &ctx);
1378     defer pm.deinit();
1379     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1380     defer allocator.free(after_ir);
1381     try testing.expectEqualStrings(before_ir, after_ir);
1382 }
1383 
1384 test "F10a retains unqualified unused read declarations during DCE" {
1385     const allocator = testing.allocator;
1386 
1387     var ctx = try buildTestContext(allocator);
1388     defer ctx.deinit(allocator);
1389     try dialects.registerAllDialects(&ctx);
1390     try ctx.registerOperationInterface(
1391         "test.read_operand_value",
1392         ir.interfaces.EffectOpInterface.entryFor(.{}),
1393     );
1394 
1395     const loc = ir.Location.getUnknown();
1396     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1397     const block = module.getBodyBlock();
1398     const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
1399     const input = try block.addArgument(i32_type, loc);
1400 
1401     _ = try createOperandResultOp(&ctx, block, "test.read_operand_value", input, i32_type);
1402 
1403     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1404     defer allocator.free(before_ir);
1405     var pm = try runDcePass(allocator, module.op, &ctx);
1406     defer pm.deinit();
1407     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1408     defer allocator.free(after_ir);
1409     try testing.expectEqualStrings(before_ir, after_ir);
1410 }
1411 
1412 test "choir-sccp propagates constants through computed scf.if condition" {
1413     const allocator = testing.allocator;
1414 
1415     var ctx = try buildTestContext(allocator);
1416     defer ctx.deinit(allocator);
1417     try dialects.registerAllDialects(&ctx);
1418 
1419     const loc = ir.Location.getUnknown();
1420     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1421     const block = module.getBodyBlock();
1422     const i32_type = try arith.getScalarType(&ctx, .i32);
1423 
1424     var one = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 1);
1425     var two = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 2);
1426     try block.addOperation(one.op);
1427     try block.addOperation(two.op);
1428 
1429     var cmp = try arith.CmpOp.create(&ctx, loc, .eq, one.getResult(), one.getResult());
1430     try block.addOperation(cmp.op);
1431 
1432     var if_op = try scf.IfOp.create(&ctx, loc, cmp.getResult(), &.{i32_type});
1433     try block.addOperation(if_op.op);
1434 
1435     const then_block = if_op.getThenBlock();
1436     var sum = try arith.AddOp.create(&ctx, loc, one.getResult(), two.getResult());
1437     try then_block.addOperation(sum.op);
1438     const then_yield = try scf.YieldOp.create(&ctx, loc, &.{sum.getResult()});
1439     try then_block.addOperation(then_yield.op);
1440 
1441     const else_block = if_op.getElseBlock().?;
1442     const else_yield = try scf.YieldOp.create(&ctx, loc, &.{two.getResult()});
1443     try else_block.addOperation(else_yield.op);
1444 
1445     const ret = try createReturn(&ctx, block, &.{if_op.getResult(0).?});
1446 
1447     var pm = try runSccpPass(allocator, module.op, &ctx);
1448     defer pm.deinit();
1449 
1450     try testing.expectEqual(ConstValue{ .int = 3 }, constantFromValue(ret.op.getOperand(0).?).?);
1451     try testing.expectEqual(@as(u64, 1), pm.stats.passes_modified);
1452 }
1453 
1454 test "choir-sccp propagates through materialized SSA replacements" {
1455     const allocator = testing.allocator;
1456 
1457     var ctx = try buildTestContext(allocator);
1458     defer ctx.deinit(allocator);
1459     try dialects.registerAllDialects(&ctx);
1460 
1461     const loc = ir.Location.getUnknown();
1462     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1463     const block = module.getBodyBlock();
1464     const i32_type = try arith.getScalarType(&ctx, .i32);
1465 
1466     var one = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 1);
1467     var two = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 2);
1468     try block.addOperation(one.op);
1469     try block.addOperation(two.op);
1470 
1471     var sum = try arith.AddOp.create(&ctx, loc, one.getResult(), two.getResult());
1472     try block.addOperation(sum.op);
1473     var product = try arith.AddOp.create(&ctx, loc, sum.getResult(), two.getResult());
1474     try block.addOperation(product.op);
1475     const ret = try createReturn(&ctx, block, &.{product.getResult()});
1476 
1477     var pm = try runSccpPass(allocator, module.op, &ctx);
1478     defer pm.deinit();
1479 
1480     const propagated = constantFromValue(ret.op.getOperand(0).?) orelse return error.ExpectedConstant;
1481     try testing.expectEqual(@as(i64, 5), constInt(propagated).?);
1482     try testing.expectEqual(@as(u64, 1), pm.stats.passes_modified);
1483 }
1484 
1485 test "choir-sccp propagates common constants from unknown scf.if branches" {
1486     const allocator = testing.allocator;
1487 
1488     var ctx = try buildTestContext(allocator);
1489     defer ctx.deinit(allocator);
1490     try dialects.registerAllDialects(&ctx);
1491 
1492     const loc = ir.Location.getUnknown();
1493     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1494     const block = module.getBodyBlock();
1495     const bool_type = try arith.getScalarType(&ctx, .bool);
1496     const i32_type = try arith.getScalarType(&ctx, .i32);
1497     const cond = try block.addArgument(bool_type, loc);
1498 
1499     var zero = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 0);
1500     var seven = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 7);
1501     try block.addOperation(zero.op);
1502     try block.addOperation(seven.op);
1503 
1504     var if_op = try scf.IfOp.create(&ctx, loc, cond, &.{i32_type});
1505     try block.addOperation(if_op.op);
1506 
1507     var then_sum = try arith.AddOp.create(&ctx, loc, seven.getResult(), zero.getResult());
1508     try if_op.getThenBlock().addOperation(then_sum.op);
1509     const then_yield = try scf.YieldOp.create(&ctx, loc, &.{then_sum.getResult()});
1510     try if_op.getThenBlock().addOperation(then_yield.op);
1511 
1512     var else_sum = try arith.AddOp.create(&ctx, loc, zero.getResult(), seven.getResult());
1513     try if_op.getElseBlock().?.addOperation(else_sum.op);
1514     const else_yield = try scf.YieldOp.create(&ctx, loc, &.{else_sum.getResult()});
1515     try if_op.getElseBlock().?.addOperation(else_yield.op);
1516 
1517     const ret = try createReturn(&ctx, block, &.{if_op.getResult(0).?});
1518 
1519     var pm = try runSccpPass(allocator, module.op, &ctx);
1520     defer pm.deinit();
1521 
1522     try testing.expect(ret.op.getOperand(0).? == if_op.getResult(0).?);
1523     try testing.expect(constantFromValue(then_yield.op.getOperand(0).?) != null);
1524     try testing.expectEqual(@as(u64, 1), pm.stats.passes_modified);
1525 }
1526 
1527 test "choir-sccp no-op path uses no pass allocator" {
1528     const allocator = testing.allocator;
1529 
1530     var ctx = try buildTestContext(allocator);
1531     defer ctx.deinit(allocator);
1532     try dialects.registerAllDialects(&ctx);
1533 
1534     const module = try test_dialect.TestDialect.ModuleOp.create(
1535         &ctx,
1536         ir.Location.getUnknown(),
1537     );
1538 
1539     var failing = testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });
1540     var analysis_cache = pass_mod.AnalysisCache.init(failing.allocator(), null);
1541     defer analysis_cache.deinit();
1542     var pass_ctx = PassContext.init(
1543         module.op,
1544         &ctx,
1545         failing.allocator(),
1546         &analysis_cache,
1547     );
1548     defer pass_ctx.deinit();
1549 
1550     try testing.expectEqual(
1551         PassResult.success,
1552         createSparseConditionalConstantPropagationPass().run(&pass_ctx),
1553     );
1554     try testing.expectEqual(@as(usize, 0), failing.alloc_index);
1555 }
1556 
1557 test "choir-sccp enforces its operation nesting boundary" {
1558     const allocator = testing.allocator;
1559 
1560     var ctx = try buildTestContext(allocator);
1561     defer ctx.deinit(allocator);
1562     try ctx.allowUnregistered();
1563 
1564     var root_state = ir.Operation.State.init(
1565         "test.sccp_depth_root",
1566         ir.Location.getUnknown(),
1567     );
1568     root_state.addRegion();
1569     const root = try ctx.createOperation(root_state);
1570     var current = root;
1571     for (1..maximum_sccp_operation_depth) |_| {
1572         var child_state = ir.Operation.State.init(
1573             "test.sccp_depth_child",
1574             ir.Location.getUnknown(),
1575         );
1576         child_state.addRegion();
1577         const child = try ctx.createOperation(child_state);
1578         const block = try current.getRegion(0).?.addBlock();
1579         try block.addOperation(child);
1580         current = child;
1581     }
1582 
1583     var manager = pass_mod.PassManager.init(allocator);
1584     defer manager.deinit();
1585     try manager.addPass(createSparseConditionalConstantPropagationPass());
1586     try testing.expectEqual(PassResult.success, manager.run(root, &ctx));
1587 
1588     var one_past_state = ir.Operation.State.init(
1589         "test.sccp_depth_one_past",
1590         ir.Location.getUnknown(),
1591     );
1592     one_past_state.addRegion();
1593     const one_past = try ctx.createOperation(one_past_state);
1594     const block = try current.getRegion(0).?.addBlock();
1595     try block.addOperation(one_past);
1596     try testing.expectEqual(PassResult.failure, manager.run(root, &ctx));
1597 }
1598 
1599 test "choir-licm hoists dependent qualified operations by ancestry" {
1600     const allocator = testing.allocator;
1601 
1602     var ctx = try buildTestContext(allocator);
1603     defer ctx.deinit(allocator);
1604     try dialects.registerAllDialects(&ctx);
1605     _ = try ctx.registerOperation("test.loop_pure", .{});
1606     try ctx.registerOperationInterface(
1607         "test.loop_write",
1608         ir.interfaces.EffectOpInterface.entryFor(.{}),
1609     );
1610 
1611     const loc = ir.Location.getUnknown();
1612     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1613     const outer_block = module.getBodyBlock();
1614     const index_type = try arith.getScalarType(&ctx, .i64);
1615 
1616     var lower = try arith.ConstantOp.createInt(&ctx, loc, index_type, 0);
1617     var upper = try arith.ConstantOp.createInt(&ctx, loc, index_type, 4);
1618     var step = try arith.ConstantOp.createInt(&ctx, loc, index_type, 1);
1619     try outer_block.addOperation(lower.op);
1620     try outer_block.addOperation(upper.op);
1621     try outer_block.addOperation(step.op);
1622 
1623     var for_op = try scf.ForOp.create(&ctx, loc, lower.getResult(), upper.getResult(), step.getResult(), &.{}, &.{});
1624     try outer_block.addOperation(for_op.op);
1625 
1626     const body_block = for_op.getBodyBlock();
1627     const pure = (try arith.ConstantOp.createInt(&ctx, loc, index_type, 42)).op;
1628     try body_block.addOperation(pure);
1629     const dependent = (try arith.AddOp.create(&ctx, loc, pure.getResult(0).?, step.getResult())).op;
1630     try body_block.addOperation(dependent);
1631     var write_state = ir.Operation.State.init("test.loop_write", loc);
1632     write_state.addOperands(&.{dependent.getResult(0).?});
1633     write_state.addTypes(&.{index_type});
1634     var builder = ir.OperationBuilder.init(&ctx);
1635     const write = try builder.create(write_state);
1636     try body_block.addOperation(write);
1637     const yield = try scf.YieldOp.create(&ctx, loc, &.{});
1638     try body_block.addOperation(yield.op);
1639 
1640     try testing.expectEqual(@as(usize, 1), pure.getResult(0).?.getNumUses());
1641 
1642     var pm = try runLicmPass(allocator, module.op, &ctx);
1643     defer pm.deinit();
1644 
1645     try testing.expect(pure.parent_block == outer_block);
1646     try testing.expect(pure.prev_op == step.op);
1647     try testing.expect(pure.next_op == dependent);
1648     try testing.expect(dependent.parent_block == outer_block);
1649     try testing.expect(dependent.prev_op == pure);
1650     try testing.expect(dependent.next_op == for_op.op);
1651     try testing.expect(for_op.op.prev_op == dependent);
1652     try testing.expect(write.parent_block == body_block);
1653     try testing.expectEqual(@as(usize, 1), pure.getResult(0).?.getNumUses());
1654     try testing.expectEqual(@as(usize, 1), dependent.getResult(0).?.getNumUses());
1655     try testing.expect(write.getOperand(0).? == dependent.getResult(0).?);
1656     try testing.expectEqual(@as(u64, 1), pm.stats.passes_modified);
1657 }
1658 
1659 test "choir-licm hoists nested-loop invariants to the outermost invariant block" {
1660     const allocator = testing.allocator;
1661 
1662     var ctx = try buildTestContext(allocator);
1663     defer ctx.deinit(allocator);
1664     try dialects.registerAllDialects(&ctx);
1665     try ctx.registerOperationInterface(
1666         "test.loop_write",
1667         ir.interfaces.EffectOpInterface.entryFor(.{}),
1668     );
1669 
1670     const loc = ir.Location.getUnknown();
1671     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1672     const outer_block = module.getBodyBlock();
1673     const index_type = try arith.getScalarType(&ctx, .i64);
1674 
1675     var lower = try arith.ConstantOp.createInt(&ctx, loc, index_type, 0);
1676     var upper = try arith.ConstantOp.createInt(&ctx, loc, index_type, 4);
1677     var step = try arith.ConstantOp.createInt(&ctx, loc, index_type, 1);
1678     try outer_block.addOperation(lower.op);
1679     try outer_block.addOperation(upper.op);
1680     try outer_block.addOperation(step.op);
1681 
1682     var outer_for = try scf.ForOp.create(&ctx, loc, lower.getResult(), upper.getResult(), step.getResult(), &.{}, &.{});
1683     try outer_block.addOperation(outer_for.op);
1684     const outer_body = outer_for.getBodyBlock();
1685     const outer_iv = outer_body.arguments.items[0];
1686 
1687     var middle_for = try scf.ForOp.create(&ctx, loc, lower.getResult(), upper.getResult(), step.getResult(), &.{}, &.{});
1688     try outer_body.addOperation(middle_for.op);
1689     const middle_body = middle_for.getBodyBlock();
1690     const outer_yield = try scf.YieldOp.create(&ctx, loc, &.{});
1691     try outer_body.addOperation(outer_yield.op);
1692 
1693     var inner_for = try scf.ForOp.create(&ctx, loc, lower.getResult(), upper.getResult(), step.getResult(), &.{}, &.{});
1694     try middle_body.addOperation(inner_for.op);
1695     const inner_body = inner_for.getBodyBlock();
1696     const middle_yield = try scf.YieldOp.create(&ctx, loc, &.{});
1697     try middle_body.addOperation(middle_yield.op);
1698 
1699     var invariant = try arith.AddOp.create(&ctx, loc, outer_iv, upper.getResult());
1700     try inner_body.addOperation(invariant.op);
1701     var write_state = ir.Operation.State.init("test.loop_write", loc);
1702     write_state.addOperands(&.{invariant.getResult()});
1703     write_state.addTypes(&.{index_type});
1704     var builder = ir.OperationBuilder.init(&ctx);
1705     const write = try builder.create(write_state);
1706     try inner_body.addOperation(write);
1707     const inner_yield = try scf.YieldOp.create(&ctx, loc, &.{});
1708     try inner_body.addOperation(inner_yield.op);
1709 
1710     var pm = try runLicmPass(allocator, module.op, &ctx);
1711     defer pm.deinit();
1712 
1713     try testing.expect(invariant.op.parent_block == outer_body);
1714     try testing.expect(invariant.op.next_op == middle_for.op);
1715     try testing.expect(write.parent_block == inner_body);
1716     try testing.expectEqual(@as(u64, 1), pm.stats.passes_modified);
1717 }
1718 
1719 test "F10a retains unqualified memory accesses across ordinary operations" {
1720     const allocator = testing.allocator;
1721 
1722     var ctx = try buildTestContext(allocator);
1723     defer ctx.deinit(allocator);
1724     try dialects.registerAllDialects(&ctx);
1725     _ = try ctx.registerOperation("test.noop", .{});
1726 
1727     const loc = ir.Location.getUnknown();
1728     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1729     const block = module.getBodyBlock();
1730     const f32_type = try arith.getScalarType(&ctx, .f32);
1731     const index_type = try arith.getIndexType(&ctx);
1732     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1733     const memref_arg = try block.addArgument(memref_type, loc);
1734     const index_arg = try block.addArgument(index_type, loc);
1735     const value_arg = try block.addArgument(f32_type, loc);
1736 
1737     const store = try memref.StoreOp.create(&ctx, loc, value_arg, memref_arg, index_arg);
1738     try block.addOperation(store.op);
1739     _ = try createResultOp(&ctx, block, "test.noop", index_type);
1740     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, index_arg, f32_type);
1741     try block.addOperation(load.op);
1742     _ = try createReturn(&ctx, block, &.{load.getResult()});
1743 
1744     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1745     defer allocator.free(before_ir);
1746     var pm = try runLoadStoreForwardingPass(allocator, module.op, &ctx);
1747     defer pm.deinit();
1748     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1749     defer allocator.free(after_ir);
1750     try testing.expectEqualStrings(before_ir, after_ir);
1751 }
1752 
1753 test "choir-load-store-forward stops at generic write effects" {
1754     const allocator = testing.allocator;
1755 
1756     var ctx = try buildTestContext(allocator);
1757     defer ctx.deinit(allocator);
1758     try dialects.registerAllDialects(&ctx);
1759     try ctx.registerOperationInterface(
1760         "test.write_barrier",
1761         ir.interfaces.EffectOpInterface.entryFor(.{}),
1762     );
1763 
1764     const loc = ir.Location.getUnknown();
1765     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1766     const block = module.getBodyBlock();
1767     const f32_type = try arith.getScalarType(&ctx, .f32);
1768     const index_type = try arith.getIndexType(&ctx);
1769     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1770     const memref_arg = try block.addArgument(memref_type, loc);
1771     const index_arg = try block.addArgument(index_type, loc);
1772     const value_arg = try block.addArgument(f32_type, loc);
1773 
1774     const store = try memref.StoreOp.create(&ctx, loc, value_arg, memref_arg, index_arg);
1775     try block.addOperation(store.op);
1776     _ = try createResultOp(&ctx, block, "test.write_barrier", index_type);
1777     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, index_arg, f32_type);
1778     try block.addOperation(load.op);
1779     const ret = try createReturn(&ctx, block, &.{load.getResult()});
1780 
1781     var pm = try runLoadStoreForwardingPass(allocator, module.op, &ctx);
1782     defer pm.deinit();
1783 
1784     try testing.expectEqual(@as(usize, 1), ir.inspection.countOperationsNamed(module.op, memref.LoadOp.operation_name));
1785     try testing.expect(ret.op.getOperand(0).? == load.getResult());
1786     try testing.expectEqual(@as(u64, 0), pm.stats.passes_modified);
1787 }
1788 
1789 test "F10a retains unqualified memory accesses with independent indexes" {
1790     const allocator = testing.allocator;
1791 
1792     var ctx = try buildTestContext(allocator);
1793     defer ctx.deinit(allocator);
1794     try dialects.registerAllDialects(&ctx);
1795 
1796     const loc = ir.Location.getUnknown();
1797     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1798     const block = module.getBodyBlock();
1799     const f32_type = try arith.getScalarType(&ctx, .f32);
1800     const index_type = try arith.getIndexType(&ctx);
1801     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1802     _ = try block.addArgument(memref_type, loc);
1803     _ = try block.addArgument(index_type, loc);
1804     _ = try block.addArgument(index_type, loc);
1805     _ = try block.addArgument(f32_type, loc);
1806     _ = try block.addArgument(f32_type, loc);
1807     const memref_arg = block.getArgument(0).?;
1808     const first_index = block.getArgument(1).?;
1809     const second_index = block.getArgument(2).?;
1810     const first_value = block.getArgument(3).?;
1811     const second_value = block.getArgument(4).?;
1812 
1813     const first_store = try memref.StoreOp.create(&ctx, loc, first_value, memref_arg, first_index);
1814     try block.addOperation(first_store.op);
1815     const second_store = try memref.StoreOp.create(&ctx, loc, second_value, memref_arg, second_index);
1816     try block.addOperation(second_store.op);
1817     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, first_index, f32_type);
1818     try block.addOperation(load.op);
1819     _ = try createReturn(&ctx, block, &.{load.getResult()});
1820 
1821     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1822     defer allocator.free(before_ir);
1823     var pm = try runLoadStoreForwardingPass(allocator, module.op, &ctx);
1824     defer pm.deinit();
1825     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1826     defer allocator.free(after_ir);
1827     try testing.expectEqualStrings(before_ir, after_ir);
1828 }
1829 
1830 test "F10a retains unqualified overwritten block-local stores" {
1831     const allocator = testing.allocator;
1832 
1833     var ctx = try buildTestContext(allocator);
1834     defer ctx.deinit(allocator);
1835     try dialects.registerAllDialects(&ctx);
1836 
1837     const loc = ir.Location.getUnknown();
1838     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1839     const block = module.getBodyBlock();
1840     const f32_type = try arith.getScalarType(&ctx, .f32);
1841     const index_type = try arith.getIndexType(&ctx);
1842     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1843     _ = try block.addArgument(memref_type, loc);
1844     _ = try block.addArgument(index_type, loc);
1845     _ = try block.addArgument(f32_type, loc);
1846     _ = try block.addArgument(f32_type, loc);
1847     const memref_arg = block.getArgument(0).?;
1848     const index_arg = block.getArgument(1).?;
1849     const first_value = block.getArgument(2).?;
1850     const second_value = block.getArgument(3).?;
1851 
1852     const first_store = try memref.StoreOp.create(&ctx, loc, first_value, memref_arg, index_arg);
1853     try block.addOperation(first_store.op);
1854     const second_store = try memref.StoreOp.create(&ctx, loc, second_value, memref_arg, index_arg);
1855     try block.addOperation(second_store.op);
1856     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, index_arg, f32_type);
1857     try block.addOperation(load.op);
1858     _ = try createReturn(&ctx, block, &.{load.getResult()});
1859 
1860     const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1861     defer allocator.free(before_ir);
1862     var pm = try runDeadStoreEliminationPass(allocator, module.op, &ctx);
1863     defer pm.deinit();
1864     const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1865     defer allocator.free(after_ir);
1866     try testing.expectEqualStrings(before_ir, after_ir);
1867 }
1868 
1869 test "choir-dse preserves stores observed before overwrite" {
1870     const allocator = testing.allocator;
1871 
1872     var ctx = try buildTestContext(allocator);
1873     defer ctx.deinit(allocator);
1874     try dialects.registerAllDialects(&ctx);
1875 
1876     const loc = ir.Location.getUnknown();
1877     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1878     const block = module.getBodyBlock();
1879     const f32_type = try arith.getScalarType(&ctx, .f32);
1880     const index_type = try arith.getIndexType(&ctx);
1881     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1882     _ = try block.addArgument(memref_type, loc);
1883     _ = try block.addArgument(index_type, loc);
1884     _ = try block.addArgument(f32_type, loc);
1885     _ = try block.addArgument(f32_type, loc);
1886     const memref_arg = block.getArgument(0).?;
1887     const index_arg = block.getArgument(1).?;
1888     const first_value = block.getArgument(2).?;
1889     const second_value = block.getArgument(3).?;
1890 
1891     const first_store = try memref.StoreOp.create(&ctx, loc, first_value, memref_arg, index_arg);
1892     try block.addOperation(first_store.op);
1893     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, index_arg, f32_type);
1894     try block.addOperation(load.op);
1895     const second_store = try memref.StoreOp.create(&ctx, loc, second_value, memref_arg, index_arg);
1896     try block.addOperation(second_store.op);
1897     _ = try createReturn(&ctx, block, &.{load.getResult()});
1898 
1899     var pm = try runDeadStoreEliminationPass(allocator, module.op, &ctx);
1900     defer pm.deinit();
1901 
1902     try testing.expectEqual(@as(usize, 2), ir.inspection.countOperationsNamed(module.op, memref.StoreOp.operation_name));
1903     try testing.expect(first_store.op.parent_block != null);
1904     try testing.expect(second_store.op.parent_block != null);
1905     try testing.expectEqual(@as(u64, 0), pm.stats.passes_modified);
1906 }
1907 
1908 test "choir-dse keeps stores to distinct indexes" {
1909     const allocator = testing.allocator;
1910 
1911     var ctx = try buildTestContext(allocator);
1912     defer ctx.deinit(allocator);
1913     try dialects.registerAllDialects(&ctx);
1914 
1915     const loc = ir.Location.getUnknown();
1916     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1917     const block = module.getBodyBlock();
1918     const f32_type = try arith.getScalarType(&ctx, .f32);
1919     const index_type = try arith.getIndexType(&ctx);
1920     const memref_type = try memref.getMemrefType1D(&ctx, 16, f32_type, .host);
1921     _ = try block.addArgument(memref_type, loc);
1922     _ = try block.addArgument(index_type, loc);
1923     _ = try block.addArgument(index_type, loc);
1924     _ = try block.addArgument(f32_type, loc);
1925     _ = try block.addArgument(f32_type, loc);
1926     const memref_arg = block.getArgument(0).?;
1927     const first_index = block.getArgument(1).?;
1928     const second_index = block.getArgument(2).?;
1929     const first_value = block.getArgument(3).?;
1930     const second_value = block.getArgument(4).?;
1931 
1932     const first_store = try memref.StoreOp.create(&ctx, loc, first_value, memref_arg, first_index);
1933     try block.addOperation(first_store.op);
1934     const second_store = try memref.StoreOp.create(&ctx, loc, second_value, memref_arg, second_index);
1935     try block.addOperation(second_store.op);
1936     const load = try memref.LoadOp.create(&ctx, loc, memref_arg, first_index, f32_type);
1937     try block.addOperation(load.op);
1938     _ = try createReturn(&ctx, block, &.{load.getResult()});
1939 
1940     var pm = try runDeadStoreEliminationPass(allocator, module.op, &ctx);
1941     defer pm.deinit();
1942 
1943     try testing.expectEqual(@as(usize, 2), ir.inspection.countOperationsNamed(module.op, memref.StoreOp.operation_name));
1944     try testing.expect(first_store.op.parent_block != null);
1945     try testing.expect(second_store.op.parent_block != null);
1946     try testing.expectEqual(@as(u64, 0), pm.stats.passes_modified);
1947 }
1948 
1949 fn runEqualitySaturationPass(
1950     allocator: std.mem.Allocator,
1951     module: *ir.Operation,
1952     ctx: *ir.Context,
1953 ) !pass_mod.PassManager {
1954     var pm = pass_mod.PassManager.init(allocator);
1955     errdefer pm.deinit();
1956     try pm.addPass(createEqualitySaturationPass());
1957     try testing.expectEqual(PassResult.success, pm.run(module, ctx));
1958     return pm;
1959 }
1960 
1961 test "Precision1 choir-eqsat-arith strength-reduces multiplication by power of two" {
1962     const allocator = testing.allocator;
1963 
1964     var ctx = try buildTestContext(allocator);
1965     defer ctx.deinit(allocator);
1966 
1967     const loc = ir.Location.getUnknown();
1968     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1969     const block = module.getBodyBlock();
1970     const i32_type = try arith.getI32Type(&ctx);
1971     _ = try block.addArgument(i32_type, loc);
1972     const source = block.getArgument(0).?;
1973 
1974     var two = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 2);
1975     try block.addOperation(two.op);
1976     var product = try arith.MulOp.create(&ctx, loc, source, two.getResult());
1977     try block.addOperation(product.op);
1978     const ret = try createReturn(&ctx, block, &.{product.getResult()});
1979 
1980     var pm = try runEqualitySaturationPass(allocator, module.op, &ctx);
1981     defer pm.deinit();
1982 
1983     const replacement = ret.op.getOperand(0).?;
1984     const def_any = replacement.getDefiningOp() orelse return error.TestExpectedResult;
1985     const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1986     try testing.expectEqualStrings(arith.ShlOp.operation_name, def_op.name.name);
1987     try testing.expect(def_op.getOperand(0).? == source);
1988     try testing.expectEqual(ConstValue{ .int = 1 }, constantFromValue(def_op.getOperand(1).?).?);
1989     try ir.verifyOperation(module.op, ir.verify.default_options);
1990 }
1991 
1992 test "Precision1 choir-eqsat-arith cancels self subtraction to a materialized zero" {
1993     const allocator = testing.allocator;
1994 
1995     var ctx = try buildTestContext(allocator);
1996     defer ctx.deinit(allocator);
1997 
1998     const loc = ir.Location.getUnknown();
1999     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2000     const block = module.getBodyBlock();
2001     const i32_type = try arith.getI32Type(&ctx);
2002     _ = try block.addArgument(i32_type, loc);
2003     const source = block.getArgument(0).?;
2004 
2005     var difference = try arith.SubOp.create(&ctx, loc, source, source);
2006     try block.addOperation(difference.op);
2007     const ret = try createReturn(&ctx, block, &.{difference.getResult()});
2008 
2009     var pm = try runEqualitySaturationPass(allocator, module.op, &ctx);
2010     defer pm.deinit();
2011 
2012     const replacement = ret.op.getOperand(0).?;
2013     try testing.expectEqual(ConstValue{ .int = 0 }, constantFromValue(replacement).?);
2014     try ir.verifyOperation(module.op, ir.verify.default_options);
2015 }
2016 
2017 test "choir-eqsat-arith leaves float addition with positive zero intact" {
2018     const allocator = testing.allocator;
2019 
2020     var ctx = try buildTestContext(allocator);
2021     defer ctx.deinit(allocator);
2022 
2023     const loc = ir.Location.getUnknown();
2024     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2025     const block = module.getBodyBlock();
2026     const f32_type = try arith.getScalarType(&ctx, .f32);
2027     _ = try block.addArgument(f32_type, loc);
2028     const source = block.getArgument(0).?;
2029 
2030     var zero = try arith.ConstantOp.createFloat(&ctx, loc, f32_type, 0.0);
2031     try block.addOperation(zero.op);
2032     var total = try arith.AddOp.create(&ctx, loc, source, zero.getResult());
2033     try block.addOperation(total.op);
2034     const ret = try createReturn(&ctx, block, &.{total.getResult()});
2035 
2036     var pm = try runEqualitySaturationPass(allocator, module.op, &ctx);
2037     defer pm.deinit();
2038 
2039     try testing.expect(ret.op.getOperand(0).? == total.getResult());
2040     try testing.expectEqual(@as(u64, 0), pm.stats.passes_modified);
2041 }
2042 
2043 const EffectObservation = struct {
2044     const Event = struct {
2045         kind: enum {
2046             output,
2047             draw,
2048             retain,
2049             borrow,
2050             move,
2051             release,
2052             destroy,
2053             allocate,
2054             write,
2055             synchronize,
2056         },
2057         value: i64,
2058     };
2059     const ValueBinding = struct { value: *ir.Value, number: i64 };
2060     const Failure = enum { none, divide_by_zero, signed_overflow, bounds, lifetime, capacity };
2061     bindings: [256]ValueBinding = undefined,
2062     binding_count: usize = 0,
2063     events: [128]Event = undefined,
2064     event_count: usize = 0,
2065     failure: Failure = .none,
2066     fuel: usize = 4096,
2067     draws: i64 = 0,
2068     global_draws: i64 = 0,
2069     addressed_draws: [16]i64 = @splat(0),
2070     allocations: usize = 0,
2071     capacity: usize = 16,
2072     references: [16]usize = @splat(0),
2073     memory: [16][4]i64 = @splat(@splat(0)),
2074 
2075     fn observe(root: *ir.Operation, capacity: usize) !EffectObservation {
2076         var self = EffectObservation{ .capacity = capacity };
2077         try self.operation(root, 0);
2078         return self;
2079     }
2080 
2081     fn expectEqual(self: *const EffectObservation, after: *const EffectObservation) !void {
2082         try testing.expectEqual(self.failure, after.failure);
2083         try testing.expectEqualSlices(
2084             Event,
2085             self.events[0..self.event_count],
2086             after.events[0..after.event_count],
2087         );
2088     }
2089 
2090     /// How many events of one kind this run saw.
2091     fn countEvents(self: *const EffectObservation, kind: @FieldType(Event, "kind")) usize {
2092         var count: usize = 0;
2093         for (self.events[0..self.event_count]) |seen| {
2094             if (seen.kind == kind) count += 1;
2095         }
2096         return count;
2097     }
2098 
2099     /// Compares what the two runs handed out, which is what a caller sees.
2100     ///
2101     /// A promotion that is permitted removes writes nobody could observe, so
2102     /// the event sequences differ by exactly those writes while the outputs
2103     /// and the failure do not move. Those are compared here, and the writes
2104     /// are counted by the caller that knows how many it expects to lose.
2105     fn expectSameOutputs(self: *const EffectObservation, after: *const EffectObservation) !void {
2106         try testing.expectEqual(self.failure, after.failure);
2107         var mine: [128]i64 = undefined;
2108         var theirs: [128]i64 = undefined;
2109         var mine_count: usize = 0;
2110         var theirs_count: usize = 0;
2111         for (self.events[0..self.event_count]) |seen| {
2112             if (seen.kind != .output) continue;
2113             mine[mine_count] = seen.value;
2114             mine_count += 1;
2115         }
2116         for (after.events[0..after.event_count]) |seen| {
2117             if (seen.kind != .output) continue;
2118             theirs[theirs_count] = seen.value;
2119             theirs_count += 1;
2120         }
2121         try testing.expectEqualSlices(i64, mine[0..mine_count], theirs[0..theirs_count]);
2122     }
2123 
2124     fn bind(self: *EffectObservation, value: *ir.Value, number: i64) !void {
2125         for (self.bindings[0..self.binding_count]) |*binding| {
2126             if (binding.value == value) {
2127                 binding.number = number;
2128                 return;
2129             }
2130         }
2131         if (self.binding_count == self.bindings.len) return error.WitnessValueLimit;
2132         self.bindings[self.binding_count] = .{ .value = value, .number = number };
2133         self.binding_count += 1;
2134     }
2135 
2136     fn valueOf(self: *const EffectObservation, value: *ir.Value) !i64 {
2137         for (self.bindings[0..self.binding_count]) |binding| {
2138             if (binding.value == value) return binding.number;
2139         }
2140         return error.WitnessUndefinedValue;
2141     }
2142 
2143     fn event(self: *EffectObservation, kind: @FieldType(Event, "kind"), value: i64) !void {
2144         if (self.event_count == self.events.len) return error.WitnessEventLimit;
2145         self.events[self.event_count] = .{ .kind = kind, .value = value };
2146         self.event_count += 1;
2147     }
2148 
2149     fn block(self: *EffectObservation, body: *ir.Block, depth: usize) anyerror!void {
2150         if (depth == 32) return error.WitnessDepthLimit;
2151         var operations = body.getOperations();
2152         while (operations.next()) |op| {
2153             if (self.failure != .none) return;
2154             try self.operation(op, depth + 1);
2155         }
2156     }
2157 
2158     fn operation(self: *EffectObservation, op: *ir.Operation, depth: usize) anyerror!void {
2159         if (self.fuel == 0) return error.WitnessExecutionLimit;
2160         self.fuel -= 1;
2161         const name = op.name.name;
2162         if (std.mem.eql(
2163             u8,
2164             name,
2165             "test.module",
2166         ) or std.mem.eql(u8, name, "func.func")) return self.block(
2167             op.getRegion(0).?.getEntryBlock().?,
2168             depth,
2169         );
2170         if (std.mem.eql(u8, name, "scf.yield")) return;
2171         if (std.mem.eql(u8, name, "scf.for")) return self.loop(op, depth);
2172         if (std.mem.eql(u8, name, "scf.if")) {
2173             const selected: usize = if (try self.valueOf(op.getOperand(0).?) != 0) 0 else 1;
2174             if (op.getRegion(selected)) |region| try self.block(region.getEntryBlock().?, depth);
2175             return;
2176         }
2177         if (std.mem.eql(u8, name, "test.observe") or std.mem.eql(u8, name, "func.return")) {
2178             for (op.operands.items) |operand| try self.event(
2179                 .output,
2180                 try self.valueOf(operand.value),
2181             );
2182             return;
2183         }
2184         if (std.mem.eql(u8, name, "arith.constant")) {
2185             const value = if (op.getAttrAs(
2186                 ir.Attribute.IntegerAttr,
2187                 "value",
2188             )) |attr| attr.value else @as(
2189                 i64,
2190                 if (op.getAttrAs(ir.Attribute.BoolAttr, "value").?.value) 1 else 0,
2191             );
2192             return self.bind(op.getResult(0).?, value);
2193         }
2194         if (std.mem.eql(u8, name, "arith.add") or std.mem.eql(u8, name, "arith.div")) {
2195             return self.arithmetic(op);
2196         }
2197         if (std.mem.eql(u8, name, "arith.cmp")) {
2198             const lhs = try self.valueOf(op.getOperand(0).?);
2199             const rhs = try self.valueOf(op.getOperand(1).?);
2200             const predicate = (arith.CmpOp{ .op = op }).getPredicate();
2201             if (predicate != .ne) return error.WitnessUnsupportedComparison;
2202             return self.bind(op.getResult(0).?, if (lhs != rhs) 1 else 0);
2203         }
2204         return self.resourceOperation(op);
2205     }
2206 
2207     fn resourceOperation(self: *EffectObservation, op: *ir.Operation) !void {
2208         const name = op.name.name;
2209         if (std.mem.eql(u8, name, "test.draw") or std.mem.eql(u8, name, "test.addressed_draw")) {
2210             const address = if (op.getOperand(0)) |value| try self.valueOf(value) else 0;
2211             self.draws += 1;
2212             const index = std.math.cast(usize, address) orelse return error.WitnessResourceLimit;
2213             if (index >= self.addressed_draws.len) return error.WitnessResourceLimit;
2214             const counter = if (op.getNumOperands() == 0) counter: {
2215                 break :counter &self.global_draws;
2216             } else &self.addressed_draws[index];
2217             counter.* +%= 1;
2218             const result = address *% 17 +% counter.*;
2219             try self.event(.draw, result);
2220             return self.bind(op.getResult(0).?, result);
2221         }
2222         if (std.mem.eql(u8, name, "test.safe_read")) return self.bind(op.getResult(0).?, 7);
2223         if (std.mem.eql(u8, name, "memref.load")) return self.checkedLoad(op);
2224         if (std.mem.eql(u8, name, "memref.store")) return self.checkedStore(op);
2225         if (std.mem.eql(u8, name, "memref.fence")) return self.event(.synchronize, 0);
2226         if (std.mem.eql(u8, name, "memref.dealloc")) {
2227             const identity = try self.valueOf(op.getOperand(0).?);
2228             const index = std.math.cast(usize, identity) orelse return error.WitnessResourceLimit;
2229             if (index >= self.references.len) return error.WitnessResourceLimit;
2230             if (self.references[index] == 0) {
2231                 self.failure = .lifetime;
2232                 return;
2233             }
2234             self.references[index] = 0;
2235             return self.event(.destroy, identity);
2236         }
2237         if (std.mem.startsWith(u8, name, "rc.")) return self.ownership(op);
2238         if (std.mem.eql(u8, name, "memref.alloc") or std.mem.eql(u8, name, "memref.alloca")) {
2239             if (self.allocations == self.capacity) {
2240                 self.failure = .capacity;
2241                 return;
2242             }
2243             if (self.allocations == self.references.len) return error.WitnessResourceLimit;
2244             const identity = self.allocations;
2245             self.allocations += 1;
2246             self.references[identity] = 1;
2247             try self.event(.allocate, @intCast(identity));
2248             return self.bind(op.getResult(0).?, @intCast(identity));
2249         }
2250         return error.WitnessUnsupportedOperation;
2251     }
2252 
2253     const Access = struct { resource: usize, index: usize };
2254 
2255     fn checkedAccess(
2256         self: *EffectObservation,
2257         op: *ir.Operation,
2258         base_index: usize,
2259         index_index: usize,
2260     ) !?Access {
2261         const base = op.getOperand(base_index).?;
2262         const identity = try self.valueOf(base);
2263         const resource = std.math.cast(usize, identity) orelse return error.WitnessResourceLimit;
2264         if (resource >= self.references.len) return error.WitnessResourceLimit;
2265         if (self.references[resource] == 0) {
2266             self.failure = .lifetime;
2267             return null;
2268         }
2269         const index = try self.valueOf(op.getOperand(index_index).?);
2270         const params = memref.parseMemrefParams(base.type.getDialectParamKey().?).?;
2271         const extent = params.size orelse return error.WitnessUnsupportedExtent;
2272         if (index < 0 or @as(u64, @intCast(index)) >= extent) {
2273             self.failure = .bounds;
2274             return null;
2275         }
2276         if (index >= 4) return error.WitnessResourceLimit;
2277         return .{ .resource = resource, .index = @intCast(index) };
2278     }
2279 
2280     fn checkedLoad(self: *EffectObservation, op: *ir.Operation) !void {
2281         const access = try self.checkedAccess(op, 0, 1) orelse return;
2282         try self.bind(op.getResult(0).?, self.memory[access.resource][access.index]);
2283     }
2284 
2285     fn checkedStore(self: *EffectObservation, op: *ir.Operation) !void {
2286         const access = try self.checkedAccess(op, 1, 2) orelse return;
2287         const value = try self.valueOf(op.getOperand(0).?);
2288         self.memory[access.resource][access.index] = value;
2289         try self.event(.write, value);
2290     }
2291 
2292     fn arithmetic(self: *EffectObservation, op: *ir.Operation) !void {
2293         const lhs = try self.valueOf(op.getOperand(0).?);
2294         const rhs = try self.valueOf(op.getOperand(1).?);
2295         if (std.mem.eql(u8, op.name.name, "arith.add")) {
2296             return self.bind(op.getResult(0).?, lhs +% rhs);
2297         }
2298         if (rhs == 0) {
2299             self.failure = .divide_by_zero;
2300             return;
2301         }
2302         if (lhs == std.math.minInt(i64) and rhs == -1) {
2303             self.failure = .signed_overflow;
2304             return;
2305         }
2306         try self.bind(op.getResult(0).?, @divTrunc(lhs, rhs));
2307     }
2308 
2309     fn loop(self: *EffectObservation, op: *ir.Operation, depth: usize) !void {
2310         const loop_op = scf.ForOp{ .op = op };
2311         var induction = try self.valueOf(loop_op.getLowerBound());
2312         const upper = try self.valueOf(loop_op.getUpperBound());
2313         const step = try self.valueOf(loop_op.getStep());
2314         if (step <= 0 or op.getNumResults() != 0) return error.WitnessUnsupportedLoop;
2315         while (induction < upper and self.failure == .none) : (induction += step) {
2316             if (self.fuel == 0) return error.WitnessExecutionLimit;
2317             self.fuel -= 1;
2318             try self.bind(loop_op.getBodyBlock().getArgument(0).?, induction);
2319             try self.block(loop_op.getBodyBlock(), depth);
2320         }
2321     }
2322 
2323     fn ownership(self: *EffectObservation, op: *ir.Operation) !void {
2324         const identity = try self.valueOf(op.getOperand(0).?);
2325         const index = std.math.cast(usize, identity) orelse return error.WitnessResourceLimit;
2326         if (index >= self.references.len) return error.WitnessResourceLimit;
2327         if (self.references[index] == 0) {
2328             self.failure = .lifetime;
2329             return;
2330         }
2331         const kind: @FieldType(Event, "kind") = if (std.mem.eql(u8, op.name.name, "rc.retain"))
2332             .retain
2333         else if (std.mem.eql(
2334             u8,
2335             op.name.name,
2336             "rc.release",
2337         )) .release else if (std.mem.eql(u8, op.name.name, "rc.borrow")) .borrow else .move;
2338         try self.event(kind, identity);
2339         if (kind == .retain) self.references[index] += 1;
2340         if (kind == .release) {
2341             self.references[index] -= 1;
2342             if (self.references[index] == 0) try self.event(.destroy, identity);
2343         }
2344         if (op.getResult(0)) |result| try self.bind(result, identity);
2345     }
2346 };
2347 
2348 fn registerObservation(ctx: *ir.Context) !void {
2349     try ctx.registerOperationInterface("test.observe", ir.interfaces.EffectOpInterface.entryFor(.{
2350         .complete = true,
2351         .facts = &.{.{ .event = .{ .kind = .io } }},
2352     }));
2353 }
2354 
2355 fn observeValues(ctx: *ir.Context, block: *ir.Block, values: []const *ir.Value) !void {
2356     var state = ir.Operation.State.init("test.observe", .unknown);
2357     state.addOperands(values);
2358     try block.addOperation(try ctx.createOperation(state));
2359 }
2360 
2361 fn witnessConstant(
2362     ctx: *ir.Context,
2363     block: *ir.Block,
2364     kind: dialects.arith.ScalarKind,
2365     n: i64,
2366 ) !*ir.Value {
2367     var constant = try arith.ConstantOp.createInt(
2368         ctx,
2369         .unknown,
2370         try arith.getScalarType(ctx, kind),
2371         n,
2372     );
2373     try block.addOperation(constant.op);
2374     return constant.getResult();
2375 }
2376 
2377 const LicmWitness = struct {
2378     trips: i64,
2379     numerator: i64 = 1,
2380     denominator: i64 = 0,
2381     add: bool = false,
2382     guarded: bool = false,
2383 };
2384 
2385 fn checkLicmWitness(case: LicmWitness) !void {
2386     var ctx = try buildTestContext(testing.allocator);
2387     defer ctx.deinit(testing.allocator);
2388     try dialects.registerAllDialects(&ctx);
2389     try registerObservation(&ctx);
2390     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2391     const outer = module.getBodyBlock();
2392     const lower = try witnessConstant(&ctx, outer, .index, 0);
2393     const upper = try witnessConstant(&ctx, outer, .index, case.trips);
2394     const step = try witnessConstant(&ctx, outer, .index, 1);
2395     const lhs = try witnessConstant(&ctx, outer, .i64, case.numerator);
2396     const rhs = try witnessConstant(&ctx, outer, .i64, case.denominator);
2397     const loop = try scf.ForOp.create(&ctx, .unknown, lower, upper, step, &.{}, &.{});
2398     try outer.addOperation(loop.op);
2399     const body = loop.getBodyBlock();
2400     const candidate = if (case.add) (try arith.AddOp.create(
2401         &ctx,
2402         .unknown,
2403         lhs,
2404         rhs,
2405     )).op else (try arith.DivOp.create(&ctx, .unknown, lhs, rhs)).op;
2406     if (case.guarded) try candidate.setAttr("body_nonzero_proof", try ctx.getBoolAttr(true));
2407     try body.addOperation(candidate);
2408     try observeValues(&ctx, body, &.{candidate.getResult(0).?});
2409     try body.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
2410     const before = try EffectObservation.observe(module.op, 16);
2411     const before_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2412     defer testing.allocator.free(before_ir);
2413     var manager = try runLicmPass(testing.allocator, module.op, &ctx);
2414     defer manager.deinit();
2415     const after = try EffectObservation.observe(module.op, 16);
2416     try before.expectEqual(&after);
2417     const hoists = case.add or (case.denominator != 0 and
2418         !(case.numerator == std.math.minInt(i64) and case.denominator == -1));
2419     try testing.expect(candidate.getBlock() == if (hoists) outer else body);
2420     const after_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2421     defer testing.allocator.free(after_ir);
2422     if (!hoists) try testing.expectEqualStrings(before_ir, after_ir);
2423 }
2424 
2425 test "F10a LICM preserves skipped and executed division failures with total add control" {
2426     try checkLicmWitness(.{ .trips = 0 });
2427     try checkLicmWitness(.{ .trips = 2 });
2428     try checkLicmWitness(.{ .trips = 2, .numerator = std.math.minInt(i64), .denominator = -1 });
2429     try checkLicmWitness(.{ .trips = 0, .guarded = true });
2430     try checkLicmWitness(.{ .trips = 2, .denominator = 2 });
2431     try checkLicmWitness(.{ .trips = 0, .add = true });
2432     try checkLicmWitness(.{
2433         .trips = 2,
2434         .numerator = std.math.maxInt(i64),
2435         .denominator = 1,
2436         .add = true,
2437     });
2438 }
2439 
2440 test "F10a LICM retains branch-local proof and checks crossed observations" {
2441     var ctx = try buildTestContext(testing.allocator);
2442     defer ctx.deinit(testing.allocator);
2443     try dialects.registerAllDialects(&ctx);
2444     try registerObservation(&ctx);
2445     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2446     const outer = module.getBodyBlock();
2447     const lower = try witnessConstant(&ctx, outer, .index, 0);
2448     const upper = try witnessConstant(&ctx, outer, .index, 2);
2449     const step = try witnessConstant(&ctx, outer, .index, 1);
2450     const numerator = try witnessConstant(&ctx, outer, .i64, 1);
2451     const denominator = try witnessConstant(&ctx, outer, .i64, 0);
2452     const zero = try witnessConstant(&ctx, outer, .i64, 0);
2453     var guard = try arith.CmpOp.create(&ctx, .unknown, .ne, denominator, zero);
2454     try outer.addOperation(guard.op);
2455     const loop = try scf.ForOp.create(&ctx, .unknown, lower, upper, step, &.{}, &.{});
2456     try outer.addOperation(loop.op);
2457     const body = loop.getBodyBlock();
2458     try observeValues(&ctx, body, &.{numerator});
2459     const add = try arith.AddOp.create(&ctx, .unknown, numerator, numerator);
2460     try body.addOperation(add.op);
2461     const branch = try scf.IfOp.create(&ctx, .unknown, guard.getResult(), &.{});
2462     try body.addOperation(branch.op);
2463     const div = try arith.DivOp.create(&ctx, .unknown, numerator, denominator);
2464     try div.op.setAttr("body_nonzero_proof", try ctx.getBoolAttr(true));
2465     try branch.getThenBlock().addOperation(div.op);
2466     try observeValues(&ctx, branch.getThenBlock(), &.{div.getResult()});
2467     try branch.getThenBlock().addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
2468     try branch.getElseBlock().?.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
2469     try observeValues(&ctx, body, &.{add.getResult()});
2470     try body.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
2471     const before = try EffectObservation.observe(module.op, 16);
2472     var manager = try runLicmPass(testing.allocator, module.op, &ctx);
2473     defer manager.deinit();
2474     const after = try EffectObservation.observe(module.op, 16);
2475     try before.expectEqual(&after);
2476     try testing.expectEqual(EffectObservation.Failure.none, after.failure);
2477     try testing.expect(div.op.getBlock() == branch.getThenBlock());
2478     try testing.expect(add.op.getBlock() == body);
2479 }
2480 
2481 fn checkDeadReadWitness(expired: bool) !void {
2482     var ctx = try buildTestContext(testing.allocator);
2483     defer ctx.deinit(testing.allocator);
2484     try dialects.registerAllDialects(&ctx);
2485     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2486     const block = module.getBodyBlock();
2487     const ty = try arith.getScalarType(&ctx, .i64);
2488     const memory_type = try memref.getMemrefType1D(&ctx, 1, ty, .host);
2489     var allocation = try memref.AllocOp.createStatic(&ctx, .unknown, memory_type);
2490     try block.addOperation(allocation.op);
2491     const index = try witnessConstant(&ctx, block, .index, if (expired) 0 else 1);
2492     if (expired) {
2493         const free = try memref.DeallocOp.create(&ctx, .unknown, allocation.getResult());
2494         try block.addOperation(free.op);
2495     }
2496     const load = try memref.LoadOp.create(&ctx, .unknown, allocation.getResult(), index, ty);
2497     try block.addOperation(load.op);
2498     const before = try EffectObservation.observe(module.op, 16);
2499     var manager = try runDcePass(testing.allocator, module.op, &ctx);
2500     defer manager.deinit();
2501     const after = try EffectObservation.observe(module.op, 16);
2502     try before.expectEqual(&after);
2503     try testing.expectEqual(
2504         if (expired) EffectObservation.Failure.lifetime else .bounds,
2505         after.failure,
2506     );
2507     try testing.expectEqual(
2508         @as(usize, 1),
2509         ir.inspection.countOperationsNamed(module.op, "memref.load"),
2510     );
2511 }
2512 
2513 test "F10a DCE retains checked read failures and discards a specified safe read" {
2514     try checkDeadReadWitness(false);
2515     try checkDeadReadWitness(true);
2516     var ctx = try buildTestContext(testing.allocator);
2517     defer ctx.deinit(testing.allocator);
2518     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2519     const block = module.getBodyBlock();
2520     var state = ir.Operation.State.init(
2521         test_dialect.TestDialect.SafeReadOp.operation_name,
2522         .unknown,
2523     );
2524     state.addTypes(&.{try test_dialect.TestDialect.getI64Type(&ctx)});
2525     const safe = try ctx.createOperation(state);
2526     try block.addOperation(safe);
2527     const before = try EffectObservation.observe(module.op, 16);
2528     var manager = try runDcePass(testing.allocator, module.op, &ctx);
2529     defer manager.deinit();
2530     const after = try EffectObservation.observe(module.op, 16);
2531     try before.expectEqual(&after);
2532     try testing.expectEqual(
2533         @as(usize, 0),
2534         ir.inspection.countOperationsNamed(
2535             module.op,
2536             test_dialect.TestDialect.SafeReadOp.operation_name,
2537         ),
2538     );
2539 }
2540 
2541 fn witnessDraw(ctx: *ir.Context, block: *ir.Block, address: ?*ir.Value) !*ir.Operation {
2542     const name = if (address != null) name: {
2543         break :name test_dialect.TestDialect.AddressedDrawOp.operation_name;
2544     } else test_dialect.TestDialect.DrawOp.operation_name;
2545     var state = ir.Operation.State.init(name, .unknown);
2546     if (address) |value| state.addOperands(&.{value});
2547     state.addTypes(&.{try arith.getScalarType(ctx, .i64)});
2548     const op = try ctx.createOperation(state);
2549     try block.addOperation(op);
2550     return op;
2551 }
2552 
2553 fn checkDrawWitness(addressed: bool, seeded: bool, transform: Pass) !void {
2554     var ctx = try buildTestContext(testing.allocator);
2555     defer ctx.deinit(testing.allocator);
2556     try dialects.registerAllDialects(&ctx);
2557     try registerObservation(&ctx);
2558     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2559     const block = module.getBodyBlock();
2560     const seed = try witnessConstant(&ctx, block, .i64, 37);
2561     const address = try witnessConstant(&ctx, block, .i64, 4);
2562     const first = if (seeded) (try arith.AddOp.create(
2563         &ctx,
2564         .unknown,
2565         seed,
2566         address,
2567     )).op else try witnessDraw(
2568         &ctx,
2569         block,
2570         if (addressed) address else null,
2571     );
2572     if (seeded) try block.addOperation(first);
2573     const second = if (seeded) (try arith.AddOp.create(
2574         &ctx,
2575         .unknown,
2576         seed,
2577         address,
2578     )).op else try witnessDraw(
2579         &ctx,
2580         block,
2581         if (addressed) address else null,
2582     );
2583     if (seeded) try block.addOperation(second);
2584     try observeValues(&ctx, block, &.{ first.getResult(0).?, second.getResult(0).? });
2585     const before = try EffectObservation.observe(module.op, 16);
2586     const before_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2587     defer testing.allocator.free(before_ir);
2588     var manager = pass_mod.PassManager.init(testing.allocator);
2589     defer manager.deinit();
2590     try manager.addPass(transform);
2591     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2592     const after = try EffectObservation.observe(module.op, 16);
2593     try before.expectEqual(&after);
2594     const name = if (seeded) arith.AddOp.operation_name else if (addressed)
2595         test_dialect.TestDialect.AddressedDrawOp.operation_name
2596     else
2597         test_dialect.TestDialect.DrawOp.operation_name;
2598     try testing.expectEqual(
2599         @as(usize, if (seeded) 1 else 2),
2600         ir.inspection.countOperationsNamed(module.op, name),
2601     );
2602     if (!seeded) {
2603         const after_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2604         defer testing.allocator.free(after_ir);
2605         try testing.expectEqualStrings(before_ir, after_ir);
2606         try testing.expectEqual(@as(i64, 2), after.draws);
2607     }
2608 }
2609 
2610 test "F10a CSE retains two consuming draws and repeats an explicit seed address function" {
2611     try checkDrawWitness(false, false, createCommonSubexpressionEliminationPass());
2612     try checkDrawWitness(true, false, createCommonSubexpressionEliminationPass());
2613     try checkDrawWitness(true, true, createCommonSubexpressionEliminationPass());
2614 }
2615 
2616 fn noEffectWitnessRules(_: *@import("../egraph/root.zig").RewriteSet) anyerror!void {}
2617 
2618 fn allEffectWitnessCandidates(_: ?*anyopaque, _: *ir.Operation) anyerror!bool {
2619     return true;
2620 }
2621 
2622 const EffectSaturationPass = @import("saturation.zig").EGraphPass(.{
2623     .name = "effect-saturation-witness",
2624     .description = "Exercise consuming-state preservation through saturation",
2625     .populate_rules = noEffectWitnessRules,
2626     .options = .{ .candidate = allEffectWitnessCandidates },
2627 });
2628 
2629 test "F10a saturation retains draws even with a permissive candidate callback" {
2630     try checkDrawWitness(false, false, EffectSaturationPass.create());
2631     try checkDrawWitness(true, false, EffectSaturationPass.create());
2632     try checkDrawWitness(true, true, EffectSaturationPass.create());
2633 }
2634 
2635 fn checkSharedExtractionWitness(consuming: bool) !void {
2636     const egraph = @import("../egraph/root.zig");
2637     var ctx = try buildTestContext(testing.allocator);
2638     defer ctx.deinit(testing.allocator);
2639     try dialects.registerAllDialects(&ctx);
2640     try registerObservation(&ctx);
2641     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2642     const block = module.getBodyBlock();
2643     const initial = try witnessConstant(&ctx, block, .i64, 0);
2644     try observeValues(&ctx, block, &.{initial});
2645     const shared = if (consuming) (try witnessDraw(
2646         &ctx,
2647         block,
2648         null,
2649     )).getResult(0).? else try witnessConstant(
2650         &ctx,
2651         block,
2652         .i64,
2653         21,
2654     );
2655     const pair = try arith.AddOp.create(&ctx, .unknown, shared, shared);
2656     try block.addOperation(pair.op);
2657     try observeValues(&ctx, block, &.{pair.getResult()});
2658     const before = try EffectObservation.observe(module.op, 16);
2659     const shared_op: *ir.Operation = @ptrCast(@alignCast(shared.getDefiningOp().?));
2660     const insertion: *ir.Operation = @ptrCast(@alignCast(initial.getDefiningOp().?));
2661     var graph = egraph.Graph.init(testing.allocator);
2662     defer graph.deinit();
2663     const child = try graph.addOperation(shared_op, &.{}, 1, 10);
2664     const root = try graph.addOperation(pair.op, &.{ child, child }, 1, 11);
2665     var extraction = try egraph.Extraction.init(testing.allocator, &graph, .{});
2666     defer extraction.deinit();
2667     extraction.analyze();
2668     var rewriter = PatternRewriter.init(testing.allocator, &ctx);
2669     defer rewriter.deinit();
2670     const materialized = try extraction.materialize(&rewriter, root, insertion, 0, null);
2671     const after = try EffectObservation.observe(module.op, 16);
2672     try before.expectEqual(&after);
2673     if (consuming) {
2674         try testing.expect(materialized == null);
2675     } else {
2676         const value = materialized orelse return error.WitnessExpectedMaterialization;
2677         const new_pair: *ir.Operation = @ptrCast(@alignCast(value.getDefiningOp().?));
2678         try testing.expect(new_pair.getOperand(0) == new_pair.getOperand(1));
2679         try testing.expect(new_pair.getOperand(0) != shared);
2680         try testing.expectEqual(
2681             @as(usize, 3),
2682             ir.inspection.countOperationsNamed(module.op, arith.ConstantOp.operation_name),
2683         );
2684     }
2685 }
2686 
2687 test "F10a saturation extraction checks duplication of a shared intermediate" {
2688     try checkSharedExtractionWitness(true);
2689     try checkSharedExtractionWitness(false);
2690 }
2691 
2692 const MemoryWitnessBarrier = enum { none, release, draw, fence, failure };
2693 
2694 fn checkMemoryWitness(barrier_kind: MemoryWitnessBarrier, transform: Pass) !void {
2695     var ctx = try buildTestContext(testing.allocator);
2696     defer ctx.deinit(testing.allocator);
2697     try dialects.registerAllDialects(&ctx);
2698     try registerObservation(&ctx);
2699     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2700     const block = module.getBodyBlock();
2701     const ty = try arith.getScalarType(&ctx, .i64);
2702     const memory_type = try memref.getMemrefType1D(&ctx, 1, ty, .host);
2703     var allocation = try memref.AllocOp.createStatic(&ctx, .unknown, memory_type);
2704     try block.addOperation(allocation.op);
2705     const base = allocation.getResult();
2706     const index = try witnessConstant(&ctx, block, .index, 0);
2707     const seven = try witnessConstant(&ctx, block, .i64, 7);
2708     const nine = try witnessConstant(&ctx, block, .i64, 9);
2709     const zero = try witnessConstant(&ctx, block, .i64, 0);
2710     try observeValues(&ctx, block, &.{base});
2711     try block.addOperation((try memref.StoreOp.create(&ctx, .unknown, seven, base, index)).op);
2712     const barrier: ?*ir.Operation = switch (barrier_kind) {
2713         .none => null,
2714         .release => (try dialects.RcDialect.ReleaseOp.create(&ctx, .unknown, base)).op,
2715         .draw => try witnessDraw(&ctx, block, null),
2716         .fence => (try memref.FenceOp.create(&ctx, .unknown, .system, .seq_cst)).op,
2717         .failure => (try arith.DivOp.create(&ctx, .unknown, seven, zero)).op,
2718     };
2719     if (barrier) |op| {
2720         if (op.getBlock() == null) try block.addOperation(op);
2721         try testing.expect(invalidatesStores(op));
2722         try testing.expect(observesOrInvalidatesStores(op));
2723     }
2724     try block.addOperation((try memref.StoreOp.create(&ctx, .unknown, nine, base, index)).op);
2725     const load = try memref.LoadOp.create(&ctx, .unknown, base, index, ty);
2726     try block.addOperation(load.op);
2727     try observeValues(&ctx, block, &.{load.getResult()});
2728     const before = try EffectObservation.observe(module.op, 16);
2729     const before_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2730     defer testing.allocator.free(before_ir);
2731     var manager = pass_mod.PassManager.init(testing.allocator);
2732     defer manager.deinit();
2733     try manager.addPass(transform);
2734     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2735     const after = try EffectObservation.observe(module.op, 16);
2736     try before.expectEqual(&after);
2737     const after_ir = try ir.dump.operationAlloc(testing.allocator, module.op);
2738     defer testing.allocator.free(after_ir);
2739     try testing.expectEqualStrings(before_ir, after_ir);
2740 }
2741 
2742 test "F10a forwarding retains unqualified loads and lifetime failure ordering barriers" {
2743     for (std.enums.values(MemoryWitnessBarrier)) |barrier| {
2744         try checkMemoryWitness(barrier, createLoadStoreForwardingPass());
2745     }
2746 }
2747 
2748 test "F10a DSE retains unqualified stores and lifetime failure ordering barriers" {
2749     for (std.enums.values(MemoryWitnessBarrier)) |barrier| {
2750         try checkMemoryWitness(barrier, createDeadStoreEliminationPass());
2751     }
2752 }
2753 
2754 test "F10a promotion preserves allocation failure and the value a local cell held" {
2755     for ([_]usize{ 0, 16 }) |capacity| {
2756         var ctx = try buildTestContext(testing.allocator);
2757         defer ctx.deinit(testing.allocator);
2758         try dialects.registerAllDialects(&ctx);
2759         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2760         const typ = try arith.getScalarType(&ctx, .i64);
2761         const function = try dialects.func.FuncDialect.FuncOp.create(
2762             &ctx,
2763             .unknown,
2764             "entry",
2765             &.{},
2766             &.{typ},
2767         );
2768         try module.getBodyBlock().addOperation(function.op);
2769         const body = function.getEntryBlock();
2770         const zero = try witnessConstant(&ctx, body, .index, 0);
2771         const seven = try witnessConstant(&ctx, body, .i64, 7);
2772         const cell_type = try memref.getMemrefType1D(&ctx, 1, typ, .host);
2773         const cell = try memref.AllocaOp.createStatic(&ctx, .unknown, cell_type);
2774         try body.addOperation(cell.op);
2775         const store = try memref.StoreOp.create(&ctx, .unknown, seven, cell.getResult(), zero);
2776         try body.addOperation(store.op);
2777         const load = try memref.LoadOp.create(&ctx, .unknown, cell.getResult(), zero, typ);
2778         try body.addOperation(load.op);
2779         const ret = try dialects.func.FuncDialect.ReturnOp.create(
2780             &ctx,
2781             .unknown,
2782             &.{load.getResult()},
2783         );
2784         try body.addOperation(ret.op);
2785         const before = try EffectObservation.observe(function.op, capacity);
2786         var manager = pass_mod.PassManager.init(testing.allocator);
2787         defer manager.deinit();
2788         try manager.addPass(createMemoryPromotionPass());
2789         try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2790         const after = try EffectObservation.observe(function.op, capacity);
2791         try before.expectSameOutputs(&after);
2792         try testing.expectEqual(
2793             if (capacity == 0) EffectObservation.Failure.capacity else .none,
2794             after.failure,
2795         );
2796         const wrote: usize = if (capacity == 0) 0 else 1;
2797         try testing.expectEqual(wrote, before.countEvents(.write));
2798         try testing.expectEqual(@as(usize, 0), after.countEvents(.write));
2799         try testing.expectEqual(before.countEvents(.allocate), after.countEvents(.allocate));
2800     }
2801 }
2802 
2803 test "F10a promotion preserves the writes of a cell an access does not qualify" {
2804     for ([_]usize{ 0, 16 }) |capacity| {
2805         var ctx = try buildTestContext(testing.allocator);
2806         defer ctx.deinit(testing.allocator);
2807         try dialects.registerAllDialects(&ctx);
2808         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2809         const typ = try arith.getScalarType(&ctx, .i64);
2810         const function = try dialects.func.FuncDialect.FuncOp.create(
2811             &ctx,
2812             .unknown,
2813             "entry",
2814             &.{},
2815             &.{typ},
2816         );
2817         try module.getBodyBlock().addOperation(function.op);
2818         const body = function.getEntryBlock();
2819         const zero = try witnessConstant(&ctx, body, .index, 0);
2820         const seven = try witnessConstant(&ctx, body, .i64, 7);
2821         const cell_type = try memref.getMemrefType1D(&ctx, 1, typ, .host);
2822         const cell = try memref.AllocaOp.createStatic(&ctx, .unknown, cell_type);
2823         try body.addOperation(cell.op);
2824         const store = try memref.StoreOp.create(&ctx, .unknown, seven, cell.getResult(), zero);
2825         try body.addOperation(store.op);
2826         const computed = try arith.AddOp.create(&ctx, .unknown, zero, zero);
2827         try body.addOperation(computed.op);
2828         const load = try memref.LoadOp.create(
2829             &ctx,
2830             .unknown,
2831             cell.getResult(),
2832             computed.getResult(),
2833             typ,
2834         );
2835         try body.addOperation(load.op);
2836         const ret = try dialects.func.FuncDialect.ReturnOp.create(
2837             &ctx,
2838             .unknown,
2839             &.{load.getResult()},
2840         );
2841         try body.addOperation(ret.op);
2842         const before = try EffectObservation.observe(function.op, capacity);
2843         var manager = pass_mod.PassManager.init(testing.allocator);
2844         defer manager.deinit();
2845         try manager.addPass(createMemoryPromotionPass());
2846         try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2847         const after = try EffectObservation.observe(function.op, capacity);
2848         try before.expectEqual(&after);
2849         try testing.expectEqual(
2850             @as(usize, if (capacity == 0) 0 else 1),
2851             after.countEvents(.write),
2852         );
2853         try testing.expectEqual(
2854             if (capacity == 0) EffectObservation.Failure.capacity else .none,
2855             after.failure,
2856         );
2857     }
2858 }
2859 
2860 fn checkFoldWitness(transform: Pass) !void {
2861     for ([_]bool{ false, true }) |add| {
2862         var ctx = try buildTestContext(testing.allocator);
2863         defer ctx.deinit(testing.allocator);
2864         try dialects.registerAllDialects(&ctx);
2865         try registerObservation(&ctx);
2866         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2867         const body = module.getBodyBlock();
2868         const lhs = try witnessConstant(&ctx, body, .i64, 6);
2869         const rhs = try witnessConstant(&ctx, body, .i64, if (add) 0 else 1);
2870         const operation = if (add) (try arith.AddOp.create(
2871             &ctx,
2872             .unknown,
2873             lhs,
2874             rhs,
2875         )).op else (try arith.DivOp.create(&ctx, .unknown, lhs, rhs)).op;
2876         try body.addOperation(operation);
2877         const result = operation.getResult(0).?;
2878         try observeValues(&ctx, body, &.{result});
2879         const before = try EffectObservation.observe(module.op, 16);
2880         var manager = pass_mod.PassManager.init(testing.allocator);
2881         defer manager.deinit();
2882         try manager.addPass(transform);
2883         try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2884         const after = try EffectObservation.observe(module.op, 16);
2885         try before.expectEqual(&after);
2886         const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
2887         try testing.expect(output.getOperand(0).? != result);
2888     }
2889 }
2890 
2891 test "Precision1 constant folding qualifies wrapping add and proved division" {
2892     try checkFoldWitness(createConstantFoldingPass());
2893 }
2894 
2895 test "Precision1 canonicalization qualifies add and proved division" {
2896     try checkFoldWitness(canonicalization.createCanonicalizationPass());
2897 }
2898 
2899 fn checkSelectionWitness(transform: Pass, selected: ?bool) !void {
2900     var ctx = try buildTestContext(testing.allocator);
2901     defer ctx.deinit(testing.allocator);
2902     try dialects.registerAllDialects(&ctx);
2903     try registerObservation(&ctx);
2904     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2905     const body = module.getBodyBlock();
2906     const one = try witnessConstant(&ctx, body, .i64, 1);
2907     const zero = try witnessConstant(&ctx, body, .i64, 0);
2908     const condition = if (selected) |value| try witnessConstant(
2909         &ctx,
2910         body,
2911         .bool,
2912         if (value) 1 else 0,
2913     ) else condition: {
2914         const cmp = try arith.CmpOp.create(&ctx, .unknown, .ne, one, zero);
2915         try body.addOperation(cmp.op);
2916         break :condition cmp.getResult();
2917     };
2918     const branch = try scf.IfOp.create(&ctx, .unknown, condition, &.{});
2919     try body.addOperation(branch.op);
2920     if (selected != null) {
2921         const division = try arith.DivOp.create(&ctx, .unknown, one, zero);
2922         try branch.getThenBlock().addOperation(division.op);
2923         try observeValues(&ctx, branch.getThenBlock(), &.{division.getResult()});
2924     }
2925     const then_yield = try scf.YieldOp.create(&ctx, .unknown, &.{});
2926     try branch.getThenBlock().addOperation(then_yield.op);
2927     const else_yield = try scf.YieldOp.create(&ctx, .unknown, &.{});
2928     try branch.getElseBlock().?.addOperation(else_yield.op);
2929     try observeValues(&ctx, body, &.{one});
2930     const before = try EffectObservation.observe(module.op, 16);
2931     var manager = pass_mod.PassManager.init(testing.allocator);
2932     defer manager.deinit();
2933     try manager.addPass(transform);
2934     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2935     const after = try EffectObservation.observe(module.op, 16);
2936     try before.expectEqual(&after);
2937     if (selected == null) try testing.expect(ctx.containsOperation(branch.op));
2938 }
2939 
2940 test "F10a canonicalization requires proved region selection" {
2941     try checkSelectionWitness(canonicalization.createCanonicalizationPass(), null);
2942     try checkSelectionWitness(canonicalization.createCanonicalizationPass(), false);
2943     try checkSelectionWitness(canonicalization.createCanonicalizationPass(), true);
2944 }
2945 
2946 test "F10a SCCP qualifies add and preserves selected region observations" {
2947     try checkFoldWitness(createSparseConditionalConstantPropagationPass());
2948     try checkSelectionWitness(createSparseConditionalConstantPropagationPass(), null);
2949     try checkSelectionWitness(createSparseConditionalConstantPropagationPass(), false);
2950     try checkSelectionWitness(createSparseConditionalConstantPropagationPass(), true);
2951 }
2952 
2953 fn checkOwnershipWitness(branch_taken: ?bool, pipeline: bool) !void {
2954     var ctx = try buildTestContext(testing.allocator);
2955     defer ctx.deinit(testing.allocator);
2956     try dialects.registerAllDialects(&ctx);
2957     try registerObservation(&ctx);
2958     const rc = dialects.rc.RcDialect;
2959     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
2960     const outer = module.getBodyBlock();
2961     const typ = try arith.getScalarType(&ctx, .i64);
2962     const cell_type = try memref.getMemrefType1D(&ctx, 1, typ, .host);
2963     const cell = try memref.AllocOp.createStatic(&ctx, .unknown, cell_type);
2964     try outer.addOperation(cell.op);
2965     const body = if (branch_taken) |taken| body: {
2966         const condition = try witnessConstant(&ctx, outer, .bool, if (taken) 1 else 0);
2967         const branch = try scf.IfOp.create(&ctx, .unknown, condition, &.{});
2968         try outer.addOperation(branch.op);
2969         const yield = try scf.YieldOp.create(&ctx, .unknown, &.{});
2970         try branch.getElseBlock().?.addOperation(yield.op);
2971         break :body branch.getThenBlock();
2972     } else outer;
2973     const retained = try rc.RetainOp.create(&ctx, .unknown, cell.getResult());
2974     try body.addOperation(retained.op);
2975     const borrowed = try rc.BorrowOp.create(&ctx, .unknown, cell.getResult());
2976     try body.addOperation(borrowed.op);
2977     try observeValues(&ctx, body, &.{borrowed.getResult()});
2978     const inner_release = try rc.ReleaseOp.create(&ctx, .unknown, cell.getResult());
2979     try body.addOperation(inner_release.op);
2980     if (branch_taken != null) {
2981         try body.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
2982     }
2983     const moved = try rc.MoveOp.create(&ctx, .unknown, cell.getResult());
2984     try outer.addOperation(moved.op);
2985     try outer.addOperation((try rc.ReleaseOp.create(&ctx, .unknown, moved.getResult())).op);
2986     const one = try witnessConstant(&ctx, outer, .i64, 1);
2987     const dead_add = try arith.AddOp.create(&ctx, .unknown, one, one);
2988     try outer.addOperation(dead_add.op);
2989     const before = try EffectObservation.observe(module.op, 16);
2990     var manager = pass_mod.PassManager.init(testing.allocator);
2991     defer manager.deinit();
2992     if (pipeline) {
2993         try addDefaultOptimizationPipeline(&manager);
2994     } else {
2995         try manager.addPass(createDeadCodeEliminationPass());
2996     }
2997     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
2998     const after = try EffectObservation.observe(module.op, 16);
2999     try before.expectEqual(&after);
3000     try testing.expectEqual(EffectObservation.Failure.none, after.failure);
3001     var destructions: usize = 0;
3002     for (after.events[0..after.event_count]) |event| {
3003         if (event.kind == .destroy) destructions += 1;
3004     }
3005     try testing.expectEqual(@as(usize, 1), destructions);
3006     if (!pipeline) try testing.expect(!ctx.containsOperation(dead_add.op));
3007 }
3008 
3009 test "F10a ownership preserves allocation backed aliases branch traces and one destructor" {
3010     for ([_]bool{ false, true }) |pipeline| {
3011         try checkOwnershipWitness(null, pipeline);
3012         try checkOwnershipWitness(false, pipeline);
3013         try checkOwnershipWitness(true, pipeline);
3014     }
3015 }
3016 
3017 fn checkAllocationIdentityWitness(pipeline: bool) !void {
3018     var ctx = try buildTestContext(testing.allocator);
3019     defer ctx.deinit(testing.allocator);
3020     try dialects.registerAllDialects(&ctx);
3021     try registerObservation(&ctx);
3022     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3023     const body = module.getBodyBlock();
3024     const typ = try arith.getScalarType(&ctx, .i64);
3025     const cell_type = try memref.getMemrefType1D(&ctx, 1, typ, .host);
3026     const first = try memref.AllocOp.createStatic(&ctx, .unknown, cell_type);
3027     const second = try memref.AllocOp.createStatic(&ctx, .unknown, cell_type);
3028     try body.addOperation(first.op);
3029     try body.addOperation(second.op);
3030     try observeValues(&ctx, body, &.{ first.getResult(), second.getResult() });
3031     const before = try EffectObservation.observe(module.op, 16);
3032     var manager = pass_mod.PassManager.init(testing.allocator);
3033     defer manager.deinit();
3034     if (pipeline) {
3035         try addDefaultOptimizationPipeline(&manager);
3036     } else {
3037         try manager.addPass(createCommonSubexpressionEliminationPass());
3038     }
3039     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
3040     const after = try EffectObservation.observe(module.op, 16);
3041     try before.expectEqual(&after);
3042     try testing.expectEqual(@as(usize, 2), after.allocations);
3043 }
3044 
3045 fn checkAllocationRegionWitness(pipeline: bool) !void {
3046     var ctx = try buildTestContext(testing.allocator);
3047     defer ctx.deinit(testing.allocator);
3048     try dialects.registerAllDialects(&ctx);
3049     try registerObservation(&ctx);
3050     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3051     const outer = module.getBodyBlock();
3052     const zero = try witnessConstant(&ctx, outer, .i64, 0);
3053     const one = try witnessConstant(&ctx, outer, .i64, 1);
3054     const loop = try scf.ForOp.create(&ctx, .unknown, zero, zero, one, &.{}, &.{});
3055     try outer.addOperation(loop.op);
3056     const body = loop.getBodyBlock();
3057     const add = try arith.AddOp.create(&ctx, .unknown, zero, one);
3058     try body.addOperation(add.op);
3059     const typ = try arith.getScalarType(&ctx, .i64);
3060     const cell_type = try memref.getMemrefType1D(&ctx, 1, typ, .host);
3061     const cell = try memref.AllocOp.createStatic(&ctx, .unknown, cell_type);
3062     try body.addOperation(cell.op);
3063     try observeValues(&ctx, body, &.{ cell.getResult(), add.getResult() });
3064     try body.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
3065     const before = try EffectObservation.observe(module.op, 0);
3066     var manager = pass_mod.PassManager.init(testing.allocator);
3067     defer manager.deinit();
3068     if (pipeline) {
3069         try addDefaultOptimizationPipeline(&manager);
3070     } else {
3071         try manager.addPass(createLoopInvariantCodeMotionPass());
3072     }
3073     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
3074     const after = try EffectObservation.observe(module.op, 0);
3075     try before.expectEqual(&after);
3076     try testing.expect(cell.op.getBlock() == body);
3077     if (!pipeline) try testing.expect(add.op.getBlock() == outer);
3078 }
3079 
3080 test "F10a allocation preserves fresh identities" {
3081     for ([_]bool{ false, true }) |pipeline| try checkAllocationIdentityWitness(pipeline);
3082 }
3083 
3084 test "F10a allocation preserves capacity failure region" {
3085     for ([_]bool{ false, true }) |pipeline| try checkAllocationRegionWitness(pipeline);
3086 }
3087 
3088 fn precisionValueOperation(
3089     ctx: *ir.Context,
3090     block: *ir.Block,
3091     name: []const u8,
3092     typ: ir.Type,
3093     operands: []const *ir.Value,
3094 ) !*ir.Operation {
3095     var state = ir.Operation.State.init(name, .unknown);
3096     state.addOperands(operands);
3097     state.addTypes(&.{typ});
3098     const operation = try ctx.createOperation(state);
3099     try block.addOperation(operation);
3100     return operation;
3101 }
3102 
3103 fn precisionFloat(
3104     ctx: *ir.Context,
3105     block: *ir.Block,
3106     kind: dialects.arith.ScalarKind,
3107     value: f64,
3108 ) !*ir.Value {
3109     var constant = try arith.ConstantOp.createFloat(
3110         ctx,
3111         .unknown,
3112         try arith.getScalarType(ctx, kind),
3113         value,
3114     );
3115     try block.addOperation(constant.op);
3116     return constant.getResult();
3117 }
3118 
3119 const PrecisionLicmCase = struct {
3120     name: []const u8,
3121     kind: dialects.arith.ScalarKind,
3122     divisor: ?i64 = null,
3123     unary: bool = false,
3124     hoists: bool = true,
3125 };
3126 
3127 fn checkPrecisionLicm(case: PrecisionLicmCase) !void {
3128     var ctx = try buildTestContext(testing.allocator);
3129     defer ctx.deinit(testing.allocator);
3130     try dialects.registerAllDialects(&ctx);
3131     try registerObservation(&ctx);
3132     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3133     const outer = module.getBodyBlock();
3134     const typ = try arith.getScalarType(&ctx, case.kind);
3135     const lhs = try outer.addArgument(typ, .unknown);
3136     const rhs = if (case.divisor) |n|
3137         try witnessConstant(&ctx, outer, case.kind, n)
3138     else
3139         try outer.addArgument(typ, .unknown);
3140     const lower = try witnessConstant(&ctx, outer, .index, 0);
3141     const upper = try witnessConstant(&ctx, outer, .index, 0);
3142     const step = try witnessConstant(&ctx, outer, .index, 1);
3143     const loop = try scf.ForOp.create(&ctx, .unknown, lower, upper, step, &.{}, &.{});
3144     try outer.addOperation(loop.op);
3145     const body = loop.getBodyBlock();
3146     const candidate = try precisionValueOperation(
3147         &ctx,
3148         body,
3149         case.name,
3150         typ,
3151         if (case.unary) &.{lhs} else &.{ lhs, rhs },
3152     );
3153     try observeValues(&ctx, body, &.{candidate.getResult(0).?});
3154     try body.addOperation((try scf.YieldOp.create(&ctx, .unknown, &.{})).op);
3155     var manager = try runLicmPass(testing.allocator, module.op, &ctx);
3156     defer manager.deinit();
3157     try testing.expect(candidate.getBlock() == if (case.hoists) outer else body);
3158 }
3159 
3160 test "Precision1 LICM hoists typed total arithmetic and retains unresolved division" {
3161     for ([_]PrecisionLicmCase{
3162         .{ .name = "arith.mul", .kind = .f32 },
3163         .{ .name = "arith.sqrt", .kind = .f64, .unary = true },
3164         .{ .name = "arith.sub", .kind = .i32 },
3165         .{ .name = "arith.div", .kind = .i64, .hoists = false },
3166         .{ .name = "arith.div", .kind = .i64, .divisor = 2 },
3167         .{ .name = "arith.div", .kind = .i64, .divisor = -1, .hoists = false },
3168     }) |case| try checkPrecisionLicm(case);
3169 }
3170 
3171 test "Precision1 DCE erases only unused shifts with a proved count" {
3172     for ([_]?i64{ 0, 7, 8, -1, null }) |count| {
3173         var ctx = try buildTestContext(testing.allocator);
3174         defer ctx.deinit(testing.allocator);
3175         try dialects.registerAllDialects(&ctx);
3176         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3177         const body = module.getBodyBlock();
3178         const typ = try arith.getScalarType(&ctx, .i8);
3179         const lhs = try body.addArgument(typ, .unknown);
3180         const rhs = if (count) |n| try witnessConstant(
3181             &ctx,
3182             body,
3183             .i8,
3184             n,
3185         ) else try body.addArgument(typ, .unknown);
3186         _ = try precisionValueOperation(&ctx, body, "arith.shl", typ, &.{ lhs, rhs });
3187         var manager = try runDcePass(testing.allocator, module.op, &ctx);
3188         defer manager.deinit();
3189         const erased = if (count) |n| n >= 0 and n < 8 else false;
3190         try testing.expectEqual(
3191             @as(usize, if (erased) 0 else 1),
3192             ir.inspection.countOperationsNamed(module.op, "arith.shl"),
3193         );
3194     }
3195 }
3196 
3197 test "Precision1 CSE floating add requires the unobservable default environment" {
3198     for ([_]bool{ false, true }) |observable| {
3199         var ctx = try buildTestContext(testing.allocator);
3200         defer ctx.deinit(testing.allocator);
3201         try dialects.registerAllDialects(&ctx);
3202         try registerObservation(&ctx);
3203         ctx.arithmetic_policy.environment_observable = observable;
3204         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3205         const body = module.getBodyBlock();
3206         const typ = try arith.getScalarType(&ctx, .f32);
3207         const lhs = try body.addArgument(typ, .unknown);
3208         const rhs = try body.addArgument(typ, .unknown);
3209         const first = try precisionValueOperation(&ctx, body, "arith.add", typ, &.{ lhs, rhs });
3210         const second = try precisionValueOperation(&ctx, body, "arith.add", typ, &.{ lhs, rhs });
3211         try observeValues(&ctx, body, &.{ first.getResult(0).?, second.getResult(0).? });
3212         var manager = pass_mod.PassManager.init(testing.allocator);
3213         defer manager.deinit();
3214         try manager.addPass(createCommonSubexpressionEliminationPass());
3215         try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
3216         const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
3217         try testing.expectEqual(!observable, output.getOperand(0).? == output.getOperand(1).?);
3218         try testing.expectEqual(
3219             @as(usize, if (observable) 2 else 1),
3220             ir.inspection.countOperationsNamed(module.op, "arith.add"),
3221         );
3222     }
3223 }
3224 
3225 test "Precision1 negative sqrt explicitly declines folding and positive sqrt folds" {
3226     for ([_]f64{ -1, 4 }) |input| {
3227         var ctx = try buildTestContext(testing.allocator);
3228         defer ctx.deinit(testing.allocator);
3229         try dialects.registerAllDialects(&ctx);
3230         try registerObservation(&ctx);
3231         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3232         const body = module.getBodyBlock();
3233         const value = try precisionFloat(&ctx, body, .f64, input);
3234         const candidate = try precisionValueOperation(
3235             &ctx,
3236             body,
3237             "arith.sqrt",
3238             value.type,
3239             &.{value},
3240         );
3241         try observeValues(&ctx, body, &.{candidate.getResult(0).?});
3242         var manager = try runConstantFoldingPass(testing.allocator, module.op, &ctx);
3243         defer manager.deinit();
3244         const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
3245         const raw = output.getOperand(0).?.getDefiningOp().?;
3246         const definition: *ir.Operation = @ptrCast(@alignCast(raw));
3247         if (input < 0) {
3248             try testing.expectEqualStrings("arith.sqrt", definition.name.name);
3249         } else {
3250             try testing.expectEqualStrings("arith.constant", definition.name.name);
3251             try testing.expectEqual(
3252                 @as(f64, 2),
3253                 definition.getAttrAs(ir.Attribute.FloatAttr, "value").?.getValue(),
3254             );
3255         }
3256     }
3257 }
3258 
3259 test "Precision1 integer to float casts fold for every scalar integer and float type" {
3260     const sources = [_]dialects.arith.ScalarKind{
3261         .i8, .i16, .i32, .i64, .u8, .u16, .u32, .u64, .index,
3262     };
3263     for (sources) |source| {
3264         for ([_]dialects.arith.ScalarKind{ .f16, .bf16, .f32, .f64 }) |target| {
3265             var ctx = try buildTestContext(testing.allocator);
3266             defer ctx.deinit(testing.allocator);
3267             try dialects.registerAllDialects(&ctx);
3268             try registerObservation(&ctx);
3269             const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3270             const body = module.getBodyBlock();
3271             const value = try witnessConstant(&ctx, body, source, 37);
3272             const typ = try arith.getScalarType(&ctx, target);
3273             const candidate = try precisionValueOperation(&ctx, body, "arith.cast", typ, &.{value});
3274             try observeValues(&ctx, body, &.{candidate.getResult(0).?});
3275             var manager = try runConstantFoldingPass(testing.allocator, module.op, &ctx);
3276             defer manager.deinit();
3277             const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
3278             const raw = output.getOperand(0).?.getDefiningOp().?;
3279             const definition: *ir.Operation = @ptrCast(@alignCast(raw));
3280             try testing.expectEqualStrings("arith.constant", definition.name.name);
3281             try testing.expectEqual(
3282                 @as(f64, 37),
3283                 definition.getAttrAs(ir.Attribute.FloatAttr, "value").?.getValue(),
3284             );
3285         }
3286     }
3287 }
3288 
3289 fn precisionEvaluateIdentity(
3290     _: *const anyopaque,
3291     operands: []const ir.Attribute,
3292     _: *const ir.interfaces.EvalContext,
3293 ) ir.interfaces.EvalError!ir.Attribute {
3294     if (operands.len != 1) return error.InvalidOperand;
3295     return operands[0];
3296 }
3297 
3298 test "Precision1 constant folding uses a non arith Evaluatable and preserves its unknown control" {
3299     for ([_]bool{ false, true }) |qualified| {
3300         var ctx = try buildTestContext(testing.allocator);
3301         defer ctx.deinit(testing.allocator);
3302         try registerObservation(&ctx);
3303         try ctx.registerOperationInterface(
3304             "test.evaluate_identity",
3305             ir.interfaces.Evaluatable.entryFor(
3306                 ir.interfaces.Evaluatable.canAlwaysFold,
3307                 precisionEvaluateIdentity,
3308             ),
3309         );
3310         if (qualified) try ctx.registerOperationInterface(
3311             "test.evaluate_identity",
3312             ir.interfaces.EffectOpInterface.entryFor(.{
3313                 .complete = true,
3314                 .facts = &.{.{ .result = .{ .index = 0, .ownership = .none } }},
3315             }),
3316         );
3317         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3318         const body = module.getBodyBlock();
3319         const value = try witnessConstant(&ctx, body, .i32, 19);
3320         const candidate = try precisionValueOperation(
3321             &ctx,
3322             body,
3323             "test.evaluate_identity",
3324             value.type,
3325             &.{value},
3326         );
3327         try observeValues(&ctx, body, &.{candidate.getResult(0).?});
3328         var manager = try runConstantFoldingPass(testing.allocator, module.op, &ctx);
3329         defer manager.deinit();
3330         try testing.expectEqual(
3331             @as(usize, if (qualified) 0 else 1),
3332             ir.inspection.countOperationsNamed(module.op, "test.evaluate_identity"),
3333         );
3334         if (qualified) {
3335             const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
3336             try testing.expectEqual(
3337                 ConstValue{ .int = 19 },
3338                 constantFromValue(output.getOperand(0).?).?,
3339             );
3340         }
3341     }
3342 }
3343 
3344 const PrecisionCastCase = struct {
3345     value: f64,
3346     target: dialects.arith.ScalarKind,
3347     expected: ?i64,
3348 };
3349 
3350 const precision_cast_cases = [_]PrecisionCastCase{
3351     .{ .value = 127.9, .target = .i8, .expected = 127 },
3352     .{ .value = -128.9, .target = .i8, .expected = -128 },
3353     .{ .value = 128, .target = .i8, .expected = null },
3354     .{ .value = -129, .target = .i8, .expected = null },
3355     .{ .value = 255.9, .target = .u8, .expected = 255 },
3356     .{ .value = -0.9, .target = .u8, .expected = 0 },
3357     .{ .value = 256, .target = .u8, .expected = null },
3358     .{ .value = -1, .target = .u8, .expected = null },
3359     .{ .value = 0x1p63, .target = .i64, .expected = null },
3360     .{ .value = -0x1p63, .target = .i64, .expected = std.math.minInt(i64) },
3361     .{ .value = -0x1.0000000000001p63, .target = .i64, .expected = null },
3362     .{ .value = 0x1.fffffffffffffp62, .target = .i64, .expected = 9223372036854774784 },
3363     .{ .value = 0x1p64, .target = .u64, .expected = null },
3364     .{ .value = 0x1.fffffffffffffp63, .target = .u64, .expected = -2048 },
3365     .{ .value = 0x1p64, .target = .index, .expected = null },
3366     .{ .value = 0x1p63, .target = .index, .expected = std.math.minInt(i64) },
3367     .{ .value = std.math.nan(f64), .target = .i32, .expected = null },
3368     .{ .value = std.math.inf(f64), .target = .i32, .expected = null },
3369     .{ .value = -std.math.inf(f64), .target = .u32, .expected = null },
3370 };
3371 
3372 fn checkPrecisionFloatCast(case: PrecisionCastCase, used: bool) !void {
3373     var ctx = try buildTestContext(testing.allocator);
3374     defer ctx.deinit(testing.allocator);
3375     try dialects.registerAllDialects(&ctx);
3376     try registerObservation(&ctx);
3377     const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3378     const body = module.getBodyBlock();
3379     const value = try precisionFloat(&ctx, body, .f64, case.value);
3380     const typ = try arith.getScalarType(&ctx, case.target);
3381     const cast = try precisionValueOperation(&ctx, body, "arith.cast", typ, &.{value});
3382     if (used) try observeValues(&ctx, body, &.{cast.getResult(0).?});
3383     var manager = pass_mod.PassManager.init(testing.allocator);
3384     defer manager.deinit();
3385     try manager.addPass(createConstantFoldingPass());
3386     if (!used) try manager.addPass(createDeadCodeEliminationPass());
3387     try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
3388     try testing.expectEqual(
3389         @as(usize, if (case.expected == null) 1 else 0),
3390         ir.inspection.countOperationsNamed(module.op, "arith.cast"),
3391     );
3392     if (used) {
3393         if (case.expected) |expected| {
3394             const output: *ir.Operation = @ptrCast(@alignCast(body.operations.tail.?));
3395             try testing.expectEqual(
3396                 ConstValue{ .int = expected },
3397                 constantFromValue(output.getOperand(0).?).?,
3398             );
3399         }
3400     }
3401 }
3402 
3403 test "Precision1 float to integer cast folds truncated endpoints and preserves domain failures" {
3404     for (precision_cast_cases) |case| {
3405         try checkPrecisionFloatCast(case, true);
3406         try checkPrecisionFloatCast(case, false);
3407     }
3408 }
3409 
3410 test "Precision1 float to integer cast retains variable sources and observable environments" {
3411     for ([_]bool{ false, true }) |observable| {
3412         var ctx = try buildTestContext(testing.allocator);
3413         defer ctx.deinit(testing.allocator);
3414         try dialects.registerAllDialects(&ctx);
3415         ctx.arithmetic_policy.environment_observable = observable;
3416         const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, .unknown);
3417         const body = module.getBodyBlock();
3418         const source = try arith.getScalarType(&ctx, .f32);
3419         const target = try arith.getScalarType(&ctx, .i32);
3420         const value = if (observable) try precisionFloat(
3421             &ctx,
3422             body,
3423             .f32,
3424             37,
3425         ) else try body.addArgument(source, .unknown);
3426         _ = try precisionValueOperation(&ctx, body, "arith.cast", target, &.{value});
3427         var manager = pass_mod.PassManager.init(testing.allocator);
3428         defer manager.deinit();
3429         try manager.addPass(createConstantFoldingPass());
3430         try manager.addPass(createDeadCodeEliminationPass());
3431         try testing.expectEqual(PassResult.success, manager.run(module.op, &ctx));
3432         try testing.expectEqual(
3433             @as(usize, 1),
3434             ir.inspection.countOperationsNamed(module.op, "arith.cast"),
3435         );
3436     }
3437 }