projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Only sort leaves on non-ANDNOT/ORNOT cells
[yosys.git] / passes / techmap / extract_fa.cc
1 /*
2 * yosys -- Yosys Open SYnthesis Suite
3 *
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 *
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 *
18 */
19
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
22 #include "kernel/consteval.h"
23
24 USING_YOSYS_NAMESPACE
25 PRIVATE_NAMESPACE_BEGIN
26
27 struct ExtractFaConfig
28 {
29 bool enable_fa = false;
30 bool enable_ha = false;
31 bool verbose = false;
32 int maxdepth = 20;
33 int maxbreadth = 6;
34 };
35
36 // http://svn.clifford.at/handicraft/2016/bindec/bindec.c
37 int bindec(unsigned char v)
38 {
39 int r = v & 1;
40 r += (~((v & 2) - 1)) & 10;
41 r += (~((v & 4) - 1)) & 100;
42 r += (~((v & 8) - 1)) & 1000;
43 r += (~((v & 16) - 1)) & 10000;
44 r += (~((v & 32) - 1)) & 100000;
45 r += (~((v & 64) - 1)) & 1000000;
46 r += (~((v & 128) - 1)) & 10000000;
47 return r;
48 }
49
50 struct ExtractFaWorker
51 {
52 const ExtractFaConfig &config;
53 Module *module;
54 ConstEval ce;
55 SigMap &sigmap;
56
57 dict<SigBit, Cell*> driver;
58 pool<SigBit> handled_bits;
59
60 const int xor2_func = 0x6, xnor2_func = 0x9;
61 const int xor3_func = 0x96, xnor3_func = 0x69;
62
63 pool<tuple<SigBit, SigBit>> xorxnor2;
64 pool<tuple<SigBit, SigBit, SigBit>> xorxnor3;
65
66 dict<tuple<SigBit, SigBit>, dict<int, pool<SigBit>>> func2;
67 dict<tuple<SigBit, SigBit, SigBit>, dict<int, pool<SigBit>>> func3;
68
69 int count_func2;
70 int count_func3;
71
72 struct func2_and_info_t {
73 bool inv_a, inv_b, inv_y;
74 };
75
76 struct func3_maj_info_t {
77 bool inv_a, inv_b, inv_c, inv_y;
78 };
79
80 dict<int, func2_and_info_t> func2_and_info;
81 dict<int, func3_maj_info_t> func3_maj_info;
82
83 ExtractFaWorker(const ExtractFaConfig &config, Module *module) :
84 config(config), module(module), ce(module), sigmap(ce.assign_map)
85 {
86 for (auto cell : module->selected_cells())
87 {
88 if (cell->type.in( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_",
89 "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_", "$_NMUX_",
90 "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_"))
91 {
92 SigBit y = sigmap(SigBit(cell->getPort("\\Y")));
93 log_assert(driver.count(y) == 0);
94 driver[y] = cell;
95 }
96 }
97
98 for (int ia = 0; ia < 2; ia++)
99 for (int ib = 0; ib < 2; ib++)
100 {
101 func2_and_info_t f2i;
102
103 f2i.inv_a = ia;
104 f2i.inv_b = ib;
105 f2i.inv_y = false;
106
107 int func = 0;
108 for (int i = 0; i < 4; i++)
109 {
110 bool a = (i & 1) ? !f2i.inv_a : f2i.inv_a;
111 bool b = (i & 2) ? !f2i.inv_b : f2i.inv_b;
112 if (a && b) func |= 1 << i;
113 }
114
115 log_assert(func2_and_info.count(func) == 0);
116 func2_and_info[func] = f2i;
117
118 f2i.inv_y = true;
119 func ^= 15;
120
121 log_assert(func2_and_info.count(func) == 0);
122 func2_and_info[func] = f2i;
123 }
124
125 for (int ia = 0; ia < 2; ia++)
126 for (int ib = 0; ib < 2; ib++)
127 for (int ic = 0; ic < 2; ic++)
128 {
129 func3_maj_info_t f3i;
130
131 f3i.inv_a = ia;
132 f3i.inv_b = ib;
133 f3i.inv_c = ic;
134 f3i.inv_y = false;
135
136 int func = 0;
137 for (int i = 0; i < 8; i++)
138 {
139 bool a = (i & 1) ? !f3i.inv_a : f3i.inv_a;
140 bool b = (i & 2) ? !f3i.inv_b : f3i.inv_b;
141 bool c = (i & 4) ? !f3i.inv_c : f3i.inv_c;
142 if ((a && b) || (a && c) || (b &&c)) func |= 1 << i;
143 }
144
145 log_assert(func3_maj_info.count(func) == 0);
146 func3_maj_info[func] = f3i;
147
148 // f3i.inv_y = true;
149 // func ^= 255;
150
151 // log_assert(func3_maj_info.count(func) == 0);
152 // func3_maj_info[func] = f3i;
153 }
154 }
155
156 void check_partition(SigBit root, pool<SigBit> &leaves, IdString cell_type)
157 {
158 if (config.enable_ha && GetSize(leaves) == 2)
159 {
160 if (!cell_type.in("$_ANDNOT_", "$_ORNOT_"))
161 leaves.sort();
162
163 SigBit A = SigSpec(leaves)[0];
164 SigBit B = SigSpec(leaves)[1];
165
166 int func = 0;
167 for (int i = 0; i < 4; i++)
168 {
169 bool a_value = (i & 1) != 0;
170 bool b_value = (i & 2) != 0;
171
172 ce.push();
173 ce.set(A, a_value ? State::S1 : State::S0);
174 ce.set(B, b_value ? State::S1 : State::S0);
175
176 SigSpec sig = root;
177
178 if (!ce.eval(sig)) {
179 ce.pop();
180 return;
181 }
182
183 if (sig == State::S1)
184 func |= 1 << i;
185
186 ce.pop();
187 }
188
189 // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root));
190
191 if (func == xor2_func || func == xnor2_func)
192 xorxnor2.insert(tuple<SigBit, SigBit>(A, B));
193
194 count_func2++;
195 func2[tuple<SigBit, SigBit>(A, B)][func].insert(root);
196 }
197
198 if (config.enable_fa && GetSize(leaves) == 3)
199 {
200 leaves.sort();
201
202 SigBit A = SigSpec(leaves)[0];
203 SigBit B = SigSpec(leaves)[1];
204 SigBit C = SigSpec(leaves)[2];
205
206 int func = 0;
207 for (int i = 0; i < 8; i++)
208 {
209 bool a_value = (i & 1) != 0;
210 bool b_value = (i & 2) != 0;
211 bool c_value = (i & 4) != 0;
212
213 ce.push();
214 ce.set(A, a_value ? State::S1 : State::S0);
215 ce.set(B, b_value ? State::S1 : State::S0);
216 ce.set(C, c_value ? State::S1 : State::S0);
217
218 SigSpec sig = root;
219
220 if (!ce.eval(sig)) {
221 ce.pop();
222 return;
223 }
224
225 if (sig == State::S1)
226 func |= 1 << i;
227
228 ce.pop();
229 }
230
231 // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root));
232
233 if (func == xor3_func || func == xnor3_func)
234 xorxnor3.insert(tuple<SigBit, SigBit, SigBit>(A, B, C));
235
236 count_func3++;
237 func3[tuple<SigBit, SigBit, SigBit>(A, B, C)][func].insert(root);
238 }
239 }
240
241 void find_partitions(SigBit root, pool<SigBit> &leaves, pool<pool<SigBit>> &cache, int maxdepth, int maxbreadth, IdString cell_type)
242 {
243 if (cache.count(leaves))
244 return;
245
246 // log("%*s[%d] %s:", 20-maxdepth, "", maxdepth, log_signal(root));
247 // for (auto bit : leaves)
248 // log(" %s", log_signal(bit));
249 // log("\n");
250
251 cache.insert(leaves);
252 check_partition(root, leaves, cell_type);
253
254 if (maxdepth == 0)
255 return;
256
257 for (SigBit bit : leaves)
258 {
259 if (driver.count(bit) == 0)
260 continue;
261
262 Cell *cell = driver.at(bit);
263 pool<SigBit> new_leaves = leaves;
264
265 new_leaves.erase(bit);
266 if (cell->hasPort("\\A")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\A"))));
267 if (cell->hasPort("\\B")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\B"))));
268 if (cell->hasPort("\\C")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\C"))));
269 if (cell->hasPort("\\D")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\D"))));
270
271 if (GetSize(new_leaves) > maxbreadth)
272 continue;
273
274 find_partitions(root, new_leaves, cache, maxdepth-1, maxbreadth, cell_type);
275 }
276 }
277
278 void assign_new_driver(SigBit bit, SigBit new_driver)
279 {
280 Cell *cell = driver.at(bit);
281 if (sigmap(cell->getPort("\\Y")) == bit) {
282 cell->setPort("\\Y", module->addWire(NEW_ID));
283 module->connect(bit, new_driver);
284 }
285 }
286
287 void run()
288 {
289 log("Extracting full/half adders from %s:\n", log_id(module));
290
291 for (auto it : driver)
292 {
293 if (it.second->type.in("$_BUF_", "$_NOT_"))
294 continue;
295
296 SigBit root = it.first;
297 pool<SigBit> leaves = { root };
298 pool<pool<SigBit>> cache;
299
300 if (config.verbose)
301 log(" checking %s\n", log_signal(it.first));
302
303 count_func2 = 0;
304 count_func3 = 0;
305
306 find_partitions(root, leaves, cache, config.maxdepth, config.maxbreadth, it.second->type);
307
308 if (config.verbose && count_func2 > 0)
309 log(" extracted %d two-input functions\n", count_func2);
310
311 if (config.verbose && count_func3 > 0)
312 log(" extracted %d three-input functions\n", count_func3);
313 }
314
315 for (auto &key : xorxnor3)
316 {
317 SigBit A = get<0>(key);
318 SigBit B = get<1>(key);
319 SigBit C = get<2>(key);
320
321 log(" 3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C));
322
323 for (auto &it : func3.at(key))
324 {
325 if (it.first != xor3_func && it.first != xnor3_func)
326 continue;
327
328 log(" %08d ->", bindec(it.first));
329 for (auto bit : it.second)
330 log(" %s", log_signal(bit));
331 log("\n");
332 }
333
334 dict<int, tuple<SigBit, SigBit, Cell*>> facache;
335
336 for (auto &it : func3_maj_info)
337 {
338 int func = it.first;
339 auto f3i = it.second;
340
341 if (func3.at(key).count(func) == 0)
342 continue;
343
344 if (func3.at(key).count(xor3_func) == 0 && func3.at(key).count(xnor3_func) != 0) {
345 f3i.inv_a = !f3i.inv_a;
346 f3i.inv_b = !f3i.inv_b;
347 f3i.inv_c = !f3i.inv_c;
348 f3i.inv_y = !f3i.inv_y;
349 }
350
351 if (!f3i.inv_a && !f3i.inv_b && !f3i.inv_c && !f3i.inv_y) {
352 log(" Majority without inversions:\n");
353 } else {
354 log(" Majority with inverted");
355 if (f3i.inv_a) log(" A");
356 if (f3i.inv_b) log(" B");
357 if (f3i.inv_c) log(" C");
358 if (f3i.inv_y) log(" Y");
359 log(":\n");
360 }
361
362 log(" %08d ->", bindec(func));
363 for (auto bit : func3.at(key).at(func))
364 log(" %s", log_signal(bit));
365 log("\n");
366
367 int fakey = 0;
368 if (f3i.inv_a) fakey |= 1;
369 if (f3i.inv_b) fakey |= 2;
370 if (f3i.inv_c) fakey |= 4;
371
372 int fakey_inv = fakey ^ 7;
373 bool invert_xy = false;
374 SigBit X, Y;
375
376 if (facache.count(fakey))
377 {
378 auto &fa = facache.at(fakey);
379 X = get<0>(fa);
380 Y = get<1>(fa);
381 log(" Reusing $fa cell %s.\n", log_id(get<2>(fa)));
382 }
383 else
384 if (facache.count(fakey_inv))
385 {
386 auto &fa = facache.at(fakey_inv);
387 invert_xy = true;
388 X = get<0>(fa);
389 Y = get<1>(fa);
390 log(" Reusing $fa cell %s.\n", log_id(get<2>(fa)));
391 }
392 else
393 {
394 Cell *cell = module->addCell(NEW_ID, "$fa");
395 cell->setParam("\\WIDTH", 1);
396
397 log(" Created $fa cell %s.\n", log_id(cell));
398
399 cell->setPort("\\A", f3i.inv_a ? module->NotGate(NEW_ID, A) : A);
400 cell->setPort("\\B", f3i.inv_b ? module->NotGate(NEW_ID, B) : B);
401 cell->setPort("\\C", f3i.inv_c ? module->NotGate(NEW_ID, C) : C);
402
403 X = module->addWire(NEW_ID);
404 Y = module->addWire(NEW_ID);
405
406 cell->setPort("\\X", X);
407 cell->setPort("\\Y", Y);
408
409 facache[fakey] = make_tuple(X, Y, cell);
410 }
411
412 if (func3.at(key).count(xor3_func)) {
413 SigBit YY = invert_xy ? module->NotGate(NEW_ID, Y) : Y;
414 for (auto bit : func3.at(key).at(xor3_func))
415 assign_new_driver(bit, YY);
416 }
417
418 if (func3.at(key).count(xnor3_func)) {
419 SigBit YY = invert_xy ? Y : module->NotGate(NEW_ID, Y);
420 for (auto bit : func3.at(key).at(xnor3_func))
421 assign_new_driver(bit, YY);
422 }
423
424 SigBit XX = invert_xy != f3i.inv_y ? module->NotGate(NEW_ID, X) : X;
425
426 for (auto bit : func3.at(key).at(func))
427 assign_new_driver(bit, XX);
428 }
429 }
430
431 for (auto &key : xorxnor2)
432 {
433 SigBit A = get<0>(key);
434 SigBit B = get<1>(key);
435
436 log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B));
437
438 for (auto &it : func2.at(key))
439 {
440 if (it.first != xor2_func && it.first != xnor2_func)
441 continue;
442
443 log(" %04d ->", bindec(it.first));
444 for (auto bit : it.second)
445 log(" %s", log_signal(bit));
446 log("\n");
447 }
448
449 dict<int, tuple<SigBit, SigBit, Cell*>> facache;
450
451 for (auto &it : func2_and_info)
452 {
453 int func = it.first;
454 auto &f2i = it.second;
455
456 if (func2.at(key).count(func) == 0)
457 continue;
458
459 if (!f2i.inv_a && !f2i.inv_b && !f2i.inv_y) {
460 log(" AND without inversions:\n");
461 } else {
462 log(" AND with inverted");
463 if (f2i.inv_a) log(" A");
464 if (f2i.inv_b) log(" B");
465 if (f2i.inv_y) log(" Y");
466 log(":\n");
467 }
468
469 log(" %04d ->", bindec(func));
470 for (auto bit : func2.at(key).at(func))
471 log(" %s", log_signal(bit));
472 log("\n");
473
474 int fakey = 0;
475 if (f2i.inv_a) fakey |= 1;
476 if (f2i.inv_b) fakey |= 2;
477
478 int fakey_inv = fakey ^ 3;
479 bool invert_xy = false;
480 SigBit X, Y;
481
482 if (facache.count(fakey))
483 {
484 auto &fa = facache.at(fakey);
485 X = get<0>(fa);
486 Y = get<1>(fa);
487 log(" Reusing $fa cell %s.\n", log_id(get<2>(fa)));
488 }
489 else
490 if (facache.count(fakey_inv))
491 {
492 auto &fa = facache.at(fakey_inv);
493 invert_xy = true;
494 X = get<0>(fa);
495 Y = get<1>(fa);
496 log(" Reusing $fa cell %s.\n", log_id(get<2>(fa)));
497 }
498 else
499 {
500 Cell *cell = module->addCell(NEW_ID, "$fa");
501 cell->setParam("\\WIDTH", 1);
502
503 log(" Created $fa cell %s.\n", log_id(cell));
504
505 cell->setPort("\\A", f2i.inv_a ? module->NotGate(NEW_ID, A) : A);
506 cell->setPort("\\B", f2i.inv_b ? module->NotGate(NEW_ID, B) : B);
507 cell->setPort("\\C", State::S0);
508
509 X = module->addWire(NEW_ID);
510 Y = module->addWire(NEW_ID);
511
512 cell->setPort("\\X", X);
513 cell->setPort("\\Y", Y);
514 }
515
516 if (func2.at(key).count(xor2_func)) {
517 SigBit YY = invert_xy ? module->NotGate(NEW_ID, Y) : Y;
518 for (auto bit : func2.at(key).at(xor2_func))
519 assign_new_driver(bit, YY);
520 }
521
522 if (func2.at(key).count(xnor2_func)) {
523 SigBit YY = invert_xy ? Y : module->NotGate(NEW_ID, Y);
524 for (auto bit : func2.at(key).at(xnor2_func))
525 assign_new_driver(bit, YY);
526 }
527
528 SigBit XX = invert_xy != f2i.inv_y ? module->NotGate(NEW_ID, X) : X;
529
530 for (auto bit : func2.at(key).at(func))
531 assign_new_driver(bit, XX);
532 }
533 }
534 }
535 };
536
537 struct ExtractFaPass : public Pass {
538 ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
539 void help() YS_OVERRIDE
540 {
541 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
542 log("\n");
543 log(" extract_fa [options] [selection]\n");
544 log("\n");
545 log("This pass extracts full/half adders from a gate-level design.\n");
546 log("\n");
547 log(" -fa, -ha\n");
548 log(" Enable cell types (fa=full adder, ha=half adder)\n");
549 log(" All types are enabled if none of this options is used\n");
550 log("\n");
551 log(" -d <int>\n");
552 log(" Set maximum depth for extracted logic cones (default=20)\n");
553 log("\n");
554 log(" -b <int>\n");
555 log(" Set maximum breadth for extracted logic cones (default=6)\n");
556 log("\n");
557 log(" -v\n");
558 log(" Verbose output\n");
559 log("\n");
560 }
561 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
562 {
563 ExtractFaConfig config;
564
565 log_header(design, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
566 log_push();
567
568 size_t argidx;
569 for (argidx = 1; argidx < args.size(); argidx++)
570 {
571 if (args[argidx] == "-fa") {
572 config.enable_fa = true;
573 continue;
574 }
575 if (args[argidx] == "-ha") {
576 config.enable_ha = true;
577 continue;
578 }
579 if (args[argidx] == "-v") {
580 config.verbose = true;
581 continue;
582 }
583 if (args[argidx] == "-d" && argidx+2 < args.size()) {
584 config.maxdepth = atoi(args[++argidx].c_str());
585 continue;
586 }
587 if (args[argidx] == "-b" && argidx+2 < args.size()) {
588 config.maxbreadth = atoi(args[++argidx].c_str());
589 continue;
590 }
591 break;
592 }
593 extra_args(args, argidx, design);
594
595 if (!config.enable_fa && !config.enable_ha) {
596 config.enable_fa = true;
597 config.enable_ha = true;
598 }
599
600 for (auto module : design->selected_modules())
601 {
602 ExtractFaWorker worker(config, module);
603 worker.run();
604 }
605
606 log_pop();
607 }
608 } ExtractFaPass;
609
610 PRIVATE_NAMESPACE_END