logicaffeine_compile/codegen_sva/
mul_tree.rs

1//! mul_tree — a word multiply as an aligned tree of adds. The product `a · x mod 2^w` is the sum of the `w` partial
2//! products `x[i] ? a << i : 0`; the tree adds them pairwise, level by level, each add only as wide as the bits it can
3//! still change (a partial product shifted by `i` is zero below bit `i`, and nothing above bit `w − 1` survives), and
4//! a register can follow any level. On a fabric with carry chains every add is one chain and nothing multiplies; cut
5//! after every level, no stage holds more than one add.
6
7/// The tree of one multiply: its declarations and combinational assignments, its registers with the value each takes
8/// every clock, the signal holding the product after the last level, and the clocks from its operands to it.
9#[derive(Clone, Debug, PartialEq)]
10pub struct MulTree {
11    pub wires: String,
12    pub regs: Vec<(String, u32)>,
13    pub moves: Vec<(String, String)>,
14    pub product: String,
15    pub latency: u32,
16}
17
18/// The levels of the tree over `width` partial products: the pairwise adds that bring them down to one.
19pub fn mul_tree_levels(width: u32) -> usize {
20    let mut terms = width as usize;
21    let mut levels = 0;
22    while terms > 1 {
23        terms = terms.div_ceil(2);
24        levels += 1;
25    }
26    levels
27}
28
29/// The product `a · x mod 2^width` of the `width`-bit Verilog expressions `a` and `x`, its signals named after
30/// `prefix`, registered after each level `level` for which `cut(level)` holds (the last level's sum is the product).
31pub fn mul_tree(prefix: &str, a: &str, x: &str, width: u32, cut: impl Fn(usize) -> bool) -> MulTree {
32    assert!(width >= 2, "a multiply of at least two bits");
33    let w = width;
34    let mut wires = String::new();
35    let mut regs = Vec::new();
36    let mut moves = Vec::new();
37    // a term: (signal, offset): bits [w-1:offset] of the product's partial sum, in w - offset bits
38    let mut terms: Vec<(String, u32)> = (0..w)
39        .map(|i| {
40            let name = format!("{prefix}_r{i}");
41            let bits = w - i;
42            wires.push_str(&format!("  wire [{}:0] {name} = {{{bits}{{{x}[{i}]}}}} & {a}[{}:0];\n", bits - 1, bits - 1));
43            (name, i)
44        })
45        .collect();
46    let mut latency = 0;
47    let mut level = 0;
48    while terms.len() > 1 {
49        let mut next = Vec::with_capacity(terms.len().div_ceil(2));
50        for (k, pair) in terms.chunks(2).enumerate() {
51            if pair.len() == 1 {
52                next.push(pair[0].clone());
53                continue;
54            }
55            let ((a_name, oa), (b_name, ob)) = (&pair[0], &pair[1]);
56            let d = ob - oa;
57            let name = format!("{prefix}_s{level}_{k}");
58            let (abits, high) = (w - oa, w - ob);
59            wires.push_str(&format!("  wire [{}:0] {name}_h = {a_name}[{}:{d}] + {b_name};\n", high - 1, abits - 1));
60            wires.push_str(&format!("  wire [{}:0] {name} = {{{name}_h, {a_name}[{}:0]}};\n", abits - 1, d - 1));
61            next.push((name, *oa));
62        }
63        if cut(level) {
64            for (name, offset) in next.iter_mut() {
65                let reg = format!("{name}_q");
66                regs.push((reg.clone(), w - *offset));
67                moves.push((reg.clone(), name.clone()));
68                *name = reg;
69            }
70            latency += 1;
71        }
72        terms = next;
73        level += 1;
74    }
75    MulTree { wires, regs, moves, product: terms.remove(0).0, latency }
76}
77
78#[cfg(test)]
79#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/codegen_sva/mul_tree/tests.rs"]
80mod tests;
logicaffeine_compile/codegen_sva/mul_tree.rs

logicaffeine_compile/codegen_sva/
mul_tree.rs
