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