tiny.choir.backends.regalloc.range

1const std = @import("std");2const ir = @import("../../core/root.zig");3const interval = @import("interval.zig");4const position = @import("position.zig");56pub const Entry = enum {7    resident,8    reload,9};1011pub const Exit = enum {12    retain,13    spill,14};1516pub fn ValueLocationRange(comptime Register: type) type {17    return struct {18        value: *ir.Value,19        start: u32,20        end: u32,21        reg: Register,22        entry: Entry = .resident,23        end_phase: position.Phase = .definition,24        exit: Exit = .retain,2526        const Self = @This();2728        pub fn startPhase(self: Self) position.Phase {29            return switch (self.entry) {30                .reload => .source,31                .resident => position.valueStartPhase(self.value),32            };33        }3435        pub fn containsPoint(self: Self, point: position.Point) bool {36            if (point.position < self.start or point.position >= self.end) return false;37            if (point.position == self.start and @backingInt(point.phase) < @backingInt(self.startPhase())) return false;38            if (point.position == self.end - 1 and @backingInt(point.phase) > @backingInt(self.end_phase)) return false;39            return true;40        }4142        pub fn startPoint(self: Self) position.Point {43            return .{ .position = self.start, .phase = self.startPhase() };44        }4546        pub fn endPoint(self: Self) position.Point {47            return .{ .position = self.end - 1, .phase = self.end_phase };48        }4950        pub fn overlaps(self: Self, other: Self) bool {51            if (self.start >= self.end or other.start >= other.end) return false;52            const start = @max(self.startPoint().rank(), other.startPoint().rank());53            const end = @min(self.endPoint().rank(), other.endPoint().rank());54            return start <= end;55        }5657        pub fn coversValueAt(self: Self, value: *ir.Value, point: position.Point) bool {58            return self.value == value and self.containsPoint(point);59        }6061        pub fn blocksRegisterAt(self: Self, reg: Register, point: position.Point) bool {62            return self.reg == reg and self.containsPoint(point);63        }64    };65}6667pub fn appendValueLocationRange(68    comptime Register: type,69    ranges: *std.ArrayListUnmanaged(ValueLocationRange(Register)),70    allocator: std.mem.Allocator,71    value: *ir.Value,72    start: u32,73    end: u32,74    reg: Register,75    entry: Entry,76    end_phase: position.Phase,77    exit: Exit,78) !void {79    if (start >= end) return;80    try ranges.append(allocator, .{81        .value = value,82        .start = start,83        .end = end,84        .reg = reg,85        .entry = entry,86        .end_phase = end_phase,87        .exit = exit,88    });89}9091pub fn candidateRangeFixedConflictStart(92    comptime Register: type,93    comptime Mask: type,94    candidate: interval.Candidate(Register, Mask),95    fixed_positions: interval.FixedPositionIndex(Register),96    proposed: ValueLocationRange(Register),97) ?position.Point {98    for (fixed_positions.between(proposed.reg, proposed.startPoint(), proposed.endPoint())) |fixed| {99        if (fixed.kind == .source or fixed.kind == .use) continue;100        if (!candidate.ownsFixedPosition(fixed)) return fixed.point;101    }102    return null;103}104105pub fn candidateRangeConflictsWithFixedPositions(106    comptime Register: type,107    comptime Mask: type,108    candidate: interval.Candidate(Register, Mask),109    fixed_positions: interval.FixedPositionIndex(Register),110    proposed: ValueLocationRange(Register),111) bool {112    return candidateRangeFixedConflictStart(Register, Mask, candidate, fixed_positions, proposed) != null;113}114115test "value location ranges compare phase-aware overlap" {116    var owner: u8 = 0;117    var first_value = ir.Value{118        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },119        .type = undefined,120        .id = 0,121    };122    var second_value = ir.Value{123        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },124        .type = undefined,125        .id = 1,126    };127128    const Range = ValueLocationRange(u8);129    const resident = Range{130        .value = &first_value,131        .start = 1,132        .end = 3,133        .reg = 1,134        .end_phase = .source,135    };136    const reload = Range{137        .value = &second_value,138        .start = 2,139        .end = 3,140        .reg = 1,141        .entry = .reload,142        .end_phase = .source,143    };144    const late = Range{145        .value = &second_value,146        .start = 2,147        .end = 3,148        .reg = 1,149    };150151    try std.testing.expect(resident.overlaps(reload));152    try std.testing.expect(!resident.overlaps(late));153}154155test "value location ranges cover values and block registers at points" {156    var owner: u8 = 0;157    var value = ir.Value{158        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },159        .type = undefined,160        .id = 0,161    };162    var other_value = ir.Value{163        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 1 } },164        .type = undefined,165        .id = 1,166    };167168    const Range = ValueLocationRange(u8);169    const range = Range{170        .value = &value,171        .start = 4,172        .end = 5,173        .reg = 2,174    };175    const point = position.Point.definition(4);176177    try std.testing.expect(range.coversValueAt(&value, point));178    try std.testing.expect(!range.coversValueAt(&other_value, point));179    try std.testing.expect(range.blocksRegisterAt(2, point));180    try std.testing.expect(!range.blocksRegisterAt(3, point));181}182183test "candidate range fixed-position conflict query uses proposed range" {184    var owner: u8 = 0;185    var value = ir.Value{186        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },187        .type = undefined,188        .id = 0,189    };190191    const Candidate = interval.Candidate(u8, u8);192    const UsePosition = interval.UsePosition(u8, u8);193    const FixedPosition = interval.FixedPosition(u8);194    const Range = ValueLocationRange(u8);195196    var uses: std.ArrayListUnmanaged(UsePosition) = .empty;197    defer uses.deinit(std.testing.allocator);198    try uses.append(std.testing.allocator, .{199        .point = position.Point.source(4),200        .requirement = .{ .fixed = 2 },201        .source_blockers = 0,202    });203204    const candidate = Candidate{205        .value = &value,206        .range = .{ .start = 0, .end = 4, .end_phase = .source },207        .use_positions = uses,208        .definition = .{209            .point = position.Point.definition(0),210            .requirement = .{ .fixed = 1 },211            .source = .any,212        },213        .order = 0,214        .is_constant = false,215    };216    var fixed_positions = [_]FixedPosition{217        .{ .point = position.Point.definition(3), .reg = 1, .kind = .clobber },218        .{ .point = position.Point.source(4), .reg = 2, .kind = .scratch_use },219        .{ .point = position.Point.source(4), .reg = 1, .kind = .use },220    };221    var fixed_position_index_storage: interval.FixedPositionIndex(u8).Storage = undefined;222    const fixed_position_index = interval.FixedPositionIndex(u8).init(&fixed_positions, &fixed_position_index_storage);223224    const crosses_clobber = Range{225        .value = &value,226        .start = 2,227        .end = 5,228        .reg = 1,229        .end_phase = .source,230    };231    const after_clobber = Range{232        .value = &value,233        .start = 4,234        .end = 5,235        .reg = 1,236        .end_phase = .source,237    };238    const owned_scratch = Range{239        .value = &value,240        .start = 4,241        .end = 5,242        .reg = 2,243        .end_phase = .source,244    };245246    try std.testing.expect(candidateRangeConflictsWithFixedPositions(u8, u8, candidate, fixed_position_index, crosses_clobber));247    try std.testing.expect(!candidateRangeConflictsWithFixedPositions(u8, u8, candidate, fixed_position_index, after_clobber));248    try std.testing.expect(!candidateRangeConflictsWithFixedPositions(u8, u8, candidate, fixed_position_index, owned_scratch));249250    const conflict = candidateRangeFixedConflictStart(u8, u8, candidate, fixed_position_index, crosses_clobber) orelse return error.TestFailure;251    try std.testing.expectEqual(position.Point.definition(3), conflict);252    try std.testing.expectEqual(@as(?position.Point, null), candidateRangeFixedConflictStart(u8, u8, candidate, fixed_position_index, after_clobber));253}254255test "value location range append skips empty ranges" {256    var owner: u8 = 0;257    var value = ir.Value{258        .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },259        .type = undefined,260        .id = 0,261    };262263    const Range = ValueLocationRange(u8);264    var ranges: std.ArrayListUnmanaged(Range) = .empty;265    defer ranges.deinit(std.testing.allocator);266267    try appendValueLocationRange(u8, &ranges, std.testing.allocator, &value, 3, 3, 1, .resident, .source, .retain);268    try std.testing.expectEqual(@as(usize, 0), ranges.items.len);269270    try appendValueLocationRange(u8, &ranges, std.testing.allocator, &value, 3, 4, 1, .resident, .definition, .retain);271    try std.testing.expectEqual(@as(usize, 1), ranges.items.len);272    try std.testing.expect(ranges.items[0].coversValueAt(&value, position.Point.definition(3)));273}

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