`dom_fn.nx` source

↩ module page · 255 lines · 9448 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
26import "syscalls.nx"
27import "types.nx"
28import "ir.nx"
29
30// Result bundle: idom pointers indexed by array position, plus
31// RPO ordering so callers can iterate dominatees-before-dominator
32// (or reverse) without recomputing.
33struct DomInfoFn {
  f:       *Function,
  n:       i64,             // == f.n_blocks
  idom:    *BasicBlock,     // array of n pointers (*BasicBlock-valued)
  rpo:     *BasicBlock,     // array of n pointers, RPO order (reachable first)
  rpo_n:   i64,             // count of reachable blocks
  rpo_num: *i64,            // block_index -> RPO position, or -1 if unreachable
40}
41
42// Look up a block's array index in f.blocks[].  Linear scan,
43// O(n); fine for small functions.  Returns -1 if not found.
44func df_block_index(f: *Function, bb: *BasicBlock) -> i64 {
  var i: i64 = 0
  while i < f.n_blocks {
      if block_at(f, i) == bb { return i }
      i = i + 1
  }
  return -1
51}
52
53// DFS from `b`, visiting successors in inline-slot order.  On
54// exit from each recursion level, push onto rpo array.  The
55// resulting rpo array, reversed at the end, is the reverse-
56// postorder traversal.
57func df_dfs(f: *Function, b: *BasicBlock,
          visited: *u8, rpo: *BasicBlock, rpo_n: *i64) -> i64 {
  let idx: i64 = df_block_index(f, b)
  if idx < 0 { return 0 }
  if visited[idx] == 1 { return 0 }
  visited[idx] = 1
  if b.succ0 != (0 as *BasicBlock) {
      df_dfs(f, b.succ0, visited, rpo, rpo_n)
  }
  if b.succ1 != (0 as *BasicBlock) {
      df_dfs(f, b.succ1, visited, rpo, rpo_n)
  }
  let n: i64 = *rpo_n
  // rpo is an array of BasicBlock* stored as 8-byte slots; we
  // write them via pointer arithmetic since NishiLang lacks a
  // *BasicBlock -> i64 slot array primitive.
  let rpo_base: i64 = rpo as i64
  let slot: *i64 = (rpo_base + n * 8) as *i64
  *slot = b as i64
  *rpo_n = n + 1
  return 0
78}
79
80// Walk up the idom chain of two blocks until they meet.
81// Parameters: idom_by_rpo is the current idom array keyed by
82// RPO position; rpo_num maps block_index to RPO position.  Both
83// b1 and b2 are array indices of blocks (not RPO positions).
84func df_intersect(idom_arr: *i64, rpo_num: *i64,
                b1: i64, b2: i64) -> i64 {
  var a: i64 = b1
  var b: i64 = b2
  while a != b {
      while rpo_num[a] > rpo_num[b] {
          a = idom_arr[a]
          if a < 0 { return b }
      }
      while rpo_num[b] > rpo_num[a] {
          b = idom_arr[b]
          if b < 0 { return a }
      }
  }
  return a
99}
100
101// Main entry: compute immediate dominators for every block in f.
102// Returns 0 on success, negative on allocation failure.  Caller
103// passes in pre-allocated DomInfoFn struct; helper fills arrays.
104func dom_compute_fn(f: *Function, info: *DomInfoFn) -> i64 {
  let n: i64 = f.n_blocks
  info.f = f
  info.n = n
  if n == 0 { return 0 }
109
  // RPO via DFS from entry, then reverse.
  let visited_raw: *u8 = sys_mmap(n + 16)
  let visited: *u8 = visited_raw
  var i: i64 = 0
  while i < n { visited[i] = 0; i = i + 1 }
  let rpo_fwd_raw: *u8 = sys_mmap(n * 8 + 16)
  let rpo_fwd: *BasicBlock = rpo_fwd_raw as *BasicBlock
  let rpo_n_raw: *u8 = sys_mmap(16)
  let rpo_n_p: *i64 = rpo_n_raw as *i64
  *rpo_n_p = 0
  df_dfs(f, f.entry, visited, rpo_fwd, rpo_n_p)
  let rpo_count: i64 = *rpo_n_p
122
  // Reverse the postorder array in place.
  let rpo_raw: *u8 = sys_mmap(n * 8 + 16)
  let rpo: *BasicBlock = rpo_raw as *BasicBlock
  let rpo_base: i64 = rpo as i64
  let rpo_fwd_base: i64 = rpo_fwd as i64
  i = 0
  while i < rpo_count {
      let src_slot: *i64 = (rpo_fwd_base + (rpo_count - 1 - i) * 8) as *i64
      let dst_slot: *i64 = (rpo_base + i * 8) as *i64
      *dst_slot = *src_slot
      i = i + 1
  }
  info.rpo = rpo
  info.rpo_n = rpo_count
137
  // rpo_num[array_index] = RPO position, or -1.
  let rpo_num_raw: *u8 = sys_mmap(n * 8 + 16)
  let rpo_num: *i64 = rpo_num_raw as *i64
  i = 0
  while i < n { rpo_num[i] = -1; i = i + 1 }
  i = 0
  while i < rpo_count {
      let slot: *i64 = (rpo_base + i * 8) as *i64
      let bb: *BasicBlock = *slot as *BasicBlock
      let idx: i64 = df_block_index(f, bb)
      if idx >= 0 { rpo_num[idx] = i }
      i = i + 1
  }
  info.rpo_num = rpo_num
152
  // idom[array_index] = array_index of immediate dominator, or -1
  // for unreachable / entry.  Start: all -1 except entry which
  // points at itself.
  let idom_arr_raw: *u8 = sys_mmap(n * 8 + 16)
  let idom_arr: *i64 = idom_arr_raw as *i64
  i = 0
  while i < n { idom_arr[i] = -1; i = i + 1 }
  let entry_idx: i64 = df_block_index(f, f.entry)
  idom_arr[entry_idx] = entry_idx
162
  // Iterate to fixpoint over non-entry reachable blocks in RPO
  // order.  For each block, idom = intersection of idom(preds).
  var changed: i64 = 1
  while changed == 1 {
      changed = 0
      var ri: i64 = 1    // skip entry (index 0 in RPO)
      while ri < rpo_count {
          let slot: *i64 = (rpo_base + ri * 8) as *i64
          let bb: *BasicBlock = *slot as *BasicBlock
          let bi: i64 = df_block_index(f, bb)
          // Find first processed predecessor.
          var new_idom: i64 = -1
          var p_idx: i64 = 0
          // Three pred slots to check.
          let pred_list: *i64 = sys_mmap(32) as *i64
          pred_list[0] = bb.pred0 as i64
          pred_list[1] = bb.pred1 as i64
          pred_list[2] = bb.pred2 as i64
          while p_idx < 3 {
              let p: *BasicBlock = pred_list[p_idx] as *BasicBlock
              if p != (0 as *BasicBlock) {
                  let p_arr: i64 = df_block_index(f, p)
                  if p_arr >= 0 {
                      if idom_arr[p_arr] >= 0 {
                          if new_idom < 0 { new_idom = p_arr }
                          else {
                              new_idom = df_intersect(idom_arr, rpo_num,
                                                       new_idom, p_arr)
                          }
                      }
                  }
              }
              p_idx = p_idx + 1
          }
          if new_idom >= 0 {
              if idom_arr[bi] != new_idom {
                  idom_arr[bi] = new_idom
                  changed = 1
              }
          }
          ri = ri + 1
      }
  }
206
  // Pack idom_arr into info.idom as BasicBlock pointers (rather
  // than indices) for caller convenience.
  let idom_bb_raw: *u8 = sys_mmap(n * 8 + 16)
  let idom_bb: *BasicBlock = idom_bb_raw as *BasicBlock
  let idom_bb_base: i64 = idom_bb as i64
  i = 0
  while i < n {
      let dst: *i64 = (idom_bb_base + i * 8) as *i64
      if idom_arr[i] >= 0 {
          *dst = block_at(f, idom_arr[i]) as i64
      } else {
          *dst = 0
      }
      i = i + 1
  }
  info.idom = idom_bb
  return 0
224}
225
226// Returns 1 iff `a` dominates `b`.  Walks b's idom chain; reaches
227// a => yes, or reaches entry first => no.
228func dom_dominates(info: *DomInfoFn, a: *BasicBlock, b: *BasicBlock) -> i64 {
  if a == b { return 1 }
  let idom_base: i64 = info.idom as i64
  var cur_idx: i64 = df_block_index(info.f, b)
  if cur_idx < 0 { return 0 }
  var hops: i64 = 0
  while hops < info.n {
      let slot: *i64 = (idom_base + cur_idx * 8) as *i64
      let idom_bb: *BasicBlock = *slot as *BasicBlock
      if idom_bb == a { return 1 }
      if idom_bb == (0 as *BasicBlock) { return 0 }
      let next_idx: i64 = df_block_index(info.f, idom_bb)
      if next_idx == cur_idx { return 0 }    // entry's self-loop
      cur_idx = next_idx
      hops = hops + 1
  }
  return 0
245}
246
247// Compile-only smoke: dom_compute on a nominal function with
248// entry only.
249func main() -> i64 {
  let info_raw: *u8 = sys_mmap(128)
  let info: *DomInfoFn = info_raw as *DomInfoFn
  info.f = 0 as *Function
  info.n = 0
  return 0
255}
dom_fn.nx source

`dom_fn.nx` source
