lib/choir/src/backends/regalloc/interval.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const position = @import("position.zig");
4
5 pub fn Requirement(comptime Register: type) type {
6 return union(enum) {
7 any,
8 fixed: Register,
9 };
10 }
11
12 pub const Range = struct {
13 start: u32,
14 end: u32,
15 end_phase: position.Phase,
16 };
17
18 pub fn UsePosition(comptime Register: type, comptime Mask: type) type {
19 const RequirementType = Requirement(Register);
20
21 return struct {
22 point: position.Point,
23 requirement: RequirementType,
24 source_blockers: Mask,
25 };
26 }
27
28 pub fn DefinitionPosition(comptime Register: type) type {
29 const RequirementType = Requirement(Register);
30
31 return struct {
32 point: position.Point,
33 requirement: RequirementType,
34 source: RequirementType,
35 };
36 }
37
38 pub const FixedPositionKind = enum {
39 source,
40 use,
41 scratch_use,
42 def,
43 clobber,
44 };
45
46 pub fn FixedPosition(comptime Register: type) type {
47 return struct {
48 point: position.Point,
49 reg: Register,
50 kind: FixedPositionKind,
51 };
52 }
53
54 pub fn FixedPositionIndex(comptime Register: type) type {
55 const FixedPositionType = FixedPosition(Register);
56 const register_count = switch (@typeInfo(Register)) {
57 .@"enum" => |info| info.field_names.len,
58 .int => 0,
59 else => @compileError("register type must be an integer or enum"),
60 };
61
62 return struct {
63 positions: []const FixedPositionType,
64 register_spans: *const Storage,
65
66 const Self = @This();
67 pub const RegisterSpan = struct {
68 start: usize = 0,
69 end: usize = 0,
70 };
71 pub const Storage = [register_count]RegisterSpan;
72 const empty_register_spans = @as([register_count]RegisterSpan, @splat(.{}));
73
74 pub fn init(positions: []FixedPositionType, register_spans: *Storage) Self {
75 std.mem.sort(FixedPositionType, positions, {}, lessThan);
76 register_spans.* = @as([register_count]RegisterSpan, @splat(.{}));
77 if (comptime register_count != 0) {
78 for (positions, 0..) |fixed, index| {
79 const span = ®ister_spans[registerIndex(fixed.reg)];
80 if (span.end == 0) span.start = index;
81 span.end = index + 1;
82 }
83 }
84 return .{ .positions = positions, .register_spans = register_spans };
85 }
86
87 pub fn empty() Self {
88 return .{ .positions = &.{}, .register_spans = &empty_register_spans };
89 }
90
91 pub fn between(self: Self, reg: Register, start: position.Point, end: position.Point) []const FixedPositionType {
92 if (comptime register_count != 0) {
93 const span = self.register_spans[registerIndex(reg)];
94 const register_positions = self.positions[span.start..span.end];
95 const first = pointLowerBound(register_positions, start.rank());
96 const last = pointLowerBound(register_positions, end.rank() + 1);
97 return register_positions[first..last];
98 }
99 const first = self.lowerBound(reg, start.rank());
100 const last = self.lowerBound(reg, end.rank() + 1);
101 return self.positions[first..last];
102 }
103
104 fn pointLowerBound(positions: []const FixedPositionType, rank: u64) usize {
105 var low: usize = 0;
106 var high = positions.len;
107 while (low < high) {
108 const middle = low + (high - low) / 2;
109 if (positions[middle].point.rank() < rank) {
110 low = middle + 1;
111 } else {
112 high = middle;
113 }
114 }
115 return low;
116 }
117
118 fn lowerBound(self: Self, reg: Register, rank: u64) usize {
119 var low: usize = 0;
120 var high = self.positions.len;
121 while (low < high) {
122 const middle = low + (high - low) / 2;
123 const fixed = self.positions[middle];
124 const order = registerOrder(fixed.reg, reg);
125 if (order == .lt or (order == .eq and fixed.point.rank() < rank)) {
126 low = middle + 1;
127 } else {
128 high = middle;
129 }
130 }
131 return low;
132 }
133
134 fn lessThan(_: void, lhs: FixedPositionType, rhs: FixedPositionType) bool {
135 const order = registerOrder(lhs.reg, rhs.reg);
136 if (order != .eq) return order == .lt;
137 if (lhs.point.rank() != rhs.point.rank()) return lhs.point.lessThan(rhs.point);
138 return @backingInt(lhs.kind) < @backingInt(rhs.kind);
139 }
140
141 fn registerIndex(reg: Register) usize {
142 const info = switch (@typeInfo(Register)) {
143 .@"enum" => |info| info,
144 else => unreachable,
145 };
146 inline for (info.field_values, 0..) |field_value, index| {
147 if (@backingInt(reg) == field_value) return index;
148 }
149 unreachable;
150 }
151
152 fn registerOrder(lhs: Register, rhs: Register) std.math.Order {
153 return switch (@typeInfo(Register)) {
154 .@"enum" => std.math.order(@backingInt(lhs), @backingInt(rhs)),
155 .int => std.math.order(lhs, rhs),
156 else => @compileError("register type must be an integer or enum"),
157 };
158 }
159 };
160 }
161
162 pub fn fixedPositionPoint(raw_position: u32, kind: FixedPositionKind) position.Point {
163 return switch (kind) {
164 .source, .use, .scratch_use => position.Point.source(raw_position),
165 .def, .clobber => position.Point.definition(raw_position),
166 };
167 }
168
169 pub fn Candidate(comptime Register: type, comptime Mask: type) type {
170 const RequirementType = Requirement(Register);
171 const UsePositionType = UsePosition(Register, Mask);
172 const DefinitionPositionType = DefinitionPosition(Register);
173 const FixedPositionType = FixedPosition(Register);
174
175 return struct {
176 value: *ir.Value,
177 range: Range,
178 use_positions: std.ArrayListUnmanaged(UsePositionType),
179 definition: DefinitionPositionType,
180 order: u32,
181 is_constant: bool,
182
183 const Self = @This();
184
185 pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
186 self.use_positions.deinit(allocator);
187 }
188
189 pub fn start(self: Self) u32 {
190 return self.range.start;
191 }
192
193 pub fn startPoint(self: Self) position.Point {
194 return .{ .position = self.range.start, .phase = position.valueStartPhase(self.value) };
195 }
196
197 pub fn end(self: Self) u32 {
198 return self.range.end;
199 }
200
201 pub fn endPhase(self: Self) position.Phase {
202 return self.range.end_phase;
203 }
204
205 pub fn endPoint(self: Self) position.Point {
206 return .{ .position = self.end(), .phase = self.endPhase() };
207 }
208
209 pub fn locationRangeEnd(self: Self) u32 {
210 return self.end() + 1;
211 }
212
213 pub fn containsPoint(self: Self, point: position.Point) bool {
214 if (point.position < self.start() or point.position > self.end()) return false;
215 if (point.position == self.start() and @backingInt(point.phase) < @backingInt(position.valueStartPhase(self.value))) return false;
216 if (point.position == self.end() and @backingInt(point.phase) > @backingInt(self.endPhase())) return false;
217 return true;
218 }
219
220 pub fn requirementMatchesReg(requirement: RequirementType, reg: Register) bool {
221 return switch (requirement) {
222 .any => false,
223 .fixed => |fixed| fixed == reg,
224 };
225 }
226
227 pub fn ownsFixedPosition(self: Self, fixed: FixedPositionType) bool {
228 return switch (fixed.kind) {
229 .use => {
230 if (self.definition.point.rank() == fixed.point.rank() and
231 requirementMatchesReg(self.definition.requirement, fixed.reg)) return true;
232 return self.ownsUsePosition(fixed.point, fixed.reg);
233 },
234 .scratch_use => self.ownsUsePosition(fixed.point, fixed.reg),
235 .source => self.definition.point.rank() == fixed.point.rank() and requirementMatchesReg(self.definition.source, fixed.reg),
236 .def => self.definition.point.rank() == fixed.point.rank() and requirementMatchesReg(self.definition.requirement, fixed.reg),
237 .clobber => self.definition.point.rank() == fixed.point.rank() and
238 self.startPoint().rank() == fixed.point.rank() and
239 requirementMatchesReg(self.definition.requirement, fixed.reg),
240 };
241 }
242
243 pub fn fixedPositionConflicts(self: Self, fixed: FixedPositionType, reg: Register) bool {
244 if (fixed.kind == .source or fixed.kind == .use) return false;
245 if (fixed.reg != reg) return false;
246 if (!self.containsPoint(fixed.point)) return false;
247 return !self.ownsFixedPosition(fixed);
248 }
249
250 pub fn conflictsWithFixedPositions(self: Self, fixed_positions: FixedPositionIndex(Register), reg: Register) bool {
251 for (fixed_positions.between(reg, self.startPoint(), self.endPoint())) |fixed| {
252 if (self.fixedPositionConflicts(fixed, reg)) return true;
253 }
254 return false;
255 }
256
257 pub fn useCount(self: Self) usize {
258 return self.use_positions.items.len;
259 }
260
261 pub fn usesAt(self: Self, point: position.Point) []const UsePositionType {
262 const first = self.useLowerBound(point.rank());
263 const last = self.useUpperBound(point.rank());
264 return self.use_positions.items[first..last];
265 }
266
267 pub fn usesBetween(self: Self, start_point: position.Point, end_point: position.Point) []const UsePositionType {
268 if (end_point.lessThan(start_point)) return self.use_positions.items[0..0];
269 const first = self.useLowerBound(start_point.rank());
270 const last = self.useUpperBound(end_point.rank());
271 return self.use_positions.items[first..last];
272 }
273
274 pub fn firstUse(self: Self) ?UsePositionType {
275 return if (self.use_positions.items.len == 0) null else self.use_positions.items[0];
276 }
277
278 pub fn firstUseAtOrAfter(self: Self, point: position.Point) ?UsePositionType {
279 const first = self.useLowerBound(point.rank());
280 return if (first == self.use_positions.items.len) null else self.use_positions.items[first];
281 }
282
283 pub fn recordUse(
284 self: *Self,
285 allocator: std.mem.Allocator,
286 point: position.Point,
287 requirement: RequirementType,
288 source_blockers: Mask,
289 ) !void {
290 const use = UsePositionType{
291 .point = point,
292 .requirement = requirement,
293 .source_blockers = source_blockers,
294 };
295 const len = self.use_positions.items.len;
296 if (len == 0 or self.use_positions.items[len - 1].point.rank() <= point.rank()) {
297 try self.use_positions.append(allocator, use);
298 } else {
299 try self.use_positions.insert(allocator, self.useUpperBound(point.rank()), use);
300 }
301 if (point.greaterThan(self.endPoint())) {
302 self.range.end = point.position;
303 self.range.end_phase = point.phase;
304 }
305 }
306
307 fn useLowerBound(self: Self, rank: u64) usize {
308 var low: usize = 0;
309 var high = self.use_positions.items.len;
310 while (low < high) {
311 const middle = low + (high - low) / 2;
312 if (self.use_positions.items[middle].point.rank() < rank) {
313 low = middle + 1;
314 } else {
315 high = middle;
316 }
317 }
318 return low;
319 }
320
321 fn useUpperBound(self: Self, rank: u64) usize {
322 var low: usize = 0;
323 var high = self.use_positions.items.len;
324 while (low < high) {
325 const middle = low + (high - low) / 2;
326 if (self.use_positions.items[middle].point.rank() <= rank) {
327 low = middle + 1;
328 } else {
329 high = middle;
330 }
331 }
332 return low;
333 }
334
335 fn ownsUsePosition(self: Self, point: position.Point, reg: Register) bool {
336 const rank = point.rank();
337 var index = self.useLowerBound(rank);
338 while (index < self.use_positions.items.len) : (index += 1) {
339 const use = self.use_positions.items[index];
340 if (use.point.rank() != rank) return false;
341 if (requirementMatchesReg(use.requirement, reg)) return true;
342 }
343 return false;
344 }
345
346 pub fn before(_: void, a: Self, b: Self) bool {
347 if (a.startPoint().rank() != b.startPoint().rank()) return a.startPoint().lessThan(b.startPoint());
348 if (a.endPoint().rank() != b.endPoint().rank()) return a.endPoint().lessThan(b.endPoint());
349 if (a.is_constant != b.is_constant) return !a.is_constant;
350 return a.order < b.order;
351 }
352 };
353 }
354
355 pub fn Candidates(comptime Register: type, comptime Mask: type) type {
356 const CandidateType = Candidate(Register, Mask);
357
358 return struct {
359 items: std.ArrayListUnmanaged(CandidateType) = .empty,
360 by_value: std.AutoHashMapUnmanaged(*ir.Value, usize) = .empty,
361
362 const Self = @This();
363
364 pub const empty: Self = .{};
365
366 pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
367 for (self.items.items) |*candidate| candidate.deinit(allocator);
368 self.items.deinit(allocator);
369 self.by_value.deinit(allocator);
370 }
371
372 pub fn append(self: *Self, allocator: std.mem.Allocator, candidate: CandidateType) !void {
373 const candidate_index = self.items.items.len;
374 try self.items.append(allocator, candidate);
375 errdefer _ = self.items.pop();
376 try self.by_value.putNoClobber(allocator, candidate.value, candidate_index);
377 }
378
379 pub fn getPtr(self: *Self, value: *ir.Value) ?*CandidateType {
380 const candidate_index = self.by_value.get(value) orelse return null;
381 return &self.items.items[candidate_index];
382 }
383
384 pub fn sort(self: *Self) void {
385 std.mem.sort(CandidateType, self.items.items, {}, CandidateType.before);
386 for (self.items.items, 0..) |candidate, candidate_index| {
387 self.by_value.getPtr(candidate.value).?.* = candidate_index;
388 }
389 }
390
391 pub fn slice(self: *Self) []CandidateType {
392 return self.items.items;
393 }
394 };
395 }
396
397 pub fn Active(comptime Register: type) type {
398 return struct {
399 start: u32,
400 end: u32,
401 end_phase: position.Phase,
402 reg: Register,
403 candidate_index: usize,
404
405 const Self = @This();
406
407 pub fn endPoint(self: Self) position.Point {
408 return .{ .position = self.end, .phase = self.end_phase };
409 }
410 };
411 }
412
413 pub fn ActiveSet(comptime Register: type) type {
414 const ActiveType = Active(Register);
415
416 return struct {
417 items: std.ArrayListUnmanaged(ActiveType) = .empty,
418
419 const Self = @This();
420
421 pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
422 self.items.deinit(allocator);
423 }
424
425 pub fn append(self: *Self, allocator: std.mem.Allocator, active: ActiveType) !void {
426 try self.items.append(allocator, active);
427 }
428
429 pub fn containsRegister(self: Self, reg: Register) bool {
430 for (self.items.items) |entry| {
431 if (entry.reg == reg) return true;
432 }
433 return false;
434 }
435
436 pub fn slice(self: Self) []const ActiveType {
437 return self.items.items;
438 }
439
440 pub fn swapRemove(self: *Self, index: usize) ActiveType {
441 return self.items.swapRemove(index);
442 }
443
444 pub fn pop(self: *Self) ?ActiveType {
445 return self.items.pop();
446 }
447
448 pub fn takeExpiredBefore(self: *Self, point: position.Point) ?ActiveType {
449 var i: usize = 0;
450 while (i < self.items.items.len) {
451 if (self.items.items[i].endPoint().lessThan(point)) return self.items.swapRemove(i);
452 i += 1;
453 }
454 return null;
455 }
456 };
457 }
458
459 pub fn firstAvailableRegister(comptime Register: type, active: ActiveSet(Register), homes: []const Register, policy: anytype) ?Register {
460 for (homes) |reg| {
461 if (active.containsRegister(reg)) continue;
462 if (policy.blocksRegister(reg)) continue;
463 return reg;
464 }
465 return null;
466 }
467
468 pub fn AvailableRegister(comptime Register: type) type {
469 return struct {
470 reg: Register,
471 until: position.Point,
472 };
473 }
474
475 pub fn bestAvailableRegister(comptime Register: type, active: ActiveSet(Register), homes: []const Register, policy: anytype) ?AvailableRegister(Register) {
476 var best: ?AvailableRegister(Register) = null;
477 for (homes) |reg| {
478 if (active.containsRegister(reg)) continue;
479 const until = policy.availableUntil(reg) orelse continue;
480 if (best) |current| {
481 if (current.until.lessThan(until)) best = .{ .reg = reg, .until = until };
482 } else {
483 best = .{ .reg = reg, .until = until };
484 }
485 }
486 return best;
487 }
488
489 pub fn evictionCandidateIndex(
490 comptime Register: type,
491 comptime CandidateType: type,
492 active: []const Active(Register),
493 candidates: []const CandidateType,
494 policy: anytype,
495 ) ?usize {
496 var victim_index: ?usize = null;
497 for (active, 0..) |entry, index| {
498 if (policy.blocksRegister(entry.reg)) continue;
499 const victim = candidates[entry.candidate_index];
500 if (!policy.canEvict(victim)) continue;
501 if (victim_index) |current_index| {
502 const current = candidates[active[current_index].candidate_index];
503 if (policy.prefersVictim(victim, current)) victim_index = index;
504 } else {
505 victim_index = index;
506 }
507 }
508 return victim_index;
509 }
510
511 test "fixed position kinds map to source and definition phases" {
512 try std.testing.expectEqual(position.Phase.source, fixedPositionPoint(3, .use).phase);
513 try std.testing.expectEqual(position.Phase.source, fixedPositionPoint(3, .scratch_use).phase);
514 try std.testing.expectEqual(position.Phase.definition, fixedPositionPoint(3, .def).phase);
515 try std.testing.expectEqual(position.Phase.definition, fixedPositionPoint(3, .clobber).phase);
516 }
517
518 test "candidate collection preserves order and indexes values" {
519 var owner: u8 = 0;
520 var first = ir.Value{
521 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
522 .type = undefined,
523 .id = 0,
524 };
525 var second = ir.Value{
526 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },
527 .type = undefined,
528 .id = 1,
529 };
530 var missing = ir.Value{
531 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 2 } },
532 .type = undefined,
533 .id = 2,
534 };
535
536 const Collection = Candidates(u8, u8);
537 var candidates: Collection = .empty;
538 defer candidates.deinit(std.testing.allocator);
539
540 try candidates.append(std.testing.allocator, .{
541 .value = &first,
542 .range = .{ .start = 1, .end = 1, .end_phase = .definition },
543 .use_positions = .empty,
544 .definition = .{ .point = position.Point.definition(1), .requirement = .any, .source = .any },
545 .order = 0,
546 .is_constant = false,
547 });
548 try candidates.append(std.testing.allocator, .{
549 .value = &second,
550 .range = .{ .start = 2, .end = 2, .end_phase = .definition },
551 .use_positions = .empty,
552 .definition = .{ .point = position.Point.definition(2), .requirement = .any, .source = .any },
553 .order = 1,
554 .is_constant = false,
555 });
556
557 const indexed = candidates.getPtr(&second) orelse return error.TestFailure;
558 try indexed.recordUse(std.testing.allocator, position.Point.source(5), .any, 0);
559
560 try std.testing.expectEqual(&first, candidates.slice()[0].value);
561 try std.testing.expectEqual(&second, candidates.slice()[1].value);
562 try std.testing.expectEqual(@as(u32, 5), candidates.slice()[1].end());
563 try std.testing.expectEqual(@as(?*Candidate(u8, u8), null), candidates.getPtr(&missing));
564 }
565
566 test "candidate fixed position ownership is requirement based" {
567 var owner: u8 = 0;
568 var value = ir.Value{
569 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
570 .type = undefined,
571 .id = 0,
572 };
573
574 const CandidateType = Candidate(u8, u8);
575 const UsePositionType = UsePosition(u8, u8);
576 const FixedPositionType = FixedPosition(u8);
577 var uses: std.ArrayListUnmanaged(UsePositionType) = .empty;
578 defer uses.deinit(std.testing.allocator);
579 try uses.append(std.testing.allocator, .{
580 .point = position.Point.definition(3),
581 .requirement = .any,
582 .source_blockers = 0,
583 });
584 try uses.append(std.testing.allocator, .{
585 .point = position.Point.source(4),
586 .requirement = .{ .fixed = 2 },
587 .source_blockers = 0,
588 });
589
590 const candidate = CandidateType{
591 .value = &value,
592 .range = .{ .start = 3, .end = 4, .end_phase = .source },
593 .use_positions = uses,
594 .definition = .{
595 .point = position.Point.definition(3),
596 .requirement = .{ .fixed = 1 },
597 .source = .any,
598 },
599 .order = 0,
600 .is_constant = false,
601 };
602 const def_fixed = FixedPositionType{ .point = position.Point.definition(3), .reg = 1, .kind = .def };
603 const scratch_fixed = FixedPositionType{ .point = position.Point.source(4), .reg = 2, .kind = .scratch_use };
604 const clobber = FixedPositionType{ .point = position.Point.definition(3), .reg = 2, .kind = .clobber };
605 var fixed_positions = [_]FixedPositionType{ def_fixed, scratch_fixed, clobber };
606 var fixed_position_index_storage: FixedPositionIndex(u8).Storage = undefined;
607 const fixed_position_index = FixedPositionIndex(u8).init(&fixed_positions, &fixed_position_index_storage);
608
609 try std.testing.expect(candidate.ownsFixedPosition(def_fixed));
610 try std.testing.expect(candidate.ownsFixedPosition(scratch_fixed));
611 try std.testing.expect(candidate.fixedPositionConflicts(clobber, 2));
612 try std.testing.expect(!candidate.fixedPositionConflicts(def_fixed, 1));
613 try std.testing.expect(candidate.conflictsWithFixedPositions(fixed_position_index, 2));
614 try std.testing.expect(!candidate.conflictsWithFixedPositions(fixed_position_index, 1));
615
616 const first_use = candidate.firstUse() orelse return error.TestFailure;
617 try std.testing.expectEqual(position.Point.definition(3), first_use.point);
618 const same_point_use = candidate.firstUseAtOrAfter(position.Point.definition(3)) orelse return error.TestFailure;
619 try std.testing.expectEqual(position.Point.definition(3), same_point_use.point);
620 const later_use = candidate.firstUseAtOrAfter(position.Point.source(4)) orelse return error.TestFailure;
621 try std.testing.expectEqual(position.Point.source(4), later_use.point);
622 try std.testing.expectEqual(@as(?UsePositionType, null), candidate.firstUseAtOrAfter(position.Point.definition(4)));
623 }
624
625 test "active set tracks registers and expires by point phase" {
626 const Set = ActiveSet(u8);
627
628 var active = Set{};
629 defer active.deinit(std.testing.allocator);
630
631 try active.append(std.testing.allocator, .{
632 .start = 0,
633 .end = 4,
634 .end_phase = .source,
635 .reg = 1,
636 .candidate_index = 0,
637 });
638 try active.append(std.testing.allocator, .{
639 .start = 1,
640 .end = 4,
641 .end_phase = .definition,
642 .reg = 2,
643 .candidate_index = 1,
644 });
645
646 try std.testing.expect(active.containsRegister(1));
647 try std.testing.expect(active.containsRegister(2));
648 try std.testing.expect(!active.containsRegister(3));
649
650 try std.testing.expectEqual(@as(?Active(u8), null), active.takeExpiredBefore(position.Point.source(4)));
651
652 const expired = active.takeExpiredBefore(position.Point.definition(4)) orelse return error.TestFailure;
653 try std.testing.expectEqual(@as(u8, 1), expired.reg);
654 try std.testing.expect(!active.containsRegister(1));
655 try std.testing.expect(active.containsRegister(2));
656
657 const remaining = active.pop() orelse return error.TestFailure;
658 try std.testing.expectEqual(@as(u8, 2), remaining.reg);
659 try std.testing.expectEqual(@as(?Active(u8), null), active.pop());
660 }
661
662 test "register selection scans homes and eviction candidates through policy" {
663 const Set = ActiveSet(u8);
664
665 var active = Set{};
666 defer active.deinit(std.testing.allocator);
667
668 try active.append(std.testing.allocator, .{
669 .start = 0,
670 .end = 8,
671 .end_phase = .definition,
672 .reg = 1,
673 .candidate_index = 0,
674 });
675 try active.append(std.testing.allocator, .{
676 .start = 0,
677 .end = 8,
678 .end_phase = .definition,
679 .reg = 2,
680 .candidate_index = 1,
681 });
682 try active.append(std.testing.allocator, .{
683 .start = 0,
684 .end = 8,
685 .end_phase = .definition,
686 .reg = 3,
687 .candidate_index = 2,
688 });
689
690 const Policy = struct {
691 blocked: u8,
692 incoming_priority: u8,
693
694 fn blocksRegister(self: @This(), reg: u8) bool {
695 return self.blocked == reg;
696 }
697
698 fn canEvict(self: @This(), victim_priority: u8) bool {
699 return self.incoming_priority > victim_priority;
700 }
701
702 fn prefersVictim(_: @This(), victim_priority: u8, current_priority: u8) bool {
703 return victim_priority < current_priority;
704 }
705 };
706
707 const homes = [_]u8{ 1, 2, 3, 4 };
708 const candidates = [_]u8{ 5, 2, 8 };
709
710 try std.testing.expectEqual(@as(?u8, 4), firstAvailableRegister(u8, active, &homes, Policy{ .blocked = 2, .incoming_priority = 6 }));
711 try std.testing.expectEqual(@as(?usize, 0), evictionCandidateIndex(u8, u8, active.slice(), &candidates, Policy{ .blocked = 2, .incoming_priority = 6 }));
712 try std.testing.expectEqual(@as(?usize, 1), evictionCandidateIndex(u8, u8, active.slice(), &candidates, Policy{ .blocked = 0, .incoming_priority = 6 }));
713 }
714
715 test "best available register chooses farthest available point" {
716 const Set = ActiveSet(u8);
717
718 var active = Set{};
719 defer active.deinit(std.testing.allocator);
720
721 try active.append(std.testing.allocator, .{
722 .start = 0,
723 .end = 8,
724 .end_phase = .definition,
725 .reg = 1,
726 .candidate_index = 0,
727 });
728
729 const Policy = struct {
730 fn availableUntil(_: @This(), reg: u8) ?position.Point {
731 return switch (reg) {
732 2 => null,
733 3 => position.Point.source(5),
734 4 => position.Point.definition(5),
735 5 => position.Point.source(9),
736 else => position.Point.source(1),
737 };
738 }
739 };
740
741 const homes = [_]u8{ 1, 2, 3, 4, 5 };
742 const choice = bestAvailableRegister(u8, active, &homes, Policy{}) orelse return error.TestFailure;
743
744 try std.testing.expectEqual(@as(u8, 5), choice.reg);
745 try std.testing.expectEqual(position.Point.source(9), choice.until);
746 }