lib/choir/src/passes/cse/storage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_observe = @import("alloc_observe");
3 const alloc_phase = @import("alloc_phase");
4 const ir = @import("../../core/root.zig");
5 const dialects = @import("../../dialects/root.zig");
6
7 const Allocator = std.mem.Allocator;
8 const effects = ir.interfaces.effects;
9
10 const maximum_cse_operation_depth: usize = 256;
11 const cse_table_max_load_percentage: usize = 80;
12 const cse_storage_alignment: usize = @max(@alignOf(u64), @alignOf(usize), @alignOf(effects.Fact));
13 pub const inline_workspace_bytes: usize = 8 * 1024;
14
15 const CseInspectError = error{
16 CapacityOverflow,
17 CountOverflow,
18 NestingLimitExceeded,
19 };
20
21 const CseFacts = struct {
22 operation_depth: usize = 0,
23 peak_candidate_count: usize = 0,
24 peak_effect_records: usize = 0,
25 requires_dominance: bool = false,
26 };
27
28 const CseLimits = struct {
29 facts: CseFacts,
30
31 pub fn inspect(root: *ir.Operation) CseInspectError!CseLimits {
32 var survey = CseSurvey{};
33 survey.facts.peak_candidate_count = try inspectCseOperation(
34 root,
35 1,
36 &survey,
37 );
38 return .{ .facts = survey.facts };
39 }
40 };
41
42 const CseCapacity = struct {
43 facts: CseFacts,
44 slot_count: usize,
45 slot_bytes: usize,
46 insertion_offset: usize,
47 insertion_bytes: usize,
48 effect_offset: usize,
49 working_bytes: usize,
50
51 pub fn derive(limits: CseLimits) error{CapacityOverflow}!CseCapacity {
52 const slot_count = try cseTableSlotCount(
53 limits.facts.peak_candidate_count,
54 );
55 const slot_bytes = std.math.mul(
56 usize,
57 slot_count,
58 @sizeOf(CseSlot),
59 ) catch return error.CapacityOverflow;
60 const insertion_bytes = std.math.mul(
61 usize,
62 limits.facts.peak_candidate_count,
63 @sizeOf(usize),
64 ) catch return error.CapacityOverflow;
65 var cursor: usize = 0;
66 _ = try csePlaceBytes(slot_bytes, @alignOf(CseSlot), &cursor);
67 const insertion_offset = try csePlaceBytes(
68 insertion_bytes,
69 @alignOf(usize),
70 &cursor,
71 );
72 const effect_bytes = std.math.mul(
73 usize,
74 limits.facts.peak_effect_records,
75 @sizeOf(effects.Fact),
76 ) catch return error.CapacityOverflow;
77 const effect_offset = try csePlaceBytes(effect_bytes, @alignOf(effects.Fact), &cursor);
78 return .{
79 .facts = limits.facts,
80 .slot_count = slot_count,
81 .slot_bytes = slot_bytes,
82 .insertion_offset = insertion_offset,
83 .insertion_bytes = insertion_bytes,
84 .effect_offset = effect_offset,
85 .working_bytes = cursor,
86 };
87 }
88 };
89
90 pub const Workspace = struct {
91 pub const claim: alloc_phase.capacity.Declaration = .{
92 .source = .{
93 .id = "choir.cse_workspace",
94 .kind = .phase_static,
95 .limit_source = .caller,
96 .storage = .{
97 .covered = &.{
98 .{
99 .id = "effect_records_bounded_by_declared_contract_capacity",
100 .lifetime = .steady,
101 .detail = "reused fact buffer bounded by arity-derived contract capacity",
102 },
103 .{
104 .id = "scoped_cse_hash_slots_bounded_by_peak_active_candidate_shapes",
105 .lifetime = .steady,
106 .detail = "scoped CSE hash slots bounded by peak active candidate shapes",
107 },
108 .{
109 .id = "lifo_insertion_indices_bounded_by_peak_active_candidate_shapes",
110 .lifetime = .steady,
111 .detail = "LIFO insertion indices bounded by peak active candidate shapes",
112 },
113 },
114 .excluded = &.{
115 "borrowed IR and dominance analysis",
116 },
117 },
118 .capacity = .{
119 .inputs = &.{
120 alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),
121 alloc_phase.capacity.bindInput(Limits, "facts_peak_candidate_count", "facts.peak_candidate_count"),
122 alloc_phase.capacity.bindInput(
123 Limits,
124 "facts_peak_effect_records",
125 "facts.peak_effect_records",
126 ),
127 },
128 .type_selectors = &.{},
129 .nodes = &.{
130 .{ .input = 0 },
131 .{ .input = 1 },
132 .{ .add = .{ .left = 0, .right = 1 } },
133 .{ .input = 2 },
134 .{ .add = .{ .left = 2, .right = 3 } },
135 },
136 .assertions = &.{.{
137 .scope = .closure_total,
138 .measure = .retained,
139 .relation = .upper_bound,
140 .expression = 4,
141 }},
142 },
143 .overload = .{
144 .kind = .reject_before_seal,
145 .detail = "nesting, count arithmetic, capacity arithmetic, or fallback OOM rejects before CSE traversal",
146 },
147 .risks = .{
148 .transitive = .{
149 .status = .witnessed,
150 .detail = "CSE equivalence, result remapping, duplicate erasure, and scoped table mutation use only admitted storage after activation",
151 },
152 .foreign = .{
153 .status = .open,
154 .detail = "the workspace has no visible foreign edge, but foreign-edge closure lacks a machine-checked certificate",
155 },
156 },
157 .obligations = &.{
158 .{ .key = "cse_inline_boundary", .role = .overload },
159 .{ .key = "cse_capacity", .role = .capacity_model },
160 .{ .key = "cse_sealed_reuse_overload", .role = .overload },
161 .{ .key = "cse_sealed_reuse_foreign_risk", .role = .foreign_risk },
162 .{ .key = "cse_oom_retry", .role = .overload },
163 .{ .key = "cse_steady_no_alloc", .role = .transitive_risk },
164 },
165 },
166 .bindings = .{
167 .owner = @This(),
168 .seal = .{
169 .family = alloc_phase.capacity.selector(@This().activate),
170 .premise = .{
171 .class = .checked_semantic_fact,
172 .authority = .checker,
173 },
174 },
175 .teardown = .{
176 .family = alloc_phase.capacity.selector(@This().deinit),
177 .premise = .{
178 .class = .checked_semantic_fact,
179 .authority = .checker,
180 },
181 },
182 },
183 };
184
185 phase: alloc_phase.capacity.Phase,
186 capacity: CseCapacity,
187 bytes: []align(cse_storage_alignment) u8,
188 slots: []CseSlot,
189 insertion_slots: []usize,
190 effect_records: []effects.Fact,
191 insertion_count: usize,
192 active_scope_count: usize,
193
194 pub const Limits = CseLimits;
195 pub const Capacity = CseCapacity;
196
197 pub fn initForRoot(allocator: Allocator, root: *ir.Operation) !Workspace {
198 return init(allocator, try Limits.inspect(root));
199 }
200
201 pub fn init(allocator: Allocator, limits: Limits) !Workspace {
202 const capacity = try Capacity.derive(limits);
203 const bytes = try allocator.alignedAlloc(
204 u8,
205 .fromByteUnits(cse_storage_alignment),
206 capacity.working_bytes,
207 );
208 const slots = cseTypedSlice(
209 CseSlot,
210 bytes,
211 0,
212 capacity.slot_count,
213 );
214 @memset(slots, .{});
215 return .{
216 .phase = .initialization,
217 .capacity = capacity,
218 .bytes = bytes,
219 .slots = slots,
220 .insertion_slots = cseTypedSlice(
221 usize,
222 bytes,
223 capacity.insertion_offset,
224 capacity.facts.peak_candidate_count,
225 ),
226 .insertion_count = 0,
227 .active_scope_count = 0,
228 .effect_records = cseTypedSlice(
229 effects.Fact,
230 bytes,
231 capacity.effect_offset,
232 capacity.facts.peak_effect_records,
233 ),
234 };
235 }
236
237 pub fn activate(self: *Workspace) error{AlreadyActive}!void {
238 if (self.phase != .initialization) return error.AlreadyActive;
239 self.phase = .steady;
240 }
241
242 pub fn requiresDominance(self: *const Workspace) bool {
243 if (self.phase != .initialization) {
244 @panic("CSE dominance admission checked outside initialization");
245 }
246 return self.capacity.facts.requires_dominance;
247 }
248
249 pub fn acquire(self: *Workspace) Table {
250 self.requireSteady();
251 self.active_scope_count = std.math.add(
252 usize,
253 self.active_scope_count,
254 1,
255 ) catch @panic("CSE active scope count overflow after activation");
256 return .{
257 .slots = self.slots,
258 .insertion_slots = self.insertion_slots,
259 .insertion_count = &self.insertion_count,
260 .log_start = self.insertion_count,
261 };
262 }
263
264 pub fn release(self: *Workspace, table: Table) void {
265 self.requireSteady();
266 std.debug.assert(table.slots.ptr == self.slots.ptr);
267 std.debug.assert(table.insertion_slots.ptr == self.insertion_slots.ptr);
268 std.debug.assert(table.insertion_count == &self.insertion_count);
269 var scope = table;
270 scope.clear();
271 std.debug.assert(self.active_scope_count > 0);
272 self.active_scope_count -= 1;
273 }
274
275 pub fn deinit(self: *Workspace, allocator: Allocator) void {
276 if (self.phase == .teardown) @panic("CSE workspace teardown is terminal");
277 std.debug.assert(self.insertion_count == 0);
278 std.debug.assert(self.active_scope_count == 0);
279 self.phase = .teardown;
280 allocator.free(self.bytes);
281 self.bytes = undefined;
282 self.slots = undefined;
283 self.insertion_slots = undefined;
284 self.insertion_count = undefined;
285 self.active_scope_count = undefined;
286 }
287
288 fn requireSteady(self: *const Workspace) void {
289 if (self.phase != .steady) {
290 @panic("CSE workspace used outside its steady phase");
291 }
292 }
293 };
294
295 comptime {
296 alloc_phase.capacity.requireAllocatorExactOwnerShape(Workspace);
297 }
298
299 const CseSlot = struct {
300 key: u64 = 0,
301 op: ?*ir.Operation = null,
302 };
303
304 pub const Table = struct {
305 slots: []CseSlot,
306 insertion_slots: []usize,
307 insertion_count: *usize,
308 log_start: usize,
309
310 pub fn candidates(self: Table, key: u64) CandidateIterator {
311 return CandidateIterator.init(self.slots, key);
312 }
313
314 pub fn add(self: Table, key: u64, op: *ir.Operation) error{CapacityExceeded}!void {
315 if (self.insertion_count.* >= self.insertion_slots.len) {
316 return error.CapacityExceeded;
317 }
318 if (self.slots.len == 0) return error.CapacityExceeded;
319 var index = cseSlotIndex(key, self.slots.len);
320 var remaining = self.slots.len;
321 while (remaining > 0) : (remaining -= 1) {
322 const slot = &self.slots[index];
323 if (slot.op == null) {
324 slot.* = .{
325 .key = key,
326 .op = op,
327 };
328 self.insertion_slots[self.insertion_count.*] = index;
329 self.insertion_count.* += 1;
330 return;
331 }
332 index = (index + 1) & (self.slots.len - 1);
333 }
334 return error.CapacityExceeded;
335 }
336
337 fn clear(self: *Table) void {
338 std.debug.assert(self.insertion_count.* >= self.log_start);
339 while (self.insertion_count.* > self.log_start) {
340 self.insertion_count.* -= 1;
341 const index = self.insertion_slots[self.insertion_count.*];
342 std.debug.assert(self.slots[index].op != null);
343 self.slots[index] = .{};
344 }
345 }
346 };
347
348 pub const CandidateIterator = struct {
349 slots: []const CseSlot,
350 key: u64,
351 index: usize,
352 remaining: usize,
353
354 fn init(slots: []const CseSlot, key: u64) CandidateIterator {
355 return .{
356 .slots = slots,
357 .key = key,
358 .index = if (slots.len == 0) 0 else cseSlotIndex(key, slots.len),
359 .remaining = slots.len,
360 };
361 }
362
363 pub fn next(self: *CandidateIterator) ?*ir.Operation {
364 while (self.remaining > 0) {
365 const slot = self.slots[self.index];
366 self.index = (self.index + 1) & (self.slots.len - 1);
367 self.remaining -= 1;
368 const op = slot.op orelse {
369 self.remaining = 0;
370 return null;
371 };
372 if (slot.key == self.key) return op;
373 }
374 return null;
375 }
376 };
377
378 fn cseSlotIndex(key: u64, slot_count: usize) usize {
379 std.debug.assert(std.math.isPowerOfTwo(slot_count));
380 return @as(usize, @truncate(key)) & (slot_count - 1);
381 }
382
383 fn cseTableSlotCount(candidate_count: usize) error{CapacityOverflow}!usize {
384 if (candidate_count == 0) return 0;
385 const scaled = std.math.mul(usize, candidate_count, 100) catch
386 return error.CapacityOverflow;
387 const minimum = std.math.add(
388 usize,
389 scaled / cse_table_max_load_percentage,
390 1,
391 ) catch return error.CapacityOverflow;
392 return std.math.ceilPowerOfTwo(usize, minimum) catch error.CapacityOverflow;
393 }
394
395 fn csePlaceBytes(
396 byte_count: usize,
397 alignment: usize,
398 cursor: *usize,
399 ) error{CapacityOverflow}!usize {
400 std.debug.assert(std.math.isPowerOfTwo(alignment));
401 const mask = alignment - 1;
402 const padded = std.math.add(usize, cursor.*, mask) catch
403 return error.CapacityOverflow;
404 const offset = padded & ~mask;
405 cursor.* = std.math.add(usize, offset, byte_count) catch
406 return error.CapacityOverflow;
407 return offset;
408 }
409
410 fn cseTypedSlice(
411 comptime T: type,
412 bytes: []align(cse_storage_alignment) u8,
413 offset: usize,
414 count: usize,
415 ) []T {
416 if (count == 0) return &.{};
417 const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
418 const region: []align(@alignOf(T)) u8 = @alignCast(
419 bytes[offset..][0..byte_count],
420 );
421 return std.mem.bytesAsSlice(T, region);
422 }
423
424 const CseSurvey = struct {
425 facts: CseFacts = .{},
426 };
427
428 fn inspectCseOperation(
429 op: *ir.Operation,
430 depth: usize,
431 survey: *CseSurvey,
432 ) CseInspectError!usize {
433 if (depth > maximum_cse_operation_depth) return error.NestingLimitExceeded;
434 survey.facts.operation_depth = @max(survey.facts.operation_depth, depth);
435
436 if (op.regions.items.len == 0) return 0;
437 const child_depth = depth + 1;
438 var peak_candidate_count: usize = 0;
439 for (op.regions.items) |*region| {
440 var active_candidate_count: usize = 0;
441 var region_peak_candidate_count: usize = 0;
442 var candidate_block_count: usize = 0;
443 var block_iter = region.getBlocks();
444 while (block_iter.next()) |block| {
445 var block_has_candidate = false;
446 var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
447 if (current != null) {
448 if (child_depth > maximum_cse_operation_depth) {
449 return error.NestingLimitExceeded;
450 }
451 survey.facts.operation_depth = @max(survey.facts.operation_depth, child_depth);
452 }
453 while (current) |current_op| {
454 const nested_peak_candidate_count = if (current_op.regions.items.len == 0)
455 0
456 else
457 try inspectCseOperation(current_op, child_depth, survey);
458 const nested_active_candidate_count = std.math.add(
459 usize,
460 active_candidate_count,
461 nested_peak_candidate_count,
462 ) catch return error.CapacityOverflow;
463 region_peak_candidate_count = @max(
464 region_peak_candidate_count,
465 nested_active_candidate_count,
466 );
467 if (hasCandidateShape(current_op)) {
468 if (current_op.getInterface(effects.EffectOpInterface)) |vtable| {
469 const count = vtable.capacity.count(
470 current_op.getNumOperands(),
471 current_op.getNumResults(),
472 current_op.getNumRegions(),
473 ) orelse return error.CapacityOverflow;
474 survey.facts.peak_effect_records = @max(
475 survey.facts.peak_effect_records,
476 count,
477 );
478 }
479 block_has_candidate = true;
480 active_candidate_count = std.math.add(usize, active_candidate_count, 1) catch
481 return error.CountOverflow;
482 region_peak_candidate_count = @max(
483 region_peak_candidate_count,
484 active_candidate_count,
485 );
486 }
487 current = current_op.next_op;
488 }
489 if (block_has_candidate) {
490 candidate_block_count = std.math.add(usize, candidate_block_count, 1) catch
491 return error.CountOverflow;
492 }
493 }
494 survey.facts.requires_dominance =
495 survey.facts.requires_dominance or candidate_block_count > 1;
496 peak_candidate_count = @max(peak_candidate_count, region_peak_candidate_count);
497 }
498 return peak_candidate_count;
499 }
500
501 pub fn hasCandidateShape(op: *ir.Operation) bool {
502 return op.regions.items.len == 0 and
503 op.successors.items.len == 0 and
504 op.result_types.len != 0;
505 }
506
507 const testing = std.testing;
508 const test_dialect = @import("../../dialects/fixture/root.zig");
509
510 fn buildTestContext(allocator: Allocator) !ir.Context {
511 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
512 errdefer ctx.deinit(allocator);
513 try test_dialect.registerTestDialect(&ctx);
514 return ctx;
515 }
516
517 const WorkspaceFixture = struct {
518 root: *ir.Operation,
519 outer_region: *ir.Region,
520 nested_region: *ir.Region,
521 sibling_region: *ir.Region,
522 };
523
524 fn appendWorkspaceCandidates(
525 ctx: *ir.Context,
526 block: *ir.Block,
527 candidate_type: ir.Type,
528 count: usize,
529 ) !void {
530 for (0..count) |_| {
531 var state = ir.Operation.State.init(
532 "test.cse_workspace_candidate",
533 ir.Location.getUnknown(),
534 );
535 state.addTypes(&.{candidate_type});
536 try block.addOperation(try ctx.createOperation(state));
537 }
538 }
539
540 fn appendWorkspaceContainer(
541 ctx: *ir.Context,
542 block: *ir.Block,
543 name: []const u8,
544 ) !*ir.Operation {
545 var state = ir.Operation.State.init(name, ir.Location.getUnknown());
546 state.addRegion();
547 const op = try ctx.createOperation(state);
548 try block.addOperation(op);
549 return op;
550 }
551
552 fn buildWorkspaceFixture(ctx: *ir.Context) !WorkspaceFixture {
553 const candidate_type = try test_dialect.TestDialect.getI32Type(ctx);
554 var root_state = ir.Operation.State.init(
555 "test.cse_workspace_root",
556 ir.Location.getUnknown(),
557 );
558 root_state.addRegion();
559 const root = try ctx.createOperation(root_state);
560 const root_region = root.getRegion(0).?;
561 const root_block = try root_region.addBlock();
562
563 const outer = try appendWorkspaceContainer(ctx, root_block, "test.cse_workspace_outer");
564 const outer_region = outer.getRegion(0).?;
565 const outer_block = try outer_region.addBlock();
566 try appendWorkspaceCandidates(ctx, outer_block, candidate_type, 3);
567
568 const nested = try appendWorkspaceContainer(ctx, outer_block, "test.cse_workspace_nested");
569 const nested_region = nested.getRegion(0).?;
570 const nested_block = try nested_region.addBlock();
571 try appendWorkspaceCandidates(ctx, nested_block, candidate_type, 7);
572
573 const sibling = try appendWorkspaceContainer(ctx, root_block, "test.cse_workspace_sibling");
574 const sibling_region = sibling.getRegion(0).?;
575 const sibling_block = try sibling_region.addBlock();
576 try appendWorkspaceCandidates(ctx, sibling_block, candidate_type, 9);
577
578 return .{
579 .root = root,
580 .outer_region = outer_region,
581 .nested_region = nested_region,
582 .sibling_region = sibling_region,
583 };
584 }
585
586 fn addWorkspaceRegionCandidates(
587 table: Table,
588 region: *ir.Region,
589 first_key: u64,
590 ) !usize {
591 var count: usize = 0;
592 var block_iter = region.getBlocks();
593 while (block_iter.next()) |block| {
594 var current: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
595 while (current) |current_op| {
596 if (hasCandidateShape(current_op)) {
597 try table.add(first_key + count, current_op);
598 count += 1;
599 }
600 current = current_op.next_op;
601 }
602 }
603 return count;
604 }
605
606 fn checkWorkspaceInitFailures(allocator: Allocator, root: *ir.Operation) !void {
607 var workspace = try Workspace.initForRoot(allocator, root);
608 defer workspace.deinit(allocator);
609 try testing.expectEqual(alloc_phase.capacity.Phase.initialization, workspace.phase);
610 }
611
612 test "CSE workspace derives peak active candidate capacity" {
613 comptime {
614 @stardustClaim(
615 @import("alloc_phase").capacity.witness(Workspace, "cse_capacity"),
616 null,
617 null,
618 null,
619 null,
620 null,
621 null,
622 );
623 }
624
625 const allocator = testing.allocator;
626 var ctx = try buildTestContext(allocator);
627 defer ctx.deinit(allocator);
628 try ctx.allowUnregistered();
629 const fixture = try buildWorkspaceFixture(&ctx);
630
631 const limits = try Workspace.Limits.inspect(fixture.root);
632 try testing.expectEqual(@as(usize, 4), limits.facts.operation_depth);
633 try testing.expectEqual(@as(usize, 10), limits.facts.peak_candidate_count);
634 try testing.expect(!limits.facts.requires_dominance);
635 try testing.expectEqual(@as(usize, 4), try cseTableSlotCount(3));
636 try testing.expectEqual(@as(usize, 16), try cseTableSlotCount(7));
637 try testing.expectEqual(@as(usize, 16), try cseTableSlotCount(9));
638
639 const capacity = try Workspace.Capacity.derive(limits);
640 try testing.expectEqual(@as(usize, 16), capacity.slot_count);
641 try testing.expectEqual(16 * @sizeOf(CseSlot), capacity.slot_bytes);
642 try testing.expectEqual(16 * @sizeOf(CseSlot), capacity.insertion_offset);
643 try testing.expectEqual(10 * @sizeOf(usize), capacity.insertion_bytes);
644 try testing.expectEqual(
645 16 * @sizeOf(CseSlot) + 10 * @sizeOf(usize),
646 capacity.working_bytes,
647 );
648 try testing.expectError(
649 error.CapacityOverflow,
650 cseTableSlotCount(std.math.maxInt(usize)),
651 );
652
653 var overflowing_limits = limits;
654 overflowing_limits.facts.peak_candidate_count = std.math.maxInt(usize);
655 try testing.expectError(
656 error.CapacityOverflow,
657 Workspace.Capacity.derive(overflowing_limits),
658 );
659
660 const second_outer_block = try fixture.outer_region.addBlock();
661 const i32_type = try test_dialect.TestDialect.getI32Type(&ctx);
662 try appendWorkspaceCandidates(&ctx, second_outer_block, i32_type, 1);
663 const multi_block_limits = try Workspace.Limits.inspect(fixture.root);
664 try testing.expect(multi_block_limits.facts.requires_dominance);
665 }
666
667 test "CSE workspace inline tier ends at exact candidate boundary" {
668 comptime {
669 @stardustClaim(
670 @import("alloc_phase").capacity.witness(Workspace, "cse_inline_boundary"),
671 null,
672 null,
673 null,
674 null,
675 null,
676 null,
677 );
678 }
679
680 const inline_limits = CseLimits{ .facts = .{
681 .operation_depth = 1,
682 .peak_candidate_count = 204,
683 } };
684 const fallback_limits = CseLimits{ .facts = .{
685 .operation_depth = 1,
686 .peak_candidate_count = 205,
687 } };
688 const inline_capacity = try CseCapacity.derive(inline_limits);
689 const fallback_capacity = try CseCapacity.derive(fallback_limits);
690 try testing.expectEqual(@as(usize, 5_728), inline_capacity.working_bytes);
691 try testing.expectEqual(@as(usize, 9_832), fallback_capacity.working_bytes);
692 try testing.expect(inline_capacity.working_bytes <= inline_workspace_bytes);
693 try testing.expect(fallback_capacity.working_bytes > inline_workspace_bytes);
694
695 var inline_failing = testing.FailingAllocator.init(
696 testing.allocator,
697 .{ .fail_index = 0 },
698 );
699 var inline_buffer: [inline_workspace_bytes]u8 = undefined;
700 var inline_fallback = alloc_observe.buffer.First.init(&inline_buffer, inline_failing.allocator());
701 const inline_allocator = inline_fallback.allocator();
702 var inline_workspace = try Workspace.init(inline_allocator, inline_limits);
703 defer inline_workspace.deinit(inline_allocator);
704 try testing.expectEqual(@as(usize, 0), inline_failing.alloc_index);
705
706 var fallback_failing = testing.FailingAllocator.init(
707 testing.allocator,
708 .{ .fail_index = 1 },
709 );
710 var dynamic_buffer: [inline_workspace_bytes]u8 = undefined;
711 var dynamic_fallback = alloc_observe.buffer.First.init(&dynamic_buffer, fallback_failing.allocator());
712 const fallback_allocator = dynamic_fallback.allocator();
713 var fallback_workspace = try Workspace.init(
714 fallback_allocator,
715 fallback_limits,
716 );
717 defer fallback_workspace.deinit(fallback_allocator);
718 try testing.expectEqual(@as(usize, 1), fallback_failing.alloc_index);
719
720 var rejecting = testing.FailingAllocator.init(
721 testing.allocator,
722 .{ .fail_index = 0 },
723 );
724 var rejecting_buffer: [inline_workspace_bytes]u8 = undefined;
725 var rejecting_fallback = alloc_observe.buffer.First.init(&rejecting_buffer, rejecting.allocator());
726 try testing.expectError(
727 error.OutOfMemory,
728 Workspace.init(rejecting_fallback.allocator(), fallback_limits),
729 );
730 }
731
732 test "CSE workspace reuses exact backing across sibling regions after sealing" {
733 comptime {
734 @stardustClaim(
735 @import("alloc_phase").capacity.witness(Workspace, "cse_sealed_reuse_overload"),
736 null,
737 null,
738 null,
739 null,
740 null,
741 null,
742 );
743 }
744 comptime {
745 @stardustClaim(
746 @import("alloc_phase").capacity.witness(Workspace, "cse_sealed_reuse_foreign_risk"),
747 null,
748 null,
749 null,
750 null,
751 null,
752 null,
753 );
754 }
755
756 const allocator = testing.allocator;
757 var ctx = try buildTestContext(allocator);
758 defer ctx.deinit(allocator);
759 try ctx.allowUnregistered();
760 const fixture = try buildWorkspaceFixture(&ctx);
761 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
762 var maybe_workspace: ?Workspace = null;
763 errdefer {
764 if (phase_allocator.phase() == .initialization) {
765 phase_allocator.abortInitialization();
766 }
767 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
768 if (maybe_workspace) |*workspace| {
769 if (workspace.phase != .teardown) {
770 workspace.deinit(phase_allocator.teardownAllocator());
771 }
772 }
773 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
774 }
775
776 maybe_workspace = try Workspace.initForRoot(
777 phase_allocator.initializationAllocator(),
778 fixture.root,
779 );
780 const workspace = &maybe_workspace.?;
781 const base_pointer = workspace.slots.ptr;
782 phase_allocator.seal();
783 try workspace.activate();
784
785 const root_table = workspace.acquire();
786 try testing.expectEqual(@as(usize, 16), root_table.slots.len);
787 try testing.expectEqual(base_pointer, root_table.slots.ptr);
788 const outer_table = workspace.acquire();
789 try testing.expectEqual(base_pointer, outer_table.slots.ptr);
790 try testing.expectEqual(
791 @as(usize, 3),
792 try addWorkspaceRegionCandidates(outer_table, fixture.outer_region, 0),
793 );
794 try testing.expectEqual(@as(usize, 3), workspace.insertion_count);
795 const nested_table = workspace.acquire();
796 try testing.expectEqual(base_pointer, nested_table.slots.ptr);
797 try testing.expectEqual(
798 @as(usize, 7),
799 try addWorkspaceRegionCandidates(nested_table, fixture.nested_region, 8),
800 );
801 try testing.expectEqual(@as(usize, 10), workspace.insertion_count);
802 workspace.release(nested_table);
803 try testing.expectEqual(@as(usize, 3), workspace.insertion_count);
804 workspace.release(outer_table);
805 try testing.expectEqual(@as(usize, 0), workspace.insertion_count);
806
807 const sibling_table = workspace.acquire();
808 try testing.expectEqual(base_pointer, sibling_table.slots.ptr);
809 try testing.expectEqual(
810 @as(usize, 9),
811 try addWorkspaceRegionCandidates(sibling_table, fixture.sibling_region, 16),
812 );
813 try testing.expectEqual(@as(usize, 9), workspace.insertion_count);
814 workspace.release(sibling_table);
815 workspace.release(root_table);
816 try testing.expectEqual(@as(usize, 0), workspace.insertion_count);
817 try testing.expectEqual(@as(usize, 0), workspace.active_scope_count);
818 try testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
819
820 phase_allocator.beginTeardown();
821 workspace.deinit(phase_allocator.teardownAllocator());
822 try testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
823 phase_allocator.deinit();
824 }
825
826 test "CSE workspace initialization is retryable after allocation failure" {
827 comptime {
828 @stardustClaim(
829 @import("alloc_phase").capacity.witness(Workspace, "cse_oom_retry"),
830 null,
831 null,
832 null,
833 null,
834 null,
835 null,
836 );
837 }
838
839 const allocator = testing.allocator;
840 var ctx = try buildTestContext(allocator);
841 defer ctx.deinit(allocator);
842 try ctx.allowUnregistered();
843 const fixture = try buildWorkspaceFixture(&ctx);
844 try testing.checkAllAllocationFailures(
845 allocator,
846 checkWorkspaceInitFailures,
847 .{fixture.root},
848 );
849
850 var workspace = try Workspace.initForRoot(allocator, fixture.root);
851 defer workspace.deinit(allocator);
852 try workspace.activate();
853 }
854
855 test "CSE workspace inspection enforces operation nesting boundary" {
856 const allocator = testing.allocator;
857 var ctx = try buildTestContext(allocator);
858 defer ctx.deinit(allocator);
859 try ctx.allowUnregistered();
860 var root_state = ir.Operation.State.init("test.cse_depth_root", ir.Location.getUnknown());
861 root_state.addRegion();
862 const root = try ctx.createOperation(root_state);
863 var current = root;
864 for (1..maximum_cse_operation_depth) |_| {
865 var child_state = ir.Operation.State.init("test.cse_depth_child", ir.Location.getUnknown());
866 child_state.addRegion();
867 const child = try ctx.createOperation(child_state);
868 const block = try current.getRegion(0).?.addBlock();
869 try block.addOperation(child);
870 current = child;
871 }
872 const limits = try Workspace.Limits.inspect(root);
873 try testing.expectEqual(maximum_cse_operation_depth, limits.facts.operation_depth);
874
875 var one_past_state = ir.Operation.State.init("test.cse_depth_one_past", ir.Location.getUnknown());
876 one_past_state.addRegion();
877 const one_past = try ctx.createOperation(one_past_state);
878 const block = try current.getRegion(0).?.addBlock();
879 try block.addOperation(one_past);
880 try testing.expectError(
881 error.NestingLimitExceeded,
882 Workspace.Limits.inspect(root),
883 );
884 }
885
886 test "CSE table preserves colliding candidate insertion order" {
887 var slots: [4]CseSlot = @splat(.{});
888 var insertion_slots: [3]usize = undefined;
889 var insertion_count: usize = 0;
890 var first: ir.Operation = undefined;
891 var intervening: ir.Operation = undefined;
892 var second: ir.Operation = undefined;
893 const table = Table{
894 .slots = &slots,
895 .insertion_slots = &insertion_slots,
896 .insertion_count = &insertion_count,
897 .log_start = 0,
898 };
899 try table.add(0, &first);
900 try table.add(4, &intervening);
901 try table.add(0, &second);
902
903 var candidates = table.candidates(0);
904 try testing.expectEqual(&first, candidates.next().?);
905 try testing.expectEqual(&second, candidates.next().?);
906 try testing.expect(candidates.next() == null);
907 }
908
909 test "CSE table releases nested collision slots without hiding parent entries" {
910 var slots: [4]CseSlot = @splat(.{});
911 var insertion_slots: [3]usize = undefined;
912 var insertion_count: usize = 0;
913 var first: ir.Operation = undefined;
914 var nested_op: ir.Operation = undefined;
915 var second: ir.Operation = undefined;
916 var outer = Table{
917 .slots = &slots,
918 .insertion_slots = &insertion_slots,
919 .insertion_count = &insertion_count,
920 .log_start = 0,
921 };
922 try outer.add(0, &first);
923 var nested = Table{
924 .slots = &slots,
925 .insertion_slots = &insertion_slots,
926 .insertion_count = &insertion_count,
927 .log_start = insertion_count,
928 };
929 try nested.add(4, &nested_op);
930 nested.clear();
931 try outer.add(8, &second);
932
933 var first_candidates = outer.candidates(0);
934 try testing.expectEqual(&first, first_candidates.next().?);
935 var second_candidates = outer.candidates(8);
936 try testing.expectEqual(&second, second_candidates.next().?);
937 outer.clear();
938 try testing.expectEqual(@as(usize, 0), insertion_count);
939 }