lib/choir/src/backends/x64/emit.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../core/root.zig");
3 const dialects = @import("../../dialects/root.zig");
4 const machine = @import("../root.zig").machine_code;
5 const cast = @import("cast.zig");
6 const scalar = @import("scalar.zig");
7 const memory = @import("memory.zig");
8 const encoding = @import("encoding.zig");
9 const registers = @import("registers/root.zig");
10 const abi = @import("abi.zig");
11 const call_plan = @import("calls.zig");
12 const debug_info = @import("../root.zig").debug_info;
13 const labels = @import("labels.zig");
14 const slot_layout = @import("slots.zig");
15 const vector = @import("vector.zig");
16 const regalloc = @import("regalloc.zig");
17 const moves = @import("moves.zig");
18 const effects = @import("../../passes/effects.zig");
19
20 const arith = dialects.arith;
21 const memref = dialects.memref;
22 const scf = dialects.scf;
23 const func_dialect = dialects.func;
24 const builtin = dialects.builtin;
25
26 const ArithDialect = arith.ArithDialect;
27 const MemrefDialect = memref.MemrefDialect;
28 const ScfDialect = scf.ScfDialect;
29 const FuncDialect = func_dialect.FuncDialect;
30 const BuiltinDialect = builtin.BuiltinDialect;
31
32 const GPR = registers.GPR;
33 const XMM = registers.XMM;
34 const Mem = encoding.Mem;
35 const Condition = encoding.Condition;
36
37 /// The registers a `func.syscall` operand reaches, in operand order: the number first, then the
38 /// kernel's arguments. The allocator owns the convention and this is its operand-order reading.
39 const syscall_operand_regs = [_]GPR{regalloc.syscall_number_gpr} ++ regalloc.syscall_argument_gprs;
40
41 /// Largest number of values one `scf.while` carries through this emitter: its
42 /// operands, its before and after block arguments, its results and the
43 /// arguments its condition hands back are all this many or fewer. A while that
44 /// carries more is refused with `error.TooManyWhileValues` before its blocks
45 /// are walked.
46 ///
47 /// A BOUND AND NOT A CAPACITY. This is not memory a caller buys and no limit
48 /// raises it, because the buffer it sizes lives on the host stack for the
49 /// length of one while. The side a program falls on is a property of the
50 /// program alone. A consumer that refuses a wider program in its own words
51 /// reads this figure here rather than copying it, so the two cannot drift.
52 pub const max_while_carried_values: usize = 16;
53
54 pub const CallRelocation = call_plan.CallRelocation;
55 const Slot = slot_layout.Slot;
56 const VectorSlot = slot_layout.VectorSlot;
57 const SretInfo = slot_layout.SretInfo;
58 const AllocationKind = slot_layout.AllocationKind;
59 const ArgSource = call_plan.ArgSource;
60 const ExternArg = call_plan.ExternArg;
61 const ExternResult = call_plan.ExternResult;
62 const TypeInfo = slot_layout.TypeInfo;
63 const IntExtension = slot_layout.IntExtension;
64 const Label = labels.Label;
65
66 /// What a type contributes to its slot, before the slot has a place.
67 ///
68 /// Width and form travel together from `slotShapeFromName` to the one site
69 /// that reserves a slot, so that a reader cannot take the width and leave the
70 /// form behind, which once made a reload interpret an unsigned byte as signed.
71 const SlotShape = struct {
72 width: u8,
73 ext: IntExtension,
74 };
75
76 const MoveScratchSlots = struct {
77 cycle: Slot,
78 save: Slot,
79 };
80
81 const StackMoveScratch = struct {
82 slots: MoveScratchSlots,
83 memory_reg: GPR,
84 };
85
86 const MoveScratch = union(enum) {
87 reg: GPR,
88 stack: StackMoveScratch,
89 };
90
91 const BlockResult = enum {
92 fell_through,
93 yielded,
94 returned,
95 conditioned,
96 };
97
98 const IfYield = struct {
99 op: *ir.Operation,
100 merge_label: *Label,
101 };
102
103 const ForYield = struct {
104 body_block: *ir.Block,
105 iv: *ir.Value,
106 step: *ir.Value,
107 entry_position: u32,
108 header_label: *Label,
109 };
110
111 const WhileCondition = struct {
112 value: *?*ir.Value,
113 args: []*ir.Value,
114 arg_count: *usize,
115 position: *u32,
116 };
117
118 const WhileYield = struct {
119 before_block: *ir.Block,
120 header_label: *Label,
121 };
122
123 const BlockTerminator = union(enum) {
124 function_return,
125 if_yield: IfYield,
126 for_yield: ForYield,
127 while_condition: WhileCondition,
128 while_yield: WhileYield,
129 };
130
131 const EmitError = error{
132 OutOfMemory,
133 CapacityOverflow,
134 NoFunctionBody,
135 NoEntryBlock,
136 UnsupportedType,
137 MissingSlot,
138 MissingOperand,
139 MissingResult,
140 MissingPredicate,
141 MissingIndex,
142 IndexOutOfBounds,
143 VectorArityMismatch,
144 MissingCallee,
145 MissingInductionVariable,
146 MissingCondition,
147 MissingYield,
148 MissingOrdering,
149 /// An ordered access was reached in a function whose values are not all in frame slots.
150 /// `memory.requireFrameSlotsOnly` raises it and `regalloc.holdsOrderedEffect` is what keeps
151 /// it unreachable, by refusing to allocate such a function at all.
152 OrderedAccessWithAllocatedValues,
153 InvalidWhileArity,
154 UnexpectedOperationAfterCondition,
155 UnexpectedYield,
156 TooManyArguments,
157 TooManyResults,
158 TooManyWhileValues,
159 ResultCountMismatch,
160 InvalidConstant,
161 InvalidDataSymbol,
162 ConflictingDataSymbol,
163 InvalidAllocation,
164 MemrefTypeMissingParams,
165 InvalidMemrefType,
166 DynamicMemref,
167 UnsupportedMemrefAddressSpace,
168 UnsupportedDeallocTarget,
169 UnsupportedOperation,
170 InvalidParallelMove,
171 NoScratchRegister,
172 };
173
174 pub const Emitter = struct {
175 allocator: std.mem.Allocator,
176 code: std.ArrayListUnmanaged(u8),
177 call_relocations: std.ArrayListUnmanaged(CallRelocation),
178 data_symbols: machine.DataSymbolSet,
179 data_relocations: std.ArrayListUnmanaged(machine.DataRelocation),
180 omitted_ops: std.AutoHashMapUnmanaged(*ir.Operation, void),
181 flag_conditions: std.AutoHashMapUnmanaged(*ir.Value, Condition),
182 slot_map: std.AutoHashMapUnmanaged(*ir.Value, Slot),
183 vector_slot_map: std.AutoHashMapUnmanaged(*ir.Value, VectorSlot),
184 alloca_payload_slots: std.AutoHashMapUnmanaged(*ir.Value, Slot),
185 slot_count: usize,
186 allocation_kinds: std.AutoHashMapUnmanaged(*ir.Value, AllocationKind),
187 frame_layout: abi.FrameLayout,
188 saw_return: bool,
189 sret_info: ?SretInfo,
190 sret_slot: ?Slot,
191 result_count: usize,
192 line_table: debug_info.LineTableBuilder,
193 value_locations: std.AutoHashMapUnmanaged(*ir.Value, GPR),
194 value_location_ranges: std.ArrayListUnmanaged(regalloc.ValueLocationRange),
195 value_location_index: regalloc.ValueLocationIndex,
196 xmm_locations: std.AutoHashMapUnmanaged(*ir.Value, XMM),
197 xmm_location_ranges: std.ArrayListUnmanaged(regalloc.XmmValueLocationRange),
198 xmm_location_index: regalloc.XmmValueLocationIndex,
199 operation_positions: std.AutoHashMapUnmanaged(*ir.Operation, u32),
200 allocation_position: u32,
201 move_scratch_slots: ?MoveScratchSlots,
202 reserved_callee_saved: usize,
203 used_callee_saved_regs: [registers.callee_saved_gprs.len]GPR,
204 /// The innermost operation whose emission failed in the current function, or `null`.
205 failed_operation: ?*ir.Operation,
206
207 pub fn init(allocator: std.mem.Allocator) Emitter {
208 return .{
209 .allocator = allocator,
210 .code = .empty,
211 .call_relocations = .empty,
212 .data_symbols = .{},
213 .data_relocations = .empty,
214 .omitted_ops = .{},
215 .flag_conditions = .{},
216 .slot_map = .{},
217 .vector_slot_map = .{},
218 .alloca_payload_slots = .{},
219 .slot_count = 0,
220 .allocation_kinds = .empty,
221 .frame_layout = abi.computeFrameLayout(0, &.{}, true),
222 .saw_return = false,
223 .sret_info = null,
224 .sret_slot = null,
225 .result_count = 0,
226 .line_table = debug_info.LineTableBuilder.init(allocator),
227 .value_locations = .empty,
228 .value_location_ranges = .empty,
229 .value_location_index = .{},
230 .xmm_locations = .empty,
231 .xmm_location_ranges = .empty,
232 .xmm_location_index = .{},
233 .operation_positions = .empty,
234 .allocation_position = 0,
235 .move_scratch_slots = null,
236 .reserved_callee_saved = 0,
237 .used_callee_saved_regs = undefined,
238 .failed_operation = null,
239 };
240 }
241
242 pub fn deinit(self: *Emitter) void {
243 self.code.deinit(self.allocator);
244 self.call_relocations.deinit(self.allocator);
245 self.data_symbols.deinit(self.allocator);
246 self.data_relocations.deinit(self.allocator);
247 self.omitted_ops.deinit(self.allocator);
248 self.flag_conditions.deinit(self.allocator);
249 self.slot_map.deinit(self.allocator);
250 self.vector_slot_map.deinit(self.allocator);
251 self.alloca_payload_slots.deinit(self.allocator);
252 self.allocation_kinds.deinit(self.allocator);
253 self.line_table.deinit();
254 self.value_locations.deinit(self.allocator);
255 self.value_location_ranges.deinit(self.allocator);
256 self.value_location_index.deinit(self.allocator);
257 self.xmm_locations.deinit(self.allocator);
258 self.xmm_location_ranges.deinit(self.allocator);
259 self.xmm_location_index.deinit(self.allocator);
260 self.operation_positions.deinit(self.allocator);
261 }
262
263 pub fn getCode(self: *const Emitter) []const u8 {
264 return self.code.items;
265 }
266
267 pub fn emitFunction(self: *Emitter, func: *ir.Operation) EmitError!void {
268 self.resetForFunction();
269
270 const region = func.getRegion(0) orelse return error.NoFunctionBody;
271 const entry = region.getEntryBlock() orelse return error.NoEntryBlock;
272 if (func.results.items.len > abi.max_result_count) return error.TooManyResults;
273 self.result_count = func.results.items.len;
274
275 try self.markOmittedOps(region);
276 try self.markFlagConditions(region);
277 try regalloc.allocate(self, region);
278 try self.collectSlotsInRegion(region);
279 try self.reserveResultAddress(func);
280
281 if (self.value_locations.count() != 0 or self.value_location_ranges.items.len != 0) {
282 self.reserveMoveScratchSlots();
283 }
284
285 const local_bytes: u32 = @intCast(self.slot_count * abi.stack_slot_size);
286 self.frame_layout = abi.computeFrameLayout(local_bytes, self.used_callee_saved_regs[0..self.reserved_callee_saved], true);
287
288 try self.frame_layout.emitPrologue(self.allocator, &self.code);
289 try self.emitArgumentSpills(entry);
290
291 _ = try self.emitBlockOps(entry, .function_return);
292
293 if (!self.saw_return) {
294 try self.emitEpilogue();
295 }
296 }
297
298 /// Reserves the slot holding a hidden result address for vector and record returns.
299 /// Several results carry scalars only; a vector result returns alone.
300 fn reserveResultAddress(self: *Emitter, func: *ir.Operation) EmitError!void {
301 const results = func.results.items;
302 std.debug.assert(results.len <= abi.max_result_count);
303 std.debug.assert(self.sret_info == null);
304 if (results.len == 1) {
305 if (try self.vectorTypeInfoFromType(results[0].type)) |vec_info| {
306 self.sret_info = .{ .vector = vec_info };
307 self.sret_slot = self.reserveSlot(64, .unsigned);
308 }
309 return;
310 }
311 for (results) |result| {
312 if (try self.vectorTypeInfoFromType(result.type) != null) return error.UnsupportedType;
313 }
314 if (!abi.returnsThroughRecord(results.len)) return;
315 self.sret_info = .{ .record = results.len };
316 self.sret_slot = self.reserveSlot(64, .unsigned);
317 }
318
319 pub fn discardFunctionState(self: *Emitter) void {
320 self.resetForFunction();
321 }
322
323 fn resetForFunction(self: *Emitter) void {
324 self.code.clearRetainingCapacity();
325 self.call_relocations.clearRetainingCapacity();
326 self.data_symbols.clearRetainingCapacity();
327 self.data_relocations.clearRetainingCapacity();
328 self.slot_map.clearRetainingCapacity();
329 self.vector_slot_map.clearRetainingCapacity();
330 self.alloca_payload_slots.clearRetainingCapacity();
331 self.slot_count = 0;
332 self.allocation_kinds.clearRetainingCapacity();
333 self.saw_return = false;
334 self.sret_info = null;
335 self.sret_slot = null;
336 self.result_count = 0;
337 self.line_table.reset();
338 self.value_locations.clearRetainingCapacity();
339 self.value_location_ranges.clearRetainingCapacity();
340 self.value_location_index.clearRetainingCapacity();
341 self.xmm_locations.clearRetainingCapacity();
342 self.xmm_location_ranges.clearRetainingCapacity();
343 self.xmm_location_index.clearRetainingCapacity();
344 self.operation_positions.clearRetainingCapacity();
345 self.omitted_ops.clearRetainingCapacity();
346 self.flag_conditions.clearRetainingCapacity();
347 self.allocation_position = 0;
348 self.move_scratch_slots = null;
349 self.reserved_callee_saved = 0;
350 self.failed_operation = null;
351 }
352
353 fn recordLocation(self: *Emitter, op: *ir.Operation) EmitError!void {
354 const offset: u32 = @intCast(self.code.items.len);
355 try self.line_table.record(offset, op.getLoc(), op.name.name);
356 }
357
358 fn enterOperationPosition(self: *Emitter, op: *ir.Operation) EmitError!void {
359 if (self.operation_positions.get(op)) |position| {
360 self.allocation_position = position;
361 }
362 try self.emitRangeEndSpills();
363 try self.emitRangeStartReloads();
364 try self.emitXmmRangeEndSpills();
365 try self.emitXmmRangeStartReloads();
366 }
367
368 fn beginOperation(self: *Emitter, op: *ir.Operation) EmitError!void {
369 try self.enterOperationPosition(op);
370 try self.recordLocation(op);
371 }
372
373 fn plannedValueLocationAtPoint(self: *const Emitter, value: *ir.Value, point: regalloc.PositionPoint) ?GPR {
374 return self.value_location_index.valueLocationAtPoint(self.value_location_ranges.items, value, point);
375 }
376
377 fn plannedValueLocationAt(self: *const Emitter, value: *ir.Value, position: u32) ?GPR {
378 return self.plannedValueLocationAtPoint(value, .{ .position = position, .phase = .source });
379 }
380
381 /// Returns the position where allocation defines the results of an operation with regions.
382 /// Results follow every nested position, so they sit just before the next operation.
383 fn mergePosition(self: *const Emitter, op: *ir.Operation) ?u32 {
384 std.debug.assert(op.regions.items.len != 0);
385 const next = op.next_op orelse return null;
386 const next_position = self.operation_positions.get(next) orelse return null;
387 const op_position = self.operation_positions.get(op) orelse return null;
388 std.debug.assert(next_position > op_position + 1);
389 return next_position - 1;
390 }
391
392 /// A linear allocation order visits both arms, but execution visits only one. Materialize
393 /// every incoming register value before the branch so a spill or reload in either arm has
394 /// a valid slot, then restore the register homes expected by the common successor.
395 fn saveIfIncomingValues(self: *Emitter, op: *ir.Operation) EmitError!void {
396 const branch_position = self.operation_positions.get(op) orelse return;
397 const point = regalloc.PositionPoint.source(branch_position);
398 for (self.value_location_ranges.items) |range| {
399 if (!range.containsPoint(point)) continue;
400 if (!self.valueDefinedBefore(range.value, branch_position)) continue;
401 const slot = self.slotForOptional(range.value) orelse continue;
402 try self.storeSlot(slot, range.reg);
403 }
404 for (self.xmm_location_ranges.items) |range| {
405 if (!range.containsPoint(point)) continue;
406 if (!self.valueDefinedBefore(range.value, branch_position)) continue;
407 if (self.vector_slot_map.get(range.value)) |slot| {
408 try vector.emitPackedStore(self, slot, range.reg);
409 } else {
410 try self.storeSlotXmm(try self.slotFor(range.value), range.reg);
411 }
412 }
413 }
414
415 /// Entry reloads wait for enterOperationPosition to spill the old register occupant.
416 fn restoreIfValuesAt(self: *Emitter, op: *ir.Operation, position: u32) EmitError!void {
417 const branch_position = self.operation_positions.get(op) orelse return;
418 const point = regalloc.PositionPoint.source(position);
419 for (self.value_location_ranges.items) |range| {
420 if (!range.containsPoint(point)) continue;
421 if (range.entry == .reload and range.start == position) continue;
422 if (!self.valueDefinedBefore(range.value, branch_position)) continue;
423 const slot = self.slotForOptional(range.value) orelse continue;
424 try self.loadSlot(slot, range.reg);
425 }
426 for (self.xmm_location_ranges.items) |range| {
427 if (!range.containsPoint(point)) continue;
428 if (range.entry == .reload and range.start == position) continue;
429 if (!self.valueDefinedBefore(range.value, branch_position)) continue;
430 if (self.vector_slot_map.get(range.value)) |slot| {
431 try vector.emitPackedLoad(self, slot, range.reg);
432 } else {
433 try self.loadSlotXmm(try self.slotFor(range.value), range.reg);
434 }
435 }
436 }
437
438 fn restoreIfArmValues(self: *Emitter, op: *ir.Operation, block: *ir.Block) EmitError!void {
439 const first: *ir.Operation = @ptrCast(@alignCast(block.operations.head orelse return));
440 const position = self.operation_positions.get(first) orelse return;
441 try self.restoreIfValuesAt(op, position);
442 }
443
444 fn restoreIfOutgoingValues(self: *Emitter, op: *ir.Operation) EmitError!void {
445 const merge_position = self.mergePosition(op) orelse return;
446 try self.restoreIfValuesAt(op, merge_position + 1);
447 }
448
449 fn valueDefinedBefore(self: *const Emitter, value: *ir.Value, position: u32) bool {
450 const defining = value.getDefiningOp() orelse return true;
451 const operation: *ir.Operation = @ptrCast(@alignCast(defining));
452 const definition_position = self.operation_positions.get(operation) orelse return false;
453 return definition_position < position;
454 }
455
456 /// Moves allocation to the merge position of a region operation and spills ranges ending
457 /// there. A result whose first range reloads later then resolves to its slot, not a register.
458 fn enterMergePosition(self: *Emitter, op: *ir.Operation) EmitError!void {
459 if (op.results.items.len == 0) return;
460 const merge_position = self.mergePosition(op) orelse return;
461 self.allocation_position = merge_position;
462 try self.emitRangeEndSpills();
463 try self.emitXmmRangeEndSpills();
464 }
465
466 fn plannedValueStart(self: *const Emitter, value: *ir.Value) ?u32 {
467 if (valueIsFloatScalar(value)) {
468 return self.xmm_location_index.valueLocationStart(self.xmm_location_ranges.items, value);
469 }
470 return self.value_location_index.valueLocationStart(self.value_location_ranges.items, value);
471 }
472
473 fn plannedValueLocation(self: *const Emitter, value: *ir.Value) ?GPR {
474 return self.plannedValueLocationAt(value, self.allocation_position);
475 }
476
477 fn plannedValueLocationForPhase(self: *const Emitter, value: *ir.Value, phase: regalloc.PositionPhase) ?GPR {
478 return self.plannedValueLocationAtPoint(value, .{ .position = self.allocation_position, .phase = phase });
479 }
480
481 fn hasPlannedValueLocation(self: *const Emitter, value: *ir.Value) bool {
482 return self.value_location_index.valueHasLocationRange(value);
483 }
484
485 fn canUsePlannedValueLocation(value: *ir.Value) bool {
486 return switch (value.kind) {
487 .op_result => true,
488 .block_argument => true,
489 };
490 }
491
492 fn registerHomeAtPoint(self: *const Emitter, value: *ir.Value, point: regalloc.PositionPoint) ?GPR {
493 if (canUsePlannedValueLocation(value)) {
494 if (self.plannedValueLocationAtPoint(value, point)) |home| return home;
495 if (self.hasPlannedValueLocation(value)) return null;
496 }
497 return self.value_locations.get(value);
498 }
499
500 fn registerHomeAt(self: *const Emitter, value: *ir.Value, position: u32) ?GPR {
501 return self.registerHomeAtPoint(value, .{ .position = position, .phase = .source });
502 }
503
504 pub fn registerHome(self: *const Emitter, value: *ir.Value) ?GPR {
505 return self.registerHomeAt(value, self.allocation_position);
506 }
507
508 pub fn registerHomeForPhase(self: *const Emitter, value: *ir.Value, phase: regalloc.PositionPhase) ?GPR {
509 return self.registerHomeAtPoint(value, .{ .position = self.allocation_position, .phase = phase });
510 }
511
512 fn valueIsFloatScalar(value: *const ir.Value) bool {
513 const name = value.type.getDialectTypeName() orelse return false;
514 return std.mem.eql(u8, name, "arith.f32") or std.mem.eql(u8, name, "arith.f64");
515 }
516
517 fn plannedXmmLocationAtPoint(self: *const Emitter, value: *ir.Value, point: regalloc.PositionPoint) ?XMM {
518 return self.xmm_location_index.valueLocationAtPoint(self.xmm_location_ranges.items, value, point);
519 }
520
521 fn hasPlannedXmmLocation(self: *const Emitter, value: *ir.Value) bool {
522 return self.xmm_location_index.valueHasLocationRange(value);
523 }
524
525 fn xmmHomeAtPoint(self: *const Emitter, value: *ir.Value, point: regalloc.PositionPoint) ?XMM {
526 if (canUsePlannedValueLocation(value)) {
527 if (self.plannedXmmLocationAtPoint(value, point)) |home| return home;
528 if (self.hasPlannedXmmLocation(value)) return null;
529 }
530 return self.xmm_locations.get(value);
531 }
532
533 pub fn xmmHome(self: *const Emitter, value: *ir.Value) ?XMM {
534 return self.xmmHomeAtPoint(value, .{ .position = self.allocation_position, .phase = .source });
535 }
536
537 pub fn xmmHomeForPhase(self: *const Emitter, value: *ir.Value, phase: regalloc.PositionPhase) ?XMM {
538 return self.xmmHomeAtPoint(value, .{ .position = self.allocation_position, .phase = phase });
539 }
540
541 fn emitRangeEndSpills(self: *Emitter) EmitError!void {
542 var iterator = self.value_location_index.rangesEndingAt(self.allocation_position);
543 while (iterator.next()) |range_index| {
544 const range = self.value_location_ranges.items[range_index];
545 if (range.exit != .spill) continue;
546 if (!canUsePlannedValueLocation(range.value)) continue;
547 const slot = self.slotForOptional(range.value) orelse continue;
548 try self.storeSlot(slot, range.reg);
549 }
550 }
551
552 fn emitRangeStartReloads(self: *Emitter) EmitError!void {
553 var iterator = self.value_location_index.rangesStartingAt(self.allocation_position);
554 while (iterator.next()) |range_index| {
555 const range = self.value_location_ranges.items[range_index];
556 if (range.entry != .reload) continue;
557 if (!canUsePlannedValueLocation(range.value)) continue;
558 const slot = self.slotForOptional(range.value) orelse continue;
559 try self.loadSlot(slot, range.reg);
560 }
561 }
562
563 fn emitXmmRangeEndSpills(self: *Emitter) EmitError!void {
564 var iterator = self.xmm_location_index.rangesEndingAt(self.allocation_position);
565 while (iterator.next()) |range_index| {
566 const range = self.xmm_location_ranges.items[range_index];
567 if (range.exit != .spill) continue;
568 if (!canUsePlannedValueLocation(range.value)) continue;
569 if (self.vector_slot_map.get(range.value)) |vslot| {
570 try vector.emitPackedStore(self, vslot, range.reg);
571 } else {
572 try self.storeSlotXmm(try self.slotFor(range.value), range.reg);
573 }
574 }
575 }
576
577 fn emitXmmRangeStartReloads(self: *Emitter) EmitError!void {
578 var iterator = self.xmm_location_index.rangesStartingAt(self.allocation_position);
579 while (iterator.next()) |range_index| {
580 const range = self.xmm_location_ranges.items[range_index];
581 if (range.entry != .reload) continue;
582 if (!canUsePlannedValueLocation(range.value)) continue;
583 if (self.vector_slot_map.get(range.value)) |vslot| {
584 try vector.emitPackedLoad(self, vslot, range.reg);
585 } else {
586 try self.loadSlotXmm(try self.slotFor(range.value), range.reg);
587 }
588 }
589 }
590
591 pub fn emitEncoding(self: *Emitter, enc: encoding.Encoding) EmitError!void {
592 try self.code.appendSlice(self.allocator, enc.slice());
593 }
594
595 fn emitEpilogue(self: *Emitter) EmitError!void {
596 try self.frame_layout.emitEpilogue(self.allocator, &self.code);
597 }
598
599 /// Marks every operation this function will leave out, before anything is allocated.
600 ///
601 /// ONE DROP MAKES MORE. An addition nothing reads is droppable, and dropping it is what
602 /// makes the two constants feeding it unread in turn. A single sweep would leave those
603 /// constants behind, because their use count still names the addition. So this repeats
604 /// until a sweep marks nothing new.
605 ///
606 /// It terminates because a sweep only ever adds to the set and the set is bounded by the
607 /// operations in the region, so the loop runs at most that many times plus the sweep that
608 /// finds nothing. The assertion states it rather than trusting it.
609 fn markOmittedOps(self: *Emitter, region: *ir.Region) EmitError!void {
610 const ceiling = countOperations(region) + 1;
611 var sweeps: usize = 0;
612 while (true) {
613 sweeps += 1;
614 std.debug.assert(sweeps <= ceiling);
615 if (!try self.sweepOmittedOps(region)) break;
616 }
617 std.debug.assert(self.omitted_ops.count() <= ceiling);
618 }
619
620 fn countOperations(region: *ir.Region) usize {
621 var total: usize = 0;
622 var block_iter = region.blocks.head;
623 while (block_iter) |block| {
624 var op_iter = block.operations.head;
625 while (op_iter) |op_ptr| {
626 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
627 total += 1;
628 for (op.regions.items) |*nested| total += countOperations(nested);
629 op_iter = op.next_op;
630 }
631 block_iter = block.next;
632 }
633 return total;
634 }
635
636 fn sweepOmittedOps(self: *Emitter, region: *ir.Region) EmitError!bool {
637 var marked = false;
638 var block_iter = region.blocks.head;
639 while (block_iter) |block| {
640 var op_iter = block.operations.head;
641 while (op_iter) |op_ptr| {
642 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
643 for (op.regions.items) |*nested| {
644 if (try self.sweepOmittedOps(nested)) marked = true;
645 }
646 if (!self.omitted_ops.contains(op) and self.omitsOperation(op)) {
647 try self.omitted_ops.put(self.allocator, op, {});
648 marked = true;
649 }
650 op_iter = op.next_op;
651 }
652 block_iter = block.next;
653 }
654 return marked;
655 }
656
657 /// Whether the backend may leave this operation out of the function entirely.
658 ///
659 /// Three things must hold. The operation defines at least one result and nothing that
660 /// survives reads any of them, so leaving it out removes no value another instruction
661 /// needs. Its declared effects permit discarding it. And it is a leaf.
662 ///
663 /// PURITY IS NOT DECIDED HERE. `effects.permitsDiscard` reads the EffectOpInterface that
664 /// arith, func, memref, rc, scf and tile each already implement, and answers from what the
665 /// operation declared: discardable means total and read only, so an operation that writes,
666 /// traps, diverges, allocates, borrows, or hands back anything it owns is refused. Asking a
667 /// second mechanism the same question is how the two come to disagree.
668 ///
669 /// THE LEAF TEST IS A COST BOUND, NOT A SAFETY ONE. `EffectSummary` walks a region or a
670 /// callee to decide, and sizes itself from the whole module's operation count when it must.
671 /// This is asked of every operation in every sweep, so a region operation or a call is
672 /// refused here rather than answered expensively. Refusing costs a slot and keeps a value.
673 ///
674 /// An operation that declares no effects is refused too, because `permitsDiscard` answers
675 /// false without the interface. Undeclared and unregistered both mean keep.
676 fn omitsOperation(self: *const Emitter, op: *ir.Operation) bool {
677 if (op.results.items.len == 0) return false;
678 for (op.results.items) |*result| {
679 if (self.valueIsRead(result)) return false;
680 }
681 if (op.regions.items.len != 0) return false;
682 if (op.hasInterface(ir.interfaces.CallOpInterface)) return false;
683 return effects.permitsDiscard(op);
684 }
685
686 /// Records the exact boolean left in flags and the condition for its false edge.
687 /// Only syntactically adjacent branches qualify. Overflow additionally admits one
688 /// single-use boolean not. Wrapped result 0 keeps its ordinary home.
689 ///
690 /// Between the writer and branch, storeFrom and enterOperationPosition emit only
691 /// mov/movsx/movzx and scalar or packed SSE moves. The elided not still enters its
692 /// allocation position. Parallel edge moves run after the jump. Calls, arithmetic
693 /// zeroing and rsp adjustments require an intervening operation and cannot qualify.
694 /// Flags-only values have no slot, so range transitions cannot spill or reload their
695 /// unmaterialized register contents. Their allocator reservations stay conservative.
696 fn markFlagConditions(self: *Emitter, region: *ir.Region) EmitError!void {
697 var block_iter = region.blocks.head;
698 while (block_iter) |block| {
699 var op_iter = block.operations.head;
700 while (op_iter) |op_ptr| {
701 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
702 op_iter = op.next_op;
703 for (op.regions.items) |*nested| try self.markFlagConditions(nested);
704 if (self.omitted_ops.contains(op)) continue;
705 if (std.mem.eql(u8, op.name.name, ArithDialect.CmpOp.operation_name)) {
706 const result = op.getResult(0) orelse continue;
707 const lhs = op.getOperand(0) orelse continue;
708 const kind = arith.scalarKindFromType(lhs.type) orelse continue;
709 if (arith.scalarKindIsFloat(kind)) continue;
710 if (!adjacentCondition(op, result)) continue;
711 const predicate = (ArithDialect.CmpOp{ .op = op }).getPredicate() orelse
712 return error.MissingPredicate;
713 try self.flag_conditions.put(self.allocator, result, invertCondition(scalar.conditionForIntPredicate(predicate)));
714 } else if (overflowOperation(op)) {
715 const overflow = op.getResult(1) orelse continue;
716 if (!valueHasSingleUse(overflow)) continue;
717 if (adjacentCondition(op, overflow)) {
718 try self.flag_conditions.put(self.allocator, overflow, .no);
719 continue;
720 }
721 const negation = op.next_op orelse continue;
722 if (!std.mem.eql(u8, negation.name.name, ArithDialect.NotOp.operation_name)) continue;
723 if (negation.getNumOperands() != 1 or negation.getNumResults() != 1) continue;
724 if (negation.getOperand(0) != overflow) continue;
725 const inverted = negation.getResult(0).?;
726 if (arith.scalarKindFromType(inverted.type) != .bool) continue;
727 if (!adjacentCondition(negation, inverted)) continue;
728 try self.flag_conditions.put(self.allocator, overflow, .no);
729 try self.flag_conditions.put(self.allocator, inverted, .o);
730 }
731 }
732 block_iter = block.next;
733 }
734 }
735
736 fn overflowOperation(op: *ir.Operation) bool {
737 inline for (.{ ArithDialect.AddoOp, ArithDialect.SuboOp, ArithDialect.MuloOp }) |Op| {
738 if (std.mem.eql(u8, op.name.name, Op.operation_name)) return true;
739 }
740 return false;
741 }
742
743 fn adjacentCondition(op: *ir.Operation, value: *ir.Value) bool {
744 if (!valueHasSingleUse(value)) return false;
745 const next = op.next_op orelse return false;
746 if (std.mem.eql(u8, next.name.name, ScfDialect.IfOp.operation_name)) {
747 return (ScfDialect.IfOp{ .op = next }).getCondition() == value;
748 }
749 if (std.mem.eql(u8, next.name.name, ScfDialect.ConditionOp.operation_name)) {
750 return (ScfDialect.ConditionOp{ .op = next }).getCondition() == value;
751 }
752 return false;
753 }
754
755 pub fn flagsOnly(self: *const Emitter, value: *ir.Value) bool {
756 return self.flag_conditions.contains(value);
757 }
758
759 /// Whether any operation that survives names this value as an operand.
760 ///
761 /// A use held only by an operation already marked is not a read, because that operation
762 /// will emit nothing. This is what carries one drop into the next.
763 fn valueIsRead(self: *const Emitter, value: *ir.Value) bool {
764 var use = value.first_use;
765 while (use) |operand| {
766 const user: *ir.Operation = @ptrCast(@alignCast(operand.owner));
767 if (!self.omitted_ops.contains(user)) return true;
768 use = operand.next_use;
769 }
770 return false;
771 }
772
773 fn collectSlotsInRegion(self: *Emitter, region: *ir.Region) EmitError!void {
774 var block_iter = region.blocks.head;
775 while (block_iter) |block| {
776 for (block.arguments.items) |arg| {
777 try self.addSlot(arg);
778 }
779
780 var op_iter = block.operations.head;
781 while (op_iter) |op_ptr| {
782 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
783 if (self.omitted_ops.contains(op)) {
784 op_iter = op.next_op;
785 continue;
786 }
787 try self.addResultSlots(op);
788 if (std.mem.eql(u8, op.name.name, MemrefDialect.AllocaOp.operation_name)) {
789 try self.addAllocaPayloadSlot(MemrefDialect.AllocaOp{ .op = op });
790 }
791 for (op.regions.items) |*nested| {
792 try self.collectSlotsInRegion(nested);
793 }
794 op_iter = op.next_op;
795 }
796
797 block_iter = block.next;
798 }
799 }
800
801 /// A record call reserves its result slots last to first, so each result sits one
802 /// eightbyte above the previous one and the first slot addresses the whole record.
803 ///
804 /// A result nothing reads is given no slot, when the operation defining it can do without
805 /// one. The frame is sized from the slots handed out, so such a value was charging the
806 /// function eight bytes of stack plus a store writing a number nothing could ever load.
807 ///
808 /// Every other value keeps a slot, including one that lives its whole life in a register:
809 /// the allocator may spill it at a range end, and the reload has to find it somewhere.
810 ///
811 /// A record result is exempt even when it is dead. Those slots are not independent. The
812 /// callee writes the record through a hidden pointer into a run of adjacent eightbytes and
813 /// the first slot addresses the whole run, so dropping a member would move the ones above
814 /// it. `slotCoversRecord` asserts the run survived.
815 fn addResultSlots(self: *Emitter, op: *ir.Operation) EmitError!void {
816 const results = op.results.items;
817 const is_call = std.mem.eql(u8, op.name.name, FuncDialect.CallOp.operation_name);
818 if (!is_call or !abi.returnsThroughRecord(results.len)) {
819 const droppable = resultSlotIsDroppable(op);
820 for (results) |*result| {
821 if (self.flagsOnly(result)) continue;
822 if (droppable and result.hasNoUses()) continue;
823 try self.addSlot(result);
824 std.debug.assert(self.hasAnySlot(result));
825 }
826 return;
827 }
828 var index = results.len;
829 while (index > 0) {
830 index -= 1;
831 try self.addSlot(&results[index]);
832 }
833 std.debug.assert(self.slotCoversRecord(results));
834 }
835
836 fn vectorTypeInfoFromType(self: *Emitter, typ: ir.Type) EmitError!?VectorSlot {
837 const name = typ.getDialectTypeName() orelse return null;
838 const info = arith.parseVectorTypeName(name) orelse return null;
839 const elem = try self.slotShapeFromName(info.elem_type_name);
840 const is_float = std.mem.eql(u8, info.elem_type_name, "arith.f32") or std.mem.eql(u8, info.elem_type_name, "arith.f64");
841 return .{
842 .base = .{ .offset = 0, .width = elem.width, .ext = elem.ext },
843 .lanes = @intCast(info.width),
844 .elem_type_name = info.elem_type_name,
845 .is_float = is_float,
846 };
847 }
848
849 fn resultIsVector(op: *ir.Operation) EmitError!bool {
850 const result = op.getResult(0) orelse return error.MissingResult;
851 const type_name = result.type.getDialectTypeName() orelse return error.UnsupportedType;
852 return arith.parseVectorTypeName(type_name) != null;
853 }
854
855 /// Reserves the frame bytes one value lives in, at most once per value.
856 ///
857 /// The frame is sized from `slot_count`, so every call here costs the function stack. A
858 /// caller that has decided a value needs no slot simply does not call this: there is no
859 /// way to hand out a slot and then take it back, because the next reservation would sit
860 /// where the withdrawn one did and every offset already published would be wrong.
861 /// Whether this operation can define a result that has no frame slot at all.
862 ///
863 /// The answer turns on where the operation puts its result, not on whether the result is
864 /// wanted. A call and a syscall return in a fixed register, so the slot is only a home for
865 /// a value that already exists, and a result nothing reads needs no home. A region
866 /// operation receives its result from a move emitted at the region's exit, and that move is
867 /// skipped for a result nothing reads by the same argument.
868 ///
869 /// Everything else keeps its slot. Arithmetic emitters name the slot directly as an
870 /// instruction's destination, so withdrawing it there would not delete a store, it would
871 /// delete the computation, and choir carries no purity model that could say when deleting a
872 /// computation is sound. An operation this function does not recognise keeps its slot,
873 /// because a wrong yes costs a wrong address and a wrong no costs eight bytes.
874 fn resultSlotIsDroppable(op: *ir.Operation) bool {
875 const name = op.name.name;
876 inline for (.{
877 FuncDialect.CallOp,
878 FuncDialect.SyscallOp,
879 ScfDialect.IfOp,
880 ScfDialect.ForOp,
881 ScfDialect.WhileOp,
882 }) |Op| {
883 if (std.mem.eql(u8, name, Op.operation_name)) return true;
884 }
885 return false;
886 }
887
888 /// Whether a value holds frame bytes of either kind, a scalar slot or a vector run.
889 fn hasAnySlot(self: *const Emitter, value: *ir.Value) bool {
890 if (self.slot_map.contains(value)) return true;
891 return self.vector_slot_map.contains(value);
892 }
893
894 fn addSlot(self: *Emitter, value: *ir.Value) EmitError!void {
895 if (self.slot_map.contains(value) or self.vector_slot_map.contains(value)) return;
896
897 if (try self.vectorTypeInfoFromType(value.type)) |vector_info| {
898 const base_offset: i32 = -@as(i32, @intCast((self.slot_count + self.reserved_callee_saved + 1) * abi.stack_slot_size));
899 var info = vector_info;
900 info.base.offset = base_offset;
901 try self.vector_slot_map.put(self.allocator, value, info);
902 self.slot_count += info.lanes;
903 return;
904 }
905
906 const shape = try self.slotShape(value.type);
907 try self.slot_map.put(self.allocator, value, self.reserveSlot(shape.width, shape.ext));
908 }
909
910 /// THE ONE PLACE A VALUE'S FORM IS FIXED. Everything downstream reads it
911 /// off the slot rather than deciding it again.
912 fn reserveSlot(self: *Emitter, width: u8, ext: IntExtension) Slot {
913 std.debug.assert(width >= 8);
914 std.debug.assert(width <= abi.stack_slot_size * 8);
915 std.debug.assert(std.math.isPowerOfTwo(width));
916 const offset: i32 = -@as(i32, @intCast((self.slot_count + self.reserved_callee_saved + 1) * abi.stack_slot_size));
917 std.debug.assert(offset < 0);
918 self.slot_count += 1;
919 return .{ .offset = offset, .width = width, .ext = ext };
920 }
921
922 fn reserveMoveScratchSlots(self: *Emitter) void {
923 if (self.move_scratch_slots != null) return;
924 self.move_scratch_slots = .{
925 .cycle = self.reserveSlot(64, .unsigned),
926 .save = self.reserveSlot(64, .unsigned),
927 };
928 }
929
930 /// Reserves the frame cell a static `memref.alloca` names, past every slot already given out.
931 ///
932 /// THE SAVED REGISTERS ARE PART OF THE OFFSET. The callee-saved registers the allocator
933 /// reserved sit between rbp and the first local, and `reserveSlot` counts them in every slot
934 /// offset it hands out, so a payload measured from `slot_count` alone overlaps the last scalar
935 /// slot, the saved registers, and the return address above them. Both the padding base and the
936 /// payload's own offset therefore count `reserved_callee_saved` as well. Nothing could reach
937 /// that overlap before a function holding an alloca could be register allocated, because only
938 /// allocation reserves a callee-saved register.
939 fn addAllocaPayloadSlot(self: *Emitter, alloca_op: MemrefDialect.AllocaOp) EmitError!void {
940 const result = alloca_op.getResult();
941 if (self.alloca_payload_slots.contains(result)) return;
942
943 const bytes = try memory.allocaByteSize(self, alloca_op);
944 const byte_count: usize = @intCast(@max(bytes, 1));
945 const payload_slots = (byte_count + abi.stack_slot_size - 1) / abi.stack_slot_size;
946 const alignment = try memory.allocaAlignment(self, alloca_op);
947 const payload_base = self.slot_count + self.reserved_callee_saved;
948 const padding_slots = allocaPaddingSlots(payload_base, payload_slots, alignment);
949 self.slot_count += padding_slots;
950 const base_offset: i32 = -@as(i32, @intCast((self.slot_count + self.reserved_callee_saved + payload_slots) * abi.stack_slot_size));
951 self.slot_count += payload_slots;
952 try self.alloca_payload_slots.put(self.allocator, result, .{
953 .offset = base_offset,
954 .width = 64,
955 .ext = .unsigned,
956 });
957 }
958
959 /// Whether the slots just reserved for a record call form the contiguous run the ABI needs.
960 ///
961 /// `canonicalizeRecordResults` and the hidden pointer argument both read the first slot as
962 /// the address of the whole record, so a gap here is a call writing over a neighbour.
963 fn slotCoversRecord(self: *Emitter, results: []ir.Value) bool {
964 const first = self.slotForOptional(&results[0]) orelse return false;
965 for (results, 0..) |*result, i| {
966 const slot = self.slotForOptional(result) orelse return false;
967 if (slot.offset != first.offset + abi.recordFieldOffset(i)) return false;
968 }
969 return true;
970 }
971
972 fn allocaPaddingSlots(slot_count: usize, payload_slots: usize, alignment: u64) usize {
973 if (alignment <= abi.stack_slot_size) return 0;
974 const effective = @min(alignment, abi.stack_alignment);
975 const payload_bytes = @as(u64, @intCast((slot_count + payload_slots) * abi.stack_slot_size));
976 const remainder = payload_bytes % effective;
977 if (remainder == 0) return 0;
978 const padding_bytes = effective - remainder;
979 return @intCast((padding_bytes + abi.stack_slot_size - 1) / abi.stack_slot_size);
980 }
981
982 /// What one type looks like in a slot: how wide, and which form a reload
983 /// puts it back in.
984 ///
985 /// THIS IS ONE TABLE BECAUSE IT USED TO BE TWO ANSWERS AND ONE OF THEM WAS
986 /// THROWN AWAY. `arith.i8` and `arith.u8` sat on adjacent lines here,
987 /// were told apart, and both answered 8, so the signedness was in hand at
988 /// the moment it was dropped and `Slot` had nowhere to put it. A `u8` of
989 /// 200 then came back out of its slot as -56. Width and
990 /// form leave this function together so that neither can be read without
991 /// the other.
992 ///
993 /// The form of a float, a memref or a `bool` is `unsigned` and is never
994 /// consulted, because only widths 8 and 16 branch on it.
995 fn slotShapeFromName(self: *Emitter, name: []const u8) EmitError!SlotShape {
996 _ = self;
997 if (std.mem.eql(u8, name, "arith.i64") or
998 std.mem.eql(u8, name, "arith.index") or
999 std.mem.eql(u8, name, "arith.bool"))
1000 {
1001 return .{ .width = 64, .ext = .signed };
1002 }
1003 if (std.mem.eql(u8, name, "arith.u64")) return .{ .width = 64, .ext = .unsigned };
1004 if (std.mem.eql(u8, name, "arith.i8")) return .{ .width = 8, .ext = .signed };
1005 if (std.mem.eql(u8, name, "arith.i16")) return .{ .width = 16, .ext = .signed };
1006 if (std.mem.eql(u8, name, "arith.i32")) return .{ .width = 32, .ext = .signed };
1007 if (std.mem.eql(u8, name, "arith.u8")) return .{ .width = 8, .ext = .unsigned };
1008 if (std.mem.eql(u8, name, "arith.u16")) return .{ .width = 16, .ext = .unsigned };
1009 if (std.mem.eql(u8, name, "arith.u32")) return .{ .width = 32, .ext = .unsigned };
1010 if (std.mem.eql(u8, name, MemrefDialect.name)) return .{ .width = 64, .ext = .unsigned };
1011 if (std.mem.eql(u8, name, "arith.f64")) return .{ .width = 64, .ext = .unsigned };
1012 if (std.mem.eql(u8, name, "arith.f32")) return .{ .width = 32, .ext = .unsigned };
1013 if (std.mem.eql(u8, name, "arith.f16") or std.mem.eql(u8, name, "arith.bf16")) return error.UnsupportedType;
1014 return error.UnsupportedType;
1015 }
1016
1017 /// The same answer for a value's own type.
1018 fn slotShape(self: *Emitter, typ: ir.Type) EmitError!SlotShape {
1019 const name = typ.getDialectTypeName() orelse return error.UnsupportedType;
1020 return self.slotShapeFromName(name);
1021 }
1022
1023 fn valueWidthFromName(self: *Emitter, name: []const u8) EmitError!u8 {
1024 return (try self.slotShapeFromName(name)).width;
1025 }
1026
1027 pub fn typeInfoFromName(self: *Emitter, name: []const u8) EmitError!TypeInfo {
1028 if (std.mem.eql(u8, name, "arith.f32")) return .{ .width = 32, .is_float = true };
1029 if (std.mem.eql(u8, name, "arith.f64")) return .{ .width = 64, .is_float = true };
1030 if (std.mem.eql(u8, name, "arith.f16") or std.mem.eql(u8, name, "arith.bf16")) return error.UnsupportedType;
1031 const width = try self.valueWidthFromName(name);
1032 return .{ .width = width, .is_float = false };
1033 }
1034
1035 pub fn slotFor(self: *Emitter, value: *ir.Value) EmitError!Slot {
1036 return self.slot_map.get(value) orelse error.MissingSlot;
1037 }
1038
1039 /// The slot a value was given, or null when it was given none because nothing reads it.
1040 ///
1041 /// Callers that settle a value they are defining use this. Callers that read an operand
1042 /// use `slotFor` and keep its refusal, because an operand is by definition a use and so
1043 /// always had a slot reserved for it.
1044 pub fn slotForOptional(self: *Emitter, value: *ir.Value) ?Slot {
1045 return self.slot_map.get(value);
1046 }
1047
1048 pub fn vectorSlotFor(self: *Emitter, value: *ir.Value) EmitError!VectorSlot {
1049 return self.vector_slot_map.get(value) orelse error.MissingSlot;
1050 }
1051
1052 fn emitArgumentSpills(self: *Emitter, entry: *ir.Block) EmitError!void {
1053 const arg_count = entry.arguments.items.len;
1054 const sret_count: usize = if (self.sret_info != null) 1 else 0;
1055 const total_count = arg_count + sret_count;
1056 if (total_count == 0) return;
1057
1058 var arg_type_names = std.ArrayListUnmanaged([]const u8).empty;
1059 defer arg_type_names.deinit(self.allocator);
1060
1061 if (sret_count != 0) {
1062 try arg_type_names.append(self.allocator, "arith.index");
1063 }
1064 for (entry.arguments.items) |arg| {
1065 const name = arg.type.getDialectTypeName() orelse return error.UnsupportedType;
1066 try arg_type_names.append(self.allocator, name);
1067 }
1068
1069 const locations = try self.allocator.alloc(abi.ValueLocation, total_count);
1070 defer self.allocator.free(locations);
1071 abi.computeArgLocations(arg_type_names.items, locations);
1072
1073 if (sret_count != 0) {
1074 const sret_slot = self.sret_slot orelse return error.MissingSlot;
1075 switch (locations[0]) {
1076 .int_reg => |reg| {
1077 try self.storeSlot(sret_slot, reg);
1078 },
1079 .fp_reg => return error.UnsupportedType,
1080 .stack => |offset| {
1081 const mem = Mem.baseDisp(.rbp, 16 + offset);
1082 try self.emitEncoding(encoding.movRegMem(.rax, mem));
1083 try self.storeSlot(sret_slot, .rax);
1084 },
1085 }
1086 }
1087
1088 var parallel: std.ArrayListUnmanaged(moves.Move) = .empty;
1089 defer parallel.deinit(self.allocator);
1090
1091 for (entry.arguments.items, 0..) |arg, i| {
1092 const slot = try self.slotFor(arg);
1093 switch (locations[i + sret_count]) {
1094 .int_reg => |reg| {
1095 try parallel.append(self.allocator, .{
1096 .src = .{ .reg = reg },
1097 .dst = try self.placeFor(arg),
1098 });
1099 },
1100 .fp_reg => |reg| {
1101 try parallel.append(self.allocator, .{
1102 .src = .{ .xmm = reg },
1103 .dst = try self.placeFor(arg),
1104 });
1105 },
1106 .stack => |offset| {
1107 try parallel.append(self.allocator, .{
1108 .src = .{ .slot = .{ .offset = 16 + offset, .width = slot.width, .ext = slot.ext } },
1109 .dst = try self.placeFor(arg),
1110 });
1111 },
1112 }
1113 }
1114 try self.emitParallelMoves(parallel.items);
1115 }
1116
1117 /// Reads a value back in the form it was spelled with.
1118 ///
1119 /// This used to pass `.signed` whatever the value was, which is the whole
1120 /// failure: a `u8` was stored by a `movzbq` that read its byte
1121 /// as 200 and returned by a `movsbq` that read the same byte as -56. The
1122 /// slot now carries the answer, so nothing here decides it.
1123 pub fn loadSlot(self: *Emitter, slot: Slot, reg: GPR) EmitError!void {
1124 try self.loadSlotWithExt(slot, reg, slot.ext);
1125 }
1126
1127 /// Reads a value zero extended REGARDLESS of how it was spelled.
1128 ///
1129 /// This is a statement about the operation and not about the value, and
1130 /// only an operation whose semantics demand the unsigned form may make
1131 /// it. A logical shift right is the clear case: it reads its input as a
1132 /// bit pattern, so an `i8` of -56 shifts as 200 and `loadSlot` would be
1133 /// wrong. A site that calls this merely because its operand happens to be
1134 /// unsigned is asking the slot a question the slot already answers, and
1135 /// should call `loadSlot`.
1136 pub fn loadSlotUnsigned(self: *Emitter, slot: Slot, reg: GPR) EmitError!void {
1137 try self.loadSlotWithExt(slot, reg, .unsigned);
1138 }
1139
1140 fn loadSlotWithExt(self: *Emitter, slot: Slot, reg: GPR, ext: IntExtension) EmitError!void {
1141 const mem = Mem.baseDisp(.rbp, slot.offset);
1142 switch (slot.width) {
1143 8 => {
1144 if (ext == .signed) {
1145 try self.emitEncoding(encoding.movsxRegMem8(reg, mem));
1146 } else {
1147 try self.emitEncoding(encoding.movzxRegMem8(reg, mem));
1148 }
1149 },
1150 16 => {
1151 if (ext == .signed) {
1152 try self.emitEncoding(encoding.movsxRegMem16(reg, mem));
1153 } else {
1154 try self.emitEncoding(encoding.movzxRegMem16(reg, mem));
1155 }
1156 },
1157 32 => {
1158 try self.emitEncoding(encoding.movRegMem32(reg, mem));
1159 },
1160 64 => {
1161 try self.emitEncoding(encoding.movRegMem(reg, mem));
1162 },
1163 else => return error.UnsupportedType,
1164 }
1165 }
1166
1167 pub fn storeSlot(self: *Emitter, slot: Slot, reg: GPR) EmitError!void {
1168 try self.storeMemory(Mem.baseDisp(.rbp, slot.offset), slot.width, reg);
1169 }
1170
1171 fn storeMemory(self: *Emitter, mem: Mem, width: u8, reg: GPR) EmitError!void {
1172 switch (width) {
1173 8 => try self.emitEncoding(encoding.movMemReg8(mem, reg)),
1174 16 => try self.emitEncoding(encoding.movMemReg16(mem, reg)),
1175 32 => try self.emitEncoding(encoding.movMemReg32(mem, reg)),
1176 64 => try self.emitEncoding(encoding.movMemReg(mem, reg)),
1177 else => return error.UnsupportedType,
1178 }
1179 }
1180
1181 pub fn loadSlotXmm(self: *Emitter, slot: Slot, reg: XMM) EmitError!void {
1182 const mem = Mem.baseDisp(.rbp, slot.offset);
1183 if (slot.width == 32) {
1184 try self.emitEncoding(encoding.movss(reg, .{ .mem = mem }));
1185 } else if (slot.width == 64) {
1186 try self.emitEncoding(encoding.movsd(reg, .{ .mem = mem }));
1187 } else {
1188 return error.UnsupportedType;
1189 }
1190 }
1191
1192 pub fn storeSlotXmm(self: *Emitter, slot: Slot, reg: XMM) EmitError!void {
1193 try self.storeMemoryXmm(Mem.baseDisp(.rbp, slot.offset), slot.width, reg);
1194 }
1195
1196 fn storeMemoryXmm(self: *Emitter, mem: Mem, width: u8, reg: XMM) EmitError!void {
1197 switch (width) {
1198 32 => try self.emitEncoding(encoding.movssStore(mem, reg)),
1199 64 => try self.emitEncoding(encoding.movsdStore(mem, reg)),
1200 else => return error.UnsupportedType,
1201 }
1202 }
1203
1204 pub fn loadInto(self: *Emitter, value: *ir.Value, reg: GPR) EmitError!void {
1205 if (self.registerHome(value)) |home| {
1206 try self.copyHome(value, home, reg);
1207 } else {
1208 try self.loadSlot(try self.slotFor(value), reg);
1209 }
1210 }
1211
1212 pub fn loadIntoUnsigned(self: *Emitter, value: *ir.Value, reg: GPR) EmitError!void {
1213 if (self.registerHome(value)) |home| {
1214 try self.copyHome(value, home, reg);
1215 } else {
1216 try self.loadSlotUnsigned(try self.slotFor(value), reg);
1217 }
1218 }
1219
1220 fn copyHome(self: *Emitter, value: *ir.Value, home: GPR, reg: GPR) EmitError!void {
1221 const slot = try self.slotFor(value);
1222 if (slot.width == 32) {
1223 try self.emitEncoding(encoding.movRegReg32(reg, home));
1224 return;
1225 }
1226 if (home != reg) try self.emitEncoding(encoding.movRegReg(reg, home));
1227 }
1228
1229 pub fn storeFrom(self: *Emitter, value: *ir.Value, reg: GPR) EmitError!void {
1230 if (self.registerHomeForPhase(value, .definition)) |home| {
1231 if (home != reg) try self.emitEncoding(encoding.movRegReg(home, reg));
1232 return;
1233 }
1234 const slot = self.slotForOptional(value) orelse {
1235 std.debug.assert(value.hasNoUses());
1236 return;
1237 };
1238 try self.storeSlot(slot, reg);
1239 }
1240
1241 pub fn loadIntoXmm(self: *Emitter, value: *ir.Value, reg: XMM) EmitError!void {
1242 if (self.xmmHome(value)) |home| {
1243 if (home != reg) try self.emitEncoding(encoding.movaps(reg, .{ .reg = home }));
1244 } else {
1245 try self.loadSlotXmm(try self.slotFor(value), reg);
1246 }
1247 }
1248
1249 pub fn storeFromXmm(self: *Emitter, value: *ir.Value, reg: XMM) EmitError!void {
1250 if (self.xmmHomeForPhase(value, .definition)) |home| {
1251 if (home != reg) try self.emitEncoding(encoding.movaps(home, .{ .reg = reg }));
1252 return;
1253 }
1254 const slot = self.slotForOptional(value) orelse {
1255 std.debug.assert(value.hasNoUses());
1256 return;
1257 };
1258 try self.storeSlotXmm(slot, reg);
1259 }
1260
1261 pub fn loadIntoXmmPacked(self: *Emitter, value: *ir.Value, reg: XMM) EmitError!void {
1262 if (self.xmmHome(value)) |home| {
1263 if (home != reg) try self.emitEncoding(encoding.movaps(reg, .{ .reg = home }));
1264 } else {
1265 try vector.emitPackedLoad(self, try self.vectorSlotFor(value), reg);
1266 }
1267 }
1268
1269 pub fn storeFromXmmPacked(self: *Emitter, value: *ir.Value, reg: XMM) EmitError!void {
1270 if (self.xmmHomeForPhase(value, .definition)) |home| {
1271 if (home != reg) try self.emitEncoding(encoding.movaps(home, .{ .reg = reg }));
1272 } else {
1273 try vector.emitPackedStore(self, try self.vectorSlotFor(value), reg);
1274 }
1275 }
1276
1277 fn placeFor(self: *Emitter, value: *ir.Value) EmitError!moves.Place {
1278 return self.placeForAt(value, self.allocation_position);
1279 }
1280
1281 fn placeForAt(self: *Emitter, value: *ir.Value, position: u32) EmitError!moves.Place {
1282 return self.placeForAtPoint(value, regalloc.PositionPoint.source(position));
1283 }
1284
1285 fn placeForAtPoint(self: *Emitter, value: *ir.Value, point: regalloc.PositionPoint) EmitError!moves.Place {
1286 if (valueIsFloatScalar(value)) {
1287 if (self.xmmHomeAtPoint(value, point)) |home| {
1288 return .{ .xmm = home };
1289 }
1290 return .{ .slot = try self.slotFor(value) };
1291 }
1292 if (self.registerHomeAtPoint(value, point)) |home| {
1293 return .{ .reg = home };
1294 }
1295 return .{ .slot = try self.slotFor(value) };
1296 }
1297
1298 fn valueHasReloadRange(self: *const Emitter, value: *ir.Value) bool {
1299 if (valueIsFloatScalar(value)) {
1300 return self.xmm_location_index.valueHasEntry(self.xmm_location_ranges.items, value, .reload);
1301 }
1302 return self.value_location_index.valueHasEntry(self.value_location_ranges.items, value, .reload);
1303 }
1304
1305 fn mirrorValueToSlotIfReloaded(self: *Emitter, value: *ir.Value, place: moves.Place) EmitError!void {
1306 if (!self.valueHasReloadRange(value)) return;
1307 switch (place) {
1308 .reg => |reg| try self.storeSlot(self.slotForOptional(value) orelse return, reg),
1309 .xmm => |reg| try self.storeSlotXmm(self.slotForOptional(value) orelse return, reg),
1310 .slot => {},
1311 }
1312 }
1313
1314 fn emitPlaceMove(self: *Emitter, source: moves.Place, target: moves.Place) EmitError!void {
1315 if (moves.samePlace(source, target)) return;
1316 if (source != .slot or target != .slot) {
1317 try self.copyPlace(source, target, .{ .reg = moves.stack_scratch_gpr });
1318 return;
1319 }
1320 const scratch = if (self.scratchAt(self.allocation_position, &.{})) |reg|
1321 MoveScratch{ .reg = reg }
1322 else if (self.move_scratch_slots) |slots|
1323 MoveScratch{ .stack = .{ .slots = slots, .memory_reg = moves.stack_scratch_gpr } }
1324 else
1325 return error.NoScratchRegister;
1326 try self.copyPlace(source, target, scratch);
1327 }
1328
1329 fn callArgSourceFor(self: *Emitter, value: *ir.Value) EmitError!ArgSource {
1330 if (self.registerHome(value)) |home| {
1331 return .{ .gpr = home };
1332 }
1333 return .{ .slot = try self.slotFor(value) };
1334 }
1335
1336 fn appendParallelValueMoveAt(
1337 self: *Emitter,
1338 parallel: *std.ArrayListUnmanaged(moves.Move),
1339 source: *ir.Value,
1340 source_position: u32,
1341 target: *ir.Value,
1342 target_position: u32,
1343 ) EmitError!void {
1344 try self.appendParallelValueMoveAtPoints(
1345 parallel,
1346 source,
1347 regalloc.PositionPoint.source(source_position),
1348 target,
1349 regalloc.PositionPoint.source(target_position),
1350 );
1351 }
1352
1353 /// Whether a region's result is worth settling when the region exits.
1354 ///
1355 /// A result nothing reads was given no slot, so the move that would carry the region's
1356 /// value into it has nowhere to land. Skipping it is the same decision slot allocation
1357 /// already made, one step later.
1358 ///
1359 /// THIS TEST IS SOUND FOR A RESULT AND NOT FOR A BLOCK ARGUMENT. A result is read only
1360 /// through its uses, so no use means no reader. A loop's block argument is different: the
1361 /// backend itself reads one at the loop exit to produce the loop's result, and that read is
1362 /// not an operand of any operation, so `hasNoUses` would call a live value dead.
1363 fn resultNeedsSettling(self: *const Emitter, result: *ir.Value) bool {
1364 _ = self;
1365 return !result.hasNoUses();
1366 }
1367
1368 /// Whether a value arrives in its frame slot rather than in a register.
1369 ///
1370 /// A value allocation gave no home of its own carries only ranges a reload enters, and a
1371 /// reload's register holds nothing until the reload itself runs. Between the point the
1372 /// value arrives and that range's start the value lives in its slot and nowhere else, so
1373 /// the slot is the only place a writer at the arrival point may use.
1374 fn arrivesInSlot(self: *const Emitter, value: *ir.Value) bool {
1375 if (valueIsFloatScalar(value)) {
1376 if (!self.hasPlannedXmmLocation(value)) return false;
1377 return !self.xmm_location_index.valueHasEntry(self.xmm_location_ranges.items, value, .resident);
1378 }
1379 if (!self.hasPlannedValueLocation(value)) return false;
1380 return !self.value_location_index.valueHasEntry(self.value_location_ranges.items, value, .resident);
1381 }
1382
1383 /// THE PLACE A LOOP EDGE WRITES FOR ONE CARRIED VALUE.
1384 ///
1385 /// A LOOP EDGE WRITES THE PLACE THE VALUE OCCUPIES WHERE CONTROL ARRIVES, NEVER A PLACE IT
1386 /// OCCUPIES LATER. A carried value is defined by the edge itself, so a range a resident
1387 /// entry opens begins where control arrives and names the register to write. A value with
1388 /// no such range arrives in its slot, and the reload allocation planned then loads what the
1389 /// edge wrote there.
1390 ///
1391 /// Reading the register of a later reload range instead leaves the arrival slot unwritten.
1392 /// The planned reload reads a frame cell nothing ever stored, while intervening operations
1393 /// may clobber the register holding the value. It can also let two carried values name one
1394 /// register, since
1395 /// two places read at two different future positions need not differ, which is the
1396 /// `InvalidParallelMove` a flat `scf.while` met at fifteen and sixteen carried values.
1397 fn arrivalPlaceFor(self: *Emitter, value: *ir.Value, fallback_position: u32, phase: regalloc.PositionPhase) EmitError!moves.Place {
1398 if (self.arrivesInSlot(value)) return .{ .slot = try self.slotFor(value) };
1399 const position = self.plannedValueStart(value) orelse fallback_position;
1400 return self.placeForAtPoint(value, .{ .position = position, .phase = phase });
1401 }
1402
1403 /// Appends the move one loop edge makes for one carried value.
1404 fn appendCarriedValueMove(
1405 self: *Emitter,
1406 parallel: *std.ArrayListUnmanaged(moves.Move),
1407 source: *ir.Value,
1408 source_point: regalloc.PositionPoint,
1409 target: *ir.Value,
1410 arrival_position: u32,
1411 arrival_phase: regalloc.PositionPhase,
1412 ) EmitError!void {
1413 const source_slot = try self.slotFor(source);
1414 const target_slot = try self.slotFor(target);
1415 if (source_slot.width != target_slot.width) return error.InvalidParallelMove;
1416 try parallel.append(self.allocator, .{
1417 .src = try self.placeForAtPoint(source, source_point),
1418 .dst = try self.arrivalPlaceFor(target, arrival_position, arrival_phase),
1419 });
1420 }
1421
1422 fn appendParallelValueMoveAtPoints(
1423 self: *Emitter,
1424 parallel: *std.ArrayListUnmanaged(moves.Move),
1425 source: *ir.Value,
1426 source_point: regalloc.PositionPoint,
1427 target: *ir.Value,
1428 target_point: regalloc.PositionPoint,
1429 ) EmitError!void {
1430 const source_slot = try self.slotFor(source);
1431 const target_slot = try self.slotFor(target);
1432 if (source_slot.width != target_slot.width) return error.InvalidParallelMove;
1433 try parallel.append(self.allocator, .{
1434 .src = try self.placeForAtPoint(source, source_point),
1435 .dst = try self.placeForAtPoint(target, target_point),
1436 });
1437 }
1438
1439 pub fn emitParallelMoves(self: *Emitter, parallel: []const moves.Move) EmitError!void {
1440 if (parallel.len == 0) return;
1441
1442 var int_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1443 defer int_moves.deinit(self.allocator);
1444 var float_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1445 defer float_moves.deinit(self.allocator);
1446 for (parallel) |move| {
1447 if (moves.placeIsXmm(move.src) or moves.placeIsXmm(move.dst)) {
1448 try float_moves.append(self.allocator, move);
1449 } else {
1450 try int_moves.append(self.allocator, move);
1451 }
1452 }
1453 try self.emitIntParallelMoves(int_moves.items);
1454 try self.emitFloatParallelMoves(float_moves.items);
1455 }
1456
1457 fn emitIntParallelMoves(self: *Emitter, parallel: []const moves.Move) EmitError!void {
1458 if (parallel.len == 0) return;
1459 const scratch = if (self.selectScratchReg(parallel)) |reg|
1460 MoveScratch{ .reg = reg }
1461 else if (self.move_scratch_slots) |slots|
1462 MoveScratch{ .stack = .{ .slots = slots, .memory_reg = moves.stack_scratch_gpr } }
1463 else
1464 return error.NoScratchRegister;
1465
1466 const scratch_place: moves.Place = switch (scratch) {
1467 .reg => |reg| .{ .reg = reg },
1468 .stack => |stack| .{ .slot = stack.slots.cycle },
1469 };
1470
1471 var resolved: std.ArrayListUnmanaged(moves.Move) = .empty;
1472 defer resolved.deinit(self.allocator);
1473 try moves.resolve(self.allocator, parallel, scratch_place, &resolved);
1474 for (resolved.items) |move| {
1475 try self.copyPlace(move.src, move.dst, scratch);
1476 }
1477 }
1478
1479 fn emitFloatParallelMoves(self: *Emitter, parallel: []const moves.Move) EmitError!void {
1480 if (parallel.len == 0) return;
1481 const scratch = self.selectXmmScratchReg(parallel) orelse return error.NoScratchRegister;
1482 var resolved: std.ArrayListUnmanaged(moves.Move) = .empty;
1483 defer resolved.deinit(self.allocator);
1484 try moves.resolve(self.allocator, parallel, .{ .xmm = scratch }, &resolved);
1485 for (resolved.items) |move| {
1486 try self.copyPlace(move.src, move.dst, .{ .reg = moves.stack_scratch_gpr });
1487 }
1488 }
1489
1490 fn xmmHostsRangeAt(self: *const Emitter, reg: XMM, position: u32) bool {
1491 return self.xmm_location_index.registerBlocksAt(reg, .{ .position = position, .phase = .source }) or
1492 self.xmm_location_index.registerBlocksAt(reg, .{ .position = position, .phase = .definition });
1493 }
1494
1495 fn selectXmmScratchReg(self: *const Emitter, parallel: []const moves.Move) ?XMM {
1496 for (registers.allocatable_xmms) |reg| {
1497 var used = false;
1498 for (parallel) |move| {
1499 if (moves.usesXmm(move.src, reg) or moves.usesXmm(move.dst, reg)) {
1500 used = true;
1501 break;
1502 }
1503 }
1504 if (used) continue;
1505 if (self.xmmHostsRangeAt(reg, self.allocation_position)) continue;
1506 return reg;
1507 }
1508 return null;
1509 }
1510
1511 fn registerHostsRangeAt(self: *const Emitter, reg: GPR, position: u32) bool {
1512 return self.value_location_index.registerBlocksAt(reg, .{ .position = position, .phase = .source }) or
1513 self.value_location_index.registerBlocksAt(reg, .{ .position = position, .phase = .definition });
1514 }
1515
1516 fn scratchAt(self: *const Emitter, position: u32, excluded: []const GPR) ?GPR {
1517 scan: for (moves.scratch_gprs) |reg| {
1518 for (excluded) |exclude| {
1519 if (exclude == reg) continue :scan;
1520 }
1521 if (self.registerHostsRangeAt(reg, position)) continue;
1522 return reg;
1523 }
1524 return null;
1525 }
1526
1527 fn selectScratchReg(self: *const Emitter, parallel: []const moves.Move) ?GPR {
1528 for (moves.scratch_gprs) |reg| {
1529 var used = false;
1530 for (parallel) |move| {
1531 if (moves.usesReg(move.src, reg) or moves.usesReg(move.dst, reg)) {
1532 used = true;
1533 break;
1534 }
1535 }
1536 if (used) continue;
1537 if (self.registerHostsRangeAt(reg, self.allocation_position)) continue;
1538 return reg;
1539 }
1540 return null;
1541 }
1542
1543 fn copyPlace(self: *Emitter, src: moves.Place, dst: moves.Place, scratch: MoveScratch) EmitError!void {
1544 if (moves.samePlace(src, dst)) return;
1545 switch (src) {
1546 .reg => |source_reg| switch (dst) {
1547 .reg => |dest_reg| try self.emitEncoding(encoding.movRegReg(dest_reg, source_reg)),
1548 .slot => |dest_slot| try self.storeSlot(dest_slot, source_reg),
1549 .xmm => return error.InvalidParallelMove,
1550 },
1551 .xmm => |source_reg| switch (dst) {
1552 .xmm => |dest_reg| try self.emitEncoding(encoding.movaps(dest_reg, .{ .reg = source_reg })),
1553 .slot => |dest_slot| try self.storeSlotXmm(dest_slot, source_reg),
1554 .reg => return error.InvalidParallelMove,
1555 },
1556 .slot => |source_slot| switch (dst) {
1557 .reg => |dest_reg| try self.loadSlot(source_slot, dest_reg),
1558 .xmm => |dest_reg| try self.loadSlotXmm(source_slot, dest_reg),
1559 .slot => |dest_slot| {
1560 if (source_slot.width != dest_slot.width) return error.InvalidParallelMove;
1561 switch (scratch) {
1562 .reg => |scratch_reg| {
1563 try self.loadSlot(source_slot, scratch_reg);
1564 try self.storeSlot(dest_slot, scratch_reg);
1565 },
1566 .stack => |stack| {
1567 try self.storeSlot(stack.slots.save, stack.memory_reg);
1568 try self.loadSlot(source_slot, stack.memory_reg);
1569 try self.storeSlot(dest_slot, stack.memory_reg);
1570 try self.loadSlot(stack.slots.save, stack.memory_reg);
1571 },
1572 }
1573 },
1574 },
1575 }
1576 }
1577
1578 /// Branch lookup uses the value, never just its producer: overflow result 0 is data.
1579 fn emitFalseBranchForConditionValue(self: *Emitter, value: *ir.Value, exit_label: *Label) EmitError!bool {
1580 const condition = self.flag_conditions.get(value) orelse return false;
1581 try self.emitJccLabel(condition, exit_label);
1582 return true;
1583 }
1584
1585 /// Sets the flags for a comparison of a materialized condition with zero, reading it where
1586 /// it lives: its register home when it has one, otherwise its frame slot.
1587 ///
1588 /// NO SCRATCH REGISTER IS TOUCHED, AND THAT IS THE POINT. The allocator records no clobber
1589 /// at a `scf.if` or a `scf.condition`, so a value it placed in any register may still be
1590 /// live across the branch. Loading the condition into rax first would destroy such a value,
1591 /// which is how a loop once forwarded its own condition in place of the value it carried.
1592 fn emitCompareWithZero(self: *Emitter, value: *ir.Value) EmitError!void {
1593 const slot = try self.slotFor(value);
1594 if (self.registerHome(value)) |home| {
1595 try self.emitEncoding(if (slot.width == 32)
1596 encoding.cmpRegImm32(home, 0)
1597 else
1598 encoding.cmpRegImm(home, 0));
1599 return;
1600 }
1601 const mem = Mem.baseDisp(.rbp, slot.offset);
1602 switch (slot.width) {
1603 32 => try self.emitEncoding(encoding.cmpMemImm8_32(mem, 0)),
1604 64 => try self.emitEncoding(encoding.cmpMemImm8(mem, 0)),
1605 else => return error.UnsupportedType,
1606 }
1607 }
1608
1609 fn valueHasSingleUse(value: *ir.Value) bool {
1610 const first = value.first_use orelse return false;
1611 return first.next_use == null;
1612 }
1613
1614 fn invertCondition(cond: Condition) Condition {
1615 return @fromBackingInt(@intCast(@backingInt(cond) ^ 1));
1616 }
1617
1618 fn recordFailure(self: *Emitter, op: *ir.Operation) void {
1619 if (self.failed_operation == null) self.failed_operation = op;
1620 }
1621
1622 fn emitBlockOps(self: *Emitter, block: *ir.Block, terminator: BlockTerminator) EmitError!BlockResult {
1623 var op_iter = block.operations.head;
1624 while (op_iter) |op_ptr| {
1625 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
1626 errdefer self.recordFailure(op);
1627 const name = op.name.name;
1628
1629 if (std.mem.eql(u8, name, ScfDialect.ConditionOp.operation_name)) {
1630 switch (terminator) {
1631 .while_condition => |ctx| {
1632 try self.enterOperationPosition(op);
1633 ctx.position.* = self.allocation_position;
1634 const cond_op = ScfDialect.ConditionOp{ .op = op };
1635 ctx.value.* = cond_op.getCondition();
1636 for (cond_op.getArgs()) |arg| {
1637 if (ctx.arg_count.* >= ctx.args.len) return error.InvalidWhileArity;
1638 ctx.args[ctx.arg_count.*] = arg;
1639 ctx.arg_count.* += 1;
1640 }
1641 if (op.next_op != null) return error.UnexpectedOperationAfterCondition;
1642 return .conditioned;
1643 },
1644 else => return error.UnsupportedOperation,
1645 }
1646 }
1647
1648 if (op.getResult(0)) |result| {
1649 if (self.flagsOnly(result)) {
1650 try self.beginOperation(op);
1651 if (std.mem.eql(u8, name, ArithDialect.CmpOp.operation_name)) {
1652 const emitted = try scalar.emitArithCmpFlags(self, op);
1653 std.debug.assert(emitted);
1654 } else {
1655 std.debug.assert(std.mem.eql(u8, name, ArithDialect.NotOp.operation_name));
1656 }
1657 op_iter = op.next_op;
1658 continue;
1659 }
1660 }
1661
1662 if (self.omitted_ops.contains(op)) {
1663 try self.enterOperationPosition(op);
1664 op_iter = op.next_op;
1665 continue;
1666 }
1667
1668 try self.beginOperation(op);
1669
1670 if (std.mem.eql(u8, name, FuncDialect.ReturnOp.operation_name)) {
1671 try self.emitReturn(op);
1672 return .returned;
1673 }
1674 if (std.mem.eql(u8, name, ScfDialect.YieldOp.operation_name)) {
1675 switch (terminator) {
1676 .function_return, .while_condition => return error.UnexpectedYield,
1677 .if_yield => |ctx| {
1678 try self.emitIfYield(op, ctx.op);
1679 try self.emitJmpLabel(ctx.merge_label);
1680 return .yielded;
1681 },
1682 .for_yield => |ctx| {
1683 try self.emitForYield(op, ctx.body_block, ctx.iv, ctx.step, ctx.entry_position, ctx.header_label);
1684 return .yielded;
1685 },
1686 .while_yield => |ctx| {
1687 try self.emitWhileYield(op, ctx.before_block, ctx.header_label);
1688 return .yielded;
1689 },
1690 }
1691 }
1692
1693 if (std.mem.eql(u8, name, ScfDialect.IfOp.operation_name)) {
1694 const if_op = ScfDialect.IfOp{ .op = op };
1695 const cond_val = if_op.getCondition();
1696
1697 try self.saveIfIncomingValues(op);
1698
1699 var else_label = Label{};
1700 defer else_label.deinit(self.allocator);
1701 var merge_label = Label{};
1702 defer merge_label.deinit(self.allocator);
1703
1704 if (!try self.emitFalseBranchForConditionValue(cond_val, &else_label)) {
1705 try self.emitCompareWithZero(cond_val);
1706 try self.emitJccLabel(.e, &else_label);
1707 }
1708
1709 const then_block = if_op.getThenBlock();
1710 try self.restoreIfArmValues(op, then_block);
1711 _ = try self.emitBlockOps(then_block, .{ .if_yield = .{
1712 .op = op,
1713 .merge_label = &merge_label,
1714 } });
1715
1716 if (if_op.getElseBlock()) |else_block| {
1717 try self.bindLabel(&else_label);
1718 try self.restoreIfArmValues(op, else_block);
1719 _ = try self.emitBlockOps(else_block, .{ .if_yield = .{
1720 .op = op,
1721 .merge_label = &merge_label,
1722 } });
1723 } else {
1724 try self.bindLabel(&else_label);
1725 }
1726
1727 try self.bindLabel(&merge_label);
1728 try self.restoreIfOutgoingValues(op);
1729 op_iter = op.next_op;
1730 continue;
1731 }
1732
1733 if (std.mem.eql(u8, name, ScfDialect.ForOp.operation_name)) {
1734 const for_op = ScfDialect.ForOp{ .op = op };
1735 const lower = for_op.getLowerBound();
1736 const upper = for_op.getUpperBound();
1737 const step = for_op.getStep();
1738
1739 const body_block = for_op.getBodyBlock();
1740 if (body_block.arguments.items.len == 0) return error.MissingInductionVariable;
1741
1742 const iv = body_block.arguments.items[0];
1743 const for_position = self.allocation_position;
1744 const entry_position = for_position + 1;
1745
1746 const num_inits = op.operands.items.len - 3;
1747 var entry_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1748 defer entry_moves.deinit(self.allocator);
1749 try self.appendCarriedValueMove(
1750 &entry_moves,
1751 lower,
1752 regalloc.PositionPoint.source(for_position),
1753 iv,
1754 entry_position,
1755 .source,
1756 );
1757 for (0..num_inits) |i| {
1758 const init_val = op.operands.items[3 + i].value;
1759 const iter_arg = body_block.arguments.items[1 + i];
1760 try self.appendCarriedValueMove(
1761 &entry_moves,
1762 init_val,
1763 regalloc.PositionPoint.source(for_position),
1764 iter_arg,
1765 entry_position,
1766 .source,
1767 );
1768 }
1769 try self.emitParallelMoves(entry_moves.items);
1770 try self.mirrorValueToSlotIfReloaded(iv, try self.arrivalPlaceFor(iv, entry_position, .source));
1771 for (0..num_inits) |i| {
1772 const iter_arg = body_block.arguments.items[1 + i];
1773 try self.mirrorValueToSlotIfReloaded(iter_arg, try self.arrivalPlaceFor(iter_arg, entry_position, .source));
1774 }
1775
1776 var header_label = Label{};
1777 defer header_label.deinit(self.allocator);
1778 var exit_label = Label{};
1779 defer exit_label.deinit(self.allocator);
1780
1781 try self.bindLabel(&header_label);
1782 try self.emitForGuard(iv, upper, entry_position, &exit_label);
1783
1784 const body_result = try self.emitBlockOps(body_block, .{ .for_yield = .{
1785 .body_block = body_block,
1786 .iv = iv,
1787 .step = step,
1788 .entry_position = entry_position,
1789 .header_label = &header_label,
1790 } });
1791 if (body_result == .returned) return .returned;
1792
1793 try self.bindLabel(&exit_label);
1794 try self.enterMergePosition(op);
1795
1796 var exit_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1797 defer exit_moves.deinit(self.allocator);
1798 for (0..num_inits) |i| {
1799 const result = op.getResult(i) orelse continue;
1800 if (!self.resultNeedsSettling(result)) continue;
1801 const iter_arg = body_block.arguments.items[1 + i];
1802 const source_slot = try self.slotFor(iter_arg);
1803 const result_slot = try self.slotFor(result);
1804 if (source_slot.width != result_slot.width) return error.InvalidParallelMove;
1805 try exit_moves.append(self.allocator, .{
1806 .src = try self.arrivalPlaceFor(iter_arg, entry_position, .source),
1807 .dst = try self.arrivalPlaceFor(result, self.allocation_position, .definition),
1808 });
1809 }
1810 try self.emitParallelMoves(exit_moves.items);
1811
1812 op_iter = op.next_op;
1813 continue;
1814 }
1815
1816 if (std.mem.eql(u8, name, ScfDialect.WhileOp.operation_name)) {
1817 const while_op = ScfDialect.WhileOp{ .op = op };
1818 const before_block = while_op.getBeforeBlock();
1819 const after_block = while_op.getAfterBlock();
1820
1821 const init_count = op.operands.items.len;
1822 if (init_count > max_while_carried_values) return error.TooManyWhileValues;
1823 if (before_block.arguments.items.len != init_count) return error.InvalidWhileArity;
1824 if (after_block.arguments.items.len != init_count) return error.InvalidWhileArity;
1825 if (op.results.items.len != init_count) return error.InvalidWhileArity;
1826
1827 var init_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1828 defer init_moves.deinit(self.allocator);
1829 for (0..init_count) |i| {
1830 const init_val = op.operands.items[i].value;
1831 const before_arg = before_block.arguments.items[i];
1832 try self.appendCarriedValueMove(
1833 &init_moves,
1834 init_val,
1835 regalloc.PositionPoint.source(self.allocation_position),
1836 before_arg,
1837 self.allocation_position,
1838 .source,
1839 );
1840 }
1841 try self.emitParallelMoves(init_moves.items);
1842
1843 var header_label = Label{};
1844 defer header_label.deinit(self.allocator);
1845 var exit_label = Label{};
1846 defer exit_label.deinit(self.allocator);
1847
1848 try self.emitJmpLabel(&header_label);
1849 try self.bindLabel(&header_label);
1850
1851 var cond_val: ?*ir.Value = null;
1852 var cond_args_buf: [max_while_carried_values]*ir.Value = undefined;
1853 var cond_arg_count: usize = 0;
1854 var condition_position: u32 = self.allocation_position;
1855
1856 const before_result = try self.emitBlockOps(before_block, .{ .while_condition = .{
1857 .value = &cond_val,
1858 .args = cond_args_buf[0..],
1859 .arg_count = &cond_arg_count,
1860 .position = &condition_position,
1861 } });
1862 if (before_result == .returned) return .returned;
1863
1864 const cond_value = cond_val orelse return error.MissingCondition;
1865 if (cond_arg_count != init_count) return error.InvalidWhileArity;
1866
1867 if (!try self.emitFalseBranchForConditionValue(cond_value, &exit_label)) {
1868 try self.emitCompareWithZero(cond_value);
1869 try self.emitJccLabel(.e, &exit_label);
1870 }
1871
1872 var condition_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1873 defer condition_moves.deinit(self.allocator);
1874 for (0..cond_arg_count) |i| {
1875 const cond_arg_slot = try self.slotFor(cond_args_buf[i]);
1876 const after_arg = after_block.arguments.items[i];
1877 const after_slot = self.slot_map.getPtr(after_arg) orelse return error.MissingSlot;
1878 after_slot.* = cond_arg_slot;
1879 try self.appendCarriedValueMove(
1880 &condition_moves,
1881 cond_args_buf[i],
1882 regalloc.PositionPoint.source(self.allocation_position),
1883 after_arg,
1884 self.allocation_position,
1885 .source,
1886 );
1887 }
1888 try self.emitParallelMoves(condition_moves.items);
1889
1890 const after_result = try self.emitBlockOps(after_block, .{ .while_yield = .{
1891 .before_block = before_block,
1892 .header_label = &header_label,
1893 } });
1894 if (after_result == .returned) return .returned;
1895
1896 try self.bindLabel(&exit_label);
1897 try self.enterMergePosition(op);
1898
1899 var exit_moves: std.ArrayListUnmanaged(moves.Move) = .empty;
1900 defer exit_moves.deinit(self.allocator);
1901 for (0..cond_arg_count) |i| {
1902 const result = op.getResult(i) orelse continue;
1903 if (!self.resultNeedsSettling(result)) continue;
1904 try self.appendCarriedValueMove(
1905 &exit_moves,
1906 cond_args_buf[i],
1907 regalloc.PositionPoint.source(condition_position),
1908 result,
1909 self.allocation_position,
1910 .definition,
1911 );
1912 }
1913 try self.emitParallelMoves(exit_moves.items);
1914
1915 op_iter = op.next_op;
1916 continue;
1917 }
1918
1919 try self.dispatchOp(op);
1920 op_iter = op.next_op;
1921 }
1922
1923 return switch (terminator) {
1924 .function_return, .while_condition => .fell_through,
1925 .if_yield, .for_yield, .while_yield => error.MissingYield,
1926 };
1927 }
1928
1929 fn dispatchOp(self: *Emitter, op: *ir.Operation) EmitError!void {
1930 const name = op.name.name;
1931
1932 if (std.mem.eql(u8, name, ArithDialect.ConstantOp.operation_name)) {
1933 if (scalar.shouldSkipArithConstant(op)) return;
1934 return scalar.emitArithConstant(self, op);
1935 }
1936 if (std.mem.eql(u8, name, ArithDialect.VecConstantOp.operation_name)) {
1937 return vector.emitConstant(self, op);
1938 }
1939 if (std.mem.eql(u8, name, ArithDialect.SplatOp.operation_name)) {
1940 return vector.emitSplat(self, op);
1941 }
1942 if (std.mem.eql(u8, name, ArithDialect.ExtractOp.operation_name)) {
1943 return vector.emitExtract(self, op);
1944 }
1945 if (std.mem.eql(u8, name, ArithDialect.InsertOp.operation_name)) {
1946 return vector.emitInsert(self, op);
1947 }
1948 if (std.mem.eql(u8, name, ArithDialect.VecShuffleOp.operation_name)) {
1949 return vector.emitShuffle(self, op);
1950 }
1951 if (std.mem.eql(u8, name, ArithDialect.VecCmpOp.operation_name)) {
1952 return vector.emitCmp(self, op);
1953 }
1954 if (std.mem.eql(u8, name, ArithDialect.AddOp.operation_name)) {
1955 if (try resultIsVector(op)) return vector.emitBinaryOp(self, op, .add);
1956 return scalar.emitBinaryIntOp(self, op, .add);
1957 }
1958 if (std.mem.eql(u8, name, ArithDialect.SubOp.operation_name)) {
1959 if (try resultIsVector(op)) return vector.emitBinaryOp(self, op, .sub);
1960 return scalar.emitBinaryIntOp(self, op, .sub);
1961 }
1962 if (std.mem.eql(u8, name, ArithDialect.MulOp.operation_name)) {
1963 if (try resultIsVector(op)) return vector.emitBinaryOp(self, op, .mul);
1964 return scalar.emitBinaryIntOp(self, op, .mul);
1965 }
1966 if (std.mem.eql(u8, name, ArithDialect.UmulhiOp.operation_name)) {
1967 if (try resultIsVector(op)) return vector.emitUmulhi(self, op);
1968 return scalar.emitArithUmulhi(self, op);
1969 }
1970 if (std.mem.eql(u8, name, ArithDialect.DivOp.operation_name)) {
1971 if (try resultIsVector(op)) return vector.emitBinaryOp(self, op, .div);
1972 return scalar.emitBinaryIntOp(self, op, .div);
1973 }
1974 if (std.mem.eql(u8, name, ArithDialect.RemOp.operation_name)) {
1975 return scalar.emitBinaryIntOp(self, op, .rem);
1976 }
1977 if (std.mem.eql(u8, name, ArithDialect.NegOp.operation_name)) {
1978 if (try resultIsVector(op)) return vector.emitNeg(self, op);
1979 return scalar.emitArithNeg(self, op);
1980 }
1981 if (std.mem.eql(u8, name, ArithDialect.MaxOp.operation_name)) {
1982 if (try resultIsVector(op)) return vector.emitMinMax(self, op, .max);
1983 return scalar.emitArithMax(self, op);
1984 }
1985 if (std.mem.eql(u8, name, ArithDialect.MinOp.operation_name)) {
1986 if (try resultIsVector(op)) return vector.emitMinMax(self, op, .min);
1987 return scalar.emitArithMin(self, op);
1988 }
1989 if (std.mem.eql(u8, name, ArithDialect.SqrtOp.operation_name)) {
1990 return scalar.emitArithSqrt(self, op);
1991 }
1992 if (std.mem.eql(u8, name, ArithDialect.FloorOp.operation_name)) {
1993 return scalar.emitArithLibmUnary(self, op, .floor);
1994 }
1995 if (std.mem.eql(u8, name, ArithDialect.AbsOp.operation_name)) {
1996 return scalar.emitArithAbs(self, op);
1997 }
1998 if (std.mem.eql(u8, name, ArithDialect.PopCountOp.operation_name)) {
1999 if (try resultIsVector(op)) return vector.emitPopCount(self, op);
2000 return scalar.emitArithPopCount(self, op);
2001 }
2002 if (std.mem.eql(u8, name, ArithDialect.SinOp.operation_name)) {
2003 return scalar.emitArithLibmUnary(self, op, .sin);
2004 }
2005 if (std.mem.eql(u8, name, ArithDialect.CosOp.operation_name)) {
2006 return scalar.emitArithLibmUnary(self, op, .cos);
2007 }
2008 if (std.mem.eql(u8, name, ArithDialect.TanOp.operation_name)) {
2009 return scalar.emitArithLibmUnary(self, op, .tan);
2010 }
2011 if (std.mem.eql(u8, name, ArithDialect.ExpOp.operation_name)) {
2012 return scalar.emitArithLibmUnary(self, op, .exp);
2013 }
2014 if (std.mem.eql(u8, name, ArithDialect.LogOp.operation_name)) {
2015 return scalar.emitArithLibmUnary(self, op, .log);
2016 }
2017 if (std.mem.eql(u8, name, ArithDialect.TanhOp.operation_name)) {
2018 return scalar.emitArithLibmUnary(self, op, .tanh);
2019 }
2020 if (std.mem.eql(u8, name, ArithDialect.PowOp.operation_name)) {
2021 return scalar.emitArithLibmBinary(self, op, .pow);
2022 }
2023 if (std.mem.eql(u8, name, ArithDialect.FmaOp.operation_name)) {
2024 return scalar.emitArithFma(self, op);
2025 }
2026 if (std.mem.eql(u8, name, ArithDialect.AndOp.operation_name)) {
2027 if (try resultIsVector(op)) return vector.emitBitwiseBinary(self, op, .band);
2028 return scalar.emitArithBitwiseBinary(self, op, .band);
2029 }
2030 if (std.mem.eql(u8, name, ArithDialect.OrOp.operation_name)) {
2031 if (try resultIsVector(op)) return vector.emitBitwiseBinary(self, op, .bor);
2032 return scalar.emitArithBitwiseBinary(self, op, .bor);
2033 }
2034 if (std.mem.eql(u8, name, ArithDialect.XorOp.operation_name)) {
2035 if (try resultIsVector(op)) return vector.emitBitwiseBinary(self, op, .bxor);
2036 return scalar.emitArithBitwiseBinary(self, op, .bxor);
2037 }
2038 if (std.mem.eql(u8, name, ArithDialect.NotOp.operation_name)) {
2039 if (try resultIsVector(op)) return vector.emitNot(self, op);
2040 return scalar.emitArithNot(self, op);
2041 }
2042 if (std.mem.eql(u8, name, ArithDialect.ShlOp.operation_name)) {
2043 if (try resultIsVector(op)) return vector.emitShift(self, op, .shl);
2044 return scalar.emitArithShift(self, op, .shl);
2045 }
2046 if (std.mem.eql(u8, name, ArithDialect.ShrOp.operation_name)) {
2047 if (try resultIsVector(op)) return vector.emitShift(self, op, .shr);
2048 return scalar.emitArithShift(self, op, .shr);
2049 }
2050 if (std.mem.eql(u8, name, ArithDialect.UshrOp.operation_name)) {
2051 if (try resultIsVector(op)) return vector.emitShift(self, op, .ushr);
2052 return scalar.emitArithShift(self, op, .ushr);
2053 }
2054 if (std.mem.eql(u8, name, ArithDialect.CastOp.operation_name)) {
2055 return cast.emitCast(self, op);
2056 }
2057 if (std.mem.eql(u8, name, ArithDialect.BitcastOp.operation_name)) {
2058 return cast.emitBitcast(self, op);
2059 }
2060 if (std.mem.eql(u8, name, ArithDialect.SelectOp.operation_name)) {
2061 if (try resultIsVector(op)) return vector.emitSelect(self, op);
2062 return scalar.emitArithSelect(self, op);
2063 }
2064 if (std.mem.eql(u8, name, ArithDialect.CmpOp.operation_name)) {
2065 return scalar.emitArithCmp(self, op);
2066 }
2067
2068 if (std.mem.eql(u8, name, FuncDialect.CallOp.operation_name)) {
2069 return self.emitCall(op);
2070 }
2071 if (std.mem.eql(u8, name, FuncDialect.SyscallOp.operation_name)) {
2072 return self.emitSyscall(op);
2073 }
2074
2075 if (std.mem.eql(u8, name, MemrefDialect.LoadOp.operation_name)) {
2076 return memory.emitLoad(self, op);
2077 }
2078 if (std.mem.eql(u8, name, MemrefDialect.StoreOp.operation_name)) {
2079 return memory.emitStore(self, op);
2080 }
2081 if (std.mem.eql(u8, name, MemrefDialect.AllocOp.operation_name)) {
2082 return memory.emitAlloc(self, op);
2083 }
2084 if (std.mem.eql(u8, name, MemrefDialect.AllocaOp.operation_name)) {
2085 return memory.emitAlloca(self, op);
2086 }
2087 if (std.mem.eql(u8, name, MemrefDialect.DeallocOp.operation_name)) {
2088 return memory.emitDealloc(self, op);
2089 }
2090 if (std.mem.eql(u8, name, MemrefDialect.GetGlobalOp.operation_name)) {
2091 return memory.emitGetGlobal(self, op);
2092 }
2093 if (std.mem.eql(u8, name, MemrefDialect.ViewOp.operation_name)) {
2094 return memory.emitView(self, op);
2095 }
2096 if (std.mem.eql(u8, name, MemrefDialect.AtomicLoadOp.operation_name)) {
2097 return memory.emitAtomicLoad(self, op);
2098 }
2099 if (std.mem.eql(u8, name, MemrefDialect.AtomicStoreOp.operation_name)) {
2100 return memory.emitAtomicStore(self, op);
2101 }
2102 if (std.mem.eql(u8, name, MemrefDialect.AtomicCasOp.operation_name)) {
2103 return memory.emitAtomicCas(self, op);
2104 }
2105 if (std.mem.eql(u8, name, MemrefDialect.FenceOp.operation_name)) {
2106 return memory.emitFence(self, op);
2107 }
2108
2109 if (std.mem.eql(u8, name, ArithDialect.AddoOp.operation_name)) {
2110 return scalar.emitOverflow(self, op, .add);
2111 }
2112 if (std.mem.eql(u8, name, ArithDialect.SuboOp.operation_name)) {
2113 return scalar.emitOverflow(self, op, .sub);
2114 }
2115 if (std.mem.eql(u8, name, ArithDialect.MuloOp.operation_name)) {
2116 return scalar.emitOverflow(self, op, .mul);
2117 }
2118
2119 return error.UnsupportedOperation;
2120 }
2121
2122 fn emitCall(self: *Emitter, op: *ir.Operation) EmitError!void {
2123 const call_op = FuncDialect.CallOp{ .op = op };
2124 const callee = call_op.getCallee() orelse return error.MissingCallee;
2125 if (op.results.items.len > abi.max_result_count) return error.TooManyResults;
2126 if (op.results.items.len > 1) return self.emitProductCall(op, callee);
2127
2128 const arg_count = op.operands.items.len;
2129 var uses_sret = false;
2130 var sret_slot: ?Slot = null;
2131
2132 if (op.getResult(0)) |result_val| {
2133 const type_name = result_val.type.getDialectTypeName() orelse return error.UnsupportedType;
2134 if (arith.parseVectorTypeName(type_name) != null) {
2135 const vec_slot = try self.vectorSlotFor(result_val);
2136 uses_sret = true;
2137 sret_slot = vec_slot.base;
2138 }
2139 }
2140
2141 const total_args: usize = arg_count + @as(usize, @intFromBool(uses_sret));
2142 const args = try self.allocator.alloc(ExternArg, total_args);
2143 defer self.allocator.free(args);
2144
2145 var arg_index: usize = 0;
2146 if (uses_sret) {
2147 const slot = sret_slot orelse return error.MissingSlot;
2148 args[arg_index] = .{ .type_name = "arith.index", .source = .{ .addr_of_slot = slot } };
2149 arg_index += 1;
2150 }
2151
2152 for (op.operands.items) |operand| {
2153 const arg_val = operand.value;
2154 const type_name = arg_val.type.getDialectTypeName() orelse return error.UnsupportedType;
2155 args[arg_index] = .{ .type_name = type_name, .source = try self.callArgSourceFor(arg_val) };
2156 arg_index += 1;
2157 }
2158
2159 var results: [1]ExternResult = undefined;
2160 var result_count: usize = 0;
2161 if (!uses_sret) {
2162 if (op.getResult(0)) |result_val| {
2163 const type_name = result_val.type.getDialectTypeName() orelse return error.UnsupportedType;
2164 results[0] = .{ .type_name = type_name, .slot = self.callResultSlot(result_val) };
2165 result_count = 1;
2166 }
2167 }
2168
2169 try call_plan.emitExtern(self, callee, args, results[0..result_count]);
2170 if (!uses_sret) {
2171 if (op.getResult(0)) |result_val| {
2172 if (self.registerHomeForPhase(result_val, .definition) != null) {
2173 try self.storeFrom(result_val, .rax);
2174 }
2175 }
2176 }
2177 }
2178
2179 /// Where the call plan settles a single scalar result, or null to leave it in rax.
2180 ///
2181 /// Two results want nothing written to the frame. One the allocator gave a register home:
2182 /// `emitCall` moves rax into that home right after the call, and a later range end spills
2183 /// the home to the slot at the point the spill belongs, so writing the slot here as well
2184 /// would be the same number stored twice. One nothing reads at all, which was given no slot.
2185 ///
2186 /// A float result with an XMM home still takes its slot. The settle after the call only
2187 /// knows how to move a general register, so the slot is how that value reaches its home.
2188 fn callResultSlot(self: *Emitter, value: *ir.Value) ?Slot {
2189 if (self.registerHomeForPhase(value, .definition) != null) return null;
2190 return self.slotForOptional(value);
2191 }
2192
2193 /// Calls a function with several scalar results and settles each result in its home.
2194 /// Results reach their slots inside the call plan, before volatile registers are restored.
2195 fn emitProductCall(self: *Emitter, op: *ir.Operation, callee: []const u8) EmitError!void {
2196 const result_count = op.results.items.len;
2197 std.debug.assert(result_count > 1);
2198 std.debug.assert(result_count <= abi.max_result_count);
2199 var results: [abi.max_result_count]ExternResult = undefined;
2200 const record = abi.returnsThroughRecord(result_count);
2201 for (op.results.items, 0..) |*result, i| {
2202 if (try self.vectorTypeInfoFromType(result.type) != null) return error.UnsupportedType;
2203 const type_name = result.type.getDialectTypeName() orelse return error.UnsupportedType;
2204 const slot: ?Slot = if (record) try self.slotFor(result) else self.slotForOptional(result);
2205 if (slot == null) std.debug.assert(result.hasNoUses());
2206 results[i] = .{ .type_name = type_name, .slot = slot };
2207 }
2208
2209 const hidden: usize = @intFromBool(record);
2210 const args = try self.allocator.alloc(ExternArg, op.operands.items.len + hidden);
2211 defer self.allocator.free(args);
2212 if (hidden != 0) {
2213 const record_slot = results[0].slot.?;
2214 args[0] = .{ .type_name = "arith.index", .source = .{ .addr_of_slot = record_slot } };
2215 }
2216 for (op.operands.items, args[hidden..]) |operand, *arg| {
2217 const value = operand.value;
2218 const type_name = value.type.getDialectTypeName() orelse return error.UnsupportedType;
2219 arg.* = .{ .type_name = type_name, .source = try self.callArgSourceFor(value) };
2220 }
2221
2222 try call_plan.emitExtern(self, callee, args, results[0..result_count]);
2223 for (op.results.items, results[0..result_count]) |*result, settled| {
2224 const slot = settled.slot orelse continue;
2225 if (self.registerHomeForPhase(result, .definition)) |home| {
2226 try self.loadSlot(slot, home);
2227 } else if (self.xmmHomeForPhase(result, .definition)) |home| {
2228 try self.loadSlotXmm(slot, home);
2229 }
2230 }
2231 }
2232
2233 /// Places every operand in the register the kernel reads it from, enters the kernel, and
2234 /// takes the kernel's answer out of rax.
2235 ///
2236 /// The placement is one parallel move, the way a call settles its arguments, so an operand
2237 /// already living in another operand's destination survives the trip in. Every operand must
2238 /// be a 64-bit integer: the kernel reads whole registers, and a narrower value would leave
2239 /// the upper half of an argument register holding whatever the last instruction put there.
2240 fn emitSyscall(self: *Emitter, op: *ir.Operation) EmitError!void {
2241 const operand_count = op.operands.items.len;
2242 if (operand_count == 0) return error.MissingOperand;
2243 if (operand_count > syscall_operand_regs.len) return error.TooManyArguments;
2244
2245 var placements: [syscall_operand_regs.len]moves.Move = undefined;
2246 const destinations = syscall_operand_regs[0..operand_count];
2247 for (op.operands.items, destinations, placements[0..operand_count]) |operand, destination, *placement| {
2248 try self.requireSyscallWord(operand.value);
2249 placement.* = .{
2250 .src = try self.placeFor(operand.value),
2251 .dst = .{ .reg = destination },
2252 };
2253 }
2254
2255 try self.emitParallelMoves(placements[0..operand_count]);
2256 try self.emitEncoding(encoding.syscall());
2257
2258 const result = op.getResult(0) orelse return error.MissingResult;
2259 try self.requireSyscallWord(result);
2260 try self.storeFrom(result, regalloc.syscall_number_gpr);
2261 }
2262
2263 /// Refuses a syscall operand or result that is not a 64-bit integer, by name rather than by
2264 /// silently widening it.
2265 fn requireSyscallWord(self: *Emitter, value: *ir.Value) EmitError!void {
2266 const type_name = value.type.getDialectTypeName() orelse return error.UnsupportedType;
2267 const info = try self.typeInfoFromName(type_name);
2268 if (info.is_float or info.width != 64) return error.UnsupportedType;
2269 }
2270
2271 fn emitReturn(self: *Emitter, op: *ir.Operation) EmitError!void {
2272 const count = op.operands.items.len;
2273 if (count > abi.max_result_count) return error.TooManyResults;
2274 if ((count > 1 or self.result_count > 1) and count != self.result_count) {
2275 return error.ResultCountMismatch;
2276 }
2277 if (self.sret_info) |sret| {
2278 switch (sret) {
2279 .vector => try self.emitVectorReturn(op),
2280 .record => |record_count| {
2281 std.debug.assert(record_count == count);
2282 try self.emitRecordReturn(op);
2283 },
2284 }
2285 } else if (count == 1) {
2286 try self.emitScalarReturn(op.operands.items[0].value);
2287 } else if (count > 1) {
2288 try self.emitRegisterResults(op);
2289 }
2290
2291 try self.emitEpilogue();
2292 self.saw_return = true;
2293 }
2294
2295 fn emitVectorReturn(self: *Emitter, op: *ir.Operation) EmitError!void {
2296 if (op.operands.items.len == 0) return error.MissingOperand;
2297 const vec = try self.vectorSlotFor(op.operands.items[0].value);
2298 const sret_slot = self.sret_slot orelse return error.MissingSlot;
2299 try self.loadSlot(sret_slot, .rax);
2300
2301 var lane_index: usize = 0;
2302 while (lane_index < vec.lanes) : (lane_index += 1) {
2303 const lane = slot_layout.laneSlot(vec.base, lane_index);
2304 const mem = Mem.baseDisp(.rax, slot_layout.laneDisplacement(vec.base, lane_index));
2305 if (vec.is_float) {
2306 try self.loadSlotXmm(lane, .xmm0);
2307 try self.storeMemoryXmm(mem, lane.width, .xmm0);
2308 } else {
2309 try self.loadSlot(lane, .rcx);
2310 try self.storeMemory(mem, lane.width, .rcx);
2311 }
2312 }
2313 }
2314
2315 fn emitScalarReturn(self: *Emitter, value: *ir.Value) EmitError!void {
2316 const type_name = value.type.getDialectTypeName() orelse return error.UnsupportedType;
2317 if (std.mem.eql(u8, type_name, "arith.f32") or std.mem.eql(u8, type_name, "arith.f64")) {
2318 try self.loadIntoXmm(value, .xmm0);
2319 return;
2320 }
2321 try self.loadInto(value, .rax);
2322 if (std.mem.eql(u8, type_name, "arith.i32")) {
2323 try self.emitEncoding(encoding.movsxdRegReg(.rax, .rax));
2324 }
2325 }
2326
2327 /// Moves a result pair into its SysV result registers as one parallel assignment.
2328 fn emitRegisterResults(self: *Emitter, op: *ir.Operation) EmitError!void {
2329 const count = op.operands.items.len;
2330 std.debug.assert(count > 1);
2331 std.debug.assert(!abi.returnsThroughRecord(count));
2332 var type_names: [abi.max_register_results][]const u8 = undefined;
2333 var locations: [abi.max_register_results]abi.ValueLocation = undefined;
2334 for (op.operands.items, 0..) |operand, i| {
2335 const operand_type = operand.value.type;
2336 type_names[i] = operand_type.getDialectTypeName() orelse return error.UnsupportedType;
2337 }
2338 abi.computeReturnLocations(type_names[0..count], locations[0..count]);
2339
2340 var parallel: [abi.max_register_results]moves.Move = undefined;
2341 for (op.operands.items, locations[0..count], 0..) |operand, location, i| {
2342 const target: moves.Place = switch (location) {
2343 .int_reg => |reg| .{ .reg = reg },
2344 .fp_reg => |reg| .{ .xmm = reg },
2345 .stack => unreachable,
2346 };
2347 parallel[i] = .{ .src = try self.placeFor(operand.value), .dst = target };
2348 }
2349 try self.emitParallelMoves(parallel[0..count]);
2350
2351 for (type_names[0..count], locations[0..count]) |type_name, location| {
2352 if (location != .int_reg or !std.mem.eql(u8, type_name, "arith.i32")) continue;
2353 try self.emitEncoding(encoding.movsxdRegReg(location.int_reg, location.int_reg));
2354 }
2355 }
2356
2357 /// Settles every result in its own slot, then copies each one into the caller's record.
2358 fn emitRecordReturn(self: *Emitter, op: *ir.Operation) EmitError!void {
2359 const count = op.operands.items.len;
2360 std.debug.assert(abi.returnsThroughRecord(count));
2361 std.debug.assert(count <= abi.max_result_count);
2362 const record = self.sret_slot orelse return error.MissingSlot;
2363
2364 var parallel: [abi.max_result_count]moves.Move = undefined;
2365 for (op.operands.items, 0..) |operand, i| {
2366 const value = operand.value;
2367 const source = try self.placeFor(value);
2368 parallel[i] = .{ .src = source, .dst = .{ .slot = try self.slotFor(value) } };
2369 }
2370 try self.emitParallelMoves(parallel[0..count]);
2371
2372 try self.loadSlot(record, .rax);
2373 for (op.operands.items, 0..) |operand, i| {
2374 const slot = try self.slotFor(operand.value);
2375 const field = Mem.baseDisp(.rax, abi.recordFieldOffset(i));
2376 if (valueIsFloatScalar(operand.value)) {
2377 try self.loadSlotXmm(slot, .xmm0);
2378 try self.storeMemoryXmm(field, slot.width, .xmm0);
2379 } else {
2380 try self.loadSlot(slot, .rcx);
2381 try self.storeMemory(field, slot.width, .rcx);
2382 }
2383 }
2384 }
2385
2386 fn emitIfYield(self: *Emitter, yield_op: *ir.Operation, if_op: *ir.Operation) EmitError!void {
2387 var parallel: std.ArrayListUnmanaged(moves.Move) = .empty;
2388 defer parallel.deinit(self.allocator);
2389 for (yield_op.operands.items, 0..) |operand, i| {
2390 const result = if_op.getResult(i) orelse return error.MissingResult;
2391 if (!self.resultNeedsSettling(result)) continue;
2392 const result_position = self.mergePosition(if_op) orelse self.allocation_position;
2393 try self.appendParallelValueMoveAtPoints(
2394 ¶llel,
2395 operand.value,
2396 regalloc.PositionPoint.source(self.allocation_position),
2397 result,
2398 regalloc.PositionPoint.definition(result_position),
2399 );
2400 }
2401 try self.emitParallelMoves(parallel.items);
2402 }
2403
2404 pub fn takeLineTable(self: *Emitter) !debug_info.LineTable {
2405 return self.line_table.finish();
2406 }
2407
2408 fn emitForGuard(self: *Emitter, iv: *ir.Value, upper: *ir.Value, entry_position: u32, exit_label: *Label) EmitError!void {
2409 const point = regalloc.PositionPoint.source(entry_position);
2410 const wide = (try self.slotFor(iv)).width != 32;
2411 const iv_place = try self.arrivalPlaceFor(iv, entry_position, .source);
2412 const upper_place = try self.placeForAtPoint(upper, point);
2413 if (self.value_location_index.valueRangeAtPoint(self.value_location_ranges.items, upper, point)) |range| {
2414 if (range.entry == .reload) try self.loadSlot(try self.slotFor(upper), range.reg);
2415 }
2416 switch (iv_place) {
2417 .reg => |iv_reg| switch (upper_place) {
2418 .reg => |upper_reg| {
2419 try self.emitEncoding(if (wide) encoding.cmpRegReg(iv_reg, upper_reg) else encoding.cmpRegReg32(iv_reg, upper_reg));
2420 },
2421 .slot => |upper_slot| {
2422 const mem = Mem.baseDisp(.rbp, upper_slot.offset);
2423 try self.emitEncoding(if (wide) encoding.cmpRegMem(iv_reg, mem) else encoding.cmpRegMem32(iv_reg, mem));
2424 },
2425 .xmm => return error.UnsupportedType,
2426 },
2427 .slot => |iv_slot| switch (upper_place) {
2428 .reg => |upper_reg| {
2429 const mem = Mem.baseDisp(.rbp, iv_slot.offset);
2430 try self.emitEncoding(if (wide) encoding.cmpMemReg(mem, upper_reg) else encoding.cmpMemReg32(mem, upper_reg));
2431 },
2432 .slot => |upper_slot| {
2433 const scratch = self.scratchAt(entry_position, &.{}) orelse return error.NoScratchRegister;
2434 try self.loadSlot(iv_slot, scratch);
2435 const mem = Mem.baseDisp(.rbp, upper_slot.offset);
2436 try self.emitEncoding(if (wide) encoding.cmpRegMem(scratch, mem) else encoding.cmpRegMem32(scratch, mem));
2437 },
2438 .xmm => return error.UnsupportedType,
2439 },
2440 .xmm => return error.UnsupportedType,
2441 }
2442 try self.emitJccLabel(.ge, exit_label);
2443 }
2444
2445 fn emitForYield(
2446 self: *Emitter,
2447 yield_op: *ir.Operation,
2448 body_block: *ir.Block,
2449 iv: *ir.Value,
2450 step: *ir.Value,
2451 entry_position: u32,
2452 header_label: *Label,
2453 ) EmitError!void {
2454 const iter_count = body_block.arguments.items.len - 1;
2455 var parallel: std.ArrayListUnmanaged(moves.Move) = .empty;
2456 defer parallel.deinit(self.allocator);
2457 for (0..iter_count) |i| {
2458 const iter_arg = body_block.arguments.items[1 + i];
2459 const yield_val = yield_op.operands.items[i].value;
2460 try self.appendCarriedValueMove(
2461 ¶llel,
2462 yield_val,
2463 regalloc.PositionPoint.source(self.allocation_position),
2464 iter_arg,
2465 entry_position,
2466 .source,
2467 );
2468 }
2469 try self.emitParallelMoves(parallel.items);
2470 for (0..iter_count) |i| {
2471 const iter_arg = body_block.arguments.items[1 + i];
2472 try self.mirrorValueToSlotIfReloaded(iter_arg, try self.arrivalPlaceFor(iter_arg, entry_position, .source));
2473 }
2474
2475 try self.emitForIvIncrement(iv, step, entry_position);
2476 try self.emitJmpLabel(header_label);
2477 }
2478
2479 fn emitAddToPlace(self: *Emitter, target: moves.Place, step: moves.Place, wide: bool) EmitError!void {
2480 switch (target) {
2481 .reg => |iv_reg| switch (step) {
2482 .reg => |step_reg| {
2483 try self.emitEncoding(if (wide) encoding.addRegReg(iv_reg, step_reg) else encoding.addRegReg32(iv_reg, step_reg));
2484 },
2485 .slot => |step_slot| {
2486 const mem = Mem.baseDisp(.rbp, step_slot.offset);
2487 try self.emitEncoding(if (wide) encoding.addRegMem(iv_reg, mem) else encoding.addRegMem32(iv_reg, mem));
2488 },
2489 .xmm => return error.UnsupportedType,
2490 },
2491 .slot => |iv_slot| switch (step) {
2492 .reg => |step_reg| {
2493 const mem = Mem.baseDisp(.rbp, iv_slot.offset);
2494 try self.emitEncoding(if (wide) encoding.addMemReg(mem, step_reg) else encoding.addMemReg32(mem, step_reg));
2495 },
2496 .slot => |step_slot| {
2497 const scratch = self.scratchAt(self.allocation_position, &.{}) orelse return error.NoScratchRegister;
2498 try self.loadSlot(step_slot, scratch);
2499 const mem = Mem.baseDisp(.rbp, iv_slot.offset);
2500 try self.emitEncoding(if (wide) encoding.addMemReg(mem, scratch) else encoding.addMemReg32(mem, scratch));
2501 },
2502 .xmm => return error.UnsupportedType,
2503 },
2504 .xmm => return error.UnsupportedType,
2505 }
2506 }
2507
2508 fn emitForIvIncrement(self: *Emitter, iv: *ir.Value, step: *ir.Value, entry_position: u32) EmitError!void {
2509 const step_point = regalloc.PositionPoint.source(self.allocation_position);
2510 const current_point = regalloc.PositionPoint.source(self.allocation_position);
2511 const wide = (try self.slotFor(iv)).width != 32;
2512 const current_iv_place = try self.placeForAtPoint(iv, current_point);
2513 const step_place = try self.placeForAtPoint(step, step_point);
2514 try self.emitAddToPlace(current_iv_place, step_place, wide);
2515 const entry_iv_place = try self.arrivalPlaceFor(iv, entry_position, .source);
2516 try self.emitPlaceMove(current_iv_place, entry_iv_place);
2517 try self.mirrorValueToSlotIfReloaded(iv, entry_iv_place);
2518 }
2519
2520 fn emitWhileYield(
2521 self: *Emitter,
2522 yield_op: *ir.Operation,
2523 before_block: *ir.Block,
2524 header_label: *Label,
2525 ) EmitError!void {
2526 const iter_count = before_block.arguments.items.len;
2527 if (yield_op.operands.items.len != iter_count) return error.InvalidWhileArity;
2528
2529 var parallel: std.ArrayListUnmanaged(moves.Move) = .empty;
2530 defer parallel.deinit(self.allocator);
2531 for (0..iter_count) |i| {
2532 const iter_arg = before_block.arguments.items[i];
2533 const yield_val = yield_op.operands.items[i].value;
2534 try self.appendCarriedValueMove(
2535 ¶llel,
2536 yield_val,
2537 regalloc.PositionPoint.source(self.allocation_position),
2538 iter_arg,
2539 self.allocation_position,
2540 .source,
2541 );
2542 }
2543 try self.emitParallelMoves(parallel.items);
2544
2545 try self.emitJmpLabel(header_label);
2546 }
2547
2548 pub fn emitJmpLabel(self: *Emitter, label: *Label) EmitError!void {
2549 const offset = self.code.items.len;
2550 if (label.offset) |target| {
2551 const disp = @as(i32, @intCast(target)) - @as(i32, @intCast(offset + 5));
2552 try self.emitEncoding(encoding.jmpRel32(disp));
2553 } else {
2554 try self.emitEncoding(encoding.jmpRel32(0));
2555 const disp_offset: u32 = @intCast(offset + 1);
2556 try label.fixups.append(self.allocator, disp_offset);
2557 }
2558 }
2559
2560 pub fn emitJccLabel(self: *Emitter, cond: Condition, label: *Label) EmitError!void {
2561 const offset = self.code.items.len;
2562 if (label.offset) |target| {
2563 const disp = @as(i32, @intCast(target)) - @as(i32, @intCast(offset + 6));
2564 try self.emitEncoding(encoding.jccRel32(cond, disp));
2565 } else {
2566 try self.emitEncoding(encoding.jccRel32(cond, 0));
2567 const disp_offset: u32 = @intCast(offset + 2);
2568 try label.fixups.append(self.allocator, disp_offset);
2569 }
2570 }
2571
2572 pub fn bindLabel(self: *Emitter, label: *Label) EmitError!void {
2573 const target: u32 = @intCast(self.code.items.len);
2574 label.offset = target;
2575 for (label.fixups.items) |fixup| {
2576 const disp = @as(i32, @intCast(target)) - @as(i32, @intCast(fixup + 4));
2577 std.mem.writeInt(i32, self.code.items[fixup..][0..4], disp, .little);
2578 }
2579 label.fixups.clearRetainingCapacity();
2580 }
2581 };
2582
2583 test "x86_64 alloca payload padding honors abi alignment" {
2584 try std.testing.expectEqual(@as(usize, 0), Emitter.allocaPaddingSlots(0, 1, 8));
2585 try std.testing.expectEqual(@as(usize, 1), Emitter.allocaPaddingSlots(0, 1, 16));
2586 try std.testing.expectEqual(@as(usize, 0), Emitter.allocaPaddingSlots(0, 2, 16));
2587 try std.testing.expectEqual(@as(usize, 0), Emitter.allocaPaddingSlots(1, 1, 16));
2588 try std.testing.expectEqual(@as(usize, 1), Emitter.allocaPaddingSlots(2, 1, 16));
2589 try std.testing.expectEqual(@as(usize, 1), Emitter.allocaPaddingSlots(0, 3, 32));
2590 }
2591
2592 /// The reload one slot must emit, spelled as the bytes rather than as an
2593 /// answer a program gives.
2594 ///
2595 /// THIS PINS THE SLOT SIGNEDNESS CONTRACT. A `u8` of 200 was stored by a `movzbq`
2596 /// that read its byte as 200 and returned by a `movsbq` that read the same
2597 /// byte as -56, because the slot carried no signedness and the reload
2598 /// guessed. Only widths 8 and 16 branch, so the four rows below are the whole
2599 /// surface.
2600 ///
2601 /// THE SIGNED ROWS MATTER AS MUCH AS THE UNSIGNED ONES. They are what makes
2602 /// this a rule about the value's own type rather than a flip of the default,
2603 /// so a change that simply made every narrow reload unsigned fails here.
2604 const narrow_reload_pins = [_]struct {
2605 width: u8,
2606 ext: IntExtension,
2607 want: encoding.Encoding,
2608 }{
2609 .{ .width = 8, .ext = .unsigned, .want = encoding.movzxRegMem8(.rax, Mem.baseDisp(.rbp, -8)) },
2610 .{ .width = 8, .ext = .signed, .want = encoding.movsxRegMem8(.rax, Mem.baseDisp(.rbp, -8)) },
2611 .{ .width = 16, .ext = .unsigned, .want = encoding.movzxRegMem16(.rax, Mem.baseDisp(.rbp, -8)) },
2612 .{ .width = 16, .ext = .signed, .want = encoding.movsxRegMem16(.rax, Mem.baseDisp(.rbp, -8)) },
2613 };
2614
2615 /// The form each type hands its slot.
2616 ///
2617 /// `slotShapeFromName` used to tell `arith.i8` from `arith.u8` and answer the
2618 /// same width for both, dropping the one fact a reload needs. Each pair here
2619 /// shares a width and differs only in form, which is exactly the drop.
2620 const slot_shape_pins = [_]struct { name: []const u8, width: u8, ext: IntExtension }{
2621 .{ .name = "arith.i8", .width = 8, .ext = .signed },
2622 .{ .name = "arith.u8", .width = 8, .ext = .unsigned },
2623 .{ .name = "arith.i16", .width = 16, .ext = .signed },
2624 .{ .name = "arith.u16", .width = 16, .ext = .unsigned },
2625 .{ .name = "arith.i32", .width = 32, .ext = .signed },
2626 .{ .name = "arith.u32", .width = 32, .ext = .unsigned },
2627 .{ .name = "arith.i64", .width = 64, .ext = .signed },
2628 .{ .name = "arith.u64", .width = 64, .ext = .unsigned },
2629 };
2630
2631 test "x86_64 a narrow reload takes the form its slot was given" {
2632 const allocator = std.testing.allocator;
2633
2634 for (narrow_reload_pins) |pin| {
2635 var emitter = Emitter.init(allocator);
2636 defer emitter.deinit();
2637 try emitter.loadSlot(.{ .offset = -8, .width = pin.width, .ext = pin.ext }, .rax);
2638 try std.testing.expectEqualSlices(u8, pin.want.slice(), emitter.getCode());
2639 }
2640 }
2641
2642 test "x86_64 a type's own signedness reaches its slot" {
2643 const allocator = std.testing.allocator;
2644 var emitter = Emitter.init(allocator);
2645 defer emitter.deinit();
2646
2647 for (slot_shape_pins) |pin| {
2648 const shape = try emitter.slotShapeFromName(pin.name);
2649 try std.testing.expectEqual(pin.width, shape.width);
2650 try std.testing.expectEqual(pin.ext, shape.ext);
2651 }
2652 }
2653
2654 test "x86_64 emit float add" {
2655 const allocator = std.testing.allocator;
2656
2657 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2658 defer ctx.deinit(allocator);
2659 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2660
2661 const loc = ir.Location.getUnknown();
2662 const f32_type = try ArithDialect.getScalarType(&ctx, .f32);
2663
2664 const func = try FuncDialect.FuncOp.create(&ctx, loc, "fadd", &.{}, &.{f32_type});
2665 const entry = func.getEntryBlock();
2666
2667 const c1 = try ArithDialect.ConstantOp.createFloat(&ctx, loc, f32_type, 1.5);
2668 const c2 = try ArithDialect.ConstantOp.createFloat(&ctx, loc, f32_type, 2.5);
2669 const add = try ArithDialect.AddOp.create(&ctx, loc, c1.getResult(), c2.getResult());
2670 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{add.getResult()});
2671
2672 try entry.addOperation(c1.op);
2673 try entry.addOperation(c2.op);
2674 try entry.addOperation(add.op);
2675 try entry.addOperation(ret.op);
2676
2677 var emitter = Emitter.init(allocator);
2678 defer emitter.deinit();
2679
2680 try emitter.emitFunction(func.op);
2681 try std.testing.expect(emitter.getCode().len > 0);
2682 }
2683
2684 test "x86_64 register allocation engages only for eligible integer functions" {
2685 const allocator = std.testing.allocator;
2686
2687 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2688 defer ctx.deinit(allocator);
2689 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2690
2691 const loc = ir.Location.getUnknown();
2692 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2693
2694 const eligible = try FuncDialect.FuncOp.create(&ctx, loc, "ra_eligible", &.{ i64_type, i64_type }, &.{i64_type});
2695 const eligible_entry = eligible.getEntryBlock();
2696 const add = try ArithDialect.AddOp.create(&ctx, loc, eligible.getArgument(0), eligible.getArgument(1));
2697 try eligible_entry.addOperation(add.op);
2698 const mul = try ArithDialect.MulOp.create(&ctx, loc, add.getResult(), eligible.getArgument(0));
2699 try eligible_entry.addOperation(mul.op);
2700 const eligible_ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{mul.getResult()});
2701 try eligible_entry.addOperation(eligible_ret.op);
2702
2703 var emitter = Emitter.init(allocator);
2704 defer emitter.deinit();
2705 try emitter.emitFunction(eligible.op);
2706 try std.testing.expect(emitter.value_locations.count() > 0);
2707 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2708
2709 const predicate = try FuncDialect.FuncOp.create(&ctx, loc, "ra_predicate", &.{ i64_type, i64_type }, &.{i64_type});
2710 const predicate_entry = predicate.getEntryBlock();
2711 const cmp = try ArithDialect.CmpOp.create(&ctx, loc, .gt, predicate.getArgument(0), predicate.getArgument(1));
2712 try predicate_entry.addOperation(cmp.op);
2713 const one = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2714 try predicate_entry.addOperation(one.op);
2715 const zero = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, 0);
2716 try predicate_entry.addOperation(zero.op);
2717 const select = try ArithDialect.SelectOp.create(&ctx, loc, cmp.getResult(), one.getResult(), zero.getResult());
2718 try predicate_entry.addOperation(select.op);
2719 const predicate_ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{select.getResult()});
2720 try predicate_entry.addOperation(predicate_ret.op);
2721
2722 try emitter.emitFunction(predicate.op);
2723 try std.testing.expect(emitter.value_locations.get(cmp.getResult()) != null);
2724 try std.testing.expect(emitter.value_locations.get(select.getResult()) != null);
2725 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2726
2727 const f32_type = try ArithDialect.getScalarType(&ctx, .f32);
2728 const ineligible = try FuncDialect.FuncOp.create(&ctx, loc, "ra_ineligible", &.{ f32_type, f32_type }, &.{f32_type});
2729 const ineligible_entry = ineligible.getEntryBlock();
2730 const fadd = try ArithDialect.AddOp.create(&ctx, loc, ineligible.getArgument(0), ineligible.getArgument(1));
2731 try ineligible_entry.addOperation(fadd.op);
2732 const ineligible_ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{fadd.getResult()});
2733 try ineligible_entry.addOperation(ineligible_ret.op);
2734
2735 try emitter.emitFunction(ineligible.op);
2736 try std.testing.expectEqual(@as(usize, 0), emitter.reserved_callee_saved);
2737 }
2738
2739 test "x86_64 emission exposes allocator positions and planned locations" {
2740 const allocator = std.testing.allocator;
2741
2742 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2743 defer ctx.deinit(allocator);
2744 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2745
2746 const loc = ir.Location.getUnknown();
2747 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2748
2749 const func = try FuncDialect.FuncOp.create(&ctx, loc, "ra_positions", &.{ i64_type, i64_type }, &.{i64_type});
2750 const entry = func.getEntryBlock();
2751 const add = try ArithDialect.AddOp.create(&ctx, loc, func.getArgument(0), func.getArgument(1));
2752 try entry.addOperation(add.op);
2753 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{add.getResult()});
2754 try entry.addOperation(ret.op);
2755
2756 var emitter = Emitter.init(allocator);
2757 defer emitter.deinit();
2758 try emitter.emitFunction(func.op);
2759
2760 try std.testing.expectEqual(@as(u32, 1), emitter.operation_positions.get(add.op).?);
2761 try std.testing.expectEqual(@as(u32, 2), emitter.operation_positions.get(ret.op).?);
2762
2763 const arg_home = emitter.plannedValueLocationAt(func.getArgument(0), 0) orelse return error.TestFailure;
2764 try std.testing.expectEqual(arg_home, emitter.plannedValueLocationAt(func.getArgument(0), 1).?);
2765 try std.testing.expectEqual(@as(?GPR, null), emitter.plannedValueLocationAt(func.getArgument(0), 2));
2766
2767 emitter.allocation_position = 1;
2768 try std.testing.expectEqual(arg_home, emitter.plannedValueLocation(func.getArgument(0)).?);
2769 }
2770
2771 test "x86_64 planned range homes respect end phase" {
2772 const allocator = std.testing.allocator;
2773
2774 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2775 defer ctx.deinit(allocator);
2776 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2777
2778 const loc = ir.Location.getUnknown();
2779 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2780
2781 const func = try FuncDialect.FuncOp.create(&ctx, loc, "range_end_phase", &.{i64_type}, &.{i64_type});
2782 const entry = func.getEntryBlock();
2783 const constant = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, 1);
2784 try entry.addOperation(constant.op);
2785 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{constant.getResult()});
2786 try entry.addOperation(ret.op);
2787
2788 var emitter = Emitter.init(allocator);
2789 defer emitter.deinit();
2790 try emitter.collectSlotsInRegion(func.getBody());
2791
2792 const arg = func.getArgument(0);
2793 try emitter.value_locations.put(allocator, arg, .rcx);
2794 try emitter.value_locations.put(allocator, constant.getResult(), .rcx);
2795 try emitter.value_location_ranges.append(allocator, .{
2796 .value = arg,
2797 .start = 0,
2798 .end = 2,
2799 .reg = .rax,
2800 .end_phase = .source,
2801 });
2802 try emitter.value_location_ranges.append(allocator, .{
2803 .value = constant.getResult(),
2804 .start = 1,
2805 .end = 2,
2806 .reg = .rax,
2807 });
2808 try emitter.value_location_index.rebuild(allocator, emitter.value_location_ranges.items);
2809
2810 emitter.allocation_position = 1;
2811 try std.testing.expectEqual(GPR.rax, emitter.registerHomeForPhase(arg, .source).?);
2812 try std.testing.expectEqual(@as(?GPR, null), emitter.registerHomeForPhase(arg, .definition));
2813 try std.testing.expectEqual(@as(?GPR, null), emitter.registerHomeForPhase(constant.getResult(), .source));
2814 try std.testing.expectEqual(GPR.rax, emitter.registerHomeForPhase(constant.getResult(), .definition).?);
2815 }
2816
2817 test "x86_64 planned range homes spill when evicted" {
2818 const allocator = std.testing.allocator;
2819
2820 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2821 defer ctx.deinit(allocator);
2822 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2823
2824 const loc = ir.Location.getUnknown();
2825 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2826
2827 const func = try FuncDialect.FuncOp.create(&ctx, loc, "range_spill", &.{i64_type}, &.{i64_type});
2828 const entry = func.getEntryBlock();
2829 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{func.getArgument(0)});
2830 try entry.addOperation(ret.op);
2831
2832 var emitter = Emitter.init(allocator);
2833 defer emitter.deinit();
2834 try emitter.collectSlotsInRegion(func.getBody());
2835
2836 const arg = func.getArgument(0);
2837 const slot = try emitter.slotFor(arg);
2838 try emitter.value_location_ranges.append(allocator, .{
2839 .value = arg,
2840 .start = 0,
2841 .end = 1,
2842 .reg = .rbx,
2843 .exit = .spill,
2844 });
2845 try emitter.value_location_index.rebuild(allocator, emitter.value_location_ranges.items);
2846
2847 emitter.allocation_position = 0;
2848 const place = try emitter.placeFor(arg);
2849 switch (place) {
2850 .reg => |reg| try std.testing.expectEqual(GPR.rbx, reg),
2851 .xmm, .slot => return error.TestFailure,
2852 }
2853
2854 emitter.allocation_position = 1;
2855 try emitter.emitRangeEndSpills();
2856
2857 var expected: std.ArrayListUnmanaged(u8) = .empty;
2858 defer expected.deinit(allocator);
2859 try expected.appendSlice(allocator, encoding.movMemReg(Mem.baseDisp(.rbp, slot.offset), .rbx).slice());
2860 try std.testing.expectEqualSlices(u8, expected.items, emitter.getCode());
2861 }
2862
2863 test "x86_64 planned range homes reload when entered" {
2864 const allocator = std.testing.allocator;
2865
2866 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2867 defer ctx.deinit(allocator);
2868 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2869
2870 const loc = ir.Location.getUnknown();
2871 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2872
2873 const func = try FuncDialect.FuncOp.create(&ctx, loc, "range_reload", &.{i64_type}, &.{i64_type});
2874 const entry = func.getEntryBlock();
2875 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{func.getArgument(0)});
2876 try entry.addOperation(ret.op);
2877
2878 var emitter = Emitter.init(allocator);
2879 defer emitter.deinit();
2880 try emitter.collectSlotsInRegion(func.getBody());
2881
2882 const arg = func.getArgument(0);
2883 const slot = try emitter.slotFor(arg);
2884 try emitter.value_location_ranges.append(allocator, .{
2885 .value = arg,
2886 .start = 1,
2887 .end = 2,
2888 .reg = .rbx,
2889 .entry = .reload,
2890 });
2891 try emitter.value_location_index.rebuild(allocator, emitter.value_location_ranges.items);
2892
2893 emitter.allocation_position = 1;
2894 try emitter.emitRangeStartReloads();
2895
2896 var expected: std.ArrayListUnmanaged(u8) = .empty;
2897 defer expected.deinit(allocator);
2898 try expected.appendSlice(allocator, encoding.movRegMem(.rbx, Mem.baseDisp(.rbp, slot.offset)).slice());
2899 try std.testing.expectEqualSlices(u8, expected.items, emitter.getCode());
2900 }
2901
2902 test "x86_64 planned block argument homes use edge positions" {
2903 const allocator = std.testing.allocator;
2904
2905 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2906 defer ctx.deinit(allocator);
2907 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2908
2909 const loc = ir.Location.getUnknown();
2910 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2911
2912 const func = try FuncDialect.FuncOp.create(&ctx, loc, "block_arg_range", &.{i64_type}, &.{i64_type});
2913 const entry = func.getEntryBlock();
2914 var while_op = try ScfDialect.WhileOp.create(&ctx, loc, &.{func.getArgument(0)}, &.{i64_type});
2915 try entry.addOperation(while_op.op);
2916 const before = while_op.getBeforeBlock();
2917 const before_arg = before.arguments.items[0];
2918 const after = while_op.getAfterBlock();
2919 const after_arg = after.arguments.items[0];
2920 const condition = try ScfDialect.ConditionOp.create(&ctx, loc, before_arg, &.{before_arg});
2921 try before.addOperation(condition.op);
2922 const yield = try ScfDialect.YieldOp.create(&ctx, loc, &.{after_arg});
2923 try after.addOperation(yield.op);
2924 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{while_op.op.getResult(0).?});
2925 try entry.addOperation(ret.op);
2926
2927 var emitter = Emitter.init(allocator);
2928 defer emitter.deinit();
2929 try emitter.collectSlotsInRegion(func.getBody());
2930 try emitter.value_locations.put(allocator, func.getArgument(0), .rax);
2931 try emitter.value_location_ranges.append(allocator, .{
2932 .value = before_arg,
2933 .start = 1,
2934 .end = 2,
2935 .reg = .rbx,
2936 .exit = .spill,
2937 });
2938 try emitter.value_location_index.rebuild(allocator, emitter.value_location_ranges.items);
2939
2940 var parallel: std.ArrayListUnmanaged(moves.Move) = .empty;
2941 defer parallel.deinit(allocator);
2942 try emitter.appendParallelValueMoveAt(¶llel, func.getArgument(0), 0, before_arg, 1);
2943 try std.testing.expectEqual(@as(usize, 1), parallel.items.len);
2944 switch (parallel.items[0].src) {
2945 .reg => |reg| try std.testing.expectEqual(GPR.rax, reg),
2946 .xmm, .slot => return error.TestFailure,
2947 }
2948 switch (parallel.items[0].dst) {
2949 .reg => |reg| try std.testing.expectEqual(GPR.rbx, reg),
2950 .xmm, .slot => return error.TestFailure,
2951 }
2952
2953 const before_slot = try emitter.slotFor(before_arg);
2954 emitter.allocation_position = 2;
2955 try emitter.emitRangeEndSpills();
2956
2957 var expected: std.ArrayListUnmanaged(u8) = .empty;
2958 defer expected.deinit(allocator);
2959 try expected.appendSlice(allocator, encoding.movMemReg(Mem.baseDisp(.rbp, before_slot.offset), .rbx).slice());
2960 try std.testing.expectEqualSlices(u8, expected.items, emitter.getCode());
2961 }
2962
2963 test "x86_64 entry argument setup preserves parallel register semantics" {
2964 const allocator = std.testing.allocator;
2965
2966 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2967 defer ctx.deinit(allocator);
2968 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
2969
2970 const loc = ir.Location.getUnknown();
2971 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
2972
2973 const func = try FuncDialect.FuncOp.create(&ctx, loc, "entry_swap", &.{ i64_type, i64_type }, &.{i64_type});
2974 const entry = func.getEntryBlock();
2975
2976 var emitter = Emitter.init(allocator);
2977 defer emitter.deinit();
2978
2979 try emitter.collectSlotsInRegion(func.getBody());
2980 try emitter.value_locations.put(allocator, func.getArgument(0), .rsi);
2981 try emitter.value_locations.put(allocator, func.getArgument(1), .rdi);
2982
2983 try emitter.emitArgumentSpills(entry);
2984
2985 var expected: std.ArrayListUnmanaged(u8) = .empty;
2986 defer expected.deinit(allocator);
2987 try expected.appendSlice(allocator, encoding.movRegReg(.rax, .rdi).slice());
2988 try expected.appendSlice(allocator, encoding.movRegReg(.rdi, .rsi).slice());
2989 try expected.appendSlice(allocator, encoding.movRegReg(.rsi, .rax).slice());
2990
2991 try std.testing.expectEqualSlices(u8, expected.items, emitter.getCode());
2992 }
2993
2994 test "x86_64 parallel moves fall back to stack scratch when scratch registers are covered" {
2995 const allocator = std.testing.allocator;
2996
2997 var emitter = Emitter.init(allocator);
2998 defer emitter.deinit();
2999 emitter.reserveMoveScratchSlots();
3000
3001 const parallel = [_]moves.Move{
3002 .{ .src = .{ .reg = .rax }, .dst = .{ .reg = .rcx } },
3003 .{ .src = .{ .reg = .rcx }, .dst = .{ .reg = .rdx } },
3004 .{ .src = .{ .reg = .rdx }, .dst = .{ .reg = .r8 } },
3005 .{ .src = .{ .reg = .r8 }, .dst = .{ .reg = .r9 } },
3006 .{ .src = .{ .reg = .r9 }, .dst = .{ .reg = .r10 } },
3007 .{ .src = .{ .reg = .r10 }, .dst = .{ .reg = .r11 } },
3008 .{ .src = .{ .reg = .r11 }, .dst = .{ .reg = .rax } },
3009 };
3010
3011 try emitter.emitParallelMoves(¶llel);
3012 try std.testing.expect(emitter.getCode().len > 0);
3013 }
3014
3015 /// The bytes a synthesized entry point costs, as an upper bound rather than an exact figure.
3016 ///
3017 /// A program that yikes builds gets a four operation `_start`: call the entry, load the exit
3018 /// number, enter the kernel, return. That function preserves nothing, spills nothing a caller
3019 /// can see, and its whole job is twelve instructions of setup, so its text is the smallest
3020 /// honest measure of what a call site costs. It stood at 140 bytes while every call site saved
3021 /// eight caller saved registers whether or not one held anything.
3022 ///
3023 /// This is a ceiling, not a golden. A change that emits fewer bytes should lower the number
3024 /// here rather than be reported as a failure, and a change that raises it is asking a reader of
3025 /// the footprint page to budget for bytes the program does not need.
3026 const start_shape_ceiling_bytes = 64;
3027
3028 test "x86_64 a synthesized entry point costs no call site register saves" {
3029 const allocator = std.testing.allocator;
3030
3031 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3032 defer ctx.deinit(allocator);
3033 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
3034
3035 const loc = ir.Location.getUnknown();
3036 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
3037
3038 const func = try FuncDialect.FuncOp.create(&ctx, loc, "_start", &.{}, &.{});
3039 const entry = func.getEntryBlock();
3040 const call = try FuncDialect.CallOp.create(&ctx, loc, "main", &.{}, &.{i64_type});
3041 try entry.addOperation(call.op);
3042 const number = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, 60);
3043 try entry.addOperation(number.op);
3044 const exit = try FuncDialect.SyscallOp.create(
3045 &ctx,
3046 loc,
3047 number.getResult(),
3048 &.{call.getResult(0).?},
3049 i64_type,
3050 );
3051 try entry.addOperation(exit.op);
3052 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{});
3053 try entry.addOperation(ret.op);
3054
3055 var emitter = Emitter.init(allocator);
3056 defer emitter.deinit();
3057 try emitter.emitFunction(func.op);
3058
3059 const code = emitter.getCode();
3060 try std.testing.expect(code.len <= start_shape_ceiling_bytes);
3061
3062 const save_area_sub = [_]u8{ 0x48, 0x83, 0xEC, 0x40 };
3063 try std.testing.expect(std.mem.indexOf(u8, code, &save_area_sub) == null);
3064 }
3065
3066 /// Builds `_start`'s shape with the call result either read by the exit syscall or ignored.
3067 ///
3068 /// Both programs run the same call and the same syscall. The only difference is whether any
3069 /// operation names the call's result, which is the one input the slot rule reads.
3070 fn buildStartShape(ctx: *ir.Context, reads_call_result: bool) !FuncDialect.FuncOp {
3071 const loc = ir.Location.getUnknown();
3072 const i64_type = try ArithDialect.getScalarType(ctx, .i64);
3073
3074 const func = try FuncDialect.FuncOp.create(ctx, loc, "_start", &.{}, &.{});
3075 const entry = func.getEntryBlock();
3076 const call = try FuncDialect.CallOp.create(ctx, loc, "main", &.{}, &.{i64_type});
3077 try entry.addOperation(call.op);
3078 const number = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 60);
3079 try entry.addOperation(number.op);
3080 const status = if (reads_call_result) call.getResult(0).? else number.getResult();
3081 const exit = try FuncDialect.SyscallOp.create(ctx, loc, number.getResult(), &.{status}, i64_type);
3082 try entry.addOperation(exit.op);
3083 const ret = try FuncDialect.ReturnOp.create(ctx, loc, &.{});
3084 try entry.addOperation(ret.op);
3085 return func;
3086 }
3087
3088 test "x86_64 a call result nothing reads gets no frame slot and no store" {
3089 const allocator = std.testing.allocator;
3090
3091 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3092 defer ctx.deinit(allocator);
3093 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
3094
3095 const ignored = try buildStartShape(&ctx, false);
3096 var ignoring = Emitter.init(allocator);
3097 defer ignoring.deinit();
3098 try ignoring.emitFunction(ignored.op);
3099 const ignoring_bytes = ignoring.getCode().len;
3100
3101 const call_op = ignored.getEntryBlock().operations.head.?;
3102 const dead = &(@as(*ir.Operation, @ptrCast(@alignCast(call_op)))).results.items[0];
3103 try std.testing.expect(dead.hasNoUses());
3104 try std.testing.expect(ignoring.slotForOptional(dead) == null);
3105
3106 const read = try buildStartShape(&ctx, true);
3107 var reading = Emitter.init(allocator);
3108 defer reading.deinit();
3109 try reading.emitFunction(read.op);
3110
3111 const read_call = read.getEntryBlock().operations.head.?;
3112 const live = &(@as(*ir.Operation, @ptrCast(@alignCast(read_call)))).results.items[0];
3113 try std.testing.expect(!live.hasNoUses());
3114 const settled = reading.slotForOptional(live) != null or
3115 reading.registerHomeForPhase(live, .definition) != null;
3116 try std.testing.expect(settled);
3117
3118 try std.testing.expect(ignoring_bytes < reading.getCode().len);
3119 }
3120
3121 /// Builds a function that exits with a constant, optionally computing a second value first
3122 /// that nothing reads. The dead value is an addition, so the shape covers a folded constant
3123 /// and an arithmetic result that has to be computed before it can be thrown away.
3124 fn buildDeadArithShape(ctx: *ir.Context, computes_dead_value: bool) !FuncDialect.FuncOp {
3125 const loc = ir.Location.getUnknown();
3126 const i64_type = try ArithDialect.getScalarType(ctx, .i64);
3127
3128 const func = try FuncDialect.FuncOp.create(ctx, loc, "_start", &.{}, &.{});
3129 const entry = func.getEntryBlock();
3130 const status = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 0);
3131 try entry.addOperation(status.op);
3132 if (computes_dead_value) {
3133 const left = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 111);
3134 try entry.addOperation(left.op);
3135 const right = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 222);
3136 try entry.addOperation(right.op);
3137 const sum = try ArithDialect.AddOp.create(ctx, loc, left.getResult(), right.getResult());
3138 try entry.addOperation(sum.op);
3139 }
3140 const number = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 60);
3141 try entry.addOperation(number.op);
3142 const exit = try FuncDialect.SyscallOp.create(ctx, loc, number.getResult(), &.{status.getResult()}, i64_type);
3143 try entry.addOperation(exit.op);
3144 const ret = try FuncDialect.ReturnOp.create(ctx, loc, &.{});
3145 try entry.addOperation(ret.op);
3146 return func;
3147 }
3148
3149 test "x86_64 an arithmetic result nothing reads costs no byte and no slot" {
3150 const allocator = std.testing.allocator;
3151
3152 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3153 defer ctx.deinit(allocator);
3154 try @import("../../dialects/root.zig").registerAllDialects(&ctx);
3155
3156 const bare = try buildDeadArithShape(&ctx, false);
3157 var without = Emitter.init(allocator);
3158 defer without.deinit();
3159 try without.emitFunction(bare.op);
3160
3161 const burdened = try buildDeadArithShape(&ctx, true);
3162 var with = Emitter.init(allocator);
3163 defer with.deinit();
3164 try with.emitFunction(burdened.op);
3165
3166 try std.testing.expectEqual(without.getCode().len, with.getCode().len);
3167 try std.testing.expectEqual(@as(usize, 3), with.omitted_ops.count());
3168 try std.testing.expectEqual(@as(usize, 0), without.omitted_ops.count());
3169
3170 var block_ops = burdened.getEntryBlock().operations.head;
3171 var slots_for_dead: usize = 0;
3172 while (block_ops) |op_ptr| {
3173 const op: *ir.Operation = @ptrCast(@alignCast(op_ptr));
3174 if (with.omitted_ops.contains(op)) {
3175 for (op.results.items) |*result| {
3176 if (with.slotForOptional(result) != null) slots_for_dead += 1;
3177 }
3178 }
3179 block_ops = op.next_op;
3180 }
3181 try std.testing.expectEqual(@as(usize, 0), slots_for_dead);
3182 }
3183
3184 /// Builds one function whose body is a single `scf.while` carrying `count`
3185 /// values, and emits it. This is the shape `max_while_carried_values` bounds,
3186 /// and the whole of what a test needs to ask which side of the figure a
3187 /// program falls on.
3188 fn emitWhileCarrying(allocator: std.mem.Allocator, count: usize) !void {
3189 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3190 defer ctx.deinit(allocator);
3191 try dialects.registerAllDialects(&ctx);
3192
3193 const loc = ir.Location.getUnknown();
3194 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
3195
3196 const func = try FuncDialect.FuncOp.create(&ctx, loc, "carry", &.{i64_type}, &.{i64_type});
3197 const entry = func.getEntryBlock();
3198
3199 var inits: std.ArrayListUnmanaged(*ir.Value) = .empty;
3200 defer inits.deinit(allocator);
3201 var result_types: std.ArrayListUnmanaged(ir.Type) = .empty;
3202 defer result_types.deinit(allocator);
3203 for (0..count) |_| {
3204 try inits.append(allocator, func.getArgument(0));
3205 try result_types.append(allocator, i64_type);
3206 }
3207
3208 var while_op = try ScfDialect.WhileOp.create(&ctx, loc, inits.items, result_types.items);
3209 try entry.addOperation(while_op.op);
3210
3211 const before = while_op.getBeforeBlock();
3212 const after = while_op.getAfterBlock();
3213 const condition = try ScfDialect.ConditionOp.create(
3214 &ctx,
3215 loc,
3216 before.arguments.items[0],
3217 before.arguments.items,
3218 );
3219 try before.addOperation(condition.op);
3220 const yield = try ScfDialect.YieldOp.create(&ctx, loc, after.arguments.items);
3221 try after.addOperation(yield.op);
3222 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{while_op.op.getResult(0).?});
3223 try entry.addOperation(ret.op);
3224
3225 var emitter = Emitter.init(allocator);
3226 defer emitter.deinit();
3227 try emitter.emitFunction(func.op);
3228 }
3229
3230 test "x86_64 a while that outgrows the carried value figure is refused by that figure's name" {
3231 const allocator = std.testing.allocator;
3232
3233 try emitWhileCarrying(allocator, max_while_carried_values);
3234 try std.testing.expectError(
3235 error.TooManyWhileValues,
3236 emitWhileCarrying(allocator, max_while_carried_values + 1),
3237 );
3238 }