nx_dom_fn.nx source
↩ module page · 285 lines · 11109 B
1// dom_fn.nx -- dominator tree on *Function (opt.nx consumer).
2//
3// Separate from dom.nx (which operates on a local Block type
4// declared in that file). dom_fn computes immediate dominators
5// directly on the runtime's shared BasicBlock struct so opt.nx
6// passes (LICM next) can consume it without type translation.
7//
8// Algorithm: Cooper-Harvey-Kennedy "A Simple, Fast Dominance
9// Algorithm" (2001). O(N * E * alpha) in practice, trivial
10// implementation compared to Lengauer-Tarjan.
11//
12// Invariants:
13// DF1 Entry block is its own idom by convention.
14// DF2 Unreachable blocks have idom == NULL. Callers should
15// run opt_sweep_unreachable_function first if they want
16// every block reachable.
17// DF3 idom[i] is indexed by ARRAY POSITION (block_index), not
18// by block.id. Caller uses block_index() to look up an
19// idom from a BasicBlock pointer.
20// DF4 RPO (reverse-postorder) guarantees every dominator is
21// seen before its dominatees during the fixpoint pass;
22// this is the invariant that makes Cooper-Harvey-Kennedy's
23// iterate-to-fixpoint converge in O(d) where d is max
24// dominator-tree depth.
25
26// nx_safety_envelope:
27// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
28// sil_target: SIL1
29// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
30// verdict: NOT_YET_EVALUATED
31
32import "nx_syscalls.nx"
33import "nx_types.nx"
34import "nx_ir.nx"
35
36// Result bundle: idom pointers indexed by array position, plus
37// RPO ordering so callers can iterate dominatees-before-dominator
38// (or reverse) without recomputing.
39struct DomInfoFn {
40 f: *Function,
41 n: i64, // == f.n_blocks
42 idom: *BasicBlock, // array of n pointers (*BasicBlock-valued)
43 rpo: *BasicBlock, // array of n pointers, RPO order (reachable first)
44 rpo_n: i64, // count of reachable blocks
45 rpo_num: *i64, // block_index -> RPO position, or -1 if unreachable
46}
47
48// Look up a block's array index in f.blocks[]. Linear scan,
49// O(n); fine for small functions. Returns -1 if not found.
50// O(1) since 2026-08-18: blocks live in ONE contiguous pool (ir_block_new hands out slot i at
51// f.blocks + i*96, block_at reads it back the same way), so the index IS the pointer difference.
52// The result is verified against block_at before it is returned -- a pointer outside the pool, or
53// not on a slot boundary, answers -1 exactly as the linear scan did. Semantics identical, and
54// proven so by a byte-identical .s over the whole buildable population (13,202 sources); the
55// scan it replaces sat inside dom_dominates' per-hop loop, which made every dominance query
56// O(depth x blocks) and LICM the largest single cost of every big-function compile
57// (measured: 324 ms of a 472 ms nx_sov_build_run build).
58func df_block_index(f: *Function, bb: *BasicBlock) -> i64 {
59 let base: i64 = f.blocks as i64
60 let off: i64 = (bb as i64) - base
61 if off < 0 { return -1 }
62 if (off % 96) != 0 { return -1 }
63 let i: i64 = off / 96
64 if i >= f.n_blocks { return -1 }
65 if block_at(f, i) != bb { return -1 }
66 return i
67}
68
69// DFS from `b`, visiting successors in inline-slot order. On
70// exit from each recursion level, push onto rpo array. The
71// resulting rpo array, reversed at the end, is the reverse-
72// postorder traversal.
73func df_dfs(f: *Function, b: *BasicBlock,
74 visited: *u8, rpo: *BasicBlock, rpo_n: *i64) -> i64 {
75 let idx: i64 = df_block_index(f, b)
76 if idx < 0 { return 0 }
77 if visited[idx] == 1 { return 0 }
78 visited[idx] = 1
79 if b.succ0 != (0 as *BasicBlock) {
80 df_dfs(f, b.succ0, visited, rpo, rpo_n)
81 }
82 if b.succ1 != (0 as *BasicBlock) {
83 df_dfs(f, b.succ1, visited, rpo, rpo_n)
84 }
85 let n: i64 = *rpo_n
86 // rpo is an array of BasicBlock* stored as 8-byte slots; we
87 // write them via pointer arithmetic since NishiLang lacks a
88 // *BasicBlock -> i64 slot array primitive.
89 let rpo_base: i64 = rpo as i64
90 let slot: *i64 = (rpo_base + n * 8) as *i64
91 *slot = b as i64
92 *rpo_n = n + 1
93 return 0
94}
95
96// Walk up the idom chain of two blocks until they meet.
97// Parameters: idom_by_rpo is the current idom array keyed by
98// RPO position; rpo_num maps block_index to RPO position. Both
99// b1 and b2 are array indices of blocks (not RPO positions).
100func df_intersect(idom_arr: *i64, rpo_num: *i64,
101 b1: i64, b2: i64) -> i64 {
102 var a: i64 = b1
103 var b: i64 = b2
104 while a != b {
105 while rpo_num[a] > rpo_num[b] {
106 a = idom_arr[a]
107 if a < 0 { return b }
108 }
109 while rpo_num[b] > rpo_num[a] {
110 b = idom_arr[b]
111 if b < 0 { return a }
112 }
113 }
114 return a
115}
116
117// Main entry: compute immediate dominators for every block in f.
118// Returns 0 on success, negative on allocation failure. Caller
119// passes in pre-allocated DomInfoFn struct; helper fills arrays.
120func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 {
121 let n: i64 = f.n_blocks
122 info.f = f
123 info.n = n
124 if n == 0 { return 0 }
125
126 // RPO via DFS from entry, then reverse.
127 let visited_raw: *u8 = sys_mmap(n + 16)
128 let visited: *u8 = visited_raw
129 var i: i64 = 0
130 while i < n { visited[i] = 0; i = i + 1 }
131 let rpo_fwd_raw: *u8 = sys_mmap(n * 8 + 16)
132 let rpo_fwd: *BasicBlock = rpo_fwd_raw as *BasicBlock
133 let rpo_n_raw: *u8 = sys_mmap(16)
134 let rpo_n_p: *i64 = rpo_n_raw as *i64
135 *rpo_n_p = 0
136 df_dfs(f, f.entry, visited, rpo_fwd, rpo_n_p)
137 let rpo_count: i64 = *rpo_n_p
138
139 // Reverse the postorder array in place.
140 let rpo_raw: *u8 = sys_mmap(n * 8 + 16)
141 let rpo: *BasicBlock = rpo_raw as *BasicBlock
142 let rpo_base: i64 = rpo as i64
143 let rpo_fwd_base: i64 = rpo_fwd as i64
144 i = 0
145 while i < rpo_count {
146 let src_slot: *i64 = (rpo_fwd_base + (rpo_count - 1 - i) * 8) as *i64
147 let dst_slot: *i64 = (rpo_base + i * 8) as *i64
148 *dst_slot = *src_slot
149 i = i + 1
150 }
151 info.rpo = rpo
152 info.rpo_n = rpo_count
153
154 // rpo_num[array_index] = RPO position, or -1.
155 let rpo_num_raw: *u8 = sys_mmap(n * 8 + 16)
156 let rpo_num: *i64 = rpo_num_raw as *i64
157 i = 0
158 while i < n { rpo_num[i] = -1; i = i + 1 }
159 i = 0
160 while i < rpo_count {
161 let slot: *i64 = (rpo_base + i * 8) as *i64
162 // DORMANT-COMPAT (2026-06-10): this read was written as
163 // `*slot as *BasicBlock`, but the pre-fix parser bound the
164 // cast INSIDE the deref (`*(slot as *BasicBlock)`) and a
165 // struct-pointee deref emitted NO LOAD -- so this path has
166 // ALWAYS seen the slot ADDRESS, df_block_index returned -1,
167 // and the stamp silently no-opped. The parse_unary
168 // precedence fix would AWAKEN it; awakened hoist/dominance
169 // decisions broke the self-host (gen3 alias registration),
170 // so the never-live logic has its own latent defects.
171 // Keep the historically-blessed dormant behavior verbatim;
172 // awakening is a named rung with its own gate.
173 let hv1: i64 = slot[0]
174 let bb: *BasicBlock = hv1 as *BasicBlock
175 let idx: i64 = df_block_index(f, bb)
176 if idx >= 0 { rpo_num[idx] = i }
177 i = i + 1
178 }
179 info.rpo_num = rpo_num
180
181 // idom[array_index] = array_index of immediate dominator, or -1
182 // for unreachable / entry. Start: all -1 except entry which
183 // points at itself.
184 let idom_arr_raw: *u8 = sys_mmap(n * 8 + 16)
185 let idom_arr: *i64 = idom_arr_raw as *i64
186 i = 0
187 while i < n { idom_arr[i] = -1; i = i + 1 }
188 let entry_idx: i64 = df_block_index(f, f.entry)
189 idom_arr[entry_idx] = entry_idx
190
191 // Iterate to fixpoint over non-entry reachable blocks in RPO
192 // order. For each block, idom = intersection of idom(preds).
193 var changed: i64 = 1
194 while changed == 1 {
195 changed = 0
196 var ri: i64 = 1 // skip entry (index 0 in RPO)
197 while ri < rpo_count {
198 let slot: *i64 = (rpo_base + ri * 8) as *i64
199 let hv2: i64 = slot[0]
200 let bb: *BasicBlock = hv2 as *BasicBlock
201 let bi: i64 = df_block_index(f, bb)
202 // Find first processed predecessor.
203 var new_idom: i64 = -1
204 var p_idx: i64 = 0
205 // Three pred slots to check.
206 let pred_list: *i64 = sys_mmap(32) as *i64
207 pred_list[0] = bb.pred0 as i64
208 pred_list[1] = bb.pred1 as i64
209 pred_list[2] = bb.pred2 as i64
210 while p_idx < 3 {
211 let p: *BasicBlock = pred_list[p_idx] as *BasicBlock
212 if p != (0 as *BasicBlock) {
213 let p_arr: i64 = df_block_index(f, p)
214 if p_arr >= 0 {
215 if idom_arr[p_arr] >= 0 {
216 if new_idom < 0 { new_idom = p_arr }
217 else {
218 new_idom = df_intersect(idom_arr, rpo_num,
219 new_idom, p_arr)
220 }
221 }
222 }
223 }
224 p_idx = p_idx + 1
225 }
226 if new_idom >= 0 {
227 if idom_arr[bi] != new_idom {
228 idom_arr[bi] = new_idom
229 changed = 1
230 }
231 }
232 ri = ri + 1
233 }
234 }
235
236 // Pack idom_arr into info.idom as BasicBlock pointers (rather
237 // than indices) for caller convenience.
238 let idom_bb_raw: *u8 = sys_mmap(n * 8 + 16)
239 let idom_bb: *BasicBlock = idom_bb_raw as *BasicBlock
240 let idom_bb_base: i64 = idom_bb as i64
241 i = 0
242 while i < n {
243 let dst: *i64 = (idom_bb_base + i * 8) as *i64
244 if idom_arr[i] >= 0 {
245 *dst = block_at(f, idom_arr[i]) as i64
246 } else {
247 *dst = 0
248 }
249 i = i + 1
250 }
251 info.idom = idom_bb
252 return 0
253}
254
255// Returns 1 iff `a` dominates `b`. Walks b's idom chain; reaches
256// a => yes, or reaches entry first => no.
257func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 {
258 if a == b { return 1 }
259 let idom_base: i64 = info.idom as i64
260 var cur_idx: i64 = df_block_index(info.f, b)
261 if cur_idx < 0 { return 0 }
262 var hops: i64 = 0
263 while hops < info.n {
264 let slot: *i64 = (idom_base + cur_idx * 8) as *i64
265 let hv3: i64 = slot[0]
266 let idom_bb: *BasicBlock = hv3 as *BasicBlock
267 if idom_bb == a { return 1 }
268 if idom_bb == (0 as *BasicBlock) { return 0 }
269 let next_idx: i64 = df_block_index(info.f, idom_bb)
270 if next_idx == cur_idx { return 0 } // entry's self-loop
271 cur_idx = next_idx
272 hops = hops + 1
273 }
274 return 0
275}
276
277// Compile-only smoke: dom_compute on a nominal function with
278// entry only.
279func main() -> i64 {
280 let info_raw: *u8 = sys_mmap(128)
281 let info: *DomInfoFn = info_raw as *DomInfoFn
282 info.f = 0 as *Function
283 info.n = 0
284 return 0
285}