prjunnamed_netlist/
isomorphic.rs

1use std::fmt::Display;
2use std::collections::{BTreeMap, BTreeSet};
3
4use crate::{Cell, Design, IoNet, Net, Value};
5
6#[derive(Debug)]
7pub enum NotIsomorphic {
8    NoOutputLeft(String),
9    NoOutputRight(String),
10    OutputSizeMismatch(String),
11    IoSizeMismatch(String),
12    NameSizeMismatch(String),
13    ValueSizeMismatch(Value, Value),
14    NetMismatch(Net, Net),
15    IoNetMismatch(IoNet, IoNet),
16}
17
18impl Display for NotIsomorphic {
19    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
20        match self {
21            NotIsomorphic::NoOutputLeft(name) => write!(f, "output {:?} is missing in the left design", name),
22            NotIsomorphic::NoOutputRight(name) => write!(f, "output {:?} is missing in the right design", name),
23            NotIsomorphic::OutputSizeMismatch(name) => write!(f, "size of output {:?} does not match", name),
24            NotIsomorphic::IoSizeMismatch(name) => write!(f, "size of IO {:?} does not match", name),
25            NotIsomorphic::NameSizeMismatch(name) => write!(f, "size of name cell {:?} does not match", name),
26            NotIsomorphic::ValueSizeMismatch(value_l, value_r) => {
27                write!(f, "size of values {} and {} do not match", value_l, value_r)
28            }
29            NotIsomorphic::NetMismatch(net_l, net_r) => write!(f, "nets {} and {} are not isomorphic", net_l, net_r),
30            NotIsomorphic::IoNetMismatch(io_net_l, io_net_r) => {
31                write!(f, "IO nets {} and {} are not isomorphic", io_net_l, io_net_r)
32            }
33        }
34    }
35}
36
37// Beware: this function will ignore instances that have no output bits.
38pub fn isomorphic(lft: &Design, rgt: &Design) -> Result<(), NotIsomorphic> {
39    let mut queue: BTreeSet<(Net, Net)> = BTreeSet::new();
40    fn queue_vals(queue: &mut BTreeSet<(Net, Net)>, val_l: &Value, val_r: &Value) -> Result<(), NotIsomorphic> {
41        if val_l.len() != val_r.len() {
42            return Err(NotIsomorphic::ValueSizeMismatch(val_l.clone(), val_r.clone()));
43        }
44        for (net_l, net_r) in val_l.iter().zip(val_r) {
45            queue.insert((net_l, net_r));
46        }
47        Ok(())
48    }
49
50    let mut visited: BTreeSet<(Net, Net)> = BTreeSet::new();
51    visited.insert((Net::UNDEF, Net::UNDEF));
52    visited.insert((Net::ZERO, Net::ZERO));
53    visited.insert((Net::ONE, Net::ONE));
54    let mut outputs_l = BTreeMap::new();
55    let mut names_l = BTreeMap::new();
56    for cell in lft.iter_cells() {
57        match &*cell.get() {
58            Cell::Output(name, value) => {
59                outputs_l.insert(name.clone(), value.clone());
60            }
61            Cell::Name(name, value) => {
62                names_l.insert(name.clone(), value.clone());
63            }
64            _ => (),
65        }
66    }
67    let mut outputs_r = BTreeMap::new();
68    let mut names_r = BTreeMap::new();
69    for cell in rgt.iter_cells() {
70        match &*cell.get() {
71            Cell::Output(name, value) => {
72                outputs_r.insert(name.clone(), value.clone());
73            }
74            Cell::Name(name, value) => {
75                names_r.insert(name.clone(), value.clone());
76            }
77            _ => (),
78        }
79    }
80    for (name, value_l) in &outputs_l {
81        if let Some(value_r) = outputs_r.get(name) {
82            if value_l.len() != value_r.len() {
83                return Err(NotIsomorphic::OutputSizeMismatch(name.clone()));
84            }
85            for (net_l, net_r) in value_l.iter().zip(value_r) {
86                queue.insert((net_l, net_r));
87            }
88        } else {
89            return Err(NotIsomorphic::NoOutputRight(name.clone()));
90        }
91    }
92    for name in outputs_r.keys() {
93        if !outputs_l.contains_key(name) {
94            return Err(NotIsomorphic::NoOutputLeft(name.clone()));
95        }
96    }
97    for (name, value_l) in &names_l {
98        if let Some(value_r) = names_r.get(name) {
99            if value_l.len() != value_r.len() {
100                return Err(NotIsomorphic::NameSizeMismatch(name.clone()));
101            }
102            for (net_l, net_r) in value_l.iter().zip(value_r) {
103                queue.insert((net_l, net_r));
104            }
105        }
106    }
107    let mut ios = BTreeSet::new();
108    ios.insert((IoNet::FLOATING, IoNet::FLOATING));
109    for (name, _) in lft.iter_ios() {
110        if let (Some(io_l), Some(io_r)) = (lft.get_io(name), rgt.get_io(name)) {
111            if io_l.len() != io_r.len() {
112                return Err(NotIsomorphic::IoSizeMismatch(name.to_owned()));
113            }
114            for (ionet_l, ionet_r) in io_l.iter().zip(io_r.iter()) {
115                ios.insert((ionet_l, ionet_r));
116            }
117        }
118    }
119    while let Some((net_l, net_r)) = queue.pop_first() {
120        if visited.contains(&(net_l, net_r)) {
121            continue;
122        }
123        if net_l.as_const().is_some() || net_r.as_const().is_some() {
124            // (const, const) pairs already added to visitted at the beginning
125            return Err(NotIsomorphic::NetMismatch(net_l, net_r));
126        }
127        let (cell_l, bit_l) = lft.find_cell(net_l).unwrap();
128        let (cell_r, bit_r) = rgt.find_cell(net_r).unwrap();
129        let out_l = cell_l.output();
130        let out_r = cell_r.output();
131        if bit_l != bit_r || out_l.len() != out_r.len() {
132            return Err(NotIsomorphic::NetMismatch(net_l, net_r));
133        }
134        for (net_l, net_r) in out_l.iter().zip(out_r) {
135            visited.insert((net_l, net_r));
136        }
137        match (&*cell_l.get(), &*cell_r.get()) {
138            (Cell::Buf(val_l), Cell::Buf(val_r)) | (Cell::Not(val_l), Cell::Not(val_r)) => {
139                queue_vals(&mut queue, val_l, val_r)?
140            }
141            (Cell::And(arg1_l, arg2_l), Cell::And(arg1_r, arg2_r))
142            | (Cell::Or(arg1_l, arg2_l), Cell::Or(arg1_r, arg2_r))
143            | (Cell::Xor(arg1_l, arg2_l), Cell::Xor(arg1_r, arg2_r))
144            | (Cell::Eq(arg1_l, arg2_l), Cell::Eq(arg1_r, arg2_r))
145            | (Cell::ULt(arg1_l, arg2_l), Cell::ULt(arg1_r, arg2_r))
146            | (Cell::SLt(arg1_l, arg2_l), Cell::SLt(arg1_r, arg2_r))
147            | (Cell::Mul(arg1_l, arg2_l), Cell::Mul(arg1_r, arg2_r))
148            | (Cell::UDiv(arg1_l, arg2_l), Cell::UDiv(arg1_r, arg2_r))
149            | (Cell::UMod(arg1_l, arg2_l), Cell::UMod(arg1_r, arg2_r))
150            | (Cell::SDivTrunc(arg1_l, arg2_l), Cell::SDivTrunc(arg1_r, arg2_r))
151            | (Cell::SDivFloor(arg1_l, arg2_l), Cell::SDivFloor(arg1_r, arg2_r))
152            | (Cell::SModTrunc(arg1_l, arg2_l), Cell::SModTrunc(arg1_r, arg2_r))
153            | (Cell::SModFloor(arg1_l, arg2_l), Cell::SModFloor(arg1_r, arg2_r)) => {
154                queue_vals(&mut queue, arg1_l, arg1_r)?;
155                queue_vals(&mut queue, arg2_l, arg2_r)?;
156            }
157            (Cell::Mux(arg1_l, arg2_l, arg3_l), Cell::Mux(sel_r, arg2_r, arg3_r)) => {
158                queue.insert((*arg1_l, *sel_r));
159                queue_vals(&mut queue, arg2_l, arg2_r)?;
160                queue_vals(&mut queue, arg3_l, arg3_r)?;
161            }
162            (Cell::Adc(arg1_l, arg2_l, arg3_l), Cell::Adc(arg1_r, arg2_r, arg3_r)) => {
163                queue_vals(&mut queue, arg1_l, arg1_r)?;
164                queue_vals(&mut queue, arg2_l, arg2_r)?;
165                queue.insert((*arg3_l, *arg3_r));
166            }
167            (Cell::Aig(arg1_l, arg2_l), Cell::Aig(arg1_r, arg2_r)) => {
168                queue.insert((arg1_l.net(), arg1_r.net()));
169                queue.insert((arg2_l.net(), arg2_r.net()));
170                if arg1_l.is_positive() != arg1_r.is_positive() || arg2_l.is_positive() != arg2_r.is_positive() {
171                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
172                }
173            }
174            (Cell::Shl(arg1_l, arg2_l, stride_l), Cell::Shl(arg1_r, arg2_r, stride_r))
175            | (Cell::UShr(arg1_l, arg2_l, stride_l), Cell::UShr(arg1_r, arg2_r, stride_r))
176            | (Cell::SShr(arg1_l, arg2_l, stride_l), Cell::SShr(arg1_r, arg2_r, stride_r))
177            | (Cell::XShr(arg1_l, arg2_l, stride_l), Cell::XShr(arg1_r, arg2_r, stride_r)) => {
178                queue_vals(&mut queue, arg1_l, arg1_r)?;
179                queue_vals(&mut queue, arg2_l, arg2_r)?;
180                if stride_l != stride_r {
181                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
182                }
183            }
184            (Cell::Dff(ff_l), Cell::Dff(ff_r)) => {
185                queue_vals(&mut queue, &ff_l.data, &ff_r.data)?;
186                queue.insert((ff_l.clock.net(), ff_r.clock.net()));
187                queue.insert((ff_l.clear.net(), ff_r.clear.net()));
188                queue.insert((ff_l.reset.net(), ff_r.reset.net()));
189                queue.insert((ff_l.enable.net(), ff_r.enable.net()));
190                if ff_l.clock.is_positive() != ff_r.clock.is_positive()
191                    || ff_l.clear.is_positive() != ff_r.clear.is_positive()
192                    || ff_l.reset.is_positive() != ff_r.reset.is_positive()
193                    || ff_l.enable.is_positive() != ff_r.enable.is_positive()
194                    || (ff_l.reset_over_enable != ff_r.reset_over_enable
195                        && !ff_l.reset.is_always(false)
196                        && !ff_l.enable.is_always(true))
197                    || ff_l.clear_value != ff_r.clear_value
198                    || ff_l.reset_value != ff_r.reset_value
199                    || ff_l.init_value != ff_r.init_value
200                {
201                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
202                }
203            }
204            (Cell::IoBuf(iobuf_l), Cell::IoBuf(iobuf_r)) => {
205                for (io_net_l, io_net_r) in iobuf_l.io.iter().zip(iobuf_r.io.iter()) {
206                    if !ios.contains(&(io_net_l, io_net_r)) {
207                        return Err(NotIsomorphic::IoNetMismatch(io_net_l, io_net_r));
208                    }
209                }
210                queue_vals(&mut queue, &iobuf_l.output, &iobuf_r.output)?;
211                queue.insert((iobuf_l.enable.net(), iobuf_r.enable.net()));
212                if iobuf_l.enable.is_positive() != iobuf_r.enable.is_positive() {
213                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
214                }
215            }
216            (Cell::Memory(memory_l), Cell::Memory(memory_r)) => {
217                if memory_l.depth != memory_r.depth
218                    || memory_l.width != memory_r.width
219                    || memory_l.init_value != memory_r.init_value
220                    || memory_l.write_ports.len() != memory_r.write_ports.len()
221                    || memory_l.read_ports.len() != memory_r.read_ports.len()
222                {
223                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
224                }
225                for (write_port_l, write_port_r) in memory_l.write_ports.iter().zip(memory_r.write_ports.iter()) {
226                    queue_vals(&mut queue, &write_port_l.addr, &write_port_r.addr)?;
227                    queue_vals(&mut queue, &write_port_l.data, &write_port_r.data)?;
228                    queue_vals(&mut queue, &write_port_l.mask, &write_port_r.mask)?;
229                    queue.insert((write_port_l.clock.net(), write_port_r.clock.net()));
230                    if write_port_l.clock.is_positive() != write_port_r.clock.is_positive() {
231                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
232                    }
233                }
234                for (read_port_l, read_port_r) in memory_l.read_ports.iter().zip(memory_r.read_ports.iter()) {
235                    queue_vals(&mut queue, &read_port_l.addr, &read_port_r.addr)?;
236                    if read_port_l.data_len != read_port_r.data_len {
237                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
238                    }
239                    match (&read_port_l.flip_flop, &read_port_r.flip_flop) {
240                        (None, None) => (),
241                        (Some(ff_l), Some(ff_r)) => {
242                            queue.insert((ff_l.clock.net(), ff_r.clock.net()));
243                            queue.insert((ff_l.clear.net(), ff_r.clear.net()));
244                            queue.insert((ff_l.reset.net(), ff_r.reset.net()));
245                            queue.insert((ff_l.enable.net(), ff_r.enable.net()));
246                            if ff_l.clock.is_positive() != ff_r.clock.is_positive()
247                                || ff_l.clear.is_positive() != ff_r.clear.is_positive()
248                                || ff_l.reset.is_positive() != ff_r.reset.is_positive()
249                                || ff_l.enable.is_positive() != ff_r.enable.is_positive()
250                                || (ff_l.reset_over_enable != ff_r.reset_over_enable
251                                    && !ff_l.reset.is_always(false)
252                                    && !ff_l.enable.is_always(true))
253                                || ff_l.clear_value != ff_r.clear_value
254                                || ff_l.reset_value != ff_r.reset_value
255                                || ff_l.init_value != ff_r.init_value
256                                || ff_l.relations != ff_r.relations
257                            {
258                                return Err(NotIsomorphic::NetMismatch(net_l, net_r));
259                            }
260                        }
261                        _ => return Err(NotIsomorphic::NetMismatch(net_l, net_r)),
262                    }
263                }
264            }
265            (Cell::Target(target_cell_l), Cell::Target(target_cell_r)) => {
266                for (io_net_l, io_net_r) in target_cell_l.ios.iter().zip(target_cell_r.ios.iter()) {
267                    if !ios.contains(&(io_net_l, io_net_r)) {
268                        return Err(NotIsomorphic::IoNetMismatch(io_net_l, io_net_r));
269                    }
270                }
271                if target_cell_l.kind != target_cell_r.kind || target_cell_l.params != target_cell_r.params {
272                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
273                }
274                queue_vals(&mut queue, &target_cell_l.inputs, &target_cell_r.inputs)?;
275            }
276            (Cell::Other(inst_l), Cell::Other(inst_r)) => {
277                if inst_l.kind != inst_r.kind || inst_l.params != inst_r.params || inst_l.outputs != inst_r.outputs {
278                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
279                }
280                for (name, value_l) in &inst_l.inputs {
281                    let Some(value_r) = inst_r.inputs.get(name) else {
282                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
283                    };
284                    queue_vals(&mut queue, value_l, value_r)?;
285                }
286                for name in inst_r.inputs.keys() {
287                    if !inst_l.inputs.contains_key(name) {
288                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
289                    }
290                }
291                for (name, io_value_l) in &inst_l.ios {
292                    let Some(io_value_r) = inst_r.ios.get(name) else {
293                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
294                    };
295                    for (io_net_l, io_net_r) in io_value_l.iter().zip(io_value_r.iter()) {
296                        if !ios.contains(&(io_net_l, io_net_r)) {
297                            return Err(NotIsomorphic::IoNetMismatch(io_net_l, io_net_r));
298                        }
299                    }
300                }
301                for name in inst_r.ios.keys() {
302                    if !inst_l.ios.contains_key(name) {
303                        return Err(NotIsomorphic::NetMismatch(net_l, net_r));
304                    }
305                }
306            }
307            (Cell::Input(name_l, _), Cell::Input(name_r, _)) => {
308                if name_l != name_r {
309                    return Err(NotIsomorphic::NetMismatch(net_l, net_r));
310                }
311            }
312            _ => return Err(NotIsomorphic::NetMismatch(net_l, net_r)),
313        }
314    }
315    Ok(())
316}
317
318#[macro_export]
319macro_rules! assert_isomorphic {
320    ( $lft:ident, $rgt:ident ) => {
321        $lft.apply();
322        $rgt.apply();
323        let result = prjunnamed_netlist::isomorphic(&$lft, &$rgt);
324        if let Err(error) = result {
325            panic!("{}\nleft design:\n{}\nright design:\n{}", error, $lft, $rgt);
326        }
327    };
328}
prjunnamed_netlist/isomorphic.rs

prjunnamed_netlist/
isomorphic.rs
