`nx_mulchain.nx` source

↩ module page · 140 lines · 5846 B
1// nx_mulchain.nx -- a FASTER, deeper superoptimizer for multiply-by-constant: search the
2// MULTIPLIER space (addition/subtraction/shift chains) instead of evaluating raw programs
3// on many inputs. Every slot holds a multiplier k (meaning k*x); ops grow the set:
4// ADD(k1,k2)=k1+k2, SUB(k1,k2)=k1-k2, SHL(k,s)=k<<s. Iterative deepening over op-count
5// returns the SHORTEST chain to C (provably minimal op count). Magnitude pruning (|k| <=
6// 4|C|) keeps it fast and lets it reach constants the raw-op search timed out on -- the
7// team escalating its OWN search to close its OWN gaps. Output is the emitter's slot form
8// (0=x, op t writes slot t+3), so se_emit_full emits it directly. license_tier: ORIGINAL
9//
10// Refs: Bernstein "Multiplication by integer constants" 1986; Lefevre, INRIA RR-4192 2001;
11// addition-chain / shift-add literature. Op constants reuse SO_ADD/SO_SUB/SO_SHL.
12
13import "nx_superopt_opt.nx"   // SO_ADD(0), SO_SUB(1), SO_SHL(3)
14
15func mc_abs(v: i64) -> i64 { if v < 0 { return 0 - v } return v }
16
17// k-th available operand slot at a position: 0 -> x (slot 0); k>=1 -> computed slot k+2.
18func mc_avslot(k: i64) -> i64 { if k == 0 { return 0 } return k + 2 }
19
20// recursive iterative-deepening enumeration; sv[] holds the multiplier per emitter slot.
21func mc_enum(op: *i64, a: *i64, b: *i64, t: i64, L: i64, sv: *i64, C: i64, bound: i64, maxsh: i64) -> i64 {
  if t == L { if sv[L + 2] == C { return 1 } return 0 }
  let nav: i64 = t + 1
  let rslot: i64 = t + 3
  // ADD (i <= j, commutative)
  var i: i64 = 0
  while i < nav {
      var j: i64 = i
      while j < nav {
          let nv: i64 = sv[mc_avslot(i)] + sv[mc_avslot(j)]
          if mc_abs(nv) <= bound {
              sv[rslot] = nv; op[t] = SO_ADD; a[t] = mc_avslot(i); b[t] = mc_avslot(j)
              if mc_enum(op, a, b, t + 1, L, sv, C, bound, maxsh) == 1 { return 1 }
          }
          j = j + 1
      }
      i = i + 1
  }
  // SUB (ordered, both directions)
  i = 0
  while i < nav {
      var j: i64 = 0
      while j < nav {
          if i != j {
              let nv: i64 = sv[mc_avslot(i)] - sv[mc_avslot(j)]
              if mc_abs(nv) <= bound {
                  sv[rslot] = nv; op[t] = SO_SUB; a[t] = mc_avslot(i); b[t] = mc_avslot(j)
                  if mc_enum(op, a, b, t + 1, L, sv, C, bound, maxsh) == 1 { return 1 }
              }
          }
          j = j + 1
      }
      i = i + 1
  }
  // SHL (slot i by sh = 1..maxsh)
  i = 0
  while i < nav {
      var sh: i64 = 1
      while sh <= maxsh {
          let nv: i64 = sv[mc_avslot(i)] << sh
          if mc_abs(nv) <= bound {
              sv[rslot] = nv; op[t] = SO_SHL; a[t] = mc_avslot(i); b[t] = sh
              if mc_enum(op, a, b, t + 1, L, sv, C, bound, maxsh) == 1 { return 1 }
          }
          sh = sh + 1
      }
      i = i + 1
  }
  // LEA: base + index*scale, scale in {2,4,8} (one x86 lea; base==index gives *3/*5/*9)
  i = 0
  while i < nav {
      var j2: i64 = 0
      while j2 < nav {
          var si: i64 = 0
          while si < 3 {
              var sc: i64 = 2
              if si == 1 { sc = 4 }
              if si == 2 { sc = 8 }
              let nv: i64 = sv[mc_avslot(i)] + sv[mc_avslot(j2)] * sc
              if mc_abs(nv) <= bound {
                  var oo: i64 = SO_LEA2
                  if sc == 4 { oo = SO_LEA4 }
                  if sc == 8 { oo = SO_LEA8 }
                  sv[rslot] = nv; op[t] = oo; a[t] = mc_avslot(i); b[t] = mc_avslot(j2)
                  if mc_enum(op, a, b, t + 1, L, sv, C, bound, maxsh) == 1 { return 1 }
              }
              si = si + 1
          }
          j2 = j2 + 1
      }
      i = i + 1
  }
  return 0
94}
95
96// find the SHORTEST shift-add chain for x*C, length 1..maxL. Writes op/a/b (emitter form),
97// returns L (op count) or 0 if not found within maxL.
98func mulchain_find(C: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 {
  let sv: *i64 = sys_mmap(8 * (maxL + 6)) as *i64
  sv[0] = 1                                      // x's multiplier is 1
  var bound: i64 = mc_abs(C) * 4 + 8
  var L: i64 = 1
  while L <= maxL {
      if mc_enum(op, a, b, 0, L, sv, C, bound, 16) == 1 { return L }
      L = L + 1
  }
  return 0
108}
109
110// EVALUATE a found chain program on input x (the Engineer's independent oracle, so a consumer
111// can VERIFY the generator's output instead of trusting it). slot 0 = x, op t -> slot t+3.
112func mc_eval(op: *i64, a: *i64, b: *i64, L: i64, x: i64) -> i64 {
  let sv: *i64 = sys_mmap(8 * (L + 6)) as *i64
  sv[0] = x
  var t: i64 = 0
  while t < L {
      let o: i64 = op[t]
      let va: i64 = sv[a[t]]
      if o == SO_ADD  { sv[t + 3] = va + sv[b[t]] }
      if o == SO_SUB  { sv[t + 3] = va - sv[b[t]] }
      if o == SO_SHL  { sv[t + 3] = va << b[t] }
      if o == SO_LEA2 { sv[t + 3] = va + sv[b[t]] * 2 }
      if o == SO_LEA4 { sv[t + 3] = va + sv[b[t]] * 4 }
      if o == SO_LEA8 { sv[t + 3] = va + sv[b[t]] * 8 }
      t = t + 1
  }
  return sv[L + 2]
128}
129
130// the trustworthy work function: get a chain, then VERIFY it actually computes c*x on
131// independent inputs. returns the op count if VERIFIED, or 0-1 if not found / not verified
132// (so the caller never banks an unchecked result -- the Engineer's "verify, don't trust").
133func mulchain_verified(c: i64, maxL: i64, op: *i64, a: *i64, b: *i64) -> i64 {
  let L: i64 = mulchain_find(c, maxL, op, a, b)
  if L <= 0 { return 0 - 1 }                          // not found (covers the 0-on-fail contract)
  if mc_eval(op, a, b, L, 7) != c * 7 { return 0 - 1 }
  if mc_eval(op, a, b, L, 131) != c * 131 { return 0 - 1 }
  if mc_eval(op, a, b, L, 0 - 9) != c * (0 - 9) { return 0 - 1 }
  return L
140}
nx_mulchain.nx source

`nx_mulchain.nx` source
