pass_ssa.c (32593B)
1 /* pass_ssa.c - mem2reg SSA construction and phi destruction for O2. */ 2 3 #include <string.h> 4 5 #include "core/arena.h" 6 #include "core/core.h" 7 #include "core/slice.h" 8 #include "core/strbuf.h" 9 #include "opt/opt_internal.h" 10 11 typedef struct SlotStack { 12 Val* vals; 13 u32 n; 14 u32 cap; 15 } SlotStack; 16 17 typedef struct RenameCtx { 18 Func* f; 19 OptAnalysis* analysis; 20 u8* promoted; 21 Val* repl; 22 u32 repl_cap; 23 SlotStack* stacks; 24 } RenameCtx; 25 26 typedef struct EdgeMove { 27 Val dst; 28 Val src; 29 KitCgTypeId type; 30 u8 cls; 31 } EdgeMove; 32 33 typedef struct RegRenameCtx { 34 Func* f; 35 OptAnalysis* analysis; 36 u32 old_nregs; 37 SlotStack* stacks; 38 } RegRenameCtx; 39 40 static u8 ssa_type_class(Func* f, KitCgTypeId ty) { 41 return opt_value_reg_class(f->c, ty); 42 } 43 44 static u32 opnd_slot_id(const Operand* op) { 45 if (!op || op->kind != OPK_LOCAL) return 0; 46 return (u32)op->v.frame_slot; 47 } 48 49 static int base_slot_promotable(const Func* f, u32 slot_id) { 50 if (slot_id == 0 || slot_id > f->nframe_slots) return 0; 51 const IRFrameSlot* s = &f->frame_slots[slot_id - 1u]; 52 if (s->kind != FS_LOCAL) return 0; 53 if (s->flags & (FSF_ADDR_TAKEN | FSF_VOLATILE)) return 0; 54 return 1; 55 } 56 57 static int operand_has_slot(const Operand* op, u32 slot_id) { 58 return op && op->kind == OPK_LOCAL && opnd_slot_id(op) == slot_id; 59 } 60 61 static int abivalue_has_slot(const CGABIValue* v, u32 slot_id) { 62 if (!v) return 0; 63 if (operand_has_slot(&v->storage, slot_id)) return 1; 64 for (u32 i = 0; i < v->nparts; ++i) 65 if (operand_has_slot(&v->parts[i].op, slot_id)) return 1; 66 return 0; 67 } 68 69 static int aux_has_slot(const Inst* in, u32 slot_id) { 70 switch ((IROp)in->op) { 71 case IR_CALL: { 72 IRCallAux* aux = (IRCallAux*)in->extra.aux; 73 if (!aux) return 0; 74 if (aux->use_plan_replay) { 75 if (operand_has_slot(&aux->plan.callee, slot_id)) return 1; 76 for (u32 i = 0; i < aux->plan.nargs; ++i) 77 if (operand_has_slot(&aux->plan.args[i].src, slot_id)) return 1; 78 for (u32 i = 0; i < aux->plan.nrets; ++i) 79 if (operand_has_slot(&aux->plan.rets[i].dst, slot_id)) return 1; 80 } else { 81 if (operand_has_slot(&aux->desc.callee, slot_id)) return 1; 82 for (u32 i = 0; i < aux->desc.nargs; ++i) 83 if (abivalue_has_slot(&aux->desc.args[i], slot_id)) return 1; 84 if (abivalue_has_slot(&aux->desc.ret, slot_id)) return 1; 85 } 86 break; 87 } 88 case IR_RET: { 89 IRRetAux* aux = (IRRetAux*)in->extra.aux; 90 return aux && aux->present && abivalue_has_slot(&aux->val, slot_id); 91 } 92 case IR_SCOPE_BEGIN: 93 return 0; 94 case IR_ASM_BLOCK: { 95 IRAsmAux* aux = (IRAsmAux*)in->extra.aux; 96 if (!aux) return 0; 97 for (u32 i = 0; i < aux->nin; ++i) 98 if (operand_has_slot(&aux->in_ops[i], slot_id)) return 1; 99 for (u32 i = 0; i < aux->nout; ++i) 100 if (operand_has_slot(&aux->out_ops[i], slot_id)) return 1; 101 break; 102 } 103 case IR_INTRINSIC: { 104 IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux; 105 if (!aux) return 0; 106 for (u32 i = 0; i < aux->narg; ++i) 107 if (operand_has_slot(&aux->args[i], slot_id)) return 1; 108 for (u32 i = 0; i < aux->ndst; ++i) 109 if (operand_has_slot(&aux->dsts[i], slot_id)) return 1; 110 break; 111 } 112 default: 113 break; 114 } 115 return 0; 116 } 117 118 static int slot_access_promotable(const Func* f, const Inst* in, u32 slot_id) { 119 if ((IROp)in->op == IR_LOAD) { 120 if (in->nopnds < 2 || opnd_slot_id(&in->opnds[1]) != slot_id) return 1; 121 if (in->opnds[0].kind != OPK_REG || opt_mem_observable(&in->extra.mem)) 122 return 0; 123 /* Post-EA cg layer can produce LOAD opnds[1]=OPK_LOCAL(slot) with an 124 * access type that differs from the slot's declared type (e.g. a 125 * sub-word read for type-punning). mem2reg would silently lose those 126 * bits, so block promotion when the access type does not match the 127 * slot's declared type. */ 128 const IRFrameSlot* s = &f->frame_slots[slot_id - 1u]; 129 KitCgTypeId at = in->extra.mem.type; 130 if (at && at != s->type) return 0; 131 if (in->opnds[0].type && in->opnds[0].type != s->type) return 0; 132 return 1; 133 } 134 if ((IROp)in->op == IR_STORE) { 135 if (in->nopnds < 2 || opnd_slot_id(&in->opnds[0]) != slot_id) return 1; 136 if (opt_mem_observable(&in->extra.mem)) return 0; 137 if (in->opnds[1].kind != OPK_REG && in->opnds[1].kind != OPK_IMM) return 0; 138 const IRFrameSlot* s = &f->frame_slots[slot_id - 1u]; 139 KitCgTypeId at = in->extra.mem.type; 140 if (at && at != s->type) return 0; 141 if (in->opnds[1].type && in->opnds[1].type != s->type) return 0; 142 return 1; 143 } 144 for (u32 i = 0; i < in->nopnds; ++i) 145 if (opnd_slot_id(&in->opnds[i]) == slot_id) return 0; 146 if (aux_has_slot(in, slot_id)) return 0; 147 return 1; 148 } 149 150 static u8* find_promoted_slots(Func* f) { 151 u8* promoted = arena_zarray(f->arena, u8, f->nframe_slots + 1u); 152 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) { 153 if (!base_slot_promotable(f, sid)) continue; 154 promoted[sid] = 1; 155 } 156 for (u32 b = 0; b < f->nblocks; ++b) { 157 Block* bl = &f->blocks[b]; 158 for (u32 i = 0; i < bl->ninsts; ++i) { 159 Inst* in = &bl->insts[i]; 160 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) { 161 if (promoted[sid] && !slot_access_promotable(f, in, sid)) 162 promoted[sid] = 0; 163 } 164 } 165 } 166 return promoted; 167 } 168 169 static void stack_push(Arena* a, SlotStack* s, Val v) { 170 if (s->n == s->cap) { 171 u32 ncap = s->cap ? s->cap * 2u : 4u; 172 Val* vals = arena_array(a, Val, ncap); 173 if (s->vals) memcpy(vals, s->vals, sizeof(vals[0]) * s->n); 174 s->vals = vals; 175 s->cap = ncap; 176 } 177 s->vals[s->n++] = v; 178 } 179 180 static Val stack_top(const SlotStack* s) { 181 return s && s->n ? s->vals[s->n - 1u] : VAL_NONE; 182 } 183 184 static int reg_in_defs(const Inst* in, Reg r) { 185 if (!in || r == (Reg)REG_NONE) return 0; 186 if (in->def == (Val)r) return 1; 187 for (u32 i = 0; i < in->ndefs; ++i) 188 if (in->defs[i] == (Val)r) return 1; 189 return 0; 190 } 191 192 static u8* find_reg_def_blocks(Func* f, u32 old_nregs) { 193 u8* def_blocks = arena_zarray(f->arena, u8, old_nregs * f->nblocks); 194 for (u32 b = 0; b < f->nblocks; ++b) { 195 Block* bl = &f->blocks[b]; 196 for (u32 i = 0; i < bl->ninsts; ++i) { 197 Inst* in = &bl->insts[i]; 198 if (in->def != VAL_NONE && in->def < old_nregs) 199 def_blocks[in->def * f->nblocks + b] = 1; 200 for (u32 d = 0; d < in->ndefs; ++d) { 201 Val v = in->defs[d]; 202 if (v != VAL_NONE && v < old_nregs) def_blocks[v * f->nblocks + b] = 1; 203 } 204 } 205 } 206 return def_blocks; 207 } 208 209 static void compute_reg_phi_sites(Func* f, OptAnalysis* a, 210 const OptLiveInfo* live, u32 old_nregs, 211 u8* needs_phi) { 212 u8* def_blocks = find_reg_def_blocks(f, old_nregs); 213 u32* work = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u); 214 u8* queued = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u); 215 216 for (u32 r = 1; r < old_nregs; ++r) { 217 if (!f->preg_type[r]) continue; 218 memset(queued, 0, f->nblocks); 219 u32 wn = 0; 220 for (u32 b = 0; b < f->nblocks; ++b) { 221 if (!def_blocks[r * f->nblocks + b]) continue; 222 queued[b] = 1; 223 work[wn++] = b; 224 } 225 while (wn) { 226 u32 x = work[--wn]; 227 OptBlockList* df = &a->dom_frontier[x]; 228 for (u32 i = 0; i < df->n; ++i) { 229 u32 y = df->items[i]; 230 if (needs_phi[r * f->nblocks + y]) continue; 231 if (live && !opt_bitset_has(&live->blocks[y].live_in, (Val)r)) continue; 232 needs_phi[r * f->nblocks + y] = 1; 233 if (!queued[y]) { 234 queued[y] = 1; 235 work[wn++] = y; 236 } 237 } 238 } 239 } 240 } 241 242 static void insert_reg_phis(Func* f, u32 b, u32 old_nregs, 243 const u8* needs_phi) { 244 Block* bl = &f->blocks[b]; 245 u32 nphi = 0; 246 for (u32 r = 1; r < old_nregs; ++r) 247 if (needs_phi[r * f->nblocks + b]) ++nphi; 248 if (!nphi) return; 249 250 u32 old_nvals = f->nvals; 251 Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + nphi); 252 u32 w = 0; 253 for (u32 r = 1; r < old_nregs; ++r) { 254 if (!needs_phi[r * f->nblocks + b]) continue; 255 Inst* in = &insts[w++]; 256 in->op = IR_PHI; 257 ir_assign_inst_id(f, in); 258 in->type = f->preg_type[r]; 259 in->def = ir_alloc_val(f, f->preg_type[r], f->preg_cls[r]); 260 f->val_def_block[in->def] = b; 261 f->val_def_inst[in->def] = w - 1u; 262 IRPhiAux* aux = arena_znew(f->arena, IRPhiAux); 263 aux->reg_id = r; 264 aux->npreds = bl->npreds; 265 if (bl->npreds) { 266 aux->pred_blocks = arena_array(f->arena, u32, bl->npreds); 267 aux->pred_vals = arena_zarray(f->arena, Val, bl->npreds); 268 memcpy(aux->pred_blocks, bl->preds, sizeof(u32) * bl->npreds); 269 } 270 in->extra.aux = aux; 271 } 272 if (bl->ninsts) memcpy(insts + nphi, bl->insts, sizeof(Inst) * bl->ninsts); 273 bl->insts = insts; 274 bl->ninsts += nphi; 275 bl->cap = bl->ninsts; 276 for (Val v = 1; v < old_nvals; ++v) 277 if (f->val_def_block[v] == b) f->val_def_inst[v] += nphi; 278 } 279 280 static Val reg_stack_top(RegRenameCtx* ctx, Reg r) { 281 if (r == (Reg)REG_NONE || (u32)r >= ctx->old_nregs) return VAL_NONE; 282 return stack_top(&ctx->stacks[(u32)r]); 283 } 284 285 static void reg_replace_use(RegRenameCtx* ctx, Operand* op) { 286 if (!op || op->kind != OPK_REG) return; 287 Reg r = op->v.reg; 288 Val v = reg_stack_top(ctx, r); 289 if (v == VAL_NONE) return; 290 op->v.reg = (Reg)v; 291 op->type = ctx->f->val_type[v]; 292 op->cls = ctx->f->val_cls[v]; 293 } 294 295 static Val reg_define_operand(RegRenameCtx* ctx, u32 b, u32 i, Inst* in, 296 Operand* op, u32 def_index, u32* pushed) { 297 if (!op || op->kind != OPK_REG) return VAL_NONE; 298 Reg r = op->v.reg; 299 if (r == (Reg)REG_NONE || (u32)r >= ctx->old_nregs) return VAL_NONE; 300 KitCgTypeId ty = op->type ? op->type : ctx->f->preg_type[(u32)r]; 301 u8 cls = op->cls; 302 Val v = ir_alloc_val(ctx->f, ty, cls); 303 op->v.reg = (Reg)v; 304 op->type = ty; 305 op->cls = cls; 306 if (def_index == 0 && in->def == (Val)r) in->def = v; 307 if (def_index < in->ndefs && in->defs[def_index] == (Val)r) 308 in->defs[def_index] = v; 309 ctx->f->val_def_block[v] = b; 310 ctx->f->val_def_inst[v] = i; 311 stack_push(ctx->f->arena, &ctx->stacks[(u32)r], v); 312 pushed[(u32)r]++; 313 return v; 314 } 315 316 static u32 reg_def_index(const Inst* in, Reg r, u32 ordinal) { 317 if (!in || !in->ndefs) return 0; 318 u32 seen = 0; 319 for (u32 i = 0; i < in->ndefs; ++i) { 320 if (in->defs[i] != (Val)r) continue; 321 if (seen == ordinal) return i; 322 ++seen; 323 } 324 return 0; 325 } 326 327 static void reg_replace_use_cb(Func* f, Inst* in, Operand* op, int is_def, 328 void* ctx) { 329 (void)f; 330 (void)in; 331 if (!is_def) reg_replace_use((RegRenameCtx*)ctx, op); 332 } 333 334 static void reg_replace_inst_uses(RegRenameCtx* ctx, Inst* in) { 335 /* Route through the centralized operand walk: it applies the same use/def 336 * classification (incl. the IR_ATOMIC_CAS two-def case) and visits the same 337 * IR_CALL/RET/ASM/INTRINSIC aux operands, decomposing OPK_INDIRECT into its 338 * base/index — exactly what the bespoke walk did. The callback rewrites only 339 * uses; defs are renamed separately (reg_define_inst_defs, which needs the 340 * per-def index/version-stack context the generic callback can't carry). */ 341 opt_walk_inst_operands(ctx->f, in, reg_replace_use_cb, ctx); 342 } 343 344 static void reg_define_abivalue(RegRenameCtx* ctx, u32 b, u32 i, Inst* in, 345 CGABIValue* v, u32* pushed) { 346 if (!v) return; 347 if (v->storage.kind == OPK_REG && reg_in_defs(in, v->storage.v.reg)) 348 reg_define_operand(ctx, b, i, in, &v->storage, 0, pushed); 349 for (u32 p = 0; p < v->nparts; ++p) { 350 Operand* op = (Operand*)&v->parts[p].op; 351 if (op->kind == OPK_REG && reg_in_defs(in, op->v.reg)) 352 reg_define_operand(ctx, b, i, in, op, p, pushed); 353 } 354 } 355 356 static void reg_define_inst_defs(RegRenameCtx* ctx, u32 b, u32 i, Inst* in, 357 u32* pushed) { 358 switch ((IROp)in->op) { 359 case IR_CALL: { 360 IRCallAux* aux = (IRCallAux*)in->extra.aux; 361 if (!aux) break; 362 if (aux->use_plan_replay) { 363 for (u32 r = 0; r < aux->plan.nrets; ++r) { 364 if (aux->plan.rets[r].dst.kind == OPK_REG && 365 reg_in_defs(in, aux->plan.rets[r].dst.v.reg)) 366 reg_define_operand(ctx, b, i, in, &aux->plan.rets[r].dst, r, 367 pushed); 368 } 369 } else { 370 reg_define_abivalue(ctx, b, i, in, &aux->desc.ret, pushed); 371 } 372 break; 373 } 374 case IR_ATOMIC_CAS: 375 if (in->nopnds >= 1 && in->opnds[0].kind == OPK_REG) 376 reg_define_operand(ctx, b, i, in, &in->opnds[0], 0, pushed); 377 if (in->nopnds >= 2 && in->opnds[1].kind == OPK_REG) 378 reg_define_operand(ctx, b, i, in, &in->opnds[1], 1, pushed); 379 break; 380 case IR_ASM_BLOCK: { 381 IRAsmAux* aux = (IRAsmAux*)in->extra.aux; 382 if (!aux) break; 383 for (u32 o = 0; o < aux->nout; ++o) { 384 if (aux->out_ops[o].kind != OPK_REG) continue; 385 reg_define_operand(ctx, b, i, in, &aux->out_ops[o], 386 reg_def_index(in, aux->out_ops[o].v.reg, o), pushed); 387 } 388 break; 389 } 390 case IR_INTRINSIC: { 391 IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux; 392 if (!aux) break; 393 for (u32 d = 0; d < aux->ndst; ++d) { 394 if (aux->dsts[d].kind != OPK_REG) continue; 395 reg_define_operand(ctx, b, i, in, &aux->dsts[d], d, pushed); 396 if (aux->result_vals) aux->result_vals[d] = (Val)aux->dsts[d].v.reg; 397 } 398 break; 399 } 400 default: 401 if (in->nopnds && in->opnds[0].kind == OPK_REG && 402 reg_in_defs(in, in->opnds[0].v.reg)) 403 reg_define_operand(ctx, b, i, in, &in->opnds[0], 0, pushed); 404 break; 405 } 406 } 407 408 static void reg_rename_block(RegRenameCtx* ctx, u32 b) { 409 Func* f = ctx->f; 410 Block* bl = &f->blocks[b]; 411 u32* pushed = arena_zarray(f->arena, u32, ctx->old_nregs); 412 413 for (u32 i = 0; i < bl->ninsts; ++i) { 414 Inst* in = &bl->insts[i]; 415 if ((IROp)in->op != IR_PHI) break; 416 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 417 if (!aux || !aux->reg_id || aux->reg_id >= ctx->old_nregs) continue; 418 stack_push(f->arena, &ctx->stacks[aux->reg_id], in->def); 419 pushed[aux->reg_id]++; 420 } 421 422 for (u32 i = 0; i < bl->ninsts; ++i) { 423 Inst* in = &bl->insts[i]; 424 if ((IROp)in->op == IR_PHI) continue; 425 reg_replace_inst_uses(ctx, in); 426 reg_define_inst_defs(ctx, b, i, in, pushed); 427 } 428 429 for (u32 s = 0; s < bl->nsucc; ++s) { 430 u32 succ = bl->succ[s]; 431 if (succ >= f->nblocks) continue; 432 Block* sb = &f->blocks[succ]; 433 u32 pred_idx = OPT_USE_NONE; 434 for (u32 p = 0; p < sb->npreds; ++p) { 435 if (sb->preds[p] == b) { 436 pred_idx = p; 437 break; 438 } 439 } 440 if (pred_idx == OPT_USE_NONE) continue; 441 for (u32 i = 0; i < sb->ninsts; ++i) { 442 Inst* phi = &sb->insts[i]; 443 if ((IROp)phi->op != IR_PHI) break; 444 IRPhiAux* aux = (IRPhiAux*)phi->extra.aux; 445 if (!aux || !aux->reg_id || aux->reg_id >= ctx->old_nregs) continue; 446 aux->pred_vals[pred_idx] = reg_stack_top(ctx, (Reg)aux->reg_id); 447 } 448 } 449 450 OptBlockList* children = &ctx->analysis->dom_children[b]; 451 for (u32 i = 0; i < children->n; ++i) 452 reg_rename_block(ctx, children->items[i]); 453 454 for (u32 r = 1; r < ctx->old_nregs; ++r) { 455 while (pushed[r]--) { 456 if (ctx->stacks[r].n) --ctx->stacks[r].n; 457 } 458 } 459 } 460 461 void opt_build_reg_ssa(Func* f) { 462 if (!f || f->nblocks == 0 || f->npregs <= 1) { 463 if (f) opt_rebuild_def_use(f); 464 return; 465 } 466 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 467 468 u32 old_nregs = f->npregs; 469 OptAnalysis a; 470 opt_analysis_build_order(f, &a); 471 opt_analysis_build_dominators(f, &a); 472 opt_analysis_build_dom_frontier(f, &a); 473 474 OptLiveInfo live; 475 opt_live_blocks(f, &live); 476 u8* needs_phi = arena_zarray(f->arena, u8, old_nregs * f->nblocks); 477 compute_reg_phi_sites(f, &a, &live, old_nregs, needs_phi); 478 for (u32 b = 0; b < f->nblocks; ++b) 479 insert_reg_phis(f, b, old_nregs, needs_phi); 480 481 RegRenameCtx ctx; 482 memset(&ctx, 0, sizeof ctx); 483 ctx.f = f; 484 ctx.analysis = &a; 485 ctx.old_nregs = old_nregs; 486 ctx.stacks = arena_zarray(f->arena, SlotStack, old_nregs); 487 reg_rename_block(&ctx, f->entry); 488 f->opt_reg_ssa = 1; 489 opt_rebuild_def_use(f); 490 } 491 492 static Val resolve_repl(const RenameCtx* ctx, Val v) { 493 while (v != VAL_NONE && v < ctx->repl_cap && ctx->repl[v] != VAL_NONE && 494 ctx->repl[v] != v) { 495 v = ctx->repl[v]; 496 } 497 return v; 498 } 499 500 static void replace_use(Func* f, Inst* in, Operand* op, int is_def, void* arg) { 501 (void)in; 502 RenameCtx* ctx = (RenameCtx*)arg; 503 if (is_def || op->kind != OPK_REG) return; 504 Val old = (Val)op->v.reg; 505 if (old == VAL_NONE || old >= f->nvals) return; 506 Val repl = resolve_repl(ctx, old); 507 if (repl != VAL_NONE && repl != old) { 508 op->v.reg = (Reg)repl; 509 op->type = f->val_type[repl]; 510 op->cls = f->val_cls[repl]; 511 } 512 } 513 514 static void insert_phis(Func* f, u32 b, const u8* needs_phi) { 515 Block* bl = &f->blocks[b]; 516 u32 nphi = 0; 517 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) 518 if (needs_phi[sid * f->nblocks + b]) ++nphi; 519 if (!nphi) return; 520 521 u32 old_nvals = f->nvals; 522 Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + nphi); 523 u32 w = 0; 524 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) { 525 if (!needs_phi[sid * f->nblocks + b]) continue; 526 const IRFrameSlot* slot = &f->frame_slots[sid - 1u]; 527 Inst* in = &insts[w++]; 528 in->op = IR_PHI; 529 ir_assign_inst_id(f, in); 530 in->type = slot->type; 531 in->def = ir_alloc_val(f, slot->type, ssa_type_class(f, slot->type)); 532 f->val_def_block[in->def] = b; 533 f->val_def_inst[in->def] = w - 1u; 534 IRPhiAux* aux = arena_znew(f->arena, IRPhiAux); 535 aux->slot_id = sid; 536 aux->npreds = bl->npreds; 537 if (bl->npreds) { 538 aux->pred_blocks = arena_array(f->arena, u32, bl->npreds); 539 aux->pred_vals = arena_zarray(f->arena, Val, bl->npreds); 540 memcpy(aux->pred_blocks, bl->preds, sizeof(u32) * bl->npreds); 541 } 542 in->extra.aux = aux; 543 } 544 if (bl->ninsts) memcpy(insts + nphi, bl->insts, sizeof(Inst) * bl->ninsts); 545 bl->insts = insts; 546 bl->ninsts += nphi; 547 bl->cap = bl->ninsts; 548 for (Val v = 1; v < old_nvals; ++v) 549 if (f->val_def_block[v] == b) f->val_def_inst[v] += nphi; 550 } 551 552 static void mark_def_blocks(Func* f, const u8* promoted, u8* def_blocks) { 553 for (u32 b = 0; b < f->nblocks; ++b) { 554 Block* bl = &f->blocks[b]; 555 for (u32 i = 0; i < bl->ninsts; ++i) { 556 Inst* in = &bl->insts[i]; 557 if ((IROp)in->op != IR_STORE || in->nopnds < 2) continue; 558 u32 sid = opnd_slot_id(&in->opnds[0]); 559 if (sid && promoted[sid]) def_blocks[sid * f->nblocks + b] = 1; 560 } 561 } 562 } 563 564 static void compute_phi_sites(Func* f, OptAnalysis* a, const u8* promoted, 565 u8* needs_phi) { 566 u8* def_blocks = 567 arena_zarray(f->arena, u8, (f->nframe_slots + 1u) * f->nblocks); 568 mark_def_blocks(f, promoted, def_blocks); 569 u32* work = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u); 570 u8* queued = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u); 571 572 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) { 573 if (!promoted[sid]) continue; 574 memset(queued, 0, f->nblocks); 575 u32 wn = 0; 576 for (u32 b = 0; b < f->nblocks; ++b) { 577 if (!def_blocks[sid * f->nblocks + b]) continue; 578 queued[b] = 1; 579 work[wn++] = b; 580 } 581 while (wn) { 582 u32 x = work[--wn]; 583 OptBlockList* df = &a->dom_frontier[x]; 584 for (u32 i = 0; i < df->n; ++i) { 585 u32 y = df->items[i]; 586 if (needs_phi[sid * f->nblocks + y]) continue; 587 needs_phi[sid * f->nblocks + y] = 1; 588 if (!queued[y]) { 589 queued[y] = 1; 590 work[wn++] = y; 591 } 592 } 593 } 594 } 595 } 596 597 static void rewrite_store_immediate(RenameCtx* ctx, Inst* in, u32 b, u32 i, 598 u32 sid) { 599 Operand src = in->opnds[1]; 600 Val v = ir_alloc_val(ctx->f, src.type, src.cls); 601 Operand* opnds = arena_array(ctx->f->arena, Operand, 1); 602 opnds[0] = src; 603 opnds[0].kind = OPK_REG; 604 opnds[0].v.reg = (Reg)v; 605 in->op = IR_LOAD_IMM; 606 in->type = src.type; 607 in->def = v; 608 in->opnds = opnds; 609 in->nopnds = 1; 610 in->extra.imm = src.v.imm; 611 ctx->f->val_def_block[v] = b; 612 ctx->f->val_def_inst[v] = i; 613 stack_push(ctx->f->arena, &ctx->stacks[sid], v); 614 } 615 616 static void rename_block(RenameCtx* ctx, u32 b) { 617 Func* f = ctx->f; 618 Block* bl = &f->blocks[b]; 619 u32* pushed = arena_zarray(f->arena, u32, f->nframe_slots + 1u); 620 621 for (u32 i = 0; i < bl->ninsts; ++i) { 622 Inst* in = &bl->insts[i]; 623 if ((IROp)in->op != IR_PHI) break; 624 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 625 if (!aux || !aux->slot_id || !ctx->promoted[aux->slot_id]) continue; 626 stack_push(f->arena, &ctx->stacks[aux->slot_id], in->def); 627 pushed[aux->slot_id]++; 628 } 629 630 for (u32 i = 0; i < bl->ninsts; ++i) { 631 Inst* in = &bl->insts[i]; 632 if ((IROp)in->op == IR_PHI) continue; 633 if ((IROp)in->op == IR_STORE && in->nopnds >= 2) { 634 u32 sid = opnd_slot_id(&in->opnds[0]); 635 if (sid && ctx->promoted[sid]) { 636 Operand src = in->opnds[1]; 637 if (src.kind == OPK_REG) { 638 stack_push(f->arena, &ctx->stacks[sid], 639 resolve_repl(ctx, (Val)src.v.reg)); 640 in->op = IR_NOP; 641 in->nopnds = 0; 642 in->opnds = NULL; 643 in->def = VAL_NONE; 644 } else { 645 rewrite_store_immediate(ctx, in, b, i, sid); 646 } 647 pushed[sid]++; 648 continue; 649 } 650 } 651 if ((IROp)in->op == IR_LOAD && in->nopnds >= 2) { 652 u32 sid = opnd_slot_id(&in->opnds[1]); 653 if (sid && ctx->promoted[sid] && in->def != VAL_NONE) { 654 Val cur = stack_top(&ctx->stacks[sid]); 655 if (cur == VAL_NONE) continue; 656 if (in->def < ctx->repl_cap) 657 ctx->repl[in->def] = resolve_repl(ctx, cur); 658 in->op = IR_NOP; 659 in->nopnds = 0; 660 in->opnds = NULL; 661 in->def = VAL_NONE; 662 continue; 663 } 664 } 665 opt_walk_inst_operands(f, in, replace_use, ctx); 666 } 667 668 for (u32 s = 0; s < bl->nsucc; ++s) { 669 u32 succ = bl->succ[s]; 670 if (succ >= f->nblocks) continue; 671 Block* sb = &f->blocks[succ]; 672 u32 pred_idx = OPT_USE_NONE; 673 for (u32 p = 0; p < sb->npreds; ++p) { 674 if (sb->preds[p] == b) { 675 pred_idx = p; 676 break; 677 } 678 } 679 if (pred_idx == OPT_USE_NONE) continue; 680 for (u32 i = 0; i < sb->ninsts; ++i) { 681 Inst* phi = &sb->insts[i]; 682 if ((IROp)phi->op != IR_PHI) break; 683 IRPhiAux* aux = (IRPhiAux*)phi->extra.aux; 684 if (!aux || !aux->slot_id || !ctx->promoted[aux->slot_id]) continue; 685 aux->pred_vals[pred_idx] = 686 resolve_repl(ctx, stack_top(&ctx->stacks[aux->slot_id])); 687 } 688 } 689 690 OptBlockList* children = &ctx->analysis->dom_children[b]; 691 for (u32 i = 0; i < children->n; ++i) rename_block(ctx, children->items[i]); 692 693 for (u32 sid = 1; sid <= f->nframe_slots; ++sid) { 694 while (pushed[sid]--) { 695 if (ctx->stacks[sid].n) --ctx->stacks[sid].n; 696 } 697 } 698 } 699 700 static void replace_phi_inputs(Func* f, RenameCtx* ctx) { 701 for (u32 b = 0; b < f->nblocks; ++b) { 702 Block* bl = &f->blocks[b]; 703 for (u32 i = 0; i < bl->ninsts; ++i) { 704 Inst* in = &bl->insts[i]; 705 if ((IROp)in->op != IR_PHI) break; 706 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 707 if (!aux) continue; 708 for (u32 p = 0; p < aux->npreds; ++p) 709 aux->pred_vals[p] = resolve_repl(ctx, aux->pred_vals[p]); 710 } 711 } 712 } 713 714 void opt_build_ssa(Func* f) { 715 if (f) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 716 if (!f || f->nblocks == 0 || f->nframe_slots == 0) { 717 if (f) opt_rebuild_def_use(f); 718 return; 719 } 720 721 OptAnalysis a; 722 opt_analysis_build_order(f, &a); 723 opt_analysis_build_dominators(f, &a); 724 opt_analysis_build_dom_frontier(f, &a); 725 726 u8* promoted = find_promoted_slots(f); 727 u8* needs_phi = 728 arena_zarray(f->arena, u8, (f->nframe_slots + 1u) * f->nblocks); 729 compute_phi_sites(f, &a, promoted, needs_phi); 730 for (u32 b = 0; b < f->nblocks; ++b) insert_phis(f, b, needs_phi); 731 732 RenameCtx ctx; 733 memset(&ctx, 0, sizeof ctx); 734 ctx.f = f; 735 ctx.analysis = &a; 736 ctx.promoted = promoted; 737 ctx.repl_cap = f->vals_cap ? f->vals_cap : f->nvals; 738 ctx.repl = arena_zarray(f->arena, Val, ctx.repl_cap ? ctx.repl_cap : 1u); 739 ctx.stacks = arena_zarray(f->arena, SlotStack, f->nframe_slots + 1u); 740 rename_block(&ctx, f->entry); 741 742 for (u32 b = 0; b < f->nblocks; ++b) { 743 Block* bl = &f->blocks[b]; 744 for (u32 i = 0; i < bl->ninsts; ++i) 745 opt_walk_inst_operands(f, &bl->insts[i], replace_use, &ctx); 746 } 747 replace_phi_inputs(f, &ctx); 748 opt_rebuild_def_use(f); 749 } 750 751 static int ssa_is_terminator(const Inst* in) { 752 switch ((IROp)in->op) { 753 case IR_BR: 754 case IR_CONDBR: 755 case IR_CMP_BRANCH: 756 case IR_SWITCH: 757 case IR_INDIRECT_BRANCH: 758 case IR_RET: 759 case IR_UNREACHABLE: 760 case IR_BREAK_TO: 761 case IR_CONTINUE_TO: 762 return 1; 763 case IR_INTRINSIC: { 764 IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux; 765 return aux && (aux->kind == INTRIN_LONGJMP || aux->kind == INTRIN_TRAP); 766 } 767 default: 768 return 0; 769 } 770 } 771 772 static Inst make_copy_inst(Func* f, Val dst, Val src, KitCgTypeId ty, u8 cls) { 773 Inst in; 774 memset(&in, 0, sizeof in); 775 in.op = IR_COPY; 776 in.flags = IRF_NO_COALESCE; 777 ir_assign_inst_id(f, &in); 778 in.type = ty; 779 in.def = dst; 780 in.nopnds = 2; 781 in.opnds = arena_array(f->arena, Operand, 2); 782 in.opnds[0].kind = OPK_REG; 783 in.opnds[0].type = ty; 784 in.opnds[0].cls = cls; 785 in.opnds[0].v.reg = (Reg)dst; 786 in.opnds[1].kind = OPK_REG; 787 in.opnds[1].type = ty; 788 in.opnds[1].cls = cls; 789 in.opnds[1].v.reg = (Reg)src; 790 return in; 791 } 792 793 static void insert_edge_moves(Func* f, u32 b, const EdgeMove* moves, u32 n) { 794 if (!n) return; 795 Block* bl = &f->blocks[b]; 796 u32 term = bl->ninsts && ssa_is_terminator(&bl->insts[bl->ninsts - 1u]); 797 u32 insert_at = bl->ninsts - term; 798 u32 extra = n == 1 ? 1u : n * 2u; 799 Inst* insts = arena_zarray(f->arena, Inst, bl->ninsts + extra); 800 if (insert_at) memcpy(insts, bl->insts, sizeof(Inst) * insert_at); 801 u32 w = insert_at; 802 if (n == 1) { 803 insts[w++] = make_copy_inst(f, moves[0].dst, moves[0].src, moves[0].type, 804 moves[0].cls); 805 } else { 806 Val* temps = arena_array(f->arena, Val, n); 807 for (u32 i = 0; i < n; ++i) { 808 temps[i] = ir_alloc_val(f, moves[i].type, moves[i].cls); 809 f->val_def_block[temps[i]] = b; 810 f->val_def_inst[temps[i]] = w; 811 insts[w++] = make_copy_inst(f, temps[i], moves[i].src, moves[i].type, 812 moves[i].cls); 813 } 814 for (u32 i = 0; i < n; ++i) { 815 insts[w] = make_copy_inst(f, moves[i].dst, temps[i], moves[i].type, 816 moves[i].cls); 817 f->val_def_block[moves[i].dst] = b; 818 f->val_def_inst[moves[i].dst] = w; 819 ++w; 820 } 821 } 822 if (term) insts[w++] = bl->insts[bl->ninsts - 1u]; 823 bl->insts = insts; 824 bl->ninsts = w; 825 bl->cap = w; 826 if (n == 1) { 827 f->val_def_block[moves[0].dst] = b; 828 f->val_def_inst[moves[0].dst] = insert_at; 829 } 830 } 831 832 static void realign_phi_preds(Func* f) { 833 for (u32 b = 0; b < f->nblocks; ++b) { 834 Block* bl = &f->blocks[b]; 835 for (u32 i = 0; i < bl->ninsts; ++i) { 836 Inst* phi = &bl->insts[i]; 837 if ((IROp)phi->op != IR_PHI) break; 838 IRPhiAux* aux = (IRPhiAux*)phi->extra.aux; 839 if (!aux) continue; 840 u32 old_n = aux->npreds; 841 u32* old_blocks = aux->pred_blocks; 842 Val* old_vals = aux->pred_vals; 843 u32* pred_blocks = 844 bl->npreds ? arena_array(f->arena, u32, bl->npreds) : NULL; 845 Val* pred_vals = 846 bl->npreds ? arena_zarray(f->arena, Val, bl->npreds) : NULL; 847 for (u32 p = 0; p < bl->npreds; ++p) { 848 pred_blocks[p] = bl->preds[p]; 849 pred_vals[p] = phi->def; 850 for (u32 old = 0; old < old_n; ++old) { 851 if (old_blocks && old_blocks[old] == bl->preds[p]) { 852 pred_vals[p] = old_vals ? old_vals[old] : VAL_NONE; 853 break; 854 } 855 } 856 } 857 aux->npreds = bl->npreds; 858 aux->pred_blocks = pred_blocks; 859 aux->pred_vals = pred_vals; 860 } 861 } 862 } 863 864 void opt_make_conventional_ssa(Func* f) { 865 if (!f) return; 866 opt_analysis_invalidate( 867 f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP); 868 for (u32 b = 0; b < f->nblocks; ++b) { 869 Block* bl = &f->blocks[b]; 870 if (!bl->ninsts || (IROp)bl->insts[0].op != IR_PHI) continue; 871 for (u32 p = 0; p < bl->npreds; ++p) { 872 u32 pred = bl->preds[p]; 873 EdgeMove* moves = arena_array(f->arena, EdgeMove, bl->ninsts); 874 u32 n = 0; 875 for (u32 i = 0; i < bl->ninsts; ++i) { 876 Inst* phi = &bl->insts[i]; 877 if ((IROp)phi->op != IR_PHI) break; 878 IRPhiAux* aux = (IRPhiAux*)phi->extra.aux; 879 if (!aux || p >= aux->npreds) continue; 880 Val src = aux->pred_vals[p]; 881 if (src == VAL_NONE || src == phi->def) continue; 882 moves[n].dst = phi->def; 883 moves[n].src = src; 884 moves[n].type = phi->type; 885 moves[n].cls = f->val_cls[phi->def]; 886 ++n; 887 } 888 if (!n) continue; 889 u32 target = pred; 890 if (pred >= f->nblocks) continue; 891 if (f->blocks[pred].nsucc != 1) target = opt_split_edge(f, pred, b); 892 insert_edge_moves(f, target, moves, n); 893 } 894 } 895 opt_build_cfg(f); 896 realign_phi_preds(f); 897 opt_rebuild_def_use(f); 898 } 899 900 void opt_undo_ssa(Func* f) { 901 if (!f) return; 902 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 903 for (u32 b = 0; b < f->nblocks; ++b) { 904 Block* bl = &f->blocks[b]; 905 u32 w = 0; 906 for (u32 i = 0; i < bl->ninsts; ++i) { 907 if ((IROp)bl->insts[i].op == IR_PHI) continue; 908 bl->insts[w++] = bl->insts[i]; 909 } 910 bl->ninsts = w; 911 } 912 opt_rebuild_def_use(f); 913 } 914 915 static void ssa_dump_write(Writer* w, const char* s) { 916 kit_writer_write(w, s, slice_from_cstr(s).len); 917 } 918 919 static void ssa_dump_sb(Writer* w, const StrBuf* sb) { 920 kit_writer_write(w, strbuf_cstr(sb), strbuf_len(sb)); 921 } 922 923 typedef struct SsaDumpUseCtx { 924 Writer* w; 925 int any; 926 } SsaDumpUseCtx; 927 928 static void ssa_dump_use(Func* f, Inst* in, Operand* op, int is_def, 929 void* arg) { 930 (void)f; 931 (void)in; 932 if (is_def || op->kind != OPK_REG) return; 933 SsaDumpUseCtx* ctx = (SsaDumpUseCtx*)arg; 934 char buf[32]; 935 StrBuf sb; 936 strbuf_init(&sb, buf, sizeof buf); 937 if (ctx->any) strbuf_putc(&sb, ','); 938 strbuf_putc(&sb, 'v'); 939 strbuf_put_u64(&sb, (u64)(unsigned)op->v.reg); 940 ssa_dump_sb(ctx->w, &sb); 941 ctx->any = 1; 942 } 943 944 void opt_ssa_dump(Func* f, Writer* w) { 945 if (!f || !w) return; 946 opt_rebuild_def_use(f); 947 char buf[160]; 948 StrBuf sb; 949 strbuf_init(&sb, buf, sizeof buf); 950 strbuf_puts(&sb, "ssa blocks="); 951 strbuf_put_u64(&sb, (u64)(unsigned)f->nblocks); 952 strbuf_puts(&sb, " vals="); 953 strbuf_put_u64(&sb, (u64)(unsigned)f->nvals); 954 strbuf_puts(&sb, " uses="); 955 strbuf_put_u64(&sb, (u64)(unsigned)f->opt_nuses); 956 strbuf_putc(&sb, '\n'); 957 ssa_dump_sb(w, &sb); 958 for (u32 b = 0; b < f->nblocks; ++b) { 959 Block* bl = &f->blocks[b]; 960 strbuf_reset(&sb); 961 strbuf_puts(&sb, "block "); 962 strbuf_put_u64(&sb, (u64)(unsigned)b); 963 strbuf_puts(&sb, " preds="); 964 strbuf_put_u64(&sb, (u64)(unsigned)bl->npreds); 965 strbuf_puts(&sb, " succs="); 966 strbuf_put_u64(&sb, (u64)(unsigned)bl->nsucc); 967 strbuf_putc(&sb, '\n'); 968 ssa_dump_sb(w, &sb); 969 for (u32 i = 0; i < bl->ninsts; ++i) { 970 Inst* in = &bl->insts[i]; 971 strbuf_reset(&sb); 972 strbuf_puts(&sb, " i"); 973 strbuf_put_u64(&sb, (u64)(unsigned)in->id); 974 strbuf_puts(&sb, " op="); 975 strbuf_put_u64(&sb, (u64)(unsigned)in->op); 976 ssa_dump_sb(w, &sb); 977 if (in->def != VAL_NONE) { 978 strbuf_reset(&sb); 979 strbuf_puts(&sb, " def=v"); 980 strbuf_put_u64(&sb, (u64)(unsigned)in->def); 981 ssa_dump_sb(w, &sb); 982 } 983 if ((IROp)in->op == IR_PHI) { 984 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 985 strbuf_reset(&sb); 986 strbuf_puts(&sb, " phi slot="); 987 strbuf_put_u64(&sb, aux ? (u64)(unsigned)aux->slot_id : 0u); 988 strbuf_puts(&sb, " preds="); 989 ssa_dump_sb(w, &sb); 990 if (aux) { 991 for (u32 p = 0; p < aux->npreds; ++p) { 992 strbuf_reset(&sb); 993 if (p) strbuf_putc(&sb, ','); 994 strbuf_putc(&sb, 'b'); 995 strbuf_put_u64(&sb, (u64)(unsigned)aux->pred_blocks[p]); 996 strbuf_puts(&sb, ":v"); 997 strbuf_put_u64(&sb, (u64)(unsigned)aux->pred_vals[p]); 998 ssa_dump_sb(w, &sb); 999 } 1000 } 1001 } else { 1002 SsaDumpUseCtx ctx; 1003 ctx.w = w; 1004 ctx.any = 0; 1005 ssa_dump_write(w, " uses="); 1006 opt_walk_inst_operands(f, in, ssa_dump_use, &ctx); 1007 if (!ctx.any) ssa_dump_write(w, "-"); 1008 } 1009 ssa_dump_write(w, "\n"); 1010 } 1011 } 1012 }