kit

pass_ssa.c (34028B)

---

 /* pass_ssa.c - mem2reg SSA construction and phi destruction for O2. */
 
 #include <string.h>
 
 #include "core/arena.h"
 #include "core/core.h"
 #include "core/slice.h"
 #include "core/strbuf.h"
 #include "opt/opt_internal.h"
 
 typedef struct SlotStack {
   Val* vals;
   u32 n;
   u32 cap;
 } SlotStack;
 
 typedef struct RenameCtx {
   Func* f;
   OptAnalysis* analysis;
   u8* promoted;
   Val* repl;
   u32 repl_cap;
   SlotStack* stacks;
 } RenameCtx;
 
 typedef struct EdgeMove {
   Val dst;
   Val src;
   KitCgTypeId type;
   u8 cls;
 } EdgeMove;
 
 typedef struct RegRenameCtx {
   Func* f;
   OptAnalysis* analysis;
   u32 old_nregs;
   SlotStack* stacks;
 } RegRenameCtx;
 
 static u8 ssa_type_class(Func* f, KitCgTypeId ty) {
   return opt_value_reg_class(f->c, ty);
 }
 
 static u32 opnd_slot_id(const Operand* op) {
   if (!op || op->kind != OPK_LOCAL) return 0;
   return (u32)op->v.frame_slot;
 }
 
 static int base_slot_promotable(const Func* f, u32 slot_id) {
   if (slot_id == 0 || slot_id > f->nframe_slots) return 0;
   const IRFrameSlot* s = &f->frame_slots[slot_id - 1u];
   if (s->kind != FS_LOCAL) return 0;
   if (s->flags & (FSF_ADDR_TAKEN | FSF_VOLATILE)) return 0;
   return 1;
 }
 
 static int operand_has_slot(const Operand* op, u32 slot_id) {
   return op && op->kind == OPK_LOCAL && opnd_slot_id(op) == slot_id;
 }
 
 static int abivalue_has_slot(const CGABIValue* v, u32 slot_id) {
   if (!v) return 0;
   if (operand_has_slot(&v->storage, slot_id)) return 1;
   for (u32 i = 0; i < v->nparts; ++i)
     if (operand_has_slot(&v->parts[i].op, slot_id)) return 1;
   return 0;
 }
 
 static int aux_has_slot(const Inst* in, u32 slot_id) {
   switch ((IROp)in->op) {
     case IR_CALL: {
       IRCallAux* aux = (IRCallAux*)in->extra.aux;
       if (!aux) return 0;
       if (aux->use_plan_replay) {
         if (operand_has_slot(&aux->plan.callee, slot_id)) return 1;
         for (u32 i = 0; i < aux->plan.nargs; ++i)
           if (operand_has_slot(&aux->plan.args[i].src, slot_id)) return 1;
         for (u32 i = 0; i < aux->plan.nrets; ++i)
           if (operand_has_slot(&aux->plan.rets[i].dst, slot_id)) return 1;
       } else {
         if (operand_has_slot(&aux->desc.callee, slot_id)) return 1;
         for (u32 i = 0; i < aux->desc.nargs; ++i)
           if (abivalue_has_slot(&aux->desc.args[i], slot_id)) return 1;
         if (abivalue_has_slot(&aux->desc.ret, slot_id)) return 1;
       }
       break;
     }
     case IR_RET: {
       IRRetAux* aux = (IRRetAux*)in->extra.aux;
       return aux && aux->present && abivalue_has_slot(&aux->val, slot_id);
     }
     case IR_SCOPE_BEGIN:
       return 0;
     case IR_ASM_BLOCK: {
       IRAsmAux* aux = (IRAsmAux*)in->extra.aux;
       if (!aux) return 0;
       for (u32 i = 0; i < aux->nin; ++i)
         if (operand_has_slot(&aux->in_ops[i], slot_id)) return 1;
       for (u32 i = 0; i < aux->nout; ++i)
         if (operand_has_slot(&aux->out_ops[i], slot_id)) return 1;
       break;
     }
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (!aux) return 0;
       for (u32 i = 0; i < aux->narg; ++i)
         if (operand_has_slot(&aux->args[i], slot_id)) return 1;
       for (u32 i = 0; i < aux->ndst; ++i)
         if (operand_has_slot(&aux->dsts[i], slot_id)) return 1;
       break;
     }
     default:
       break;
   }
   return 0;
 }
 
 static int slot_access_promotable(const Func* f, const Inst* in, u32 slot_id) {
   if ((IROp)in->op == IR_LOAD) {
     if (in->nopnds < 2 || opnd_slot_id(&in->opnds[1]) != slot_id) return 1;
     if (in->opnds[0].kind != OPK_REG || opt_mem_observable(&in->extra.mem))
       return 0;
     /* Post-EA cg layer can produce LOAD opnds[1]=OPK_LOCAL(slot) with an
      * access type that differs from the slot's declared type (e.g. a
      * sub-word read for type-punning). mem2reg would silently lose those
      * bits, so block promotion when the access type does not match the
      * slot's declared type. */
     const IRFrameSlot* s = &f->frame_slots[slot_id - 1u];
     KitCgTypeId at = in->extra.mem.type;
     if (at && at != s->type) return 0;
     if (in->opnds[0].type && in->opnds[0].type != s->type) return 0;
     return 1;
   }
   if ((IROp)in->op == IR_STORE) {
     if (in->nopnds < 2 || opnd_slot_id(&in->opnds[0]) != slot_id) return 1;
     if (opt_mem_observable(&in->extra.mem)) return 0;
     if (in->opnds[1].kind != OPK_REG && in->opnds[1].kind != OPK_IMM) return 0;
     const IRFrameSlot* s = &f->frame_slots[slot_id - 1u];
     KitCgTypeId at = in->extra.mem.type;
     if (at && at != s->type) return 0;
     if (in->opnds[1].type && in->opnds[1].type != s->type) return 0;
     return 1;
   }
   for (u32 i = 0; i < in->nopnds; ++i)
     if (opnd_slot_id(&in->opnds[i]) == slot_id) return 0;
   if (aux_has_slot(in, slot_id)) return 0;
   return 1;
 }
 
 static u8* find_promoted_slots(Func* f) {
   u8* promoted = arena_zarray(f->arena, u8, f->nframe_slots + 1u);
   for (u32 sid = 1; sid <= f->nframe_slots; ++sid) {
     if (!base_slot_promotable(f, sid)) continue;
     promoted[sid] = 1;
   }
   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];
       for (u32 sid = 1; sid <= f->nframe_slots; ++sid) {
         if (promoted[sid] && !slot_access_promotable(f, in, sid))
           promoted[sid] = 0;
       }
     }
   }
   return promoted;
 }
 
 static void stack_push(Arena* a, SlotStack* s, Val v) {
   if (s->n == s->cap) {
     u32 ncap = s->cap ? s->cap * 2u : 4u;
     Val* vals = arena_array(a, Val, ncap);
     if (s->vals) memcpy(vals, s->vals, sizeof(vals[0]) * s->n);
     s->vals = vals;
     s->cap = ncap;
   }
   s->vals[s->n++] = v;
 }
 
 static Val stack_top(const SlotStack* s) {
   return s && s->n ? s->vals[s->n - 1u] : VAL_NONE;
 }
 
 static int reg_in_defs(const Inst* in, Reg r) {
   if (!in || r == (Reg)REG_NONE) return 0;
   if (in->def == (Val)r) return 1;
   for (u32 i = 0; i < in->ndefs; ++i)
     if (in->defs[i] == (Val)r) return 1;
   return 0;
 }
 
 static u8* find_reg_def_blocks(Func* f, u32 old_nregs) {
   u8* def_blocks = arena_zarray(f->arena, u8, old_nregs * f->nblocks);
   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->def != VAL_NONE && in->def < old_nregs)
         def_blocks[in->def * f->nblocks + b] = 1;
       for (u32 d = 0; d < in->ndefs; ++d) {
         Val v = in->defs[d];
         if (v != VAL_NONE && v < old_nregs) def_blocks[v * f->nblocks + b] = 1;
       }
     }
   }
   return def_blocks;
 }
 
 static void compute_reg_phi_sites(Func* f, OptAnalysis* a,
                                   const OptLiveInfo* live, u32 old_nregs,
                                   u8* needs_phi) {
   u8* def_blocks = find_reg_def_blocks(f, old_nregs);
   u32* work = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u);
   u8* queued = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
 
   for (u32 r = 1; r < old_nregs; ++r) {
     if (!f->preg_type[r]) continue;
     memset(queued, 0, f->nblocks);
     u32 wn = 0;
     for (u32 b = 0; b < f->nblocks; ++b) {
       if (!def_blocks[r * f->nblocks + b]) continue;
       queued[b] = 1;
       work[wn++] = b;
     }
     while (wn) {
       u32 x = work[--wn];
       OptBlockList* df = &a->dom_frontier[x];
       for (u32 i = 0; i < df->n; ++i) {
         u32 y = df->items[i];
         if (needs_phi[r * f->nblocks + y]) continue;
         if (live && !opt_bitset_has(&live->blocks[y].live_in, (Val)r)) continue;
         needs_phi[r * f->nblocks + y] = 1;
         if (!queued[y]) {
           queued[y] = 1;
           work[wn++] = y;
         }
       }
     }
   }
 }
 
 static void insert_reg_phis(Func* f, u32 b, u32 old_nregs,
                             const u8* needs_phi) {
   Block* bl = &f->blocks[b];
   u32 nphi = 0;
   for (u32 r = 1; r < old_nregs; ++r)
     if (needs_phi[r * f->nblocks + b]) ++nphi;
   if (!nphi) return;
 
   u32 old_nvals = f->nvals;
   Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + nphi);
   u32 w = 0;
   for (u32 r = 1; r < old_nregs; ++r) {
     if (!needs_phi[r * f->nblocks + b]) continue;
     Inst* in = &insts[w++];
     in->op = IR_PHI;
     ir_assign_inst_id(f, in);
     in->type = f->preg_type[r];
     in->def = ir_alloc_val(f, f->preg_type[r], f->preg_cls[r]);
     f->val_def_block[in->def] = b;
     f->val_def_inst[in->def] = w - 1u;
     IRPhiAux* aux = arena_znew(f->arena, IRPhiAux);
     aux->reg_id = r;
     aux->npreds = bl->npreds;
     if (bl->npreds) {
       aux->pred_blocks = arena_array(f->arena, u32, bl->npreds);
       aux->pred_vals = arena_zarray(f->arena, Val, bl->npreds);
       memcpy(aux->pred_blocks, bl->preds, sizeof(u32) * bl->npreds);
     }
     in->extra.aux = aux;
   }
   if (bl->ninsts) memcpy(insts + nphi, bl->insts, sizeof(Inst) * bl->ninsts);
   bl->insts = insts;
   bl->ninsts += nphi;
   bl->cap = bl->ninsts;
   for (Val v = 1; v < old_nvals; ++v)
     if (f->val_def_block[v] == b) f->val_def_inst[v] += nphi;
 }
 
 static Val reg_stack_top(RegRenameCtx* ctx, Reg r) {
   if (r == (Reg)REG_NONE || (u32)r >= ctx->old_nregs) return VAL_NONE;
   return stack_top(&ctx->stacks[(u32)r]);
 }
 
 static void reg_replace_use(RegRenameCtx* ctx, Operand* op) {
   if (!op) return;
   if (op->kind == OPK_REG) {
     Reg r = op->v.reg;
     Val v = reg_stack_top(ctx, r);
     if (v == VAL_NONE) return;
     op->v.reg = (Reg)v;
     op->type = ctx->f->val_type[v];
     op->cls = ctx->f->val_cls[v];
   } else if (op->kind == OPK_INDIRECT) {
     Reg r = op->v.ind.base;
     Val v = reg_stack_top(ctx, r);
     if (v != VAL_NONE) op->v.ind.base = (Reg)v;
     if (op->v.ind.index != (Reg)REG_NONE) {
       Reg ri = op->v.ind.index;
       Val vi = reg_stack_top(ctx, ri);
       if (vi != VAL_NONE) op->v.ind.index = (Reg)vi;
     }
   }
 }
 
 static void reg_replace_abivalue_uses(RegRenameCtx* ctx, CGABIValue* v) {
   if (!v) return;
   reg_replace_use(ctx, &v->storage);
   for (u32 i = 0; i < v->nparts; ++i)
     reg_replace_use(ctx, (Operand*)&v->parts[i].op);
 }
 
 static Val reg_define_operand(RegRenameCtx* ctx, u32 b, u32 i, Inst* in,
                               Operand* op, u32 def_index, u32* pushed) {
   if (!op || op->kind != OPK_REG) return VAL_NONE;
   Reg r = op->v.reg;
   if (r == (Reg)REG_NONE || (u32)r >= ctx->old_nregs) return VAL_NONE;
   KitCgTypeId ty = op->type ? op->type : ctx->f->preg_type[(u32)r];
   u8 cls = op->cls;
   Val v = ir_alloc_val(ctx->f, ty, cls);
   op->v.reg = (Reg)v;
   op->type = ty;
   op->cls = cls;
   if (def_index == 0 && in->def == (Val)r) in->def = v;
   if (def_index < in->ndefs && in->defs[def_index] == (Val)r)
     in->defs[def_index] = v;
   ctx->f->val_def_block[v] = b;
   ctx->f->val_def_inst[v] = i;
   stack_push(ctx->f->arena, &ctx->stacks[(u32)r], v);
   pushed[(u32)r]++;
   return v;
 }
 
 static u32 reg_def_index(const Inst* in, Reg r, u32 ordinal) {
   if (!in || !in->ndefs) return 0;
   u32 seen = 0;
   for (u32 i = 0; i < in->ndefs; ++i) {
     if (in->defs[i] != (Val)r) continue;
     if (seen == ordinal) return i;
     ++seen;
   }
   return 0;
 }
 
 static void reg_replace_inst_uses(RegRenameCtx* ctx, Inst* in) {
   for (u32 o = 0; o < in->nopnds; ++o) {
     Operand* op = &in->opnds[o];
     int is_def = 0;
     if (op->kind == OPK_REG) {
       if ((IROp)in->op == IR_ATOMIC_CAS)
         is_def = (o == 0 || o == 1) && reg_in_defs(in, op->v.reg);
       else
         is_def = o == 0 && reg_in_defs(in, op->v.reg);
     }
     if (!is_def) reg_replace_use(ctx, op);
   }
 
   switch ((IROp)in->op) {
     case IR_CALL: {
       IRCallAux* aux = (IRCallAux*)in->extra.aux;
       if (!aux) break;
       if (aux->use_plan_replay) {
         reg_replace_use(ctx, &aux->plan.callee);
         for (u32 i = 0; i < aux->plan.nargs; ++i)
           reg_replace_use(ctx, &aux->plan.args[i].src);
       } else {
         reg_replace_use(ctx, &aux->desc.callee);
         for (u32 i = 0; i < aux->desc.nargs; ++i)
           reg_replace_abivalue_uses(ctx, (CGABIValue*)&aux->desc.args[i]);
       }
       break;
     }
     case IR_RET: {
       IRRetAux* aux = (IRRetAux*)in->extra.aux;
       if (aux && aux->present) reg_replace_abivalue_uses(ctx, &aux->val);
       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) reg_replace_use(ctx, &aux->in_ops[i]);
       break;
     }
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (!aux) break;
       for (u32 i = 0; i < aux->narg; ++i) reg_replace_use(ctx, &aux->args[i]);
       break;
     }
     default:
       break;
   }
 }
 
 static void reg_define_abivalue(RegRenameCtx* ctx, u32 b, u32 i, Inst* in,
                                 CGABIValue* v, u32* pushed) {
   if (!v) return;
   if (v->storage.kind == OPK_REG && reg_in_defs(in, v->storage.v.reg))
     reg_define_operand(ctx, b, i, in, &v->storage, 0, pushed);
   for (u32 p = 0; p < v->nparts; ++p) {
     Operand* op = (Operand*)&v->parts[p].op;
     if (op->kind == OPK_REG && reg_in_defs(in, op->v.reg))
       reg_define_operand(ctx, b, i, in, op, p, pushed);
   }
 }
 
 static void reg_define_inst_defs(RegRenameCtx* ctx, u32 b, u32 i, Inst* in,
                                  u32* pushed) {
   switch ((IROp)in->op) {
     case IR_CALL: {
       IRCallAux* aux = (IRCallAux*)in->extra.aux;
       if (!aux) break;
       if (aux->use_plan_replay) {
         for (u32 r = 0; r < aux->plan.nrets; ++r) {
           if (aux->plan.rets[r].dst.kind == OPK_REG &&
               reg_in_defs(in, aux->plan.rets[r].dst.v.reg))
             reg_define_operand(ctx, b, i, in, &aux->plan.rets[r].dst, r,
                                pushed);
         }
       } else {
         reg_define_abivalue(ctx, b, i, in, &aux->desc.ret, pushed);
       }
       break;
     }
     case IR_ATOMIC_CAS:
       if (in->nopnds >= 1 && in->opnds[0].kind == OPK_REG)
         reg_define_operand(ctx, b, i, in, &in->opnds[0], 0, pushed);
       if (in->nopnds >= 2 && in->opnds[1].kind == OPK_REG)
         reg_define_operand(ctx, b, i, in, &in->opnds[1], 1, pushed);
       break;
     case IR_ASM_BLOCK: {
       IRAsmAux* aux = (IRAsmAux*)in->extra.aux;
       if (!aux) break;
       for (u32 o = 0; o < aux->nout; ++o) {
         if (aux->out_ops[o].kind != OPK_REG) continue;
         reg_define_operand(ctx, b, i, in, &aux->out_ops[o],
                            reg_def_index(in, aux->out_ops[o].v.reg, o), pushed);
       }
       break;
     }
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       if (!aux) break;
       for (u32 d = 0; d < aux->ndst; ++d) {
         if (aux->dsts[d].kind != OPK_REG) continue;
         reg_define_operand(ctx, b, i, in, &aux->dsts[d], d, pushed);
         if (aux->result_vals) aux->result_vals[d] = (Val)aux->dsts[d].v.reg;
       }
       break;
     }
     default:
       if (in->nopnds && in->opnds[0].kind == OPK_REG &&
           reg_in_defs(in, in->opnds[0].v.reg))
         reg_define_operand(ctx, b, i, in, &in->opnds[0], 0, pushed);
       break;
   }
 }
 
 static void reg_rename_block(RegRenameCtx* ctx, u32 b) {
   Func* f = ctx->f;
   Block* bl = &f->blocks[b];
   u32* pushed = arena_zarray(f->arena, u32, ctx->old_nregs);
 
   for (u32 i = 0; i < bl->ninsts; ++i) {
     Inst* in = &bl->insts[i];
     if ((IROp)in->op != IR_PHI) break;
     IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
     if (!aux || !aux->reg_id || aux->reg_id >= ctx->old_nregs) continue;
     stack_push(f->arena, &ctx->stacks[aux->reg_id], in->def);
     pushed[aux->reg_id]++;
   }
 
   for (u32 i = 0; i < bl->ninsts; ++i) {
     Inst* in = &bl->insts[i];
     if ((IROp)in->op == IR_PHI) continue;
     reg_replace_inst_uses(ctx, in);
     reg_define_inst_defs(ctx, b, i, in, pushed);
   }
 
   for (u32 s = 0; s < bl->nsucc; ++s) {
     u32 succ = bl->succ[s];
     if (succ >= f->nblocks) continue;
     Block* sb = &f->blocks[succ];
     u32 pred_idx = OPT_USE_NONE;
     for (u32 p = 0; p < sb->npreds; ++p) {
       if (sb->preds[p] == b) {
         pred_idx = p;
         break;
       }
     }
     if (pred_idx == OPT_USE_NONE) continue;
     for (u32 i = 0; i < sb->ninsts; ++i) {
       Inst* phi = &sb->insts[i];
       if ((IROp)phi->op != IR_PHI) break;
       IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
       if (!aux || !aux->reg_id || aux->reg_id >= ctx->old_nregs) continue;
       aux->pred_vals[pred_idx] = reg_stack_top(ctx, (Reg)aux->reg_id);
     }
   }
 
   OptBlockList* children = &ctx->analysis->dom_children[b];
   for (u32 i = 0; i < children->n; ++i)
     reg_rename_block(ctx, children->items[i]);
 
   for (u32 r = 1; r < ctx->old_nregs; ++r) {
     while (pushed[r]--) {
       if (ctx->stacks[r].n) --ctx->stacks[r].n;
     }
   }
 }
 
 void opt_build_reg_ssa(Func* f) {
   if (!f || f->nblocks == 0 || f->npregs <= 1) {
     if (f) opt_rebuild_def_use(f);
     return;
   }
   opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
 
   u32 old_nregs = f->npregs;
   OptAnalysis a;
   opt_analysis_build_order(f, &a);
   opt_analysis_build_dominators(f, &a);
   opt_analysis_build_dom_frontier(f, &a);
 
   OptLiveInfo live;
   opt_live_blocks(f, &live);
   u8* needs_phi = arena_zarray(f->arena, u8, old_nregs * f->nblocks);
   compute_reg_phi_sites(f, &a, &live, old_nregs, needs_phi);
   for (u32 b = 0; b < f->nblocks; ++b)
     insert_reg_phis(f, b, old_nregs, needs_phi);
 
   RegRenameCtx ctx;
   memset(&ctx, 0, sizeof ctx);
   ctx.f = f;
   ctx.analysis = &a;
   ctx.old_nregs = old_nregs;
   ctx.stacks = arena_zarray(f->arena, SlotStack, old_nregs);
   reg_rename_block(&ctx, f->entry);
   f->opt_reg_ssa = 1;
   opt_rebuild_def_use(f);
 }
 
 static Val resolve_repl(const RenameCtx* ctx, Val v) {
   while (v != VAL_NONE && v < ctx->repl_cap && ctx->repl[v] != VAL_NONE &&
          ctx->repl[v] != v) {
     v = ctx->repl[v];
   }
   return v;
 }
 
 static void replace_use(Func* f, Inst* in, Operand* op, int is_def, void* arg) {
   (void)in;
   RenameCtx* ctx = (RenameCtx*)arg;
   if (is_def || op->kind != OPK_REG) return;
   Val old = (Val)op->v.reg;
   if (old == VAL_NONE || old >= f->nvals) return;
   Val repl = resolve_repl(ctx, old);
   if (repl != VAL_NONE && repl != old) {
     op->v.reg = (Reg)repl;
     op->type = f->val_type[repl];
     op->cls = f->val_cls[repl];
   }
 }
 
 static void insert_phis(Func* f, u32 b, const u8* needs_phi) {
   Block* bl = &f->blocks[b];
   u32 nphi = 0;
   for (u32 sid = 1; sid <= f->nframe_slots; ++sid)
     if (needs_phi[sid * f->nblocks + b]) ++nphi;
   if (!nphi) return;
 
   u32 old_nvals = f->nvals;
   Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + nphi);
   u32 w = 0;
   for (u32 sid = 1; sid <= f->nframe_slots; ++sid) {
     if (!needs_phi[sid * f->nblocks + b]) continue;
     const IRFrameSlot* slot = &f->frame_slots[sid - 1u];
     Inst* in = &insts[w++];
     in->op = IR_PHI;
     ir_assign_inst_id(f, in);
     in->type = slot->type;
     in->def = ir_alloc_val(f, slot->type, ssa_type_class(f, slot->type));
     f->val_def_block[in->def] = b;
     f->val_def_inst[in->def] = w - 1u;
     IRPhiAux* aux = arena_znew(f->arena, IRPhiAux);
     aux->slot_id = sid;
     aux->npreds = bl->npreds;
     if (bl->npreds) {
       aux->pred_blocks = arena_array(f->arena, u32, bl->npreds);
       aux->pred_vals = arena_zarray(f->arena, Val, bl->npreds);
       memcpy(aux->pred_blocks, bl->preds, sizeof(u32) * bl->npreds);
     }
     in->extra.aux = aux;
   }
   if (bl->ninsts) memcpy(insts + nphi, bl->insts, sizeof(Inst) * bl->ninsts);
   bl->insts = insts;
   bl->ninsts += nphi;
   bl->cap = bl->ninsts;
   for (Val v = 1; v < old_nvals; ++v)
     if (f->val_def_block[v] == b) f->val_def_inst[v] += nphi;
 }
 
 static void mark_def_blocks(Func* f, const u8* promoted, u8* def_blocks) {
   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_STORE || in->nopnds < 2) continue;
       u32 sid = opnd_slot_id(&in->opnds[0]);
       if (sid && promoted[sid]) def_blocks[sid * f->nblocks + b] = 1;
     }
   }
 }
 
 static void compute_phi_sites(Func* f, OptAnalysis* a, const u8* promoted,
                               u8* needs_phi) {
   u8* def_blocks =
       arena_zarray(f->arena, u8, (f->nframe_slots + 1u) * f->nblocks);
   mark_def_blocks(f, promoted, def_blocks);
   u32* work = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u);
   u8* queued = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u);
 
   for (u32 sid = 1; sid <= f->nframe_slots; ++sid) {
     if (!promoted[sid]) continue;
     memset(queued, 0, f->nblocks);
     u32 wn = 0;
     for (u32 b = 0; b < f->nblocks; ++b) {
       if (!def_blocks[sid * f->nblocks + b]) continue;
       queued[b] = 1;
       work[wn++] = b;
     }
     while (wn) {
       u32 x = work[--wn];
       OptBlockList* df = &a->dom_frontier[x];
       for (u32 i = 0; i < df->n; ++i) {
         u32 y = df->items[i];
         if (needs_phi[sid * f->nblocks + y]) continue;
         needs_phi[sid * f->nblocks + y] = 1;
         if (!queued[y]) {
           queued[y] = 1;
           work[wn++] = y;
         }
       }
     }
   }
 }
 
 static void rewrite_store_immediate(RenameCtx* ctx, Inst* in, u32 b, u32 i,
                                     u32 sid) {
   Operand src = in->opnds[1];
   Val v = ir_alloc_val(ctx->f, src.type, src.cls);
   Operand* opnds = arena_array(ctx->f->arena, Operand, 1);
   opnds[0] = src;
   opnds[0].kind = OPK_REG;
   opnds[0].v.reg = (Reg)v;
   in->op = IR_LOAD_IMM;
   in->type = src.type;
   in->def = v;
   in->opnds = opnds;
   in->nopnds = 1;
   in->extra.imm = src.v.imm;
   ctx->f->val_def_block[v] = b;
   ctx->f->val_def_inst[v] = i;
   stack_push(ctx->f->arena, &ctx->stacks[sid], v);
 }
 
 static void rename_block(RenameCtx* ctx, u32 b) {
   Func* f = ctx->f;
   Block* bl = &f->blocks[b];
   u32* pushed = arena_zarray(f->arena, u32, f->nframe_slots + 1u);
 
   for (u32 i = 0; i < bl->ninsts; ++i) {
     Inst* in = &bl->insts[i];
     if ((IROp)in->op != IR_PHI) break;
     IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
     if (!aux || !aux->slot_id || !ctx->promoted[aux->slot_id]) continue;
     stack_push(f->arena, &ctx->stacks[aux->slot_id], in->def);
     pushed[aux->slot_id]++;
   }
 
   for (u32 i = 0; i < bl->ninsts; ++i) {
     Inst* in = &bl->insts[i];
     if ((IROp)in->op == IR_PHI) continue;
     if ((IROp)in->op == IR_STORE && in->nopnds >= 2) {
       u32 sid = opnd_slot_id(&in->opnds[0]);
       if (sid && ctx->promoted[sid]) {
         Operand src = in->opnds[1];
         if (src.kind == OPK_REG) {
           stack_push(f->arena, &ctx->stacks[sid],
                      resolve_repl(ctx, (Val)src.v.reg));
           in->op = IR_NOP;
           in->nopnds = 0;
           in->opnds = NULL;
           in->def = VAL_NONE;
         } else {
           rewrite_store_immediate(ctx, in, b, i, sid);
         }
         pushed[sid]++;
         continue;
       }
     }
     if ((IROp)in->op == IR_LOAD && in->nopnds >= 2) {
       u32 sid = opnd_slot_id(&in->opnds[1]);
       if (sid && ctx->promoted[sid] && in->def != VAL_NONE) {
         Val cur = stack_top(&ctx->stacks[sid]);
         if (cur == VAL_NONE) continue;
         if (in->def < ctx->repl_cap)
           ctx->repl[in->def] = resolve_repl(ctx, cur);
         in->op = IR_NOP;
         in->nopnds = 0;
         in->opnds = NULL;
         in->def = VAL_NONE;
         continue;
       }
     }
     opt_walk_inst_operands(f, in, replace_use, ctx);
   }
 
   for (u32 s = 0; s < bl->nsucc; ++s) {
     u32 succ = bl->succ[s];
     if (succ >= f->nblocks) continue;
     Block* sb = &f->blocks[succ];
     u32 pred_idx = OPT_USE_NONE;
     for (u32 p = 0; p < sb->npreds; ++p) {
       if (sb->preds[p] == b) {
         pred_idx = p;
         break;
       }
     }
     if (pred_idx == OPT_USE_NONE) continue;
     for (u32 i = 0; i < sb->ninsts; ++i) {
       Inst* phi = &sb->insts[i];
       if ((IROp)phi->op != IR_PHI) break;
       IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
       if (!aux || !aux->slot_id || !ctx->promoted[aux->slot_id]) continue;
       aux->pred_vals[pred_idx] =
           resolve_repl(ctx, stack_top(&ctx->stacks[aux->slot_id]));
     }
   }
 
   OptBlockList* children = &ctx->analysis->dom_children[b];
   for (u32 i = 0; i < children->n; ++i) rename_block(ctx, children->items[i]);
 
   for (u32 sid = 1; sid <= f->nframe_slots; ++sid) {
     while (pushed[sid]--) {
       if (ctx->stacks[sid].n) --ctx->stacks[sid].n;
     }
   }
 }
 
 static void replace_phi_inputs(Func* f, RenameCtx* ctx) {
   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) break;
       IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
       if (!aux) continue;
       for (u32 p = 0; p < aux->npreds; ++p)
         aux->pred_vals[p] = resolve_repl(ctx, aux->pred_vals[p]);
     }
   }
 }
 
 void opt_build_ssa(Func* f) {
   if (f) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
   if (!f || f->nblocks == 0 || f->nframe_slots == 0) {
     if (f) opt_rebuild_def_use(f);
     return;
   }
 
   OptAnalysis a;
   opt_analysis_build_order(f, &a);
   opt_analysis_build_dominators(f, &a);
   opt_analysis_build_dom_frontier(f, &a);
 
   u8* promoted = find_promoted_slots(f);
   u8* needs_phi =
       arena_zarray(f->arena, u8, (f->nframe_slots + 1u) * f->nblocks);
   compute_phi_sites(f, &a, promoted, needs_phi);
   for (u32 b = 0; b < f->nblocks; ++b) insert_phis(f, b, needs_phi);
 
   RenameCtx ctx;
   memset(&ctx, 0, sizeof ctx);
   ctx.f = f;
   ctx.analysis = &a;
   ctx.promoted = promoted;
   ctx.repl_cap = f->vals_cap ? f->vals_cap : f->nvals;
   ctx.repl = arena_zarray(f->arena, Val, ctx.repl_cap ? ctx.repl_cap : 1u);
   ctx.stacks = arena_zarray(f->arena, SlotStack, f->nframe_slots + 1u);
   rename_block(&ctx, f->entry);
 
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     for (u32 i = 0; i < bl->ninsts; ++i)
       opt_walk_inst_operands(f, &bl->insts[i], replace_use, &ctx);
   }
   replace_phi_inputs(f, &ctx);
   opt_rebuild_def_use(f);
 }
 
 static int ssa_is_terminator(const Inst* in) {
   switch ((IROp)in->op) {
     case IR_BR:
     case IR_CONDBR:
     case IR_CMP_BRANCH:
     case IR_SWITCH:
     case IR_INDIRECT_BRANCH:
     case IR_RET:
     case IR_UNREACHABLE:
     case IR_BREAK_TO:
     case IR_CONTINUE_TO:
       return 1;
     case IR_INTRINSIC: {
       IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux;
       return aux && (aux->kind == INTRIN_LONGJMP || aux->kind == INTRIN_TRAP);
     }
     default:
       return 0;
   }
 }
 
 static Inst make_copy_inst(Func* f, Val dst, Val src, KitCgTypeId ty, u8 cls) {
   Inst in;
   memset(&in, 0, sizeof in);
   in.op = IR_COPY;
   in.flags = IRF_NO_COALESCE;
   ir_assign_inst_id(f, &in);
   in.type = ty;
   in.def = dst;
   in.nopnds = 2;
   in.opnds = arena_array(f->arena, Operand, 2);
   in.opnds[0].kind = OPK_REG;
   in.opnds[0].type = ty;
   in.opnds[0].cls = cls;
   in.opnds[0].v.reg = (Reg)dst;
   in.opnds[1].kind = OPK_REG;
   in.opnds[1].type = ty;
   in.opnds[1].cls = cls;
   in.opnds[1].v.reg = (Reg)src;
   return in;
 }
 
 static void insert_edge_moves(Func* f, u32 b, const EdgeMove* moves, u32 n) {
   if (!n) return;
   Block* bl = &f->blocks[b];
   u32 term = bl->ninsts && ssa_is_terminator(&bl->insts[bl->ninsts - 1u]);
   u32 insert_at = bl->ninsts - term;
   u32 extra = n == 1 ? 1u : n * 2u;
   Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + extra);
   if (insert_at) memcpy(insts, bl->insts, sizeof(Inst) * insert_at);
   u32 w = insert_at;
   if (n == 1) {
     insts[w++] = make_copy_inst(f, moves[0].dst, moves[0].src, moves[0].type,
                                 moves[0].cls);
   } else {
     Val* temps = arena_array(f->arena, Val, n);
     for (u32 i = 0; i < n; ++i) {
       temps[i] = ir_alloc_val(f, moves[i].type, moves[i].cls);
       f->val_def_block[temps[i]] = b;
       f->val_def_inst[temps[i]] = w;
       insts[w++] = make_copy_inst(f, temps[i], moves[i].src, moves[i].type,
                                   moves[i].cls);
     }
     for (u32 i = 0; i < n; ++i) {
       insts[w] = make_copy_inst(f, moves[i].dst, temps[i], moves[i].type,
                                 moves[i].cls);
       f->val_def_block[moves[i].dst] = b;
       f->val_def_inst[moves[i].dst] = w;
       ++w;
     }
   }
   if (term) insts[w++] = bl->insts[bl->ninsts - 1u];
   bl->insts = insts;
   bl->ninsts = w;
   bl->cap = w;
   if (n == 1) {
     f->val_def_block[moves[0].dst] = b;
     f->val_def_inst[moves[0].dst] = insert_at;
   }
 }
 
 static void realign_phi_preds(Func* f) {
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     for (u32 i = 0; i < bl->ninsts; ++i) {
       Inst* phi = &bl->insts[i];
       if ((IROp)phi->op != IR_PHI) break;
       IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
       if (!aux || aux->npreds == bl->npreds) {
         if (!aux) continue;
       }
       u32 old_n = aux->npreds;
       u32* old_blocks = aux->pred_blocks;
       Val* old_vals = aux->pred_vals;
       u32* pred_blocks =
           bl->npreds ? arena_array(f->arena, u32, bl->npreds) : NULL;
       Val* pred_vals =
           bl->npreds ? arena_zarray(f->arena, Val, bl->npreds) : NULL;
       for (u32 p = 0; p < bl->npreds; ++p) {
         pred_blocks[p] = bl->preds[p];
         pred_vals[p] = phi->def;
         for (u32 old = 0; old < old_n; ++old) {
           if (old_blocks && old_blocks[old] == bl->preds[p]) {
             pred_vals[p] = old_vals ? old_vals[old] : VAL_NONE;
             break;
           }
         }
       }
       aux->npreds = bl->npreds;
       aux->pred_blocks = pred_blocks;
       aux->pred_vals = pred_vals;
     }
   }
 }
 
 void opt_make_conventional_ssa(Func* f) {
   if (!f) return;
   opt_analysis_invalidate(f, OPT_ANALYSIS_CFG | OPT_ANALYSIS_DEF_USE |
                                  OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP);
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     if (!bl->ninsts || (IROp)bl->insts[0].op != IR_PHI) continue;
     for (u32 p = 0; p < bl->npreds; ++p) {
       u32 pred = bl->preds[p];
       EdgeMove* moves = arena_array(f->arena, EdgeMove, bl->ninsts);
       u32 n = 0;
       for (u32 i = 0; i < bl->ninsts; ++i) {
         Inst* phi = &bl->insts[i];
         if ((IROp)phi->op != IR_PHI) break;
         IRPhiAux* aux = (IRPhiAux*)phi->extra.aux;
         if (!aux || p >= aux->npreds) continue;
         Val src = aux->pred_vals[p];
         if (src == VAL_NONE || src == phi->def) continue;
         moves[n].dst = phi->def;
         moves[n].src = src;
         moves[n].type = phi->type;
         moves[n].cls = f->val_cls[phi->def];
         ++n;
       }
       if (!n) continue;
       u32 target = pred;
       if (pred >= f->nblocks) continue;
       if (f->blocks[pred].nsucc != 1) target = opt_split_edge(f, pred, b);
       insert_edge_moves(f, target, moves, n);
     }
   }
   opt_build_cfg(f);
   realign_phi_preds(f);
   opt_rebuild_def_use(f);
 }
 
 void opt_undo_ssa(Func* f) {
   if (!f) return;
   opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE);
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     u32 w = 0;
     for (u32 i = 0; i < bl->ninsts; ++i) {
       if ((IROp)bl->insts[i].op == IR_PHI) continue;
       bl->insts[w++] = bl->insts[i];
     }
     bl->ninsts = w;
   }
   opt_rebuild_def_use(f);
 }
 
 static void ssa_dump_write(Writer* w, const char* s) {
   kit_writer_write(w, s, slice_from_cstr(s).len);
 }
 
 static void ssa_dump_sb(Writer* w, const StrBuf* sb) {
   kit_writer_write(w, strbuf_cstr(sb), strbuf_len(sb));
 }
 
 typedef struct SsaDumpUseCtx {
   Writer* w;
   int any;
 } SsaDumpUseCtx;
 
 static void ssa_dump_use(Func* f, Inst* in, Operand* op, int is_def,
                          void* arg) {
   (void)f;
   (void)in;
   if (is_def || op->kind != OPK_REG) return;
   SsaDumpUseCtx* ctx = (SsaDumpUseCtx*)arg;
   char buf[32];
   StrBuf sb;
   strbuf_init(&sb, buf, sizeof buf);
   if (ctx->any) strbuf_putc(&sb, ',');
   strbuf_putc(&sb, 'v');
   strbuf_put_u64(&sb, (u64)(unsigned)op->v.reg);
   ssa_dump_sb(ctx->w, &sb);
   ctx->any = 1;
 }
 
 void opt_ssa_dump(Func* f, Writer* w) {
   if (!f || !w) return;
   opt_rebuild_def_use(f);
   char buf[160];
   StrBuf sb;
   strbuf_init(&sb, buf, sizeof buf);
   strbuf_puts(&sb, "ssa blocks=");
   strbuf_put_u64(&sb, (u64)(unsigned)f->nblocks);
   strbuf_puts(&sb, " vals=");
   strbuf_put_u64(&sb, (u64)(unsigned)f->nvals);
   strbuf_puts(&sb, " uses=");
   strbuf_put_u64(&sb, (u64)(unsigned)f->opt_nuses);
   strbuf_putc(&sb, '\n');
   ssa_dump_sb(w, &sb);
   for (u32 b = 0; b < f->nblocks; ++b) {
     Block* bl = &f->blocks[b];
     strbuf_reset(&sb);
     strbuf_puts(&sb, "block ");
     strbuf_put_u64(&sb, (u64)(unsigned)b);
     strbuf_puts(&sb, " preds=");
     strbuf_put_u64(&sb, (u64)(unsigned)bl->npreds);
     strbuf_puts(&sb, " succs=");
     strbuf_put_u64(&sb, (u64)(unsigned)bl->nsucc);
     strbuf_putc(&sb, '\n');
     ssa_dump_sb(w, &sb);
     for (u32 i = 0; i < bl->ninsts; ++i) {
       Inst* in = &bl->insts[i];
       strbuf_reset(&sb);
       strbuf_puts(&sb, "  i");
       strbuf_put_u64(&sb, (u64)(unsigned)in->id);
       strbuf_puts(&sb, " op=");
       strbuf_put_u64(&sb, (u64)(unsigned)in->op);
       ssa_dump_sb(w, &sb);
       if (in->def != VAL_NONE) {
         strbuf_reset(&sb);
         strbuf_puts(&sb, " def=v");
         strbuf_put_u64(&sb, (u64)(unsigned)in->def);
         ssa_dump_sb(w, &sb);
       }
       if ((IROp)in->op == IR_PHI) {
         IRPhiAux* aux = (IRPhiAux*)in->extra.aux;
         strbuf_reset(&sb);
         strbuf_puts(&sb, " phi slot=");
         strbuf_put_u64(&sb, aux ? (u64)(unsigned)aux->slot_id : 0u);
         strbuf_puts(&sb, " preds=");
         ssa_dump_sb(w, &sb);
         if (aux) {
           for (u32 p = 0; p < aux->npreds; ++p) {
             strbuf_reset(&sb);
             if (p) strbuf_putc(&sb, ',');
             strbuf_putc(&sb, 'b');
             strbuf_put_u64(&sb, (u64)(unsigned)aux->pred_blocks[p]);
             strbuf_puts(&sb, ":v");
             strbuf_put_u64(&sb, (u64)(unsigned)aux->pred_vals[p]);
             ssa_dump_sb(w, &sb);
           }
         }
       } else {
         SsaDumpUseCtx ctx;
         ctx.w = w;
         ctx.any = 0;
         ssa_dump_write(w, " uses=");
         opt_walk_inst_operands(f, in, ssa_dump_use, &ctx);
         if (!ctx.any) ssa_dump_write(w, "-");
       }
       ssa_dump_write(w, "\n");
     }
   }
 }