logicaffeine_compile/codegen_sva/
lutmap.rs

1//! Mapping logic onto K-input LUTs for depth, the way an FPGA's synthesis sees how deep a circuit is.
2//!
3//! An [`Xag`] holds the logic as two-input AND and XOR nodes over inputs, each edge plain or complemented, built with
4//! structural hashing and constant folding. [`map`] rebuilds it with every wide associative gate balanced for LUTs,
5//! then covers it with LUTs of at most `k` inputs:
6//! - a supergate is a maximal tree of AND nodes joined by plain edges, or of XOR nodes, whose inner nodes feed
7//!   nothing else and lie in one group (an instance of the design). It is rebuilt from its leaves `k` at a time,
8//!   the earliest-arriving first, so an AND or a parity of `n` inputs is `⌈log_k n⌉` LUT levels deep, where the
9//!   balanced binary tree a netlist hands over allows no better than `⌈log₂ n / ⌊log₂ k⌋⌉`;
10//! - every node keeps its best [`CUTS`] cuts of at most `k` leaves, ranked by arrival and then size (priority cuts:
11//!   Mishchenko, Cho, Chatterjee & Brayton, *Combinational and sequential mapping with priority cuts*, 2007), and
12//!   its level is its best cut's arrival, one more than its latest leaf's;
13//! - the cover takes each required node's best cut as a LUT, from the outputs back.
14
15use std::cmp::Reverse;
16use std::collections::{BinaryHeap, HashMap};
17
18/// How many cuts each node keeps.
19pub const CUTS: usize = 8;
20
21/// The largest LUT [`map`] maps to.
22pub const MAX_K: usize = 8;
23
24/// A node and whether the edge to it is complemented: `node << 1 | complemented`.
25pub type Lit = u32;
26
27pub const FALSE: Lit = 0;
28pub const TRUE: Lit = 1;
29
30pub fn node(l: Lit) -> usize {
31    (l >> 1) as usize
32}
33
34pub fn complemented(l: Lit) -> bool {
35    l & 1 == 1
36}
37
38/// A node of an [`Xag`].
39#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
40pub enum Gate {
41    /// Node 0, the constant false.
42    Constant,
43    Input,
44    And(Lit, Lit),
45    Xor(Lit, Lit),
46}
47
48/// An AND-XOR graph: node 0 is the constant, and every node's fanins come before it.
49#[derive(Clone, Debug)]
50pub struct Xag {
51    gates: Vec<Gate>,
52    hash: HashMap<Gate, u32>,
53}
54
55impl Default for Xag {
56    fn default() -> Xag {
57        Xag::new()
58    }
59}
60
61impl Xag {
62    pub fn new() -> Xag {
63        Xag { gates: vec![Gate::Constant], hash: HashMap::new() }
64    }
65
66    pub fn len(&self) -> usize {
67        self.gates.len()
68    }
69
70    pub fn is_empty(&self) -> bool {
71        self.gates.len() == 1
72    }
73
74    pub fn gate(&self, n: usize) -> Gate {
75        self.gates[n]
76    }
77
78    pub fn input(&mut self) -> Lit {
79        self.gates.push(Gate::Input);
80        ((self.gates.len() - 1) as u32) << 1
81    }
82
83    fn hashed(&mut self, g: Gate) -> Lit {
84        if let Some(&n) = self.hash.get(&g) {
85            return n << 1;
86        }
87        let n = self.gates.len() as u32;
88        self.gates.push(g);
89        self.hash.insert(g, n);
90        n << 1
91    }
92
93    pub fn and(&mut self, a: Lit, b: Lit) -> Lit {
94        let (a, b) = if a <= b { (a, b) } else { (b, a) };
95        match (a, b) {
96            (FALSE, _) => FALSE,
97            (TRUE, _) => b,
98            _ if a == b => a,
99            _ if a ^ 1 == b => FALSE,
100            _ => self.hashed(Gate::And(a, b)),
101        }
102    }
103
104    pub fn xor(&mut self, a: Lit, b: Lit) -> Lit {
105        let parity = (a ^ b) & 1;
106        let (a, b) = (a & !1, b & !1);
107        let (a, b) = if a <= b { (a, b) } else { (b, a) };
108        if a == FALSE {
109            return b ^ parity;
110        }
111        if a == b {
112            return FALSE ^ parity;
113        }
114        self.hashed(Gate::Xor(a, b)) ^ parity
115    }
116
117    pub fn or(&mut self, a: Lit, b: Lit) -> Lit {
118        self.and(a ^ 1, b ^ 1) ^ 1
119    }
120
121    /// `s ? t : e`.
122    pub fn mux(&mut self, s: Lit, t: Lit, e: Lit) -> Lit {
123        let on = self.and(s, t);
124        let off = self.and(s ^ 1, e);
125        self.or(on, off)
126    }
127
128    /// Every node's value under `inputs`, one bit lane per input pattern: `inputs[i]` is the `i`-th input's word.
129    pub fn simulate(&self, inputs: &[u64]) -> Vec<u64> {
130        let mut v = vec![0u64; self.gates.len()];
131        let lit = |v: &[u64], l: Lit| if complemented(l) { !v[node(l)] } else { v[node(l)] };
132        let mut next = 0;
133        for n in 0..self.gates.len() {
134            v[n] = match self.gates[n] {
135                Gate::Constant => 0,
136                Gate::Input => {
137                    next += 1;
138                    inputs.get(next - 1).copied().unwrap_or(0)
139                }
140                Gate::And(a, b) => lit(&v, a) & lit(&v, b),
141                Gate::Xor(a, b) => lit(&v, a) ^ lit(&v, b),
142            };
143        }
144        v
145    }
146}
147
148/// A cut: at most [`MAX_K`] leaves, sorted, and the level the node is at when it is a LUT over them.
149#[derive(Clone, Copy, Debug, PartialEq, Eq)]
150struct Cut {
151    len: u8,
152    leaves: [u32; MAX_K],
153    arrival: u32,
154}
155
156impl Cut {
157    fn leaves(&self) -> &[u32] {
158        &self.leaves[..self.len as usize]
159    }
160
161    fn unit(n: u32) -> Cut {
162        let mut leaves = [0; MAX_K];
163        leaves[0] = n;
164        Cut { len: 1, leaves, arrival: 0 }
165    }
166
167    /// The union of two cuts' leaves, when it has at most `k`.
168    fn merge(a: &Cut, b: &Cut, k: usize) -> Option<Cut> {
169        let (x, y) = (a.leaves(), b.leaves());
170        let mut out = [0u32; MAX_K];
171        let (mut i, mut j, mut n) = (0, 0, 0);
172        while i < x.len() || j < y.len() {
173            let take = match (x.get(i), y.get(j)) {
174                (Some(&p), Some(&q)) if p == q => {
175                    i += 1;
176                    j += 1;
177                    p
178                }
179                (Some(&p), Some(&q)) if p < q => {
180                    i += 1;
181                    p
182                }
183                (Some(&p), None) => {
184                    i += 1;
185                    p
186                }
187                (_, Some(&q)) => {
188                    j += 1;
189                    q
190                }
191                (None, None) => unreachable!(),
192            };
193            if n == k {
194                return None;
195            }
196            out[n] = take;
197            n += 1;
198        }
199        Some(Cut { len: n as u8, leaves: out, arrival: 0 })
200    }
201}
202
203/// A LUT of the cover: its root node and its leaves, nodes of the balanced network.
204#[derive(Clone, Debug, PartialEq, Eq)]
205pub struct Lut {
206    pub root: u32,
207    pub leaves: Vec<u32>,
208}
209
210/// A network mapped onto LUTs.
211#[derive(Clone, Debug)]
212pub struct Mapping {
213    /// The network rebuilt with its supergates balanced.
214    pub xag: Xag,
215    /// The literal of the balanced network each original node is; `None` for a supergate's inner node, which
216    /// nothing outside its supergate reads.
217    pub image: Vec<Option<Lit>>,
218    /// The original node each balanced node stands for: the node it computes when `exact`, else the root of the
219    /// supergate whose balancing made it.
220    pub origin: Vec<u32>,
221    pub exact: Vec<bool>,
222    /// Each balanced node's LUT level: 0 for an input.
223    pub level: Vec<u32>,
224    /// The cover: a LUT for each node an output needs, in reverse topological order.
225    pub luts: Vec<Lut>,
226}
227
228struct Builder<'a> {
229    k: usize,
230    old: &'a Xag,
231    xag: Xag,
232    cuts: Vec<Vec<Cut>>,
233    level: Vec<u32>,
234    origin: Vec<u32>,
235    exact: Vec<bool>,
236}
237
238impl Builder<'_> {
239    /// Record a node the balanced network just made or found, its cuts and level, standing for `origin`.
240    fn note(&mut self, l: Lit, origin: u32, exact: bool) -> Lit {
241        let n = node(l);
242        if n < self.cuts.len() {
243            return l;
244        }
245        self.origin.push(origin);
246        self.exact.push(exact);
247        let (cuts, level) = match self.xag.gate(n) {
248            Gate::Constant | Gate::Input => (Vec::new(), 0),
249            Gate::And(a, b) | Gate::Xor(a, b) => {
250                let (a, b) = (node(a), node(b));
251                let mut found: Vec<Cut> = Vec::with_capacity(CUTS * 4);
252                let side = |m: usize, cuts: &[Vec<Cut>], level: &[u32]| {
253                    let mut unit = Cut::unit(m as u32);
254                    unit.arrival = level[m];
255                    std::iter::once(unit).chain(cuts[m].iter().copied()).collect::<Vec<_>>()
256                };
257                let (left, right) = (side(a, &self.cuts, &self.level), side(b, &self.cuts, &self.level));
258                for x in &left {
259                    for y in &right {
260                        if let Some(mut c) = Cut::merge(x, y, self.k) {
261                            c.arrival = c.leaves().iter().map(|&m| self.level[m as usize]).max().unwrap_or(0) + 1;
262                            if !found.iter().any(|f| f.leaves() == c.leaves()) {
263                                found.push(c);
264                            }
265                        }
266                    }
267                }
268                found.sort_by_key(|c| (c.arrival, c.len));
269                found.truncate(CUTS);
270                let level = found.first().map_or(0, |c| c.arrival);
271                (found, level)
272            }
273        };
274        self.cuts.push(cuts);
275        self.level.push(level);
276        l
277    }
278
279    fn input(&mut self, origin: u32) -> Lit {
280        let l = self.xag.input();
281        self.note(l, origin, true)
282    }
283
284    fn gate(&mut self, xor: bool, a: Lit, b: Lit, origin: u32) -> Lit {
285        let l = if xor { self.xag.xor(a, b) } else { self.xag.and(a, b) };
286        self.note(l, origin, false)
287    }
288
289    /// `leaves` combined by AND or XOR, `k` at a time from the earliest-arriving, each group a balanced binary tree.
290    fn supergate(&mut self, xor: bool, leaves: Vec<Lit>, origin: u32) -> Lit {
291        let mut heap: BinaryHeap<Reverse<(u32, Lit)>> = leaves.into_iter().map(|l| Reverse((self.level[node(l)], l))).collect();
292        loop {
293            let take = heap.len().min(self.k);
294            let mut group: Vec<Lit> = (0..take).map(|_| heap.pop().expect("take ≤ len").0 .1).collect();
295            while group.len() > 1 {
296                group = group.chunks(2).map(|p| if p.len() == 2 { self.gate(xor, p[0], p[1], origin) } else { p[0] }).collect();
297            }
298            let root = group.first().copied().unwrap_or(if xor { FALSE } else { TRUE });
299            if heap.is_empty() {
300                return root;
301            }
302            heap.push(Reverse((self.level[node(root)], root)));
303        }
304    }
305}
306
307/// Map `xag` onto LUTs of at most `k` inputs (`2 ≤ k ≤ MAX_K`), its supergates confined to `group`s (one entry a
308/// node), covering the nodes `outputs` read.
309pub fn map(xag: &Xag, group: &[u32], outputs: &[Lit], k: usize) -> Mapping {
310    assert!((2..=MAX_K).contains(&k), "a LUT has 2 to {MAX_K} inputs");
311    assert_eq!(group.len(), xag.len(), "a group for every node");
312    let n = xag.len();
313    let mut fanout = vec![0u32; n];
314    let mut reader = vec![usize::MAX; n];
315    for (m, g) in xag.gates.iter().enumerate() {
316        if let Gate::And(a, b) | Gate::Xor(a, b) = *g {
317            for l in [a, b] {
318                fanout[node(l)] += 1;
319                reader[node(l)] = m;
320            }
321        }
322    }
323    for &l in outputs {
324        fanout[node(l)] += 1;
325        reader[node(l)] = usize::MAX;
326    }
327    // A supergate's inner node: one reader, of its own kind and group, by a plain edge for an AND.
328    let inner: Vec<bool> = (0..n)
329        .map(|m| {
330            let r = reader[m];
331            if fanout[m] != 1 || r == usize::MAX || group[r] != group[m] {
332                return false;
333            }
334            match (xag.gates[m], xag.gates[r]) {
335                (Gate::And(..), Gate::And(a, b)) => [a, b].iter().any(|&l| node(l) == m && !complemented(l)),
336                (Gate::Xor(..), Gate::Xor(..)) => true,
337                _ => false,
338            }
339        })
340        .collect();
341    let mut b = Builder { k, old: xag, xag: Xag::new(), cuts: vec![Vec::new()], level: vec![0], origin: vec![0], exact: vec![true] };
342    let mut image: Vec<Option<Lit>> = vec![None; n];
343    image[0] = Some(FALSE);
344    for m in 1..n {
345        if inner[m] {
346            continue;
347        }
348        let gate = b.old.gates[m];
349        let img = match gate {
350            Gate::Constant => FALSE,
351            Gate::Input => b.input(m as u32),
352            Gate::And(x, y) | Gate::Xor(x, y) => {
353                let xor = matches!(gate, Gate::Xor(..));
354                let mut parity = 0;
355                let mut leaves = Vec::new();
356                let mut stack = vec![x, y];
357                while let Some(l) = stack.pop() {
358                    let f = node(l);
359                    if inner[f] {
360                        if xor {
361                            parity ^= l & 1;
362                        }
363                        if let Gate::And(p, q) | Gate::Xor(p, q) = b.old.gates[f] {
364                            stack.push(p);
365                            stack.push(q);
366                        }
367                        continue;
368                    }
369                    let mapped = image[f].expect("a leaf comes before its supergate") ^ (l & 1);
370                    if xor {
371                        parity ^= mapped & 1;
372                        leaves.push(mapped & !1);
373                    } else {
374                        leaves.push(mapped);
375                    }
376                }
377                leaves.sort_unstable();
378                if xor {
379                    let mut kept: Vec<Lit> = Vec::with_capacity(leaves.len());
380                    for l in leaves {
381                        if kept.last() == Some(&l) {
382                            kept.pop();
383                        } else {
384                            kept.push(l);
385                        }
386                    }
387                    leaves = kept;
388                } else {
389                    leaves.dedup();
390                }
391                let out = if !xor && leaves.windows(2).any(|w| w[0] ^ 1 == w[1]) || !xor && leaves.contains(&FALSE) {
392                    FALSE
393                } else {
394                    leaves.retain(|&l| l != if xor { FALSE } else { TRUE });
395                    b.supergate(xor, leaves, m as u32) ^ parity
396                };
397                let n_out = node(out);
398                if n_out < b.exact.len() && b.origin[n_out] == m as u32 {
399                    b.exact[n_out] = true;
400                }
401                out
402            }
403        };
404        image[m] = Some(img);
405    }
406    let size = b.xag.len();
407    let mut required = vec![false; size];
408    for &l in outputs {
409        if let Some(img) = image[node(l)] {
410            required[node(img)] = true;
411        }
412    }
413    let mut luts = Vec::new();
414    for m in (1..size).rev() {
415        if !required[m] {
416            continue;
417        }
418        if let Some(best) = b.cuts[m].first() {
419            for &leaf in best.leaves() {
420                required[leaf as usize] = true;
421            }
422            luts.push(Lut { root: m as u32, leaves: best.leaves().to_vec() });
423        }
424    }
425    Mapping { xag: b.xag, image, origin: b.origin, exact: b.exact, level: b.level, luts }
426}
427
428/// The truth table of `root` over `leaves` (at most six): bit `i` of the table is the root's value when leaf `j`
429/// holds bit `j` of `i`. Every path from the root down must end at a leaf, as a cut's do.
430pub fn function(xag: &Xag, root: u32, leaves: &[u32]) -> u64 {
431    assert!(leaves.len() <= 6, "a table of at most six inputs");
432    const VARS: [u64; 6] = [
433        0xAAAA_AAAA_AAAA_AAAA,
434        0xCCCC_CCCC_CCCC_CCCC,
435        0xF0F0_F0F0_F0F0_F0F0,
436        0xFF00_FF00_FF00_FF00,
437        0xFFFF_0000_FFFF_0000,
438        0xFFFF_FFFF_0000_0000,
439    ];
440    let mut value: HashMap<u32, u64> = leaves.iter().enumerate().map(|(i, &l)| (l, VARS[i])).collect();
441    value.entry(0).or_insert(0);
442    let mut stack = vec![root];
443    while let Some(&n) = stack.last() {
444        if value.contains_key(&n) {
445            stack.pop();
446            continue;
447        }
448        let (a, b) = match xag.gate(n as usize) {
449            Gate::And(a, b) | Gate::Xor(a, b) => (a, b),
450            Gate::Input | Gate::Constant => panic!("node {n} is below the cut"),
451        };
452        let missing: Vec<u32> = [a, b].iter().map(|&l| node(l) as u32).filter(|m| !value.contains_key(m)).collect();
453        if !missing.is_empty() {
454            stack.extend(missing);
455            continue;
456        }
457        let lit = |l: Lit| if complemented(l) { !value[&(node(l) as u32)] } else { value[&(node(l) as u32)] };
458        let v = match xag.gate(n as usize) {
459            Gate::And(..) => lit(a) & lit(b),
460            _ => lit(a) ^ lit(b),
461        };
462        value.insert(n, v);
463        stack.pop();
464    }
465    let width = 1u32 << leaves.len();
466    let mask = if width == 64 { u64::MAX } else { (1u64 << width) - 1 };
467    value[&root] & mask
468}
469
470#[cfg(test)]
471#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/codegen_sva/lutmap/tests.rs"]
472mod tests;
logicaffeine_compile/codegen_sva/lutmap.rs

logicaffeine_compile/codegen_sva/
lutmap.rs
