zig

blob 435075a4 (48408B) - Raw

---

 //! For each AIR instruction, we want to know:
 //! * Is the instruction unreferenced (e.g. dies immediately)?
 //! * For each of its operands, does the operand die with this instruction (e.g. is
 //!   this the last reference to it)?
 //! Some instructions are special, such as:
 //! * Conditional Branches
 //! * Switch Branches
 const Liveness = @This();
 const std = @import("std");
 const trace = @import("tracy.zig").trace;
 const log = std.log.scoped(.liveness);
 const assert = std.debug.assert;
 const Allocator = std.mem.Allocator;
 const Air = @import("Air.zig");
 const Log2Int = std.math.Log2Int;
 
 /// This array is split into sets of 4 bits per AIR instruction.
 /// The MSB (0bX000) is whether the instruction is unreferenced.
 /// The LSB (0b000X) is the first operand, and so on, up to 3 operands. A set bit means the
 /// operand dies after this instruction.
 /// Instructions which need more data to track liveness have special handling via the
 /// `special` table.
 tomb_bits: []usize,
 /// Sparse table of specially handled instructions. The value is an index into the `extra`
 /// array. The meaning of the data depends on the AIR tag.
 ///  * `cond_br` - points to a `CondBr` in `extra` at this index.
 ///  * `switch_br` - points to a `SwitchBr` in `extra` at this index.
 ///  * `asm`, `call`, `aggregate_init` - the value is a set of bits which are the extra tomb
 ///    bits of operands.
 ///    The main tomb bits are still used and the extra ones are starting with the lsb of the
 ///    value here.
 special: std.AutoHashMapUnmanaged(Air.Inst.Index, u32),
 /// Auxiliary data. The way this data is interpreted is determined contextually.
 extra: []const u32,
 
 /// Trailing is the set of instructions whose lifetimes end at the start of the then branch,
 /// followed by the set of instructions whose lifetimes end at the start of the else branch.
 pub const CondBr = struct {
     then_death_count: u32,
     else_death_count: u32,
 };
 
 /// Trailing is:
 /// * For each case in the same order as in the AIR:
 ///   - case_death_count: u32
 ///   - Air.Inst.Index for each `case_death_count`: set of instructions whose lifetimes
 ///     end at the start of this case.
 /// * Air.Inst.Index for each `else_death_count`: set of instructions whose lifetimes
 ///   end at the start of the else case.
 pub const SwitchBr = struct {
     else_death_count: u32,
 };
 
 pub fn analyze(gpa: Allocator, air: Air) Allocator.Error!Liveness {
     const tracy = trace(@src());
     defer tracy.end();
 
     var a: Analysis = .{
         .gpa = gpa,
         .air = air,
         .table = .{},
         .tomb_bits = try gpa.alloc(
             usize,
             (air.instructions.len * bpi + @bitSizeOf(usize) - 1) / @bitSizeOf(usize),
         ),
         .extra = .{},
         .special = .{},
     };
     errdefer gpa.free(a.tomb_bits);
     errdefer a.special.deinit(gpa);
     defer a.extra.deinit(gpa);
     defer a.table.deinit(gpa);
 
     std.mem.set(usize, a.tomb_bits, 0);
 
     const main_body = air.getMainBody();
     try a.table.ensureTotalCapacity(gpa, @intCast(u32, main_body.len));
     try analyzeWithContext(&a, null, main_body);
     return Liveness{
         .tomb_bits = a.tomb_bits,
         .special = a.special,
         .extra = a.extra.toOwnedSlice(gpa),
     };
 }
 
 pub fn getTombBits(l: Liveness, inst: Air.Inst.Index) Bpi {
     const usize_index = (inst * bpi) / @bitSizeOf(usize);
     return @truncate(Bpi, l.tomb_bits[usize_index] >>
         @intCast(Log2Int(usize), (inst % (@bitSizeOf(usize) / bpi)) * bpi));
 }
 
 pub fn isUnused(l: Liveness, inst: Air.Inst.Index) bool {
     const usize_index = (inst * bpi) / @bitSizeOf(usize);
     const mask = @as(usize, 1) <<
         @intCast(Log2Int(usize), (inst % (@bitSizeOf(usize) / bpi)) * bpi + (bpi - 1));
     return (l.tomb_bits[usize_index] & mask) != 0;
 }
 
 pub fn operandDies(l: Liveness, inst: Air.Inst.Index, operand: OperandInt) bool {
     assert(operand < bpi - 1);
     const usize_index = (inst * bpi) / @bitSizeOf(usize);
     const mask = @as(usize, 1) <<
         @intCast(Log2Int(usize), (inst % (@bitSizeOf(usize) / bpi)) * bpi + operand);
     return (l.tomb_bits[usize_index] & mask) != 0;
 }
 
 pub fn clearOperandDeath(l: Liveness, inst: Air.Inst.Index, operand: OperandInt) void {
     assert(operand < bpi - 1);
     const usize_index = (inst * bpi) / @bitSizeOf(usize);
     const mask = @as(usize, 1) <<
         @intCast(Log2Int(usize), (inst % (@bitSizeOf(usize) / bpi)) * bpi + operand);
     l.tomb_bits[usize_index] &= ~mask;
 }
 
 const OperandCategory = enum {
     /// The operand lives on, but this instruction cannot possibly mutate memory.
     none,
     /// The operand lives on and this instruction can mutate memory.
     write,
     /// The operand dies at this instruction.
     tomb,
     /// The operand lives on, and this instruction is noreturn.
     noret,
     /// This instruction is too complicated for analysis, no information is available.
     complex,
 };
 
 /// Given an instruction that we are examining, and an operand that we are looking for,
 /// returns a classification.
 pub fn categorizeOperand(
     l: Liveness,
     air: Air,
     inst: Air.Inst.Index,
     operand: Air.Inst.Index,
 ) OperandCategory {
     const air_tags = air.instructions.items(.tag);
     const air_datas = air.instructions.items(.data);
     const operand_ref = Air.indexToRef(operand);
     switch (air_tags[inst]) {
         .add,
         .addwrap,
         .add_sat,
         .sub,
         .subwrap,
         .sub_sat,
         .mul,
         .mulwrap,
         .mul_sat,
         .div_float,
         .div_trunc,
         .div_floor,
         .div_exact,
         .rem,
         .mod,
         .bit_and,
         .bit_or,
         .xor,
         .cmp_lt,
         .cmp_lte,
         .cmp_eq,
         .cmp_gte,
         .cmp_gt,
         .cmp_neq,
         .bool_and,
         .bool_or,
         .array_elem_val,
         .slice_elem_val,
         .ptr_elem_val,
         .shl,
         .shl_exact,
         .shl_sat,
         .shr,
         .shr_exact,
         .min,
         .max,
         .add_optimized,
         .addwrap_optimized,
         .sub_optimized,
         .subwrap_optimized,
         .mul_optimized,
         .mulwrap_optimized,
         .div_float_optimized,
         .div_trunc_optimized,
         .div_floor_optimized,
         .div_exact_optimized,
         .rem_optimized,
         .mod_optimized,
         .neg_optimized,
         .cmp_lt_optimized,
         .cmp_lte_optimized,
         .cmp_eq_optimized,
         .cmp_gte_optimized,
         .cmp_gt_optimized,
         .cmp_neq_optimized,
         => {
             const o = air_datas[inst].bin_op;
             if (o.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (o.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             return .none;
         },
 
         .store,
         .atomic_store_unordered,
         .atomic_store_monotonic,
         .atomic_store_release,
         .atomic_store_seq_cst,
         .set_union_tag,
         => {
             const o = air_datas[inst].bin_op;
             if (o.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             if (o.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .write);
             return .write;
         },
 
         .arg,
         .alloc,
         .ret_ptr,
         .constant,
         .const_ty,
         .breakpoint,
         .dbg_stmt,
         .dbg_inline_begin,
         .dbg_inline_end,
         .dbg_block_begin,
         .dbg_block_end,
         .unreach,
         .ret_addr,
         .frame_addr,
         .wasm_memory_size,
         .err_return_trace,
         => return .none,
 
         .fence => return .write,
 
         .not,
         .bitcast,
         .load,
         .fpext,
         .fptrunc,
         .intcast,
         .trunc,
         .optional_payload,
         .optional_payload_ptr,
         .wrap_optional,
         .unwrap_errunion_payload,
         .unwrap_errunion_err,
         .unwrap_errunion_payload_ptr,
         .unwrap_errunion_err_ptr,
         .wrap_errunion_payload,
         .wrap_errunion_err,
         .slice_ptr,
         .slice_len,
         .ptr_slice_len_ptr,
         .ptr_slice_ptr_ptr,
         .struct_field_ptr_index_0,
         .struct_field_ptr_index_1,
         .struct_field_ptr_index_2,
         .struct_field_ptr_index_3,
         .array_to_slice,
         .float_to_int,
         .float_to_int_optimized,
         .int_to_float,
         .get_union_tag,
         .clz,
         .ctz,
         .popcount,
         .byte_swap,
         .bit_reverse,
         .splat,
         => {
             const o = air_datas[inst].ty_op;
             if (o.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
 
         .optional_payload_ptr_set,
         .errunion_payload_ptr_set,
         => {
             const o = air_datas[inst].ty_op;
             if (o.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             return .write;
         },
 
         .is_null,
         .is_non_null,
         .is_null_ptr,
         .is_non_null_ptr,
         .is_err,
         .is_non_err,
         .is_err_ptr,
         .is_non_err_ptr,
         .ptrtoint,
         .bool_to_int,
         .tag_name,
         .error_name,
         .sqrt,
         .sin,
         .cos,
         .tan,
         .exp,
         .exp2,
         .log,
         .log2,
         .log10,
         .fabs,
         .floor,
         .ceil,
         .round,
         .trunc_float,
         .neg,
         .cmp_lt_errors_len,
         => {
             const o = air_datas[inst].un_op;
             if (o == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
 
         .ret,
         .ret_load,
         => {
             const o = air_datas[inst].un_op;
             if (o == operand_ref) return matchOperandSmallIndex(l, inst, 0, .noret);
             return .noret;
         },
 
         .set_err_return_trace => {
             const o = air_datas[inst].un_op;
             if (o == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             return .write;
         },
 
         .add_with_overflow,
         .sub_with_overflow,
         .mul_with_overflow,
         .shl_with_overflow,
         .ptr_add,
         .ptr_sub,
         .ptr_elem_ptr,
         .slice_elem_ptr,
         .slice,
         => {
             const ty_pl = air_datas[inst].ty_pl;
             const extra = air.extraData(Air.Bin, ty_pl.payload).data;
             if (extra.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (extra.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             return .none;
         },
 
         .dbg_var_ptr,
         .dbg_var_val,
         => {
             const o = air_datas[inst].pl_op.operand;
             if (o == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
 
         .prefetch => {
             const prefetch = air_datas[inst].prefetch;
             if (prefetch.ptr == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
 
         .call, .call_always_tail, .call_never_tail, .call_never_inline => {
             const inst_data = air_datas[inst].pl_op;
             const callee = inst_data.operand;
             const extra = air.extraData(Air.Call, inst_data.payload);
             const args = @ptrCast([]const Air.Inst.Ref, air.extra[extra.end..][0..extra.data.args_len]);
             if (args.len + 1 <= bpi - 1) {
                 if (callee == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
                 for (args) |arg, i| {
                     if (arg == operand_ref) return matchOperandSmallIndex(l, inst, @intCast(OperandInt, i + 1), .write);
                 }
                 return .write;
             }
             var bt = l.iterateBigTomb(inst);
             if (bt.feed()) {
                 if (callee == operand_ref) return .tomb;
             } else {
                 if (callee == operand_ref) return .write;
             }
             for (args) |arg| {
                 if (bt.feed()) {
                     if (arg == operand_ref) return .tomb;
                 } else {
                     if (arg == operand_ref) return .write;
                 }
             }
             return .write;
         },
         .select => {
             const pl_op = air_datas[inst].pl_op;
             const extra = air.extraData(Air.Bin, pl_op.payload).data;
             if (pl_op.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (extra.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             if (extra.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 2, .none);
             return .none;
         },
         .shuffle => {
             const extra = air.extraData(Air.Shuffle, air_datas[inst].ty_pl.payload).data;
             if (extra.a == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (extra.b == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             return .none;
         },
         .reduce, .reduce_optimized => {
             const reduce = air_datas[inst].reduce;
             if (reduce.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
         .cmp_vector, .cmp_vector_optimized => {
             const extra = air.extraData(Air.VectorCmp, air_datas[inst].ty_pl.payload).data;
             if (extra.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (extra.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             return .none;
         },
         .aggregate_init => {
             const ty_pl = air_datas[inst].ty_pl;
             const aggregate_ty = air.getRefType(ty_pl.ty);
             const len = @intCast(usize, aggregate_ty.arrayLen());
             const elements = @ptrCast([]const Air.Inst.Ref, air.extra[ty_pl.payload..][0..len]);
 
             if (elements.len <= bpi - 1) {
                 for (elements) |elem, i| {
                     if (elem == operand_ref) return matchOperandSmallIndex(l, inst, @intCast(OperandInt, i), .none);
                 }
                 return .none;
             }
 
             var bt = l.iterateBigTomb(inst);
             for (elements) |elem| {
                 if (bt.feed()) {
                     if (elem == operand_ref) return .tomb;
                 } else {
                     if (elem == operand_ref) return .write;
                 }
             }
             return .write;
         },
         .union_init => {
             const extra = air.extraData(Air.UnionInit, air_datas[inst].ty_pl.payload).data;
             if (extra.init == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
         .struct_field_ptr, .struct_field_val => {
             const extra = air.extraData(Air.StructField, air_datas[inst].ty_pl.payload).data;
             if (extra.struct_operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
         .field_parent_ptr => {
             const extra = air.extraData(Air.FieldParentPtr, air_datas[inst].ty_pl.payload).data;
             if (extra.field_ptr == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
         .cmpxchg_strong, .cmpxchg_weak => {
             const extra = air.extraData(Air.Cmpxchg, air_datas[inst].ty_pl.payload).data;
             if (extra.ptr == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             if (extra.expected_value == operand_ref) return matchOperandSmallIndex(l, inst, 1, .write);
             if (extra.new_value == operand_ref) return matchOperandSmallIndex(l, inst, 2, .write);
             return .write;
         },
         .mul_add => {
             const pl_op = air_datas[inst].pl_op;
             const extra = air.extraData(Air.Bin, pl_op.payload).data;
             if (extra.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             if (extra.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .none);
             if (pl_op.operand == operand_ref) return matchOperandSmallIndex(l, inst, 2, .none);
             return .none;
         },
         .atomic_load => {
             const ptr = air_datas[inst].atomic_load.ptr;
             if (ptr == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
         .atomic_rmw => {
             const pl_op = air_datas[inst].pl_op;
             const extra = air.extraData(Air.AtomicRmw, pl_op.payload).data;
             if (pl_op.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             if (extra.operand == operand_ref) return matchOperandSmallIndex(l, inst, 1, .write);
             return .write;
         },
         .memset,
         .memcpy,
         => {
             const pl_op = air_datas[inst].pl_op;
             const extra = air.extraData(Air.Bin, pl_op.payload).data;
             if (pl_op.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .write);
             if (extra.lhs == operand_ref) return matchOperandSmallIndex(l, inst, 1, .write);
             if (extra.rhs == operand_ref) return matchOperandSmallIndex(l, inst, 2, .write);
             return .write;
         },
 
         .br => {
             const br = air_datas[inst].br;
             if (br.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .noret);
             return .noret;
         },
         .assembly => {
             return .complex;
         },
         .block => {
             return .complex;
         },
         .@"try" => {
             return .complex;
         },
         .try_ptr => {
             return .complex;
         },
         .loop => {
             return .complex;
         },
         .cond_br => {
             return .complex;
         },
         .switch_br => {
             return .complex;
         },
         .wasm_memory_grow => {
             const pl_op = air_datas[inst].pl_op;
             if (pl_op.operand == operand_ref) return matchOperandSmallIndex(l, inst, 0, .none);
             return .none;
         },
     }
 }
 
 fn matchOperandSmallIndex(
     l: Liveness,
     inst: Air.Inst.Index,
     operand: OperandInt,
     default: OperandCategory,
 ) OperandCategory {
     if (operandDies(l, inst, operand)) {
         return .tomb;
     } else {
         return default;
     }
 }
 
 /// Higher level API.
 pub const CondBrSlices = struct {
     then_deaths: []const Air.Inst.Index,
     else_deaths: []const Air.Inst.Index,
 };
 
 pub fn getCondBr(l: Liveness, inst: Air.Inst.Index) CondBrSlices {
     var index: usize = l.special.get(inst) orelse return .{
         .then_deaths = &.{},
         .else_deaths = &.{},
     };
     const then_death_count = l.extra[index];
     index += 1;
     const else_death_count = l.extra[index];
     index += 1;
     const then_deaths = l.extra[index..][0..then_death_count];
     index += then_death_count;
     return .{
         .then_deaths = then_deaths,
         .else_deaths = l.extra[index..][0..else_death_count],
     };
 }
 
 /// Indexed by case number as they appear in AIR.
 /// Else is the last element.
 pub const SwitchBrTable = struct {
     deaths: []const []const Air.Inst.Index,
 };
 
 /// Caller owns the memory.
 pub fn getSwitchBr(l: Liveness, gpa: Allocator, inst: Air.Inst.Index, cases_len: u32) Allocator.Error!SwitchBrTable {
     var index: usize = l.special.get(inst) orelse return SwitchBrTable{
         .deaths = &.{},
     };
     const else_death_count = l.extra[index];
     index += 1;
 
     var deaths = std.ArrayList([]const Air.Inst.Index).init(gpa);
     defer deaths.deinit();
     try deaths.ensureTotalCapacity(cases_len + 1);
 
     var case_i: u32 = 0;
     while (case_i < cases_len - 1) : (case_i += 1) {
         const case_death_count: u32 = l.extra[index];
         index += 1;
         const case_deaths = l.extra[index..][0..case_death_count];
         index += case_death_count;
         deaths.appendAssumeCapacity(case_deaths);
     }
     {
         // Else
         const else_deaths = l.extra[index..][0..else_death_count];
         deaths.appendAssumeCapacity(else_deaths);
     }
     return SwitchBrTable{
         .deaths = deaths.toOwnedSlice(),
     };
 }
 
 pub fn deinit(l: *Liveness, gpa: Allocator) void {
     gpa.free(l.tomb_bits);
     gpa.free(l.extra);
     l.special.deinit(gpa);
     l.* = undefined;
 }
 
 pub fn iterateBigTomb(l: Liveness, inst: Air.Inst.Index) BigTomb {
     return .{
         .tomb_bits = l.getTombBits(inst),
         .extra_start = l.special.get(inst) orelse 0,
         .extra_offset = 0,
         .extra = l.extra,
         .bit_index = 0,
     };
 }
 
 /// How many tomb bits per AIR instruction.
 pub const bpi = 4;
 pub const Bpi = std.meta.Int(.unsigned, bpi);
 pub const OperandInt = std.math.Log2Int(Bpi);
 
 /// Useful for decoders of Liveness information.
 pub const BigTomb = struct {
     tomb_bits: Liveness.Bpi,
     bit_index: u32,
     extra_start: u32,
     extra_offset: u32,
     extra: []const u32,
 
     /// Returns whether the next operand dies.
     pub fn feed(bt: *BigTomb) bool {
         const this_bit_index = bt.bit_index;
         bt.bit_index += 1;
 
         const small_tombs = Liveness.bpi - 1;
         if (this_bit_index < small_tombs) {
             const dies = @truncate(u1, bt.tomb_bits >> @intCast(Liveness.OperandInt, this_bit_index)) != 0;
             return dies;
         }
 
         const big_bit_index = this_bit_index - small_tombs;
         while (big_bit_index - bt.extra_offset * 31 >= 31) {
             bt.extra_offset += 1;
         }
         const dies = @truncate(u1, bt.extra[bt.extra_start + bt.extra_offset] >>
             @intCast(u5, big_bit_index - bt.extra_offset * 31)) != 0;
         return dies;
     }
 };
 
 /// In-progress data; on successful analysis converted into `Liveness`.
 const Analysis = struct {
     gpa: Allocator,
     air: Air,
     table: std.AutoHashMapUnmanaged(Air.Inst.Index, void),
     tomb_bits: []usize,
     special: std.AutoHashMapUnmanaged(Air.Inst.Index, u32),
     extra: std.ArrayListUnmanaged(u32),
 
     fn storeTombBits(a: *Analysis, inst: Air.Inst.Index, tomb_bits: Bpi) void {
         const usize_index = (inst * bpi) / @bitSizeOf(usize);
         a.tomb_bits[usize_index] |= @as(usize, tomb_bits) <<
             @intCast(Log2Int(usize), (inst % (@bitSizeOf(usize) / bpi)) * bpi);
     }
 
     fn addExtra(a: *Analysis, extra: anytype) Allocator.Error!u32 {
         const fields = std.meta.fields(@TypeOf(extra));
         try a.extra.ensureUnusedCapacity(a.gpa, fields.len);
         return addExtraAssumeCapacity(a, extra);
     }
 
     fn addExtraAssumeCapacity(a: *Analysis, extra: anytype) u32 {
         const fields = std.meta.fields(@TypeOf(extra));
         const result = @intCast(u32, a.extra.items.len);
         inline for (fields) |field| {
             a.extra.appendAssumeCapacity(switch (field.field_type) {
                 u32 => @field(extra, field.name),
                 else => @compileError("bad field type"),
             });
         }
         return result;
     }
 };
 
 fn analyzeWithContext(
     a: *Analysis,
     new_set: ?*std.AutoHashMapUnmanaged(Air.Inst.Index, void),
     body: []const Air.Inst.Index,
 ) Allocator.Error!void {
     var i: usize = body.len;
 
     if (new_set) |ns| {
         // We are only interested in doing this for instructions which are born
         // before a conditional branch, so after obtaining the new set for
         // each branch we prune the instructions which were born within.
         while (i != 0) {
             i -= 1;
             const inst = body[i];
             _ = ns.remove(inst);
             try analyzeInst(a, new_set, inst);
         }
     } else {
         while (i != 0) {
             i -= 1;
             const inst = body[i];
             try analyzeInst(a, new_set, inst);
         }
     }
 }
 
 fn analyzeInst(
     a: *Analysis,
     new_set: ?*std.AutoHashMapUnmanaged(Air.Inst.Index, void),
     inst: Air.Inst.Index,
 ) Allocator.Error!void {
     const gpa = a.gpa;
     const table = &a.table;
     const inst_tags = a.air.instructions.items(.tag);
     const inst_datas = a.air.instructions.items(.data);
 
     // No tombstone for this instruction means it is never referenced,
     // and its birth marks its own death. Very metal 🤘
     const main_tomb = !table.contains(inst);
 
     switch (inst_tags[inst]) {
         .add,
         .add_optimized,
         .addwrap,
         .addwrap_optimized,
         .add_sat,
         .sub,
         .sub_optimized,
         .subwrap,
         .subwrap_optimized,
         .sub_sat,
         .mul,
         .mul_optimized,
         .mulwrap,
         .mulwrap_optimized,
         .mul_sat,
         .div_float,
         .div_float_optimized,
         .div_trunc,
         .div_trunc_optimized,
         .div_floor,
         .div_floor_optimized,
         .div_exact,
         .div_exact_optimized,
         .rem,
         .rem_optimized,
         .mod,
         .mod_optimized,
         .bit_and,
         .bit_or,
         .xor,
         .cmp_lt,
         .cmp_lt_optimized,
         .cmp_lte,
         .cmp_lte_optimized,
         .cmp_eq,
         .cmp_eq_optimized,
         .cmp_gte,
         .cmp_gte_optimized,
         .cmp_gt,
         .cmp_gt_optimized,
         .cmp_neq,
         .cmp_neq_optimized,
         .bool_and,
         .bool_or,
         .store,
         .array_elem_val,
         .slice_elem_val,
         .ptr_elem_val,
         .shl,
         .shl_exact,
         .shl_sat,
         .shr,
         .shr_exact,
         .atomic_store_unordered,
         .atomic_store_monotonic,
         .atomic_store_release,
         .atomic_store_seq_cst,
         .set_union_tag,
         .min,
         .max,
         => {
             const o = inst_datas[inst].bin_op;
             return trackOperands(a, new_set, inst, main_tomb, .{ o.lhs, o.rhs, .none });
         },
 
         .arg,
         .alloc,
         .ret_ptr,
         .constant,
         .const_ty,
         .breakpoint,
         .dbg_stmt,
         .dbg_inline_begin,
         .dbg_inline_end,
         .dbg_block_begin,
         .dbg_block_end,
         .unreach,
         .fence,
         .ret_addr,
         .frame_addr,
         .wasm_memory_size,
         .err_return_trace,
         => return trackOperands(a, new_set, inst, main_tomb, .{ .none, .none, .none }),
 
         .not,
         .bitcast,
         .load,
         .fpext,
         .fptrunc,
         .intcast,
         .trunc,
         .optional_payload,
         .optional_payload_ptr,
         .optional_payload_ptr_set,
         .errunion_payload_ptr_set,
         .wrap_optional,
         .unwrap_errunion_payload,
         .unwrap_errunion_err,
         .unwrap_errunion_payload_ptr,
         .unwrap_errunion_err_ptr,
         .wrap_errunion_payload,
         .wrap_errunion_err,
         .slice_ptr,
         .slice_len,
         .ptr_slice_len_ptr,
         .ptr_slice_ptr_ptr,
         .struct_field_ptr_index_0,
         .struct_field_ptr_index_1,
         .struct_field_ptr_index_2,
         .struct_field_ptr_index_3,
         .array_to_slice,
         .float_to_int,
         .float_to_int_optimized,
         .int_to_float,
         .get_union_tag,
         .clz,
         .ctz,
         .popcount,
         .byte_swap,
         .bit_reverse,
         .splat,
         => {
             const o = inst_datas[inst].ty_op;
             return trackOperands(a, new_set, inst, main_tomb, .{ o.operand, .none, .none });
         },
 
         .is_null,
         .is_non_null,
         .is_null_ptr,
         .is_non_null_ptr,
         .is_err,
         .is_non_err,
         .is_err_ptr,
         .is_non_err_ptr,
         .ptrtoint,
         .bool_to_int,
         .ret,
         .ret_load,
         .tag_name,
         .error_name,
         .sqrt,
         .sin,
         .cos,
         .tan,
         .exp,
         .exp2,
         .log,
         .log2,
         .log10,
         .fabs,
         .floor,
         .ceil,
         .round,
         .trunc_float,
         .neg,
         .neg_optimized,
         .cmp_lt_errors_len,
         .set_err_return_trace,
         => {
             const operand = inst_datas[inst].un_op;
             return trackOperands(a, new_set, inst, main_tomb, .{ operand, .none, .none });
         },
 
         .add_with_overflow,
         .sub_with_overflow,
         .mul_with_overflow,
         .shl_with_overflow,
         .ptr_add,
         .ptr_sub,
         .ptr_elem_ptr,
         .slice_elem_ptr,
         .slice,
         => {
             const ty_pl = inst_datas[inst].ty_pl;
             const extra = a.air.extraData(Air.Bin, ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.lhs, extra.rhs, .none });
         },
 
         .dbg_var_ptr,
         .dbg_var_val,
         => {
             const operand = inst_datas[inst].pl_op.operand;
             return trackOperands(a, new_set, inst, main_tomb, .{ operand, .none, .none });
         },
 
         .prefetch => {
             const prefetch = inst_datas[inst].prefetch;
             return trackOperands(a, new_set, inst, main_tomb, .{ prefetch.ptr, .none, .none });
         },
 
         .call, .call_always_tail, .call_never_tail, .call_never_inline => {
             const inst_data = inst_datas[inst].pl_op;
             const callee = inst_data.operand;
             const extra = a.air.extraData(Air.Call, inst_data.payload);
             const args = @ptrCast([]const Air.Inst.Ref, a.air.extra[extra.end..][0..extra.data.args_len]);
             if (args.len + 1 <= bpi - 1) {
                 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
                 buf[0] = callee;
                 std.mem.copy(Air.Inst.Ref, buf[1..], args);
                 return trackOperands(a, new_set, inst, main_tomb, buf);
             }
             var extra_tombs: ExtraTombs = .{
                 .analysis = a,
                 .new_set = new_set,
                 .inst = inst,
                 .main_tomb = main_tomb,
             };
             defer extra_tombs.deinit();
             try extra_tombs.feed(callee);
             for (args) |arg| {
                 try extra_tombs.feed(arg);
             }
             return extra_tombs.finish();
         },
         .select => {
             const pl_op = inst_datas[inst].pl_op;
             const extra = a.air.extraData(Air.Bin, pl_op.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs });
         },
         .shuffle => {
             const extra = a.air.extraData(Air.Shuffle, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.a, extra.b, .none });
         },
         .reduce, .reduce_optimized => {
             const reduce = inst_datas[inst].reduce;
             return trackOperands(a, new_set, inst, main_tomb, .{ reduce.operand, .none, .none });
         },
         .cmp_vector, .cmp_vector_optimized => {
             const extra = a.air.extraData(Air.VectorCmp, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.lhs, extra.rhs, .none });
         },
         .aggregate_init => {
             const ty_pl = inst_datas[inst].ty_pl;
             const aggregate_ty = a.air.getRefType(ty_pl.ty);
             const len = @intCast(usize, aggregate_ty.arrayLen());
             const elements = @ptrCast([]const Air.Inst.Ref, a.air.extra[ty_pl.payload..][0..len]);
 
             if (elements.len <= bpi - 1) {
                 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
                 std.mem.copy(Air.Inst.Ref, &buf, elements);
                 return trackOperands(a, new_set, inst, main_tomb, buf);
             }
             var extra_tombs: ExtraTombs = .{
                 .analysis = a,
                 .new_set = new_set,
                 .inst = inst,
                 .main_tomb = main_tomb,
             };
             defer extra_tombs.deinit();
             for (elements) |elem| {
                 try extra_tombs.feed(elem);
             }
             return extra_tombs.finish();
         },
         .union_init => {
             const extra = a.air.extraData(Air.UnionInit, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.init, .none, .none });
         },
         .struct_field_ptr, .struct_field_val => {
             const extra = a.air.extraData(Air.StructField, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.struct_operand, .none, .none });
         },
         .field_parent_ptr => {
             const extra = a.air.extraData(Air.FieldParentPtr, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.field_ptr, .none, .none });
         },
         .cmpxchg_strong, .cmpxchg_weak => {
             const extra = a.air.extraData(Air.Cmpxchg, inst_datas[inst].ty_pl.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.ptr, extra.expected_value, extra.new_value });
         },
         .mul_add => {
             const pl_op = inst_datas[inst].pl_op;
             const extra = a.air.extraData(Air.Bin, pl_op.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.lhs, extra.rhs, pl_op.operand });
         },
         .atomic_load => {
             const ptr = inst_datas[inst].atomic_load.ptr;
             return trackOperands(a, new_set, inst, main_tomb, .{ ptr, .none, .none });
         },
         .atomic_rmw => {
             const pl_op = inst_datas[inst].pl_op;
             const extra = a.air.extraData(Air.AtomicRmw, pl_op.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.operand, .none });
         },
         .memset,
         .memcpy,
         => {
             const pl_op = inst_datas[inst].pl_op;
             const extra = a.air.extraData(Air.Bin, pl_op.payload).data;
             return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, extra.lhs, extra.rhs });
         },
 
         .br => {
             const br = inst_datas[inst].br;
             return trackOperands(a, new_set, inst, main_tomb, .{ br.operand, .none, .none });
         },
         .assembly => {
             const extra = a.air.extraData(Air.Asm, inst_datas[inst].ty_pl.payload);
             var extra_i: usize = extra.end;
             const outputs = @ptrCast([]const Air.Inst.Ref, a.air.extra[extra_i..][0..extra.data.outputs_len]);
             extra_i += outputs.len;
             const inputs = @ptrCast([]const Air.Inst.Ref, a.air.extra[extra_i..][0..extra.data.inputs_len]);
             extra_i += inputs.len;
 
             simple: {
                 var buf = [1]Air.Inst.Ref{.none} ** (bpi - 1);
                 var buf_index: usize = 0;
                 for (outputs) |output| {
                     if (output != .none) {
                         if (buf_index >= buf.len) break :simple;
                         buf[buf_index] = output;
                         buf_index += 1;
                     }
                 }
                 if (buf_index + inputs.len > buf.len) break :simple;
                 std.mem.copy(Air.Inst.Ref, buf[buf_index..], inputs);
                 return trackOperands(a, new_set, inst, main_tomb, buf);
             }
             var extra_tombs: ExtraTombs = .{
                 .analysis = a,
                 .new_set = new_set,
                 .inst = inst,
                 .main_tomb = main_tomb,
             };
             defer extra_tombs.deinit();
             for (outputs) |output| {
                 if (output != .none) {
                     try extra_tombs.feed(output);
                 }
             }
             for (inputs) |input| {
                 try extra_tombs.feed(input);
             }
             return extra_tombs.finish();
         },
         .block => {
             const extra = a.air.extraData(Air.Block, inst_datas[inst].ty_pl.payload);
             const body = a.air.extra[extra.end..][0..extra.data.body_len];
             try analyzeWithContext(a, new_set, body);
             return trackOperands(a, new_set, inst, main_tomb, .{ .none, .none, .none });
         },
         .loop => {
             const extra = a.air.extraData(Air.Block, inst_datas[inst].ty_pl.payload);
             const body = a.air.extra[extra.end..][0..extra.data.body_len];
             try analyzeWithContext(a, new_set, body);
             return; // Loop has no operands and it is always unreferenced.
         },
         .@"try" => {
             const pl_op = inst_datas[inst].pl_op;
             const extra = a.air.extraData(Air.Try, pl_op.payload);
             const body = a.air.extra[extra.end..][0..extra.data.body_len];
             try analyzeWithContext(a, new_set, body);
             return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, .none, .none });
         },
         .try_ptr => {
             const extra = a.air.extraData(Air.TryPtr, inst_datas[inst].ty_pl.payload);
             const body = a.air.extra[extra.end..][0..extra.data.body_len];
             try analyzeWithContext(a, new_set, body);
             return trackOperands(a, new_set, inst, main_tomb, .{ extra.data.ptr, .none, .none });
         },
         .cond_br => {
             // Each death that occurs inside one branch, but not the other, needs
             // to be added as a death immediately upon entering the other branch.
             const inst_data = inst_datas[inst].pl_op;
             const condition = inst_data.operand;
             const extra = a.air.extraData(Air.CondBr, inst_data.payload);
             const then_body = a.air.extra[extra.end..][0..extra.data.then_body_len];
             const else_body = a.air.extra[extra.end + then_body.len ..][0..extra.data.else_body_len];
 
             var then_table: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .{};
             defer then_table.deinit(gpa);
             try analyzeWithContext(a, &then_table, then_body);
 
             // Reset the table back to its state from before the branch.
             {
                 var it = then_table.keyIterator();
                 while (it.next()) |key| {
                     assert(table.remove(key.*));
                 }
             }
 
             var else_table: std.AutoHashMapUnmanaged(Air.Inst.Index, void) = .{};
             defer else_table.deinit(gpa);
             try analyzeWithContext(a, &else_table, else_body);
 
             var then_entry_deaths = std.ArrayList(Air.Inst.Index).init(gpa);
             defer then_entry_deaths.deinit();
             var else_entry_deaths = std.ArrayList(Air.Inst.Index).init(gpa);
             defer else_entry_deaths.deinit();
 
             {
                 var it = else_table.keyIterator();
                 while (it.next()) |key| {
                     const else_death = key.*;
                     if (!then_table.contains(else_death)) {
                         try then_entry_deaths.append(else_death);
                     }
                 }
             }
             // This loop is the same, except it's for the then branch, and it additionally
             // has to put its items back into the table to undo the reset.
             {
                 var it = then_table.keyIterator();
                 while (it.next()) |key| {
                     const then_death = key.*;
                     if (!else_table.contains(then_death)) {
                         try else_entry_deaths.append(then_death);
                     }
                     try table.put(gpa, then_death, {});
                 }
             }
             // Now we have to correctly populate new_set.
             if (new_set) |ns| {
                 try ns.ensureUnusedCapacity(gpa, @intCast(u32, then_table.count() + else_table.count()));
                 var it = then_table.keyIterator();
                 while (it.next()) |key| {
                     _ = ns.putAssumeCapacity(key.*, {});
                 }
                 it = else_table.keyIterator();
                 while (it.next()) |key| {
                     _ = ns.putAssumeCapacity(key.*, {});
                 }
             }
             const then_death_count = @intCast(u32, then_entry_deaths.items.len);
             const else_death_count = @intCast(u32, else_entry_deaths.items.len);
 
             try a.extra.ensureUnusedCapacity(gpa, std.meta.fields(Air.CondBr).len +
                 then_death_count + else_death_count);
             const extra_index = a.addExtraAssumeCapacity(CondBr{
                 .then_death_count = then_death_count,
                 .else_death_count = else_death_count,
             });
             a.extra.appendSliceAssumeCapacity(then_entry_deaths.items);
             a.extra.appendSliceAssumeCapacity(else_entry_deaths.items);
             try a.special.put(gpa, inst, extra_index);
 
             // Continue on with the instruction analysis. The following code will find the condition
             // instruction, and the deaths flag for the CondBr instruction will indicate whether the
             // condition's lifetime ends immediately before entering any branch.
             return trackOperands(a, new_set, inst, main_tomb, .{ condition, .none, .none });
         },
         .switch_br => {
             const pl_op = inst_datas[inst].pl_op;
             const condition = pl_op.operand;
             const switch_br = a.air.extraData(Air.SwitchBr, pl_op.payload);
 
             const Table = std.AutoHashMapUnmanaged(Air.Inst.Index, void);
             const case_tables = try gpa.alloc(Table, switch_br.data.cases_len + 1); // +1 for else
             defer gpa.free(case_tables);
 
             std.mem.set(Table, case_tables, .{});
             defer for (case_tables) |*ct| ct.deinit(gpa);
 
             var air_extra_index: usize = switch_br.end;
             for (case_tables[0..switch_br.data.cases_len]) |*case_table| {
                 const case = a.air.extraData(Air.SwitchBr.Case, air_extra_index);
                 const case_body = a.air.extra[case.end + case.data.items_len ..][0..case.data.body_len];
                 air_extra_index = case.end + case.data.items_len + case_body.len;
                 try analyzeWithContext(a, case_table, case_body);
 
                 // Reset the table back to its state from before the case.
                 var it = case_table.keyIterator();
                 while (it.next()) |key| {
                     assert(table.remove(key.*));
                 }
             }
             { // else
                 const else_table = &case_tables[case_tables.len - 1];
                 const else_body = a.air.extra[air_extra_index..][0..switch_br.data.else_body_len];
                 try analyzeWithContext(a, else_table, else_body);
 
                 // Reset the table back to its state from before the case.
                 var it = else_table.keyIterator();
                 while (it.next()) |key| {
                     assert(table.remove(key.*));
                 }
             }
 
             const List = std.ArrayListUnmanaged(Air.Inst.Index);
             const case_deaths = try gpa.alloc(List, case_tables.len); // includes else
             defer gpa.free(case_deaths);
 
             std.mem.set(List, case_deaths, .{});
             defer for (case_deaths) |*cd| cd.deinit(gpa);
 
             var total_deaths: u32 = 0;
             for (case_tables) |*ct, i| {
                 total_deaths += ct.count();
                 var it = ct.keyIterator();
                 while (it.next()) |key| {
                     const case_death = key.*;
                     for (case_tables) |*ct_inner, j| {
                         if (i == j) continue;
                         if (!ct_inner.contains(case_death)) {
                             // instruction is not referenced in this case
                             try case_deaths[j].append(gpa, case_death);
                         }
                     }
                     // undo resetting the table
                     try table.put(gpa, case_death, {});
                 }
             }
 
             // Now we have to correctly populate new_set.
             if (new_set) |ns| {
                 try ns.ensureUnusedCapacity(gpa, total_deaths);
                 for (case_tables) |*ct| {
                     var it = ct.keyIterator();
                     while (it.next()) |key| {
                         _ = ns.putAssumeCapacity(key.*, {});
                     }
                 }
             }
 
             const else_death_count = @intCast(u32, case_deaths[case_deaths.len - 1].items.len);
             const extra_index = try a.addExtra(SwitchBr{
                 .else_death_count = else_death_count,
             });
             for (case_deaths[0 .. case_deaths.len - 1]) |*cd| {
                 const case_death_count = @intCast(u32, cd.items.len);
                 try a.extra.ensureUnusedCapacity(gpa, 1 + case_death_count + else_death_count);
                 a.extra.appendAssumeCapacity(case_death_count);
                 a.extra.appendSliceAssumeCapacity(cd.items);
             }
             a.extra.appendSliceAssumeCapacity(case_deaths[case_deaths.len - 1].items);
             try a.special.put(gpa, inst, extra_index);
 
             return trackOperands(a, new_set, inst, main_tomb, .{ condition, .none, .none });
         },
         .wasm_memory_grow => {
             const pl_op = inst_datas[inst].pl_op;
             return trackOperands(a, new_set, inst, main_tomb, .{ pl_op.operand, .none, .none });
         },
     }
 }
 
 fn trackOperands(
     a: *Analysis,
     new_set: ?*std.AutoHashMapUnmanaged(Air.Inst.Index, void),
     inst: Air.Inst.Index,
     main_tomb: bool,
     operands: [bpi - 1]Air.Inst.Ref,
 ) Allocator.Error!void {
     const table = &a.table;
     const gpa = a.gpa;
 
     var tomb_bits: Bpi = @boolToInt(main_tomb);
     var i = operands.len;
 
     while (i > 0) {
         i -= 1;
         tomb_bits <<= 1;
         const op_int = @enumToInt(operands[i]);
         if (op_int < Air.Inst.Ref.typed_value_map.len) continue;
         const operand: Air.Inst.Index = op_int - @intCast(u32, Air.Inst.Ref.typed_value_map.len);
         const prev = try table.fetchPut(gpa, operand, {});
         if (prev == null) {
             // Death.
             tomb_bits |= 1;
             if (new_set) |ns| try ns.putNoClobber(gpa, operand, {});
         }
     }
     a.storeTombBits(inst, tomb_bits);
 }
 
 const ExtraTombs = struct {
     analysis: *Analysis,
     new_set: ?*std.AutoHashMapUnmanaged(Air.Inst.Index, void),
     inst: Air.Inst.Index,
     main_tomb: bool,
     bit_index: usize = 0,
     tomb_bits: Bpi = 0,
     big_tomb_bits: u32 = 0,
     big_tomb_bits_extra: std.ArrayListUnmanaged(u32) = .{},
 
     fn feed(et: *ExtraTombs, op_ref: Air.Inst.Ref) !void {
         const this_bit_index = et.bit_index;
         et.bit_index += 1;
         const gpa = et.analysis.gpa;
         const op_index = Air.refToIndex(op_ref) orelse return;
         const prev = try et.analysis.table.fetchPut(gpa, op_index, {});
         if (prev == null) {
             // Death.
             if (et.new_set) |ns| try ns.putNoClobber(gpa, op_index, {});
             const available_tomb_bits = bpi - 1;
             if (this_bit_index < available_tomb_bits) {
                 et.tomb_bits |= @as(Bpi, 1) << @intCast(OperandInt, this_bit_index);
             } else {
                 const big_bit_index = this_bit_index - available_tomb_bits;
                 while (big_bit_index >= (et.big_tomb_bits_extra.items.len + 1) * 31) {
                     // We need another element in the extra array.
                     try et.big_tomb_bits_extra.append(gpa, et.big_tomb_bits);
                     et.big_tomb_bits = 0;
                 } else {
                     const final_bit_index = big_bit_index - et.big_tomb_bits_extra.items.len * 31;
                     et.big_tomb_bits |= @as(u32, 1) << @intCast(u5, final_bit_index);
                 }
             }
         }
     }
 
     fn finish(et: *ExtraTombs) !void {
         et.tomb_bits |= @as(Bpi, @boolToInt(et.main_tomb)) << (bpi - 1);
         // Signal the terminal big_tomb_bits element.
         et.big_tomb_bits |= @as(u32, 1) << 31;
 
         et.analysis.storeTombBits(et.inst, et.tomb_bits);
         const extra_index = @intCast(u32, et.analysis.extra.items.len);
         try et.analysis.extra.ensureUnusedCapacity(et.analysis.gpa, et.big_tomb_bits_extra.items.len + 1);
         try et.analysis.special.put(et.analysis.gpa, et.inst, extra_index);
         et.analysis.extra.appendSliceAssumeCapacity(et.big_tomb_bits_extra.items);
         et.analysis.extra.appendAssumeCapacity(et.big_tomb_bits);
     }
 
     fn deinit(et: *ExtraTombs) void {
         et.big_tomb_bits_extra.deinit(et.analysis.gpa);
     }
 };