prjunnamed_netlist/
design.rs

1use std::fmt::Display;
2use std::ops::{Deref, Range};
3use std::cell::{Ref, RefCell};
4use std::borrow::Cow;
5use std::hash::Hash;
6use std::collections::{btree_map, BTreeMap, BTreeSet, HashMap};
7use std::rc::Rc;
8use std::sync::Arc;
9
10use crate::{MetaItem, MetaStringRef, MetaItemRef};
11use crate::{
12    cell::CellRepr, AssignCell, Cell, ControlNet, FlipFlop, Instance, IoBuffer, IoNet, IoValue, MatchCell, Memory, Net,
13    Target, TargetCell, TargetCellPurity, TargetPrototype, Trit, Value,
14};
15use crate::metadata::{MetadataStore, MetaStringIndex, MetaItemIndex};
16use crate::smt::{SmtEngine, SmtBuilder};
17
18/// Sea of [`Cell`]s.
19#[derive(Debug, Clone)]
20pub struct Design {
21    ios: BTreeMap<String, Range<u32>>,
22    cells: Vec<AnnotatedCell>,
23    changes: RefCell<ChangeQueue>,
24    metadata: RefCell<MetadataStore>,
25    target: Option<Arc<dyn Target>>,
26}
27
28#[derive(Debug, Clone, Default)]
29struct ChangeQueue {
30    next_io: u32,
31    added_ios: BTreeMap<String, Range<u32>>,
32    added_cells: Vec<AnnotatedCell>,
33    cell_cache: HashMap<AnnotatedCell, Value>,
34    cell_metadata: MetaItemIndex,
35    appended_metadata: BTreeMap<usize, Vec<MetaItemIndex>>,
36    replaced_cells: BTreeMap<usize, AnnotatedCell>,
37    unalived_cells: BTreeSet<usize>,
38    replaced_nets: BTreeMap<Net, Net>,
39}
40
41impl Design {
42    pub fn new() -> Design {
43        Self::with_target(None)
44    }
45
46    pub fn with_target(target: Option<Arc<dyn Target>>) -> Design {
47        Design {
48            ios: BTreeMap::new(),
49            cells: vec![],
50            changes: RefCell::new(ChangeQueue::default()),
51            metadata: RefCell::new(MetadataStore::new()),
52            target,
53        }
54    }
55
56    pub fn add_io(&self, name: impl Into<String>, width: usize) -> IoValue {
57        let mut changes = self.changes.borrow_mut();
58        let name = name.into();
59        let width = width as u32;
60        let range = changes.next_io..(changes.next_io + width);
61        changes.next_io += width;
62        if self.ios.contains_key(&name) {
63            panic!("duplicate IO port {name}");
64        }
65        match changes.added_ios.entry(name) {
66            btree_map::Entry::Occupied(entry) => {
67                panic!("duplicate IO port {}", entry.key());
68            }
69            btree_map::Entry::Vacant(entry) => {
70                entry.insert(range.clone());
71            }
72        }
73        IoValue::from_range(range)
74    }
75
76    pub fn get_io(&self, name: impl AsRef<str>) -> Option<IoValue> {
77        self.ios.get(name.as_ref()).map(|range| IoValue::from_range(range.clone()))
78    }
79
80    pub fn find_io(&self, io_net: IoNet) -> Option<(&str, usize)> {
81        for (name, range) in self.ios.iter() {
82            if range.contains(&io_net.index) {
83                return Some((name.as_str(), (io_net.index - range.start) as usize));
84            }
85        }
86        None
87    }
88
89    pub fn iter_ios(&self) -> impl Iterator<Item = (&str, IoValue)> {
90        self.ios.iter().map(|(name, range)| (name.as_str(), IoValue::from_range(range.clone())))
91    }
92
93    pub(crate) fn add_cell_with_metadata_index(&self, cell: Cell, metadata: MetaItemIndex) -> Value {
94        cell.validate(self);
95        let cell_with_meta = AnnotatedCell { repr: cell.clone().into(), meta: metadata };
96        let mut changes = self.changes.borrow_mut();
97        if let Some(value) = changes.cell_cache.get(&cell_with_meta) {
98            value.clone()
99        } else {
100            let index = self.cells.len() + changes.added_cells.len();
101            let output_len = cell.output_len();
102            let output = Value::from_cell_range(index, output_len);
103            if !cell.has_effects(self) {
104                changes.cell_cache.insert(cell_with_meta.clone(), output.clone());
105            }
106            changes.added_cells.push(cell_with_meta);
107            for _ in 0..output_len.checked_sub(1).unwrap_or(0) {
108                changes.added_cells.push(CellRepr::Skip(index.try_into().expect("cell index too large")).into())
109            }
110            output
111        }
112    }
113
114    pub fn add_cell_with_metadata_ref(&self, cell: Cell, metadata: MetaItemRef) -> Value {
115        self.add_cell_with_metadata_index(cell, metadata.index())
116    }
117
118    pub fn add_cell_with_metadata(&self, cell: Cell, metadata: &MetaItem) -> Value {
119        metadata.validate();
120        let metadata = self.metadata.borrow_mut().add_item(metadata);
121        self.add_cell_with_metadata_index(cell, metadata)
122    }
123
124    pub fn use_metadata(&self, item: MetaItemRef) -> WithMetadataGuard<'_> {
125        let mut changes = self.changes.borrow_mut();
126        let guard = WithMetadataGuard { design: self, restore: changes.cell_metadata };
127        changes.cell_metadata = item.index();
128        guard
129    }
130
131    pub fn use_metadata_from(&self, cell_refs: &[CellRef]) -> WithMetadataGuard<'_> {
132        let item = MetaItemRef::from_merge(self, cell_refs.iter().map(CellRef::metadata));
133        self.use_metadata(item)
134    }
135
136    pub fn add_cell(&self, cell: Cell) -> Value {
137        let metadata = self.changes.borrow().cell_metadata;
138        self.add_cell_with_metadata_index(cell, metadata)
139    }
140
141    pub fn add_void(&self, width: usize) -> Value {
142        let mut changes = self.changes.borrow_mut();
143        let index = self.cells.len() + changes.added_cells.len();
144        for _ in 0..width {
145            changes.added_cells.push(CellRepr::Void.into());
146        }
147        Value::from_cell_range(index, width)
148    }
149
150    #[inline]
151    pub fn find_cell(&self, net: Net) -> Result<(CellRef<'_>, usize), Trit> {
152        let index = net.as_cell_index()?;
153        match self.cells[index].repr {
154            CellRepr::Void => panic!("located a void cell %{index} in design"),
155            CellRepr::Skip(start) => Ok((CellRef { design: self, index: start as usize }, index - start as usize)),
156            _ => Ok((CellRef { design: self, index }, 0)),
157        }
158    }
159
160    pub fn iter_cells(&self) -> CellIter<'_> {
161        CellIter { design: self, index: 0 }
162    }
163
164    pub(crate) fn is_valid_cell_index(&self, index: usize) -> bool {
165        index < self.cells.len()
166    }
167
168    pub(crate) fn metadata(&self) -> Ref<'_, MetadataStore> {
169        self.metadata.borrow()
170    }
171
172    pub fn add_metadata_string(&self, string: &str) -> MetaStringRef<'_> {
173        let index = self.metadata.borrow_mut().add_string(string);
174        self.metadata.borrow().ref_string(self, index)
175    }
176
177    pub(crate) fn ref_metadata_string(&self, index: MetaStringIndex) -> MetaStringRef<'_> {
178        self.metadata.borrow().ref_string(self, index)
179    }
180
181    pub fn add_metadata_item(&self, item: &MetaItem) -> MetaItemRef<'_> {
182        item.validate();
183        let index = self.metadata.borrow_mut().add_item(item);
184        self.metadata.borrow().ref_item(self, index)
185    }
186
187    pub(crate) fn ref_metadata_item(&self, index: MetaItemIndex) -> MetaItemRef<'_> {
188        self.metadata.borrow().ref_item(self, index)
189    }
190
191    pub fn replace_net(&self, from_net: impl Into<Net>, to_net: impl Into<Net>) {
192        let (from_net, to_net) = (from_net.into(), to_net.into());
193        if from_net != to_net {
194            let mut changes = self.changes.borrow_mut();
195            assert_eq!(changes.replaced_nets.insert(from_net, to_net), None);
196        }
197    }
198
199    pub fn replace_value<'a, 'b>(&self, from_value: impl Into<Cow<'a, Value>>, to_value: impl Into<Cow<'b, Value>>) {
200        let (from_value, to_value) = (from_value.into(), to_value.into());
201        assert_eq!(from_value.len(), to_value.len());
202        for (from_net, to_net) in from_value.iter().zip(to_value.iter()) {
203            self.replace_net(from_net, to_net);
204        }
205    }
206
207    pub fn map_net(&self, net: impl Into<Net>) -> Net {
208        let changes = self.changes.borrow();
209        let net = net.into();
210        let mut mapped_net = net;
211        while let Some(new_net) = changes.replaced_nets.get(&mapped_net) {
212            mapped_net = *new_net;
213        }
214        // Assume the caller might want to locate the cell behind the net.
215        match mapped_net.as_cell_index() {
216            Ok(index) if index >= self.cells.len() => net,
217            _ => mapped_net,
218        }
219    }
220
221    pub fn map_value(&self, value: impl Into<Value>) -> Value {
222        let mut value = value.into();
223        value.visit_mut(|net| *net = self.map_net(*net));
224        value
225    }
226
227    pub fn is_empty(&self) -> bool {
228        self.ios.is_empty() && self.cells.is_empty() && !self.is_changed() && self.target.is_none()
229    }
230
231    pub fn is_changed(&self) -> bool {
232        let changes = self.changes.borrow();
233        !changes.added_ios.is_empty()
234            || !changes.added_cells.is_empty()
235            || !changes.replaced_cells.is_empty()
236            || !changes.unalived_cells.is_empty()
237            || !changes.replaced_nets.is_empty()
238    }
239
240    pub fn verify<SMT: SmtEngine>(&self, engine: SMT) -> Result<(), SMT::Error> {
241        let changes = self.changes.borrow();
242        let locate_cell = |net: Net| {
243            net.as_cell_index().map(|index| {
244                if index < self.cells.len() {
245                    &self.cells[index].repr
246                } else {
247                    &changes.added_cells[index - self.cells.len()].repr
248                }
249            })
250        };
251        let get_cell = |net: Net| match locate_cell(net) {
252            Ok(CellRepr::Skip(index)) => locate_cell(Net::from_cell_index(*index as usize)),
253            result => result,
254        };
255
256        let mut smt = SmtBuilder::new(self, engine);
257        for (index, cell) in self.cells.iter().chain(changes.added_cells.iter()).enumerate() {
258            if matches!(cell.repr, CellRepr::Skip(_) | CellRepr::Void) {
259            } else if cell.output_len() == 0 {
260            } else if let Some(new_cell) = changes.replaced_cells.get(&index) {
261                smt.replace_cell(&Value::from_cell_range(index, cell.output_len()), &*cell.get(), &*new_cell.get())?;
262            } else {
263                smt.add_cell(&Value::from_cell_range(index, cell.output_len()), &*cell.get())?;
264            }
265        }
266        for (&net, &new_net) in changes.replaced_nets.iter() {
267            if let Ok(cell) = get_cell(net) {
268                if matches!(cell, CellRepr::Void) {
269                    smt.replace_void_net(net, new_net)?;
270                    continue;
271                } else if matches!(&*cell.get(), Cell::Dff(_)) {
272                    if let Ok(new_cell) = get_cell(new_net) {
273                        if matches!(&*new_cell.get(), Cell::Dff(_)) {
274                            smt.replace_dff_net(net, new_net)?;
275                        }
276                    }
277                }
278            }
279            smt.replace_net(net, new_net)?;
280        }
281        if let Some(example) = smt.check()? {
282            let mut message = format!("verification failed!\n");
283            message.push_str(&format!("\ndesign:\n{self:#}"));
284            message.push_str("\ncounterexample:\n");
285            for (index, cell) in self.cells.iter().chain(changes.added_cells.iter()).enumerate() {
286                if matches!(cell.repr, CellRepr::Skip(_) | CellRepr::Void) {
287                } else if cell.output_len() == 0 {
288                } else {
289                    let output = Value::from_cell_range(index, cell.output_len());
290                    let (was, now) = (example.get_past_value(&output), example.get_value(&output));
291                    message.push_str(&match (was, now) {
292                        (Some(was), Some(now)) => format!("{} = {} -> {}\n", self.display_value(&output), was, now),
293                        (None, Some(now)) => format!("{} = {}\n", self.display_value(&output), now),
294                        (Some(was), None) => format!("{} = {} -> ?\n", self.display_value(&output), was),
295                        (None, None) => unreachable!(),
296                    });
297                }
298            }
299            for (&net, &new_net) in changes.replaced_nets.iter() {
300                if example.get_value(net) != example.get_value(new_net) {
301                    message.push_str(&format!(
302                        "\npossible cause: replacing net {} with net {} is not valid",
303                        self.display_net(net),
304                        self.display_net(new_net)
305                    ));
306                }
307            }
308            panic!("{message}");
309        }
310        Ok(())
311    }
312
313    pub fn apply(&mut self) -> bool {
314        #[cfg(feature = "verify")]
315        self.verify(crate::EasySmtEngine::z3().unwrap()).unwrap();
316
317        let mut changes = std::mem::take(self.changes.get_mut());
318        self.changes.get_mut().next_io = changes.next_io;
319
320        let mut did_change = !changes.added_ios.is_empty() || !changes.added_cells.is_empty();
321        for (cell_index, new_items) in changes.appended_metadata {
322            let cell_meta_iter = self.ref_metadata_item(self.cells[cell_index].meta).iter();
323            let new_items_iter = new_items.into_iter().flat_map(|new_item| self.ref_metadata_item(new_item).iter());
324            self.cells[cell_index].meta = MetaItemRef::from_iter(self, cell_meta_iter.chain(new_items_iter)).index();
325        }
326        for cell_index in changes.unalived_cells {
327            let output_len = self.cells[cell_index].output_len().max(1);
328            for index in cell_index..cell_index + output_len {
329                self.cells[index] = CellRepr::Void.into();
330            }
331            did_change = true;
332        }
333        for (index, new_cell) in changes.replaced_cells {
334            assert_eq!(self.cells[index].output_len(), new_cell.output_len());
335            self.cells[index] = new_cell;
336            // CellRef::replace() ensures the new cell is different.
337            did_change = true;
338        }
339        self.ios.extend(changes.added_ios);
340        self.cells.extend(changes.added_cells);
341        changes.cell_cache.clear();
342        if !changes.replaced_nets.is_empty() {
343            for cell in self.cells.iter_mut().filter(|cell| !matches!(cell.repr, CellRepr::Skip(_) | CellRepr::Void)) {
344                cell.repr.visit_mut(|net| {
345                    while let Some(new_net) = changes.replaced_nets.get(net) {
346                        if *net != *new_net {
347                            *net = *new_net;
348                            did_change = true;
349                        }
350                    }
351                });
352            }
353            changes.replaced_nets.clear();
354        }
355        did_change
356    }
357
358    pub fn target(&self) -> Option<Arc<dyn Target>> {
359        self.target.as_ref().map(|target| target.clone())
360    }
361
362    pub fn target_prototype(&self, target_cell: &TargetCell) -> &TargetPrototype {
363        self.target
364            .as_ref()
365            .expect("design has no target")
366            .prototype(&target_cell.kind)
367            .expect("target prototype not defined")
368    }
369}
370
371#[derive(Debug, Clone, PartialEq, Eq, Hash)]
372struct AnnotatedCell {
373    repr: CellRepr,
374    meta: MetaItemIndex,
375}
376
377impl Deref for AnnotatedCell {
378    type Target = CellRepr;
379
380    fn deref(&self) -> &Self::Target {
381        &self.repr
382    }
383}
384
385impl Into<AnnotatedCell> for CellRepr {
386    fn into(self) -> AnnotatedCell {
387        AnnotatedCell { repr: self, meta: MetaItemIndex::NONE }
388    }
389}
390
391pub struct WithMetadataGuard<'a> {
392    design: &'a Design,
393    restore: MetaItemIndex,
394}
395
396impl Drop for WithMetadataGuard<'_> {
397    fn drop(&mut self) {
398        self.design.changes.borrow_mut().cell_metadata = self.restore;
399    }
400}
401
402#[derive(Clone, Copy)]
403pub struct CellRef<'a> {
404    design: &'a Design,
405    index: usize,
406}
407
408impl PartialEq<CellRef<'_>> for CellRef<'_> {
409    fn eq(&self, other: &CellRef<'_>) -> bool {
410        std::ptr::eq(self.design, other.design) && self.index == other.index
411    }
412}
413
414impl Eq for CellRef<'_> {}
415
416impl PartialOrd<CellRef<'_>> for CellRef<'_> {
417    fn partial_cmp(&self, other: &CellRef<'_>) -> Option<std::cmp::Ordering> {
418        Some(self.cmp(other))
419    }
420}
421
422impl Ord for CellRef<'_> {
423    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
424        match (self.design as *const Design).cmp(&(other.design as *const Design)) {
425            core::cmp::Ordering::Equal => self.index.cmp(&other.index),
426            ord => ord,
427        }
428    }
429}
430
431impl Hash for CellRef<'_> {
432    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
433        self.index.hash(state);
434    }
435}
436
437impl<'a> CellRef<'a> {
438    pub fn get(&self) -> Cow<'_, Cell> {
439        self.design.cells[self.index].get()
440    }
441
442    pub fn metadata(&self) -> MetaItemRef<'a> {
443        self.design.metadata.borrow().ref_item(self.design, self.design.cells[self.index].meta)
444    }
445
446    pub fn output_len(&self) -> usize {
447        self.design.cells[self.index].output_len()
448    }
449
450    pub fn output(&self) -> Value {
451        Value::from_cell_range(self.index, self.output_len())
452    }
453
454    pub fn visit(&self, f: impl FnMut(Net)) {
455        self.design.cells[self.index].visit(f)
456    }
457
458    pub fn replace(&self, to_cell: Cell) {
459        if *self.design.cells[self.index].get() != to_cell {
460            to_cell.validate(self.design);
461            let to_cell = AnnotatedCell { repr: to_cell.into(), meta: self.design.cells[self.index].meta };
462            let mut changes = self.design.changes.borrow_mut();
463            assert!(changes.replaced_cells.insert(self.index, to_cell).is_none());
464        }
465    }
466
467    pub fn append_metadata(&self, metadata: MetaItemRef<'a>) {
468        let mut changes = self.design.changes.borrow_mut();
469        changes.appended_metadata.entry(self.index).or_default().push(metadata.index())
470    }
471
472    pub fn unalive(&self) {
473        let mut changes = self.design.changes.borrow_mut();
474        changes.unalived_cells.insert(self.index);
475    }
476
477    /// Returns the same index as the one used by `Display` implementation. There is intentionally no way to retrieve
478    /// a cell by its index.
479    pub fn debug_index(&self) -> usize {
480        self.index
481    }
482
483    pub(crate) fn metadata_index(&self) -> MetaItemIndex {
484        self.design.cells[self.index].meta
485    }
486
487    /// Returns a reference to the underlying [`Design`].
488    pub fn design(self) -> &'a Design {
489        self.design
490    }
491}
492
493pub struct CellIter<'a> {
494    design: &'a Design,
495    index: usize,
496}
497
498impl<'a> Iterator for CellIter<'a> {
499    type Item = CellRef<'a>;
500
501    fn next(&mut self) -> Option<Self::Item> {
502        while matches!(self.design.cells.get(self.index), Some(AnnotatedCell { repr: CellRepr::Void, .. })) {
503            self.index += 1;
504        }
505        if self.index < self.design.cells.len() {
506            let cell_ref = CellRef { design: self.design, index: self.index };
507            self.index += self.design.cells[self.index].output_len().max(1);
508            Some(cell_ref)
509        } else {
510            None
511        }
512    }
513}
514
515macro_rules! builder_fn {
516    () => {};
517
518    ($func:ident( $($arg:ident : $argty:ty),+ ) -> $retty:ty : $cstr:ident $body:tt; $($rest:tt)*) => {
519        pub fn $func(&self, $( $arg: $argty ),+) -> $retty {
520            self.add_cell(Cell::$cstr $body).try_into().unwrap()
521        }
522
523        builder_fn!{ $($rest)* }
524    };
525
526    // For cells with no output value.
527    ($func:ident( $($arg:ident : $argty:ty),+ ) : $cstr:ident $body:tt; $($rest:tt)*) => {
528        pub fn $func(&self, $( $arg: $argty ),+) {
529            self.add_cell(Cell::$cstr $body);
530        }
531
532        builder_fn!{ $($rest)* }
533    };
534}
535
536impl Design {
537    builder_fn! {
538        add_buf(arg: impl Into<Value>) -> Value :
539            Buf(arg.into());
540        add_buf1(arg: impl Into<Net>) -> Net :
541            Buf(arg.into().into());
542        add_not(arg: impl Into<Value>) -> Value :
543            Not(arg.into());
544        add_not1(arg: impl Into<Net>) -> Net :
545            Not(arg.into().into());
546        add_and(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
547            And(arg1.into(), arg2.into());
548        add_and1(arg1: impl Into<Net>, arg2: impl Into<Net>) -> Net :
549            And(arg1.into().into(), arg2.into().into());
550        add_or(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
551            Or(arg1.into(), arg2.into());
552        add_or1(arg1: impl Into<Net>, arg2: impl Into<Net>) -> Net :
553            Or(arg1.into().into(), arg2.into().into());
554        add_xor(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
555            Xor(arg1.into(), arg2.into());
556        add_xor1(arg1: impl Into<Net>, arg2: impl Into<Net>) -> Net :
557            Xor(arg1.into().into(), arg2.into().into());
558        add_adc(arg1: impl Into<Value>, arg2: impl Into<Value>, arg3: impl Into<Net>) -> Value :
559            Adc(arg1.into(), arg2.into(), arg3.into());
560        add_aig(arg1: impl Into<ControlNet>, arg2: impl Into<ControlNet>) -> Net :
561            Aig(arg1.into(), arg2.into());
562
563        add_eq(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Net :
564            Eq(arg1.into(), arg2.into());
565        add_ult(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Net :
566            ULt(arg1.into(), arg2.into());
567        add_slt(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Net :
568            SLt(arg1.into(), arg2.into());
569
570        add_shl(arg1: impl Into<Value>, arg2: impl Into<Value>, stride: u32) -> Value :
571            Shl(arg1.into(), arg2.into(), stride);
572        add_ushr(arg1: impl Into<Value>, arg2: impl Into<Value>, stride: u32) -> Value :
573            UShr(arg1.into(), arg2.into(), stride);
574        add_sshr(arg1: impl Into<Value>, arg2: impl Into<Value>, stride: u32) -> Value :
575            SShr(arg1.into(), arg2.into(), stride);
576        add_xshr(arg1: impl Into<Value>, arg2: impl Into<Value>, stride: u32) -> Value :
577            XShr(arg1.into(), arg2.into(), stride);
578
579        add_mul(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
580            Mul(arg1.into(), arg2.into());
581        add_udiv(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
582            UDiv(arg1.into(), arg2.into());
583        add_umod(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
584            UMod(arg1.into(), arg2.into());
585        add_sdiv_trunc(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
586            SDivTrunc(arg1.into(), arg2.into());
587        add_sdiv_floor(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
588            SDivFloor(arg1.into(), arg2.into());
589        add_smod_trunc(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
590            SModTrunc(arg1.into(), arg2.into());
591        add_smod_floor(arg1: impl Into<Value>, arg2: impl Into<Value>) -> Value :
592            SModFloor(arg1.into(), arg2.into());
593
594        add_match(arg: impl Into<MatchCell>) -> Value :
595            Match(arg.into());
596        add_assign(arg: impl Into<AssignCell>) -> Value :
597            Assign(arg.into());
598        add_dff(arg: impl Into<FlipFlop>) -> Value :
599            Dff(arg.into());
600        add_memory(arg: impl Into<Memory>) -> Value :
601            Memory(arg.into());
602        add_iobuf(arg: impl Into<IoBuffer>) -> Value :
603            IoBuf(arg.into());
604        add_other(arg: impl Into<Instance>) -> Value :
605            Other(arg.into());
606        add_target(arg: impl Into<TargetCell>) -> Value :
607            Target(arg.into());
608
609        add_input(name: impl Into<String>, width: usize) -> Value :
610            Input(name.into(), width);
611        add_input1(name: impl Into<String>) -> Net :
612            Input(name.into(), 1);
613        add_output(name: impl Into<String>, value: impl Into<Value>) :
614            Output(name.into(), value.into());
615        add_name(name: impl Into<String>, value: impl Into<Value>) :
616            Name(name.into(), value.into());
617        add_debug(name: impl Into<String>, value: impl Into<Value>) :
618            Debug(name.into(), value.into());
619    }
620
621    pub fn add_mux(&self, arg1: impl Into<ControlNet>, arg2: impl Into<Value>, arg3: impl Into<Value>) -> Value {
622        match arg1.into() {
623            ControlNet::Pos(net) => self.add_cell(Cell::Mux(net, arg2.into(), arg3.into())),
624            ControlNet::Neg(net) => self.add_cell(Cell::Mux(net, arg3.into(), arg2.into())),
625        }
626    }
627
628    pub fn add_mux1(&self, arg1: impl Into<ControlNet>, arg2: impl Into<Net>, arg3: impl Into<Net>) -> Net {
629        match arg1.into() {
630            ControlNet::Pos(net) => self.add_cell(Cell::Mux(net, arg2.into().into(), arg3.into().into())).unwrap_net(),
631            ControlNet::Neg(net) => self.add_cell(Cell::Mux(net, arg3.into().into(), arg2.into().into())).unwrap_net(),
632        }
633    }
634
635    pub fn add_ne(&self, arg1: impl Into<Value>, arg2: impl Into<Value>) -> Net {
636        let eq = self.add_eq(arg1, arg2);
637        self.add_not1(eq)
638    }
639}
640
641impl Design {
642    pub fn iter_cells_topo(&self) -> impl DoubleEndedIterator<Item = CellRef<'_>> {
643        fn get_deps(design: &Design, cell: CellRef) -> BTreeSet<usize> {
644            let mut result = BTreeSet::new();
645            cell.visit(|net| {
646                if let Ok((cell, _offset)) = design.find_cell(net) {
647                    result.insert(cell.index);
648                }
649            });
650            result
651        }
652
653        let mut result = vec![];
654        let mut visited = BTreeSet::new();
655        // emit inputs, iobs and stateful cells first, in netlist order
656        for cell in self.iter_cells() {
657            match &*cell.get() {
658                Cell::Input(..) | Cell::IoBuf(..) | Cell::Dff(..) | Cell::Other(..) => {
659                    visited.insert(cell.index);
660                    result.push(cell);
661                }
662                Cell::Target(target_cell) => {
663                    if self.target_prototype(target_cell).purity != TargetCellPurity::Pure {
664                        visited.insert(cell.index);
665                        result.push(cell);
666                    }
667                }
668                _ => (),
669            }
670        }
671        // now emit combinational cells, in topologically-sorted order whenever possible.
672        // we try to emit them in netlist order; however, if we try to emit a cell
673        // that has an input that has not yet been emitted, we push it on a stack,
674        // and go emit the inputs instead.  the cell is put on the "visitted" list
675        // as soon as we start processing it, so cycles will be automatically broken
676        // by considering inputs already on the processing stack as "already emitted".
677        for cell in self.iter_cells() {
678            if matches!(&*cell.get(), Cell::Output(..) | Cell::Name(..) | Cell::Debug(..)) {
679                continue;
680            }
681            if visited.contains(&cell.index) {
682                continue;
683            }
684            visited.insert(cell.index);
685            let mut stack = vec![(cell, get_deps(self, cell))];
686            'outer: while let Some((cell, deps)) = stack.last_mut() {
687                while let Some(dep_index) = deps.pop_first() {
688                    if !visited.contains(&dep_index) {
689                        let cell = CellRef { design: self, index: dep_index };
690                        visited.insert(dep_index);
691                        stack.push((cell, get_deps(self, cell)));
692                        continue 'outer;
693                    }
694                }
695                result.push(*cell);
696                stack.pop();
697            }
698        }
699        // finally, emit outputs, names, and debugs
700        for cell in self.iter_cells() {
701            if visited.contains(&cell.index) {
702                continue;
703            }
704            result.push(cell);
705        }
706        result.into_iter()
707    }
708
709    pub fn compact(&mut self) -> bool {
710        let did_change = self.apply();
711
712        let mut queue = BTreeSet::new();
713        let mut debug = BTreeMap::new();
714        for (index, cell) in self.cells.iter().enumerate() {
715            if matches!(cell.repr, CellRepr::Skip(_) | CellRepr::Void) {
716                continue;
717            }
718            match &*cell.get() {
719                cell if cell.has_effects(self) => {
720                    queue.insert(index);
721                }
722                Cell::Debug(name, value) => {
723                    debug.insert(name.clone(), (value.clone(), cell.meta));
724                }
725                _ => (),
726            }
727        }
728
729        let mut keep = BTreeSet::new();
730        while let Some(index) = queue.pop_first() {
731            keep.insert(index);
732            self.cells[index].visit(|net| {
733                if let Ok((cell_ref, _offset)) = self.find_cell(net) {
734                    if !keep.contains(&cell_ref.index) {
735                        queue.insert(cell_ref.index);
736                    }
737                }
738            });
739        }
740
741        let mut net_map = BTreeMap::new();
742        for (old_index, cell) in std::mem::take(&mut self.cells).into_iter().enumerate() {
743            if keep.contains(&old_index) {
744                let new_index = self.cells.len();
745                for offset in 0..cell.output_len() {
746                    net_map.insert(Net::from_cell_index(old_index + offset), Net::from_cell_index(new_index + offset));
747                }
748                let skip_count = cell.output_len().checked_sub(1).unwrap_or(0);
749                self.cells.push(cell);
750                for _ in 0..skip_count {
751                    self.cells.push(CellRepr::Skip(new_index as u32).into());
752                }
753            }
754        }
755
756        for cell in self.cells.iter_mut().filter(|cell| !matches!(cell.repr, CellRepr::Skip(_))) {
757            cell.repr.visit_mut(|net| {
758                if net.is_cell() {
759                    *net = net_map[net];
760                }
761            });
762        }
763
764        for (name, (mut value, meta)) in debug {
765            value.visit_mut(|net| {
766                if net.is_cell() {
767                    if let Some(&new_net) = net_map.get(net) {
768                        *net = new_net;
769                    } else {
770                        *net = Net::UNDEF;
771                    }
772                }
773            });
774            self.cells.push(AnnotatedCell { repr: CellRepr::Boxed(Box::new(Cell::Debug(name, value))), meta });
775        }
776
777        did_change
778    }
779
780    pub fn statistics(&self) -> BTreeMap<String, usize> {
781        let result = RefCell::new(BTreeMap::<String, usize>::new());
782        for cell_ref in self.iter_cells() {
783            let simple = |name: &str| {
784                *result.borrow_mut().entry(format!("{name}")).or_default() += 1;
785            };
786            let bitwise = |name: &str, amount: usize| {
787                *result.borrow_mut().entry(format!("{name}")).or_default() += amount;
788            };
789            let wide = |name: &str, size: usize| {
790                *result.borrow_mut().entry(format!("{name}:{size}")).or_default() += 1;
791            };
792            let custom = |args: std::fmt::Arguments| {
793                *result.borrow_mut().entry(format!("{args}")).or_default() += 1;
794            };
795            match &*cell_ref.get() {
796                Cell::Buf(arg) => bitwise("buf", arg.len()),
797                Cell::Not(arg) => bitwise("not", arg.len()),
798                Cell::And(arg, _) => bitwise("and", arg.len()),
799                Cell::Or(arg, _) => bitwise("or", arg.len()),
800                Cell::Xor(arg, _) => bitwise("xor", arg.len()),
801                Cell::Mux(_, arg, _) => bitwise("mux", arg.len()),
802                Cell::Adc(arg, _, _) => wide("adc", arg.len()),
803                Cell::Aig(_, _) => simple("aig"),
804                Cell::Eq(arg, _) => wide("eq", arg.len()),
805                Cell::ULt(arg, _) => wide("ult", arg.len()),
806                Cell::SLt(arg, _) => wide("slt", arg.len()),
807                Cell::Shl(arg, _, _) => wide("shl", arg.len()),
808                Cell::UShr(arg, _, _) => wide("ushr", arg.len()),
809                Cell::SShr(arg, _, _) => wide("sshr", arg.len()),
810                Cell::XShr(arg, _, _) => wide("xshr", arg.len()),
811                Cell::Mul(arg, _) => wide("mul", arg.len()),
812                Cell::UDiv(arg, _) => wide("udiv", arg.len()),
813                Cell::UMod(arg, _) => wide("umod", arg.len()),
814                Cell::SDivTrunc(arg, _) => wide("sdiv_trunc", arg.len()),
815                Cell::SDivFloor(arg, _) => wide("sdiv_floor", arg.len()),
816                Cell::SModTrunc(arg, _) => wide("smod_trunc", arg.len()),
817                Cell::SModFloor(arg, _) => wide("smod_floor", arg.len()),
818                Cell::Match(_) => custom(format_args!("match")),
819                Cell::Assign(AssignCell { value, .. }) => bitwise("assign", value.len()),
820                Cell::Dff(FlipFlop { data, .. }) => bitwise("dff", data.len()),
821                Cell::Memory(Memory { depth, width, .. }) => custom(format_args!("memory:{depth}:{width}")),
822                Cell::IoBuf(IoBuffer { io, .. }) => bitwise("iobuf", io.len()),
823                Cell::Target(TargetCell { kind, .. }) => custom(format_args!("{kind}")),
824                Cell::Other(Instance { kind, .. }) => custom(format_args!("{kind}")),
825                Cell::Input(_, width) => bitwise("input", *width),
826                Cell::Output(_, value) => bitwise("output", value.len()),
827                Cell::Name(..) | Cell::Debug(..) => (),
828            }
829        }
830        result.into_inner()
831    }
832}
833
834// This can't be in `crate::print` because of the privacy violations.
835impl Display for Design {
836    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
837        let changes = self.changes.borrow();
838
839        let diff = self.is_changed();
840        let added = "+";
841        let removed = "-";
842        let unchanged = " ";
843        let comment = if !diff { "; " } else { " ; " };
844
845        let mut net_names = BTreeMap::new();
846        for cell_ref in self.iter_cells() {
847            match &*cell_ref.get() {
848                Cell::Output(name, value) | Cell::Name(name, value) | Cell::Debug(name, value) => {
849                    let name = Rc::new(name.clone());
850                    for (offset, net) in value.iter().enumerate() {
851                        if net.is_cell() {
852                            net_names.insert(net, (name.clone(), offset));
853                        }
854                    }
855                }
856                _ => (),
857            }
858        }
859
860        if let Some(target) = self.target() {
861            write!(f, "{}target ", if !diff { "" } else { unchanged })?;
862            Design::write_string(f, target.name())?;
863            for (name, value) in target.options() {
864                write!(f, " ")?;
865                Design::write_string(f, &name)?;
866                write!(f, "=")?;
867                Design::write_string(f, &value)?;
868            }
869            writeln!(f)?;
870        }
871
872        for metadata_ref in self.metadata.borrow().iter_items(self) {
873            if metadata_ref.index() == MetaItemIndex::NONE {
874                continue;
875            }
876            write!(f, "{}", if !diff { "" } else { unchanged })?;
877            write!(f, "{} = ", metadata_ref.index())?;
878            let item = metadata_ref.get();
879            match item {
880                MetaItem::None => unreachable!(),
881                MetaItem::Set(items) => {
882                    write!(f, "{{")?;
883                    for item in items {
884                        write!(f, " {}", item.index())?;
885                    }
886                    write!(f, " }}")?;
887                }
888                MetaItem::Source { file, start, end } => {
889                    write!(f, "source ")?;
890                    Design::write_string(f, &file.get())?;
891                    write!(f, " (#{} #{}) (#{} #{})", start.line, start.column, end.line, end.column)?;
892                }
893                MetaItem::NamedScope { name: _, source, parent }
894                | MetaItem::IndexedScope { index: _, source, parent } => {
895                    write!(f, "scope ")?;
896                    match item {
897                        MetaItem::NamedScope { name, .. } => Design::write_string(f, &name.get())?,
898                        MetaItem::IndexedScope { index, .. } => write!(f, "#{index}")?,
899                        _ => unreachable!(),
900                    }
901                    if !parent.is_none() {
902                        write!(f, " in={}", parent.index())?;
903                    }
904                    if !source.is_none() {
905                        write!(f, " src={}", source.index())?;
906                    }
907                }
908                MetaItem::Ident { name, scope } => {
909                    write!(f, "ident ")?;
910                    Design::write_string(f, &name.get())?;
911                    write!(f, " in={}", scope.index())?;
912                }
913                MetaItem::Attr { name, value } => {
914                    write!(f, "attr ")?;
915                    Design::write_string(f, &name.get())?;
916                    write!(f, " {value}")?;
917                }
918            }
919            writeln!(f)?;
920        }
921
922        for (name, io_value) in self.iter_ios() {
923            write!(f, "{}&", if !diff { "" } else { unchanged })?;
924            Design::write_string(f, name)?;
925            writeln!(f, ":{} = io", io_value.len())?;
926        }
927        for (name, io_value) in &changes.added_ios {
928            write!(f, "{added}&")?;
929            Design::write_string(f, name)?;
930            writeln!(f, ":{} = io", io_value.len())?;
931        }
932
933        let write_cell = |f: &mut std::fmt::Formatter, index: usize, cell: &Cell, metadata: MetaItemIndex| {
934            for item in self.ref_metadata_item(metadata).iter() {
935                match item.get() {
936                    MetaItem::Source { file, start, end: _ } => {
937                        writeln!(f, "{comment}source file://{}#{}", file.get(), start.line + 1)?;
938                    }
939                    MetaItem::NamedScope { .. } => {
940                        let mut names = Vec::new();
941                        let mut scope = item;
942                        while !scope.is_none() {
943                            let MetaItem::NamedScope { name, parent, .. } = scope.get() else { break };
944                            names.push(name);
945                            scope = parent;
946                        }
947                        if !names.is_empty() {
948                            write!(f, "{comment}scope ")?;
949                            for (index, name) in names.iter().rev().enumerate() {
950                                if index > 0 {
951                                    write!(f, ".")?;
952                                }
953                                write!(f, "{}", name.get())?;
954                            }
955                            writeln!(f)?;
956                        }
957                    }
958                    _ => (),
959                }
960            }
961            if matches!(cell, Cell::Target(..)) {
962                for index in (index..index + cell.output_len()).rev() {
963                    if let Some((name, offset)) = net_names.get(&Net::from_cell_index(index)) {
964                        write!(f, "{comment}drives ")?;
965                        Design::write_string(f, &*name)?;
966                        writeln!(f, "+{offset}")?;
967                    }
968                }
969            }
970            if !diff {
971                self.write_cell(f, "", index, cell, metadata)?;
972            } else if changes.unalived_cells.contains(&index) {
973                self.write_cell(f, removed, index, cell, metadata)?;
974            } else {
975                let mut mapped_cell;
976                if let Some(replaced_cell) = changes.replaced_cells.get(&index) {
977                    mapped_cell = (*replaced_cell.get()).clone();
978                } else {
979                    mapped_cell = cell.clone();
980                }
981                mapped_cell.visit_mut(|net| {
982                    while let Some(&new_net) = changes.replaced_nets.get(net) {
983                        *net = new_net;
984                    }
985                });
986                if index >= self.cells.len() {
987                    self.write_cell(f, added, index, &mapped_cell, metadata)?;
988                } else if mapped_cell != *cell {
989                    self.write_cell(f, removed, index, cell, metadata)?;
990                    writeln!(f)?;
991                    self.write_cell(f, added, index, &mapped_cell, metadata)?;
992                } else {
993                    self.write_cell(f, unchanged, index, cell, metadata)?;
994                }
995            }
996            writeln!(f)
997        };
998
999        if f.alternate() {
1000            for cell_ref in self.iter_cells() {
1001                write_cell(f, cell_ref.index, &*cell_ref.get(), cell_ref.metadata_index())?;
1002            }
1003        } else {
1004            for cell_ref in self.iter_cells_topo() {
1005                write_cell(f, cell_ref.index, &*cell_ref.get(), cell_ref.metadata_index())?;
1006            }
1007        }
1008        for (offset, cell) in changes.added_cells.iter().enumerate() {
1009            if !matches!(cell.repr, CellRepr::Skip(_) | CellRepr::Void) {
1010                write_cell(f, self.cells.len() + offset, &*cell.get(), cell.meta)?;
1011            }
1012        }
1013
1014        Ok(())
1015    }
1016}
prjunnamed_netlist/design.rs

prjunnamed_netlist/
design.rs
