lib/choir/src/properties/candidates.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const choir = @import("choir");
4
5 const regalloc = choir.backends.regalloc;
6 const Candidate = regalloc.Candidate(u8, u8);
7 const Candidates = regalloc.Candidates(u8, u8);
8 const FixedPosition = regalloc.FixedPosition(u8);
9 const Point = regalloc.PositionPoint;
10 const Requirement = regalloc.Requirement(u8);
11 const UsePosition = regalloc.UsePosition(u8, u8);
12
13 fn settings() hypothesis.Settings {
14 return hypothesis.Settings.quick()
15 .withSeed(0xca7d_1da7_e001)
16 .withDatabase("zig-out/hypothesis-failures/choir-regalloc-candidates");
17 }
18
19 fn useSettings() hypothesis.Settings {
20 return hypothesis.Settings.quick()
21 .withSeed(0x5e5f_0577_10d3)
22 .withDatabase("zig-out/hypothesis-failures/choir-regalloc-candidate-uses");
23 }
24
25 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
26 return @intCast(try conjecture.drawInteger(@intCast(min), @intCast(max), @intCast(shrink_towards)));
27 }
28
29 pub const CandidateCollectionProperty = struct {
30 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
31 var owner: u8 = 0;
32 const value_count = try drawUsize(conjecture, 1, 128, 1);
33 const values = try allocator.alloc(choir.Value, value_count);
34 defer allocator.free(values);
35 const expected_ends = try allocator.alloc(Point, value_count);
36 defer allocator.free(expected_ends);
37
38 for (values, expected_ends, 0..) |*value, *expected_end, index| {
39 const start: u32 = @intCast(index);
40 value.* = .{
41 .kind = .{ .op_result = .{ .owner = &owner, .result_number = @intCast(index) } },
42 .type = undefined,
43 .id = @intCast(index),
44 };
45 expected_end.* = Point.definition(start);
46 }
47
48 var candidates: Candidates = .empty;
49 defer candidates.deinit(allocator);
50 const reverse = try conjecture.drawBoolean();
51 for (0..value_count) |insertion_index| {
52 const value_index = if (reverse) value_count - insertion_index - 1 else insertion_index;
53 const start: u32 = @intCast(value_index);
54 try candidates.append(allocator, .{
55 .value = &values[value_index],
56 .range = .{ .start = start, .end = start, .end_phase = .definition },
57 .use_positions = .empty,
58 .definition = .{ .point = Point.definition(start), .requirement = .any, .source = .any },
59 .order = @intCast(insertion_index),
60 .is_constant = false,
61 });
62 }
63
64 const query_count = try drawUsize(conjecture, 1, 256, 1);
65 for (0..query_count) |_| {
66 const value_index = try drawUsize(conjecture, 0, value_count - 1, 0);
67 const point = Point{
68 .position = @intCast(try drawUsize(conjecture, 0, 255, 0)),
69 .phase = if (try conjecture.drawBoolean()) .definition else .source,
70 };
71 const candidate = candidates.getPtr(&values[value_index]) orelse return error.TestFailure;
72 try candidate.recordUse(allocator, point, .any, 0);
73 if (point.greaterThan(expected_ends[value_index])) expected_ends[value_index] = point;
74 try std.testing.expectEqual(expected_ends[value_index], candidate.endPoint());
75
76 const insertion_index = if (reverse) value_count - value_index - 1 else value_index;
77 try std.testing.expectEqual(&values[value_index], candidates.slice()[insertion_index].value);
78 try std.testing.expectEqual(candidate, &candidates.slice()[insertion_index]);
79 }
80
81 candidates.sort();
82 for (values, 0..) |*value, value_index| {
83 try std.testing.expectEqual(value, candidates.slice()[value_index].value);
84 try std.testing.expectEqual(&candidates.slice()[value_index], candidates.getPtr(value).?);
85 }
86
87 var missing = choir.Value{
88 .kind = .{ .op_result = .{ .owner = &owner, .result_number = @intCast(value_count) } },
89 .type = undefined,
90 .id = @intCast(value_count),
91 };
92 try std.testing.expectEqual(@as(?*regalloc.Candidate(u8, u8), null), candidates.getPtr(&missing));
93 }
94 };
95
96 fn drawPoint(conjecture: *hypothesis.ConjectureData) !Point {
97 return .{
98 .position = @intCast(try drawUsize(conjecture, 1, 64, 1)),
99 .phase = if (try conjecture.drawBoolean()) .definition else .source,
100 };
101 }
102
103 fn drawRequirement(conjecture: *hypothesis.ConjectureData) !Requirement {
104 if (try conjecture.drawBoolean()) return .any;
105 return .{ .fixed = @intCast(try drawUsize(conjecture, 0, 7, 0)) };
106 }
107
108 fn useBefore(_: void, lhs: UsePosition, rhs: UsePosition) bool {
109 if (lhs.point.rank() != rhs.point.rank()) return lhs.point.lessThan(rhs.point);
110 return lhs.source_blockers < rhs.source_blockers;
111 }
112
113 fn requirementMatches(requirement: Requirement, reg: u8) bool {
114 return switch (requirement) {
115 .any => false,
116 .fixed => |fixed| fixed == reg,
117 };
118 }
119
120 fn ownsFixedPositionLinear(candidate: Candidate, uses: []const UsePosition, fixed: FixedPosition) bool {
121 return switch (fixed.kind) {
122 .use => owns: {
123 if (candidate.definition.point.rank() == fixed.point.rank() and
124 requirementMatches(candidate.definition.requirement, fixed.reg)) break :owns true;
125 for (uses) |use| {
126 if (use.point.rank() == fixed.point.rank() and requirementMatches(use.requirement, fixed.reg)) break :owns true;
127 }
128 break :owns false;
129 },
130 .scratch_use => owns: {
131 for (uses) |use| {
132 if (use.point.rank() == fixed.point.rank() and requirementMatches(use.requirement, fixed.reg)) break :owns true;
133 }
134 break :owns false;
135 },
136 .source => candidate.definition.point.rank() == fixed.point.rank() and requirementMatches(candidate.definition.source, fixed.reg),
137 .def => candidate.definition.point.rank() == fixed.point.rank() and requirementMatches(candidate.definition.requirement, fixed.reg),
138 .clobber => candidate.definition.point.rank() == fixed.point.rank() and
139 candidate.startPoint().rank() == fixed.point.rank() and
140 requirementMatches(candidate.definition.requirement, fixed.reg),
141 };
142 }
143
144 fn firstAtOrAfterLinear(uses: []const UsePosition, point: Point) ?UsePosition {
145 for (uses) |use| {
146 if (!use.point.lessThan(point)) return use;
147 }
148 return null;
149 }
150
151 fn sliceBoundsLinear(uses: []const UsePosition, start: Point, end: Point) struct { first: usize, last: usize } {
152 var first: usize = 0;
153 while (first < uses.len and uses[first].point.lessThan(start)) first += 1;
154 var last = first;
155 while (last < uses.len and !end.lessThan(uses[last].point)) last += 1;
156 return .{ .first = first, .last = last };
157 }
158
159 pub const CandidateUseProperty = struct {
160 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
161 var owner: u8 = 0;
162 var value = choir.Value{
163 .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
164 .type = undefined,
165 .id = 0,
166 };
167 var candidate = Candidate{
168 .value = &value,
169 .range = .{ .start = 0, .end = 0, .end_phase = .definition },
170 .use_positions = .empty,
171 .definition = .{
172 .point = Point.definition(0),
173 .requirement = .{ .fixed = 1 },
174 .source = .{ .fixed = 2 },
175 },
176 .order = 0,
177 .is_constant = false,
178 };
179 defer candidate.deinit(allocator);
180
181 var expected: std.ArrayListUnmanaged(UsePosition) = .empty;
182 defer expected.deinit(allocator);
183 const use_count = try drawUsize(conjecture, 1, 256, 1);
184 for (0..use_count) |insertion_index| {
185 const use = UsePosition{
186 .point = try drawPoint(conjecture),
187 .requirement = try drawRequirement(conjecture),
188 .source_blockers = @intCast(insertion_index),
189 };
190 try expected.append(allocator, use);
191 try candidate.recordUse(allocator, use.point, use.requirement, use.source_blockers);
192 }
193 std.mem.sort(UsePosition, expected.items, {}, useBefore);
194
195 try std.testing.expectEqualSlices(UsePosition, expected.items, candidate.use_positions.items);
196 try std.testing.expectEqual(expected.items[0], candidate.firstUse().?);
197
198 const query_count = try drawUsize(conjecture, 1, 128, 1);
199 for (0..query_count) |_| {
200 const point = try drawPoint(conjecture);
201 try std.testing.expectEqual(firstAtOrAfterLinear(expected.items, point), candidate.firstUseAtOrAfter(point));
202
203 const at_bounds = sliceBoundsLinear(expected.items, point, point);
204 try std.testing.expectEqualSlices(
205 UsePosition,
206 expected.items[at_bounds.first..at_bounds.last],
207 candidate.usesAt(point),
208 );
209
210 var start = point;
211 var end = try drawPoint(conjecture);
212 if (end.lessThan(start)) std.mem.swap(Point, &start, &end);
213 const range_bounds = sliceBoundsLinear(expected.items, start, end);
214 try std.testing.expectEqualSlices(
215 UsePosition,
216 expected.items[range_bounds.first..range_bounds.last],
217 candidate.usesBetween(start, end),
218 );
219
220 const fixed = FixedPosition{
221 .point = point,
222 .reg = @intCast(try drawUsize(conjecture, 0, 7, 0)),
223 .kind = @fromBackingInt(@intCast(try drawUsize(conjecture, 0, 4, 0))),
224 };
225 try std.testing.expectEqual(
226 ownsFixedPositionLinear(candidate, expected.items, fixed),
227 candidate.ownsFixedPosition(fixed),
228 );
229 }
230 }
231 };
232
233 test "property: candidate collection matches insertion order and value lookup" {
234 try hypothesis.checkNamed(CandidateCollectionProperty, "choir-regalloc-candidates", settings());
235 }
236
237 test "property: candidate uses preserve ordered query semantics" {
238 try hypothesis.checkNamed(CandidateUseProperty, "choir-regalloc-candidate-uses", useSettings());
239 }