lib/choir/src/core/equivalence.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const Operation = @import("operation/root.zig").Operation;
4 const Value = @import("value.zig").Value;
5 const Attribute = @import("attribute.zig").Attribute;
6 const NamedAttribute = @import("attribute.zig").NamedAttribute;
7 const context_mod = @import("context/root.zig");
8 const Context = context_mod.Context;
9 const Location = @import("location.zig").Location;
10 const interfaces = @import("interfaces/root.zig");
11
12 pub const OperationEquivalence = struct {
13 pub const ValueMapper = *const fn (?*const anyopaque, *Value) *Value;
14
15 pub const AttributeFilter = *const fn (?*const anyopaque, *Operation, NamedAttribute) bool;
16
17 pub const Options = struct {
18 value_mapper: ?ValueMapper = null,
19 value_mapper_context: ?*const anyopaque = null,
20 attribute_filter: ?AttributeFilter = null,
21 attribute_filter_context: ?*const anyopaque = null,
22 commute_operands: bool = false,
23 include_locations: bool = false,
24 };
25
26 pub fn computeHash(
27 op: *Operation,
28 options: Options,
29 ) u64 {
30 var hasher = std.hash.Wyhash.init(0);
31
32 updateBytes(&hasher, op.name.name);
33 updateU64(&hasher, op.regions.items.len);
34 updateU64(&hasher, op.successors.items.len);
35 updateU64(&hasher, op.result_types.len);
36 for (op.result_types) |typ| {
37 updateU64(&hasher, typ.uniqueId());
38 }
39
40 if (options.include_locations) {
41 updateLocation(&hasher, op.location);
42 }
43
44 const operands = op.operand_values;
45 updateU64(&hasher, operands.len);
46 if (options.commute_operands and operands.len > 1) {
47 var operand_hash: u64 = 0;
48 for (operands) |operand| {
49 operand_hash +%= valueHash(options, operand);
50 }
51 updateU64(&hasher, operand_hash);
52 } else {
53 for (operands) |operand| {
54 updateU64(&hasher, valueHash(options, operand));
55 }
56 }
57
58 var hash_iter = op.getAttrs();
59 while (hash_iter.next()) |attr| {
60 if (!attributeIncluded(options, op, attr)) continue;
61 updateBytes(&hasher, attr.name);
62 updateAttribute(&hasher, attr.value);
63 }
64
65 return hasher.final();
66 }
67
68 pub fn isEquivalentTo(
69 lhs: *Operation,
70 rhs: *Operation,
71 options: Options,
72 ) bool {
73 if (lhs == rhs) return true;
74 if (!sameName(lhs.name.name, rhs.name.name)) return false;
75 if (lhs.regions.items.len != rhs.regions.items.len) return false;
76 if (lhs.successors.items.len != rhs.successors.items.len) return false;
77 if (lhs.operands.items.len != rhs.operands.items.len) return false;
78 if (lhs.result_types.len != rhs.result_types.len) return false;
79 if (options.include_locations and !lhs.location.eql(rhs.location)) return false;
80
81 for (lhs.result_types, rhs.result_types) |lhs_type, rhs_type| {
82 if (!lhs_type.eql(rhs_type)) return false;
83 }
84
85 if (!operandsEquivalent(lhs.operand_values, rhs.operand_values, options)) {
86 return false;
87 }
88
89 return attrsEquivalent(lhs, rhs, options);
90 }
91
92 pub fn exactValueMapper(_: ?*const anyopaque, value: *Value) *Value {
93 return value;
94 }
95
96 fn valueHash(options: Options, value: *Value) u64 {
97 return @intFromPtr(mapValue(options, value));
98 }
99
100 fn mapValue(options: Options, value: *Value) *Value {
101 if (options.value_mapper) |mapper| {
102 return mapper(options.value_mapper_context, value);
103 }
104 return value;
105 }
106
107 fn attributeIncluded(options: Options, op: *Operation, attr: NamedAttribute) bool {
108 if (options.attribute_filter) |filter| {
109 return filter(options.attribute_filter_context, op, attr);
110 }
111 return true;
112 }
113 };
114
115 fn operandsEquivalent(
116 lhs: []const *Value,
117 rhs: []const *Value,
118 options: OperationEquivalence.Options,
119 ) bool {
120 if (lhs.len != rhs.len) return false;
121 if (!options.commute_operands or lhs.len <= 1) {
122 for (lhs, rhs) |lhs_value, rhs_value| {
123 if (OperationEquivalence.mapValue(options, lhs_value) !=
124 OperationEquivalence.mapValue(options, rhs_value))
125 {
126 return false;
127 }
128 }
129 return true;
130 }
131
132 if (lhs.len == 2) {
133 const lhs_0 = OperationEquivalence.mapValue(options, lhs[0]);
134 const lhs_1 = OperationEquivalence.mapValue(options, lhs[1]);
135 const rhs_0 = OperationEquivalence.mapValue(options, rhs[0]);
136 const rhs_1 = OperationEquivalence.mapValue(options, rhs[1]);
137 return (lhs_0 == rhs_0 and lhs_1 == rhs_1) or
138 (lhs_0 == rhs_1 and lhs_1 == rhs_0);
139 }
140
141 for (lhs, 0..) |lhs_value, lhs_index| {
142 const mapped_lhs = OperationEquivalence.mapValue(options, lhs_value);
143 var seen = false;
144 for (lhs[0..lhs_index]) |earlier_value| {
145 if (OperationEquivalence.mapValue(options, earlier_value) == mapped_lhs) {
146 seen = true;
147 break;
148 }
149 }
150 if (seen) continue;
151
152 var lhs_count: usize = 0;
153 for (lhs) |value| {
154 lhs_count += @intFromBool(OperationEquivalence.mapValue(options, value) == mapped_lhs);
155 }
156 var rhs_count: usize = 0;
157 for (rhs) |value| {
158 rhs_count += @intFromBool(OperationEquivalence.mapValue(options, value) == mapped_lhs);
159 }
160 if (lhs_count != rhs_count) return false;
161 }
162 return true;
163 }
164
165 fn attrsEquivalent(lhs: *Operation, rhs: *Operation, options: OperationEquivalence.Options) bool {
166 var lhs_iter = lhs.getAttrs();
167 var rhs_iter = rhs.getAttrs();
168 while (true) {
169 const lhs_attr = nextIncluded(&lhs_iter, lhs, options);
170 const rhs_attr = nextIncluded(&rhs_iter, rhs, options);
171 if (lhs_attr == null or rhs_attr == null) return lhs_attr == null and rhs_attr == null;
172 if (!sameName(lhs_attr.?.name, rhs_attr.?.name)) return false;
173 if (!lhs_attr.?.value.eql(rhs_attr.?.value)) return false;
174 }
175 }
176
177 fn nextIncluded(
178 attrs: *Operation.AttributeIterator,
179 op: *Operation,
180 options: OperationEquivalence.Options,
181 ) ?NamedAttribute {
182 while (attrs.next()) |attr| {
183 if (OperationEquivalence.attributeIncluded(options, op, attr)) return attr;
184 }
185 return null;
186 }
187
188 fn sameName(lhs: []const u8, rhs: []const u8) bool {
189 return (lhs.ptr == rhs.ptr and lhs.len == rhs.len) or std.mem.eql(u8, lhs, rhs);
190 }
191
192 fn updateLocation(hasher: *std.hash.Wyhash, loc: Location) void {
193 const Tag = std.meta.Tag(Location);
194 updateU64(hasher, @backingInt(@as(Tag, loc)));
195 switch (loc) {
196 .unknown => {},
197 .file => |file| {
198 updateBytes(hasher, file.filename);
199 updateU64(hasher, file.line);
200 updateU64(hasher, file.column);
201 },
202 .file_range => |range| {
203 updateBytes(hasher, range.filename);
204 updateU64(hasher, range.start.byte);
205 updateU64(hasher, range.start.line);
206 updateU64(hasher, range.start.column);
207 updateU64(hasher, range.end.byte);
208 updateU64(hasher, range.end.line);
209 updateU64(hasher, range.end.column);
210 },
211 .name => |name| {
212 updateBytes(hasher, name.name);
213 updateU64(hasher, if (name.child == null) 0 else 1);
214 if (name.child) |child| updateLocation(hasher, child.*);
215 },
216 .fused => |fused| {
217 updateU64(hasher, fused.locations.len);
218 for (fused.locations) |child| {
219 updateLocation(hasher, child);
220 }
221 updateU64(hasher, if (fused.metadata) |metadata| @intFromPtr(metadata) else 0);
222 },
223 .call_site => |call_site| {
224 updateLocation(hasher, call_site.callee.*);
225 updateLocation(hasher, call_site.caller.*);
226 },
227 }
228 }
229
230 fn updateAttribute(hasher: *std.hash.Wyhash, attr: Attribute) void {
231 updateU64(hasher, @backingInt(attr.attr_id));
232 updateBytes(hasher, attr.abstract.name);
233
234 if (attr.cast(Attribute.IntegerAttr)) |int_attr| {
235 updateU64(hasher, @bitCast(int_attr.value));
236 updateU64(hasher, int_attr.width);
237 updateU64(hasher, if (int_attr.is_signed) 1 else 0);
238 return;
239 }
240 if (attr.cast(Attribute.FloatAttr)) |float_attr| {
241 updateU64(hasher, @bitCast(float_attr.value));
242 updateU64(hasher, float_attr.width);
243 return;
244 }
245 if (attr.cast(Attribute.BoolAttr)) |bool_attr| {
246 updateU64(hasher, if (bool_attr.value) 1 else 0);
247 return;
248 }
249 if (attr.cast(Attribute.StringAttr)) |string_attr| {
250 updateBytes(hasher, string_attr.value);
251 return;
252 }
253 if (attr.cast(Attribute.SymbolRefAttr)) |symbol_ref| {
254 updateBytes(hasher, symbol_ref.root_reference);
255 updateU64(hasher, symbol_ref.nested_references.len);
256 for (symbol_ref.nested_references) |nested| {
257 updateBytes(hasher, nested);
258 }
259 return;
260 }
261 if (attr.cast(Attribute.StringListAttr)) |list_attr| {
262 updateU64(hasher, list_attr.values.len);
263 for (list_attr.values) |value| {
264 updateBytes(hasher, value);
265 }
266 return;
267 }
268 if (attr.cast(Attribute.TypeListAttr)) |list_attr| {
269 updateU64(hasher, list_attr.values.len);
270 for (list_attr.values) |typ| {
271 updateU64(hasher, typ.uniqueId());
272 }
273 return;
274 }
275 if (attr.cast(Attribute.ArrayAttr)) |array_attr| {
276 updateU64(hasher, array_attr.values.len);
277 for (array_attr.values) |value| {
278 updateAttribute(hasher, value);
279 }
280 return;
281 }
282 if (attr.cast(Attribute.DialectAttr)) |dialect_attr| {
283 updateBytes(hasher, dialect_attr.payload);
284 return;
285 }
286
287 updateU64(hasher, @intFromPtr(attr.impl));
288 }
289
290 fn updateBytes(hasher: *std.hash.Wyhash, bytes: []const u8) void {
291 updateU64(hasher, bytes.len);
292 hasher.update(bytes);
293 }
294
295 fn updateU64(hasher: *std.hash.Wyhash, value: u64) void {
296 var buf: [8]u8 = undefined;
297 std.mem.writeInt(u64, &buf, value, .little);
298 hasher.update(&buf);
299 }
300
301 fn operationWithOperands(
302 ctx: *Context,
303 name: []const u8,
304 operands: []const *Value,
305 result_type: @import("type.zig").Type,
306 ) !*Operation {
307 var state = Operation.State.init(name, Location.getUnknown());
308 state.addOperands(operands);
309 state.addTypes(&.{result_type});
310 return try ctx.createOperation(state);
311 }
312
313 fn ignoreDebugAttr(_: ?*const anyopaque, _: *Operation, attr: NamedAttribute) bool {
314 return !std.mem.eql(u8, attr.name, "debug.span");
315 }
316
317 const RemapPair = struct {
318 from: *Value,
319 to: *Value,
320 };
321
322 fn pairValueMapper(mapper_context: ?*const anyopaque, value: *Value) *Value {
323 const pair: *const RemapPair = @ptrCast(@alignCast(mapper_context.?));
324 if (value == pair.from) return pair.to;
325 return value;
326 }
327
328 test "OperationEquivalence matches same operation shape" {
329 const testing = std.testing;
330 const allocator = testing.allocator;
331
332 var arena = alloc_arena.Arena.init(allocator);
333 defer arena.deinit();
334 const arena_alloc = arena.allocator();
335
336 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
337 defer ctx.deinit(arena_alloc);
338 try ctx.allowUnregistered();
339
340 var region = context_mod.initRegion(&ctx);
341 const block = try region.addBlock();
342 const i32_type = try ctx.getDialectTypeFromName("test.i32");
343 const lhs = try block.addArgument(i32_type, Location.getUnknown());
344 const rhs = try block.addArgument(i32_type, Location.getUnknown());
345
346 const first = try operationWithOperands(&ctx, "test.add", &.{ lhs, rhs }, i32_type);
347 const second = try operationWithOperands(&ctx, "test.add", &.{ lhs, rhs }, i32_type);
348 try first.setAttr("value", try ctx.getI64Attr(1));
349 try second.setAttr("value", try ctx.getI64Attr(1));
350
351 const first_hash = OperationEquivalence.computeHash(first, .{});
352 const second_hash = OperationEquivalence.computeHash(second, .{});
353 try testing.expectEqual(first_hash, second_hash);
354 try testing.expect(OperationEquivalence.isEquivalentTo(first, second, .{}));
355 }
356
357 test "OperationEquivalence keeps distinct attrs apart" {
358 const testing = std.testing;
359 const allocator = testing.allocator;
360
361 var arena = alloc_arena.Arena.init(allocator);
362 defer arena.deinit();
363 const arena_alloc = arena.allocator();
364
365 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
366 defer ctx.deinit(arena_alloc);
367 try ctx.allowUnregistered();
368
369 const i32_type = try ctx.getDialectTypeFromName("test.i32");
370 const first = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
371 const second = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
372 try first.setAttr("value", try ctx.getI64Attr(1));
373 try second.setAttr("value", try ctx.getI64Attr(2));
374
375 const first_hash = OperationEquivalence.computeHash(first, .{});
376 const second_hash = OperationEquivalence.computeHash(second, .{});
377 try testing.expect(first_hash != second_hash);
378 try testing.expect(!OperationEquivalence.isEquivalentTo(first, second, .{}));
379 }
380
381 test "OperationEquivalence filters nonsemantic attrs" {
382 const testing = std.testing;
383 const allocator = testing.allocator;
384
385 var arena = alloc_arena.Arena.init(allocator);
386 defer arena.deinit();
387 const arena_alloc = arena.allocator();
388
389 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
390 defer ctx.deinit(arena_alloc);
391 try ctx.allowUnregistered();
392
393 const i32_type = try ctx.getDialectTypeFromName("test.i32");
394 const first = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
395 const second = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
396 try first.setAttr("debug.span", try ctx.getI64Attr(1));
397 try second.setAttr("debug.span", try ctx.getI64Attr(2));
398
399 const options = OperationEquivalence.Options{ .attribute_filter = ignoreDebugAttr };
400 const first_hash = OperationEquivalence.computeHash(first, options);
401 const second_hash = OperationEquivalence.computeHash(second, options);
402 try testing.expectEqual(first_hash, second_hash);
403 try testing.expect(OperationEquivalence.isEquivalentTo(first, second, options));
404 }
405
406 test "OperationEquivalence hashes inherent attributes without temporary allocation" {
407 const testing = std.testing;
408
409 var ctx = try Context.init(testing.allocator, Context.Limits.testing);
410 defer ctx.deinit(testing.allocator);
411 try ctx.allowUnregistered();
412
413 _ = try ctx.registerOperation("test.constant", .{});
414 try ctx.registerOperationInherentAttributeName("test.constant", "value");
415 try ctx.registerOperationPropertiesModel(
416 "test.constant",
417 interfaces.singleAttributePropertiesModel("test.constant.properties", "value"),
418 );
419
420 const i32_type = try ctx.getDialectTypeFromName("test.i32");
421 const first = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
422 const second = try operationWithOperands(&ctx, "test.constant", &.{}, i32_type);
423 try first.setAttr("value", try ctx.getI64Attr(7));
424 try second.setAttr("value", try ctx.getI64Attr(8));
425
426 const first_hash = OperationEquivalence.computeHash(first, .{});
427 const second_hash = OperationEquivalence.computeHash(second, .{});
428 try testing.expect(first_hash != second_hash);
429 try testing.expect(!OperationEquivalence.isEquivalentTo(first, second, .{}));
430 }
431
432 test "OperationEquivalence commutes operands" {
433 const testing = std.testing;
434 const allocator = testing.allocator;
435
436 var arena = alloc_arena.Arena.init(allocator);
437 defer arena.deinit();
438 const arena_alloc = arena.allocator();
439
440 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
441 defer ctx.deinit(arena_alloc);
442 try ctx.allowUnregistered();
443
444 var region = context_mod.initRegion(&ctx);
445 const block = try region.addBlock();
446 const i32_type = try ctx.getDialectTypeFromName("test.i32");
447 const lhs = try block.addArgument(i32_type, Location.getUnknown());
448 const rhs = try block.addArgument(i32_type, Location.getUnknown());
449
450 const first = try operationWithOperands(&ctx, "test.add", &.{ lhs, rhs }, i32_type);
451 const second = try operationWithOperands(&ctx, "test.add", &.{ rhs, lhs }, i32_type);
452 const options = OperationEquivalence.Options{ .commute_operands = true };
453
454 const first_hash = OperationEquivalence.computeHash(first, options);
455 const second_hash = OperationEquivalence.computeHash(second, options);
456 try testing.expectEqual(first_hash, second_hash);
457 try testing.expect(OperationEquivalence.isEquivalentTo(first, second, options));
458 try testing.expect(!OperationEquivalence.isEquivalentTo(first, second, .{}));
459 }
460
461 test "OperationEquivalence preserves multiplicity for variadic commutative operands" {
462 const testing = std.testing;
463 const allocator = testing.allocator;
464
465 var arena = alloc_arena.Arena.init(allocator);
466 defer arena.deinit();
467 const arena_alloc = arena.allocator();
468
469 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
470 defer ctx.deinit(arena_alloc);
471 try ctx.allowUnregistered();
472
473 var region = context_mod.initRegion(&ctx);
474 const block = try region.addBlock();
475 const i32_type = try ctx.getDialectTypeFromName("test.i32");
476 const lhs = try block.addArgument(i32_type, Location.getUnknown());
477 const rhs = try block.addArgument(i32_type, Location.getUnknown());
478 const extra = try block.addArgument(i32_type, Location.getUnknown());
479
480 const first = try operationWithOperands(
481 &ctx,
482 "test.combine",
483 &.{ lhs, rhs, lhs, extra },
484 i32_type,
485 );
486 const reordered = try operationWithOperands(
487 &ctx,
488 "test.combine",
489 &.{ extra, lhs, rhs, lhs },
490 i32_type,
491 );
492 const different = try operationWithOperands(
493 &ctx,
494 "test.combine",
495 &.{ extra, lhs, rhs, rhs },
496 i32_type,
497 );
498 const options = OperationEquivalence.Options{ .commute_operands = true };
499
500 try testing.expectEqual(
501 OperationEquivalence.computeHash(first, options),
502 OperationEquivalence.computeHash(reordered, options),
503 );
504 try testing.expect(OperationEquivalence.isEquivalentTo(first, reordered, options));
505 try testing.expect(!OperationEquivalence.isEquivalentTo(first, different, options));
506 }
507
508 test "OperationEquivalence maps values before comparing operands" {
509 const testing = std.testing;
510 const allocator = testing.allocator;
511
512 var arena = alloc_arena.Arena.init(allocator);
513 defer arena.deinit();
514 const arena_alloc = arena.allocator();
515
516 var ctx = try Context.init(arena_alloc, Context.Limits.testing);
517 defer ctx.deinit(arena_alloc);
518 try ctx.allowUnregistered();
519
520 var region = context_mod.initRegion(&ctx);
521 const block = try region.addBlock();
522 const i32_type = try ctx.getDialectTypeFromName("test.i32");
523 const canonical = try block.addArgument(i32_type, Location.getUnknown());
524 const stale = try block.addArgument(i32_type, Location.getUnknown());
525
526 const first = try operationWithOperands(&ctx, "test.use", &.{canonical}, i32_type);
527 const second = try operationWithOperands(&ctx, "test.use", &.{stale}, i32_type);
528 const pair = RemapPair{ .from = stale, .to = canonical };
529 const options = OperationEquivalence.Options{
530 .value_mapper = pairValueMapper,
531 .value_mapper_context = &pair,
532 };
533
534 const first_hash = OperationEquivalence.computeHash(first, options);
535 const second_hash = OperationEquivalence.computeHash(second, options);
536 try testing.expectEqual(first_hash, second_hash);
537 try testing.expect(OperationEquivalence.isEquivalentTo(first, second, options));
538 try testing.expect(!OperationEquivalence.isEquivalentTo(first, second, .{}));
539 }