code wiki / (root) / nx_dom_oracle_gate.nx
`nx_dom_oracle_gate.nx` source

↩ module page · 316 lines · 11430 B
1// nx_dom_oracle_gate.nx -- BRUTE-FORCE DOMINANCE ORACLE for dom_fn.nx.
2//
3// The banked LICM awakening rung (nx_opt.nx DORMANT-COMPAT, 2026-06-10):
4// "Awakening rung = dominance brute-force oracle FIRST, then this load."
5// This gate IS that oracle. Definition-level ground truth: D dominates B iff
6// removing D makes B unreachable from entry. Compares that, pairwise, against
7// dom_compute_fn's idom chains over EVERY function of the FULL self-host
8// compiler source (the exact merge-heavy CFGs that broke the 06-10 awakening),
9// on the post-parse CFG AND the post-opt_run CFG (the shapes LICM actually
10// sees inside the fixpoint).
11//
12// Skips (reported, never silent): functions with any block n_preds > 3 (the
13// pred-truncation class -- opt_licm DECLINES these, so they are outside the
14// awakening's blast zone) and functions with n_blocks > DOR_MAX_B (brute cost).
15// NEGATIVE CONTROL: a deliberately corrupted idom entry must produce
16// mismatches -- proves the comparator can see a lie.
17// Verdict GREEN iff mismatches == 0 AND negctl fired. license_tier: ORIGINAL
18import "nx_syscalls.nx"
19import "nx_types.nx"
20import "nx_lex_kinds.nx"
21import "nx_outbuf.nx"
22import "nx_ir.nx"
23import "nx_tokenizer.nx"
24import "nx_parse.nx"
25import "nx_opt.nx"
26import "nx_ir_validate.nx"
27import "nx_import.nx"
28import "nx_gate_verdict.nx"
29
30const DOR_MAX_B: i64 = 256
31const DOR_EXPAND_CAP: i64 = 4194304
32
33func dor_w(s: *u8) -> i64 {
  var n: i64 = 0
  while s[n] != (0 as u8) { n = n + 1 }
  sys_write(1, s, n)
  return 0
38}
39func dor_wn(v: i64) -> i64 {
  let t: *u8 = sys_mmap(32)
  let o: *u8 = sys_mmap(32)
  var m: i64 = v
  var neg: i64 = 0
  if m < 0 { neg = 1; m = 0 - m }
  var k: i64 = 0
  if m == 0 { t[0] = 48 as u8; k = 1 }
  while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
  var w: i64 = 0
  if neg == 1 { o[0] = 45 as u8; w = 1 }
  var i: i64 = 0
  while i < k { o[w + i] = t[k - 1 - i]; i = i + 1 }
  sys_write(1, o, w + k)
  return 0
54}
55
56// index of block pointer within f.blocks[]; -1 if absent.
57func dor_bidx(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 0 - 1
64}
65
66// Forward BFS from entry over succ0/succ1, skipping block `skip` (-1 = none).
67// Writes reach[i]=1 for visited. Iterative worklist (no recursion).
68func dor_reach(f: *Function, skip: i64, reach: *u8, wl: *i64) -> i64 {
  let n: i64 = f.n_blocks
  var i: i64 = 0
  while i < n { reach[i] = 0 as u8; i = i + 1 }
  let e: i64 = dor_bidx(f, f.entry)
  if e < 0 { return 0 }
  if e == skip { return 0 }
  var head: i64 = 0
  var tail: i64 = 0
  wl[tail] = e
  tail = tail + 1
  reach[e] = 1 as u8
  while head < tail {
      let cur: i64 = wl[head]
      head = head + 1
      let b: *BasicBlock = block_at(f, cur)
      let s0: *BasicBlock = b.succ0
      if s0 != (0 as *BasicBlock) {
          let i0: i64 = dor_bidx(f, s0)
          if i0 >= 0 { if i0 != skip { if reach[i0] == 0 {
              reach[i0] = 1 as u8
              wl[tail] = i0
              tail = tail + 1
          } } }
      }
      let s1: *BasicBlock = b.succ1
      if s1 != (0 as *BasicBlock) {
          let i1: i64 = dor_bidx(f, s1)
          if i1 >= 0 { if i1 != skip { if reach[i1] == 0 {
              reach[i1] = 1 as u8
              wl[tail] = i1
              tail = tail + 1
          } } }
      }
  }
  return 0
104}
105
106// dominates-by-idom-chain using a PRE-INDEXED idom array (entry: idom==self).
107func dor_chain_dom(idom_idx: *i64, n: i64, d: i64, b: i64) -> i64 {
  if d == b { return 1 }
  var cur: i64 = b
  var hops: i64 = 0
  while hops < n {
      let up: i64 = idom_idx[cur]
      if up < 0 { return 0 }
      if up == d { return 1 }
      if up == cur { return 0 }      // reached entry
      cur = up
      hops = hops + 1
  }
  return 0
120}
121
122// Check one function's CFG. Returns mismatch count; accumulates pair count
123// into cnt[0] and prints the first few mismatches.
124func dor_check_fn(f: *Function, fname: *u8, cnt: *i64, negctl: i64) -> i64 {
  let n: i64 = f.n_blocks
  if n < 2 { return 0 }
  if n > DOR_MAX_B { cnt[1] = cnt[1] + 1; return 0 }
  var tb: i64 = 0
  while tb < n {
      let tbb: *BasicBlock = block_at(f, tb)
      if tbb.n_preds > 3 { cnt[2] = cnt[2] + 1; return 0 }
      tb = tb + 1
  }
  let info_raw: *u8 = sys_mmap(128)
  let info: *DomInfoFn = info_raw as *DomInfoFn
  dom_compute_fn(f, info)
  // idom as INDICES once (kills the O(n) pointer lookup inside pair loops).
  let ii_raw: *u8 = sys_mmap(n * 8 + 16)
  let idom_idx: *i64 = ii_raw as *i64
  let ibase: i64 = info.idom as i64
  var i: i64 = 0
  while i < n {
      let sl: *i64 = (ibase + i * 8) as *i64
      let p: *BasicBlock = *sl as *BasicBlock
      if p == (0 as *BasicBlock) { idom_idx[i] = 0 - 1 }
      if p != (0 as *BasicBlock) { idom_idx[i] = dor_bidx(f, p) }
      i = i + 1
  }
  // NEGCTL: corrupt one reachable non-entry idom to SELF (claims "I am a root"
  // -> its dominators vanish from the chain -> brute must disagree).
  let reach_raw: *u8 = sys_mmap(n + 16)
  let reach: *u8 = reach_raw
  let wl_raw: *u8 = sys_mmap(n * 8 + 16)
  let wl: *i64 = wl_raw as *i64
  dor_reach(f, 0 - 1, reach, wl)
  let e: i64 = dor_bidx(f, f.entry)
  if negctl == 1 {
      // Corrupt an INTERMEDIATE dominator: a reachable block whose idom is a
      // real NON-ENTRY block. Reparent it to entry (skipping its true idom) ->
      // the pair (true_idom, vic) MUST mismatch (brute=1, chain misses it).
      // Self-corruption on an entry-child never fires: entry is excluded from
      // the D side of the pairwise check.
      var vic: i64 = 0 - 1
      var s: i64 = 0
      while s < n {
          if vic < 0 { if s != e { if reach[s] == 1 {
              if idom_idx[s] != s { if idom_idx[s] != e { if idom_idx[s] >= 0 { vic = s } } }
          } } }
          s = s + 1
      }
      if vic >= 0 { idom_idx[vic] = e }
  }
  // Pairwise: for each reachable D != entry, brute = reach-without-D.
  let rd_raw: *u8 = sys_mmap(n + 16)
  let rd: *u8 = rd_raw
  var mism: i64 = 0
  var d: i64 = 0
  while d < n {
      if reach[d] == 1 { if d != e {
          dor_reach(f, d, rd, wl)
          var b: i64 = 0
          while b < n {
              if b != d { if reach[b] == 1 {
                  var brute: i64 = 0
                  if rd[b] == 0 { brute = 1 }
                  let claim: i64 = dor_chain_dom(idom_idx, n, d, b)
                  cnt[0] = cnt[0] + 1
                  if brute != claim {
                      mism = mism + 1
                      if mism <= 3 {
                          dor_w("  MISMATCH fn#" as *u8)
                          dor_wn(cnt[3])
                          dor_w(" D=" as *u8)
                          dor_wn(d)
                          dor_w(" B=" as *u8)
                          dor_wn(b)
                          dor_w(" brute=" as *u8)
                          dor_wn(brute)
                          dor_w(" dom_fn=" as *u8)
                          dor_wn(claim)
                          dor_w("\n" as *u8)
                      }
                  }
              } }
              b = b + 1
          }
      } }
      d = d + 1
  }
  return mism
211}
212
213func main(argc: i64, argv: *i64) -> i64 {
  dor_w("NX-DOM-ORACLE start\n" as *u8)
  let expand_buf: *u8 = sys_mmap(DOR_EXPAND_CAP)
  let ctx: *ExpandCtx = expand_ctx_new(expand_buf, DOR_EXPAND_CAP)
  let rc: i64 = expand_imports(ctx, "runtime/nx_compile_x86.nx" as *u8)
  if rc < 0 { dor_w("expand FAIL\n" as *u8); return 2 }
  let op: *i64 = ctx.out_pos
  let end: i64 = *op
  expand_buf[end] = 0 as u8
  let toks: *Tok = lex_source(expand_buf, 262144)
  if toks == (0 as *Tok) { dor_w("lex FAIL\n" as *u8); return 3 }
  let m: *Module = parse_module(toks, 0 as *Module)
  if m == (0 as *Module) { dor_w("parse FAIL\n" as *u8); return 4 }
  dor_w("parsed fns=" as *u8)
  dor_wn(m.n_functions)
  dor_w("\n" as *u8)
229
  let cnt_raw: *u8 = sys_mmap(64)
  let cnt: *i64 = cnt_raw as *i64      // [0]=pairs [1]=skip_big [2]=skip_pred
  var mism_pp: i64 = 0
  var mism_po: i64 = 0
  var checked: i64 = 0
235
  // PASS 1: post-parse CFGs.
  var fi: i64 = 0
  while fi < m.n_functions {
      let fb: i64 = m.functions as i64
      let f: *Function = (fb + fi * 176) as *Function
      cnt[3] = fi
      mism_pp = mism_pp + dor_check_fn(f, f.name_start as *u8, cnt, 0)
      checked = checked + 1
      fi = fi + 1
  }
  dor_w("post-parse: fns=" as *u8)
  dor_wn(checked)
  dor_w(" pairs=" as *u8)
  dor_wn(cnt[0])
  dor_w(" skip_big=" as *u8)
  dor_wn(cnt[1])
  dor_w(" skip_pred=" as *u8)
  dor_wn(cnt[2])
  dor_w(" mismatches=" as *u8)
  dor_wn(mism_pp)
  dor_w("\n" as *u8)
257
  // PASS 2: post-opt CFGs (the shapes LICM sees). opt_run mutates in place.
  // opt_run mutates in place, then cfg_rebuild_edges (the LICM fix) recomputes
  // succ/pred from the terminators -- the EXACT graph LICM computes dominance
  // on. This measures whether the rebuild makes post-opt dominance sound.
  fi = 0
  while fi < m.n_functions {
      let fb2: i64 = m.functions as i64
      let f2: *Function = (fb2 + fi * 176) as *Function
      opt_run(f2)
      cfg_rebuild_edges(f2)
      cnt[3] = fi
      mism_po = mism_po + dor_check_fn(f2, f2.name_start as *u8, cnt, 0)
      fi = fi + 1
  }
  dor_w("post-opt: pairs_total=" as *u8)
  dor_wn(cnt[0])
  dor_w(" mismatches=" as *u8)
  dor_wn(mism_po)
  dor_w("\n" as *u8)
277
  // NEGATIVE CONTROL on the first function with >= 3 blocks.
  var neg_fired: i64 = 0
  fi = 0
  while fi < m.n_functions {
      if neg_fired == 0 {
          let fb3: i64 = m.functions as i64
          let f3: *Function = (fb3 + fi * 176) as *Function
          if f3.n_blocks >= 3 { if f3.n_blocks <= DOR_MAX_B {
              var okpred: i64 = 1
              var q: i64 = 0
              while q < f3.n_blocks {
                  let qb: *BasicBlock = block_at(f3, q)
                  if qb.n_preds > 3 { okpred = 0 }
                  q = q + 1
              }
              if okpred == 1 {
                  let nm: i64 = dor_check_fn(f3, f3.name_start as *u8, cnt, 1)
                  if nm > 0 { neg_fired = 1 }
              }
          } }
      }
      fi = fi + 1
  }
  dor_w("negctl_fired=" as *u8)
  dor_wn(neg_fired)
  dor_w("\n" as *u8)
304
  var green: i64 = 0
  if mism_pp == 0 { if mism_po == 0 { if neg_fired == 1 { green = 1 } } }
  // MIGRATED onto nx_gate_verdict by nx_gate_dry_apply (D001, minimal form): every check
  // row above is untouched, so the PASS/FAIL vector cannot change; only the hand-rolled
  // verdict emission is replaced by the ONE shared base class. Proven by nx_gate_migrate verify.
  let ctr__dry: *i64 = gv_ctr()
  ctr__dry[0] = green
  ctr__dry[1] = 1
  let rc__dry: i64 = gv_verdict("DOM-ORACLE-GATE" as *u8, ctr__dry, "dom_fn matches brute-force dominance on the full self-host corpus, post-parse + post-opt; negctl fired)" as *u8)
  sys_exit(rc__dry)
  return rc__dry
316}
nx_dom_oracle_gate.nx source

`nx_dom_oracle_gate.nx` source
