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, y: SMT::BitVec, }
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(), self.engine.build_bvand(to.x, from.x), );
202 let y_refine = self.engine.build_bitvec_eq(
203 self.engine.build_bvand(from_def.clone(), from.y), self.engine.build_bvand(from_def.clone(), to.y), );
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 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 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 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 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); }
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)?, 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 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 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}