tiny.choir.ir.equivalence

1const std = @import("std");2const alloc_arena = @import("alloc_arena");3const Operation = @import("operation/root.zig").Operation;4const Value = @import("value.zig").Value;5const Attribute = @import("attribute.zig").Attribute;6const NamedAttribute = @import("attribute.zig").NamedAttribute;7const context_mod = @import("context/root.zig");8const Context = context_mod.Context;9const Location = @import("location.zig").Location;10const interfaces = @import("interfaces/root.zig");1112pub const OperationEquivalence = struct {13    pub const ValueMapper = *const fn (?*const anyopaque, *Value) *Value;1415    pub const AttributeFilter = *const fn (?*const anyopaque, *Operation, NamedAttribute) bool;1617    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    };2526    pub fn computeHash(27        op: *Operation,28        options: Options,29    ) u64 {30        var hasher = std.hash.Wyhash.init(0);3132        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        }3940        if (options.include_locations) {41            updateLocation(&hasher, op.location);42        }4344        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        }5758        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        }6465        return hasher.final();66    }6768    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;8081        for (lhs.result_types, rhs.result_types) |lhs_type, rhs_type| {82            if (!lhs_type.eql(rhs_type)) return false;83        }8485        if (!operandsEquivalent(lhs.operand_values, rhs.operand_values, options)) {86            return false;87        }8889        return attrsEquivalent(lhs, rhs, options);90    }9192    pub fn exactValueMapper(_: ?*const anyopaque, value: *Value) *Value {93        return value;94    }9596    fn valueHash(options: Options, value: *Value) u64 {97        return @intFromPtr(mapValue(options, value));98    }99100    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    }106107    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};114115fn 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    }131132    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) or138            (lhs_0 == rhs_1 and lhs_1 == rhs_0);139    }140141    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;151152        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}164165fn 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}176177fn 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}187188fn 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}191192fn 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}229230fn updateAttribute(hasher: *std.hash.Wyhash, attr: Attribute) void {231    updateU64(hasher, @backingInt(attr.attr_id));232    updateBytes(hasher, attr.abstract.name);233234    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    }286287    updateU64(hasher, @intFromPtr(attr.impl));288}289290fn updateBytes(hasher: *std.hash.Wyhash, bytes: []const u8) void {291    updateU64(hasher, bytes.len);292    hasher.update(bytes);293}294295fn 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}300301fn 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}312313fn ignoreDebugAttr(_: ?*const anyopaque, _: *Operation, attr: NamedAttribute) bool {314    return !std.mem.eql(u8, attr.name, "debug.span");315}316317const RemapPair = struct {318    from: *Value,319    to: *Value,320};321322fn 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}327328test "OperationEquivalence matches same operation shape" {329    const testing = std.testing;330    const allocator = testing.allocator;331332    var arena = alloc_arena.Arena.init(allocator);333    defer arena.deinit();334    const arena_alloc = arena.allocator();335336    var ctx = try Context.init(arena_alloc, Context.Limits.testing);337    defer ctx.deinit(arena_alloc);338    try ctx.allowUnregistered();339340    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());345346    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));350351    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}356357test "OperationEquivalence keeps distinct attrs apart" {358    const testing = std.testing;359    const allocator = testing.allocator;360361    var arena = alloc_arena.Arena.init(allocator);362    defer arena.deinit();363    const arena_alloc = arena.allocator();364365    var ctx = try Context.init(arena_alloc, Context.Limits.testing);366    defer ctx.deinit(arena_alloc);367    try ctx.allowUnregistered();368369    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));374375    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}380381test "OperationEquivalence filters nonsemantic attrs" {382    const testing = std.testing;383    const allocator = testing.allocator;384385    var arena = alloc_arena.Arena.init(allocator);386    defer arena.deinit();387    const arena_alloc = arena.allocator();388389    var ctx = try Context.init(arena_alloc, Context.Limits.testing);390    defer ctx.deinit(arena_alloc);391    try ctx.allowUnregistered();392393    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));398399    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}405406test "OperationEquivalence hashes inherent attributes without temporary allocation" {407    const testing = std.testing;408409    var ctx = try Context.init(testing.allocator, Context.Limits.testing);410    defer ctx.deinit(testing.allocator);411    try ctx.allowUnregistered();412413    _ = 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    );419420    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));425426    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}431432test "OperationEquivalence commutes operands" {433    const testing = std.testing;434    const allocator = testing.allocator;435436    var arena = alloc_arena.Arena.init(allocator);437    defer arena.deinit();438    const arena_alloc = arena.allocator();439440    var ctx = try Context.init(arena_alloc, Context.Limits.testing);441    defer ctx.deinit(arena_alloc);442    try ctx.allowUnregistered();443444    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());449450    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 };453454    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}460461test "OperationEquivalence preserves multiplicity for variadic commutative operands" {462    const testing = std.testing;463    const allocator = testing.allocator;464465    var arena = alloc_arena.Arena.init(allocator);466    defer arena.deinit();467    const arena_alloc = arena.allocator();468469    var ctx = try Context.init(arena_alloc, Context.Limits.testing);470    defer ctx.deinit(arena_alloc);471    try ctx.allowUnregistered();472473    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());479480    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 };499500    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}507508test "OperationEquivalence maps values before comparing operands" {509    const testing = std.testing;510    const allocator = testing.allocator;511512    var arena = alloc_arena.Arena.init(allocator);513    defer arena.deinit();514    const arena_alloc = arena.allocator();515516    var ctx = try Context.init(arena_alloc, Context.Limits.testing);517    defer ctx.deinit(arena_alloc);518    try ctx.allowUnregistered();519520    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());525526    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    };533534    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}

1pub const equivalence = @import("equivalence.zig");