lib/choir/src/properties/locations.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 Point = regalloc.PositionPoint;
 7 const Range = regalloc.ValueLocationRange(u8);
 8 const Index = regalloc.ValueLocationIndex(u8);
 9 
10 fn settings() hypothesis.Settings {
11     return hypothesis.Settings.quick()
12         .withSeed(0x10ca_710c_a710)
13         .withDatabase("zig-out/hypothesis-failures/choir-regalloc-locations");
14 }
15 
16 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
17     return @intCast(try conjecture.drawInteger(@intCast(min), @intCast(max), @intCast(shrink_towards)));
18 }
19 
20 fn drawPoint(conjecture: *hypothesis.ConjectureData) !Point {
21     return .{
22         .position = @intCast(try drawUsize(conjecture, 0, 79, 0)),
23         .phase = if (try conjecture.drawBoolean()) .definition else .source,
24     };
25 }
26 
27 fn drawRange(conjecture: *hypothesis.ConjectureData, value: *choir.Value) !Range {
28     const start = try drawUsize(conjecture, 0, 63, 0);
29     const span = try drawUsize(conjecture, 1, 16, 1);
30     return .{
31         .value = value,
32         .start = @intCast(start),
33         .end = @intCast(start + span),
34         .reg = @intCast(try drawUsize(conjecture, 0, 3, 0)),
35         .entry = if (try conjecture.drawBoolean()) .reload else .resident,
36         .end_phase = if (try conjecture.drawBoolean()) .definition else .source,
37     };
38 }
39 
40 fn earlier(current: ?Point, candidate: Point) Point {
41     if (current) |point| return if (candidate.lessThan(point)) candidate else point;
42     return candidate;
43 }
44 
45 pub const LocationIndexProperty = struct {
46     pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
47         var owner: u8 = 0;
48         var value = choir.Value{
49             .kind = .{ .op_result = .{ .owner = &owner, .result_number = 0 } },
50             .type = undefined,
51             .id = 0,
52         };
53         var ranges: std.ArrayListUnmanaged(Range) = .empty;
54         defer ranges.deinit(allocator);
55         var index = Index{};
56         defer index.deinit(allocator);
57 
58         const range_count = try drawUsize(conjecture, 1, 64, 1);
59         for (0..range_count) |_| {
60             const entry = try drawRange(conjecture, &value);
61             try ranges.append(allocator, entry);
62         }
63         try index.rebuild(allocator, ranges.items);
64 
65         const point = try drawPoint(conjecture);
66         const reg: u8 = @intCast(try drawUsize(conjecture, 0, 3, 0));
67         var expected_blocks = false;
68         var expected_location: ?u8 = null;
69         for (ranges.items) |entry| {
70             if (entry.blocksRegisterAt(reg, point)) expected_blocks = true;
71             if (expected_location == null and entry.coversValueAt(&value, point)) expected_location = entry.reg;
72         }
73         try std.testing.expectEqual(expected_blocks, index.registerBlocksAt(reg, point));
74         try std.testing.expectEqual(expected_location, index.valueLocationAtPoint(ranges.items, &value, point));
75 
76         const proposed = try drawRange(conjecture, &value);
77         var expected_overlap: ?Point = null;
78         for (ranges.items) |entry| {
79             if (entry.reg != proposed.reg or !entry.overlaps(proposed)) continue;
80             const overlap_start = if (entry.startPoint().lessThan(proposed.startPoint())) proposed.startPoint() else entry.startPoint();
81             expected_overlap = earlier(expected_overlap, overlap_start);
82         }
83         const actual_overlap = index.registerRangeFirstOverlapStart(
84             ranges.items,
85             &value,
86             proposed.start,
87             proposed.end,
88             proposed.reg,
89             proposed.entry,
90             proposed.end_phase,
91         );
92         try std.testing.expectEqual(expected_overlap, actual_overlap);
93     }
94 };
95 
96 test "property: value location index matches linear range queries" {
97     try hypothesis.checkNamed(LocationIndexProperty, "choir-regalloc-location-index", settings());
98 }