tiny.choir.backends.regalloc.interval

1const std = @import("std");2const ir = @import("../../core/root.zig");3const position = @import("position.zig");45pub fn Requirement(comptime Register: type) type {6    return union(enum) {7        any,8        fixed: Register,9    };10}1112pub const Range = struct {13    start: u32,14    end: u32,15    end_phase: position.Phase,16};1718pub fn UsePosition(comptime Register: type, comptime Mask: type) type {19    const RequirementType = Requirement(Register);2021    return struct {22        point: position.Point,23        requirement: RequirementType,24        source_blockers: Mask,25    };26}2728pub fn DefinitionPosition(comptime Register: type) type {29    const RequirementType = Requirement(Register);3031    return struct {32        point: position.Point,33        requirement: RequirementType,34        source: RequirementType,35    };36}3738pub const FixedPositionKind = enum {39    source,40    use,41    scratch_use,42    def,43    clobber,44};4546pub fn FixedPosition(comptime Register: type) type {47    return struct {48        point: position.Point,49        reg: Register,50        kind: FixedPositionKind,51    };52}5354pub 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    };6162    return struct {63        positions: []const FixedPositionType,64        register_spans: *const Storage,6566        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(.{}));7374        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 = &register_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        }8687        pub fn empty() Self {88            return .{ .positions = &.{}, .register_spans = &empty_register_spans };89        }9091        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        }103104        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        }117118        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        }133134        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        }140141        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        }151152        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}161162pub 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}168169pub 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);174175    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,182183        const Self = @This();184185        pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {186            self.use_positions.deinit(allocator);187        }188189        pub fn start(self: Self) u32 {190            return self.range.start;191        }192193        pub fn startPoint(self: Self) position.Point {194            return .{ .position = self.range.start, .phase = position.valueStartPhase(self.value) };195        }196197        pub fn end(self: Self) u32 {198            return self.range.end;199        }200201        pub fn endPhase(self: Self) position.Phase {202            return self.range.end_phase;203        }204205        pub fn endPoint(self: Self) position.Point {206            return .{ .position = self.end(), .phase = self.endPhase() };207        }208209        pub fn locationRangeEnd(self: Self) u32 {210            return self.end() + 1;211        }212213        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        }219220        pub fn requirementMatchesReg(requirement: RequirementType, reg: Register) bool {221            return switch (requirement) {222                .any => false,223                .fixed => |fixed| fixed == reg,224            };225        }226227        pub fn ownsFixedPosition(self: Self, fixed: FixedPositionType) bool {228            return switch (fixed.kind) {229                .use => {230                    if (self.definition.point.rank() == fixed.point.rank() and231                        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() and238                    self.startPoint().rank() == fixed.point.rank() and239                    requirementMatchesReg(self.definition.requirement, fixed.reg),240            };241        }242243        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        }249250        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        }256257        pub fn useCount(self: Self) usize {258            return self.use_positions.items.len;259        }260261        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        }266267        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        }273274        pub fn firstUse(self: Self) ?UsePositionType {275            return if (self.use_positions.items.len == 0) null else self.use_positions.items[0];276        }277278        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        }282283        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        }306307        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        }320321        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        }334335        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        }345346        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}354355pub fn Candidates(comptime Register: type, comptime Mask: type) type {356    const CandidateType = Candidate(Register, Mask);357358    return struct {359        items: std.ArrayListUnmanaged(CandidateType) = .empty,360        by_value: std.AutoHashMapUnmanaged(*ir.Value, usize) = .empty,361362        const Self = @This();363364        pub const empty: Self = .{};365366        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        }371372        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        }378379        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        }383384        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        }390391        pub fn slice(self: *Self) []CandidateType {392            return self.items.items;393        }394    };395}396397pub 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,404405        const Self = @This();406407        pub fn endPoint(self: Self) position.Point {408            return .{ .position = self.end, .phase = self.end_phase };409        }410    };411}412413pub fn ActiveSet(comptime Register: type) type {414    const ActiveType = Active(Register);415416    return struct {417        items: std.ArrayListUnmanaged(ActiveType) = .empty,418419        const Self = @This();420421        pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {422            self.items.deinit(allocator);423        }424425        pub fn append(self: *Self, allocator: std.mem.Allocator, active: ActiveType) !void {426            try self.items.append(allocator, active);427        }428429        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        }435436        pub fn slice(self: Self) []const ActiveType {437            return self.items.items;438        }439440        pub fn swapRemove(self: *Self, index: usize) ActiveType {441            return self.items.swapRemove(index);442        }443444        pub fn pop(self: *Self) ?ActiveType {445            return self.items.pop();446        }447448        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}458459pub 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}467468pub fn AvailableRegister(comptime Register: type) type {469    return struct {470        reg: Register,471        until: position.Point,472    };473}474475pub 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}488489pub 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}510511test "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}517518test "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    };535536    const Collection = Candidates(u8, u8);537    var candidates: Collection = .empty;538    defer candidates.deinit(std.testing.allocator);539540    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    });556557    const indexed = candidates.getPtr(&second) orelse return error.TestFailure;558    try indexed.recordUse(std.testing.allocator, position.Point.source(5), .any, 0);559560    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}565566test "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    };573574    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    });589590    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);608609    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));615616    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}624625test "active set tracks registers and expires by point phase" {626    const Set = ActiveSet(u8);627628    var active = Set{};629    defer active.deinit(std.testing.allocator);630631    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    });645646    try std.testing.expect(active.containsRegister(1));647    try std.testing.expect(active.containsRegister(2));648    try std.testing.expect(!active.containsRegister(3));649650    try std.testing.expectEqual(@as(?Active(u8), null), active.takeExpiredBefore(position.Point.source(4)));651652    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));656657    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}661662test "register selection scans homes and eviction candidates through policy" {663    const Set = ActiveSet(u8);664665    var active = Set{};666    defer active.deinit(std.testing.allocator);667668    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    });689690    const Policy = struct {691        blocked: u8,692        incoming_priority: u8,693694        fn blocksRegister(self: @This(), reg: u8) bool {695            return self.blocked == reg;696        }697698        fn canEvict(self: @This(), victim_priority: u8) bool {699            return self.incoming_priority > victim_priority;700        }701702        fn prefersVictim(_: @This(), victim_priority: u8, current_priority: u8) bool {703            return victim_priority < current_priority;704        }705    };706707    const homes = [_]u8{ 1, 2, 3, 4 };708    const candidates = [_]u8{ 5, 2, 8 };709710    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}714715test "best available register chooses farthest available point" {716    const Set = ActiveSet(u8);717718    var active = Set{};719    defer active.deinit(std.testing.allocator);720721    try active.append(std.testing.allocator, .{722        .start = 0,723        .end = 8,724        .end_phase = .definition,725        .reg = 1,726        .candidate_index = 0,727    });728729    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    };740741    const homes = [_]u8{ 1, 2, 3, 4, 5 };742    const choice = bestAvailableRegister(u8, active, &homes, Policy{}) orelse return error.TestFailure;743744    try std.testing.expectEqual(@as(u8, 5), choice.reg);745    try std.testing.expectEqual(position.Point.source(9), choice.until);746}

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