nx_dom_fn.nx source
↩ module page · 275 lines · 10264 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.
50func df_block_index(f: *Function, bb: *BasicBlock) -> i64 {
51 var i: i64 = 0
52 while i < f.n_blocks {
53 if block_at(f, i) == bb { return i }
54 i = i + 1
55 }
56 return -1
57}
58
59// DFS from `b`, visiting successors in inline-slot order. On
60// exit from each recursion level, push onto rpo array. The
61// resulting rpo array, reversed at the end, is the reverse-
62// postorder traversal.
63func df_dfs(f: *Function, b: *BasicBlock,
64 visited: *u8, rpo: *BasicBlock, rpo_n: *i64) -> i64 {
65 let idx: i64 = df_block_index(f, b)
66 if idx < 0 { return 0 }
67 if visited[idx] == 1 { return 0 }
68 visited[idx] = 1
69 if b.succ0 != (0 as *BasicBlock) {
70 df_dfs(f, b.succ0, visited, rpo, rpo_n)
71 }
72 if b.succ1 != (0 as *BasicBlock) {
73 df_dfs(f, b.succ1, visited, rpo, rpo_n)
74 }
75 let n: i64 = *rpo_n
76 // rpo is an array of BasicBlock* stored as 8-byte slots; we
77 // write them via pointer arithmetic since NishiLang lacks a
78 // *BasicBlock -> i64 slot array primitive.
79 let rpo_base: i64 = rpo as i64
80 let slot: *i64 = (rpo_base + n * 8) as *i64
81 *slot = b as i64
82 *rpo_n = n + 1
83 return 0
84}
85
86// Walk up the idom chain of two blocks until they meet.
87// Parameters: idom_by_rpo is the current idom array keyed by
88// RPO position; rpo_num maps block_index to RPO position. Both
89// b1 and b2 are array indices of blocks (not RPO positions).
90func df_intersect(idom_arr: *i64, rpo_num: *i64,
91 b1: i64, b2: i64) -> i64 {
92 var a: i64 = b1
93 var b: i64 = b2
94 while a != b {
95 while rpo_num[a] > rpo_num[b] {
96 a = idom_arr[a]
97 if a < 0 { return b }
98 }
99 while rpo_num[b] > rpo_num[a] {
100 b = idom_arr[b]
101 if b < 0 { return a }
102 }
103 }
104 return a
105}
106
107// Main entry: compute immediate dominators for every block in f.
108// Returns 0 on success, negative on allocation failure. Caller
109// passes in pre-allocated DomInfoFn struct; helper fills arrays.
110func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 {
111 let n: i64 = f.n_blocks
112 info.f = f
113 info.n = n
114 if n == 0 { return 0 }
115
116 // RPO via DFS from entry, then reverse.
117 let visited_raw: *u8 = sys_mmap(n + 16)
118 let visited: *u8 = visited_raw
119 var i: i64 = 0
120 while i < n { visited[i] = 0; i = i + 1 }
121 let rpo_fwd_raw: *u8 = sys_mmap(n * 8 + 16)
122 let rpo_fwd: *BasicBlock = rpo_fwd_raw as *BasicBlock
123 let rpo_n_raw: *u8 = sys_mmap(16)
124 let rpo_n_p: *i64 = rpo_n_raw as *i64
125 *rpo_n_p = 0
126 df_dfs(f, f.entry, visited, rpo_fwd, rpo_n_p)
127 let rpo_count: i64 = *rpo_n_p
128
129 // Reverse the postorder array in place.
130 let rpo_raw: *u8 = sys_mmap(n * 8 + 16)
131 let rpo: *BasicBlock = rpo_raw as *BasicBlock
132 let rpo_base: i64 = rpo as i64
133 let rpo_fwd_base: i64 = rpo_fwd as i64
134 i = 0
135 while i < rpo_count {
136 let src_slot: *i64 = (rpo_fwd_base + (rpo_count - 1 - i) * 8) as *i64
137 let dst_slot: *i64 = (rpo_base + i * 8) as *i64
138 *dst_slot = *src_slot
139 i = i + 1
140 }
141 info.rpo = rpo
142 info.rpo_n = rpo_count
143
144 // rpo_num[array_index] = RPO position, or -1.
145 let rpo_num_raw: *u8 = sys_mmap(n * 8 + 16)
146 let rpo_num: *i64 = rpo_num_raw as *i64
147 i = 0
148 while i < n { rpo_num[i] = -1; i = i + 1 }
149 i = 0
150 while i < rpo_count {
151 let slot: *i64 = (rpo_base + i * 8) as *i64
152 // DORMANT-COMPAT (2026-06-10): this read was written as
153 // `*slot as *BasicBlock`, but the pre-fix parser bound the
154 // cast INSIDE the deref (`*(slot as *BasicBlock)`) and a
155 // struct-pointee deref emitted NO LOAD -- so this path has
156 // ALWAYS seen the slot ADDRESS, df_block_index returned -1,
157 // and the stamp silently no-opped. The parse_unary
158 // precedence fix would AWAKEN it; awakened hoist/dominance
159 // decisions broke the self-host (gen3 alias registration),
160 // so the never-live logic has its own latent defects.
161 // Keep the historically-blessed dormant behavior verbatim;
162 // awakening is a named rung with its own gate.
163 let hv1: i64 = slot[0]
164 let bb: *BasicBlock = hv1 as *BasicBlock
165 let idx: i64 = df_block_index(f, bb)
166 if idx >= 0 { rpo_num[idx] = i }
167 i = i + 1
168 }
169 info.rpo_num = rpo_num
170
171 // idom[array_index] = array_index of immediate dominator, or -1
172 // for unreachable / entry. Start: all -1 except entry which
173 // points at itself.
174 let idom_arr_raw: *u8 = sys_mmap(n * 8 + 16)
175 let idom_arr: *i64 = idom_arr_raw as *i64
176 i = 0
177 while i < n { idom_arr[i] = -1; i = i + 1 }
178 let entry_idx: i64 = df_block_index(f, f.entry)
179 idom_arr[entry_idx] = entry_idx
180
181 // Iterate to fixpoint over non-entry reachable blocks in RPO
182 // order. For each block, idom = intersection of idom(preds).
183 var changed: i64 = 1
184 while changed == 1 {
185 changed = 0
186 var ri: i64 = 1 // skip entry (index 0 in RPO)
187 while ri < rpo_count {
188 let slot: *i64 = (rpo_base + ri * 8) as *i64
189 let hv2: i64 = slot[0]
190 let bb: *BasicBlock = hv2 as *BasicBlock
191 let bi: i64 = df_block_index(f, bb)
192 // Find first processed predecessor.
193 var new_idom: i64 = -1
194 var p_idx: i64 = 0
195 // Three pred slots to check.
196 let pred_list: *i64 = sys_mmap(32) as *i64
197 pred_list[0] = bb.pred0 as i64
198 pred_list[1] = bb.pred1 as i64
199 pred_list[2] = bb.pred2 as i64
200 while p_idx < 3 {
201 let p: *BasicBlock = pred_list[p_idx] as *BasicBlock
202 if p != (0 as *BasicBlock) {
203 let p_arr: i64 = df_block_index(f, p)
204 if p_arr >= 0 {
205 if idom_arr[p_arr] >= 0 {
206 if new_idom < 0 { new_idom = p_arr }
207 else {
208 new_idom = df_intersect(idom_arr, rpo_num,
209 new_idom, p_arr)
210 }
211 }
212 }
213 }
214 p_idx = p_idx + 1
215 }
216 if new_idom >= 0 {
217 if idom_arr[bi] != new_idom {
218 idom_arr[bi] = new_idom
219 changed = 1
220 }
221 }
222 ri = ri + 1
223 }
224 }
225
226 // Pack idom_arr into info.idom as BasicBlock pointers (rather
227 // than indices) for caller convenience.
228 let idom_bb_raw: *u8 = sys_mmap(n * 8 + 16)
229 let idom_bb: *BasicBlock = idom_bb_raw as *BasicBlock
230 let idom_bb_base: i64 = idom_bb as i64
231 i = 0
232 while i < n {
233 let dst: *i64 = (idom_bb_base + i * 8) as *i64
234 if idom_arr[i] >= 0 {
235 *dst = block_at(f, idom_arr[i]) as i64
236 } else {
237 *dst = 0
238 }
239 i = i + 1
240 }
241 info.idom = idom_bb
242 return 0
243}
244
245// Returns 1 iff `a` dominates `b`. Walks b's idom chain; reaches
246// a => yes, or reaches entry first => no.
247func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 {
248 if a == b { return 1 }
249 let idom_base: i64 = info.idom as i64
250 var cur_idx: i64 = df_block_index(info.f, b)
251 if cur_idx < 0 { return 0 }
252 var hops: i64 = 0
253 while hops < info.n {
254 let slot: *i64 = (idom_base + cur_idx * 8) as *i64
255 let hv3: i64 = slot[0]
256 let idom_bb: *BasicBlock = hv3 as *BasicBlock
257 if idom_bb == a { return 1 }
258 if idom_bb == (0 as *BasicBlock) { return 0 }
259 let next_idx: i64 = df_block_index(info.f, idom_bb)
260 if next_idx == cur_idx { return 0 } // entry's self-loop
261 cur_idx = next_idx
262 hops = hops + 1
263 }
264 return 0
265}
266
267// Compile-only smoke: dom_compute on a nominal function with
268// entry only.
269func main() -> i64 {
270 let info_raw: *u8 = sys_mmap(128)
271 let info: *DomInfoFn = info_raw as *DomInfoFn
272 info.f = 0 as *Function
273 info.n = 0
274 return 0
275}