nx_dom.nx source

1// dom.nx -- Cooper-Harvey-Kennedy dominance, in NishiLang. 2// 3// Ports the algorithm in dom.c to NishiLang. This is the first 4// module of the self-hosted compiler: pure graph operations on a 5// CFG, no dependency on ir.c's types. Future integration wraps this 6// so the rest of the compiler can call it. 7// 8// Algorithm summary: 9// 1. Reverse-postorder DFS from entry -> rpo[], rpo_num[]. 10// 2. Iterative dominators until fixed point (CHK 2001). 11// 3. Dominance frontier via Cytron's closed-form walk. 12// 4. Dominator-tree children table for pre-order walks. 13 14// ---- runtime dependencies (inline copies for now) ---- 15 16// ---- CFG representation ---- 17// 18// A miniature CFG for this module. Real integration maps each nxc2 19// BasicBlock to one of these via id. Each Block holds succ / pred 20// index lists as offsets into a side array. 21 22// nx_safety_envelope: 23// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 24// sil_target: SIL1 25// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 26// verdict: NOT_YET_EVALUATED 27 28import "nx_syscalls.nx" 29struct Block { 30 id: i64, 31 n_succs: i64, 32 succ0: i64, // first two succs inline; wider CFGs would use a heap list 33 succ1: i64, 34 n_preds: i64, 35 pred0: i64, 36 pred1: i64, 37 pred2: i64, 38 rpo_num: i64, 39 idom: i64, // index of immediate dominator block, or -1 for entry 40} 41 42// ---- DFS for RPO ---- 43// 44// Visit `b` and recursively visit every successor reachable from it, 45// assigning post-order indices into `post_order` via `*post_idx`. 46 47func rpo_dfs(blocks: *Block, b: i64, 48 visited: *u8, post_order: *i64, post_idx: *i64) -> i64 { 49 if visited[b] != 0 { return 0 } 50 visited[b] = 1 51 let base: i64 = blocks as i64 52 let bb: *Block = (base + b * 80) as *Block 53 let n: i64 = bb.n_succs 54 if n > 0 { rpo_dfs(blocks, bb.succ0, visited, post_order, post_idx) } 55 if n > 1 { rpo_dfs(blocks, bb.succ1, visited, post_order, post_idx) } 56 post_order[*post_idx] = b 57 *post_idx = *post_idx + 1 58 return 0 59} 60 61// ---- intersect two dom chains ---- 62// 63// Walk `b1` and `b2` up their idom links until they meet. Both 64// walks terminate because each step increases the meeting block's 65// rpo_num upper bound. 66 67func dom_intersect(blocks: *Block, b1: i64, b2: i64) -> i64 { 68 let base: i64 = blocks as i64 69 var f1: i64 = b1 70 var f2: i64 = b2 71 while f1 != f2 { 72 while f1 > f2 { 73 let b: *Block = (base + f1 * 80) as *Block 74 f1 = b.idom 75 if f1 < 0 { return -1 } 76 } 77 while f2 > f1 { 78 let b: *Block = (base + f2 * 80) as *Block 79 f2 = b.idom 80 if f2 < 0 { return -1 } 81 } 82 } 83 return f1 84} 85 86// ---- main dominator computation ---- 87// 88// Mutates each Block's idom field to the index of its immediate 89// dominator. `entry` = index of the entry block (usually 0). 90// Assumes all blocks are reachable from entry. 91 92func dom_compute(blocks: *Block, n_blocks: i64, entry: i64) -> i64 { 93 // --- DFS to build post-order then RPO numbering --- 94 let visited: *u8 = sys_mmap(n_blocks + 8) 95 let post_raw: *u8 = sys_mmap(n_blocks * 8 + 16) 96 let post: *i64 = post_raw as *i64 97 let idx_raw: *u8 = sys_mmap(8) 98 let idx: *i64 = idx_raw as *i64 99 *idx = 0 100 rpo_dfs(blocks, entry, visited, post, idx) 101 let n_reached: i64 = *idx 102 103 let base: i64 = blocks as i64 104 105 // Assign rpo_num; entry gets 0, next block 1, ... 106 var i: i64 = 0 107 while i < n_reached { 108 let rpo_i: i64 = n_reached - 1 - i 109 let b: *Block = (base + post[i] * 80) as *Block 110 b.rpo_num = rpo_i 111 i = i + 1 112 } 113 114 // Initialize idom: entry dominates itself; everyone else -1. 115 var j: i64 = 0 116 while j < n_blocks { 117 let b: *Block = (base + j * 80) as *Block 118 b.idom = -1 119 j = j + 1 120 } 121 let eb: *Block = (base + entry * 80) as *Block 122 eb.idom = entry 123 124 // --- CHK iterative fixed point --- 125 var changed: i64 = 1 126 while changed { 127 changed = 0 128 var ri: i64 = 1 129 while ri < n_reached { 130 // Which block has rpo_num == ri? Simplest: linear scan. 131 var bi: i64 = 0 132 var found: i64 = -1 133 while bi < n_blocks { 134 let b: *Block = (base + bi * 80) as *Block 135 if b.rpo_num == ri { found = bi } 136 bi = bi + 1 137 } 138 if found < 0 { ri = ri + 1; continue } 139 let cur: *Block = (base + found * 80) as *Block 140 // Iterate preds; compute intersection. 141 var new_idom: i64 = -1 142 var k: i64 = 0 143 let np: i64 = cur.n_preds 144 while k < np { 145 var pid: i64 = -1 146 if k == 0 { pid = cur.pred0 } 147 if k == 1 { pid = cur.pred1 } 148 if k == 2 { pid = cur.pred2 } 149 if pid >= 0 { 150 let p: *Block = (base + pid * 80) as *Block 151 if p.idom >= 0 { 152 if new_idom < 0 { 153 new_idom = pid 154 } 155 if new_idom >= 0 { 156 if new_idom != pid { 157 new_idom = dom_intersect(blocks, pid, new_idom) 158 } 159 } 160 } 161 } 162 k = k + 1 163 } 164 if new_idom >= 0 { 165 if cur.idom != new_idom { 166 cur.idom = new_idom 167 changed = 1 168 } 169 } 170 ri = ri + 1 171 } 172 } 173 return n_reached 174} 175 176// ---- dominance frontier (Cytron 1991 closed-form) ---- 177// 178// For every join block b (|preds(b)| >= 2), walk each pred's dom 179// chain up until it reaches idom(b), adding b to each walked block's 180// DF. The algorithm is linear in the size of the dominator tree 181// times the number of edges, and writes directly into a flat 182// (df_starts, df_flat) layout so callers can iterate without 183// allocation. 184// 185// Outputs: 186// df_counts[b] = number of blocks for which b is in the frontier 187// df_starts[b] = start index into df_flat where b's DF is listed 188// df_flat[k] = block id in b's frontier 189// df_flat_used = total entries written 190// 191// Caller sizes df_flat >= worst-case sum of (2 * |preds|) across 192// blocks; MAX_BLOCKS * MAX_BLOCKS is an easy safe upper bound. 193 194func df_compute(blocks: *Block, n_blocks: i64, 195 df_counts: *i64, df_starts: *i64, 196 df_flat: *i64, df_flat_cap: i64) -> i64 { 197 let base: i64 = blocks as i64 198 // Pass 1: count DF sizes per block. 199 var b: i64 = 0 200 while b < n_blocks { 201 df_counts[b] = 0 202 b = b + 1 203 } 204 var bi: i64 = 0 205 while bi < n_blocks { 206 let bb: *Block = (base + bi * 80) as *Block 207 let np: i64 = bb.n_preds 208 if np >= 2 { 209 let idom_b: i64 = bb.idom 210 var k: i64 = 0 211 while k < np { 212 var pid: i64 = -1 213 if k == 0 { pid = bb.pred0 } 214 if k == 1 { pid = bb.pred1 } 215 if k == 2 { pid = bb.pred2 } 216 if pid >= 0 { 217 var runner: i64 = pid 218 while runner != idom_b { 219 df_counts[runner] = df_counts[runner] + 1 220 let rb: *Block = (base + runner * 80) as *Block 221 runner = rb.idom 222 if runner < 0 { runner = idom_b } 223 } 224 } 225 k = k + 1 226 } 227 } 228 bi = bi + 1 229 } 230 // Pass 2: prefix sum -> df_starts, clear df_counts for re-fill. 231 var acc: i64 = 0 232 var i: i64 = 0 233 while i < n_blocks { 234 df_starts[i] = acc 235 acc = acc + df_counts[i] 236 df_counts[i] = 0 237 i = i + 1 238 } 239 if acc > df_flat_cap { return -1 } 240 // Pass 3: fill df_flat. 241 var bi2: i64 = 0 242 while bi2 < n_blocks { 243 let bb: *Block = (base + bi2 * 80) as *Block 244 let np: i64 = bb.n_preds 245 if np >= 2 { 246 let idom_b: i64 = bb.idom 247 var k: i64 = 0 248 while k < np { 249 var pid: i64 = -1 250 if k == 0 { pid = bb.pred0 } 251 if k == 1 { pid = bb.pred1 } 252 if k == 2 { pid = bb.pred2 } 253 if pid >= 0 { 254 var runner: i64 = pid 255 while runner != idom_b { 256 let slot: i64 = df_starts[runner] + df_counts[runner] 257 df_flat[slot] = bi2 258 df_counts[runner] = df_counts[runner] + 1 259 let rb: *Block = (base + runner * 80) as *Block 260 runner = rb.idom 261 if runner < 0 { runner = idom_b } 262 } 263 } 264 k = k + 1 265 } 266 } 267 bi2 = bi2 + 1 268 } 269 return acc 270} 271 272// ---- natural-loop detection ---- 273// 274// A back edge is (n -> h) where h dominates n. The natural loop 275// of the back edge is {h} union all blocks from which n is reachable 276// without going through h (Allen-Cocke 1970). 277// 278// Output layout mirrors df_*: loop_counts / loop_starts / loop_flat, 279// indexed by header block b. Headers with no back-edges get count=0. 280 281func loop_detect(blocks: *Block, n_blocks: i64, 282 loop_counts: *i64, loop_starts: *i64, 283 loop_flat: *i64, loop_flat_cap: i64) -> i64 { 284 let base: i64 = blocks as i64 285 // First identify headers and back-edges by scanning succs. 286 // For each edge n -> h, check whether h dominates n via the 287 // idom chain from n. 288 var h: i64 = 0 289 while h < n_blocks { 290 loop_counts[h] = 0 291 h = h + 1 292 } 293 // Per-header worklist: simple re-discovery on each call is fine 294 // for small CFGs. For each (n, h) back-edge, mark h + every 295 // predecessor chain that reaches n without passing through h. 296 // 297 // We first count, then fill. 298 var pass: i64 = 0 299 while pass < 2 { 300 var n_idx: i64 = 0 301 while n_idx < n_blocks { 302 let nb: *Block = (base + n_idx * 80) as *Block 303 let ns: i64 = nb.n_succs 304 var si: i64 = 0 305 while si < ns { 306 var tgt: i64 = -1 307 if si == 0 { tgt = nb.succ0 } 308 if si == 1 { tgt = nb.succ1 } 309 if tgt >= 0 { 310 // Does tgt dominate n_idx? 311 var walker: i64 = n_idx 312 var is_back: i64 = 0 313 while walker >= 0 { 314 if walker == tgt { is_back = 1; walker = -1 } else { 315 let wb: *Block = (base + walker * 80) as *Block 316 if wb.idom == walker { walker = -1 } else { 317 walker = wb.idom 318 } 319 } 320 } 321 if is_back == 1 { 322 // Found back-edge n_idx -> tgt. Enumerate 323 // loop body: BFS backwards from n_idx, 324 // stopping at tgt. We record each member 325 // exactly once by checking loop_flat in the 326 // current header's slice. 327 if pass == 0 { 328 // Counting pass: conservative upper 329 // bound = every block except tgt's 330 // non-members -- but we need exactness 331 // for the flat layout. Use visited 332 // bitmap. 333 let vis: *u8 = sys_mmap(n_blocks + 8) 334 vis[tgt] = 1 335 // count header itself 336 loop_counts[tgt] = loop_counts[tgt] + 1 337 // reverse-walk queue implemented on stack 338 let q_raw: *u8 = sys_mmap(n_blocks * 8 + 16) 339 let q: *i64 = q_raw as *i64 340 q[0] = n_idx 341 var qh: i64 = 0 342 var qt: i64 = 1 343 while qh < qt { 344 let cur: i64 = q[qh] 345 qh = qh + 1 346 if vis[cur] == 0 { 347 vis[cur] = 1 348 loop_counts[tgt] = loop_counts[tgt] + 1 349 // enqueue preds 350 let cb: *Block = (base + cur * 80) as *Block 351 let npp: i64 = cb.n_preds 352 var pk: i64 = 0 353 while pk < npp { 354 var pid: i64 = -1 355 if pk == 0 { pid = cb.pred0 } 356 if pk == 1 { pid = cb.pred1 } 357 if pk == 2 { pid = cb.pred2 } 358 if pid >= 0 { 359 if vis[pid] == 0 { 360 q[qt] = pid 361 qt = qt + 1 362 } 363 } 364 pk = pk + 1 365 } 366 } 367 } 368 } else { 369 // Filling pass -- write into loop_flat. 370 let start: i64 = loop_starts[tgt] 371 var fill: i64 = 0 372 let vis2: *u8 = sys_mmap(n_blocks + 8) 373 vis2[tgt] = 1 374 loop_flat[start + fill] = tgt 375 fill = fill + 1 376 let q2_raw: *u8 = sys_mmap(n_blocks * 8 + 16) 377 let q2: *i64 = q2_raw as *i64 378 q2[0] = n_idx 379 var qh2: i64 = 0 380 var qt2: i64 = 1 381 while qh2 < qt2 { 382 let cur: i64 = q2[qh2] 383 qh2 = qh2 + 1 384 if vis2[cur] == 0 { 385 vis2[cur] = 1 386 loop_flat[start + fill] = cur 387 fill = fill + 1 388 let cb: *Block = (base + cur * 80) as *Block 389 let npp: i64 = cb.n_preds 390 var pk: i64 = 0 391 while pk < npp { 392 var pid: i64 = -1 393 if pk == 0 { pid = cb.pred0 } 394 if pk == 1 { pid = cb.pred1 } 395 if pk == 2 { pid = cb.pred2 } 396 if pid >= 0 { 397 if vis2[pid] == 0 { 398 q2[qt2] = pid 399 qt2 = qt2 + 1 400 } 401 } 402 pk = pk + 1 403 } 404 } 405 } 406 } 407 } 408 } 409 si = si + 1 410 } 411 n_idx = n_idx + 1 412 } 413 if pass == 0 { 414 // After counting, prefix-sum loop_starts and clear counts 415 // for a re-count while filling (counts now double as 416 // fill-offset by construction because we write exactly 417 // loop_counts[tgt] entries per header). 418 var acc: i64 = 0 419 var hh: i64 = 0 420 while hh < n_blocks { 421 loop_starts[hh] = acc 422 acc = acc + loop_counts[hh] 423 hh = hh + 1 424 } 425 if acc > loop_flat_cap { return -1 } 426 } 427 pass = pass + 1 428 } 429 return 0 430} 431 432// Library only; self-test lives in dom_test.nx.