master
1//! For each AIR instruction, we want to know:
2//! * Is the instruction unreferenced (e.g. dies immediately)?
3//! * For each of its operands, does the operand die with this instruction (e.g. is
4//! this the last reference to it)?
5//! Some instructions are special, such as:
6//! * Conditional Branches
7//! * Switch Branches
8const std = @import("std");
9const log = std.log.scoped(.liveness);
10const assert = std.debug.assert;
11const Allocator = std.mem.Allocator;
12const Log2Int = std.math.Log2Int;
13const Writer = std.Io.Writer;
14
15const Liveness = @This();
16const trace = @import("../tracy.zig").trace;
17const Air = @import("../Air.zig");
18const InternPool = @import("../InternPool.zig");
19const Zcu = @import("../Zcu.zig");
20
21pub const Verify = @import("Liveness/Verify.zig");
22
23/// This array is split into sets of 4 bits per AIR instruction.
24/// The MSB (0bX000) is whether the instruction is unreferenced.
25/// The LSB (0b000X) is the first operand, and so on, up to 3 operands. A set bit means the
26/// operand dies after this instruction.
27/// Instructions which need more data to track liveness have special handling via the
28/// `special` table.
29tomb_bits: []usize,
30/// Sparse table of specially handled instructions. The value is an index into the `extra`
31/// array. The meaning of the data depends on the AIR tag.
32/// * `cond_br` - points to a `CondBr` in `extra` at this index.
33/// * `try`, `try_ptr` - points to a `CondBr` in `extra` at this index. The error path (the block
34/// in the instruction) is considered the "else" path, and the rest of the block the "then".
35/// * `switch_br` - points to a `SwitchBr` in `extra` at this index.
36/// * `loop_switch_br` - points to a `SwitchBr` in `extra` at this index.
37/// * `block` - points to a `Block` in `extra` at this index.
38/// * `asm`, `call`, `aggregate_init` - the value is a set of bits which are the extra tomb
39/// bits of operands.
40/// The main tomb bits are still used and the extra ones are starting with the lsb of the
41/// value here.
42special: std.AutoHashMapUnmanaged(Air.Inst.Index, u32),
43/// Auxiliary data. The way this data is interpreted is determined contextually.
44extra: []const u32,
45
46/// Trailing is the set of instructions whose lifetimes end at the start of the then branch,
47/// followed by the set of instructions whose lifetimes end at the start of the else branch.
48pub const CondBr = struct {
49 then_death_count: u32,
50 else_death_count: u32,
51};
52
53/// Trailing is:
54/// * For each case in the same order as in the AIR:
55/// - case_death_count: u32
56/// - Air.Inst.Index for each `case_death_count`: set of instructions whose lifetimes
57/// end at the start of this case.
58/// * Air.Inst.Index for each `else_death_count`: set of instructions whose lifetimes
59/// end at the start of the else case.
60pub const SwitchBr = struct {
61 else_death_count: u32,
62};
63
64/// Trailing is the set of instructions which die in the block. Note that these are not additional
65/// deaths (they are all recorded as normal within the block), but backends may use this information
66/// as a more efficient way to track which instructions are still alive after a block.
67pub const Block = struct {
68 death_count: u32,
69};
70
71/// Liveness analysis runs in several passes. Each pass iterates backwards over instructions in
72/// bodies, and recurses into bodies.
73const LivenessPass = enum {
74 /// In this pass, we perform some basic analysis of loops to gain information the main pass needs.
75 /// In particular, for every `loop` and `loop_switch_br`, we track the following information:
76 /// * Every outer block which the loop body contains a `br` to.
77 /// * Every outer loop which the loop body contains a `repeat` to.
78 /// * Every operand referenced within the loop body but created outside the loop.
79 /// This gives the main analysis pass enough information to determine the full set of
80 /// instructions which need to be alive when a loop repeats. This data is TEMPORARILY stored in
81 /// `a.extra`. It is not re-added to `extra` by the main pass, since it is not useful to
82 /// backends.
83 loop_analysis,
84
85 /// This pass performs the main liveness analysis, setting up tombs and extra data while
86 /// considering control flow etc.
87 main_analysis,
88};
89
90/// Each analysis pass may wish to pass data through calls. A pointer to a `LivenessPassData(pass)`
91/// stored on the stack is passed through calls to `analyzeInst` etc.
92fn LivenessPassData(comptime pass: LivenessPass) type {
93 return switch (pass) {
94 .loop_analysis => struct {
95 /// The set of blocks which are exited with a `br` instruction at some point within this
96 /// body and which we are currently within. Also includes `loop`s which are the target
97 /// of a `repeat` instruction, and `loop_switch_br`s which are the target of a
98 /// `switch_dispatch` instruction.
99 breaks: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .empty,
100
101 /// The set of operands for which we have seen at least one usage but not their birth.
102 live_set: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .empty,
103
104 fn deinit(self: *@This(), gpa: Allocator) void {
105 self.breaks.deinit(gpa);
106 self.live_set.deinit(gpa);
107 }
108 },
109
110 .main_analysis => struct {
111 /// Every `block` and `loop` currently under analysis.
112 block_scopes: std.AutoHashMapUnmanaged(Air.Inst.Index, BlockScope) = .empty,
113
114 /// The set of instructions currently alive in the current control
115 /// flow branch.
116 live_set: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .empty,
117
118 /// The extra data initialized by the `loop_analysis` pass for this pass to consume.
119 /// Owned by this struct during this pass.
120 old_extra: std.ArrayList(u32) = .empty,
121
122 const BlockScope = struct {
123 /// If this is a `block`, these instructions are alive upon a `br` to this block.
124 /// If this is a `loop`, these instructions are alive upon a `repeat` to this block.
125 live_set: std.AutoHashMapUnmanaged(Air.Inst.Index, void),
126 };
127
128 fn deinit(self: *@This(), gpa: Allocator) void {
129 var it = self.block_scopes.valueIterator();
130 while (it.next()) |block| {
131 block.live_set.deinit(gpa);
132 }
133 self.block_scopes.deinit(gpa);
134 self.live_set.deinit(gpa);
135 self.old_extra.deinit(gpa);
136 }
137 },
138 };
139}
140
141pub fn analyze(zcu: *Zcu, air: Air, intern_pool: *InternPool) Allocator.Error!Liveness {
142 const tracy = trace(@src());
143 defer tracy.end();
144
145 const gpa = zcu.gpa;
146
147 var a: Analysis = .{
148 .gpa = gpa,
149 .zcu = zcu,
150 .air = air,
151 .tomb_bits = try gpa.alloc(
152 usize,
153 (air.instructions.len * bpi + @bitSizeOf(usize) - 1) / @bitSizeOf(usize),
154 ),
155 .extra = .{},
156 .special = .{},
157 .intern_pool = intern_pool,
158 };
159 errdefer gpa.free(a.tomb_bits);
160 errdefer a.special.deinit(gpa);
161 defer a.extra.deinit(gpa);
162
163 @memset(a.tomb_bits, 0);
164
165 const main_body = air.getMainBody();
166
167 {
168 var data: LivenessPassData(.loop_analysis) = .{};
169 defer data.deinit(gpa);
170 try analyzeBody(&a, .loop_analysis, &data, main_body);
171 }
172
173 {
174 var data: LivenessPassData(.main_analysis) = .{};
175 defer data.deinit(gpa);
176 data.old_extra = a.extra;
177 a.extra = .{};
178 try analyzeBody(&a, .main_analysis, &data, main_body);
179 assert(data.live_set.count() == 0);
180 }
181
182 return .{
183 .tomb_bits = a.tomb_bits,
184 .special = a.special,
185 .extra = try a.extra.toOwnedSlice(gpa),
186 };
187}
188
189pub fn getTombBits(l: Liveness, inst: Air.Inst.Index) Bpi {
190 const usize_index = (@intFromEnum(inst) * bpi) / @bitSizeOf(usize);
191 return @as(Bpi, @truncate(l.tomb_bits[usize_index] >>
192 @as(Log2Int(usize), @intCast((@intFromEnum(inst) % (@bitSizeOf(usize) / bpi)) * bpi))));
193}
194
195pub fn isUnused(l: Liveness, inst: Air.Inst.Index) bool {
196 const usize_index = (@intFromEnum(inst) * bpi) / @bitSizeOf(usize);
197 const mask = @as(usize, 1) <<
198 @as(Log2Int(usize), @intCast((@intFromEnum(inst) % (@bitSizeOf(usize) / bpi)) * bpi + (bpi - 1)));
199 return (l.tomb_bits[usize_index] & mask) != 0;
200}
201
202pub fn operandDies(l: Liveness, inst: Air.Inst.Index, operand: OperandInt) bool {
203 assert(operand < bpi - 1);
204 const usize_index = (@intFromEnum(inst) * bpi) / @bitSizeOf(usize);
205 const mask = @as(usize, 1) <<
206 @as(Log2Int(usize), @intCast((@intFromEnum(inst) % (@bitSizeOf(usize) / bpi)) * bpi + operand));
207 return (l.tomb_bits[usize_index] & mask) != 0;
208}
209
210/// Higher level API.
211pub const CondBrSlices = struct {
212 then_deaths: []const Air.Inst.Index,
213 else_deaths: []const Air.Inst.Index,
214};
215
216pub fn getCondBr(l: Liveness, inst: Air.Inst.Index) CondBrSlices {
217 var index: usize = l.special.get(inst) orelse return .{
218 .then_deaths = &.{},
219 .else_deaths = &.{},
220 };
221 const then_death_count = l.extra[index];
222 index += 1;
223 const else_death_count = l.extra[index];
224 index += 1;
225 const then_deaths: []const Air.Inst.Index = @ptrCast(l.extra[index..][0..then_death_count]);
226 index += then_death_count;
227 return .{
228 .then_deaths = then_deaths,
229 .else_deaths = @ptrCast(l.extra[index..][0..else_death_count]),
230 };
231}
232
233/// Indexed by case number as they appear in AIR.
234/// Else is the last element.
235pub const SwitchBrTable = struct {
236 deaths: []const []const Air.Inst.Index,
237};
238
239/// Caller owns the memory.
240pub fn getSwitchBr(l: Liveness, gpa: Allocator, inst: Air.Inst.Index, cases_len: u32) Allocator.Error!SwitchBrTable {
241 var index: usize = l.special.get(inst) orelse return .{ .deaths = &.{} };
242 const else_death_count = l.extra[index];
243 index += 1;
244
245 var deaths = try gpa.alloc([]const Air.Inst.Index, cases_len);
246 errdefer gpa.free(deaths);
247
248 var case_i: u32 = 0;
249 while (case_i < cases_len - 1) : (case_i += 1) {
250 const case_death_count: u32 = l.extra[index];
251 index += 1;
252 deaths[case_i] = @ptrCast(l.extra[index..][0..case_death_count]);
253 index += case_death_count;
254 }
255 {
256 // Else
257 deaths[case_i] = @ptrCast(l.extra[index..][0..else_death_count]);
258 }
259 return .{ .deaths = deaths };
260}
261
262/// Note that this information is technically redundant, but is useful for
263/// backends nonetheless: see `Block`.
264pub const BlockSlices = struct {
265 deaths: []const Air.Inst.Index,
266};
267
268pub fn getBlock(l: Liveness, inst: Air.Inst.Index) BlockSlices {
269 const index: usize = l.special.get(inst) orelse return .{
270 .deaths = &.{},
271 };
272 const death_count = l.extra[index];
273 const deaths: []const Air.Inst.Index = @ptrCast(l.extra[index + 1 ..][0..death_count]);
274 return .{
275 .deaths = deaths,
276 };
277}
278
279pub const LoopSlice = struct {
280 deaths: []const Air.Inst.Index,
281};
282
283pub fn deinit(l: *Liveness, gpa: Allocator) void {
284 gpa.free(l.tomb_bits);
285 gpa.free(l.extra);
286 l.special.deinit(gpa);
287 l.* = undefined;
288}
289
290pub fn iterateBigTomb(l: Liveness, inst: Air.Inst.Index) BigTomb {
291 return .{
292 .tomb_bits = l.getTombBits(inst),
293 .extra_start = l.special.get(inst) orelse 0,
294 .extra_offset = 0,
295 .extra = l.extra,
296 .bit_index = 0,
297 .reached_end = false,
298 };
299}
300
301/// How many tomb bits per AIR instruction.
302pub const bpi = 4;
303pub const Bpi = std.meta.Int(.unsigned, bpi);
304pub const OperandInt = std.math.Log2Int(Bpi);
305
306/// Useful for decoders of Liveness information.
307pub const BigTomb = struct {
308 tomb_bits: Liveness.Bpi,
309 bit_index: u32,
310 extra_start: u32,
311 extra_offset: u32,
312 extra: []const u32,
313 reached_end: bool,
314
315 /// Returns whether the next operand dies.
316 pub fn feed(bt: *BigTomb) bool {
317 if (bt.reached_end) return false;
318
319 const this_bit_index = bt.bit_index;
320 bt.bit_index += 1;
321
322 const small_tombs = bpi - 1;
323 if (this_bit_index < small_tombs) {
324 const dies = @as(u1, @truncate(bt.tomb_bits >> @as(Liveness.OperandInt, @intCast(this_bit_index)))) != 0;
325 return dies;
326 }
327
328 const big_bit_index = this_bit_index - small_tombs;
329 while (big_bit_index - bt.extra_offset * 31 >= 31) {
330 if (@as(u1, @truncate(bt.extra[bt.extra_start + bt.extra_offset] >> 31)) != 0) {
331 bt.reached_end = true;
332 return false;
333 }
334 bt.extra_offset += 1;
335 }
336 const dies = @as(u1, @truncate(bt.extra[bt.extra_start + bt.extra_offset] >>
337 @as(u5, @intCast(big_bit_index - bt.extra_offset * 31)))) != 0;
338 return dies;
339 }
340};
341
342/// In-progress data; on successful analysis converted into `Liveness`.
343const Analysis = struct {
344 gpa: Allocator,
345 zcu: *Zcu,
346 air: Air,
347 intern_pool: *InternPool,
348 tomb_bits: []usize,
349 special: std.AutoHashMapUnmanaged(Air.Inst.Index, u32),
350 extra: std.ArrayList(u32),
351
352 fn addExtra(a: *Analysis, extra: anytype) Allocator.Error!u32 {
353 const fields = std.meta.fields(@TypeOf(extra));
354 try a.extra.ensureUnusedCapacity(a.gpa, fields.len);
355 return addExtraAssumeCapacity(a, extra);
356 }
357
358 fn addExtraAssumeCapacity(a: *Analysis, extra: anytype) u32 {
359 const fields = std.meta.fields(@TypeOf(extra));
360 const result = @as(u32, @intCast(a.extra.items.len));
361 inline for (fields) |field| {
362 a.extra.appendAssumeCapacity(switch (field.type) {
363 u32 => @field(extra, field.name),
364 else => @compileError("bad field type"),
365 });
366 }
367 return result;
368 }
369};
370
371fn analyzeBody(
372 a: *Analysis,
373 comptime pass: LivenessPass,
374 data: *LivenessPassData(pass),
375 body: []const Air.Inst.Index,
376) Allocator.Error!void {
377 var i: usize = body.len;
378 while (i != 0) {
379 i -= 1;
380 const inst = body[i];
381 try analyzeInst(a, pass, data, inst);
382 }
383}
384
385fn analyzeInst(
386 a: *Analysis,
387 comptime pass: LivenessPass,
388 data: *LivenessPassData(pass),
389 inst: Air.Inst.Index,
390) Allocator.Error!void {
391 const ip = a.intern_pool;
392 const inst_tags = a.air.instructions.items(.tag);
393 const inst_datas = a.air.instructions.items(.data);
394
395 switch (inst_tags[@intFromEnum(inst)]) {
396 .add,
397 .add_safe,
398 .add_optimized,
399 .add_wrap,
400 .add_sat,
401 .sub,
402 .sub_safe,
403 .sub_optimized,
404 .sub_wrap,
405 .sub_sat,
406 .mul,
407 .mul_safe,
408 .mul_optimized,
409 .mul_wrap,
410 .mul_sat,
411 .div_float,
412 .div_float_optimized,
413 .div_trunc,
414 .div_trunc_optimized,
415 .div_floor,
416 .div_floor_optimized,
417 .div_exact,
418 .div_exact_optimized,
419 .rem,
420 .rem_optimized,
421 .mod,
422 .mod_optimized,
423 .bit_and,
424 .bit_or,
425 .xor,
426 .cmp_lt,
427 .cmp_lt_optimized,
428 .cmp_lte,
429 .cmp_lte_optimized,
430 .cmp_eq,
431 .cmp_eq_optimized,
432 .cmp_gte,
433 .cmp_gte_optimized,
434 .cmp_gt,
435 .cmp_gt_optimized,
436 .cmp_neq,
437 .cmp_neq_optimized,
438 .bool_and,
439 .bool_or,
440 .store,
441 .store_safe,
442 .array_elem_val,
443 .slice_elem_val,
444 .ptr_elem_val,
445 .shl,
446 .shl_exact,
447 .shl_sat,
448 .shr,
449 .shr_exact,
450 .atomic_store_unordered,
451 .atomic_store_monotonic,
452 .atomic_store_release,
453 .atomic_store_seq_cst,
454 .set_union_tag,
455 .min,
456 .max,
457 .memset,
458 .memset_safe,
459 .memcpy,
460 .memmove,
461 .legalize_vec_elem_val,
462 => {
463 const o = inst_datas[@intFromEnum(inst)].bin_op;
464 return analyzeOperands(a, pass, data, inst, .{ o.lhs, o.rhs, .none });
465 },
466
467 .arg,
468 .alloc,
469 .ret_ptr,
470 .breakpoint,
471 .dbg_stmt,
472 .dbg_empty_stmt,
473 .ret_addr,
474 .frame_addr,
475 .wasm_memory_size,
476 .err_return_trace,
477 .save_err_return_trace_index,
478 .runtime_nav_ptr,
479 .c_va_start,
480 .work_item_id,
481 .work_group_size,
482 .work_group_id,
483 => return analyzeOperands(a, pass, data, inst, .{ .none, .none, .none }),
484
485 .inferred_alloc, .inferred_alloc_comptime => unreachable,
486
487 .trap,
488 .unreach,
489 => return analyzeFuncEnd(a, pass, data, inst, .{ .none, .none, .none }),
490
491 .not,
492 .bitcast,
493 .load,
494 .fpext,
495 .fptrunc,
496 .intcast,
497 .intcast_safe,
498 .trunc,
499 .optional_payload,
500 .optional_payload_ptr,
501 .optional_payload_ptr_set,
502 .errunion_payload_ptr_set,
503 .wrap_optional,
504 .unwrap_errunion_payload,
505 .unwrap_errunion_err,
506 .unwrap_errunion_payload_ptr,
507 .unwrap_errunion_err_ptr,
508 .wrap_errunion_payload,
509 .wrap_errunion_err,
510 .slice_ptr,
511 .slice_len,
512 .ptr_slice_len_ptr,
513 .ptr_slice_ptr_ptr,
514 .struct_field_ptr_index_0,
515 .struct_field_ptr_index_1,
516 .struct_field_ptr_index_2,
517 .struct_field_ptr_index_3,
518 .array_to_slice,
519 .int_from_float,
520 .int_from_float_optimized,
521 .int_from_float_safe,
522 .int_from_float_optimized_safe,
523 .float_from_int,
524 .get_union_tag,
525 .clz,
526 .ctz,
527 .popcount,
528 .byte_swap,
529 .bit_reverse,
530 .splat,
531 .error_set_has_value,
532 .addrspace_cast,
533 .c_va_arg,
534 .c_va_copy,
535 .abs,
536 => {
537 const o = inst_datas[@intFromEnum(inst)].ty_op;
538 return analyzeOperands(a, pass, data, inst, .{ o.operand, .none, .none });
539 },
540
541 .is_null,
542 .is_non_null,
543 .is_null_ptr,
544 .is_non_null_ptr,
545 .is_err,
546 .is_non_err,
547 .is_err_ptr,
548 .is_non_err_ptr,
549 .is_named_enum_value,
550 .tag_name,
551 .error_name,
552 .sqrt,
553 .sin,
554 .cos,
555 .tan,
556 .exp,
557 .exp2,
558 .log,
559 .log2,
560 .log10,
561 .floor,
562 .ceil,
563 .round,
564 .trunc_float,
565 .neg,
566 .neg_optimized,
567 .cmp_lt_errors_len,
568 .set_err_return_trace,
569 .c_va_end,
570 => {
571 const operand = inst_datas[@intFromEnum(inst)].un_op;
572 return analyzeOperands(a, pass, data, inst, .{ operand, .none, .none });
573 },
574
575 .ret,
576 .ret_safe,
577 .ret_load,
578 => {
579 const operand = inst_datas[@intFromEnum(inst)].un_op;
580 return analyzeFuncEnd(a, pass, data, inst, .{ operand, .none, .none });
581 },
582
583 .add_with_overflow,
584 .sub_with_overflow,
585 .mul_with_overflow,
586 .shl_with_overflow,
587 .ptr_add,
588 .ptr_sub,
589 .ptr_elem_ptr,
590 .slice_elem_ptr,
591 .slice,
592 => {
593 const ty_pl = inst_datas[@intFromEnum(inst)].ty_pl;
594 const extra = a.air.extraData(Air.Bin, ty_pl.payload).data;
595 return analyzeOperands(a, pass, data, inst, .{ extra.lhs, extra.rhs, .none });
596 },
597
598 .dbg_var_ptr,
599 .dbg_var_val,
600 .dbg_arg_inline,
601 => {
602 const operand = inst_datas[@intFromEnum(inst)].pl_op.operand;
603 return analyzeOperands(a, pass, data, inst, .{ operand, .none, .none });
604 },
605
606 .prefetch => {
607 const prefetch = inst_datas[@intFromEnum(inst)].prefetch;
608 return analyzeOperands(a, pass, data, inst, .{ prefetch.ptr, .none, .none });
609 },
610
611 .call, .call_always_tail, .call_never_tail, .call_never_inline => {
612 const inst_data = inst_datas[@intFromEnum(inst)].pl_op;
613 const callee = inst_data.operand;
614 const extra = a.air.extraData(Air.Call, inst_data.payload);
615 const args = @as([]const Air.Inst.Ref, @ptrCast(a.air.extra.items[extra.end..][0..extra.data.args_len]));
616 if (args.len + 1 <= bpi - 1) {
617 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
618 buf[0] = callee;
619 @memcpy(buf[1..][0..args.len], args);
620 return analyzeOperands(a, pass, data, inst, buf);
621 }
622
623 var big = try AnalyzeBigOperands(pass).init(a, data, inst, args.len + 1);
624 defer big.deinit();
625 var i: usize = args.len;
626 while (i > 0) {
627 i -= 1;
628 try big.feed(args[i]);
629 }
630 try big.feed(callee);
631 return big.finish();
632 },
633 .select => {
634 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
635 const extra = a.air.extraData(Air.Bin, pl_op.payload).data;
636 return analyzeOperands(a, pass, data, inst, .{ pl_op.operand, extra.lhs, extra.rhs });
637 },
638 .shuffle_one => {
639 const unwrapped = a.air.unwrapShuffleOne(a.zcu, inst);
640 return analyzeOperands(a, pass, data, inst, .{ unwrapped.operand, .none, .none });
641 },
642 .shuffle_two => {
643 const unwrapped = a.air.unwrapShuffleTwo(a.zcu, inst);
644 return analyzeOperands(a, pass, data, inst, .{ unwrapped.operand_a, unwrapped.operand_b, .none });
645 },
646 .reduce, .reduce_optimized => {
647 const reduce = inst_datas[@intFromEnum(inst)].reduce;
648 return analyzeOperands(a, pass, data, inst, .{ reduce.operand, .none, .none });
649 },
650 .cmp_vector, .cmp_vector_optimized => {
651 const extra = a.air.extraData(Air.VectorCmp, inst_datas[@intFromEnum(inst)].ty_pl.payload).data;
652 return analyzeOperands(a, pass, data, inst, .{ extra.lhs, extra.rhs, .none });
653 },
654 .aggregate_init => {
655 const ty_pl = inst_datas[@intFromEnum(inst)].ty_pl;
656 const aggregate_ty = ty_pl.ty.toType();
657 const len = @as(usize, @intCast(aggregate_ty.arrayLenIp(ip)));
658 const elements = @as([]const Air.Inst.Ref, @ptrCast(a.air.extra.items[ty_pl.payload..][0..len]));
659
660 if (elements.len <= bpi - 1) {
661 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
662 @memcpy(buf[0..elements.len], elements);
663 return analyzeOperands(a, pass, data, inst, buf);
664 }
665
666 var big = try AnalyzeBigOperands(pass).init(a, data, inst, elements.len);
667 defer big.deinit();
668 var i: usize = elements.len;
669 while (i > 0) {
670 i -= 1;
671 try big.feed(elements[i]);
672 }
673 return big.finish();
674 },
675 .union_init => {
676 const extra = a.air.extraData(Air.UnionInit, inst_datas[@intFromEnum(inst)].ty_pl.payload).data;
677 return analyzeOperands(a, pass, data, inst, .{ extra.init, .none, .none });
678 },
679 .struct_field_ptr, .struct_field_val => {
680 const extra = a.air.extraData(Air.StructField, inst_datas[@intFromEnum(inst)].ty_pl.payload).data;
681 return analyzeOperands(a, pass, data, inst, .{ extra.struct_operand, .none, .none });
682 },
683 .field_parent_ptr => {
684 const extra = a.air.extraData(Air.FieldParentPtr, inst_datas[@intFromEnum(inst)].ty_pl.payload).data;
685 return analyzeOperands(a, pass, data, inst, .{ extra.field_ptr, .none, .none });
686 },
687 .cmpxchg_strong, .cmpxchg_weak => {
688 const extra = a.air.extraData(Air.Cmpxchg, inst_datas[@intFromEnum(inst)].ty_pl.payload).data;
689 return analyzeOperands(a, pass, data, inst, .{ extra.ptr, extra.expected_value, extra.new_value });
690 },
691 .mul_add => {
692 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
693 const extra = a.air.extraData(Air.Bin, pl_op.payload).data;
694 return analyzeOperands(a, pass, data, inst, .{ extra.lhs, extra.rhs, pl_op.operand });
695 },
696 .atomic_load => {
697 const ptr = inst_datas[@intFromEnum(inst)].atomic_load.ptr;
698 return analyzeOperands(a, pass, data, inst, .{ ptr, .none, .none });
699 },
700 .atomic_rmw => {
701 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
702 const extra = a.air.extraData(Air.AtomicRmw, pl_op.payload).data;
703 return analyzeOperands(a, pass, data, inst, .{ pl_op.operand, extra.operand, .none });
704 },
705
706 .br => return analyzeInstBr(a, pass, data, inst),
707 .repeat => return analyzeInstRepeat(a, pass, data, inst),
708 .switch_dispatch => return analyzeInstSwitchDispatch(a, pass, data, inst),
709
710 .assembly => {
711 const extra = a.air.extraData(Air.Asm, inst_datas[@intFromEnum(inst)].ty_pl.payload);
712 const outputs_len = extra.data.flags.outputs_len;
713 var extra_i: usize = extra.end;
714 const outputs = @as([]const Air.Inst.Ref, @ptrCast(a.air.extra.items[extra_i..][0..outputs_len]));
715 extra_i += outputs.len;
716 const inputs = @as([]const Air.Inst.Ref, @ptrCast(a.air.extra.items[extra_i..][0..extra.data.inputs_len]));
717 extra_i += inputs.len;
718
719 const num_operands = simple: {
720 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
721 var buf_index: usize = 0;
722 for (outputs) |output| {
723 if (output != .none) {
724 if (buf_index < buf.len) buf[buf_index] = output;
725 buf_index += 1;
726 }
727 }
728 if (buf_index + inputs.len > buf.len) {
729 break :simple buf_index + inputs.len;
730 }
731 @memcpy(buf[buf_index..][0..inputs.len], inputs);
732 return analyzeOperands(a, pass, data, inst, buf);
733 };
734
735 var big = try AnalyzeBigOperands(pass).init(a, data, inst, num_operands);
736 defer big.deinit();
737 var i: usize = inputs.len;
738 while (i > 0) {
739 i -= 1;
740 try big.feed(inputs[i]);
741 }
742 i = outputs.len;
743 while (i > 0) {
744 i -= 1;
745 if (outputs[i] != .none) {
746 try big.feed(outputs[i]);
747 }
748 }
749 return big.finish();
750 },
751
752 inline .block, .dbg_inline_block => |comptime_tag| {
753 const ty_pl = inst_datas[@intFromEnum(inst)].ty_pl;
754 const extra = a.air.extraData(switch (comptime_tag) {
755 .block => Air.Block,
756 .dbg_inline_block => Air.DbgInlineBlock,
757 else => unreachable,
758 }, ty_pl.payload);
759 return analyzeInstBlock(a, pass, data, inst, ty_pl.ty, @ptrCast(a.air.extra.items[extra.end..][0..extra.data.body_len]));
760 },
761 .loop => return analyzeInstLoop(a, pass, data, inst),
762
763 .@"try", .try_cold => return analyzeInstCondBr(a, pass, data, inst, .@"try"),
764 .try_ptr, .try_ptr_cold => return analyzeInstCondBr(a, pass, data, inst, .try_ptr),
765 .cond_br => return analyzeInstCondBr(a, pass, data, inst, .cond_br),
766 .switch_br => return analyzeInstSwitchBr(a, pass, data, inst, false),
767 .loop_switch_br => return analyzeInstSwitchBr(a, pass, data, inst, true),
768
769 .wasm_memory_grow => {
770 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
771 return analyzeOperands(a, pass, data, inst, .{ pl_op.operand, .none, .none });
772 },
773
774 .legalize_vec_store_elem => {
775 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
776 const bin = a.air.extraData(Air.Bin, pl_op.payload).data;
777 return analyzeOperands(a, pass, data, inst, .{ pl_op.operand, bin.lhs, bin.rhs });
778 },
779
780 .legalize_compiler_rt_call => {
781 const extra = a.air.extraData(Air.Call, inst_datas[@intFromEnum(inst)].legalize_compiler_rt_call.payload);
782 const args: []const Air.Inst.Ref = @ptrCast(a.air.extra.items[extra.end..][0..extra.data.args_len]);
783 if (args.len <= bpi - 1) {
784 var buf: [bpi - 1]Air.Inst.Ref = @splat(.none);
785 @memcpy(buf[0..args.len], args);
786 return analyzeOperands(a, pass, data, inst, buf);
787 }
788 var big = try AnalyzeBigOperands(pass).init(a, data, inst, args.len + 1);
789 defer big.deinit();
790 var i: usize = args.len;
791 while (i > 0) {
792 i -= 1;
793 try big.feed(args[i]);
794 }
795 return big.finish();
796 },
797 }
798}
799
800/// Every instruction should hit this (after handling any nested bodies), in every pass. In the
801/// initial pass, it is responsible for marking deaths of the (first three) operands and noticing
802/// immediate deaths.
803fn analyzeOperands(
804 a: *Analysis,
805 comptime pass: LivenessPass,
806 data: *LivenessPassData(pass),
807 inst: Air.Inst.Index,
808 operands: [bpi - 1]Air.Inst.Ref,
809) Allocator.Error!void {
810 const gpa = a.gpa;
811 const ip = a.intern_pool;
812
813 switch (pass) {
814 .loop_analysis => {
815 _ = data.live_set.remove(inst);
816
817 for (operands) |op_ref| {
818 const operand = op_ref.toIndexAllowNone() orelse continue;
819 _ = try data.live_set.put(gpa, operand, {});
820 }
821 },
822
823 .main_analysis => {
824 const usize_index = (@intFromEnum(inst) * bpi) / @bitSizeOf(usize);
825
826 // This logic must synchronize with `will_die_immediately` in `AnalyzeBigOperands.init`.
827 const immediate_death = if (data.live_set.remove(inst)) blk: {
828 log.debug("[{}] %{d}: removed from live set", .{ pass, @intFromEnum(inst) });
829 break :blk false;
830 } else blk: {
831 log.debug("[{}] %{d}: immediate death", .{ pass, @intFromEnum(inst) });
832 break :blk true;
833 };
834
835 var tomb_bits: Bpi = @as(Bpi, @intFromBool(immediate_death)) << (bpi - 1);
836
837 // If our result is unused and the instruction doesn't need to be lowered, backends will
838 // skip the lowering of this instruction, so we don't want to record uses of operands.
839 // That way, we can mark as many instructions as possible unused.
840 if (!immediate_death or a.air.mustLower(inst, ip)) {
841 // Note that it's important we iterate over the operands backwards, so that if a dying
842 // operand is used multiple times we mark its last use as its death.
843 var i = operands.len;
844 while (i > 0) {
845 i -= 1;
846 const op_ref = operands[i];
847 const operand = op_ref.toIndexAllowNone() orelse continue;
848
849 const mask = @as(Bpi, 1) << @as(OperandInt, @intCast(i));
850
851 if ((try data.live_set.fetchPut(gpa, operand, {})) == null) {
852 log.debug("[{}] %{d}: added %{d} to live set (operand dies here)", .{ pass, @intFromEnum(inst), operand });
853 tomb_bits |= mask;
854 }
855 }
856 }
857
858 a.tomb_bits[usize_index] |= @as(usize, tomb_bits) <<
859 @as(Log2Int(usize), @intCast((@intFromEnum(inst) % (@bitSizeOf(usize) / bpi)) * bpi));
860 },
861 }
862}
863
864/// Like `analyzeOperands`, but for an instruction which returns from a function, so should
865/// effectively kill every remaining live value other than its operands.
866fn analyzeFuncEnd(
867 a: *Analysis,
868 comptime pass: LivenessPass,
869 data: *LivenessPassData(pass),
870 inst: Air.Inst.Index,
871 operands: [bpi - 1]Air.Inst.Ref,
872) Allocator.Error!void {
873 switch (pass) {
874 .loop_analysis => {
875 // No operands need to be alive if we're returning from the function, so we don't need
876 // to touch `breaks` here even though this is sort of like a break to the top level.
877 },
878
879 .main_analysis => {
880 data.live_set.clearRetainingCapacity();
881 },
882 }
883
884 return analyzeOperands(a, pass, data, inst, operands);
885}
886
887fn analyzeInstBr(
888 a: *Analysis,
889 comptime pass: LivenessPass,
890 data: *LivenessPassData(pass),
891 inst: Air.Inst.Index,
892) !void {
893 const inst_datas = a.air.instructions.items(.data);
894 const br = inst_datas[@intFromEnum(inst)].br;
895 const gpa = a.gpa;
896
897 switch (pass) {
898 .loop_analysis => {
899 try data.breaks.put(gpa, br.block_inst, {});
900 },
901
902 .main_analysis => {
903 const block_scope = data.block_scopes.get(br.block_inst).?; // we should always be breaking from an enclosing block
904
905 const new_live_set = try block_scope.live_set.clone(gpa);
906 data.live_set.deinit(gpa);
907 data.live_set = new_live_set;
908 },
909 }
910
911 return analyzeOperands(a, pass, data, inst, .{ br.operand, .none, .none });
912}
913
914fn analyzeInstRepeat(
915 a: *Analysis,
916 comptime pass: LivenessPass,
917 data: *LivenessPassData(pass),
918 inst: Air.Inst.Index,
919) !void {
920 const inst_datas = a.air.instructions.items(.data);
921 const repeat = inst_datas[@intFromEnum(inst)].repeat;
922 const gpa = a.gpa;
923
924 switch (pass) {
925 .loop_analysis => {
926 try data.breaks.put(gpa, repeat.loop_inst, {});
927 },
928
929 .main_analysis => {
930 const block_scope = data.block_scopes.get(repeat.loop_inst).?; // we should always be repeating an enclosing loop
931
932 const new_live_set = try block_scope.live_set.clone(gpa);
933 data.live_set.deinit(gpa);
934 data.live_set = new_live_set;
935 },
936 }
937
938 return analyzeOperands(a, pass, data, inst, .{ .none, .none, .none });
939}
940
941fn analyzeInstSwitchDispatch(
942 a: *Analysis,
943 comptime pass: LivenessPass,
944 data: *LivenessPassData(pass),
945 inst: Air.Inst.Index,
946) !void {
947 // This happens to be identical to `analyzeInstBr`, but is separated anyway for clarity.
948
949 const inst_datas = a.air.instructions.items(.data);
950 const br = inst_datas[@intFromEnum(inst)].br;
951 const gpa = a.gpa;
952
953 switch (pass) {
954 .loop_analysis => {
955 try data.breaks.put(gpa, br.block_inst, {});
956 },
957
958 .main_analysis => {
959 const block_scope = data.block_scopes.get(br.block_inst).?; // we should always be repeating an enclosing loop
960
961 const new_live_set = try block_scope.live_set.clone(gpa);
962 data.live_set.deinit(gpa);
963 data.live_set = new_live_set;
964 },
965 }
966
967 return analyzeOperands(a, pass, data, inst, .{ br.operand, .none, .none });
968}
969
970fn analyzeInstBlock(
971 a: *Analysis,
972 comptime pass: LivenessPass,
973 data: *LivenessPassData(pass),
974 inst: Air.Inst.Index,
975 ty: Air.Inst.Ref,
976 body: []const Air.Inst.Index,
977) !void {
978 const gpa = a.gpa;
979
980 // We actually want to do `analyzeOperands` *first*, since our result logically doesn't
981 // exist until the block body ends (and we're iterating backwards)
982 try analyzeOperands(a, pass, data, inst, .{ .none, .none, .none });
983
984 switch (pass) {
985 .loop_analysis => {
986 try analyzeBody(a, pass, data, body);
987 _ = data.breaks.remove(inst);
988 },
989
990 .main_analysis => {
991 log.debug("[{}] %{f}: block live set is {f}", .{ pass, inst, fmtInstSet(&data.live_set) });
992 // We can move the live set because the body should have a noreturn
993 // instruction which overrides the set.
994 try data.block_scopes.put(gpa, inst, .{
995 .live_set = data.live_set.move(),
996 });
997 defer {
998 log.debug("[{}] %{f}: popped block scope", .{ pass, inst });
999 var scope = data.block_scopes.fetchRemove(inst).?.value;
1000 scope.live_set.deinit(gpa);
1001 }
1002
1003 log.debug("[{}] %{f}: pushed new block scope", .{ pass, inst });
1004 try analyzeBody(a, pass, data, body);
1005
1006 // If the block is noreturn, block deaths not only aren't useful, they're impossible to
1007 // find: there could be more stuff alive after the block than before it!
1008 if (!a.intern_pool.isNoReturn(ty.toType().toIntern())) {
1009 // The block kills the difference in the live sets
1010 const block_scope = data.block_scopes.get(inst).?;
1011 const num_deaths = data.live_set.count() - block_scope.live_set.count();
1012
1013 try a.extra.ensureUnusedCapacity(gpa, num_deaths + std.meta.fields(Block).len);
1014 const extra_index = a.addExtraAssumeCapacity(Block{
1015 .death_count = num_deaths,
1016 });
1017
1018 var measured_num: u32 = 0;
1019 var it = data.live_set.keyIterator();
1020 while (it.next()) |key| {
1021 const alive = key.*;
1022 if (!block_scope.live_set.contains(alive)) {
1023 // Dies in block
1024 a.extra.appendAssumeCapacity(@intFromEnum(alive));
1025 measured_num += 1;
1026 }
1027 }
1028 assert(measured_num == num_deaths); // post-live-set should be a subset of pre-live-set
1029 try a.special.put(gpa, inst, extra_index);
1030 log.debug("[{}] %{f}: block deaths are {f}", .{
1031 pass,
1032 inst,
1033 fmtInstList(@ptrCast(a.extra.items[extra_index + 1 ..][0..num_deaths])),
1034 });
1035 }
1036 },
1037 }
1038}
1039
1040fn writeLoopInfo(
1041 a: *Analysis,
1042 data: *LivenessPassData(.loop_analysis),
1043 inst: Air.Inst.Index,
1044 old_breaks: std.AutoHashMapUnmanaged(Air.Inst.Index, void),
1045 old_live: std.AutoHashMapUnmanaged(Air.Inst.Index, void),
1046) !void {
1047 const gpa = a.gpa;
1048
1049 // `loop`s are guaranteed to have at least one matching `repeat`.
1050 // Similarly, `loop_switch_br`s have a matching `switch_dispatch`.
1051 // However, we no longer care about repeats of this loop for resolving
1052 // which operands must live within it.
1053 assert(data.breaks.remove(inst));
1054
1055 const extra_index: u32 = @intCast(a.extra.items.len);
1056
1057 const num_breaks = data.breaks.count();
1058 try a.extra.ensureUnusedCapacity(gpa, 1 + num_breaks);
1059
1060 a.extra.appendAssumeCapacity(num_breaks);
1061
1062 var it = data.breaks.keyIterator();
1063 while (it.next()) |key| {
1064 const block_inst = key.*;
1065 a.extra.appendAssumeCapacity(@intFromEnum(block_inst));
1066 }
1067 log.debug("[{}] %{f}: includes breaks to {f}", .{ LivenessPass.loop_analysis, inst, fmtInstSet(&data.breaks) });
1068
1069 // Now we put the live operands from the loop body in too
1070 const num_live = data.live_set.count();
1071 try a.extra.ensureUnusedCapacity(gpa, 1 + num_live);
1072
1073 a.extra.appendAssumeCapacity(num_live);
1074 it = data.live_set.keyIterator();
1075 while (it.next()) |key| {
1076 const alive = key.*;
1077 a.extra.appendAssumeCapacity(@intFromEnum(alive));
1078 }
1079 log.debug("[{}] %{f}: maintain liveness of {f}", .{ LivenessPass.loop_analysis, inst, fmtInstSet(&data.live_set) });
1080
1081 try a.special.put(gpa, inst, extra_index);
1082
1083 // Add back operands which were previously alive
1084 it = old_live.keyIterator();
1085 while (it.next()) |key| {
1086 const alive = key.*;
1087 try data.live_set.put(gpa, alive, {});
1088 }
1089
1090 // And the same for breaks
1091 it = old_breaks.keyIterator();
1092 while (it.next()) |key| {
1093 const block_inst = key.*;
1094 try data.breaks.put(gpa, block_inst, {});
1095 }
1096}
1097
1098/// When analyzing a loop in the main pass, sets up `data.live_set` to be the set
1099/// of operands known to be alive when the loop repeats.
1100fn resolveLoopLiveSet(
1101 a: *Analysis,
1102 data: *LivenessPassData(.main_analysis),
1103 inst: Air.Inst.Index,
1104) !void {
1105 const gpa = a.gpa;
1106
1107 const extra_idx = a.special.fetchRemove(inst).?.value;
1108 const num_breaks = data.old_extra.items[extra_idx];
1109 const breaks: []const Air.Inst.Index = @ptrCast(data.old_extra.items[extra_idx + 1 ..][0..num_breaks]);
1110
1111 const num_loop_live = data.old_extra.items[extra_idx + num_breaks + 1];
1112 const loop_live: []const Air.Inst.Index = @ptrCast(data.old_extra.items[extra_idx + num_breaks + 2 ..][0..num_loop_live]);
1113
1114 // This is necessarily not in the same control flow branch, because loops are noreturn
1115 data.live_set.clearRetainingCapacity();
1116
1117 try data.live_set.ensureUnusedCapacity(gpa, @intCast(loop_live.len));
1118 for (loop_live) |alive| data.live_set.putAssumeCapacity(alive, {});
1119
1120 log.debug("[{}] %{f}: block live set is {f}", .{ LivenessPass.main_analysis, inst, fmtInstSet(&data.live_set) });
1121
1122 for (breaks) |block_inst| {
1123 // We might break to this block, so include every operand that the block needs alive
1124 const block_scope = data.block_scopes.get(block_inst).?;
1125
1126 var it = block_scope.live_set.keyIterator();
1127 while (it.next()) |key| {
1128 const alive = key.*;
1129 try data.live_set.put(gpa, alive, {});
1130 }
1131 }
1132
1133 log.debug("[{}] %{f}: loop live set is {f}", .{ LivenessPass.main_analysis, inst, fmtInstSet(&data.live_set) });
1134}
1135
1136fn analyzeInstLoop(
1137 a: *Analysis,
1138 comptime pass: LivenessPass,
1139 data: *LivenessPassData(pass),
1140 inst: Air.Inst.Index,
1141) !void {
1142 const inst_datas = a.air.instructions.items(.data);
1143 const extra = a.air.extraData(Air.Block, inst_datas[@intFromEnum(inst)].ty_pl.payload);
1144 const body: []const Air.Inst.Index = @ptrCast(a.air.extra.items[extra.end..][0..extra.data.body_len]);
1145 const gpa = a.gpa;
1146
1147 try analyzeOperands(a, pass, data, inst, .{ .none, .none, .none });
1148
1149 switch (pass) {
1150 .loop_analysis => {
1151 var old_breaks = data.breaks.move();
1152 defer old_breaks.deinit(gpa);
1153
1154 var old_live = data.live_set.move();
1155 defer old_live.deinit(gpa);
1156
1157 try analyzeBody(a, pass, data, body);
1158
1159 try writeLoopInfo(a, data, inst, old_breaks, old_live);
1160 },
1161
1162 .main_analysis => {
1163 try resolveLoopLiveSet(a, data, inst);
1164
1165 // Now, `data.live_set` is the operands which must be alive when the loop repeats.
1166 // Move them into a block scope for corresponding `repeat` instructions to notice.
1167 try data.block_scopes.putNoClobber(gpa, inst, .{
1168 .live_set = data.live_set.move(),
1169 });
1170 defer {
1171 log.debug("[{}] %{f}: popped loop block scop", .{ pass, inst });
1172 var scope = data.block_scopes.fetchRemove(inst).?.value;
1173 scope.live_set.deinit(gpa);
1174 }
1175 try analyzeBody(a, pass, data, body);
1176 },
1177 }
1178}
1179
1180/// Despite its name, this function is used for analysis of not only `cond_br` instructions, but
1181/// also `try` and `try_ptr`, which are highly related. The `inst_type` parameter indicates which
1182/// type of instruction `inst` points to.
1183fn analyzeInstCondBr(
1184 a: *Analysis,
1185 comptime pass: LivenessPass,
1186 data: *LivenessPassData(pass),
1187 inst: Air.Inst.Index,
1188 comptime inst_type: enum { cond_br, @"try", try_ptr },
1189) !void {
1190 const inst_datas = a.air.instructions.items(.data);
1191 const gpa = a.gpa;
1192
1193 const extra = switch (inst_type) {
1194 .cond_br => a.air.extraData(Air.CondBr, inst_datas[@intFromEnum(inst)].pl_op.payload),
1195 .@"try" => a.air.extraData(Air.Try, inst_datas[@intFromEnum(inst)].pl_op.payload),
1196 .try_ptr => a.air.extraData(Air.TryPtr, inst_datas[@intFromEnum(inst)].ty_pl.payload),
1197 };
1198
1199 const condition = switch (inst_type) {
1200 .cond_br, .@"try" => inst_datas[@intFromEnum(inst)].pl_op.operand,
1201 .try_ptr => extra.data.ptr,
1202 };
1203
1204 const then_body: []const Air.Inst.Index = switch (inst_type) {
1205 .cond_br => @ptrCast(a.air.extra.items[extra.end..][0..extra.data.then_body_len]),
1206 else => &.{}, // we won't use this
1207 };
1208
1209 const else_body: []const Air.Inst.Index = @ptrCast(switch (inst_type) {
1210 .cond_br => a.air.extra.items[extra.end + then_body.len ..][0..extra.data.else_body_len],
1211 .@"try", .try_ptr => a.air.extra.items[extra.end..][0..extra.data.body_len],
1212 });
1213
1214 switch (pass) {
1215 .loop_analysis => {
1216 switch (inst_type) {
1217 .cond_br => try analyzeBody(a, pass, data, then_body),
1218 .@"try", .try_ptr => {},
1219 }
1220 try analyzeBody(a, pass, data, else_body);
1221 },
1222
1223 .main_analysis => {
1224 switch (inst_type) {
1225 .cond_br => try analyzeBody(a, pass, data, then_body),
1226 .@"try", .try_ptr => {}, // The "then body" is just the remainder of this block
1227 }
1228 var then_live = data.live_set.move();
1229 defer then_live.deinit(gpa);
1230
1231 try analyzeBody(a, pass, data, else_body);
1232 var else_live = data.live_set.move();
1233 defer else_live.deinit(gpa);
1234
1235 // Operands which are alive in one branch but not the other need to die at the start of
1236 // the peer branch.
1237
1238 var then_mirrored_deaths: std.ArrayList(Air.Inst.Index) = .empty;
1239 defer then_mirrored_deaths.deinit(gpa);
1240
1241 var else_mirrored_deaths: std.ArrayList(Air.Inst.Index) = .empty;
1242 defer else_mirrored_deaths.deinit(gpa);
1243
1244 // Note: this invalidates `else_live`, but expands `then_live` to be their union
1245 {
1246 var it = then_live.keyIterator();
1247 while (it.next()) |key| {
1248 const death = key.*;
1249 if (else_live.remove(death)) continue; // removing makes the loop below faster
1250
1251 // If this is a `try`, the "then body" (rest of the branch) might have
1252 // referenced our result. We want to avoid killing this value in the else branch
1253 // if that's the case, since it only exists in the (fake) then branch.
1254 switch (inst_type) {
1255 .cond_br => {},
1256 .@"try", .try_ptr => if (death == inst) continue,
1257 }
1258
1259 try else_mirrored_deaths.append(gpa, death);
1260 }
1261 // Since we removed common stuff above, `else_live` is now only operands
1262 // which are *only* alive in the else branch
1263 it = else_live.keyIterator();
1264 while (it.next()) |key| {
1265 const death = key.*;
1266 try then_mirrored_deaths.append(gpa, death);
1267 // Make `then_live` contain the full live set (i.e. union of both)
1268 try then_live.put(gpa, death, {});
1269 }
1270 }
1271
1272 log.debug("[{}] %{f}: 'then' branch mirrored deaths are {f}", .{ pass, inst, fmtInstList(then_mirrored_deaths.items) });
1273 log.debug("[{}] %{f}: 'else' branch mirrored deaths are {f}", .{ pass, inst, fmtInstList(else_mirrored_deaths.items) });
1274
1275 data.live_set.deinit(gpa);
1276 data.live_set = then_live.move(); // Really the union of both live sets
1277
1278 log.debug("[{}] %{f}: new live set is {f}", .{ pass, inst, fmtInstSet(&data.live_set) });
1279
1280 // Write the mirrored deaths to `extra`
1281 const then_death_count = @as(u32, @intCast(then_mirrored_deaths.items.len));
1282 const else_death_count = @as(u32, @intCast(else_mirrored_deaths.items.len));
1283 try a.extra.ensureUnusedCapacity(gpa, std.meta.fields(CondBr).len + then_death_count + else_death_count);
1284 const extra_index = a.addExtraAssumeCapacity(CondBr{
1285 .then_death_count = then_death_count,
1286 .else_death_count = else_death_count,
1287 });
1288 a.extra.appendSliceAssumeCapacity(@ptrCast(then_mirrored_deaths.items));
1289 a.extra.appendSliceAssumeCapacity(@ptrCast(else_mirrored_deaths.items));
1290 try a.special.put(gpa, inst, extra_index);
1291 },
1292 }
1293
1294 try analyzeOperands(a, pass, data, inst, .{ condition, .none, .none });
1295}
1296
1297fn analyzeInstSwitchBr(
1298 a: *Analysis,
1299 comptime pass: LivenessPass,
1300 data: *LivenessPassData(pass),
1301 inst: Air.Inst.Index,
1302 is_dispatch_loop: bool,
1303) !void {
1304 const inst_datas = a.air.instructions.items(.data);
1305 const pl_op = inst_datas[@intFromEnum(inst)].pl_op;
1306 const condition = pl_op.operand;
1307 const switch_br = a.air.unwrapSwitch(inst);
1308 const gpa = a.gpa;
1309 const ncases = switch_br.cases_len;
1310
1311 switch (pass) {
1312 .loop_analysis => {
1313 var old_breaks: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .empty;
1314 defer old_breaks.deinit(gpa);
1315
1316 var old_live: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .empty;
1317 defer old_live.deinit(gpa);
1318
1319 if (is_dispatch_loop) {
1320 old_breaks = data.breaks.move();
1321 old_live = data.live_set.move();
1322 }
1323
1324 var it = switch_br.iterateCases();
1325 while (it.next()) |case| {
1326 try analyzeBody(a, pass, data, case.body);
1327 }
1328 { // else
1329 const else_body = it.elseBody();
1330 try analyzeBody(a, pass, data, else_body);
1331 }
1332
1333 if (is_dispatch_loop) {
1334 try writeLoopInfo(a, data, inst, old_breaks, old_live);
1335 }
1336 },
1337
1338 .main_analysis => {
1339 if (is_dispatch_loop) {
1340 try resolveLoopLiveSet(a, data, inst);
1341 try data.block_scopes.putNoClobber(gpa, inst, .{
1342 .live_set = data.live_set.move(),
1343 });
1344 }
1345 defer if (is_dispatch_loop) {
1346 log.debug("[{}] %{f}: popped loop block scop", .{ pass, inst });
1347 var scope = data.block_scopes.fetchRemove(inst).?.value;
1348 scope.live_set.deinit(gpa);
1349 };
1350 // This is, all in all, just a messier version of the `cond_br` logic. If you're trying
1351 // to understand it, I encourage looking at `analyzeInstCondBr` first.
1352
1353 const DeathSet = std.AutoHashMapUnmanaged(Air.Inst.Index, void);
1354 const DeathList = std.ArrayList(Air.Inst.Index);
1355
1356 var case_live_sets = try gpa.alloc(std.AutoHashMapUnmanaged(Air.Inst.Index, void), ncases + 1); // +1 for else
1357 defer gpa.free(case_live_sets);
1358
1359 @memset(case_live_sets, .{});
1360 defer for (case_live_sets) |*live_set| live_set.deinit(gpa);
1361
1362 var case_it = switch_br.iterateCases();
1363 while (case_it.next()) |case| {
1364 try analyzeBody(a, pass, data, case.body);
1365 case_live_sets[case.idx] = data.live_set.move();
1366 }
1367 { // else
1368 const else_body = case_it.elseBody();
1369 try analyzeBody(a, pass, data, else_body);
1370 case_live_sets[ncases] = data.live_set.move();
1371 }
1372
1373 const mirrored_deaths = try gpa.alloc(DeathList, ncases + 1);
1374 defer gpa.free(mirrored_deaths);
1375
1376 @memset(mirrored_deaths, .{});
1377 defer for (mirrored_deaths) |*md| md.deinit(gpa);
1378
1379 {
1380 var all_alive: DeathSet = .{};
1381 defer all_alive.deinit(gpa);
1382
1383 for (case_live_sets) |*live_set| {
1384 try all_alive.ensureUnusedCapacity(gpa, live_set.count());
1385 var it = live_set.keyIterator();
1386 while (it.next()) |key| {
1387 const alive = key.*;
1388 all_alive.putAssumeCapacity(alive, {});
1389 }
1390 }
1391
1392 for (mirrored_deaths, case_live_sets) |*mirrored, *live_set| {
1393 var it = all_alive.keyIterator();
1394 while (it.next()) |key| {
1395 const alive = key.*;
1396 if (!live_set.contains(alive)) {
1397 // Should die at the start of this branch
1398 try mirrored.append(gpa, alive);
1399 }
1400 }
1401 }
1402
1403 for (mirrored_deaths, 0..) |mirrored, i| {
1404 log.debug("[{}] %{f}: case {} mirrored deaths are {f}", .{ pass, inst, i, fmtInstList(mirrored.items) });
1405 }
1406
1407 data.live_set.deinit(gpa);
1408 data.live_set = all_alive.move();
1409
1410 log.debug("[{}] %{f}: new live set is {f}", .{ pass, inst, fmtInstSet(&data.live_set) });
1411 }
1412
1413 const else_death_count = @as(u32, @intCast(mirrored_deaths[ncases].items.len));
1414 const extra_index = try a.addExtra(SwitchBr{
1415 .else_death_count = else_death_count,
1416 });
1417 for (mirrored_deaths[0..ncases]) |mirrored| {
1418 const num = @as(u32, @intCast(mirrored.items.len));
1419 try a.extra.ensureUnusedCapacity(gpa, num + 1);
1420 a.extra.appendAssumeCapacity(num);
1421 a.extra.appendSliceAssumeCapacity(@ptrCast(mirrored.items));
1422 }
1423 try a.extra.ensureUnusedCapacity(gpa, else_death_count);
1424 a.extra.appendSliceAssumeCapacity(@ptrCast(mirrored_deaths[ncases].items));
1425 try a.special.put(gpa, inst, extra_index);
1426 },
1427 }
1428
1429 try analyzeOperands(a, pass, data, inst, .{ condition, .none, .none });
1430}
1431
1432fn AnalyzeBigOperands(comptime pass: LivenessPass) type {
1433 return struct {
1434 a: *Analysis,
1435 data: *LivenessPassData(pass),
1436 inst: Air.Inst.Index,
1437
1438 operands_remaining: u32,
1439 small: [bpi - 1]Air.Inst.Ref = .{.none} ** (bpi - 1),
1440 extra_tombs: []u32,
1441
1442 // Only used in `LivenessPass.main_analysis`
1443 will_die_immediately: bool,
1444
1445 const Self = @This();
1446
1447 fn init(
1448 a: *Analysis,
1449 data: *LivenessPassData(pass),
1450 inst: Air.Inst.Index,
1451 total_operands: usize,
1452 ) !Self {
1453 const extra_operands = @as(u32, @intCast(total_operands)) -| (bpi - 1);
1454 const max_extra_tombs = (extra_operands + 30) / 31;
1455
1456 const extra_tombs: []u32 = switch (pass) {
1457 .loop_analysis => &.{},
1458 .main_analysis => try a.gpa.alloc(u32, max_extra_tombs),
1459 };
1460 errdefer a.gpa.free(extra_tombs);
1461
1462 @memset(extra_tombs, 0);
1463
1464 const will_die_immediately: bool = switch (pass) {
1465 .loop_analysis => false, // track everything, since we don't have full liveness information yet
1466 .main_analysis => !data.live_set.contains(inst),
1467 };
1468
1469 return .{
1470 .a = a,
1471 .data = data,
1472 .inst = inst,
1473 .operands_remaining = @as(u32, @intCast(total_operands)),
1474 .extra_tombs = extra_tombs,
1475 .will_die_immediately = will_die_immediately,
1476 };
1477 }
1478
1479 /// Must be called with operands in reverse order.
1480 fn feed(big: *Self, op_ref: Air.Inst.Ref) !void {
1481 const ip = big.a.intern_pool;
1482 // Note that after this, `operands_remaining` becomes the index of the current operand
1483 big.operands_remaining -= 1;
1484
1485 if (big.operands_remaining < bpi - 1) {
1486 big.small[big.operands_remaining] = op_ref;
1487 return;
1488 }
1489
1490 const operand = op_ref.toIndex() orelse return;
1491
1492 // If our result is unused and the instruction doesn't need to be lowered, backends will
1493 // skip the lowering of this instruction, so we don't want to record uses of operands.
1494 // That way, we can mark as many instructions as possible unused.
1495 if (big.will_die_immediately and !big.a.air.mustLower(big.inst, ip)) return;
1496
1497 const extra_byte = (big.operands_remaining - (bpi - 1)) / 31;
1498 const extra_bit = @as(u5, @intCast(big.operands_remaining - (bpi - 1) - extra_byte * 31));
1499
1500 const gpa = big.a.gpa;
1501
1502 switch (pass) {
1503 .loop_analysis => {
1504 _ = try big.data.live_set.put(gpa, operand, {});
1505 },
1506
1507 .main_analysis => {
1508 if ((try big.data.live_set.fetchPut(gpa, operand, {})) == null) {
1509 log.debug("[{}] %{f}: added %{f} to live set (operand dies here)", .{ pass, big.inst, operand });
1510 big.extra_tombs[extra_byte] |= @as(u32, 1) << extra_bit;
1511 }
1512 },
1513 }
1514 }
1515
1516 fn finish(big: *Self) !void {
1517 const gpa = big.a.gpa;
1518
1519 std.debug.assert(big.operands_remaining == 0);
1520
1521 switch (pass) {
1522 .loop_analysis => {},
1523
1524 .main_analysis => {
1525 // Note that the MSB is set on the final tomb to indicate the terminal element. This
1526 // allows for an optimisation where we only add as many extra tombs as are needed to
1527 // represent the dying operands. Each pass modifies operand bits and so needs to write
1528 // back, so let's figure out how many extra tombs we really need. Note that we always
1529 // keep at least one.
1530 var num: usize = big.extra_tombs.len;
1531 while (num > 1) {
1532 if (@as(u31, @truncate(big.extra_tombs[num - 1])) != 0) {
1533 // Some operand dies here
1534 break;
1535 }
1536 num -= 1;
1537 }
1538 // Mark final tomb
1539 big.extra_tombs[num - 1] |= @as(u32, 1) << 31;
1540
1541 const extra_tombs = big.extra_tombs[0..num];
1542
1543 const extra_index = @as(u32, @intCast(big.a.extra.items.len));
1544 try big.a.extra.appendSlice(gpa, extra_tombs);
1545 try big.a.special.put(gpa, big.inst, extra_index);
1546 },
1547 }
1548
1549 try analyzeOperands(big.a, pass, big.data, big.inst, big.small);
1550 }
1551
1552 fn deinit(big: *Self) void {
1553 big.a.gpa.free(big.extra_tombs);
1554 }
1555 };
1556}
1557
1558fn fmtInstSet(set: *const std.AutoHashMapUnmanaged(Air.Inst.Index, void)) FmtInstSet {
1559 return .{ .set = set };
1560}
1561
1562const FmtInstSet = struct {
1563 set: *const std.AutoHashMapUnmanaged(Air.Inst.Index, void),
1564
1565 pub fn format(val: FmtInstSet, w: *Writer) Writer.Error!void {
1566 if (val.set.count() == 0) {
1567 try w.writeAll("[no instructions]");
1568 return;
1569 }
1570 var it = val.set.keyIterator();
1571 try w.print("%{f}", .{it.next().?.*});
1572 while (it.next()) |key| {
1573 try w.print(" %{f}", .{key.*});
1574 }
1575 }
1576};
1577
1578fn fmtInstList(list: []const Air.Inst.Index) FmtInstList {
1579 return .{ .list = list };
1580}
1581
1582const FmtInstList = struct {
1583 list: []const Air.Inst.Index,
1584
1585 pub fn format(val: FmtInstList, w: *Writer) Writer.Error!void {
1586 if (val.list.len == 0) {
1587 try w.writeAll("[no instructions]");
1588 return;
1589 }
1590 try w.print("%{f}", .{val.list[0]});
1591 for (val.list[1..]) |inst| {
1592 try w.print(" %{f}", .{inst});
1593 }
1594 }
1595};