prjunnamed_generic/
decision.rs

1//! Decision tree lowering.
2//!
3//! The `decision` pass implements decision tree lowering based on the well-known heuristic
4//! algorithm developed for ML from the paper "Tree pattern matching for ML" by Marianne Baudinet
5//! and David MacQueen (unpublished, 1985) the extended abstract of which is available from:
6//! *  <https://smlfamily.github.io/history/Baudinet-DM-tree-pat-match-12-85.pdf> (scan)
7//! *  <https://www.classes.cs.uchicago.edu/archive/2011/spring/22620-1/papers/macqueen-baudinet85.pdf> (OCR)
8//!
9//! The algorithm is described in §4 "Decision trees and the dispatching problem". Only two
10//! of the heuristics described apply here: the relevance heuristic and the branching factor
11//! heuristic.
12
13use std::fmt::Display;
14use std::collections::{BTreeMap, BTreeSet};
15use std::rc::Rc;
16
17use prjunnamed_netlist::{AssignCell, Cell, CellRef, Const, Design, MatchCell, Net, Trit, Value};
18
19/// Maps `pattern` (a constant where 0 and 1 match the respective states, and X matches any state)
20/// to a set of `rules` (the nets that are asserted if the `pattern` matches the value being tested).
21#[derive(Debug, Clone, PartialEq, Eq)]
22struct MatchRow {
23    pattern: Const,
24    rules: BTreeSet<Net>,
25}
26
27/// Matches `value` against ordered `rows` of patterns and their corresponding rules, where the `rules`
28/// for the first pattern that matches the value being tested are asserted, and all other `rules`
29/// are deasserted.
30///
31/// Invariant: once a matrix is constructed, there is always a case that matches.
32/// Note that due to the possiblity of inputs being `X`, this is only
33/// satisfiable with a catch-all row.
34#[derive(Debug, Clone, PartialEq, Eq)]
35struct MatchMatrix {
36    value: Value,
37    rows: Vec<MatchRow>,
38}
39
40/// Describes the process of testing individual nets of a value (equivalently, eliminating columns
41/// from a match matrix) until a specific row is reached.
42#[derive(Debug, Clone, PartialEq, Eq)]
43enum Decision {
44    /// Drive a set of nets to 1.
45    Result { rules: BTreeSet<Net> },
46    /// Branch on the value of a particular net.
47    Branch { test: Net, if0: Box<Decision>, if1: Box<Decision> },
48}
49
50impl MatchRow {
51    fn new(pattern: impl Into<Const>, rules: impl IntoIterator<Item = Net>) -> Self {
52        Self { pattern: pattern.into(), rules: BTreeSet::from_iter(rules) }
53    }
54
55    fn empty(pattern_len: usize) -> Self {
56        Self::new(Const::undef(pattern_len), [])
57    }
58
59    fn merge(mut self, other: &MatchRow) -> Self {
60        self.pattern.extend(&other.pattern);
61        self.rules.extend(other.rules.iter().cloned());
62        self
63    }
64}
65
66impl MatchMatrix {
67    fn new(value: impl Into<Value>) -> Self {
68        Self { value: value.into(), rows: Vec::new() }
69    }
70
71    fn add(&mut self, row: MatchRow) -> usize {
72        assert_eq!(self.value.len(), row.pattern.len());
73        self.rows.push(row);
74        self.rows.len() - 1
75    }
76
77    fn add_enable(&mut self, enable: Net) {
78        if enable != Net::ONE {
79            for row in &mut self.rows {
80                row.pattern.push(Trit::One);
81            }
82            self.rows.insert(0, MatchRow::new(Const::undef(self.value.len()).concat(Trit::Zero), []));
83            self.value.push(enable);
84        }
85    }
86
87    /// Merge in a `MatchMatrix` describing a child `match` cell whose `enable`
88    /// input is being driven by `at`.
89    fn merge(mut self, at: Net, other: &MatchMatrix) -> Self {
90        self.value.extend(&other.value);
91        for self_row in std::mem::take(&mut self.rows) {
92            if self_row.rules.contains(&at) {
93                for other_row in &other.rows {
94                    self.add(self_row.clone().merge(other_row));
95                }
96            } else {
97                self.add(self_row.merge(&MatchRow::empty(other.value.len())));
98            }
99        }
100        self
101    }
102
103    fn iter_outputs(&self) -> impl Iterator<Item = Net> {
104        let mut outputs: Vec<Net> = self.rows.iter().flat_map(|row| row.rules.iter().copied()).collect();
105        outputs.sort();
106        outputs.dedup();
107        outputs.into_iter()
108    }
109
110    fn assume(mut self, target: Net, value: Trit) -> Self {
111        self.value =
112            Value::from_iter(self.value.into_iter().map(|net| if net == target { Net::from(value) } else { net }));
113        self
114    }
115
116    /// Remove redundant rows and columns.
117    ///
118    /// This function ensures the following normal-form properties:
119    /// - `self.value` does not contain any constant nets
120    /// - all nets occurs within `self.value` at most once
121    /// - a row of all `X` can only occur at the very end
122    /// - no two identical rows can occur immediately next to each other
123    ///
124    /// Note that the last of these properties is relatively weak, in that
125    /// stronger properties exist which can still be feasibly checked.
126    fn normalize(mut self) -> Self {
127        let mut remove_cols = BTreeSet::new();
128        let mut remove_rows = BTreeSet::new();
129
130        // Pick columns to remove where the matched value is constant or has repeated nets.
131
132        // For each `Net`, store the index of the first column being driven
133        // by that net.
134        let mut first_at = BTreeMap::new();
135        for (index, net) in self.value.iter().enumerate() {
136            if net.is_cell() && !first_at.contains_key(&net) {
137                first_at.insert(net, index);
138            } else {
139                remove_cols.insert(index);
140            }
141        }
142
143        // Pick rows to remove that:
144        // * are redundant with the immediately preceeding row, or
145        // * contradict themselves or the constant nets in matched value.
146        let mut prev_pattern = None;
147        'outer: for (row_index, row) in self.rows.iter_mut().enumerate() {
148            // Check if row will never match because of a previous row that:
149            // * has the same pattern, or
150            // * matches any value.
151            if let Some(ref prev_pattern) = prev_pattern
152                && (row.pattern == *prev_pattern || prev_pattern.is_undef())
153            {
154                remove_rows.insert(row_index);
155                continue;
156            }
157            prev_pattern = Some(row.pattern.clone());
158            // Check if row is contradictory.
159            for (net_index, net) in self.value.iter().enumerate() {
160                let mask = row.pattern[net_index];
161                // Row contradicts constant in matched value.
162                //
163                // Note that if we're matching against a constant `X`, removing
164                // the row is nevertheless valid, since the row isn't guaranteed
165                // to match regardless of the value of the `X`, and so we can
166                // refine it into "doesn't match".
167                match net.as_const() {
168                    Some(trit) if trit != mask && mask != Trit::Undef => {
169                        remove_rows.insert(row_index);
170                        continue 'outer;
171                    }
172                    _ => (),
173                }
174                // Check if the net appears multiple times in the matched value.
175                match first_at.get(&net) {
176                    // It doesn't.
177                    None => (),
178                    // It does and this is the first occurrence. Leave it alone.
179                    Some(&first_index) if first_index == net_index => (),
180                    // It does and this is the second or later occurrence. Check if it is compatible with
181                    // the first one. Also, if the first one was a don't-care, move this one into the position
182                    // of the first one.
183                    Some(&first_index) => {
184                        let first_mask = &mut row.pattern[first_index];
185                        if *first_mask != Trit::Undef && mask != Trit::Undef && *first_mask != mask {
186                            remove_rows.insert(row_index);
187                            continue 'outer;
188                        }
189                        if *first_mask == Trit::Undef {
190                            *first_mask = mask;
191                        }
192                    }
193                }
194            }
195        }
196
197        // Pick columns to remove where all of the patterns match any value.
198        let mut all_undef = vec![true; self.value.len()];
199        for (row_index, row) in self.rows.iter().enumerate() {
200            if remove_rows.contains(&row_index) {
201                continue;
202            }
203            for col_index in 0..self.value.len() {
204                if row.pattern[col_index] != Trit::Undef {
205                    all_undef[col_index] = false;
206                }
207            }
208        }
209        for (col_index, matches_any) in all_undef.into_iter().enumerate() {
210            if matches_any {
211                remove_cols.insert(col_index);
212            }
213        }
214
215        // Execute column and row removal.
216        fn remove_indices<'a, T>(
217            iter: impl IntoIterator<Item = T> + 'a,
218            remove_set: &'a BTreeSet<usize>,
219        ) -> impl Iterator<Item = T> + 'a {
220            iter.into_iter().enumerate().filter_map(|(index, elem)| (!remove_set.contains(&index)).then_some(elem))
221        }
222
223        self.value = Value::from_iter(remove_indices(self.value, &remove_cols));
224        self.rows = Vec::from_iter(remove_indices(self.rows, &remove_rows));
225        for row in &mut self.rows {
226            row.pattern = Const::from_iter(remove_indices(row.pattern.iter(), &remove_cols));
227        }
228        self
229    }
230
231    /// Construct a decision tree for the match matrix.
232    fn dispatch(mut self) -> Decision {
233        self = self.normalize();
234        if self.value.is_empty() || self.rows.len() == 1 {
235            Decision::Result { rules: self.rows.into_iter().next().map(|r| r.rules).unwrap_or_default() }
236        } else {
237            // Fanfiction of the heuristics from the 1986 paper that reduces them to: split the matrix on the column
238            // with the fewest don't-care's in it.
239            let mut undef_count = vec![0; self.value.len()];
240            for row in self.rows.iter() {
241                for (col_index, mask) in row.pattern.iter().enumerate() {
242                    if mask == Trit::Undef {
243                        undef_count[col_index] += 1;
244                    }
245                }
246            }
247            let test_index = (0..self.value.len()).min_by_key(|&i| undef_count[i]);
248            let test = self.value[test_index.unwrap()];
249
250            // Split the matrix into two, where the test net has a value of 0 and 1, and recurse.
251            let if0 = self.clone().assume(test, Trit::Zero).dispatch();
252            let if1 = self.assume(test, Trit::One).dispatch();
253            if if0 == if1 {
254                // Skip the branch if the outputs of the decision function are the same. This can happen
255                // e.g. in the following matrix:
256                //   00 => x
257                //   10 => x
258                //   XX => y
259                // regardless of the column selection order. This is readily apparent when the left-hand
260                // column is split on first, but even if the right-hand column is chosen, there will a
261                // case-split with both arms leading to `Decision::Result(x)`.
262                if0
263            } else {
264                Decision::Branch { test, if0: if0.into(), if1: if1.into() }
265            }
266        }
267    }
268}
269
270impl Decision {
271    /// Call `f` on the contents of each `Decision::Result` in this tree.
272    fn each_leaf(&self, f: &mut impl FnMut(&BTreeSet<Net>)) {
273        match self {
274            Decision::Result { rules } => f(rules),
275            Decision::Branch { if0, if1, .. } => {
276                if0.each_leaf(f);
277                if1.each_leaf(f);
278            }
279        }
280    }
281
282    /// Emit a mux-tree that outputs `values[x]` when net `x` would be `1`
283    /// according to the decision tree.
284    ///
285    /// Assumes that each case within `values` is mutually exclusive. Panics if
286    /// that is not the case.
287    fn emit_disjoint_mux(&self, design: &Design, values: &BTreeMap<Net, Value>, default: &Value) -> Value {
288        match self {
289            Decision::Result { rules } => {
290                let mut result = None;
291                for rule in rules {
292                    if let Some(value) = values.get(rule) {
293                        assert!(result.is_none());
294                        result = Some(value.clone());
295                    }
296                }
297                result.unwrap_or(default.clone())
298            }
299            Decision::Branch { test, if0, if1 } => design.add_mux(
300                *test,
301                if1.emit_disjoint_mux(design, values, default),
302                if0.emit_disjoint_mux(design, values, default),
303            ),
304        }
305    }
306
307    /// Emit a mux-tree that drives the `nets` according to the decision tree.
308    fn emit_one_hot_mux(&self, design: &Design, nets: &Value) -> Value {
309        match self {
310            Decision::Result { rules } => Value::from_iter(
311                nets.iter().map(|net| if rules.contains(&net) { Trit::One } else { Trit::Zero }.into()),
312            ),
313            Decision::Branch { test, if0, if1 } => {
314                design.add_mux(*test, if1.emit_one_hot_mux(design, nets), if0.emit_one_hot_mux(design, nets))
315            }
316        }
317    }
318}
319
320struct MatchTrees<'a> {
321    design: &'a Design,
322    /// Set of all `match` cells that aren't children. A `match` cell is a child
323    /// of another `match` cell if its `enable` input is being driven from
324    /// the output of the parent, and it is the unique such `match` cell for
325    /// that particular output bit. That is, if it is possible to merge the
326    /// child into the same decision tree.
327    roots: BTreeSet<CellRef<'a>>,
328    /// Maps a particular output of a `match` cell to the child `match` cell
329    /// whose `enable` input it is driving.
330    subtrees: BTreeMap<(CellRef<'a>, usize), CellRef<'a>>,
331}
332
333impl<'a> MatchTrees<'a> {
334    /// Recognize a tree of `match` cells, connected by their enable inputs.
335    fn build(design: &'a Design) -> MatchTrees<'a> {
336        let mut roots: BTreeSet<CellRef> = BTreeSet::new();
337        let mut subtrees: BTreeMap<(CellRef, usize), BTreeSet<CellRef>> = BTreeMap::new();
338        for cell_ref in design.iter_cells() {
339            let Cell::Match(MatchCell { enable, .. }) = &*cell_ref.get() else { continue };
340            if let Ok((enable_cell_ref, offset)) = design.find_cell(*enable)
341                && let Cell::Match(_) = &*enable_cell_ref.get()
342            {
343                // Driven by a match cell; may be a subtree or a root depending on its fanout.
344                subtrees.entry((enable_cell_ref, offset)).or_default().insert(cell_ref);
345                continue;
346            }
347            // Driven by some other cell or a constant; is a root.
348            roots.insert(cell_ref);
349        }
350
351        // Whenever multiple subtrees are connected to the same one-hot output, it is not possible
352        // to merge all of them into the same matrix. Turn all of these subtrees into roots.
353        let subtrees = subtrees
354            .into_iter()
355            .filter_map(|(key, subtrees)| {
356                if subtrees.len() == 1 {
357                    Some((key, subtrees.into_iter().next().unwrap()))
358                } else {
359                    roots.extend(subtrees);
360                    None
361                }
362            })
363            .collect();
364
365        Self { design, roots, subtrees }
366    }
367
368    /// Convert a tree of `match` cells into a matrix.
369    ///
370    /// Collects a list of all the cells being lifted into the matrix into
371    /// `all_cell_refs`.
372    ///
373    /// Replaces outputs that don't have any patterns at all with `Net::ZERO`,
374    /// but otherwise doesn't modify the design.
375    fn cell_into_matrix(&self, cell_ref: CellRef<'a>, all_cell_refs: &mut Vec<CellRef<'a>>) -> MatchMatrix {
376        let Cell::Match(match_cell) = &*cell_ref.get() else { unreachable!() };
377        let output = cell_ref.output();
378        all_cell_refs.push(cell_ref);
379
380        // Create matrix for this cell.
381        let mut matrix = MatchMatrix::new(&match_cell.value);
382        for (output_net, alternates) in output.iter().zip(match_cell.patterns.iter()) {
383            for pattern in alternates {
384                matrix.add(MatchRow::new(pattern.clone(), [output_net]));
385            }
386            if alternates.is_empty() {
387                self.design.replace_net(output_net, Net::ZERO);
388            }
389        }
390        matrix.add(MatchRow::empty(match_cell.value.len()));
391
392        // Create matrices for subtrees and merge them into the matrix for this cell.
393        for (offset, output_net) in output.iter().enumerate() {
394            if let Some(&sub_cell_ref) = self.subtrees.get(&(cell_ref, offset)) {
395                matrix = matrix.merge(output_net, &self.cell_into_matrix(sub_cell_ref, all_cell_refs));
396            }
397        }
398
399        matrix
400    }
401
402    /// For each tree of `match` cells, return a corresponding `MatchMatrix`
403    /// and a list of `match` cells that this matrix implements.
404    fn iter_matrices<'b>(&'b self) -> impl Iterator<Item = (MatchMatrix, Vec<CellRef<'b>>)> + 'b {
405        self.roots.iter().map(|&cell_ref| {
406            let Cell::Match(MatchCell { enable, .. }) = &*cell_ref.get() else { unreachable!() };
407            let mut all_cell_refs = Vec::new();
408            let mut matrix = self.cell_into_matrix(cell_ref, &mut all_cell_refs);
409            matrix.add_enable(*enable);
410            (matrix, all_cell_refs)
411        })
412    }
413}
414
415struct AssignChains<'a> {
416    chains: Vec<Vec<CellRef<'a>>>,
417}
418
419impl<'a> AssignChains<'a> {
420    fn build(design: &'a Design) -> AssignChains<'a> {
421        let mut roots: BTreeSet<CellRef> = BTreeSet::new();
422        let mut links: BTreeMap<CellRef, BTreeSet<CellRef>> = BTreeMap::new();
423        for cell_ref in design.iter_cells() {
424            let Cell::Assign(AssignCell { value, offset: 0, update, .. }) = &*cell_ref.get() else { continue };
425            if update.len() != value.len() {
426                continue;
427            }
428            if let Ok((value_cell_ref, _offset)) = design.find_cell(value[0])
429                && value_cell_ref.output() == *value
430                && let Cell::Assign(_) = &*value_cell_ref.get()
431            {
432                links.entry(value_cell_ref).or_default().insert(cell_ref);
433                continue;
434            }
435            roots.insert(cell_ref);
436        }
437
438        let mut chains = Vec::new();
439        for root in roots {
440            let mut chain = vec![root];
441            while let Some(links) = links.get(chain.last().unwrap()) {
442                if links.len() == 1 {
443                    chain.push(*links.first().unwrap());
444                } else {
445                    break;
446                }
447            }
448            if chain.len() > 1 {
449                chains.push(chain);
450            }
451        }
452
453        Self { chains }
454    }
455
456    fn iter_disjoint<'b>(
457        &'b self,
458        decisions: &'a BTreeMap<Net, Rc<Decision>>,
459        occurrences: &BTreeMap<Net, Vec<u32>>,
460    ) -> impl Iterator<Item = (Rc<Decision>, &'b [CellRef<'a>])> {
461        fn enable_of(cell_ref: CellRef) -> Net {
462            let Cell::Assign(AssignCell { enable, .. }) = &*cell_ref.get() else { unreachable!() };
463            *enable
464        }
465
466        self.chains.iter().filter_map(|chain| {
467            let mut used_branches = BTreeSet::new();
468            // Add all branches driving `net` to `used_branches`. Returns
469            // `false` if this is a conflict (i.e. the nets aren't mutually
470            // exclusive).
471            let mut consume_branches = |net: Net| -> bool {
472                let Some(occurs) = occurrences.get(&net) else {
473                    // net is not driven by any branches in this decision tree.
474                    // this can happen if a pattern turns out to be impossible
475                    // (e.g. due to constant propagation)
476                    return true;
477                };
478
479                for &occurrence in occurs {
480                    if !used_branches.insert(occurrence) {
481                        return false;
482                    }
483                }
484
485                true
486            };
487
488            // Check if the enables belong to disjoint branches within the same decision tree
489            // (like in a SystemVerilog "unique" or "unique0" statement).
490            let enable = enable_of(chain[0]);
491            let decision = decisions.get(&enable)?;
492            assert!(consume_branches(enable));
493            let mut end_index = chain.len();
494            'chain: for (index, &other_cell) in chain.iter().enumerate().skip(1) {
495                let enable = enable_of(other_cell);
496                let other_decision = decisions.get(&enable)?;
497                if !Rc::ptr_eq(decision, other_decision) || !consume_branches(enable) {
498                    end_index = index;
499                    break 'chain;
500                }
501            }
502            let chain = &chain[..end_index];
503
504            Some((decision.clone(), chain))
505        })
506    }
507}
508
509pub fn decision(design: &mut Design) {
510    // Detect and extract trees of `match` cells present in the netlist.
511    let match_trees = MatchTrees::build(design);
512
513    // Detect and extract chains of `assign` statements without slicing.
514    let assign_chains = AssignChains::build(design);
515
516    // Combine each tree of `match` cells into a single match matrix.
517    // Then build a decision tree for it and use it to drive the output.
518    let mut decisions: BTreeMap<Net, Rc<Decision>> = BTreeMap::new();
519
520    let mut next_branch: u32 = 0;
521    let mut occurrences: BTreeMap<Net, Vec<u32>> = BTreeMap::new();
522
523    for (matrix, matches) in match_trees.iter_matrices() {
524        let all_outputs = BTreeSet::from_iter(matrix.iter_outputs());
525        if cfg!(feature = "trace") {
526            eprint!(">matrix:\n{matrix}");
527        }
528
529        let decision = Rc::new(matrix.dispatch());
530        if cfg!(feature = "trace") {
531            eprint!(">decision tree:\n{decision}")
532        }
533
534        decision.each_leaf(&mut |outputs| {
535            let branch = next_branch;
536            next_branch += 1;
537
538            for &output in outputs {
539                occurrences.entry(output).or_default().push(branch);
540            }
541        });
542
543        for &output in &all_outputs {
544            decisions.insert(output, decision.clone());
545        }
546
547        let _guard = design.use_metadata_from(&matches[..]);
548        let nets = Value::from_iter(all_outputs);
549        design.replace_value(&nets, decision.emit_one_hot_mux(design, &nets));
550    }
551
552    // Find chains of `assign` cells that are order-independent.
553    // Then lower these cells to a `mux` tree without `eq` cells.
554    let mut used_assigns = BTreeSet::new();
555    for (decision, chain) in assign_chains.iter_disjoint(&decisions, &occurrences) {
556        let (first_assign, last_assign) = (chain.first().unwrap(), chain.last().unwrap());
557        if cfg!(feature = "trace") {
558            eprintln!(">disjoint:");
559            for &cell_ref in chain {
560                eprintln!("{}", design.display_cell(cell_ref));
561            }
562        }
563
564        let mut values = BTreeMap::new();
565        let Cell::Assign(AssignCell { value: default, .. }) = &*first_assign.get() else { unreachable!() };
566        for &cell_ref in chain {
567            let Cell::Assign(AssignCell { enable, update, .. }) = &*cell_ref.get() else { unreachable!() };
568            values.insert(*enable, update.clone());
569        }
570
571        let _guard = design.use_metadata_from(chain);
572        design.replace_value(last_assign.output(), decision.emit_disjoint_mux(design, &values, default));
573        used_assigns.insert(*last_assign);
574    }
575
576    // Lower other `assign` cells.
577    for cell_ref in design.iter_cells().filter(|cell_ref| !used_assigns.contains(cell_ref)) {
578        let Cell::Assign(assign_cell) = &*cell_ref.get() else { continue };
579        if cfg!(feature = "trace") {
580            eprintln!(">chained: {}", design.display_cell(cell_ref));
581        }
582
583        let _guard = design.use_metadata_from(&[cell_ref]);
584        let mut nets = Vec::from_iter(assign_cell.value.iter());
585        let slice = assign_cell.offset..(assign_cell.offset + assign_cell.update.len());
586        nets[slice.clone()].copy_from_slice(
587            &design.add_mux(assign_cell.enable, &assign_cell.update, assign_cell.value.slice(slice))[..],
588        );
589        design.replace_value(cell_ref.output(), Value::from(nets));
590    }
591
592    design.compact();
593}
594
595impl Display for MatchRow {
596    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
597        for (index, trit) in self.pattern.iter().rev().enumerate() {
598            if index != 0 && index.is_multiple_of(4) {
599                write!(f, "_")?;
600            }
601            write!(f, "{trit}")?;
602        }
603        write!(f, " =>")?;
604        if self.rules.is_empty() {
605            return write!(f, " (empty)");
606        }
607        for rule in &self.rules {
608            write!(f, " {rule}")?;
609        }
610        Ok(())
611    }
612}
613
614impl Display for MatchMatrix {
615    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
616        writeln!(f, "{}:", self.value)?;
617        for row in &self.rows {
618            writeln!(f, "  {row}")?;
619        }
620        Ok(())
621    }
622}
623
624impl Decision {
625    fn format(&self, f: &mut std::fmt::Formatter, level: usize) -> std::fmt::Result {
626        let format_rules = |f: &mut std::fmt::Formatter, rules: &BTreeSet<Net>| {
627            if rules.is_empty() {
628                write!(f, " (empty)")
629            } else {
630                for rule in rules {
631                    write!(f, " {rule}")?;
632                }
633                Ok(())
634            }
635        };
636
637        let format_decision = |f: &mut std::fmt::Formatter, net: Net, value: usize, decision: &Decision| {
638            if let Decision::Result { rules } = decision
639                && rules.is_empty()
640            {
641                return Ok(());
642            }
643            for _ in 0..level {
644                write!(f, "  ")?;
645            }
646            match decision {
647                Decision::Result { rules } => {
648                    write!(f, "{net} = {value} =>")?;
649                    format_rules(f, rules)?;
650                    writeln!(f)
651                }
652                Decision::Branch { .. } => {
653                    writeln!(f, "{net} = {value} =>")?;
654                    decision.format(f, level + 1)
655                }
656            }
657        };
658
659        match self {
660            Decision::Result { rules } => {
661                assert_eq!(level, 0);
662                write!(f, "=>")?;
663                format_rules(f, rules)?;
664                writeln!(f)?;
665            }
666            Decision::Branch { test, if0, if1 } => {
667                format_decision(f, *test, 0, if0)?;
668                format_decision(f, *test, 1, if1)?;
669            }
670        }
671        Ok(())
672    }
673}
674
675impl Display for Decision {
676    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
677        self.format(f, 0)
678    }
679}
680
681#[cfg(test)]
682mod test {
683    #![allow(non_snake_case)]
684
685    use std::collections::{BTreeMap, BTreeSet};
686
687    use prjunnamed_netlist::{assert_isomorphic, AssignCell, Cell, Const, Design, MatchCell, Net, Value};
688
689    use super::{decision, AssignChains, Decision, MatchMatrix, MatchRow, MatchTrees};
690
691    struct Helper(Design);
692
693    impl Helper {
694        fn new() -> Self {
695            Self(Design::new())
696        }
697
698        fn val(&self, width: usize) -> Value {
699            self.0.add_void(width)
700        }
701
702        fn net(&self) -> Net {
703            self.0.add_void(1).unwrap_net()
704        }
705
706        fn rs(&self, rule: Net) -> Box<Decision> {
707            Box::new(Decision::Result { rules: BTreeSet::from_iter([rule]) })
708        }
709
710        fn br(&self, test: Net, if1: Box<Decision>, if0: Box<Decision>) -> Box<Decision> {
711            Box::new(Decision::Branch { test, if0, if1 })
712        }
713    }
714
715    #[test]
716    fn test_add_enable() {
717        let h = Helper::new();
718
719        let v = h.val(2);
720        let (n1, n2, en) = (h.net(), h.net(), h.net());
721
722        let mut ml = MatchMatrix::new(&v);
723        ml.add(MatchRow::new(Const::lit("10"), [n1]));
724        ml.add(MatchRow::new(Const::lit("01"), [n2]));
725
726        let mut mr = MatchMatrix::new(v.concat(en));
727        mr.add(MatchRow::new(Const::lit("0XX"), []));
728        mr.add(MatchRow::new(Const::lit("110"), [n1]));
729        mr.add(MatchRow::new(Const::lit("101"), [n2]));
730
731        ml.add_enable(en);
732        assert_eq!(ml, mr, "\n{ml} != \n{mr}");
733    }
734
735    #[test]
736    fn test_add_enable_trivial() {
737        let h = Helper::new();
738
739        let v = h.val(2);
740        let (n1, n2) = (h.net(), h.net());
741
742        let mut ml = MatchMatrix::new(&v);
743        ml.add(MatchRow::new(Const::lit("10"), [n1]));
744        ml.add(MatchRow::new(Const::lit("01"), [n2]));
745
746        let mr = ml.clone();
747
748        ml.add_enable(Net::ONE);
749        assert_eq!(ml, mr, "\n{ml} != \n{mr}");
750    }
751
752    #[test]
753    fn test_merge_1() {
754        let h = Helper::new();
755
756        let v1 = h.val(2);
757        let (n11, n12) = (h.net(), h.net());
758        let v2 = h.val(3);
759        let (n21, n22) = (h.net(), h.net());
760        let mut m1 = MatchMatrix::new(&v1);
761        m1.add(MatchRow::new(Const::lit("10"), [n11]));
762        m1.add(MatchRow::new(Const::lit("01"), [n12]));
763        m1.add(MatchRow::new(Const::lit("XX"), []));
764
765        let mut m2 = MatchMatrix::new(&v2);
766        m2.add(MatchRow::new(Const::lit("X00"), [n21]));
767        m2.add(MatchRow::new(Const::lit("10X"), [n22]));
768        m2.add(MatchRow::new(Const::lit("XXX"), []));
769
770        let ml1 = m1.clone().merge(n12, &m2);
771
772        let mut mr1 = MatchMatrix::new(v1.concat(&v2));
773        mr1.add(MatchRow::new(Const::lit("XXX10"), [n11]));
774        mr1.add(MatchRow::new(Const::lit("X0001"), [n12, n21]));
775        mr1.add(MatchRow::new(Const::lit("10X01"), [n12, n22]));
776        mr1.add(MatchRow::new(Const::lit("XXX01"), [n12]));
777        mr1.add(MatchRow::new(Const::lit("XXXXX"), []));
778
779        assert_eq!(ml1, mr1, "\n{ml1} != \n{mr1}");
780    }
781
782    #[test]
783    fn test_merge_2() {
784        let h = Helper::new();
785
786        let v1 = h.val(2);
787        let (n11, n12) = (h.net(), h.net());
788        let v2 = h.val(3);
789        let (n21, n22) = (h.net(), h.net());
790        let mut m1 = MatchMatrix::new(&v1);
791        m1.add(MatchRow::new(Const::lit("10"), [n11]));
792        m1.add(MatchRow::new(Const::lit("01"), [n11]));
793        m1.add(MatchRow::new(Const::lit("XX"), [n12]));
794
795        let mut m2 = MatchMatrix::new(&v2);
796        m2.add(MatchRow::new(Const::lit("X00"), [n21]));
797        m2.add(MatchRow::new(Const::lit("10X"), [n22]));
798        m2.add(MatchRow::new(Const::lit("XXX"), []));
799
800        let ml1 = m1.clone().merge(n11, &m2);
801
802        let mut mr1 = MatchMatrix::new(v1.concat(&v2));
803        mr1.add(MatchRow::new(Const::lit("X0010"), [n11, n21]));
804        mr1.add(MatchRow::new(Const::lit("10X10"), [n11, n22]));
805        mr1.add(MatchRow::new(Const::lit("XXX10"), [n11]));
806        mr1.add(MatchRow::new(Const::lit("X0001"), [n11, n21]));
807        mr1.add(MatchRow::new(Const::lit("10X01"), [n11, n22]));
808        mr1.add(MatchRow::new(Const::lit("XXX01"), [n11]));
809        mr1.add(MatchRow::new(Const::lit("XXXXX"), [n12]));
810
811        assert_eq!(ml1, mr1, "\n{ml1} != \n{mr1}");
812    }
813
814    #[test]
815    fn test_normalize_vertical() {
816        let h = Helper::new();
817        let n = h.net();
818
819        let mut m00 = MatchMatrix::new(Value::from(Const::lit("0")));
820        m00.add(MatchRow::new(Const::lit("0"), [n]));
821
822        let mut m01 = MatchMatrix::new(Value::from(Const::lit("0")));
823        m01.add(MatchRow::new(Const::lit("1"), [n]));
824
825        let mut m0X = MatchMatrix::new(Value::from(Const::lit("0")));
826        m0X.add(MatchRow::new(Const::lit("X"), [n]));
827
828        let mut m10 = MatchMatrix::new(Value::from(Const::lit("1")));
829        m10.add(MatchRow::new(Const::lit("0"), [n]));
830
831        let mut m11 = MatchMatrix::new(Value::from(Const::lit("1")));
832        m11.add(MatchRow::new(Const::lit("1"), [n]));
833
834        let mut m1X = MatchMatrix::new(Value::from(Const::lit("1")));
835        m1X.add(MatchRow::new(Const::lit("X"), [n]));
836
837        let mut mX0 = MatchMatrix::new(Value::from(Const::lit("X")));
838        mX0.add(MatchRow::new(Const::lit("0"), [n]));
839
840        let mut mX1 = MatchMatrix::new(Value::from(Const::lit("X")));
841        mX1.add(MatchRow::new(Const::lit("1"), [n]));
842
843        let mut mXX = MatchMatrix::new(Value::from(Const::lit("X")));
844        mXX.add(MatchRow::new(Const::lit("X"), [n]));
845
846        for must_reject in [m01, m10, mX0, mX1] {
847            let normalized = must_reject.clone().normalize();
848            assert_eq!(normalized.rows.len(), 0, "before:\n{must_reject}\nafter:\n{normalized}");
849        }
850        for must_accept in [m00, m0X, m11, m1X, mXX] {
851            let normalized = must_accept.clone().normalize();
852            assert_eq!(normalized.rows.len(), 1, "before:\n{must_accept}\nafter:\n{normalized}");
853            assert_eq!(normalized.rows[0].pattern.len(), 0, "before:\n{must_accept}\nafter:\n{normalized}");
854        }
855    }
856
857    #[test]
858    fn test_normalize_horizontal() {
859        let h = Helper::new();
860        let v = h.val(1);
861        let n = h.net();
862
863        let mut m1 = MatchMatrix::new(v.concat(&v));
864        m1.add(MatchRow::new(Const::lit("0X"), [n]));
865        m1 = m1.normalize();
866        assert_eq!(m1.rows[0].pattern, Const::lit("0"));
867
868        let mut m2 = MatchMatrix::new(v.concat(&v));
869        m2.add(MatchRow::new(Const::lit("X0"), [n]));
870        m2 = m2.normalize();
871        assert_eq!(m2.rows[0].pattern, Const::lit("0"));
872
873        let mut m3 = MatchMatrix::new(v.concat(&v));
874        m3.add(MatchRow::new(Const::lit("10"), [n]));
875        m3 = m3.normalize();
876        assert_eq!(m3.rows.len(), 0);
877    }
878
879    #[test]
880    fn test_normalize_duplicate_row() {
881        let h = Helper::new();
882        let v = h.val(2);
883        let (n1, n2) = (h.net(), h.net());
884
885        let mut m = MatchMatrix::new(v);
886        m.add(MatchRow::new(Const::lit("10"), [n1]));
887        m.add(MatchRow::new(Const::lit("10"), [n2]));
888        m = m.normalize();
889        assert_eq!(m.rows.len(), 1);
890        assert_eq!(m.rows[0].pattern, Const::lit("10"));
891        assert_eq!(m.rows[0].rules, BTreeSet::from_iter([n1]));
892    }
893
894    #[test]
895    fn test_normalize_irrefitable() {
896        let h = Helper::new();
897        let v = h.val(2);
898        let (n1, n2) = (h.net(), h.net());
899
900        let mut m = MatchMatrix::new(v);
901        m.add(MatchRow::new(Const::lit("XX"), [n1]));
902        m.add(MatchRow::new(Const::lit("10"), [n2]));
903        m = m.normalize();
904        assert_eq!(m.rows.len(), 1);
905        assert_eq!(m.rows[0].pattern, Const::lit(""));
906        assert_eq!(m.rows[0].rules, BTreeSet::from_iter([n1]));
907    }
908
909    #[test]
910    fn test_normalize_unused_column() {
911        let h = Helper::new();
912        let v = h.val(2);
913        let (n1, n2) = (h.net(), h.net());
914
915        let mut m = MatchMatrix::new(&v);
916        m.add(MatchRow::new(Const::lit("X0"), [n1]));
917        m.add(MatchRow::new(Const::lit("X1"), [n2]));
918        m = m.normalize();
919        assert_eq!(m.value, v.slice(0..1));
920        assert_eq!(m.rows.len(), 2);
921        assert_eq!(m.rows[0], MatchRow::new(Const::lit("0"), [n1]));
922        assert_eq!(m.rows[1], MatchRow::new(Const::lit("1"), [n2]));
923    }
924
925    #[test]
926    fn test_normalize_unused_column_after_elim() {
927        let h = Helper::new();
928        let v = h.val(2);
929        let (n1, n2, n3) = (h.net(), h.net(), h.net());
930
931        let mut m = MatchMatrix::new(v.concat(&v));
932        m.add(MatchRow::new(Const::lit("XXX0"), [n1]));
933        m.add(MatchRow::new(Const::lit("XXX1"), [n2]));
934        m.add(MatchRow::new(Const::lit("1X0X"), [n3]));
935        m = m.normalize();
936        assert_eq!(m.value, v.slice(0..1));
937        assert_eq!(m.rows.len(), 2);
938        assert_eq!(m.rows[0], MatchRow::new(Const::lit("0"), [n1]));
939        assert_eq!(m.rows[1], MatchRow::new(Const::lit("1"), [n2]));
940    }
941
942    macro_rules! assert_dispatch {
943        ($m:expr, $d:expr) => {
944            let dl = $m.clone().dispatch();
945            let dr = $d;
946            assert!(dl == *dr, "\ndispatching {}\n{} != \n{}", $m, dl, dr);
947        };
948    }
949
950    #[test]
951    fn test_decide_0() {
952        let h = Helper::new();
953
954        let v = h.val(1);
955        let n = h.net();
956        let mut m = MatchMatrix::new(&v);
957        m.add(MatchRow::new(Const::lit("0"), [n]));
958
959        let d = h.rs(n);
960
961        assert_dispatch!(m, d);
962    }
963
964    #[test]
965    fn test_decide_0_1() {
966        let h = Helper::new();
967
968        let v = h.val(1);
969        let (n1, n2) = (h.net(), h.net());
970        let mut m = MatchMatrix::new(&v);
971        m.add(MatchRow::new(Const::lit("0"), [n1]));
972        m.add(MatchRow::new(Const::lit("1"), [n2]));
973
974        let d = h.br(v[0], h.rs(n2), h.rs(n1));
975
976        assert_dispatch!(m, d);
977    }
978
979    #[test]
980    fn test_decide_0_X() {
981        let h = Helper::new();
982
983        let v = h.val(1);
984        let (n1, n2) = (h.net(), h.net());
985        let mut m = MatchMatrix::new(&v);
986        m.add(MatchRow::new(Const::lit("0"), [n1]));
987        m.add(MatchRow::new(Const::lit("X"), [n2]));
988
989        let d = h.br(v[0], h.rs(n2), h.rs(n1));
990
991        assert_dispatch!(m, d);
992    }
993
994    #[test]
995    fn test_decide_1_X() {
996        let h = Helper::new();
997
998        let v = h.val(1);
999        let (n1, n2) = (h.net(), h.net());
1000        let mut m = MatchMatrix::new(&v);
1001        m.add(MatchRow::new(Const::lit("1"), [n1]));
1002        m.add(MatchRow::new(Const::lit("X"), [n2]));
1003
1004        let d = h.br(v[0], h.rs(n1), h.rs(n2));
1005
1006        assert_dispatch!(m, d);
1007    }
1008
1009    #[test]
1010    fn test_decide_X_0_1() {
1011        let h = Helper::new();
1012
1013        let v = h.val(1);
1014        let (n1, n2, n3) = (h.net(), h.net(), h.net());
1015        let mut m = MatchMatrix::new(&v);
1016        m.add(MatchRow::new(Const::lit("X"), [n1]));
1017        m.add(MatchRow::new(Const::lit("0"), [n2]));
1018        m.add(MatchRow::new(Const::lit("1"), [n3]));
1019
1020        let d = h.rs(n1);
1021
1022        assert_dispatch!(m, d);
1023    }
1024
1025    #[test]
1026    fn test_decide_0_1_X() {
1027        let h = Helper::new();
1028
1029        let v = h.val(1);
1030        let (n1, n2, n3) = (h.net(), h.net(), h.net());
1031        let mut m = MatchMatrix::new(&v);
1032        m.add(MatchRow::new(Const::lit("0"), [n1]));
1033        m.add(MatchRow::new(Const::lit("1"), [n2]));
1034        m.add(MatchRow::new(Const::lit("X"), [n3]));
1035
1036        let d = h.br(v[0], h.rs(n2), h.rs(n1));
1037
1038        assert_dispatch!(m, d);
1039    }
1040
1041    #[test]
1042    fn test_decide_0X_1X_XX() {
1043        let h = Helper::new();
1044
1045        let v = h.val(2);
1046        let (n1, n2, n3) = (h.net(), h.net(), h.net());
1047        let mut m = MatchMatrix::new(&v);
1048        m.add(MatchRow::new(Const::lit("X0"), [n1]));
1049        m.add(MatchRow::new(Const::lit("X1"), [n2]));
1050        m.add(MatchRow::new(Const::lit("XX"), [n3]));
1051
1052        let d = h.br(v[0], h.rs(n2), h.rs(n1));
1053
1054        assert_dispatch!(m, d);
1055    }
1056
1057    #[test]
1058    fn test_decide_0X_11_XX() {
1059        let h = Helper::new();
1060
1061        let v = h.val(2);
1062        let (n1, n2, n3) = (h.net(), h.net(), h.net());
1063        let mut m = MatchMatrix::new(&v);
1064        m.add(MatchRow::new(Const::lit("0X"), [n1]));
1065        m.add(MatchRow::new(Const::lit("11"), [n2]));
1066        m.add(MatchRow::new(Const::lit("XX"), [n3]));
1067
1068        let d = h.br(v[1], h.br(v[0], h.rs(n2), h.rs(n3)), h.rs(n1));
1069
1070        assert_dispatch!(m, d);
1071    }
1072
1073    #[test]
1074    fn test_decide_00_10_XX() {
1075        let h = Helper::new();
1076
1077        let v = h.val(2);
1078        let (n1, n2) = (h.net(), h.net());
1079        let mut m = MatchMatrix::new(&v);
1080        m.add(MatchRow::new(Const::lit("00"), [n1]));
1081        m.add(MatchRow::new(Const::lit("01"), [n1]));
1082        m.add(MatchRow::new(Const::lit("XX"), [n2]));
1083
1084        let d = h.br(v[1], h.rs(n2), h.rs(n1));
1085
1086        assert_dispatch!(m, d);
1087    }
1088
1089    #[test]
1090    fn test_match_tree_build_root_1() {
1091        let mut design = Design::new();
1092        let a = design.add_input("a", 1);
1093        let y = design.add_match(MatchCell { value: a, enable: Net::ONE, patterns: vec![vec![Const::lit("0")]] });
1094        design.apply();
1095
1096        let y_cell = design.find_cell(y[0]).unwrap().0;
1097
1098        let match_trees = MatchTrees::build(&design);
1099        assert!(match_trees.roots == BTreeSet::from_iter([y_cell]));
1100        assert!(match_trees.subtrees == BTreeMap::from_iter([]));
1101    }
1102
1103    #[test]
1104    fn test_match_tree_build_root_pi() {
1105        let mut design = Design::new();
1106        let a = design.add_input("a", 1);
1107        let b = design.add_input1("b");
1108        let y = design.add_match(MatchCell { value: a, enable: b, patterns: vec![vec![Const::lit("0")]] });
1109        design.apply();
1110
1111        let y_cell = design.find_cell(y[0]).unwrap().0;
1112
1113        let match_trees = MatchTrees::build(&design);
1114        assert!(match_trees.roots == BTreeSet::from_iter([y_cell]));
1115        assert!(match_trees.subtrees == BTreeMap::from_iter([]));
1116    }
1117
1118    #[test]
1119    fn test_match_tree_build_root_subtree() {
1120        let mut design = Design::new();
1121        let a = design.add_input("a", 1);
1122        let y1 =
1123            design.add_match(MatchCell { value: a.clone(), enable: Net::ONE, patterns: vec![vec![Const::lit("0")]] });
1124        let y2 = design.add_match(MatchCell { value: a, enable: y1[0], patterns: vec![vec![Const::lit("0")]] });
1125        design.apply();
1126
1127        let y1_cell = design.find_cell(y1[0]).unwrap().0;
1128        let y2_cell = design.find_cell(y2[0]).unwrap().0;
1129
1130        let match_trees = MatchTrees::build(&design);
1131        assert!(match_trees.roots == BTreeSet::from_iter([y1_cell]));
1132        assert!(match_trees.subtrees == BTreeMap::from_iter([((y1_cell, 0), y2_cell)]));
1133    }
1134
1135    #[test]
1136    fn test_match_tree_build_root_subtrees_disjoint() {
1137        let mut design = Design::new();
1138        let a = design.add_input("a", 1);
1139        let y1 = design.add_match(MatchCell {
1140            value: a.clone(),
1141            enable: Net::ONE,
1142            patterns: vec![vec![Const::lit("0")], vec![Const::lit("1")]],
1143        });
1144        let y2 = design.add_match(MatchCell { value: a.clone(), enable: y1[0], patterns: vec![vec![Const::lit("0")]] });
1145        let y3 = design.add_match(MatchCell { value: a, enable: y1[1], patterns: vec![vec![Const::lit("0")]] });
1146        design.apply();
1147
1148        let y1_cell = design.find_cell(y1[0]).unwrap().0;
1149        let y2_cell = design.find_cell(y2[0]).unwrap().0;
1150        let y3_cell = design.find_cell(y3[0]).unwrap().0;
1151
1152        let match_trees = MatchTrees::build(&design);
1153        assert!(match_trees.roots == BTreeSet::from_iter([y1_cell]));
1154        assert!(match_trees.subtrees == BTreeMap::from_iter([((y1_cell, 0), y2_cell), ((y1_cell, 1), y3_cell)]));
1155    }
1156
1157    #[test]
1158    fn test_match_tree_build_root_subtrees_rerooted() {
1159        let mut design = Design::new();
1160        let a = design.add_input("a", 1);
1161        let y1 =
1162            design.add_match(MatchCell { value: a.clone(), enable: Net::ONE, patterns: vec![vec![Const::lit("0")]] });
1163        let y2 = design.add_match(MatchCell { value: a.clone(), enable: y1[0], patterns: vec![vec![Const::lit("0")]] });
1164        let y3 = design.add_match(MatchCell { value: a, enable: y1[0], patterns: vec![vec![Const::lit("1")]] });
1165        design.apply();
1166
1167        let y1_cell = design.find_cell(y1[0]).unwrap().0;
1168        let y2_cell = design.find_cell(y2[0]).unwrap().0;
1169        let y3_cell = design.find_cell(y3[0]).unwrap().0;
1170
1171        let match_trees = MatchTrees::build(&design);
1172        assert!(match_trees.roots == BTreeSet::from_iter([y1_cell, y2_cell, y3_cell]));
1173        assert!(match_trees.subtrees == BTreeMap::from_iter([]));
1174    }
1175
1176    #[test]
1177    fn test_match_cell_into_matrix_flat() {
1178        let mut design = Design::new();
1179        let a = design.add_input("a", 3);
1180        let y = design.add_match(MatchCell {
1181            value: a.clone(),
1182            enable: Net::ONE,
1183            patterns: vec![vec![Const::lit("000"), Const::lit("111")], vec![Const::lit("010")]],
1184        });
1185        let yy = design.add_buf(&y);
1186        design.add_output("y", &yy);
1187        design.apply();
1188
1189        let y_cell = design.find_cell(y[0]).unwrap().0;
1190        let mut match_cells = Vec::new();
1191        let m = MatchTrees::build(&design).cell_into_matrix(y_cell, &mut match_cells);
1192        assert_eq!(match_cells.len(), 1);
1193        assert_eq!(match_cells[0].output(), y);
1194        design.apply();
1195
1196        let yy_cell = design.find_cell(yy[0]).unwrap().0;
1197        let Cell::Buf(y) = &*yy_cell.get() else { unreachable!() };
1198        assert_eq!(m.value, a);
1199        assert_eq!(m.rows, vec![
1200            MatchRow::new(Const::lit("000"), [y[0]]),
1201            MatchRow::new(Const::lit("111"), [y[0]]),
1202            MatchRow::new(Const::lit("010"), [y[1]]),
1203            MatchRow::new(Const::lit("XXX"), []),
1204        ]);
1205    }
1206
1207    #[test]
1208    fn test_match_cell_into_matrix_nested() {
1209        let mut design = Design::new();
1210        let a = design.add_input("a", 3);
1211        let b = design.add_input("b", 2);
1212        let ya = design.add_match(MatchCell {
1213            value: a.clone(),
1214            enable: Net::ONE,
1215            patterns: vec![vec![Const::lit("000"), Const::lit("111")], vec![Const::lit("010")]],
1216        });
1217        let yb = design.add_match(MatchCell {
1218            value: b.clone(),
1219            enable: ya[1],
1220            patterns: vec![vec![Const::lit("00")], vec![Const::lit("11")]],
1221        });
1222        let yya = design.add_buf(&ya);
1223        let yyb = design.add_buf(&yb);
1224        design.add_output("ya", &yya);
1225        design.add_output("yb", &yyb);
1226        design.apply();
1227
1228        let ya_cell = design.find_cell(ya[0]).unwrap().0;
1229        let mut match_cells = Vec::new();
1230        let ml = MatchTrees::build(&design).cell_into_matrix(ya_cell, &mut match_cells);
1231        assert_eq!(match_cells.len(), 2);
1232        assert_eq!(match_cells[0].output(), ya);
1233        assert_eq!(match_cells[1].output(), yb);
1234        design.apply();
1235
1236        let ya_cell = design.find_cell(yya[0]).unwrap().0;
1237        let yb_cell = design.find_cell(yyb[0]).unwrap().0;
1238
1239        let Cell::Buf(ya) = &*ya_cell.get() else { unreachable!() };
1240        let Cell::Buf(yb) = &*yb_cell.get() else { unreachable!() };
1241        let mut mr = MatchMatrix::new(a.concat(b));
1242        mr.add(MatchRow::new(Const::lit("XX000"), [ya[0]]));
1243        mr.add(MatchRow::new(Const::lit("XX111"), [ya[0]]));
1244        mr.add(MatchRow::new(Const::lit("00010"), [ya[1], yb[0]]));
1245        mr.add(MatchRow::new(Const::lit("11010"), [ya[1], yb[1]]));
1246        mr.add(MatchRow::new(Const::lit("XX010"), [ya[1]]));
1247        mr.add(MatchRow::new(Const::lit("XXXXX"), []));
1248
1249        assert_eq!(ml, mr, "\n{ml} != \n{mr}");
1250    }
1251
1252    fn assign(value: impl Into<Value>, enable: impl Into<Net>, update: impl Into<Value>) -> AssignCell {
1253        AssignCell { value: value.into(), enable: enable.into(), update: update.into(), offset: 0 }
1254    }
1255
1256    #[test]
1257    fn test_assign_chains_build_1() {
1258        let mut design = Design::new();
1259        let x = design.add_input("x", 4);
1260        let _a1 = design.add_assign(assign(Value::zero(4), Net::ONE, x));
1261        design.apply();
1262
1263        let AssignChains { chains } = AssignChains::build(&design);
1264
1265        assert!(chains.is_empty());
1266    }
1267
1268    #[test]
1269    fn test_assign_chains_build_2() {
1270        let mut design = Design::new();
1271        let x = design.add_input("x", 4);
1272        let a1 = design.add_assign(assign(Value::zero(4), Net::ONE, x));
1273        let y = design.add_input("y", 4);
1274        let a2 = design.add_assign(assign(a1.clone(), Net::ONE, y));
1275        design.apply();
1276
1277        let a1_cell = design.find_cell(a1[0]).unwrap().0;
1278        let a2_cell = design.find_cell(a2[0]).unwrap().0;
1279        let AssignChains { chains } = AssignChains::build(&design);
1280
1281        assert!(chains == [vec![a1_cell, a2_cell]]);
1282    }
1283
1284    #[test]
1285    fn test_assign_chains_build_3_fork() {
1286        let mut design = Design::new();
1287        let x = design.add_input("x", 4);
1288        let a1 = design.add_assign(assign(Value::zero(4), Net::ONE, x));
1289        let y = design.add_input("y", 4);
1290        let _a2 = design.add_assign(assign(a1.clone(), Net::ONE, y));
1291        let z = design.add_input("z", 4);
1292        let _a3 = design.add_assign(assign(a1.clone(), Net::ONE, z));
1293        design.apply();
1294
1295        let AssignChains { chains } = AssignChains::build(&design);
1296
1297        assert!(chains.is_empty());
1298    }
1299
1300    #[test]
1301    fn test_assign_chains_build_partial_update() {
1302        let mut design = Design::new();
1303        let x = design.add_input("x", 4);
1304        let a1 = design.add_assign(assign(Value::zero(4), Net::ONE, x));
1305        let y = design.add_input("y", 3);
1306        let _a2 = design.add_assign(AssignCell { value: a1.clone(), enable: Net::ONE, update: y, offset: 1 });
1307        design.apply();
1308
1309        let AssignChains { chains } = AssignChains::build(&design);
1310
1311        assert!(chains.is_empty());
1312    }
1313
1314    #[test]
1315    fn test_assign_chains_build_partial_value() {
1316        let mut design = Design::new();
1317        let x = design.add_input("x", 4);
1318        let a1 = design.add_assign(assign(Value::zero(4), Net::ONE, x));
1319        let y = design.add_input("y", 3);
1320        let _a2 = design.add_assign(assign(a1.slice(..3), Net::ONE, y));
1321        design.apply();
1322
1323        let AssignChains { chains } = AssignChains::build(&design);
1324
1325        assert!(chains.is_empty());
1326    }
1327
1328    #[test]
1329    fn test_assign_lower_disjoint() {
1330        let mut dl = Design::new();
1331        let c = dl.add_input("c", 2);
1332        let m = dl.add_match(MatchCell {
1333            value: c.clone(),
1334            enable: Net::ONE,
1335            patterns: vec![
1336                vec![
1337                    Const::lit("00"), // x1
1338                    Const::lit("11"), // x1
1339                ],
1340                vec![Const::lit("01")], // x2
1341                vec![Const::lit("10")], // x3
1342            ],
1343        });
1344        let a1 = dl.add_assign(assign(Value::zero(4), m[0], dl.add_input("x1", 4)));
1345        let a2 = dl.add_assign(assign(a1, m[1], dl.add_input("x2", 4)));
1346        let a3 = dl.add_assign(assign(a2, m[2], dl.add_input("x3", 4)));
1347        dl.add_output("y", a3);
1348        dl.apply();
1349
1350        decision(&mut dl);
1351
1352        let mut dr = Design::new();
1353        let c = dr.add_input("c", 2);
1354        let x1 = dr.add_input("x1", 4);
1355        let x2 = dr.add_input("x2", 4);
1356        let x3 = dr.add_input("x3", 4);
1357        let m1 = dr.add_mux(c[1], &x3, &x1);
1358        let m2 = dr.add_mux(c[1], &x1, &x2);
1359        let m3 = dr.add_mux(c[0], m2, m1);
1360        dr.add_output("y", m3);
1361
1362        assert_isomorphic!(dl, dr);
1363    }
1364
1365    #[test]
1366    fn test_assign_lower_disjoint_partial() {
1367        let mut dl = Design::new();
1368        let c = dl.add_input("c", 2);
1369        let m = dl.add_match(MatchCell {
1370            value: c.clone(),
1371            enable: Net::ONE,
1372            patterns: vec![
1373                vec![
1374                    Const::lit("00"), // x1
1375                    Const::lit("11"), // x1
1376                ],
1377                vec![Const::lit("01")], // x2
1378                vec![Const::lit("10")], // x3
1379            ],
1380        });
1381        let a1 = dl.add_assign(assign(Value::zero(4), m[0], dl.add_input("x1", 4)));
1382        let a2 = dl.add_assign(assign(a1, m[1], dl.add_input("x2", 4)));
1383        let a3 = dl.add_assign(assign(a2, m[2], dl.add_input("x3", 3)));
1384        dl.add_output("y", a3);
1385        dl.apply();
1386
1387        decision(&mut dl);
1388        // the particular output generated here is uninteresting, assert that
1389        // lowering doesn't panic and is accepted by SMT
1390    }
1391
1392    #[test]
1393    fn test_assign_lower_disjoint_child() {
1394        let mut dl = Design::new();
1395        let c1 = dl.add_input("c1", 1);
1396        let m1 = dl.add_match(MatchCell {
1397            value: c1,
1398            enable: Net::ONE,
1399            patterns: vec![
1400                vec![Const::lit("0")], // m2
1401                vec![Const::lit("1")], // x2
1402            ],
1403        });
1404
1405        let c2 = dl.add_input("c2", 2);
1406        let m2 = dl.add_match(MatchCell {
1407            value: c2,
1408            enable: m1[0],
1409            patterns: vec![
1410                vec![Const::lit("01")], // x1
1411            ],
1412        });
1413
1414        let a1 = dl.add_assign(assign(Value::zero(4), m2[0], dl.add_input("x1", 4)));
1415        let a2 = dl.add_assign(assign(a1, m1[1], dl.add_input("x2", 4)));
1416        dl.add_output("y", a2);
1417        dl.apply();
1418
1419        decision(&mut dl);
1420
1421        let mut dr = Design::new();
1422        let c1 = dr.add_input("c1", 1);
1423        let c2 = dr.add_input("c2", 2);
1424        let x1 = dr.add_input("x1", 4);
1425        let x2 = dr.add_input("x2", 4);
1426        let m1 = dr.add_mux(c2[1], Value::zero(4), &x1);
1427        let m2 = dr.add_mux(c2[0], &m1, Value::zero(4));
1428        let m3 = dr.add_mux(c1[0], &x2, &m2);
1429        dr.add_output("y", m3);
1430
1431        assert_isomorphic!(dl, dr);
1432    }
1433
1434    #[test]
1435    fn test_assign_lower_overlapping() {
1436        let mut dl = Design::new();
1437        let c = dl.add_input("c", 1);
1438        let m = dl.add_match(MatchCell {
1439            value: c.clone(),
1440            enable: Net::ONE,
1441            patterns: vec![vec![Const::lit("0")], vec![Const::lit("1")]],
1442        });
1443        let a1 = dl.add_assign(assign(Value::zero(4), m[0], dl.add_input("x1", 4)));
1444        let a2 = dl.add_assign(assign(a1, m[1], dl.add_input("x2", 4)));
1445        let a3 = dl.add_assign(assign(a2, m[1], dl.add_input("x3", 4)));
1446        dl.add_output("y", a3);
1447        dl.apply();
1448
1449        decision(&mut dl);
1450
1451        let mut dr = Design::new();
1452        let c = dr.add_input1("c");
1453        let x1 = dr.add_input("x1", 4);
1454        let x2 = dr.add_input("x2", 4);
1455        let x3 = dr.add_input("x3", 4);
1456        let mc = dr.add_mux(c, Const::lit("10"), Const::lit("01"));
1457        let m2 = dr.add_mux(c, x2, x1);
1458        let m3 = dr.add_mux(mc[1], x3, m2);
1459        dr.add_output("y", m3);
1460
1461        assert_isomorphic!(dl, dr);
1462    }
1463
1464    #[test]
1465    fn test_assign_lower_different_matches() {
1466        let mut dl = Design::new();
1467        let c1 = dl.add_input("c1", 1);
1468        let c2 = dl.add_input("c2", 1);
1469        let m1 = dl.add_match(MatchCell { value: c1, enable: Net::ONE, patterns: vec![vec![Const::lit("0")]] });
1470        let m2 = dl.add_match(MatchCell { value: c2, enable: Net::ONE, patterns: vec![vec![Const::lit("0")]] });
1471        let a1 = dl.add_assign(assign(Value::zero(4), m1[0], dl.add_input("x1", 4)));
1472        let a2 = dl.add_assign(assign(a1, m2[0], dl.add_input("x2", 4)));
1473        dl.add_output("y", a2);
1474        dl.apply();
1475
1476        decision(&mut dl);
1477
1478        let mut dr = Design::new();
1479        let c1 = dr.add_input1("c1");
1480        let c2 = dr.add_input1("c2");
1481        let mc2 = dr.add_mux(c2, Const::lit("0"), Const::lit("1"));
1482        let m1 = dr.add_mux(c1, Value::zero(4), dr.add_input("x1", 4));
1483        let m2 = dr.add_mux(mc2[0], dr.add_input("x2", 4), m1);
1484        dr.add_output("y", m2);
1485
1486        assert_isomorphic!(dl, dr);
1487    }
1488
1489    #[test]
1490    fn test_assign_lower_partial() {
1491        let mut dl = Design::new();
1492        let en = dl.add_input1("en");
1493        let assign = dl.add_assign(AssignCell {
1494            value: dl.add_input("value", 6),
1495            enable: en,
1496            update: dl.add_input("update", 3),
1497            offset: 2,
1498        });
1499        dl.add_output("assign", assign);
1500        dl.apply();
1501
1502        decision(&mut dl);
1503
1504        let mut dr = Design::new();
1505        let en = dr.add_input1("en");
1506        let value = dr.add_input("value", 6);
1507        let update = dr.add_input("update", 3);
1508        let mux = dr.add_mux(en, update, value.slice(2..5));
1509        dr.add_output("assign", value.slice(..2).concat(mux.concat(value.slice(5..))));
1510
1511        assert_isomorphic!(dl, dr);
1512    }
1513
1514    #[test]
1515    fn test_match_eq_refinement() {
1516        let mut design = Design::new();
1517        let a = design.add_input("a", 2);
1518        let m = design.add_match(MatchCell {
1519            value: a,
1520            enable: Net::ONE,
1521            patterns: vec![vec![Const::lit("00")], vec![Const::lit("XX")]],
1522        });
1523        design.add_output("y", m);
1524        design.apply();
1525
1526        decision(&mut design);
1527        // the particular output generated here is uninteresting, assert that
1528        // lowering doesn't panic and is accepted by SMT
1529    }
1530}
prjunnamed_generic/decision.rs

prjunnamed_generic/
decision.rs
