prjunnamed_generic/
merge.rs

1use std::{borrow::Cow, collections::HashMap};
2
3use prjunnamed_netlist::{Cell, Design, Value};
4
5struct Numberer(HashMap<Cell, Value>);
6
7impl Numberer {
8    fn new() -> Self {
9        Numberer(HashMap::new())
10    }
11
12    fn find_or_insert<'a>(&mut self, cell: Cell, value: impl Into<Cow<'a, Value>>) -> Value {
13        self.0.entry(cell).or_insert_with(|| value.into().into_owned()).clone()
14    }
15
16    fn bitwise_unary<F>(&mut self, rebuild: F, arg: Value, out: &Value) -> Value
17    where
18        F: Fn(Value) -> Cell,
19    {
20        let mut result = Value::new();
21        for (out_net, arg_net) in out.iter().zip(arg.iter()) {
22            let bit_cell = rebuild(Value::from(arg_net));
23            result.extend(self.find_or_insert(bit_cell, out_net));
24        }
25        result
26    }
27
28    fn commutative_bitwise_binary<F>(&mut self, rebuild: F, arg1: Value, arg2: Value, out: &Value) -> Value
29    where
30        F: Fn(Value, Value) -> Cell,
31    {
32        let mut result = Value::new();
33        for (out_net, (arg1_net, arg2_net)) in out.iter().zip(arg1.iter().zip(arg2.iter())) {
34            let (arg1_net, arg2_net) = if arg1_net <= arg2_net { (arg1_net, arg2_net) } else { (arg2_net, arg1_net) };
35            let bit_cell = rebuild(Value::from(arg1_net), Value::from(arg2_net));
36            result.extend(self.find_or_insert(bit_cell, out_net));
37        }
38        result
39    }
40
41    fn bitwise_binary<F>(&mut self, rebuild: F, arg1: Value, arg2: Value, out: &Value) -> Value
42    where
43        F: Fn(Value, Value) -> Cell,
44    {
45        let mut result = Value::new();
46        for (out_net, (arg1_net, arg2_net)) in out.iter().zip(arg1.iter().zip(arg2.iter())) {
47            let bit_cell = rebuild(Value::from(arg1_net), Value::from(arg2_net));
48            result.extend(self.find_or_insert(bit_cell, out_net));
49        }
50        result
51    }
52
53    fn commutative_binary<F>(&mut self, rebuild: F, arg1: Value, arg2: Value, out: &Value) -> Value
54    where
55        F: Fn(Value, Value) -> Cell,
56    {
57        let (arg1, arg2) = if arg1 <= arg2 { (arg1, arg2) } else { (arg2, arg1) };
58        let cell = rebuild(arg1, arg2);
59        self.find_or_insert(cell, out)
60    }
61}
62
63pub fn merge(design: &mut Design) -> bool {
64    let mut numberer = Numberer::new();
65    for cell_ref in design.iter_cells_topo().filter(|cell_ref| !cell_ref.get().has_effects(design)) {
66        let mut cell = cell_ref.get().into_owned();
67        if let Cell::Const(_) = cell {
68            continue;
69        }
70        cell.visit_mut(|net| *net = design.map_net(*net));
71        let output = cell_ref.output();
72        let canon = match cell {
73            Cell::Buf(arg) => numberer.bitwise_unary(Cell::Buf, arg, &output),
74            Cell::Not(arg) => numberer.bitwise_unary(Cell::Not, arg, &output),
75            Cell::And(arg1, arg2) => numberer.commutative_bitwise_binary(Cell::And, arg1, arg2, &output),
76            Cell::Or(arg1, arg2) => numberer.commutative_bitwise_binary(Cell::Or, arg1, arg2, &output),
77            Cell::Xor(arg1, arg2) => numberer.commutative_bitwise_binary(Cell::Xor, arg1, arg2, &output),
78            Cell::Mux(arg1, arg2, arg3) => {
79                numberer.bitwise_binary(|arg2, arg3| Cell::Mux(arg1, arg2, arg3), arg2, arg3, &output)
80            }
81            Cell::Adc(arg1, arg2, arg3) => {
82                numberer.commutative_binary(|arg1, arg2| Cell::Adc(arg1, arg2, arg3), arg1, arg2, &output)
83            }
84            Cell::Eq(arg1, arg2) => numberer.commutative_binary(Cell::Eq, arg1, arg2, &output),
85            Cell::Mul(arg1, arg2) => numberer.commutative_binary(Cell::Mul, arg1, arg2, &output),
86            Cell::Aig(arg1, arg2) => {
87                let (arg1, arg2) = if arg1 <= arg2 { (arg1, arg2) } else { (arg2, arg1) };
88                let cell = Cell::Aig(arg1, arg2);
89                numberer.find_or_insert(cell, &output)
90            }
91            _ => numberer.find_or_insert(cell, &output),
92        };
93        if cfg!(feature = "trace") && output != canon {
94            eprintln!(">merge {} => {}", design.display_value(&output), design.display_value(&canon));
95        }
96        for canon_net in canon.iter() {
97            let (canon_cell_ref, _offset) = design.find_cell(canon_net);
98            canon_cell_ref.append_metadata(cell_ref.metadata());
99        }
100        design.replace_value(output, canon);
101    }
102    design.compact()
103}
104
105#[cfg(test)]
106mod test {
107    use prjunnamed_netlist::{assert_isomorphic, Design, Value};
108
109    use crate::merge::merge;
110
111    #[test]
112    fn test_merge_commutative_xor() {
113        let mut dl = Design::new();
114        let a = dl.add_input("a", 2);
115        let b = dl.add_input("b", 2);
116        let x1 = dl.add_xor1(a[0], b[0]);
117        let x2 = dl.add_xor1(a[1], b[1]);
118        let x3 = dl.add_xor(b, a);
119        dl.add_output("y", Value::from(x1).concat(x2).concat(x3));
120        dl.apply();
121        merge(&mut dl);
122
123        let mut dr = Design::new();
124        let a = dr.add_input("a", 2);
125        let b = dr.add_input("b", 2);
126        let x1 = dr.add_xor1(a[0], b[0]);
127        let x2 = dr.add_xor1(a[1], b[1]);
128        dr.add_output("y", Value::from(x1).concat(x2).concat(x1).concat(x2));
129        dr.apply();
130
131        assert_isomorphic!(dl, dr);
132    }
133}
prjunnamed_generic/merge.rs

prjunnamed_generic/
merge.rs
