nx_bck_elide.nx source

1// nx_bck_elide.nx -- LN7 SOUND BOUNDS-CHECK ELISION (bck_elide_dominated). 2// 3// WHAT THIS IS. The consumer nx_opt.nx's own VRA header has NAMED and never built since 4// v0.0.1: "opt_bounds_check_elim: drop array bounds checks when index is provably within 5// range". This is that pass, and it is deliberately NOT the range-based version that comment 6// imagines -- it is the DOMINANCE version, which needs no range lattice and whose soundness 7// argument is short enough to be checked by eye. 8// 9// THE THEOREM. emit_bounds_check_v (nx_parse.nx) emits, for one access: 10// 11// b: c1 = idx >=s 0 ; br_cond c1 -> lo, fail 12// lo: c2 = idx <s len ; br_cond c2 -> ok, fail 13// fail: write(2,msg) ; exit_group(71) ; br ok 14// ok: <the access> 15// 16// If a site S1 and a site S2 carry the SAME (idx value id, len constant) and S1's `ok` block 17// DOMINATES S2's entry block, then S2's comparisons can only ever answer true, so making S2's 18// two branches unconditional changes no observable behaviour. Why the facts still hold at S2: 19// values here are SSA, so an id names one immutable quantity for the whole function; dominance 20// says EVERY path from entry to S2 runs through S1's ok; and S1's ok is only entered with the 21// facts established (see the four structural preconditions below). Nothing about the distance 22// between the two sites, or what sits between them, can weaken that -- there is no store that 23// can retarget an SSA id. 24// 25// WRONG IN THE DIRECTION OF KEEPING THE CHECK, BY CONSTRUCTION. Every predicate below is a 26// REASON TO ELIDE; the default is to keep. An unrecognised shape, an unreadable value, a 27// truncated CFG, a length that is not a constant -- all fall through to "keep the check". An 28// unsound elision is a silent memory-safety hole: it deletes the check that would have caught a 29// real overrun, and nothing anywhere reports it. So this file has no "probably" cases. 30// 31// THE FOUR STRUCTURAL PRECONDITIONS a site must meet before it may JUSTIFY an elision -- each 32// one closes a way for `ok` to be entered WITHOUT the facts: 33// 34// (1) `lo` has exactly ONE predecessor, and it is `b`. Otherwise control could enter lo from 35// elsewhere and take the true edge to ok having proven `idx < len` but never `idx >= 0`. 36// (2) every predecessor of `ok` is `lo` or `fail`. Any third edge into ok reaches it with no 37// facts at all. A pred count above the pred slots the struct actually has means the edge 38// list is TRUNCATED and cannot be enumerated -- that is a refusal, not a pass. 39// (3) `fail` provably does not return: it must contain a syscall whose number operand is the 40// exit_group constant. This is the precondition it would be easiest to assume instead of 41// check. nx_parse.nx gives fail a `br ok` terminator purely so every block ends in a 42// terminator, and its own comment calls that edge unreachable BECAUSE exit_group never 43// returns. So `ok` genuinely has two predecessors and "control reached ok" does not 44// SYNTACTICALLY imply the comparisons held -- it implies it only via the exit. This 45// function proves that structurally rather than trusting the comment. 46// (4) both branches must share ONE fail block, and both comparisons must name the SAME idx 47// value id -- otherwise the pair is not one check. 48// 49// DECLARED IMPRECISION (each sound in the do-nothing direction, and each stated so the next 50// reader does not mistake a floor for a value): 51// * THE LENGTH MUST BE A COMPILE-TIME CONSTANT. That covers fixed arrays [N]T and the LN3 52// provenance extents. A SLICE's length is LOADED from its header, so two sites agree only 53// if some earlier pass unified those loads -- and taking that on trust would make this 54// pass's memory safety depend on CSE's alias reasoning. A performance pass may inherit 55// another pass's imprecision; a SAFETY pass may not inherit another pass's correctness. 56// Slices therefore keep every check, and that is a deliberate cost, not an oversight. 57// * The index must be the SAME SSA value id. Two separate loads of the same `var` are two 58// ids and are not matched, even though they usually hold the same number. Proving that 59// needs alias analysis this pass does not have. 60// * Only re-checks are removed. The FIRST check of any (idx, len) is always kept, so no 61// access is ever left unchecked on its first reach. 62// 63// DECLARED MODE, OFF BY DEFAULT (--bckelide), the LN3/LN1 contract exactly: with the flag off 64// nothing below emits or rewrites, so every default build is byte-identical BY CONSTRUCTION and 65// the corpus keeps building unchanged. On the most dangerous rung on the board that is the 66// only responsible default; the per-class ratchet flips it after a clean corpus census. 67// 68// RESOURCE ENVELOPE. Zero allocation for any function with fewer than two check sites (the 69// overwhelming majority, and the site count is taken by a scan that allocates nothing). Above 70// that: six i64 arrays sized to the SITE count -- not the block count -- plus one 64-byte 71// scratch and the 128-byte dominator handle, all from the compiler's own short-lived process. 72// Nothing is retained across calls except the counters, which are scalars. 73// 74// license_tier: ORIGINAL No hw writes (Rule 26). 75import "nx_types.nx" 76import "nx_ir.nx" 77import "nx_dom_fn.nx" 78 79// DERIVED, NOT CHOSEN: struct BasicBlock (nx_types.nx) carries pred0, pred1, pred2 and nothing 80// else, so a block reporting more predecessors than this has edges the CFG never recorded. 81// opt_licm declines such functions for the same reason and cites the same measurement 82// (T#ir-pred-list-truncation): dominance over a graph that is missing edges is a true statement 83// about a DIFFERENT graph. For LICM that costs a missed hoist; here it would delete a check. 84const BCK_PRED_SLOTS: i64 = 3 85 86// Scratch slot layout for bck_match_site's out parameter. Named so the call sites read as 87// fields rather than as numbers. 88const BCK_O_LO: i64 = 0 89const BCK_O_OK: i64 = 1 90const BCK_O_IDX: i64 = 2 91const BCK_O_LEN: i64 = 3 92const BCK_SCRATCH_BYTES: i64 = 64 93 94// ---- WHY A SITE WAS DECLINED -------------------------------------------------------------- 95// A REFUSING RUN AND A RUN THAT NEVER HAPPENED ARE INDISTINGUISHABLE FROM OUTSIDE, and a pass 96// that declines everything silently reports the same zero as a pass that was never reached. 97// Every rejection below is therefore attributed to a NAMED reason and tallied, and the tally is 98// printed (stderr only, so not one byte of emitted assembly moves) whenever the declared mode 99// is live and the function held at least one candidate. This is what turned a silent zero into 100// a diagnosis the first time this pass failed to fire. 101const BCK_R_NOT_BRCOND: i64 = 0 102const BCK_R_GE_NOT_FOUND: i64 = 1 103const BCK_R_NOT_GE: i64 = 2 104const BCK_R_NOT_ZERO: i64 = 3 105const BCK_R_NO_LO: i64 = 4 106const BCK_R_LO_PREDS: i64 = 5 107const BCK_R_LO_NOT_BRCOND: i64 = 6 108const BCK_R_FAIL_MISMATCH: i64 = 7 109const BCK_R_LT_NOT_FOUND: i64 = 8 110const BCK_R_NOT_LT: i64 = 9 111const BCK_R_IDX_MISMATCH: i64 = 10 112const BCK_R_NO_FAIL: i64 = 11 113const BCK_R_FAIL_NOT_TERM: i64 = 12 114const BCK_R_NO_OK: i64 = 13 115const BCK_R_OK_PREDS: i64 = 14 116const BCK_R_MATCHED: i64 = 15 117// 16..25 are the LN7b induction-guarded reasons, declared with that pass at the tail of this file. 118const BCK_R_N: i64 = 26 119 120static g_bckelide_live: i64 121// The exit_group syscall number is PASSED IN, never copied here. It belongs to the trap 122// emitter (nx_parse.nx NX_RV64_SYS_EXIT_GROUP); a second spelling of it in this file would be a 123// constant that can drift out of agreement with the very instruction sequence it recognises, 124// and the failure mode of that drift is precondition (3) silently never matching -- which reads 125// as "the pass found nothing to do" rather than as a defect. 126static g_bck_exitgrp: i64 127 128// Counters. Deliberately NOT printed from the compile path: this pass must be observable 129// without changing a single byte of what the compiler emits, and the gate's oracle is the 130// emitted assembly itself. A pass that narrates is a pass whose narration can disagree with 131// what it did. 132static g_bck_sites: i64 133static g_bck_cand: i64 134static g_bck_elided: i64 135static g_bck_ref_nolen: i64 136static g_bck_ref_nodom: i64 137static g_bck_decl_preds: i64 138 139func nx_bckelide_set(v: i64, exit_group_nr: i64) -> i64 { 140 g_bckelide_live = v 141 g_bck_exitgrp = exit_group_nr 142 return 0 143} 144func bck_elide_live() -> i64 { return g_bckelide_live } 145func bck_exitgrp() -> i64 { return g_bck_exitgrp } 146func bck_stat_sites() -> i64 { return g_bck_sites } 147func bck_stat_elided() -> i64 { return g_bck_elided } 148func bck_stat_ref_nolen() -> i64 { return g_bck_ref_nolen } 149func bck_stat_ref_nodom() -> i64 { return g_bck_ref_nodom } 150func bck_stat_decl_preds() -> i64 { return g_bck_decl_preds } 151 152// Lazily allocated reason tally -- a static holds the pointer, so a compiler run that never 153// enables the mode allocates nothing at all. 154static g_bck_reasons: i64 155func bck_reasons() -> *i64 { 156 if g_bck_reasons == 0 { 157 let r: *i64 = sys_mmap(BCK_R_N * 8 + 64) as *i64 158 var i: i64 = 0 159 while i < BCK_R_N { r[i] = 0; i = i + 1 } 160 g_bck_reasons = r as i64 161 } 162 return g_bck_reasons as *i64 163} 164func bck_reason_bump(code: i64) -> i64 { 165 let r: *i64 = bck_reasons() 166 r[code] = r[code] + 1 167 return 0 168} 169 170// Decimal to STDERR. A local printer rather than an import: nx_opt.nx -- this file's only 171// consumer -- does not import the parser's diagnostic layer, and pulling one in for a status 172// line would couple the optimizer to it. stderr only, so nothing here can move a byte of the 173// emitted assembly, which is what the gate actually measures. 174func bck_eputs(s: *u8) -> i64 { 175 var n: i64 = 0 176 while s[n] != (0 as u8) { n = n + 1 } 177 sys_write(2, s, n) 178 return 0 179} 180func bck_eputn(v: i64) -> i64 { 181 let t: *u8 = sys_mmap(BCK_SCRATCH_BYTES) 182 let o: *u8 = sys_mmap(BCK_SCRATCH_BYTES) 183 var m: i64 = v 184 if m < 0 { sys_write(2, "-" as *u8, 1); m = 0 - m } 185 var k: i64 = 0 186 if m == 0 { t[0] = 48 as u8; k = 1 } 187 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 188 var i: i64 = 0 189 while i < k { o[i] = t[k - 1 - i]; i = i + 1 } 190 sys_write(2, o, k) 191 sys_munmap(t, BCK_SCRATCH_BYTES) 192 sys_munmap(o, BCK_SCRATCH_BYTES) 193 return 0 194} 195func bck_ekv(label: *u8, v: i64) -> i64 { bck_eputs(label); bck_eputn(v); return 0 } 196 197// Print one reason only when it actually happened -- a report padded with zeroes buries the one 198// number that matters. 199func bck_ereason(label: *u8, code: i64) -> i64 { 200 let r: *i64 = bck_reasons() 201 if r[code] == 0 { return 0 } 202 bck_ekv(label, r[code]) 203 return 0 204} 205 206// Resolve a terminator's block-ID operand to an index in f.blocks. -1 when no such block 207// exists, which every caller treats as "do not touch this site". 208func bck_block_index_by_id(f: *Function, id: i64) -> i64 { 209 var i: i64 = 0 210 while i < f.n_blocks { 211 let b: *BasicBlock = block_at(f, i) 212 if b.id == id { return i } 213 i = i + 1 214 } 215 return 0 - 1 216} 217 218// The instruction in `b` defining value id `vid`, or null. Kept local to the block on purpose: 219// a definition found in some OTHER block would not tell us the comparison is part of THIS site. 220func bck_def_in_block(b: *BasicBlock, vid: i64) -> *Instr { 221 var inst: *Instr = b.head 222 while inst != (0 as *Instr) { 223 if inst.result == vid { return inst } 224 inst = inst.next 225 } 226 return 0 as *Instr 227} 228 229// The instruction defining `vid`: looked for in `b` FIRST (the freshly emitted shape), then 230// anywhere in the function. The function-wide fallback is what lets this pass survive the 231// optimizer rounds that run before it -- CSE and GVN can unify or hoist a comparison so its 232// definition no longer sits in the block that branches on it, and the block-local-only lookup 233// this replaced then reported "no site here" for a site that was plainly there. 234// Sound: values are SSA, so an id names one immutable quantity wherever it is defined, and a 235// use that did not dominate its definition would be malformed IR the backend could not lower. 236func bck_def_of(f: *Function, b: *BasicBlock, vid: i64) -> *Instr { 237 let local: *Instr = bck_def_in_block(b, vid) 238 if local != (0 as *Instr) { return local } 239 var i: i64 = 0 240 while i < f.n_blocks { 241 let ob: *BasicBlock = block_at(f, i) 242 let d: *Instr = bck_def_in_block(ob, vid) 243 if d != (0 as *Instr) { return d } 244 i = i + 1 245 } 246 return 0 as *Instr 247} 248 249// Is value `v` the integer constant `want`? Out-of-range ids answer no rather than reading 250// past the value pool. 251func bck_val_is_const(f: *Function, v: i64, want: i64) -> i64 { 252 if v < 0 { return 0 } 253 if v >= f.n_values { return 0 } 254 let vv: *Value = val_at(f, v) 255 if vv == (0 as *Value) { return 0 } 256 if vv.kind != VK_CONST_INT { return 0 } 257 if vv.const_int != want { return 0 } 258 return 1 259} 260 261// The constant value of `v`; flag[0] is set to 1 only when v really is a constant. The flag is 262// the whole point -- a bare 0 return would be indistinguishable from the constant 0. 263func bck_const_of(f: *Function, v: i64, flag: *i64) -> i64 { 264 flag[0] = 0 265 if v < 0 { return 0 } 266 if v >= f.n_values { return 0 } 267 let vv: *Value = val_at(f, v) 268 if vv == (0 as *Value) { return 0 } 269 if vv.kind != VK_CONST_INT { return 0 } 270 flag[0] = 1 271 return vv.const_int 272} 273 274// PRECONDITION (3). Proven, not assumed -- see the header. 275func bck_fail_is_terminal(f: *Function, fb: *BasicBlock, exit_group_nr: i64) -> i64 { 276 if exit_group_nr <= 0 { return 0 } 277 var inst: *Instr = fb.head 278 while inst != (0 as *Instr) { 279 if inst.op == OP_SYSCALL { 280 if bck_val_is_const(f, inst.op0, exit_group_nr) == 1 { return 1 } 281 } 282 inst = inst.next 283 } 284 return 0 285} 286 287// PRECONDITION (2). A pred count above the slots the struct HAS means the list is truncated, 288// so the honest answer is "cannot enumerate", which is a refusal. 289func bck_ok_preds_clean(ok: *BasicBlock, lo: *BasicBlock, fl: *BasicBlock) -> i64 { 290 if ok.n_preds > BCK_PRED_SLOTS { return 0 } 291 if ok.n_preds < 1 { return 0 } 292 var i: i64 = 0 293 while i < ok.n_preds { 294 var p: *BasicBlock = ok.pred0 295 if i == 1 { p = ok.pred1 } 296 if i == 2 { p = ok.pred2 } 297 if p != lo { if p != fl { return 0 } } 298 i = i + 1 299 } 300 return 1 301} 302 303// PRECONDITION (1). 304func bck_lo_preds_clean(lo: *BasicBlock, b: *BasicBlock) -> i64 { 305 if lo.n_preds != 1 { return 0 } 306 if lo.pred0 != b { return 0 } 307 return 1 308} 309 310// Recognise ONE complete check site rooted at block index bi, writing its parts into out[]. 311// Returns 1 only when all four structural preconditions hold; 0 otherwise, and 0 always means 312// "leave this alone". 313// Decline with a NAMED reason. `tally` is 1 only on the counting scan, so the two passes over 314// the blocks cannot double-count a rejection. 315func bck_decline(code: i64, tally: i64) -> i64 { 316 if tally == 1 { bck_reason_bump(code) } 317 return 0 318} 319 320func bck_match_site(f: *Function, bi: i64, exit_group_nr: i64, out: *i64, tally: i64) -> i64 { 321 let b: *BasicBlock = block_at(f, bi) 322 let t1: *Instr = b.tail 323 if t1 == (0 as *Instr) { return 0 } 324 // Not tallied: most blocks end in a return or a plain branch, so counting them as 325 // "rejections" would bury the reasons that actually distinguish one shape from another. 326 if t1.op != OP_BR_COND { return 0 } 327 if tally == 1 { g_bck_cand = g_bck_cand + 1 } 328 let d1: *Instr = bck_def_of(f, b, t1.op0) 329 if d1 == (0 as *Instr) { return bck_decline(BCK_R_GE_NOT_FOUND, tally) } 330 if d1.op != OP_GE_S { return bck_decline(BCK_R_NOT_GE, tally) } 331 if bck_val_is_const(f, d1.op1, 0) != 1 { return bck_decline(BCK_R_NOT_ZERO, tally) } 332 let idx: i64 = d1.op0 333 let fail_id: i64 = t1.op2 334 335 let lo_i: i64 = bck_block_index_by_id(f, t1.op1) 336 if lo_i < 0 { return bck_decline(BCK_R_NO_LO, tally) } 337 let lo: *BasicBlock = block_at(f, lo_i) 338 if bck_lo_preds_clean(lo, b) != 1 { return bck_decline(BCK_R_LO_PREDS, tally) } 339 let t2: *Instr = lo.tail 340 if t2 == (0 as *Instr) { return bck_decline(BCK_R_LO_NOT_BRCOND, tally) } 341 if t2.op != OP_BR_COND { return bck_decline(BCK_R_LO_NOT_BRCOND, tally) } 342 if t2.op2 != fail_id { return bck_decline(BCK_R_FAIL_MISMATCH, tally) } 343 let d2: *Instr = bck_def_of(f, lo, t2.op0) 344 if d2 == (0 as *Instr) { return bck_decline(BCK_R_LT_NOT_FOUND, tally) } 345 if d2.op != OP_LT_S { return bck_decline(BCK_R_NOT_LT, tally) } 346 if d2.op0 != idx { return bck_decline(BCK_R_IDX_MISMATCH, tally) } 347 348 let fail_i: i64 = bck_block_index_by_id(f, fail_id) 349 if fail_i < 0 { return bck_decline(BCK_R_NO_FAIL, tally) } 350 let fl: *BasicBlock = block_at(f, fail_i) 351 if bck_fail_is_terminal(f, fl, exit_group_nr) != 1 { return bck_decline(BCK_R_FAIL_NOT_TERM, tally) } 352 353 let ok_i: i64 = bck_block_index_by_id(f, t2.op1) 354 if ok_i < 0 { return bck_decline(BCK_R_NO_OK, tally) } 355 let ok: *BasicBlock = block_at(f, ok_i) 356 if bck_ok_preds_clean(ok, lo, fl) != 1 { return bck_decline(BCK_R_OK_PREDS, tally) } 357 358 if tally == 1 { bck_reason_bump(BCK_R_MATCHED) } 359 out[BCK_O_LO] = lo_i 360 out[BCK_O_OK] = ok_i 361 out[BCK_O_IDX] = idx 362 // d2.op1, NOT t2.op1. t2 is the BRANCH, whose op1 is the true-target BLOCK ID (used just 363 // above to find `ok`); the length is the second operand of the COMPARISON. Reading the 364 // branch operand here keyed every site on a block id reinterpreted as a value id, so the 365 // key was a different arbitrary value at each site -- which is why the pass matched sites 366 // correctly and then elided nothing at all. It failed in the safe direction only by luck: 367 // had two of those garbage keys ever collided, this would have elided a check that was 368 // never proven redundant. Found by the r_nonconst_len tally in one run. 369 out[BCK_O_LEN] = d2.op1 370 return 1 371} 372 373// THE REWRITE. Byte-for-byte the shape opt_sccp_branches already uses to make a branch 374// unconditional (op -> OP_BR, op0 = taken target's BLOCK ID, op1/op2 cleared, n_operands 1), so 375// the optimizer keeps exactly one spelling of that operation rather than growing a second. 376// Nothing is deleted here: the two comparisons simply become dead and opt_dce collects them, 377// and the fail block becomes unreachable and opt_sweep_unreachable_function collects that. 378// Deleting them directly would mean duplicating two passes that already do it correctly. 379func bck_rewrite_site(f: *Function, b_i: i64, lo_i: i64, ok_i: i64) -> i64 { 380 let b: *BasicBlock = block_at(f, b_i) 381 let lo: *BasicBlock = block_at(f, lo_i) 382 let ok: *BasicBlock = block_at(f, ok_i) 383 let t1: *Instr = b.tail 384 if t1 == (0 as *Instr) { return 0 } 385 let t2: *Instr = lo.tail 386 if t2 == (0 as *Instr) { return 0 } 387 t1.op = OP_BR 388 t1.op0 = lo.id 389 t1.op1 = 0 390 t1.op2 = 0 391 t1.n_operands = 1 392 t2.op = OP_BR 393 t2.op0 = ok.id 394 t2.op1 = 0 395 t2.op2 = 0 396 t2.n_operands = 1 397 return 1 398} 399 400// THE REFUSAL REPORT, to stderr, once per function that contained at least one conditional 401// branch, and only while the declared mode is live. A pass that matches nothing otherwise 402// prints exactly the zero a pass that was never reached prints -- which is the state this one 403// was in on its first run, and reading this line is what located the cause in a single run 404// instead of a guess. The per-function figures are local; every r_* figure is CUMULATIVE for 405// the whole compile, so the LAST line emitted is the whole-compile summary. 406func bck_report(fn_blocks: i64, cand_here: i64, sites_here: i64, elided_here: i64) -> i64 { 407 if g_bckelide_live != 1 { return 0 } 408 if cand_here == 0 { return 0 } 409 bck_ekv("BCK-ELIDE blocks=" as *u8, fn_blocks) 410 bck_ekv(" cand=" as *u8, cand_here) 411 bck_ekv(" sites=" as *u8, sites_here) 412 bck_ekv(" elided=" as *u8, elided_here) 413 bck_ekv(" cum_sites=" as *u8, g_bck_sites) 414 bck_ekv(" cum_elided=" as *u8, g_bck_elided) 415 bck_ereason(" r_ge_not_found=" as *u8, BCK_R_GE_NOT_FOUND) 416 bck_ereason(" r_not_ge=" as *u8, BCK_R_NOT_GE) 417 bck_ereason(" r_not_zero=" as *u8, BCK_R_NOT_ZERO) 418 bck_ereason(" r_no_lo=" as *u8, BCK_R_NO_LO) 419 bck_ereason(" r_lo_preds=" as *u8, BCK_R_LO_PREDS) 420 bck_ereason(" r_lo_not_brcond=" as *u8, BCK_R_LO_NOT_BRCOND) 421 bck_ereason(" r_fail_mismatch=" as *u8, BCK_R_FAIL_MISMATCH) 422 bck_ereason(" r_lt_not_found=" as *u8, BCK_R_LT_NOT_FOUND) 423 bck_ereason(" r_not_lt=" as *u8, BCK_R_NOT_LT) 424 bck_ereason(" r_idx_mismatch=" as *u8, BCK_R_IDX_MISMATCH) 425 bck_ereason(" r_no_fail=" as *u8, BCK_R_NO_FAIL) 426 bck_ereason(" r_fail_not_terminal=" as *u8, BCK_R_FAIL_NOT_TERM) 427 bck_ereason(" r_no_ok=" as *u8, BCK_R_NO_OK) 428 bck_ereason(" r_ok_preds=" as *u8, BCK_R_OK_PREDS) 429 bck_ereason(" r_matched=" as *u8, BCK_R_MATCHED) 430 bck_ekv(" r_nonconst_len=" as *u8, g_bck_ref_nolen) 431 bck_ekv(" r_no_dominating_twin=" as *u8, g_bck_ref_nodom) 432 bck_ekv(" declined_pred_truncated=" as *u8, g_bck_decl_preds) 433 bck_eputs("\n" as *u8) 434 return 0 435} 436 437// THE PASS. `info` must be a dominator tree computed from CURRENT edges by the caller (the 438// nx_opt.nx wrapper rebuilds them first, exactly as opt_licm does). 439// 440// WHY ONE DOMINATOR TREE IS ENOUGH FOR THE WHOLE PASS, even though each elision changes the 441// CFG: an elision only ever REMOVES edges (the two branches to `fail`). Removing edges removes 442// paths, and dominance is a statement about all paths -- so every dominance fact true of the 443// original graph is still true of the reduced one. The tree computed at entry is therefore 444// conservative, never stale in the unsafe direction. 445func bck_elide_dominated(f: *Function, info: *DomInfoFn, exit_group_nr: i64) -> i64 { 446 if g_bckelide_live != 1 { return 0 } 447 if exit_group_nr <= 0 { return 0 } 448 if f.n_blocks < 2 { return 0 } 449 450 var tb: i64 = 0 451 while tb < f.n_blocks { 452 let tbb: *BasicBlock = block_at(f, tb) 453 if tbb.n_preds > BCK_PRED_SLOTS { 454 g_bck_decl_preds = g_bck_decl_preds + 1 455 return 0 456 } 457 tb = tb + 1 458 } 459 460 let scratch: *i64 = sys_mmap(BCK_SCRATCH_BYTES) as *i64 461 let cand0: i64 = g_bck_cand 462 463 // Pass 1: COUNT, and attribute every rejection to a named reason. Allocates nothing beyond 464 // the scratch slot, so a function with no re-check to remove -- which is most of them -- 465 // costs one scan and no table at all. 466 var nsite: i64 = 0 467 var bi: i64 = 0 468 while bi < f.n_blocks { 469 if bck_match_site(f, bi, exit_group_nr, scratch, 1) == 1 { nsite = nsite + 1 } 470 bi = bi + 1 471 } 472 g_bck_sites = g_bck_sites + nsite 473 // One check cannot be a RE-check, so a single site is the common honest zero -- reported, 474 // not silent, so it can be told apart from "the pass never ran". 475 if nsite < 2 { 476 bck_report(f.n_blocks, g_bck_cand - cand0, nsite, 0) 477 return 0 478 } 479 480 let nb: i64 = nsite * 8 + 64 481 let s_b: *i64 = sys_mmap(nb) as *i64 482 let s_lo: *i64 = sys_mmap(nb) as *i64 483 let s_ok: *i64 = sys_mmap(nb) as *i64 484 let s_idx: *i64 = sys_mmap(nb) as *i64 485 let s_len: *i64 = sys_mmap(nb) as *i64 486 let s_out: *i64 = sys_mmap(nb) as *i64 487 let cflag: *i64 = sys_mmap(BCK_SCRATCH_BYTES) as *i64 488 489 // Pass 2: COLLECT, keyed by (idx value id, len CONSTANT). A site whose length is not a 490 // constant is dropped from the table entirely, so it can neither be elided nor justify an 491 // elision -- the declared slice refusal, applied in both directions. 492 var n: i64 = 0 493 var bj: i64 = 0 494 while bj < f.n_blocks { 495 if n < nsite { 496 if bck_match_site(f, bj, exit_group_nr, scratch, 0) == 1 { 497 let lc: i64 = bck_const_of(f, scratch[BCK_O_LEN], cflag) 498 if cflag[0] == 1 { 499 s_b[n] = bj 500 s_lo[n] = scratch[BCK_O_LO] 501 s_ok[n] = scratch[BCK_O_OK] 502 s_idx[n] = scratch[BCK_O_IDX] 503 s_len[n] = lc 504 s_out[n] = 0 505 n = n + 1 506 } 507 if cflag[0] != 1 { g_bck_ref_nolen = g_bck_ref_nolen + 1 } 508 } 509 } 510 bj = bj + 1 511 } 512 513 // Pass 3: DECIDE. For each site, look for a still-live site with the same key whose `ok` 514 // dominates this site's entry. 515 var elided: i64 = 0 516 var si: i64 = 0 517 while si < n { 518 var j: i64 = 0 519 var done: i64 = 0 520 while j < n { 521 if done == 0 { 522 if j != si { 523 // CIRCULAR-JUSTIFICATION GUARD. A site that has itself been elided no 524 // longer performs a comparison, so it cannot be the reason another site is 525 // safe. The dominator tree makes a genuine cycle impossible here (each 526 // site's ok is a descendant of its own b, so mutual justification would 527 // need a block to be its own strict ancestor) -- this guard makes that 528 // argument LOCAL instead of leaving the reader to reconstruct it. 529 if s_out[j] == 0 { 530 if s_idx[j] == s_idx[si] { 531 if s_len[j] == s_len[si] { 532 let okj: *BasicBlock = block_at(f, s_ok[j]) 533 let bsi: *BasicBlock = block_at(f, s_b[si]) 534 if dom_dominates(info, okj, bsi) == 1 { 535 if bck_rewrite_site(f, s_b[si], s_lo[si], s_ok[si]) == 1 { 536 s_out[si] = 1 537 elided = elided + 1 538 g_bck_elided = g_bck_elided + 1 539 done = 1 540 } 541 } 542 } 543 } 544 } 545 } 546 } 547 j = j + 1 548 } 549 if done == 0 { g_bck_ref_nodom = g_bck_ref_nodom + 1 } 550 si = si + 1 551 } 552 bck_report(f.n_blocks, g_bck_cand - cand0, n, elided) 553 return elided 554} 555 556// ============================================================================================ 557// LN7b: INDUCTION-GUARDED ELISION -- bck_elide_induction (2026-09-01, the F1 lane). 558// 559// WHAT THE DOMINANCE PASS ABOVE CANNOT SEE. Measured on the receipt loop that /compare/lang 560// publishes (a [1024]i64 summed 20,000 times): `--bckelide` ran, found 3 candidates and elided 561// NOTHING -- `BCK-ELIDE blocks=10 cand=3 sites=0 elided=0`. The loop carries ONE check per 562// iteration, so there is no "re-check of the same SSA id" for dominance to remove; the fact 563// that proves the check is the LOOP GUARD `k < 1024` in the header, which tests a DIFFERENT 564// load of the same counter. Every iteration then re-loads k, re-tests `k >= 0` and `k < 1024`, 565// and branches twice -- two compares and two branches on a body of eleven instructions. 566// 567// THE THEOREM. Let A be a stack slot (an OP_ALLOCA) such that 568// (a) A NEVER ESCAPES: its id appears only as the ADDRESS operand of a LOAD or a STORE (the 569// same rule opt_licm's licm_alloca_noescape applies). Then no other value id can name 570// that memory, and the only writes to it are the STOREs this pass can see. 571// (b) the first instruction touching A after its alloca, in the alloca's own block, is a 572// STORE of a constant c0 with 0 <= c0 <= BCK_IV_MAX_CONST (the initialiser), and no LOAD 573// of A precedes it there; 574// (c) EVERY STORE to A writes either a constant c with 0 <= c <= BCK_IV_MAX_CONST, or 575// LOAD(A) + c with 0 <= c <= BCK_IV_MAX_CONST, and every store of the second kind is 576// GUARDED: some `LOAD(A) <s L'` (L' a constant, L' <= BCK_IV_MAX_CONST) whose TRUE edge 577// dominates the store, with no store to A on any path from that edge to the store. 578// Then by induction on the stores, at every point of the function 0 <= A < 2^61: a reset writes 579// a small non-negative constant, and an increment adds at most 2^60 to a value the guard just 580// proved below 2^60, so no store ever wraps. Hence A >= 0 everywhere, which discharges the 581// site's `idx >= 0` leg for idx = LOAD(A). 582// For the `idx < len` leg: if a guard `LOAD(A) <s L` with L <= len has a TRUE edge T that 583// DOMINATES the site block, and no STORE to A can execute on any path from T's entry to the 584// site's own load of idx, then the value the guard tested is the value the site loads, and it 585// is below L <= len. Both comparisons can only answer true, so making the two branches 586// unconditional changes no observable behaviour -- the same rewrite the dominance pass uses. 587// 588// WHERE THE FIELD IS. LLVM's InductiveRangeCheckElimination splits the iteration space 589// (a pre-loop, a check-free main loop and a post-loop) so it can drop checks whose bound is not 590// implied by the guard; Go's prove pass carries per-value limit lattices through the CFG 591// (knowledge/fetched/cmp_lang_llvm_irce.cpp, cmp_lang_go_prove.go, both mirrored and pinned in 592// lang.refs). This pass is DELIBERATELY the smaller theorem: it removes a check only where the 593// loop guard's bound already implies it, adds no code, splits no loop, and its proof fits in 594// one screen. The IRCE split is the next rung, named in lang.plan, not smuggled in here. 595// 596// WRONG IN THE DIRECTION OF KEEPING THE CHECK, BY CONSTRUCTION -- every predicate below is a 597// reason to elide; every unrecognised shape keeps the check, and every refusal is NAMED and 598// tallied on stderr, because a refusing run and a run that never happened print the same zero. 599// 600// DECLARED IMPRECISION, each sound in the do-nothing direction: 601// * the site's load of idx must sit IN the site's own block (the freshly emitted shape); a 602// load hoisted elsewhere is refused (r_iv_load_not_local) rather than reasoned about; 603// * the guard must be `LOAD(A) <s CONST` at a block's terminator, with no store to A between 604// that load and the branch; `CONST >s LOAD(A)`, `<=`, unsigned and slice lengths are all 605// refused -- a slice length is loaded, not constant, and stays exactly as declared above; 606// * reachability is over succ0/succ1 and pred0..pred2, and a function whose pred lists are 607// truncated is refused whole, as the dominance pass and opt_licm already refuse it; 608// * a block on the guard-to-site path is treated as store-carrying if it stores to A 609// ANYWHERE in it, prefix or suffix -- a whole-block over-approximation that can only 610// refuse a valid elision. 611// ============================================================================================ 612const BCK_IV_MAX_CONST: i64 = 1152921504606846976 // 2^60: guard bound + increment stays far below 2^63 613const BCK_R_IV_LOAD_NOT_LOCAL: i64 = 16 614const BCK_R_IV_NOT_LOAD: i64 = 17 615const BCK_R_IV_NOT_ALLOCA: i64 = 18 616const BCK_R_IV_ESCAPES: i64 = 19 617const BCK_R_IV_NO_INIT: i64 = 20 618const BCK_R_IV_BAD_STORE: i64 = 21 619const BCK_R_IV_INC_UNGUARDED: i64 = 22 620const BCK_R_IV_NO_GUARD: i64 = 23 621const BCK_R_IV_STORE_ON_PATH: i64 = 24 622const BCK_R_IV_MATCHED: i64 = 25 623const BCK_IV_OPERAND_SLOTS: i64 = 24 624 625static g_bck_iv_sites: i64 626static g_bck_iv_elided: i64 627func bck_stat_iv_sites() -> i64 { return g_bck_iv_sites } 628func bck_stat_iv_elided() -> i64 { return g_bck_iv_elided } 629 630// operand k of an instruction. A local twin of nx_opt.nx's opt_opk: that file IMPORTS this one, 631// and NishiLang resolves names in textual order, so the optimizer's copy is not visible here. 632func bck_iv_opk(inst: *Instr, k: i64) -> i64 { 633 if k == 0 { return inst.op0 } 634 if k == 1 { return inst.op1 } 635 if k == 2 { return inst.op2 } 636 if k == 3 { return inst.op3 } 637 if k == 4 { return inst.op4 } 638 if k == 5 { return inst.op5 } 639 if k == 6 { return inst.op6 } 640 if k == 7 { return inst.op7 } 641 if k == 8 { return inst.op8 } 642 if k == 9 { return inst.op9 } 643 if k == 10 { return inst.op10 } 644 if k == 11 { return inst.op11 } 645 if k == 12 { return inst.op12 } 646 if k == 13 { return inst.op13 } 647 if k == 14 { return inst.op14 } 648 if k == 15 { return inst.op15 } 649 if k == 16 { return inst.op16 } 650 if k == 17 { return inst.op17 } 651 if k == 18 { return inst.op18 } 652 if k == 19 { return inst.op19 } 653 if k == 20 { return inst.op20 } 654 if k == 21 { return inst.op21 } 655 if k == 22 { return inst.op22 } 656 if k == 23 { return inst.op23 } 657 return 0 - 1 658} 659 660// The defining instruction of value id v anywhere in f, or null. 661func bck_iv_def(f: *Function, v: i64) -> *Instr { 662 if v < 0 { return 0 as *Instr } 663 if v >= f.n_values { return 0 as *Instr } 664 return bck_def_of(f, block_at(f, 0), v) 665} 666 667// (a) A NEVER ESCAPES -- the licm_alloca_noescape rule, restated (see bck_iv_opk for why). 668func bck_iv_noescape(f: *Function, aid: i64) -> i64 { 669 var bi: i64 = 0 670 while bi < f.n_blocks { 671 let b: *BasicBlock = block_at(f, bi) 672 var inst: *Instr = b.head 673 while inst != (0 as *Instr) { 674 var no: i64 = inst.n_operands 675 if no > BCK_IV_OPERAND_SLOTS { no = BCK_IV_OPERAND_SLOTS } 676 var k: i64 = 0 677 while k < no { 678 // A terminator's target operands are BLOCK IDS, not value ids: OP_BR op0 and 679 // OP_BR_COND op1/op2 name blocks, and a block number that happens to equal an 680 // alloca's value id is not a use of it. MEASURED on the first probe: the init 681 // loop's counter (alloca id 2) was refused as escaping because the loop's own 682 // `br_cond ... -> block 2` carried the number 2. Skipped by position, never by 683 // value, so the check stays exact for every real operand. 684 var isblk: i64 = 0 685 if inst.op == OP_BR { if k == 0 { isblk = 1 } } 686 if inst.op == OP_BR_COND { if k == 1 { isblk = 1 } if k == 2 { isblk = 1 } } 687 if isblk == 0 { if bck_iv_opk(inst, k) == aid { 688 var okpos: i64 = 0 689 if inst.op == OP_LOAD { if k == 0 { okpos = 1 } } 690 if inst.op == OP_STORE { if k == 0 { okpos = 1 } } 691 if okpos == 0 { return 0 } 692 } } 693 k = k + 1 694 } 695 inst = inst.next 696 } 697 bi = bi + 1 698 } 699 return 1 700} 701 702// v is a constant in [0, BCK_IV_MAX_CONST]; out[0] receives it 703func bck_iv_small_const(f: *Function, v: i64, out: *i64) -> i64 { 704 let fl: *i64 = sys_mmap(16) as *i64 705 let c: i64 = bck_const_of(f, v, fl) 706 if fl[0] != 1 { return 0 } 707 if c < 0 { return 0 } 708 if c > BCK_IV_MAX_CONST { return 0 } 709 out[0] = c 710 return 1 711} 712 713// v is LOAD(aid) 714func bck_iv_is_load_of(f: *Function, v: i64, aid: i64) -> i64 { 715 let d: *Instr = bck_iv_def(f, v) 716 if d == (0 as *Instr) { return 0 } 717 if d.op != OP_LOAD { return 0 } 718 if d.op0 != aid { return 0 } 719 return 1 720} 721 722// (c) classify one STORE to aid: 1 reset (small non-negative constant), 2 increment 723// (LOAD(aid) + small non-negative constant, either operand order), 0 anything else. 724func bck_iv_store_kind(f: *Function, st: *Instr, aid: i64) -> i64 { 725 let c: *i64 = sys_mmap(16) as *i64 726 if bck_iv_small_const(f, st.op1, c) == 1 { return 1 } 727 let d: *Instr = bck_iv_def(f, st.op1) 728 if d == (0 as *Instr) { return 0 } 729 if d.op != OP_ADD { return 0 } 730 if bck_iv_is_load_of(f, d.op0, aid) == 1 { if bck_iv_small_const(f, d.op1, c) == 1 { return 2 } } 731 if bck_iv_is_load_of(f, d.op1, aid) == 1 { if bck_iv_small_const(f, d.op0, c) == 1 { return 2 } } 732 return 0 733} 734 735// (b) the initialiser: after the alloca, in its own block, the first touch of aid is a reset store 736func bck_iv_init_ok(f: *Function, aid: i64) -> i64 { 737 let ad: *Instr = bck_iv_def(f, aid) 738 if ad == (0 as *Instr) { return 0 } 739 if ad.op != OP_ALLOCA { return 0 } 740 let c: *i64 = sys_mmap(16) as *i64 741 var inst: *Instr = ad.next 742 while inst != (0 as *Instr) { 743 if inst.op == OP_LOAD { if inst.op0 == aid { return 0 } } 744 if inst.op == OP_STORE { if inst.op0 == aid { 745 if bck_iv_small_const(f, inst.op1, c) == 1 { return 1 } 746 return 0 747 } } 748 inst = inst.next 749 } 750 return 0 751} 752 753func bck_iv_block_has_store(b: *BasicBlock, aid: i64) -> i64 { 754 var inst: *Instr = b.head 755 while inst != (0 as *Instr) { 756 if inst.op == OP_STORE { if inst.op0 == aid { return 1 } } 757 inst = inst.next 758 } 759 return 0 760} 761 762func bck_iv_push_succ(f: *Function, s: *BasicBlock, t_i: i64, mark: *u8, stack: *i64, sp: *i64) -> i64 { 763 if s == (0 as *BasicBlock) { return 0 } 764 let si: i64 = df_block_index(f, s) 765 if si < 0 { return 0 } 766 if si == t_i { return 0 } 767 if mark[si] != (0 as u8) { return 0 } 768 mark[si] = 1 as u8 769 stack[sp[0]] = si 770 sp[0] = sp[0] + 1 771 return 1 772} 773 774// FORWARD: every block reachable from T's successors without re-entering T. 775func bck_iv_mark_fwd(f: *Function, t_i: i64, mark: *u8, stack: *i64) -> i64 { 776 var z: i64 = 0 777 while z < f.n_blocks { mark[z] = 0 as u8; z = z + 1 } 778 let sp: *i64 = sys_mmap(16) as *i64 779 sp[0] = 0 780 let tb: *BasicBlock = block_at(f, t_i) 781 bck_iv_push_succ(f, tb.succ0, t_i, mark, stack, sp) 782 bck_iv_push_succ(f, tb.succ1, t_i, mark, stack, sp) 783 while sp[0] > 0 { 784 sp[0] = sp[0] - 1 785 let x: i64 = stack[sp[0]] 786 let xb: *BasicBlock = block_at(f, x) 787 bck_iv_push_succ(f, xb.succ0, t_i, mark, stack, sp) 788 bck_iv_push_succ(f, xb.succ1, t_i, mark, stack, sp) 789 } 790 return 0 791} 792 793func bck_iv_push_pred(f: *Function, p: *BasicBlock, t_i: i64, mark: *u8, stack: *i64, sp: *i64) -> i64 { 794 if p == (0 as *BasicBlock) { return 0 } 795 let pi: i64 = df_block_index(f, p) 796 if pi < 0 { return 0 } 797 if pi == t_i { return 0 } 798 if mark[pi] != (0 as u8) { return 0 } 799 mark[pi] = 1 as u8 800 stack[sp[0]] = pi 801 sp[0] = sp[0] + 1 802 return 1 803} 804 805// BACKWARD: every block from which dst is reachable without passing through T (dst itself marked). 806func bck_iv_mark_bwd(f: *Function, t_i: i64, dst_i: i64, mark: *u8, stack: *i64) -> i64 { 807 var z: i64 = 0 808 while z < f.n_blocks { mark[z] = 0 as u8; z = z + 1 } 809 let sp: *i64 = sys_mmap(16) as *i64 810 sp[0] = 0 811 mark[dst_i] = 1 as u8 812 stack[0] = dst_i 813 sp[0] = 1 814 while sp[0] > 0 { 815 sp[0] = sp[0] - 1 816 let x: i64 = stack[sp[0]] 817 let xb: *BasicBlock = block_at(f, x) 818 if xb.n_preds > 0 { bck_iv_push_pred(f, xb.pred0, t_i, mark, stack, sp) } 819 if xb.n_preds > 1 { bck_iv_push_pred(f, xb.pred1, t_i, mark, stack, sp) } 820 if xb.n_preds > 2 { bck_iv_push_pred(f, xb.pred2, t_i, mark, stack, sp) } 821 } 822 return 0 823} 824 825// 1 iff no STORE to aid can execute on any path from T's entry to `stop` (exclusive) in dst. 826func bck_iv_store_free(f: *Function, t_i: i64, dst_i: i64, aid: i64, stop: *Instr, fwd: *u8, bwd: *u8, stack: *i64) -> i64 { 827 let db: *BasicBlock = block_at(f, dst_i) 828 var inst: *Instr = db.head 829 while inst != (0 as *Instr) { 830 if inst == stop { break } 831 if inst.op == OP_STORE { if inst.op0 == aid { return 0 } } 832 inst = inst.next 833 } 834 // straight from the guard's true edge into this very block: only the prefix is on the path 835 if t_i == dst_i { return 1 } 836 // T is entered from the guard; a store anywhere in it is on the path (whole-block, conservative) 837 if bck_iv_block_has_store(block_at(f, t_i), aid) == 1 { return 0 } 838 bck_iv_mark_fwd(f, t_i, fwd, stack) 839 bck_iv_mark_bwd(f, t_i, dst_i, bwd, stack) 840 // dst can re-enter itself without passing T only through a successor that reaches dst without T; 841 // then dst's OWN suffix stores lie on a path to stop as well -- refuse if dst stores at all 842 var cyc: i64 = 0 843 if db.succ0 != (0 as *BasicBlock) { let s0: i64 = df_block_index(f, db.succ0); if s0 >= 0 { if s0 != t_i { if bwd[s0] != (0 as u8) { cyc = 1 } } } } 844 if db.succ1 != (0 as *BasicBlock) { let s1: i64 = df_block_index(f, db.succ1); if s1 >= 0 { if s1 != t_i { if bwd[s1] != (0 as u8) { cyc = 1 } } } } 845 if cyc == 1 { if bck_iv_block_has_store(db, aid) == 1 { return 0 } } 846 var x: i64 = 0 847 while x < f.n_blocks { 848 if x != t_i { if x != dst_i { if fwd[x] != (0 as u8) { if bwd[x] != (0 as u8) { 849 if bck_iv_block_has_store(block_at(f, x), aid) == 1 { return 0 } 850 } } } } 851 x = x + 1 852 } 853 return 1 854} 855 856// A guard: a block whose terminator is BR_COND on `LOAD(aid) <s L'` with L' <= limit, whose TRUE 857// edge dominates dst, and with no store to aid between that load and the branch. Returns the 858// TRUE-edge block index, or -1. 859func bck_iv_find_guard(f: *Function, info: *DomInfoFn, aid: i64, limit: i64, dst: *BasicBlock) -> i64 { 860 let c: *i64 = sys_mmap(16) as *i64 861 var gi: i64 = 0 862 while gi < f.n_blocks { 863 let g: *BasicBlock = block_at(f, gi) 864 let t: *Instr = g.tail 865 if t != (0 as *Instr) { if t.op == OP_BR_COND { 866 let d: *Instr = bck_def_of(f, g, t.op0) 867 if d != (0 as *Instr) { if d.op == OP_LT_S { 868 if bck_iv_is_load_of(f, d.op0, aid) == 1 { if bck_iv_small_const(f, d.op1, c) == 1 { if c[0] <= limit { 869 // the tested load must live in g, and nothing may store to aid between it and the branch 870 let ld: *Instr = bck_def_in_block(g, d.op0) 871 if ld != (0 as *Instr) { 872 var clean: i64 = 1 873 var s: *Instr = ld.next 874 while s != (0 as *Instr) { 875 if s.op == OP_STORE { if s.op0 == aid { clean = 0 } } 876 s = s.next 877 } 878 if clean == 1 { 879 let ti: i64 = bck_block_index_by_id(f, t.op1) 880 if ti >= 0 { if dom_dominates(info, block_at(f, ti), dst) == 1 { return ti } } 881 } 882 } 883 } } } 884 } } 885 } } 886 gi = gi + 1 887 } 888 return 0 - 1 889} 890 891// One site: returns BCK_R_IV_MATCHED or the named refusal. 892func bck_iv_check(f: *Function, info: *DomInfoFn, b: *BasicBlock, bi: i64, ld: *Instr, lc: i64, fwd: *u8, bwd: *u8, stack: *i64) -> i64 { 893 if ld == (0 as *Instr) { return BCK_R_IV_LOAD_NOT_LOCAL } 894 if ld.op != OP_LOAD { return BCK_R_IV_NOT_LOAD } 895 let aid: i64 = ld.op0 896 let ad: *Instr = bck_iv_def(f, aid) 897 if ad == (0 as *Instr) { return BCK_R_IV_NOT_ALLOCA } 898 if ad.op != OP_ALLOCA { return BCK_R_IV_NOT_ALLOCA } 899 if bck_iv_noescape(f, aid) != 1 { return BCK_R_IV_ESCAPES } 900 if bck_iv_init_ok(f, aid) != 1 { return BCK_R_IV_NO_INIT } 901 var sb: i64 = 0 902 while sb < f.n_blocks { 903 let xb: *BasicBlock = block_at(f, sb) 904 var inst: *Instr = xb.head 905 while inst != (0 as *Instr) { 906 if inst.op == OP_STORE { if inst.op0 == aid { 907 let k: i64 = bck_iv_store_kind(f, inst, aid) 908 if k == 0 { return BCK_R_IV_BAD_STORE } 909 if k == 2 { 910 let ti2: i64 = bck_iv_find_guard(f, info, aid, BCK_IV_MAX_CONST, xb) 911 if ti2 < 0 { return BCK_R_IV_INC_UNGUARDED } 912 if bck_iv_store_free(f, ti2, sb, aid, inst, fwd, bwd, stack) != 1 { return BCK_R_IV_INC_UNGUARDED } 913 } 914 } } 915 inst = inst.next 916 } 917 sb = sb + 1 918 } 919 let ti: i64 = bck_iv_find_guard(f, info, aid, lc, b) 920 if ti < 0 { return BCK_R_IV_NO_GUARD } 921 if bck_iv_store_free(f, ti, bi, aid, ld, fwd, bwd, stack) != 1 { return BCK_R_IV_STORE_ON_PATH } 922 return BCK_R_IV_MATCHED 923} 924 925func bck_iv_report(fn_blocks: i64, cand: i64, elided: i64) -> i64 { 926 if g_bckelide_live != 1 { return 0 } 927 if cand == 0 { return 0 } 928 bck_ekv("BCK-ELIDE-IV blocks=" as *u8, fn_blocks) 929 bck_ekv(" cand=" as *u8, cand) 930 bck_ekv(" elided=" as *u8, elided) 931 bck_ekv(" cum_iv_sites=" as *u8, g_bck_iv_sites) 932 bck_ekv(" cum_iv_elided=" as *u8, g_bck_iv_elided) 933 bck_ereason(" r_iv_load_not_local=" as *u8, BCK_R_IV_LOAD_NOT_LOCAL) 934 bck_ereason(" r_iv_not_load=" as *u8, BCK_R_IV_NOT_LOAD) 935 bck_ereason(" r_iv_not_alloca=" as *u8, BCK_R_IV_NOT_ALLOCA) 936 bck_ereason(" r_iv_escapes=" as *u8, BCK_R_IV_ESCAPES) 937 bck_ereason(" r_iv_no_init=" as *u8, BCK_R_IV_NO_INIT) 938 bck_ereason(" r_iv_bad_store=" as *u8, BCK_R_IV_BAD_STORE) 939 bck_ereason(" r_iv_inc_unguarded=" as *u8, BCK_R_IV_INC_UNGUARDED) 940 bck_ereason(" r_iv_no_guard=" as *u8, BCK_R_IV_NO_GUARD) 941 bck_ereason(" r_iv_store_on_path=" as *u8, BCK_R_IV_STORE_ON_PATH) 942 bck_ereason(" r_iv_matched=" as *u8, BCK_R_IV_MATCHED) 943 bck_eputs("\n" as *u8) 944 return 0 945} 946 947// THE PASS. Same contract as bck_elide_dominated: `info` is a dominator tree over CURRENT 948// edges; an elision only removes edges, so the tree stays conservative for the whole pass. 949// Runs on every matched site whose length is a compile-time constant; a site the dominance pass 950// already rewrote is no longer a BR_COND site and is simply not matched again. 951func bck_elide_induction(f: *Function, info: *DomInfoFn, exit_group_nr: i64) -> i64 { 952 if g_bckelide_live != 1 { return 0 } 953 if exit_group_nr <= 0 { return 0 } 954 if f.n_blocks < 2 { return 0 } 955 var tb: i64 = 0 956 while tb < f.n_blocks { 957 let tbb: *BasicBlock = block_at(f, tb) 958 if tbb.n_preds > BCK_PRED_SLOTS { g_bck_decl_preds = g_bck_decl_preds + 1; return 0 } 959 tb = tb + 1 960 } 961 let scratch: *i64 = sys_mmap(BCK_SCRATCH_BYTES) as *i64 962 let cflag: *i64 = sys_mmap(16) as *i64 963 let fwd: *u8 = sys_mmap(f.n_blocks + 16) 964 let bwd: *u8 = sys_mmap(f.n_blocks + 16) 965 let stack: *i64 = sys_mmap(f.n_blocks * 8 + 64) as *i64 966 var elided: i64 = 0 967 var cand: i64 = 0 968 var bi: i64 = 0 969 while bi < f.n_blocks { 970 if bck_match_site(f, bi, exit_group_nr, scratch, 0) == 1 { 971 let lc: i64 = bck_const_of(f, scratch[BCK_O_LEN], cflag) 972 if cflag[0] == 1 { 973 cand = cand + 1 974 let b: *BasicBlock = block_at(f, bi) 975 let ld: *Instr = bck_def_in_block(b, scratch[BCK_O_IDX]) 976 let r: i64 = bck_iv_check(f, info, b, bi, ld, lc, fwd, bwd, stack) 977 bck_reason_bump(r) 978 if r == BCK_R_IV_MATCHED { 979 if bck_rewrite_site(f, bi, scratch[BCK_O_LO], scratch[BCK_O_OK]) == 1 { 980 elided = elided + 1 981 g_bck_iv_elided = g_bck_iv_elided + 1 982 } 983 } 984 } 985 } 986 bi = bi + 1 987 } 988 g_bck_iv_sites = g_bck_iv_sites + cand 989 bck_iv_report(f.n_blocks, cand, elided) 990 sys_munmap(fwd, f.n_blocks + 16) 991 sys_munmap(bwd, f.n_blocks + 16) 992 sys_munmap(stack as *u8, f.n_blocks * 8 + 64) 993 return elided 994}