pass_coalesce.c (18120B)
1 #include <stdlib.h> 2 #include <string.h> 3 4 #include "core/arena.h" 5 #include "core/metrics.h" 6 #include "opt/opt_internal.h" 7 8 typedef struct CoalesceMove { 9 PReg dst; 10 PReg src; 11 u32 weight; 12 } CoalesceMove; 13 14 typedef struct CoalesceCtx { 15 Func* f; 16 const OptLiveRangeSet* ranges; 17 PReg* related; 18 u32 nrelated; 19 u32 related_cap; 20 u32* related_index; 21 u64* conflicts; 22 u64* unit_conflicts; 23 u32 conflict_words; 24 } CoalesceCtx; 25 26 static PReg coalesce_find(Func* f, PReg v) { 27 if (!f->opt_coalesce_parent || v == PREG_NONE || v >= opt_reg_count(f)) 28 return v; 29 PReg p = (PReg)f->opt_coalesce_parent[v]; 30 while (p != f->opt_coalesce_parent[p]) p = (PReg)f->opt_coalesce_parent[p]; 31 while (v != p) { 32 PReg n = (PReg)f->opt_coalesce_parent[v]; 33 f->opt_coalesce_parent[v] = p; 34 v = n; 35 } 36 return p; 37 } 38 39 static void coalesce_add_related(CoalesceCtx* c, PReg v) { 40 Func* f = c->f; 41 if (!opt_reg_valid(f, v)) return; 42 if (c->related_index[v] != OPT_RANGE_NONE) return; 43 if (c->nrelated == c->related_cap) { 44 u32 ncap = c->related_cap ? c->related_cap * 2u : 32u; 45 PReg* nr = arena_array(f->arena, PReg, ncap); 46 if (c->related) memcpy(nr, c->related, sizeof(c->related[0]) * c->nrelated); 47 c->related = nr; 48 c->related_cap = ncap; 49 } 50 c->related_index[v] = c->nrelated; 51 c->related[c->nrelated++] = v; 52 } 53 54 int opt_ranges_overlap_kind(const OptLiveRangeSet* ranges, PReg a, PReg b) { 55 /* Returns 0 (no overlap), 1 (a single unit-length overlap), or 2 (real 56 * conflict: an overlap longer than one point, or two or more disjoint 57 * unit-length overlaps). 58 * 59 * A single unit-length overlap is the natural conflict of a move 60 * `dst = COPY src`: at the def point of dst, src is still live for one 61 * point. `group_conflicts` allows that single unit conflict to permit 62 * coalescing the move. Two or more unit overlaps at distinct points imply 63 * dst has multiple non-SSA defs whose live ranges each clip src — those 64 * are real conflicts and must block coalescing, otherwise we'd allocate 65 * dst into src's hard register and clobber src at the extra def. */ 66 /* Overlap must be measured on the *raw* (pre-compression) point numbers, 67 * not the compressed start/end. range_compress_points only keeps points 68 * that are some range's boundary, so an interior instruction point shared 69 * by two live values can be dropped — collapsing a genuine multi-point 70 * overlap down to a single compressed point and masquerading as the benign 71 * unit-overlap of a coalescable move. The benign move/swap pattern 72 * (`dst = COPY src`, or `sub x0, x21, x0`) is genuinely one *raw* point 73 * wide: src is used and dst is defined at the same instruction. A value 74 * that stays live across the def of an unrelated value spans two or more 75 * raw points and is a real conflict. */ 76 u32 unit_count = 0; 77 for (u32 ar = ranges->first_range_by_preg[a]; ar != OPT_RANGE_NONE; 78 ar = ranges->ranges[ar].next) { 79 const OptLiveRange* ra = &ranges->ranges[ar]; 80 for (u32 br = ranges->first_range_by_preg[b]; br != OPT_RANGE_NONE; 81 br = ranges->ranges[br].next) { 82 const OptLiveRange* rb = &ranges->ranges[br]; 83 if (ra->raw_start < rb->raw_end && rb->raw_start < ra->raw_end) { 84 u32 start = 85 ra->raw_start > rb->raw_start ? ra->raw_start : rb->raw_start; 86 u32 end = ra->raw_end < rb->raw_end ? ra->raw_end : rb->raw_end; 87 if (end > start + 1u) return 2; 88 if (++unit_count > 1u) return 2; 89 } 90 } 91 } 92 return unit_count ? 1 : 0; 93 } 94 95 static void coalesce_set_conflict_bit(u64* bits, u32 nrelated, u32 a, u32 b) { 96 if (!bits) return; 97 if (a == b) return; 98 u32 x = a < b ? a : b; 99 u32 y = a < b ? b : a; 100 u32 bit = x * nrelated + y; 101 bits[bit / 64u] |= 1ull << (bit % 64u); 102 } 103 104 static void coalesce_set_conflict(CoalesceCtx* c, u32 a, u32 b, int unit) { 105 coalesce_set_conflict_bit(c->conflicts, c->nrelated, a, b); 106 if (unit) coalesce_set_conflict_bit(c->unit_conflicts, c->nrelated, a, b); 107 } 108 109 static int coalesce_has_bit(const CoalesceCtx* c, const u64* bits, PReg a, 110 PReg b) { 111 if (!bits || a >= opt_reg_count(c->f) || b >= opt_reg_count(c->f)) return 1; 112 u32 ai = c->related_index[a]; 113 u32 bi = c->related_index[b]; 114 if (ai == OPT_RANGE_NONE || bi == OPT_RANGE_NONE) return 0; 115 if (ai == bi) return 0; 116 u32 x = ai < bi ? ai : bi; 117 u32 y = ai < bi ? bi : ai; 118 u32 bit = x * c->nrelated + y; 119 return (bits[bit / 64u] & (1ull << (bit % 64u))) != 0; 120 } 121 122 static int coalesce_has_conflict(const CoalesceCtx* c, PReg a, PReg b) { 123 return coalesce_has_bit(c, c->conflicts, a, b); 124 } 125 126 static int coalesce_has_unit_conflict(const CoalesceCtx* c, PReg a, PReg b) { 127 return coalesce_has_bit(c, c->unit_conflicts, a, b); 128 } 129 130 static int group_conflicts(const CoalesceCtx* c, PReg ra, PReg rb, PReg allow_a, 131 PReg allow_b) { 132 for (u32 i = 0; i < c->nrelated; ++i) { 133 PReg a = c->related[i]; 134 if (coalesce_find(c->f, a) != ra) continue; 135 for (u32 j = 0; j < c->nrelated; ++j) { 136 PReg b = c->related[j]; 137 if (coalesce_find(c->f, b) != rb) continue; 138 if (((a == allow_a && b == allow_b) || (a == allow_b && b == allow_a)) && 139 coalesce_has_unit_conflict(c, a, b)) 140 continue; 141 if (coalesce_has_conflict(c, a, b)) return 1; 142 } 143 } 144 return 0; 145 } 146 147 static int hard_reg_possible(Func* f, u8 cls, u32 forbidden) { 148 for (u32 i = 0; i < f->opt_hard_reg_count[cls]; ++i) { 149 Reg r = f->opt_hard_regs[cls][i]; 150 if (r >= 32) continue; 151 if ((forbidden & (1u << r)) == 0) return 1; 152 } 153 return f->opt_hard_reg_count[cls] == 0; 154 } 155 156 static int group_constraints_compatible(const CoalesceCtx* c, PReg ra, 157 PReg rb) { 158 Func* f = c->f; 159 u8 cls = opt_reg_cls(f, ra); 160 KitCgTypeId type = opt_reg_type(f, ra); 161 u32 forbidden = 0; 162 for (PReg v = 1; v < opt_reg_count(f); ++v) { 163 PReg r = coalesce_find(f, v); 164 if (r != ra && r != rb) continue; 165 if (opt_reg_cls(f, v) != cls || opt_reg_type(f, v) != type) return 0; 166 const OptPRegInfo* vi = &f->preg_info[v]; 167 forbidden |= vi->forbidden_hard_regs; 168 } 169 return hard_reg_possible(f, cls, forbidden); 170 } 171 172 static void coalesce_union(Func* f, PReg a, PReg b) { 173 PReg ra = coalesce_find(f, a); 174 PReg rb = coalesce_find(f, b); 175 if (ra == rb) return; 176 u32 as = f->opt_coalesce_size[ra]; 177 u32 bs = f->opt_coalesce_size[rb]; 178 if (as < bs || (as == bs && rb < ra)) { 179 PReg t = ra; 180 ra = rb; 181 rb = t; 182 } 183 f->opt_coalesce_parent[rb] = ra; 184 f->opt_coalesce_size[ra] += f->opt_coalesce_size[rb]; 185 } 186 187 static int move_higher(const CoalesceMove* a, const CoalesceMove* b) { 188 if (a->weight != b->weight) return a->weight > b->weight; 189 if (a->dst != b->dst) return a->dst < b->dst; 190 return a->src < b->src; 191 } 192 193 static int move_cmp(const void* va, const void* vb) { 194 const CoalesceMove* a = (const CoalesceMove*)va; 195 const CoalesceMove* b = (const CoalesceMove*)vb; 196 if (move_higher(a, b)) return -1; 197 if (move_higher(b, a)) return 1; 198 return 0; 199 } 200 201 static int collect_move(Func* f, const OptLiveRangeSet* ranges, Inst* in, 202 u32 block, CoalesceMove* out) { 203 if ((IROp)in->op != IR_COPY || in->nopnds < 2) return 0; 204 if (in->flags & IRF_NO_COALESCE) return 0; 205 if (in->opnds[0].kind != OPK_REG || in->opnds[1].kind != OPK_REG) return 0; 206 PReg dst = (PReg)in->opnds[0].v.reg; 207 PReg src = (PReg)in->opnds[1].v.reg; 208 if (!opt_reg_valid(f, dst) || !opt_reg_valid(f, src) || dst == src) return 0; 209 if (ranges->first_range_by_preg[dst] == OPT_RANGE_NONE || 210 ranges->first_range_by_preg[src] == OPT_RANGE_NONE) 211 return 0; 212 if (opt_reg_cls(f, dst) != opt_reg_cls(f, src)) return 0; 213 if (opt_reg_type(f, dst) != opt_reg_type(f, src)) return 0; 214 out->dst = dst; 215 out->src = src; 216 out->weight = f->blocks[block].frequency ? f->blocks[block].frequency : 1u; 217 return 1; 218 } 219 220 void opt_coalesce_ranges(Func* f, const OptLiveRangeSet* ranges) { 221 if (!f || !ranges || !f->preg_info) return; 222 u32 nregs = opt_reg_count(f); 223 f->opt_coalesce_moves_seen = 0; 224 f->opt_coalesce_candidates = 0; 225 f->opt_coalesce_conflicts = 0; 226 f->opt_coalesce_merge_attempts = 0; 227 f->opt_coalesce_merges = 0; 228 f->opt_coalesce_parent = arena_array(f->arena, u32, nregs ? nregs : 1u); 229 f->opt_coalesce_size = arena_array(f->arena, u32, nregs ? nregs : 1u); 230 for (PReg v = 0; v < nregs; ++v) { 231 f->opt_coalesce_parent[v] = v; 232 f->opt_coalesce_size[v] = 1; 233 } 234 235 CoalesceMove* moves = NULL; 236 u32 nmoves = 0; 237 u32 move_cap = 0; 238 CoalesceCtx ctx; 239 memset(&ctx, 0, sizeof ctx); 240 ctx.f = f; 241 ctx.ranges = ranges; 242 ctx.related_index = arena_array(f->arena, u32, nregs ? nregs : 1u); 243 memset(ctx.related_index, 0xff, 244 sizeof(ctx.related_index[0]) * (nregs ? nregs : 1u)); 245 246 for (u32 b = 0; b < f->nblocks; ++b) { 247 Block* bl = &f->blocks[b]; 248 for (u32 i = 0; i < bl->ninsts; ++i) { 249 if ((IROp)bl->insts[i].op == IR_COPY) ++f->opt_coalesce_moves_seen; 250 CoalesceMove m; 251 if (!collect_move(f, ranges, &bl->insts[i], b, &m)) continue; 252 if (nmoves == move_cap) { 253 u32 ncap = move_cap ? move_cap * 2u : 32u; 254 CoalesceMove* nv = arena_array(f->arena, CoalesceMove, ncap); 255 if (moves) memcpy(nv, moves, sizeof(moves[0]) * nmoves); 256 moves = nv; 257 move_cap = ncap; 258 } 259 moves[nmoves++] = m; 260 coalesce_add_related(&ctx, m.dst); 261 coalesce_add_related(&ctx, m.src); 262 } 263 } 264 f->opt_coalesce_candidates = nmoves; 265 if (!nmoves || ctx.nrelated < 2) goto metrics; 266 267 ctx.conflict_words = (ctx.nrelated * ctx.nrelated + 63u) / 64u; 268 ctx.conflicts = 269 arena_zarray(f->arena, u64, ctx.conflict_words ? ctx.conflict_words : 1u); 270 ctx.unit_conflicts = 271 arena_zarray(f->arena, u64, ctx.conflict_words ? ctx.conflict_words : 1u); 272 for (u32 i = 0; i < ctx.nrelated; ++i) { 273 for (u32 j = i + 1u; j < ctx.nrelated; ++j) { 274 int kind = 275 opt_ranges_overlap_kind(ranges, ctx.related[i], ctx.related[j]); 276 if (kind) { 277 coalesce_set_conflict(&ctx, i, j, kind == 1); 278 ++f->opt_coalesce_conflicts; 279 } 280 } 281 } 282 283 qsort(moves, nmoves, sizeof(moves[0]), move_cmp); 284 for (u32 i = 0; i < nmoves; ++i) { 285 PReg ra = coalesce_find(f, moves[i].dst); 286 PReg rb = coalesce_find(f, moves[i].src); 287 if (ra == rb) continue; 288 ++f->opt_coalesce_merge_attempts; 289 if (group_conflicts(&ctx, ra, rb, moves[i].dst, moves[i].src)) continue; 290 if (!group_constraints_compatible(&ctx, ra, rb)) continue; 291 coalesce_union(f, ra, rb); 292 ++f->opt_coalesce_merges; 293 } 294 295 metrics: 296 metrics_count(f->c, "opt.coalesce.moves_seen", f->opt_coalesce_moves_seen); 297 metrics_count(f->c, "opt.coalesce.candidates", f->opt_coalesce_candidates); 298 metrics_count(f->c, "opt.coalesce.conflicts", f->opt_coalesce_conflicts); 299 metrics_count(f->c, "opt.coalesce.merge_attempts", 300 f->opt_coalesce_merge_attempts); 301 metrics_count(f->c, "opt.coalesce.merges", f->opt_coalesce_merges); 302 } 303 304 void opt_coalesce(Func* f) { 305 if (!f) return; 306 OptLiveInfo live; 307 opt_live_blocks(f, &live); 308 OptLiveRangeSet ranges; 309 opt_live_ranges_build(f, &live, &ranges); 310 opt_coalesce_ranges(f, &ranges); 311 } 312 313 /* ---- Linear move coalescing for the no-SSA O1 regalloc path (O1.md W3) ---- 314 * 315 * The O2 coalescer above (opt_coalesce_ranges) builds an O(n^2) conflict matrix 316 * over the *related set* (every PReg touched by any move) and then merges. W3 317 * needs the same union-find result for the O1 allocator without that matrix. 318 * 319 * We keep, per coalesce root: a member-PReg list (capped at K) and the 320 * aggregated register constraints. A merge tests the two roots with the proven 321 * raw-range overlap predicate (opt_ranges_overlap_kind) over the bounded K^2 322 * member cross-product — exactly the rule the O2 group_conflicts uses: the only 323 * permitted overlap in the whole cross-product is the move's single unit 324 * overlap (dst defined where src dies); any other overlap (unit or wide) blocks 325 * the merge. Per-PReg ranges are NOT globally sorted (a non-SSA value redefined 326 * in a block produces overlapping sub-ranges), so a sorted-list sweep is wrong 327 * here; the nested raw-range test in opt_ranges_overlap_kind is order-agnostic 328 * and correct. With K bounded and per-PReg range counts bounded, each merge is 329 * O(1) and the pass is linear in moves. Classes that would exceed K simply stop 330 * coalescing further (the conservative fallback in O1.md W3) — correct, just 331 * leaving a few copies. No nrelated^2 work anywhere. 332 */ 333 #define LIN_COAL_MAX_MEMBERS 64u 334 335 typedef struct LinCoalState { 336 PReg* members; /* per root: PReg members of the coalesce group (capped) */ 337 u32 nmembers; 338 u32 forbidden; /* OR of forbidden_hard_regs over the group */ 339 u8 init; /* state has been populated for this root */ 340 u8 cls; 341 u8 pad[2]; 342 KitCgTypeId type; 343 } LinCoalState; 344 345 /* Conflict test for merging roots ra/rb via move endpoints (md,ms). Returns 1 346 * if any member pair (a in ra, b in rb) overlaps, except the single benign unit 347 * overlap of the move endpoints themselves. Mirrors O2 group_conflicts. */ 348 static int lin_group_conflicts(const OptLiveRangeSet* ranges, 349 const LinCoalState* sa, const LinCoalState* sb, 350 PReg md, PReg ms) { 351 for (u32 i = 0; i < sa->nmembers; ++i) { 352 PReg a = sa->members[i]; 353 for (u32 j = 0; j < sb->nmembers; ++j) { 354 PReg b = sb->members[j]; 355 int kind = opt_ranges_overlap_kind(ranges, a, b); 356 if (!kind) continue; 357 /* The one excusable overlap: the move's endpoints, unit-length only. */ 358 if (kind == 1 && ((a == md && b == ms) || (a == ms && b == md))) 359 continue; 360 return 1; 361 } 362 } 363 return 0; 364 } 365 366 /* Constraint compatibility on the precomputed group masks (mirrors 367 * group_constraints_compatible's mask math, but incremental rather than 368 * re-scanning every PReg). Requires at least one plausible hard register so a 369 * merge does not over-constrain the class onto the stack. */ 370 static int lin_constraints_ok(Func* f, const LinCoalState* sa, 371 const LinCoalState* sb) { 372 if (sa->cls != sb->cls || sa->type != sb->type) return 0; 373 u32 forbidden = sa->forbidden | sb->forbidden; 374 return hard_reg_possible(f, sa->cls, forbidden); 375 } 376 377 void opt_coalesce_linear(Func* f, const OptLiveRangeSet* ranges) { 378 if (!f || !ranges || !f->preg_info) return; 379 u32 nregs = opt_reg_count(f); 380 f->opt_coalesce_moves_seen = 0; 381 f->opt_coalesce_candidates = 0; 382 f->opt_coalesce_conflicts = 0; 383 f->opt_coalesce_merge_attempts = 0; 384 f->opt_coalesce_merges = 0; 385 f->opt_coalesce_parent = arena_array(f->arena, u32, nregs ? nregs : 1u); 386 f->opt_coalesce_size = arena_array(f->arena, u32, nregs ? nregs : 1u); 387 for (PReg v = 0; v < nregs; ++v) { 388 f->opt_coalesce_parent[v] = v; 389 f->opt_coalesce_size[v] = 1; 390 } 391 f->opt_o1_coalescing = 1; 392 393 /* Collect eligible moves (same predicate the O2 path uses). */ 394 CoalesceMove* moves = NULL; 395 u32 nmoves = 0; 396 u32 move_cap = 0; 397 for (u32 b = 0; b < f->nblocks; ++b) { 398 Block* bl = &f->blocks[b]; 399 for (u32 i = 0; i < bl->ninsts; ++i) { 400 if ((IROp)bl->insts[i].op == IR_COPY) ++f->opt_coalesce_moves_seen; 401 CoalesceMove m; 402 if (!collect_move(f, ranges, &bl->insts[i], b, &m)) continue; 403 if (nmoves == move_cap) { 404 u32 ncap = move_cap ? move_cap * 2u : 32u; 405 CoalesceMove* nv = arena_array(f->arena, CoalesceMove, ncap); 406 if (moves) memcpy(nv, moves, sizeof(moves[0]) * nmoves); 407 moves = nv; 408 move_cap = ncap; 409 } 410 moves[nmoves++] = m; 411 } 412 } 413 f->opt_coalesce_candidates = nmoves; 414 if (!nmoves) goto metrics; 415 416 /* Per-root state, indexed by PReg (root is its own index). Only roots that 417 * appear as a move endpoint are ever consulted, but a flat array keeps the 418 * union-find indexing trivial. */ 419 LinCoalState* st = arena_array(f->arena, LinCoalState, nregs ? nregs : 1u); 420 for (PReg v = 0; v < nregs; ++v) { 421 st[v].members = NULL; 422 st[v].nmembers = 0; 423 st[v].forbidden = 0; 424 st[v].init = 0; 425 st[v].cls = 0; 426 st[v].type = 0; 427 } 428 for (u32 i = 0; i < nmoves; ++i) { 429 PReg ends[2] = {moves[i].dst, moves[i].src}; 430 for (int e = 0; e < 2; ++e) { 431 PReg v = ends[e]; 432 if (st[v].init) continue; 433 const OptPRegInfo* vi = &f->preg_info[v]; 434 st[v].init = 1; 435 st[v].members = arena_array(f->arena, PReg, LIN_COAL_MAX_MEMBERS); 436 st[v].members[0] = v; 437 st[v].nmembers = 1; 438 st[v].forbidden = vi->forbidden_hard_regs; 439 st[v].cls = opt_reg_cls(f, v); 440 st[v].type = opt_reg_type(f, v); 441 } 442 } 443 444 qsort(moves, nmoves, sizeof(moves[0]), move_cmp); 445 for (u32 i = 0; i < nmoves; ++i) { 446 PReg ra = coalesce_find(f, moves[i].dst); 447 PReg rb = coalesce_find(f, moves[i].src); 448 if (ra == rb) continue; 449 ++f->opt_coalesce_merge_attempts; 450 /* Conservative size cap (O1.md W3 fallback): stop growing a class past K. */ 451 if (st[ra].nmembers + st[rb].nmembers > LIN_COAL_MAX_MEMBERS) continue; 452 if (lin_group_conflicts(ranges, &st[ra], &st[rb], moves[i].dst, 453 moves[i].src)) { 454 ++f->opt_coalesce_conflicts; 455 continue; 456 } 457 if (!lin_constraints_ok(f, &st[ra], &st[rb])) continue; 458 coalesce_union(f, ra, rb); 459 PReg nr = coalesce_find(f, ra); 460 PReg orr = (nr == ra) ? rb : ra; 461 /* Fold `orr` group state into surviving root `nr`. */ 462 for (u32 m = 0; m < st[orr].nmembers; ++m) 463 st[nr].members[st[nr].nmembers++] = st[orr].members[m]; 464 st[nr].forbidden |= st[orr].forbidden; 465 st[orr].nmembers = 0; /* folded into nr */ 466 ++f->opt_coalesce_merges; 467 } 468 469 metrics: 470 metrics_count(f->c, "opt.coalesce.moves_seen", f->opt_coalesce_moves_seen); 471 metrics_count(f->c, "opt.coalesce.candidates", f->opt_coalesce_candidates); 472 metrics_count(f->c, "opt.coalesce.conflicts", f->opt_coalesce_conflicts); 473 metrics_count(f->c, "opt.coalesce.merge_attempts", 474 f->opt_coalesce_merge_attempts); 475 metrics_count(f->c, "opt.coalesce.merges", f->opt_coalesce_merges); 476 }