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