lib/choir/src/passes/canonicalization.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../core/root.zig");
3 const rewrite = ir.rewrite;
4 const pass = @import("pass/root.zig");
5 const conversion = @import("conversion.zig");
6 const effects = @import("effects.zig");
7 const registry = @import("pipeline.zig");
8 const dialects = @import("../dialects/root.zig");
9
10 const arith = dialects.ArithDialect;
11 const CmpPredicate = dialects.arith.CmpPredicate;
12 const scf = dialects.ScfDialect;
13
14 pub const canonicalization_pass_name = "choir-canonicalize";
15 pub const canonicalization_pass_description =
16 "Apply Choir rewrite patterns and remove trivially dead operations";
17
18 pub const PopulatePatternsFn = *const fn (*rewrite.RewritePatternSet) anyerror!void;
19
20 const RegisteredDialect = struct {
21 name: []const u8,
22 vtable: *const rewrite.DialectCanonicalizationInterface.VTable,
23 };
24
25 const InitialPatternFacts = struct {
26 registered_fold_count: usize,
27 };
28
29 const InitialPatternLimits = struct {
30 facts: InitialPatternFacts,
31
32 const empty: InitialPatternLimits = .{
33 .facts = .{ .registered_fold_count = 0 },
34 };
35
36 fn inspect(ctx: *ir.Context) error{CapacityOverflow}!InitialPatternLimits {
37 var registered_fold_count: usize = 0;
38 var iter = ctx.dialect_registry.operation_registry.ops.iterator();
39 while (iter.next()) |entry| {
40 const op_info = entry.value_ptr.*;
41 if (op_info.hasInterface(ir.interfaces.FoldOpInterface.id)) {
42 registered_fold_count = std.math.add(
43 usize,
44 registered_fold_count,
45 1,
46 ) catch return error.CapacityOverflow;
47 }
48 }
49 return .{
50 .facts = .{ .registered_fold_count = registered_fold_count },
51 };
52 }
53 };
54
55 const InitialPatternCapacity = struct {
56 pattern_count: usize,
57 fold_name_count: usize,
58
59 fn derive(
60 limits: InitialPatternLimits,
61 include_builtin_patterns: bool,
62 include_registered_fold_patterns: bool,
63 ) error{CapacityOverflow}!InitialPatternCapacity {
64 const builtin_count = if (include_builtin_patterns)
65 builtin_canonicalization_patterns.len
66 else
67 0;
68 const fold_name_count = if (include_registered_fold_patterns)
69 limits.facts.registered_fold_count
70 else
71 0;
72 const pattern_count = std.math.add(
73 usize,
74 builtin_count,
75 fold_name_count,
76 ) catch return error.CapacityOverflow;
77 return .{
78 .pattern_count = pattern_count,
79 .fold_name_count = fold_name_count,
80 };
81 }
82 };
83
84 fn byte_slice_less_than(_: void, lhs: []const u8, rhs: []const u8) bool {
85 return std.mem.lessThan(u8, lhs, rhs);
86 }
87
88 fn registered_dialect_less_than(
89 _: void,
90 lhs: RegisteredDialect,
91 rhs: RegisteredDialect,
92 ) bool {
93 return std.mem.lessThan(u8, lhs.name, rhs.name);
94 }
95
96 pub const PatternPopulationBounds = struct {
97 patterns: u64,
98 name_bytes: u64,
99 visits: u64,
100 bytes: u64,
101 };
102
103 /// Reservation for the default builtin/fold population, registered dialect
104 /// patterns, and the caller's extra specs. This only reads population inputs.
105 pub fn patternPopulationBounds(
106 context: *ir.Context,
107 extra: []const rewrite.RewritePatternSpec,
108 ) !PatternPopulationBounds {
109 const work = pass.work;
110 const limits = InitialPatternLimits.inspect(context) catch return error.WorkOverflow;
111 const initial = InitialPatternCapacity.derive(limits, true, true) catch return error.WorkOverflow;
112 var count = try work.add(initial.pattern_count, extra.len);
113 var names: u64 = 0;
114 for (extra) |spec| {
115 names = try work.add(names, try work.add(spec.name.len, spec.root_op_name.len));
116 }
117 for (builtin_canonicalization_patterns) |pattern| {
118 names = try work.add(names, try work.add(pattern.spec.name.len, pattern.spec.root_op_name.len));
119 }
120 var operations = context.dialect_registry.operation_registry.ops.iterator();
121 while (operations.next()) |entry| names = try work.add(names, entry.key_ptr.*.len);
122 var dialect_count: u64 = 0;
123 var interface_count: u64 = 0;
124 var interfaces = context.dialect_registry.interfaces.iterator();
125 while (interfaces.next()) |entry| {
126 names = try work.add(names, entry.key_ptr.*.len);
127 interface_count = try work.add(interface_count, entry.value_ptr.items.len);
128 for (entry.value_ptr.items) |interface| {
129 if (interface.id != rewrite.DialectCanonicalizationInterface.id) continue;
130 const table = rewrite.DialectCanonicalizationInterface.fromOpaque(interface.vtable);
131 dialect_count = try work.add(dialect_count, 1);
132 count = try work.add(count, table.patterns.len);
133 for (table.patterns) |pattern| {
134 names = try work.add(names, try work.add(pattern.spec.name.len, pattern.spec.root_op_name.len));
135 }
136 break;
137 }
138 }
139 if (count > std.math.maxInt(u32)) return error.WorkOverflow;
140 const index = rewrite.PatternIndex.Capacity.derive(.{
141 .patterns = &.{},
142 .facts = .{ .pattern_count = @intCast(count) },
143 }) catch return error.WorkOverflow;
144 const patterns = try work.arrayListGrowth(rewrite.RewritePattern, count);
145 const dialect_storage = try work.arrayListGrowth(RegisteredDialect, dialect_count);
146 const fold_bytes = try work.multiply(initial.fold_name_count, @sizeOf([]const u8));
147 const fold_names = try work.add(fold_bytes, @alignOf([]const u8));
148 const alignment = @alignOf(rewrite.RewritePattern) + @alignOf(RegisteredDialect);
149 const population_bytes = try work.add(patterns, dialect_storage);
150 const sealed_bytes = try work.add(index.working_bytes, alignment);
151 const storage = try work.add(population_bytes, try work.add(fold_names, sealed_bytes));
152 const population = try work.add(count, context.dialect_registry.operation_registry.ops.count());
153 const units = try work.add(try work.add(names, population), interface_count);
154 return .{
155 .patterns = count,
156 .name_bytes = names,
157 .visits = try work.multiply(16, try work.multiply(
158 try work.add(units, 1),
159 try work.add(count, 1),
160 )),
161 .bytes = storage,
162 };
163 }
164
165 const CanonicalizationPatternCatalog = struct {
166 ctx: *ir.Context,
167 arith_patterns: []const rewrite.RewritePattern,
168 arith_patterns_are_static: bool,
169 arith_fold_cache: [ArithOperationIndex.operation_count]ArithFoldCacheEntry,
170 include_builtin_patterns: bool,
171 include_registered_fold_patterns: bool,
172 include_registered_canonicalization_patterns: bool,
173
174 fn init(
175 ctx: *ir.Context,
176 include_builtin_patterns: bool,
177 include_registered_fold_patterns: bool,
178 include_registered_canonicalization_patterns: bool,
179 ) CanonicalizationPatternCatalog {
180 const arith_patterns = if (include_registered_canonicalization_patterns)
181 registeredDialectPatterns(ctx, arith.name)
182 else
183 &.{};
184 return .{
185 .ctx = ctx,
186 .arith_patterns = arith_patterns,
187 .arith_patterns_are_static = arith_patterns.len == dialects.arith.canonicalization_patterns.len and
188 arith_patterns.ptr == dialects.arith.canonicalization_patterns[0..].ptr,
189 .arith_fold_cache = @splat(.{}),
190 .include_builtin_patterns = include_builtin_patterns,
191 .include_registered_fold_patterns = include_registered_fold_patterns,
192 .include_registered_canonicalization_patterns = include_registered_canonicalization_patterns,
193 };
194 }
195
196 fn hasPatterns(self: *const CanonicalizationPatternCatalog) bool {
197 if (self.include_builtin_patterns and builtin_canonicalization_patterns.len > 0) {
198 return true;
199 }
200 if (self.include_registered_fold_patterns) {
201 var op_iter = self.ctx.dialect_registry.operation_registry.ops.iterator();
202 while (op_iter.next()) |entry| {
203 if (entry.value_ptr.*.hasInterface(ir.interfaces.FoldOpInterface.id)) {
204 return true;
205 }
206 }
207 }
208 if (self.include_registered_canonicalization_patterns) {
209 const Interface = rewrite.DialectCanonicalizationInterface;
210 var dialect_iter = self.ctx.dialect_registry.interfaces.iterator();
211 while (dialect_iter.next()) |entry| {
212 for (entry.value_ptr.items) |iface_entry| {
213 if (iface_entry.id != Interface.id) continue;
214 if (Interface.fromOpaque(iface_entry.vtable).patterns.len > 0) {
215 return true;
216 }
217 break;
218 }
219 }
220 }
221 return false;
222 }
223
224 pub fn applyFirstMatchingPattern(
225 self: *CanonicalizationPatternCatalog,
226 op: *ir.Operation,
227 rewriter: *rewrite.PatternRewriter,
228 ) bool {
229 if (std.mem.eql(u8, op.name.name, scf.IfOp.operation_name)) {
230 return self.include_builtin_patterns and rewriteScfIf(op, rewriter) == .success;
231 }
232 if (!effects.permitsRepeatableExpression(op)) return false;
233 if (arith_operation_index.get(op.name.name)) |route_index| {
234 return self.applyArithPatterns(route_index, op, rewriter);
235 }
236
237 if (self.include_registered_fold_patterns) {
238 if (op.getRegisteredInfo()) |op_info| {
239 if (op_info.getInterface(ir.interfaces.FoldOpInterface.id)) |vtable_opaque| {
240 const vtable: *const ir.interfaces.FoldOpInterface.VTable = @ptrCast(@alignCast(vtable_opaque));
241 var attempt = rewrite.PatternRewriteAttempt.init(op, rewriter);
242 if (attempt.finish(rewriteFoldInterfaceWithVTable(op, rewriter, vtable))) {
243 return true;
244 }
245 }
246 }
247 }
248
249 if (self.include_registered_canonicalization_patterns) {
250 const dialect_name = op.name.getDialectNamespace();
251 const patterns = if (std.mem.eql(u8, dialect_name, arith.name))
252 self.arith_patterns
253 else
254 registeredDialectPatterns(self.ctx, dialect_name);
255 for (patterns) |*pattern| {
256 if (!std.mem.eql(u8, pattern.spec.root_op_name, op.name.name)) continue;
257 if (rewrite.tryApplyRewritePattern(pattern, op, rewriter)) {
258 return true;
259 }
260 }
261 }
262
263 if (self.include_builtin_patterns) {
264 if (builtin_canonicalization_pattern_map.get(op.name.name)) |index| {
265 if (rewrite.tryApplyRewritePattern(
266 &builtin_canonicalization_patterns[index],
267 op,
268 rewriter,
269 )) {
270 return true;
271 }
272 }
273 }
274
275 return false;
276 }
277
278 fn applyArithPatterns(
279 self: *CanonicalizationPatternCatalog,
280 route_index: usize,
281 op: *ir.Operation,
282 rewriter: *rewrite.PatternRewriter,
283 ) bool {
284 const route = arith_operation_index.routes[route_index];
285 if (self.include_registered_fold_patterns) {
286 if (op.getRegisteredInfo()) |op_info| {
287 const cache = &self.arith_fold_cache[route_index];
288 if (cache.info != op_info) {
289 cache.* = .{
290 .info = op_info,
291 .vtable = foldVTable(op_info),
292 };
293 }
294 if (cache.vtable) |vtable| {
295 var attempt = rewrite.PatternRewriteAttempt.init(op, rewriter);
296 if (attempt.finish(rewriteFoldInterfaceWithVTable(op, rewriter, vtable))) {
297 return true;
298 }
299 }
300 }
301 }
302
303 if (self.include_registered_canonicalization_patterns and
304 (!self.arith_patterns_are_static or route.has_dialect_pattern))
305 {
306 for (self.arith_patterns) |*pattern| {
307 if (!std.mem.eql(u8, pattern.spec.root_op_name, op.name.name)) continue;
308 if (rewrite.tryApplyRewritePattern(pattern, op, rewriter)) {
309 return true;
310 }
311 }
312 }
313
314 if (self.include_builtin_patterns) {
315 if (route.builtin_pattern_index) |index| {
316 if (rewrite.tryApplyRewritePattern(
317 &builtin_canonicalization_patterns[index],
318 op,
319 rewriter,
320 )) {
321 return true;
322 }
323 }
324 }
325
326 return false;
327 }
328 };
329
330 const ArithFoldCacheEntry = struct {
331 info: ?*const ir.interfaces.OperationInfo = null,
332 vtable: ?*const ir.interfaces.FoldOpInterface.VTable = null,
333 };
334
335 fn foldVTable(op_info: *const ir.interfaces.OperationInfo) ?*const ir.interfaces.FoldOpInterface.VTable {
336 const vtable_opaque = op_info.getInterface(ir.interfaces.FoldOpInterface.id) orelse return null;
337 return @ptrCast(@alignCast(vtable_opaque));
338 }
339
340 fn registeredDialectPatterns(
341 ctx: *ir.Context,
342 dialect_name: []const u8,
343 ) []const rewrite.RewritePattern {
344 if (dialect_name.len == 0) return &.{};
345 const Interface = rewrite.DialectCanonicalizationInterface;
346 const vtable_opaque = ctx.getDialectInterface(dialect_name, Interface.id) orelse return &.{};
347 return Interface.fromOpaque(vtable_opaque).patterns;
348 }
349
350 pub const CanonicalizationPassSpec = struct {
351 name: []const u8 = canonicalization_pass_name,
352 description: []const u8 = canonicalization_pass_description,
353 populate_patterns: ?PopulatePatternsFn = null,
354 greedy_config: conversion.GreedyRewriteConfig = .{},
355 cleanup_dead_ops: bool = true,
356 include_builtin_patterns: bool = true,
357 include_registered_fold_patterns: bool = true,
358 include_registered_canonicalization_patterns: bool = true,
359 mutation_scope: pass.PassMutationScope = .isolated,
360 };
361
362 const CanonicalizationPatterns = struct {
363 patterns: *rewrite.RewritePatternSet,
364 include_scf: bool,
365
366 pub fn applyFirstMatchingPattern(
367 self: *CanonicalizationPatterns,
368 op: *ir.Operation,
369 rewriter: *rewrite.PatternRewriter,
370 ) bool {
371 if (std.mem.eql(u8, op.name.name, scf.IfOp.operation_name)) {
372 return self.include_scf and rewriteScfIf(op, rewriter) == .success;
373 }
374 if (!effects.permitsRepeatableExpression(op)) return false;
375 for (self.patterns.getMatchingPatterns(op)) |*pattern| {
376 if (rewrite.tryApplyRewritePattern(pattern, op, rewriter)) return true;
377 }
378 return false;
379 }
380 };
381
382 pub fn CanonicalizationPass(comptime spec: CanonicalizationPassSpec) type {
383 return struct {
384 pub fn init() pass.Pass {
385 return .{
386 .name = spec.name,
387 .description = spec.description,
388 .run_fn = run,
389 .mutation_scope = spec.mutation_scope,
390 };
391 }
392
393 fn run(ctx: *pass.PassContext) pass.PassResult {
394 var changed = false;
395
396 if (spec.populate_patterns) |populate| {
397 var patterns = rewrite.RewritePatternSet.init(ctx.allocator);
398 defer patterns.deinit();
399
400 _ = populateInitialCanonicalizationPatterns(
401 ctx.ir_ctx,
402 &patterns,
403 spec.include_builtin_patterns,
404 spec.include_registered_fold_patterns,
405 ) catch return .failure;
406 if (spec.include_registered_canonicalization_patterns) {
407 populateRegisteredCanonicalizationPatterns(ctx.ir_ctx, &patterns) catch return .failure;
408 }
409 populate(&patterns) catch return .failure;
410 patterns.seal() catch return .failure;
411
412 if (patterns.count() > 0) {
413 var source = CanonicalizationPatterns{
414 .patterns = &patterns,
415 .include_scf = spec.include_builtin_patterns,
416 };
417 const result = conversion.applyPatternsGreedilyFromSource(
418 ctx.allocator,
419 ctx.ir_ctx,
420 ctx.op,
421 &source,
422 spec.greedy_config,
423 );
424 if (observeGreedyResult(ctx, result) == .failure) return .failure;
425 changed = changed or result.changed;
426 }
427 } else {
428 var catalog = CanonicalizationPatternCatalog.init(
429 ctx.ir_ctx,
430 spec.include_builtin_patterns,
431 spec.include_registered_fold_patterns,
432 spec.include_registered_canonicalization_patterns,
433 );
434 if (catalog.hasPatterns()) {
435 const result = conversion.applyPatternsGreedilyFromSource(
436 ctx.allocator,
437 ctx.ir_ctx,
438 ctx.op,
439 &catalog,
440 spec.greedy_config,
441 );
442 if (observeGreedyResult(ctx, result) == .failure) return .failure;
443 changed = changed or result.changed;
444 }
445 }
446
447 if (spec.cleanup_dead_ops) {
448 changed = eliminateDeadOps(ctx) or changed;
449 }
450
451 if (changed) {
452 ctx.markModified();
453 } else {
454 ctx.preserveAllAnalyses();
455 }
456
457 return .success;
458 }
459 };
460 }
461
462 fn observeGreedyResult(ctx: *pass.PassContext, result: conversion.GreedyRewriteResult) pass.PassResult {
463 if (result.changed) ctx.markModified();
464 if (ctx.analysis_cache.accounting) |ledger| {
465 if (result.termination == .iteration_limit or result.termination == .rewrite_limit) {
466 ledger.fail(.exhausted);
467 }
468 ledger.observeCounters(.{
469 .successful_rewrites = result.rewrites,
470 .rewrite_iterations = result.iterations,
471 }) catch return .failure;
472 }
473 return if (result.termination == .converged) .success else .failure;
474 }
475
476 pub fn createCanonicalizationPass() pass.Pass {
477 return CanonicalizationPass(.{}).init();
478 }
479
480 pub const builtin_canonicalization_patterns = [_]rewrite.RewritePattern{
481 rewrite.RewritePattern.init(.{ .name = "choir-scf-if-fold", .root_op_name = scf.IfOp.operation_name, .benefit = 10, .products = .none }, rewriteScfIf),
482 rewrite.RewritePattern.init(.{ .name = "choir-arith-add-fold", .root_op_name = arith.AddOp.operation_name, .benefit = 10, .products = .none }, rewriteArithAdd),
483 rewrite.RewritePattern.init(.{ .name = "choir-arith-sub-fold", .root_op_name = arith.SubOp.operation_name, .benefit = 10, .products = .{ .operations = &.{arith.ConstantOp.operation_name} } }, rewriteArithSub),
484 rewrite.RewritePattern.init(.{ .name = "choir-arith-mul-fold", .root_op_name = arith.MulOp.operation_name, .benefit = 10, .products = .none }, rewriteArithMul),
485 rewrite.RewritePattern.init(.{ .name = "choir-arith-div-fold", .root_op_name = arith.DivOp.operation_name, .benefit = 10, .products = .none }, rewriteArithDiv),
486 rewrite.RewritePattern.init(.{ .name = "choir-arith-and-fold", .root_op_name = arith.AndOp.operation_name, .benefit = 10, .products = .none }, rewriteArithAnd),
487 rewrite.RewritePattern.init(.{ .name = "choir-arith-or-fold", .root_op_name = arith.OrOp.operation_name, .benefit = 10, .products = .none }, rewriteArithOr),
488 rewrite.RewritePattern.init(.{ .name = "choir-arith-xor-fold", .root_op_name = arith.XorOp.operation_name, .benefit = 10, .products = .{ .operations = &.{arith.ConstantOp.operation_name} } }, rewriteArithXor),
489 rewrite.RewritePattern.init(.{ .name = "choir-arith-not-fold", .root_op_name = arith.NotOp.operation_name, .benefit = 10, .products = .{ .operations = &.{arith.ConstantOp.operation_name} } }, rewriteArithNot),
490 rewrite.RewritePattern.init(.{ .name = "choir-arith-shl-fold", .root_op_name = arith.ShlOp.operation_name, .benefit = 10, .products = .none }, rewriteArithShift),
491 rewrite.RewritePattern.init(.{ .name = "choir-arith-shr-fold", .root_op_name = arith.ShrOp.operation_name, .benefit = 10, .products = .none }, rewriteArithShift),
492 rewrite.RewritePattern.init(.{ .name = "choir-arith-ushr-fold", .root_op_name = arith.UshrOp.operation_name, .benefit = 10, .products = .none }, rewriteArithShift),
493 rewrite.RewritePattern.init(.{ .name = "choir-arith-cmp-fold", .root_op_name = arith.CmpOp.operation_name, .benefit = 10, .products = .{ .operations = &.{arith.ConstantOp.operation_name} } }, rewriteArithCmp),
494 rewrite.RewritePattern.init(.{ .name = "choir-arith-cast-fold", .root_op_name = arith.CastOp.operation_name, .benefit = 10, .products = .none }, rewriteArithCast),
495 rewrite.RewritePattern.init(.{ .name = "choir-arith-bitcast-fold", .root_op_name = arith.BitcastOp.operation_name, .benefit = 10, .products = .none }, rewriteArithBitcast),
496 rewrite.RewritePattern.init(.{ .name = "choir-arith-select-fold", .root_op_name = arith.SelectOp.operation_name, .benefit = 10, .products = .{ .operations = &.{arith.NotOp.operation_name} } }, rewriteArithSelect),
497 };
498
499 const BuiltinPatternIndex = struct {
500 const pattern_count = builtin_canonicalization_patterns.len;
501 const slot_count = pattern_count * 2;
502 const Slot = std.math.IntFittingRange(0, pattern_count);
503 const empty_slot: Slot = @intCast(pattern_count);
504
505 slots: [slot_count]Slot,
506
507 fn initComptime() BuiltinPatternIndex {
508 var index = BuiltinPatternIndex{ .slots = @splat(empty_slot) };
509 for (builtin_canonicalization_patterns, 0..) |pattern, pattern_index| {
510 if (pattern.spec.benefit != rewrite.builtin_pattern_benefit) {
511 @compileError("builtin canonicalization patterns must share the builtin benefit tier");
512 }
513 var slot = slotIndex(pattern.spec.root_op_name);
514 while (index.slots[slot] != empty_slot) {
515 const existing_index: usize = index.slots[slot];
516 if (std.mem.eql(
517 u8,
518 builtin_canonicalization_patterns[existing_index].spec.root_op_name,
519 pattern.spec.root_op_name,
520 )) {
521 @compileError("builtin canonicalization patterns require unique roots");
522 }
523 slot = (slot + 1) % slot_count;
524 }
525 index.slots[slot] = @intCast(pattern_index);
526 }
527 return index;
528 }
529
530 fn get(self: *const BuiltinPatternIndex, root_name: []const u8) ?usize {
531 var slot = slotIndex(root_name);
532 var probe_count: usize = 0;
533 while (probe_count < slot_count) : (probe_count += 1) {
534 const pattern_index = self.slots[slot];
535 if (pattern_index == empty_slot) return null;
536 const index: usize = pattern_index;
537 if (std.mem.eql(
538 u8,
539 builtin_canonicalization_patterns[index].spec.root_op_name,
540 root_name,
541 )) {
542 return index;
543 }
544 slot = (slot + 1) % slot_count;
545 }
546 return null;
547 }
548
549 fn slotIndex(root_name: []const u8) usize {
550 const hash = std.hash_map.hashString(root_name);
551 const reduced = @as(u128, hash) * @as(u128, slot_count);
552 return @intCast(reduced >> 64);
553 }
554 };
555
556 const builtin_canonicalization_pattern_map = BuiltinPatternIndex.initComptime();
557
558 const ArithOperationIndex = struct {
559 const operation_count = dialects.arith.spec.operations.len;
560 const slot_count = operation_count * 2;
561 const Slot = std.math.IntFittingRange(0, operation_count);
562 const empty_slot: Slot = @intCast(operation_count);
563
564 const Route = struct {
565 has_dialect_pattern: bool,
566 builtin_pattern_index: ?usize,
567 };
568
569 slots: [slot_count]Slot,
570 routes: [operation_count]Route,
571
572 fn initComptime() ArithOperationIndex {
573 @setEvalBranchQuota(10_000);
574 var index = ArithOperationIndex{
575 .slots = @splat(empty_slot),
576 .routes = undefined,
577 };
578 for (dialects.arith.spec.operations, 0..) |op_spec, operation_index| {
579 var has_dialect_pattern = false;
580 for (dialects.arith.canonicalization_patterns) |pattern| {
581 if (std.mem.eql(u8, pattern.spec.root_op_name, op_spec.name)) {
582 has_dialect_pattern = true;
583 }
584 }
585 var builtin_pattern_index: ?usize = null;
586 for (builtin_canonicalization_patterns, 0..) |pattern, pattern_index| {
587 if (std.mem.eql(u8, pattern.spec.root_op_name, op_spec.name)) {
588 builtin_pattern_index = pattern_index;
589 break;
590 }
591 }
592 index.routes[operation_index] = .{
593 .has_dialect_pattern = has_dialect_pattern,
594 .builtin_pattern_index = builtin_pattern_index,
595 };
596
597 var slot = slotIndex(op_spec.name);
598 while (index.slots[slot] != empty_slot) {
599 const existing_index: usize = index.slots[slot];
600 if (std.mem.eql(
601 u8,
602 dialects.arith.spec.operations[existing_index].name,
603 op_spec.name,
604 )) {
605 @compileError("arith operation routes require unique roots");
606 }
607 slot = (slot + 1) % slot_count;
608 }
609 index.slots[slot] = @intCast(operation_index);
610 }
611 return index;
612 }
613
614 fn get(self: *const ArithOperationIndex, root_name: []const u8) ?usize {
615 var slot = slotIndex(root_name);
616 var probe_count: usize = 0;
617 while (probe_count < slot_count) : (probe_count += 1) {
618 const operation_index = self.slots[slot];
619 if (operation_index == empty_slot) return null;
620 const index: usize = operation_index;
621 if (std.mem.eql(
622 u8,
623 dialects.arith.spec.operations[index].name,
624 root_name,
625 )) {
626 return index;
627 }
628 slot = (slot + 1) % slot_count;
629 }
630 return null;
631 }
632
633 fn slotIndex(root_name: []const u8) usize {
634 const hash = std.hash_map.hashString(root_name);
635 const reduced = @as(u128, hash) * @as(u128, slot_count);
636 return @intCast(reduced >> 64);
637 }
638 };
639
640 const arith_operation_index = ArithOperationIndex.initComptime();
641
642 pub fn populateBuiltinCanonicalizationPatterns(patterns: *rewrite.RewritePatternSet) !void {
643 try patterns.ensureUnusedCapacity(builtin_canonicalization_patterns.len);
644 try populateBuiltinCanonicalizationPatternsReserved(patterns);
645 }
646
647 fn populateBuiltinCanonicalizationPatternsReserved(patterns: *rewrite.RewritePatternSet) !void {
648 for (builtin_canonicalization_patterns) |pattern| {
649 try patterns.add(pattern);
650 }
651 }
652
653 pub fn registeredFoldPatternSpec(op_name: []const u8) rewrite.RewritePatternSpec {
654 return .{
655 .name = "choir-fold-interface",
656 .root_op_name = op_name,
657 .benefit = rewrite.fold_pattern_benefit,
658 .kind = .fold,
659 .products = .{ .operations = &.{arith.ConstantOp.operation_name} },
660 };
661 }
662
663 pub fn populateRegisteredFoldPatterns(ctx: *ir.Context, patterns: *rewrite.RewritePatternSet) !void {
664 const limits = try InitialPatternLimits.inspect(ctx);
665 const capacity = try InitialPatternCapacity.derive(limits, false, true);
666 try patterns.ensureUnusedCapacity(capacity.pattern_count);
667 try populateRegisteredFoldPatternsReserved(ctx, patterns, capacity.fold_name_count);
668 }
669
670 fn populateRegisteredFoldPatternsReserved(
671 ctx: *ir.Context,
672 patterns: *rewrite.RewritePatternSet,
673 expected_count: usize,
674 ) !void {
675 var op_names: std.ArrayListUnmanaged([]const u8) = .empty;
676 defer op_names.deinit(patterns.allocator);
677 try op_names.ensureTotalCapacityPrecise(patterns.allocator, expected_count);
678
679 var iter = ctx.dialect_registry.operation_registry.ops.iterator();
680 while (iter.next()) |entry| {
681 const op_info = entry.value_ptr.*;
682 if (op_info.hasInterface(ir.interfaces.FoldOpInterface.id)) {
683 if (op_names.items.len == expected_count) {
684 return error.OperationRegistryChanged;
685 }
686 op_names.appendAssumeCapacity(entry.key_ptr.*);
687 }
688 }
689 if (op_names.items.len != expected_count) return error.OperationRegistryChanged;
690
691 std.mem.sort([]const u8, op_names.items, {}, byte_slice_less_than);
692
693 for (op_names.items) |op_name| {
694 try patterns.add(rewrite.RewritePattern.init(registeredFoldPatternSpec(op_name), rewriteFoldInterface));
695 }
696 }
697
698 fn populateInitialCanonicalizationPatterns(
699 ctx: *ir.Context,
700 patterns: *rewrite.RewritePatternSet,
701 include_builtin_patterns: bool,
702 include_registered_fold_patterns: bool,
703 ) !InitialPatternCapacity {
704 const limits = if (include_registered_fold_patterns)
705 try InitialPatternLimits.inspect(ctx)
706 else
707 InitialPatternLimits.empty;
708 const capacity = try InitialPatternCapacity.derive(
709 limits,
710 include_builtin_patterns,
711 include_registered_fold_patterns,
712 );
713 try patterns.ensureUnusedCapacity(capacity.pattern_count);
714 if (include_builtin_patterns) {
715 try populateBuiltinCanonicalizationPatternsReserved(patterns);
716 }
717 if (include_registered_fold_patterns) {
718 try populateRegisteredFoldPatternsReserved(ctx, patterns, capacity.fold_name_count);
719 }
720 return capacity;
721 }
722
723 pub fn populateRegisteredCanonicalizationPatterns(ctx: *ir.Context, patterns: *rewrite.RewritePatternSet) !void {
724 const Interface = rewrite.DialectCanonicalizationInterface;
725 var registered: std.ArrayListUnmanaged(RegisteredDialect) = .empty;
726 defer registered.deinit(patterns.allocator);
727
728 var iter = ctx.dialect_registry.interfaces.iterator();
729 while (iter.next()) |entry| {
730 for (entry.value_ptr.items) |iface_entry| {
731 if (iface_entry.id == Interface.id) {
732 try registered.append(patterns.allocator, .{
733 .name = entry.key_ptr.*,
734 .vtable = Interface.fromOpaque(iface_entry.vtable),
735 });
736 break;
737 }
738 }
739 }
740
741 std.mem.sort(RegisteredDialect, registered.items, {}, registered_dialect_less_than);
742
743 for (registered.items) |entry| {
744 try patterns.ensureUnusedCapacity(entry.vtable.patterns.len);
745 for (entry.vtable.patterns) |pattern| {
746 try patterns.add(pattern);
747 }
748 }
749 }
750
751 pub const canonicalization_pass_registration = registry.PassRegistration{
752 .name = canonicalization_pass_name,
753 .description = canonicalization_pass_description,
754 .pass = createCanonicalizationPass(),
755 };
756
757 pub fn eliminateDeadOps(ctx: *pass.PassContext) bool {
758 var modified = false;
759 while (eliminateDeadOpsInOperation(ctx.op)) {
760 modified = true;
761 }
762 return modified;
763 }
764
765 fn eliminateDeadOpsInOperation(op: *ir.Operation) bool {
766 var changed = false;
767 var region_index = op.regions.items.len;
768 while (region_index > 0) {
769 region_index -= 1;
770 const region = &op.regions.items[region_index];
771 var block = region.blocks.tail;
772 while (block) |current_block| {
773 const previous_block = current_block.prev;
774 var current: ?*ir.Operation = @ptrCast(@alignCast(current_block.operations.tail));
775 while (current) |current_op| {
776 const previous = current_op.prev_op;
777 if (current_op.regions.items.len > 0) {
778 changed = eliminateDeadOpsInOperation(current_op) or changed;
779 }
780 if (isTriviallyDead(current_op)) {
781 current_op.erase();
782 changed = true;
783 }
784 current = previous;
785 }
786 block = previous_block;
787 }
788 }
789 return changed;
790 }
791
792 pub fn isTriviallyDead(op: *ir.Operation) bool {
793 if (op.regions.items.len > 0) return false;
794 if (op.getNumResults() == 0) return false;
795 if (!op.hasNoUses()) return false;
796
797 const traits = op.getTraits();
798 if (traits.is_terminator) return false;
799 if (op.hasInterface(ir.interfaces.SymbolOpInterface)) return false;
800 return effects.permitsDiscard(op);
801 }
802
803 fn rewriteScfIf(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
804 const if_op = scf.IfOp{ .op = op };
805 const condition = constantBoolFromValue(if_op.getCondition()) orelse return .failure;
806 if (op.getNumResults() == 0) {
807 return rewriteEffectlessConstantIf(if_op, condition, rewriter);
808 }
809 return rewriteYieldOnlyConstantIf(if_op, condition, rewriter);
810 }
811
812 fn rewriteFoldInterface(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
813 const vtable = op.getInterface(ir.interfaces.FoldOpInterface) orelse return .failure;
814 return rewriteFoldInterfaceWithVTable(op, rewriter, vtable);
815 }
816
817 fn rewriteFoldInterfaceWithVTable(
818 op: *ir.Operation,
819 rewriter: *rewrite.PatternRewriter,
820 vtable: *const ir.interfaces.FoldOpInterface.VTable,
821 ) rewrite.PatternResult {
822 if (!effects.permitsRepeatableExpression(op)) return .failure;
823 const result_count = op.getNumResults();
824 var inline_results: [1]ir.interfaces.FoldResult = undefined;
825 const result_storage = if (result_count <= inline_results.len)
826 inline_results[0..result_count]
827 else
828 rewriter.allocator.alloc(ir.interfaces.FoldResult, result_count) catch return .failure;
829 defer if (result_count > inline_results.len) rewriter.allocator.free(result_storage);
830
831 var folded = ir.interfaces.FoldResults.init(result_storage);
832 const op_opaque: *const anyopaque = @ptrCast(op);
833 vtable.fold(op_opaque, &folded) catch return .failure;
834 const folded_results = folded.slice();
835
836 if (folded_results.len == 0) return .failure;
837 if (folded_results.len != result_count) return .failure;
838
839 var inline_values: [1]*ir.Value = undefined;
840 const values = if (result_count <= inline_values.len)
841 inline_values[0..result_count]
842 else
843 rewriter.allocator.alloc(*ir.Value, result_count) catch return .failure;
844 defer if (result_count > inline_values.len) rewriter.allocator.free(values);
845
846 for (folded_results, 0..) |result, index| {
847 const op_result = op.getResult(index) orelse return .failure;
848 const value = switch (result) {
849 .value => |value| value,
850 .attribute => |attr| materializeFoldAttribute(op, op_result.type, attr, rewriter) orelse return .failure,
851 };
852 if (!op_result.type.eql(value.type)) return .failure;
853 if (valueDefinedWithinOp(value, op)) return .failure;
854 values[index] = value;
855 }
856
857 rewriter.replaceOp(op, values) catch return .failure;
858 return .success;
859 }
860
861 fn materializeFoldAttribute(
862 op: *ir.Operation,
863 ty: ir.Type,
864 attr: ir.Attribute,
865 rewriter: *rewrite.PatternRewriter,
866 ) ?*ir.Value {
867 if (!canMaterializeArithAttribute(ty, attr)) return null;
868
869 rewriter.setInsertionPointBefore(op);
870 var state = ir.Operation.State.init(arith.ConstantOp.operation_name, op.location);
871 state.addTypes(&.{ty});
872 const uses_properties = state.setPropertiesAttrIfRegistered(rewriter.ir_ctx, attr) catch return null;
873 const const_op = rewriter.create(state) catch return null;
874 if (!uses_properties) const_op.setAttr("value", attr) catch return null;
875 return const_op.getResult(0);
876 }
877
878 fn canMaterializeArithAttribute(ty: ir.Type, attr: ir.Attribute) bool {
879 if (isBoolType(ty)) return arith.getBoolValue(attr) != null;
880 if (isIntegerLikeType(ty)) return arith.getIntValue(attr) != null;
881 if (isFloatLikeType(ty)) return arith.getFloatValue(attr) != null;
882 return false;
883 }
884
885 fn rewriteArithSelect(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
886 if (!effects.permitsRepeatableExpression(op)) return .failure;
887 const select = arith.SelectOp{ .op = op };
888 const condition_value = select.getCondition();
889 const true_value = select.getTrueValue();
890 const false_value = select.getFalseValue();
891 if (true_value == false_value) {
892 rewriter.replaceOpWithValue(op, true_value) catch return .failure;
893 return .success;
894 }
895 if (true_value == condition_value) {
896 if (constantBoolEquals(false_value, false)) return rewriteSameTypeForwarding(op, condition_value, rewriter);
897 if (constantBoolEquals(false_value, true)) return rewriteSameTypeForwarding(op, false_value, rewriter);
898 }
899 if (false_value == condition_value) {
900 if (constantBoolEquals(true_value, true)) return rewriteSameTypeForwarding(op, condition_value, rewriter);
901 if (constantBoolEquals(true_value, false)) return rewriteSameTypeForwarding(op, true_value, rewriter);
902 }
903 if (constantBoolEquals(true_value, true) and constantBoolEquals(false_value, false)) {
904 return rewriteSameTypeForwarding(op, condition_value, rewriter);
905 }
906 if (constantBoolEquals(true_value, false) and constantBoolEquals(false_value, true)) {
907 return rewriteBoolNot(op, condition_value, rewriter);
908 }
909 const condition = constantBoolFromValue(condition_value) orelse return .failure;
910 rewriter.replaceOpWithValue(op, if (condition) true_value else false_value) catch return .failure;
911 return .success;
912 }
913
914 fn rewriteArithCast(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
915 if (!effects.permitsRepeatableExpression(op)) return .failure;
916 const cast = arith.CastOp{ .op = op };
917 return rewriteSameTypeUnaryForwarding(op, cast.getInput(), rewriter);
918 }
919
920 fn rewriteArithBitcast(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
921 if (!effects.permitsRepeatableExpression(op)) return .failure;
922 const cast = arith.BitcastOp{ .op = op };
923 return rewriteSameTypeUnaryForwarding(op, cast.getInput(), rewriter);
924 }
925
926 fn rewriteArithAdd(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
927 if (!effects.permitsRepeatableExpression(op)) return .failure;
928 const operands = binaryOperands(op) orelse return .failure;
929 if (constantIntEquals(operands.rhs, 0)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
930 if (constantIntEquals(operands.lhs, 0)) return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
931 return .failure;
932 }
933
934 fn rewriteArithSub(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
935 if (!effects.permitsRepeatableExpression(op)) return .failure;
936 const operands = binaryOperands(op) orelse return .failure;
937 if (constantIntEquals(operands.rhs, 0)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
938 if (operands.lhs == operands.rhs) return rewriteIntConstant(op, 0, rewriter);
939 return .failure;
940 }
941
942 fn rewriteArithMul(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
943 if (!effects.permitsRepeatableExpression(op)) return .failure;
944 const operands = binaryOperands(op) orelse return .failure;
945 if (constantIntEquals(operands.rhs, 0)) return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
946 if (constantIntEquals(operands.lhs, 0)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
947 if (constantIntEquals(operands.rhs, 1)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
948 if (constantIntEquals(operands.lhs, 1)) return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
949 return .failure;
950 }
951
952 fn rewriteArithDiv(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
953 if (!effects.permitsRepeatableExpression(op)) return .failure;
954 const operands = binaryOperands(op) orelse return .failure;
955 if (constantIntEquals(operands.rhs, 1)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
956 return .failure;
957 }
958
959 fn rewriteArithAnd(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
960 if (!effects.permitsRepeatableExpression(op)) return .failure;
961 const operands = binaryOperands(op) orelse return .failure;
962 if (operands.lhs == operands.rhs) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
963 if (constantBoolEquals(operands.rhs, false) or constantIntEquals(operands.rhs, 0)) {
964 return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
965 }
966 if (constantBoolEquals(operands.lhs, false) or constantIntEquals(operands.lhs, 0)) {
967 return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
968 }
969 if (constantBoolEquals(operands.rhs, true) or constantIntEquals(operands.rhs, -1)) {
970 return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
971 }
972 if (constantBoolEquals(operands.lhs, true) or constantIntEquals(operands.lhs, -1)) {
973 return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
974 }
975 return .failure;
976 }
977
978 fn rewriteArithOr(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
979 if (!effects.permitsRepeatableExpression(op)) return .failure;
980 const operands = binaryOperands(op) orelse return .failure;
981 if (operands.lhs == operands.rhs) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
982 if (constantBoolEquals(operands.rhs, true) or constantIntEquals(operands.rhs, -1)) {
983 return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
984 }
985 if (constantBoolEquals(operands.lhs, true) or constantIntEquals(operands.lhs, -1)) {
986 return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
987 }
988 if (constantBoolEquals(operands.rhs, false) or constantIntEquals(operands.rhs, 0)) {
989 return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
990 }
991 if (constantBoolEquals(operands.lhs, false) or constantIntEquals(operands.lhs, 0)) {
992 return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
993 }
994 return .failure;
995 }
996
997 fn rewriteArithXor(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
998 if (!effects.permitsRepeatableExpression(op)) return .failure;
999 const operands = binaryOperands(op) orelse return .failure;
1000 if (operands.lhs == operands.rhs) return rewriteZeroLikeConstant(op, rewriter);
1001 if (constantBoolEquals(operands.rhs, false) or constantIntEquals(operands.rhs, 0)) {
1002 return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
1003 }
1004 if (constantBoolEquals(operands.lhs, false) or constantIntEquals(operands.lhs, 0)) {
1005 return rewriteSameTypeForwarding(op, operands.rhs, rewriter);
1006 }
1007 return .failure;
1008 }
1009
1010 fn rewriteArithNot(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
1011 if (!effects.permitsRepeatableExpression(op)) return .failure;
1012 const not = arith.NotOp{ .op = op };
1013 const input = not.getInput();
1014 if (constantBoolFromValue(input)) |value| {
1015 return rewriteBoolConstant(op, !value, rewriter);
1016 }
1017
1018 const def_any = input.getDefiningOp() orelse return .failure;
1019 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1020 if (!std.mem.eql(u8, def_op.name.name, arith.NotOp.operation_name)) return .failure;
1021 const inner_not = arith.NotOp{ .op = def_op };
1022 const result = rewriteSameTypeForwarding(op, inner_not.getInput(), rewriter);
1023 if (result != .success) return result;
1024 if (def_op.hasOneUse()) {
1025 rewriter.eraseOp(def_op) catch return .failure;
1026 }
1027 return .success;
1028 }
1029
1030 fn rewriteArithShift(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
1031 if (!effects.permitsRepeatableExpression(op)) return .failure;
1032 const operands = binaryOperands(op) orelse return .failure;
1033 if (constantIntEquals(operands.rhs, 0)) return rewriteSameTypeForwarding(op, operands.lhs, rewriter);
1034 return .failure;
1035 }
1036
1037 fn rewriteArithCmp(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
1038 if (!effects.permitsRepeatableExpression(op)) return .failure;
1039 const operands = binaryOperands(op) orelse return .failure;
1040 if (operands.lhs != operands.rhs) return .failure;
1041 const cmp = arith.CmpOp{ .op = op };
1042 const predicate = cmp.getPredicate() orelse return .failure;
1043 const folded = cmpSelfResult(predicate, operands.lhs.type) orelse return .failure;
1044 return rewriteBoolConstant(op, folded, rewriter);
1045 }
1046
1047 fn rewriteSameTypeUnaryForwarding(
1048 op: *ir.Operation,
1049 input: *ir.Value,
1050 rewriter: *rewrite.PatternRewriter,
1051 ) rewrite.PatternResult {
1052 return rewriteSameTypeForwarding(op, input, rewriter);
1053 }
1054
1055 fn rewriteSameTypeForwarding(
1056 op: *ir.Operation,
1057 input: *ir.Value,
1058 rewriter: *rewrite.PatternRewriter,
1059 ) rewrite.PatternResult {
1060 if (op.getNumResults() != 1) return .failure;
1061 const result = op.getResult(0) orelse return .failure;
1062 if (!result.type.eql(input.type)) return .failure;
1063 rewriter.replaceOpWithValue(op, input) catch return .failure;
1064 return .success;
1065 }
1066
1067 fn rewriteBoolConstant(
1068 op: *ir.Operation,
1069 value: bool,
1070 rewriter: *rewrite.PatternRewriter,
1071 ) rewrite.PatternResult {
1072 if (op.getNumResults() != 1) return .failure;
1073 const result = op.getResult(0) orelse return .failure;
1074 if (!isBoolType(result.type)) return .failure;
1075
1076 rewriter.setInsertionPointBefore(op);
1077 var state = ir.Operation.State.init(arith.ConstantOp.operation_name, op.location);
1078 state.addTypes(&.{result.type});
1079 const attr = arith.getBoolAttr(rewriter.ir_ctx, value) catch return .failure;
1080 const uses_properties = state.setPropertiesAttrIfRegistered(rewriter.ir_ctx, attr) catch return .failure;
1081 if (!uses_properties) state.addAttributes(&.{.{ .name = "value", .value = attr }});
1082 _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;
1083 return .success;
1084 }
1085
1086 fn rewriteIntConstant(
1087 op: *ir.Operation,
1088 value: i64,
1089 rewriter: *rewrite.PatternRewriter,
1090 ) rewrite.PatternResult {
1091 if (op.getNumResults() != 1) return .failure;
1092 const result = op.getResult(0) orelse return .failure;
1093 if (!isIntegerLikeType(result.type)) return .failure;
1094
1095 rewriter.setInsertionPointBefore(op);
1096 var state = ir.Operation.State.init(arith.ConstantOp.operation_name, op.location);
1097 state.addTypes(&.{result.type});
1098 const attr = arith.getIntAttr(rewriter.ir_ctx, value) catch return .failure;
1099 const uses_properties = state.setPropertiesAttrIfRegistered(rewriter.ir_ctx, attr) catch return .failure;
1100 if (!uses_properties) state.addAttributes(&.{.{ .name = "value", .value = attr }});
1101 _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;
1102 return .success;
1103 }
1104
1105 fn rewriteZeroLikeConstant(
1106 op: *ir.Operation,
1107 rewriter: *rewrite.PatternRewriter,
1108 ) rewrite.PatternResult {
1109 if (op.getNumResults() != 1) return .failure;
1110 const result = op.getResult(0) orelse return .failure;
1111 if (isBoolType(result.type)) return rewriteBoolConstant(op, false, rewriter);
1112 return rewriteIntConstant(op, 0, rewriter);
1113 }
1114
1115 fn rewriteBoolNot(
1116 op: *ir.Operation,
1117 input: *ir.Value,
1118 rewriter: *rewrite.PatternRewriter,
1119 ) rewrite.PatternResult {
1120 if (op.getNumResults() != 1) return .failure;
1121 const result = op.getResult(0) orelse return .failure;
1122 if (!result.type.eql(input.type) or !isBoolType(result.type)) return .failure;
1123
1124 rewriter.setInsertionPointBefore(op);
1125 var state = ir.Operation.State.init(arith.NotOp.operation_name, op.location);
1126 state.addOperands(&.{input});
1127 state.addTypes(&.{result.type});
1128 _ = rewriter.replaceOpWithNewOp(op, state) catch return .failure;
1129 return .success;
1130 }
1131
1132 fn cmpSelfResult(predicate_value: CmpPredicate, ty: ir.Type) ?bool {
1133 if (isBoolType(ty)) {
1134 return switch (predicate_value) {
1135 .eq => true,
1136 .ne => false,
1137 else => null,
1138 };
1139 }
1140 if (!isIntegerLikeType(ty)) return null;
1141 return switch (predicate_value) {
1142 .eq, .le, .ge, .sle, .sge, .ule, .uge => true,
1143 .ne, .lt, .gt, .slt, .sgt, .ult, .ugt => false,
1144 };
1145 }
1146
1147 fn rewriteEffectlessConstantIf(
1148 if_op: scf.IfOp,
1149 condition: bool,
1150 rewriter: *rewrite.PatternRewriter,
1151 ) rewrite.PatternResult {
1152 const selected = selectedIfBlock(if_op, condition) orelse {
1153 rewriter.eraseOp(if_op.op) catch return .failure;
1154 return .success;
1155 };
1156 if (!blockIsEmptyOrZeroYield(selected)) return .failure;
1157 rewriter.eraseOp(if_op.op) catch return .failure;
1158 return .success;
1159 }
1160
1161 fn rewriteYieldOnlyConstantIf(
1162 if_op: scf.IfOp,
1163 condition: bool,
1164 rewriter: *rewrite.PatternRewriter,
1165 ) rewrite.PatternResult {
1166 const selected = selectedIfBlock(if_op, condition) orelse return .failure;
1167 const yield = singleYieldOp(selected) orelse return .failure;
1168 if (yield.operands.items.len != if_op.op.getNumResults()) return .failure;
1169
1170 const values = rewriter.allocator.alloc(*ir.Value, yield.operands.items.len) catch return .failure;
1171 defer rewriter.allocator.free(values);
1172
1173 for (yield.operands.items, 0..) |operand, index| {
1174 const value = operand.value;
1175 if (valueDefinedWithinOp(value, if_op.op)) return .failure;
1176 values[index] = value;
1177 }
1178
1179 rewriter.replaceOp(if_op.op, values) catch return .failure;
1180 return .success;
1181 }
1182
1183 fn selectedIfBlock(if_op: scf.IfOp, condition: bool) ?*ir.Block {
1184 if (condition) return if_op.getThenBlock();
1185 return if_op.getElseBlock();
1186 }
1187
1188 fn blockIsEmptyOrZeroYield(block: *ir.Block) bool {
1189 const first = block.operations.head orelse return true;
1190 const op: *ir.Operation = @ptrCast(@alignCast(first));
1191 if (op.next_op != null) return false;
1192 if (!std.mem.eql(u8, op.name.name, scf.YieldOp.operation_name)) return false;
1193 return op.operands.items.len == 0;
1194 }
1195
1196 fn singleYieldOp(block: *ir.Block) ?*ir.Operation {
1197 const first = block.operations.head orelse return null;
1198 const op: *ir.Operation = @ptrCast(@alignCast(first));
1199 if (op.next_op != null) return null;
1200 if (!std.mem.eql(u8, op.name.name, scf.YieldOp.operation_name)) return null;
1201 return op;
1202 }
1203
1204 fn constantBoolFromValue(value: *ir.Value) ?bool {
1205 const def_any = value.getDefiningOp() orelse return null;
1206 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1207 if (!std.mem.eql(u8, def_op.name.name, arith.ConstantOp.operation_name)) return null;
1208 if (def_op.getAttrAs(ir.Attribute.BoolAttr, "value")) |bool_attr| return bool_attr.getValue();
1209 if (def_op.getAttrAs(ir.Attribute.IntegerAttr, "value")) |int_attr| {
1210 const int_value = int_attr.getValue();
1211 if (!isBoolType(value.type)) return null;
1212 return int_value != 0;
1213 }
1214 return null;
1215 }
1216
1217 fn constantIntFromValue(value: *ir.Value) ?i64 {
1218 if (!isIntegerLikeType(value.type)) return null;
1219 const def_any = value.getDefiningOp() orelse return null;
1220 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1221 if (!std.mem.eql(u8, def_op.name.name, arith.ConstantOp.operation_name)) return null;
1222 const int_attr = def_op.getAttrAs(ir.Attribute.IntegerAttr, "value") orelse return null;
1223 return int_attr.getValue();
1224 }
1225
1226 fn constantIntEquals(value: *ir.Value, expected: i64) bool {
1227 return (constantIntFromValue(value) orelse return false) == expected;
1228 }
1229
1230 fn constantBoolEquals(value: *ir.Value, expected: bool) bool {
1231 return (constantBoolFromValue(value) orelse return false) == expected;
1232 }
1233
1234 fn isBoolType(ty: ir.Type) bool {
1235 return dialects.arith.scalarKindFromType(ty) == .bool;
1236 }
1237
1238 fn isIntegerLikeType(ty: ir.Type) bool {
1239 const kind = dialects.arith.scalarKindFromType(ty) orelse return false;
1240 return dialects.arith.scalarKindIsSignedInteger(kind);
1241 }
1242
1243 fn isFloatLikeType(ty: ir.Type) bool {
1244 const kind = dialects.arith.scalarKindFromType(ty) orelse return false;
1245 return switch (kind) {
1246 .f16, .f32, .f64 => true,
1247 else => false,
1248 };
1249 }
1250
1251 const BinaryOperands = struct {
1252 lhs: *ir.Value,
1253 rhs: *ir.Value,
1254 };
1255
1256 fn binaryOperands(op: *ir.Operation) ?BinaryOperands {
1257 if (op.operands.items.len != 2) return null;
1258 return .{
1259 .lhs = op.operands.items[0].value,
1260 .rhs = op.operands.items[1].value,
1261 };
1262 }
1263
1264 fn valueDefinedWithinOp(value: *ir.Value, ancestor: *ir.Operation) bool {
1265 if (value.getDefiningOp()) |def_any| {
1266 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1267 return ancestor.isAncestor(def_op);
1268 }
1269 if (value.getOwnerBlock()) |block_any| {
1270 const block: *ir.Block = @ptrCast(@alignCast(block_any));
1271 const parent_op = block.getParentOperation() orelse return false;
1272 return ancestor.isAncestor(parent_op);
1273 }
1274 return false;
1275 }
1276
1277 fn populateIdentityPattern(patterns: *rewrite.RewritePatternSet) anyerror!void {
1278 try patterns.add(rewrite.RewritePattern.init(.{
1279 .name = "test-identity",
1280 .root_op_name = "test.identity",
1281 .benefit = 1,
1282 .products = .none,
1283 }, rewriteIdentity));
1284 }
1285
1286 fn rewriteIdentity(op: *ir.Operation, rewriter: *rewrite.PatternRewriter) rewrite.PatternResult {
1287 const input = op.getOperand(0) orelse return .failure;
1288 rewriter.replaceOpWithValue(op, input) catch return .failure;
1289 return .success;
1290 }
1291
1292 fn foldIdentityOp(
1293 op_ptr: *const anyopaque,
1294 results: *ir.interfaces.FoldResults,
1295 ) anyerror!void {
1296 const op: *const ir.Operation = @ptrCast(@alignCast(op_ptr));
1297 if (op.operands.items.len != 1) return;
1298 try results.append(.{ .value = op.operands.items[0].value });
1299 }
1300
1301 fn foldFalseAttribute(
1302 op_ptr: *const anyopaque,
1303 results: *ir.interfaces.FoldResults,
1304 ) anyerror!void {
1305 const op: *const ir.Operation = @ptrCast(@alignCast(op_ptr));
1306 const attr = try arith.getBoolAttr(op.getContext(), false);
1307 try results.append(.{ .attribute = attr });
1308 }
1309
1310 fn foldPairOp(
1311 op_ptr: *const anyopaque,
1312 results: *ir.interfaces.FoldResults,
1313 ) anyerror!void {
1314 const op: *const ir.Operation = @ptrCast(@alignCast(op_ptr));
1315 if (op.operands.items.len != 2) return;
1316 try results.append(.{ .value = op.operands.items[0].value });
1317 try results.append(.{ .value = op.operands.items[1].value });
1318 }
1319
1320 test "builtin canonicalization patterns materialize from inspectable specs" {
1321 const testing = std.testing;
1322 const allocator = testing.allocator;
1323
1324 var patterns = rewrite.RewritePatternSet.init(allocator);
1325 defer patterns.deinit();
1326
1327 try populateBuiltinCanonicalizationPatterns(&patterns);
1328
1329 try testing.expectEqual(builtin_canonicalization_patterns.len, patterns.patterns.items.len);
1330 for (builtin_canonicalization_patterns, patterns.patterns.items, 0..) |entry, pattern, index| {
1331 try testing.expectEqualStrings(entry.spec.name, pattern.spec.name);
1332 try testing.expectEqualStrings(entry.spec.root_op_name, pattern.spec.root_op_name);
1333 try testing.expectEqual(entry.spec.benefit, pattern.spec.benefit);
1334 try testing.expectEqual(entry.spec.kind, pattern.spec.kind);
1335 try testing.expectEqual(index, builtin_canonicalization_pattern_map.get(entry.spec.root_op_name).?);
1336 }
1337 switch (builtin_canonicalization_patterns[2].spec.products) {
1338 .operations => |ops| try testing.expectEqualStrings(arith.ConstantOp.operation_name, ops[0]),
1339 else => return error.TestExpectedBuiltinProducts,
1340 }
1341 }
1342
1343 test "CanonicalizationPass borrows its default catalog without allocating" {
1344 const testing = std.testing;
1345 const test_dialect = @import("../dialects/fixture/root.zig");
1346 const allocator = testing.allocator;
1347
1348 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1349 defer ctx.deinit(allocator);
1350 try ir.dialects.loadDialectSpec(&ctx, dialects.arith.spec);
1351
1352 const module = try test_dialect.TestDialect.ModuleOp.create(
1353 &ctx,
1354 ir.Location.getUnknown(),
1355 );
1356
1357 var failing = testing.FailingAllocator.init(allocator, .{ .fail_index = 0 });
1358 var analysis_cache = pass.AnalysisCache.init(failing.allocator(), null);
1359 defer analysis_cache.deinit();
1360 var pass_ctx = pass.PassContext.init(
1361 module.op,
1362 &ctx,
1363 failing.allocator(),
1364 &analysis_cache,
1365 );
1366 defer pass_ctx.deinit();
1367
1368 try testing.expectEqual(
1369 pass.PassResult.success,
1370 createCanonicalizationPass().run(&pass_ctx),
1371 );
1372 try testing.expectEqual(@as(usize, 0), failing.alloc_index);
1373 }
1374
1375 test "populateRegisteredFoldPatterns orders fold hooks by operation name" {
1376 const testing = std.testing;
1377 const allocator = testing.allocator;
1378
1379 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1380 defer ctx.deinit(allocator);
1381
1382 _ = try ctx.registerOperation("test.z_fold", .{});
1383 try ctx.registerOperationInterface(
1384 "test.z_fold",
1385 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1386 );
1387 _ = try ctx.registerOperation("test.a_fold", .{});
1388 try ctx.registerOperationInterface(
1389 "test.a_fold",
1390 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1391 );
1392
1393 var patterns = rewrite.RewritePatternSet.init(allocator);
1394 defer patterns.deinit();
1395
1396 try populateRegisteredFoldPatterns(&ctx, &patterns);
1397
1398 try testing.expectEqual(@as(usize, 2), patterns.patterns.items.len);
1399 try testing.expectEqualStrings("choir-fold-interface", patterns.patterns.items[0].spec.name);
1400 try testing.expectEqual(.fold, patterns.patterns.items[0].spec.kind);
1401 try testing.expectEqualStrings("test.a_fold", patterns.patterns.items[0].spec.root_op_name);
1402 try testing.expectEqualStrings("test.z_fold", patterns.patterns.items[1].spec.root_op_name);
1403 switch (patterns.patterns.items[0].spec.products) {
1404 .operations => |ops| try testing.expectEqualStrings(arith.ConstantOp.operation_name, ops[0]),
1405 else => return error.TestExpectedFoldProducts,
1406 }
1407 }
1408
1409 test "initial canonicalization pattern capacity follows registered folds" {
1410 const testing = std.testing;
1411 const allocator = testing.allocator;
1412
1413 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1414 defer ctx.deinit(allocator);
1415
1416 _ = try ctx.registerOperation("test.z_fold", .{});
1417 try ctx.registerOperationInterface(
1418 "test.z_fold",
1419 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1420 );
1421 _ = try ctx.registerOperation("test.a_fold", .{});
1422 try ctx.registerOperationInterface(
1423 "test.a_fold",
1424 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1425 );
1426
1427 const limits = try InitialPatternLimits.inspect(&ctx);
1428 try testing.expectEqual(@as(usize, 2), limits.facts.registered_fold_count);
1429
1430 const full = try InitialPatternCapacity.derive(limits, true, true);
1431 try testing.expectEqual(
1432 builtin_canonicalization_patterns.len + 2,
1433 full.pattern_count,
1434 );
1435 try testing.expectEqual(@as(usize, 2), full.fold_name_count);
1436
1437 const builtin_only = try InitialPatternCapacity.derive(limits, true, false);
1438 try testing.expectEqual(
1439 builtin_canonicalization_patterns.len,
1440 builtin_only.pattern_count,
1441 );
1442 try testing.expectEqual(@as(usize, 0), builtin_only.fold_name_count);
1443
1444 const maximum_fold_count = std.math.maxInt(usize) -
1445 builtin_canonicalization_patterns.len;
1446 const maximum = try InitialPatternCapacity.derive(.{
1447 .facts = .{ .registered_fold_count = maximum_fold_count },
1448 }, true, true);
1449 try testing.expectEqual(std.math.maxInt(usize), maximum.pattern_count);
1450 try testing.expectError(
1451 error.CapacityOverflow,
1452 InitialPatternCapacity.derive(.{
1453 .facts = .{ .registered_fold_count = maximum_fold_count + 1 },
1454 }, true, true),
1455 );
1456
1457 var stale_patterns = rewrite.RewritePatternSet.init(allocator);
1458 defer stale_patterns.deinit();
1459 try stale_patterns.ensureUnusedCapacity(1);
1460 try testing.expectError(
1461 error.OperationRegistryChanged,
1462 populateRegisteredFoldPatternsReserved(&ctx, &stale_patterns, 1),
1463 );
1464 try testing.expectEqual(@as(usize, 0), stale_patterns.patterns.items.len);
1465 }
1466
1467 test "initial canonicalization patterns reuse one builder backing" {
1468 const testing = std.testing;
1469 const allocator = testing.allocator;
1470
1471 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1472 defer ctx.deinit(allocator);
1473
1474 _ = try ctx.registerOperation("test.z_fold", .{});
1475 try ctx.registerOperationInterface(
1476 "test.z_fold",
1477 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1478 );
1479 _ = try ctx.registerOperation("test.a_fold", .{});
1480 try ctx.registerOperationInterface(
1481 "test.a_fold",
1482 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1483 );
1484
1485 var patterns = rewrite.RewritePatternSet.init(allocator);
1486 defer patterns.deinit();
1487
1488 const limits = try InitialPatternLimits.inspect(&ctx);
1489 const capacity = try InitialPatternCapacity.derive(limits, true, true);
1490 try patterns.ensureUnusedCapacity(capacity.pattern_count);
1491 const base_pointer = patterns.patterns.items.ptr;
1492 try populateBuiltinCanonicalizationPatternsReserved(&patterns);
1493 try populateRegisteredFoldPatternsReserved(
1494 &ctx,
1495 &patterns,
1496 capacity.fold_name_count,
1497 );
1498
1499 try testing.expectEqual(capacity.pattern_count, patterns.patterns.items.len);
1500 try testing.expectEqual(base_pointer, patterns.patterns.items.ptr);
1501 try testing.expect(patterns.patterns.capacity >= capacity.pattern_count);
1502 }
1503
1504 fn checkInitialCanonicalizationPatternFailures(
1505 allocator: std.mem.Allocator,
1506 ctx: *ir.Context,
1507 ) !void {
1508 var patterns = rewrite.RewritePatternSet.init(allocator);
1509 defer patterns.deinit();
1510
1511 const capacity = try populateInitialCanonicalizationPatterns(
1512 ctx,
1513 &patterns,
1514 true,
1515 true,
1516 );
1517 try std.testing.expectEqual(capacity.pattern_count, patterns.patterns.items.len);
1518 }
1519
1520 test "initial canonicalization pattern population is retryable after allocation failure" {
1521 const testing = std.testing;
1522 const allocator = testing.allocator;
1523
1524 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1525 defer ctx.deinit(allocator);
1526
1527 _ = try ctx.registerOperation("test.fold", .{});
1528 try ctx.registerOperationInterface(
1529 "test.fold",
1530 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1531 );
1532
1533 try testing.checkAllAllocationFailures(
1534 allocator,
1535 checkInitialCanonicalizationPatternFailures,
1536 .{&ctx},
1537 );
1538 }
1539
1540 fn appendUser(ctx: *ir.Context, block: *ir.Block, loc: ir.Location, value: *ir.Value) !*ir.Operation {
1541 var builder = ir.OperationBuilder.init(ctx);
1542 var user_state = ir.Operation.State.init("test.user", loc);
1543 user_state.addOperands(&.{value});
1544 const user = try builder.create(user_state);
1545 try block.addOperation(user);
1546 return user;
1547 }
1548
1549 test "CanonicalizationPass retains unqualified operations with registered fold interfaces" {
1550 const testing = std.testing;
1551 const test_dialect = @import("../dialects/fixture/root.zig");
1552 const allocator = testing.allocator;
1553
1554 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1555 defer ctx.deinit(allocator);
1556
1557 _ = try ctx.registerOperation("test.fold_identity", .{});
1558 try ctx.registerOperationInterface(
1559 "test.fold_identity",
1560 ir.interfaces.FoldOpInterface.entryFor(foldIdentityOp),
1561 );
1562
1563 const loc = ir.Location.getUnknown();
1564 const i32_type = try arith.getScalarType(&ctx, .i32);
1565
1566 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1567 const block = module.getBodyBlock();
1568 const value = try block.addArgument(i32_type, loc);
1569
1570 var builder = ir.OperationBuilder.init(&ctx);
1571 var fold_state = ir.Operation.State.init("test.fold_identity", loc);
1572 fold_state.addOperands(&.{value});
1573 fold_state.addTypes(&.{i32_type});
1574 const identity = try builder.create(fold_state);
1575 try block.addOperation(identity);
1576 const user = try appendUser(&ctx, block, loc, identity.getResult(0).?);
1577
1578 var manager = pass.PassManager.init(allocator);
1579 defer manager.deinit();
1580 try manager.addPass(createCanonicalizationPass());
1581
1582 try testing.expect(user.getNumOperands() > 0);
1583 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1584 defer allocator.free(before_ir);
1585 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1586 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1587 defer allocator.free(after_ir);
1588 try testing.expectEqualStrings(before_ir, after_ir);
1589 }
1590
1591 test "CanonicalizationPass retains unqualified multi-result folds" {
1592 const testing = std.testing;
1593 const test_dialect = @import("../dialects/fixture/root.zig");
1594 const allocator = testing.allocator;
1595
1596 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1597 defer ctx.deinit(allocator);
1598
1599 _ = try ctx.registerOperation("test.fold_pair", .{});
1600 try ctx.registerOperationInterface(
1601 "test.fold_pair",
1602 ir.interfaces.FoldOpInterface.entryFor(foldPairOp),
1603 );
1604
1605 const loc = ir.Location.getUnknown();
1606 const i32_type = try arith.getScalarType(&ctx, .i32);
1607 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1608 const block = module.getBodyBlock();
1609 const first = try block.addArgument(i32_type, loc);
1610 const second = try block.addArgument(i32_type, loc);
1611
1612 var builder = ir.OperationBuilder.init(&ctx);
1613 var fold_state = ir.Operation.State.init("test.fold_pair", loc);
1614 fold_state.addOperands(&.{ first, second });
1615 fold_state.addTypes(&.{ i32_type, i32_type });
1616 const pair = try builder.create(fold_state);
1617 try block.addOperation(pair);
1618 const first_user = try appendUser(&ctx, block, loc, pair.getResult(0).?);
1619 const second_user = try appendUser(&ctx, block, loc, pair.getResult(1).?);
1620
1621 var manager = pass.PassManager.init(allocator);
1622 defer manager.deinit();
1623 try manager.addPass(CanonicalizationPass(.{ .include_builtin_patterns = false }).init());
1624
1625 try testing.expect(first_user.getNumOperands() > 0);
1626 try testing.expect(second_user.getNumOperands() > 0);
1627 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1628 defer allocator.free(before_ir);
1629 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1630 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1631 defer allocator.free(after_ir);
1632 try testing.expectEqualStrings(before_ir, after_ir);
1633 }
1634
1635 test "CanonicalizationPass retains unqualified attribute folds" {
1636 const testing = std.testing;
1637 const test_dialect = @import("../dialects/fixture/root.zig");
1638 const allocator = testing.allocator;
1639
1640 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1641 defer ctx.deinit(allocator);
1642
1643 _ = try ctx.registerOperation("test.fold_false", .{});
1644 try ctx.registerOperationInterface(
1645 "test.fold_false",
1646 ir.interfaces.FoldOpInterface.entryFor(foldFalseAttribute),
1647 );
1648
1649 const loc = ir.Location.getUnknown();
1650 const bool_type = try arith.getScalarType(&ctx, .bool);
1651
1652 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1653 const block = module.getBodyBlock();
1654
1655 var builder = ir.OperationBuilder.init(&ctx);
1656 var fold_state = ir.Operation.State.init("test.fold_false", loc);
1657 fold_state.addTypes(&.{bool_type});
1658 const folded = try builder.create(fold_state);
1659 try block.addOperation(folded);
1660 const user = try appendUser(&ctx, block, loc, folded.getResult(0).?);
1661
1662 var manager = pass.PassManager.init(allocator);
1663 defer manager.deinit();
1664 try manager.addPass(CanonicalizationPass(.{ .include_builtin_patterns = false }).init());
1665
1666 try testing.expect(user.getNumOperands() > 0);
1667 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
1668 defer allocator.free(before_ir);
1669 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1670 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
1671 defer allocator.free(after_ir);
1672 try testing.expectEqualStrings(before_ir, after_ir);
1673 }
1674
1675 test "Precision1 CanonicalizationPass applies arith fold hooks without builtin patterns" {
1676 const testing = std.testing;
1677 const test_dialect = @import("../dialects/fixture/root.zig");
1678 const allocator = testing.allocator;
1679
1680 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1681 defer ctx.deinit(allocator);
1682 try ir.dialects.loadDialectSpec(&ctx, dialects.arith.spec);
1683
1684 const loc = ir.Location.getUnknown();
1685 const bool_type = try arith.getScalarType(&ctx, .bool);
1686 const i32_type = try arith.getScalarType(&ctx, .i32);
1687
1688 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1689 const block = module.getBodyBlock();
1690 const condition = try block.addArgument(bool_type, loc);
1691 const value = try block.addArgument(i32_type, loc);
1692
1693 const zero = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 0);
1694 try block.addOperation(zero.op);
1695 const one = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 1);
1696 try block.addOperation(one.op);
1697 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
1698 try block.addOperation(true_value.op);
1699
1700 const add = try arith.AddOp.create(&ctx, loc, value, zero.getResult());
1701 try block.addOperation(add.op);
1702 const add_user = try appendUser(&ctx, block, loc, add.getResult());
1703
1704 const sub_same = try arith.SubOp.create(&ctx, loc, value, value);
1705 try block.addOperation(sub_same.op);
1706 const sub_same_user = try appendUser(&ctx, block, loc, sub_same.getResult());
1707
1708 const mul = try arith.MulOp.create(&ctx, loc, one.getResult(), value);
1709 try block.addOperation(mul.op);
1710 const mul_user = try appendUser(&ctx, block, loc, mul.getResult());
1711
1712 const cmp_same = try arith.CmpOp.create(&ctx, loc, .eq, value, value);
1713 try block.addOperation(cmp_same.op);
1714 const cmp_same_user = try appendUser(&ctx, block, loc, cmp_same.getResult());
1715
1716 const shl = try arith.ShlOp.create(&ctx, loc, value, zero.getResult());
1717 try block.addOperation(shl.op);
1718 const shl_user = try appendUser(&ctx, block, loc, shl.getResult());
1719
1720 const and_op = try arith.AndOp.create(&ctx, loc, condition, true_value.getResult());
1721 try block.addOperation(and_op.op);
1722 const and_user = try appendUser(&ctx, block, loc, and_op.getResult());
1723
1724 const xor_same = try arith.XorOp.create(&ctx, loc, condition, condition);
1725 try block.addOperation(xor_same.op);
1726 const xor_same_user = try appendUser(&ctx, block, loc, xor_same.getResult());
1727
1728 const not_true = try arith.NotOp.create(&ctx, loc, true_value.getResult());
1729 try block.addOperation(not_true.op);
1730 const not_true_user = try appendUser(&ctx, block, loc, not_true.getResult());
1731
1732 const cast = try arith.CastOp.create(&ctx, loc, value, i32_type);
1733 try block.addOperation(cast.op);
1734 const cast_user = try appendUser(&ctx, block, loc, cast.getResult());
1735
1736 const select = try arith.SelectOp.create(&ctx, loc, condition, value, value);
1737 try block.addOperation(select.op);
1738 const select_user = try appendUser(&ctx, block, loc, select.getResult());
1739
1740 var manager = pass.PassManager.init(allocator);
1741 defer manager.deinit();
1742 try manager.addPass(CanonicalizationPass(.{ .include_builtin_patterns = false }).init());
1743
1744 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1745 try testing.expectEqual(
1746 @as(usize, 0),
1747 ir.inspection.countOperationsNamed(module.op, arith.AddOp.operation_name),
1748 );
1749 try testing.expectEqual(
1750 @as(usize, 0),
1751 ir.inspection.countOperationsNamed(module.op, arith.SubOp.operation_name),
1752 );
1753 try testing.expectEqual(
1754 @as(usize, 0),
1755 ir.inspection.countOperationsNamed(module.op, arith.MulOp.operation_name),
1756 );
1757 try testing.expectEqual(
1758 @as(usize, 0),
1759 ir.inspection.countOperationsNamed(module.op, arith.CmpOp.operation_name),
1760 );
1761 try testing.expectEqual(
1762 @as(usize, 0),
1763 ir.inspection.countOperationsNamed(module.op, arith.ShlOp.operation_name),
1764 );
1765 try testing.expectEqual(
1766 @as(usize, 0),
1767 ir.inspection.countOperationsNamed(module.op, arith.AndOp.operation_name),
1768 );
1769 try testing.expectEqual(
1770 @as(usize, 0),
1771 ir.inspection.countOperationsNamed(module.op, arith.XorOp.operation_name),
1772 );
1773 try testing.expectEqual(
1774 @as(usize, 0),
1775 ir.inspection.countOperationsNamed(module.op, arith.NotOp.operation_name),
1776 );
1777 try testing.expectEqual(
1778 @as(usize, 0),
1779 ir.inspection.countOperationsNamed(module.op, arith.CastOp.operation_name),
1780 );
1781 try testing.expectEqual(
1782 @as(usize, 0),
1783 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
1784 );
1785 try testing.expect(add_user.getOperand(0).? == value);
1786 try testing.expectEqual(@as(i64, 0), constantIntFromValue(sub_same_user.getOperand(0).?).?);
1787 try testing.expect(mul_user.getOperand(0).? == value);
1788 try testing.expectEqual(true, constantBoolFromValue(cmp_same_user.getOperand(0).?).?);
1789 try testing.expect(shl_user.getOperand(0).? == value);
1790 try testing.expect(and_user.getOperand(0).? == condition);
1791 try testing.expectEqual(false, constantBoolFromValue(xor_same_user.getOperand(0).?).?);
1792 try testing.expectEqual(false, constantBoolFromValue(not_true_user.getOperand(0).?).?);
1793 try testing.expect(cast_user.getOperand(0).? == value);
1794 try testing.expect(select_user.getOperand(0).? == value);
1795 }
1796
1797 test "Precision1 CanonicalizationPass applies arith canonicalization hooks without builtin or fold patterns" {
1798 const testing = std.testing;
1799 const test_dialect = @import("../dialects/fixture/root.zig");
1800 const allocator = testing.allocator;
1801
1802 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1803 defer ctx.deinit(allocator);
1804 try ir.dialects.loadDialectSpec(&ctx, dialects.arith.spec);
1805
1806 const loc = ir.Location.getUnknown();
1807 const bool_type = try arith.getScalarType(&ctx, .bool);
1808
1809 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1810 const block = module.getBodyBlock();
1811 const condition = try block.addArgument(bool_type, loc);
1812
1813 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
1814 try block.addOperation(false_value.op);
1815 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
1816 try block.addOperation(true_value.op);
1817
1818 const select = try arith.SelectOp.create(&ctx, loc, condition, false_value.getResult(), true_value.getResult());
1819 try block.addOperation(select.op);
1820 const select_user = try appendUser(&ctx, block, loc, select.getResult());
1821
1822 const inner_not = try arith.NotOp.create(&ctx, loc, condition);
1823 try block.addOperation(inner_not.op);
1824 const outer_not = try arith.NotOp.create(&ctx, loc, inner_not.getResult());
1825 try block.addOperation(outer_not.op);
1826 const outer_user = try appendUser(&ctx, block, loc, outer_not.getResult());
1827
1828 var manager = pass.PassManager.init(allocator);
1829 defer manager.deinit();
1830 try manager.addPass(CanonicalizationPass(.{
1831 .include_builtin_patterns = false,
1832 .include_registered_fold_patterns = false,
1833 }).init());
1834
1835 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1836 try testing.expectEqual(
1837 @as(usize, 0),
1838 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
1839 );
1840 try testing.expectEqual(
1841 @as(usize, 1),
1842 ir.inspection.countOperationsNamed(module.op, arith.NotOp.operation_name),
1843 );
1844 try testing.expect(outer_user.getOperand(0).? == condition);
1845
1846 const replacement = select_user.getOperand(0).?;
1847 const def_any = replacement.getDefiningOp().?;
1848 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
1849 try testing.expectEqualStrings(arith.NotOp.operation_name, def_op.name.name);
1850 const not = arith.NotOp{ .op = def_op };
1851 try testing.expect(not.getInput() == condition);
1852 }
1853
1854 test "CanonicalizationPass folds constant scf.if yielding external values" {
1855 const testing = std.testing;
1856 const test_dialect = @import("../dialects/fixture/root.zig");
1857 const allocator = testing.allocator;
1858
1859 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1860 defer ctx.deinit(allocator);
1861
1862 const loc = ir.Location.getUnknown();
1863 const i32_type = try arith.getScalarType(&ctx, .i32);
1864
1865 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1866 const block = module.getBodyBlock();
1867
1868 const condition = try arith.ConstantOp.createBool(&ctx, loc, true);
1869 try block.addOperation(condition.op);
1870 const then_value = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 11);
1871 try block.addOperation(then_value.op);
1872 const else_value = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 22);
1873 try block.addOperation(else_value.op);
1874
1875 const if_op = try scf.IfOp.create(&ctx, loc, condition.getResult(), &.{i32_type});
1876 try block.addOperation(if_op.op);
1877 const then_yield = try scf.YieldOp.create(&ctx, loc, &.{then_value.getResult()});
1878 try if_op.getThenBlock().addOperation(then_yield.op);
1879 const else_yield = try scf.YieldOp.create(&ctx, loc, &.{else_value.getResult()});
1880 try if_op.getElseBlock().?.addOperation(else_yield.op);
1881
1882 var builder = ir.OperationBuilder.init(&ctx);
1883 var user_state = ir.Operation.State.init("test.user", loc);
1884 user_state.addOperands(&.{if_op.getResult(0).?});
1885 const user = try builder.create(user_state);
1886 try block.addOperation(user);
1887
1888 var manager = pass.PassManager.init(allocator);
1889 defer manager.deinit();
1890 try manager.addPass(createCanonicalizationPass());
1891
1892 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1893 try testing.expectEqual(@as(usize, 0), ir.inspection.countOperationsNamed(module.op, scf.IfOp.operation_name));
1894 try testing.expect(user.getOperand(0).? == then_value.getResult());
1895 }
1896
1897 test "Precision1 CanonicalizationPass folds arith.select with constant condition" {
1898 const testing = std.testing;
1899 const test_dialect = @import("../dialects/fixture/root.zig");
1900 const allocator = testing.allocator;
1901
1902 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1903 defer ctx.deinit(allocator);
1904
1905 const loc = ir.Location.getUnknown();
1906 const i32_type = try arith.getScalarType(&ctx, .i32);
1907
1908 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1909 const block = module.getBodyBlock();
1910 const true_value = try block.addArgument(i32_type, loc);
1911 const false_value = try block.addArgument(i32_type, loc);
1912
1913 const condition = try arith.ConstantOp.createBool(&ctx, loc, true);
1914 try block.addOperation(condition.op);
1915 const select = try arith.SelectOp.create(&ctx, loc, condition.getResult(), true_value, false_value);
1916 try block.addOperation(select.op);
1917
1918 var builder = ir.OperationBuilder.init(&ctx);
1919 var user_state = ir.Operation.State.init("test.user", loc);
1920 user_state.addOperands(&.{select.getResult()});
1921 const user = try builder.create(user_state);
1922 try block.addOperation(user);
1923
1924 var manager = pass.PassManager.init(allocator);
1925 defer manager.deinit();
1926 try manager.addPass(createCanonicalizationPass());
1927
1928 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1929 try testing.expectEqual(
1930 @as(usize, 0),
1931 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
1932 );
1933 try testing.expect(user.getOperand(0).? == true_value);
1934 }
1935
1936 test "Precision1 CanonicalizationPass folds arith.select with identical values" {
1937 const testing = std.testing;
1938 const test_dialect = @import("../dialects/fixture/root.zig");
1939 const allocator = testing.allocator;
1940
1941 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1942 defer ctx.deinit(allocator);
1943
1944 const loc = ir.Location.getUnknown();
1945 const bool_type = try arith.getScalarType(&ctx, .bool);
1946 const i32_type = try arith.getScalarType(&ctx, .i32);
1947
1948 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1949 const block = module.getBodyBlock();
1950 const condition = try block.addArgument(bool_type, loc);
1951 const value = try block.addArgument(i32_type, loc);
1952
1953 const select = try arith.SelectOp.create(&ctx, loc, condition, value, value);
1954 try block.addOperation(select.op);
1955
1956 var builder = ir.OperationBuilder.init(&ctx);
1957 var user_state = ir.Operation.State.init("test.user", loc);
1958 user_state.addOperands(&.{select.getResult()});
1959 const user = try builder.create(user_state);
1960 try block.addOperation(user);
1961
1962 var manager = pass.PassManager.init(allocator);
1963 defer manager.deinit();
1964 try manager.addPass(createCanonicalizationPass());
1965
1966 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
1967 try testing.expectEqual(
1968 @as(usize, 0),
1969 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
1970 );
1971 try testing.expect(user.getOperand(0).? == value);
1972 }
1973
1974 test "Precision1 CanonicalizationPass forwards boolean arith.select identity" {
1975 const testing = std.testing;
1976 const test_dialect = @import("../dialects/fixture/root.zig");
1977 const allocator = testing.allocator;
1978
1979 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
1980 defer ctx.deinit(allocator);
1981
1982 const loc = ir.Location.getUnknown();
1983 const bool_type = try arith.getScalarType(&ctx, .bool);
1984
1985 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
1986 const block = module.getBodyBlock();
1987 const condition = try block.addArgument(bool_type, loc);
1988
1989 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
1990 try block.addOperation(true_value.op);
1991 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
1992 try block.addOperation(false_value.op);
1993
1994 const select = try arith.SelectOp.create(&ctx, loc, condition, true_value.getResult(), false_value.getResult());
1995 try block.addOperation(select.op);
1996 const user = try appendUser(&ctx, block, loc, select.getResult());
1997
1998 var manager = pass.PassManager.init(allocator);
1999 defer manager.deinit();
2000 try manager.addPass(createCanonicalizationPass());
2001
2002 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2003 try testing.expectEqual(
2004 @as(usize, 0),
2005 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
2006 );
2007 try testing.expect(user.getOperand(0).? == condition);
2008 }
2009
2010 test "Precision1 CanonicalizationPass rewrites boolean arith.select inverse" {
2011 const testing = std.testing;
2012 const test_dialect = @import("../dialects/fixture/root.zig");
2013 const allocator = testing.allocator;
2014
2015 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2016 defer ctx.deinit(allocator);
2017
2018 const loc = ir.Location.getUnknown();
2019 const bool_type = try arith.getScalarType(&ctx, .bool);
2020
2021 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2022 const block = module.getBodyBlock();
2023 const condition = try block.addArgument(bool_type, loc);
2024
2025 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
2026 try block.addOperation(false_value.op);
2027 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
2028 try block.addOperation(true_value.op);
2029
2030 const select = try arith.SelectOp.create(&ctx, loc, condition, false_value.getResult(), true_value.getResult());
2031 try block.addOperation(select.op);
2032 const user = try appendUser(&ctx, block, loc, select.getResult());
2033
2034 var manager = pass.PassManager.init(allocator);
2035 defer manager.deinit();
2036 try manager.addPass(createCanonicalizationPass());
2037
2038 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2039 try testing.expectEqual(
2040 @as(usize, 0),
2041 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
2042 );
2043 try testing.expectEqual(
2044 @as(usize, 1),
2045 ir.inspection.countOperationsNamed(module.op, arith.NotOp.operation_name),
2046 );
2047
2048 const replacement = user.getOperand(0).?;
2049 const def_any = replacement.getDefiningOp().?;
2050 const def_op: *ir.Operation = @ptrCast(@alignCast(def_any));
2051 try testing.expectEqualStrings(arith.NotOp.operation_name, def_op.name.name);
2052 const not = arith.NotOp{ .op = def_op };
2053 try testing.expect(not.getInput() == condition);
2054 }
2055
2056 test "Precision1 CanonicalizationPass folds boolean arith.select absorption" {
2057 const testing = std.testing;
2058 const test_dialect = @import("../dialects/fixture/root.zig");
2059 const allocator = testing.allocator;
2060
2061 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2062 defer ctx.deinit(allocator);
2063
2064 const loc = ir.Location.getUnknown();
2065 const bool_type = try arith.getScalarType(&ctx, .bool);
2066
2067 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2068 const block = module.getBodyBlock();
2069 const condition = try block.addArgument(bool_type, loc);
2070
2071 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
2072 try block.addOperation(true_value.op);
2073 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
2074 try block.addOperation(false_value.op);
2075
2076 const true_absorb = try arith.SelectOp.create(&ctx, loc, condition, condition, false_value.getResult());
2077 try block.addOperation(true_absorb.op);
2078 const true_absorb_user = try appendUser(&ctx, block, loc, true_absorb.getResult());
2079
2080 const false_absorb = try arith.SelectOp.create(&ctx, loc, condition, true_value.getResult(), condition);
2081 try block.addOperation(false_absorb.op);
2082 const false_absorb_user = try appendUser(&ctx, block, loc, false_absorb.getResult());
2083
2084 const true_constant = try arith.SelectOp.create(&ctx, loc, condition, condition, true_value.getResult());
2085 try block.addOperation(true_constant.op);
2086 const true_constant_user = try appendUser(&ctx, block, loc, true_constant.getResult());
2087
2088 const false_constant = try arith.SelectOp.create(&ctx, loc, condition, false_value.getResult(), condition);
2089 try block.addOperation(false_constant.op);
2090 const false_constant_user = try appendUser(&ctx, block, loc, false_constant.getResult());
2091
2092 var manager = pass.PassManager.init(allocator);
2093 defer manager.deinit();
2094 try manager.addPass(createCanonicalizationPass());
2095
2096 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2097 try testing.expectEqual(
2098 @as(usize, 0),
2099 ir.inspection.countOperationsNamed(module.op, arith.SelectOp.operation_name),
2100 );
2101 try testing.expect(true_absorb_user.getOperand(0).? == condition);
2102 try testing.expect(false_absorb_user.getOperand(0).? == condition);
2103 try testing.expectEqual(true, constantBoolFromValue(true_constant_user.getOperand(0).?).?);
2104 try testing.expectEqual(false, constantBoolFromValue(false_constant_user.getOperand(0).?).?);
2105 }
2106
2107 test "Precision1 CanonicalizationPass forwards same-type arith.cast" {
2108 const testing = std.testing;
2109 const test_dialect = @import("../dialects/fixture/root.zig");
2110 const allocator = testing.allocator;
2111
2112 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2113 defer ctx.deinit(allocator);
2114
2115 const loc = ir.Location.getUnknown();
2116 const i32_type = try arith.getScalarType(&ctx, .i32);
2117
2118 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2119 const block = module.getBodyBlock();
2120 const value = try block.addArgument(i32_type, loc);
2121
2122 const cast = try arith.CastOp.create(&ctx, loc, value, i32_type);
2123 try block.addOperation(cast.op);
2124
2125 var builder = ir.OperationBuilder.init(&ctx);
2126 var user_state = ir.Operation.State.init("test.user", loc);
2127 user_state.addOperands(&.{cast.getResult()});
2128 const user = try builder.create(user_state);
2129 try block.addOperation(user);
2130
2131 var manager = pass.PassManager.init(allocator);
2132 defer manager.deinit();
2133 try manager.addPass(createCanonicalizationPass());
2134
2135 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2136 try testing.expectEqual(
2137 @as(usize, 0),
2138 ir.inspection.countOperationsNamed(module.op, arith.CastOp.operation_name),
2139 );
2140 try testing.expect(user.getOperand(0).? == value);
2141 }
2142
2143 test "Precision1 CanonicalizationPass forwards same-type arith.bitcast" {
2144 const testing = std.testing;
2145 const test_dialect = @import("../dialects/fixture/root.zig");
2146 const allocator = testing.allocator;
2147
2148 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2149 defer ctx.deinit(allocator);
2150
2151 const loc = ir.Location.getUnknown();
2152 const i32_type = try arith.getScalarType(&ctx, .i32);
2153
2154 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2155 const block = module.getBodyBlock();
2156 const value = try block.addArgument(i32_type, loc);
2157
2158 const cast = try arith.BitcastOp.create(&ctx, loc, value, i32_type);
2159 try block.addOperation(cast.op);
2160
2161 var builder = ir.OperationBuilder.init(&ctx);
2162 var user_state = ir.Operation.State.init("test.user", loc);
2163 user_state.addOperands(&.{cast.getResult()});
2164 const user = try builder.create(user_state);
2165 try block.addOperation(user);
2166
2167 var manager = pass.PassManager.init(allocator);
2168 defer manager.deinit();
2169 try manager.addPass(createCanonicalizationPass());
2170
2171 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2172 try testing.expectEqual(
2173 @as(usize, 0),
2174 ir.inspection.countOperationsNamed(module.op, arith.BitcastOp.operation_name),
2175 );
2176 try testing.expect(user.getOperand(0).? == value);
2177 }
2178
2179 test "Precision1 CanonicalizationPass forwards integer arithmetic identities" {
2180 const testing = std.testing;
2181 const test_dialect = @import("../dialects/fixture/root.zig");
2182 const allocator = testing.allocator;
2183
2184 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2185 defer ctx.deinit(allocator);
2186
2187 const loc = ir.Location.getUnknown();
2188 const i32_type = try arith.getScalarType(&ctx, .i32);
2189
2190 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2191 const block = module.getBodyBlock();
2192 const value = try block.addArgument(i32_type, loc);
2193
2194 const zero = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 0);
2195 try block.addOperation(zero.op);
2196 const one = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 1);
2197 try block.addOperation(one.op);
2198 const all_ones = try arith.ConstantOp.createInt(&ctx, loc, i32_type, -1);
2199 try block.addOperation(all_ones.op);
2200
2201 const add_rhs = try arith.AddOp.create(&ctx, loc, value, zero.getResult());
2202 try block.addOperation(add_rhs.op);
2203 const add_rhs_user = try appendUser(&ctx, block, loc, add_rhs.getResult());
2204
2205 const add_lhs = try arith.AddOp.create(&ctx, loc, zero.getResult(), value);
2206 try block.addOperation(add_lhs.op);
2207 const add_lhs_user = try appendUser(&ctx, block, loc, add_lhs.getResult());
2208
2209 const sub_rhs = try arith.SubOp.create(&ctx, loc, value, zero.getResult());
2210 try block.addOperation(sub_rhs.op);
2211 const sub_rhs_user = try appendUser(&ctx, block, loc, sub_rhs.getResult());
2212
2213 const sub_same = try arith.SubOp.create(&ctx, loc, value, value);
2214 try block.addOperation(sub_same.op);
2215 const sub_same_user = try appendUser(&ctx, block, loc, sub_same.getResult());
2216
2217 const mul_rhs = try arith.MulOp.create(&ctx, loc, value, one.getResult());
2218 try block.addOperation(mul_rhs.op);
2219 const mul_rhs_user = try appendUser(&ctx, block, loc, mul_rhs.getResult());
2220
2221 const mul_lhs = try arith.MulOp.create(&ctx, loc, one.getResult(), value);
2222 try block.addOperation(mul_lhs.op);
2223 const mul_lhs_user = try appendUser(&ctx, block, loc, mul_lhs.getResult());
2224
2225 const mul_zero_rhs = try arith.MulOp.create(&ctx, loc, value, zero.getResult());
2226 try block.addOperation(mul_zero_rhs.op);
2227 const mul_zero_rhs_user = try appendUser(&ctx, block, loc, mul_zero_rhs.getResult());
2228
2229 const mul_zero_lhs = try arith.MulOp.create(&ctx, loc, zero.getResult(), value);
2230 try block.addOperation(mul_zero_lhs.op);
2231 const mul_zero_lhs_user = try appendUser(&ctx, block, loc, mul_zero_lhs.getResult());
2232
2233 const div_rhs = try arith.DivOp.create(&ctx, loc, value, one.getResult());
2234 try block.addOperation(div_rhs.op);
2235 const div_rhs_user = try appendUser(&ctx, block, loc, div_rhs.getResult());
2236
2237 const and_rhs = try arith.AndOp.create(&ctx, loc, value, all_ones.getResult());
2238 try block.addOperation(and_rhs.op);
2239 const and_rhs_user = try appendUser(&ctx, block, loc, and_rhs.getResult());
2240
2241 const and_same = try arith.AndOp.create(&ctx, loc, value, value);
2242 try block.addOperation(and_same.op);
2243 const and_same_user = try appendUser(&ctx, block, loc, and_same.getResult());
2244
2245 const and_zero = try arith.AndOp.create(&ctx, loc, value, zero.getResult());
2246 try block.addOperation(and_zero.op);
2247 const and_zero_user = try appendUser(&ctx, block, loc, and_zero.getResult());
2248
2249 const or_rhs = try arith.OrOp.create(&ctx, loc, value, zero.getResult());
2250 try block.addOperation(or_rhs.op);
2251 const or_rhs_user = try appendUser(&ctx, block, loc, or_rhs.getResult());
2252
2253 const or_same = try arith.OrOp.create(&ctx, loc, value, value);
2254 try block.addOperation(or_same.op);
2255 const or_same_user = try appendUser(&ctx, block, loc, or_same.getResult());
2256
2257 const or_all_ones = try arith.OrOp.create(&ctx, loc, all_ones.getResult(), value);
2258 try block.addOperation(or_all_ones.op);
2259 const or_all_ones_user = try appendUser(&ctx, block, loc, or_all_ones.getResult());
2260
2261 const xor_lhs = try arith.XorOp.create(&ctx, loc, zero.getResult(), value);
2262 try block.addOperation(xor_lhs.op);
2263 const xor_lhs_user = try appendUser(&ctx, block, loc, xor_lhs.getResult());
2264
2265 const xor_same = try arith.XorOp.create(&ctx, loc, value, value);
2266 try block.addOperation(xor_same.op);
2267 const xor_same_user = try appendUser(&ctx, block, loc, xor_same.getResult());
2268
2269 const shl_rhs = try arith.ShlOp.create(&ctx, loc, value, zero.getResult());
2270 try block.addOperation(shl_rhs.op);
2271 const shl_rhs_user = try appendUser(&ctx, block, loc, shl_rhs.getResult());
2272
2273 const shr_rhs = try arith.ShrOp.create(&ctx, loc, value, zero.getResult());
2274 try block.addOperation(shr_rhs.op);
2275 const shr_rhs_user = try appendUser(&ctx, block, loc, shr_rhs.getResult());
2276
2277 const ushr_rhs = try arith.UshrOp.create(&ctx, loc, value, zero.getResult());
2278 try block.addOperation(ushr_rhs.op);
2279 const ushr_rhs_user = try appendUser(&ctx, block, loc, ushr_rhs.getResult());
2280
2281 var manager = pass.PassManager.init(allocator);
2282 defer manager.deinit();
2283 try manager.addPass(createCanonicalizationPass());
2284
2285 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2286 try testing.expect(add_rhs_user.getOperand(0).? == value);
2287 try testing.expect(add_lhs_user.getOperand(0).? == value);
2288 try testing.expect(sub_rhs_user.getOperand(0).? == value);
2289 try testing.expectEqual(@as(i64, 0), constantIntFromValue(sub_same_user.getOperand(0).?).?);
2290 try testing.expect(mul_rhs_user.getOperand(0).? == value);
2291 try testing.expect(mul_lhs_user.getOperand(0).? == value);
2292 try testing.expect(mul_zero_rhs_user.getOperand(0).? == zero.getResult());
2293 try testing.expect(mul_zero_lhs_user.getOperand(0).? == zero.getResult());
2294 try testing.expect(div_rhs_user.getOperand(0).? == value);
2295 try testing.expect(and_rhs_user.getOperand(0).? == value);
2296 try testing.expect(and_same_user.getOperand(0).? == value);
2297 try testing.expect(and_zero_user.getOperand(0).? == zero.getResult());
2298 try testing.expect(or_rhs_user.getOperand(0).? == value);
2299 try testing.expect(or_same_user.getOperand(0).? == value);
2300 try testing.expect(or_all_ones_user.getOperand(0).? == all_ones.getResult());
2301 try testing.expect(xor_lhs_user.getOperand(0).? == value);
2302 try testing.expectEqual(@as(i64, 0), constantIntFromValue(xor_same_user.getOperand(0).?).?);
2303 try testing.expect(shl_rhs_user.getOperand(0).? == value);
2304 try testing.expect(shr_rhs_user.getOperand(0).? == value);
2305 try testing.expect(ushr_rhs_user.getOperand(0).? == value);
2306 try testing.expectEqual(
2307 @as(usize, 0),
2308 ir.inspection.countOperationsNamed(module.op, arith.AddOp.operation_name),
2309 );
2310 try testing.expectEqual(
2311 @as(usize, 0),
2312 ir.inspection.countOperationsNamed(module.op, arith.SubOp.operation_name),
2313 );
2314 try testing.expectEqual(
2315 @as(usize, 0),
2316 ir.inspection.countOperationsNamed(module.op, arith.MulOp.operation_name),
2317 );
2318 try testing.expectEqual(
2319 @as(usize, 0),
2320 ir.inspection.countOperationsNamed(module.op, arith.DivOp.operation_name),
2321 );
2322 try testing.expectEqual(
2323 @as(usize, 0),
2324 ir.inspection.countOperationsNamed(module.op, arith.AndOp.operation_name),
2325 );
2326 try testing.expectEqual(
2327 @as(usize, 0),
2328 ir.inspection.countOperationsNamed(module.op, arith.OrOp.operation_name),
2329 );
2330 try testing.expectEqual(
2331 @as(usize, 0),
2332 ir.inspection.countOperationsNamed(module.op, arith.XorOp.operation_name),
2333 );
2334 try testing.expectEqual(
2335 @as(usize, 0),
2336 ir.inspection.countOperationsNamed(module.op, arith.ShlOp.operation_name),
2337 );
2338 try testing.expectEqual(
2339 @as(usize, 0),
2340 ir.inspection.countOperationsNamed(module.op, arith.ShrOp.operation_name),
2341 );
2342 try testing.expectEqual(
2343 @as(usize, 0),
2344 ir.inspection.countOperationsNamed(module.op, arith.UshrOp.operation_name),
2345 );
2346 }
2347
2348 test "Precision1 CanonicalizationPass forwards boolean arithmetic identities" {
2349 const testing = std.testing;
2350 const test_dialect = @import("../dialects/fixture/root.zig");
2351 const allocator = testing.allocator;
2352
2353 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2354 defer ctx.deinit(allocator);
2355
2356 const loc = ir.Location.getUnknown();
2357 const bool_type = try arith.getScalarType(&ctx, .bool);
2358
2359 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2360 const block = module.getBodyBlock();
2361 const value = try block.addArgument(bool_type, loc);
2362
2363 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
2364 try block.addOperation(true_value.op);
2365 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
2366 try block.addOperation(false_value.op);
2367
2368 const and_rhs = try arith.AndOp.create(&ctx, loc, value, true_value.getResult());
2369 try block.addOperation(and_rhs.op);
2370 const and_rhs_user = try appendUser(&ctx, block, loc, and_rhs.getResult());
2371
2372 const and_lhs = try arith.AndOp.create(&ctx, loc, true_value.getResult(), value);
2373 try block.addOperation(and_lhs.op);
2374 const and_lhs_user = try appendUser(&ctx, block, loc, and_lhs.getResult());
2375
2376 const and_same = try arith.AndOp.create(&ctx, loc, value, value);
2377 try block.addOperation(and_same.op);
2378 const and_same_user = try appendUser(&ctx, block, loc, and_same.getResult());
2379
2380 const and_false = try arith.AndOp.create(&ctx, loc, value, false_value.getResult());
2381 try block.addOperation(and_false.op);
2382 const and_false_user = try appendUser(&ctx, block, loc, and_false.getResult());
2383
2384 const or_rhs = try arith.OrOp.create(&ctx, loc, value, false_value.getResult());
2385 try block.addOperation(or_rhs.op);
2386 const or_rhs_user = try appendUser(&ctx, block, loc, or_rhs.getResult());
2387
2388 const or_lhs = try arith.OrOp.create(&ctx, loc, false_value.getResult(), value);
2389 try block.addOperation(or_lhs.op);
2390 const or_lhs_user = try appendUser(&ctx, block, loc, or_lhs.getResult());
2391
2392 const or_same = try arith.OrOp.create(&ctx, loc, value, value);
2393 try block.addOperation(or_same.op);
2394 const or_same_user = try appendUser(&ctx, block, loc, or_same.getResult());
2395
2396 const or_true = try arith.OrOp.create(&ctx, loc, true_value.getResult(), value);
2397 try block.addOperation(or_true.op);
2398 const or_true_user = try appendUser(&ctx, block, loc, or_true.getResult());
2399
2400 const xor_rhs = try arith.XorOp.create(&ctx, loc, value, false_value.getResult());
2401 try block.addOperation(xor_rhs.op);
2402 const xor_rhs_user = try appendUser(&ctx, block, loc, xor_rhs.getResult());
2403
2404 const xor_lhs = try arith.XorOp.create(&ctx, loc, false_value.getResult(), value);
2405 try block.addOperation(xor_lhs.op);
2406 const xor_lhs_user = try appendUser(&ctx, block, loc, xor_lhs.getResult());
2407
2408 const xor_same = try arith.XorOp.create(&ctx, loc, value, value);
2409 try block.addOperation(xor_same.op);
2410 const xor_same_user = try appendUser(&ctx, block, loc, xor_same.getResult());
2411
2412 var manager = pass.PassManager.init(allocator);
2413 defer manager.deinit();
2414 try manager.addPass(createCanonicalizationPass());
2415
2416 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2417 try testing.expect(and_rhs_user.getOperand(0).? == value);
2418 try testing.expect(and_lhs_user.getOperand(0).? == value);
2419 try testing.expect(and_same_user.getOperand(0).? == value);
2420 try testing.expect(and_false_user.getOperand(0).? == false_value.getResult());
2421 try testing.expect(or_rhs_user.getOperand(0).? == value);
2422 try testing.expect(or_lhs_user.getOperand(0).? == value);
2423 try testing.expect(or_same_user.getOperand(0).? == value);
2424 try testing.expect(or_true_user.getOperand(0).? == true_value.getResult());
2425 try testing.expect(xor_rhs_user.getOperand(0).? == value);
2426 try testing.expect(xor_lhs_user.getOperand(0).? == value);
2427 try testing.expectEqual(false, constantBoolFromValue(xor_same_user.getOperand(0).?).?);
2428 try testing.expectEqual(
2429 @as(usize, 0),
2430 ir.inspection.countOperationsNamed(module.op, arith.AndOp.operation_name),
2431 );
2432 try testing.expectEqual(
2433 @as(usize, 0),
2434 ir.inspection.countOperationsNamed(module.op, arith.OrOp.operation_name),
2435 );
2436 try testing.expectEqual(
2437 @as(usize, 0),
2438 ir.inspection.countOperationsNamed(module.op, arith.XorOp.operation_name),
2439 );
2440 }
2441
2442 test "Precision1 CanonicalizationPass folds arith.not identities" {
2443 const testing = std.testing;
2444 const test_dialect = @import("../dialects/fixture/root.zig");
2445 const allocator = testing.allocator;
2446
2447 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2448 defer ctx.deinit(allocator);
2449
2450 const loc = ir.Location.getUnknown();
2451 const bool_type = try arith.getScalarType(&ctx, .bool);
2452
2453 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2454 const block = module.getBodyBlock();
2455 const value = try block.addArgument(bool_type, loc);
2456
2457 const true_value = try arith.ConstantOp.createBool(&ctx, loc, true);
2458 try block.addOperation(true_value.op);
2459 const false_value = try arith.ConstantOp.createBool(&ctx, loc, false);
2460 try block.addOperation(false_value.op);
2461
2462 const not_true = try arith.NotOp.create(&ctx, loc, true_value.getResult());
2463 try block.addOperation(not_true.op);
2464 const not_true_user = try appendUser(&ctx, block, loc, not_true.getResult());
2465
2466 const not_false = try arith.NotOp.create(&ctx, loc, false_value.getResult());
2467 try block.addOperation(not_false.op);
2468 const not_false_user = try appendUser(&ctx, block, loc, not_false.getResult());
2469
2470 const inner_not = try arith.NotOp.create(&ctx, loc, value);
2471 try block.addOperation(inner_not.op);
2472 const outer_not = try arith.NotOp.create(&ctx, loc, inner_not.getResult());
2473 try block.addOperation(outer_not.op);
2474 const outer_not_user = try appendUser(&ctx, block, loc, outer_not.getResult());
2475
2476 var manager = pass.PassManager.init(allocator);
2477 defer manager.deinit();
2478 try manager.addPass(createCanonicalizationPass());
2479
2480 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2481 try testing.expectEqual(
2482 @as(usize, 0),
2483 ir.inspection.countOperationsNamed(module.op, arith.NotOp.operation_name),
2484 );
2485 try testing.expectEqual(false, constantBoolFromValue(not_true_user.getOperand(0).?).?);
2486 try testing.expectEqual(true, constantBoolFromValue(not_false_user.getOperand(0).?).?);
2487 try testing.expect(outer_not_user.getOperand(0).? == value);
2488 }
2489
2490 test "Precision1 CanonicalizationPass folds arith.cmp self comparisons" {
2491 const testing = std.testing;
2492 const test_dialect = @import("../dialects/fixture/root.zig");
2493 const allocator = testing.allocator;
2494
2495 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2496 defer ctx.deinit(allocator);
2497
2498 const loc = ir.Location.getUnknown();
2499 const i32_type = try arith.getScalarType(&ctx, .i32);
2500 const f32_type = try arith.getScalarType(&ctx, .f32);
2501 const bool_type = try arith.getScalarType(&ctx, .bool);
2502
2503 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2504 const block = module.getBodyBlock();
2505 const int_value = try block.addArgument(i32_type, loc);
2506 const bool_value = try block.addArgument(bool_type, loc);
2507 const float_value = try block.addArgument(f32_type, loc);
2508
2509 const int_eq = try arith.CmpOp.create(&ctx, loc, .eq, int_value, int_value);
2510 try block.addOperation(int_eq.op);
2511 const int_eq_user = try appendUser(&ctx, block, loc, int_eq.getResult());
2512
2513 const int_ult = try arith.CmpOp.create(&ctx, loc, .ult, int_value, int_value);
2514 try block.addOperation(int_ult.op);
2515 const int_ult_user = try appendUser(&ctx, block, loc, int_ult.getResult());
2516
2517 const bool_eq = try arith.CmpOp.create(&ctx, loc, .eq, bool_value, bool_value);
2518 try block.addOperation(bool_eq.op);
2519 const bool_eq_user = try appendUser(&ctx, block, loc, bool_eq.getResult());
2520
2521 const bool_ne = try arith.CmpOp.create(&ctx, loc, .ne, bool_value, bool_value);
2522 try block.addOperation(bool_ne.op);
2523 const bool_ne_user = try appendUser(&ctx, block, loc, bool_ne.getResult());
2524
2525 const float_eq = try arith.CmpOp.create(&ctx, loc, .eq, float_value, float_value);
2526 try block.addOperation(float_eq.op);
2527 const float_eq_user = try appendUser(&ctx, block, loc, float_eq.getResult());
2528
2529 var manager = pass.PassManager.init(allocator);
2530 defer manager.deinit();
2531 try manager.addPass(createCanonicalizationPass());
2532
2533 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2534 try testing.expectEqual(
2535 @as(usize, 1),
2536 ir.inspection.countOperationsNamed(module.op, arith.CmpOp.operation_name),
2537 );
2538 try testing.expectEqual(
2539 @as(usize, 4),
2540 ir.inspection.countOperationsNamed(module.op, arith.ConstantOp.operation_name),
2541 );
2542 try testing.expectEqual(true, constantBoolFromValue(int_eq_user.getOperand(0).?).?);
2543 try testing.expectEqual(false, constantBoolFromValue(int_ult_user.getOperand(0).?).?);
2544 try testing.expectEqual(true, constantBoolFromValue(bool_eq_user.getOperand(0).?).?);
2545 try testing.expectEqual(false, constantBoolFromValue(bool_ne_user.getOperand(0).?).?);
2546 try testing.expect(float_eq_user.getOperand(0).? == float_eq.getResult());
2547 }
2548
2549 test "CanonicalizationPass retains unqualified empty scf.if with unknown condition" {
2550 const testing = std.testing;
2551 const test_dialect = @import("../dialects/fixture/root.zig");
2552 const allocator = testing.allocator;
2553
2554 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2555 defer ctx.deinit(allocator);
2556
2557 const loc = ir.Location.getUnknown();
2558 const bool_type = try arith.getScalarType(&ctx, .bool);
2559
2560 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2561 const block = module.getBodyBlock();
2562 const condition = try block.addArgument(bool_type, loc);
2563
2564 const if_op = try scf.IfOp.createWithoutElse(&ctx, loc, condition);
2565 try block.addOperation(if_op.op);
2566
2567 var manager = pass.PassManager.init(allocator);
2568 defer manager.deinit();
2569 try manager.addPass(createCanonicalizationPass());
2570
2571 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
2572 defer allocator.free(before_ir);
2573 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2574 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
2575 defer allocator.free(after_ir);
2576 try testing.expectEqualStrings(before_ir, after_ir);
2577 }
2578
2579 test "CanonicalizationPass retains unqualified scf.if with equivalent yields" {
2580 const testing = std.testing;
2581 const test_dialect = @import("../dialects/fixture/root.zig");
2582 const allocator = testing.allocator;
2583
2584 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2585 defer ctx.deinit(allocator);
2586
2587 const loc = ir.Location.getUnknown();
2588 const bool_type = try arith.getScalarType(&ctx, .bool);
2589 const i32_type = try arith.getScalarType(&ctx, .i32);
2590
2591 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2592 const block = module.getBodyBlock();
2593 const condition = try block.addArgument(bool_type, loc);
2594 const value = try block.addArgument(i32_type, loc);
2595
2596 const if_op = try scf.IfOp.create(&ctx, loc, condition, &.{i32_type});
2597 try block.addOperation(if_op.op);
2598 const then_yield = try scf.YieldOp.create(&ctx, loc, &.{value});
2599 try if_op.getThenBlock().addOperation(then_yield.op);
2600 const else_yield = try scf.YieldOp.create(&ctx, loc, &.{value});
2601 try if_op.getElseBlock().?.addOperation(else_yield.op);
2602
2603 const user = try appendUser(&ctx, block, loc, if_op.getResult(0).?);
2604
2605 var manager = pass.PassManager.init(allocator);
2606 defer manager.deinit();
2607 try manager.addPass(createCanonicalizationPass());
2608
2609 try testing.expect(user.getNumOperands() > 0);
2610 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
2611 defer allocator.free(before_ir);
2612 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2613 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
2614 defer allocator.free(after_ir);
2615 try testing.expectEqualStrings(before_ir, after_ir);
2616 }
2617
2618 test "CanonicalizationPass erases constant false scf.if without else" {
2619 const testing = std.testing;
2620 const test_dialect = @import("../dialects/fixture/root.zig");
2621 const allocator = testing.allocator;
2622
2623 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2624 defer ctx.deinit(allocator);
2625
2626 const loc = ir.Location.getUnknown();
2627 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2628 const block = module.getBodyBlock();
2629
2630 const condition = try arith.ConstantOp.createBool(&ctx, loc, false);
2631 try block.addOperation(condition.op);
2632 const if_op = try scf.IfOp.createWithoutElse(&ctx, loc, condition.getResult());
2633 try block.addOperation(if_op.op);
2634
2635 var manager = pass.PassManager.init(allocator);
2636 defer manager.deinit();
2637 try manager.addPass(createCanonicalizationPass());
2638
2639 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2640 try testing.expectEqual(@as(usize, 0), ir.inspection.countOperationsNamed(module.op, scf.IfOp.operation_name));
2641 }
2642
2643 test "CanonicalizationPass keeps constant scf.if yielding branch-local values" {
2644 const testing = std.testing;
2645 const test_dialect = @import("../dialects/fixture/root.zig");
2646 const allocator = testing.allocator;
2647
2648 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2649 defer ctx.deinit(allocator);
2650
2651 const loc = ir.Location.getUnknown();
2652 const i32_type = try arith.getScalarType(&ctx, .i32);
2653
2654 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2655 const block = module.getBodyBlock();
2656
2657 const condition = try arith.ConstantOp.createBool(&ctx, loc, true);
2658 try block.addOperation(condition.op);
2659 const else_value = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 22);
2660 try block.addOperation(else_value.op);
2661
2662 const if_op = try scf.IfOp.create(&ctx, loc, condition.getResult(), &.{i32_type});
2663 try block.addOperation(if_op.op);
2664 const then_value = try arith.ConstantOp.createInt(&ctx, loc, i32_type, 11);
2665 try if_op.getThenBlock().addOperation(then_value.op);
2666 const then_yield = try scf.YieldOp.create(&ctx, loc, &.{then_value.getResult()});
2667 try if_op.getThenBlock().addOperation(then_yield.op);
2668 const else_yield = try scf.YieldOp.create(&ctx, loc, &.{else_value.getResult()});
2669 try if_op.getElseBlock().?.addOperation(else_yield.op);
2670
2671 var builder = ir.OperationBuilder.init(&ctx);
2672 var user_state = ir.Operation.State.init("test.user", loc);
2673 user_state.addOperands(&.{if_op.getResult(0).?});
2674 const user = try builder.create(user_state);
2675 try block.addOperation(user);
2676
2677 var manager = pass.PassManager.init(allocator);
2678 defer manager.deinit();
2679 try manager.addPass(createCanonicalizationPass());
2680
2681 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2682 try testing.expectEqual(
2683 @as(usize, 1),
2684 ir.inspection.countOperationsNamed(module.op, scf.IfOp.operation_name),
2685 );
2686 try testing.expect(user.getOperand(0).? == if_op.getResult(0).?);
2687 }
2688
2689 test "CanonicalizationPass retains unqualified operations with populated rewrite patterns" {
2690 const testing = std.testing;
2691 const test_dialect = @import("../dialects/fixture/root.zig");
2692 const allocator = testing.allocator;
2693
2694 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2695 defer ctx.deinit(allocator);
2696
2697 const loc = ir.Location.getUnknown();
2698 const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
2699
2700 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2701 const block = module.getBodyBlock();
2702 const arg = try block.addArgument(i32_type, loc);
2703
2704 var builder = ir.OperationBuilder.init(&ctx);
2705 var identity_state = ir.Operation.State.init("test.identity", loc);
2706 identity_state.addOperands(&.{arg});
2707 identity_state.addTypes(&.{i32_type});
2708 const identity = try builder.create(identity_state);
2709 try block.addOperation(identity);
2710
2711 var user_state = ir.Operation.State.init("test.user", loc);
2712 user_state.addOperands(&.{identity.getResult(0).?});
2713 const user = try builder.create(user_state);
2714 try block.addOperation(user);
2715
2716 const TestCanonicalizationPass = CanonicalizationPass(.{
2717 .name = "test-canonicalize",
2718 .description = "test canonicalization pass",
2719 .populate_patterns = populateIdentityPattern,
2720 });
2721
2722 var manager = pass.PassManager.init(allocator);
2723 defer manager.deinit();
2724 try manager.addPass(TestCanonicalizationPass.init());
2725
2726 try testing.expect(user.getNumOperands() > 0);
2727 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
2728 defer allocator.free(before_ir);
2729 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2730 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
2731 defer allocator.free(after_ir);
2732 try testing.expectEqualStrings(before_ir, after_ir);
2733 }
2734
2735 test "CanonicalizationPass retains unqualified unused operations" {
2736 const testing = std.testing;
2737 const test_dialect = @import("../dialects/fixture/root.zig");
2738 const allocator = testing.allocator;
2739
2740 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2741 defer ctx.deinit(allocator);
2742 _ = try ctx.registerOperation("test.dead", .{});
2743 _ = try ctx.registerOperation("test.effect", .{});
2744
2745 const loc = ir.Location.getUnknown();
2746 const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
2747
2748 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, loc);
2749 const block = module.getBodyBlock();
2750
2751 var builder = ir.OperationBuilder.init(&ctx);
2752 var dead_state = ir.Operation.State.init("test.dead", loc);
2753 dead_state.addTypes(&.{i32_type});
2754 const dead = try builder.create(dead_state);
2755 try block.addOperation(dead);
2756
2757 var effect_state = ir.Operation.State.init("test.effect", loc);
2758 effect_state.addTypes(&.{i32_type});
2759 const effect = try builder.create(effect_state);
2760 try block.addOperation(effect);
2761
2762 var manager = pass.PassManager.init(allocator);
2763 defer manager.deinit();
2764 try manager.addPass(createCanonicalizationPass());
2765
2766 const before_ir = try ir.dump.operationAlloc(allocator, module.op);
2767 defer allocator.free(before_ir);
2768 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2769 const after_ir = try ir.dump.operationAlloc(allocator, module.op);
2770 defer allocator.free(after_ir);
2771 try testing.expectEqualStrings(before_ir, after_ir);
2772 }
2773
2774 test "CanonicalizationPass preserves analyses when unchanged" {
2775 const testing = std.testing;
2776 const test_dialect = @import("../dialects/fixture/root.zig");
2777 const allocator = testing.allocator;
2778
2779 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2780 defer ctx.deinit(allocator);
2781
2782 const module = try test_dialect.TestDialect.ModuleOp.create(&ctx, ir.Location.getUnknown());
2783
2784 var manager = pass.PassManager.init(allocator);
2785 defer manager.deinit();
2786 try manager.addPass(createCanonicalizationPass());
2787
2788 try testing.expectEqual(pass.PassResult.success, manager.run(module.op, &ctx));
2789 try testing.expectEqual(@as(u64, 0), manager.stats.passes_modified);
2790 }
2791
2792 test "CanonicalizationPass reports limits and mutation through both pattern routes" {
2793 inline for (.{ false, true }) |explicit| {
2794 try checkCanonicalizationTermination(explicit, .{}, false, false, false);
2795 try checkCanonicalizationTermination(explicit, .{}, false, false, true);
2796 try checkCanonicalizationTermination(explicit, .{}, true, false, true);
2797 try checkCanonicalizationTermination(explicit, .{}, true, false, false);
2798 try checkCanonicalizationTermination(explicit, .{ .max_iterations = 1 }, true, true, false);
2799 try checkCanonicalizationTermination(explicit, .{ .max_rewrites = 1 }, true, true, false);
2800 }
2801 }
2802
2803 fn noExtraCanonicalizationPatterns(_: *rewrite.RewritePatternSet) !void {}
2804
2805 fn checkCanonicalizationTermination(
2806 comptime explicit: bool,
2807 comptime config: conversion.GreedyRewriteConfig,
2808 add_rewrite: bool,
2809 exhausted: bool,
2810 invalid: bool,
2811 ) !void {
2812 const revision = @import("../product/revision/root.zig");
2813 const fixture = @import("../dialects/fixture/root.zig");
2814 const allocator = std.testing.allocator;
2815 var context = try ir.Context.init(allocator, ir.Context.Limits.testing);
2816 defer context.deinit(allocator);
2817 try ir.dialects.loadDialectSpec(&context, dialects.arith.spec);
2818 const module = try fixture.TestDialect.ModuleOp.create(&context, .unknown);
2819 const block = module.getBodyBlock();
2820 const user = try appendTerminationRewrite(&context, block, add_rewrite);
2821 var foreign = try ir.Context.init(allocator, ir.Context.Limits.testing);
2822 defer foreign.deinit(allocator);
2823 try foreign.allowUnregistered();
2824 const foreign_state = ir.Operation.State.init("test.foreign", .unknown);
2825 const foreign_op = try foreign.createOperation(foreign_state);
2826 if (invalid) try block.addOperation(foreign_op);
2827 defer if (invalid) block.detachOperation(foreign_op);
2828 const ledger = try revision.AccountingV1.create(allocator, .{
2829 .allowance = .uniform(std.math.maxInt(u64)),
2830 .workspace = 1 << 20,
2831 .events = 16,
2832 }, &.{});
2833 defer ledger.destroy();
2834 var cache = try pass.AnalysisCache.initAccounted(allocator, null, ledger, .{}, 8);
2835 defer cache.deinit();
2836 var manager = pass.PassManager.init(allocator);
2837 defer manager.deinit();
2838 try manager.addPass(CanonicalizationPass(.{
2839 .populate_patterns = if (explicit) noExtraCanonicalizationPatterns else null,
2840 .greedy_config = config,
2841 .cleanup_dead_ops = false,
2842 }).init());
2843 const result = manager.runWithAnalysisCache(module.op, &context, &cache, .{ .max_threads = 1 });
2844 try std.testing.expectEqual(
2845 if (exhausted or invalid) pass.PassResult.failure else .success,
2846 result,
2847 );
2848 try checkTerminationReceipt(&manager, ledger, add_rewrite, exhausted, invalid);
2849 try std.testing.expect(user.getOperand(0).? == block.arguments.items[0]);
2850 try std.testing.expectEqual(
2851 0,
2852 ir.inspection.countOperationsNamed(module.op, arith.AddOp.operation_name),
2853 );
2854 }
2855
2856 fn checkTerminationReceipt(
2857 manager: *const pass.PassManager,
2858 ledger: *@import("../product/revision/root.zig").AccountingV1,
2859 add_rewrite: bool,
2860 exhausted: bool,
2861 invalid: bool,
2862 ) !void {
2863 const revision = @import("../product/revision/root.zig");
2864 const receipt = ledger.view();
2865 const ordinary: revision.receipt.Outcome = if (invalid) .rejected else .running;
2866 const outcome: revision.receipt.Outcome = if (exhausted) .exhausted else ordinary;
2867 try std.testing.expectEqual(outcome, receipt.outcome);
2868 try std.testing.expectEqual(
2869 @intFromBool(add_rewrite),
2870 receipt.executed.counters.successful_rewrites,
2871 );
2872 const iterations: u64 = if (add_rewrite and !exhausted and !invalid) 2 else 1;
2873 try std.testing.expectEqual(iterations, receipt.executed.counters.rewrite_iterations);
2874 try std.testing.expectEqual(
2875 @intFromBool(add_rewrite),
2876 receipt.executed.counters.passes_modified,
2877 );
2878 try std.testing.expectEqual(1, receipt.executed.counters.pass_runs);
2879 if (exhausted) {
2880 try std.testing.expectEqual(
2881 .exhausted,
2882 manager.getLastFailureReproducer().?.failure_kind.?,
2883 );
2884 try std.testing.expectError(error.WorkExhausted, ledger.producersComplete());
2885 }
2886 }
2887
2888 fn appendTerminationRewrite(
2889 context: *ir.Context,
2890 block: *ir.Block,
2891 add_rewrite: bool,
2892 ) !*ir.Operation {
2893 const typ = try arith.getScalarType(context, .i32);
2894 const value = try block.addArgument(typ, .unknown);
2895 var output = value;
2896 if (add_rewrite) {
2897 const zero = try arith.ConstantOp.createInt(context, .unknown, typ, 0);
2898 try block.addOperation(zero.op);
2899 const add = try arith.AddOp.create(context, .unknown, value, zero.getResult());
2900 try block.addOperation(add.op);
2901 output = add.getResult();
2902 }
2903 return appendUser(context, block, .unknown, output);
2904 }
2905
2906 test "canonicalization population bounds cover sealed builder allocation traffic" {
2907 const fixed = @import("alloc_fixed");
2908 const allocator = std.testing.allocator;
2909 var context = try ir.Context.init(allocator, ir.Context.Limits.testing);
2910 defer context.deinit(allocator);
2911 try ir.dialects.loadDialectSpec(&context, dialects.arith.spec);
2912 const specs: [64]rewrite.RewritePatternSpec = @splat(.{
2913 .name = "population-extra",
2914 .root_op_name = "test.extra",
2915 });
2916 for ([_]usize{ 0, 1, 64 }) |extra| {
2917 const bounds = try patternPopulationBounds(&context, specs[0..extra]);
2918 const bytes = try allocator.alignedAlloc(u8, .@"64", @intCast(bounds.bytes));
2919 defer allocator.free(bytes);
2920 var backing = fixed.Tracked.init(bytes);
2921 var retained = fixed.Monotonic.init(backing.allocator(), bytes.len);
2922 var patterns = rewrite.RewritePatternSet.init(retained.allocator());
2923 defer patterns.deinit();
2924 _ = try populateInitialCanonicalizationPatterns(&context, &patterns, true, true);
2925 try populateRegisteredCanonicalizationPatterns(&context, &patterns);
2926 for (specs[0..extra]) |spec| {
2927 try patterns.add(rewrite.RewritePattern.init(spec, populationNoMatch));
2928 }
2929 try patterns.seal();
2930 try std.testing.expectEqual(bounds.patterns, patterns.count());
2931 const used = if (retained.current) |*current| fixed.used(current) else 0;
2932 try std.testing.expect(used <= bounds.bytes);
2933 try std.testing.expect(!backing.exhausted);
2934 }
2935 }
2936
2937 fn populationNoMatch(_: *ir.Operation, _: *rewrite.PatternRewriter) rewrite.PatternResult {
2938 return .failure;
2939 }