safety_net/
graph.rs

1/*!
2
3  Graph utils for the `graph` module.
4
5*/
6
7use crate::circuit::{Instantiable, Net};
8use crate::error::Error;
9#[cfg(feature = "graph")]
10use crate::netlist::Connection;
11use crate::netlist::{DrivenNet, InputPort, NetRef, Netlist};
12#[cfg(feature = "graph")]
13use petgraph::graph::DiGraph;
14use std::cmp::Reverse;
15use std::collections::{BinaryHeap, HashMap, HashSet};
16
17/// A common trait of analyses than can be performed on a netlist.
18/// An analysis becomes stale when the netlist is modified.
19pub trait Analysis<'a, I: Instantiable>
20where
21    Self: Sized + 'a,
22{
23    /// Construct the analysis to the current state of the netlist.
24    fn build(netlist: &'a Netlist<I>) -> Result<Self, Error>;
25}
26
27/// A table that maps nets to the circuit nodes they drive
28pub struct FanOutTable<'a, I: Instantiable> {
29    /// A reference to the underlying netlist
30    _netlist: &'a Netlist<I>,
31    /// Maps a net to the list of nodes it drives
32    net_fan_out: HashMap<Net, Vec<NetRef<I>>>,
33    /// Maps a driven net to a list of inputs it drives
34    dnet_fan_out: HashMap<DrivenNet<I>, Vec<InputPort<I>>>,
35    /// Maps a node to the list of nodes it drives
36    node_fan_out: HashMap<NetRef<I>, Vec<NetRef<I>>>,
37    /// The number of references held by all the  data structures
38    ref_count: HashMap<NetRef<I>, usize>,
39    /// Contains nets which are outputs
40    is_an_output: HashSet<Net>,
41}
42
43impl<I> FanOutTable<'_, I>
44where
45    I: Instantiable,
46{
47    /// Returns an iterator to the circuit nodes that use `net`.
48    pub fn get_net_users(&self, net: &Net) -> impl Iterator<Item = NetRef<I>> {
49        self.net_fan_out
50            .get(net)
51            .into_iter()
52            .flat_map(|users| users.iter().cloned())
53    }
54
55    /// Returns an iterator to the circuit nodes that use `node`.
56    pub fn get_node_users(&self, node: &NetRef<I>) -> impl Iterator<Item = NetRef<I>> {
57        self.node_fan_out
58            .get(node)
59            .into_iter()
60            .flat_map(|users| users.iter().cloned())
61    }
62
63    /// Returns an iterator to the uses of `net`.
64    pub fn get_users(&self, net: &DrivenNet<I>) -> impl Iterator<Item = InputPort<I>> {
65        self.dnet_fan_out
66            .get(net)
67            .into_iter()
68            .flat_map(|users| users.iter().cloned())
69    }
70
71    /// Get the number of reference held by this table
72    pub fn get_ref_count(&self, node: &NetRef<I>) -> usize {
73        self.ref_count.get(node).copied().unwrap_or(0)
74    }
75
76    /// Returns `true` if the net has any used by any cells in the circuit
77    /// This does incude nets that are only used as outputs.
78    pub fn net_has_uses(&self, net: &Net) -> bool {
79        (self.net_fan_out.contains_key(net) && !self.net_fan_out[net].is_empty())
80            || self.is_an_output.contains(net)
81    }
82
83    /// Returns `true` if the net has any uses  in the circuit
84    pub fn has_uses(&self, net: &DrivenNet<I>) -> bool {
85        net.is_top_level_output()
86            || (self.dnet_fan_out.contains_key(net) && !self.dnet_fan_out[net].is_empty())
87    }
88}
89
90impl<'a, I> Analysis<'a, I> for FanOutTable<'a, I>
91where
92    I: Instantiable,
93{
94    fn build(netlist: &'a Netlist<I>) -> Result<Self, Error> {
95        let mut net_fan_out: HashMap<Net, Vec<NetRef<I>>> = HashMap::new();
96        let mut dnet_fan_out: HashMap<DrivenNet<I>, Vec<InputPort<I>>> = HashMap::new();
97        let mut node_fan_out: HashMap<NetRef<I>, Vec<NetRef<I>>> = HashMap::new();
98        let mut is_an_output: HashSet<Net> = HashSet::new();
99        let mut ref_count: HashMap<NetRef<I>, usize> = HashMap::new();
100
101        // We can only build the fanout table if netlist is mostly intact
102        if let Err(e) = netlist.verify()
103            && matches!(
104                e,
105                Error::NonuniqueNets(_) | Error::NonuniqueInsts(_) | Error::InstantiableError(_)
106            )
107        {
108            return Err(e);
109        }
110
111        for c in netlist.connections() {
112            let e = net_fan_out.entry(c.net()).or_default();
113            e.push(c.target().unwrap());
114
115            let e = dnet_fan_out.entry(c.src()).or_default();
116            e.push(c.target());
117
118            let e = node_fan_out.entry(c.src().unwrap()).or_default();
119            e.push(c.target().unwrap());
120        }
121
122        for (o, n) in netlist.outputs() {
123            is_an_output.insert(o.as_net().clone());
124            is_an_output.insert(n);
125        }
126
127        for v in net_fan_out.values() {
128            for nr in v {
129                *ref_count.entry(nr.clone()).or_insert(1) += 1;
130            }
131        }
132
133        for (k, v) in &dnet_fan_out {
134            for nr in v {
135                *ref_count.entry(nr.clone().unwrap()).or_insert(1) += 1;
136            }
137            *ref_count.entry(k.clone().unwrap()).or_insert(1) += 1;
138        }
139
140        for (k, v) in &node_fan_out {
141            for nr in v {
142                *ref_count.entry(nr.clone()).or_insert(1) += 1;
143            }
144            *ref_count.entry(k.clone()).or_insert(1) += 1;
145        }
146
147        Ok(FanOutTable {
148            _netlist: netlist,
149            net_fan_out,
150            dnet_fan_out,
151            node_fan_out,
152            is_an_output,
153            ref_count,
154        })
155    }
156}
157
158/// A simple example to analyze the logic levels of a netlist.
159/// This analysis checks for cycles, but it doesn't check for registers.
160/// Result of combinational depth analysis for a single net.
161#[derive(Debug, Copy, Clone, PartialEq, Eq)]
162pub enum CombDepthResult {
163    /// Signal has no driver
164    Undefined,
165    /// Signal is along a cycle
166    CombCycle,
167    /// Integer logic level
168    Depth(usize),
169}
170
171/// Computes the combinational depth of each net in a netlist.
172///
173/// Each net is classified as having a defined depth, being undefined,
174/// or participating in a combinational cycle.
175pub struct CombDepthInfo<'a, I: Instantiable> {
176    _netlist: &'a Netlist<I>,
177    /// The total distance from a sequential element
178    results: HashMap<NetRef<I>, CombDepthResult>,
179    /// The critical predecessor to the node
180    critical_par: HashMap<NetRef<I>, InputPort<I>>,
181    /// Critical endpoints to build paths from
182    critical_ends: BinaryHeap<(Reverse<usize>, NetRef<I>)>,
183    /// Max will be `None` if the entire circuit is part of a combinational cycle or has undriven elements
184    max_depth: Option<usize>,
185}
186
187impl<I> CombDepthInfo<'_, I>
188where
189    I: Instantiable,
190{
191    /// Max number of critical endpoints to keep in the heap.
192    const SIZE_HEAP: usize = 10;
193
194    /// Returns the logic level of a node in the circuit.
195    pub fn get_comb_depth(&self, node: &NetRef<I>) -> Option<CombDepthResult> {
196        self.results.get(node).copied()
197    }
198
199    /// Returns the critical input port
200    pub fn get_crit_input(&self, node: &NetRef<I>) -> Option<&InputPort<I>> {
201        self.critical_par.get(node)
202    }
203
204    /// Returns the most critical endpoints in the circuit
205    pub fn get_critical_points(&self) -> impl IntoIterator<Item = DrivenNet<I>> {
206        let mut v = self.critical_ends.iter().collect::<Vec<_>>();
207        v.sort_by_key(|(d, _)| *d);
208        v.into_iter().flat_map(|(_, n)| n.outputs())
209    }
210
211    /// Builds the most critical path
212    pub fn build_critical_path(&self) -> Option<Vec<DrivenNet<I>>> {
213        let mut path = Vec::new();
214        let mut current = self.get_critical_points().into_iter().next()?;
215        while let Some(crit) = self.critical_par.get(&current.clone().unwrap()) {
216            path.push(current.clone());
217            current = self
218                ._netlist
219                .get_driver(current.unwrap(), crit.get_input_num())
220                .unwrap();
221        }
222        path.push(current);
223        Some(path)
224    }
225
226    /// Returns the maximum logic level of the circuit.
227    pub fn get_max_depth(&self) -> Option<usize> {
228        self.max_depth
229    }
230}
231
232impl<'a, I> Analysis<'a, I> for CombDepthInfo<'a, I>
233where
234    I: Instantiable,
235{
236    fn build(netlist: &'a Netlist<I>) -> Result<Self, Error> {
237        let mut results: HashMap<NetRef<I>, CombDepthResult> = HashMap::new();
238        let mut critical_par: HashMap<NetRef<I>, InputPort<I>> = HashMap::new();
239        let mut critical_ends: BinaryHeap<(_, NetRef<I>)> = BinaryHeap::new();
240        let mut visiting: HashSet<NetRef<I>> = HashSet::new();
241        let mut max_depth: Option<usize> = None;
242
243        fn compute<I: Instantiable>(
244            node: NetRef<I>,
245            netlist: &Netlist<I>,
246            results: &mut HashMap<NetRef<I>, CombDepthResult>,
247            critical_par: &mut HashMap<NetRef<I>, InputPort<I>>,
248            visiting: &mut HashSet<NetRef<I>>,
249        ) -> CombDepthResult {
250            // Memoized result
251            if let Some(&r) = results.get(&node) {
252                return r;
253            }
254
255            // Cycle detection
256            if visiting.contains(&node) {
257                for n in visiting.iter() {
258                    results.insert(n.clone(), CombDepthResult::CombCycle);
259                }
260                return CombDepthResult::CombCycle;
261            }
262
263            // Input nodes and reg have depth 0
264            if node.is_an_input() || node.get_instance_type().is_some_and(|inst| inst.is_seq()) {
265                let r = CombDepthResult::Depth(0);
266                results.insert(node.clone(), r);
267                return r;
268            }
269
270            visiting.insert(node.clone());
271
272            let mut max_depth = 0;
273            let mut crit: Option<InputPort<I>> = None;
274            let mut is_undefined = false;
275
276            for i in 0..node.get_num_input_ports() {
277                let driver = match netlist.get_driver(node.clone(), i) {
278                    Some(d) => d.unwrap(),
279                    None => {
280                        is_undefined = true;
281                        continue;
282                    }
283                };
284
285                if let Some(inst) = driver.get_instance_type()
286                    && inst.is_seq()
287                {
288                    continue;
289                }
290
291                match compute(driver, netlist, results, critical_par, visiting) {
292                    CombDepthResult::Depth(d) => {
293                        if d > max_depth {
294                            max_depth = d;
295                            crit = Some(node.get_input(i));
296                        }
297                    }
298                    CombDepthResult::Undefined => {
299                        is_undefined = true;
300                    }
301                    CombDepthResult::CombCycle => {
302                        let r = CombDepthResult::CombCycle;
303                        results.insert(node.clone(), r);
304                        visiting.remove(&node);
305                        return r;
306                    }
307                }
308            }
309
310            visiting.remove(&node);
311            let r = if is_undefined {
312                CombDepthResult::Undefined
313            } else {
314                if let Some(crit) = crit {
315                    critical_par.insert(node.clone(), crit);
316                }
317                let d = max_depth + 1;
318                CombDepthResult::Depth(d)
319            };
320            results.insert(node.clone(), r);
321            r
322        }
323
324        for (driven, _) in netlist.outputs() {
325            let node = driven.unwrap();
326            let r = compute(
327                node.clone(),
328                netlist,
329                &mut results,
330                &mut critical_par,
331                &mut visiting,
332            );
333
334            if let CombDepthResult::Depth(d) = r {
335                critical_ends.push((Reverse(d), node));
336                if critical_ends.len() > CombDepthInfo::<I>::SIZE_HEAP {
337                    critical_ends.pop();
338                }
339                max_depth = Some(max_depth.map_or(d, |m| m.max(d)));
340            }
341        }
342
343        for node in netlist.matches(|inst| inst.is_seq()) {
344            compute(
345                node.clone(),
346                netlist,
347                &mut results,
348                &mut critical_par,
349                &mut visiting,
350            );
351            for i in 0..node.get_num_input_ports() {
352                if let Some(driver) = netlist.get_driver(node.clone(), i) {
353                    if driver.get_instance_type().is_some_and(|inst| inst.is_seq()) {
354                        continue;
355                    }
356
357                    let r = compute(
358                        driver.clone().unwrap(),
359                        netlist,
360                        &mut results,
361                        &mut critical_par,
362                        &mut visiting,
363                    );
364                    if let CombDepthResult::Depth(d) = r {
365                        critical_ends.push((Reverse(d), driver.unwrap()));
366                        if critical_ends.len() > CombDepthInfo::<I>::SIZE_HEAP {
367                            critical_ends.pop();
368                        }
369                        max_depth = Some(max_depth.map_or(d, |m| m.max(d)));
370                    }
371                }
372            }
373        }
374
375        Ok(CombDepthInfo {
376            _netlist: netlist,
377            results,
378            critical_par,
379            critical_ends,
380            max_depth,
381        })
382    }
383}
384
385/// An enum to provide pseudo-nodes for any misc user-programmable behavior.
386#[cfg(feature = "graph")]
387#[derive(Debug, Clone)]
388pub enum Node<I: Instantiable, T: Clone + std::fmt::Debug + std::fmt::Display> {
389    /// A 'real' circuit node
390    NetRef(NetRef<I>),
391    /// Any other user-programmable node
392    Pseudo(T),
393}
394
395#[cfg(feature = "graph")]
396impl<I, T> std::fmt::Display for Node<I, T>
397where
398    I: Instantiable,
399    T: Clone + std::fmt::Debug + std::fmt::Display,
400{
401    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
402        match self {
403            Node::NetRef(nr) => nr.fmt(f),
404            Node::Pseudo(t) => std::fmt::Display::fmt(t, f),
405        }
406    }
407}
408
409/// An enum to provide pseudo-edges for any misc user-programmable behavior.
410#[cfg(feature = "graph")]
411#[derive(Debug, Clone)]
412pub enum Edge<I: Instantiable, T: Clone + std::fmt::Debug + std::fmt::Display> {
413    /// A 'real' circuit connection
414    Connection(Connection<I>),
415    /// Any other user-programmable node
416    Pseudo(T),
417}
418
419#[cfg(feature = "graph")]
420impl<I, T> std::fmt::Display for Edge<I, T>
421where
422    I: Instantiable,
423    T: Clone + std::fmt::Debug + std::fmt::Display,
424{
425    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
426        match self {
427            Edge::Connection(c) => c.fmt(f),
428            Edge::Pseudo(t) => std::fmt::Display::fmt(t, f),
429        }
430    }
431}
432
433/// Returns a petgraph representation of the netlist as a directed multi-graph with type [DiGraph<Object, NetLabel>].
434#[cfg(feature = "graph")]
435pub struct MultiDiGraph<'a, I: Instantiable> {
436    _netlist: &'a Netlist<I>,
437    graph: DiGraph<Node<I, String>, Edge<I, Net>>,
438}
439
440#[cfg(feature = "graph")]
441impl<'a, I> MultiDiGraph<'a, I>
442where
443    I: Instantiable,
444{
445    /// Create a new petgraph representation of the netlist
446    pub fn new(netlist: &'a Netlist<I>) -> Self {
447        let mut mapping = HashMap::new();
448        let mut graph = DiGraph::new();
449
450        for obj in netlist.objects() {
451            let id = graph.add_node(Node::NetRef(obj.clone()));
452            mapping.insert(obj, id);
453        }
454
455        for connection in netlist.connections() {
456            let source = connection.src().unwrap();
457            let target = connection.target().unwrap();
458            let s_id = mapping[&source];
459            let t_id = mapping[&target];
460            graph.add_edge(s_id, t_id, Edge::Connection(connection));
461        }
462
463        // Finally, add the output connections
464        for (o, n) in netlist.outputs() {
465            let s_id = mapping[&o.clone().unwrap()];
466            let t_id = graph.add_node(Node::Pseudo(format!("Output({n})")));
467            graph.add_edge(s_id, t_id, Edge::Pseudo(o.as_net().clone()));
468        }
469
470        Self {
471            _netlist: netlist,
472            graph,
473        }
474    }
475
476    /// Return a reference to the graph constructed by this analysis
477    pub fn get_graph(&self) -> &DiGraph<Node<I, String>, Edge<I, Net>> {
478        &self.graph
479    }
480
481    /// Iterates through a [greedy feedback arc set](https://doi.org/10.1016/0020-0190(93)90079-O) for the graph.
482    pub fn greedy_feedback_arcs(&self) -> impl Iterator<Item = Connection<I>> {
483        petgraph::algo::feedback_arc_set::greedy_feedback_arc_set(&self.graph)
484            .map(|e| match e.weight() {
485                Edge::Connection(c) => c,
486                _ => unreachable!("Outputs should be sinks"),
487            })
488            .cloned()
489    }
490
491    /// Returns all the circuit nodes sorted into their strongly connected components.
492    pub fn sccs(&self) -> Vec<Vec<NetRef<I>>> {
493        let mut res = Vec::new();
494        for scc in petgraph::algo::tarjan_scc(&self.graph) {
495            let c: Vec<NetRef<I>> = scc
496                .into_iter()
497                .filter_map(|i| match &self.graph[i] {
498                    Node::NetRef(nr) => Some(nr.clone()),
499                    _ => None,
500                })
501                .collect();
502            if !c.is_empty() {
503                res.push(c);
504            }
505        }
506        res
507    }
508}
509
510#[cfg(feature = "graph")]
511impl<'a, I> Analysis<'a, I> for MultiDiGraph<'a, I>
512where
513    I: Instantiable,
514{
515    fn build(netlist: &'a Netlist<I>) -> Result<Self, Error> {
516        Ok(Self::new(netlist))
517    }
518}
519
520#[cfg(test)]
521mod tests {
522    use super::*;
523    use crate::{format_id, netlist::*};
524
525    fn full_adder() -> Gate {
526        Gate::new_logical_multi(
527            "FA".into(),
528            vec!["CIN".into(), "A".into(), "B".into()],
529            vec!["S".into(), "COUT".into()],
530        )
531    }
532
533    fn ripple_adder() -> GateNetlist {
534        let netlist = Netlist::new("ripple_adder".into());
535        let bitwidth = 4;
536
537        // Add the the inputs
538        let a = netlist.insert_input_logic_bus("a".to_string(), bitwidth);
539        let b = netlist.insert_input_logic_bus("b".to_string(), bitwidth);
540        let mut carry: DrivenNet<Gate> = netlist.insert_input("cin".into());
541
542        for (i, (a, b)) in a.into_iter().zip(b).enumerate() {
543            // Instantiate a full adder for each bit
544            let fa = netlist
545                .insert_gate(full_adder(), format_id!("fa_{i}"), &[carry, a, b])
546                .unwrap();
547
548            // Expose the sum
549            fa.expose_net(&fa.get_net(0)).unwrap();
550
551            carry = fa.find_output(&"COUT".into()).unwrap();
552
553            if i == bitwidth - 1 {
554                // Last full adder, expose the carry out
555                fa.get_output(1).expose_with_name("cout".into()).unwrap();
556            }
557        }
558
559        netlist.reclaim().unwrap()
560    }
561
562    #[test]
563    fn fanout_table() {
564        let netlist = ripple_adder();
565        let analysis = FanOutTable::build(&netlist);
566        assert!(analysis.is_ok());
567        let analysis = analysis.unwrap();
568        assert!(netlist.verify().is_ok());
569
570        for item in netlist.objects().filter(|o| !o.is_an_input()) {
571            // Sum bit has no users (it is a direct output)
572            assert!(
573                analysis
574                    .get_net_users(&item.find_output(&"S".into()).unwrap().as_net())
575                    .next()
576                    .is_none(),
577                "Sum bit should not have users"
578            );
579
580            assert!(
581                item.get_instance_name().is_some(),
582                "Item should have a name. Filtered inputs"
583            );
584
585            let net = item.find_output(&"COUT".into()).unwrap().as_net().clone();
586            let mut cout_users = analysis.get_net_users(&net);
587            if item.get_instance_name().unwrap().to_string() != "fa_3" {
588                assert!(cout_users.next().is_some(), "Carry bit should have users");
589            }
590
591            assert!(
592                cout_users.next().is_none(),
593                "Carry bit should have 1 or 0 user"
594            );
595        }
596    }
597}
safety_net/graph.rs

safety_net/
graph.rs
