Skip to main content

prjunnamed_generic/rewrite/
aig.rs

1use prjunnamed_netlist::{
2    Cell, ControlNet, MetaItemId, ValueBit, RewriteNetSource, RewriteResult, RewriteRuleset, Rewriter, Value,
3};
4
5/// Implements simple AIG optimizations.
6///
7/// The following transformations are done:
8///
9/// - multi-bit And, Or, Xor, Not are bitblasted
10/// - single-bit And, Or are transformed into Aig
11/// - Not cells on Aig inputs are merged into the Aig
12/// - Not cells on Xor inputs are pushed onto the output
13/// - const folding:
14///   - ~0 -> 1
15///   - ~1 -> 0
16///   - ~X -> X
17///   - a & 0 -> 0
18///   - a & 1 -> a
19///   - a ^ 0 -> a
20///   - a ^ 1 -> ~a
21///   - a ^ X -> X
22/// - idempotence:
23///   - a & a -> a
24///   - (a & b) & a -> a
25///   - (a & b) & (a & c) -> (a & b) & c
26/// - contradiction:
27///   - a & ~a -> 0
28///   - (a & b) & ~a -> 0
29///   - (a & b) & (~a & c) -> 0
30/// - subsumption:
31///   - (a | b) & a -> a
32///   - (a | b) & (a & c) -> a & c
33/// - resolution:
34///   - (a | b) & (~a | b) -> b
35/// - substitution:
36///   - (a | b) & ~b -> a & ~b
37///   - (a | b) & (~b & c) -> a & (~b & c)
38///   - (a ^ b) & ~b -> a & ~b
39///   - (a ^ b) & b -> ~a & b
40///   - ~(a ^ b) & ~b -> ~a & ~b
41///   - ~(a ^ b) & b -> a & b
42///   - (a ^ b) & (~b & c) -> a & (~b & c)
43///   - (a ^ b) & (b & c) -> ~a & (b & c)
44///   - ~(a ^ b) & (~b & c) -> ~a & (~b & c)
45///   - ~(a ^ b) & (b & c) -> a & (b & c)
46/// - XOR folding:
47///   - a ^ a -> 0
48///   - (a ^ b) ^ a -> b
49///   - (a ^ b) ^ (a ^ c) -> b ^ c
50/// - AND-XOR optimization:
51///   - (a & b) ^ a -> a & ~b
52///   - (a & b) ^ ~a -> ~(a & ~b)
53/// - XOR recognition:
54///   - ~(a & b) & ~(~a & ~b) -> a ^ b
55///
56/// All rules above are replicated for any commutation of operands, and any negation of inputs.
57///
58/// This ruleset ensures that any fragment of the netlist including only Not, And, Or, Xor, Aig cells will
59/// be transformed into a fragment containing only Aig, single-bit Xor, and single-bit Not cells, with the single-bit
60/// Not cells only present when required by non-Aig non-Xor cell inputs.
61///
62/// The optimizations performed here are mostly borrowed from <https://fmv.jku.at/papers/BrummayerBiere-MEMICS06.pdf>
63/// and have an important property described in the paper: they will never create more than one new cell (Not cells
64/// don't count), and they will not increase the logic level. Thus, they can never make the netlist "worse".
65pub struct SimpleAigOpt;
66
67impl RewriteRuleset for SimpleAigOpt {
68    fn rewrite<'a>(
69        &self,
70        cell: &Cell,
71        meta: MetaItemId,
72        _output: Option<&Value>,
73        rewriter: &Rewriter<'a>,
74    ) -> RewriteResult {
75        match *cell {
76            Cell::Not(ref val) if val.len() == 1 => {
77                let net = val[0];
78                if net == ValueBit::ZERO {
79                    return ValueBit::ONE.into();
80                }
81                if net == ValueBit::ONE {
82                    return ValueBit::ZERO.into();
83                }
84                if net == ValueBit::UNDEF {
85                    return ValueBit::UNDEF.into();
86                }
87                let src = rewriter.find_cell(net);
88                if let RewriteNetSource::Cell(cell, _, bit) = src
89                    && let Cell::Not(ref val) = *cell
90                {
91                    return val[bit].into();
92                }
93                RewriteResult::None
94            }
95
96            Cell::Aig(net1, net2) => {
97                for (net_a, net_b) in [(net1, net2), (net2, net1)] {
98                    let src_a = rewriter.find_cell(net_a.net());
99                    let src_b = rewriter.find_cell(net_b.net());
100
101                    // idempotence: a & a -> a
102                    if net_a == net_b {
103                        return net_a.into();
104                    }
105
106                    // contradiction: a & ~a, a & 0 -> 0
107                    if net_a == !net_b || net_b.is_always(false) {
108                        return ValueBit::ZERO.into();
109                    }
110
111                    // identity: a & 1 -> a
112                    if net_b.is_always(true) {
113                        return net_a.into();
114                    }
115
116                    // merge inverters into AIG cell
117                    if let RewriteNetSource::Cell(ref cell_a, meta_a, bit) = src_a
118                        && let Cell::Not(ref val) = **cell_a
119                    {
120                        let new_a = ControlNet::from_net_invert(val[bit], !net_a.is_negative());
121                        let meta = rewriter.meta_from_merge([meta, meta_a]);
122                        return RewriteResult::CellMeta(Cell::Aig(new_a, net_b), meta);
123                    }
124
125                    if let RewriteNetSource::Cell(ref cell_a, _, _) = src_a
126                        && let Cell::Aig(net_a1, net_a2) = **cell_a
127                        && net_a.is_positive()
128                    {
129                        // (aa & ab) & b
130                        for (net_aa, _net_ab) in [(net_a1, net_a2), (net_a2, net_a1)] {
131                            // idempotence: (aa & ab) & aa -> aa & ab
132                            if net_aa == net_b {
133                                return net_a.into();
134                            }
135                            // contradiction: (aa & ab) & ~aa -> 0
136                            if net_aa == !net_b {
137                                return ValueBit::ZERO.into();
138                            }
139
140                            if let RewriteNetSource::Cell(ref cell_b, _, _) = src_b
141                                && let Cell::Aig(net_b1, net_b2) = **cell_b
142                                && net_b.is_positive()
143                            {
144                                // (aa & ab) & (ba & bb)
145                                for (net_ba, net_bb) in [(net_b1, net_b2), (net_b2, net_b1)] {
146                                    // idempotence: (aa & ab) & (aa & bb) -> (aa & ab) & bb
147                                    if net_aa == net_ba {
148                                        return Cell::Aig(net_a, net_bb).into();
149                                    }
150                                    // contradiction: (aa & ab) & (~aa & bb) -> 0
151                                    if net_aa == !net_ba {
152                                        return ValueBit::ZERO.into();
153                                    }
154                                }
155                            }
156                        }
157                    }
158
159                    if let RewriteNetSource::Cell(ref cell_a, meta_a, _) = src_a
160                        && let Cell::Aig(net_a1, net_a2) = **cell_a
161                        && net_a.is_negative()
162                    {
163                        // ~(aa & ab) & b
164                        for (net_aa, net_ab) in [(net_a1, net_a2), (net_a2, net_a1)] {
165                            // substitution: ~(aa & ab) & aa -> ~ab & aa
166                            if net_aa == net_b {
167                                return Cell::Aig(!net_ab, net_b).into();
168                            }
169                            // subsumption: ~(aa & ab) & ~aa -> ~aa
170                            if net_aa == !net_b {
171                                return net_b.into();
172                            }
173
174                            if let RewriteNetSource::Cell(ref cell_b, _, _) = src_b
175                                && let Cell::Aig(net_b1, net_b2) = **cell_b
176                                && net_b.is_positive()
177                            {
178                                // ~(aa & ab) & (ba & bb)
179                                for (net_ba, _net_bb) in [(net_b1, net_b2), (net_b2, net_b1)] {
180                                    // substitution: ~(aa & ab) & (aa & bb) -> ~ab & (aa & bb)
181                                    if net_aa == net_ba {
182                                        return Cell::Aig(!net_ab, net_b).into();
183                                    }
184                                    // subsumption: ~(aa & ab) & (~aa & bb) -> (~aa & bb)
185                                    if net_aa == !net_ba {
186                                        return net_b.into();
187                                    }
188                                }
189                            }
190
191                            if let RewriteNetSource::Cell(ref cell_b, meta_b, _) = src_b
192                                && let Cell::Aig(net_b1, net_b2) = **cell_b
193                                && net_b.is_negative()
194                            {
195                                // ~(aa & ab) & ~(ba & bb)
196                                for (net_ba, net_bb) in [(net_b1, net_b2), (net_b2, net_b1)] {
197                                    // resolution: ~(aa & ab) & ~(~aa & ab) -> ~ab
198                                    if net_aa == !net_ba && net_ab == net_bb {
199                                        return (!net_ab).into();
200                                    }
201                                    // XOR recognition: ~(aa & ab) & ~(~aa & ~ab) -> aa ^ ab
202                                    if net_aa == !net_ba && net_ab == !net_bb {
203                                        let xor_meta = rewriter.meta_from_merge([meta, meta_a, meta_b]);
204                                        let xor = Cell::Xor(net_aa.net().into(), net_ab.net().into());
205                                        if net_aa.is_negative() ^ net_ab.is_negative() {
206                                            let xor = rewriter.add_cell_meta(xor, xor_meta);
207                                            return Cell::Not(xor).into();
208                                        } else {
209                                            return RewriteResult::CellMeta(xor, xor_meta);
210                                        }
211                                    }
212                                }
213                            }
214                        }
215                    }
216
217                    if let RewriteNetSource::Cell(ref cell_a, _, bit) = src_a
218                        && let Cell::Xor(ref val_a1, ref val_a2) = **cell_a
219                    {
220                        let inv_a = net_a.is_negative();
221                        let net_a1 = val_a1[bit];
222                        let net_a2 = val_a2[bit];
223                        // (aa ^ ab) & b
224                        for (net_aa, net_ab) in [(net_a1, net_a2), (net_a2, net_a1)] {
225                            // substitution: (aa ^ ab) & aa -> ~ab & aa
226                            // substitution: ~(aa ^ ab) & aa -> ab & aa
227                            // substitution: (aa ^ ab) & ~aa -> ab & ~aa
228                            // substitution: ~(aa ^ ab) & ~aa -> ~ab & ~aa
229                            if net_aa == net_b.net() {
230                                let inv = !(inv_a ^ net_b.is_negative());
231                                return Cell::Aig(ControlNet::from_net_invert(net_ab, inv), net_b).into();
232                            }
233
234                            if let RewriteNetSource::Cell(ref cell_b, _, _) = src_b
235                                && let Cell::Aig(net_b1, net_b2) = **cell_b
236                                && net_b.is_positive()
237                            {
238                                // (aa ^ ab) & (ba & bb)
239                                for (net_ba, _net_bb) in [(net_b1, net_b2), (net_b2, net_b1)] {
240                                    // substitution: (aa ^ ab) & (aa & bb) -> ~ab & aa
241                                    // substitution: ~(aa ^ ab) & (aa & bb) -> ab & aa
242                                    // substitution: (aa ^ ab) & (~aa & bb) -> ab & ~aa
243                                    // substitution: ~(aa ^ ab) & (~aa & bb) -> ~ab & ~aa
244                                    if net_aa == net_ba.net() {
245                                        let inv = !(inv_a ^ net_ba.is_negative());
246                                        return Cell::Aig(ControlNet::from_net_invert(net_ab, inv), net_b).into();
247                                    }
248                                }
249                            }
250                        }
251                    }
252                }
253
254                RewriteResult::None
255            }
256
257            Cell::Xor(ref val1, ref val2) if val1.len() == 1 => {
258                let net1 = val1[0];
259                let net2 = val2[0];
260                for (net_a, net_b) in [(net1, net2), (net2, net1)] {
261                    let src_a = rewriter.find_cell(net_a);
262                    let src_b = rewriter.find_cell(net_b);
263
264                    // a ^ a -> 0
265                    if net_a == net_b {
266                        return ValueBit::ZERO.into();
267                    }
268
269                    // a ^ X -> X
270                    if net_b == ValueBit::UNDEF {
271                        return ValueBit::UNDEF.into();
272                    }
273
274                    // a ^ 0 -> a
275                    if net_b == ValueBit::ZERO {
276                        return net_a.into();
277                    }
278
279                    // a ^ 1 -> ~a
280                    if net_b == ValueBit::ONE {
281                        return Cell::Not(net_a.into()).into();
282                    }
283
284                    // !a ^ b -> !(a ^ b)
285                    if let RewriteNetSource::Cell(ref cell_a, meta_a, bit) = src_a
286                        && let Cell::Not(ref val) = **cell_a
287                    {
288                        let meta = rewriter.meta_from_merge([meta, meta_a]);
289                        let xor = rewriter.add_cell_meta(Cell::Xor(val[bit].into(), net_b.into()), meta);
290                        return RewriteResult::CellMeta(Cell::Not(xor), meta);
291                    }
292
293                    if let RewriteNetSource::Cell(ref cell_a, meta_a, _) = src_a
294                        && let Cell::Aig(net_a1, net_a2) = **cell_a
295                    {
296                        // (aa & ab) ^ b
297                        for (net_aa, net_ab) in [(net_a1, net_a2), (net_a2, net_a1)] {
298                            // (aa & ab) ^ aa -> aa & ~ab
299                            let meta = rewriter.meta_from_merge([meta, meta_a]);
300                            if net_aa == ControlNet::Pos(net_b) {
301                                return RewriteResult::CellMeta(Cell::Aig(net_aa, !net_ab), meta);
302                            }
303                            // (aa & ab) ^ ~aa -> ~(aa & ~ab)
304                            if net_aa == ControlNet::Neg(net_b) {
305                                let aig = rewriter.add_cell(Cell::Aig(net_aa, !net_ab));
306                                return RewriteResult::CellMeta(Cell::Not(aig), meta);
307                            }
308                        }
309                    }
310
311                    if let RewriteNetSource::Cell(ref cell_a, meta_a, bit) = src_a
312                        && let Cell::Xor(ref val_a1, ref val_a2) = **cell_a
313                    {
314                        let net_a1 = val_a1[bit];
315                        let net_a2 = val_a2[bit];
316                        // (aa ^ ab) ^ b
317                        for (net_aa, net_ab) in [(net_a1, net_a2), (net_a2, net_a1)] {
318                            // (aa ^ ab) ^ aa -> ab
319                            if net_aa == net_b {
320                                return net_ab.into();
321                            }
322
323                            if let RewriteNetSource::Cell(ref cell_b, meta_b, bit) = src_b
324                                && let Cell::Xor(ref val_b1, ref val_b2) = **cell_b
325                            {
326                                let net_b1 = val_b1[bit];
327                                let net_b2 = val_b2[bit];
328                                // (aa ^ ab) ^ (ba ^ bb)
329                                for (net_ba, net_bb) in [(net_b1, net_b2), (net_b2, net_b1)] {
330                                    // (aa ^ ab) ^ (aa ^ bb) -> ab ^ bb
331                                    if net_aa == net_ba {
332                                        let meta = rewriter.meta_from_merge([meta, meta_a, meta_b]);
333                                        return RewriteResult::CellMeta(Cell::Xor(net_ab.into(), net_bb.into()), meta);
334                                    }
335                                }
336                            }
337                        }
338                    }
339                }
340                RewriteResult::None
341            }
342
343            // Split bitwise Not and Xor into single-bit cells.
344            Cell::Not(ref val) => {
345                let mut result = Value::new();
346                for net in val {
347                    result.extend(rewriter.add_cell(Cell::Not(net.into())));
348                }
349                result.into()
350            }
351            Cell::Xor(ref val_a, ref val_b) => {
352                let mut result = Value::new();
353                for (net_a, net_b) in val_a.iter().zip(val_b.iter()) {
354                    result.extend(rewriter.add_cell(Cell::Xor(net_a.into(), net_b.into())));
355                }
356                result.into()
357            }
358
359            // Convert And and Or into AIG.
360            Cell::And(ref val_a, ref val_b) => {
361                let mut result = Value::new();
362                for (net_a, net_b) in val_a.iter().zip(val_b.iter()) {
363                    result.extend(rewriter.add_cell(Cell::Aig(net_a.into(), net_b.into())));
364                }
365                result.into()
366            }
367            Cell::Or(ref val_a, ref val_b) => {
368                let mut result = Value::new();
369                for (net_a, net_b) in val_a.iter().zip(val_b.iter()) {
370                    let aig = rewriter.add_cell(Cell::Aig(ControlNet::Neg(net_a), ControlNet::Neg(net_b)));
371                    result.extend(rewriter.add_cell(Cell::Not(aig)));
372                }
373                result.into()
374            }
375
376            _ => RewriteResult::None,
377        }
378    }
379}