kit

pass_analysis.c (31986B)

---

 #include <string.h>
 
 #include "core/arena.h"
 #include "core/core.h"
 #include "core/slice.h"
 #include "opt/opt_internal.h"
 
 #define OPT_BLK_NONE 0xffffffffu
 
 #ifndef NDEBUG
 static SrcLoc opt_no_loc(void) {
   SrcLoc loc = {0, 0, 0};
   return loc;
 }
 
 static void opt_fail(Func* f, const char* stage, const char* msg, u32 a,
                      u32 b) {
   compiler_panic(f->c, opt_no_loc(), "opt verify[%.*s]: %.*s (%u, %u)",
                  SLICE_ARG(slice_from_cstr(stage ? stage : "?")),
                  SLICE_ARG(slice_from_cstr(msg)), (unsigned)a, (unsigned)b);
 }
 
 /* Does `hay` contain the bytes of NUL-terminated `needle`? Length-explicit
  * substring search; no strstr. */
 static int slice_contains_cstr(Slice hay, const char* needle) {
   Slice n = slice_from_cstr(needle);
   size_t i;
   if (n.len == 0) return 1;
   if (hay.len < n.len) return 0;
   for (i = 0; i + n.len <= hay.len; ++i)
     if (memcmp(hay.s + i, n.s, n.len) == 0) return 1;
   return 0;
 }
 
 static int verify_stage_is_ssa(const char* stage) {
   Slice s = slice_from_cstr(stage);
   return stage && slice_contains_cstr(s, "ssa") &&
          !slice_contains_cstr(s, "pre-ssa");
 }
 
 static u8 verify_type_reg_class(Func* f, KitCgTypeId ty) {
   return opt_value_reg_class(f->c, ty);
 }
 
 static void verify_frame_slot(Func* f, const char* stage, FrameSlot slot,
                               const char* msg) {
   if (slot == FRAME_SLOT_NONE || slot > f->nframe_slots)
     opt_fail(f, stage, msg, slot, f->nframe_slots);
 }
 
 static void verify_storage(Func* f, const char* stage, CGLocalStorage st,
                            KitCgTypeId type, u8 expect_cls, const char* msg) {
   switch ((CGLocalStorageKind)st.kind) {
     case CG_LOCAL_STORAGE_FRAME:
       verify_frame_slot(f, stage, st.v.frame_slot, msg);
       break;
     case CG_LOCAL_STORAGE_REG: {
       PReg r = (PReg)st.v.reg;
       if (r == PREG_NONE || r == 0 || r >= opt_reg_count(f))
         opt_fail(f, stage, msg, r, opt_reg_count(f));
       if (!f->opt_reg_ssa && f->preg_cls && f->preg_cls[r] != expect_cls)
         opt_fail(f, stage, "storage class mismatch", r, f->preg_cls[r]);
       if (!f->opt_reg_ssa && type && f->preg_type && f->preg_type[r] &&
           f->preg_type[r] != type)
         opt_fail(f, stage, "storage type mismatch", r, type);
       break;
     }
     default:
       opt_fail(f, stage, "bad storage kind", st.kind, 0);
       break;
   }
 }
 
 static void verify_operand_shape(Func* f, const char* stage, const Operand* op,
                                  int physical_regs) {
   if (!op) return;
   switch ((OptOperandKind)op->kind) {
     case OPK_IMM:
     case OPK_GLOBAL:
       break;
     case OPK_LOCAL:
       verify_frame_slot(f, stage, op->v.frame_slot, "bad local frame slot");
       break;
     case OPK_REG:
       if (op->cls >= OPT_REG_CLASSES)
         opt_fail(f, stage, "bad operand class", op->cls, OPT_REG_CLASSES);
       if (physical_regs) {
         if (op->v.reg == (Reg)REG_NONE || op->v.reg >= OPT_MAX_HARD_REGS)
           opt_fail(f, stage, "bad physical operand reg", op->v.reg,
                    OPT_MAX_HARD_REGS);
       }
       break;
     case OPK_INDIRECT:
       if (op->cls >= OPT_REG_CLASSES)
         opt_fail(f, stage, "bad indirect class", op->cls, OPT_REG_CLASSES);
       if (physical_regs) {
         if (op->v.ind.base == (Reg)REG_NONE ||
             op->v.ind.base >= OPT_MAX_HARD_REGS)
           opt_fail(f, stage, "bad physical indirect base", op->v.ind.base,
                    OPT_MAX_HARD_REGS);
         if (op->v.ind.index != (Reg)REG_NONE &&
             op->v.ind.index >= OPT_MAX_HARD_REGS)
           opt_fail(f, stage, "bad physical indirect index", op->v.ind.index,
                    OPT_MAX_HARD_REGS);
       }
       break;
     default:
       opt_fail(f, stage, "bad operand kind", op->kind, 0);
       break;
   }
 }
 
 static void verify_abivalue_shape(Func* f, const char* stage, CGABIValue* v,
                                   int physical_regs) {
   if (!v) return;
   verify_operand_shape(f, stage, &v->storage, physical_regs);
   for (u32 i = 0; i < v->nparts; ++i)
     verify_operand_shape(f, stage, &v->parts[i].op, physical_regs);
 }
 
 static void verify_call_plan_shape(Func* f, const char* stage, CGCallPlan* plan,
                                    int physical_regs) {
   if (!plan) return;
   verify_operand_shape(f, stage, &plan->callee, physical_regs);
   for (u32 i = 0; i < plan->nargs; ++i) {
     verify_operand_shape(f, stage, &plan->args[i].src, physical_regs);
     if (plan->args[i].dst_kind == CG_CALL_PLAN_REG &&
         plan->args[i].dst_reg >= OPT_MAX_HARD_REGS)
       opt_fail(f, stage, "bad call-plan dst reg", plan->args[i].dst_reg,
                OPT_MAX_HARD_REGS);
   }
   for (u32 i = 0; i < plan->nrets; ++i) {
     verify_operand_shape(f, stage, &plan->rets[i].dst, physical_regs);
     if (plan->rets[i].src_reg >= OPT_MAX_HARD_REGS)
       opt_fail(f, stage, "bad call-plan ret reg", plan->rets[i].src_reg,
                OPT_MAX_HARD_REGS);
   }
 }
 
 static void verify_aux_shapes(Func* f, const char* stage, Inst* in,
                               int physical_regs) {
   switch ((IROp)in->op) {
     case IR_CALL: {
       IRCallAux* aux = (IRCallAux*)in->extra.aux;
       if (!aux) break;
       if (aux->use_plan_replay) {
         verify_call_plan_shape(f, stage, &aux->plan, physical_regs);
       } else {
         verify_operand_shape(f, stage, &aux->desc.callee, physical_regs);
         for (u32 i = 0; i < aux->desc.nargs; ++i)
           verify_abivalue_shape(f, stage, (CGABIValue*)&aux->desc.args[i],
                                 physical_regs);
         verify_abivalue_shape(f, stage, &aux->desc.ret, physical_regs);
       }
       break;
     }
     case IR_RET: {
       IRRetAux* aux = (IRRetAux*)in->extra.aux;
       if (aux && aux->present)
         verify_abivalue_shape(f, stage, &aux->val, physical_regs);
       break;
     }
     case IR_SCOPE_BEGIN:
       break;
     case IR_ASM_BLOCK: {
       IRAsmAux* aux = (IRAsmAux*)in->extra.aux;
       if (!aux) break;
       for (u32 i = 0; i < aux->nin; ++i)
         verify_operand_shape(f, stage, &aux->in_ops[i], physical_regs);
       for (u32 i = 0; i < aux->nout; ++i)
         verify_operand_shape(f, stage, &aux->out_ops[i], physical_regs);
       break;
     }
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (!aux) break;
       for (u32 i = 0; i < aux->narg; ++i)
         verify_operand_shape(f, stage, &aux->args[i], physical_regs);
       for (u32 i = 0; i < aux->ndst; ++i)
         verify_operand_shape(f, stage, &aux->dsts[i], physical_regs);
       break;
     }
     default:
       break;
   }
 }
 #endif
 
 void opt_analysis_mark_valid(Func* f, u32 flags) {
   if (!f) return;
   f->opt_valid_analyses |= flags;
 }
 
 void opt_analysis_invalidate(Func* f, u32 flags) {
   if (!f) return;
   f->opt_valid_analyses &= ~flags;
 }
 
 int opt_analysis_has(Func* f, u32 flags) {
   return f && (f->opt_valid_analyses & flags) == flags;
 }
 
 static void block_list_add(Arena* arena, OptBlockList* list, u32 block) {
   if (list->n == list->cap) {
     u32 ncap = list->cap ? list->cap * 2u : 4u;
     u32* items = arena_array(arena, u32, ncap);
     if (list->items) memcpy(items, list->items, sizeof(items[0]) * list->n);
     list->items = items;
     list->cap = ncap;
   }
   list->items[list->n++] = block;
 }
 
 static void block_list_add_unique(Arena* arena, OptBlockList* list, u32 block) {
   for (u32 i = 0; i < list->n; ++i)
     if (list->items[i] == block) return;
   block_list_add(arena, list, block);
 }
 
 /* The label-addr target block reachable from one instruction, if any
  * (computed gotos / local static-data label addresses keep their target block
  * live). Returns 1 and sets *out when the inst names a target. */
 static int order_inst_label_target(const Inst* in, u32* out) {
   switch ((IROp)in->op) {
     case IR_LOAD_LABEL_ADDR:
       *out = (u32)in->extra.imm;
       return 1;
     case IR_LOCAL_STATIC_DATA_LABEL_ADDR: {
       CgIrLocalStaticLabelAux* aux = (CgIrLocalStaticLabelAux*)in->extra.aux;
       if (!aux) return 0;
       *out = (u32)aux->target;
       return 1;
     }
     default:
       return 0;
   }
 }
 
 /* One in-progress DFS frame: the block plus cursors into its successor list
  * and instruction stream (the two child sources, walked in that order). */
 typedef struct OrderFrame {
   u32 block;
   u32 succ_i;
   u32 inst_i;
 } OrderFrame;
 
 /* Iterative post-order DFS over the block graph: successors first, then the
  * label-addr targets in instruction order, recording the block once its
  * children are exhausted. An explicit stack replaces recursion so a deeply
  * linear CFG cannot overflow the C stack; the visit/mark/emit sequence is
  * identical to the former recursive walk, so the post-order (and the
  * dominance/RPO numbering derived from it) is unchanged. */
 static void order_dfs(OptAnalysis* a, u32 entry) {
   OrderFrame* stack;
   u32 sp = 0;
   if (entry >= a->nblocks || a->reachable[entry]) return;
   stack = arena_array(a->arena, OrderFrame, a->nblocks);
   a->reachable[entry] = 1;
   stack[sp].block = entry;
   stack[sp].succ_i = 0;
   stack[sp].inst_i = 0;
   ++sp;
   while (sp > 0) {
     OrderFrame* fr = &stack[sp - 1];
     Block* bl = &a->f->blocks[fr->block];
     int pushed = 0;
     while (fr->succ_i < bl->nsucc) {
       u32 c = bl->succ[fr->succ_i++];
       if (c < a->nblocks && !a->reachable[c]) {
         a->reachable[c] = 1;
         stack[sp].block = c;
         stack[sp].succ_i = 0;
         stack[sp].inst_i = 0;
         ++sp;
         pushed = 1;
         break;
       }
     }
     if (pushed) continue;
     while (fr->inst_i < bl->ninsts) {
       u32 c;
       if (order_inst_label_target(&bl->insts[fr->inst_i++], &c) &&
           c < a->nblocks && !a->reachable[c]) {
         a->reachable[c] = 1;
         stack[sp].block = c;
         stack[sp].succ_i = 0;
         stack[sp].inst_i = 0;
         ++sp;
         pushed = 1;
         break;
       }
     }
     if (pushed) continue;
     a->po[a->npo] = fr->block;
     a->po_index[fr->block] = a->npo;
     ++a->npo;
     --sp;
   }
 }
 
 void opt_analysis_build_order(Func* f, OptAnalysis* a) {
   memset(a, 0, sizeof *a);
   a->arena = f->arena;
   a->f = f;
   a->nblocks = f->nblocks;
   a->entry = f->entry;
   u32 n = f->nblocks ? f->nblocks : 1u;
   a->po = arena_array(f->arena, u32, n);
   a->rpo = arena_array(f->arena, u32, n);
   a->po_index = arena_array(f->arena, u32, n);
   a->reachable = arena_zarray(f->arena, u8, n);
   for (u32 i = 0; i < n; ++i) a->po_index[i] = OPT_BLK_NONE;
   if (f->entry < f->nblocks) order_dfs(a, f->entry);
   a->nrpo = a->npo;
   for (u32 i = 0; i < a->npo; ++i) a->rpo[i] = a->po[a->npo - 1u - i];
 }
 
 static u32 dom_intersect(u32 b1, u32 b2, const u32* idom, const u32* po_index) {
   while (b1 != b2) {
     while (po_index[b1] < po_index[b2]) b1 = idom[b1];
     while (po_index[b2] < po_index[b1]) b2 = idom[b2];
   }
   return b1;
 }
 
 void opt_analysis_build_dominators(Func* f, OptAnalysis* a) {
   if (!a->reachable) opt_analysis_build_order(f, a);
   u32 n = f->nblocks ? f->nblocks : 1u;
   a->idom = arena_array(f->arena, u32, n);
   a->dom_children = arena_zarray(f->arena, OptBlockList, n);
   for (u32 i = 0; i < n; ++i) a->idom[i] = OPT_BLK_NONE;
   if (f->entry >= f->nblocks || !a->reachable[f->entry]) {
     opt_analysis_mark_valid(f, OPT_ANALYSIS_DOM);
     return;
   }
   a->idom[f->entry] = f->entry;
 
   int changed = 1;
   while (changed) {
     changed = 0;
     for (u32 ri = 0; ri < a->nrpo; ++ri) {
       u32 b = a->rpo[ri];
       if (b == f->entry) continue;
       Block* bl = &f->blocks[b];
       u32 new_idom = OPT_BLK_NONE;
       for (u32 p = 0; p < bl->npreds; ++p) {
         u32 pred = bl->preds[p];
         if (pred >= f->nblocks || !a->reachable[pred]) continue;
         if (a->idom[pred] == OPT_BLK_NONE) continue;
         new_idom = new_idom == OPT_BLK_NONE
                        ? pred
                        : dom_intersect(pred, new_idom, a->idom, a->po_index);
       }
       if (new_idom != OPT_BLK_NONE && a->idom[b] != new_idom) {
         a->idom[b] = new_idom;
         changed = 1;
       }
     }
   }
 
   for (u32 i = 0; i < a->npo; ++i) {
     u32 b = a->po[i];
     u32 idom = a->idom[b];
     if (idom == OPT_BLK_NONE || idom == b) continue;
     block_list_add(f->arena, &a->dom_children[idom], b);
   }
   opt_analysis_mark_valid(f, OPT_ANALYSIS_DOM);
 }
 
 void opt_analysis_build_dom_frontier(Func* f, OptAnalysis* a) {
   if (!a->idom) opt_analysis_build_dominators(f, a);
   u32 n = f->nblocks ? f->nblocks : 1u;
   a->dom_frontier = arena_zarray(f->arena, OptBlockList, n);
   for (u32 i = 0; i < a->npo; ++i) {
     u32 b = a->po[i];
     Block* bl = &f->blocks[b];
     if (bl->npreds < 2 || a->idom[b] == OPT_BLK_NONE) continue;
     for (u32 p = 0; p < bl->npreds; ++p) {
       u32 runner = bl->preds[p];
       while (runner != OPT_BLK_NONE && runner != a->idom[b]) {
         block_list_add_unique(f->arena, &a->dom_frontier[runner], b);
         runner = a->idom[runner];
       }
     }
   }
 }
 
 int opt_analysis_dominates(const OptAnalysis* a, u32 dom, u32 node) {
   if (!a || !a->idom || dom >= a->nblocks || node >= a->nblocks) return 0;
   if (!a->reachable || !a->reachable[dom] || !a->reachable[node]) return 0;
   u32 cur = node;
   while (cur != OPT_BLK_NONE) {
     if (cur == dom) return 1;
     if (cur == a->entry) break;
     cur = a->idom[cur];
   }
   return 0;
 }
 
 #ifndef NDEBUG
 static int block_has_pred(const Block* bl, u32 pred) {
   for (u32 i = 0; i < bl->npreds; ++i)
     if (bl->preds[i] == pred) return 1;
   return 0;
 }
 
 static int block_has_succ(const Block* bl, u32 succ) {
   for (u32 i = 0; i < bl->nsucc; ++i)
     if (bl->succ[i] == succ) return 1;
   return 0;
 }
 
 static int fixed_terminator_succ_count(const Inst* in, u32* count_out) {
   switch ((IROp)in->op) {
     case IR_RET:
     case IR_UNREACHABLE:
       *count_out = 0;
       return 1;
     case IR_BR:
     case IR_BREAK_TO:
     case IR_CONTINUE_TO:
       *count_out = 1;
       return 1;
     case IR_CONDBR:
     case IR_CMP_BRANCH:
       *count_out = 2;
       return 1;
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (aux && (aux->kind == INTRIN_LONGJMP || aux->kind == INTRIN_TRAP)) {
         *count_out = 0;
         return 1;
       }
       return 0;
     }
     default:
       return 0;
   }
 }
 #endif /* !NDEBUG (verify-only helpers) */
 
 static void opt_use_add(Func* f, Val v, u32 b, u32 i, u8 kind, u32 op_idx,
                         u32 pred_idx, Operand* op) {
   if (v == VAL_NONE || v >= f->nvals) return;
   if (f->opt_nuses == f->opt_uses_cap) {
     u32 ncap = f->opt_uses_cap ? f->opt_uses_cap * 2u : 32u;
     OptUse* uses = arena_zarray(f->arena, OptUse, ncap);
     if (f->opt_uses) memcpy(uses, f->opt_uses, sizeof(uses[0]) * f->opt_nuses);
     f->opt_uses = uses;
     f->opt_uses_cap = ncap;
   }
   u32 id = f->opt_nuses++;
   OptUse* u = &f->opt_uses[id];
   u->val = v;
   u->block = b;
   u->inst = i;
   u->inst_id = f->blocks[b].insts[i].id;
   u->kind = kind;
   u->operand_index = op_idx;
   u->phi_pred_index = pred_idx;
   u->operand = op;
   u->next_for_val = f->opt_first_use_by_val[v];
   f->opt_first_use_by_val[v] = id;
 }
 
 static void opt_use_add_operand(Func* f, u32 b, u32 i, u32 op_idx, Operand* op,
                                 int is_def) {
   if (!op || is_def) return;
   if (op->kind == OPK_REG) {
     opt_use_add(f, (Val)op->v.reg, b, i, OPT_USE_OPERAND, op_idx, OPT_USE_NONE,
                 op);
   } else if (op->kind == OPK_INDIRECT) {
     opt_use_add(f, (Val)op->v.ind.base, b, i, OPT_USE_INDIRECT_BASE, op_idx,
                 OPT_USE_NONE, op);
     if (op->v.ind.index != (Reg)REG_NONE) {
       opt_use_add(f, (Val)op->v.ind.index, b, i, OPT_USE_INDIRECT_INDEX, op_idx,
                   OPT_USE_NONE, op);
     }
   }
 }
 
 static void opt_use_add_abivalue(Func* f, u32 b, u32 i, CGABIValue* v,
                                  int storage_def) {
   if (!v) return;
   opt_use_add_operand(f, b, i, OPT_USE_NONE, &v->storage, storage_def);
   for (u32 p = 0; p < v->nparts; ++p)
     opt_use_add_operand(f, b, i, p, (Operand*)&v->parts[p].op, storage_def);
 }
 
 static int collect_operand_index_is_def(const Inst* in, u32 i) {
   if (!in || i >= in->nopnds || in->opnds[i].kind != OPK_REG) return 0;
   if (!opt_val_in_inst_defs(in, (Val)in->opnds[i].v.reg)) return 0;
   switch ((IROp)in->op) {
     case IR_ATOMIC_CAS:
       return i == 0 || i == 1;
     default:
       return i == 0;
   }
 }
 
 static void opt_collect_inst_uses(Func* f, u32 b, u32 i, Inst* in) {
   for (u32 o = 0; o < in->nopnds; ++o) {
     int is_def = collect_operand_index_is_def(in, o);
     opt_use_add_operand(f, b, i, o, &in->opnds[o], is_def);
   }
 
   switch ((IROp)in->op) {
     case IR_PHI: {
       IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
       if (!aux) break;
       for (u32 p = 0; p < aux->npreds; ++p)
         opt_use_add(f, aux->pred_vals[p], b, i, OPT_USE_PHI_INPUT, OPT_USE_NONE,
                     p, NULL);
       break;
     }
     case IR_CALL: {
       IRCallAux* aux = (IRCallAux*)in->extra.aux;
       if (!aux) break;
       if (aux->use_plan_replay) {
         opt_use_add_operand(f, b, i, OPT_USE_NONE, &aux->plan.callee, 0);
         for (u32 a = 0; a < aux->plan.nargs; ++a)
           opt_use_add_operand(f, b, i, a, &aux->plan.args[a].src, 0);
       } else {
         opt_use_add_operand(f, b, i, OPT_USE_NONE, &aux->desc.callee, 0);
         for (u32 a = 0; a < aux->desc.nargs; ++a)
           opt_use_add_abivalue(f, b, i, (CGABIValue*)&aux->desc.args[a], 0);
       }
       break;
     }
     case IR_RET: {
       IRRetAux* aux = (IRRetAux*)in->extra.aux;
       if (aux && aux->present) opt_use_add_abivalue(f, b, i, &aux->val, 0);
       break;
     }
     case IR_SCOPE_BEGIN:
       break;
     case IR_ASM_BLOCK: {
       IRAsmAux* aux = (IRAsmAux*)in->extra.aux;
       if (!aux) break;
       for (u32 a = 0; a < aux->nin; ++a)
         opt_use_add_operand(f, b, i, a, &aux->in_ops[a], 0);
       break;
     }
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (!aux) break;
       for (u32 a = 0; a < aux->narg; ++a)
         opt_use_add_operand(f, b, i, a, &aux->args[a], 0);
       break;
     }
     default:
       break;
   }
 }
 
 void opt_rebuild_def_use(Func* f) {
   u32 nheads;
   if (!f) return;
   f->opt_nuses = 0;
   nheads = f->nvals ? f->nvals : 1u;
   if (nheads > f->opt_first_use_by_val_cap) {
     u32 ncap = f->opt_first_use_by_val_cap ? f->opt_first_use_by_val_cap : 16u;
     while (ncap < nheads) ncap *= 2u;
     f->opt_first_use_by_val = arena_array(f->arena, u32, ncap);
     f->opt_first_use_by_val_cap = ncap;
   }
   for (u32 v = 0; v < f->nvals; ++v) f->opt_first_use_by_val[v] = OPT_USE_NONE;
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     for (u32 i = 0; i < bl->ninsts; ++i)
       opt_collect_inst_uses(f, b, i, &bl->insts[i]);
   }
   opt_analysis_mark_valid(f, OPT_ANALYSIS_DEF_USE);
 }
 
 #ifndef NDEBUG
 static void verify_operand(Func* f, Inst* in, Operand* op, int is_def,
                            void* arg) {
   (void)in;
   const char* stage = (const char*)arg;
   if (op->kind != OPK_REG) return;
   Val v = (Val)op->v.reg;
   u32 nregs = verify_stage_is_ssa(stage) ? f->nvals : opt_reg_count(f);
   if (v == VAL_NONE || v >= nregs)
     opt_fail(f, stage, is_def ? "bad def val" : "bad use val", v, nregs);
   if (!verify_stage_is_ssa(stage)) return;
   if (op->cls != f->val_cls[v])
     opt_fail(f, stage, is_def ? "def class mismatch" : "use class mismatch", v,
              op->cls);
 }
 
 static void verify_values(Func* f, const char* stage) {
   if (f->opt_rewritten) return;
   u32 inst_cap = f->next_inst_id ? f->next_inst_id : 1u;
   u8* seen_inst = arena_zarray(f->arena, u8, inst_cap);
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     for (u32 i = 0; i < bl->ninsts; ++i) {
       Inst* in = &bl->insts[i];
       if (in->id == INST_ID_NONE || in->id >= f->next_inst_id)
         opt_fail(f, stage, "bad inst id", b, i);
       if (seen_inst[in->id]) opt_fail(f, stage, "duplicate inst id", in->id, b);
       seen_inst[in->id] = 1;
       if (in->def != VAL_NONE) {
         u32 ndefs = verify_stage_is_ssa(stage) ? f->nvals : opt_reg_count(f);
         if (in->def >= ndefs) opt_fail(f, stage, "bad inst def", b, i);
         if (verify_stage_is_ssa(stage) && (IROp)in->op == IR_PHI && in->type &&
             f->val_type[in->def] && in->type != f->val_type[in->def])
           opt_fail(f, stage, "inst def type mismatch", in->def, b);
       }
       for (u32 d = 0; d < in->ndefs; ++d) {
         Val v = in->defs[d];
         u32 ndefs = verify_stage_is_ssa(stage) ? f->nvals : opt_reg_count(f);
         if (v == VAL_NONE || v >= ndefs)
           opt_fail(f, stage, "bad inst multi-def", b, d);
       }
       for (u32 o = 0; o < in->nopnds; ++o)
         verify_operand_shape(f, stage, &in->opnds[o], 0);
       verify_aux_shapes(f, stage, in, 0);
       opt_walk_inst_operands(f, in, verify_operand, (void*)stage);
       if ((IROp)in->op == IR_PHI) {
         IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
         if (!aux) opt_fail(f, stage, "phi missing aux", b, i);
         if (in->def == VAL_NONE) opt_fail(f, stage, "phi missing def", b, i);
         if (in->nopnds || in->opnds)
           opt_fail(f, stage, "phi should not carry operands", b, i);
         if (aux->slot_id > f->nframe_slots)
           opt_fail(f, stage, "phi bad slot id", aux->slot_id, f->nframe_slots);
         if (aux->reg_id != 0 && aux->reg_id >= f->npregs)
           opt_fail(f, stage, "phi bad reg id", aux->reg_id, f->npregs);
         if (aux->npreds != bl->npreds)
           opt_fail(f, stage, "phi pred count mismatch", aux->npreds,
                    bl->npreds);
         for (u32 p = 0; p < aux->npreds; ++p) {
           if (p >= bl->npreds || aux->pred_blocks[p] != bl->preds[p])
             opt_fail(f, stage, "phi pred block mismatch", b, p);
           if (aux->pred_vals[p] != VAL_NONE && aux->pred_vals[p] >= f->nvals)
             opt_fail(f, stage, "phi bad pred value", aux->pred_vals[p],
                      f->nvals);
           if (aux->pred_vals[p] != VAL_NONE && f->val_type[aux->pred_vals[p]] &&
               f->val_type[aux->pred_vals[p]] != in->type)
             opt_fail(f, stage, "phi input type mismatch", b, p);
         }
       } else if ((IROp)in->op == IR_PARAM_DECL) {
         IRParamDeclAux* aux = (IRParamDeclAux*)in->extra.aux;
         if (in->nopnds || in->opnds)
           opt_fail(f, stage, "param_decl should not carry operands", b, i);
         if ((!aux || aux->desc.storage.kind == CG_LOCAL_STORAGE_REG) &&
             in->def == VAL_NONE)
           opt_fail(f, stage, "param_decl missing def", b, i);
       }
     }
   }
 }
 
 static void verify_function_storage(Func* f, const char* stage) {
   for (u32 i = 0; i < f->nframe_slots; ++i) {
     IRFrameSlot* s = &f->frame_slots[i];
     if (s->id != i + 1u) opt_fail(f, stage, "frame slot id mismatch", s->id, i);
     if (s->kind > FS_SPILL)
       opt_fail(f, stage, "bad frame slot kind", s->kind, i);
   }
   for (u32 i = 0; i < f->nparams; ++i) {
     IRParam* p = &f->params[i];
     u8 cls = verify_type_reg_class(f, p->type);
     if (p->index != i) opt_fail(f, stage, "param index mismatch", p->index, i);
     verify_storage(f, stage, p->storage, p->type, cls, "bad param storage");
   }
   for (u32 i = 0; i < f->nlocals; ++i) {
     IRLocal* l = &f->locals[i];
     u8 cls = verify_type_reg_class(f, l->desc.type);
     verify_storage(f, stage, l->storage, l->desc.type, cls,
                    "bad local storage");
     if (l->home_slot != FRAME_SLOT_NONE)
       verify_frame_slot(f, stage, l->home_slot, "bad local home slot");
   }
 }
 
 static void verify_allocations(Func* f, const char* stage) {
   if (!f->preg_info && !f->preg_locs) return;
   for (PReg r = 1; r < opt_reg_count(f); ++r) {
     OptPRegInfo* pi = f->preg_info ? &f->preg_info[r] : NULL;
     OptLoc* loc = f->preg_locs ? &f->preg_locs[r] : NULL;
     u8 alloc_kind = opt_preg_alloc_kind(f, r);
     u8 cls = opt_preg_loc_cls(f, r);
     if (cls >= OPT_REG_CLASSES)
       opt_fail(f, stage, "bad preg alloc class", r, cls);
     if (pi && pi->alloc_kind != alloc_kind)
       opt_fail(f, stage, "alloc kind mirror mismatch", r, pi->alloc_kind);
     switch ((OptAllocKind)alloc_kind) {
       case OPT_ALLOC_NONE:
         if (loc && loc->kind != OPT_LOC_NONE)
           opt_fail(f, stage, "alloc location mismatch", r, loc->kind);
         break;
       case OPT_ALLOC_HARD:
         if (opt_preg_hard_reg(f, r) == (Reg)REG_NONE ||
             opt_preg_hard_reg(f, r) >= OPT_MAX_HARD_REGS)
           opt_fail(f, stage, "bad hard allocation", r, opt_preg_hard_reg(f, r));
         if (pi && (pi->cls != cls || pi->hard_reg != opt_preg_hard_reg(f, r)))
           opt_fail(f, stage, "hard alloc mirror mismatch", r, pi->hard_reg);
         if (loc && (loc->kind != OPT_LOC_HARD || loc->cls != cls))
           opt_fail(f, stage, "hard alloc location mismatch", r,
                    opt_preg_hard_reg(f, r));
         break;
       case OPT_ALLOC_SPILL:
         verify_frame_slot(f, stage, opt_preg_spill_slot(f, r),
                           "bad spill slot");
         if (f->frame_slots[opt_preg_spill_slot(f, r) - 1u].kind != FS_SPILL)
           opt_fail(f, stage, "spill slot is not FS_SPILL", r,
                    opt_preg_spill_slot(f, r));
         if (pi &&
             (pi->cls != cls || pi->spill_slot != opt_preg_spill_slot(f, r)))
           opt_fail(f, stage, "spill alloc mirror mismatch", r, pi->spill_slot);
         if (loc && (loc->kind != OPT_LOC_STACK || loc->cls != cls))
           opt_fail(f, stage, "spill alloc location mismatch", r,
                    opt_preg_spill_slot(f, r));
         break;
       default:
         opt_fail(f, stage, "bad allocation kind", r, alloc_kind);
         break;
     }
   }
 }
 
 static void verify_rewritten(Func* f, const char* stage) {
   if (!f->opt_rewritten) return;
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     for (u32 i = 0; i < bl->ninsts; ++i) {
       Inst* in = &bl->insts[i];
       if ((IROp)in->op == IR_PHI)
         opt_fail(f, stage, "phi survived rewrite", b, i);
       if ((IROp)in->op == IR_PARAM_DECL) {
         IRParamDeclAux* aux = (IRParamDeclAux*)in->extra.aux;
         if (in->nopnds || in->opnds)
           opt_fail(f, stage, "param_decl carries operands after rewrite", b, i);
         if ((!aux || aux->desc.storage.kind == CG_LOCAL_STORAGE_REG) &&
             (in->def == VAL_NONE || in->def >= opt_reg_count(f)))
           opt_fail(f, stage, "bad param_decl def after rewrite", b, i);
         continue;
       }
       for (u32 o = 0; o < in->nopnds; ++o)
         verify_operand_shape(f, stage, &in->opnds[o], 1);
       verify_aux_shapes(f, stage, in, 1);
     }
   }
 }
 
 static void verify_use_site(Func* f, const char* stage, const OptUse* use) {
   Inst* in = &f->blocks[use->block].insts[use->inst];
   if (in->id != use->inst_id)
     opt_fail(f, stage, "def-use stale inst id", use->inst_id, in->id);
   switch ((OptUseKind)use->kind) {
     case OPT_USE_OPERAND:
       if (!use->operand)
         opt_fail(f, stage, "def-use missing operand", use->block, use->inst);
       if (use->operand->kind != OPK_REG || (Val)use->operand->v.reg != use->val)
         opt_fail(f, stage, "def-use operand mismatch", use->val, use->kind);
       break;
     case OPT_USE_INDIRECT_BASE:
       if (!use->operand || use->operand->kind != OPK_INDIRECT ||
           (Val)use->operand->v.ind.base != use->val)
         opt_fail(f, stage, "def-use indirect mismatch", use->val, use->kind);
       break;
     case OPT_USE_INDIRECT_INDEX:
       if (!use->operand || use->operand->kind != OPK_INDIRECT ||
           use->operand->v.ind.index == (Reg)REG_NONE ||
           (Val)use->operand->v.ind.index != use->val)
         opt_fail(f, stage, "def-use indirect index mismatch", use->val,
                  use->kind);
       break;
     case OPT_USE_PHI_INPUT: {
       if ((IROp)in->op != IR_PHI)
         opt_fail(f, stage, "def-use phi site mismatch", use->block, use->inst);
       IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
       if (!aux || use->phi_pred_index >= aux->npreds)
         opt_fail(f, stage, "def-use phi pred mismatch", use->val,
                  use->phi_pred_index);
       if (aux->pred_vals[use->phi_pred_index] != use->val)
         opt_fail(f, stage, "def-use phi value mismatch", use->val,
                  use->phi_pred_index);
       break;
     }
     default:
       opt_fail(f, stage, "def-use bad kind", use->kind, use->val);
   }
 }
 
 static void verify_def_use(Func* f, const char* stage) {
   if (f->opt_rewritten) return;
   if (opt_analysis_has(f, OPT_ANALYSIS_DEF_USE)) {
     for (u32 u = 0; u < f->opt_nuses; ++u) {
       OptUse* use = &f->opt_uses[u];
       if (use->val == VAL_NONE || use->val >= f->nvals)
         opt_fail(f, stage, "def-use bad cached val", use->val, f->nvals);
       if (use->block >= f->nblocks)
         opt_fail(f, stage, "def-use bad cached block", use->block, f->nblocks);
       if (use->inst >= f->blocks[use->block].ninsts)
         opt_fail(f, stage, "def-use bad cached inst", use->inst,
                  f->blocks[use->block].ninsts);
       verify_use_site(f, stage, use);
     }
   }
   opt_rebuild_def_use(f);
   for (u32 u = 0; u < f->opt_nuses; ++u) {
     OptUse* use = &f->opt_uses[u];
     if (use->val == VAL_NONE || use->val >= f->nvals)
       opt_fail(f, stage, "def-use bad use val", use->val, f->nvals);
     if (use->block >= f->nblocks)
       opt_fail(f, stage, "def-use bad block", use->block, f->nblocks);
     if (use->inst >= f->blocks[use->block].ninsts)
       opt_fail(f, stage, "def-use bad inst", use->inst,
                f->blocks[use->block].ninsts);
     verify_use_site(f, stage, use);
     if (f->val_def_block[use->val] >= f->nblocks)
       opt_fail(f, stage, "def-use bad def block", use->val,
                f->val_def_block[use->val]);
   }
   for (Val v = 1; v < f->nvals; ++v) {
     for (u32 u = f->opt_first_use_by_val[v]; u != OPT_USE_NONE;
          u = f->opt_uses[u].next_for_val) {
       if (u >= f->opt_nuses) opt_fail(f, stage, "def-use bad next", v, u);
       if (f->opt_uses[u].val != v)
         opt_fail(f, stage, "def-use wrong value list", v, u);
     }
   }
 }
 
 #endif /* !NDEBUG */
 
 void opt_verify(Func* f, const char* stage) {
 #ifdef NDEBUG
   (void)f;
   (void)stage;
   return;
 #else
   if (!f) return;
   if (f->nblocks && f->entry >= f->nblocks)
     opt_fail(f, stage, "entry out of range", f->entry, f->nblocks);
   OptAnalysis a;
   opt_analysis_build_order(f, &a);
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     if (bl->id != b) opt_fail(f, stage, "block id mismatch", bl->id, b);
     if (!a.reachable[b] && (bl->ninsts || bl->nsucc || bl->npreds))
       opt_fail(f, stage, "unreachable block still connected", b, bl->ninsts);
     if (bl->ninsts) {
       u32 expected = 0;
       if (fixed_terminator_succ_count(&bl->insts[bl->ninsts - 1], &expected) &&
           bl->nsucc != expected)
         opt_fail(f, stage, "terminator successor count mismatch", b, bl->nsucc);
     }
     for (u32 s = 0; s < bl->nsucc; ++s) {
       u32 succ = bl->succ[s];
       if (succ >= f->nblocks)
         opt_fail(f, stage, "successor out of range", b, s);
       if (!block_has_pred(&f->blocks[succ], b))
         opt_fail(f, stage, "successor missing reciprocal predecessor", b, succ);
     }
     for (u32 p = 0; p < bl->npreds; ++p) {
       u32 pred = bl->preds[p];
       if (pred >= f->nblocks)
         opt_fail(f, stage, "predecessor out of range", b, p);
       if (!block_has_succ(&f->blocks[pred], b))
         opt_fail(f, stage, "predecessor missing reciprocal successor", b, pred);
     }
   }
   u8* seen_emit = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
   for (u32 i = 0; i < f->emit_order_n; ++i) {
     u32 b = f->emit_order[i];
     if (b >= f->nblocks) opt_fail(f, stage, "emit block out of range", b, i);
     if (seen_emit[b]) opt_fail(f, stage, "duplicate emit block", b, i);
     seen_emit[b] = 1;
   }
   verify_function_storage(f, stage);
   verify_allocations(f, stage);
   verify_values(f, stage);
   verify_rewritten(f, stage);
   verify_def_use(f, stage);
 #endif
 }