pass_o2.c (80543B)
1 #include <kit/cg.h> 2 #include <string.h> 3 4 #include "cg/ir_eval.h" 5 #include "opt/opt_internal.h" 6 7 #define OPT_BLOCK_NONE 0xffffffffu 8 #define OPT_CLONE_MAX_BLOCK_INSTS 4u 9 #define OPT_CLONE_MAX_PREDS 4u 10 #define OPT_CLONE_ABS_GROWTH_LIMIT 32u 11 #define GVN_ENTRY_NONE 0xffffffffu 12 #define DSE_KEY_NONE 0xffffffffu 13 14 void opt_cleanup(Func* f) { 15 if (!f) return; 16 opt_build_cfg(f); 17 opt_jump_cleanup(f, OPT_JUMP_CLEANUP_CFG); 18 opt_build_cfg(f); 19 opt_verify(f, "o2-pre-ssa-cfg"); 20 opt_build_reg_ssa(f); 21 opt_verify(f, "o2-reg-ssa"); 22 opt_block_cloning(f); 23 opt_verify(f, "o2-block-clone-cfg"); 24 opt_build_ssa(f); 25 opt_verify(f, "o2-ssa"); 26 opt_ssa_dce(f); 27 opt_copy_cleanup(f); 28 opt_verify(f, "o2-pre-addr-cleanup"); 29 opt_addr_xform(f); 30 opt_verify(f, "o2-addr-xform-ssa"); 31 opt_ssa_dce(f); 32 opt_verify(f, "o2-addr-xform-dce"); 33 opt_copy_cleanup(f); 34 opt_verify(f, "o2-addr-xform-copy-cleanup"); 35 opt_simplify(f); 36 opt_verify(f, "o2-simplify-ssa"); 37 opt_ssa_dce(f); 38 opt_copy_cleanup(f); 39 opt_verify(f, "o2-simplify-cleanup"); 40 opt_gvn(f); 41 opt_verify(f, "o2-gvn-ssa"); 42 opt_copy_prop(f); 43 opt_verify(f, "o2-copy-prop-ssa"); 44 opt_ssa_dce(f); 45 opt_verify(f, "o2-copy-dce"); 46 opt_dse(f); 47 opt_verify(f, "o2-dse-ssa"); 48 opt_ssa_dce(f); 49 opt_verify(f, "o2-dse-dce"); 50 opt_build_loop_tree(f); 51 opt_licm(f); 52 opt_verify(f, "o2-licm-ssa"); 53 opt_pressure_relief(f); 54 opt_verify(f, "o2-pressure-relief-ssa"); 55 opt_make_conventional_ssa(f); 56 opt_verify(f, "o2-conventional-ssa"); 57 opt_ssa_combine(f); 58 opt_verify(f, "o2-ssa-combine"); 59 opt_undo_ssa(f); 60 opt_copy_cleanup(f); 61 opt_verify(f, "o2-undo-copy-cleanup"); 62 opt_jump_opt(f); 63 opt_verify(f, "o2-jump-opt"); 64 } 65 66 typedef struct CloneValMap { 67 Val old_val; 68 Val new_val; 69 } CloneValMap; 70 71 typedef struct GvnConst { 72 i64 value; 73 u8 valid; 74 } GvnConst; 75 76 typedef struct GvnOperandKey { 77 u8 kind; 78 u8 cls; 79 u16 pad; 80 KitCgTypeId type; 81 union { 82 Val reg; 83 i64 imm; 84 struct { 85 Val base; 86 Val index; 87 i32 ofs; 88 u8 log2_scale; 89 u8 pad[3]; 90 } ind; 91 } v; 92 } GvnOperandKey; 93 94 typedef struct GvnMemKey { 95 u8 valid; 96 u8 root_kind; 97 u8 has_addr; 98 u8 pad0; 99 u16 addr_space; 100 u16 flags; 101 KitCgTypeId mem_type; 102 u32 size; 103 u32 align; 104 i64 root_id; 105 i64 offset; 106 u32 root_version; 107 u32 unknown_version; 108 } GvnMemKey; 109 110 typedef struct GvnKey { 111 u16 op; 112 u16 nops; 113 KitCgTypeId type; 114 u8 cls; 115 u8 pad[3]; 116 i64 tag; 117 GvnMemKey mem; 118 GvnOperandKey ops[2]; 119 } GvnKey; 120 121 typedef struct GvnEntry { 122 GvnKey key; 123 Val val; 124 u32 block; 125 u32 inst; 126 u32 next; 127 } GvnEntry; 128 129 typedef struct GvnTable { 130 Func* f; 131 u32* buckets; 132 u32 nbuckets; 133 GvnEntry* entries; 134 u32 nentries; 135 u32 cap; 136 } GvnTable; 137 138 typedef struct GvnMemVersion { 139 u8 root_kind; 140 u8 pad0; 141 u16 addr_space; 142 i64 root_id; 143 u32 version; 144 } GvnMemVersion; 145 146 typedef struct GvnMemAvail { 147 GvnKey key; 148 Val val; 149 } GvnMemAvail; 150 151 typedef struct GvnMemState { 152 GvnMemVersion* roots; 153 u32 nroots; 154 u32 cap; 155 GvnMemAvail* avail; 156 u32 navail; 157 u32 cap_avail; 158 u32 unknown_version; 159 } GvnMemState; 160 161 typedef struct GvnBlockMemState { 162 GvnMemState in; 163 GvnMemState out; 164 u8 out_valid; 165 } GvnBlockMemState; 166 167 typedef struct GvnCtx { 168 Func* f; 169 OptAnalysis* analysis; 170 Val* parent; 171 GvnConst* constants; 172 GvnTable table; 173 GvnMemState mem; 174 GvnBlockMemState* block_mem; 175 u8* local_escaped; 176 int changed; 177 int cfg_changed; 178 } GvnCtx; 179 180 typedef struct DseKey { 181 u8 root_kind; 182 u8 pad0; 183 u16 addr_space; 184 u16 flags; 185 u16 pad1; 186 KitCgTypeId mem_type; 187 u32 size; 188 u32 align; 189 i64 root_id; 190 i64 offset; 191 } DseKey; 192 193 typedef struct DseBitset { 194 u64* words; 195 } DseBitset; 196 197 typedef struct DseBlockState { 198 DseBitset in; 199 DseBitset out; 200 } DseBlockState; 201 202 typedef struct DseCtx { 203 Func* f; 204 GvnCtx gvn; 205 DseKey* keys; 206 u32 nkeys; 207 u32 cap_keys; 208 u32** store_key_by_inst; 209 DseBlockState* block; 210 DseBitset scratch_in; 211 DseBitset scratch_out; 212 u8* local_escaped; 213 u32 words; 214 int changed; 215 } DseCtx; 216 217 typedef struct LicmLoop { 218 u32 header; 219 u32 preheader; 220 u8* body; 221 } LicmLoop; 222 223 typedef struct PressureBlockPlan { 224 u8* move_src; 225 u32* first_before; 226 u32* last_before; 227 u32* next_move; 228 } PressureBlockPlan; 229 230 typedef struct PressurePlan { 231 PressureBlockPlan* blocks; 232 u32 nmoves; 233 } PressurePlan; 234 235 static u32 opt_inst_count(Func* f) { 236 u32 n = 0; 237 for (u32 b = 0; b < f->nblocks; ++b) n += f->blocks[b].ninsts; 238 return n; 239 } 240 241 static int o2_is_terminator(const Inst* in) { 242 switch ((IROp)in->op) { 243 case IR_BR: 244 case IR_CONDBR: 245 case IR_CMP_BRANCH: 246 case IR_SWITCH: 247 case IR_INDIRECT_BRANCH: 248 case IR_RET: 249 case IR_UNREACHABLE: 250 case IR_BREAK_TO: 251 case IR_CONTINUE_TO: 252 return 1; 253 case IR_INTRINSIC: { 254 IRIntrinAux* aux = (IRIntrinAux*)in->extra.aux; 255 return aux && (aux->kind == INTRIN_LONGJMP || aux->kind == INTRIN_TRAP); 256 } 257 default: 258 return 0; 259 } 260 } 261 262 static int o2_cloneable_inst(const Inst* in) { 263 if (in->ndefs) return 0; 264 switch ((IROp)in->op) { 265 case IR_NOP: 266 case IR_LOAD_IMM: 267 case IR_LOAD_CONST: 268 case IR_COPY: 269 case IR_LOAD: 270 case IR_STORE: 271 case IR_ADDR_OF: 272 case IR_BINOP: 273 case IR_UNOP: 274 case IR_CMP: 275 case IR_CONVERT: 276 case IR_BR: 277 case IR_RET: 278 return 1; 279 default: 280 return 0; 281 } 282 } 283 284 static int block_has_phi(Func* f, u32 b) { 285 if (b >= f->nblocks) return 0; 286 Block* bl = &f->blocks[b]; 287 return bl->ninsts && (IROp)bl->insts[0].op == IR_PHI; 288 } 289 290 static int block_defs_are_local(Func* f, u32 b) { 291 Block* bl = &f->blocks[b]; 292 opt_rebuild_def_use(f); 293 for (u32 i = 0; i < bl->ninsts; ++i) { 294 Inst* in = &bl->insts[i]; 295 if (in->def == VAL_NONE) continue; 296 for (u32 u = f->opt_first_use_by_val[in->def]; u != OPT_USE_NONE; 297 u = f->opt_uses[u].next_for_val) { 298 if (f->opt_uses[u].block != b) return 0; 299 } 300 } 301 return 1; 302 } 303 304 static int block_defines_val(const Block* bl, Val v) { 305 for (u32 i = 0; i < bl->ninsts; ++i) { 306 const Inst* in = &bl->insts[i]; 307 if (in->def == v) return 1; 308 for (u32 d = 0; d < in->ndefs; ++d) 309 if (in->defs[d] == v) return 1; 310 } 311 return 0; 312 } 313 314 static int block_external_uses_dominated(Func* f, const OptAnalysis* a, u32 b) { 315 Block* bl = &f->blocks[b]; 316 opt_rebuild_def_use(f); 317 for (u32 i = 0; i < bl->ninsts; ++i) { 318 for (u32 u = 0; u < f->opt_nuses; ++u) { 319 OptUse* use = &f->opt_uses[u]; 320 if (use->block != b || use->inst != i) continue; 321 Val v = use->val; 322 if (block_defines_val(bl, v)) continue; 323 if (v == VAL_NONE || v >= f->nvals) return 0; 324 if (!opt_analysis_dominates(a, f->val_def_block[v], b)) return 0; 325 } 326 } 327 return 1; 328 } 329 330 static int clone_candidate(Func* f, const OptAnalysis* a, u32 block) { 331 if (block >= f->nblocks || block == f->entry) return 0; 332 Block* bl = &f->blocks[block]; 333 if (!a->reachable || !a->reachable[block]) return 0; 334 if (bl->npreds < 2 || bl->npreds > OPT_CLONE_MAX_PREDS) return 0; 335 if (bl->ninsts == 0 || bl->ninsts > OPT_CLONE_MAX_BLOCK_INSTS) return 0; 336 if (bl->nsucc > 1) return 0; 337 if (bl->loop_depth) return 0; 338 if (block_has_phi(f, block)) return 0; 339 if (bl->nsucc == 1 && block_has_phi(f, bl->succ[0])) return 0; 340 for (u32 i = 0; i < bl->ninsts; ++i) { 341 if (!o2_cloneable_inst(&bl->insts[i])) return 0; 342 if (i + 1u != bl->ninsts && o2_is_terminator(&bl->insts[i])) return 0; 343 } 344 for (u32 p = 0; p < bl->npreds; ++p) { 345 u32 pred = bl->preds[p]; 346 if (pred >= f->nblocks) return 0; 347 if (f->blocks[pred].loop_depth) return 0; 348 if (opt_analysis_dominates(a, block, pred)) return 0; 349 } 350 return block_defs_are_local(f, block) && 351 block_external_uses_dominated(f, a, block); 352 } 353 354 static Val map_lookup(const CloneValMap* map, u32 nmap, Val v) { 355 for (u32 i = 0; i < nmap; ++i) 356 if (map[i].old_val == v) return map[i].new_val; 357 return VAL_NONE; 358 } 359 360 static void remap_operand(Func* f, Inst* in, Operand* op, int is_def, 361 void* arg) { 362 (void)in; 363 (void)is_def; 364 CloneValMap* map = (CloneValMap*)arg; 365 u32 nmap = map[0].old_val; 366 if (op->kind != OPK_REG) return; 367 Val repl = map_lookup(map + 1, nmap, (Val)op->v.reg); 368 if (repl == VAL_NONE) return; 369 op->v.reg = (Reg)repl; 370 op->type = f->val_type[repl]; 371 op->cls = f->val_cls[repl]; 372 } 373 374 static IRRetAux* clone_ret_aux(Func* f, const IRRetAux* src) { 375 if (!src) return NULL; 376 IRRetAux* dst = arena_znew(f->arena, IRRetAux); 377 *dst = *src; 378 if (src->val.nparts) { 379 CGABIPart* parts = arena_array(f->arena, CGABIPart, src->val.nparts); 380 memcpy(parts, src->val.parts, sizeof(parts[0]) * src->val.nparts); 381 dst->val.parts = parts; 382 } 383 return dst; 384 } 385 386 static void clone_inst_aux(Func* f, Inst* dst, const Inst* src) { 387 if ((IROp)src->op == IR_RET) { 388 dst->extra.aux = clone_ret_aux(f, (const IRRetAux*)src->extra.aux); 389 } 390 } 391 392 static u32 emit_order_pos(Func* f, u32 block) { 393 for (u32 i = 0; i < f->emit_order_n; ++i) 394 if (f->emit_order[i] == block) return i; 395 return OPT_BLOCK_NONE; 396 } 397 398 static void emit_order_insert_after(Func* f, u32 after, u32 block) { 399 if (emit_order_pos(f, block) != OPT_BLOCK_NONE) return; 400 if (f->emit_order_n == f->emit_order_cap) { 401 u32 ncap = f->emit_order_cap ? f->emit_order_cap * 2u : 8u; 402 u32* order = arena_array(f->arena, u32, ncap); 403 if (f->emit_order) 404 memcpy(order, f->emit_order, sizeof(order[0]) * f->emit_order_n); 405 f->emit_order = order; 406 f->emit_order_cap = ncap; 407 } 408 u32 pos = f->emit_order_n; 409 u32 after_pos = emit_order_pos(f, after); 410 if (after_pos != OPT_BLOCK_NONE) pos = after_pos + 1u; 411 for (u32 i = f->emit_order_n; i > pos; --i) 412 f->emit_order[i] = f->emit_order[i - 1u]; 413 f->emit_order[pos] = block; 414 ++f->emit_order_n; 415 } 416 417 static void replace_succ_ref(Func* f, u32 pred, u32 old_succ, u32 new_succ) { 418 Block* bl = &f->blocks[pred]; 419 for (u32 s = 0; s < bl->nsucc; ++s) 420 if (bl->succ[s] == old_succ) bl->succ[s] = new_succ; 421 if (!bl->ninsts) return; 422 Inst* term = &bl->insts[bl->ninsts - 1u]; 423 if ((IROp)term->op == IR_SWITCH) { 424 IRSwitchAux* aux = (IRSwitchAux*)term->extra.aux; 425 if (!aux) return; 426 for (u32 i = 0; i < aux->ncases; ++i) 427 if (aux->cases[i].block == old_succ) aux->cases[i].block = new_succ; 428 if (aux->default_block == old_succ) aux->default_block = new_succ; 429 } else if ((IROp)term->op == IR_INDIRECT_BRANCH) { 430 IRIndirectAux* aux = (IRIndirectAux*)term->extra.aux; 431 if (!aux) return; 432 for (u32 i = 0; i < aux->ntargets; ++i) 433 if (aux->targets[i] == old_succ) aux->targets[i] = new_succ; 434 } 435 } 436 437 static u32 clone_block_for_pred(Func* f, u32 block, u32 pred) { 438 Block* src = &f->blocks[block]; 439 u32 nb = ir_block_new(f); 440 Block* dst = &f->blocks[nb]; 441 ir_block_set_nsucc(f, nb, src->nsucc); 442 for (u32 s = 0; s < src->nsucc; ++s) dst->succ[s] = src->succ[s]; 443 dst->loop_depth = src->loop_depth; 444 dst->frequency = src->frequency; 445 446 CloneValMap* map = arena_zarray(f->arena, CloneValMap, src->ninsts + 1u); 447 u32 nmap = 0; 448 for (u32 i = 0; i < src->ninsts; ++i) { 449 Val old = src->insts[i].def; 450 if (old == VAL_NONE) continue; 451 map[++nmap].old_val = old; 452 map[nmap].new_val = ir_alloc_val(f, f->val_type[old], f->val_cls[old]); 453 } 454 map[0].old_val = nmap; 455 456 for (u32 i = 0; i < src->ninsts; ++i) { 457 Inst* in = ir_emit(f, nb, (IROp)src->insts[i].op); 458 InstId id = in->id; 459 *in = src->insts[i]; 460 in->id = id; 461 if (in->nopnds) { 462 Operand* opnds = arena_array(f->arena, Operand, in->nopnds); 463 memcpy(opnds, src->insts[i].opnds, sizeof(opnds[0]) * in->nopnds); 464 in->opnds = opnds; 465 } 466 clone_inst_aux(f, in, &src->insts[i]); 467 if (in->def != VAL_NONE) in->def = map_lookup(map + 1, nmap, in->def); 468 opt_walk_inst_operands(f, in, remap_operand, map); 469 if (in->def != VAL_NONE && in->def < f->nvals) { 470 f->val_def_block[in->def] = nb; 471 f->val_def_inst[in->def] = dst->ninsts - 1u; 472 } 473 } 474 475 replace_succ_ref(f, pred, block, nb); 476 emit_order_insert_after(f, pred, nb); 477 return nb; 478 } 479 480 void opt_block_cloning(Func* f) { 481 if (!f || f->opt_rewritten) return; 482 /* This pass remaps OPK_REG defs as Val ids. In the normal O2 pipeline it 483 * must run after opt_build_reg_ssa; standalone unit tests that build Val IR 484 * directly have no pseudo-register table beyond the sentinel. */ 485 if (!f->opt_reg_ssa && f->npregs > 1) return; 486 opt_build_loop_tree(f); 487 OptAnalysis a; 488 memset(&a, 0, sizeof a); 489 opt_analysis_build_dominators(f, &a); 490 491 u32 base_insts = opt_inst_count(f); 492 u32 max_extra = base_insts / 4u + 8u; 493 if (max_extra > OPT_CLONE_ABS_GROWTH_LIMIT) 494 max_extra = OPT_CLONE_ABS_GROWTH_LIMIT; 495 u32 extra = 0; 496 int changed = 0; 497 498 u32 original_blocks = f->nblocks; 499 for (u32 b = 0; b < original_blocks; ++b) { 500 if (!clone_candidate(f, &a, b)) continue; 501 Block* bl = &f->blocks[b]; 502 u32 cost = bl->ninsts; 503 if (cost == 0 || cost * bl->npreds + extra > max_extra) continue; 504 u32 npreds = bl->npreds; 505 u32* preds = arena_array(f->arena, u32, npreds); 506 memcpy(preds, bl->preds, sizeof(preds[0]) * npreds); 507 for (u32 p = 0; p < npreds; ++p) { 508 clone_block_for_pred(f, b, preds[p]); 509 extra += cost; 510 } 511 changed = 1; 512 } 513 514 if (changed) { 515 opt_analysis_invalidate( 516 f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP); 517 opt_build_cfg(f); 518 } 519 opt_rebuild_def_use(f); 520 } 521 522 static int addr_def_inst(Func* f, Val v, Inst** out) { 523 if (v == VAL_NONE || v >= f->nvals) return 0; 524 u32 b = f->val_def_block[v]; 525 u32 i = f->val_def_inst[v]; 526 if (b >= f->nblocks || i >= f->blocks[b].ninsts) return 0; 527 Inst* in = &f->blocks[b].insts[i]; 528 if ((IROp)in->op != IR_ADDR_OF || in->def != v || in->nopnds < 2) return 0; 529 *out = in; 530 return 1; 531 } 532 533 static int val_def_inst(Func* f, Val v, Inst** out) { 534 if (v == VAL_NONE || v >= f->nvals) return 0; 535 u32 b = f->val_def_block[v]; 536 u32 i = f->val_def_inst[v]; 537 if (b >= f->nblocks || i >= f->blocks[b].ninsts) return 0; 538 Inst* in = &f->blocks[b].insts[i]; 539 if (in->def != v) return 0; 540 *out = in; 541 return 1; 542 } 543 544 /* Use classification for the SSA-namespace addr-xform; mirrors the PReg 545 * variant. Returns 0 for escapes, 1 for zero-EA folds (rewrite to 546 * OPK_LOCAL), 2 for EA-shaped folds (leave the OPK_INDIRECT alone so the 547 * EA stays on the load/store). */ 548 static int addr_use_foldable_kind(Func* f, const OptUse* use) { 549 if (!use || use->kind != OPT_USE_INDIRECT_BASE) return 0; 550 if (use->block >= f->nblocks || use->inst >= f->blocks[use->block].ninsts) 551 return 0; 552 Inst* in = &f->blocks[use->block].insts[use->inst]; 553 if ((IROp)in->op != IR_LOAD && (IROp)in->op != IR_STORE) return 0; 554 if (opt_mem_observable(&in->extra.mem)) return 0; 555 if (!use->operand || use->operand->kind != OPK_INDIRECT) return 0; 556 if ((IROp)in->op == IR_LOAD && use->operand_index != 1u) return 0; 557 if ((IROp)in->op == IR_STORE && use->operand_index != 0u) return 0; 558 if (use->operand->v.ind.ofs == 0 && 559 use->operand->v.ind.index == (Reg)REG_NONE) 560 return 1; 561 return 2; 562 } 563 564 static int addr_all_uses_foldable(Func* f, Val v, int* out_has_ea) { 565 u32 nuses = 0; 566 int has_ea = 0; 567 for (u32 u = f->opt_first_use_by_val[v]; u != OPT_USE_NONE; 568 u = f->opt_uses[u].next_for_val) { 569 ++nuses; 570 int k = addr_use_foldable_kind(f, &f->opt_uses[u]); 571 if (!k) return 0; 572 if (k == 2) has_ea = 1; 573 } 574 if (out_has_ea) *out_has_ea = has_ea; 575 return nuses != 0; 576 } 577 578 static void addr_inst_remove(Inst* in) { 579 in->op = IR_NOP; 580 in->def = VAL_NONE; 581 in->ndefs = 0; 582 in->defs = NULL; 583 in->nopnds = 0; 584 in->opnds = NULL; 585 } 586 587 void opt_addr_xform(Func* f) { 588 if (!f || f->opt_rewritten) return; 589 opt_rebuild_def_use(f); 590 int changed = 0; 591 u32 nvals = f->nvals; 592 for (Val v = 1; v < nvals; ++v) { 593 Inst* def = NULL; 594 if (!addr_def_inst(f, v, &def)) continue; 595 Operand lv = def->opnds[1]; 596 if (lv.kind != OPK_LOCAL) continue; 597 int has_ea = 0; 598 if (!addr_all_uses_foldable(f, v, &has_ea)) continue; 599 600 /* Rewrite zero-EA uses to OPK_LOCAL; leave EA-shaped uses as 601 * OPK_INDIRECT(p, ofs, index, log2_scale). When any EA-shaped use 602 * remains, the IR_ADDR_OF def must stay alive to feed its base. */ 603 for (u32 u = f->opt_first_use_by_val[v]; u != OPT_USE_NONE; 604 u = f->opt_uses[u].next_for_val) { 605 OptUse* use = &f->opt_uses[u]; 606 Operand* op = use->operand; 607 if (!op || op->kind != OPK_INDIRECT) continue; 608 if (op->v.ind.ofs != 0 || op->v.ind.index != (Reg)REG_NONE) continue; 609 Inst* mem = &f->blocks[use->block].insts[use->inst]; 610 Operand folded = lv; 611 folded.type = mem->extra.mem.type ? mem->extra.mem.type : lv.type; 612 *op = folded; 613 } 614 if (!has_ea) addr_inst_remove(def); 615 changed = 1; 616 } 617 if (changed) 618 opt_analysis_invalidate( 619 f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP); 620 opt_rebuild_def_use(f); 621 } 622 623 /* gvn's TYPE policy is int-LIKE width (no-PTR); the value arithmetic is the 624 * shared cg/ir_eval core (see src/cg/ir_eval.h). */ 625 static int gvn_int_like_width(Func* f, KitCgTypeId ty, u32* width_out) { 626 u32 width = kit_cg_type_int_width((KitCompiler*)f->c, ty); 627 if (!width || width > 64u) return 0; 628 *width_out = width; 629 return 1; 630 } 631 632 static int gvn_fold_binop(Func* f, BinOp op, KitCgTypeId ty, i64 a, i64 b, 633 i64* out) { 634 u32 width; 635 if (!gvn_int_like_width(f, ty, &width)) return 0; 636 return kit_ir_eval_binop(op, width, a, b, out); 637 } 638 639 static int gvn_fold_unop(Func* f, UnOp op, KitCgTypeId ty, i64 a, i64* out) { 640 u32 width; 641 if (!gvn_int_like_width(f, ty, &width)) return 0; 642 return kit_ir_eval_unop(op, width, a, out); 643 } 644 645 static int gvn_fold_cmp(Func* f, CmpOp op, KitCgTypeId ty, i64 a, i64 b, 646 i64* out) { 647 u32 width; 648 if (!gvn_int_like_width(f, ty, &width)) return 0; 649 return kit_ir_eval_cmp(op, width, a, b, out); 650 } 651 652 static int gvn_fold_convert(Func* f, ConvKind k, KitCgTypeId dst_ty, 653 KitCgTypeId src_ty, i64 src, i64* out) { 654 u32 sw, dw; 655 if (!gvn_int_like_width(f, src_ty, &sw) || 656 !gvn_int_like_width(f, dst_ty, &dw)) 657 return 0; 658 return kit_ir_eval_convert(k, sw, dw, src, out); 659 } 660 661 static Val gvn_find(GvnCtx* ctx, Val v) { 662 if (v == VAL_NONE || v >= ctx->f->nvals) return VAL_NONE; 663 Val p = ctx->parent[v]; 664 if (p == VAL_NONE || p == v) return v; 665 ctx->parent[v] = gvn_find(ctx, p); 666 return ctx->parent[v]; 667 } 668 669 static int gvn_same_shape(Func* f, Val a, Val b) { 670 if (a == VAL_NONE || b == VAL_NONE || a >= f->nvals || b >= f->nvals) 671 return 0; 672 return f->val_type[a] == f->val_type[b] && f->val_cls[a] == f->val_cls[b]; 673 } 674 675 static int gvn_const_for_operand(GvnCtx* ctx, const Operand* op, i64* out) { 676 if (!op) return 0; 677 if (op->kind == OPK_IMM) { 678 *out = op->v.imm; 679 return 1; 680 } 681 if (op->kind != OPK_REG) return 0; 682 Val v = gvn_find(ctx, (Val)op->v.reg); 683 if (v == VAL_NONE || v >= ctx->f->nvals || !ctx->constants[v].valid) return 0; 684 *out = ctx->constants[v].value; 685 return 1; 686 } 687 688 static void gvn_make_load_imm(Func* f, Inst* in, i64 value) { 689 Val dst = in->def; 690 KitCgTypeId ty = 691 dst != VAL_NONE && dst < f->nvals ? f->val_type[dst] : in->type; 692 u8 cls = dst != VAL_NONE && dst < f->nvals ? f->val_cls[dst] : RC_INT; 693 Operand* opnds = in->opnds; 694 if (!opnds) opnds = arena_array(f->arena, Operand, 1); 695 memset(&opnds[0], 0, sizeof opnds[0]); 696 opnds[0].kind = OPK_REG; 697 opnds[0].type = ty; 698 opnds[0].cls = cls; 699 opnds[0].v.reg = (Reg)dst; 700 in->op = IR_LOAD_IMM; 701 in->type = ty; 702 in->opnds = opnds; 703 in->nopnds = 1; 704 in->extra.imm = value; 705 } 706 707 static int gvn_try_fold_inst(GvnCtx* ctx, Inst* in) { 708 i64 a, b, out; 709 switch ((IROp)in->op) { 710 case IR_BINOP: 711 if (in->nopnds < 3) return 0; 712 if (!gvn_const_for_operand(ctx, &in->opnds[1], &a) || 713 !gvn_const_for_operand(ctx, &in->opnds[2], &b)) 714 return 0; 715 if (!gvn_fold_binop(ctx->f, (BinOp)in->extra.imm, in->type, a, b, &out)) 716 return 0; 717 gvn_make_load_imm(ctx->f, in, out); 718 return 1; 719 case IR_UNOP: 720 if (in->nopnds < 2) return 0; 721 if (!gvn_const_for_operand(ctx, &in->opnds[1], &a)) return 0; 722 if (!gvn_fold_unop(ctx->f, (UnOp)in->extra.imm, in->type, a, &out)) 723 return 0; 724 gvn_make_load_imm(ctx->f, in, out); 725 return 1; 726 case IR_CMP: 727 if (in->nopnds < 3) return 0; 728 if (!gvn_const_for_operand(ctx, &in->opnds[1], &a) || 729 !gvn_const_for_operand(ctx, &in->opnds[2], &b)) 730 return 0; 731 if (!gvn_fold_cmp(ctx->f, (CmpOp)in->extra.imm, in->opnds[1].type, a, b, 732 &out)) 733 return 0; 734 gvn_make_load_imm(ctx->f, in, out); 735 return 1; 736 case IR_CONVERT: 737 if (in->nopnds < 2) return 0; 738 if (!gvn_const_for_operand(ctx, &in->opnds[1], &a)) return 0; 739 if (!gvn_fold_convert(ctx->f, (ConvKind)in->extra.imm, in->opnds[0].type, 740 in->opnds[1].type, a, &out)) 741 return 0; 742 gvn_make_load_imm(ctx->f, in, out); 743 return 1; 744 default: 745 return 0; 746 } 747 } 748 749 static u64 gvn_mix_u64(u64 h, u64 v) { 750 h ^= v + 0x9e3779b97f4a7c15ull + (h << 6) + (h >> 2); 751 return h; 752 } 753 754 static u64 gvn_key_hash(const GvnKey* k) { 755 u64 h = 1469598103934665603ull; 756 h = gvn_mix_u64(h, k->op); 757 h = gvn_mix_u64(h, k->nops); 758 h = gvn_mix_u64(h, k->type); 759 h = gvn_mix_u64(h, k->cls); 760 h = gvn_mix_u64(h, (u64)k->tag); 761 h = gvn_mix_u64(h, k->mem.valid); 762 if (k->mem.valid) { 763 h = gvn_mix_u64(h, k->mem.root_kind); 764 h = gvn_mix_u64(h, k->mem.has_addr); 765 h = gvn_mix_u64(h, k->mem.addr_space); 766 h = gvn_mix_u64(h, k->mem.flags); 767 h = gvn_mix_u64(h, k->mem.mem_type); 768 h = gvn_mix_u64(h, k->mem.size); 769 h = gvn_mix_u64(h, k->mem.align); 770 h = gvn_mix_u64(h, (u64)k->mem.root_id); 771 h = gvn_mix_u64(h, (u64)k->mem.offset); 772 h = gvn_mix_u64(h, k->mem.root_version); 773 h = gvn_mix_u64(h, k->mem.unknown_version); 774 } 775 for (u32 i = 0; i < k->nops; ++i) { 776 h = gvn_mix_u64(h, k->ops[i].kind); 777 h = gvn_mix_u64(h, k->ops[i].cls); 778 h = gvn_mix_u64(h, k->ops[i].type); 779 if (k->ops[i].kind == OPK_INDIRECT) { 780 h = gvn_mix_u64(h, k->ops[i].v.ind.base); 781 h = gvn_mix_u64(h, k->ops[i].v.ind.index); 782 h = gvn_mix_u64(h, (u64)(i64)k->ops[i].v.ind.ofs); 783 h = gvn_mix_u64(h, k->ops[i].v.ind.log2_scale); 784 h = gvn_mix_u64(h, k->ops[i].v.ind.index_ext); 785 h = gvn_mix_u64(h, k->ops[i].v.ind.base_type); 786 h = gvn_mix_u64(h, k->ops[i].v.ind.index_type); 787 } else { 788 h = gvn_mix_u64(h, k->ops[i].kind == OPK_REG ? k->ops[i].v.reg 789 : (u64)k->ops[i].v.imm); 790 } 791 } 792 return h; 793 } 794 795 static int gvn_operand_key_equal(const GvnOperandKey* a, 796 const GvnOperandKey* b) { 797 if (a->kind != b->kind || a->cls != b->cls || a->type != b->type) return 0; 798 if (a->kind == OPK_INDIRECT) 799 return a->v.ind.base == b->v.ind.base && a->v.ind.index == b->v.ind.index && 800 a->v.ind.ofs == b->v.ind.ofs && 801 a->v.ind.log2_scale == b->v.ind.log2_scale && 802 a->v.ind.index_ext == b->v.ind.index_ext && 803 a->v.ind.base_type == b->v.ind.base_type && 804 a->v.ind.index_type == b->v.ind.index_type; 805 if (a->kind == OPK_REG) return a->v.reg == b->v.reg; 806 return a->v.imm == b->v.imm; 807 } 808 809 static int gvn_key_equal(const GvnKey* a, const GvnKey* b) { 810 if (a->op != b->op || a->nops != b->nops || a->type != b->type || 811 a->cls != b->cls || a->tag != b->tag) 812 return 0; 813 if (a->mem.valid != b->mem.valid) return 0; 814 if (a->mem.valid && 815 (a->mem.root_kind != b->mem.root_kind || 816 a->mem.has_addr != b->mem.has_addr || 817 a->mem.addr_space != b->mem.addr_space || a->mem.flags != b->mem.flags || 818 a->mem.mem_type != b->mem.mem_type || a->mem.size != b->mem.size || 819 a->mem.align != b->mem.align || a->mem.root_id != b->mem.root_id || 820 a->mem.offset != b->mem.offset || 821 a->mem.root_version != b->mem.root_version || 822 a->mem.unknown_version != b->mem.unknown_version)) 823 return 0; 824 for (u32 i = 0; i < a->nops; ++i) 825 if (!gvn_operand_key_equal(&a->ops[i], &b->ops[i])) return 0; 826 return 1; 827 } 828 829 static void gvn_table_init(GvnTable* t, Func* f) { 830 u32 ninsts = opt_inst_count(f); 831 u32 nbuckets = 16u; 832 while (nbuckets < ninsts * 2u + 1u) nbuckets *= 2u; 833 t->f = f; 834 t->nbuckets = nbuckets; 835 t->buckets = arena_array(f->arena, u32, nbuckets); 836 for (u32 i = 0; i < nbuckets; ++i) t->buckets[i] = GVN_ENTRY_NONE; 837 t->entries = NULL; 838 t->nentries = 0; 839 t->cap = 0; 840 } 841 842 static void gvn_table_add(GvnTable* t, const GvnKey* key, Val v, u32 b, u32 i) { 843 if (t->nentries == t->cap) { 844 u32 ncap = t->cap ? t->cap * 2u : 32u; 845 GvnEntry* entries = arena_array(t->f->arena, GvnEntry, ncap); 846 if (t->entries) 847 memcpy(entries, t->entries, sizeof(entries[0]) * t->nentries); 848 t->entries = entries; 849 t->cap = ncap; 850 } 851 u32 bucket = (u32)(gvn_key_hash(key) & (u64)(t->nbuckets - 1u)); 852 GvnEntry* e = &t->entries[t->nentries]; 853 e->key = *key; 854 e->val = v; 855 e->block = b; 856 e->inst = i; 857 e->next = t->buckets[bucket]; 858 t->buckets[bucket] = t->nentries++; 859 } 860 861 static int gvn_leader_dominates_site(const OptAnalysis* a, u32 leader_b, 862 u32 leader_i, u32 use_b, u32 use_i) { 863 if (leader_b == use_b) return leader_i < use_i; 864 return opt_analysis_dominates(a, leader_b, use_b); 865 } 866 867 static int gvn_leader_dominates_use(GvnCtx* ctx, u32 leader_b, u32 leader_i, 868 const OptUse* use) { 869 if (use->kind == OPT_USE_PHI_INPUT) { 870 Inst* in = &ctx->f->blocks[use->block].insts[use->inst]; 871 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 872 if (!aux || use->phi_pred_index >= aux->npreds) return 0; 873 u32 pred = aux->pred_blocks[use->phi_pred_index]; 874 if (leader_b == pred) return 1; 875 return opt_analysis_dominates(ctx->analysis, leader_b, pred); 876 } 877 return gvn_leader_dominates_site(ctx->analysis, leader_b, leader_i, 878 use->block, use->inst); 879 } 880 881 static int gvn_table_find(GvnCtx* ctx, const GvnKey* key, u32 b, u32 i, 882 Val* out) { 883 GvnTable* t = &ctx->table; 884 u32 bucket = (u32)(gvn_key_hash(key) & (u64)(t->nbuckets - 1u)); 885 for (u32 e = t->buckets[bucket]; e != GVN_ENTRY_NONE; 886 e = t->entries[e].next) { 887 GvnEntry* ent = &t->entries[e]; 888 if (!gvn_key_equal(&ent->key, key)) continue; 889 if (!gvn_leader_dominates_site(ctx->analysis, ent->block, ent->inst, b, i)) 890 continue; 891 *out = ent->val; 892 return 1; 893 } 894 return 0; 895 } 896 897 static int gvn_make_operand_key(GvnCtx* ctx, const Operand* op, 898 GvnOperandKey* out) { 899 memset(out, 0, sizeof *out); 900 if (!op || (op->kind != OPK_REG && op->kind != OPK_IMM)) return 0; 901 out->kind = op->kind; 902 out->cls = op->cls; 903 out->type = op->type; 904 if (op->kind == OPK_REG) { 905 Val v = gvn_find(ctx, (Val)op->v.reg); 906 if (v == VAL_NONE || v >= ctx->f->nvals) return 0; 907 out->v.reg = v; 908 } else { 909 out->v.imm = op->v.imm; 910 } 911 return 1; 912 } 913 914 static int gvn_make_addr_operand_key(GvnCtx* ctx, const Operand* op, 915 GvnOperandKey* out) { 916 memset(out, 0, sizeof *out); 917 if (!op) return 0; 918 out->kind = op->kind; 919 out->cls = op->cls; 920 out->type = op->type; 921 switch ((OpKind)op->kind) { 922 case OPK_REG: { 923 Val v = gvn_find(ctx, (Val)op->v.reg); 924 if (v == VAL_NONE || v >= ctx->f->nvals) return 0; 925 out->v.reg = v; 926 return 1; 927 } 928 case OPK_INDIRECT: { 929 Val base = gvn_find(ctx, (Val)op->v.ind.base); 930 if (base == VAL_NONE || base >= ctx->f->nvals) return 0; 931 out->v.ind.base = base; 932 out->v.ind.base_type = ctx->f->val_type[base]; 933 out->v.ind.index = VAL_NONE; 934 if (op->v.ind.index != REG_NONE) { 935 Val index = gvn_find(ctx, (Val)op->v.ind.index); 936 if (index == VAL_NONE || index >= ctx->f->nvals) return 0; 937 out->v.ind.index = index; 938 out->v.ind.index_type = ctx->f->val_type[index]; 939 out->v.ind.log2_scale = op->v.ind.log2_scale; 940 out->v.ind.index_ext = op->v.ind.index_ext; 941 } 942 out->v.ind.ofs = op->v.ind.ofs; 943 return 1; 944 } 945 case OPK_LOCAL: 946 out->v.imm = (i64)op->v.frame_slot; 947 return 1; 948 case OPK_GLOBAL: 949 out->v.imm = (i64)op->v.global.sym; 950 return 1; 951 default: 952 return 0; 953 } 954 } 955 956 static int gvn_mem_root_from_addr_val(GvnCtx* ctx, Val addr_val, u32 depth, 957 u8* kind_out, i64* id_out, 958 i64* offset_out, int* singleton_out) { 959 Inst* def = NULL; 960 if (!ctx || depth > 4u) return 0; 961 addr_val = gvn_find(ctx, addr_val); 962 if (!val_def_inst(ctx->f, addr_val, &def)) return 0; 963 964 if ((IROp)def->op == IR_ADDR_OF && def->nopnds >= 2) { 965 Operand* lv = &def->opnds[1]; 966 if (lv->kind == OPK_LOCAL) { 967 *kind_out = ALIAS_LOCAL; 968 *id_out = (i64)lv->v.frame_slot; 969 *offset_out = 0; 970 *singleton_out = 1; 971 return 1; 972 } 973 if (lv->kind == OPK_GLOBAL) { 974 *kind_out = ALIAS_GLOBAL; 975 *id_out = (i64)lv->v.global.sym; 976 *offset_out = lv->v.global.addend; 977 *singleton_out = 1; 978 return 1; 979 } 980 return 0; 981 } 982 983 if ((IROp)def->op == IR_COPY && def->nopnds >= 2 && 984 def->opnds[1].kind == OPK_REG) { 985 return gvn_mem_root_from_addr_val(ctx, (Val)def->opnds[1].v.reg, depth + 1u, 986 kind_out, id_out, offset_out, 987 singleton_out); 988 } 989 990 if ((IROp)def->op == IR_BINOP && def->nopnds >= 3 && 991 (BinOp)def->extra.imm == BO_IADD) { 992 i64 c = 0; 993 if (def->opnds[1].kind == OPK_REG && 994 gvn_const_for_operand(ctx, &def->opnds[2], &c) && c == 0) { 995 return gvn_mem_root_from_addr_val(ctx, (Val)def->opnds[1].v.reg, 996 depth + 1u, kind_out, id_out, 997 offset_out, singleton_out); 998 } 999 if (def->opnds[2].kind == OPK_REG && 1000 gvn_const_for_operand(ctx, &def->opnds[1], &c) && c == 0) { 1001 return gvn_mem_root_from_addr_val(ctx, (Val)def->opnds[2].v.reg, 1002 depth + 1u, kind_out, id_out, 1003 offset_out, singleton_out); 1004 } 1005 } 1006 1007 return 0; 1008 } 1009 1010 static int gvn_mem_root_from_access(GvnCtx* ctx, const Operand* addr, 1011 const MemAccess* mem, u8* kind_out, 1012 i64* id_out, i64* offset_out, 1013 int* singleton_out) { 1014 u8 kind = ALIAS_UNKNOWN; 1015 i64 id = 0; 1016 i64 offset = 0; 1017 int singleton = 0; 1018 1019 if (addr) { 1020 switch ((OpKind)addr->kind) { 1021 case OPK_LOCAL: 1022 kind = ALIAS_LOCAL; 1023 id = (i64)addr->v.frame_slot; 1024 singleton = 1; 1025 break; 1026 case OPK_GLOBAL: 1027 kind = ALIAS_GLOBAL; 1028 id = (i64)addr->v.global.sym; 1029 offset = addr->v.global.addend; 1030 singleton = 1; 1031 break; 1032 case OPK_INDIRECT: 1033 offset = addr->v.ind.ofs; 1034 if (addr->v.ind.index != REG_NONE) singleton = 0; 1035 if (ctx) { 1036 Val base = gvn_find(ctx, (Val)addr->v.ind.base); 1037 u8 akind; 1038 i64 aid; 1039 i64 aofs; 1040 int asing; 1041 if (gvn_mem_root_from_addr_val(ctx, base, 0, &akind, &aid, &aofs, 1042 &asing)) { 1043 kind = akind; 1044 id = aid; 1045 offset += aofs; 1046 singleton = asing && addr->v.ind.index == REG_NONE; 1047 } 1048 } 1049 break; 1050 default: 1051 break; 1052 } 1053 } 1054 1055 if (kind == ALIAS_UNKNOWN && mem) { 1056 kind = mem->alias.kind; 1057 switch ((AliasKind)kind) { 1058 case ALIAS_LOCAL: 1059 id = mem->alias.v.local_id; 1060 break; 1061 case ALIAS_GLOBAL: 1062 id = (i64)mem->alias.v.global; 1063 break; 1064 case ALIAS_PARAM: 1065 id = (i64)mem->alias.v.param_idx; 1066 break; 1067 case ALIAS_STRING: 1068 id = (i64)mem->alias.v.string_id; 1069 break; 1070 case ALIAS_HEAP: 1071 id = 0; 1072 break; 1073 default: 1074 kind = ALIAS_UNKNOWN; 1075 id = 0; 1076 break; 1077 } 1078 } 1079 1080 *kind_out = kind; 1081 *id_out = id; 1082 *offset_out = offset; 1083 *singleton_out = singleton; 1084 return kind != ALIAS_UNKNOWN; 1085 } 1086 1087 static GvnMemVersion* gvn_mem_version(GvnCtx* ctx, u8 kind, u16 addr_space, 1088 i64 root_id) { 1089 GvnMemState* s = &ctx->mem; 1090 for (u32 i = 0; i < s->nroots; ++i) { 1091 GvnMemVersion* r = &s->roots[i]; 1092 if (r->root_kind == kind && r->addr_space == addr_space && 1093 r->root_id == root_id) 1094 return r; 1095 } 1096 if (s->nroots == s->cap) { 1097 u32 ncap = s->cap ? s->cap * 2u : 16u; 1098 GvnMemVersion* roots = arena_array(ctx->f->arena, GvnMemVersion, ncap); 1099 if (s->roots) memcpy(roots, s->roots, sizeof(roots[0]) * s->nroots); 1100 s->roots = roots; 1101 s->cap = ncap; 1102 } 1103 GvnMemVersion* r = &s->roots[s->nroots++]; 1104 memset(r, 0, sizeof *r); 1105 r->root_kind = kind; 1106 r->addr_space = addr_space; 1107 r->root_id = root_id; 1108 return r; 1109 } 1110 1111 static void gvn_mem_state_copy(GvnCtx* ctx, GvnMemState* dst, 1112 const GvnMemState* src) { 1113 memset(dst, 0, sizeof *dst); 1114 dst->unknown_version = src->unknown_version; 1115 if (src->nroots) { 1116 dst->roots = arena_array(ctx->f->arena, GvnMemVersion, src->nroots); 1117 memcpy(dst->roots, src->roots, sizeof(dst->roots[0]) * src->nroots); 1118 dst->nroots = src->nroots; 1119 dst->cap = src->nroots; 1120 } 1121 if (src->navail) { 1122 dst->avail = arena_array(ctx->f->arena, GvnMemAvail, src->navail); 1123 memcpy(dst->avail, src->avail, sizeof(dst->avail[0]) * src->navail); 1124 dst->navail = src->navail; 1125 dst->cap_avail = src->navail; 1126 } 1127 } 1128 1129 static int gvn_mem_key_tracks_unknown(GvnCtx* ctx, u8 kind, i64 root_id) { 1130 if (kind == ALIAS_LOCAL && root_id > 0 && 1131 (u32)root_id <= ctx->f->nframe_slots) 1132 return ctx->local_escaped && ctx->local_escaped[root_id]; 1133 return kind != ALIAS_STRING; 1134 } 1135 1136 static int gvn_mem_call_clobbers_root(GvnCtx* ctx, u8 kind, i64 root_id) { 1137 if (kind == ALIAS_LOCAL && root_id > 0 && 1138 (u32)root_id <= ctx->f->nframe_slots) 1139 return !ctx->local_escaped || ctx->local_escaped[root_id]; 1140 return kind != ALIAS_STRING; 1141 } 1142 1143 static void gvn_mem_avail_remove_at(GvnMemState* s, u32 i) { 1144 if (i + 1u < s->navail) 1145 memmove(&s->avail[i], &s->avail[i + 1u], 1146 sizeof(s->avail[0]) * (s->navail - i - 1u)); 1147 --s->navail; 1148 } 1149 1150 static void gvn_mem_avail_add(GvnCtx* ctx, const GvnKey* key, Val val) { 1151 GvnMemState* s = &ctx->mem; 1152 for (u32 i = 0; i < s->navail; ++i) { 1153 if (gvn_key_equal(&s->avail[i].key, key)) { 1154 s->avail[i].val = val; 1155 return; 1156 } 1157 } 1158 if (s->navail == s->cap_avail) { 1159 u32 ncap = s->cap_avail ? s->cap_avail * 2u : 16u; 1160 GvnMemAvail* avail = arena_array(ctx->f->arena, GvnMemAvail, ncap); 1161 if (s->avail) memcpy(avail, s->avail, sizeof(avail[0]) * s->navail); 1162 s->avail = avail; 1163 s->cap_avail = ncap; 1164 } 1165 s->avail[s->navail].key = *key; 1166 s->avail[s->navail].val = val; 1167 ++s->navail; 1168 } 1169 1170 static int gvn_mem_avail_find(GvnCtx* ctx, const GvnKey* key, u32 b, u32 i, 1171 Val* out) { 1172 for (u32 a = 0; a < ctx->mem.navail; ++a) { 1173 Val v = ctx->mem.avail[a].val; 1174 if (!gvn_key_equal(&ctx->mem.avail[a].key, key)) continue; 1175 if (v == VAL_NONE || v >= ctx->f->nvals) continue; 1176 if (!gvn_leader_dominates_site(ctx->analysis, ctx->f->val_def_block[v], 1177 ctx->f->val_def_inst[v], b, i)) 1178 continue; 1179 *out = v; 1180 return 1; 1181 } 1182 return 0; 1183 } 1184 1185 static void gvn_mem_avail_remove_call_clobbered(GvnCtx* ctx) { 1186 GvnMemState* s = &ctx->mem; 1187 for (u32 i = 0; i < s->navail;) { 1188 GvnMemKey* m = &s->avail[i].key.mem; 1189 if (!m->valid || m->root_kind == ALIAS_UNKNOWN || 1190 gvn_mem_call_clobbers_root(ctx, m->root_kind, m->root_id)) 1191 gvn_mem_avail_remove_at(s, i); 1192 else 1193 ++i; 1194 } 1195 } 1196 1197 static void gvn_mem_barrier(GvnCtx* ctx) { 1198 ++ctx->mem.unknown_version; 1199 for (u32 i = 0; i < ctx->mem.nroots; ++i) ++ctx->mem.roots[i].version; 1200 ctx->mem.navail = 0; 1201 } 1202 1203 static void gvn_mem_call_barrier(GvnCtx* ctx) { 1204 ++ctx->mem.unknown_version; 1205 for (u32 i = 0; i < ctx->mem.nroots; ++i) { 1206 GvnMemVersion* r = &ctx->mem.roots[i]; 1207 if (gvn_mem_call_clobbers_root(ctx, r->root_kind, r->root_id)) ++r->version; 1208 } 1209 gvn_mem_avail_remove_call_clobbered(ctx); 1210 } 1211 1212 static void gvn_mem_bump_store(GvnCtx* ctx, u8 kind, u16 addr_space, 1213 i64 root_id) { 1214 if (kind == ALIAS_UNKNOWN) { 1215 gvn_mem_barrier(ctx); 1216 return; 1217 } 1218 ++gvn_mem_version(ctx, kind, addr_space, root_id)->version; 1219 } 1220 1221 static int gvn_make_memory_key(GvnCtx* ctx, const Inst* in, u32 addr_idx, 1222 KitCgTypeId val_ty, u8 val_cls, GvnKey* key) { 1223 const MemAccess* mem; 1224 const Operand* addr; 1225 u8 root_kind; 1226 i64 root_id; 1227 i64 offset; 1228 int singleton; 1229 1230 if (!in || addr_idx >= in->nopnds) return 0; 1231 mem = &in->extra.mem; 1232 addr = &in->opnds[addr_idx]; 1233 if (opt_mem_observable(mem)) return 0; 1234 1235 memset(key, 0, sizeof *key); 1236 key->op = IR_LOAD; 1237 key->type = val_ty; 1238 key->cls = val_cls; 1239 key->mem.valid = 1; 1240 key->mem.addr_space = mem->addr_space; 1241 key->mem.flags = mem->flags; 1242 key->mem.mem_type = mem->type; 1243 key->mem.size = mem->size; 1244 key->mem.align = mem->align; 1245 (void)gvn_mem_root_from_access(ctx, addr, mem, &root_kind, &root_id, &offset, 1246 &singleton); 1247 key->mem.root_kind = root_kind; 1248 key->mem.root_id = root_id; 1249 key->mem.offset = offset; 1250 if (gvn_mem_key_tracks_unknown(ctx, root_kind, root_id)) 1251 key->mem.unknown_version = ctx->mem.unknown_version; 1252 if (root_kind != ALIAS_UNKNOWN) { 1253 key->mem.root_version = 1254 gvn_mem_version(ctx, root_kind, mem->addr_space, root_id)->version; 1255 } 1256 1257 if (!singleton) { 1258 key->mem.has_addr = 1; 1259 key->nops = 1; 1260 if (!gvn_make_addr_operand_key(ctx, addr, &key->ops[0])) return 0; 1261 } 1262 return 1; 1263 } 1264 1265 static int gvn_operand_key_less(const GvnOperandKey* a, 1266 const GvnOperandKey* b) { 1267 if (a->kind != b->kind) return a->kind < b->kind; 1268 if (a->type != b->type) return a->type < b->type; 1269 if (a->cls != b->cls) return a->cls < b->cls; 1270 if (a->kind == OPK_INDIRECT) { 1271 if (a->v.ind.base != b->v.ind.base) return a->v.ind.base < b->v.ind.base; 1272 if (a->v.ind.index != b->v.ind.index) 1273 return a->v.ind.index < b->v.ind.index; 1274 if (a->v.ind.ofs != b->v.ind.ofs) return a->v.ind.ofs < b->v.ind.ofs; 1275 if (a->v.ind.log2_scale != b->v.ind.log2_scale) 1276 return a->v.ind.log2_scale < b->v.ind.log2_scale; 1277 if (a->v.ind.index_ext != b->v.ind.index_ext) 1278 return a->v.ind.index_ext < b->v.ind.index_ext; 1279 if (a->v.ind.base_type != b->v.ind.base_type) 1280 return a->v.ind.base_type < b->v.ind.base_type; 1281 return a->v.ind.index_type < b->v.ind.index_type; 1282 } 1283 if (a->kind == OPK_REG) return a->v.reg < b->v.reg; 1284 return a->v.imm < b->v.imm; 1285 } 1286 1287 static int gvn_make_key(GvnCtx* ctx, const Inst* in, GvnKey* key) { 1288 memset(key, 0, sizeof *key); 1289 if (in->def == VAL_NONE || in->def >= ctx->f->nvals) return 0; 1290 key->op = in->op; 1291 key->type = ctx->f->val_type[in->def]; 1292 key->cls = ctx->f->val_cls[in->def]; 1293 key->tag = in->extra.imm; 1294 1295 switch ((IROp)in->op) { 1296 case IR_LOAD_IMM: 1297 case IR_CONST_I: 1298 key->nops = 0; 1299 key->tag = in->extra.imm; 1300 return 1; 1301 case IR_COPY: 1302 if (in->nopnds < 2) return 0; 1303 key->nops = 1; 1304 return gvn_make_operand_key(ctx, &in->opnds[1], &key->ops[0]); 1305 case IR_UNOP: 1306 case IR_CONVERT: 1307 if (in->nopnds < 2) return 0; 1308 key->nops = 1; 1309 return gvn_make_operand_key(ctx, &in->opnds[1], &key->ops[0]); 1310 case IR_BINOP: 1311 case IR_CMP: 1312 if (in->nopnds < 3) return 0; 1313 key->nops = 2; 1314 if (!gvn_make_operand_key(ctx, &in->opnds[1], &key->ops[0]) || 1315 !gvn_make_operand_key(ctx, &in->opnds[2], &key->ops[1])) 1316 return 0; 1317 if (((IROp)in->op == IR_BINOP && 1318 kit_ir_binop_is_commutative_int((BinOp)in->extra.imm)) || 1319 ((IROp)in->op == IR_CMP && 1320 kit_ir_cmp_is_commutative_int((CmpOp)in->extra.imm))) { 1321 if (gvn_operand_key_less(&key->ops[1], &key->ops[0])) { 1322 GvnOperandKey tmp = key->ops[0]; 1323 key->ops[0] = key->ops[1]; 1324 key->ops[1] = tmp; 1325 } 1326 } 1327 return 1; 1328 default: 1329 return 0; 1330 } 1331 } 1332 1333 static void gvn_replace_one_use(Func* f, const OptUse* use, Val repl) { 1334 Inst* in = &f->blocks[use->block].insts[use->inst]; 1335 switch ((OptUseKind)use->kind) { 1336 case OPT_USE_OPERAND: 1337 use->operand->v.reg = (Reg)repl; 1338 use->operand->type = f->val_type[repl]; 1339 use->operand->cls = f->val_cls[repl]; 1340 break; 1341 case OPT_USE_INDIRECT_BASE: 1342 use->operand->v.ind.base = (Reg)repl; 1343 use->operand->v.ind.base_type = f->val_type[repl]; 1344 break; 1345 case OPT_USE_INDIRECT_INDEX: 1346 use->operand->v.ind.index = (Reg)repl; 1347 use->operand->v.ind.index_type = f->val_type[repl]; 1348 break; 1349 case OPT_USE_PHI_INPUT: { 1350 IRPhiAux* aux = (IRPhiAux*)in->extra.aux; 1351 if (aux && use->phi_pred_index < aux->npreds) 1352 aux->pred_vals[use->phi_pred_index] = repl; 1353 break; 1354 } 1355 default: 1356 break; 1357 } 1358 } 1359 1360 static int gvn_replace_dominated_uses(GvnCtx* ctx, Val old, Val repl, u32 rb, 1361 u32 ri) { 1362 Func* f = ctx->f; 1363 int changed = 0; 1364 if (old == VAL_NONE || old >= f->nvals || repl == VAL_NONE || 1365 repl >= f->nvals || old == repl || !gvn_same_shape(f, old, repl)) 1366 return 0; 1367 for (u32 u = f->opt_first_use_by_val[old]; u != OPT_USE_NONE; 1368 u = f->opt_uses[u].next_for_val) { 1369 OptUse* use = &f->opt_uses[u]; 1370 if (!gvn_leader_dominates_use(ctx, rb, ri, use)) continue; 1371 gvn_replace_one_use(f, use, repl); 1372 changed = 1; 1373 } 1374 if (changed) { 1375 ctx->parent[old] = repl; 1376 ctx->constants[old] = ctx->constants[gvn_find(ctx, repl)]; 1377 } 1378 return changed; 1379 } 1380 1381 static void gvn_note_const(GvnCtx* ctx, Inst* in) { 1382 if (in->def == VAL_NONE || in->def >= ctx->f->nvals) return; 1383 if ((IROp)in->op == IR_LOAD_IMM || (IROp)in->op == IR_CONST_I) { 1384 ctx->constants[in->def].valid = 1; 1385 ctx->constants[in->def].value = in->extra.imm; 1386 } 1387 } 1388 1389 static int gvn_scalar_candidate(const Inst* in) { 1390 if (!in || in->def == VAL_NONE || in->ndefs) return 0; 1391 switch ((IROp)in->op) { 1392 case IR_CONST_I: 1393 case IR_LOAD_IMM: 1394 case IR_COPY: 1395 case IR_BINOP: 1396 case IR_UNOP: 1397 case IR_CMP: 1398 case IR_CONVERT: 1399 return 1; 1400 default: 1401 return 0; 1402 } 1403 } 1404 1405 static int gvn_fold_branch(GvnCtx* ctx, u32 b, Inst* in) { 1406 Block* bl = &ctx->f->blocks[b]; 1407 i64 a, c, taken; 1408 u32 target; 1409 switch ((IROp)in->op) { 1410 case IR_CONDBR: 1411 if (in->nopnds < 1 || bl->nsucc < 2) return 0; 1412 if (in->opnds[0].kind != OPK_REG) return 0; 1413 if (!gvn_const_for_operand(ctx, &in->opnds[0], &a)) return 0; 1414 target = bl->succ[a != 0 ? 0u : 1u]; 1415 break; 1416 case IR_CMP_BRANCH: 1417 if (in->nopnds < 2 || bl->nsucc < 2) return 0; 1418 if (in->opnds[0].kind != OPK_REG && in->opnds[1].kind != OPK_REG) 1419 return 0; 1420 if (!gvn_const_for_operand(ctx, &in->opnds[0], &a) || 1421 !gvn_const_for_operand(ctx, &in->opnds[1], &c)) 1422 return 0; 1423 if (!gvn_fold_cmp(ctx->f, (CmpOp)in->extra.imm, in->opnds[0].type, a, c, 1424 &taken)) 1425 return 0; 1426 target = bl->succ[taken ? 0u : 1u]; 1427 break; 1428 default: 1429 return 0; 1430 } 1431 1432 in->op = IR_BR; 1433 in->def = VAL_NONE; 1434 in->ndefs = 0; 1435 in->defs = NULL; 1436 in->nopnds = 0; 1437 in->opnds = NULL; 1438 bl->succ[0] = target; 1439 bl->nsucc = 1; 1440 return 1; 1441 } 1442 1443 static int gvn_inst_memory_barrier(const Inst* in) { 1444 switch ((IROp)in->op) { 1445 case IR_CALL: 1446 case IR_AGG_COPY: 1447 case IR_AGG_SET: 1448 case IR_BITFIELD_LOAD: 1449 case IR_BITFIELD_STORE: 1450 case IR_VA_START: 1451 case IR_VA_ARG: 1452 case IR_VA_END: 1453 case IR_VA_COPY: 1454 case IR_ATOMIC_LOAD: 1455 case IR_ATOMIC_STORE: 1456 case IR_ATOMIC_RMW: 1457 case IR_ATOMIC_CAS: 1458 case IR_FENCE: 1459 case IR_ASM_BLOCK: 1460 case IR_INTRINSIC: 1461 return 1; 1462 default: 1463 return 0; 1464 } 1465 } 1466 1467 static int gvn_visit_memory_inst(GvnCtx* ctx, u32 b, u32 i, Inst* in) { 1468 if ((IROp)in->op == IR_LOAD) { 1469 if (opt_mem_observable(&in->extra.mem)) { 1470 gvn_mem_barrier(ctx); 1471 return 1; 1472 } 1473 if (in->def == VAL_NONE || in->def >= ctx->f->nvals) return 1; 1474 GvnKey key; 1475 if (!gvn_make_memory_key(ctx, in, 1u, ctx->f->val_type[in->def], 1476 ctx->f->val_cls[in->def], &key)) 1477 return 1; 1478 Val leader = VAL_NONE; 1479 if (gvn_mem_avail_find(ctx, &key, b, i, &leader)) { 1480 if (gvn_replace_dominated_uses(ctx, in->def, leader, 1481 ctx->f->val_def_block[leader], 1482 ctx->f->val_def_inst[leader])) 1483 ctx->changed = 1; 1484 return 1; 1485 } 1486 gvn_mem_avail_add(ctx, &key, in->def); 1487 return 1; 1488 } 1489 1490 if ((IROp)in->op == IR_STORE) { 1491 u8 root_kind; 1492 i64 root_id; 1493 i64 offset; 1494 int singleton; 1495 Val src; 1496 if (opt_mem_observable(&in->extra.mem)) { 1497 gvn_mem_barrier(ctx); 1498 return 1; 1499 } 1500 if (in->nopnds < 2) { 1501 gvn_mem_barrier(ctx); 1502 return 1; 1503 } 1504 (void)gvn_mem_root_from_access(ctx, &in->opnds[0], &in->extra.mem, 1505 &root_kind, &root_id, &offset, &singleton); 1506 (void)offset; 1507 (void)singleton; 1508 gvn_mem_bump_store(ctx, root_kind, in->extra.mem.addr_space, root_id); 1509 if (in->opnds[1].kind != OPK_REG) return 1; 1510 src = gvn_find(ctx, (Val)in->opnds[1].v.reg); 1511 if (src == VAL_NONE || src >= ctx->f->nvals) return 1; 1512 GvnKey key; 1513 if (!gvn_make_memory_key(ctx, in, 0u, ctx->f->val_type[src], 1514 ctx->f->val_cls[src], &key)) 1515 return 1; 1516 gvn_mem_avail_add(ctx, &key, src); 1517 return 1; 1518 } 1519 1520 if ((IROp)in->op == IR_CALL) { 1521 gvn_mem_call_barrier(ctx); 1522 return 1; 1523 } 1524 1525 if (gvn_inst_memory_barrier(in)) { 1526 gvn_mem_barrier(ctx); 1527 return 1; 1528 } 1529 return 0; 1530 } 1531 1532 static void gvn_visit_inst(GvnCtx* ctx, u32 b, u32 i) { 1533 Inst* in = &ctx->f->blocks[b].insts[i]; 1534 if (gvn_fold_branch(ctx, b, in)) { 1535 ctx->changed = 1; 1536 ctx->cfg_changed = 1; 1537 return; 1538 } 1539 if (gvn_visit_memory_inst(ctx, b, i, in)) return; 1540 if (!gvn_scalar_candidate(in)) return; 1541 1542 if (gvn_try_fold_inst(ctx, in)) ctx->changed = 1; 1543 gvn_note_const(ctx, in); 1544 1545 GvnKey key; 1546 if (!gvn_make_key(ctx, in, &key)) return; 1547 1548 Val leader = VAL_NONE; 1549 if (gvn_table_find(ctx, &key, b, i, &leader)) { 1550 if (gvn_replace_dominated_uses(ctx, in->def, leader, 1551 ctx->f->val_def_block[leader], 1552 ctx->f->val_def_inst[leader])) 1553 ctx->changed = 1; 1554 return; 1555 } 1556 gvn_table_add(&ctx->table, &key, in->def, b, i); 1557 } 1558 1559 static int gvn_raw_const_zero(Func* f, Val v) { 1560 Inst* def = NULL; 1561 return val_def_inst(f, v, &def) && def && (IROp)def->op == IR_LOAD_IMM && 1562 def->extra.imm == 0; 1563 } 1564 1565 static int gvn_raw_operand_zero(Func* f, const Operand* op) { 1566 if (!op) return 0; 1567 if (op->kind == OPK_IMM) return op->v.imm == 0; 1568 if (op->kind == OPK_REG) return gvn_raw_const_zero(f, (Val)op->v.reg); 1569 return 0; 1570 } 1571 1572 static int gvn_raw_local_addr_root(Func* f, Val v, u32 depth, FrameSlot* out) { 1573 Inst* def = NULL; 1574 if (!f || depth > 4u || v == VAL_NONE) return 0; 1575 if (!val_def_inst(f, v, &def) || !def) return 0; 1576 if ((IROp)def->op == IR_ADDR_OF && def->nopnds >= 2 && 1577 def->opnds[1].kind == OPK_LOCAL) { 1578 *out = def->opnds[1].v.frame_slot; 1579 return 1; 1580 } 1581 if ((IROp)def->op == IR_COPY && def->nopnds >= 2 && 1582 def->opnds[1].kind == OPK_REG) 1583 return gvn_raw_local_addr_root(f, (Val)def->opnds[1].v.reg, depth + 1u, 1584 out); 1585 if ((IROp)def->op == IR_BINOP && def->nopnds >= 3) { 1586 if ((BinOp)def->extra.imm == BO_IADD) { 1587 if (def->opnds[1].kind == OPK_REG && 1588 gvn_raw_operand_zero(f, &def->opnds[2])) 1589 return gvn_raw_local_addr_root(f, (Val)def->opnds[1].v.reg, depth + 1u, 1590 out); 1591 if (def->opnds[2].kind == OPK_REG && 1592 gvn_raw_operand_zero(f, &def->opnds[1])) 1593 return gvn_raw_local_addr_root(f, (Val)def->opnds[2].v.reg, depth + 1u, 1594 out); 1595 } 1596 if ((BinOp)def->extra.imm == BO_ISUB && def->opnds[1].kind == OPK_REG && 1597 gvn_raw_operand_zero(f, &def->opnds[2])) 1598 return gvn_raw_local_addr_root(f, (Val)def->opnds[1].v.reg, depth + 1u, 1599 out); 1600 } 1601 return 0; 1602 } 1603 1604 static void gvn_mark_escaped_operand(GvnCtx* ctx, const Operand* op) { 1605 FrameSlot fs = FRAME_SLOT_NONE; 1606 if (!op) return; 1607 if (op->kind == OPK_LOCAL) { 1608 fs = op->v.frame_slot; 1609 if (fs > 0 && (u32)fs <= ctx->f->nframe_slots) ctx->local_escaped[fs] = 1; 1610 } else if (op->kind == OPK_REG) { 1611 if (gvn_raw_local_addr_root(ctx->f, (Val)op->v.reg, 0, &fs) && fs > 0 && 1612 (u32)fs <= ctx->f->nframe_slots) 1613 ctx->local_escaped[fs] = 1; 1614 } else if (op->kind == OPK_INDIRECT) { 1615 if (gvn_raw_local_addr_root(ctx->f, (Val)op->v.ind.base, 0, &fs) && 1616 fs > 0 && (u32)fs <= ctx->f->nframe_slots) 1617 ctx->local_escaped[fs] = 1; 1618 } 1619 } 1620 1621 static void gvn_mark_escaped_abivalue(GvnCtx* ctx, const CGABIValue* v) { 1622 if (!v) return; 1623 gvn_mark_escaped_operand(ctx, &v->storage); 1624 for (u32 i = 0; i < v->nparts; ++i) 1625 gvn_mark_escaped_operand(ctx, &v->parts[i].op); 1626 } 1627 1628 static void gvn_collect_local_escapes(GvnCtx* ctx) { 1629 Func* f = ctx->f; 1630 for (u32 b = 0; b < f->nblocks; ++b) { 1631 Block* bl = &f->blocks[b]; 1632 for (u32 i = 0; i < bl->ninsts; ++i) { 1633 Inst* in = &bl->insts[i]; 1634 switch ((IROp)in->op) { 1635 case IR_LOAD: 1636 case IR_ADDR_OF: 1637 case IR_COPY: 1638 break; 1639 case IR_STORE: 1640 if (in->nopnds >= 2) gvn_mark_escaped_operand(ctx, &in->opnds[1]); 1641 break; 1642 case IR_BINOP: 1643 if (in->nopnds >= 3 && (BinOp)in->extra.imm == BO_IADD && 1644 (gvn_raw_operand_zero(f, &in->opnds[1]) || 1645 gvn_raw_operand_zero(f, &in->opnds[2]))) 1646 break; 1647 if (in->nopnds >= 3 && (BinOp)in->extra.imm == BO_ISUB && 1648 gvn_raw_operand_zero(f, &in->opnds[2])) 1649 break; 1650 for (u32 o = 1; o < in->nopnds; ++o) 1651 gvn_mark_escaped_operand(ctx, &in->opnds[o]); 1652 break; 1653 case IR_CALL: { 1654 IRCallAux* aux = (IRCallAux*)in->extra.aux; 1655 if (!aux) break; 1656 if (aux->use_plan_replay) { 1657 gvn_mark_escaped_operand(ctx, &aux->plan.callee); 1658 for (u32 a = 0; a < aux->plan.nargs; ++a) 1659 gvn_mark_escaped_operand(ctx, &aux->plan.args[a].src); 1660 for (u32 r = 0; r < aux->plan.nrets; ++r) 1661 gvn_mark_escaped_operand(ctx, &aux->plan.rets[r].dst); 1662 } else { 1663 gvn_mark_escaped_operand(ctx, &aux->desc.callee); 1664 for (u32 a = 0; a < aux->desc.nargs; ++a) 1665 gvn_mark_escaped_abivalue(ctx, &aux->desc.args[a]); 1666 gvn_mark_escaped_abivalue(ctx, &aux->desc.ret); 1667 } 1668 break; 1669 } 1670 case IR_RET: { 1671 IRRetAux* aux = (IRRetAux*)in->extra.aux; 1672 if (aux && aux->present) gvn_mark_escaped_abivalue(ctx, &aux->val); 1673 break; 1674 } 1675 default: 1676 if (gvn_inst_memory_barrier(in)) 1677 for (u32 o = 0; o < in->nopnds; ++o) 1678 gvn_mark_escaped_operand(ctx, &in->opnds[o]); 1679 break; 1680 } 1681 } 1682 } 1683 } 1684 1685 static int gvn_mem_state_has_avail(const GvnMemState* s, const GvnKey* key, 1686 Val val) { 1687 for (u32 i = 0; i < s->navail; ++i) 1688 if (s->avail[i].val == val && gvn_key_equal(&s->avail[i].key, key)) 1689 return 1; 1690 return 0; 1691 } 1692 1693 static void gvn_mem_merge_block_in(GvnCtx* ctx, u32 b) { 1694 Func* f = ctx->f; 1695 Block* bl = &f->blocks[b]; 1696 GvnBlockMemState* bs = &ctx->block_mem[b]; 1697 memset(&bs->in, 0, sizeof bs->in); 1698 if (!bl->npreds) return; 1699 const GvnMemState* first = NULL; 1700 for (u32 p = 0; p < bl->npreds; ++p) { 1701 u32 pred = bl->preds[p]; 1702 if (pred >= f->nblocks || !ctx->analysis->reachable[pred]) continue; 1703 if (!ctx->block_mem[pred].out_valid) return; 1704 if (!first) first = &ctx->block_mem[pred].out; 1705 } 1706 if (!first) return; 1707 gvn_mem_state_copy(ctx, &bs->in, first); 1708 for (u32 i = 0; i < bs->in.navail;) { 1709 GvnMemAvail* a = &bs->in.avail[i]; 1710 int keep = 1; 1711 for (u32 p = 0; p < bl->npreds; ++p) { 1712 u32 pred = bl->preds[p]; 1713 if (pred >= f->nblocks || !ctx->analysis->reachable[pred]) continue; 1714 if (!gvn_mem_state_has_avail(&ctx->block_mem[pred].out, &a->key, 1715 a->val)) { 1716 keep = 0; 1717 break; 1718 } 1719 } 1720 if (keep) 1721 ++i; 1722 else 1723 gvn_mem_avail_remove_at(&bs->in, i); 1724 } 1725 } 1726 1727 static void gvn_realign_phi_preds(Func* f) { 1728 for (u32 b = 0; b < f->nblocks; ++b) { 1729 Block* bl = &f->blocks[b]; 1730 for (u32 i = 0; i < bl->ninsts; ++i) { 1731 Inst* phi = &bl->insts[i]; 1732 if ((IROp)phi->op != IR_PHI) break; 1733 IRPhiAux* aux = (IRPhiAux*)phi->extra.aux; 1734 if (!aux) continue; 1735 u32 old_n = aux->npreds; 1736 u32* old_blocks = aux->pred_blocks; 1737 Val* old_vals = aux->pred_vals; 1738 u32* pred_blocks = 1739 bl->npreds ? arena_array(f->arena, u32, bl->npreds) : NULL; 1740 Val* pred_vals = 1741 bl->npreds ? arena_zarray(f->arena, Val, bl->npreds) : NULL; 1742 for (u32 p = 0; p < bl->npreds; ++p) { 1743 pred_blocks[p] = bl->preds[p]; 1744 pred_vals[p] = phi->def; 1745 for (u32 old = 0; old < old_n; ++old) { 1746 if (old_blocks && old_blocks[old] == bl->preds[p]) { 1747 pred_vals[p] = old_vals ? old_vals[old] : VAL_NONE; 1748 break; 1749 } 1750 } 1751 } 1752 aux->npreds = bl->npreds; 1753 aux->pred_blocks = pred_blocks; 1754 aux->pred_vals = pred_vals; 1755 } 1756 } 1757 } 1758 1759 void opt_gvn(Func* f) { 1760 if (!f || f->opt_rewritten) return; 1761 if (!f->opt_reg_ssa && f->npregs > 1) { 1762 opt_rebuild_def_use(f); 1763 return; 1764 } 1765 1766 opt_rebuild_def_use(f); 1767 OptAnalysis a; 1768 memset(&a, 0, sizeof a); 1769 opt_analysis_build_dominators(f, &a); 1770 1771 GvnCtx ctx; 1772 memset(&ctx, 0, sizeof ctx); 1773 ctx.f = f; 1774 ctx.analysis = &a; 1775 ctx.parent = arena_array(f->arena, Val, f->nvals ? f->nvals : 1u); 1776 ctx.constants = arena_zarray(f->arena, GvnConst, f->nvals ? f->nvals : 1u); 1777 ctx.block_mem = 1778 arena_zarray(f->arena, GvnBlockMemState, f->nblocks ? f->nblocks : 1u); 1779 ctx.local_escaped = 1780 arena_zarray(f->arena, u8, f->nframe_slots ? f->nframe_slots + 1u : 1u); 1781 for (Val v = 0; v < f->nvals; ++v) ctx.parent[v] = v; 1782 gvn_table_init(&ctx.table, f); 1783 gvn_collect_local_escapes(&ctx); 1784 1785 for (u32 ri = 0; ri < a.nrpo; ++ri) { 1786 u32 b = a.rpo[ri]; 1787 if (b >= f->nblocks || !a.reachable[b]) continue; 1788 gvn_mem_merge_block_in(&ctx, b); 1789 gvn_mem_state_copy(&ctx, &ctx.mem, &ctx.block_mem[b].in); 1790 for (u32 i = 0; i < f->blocks[b].ninsts; ++i) gvn_visit_inst(&ctx, b, i); 1791 gvn_mem_state_copy(&ctx, &ctx.block_mem[b].out, &ctx.mem); 1792 ctx.block_mem[b].out_valid = 1; 1793 } 1794 1795 if (ctx.cfg_changed) { 1796 opt_analysis_invalidate( 1797 f, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP); 1798 opt_build_cfg(f); 1799 gvn_realign_phi_preds(f); 1800 } else if (ctx.changed) { 1801 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 1802 } 1803 opt_rebuild_def_use(f); 1804 } 1805 1806 static int dse_key_equal(const DseKey* a, const DseKey* b) { 1807 return a->root_kind == b->root_kind && a->addr_space == b->addr_space && 1808 a->flags == b->flags && a->mem_type == b->mem_type && 1809 a->size == b->size && a->align == b->align && 1810 a->root_id == b->root_id && a->offset == b->offset; 1811 } 1812 1813 static int dse_key_same_root(const DseKey* a, const DseKey* b) { 1814 return a->root_kind == b->root_kind && a->addr_space == b->addr_space && 1815 a->root_id == b->root_id; 1816 } 1817 1818 static int dse_ranges_overlap(const DseKey* a, const DseKey* b) { 1819 i64 ae = a->offset + (i64)a->size; 1820 i64 be = b->offset + (i64)b->size; 1821 return a->offset < be && b->offset < ae; 1822 } 1823 1824 static int dse_range_covers(const DseKey* cover, const DseKey* covered) { 1825 i64 ce = cover->offset + (i64)cover->size; 1826 i64 de = covered->offset + (i64)covered->size; 1827 return cover->offset <= covered->offset && ce >= de; 1828 } 1829 1830 static int dse_root_call_clobbered(DseCtx* ctx, const DseKey* key) { 1831 if (key->root_kind == ALIAS_LOCAL && key->root_id > 0 && 1832 (u32)key->root_id <= ctx->f->nframe_slots) 1833 return ctx->local_escaped && ctx->local_escaped[key->root_id]; 1834 return key->root_kind != ALIAS_STRING; 1835 } 1836 1837 static int dse_root_observable_at_exit(DseCtx* ctx, const DseKey* key) { 1838 if (key->root_kind == ALIAS_LOCAL && key->root_id > 0 && 1839 (u32)key->root_id <= ctx->f->nframe_slots) 1840 return ctx->local_escaped && ctx->local_escaped[key->root_id]; 1841 return key->root_kind != ALIAS_UNKNOWN; 1842 } 1843 1844 static int dse_make_key(DseCtx* ctx, const Inst* in, u32 addr_idx, 1845 DseKey* out) { 1846 u8 root_kind; 1847 i64 root_id; 1848 i64 offset; 1849 int singleton; 1850 1851 if (!ctx || !in || addr_idx >= in->nopnds || 1852 opt_mem_observable(&in->extra.mem)) 1853 return 0; 1854 if (in->extra.mem.size == 0) return 0; 1855 if (!gvn_mem_root_from_access(&ctx->gvn, &in->opnds[addr_idx], &in->extra.mem, 1856 &root_kind, &root_id, &offset, &singleton)) 1857 return 0; 1858 if (!singleton || root_kind == ALIAS_UNKNOWN) return 0; 1859 1860 memset(out, 0, sizeof *out); 1861 out->root_kind = root_kind; 1862 out->addr_space = in->extra.mem.addr_space; 1863 out->flags = in->extra.mem.flags; 1864 out->mem_type = in->extra.mem.type; 1865 out->size = in->extra.mem.size; 1866 out->align = in->extra.mem.align; 1867 out->root_id = root_id; 1868 out->offset = offset; 1869 return 1; 1870 } 1871 1872 static u32 dse_key_intern(DseCtx* ctx, const DseKey* key) { 1873 for (u32 i = 0; i < ctx->nkeys; ++i) 1874 if (dse_key_equal(&ctx->keys[i], key)) return i; 1875 if (ctx->nkeys == ctx->cap_keys) { 1876 u32 ncap = ctx->cap_keys ? ctx->cap_keys * 2u : 16u; 1877 DseKey* keys = arena_array(ctx->f->arena, DseKey, ncap); 1878 if (ctx->keys) memcpy(keys, ctx->keys, sizeof(keys[0]) * ctx->nkeys); 1879 ctx->keys = keys; 1880 ctx->cap_keys = ncap; 1881 } 1882 ctx->keys[ctx->nkeys] = *key; 1883 return ctx->nkeys++; 1884 } 1885 1886 static void dse_bitset_clear(DseCtx* ctx, DseBitset* bs) { 1887 memset(bs->words, 0, sizeof(bs->words[0]) * ctx->words); 1888 } 1889 1890 static int dse_bitset_copy(DseCtx* ctx, DseBitset* dst, const DseBitset* src) { 1891 int changed = 1892 memcmp(dst->words, src->words, sizeof(dst->words[0]) * ctx->words) != 0; 1893 if (changed) 1894 memcpy(dst->words, src->words, sizeof(dst->words[0]) * ctx->words); 1895 return changed; 1896 } 1897 1898 static void dse_bitset_or(DseCtx* ctx, DseBitset* dst, const DseBitset* src) { 1899 for (u32 w = 0; w < ctx->words; ++w) dst->words[w] |= src->words[w]; 1900 } 1901 1902 static int dse_bitset_test(const DseBitset* bs, u32 bit) { 1903 return (bs->words[bit / 64u] & (1ull << (bit % 64u))) != 0; 1904 } 1905 1906 static void dse_bitset_set(DseBitset* bs, u32 bit) { 1907 bs->words[bit / 64u] |= 1ull << (bit % 64u); 1908 } 1909 1910 static void dse_bitset_reset(DseBitset* bs, u32 bit) { 1911 bs->words[bit / 64u] &= ~(1ull << (bit % 64u)); 1912 } 1913 1914 static int dse_live_overlaps(DseCtx* ctx, const DseBitset* live, 1915 const DseKey* key) { 1916 for (u32 i = 0; i < ctx->nkeys; ++i) { 1917 if (!dse_bitset_test(live, i)) continue; 1918 if (dse_key_same_root(&ctx->keys[i], key) && 1919 dse_ranges_overlap(&ctx->keys[i], key)) 1920 return 1; 1921 } 1922 return 0; 1923 } 1924 1925 static void dse_live_mark_overlaps(DseCtx* ctx, DseBitset* live, 1926 const DseKey* key) { 1927 for (u32 i = 0; i < ctx->nkeys; ++i) { 1928 if (dse_key_same_root(&ctx->keys[i], key) && 1929 dse_ranges_overlap(&ctx->keys[i], key)) 1930 dse_bitset_set(live, i); 1931 } 1932 } 1933 1934 static void dse_live_clear_covered(DseCtx* ctx, DseBitset* live, 1935 const DseKey* key) { 1936 for (u32 i = 0; i < ctx->nkeys; ++i) { 1937 if (dse_key_same_root(&ctx->keys[i], key) && 1938 dse_range_covers(key, &ctx->keys[i])) 1939 dse_bitset_reset(live, i); 1940 } 1941 } 1942 1943 static void dse_live_mark_all(DseCtx* ctx, DseBitset* live) { 1944 for (u32 i = 0; i < ctx->nkeys; ++i) dse_bitset_set(live, i); 1945 } 1946 1947 static void dse_live_mark_call_clobbered(DseCtx* ctx, DseBitset* live) { 1948 for (u32 i = 0; i < ctx->nkeys; ++i) 1949 if (dse_root_call_clobbered(ctx, &ctx->keys[i])) dse_bitset_set(live, i); 1950 } 1951 1952 static void dse_live_mark_exit_observable(DseCtx* ctx, DseBitset* live) { 1953 for (u32 i = 0; i < ctx->nkeys; ++i) 1954 if (dse_root_observable_at_exit(ctx, &ctx->keys[i])) 1955 dse_bitset_set(live, i); 1956 } 1957 1958 static int dse_store_site_key(DseCtx* ctx, u32 block, u32 inst, u32* out) { 1959 if (!ctx->store_key_by_inst || block >= ctx->f->nblocks || 1960 inst >= ctx->f->blocks[block].ninsts || !ctx->store_key_by_inst[block]) 1961 return 0; 1962 *out = ctx->store_key_by_inst[block][inst]; 1963 if (*out != DSE_KEY_NONE) return 1; 1964 return 0; 1965 } 1966 1967 static int dse_inst_full_barrier(const Inst* in) { 1968 return gvn_inst_memory_barrier(in); 1969 } 1970 1971 static void dse_transfer_inst(DseCtx* ctx, DseBitset* live, u32 block, u32 inst, 1972 int mark_dead) { 1973 Inst* in = &ctx->f->blocks[block].insts[inst]; 1974 DseKey key; 1975 u32 key_id; 1976 1977 switch ((IROp)in->op) { 1978 case IR_LOAD: 1979 if (opt_mem_observable(&in->extra.mem)) { 1980 dse_live_mark_all(ctx, live); 1981 } else if (dse_make_key(ctx, in, 1u, &key)) { 1982 dse_live_mark_overlaps(ctx, live, &key); 1983 } else { 1984 dse_live_mark_all(ctx, live); 1985 } 1986 break; 1987 case IR_STORE: 1988 if (!dse_store_site_key(ctx, block, inst, &key_id)) { 1989 dse_live_mark_all(ctx, live); 1990 break; 1991 } 1992 key = ctx->keys[key_id]; 1993 if (mark_dead && !dse_live_overlaps(ctx, live, &key)) { 1994 in->op = IR_NOP; 1995 in->nopnds = 0; 1996 in->opnds = NULL; 1997 ctx->changed = 1; 1998 } 1999 dse_live_clear_covered(ctx, live, &key); 2000 break; 2001 case IR_CALL: 2002 dse_live_mark_call_clobbered(ctx, live); 2003 break; 2004 default: 2005 if (dse_inst_full_barrier(in)) dse_live_mark_all(ctx, live); 2006 break; 2007 } 2008 } 2009 2010 static void dse_collect_constants(GvnCtx* ctx) { 2011 for (u32 b = 0; b < ctx->f->nblocks; ++b) { 2012 Block* bl = &ctx->f->blocks[b]; 2013 for (u32 i = 0; i < bl->ninsts; ++i) gvn_note_const(ctx, &bl->insts[i]); 2014 } 2015 } 2016 2017 static void dse_collect_stores(DseCtx* ctx) { 2018 Func* f = ctx->f; 2019 ctx->store_key_by_inst = 2020 arena_zarray(f->arena, u32*, f->nblocks ? f->nblocks : 1u); 2021 for (u32 b = 0; b < f->nblocks; ++b) { 2022 Block* bl = &f->blocks[b]; 2023 ctx->store_key_by_inst[b] = 2024 arena_array(f->arena, u32, bl->ninsts ? bl->ninsts : 1u); 2025 for (u32 i = 0; i < bl->ninsts; ++i) 2026 ctx->store_key_by_inst[b][i] = DSE_KEY_NONE; 2027 for (u32 i = 0; i < bl->ninsts; ++i) { 2028 Inst* in = &bl->insts[i]; 2029 DseKey key; 2030 if ((IROp)in->op != IR_STORE) continue; 2031 if (!dse_make_key(ctx, in, 0u, &key)) continue; 2032 ctx->store_key_by_inst[b][i] = dse_key_intern(ctx, &key); 2033 } 2034 } 2035 } 2036 2037 static DseBitset dse_bitset_new(DseCtx* ctx) { 2038 DseBitset bs; 2039 bs.words = arena_zarray(ctx->f->arena, u64, ctx->words ? ctx->words : 1u); 2040 return bs; 2041 } 2042 2043 static void dse_init_block_sets(DseCtx* ctx) { 2044 Func* f = ctx->f; 2045 ctx->words = (ctx->nkeys + 63u) / 64u; 2046 if (!ctx->words) ctx->words = 1u; 2047 ctx->block = 2048 arena_zarray(f->arena, DseBlockState, f->nblocks ? f->nblocks : 1u); 2049 for (u32 b = 0; b < f->nblocks; ++b) { 2050 ctx->block[b].in = dse_bitset_new(ctx); 2051 ctx->block[b].out = dse_bitset_new(ctx); 2052 } 2053 ctx->scratch_in = dse_bitset_new(ctx); 2054 ctx->scratch_out = dse_bitset_new(ctx); 2055 } 2056 2057 static void dse_compute_block_out(DseCtx* ctx, u32 b, DseBitset* out) { 2058 Func* f = ctx->f; 2059 Block* bl = &f->blocks[b]; 2060 dse_bitset_clear(ctx, out); 2061 if (!bl->nsucc) { 2062 dse_live_mark_exit_observable(ctx, out); 2063 return; 2064 } 2065 for (u32 s = 0; s < bl->nsucc; ++s) { 2066 u32 succ = bl->succ[s]; 2067 if (succ < f->nblocks) dse_bitset_or(ctx, out, &ctx->block[succ].in); 2068 } 2069 } 2070 2071 static void dse_transfer_block(DseCtx* ctx, u32 b, const DseBitset* out, 2072 DseBitset* in, int mark_dead) { 2073 Block* bl = &ctx->f->blocks[b]; 2074 dse_bitset_copy(ctx, in, out); 2075 for (u32 ri = bl->ninsts; ri > 0; --ri) 2076 dse_transfer_inst(ctx, in, b, ri - 1u, mark_dead); 2077 } 2078 2079 static void dse_refresh_def_locations(Func* f) { 2080 for (u32 b = 0; b < f->nblocks; ++b) { 2081 Block* bl = &f->blocks[b]; 2082 for (u32 i = 0; i < bl->ninsts; ++i) { 2083 Inst* in = &bl->insts[i]; 2084 if (in->def != VAL_NONE && in->def < f->nvals) { 2085 f->val_def_block[in->def] = b; 2086 f->val_def_inst[in->def] = i; 2087 } 2088 for (u32 d = 0; d < in->ndefs; ++d) { 2089 Val v = in->defs[d]; 2090 if (v != VAL_NONE && v < f->nvals) { 2091 f->val_def_block[v] = b; 2092 f->val_def_inst[v] = i; 2093 } 2094 } 2095 } 2096 } 2097 } 2098 2099 static void dse_compact_nops(Func* f) { 2100 for (u32 b = 0; b < f->nblocks; ++b) { 2101 Block* bl = &f->blocks[b]; 2102 u32 w = 0; 2103 for (u32 i = 0; i < bl->ninsts; ++i) { 2104 if ((IROp)bl->insts[i].op == IR_NOP) continue; 2105 bl->insts[w++] = bl->insts[i]; 2106 } 2107 bl->ninsts = w; 2108 } 2109 dse_refresh_def_locations(f); 2110 } 2111 2112 void opt_dse(Func* f) { 2113 if (!f || f->opt_rewritten) return; 2114 if (!f->opt_reg_ssa && f->npregs > 1) { 2115 opt_rebuild_def_use(f); 2116 return; 2117 } 2118 2119 opt_rebuild_def_use(f); 2120 DseCtx ctx; 2121 memset(&ctx, 0, sizeof ctx); 2122 ctx.f = f; 2123 ctx.local_escaped = 2124 arena_zarray(f->arena, u8, f->nframe_slots ? f->nframe_slots + 1u : 1u); 2125 2126 memset(&ctx.gvn, 0, sizeof ctx.gvn); 2127 ctx.gvn.f = f; 2128 ctx.gvn.parent = arena_array(f->arena, Val, f->nvals ? f->nvals : 1u); 2129 ctx.gvn.constants = 2130 arena_zarray(f->arena, GvnConst, f->nvals ? f->nvals : 1u); 2131 ctx.gvn.local_escaped = ctx.local_escaped; 2132 for (Val v = 0; v < f->nvals; ++v) ctx.gvn.parent[v] = v; 2133 gvn_collect_local_escapes(&ctx.gvn); 2134 dse_collect_constants(&ctx.gvn); 2135 dse_collect_stores(&ctx); 2136 if (!ctx.nkeys) { 2137 opt_rebuild_def_use(f); 2138 return; 2139 } 2140 2141 dse_init_block_sets(&ctx); 2142 int changed = 1; 2143 while (changed) { 2144 changed = 0; 2145 for (u32 rb = f->nblocks; rb > 0; --rb) { 2146 u32 b = rb - 1u; 2147 dse_compute_block_out(&ctx, b, &ctx.scratch_out); 2148 dse_transfer_block(&ctx, b, &ctx.scratch_out, &ctx.scratch_in, 0); 2149 changed |= dse_bitset_copy(&ctx, &ctx.block[b].out, &ctx.scratch_out); 2150 changed |= dse_bitset_copy(&ctx, &ctx.block[b].in, &ctx.scratch_in); 2151 } 2152 } 2153 2154 for (u32 b = 0; b < f->nblocks; ++b) { 2155 dse_transfer_block(&ctx, b, &ctx.block[b].out, &ctx.scratch_in, 1); 2156 } 2157 2158 if (ctx.changed) { 2159 dse_compact_nops(f); 2160 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 2161 } 2162 opt_rebuild_def_use(f); 2163 } 2164 2165 static void licm_mark_body(Func* f, const u8* reachable, u32 header, u32 latch, 2166 u8* body, u32* stack) { 2167 u32 sp = 0; 2168 if (!body[header]) body[header] = 1; 2169 if (!body[latch]) { 2170 body[latch] = 1; 2171 stack[sp++] = latch; 2172 } 2173 2174 while (sp) { 2175 u32 b = stack[--sp]; 2176 if (b == header) continue; 2177 Block* bl = &f->blocks[b]; 2178 for (u32 p = 0; p < bl->npreds; ++p) { 2179 u32 pred = bl->preds[p]; 2180 if (pred >= f->nblocks || !reachable[pred] || body[pred]) continue; 2181 body[pred] = 1; 2182 stack[sp++] = pred; 2183 } 2184 } 2185 } 2186 2187 static u32 licm_collect_loops(Func* f, OptAnalysis* a, LicmLoop** out) { 2188 u32 nloops = 0; 2189 LicmLoop* loops = 2190 arena_zarray(f->arena, LicmLoop, f->nblocks ? f->nblocks : 1u); 2191 u8* scratch = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u); 2192 u32* stack = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u); 2193 2194 for (u32 header = 0; header < f->nblocks; ++header) { 2195 if (!a->reachable || !a->reachable[header]) continue; 2196 memset(scratch, 0, f->nblocks * sizeof scratch[0]); 2197 int has_loop = 0; 2198 2199 for (u32 latch = 0; latch < f->nblocks; ++latch) { 2200 if (!a->reachable[latch]) continue; 2201 Block* lb = &f->blocks[latch]; 2202 for (u32 s = 0; s < lb->nsucc; ++s) { 2203 if (lb->succ[s] != header) continue; 2204 if (!opt_analysis_dominates(a, header, latch)) continue; 2205 has_loop = 1; 2206 licm_mark_body(f, a->reachable, header, latch, scratch, stack); 2207 } 2208 } 2209 if (!has_loop) continue; 2210 2211 u32 preheader = OPT_BLOCK_NONE; 2212 Block* hb = &f->blocks[header]; 2213 for (u32 p = 0; p < hb->npreds; ++p) { 2214 u32 pred = hb->preds[p]; 2215 if (pred >= f->nblocks || scratch[pred]) continue; 2216 if (preheader != OPT_BLOCK_NONE) { 2217 preheader = OPT_BLOCK_NONE; 2218 break; 2219 } 2220 preheader = pred; 2221 } 2222 if (preheader == OPT_BLOCK_NONE) continue; 2223 if (f->blocks[preheader].nsucc != 1 || 2224 f->blocks[preheader].succ[0] != header) 2225 continue; 2226 2227 u8* body = arena_array(f->arena, u8, f->nblocks ? f->nblocks : 1u); 2228 memcpy(body, scratch, f->nblocks * sizeof body[0]); 2229 loops[nloops].header = header; 2230 loops[nloops].preheader = preheader; 2231 loops[nloops].body = body; 2232 ++nloops; 2233 } 2234 2235 *out = loops; 2236 return nloops; 2237 } 2238 2239 static int licm_safe_binop(BinOp op) { 2240 switch (op) { 2241 case BO_SDIV: 2242 case BO_UDIV: 2243 case BO_SREM: 2244 case BO_UREM: 2245 case BO_FDIV: 2246 return 0; 2247 default: 2248 return 1; 2249 } 2250 } 2251 2252 static int licm_candidate(Func* f, const Inst* in) { 2253 if (!in || in->def == VAL_NONE || in->ndefs || in->flags) return 0; 2254 if (in->def >= f->nvals || opt_inst_has_side_effect(f, in)) return 0; 2255 switch ((IROp)in->op) { 2256 case IR_CONST_I: 2257 case IR_CONST_BYTES: 2258 case IR_LOAD_IMM: 2259 case IR_LOAD_CONST: 2260 case IR_LOAD_LABEL_ADDR: 2261 case IR_COPY: 2262 case IR_ADDR_OF: 2263 case IR_UNOP: 2264 case IR_CMP: 2265 case IR_CONVERT: 2266 return 1; 2267 case IR_BINOP: 2268 return licm_safe_binop((BinOp)in->extra.imm); 2269 default: 2270 return 0; 2271 } 2272 } 2273 2274 static int licm_operand_invariant(Func* f, const u8* body, const Operand* op) { 2275 if (!op) return 1; 2276 if (op->kind == OPK_REG) { 2277 Val v = (Val)op->v.reg; 2278 if (v == VAL_NONE || v >= f->nvals) return 0; 2279 u32 def_block = f->val_def_block[v]; 2280 return def_block < f->nblocks && !body[def_block]; 2281 } 2282 if (op->kind == OPK_INDIRECT) { 2283 Val v = (Val)op->v.ind.base; 2284 if (v == VAL_NONE || v >= f->nvals) return 0; 2285 u32 def_block = f->val_def_block[v]; 2286 return def_block < f->nblocks && !body[def_block]; 2287 } 2288 return 1; 2289 } 2290 2291 static int licm_inst_invariant(Func* f, const LicmLoop* loop, const Inst* in) { 2292 if (!licm_candidate(f, in)) return 0; 2293 for (u32 i = 0; i < in->nopnds; ++i) { 2294 const Operand* op = &in->opnds[i]; 2295 if (op->kind == OPK_REG && opt_val_in_inst_defs(in, (Val)op->v.reg)) 2296 continue; 2297 if (!licm_operand_invariant(f, loop->body, op)) return 0; 2298 } 2299 return 1; 2300 } 2301 2302 static void licm_insert_inst(Func* f, u32 block, u32 at, Inst in) { 2303 Block* bl = &f->blocks[block]; 2304 if (at > bl->ninsts) at = bl->ninsts; 2305 if (bl->ninsts == bl->cap) { 2306 u32 ncap = bl->cap ? bl->cap * 2u : 8u; 2307 while (ncap < bl->ninsts + 1u) ncap *= 2u; 2308 Inst* insts = arena_zarray(f->arena, Inst, ncap); 2309 if (at) memcpy(insts, bl->insts, sizeof(insts[0]) * at); 2310 if (bl->ninsts > at) 2311 memcpy(&insts[at + 1u], &bl->insts[at], 2312 sizeof(insts[0]) * (bl->ninsts - at)); 2313 bl->insts = insts; 2314 bl->cap = ncap; 2315 } else { 2316 for (u32 i = bl->ninsts; i > at; --i) bl->insts[i] = bl->insts[i - 1u]; 2317 } 2318 bl->insts[at] = in; 2319 ++bl->ninsts; 2320 } 2321 2322 static void licm_remove_inst(Func* f, u32 block, u32 at) { 2323 Block* bl = &f->blocks[block]; 2324 if (at >= bl->ninsts) return; 2325 for (u32 i = at + 1u; i < bl->ninsts; ++i) bl->insts[i - 1u] = bl->insts[i]; 2326 --bl->ninsts; 2327 } 2328 2329 static u32 licm_preheader_insert_pos(Func* f, u32 preheader) { 2330 Block* bl = &f->blocks[preheader]; 2331 if (bl->ninsts && o2_is_terminator(&bl->insts[bl->ninsts - 1u])) 2332 return bl->ninsts - 1u; 2333 return bl->ninsts; 2334 } 2335 2336 static void licm_hoist_inst(Func* f, const LicmLoop* loop, u32 block, 2337 u32 inst) { 2338 Inst moved = f->blocks[block].insts[inst]; 2339 u32 at = licm_preheader_insert_pos(f, loop->preheader); 2340 licm_insert_inst(f, loop->preheader, at, moved); 2341 licm_remove_inst(f, block, inst); 2342 if (moved.def != VAL_NONE && moved.def < f->nvals) { 2343 f->val_def_block[moved.def] = loop->preheader; 2344 f->val_def_inst[moved.def] = at; 2345 } 2346 } 2347 2348 void opt_licm(Func* f) { 2349 if (!f || f->opt_rewritten) return; 2350 if (!f->opt_reg_ssa && f->npregs > 1) { 2351 opt_rebuild_def_use(f); 2352 return; 2353 } 2354 2355 OptAnalysis a; 2356 memset(&a, 0, sizeof a); 2357 opt_analysis_build_dominators(f, &a); 2358 LicmLoop* loops = NULL; 2359 u32 nloops = licm_collect_loops(f, &a, &loops); 2360 int changed = 0; 2361 2362 for (u32 l = 0; l < nloops; ++l) { 2363 LicmLoop* loop = &loops[l]; 2364 int again = 1; 2365 while (again) { 2366 again = 0; 2367 for (u32 b = 0; b < f->nblocks; ++b) { 2368 if (!loop->body[b] || b == loop->preheader) continue; 2369 Block* bl = &f->blocks[b]; 2370 for (u32 i = 0; i < bl->ninsts;) { 2371 Inst* in = &bl->insts[i]; 2372 if (!licm_inst_invariant(f, loop, in)) { 2373 ++i; 2374 continue; 2375 } 2376 licm_hoist_inst(f, loop, b, i); 2377 changed = 1; 2378 again = 1; 2379 bl = &f->blocks[b]; 2380 } 2381 } 2382 } 2383 } 2384 2385 if (changed) { 2386 dse_refresh_def_locations(f); 2387 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 2388 } 2389 opt_rebuild_def_use(f); 2390 } 2391 2392 static int pressure_candidate(const Inst* in) { 2393 if (!in || in->def == VAL_NONE || in->ndefs) return 0; 2394 switch ((IROp)in->op) { 2395 case IR_LOAD_IMM: 2396 case IR_CONST_I: 2397 return 1; 2398 default: 2399 return 0; 2400 } 2401 } 2402 2403 static int pressure_barrier(const Inst* in) { 2404 if (!in) return 1; 2405 if (o2_is_terminator(in)) return 1; 2406 switch ((IROp)in->op) { 2407 case IR_LOAD: 2408 case IR_STORE: 2409 case IR_LOAD_CONST: 2410 case IR_AGG_COPY: 2411 case IR_AGG_SET: 2412 case IR_BITFIELD_LOAD: 2413 case IR_BITFIELD_STORE: 2414 case IR_CALL: 2415 case IR_SCOPE_BEGIN: 2416 case IR_SCOPE_END: 2417 case IR_BREAK_TO: 2418 case IR_CONTINUE_TO: 2419 case IR_ALLOCA: 2420 case IR_VA_START: 2421 case IR_VA_ARG: 2422 case IR_VA_END: 2423 case IR_VA_COPY: 2424 case IR_ATOMIC_LOAD: 2425 case IR_ATOMIC_STORE: 2426 case IR_ATOMIC_RMW: 2427 case IR_ATOMIC_CAS: 2428 case IR_FENCE: 2429 case IR_ASM_BLOCK: 2430 case IR_INTRINSIC: 2431 return 1; 2432 default: 2433 return 0; 2434 } 2435 } 2436 2437 static int pressure_single_use(Func* f, Val v, OptUse* out) { 2438 u32 n = 0; 2439 OptUse one; 2440 memset(&one, 0, sizeof one); 2441 for (u32 u = f->opt_first_use_by_val[v]; u != OPT_USE_NONE; 2442 u = f->opt_uses[u].next_for_val) { 2443 one = f->opt_uses[u]; 2444 ++n; 2445 if (n > 1u) return 0; 2446 } 2447 if (n != 1u) return 0; 2448 *out = one; 2449 return 1; 2450 } 2451 2452 static int pressure_can_move_within_block(Func* f, u32 b, u32 from, u32 to) { 2453 if (b >= f->nblocks || from >= to) return 0; 2454 Block* bl = &f->blocks[b]; 2455 if (to > bl->ninsts) return 0; 2456 for (u32 i = from + 1u; i < to; ++i) 2457 if (pressure_barrier(&bl->insts[i])) return 0; 2458 return 1; 2459 } 2460 2461 static PressureBlockPlan* pressure_block_plan(Func* f, PressurePlan* plan, 2462 u32 b) { 2463 if (!plan->blocks) 2464 plan->blocks = 2465 arena_zarray(f->arena, PressureBlockPlan, f->nblocks ? f->nblocks : 1u); 2466 PressureBlockPlan* bp = &plan->blocks[b]; 2467 if (!bp->move_src) { 2468 Block* bl = &f->blocks[b]; 2469 u32 n = bl->ninsts ? bl->ninsts : 1u; 2470 bp->move_src = arena_zarray(f->arena, u8, n); 2471 bp->first_before = arena_array(f->arena, u32, n); 2472 bp->last_before = arena_array(f->arena, u32, n); 2473 bp->next_move = arena_array(f->arena, u32, n); 2474 for (u32 i = 0; i < n; ++i) { 2475 bp->first_before[i] = OPT_BLOCK_NONE; 2476 bp->last_before[i] = OPT_BLOCK_NONE; 2477 bp->next_move[i] = OPT_BLOCK_NONE; 2478 } 2479 } 2480 return bp; 2481 } 2482 2483 static void pressure_plan_move(Func* f, PressurePlan* plan, u32 b, u32 from, 2484 u32 to) { 2485 PressureBlockPlan* bp = pressure_block_plan(f, plan, b); 2486 if (bp->move_src[from]) return; 2487 bp->move_src[from] = 1; 2488 bp->next_move[from] = OPT_BLOCK_NONE; 2489 if (bp->first_before[to] == OPT_BLOCK_NONE) { 2490 bp->first_before[to] = from; 2491 } else { 2492 bp->next_move[bp->last_before[to]] = from; 2493 } 2494 bp->last_before[to] = from; 2495 plan->nmoves++; 2496 } 2497 2498 static int pressure_plan(Func* f, PressurePlan* plan) { 2499 memset(plan, 0, sizeof *plan); 2500 for (Val v = 1; v < f->nvals; ++v) { 2501 u32 db = f->val_def_block[v]; 2502 u32 di = f->val_def_inst[v]; 2503 if (db >= f->nblocks || di >= f->blocks[db].ninsts) continue; 2504 Inst* def = &f->blocks[db].insts[di]; 2505 if (def->def != v || !pressure_candidate(def)) continue; 2506 2507 OptUse use; 2508 if (!pressure_single_use(f, v, &use)) continue; 2509 if (use.kind != OPT_USE_OPERAND) continue; 2510 if (use.block != db) continue; 2511 if (use.inst <= di + 1u) continue; 2512 if (f->blocks[use.block].loop_depth > f->blocks[db].loop_depth) continue; 2513 if (!pressure_can_move_within_block(f, db, di, use.inst)) continue; 2514 2515 pressure_plan_move(f, plan, db, di, use.inst); 2516 } 2517 return plan->nmoves != 0; 2518 } 2519 2520 static void pressure_apply_block(Func* f, u32 b, PressureBlockPlan* bp) { 2521 Block* bl = &f->blocks[b]; 2522 Inst* old = bl->insts; 2523 Inst* insts = arena_array(f->arena, Inst, bl->ninsts ? bl->ninsts : 1u); 2524 u32 w = 0; 2525 for (u32 i = 0; i < bl->ninsts; ++i) { 2526 for (u32 m = bp->first_before[i]; m != OPT_BLOCK_NONE; 2527 m = bp->next_move[m]) { 2528 insts[w++] = old[m]; 2529 } 2530 if (!bp->move_src[i]) insts[w++] = old[i]; 2531 } 2532 bl->insts = insts; 2533 bl->cap = bl->ninsts; 2534 if (w != bl->ninsts) { 2535 SrcLoc loc = {0, 0, 0}; 2536 compiler_panic(f->c, loc, "opt pressure-relief: bad rewrite (%u, %u)", 2537 (unsigned)w, (unsigned)bl->ninsts); 2538 } 2539 } 2540 2541 static void pressure_apply(Func* f, PressurePlan* plan) { 2542 if (!plan->blocks || !plan->nmoves) return; 2543 for (u32 b = 0; b < f->nblocks; ++b) { 2544 PressureBlockPlan* bp = &plan->blocks[b]; 2545 if (bp->move_src) pressure_apply_block(f, b, bp); 2546 } 2547 dse_refresh_def_locations(f); 2548 opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 2549 } 2550 2551 void opt_pressure_relief(Func* f) { 2552 if (!f || f->opt_rewritten) return; 2553 if (!f->opt_reg_ssa && f->npregs > 1) { 2554 opt_rebuild_def_use(f); 2555 return; 2556 } 2557 2558 PressurePlan plan; 2559 opt_rebuild_def_use(f); 2560 if (pressure_plan(f, &plan)) pressure_apply(f, &plan); 2561 opt_rebuild_def_use(f); 2562 } 2563 2564 static int ssa_combine_cmp_def(Func* f, Val v, Inst** out) { 2565 Inst* def = NULL; 2566 if (!val_def_inst(f, v, &def)) return 0; 2567 if ((IROp)def->op != IR_CMP || def->nopnds < 3) return 0; 2568 *out = def; 2569 return 1; 2570 } 2571 2572 static int ssa_combine_fold_cmp_branch(Func* f) { 2573 int changed = 0; 2574 for (u32 b = 0; b < f->nblocks; ++b) { 2575 Block* bl = &f->blocks[b]; 2576 if (!bl->ninsts || bl->nsucc < 2) continue; 2577 Inst* br = &bl->insts[bl->ninsts - 1u]; 2578 if ((IROp)br->op != IR_CONDBR || br->nopnds < 1) continue; 2579 if (br->opnds[0].kind != OPK_REG) continue; 2580 Inst* cmp = NULL; 2581 if (!ssa_combine_cmp_def(f, (Val)br->opnds[0].v.reg, &cmp)) continue; 2582 2583 Operand* opnds = arena_array(f->arena, Operand, 2); 2584 opnds[0] = cmp->opnds[1]; 2585 opnds[1] = cmp->opnds[2]; 2586 br->op = IR_CMP_BRANCH; 2587 br->opnds = opnds; 2588 br->nopnds = 2; 2589 br->extra.imm = cmp->extra.imm; 2590 changed = 1; 2591 } 2592 return changed; 2593 } 2594 2595 static int ssa_combine_fold_addr_uses(Func* f) { 2596 int changed = 0; 2597 opt_rebuild_def_use(f); 2598 u32 nvals = f->nvals; 2599 for (Val v = 1; v < nvals; ++v) { 2600 Inst* def = NULL; 2601 if (!addr_def_inst(f, v, &def)) continue; 2602 Operand addr = def->opnds[1]; 2603 if (addr.kind != OPK_LOCAL) continue; 2604 2605 for (u32 u = f->opt_first_use_by_val[v]; u != OPT_USE_NONE; 2606 u = f->opt_uses[u].next_for_val) { 2607 OptUse* use = &f->opt_uses[u]; 2608 /* Only fold zero-EA uses to OPK_LOCAL. EA-shaped uses keep the EA 2609 * on the load/store; OPK_LOCAL cannot carry the offset/index. */ 2610 if (addr_use_foldable_kind(f, use) != 1) continue; 2611 Inst* mem = &f->blocks[use->block].insts[use->inst]; 2612 Operand folded = addr; 2613 folded.type = mem->extra.mem.type ? mem->extra.mem.type : addr.type; 2614 *use->operand = folded; 2615 changed = 1; 2616 } 2617 } 2618 return changed; 2619 } 2620 2621 void opt_ssa_combine(Func* f) { 2622 if (!f || f->opt_rewritten) return; 2623 if (!f->opt_reg_ssa && f->npregs > 1) { 2624 opt_rebuild_def_use(f); 2625 return; 2626 } 2627 2628 opt_rebuild_def_use(f); 2629 int changed = ssa_combine_fold_cmp_branch(f); 2630 changed |= ssa_combine_fold_addr_uses(f); 2631 if (changed) opt_analysis_invalidate(f, OPT_ANALYSIS_DEF_USE); 2632 opt_rebuild_def_use(f); 2633 }