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}