xlsynth_g8r/transforms/
transform_trait.rs

1// SPDX-License-Identifier: Apache-2.0
2
3use crate::aig::gate::PirNodeIds;
4use crate::aig::{AigOperand, AigRef, GateFn};
5use anyhow::Result;
6use std::fmt::{self, Debug};
7
8/// Enum representing the different kinds of transformations that can be
9/// applied.
10#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
11pub enum TransformKind {
12    SwapOperands,
13    ToggleOutputBit,
14    DoubleNegate,
15    InsertRedundantAnd,
16    RemoveRedundantAnd,
17    DuplicateGate,
18    UnduplicateGate,
19    InsertFalseAnd,
20    RemoveFalseAnd,
21    InsertTrueAnd,
22    RemoveTrueAnd,
23    SwapOutputBits,
24    RotateAndRight,
25    RotateAndLeft,
26    AndAbsorbRight,
27    AndAbsorbLeft,
28    BalanceAndTree,
29    UnbalanceAndTree,
30    ToggleOperandNegation,
31    RewireOperand,
32    PushNegation,
33    MergeEquivLeaves,
34    SplitFanout,
35    MergeFanout,
36    FactorSharedAnd,
37    UnfactorSharedAnd,
38}
39
40impl fmt::Display for TransformKind {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        match self {
43            TransformKind::SwapOperands => write!(f, "SwapOp"),
44            TransformKind::ToggleOutputBit => write!(f, "ToggleOut"),
45            TransformKind::DoubleNegate => write!(f, "DblNeg"),
46            TransformKind::InsertRedundantAnd => write!(f, "InsRedAnd"),
47            TransformKind::RemoveRedundantAnd => write!(f, "RemRedAnd"),
48            TransformKind::DuplicateGate => write!(f, "DupGate"),
49            TransformKind::UnduplicateGate => write!(f, "UndupGate"),
50            TransformKind::InsertFalseAnd => write!(f, "InsFalseAnd"),
51            TransformKind::RemoveFalseAnd => write!(f, "RemFalseAnd"),
52            TransformKind::InsertTrueAnd => write!(f, "InsTrueAnd"),
53            TransformKind::RemoveTrueAnd => write!(f, "RemTrueAnd"),
54            TransformKind::SwapOutputBits => write!(f, "SwapOutBits"),
55            TransformKind::RotateAndRight => write!(f, "RotAndR"),
56            TransformKind::RotateAndLeft => write!(f, "RotAndL"),
57            TransformKind::AndAbsorbRight => write!(f, "AbsorbR"),
58            TransformKind::AndAbsorbLeft => write!(f, "AbsorbL"),
59            TransformKind::BalanceAndTree => write!(f, "BalTree"),
60            TransformKind::UnbalanceAndTree => write!(f, "UnbalTree"),
61            TransformKind::ToggleOperandNegation => write!(f, "TogOpNeg"),
62            TransformKind::RewireOperand => write!(f, "RewireOp"),
63            TransformKind::PushNegation => write!(f, "PushNeg"),
64            TransformKind::MergeEquivLeaves => write!(f, "MergeLeaves"),
65            TransformKind::SplitFanout => write!(f, "SplitFan"),
66            TransformKind::MergeFanout => write!(f, "MergeFan"),
67            TransformKind::FactorSharedAnd => write!(f, "FactorAnd"),
68            TransformKind::UnfactorSharedAnd => write!(f, "UnfactorAnd"),
69        }
70    }
71}
72
73/// Enum to specify the direction of transformation.
74#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
75pub enum TransformDirection {
76    Forward,
77    Backward,
78}
79
80/// Represents a specific location in the GateFn where a transform can be
81/// applied.
82#[derive(Debug, Clone)]
83pub enum TransformLocation {
84    Node(AigRef),
85    Operand(AigRef, bool),
86    OutputPortBit {
87        output_idx: usize,
88        bit_idx: usize,
89    },
90    OperandReplacement {
91        parent: AigRef,
92        is_rhs: bool,
93        old_op: AigOperand,
94        new_op: AigOperand,
95    },
96    SwapOutputBits {
97        out_a_idx: usize,
98        bit_a_idx: usize,
99        out_b_idx: usize,
100        bit_b_idx: usize,
101    },
102    OperandTarget {
103        parent: AigRef,
104        is_rhs: bool,
105        old_op: AigOperand,
106    },
107    FanoutEdge {
108        parent: AigRef,
109        child: AigRef,
110    },
111}
112
113/// Defines a reversible transformation that can be applied to a `GateFn`.
114pub trait Transform: Debug + Send + Sync {
115    /// Returns the specific `TransformKind` that this trait object represents.
116    fn kind(&self) -> TransformKind;
117
118    /// Returns a human-readable display name for this transform.
119    /// Defaults to the `Display` implementation of `TransformKind`.
120    fn display_name(&self) -> String {
121        format!("{:?}", self.kind())
122    }
123
124    /// Finds all possible application sites for this transform in the given
125    /// GateFn for the specified direction.
126    fn find_candidates(
127        &mut self,
128        g: &GateFn,
129        direction: TransformDirection,
130    ) -> Vec<TransformLocation>;
131
132    /// Applies the transform to the GateFn at the given candidate site
133    /// in the specified direction.
134    /// The MCMC loop is expected to pass a clone of the GateFn if rejection
135    /// implies reverting to the prior state.
136    fn apply(
137        &self,
138        g: &mut GateFn,
139        candidate_location: &TransformLocation,
140        direction: TransformDirection,
141    ) -> Result<()>;
142
143    /// Indicates whether this transform is always semantics preserving.
144    /// When `true`, applying the transform cannot change the functional
145    /// behaviour of the circuit, so equivalence checks can be skipped.
146    fn always_equivalent(&self) -> bool;
147}
148
149/// Collects the sorted, deduplicated provenance IDs from the given source
150/// nodes.
151pub(crate) fn collect_node_provenance(g: &GateFn, source_refs: &[AigRef]) -> PirNodeIds {
152    let mut pir_node_ids = PirNodeIds::new();
153    for source_ref in source_refs {
154        for pir_node_id in g.gates[source_ref.id].get_pir_node_ids() {
155            match pir_node_ids.binary_search(pir_node_id) {
156                Ok(_) => {}
157                Err(index) => pir_node_ids.insert(index, *pir_node_id),
158            }
159        }
160    }
161    pir_node_ids
162}
163
164/// Unions the provenance of the source nodes onto the destination node.
165pub(crate) fn union_node_provenance_into_node(
166    g: &mut GateFn,
167    dst_ref: AigRef,
168    source_refs: &[AigRef],
169) {
170    let pir_node_ids = collect_node_provenance(g, source_refs);
171    g.gates[dst_ref.id].try_add_pir_node_ids(pir_node_ids.as_slice());
172}
xlsynth_g8r/transforms/transform_trait.rs

xlsynth_g8r/transforms/
transform_trait.rs
