1const std = @import("std");
2const mem = std.mem;
3const Allocator = std.mem.Allocator;
4const assert = std.debug.assert;
5
6const CodeGen = @This();
7const link = @import("../../link.zig");
8const Spork8 = link.File.Spork8;
9const Zcu = @import("../../Zcu.zig");
10const InternPool = @import("../../InternPool.zig");
11const Air = @import("../../Air.zig");
12const Liveness = Air.Liveness;
13const Mir = @import("Mir.zig");
14
15air: Air,
16liveness: Liveness,
17gpa: Allocator,
18pt: Zcu.PerThread,
19owner_nav: InternPool.Nav.Index,
20func_index: InternPool.Index,
21mir_instructions: std.MultiArrayList(Mir.Inst),
22/// Contains extra data for MIR
23mir_extra: std.ArrayListUnmanaged(u32),
24
25pub fn legalizeFeatures(_: *const std.Target) *const Air.Legalize.Features {
26 return comptime &.initMany(&.{
27 .expand_bit_cast_safe,
28 .expand_int_cast_safe,
29 .expand_int_from_float_safe,
30 .expand_int_from_float_optimized_safe,
31 .expand_add_safe,
32 .expand_sub_safe,
33 .expand_mul_safe,
34
35 .expand_packed_load,
36 .expand_packed_store,
37 .expand_packed_agg_field_val,
38 .expand_packed_aggregate_init,
39 .expand_array_to_vector,
40
41 .scalarize_add,
42 .scalarize_add_optimized,
43 .scalarize_add_wrap,
44 .scalarize_add_sat,
45 .scalarize_sub,
46 .scalarize_sub_optimized,
47 .scalarize_sub_wrap,
48 .scalarize_sub_sat,
49 .scalarize_mul,
50 .scalarize_mul_optimized,
51 .scalarize_mul_wrap,
52 .scalarize_mul_sat,
53 .scalarize_div_float,
54 .scalarize_div_float_optimized,
55 .scalarize_div_trunc,
56 .scalarize_div_trunc_optimized,
57 .scalarize_div_floor,
58 .scalarize_div_floor_optimized,
59 .scalarize_div_ceil,
60 .scalarize_div_ceil_optimized,
61 .scalarize_div_exact,
62 .scalarize_div_exact_optimized,
63 .scalarize_rem,
64 .scalarize_rem_optimized,
65 .scalarize_mod,
66 .scalarize_mod_optimized,
67 .scalarize_max,
68 .scalarize_min,
69 .scalarize_add_with_overflow,
70 .scalarize_sub_with_overflow,
71 .scalarize_mul_with_overflow,
72 .scalarize_shl_with_overflow,
73 .scalarize_bit_and,
74 .scalarize_bit_or,
75 .scalarize_shr,
76 .scalarize_shr_exact,
77 .scalarize_shl,
78 .scalarize_shl_exact,
79 .scalarize_shl_sat,
80 .scalarize_xor,
81 .scalarize_not,
82 .scalarize_clz,
83 .scalarize_ctz,
84 .scalarize_popcount,
85 .scalarize_byte_swap,
86 .scalarize_bit_reverse,
87 .scalarize_sqrt,
88 .scalarize_sin,
89 .scalarize_cos,
90 .scalarize_tan,
91 .scalarize_exp,
92 .scalarize_exp2,
93 .scalarize_log,
94 .scalarize_log2,
95 .scalarize_log10,
96 .scalarize_abs,
97 .scalarize_floor,
98 .scalarize_ceil,
99 .scalarize_round,
100 .scalarize_trunc_float,
101 .scalarize_neg,
102 .scalarize_neg_optimized,
103 .scalarize_cmp_vector,
104 .scalarize_cmp_vector_optimized,
105 .scalarize_fptrunc,
106 .scalarize_fpext,
107 .scalarize_int_cast,
108 .scalarize_ptr_cast,
109 .scalarize_ptr_from_int,
110 .scalarize_int_from_ptr,
111 .scalarize_trunc,
112 .scalarize_int_from_float,
113 .scalarize_int_from_float_optimized,
114 .scalarize_float_from_int,
115 .scalarize_reduce,
116 .scalarize_reduce_optimized,
117 .scalarize_shuffle_one,
118 .scalarize_shuffle_two,
119 .scalarize_select,
120 .scalarize_mul_add,
121
122 .scalarize_bit_cast_padded_elems,
123 });
124}
125
126pub fn generate(
127 bin_file: *link.File,
128 pt: Zcu.PerThread,
129 func_index: InternPool.Index,
130 air: *const Air,
131 liveness: *const ?Air.Liveness,
132) link.Error!Mir {
133 _ = bin_file;
134 const zcu = pt.zcu;
135 const gpa = zcu.gpa;
136 const cg = zcu.funcInfo(func_index);
137
138 var code_gen: CodeGen = .{
139 .gpa = gpa,
140 .pt = pt,
141 .air = air.*,
142 .liveness = liveness.*.?,
143 .owner_nav = cg.owner_nav,
144 .func_index = func_index,
145 .mir_instructions = .empty,
146 .mir_extra = .empty,
147 };
148 defer code_gen.deinit();
149
150 return generateInner(&code_gen) catch |err| switch (err) {
151 error.AlreadyReported,
152 error.OutOfMemory,
153 => |e| return e,
154 };
155}
156
157pub fn deinit(cg: *CodeGen) void {
158 cg.* = undefined;
159}
160
161const InnerError = error{
162 AlreadyReported,
163 OutOfMemory,
164};
165
166fn generateInner(cg: *CodeGen) InnerError!Mir {
167 // Generate MIR for function body
168 try cg.genBody(cg.air.getMainBody());
169
170 try cg.mir_extra.shrinkToLen(cg.gpa);
171
172 return .{
173 .instructions = cg.mir_instructions.toOwnedSlice(),
174 .extra = cg.mir_extra.toOwnedSliceAssert(),
175 };
176}
177
178fn genBody(cg: *CodeGen, body: []const Air.Inst.Index) InnerError!void {
179 const zcu = cg.pt.zcu;
180 const ip = &zcu.intern_pool;
181
182 for (body) |inst| {
183 if (cg.liveness.isUnused(inst) and !cg.air.mustLower(inst, ip)) continue;
184 try cg.genInst(inst);
185 }
186}
187
188fn genInst(cg: *CodeGen, inst: Air.Inst.Index) InnerError!void {
189 const air_tags = cg.air.instructions.items(.tag);
190 return switch (air_tags[@backingInt(inst)]) {
191 .inferred_alloc, .inferred_alloc_comptime => unreachable,
192
193 .add,
194 .add_sat,
195 .add_wrap,
196 .sub,
197 .sub_sat,
198 .sub_wrap,
199 .mul,
200 .mul_sat,
201 .mul_wrap,
202 .div_float,
203 .div_exact,
204 .div_trunc,
205 .div_floor,
206 .bit_and,
207 .bit_or,
208 .rem,
209 .mod,
210 .shl,
211 .shl_exact,
212 .shl_sat,
213 .shr,
214 .shr_exact,
215 .xor,
216 .max,
217 .min,
218 .mul_add,
219
220 .sqrt,
221 .sin,
222 .cos,
223 .tan,
224 .exp,
225 .exp2,
226 .log,
227 .log2,
228 .log10,
229 .floor,
230 .ceil,
231 .round,
232 .trunc_float,
233 .neg,
234
235 .abs,
236
237 .add_with_overflow,
238 .sub_with_overflow,
239 .shl_with_overflow,
240 .mul_with_overflow,
241
242 .clz,
243 .ctz,
244
245 .cmp_eq,
246 .cmp_gte,
247 .cmp_gt,
248 .cmp_lte,
249 .cmp_lt,
250 .cmp_neq,
251
252 .cmp_vector,
253
254 .array_elem_val,
255 .array_to_slice,
256 .alloc,
257 .arg,
258 .block,
259 .breakpoint,
260 .br,
261 .repeat,
262 .switch_dispatch,
263 .cond_br,
264 .fptrunc,
265 .fpext,
266 .int_from_float,
267 .float_from_int,
268 .get_union_tag,
269
270 .@"try",
271 .try_cold,
272 .try_ptr,
273 .try_ptr_cold,
274
275 .dbg_stmt,
276 .dbg_empty_stmt,
277 .dbg_inline_block,
278 .dbg_var_ptr,
279 .dbg_var_val,
280 .dbg_arg_inline,
281
282 .call,
283 .call_always_tail,
284 .call_never_tail,
285 .call_never_inline,
286
287 .is_err,
288 .is_non_err,
289
290 .is_null,
291 .is_non_null,
292 .is_null_ptr,
293 .is_non_null_ptr,
294
295 .load,
296 .loop,
297 .memset,
298 .memset_safe,
299 .not,
300 .optional_payload,
301 .optional_payload_ptr,
302 .optional_payload_ptr_set,
303 .ptr_add,
304 .ptr_sub,
305 .ptr_elem_ptr,
306 .ptr_elem_val,
307 .ret,
308 .ret_safe,
309 .ret_ptr,
310 .ret_load,
311 .splat,
312 .select,
313 .reduce,
314 .aggregate_init,
315 .union_init,
316 .prefetch,
317 .popcount,
318 .byte_swap,
319 .bit_reverse,
320
321 .slice,
322 .slice_len,
323 .slice_elem_val,
324 .slice_elem_ptr,
325 .slice_ptr,
326 .ptr_slice_len_ptr,
327 .ptr_slice_ptr_ptr,
328 .store,
329 .store_safe,
330
331 .set_union_tag,
332 .struct_field_ptr,
333 .struct_field_ptr_index_0,
334 .struct_field_ptr_index_1,
335 .struct_field_ptr_index_2,
336 .struct_field_ptr_index_3,
337 .field_parent_ptr,
338
339 .switch_br,
340 .loop_switch_br,
341 .trunc,
342
343 .wrap_optional,
344 .unwrap_errunion_payload,
345 .unwrap_errunion_payload_ptr,
346 .unwrap_errunion_err,
347 .unwrap_errunion_err_ptr,
348 .wrap_errunion_payload,
349 .wrap_errunion_err,
350 .errunion_payload_ptr_set,
351 .error_name,
352
353 .wasm_memory_size,
354 .wasm_memory_grow,
355
356 .memcpy,
357
358 .ret_addr,
359 .tag_name,
360
361 .error_set_has_value,
362 .frame_addr,
363
364 .is_err_ptr,
365 .is_non_err_ptr,
366
367 .err_return_trace,
368 .set_err_return_trace,
369 .save_err_return_trace_index,
370 .is_named_enum_value,
371 .addrspace_cast,
372 .c_va_arg,
373 .c_va_copy,
374 .c_va_end,
375 .c_va_start,
376 .memmove,
377
378 .atomic_load,
379 .atomic_store_unordered,
380 .atomic_store_monotonic,
381 .atomic_store_release,
382 .atomic_store_seq_cst,
383 .atomic_rmw,
384 .cmpxchg_weak,
385 .cmpxchg_strong,
386
387 .add_optimized,
388 .sub_optimized,
389 .mul_optimized,
390 .div_float_optimized,
391 .div_trunc_optimized,
392 .div_floor_optimized,
393 .div_exact_optimized,
394 .rem_optimized,
395 .mod_optimized,
396 .neg_optimized,
397 .cmp_lt_optimized,
398 .cmp_lte_optimized,
399 .cmp_eq_optimized,
400 .cmp_gte_optimized,
401 .cmp_gt_optimized,
402 .cmp_neq_optimized,
403 .cmp_vector_optimized,
404 .reduce_optimized,
405 .int_from_float_optimized,
406 .add_safe,
407 .sub_safe,
408 .mul_safe,
409 .div_ceil,
410 .div_ceil_optimized,
411 .bit_cast,
412 .bit_cast_safe,
413 .ptr_cast,
414 .ptr_from_int,
415 .int_from_ptr,
416 .error_cast,
417 .error_from_int,
418 .int_from_error,
419 .union_from_enum,
420 .int_cast,
421 .int_cast_safe,
422 .agg_field_val,
423 .array_to_vector,
424 .int_from_float_safe,
425 .int_from_float_optimized_safe,
426 .shuffle_one,
427 .shuffle_two,
428 .cmp_lte_errors_len,
429 .runtime_nav_ptr,
430 .spirv_runtime_array_len,
431 .legalize_vec_store_elem,
432 .legalize_vec_elem_val,
433 .legalize_compiler_rt_call,
434 => |tag| return cg.fail("TODO: implement spork8 inst: {t}", .{tag}),
435
436 .unreach => cg.airUnreachable(inst),
437 .assembly => cg.airAssembly(inst),
438 .trap => cg.airTrap(inst),
439
440 .work_item_id,
441 .work_group_size,
442 .work_group_id,
443 => unreachable,
444 };
445}
446
447fn airUnreachable(cg: *CodeGen, inst: Air.Inst.Index) InnerError!void {
448 _ = cg;
449 _ = inst;
450}
451
452fn airTrap(cg: *CodeGen, inst: Air.Inst.Index) InnerError!void {
453 _ = inst;
454 try cg.addTag(.halt);
455}
456
457fn airAssembly(cg: *CodeGen, inst: Air.Inst.Index) InnerError!void {
458 const unwrapped_asm = cg.air.unwrapAsm(inst);
459 const outputs = unwrapped_asm.outputs;
460 // const inputs = unwrapped_asm.inputs;
461
462 const zcu = cg.pt.zcu;
463 // const output_ty = cg.typeOfIndex(inst);
464
465 if (outputs.len != 0) {
466 @panic("TODO: Support assembly outputs");
467 }
468
469 var constValues: std.array_hash_map.String(u8) = .empty;
470 defer constValues.deinit(zcu.gpa);
471 {
472 var it = unwrapped_asm.iterateInputs();
473 while (it.next()) |input| {
474 const constraint = input.constraint;
475 if (!mem.eql(u8, constraint, "I")) {
476 return cg.fail("assembly constraint {q} not supported", .{constraint});
477 }
478 const operand = input.operand.toInterned() orelse {
479 return cg.fail("immediate argument to inline assembly must be compile-time value", .{});
480 };
481 const name = input.name;
482
483 const value = switch (zcu.intern_pool.indexToKey(operand)) {
484 .int => |val| v: {
485 if (val.ty != .u8_type) {
486 return cg.fail("non-u8 type used in inline assembly value: {}", .{val.ty});
487 }
488 break :v val.storage.u64;
489 },
490 else => return cg.fail("non-int operands not supported", .{}),
491 };
492
493 try constValues.put(zcu.gpa, name, @intCast(value));
494 }
495 }
496
497 {
498 var lines = mem.tokenizeScalar(u8, unwrapped_asm.source, '\n');
499 while (lines.next()) |line| {
500 var tokens = mem.tokenizeScalar(u8, line, ' ');
501 // If there's no tokens, then it must be a blank line, so just skip it.
502 const op = tokens.next() orelse continue;
503 const instType = std.meta.stringToEnum(AsmInstType, op) orelse return cg.fail("invalid asm instruction: {q}", .{op});
504 switch (instType) {
505 .LoadI => {
506 const registerString = tokens.next() orelse return cg.fail("missing register for LoadI instruction", .{});
507 const register = std.meta.stringToEnum(Register, registerString) orelse return cg.fail("invalid register: {q}", .{registerString});
508 const value = tokens.next() orelse return cg.fail("missing immediate value for LoadI", .{});
509 const intValue = v: {
510 if (mem.startsWith(u8, value, "%[")) {
511 const name = value[2 .. value.len - 1];
512 break :v constValues.get(name) orelse return cg.fail("constraint name {q} not included in constraints for inline asm", .{name});
513 } else {
514 break :v std.fmt.parseInt(u8, value, 0) catch |err|
515 return cg.fail("invalid LoadI immediate value: {t}", .{err});
516 }
517 };
518 if (register != .OutA) {
519 return cg.fail("TODO: support other variants of LoadI", .{});
520 }
521 try cg.addTagImm8(.load_i_outa, intValue);
522 },
523 else => return cg.fail("TODO: support asm instruction: {t}", .{instType}),
524 }
525 }
526 }
527}
528
529pub fn addInst(cg: *CodeGen, inst: Mir.Inst) error{OutOfMemory}!void {
530 try cg.mir_instructions.append(cg.gpa, inst);
531}
532
533pub fn addTag(cg: *CodeGen, tag: Mir.Inst.Tag) error{OutOfMemory}!void {
534 try cg.addInst(.{ .tag = tag, .data = .{ .nothing = {} } });
535}
536
537pub fn addTagImm8(cg: *CodeGen, tag: Mir.Inst.Tag, imm8: u8) error{OutOfMemory}!void {
538 try cg.addInst(.{ .tag = tag, .data = .{ .imm8 = imm8 } });
539}
540
541fn fail(cg: *CodeGen, comptime fmt: []const u8, args: anytype) error{ OutOfMemory, AlreadyReported } {
542 const zcu = cg.pt.zcu;
543 const func = zcu.funcInfo(cg.func_index);
544 return zcu.codegenFail(func.owner_nav, fmt, args);
545}
546
547fn extraLen(cg: *const CodeGen) u32 {
548 return @intCast(cg.mir_extra.items.len - cg.start_mir_extra_off);
549}
550
551const AsmInstType = enum(u8) {
552 /// Set the memory address high byte to a register value.
553 SetPageReg,
554 /// Set the memory address high byte to a constant value.
555 SetPageI,
556 /// Set the memory address low byte to a register value.
557 SetAddrReg,
558 /// Set the memory address low byte to a constant value.
559 SetAddrI,
560 /// Load a value from a constant address into a register.
561 Load,
562 /// Load a constant value into a register.
563 LoadI,
564 /// Load a value from a constant address (setting low byte only) into a register.
565 LoadP,
566 /// Load a value from the currently set memory address into a register, and increment the address n times.
567 LoadInc,
568 /// Load a value from an offset on the current stack frame into a register.
569 LoadStck,
570 /// Store a value to a constant address from a register.
571 Store,
572 /// Store a constant value into a constant address.
573 StoreI,
574 /// Store a value to a constant address (low byte only) from a register.
575 StoreP,
576 /// Store a value from the currently set memory address from a register, and increment the address n times.
577 StoreInc,
578 /// Store a value to an offset on the current stack frame, from a register.
579 StoreStck,
580 /// Store a value to an offset on the next stack frame, from a register.
581 StoreNStck,
582 /// Store a value to an offset on the previous stack frame, from a register.
583 StorePStck,
584 /// Store a constant value to an offset on the current stack frame.
585 StoreStckI,
586 /// Store a constant value to an offset on the next stack frame.
587 StoreNStckI,
588 /// Store a constant value to an offset on the previous stack frame.
589 StorePStckI,
590 /// Copy a value from one register to another register.
591 Copy,
592 /// Jump to a constant location.
593 Jump,
594 /// Jump to a register A (high byte) + register B (low byte).
595 JumpReg,
596 /// Jump to a location pointed to by memory at the current memory address (high byte first).
597 JumpMem,
598 /// Call a function.
599 Call,
600 /// Return from a function.
601 Return,
602 /// Compare A to a constant value (sets flags, but discards result).
603 CmpI,
604 /// Compare A to a constant value with bitwise AND (sets flags, but discards result).
605 CmpAndI,
606 /// Compare A to a value from memory (sets flags, but discards result).
607 Cmp,
608 /// Compare A to a value in memory with bitwise AND (sets flags, but discards result).
609 CmpAnd,
610 /// Compare A to a value from a register (sets flags, but discards result).
611 CmpReg,
612 /// Compare A to a value from a register with bitwise AND (sets flags, but discards result).
613 CmpAndReg,
614 /// Shift B left by 1.
615 ShiftL,
616 /// Shift B right by 1.
617 ShiftR,
618 /// Rotate B left by 1.
619 RotateL,
620 /// Rotate B right by 1.
621 RotateR,
622 /// Add a constant value to A.
623 AddI,
624 /// Subtract a constant value from A.
625 SubI,
626 /// Bitwise-AND A with a constant value.
627 AndI,
628 /// Add a constant value to A, without updating flags.
629 AddINF,
630 /// Subtract a constant value from A, without updating flags.
631 SubINF,
632 /// Bitwise-AND A with a constant value, without updating flags.
633 AndINF,
634 /// Add register B to A -> A.
635 AccumulateAdd,
636 /// Subtract register B from A -> A.
637 AccumulateSub,
638 /// A & B -> A.
639 AccumulateAnd,
640 /// Bitwise OR B with A -> A.
641 OrI,
642 /// Bitwise OR a constant value with A -> A.
643 XorI,
644 /// Invert register A.
645 Not,
646 /// Add a value from memory to A.
647 Add,
648 /// Subtract a value from memory from A.
649 Sub,
650 /// AND A with a value from memory.
651 And,
652 /// OR A with a value from memory.
653 Or,
654 /// XOR A with a value from memory.
655 Xor,
656 /// No-op.
657 Nop,
658 /// No-op with 1 extra clock cycle.
659 Nop1,
660 /// No-op with 2 extra clock cycles.
661 Nop2,
662 /// Halt - stop the program forever (until reset).
663 Halt,
664};
665
666const Register = enum(u8) {
667 A,
668 B,
669 C,
670 PCnt,
671 MAdr,
672 Stack,
673 OutA,
674 Shift,
675 Swap,
676};