lib/choir/src/backends/regalloc/verify.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const ir = @import("../../core/root.zig");
4 const interval = @import("interval.zig");
5 const position = @import("position.zig");
6 const range = @import("range.zig");
7
8 const Allocator = std.mem.Allocator;
9
10 pub const Error = error{
11 InvalidAllocation,
12 };
13
14 const CapacityError = error{
15 CapacityOverflow,
16 };
17
18 const CandidateIndex = struct {
19 value: *ir.Value,
20 index: usize,
21 };
22
23 fn candidateIndexLessThan(_: void, lhs: CandidateIndex, rhs: CandidateIndex) bool {
24 return @intFromPtr(lhs.value) < @intFromPtr(rhs.value);
25 }
26
27 fn candidateIndexOrder(value: *ir.Value, entry: CandidateIndex) std.math.Order {
28 return std.math.order(@intFromPtr(value), @intFromPtr(entry.value));
29 }
30
31 fn valueLocationRangeOrder(comptime Register: type) type {
32 const Range = range.ValueLocationRange(Register);
33 return struct {
34 fn lessThan(_: void, lhs: Range, rhs: Range) bool {
35 const register_order = switch (@typeInfo(Register)) {
36 .@"enum" => std.math.order(@backingInt(lhs.reg), @backingInt(rhs.reg)),
37 .int => std.math.order(lhs.reg, rhs.reg),
38 else => @compileError("register type must be an integer or enum"),
39 };
40 if (register_order != .eq) return register_order == .lt;
41 const lhs_start = lhs.startPoint().rank();
42 const rhs_start = rhs.startPoint().rank();
43 if (lhs_start != rhs_start) return lhs_start < rhs_start;
44 if (lhs.end != rhs.end) return lhs.end < rhs.end;
45 return @backingInt(lhs.end_phase) < @backingInt(rhs.end_phase);
46 }
47 };
48 }
49
50 fn VerificationLimits(comptime Register: type, comptime Mask: type) type {
51 return struct {
52 ranges: []const range.ValueLocationRange(Register),
53 candidates: []const interval.Candidate(Register, Mask),
54 fixed_positions: interval.FixedPositionIndex(Register),
55 };
56 }
57
58 fn VerificationCapacity(comptime Register: type, comptime Mask: type) type {
59 const Limits = VerificationLimits(Register, Mask);
60 const Range = range.ValueLocationRange(Register);
61 return struct {
62 candidate_count: usize,
63 range_count: usize,
64 candidate_index_bytes: usize,
65 ordered_range_bytes: usize,
66 working_bytes: usize,
67
68 const Self = @This();
69
70 pub fn derive(limits: Limits) CapacityError!Self {
71 return deriveCounts(limits.candidates.len, limits.ranges.len);
72 }
73
74 fn deriveCounts(candidate_count: usize, range_count: usize) CapacityError!Self {
75 const candidate_index_bytes = std.math.mul(
76 usize,
77 candidate_count,
78 @sizeOf(CandidateIndex),
79 ) catch return error.CapacityOverflow;
80 const ordered_range_bytes = std.math.mul(
81 usize,
82 range_count,
83 @sizeOf(Range),
84 ) catch return error.CapacityOverflow;
85 const working_bytes = std.math.add(
86 usize,
87 candidate_index_bytes,
88 ordered_range_bytes,
89 ) catch return error.CapacityOverflow;
90 return .{
91 .candidate_count = candidate_count,
92 .range_count = range_count,
93 .candidate_index_bytes = candidate_index_bytes,
94 .ordered_range_bytes = ordered_range_bytes,
95 .working_bytes = working_bytes,
96 };
97 }
98 };
99 }
100
101 fn verifyOrderedRangeInterference(
102 comptime Register: type,
103 ordered: []const range.ValueLocationRange(Register),
104 ) Error!void {
105 const Range = range.ValueLocationRange(Register);
106 var active: ?Range = null;
107 for (ordered) |entry| {
108 std.debug.assert(entry.start < entry.end);
109 const current = active orelse {
110 active = entry;
111 continue;
112 };
113 if (current.reg != entry.reg) {
114 active = entry;
115 continue;
116 }
117 const overlaps = current.endPoint().rank() >= entry.startPoint().rank();
118 if (overlaps and current.value != entry.value) return error.InvalidAllocation;
119 if (!overlaps or current.endPoint().rank() < entry.endPoint().rank()) active = entry;
120 }
121 }
122
123 fn initAllocationVerifier(
124 comptime Register: type,
125 comptime Mask: type,
126 comptime Owner: type,
127 allocator: Allocator,
128 limits: Owner.Limits,
129 ) !Owner {
130 const Range = range.ValueLocationRange(Register);
131 const capacity = try Owner.Capacity.derive(limits);
132 const candidate_indices = try allocator.alloc(
133 CandidateIndex,
134 capacity.candidate_count,
135 );
136 errdefer allocator.free(candidate_indices);
137 for (limits.candidates, 0..) |candidate, index| {
138 candidate_indices[index] = .{ .value = candidate.value, .index = index };
139 }
140 std.sort.heap(CandidateIndex, candidate_indices, {}, candidateIndexLessThan);
141
142 const ordered_ranges = try allocator.dupe(Range, limits.ranges);
143 errdefer allocator.free(ordered_ranges);
144 std.sort.heap(
145 Range,
146 ordered_ranges,
147 {},
148 valueLocationRangeOrder(Register).lessThan,
149 );
150
151 std.debug.assert(candidate_indices.len == capacity.candidate_count);
152 std.debug.assert(ordered_ranges.len == capacity.range_count);
153 _ = Mask;
154 return .{
155 .phase = .initialization,
156 .capacity = capacity,
157 .candidate_indices = candidate_indices,
158 .ordered_ranges = ordered_ranges,
159 .candidates = limits.candidates,
160 .fixed_positions = limits.fixed_positions,
161 };
162 }
163
164 fn activateAllocationVerifier(comptime Owner: type, self: *Owner) error{AlreadyActive}!void {
165 if (self.phase != .initialization) return error.AlreadyActive;
166 self.phase = .steady;
167 }
168
169 fn deinitAllocationVerifier(comptime Owner: type, self: *Owner, allocator: Allocator) void {
170 if (self.phase == .teardown) {
171 @panic("allocation verifier teardown is terminal");
172 }
173 self.phase = .teardown;
174 allocator.free(self.ordered_ranges);
175 allocator.free(self.candidate_indices);
176 self.ordered_ranges = undefined;
177 self.candidate_indices = undefined;
178 }
179
180 fn candidateForValue(
181 comptime Register: type,
182 comptime Mask: type,
183 comptime Owner: type,
184 self: *const Owner,
185 value: *ir.Value,
186 ) ?interval.Candidate(Register, Mask) {
187 const candidate_index = std.sort.binarySearch(
188 CandidateIndex,
189 self.candidate_indices,
190 value,
191 candidateIndexOrder,
192 ) orelse return null;
193 return self.candidates[self.candidate_indices[candidate_index].index];
194 }
195
196 fn verifyCandidateIndex(comptime Owner: type, self: *const Owner) Error!void {
197 if (self.candidate_indices.len < 2) return;
198 for (
199 self.candidate_indices[1..],
200 self.candidate_indices[0 .. self.candidate_indices.len - 1],
201 ) |current, previous| {
202 if (current.value == previous.value) return error.InvalidAllocation;
203 }
204 }
205
206 fn verifyRangeCandidates(
207 comptime Register: type,
208 comptime Mask: type,
209 comptime Owner: type,
210 self: *const Owner,
211 ) Error!void {
212 for (self.ordered_ranges) |entry| {
213 if (entry.start >= entry.end) return error.InvalidAllocation;
214 if (entry.startPoint().rank() > entry.endPoint().rank()) {
215 return error.InvalidAllocation;
216 }
217 const candidate = candidateForValue(Register, Mask, Owner, self, entry.value) orelse
218 return error.InvalidAllocation;
219 if (!candidate.containsPoint(entry.startPoint())) return error.InvalidAllocation;
220 if (!candidate.containsPoint(entry.endPoint())) return error.InvalidAllocation;
221 }
222 }
223
224 fn verifyFixedPositions(
225 comptime Register: type,
226 comptime Mask: type,
227 comptime Owner: type,
228 self: *const Owner,
229 ) Error!void {
230 for (self.ordered_ranges) |entry| {
231 const candidate = candidateForValue(Register, Mask, Owner, self, entry.value) orelse
232 return error.InvalidAllocation;
233 for (self.fixed_positions.between(
234 entry.reg,
235 entry.startPoint(),
236 entry.endPoint(),
237 )) |fixed| {
238 switch (fixed.kind) {
239 .source, .use => continue,
240 .scratch_use, .def, .clobber => {},
241 }
242 if (!candidate.ownsFixedPosition(fixed)) return error.InvalidAllocation;
243 }
244 }
245 }
246
247 fn verifyAllocationVerifier(
248 comptime Register: type,
249 comptime Mask: type,
250 comptime Owner: type,
251 self: *const Owner,
252 ) Error!void {
253 if (self.phase != .steady) {
254 @panic("allocation verifier used outside its steady phase");
255 }
256 std.debug.assert(self.candidate_indices.len == self.capacity.candidate_count);
257 std.debug.assert(self.ordered_ranges.len == self.capacity.range_count);
258 try verifyCandidateIndex(Owner, self);
259 try verifyRangeCandidates(Register, Mask, Owner, self);
260 try verifyOrderedRangeInterference(Register, self.ordered_ranges);
261 try verifyFixedPositions(Register, Mask, Owner, self);
262 }
263
264 fn allocationVerifierType(comptime Register: type, comptime Mask: type) type {
265 const Candidate = interval.Candidate(Register, Mask);
266 const CapacityType = VerificationCapacity(Register, Mask);
267 const FixedPositionIndex = interval.FixedPositionIndex(Register);
268 const LimitsType = VerificationLimits(Register, Mask);
269 const Range = range.ValueLocationRange(Register);
270 return struct {
271 pub const claim: alloc_phase.capacity.Declaration = .{
272 .source = .{
273 .id = "choir.allocation_verifier",
274 .kind = .phase_static,
275 .limit_source = .caller,
276 .storage = .{
277 .covered = &.{
278 .{
279 .id = "sorted_candidateindex_entries_and_duplicated_ordere_0d17418499cc",
280 .lifetime = .steady,
281 .detail = "sorted CandidateIndex entries and duplicated ordered Range entries",
282 },
283 },
284 .excluded = &.{
285 "borrowed candidate records and use-position backing",
286 "borrowed fixed-position records and register spans",
287 "borrowed IR Value pointees and target emitter output",
288 },
289 },
290 .capacity = .{
291 .inputs = &.{},
292 .type_selectors = &.{},
293 .nodes = &.{
294 .{ .constant = 0 },
295 },
296 .assertions = &.{.{
297 .scope = .closure_total,
298 .measure = .retained,
299 .relation = .exact,
300 .expression = 0,
301 }},
302 },
303 .overload = .{
304 .kind = .reject_before_seal,
305 .detail = "capacity overflow or OOM rejects before steady verification; invalid allocations remain an explicit steady semantic error, and no steady exhaustion exists",
306 },
307 .risks = .{
308 .transitive = .{
309 .status = .open,
310 .detail = "the source-reviewed helper chain is clean but current tooling cannot close comptime generic calls and std binary search",
311 },
312 .foreign = .{
313 .status = .open,
314 .detail = "no foreign edge is visible in the reviewed sources, but the transitive machine certificate is incomplete",
315 },
316 },
317 .obligations = &.{
318 .{ .key = "verifier_capacity_capacity_model", .role = .capacity_model },
319 .{ .key = "verifier_capacity_overload", .role = .overload },
320 .{ .key = "verifier_oom_retry", .role = .overload },
321 .{ .key = "verifier_sealed_valid_transitive_risk", .role = .transitive_risk },
322 .{ .key = "verifier_sealed_valid_foreign_risk", .role = .foreign_risk },
323 .{ .key = "verifier_sealed_invalid_overload", .role = .overload },
324 .{ .key = "verifier_sealed_invalid_transitive_risk", .role = .transitive_risk },
325 },
326 },
327 .bindings = .{
328 .owner = @This(),
329 .seal = .{
330 .family = alloc_phase.capacity.selector(@This().activate),
331 .premise = .{
332 .class = .checked_semantic_fact,
333 .authority = .checker,
334 },
335 },
336 .teardown = .{
337 .family = alloc_phase.capacity.selector(@This().deinit),
338 .premise = .{
339 .class = .checked_semantic_fact,
340 .authority = .checker,
341 },
342 },
343 },
344 };
345 phase: alloc_phase.capacity.Phase,
346 capacity: Capacity,
347 candidate_indices: []CandidateIndex,
348 ordered_ranges: []Range,
349 candidates: []const Candidate,
350 fixed_positions: FixedPositionIndex,
351
352 pub const Limits: type = LimitsType;
353 pub const Capacity: type = CapacityType;
354
355 const Self = @This();
356
357 pub fn init(allocator: Allocator, limits: Limits) !Self {
358 return initAllocationVerifier(Register, Mask, Self, allocator, limits);
359 }
360
361 pub fn activate(self: *Self) error{AlreadyActive}!void {
362 return activateAllocationVerifier(Self, self);
363 }
364
365 pub fn verify(self: *const Self) Error!void {
366 return verifyAllocationVerifier(Register, Mask, Self, self);
367 }
368
369 pub fn deinit(self: *Self, allocator: Allocator) void {
370 deinitAllocationVerifier(Self, self, allocator);
371 }
372 };
373 }
374
375 pub fn AllocationVerifier(comptime Register: type, comptime Mask: type) type {
376 const Verifier = allocationVerifierType(Register, Mask);
377 comptime alloc_phase.capacity.requireAllocatorExactOwnerShape(Verifier);
378 return Verifier;
379 }
380
381 const TestVerifier = AllocationVerifier(u8, u8);
382 const TestCandidate = interval.Candidate(u8, u8);
383 const TestRange = range.ValueLocationRange(u8);
384
385 const VerificationFixture = struct {
386 owner: u8,
387 values: [2]ir.Value,
388 candidates: [2]TestCandidate,
389 ranges: [3]TestRange,
390
391 fn init(self: *@This()) void {
392 self.owner = 0;
393 self.values = .{
394 .{
395 .kind = .{ .op_result = .{ .owner = &self.owner, .result_number = 0 } },
396 .type = undefined,
397 .id = 0,
398 },
399 .{
400 .kind = .{ .op_result = .{ .owner = &self.owner, .result_number = 1 } },
401 .type = undefined,
402 .id = 1,
403 },
404 };
405 self.candidates = .{
406 .{
407 .value = &self.values[0],
408 .range = .{ .start = 0, .end = 2, .end_phase = .definition },
409 .use_positions = .empty,
410 .definition = .{
411 .point = position.Point.definition(0),
412 .requirement = .any,
413 .source = .any,
414 },
415 .order = 0,
416 .is_constant = false,
417 },
418 .{
419 .value = &self.values[1],
420 .range = .{ .start = 1, .end = 3, .end_phase = .definition },
421 .use_positions = .empty,
422 .definition = .{
423 .point = position.Point.definition(1),
424 .requirement = .any,
425 .source = .any,
426 },
427 .order = 1,
428 .is_constant = false,
429 },
430 };
431 self.ranges = .{
432 .{ .value = &self.values[1], .start = 2, .end = 3, .reg = 1 },
433 .{
434 .value = &self.values[0],
435 .start = 0,
436 .end = 2,
437 .reg = 1,
438 .end_phase = .source,
439 },
440 .{ .value = &self.values[1], .start = 1, .end = 4, .reg = 1 },
441 };
442 }
443
444 fn limits(self: *const @This()) TestVerifier.Limits {
445 return .{
446 .ranges = &self.ranges,
447 .candidates = &self.candidates,
448 .fixed_positions = interval.FixedPositionIndex(u8).empty(),
449 };
450 }
451 };
452
453 const VerifierSnapshot = struct {
454 phase: alloc_phase.capacity.Phase,
455 capacity: TestVerifier.Capacity,
456 candidate_indices_pointer: [*]CandidateIndex,
457 candidate_indices_length: usize,
458 ordered_ranges_pointer: [*]TestRange,
459 ordered_ranges_length: usize,
460 };
461
462 fn verifierSnapshot(verifier: *const TestVerifier) VerifierSnapshot {
463 return .{
464 .phase = verifier.phase,
465 .capacity = verifier.capacity,
466 .candidate_indices_pointer = verifier.candidate_indices.ptr,
467 .candidate_indices_length = verifier.candidate_indices.len,
468 .ordered_ranges_pointer = verifier.ordered_ranges.ptr,
469 .ordered_ranges_length = verifier.ordered_ranges.len,
470 };
471 }
472
473 fn checkVerifierInitAllocationFailures(
474 allocator: Allocator,
475 limits: TestVerifier.Limits,
476 ) !void {
477 var verifier = try TestVerifier.init(allocator, limits);
478 defer verifier.deinit(allocator);
479 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, verifier.phase);
480 }
481
482 fn verifyTestAllocation(
483 ranges: []const range.ValueLocationRange(u8),
484 candidates: []const interval.Candidate(u8, u8),
485 fixed_positions: interval.FixedPositionIndex(u8),
486 ) !void {
487 var verifier = try TestVerifier.init(std.testing.allocator, .{
488 .ranges = ranges,
489 .candidates = candidates,
490 .fixed_positions = fixed_positions,
491 });
492 defer verifier.deinit(std.testing.allocator);
493 try verifier.activate();
494 try verifier.verify();
495 }
496
497 fn verifyTestInterference(ranges: []range.ValueLocationRange(u8)) Error!void {
498 std.sort.heap(
499 range.ValueLocationRange(u8),
500 ranges,
501 {},
502 valueLocationRangeOrder(u8).lessThan,
503 );
504 try verifyOrderedRangeInterference(u8, ranges);
505 }
506
507 test "allocation verifier derives exact typed working capacity" {
508 comptime {
509 @stardustClaim(
510 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_capacity_capacity_model"),
511 null,
512 null,
513 null,
514 null,
515 null,
516 null,
517 );
518 }
519 comptime {
520 @stardustClaim(
521 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_capacity_overload"),
522 null,
523 null,
524 null,
525 null,
526 null,
527 null,
528 );
529 }
530
531 for (0..9) |candidate_count| {
532 for (0..9) |range_count| {
533 const capacity = try TestVerifier.Capacity.deriveCounts(
534 candidate_count,
535 range_count,
536 );
537 const candidate_bytes = candidate_count * @sizeOf(CandidateIndex);
538 const range_bytes = range_count * @sizeOf(TestRange);
539 try std.testing.expectEqual(candidate_count, capacity.candidate_count);
540 try std.testing.expectEqual(range_count, capacity.range_count);
541 try std.testing.expectEqual(candidate_bytes, capacity.candidate_index_bytes);
542 try std.testing.expectEqual(range_bytes, capacity.ordered_range_bytes);
543 try std.testing.expectEqual(candidate_bytes + range_bytes, capacity.working_bytes);
544 }
545 }
546
547 const maximum = std.math.maxInt(usize);
548 try std.testing.expectError(
549 error.CapacityOverflow,
550 TestVerifier.Capacity.deriveCounts(maximum / @sizeOf(CandidateIndex) + 1, 0),
551 );
552 try std.testing.expectError(
553 error.CapacityOverflow,
554 TestVerifier.Capacity.deriveCounts(0, maximum / @sizeOf(TestRange) + 1),
555 );
556 try std.testing.expectError(
557 error.CapacityOverflow,
558 TestVerifier.Capacity.deriveCounts(maximum / @sizeOf(CandidateIndex), 1),
559 );
560 }
561
562 test "allocation verifier accepts an empty exact job" {
563 var verifier = try TestVerifier.init(std.testing.allocator, .{
564 .ranges = &.{},
565 .candidates = &.{},
566 .fixed_positions = interval.FixedPositionIndex(u8).empty(),
567 });
568 defer verifier.deinit(std.testing.allocator);
569 try verifier.activate();
570 try verifier.verify();
571 try std.testing.expectEqual(@as(usize, 0), verifier.capacity.working_bytes);
572 }
573
574 test "allocation verifier initialization is retryable after every allocation failure" {
575 comptime {
576 @stardustClaim(
577 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_oom_retry"),
578 null,
579 null,
580 null,
581 null,
582 null,
583 null,
584 );
585 }
586
587 var fixture: VerificationFixture = undefined;
588 fixture.init();
589 try std.testing.checkAllAllocationFailures(
590 std.testing.allocator,
591 checkVerifierInitAllocationFailures,
592 .{fixture.limits()},
593 );
594
595 var verifier = try TestVerifier.init(std.testing.allocator, fixture.limits());
596 defer verifier.deinit(std.testing.allocator);
597 try verifier.activate();
598 try verifier.verify();
599 }
600
601 test "allocation verifier rejects duplicate and empty semantic input after activation" {
602 var fixture: VerificationFixture = undefined;
603 fixture.init();
604 fixture.candidates[1].value = fixture.candidates[0].value;
605 try std.testing.expectError(
606 error.InvalidAllocation,
607 verifyTestAllocation(
608 &fixture.ranges,
609 &fixture.candidates,
610 interval.FixedPositionIndex(u8).empty(),
611 ),
612 );
613
614 fixture.init();
615 fixture.ranges[0].end = fixture.ranges[0].start;
616 try std.testing.expectError(
617 error.InvalidAllocation,
618 verifyTestAllocation(
619 &fixture.ranges,
620 &fixture.candidates,
621 interval.FixedPositionIndex(u8).empty(),
622 ),
623 );
624
625 fixture.init();
626 fixture.ranges[0] = .{
627 .value = &fixture.values[0],
628 .start = 1,
629 .end = 2,
630 .reg = 2,
631 .end_phase = .source,
632 };
633 try std.testing.expectError(
634 error.InvalidAllocation,
635 verifyTestAllocation(
636 &fixture.ranges,
637 &fixture.candidates,
638 interval.FixedPositionIndex(u8).empty(),
639 ),
640 );
641 }
642
643 test "allocation verifier is sealed before its first valid verification" {
644 comptime {
645 @stardustClaim(
646 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_sealed_valid_transitive_risk"),
647 null,
648 null,
649 null,
650 null,
651 null,
652 null,
653 );
654 }
655 comptime {
656 @stardustClaim(
657 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_sealed_valid_foreign_risk"),
658 null,
659 null,
660 null,
661 null,
662 null,
663 null,
664 );
665 }
666
667 var fixture: VerificationFixture = undefined;
668 fixture.init();
669 const candidates_before = fixture.candidates;
670 const ranges_before = fixture.ranges;
671
672 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);
673 var maybe_verifier: ?TestVerifier = null;
674 errdefer {
675 if (phase_allocator.phase() == .initialization) {
676 phase_allocator.abortInitialization();
677 }
678 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
679 if (maybe_verifier) |*verifier| {
680 if (verifier.phase != .teardown) {
681 verifier.deinit(phase_allocator.teardownAllocator());
682 }
683 }
684 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
685 }
686
687 maybe_verifier = try TestVerifier.init(
688 phase_allocator.initializationAllocator(),
689 fixture.limits(),
690 );
691 const verifier = &maybe_verifier.?;
692 const initialized = verifierSnapshot(verifier);
693 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, initialized.phase);
694 try std.testing.expectEqual(@as(usize, 2), initialized.capacity.candidate_count);
695 try std.testing.expectEqual(@as(usize, 3), initialized.capacity.range_count);
696
697 phase_allocator.seal();
698 try verifier.activate();
699 try verifier.verify();
700 try verifier.verify();
701
702 const verified = verifierSnapshot(verifier);
703 try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, verified.phase);
704 try std.testing.expectEqual(initialized.capacity, verified.capacity);
705 try std.testing.expectEqual(
706 initialized.candidate_indices_pointer,
707 verified.candidate_indices_pointer,
708 );
709 try std.testing.expectEqual(
710 initialized.candidate_indices_length,
711 verified.candidate_indices_length,
712 );
713 try std.testing.expectEqual(
714 initialized.ordered_ranges_pointer,
715 verified.ordered_ranges_pointer,
716 );
717 try std.testing.expectEqual(
718 initialized.ordered_ranges_length,
719 verified.ordered_ranges_length,
720 );
721 try std.testing.expectEqual(candidates_before, fixture.candidates);
722 try std.testing.expectEqual(ranges_before, fixture.ranges);
723 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
724
725 phase_allocator.beginTeardown();
726 verifier.deinit(phase_allocator.teardownAllocator());
727 try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, verifier.phase);
728 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
729 phase_allocator.deinit();
730 }
731
732 test "allocation verifier is sealed before its first invalid verification" {
733 comptime {
734 @stardustClaim(
735 @import("alloc_phase").capacity.witness(TestVerifier, "verifier_sealed_invalid_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(TestVerifier, "verifier_sealed_invalid_transitive_risk"),
747 null,
748 null,
749 null,
750 null,
751 null,
752 null,
753 );
754 }
755
756 var fixture: VerificationFixture = undefined;
757 fixture.init();
758 fixture.ranges[1].end_phase = .definition;
759
760 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);
761 var maybe_verifier: ?TestVerifier = null;
762 errdefer {
763 if (phase_allocator.phase() == .initialization) {
764 phase_allocator.abortInitialization();
765 }
766 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
767 if (maybe_verifier) |*verifier| {
768 if (verifier.phase != .teardown) {
769 verifier.deinit(phase_allocator.teardownAllocator());
770 }
771 }
772 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
773 }
774
775 maybe_verifier = try TestVerifier.init(
776 phase_allocator.initializationAllocator(),
777 fixture.limits(),
778 );
779 const verifier = &maybe_verifier.?;
780 const initialized = verifierSnapshot(verifier);
781 phase_allocator.seal();
782 try verifier.activate();
783 try std.testing.expectError(error.InvalidAllocation, verifier.verify());
784 try std.testing.expectEqual(initialized.capacity, verifier.capacity);
785 try std.testing.expectEqual(
786 initialized.candidate_indices_pointer,
787 verifier.candidate_indices.ptr,
788 );
789 try std.testing.expectEqual(
790 initialized.candidate_indices_length,
791 verifier.candidate_indices.len,
792 );
793 try std.testing.expectEqual(initialized.ordered_ranges_pointer, verifier.ordered_ranges.ptr);
794 try std.testing.expectEqual(initialized.ordered_ranges_length, verifier.ordered_ranges.len);
795 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
796
797 phase_allocator.beginTeardown();
798 verifier.deinit(phase_allocator.teardownAllocator());
799 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
800 phase_allocator.deinit();
801 }
802
803 test "allocation verifier rejects ranges without candidate ownership" {
804 var owner: u8 = 0;
805 var value = ir.Value{
806 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
807 .type = undefined,
808 .id = 0,
809 };
810
811 const Range = range.ValueLocationRange(u8);
812 const ranges = [_]Range{.{
813 .value = &value,
814 .start = 1,
815 .end = 2,
816 .reg = 1,
817 }};
818
819 try std.testing.expectError(
820 error.InvalidAllocation,
821 verifyTestAllocation(&ranges, &.{}, interval.FixedPositionIndex(u8).empty()),
822 );
823 }
824
825 test "allocation verifier rejects ranges outside candidate intervals" {
826 var owner: u8 = 0;
827 var value = ir.Value{
828 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
829 .type = undefined,
830 .id = 0,
831 };
832
833 const Candidate = interval.Candidate(u8, u8);
834 const Range = range.ValueLocationRange(u8);
835 const candidates = [_]Candidate{.{
836 .value = &value,
837 .range = .{ .start = 1, .end = 1, .end_phase = .definition },
838 .use_positions = .empty,
839 .definition = .{
840 .point = position.Point.definition(1),
841 .requirement = .any,
842 .source = .any,
843 },
844 .order = 0,
845 .is_constant = false,
846 }};
847 const ranges = [_]Range{.{
848 .value = &value,
849 .start = 0,
850 .end = 2,
851 .reg = 1,
852 }};
853
854 try std.testing.expectError(
855 error.InvalidAllocation,
856 verifyTestAllocation(
857 &ranges,
858 &candidates,
859 interval.FixedPositionIndex(u8).empty(),
860 ),
861 );
862 }
863
864 test "allocation verifier accepts owned noninterfering ranges" {
865 var owner: u8 = 0;
866 var value = ir.Value{
867 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
868 .type = undefined,
869 .id = 0,
870 };
871 var other = ir.Value{
872 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },
873 .type = undefined,
874 .id = 1,
875 };
876
877 const Candidate = interval.Candidate(u8, u8);
878 const Range = range.ValueLocationRange(u8);
879 const candidates = [_]Candidate{
880 .{
881 .value = &value,
882 .range = .{ .start = 1, .end = 1, .end_phase = .definition },
883 .use_positions = .empty,
884 .definition = .{
885 .point = position.Point.definition(1),
886 .requirement = .any,
887 .source = .any,
888 },
889 .order = 0,
890 .is_constant = false,
891 },
892 .{
893 .value = &other,
894 .range = .{ .start = 2, .end = 2, .end_phase = .definition },
895 .use_positions = .empty,
896 .definition = .{
897 .point = position.Point.definition(2),
898 .requirement = .any,
899 .source = .any,
900 },
901 .order = 1,
902 .is_constant = false,
903 },
904 };
905 const ranges = [_]Range{
906 .{
907 .value = &value,
908 .start = 1,
909 .end = 2,
910 .reg = 1,
911 },
912 .{
913 .value = &other,
914 .start = 2,
915 .end = 3,
916 .reg = 1,
917 },
918 };
919
920 try verifyTestAllocation(
921 &ranges,
922 &candidates,
923 interval.FixedPositionIndex(u8).empty(),
924 );
925 }
926
927 test "interference verifier retains the widest same-value range" {
928 var owner: u8 = 0;
929 var value = ir.Value{
930 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
931 .type = undefined,
932 .id = 0,
933 };
934 var other = ir.Value{
935 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },
936 .type = undefined,
937 .id = 1,
938 };
939 const Range = range.ValueLocationRange(u8);
940 var ranges = [_]Range{
941 .{ .value = &other, .start = 4, .end = 5, .reg = 1 },
942 .{ .value = &other, .start = 1, .end = 7, .reg = 2 },
943 .{ .value = &value, .start = 2, .end = 3, .reg = 1 },
944 .{ .value = &value, .start = 1, .end = 8, .reg = 1 },
945 };
946
947 try std.testing.expectError(
948 error.InvalidAllocation,
949 verifyTestInterference(&ranges),
950 );
951 }
952
953 test "interference verifier permits overlapping ranges for one value" {
954 var owner: u8 = 0;
955 var value = ir.Value{
956 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
957 .type = undefined,
958 .id = 0,
959 };
960 var other = ir.Value{
961 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },
962 .type = undefined,
963 .id = 1,
964 };
965 const Range = range.ValueLocationRange(u8);
966 var ranges = [_]Range{
967 .{ .value = &value, .start = 5, .end = 9, .reg = 1 },
968 .{ .value = &other, .start = 5, .end = 9, .reg = 2 },
969 .{ .value = &value, .start = 1, .end = 8, .reg = 1 },
970 };
971
972 try verifyTestInterference(&ranges);
973 }