pass_inline.c (34223B)
1 #include <string.h> 2 3 #include "core/arena.h" 4 #include "core/core.h" 5 #include "core/hashmap.h" 6 #include "core/metrics.h" 7 #include "opt/opt_internal.h" 8 9 typedef struct InlineMap { 10 Func* caller; 11 Func* callee; 12 PReg* preg; 13 u32 npreg; 14 FrameSlot* slot; 15 u32 nslot; 16 u32* block; 17 u32 nblock; 18 } InlineMap; 19 20 typedef struct InstVec { 21 Func* f; 22 Inst* v; 23 u32 n; 24 u32 cap; 25 } InstVec; 26 27 typedef struct InlineOrderCtx { 28 FuncSet* fs; 29 u8* temp; 30 u8* done; 31 Func** order; 32 u32 norder; 33 } InlineOrderCtx; 34 35 #define INLINE_NORMAL_COST_LIMIT 20u 36 #define INLINE_HINT_COST_LIMIT 40u 37 #define INLINE_ABS_GROWTH_LIMIT 64u 38 #define INLINE_HINT_ABS_GROWTH_LIMIT 128u 39 40 /* Inline-pressure cap (O1.md W4). The existing cost/growth gates bound how much 41 * a single inline *grows* a caller, but at -O1 there is no SSA post-inline 42 * cleanup (GVN/DSE/redundant-load elim are O2-only), so inlining into a caller 43 * whose live-set is already far past the register file just deepens the spilling 44 * it does. The whole-program inliner walks callers bottom-up to a fixpoint, so a 45 * single hot caller can accrete dozens of small bodies and climb to hundreds of 46 * simultaneously-live pseudo-registers. This is a cheap, per-call-site back-off: 47 * once the estimated post-inline live-set (caller pregs + callee pregs, an upper 48 * bound — param/return materialization actually reuses some) would sit past this 49 * cap, refuse a DEFAULT/HINT inline. ALWAYS still bypasses it (the frontend's 50 * explicit request wins, matching the cost-cap behavior). 51 * 52 * The cap is set well above any target's register file (aa64/rv64 = 32 GPRs, 53 * x64 = 16; allocatable ~16-28 after reserves), so it only fires on callers that 54 * are *already* spilling heavily and can only spill worse — it is deliberately 55 * conservative and never trims a moderate-pressure hot loop. Measured on the 56 * ecosystem corpus (aarch64/Darwin, -O1): byte-identical on the inline-win files 57 * (lz4 0.39x, yyjson 0.88x, lapi, cjson, miniz) and a small spill reduction on 58 * sqlite (the inline-heavy / huge-function case the doc names). See O1.md W4. */ 59 #define INLINE_PRESSURE_CAP 512u 60 61 /* Streaming O1 tiny-inline: a much smaller budget than the whole-program 62 * inliner. DEFAULT/HINT callees must fit under this cost; ALWAYS bypasses it. 63 * Bounded by max passes since an inlined straightline body never introduces a 64 * new call site. */ 65 #define INLINE_TINY_COST_LIMIT 8u 66 #define TINY_INLINE_MAX_PASSES 4u 67 68 static u32 func_inline_cost(Func* f) { 69 u32 cost = 0; 70 if (!f) return 0; 71 for (u32 b = 0; b < f->nblocks; ++b) { 72 Block* bl = &f->blocks[b]; 73 for (u32 i = 0; i < bl->ninsts; ++i) { 74 switch ((IROp)bl->insts[i].op) { 75 case IR_NOP: 76 case IR_PARAM_DECL: 77 case IR_BR: 78 case IR_RET: 79 break; 80 default: 81 ++cost; 82 break; 83 } 84 } 85 } 86 return cost; 87 } 88 89 static void instvec_push(InstVec* iv, const Inst* in) { 90 if (iv->n == iv->cap) { 91 u32 ncap = iv->cap ? iv->cap * 2u : 16u; 92 Inst* nv = arena_array(iv->f->arena, Inst, ncap); 93 if (iv->v) memcpy(nv, iv->v, sizeof(Inst) * iv->n); 94 iv->v = nv; 95 iv->cap = ncap; 96 } 97 iv->v[iv->n++] = *in; 98 } 99 100 /* Symbol -> index-into-fs->funcs map. Key 0 (OBJ_SYM_NONE) is the empty-slot 101 * sentinel in the hashmap, which is fine: a NONE-named function is never a 102 * callee (no symbol to call) and is handled by the linear fallback as a 103 * caller. */ 104 HASHMAP_DEFINE(InlineSymMap, ObjSymId, u32, hash_u32); 105 106 /* O(1)-lookup acceleration for opt_inline, attached to FuncSet.index. Built 107 * once over the whole-program set; the streaming tiny-inliner leaves 108 * FuncSet.index NULL and the helpers below fall back to a linear scan over its 109 * 2-element set. */ 110 typedef struct InlineIndex { 111 InlineSymMap sym2idx; /* ObjSymId -> index into fs->funcs */ 112 u32* scc; /* SCC id per fs index; same id <=> mutually recursive */ 113 u32 nfuncs; /* size of scc[] (== fs->nfuncs at build time) */ 114 } InlineIndex; 115 116 static Func* funcset_find(FuncSet* fs, ObjSymId sym) { 117 if (!fs || sym == OBJ_SYM_NONE) return NULL; 118 if (fs->index) { 119 InlineIndex* idx = (InlineIndex*)fs->index; 120 u32* slot = InlineSymMap_get(&idx->sym2idx, sym); 121 return slot ? fs->funcs[*slot] : NULL; 122 } 123 for (u32 i = 0; i < fs->nfuncs; ++i) 124 if (fs->funcs[i] && fs->funcs[i]->name == sym) return fs->funcs[i]; 125 return NULL; 126 } 127 128 static int funcset_index(FuncSet* fs, Func* f) { 129 if (!fs || !f) return -1; 130 if (fs->index && f->name != OBJ_SYM_NONE) { 131 InlineIndex* idx = (InlineIndex*)fs->index; 132 u32* slot = InlineSymMap_get(&idx->sym2idx, f->name); 133 /* Guard against a (deduped-away in practice) name collision: only trust the 134 * mapped slot when it actually points back at f. */ 135 if (slot && fs->funcs[*slot] == f) return (int)*slot; 136 } 137 for (u32 i = 0; i < fs->nfuncs; ++i) 138 if (fs->funcs[i] == f) return (int)i; 139 return -1; 140 } 141 142 static Func* direct_callee(FuncSet* fs, const Inst* in) { 143 if (!in || (IROp)in->op != IR_CALL) return NULL; 144 IRCallAux* aux = (IRCallAux*)in->extra.aux; 145 if (!aux || aux->use_plan_replay) return NULL; 146 if (aux->desc.flags & CG_CALL_TAIL) return NULL; 147 if (aux->desc.callee.kind != OPK_GLOBAL) return NULL; 148 if (aux->desc.callee.v.global.addend != 0) return NULL; 149 return funcset_find(fs, aux->desc.callee.v.global.sym); 150 } 151 152 static KitCgInlinePolicy call_inline_policy(const Inst* in) { 153 if (!in || (IROp)in->op != IR_CALL) return KIT_CG_INLINE_DEFAULT; 154 IRCallAux* aux = (IRCallAux*)in->extra.aux; 155 return aux ? aux->desc.inline_policy : KIT_CG_INLINE_DEFAULT; 156 } 157 158 static KitCgInlinePolicy effective_inline_policy(const Inst* in, 159 const Func* callee) { 160 KitCgInlinePolicy call_policy = call_inline_policy(in); 161 KitCgInlinePolicy callee_policy = 162 callee ? callee->desc.inline_policy : KIT_CG_INLINE_DEFAULT; 163 if (call_policy == KIT_CG_INLINE_NEVER || 164 callee_policy == KIT_CG_INLINE_NEVER) 165 return KIT_CG_INLINE_NEVER; 166 if (call_policy == KIT_CG_INLINE_ALWAYS || 167 callee_policy == KIT_CG_INLINE_ALWAYS) 168 return KIT_CG_INLINE_ALWAYS; 169 if (call_policy == KIT_CG_INLINE_HINT || callee_policy == KIT_CG_INLINE_HINT) 170 return KIT_CG_INLINE_HINT; 171 return KIT_CG_INLINE_DEFAULT; 172 } 173 174 static int func_reaches(FuncSet* fs, Func* from, Func* target, u8* seen) { 175 int idx = funcset_index(fs, from); 176 if (idx < 0) return 0; 177 if (seen[idx]) return 0; 178 seen[idx] = 1; 179 for (u32 b = 0; b < from->nblocks; ++b) { 180 Block* bl = &from->blocks[b]; 181 for (u32 i = 0; i < bl->ninsts; ++i) { 182 Func* callee = direct_callee(fs, &bl->insts[i]); 183 if (!callee) continue; 184 if (callee == target) return 1; 185 if (func_reaches(fs, callee, target, seen)) return 1; 186 } 187 } 188 return 0; 189 } 190 191 static int recursive_or_scc(FuncSet* fs, Func* caller, Func* callee) { 192 if (caller == callee) return 1; 193 /* Whole-program path: the inliner only ever asks this where a caller->callee 194 * call edge exists, so "callee can transitively reach caller" is exactly 195 * "caller and callee share a strongly-connected component". With the SCC ids 196 * precomputed (inline_index_build) this is O(1) and gives the identical 197 * verdict the linear func_reaches DFS would. */ 198 if (fs->index) { 199 InlineIndex* idx = (InlineIndex*)fs->index; 200 if (idx->scc) { 201 int ci = funcset_index(fs, caller); 202 int ce = funcset_index(fs, callee); 203 if (ci >= 0 && ce >= 0 && (u32)ci < idx->nfuncs && (u32)ce < idx->nfuncs) 204 return idx->scc[ci] == idx->scc[ce]; 205 } 206 } 207 /* Ad-hoc 2-element set (streaming tiny-inliner): direct reachability DFS. */ 208 u8* seen = arena_zarray(fs->arena, u8, fs->nfuncs ? fs->nfuncs : 1u); 209 return func_reaches(fs, callee, caller, seen); 210 } 211 212 static int op_supported_in_straightline_inline(IROp op) { 213 switch (op) { 214 case IR_NOP: 215 case IR_PARAM_DECL: 216 case IR_LOAD_IMM: 217 case IR_LOAD_CONST: 218 case IR_COPY: 219 case IR_LOAD: 220 case IR_STORE: 221 case IR_BINOP: 222 case IR_UNOP: 223 case IR_CMP: 224 case IR_CONVERT: 225 case IR_BR: 226 case IR_CONDBR: 227 case IR_CMP_BRANCH: 228 case IR_RET: 229 return 1; 230 default: 231 return 0; 232 } 233 } 234 235 static int callee_inline_shape(Func* callee, KitCgInlinePolicy policy, 236 u32* cost_out) { 237 if (!callee || callee->opt_reg_ssa || callee->opt_rewritten) return 0; 238 if (kit_cg_type_func_is_variadic((KitCompiler*)callee->c, callee->type)) { 239 metrics_count(callee->c, "opt.inline.refuse_shape_variadic", 1); 240 return 0; 241 } 242 if (callee->entry >= callee->nblocks) { 243 metrics_count(callee->c, "opt.inline.refuse_shape_entry", 1); 244 return 0; 245 } 246 247 u32 nret = 0; 248 u32 cost = 0; 249 for (u32 b = 0; b < callee->nblocks; ++b) { 250 Block* bl = &callee->blocks[b]; 251 for (u32 i = 0; i < bl->ninsts; ++i) { 252 Inst* in = &bl->insts[i]; 253 IROp op = (IROp)in->op; 254 if (!op_supported_in_straightline_inline(op)) { 255 metrics_count(callee->c, "opt.inline.refuse_shape_op", 1); 256 return 0; 257 } 258 if (op == IR_RET) { 259 ++nret; 260 if (i + 1u != bl->ninsts) { 261 metrics_count(callee->c, "opt.inline.refuse_shape_ret_pos", 1); 262 return 0; 263 } 264 continue; 265 } 266 if (op != IR_NOP && op != IR_PARAM_DECL && op != IR_BR) ++cost; 267 } 268 } 269 if (nret == 0) { 270 metrics_count(callee->c, "opt.inline.refuse_shape_ret_count", 1); 271 return 0; 272 } 273 if (nret > 1) cost += (nret - 1u) * 4u; 274 u32 cost_limit = policy == KIT_CG_INLINE_ALWAYS ? 0xffffffffu 275 : policy == KIT_CG_INLINE_HINT ? INLINE_HINT_COST_LIMIT 276 : INLINE_NORMAL_COST_LIMIT; 277 if (cost > cost_limit) { 278 metrics_count(callee->c, "opt.inline.refuse_shape_budget", 1); 279 return 0; 280 } 281 if (cost_out) *cost_out = cost; 282 return 1; 283 } 284 285 static PReg map_preg(InlineMap* m, PReg r) { 286 if (r == PREG_NONE || r == 0 || r >= m->npreg) return r; 287 return m->preg[r] ? m->preg[r] : r; 288 } 289 290 static FrameSlot map_slot(InlineMap* m, FrameSlot s) { 291 if (s == FRAME_SLOT_NONE || s >= m->nslot) return s; 292 return m->slot[s] ? m->slot[s] : s; 293 } 294 295 static u32 map_block(InlineMap* m, u32 b) { 296 if (b >= m->nblock) return b; 297 return m->block[b] != 0xffffffffu ? m->block[b] : b; 298 } 299 300 static void map_mem(InlineMap* m, MemAccess* mem) { 301 if (!mem) return; 302 if (mem->alias.kind == ALIAS_LOCAL && mem->alias.v.local_id > 0) { 303 FrameSlot old = (FrameSlot)mem->alias.v.local_id; 304 mem->alias.v.local_id = (i32)map_slot(m, old); 305 } 306 } 307 308 static Operand map_operand(InlineMap* m, Operand op) { 309 switch ((OptOperandKind)op.kind) { 310 case OPK_REG: 311 op.v.reg = map_preg(m, (PReg)op.v.reg); 312 break; 313 case OPK_LOCAL: 314 op.v.frame_slot = map_slot(m, op.v.frame_slot); 315 break; 316 case OPK_INDIRECT: 317 op.v.ind.base = map_preg(m, (PReg)op.v.ind.base); 318 if (op.v.ind.index != (Reg)REG_NONE) 319 op.v.ind.index = map_preg(m, (PReg)op.v.ind.index); 320 break; 321 default: 322 break; 323 } 324 return op; 325 } 326 327 static int build_inline_map(InlineMap* m, Func* caller, Func* callee) { 328 memset(m, 0, sizeof *m); 329 m->caller = caller; 330 m->callee = callee; 331 m->npreg = callee->npregs; 332 m->nslot = callee->nframe_slots + 1u; 333 m->nblock = callee->nblocks; 334 m->preg = arena_zarray(caller->arena, PReg, m->npreg ? m->npreg : 1u); 335 m->slot = arena_zarray(caller->arena, FrameSlot, m->nslot ? m->nslot : 1u); 336 m->block = arena_array(caller->arena, u32, m->nblock ? m->nblock : 1u); 337 for (u32 b = 0; b < m->nblock; ++b) m->block[b] = 0xffffffffu; 338 339 for (FrameSlot s = 1; s <= callee->nframe_slots; ++s) { 340 IRFrameSlot* old = &callee->frame_slots[s - 1u]; 341 FrameSlotDesc d; 342 memset(&d, 0, sizeof d); 343 d.type = old->type; 344 d.name = old->name; 345 d.loc = old->loc; 346 d.size = old->size; 347 d.align = old->align; 348 d.kind = old->kind == FS_PARAM ? FS_LOCAL : old->kind; 349 d.flags = old->flags; 350 m->slot[s] = ir_frame_slot_new(caller, &d); 351 } 352 353 for (PReg r = 1; r < callee->npregs; ++r) { 354 m->preg[r] = 355 ir_alloc_preg(caller, callee->preg_type[r], callee->preg_cls[r]); 356 } 357 for (u32 b = 0; b < callee->nblocks; ++b) m->block[b] = ir_block_new(caller); 358 return 1; 359 } 360 361 static Inst make_inst(Func* f, IROp op, SrcLoc loc) { 362 Inst in; 363 memset(&in, 0, sizeof in); 364 in.op = (u16)op; 365 in.id = ir_inst_id_new(f); 366 in.loc = loc; 367 return in; 368 } 369 370 static Operand local_operand(FrameSlot s, KitCgTypeId ty) { 371 Operand op; 372 memset(&op, 0, sizeof op); 373 op.kind = OPK_LOCAL; 374 op.cls = RC_INT; 375 op.type = ty; 376 op.v.frame_slot = s; 377 return op; 378 } 379 380 static MemAccess param_mem(const IRParam* p, FrameSlot s) { 381 MemAccess m; 382 memset(&m, 0, sizeof m); 383 m.type = p->type; 384 m.size = p->size; 385 m.align = p->align; 386 m.alias.kind = ALIAS_LOCAL; 387 m.alias.v.local_id = (i32)s; 388 return m; 389 } 390 391 static int append_param_materialization(InstVec* out, InlineMap* m, 392 const Inst* call) { 393 IRCallAux* aux = (IRCallAux*)call->extra.aux; 394 Func* caller = m->caller; 395 Func* callee = m->callee; 396 if (!aux || aux->desc.nargs != callee->nparams) return 0; 397 398 for (u32 i = 0; i < callee->nparams; ++i) { 399 IRParam* p = &callee->params[i]; 400 const CGABIValue* av = &aux->desc.args[i]; 401 if (av->nparts != 0) return 0; 402 Operand src = av->storage; 403 if (src.kind != OPK_REG && src.kind != OPK_IMM) return 0; 404 if (p->storage.kind == CG_LOCAL_STORAGE_REG) { 405 PReg dst_r = map_preg(m, (PReg)p->storage.v.reg); 406 Operand dst; 407 memset(&dst, 0, sizeof dst); 408 dst.kind = OPK_REG; 409 dst.cls = opt_reg_cls(caller, dst_r); 410 dst.type = p->type; 411 dst.v.reg = dst_r; 412 Inst in = make_inst(caller, src.kind == OPK_IMM ? IR_LOAD_IMM : IR_COPY, 413 call->loc); 414 in.type = p->type; 415 in.def = (Val)dst_r; 416 in.opnds = 417 arena_array(caller->arena, Operand, src.kind == OPK_IMM ? 1u : 2u); 418 in.opnds[0] = dst; 419 in.nopnds = src.kind == OPK_IMM ? 1u : 2u; 420 if (src.kind == OPK_IMM) { 421 in.extra.imm = src.v.imm; 422 } else { 423 in.opnds[1] = src; 424 } 425 instvec_push(out, &in); 426 } else { 427 FrameSlot dst_s = map_slot(m, p->storage.v.frame_slot); 428 Inst in = make_inst(caller, IR_STORE, call->loc); 429 in.opnds = arena_array(caller->arena, Operand, 2); 430 in.opnds[0] = local_operand(dst_s, p->type); 431 in.opnds[1] = src; 432 in.nopnds = 2; 433 in.extra.mem = param_mem(p, dst_s); 434 instvec_push(out, &in); 435 } 436 } 437 return 1; 438 } 439 440 static Inst clone_inst(InlineMap* m, const Inst* src) { 441 Func* caller = m->caller; 442 Inst dst = *src; 443 dst.id = ir_inst_id_new(caller); 444 dst.def = src->def != VAL_NONE ? (Val)map_preg(m, (PReg)src->def) : VAL_NONE; 445 if (src->ndefs) { 446 dst.defs = arena_array(caller->arena, Val, src->ndefs); 447 for (u32 i = 0; i < src->ndefs; ++i) { 448 dst.defs[i] = src->defs[i] != VAL_NONE 449 ? (Val)map_preg(m, (PReg)src->defs[i]) 450 : VAL_NONE; 451 } 452 } 453 if (src->nopnds) { 454 dst.opnds = arena_array(caller->arena, Operand, src->nopnds); 455 for (u32 i = 0; i < src->nopnds; ++i) 456 dst.opnds[i] = map_operand(m, src->opnds[i]); 457 } 458 if ((IROp)dst.op == IR_LOAD || (IROp)dst.op == IR_STORE) { 459 map_mem(m, &dst.extra.mem); 460 } 461 return dst; 462 } 463 464 static void clone_block_succs(InlineMap* m, Block* dst, const Block* src) { 465 ir_block_set_nsucc(m->caller, dst->id, src->nsucc); 466 for (u32 s = 0; s < src->nsucc; ++s) 467 dst->succ[s] = map_block(m, src->succ[s]); 468 } 469 470 static int append_return_materialization(InstVec* out, InlineMap* m, 471 const Inst* call, const Inst* ret) { 472 IRCallAux* call_aux = (IRCallAux*)call->extra.aux; 473 IRRetAux* ret_aux = (IRRetAux*)ret->extra.aux; 474 Func* caller = m->caller; 475 if (!call_aux) return 0; 476 if (!ret_aux || !ret_aux->present) return 1; 477 if (ret_aux->val.nparts != 0 || call_aux->desc.ret.nparts != 0) return 0; 478 Operand dst = call_aux->desc.ret.storage; 479 Operand src = ret_aux->val.storage; 480 if (dst.kind == OPK_IMM) return 1; 481 if (dst.kind != OPK_REG) return 0; 482 src = map_operand(m, src); 483 if (src.kind != OPK_REG && src.kind != OPK_IMM) return 0; 484 485 Inst in = 486 make_inst(caller, src.kind == OPK_IMM ? IR_LOAD_IMM : IR_COPY, call->loc); 487 in.type = dst.type; 488 in.def = (Val)dst.v.reg; 489 in.opnds = arena_array(caller->arena, Operand, src.kind == OPK_IMM ? 1u : 2u); 490 in.opnds[0] = dst; 491 in.nopnds = src.kind == OPK_IMM ? 1u : 2u; 492 if (src.kind == OPK_IMM) { 493 in.extra.imm = src.v.imm; 494 } else { 495 in.opnds[1] = src; 496 } 497 instvec_push(out, &in); 498 return 1; 499 } 500 501 static Inst make_branch(Func* f, SrcLoc loc) { 502 return make_inst(f, IR_BR, loc); 503 } 504 505 static void emit_order_push_unique(u32* out, u32* nout, u32 b) { 506 for (u32 i = 0; i < *nout; ++i) 507 if (out[i] == b) return; 508 out[(*nout)++] = b; 509 } 510 511 static void inline_rebuild_emit_order(Func* caller, u32 anchor, InlineMap* m, 512 u32 cont) { 513 u32 cap = 514 caller->emit_order_n + m->callee->emit_order_n + m->callee->nblocks + 2u; 515 u32* order = arena_array(caller->arena, u32, cap ? cap : 1u); 516 u32 norder = 0; 517 int inserted = 0; 518 for (u32 i = 0; i < caller->emit_order_n; ++i) { 519 u32 b = caller->emit_order[i]; 520 emit_order_push_unique(order, &norder, b); 521 if (b != anchor) continue; 522 for (u32 j = 0; j < m->callee->emit_order_n; ++j) 523 emit_order_push_unique(order, &norder, 524 map_block(m, m->callee->emit_order[j])); 525 for (u32 cb = 0; cb < m->callee->nblocks; ++cb) 526 emit_order_push_unique(order, &norder, map_block(m, cb)); 527 emit_order_push_unique(order, &norder, cont); 528 inserted = 1; 529 } 530 if (!inserted) { 531 emit_order_push_unique(order, &norder, anchor); 532 for (u32 j = 0; j < m->callee->emit_order_n; ++j) 533 emit_order_push_unique(order, &norder, 534 map_block(m, m->callee->emit_order[j])); 535 for (u32 cb = 0; cb < m->callee->nblocks; ++cb) 536 emit_order_push_unique(order, &norder, map_block(m, cb)); 537 emit_order_push_unique(order, &norder, cont); 538 } 539 caller->emit_order = order; 540 caller->emit_order_n = norder; 541 caller->emit_order_cap = cap; 542 } 543 544 static int inline_rewrite_supported(Func* callee, const Inst* call) { 545 IRCallAux* call_aux = (IRCallAux*)call->extra.aux; 546 if (!call_aux || call_aux->desc.nargs != callee->nparams) return 0; 547 for (u32 i = 0; i < callee->nparams; ++i) { 548 const CGABIValue* av = &call_aux->desc.args[i]; 549 if (av->nparts != 0) return 0; 550 if (av->storage.kind != OPK_REG && av->storage.kind != OPK_IMM) return 0; 551 } 552 553 for (u32 b = 0; b < callee->nblocks; ++b) { 554 Block* bl = &callee->blocks[b]; 555 for (u32 i = 0; i < bl->ninsts; ++i) { 556 Inst* in = &bl->insts[i]; 557 if ((IROp)in->op != IR_RET) continue; 558 IRRetAux* ret_aux = (IRRetAux*)in->extra.aux; 559 if (!ret_aux || !ret_aux->present) continue; 560 if (ret_aux->val.nparts != 0 || call_aux->desc.ret.nparts != 0) return 0; 561 if (call_aux->desc.ret.storage.kind == OPK_IMM) continue; 562 if (call_aux->desc.ret.storage.kind != OPK_REG) return 0; 563 if (ret_aux->val.storage.kind != OPK_REG && 564 ret_aux->val.storage.kind != OPK_IMM) 565 return 0; 566 } 567 } 568 return 1; 569 } 570 571 static int inline_call_site(Func* caller, u32 block_idx, u32 inst_idx, 572 Func* callee) { 573 Block* old_bl = &caller->blocks[block_idx]; 574 Inst* old_insts = old_bl->insts; 575 u32 old_ninsts = old_bl->ninsts; 576 u32 old_nsucc = old_bl->nsucc; 577 u32* old_succ = arena_array(caller->arena, u32, old_nsucc ? old_nsucc : 1u); 578 for (u32 s = 0; s < old_nsucc; ++s) old_succ[s] = old_bl->succ[s]; 579 Inst call = old_insts[inst_idx]; 580 InlineMap map; 581 if (!build_inline_map(&map, caller, callee)) return 0; 582 u32 cont = ir_block_new(caller); 583 584 InstVec pre; 585 memset(&pre, 0, sizeof pre); 586 pre.f = caller; 587 for (u32 i = 0; i < inst_idx; ++i) instvec_push(&pre, &old_insts[i]); 588 if (!append_param_materialization(&pre, &map, &call)) return 0; 589 Inst br = make_branch(caller, call.loc); 590 instvec_push(&pre, &br); 591 592 Block* pre_bl = &caller->blocks[block_idx]; 593 pre_bl->insts = pre.v; 594 pre_bl->ninsts = pre.n; 595 pre_bl->cap = pre.cap; 596 ir_block_set_nsucc(caller, block_idx, 1); 597 pre_bl = &caller->blocks[block_idx]; 598 pre_bl->succ[0] = map_block(&map, callee->entry); 599 600 Block* cont_bl = &caller->blocks[cont]; 601 InstVec cont_out; 602 memset(&cont_out, 0, sizeof cont_out); 603 cont_out.f = caller; 604 for (u32 i = inst_idx + 1u; i < old_ninsts; ++i) 605 instvec_push(&cont_out, &old_insts[i]); 606 cont_bl->insts = cont_out.v; 607 cont_bl->ninsts = cont_out.n; 608 cont_bl->cap = cont_out.cap; 609 ir_block_set_nsucc(caller, cont, old_nsucc); 610 cont_bl = &caller->blocks[cont]; 611 for (u32 s = 0; s < old_nsucc; ++s) cont_bl->succ[s] = old_succ[s]; 612 613 for (u32 b = 0; b < callee->nblocks; ++b) { 614 Block* src_bl = &callee->blocks[b]; 615 u32 dst_b = map_block(&map, b); 616 Block* dst_bl = &caller->blocks[dst_b]; 617 InstVec body; 618 memset(&body, 0, sizeof body); 619 body.f = caller; 620 for (u32 i = 0; i < src_bl->ninsts; ++i) { 621 Inst* src = &src_bl->insts[i]; 622 switch ((IROp)src->op) { 623 case IR_NOP: 624 case IR_PARAM_DECL: 625 break; 626 case IR_RET: { 627 if (!append_return_materialization(&body, &map, &call, src)) return 0; 628 Inst ret_br = make_branch(caller, src->loc); 629 instvec_push(&body, &ret_br); 630 break; 631 } 632 default: { 633 Inst cloned = clone_inst(&map, src); 634 instvec_push(&body, &cloned); 635 break; 636 } 637 } 638 } 639 dst_bl = &caller->blocks[dst_b]; 640 dst_bl->insts = body.v; 641 dst_bl->ninsts = body.n; 642 dst_bl->cap = body.cap; 643 if (body.n && (IROp)body.v[body.n - 1u].op == IR_BR && src_bl->ninsts && 644 (IROp)src_bl->insts[src_bl->ninsts - 1u].op == IR_RET) { 645 ir_block_set_nsucc(caller, dst_b, 1); 646 caller->blocks[dst_b].succ[0] = cont; 647 } else { 648 clone_block_succs(&map, &caller->blocks[dst_b], src_bl); 649 } 650 } 651 652 inline_rebuild_emit_order(caller, block_idx, &map, cont); 653 opt_analysis_invalidate( 654 caller, OPT_ANALYSIS_DEF_USE | OPT_ANALYSIS_DOM | OPT_ANALYSIS_LOOP); 655 return 1; 656 } 657 658 static int caller_growth_ok(FuncSet* fs, Func* caller, const u32* base_cost, 659 u32 callee_cost, KitCgInlinePolicy policy) { 660 if (policy == KIT_CG_INLINE_ALWAYS) return 1; 661 int idx = funcset_index(fs, caller); 662 u32 base = idx >= 0 ? base_cost[idx] : func_inline_cost(caller); 663 u32 growth_limit = base / 4u; 664 if (growth_limit < INLINE_NORMAL_COST_LIMIT) 665 growth_limit = INLINE_NORMAL_COST_LIMIT; 666 if (policy == KIT_CG_INLINE_HINT) { 667 growth_limit *= 2u; 668 if (growth_limit < INLINE_HINT_COST_LIMIT) 669 growth_limit = INLINE_HINT_COST_LIMIT; 670 if (growth_limit > INLINE_HINT_ABS_GROWTH_LIMIT) 671 growth_limit = INLINE_HINT_ABS_GROWTH_LIMIT; 672 } else if (growth_limit > INLINE_ABS_GROWTH_LIMIT) { 673 growth_limit = INLINE_ABS_GROWTH_LIMIT; 674 } 675 return func_inline_cost(caller) + callee_cost <= base + growth_limit; 676 } 677 678 /* O1.md W4: back off when the estimated post-inline live-set would sit past the 679 * pressure cap (see INLINE_PRESSURE_CAP). Cheap and linear — one read of the two 680 * functions' pseudo-register counts, no analysis. ALWAYS bypasses, matching the 681 * cost/growth gates: an explicit always_inline request wins over the heuristic. 682 * The callee's pregs are an upper bound on the bodies it adds (param/return 683 * materialization reuses some), so the estimate never *under*-counts pressure. */ 684 static int caller_pressure_ok(const Func* caller, const Func* callee, 685 KitCgInlinePolicy policy) { 686 if (policy == KIT_CG_INLINE_ALWAYS) return 1; 687 return (u64)caller->npregs + (u64)callee->npregs < INLINE_PRESSURE_CAP; 688 } 689 690 static int try_inline_call(FuncSet* fs, Func* caller, u32 b, u32 i, 691 const u32* base_cost) { 692 Inst* in = &caller->blocks[b].insts[i]; 693 Func* callee = direct_callee(fs, in); 694 u32 cost = 0; 695 KitCgInlinePolicy policy; 696 if (!callee) return 0; 697 policy = effective_inline_policy(in, callee); 698 metrics_count(caller->c, "opt.inline.candidates", 1); 699 if (policy == KIT_CG_INLINE_NEVER) { 700 metrics_count(caller->c, "opt.inline.refuse_policy", 1); 701 return 0; 702 } 703 if (recursive_or_scc(fs, caller, callee)) { 704 metrics_count(caller->c, "opt.inline.refuse_scc", 1); 705 return 0; 706 } 707 if (!callee_inline_shape(callee, policy, &cost)) { 708 metrics_count(caller->c, "opt.inline.refuse_shape", 1); 709 return 0; 710 } 711 if (!caller_growth_ok(fs, caller, base_cost, cost, policy)) { 712 metrics_count(caller->c, "opt.inline.refuse_growth", 1); 713 return 0; 714 } 715 if (!caller_pressure_ok(caller, callee, policy)) { 716 /* Folded into the growth-refusal bucket (no schema change): both are 717 * "refuse because the caller would get too big". */ 718 metrics_count(caller->c, "opt.inline.refuse_growth", 1); 719 return 0; 720 } 721 if (!inline_rewrite_supported(callee, in)) { 722 metrics_count(caller->c, "opt.inline.refuse_rewrite_shape", 1); 723 return 0; 724 } 725 if (!inline_call_site(caller, b, i, callee)) { 726 metrics_count(caller->c, "opt.inline.refuse_rewrite", 1); 727 return 0; 728 } 729 metrics_count(caller->c, "opt.inline.inlined", 1); 730 return 1; 731 } 732 733 static void inline_order_visit(InlineOrderCtx* ctx, Func* f) { 734 int idx = funcset_index(ctx->fs, f); 735 if (idx < 0 || ctx->done[idx]) return; 736 if (ctx->temp[idx]) return; 737 ctx->temp[idx] = 1; 738 for (u32 b = 0; b < f->nblocks; ++b) { 739 Block* bl = &f->blocks[b]; 740 for (u32 i = 0; i < bl->ninsts; ++i) { 741 Func* callee = direct_callee(ctx->fs, &bl->insts[i]); 742 if (callee) inline_order_visit(ctx, callee); 743 } 744 } 745 ctx->temp[idx] = 0; 746 ctx->done[idx] = 1; 747 ctx->order[ctx->norder++] = f; 748 } 749 750 /* Count the direct in-set callees of f (CSR degree / fill helper). */ 751 static u32 inline_collect_callees(FuncSet* fs, Func* f, u32* out, u32 base) { 752 u32 n = 0; 753 if (!f) return 0; 754 for (u32 b = 0; b < f->nblocks; ++b) { 755 Block* bl = &f->blocks[b]; 756 for (u32 k = 0; k < bl->ninsts; ++k) { 757 Func* c = direct_callee(fs, &bl->insts[k]); 758 int ci = c ? funcset_index(fs, c) : -1; 759 if (ci < 0) continue; 760 if (out) out[base + n] = (u32)ci; 761 ++n; 762 } 763 } 764 return n; 765 } 766 767 /* Build FuncSet.index: a symbol->index map and per-function SCC ids over the 768 * direct-call graph, so funcset_find and the recursion/SCC gate are O(1). The 769 * SCC partition is invariant under the inlining the pass performs (it only adds 770 * caller->X edges where X already sat strictly below the caller in the 771 * condensation DAG, and only removes cross-SCC call edges), so one build serves 772 * every fixpoint iteration. Tarjan's algorithm, iterative to bound stack depth 773 * on deep call chains. O(V + E). */ 774 static void inline_index_build(FuncSet* fs, InlineIndex* idx) { 775 u32 n = fs->nfuncs; 776 u32 *deg, *off, *edges, *comp, *st_node, *st_ei, *low; 777 i32* dfsnum; 778 u8* onstack; 779 u32 nedges, comp_top = 0, st_top = 0, counter = 0, ncomp = 0; 780 memset(idx, 0, sizeof *idx); 781 InlineSymMap_init_cap(&idx->sym2idx, fs->c->ctx->heap, 0); 782 for (u32 i = 0; i < n; ++i) 783 if (fs->funcs[i] && fs->funcs[i]->name != OBJ_SYM_NONE) 784 (void)InlineSymMap_set(&idx->sym2idx, fs->funcs[i]->name, i); 785 fs->index = idx; /* enables the O(1) funcset_find/index used just below */ 786 idx->nfuncs = n; 787 if (n == 0) return; 788 789 deg = arena_zarray(fs->arena, u32, n); 790 for (u32 i = 0; i < n; ++i) deg[i] = inline_collect_callees(fs, fs->funcs[i], NULL, 0); 791 off = arena_array(fs->arena, u32, n + 1u); 792 off[0] = 0; 793 for (u32 i = 0; i < n; ++i) off[i + 1u] = off[i] + deg[i]; 794 nedges = off[n]; 795 edges = arena_array(fs->arena, u32, nedges ? nedges : 1u); 796 for (u32 i = 0; i < n; ++i) 797 (void)inline_collect_callees(fs, fs->funcs[i], edges, off[i]); 798 799 idx->scc = arena_array(fs->arena, u32, n); 800 dfsnum = arena_array(fs->arena, i32, n); 801 low = arena_array(fs->arena, u32, n); 802 onstack = arena_zarray(fs->arena, u8, n); 803 comp = arena_array(fs->arena, u32, n); 804 st_node = arena_array(fs->arena, u32, n); 805 st_ei = arena_array(fs->arena, u32, n); 806 for (u32 i = 0; i < n; ++i) { 807 dfsnum[i] = -1; 808 idx->scc[i] = 0; 809 } 810 for (u32 root = 0; root < n; ++root) { 811 if (dfsnum[root] != -1) continue; 812 st_node[st_top] = root; 813 st_ei[st_top] = 0; 814 ++st_top; 815 while (st_top) { 816 u32 v = st_node[st_top - 1u]; 817 u32 ei = st_ei[st_top - 1u]; 818 if (ei == 0) { /* pre-order visit */ 819 dfsnum[v] = (i32)counter; 820 low[v] = counter; 821 ++counter; 822 comp[comp_top++] = v; 823 onstack[v] = 1; 824 } 825 if (ei < deg[v]) { 826 u32 w = edges[off[v] + ei]; 827 st_ei[st_top - 1u] = ei + 1u; 828 if (dfsnum[w] == -1) { /* tree edge: descend */ 829 st_node[st_top] = w; 830 st_ei[st_top] = 0; 831 ++st_top; 832 } else if (onstack[w] && (u32)dfsnum[w] < low[v]) { 833 low[v] = (u32)dfsnum[w]; /* back/cross edge to a live ancestor */ 834 } 835 } else { /* post-order: v's subtree done */ 836 if (low[v] == (u32)dfsnum[v]) { 837 for (;;) { 838 u32 w = comp[--comp_top]; 839 onstack[w] = 0; 840 idx->scc[w] = ncomp; 841 if (w == v) break; 842 } 843 ++ncomp; 844 } 845 --st_top; 846 if (st_top) { 847 u32 p = st_node[st_top - 1u]; 848 if (low[v] < low[p]) low[p] = low[v]; 849 } 850 } 851 } 852 } 853 } 854 855 static void inline_index_fini(FuncSet* fs, InlineIndex* idx) { 856 InlineSymMap_fini(&idx->sym2idx); 857 fs->index = NULL; 858 } 859 860 void opt_inline(FuncSet* fs, int max_iters) { 861 if (!fs || fs->nfuncs == 0 || max_iters <= 0) return; 862 if (max_iters > 4) max_iters = 4; 863 InlineIndex idx; 864 inline_index_build(fs, &idx); 865 u32* base_cost = arena_array(fs->arena, u32, fs->nfuncs); 866 for (u32 i = 0; i < fs->nfuncs; ++i) 867 base_cost[i] = func_inline_cost(fs->funcs[i]); 868 for (int iter = 0; iter < max_iters; ++iter) { 869 int changed = 0; 870 InlineOrderCtx ctx; 871 memset(&ctx, 0, sizeof ctx); 872 ctx.fs = fs; 873 ctx.temp = arena_zarray(fs->arena, u8, fs->nfuncs); 874 ctx.done = arena_zarray(fs->arena, u8, fs->nfuncs); 875 ctx.order = arena_array(fs->arena, Func*, fs->nfuncs); 876 for (u32 fidx = 0; fidx < fs->nfuncs; ++fidx) 877 inline_order_visit(&ctx, fs->funcs[fidx]); 878 879 for (u32 fidx = 0; fidx < ctx.norder; ++fidx) { 880 Func* caller = ctx.order[fidx]; 881 if (!caller || caller->opt_reg_ssa || caller->opt_rewritten) continue; 882 for (u32 b = 0; b < caller->nblocks; ++b) { 883 Block* bl = &caller->blocks[b]; 884 for (u32 i = 0; i < bl->ninsts; ++i) { 885 if ((IROp)bl->insts[i].op != IR_CALL) continue; 886 if (try_inline_call(fs, caller, b, i, base_cost)) { 887 changed = 1; 888 bl = &caller->blocks[b]; 889 } 890 } 891 } 892 } 893 if (!changed) break; 894 } 895 inline_index_fini(fs, &idx); 896 } 897 898 /* Streaming single-caller variant for the O1 pipeline. Same gates as 899 * try_inline_call, minus the whole-program growth check (which needs a 900 * base_cost array the streaming path lacks), plus the tiny cost cap. */ 901 static int try_tiny_inline_call(FuncSet* fs, Func* caller, u32 b, u32 i) { 902 Inst* in = &caller->blocks[b].insts[i]; 903 Func* callee = direct_callee(fs, in); 904 u32 cost = 0; 905 KitCgInlinePolicy policy; 906 if (!callee) return 0; 907 policy = effective_inline_policy(in, callee); 908 metrics_count(caller->c, "opt.tiny_inline.candidates", 1); 909 if (policy == KIT_CG_INLINE_NEVER) { 910 metrics_count(caller->c, "opt.tiny_inline.refuse_policy", 1); 911 return 0; 912 } 913 if (recursive_or_scc(fs, caller, callee)) { 914 metrics_count(caller->c, "opt.tiny_inline.refuse_scc", 1); 915 return 0; 916 } 917 if (!callee_inline_shape(callee, policy, &cost)) { 918 metrics_count(caller->c, "opt.tiny_inline.refuse_shape", 1); 919 return 0; 920 } 921 if (policy != KIT_CG_INLINE_ALWAYS && cost > INLINE_TINY_COST_LIMIT) { 922 metrics_count(caller->c, "opt.tiny_inline.refuse_budget", 1); 923 return 0; 924 } 925 /* No pressure cap here: the streaming tiny-inliner only fuses callees of cost 926 * <= INLINE_TINY_COST_LIMIT, which add a handful of pregs at most, so a tiny 927 * fuse never meaningfully grows the live-set. The W4 pressure cap targets the 928 * whole-program inliner (try_inline_call), which is where many small bodies 929 * accrete into one caller; applying it here measurably *hurt* (it blocked 930 * beneficial tiny fuses into large-but-not-pressured callers). */ 931 if (!inline_rewrite_supported(callee, in)) { 932 metrics_count(caller->c, "opt.tiny_inline.refuse_rewrite_shape", 1); 933 return 0; 934 } 935 if (!inline_call_site(caller, b, i, callee)) { 936 metrics_count(caller->c, "opt.tiny_inline.refuse_rewrite", 1); 937 return 0; 938 } 939 metrics_count(caller->c, "opt.tiny_inline.inlined", 1); 940 return 1; 941 } 942 943 int opt_try_tiny_inline(Func* caller, OptInlineCalleeLookup lookup, void* ctx) { 944 int total = 0; 945 if (!caller || !lookup || caller->opt_reg_ssa || caller->opt_rewritten) 946 return 0; 947 for (u32 pass = 0; pass < TINY_INLINE_MAX_PASSES; ++pass) { 948 int changed = 0; 949 for (u32 b = 0; b < caller->nblocks && !changed; ++b) { 950 Block* bl = &caller->blocks[b]; 951 for (u32 i = 0; i < bl->ninsts; ++i) { 952 Inst* in = &bl->insts[i]; 953 if ((IROp)in->op != IR_CALL) continue; 954 IRCallAux* aux = (IRCallAux*)in->extra.aux; 955 if (!aux || aux->desc.callee.kind != OPK_GLOBAL) continue; 956 Func* callee = lookup(ctx, aux->desc.callee.v.global.sym); 957 if (!callee) continue; 958 /* Ad-hoc 2-element FuncSet so the existing gates (direct_callee, 959 * recursive_or_scc) resolve the callee by symbol. */ 960 Func* funcs[2] = {caller, callee}; 961 FuncSet fs; 962 memset(&fs, 0, sizeof fs); 963 fs.c = caller->c; 964 fs.arena = caller->arena; 965 fs.funcs = funcs; 966 fs.nfuncs = (caller == callee) ? 1u : 2u; 967 fs.cap = fs.nfuncs; 968 if (try_tiny_inline_call(&fs, caller, b, i)) { 969 ++total; 970 changed = 1; /* indices invalidated by the split; restart scan */ 971 break; 972 } 973 } 974 } 975 if (!changed) break; 976 } 977 return total; 978 }