1//! Verifies that Liveness information is valid.
2
3gpa: std.mem.Allocator,
4zcu: *Zcu,
5air: Air,
6liveness: Liveness,
7live: LiveMap = .{},
8blocks: std.AutoHashMapUnmanaged(Air.Inst.Index, LiveMap) = .empty,
9loops: std.AutoHashMapUnmanaged(Air.Inst.Index, LiveMap) = .empty,
10intern_pool: *const InternPool,
11
12pub const Error = error{ LivenessInvalid, OutOfMemory };
13
14pub fn deinit(self: *Verify) void {
15 self.live.deinit(self.gpa);
16 {
17 var it = self.blocks.valueIterator();
18 while (it.next()) |block| block.deinit(self.gpa);
19 self.blocks.deinit(self.gpa);
20 }
21 {
22 var it = self.loops.valueIterator();
23 while (it.next()) |block| block.deinit(self.gpa);
24 self.loops.deinit(self.gpa);
25 }
26 self.* = undefined;
27}
28
29pub fn verify(self: *Verify) Error!void {
30 self.live.clearRetainingCapacity();
31 self.blocks.clearRetainingCapacity();
32 self.loops.clearRetainingCapacity();
33 try self.verifyBody(self.air.getMainBody());
34 // We don't care about `self.live` now, because the loop body was noreturn - everything being dead was checked on `ret` etc
35 assert(self.blocks.count() == 0);
36 assert(self.loops.count() == 0);
37}
38
39const LiveMap = std.AutoHashMapUnmanaged(Air.Inst.Index, void);
40
41fn verifyBody(self: *Verify, body: []const Air.Inst.Index) Error!void {
42 const ip = self.intern_pool;
43 const tags = self.air.instructions.items(.tag);
44 const data = self.air.instructions.items(.data);
45 for (body) |inst| {
46 if (self.liveness.isUnused(inst) and !self.air.mustLower(inst, ip)) {
47 // This instruction will not be lowered and should be ignored.
48 continue;
49 }
50
51 switch (tags[@backingInt(inst)]) {
52 // no operands
53 .arg,
54 .alloc,
55 .inferred_alloc,
56 .inferred_alloc_comptime,
57 .ret_ptr,
58 .breakpoint,
59 .dbg_stmt,
60 .dbg_empty_stmt,
61 .ret_addr,
62 .frame_addr,
63 .wasm_memory_size,
64 .err_return_trace,
65 .save_err_return_trace_index,
66 .runtime_nav_ptr,
67 .c_va_start,
68 .work_item_id,
69 .work_group_size,
70 .work_group_id,
71 => try self.verifyInstOperands(inst, .{ .none, .none, .none }),
72
73 .trap, .unreach => {
74 try self.verifyInstOperands(inst, .{ .none, .none, .none });
75 // This instruction terminates the function, so everything should be dead
76 if (self.live.count() > 0) return invalid("{f}: instructions still alive", .{inst});
77 },
78
79 // unary
80 .not,
81 .bit_cast,
82 .bit_cast_safe,
83 .ptr_cast,
84 .ptr_from_int,
85 .int_from_ptr,
86 .error_cast,
87 .error_from_int,
88 .int_from_error,
89 .union_from_enum,
90 .load,
91 .fpext,
92 .fptrunc,
93 .int_cast,
94 .int_cast_safe,
95 .trunc,
96 .optional_payload,
97 .optional_payload_ptr,
98 .optional_payload_ptr_set,
99 .errunion_payload_ptr_set,
100 .wrap_optional,
101 .unwrap_errunion_payload,
102 .unwrap_errunion_err,
103 .unwrap_errunion_payload_ptr,
104 .unwrap_errunion_err_ptr,
105 .wrap_errunion_payload,
106 .wrap_errunion_err,
107 .slice_ptr,
108 .slice_len,
109 .ptr_slice_len_ptr,
110 .ptr_slice_ptr_ptr,
111 .struct_field_ptr_index_0,
112 .struct_field_ptr_index_1,
113 .struct_field_ptr_index_2,
114 .struct_field_ptr_index_3,
115 .array_to_slice,
116 .array_to_vector,
117 .int_from_float,
118 .int_from_float_optimized,
119 .int_from_float_safe,
120 .int_from_float_optimized_safe,
121 .float_from_int,
122 .get_union_tag,
123 .clz,
124 .ctz,
125 .popcount,
126 .byte_swap,
127 .bit_reverse,
128 .splat,
129 .error_set_has_value,
130 .addrspace_cast,
131 .c_va_arg,
132 .c_va_copy,
133 .abs,
134 => {
135 const ty_op = data[@backingInt(inst)].ty_op;
136 try self.verifyInstOperands(inst, .{ ty_op.operand, .none, .none });
137 },
138 .is_null,
139 .is_non_null,
140 .is_null_ptr,
141 .is_non_null_ptr,
142 .is_err,
143 .is_non_err,
144 .is_err_ptr,
145 .is_non_err_ptr,
146 .is_named_enum_value,
147 .tag_name,
148 .error_name,
149 .sqrt,
150 .sin,
151 .cos,
152 .tan,
153 .exp,
154 .exp2,
155 .log,
156 .log2,
157 .log10,
158 .floor,
159 .ceil,
160 .round,
161 .trunc_float,
162 .neg,
163 .neg_optimized,
164 .cmp_lte_errors_len,
165 .set_err_return_trace,
166 .c_va_end,
167 => {
168 const un_op = data[@backingInt(inst)].un_op;
169 try self.verifyInstOperands(inst, .{ un_op, .none, .none });
170 },
171 .ret,
172 .ret_safe,
173 .ret_load,
174 => {
175 const un_op = data[@backingInt(inst)].un_op;
176 try self.verifyInstOperands(inst, .{ un_op, .none, .none });
177 // This instruction terminates the function, so everything should be dead
178 if (self.live.count() > 0) return invalid("{f}: instructions still alive", .{inst});
179 },
180 .dbg_var_ptr,
181 .dbg_var_val,
182 .dbg_arg_inline,
183 .wasm_memory_grow,
184 => {
185 const pl_op = data[@backingInt(inst)].pl_op;
186 try self.verifyInstOperands(inst, .{ pl_op.operand, .none, .none });
187 },
188 .prefetch => {
189 const prefetch = data[@backingInt(inst)].prefetch;
190 try self.verifyInstOperands(inst, .{ prefetch.ptr, .none, .none });
191 },
192 .reduce,
193 .reduce_optimized,
194 => {
195 const reduce = data[@backingInt(inst)].reduce;
196 try self.verifyInstOperands(inst, .{ reduce.operand, .none, .none });
197 },
198 .union_init => {
199 const ty_pl = data[@backingInt(inst)].ty_pl;
200 const extra = self.air.extraData(Air.UnionInit, ty_pl.payload).data;
201 try self.verifyInstOperands(inst, .{ extra.init, .none, .none });
202 },
203 .struct_field_ptr, .agg_field_val, .spirv_runtime_array_len => {
204 const ty_pl = data[@backingInt(inst)].ty_pl;
205 const extra = self.air.extraData(Air.StructField, ty_pl.payload).data;
206 try self.verifyInstOperands(inst, .{ extra.struct_operand, .none, .none });
207 },
208 .field_parent_ptr => {
209 const ty_pl = data[@backingInt(inst)].ty_pl;
210 const extra = self.air.extraData(Air.FieldParentPtr, ty_pl.payload).data;
211 try self.verifyInstOperands(inst, .{ extra.field_ptr, .none, .none });
212 },
213 .atomic_load => {
214 const atomic_load = data[@backingInt(inst)].atomic_load;
215 try self.verifyInstOperands(inst, .{ atomic_load.ptr, .none, .none });
216 },
217
218 // binary
219 .add,
220 .add_safe,
221 .add_optimized,
222 .add_wrap,
223 .add_sat,
224 .sub,
225 .sub_safe,
226 .sub_optimized,
227 .sub_wrap,
228 .sub_sat,
229 .mul,
230 .mul_safe,
231 .mul_optimized,
232 .mul_wrap,
233 .mul_sat,
234 .div_float,
235 .div_float_optimized,
236 .div_trunc,
237 .div_trunc_optimized,
238 .div_floor,
239 .div_floor_optimized,
240 .div_ceil,
241 .div_ceil_optimized,
242 .div_exact,
243 .div_exact_optimized,
244 .rem,
245 .rem_optimized,
246 .mod,
247 .mod_optimized,
248 .bit_and,
249 .bit_or,
250 .xor,
251 .cmp_lt,
252 .cmp_lt_optimized,
253 .cmp_lte,
254 .cmp_lte_optimized,
255 .cmp_eq,
256 .cmp_eq_optimized,
257 .cmp_gte,
258 .cmp_gte_optimized,
259 .cmp_gt,
260 .cmp_gt_optimized,
261 .cmp_neq,
262 .cmp_neq_optimized,
263 .store,
264 .store_safe,
265 .array_elem_val,
266 .slice_elem_val,
267 .ptr_elem_val,
268 .shl,
269 .shl_exact,
270 .shl_sat,
271 .shr,
272 .shr_exact,
273 .atomic_store_unordered,
274 .atomic_store_monotonic,
275 .atomic_store_release,
276 .atomic_store_seq_cst,
277 .set_union_tag,
278 .min,
279 .max,
280 .memset,
281 .memset_safe,
282 .memcpy,
283 .memmove,
284 .legalize_vec_elem_val,
285 => {
286 const bin_op = data[@backingInt(inst)].bin_op;
287 try self.verifyInstOperands(inst, .{ bin_op.lhs, bin_op.rhs, .none });
288 },
289 .add_with_overflow,
290 .sub_with_overflow,
291 .mul_with_overflow,
292 .shl_with_overflow,
293 .ptr_add,
294 .ptr_sub,
295 .ptr_elem_ptr,
296 .slice_elem_ptr,
297 .slice,
298 => {
299 const ty_pl = data[@backingInt(inst)].ty_pl;
300 const extra = self.air.extraData(Air.Bin, ty_pl.payload).data;
301 try self.verifyInstOperands(inst, .{ extra.lhs, extra.rhs, .none });
302 },
303 .shuffle_one => {
304 const unwrapped = self.air.unwrapShuffleOne(self.zcu, inst);
305 try self.verifyInstOperands(inst, .{ unwrapped.operand, .none, .none });
306 },
307 .shuffle_two => {
308 const unwrapped = self.air.unwrapShuffleTwo(self.zcu, inst);
309 try self.verifyInstOperands(inst, .{ unwrapped.operand_a, unwrapped.operand_b, .none });
310 },
311 .cmp_vector,
312 .cmp_vector_optimized,
313 => {
314 const ty_pl = data[@backingInt(inst)].ty_pl;
315 const extra = self.air.extraData(Air.VectorCmp, ty_pl.payload).data;
316 try self.verifyInstOperands(inst, .{ extra.lhs, extra.rhs, .none });
317 },
318 .atomic_rmw => {
319 const pl_op = data[@backingInt(inst)].pl_op;
320 const extra = self.air.extraData(Air.AtomicRmw, pl_op.payload).data;
321 try self.verifyInstOperands(inst, .{ pl_op.operand, extra.operand, .none });
322 },
323
324 // ternary
325 .select => {
326 const pl_op = data[@backingInt(inst)].pl_op;
327 const extra = self.air.extraData(Air.Bin, pl_op.payload).data;
328 try self.verifyInstOperands(inst, .{ pl_op.operand, extra.lhs, extra.rhs });
329 },
330 .mul_add => {
331 const pl_op = data[@backingInt(inst)].pl_op;
332 const extra = self.air.extraData(Air.Bin, pl_op.payload).data;
333 try self.verifyInstOperands(inst, .{ extra.lhs, extra.rhs, pl_op.operand });
334 },
335 .cmpxchg_strong,
336 .cmpxchg_weak,
337 => {
338 const ty_pl = data[@backingInt(inst)].ty_pl;
339 const extra = self.air.extraData(Air.Cmpxchg, ty_pl.payload).data;
340 try self.verifyInstOperands(inst, .{ extra.ptr, extra.expected_value, extra.new_value });
341 },
342
343 // big tombs
344 .aggregate_init => {
345 const ty_pl = data[@backingInt(inst)].ty_pl;
346 const aggregate_ty = ty_pl.ty;
347 const len = @as(usize, @intCast(aggregate_ty.arrayLenIp(ip)));
348 const elements = @as([]const Air.Inst.Ref, @ptrCast(self.air.extra.items[ty_pl.payload..][0..len]));
349
350 var bt = self.liveness.iterateBigTomb(inst);
351 for (elements) |element| {
352 try self.verifyOperand(inst, element, bt.feed());
353 }
354 try self.verifyInst(inst);
355 },
356 .call, .call_always_tail, .call_never_tail, .call_never_inline => {
357 const call = self.air.unwrapCall(inst);
358 const args = call.args;
359
360 var bt = self.liveness.iterateBigTomb(inst);
361 try self.verifyOperand(inst, call.callee, bt.feed());
362 for (args) |arg| {
363 try self.verifyOperand(inst, arg, bt.feed());
364 }
365 try self.verifyInst(inst);
366 },
367 .assembly => {
368 const unwrapped_asm = self.air.unwrapAsm(inst);
369
370 var bt = self.liveness.iterateBigTomb(inst);
371 for (unwrapped_asm.outputs) |output| {
372 if (output != .none) {
373 try self.verifyOperand(inst, output, bt.feed());
374 }
375 }
376 for (unwrapped_asm.inputs) |input| {
377 try self.verifyOperand(inst, input, bt.feed());
378 }
379 try self.verifyInst(inst);
380 },
381
382 // control flow
383 .@"try", .try_cold => {
384 const unwrapped_try = self.air.unwrapTry(inst);
385 const try_body = unwrapped_try.else_body;
386
387 const cond_br_liveness = self.liveness.getCondBr(inst);
388
389 try self.verifyOperand(inst, unwrapped_try.error_union, self.liveness.operandDies(inst, 0));
390
391 var live = try self.live.clone(self.gpa);
392 defer live.deinit(self.gpa);
393
394 for (cond_br_liveness.else_deaths) |death| try self.verifyDeath(inst, death);
395 try self.verifyBody(try_body);
396
397 self.live.deinit(self.gpa);
398 self.live = live.move();
399
400 for (cond_br_liveness.then_deaths) |death| try self.verifyDeath(inst, death);
401
402 try self.verifyInst(inst);
403 },
404 .try_ptr, .try_ptr_cold => {
405 const unwrapped_try = self.air.unwrapTryPtr(inst);
406 const try_body = unwrapped_try.else_body;
407
408 const cond_br_liveness = self.liveness.getCondBr(inst);
409
410 try self.verifyOperand(inst, unwrapped_try.error_union_ptr, self.liveness.operandDies(inst, 0));
411
412 var live = try self.live.clone(self.gpa);
413 defer live.deinit(self.gpa);
414
415 for (cond_br_liveness.else_deaths) |death| try self.verifyDeath(inst, death);
416 try self.verifyBody(try_body);
417
418 self.live.deinit(self.gpa);
419 self.live = live.move();
420
421 for (cond_br_liveness.then_deaths) |death| try self.verifyDeath(inst, death);
422
423 try self.verifyInst(inst);
424 },
425 .br => {
426 const br = data[@backingInt(inst)].br;
427 const gop = try self.blocks.getOrPut(self.gpa, br.block_inst);
428
429 try self.verifyOperand(inst, br.operand, self.liveness.operandDies(inst, 0));
430 if (gop.found_existing) {
431 try self.verifyMatchingLiveness(br.block_inst, gop.value_ptr.*);
432 } else {
433 gop.value_ptr.* = try self.live.clone(self.gpa);
434 }
435 try self.verifyInst(inst);
436 },
437 .repeat => {
438 const repeat = data[@backingInt(inst)].repeat;
439 const expected_live = self.loops.get(repeat.loop_inst) orelse
440 return invalid("{f}: loop {f} not in scope", .{ inst, repeat.loop_inst });
441
442 try self.verifyMatchingLiveness(repeat.loop_inst, expected_live);
443 },
444 .switch_dispatch => {
445 const br = data[@backingInt(inst)].br;
446
447 try self.verifyOperand(inst, br.operand, self.liveness.operandDies(inst, 0));
448
449 const expected_live = self.loops.get(br.block_inst) orelse
450 return invalid("{f}: loop {f} not in scope", .{ inst, br.block_inst });
451
452 try self.verifyMatchingLiveness(br.block_inst, expected_live);
453 },
454 .block, .dbg_inline_block => |tag| {
455 const ty_pl = data[@backingInt(inst)].ty_pl;
456 const block_ty = ty_pl.ty;
457 const block_body = switch (tag) {
458 .block => self.air.unwrapBlock(inst).body,
459 .dbg_inline_block => self.air.unwrapDbgBlock(inst).body,
460 else => unreachable,
461 };
462 const block_liveness = self.liveness.getBlock(inst);
463
464 var orig_live = try self.live.clone(self.gpa);
465 defer orig_live.deinit(self.gpa);
466
467 assert(!self.blocks.contains(inst));
468 try self.verifyBody(block_body);
469
470 // Liveness data after the block body is garbage, but we want to
471 // restore it to verify deaths
472 self.live.deinit(self.gpa);
473 self.live = orig_live.move();
474
475 for (block_liveness.deaths) |death| try self.verifyDeath(inst, death);
476
477 if (block_ty.isNoReturn(self.zcu)) {
478 assert(!self.blocks.contains(inst));
479 } else {
480 var live = if (self.blocks.fetchRemove(inst)) |kv| kv.value else {
481 return invalid(
482 "{f}: block of type '{f}' not terminated correctly",
483 .{ inst, block_ty.fmtDebug() },
484 );
485 };
486 defer live.deinit(self.gpa);
487
488 try self.verifyMatchingLiveness(inst, live);
489 }
490
491 try self.verifyInstOperands(inst, .{ .none, .none, .none });
492 },
493 .loop => {
494 const block = self.air.unwrapBlock(inst);
495
496 // The same stuff should be alive after the loop as before it.
497 const gop = try self.loops.getOrPut(self.gpa, inst);
498 if (gop.found_existing) return invalid("{f}: loop already exists", .{inst});
499 defer {
500 var live = self.loops.fetchRemove(inst).?;
501 live.value.deinit(self.gpa);
502 }
503 gop.value_ptr.* = try self.live.clone(self.gpa);
504
505 try self.verifyBody(block.body);
506
507 try self.verifyInstOperands(inst, .{ .none, .none, .none });
508 },
509 .cond_br => {
510 const cond_br = self.air.unwrapCondBr(inst);
511 const then_body = cond_br.then_body;
512 const else_body = cond_br.else_body;
513 const cond_br_liveness = self.liveness.getCondBr(inst);
514
515 try self.verifyOperand(inst, cond_br.condition, self.liveness.operandDies(inst, 0));
516
517 var live = try self.live.clone(self.gpa);
518 defer live.deinit(self.gpa);
519
520 for (cond_br_liveness.then_deaths) |death| try self.verifyDeath(inst, death);
521 try self.verifyBody(then_body);
522
523 self.live.deinit(self.gpa);
524 self.live = live.move();
525
526 for (cond_br_liveness.else_deaths) |death| try self.verifyDeath(inst, death);
527 try self.verifyBody(else_body);
528
529 try self.verifyInst(inst);
530 },
531 .switch_br, .loop_switch_br => {
532 const switch_br = self.air.unwrapSwitch(inst);
533 const switch_br_liveness = try self.liveness.getSwitchBr(
534 self.gpa,
535 inst,
536 switch_br.cases_len + 1,
537 );
538 defer self.gpa.free(switch_br_liveness.deaths);
539
540 try self.verifyOperand(inst, switch_br.operand, self.liveness.operandDies(inst, 0));
541
542 // Excluding the operand (which we just handled), the same stuff should be alive
543 // after the loop as before it.
544 {
545 const gop = try self.loops.getOrPut(self.gpa, inst);
546 if (gop.found_existing) return invalid("{f}: loop already exists", .{inst});
547 gop.value_ptr.* = self.live.move();
548 }
549 defer {
550 var live = self.loops.fetchRemove(inst).?;
551 live.value.deinit(self.gpa);
552 }
553
554 var it = switch_br.iterateCases();
555 while (it.next()) |case| {
556 self.live.deinit(self.gpa);
557 self.live = try self.loops.get(inst).?.clone(self.gpa);
558
559 for (switch_br_liveness.deaths[case.idx]) |death| try self.verifyDeath(inst, death);
560 try self.verifyBody(case.body);
561 }
562
563 const else_body = it.elseBody();
564 if (else_body.len > 0) {
565 self.live.deinit(self.gpa);
566 self.live = try self.loops.get(inst).?.clone(self.gpa);
567 for (switch_br_liveness.deaths[switch_br.cases_len]) |death| try self.verifyDeath(inst, death);
568 try self.verifyBody(else_body);
569 }
570
571 try self.verifyInst(inst);
572 },
573 .legalize_vec_store_elem => {
574 const pl_op = data[@backingInt(inst)].pl_op;
575 const bin = self.air.extraData(Air.Bin, pl_op.payload).data;
576 try self.verifyInstOperands(inst, .{ pl_op.operand, bin.lhs, bin.rhs });
577 },
578 .legalize_compiler_rt_call => {
579 const rt_call = self.air.unwrapCompilerRtCall(inst);
580 const args = rt_call.args;
581 var bt = self.liveness.iterateBigTomb(inst);
582 for (args) |arg| {
583 try self.verifyOperand(inst, arg, bt.feed());
584 }
585 try self.verifyInst(inst);
586 },
587 }
588 }
589}
590
591fn verifyDeath(self: *Verify, inst: Air.Inst.Index, operand: Air.Inst.Index) Error!void {
592 try self.verifyOperand(inst, operand.toRef(), true);
593}
594
595fn verifyOperand(self: *Verify, inst: Air.Inst.Index, op_ref: Air.Inst.Ref, dies: bool) Error!void {
596 const operand = op_ref.toIndexAllowNone() orelse {
597 assert(!dies);
598 return;
599 };
600 if (dies) {
601 if (!self.live.remove(operand)) return invalid("{f}: dead operand {f} reused and killed again", .{
602 inst, operand,
603 });
604 } else {
605 if (!self.live.contains(operand)) return invalid("{f}: dead operand {f} reused", .{ inst, operand });
606 }
607}
608
609fn verifyInstOperands(
610 self: *Verify,
611 inst: Air.Inst.Index,
612 operands: [Liveness.bpi - 1]Air.Inst.Ref,
613) Error!void {
614 for (operands, 0..) |operand, operand_index| {
615 const dies = self.liveness.operandDies(inst, @as(Liveness.OperandInt, @intCast(operand_index)));
616 try self.verifyOperand(inst, operand, dies);
617 }
618 try self.verifyInst(inst);
619}
620
621fn verifyInst(self: *Verify, inst: Air.Inst.Index) Error!void {
622 if (self.liveness.isUnused(inst)) {
623 assert(!self.live.contains(inst));
624 } else {
625 try self.live.putNoClobber(self.gpa, inst, {});
626 }
627}
628
629fn verifyMatchingLiveness(self: *Verify, block: Air.Inst.Index, live: LiveMap) Error!void {
630 if (self.live.count() != live.count()) return invalid("{f}: different deaths across branches", .{block});
631 var live_it = self.live.keyIterator();
632 while (live_it.next()) |live_inst| if (!live.contains(live_inst.*)) return invalid("{f}: different deaths across branches", .{block});
633}
634
635fn invalid(comptime fmt: []const u8, args: anytype) error{LivenessInvalid} {
636 log.err(fmt, args);
637 return error.LivenessInvalid;
638}
639
640const std = @import("std");
641const assert = std.debug.assert;
642const log = std.log.scoped(.liveness_verify);
643
644const Air = @import("../../Air.zig");
645const Liveness = @import("../Liveness.zig");
646const InternPool = @import("../../InternPool.zig");
647const Zcu = @import("../../Zcu.zig");
648const Verify = @This();