lib/choir/src/backends/x64/regalloc.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const dialects = @import("../../dialects/root.zig");
4 const shared = @import("../root.zig").regalloc;
5 const registers = @import("registers/root.zig");
6 const abi = @import("abi.zig");
7 const call_plan = @import("calls.zig");
8 const scalar = @import("scalar.zig");
9
10 const GPR = registers.GPR;
11 const XMM = registers.XMM;
12 const ArithDialect = dialects.ArithDialect;
13 const FuncDialect = dialects.FuncDialect;
14 const MemrefDialect = dialects.MemrefDialect;
15 const ScfDialect = dialects.ScfDialect;
16
17 const caller_saved_homes = registers.allocatable_gprs;
18 const callee_saved_homes = [_]GPR{ .rbx, .r12, .r13, .r14, .r15 };
19 const interval_homes = caller_saved_homes ++ callee_saved_homes;
20
21 const i64_type_name = "arith.i64";
22 const index_type_name = "arith.index";
23 const bool_type_name = "arith.bool";
24
25 const eligible_mnemonics = [_][]const u8{
26 "arith.add",
27 "arith.sub",
28 "arith.mul",
29 "arith.neg",
30 "arith.abs",
31 "arith.div",
32 "arith.rem",
33 "arith.max",
34 "arith.min",
35 "arith.and",
36 "arith.or",
37 "arith.xor",
38 "arith.not",
39 "arith.shl",
40 "arith.shr",
41 "arith.ushr",
42 "arith.cmp",
43 "arith.select",
44 "arith.constant",
45 "func.call",
46 "func.syscall",
47 "scf.while",
48 "scf.condition",
49 "scf.yield",
50 "arith.addo",
51 "arith.subo",
52 "arith.mulo",
53 };
54
55 fn isOverflowOp(op: *const ir.Operation) bool {
56 inline for (.{ ArithDialect.AddoOp, ArithDialect.SuboOp, ArithDialect.MuloOp }) |Op| {
57 if (std.mem.eql(u8, op.name.name, Op.operation_name)) return true;
58 }
59 return false;
60 }
61
62 fn isEligibleOp(name: []const u8) bool {
63 if (std.mem.eql(u8, name, "func.return")) return true;
64 for (eligible_mnemonics) |mnemonic| {
65 if (std.mem.eql(u8, name, mnemonic)) return true;
66 }
67 return false;
68 }
69
70 const float_eligible_mnemonics = [_][]const u8{
71 "arith.add",
72 "arith.sub",
73 "arith.mul",
74 "arith.div",
75 "arith.neg",
76 "arith.max",
77 "arith.min",
78 };
79
80 fn isFloatEligibleOp(name: []const u8) bool {
81 for (float_eligible_mnemonics) |mnemonic| {
82 if (std.mem.eql(u8, name, mnemonic)) return true;
83 }
84 return false;
85 }
86
87 fn typeName(value: *const ir.Value) ?[]const u8 {
88 return value.type.getDialectTypeName();
89 }
90
91 fn isBool(value: *const ir.Value) bool {
92 const name = typeName(value) orelse return false;
93 return std.mem.eql(u8, name, bool_type_name);
94 }
95
96 fn isRegisterScalar(value: *const ir.Value) bool {
97 const name = typeName(value) orelse return false;
98 return std.mem.eql(u8, name, i64_type_name) or
99 std.mem.eql(u8, name, index_type_name) or
100 std.mem.eql(u8, name, bool_type_name) or
101 std.mem.eql(u8, name, "arith.i32") or
102 std.mem.eql(u8, name, "arith.u32");
103 }
104
105 fn isMemref(value: *const ir.Value) bool {
106 const name = typeName(value) orelse return false;
107 return std.mem.eql(u8, name, MemrefDialect.name);
108 }
109
110 fn isFloatScalar(value: *const ir.Value) bool {
111 const name = typeName(value) orelse return false;
112 return std.mem.eql(u8, name, "arith.f32") or std.mem.eql(u8, name, "arith.f64");
113 }
114
115 fn isPacked128(value: *const ir.Value) bool {
116 const name = typeName(value) orelse return false;
117 return packedTypeName(name);
118 }
119
120 fn packedTypeName(name: []const u8) bool {
121 const info = dialects.arith.parseVectorTypeName(name) orelse return false;
122 if (info.width == 4) {
123 return std.mem.eql(u8, info.elem_type_name, "arith.f32") or
124 std.mem.eql(u8, info.elem_type_name, "arith.i32") or
125 std.mem.eql(u8, info.elem_type_name, "arith.u32");
126 }
127 if (info.width == 2) {
128 return std.mem.eql(u8, info.elem_type_name, "arith.f64") or
129 std.mem.eql(u8, info.elem_type_name, "arith.i64") or
130 std.mem.eql(u8, info.elem_type_name, "arith.u64");
131 }
132 return false;
133 }
134
135 fn isPackedFloat128(value: *const ir.Value) bool {
136 const name = typeName(value) orelse return false;
137 const info = dialects.arith.parseVectorTypeName(name) orelse return false;
138 return (info.width == 4 and std.mem.eql(u8, info.elem_type_name, "arith.f32")) or
139 (info.width == 2 and std.mem.eql(u8, info.elem_type_name, "arith.f64"));
140 }
141
142 fn isXmmHomeable(value: *const ir.Value) bool {
143 return isFloatScalar(value) or isPacked128(value);
144 }
145
146 /// Whether the value an operation defines is the frame address a `memref.alloca` reserved.
147 ///
148 /// `memory.emitAlloca` computes that address into the frame slot the value was given and writes it
149 /// nowhere else, so a register home for it would be read before anything wrote it.
150 fn isAllocaAddress(value: *const ir.Value) bool {
151 const owner = value.getDefiningOp() orelse return false;
152 const op: *ir.Operation = @ptrCast(@alignCast(owner));
153 return std.mem.eql(u8, op.name.name, MemrefDialect.AllocaOp.operation_name);
154 }
155
156 fn isGprHomeable(value: *const ir.Value) bool {
157 if (isAllocaAddress(value)) return false;
158 return isRegisterScalar(value) or isMemref(value);
159 }
160
161 fn isCarriedScalar(value: *const ir.Value) bool {
162 return isGprHomeable(value) or isFloatScalar(value);
163 }
164
165 fn isBlockArgumentEligible(value: *const ir.Value) bool {
166 return isCarriedScalar(value);
167 }
168
169 fn allResultsRegisterScalar(op: *ir.Operation) bool {
170 for (op.results.items) |*result| {
171 if (!isRegisterScalar(result)) return false;
172 }
173 return true;
174 }
175
176 fn allOperandsRegisterScalar(op: *ir.Operation) bool {
177 for (op.operands.items) |operand| {
178 if (!isRegisterScalar(operand.value)) return false;
179 }
180 return true;
181 }
182
183 fn allResultsFloatScalar(op: *ir.Operation) bool {
184 for (op.results.items) |*result| {
185 if (!isFloatScalar(result)) return false;
186 }
187 return true;
188 }
189
190 fn allOperandsFloatScalar(op: *ir.Operation) bool {
191 for (op.operands.items) |operand| {
192 if (!isFloatScalar(operand.value)) return false;
193 }
194 return true;
195 }
196
197 fn allOperandsCarriedScalar(op: *ir.Operation) bool {
198 for (op.operands.items) |operand| {
199 if (!isCarriedScalar(operand.value)) return false;
200 }
201 return true;
202 }
203
204 fn allResultsCarriedScalar(op: *ir.Operation) bool {
205 for (op.results.items) |*result| {
206 if (!isCarriedScalar(result)) return false;
207 }
208 return true;
209 }
210
211 fn allResultsPacked128(op: *ir.Operation) bool {
212 for (op.results.items) |*result| {
213 if (!isPacked128(result)) return false;
214 }
215 return true;
216 }
217
218 fn allOperandsPacked128(op: *ir.Operation) bool {
219 for (op.operands.items) |operand| {
220 if (!isPacked128(operand.value)) return false;
221 }
222 return true;
223 }
224
225 fn isPackedEligibleOp(op: *ir.Operation) bool {
226 const name = op.name.name;
227 if (std.mem.eql(u8, name, ArithDialect.AddOp.operation_name) or
228 std.mem.eql(u8, name, ArithDialect.SubOp.operation_name) or
229 std.mem.eql(u8, name, ArithDialect.AndOp.operation_name) or
230 std.mem.eql(u8, name, ArithDialect.OrOp.operation_name) or
231 std.mem.eql(u8, name, ArithDialect.XorOp.operation_name))
232 {
233 return allResultsPacked128(op) and allOperandsPacked128(op);
234 }
235 if (std.mem.eql(u8, name, ArithDialect.MulOp.operation_name) or
236 std.mem.eql(u8, name, ArithDialect.DivOp.operation_name))
237 {
238 if (!allResultsPacked128(op) or !allOperandsPacked128(op)) return false;
239 if (std.mem.eql(u8, name, ArithDialect.DivOp.operation_name)) {
240 const result = op.getResult(0) orelse return false;
241 return isPackedFloat128(result);
242 }
243 return true;
244 }
245 if (std.mem.eql(u8, name, ArithDialect.SplatOp.operation_name)) {
246 if (op.operands.items.len != 1 or op.results.items.len != 1) return false;
247 const operand = op.getOperand(0) orelse return false;
248 const result = op.getResult(0) orelse return false;
249 return (isFloatScalar(operand) or isRegisterScalar(operand)) and isPacked128(result);
250 }
251 if (std.mem.eql(u8, name, ArithDialect.VecConstantOp.operation_name)) {
252 return op.operands.items.len == 0 and allResultsPacked128(op);
253 }
254 return false;
255 }
256
257 fn isEligibleCast(op: *ir.Operation) bool {
258 if (op.operands.items.len != 1 or op.results.items.len != 1) return false;
259 return allOperandsRegisterScalar(op) and allResultsRegisterScalar(op);
260 }
261
262 fn isScalarWord(value: *const ir.Value) bool {
263 const name = typeName(value) orelse return false;
264 return std.mem.eql(u8, name, "arith.i32") or std.mem.eql(u8, name, "arith.u32") or
265 std.mem.eql(u8, name, "arith.i64") or std.mem.eql(u8, name, "arith.u64");
266 }
267
268 fn isEligibleBitcast(op: *ir.Operation) bool {
269 if (op.operands.items.len != 1 or op.results.items.len != 1) return false;
270 const operand = op.getOperand(0) orelse return false;
271 const result = op.getResult(0) orelse return false;
272 if (isScalarWord(operand) and isFloatScalar(result)) return true;
273 if (isFloatScalar(operand) and isScalarWord(result)) return true;
274 return false;
275 }
276
277 /// A static `memref.alloca` reserves a frame slot and computes its address. It costs the frame the
278 /// bytes its type states whether or not this allocator runs, because `Emitter.collectSlotsInRegion`
279 /// reserves the payload after allocation is over, so admitting it here moves no byte of the cell
280 /// and only stops the rest of the function from being refused over it.
281 ///
282 /// A dynamic `memref.alloca` carries the size as its one operand and moves the stack pointer, which
283 /// this allocator's frame reasoning does not model, so it stays refused.
284 fn isEligibleStaticAlloca(op: *ir.Operation) bool {
285 if (op.operands.items.len != 0) return false;
286 if (op.results.items.len != 1) return false;
287 const result = op.getResult(0) orelse return false;
288 return isMemref(result);
289 }
290
291 fn isEligibleMemrefLoad(op: *ir.Operation) bool {
292 if (op.operands.items.len != 2 or op.results.items.len != 1) return false;
293 const memref_val = op.getOperand(0) orelse return false;
294 const index_val = op.getOperand(1) orelse return false;
295 if (!isMemref(memref_val) or !isRegisterScalar(index_val)) return false;
296 const result = op.getResult(0) orelse return false;
297 return isRegisterScalar(result) or isFloatScalar(result) or isPacked128(result);
298 }
299
300 fn isEligibleMemrefStore(op: *ir.Operation) bool {
301 if (op.operands.items.len != 3 or op.results.items.len != 0) return false;
302 const value = op.getOperand(0) orelse return false;
303 const memref_val = op.getOperand(1) orelse return false;
304 const index_val = op.getOperand(2) orelse return false;
305 if (!isMemref(memref_val) or !isRegisterScalar(index_val)) return false;
306 return isRegisterScalar(value) or isFloatScalar(value) or isPacked128(value);
307 }
308
309 fn isEligibleScalarOp(op: *ir.Operation) bool {
310 const name = op.name.name;
311 if (std.mem.eql(u8, name, ArithDialect.ConstantOp.operation_name)) {
312 for (op.results.items) |*result| {
313 if (!isRegisterScalar(result) and !isFloatScalar(result)) return false;
314 }
315 return op.operands.items.len == 0;
316 }
317 if (std.mem.eql(u8, name, ArithDialect.CastOp.operation_name)) {
318 return isEligibleCast(op);
319 }
320 if (std.mem.eql(u8, name, ArithDialect.BitcastOp.operation_name)) {
321 return isEligibleBitcast(op);
322 }
323 if (std.mem.eql(u8, name, MemrefDialect.AllocaOp.operation_name)) {
324 return isEligibleStaticAlloca(op);
325 }
326 if (std.mem.eql(u8, name, MemrefDialect.LoadOp.operation_name)) {
327 return isEligibleMemrefLoad(op);
328 }
329 if (std.mem.eql(u8, name, MemrefDialect.StoreOp.operation_name)) {
330 return isEligibleMemrefStore(op);
331 }
332
333 if (isEligibleOp(name) and allResultsRegisterScalar(op) and allOperandsRegisterScalar(op)) return true;
334 if (isFloatEligibleOp(name) and allResultsFloatScalar(op) and allOperandsFloatScalar(op)) return true;
335 return isPackedEligibleOp(op);
336 }
337
338 const BlockKind = enum {
339 entry,
340 nested,
341 if_branch,
342 };
343
344 fn isEligibleOperation(op: *ir.Operation, kind: BlockKind) bool {
345 if (op.successors.items.len != 0) return false;
346
347 const name = op.name.name;
348 if (op.regions.items.len != 0) return false;
349 if (std.mem.eql(u8, name, FuncDialect.ReturnOp.operation_name)) {
350 return kind == .entry and allOperandsRegisterScalar(op);
351 }
352 if (std.mem.eql(u8, name, ScfDialect.YieldOp.operation_name)) {
353 return kind != .entry and allOperandsCarriedScalar(op);
354 }
355 if (std.mem.eql(u8, name, ScfDialect.ConditionOp.operation_name)) {
356 return kind == .nested and allOperandsRegisterScalar(op);
357 }
358 return isEligibleScalarOp(op);
359 }
360
361 /// The facts one operation may declare that this probe reads without allocating. An operation
362 /// declaring more is refused, which costs it register allocation and never changes what it means.
363 /// No allocator or configurable limit reaches this probe, so the side an operation falls on is
364 /// a property of the program alone.
365 pub const ordered_probe_facts = 32;
366
367 /// Whether an operation declares an ordered event, which is the effect record an atomic or a
368 /// volatile access carries (`memref.atomic_load` and `memref.atomic_store` today).
369 ///
370 /// A function holding one is refused by `isEligibleBlock`, so every value in it stays in its frame
371 /// slot. `memory.zig` relies on exactly that: its atomic path addresses memory through the fixed
372 /// scratch registers rcx, rdx and r8, which clobber nothing only while nothing is register homed.
373 /// The test is the effect record and not the mnemonic, so an ordered operation added after this
374 /// line inherits the refusal instead of quietly falling through a list it was never added to.
375 ///
376 /// An operation this cannot read (no interface capacity, more facts than the probe holds, or a
377 /// collection that refuses) is treated as ordered. The conservative answer costs allocation and
378 /// never emits a different program.
379 fn holdsOrderedEffect(op: *ir.Operation) bool {
380 const vtable = op.getInterface(ir.interfaces.EffectOpInterface) orelse return false;
381 const count = vtable.capacity.count(
382 op.getNumOperands(),
383 op.getNumResults(),
384 op.getNumRegions(),
385 ) orelse return true;
386 if (count > ordered_probe_facts) return true;
387 var storage: [ordered_probe_facts]ir.interfaces.effects.Fact = undefined;
388 const facts = ir.interfaces.effects.collectInto(op, storage[0..count]) catch return true;
389 for (facts.records) |record| switch (record) {
390 .event => |event| if (event.ordered) return true,
391 else => {},
392 };
393 return false;
394 }
395
396 fn singleRegionBlock(region: *ir.Region) ?*ir.Block {
397 const block = region.blocks.head orelse return null;
398 if (block.next != null) return null;
399 return block;
400 }
401
402 fn isEligibleBlock(block: *ir.Block, kind: BlockKind) bool {
403 for (block.arguments.items) |arg| {
404 if (!isBlockArgumentEligible(arg)) return false;
405 }
406
407 var saw_terminator = false;
408 var op_iter = block.operations.head;
409 while (op_iter) |op_ptr| {
410 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
411 const name = op.name.name;
412
413 if (holdsOrderedEffect(op)) return false;
414
415 if (std.mem.eql(u8, name, ScfDialect.IfOp.operation_name)) {
416 if (op.successors.items.len != 0) return false;
417 if (!allResultsRegisterScalar(op)) return false;
418 if (op.operands.items.len != 1) return false;
419 if (!isBool(op.operands.items[0].value)) return false;
420 if (op.results.items.len != 0 and op.regions.items.len != 2) return false;
421
422 const if_op = ScfDialect.IfOp{ .op = op };
423 if (!isEligibleBlock(if_op.getThenBlock(), .if_branch)) return false;
424 if (if_op.getElseBlock()) |else_block| {
425 if (!isEligibleBlock(else_block, .if_branch)) return false;
426 } else if (op.results.items.len != 0) {
427 return false;
428 }
429
430 op_iter = op.next_op;
431 continue;
432 }
433
434 if (std.mem.eql(u8, name, ScfDialect.WhileOp.operation_name)) {
435 if (op.successors.items.len != 0) return false;
436 if (!allResultsRegisterScalar(op)) return false;
437 if (!allOperandsRegisterScalar(op)) return false;
438 for (op.regions.items) |*nested| {
439 const nested_block = singleRegionBlock(nested) orelse return false;
440 if (!isEligibleBlock(nested_block, .nested)) return false;
441 }
442
443 op_iter = op.next_op;
444 continue;
445 }
446
447 if (std.mem.eql(u8, name, ScfDialect.ForOp.operation_name)) {
448 if (op.successors.items.len != 0) return false;
449 if (op.operands.items.len < 3) return false;
450 if (!allResultsCarriedScalar(op)) return false;
451 if (!allOperandsCarriedScalar(op)) return false;
452 for (0..3) |bound_index| {
453 const bound = op.getOperand(bound_index) orelse return false;
454 if (!isRegisterScalar(bound)) return false;
455 }
456 for (op.regions.items) |*nested| {
457 const nested_block = singleRegionBlock(nested) orelse return false;
458 if (!isEligibleBlock(nested_block, .nested)) return false;
459 }
460
461 op_iter = op.next_op;
462 continue;
463 }
464
465 if (!isEligibleOperation(op, kind)) return false;
466 if (kind == .entry and std.mem.eql(u8, name, FuncDialect.ReturnOp.operation_name)) {
467 saw_terminator = true;
468 }
469 if (kind == .if_branch and std.mem.eql(u8, name, ScfDialect.YieldOp.operation_name)) {
470 saw_terminator = true;
471 }
472 op_iter = op.next_op;
473 }
474 return switch (kind) {
475 .entry, .if_branch => saw_terminator,
476 .nested => true,
477 };
478 }
479
480 fn isEligibleFunction(region: *ir.Region) bool {
481 const block = singleRegionBlock(region) orelse return false;
482 return isEligibleBlock(block, .entry);
483 }
484
485 const GprMask = u16;
486 const XmmMask = u16;
487
488 pub const PositionPhase = shared.PositionPhase;
489
490 const ReloadRangeEnd = struct {
491 end: u32,
492 phase: PositionPhase,
493 };
494 pub const PositionPoint = shared.PositionPoint;
495 pub const ValueLocationRangeEntry = shared.ValueLocationRangeEntry;
496 pub const ValueLocationRangeExit = shared.ValueLocationRangeExit;
497 pub const ValueLocationRange = shared.ValueLocationRange(GPR);
498 pub const XmmValueLocationRange = shared.ValueLocationRange(XMM);
499 pub const ValueLocationIndex = shared.ValueLocationIndex(GPR);
500 pub const XmmValueLocationIndex = shared.ValueLocationIndex(XMM);
501
502 const FixedPositionKind = shared.FixedPositionKind;
503
504 pub fn Core(
505 comptime Register: type,
506 comptime Mask: type,
507 comptime promotable: fn (value: *const ir.Value) bool,
508 ) type {
509 return struct {
510 const Requirement: type = shared.Requirement(Register);
511 const UsePosition: type = shared.UsePosition(Register, Mask);
512 const FixedPosition: type = shared.FixedPosition(Register);
513 const FixedPositionIndex: type = shared.FixedPositionIndex(Register);
514 pub const Candidate: type = shared.Candidate(Register, Mask);
515 pub const Candidates: type = shared.Candidates(Register, Mask);
516 const Active: type = shared.Active(Register);
517 const ActiveSet: type = shared.ActiveSet(Register);
518 const AvailableRegister: type = shared.AvailableRegister(Register);
519 const LocationRange: type = shared.ValueLocationRange(Register);
520 const LocationIndex: type = shared.ValueLocationIndex(Register);
521
522 const ReloadChoice = struct {
523 reg: Register,
524 end: ReloadRangeEnd,
525 };
526
527 const RegisterSelectionPolicy = struct {
528 candidate: Candidate,
529 fixed_positions: FixedPositionIndex,
530 loop_intervals: []const shared.LoopInterval,
531
532 pub fn blocksRegister(self: @This(), reg: Register) bool {
533 return candidateConflictsWithRegisterConstraints(self.candidate, self.fixed_positions, reg);
534 }
535
536 pub fn availableUntil(self: @This(), reg: Register) ?PositionPoint {
537 const until = residentAvailableUntil(self.candidate, self.fixed_positions, reg) orelse return null;
538 if (shared.rangeCrossesLoopEntry(self.candidate.start(), self.candidate.end(), self.loop_intervals) and
539 until.lessThan(self.candidate.endPoint())) return null;
540 return until;
541 }
542
543 pub fn canEvict(self: @This(), victim: Candidate) bool {
544 if (shared.evictionUnsafeAt(victim.start(), self.candidate.start(), self.loop_intervals)) return false;
545 return candidateHasHigherSpillPriority(self.candidate, victim);
546 }
547
548 pub fn prefersVictim(_: @This(), victim: Candidate, current: Candidate) bool {
549 return candidateHasLowerSpillPriority(victim, current);
550 }
551 };
552
553 inline fn locations(emitter: anytype) *std.AutoHashMapUnmanaged(*ir.Value, Register) {
554 if (comptime Register == GPR) return &emitter.value_locations;
555 return &emitter.xmm_locations;
556 }
557
558 inline fn locationRanges(emitter: anytype) *std.ArrayListUnmanaged(LocationRange) {
559 if (comptime Register == GPR) return &emitter.value_location_ranges;
560 return &emitter.xmm_location_ranges;
561 }
562
563 inline fn locationIndex(emitter: anytype) *LocationIndex {
564 if (comptime Register == GPR) return &emitter.value_location_index;
565 return &emitter.xmm_location_index;
566 }
567
568 fn appendCandidate(
569 candidates: *Candidates,
570 allocator: std.mem.Allocator,
571 value: *ir.Value,
572 start: u32,
573 order: *u32,
574 is_constant: bool,
575 definition_requirement: Requirement,
576 definition_source: Requirement,
577 ) !void {
578 if (!promotable(value)) return;
579 const start_phase = shared.valueStartPhase(value);
580 try candidates.append(allocator, .{
581 .value = value,
582 .range = .{
583 .start = start,
584 .end = start,
585 .end_phase = start_phase,
586 },
587 .use_positions = .empty,
588 .definition = .{
589 .point = .{ .position = start, .phase = start_phase },
590 .requirement = definition_requirement,
591 .source = definition_source,
592 },
593 .order = order.*,
594 .is_constant = is_constant,
595 });
596 order.* += 1;
597 }
598
599 fn appendFixedPosition(
600 fixed_positions: *std.ArrayListUnmanaged(FixedPosition),
601 allocator: std.mem.Allocator,
602 position: u32,
603 kind: FixedPositionKind,
604 requirement: Requirement,
605 ) !void {
606 switch (requirement) {
607 .any => {},
608 .fixed => |reg| {
609 try fixed_positions.append(allocator, .{
610 .point = shared.fixedPositionPoint(position, kind),
611 .reg = reg,
612 .kind = kind,
613 });
614 },
615 }
616 }
617 fn regBit(reg: Register) Mask {
618 return @as(Mask, 1) << @intCast(reg.id());
619 }
620
621 fn maskHasReg(mask: Mask, reg: Register) bool {
622 return (mask & regBit(reg)) != 0;
623 }
624 fn recordUse(
625 candidates: *Candidates,
626 allocator: std.mem.Allocator,
627 value: *ir.Value,
628 point: PositionPoint,
629 requirement: Requirement,
630 source_blockers: Mask,
631 ) !void {
632 const candidate = candidates.getPtr(value) orelse return;
633 try candidate.recordUse(allocator, point, requirement, source_blockers);
634 }
635
636 fn recordFixedSourceUse(
637 candidates: *Candidates,
638 fixed_positions: *std.ArrayListUnmanaged(FixedPosition),
639 allocator: std.mem.Allocator,
640 value: *ir.Value,
641 point: PositionPoint,
642 reg: Register,
643 kind: FixedPositionKind,
644 source_blockers: Mask,
645 ) !void {
646 const requirement: Requirement = .{ .fixed = reg };
647 try recordUse(candidates, allocator, value, point, requirement, source_blockers);
648 try appendFixedPosition(fixed_positions, allocator, point.position, kind, requirement);
649 }
650 fn appendScratchClobbers(
651 fixed_positions: *std.ArrayListUnmanaged(FixedPosition),
652 allocator: std.mem.Allocator,
653 position: u32,
654 regs: []const Register,
655 ) !void {
656 for (regs) |reg| {
657 try fixed_positions.append(allocator, .{ .point = shared.fixedPositionPoint(position, .clobber), .reg = reg, .kind = .clobber });
658 }
659 }
660 fn verifyAllocation(emitter: anytype, candidates: []const Candidate, fixed_positions: FixedPositionIndex) !void {
661 const Verifier = shared.AllocationVerifier(Register, Mask);
662 var verifier = try Verifier.init(emitter.allocator, .{
663 .ranges = locationRanges(emitter).items,
664 .candidates = candidates,
665 .fixed_positions = fixed_positions,
666 });
667 defer verifier.deinit(emitter.allocator);
668 verifier.activate() catch unreachable;
669 try verifier.verify();
670 }
671
672 fn appendValueLocationRange(
673 emitter: anytype,
674 value: *ir.Value,
675 start: u32,
676 end: u32,
677 reg: Register,
678 entry: ValueLocationRangeEntry,
679 end_phase: PositionPhase,
680 exit: ValueLocationRangeExit,
681 ) !void {
682 const ranges = locationRanges(emitter);
683 const old_len = ranges.items.len;
684 try shared.appendValueLocationRange(
685 Register,
686 ranges,
687 emitter.allocator,
688 value,
689 start,
690 end,
691 reg,
692 entry,
693 end_phase,
694 exit,
695 );
696 if (ranges.items.len != old_len) {
697 locationIndex(emitter).append(old_len, ranges.items[old_len]);
698 }
699 }
700
701 fn closeActiveRange(
702 emitter: anytype,
703 candidates: []const Candidate,
704 active: Active,
705 end: u32,
706 end_phase: PositionPhase,
707 exit: ValueLocationRangeExit,
708 ) !void {
709 const candidate = candidates[active.candidate_index];
710 try appendValueLocationRange(emitter, candidate.value, active.start, end, active.reg, .resident, end_phase, exit);
711 }
712
713 fn expireActive(emitter: anytype, active: *ActiveSet, candidates: []const Candidate, point: PositionPoint) !void {
714 while (active.takeExpiredBefore(point)) |expired| {
715 const candidate = candidates[expired.candidate_index];
716 try closeActiveRange(emitter, candidates, expired, expired.end + 1, expired.end_phase, activeRangeExit(expired, candidate));
717 }
718 }
719
720 fn closeRemainingActiveRanges(emitter: anytype, active: *ActiveSet, candidates: []const Candidate) !void {
721 while (active.pop()) |entry| {
722 const candidate = candidates[entry.candidate_index];
723 try closeActiveRange(emitter, candidates, entry, entry.end + 1, entry.end_phase, activeRangeExit(entry, candidate));
724 }
725 }
726
727 fn activeRangeExit(active: Active, candidate: Candidate) ValueLocationRangeExit {
728 return if (active.endPoint().rank() == candidate.endPoint().rank()) .retain else .spill;
729 }
730
731 fn valueHasRangeAtPoint(emitter: anytype, value: *ir.Value, point: PositionPoint) bool {
732 return locationIndex(emitter).valueHasRangeAtPoint(locationRanges(emitter).items, value, point);
733 }
734
735 fn registerBlocksAt(emitter: anytype, reg: Register, point: PositionPoint) bool {
736 return locationIndex(emitter).registerBlocksAt(reg, point);
737 }
738
739 fn reloadRegisterAvailableAtUse(emitter: anytype, use: UsePosition, reg: Register) bool {
740 if (maskHasReg(use.source_blockers, reg)) return false;
741 if (registerBlocksAt(emitter, reg, use.point)) return false;
742 return true;
743 }
744
745 fn reloadLocationRange(
746 candidate: Candidate,
747 use: UsePosition,
748 end: u32,
749 end_phase: PositionPhase,
750 reg: Register,
751 ) LocationRange {
752 return .{
753 .value = candidate.value,
754 .start = use.point.position,
755 .end = end,
756 .reg = reg,
757 .entry = .reload,
758 .end_phase = end_phase,
759 };
760 }
761
762 fn reloadRangeEndPoint(end: ReloadRangeEnd) PositionPoint {
763 return .{ .position = end.end - 1, .phase = end.phase };
764 }
765
766 fn reloadRangeEndBeforePoint(point: PositionPoint) ReloadRangeEnd {
767 return switch (point.phase) {
768 .source => .{ .end = point.position, .phase = .definition },
769 .definition => .{ .end = point.position + 1, .phase = .source },
770 };
771 }
772
773 fn limitReloadRangeEnd(limit: *ReloadRangeEnd, point: PositionPoint) void {
774 const candidate = reloadRangeEndBeforePoint(point);
775 if (candidate.end == 0) return;
776 if (reloadRangeEndPoint(candidate).lessThan(reloadRangeEndPoint(limit.*))) limit.* = candidate;
777 }
778
779 fn firstReloadRangeUseBlocker(
780 candidate: Candidate,
781 use: UsePosition,
782 end: u32,
783 end_phase: PositionPhase,
784 reg: Register,
785 ) ?PositionPoint {
786 const proposed = reloadLocationRange(candidate, use, end, end_phase, reg);
787 for (candidate.usesBetween(proposed.startPoint(), proposed.endPoint())) |candidate_use| {
788 if (!maskHasReg(candidate_use.source_blockers, reg)) continue;
789 return candidate_use.point;
790 }
791 return null;
792 }
793
794 fn reloadRangeEnd(
795 emitter: anytype,
796 candidate: Candidate,
797 fixed_positions: FixedPositionIndex,
798 use: UsePosition,
799 reg: Register,
800 loop_intervals: []const shared.LoopInterval,
801 ) ReloadRangeEnd {
802 const full_end = candidate.locationRangeEnd();
803 const full_phase = candidate.endPhase();
804 var limit = ReloadRangeEnd{ .end = full_end, .phase = full_phase };
805
806 if (shared.innermostTrailing(use.point.position, loop_intervals)) |trailing| {
807 const clamp = ReloadRangeEnd{ .end = trailing + 1, .phase = .source };
808 if (reloadRangeEndPoint(clamp).lessThan(reloadRangeEndPoint(limit))) limit = clamp;
809 }
810
811 if (locationIndex(emitter).registerRangeFirstOverlapStart(
812 locationRanges(emitter).items,
813 candidate.value,
814 use.point.position,
815 full_end,
816 reg,
817 .reload,
818 full_phase,
819 )) |point| {
820 limitReloadRangeEnd(&limit, point);
821 }
822 if (shared.candidateRangeFixedConflictStart(
823 Register,
824 Mask,
825 candidate,
826 fixed_positions,
827 reloadLocationRange(candidate, use, full_end, full_phase, reg),
828 )) |point| {
829 limitReloadRangeEnd(&limit, point);
830 }
831 if (firstReloadRangeUseBlocker(candidate, use, full_end, full_phase, reg)) |point| {
832 limitReloadRangeEnd(&limit, point);
833 }
834
835 const single_use = ReloadRangeEnd{ .end = use.point.position + 1, .phase = use.point.phase };
836 if (reloadRangeEndPoint(limit).lessThan(reloadRangeEndPoint(single_use))) return single_use;
837 return limit;
838 }
839
840 fn chooseBetterReloadChoice(best: ?ReloadChoice, choice: ReloadChoice) ReloadChoice {
841 return if (best) |current| choice: {
842 break :choice if (reloadRangeEndPoint(current.end).lessThan(reloadRangeEndPoint(choice.end))) choice else current;
843 } else choice;
844 }
845
846 fn reloadChoiceForRegister(
847 emitter: anytype,
848 candidate: Candidate,
849 fixed_positions: FixedPositionIndex,
850 use: UsePosition,
851 reg: Register,
852 loop_intervals: []const shared.LoopInterval,
853 ) ?ReloadChoice {
854 if (!reloadRegisterAvailableAtUse(emitter, use, reg)) return null;
855 const end = reloadRangeEnd(emitter, candidate, fixed_positions, use, reg, loop_intervals);
856 if (shared.candidateRangeConflictsWithFixedPositions(
857 Register,
858 Mask,
859 candidate,
860 fixed_positions,
861 reloadLocationRange(candidate, use, end.end, end.phase, reg),
862 )) return null;
863 return .{ .reg = reg, .end = end };
864 }
865
866 fn reloadChoiceForUse(
867 emitter: anytype,
868 candidate: Candidate,
869 fixed_positions: FixedPositionIndex,
870 use: UsePosition,
871 homes: []const Register,
872 loop_intervals: []const shared.LoopInterval,
873 ) ?ReloadChoice {
874 switch (use.requirement) {
875 .fixed => |reg| {
876 return reloadChoiceForRegister(emitter, candidate, fixed_positions, use, reg, loop_intervals);
877 },
878 .any => {
879 var best: ?ReloadChoice = null;
880 for (homes) |reg| {
881 const choice = reloadChoiceForRegister(emitter, candidate, fixed_positions, use, reg, loop_intervals) orelse continue;
882 best = chooseBetterReloadChoice(best, choice);
883 }
884 return best;
885 },
886 }
887 }
888
889 fn appendReloadRanges(
890 emitter: anytype,
891 candidates: []const Candidate,
892 fixed_positions: FixedPositionIndex,
893 homes: []const Register,
894 loop_intervals: []const shared.LoopInterval,
895 ) !void {
896 for (candidates) |candidate| {
897 if (candidate.useCount() == 0) continue;
898 if (locations(emitter).contains(candidate.value)) continue;
899 for (candidate.use_positions.items) |use| {
900 if (valueHasRangeAtPoint(emitter, candidate.value, use.point)) continue;
901 const choice = reloadChoiceForUse(emitter, candidate, fixed_positions, use, homes, loop_intervals) orelse continue;
902 try appendValueLocationRange(emitter, candidate.value, use.point.position, choice.end.end, choice.reg, .reload, choice.end.phase, .retain);
903 markUsed(emitter, choice.reg);
904 }
905 }
906 }
907
908 fn candidateConflictsWithRegisterConstraints(candidate: Candidate, fixed_positions: FixedPositionIndex, reg: Register) bool {
909 for (candidate.use_positions.items) |use| {
910 if (maskHasReg(use.source_blockers, reg)) return true;
911 }
912 return candidate.conflictsWithFixedPositions(fixed_positions, reg);
913 }
914
915 fn residentLocationRange(candidate: Candidate, reg: Register) LocationRange {
916 return .{
917 .value = candidate.value,
918 .start = candidate.start(),
919 .end = candidate.locationRangeEnd(),
920 .reg = reg,
921 .entry = .resident,
922 .end_phase = candidate.endPhase(),
923 };
924 }
925
926 fn firstCandidateSourceBlocker(candidate: Candidate, reg: Register) ?PositionPoint {
927 for (candidate.use_positions.items) |use| {
928 if (!maskHasReg(use.source_blockers, reg)) continue;
929 return use.point;
930 }
931 return null;
932 }
933
934 fn firstResidentConstraintStart(candidate: Candidate, fixed_positions: FixedPositionIndex, reg: Register) ?PositionPoint {
935 var first = shared.candidateRangeFixedConflictStart(
936 Register,
937 Mask,
938 candidate,
939 fixed_positions,
940 residentLocationRange(candidate, reg),
941 );
942 if (firstCandidateSourceBlocker(candidate, reg)) |point| {
943 first = earlierPoint(first, point);
944 }
945 return first;
946 }
947
948 fn residentAvailableUntil(candidate: Candidate, fixed_positions: FixedPositionIndex, reg: Register) ?PositionPoint {
949 const first_constraint = firstResidentConstraintStart(candidate, fixed_positions, reg) orelse return candidate.endPoint();
950 if (!candidate.startPoint().lessThan(first_constraint)) return null;
951 if (first_constraint.position == 0) return null;
952 const until = PositionPoint.definition(first_constraint.position - 1);
953 if (until.lessThan(candidate.startPoint())) return null;
954 return until;
955 }
956
957 fn requirementSpillWeight(requirement: Requirement) u64 {
958 return switch (requirement) {
959 .any => 1,
960 .fixed => 4,
961 };
962 }
963
964 fn candidateSpillWeight(candidate: Candidate) u64 {
965 var weight: u64 = if (candidate.is_constant) 1 else 2;
966 weight += requirementSpillWeight(candidate.definition.requirement);
967 weight += requirementSpillWeight(candidate.definition.source);
968 for (candidate.use_positions.items) |use| {
969 weight += 8 * requirementSpillWeight(use.requirement);
970 weight += @popCount(use.source_blockers);
971 }
972 return weight;
973 }
974
975 fn candidateLength(candidate: Candidate) u64 {
976 return @max(1, @as(u64, candidate.end() - candidate.start()));
977 }
978
979 fn candidateHasEarlierFutureUse(candidate: Candidate, victim: Candidate) ?bool {
980 const point = candidate.startPoint();
981 const candidate_use = candidate.firstUseAtOrAfter(point) orelse return false;
982 const victim_use = victim.firstUseAtOrAfter(point) orelse return true;
983 if (candidate_use.point.rank() == victim_use.point.rank()) return null;
984 return candidate_use.point.lessThan(victim_use.point);
985 }
986
987 fn candidateHasHigherSpillPriority(candidate: Candidate, victim: Candidate) bool {
988 if (candidateHasEarlierFutureUse(candidate, victim)) |higher| return higher;
989 const candidate_weight = candidateSpillWeight(candidate);
990 const victim_weight = candidateSpillWeight(victim);
991 const candidate_score = candidate_weight * candidateLength(victim);
992 const victim_score = victim_weight * candidateLength(candidate);
993 if (candidate_score != victim_score) return candidate_score > victim_score;
994 if (candidate_weight != victim_weight) return candidate_weight > victim_weight;
995 return candidate.end() < victim.end();
996 }
997
998 fn candidateHasLowerSpillPriority(candidate: Candidate, victim: Candidate) bool {
999 return candidateHasHigherSpillPriority(victim, candidate);
1000 }
1001
1002 fn registerSelectionPolicy(
1003 candidate: Candidate,
1004 fixed_positions: FixedPositionIndex,
1005 loop_intervals: []const shared.LoopInterval,
1006 ) RegisterSelectionPolicy {
1007 return .{ .candidate = candidate, .fixed_positions = fixed_positions, .loop_intervals = loop_intervals };
1008 }
1009
1010 fn bestFree(
1011 active: ActiveSet,
1012 fixed_positions: FixedPositionIndex,
1013 candidate: Candidate,
1014 homes: []const Register,
1015 loop_intervals: []const shared.LoopInterval,
1016 ) ?AvailableRegister {
1017 return shared.bestAvailableRegister(Register, active, homes, registerSelectionPolicy(candidate, fixed_positions, loop_intervals));
1018 }
1019
1020 fn evictionCandidate(
1021 active: []const Active,
1022 candidates: []const Candidate,
1023 fixed_positions: FixedPositionIndex,
1024 candidate: Candidate,
1025 loop_intervals: []const shared.LoopInterval,
1026 ) ?usize {
1027 return shared.evictionCandidateIndex(Register, Candidate, active, candidates, registerSelectionPolicy(candidate, fixed_positions, loop_intervals));
1028 }
1029
1030 fn markUsed(emitter: anytype, reg: Register) void {
1031 if (comptime Register != GPR) return;
1032 if (!reg.isCalleeSaved() or reg == .rbp) return;
1033 for (emitter.used_callee_saved_regs[0..emitter.reserved_callee_saved]) |used| {
1034 if (used == reg) return;
1035 }
1036 emitter.used_callee_saved_regs[emitter.reserved_callee_saved] = reg;
1037 emitter.reserved_callee_saved += 1;
1038 }
1039
1040 fn prepareLocationIndex(
1041 emitter: anytype,
1042 candidates: []const Candidate,
1043 homes: []const Register,
1044 ) !void {
1045 var value_capacity: usize = 0;
1046 var position_count: usize = 0;
1047 var range_capacity: usize = 0;
1048 for (candidates) |candidate| {
1049 const use_count = candidate.useCount();
1050 if (use_count == 0) continue;
1051 value_capacity = std.math.add(usize, value_capacity, 1) catch
1052 return error.OutOfMemory;
1053 position_count = @max(
1054 position_count,
1055 @as(usize, candidate.locationRangeEnd()) + 1,
1056 );
1057 const candidate_capacity = std.math.add(usize, use_count, 1) catch
1058 return error.OutOfMemory;
1059 range_capacity = std.math.add(usize, range_capacity, candidate_capacity) catch
1060 return error.OutOfMemory;
1061 }
1062 try locationIndex(emitter).prepare(
1063 emitter.allocator,
1064 value_capacity,
1065 position_count,
1066 range_capacity,
1067 homes.len,
1068 );
1069 for (candidates) |candidate| {
1070 if (candidate.useCount() != 0) locationIndex(emitter).includeValue(candidate.value);
1071 }
1072 try locationIndex(emitter).sealValues(emitter.allocator);
1073 }
1074
1075 fn allocateIntervalHomes(
1076 emitter: anytype,
1077 candidates: *Candidates,
1078 fixed_positions: []FixedPosition,
1079 homes: []const Register,
1080 loop_intervals: []const shared.LoopInterval,
1081 ) !void {
1082 candidates.sort();
1083 const ordered = candidates.slice();
1084 try prepareLocationIndex(emitter, ordered, homes);
1085 var fixed_position_index_storage: FixedPositionIndex.Storage = undefined;
1086 const fixed_position_index = FixedPositionIndex.init(fixed_positions, &fixed_position_index_storage);
1087
1088 var active = ActiveSet{};
1089 defer active.deinit(emitter.allocator);
1090
1091 for (ordered, 0..) |candidate, candidate_index| {
1092 if (candidate.useCount() == 0) continue;
1093 try expireActive(emitter, &active, ordered, candidate.startPoint());
1094 const choice = bestFree(active, fixed_position_index, candidate, homes, loop_intervals) orelse choice: {
1095 const victim_index = evictionCandidate(active.slice(), ordered, fixed_position_index, candidate, loop_intervals) orelse continue;
1096 const victim = active.swapRemove(victim_index);
1097 const evicted = ordered[victim.candidate_index];
1098 try closeActiveRange(emitter, ordered, victim, candidate.start(), .definition, .spill);
1099 _ = locations(emitter).remove(evicted.value);
1100 break :choice AvailableRegister{ .reg = victim.reg, .until = candidate.endPoint() };
1101 };
1102 try active.append(emitter.allocator, .{
1103 .start = candidate.start(),
1104 .end = choice.until.position,
1105 .end_phase = choice.until.phase,
1106 .reg = choice.reg,
1107 .candidate_index = candidate_index,
1108 });
1109 if (choice.until.rank() == candidate.endPoint().rank()) {
1110 try locations(emitter).put(emitter.allocator, candidate.value, choice.reg);
1111 }
1112 markUsed(emitter, choice.reg);
1113 }
1114 try closeRemainingActiveRanges(emitter, &active, ordered);
1115 try appendReloadRanges(emitter, ordered, fixed_position_index, homes, loop_intervals);
1116 try verifyAllocation(emitter, ordered, fixed_position_index);
1117 }
1118 };
1119 }
1120
1121 const GprCore = Core(GPR, GprMask, isGprHomeable);
1122 const XmmCore = Core(XMM, XmmMask, isXmmHomeable);
1123
1124 const xmm_interval_homes = registers.allocatable_xmms;
1125
1126 const Books = struct {
1127 gpr_candidates: *GprCore.Candidates,
1128 gpr_fixed: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1129 xmm_candidates: *XmmCore.Candidates,
1130 xmm_fixed: *std.ArrayListUnmanaged(XmmCore.FixedPosition),
1131 };
1132
1133 fn xmmRequirementFromValueLocation(location: abi.ValueLocation) XmmCore.Requirement {
1134 return switch (location) {
1135 .fp_reg => |reg| .{ .fixed = reg },
1136 .int_reg, .stack => .any,
1137 };
1138 }
1139
1140 fn requirementFromValueLocation(location: abi.ValueLocation) GprCore.Requirement {
1141 return switch (location) {
1142 .int_reg => |reg| .{ .fixed = reg },
1143 .fp_reg, .stack => .any,
1144 };
1145 }
1146
1147 fn entryArgumentSources(
1148 block: *ir.Block,
1149 allocator: std.mem.Allocator,
1150 gpr_sources: []GprCore.Requirement,
1151 xmm_sources: []XmmCore.Requirement,
1152 ) !void {
1153 const function = entryFunction(block) orelse {
1154 @memset(gpr_sources, .any);
1155 @memset(xmm_sources, .any);
1156 return;
1157 };
1158
1159 const hidden: usize = @intFromBool(abi.returnsThroughRecord(function.results.items.len));
1160 const arg_count = block.arguments.items.len + hidden;
1161 const arg_type_names = try allocator.alloc([]const u8, arg_count);
1162 defer allocator.free(arg_type_names);
1163 const arg_locations = try allocator.alloc(abi.ValueLocation, arg_count);
1164 defer allocator.free(arg_locations);
1165
1166 if (hidden != 0) arg_type_names[0] = index_type_name;
1167 for (block.arguments.items, hidden..) |arg, i| {
1168 arg_type_names[i] = arg.type.getDialectTypeName() orelse return error.UnsupportedType;
1169 }
1170 abi.computeArgLocations(arg_type_names, arg_locations);
1171
1172 for (arg_locations[hidden..], 0..) |location, i| {
1173 gpr_sources[i] = requirementFromValueLocation(location);
1174 xmm_sources[i] = xmmRequirementFromValueLocation(location);
1175 }
1176 }
1177
1178 fn entryFunction(block: *ir.Block) ?*ir.Operation {
1179 const region = block.getParentRegion() orelse return null;
1180 if (region.getEntryBlock() != block) return null;
1181 const parent = region.getParentOperation() orelse return null;
1182 if (!std.mem.eql(u8, parent.name.name, FuncDialect.FuncOp.operation_name)) return null;
1183 return parent;
1184 }
1185
1186 fn appendBlockArgumentCandidates(
1187 books: Books,
1188 allocator: std.mem.Allocator,
1189 block: *ir.Block,
1190 start: u32,
1191 order: *u32,
1192 ) !void {
1193 const gpr_sources = try allocator.alloc(GprCore.Requirement, block.arguments.items.len);
1194 defer allocator.free(gpr_sources);
1195 const xmm_sources = try allocator.alloc(XmmCore.Requirement, block.arguments.items.len);
1196 defer allocator.free(xmm_sources);
1197 try entryArgumentSources(block, allocator, gpr_sources, xmm_sources);
1198
1199 for (block.arguments.items, 0..) |arg, i| {
1200 try GprCore.appendCandidate(books.gpr_candidates, allocator, arg, start, order, false, .any, gpr_sources[i]);
1201 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, start, .source, gpr_sources[i]);
1202 try XmmCore.appendCandidate(books.xmm_candidates, allocator, arg, start, order, false, .any, xmm_sources[i]);
1203 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, start, .source, xmm_sources[i]);
1204 }
1205 }
1206
1207 /// The register the Linux x86-64 kernel reads the call number from, and answers through.
1208 pub const syscall_number_gpr: GPR = .rax;
1209
1210 /// The registers the Linux x86-64 kernel reads its arguments from, in argument order.
1211 ///
1212 /// Argument three is r10 and not rcx. `syscall` writes the return address into rcx before the
1213 /// kernel runs, so a number placed there would be destroyed by the instruction that reads it.
1214 /// The C ABI's third argument register IS rcx (`registers.GPR.arg3`), which is why the
1215 /// `arg0..arg5` alias set cannot stand in for this table.
1216 pub const syscall_argument_gprs = [_]GPR{ .rdi, .rsi, .rdx, .r10, .r8, .r9 };
1217
1218 /// The registers `syscall` destroys without being told to: it stores rip in rcx and rflags in
1219 /// r11. rax is not listed because the op defines it, and a definition already excludes every
1220 /// other live range from it.
1221 pub const syscall_clobbered_gprs = [_]GPR{ .rcx, .r11 };
1222
1223 /// The register operand `index` must reach, or null when no such operand exists.
1224 fn syscallOperandGpr(index: usize) ?GPR {
1225 if (index == 0) return syscall_number_gpr;
1226 if (index - 1 >= syscall_argument_gprs.len) return null;
1227 return syscall_argument_gprs[index - 1];
1228 }
1229
1230 /// Pins every operand of one `func.syscall` to the register the kernel reads it from and
1231 /// records the two registers the instruction destroys.
1232 ///
1233 /// The operands are recorded as plain uses rather than ordered scratch uses because the
1234 /// emitter settles them with one parallel move, the way it settles a call's arguments, so no
1235 /// operand can be overwritten by an earlier one.
1236 fn recordSyscallUses(
1237 books: Books,
1238 allocator: std.mem.Allocator,
1239 op: *ir.Operation,
1240 position: u32,
1241 ) !void {
1242 const point = PositionPoint.source(position);
1243 for (op.operands.items, 0..) |operand, index| {
1244 const reg = syscallOperandGpr(index) orelse return error.UnsupportedOperation;
1245 const requirement = GprCore.Requirement{ .fixed = reg };
1246 try GprCore.recordUse(books.gpr_candidates, allocator, operand.value, point, requirement, 0);
1247 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position, .use, requirement);
1248 }
1249 try GprCore.appendScratchClobbers(books.gpr_fixed, allocator, position, &syscall_clobbered_gprs);
1250 }
1251
1252 fn recordCallClobbers(
1253 fixed_positions: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1254 allocator: std.mem.Allocator,
1255 position: u32,
1256 ) !void {
1257 try fixed_positions.append(allocator, .{ .point = shared.fixedPositionPoint(position, .clobber), .reg = abi.int_return_reg, .kind = .clobber });
1258 for (call_plan.call_clobbered_gprs) |reg| {
1259 try fixed_positions.append(allocator, .{ .point = shared.fixedPositionPoint(position, .clobber), .reg = reg, .kind = .clobber });
1260 }
1261 }
1262
1263 fn hasI32ImmediateRhs(op: *ir.Operation) !bool {
1264 const rhs = op.getOperand(1) orelse return error.MissingOperand;
1265 return scalar.constantIntI32(rhs) != null;
1266 }
1267
1268 fn recordScalarScratchClobbers(
1269 fixed_positions: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1270 allocator: std.mem.Allocator,
1271 op: *ir.Operation,
1272 position: u32,
1273 ) !void {
1274 const name = op.name.name;
1275 if (std.mem.eql(u8, name, ArithDialect.ConstantOp.operation_name)) {
1276 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1277 } else if (std.mem.eql(u8, name, ArithDialect.AddOp.operation_name) or
1278 std.mem.eql(u8, name, ArithDialect.MulOp.operation_name) or
1279 std.mem.eql(u8, name, ArithDialect.MaxOp.operation_name) or
1280 std.mem.eql(u8, name, ArithDialect.MinOp.operation_name) or
1281 std.mem.eql(u8, name, ArithDialect.AndOp.operation_name) or
1282 std.mem.eql(u8, name, ArithDialect.OrOp.operation_name) or
1283 std.mem.eql(u8, name, ArithDialect.XorOp.operation_name))
1284 {
1285 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1286 } else if (std.mem.eql(u8, name, ArithDialect.NegOp.operation_name) or
1287 std.mem.eql(u8, name, ArithDialect.NotOp.operation_name) or
1288 std.mem.eql(u8, name, ArithDialect.ShlOp.operation_name) or
1289 std.mem.eql(u8, name, ArithDialect.ShrOp.operation_name) or
1290 std.mem.eql(u8, name, ArithDialect.UshrOp.operation_name))
1291 {
1292 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1293 } else if (std.mem.eql(u8, name, ArithDialect.AbsOp.operation_name)) {
1294 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rcx });
1295 } else if (std.mem.eql(u8, name, ArithDialect.SubOp.operation_name) or
1296 std.mem.eql(u8, name, ArithDialect.CmpOp.operation_name))
1297 {
1298 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1299 } else if (std.mem.eql(u8, name, ArithDialect.DivOp.operation_name) or
1300 std.mem.eql(u8, name, ArithDialect.RemOp.operation_name))
1301 {
1302 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rdx });
1303 } else if (std.mem.eql(u8, name, ArithDialect.SelectOp.operation_name)) {
1304 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rdx});
1305 } else if (std.mem.eql(u8, name, ArithDialect.CastOp.operation_name)) {
1306 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rcx });
1307 } else if (std.mem.eql(u8, name, ArithDialect.BitcastOp.operation_name)) {
1308 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1309 } else if (std.mem.eql(u8, name, MemrefDialect.LoadOp.operation_name)) {
1310 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rcx });
1311 } else if (std.mem.eql(u8, name, MemrefDialect.StoreOp.operation_name)) {
1312 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rcx, .rdx });
1313 } else if (std.mem.eql(u8, name, MemrefDialect.AllocaOp.operation_name)) {
1314 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{.rax});
1315 } else if (isOverflowOp(op)) {
1316 try GprCore.appendScratchClobbers(fixed_positions, allocator, position, &.{ .rax, .rcx });
1317 }
1318 }
1319
1320 fn recordOrderedScalarSources(
1321 candidates: *GprCore.Candidates,
1322 fixed_positions: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1323 allocator: std.mem.Allocator,
1324 op: *ir.Operation,
1325 position: u32,
1326 sources: []const GPR,
1327 ) !void {
1328 var source_blockers: GprMask = 0;
1329 const point = PositionPoint.source(position);
1330 for (sources, 0..) |source, index| {
1331 const operand = op.getOperand(index) orelse return error.MissingOperand;
1332 try GprCore.recordFixedSourceUse(candidates, fixed_positions, allocator, operand, point, source, .scratch_use, source_blockers);
1333 source_blockers |= GprCore.regBit(source);
1334 }
1335 }
1336
1337 fn recordScalarSourceOrder(
1338 candidates: *GprCore.Candidates,
1339 fixed_positions: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1340 allocator: std.mem.Allocator,
1341 op: *ir.Operation,
1342 position: u32,
1343 ) !bool {
1344 const name = op.name.name;
1345 if (std.mem.eql(u8, name, ArithDialect.AddOp.operation_name) or
1346 std.mem.eql(u8, name, ArithDialect.MulOp.operation_name) or
1347 std.mem.eql(u8, name, ArithDialect.MaxOp.operation_name) or
1348 std.mem.eql(u8, name, ArithDialect.MinOp.operation_name) or
1349 std.mem.eql(u8, name, ArithDialect.AndOp.operation_name) or
1350 std.mem.eql(u8, name, ArithDialect.OrOp.operation_name) or
1351 std.mem.eql(u8, name, ArithDialect.XorOp.operation_name))
1352 {
1353 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx });
1354 return true;
1355 }
1356 if (std.mem.eql(u8, name, ArithDialect.NegOp.operation_name) or
1357 std.mem.eql(u8, name, ArithDialect.AbsOp.operation_name) or
1358 std.mem.eql(u8, name, ArithDialect.NotOp.operation_name))
1359 {
1360 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{.rax});
1361 return true;
1362 }
1363 if (std.mem.eql(u8, name, ArithDialect.ShlOp.operation_name) or
1364 std.mem.eql(u8, name, ArithDialect.ShrOp.operation_name) or
1365 std.mem.eql(u8, name, ArithDialect.UshrOp.operation_name))
1366 {
1367 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx });
1368 return true;
1369 }
1370 if (std.mem.eql(u8, name, ArithDialect.SubOp.operation_name) or
1371 std.mem.eql(u8, name, ArithDialect.CmpOp.operation_name))
1372 {
1373 if (try hasI32ImmediateRhs(op)) {
1374 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{.rax});
1375 } else {
1376 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx });
1377 }
1378 return true;
1379 }
1380 if (std.mem.eql(u8, name, ArithDialect.DivOp.operation_name) or
1381 std.mem.eql(u8, name, ArithDialect.RemOp.operation_name))
1382 {
1383 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx });
1384 return true;
1385 }
1386 if (std.mem.eql(u8, name, ArithDialect.SelectOp.operation_name)) {
1387 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx, .rdx });
1388 return true;
1389 }
1390 if (isOverflowOp(op)) {
1391 try recordOrderedScalarSources(candidates, fixed_positions, allocator, op, position, &.{ .rax, .rcx });
1392 return true;
1393 }
1394 return false;
1395 }
1396
1397 fn recordXmmOrderedSources(
1398 candidates: *XmmCore.Candidates,
1399 fixed_positions: *std.ArrayListUnmanaged(XmmCore.FixedPosition),
1400 allocator: std.mem.Allocator,
1401 op: *ir.Operation,
1402 position: u32,
1403 sources: []const XMM,
1404 ) !void {
1405 var source_blockers: XmmMask = 0;
1406 const point = PositionPoint.source(position);
1407 for (sources, 0..) |source, index| {
1408 const operand = op.getOperand(index) orelse return error.MissingOperand;
1409 try XmmCore.recordFixedSourceUse(candidates, fixed_positions, allocator, operand, point, source, .scratch_use, source_blockers);
1410 source_blockers |= XmmCore.regBit(source);
1411 }
1412 }
1413
1414 fn isFloatArithOp(op: *ir.Operation) bool {
1415 if (op.operands.items.len == 0) return false;
1416 if (!isFloatEligibleOp(op.name.name)) return false;
1417 return allOperandsFloatScalar(op);
1418 }
1419
1420 fn recordFloatOperation(
1421 books: Books,
1422 allocator: std.mem.Allocator,
1423 op: *ir.Operation,
1424 position: u32,
1425 ) !void {
1426 const name = op.name.name;
1427 if (std.mem.eql(u8, name, ArithDialect.NegOp.operation_name)) {
1428 try recordXmmOrderedSources(books.xmm_candidates, books.xmm_fixed, allocator, op, position, &.{.xmm0});
1429 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{ .xmm0, .xmm1 });
1430 return;
1431 }
1432 if (std.mem.eql(u8, name, ArithDialect.MaxOp.operation_name) or
1433 std.mem.eql(u8, name, ArithDialect.MinOp.operation_name))
1434 {
1435 try recordXmmOrderedSources(books.xmm_candidates, books.xmm_fixed, allocator, op, position, &.{ .xmm0, .xmm1 });
1436 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{ .xmm0, .xmm1, .xmm2 });
1437 return;
1438 }
1439 try recordXmmOrderedSources(books.xmm_candidates, books.xmm_fixed, allocator, op, position, &.{ .xmm0, .xmm1 });
1440 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{ .xmm0, .xmm1 });
1441 }
1442
1443 fn recordPackedOperation(
1444 books: Books,
1445 allocator: std.mem.Allocator,
1446 op: *ir.Operation,
1447 position: u32,
1448 ) !void {
1449 const name = op.name.name;
1450 if (std.mem.eql(u8, name, ArithDialect.SplatOp.operation_name)) {
1451 const operand = op.getOperand(0) orelse return error.MissingOperand;
1452 if (isFloatScalar(operand)) {
1453 try recordXmmOrderedSources(books.xmm_candidates, books.xmm_fixed, allocator, op, position, &.{.xmm0});
1454 } else {
1455 try recordOrderedScalarSources(books.gpr_candidates, books.gpr_fixed, allocator, op, position, &.{.rax});
1456 try GprCore.appendScratchClobbers(books.gpr_fixed, allocator, position, &.{.rax});
1457 }
1458 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{.xmm0});
1459 return;
1460 }
1461 if (std.mem.eql(u8, name, ArithDialect.VecConstantOp.operation_name)) {
1462 try GprCore.appendScratchClobbers(books.gpr_fixed, allocator, position, &.{.rax});
1463 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{.xmm0});
1464 return;
1465 }
1466
1467 try recordXmmOrderedSources(books.xmm_candidates, books.xmm_fixed, allocator, op, position, &.{ .xmm0, .xmm1 });
1468 if (std.mem.eql(u8, name, ArithDialect.MulOp.operation_name)) {
1469 const result = op.getResult(0) orelse return error.MissingResult;
1470 if (!isPackedFloat128(result)) {
1471 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{ .xmm0, .xmm1, .xmm2, .xmm3, .xmm4 });
1472 return;
1473 }
1474 }
1475 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{ .xmm0, .xmm1 });
1476 }
1477
1478 fn memrefElementValue(op: *ir.Operation) ?*ir.Value {
1479 const name = op.name.name;
1480 if (std.mem.eql(u8, name, MemrefDialect.LoadOp.operation_name)) return op.getResult(0);
1481 if (std.mem.eql(u8, name, MemrefDialect.StoreOp.operation_name)) return op.getOperand(0);
1482 return null;
1483 }
1484
1485 fn recordMemrefXmmClobbers(
1486 books: Books,
1487 allocator: std.mem.Allocator,
1488 op: *ir.Operation,
1489 position: u32,
1490 ) !void {
1491 const element = memrefElementValue(op) orelse return;
1492 if (!isFloatScalar(element) and !isPacked128(element)) return;
1493 try XmmCore.appendScratchClobbers(books.xmm_fixed, allocator, position, &.{.xmm0});
1494 }
1495
1496 fn recordXmmCallClobbers(
1497 fixed_positions: *std.ArrayListUnmanaged(XmmCore.FixedPosition),
1498 allocator: std.mem.Allocator,
1499 position: u32,
1500 ) !void {
1501 for (registers.allocatable_xmms) |reg| {
1502 try fixed_positions.append(allocator, .{ .point = shared.fixedPositionPoint(position, .clobber), .reg = reg, .kind = .clobber });
1503 }
1504 }
1505
1506 fn recordOperationUses(
1507 books: Books,
1508 allocator: std.mem.Allocator,
1509 op: *ir.Operation,
1510 position: u32,
1511 ) !void {
1512 if (std.mem.eql(u8, op.name.name, FuncDialect.CallOp.operation_name)) {
1513 const hidden: usize = @intFromBool(abi.returnsThroughRecord(op.results.items.len));
1514 const arg_count = op.operands.items.len + hidden;
1515 const arg_type_names = try allocator.alloc([]const u8, arg_count);
1516 defer allocator.free(arg_type_names);
1517 const arg_locations = try allocator.alloc(abi.ValueLocation, arg_count);
1518 defer allocator.free(arg_locations);
1519
1520 if (hidden != 0) arg_type_names[0] = index_type_name;
1521 for (op.operands.items, hidden..) |operand, i| {
1522 arg_type_names[i] = operand.value.type.getDialectTypeName() orelse return error.UnsupportedType;
1523 }
1524 abi.computeArgLocations(arg_type_names, arg_locations);
1525
1526 for (op.operands.items, hidden..) |operand, i| {
1527 const requirement = requirementFromValueLocation(arg_locations[i]);
1528 try GprCore.recordUse(books.gpr_candidates, allocator, operand.value, PositionPoint.source(position), requirement, 0);
1529 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position, .use, requirement);
1530 const xmm_requirement = xmmRequirementFromValueLocation(arg_locations[i]);
1531 try XmmCore.recordUse(books.xmm_candidates, allocator, operand.value, PositionPoint.source(position), xmm_requirement, 0);
1532 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position, .use, xmm_requirement);
1533 }
1534 try recordCallClobbers(books.gpr_fixed, allocator, position);
1535 try recordXmmCallClobbers(books.xmm_fixed, allocator, position);
1536 return;
1537 }
1538
1539 if (std.mem.eql(u8, op.name.name, FuncDialect.SyscallOp.operation_name)) {
1540 return recordSyscallUses(books, allocator, op, position);
1541 }
1542
1543 if (std.mem.eql(u8, op.name.name, FuncDialect.ReturnOp.operation_name) and
1544 op.operands.items.len == 1 and isFloatScalar(op.operands.items[0].value))
1545 {
1546 try XmmCore.recordFixedSourceUse(books.xmm_candidates, books.xmm_fixed, allocator, op.operands.items[0].value, PositionPoint.source(position), .xmm0, .use, 0);
1547 return;
1548 }
1549
1550 if (isFloatArithOp(op)) {
1551 return recordFloatOperation(books, allocator, op, position);
1552 }
1553
1554 if (isPackedEligibleOp(op)) {
1555 return recordPackedOperation(books, allocator, op, position);
1556 }
1557
1558 if (try recordScalarSourceOrder(books.gpr_candidates, books.gpr_fixed, allocator, op, position)) {
1559 try recordScalarScratchClobbers(books.gpr_fixed, allocator, op, position);
1560 return;
1561 }
1562
1563 for (op.operands.items) |operand| {
1564 try GprCore.recordUse(books.gpr_candidates, allocator, operand.value, PositionPoint.source(position), .any, 0);
1565 try XmmCore.recordUse(books.xmm_candidates, allocator, operand.value, PositionPoint.source(position), .any, 0);
1566 }
1567 try recordScalarScratchClobbers(books.gpr_fixed, allocator, op, position);
1568 try recordMemrefXmmClobbers(books, allocator, op, position);
1569 }
1570
1571 fn recordOperationPosition(
1572 operation_positions: ?*std.AutoHashMapUnmanaged(*ir.Operation, u32),
1573 allocator: std.mem.Allocator,
1574 op: *ir.Operation,
1575 position: u32,
1576 ) !void {
1577 if (operation_positions) |positions| {
1578 try positions.put(allocator, op, position);
1579 }
1580 }
1581
1582 fn definitionRequirement(op: *ir.Operation, result_index: usize) GprCore.Requirement {
1583 if (result_index != 0) {
1584 if (result_index == 1 and isOverflowOp(op)) return .{ .fixed = .rcx };
1585 return .any;
1586 }
1587 if (op.getResult(result_index)) |result| {
1588 if (!isRegisterScalar(result) and !isMemref(result)) return .any;
1589 }
1590 const name = op.name.name;
1591 if (std.mem.eql(u8, name, FuncDialect.CallOp.operation_name)) {
1592 const result = op.getResult(result_index) orelse return .any;
1593 const type_name = result.type.getDialectTypeName() orelse return .any;
1594 return switch (abi.computeReturnLocation(type_name)) {
1595 .int_reg => |reg| .{ .fixed = reg },
1596 .fp_reg, .stack => .any,
1597 };
1598 }
1599 if (std.mem.eql(u8, name, FuncDialect.SyscallOp.operation_name)) {
1600 return .{ .fixed = syscall_number_gpr };
1601 }
1602 if (std.mem.eql(u8, name, ArithDialect.ConstantOp.operation_name) or
1603 std.mem.eql(u8, name, ArithDialect.AddOp.operation_name) or
1604 std.mem.eql(u8, name, ArithDialect.SubOp.operation_name) or
1605 std.mem.eql(u8, name, ArithDialect.MulOp.operation_name) or
1606 std.mem.eql(u8, name, ArithDialect.NegOp.operation_name) or
1607 std.mem.eql(u8, name, ArithDialect.AbsOp.operation_name) or
1608 std.mem.eql(u8, name, ArithDialect.DivOp.operation_name) or
1609 std.mem.eql(u8, name, ArithDialect.MaxOp.operation_name) or
1610 std.mem.eql(u8, name, ArithDialect.MinOp.operation_name) or
1611 std.mem.eql(u8, name, ArithDialect.AndOp.operation_name) or
1612 std.mem.eql(u8, name, ArithDialect.OrOp.operation_name) or
1613 std.mem.eql(u8, name, ArithDialect.XorOp.operation_name) or
1614 std.mem.eql(u8, name, ArithDialect.NotOp.operation_name) or
1615 std.mem.eql(u8, name, ArithDialect.ShlOp.operation_name) or
1616 std.mem.eql(u8, name, ArithDialect.ShrOp.operation_name) or
1617 std.mem.eql(u8, name, ArithDialect.UshrOp.operation_name) or
1618 std.mem.eql(u8, name, ArithDialect.CmpOp.operation_name))
1619 {
1620 return .{ .fixed = .rax };
1621 }
1622 if (std.mem.eql(u8, name, ArithDialect.SelectOp.operation_name)) {
1623 return .{ .fixed = .rdx };
1624 }
1625 if (std.mem.eql(u8, name, ArithDialect.RemOp.operation_name)) {
1626 return .{ .fixed = .rdx };
1627 }
1628 if (std.mem.eql(u8, name, ArithDialect.CastOp.operation_name)) {
1629 return .{ .fixed = .rax };
1630 }
1631 if (std.mem.eql(u8, name, ArithDialect.BitcastOp.operation_name)) {
1632 return .{ .fixed = .rax };
1633 }
1634 if (isOverflowOp(op)) return .{ .fixed = .rax };
1635 return .any;
1636 }
1637
1638 fn xmmDefinitionRequirement(op: *ir.Operation, result_index: usize) XmmCore.Requirement {
1639 if (result_index != 0) return .any;
1640 const result = op.getResult(result_index) orelse return .any;
1641 if (isFloatScalar(result)) {
1642 if (isFloatEligibleOp(op.name.name)) return .{ .fixed = .xmm0 };
1643 return .any;
1644 }
1645 if (isPacked128(result)) {
1646 if (std.mem.eql(u8, op.name.name, MemrefDialect.LoadOp.operation_name)) return .any;
1647 if (isPackedEligibleOp(op)) return .{ .fixed = .xmm0 };
1648 }
1649 return .any;
1650 }
1651
1652 fn collectBlockCandidates(
1653 books: Books,
1654 operation_positions: ?*std.AutoHashMapUnmanaged(*ir.Operation, u32),
1655 allocator: std.mem.Allocator,
1656 block: *ir.Block,
1657 position: *u32,
1658 order: *u32,
1659 ) !void {
1660 try appendBlockArgumentCandidates(books, allocator, block, 0, order);
1661
1662 var op_iter = block.operations.head;
1663 while (op_iter) |op_ptr| {
1664 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
1665
1666 if (std.mem.eql(u8, op.name.name, ScfDialect.IfOp.operation_name)) {
1667 try recordOperationPosition(operation_positions, allocator, op, position.*);
1668 try recordOperationUses(books, allocator, op, position.*);
1669 position.* += 1;
1670
1671 const if_op = ScfDialect.IfOp{ .op = op };
1672 try collectBlockCandidates(books, operation_positions, allocator, if_op.getThenBlock(), position, order);
1673 if (if_op.getElseBlock()) |else_block| {
1674 try collectBlockCandidates(books, operation_positions, allocator, else_block, position, order);
1675 }
1676
1677 for (op.results.items, 0..) |*result, result_index| {
1678 const requirement = definitionRequirement(op, result_index);
1679 try GprCore.appendCandidate(books.gpr_candidates, allocator, result, position.*, order, false, requirement, requirement);
1680 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position.*, .def, requirement);
1681 const xmm_requirement = xmmDefinitionRequirement(op, result_index);
1682 try XmmCore.appendCandidate(books.xmm_candidates, allocator, result, position.*, order, false, xmm_requirement, xmm_requirement);
1683 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position.*, .def, xmm_requirement);
1684 }
1685 position.* += 1;
1686 } else {
1687 const is_constant = std.mem.eql(u8, op.name.name, ArithDialect.ConstantOp.operation_name);
1688 try recordOperationPosition(operation_positions, allocator, op, position.*);
1689 try recordOperationUses(books, allocator, op, position.*);
1690 for (op.results.items, 0..) |*result, result_index| {
1691 const requirement = definitionRequirement(op, result_index);
1692 try GprCore.appendCandidate(books.gpr_candidates, allocator, result, position.*, order, is_constant, requirement, requirement);
1693 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position.*, .def, requirement);
1694 const xmm_requirement = xmmDefinitionRequirement(op, result_index);
1695 try XmmCore.appendCandidate(books.xmm_candidates, allocator, result, position.*, order, is_constant, xmm_requirement, xmm_requirement);
1696 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position.*, .def, xmm_requirement);
1697 }
1698 position.* += 1;
1699 }
1700
1701 op_iter = op.next_op;
1702 }
1703 }
1704
1705 fn earlierPoint(current: ?PositionPoint, candidate: PositionPoint) PositionPoint {
1706 return if (current) |point| point: {
1707 break :point if (candidate.lessThan(point)) candidate else point;
1708 } else candidate;
1709 }
1710
1711 pub fn allocate(emitter: anytype, region: *ir.Region) !void {
1712 if (!isEligibleFunction(region)) return;
1713 const block = region.blocks.head orelse return;
1714
1715 var gpr_candidates: GprCore.Candidates = .empty;
1716 defer gpr_candidates.deinit(emitter.allocator);
1717
1718 var gpr_fixed: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
1719 defer gpr_fixed.deinit(emitter.allocator);
1720
1721 var xmm_candidates: XmmCore.Candidates = .empty;
1722 defer xmm_candidates.deinit(emitter.allocator);
1723
1724 var xmm_fixed: std.ArrayListUnmanaged(XmmCore.FixedPosition) = .empty;
1725 defer xmm_fixed.deinit(emitter.allocator);
1726
1727 var loop_intervals: std.ArrayListUnmanaged(shared.LoopInterval) = .empty;
1728 defer loop_intervals.deinit(emitter.allocator);
1729
1730 const books = Books{
1731 .gpr_candidates = &gpr_candidates,
1732 .gpr_fixed = &gpr_fixed,
1733 .xmm_candidates = &xmm_candidates,
1734 .xmm_fixed = &xmm_fixed,
1735 };
1736
1737 var order: u32 = 0;
1738 const has_non_if_regions = blockHasNonIfRegions(block);
1739 if (has_non_if_regions) {
1740 var position: u32 = 1;
1741 try collectRegionBlockCandidates(books, &loop_intervals, &emitter.operation_positions, emitter.allocator, block, 0, &position, &order);
1742 } else {
1743 var position: u32 = 1;
1744 try collectBlockCandidates(books, &emitter.operation_positions, emitter.allocator, block, &position, &order);
1745 }
1746 shared.extendAcrossLoops(GPR, GprMask, gpr_candidates.slice(), loop_intervals.items);
1747 shared.extendAcrossLoops(XMM, XmmMask, xmm_candidates.slice(), loop_intervals.items);
1748 try GprCore.allocateIntervalHomes(emitter, &gpr_candidates, gpr_fixed.items, &interval_homes, loop_intervals.items);
1749 try XmmCore.allocateIntervalHomes(emitter, &xmm_candidates, xmm_fixed.items, &xmm_interval_homes, loop_intervals.items);
1750 }
1751
1752 fn blockHasNonIfRegions(block: *ir.Block) bool {
1753 var op_iter = block.operations.head;
1754 while (op_iter) |op_ptr| {
1755 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
1756 if (op.regions.items.len != 0) {
1757 if (!std.mem.eql(u8, op.name.name, ScfDialect.IfOp.operation_name)) return true;
1758 const if_op = ScfDialect.IfOp{ .op = op };
1759 if (blockHasNonIfRegions(if_op.getThenBlock())) return true;
1760 if (if_op.getElseBlock()) |else_block| {
1761 if (blockHasNonIfRegions(else_block)) return true;
1762 }
1763 }
1764 op_iter = op.next_op;
1765 }
1766 return false;
1767 }
1768
1769 fn collectRegionBlockCandidates(
1770 books: Books,
1771 loop_intervals: *std.ArrayListUnmanaged(shared.LoopInterval),
1772 operation_positions: ?*std.AutoHashMapUnmanaged(*ir.Operation, u32),
1773 allocator: std.mem.Allocator,
1774 block: *ir.Block,
1775 block_start: u32,
1776 position: *u32,
1777 order: *u32,
1778 ) !void {
1779 try appendBlockArgumentCandidates(books, allocator, block, block_start, order);
1780 var op_iter = block.operations.head;
1781 while (op_iter) |op_ptr| {
1782 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
1783 const is_constant = std.mem.eql(u8, op.name.name, "arith.constant");
1784 try recordOperationPosition(operation_positions, allocator, op, position.*);
1785 try recordOperationUses(books, allocator, op, position.*);
1786 if (op.regions.items.len == 0) {
1787 for (op.results.items, 0..) |*result, result_index| {
1788 const requirement = definitionRequirement(op, result_index);
1789 try GprCore.appendCandidate(books.gpr_candidates, allocator, result, position.*, order, is_constant, requirement, requirement);
1790 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position.*, .def, requirement);
1791 const xmm_requirement = xmmDefinitionRequirement(op, result_index);
1792 try XmmCore.appendCandidate(books.xmm_candidates, allocator, result, position.*, order, is_constant, xmm_requirement, xmm_requirement);
1793 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position.*, .def, xmm_requirement);
1794 }
1795 position.* += 1;
1796 } else if (std.mem.eql(u8, op.name.name, ScfDialect.IfOp.operation_name)) {
1797 position.* += 1;
1798 for (op.regions.items) |*region| {
1799 const nested = region.blocks.head orelse continue;
1800 try collectRegionBlockCandidates(books, loop_intervals, operation_positions, allocator, nested, position.*, position, order);
1801 }
1802 for (op.results.items, 0..) |*result, result_index| {
1803 const requirement = definitionRequirement(op, result_index);
1804 try GprCore.appendCandidate(books.gpr_candidates, allocator, result, position.*, order, is_constant, requirement, requirement);
1805 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position.*, .def, requirement);
1806 const xmm_requirement = xmmDefinitionRequirement(op, result_index);
1807 try XmmCore.appendCandidate(books.xmm_candidates, allocator, result, position.*, order, is_constant, xmm_requirement, xmm_requirement);
1808 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position.*, .def, xmm_requirement);
1809 }
1810 position.* += 1;
1811 } else {
1812 position.* += 1;
1813 const loop_entry = position.*;
1814 for (op.regions.items) |*region| {
1815 const nested = region.blocks.head orelse continue;
1816 try collectRegionBlockCandidates(books, loop_intervals, operation_positions, allocator, nested, position.*, position, order);
1817 }
1818 try loop_intervals.append(allocator, .{ .entry = loop_entry, .trailing = position.* });
1819 if (std.mem.eql(u8, op.name.name, ScfDialect.ForOp.operation_name)) {
1820 const trailing_point = PositionPoint.source(position.*);
1821 const body = (ScfDialect.ForOp{ .op = op }).getBodyBlock();
1822 for (body.arguments.items) |arg| {
1823 try GprCore.recordUse(books.gpr_candidates, allocator, arg, trailing_point, .any, 0);
1824 try XmmCore.recordUse(books.xmm_candidates, allocator, arg, trailing_point, .any, 0);
1825 }
1826 if (op.getOperand(1)) |upper| {
1827 try GprCore.recordUse(books.gpr_candidates, allocator, upper, trailing_point, .any, 0);
1828 }
1829 if (op.getOperand(2)) |step| {
1830 try GprCore.recordUse(books.gpr_candidates, allocator, step, trailing_point, .any, 0);
1831 }
1832 }
1833 for (op.results.items, 0..) |*result, result_index| {
1834 const requirement = definitionRequirement(op, result_index);
1835 try GprCore.appendCandidate(books.gpr_candidates, allocator, result, position.*, order, is_constant, requirement, requirement);
1836 try GprCore.appendFixedPosition(books.gpr_fixed, allocator, position.*, .def, requirement);
1837 const xmm_requirement = xmmDefinitionRequirement(op, result_index);
1838 try XmmCore.appendCandidate(books.xmm_candidates, allocator, result, position.*, order, is_constant, xmm_requirement, xmm_requirement);
1839 try XmmCore.appendFixedPosition(books.xmm_fixed, allocator, position.*, .def, xmm_requirement);
1840 }
1841 position.* += 1;
1842 }
1843 op_iter = op.next_op;
1844 }
1845 }
1846
1847 const TestBooks = struct {
1848 xmm_candidates: XmmCore.Candidates = .empty,
1849 xmm_fixed: std.ArrayListUnmanaged(XmmCore.FixedPosition) = .empty,
1850
1851 fn books(
1852 self: *TestBooks,
1853 candidates: *GprCore.Candidates,
1854 fixed: *std.ArrayListUnmanaged(GprCore.FixedPosition),
1855 ) Books {
1856 return .{
1857 .gpr_candidates = candidates,
1858 .gpr_fixed = fixed,
1859 .xmm_candidates = &self.xmm_candidates,
1860 .xmm_fixed = &self.xmm_fixed,
1861 };
1862 }
1863
1864 fn deinit(self: *TestBooks, allocator: std.mem.Allocator) void {
1865 self.xmm_candidates.deinit(allocator);
1866 self.xmm_fixed.deinit(allocator);
1867 }
1868 };
1869
1870 const TestEmitter = struct {
1871 allocator: std.mem.Allocator,
1872 value_locations: std.AutoHashMapUnmanaged(*ir.Value, GPR) = .empty,
1873 value_location_ranges: std.ArrayListUnmanaged(ValueLocationRange) = .empty,
1874 value_location_index: ValueLocationIndex = .{},
1875 xmm_locations: std.AutoHashMapUnmanaged(*ir.Value, XMM) = .empty,
1876 xmm_location_ranges: std.ArrayListUnmanaged(shared.ValueLocationRange(XMM)) = .empty,
1877 xmm_location_index: XmmValueLocationIndex = .{},
1878 operation_positions: std.AutoHashMapUnmanaged(*ir.Operation, u32) = .empty,
1879 reserved_callee_saved: usize = 0,
1880 used_callee_saved_regs: [registers.callee_saved_gprs.len]GPR = undefined,
1881
1882 fn deinit(self: *TestEmitter) void {
1883 self.value_locations.deinit(self.allocator);
1884 self.value_location_ranges.deinit(self.allocator);
1885 self.value_location_index.deinit(self.allocator);
1886 self.xmm_locations.deinit(self.allocator);
1887 self.xmm_location_ranges.deinit(self.allocator);
1888 self.xmm_location_index.deinit(self.allocator);
1889 self.operation_positions.deinit(self.allocator);
1890 }
1891 };
1892
1893 fn prepareTestValueLocationIndex(
1894 emitter: *TestEmitter,
1895 values: []const *ir.Value,
1896 position_count: usize,
1897 range_capacity: usize,
1898 register_capacity: usize,
1899 ) !void {
1900 try emitter.value_location_index.prepare(
1901 emitter.allocator,
1902 values.len,
1903 position_count,
1904 range_capacity,
1905 register_capacity,
1906 );
1907 for (values) |value| emitter.value_location_index.includeValue(value);
1908 try emitter.value_location_index.sealValues(emitter.allocator);
1909 }
1910
1911 fn locationFor(emitter: *TestEmitter, value: *ir.Value) !GPR {
1912 return emitter.value_locations.get(value) orelse error.TestFailure;
1913 }
1914
1915 fn hasCallerSavedHome(emitter: *TestEmitter) bool {
1916 var it = emitter.value_locations.iterator();
1917 while (it.next()) |entry| {
1918 if (entry.value_ptr.*.isCallerSaved()) return true;
1919 }
1920 return false;
1921 }
1922
1923 fn hasValueLocationRangeWithActions(
1924 emitter: *TestEmitter,
1925 value: *ir.Value,
1926 start: u32,
1927 end: u32,
1928 reg: GPR,
1929 entry: ValueLocationRangeEntry,
1930 end_phase: PositionPhase,
1931 exit: ValueLocationRangeExit,
1932 ) bool {
1933 for (emitter.value_location_ranges.items) |range| {
1934 if (range.value == value and
1935 range.start == start and
1936 range.end == end and
1937 range.reg == reg and
1938 range.entry == entry and
1939 range.end_phase == end_phase and
1940 range.exit == exit) return true;
1941 }
1942 return false;
1943 }
1944
1945 fn hasValueLocationRange(emitter: *TestEmitter, value: *ir.Value, start: u32, end: u32, reg: GPR) bool {
1946 return hasValueLocationRangeWithActions(emitter, value, start, end, reg, .resident, .source, .retain);
1947 }
1948
1949 fn expectFixedGpr(requirement: GprCore.Requirement, expected: GPR) !void {
1950 switch (requirement) {
1951 .fixed => |actual| try std.testing.expectEqual(expected, actual),
1952 .any => return error.TestFailure,
1953 }
1954 }
1955
1956 fn expectAnyRequirement(requirement: GprCore.Requirement) !void {
1957 switch (requirement) {
1958 .any => {},
1959 .fixed => return error.TestFailure,
1960 }
1961 }
1962
1963 fn hasFixedPosition(positions: []const GprCore.FixedPosition, position: u32, kind: FixedPositionKind, reg: GPR) bool {
1964 for (positions) |fixed| {
1965 if (fixed.point.position == position and fixed.kind == kind and fixed.reg == reg) return true;
1966 }
1967 return false;
1968 }
1969
1970 fn expectUseBlockers(candidate: GprCore.Candidate, use_index: usize, blocked: []const GPR, clear: []const GPR) !void {
1971 const use = candidate.use_positions.items[use_index];
1972 for (blocked) |reg| {
1973 try std.testing.expect(GprCore.maskHasReg(use.source_blockers, reg));
1974 }
1975 for (clear) |reg| {
1976 try std.testing.expect(!GprCore.maskHasReg(use.source_blockers, reg));
1977 }
1978 }
1979
1980 test "allocation verifier rejects overlapping register ranges" {
1981 const builtin = @import("../../dialects/root.zig");
1982 const Arith = builtin.ArithDialect;
1983 const Func = builtin.FuncDialect;
1984
1985 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
1986 defer ctx.deinit(std.testing.allocator);
1987 try builtin.registerAllDialects(&ctx);
1988
1989 const i64_type = try Arith.getScalarType(&ctx, .i64);
1990 const loc = ir.Location.getUnknown();
1991 const func = try Func.FuncOp.create(&ctx, loc, "verify_overlap", &.{ i64_type, i64_type }, &.{i64_type});
1992
1993 var candidates: GprCore.Candidates = .empty;
1994 defer candidates.deinit(std.testing.allocator);
1995
1996 var order: u32 = 0;
1997 try GprCore.appendCandidate(&candidates, std.testing.allocator, func.getArgument(0), 0, &order, false, .any, .any);
1998 try GprCore.appendCandidate(&candidates, std.testing.allocator, func.getArgument(1), 0, &order, false, .any, .any);
1999
2000 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2001 defer emitter.deinit();
2002
2003 try prepareTestValueLocationIndex(&emitter, &.{ func.getArgument(0), func.getArgument(1) }, 3, 2, 1);
2004 try GprCore.appendValueLocationRange(&emitter, func.getArgument(0), 0, 2, .rbx, .resident, .source, .retain);
2005 try GprCore.appendValueLocationRange(&emitter, func.getArgument(1), 0, 2, .rbx, .resident, .source, .retain);
2006
2007 try std.testing.expectError(error.InvalidAllocation, GprCore.verifyAllocation(&emitter, candidates.slice(), GprCore.FixedPositionIndex.empty()));
2008 }
2009
2010 test "allocation verifier rejects fixed clobber overlap" {
2011 const builtin = @import("../../dialects/root.zig");
2012 const Arith = builtin.ArithDialect;
2013 const Func = builtin.FuncDialect;
2014
2015 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2016 defer ctx.deinit(std.testing.allocator);
2017 try builtin.registerAllDialects(&ctx);
2018
2019 const i64_type = try Arith.getScalarType(&ctx, .i64);
2020 const loc = ir.Location.getUnknown();
2021 const func = try Func.FuncOp.create(&ctx, loc, "verify_clobber", &.{i64_type}, &.{i64_type});
2022
2023 var candidates: GprCore.Candidates = .empty;
2024 defer candidates.deinit(std.testing.allocator);
2025 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2026 defer fixed_positions.deinit(std.testing.allocator);
2027
2028 var order: u32 = 0;
2029 try GprCore.appendCandidate(&candidates, std.testing.allocator, func.getArgument(0), 0, &order, false, .any, .any);
2030 try GprCore.appendFixedPosition(&fixed_positions, std.testing.allocator, 2, .clobber, .{ .fixed = .rax });
2031
2032 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2033 defer emitter.deinit();
2034
2035 try prepareTestValueLocationIndex(&emitter, &.{func.getArgument(0)}, 5, 1, 1);
2036 try GprCore.appendValueLocationRange(&emitter, func.getArgument(0), 0, 4, .rax, .resident, .definition, .retain);
2037
2038 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2039 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
2040 try std.testing.expectError(error.InvalidAllocation, GprCore.verifyAllocation(&emitter, candidates.slice(), fixed_position_index));
2041 }
2042
2043 test "allocation verifier accepts source definition handoff" {
2044 const builtin = @import("../../dialects/root.zig");
2045 const Arith = builtin.ArithDialect;
2046 const Func = builtin.FuncDialect;
2047
2048 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2049 defer ctx.deinit(std.testing.allocator);
2050 try builtin.registerAllDialects(&ctx);
2051
2052 const i64_type = try Arith.getScalarType(&ctx, .i64);
2053 const loc = ir.Location.getUnknown();
2054 const func = try Func.FuncOp.create(&ctx, loc, "verify_handoff", &.{i64_type}, &.{i64_type});
2055 const constant = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2056
2057 var candidates: GprCore.Candidates = .empty;
2058 defer candidates.deinit(std.testing.allocator);
2059 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2060 defer fixed_positions.deinit(std.testing.allocator);
2061
2062 var order: u32 = 0;
2063 try GprCore.appendCandidate(&candidates, std.testing.allocator, func.getArgument(0), 0, &order, false, .any, .any);
2064 try GprCore.appendCandidate(&candidates, std.testing.allocator, constant.getResult(), 1, &order, false, .{ .fixed = .rax }, .{ .fixed = .rax });
2065 try GprCore.recordUse(&candidates, std.testing.allocator, func.getArgument(0), PositionPoint.source(1), .any, 0);
2066 try GprCore.recordUse(&candidates, std.testing.allocator, constant.getResult(), PositionPoint.source(2), .any, 0);
2067 try GprCore.appendFixedPosition(&fixed_positions, std.testing.allocator, 1, .def, .{ .fixed = .rax });
2068
2069 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2070 defer emitter.deinit();
2071
2072 try prepareTestValueLocationIndex(&emitter, &.{ func.getArgument(0), constant.getResult() }, 4, 2, 1);
2073 try GprCore.appendValueLocationRange(&emitter, func.getArgument(0), 0, 2, .rax, .resident, .source, .retain);
2074 try GprCore.appendValueLocationRange(&emitter, constant.getResult(), 1, 3, .rax, .resident, .source, .retain);
2075
2076 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2077 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
2078 try GprCore.verifyAllocation(&emitter, candidates.slice(), fixed_position_index);
2079 }
2080
2081 test "allocation verifier accepts copied fixed definition homes" {
2082 const builtin = @import("../../dialects/root.zig");
2083 const Arith = builtin.ArithDialect;
2084 const Func = builtin.FuncDialect;
2085
2086 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2087 defer ctx.deinit(std.testing.allocator);
2088 try builtin.registerAllDialects(&ctx);
2089
2090 const i64_type = try Arith.getScalarType(&ctx, .i64);
2091 const loc = ir.Location.getUnknown();
2092 _ = try Func.FuncOp.create(&ctx, loc, "verify_copied_def", &.{}, &.{i64_type});
2093 const constant = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2094
2095 var candidates: GprCore.Candidates = .empty;
2096 defer candidates.deinit(std.testing.allocator);
2097 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2098 defer fixed_positions.deinit(std.testing.allocator);
2099
2100 var order: u32 = 0;
2101 try GprCore.appendCandidate(&candidates, std.testing.allocator, constant.getResult(), 1, &order, false, .{ .fixed = .rax }, .{ .fixed = .rax });
2102 try GprCore.recordUse(&candidates, std.testing.allocator, constant.getResult(), PositionPoint.source(2), .any, 0);
2103 try GprCore.appendFixedPosition(&fixed_positions, std.testing.allocator, 1, .def, .{ .fixed = .rax });
2104
2105 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2106 defer emitter.deinit();
2107
2108 try prepareTestValueLocationIndex(&emitter, &.{constant.getResult()}, 4, 1, 1);
2109 try GprCore.appendValueLocationRange(&emitter, constant.getResult(), 1, 3, .rbx, .resident, .source, .retain);
2110
2111 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2112 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
2113 try GprCore.verifyAllocation(&emitter, candidates.slice(), fixed_position_index);
2114 }
2115
2116 test "range end phase stops before definition phase" {
2117 const builtin = @import("../../dialects/root.zig");
2118 const Arith = builtin.ArithDialect;
2119 const Func = builtin.FuncDialect;
2120
2121 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2122 defer ctx.deinit(std.testing.allocator);
2123 try builtin.registerAllDialects(&ctx);
2124
2125 const i64_type = try Arith.getScalarType(&ctx, .i64);
2126 const loc = ir.Location.getUnknown();
2127 const func = try Func.FuncOp.create(&ctx, loc, "range_end_phase", &.{i64_type}, &.{i64_type});
2128
2129 const range = ValueLocationRange{
2130 .value = func.getArgument(0),
2131 .start = 0,
2132 .end = 2,
2133 .reg = .rax,
2134 .end_phase = .source,
2135 };
2136
2137 try std.testing.expect(range.containsPoint(.{ .position = 1, .phase = .source }));
2138 try std.testing.expect(!range.containsPoint(.{ .position = 1, .phase = .definition }));
2139 }
2140
2141 test "isEligibleFunction rejects multi-block regions" {
2142 const builtin = @import("../../dialects/root.zig");
2143 const Arith = builtin.ArithDialect;
2144 const Func = builtin.FuncDialect;
2145
2146 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2147 defer ctx.deinit(std.testing.allocator);
2148 try builtin.registerAllDialects(&ctx);
2149
2150 const i64_type = try Arith.getScalarType(&ctx, .i64);
2151 const loc = ir.Location.getUnknown();
2152
2153 const func = try Func.FuncOp.create(&ctx, loc, "f", &.{i64_type}, &.{i64_type});
2154 const entry = func.getEntryBlock();
2155 const c = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 3);
2156 try entry.addOperation(c.op);
2157 const add = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), c.getResult());
2158 try entry.addOperation(add.op);
2159 const ret = try Func.ReturnOp.create(&ctx, loc, &.{add.getResult()});
2160 try entry.addOperation(ret.op);
2161
2162 try std.testing.expect(isEligibleFunction(func.getBody()));
2163
2164 const f32_type = try Arith.getScalarType(&ctx, .f32);
2165 const gfunc = try Func.FuncOp.create(&ctx, loc, "g", &.{f32_type}, &.{f32_type});
2166 const gentry = gfunc.getEntryBlock();
2167 const gret = try Func.ReturnOp.create(&ctx, loc, &.{gfunc.getArgument(0)});
2168 try gentry.addOperation(gret.op);
2169 try std.testing.expect(!isEligibleFunction(gfunc.getBody()));
2170 }
2171
2172 test "allocate reuses caller saved registers for disjoint intervals" {
2173 const builtin = @import("../../dialects/root.zig");
2174 const Arith = builtin.ArithDialect;
2175 const Func = builtin.FuncDialect;
2176
2177 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2178 defer ctx.deinit(std.testing.allocator);
2179 try builtin.registerAllDialects(&ctx);
2180
2181 const i64_type = try Arith.getScalarType(&ctx, .i64);
2182 const loc = ir.Location.getUnknown();
2183
2184 const func = try Func.FuncOp.create(&ctx, loc, "reuse", &.{}, &.{i64_type});
2185 const entry = func.getEntryBlock();
2186 const c0 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2187 try entry.addOperation(c0.op);
2188 const c1 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
2189 try entry.addOperation(c1.op);
2190 const sum0 = try Arith.AddOp.create(&ctx, loc, c0.getResult(), c1.getResult());
2191 try entry.addOperation(sum0.op);
2192 const c2 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 3);
2193 try entry.addOperation(c2.op);
2194 const c3 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 4);
2195 try entry.addOperation(c3.op);
2196 const sum1 = try Arith.AddOp.create(&ctx, loc, c2.getResult(), c3.getResult());
2197 try entry.addOperation(sum1.op);
2198 const sum2 = try Arith.AddOp.create(&ctx, loc, sum0.getResult(), sum1.getResult());
2199 try entry.addOperation(sum2.op);
2200 const ret = try Func.ReturnOp.create(&ctx, loc, &.{sum2.getResult()});
2201 try entry.addOperation(ret.op);
2202
2203 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2204 defer emitter.deinit();
2205
2206 try allocate(&emitter, func.getBody());
2207
2208 try std.testing.expect(emitter.value_locations.count() > callee_saved_homes.len);
2209 try std.testing.expect(hasCallerSavedHome(&emitter));
2210 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2211 try std.testing.expectEqual(@as(u32, 1), emitter.operation_positions.get(c0.op).?);
2212 try std.testing.expectEqual(@as(u32, 7), emitter.operation_positions.get(sum2.op).?);
2213 try std.testing.expectEqual(@as(u32, 8), emitter.operation_positions.get(ret.op).?);
2214 }
2215
2216 test "allocate reuses registers across scf if branches" {
2217 const builtin = @import("../../dialects/root.zig");
2218 const Arith = builtin.ArithDialect;
2219 const Func = builtin.FuncDialect;
2220 const Scf = builtin.ScfDialect;
2221
2222 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2223 defer ctx.deinit(std.testing.allocator);
2224 try builtin.registerAllDialects(&ctx);
2225
2226 const i64_type = try Arith.getScalarType(&ctx, .i64);
2227 const bool_type = try Arith.getScalarType(&ctx, .bool);
2228 const loc = ir.Location.getUnknown();
2229
2230 const func = try Func.FuncOp.create(&ctx, loc, "branch_reuse", &.{bool_type}, &.{i64_type});
2231 const entry = func.getEntryBlock();
2232 var if_op = try Scf.IfOp.create(&ctx, loc, func.getArgument(0), &.{i64_type});
2233 try entry.addOperation(if_op.op);
2234
2235 const then_block = if_op.getThenBlock();
2236 const t0 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2237 try then_block.addOperation(t0.op);
2238 const t1 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
2239 try then_block.addOperation(t1.op);
2240 const tsum = try Arith.AddOp.create(&ctx, loc, t0.getResult(), t1.getResult());
2241 try then_block.addOperation(tsum.op);
2242 const then_yield = try Scf.YieldOp.create(&ctx, loc, &.{tsum.getResult()});
2243 try then_block.addOperation(then_yield.op);
2244
2245 const else_block = if_op.getElseBlock().?;
2246 const e0 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 3);
2247 try else_block.addOperation(e0.op);
2248 const e1 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 4);
2249 try else_block.addOperation(e1.op);
2250 const esum = try Arith.AddOp.create(&ctx, loc, e0.getResult(), e1.getResult());
2251 try else_block.addOperation(esum.op);
2252 const else_yield = try Scf.YieldOp.create(&ctx, loc, &.{esum.getResult()});
2253 try else_block.addOperation(else_yield.op);
2254
2255 const ret = try Func.ReturnOp.create(&ctx, loc, &.{if_op.getResult(0).?});
2256 try entry.addOperation(ret.op);
2257
2258 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2259 defer emitter.deinit();
2260
2261 try allocate(&emitter, func.getBody());
2262
2263 try std.testing.expect(emitter.value_locations.contains(tsum.getResult()));
2264 try std.testing.expect(emitter.value_locations.contains(esum.getResult()));
2265 try std.testing.expect(emitter.value_locations.contains(if_op.getResult(0).?));
2266 try std.testing.expect(emitter.value_locations.count() > callee_saved_homes.len);
2267 try std.testing.expect(hasCallerSavedHome(&emitter));
2268 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2269 }
2270
2271 test "allocate evicts lower priority intervals under pressure" {
2272 const builtin = @import("../../dialects/root.zig");
2273 const Arith = builtin.ArithDialect;
2274 const Func = builtin.FuncDialect;
2275
2276 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2277 defer ctx.deinit(std.testing.allocator);
2278 try builtin.registerAllDialects(&ctx);
2279
2280 const i64_type = try Arith.getScalarType(&ctx, .i64);
2281 const loc = ir.Location.getUnknown();
2282
2283 const func = try Func.FuncOp.create(&ctx, loc, "spill_priority", &.{ i64_type, i64_type }, &.{i64_type});
2284 const cold = func.getArgument(0);
2285 const hot = func.getArgument(1);
2286
2287 var candidates: GprCore.Candidates = .empty;
2288 defer candidates.deinit(std.testing.allocator);
2289 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2290 defer fixed_positions.deinit(std.testing.allocator);
2291
2292 var order: u32 = 0;
2293 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2294 try GprCore.appendCandidate(&candidates, std.testing.allocator, hot, 1, &order, false, .any, .any);
2295 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(40), .any, 0);
2296 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(41), .any, 0);
2297 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(2), .any, 0);
2298 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(3), .any, 0);
2299 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(4), .any, 0);
2300 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(5), .any, 0);
2301
2302 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2303 defer emitter.deinit();
2304
2305 const homes = [_]GPR{.rbx};
2306 try GprCore.allocateIntervalHomes(&emitter, &candidates, fixed_positions.items, &homes, &.{});
2307
2308 try std.testing.expect(!emitter.value_locations.contains(cold));
2309 try std.testing.expectEqual(GPR.rbx, try locationFor(&emitter, hot));
2310 try std.testing.expectEqual(@as(usize, 3), emitter.value_location_ranges.items.len);
2311 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 0, 1, .rbx, .resident, .definition, .spill));
2312 try std.testing.expect(hasValueLocationRange(&emitter, hot, 1, 6, .rbx));
2313 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 40, 42, .rbx, .reload, .source, .retain));
2314 try std.testing.expectEqual(@as(usize, 1), emitter.reserved_callee_saved);
2315 }
2316
2317 test "allocate chooses longest resident prefix before blockers" {
2318 const builtin = @import("../../dialects/root.zig");
2319 const Arith = builtin.ArithDialect;
2320 const Func = builtin.FuncDialect;
2321
2322 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2323 defer ctx.deinit(std.testing.allocator);
2324 try builtin.registerAllDialects(&ctx);
2325
2326 const i64_type = try Arith.getScalarType(&ctx, .i64);
2327 const loc = ir.Location.getUnknown();
2328
2329 const func = try Func.FuncOp.create(&ctx, loc, "resident_prefix", &.{i64_type}, &.{i64_type});
2330 const value = func.getArgument(0);
2331
2332 var candidates: GprCore.Candidates = .empty;
2333 defer candidates.deinit(std.testing.allocator);
2334
2335 var order: u32 = 0;
2336 try GprCore.appendCandidate(&candidates, std.testing.allocator, value, 0, &order, false, .any, .any);
2337 try GprCore.recordUse(&candidates, std.testing.allocator, value, PositionPoint.source(50), .any, 0);
2338 try GprCore.recordUse(&candidates, std.testing.allocator, value, PositionPoint.source(70), .any, GprCore.regBit(.r12));
2339
2340 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2341 defer emitter.deinit();
2342
2343 var fixed_positions = [_]GprCore.FixedPosition{.{
2344 .point = PositionPoint.source(40),
2345 .reg = .rbx,
2346 .kind = .scratch_use,
2347 }};
2348 const homes = [_]GPR{ .rbx, .r12 };
2349 try GprCore.allocateIntervalHomes(&emitter, &candidates, &fixed_positions, &homes, &.{});
2350
2351 try std.testing.expect(!emitter.value_locations.contains(value));
2352 try std.testing.expectEqual(@as(usize, 2), emitter.value_location_ranges.items.len);
2353 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, value, 0, 70, .r12, .resident, .definition, .spill));
2354 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, value, 70, 71, .rbx, .reload, .source, .retain));
2355 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2356 const fixed_position_index = GprCore.FixedPositionIndex.init(&fixed_positions, &fixed_position_index_storage);
2357 try GprCore.verifyAllocation(&emitter, candidates.slice(), fixed_position_index);
2358 }
2359
2360 test "append reload ranges stops before next register range" {
2361 const builtin = @import("../../dialects/root.zig");
2362 const Arith = builtin.ArithDialect;
2363 const Func = builtin.FuncDialect;
2364
2365 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2366 defer ctx.deinit(std.testing.allocator);
2367 try builtin.registerAllDialects(&ctx);
2368
2369 const i64_type = try Arith.getScalarType(&ctx, .i64);
2370 const loc = ir.Location.getUnknown();
2371
2372 const func = try Func.FuncOp.create(&ctx, loc, "reload_range_blocker", &.{ i64_type, i64_type }, &.{i64_type});
2373 const cold = func.getArgument(0);
2374 const blocker = func.getArgument(1);
2375
2376 var candidates: GprCore.Candidates = .empty;
2377 defer candidates.deinit(std.testing.allocator);
2378
2379 var order: u32 = 0;
2380 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2381 try GprCore.appendCandidate(&candidates, std.testing.allocator, blocker, 42, &order, false, .any, .any);
2382 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(40), .{ .fixed = .rbx }, 0);
2383 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(41), .{ .fixed = .rbx }, 0);
2384 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(43), .{ .fixed = .rbx }, 0);
2385 try GprCore.recordUse(&candidates, std.testing.allocator, blocker, PositionPoint.source(43), .any, 0);
2386
2387 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2388 defer emitter.deinit();
2389
2390 const homes = [_]GPR{ .rbx, .r12 };
2391 try GprCore.prepareLocationIndex(&emitter, candidates.slice(), &homes);
2392 try GprCore.appendValueLocationRange(&emitter, blocker, 42, 44, .rbx, .resident, .source, .retain);
2393 try GprCore.appendReloadRanges(&emitter, candidates.slice(), GprCore.FixedPositionIndex.empty(), &homes, &.{});
2394
2395 try std.testing.expectEqual(@as(usize, 2), emitter.value_location_ranges.items.len);
2396 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 40, 42, .rbx, .reload, .definition, .retain));
2397 }
2398
2399 test "append reload ranges chooses longest available home" {
2400 const builtin = @import("../../dialects/root.zig");
2401 const Arith = builtin.ArithDialect;
2402 const Func = builtin.FuncDialect;
2403
2404 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2405 defer ctx.deinit(std.testing.allocator);
2406 try builtin.registerAllDialects(&ctx);
2407
2408 const i64_type = try Arith.getScalarType(&ctx, .i64);
2409 const loc = ir.Location.getUnknown();
2410
2411 const func = try Func.FuncOp.create(&ctx, loc, "reload_range_choice", &.{ i64_type, i64_type }, &.{i64_type});
2412 const cold = func.getArgument(0);
2413 const blocker = func.getArgument(1);
2414
2415 var candidates: GprCore.Candidates = .empty;
2416 defer candidates.deinit(std.testing.allocator);
2417
2418 var order: u32 = 0;
2419 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2420 try GprCore.appendCandidate(&candidates, std.testing.allocator, blocker, 42, &order, false, .any, .any);
2421 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(40), .any, 0);
2422 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(41), .any, 0);
2423 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(43), .any, 0);
2424 try GprCore.recordUse(&candidates, std.testing.allocator, blocker, PositionPoint.source(43), .any, 0);
2425
2426 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2427 defer emitter.deinit();
2428
2429 const homes = [_]GPR{ .rbx, .r12 };
2430 try GprCore.prepareLocationIndex(&emitter, candidates.slice(), &homes);
2431 try GprCore.appendValueLocationRange(&emitter, blocker, 42, 44, .rbx, .resident, .source, .retain);
2432 try GprCore.appendReloadRanges(&emitter, candidates.slice(), GprCore.FixedPositionIndex.empty(), &homes, &.{});
2433
2434 try std.testing.expectEqual(@as(usize, 2), emitter.value_location_ranges.items.len);
2435 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 40, 44, .r12, .reload, .source, .retain));
2436 }
2437
2438 test "append reload ranges stops before source blockers" {
2439 const builtin = @import("../../dialects/root.zig");
2440 const Arith = builtin.ArithDialect;
2441 const Func = builtin.FuncDialect;
2442
2443 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2444 defer ctx.deinit(std.testing.allocator);
2445 try builtin.registerAllDialects(&ctx);
2446
2447 const i64_type = try Arith.getScalarType(&ctx, .i64);
2448 const loc = ir.Location.getUnknown();
2449
2450 const func = try Func.FuncOp.create(&ctx, loc, "reload_source_blocker", &.{i64_type}, &.{i64_type});
2451 const cold = func.getArgument(0);
2452
2453 var candidates: GprCore.Candidates = .empty;
2454 defer candidates.deinit(std.testing.allocator);
2455
2456 var order: u32 = 0;
2457 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2458 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(40), .{ .fixed = .rbx }, 0);
2459 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(41), .{ .fixed = .rbx }, 0);
2460 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(42), .any, GprCore.regBit(.rbx));
2461
2462 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2463 defer emitter.deinit();
2464
2465 const homes = [_]GPR{ .rbx, .r12 };
2466 try GprCore.prepareLocationIndex(&emitter, candidates.slice(), &homes);
2467 try GprCore.appendReloadRanges(&emitter, candidates.slice(), GprCore.FixedPositionIndex.empty(), &homes, &.{});
2468
2469 try std.testing.expectEqual(@as(usize, 2), emitter.value_location_ranges.items.len);
2470 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 40, 42, .rbx, .reload, .definition, .retain));
2471 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 42, 43, .r12, .reload, .source, .retain));
2472 }
2473
2474 test "append reload ranges rejects fixed positions at current point" {
2475 const builtin = @import("../../dialects/root.zig");
2476 const Arith = builtin.ArithDialect;
2477 const Func = builtin.FuncDialect;
2478
2479 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2480 defer ctx.deinit(std.testing.allocator);
2481 try builtin.registerAllDialects(&ctx);
2482
2483 const i64_type = try Arith.getScalarType(&ctx, .i64);
2484 const loc = ir.Location.getUnknown();
2485
2486 const func = try Func.FuncOp.create(&ctx, loc, "reload_current_fixed", &.{i64_type}, &.{i64_type});
2487 const cold = func.getArgument(0);
2488
2489 var candidates: GprCore.Candidates = .empty;
2490 defer candidates.deinit(std.testing.allocator);
2491
2492 var order: u32 = 0;
2493 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2494 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(40), .any, 0);
2495
2496 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2497 defer emitter.deinit();
2498
2499 var fixed_positions = [_]GprCore.FixedPosition{.{
2500 .point = PositionPoint.source(40),
2501 .reg = .rbx,
2502 .kind = .scratch_use,
2503 }};
2504 const homes = [_]GPR{ .rbx, .r12 };
2505 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2506 const fixed_position_index = GprCore.FixedPositionIndex.init(&fixed_positions, &fixed_position_index_storage);
2507 try GprCore.prepareLocationIndex(&emitter, candidates.slice(), &homes);
2508 try GprCore.appendReloadRanges(&emitter, candidates.slice(), fixed_position_index, &homes, &.{});
2509
2510 try std.testing.expectEqual(@as(usize, 1), emitter.value_location_ranges.items.len);
2511 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 40, 41, .r12, .reload, .source, .retain));
2512 try GprCore.verifyAllocation(&emitter, candidates.slice(), fixed_position_index);
2513 }
2514
2515 test "allocate reloads source into same-position result home" {
2516 const builtin = @import("../../dialects/root.zig");
2517 const Arith = builtin.ArithDialect;
2518 const Func = builtin.FuncDialect;
2519
2520 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2521 defer ctx.deinit(std.testing.allocator);
2522 try builtin.registerAllDialects(&ctx);
2523
2524 const i64_type = try Arith.getScalarType(&ctx, .i64);
2525 const loc = ir.Location.getUnknown();
2526
2527 const func = try Func.FuncOp.create(&ctx, loc, "source_def_phase", &.{ i64_type, i64_type }, &.{i64_type});
2528 const cold = func.getArgument(0);
2529 const hot = func.getArgument(1);
2530 const constant = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 7);
2531 const late_result = constant.getResult();
2532
2533 var candidates: GprCore.Candidates = .empty;
2534 defer candidates.deinit(std.testing.allocator);
2535 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2536 defer fixed_positions.deinit(std.testing.allocator);
2537
2538 var order: u32 = 0;
2539 try GprCore.appendCandidate(&candidates, std.testing.allocator, cold, 0, &order, false, .any, .any);
2540 try GprCore.appendCandidate(&candidates, std.testing.allocator, hot, 1, &order, false, .any, .any);
2541 try GprCore.appendCandidate(&candidates, std.testing.allocator, late_result, 5, &order, false, .{ .fixed = .rax }, .{ .fixed = .rax });
2542 try GprCore.recordUse(&candidates, std.testing.allocator, cold, PositionPoint.source(5), .{ .fixed = .rax }, 0);
2543 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(2), .any, 0);
2544 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(3), .any, 0);
2545 try GprCore.recordUse(&candidates, std.testing.allocator, hot, PositionPoint.source(4), .any, 0);
2546 try GprCore.recordUse(&candidates, std.testing.allocator, late_result, PositionPoint.source(6), .any, 0);
2547
2548 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2549 defer emitter.deinit();
2550
2551 const homes = [_]GPR{.rax};
2552 try GprCore.allocateIntervalHomes(&emitter, &candidates, fixed_positions.items, &homes, &.{});
2553
2554 try std.testing.expect(!emitter.value_locations.contains(cold));
2555 try std.testing.expectEqual(GPR.rax, try locationFor(&emitter, late_result));
2556 try std.testing.expectEqual(@as(usize, 4), emitter.value_location_ranges.items.len);
2557 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 0, 1, .rax, .resident, .definition, .spill));
2558 try std.testing.expect(hasValueLocationRange(&emitter, hot, 1, 5, .rax));
2559 try std.testing.expect(hasValueLocationRange(&emitter, late_result, 5, 7, .rax));
2560 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, cold, 5, 6, .rax, .reload, .source, .retain));
2561 }
2562
2563 test "allocate assigns result to same-position source register" {
2564 const builtin = @import("../../dialects/root.zig");
2565 const Arith = builtin.ArithDialect;
2566 const Func = builtin.FuncDialect;
2567
2568 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2569 defer ctx.deinit(std.testing.allocator);
2570 try builtin.registerAllDialects(&ctx);
2571
2572 const i64_type = try Arith.getScalarType(&ctx, .i64);
2573 const loc = ir.Location.getUnknown();
2574
2575 const func = try Func.FuncOp.create(&ctx, loc, "source_result_phase", &.{i64_type}, &.{i64_type});
2576 const source = func.getArgument(0);
2577 const constant = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 11);
2578 const result = constant.getResult();
2579
2580 var candidates: GprCore.Candidates = .empty;
2581 defer candidates.deinit(std.testing.allocator);
2582 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2583 defer fixed_positions.deinit(std.testing.allocator);
2584
2585 var order: u32 = 0;
2586 try GprCore.appendCandidate(&candidates, std.testing.allocator, source, 0, &order, false, .any, .any);
2587 try GprCore.appendCandidate(&candidates, std.testing.allocator, result, 5, &order, false, .any, .any);
2588 try GprCore.recordFixedSourceUse(&candidates, &fixed_positions, std.testing.allocator, source, PositionPoint.source(5), .rax, .scratch_use, 0);
2589 try GprCore.recordUse(&candidates, std.testing.allocator, result, PositionPoint.source(6), .any, 0);
2590
2591 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2592 defer emitter.deinit();
2593
2594 const homes = [_]GPR{.rax};
2595 try GprCore.allocateIntervalHomes(&emitter, &candidates, fixed_positions.items, &homes, &.{});
2596
2597 try std.testing.expectEqual(GPR.rax, try locationFor(&emitter, result));
2598 try std.testing.expect(hasValueLocationRange(&emitter, source, 0, 6, .rax));
2599 try std.testing.expect(hasValueLocationRange(&emitter, result, 5, 7, .rax));
2600 }
2601
2602 test "active expiration keeps same-position source ranges overlapping" {
2603 const builtin = @import("../../dialects/root.zig");
2604 const Arith = builtin.ArithDialect;
2605 const Func = builtin.FuncDialect;
2606
2607 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2608 defer ctx.deinit(std.testing.allocator);
2609 try builtin.registerAllDialects(&ctx);
2610
2611 const i64_type = try Arith.getScalarType(&ctx, .i64);
2612 const loc = ir.Location.getUnknown();
2613
2614 const func = try Func.FuncOp.create(&ctx, loc, "source_source_overlap", &.{ i64_type, i64_type }, &.{i64_type});
2615 const live_source = func.getArgument(0);
2616 const starting_source = func.getArgument(1);
2617
2618 var candidates: GprCore.Candidates = .empty;
2619 defer candidates.deinit(std.testing.allocator);
2620 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2621 defer fixed_positions.deinit(std.testing.allocator);
2622
2623 var order: u32 = 0;
2624 try GprCore.appendCandidate(&candidates, std.testing.allocator, live_source, 0, &order, false, .any, .any);
2625 try GprCore.appendCandidate(&candidates, std.testing.allocator, starting_source, 5, &order, false, .any, .any);
2626 try GprCore.recordUse(&candidates, std.testing.allocator, live_source, PositionPoint.source(1), .any, 0);
2627 try GprCore.recordUse(&candidates, std.testing.allocator, live_source, PositionPoint.source(2), .any, 0);
2628 try GprCore.recordUse(&candidates, std.testing.allocator, live_source, PositionPoint.source(3), .any, 0);
2629 try GprCore.recordUse(&candidates, std.testing.allocator, live_source, PositionPoint.source(4), .any, 0);
2630 try GprCore.recordUse(&candidates, std.testing.allocator, live_source, PositionPoint.source(5), .any, 0);
2631 try GprCore.recordUse(&candidates, std.testing.allocator, starting_source, PositionPoint.source(100), .any, 0);
2632
2633 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2634 defer emitter.deinit();
2635
2636 const homes = [_]GPR{.rbx};
2637 try GprCore.allocateIntervalHomes(&emitter, &candidates, fixed_positions.items, &homes, &.{});
2638
2639 try std.testing.expectEqual(GPR.rbx, try locationFor(&emitter, live_source));
2640 try std.testing.expect(!emitter.value_locations.contains(starting_source));
2641 try std.testing.expect(hasValueLocationRange(&emitter, live_source, 0, 6, .rbx));
2642 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, starting_source, 100, 101, .rbx, .reload, .source, .retain));
2643 }
2644
2645 test "definition point use extends range through definition phase" {
2646 const builtin = @import("../../dialects/root.zig");
2647 const Arith = builtin.ArithDialect;
2648 const Func = builtin.FuncDialect;
2649
2650 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2651 defer ctx.deinit(std.testing.allocator);
2652 try builtin.registerAllDialects(&ctx);
2653
2654 const i64_type = try Arith.getScalarType(&ctx, .i64);
2655 const loc = ir.Location.getUnknown();
2656
2657 const func = try Func.FuncOp.create(&ctx, loc, "definition_point_use", &.{i64_type}, &.{i64_type});
2658 const value = func.getArgument(0);
2659
2660 var candidates: GprCore.Candidates = .empty;
2661 defer candidates.deinit(std.testing.allocator);
2662 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2663 defer fixed_positions.deinit(std.testing.allocator);
2664
2665 var order: u32 = 0;
2666 try GprCore.appendCandidate(&candidates, std.testing.allocator, value, 0, &order, false, .any, .any);
2667 try GprCore.recordUse(&candidates, std.testing.allocator, value, PositionPoint.definition(5), .any, 0);
2668 try GprCore.appendFixedPosition(&fixed_positions, std.testing.allocator, 5, .clobber, .{ .fixed = .rax });
2669
2670 const candidate = candidates.getPtr(value) orelse return error.TestFailure;
2671 try std.testing.expectEqual(PositionPhase.definition, candidate.endPhase());
2672 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2673 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
2674 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(candidate.*, fixed_position_index, .rax));
2675
2676 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2677 defer emitter.deinit();
2678
2679 const homes = [_]GPR{.rbx};
2680 try GprCore.allocateIntervalHomes(&emitter, &candidates, fixed_positions.items, &homes, &.{});
2681
2682 try std.testing.expect(hasValueLocationRangeWithActions(&emitter, value, 0, 6, .rbx, .resident, .definition, .retain));
2683 }
2684
2685 test "allocate admits scalar call operands and results" {
2686 const builtin = @import("../../dialects/root.zig");
2687 const Arith = builtin.ArithDialect;
2688 const Func = builtin.FuncDialect;
2689
2690 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2691 defer ctx.deinit(std.testing.allocator);
2692 try builtin.registerAllDialects(&ctx);
2693
2694 const i64_type = try Arith.getScalarType(&ctx, .i64);
2695 const loc = ir.Location.getUnknown();
2696
2697 const func = try Func.FuncOp.create(&ctx, loc, "call_reuse", &.{i64_type}, &.{i64_type});
2698 const entry = func.getEntryBlock();
2699
2700 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2701 try entry.addOperation(one.op);
2702 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), one.getResult());
2703 try entry.addOperation(shifted.op);
2704 const call = try Func.CallOp.create(&ctx, loc, "choir_external_add1", &.{shifted.getResult()}, &.{i64_type});
2705 try entry.addOperation(call.op);
2706 const result = call.getResult(0) orelse return error.TestFailure;
2707 const final_sum = try Arith.AddOp.create(&ctx, loc, result, shifted.getResult());
2708 try entry.addOperation(final_sum.op);
2709 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
2710 try entry.addOperation(ret.op);
2711
2712 try std.testing.expect(isEligibleFunction(func.getBody()));
2713
2714 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2715 defer emitter.deinit();
2716
2717 try allocate(&emitter, func.getBody());
2718
2719 try std.testing.expect(emitter.value_locations.contains(shifted.getResult()));
2720 try std.testing.expect(emitter.value_locations.contains(result));
2721
2722 const shifted_home = try locationFor(&emitter, shifted.getResult());
2723 try std.testing.expect(shifted_home.isCalleeSaved());
2724 const result_home = try locationFor(&emitter, result);
2725 try std.testing.expect(result_home.isCallerSaved());
2726 try std.testing.expectEqual(@as(usize, 1), emitter.reserved_callee_saved);
2727 }
2728
2729 test "allocate assigns caller saved homes through while regions" {
2730 const builtin = @import("../../dialects/root.zig");
2731 const Arith = builtin.ArithDialect;
2732 const Func = builtin.FuncDialect;
2733 const Scf = builtin.ScfDialect;
2734
2735 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2736 defer ctx.deinit(std.testing.allocator);
2737 try builtin.registerAllDialects(&ctx);
2738
2739 const i64_type = try Arith.getScalarType(&ctx, .i64);
2740 const loc = ir.Location.getUnknown();
2741
2742 const func = try Func.FuncOp.create(&ctx, loc, "while_alloc", &.{}, &.{i64_type});
2743 const entry = func.getEntryBlock();
2744 const n_init = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 5);
2745 try entry.addOperation(n_init.op);
2746 const acc_init = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 0);
2747 try entry.addOperation(acc_init.op);
2748
2749 var while_op = try Scf.WhileOp.create(&ctx, loc, &.{ n_init.getResult(), acc_init.getResult() }, &.{ i64_type, i64_type });
2750 try entry.addOperation(while_op.op);
2751
2752 const before = while_op.getBeforeBlock();
2753 const before_n = before.arguments.items[0];
2754 const before_acc = before.arguments.items[1];
2755 const zero = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 0);
2756 try before.addOperation(zero.op);
2757 const keep_going = try Arith.CmpOp.create(&ctx, loc, .gt, before_n, zero.getResult());
2758 try before.addOperation(keep_going.op);
2759 const condition = try Scf.ConditionOp.create(&ctx, loc, keep_going.getResult(), &.{ before_n, before_acc });
2760 try before.addOperation(condition.op);
2761
2762 const after = while_op.getAfterBlock();
2763 const after_n = after.arguments.items[0];
2764 const after_acc = after.arguments.items[1];
2765 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2766 try after.addOperation(one.op);
2767 const next_n = try Arith.SubOp.create(&ctx, loc, after_n, one.getResult());
2768 try after.addOperation(next_n.op);
2769 const next_acc = try Arith.AddOp.create(&ctx, loc, after_acc, after_n);
2770 try after.addOperation(next_acc.op);
2771 const yield = try Scf.YieldOp.create(&ctx, loc, &.{ next_n.getResult(), next_acc.getResult() });
2772 try after.addOperation(yield.op);
2773
2774 const result = while_op.op.getResult(1) orelse return error.TestFailure;
2775 const ret = try Func.ReturnOp.create(&ctx, loc, &.{result});
2776 try entry.addOperation(ret.op);
2777
2778 var emitter = TestEmitter{ .allocator = std.testing.allocator };
2779 defer emitter.deinit();
2780
2781 try allocate(&emitter, func.getBody());
2782
2783 try std.testing.expect(hasCallerSavedHome(&emitter));
2784 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2785 try std.testing.expect((try locationFor(&emitter, before_n)).isCallerSaved());
2786 try std.testing.expect((try locationFor(&emitter, before_acc)).isCallerSaved());
2787 try std.testing.expect((try locationFor(&emitter, after_n)).isCallerSaved());
2788 try std.testing.expect((try locationFor(&emitter, after_acc)).isCallerSaved());
2789 try std.testing.expect((try locationFor(&emitter, result)).isCallerSaved());
2790 }
2791
2792 test "collects ordered use positions for scalar intervals" {
2793 const builtin = @import("../../dialects/root.zig");
2794 const Arith = builtin.ArithDialect;
2795 const Func = builtin.FuncDialect;
2796
2797 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2798 defer ctx.deinit(std.testing.allocator);
2799 try builtin.registerAllDialects(&ctx);
2800
2801 const i64_type = try Arith.getScalarType(&ctx, .i64);
2802 const loc = ir.Location.getUnknown();
2803
2804 const func = try Func.FuncOp.create(&ctx, loc, "use_positions", &.{i64_type}, &.{i64_type});
2805 const entry = func.getEntryBlock();
2806
2807 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2808 try entry.addOperation(one.op);
2809 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), one.getResult());
2810 try entry.addOperation(shifted.op);
2811 const two = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
2812 try entry.addOperation(two.op);
2813 const product = try Arith.MulOp.create(&ctx, loc, shifted.getResult(), two.getResult());
2814 try entry.addOperation(product.op);
2815 const final_sum = try Arith.AddOp.create(&ctx, loc, shifted.getResult(), product.getResult());
2816 try entry.addOperation(final_sum.op);
2817 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
2818 try entry.addOperation(ret.op);
2819
2820 try std.testing.expect(isEligibleFunction(func.getBody()));
2821
2822 var candidates: GprCore.Candidates = .empty;
2823 defer candidates.deinit(std.testing.allocator);
2824 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2825 defer fixed_positions.deinit(std.testing.allocator);
2826
2827 var position: u32 = 1;
2828 var order: u32 = 0;
2829 var test_books = TestBooks{};
2830 defer test_books.deinit(std.testing.allocator);
2831 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
2832
2833 const shifted_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
2834 try std.testing.expectEqual(@as(u32, 2), shifted_interval.start());
2835 try std.testing.expectEqual(@as(u32, 5), shifted_interval.end());
2836 try std.testing.expectEqual(@as(usize, 2), shifted_interval.use_positions.items.len);
2837 try std.testing.expectEqual(@as(u32, 4), shifted_interval.use_positions.items[0].point.position);
2838 try std.testing.expectEqual(@as(u32, 5), shifted_interval.use_positions.items[1].point.position);
2839
2840 const final_interval = candidates.getPtr(final_sum.getResult()) orelse return error.TestFailure;
2841 try std.testing.expectEqual(@as(u32, 5), final_interval.start());
2842 try std.testing.expectEqual(@as(u32, 6), final_interval.end());
2843 try std.testing.expectEqual(@as(u32, 6), final_interval.use_positions.items[0].point.position);
2844 }
2845
2846 test "collects ordered use positions through while regions" {
2847 const builtin = @import("../../dialects/root.zig");
2848 const Arith = builtin.ArithDialect;
2849 const Func = builtin.FuncDialect;
2850 const Scf = builtin.ScfDialect;
2851
2852 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2853 defer ctx.deinit(std.testing.allocator);
2854 try builtin.registerAllDialects(&ctx);
2855
2856 const i64_type = try Arith.getScalarType(&ctx, .i64);
2857 const loc = ir.Location.getUnknown();
2858
2859 const func = try Func.FuncOp.create(&ctx, loc, "while_positions", &.{}, &.{i64_type});
2860 const entry = func.getEntryBlock();
2861 const n_init = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 5);
2862 try entry.addOperation(n_init.op);
2863 const acc_init = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 0);
2864 try entry.addOperation(acc_init.op);
2865
2866 var while_op = try Scf.WhileOp.create(&ctx, loc, &.{ n_init.getResult(), acc_init.getResult() }, &.{ i64_type, i64_type });
2867 try entry.addOperation(while_op.op);
2868
2869 const before = while_op.getBeforeBlock();
2870 const before_n = before.arguments.items[0];
2871 const before_acc = before.arguments.items[1];
2872 const zero = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 0);
2873 try before.addOperation(zero.op);
2874 const keep_going = try Arith.CmpOp.create(&ctx, loc, .gt, before_n, zero.getResult());
2875 try before.addOperation(keep_going.op);
2876 const condition = try Scf.ConditionOp.create(&ctx, loc, keep_going.getResult(), &.{ before_n, before_acc });
2877 try before.addOperation(condition.op);
2878
2879 const after = while_op.getAfterBlock();
2880 const after_n = after.arguments.items[0];
2881 const after_acc = after.arguments.items[1];
2882 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2883 try after.addOperation(one.op);
2884 const next_n = try Arith.SubOp.create(&ctx, loc, after_n, one.getResult());
2885 try after.addOperation(next_n.op);
2886 const next_acc = try Arith.AddOp.create(&ctx, loc, after_acc, after_n);
2887 try after.addOperation(next_acc.op);
2888 const yield = try Scf.YieldOp.create(&ctx, loc, &.{ next_n.getResult(), next_acc.getResult() });
2889 try after.addOperation(yield.op);
2890
2891 const result = while_op.op.getResult(1) orelse return error.TestFailure;
2892 const ret = try Func.ReturnOp.create(&ctx, loc, &.{result});
2893 try entry.addOperation(ret.op);
2894
2895 var candidates: GprCore.Candidates = .empty;
2896 defer candidates.deinit(std.testing.allocator);
2897 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2898 defer fixed_positions.deinit(std.testing.allocator);
2899
2900 var position: u32 = 1;
2901 var order: u32 = 0;
2902 var loop_intervals: std.ArrayListUnmanaged(shared.LoopInterval) = .empty;
2903 defer loop_intervals.deinit(std.testing.allocator);
2904 var test_books = TestBooks{};
2905 defer test_books.deinit(std.testing.allocator);
2906 try collectRegionBlockCandidates(test_books.books(&candidates, &fixed_positions), &loop_intervals, null, std.testing.allocator, entry, 0, &position, &order);
2907
2908 const n_init_interval = candidates.getPtr(n_init.getResult()) orelse return error.TestFailure;
2909 try std.testing.expectEqual(@as(u32, 1), n_init_interval.start());
2910 try std.testing.expectEqual(@as(u32, 3), n_init_interval.end());
2911 try std.testing.expectEqual(@as(u32, 3), n_init_interval.use_positions.items[0].point.position);
2912
2913 const before_n_interval = candidates.getPtr(before_n) orelse return error.TestFailure;
2914 try std.testing.expectEqual(@as(u32, 4), before_n_interval.start());
2915 try std.testing.expectEqual(@as(u32, 6), before_n_interval.end());
2916 try std.testing.expectEqual(@as(u32, 5), before_n_interval.use_positions.items[0].point.position);
2917 try std.testing.expectEqual(@as(u32, 6), before_n_interval.use_positions.items[1].point.position);
2918
2919 const after_n_interval = candidates.getPtr(after_n) orelse return error.TestFailure;
2920 try std.testing.expectEqual(@as(u32, 7), after_n_interval.start());
2921 try std.testing.expectEqual(@as(u32, 9), after_n_interval.end());
2922 try std.testing.expectEqual(@as(u32, 8), after_n_interval.use_positions.items[0].point.position);
2923 try std.testing.expectEqual(@as(u32, 9), after_n_interval.use_positions.items[1].point.position);
2924
2925 const next_acc_interval = candidates.getPtr(next_acc.getResult()) orelse return error.TestFailure;
2926 try std.testing.expectEqual(@as(u32, 9), next_acc_interval.start());
2927 try std.testing.expectEqual(@as(u32, 10), next_acc_interval.end());
2928 try std.testing.expectEqual(@as(u32, 10), next_acc_interval.use_positions.items[0].point.position);
2929
2930 const result_interval = candidates.getPtr(result) orelse return error.TestFailure;
2931 try std.testing.expectEqual(@as(u32, 11), result_interval.start());
2932 try std.testing.expectEqual(@as(u32, 12), result_interval.end());
2933 try std.testing.expectEqual(@as(u32, 12), result_interval.use_positions.items[0].point.position);
2934
2935 try std.testing.expect(hasFixedPosition(fixed_positions.items, 5, .clobber, .rax));
2936 try std.testing.expect(hasFixedPosition(fixed_positions.items, 9, .scratch_use, .rcx));
2937 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 0, .clobber, .rax));
2938 }
2939
2940 test "collects entry argument source positions" {
2941 const builtin = @import("../../dialects/root.zig");
2942 const Arith = builtin.ArithDialect;
2943 const Func = builtin.FuncDialect;
2944
2945 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2946 defer ctx.deinit(std.testing.allocator);
2947 try builtin.registerAllDialects(&ctx);
2948
2949 const i64_type = try Arith.getScalarType(&ctx, .i64);
2950 const loc = ir.Location.getUnknown();
2951
2952 const func = try Func.FuncOp.create(&ctx, loc, "entry_sources", &.{ i64_type, i64_type }, &.{i64_type});
2953 const entry = func.getEntryBlock();
2954
2955 const sum = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
2956 try entry.addOperation(sum.op);
2957 const ret = try Func.ReturnOp.create(&ctx, loc, &.{sum.getResult()});
2958 try entry.addOperation(ret.op);
2959
2960 var candidates: GprCore.Candidates = .empty;
2961 defer candidates.deinit(std.testing.allocator);
2962 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
2963 defer fixed_positions.deinit(std.testing.allocator);
2964
2965 var position: u32 = 1;
2966 var order: u32 = 0;
2967 var test_books = TestBooks{};
2968 defer test_books.deinit(std.testing.allocator);
2969 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
2970
2971 const arg0_interval = candidates.getPtr(func.getArgument(0)) orelse return error.TestFailure;
2972 try expectAnyRequirement(arg0_interval.definition.requirement);
2973 try expectFixedGpr(arg0_interval.definition.source, abi.int_arg_regs[0]);
2974
2975 const arg1_interval = candidates.getPtr(func.getArgument(1)) orelse return error.TestFailure;
2976 try expectAnyRequirement(arg1_interval.definition.requirement);
2977 try expectFixedGpr(arg1_interval.definition.source, abi.int_arg_regs[1]);
2978
2979 try std.testing.expect(hasFixedPosition(fixed_positions.items, 0, .source, abi.int_arg_regs[0]));
2980 try std.testing.expect(hasFixedPosition(fixed_positions.items, 0, .source, abi.int_arg_regs[1]));
2981 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
2982 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
2983 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(arg1_interval.*, fixed_position_index, abi.int_arg_regs[0]));
2984 }
2985
2986 test "scalar source order rejects overwritten binary operand homes" {
2987 const builtin = @import("../../dialects/root.zig");
2988 const Arith = builtin.ArithDialect;
2989 const Func = builtin.FuncDialect;
2990
2991 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
2992 defer ctx.deinit(std.testing.allocator);
2993 try builtin.registerAllDialects(&ctx);
2994
2995 const i64_type = try Arith.getScalarType(&ctx, .i64);
2996 const loc = ir.Location.getUnknown();
2997
2998 const func = try Func.FuncOp.create(&ctx, loc, "binary_sources", &.{ i64_type, i64_type }, &.{i64_type});
2999 const entry = func.getEntryBlock();
3000
3001 const sum = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3002 try entry.addOperation(sum.op);
3003 const ret = try Func.ReturnOp.create(&ctx, loc, &.{sum.getResult()});
3004 try entry.addOperation(ret.op);
3005
3006 var candidates: GprCore.Candidates = .empty;
3007 defer candidates.deinit(std.testing.allocator);
3008 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3009 defer fixed_positions.deinit(std.testing.allocator);
3010
3011 var position: u32 = 1;
3012 var order: u32 = 0;
3013 var test_books = TestBooks{};
3014 defer test_books.deinit(std.testing.allocator);
3015 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3016
3017 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3018 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3019 const lhs_interval = candidates.getPtr(func.getArgument(0)) orelse return error.TestFailure;
3020 try expectFixedGpr(lhs_interval.use_positions.items[0].requirement, .rax);
3021 try expectUseBlockers(lhs_interval.*, 0, &.{}, &.{ .rax, .rcx });
3022 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(lhs_interval.*, fixed_position_index, .rax));
3023
3024 const rhs_interval = candidates.getPtr(func.getArgument(1)) orelse return error.TestFailure;
3025 try expectFixedGpr(rhs_interval.use_positions.items[0].requirement, .rcx);
3026 try expectUseBlockers(rhs_interval.*, 0, &.{.rax}, &.{ .rcx, .rdx });
3027 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(rhs_interval.*, fixed_position_index, .rax));
3028 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(rhs_interval.*, fixed_position_index, .rcx));
3029
3030 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rax));
3031 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rcx));
3032 }
3033
3034 test "scalar scratch use preserves operand home" {
3035 const builtin = @import("../../dialects/root.zig");
3036 const Arith = builtin.ArithDialect;
3037 const Func = builtin.FuncDialect;
3038
3039 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3040 defer ctx.deinit(std.testing.allocator);
3041 try builtin.registerAllDialects(&ctx);
3042
3043 const i64_type = try Arith.getScalarType(&ctx, .i64);
3044 const loc = ir.Location.getUnknown();
3045
3046 const func = try Func.FuncOp.create(&ctx, loc, "scratch_use_owner", &.{ i64_type, i64_type, i64_type }, &.{ i64_type, i64_type });
3047 const entry = func.getEntryBlock();
3048
3049 const sum = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3050 try entry.addOperation(sum.op);
3051 const ret = try Func.ReturnOp.create(&ctx, loc, &.{ func.getArgument(1), func.getArgument(2) });
3052 try entry.addOperation(ret.op);
3053
3054 var candidates: GprCore.Candidates = .empty;
3055 defer candidates.deinit(std.testing.allocator);
3056 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3057 defer fixed_positions.deinit(std.testing.allocator);
3058
3059 var position: u32 = 1;
3060 var order: u32 = 0;
3061 var test_books = TestBooks{};
3062 defer test_books.deinit(std.testing.allocator);
3063 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3064
3065 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3066 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3067 const rhs_interval = candidates.getPtr(func.getArgument(1)) orelse return error.TestFailure;
3068 try expectFixedGpr(rhs_interval.use_positions.items[0].requirement, .rcx);
3069 try std.testing.expectEqual(@as(u32, 2), rhs_interval.end());
3070 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(rhs_interval.*, fixed_position_index, .rcx));
3071
3072 const live_interval = candidates.getPtr(func.getArgument(2)) orelse return error.TestFailure;
3073 try std.testing.expectEqual(@as(u32, 2), live_interval.end());
3074 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rcx));
3075 }
3076
3077 test "scalar source order skips immediate rhs registers" {
3078 const builtin = @import("../../dialects/root.zig");
3079 const Arith = builtin.ArithDialect;
3080 const Func = builtin.FuncDialect;
3081
3082 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3083 defer ctx.deinit(std.testing.allocator);
3084 try builtin.registerAllDialects(&ctx);
3085
3086 const i64_type = try Arith.getScalarType(&ctx, .i64);
3087 const loc = ir.Location.getUnknown();
3088
3089 const func = try Func.FuncOp.create(&ctx, loc, "immediate_sources", &.{i64_type}, &.{i64_type});
3090 const entry = func.getEntryBlock();
3091
3092 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3093 try entry.addOperation(one.op);
3094 const diff = try Arith.SubOp.create(&ctx, loc, func.getArgument(0), one.getResult());
3095 try entry.addOperation(diff.op);
3096 const ret = try Func.ReturnOp.create(&ctx, loc, &.{diff.getResult()});
3097 try entry.addOperation(ret.op);
3098
3099 var candidates: GprCore.Candidates = .empty;
3100 defer candidates.deinit(std.testing.allocator);
3101 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3102 defer fixed_positions.deinit(std.testing.allocator);
3103
3104 var position: u32 = 1;
3105 var order: u32 = 0;
3106 var test_books = TestBooks{};
3107 defer test_books.deinit(std.testing.allocator);
3108 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3109
3110 const lhs_interval = candidates.getPtr(func.getArgument(0)) orelse return error.TestFailure;
3111 try expectFixedGpr(lhs_interval.use_positions.items[0].requirement, .rax);
3112 try expectUseBlockers(lhs_interval.*, 0, &.{}, &.{ .rax, .rcx });
3113
3114 const immediate_interval = candidates.getPtr(one.getResult()) orelse return error.TestFailure;
3115 try std.testing.expectEqual(@as(usize, 0), immediate_interval.useCount());
3116
3117 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rax));
3118 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rcx));
3119 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rax));
3120 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 2, .clobber, .rcx));
3121 }
3122
3123 test "scalar source order accumulates select operand blockers" {
3124 const builtin = @import("../../dialects/root.zig");
3125 const Arith = builtin.ArithDialect;
3126 const Func = builtin.FuncDialect;
3127
3128 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3129 defer ctx.deinit(std.testing.allocator);
3130 try builtin.registerAllDialects(&ctx);
3131
3132 const bool_type = try Arith.getScalarType(&ctx, .bool);
3133 const i64_type = try Arith.getScalarType(&ctx, .i64);
3134 const loc = ir.Location.getUnknown();
3135
3136 const func = try Func.FuncOp.create(&ctx, loc, "select_sources", &.{ bool_type, i64_type, i64_type }, &.{i64_type});
3137 const entry = func.getEntryBlock();
3138
3139 const selected = try Arith.SelectOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1), func.getArgument(2));
3140 try entry.addOperation(selected.op);
3141 const ret = try Func.ReturnOp.create(&ctx, loc, &.{selected.getResult()});
3142 try entry.addOperation(ret.op);
3143
3144 var candidates: GprCore.Candidates = .empty;
3145 defer candidates.deinit(std.testing.allocator);
3146 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3147 defer fixed_positions.deinit(std.testing.allocator);
3148
3149 var position: u32 = 1;
3150 var order: u32 = 0;
3151 var test_books = TestBooks{};
3152 defer test_books.deinit(std.testing.allocator);
3153 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3154
3155 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3156 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3157 const cond_interval = candidates.getPtr(func.getArgument(0)) orelse return error.TestFailure;
3158 try expectFixedGpr(cond_interval.use_positions.items[0].requirement, .rax);
3159 try expectUseBlockers(cond_interval.*, 0, &.{}, &.{ .rax, .rcx, .rdx });
3160 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(cond_interval.*, fixed_position_index, .rax));
3161
3162 const true_interval = candidates.getPtr(func.getArgument(1)) orelse return error.TestFailure;
3163 try expectFixedGpr(true_interval.use_positions.items[0].requirement, .rcx);
3164 try expectUseBlockers(true_interval.*, 0, &.{.rax}, &.{ .rcx, .rdx });
3165 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(true_interval.*, fixed_position_index, .rax));
3166 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(true_interval.*, fixed_position_index, .rcx));
3167
3168 const false_interval = candidates.getPtr(func.getArgument(2)) orelse return error.TestFailure;
3169 try expectFixedGpr(false_interval.use_positions.items[0].requirement, .rdx);
3170 try expectUseBlockers(false_interval.*, 0, &.{ .rax, .rcx }, &.{.rdx});
3171 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(false_interval.*, fixed_position_index, .rax));
3172 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(false_interval.*, fixed_position_index, .rcx));
3173 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(false_interval.*, fixed_position_index, .rdx));
3174 }
3175
3176 test "collects fixed call requirements and clobber positions" {
3177 const builtin = @import("../../dialects/root.zig");
3178 const Arith = builtin.ArithDialect;
3179 const Func = builtin.FuncDialect;
3180
3181 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3182 defer ctx.deinit(std.testing.allocator);
3183 try builtin.registerAllDialects(&ctx);
3184
3185 const i64_type = try Arith.getScalarType(&ctx, .i64);
3186 const loc = ir.Location.getUnknown();
3187
3188 const func = try Func.FuncOp.create(&ctx, loc, "call_positions", &.{i64_type}, &.{i64_type});
3189 const entry = func.getEntryBlock();
3190
3191 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3192 try entry.addOperation(one.op);
3193 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), one.getResult());
3194 try entry.addOperation(shifted.op);
3195 const call = try Func.CallOp.create(&ctx, loc, "choir_external_add1", &.{shifted.getResult()}, &.{i64_type});
3196 try entry.addOperation(call.op);
3197 const call_result = call.getResult(0) orelse return error.TestFailure;
3198 const two = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
3199 try entry.addOperation(two.op);
3200 const final_sum = try Arith.AddOp.create(&ctx, loc, call_result, two.getResult());
3201 try entry.addOperation(final_sum.op);
3202 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3203 try entry.addOperation(ret.op);
3204
3205 var candidates: GprCore.Candidates = .empty;
3206 defer candidates.deinit(std.testing.allocator);
3207 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3208 defer fixed_positions.deinit(std.testing.allocator);
3209
3210 var position: u32 = 1;
3211 var order: u32 = 0;
3212 var test_books = TestBooks{};
3213 defer test_books.deinit(std.testing.allocator);
3214 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3215
3216 const shifted_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
3217 try std.testing.expectEqual(@as(usize, 1), shifted_interval.use_positions.items.len);
3218 try std.testing.expectEqual(@as(u32, 3), shifted_interval.use_positions.items[0].point.position);
3219 try expectFixedGpr(shifted_interval.use_positions.items[0].requirement, abi.int_arg_regs[0]);
3220
3221 const call_interval = candidates.getPtr(call_result) orelse return error.TestFailure;
3222 try expectFixedGpr(call_interval.definition.requirement, abi.int_return_reg);
3223 try std.testing.expectEqual(@as(u32, 3), call_interval.definition.point.position);
3224 try std.testing.expectEqual(@as(u32, 5), call_interval.use_positions.items[0].point.position);
3225
3226 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .use, abi.int_arg_regs[0]));
3227 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .def, abi.int_return_reg));
3228 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .clobber, abi.int_return_reg));
3229 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .clobber, .r11));
3230 }
3231
3232 test "syscall operands take the kernel entry registers and not the C ABI's" {
3233 const builtin = @import("../../dialects/root.zig");
3234 const Arith = builtin.ArithDialect;
3235 const Func = builtin.FuncDialect;
3236
3237 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3238 defer ctx.deinit(std.testing.allocator);
3239 try builtin.registerAllDialects(&ctx);
3240
3241 const i64_type = try Arith.getScalarType(&ctx, .i64);
3242 const loc = ir.Location.getUnknown();
3243
3244 const parameters: [syscall_argument_gprs.len + 1]ir.Type = @splat(i64_type);
3245 const func = try Func.FuncOp.create(&ctx, loc, "syscall_positions", ¶meters, &.{i64_type});
3246 const entry = func.getEntryBlock();
3247
3248 var arguments: [syscall_argument_gprs.len]*ir.Value = undefined;
3249 for (&arguments, 1..) |*argument, index| argument.* = func.getArgument(index);
3250 const entered = try Func.SyscallOp.create(&ctx, loc, func.getArgument(0), &arguments, i64_type);
3251 try entry.addOperation(entered.op);
3252 const ret = try Func.ReturnOp.create(&ctx, loc, &.{entered.getResult()});
3253 try entry.addOperation(ret.op);
3254
3255 var candidates: GprCore.Candidates = .empty;
3256 defer candidates.deinit(std.testing.allocator);
3257 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3258 defer fixed_positions.deinit(std.testing.allocator);
3259
3260 var position: u32 = 1;
3261 var order: u32 = 0;
3262 var test_books = TestBooks{};
3263 defer test_books.deinit(std.testing.allocator);
3264 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3265
3266 const expected = [_]GPR{ .rax, .rdi, .rsi, .rdx, .r10, .r8, .r9 };
3267 for (expected, 0..) |reg, index| {
3268 const interval = candidates.getPtr(func.getArgument(index)) orelse return error.TestFailure;
3269 try std.testing.expectEqual(@as(usize, 1), interval.use_positions.items.len);
3270 try std.testing.expectEqual(@as(u32, 1), interval.use_positions.items[0].point.position);
3271 try expectFixedGpr(interval.use_positions.items[0].requirement, reg);
3272 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .use, reg));
3273 }
3274
3275 try std.testing.expectEqual(GPR.rcx, registers.GPR.arg3);
3276 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 1, .use, .rcx));
3277
3278 const result_interval = candidates.getPtr(entered.getResult()) orelse return error.TestFailure;
3279 try expectFixedGpr(result_interval.definition.requirement, .rax);
3280 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rcx));
3281 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .r11));
3282 }
3283
3284 test "call operands do not block parallel argument homes" {
3285 const builtin = @import("../../dialects/root.zig");
3286 const Arith = builtin.ArithDialect;
3287 const Func = builtin.FuncDialect;
3288
3289 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3290 defer ctx.deinit(std.testing.allocator);
3291 try builtin.registerAllDialects(&ctx);
3292
3293 const i64_type = try Arith.getScalarType(&ctx, .i64);
3294 const loc = ir.Location.getUnknown();
3295
3296 const func = try Func.FuncOp.create(&ctx, loc, "call_source_order", &.{}, &.{i64_type});
3297 const entry = func.getEntryBlock();
3298
3299 const c0 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3300 try entry.addOperation(c0.op);
3301 const c1 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
3302 try entry.addOperation(c1.op);
3303 const c2 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 3);
3304 try entry.addOperation(c2.op);
3305 const c3 = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 4);
3306 try entry.addOperation(c3.op);
3307 const call = try Func.CallOp.create(&ctx, loc, "choir_sum4", &.{
3308 c0.getResult(),
3309 c1.getResult(),
3310 c2.getResult(),
3311 c3.getResult(),
3312 }, &.{i64_type});
3313 try entry.addOperation(call.op);
3314 const ret = try Func.ReturnOp.create(&ctx, loc, &.{call.getResult(0).?});
3315 try entry.addOperation(ret.op);
3316
3317 var candidates: GprCore.Candidates = .empty;
3318 defer candidates.deinit(std.testing.allocator);
3319 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3320 defer fixed_positions.deinit(std.testing.allocator);
3321
3322 var position: u32 = 1;
3323 var order: u32 = 0;
3324 var test_books = TestBooks{};
3325 defer test_books.deinit(std.testing.allocator);
3326 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3327
3328 const arg0 = candidates.getPtr(c0.getResult()) orelse return error.TestFailure;
3329 try expectFixedGpr(arg0.use_positions.items[0].requirement, abi.int_arg_regs[0]);
3330 try expectUseBlockers(arg0.*, 0, &.{}, &.{ .rdi, .rsi, .rdx, .rcx });
3331
3332 const arg1 = candidates.getPtr(c1.getResult()) orelse return error.TestFailure;
3333 try expectFixedGpr(arg1.use_positions.items[0].requirement, abi.int_arg_regs[1]);
3334 try expectUseBlockers(arg1.*, 0, &.{}, &.{ .rdi, .rsi, .rdx, .rcx });
3335
3336 const arg2 = candidates.getPtr(c2.getResult()) orelse return error.TestFailure;
3337 try expectFixedGpr(arg2.use_positions.items[0].requirement, abi.int_arg_regs[2]);
3338 try expectUseBlockers(arg2.*, 0, &.{}, &.{ .rdi, .rsi, .rdx, .rcx });
3339
3340 const arg3 = candidates.getPtr(c3.getResult()) orelse return error.TestFailure;
3341 try expectFixedGpr(arg3.use_positions.items[0].requirement, abi.int_arg_regs[3]);
3342 try expectUseBlockers(arg3.*, 0, &.{}, &.{ .rdi, .rsi, .rdx, .rcx, .r8 });
3343 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3344 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3345 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(arg3.*, fixed_position_index, .rdi));
3346 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(arg3.*, fixed_position_index, .rsi));
3347 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(arg3.*, fixed_position_index, .rdx));
3348 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(arg3.*, fixed_position_index, .rcx));
3349 }
3350
3351 test "collects scalar scratch clobber positions" {
3352 const builtin = @import("../../dialects/root.zig");
3353 const Arith = builtin.ArithDialect;
3354 const Func = builtin.FuncDialect;
3355
3356 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3357 defer ctx.deinit(std.testing.allocator);
3358 try builtin.registerAllDialects(&ctx);
3359
3360 const i64_type = try Arith.getScalarType(&ctx, .i64);
3361 const bool_type = try Arith.getScalarType(&ctx, .bool);
3362 const loc = ir.Location.getUnknown();
3363
3364 const func = try Func.FuncOp.create(&ctx, loc, "scalar_positions", &.{ bool_type, i64_type }, &.{i64_type});
3365 const entry = func.getEntryBlock();
3366
3367 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3368 try entry.addOperation(one.op);
3369 const two = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
3370 try entry.addOperation(two.op);
3371 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(1), one.getResult());
3372 try entry.addOperation(shifted.op);
3373 const selected = try Arith.SelectOp.create(&ctx, loc, func.getArgument(0), shifted.getResult(), two.getResult());
3374 try entry.addOperation(selected.op);
3375 const final_sum = try Arith.AddOp.create(&ctx, loc, func.getArgument(1), selected.getResult());
3376 try entry.addOperation(final_sum.op);
3377 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3378 try entry.addOperation(ret.op);
3379
3380 var candidates: GprCore.Candidates = .empty;
3381 defer candidates.deinit(std.testing.allocator);
3382 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3383 defer fixed_positions.deinit(std.testing.allocator);
3384
3385 var position: u32 = 1;
3386 var order: u32 = 0;
3387 var test_books = TestBooks{};
3388 defer test_books.deinit(std.testing.allocator);
3389 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3390
3391 const one_interval = candidates.getPtr(one.getResult()) orelse return error.TestFailure;
3392 try expectFixedGpr(one_interval.definition.requirement, .rax);
3393 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .def, .rax));
3394 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rax));
3395
3396 const shifted_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
3397 try expectFixedGpr(shifted_interval.definition.requirement, .rax);
3398 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .def, .rax));
3399 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .clobber, .rax));
3400 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 3, .clobber, .rcx));
3401 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .scratch_use, .rcx));
3402
3403 const selected_interval = candidates.getPtr(selected.getResult()) orelse return error.TestFailure;
3404 try expectFixedGpr(selected_interval.definition.requirement, .rdx);
3405 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .def, .rdx));
3406 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 4, .clobber, .rax));
3407 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 4, .clobber, .rcx));
3408 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .clobber, .rdx));
3409 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .scratch_use, .rax));
3410 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .scratch_use, .rcx));
3411 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .scratch_use, .rdx));
3412 }
3413
3414 test "collects unary and shift scratch clobber positions" {
3415 const builtin = @import("../../dialects/root.zig");
3416 const Arith = builtin.ArithDialect;
3417 const Func = builtin.FuncDialect;
3418
3419 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3420 defer ctx.deinit(std.testing.allocator);
3421 try builtin.registerAllDialects(&ctx);
3422
3423 const i64_type = try Arith.getScalarType(&ctx, .i64);
3424 const loc = ir.Location.getUnknown();
3425
3426 const func = try Func.FuncOp.create(&ctx, loc, "unary_shift_positions", &.{ i64_type, i64_type, i64_type }, &.{i64_type});
3427 const entry = func.getEntryBlock();
3428
3429 const negated = try Arith.NegOp.create(&ctx, loc, func.getArgument(0));
3430 try entry.addOperation(negated.op);
3431 const absolute = try Arith.AbsOp.create(&ctx, loc, func.getArgument(0));
3432 try entry.addOperation(absolute.op);
3433 const inverted = try Arith.NotOp.create(&ctx, loc, negated.getResult());
3434 try entry.addOperation(inverted.op);
3435 const shifted = try Arith.ShlOp.create(&ctx, loc, inverted.getResult(), func.getArgument(1));
3436 try entry.addOperation(shifted.op);
3437 const combined = try Arith.AddOp.create(&ctx, loc, shifted.getResult(), absolute.getResult());
3438 try entry.addOperation(combined.op);
3439 const final_sum = try Arith.AddOp.create(&ctx, loc, combined.getResult(), func.getArgument(2));
3440 try entry.addOperation(final_sum.op);
3441 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3442 try entry.addOperation(ret.op);
3443
3444 try std.testing.expect(isEligibleFunction(func.getBody()));
3445
3446 var candidates: GprCore.Candidates = .empty;
3447 defer candidates.deinit(std.testing.allocator);
3448 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3449 defer fixed_positions.deinit(std.testing.allocator);
3450
3451 var position: u32 = 1;
3452 var order: u32 = 0;
3453 var test_books = TestBooks{};
3454 defer test_books.deinit(std.testing.allocator);
3455 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3456
3457 const neg_interval = candidates.getPtr(negated.getResult()) orelse return error.TestFailure;
3458 try expectFixedGpr(neg_interval.definition.requirement, .rax);
3459 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .def, .rax));
3460 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rax));
3461 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 1, .clobber, .rcx));
3462 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rax));
3463
3464 const abs_interval = candidates.getPtr(absolute.getResult()) orelse return error.TestFailure;
3465 try expectFixedGpr(abs_interval.definition.requirement, .rax);
3466 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .def, .rax));
3467 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rax));
3468 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rcx));
3469 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rax));
3470
3471 const not_interval = candidates.getPtr(inverted.getResult()) orelse return error.TestFailure;
3472 try expectFixedGpr(not_interval.definition.requirement, .rax);
3473 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .def, .rax));
3474 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .clobber, .rax));
3475 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 3, .clobber, .rcx));
3476 try std.testing.expect(hasFixedPosition(fixed_positions.items, 3, .scratch_use, .rax));
3477
3478 const shift_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
3479 try expectFixedGpr(shift_interval.definition.requirement, .rax);
3480 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .def, .rax));
3481 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .clobber, .rax));
3482 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 4, .clobber, .rcx));
3483 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .scratch_use, .rax));
3484 try std.testing.expect(hasFixedPosition(fixed_positions.items, 4, .scratch_use, .rcx));
3485
3486 const live_interval = candidates.getPtr(func.getArgument(2)) orelse return error.TestFailure;
3487 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3488 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3489 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rax));
3490 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rcx));
3491
3492 var emitter = TestEmitter{ .allocator = std.testing.allocator };
3493 defer emitter.deinit();
3494 try allocate(&emitter, func.getBody());
3495 _ = try locationFor(&emitter, negated.getResult());
3496 _ = try locationFor(&emitter, absolute.getResult());
3497 _ = try locationFor(&emitter, inverted.getResult());
3498 _ = try locationFor(&emitter, shifted.getResult());
3499 }
3500
3501 test "collects minmax scratch clobber positions" {
3502 const builtin = @import("../../dialects/root.zig");
3503 const Arith = builtin.ArithDialect;
3504 const Func = builtin.FuncDialect;
3505
3506 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3507 defer ctx.deinit(std.testing.allocator);
3508 try builtin.registerAllDialects(&ctx);
3509
3510 const i64_type = try Arith.getScalarType(&ctx, .i64);
3511 const loc = ir.Location.getUnknown();
3512
3513 const func = try Func.FuncOp.create(&ctx, loc, "minmax_positions", &.{ i64_type, i64_type, i64_type }, &.{i64_type});
3514 const entry = func.getEntryBlock();
3515
3516 const maximum = try Arith.MaxOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3517 try entry.addOperation(maximum.op);
3518 const minimum = try Arith.MinOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3519 try entry.addOperation(minimum.op);
3520 const combined = try Arith.AddOp.create(&ctx, loc, maximum.getResult(), minimum.getResult());
3521 try entry.addOperation(combined.op);
3522 const final_sum = try Arith.AddOp.create(&ctx, loc, combined.getResult(), func.getArgument(2));
3523 try entry.addOperation(final_sum.op);
3524 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3525 try entry.addOperation(ret.op);
3526
3527 try std.testing.expect(isEligibleFunction(func.getBody()));
3528
3529 var candidates: GprCore.Candidates = .empty;
3530 defer candidates.deinit(std.testing.allocator);
3531 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3532 defer fixed_positions.deinit(std.testing.allocator);
3533
3534 var position: u32 = 1;
3535 var order: u32 = 0;
3536 var test_books = TestBooks{};
3537 defer test_books.deinit(std.testing.allocator);
3538 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3539
3540 const max_interval = candidates.getPtr(maximum.getResult()) orelse return error.TestFailure;
3541 try expectFixedGpr(max_interval.definition.requirement, .rax);
3542 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .def, .rax));
3543 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rax));
3544 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 1, .clobber, .rcx));
3545 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rax));
3546 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rcx));
3547
3548 const min_interval = candidates.getPtr(minimum.getResult()) orelse return error.TestFailure;
3549 try expectFixedGpr(min_interval.definition.requirement, .rax);
3550 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .def, .rax));
3551 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rax));
3552 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 2, .clobber, .rcx));
3553 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rax));
3554 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rcx));
3555
3556 const live_interval = candidates.getPtr(func.getArgument(2)) orelse return error.TestFailure;
3557 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3558 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3559 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rax));
3560 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rcx));
3561
3562 var emitter = TestEmitter{ .allocator = std.testing.allocator };
3563 defer emitter.deinit();
3564 try allocate(&emitter, func.getBody());
3565 _ = try locationFor(&emitter, maximum.getResult());
3566 _ = try locationFor(&emitter, minimum.getResult());
3567 }
3568
3569 test "collects division scratch clobber positions" {
3570 const builtin = @import("../../dialects/root.zig");
3571 const Arith = builtin.ArithDialect;
3572 const Func = builtin.FuncDialect;
3573
3574 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3575 defer ctx.deinit(std.testing.allocator);
3576 try builtin.registerAllDialects(&ctx);
3577
3578 const i64_type = try Arith.getScalarType(&ctx, .i64);
3579 const loc = ir.Location.getUnknown();
3580
3581 const func = try Func.FuncOp.create(&ctx, loc, "division_positions", &.{ i64_type, i64_type, i64_type }, &.{i64_type});
3582 const entry = func.getEntryBlock();
3583
3584 const quotient = try Arith.DivOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3585 try entry.addOperation(quotient.op);
3586 const remainder = try Arith.RemOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
3587 try entry.addOperation(remainder.op);
3588 const combined = try Arith.AddOp.create(&ctx, loc, quotient.getResult(), remainder.getResult());
3589 try entry.addOperation(combined.op);
3590 const final_sum = try Arith.AddOp.create(&ctx, loc, combined.getResult(), func.getArgument(2));
3591 try entry.addOperation(final_sum.op);
3592 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3593 try entry.addOperation(ret.op);
3594
3595 var candidates: GprCore.Candidates = .empty;
3596 defer candidates.deinit(std.testing.allocator);
3597 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3598 defer fixed_positions.deinit(std.testing.allocator);
3599
3600 var position: u32 = 1;
3601 var order: u32 = 0;
3602 var test_books = TestBooks{};
3603 defer test_books.deinit(std.testing.allocator);
3604 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3605
3606 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3607 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3608 const quotient_interval = candidates.getPtr(quotient.getResult()) orelse return error.TestFailure;
3609 try expectFixedGpr(quotient_interval.definition.requirement, .rax);
3610 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .def, .rax));
3611 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rax));
3612 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .clobber, .rdx));
3613 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 1, .clobber, .rcx));
3614 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rax));
3615 try std.testing.expect(hasFixedPosition(fixed_positions.items, 1, .scratch_use, .rcx));
3616 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(quotient_interval.*, fixed_position_index, .rdx));
3617
3618 const remainder_interval = candidates.getPtr(remainder.getResult()) orelse return error.TestFailure;
3619 try expectFixedGpr(remainder_interval.definition.requirement, .rdx);
3620 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .def, .rdx));
3621 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rax));
3622 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .clobber, .rdx));
3623 try std.testing.expect(!hasFixedPosition(fixed_positions.items, 2, .clobber, .rcx));
3624 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rax));
3625 try std.testing.expect(hasFixedPosition(fixed_positions.items, 2, .scratch_use, .rcx));
3626 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(remainder_interval.*, fixed_position_index, .rax));
3627
3628 const live_interval = candidates.getPtr(func.getArgument(2)) orelse return error.TestFailure;
3629 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rax));
3630 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_interval.*, fixed_position_index, .rdx));
3631
3632 var emitter = TestEmitter{ .allocator = std.testing.allocator };
3633 defer emitter.deinit();
3634 try allocate(&emitter, func.getBody());
3635 _ = try locationFor(&emitter, quotient.getResult());
3636 _ = try locationFor(&emitter, remainder.getResult());
3637 }
3638
3639 test "scalar scratch positions reject live-through intervals" {
3640 const builtin = @import("../../dialects/root.zig");
3641 const Arith = builtin.ArithDialect;
3642 const Func = builtin.FuncDialect;
3643
3644 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3645 defer ctx.deinit(std.testing.allocator);
3646 try builtin.registerAllDialects(&ctx);
3647
3648 const i64_type = try Arith.getScalarType(&ctx, .i64);
3649 const bool_type = try Arith.getScalarType(&ctx, .bool);
3650 const loc = ir.Location.getUnknown();
3651
3652 const func = try Func.FuncOp.create(&ctx, loc, "scratch_conflicts", &.{ bool_type, i64_type }, &.{i64_type});
3653 const entry = func.getEntryBlock();
3654
3655 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3656 try entry.addOperation(one.op);
3657 const two = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 2);
3658 try entry.addOperation(two.op);
3659 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(1), one.getResult());
3660 try entry.addOperation(shifted.op);
3661 const selected = try Arith.SelectOp.create(&ctx, loc, func.getArgument(0), shifted.getResult(), two.getResult());
3662 try entry.addOperation(selected.op);
3663 const final_sum = try Arith.AddOp.create(&ctx, loc, func.getArgument(1), selected.getResult());
3664 try entry.addOperation(final_sum.op);
3665 const ret = try Func.ReturnOp.create(&ctx, loc, &.{final_sum.getResult()});
3666 try entry.addOperation(ret.op);
3667
3668 var candidates: GprCore.Candidates = .empty;
3669 defer candidates.deinit(std.testing.allocator);
3670 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3671 defer fixed_positions.deinit(std.testing.allocator);
3672
3673 var position: u32 = 1;
3674 var order: u32 = 0;
3675 var test_books = TestBooks{};
3676 defer test_books.deinit(std.testing.allocator);
3677 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3678
3679 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3680 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3681 const live_arg = candidates.getPtr(func.getArgument(1)) orelse return error.TestFailure;
3682 try std.testing.expectEqual(@as(u32, 0), live_arg.start());
3683 try std.testing.expectEqual(@as(u32, 5), live_arg.end());
3684 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_arg.*, fixed_position_index, .rax));
3685 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_arg.*, fixed_position_index, .rcx));
3686 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(live_arg.*, fixed_position_index, .rdx));
3687 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(live_arg.*, fixed_position_index, .rbx));
3688
3689 const shifted_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
3690 try expectFixedGpr(shifted_interval.definition.requirement, .rax);
3691 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .rax));
3692 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .rbx));
3693
3694 const selected_interval = candidates.getPtr(selected.getResult()) orelse return error.TestFailure;
3695 try expectFixedGpr(selected_interval.definition.requirement, .rdx);
3696 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(selected_interval.*, fixed_position_index, .rdx));
3697 }
3698
3699 test "fixed positions reject registers for live-through intervals" {
3700 const builtin = @import("../../dialects/root.zig");
3701 const Arith = builtin.ArithDialect;
3702 const Func = builtin.FuncDialect;
3703
3704 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3705 defer ctx.deinit(std.testing.allocator);
3706 try builtin.registerAllDialects(&ctx);
3707
3708 const i64_type = try Arith.getScalarType(&ctx, .i64);
3709 const loc = ir.Location.getUnknown();
3710
3711 const func = try Func.FuncOp.create(&ctx, loc, "fixed_conflicts", &.{i64_type}, &.{i64_type});
3712 const entry = func.getEntryBlock();
3713
3714 const one = try Arith.ConstantOp.createInt(&ctx, loc, i64_type, 1);
3715 try entry.addOperation(one.op);
3716 const shifted = try Arith.AddOp.create(&ctx, loc, func.getArgument(0), one.getResult());
3717 try entry.addOperation(shifted.op);
3718 const call = try Func.CallOp.create(&ctx, loc, "choir_external_add1", &.{shifted.getResult()}, &.{i64_type});
3719 try entry.addOperation(call.op);
3720 const call_result = call.getResult(0) orelse return error.TestFailure;
3721 const after_call = try Arith.AddOp.create(&ctx, loc, shifted.getResult(), call_result);
3722 try entry.addOperation(after_call.op);
3723 const ret = try Func.ReturnOp.create(&ctx, loc, &.{after_call.getResult()});
3724 try entry.addOperation(ret.op);
3725
3726 var candidates: GprCore.Candidates = .empty;
3727 defer candidates.deinit(std.testing.allocator);
3728 var fixed_positions: std.ArrayListUnmanaged(GprCore.FixedPosition) = .empty;
3729 defer fixed_positions.deinit(std.testing.allocator);
3730
3731 var position: u32 = 1;
3732 var order: u32 = 0;
3733 var test_books = TestBooks{};
3734 defer test_books.deinit(std.testing.allocator);
3735 try collectBlockCandidates(test_books.books(&candidates, &fixed_positions), null, std.testing.allocator, entry, &position, &order);
3736
3737 var fixed_position_index_storage: GprCore.FixedPositionIndex.Storage = undefined;
3738 const fixed_position_index = GprCore.FixedPositionIndex.init(fixed_positions.items, &fixed_position_index_storage);
3739 const shifted_interval = candidates.getPtr(shifted.getResult()) orelse return error.TestFailure;
3740 try std.testing.expectEqual(@as(u32, 2), shifted_interval.start());
3741 try std.testing.expectEqual(@as(u32, 4), shifted_interval.end());
3742 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, abi.int_arg_regs[0]));
3743 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, abi.int_return_reg));
3744 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .r8));
3745 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .r11));
3746 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .rbx));
3747 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(shifted_interval.*, fixed_position_index, .r12));
3748
3749 const call_interval = candidates.getPtr(call_result) orelse return error.TestFailure;
3750 try expectFixedGpr(call_interval.definition.requirement, abi.int_return_reg);
3751 try std.testing.expect(GprCore.candidateConflictsWithRegisterConstraints(call_interval.*, fixed_position_index, abi.int_return_reg));
3752 try std.testing.expect(!GprCore.candidateConflictsWithRegisterConstraints(call_interval.*, fixed_position_index, .rbx));
3753 }
3754
3755 test "an ordered access refuses a function that a plain access admits" {
3756 const builtin = @import("../../dialects/root.zig");
3757 const Arith = builtin.ArithDialect;
3758 const Func = builtin.FuncDialect;
3759 const Memref = builtin.MemrefDialect;
3760
3761 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3762 defer ctx.deinit(std.testing.allocator);
3763 try builtin.registerAllDialects(&ctx);
3764
3765 const i64_type = try Arith.getScalarType(&ctx, .i64);
3766 const index_type = try Arith.getScalarType(&ctx, .index);
3767 const buffer_type = try Memref.getMemrefType1D(&ctx, 4, i64_type, .host);
3768 const loc = ir.Location.getUnknown();
3769
3770 const plain = try Func.FuncOp.create(&ctx, loc, "plain", &.{ buffer_type, index_type }, &.{i64_type});
3771 const plain_entry = plain.getEntryBlock();
3772 const plain_load = try Memref.LoadOp.create(&ctx, loc, plain.getArgument(0), plain.getArgument(1), i64_type);
3773 try plain_entry.addOperation(plain_load.op);
3774 const plain_return = try Func.ReturnOp.create(&ctx, loc, &.{plain_load.getResult()});
3775 try plain_entry.addOperation(plain_return.op);
3776
3777 const ordered = try Func.FuncOp.create(&ctx, loc, "ordered", &.{ buffer_type, index_type }, &.{i64_type});
3778 const ordered_entry = ordered.getEntryBlock();
3779 const ordered_load = try Memref.AtomicLoadOp.create(
3780 &ctx,
3781 loc,
3782 ordered.getArgument(0),
3783 ordered.getArgument(1),
3784 i64_type,
3785 .acquire,
3786 );
3787 try ordered_entry.addOperation(ordered_load.op);
3788 const ordered_return = try Func.ReturnOp.create(&ctx, loc, &.{ordered_load.getResult()});
3789 try ordered_entry.addOperation(ordered_return.op);
3790
3791 try std.testing.expect(!holdsOrderedEffect(plain_load.op));
3792 try std.testing.expect(holdsOrderedEffect(ordered_load.op));
3793
3794 const plain_region = plain.op.getRegion(0) orelse return error.TestFailure;
3795 const ordered_region = ordered.op.getRegion(0) orelse return error.TestFailure;
3796 try std.testing.expect(isEligibleFunction(plain_region));
3797 try std.testing.expect(!isEligibleFunction(ordered_region));
3798 }
3799
3800 test "the ordered effect probe conservatively refuses facts past its horizon" {
3801 const effects = ir.interfaces.effects;
3802 const plain = effects.Fact{ .event = .{ .kind = .read } };
3803 const facts: [ordered_probe_facts + 1]effects.Fact = @splat(plain);
3804 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
3805 defer ctx.deinit(std.testing.allocator);
3806 try ctx.allowUnregistered();
3807 try ctx.registerOperationInterface("test.at_horizon", effects.EffectOpInterface.entryFor(.{
3808 .complete = true,
3809 .facts = facts[0..ordered_probe_facts],
3810 }));
3811 try ctx.registerOperationInterface("test.past_horizon", effects.EffectOpInterface.entryFor(.{
3812 .complete = true,
3813 .facts = &facts,
3814 }));
3815 const at_horizon = try ctx.createOperation(ir.Operation.State.init("test.at_horizon", .unknown));
3816 const past_horizon = try ctx.createOperation(ir.Operation.State.init("test.past_horizon", .unknown));
3817 try std.testing.expect(!holdsOrderedEffect(at_horizon));
3818 try std.testing.expect(holdsOrderedEffect(past_horizon));
3819 }