code wiki / (root) / dom_fn.nx

dom_fn.nx

buildroot/runtime/dom_fn.nx

9448 B255 linesdepth 5pulls 8 transitivereach 0 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 · 0 importers

syscalls.nx types.nx ir.nx dom_fn.nx

imports: syscalls.nxtypes.nxir.nx

imported by: nobody (leaf or entry point)

structs

33struct DomInfoFn {

consts

none

functions

44func df_block_index(f: *Function, bb: *BasicBlock) -> i64 {
57func df_dfs(f: *Function, b: *BasicBlock,
84func df_intersect(idom_arr: *i64, rpo_num: *i64,
called by 1: dom_compute_fn
104func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 {
228func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 {
calls 1: df_block_index
249func main() -> i64 {