lib/choir/src/passes/pass/work.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const revision = @import("../../product/revision/root.zig");
4
5 /// Structural and byte counts read without allocation before producer admission.
6 pub const Census = struct {
7 operations: u64 = 0,
8 values: u64 = 0,
9 operands: u64 = 0,
10 atoms: u64 = 0,
11 input_bytes: u64 = 0,
12
13 pub fn inspect(op: *ir.Operation) !Census {
14 var counts: Census = .{};
15 _ = try op.walk(.{ .order = .pre_order }, &counts, visit);
16 return counts;
17 }
18
19 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 }
46
47 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 }
54
55 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 };
64
65 pub const Phase = enum { pass, analysis };
66
67 /// Borrowed failure observations for independently bounded producer storage owners.
68 pub const AllocationFailure = struct {
69 workspace: ?*const bool = null,
70 context: ?*const ir.Context = null,
71
72 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 }
79
80 pub fn classify(self: AllocationFailure, err: anyerror) anyerror {
81 return if (self.exhausted()) error.WorkExhausted else err;
82 }
83 };
84
85 pub const Input = struct {
86 operation: *ir.Operation,
87 state: ?*const anyopaque = null,
88 options: ir.ThreadingOptions = .{},
89 };
90
91 pub const Bounds = struct {
92 work: revision.WorkVector,
93 workspace: u64 = 0,
94 retained_storage: u64 = 0,
95 };
96
97 /// Estimation reads declared inputs without mutation or allocation. It includes
98 /// the producer's deterministic traversal, options and scheduling bounds.
99 pub const Contract = struct {
100 identity: revision.record.Version,
101 estimate: *const fn (Input) anyerror!Bounds,
102 };
103
104 /// A missing declaration permits transient work but revokes publication authority.
105 pub 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 .exhausted
121 else
122 .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 }
140
141 pub fn add(left: u64, right: u64) error{WorkOverflow}!u64 {
142 return std.math.add(u64, left, right) catch return error.WorkOverflow;
143 }
144
145 pub fn multiply(left: u64, right: u64) error{WorkOverflow}!u64 {
146 return std.math.mul(u64, left, right) catch return error.WorkOverflow;
147 }
148
149 /// Capacity for a default-load-factor std.HashMap on the pinned toolchain.
150 pub 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)) catch
155 return error.WorkOverflow;
156 if (capacity > std.math.maxInt(u32) / 80) return error.WorkOverflow;
157 return @max(8, capacity);
158 }
159
160 /// Conservative cumulative allocation traffic, including old tables and alignment.
161 pub 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 }
167
168 /// Conservative cumulative std.ArrayList traffic, including geometric growth.
169 pub 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 }
174
175 test "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 }
186
187 fn 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 else
192 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 }
215
216 test "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 }
231
232 test "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 }