tiny.choir.passes.pass.work

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

1const std = @import("std");2const ir = @import("../../core/root.zig");3const revision = @import("../../product/revision/root.zig");45/// Structural and byte counts read without allocation before producer admission.6pub const Census = struct {7    operations: u64 = 0,8    values: u64 = 0,9    operands: u64 = 0,10    atoms: u64 = 0,11    input_bytes: u64 = 0,1213    pub fn inspect(op: *ir.Operation) !Census {14        var counts: Census = .{};15        _ = try op.walk(.{ .order = .pre_order }, &counts, visit);16        return counts;17    }1819    fn visit(self: *Census, op: *ir.Operation) !ir.Operation.WalkResult {20        self.operations = try add(self.operations, 1);21        self.operands = try add(self.operands, op.getOperandValues().len);22        self.atoms = try add(self.atoms, try add(1, op.getOperandValues().len));23        self.input_bytes = try add(self.input_bytes, op.name.name.len);24        for (op.results.items) |*result| try self.value(result);25        for (op.getOperandValues()) |operand| try self.typeBytes(operand.type);26        var attrs = op.getAttrs();27        while (attrs.next()) |attr| {28            self.atoms = try add(self.atoms, 1);29            self.input_bytes = try add(self.input_bytes, attr.name.len);30            if (attr.value.cast(ir.Attribute.DialectAttr)) |dialect| {31                self.input_bytes = try add(self.input_bytes, dialect.payload.len);32            } else if (attr.value.cast(ir.Attribute.StringAttr)) |string| {33                self.input_bytes = try add(self.input_bytes, string.getValue().len);34            }35        }36        for (op.regions.items) |*region| {37            self.atoms = try add(self.atoms, 1);38            var blocks = region.getBlocks();39            while (blocks.next()) |block| {40                self.atoms = try add(self.atoms, 1);41                for (block.arguments.items) |arg| try self.value(arg);42            }43        }44        return .advance;45    }4647    fn value(self: *Census, item: *ir.Value) !void {48        self.values = try add(self.values, 1);49        self.atoms = try add(self.atoms, 1);50        try self.typeBytes(item.type);51        var use = item.first_use;52        while (use) |edge| : (use = edge.next_use) self.atoms = try add(self.atoms, 1);53    }5455    fn typeBytes(self: *Census, typ: ir.Type) !void {56        if (typ.getDialectTypeName()) |name| {57            self.input_bytes = try add(self.input_bytes, name.len);58        }59        if (typ.getDialectParamKey()) |key| {60            self.input_bytes = try add(self.input_bytes, key.len);61        }62    }63};6465pub const Phase = enum { pass, analysis };6667/// Borrowed failure observations for independently bounded producer storage owners.68pub const AllocationFailure = struct {69    workspace: ?*const bool = null,70    context: ?*const ir.Context = null,7172    pub fn exhausted(self: AllocationFailure) bool {73        if (self.workspace) |failed| {74            if (failed.*) return true;75        }76        if (self.context) |context| return context.exhaustedSegment() != null;77        return false;78    }7980    pub fn classify(self: AllocationFailure, err: anyerror) anyerror {81        return if (self.exhausted()) error.WorkExhausted else err;82    }83};8485pub const Input = struct {86    operation: *ir.Operation,87    state: ?*const anyopaque = null,88    options: ir.ThreadingOptions = .{},89};9091pub const Bounds = struct {92    work: revision.WorkVector,93    workspace: u64 = 0,94    retained_storage: u64 = 0,95};9697/// Estimation reads declared inputs without mutation or allocation. It includes98/// the producer's deterministic traversal, options and scheduling bounds.99pub const Contract = struct {100    identity: revision.record.Version,101    estimate: *const fn (Input) anyerror!Bounds,102};103104/// A missing declaration permits transient work but revokes publication authority.105pub fn begin(106    accounting: ?*revision.AccountingV1,107    phase: Phase,108    contract: ?Contract,109    input: Input,110) !?u32 {111    const ledger = accounting orelse return null;112    if (ledger.view().outcome != .running) return error.TerminalWorkOutcome;113    const declared = contract orelse {114        ledger.missingContract();115        return null;116    };117    const bounds = declared.estimate(input) catch |err| {118        if (err == error.MissingWorkContract) ledger.missingContract();119        ledger.fail(if (err == error.WorkOverflow or err == error.WorkExhausted)120            .exhausted121        else122            .rejected);123        return err;124    };125    if (phase == .analysis and bounds.work.analysis_computations != 1) {126        ledger.missingContract();127        ledger.fail(.rejected);128        return error.MissingWorkContract;129    }130    return try ledger.begin(switch (phase) {131        .pass => .pass,132        .analysis => .analysis,133    }, .{134        .identity = declared.identity,135        .work = bounds.work,136        .workspace = bounds.workspace,137        .retained_storage = bounds.retained_storage,138    });139}140141pub fn add(left: u64, right: u64) error{WorkOverflow}!u64 {142    return std.math.add(u64, left, right) catch return error.WorkOverflow;143}144145pub fn multiply(left: u64, right: u64) error{WorkOverflow}!u64 {146    return std.math.mul(u64, left, right) catch return error.WorkOverflow;147}148149/// Capacity for a default-load-factor std.HashMap on the pinned toolchain.150pub fn hashMapCapacity(entries: u64) !u64 {151    if (entries == 0) return 0;152    const needed = try add(try multiply(entries, 100) / 80, 1);153    if (needed > std.math.maxInt(u32)) return error.WorkOverflow;154    const capacity = std.math.ceilPowerOfTwo(u32, @intCast(needed)) catch155        return error.WorkOverflow;156    if (capacity > std.math.maxInt(u32) / 80) return error.WorkOverflow;157    return @max(8, capacity);158}159160/// Conservative cumulative allocation traffic, including old tables and alignment.161pub fn hashMapGrowth(comptime Key: type, comptime Value: type, entries: u64) !u64 {162    const alignment = @max(@alignOf(usize), @alignOf(Key), @alignOf(Value));163    const slot = 1 + @sizeOf(Key) + @sizeOf(Value);164    const overhead = 4 * @sizeOf(usize) + 3 * alignment;165    return multiply(try multiply(2, try hashMapCapacity(entries)), slot + overhead);166}167168/// Conservative cumulative std.ArrayList traffic, including geometric growth.169pub fn arrayListGrowth(comptime Item: type, entries: u64) !u64 {170    if (entries == 0) return 0;171    const capacity = try add(try multiply(4, entries), 64);172    return multiply(try multiply(4, capacity), @sizeOf(Item) + @alignOf(Item));173}174175test "U0 work container growth bounds cover retained allocations" {176    const Aligned = struct { bytes: [32]u8 align(32) };177    inline for (.{ u8, u64, Aligned }) |Value| {178        for ([_]usize{ 0, 1, 6, 7, 16, 64, 257 }) |count| {179            try checkContainerGrowth(Value, count, true);180            try checkContainerGrowth(Value, count, false);181        }182    }183    try std.testing.expectError(error.WorkOverflow, hashMapCapacity(std.math.maxInt(u64)));184    try std.testing.expectError(error.WorkOverflow, arrayListGrowth(u64, std.math.maxInt(u64)));185}186187fn checkContainerGrowth(comptime Value: type, count: usize, comptime map_case: bool) !void {188    const fixed = @import("alloc_fixed");189    const allowance = if (map_case)190        try hashMapGrowth(u64, Value, count)191    else192        try arrayListGrowth(Value, count);193    const bytes = try std.testing.allocator.alignedAlloc(u8, .@"64", @intCast(allowance));194    defer std.testing.allocator.free(bytes);195    var backing = fixed.Tracked.init(bytes);196    var retained = fixed.Monotonic.init(backing.allocator(), @max(1, bytes.len));197    var map = std.AutoHashMap(u64, Value).init(retained.allocator());198    defer map.deinit();199    var list: std.ArrayList(Value) = .empty;200    defer list.deinit(retained.allocator());201    for (0..count) |index| {202        if (map_case) {203            try map.put(@intCast(index), std.mem.zeroes(Value));204        } else {205            try list.append(retained.allocator(), std.mem.zeroes(Value));206        }207    }208    try std.testing.expectEqual(if (map_case) count else 0, map.count());209    try std.testing.expectEqual(if (map_case) 0 else count, list.items.len);210    try std.testing.expect(map.capacity() <= try hashMapCapacity(count));211    const used = if (retained.current) |*current| fixed.used(current) else 0;212    try std.testing.expect(used <= allowance);213    try std.testing.expect(!backing.exhausted);214}215216test "U0 work census counts an unregistered operation" {217    const allocator = std.testing.allocator;218    var context = try ir.Context.init(allocator, ir.Context.Limits.testing);219    defer context.deinit(allocator);220    try context.allowUnregistered();221    var builder = ir.OperationBuilder.init(&context);222    const name = "work.census";223    const op = try builder.create(ir.Operation.State.init(name, ir.Location.getUnknown()));224    const counts = try Census.inspect(op);225    try std.testing.expectEqual(@as(u64, 1), counts.operations);226    try std.testing.expectEqual(@as(u64, 1), counts.atoms);227    try std.testing.expectEqual(@as(u64, 0), counts.values);228    try std.testing.expectEqual(@as(u64, 0), counts.operands);229    try std.testing.expectEqual(@as(u64, name.len), counts.input_bytes);230}231232test "U0 work census counts ordinary string attribute payload growth" {233    var context = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);234    defer context.deinit(std.testing.allocator);235    try context.allowUnregistered();236    var builder = ir.OperationBuilder.init(&context);237    const op = try builder.create(ir.Operation.State.init("work.string", .unknown));238    const baseline = try Census.inspect(op);239    for ([_]usize{ 0, 1, 31, 128, 1024 }) |length| {240        const payload = try std.testing.allocator.alloc(u8, length);241        defer std.testing.allocator.free(payload);242        @memset(payload, 'x');243        try op.setAttr("target", try context.getStringAttr(payload));244        const counts = try Census.inspect(op);245        try std.testing.expectEqual(246            baseline.input_bytes + "target".len + length,247            counts.input_bytes,248        );249        try std.testing.expectEqual(baseline.atoms + 1, counts.atoms);250        try std.testing.expectEqual(baseline.operations, counts.operations);251    }252}