pass_live.c (29410B)
1 #include <stdlib.h> 2 #include <string.h> 3 4 #include "core/arena.h" 5 #include "core/slice.h" 6 #include "core/strbuf.h" 7 #include "opt/opt.h" 8 #include "opt/opt_internal.h" 9 10 static u32 opt_bit_words(u32 nregs) { return (nregs + 63u) / 64u; } 11 12 static void opt_bitset_init(Arena* arena, OptBitset* bs, u32 nwords) { 13 memset(bs, 0, sizeof *bs); 14 bs->arena = arena; 15 bs->nwords = nwords; 16 bs->words = arena_zarray(arena, u64, nwords ? nwords : 1u); 17 } 18 19 static int opt_bitset_grow(OptBitset* bs, u32 need_words) { 20 if (!bs || need_words <= bs->nwords) return 1; 21 if (!bs->arena) return 0; 22 u32 nwords = bs->nwords ? bs->nwords : 1u; 23 while (nwords < need_words) nwords *= 2u; 24 u64* words = arena_zarray(bs->arena, u64, nwords); 25 if (bs->words && bs->nwords) 26 memcpy(words, bs->words, sizeof(words[0]) * bs->nwords); 27 bs->words = words; 28 bs->nwords = nwords; 29 return 1; 30 } 31 32 static void opt_bitset_trim(OptBitset* bs) { 33 u32 n = bs->active_words; 34 while (n && bs->words[n - 1u] == 0) --n; 35 bs->active_words = n; 36 } 37 38 void opt_bitset_clear(OptBitset* bs) { 39 if (!bs || !bs->words) return; 40 for (u32 i = 0; i < bs->active_words; ++i) bs->words[i] = 0; 41 bs->active_words = 0; 42 } 43 44 void opt_bitset_set(OptBitset* bs, PReg r) { 45 if (!bs) return; 46 u32 w = r / 64u; 47 if (w >= bs->nwords && !opt_bitset_grow(bs, w + 1u)) return; 48 bs->words[w] |= 1ull << (r % 64u); 49 if (bs->active_words <= w) bs->active_words = w + 1u; 50 } 51 52 void opt_bitset_clear_bit(OptBitset* bs, PReg r) { 53 if (!bs || !bs->words) return; 54 u32 w = r / 64u; 55 if (w >= bs->active_words) return; 56 bs->words[w] &= ~(1ull << (r % 64u)); 57 if (w + 1u == bs->active_words && bs->words[w] == 0) opt_bitset_trim(bs); 58 } 59 60 int opt_bitset_has(const OptBitset* bs, PReg r) { 61 if (!bs || !bs->words) return 0; 62 u32 w = r / 64u; 63 if (w >= bs->active_words) return 0; 64 return (bs->words[w] & (1ull << (r % 64u))) != 0; 65 } 66 67 int opt_bitset_copy(OptBitset* dst, const OptBitset* src) { 68 int changed = 0; 69 u32 n; 70 u32 old_active; 71 if (!dst || !src || !src->words) return 0; 72 if (src->active_words > dst->nwords && 73 !opt_bitset_grow(dst, src->active_words)) 74 return 0; 75 old_active = dst->active_words; 76 n = src->active_words; 77 for (u32 i = 0; i < n; ++i) { 78 changed |= dst->words[i] != src->words[i]; 79 dst->words[i] = src->words[i]; 80 } 81 for (u32 i = n; i < old_active; ++i) { 82 changed |= dst->words[i] != 0; 83 dst->words[i] = 0; 84 } 85 dst->active_words = n; 86 return changed; 87 } 88 89 int opt_bitset_union(OptBitset* dst, const OptBitset* src) { 90 int changed = 0; 91 u32 n; 92 u32 active; 93 if (!dst || !src || !src->words) return 0; 94 if (src->active_words > dst->nwords && 95 !opt_bitset_grow(dst, src->active_words)) 96 return 0; 97 n = src->active_words; 98 active = dst->active_words; 99 for (u32 i = 0; i < n; ++i) { 100 u64 old = dst->words[i]; 101 dst->words[i] |= src->words[i]; 102 changed |= dst->words[i] != old; 103 if (dst->words[i] && active <= i) active = i + 1u; 104 } 105 dst->active_words = active; 106 return changed; 107 } 108 109 int opt_bitset_union_and_not(OptBitset* dst, const OptBitset* src, 110 const OptBitset* not_bits) { 111 int changed = 0; 112 u32 n; 113 u32 active; 114 if (!dst || !src || !src->words) return 0; 115 if (src->active_words > dst->nwords && 116 !opt_bitset_grow(dst, src->active_words)) 117 return 0; 118 n = src->active_words; 119 active = dst->active_words; 120 for (u32 i = 0; i < n; ++i) { 121 u64 mask = 122 (not_bits && i < not_bits->active_words) ? not_bits->words[i] : 0; 123 u64 old = dst->words[i]; 124 dst->words[i] |= src->words[i] & ~mask; 125 changed |= dst->words[i] != old; 126 if (dst->words[i] && active <= i) active = i + 1u; 127 } 128 dst->active_words = active; 129 return changed; 130 } 131 132 void opt_bitset_iter_set(const OptBitset* bs, OptBitsetIterFn fn, void* arg) { 133 if (!bs || !bs->words || !fn) return; 134 for (u32 w = 0; w < bs->active_words; ++w) { 135 u64 bits = bs->words[w]; 136 while (bits) { 137 u32 bit = (u32)__builtin_ctzll(bits); 138 fn(w * 64u + bit, arg); 139 bits &= bits - 1u; 140 } 141 } 142 } 143 144 typedef struct LiveUseDefCtx { 145 OptBitset* use; 146 OptBitset* def; 147 } LiveUseDefCtx; 148 149 static void live_collect_use_def(Func* f, Inst* in, Operand* op, int is_def, 150 void* arg) { 151 (void)in; 152 LiveUseDefCtx* c = (LiveUseDefCtx*)arg; 153 if (op->kind != OPK_REG) return; 154 PReg r = (PReg)op->v.reg; 155 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(f)) return; 156 if (is_def) { 157 opt_bitset_set(c->def, r); 158 } else if (!opt_bitset_has(c->def, r)) { 159 opt_bitset_set(c->use, r); 160 } 161 } 162 163 static void live_count_bit(PReg r, void* arg) { 164 (void)r; 165 ++*(u64*)arg; 166 } 167 168 static u64 live_count_set_bits(const OptBitset* bs) { 169 u64 n = 0; 170 opt_bitset_iter_set(bs, live_count_bit, &n); 171 return n; 172 } 173 174 static void live_metric_clear(OptLiveInfo* live, OptBitset* bs) { 175 u32 touched = bs ? bs->active_words : 0; 176 if (live) { 177 u64 old = live->bitset_words_touched; 178 live->bitset_words_touched = old + touched; 179 } 180 opt_bitset_clear(bs); 181 } 182 183 static int live_metric_copy(OptLiveInfo* live, OptBitset* dst, 184 const OptBitset* src) { 185 u32 n = 0; 186 if (dst && src) { 187 n = src->active_words > dst->active_words ? src->active_words 188 : dst->active_words; 189 } 190 if (live) live->bitset_words_touched += n; 191 return opt_bitset_copy(dst, src); 192 } 193 194 static int live_metric_union(OptLiveInfo* live, OptBitset* dst, 195 const OptBitset* src) { 196 u32 n = 0; 197 if (dst && src) n = src->active_words; 198 if (live) live->bitset_words_touched += n; 199 return opt_bitset_union(dst, src); 200 } 201 202 static int live_metric_union_and_not(OptLiveInfo* live, OptBitset* dst, 203 const OptBitset* src, 204 const OptBitset* not_bits) { 205 u32 n = 0; 206 (void)not_bits; 207 if (dst && src) n = src->active_words; 208 if (live) live->bitset_words_touched += n; 209 return opt_bitset_union_and_not(dst, src, not_bits); 210 } 211 212 static void live_recompute_metrics(OptLiveInfo* live) { 213 live->active_words = 0; 214 live->block_bytes = 0; 215 live->set_bit_scans = 0; 216 for (u32 b = 0; b < live->f->nblocks; ++b) { 217 OptBlockLive* bl = &live->blocks[b]; 218 live->active_words += bl->live_in.active_words; 219 live->active_words += bl->live_out.active_words; 220 live->active_words += bl->live_use.active_words; 221 live->active_words += bl->live_def.active_words; 222 live->set_bit_scans += live_count_set_bits(&bl->live_in); 223 live->set_bit_scans += live_count_set_bits(&bl->live_out); 224 live->set_bit_scans += live_count_set_bits(&bl->live_use); 225 live->set_bit_scans += live_count_set_bits(&bl->live_def); 226 } 227 live->block_bytes = live->active_words * (u64)sizeof(u64); 228 } 229 230 static void live_worklist_push(u32* worklist, u8* queued, u32* n, u32 b) { 231 if (queued[b]) return; 232 queued[b] = 1; 233 worklist[(*n)++] = b; 234 } 235 236 void opt_live_blocks(Func* f, OptLiveInfo* live) { 237 memset(live, 0, sizeof *live); 238 live->arena = f->arena; 239 live->f = f; 240 live->words = opt_bit_words(opt_reg_count(f)); 241 f->opt_live_words = (u16)live->words; 242 live->blocks = 243 arena_zarray(f->arena, OptBlockLive, f->nblocks ? f->nblocks : 1u); 244 245 for (u32 b = 0; b < f->nblocks; ++b) { 246 Block* bl = &f->blocks[b]; 247 OptBlockLive* lb = &live->blocks[b]; 248 opt_bitset_init(f->arena, &lb->live_in, 0); 249 opt_bitset_init(f->arena, &lb->live_out, 0); 250 opt_bitset_init(f->arena, &lb->live_use, 0); 251 opt_bitset_init(f->arena, &lb->live_def, 0); 252 253 LiveUseDefCtx ctx; 254 ctx.use = &lb->live_use; 255 ctx.def = &lb->live_def; 256 for (u32 i = 0; i < bl->ninsts; ++i) 257 opt_walk_inst_operands(f, &bl->insts[i], live_collect_use_def, &ctx); 258 } 259 260 OptBitset new_out; 261 OptBitset tmp; 262 opt_bitset_init(f->arena, &new_out, 0); 263 opt_bitset_init(f->arena, &tmp, 0); 264 265 u32* worklist = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u); 266 u8* queued = arena_zarray(f->arena, u8, f->nblocks ? f->nblocks : 1u); 267 u32 nwork = 0; 268 for (u32 bi = f->nblocks; bi > 0; --bi) 269 live_worklist_push(worklist, queued, &nwork, bi - 1u); 270 271 while (nwork) { 272 u32 b = worklist[--nwork]; 273 queued[b] = 0; 274 Block* bl = &f->blocks[b]; 275 OptBlockLive* lb = &live->blocks[b]; 276 ++live->dataflow_iterations; 277 ++live->dataflow_block_visits; 278 live_metric_clear(live, &new_out); 279 live_metric_clear(live, &tmp); 280 for (u32 s = 0; s < bl->nsucc; ++s) { 281 u32 t = bl->succ[s]; 282 if (t < f->nblocks) 283 live_metric_union(live, &new_out, &live->blocks[t].live_in); 284 } 285 live_metric_copy(live, &tmp, &lb->live_use); 286 live_metric_union_and_not(live, &tmp, &new_out, &lb->live_def); 287 (void)live_metric_copy(live, &lb->live_out, &new_out); 288 if (live_metric_copy(live, &lb->live_in, &tmp)) { 289 for (u32 p = 0; p < bl->npreds; ++p) { 290 u32 pred = bl->preds[p]; 291 if (pred < f->nblocks) 292 live_worklist_push(worklist, queued, &nwork, pred); 293 } 294 } 295 } 296 297 live_recompute_metrics(live); 298 } 299 300 static void dump_write(Writer* w, const char* s) { 301 kit_writer_write(w, s, slice_from_cstr(s).len); 302 } 303 304 static void dump_sb(Writer* w, const StrBuf* sb) { 305 kit_writer_write(w, strbuf_cstr(sb), strbuf_len(sb)); 306 } 307 308 static void dump_bit(PReg r, void* arg) { 309 Writer* w = (Writer*)arg; 310 char buf[32]; 311 StrBuf sb; 312 strbuf_init(&sb, buf, sizeof buf); 313 strbuf_puts(&sb, " r"); 314 strbuf_put_u64(&sb, (u64)(unsigned)r); 315 dump_sb(w, &sb); 316 } 317 318 static void dump_set(Writer* w, const char* name, const OptBitset* bs) { 319 dump_write(w, " "); 320 dump_write(w, name); 321 dump_write(w, ":"); 322 opt_bitset_iter_set(bs, dump_bit, w); 323 dump_write(w, "\n"); 324 } 325 326 void opt_live_dump_blocks(Func* f, const OptLiveInfo* live, Writer* w) { 327 (void)f; 328 if (!live || !w) return; 329 for (u32 b = 0; b < live->f->nblocks; ++b) { 330 char buf[64]; 331 StrBuf sb; 332 strbuf_init(&sb, buf, sizeof buf); 333 strbuf_puts(&sb, "block "); 334 strbuf_put_u64(&sb, (u64)(unsigned)b); 335 strbuf_putc(&sb, '\n'); 336 dump_sb(w, &sb); 337 dump_set(w, "use", &live->blocks[b].live_use); 338 dump_set(w, "def", &live->blocks[b].live_def); 339 dump_set(w, "in", &live->blocks[b].live_in); 340 dump_set(w, "out", &live->blocks[b].live_out); 341 } 342 } 343 344 typedef struct RangeBuildCtx { 345 Func* f; 346 OptLiveRangeSet* ranges; 347 u32* last_range_by_preg; 348 u32* open_end_by_preg; 349 u32* open_gen_by_preg; 350 u32 open_gen; 351 PReg* open_pregs; 352 u32 nopen_pregs; 353 u32 open_pregs_cap; 354 PReg* range_pregs; 355 u32 nrange_pregs; 356 u32 range_pregs_cap; 357 u32* raw_points; 358 u32 nraw_points; 359 u32 raw_points_cap; 360 } RangeBuildCtx; 361 362 typedef struct RangeInstRefs { 363 PReg* uses; 364 PReg* defs; 365 u32 nuses; 366 u32 ndefs; 367 u32 use_cap; 368 u32 def_cap; 369 u32* use_mark; 370 u32* def_mark; 371 u32 gen; 372 } RangeInstRefs; 373 374 typedef struct RangeLivePregs { 375 Func* f; 376 PReg* regs; 377 u32 nregs; 378 u32 cap; 379 u32* pos_by_preg; 380 } RangeLivePregs; 381 382 static void range_refs_init(Func* f, RangeInstRefs* refs) { 383 memset(refs, 0, sizeof *refs); 384 refs->use_mark = 385 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 386 refs->def_mark = 387 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 388 refs->gen = 1; 389 } 390 391 static void range_refs_reset(Func* f, RangeInstRefs* refs) { 392 refs->nuses = 0; 393 refs->ndefs = 0; 394 ++refs->gen; 395 if (refs->gen) return; 396 memset( 397 refs->use_mark, 0, 398 sizeof(refs->use_mark[0]) * (opt_reg_count(f) ? opt_reg_count(f) : 1u)); 399 memset( 400 refs->def_mark, 0, 401 sizeof(refs->def_mark[0]) * (opt_reg_count(f) ? opt_reg_count(f) : 1u)); 402 refs->gen = 1; 403 } 404 405 static void range_refs_push_use(Func* f, RangeInstRefs* refs, PReg r) { 406 if (refs->use_mark[r] == refs->gen) return; 407 refs->use_mark[r] = refs->gen; 408 if (refs->nuses == refs->use_cap) { 409 u32 ncap = refs->use_cap ? refs->use_cap * 2u : 8u; 410 PReg* nr = arena_array(f->arena, PReg, ncap); 411 if (refs->uses) memcpy(nr, refs->uses, sizeof(refs->uses[0]) * refs->nuses); 412 refs->uses = nr; 413 refs->use_cap = ncap; 414 } 415 refs->uses[refs->nuses++] = r; 416 } 417 418 static void range_refs_push_def(Func* f, RangeInstRefs* refs, PReg r) { 419 if (refs->def_mark[r] == refs->gen) return; 420 refs->def_mark[r] = refs->gen; 421 if (refs->ndefs == refs->def_cap) { 422 u32 ncap = refs->def_cap ? refs->def_cap * 2u : 4u; 423 PReg* nr = arena_array(f->arena, PReg, ncap); 424 if (refs->defs) memcpy(nr, refs->defs, sizeof(refs->defs[0]) * refs->ndefs); 425 refs->defs = nr; 426 refs->def_cap = ncap; 427 } 428 refs->defs[refs->ndefs++] = r; 429 } 430 431 static int range_refs_has_def(const RangeInstRefs* refs, PReg r) { 432 return refs->def_mark[r] == refs->gen; 433 } 434 435 static void range_live_pregs_init(Func* f, RangeLivePregs* live) { 436 memset(live, 0, sizeof *live); 437 live->f = f; 438 live->pos_by_preg = 439 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 440 } 441 442 static void range_live_pregs_clear(RangeLivePregs* live) { 443 for (u32 i = 0; i < live->nregs; ++i) live->pos_by_preg[live->regs[i]] = 0; 444 live->nregs = 0; 445 } 446 447 static void range_live_pregs_add(RangeLivePregs* live, PReg r) { 448 Func* f = live->f; 449 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(f)) return; 450 if (live->pos_by_preg[r]) return; 451 if (live->nregs == live->cap) { 452 u32 ncap = live->cap ? live->cap * 2u : 64u; 453 PReg* nr = arena_array(f->arena, PReg, ncap); 454 if (live->regs) memcpy(nr, live->regs, sizeof(live->regs[0]) * live->nregs); 455 live->regs = nr; 456 live->cap = ncap; 457 } 458 live->regs[live->nregs] = r; 459 live->pos_by_preg[r] = live->nregs + 1u; 460 ++live->nregs; 461 } 462 463 static void range_live_pregs_remove(RangeLivePregs* live, PReg r) { 464 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(live->f)) return; 465 u32 pos = live->pos_by_preg[r]; 466 if (!pos) return; 467 u32 idx = pos - 1u; 468 PReg last = live->regs[live->nregs - 1u]; 469 live->regs[idx] = last; 470 live->pos_by_preg[last] = idx + 1u; 471 live->pos_by_preg[r] = 0; 472 --live->nregs; 473 } 474 475 static void range_live_pregs_add_bit(PReg r, void* arg) { 476 range_live_pregs_add((RangeLivePregs*)arg, r); 477 } 478 479 static void range_collect_bits(Func* f, Inst* in, Operand* op, int is_def, 480 void* arg) { 481 (void)in; 482 RangeInstRefs* refs = (RangeInstRefs*)arg; 483 if (op->kind != OPK_REG) return; 484 PReg r = (PReg)op->v.reg; 485 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(f)) return; 486 if (is_def) 487 range_refs_push_def(f, refs, r); 488 else 489 range_refs_push_use(f, refs, r); 490 } 491 492 static void range_push_raw_point(RangeBuildCtx* c, u32 p) { 493 if (c->nraw_points == c->raw_points_cap) { 494 u32 ncap = c->raw_points_cap ? c->raw_points_cap * 2u : 64u; 495 u32* np = arena_array(c->f->arena, u32, ncap); 496 if (c->raw_points) 497 memcpy(np, c->raw_points, sizeof(c->raw_points[0]) * c->nraw_points); 498 c->raw_points = np; 499 c->raw_points_cap = ncap; 500 } 501 c->raw_points[c->nraw_points++] = p; 502 } 503 504 static void range_push_open_preg(RangeBuildCtx* c, PReg r) { 505 if (c->nopen_pregs == c->open_pregs_cap) { 506 u32 ncap = c->open_pregs_cap ? c->open_pregs_cap * 2u : 64u; 507 PReg* nr = arena_array(c->f->arena, PReg, ncap); 508 if (c->open_pregs) 509 memcpy(nr, c->open_pregs, sizeof(c->open_pregs[0]) * c->nopen_pregs); 510 c->open_pregs = nr; 511 c->open_pregs_cap = ncap; 512 } 513 c->open_pregs[c->nopen_pregs++] = r; 514 } 515 516 static void range_push_range_preg(RangeBuildCtx* c, PReg r) { 517 if (c->nrange_pregs == c->range_pregs_cap) { 518 u32 ncap = c->range_pregs_cap ? c->range_pregs_cap * 2u : 64u; 519 PReg* nr = arena_array(c->f->arena, PReg, ncap); 520 if (c->range_pregs) 521 memcpy(nr, c->range_pregs, sizeof(c->range_pregs[0]) * c->nrange_pregs); 522 c->range_pregs = nr; 523 c->range_pregs_cap = ncap; 524 } 525 c->range_pregs[c->nrange_pregs++] = r; 526 } 527 528 static void range_block_reset(RangeBuildCtx* c) { 529 c->nopen_pregs = 0; 530 ++c->open_gen; 531 if (c->open_gen) return; 532 memset(c->open_gen_by_preg, 0, 533 sizeof(c->open_gen_by_preg[0]) * 534 (opt_reg_count(c->f) ? opt_reg_count(c->f) : 1u)); 535 c->open_gen = 1; 536 } 537 538 static int range_is_open(const RangeBuildCtx* c, PReg r) { 539 return r < opt_reg_count(c->f) && c->open_gen_by_preg[r] == c->open_gen; 540 } 541 542 static u32 range_open_end(const RangeBuildCtx* c, PReg r) { 543 return range_is_open(c, r) ? c->open_end_by_preg[r] : OPT_RANGE_NONE; 544 } 545 546 static void range_set_open_end(RangeBuildCtx* c, PReg r, u32 end) { 547 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(c->f)) return; 548 if (!range_is_open(c, r)) { 549 c->open_gen_by_preg[r] = c->open_gen; 550 range_push_open_preg(c, r); 551 } 552 c->open_end_by_preg[r] = end; 553 } 554 555 static void range_close_open_end(RangeBuildCtx* c, PReg r) { 556 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(c->f)) return; 557 c->open_gen_by_preg[r] = 0; 558 } 559 560 static void range_append(RangeBuildCtx* c, PReg r, u32 start, u32 end, 561 u32 block, int whole_block) { 562 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(c->f)) return; 563 if (end <= start) end = start + 1u; 564 OptLiveRangeSet* ranges = c->ranges; 565 if (ranges->nranges == ranges->cap) { 566 u32 ncap = ranges->cap ? ranges->cap * 2u : 64u; 567 OptLiveRange* nr = arena_array(c->f->arena, OptLiveRange, ncap); 568 if (ranges->ranges) 569 memcpy(nr, ranges->ranges, sizeof(ranges->ranges[0]) * ranges->nranges); 570 ranges->ranges = nr; 571 ranges->cap = ncap; 572 } 573 u32 idx = ranges->nranges++; 574 OptLiveRange* lr = &ranges->ranges[idx]; 575 memset(lr, 0, sizeof *lr); 576 lr->preg = r; 577 lr->start = start; 578 lr->end = end; 579 lr->raw_start = start; 580 lr->raw_end = end; 581 lr->next = OPT_RANGE_NONE; 582 lr->block = block; 583 lr->whole_block = whole_block ? 1u : 0u; 584 if (ranges->first_range_by_preg[r] == OPT_RANGE_NONE) { 585 ranges->first_range_by_preg[r] = idx; 586 range_push_range_preg(c, r); 587 } else { 588 ranges->ranges[c->last_range_by_preg[r]].next = idx; 589 } 590 c->last_range_by_preg[r] = idx; 591 range_push_raw_point(c, start); 592 range_push_raw_point(c, end); 593 if (whole_block) ++ranges->whole_block_spans; 594 } 595 596 typedef struct RangeOpenCtx { 597 RangeBuildCtx* build; 598 u32 raw_end; 599 } RangeOpenCtx; 600 601 static void range_open_at_end(PReg r, void* arg) { 602 RangeOpenCtx* c = (RangeOpenCtx*)arg; 603 range_set_open_end(c->build, r, c->raw_end); 604 } 605 606 typedef struct RangeCloseCtx { 607 RangeBuildCtx* build; 608 u32 start; 609 u32 block; 610 } RangeCloseCtx; 611 612 static void range_close_def(PReg r, void* arg) { 613 RangeCloseCtx* c = (RangeCloseCtx*)arg; 614 RangeBuildCtx* b = c->build; 615 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(b->f)) return; 616 u32 open_end = range_open_end(b, r); 617 if (open_end != OPT_RANGE_NONE) { 618 range_append(b, r, c->start, open_end, c->block, 0); 619 range_close_open_end(b, r); 620 } else { 621 range_append(b, r, c->start, c->start + 1u, c->block, 0); 622 } 623 b->ranges->def_freq_by_preg[r] += b->f->blocks[c->block].frequency; 624 } 625 626 typedef struct RangeUseCtx { 627 RangeBuildCtx* build; 628 u32 end; 629 u32 block; 630 } RangeUseCtx; 631 632 static void range_open_use(PReg r, void* arg) { 633 RangeUseCtx* c = (RangeUseCtx*)arg; 634 RangeBuildCtx* b = c->build; 635 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(b->f)) return; 636 if (!range_is_open(b, r)) range_set_open_end(b, r, c->end); 637 b->ranges->use_freq_by_preg[r] += b->f->blocks[c->block].frequency; 638 } 639 640 typedef struct RangeBlockFreqCtx { 641 OptLiveRangeSet* ranges; 642 u32 freq; 643 } RangeBlockFreqCtx; 644 645 static void range_add_block_freq(PReg r, void* arg) { 646 RangeBlockFreqCtx* c = (RangeBlockFreqCtx*)arg; 647 c->ranges->live_block_freq_by_preg[r] += c->freq; 648 } 649 650 typedef struct RangeCallCtx { 651 Func* f; 652 OptLiveRangeSet* ranges; 653 const RangeInstRefs* refs; 654 u32 freq; 655 } RangeCallCtx; 656 657 static void range_add_live_across_call(PReg r, void* arg) { 658 RangeCallCtx* c = (RangeCallCtx*)arg; 659 if (r == PREG_NONE || r == 0 || r >= opt_reg_count(c->f)) return; 660 if (range_refs_has_def(c->refs, r)) return; 661 c->ranges->live_across_call_freq_by_preg[r] += c->freq; 662 } 663 664 static void range_live_pregs_update_before(RangeLivePregs* live, 665 const RangeInstRefs* refs) { 666 for (u32 i = 0; i < refs->ndefs; ++i) 667 range_live_pregs_remove(live, refs->defs[i]); 668 for (u32 i = 0; i < refs->nuses; ++i) 669 range_live_pregs_add(live, refs->uses[i]); 670 } 671 672 static void range_compress_points(OptLiveRangeSet* ranges, 673 RangeBuildCtx* build) { 674 if (build->nraw_points == 0) return; 675 u32 raw_count = ranges->raw_point_count; 676 for (u32 i = 0; i < build->nraw_points; ++i) 677 if (build->raw_points[i] >= raw_count) raw_count = build->raw_points[i] + 1u; 678 679 u8* present = arena_zarray(build->f->arena, u8, raw_count ? raw_count : 1u); 680 for (u32 i = 0; i < build->nraw_points; ++i) present[build->raw_points[i]] = 1; 681 682 u32* raw_to_point = 683 arena_array(build->f->arena, u32, raw_count ? raw_count : 1u); 684 u32 unique = 0; 685 for (u32 raw = 0; raw < raw_count; ++raw) { 686 raw_to_point[raw] = unique; 687 if (present[raw]) build->raw_points[unique++] = raw; 688 } 689 ranges->point_count = unique; 690 ranges->raw_point_count = raw_count; 691 for (u32 i = 0; i < ranges->nranges; ++i) { 692 OptLiveRange* r = &ranges->ranges[i]; 693 r->start = r->start < raw_count ? raw_to_point[r->start] : unique; 694 r->end = r->end < raw_count ? raw_to_point[r->end] : unique; 695 if (r->end <= r->start) r->end = r->start + 1u; 696 u32 len = r->end - r->start; 697 ranges->range_point_visits += len; 698 ranges->live_length_by_preg[r->preg] += len; 699 if (ranges->max_live_length < len) ranges->max_live_length = len; 700 } 701 } 702 703 void opt_live_ranges_build(Func* f, const OptLiveInfo* live, 704 OptLiveRangeSet* ranges) { 705 memset(ranges, 0, sizeof *ranges); 706 if (!f || !live) return; 707 ranges->arena = f->arena; 708 ranges->f = f; 709 ranges->first_range_by_preg = 710 arena_array(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 711 ranges->live_length_by_preg = 712 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 713 ranges->use_freq_by_preg = 714 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 715 ranges->def_freq_by_preg = 716 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 717 ranges->live_block_freq_by_preg = 718 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 719 ranges->live_across_call_freq_by_preg = 720 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 721 ranges->spill_cost_by_preg = 722 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 723 memset(ranges->first_range_by_preg, 0xff, 724 sizeof(ranges->first_range_by_preg[0]) * 725 (opt_reg_count(f) ? opt_reg_count(f) : 1u)); 726 727 RangeBuildCtx build; 728 memset(&build, 0, sizeof build); 729 build.f = f; 730 build.ranges = ranges; 731 build.last_range_by_preg = 732 arena_array(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 733 build.open_end_by_preg = 734 arena_array(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 735 build.open_gen_by_preg = 736 arena_zarray(f->arena, u32, opt_reg_count(f) ? opt_reg_count(f) : 1u); 737 build.open_gen = 1; 738 memset(build.last_range_by_preg, 0xff, 739 sizeof(build.last_range_by_preg[0]) * 740 (opt_reg_count(f) ? opt_reg_count(f) : 1u)); 741 742 u32* block_base = arena_array(f->arena, u32, f->nblocks ? f->nblocks : 1u); 743 u32 raw = 0; 744 for (u32 b = 0; b < f->nblocks; ++b) { 745 block_base[b] = raw; 746 raw += f->blocks[b].ninsts ? f->blocks[b].ninsts : 1u; 747 } 748 ranges->raw_point_count = raw + 1u; 749 750 OptBitset block_live; 751 opt_bitset_init(f->arena, &block_live, live->words); 752 RangeInstRefs refs; 753 range_refs_init(f, &refs); 754 RangeLivePregs live_pregs; 755 range_live_pregs_init(f, &live_pregs); 756 757 for (u32 b = 0; b < f->nblocks; ++b) { 758 Block* bl = &f->blocks[b]; 759 const OptBlockLive* lb = &live->blocks[b]; 760 range_block_reset(&build); 761 range_live_pregs_clear(&live_pregs); 762 u32 raw_start = block_base[b]; 763 u32 raw_end = raw_start + (bl->ninsts ? bl->ninsts : 1u); 764 RangeOpenCtx open_ctx = {&build, raw_end}; 765 ranges->live_words_touched += lb->live_out.active_words; 766 opt_bitset_iter_set(&lb->live_out, range_open_at_end, &open_ctx); 767 opt_bitset_iter_set(&lb->live_out, range_live_pregs_add_bit, &live_pregs); 768 769 RangeBlockFreqCtx freq_ctx = {ranges, bl->frequency}; 770 ranges->live_words_touched += block_live.nwords < lb->live_in.active_words 771 ? block_live.nwords 772 : lb->live_in.active_words; 773 if (block_live.active_words > lb->live_in.active_words) 774 ranges->live_words_touched += 775 block_live.active_words - lb->live_in.active_words; 776 opt_bitset_copy(&block_live, &lb->live_in); 777 ranges->live_words_touched += block_live.nwords < lb->live_out.active_words 778 ? block_live.nwords 779 : lb->live_out.active_words; 780 opt_bitset_union(&block_live, &lb->live_out); 781 ranges->live_words_touched += block_live.active_words; 782 opt_bitset_iter_set(&block_live, range_add_block_freq, &freq_ctx); 783 784 for (u32 ri = bl->ninsts; ri > 0; --ri) { 785 u32 i = ri - 1u; 786 Inst* in = &bl->insts[i]; 787 range_refs_reset(f, &refs); 788 opt_walk_inst_operands(f, in, range_collect_bits, &refs); 789 790 if ((IROp)in->op == IR_CALL) { 791 RangeCallCtx call_ctx = {f, ranges, &refs, bl->frequency}; 792 ranges->live_words_touched += live_pregs.nregs; 793 for (u32 k = 0; k < live_pregs.nregs; ++k) 794 range_add_live_across_call(live_pregs.regs[k], &call_ctx); 795 } 796 797 /* Incoming parameters are all delivered simultaneously by the ABI at 798 * function entry, so their values are mutually live there even though the 799 * param_decl markers are sequenced. Anchor every param_decl def at the 800 * entry block's base point so the params interfere with one another; this 801 * stops the allocator from coalescing a dead param (e.g. an unused arg) 802 * into a live param's incoming register, which the entry-bind parallel 803 * copy could not then resolve (two binds targeting one register). */ 804 u32 def_pos = ((IROp)in->op == IR_PARAM_DECL) ? raw_start : raw_start + i; 805 RangeCloseCtx close_ctx = {&build, def_pos, b}; 806 for (u32 k = 0; k < refs.ndefs; ++k) 807 range_close_def(refs.defs[k], &close_ctx); 808 RangeUseCtx use_ctx = {&build, raw_start + i + 1u, b}; 809 for (u32 k = 0; k < refs.nuses; ++k) 810 range_open_use(refs.uses[k], &use_ctx); 811 range_live_pregs_update_before(&live_pregs, &refs); 812 } 813 814 for (u32 oi = 0; oi < build.nopen_pregs; ++oi) { 815 PReg r = build.open_pregs[oi]; 816 if (!range_is_open(&build, r)) continue; 817 u32 open_end = range_open_end(&build, r); 818 if (open_end == OPT_RANGE_NONE) continue; 819 int whole_block = open_end == raw_end && 820 !opt_bitset_has(&lb->live_use, r) && 821 !opt_bitset_has(&lb->live_def, r); 822 range_append(&build, r, raw_start, open_end, b, whole_block); 823 range_close_open_end(&build, r); 824 } 825 ranges->preg_scans += build.nopen_pregs; 826 } 827 828 range_compress_points(ranges, &build); 829 830 for (u32 vi = 0; vi < build.nrange_pregs; ++vi) { 831 PReg r = build.range_pregs[vi]; 832 u32 nranges = 0; 833 for (u32 ri = ranges->first_range_by_preg[r]; ri != OPT_RANGE_NONE; 834 ri = ranges->ranges[ri].next) 835 ++nranges; 836 if (ranges->max_ranges_per_preg < nranges) 837 ranges->max_ranges_per_preg = nranges; 838 ranges->spill_cost_by_preg[r] = (ranges->use_freq_by_preg[r] * 2u) + 839 ranges->def_freq_by_preg[r] + 840 ranges->live_across_call_freq_by_preg[r] + 841 ranges->live_block_freq_by_preg[r]; 842 } 843 ranges->preg_scans += build.nrange_pregs; 844 } 845 846 void opt_live_dump_ranges(Func* f, const OptLiveRangeSet* ranges, Writer* w) { 847 (void)f; 848 if (!ranges || !w) return; 849 char buf[160]; 850 StrBuf sb; 851 strbuf_init(&sb, buf, sizeof buf); 852 strbuf_puts(&sb, "ranges total="); 853 strbuf_put_u64(&sb, (u64)(unsigned)ranges->nranges); 854 strbuf_puts(&sb, " points="); 855 strbuf_put_u64(&sb, (u64)(unsigned)ranges->point_count); 856 strbuf_puts(&sb, " raw_points="); 857 strbuf_put_u64(&sb, (u64)(unsigned)ranges->raw_point_count); 858 strbuf_puts(&sb, " whole_block="); 859 strbuf_put_u64(&sb, (u64)(unsigned)ranges->whole_block_spans); 860 strbuf_putc(&sb, '\n'); 861 dump_sb(w, &sb); 862 for (PReg r = 1; r < opt_reg_count(ranges->f); ++r) { 863 if (ranges->first_range_by_preg[r] == OPT_RANGE_NONE) continue; 864 strbuf_reset(&sb); 865 strbuf_putc(&sb, 'r'); 866 strbuf_put_u64(&sb, (u64)(unsigned)r); 867 strbuf_puts(&sb, " len="); 868 strbuf_put_u64(&sb, (u64)(unsigned)ranges->live_length_by_preg[r]); 869 strbuf_puts(&sb, " spill="); 870 strbuf_put_u64(&sb, (u64)(unsigned)ranges->spill_cost_by_preg[r]); 871 strbuf_putc(&sb, ':'); 872 dump_sb(w, &sb); 873 for (u32 ri = ranges->first_range_by_preg[r]; ri != OPT_RANGE_NONE; 874 ri = ranges->ranges[ri].next) { 875 const OptLiveRange* lr = &ranges->ranges[ri]; 876 strbuf_reset(&sb); 877 strbuf_puts(&sb, " ["); 878 strbuf_put_u64(&sb, (u64)(unsigned)lr->start); 879 strbuf_putc(&sb, ','); 880 strbuf_put_u64(&sb, (u64)(unsigned)lr->end); 881 strbuf_puts(&sb, ")b"); 882 strbuf_put_u64(&sb, (u64)(unsigned)lr->block); 883 if (lr->whole_block) strbuf_putc(&sb, '*'); 884 dump_sb(w, &sb); 885 } 886 dump_write(w, "\n"); 887 } 888 }