lib/choir/src/backends/regalloc/range.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const interval = @import("interval.zig");
4 const position = @import("position.zig");
5
6 pub const Entry = enum {
7 resident,
8 reload,
9 };
10
11 pub const Exit = enum {
12 retain,
13 spill,
14 };
15
16 pub 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,
25
26 const Self = @This();
27
28 pub fn startPhase(self: Self) position.Phase {
29 return switch (self.entry) {
30 .reload => .source,
31 .resident => position.valueStartPhase(self.value),
32 };
33 }
34
35 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 }
41
42 pub fn startPoint(self: Self) position.Point {
43 return .{ .position = self.start, .phase = self.startPhase() };
44 }
45
46 pub fn endPoint(self: Self) position.Point {
47 return .{ .position = self.end - 1, .phase = self.end_phase };
48 }
49
50 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 }
56
57 pub fn coversValueAt(self: Self, value: *ir.Value, point: position.Point) bool {
58 return self.value == value and self.containsPoint(point);
59 }
60
61 pub fn blocksRegisterAt(self: Self, reg: Register, point: position.Point) bool {
62 return self.reg == reg and self.containsPoint(point);
63 }
64 };
65 }
66
67 pub 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 }
90
91 pub 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 }
104
105 pub 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 }
114
115 test "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 };
127
128 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 };
150
151 try std.testing.expect(resident.overlaps(reload));
152 try std.testing.expect(!resident.overlaps(late));
153 }
154
155 test "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 };
167
168 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);
176
177 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 }
182
183 test "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 };
190
191 const Candidate = interval.Candidate(u8, u8);
192 const UsePosition = interval.UsePosition(u8, u8);
193 const FixedPosition = interval.FixedPosition(u8);
194 const Range = ValueLocationRange(u8);
195
196 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 });
203
204 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);
223
224 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 };
245
246 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));
249
250 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 }
254
255 test "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 };
262
263 const Range = ValueLocationRange(u8);
264 var ranges: std.ArrayListUnmanaged(Range) = .empty;
265 defer ranges.deinit(std.testing.allocator);
266
267 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);
269
270 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 }