code wiki / (root) / nx_dom_fn.nx

nx_dom_fn.nx

buildroot/runtime/nx_dom_fn.nx

11109 B285 linesdepth 4pulls 6 transitivereach 197 importersview sourcekind tooltopic dom
docsdependenciesstructsconstsfunctions

about

dom_fn.nx -- dominator tree on *Function (opt.nx consumer). Separate from dom.nx (which operates on a local Block type declared in that file). dom_fn computes immediate dominators directly on the runtime's shared BasicBlock struct so opt.nx passes (LICM next) can consume it without type translation. Algorithm: Cooper-Harvey-Kennedy "A Simple, Fast Dominance Algorithm" (2001). O(N * E * alpha) in practice, trivial implementation compared to Lengauer-Tarjan. Invariants: DF1 Entry block is its own idom by convention. DF2 Unreachable blocks have idom == NULL. Callers should run opt_sweep_unreachable_function first if they want every block reachable. DF3 idom[i] is indexed by ARRAY POSITION (block_index), not by block.id. Caller uses block_index() to look up an idom from a BasicBlock pointer. DF4 RPO (reverse-postorder) guarantees every dominator is seen before its dominatees during the fixpoint pass; this is the invariant that makes Cooper-Harvey-Kennedy's iterate-to-fixpoint converge in O(d) where d is max dominator-tree depth.

dependencies 3 imports · 2 importers

nx_syscalls.nx nx_types.nx nx_ir.nx nx_dom_fn.nx nx_bck_elide.nx nx_opt.nx

imports: nx_syscalls.nxnx_types.nxnx_ir.nx

imported by: nx_bck_elide.nxnx_opt.nx

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main sys_mmap nxa_die sys_write sys_exit nxa_lock_take nxa_lock_addr sys_write ↻ nxa_lock_give nxa_lock_addr ↻ nxa_report_overrun sys_write ↻ nxa_dump_printable sys_write ↻ nxa_dump_sizes sys_write ↻

structs

39struct DomInfoFn

consts

none

functions

58func df_block_index(f: *Function, bb: *BasicBlock) -> i64
73func df_dfs(f: *Function, b: *BasicBlock,
100func df_intersect(idom_arr: *i64, rpo_num: *i64,
called by 1: dom_compute_fn
120func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64
257func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64
279func main() -> i64
calls 1: sys_mmap