tiny.choir.StableValueNumbering

1pub const StableValueNumbering = struct {2    pub const claim: alloc_phase.capacity.Declaration = .{3        .source = .{4            .id = "choir.stable_value_numbering",5            .kind = .phase_static,6            .limit_source = .caller,7            .storage = .{8                .covered = &.{9                    .{10                        .id = "valueentry_array_operationframe_array_and_attributeframe_array",11                        .lifetime = .steady,12                        .detail = "ValueEntry array, OperationFrame array, and AttributeFrame array",13                    },14                },15                .excluded = &.{16                    "borrowed mutable IR and every referenced Value, type, and attribute payload",17                    "generic fingerprint builder storage and side effects",18                },19            },20            .capacity = .{21                .inputs = &.{22                    alloc_phase.capacity.bindInput(Limits, "facts_value_count", "facts.value_count"),23                    alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),24                    alloc_phase.capacity.bindInput(Limits, "facts_attribute_depth", "facts.attribute_depth"),25                },26                .type_selectors = &.{27                    alloc_phase.capacity.bindType(capacity_model.ValueEntry, "valueentry"),28                    alloc_phase.capacity.bindType(capacity_model.OperationFrame, "operationframe"),29                    alloc_phase.capacity.bindType(capacity_model.AttributeFrame, "attributeframe"),30                },31                .nodes = &.{32                    .{ .input = 0 },33                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },34                    .{ .input = 1 },35                    .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 1 } } },36                    .{ .input = 2 },37                    .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },38                    .{ .add = .{ .left = 1, .right = 3 } },39                    .{ .add = .{ .left = 6, .right = 5 } },40                },41                .assertions = &.{.{42                    .scope = .closure_total,43                    .measure = .retained,44                    .relation = .exact,45                    .expression = 7,46                }},47            },48            .overload = .{49                .kind = .reject_before_seal,50                .detail = "nesting, arithmetic, OOM, or definition drift rejects before activation; there is no steady exhaustion",51            },52            .risks = .{53                .transitive = .{54                    .status = .open,55                    .detail = "updateSubtreeFingerprint invokes unconstrained anytype builder methods and an indirect inherent-property hook",56                },57                .foreign = .{58                    .status = .open,59                    .detail = "generic builder and property hook implementations may reacquire allocator policy or cross foreign boundaries",60                },61            },62            .obligations = &.{63                .{ .key = "numbering_capacity", .role = .capacity_model },64                .{ .key = "numbering_sealed_repeat_overload", .role = .overload },65                .{ .key = "numbering_sealed_repeat_transitive_risk", .role = .transitive_risk },66                .{ .key = "numbering_sealed_repeat_foreign_risk", .role = .foreign_risk },67                .{ .key = "numbering_oom_retry", .role = .overload },68            },69        },70        .bindings = .{71            .owner = @This(),72            .seal = .{73                .family = alloc_phase.capacity.selector(@This().activate),74                .premise = .{75                    .class = .checked_semantic_fact,76                    .authority = .checker,77                },78            },79            .teardown = .{80                .family = alloc_phase.capacity.selector(@This().deinit),81                .premise = .{82                    .class = .checked_semantic_fact,83                    .authority = .checker,84                },85            },86        },87    };88    phase: alloc_phase.capacity.Phase,89    capacity: Capacity,90    root: *ir.Operation,91    index: index_model.ValueIndex,92    operation_frames: []capacity_model.OperationFrame,93    attribute_frames: []capacity_model.AttributeFrame,9495    pub const Limits = capacity_model.Limits;96    pub const Capacity = capacity_model.Capacity;9798    const Self = @This();99100    pub fn init(allocator: Allocator, limits: Limits) !Self {101        const current = Limits.inspect(limits.root) catch return error.InputChanged;102        if (!limits.facts.eql(current.facts)) return error.InputChanged;103        const derived = try Capacity.derive(limits);104        var index = try index_model.ValueIndex.init(allocator, derived);105        errdefer index.deinit(allocator);106        const operation_frames = try allocator.alloc(107            capacity_model.OperationFrame,108            derived.facts.operation_depth,109        );110        errdefer allocator.free(operation_frames);111        const attribute_frames = try allocator.alloc(112            capacity_model.AttributeFrame,113            derived.facts.attribute_depth,114        );115        errdefer allocator.free(attribute_frames);116        try index.fill(limits.root, operation_frames);117        return .{118            .phase = .initialization,119            .capacity = derived,120            .root = limits.root,121            .index = index,122            .operation_frames = operation_frames,123            .attribute_frames = attribute_frames,124        };125    }126127    pub fn activate(self: *Self) error{ AlreadyActive, InputChanged }!void {128        if (self.phase != .initialization) return error.AlreadyActive;129        const current = Limits.inspect(self.root) catch return error.InputChanged;130        if (!self.capacity.facts.eql(current.facts)) return error.InputChanged;131        if (!self.index.matchesDefinitions(self.root, self.operation_frames)) {132            return error.InputChanged;133        }134        self.phase = .steady;135    }136137    pub fn valueId(self: *const Self, value: *const ir.Value) ?u64 {138        self.requireSteady();139        return self.index.lookup(value);140    }141142    pub fn updateSubtreeFingerprint(143        self: *Self,144        builder: anytype,145        operation: *ir.Operation,146    ) void {147        self.requireSteady();148        if (!self.root.isAncestor(operation)) {149            @panic("stable value numbering subtree is outside its indexed root");150        }151        var iterator = walk.Iterator.init(self.operation_frames, operation);152        while (iterator.next()) |event| switch (event) {153            .operation => |op| self.updateOperation(builder, op),154            .region => |region| updateRegion(builder, region),155            .block => |block| self.updateBlock(builder, block),156        };157    }158159    pub fn deinit(self: *Self, allocator: Allocator) void {160        if (self.phase == .teardown) @panic("stable value numbering teardown is terminal");161        self.phase = .teardown;162        allocator.free(self.attribute_frames);163        allocator.free(self.operation_frames);164        self.index.deinit(allocator);165        self.root = undefined;166        self.operation_frames = undefined;167        self.attribute_frames = undefined;168    }169170    fn updateOperation(171        self: *Self,172        builder: anytype,173        operation: *ir.Operation,174    ) void {175        builder.updateBytes(operation.getName().name);176177        builder.updateUsize(operation.getNumAttrs());178        var attrs = operation.getAttrs();179        while (attrs.next()) |attr| {180            builder.updateBytes(attr.name);181            updateAttributeFingerprint(builder, attr.value, self.attribute_frames);182        }183184        builder.updateU64(operation.getNumResults());185        for (operation.results.items) |*result| {186            updateTypeFingerprint(builder, result.type);187            self.updateNumberedValue(builder, result);188        }189190        builder.updateU64(operation.getNumOperands());191        for (operation.operands.items) |operand| {192            self.updateNumberedValue(builder, operand.value);193        }194        builder.updateU64(operation.getNumRegions());195    }196197    fn updateBlock(198        self: *Self,199        builder: anytype,200        block: *ir.Block,201    ) void {202        builder.updateU64(block.getNumArguments());203        for (block.arguments.items) |argument| {204            updateTypeFingerprint(builder, argument.type);205            self.updateNumberedValue(builder, argument);206        }207208        var operation_count: usize = 0;209        var operation_opaque = block.operations.head;210        while (operation_opaque) |operation_ptr| {211            operation_count += 1;212            const operation: *ir.Operation = @ptrCast(@alignCast(operation_ptr));213            operation_opaque = operation.next_op;214        }215        builder.updateUsize(operation_count);216    }217218    fn updateNumberedValue(219        self: *const Self,220        builder: anytype,221        value: *const ir.Value,222    ) void {223        if (self.valueId(value)) |id| {224            builder.updateBool(true);225            builder.updateU64(id);226        } else {227            builder.updateBool(false);228            builder.updateU64(std.math.maxInt(u64));229        }230    }231232    fn requireSteady(self: *const Self) void {233        if (self.phase != .steady) {234            @panic("stable value numbering used outside its steady phase");235        }236    }237};

1pub const StableValueNumbering = product.StableValueNumbering;