lib/choir/src/backends/aarch64/placement.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const shared = @import("../root.zig").regalloc;
4 const control = @import("root.zig").control;
5 const GPR = @import("root.zig").GPR;
6
7 pub const max_registers: usize = 7;
8 pub const max_frame_slots: usize = 64;
9 pub const max_live_values: usize = max_registers + max_frame_slots;
10 pub const max_values: usize = 256;
11 pub const max_operations: usize = 1024;
12 pub const max_events: usize = 3 * max_operations;
13 pub const Event = struct {
14 pub const Kind = enum { operation, next_region, end };
15 kind: Kind,
16 op: *ir.Operation,
17 depth: usize,
18 };
19 pub const slot_bytes: usize = 8;
20 pub const registers = [max_registers]GPR{ .x9, .x10, .x11, .x12, .x13, .x14, .x15 };
21
22 pub const Location = union(enum) { register: GPR, stack: u16, dead };
23 pub const Error = control.Error || error{ ValueCapacity, FrameCapacity, OperationCapacity, MissingValue };
24
25 const Entry = struct {
26 value: *ir.Value,
27 owner: *ir.Operation,
28 retained: bool,
29 range: shared.IntervalRange,
30 location: Location = .dead,
31 };
32
33 /// One immutable home per SSA result. Arguments retain their incoming homes.
34 pub const Plan = struct {
35 entries: [max_values]Entry = undefined,
36 count: usize = 0,
37 events: [max_events]Event = undefined,
38 event_count: usize = 0,
39 loops: [max_operations]shared.LoopInterval = undefined,
40 loop_count: usize = 0,
41 frame_slots: usize = 0,
42 entry_block: ?*ir.Block = null,
43 refused_operation: ?*ir.Operation = null,
44
45 pub fn storageBytes() usize {
46 return @sizeOf(Plan);
47 }
48
49 pub fn frameBytes(self: *const Plan) usize {
50 std.debug.assert(self.frame_slots <= max_frame_slots);
51 return std.mem.alignForward(usize, self.frame_slots * slot_bytes, 16);
52 }
53
54 pub fn get(self: *const Plan, value: *ir.Value) ?Location {
55 std.debug.assert(self.count <= max_values);
56 for (self.entries[0..self.count]) |entry| {
57 if (entry.value == value) return entry.location;
58 }
59 return null;
60 }
61
62 /// A fixed traversal stack linearizes regions without host recursion.
63 /// Once loop boundaries exist, each actual source use reaches the shared
64 /// loop extension through one borrowed record, without allocation.
65 pub fn build(self: *Plan, block: *ir.Block) Error!void {
66 self.* = .{ .entry_block = block };
67 const Frame = struct { next: ?*ir.Operation, owner: ?*ir.Operation = null, region: usize = 0, entry: u32 = 0 };
68 var frames: [control.max_depth + 1]Frame = undefined;
69 frames[0] = .{ .next = first(block) };
70 var depth: usize = 0;
71 var operations: usize = 0;
72 for (0..max_events) |_| {
73 const frame = &frames[depth];
74 if (frame.next) |op| {
75 self.refused_operation = op;
76 if (operations == max_operations) return error.OperationCapacity;
77 operations += 1;
78 frame.next = op.next_op;
79 const position = self.appendEvent(.operation, op, depth);
80 if (control.kind(op)) |construct| {
81 if (depth == control.max_depth) return error.DepthCapacity;
82 try control.validate(op, construct);
83 for (op.results.items) |*value| try self.define(value, op, position, true);
84 for (op.regions.items) |*region| {
85 for (region.getEntryBlock().?.arguments.items) |arg| try self.define(arg, op, position, true);
86 }
87 depth += 1;
88 frames[depth] = .{ .next = first(op.regions.items[0].getEntryBlock().?), .owner = op, .entry = position + 1 };
89 } else {
90 if (op.regions.items.len != 0) return error.ControlShape;
91 for (op.results.items) |*value| try self.define(value, op, position, false);
92 }
93 } else if (frame.owner) |owner| {
94 self.refused_operation = owner;
95 frame.region += 1;
96 if (frame.region < owner.regions.items.len) {
97 _ = self.appendEvent(.next_region, owner, depth - 1);
98 frame.next = first(owner.regions.items[frame.region].getEntryBlock().?);
99 } else {
100 const position = self.appendEvent(.end, owner, depth - 1);
101 if (control.kind(owner).? != .conditional) {
102 std.debug.assert(self.loop_count < max_operations);
103 self.loops[self.loop_count] = .{ .entry = frame.entry, .trailing = position };
104 self.loop_count += 1;
105 }
106 for (owner.results.items) |*value| try self.use(value, position);
107 for (owner.regions.items) |*region| {
108 for (region.getEntryBlock().?.arguments.items) |arg| try self.use(arg, position);
109 }
110 if (control.kind(owner).? == .counted) {
111 try self.use(owner.operands.items[1].value, position);
112 try self.use(owner.operands.items[2].value, position);
113 }
114 depth -= 1;
115 }
116 } else break;
117 } else unreachable;
118 for (self.events[0..self.event_count], 0..) |event, position| {
119 if (event.kind != .operation) continue;
120 self.refused_operation = event.op;
121 for (event.op.operands.items) |operand| try self.use(operand.value, @intCast(position));
122 }
123 try self.place();
124 self.refused_operation = null;
125 }
126
127 fn first(block: *ir.Block) ?*ir.Operation {
128 return if (block.operations.head) |op| @ptrCast(@alignCast(op)) else null;
129 }
130
131 fn appendEvent(self: *Plan, kind: Event.Kind, op: *ir.Operation, depth: usize) u32 {
132 std.debug.assert(self.event_count < max_events);
133 const position = self.event_count;
134 self.events[position] = .{ .kind = kind, .op = op, .depth = depth };
135 self.event_count += 1;
136 return @intCast(position);
137 }
138
139 fn define(self: *Plan, value: *ir.Value, owner: *ir.Operation, position: u32, retained: bool) Error!void {
140 if (self.count == max_values) return error.ValueCapacity;
141 self.entries[self.count] = .{
142 .value = value,
143 .owner = owner,
144 .retained = retained,
145 .range = .{ .start = position, .end = position, .end_phase = .definition },
146 };
147 self.count += 1;
148 }
149
150 fn use(self: *Plan, value: *ir.Value, position: u32) Error!void {
151 const entry = self.find(value) orelse {
152 if (value.getOwnerBlock() == @as(*anyopaque, self.entry_block.?)) return;
153 return error.MissingValue;
154 };
155 if (entry.range.start > position) return error.MissingValue;
156 if (position >= entry.range.end) {
157 entry.range.end = position;
158 entry.range.end_phase = .source;
159 }
160 var use_storage = [_]shared.UsePosition(GPR, u32){.{ .point = shared.PositionPoint.source(position), .requirement = .any, .source_blockers = 0 }};
161 var candidate = [_]shared.Candidate(GPR, u32){.{
162 .value = value,
163 .range = entry.range,
164 .use_positions = .{ .items = &use_storage, .capacity = use_storage.len },
165 .definition = .{ .point = shared.PositionPoint.definition(entry.range.start), .requirement = .any, .source = .any },
166 .order = 0,
167 .is_constant = false,
168 }};
169 shared.extendAcrossLoops(GPR, u32, &candidate, self.loops[0..self.loop_count]);
170 entry.range = candidate[0].range;
171 }
172
173 fn find(self: *Plan, value: *ir.Value) ?*Entry {
174 for (self.entries[0..self.count]) |*entry| {
175 if (entry.value == value) return entry;
176 }
177 return null;
178 }
179
180 /// Shared interval expiration and register selection borrow stack storage.
181 fn place(self: *Plan) Error!void {
182 var active_storage: [max_registers]shared.Active(GPR) = undefined;
183 var active: shared.ActiveSet(GPR) = .{
184 .items = .{ .items = active_storage[0..0], .capacity = active_storage.len },
185 };
186 var stack_ends: [max_frame_slots]?shared.PositionPoint = @splat(null);
187 for (self.entries[0..self.count], 0..) |*entry, index| {
188 if (!entry.retained and entry.value.hasNoUses()) continue;
189 self.refused_operation = entry.owner;
190 const start = shared.PositionPoint.definition(entry.range.start);
191 const end: shared.PositionPoint = .{ .position = entry.range.end, .phase = entry.range.end_phase };
192 for (0..max_registers) |_| {
193 if (active.takeExpiredBefore(start) == null) break;
194 }
195 if (shared.firstAvailableRegister(GPR, active, ®isters, Policy{})) |register| {
196 std.debug.assert(active.items.items.len < max_registers);
197 active.items.appendAssumeCapacity(.{
198 .start = entry.range.start,
199 .end = entry.range.end,
200 .end_phase = entry.range.end_phase,
201 .reg = register,
202 .candidate_index = index,
203 });
204 entry.location = .{ .register = register };
205 continue;
206 }
207 var placed = false;
208 for (&stack_ends, 0..) |*last, slot| {
209 if (last.*) |point| if (!point.lessThan(start)) continue;
210 last.* = end;
211 entry.location = .{ .stack = @intCast(slot) };
212 self.frame_slots = @max(self.frame_slots, slot + 1);
213 placed = true;
214 break;
215 }
216 if (!placed) return error.FrameCapacity;
217 }
218 }
219 };
220
221 const Policy = struct {
222 pub fn blocksRegister(_: Policy, _: GPR) bool {
223 return false;
224 }
225 };