dom_fn.nx
buildroot/runtime/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 · 0 importers
imports: syscalls.nxtypes.nxir.nx
imported by: nobody (leaf or entry point)
structs
| 33 | struct DomInfoFn { |
consts
| none |
functions
| 44 | func df_block_index(f: *Function, bb: *BasicBlock) -> i64 { |
| 57 | func df_dfs(f: *Function, b: *BasicBlock, |
| 84 | func df_intersect(idom_arr: *i64, rpo_num: *i64,
called by 1: dom_compute_fn |
| 104 | func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 { |
| 228 | func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 {
calls 1: df_block_index |
| 249 | func main() -> i64 { |