nx_dom_fn.nx
buildroot/runtime/nx_dom_fn.nx
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 · 1 importers
imports: nx_syscalls.nxnx_types.nxnx_ir.nx
imported by: nx_opt.nx
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| 39 | struct DomInfoFn |
consts
| none |
functions
| 50 | func df_block_index(f: *Function, bb: *BasicBlock) -> i64 |
| 63 | func df_dfs(f: *Function, b: *BasicBlock, |
| 90 | func df_intersect(idom_arr: *i64, rpo_num: *i64, called by 1: dom_compute_fn |
| 110 | func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 |
| 247 | func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 called by 3: opt_licmlicm_store_dominated_by_headeroperands_are_loop_invariant calls 1: df_block_index |
| 269 | func main() -> i64 calls 1: sys_mmap |