2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
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.
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.
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
22 #include "kernel/consteval.h"
25 PRIVATE_NAMESPACE_BEGIN
27 struct ExtractFaConfig
29 bool enable_fa
= false;
30 bool enable_ha
= false;
36 // http://svn.clifford.at/handicraft/2016/bindec/bindec.c
37 int bindec(unsigned char v
)
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;
50 struct ExtractFaWorker
52 const ExtractFaConfig
&config
;
57 dict
<SigBit
, Cell
*> driver
;
58 pool
<SigBit
> handled_bits
;
60 const int xor2_func
= 0x6, xnor2_func
= 0x9;
61 const int xor3_func
= 0x96, xnor3_func
= 0x69;
63 pool
<tuple
<SigBit
, SigBit
>> xorxnor2
;
64 pool
<tuple
<SigBit
, SigBit
, SigBit
>> xorxnor3
;
66 dict
<tuple
<SigBit
, SigBit
>, dict
<int, pool
<SigBit
>>> func2
;
67 dict
<tuple
<SigBit
, SigBit
, SigBit
>, dict
<int, pool
<SigBit
>>> func3
;
72 struct func2_and_info_t
{
73 bool inv_a
, inv_b
, inv_y
;
76 struct func3_maj_info_t
{
77 bool inv_a
, inv_b
, inv_c
, inv_y
;
80 dict
<int, func2_and_info_t
> func2_and_info
;
81 dict
<int, func3_maj_info_t
> func3_maj_info
;
83 ExtractFaWorker(const ExtractFaConfig
&config
, Module
*module
) :
84 config(config
), module(module
), ce(module
), sigmap(ce
.assign_map
)
86 for (auto cell
: module
->selected_cells())
88 if (cell
->type
.in( ID($_BUF_
), ID($_NOT_
), ID($_AND_
), ID($_NAND_
), ID($_OR_
), ID($_NOR_
),
89 ID($_XOR_
), ID($_XNOR_
), ID($_ANDNOT_
), ID($_ORNOT_
), ID($_MUX_
), ID($_NMUX_
),
90 ID($_AOI3_
), ID($_OAI3_
), ID($_AOI4_
), ID($_OAI4_
)))
92 SigBit y
= sigmap(SigBit(cell
->getPort(ID(\\Y
))));
93 log_assert(driver
.count(y
) == 0);
98 for (int ia
= 0; ia
< 2; ia
++)
99 for (int ib
= 0; ib
< 2; ib
++)
101 func2_and_info_t f2i
;
108 for (int i
= 0; i
< 4; i
++)
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
;
115 log_assert(func2_and_info
.count(func
) == 0);
116 func2_and_info
[func
] = f2i
;
121 log_assert(func2_and_info
.count(func
) == 0);
122 func2_and_info
[func
] = f2i
;
125 for (int ia
= 0; ia
< 2; ia
++)
126 for (int ib
= 0; ib
< 2; ib
++)
127 for (int ic
= 0; ic
< 2; ic
++)
129 func3_maj_info_t f3i
;
137 for (int i
= 0; i
< 8; i
++)
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
;
145 log_assert(func3_maj_info
.count(func
) == 0);
146 func3_maj_info
[func
] = f3i
;
151 // log_assert(func3_maj_info.count(func) == 0);
152 // func3_maj_info[func] = f3i;
156 void check_partition(SigBit root
, pool
<SigBit
> &leaves
)
158 if (config
.enable_ha
&& GetSize(leaves
) == 2)
162 SigBit A
= SigSpec(leaves
)[0];
163 SigBit B
= SigSpec(leaves
)[1];
166 for (int i
= 0; i
< 4; i
++)
168 bool a_value
= (i
& 1) != 0;
169 bool b_value
= (i
& 2) != 0;
172 ce
.set(A
, a_value
? State::S1
: State::S0
);
173 ce
.set(B
, b_value
? State::S1
: State::S0
);
182 if (sig
== State::S1
)
188 // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root));
190 if (func
== xor2_func
|| func
== xnor2_func
)
191 xorxnor2
.insert(tuple
<SigBit
, SigBit
>(A
, B
));
194 func2
[tuple
<SigBit
, SigBit
>(A
, B
)][func
].insert(root
);
197 if (config
.enable_fa
&& GetSize(leaves
) == 3)
201 SigBit A
= SigSpec(leaves
)[0];
202 SigBit B
= SigSpec(leaves
)[1];
203 SigBit C
= SigSpec(leaves
)[2];
206 for (int i
= 0; i
< 8; i
++)
208 bool a_value
= (i
& 1) != 0;
209 bool b_value
= (i
& 2) != 0;
210 bool c_value
= (i
& 4) != 0;
213 ce
.set(A
, a_value
? State::S1
: State::S0
);
214 ce
.set(B
, b_value
? State::S1
: State::S0
);
215 ce
.set(C
, c_value
? State::S1
: State::S0
);
224 if (sig
== State::S1
)
230 // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root));
232 if (func
== xor3_func
|| func
== xnor3_func
)
233 xorxnor3
.insert(tuple
<SigBit
, SigBit
, SigBit
>(A
, B
, C
));
236 func3
[tuple
<SigBit
, SigBit
, SigBit
>(A
, B
, C
)][func
].insert(root
);
240 void find_partitions(SigBit root
, pool
<SigBit
> &leaves
, pool
<pool
<SigBit
>> &cache
, int maxdepth
, int maxbreadth
)
242 if (cache
.count(leaves
))
245 // log("%*s[%d] %s:", 20-maxdepth, "", maxdepth, log_signal(root));
246 // for (auto bit : leaves)
247 // log(" %s", log_signal(bit));
250 cache
.insert(leaves
);
251 check_partition(root
, leaves
);
256 for (SigBit bit
: leaves
)
258 if (driver
.count(bit
) == 0)
261 Cell
*cell
= driver
.at(bit
);
262 pool
<SigBit
> new_leaves
= leaves
;
264 new_leaves
.erase(bit
);
265 if (cell
->hasPort(ID(\\A
))) new_leaves
.insert(sigmap(SigBit(cell
->getPort(ID(\\A
)))));
266 if (cell
->hasPort(ID(\\B
))) new_leaves
.insert(sigmap(SigBit(cell
->getPort(ID(\\B
)))));
267 if (cell
->hasPort(ID(\\C
))) new_leaves
.insert(sigmap(SigBit(cell
->getPort(ID(\\C
)))));
268 if (cell
->hasPort(ID(\\D
))) new_leaves
.insert(sigmap(SigBit(cell
->getPort(ID(\\D
)))));
270 if (GetSize(new_leaves
) > maxbreadth
)
273 find_partitions(root
, new_leaves
, cache
, maxdepth
-1, maxbreadth
);
277 void assign_new_driver(SigBit bit
, SigBit new_driver
)
279 Cell
*cell
= driver
.at(bit
);
280 if (sigmap(cell
->getPort(ID(\\Y
))) == bit
) {
281 cell
->setPort(ID(\\Y
), module
->addWire(NEW_ID
));
282 module
->connect(bit
, new_driver
);
288 log("Extracting full/half adders from %s:\n", log_id(module
));
290 for (auto it
: driver
)
292 if (it
.second
->type
.in(ID($_BUF_
), ID($_NOT_
)))
295 SigBit root
= it
.first
;
296 pool
<SigBit
> leaves
= { root
};
297 pool
<pool
<SigBit
>> cache
;
300 log(" checking %s\n", log_signal(it
.first
));
305 find_partitions(root
, leaves
, cache
, config
.maxdepth
, config
.maxbreadth
);
307 if (config
.verbose
&& count_func2
> 0)
308 log(" extracted %d two-input functions\n", count_func2
);
310 if (config
.verbose
&& count_func3
> 0)
311 log(" extracted %d three-input functions\n", count_func3
);
314 for (auto &key
: xorxnor3
)
316 SigBit A
= get
<0>(key
);
317 SigBit B
= get
<1>(key
);
318 SigBit C
= get
<2>(key
);
320 log(" 3-Input XOR/XNOR %s %s %s:\n", log_signal(A
), log_signal(B
), log_signal(C
));
322 for (auto &it
: func3
.at(key
))
324 if (it
.first
!= xor3_func
&& it
.first
!= xnor3_func
)
327 log(" %08d ->", bindec(it
.first
));
328 for (auto bit
: it
.second
)
329 log(" %s", log_signal(bit
));
333 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
335 for (auto &it
: func3_maj_info
)
338 auto f3i
= it
.second
;
340 if (func3
.at(key
).count(func
) == 0)
343 if (func3
.at(key
).count(xor3_func
) == 0 && func3
.at(key
).count(xnor3_func
) != 0) {
344 f3i
.inv_a
= !f3i
.inv_a
;
345 f3i
.inv_b
= !f3i
.inv_b
;
346 f3i
.inv_c
= !f3i
.inv_c
;
347 f3i
.inv_y
= !f3i
.inv_y
;
350 if (!f3i
.inv_a
&& !f3i
.inv_b
&& !f3i
.inv_c
&& !f3i
.inv_y
) {
351 log(" Majority without inversions:\n");
353 log(" Majority with inverted");
354 if (f3i
.inv_a
) log(" A");
355 if (f3i
.inv_b
) log(" B");
356 if (f3i
.inv_c
) log(" C");
357 if (f3i
.inv_y
) log(" Y");
361 log(" %08d ->", bindec(func
));
362 for (auto bit
: func3
.at(key
).at(func
))
363 log(" %s", log_signal(bit
));
367 if (f3i
.inv_a
) fakey
|= 1;
368 if (f3i
.inv_b
) fakey
|= 2;
369 if (f3i
.inv_c
) fakey
|= 4;
371 int fakey_inv
= fakey
^ 7;
372 bool invert_xy
= false;
375 if (facache
.count(fakey
))
377 auto &fa
= facache
.at(fakey
);
380 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
383 if (facache
.count(fakey_inv
))
385 auto &fa
= facache
.at(fakey_inv
);
389 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
393 Cell
*cell
= module
->addCell(NEW_ID
, ID($fa
));
394 cell
->setParam(ID(\\WIDTH
), 1);
396 log(" Created $fa cell %s.\n", log_id(cell
));
398 cell
->setPort(ID(\\A
), f3i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
399 cell
->setPort(ID(\\B
), f3i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
400 cell
->setPort(ID(\\C
), f3i
.inv_c
? module
->NotGate(NEW_ID
, C
) : C
);
402 X
= module
->addWire(NEW_ID
);
403 Y
= module
->addWire(NEW_ID
);
405 cell
->setPort(ID(\\X
), X
);
406 cell
->setPort(ID(\\Y
), Y
);
408 facache
[fakey
] = make_tuple(X
, Y
, cell
);
411 if (func3
.at(key
).count(xor3_func
)) {
412 SigBit YY
= invert_xy
? module
->NotGate(NEW_ID
, Y
) : Y
;
413 for (auto bit
: func3
.at(key
).at(xor3_func
))
414 assign_new_driver(bit
, YY
);
417 if (func3
.at(key
).count(xnor3_func
)) {
418 SigBit YY
= invert_xy
? Y
: module
->NotGate(NEW_ID
, Y
);
419 for (auto bit
: func3
.at(key
).at(xnor3_func
))
420 assign_new_driver(bit
, YY
);
423 SigBit XX
= invert_xy
!= f3i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
425 for (auto bit
: func3
.at(key
).at(func
))
426 assign_new_driver(bit
, XX
);
430 for (auto &key
: xorxnor2
)
432 SigBit A
= get
<0>(key
);
433 SigBit B
= get
<1>(key
);
435 log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A
), log_signal(B
));
437 for (auto &it
: func2
.at(key
))
439 if (it
.first
!= xor2_func
&& it
.first
!= xnor2_func
)
442 log(" %04d ->", bindec(it
.first
));
443 for (auto bit
: it
.second
)
444 log(" %s", log_signal(bit
));
448 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
450 for (auto &it
: func2_and_info
)
453 auto &f2i
= it
.second
;
455 if (func2
.at(key
).count(func
) == 0)
458 if (!f2i
.inv_a
&& !f2i
.inv_b
&& !f2i
.inv_y
) {
459 log(" AND without inversions:\n");
461 log(" AND with inverted");
462 if (f2i
.inv_a
) log(" A");
463 if (f2i
.inv_b
) log(" B");
464 if (f2i
.inv_y
) log(" Y");
468 log(" %04d ->", bindec(func
));
469 for (auto bit
: func2
.at(key
).at(func
))
470 log(" %s", log_signal(bit
));
474 if (f2i
.inv_a
) fakey
|= 1;
475 if (f2i
.inv_b
) fakey
|= 2;
477 int fakey_inv
= fakey
^ 3;
478 bool invert_xy
= false;
481 if (facache
.count(fakey
))
483 auto &fa
= facache
.at(fakey
);
486 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
489 if (facache
.count(fakey_inv
))
491 auto &fa
= facache
.at(fakey_inv
);
495 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
499 Cell
*cell
= module
->addCell(NEW_ID
, ID($fa
));
500 cell
->setParam(ID(\\WIDTH
), 1);
502 log(" Created $fa cell %s.\n", log_id(cell
));
504 cell
->setPort(ID(\\A
), f2i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
505 cell
->setPort(ID(\\B
), f2i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
506 cell
->setPort(ID(\\C
), State::S0
);
508 X
= module
->addWire(NEW_ID
);
509 Y
= module
->addWire(NEW_ID
);
511 cell
->setPort(ID(\\X
), X
);
512 cell
->setPort(ID(\\Y
), Y
);
515 if (func2
.at(key
).count(xor2_func
)) {
516 SigBit YY
= invert_xy
|| (f2i
.inv_a
&& !f2i
.inv_b
) || (!f2i
.inv_a
&& f2i
.inv_b
) ? module
->NotGate(NEW_ID
, Y
) : Y
;
517 for (auto bit
: func2
.at(key
).at(xor2_func
))
518 assign_new_driver(bit
, YY
);
521 if (func2
.at(key
).count(xnor2_func
)) {
522 SigBit YY
= invert_xy
|| (f2i
.inv_a
&& !f2i
.inv_b
) || (!f2i
.inv_a
&& f2i
.inv_b
) ? Y
: module
->NotGate(NEW_ID
, Y
);
523 for (auto bit
: func2
.at(key
).at(xnor2_func
))
524 assign_new_driver(bit
, YY
);
527 SigBit XX
= invert_xy
!= f2i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
529 for (auto bit
: func2
.at(key
).at(func
))
530 assign_new_driver(bit
, XX
);
536 struct ExtractFaPass
: public Pass
{
537 ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
538 void help() YS_OVERRIDE
540 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
542 log(" extract_fa [options] [selection]\n");
544 log("This pass extracts full/half adders from a gate-level design.\n");
547 log(" Enable cell types (fa=full adder, ha=half adder)\n");
548 log(" All types are enabled if none of this options is used\n");
551 log(" Set maximum depth for extracted logic cones (default=20)\n");
554 log(" Set maximum breadth for extracted logic cones (default=6)\n");
557 log(" Verbose output\n");
560 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
562 ExtractFaConfig config
;
564 log_header(design
, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
568 for (argidx
= 1; argidx
< args
.size(); argidx
++)
570 if (args
[argidx
] == "-fa") {
571 config
.enable_fa
= true;
574 if (args
[argidx
] == "-ha") {
575 config
.enable_ha
= true;
578 if (args
[argidx
] == "-v") {
579 config
.verbose
= true;
582 if (args
[argidx
] == "-d" && argidx
+2 < args
.size()) {
583 config
.maxdepth
= atoi(args
[++argidx
].c_str());
586 if (args
[argidx
] == "-b" && argidx
+2 < args
.size()) {
587 config
.maxbreadth
= atoi(args
[++argidx
].c_str());
592 extra_args(args
, argidx
, design
);
594 if (!config
.enable_fa
&& !config
.enable_ha
) {
595 config
.enable_fa
= true;
596 config
.enable_ha
= true;
599 for (auto module
: design
->selected_modules())
601 ExtractFaWorker
worker(config
, module
);
609 PRIVATE_NAMESPACE_END