Skip to main content

prjunnamed_netlist/
smt.rs

1use std::{borrow::Cow, cell::RefCell, collections::BTreeMap};
2
3use crate::{AssignCell, Cell, Const, ConstBit, ConstSlice, ControlNet, Design, MatchCell, Value, ValueBit, ValueSlice};
4
5#[cfg(feature = "easy-smt")]
6pub mod easy_smt;
7
8#[derive(Debug, Clone)]
9pub enum SmtResponse {
10    Sat,
11    Unsat,
12    Unknown,
13}
14
15struct SmtTritVec<SMT: SmtEngine> {
16    x: SMT::BitVec, // is undef?
17    y: SMT::BitVec, // if not undef, is one?
18}
19
20pub trait SmtEngine {
21    type Bool: Clone;
22    type BitVec: Clone;
23
24    fn build_bool_lit(&self, value: bool) -> Self::Bool;
25    fn build_bool_eq(&self, arg1: Self::Bool, arg2: Self::Bool) -> Self::Bool;
26    fn build_bool_ite(&self, cond: Self::Bool, if_true: Self::Bool, if_false: Self::Bool) -> Self::Bool;
27    fn build_bool_let(&self, var: &str, expr: Self::Bool, body: impl FnOnce(Self::Bool) -> Self::Bool) -> Self::Bool;
28    fn build_not(&self, arg: Self::Bool) -> Self::Bool;
29    fn build_and(&self, args: &[Self::Bool]) -> Self::Bool;
30    fn build_or(&self, args: &[Self::Bool]) -> Self::Bool;
31    fn build_xor(&self, args: &[Self::Bool]) -> Self::Bool;
32
33    fn build_bitvec_lit(&self, value: &ConstSlice) -> Self::BitVec;
34    fn build_bitvec_eq(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::Bool;
35    fn build_bitvec_ite(&self, cond: Self::Bool, if_true: Self::BitVec, if_false: Self::BitVec) -> Self::BitVec;
36    fn build_bitvec_let(
37        &self,
38        var: &str,
39        expr: Self::BitVec,
40        body: impl FnOnce(Self::BitVec) -> Self::BitVec,
41    ) -> Self::BitVec;
42    fn build_concat(&self, arg_msb: Self::BitVec, arg_lsb: Self::BitVec) -> Self::BitVec;
43    fn build_extract(&self, index_msb: usize, index_lsb: usize, arg: Self::BitVec) -> Self::BitVec;
44    fn build_bvnot(&self, arg1: Self::BitVec) -> Self::BitVec;
45    fn build_bvand(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
46    fn build_bvor(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
47    fn build_bvxor(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
48    fn build_bvadd(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
49    fn build_bvcomp(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
50    fn build_bvult(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::Bool;
51    fn build_bvslt(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::Bool;
52    fn build_bvshl(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
53    fn build_bvlshr(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
54    fn build_bvashr(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
55    fn build_bvmul(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
56    fn build_bvudiv(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
57    fn build_bvurem(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
58    fn build_bvsdiv(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
59    fn build_bvsrem(&self, arg1: Self::BitVec, arg2: Self::BitVec) -> Self::BitVec;
60
61    type Error;
62
63    fn declare_bool_const(&self, name: &str) -> Result<Self::Bool, Self::Error>;
64    fn declare_bitvec_const(&self, name: &str, width: usize) -> Result<Self::BitVec, Self::Error>;
65    fn assert(&mut self, term: Self::Bool) -> Result<(), Self::Error>;
66
67    fn check(&mut self) -> Result<SmtResponse, Self::Error>;
68    fn get_bool(&self, term: &Self::Bool) -> Result<bool, Self::Error>;
69    fn get_bitvec(&self, term: &Self::BitVec) -> Result<Const, Self::Error>;
70}
71
72impl<SMT: SmtEngine> Clone for SmtTritVec<SMT> {
73    fn clone(&self) -> Self {
74        Self { x: self.x.clone(), y: self.y.clone() }
75    }
76}
77
78pub struct SmtBuilder<'a, SMT: SmtEngine> {
79    design: &'a Design,
80    engine: SMT,
81    temp: usize,
82    curr: RefCell<BTreeMap<ValueBit, SmtTritVec<SMT>>>,
83    past: RefCell<BTreeMap<ValueBit, SmtTritVec<SMT>>>,
84    eqs: RefCell<Vec<SMT::Bool>>,
85}
86
87impl<'a, SMT: SmtEngine> SmtBuilder<'a, SMT> {
88    pub fn new(design: &'a Design, engine: SMT) -> Self {
89        Self {
90            design,
91            engine,
92            temp: 0,
93            curr: RefCell::new(BTreeMap::new()),
94            past: RefCell::new(BTreeMap::new()),
95            eqs: RefCell::new(Vec::new()),
96        }
97    }
98
99    fn bv_lit<'b>(&self, value: impl Into<Cow<'b, ConstSlice>>) -> SMT::BitVec {
100        self.engine.build_bitvec_lit(&value.into())
101    }
102
103    fn bv_const(&self, prefix: &str, index: usize, suffix: &str, width: usize) -> Result<SMT::BitVec, SMT::Error> {
104        self.engine.declare_bitvec_const(&format!("{prefix}{index}{suffix}"), width)
105    }
106
107    fn bv_bind(&mut self, bv_value: SMT::BitVec, width: usize) -> Result<SMT::BitVec, SMT::Error> {
108        let bv_temp = self.engine.declare_bitvec_const(&format!("t{}", self.temp), width)?;
109        self.temp += 1;
110        self.engine.assert(self.engine.build_bitvec_eq(bv_temp.clone(), bv_value))?;
111        Ok(bv_temp)
112    }
113
114    fn bv_concat(&self, elems: impl IntoIterator<IntoIter: DoubleEndedIterator<Item = SMT::BitVec>>) -> SMT::BitVec {
115        let mut bv_result = None;
116        for elem in elems.into_iter().rev() {
117            bv_result = Some(match bv_result {
118                Some(bv_msb) => self.engine.build_concat(bv_msb, elem),
119                None => elem,
120            })
121        }
122        bv_result.expect("SMT bit vectors cannot be empty")
123    }
124
125    fn bv_is_zero(&self, bv_value: SMT::BitVec, width: usize) -> SMT::Bool {
126        self.engine.build_bitvec_eq(bv_value, self.bv_lit(Const::zero(width)))
127    }
128
129    fn bv_to_bool(&self, bv_value: SMT::BitVec) -> SMT::Bool {
130        self.engine.build_bitvec_eq(bv_value, self.bv_lit(ConstBit::One))
131    }
132
133    fn bool_to_bv(&self, bool_value: SMT::Bool) -> SMT::BitVec {
134        self.engine.build_bitvec_ite(bool_value, self.bv_lit(ConstBit::One), self.bv_lit(ConstBit::Zero))
135    }
136
137    fn tv_lit<'b>(&self, value: impl Into<Cow<'b, ConstSlice>>) -> SmtTritVec<SMT> {
138        let value = value.into();
139        let is_undef =
140            Const::from_iter(value.iter().map(|t| if t == ConstBit::Undef { ConstBit::One } else { ConstBit::Zero }));
141        let is_one =
142            Const::from_iter(value.iter().map(|t| if t == ConstBit::One { ConstBit::One } else { ConstBit::Zero }));
143        SmtTritVec { x: self.bv_lit(is_undef), y: self.bv_lit(is_one) }
144    }
145
146    fn tv_const(&self, prefix: &str, index: usize, width: usize) -> Result<SmtTritVec<SMT>, SMT::Error> {
147        Ok(SmtTritVec { x: self.bv_const(prefix, index, "x", width)?, y: self.bv_const(prefix, index, "y", width)? })
148    }
149
150    fn tv_bind(&mut self, tv_value: SmtTritVec<SMT>, width: usize) -> Result<SmtTritVec<SMT>, SMT::Error> {
151        let bv_temp_x = self.engine.declare_bitvec_const(&format!("t{}x", self.temp), width)?;
152        let bv_temp_y = self.engine.declare_bitvec_const(&format!("t{}y", self.temp), width)?;
153        self.temp += 1;
154        self.engine.assert(self.engine.build_bitvec_eq(bv_temp_x.clone(), tv_value.x))?;
155        self.engine.assert(self.engine.build_bitvec_eq(bv_temp_y.clone(), tv_value.y))?;
156        Ok(SmtTritVec { x: bv_temp_x, y: bv_temp_y })
157    }
158
159    fn tv_concat<I>(&self, elems: I) -> SmtTritVec<SMT>
160    where
161        I: IntoIterator<IntoIter: DoubleEndedIterator<Item = SmtTritVec<SMT>>>,
162    {
163        let mut bv_result = None;
164        for elem in elems.into_iter().rev() {
165            bv_result = Some(match bv_result {
166                Some((bv_x_msb, bv_y_msb)) => {
167                    (self.engine.build_concat(bv_x_msb, elem.x), self.engine.build_concat(bv_y_msb, elem.y))
168                }
169                None => (elem.x, elem.y),
170            })
171        }
172        bv_result.map(|(x, y)| SmtTritVec { x, y }).expect("SMT bit vectors cannot be empty")
173    }
174
175    fn tv_extract(&self, index_msb: usize, index_lsb: usize, tv: SmtTritVec<SMT>) -> SmtTritVec<SMT> {
176        SmtTritVec {
177            x: self.engine.build_extract(index_msb, index_lsb, tv.x),
178            y: self.engine.build_extract(index_msb, index_lsb, tv.y),
179        }
180    }
181
182    fn tv_is0(&self, tv: SmtTritVec<SMT>) -> SMT::BitVec {
183        self.engine.build_bvand(self.engine.build_bvnot(tv.y), self.engine.build_bvnot(tv.x))
184    }
185
186    fn tv_is1(&self, tv: SmtTritVec<SMT>) -> SMT::BitVec {
187        self.engine.build_bvand(tv.y, self.engine.build_bvnot(tv.x))
188    }
189
190    fn tv_eq(&self, tv_a: SmtTritVec<SMT>, tv_b: SmtTritVec<SMT>) -> SMT::Bool {
191        let x_eq = self.engine.build_bitvec_eq(tv_a.x, tv_b.x);
192        let y_eq = self.engine.build_bitvec_eq(tv_a.y, tv_b.y);
193        self.engine.build_and(&[x_eq, y_eq])
194    }
195
196    fn tv_refines(&self, from: SmtTritVec<SMT>, to: SmtTritVec<SMT>) -> SMT::Bool {
197        let from_def = self.engine.build_bvnot(from.x.clone());
198        let x_refine = self.engine.build_bitvec_eq(
199            to.x.clone(),                          // if a bit is X in `to`...
200            self.engine.build_bvand(to.x, from.x), // ... it should be X in `from`.
201        );
202        let y_refine = self.engine.build_bitvec_eq(
203            self.engine.build_bvand(from_def.clone(), from.y), // if a bit was 0/1 in `from`...
204            self.engine.build_bvand(from_def.clone(), to.y),   // ... it should be that same value in `to`.
205        );
206        self.engine.build_and(&[x_refine, y_refine])
207    }
208
209    fn tv_not(&self, tv_a: SmtTritVec<SMT>) -> SmtTritVec<SMT> {
210        SmtTritVec { y: self.engine.build_bvnot(tv_a.y), x: tv_a.x }
211    }
212
213    fn tv_and(
214        &mut self,
215        tv_a: SmtTritVec<SMT>,
216        tv_b: SmtTritVec<SMT>,
217        width: usize,
218    ) -> Result<SmtTritVec<SMT>, SMT::Error> {
219        //   0 1 X
220        // 0 0 0 0
221        // 1 0 1 X
222        // X 0 X X
223        let (tv_a, tv_b) = (self.tv_bind(tv_a, width)?, self.tv_bind(tv_b, width)?);
224        let bv_arg1_is0 = self.tv_is0(tv_a.clone());
225        let bv_arg2_is0 = self.tv_is0(tv_b.clone());
226        Ok(SmtTritVec {
227            y: self.engine.build_bvand(tv_a.y, tv_b.y),
228            x: self.engine.build_bvand(
229                self.engine.build_bvor(tv_a.x, tv_b.x),
230                self.engine.build_bvnot(self.engine.build_bvor(bv_arg1_is0, bv_arg2_is0)),
231            ),
232        })
233    }
234
235    fn tv_or(
236        &mut self,
237        tv_a: SmtTritVec<SMT>,
238        tv_b: SmtTritVec<SMT>,
239        width: usize,
240    ) -> Result<SmtTritVec<SMT>, SMT::Error> {
241        //   0 1 X
242        // 0 0 1 X
243        // 1 1 1 1
244        // X X 1 1
245        let (tv_a, tv_b) = (self.tv_bind(tv_a, width)?, self.tv_bind(tv_b, width)?);
246        let bv_arg1_is1 = self.tv_is1(tv_a.clone());
247        let bv_arg2_is1 = self.tv_is1(tv_b.clone());
248        Ok(SmtTritVec {
249            y: self.engine.build_bvor(tv_a.y, tv_b.y),
250            x: self.engine.build_bvand(
251                self.engine.build_bvor(tv_a.x, tv_b.x),
252                self.engine.build_bvnot(self.engine.build_bvor(bv_arg1_is1, bv_arg2_is1)),
253            ),
254        })
255    }
256
257    fn tv_xor(&self, tv_a: SmtTritVec<SMT>, tv_b: SmtTritVec<SMT>) -> SmtTritVec<SMT> {
258        //   0 1 X
259        // 0 0 1 X
260        // 1 1 0 X
261        // X X X X
262        SmtTritVec { y: self.engine.build_bvxor(tv_a.y, tv_b.y), x: self.engine.build_bvor(tv_a.x, tv_b.x) }
263    }
264
265    fn tv_mux(
266        &mut self,
267        tv_s: SmtTritVec<SMT>,
268        tv_vals: [SmtTritVec<SMT>; 2],
269        width: usize,
270    ) -> Result<SmtTritVec<SMT>, SMT::Error> {
271        let [tv_v0, tv_v1] = tv_vals;
272        // S V0 V1 O    S V1 V0 O    S V1 V0 O
273        // 0 0  ?  0    1 ?  0  0    X 0  0  0
274        // 0 1  ?  1    1 ?  1  1    X 1  1  1
275        // 0 X  ?  X    1 ?  X  X    X ?  ?  X
276        let (tv_s, tv_v0, tv_v1) = (self.tv_bind(tv_s, 1)?, self.tv_bind(tv_v0, width)?, self.tv_bind(tv_v1, width)?);
277        let (bv_s_is0, bv_s_is1) = (self.tv_is0(tv_s.clone()), self.tv_is1(tv_s));
278        let (bool_s_is0, bool_s_is1) = (self.bv_to_bool(bv_s_is0), self.bv_to_bool(bv_s_is1));
279        let bv_x_sx = self.engine.build_bvxor(tv_v1.y.clone(), tv_v0.y.clone());
280        let bv_x_sx = self.engine.build_bvor(bv_x_sx, tv_v1.x.clone());
281        let bv_x_sx = self.engine.build_bvor(bv_x_sx, tv_v0.x.clone());
282        let bv_x_s1 = self.engine.build_bitvec_ite(bool_s_is1.clone(), tv_v1.x, bv_x_sx);
283        let bv_x_s0 = self.engine.build_bitvec_ite(bool_s_is0.clone(), tv_v0.x, bv_x_s1);
284        let bv_y_sx = self.engine.build_bvand(tv_v1.y.clone(), tv_v0.y.clone());
285        let bv_y_s1 = self.engine.build_bitvec_ite(bool_s_is1, tv_v1.y, bv_y_sx);
286        let bv_y_s0 = self.engine.build_bitvec_ite(bool_s_is0, tv_v0.y, bv_y_s1);
287        Ok(SmtTritVec { y: bv_y_s0, x: bv_x_s0 })
288    }
289
290    fn curr_net(&self, net: ValueBit) -> Result<SmtTritVec<SMT>, SMT::Error> {
291        if let Some(trit) = net.as_const() {
292            Ok(self.tv_lit(trit))
293        } else {
294            let cell_index = net.as_cell_index();
295            let tv_net = self.tv_const("n", cell_index, 1)?;
296            self.curr.borrow_mut().insert(net, tv_net.clone());
297            Ok(tv_net)
298        }
299    }
300
301    fn curr_value(&self, value: &Value) -> Result<SmtTritVec<SMT>, SMT::Error> {
302        Ok(self.tv_concat(value.iter().map(|net| self.curr_net(net)).collect::<Result<Vec<_>, _>>()?))
303    }
304
305    fn past_net(&self, net: ValueBit) -> Result<SmtTritVec<SMT>, SMT::Error> {
306        if let Some(trit) = net.as_const() {
307            Ok(self.tv_lit(trit))
308        } else {
309            let cell_index = net.as_cell_index();
310            let tv_net = self.tv_const("p", cell_index, 1)?;
311            self.curr.borrow_mut().insert(net, tv_net.clone());
312            Ok(tv_net)
313        }
314    }
315
316    fn past_value(&self, value: &Value) -> Result<SmtTritVec<SMT>, SMT::Error> {
317        Ok(self.tv_concat(value.iter().map(|net| self.past_net(net)).collect::<Result<Vec<_>, _>>()?))
318    }
319
320    fn net(&self, net: ValueBit) -> Result<SmtTritVec<SMT>, SMT::Error> {
321        let index = net.as_cell_index();
322        if !self.design.is_valid_cell_index(index) {
323            return self.curr_net(net); // FIXME: is this even sound?
324        }
325        let (cell_id, _offset) = self.design.find_cell(net);
326        if matches!(&*self.design.cell(cell_id), Cell::Dff(_)) { self.past_net(net) } else { self.curr_net(net) }
327    }
328
329    fn value(&self, value: &Value) -> Result<SmtTritVec<SMT>, SMT::Error> {
330        Ok(self.tv_concat(value.iter().map(|net| self.net(net)).collect::<Result<Vec<_>, _>>()?))
331    }
332
333    fn invert_net(&self, control_net: ControlNet, tv_net: SmtTritVec<SMT>) -> Result<SmtTritVec<SMT>, SMT::Error> {
334        let active = if control_net.is_positive() { Const::ones(1) } else { Const::zero(1) };
335        Ok(SmtTritVec { y: self.engine.build_bvcomp(tv_net.y, self.engine.build_bitvec_lit(&active)), x: tv_net.x })
336    }
337
338    fn control_net(&self, control_net: ControlNet) -> Result<SmtTritVec<SMT>, SMT::Error> {
339        self.invert_net(control_net, self.net(control_net.net())?)
340    }
341
342    fn clock_net(&mut self, control_net: ControlNet) -> Result<SmtTritVec<SMT>, SMT::Error> {
343        self.tv_and(
344            self.invert_net(control_net, self.curr_net(control_net.net())?)?,
345            self.tv_not(self.invert_net(control_net, self.past_net(control_net.net())?)?),
346            1,
347        )
348    }
349
350    fn cell(&mut self, output: &Value, cell: &Cell) -> Result<SmtTritVec<SMT>, SMT::Error> {
351        let prepare_shift = |value: &Value, amount: &Value, stride: u32, signed: bool| -> Result<_, SMT::Error> {
352            let width = value.len().max(amount.len() + stride.max(1).ilog2() as usize + 1);
353            let value_ext = if signed { value.sext(width) } else { value.zext(width) };
354            let amount_ext = amount.zext(width);
355            let (tv_value_ext, tv_amount_ext) = (self.value(&value_ext)?, self.value(&amount_ext)?);
356            let bv_stride = self.engine.build_bitvec_lit(&Const::from_uint(stride as u128, width));
357            let bv_amount_mul = self.engine.build_bvmul(tv_amount_ext.y.clone(), bv_stride);
358            Ok((width, tv_value_ext, tv_amount_ext, bv_amount_mul))
359        };
360
361        let bv_cell = match &cell {
362            Cell::Const(a) => self.tv_lit(*a),
363            Cell::Buf(a) => self.value(a)?,
364            Cell::Not(a) => self.tv_not(self.value(a)?),
365            Cell::And(a, b) => self.tv_and(self.value(a)?, self.value(b)?, output.len())?,
366            Cell::Or(a, b) => self.tv_or(self.value(a)?, self.value(b)?, output.len())?,
367            Cell::Xor(a, b) => self.tv_xor(self.value(a)?, self.value(b)?),
368            Cell::Mux(s, [v0, v1]) => self.tv_mux(self.net(*s)?, [self.value(v0)?, self.value(v1)?], output.len())?,
369            Cell::Adc(a, b, c) => {
370                if a.is_empty() {
371                    self.net(*c)?
372                } else {
373                    let (tv_a, tv_b, tv_c) = (self.value(a)?, self.value(b)?, self.net(*c)?);
374                    let (tv_a, tv_b) = (self.tv_bind(tv_a, a.len())?, self.tv_bind(tv_b, b.len())?);
375                    let mut bv_x = vec![];
376                    let mut bv_carry_x = tv_c.x;
377                    for index in 0..a.len() {
378                        bv_carry_x = self.bv_bind(
379                            self.engine.build_bvor(
380                                bv_carry_x,
381                                self.engine.build_bvor(
382                                    self.engine.build_extract(index, index, tv_a.x.clone()),
383                                    self.engine.build_extract(index, index, tv_b.x.clone()),
384                                ),
385                            ),
386                            1,
387                        )?;
388                        bv_x.push(bv_carry_x.clone());
389                    }
390                    bv_x.push(bv_carry_x.clone());
391                    SmtTritVec {
392                        x: self.bv_concat(bv_x),
393                        y: self.engine.build_bvadd(
394                            self.engine.build_bvadd(
395                                self.engine.build_concat(self.bv_lit(ConstBit::Zero), tv_a.y),
396                                self.engine.build_concat(self.bv_lit(ConstBit::Zero), tv_b.y),
397                            ),
398                            self.engine.build_concat(self.bv_lit(Const::zero(a.len())), tv_c.y),
399                        ),
400                    }
401                }
402            }
403            Cell::Aig(a, b) => self.tv_and(self.control_net(*a)?, self.control_net(*b)?, 1)?,
404            Cell::Eq(a, b) => {
405                let (tv_a, tv_b) = (self.value(a)?, self.value(b)?);
406                let bv_a_xor_b = self.engine.build_bvxor(tv_a.y.clone(), tv_b.y.clone());
407                let bv_unequal = self.engine.build_bvand(
408                    bv_a_xor_b,
409                    self.engine.build_bvnot(self.engine.build_bvor(tv_a.x.clone(), tv_b.x.clone())),
410                );
411                let bool_any_unequal = self.engine.build_not(self.bv_is_zero(bv_unequal, a.len()));
412                SmtTritVec {
413                    x: self.bool_to_bv(self.engine.build_bool_ite(
414                        bool_any_unequal,
415                        self.engine.build_bool_lit(false),
416                        self.engine.build_not(self.engine.build_and(&[
417                            self.bv_is_zero(tv_a.x.clone(), a.len()),
418                            self.bv_is_zero(tv_b.x.clone(), b.len()),
419                        ])),
420                    )),
421                    y: self.engine.build_bvcomp(tv_a.y, tv_b.y),
422                }
423            }
424            Cell::ULt(a, b) => {
425                let (tv_a, tv_b) = (self.value(a)?, self.value(b)?);
426                SmtTritVec {
427                    x: self.bool_to_bv(self.engine.build_not(
428                        self.engine.build_and(&[self.bv_is_zero(tv_a.x, a.len()), self.bv_is_zero(tv_b.x, b.len())]),
429                    )),
430                    y: self.bool_to_bv(self.engine.build_bvult(tv_a.y, tv_b.y)),
431                }
432            }
433            Cell::SLt(a, b) => {
434                let (tv_a, tv_b) = (self.value(a)?, self.value(b)?);
435                SmtTritVec {
436                    x: self.bool_to_bv(self.engine.build_not(
437                        self.engine.build_and(&[self.bv_is_zero(tv_a.x, a.len()), self.bv_is_zero(tv_b.x, b.len())]),
438                    )),
439                    y: self.bool_to_bv(self.engine.build_bvslt(tv_a.y, tv_b.y)),
440                }
441            }
442            Cell::Shl(value, amount, stride) => {
443                let (width, tv_value_ext, tv_amount_ext, bv_amount_mul) = prepare_shift(value, amount, *stride, false)?;
444                let tv_result = SmtTritVec {
445                    x: self.engine.build_bitvec_ite(
446                        self.bv_is_zero(tv_amount_ext.x, width),
447                        self.engine.build_bvshl(tv_value_ext.x, bv_amount_mul.clone()),
448                        self.engine.build_bitvec_lit(&Const::ones(width)),
449                    ),
450                    y: self.engine.build_bvshl(tv_value_ext.y, bv_amount_mul),
451                };
452                self.tv_extract(value.len() - 1, 0, tv_result)
453            }
454            Cell::UShr(value, amount, stride) => {
455                let (width, tv_value_ext, tv_amount_ext, bv_amount_mul) = prepare_shift(value, amount, *stride, false)?;
456                let tv_result = SmtTritVec {
457                    x: self.engine.build_bitvec_ite(
458                        self.bv_is_zero(tv_amount_ext.x, width),
459                        self.engine.build_bvlshr(tv_value_ext.x, bv_amount_mul.clone()),
460                        self.engine.build_bitvec_lit(&Const::ones(width)),
461                    ),
462                    y: self.engine.build_bvlshr(tv_value_ext.y, bv_amount_mul),
463                };
464                self.tv_extract(value.len() - 1, 0, tv_result)
465            }
466            Cell::SShr(value, amount, stride) => {
467                let (width, tv_value_ext, tv_amount_ext, bv_amount_mul) = prepare_shift(value, amount, *stride, true)?;
468                let tv_result = SmtTritVec {
469                    x: self.engine.build_bitvec_ite(
470                        self.bv_is_zero(tv_amount_ext.x, width),
471                        self.engine.build_bvashr(tv_value_ext.x, bv_amount_mul.clone()),
472                        self.engine.build_bitvec_lit(&Const::ones(width)),
473                    ),
474                    y: self.engine.build_bvashr(tv_value_ext.y, bv_amount_mul),
475                };
476                self.tv_extract(value.len() - 1, 0, tv_result)
477            }
478            Cell::XShr(value, amount, stride) => {
479                let (width, tv_value_ext, tv_amount_ext, bv_amount_mul) =
480                    prepare_shift(&value.concat(Value::undef(1)), amount, *stride, true)?;
481                let tv_result = SmtTritVec {
482                    x: self.engine.build_bitvec_ite(
483                        self.bv_is_zero(tv_amount_ext.x, width),
484                        self.engine.build_bvashr(tv_value_ext.x, bv_amount_mul.clone()),
485                        self.engine.build_bitvec_lit(&Const::ones(width)),
486                    ),
487                    y: self.engine.build_bvlshr(tv_value_ext.y, bv_amount_mul),
488                };
489                self.tv_extract(value.len() - 1, 0, tv_result)
490            }
491            Cell::Mul(a, b) => {
492                let (tv_a, tv_b) = (self.value(a)?, self.value(b)?);
493                SmtTritVec {
494                    x: self.engine.build_bitvec_ite(
495                        self.engine.build_and(&[self.bv_is_zero(tv_a.x, a.len()), self.bv_is_zero(tv_b.x, b.len())]),
496                        self.engine.build_bitvec_lit(&Const::zero(a.len())),
497                        self.engine.build_bitvec_lit(&Const::ones(a.len())),
498                    ),
499                    y: self.engine.build_bvmul(tv_a.y, tv_b.y),
500                }
501            }
502            Cell::UDiv(..) => unimplemented!("lowering of udiv to SMT-LIB is not implemented"),
503            Cell::UMod(..) => unimplemented!("lowering of umod to SMT-LIB is not implemented"),
504            Cell::SDivTrunc(..) => unimplemented!("lowering of sdiv_trunc to SMT-LIB is not implemented"),
505            Cell::SDivFloor(..) => unimplemented!("lowering of sdiv_floor to SMT-LIB is not implemented"),
506            Cell::SModTrunc(..) => unimplemented!("lowering of smod_trunc to SMT-LIB is not implemented"),
507            Cell::SModFloor(..) => unimplemented!("lowering of smod_floor to SMT-LIB is not implemented"),
508            Cell::Match(MatchCell { value, enable, patterns }) => {
509                let mut tv_matches = vec![];
510                for alternates in patterns {
511                    let mut tv_sum = self.tv_lit(ConstBit::Zero);
512                    for pattern in alternates {
513                        let mut tv_prd = self.tv_lit(ConstBit::One);
514                        for (index, mask) in
515                            pattern.iter().enumerate().filter(|(_index, mask)| *mask != ConstBit::Undef)
516                        {
517                            let tv_eq = self.tv_not(self.tv_xor(self.net(value[index])?, self.net(mask.into())?));
518                            tv_prd = self.tv_and(tv_prd, tv_eq, 1)?;
519                        }
520                        tv_sum = self.tv_or(tv_sum, tv_prd, 1)?;
521                    }
522                    tv_matches.push(tv_sum);
523                }
524                let tv_matches = self.tv_bind(self.tv_concat(tv_matches), patterns.len())?;
525                let tv_enable = self.net(*enable)?;
526                let tv_all_cold = self.tv_lit(Const::zero(patterns.len()));
527                let mut tv_result = tv_all_cold.clone();
528                for index in (0..patterns.len()).rev() {
529                    tv_result = self.tv_mux(
530                        self.tv_extract(index, index, tv_matches.clone()),
531                        [tv_result, self.tv_lit(Const::one_hot(patterns.len(), index))],
532                        patterns.len(),
533                    )?;
534                }
535                self.tv_mux(tv_enable.clone(), [tv_all_cold, tv_result], patterns.len())?
536            }
537            Cell::Assign(AssignCell { value, enable, update, offset }) => self.tv_mux(
538                self.net(*enable)?,
539                [
540                    self.value(value)?,
541                    self.value(&{
542                        let mut nets = Value::from_iter(value.iter());
543                        nets[*offset..(*offset + update.len())].copy_from_slice(&update[..]);
544                        nets
545                    })?,
546                ],
547                output.len(),
548            )?,
549            Cell::Dff(flip_flop) => {
550                let mut data = self.value(&flip_flop.data)?;
551                let clear = self.control_net(flip_flop.clear)?;
552                let load = self.control_net(flip_flop.load)?;
553                let load_data = self.value(&flip_flop.load_data)?;
554                let reset = self.control_net(flip_flop.reset)?;
555                let enable = self.control_net(flip_flop.enable)?;
556                if flip_flop.reset_over_enable {
557                    data = self.tv_mux(enable, [self.past_value(output)?, data], output.len())?;
558                    data = self.tv_mux(reset, [data, self.tv_lit(&flip_flop.reset_value)], output.len())?;
559                } else {
560                    data = self.tv_mux(reset, [data, self.tv_lit(&flip_flop.reset_value)], output.len())?;
561                    data = self.tv_mux(enable, [self.past_value(output)?, data], output.len())?;
562                }
563                let active_edge = self.clock_net(flip_flop.clock)?;
564                let mut value = self.tv_mux(active_edge, [self.past_value(output)?, data], output.len())?;
565                if flip_flop.has_load() {
566                    value = self.tv_mux(load, [value, load_data], output.len())?
567                }
568                if flip_flop.has_clear() {
569                    value = self.tv_mux(clear, [value, self.tv_lit(&flip_flop.clear_value)], output.len())?
570                }
571                value
572            }
573            Cell::Memory(_memory) => unimplemented!("memories are not lowered to SMT-LIB yet"),
574            Cell::IoBuf(_io_buffer) => self.value(output)?, // i/en/o treated as POs/PIs
575            Cell::Target(_target_cell) => unimplemented!("target cells cannot be lowered to SMT-LIB yet"),
576            Cell::Other(_) => unreachable!("instances cannot be lowered to SMT-LIB"),
577            Cell::Input(..) | Cell::Output(..) | Cell::Name(..) | Cell::Debug(..) => unreachable!(),
578        };
579
580        Ok(bv_cell)
581    }
582
583    pub fn add_cell(&mut self, output: &Value, cell: &Cell) -> Result<(), SMT::Error> {
584        // Declare the nets used by the cell so that it is present in the counterexample even if unused.
585        if let Cell::Input(..) = cell {
586            self.curr_value(output)?;
587            return Ok(());
588        }
589        let tv_cell = self.cell(output, cell)?;
590        self.engine.assert(self.tv_eq(self.curr_value(output)?, tv_cell))
591    }
592
593    pub fn replace_cell(&mut self, output: &Value, old_cell: &Cell, new_cell: &Cell) -> Result<(), SMT::Error> {
594        self.add_cell(output, old_cell)?;
595        let tv_new_cell = self.cell(output, new_cell)?;
596        self.eqs.borrow_mut().push(self.tv_refines(self.curr_value(output)?, tv_new_cell));
597        Ok(())
598    }
599
600    pub fn replace_net(&mut self, from_net: ValueBit, to_net: ValueBit) -> Result<(), SMT::Error> {
601        self.eqs.borrow_mut().push(self.tv_refines(self.curr_net(from_net)?, self.net(to_net)?));
602        Ok(())
603    }
604
605    pub fn replace_void_net(&mut self, from_net: ValueBit, to_net: ValueBit) -> Result<(), SMT::Error> {
606        self.engine.assert(self.tv_eq(self.curr_net(from_net)?, self.net(to_net)?))
607    }
608
609    pub fn replace_dff_net(&mut self, from_net: ValueBit, to_net: ValueBit) -> Result<(), SMT::Error> {
610        // Essentially a single induction step.
611        self.engine.assert(self.tv_eq(self.past_net(from_net)?, self.past_net(to_net)?))?;
612        self.eqs.borrow_mut().push(self.tv_refines(self.curr_net(from_net)?, self.curr_net(to_net)?));
613        Ok(())
614    }
615
616    pub fn check(&mut self) -> Result<Option<SmtExample>, SMT::Error> {
617        if self.eqs.borrow().is_empty() {
618            return Ok(None);
619        }
620        let not_and_eqs = self.engine.build_not(self.engine.build_and(&self.eqs.borrow()[..]));
621        self.engine.assert(not_and_eqs)?;
622        match self.engine.check()? {
623            SmtResponse::Unknown => panic!("SMT solver returned unknown"),
624            SmtResponse::Unsat => Ok(None),
625            SmtResponse::Sat => {
626                let get_trit = |tv_net: &SmtTritVec<SMT>| -> Result<ConstBit, SMT::Error> {
627                    if self.engine.get_bitvec(&tv_net.x)?[0] == ConstBit::One {
628                        Ok(ConstBit::Undef)
629                    } else {
630                        Ok(self.engine.get_bitvec(&tv_net.y)?[0])
631                    }
632                };
633                let (mut curr, mut past) = (BTreeMap::new(), BTreeMap::new());
634                for (net, tv_net) in self.curr.borrow().iter() {
635                    curr.insert(*net, get_trit(tv_net)?);
636                }
637                for (net, tv_net) in self.past.borrow().iter() {
638                    past.insert(*net, get_trit(tv_net)?);
639                }
640                Ok(Some(SmtExample { curr, past }))
641            }
642        }
643    }
644}
645
646#[derive(Debug, Clone, PartialEq, Eq)]
647pub struct SmtExample {
648    curr: BTreeMap<ValueBit, ConstBit>,
649    past: BTreeMap<ValueBit, ConstBit>,
650}
651
652impl SmtExample {
653    pub fn get_net(&self, net: ValueBit) -> Option<ConstBit> {
654        self.curr.get(&net).cloned()
655    }
656
657    pub fn get_value(&self, value: impl AsRef<ValueSlice>) -> Option<Const> {
658        let mut result = Const::new();
659        for net in value.as_ref() {
660            result.push(self.get_net(net)?);
661        }
662        Some(result)
663    }
664
665    pub fn get_past_net(&self, net: ValueBit) -> Option<ConstBit> {
666        self.past.get(&net).cloned()
667    }
668
669    pub fn get_past_value(&self, value: impl AsRef<ValueSlice>) -> Option<Const> {
670        let mut result = Const::new();
671        for net in value.as_ref() {
672            result.push(self.get_past_net(net)?);
673        }
674        Some(result)
675    }
676}