tiny.choir.product.hashing.numbering

1const std = @import("std");2const alloc_arena = @import("alloc_arena");3const alloc_phase = @import("alloc_phase");4const ir = @import("../../core/root.zig");5const hashing = @import("root.zig");6const capacity_model = hashing.capacity;7const index_model = hashing.index;8const walk = hashing.walk;910const Allocator = std.mem.Allocator;1112pub const StableValueNumbering = struct {13    pub const claim: alloc_phase.capacity.Declaration = .{14        .source = .{15            .id = "choir.stable_value_numbering",16            .kind = .phase_static,17            .limit_source = .caller,18            .storage = .{19                .covered = &.{20                    .{21                        .id = "valueentry_array_operationframe_array_and_attributeframe_array",22                        .lifetime = .steady,23                        .detail = "ValueEntry array, OperationFrame array, and AttributeFrame array",24                    },25                },26                .excluded = &.{27                    "borrowed mutable IR and every referenced Value, type, and attribute payload",28                    "generic fingerprint builder storage and side effects",29                },30            },31            .capacity = .{32                .inputs = &.{33                    alloc_phase.capacity.bindInput(Limits, "facts_value_count", "facts.value_count"),34                    alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),35                    alloc_phase.capacity.bindInput(Limits, "facts_attribute_depth", "facts.attribute_depth"),36                },37                .type_selectors = &.{38                    alloc_phase.capacity.bindType(capacity_model.ValueEntry, "valueentry"),39                    alloc_phase.capacity.bindType(capacity_model.OperationFrame, "operationframe"),40                    alloc_phase.capacity.bindType(capacity_model.AttributeFrame, "attributeframe"),41                },42                .nodes = &.{43                    .{ .input = 0 },44                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },45                    .{ .input = 1 },46                    .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 1 } } },47                    .{ .input = 2 },48                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },49                    .{ .add = .{ .left = 1, .right = 3 } },50                    .{ .add = .{ .left = 6, .right = 5 } },51                },52                .assertions = &.{.{53                    .scope = .closure_total,54                    .measure = .retained,55                    .relation = .exact,56                    .expression = 7,57                }},58            },59            .overload = .{60                .kind = .reject_before_seal,61                .detail = "nesting, arithmetic, OOM, or definition drift rejects before activation; there is no steady exhaustion",62            },63            .risks = .{64                .transitive = .{65                    .status = .open,66                    .detail = "updateSubtreeFingerprint invokes unconstrained anytype builder methods and an indirect inherent-property hook",67                },68                .foreign = .{69                    .status = .open,70                    .detail = "generic builder and property hook implementations may reacquire allocator policy or cross foreign boundaries",71                },72            },73            .obligations = &.{74                .{ .key = "numbering_capacity", .role = .capacity_model },75                .{ .key = "numbering_sealed_repeat_overload", .role = .overload },76                .{ .key = "numbering_sealed_repeat_transitive_risk", .role = .transitive_risk },77                .{ .key = "numbering_sealed_repeat_foreign_risk", .role = .foreign_risk },78                .{ .key = "numbering_oom_retry", .role = .overload },79            },80        },81        .bindings = .{82            .owner = @This(),83            .seal = .{84                .family = alloc_phase.capacity.selector(@This().activate),85                .premise = .{86                    .class = .checked_semantic_fact,87                    .authority = .checker,88                },89            },90            .teardown = .{91                .family = alloc_phase.capacity.selector(@This().deinit),92                .premise = .{93                    .class = .checked_semantic_fact,94                    .authority = .checker,95                },96            },97        },98    };99    phase: alloc_phase.capacity.Phase,100    capacity: Capacity,101    root: *ir.Operation,102    index: index_model.ValueIndex,103    operation_frames: []capacity_model.OperationFrame,104    attribute_frames: []capacity_model.AttributeFrame,105106    pub const Limits = capacity_model.Limits;107    pub const Capacity = capacity_model.Capacity;108109    const Self = @This();110111    pub fn init(allocator: Allocator, limits: Limits) !Self {112        const current = Limits.inspect(limits.root) catch return error.InputChanged;113        if (!limits.facts.eql(current.facts)) return error.InputChanged;114        const derived = try Capacity.derive(limits);115        var index = try index_model.ValueIndex.init(allocator, derived);116        errdefer index.deinit(allocator);117        const operation_frames = try allocator.alloc(118            capacity_model.OperationFrame,119            derived.facts.operation_depth,120        );121        errdefer allocator.free(operation_frames);122        const attribute_frames = try allocator.alloc(123            capacity_model.AttributeFrame,124            derived.facts.attribute_depth,125        );126        errdefer allocator.free(attribute_frames);127        try index.fill(limits.root, operation_frames);128        return .{129            .phase = .initialization,130            .capacity = derived,131            .root = limits.root,132            .index = index,133            .operation_frames = operation_frames,134            .attribute_frames = attribute_frames,135        };136    }137138    pub fn activate(self: *Self) error{ AlreadyActive, InputChanged }!void {139        if (self.phase != .initialization) return error.AlreadyActive;140        const current = Limits.inspect(self.root) catch return error.InputChanged;141        if (!self.capacity.facts.eql(current.facts)) return error.InputChanged;142        if (!self.index.matchesDefinitions(self.root, self.operation_frames)) {143            return error.InputChanged;144        }145        self.phase = .steady;146    }147148    pub fn valueId(self: *const Self, value: *const ir.Value) ?u64 {149        self.requireSteady();150        return self.index.lookup(value);151    }152153    pub fn updateSubtreeFingerprint(154        self: *Self,155        builder: anytype,156        operation: *ir.Operation,157    ) void {158        self.requireSteady();159        if (!self.root.isAncestor(operation)) {160            @panic("stable value numbering subtree is outside its indexed root");161        }162        var iterator = walk.Iterator.init(self.operation_frames, operation);163        while (iterator.next()) |event| switch (event) {164            .operation => |op| self.updateOperation(builder, op),165            .region => |region| updateRegion(builder, region),166            .block => |block| self.updateBlock(builder, block),167        };168    }169170    pub fn deinit(self: *Self, allocator: Allocator) void {171        if (self.phase == .teardown) @panic("stable value numbering teardown is terminal");172        self.phase = .teardown;173        allocator.free(self.attribute_frames);174        allocator.free(self.operation_frames);175        self.index.deinit(allocator);176        self.root = undefined;177        self.operation_frames = undefined;178        self.attribute_frames = undefined;179    }180181    fn updateOperation(182        self: *Self,183        builder: anytype,184        operation: *ir.Operation,185    ) void {186        builder.updateBytes(operation.getName().name);187188        builder.updateUsize(operation.getNumAttrs());189        var attrs = operation.getAttrs();190        while (attrs.next()) |attr| {191            builder.updateBytes(attr.name);192            updateAttributeFingerprint(builder, attr.value, self.attribute_frames);193        }194195        builder.updateU64(operation.getNumResults());196        for (operation.results.items) |*result| {197            updateTypeFingerprint(builder, result.type);198            self.updateNumberedValue(builder, result);199        }200201        builder.updateU64(operation.getNumOperands());202        for (operation.operands.items) |operand| {203            self.updateNumberedValue(builder, operand.value);204        }205        builder.updateU64(operation.getNumRegions());206    }207208    fn updateBlock(209        self: *Self,210        builder: anytype,211        block: *ir.Block,212    ) void {213        builder.updateU64(block.getNumArguments());214        for (block.arguments.items) |argument| {215            updateTypeFingerprint(builder, argument.type);216            self.updateNumberedValue(builder, argument);217        }218219        var operation_count: usize = 0;220        var operation_opaque = block.operations.head;221        while (operation_opaque) |operation_ptr| {222            operation_count += 1;223            const operation: *ir.Operation = @ptrCast(@alignCast(operation_ptr));224            operation_opaque = operation.next_op;225        }226        builder.updateUsize(operation_count);227    }228229    fn updateNumberedValue(230        self: *const Self,231        builder: anytype,232        value: *const ir.Value,233    ) void {234        if (self.valueId(value)) |id| {235            builder.updateBool(true);236            builder.updateU64(id);237        } else {238            builder.updateBool(false);239            builder.updateU64(std.math.maxInt(u64));240        }241    }242243    fn requireSteady(self: *const Self) void {244        if (self.phase != .steady) {245            @panic("stable value numbering used outside its steady phase");246        }247    }248};249250comptime {251    alloc_phase.capacity.requireAllocatorExactOwnerShape(StableValueNumbering);252}253254fn updateRegion(builder: anytype, region: *ir.Region) void {255    var block_count: usize = 0;256    var block_opaque = region.blocks.head;257    while (block_opaque) |block_ptr| {258        block_count += 1;259        const block: *ir.Block = @ptrCast(@alignCast(block_ptr));260        block_opaque = block.next;261    }262    builder.updateUsize(block_count);263}264265fn updateTypeFingerprint(builder: anytype, typ: ir.Type) void {266    if (typ.getDialectStorage()) |storage| {267        builder.updateBool(true);268        builder.updateBytes(storage.name);269        builder.updateBytes(storage.param_key);270        return;271    }272    builder.updateBool(false);273    builder.updateU64(@intFromPtr(typ.impl));274}275276fn updateAttributeFingerprint(277    builder: anytype,278    root: ir.Attribute,279    frames: []capacity_model.AttributeFrame,280) void {281    var current: ?ir.Attribute = root;282    var depth: usize = 0;283    while (true) {284        if (current) |attr| {285            builder.updateU64(@backingInt(attr.attr_id));286            builder.updateBytes(attr.abstract.name);287288            if (attr.cast(ir.Attribute.IntegerAttr)) |integer| {289                builder.updateU64(@bitCast(integer.value));290                builder.updateU64(integer.width);291                builder.updateBool(integer.is_signed);292            } else if (attr.cast(ir.Attribute.FloatAttr)) |float| {293                builder.updateU64(@bitCast(float.value));294                builder.updateU64(float.width);295            } else if (attr.cast(ir.Attribute.BoolAttr)) |boolean| {296                builder.updateBool(boolean.value);297            } else if (attr.cast(ir.Attribute.StringAttr)) |string| {298                builder.updateBytes(string.value);299            } else if (attr.cast(ir.Attribute.SymbolRefAttr)) |symbol| {300                builder.updateBytes(symbol.root_reference);301                builder.updateUsize(symbol.nested_references.len);302                for (symbol.nested_references) |nested| builder.updateBytes(nested);303            } else if (attr.cast(ir.Attribute.StringListAttr)) |list| {304                builder.updateUsize(list.values.len);305                for (list.values) |value| builder.updateBytes(value);306            } else if (attr.cast(ir.Attribute.TypeListAttr)) |list| {307                builder.updateUsize(list.values.len);308                for (list.values) |typ| updateTypeFingerprint(builder, typ);309            } else if (attr.cast(ir.Attribute.ArrayAttr)) |array| {310                builder.updateUsize(array.values.len);311                if (array.values.len > 0) {312                    if (depth >= frames.len) {313                        @panic("attribute traversal exceeded inspected depth");314                    }315                    frames[depth] = .{ .values = array.values, .next_index = 1 };316                    depth += 1;317                    current = array.values[0];318                    continue;319                }320            } else if (attr.cast(ir.Attribute.DialectAttr)) |dialect| {321                builder.updateBytes(dialect.payload);322            } else {323                builder.updateU64(@intFromPtr(attr.impl));324            }325        }326327        current = null;328        while (depth > 0) {329            const frame = &frames[depth - 1];330            if (frame.next_index < frame.values.len) {331                current = frame.values[frame.next_index];332                frame.next_index += 1;333                break;334            }335            depth -= 1;336        }337        if (current == null) return;338    }339}340341const TestFingerprintBuilder = struct {342    value: u64 = 14_695_981_039_346_656_037,343344    fn updateBytes(self: *@This(), bytes: []const u8) void {345        self.updateU64(bytes.len);346        self.updateRawBytes(bytes);347    }348349    fn updateRawBytes(self: *@This(), bytes: []const u8) void {350        for (bytes) |byte| {351            self.value ^= byte;352            self.value *%= 1_099_511_628_211;353        }354    }355356    fn updateBool(self: *@This(), value: bool) void {357        self.updateU64(@intFromBool(value));358    }359360    fn updateU64(self: *@This(), value: u64) void {361        var bytes: [8]u8 = undefined;362        std.mem.writeInt(u64, &bytes, value, .little);363        self.updateRawBytes(&bytes);364    }365366    fn updateUsize(self: *@This(), value: usize) void {367        self.updateU64(@intCast(value));368    }369370    fn finish(self: @This()) u64 {371        return self.value;372    }373};374375fn makeNumberingTree(376    context: *ir.Context,377    operation_name: []const u8,378    reverse_operands: bool,379) !*ir.Operation {380    const test_dialect = @import("../../dialects/fixture/root.zig");381    const location = ir.Location.getUnknown();382    const integer_type = try test_dialect.TestDialect.getI64Type(context);383    var region = ir.context.initRegion(context);384    defer region.deinit();385    const block = try region.addBlock();386    const first = try block.addArgument(integer_type, location);387    const second = try block.addArgument(integer_type, location);388    var state = ir.Operation.State.init(operation_name, location);389    state.addOperands(if (reverse_operands) &.{ second, first } else &.{ first, second });390    state.addTypes(&.{integer_type});391    const operation = try context.createOperation(state);392    try block.addOperation(operation);393    var wrapper_state = ir.Operation.State.init("wrapper", location);394    wrapper_state.addRegionBodies(&.{&region});395    return context.createOperation(wrapper_state);396}397398fn numberedFingerprint(allocator: Allocator, operation: *ir.Operation) !u64 {399    const limits = try StableValueNumbering.Limits.inspect(operation);400    var numbering = try StableValueNumbering.init(allocator, limits);401    defer numbering.deinit(allocator);402    try numbering.activate();403    var builder = TestFingerprintBuilder{};404    numbering.updateSubtreeFingerprint(&builder, operation);405    return builder.finish();406}407408fn checkStableValueNumberingInitFailures(409    allocator: Allocator,410    limits: StableValueNumbering.Limits,411) !void {412    var numbering = try StableValueNumbering.init(allocator, limits);413    defer numbering.deinit(allocator);414    try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, numbering.phase);415}416417test "stable value numbering preserves established protocols" {418    const allocator = std.testing.allocator;419    var arena = alloc_arena.Arena.init(allocator);420    defer arena.deinit();421    var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);422    defer context.deinit(arena.allocator());423    try context.allowUnregistered();424425    const first_add = try makeNumberingTree(&context, "test.add", false);426    const second_add = try makeNumberingTree(&context, "test.add", false);427    const first_add_fingerprint = try numberedFingerprint(allocator, first_add);428    const second_add_fingerprint = try numberedFingerprint(allocator, second_add);429    try std.testing.expectEqual(first_add_fingerprint, second_add_fingerprint);430    try std.testing.expectEqual(431        @as(u64, 11_742_538_809_681_872_813),432        first_add_fingerprint,433    );434435    const first_sub = try makeNumberingTree(&context, "test.sub", false);436    const second_sub = try makeNumberingTree(&context, "test.sub", true);437    try std.testing.expectEqual(438        @as(u64, 13_191_181_002_833_531_052),439        try numberedFingerprint(allocator, first_sub),440    );441    try std.testing.expectEqual(442        @as(u64, 13_697_684_465_524_774_060),443        try numberedFingerprint(allocator, second_sub),444    );445}446447test "stable value numbering initialization cleans every allocation failure and retries" {448    comptime {449        @stardustClaim(450            @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_oom_retry"),451            null,452            null,453            null,454            null,455            null,456            null,457        );458    }459460    const allocator = std.testing.allocator;461    var arena = alloc_arena.Arena.init(allocator);462    defer arena.deinit();463    var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);464    defer context.deinit(arena.allocator());465    try context.allowUnregistered();466467    const root = try makeNumberingTree(&context, "test.add", false);468    const leaf = try context.getStringAttr("leaf");469    const inner = try context.getArrayAttr(&.{leaf});470    try root.setAttr("nested", try context.getArrayAttr(&.{inner}));471    const limits = try StableValueNumbering.Limits.inspect(root);472    try std.testing.expect(limits.facts.value_count > 0);473    try std.testing.expect(limits.facts.operation_depth > 1);474    try std.testing.expect(limits.facts.attribute_depth > 1);475476    try std.testing.checkAllAllocationFailures(477        allocator,478        checkStableValueNumberingInitFailures,479        .{limits},480    );481482    var numbering = try StableValueNumbering.init(allocator, limits);483    defer numbering.deinit(allocator);484    try numbering.activate();485    const block: *ir.Block = @ptrCast(@alignCast(root.regions.items[0].blocks.head.?));486    try std.testing.expect(numbering.valueId(block.arguments.items[0]) != null);487    var builder = TestFingerprintBuilder{};488    numbering.updateSubtreeFingerprint(&builder, root);489    _ = builder.finish();490}491492test "stable value numbering rejects reordered definitions with unchanged facts" {493    const allocator = std.testing.allocator;494    var arena = alloc_arena.Arena.init(allocator);495    defer arena.deinit();496    var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);497    defer context.deinit(arena.allocator());498    try context.allowUnregistered();499    const location = ir.Location.getUnknown();500    const integer_type = try context.getDialectTypeFromName("test.i64");501502    var first_state = ir.Operation.State.init("first", location);503    first_state.addTypes(&.{integer_type});504    const first = try context.createOperation(first_state);505    var second_state = ir.Operation.State.init("second", location);506    second_state.addTypes(&.{integer_type});507    const second = try context.createOperation(second_state);508    var region = ir.context.initRegion(&context);509    defer region.deinit();510    const block = try region.addBlock();511    try block.addOperation(first);512    try block.addOperation(second);513    var root_state = ir.Operation.State.init("root", location);514    root_state.addRegionBodies(&.{&region});515    const root = try context.createOperation(root_state);516517    const limits = try StableValueNumbering.Limits.inspect(root);518    var numbering = try StableValueNumbering.init(allocator, limits);519    defer numbering.deinit(allocator);520    try second.moveBefore(first);521    const current = try StableValueNumbering.Limits.inspect(root);522    try std.testing.expect(limits.facts.eql(current.facts));523    try std.testing.expect(!numbering.index.matchesDefinitions(524        root,525        numbering.operation_frames,526    ));527    try std.testing.expectError(error.InputChanged, numbering.activate());528}529530test "stable value numbering repeats overlapping updates after sealing" {531    comptime {532        @stardustClaim(533            @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_overload"),534            null,535            null,536            null,537            null,538            null,539            null,540        );541    }542    comptime {543        @stardustClaim(544            @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_transitive_risk"),545            null,546            null,547            null,548            null,549            null,550            null,551        );552    }553    comptime {554        @stardustClaim(555            @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_foreign_risk"),556            null,557            null,558            null,559            null,560            null,561            null,562        );563    }564565    const allocator = std.testing.allocator;566    var arena = alloc_arena.Arena.init(allocator);567    defer arena.deinit();568    var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);569    defer context.deinit(arena.allocator());570    try context.allowUnregistered();571    const root = try makeNumberingTree(&context, "test.add", false);572    const block_opaque = root.regions.items[0].blocks.head.?;573    const block: *ir.Block = @ptrCast(@alignCast(block_opaque));574    const child_opaque = block.operations.head.?;575    const child: *ir.Operation = @ptrCast(@alignCast(child_opaque));576    const limits = try StableValueNumbering.Limits.inspect(root);577578    var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);579    var maybe_numbering: ?StableValueNumbering = null;580    errdefer {581        if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();582        if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();583        if (maybe_numbering) |*numbering| {584            if (numbering.phase != .teardown) {585                numbering.deinit(phase_allocator.teardownAllocator());586            }587        }588        if (phase_allocator.phase() == .teardown) phase_allocator.deinit();589    }590591    maybe_numbering = try StableValueNumbering.init(592        phase_allocator.initializationAllocator(),593        limits,594    );595    const numbering = &maybe_numbering.?;596    const entries_pointer = numbering.index.entries.ptr;597    const operations_pointer = numbering.operation_frames.ptr;598    const attributes_pointer = numbering.attribute_frames.ptr;599    phase_allocator.seal();600    try numbering.activate();601602    var first = TestFingerprintBuilder{};603    numbering.updateSubtreeFingerprint(&first, child);604    numbering.updateSubtreeFingerprint(&first, root);605    var second = TestFingerprintBuilder{};606    numbering.updateSubtreeFingerprint(&second, child);607    numbering.updateSubtreeFingerprint(&second, root);608    try std.testing.expectEqual(first.finish(), second.finish());609    try std.testing.expectEqual(entries_pointer, numbering.index.entries.ptr);610    try std.testing.expectEqual(operations_pointer, numbering.operation_frames.ptr);611    try std.testing.expectEqual(attributes_pointer, numbering.attribute_frames.ptr);612    try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());613614    phase_allocator.beginTeardown();615    numbering.deinit(phase_allocator.teardownAllocator());616    try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, numbering.phase);617    try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());618    phase_allocator.deinit();619}

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