`nx_fpga_pnr.nx` source

↩ module page · 240 lines · 9864 B
1// nx_fpga_pnr.nx -- LIB: sovereign PLACE-AND-ROUTE (omniforge SI M4, the nextpnr replacement) for the LUT4
2// fabric. Input = the nx_fpga_fabric bitstream netlist (ncells, npi, inits[], src[4*ncells]; a source s is
3// PI s if s<npi else the output of cell s-npi). P&R does what fab_eval's implicit "index order" does NOT:
4//   (1) PLACE each cell on a DISTINCT 2D grid site, honoring topological columns -- every driver sits in a
5//       strictly-earlier column than its sink, so signals flow left->right with no combinational loop.
6//   (2) ROUTE every wire (PI->cell and cell->cell) as a shortest Manhattan path via Lee/BFS over a grid whose
7//       EDGES carry a finite channel capacity -- so routing CONGESTS and can FAIL. Routing success is
8//       capacity-gated, never fabricated.
9// P&R preserves logic, so fab_eval over the (routed) driver map reproduces the golden function; the gate proves
10// faithfulness + that routing is load-bearing (corrupt a net -> diverge) + that capacity exhaustion -> UNROUTABLE.
11// never-brick #26: pure memory, BFS bounded by W*H nodes, deterministic, ZERO hardware writes. license_tier: ORIGINAL
12import "nx_fpga_fabric.nx"   // fab_eval (logic eval; P&R preserves logic)
13import "nx_syscalls.nx"
14
15// levelize: cell level = 1 + max(driver levels); a PI driver contributes level 0. Requires topological src
16// (cell k only wires from PIs or cells < k -- the fabric convention). Returns the max cell level (= last column).
17func pnr_levelize(ncells: i64, npi: i64, src: *i64, level: *i64) -> i64 {
  var maxl: i64 = 0
  var k: i64 = 0
  while k < ncells {
      var lv: i64 = 0
      var i: i64 = 0
      while i < 4 {
          let s: i64 = src[k*4 + i]
          if s >= npi {
              let dl: i64 = level[s - npi]
              if dl > lv { lv = dl }
          }
          i = i + 1
      }
      level[k] = lv + 1
      if level[k] > maxl { maxl = level[k] }
      k = k + 1
  }
  return maxl
36}
37
38// place: PIs in column 0 (rows 0..npi-1); cell k in column level[k], next free row in that column. site = row*W + col.
39// Returns 0 on success, or 0-1 if infeasible (npi>H, a needed column >= W, or a column overflows H). colnext is
40// W-long scratch. PIs (col 0) and cells (col>=1) never collide; cells in a column take distinct rows -> all sites distinct.
41func pnr_place(ncells: i64, npi: i64, level: *i64, W: i64, H: i64,
             pi_site: *i64, cell_site: *i64, colnext: *i64) -> i64 {
  if npi > H { return 0 - 1 }
  var j: i64 = 0
  while j < npi { pi_site[j] = j*W + 0; j = j + 1 }
  var c: i64 = 0
  while c < W { colnext[c] = 0; c = c + 1 }
  var k: i64 = 0
  while k < ncells {
      let col: i64 = level[k]
      if col >= W { return 0 - 1 }
      let row: i64 = colnext[col]
      if row >= H { return 0 - 1 }
      cell_site[k] = row*W + col
      colnext[col] = row + 1
      k = k + 1
  }
  return 0
59}
60
61// route one net (sx,sy)->(tx,ty) over the WxH grid; an edge is traversable iff its remaining capacity > 0.
62// On success: decrement capacity along the chosen shortest path and return its hop-length. On failure: return 0-1.
63// Scratch arrays vis/came/q are each >= W*H long. cap_h is H*(W-1) long, cap_v is (H-1)*W long.
64func pnr_route_net(W: i64, H: i64, cap_h: *i64, cap_v: *i64,
                 sx: i64, sy: i64, tx: i64, ty: i64,
                 vis: *i64, came: *i64, q: *i64) -> i64 {
  let n: i64 = W * H
  var i: i64 = 0
  while i < n { vis[i] = 0; came[i] = 0 - 1; i = i + 1 }
  let start: i64 = sy*W + sx
  let target: i64 = ty*W + tx
  if start == target { return 0 }
  var qh: i64 = 0
  var qt: i64 = 0
  vis[start] = 1
  q[qt] = start; qt = qt + 1
  var found: i64 = 0
  while qh < qt {
      let cur: i64 = q[qh]; qh = qh + 1
      if cur == target { found = 1; qh = qt }
      if found == 0 {
          let cx: i64 = cur % W
          let cy: i64 = cur / W
          if cx + 1 < W {
              let eh: i64 = cy*(W-1) + cx
              if cap_h[eh] > 0 {
                  let nb: i64 = cy*W + (cx+1)
                  if vis[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 }
              }
          }
          if cx - 1 >= 0 {
              let eh: i64 = cy*(W-1) + (cx-1)
              if cap_h[eh] > 0 {
                  let nb: i64 = cy*W + (cx-1)
                  if vis[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 }
              }
          }
          if cy + 1 < H {
              let ev: i64 = cy*W + cx
              if cap_v[ev] > 0 {
                  let nb: i64 = (cy+1)*W + cx
                  if vis[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 }
              }
          }
          if cy - 1 >= 0 {
              let ev: i64 = (cy-1)*W + cx
              if cap_v[ev] > 0 {
                  let nb: i64 = (cy-1)*W + cx
                  if vis[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 }
              }
          }
      }
  }
  if found == 0 { return 0 - 1 }
  var len: i64 = 0
  var node: i64 = target
  while node != start {
      let p: i64 = came[node]
      let nx2: i64 = node % W
      let ny2: i64 = node / W
      let px: i64 = p % W
      let py: i64 = p / W
      if py == ny2 {
          var lx: i64 = px
          if nx2 < lx { lx = nx2 }
          let eh: i64 = py*(W-1) + lx
          cap_h[eh] = cap_h[eh] - 1
      } else {
          var ly: i64 = py
          if ny2 < ly { ly = ny2 }
          let ev: i64 = ly*W + px
          cap_v[ev] = cap_v[ev] - 1
      }
      len = len + 1
      node = p
  }
  return len
138}
139
140// route ALL wires: each cell's 4 input nets (driver_site -> cell_site). Returns total wirelength; sets ok[0]=1
141// iff every net routed, else 0. A net whose driver and sink share a site contributes length 0 (no channel use).
142func pnr_route_all(ncells: i64, npi: i64, src: *i64,
                 pi_site: *i64, cell_site: *i64,
                 W: i64, H: i64, cap_h: *i64, cap_v: *i64,
                 vis: *i64, came: *i64, q: *i64, ok: *i64) -> i64 {
  var wl: i64 = 0
  var allok: i64 = 1
  var k: i64 = 0
  while k < ncells {
      let csite: i64 = cell_site[k]
      let tx: i64 = csite % W
      let ty: i64 = csite / W
      var i: i64 = 0
      while i < 4 {
          let s: i64 = src[k*4 + i]
          var dsite: i64 = 0
          if s < npi { dsite = pi_site[s] } else { dsite = cell_site[s - npi] }
          let sx: i64 = dsite % W
          let sy: i64 = dsite / W
          let r: i64 = pnr_route_net(W, H, cap_h, cap_v, sx, sy, tx, ty, vis, came, q)
          if r < 0 { allok = 0 } else { wl = wl + r }
          i = i + 1
      }
      k = k + 1
  }
  ok[0] = allok
  return wl
168}
169
170// EXTENDED router (SHARED with the PCB autorouter): like pnr_route_net but (a) a NODE can be KEEPOUT-blocked
171// (block[node]==1 -> not traversable) so traces from different nets stay NODE-disjoint on a single layer (no
172// shorts / crossings = the core DRC), and (b) the chosen path is written to pathbuf (target..start, len+1 nodes)
173// so the caller can mark those nodes blocked for later nets. Returns hop-length, or 0-1 if unroutable. Same grid +
174// edge-capacity model -> ONE router serves FPGA place-and-route AND PCB copper autorouting.
175func pnr_route_net_ex(W: i64, H: i64, cap_h: *i64, cap_v: *i64, block: *i64,
                    sx: i64, sy: i64, tx: i64, ty: i64,
                    vis: *i64, came: *i64, q: *i64, pathbuf: *i64) -> i64 {
  let n: i64 = W * H
  var i: i64 = 0
  while i < n { vis[i] = 0; came[i] = 0 - 1; i = i + 1 }
  let start: i64 = sy*W + sx
  let target: i64 = ty*W + tx
  if start == target { pathbuf[0] = start; return 0 }
  var qh: i64 = 0
  var qt: i64 = 0
  vis[start] = 1
  q[qt] = start; qt = qt + 1
  var found: i64 = 0
  while qh < qt {
      let cur: i64 = q[qh]; qh = qh + 1
      if cur == target { found = 1; qh = qt }
      if found == 0 {
          let cx: i64 = cur % W
          let cy: i64 = cur / W
          if cx + 1 < W {
              let eh: i64 = cy*(W-1) + cx
              if cap_h[eh] > 0 { let nb: i64 = cy*W + (cx+1); if vis[nb] == 0 { if block[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 } } }
          }
          if cx - 1 >= 0 {
              let eh: i64 = cy*(W-1) + (cx-1)
              if cap_h[eh] > 0 { let nb: i64 = cy*W + (cx-1); if vis[nb] == 0 { if block[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 } } }
          }
          if cy + 1 < H {
              let ev: i64 = cy*W + cx
              if cap_v[ev] > 0 { let nb: i64 = (cy+1)*W + cx; if vis[nb] == 0 { if block[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 } } }
          }
          if cy - 1 >= 0 {
              let ev: i64 = (cy-1)*W + cx
              if cap_v[ev] > 0 { let nb: i64 = (cy-1)*W + cx; if vis[nb] == 0 { if block[nb] == 0 { vis[nb]=1; came[nb]=cur; q[qt]=nb; qt=qt+1 } } }
          }
      }
  }
  if found == 0 { return 0 - 1 }
  var idx: i64 = 0
  pathbuf[idx] = target; idx = idx + 1
  var len: i64 = 0
  var nd: i64 = target
  while nd != start {
      let pr: i64 = came[nd]
      let nx2: i64 = nd % W
      let ny2: i64 = nd / W
      let px: i64 = pr % W
      let py: i64 = pr / W
      if py == ny2 {
          var lx: i64 = px
          if nx2 < lx { lx = nx2 }
          let eh: i64 = py*(W-1) + lx
          cap_h[eh] = cap_h[eh] - 1
      } else {
          var ly: i64 = py
          if ny2 < ly { ly = ny2 }
          let ev: i64 = ly*W + px
          cap_v[ev] = cap_v[ev] - 1
      }
      pathbuf[idx] = pr; idx = idx + 1
      len = len + 1
      nd = pr
  }
  return len
240}
nx_fpga_pnr.nx source

`nx_fpga_pnr.nx` source
