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( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_",
89 "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_", "$_NMUX_",
90 "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_"))
92 SigBit y
= sigmap(SigBit(cell
->getPort("\\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
, const pool
<SigBit
> &leaves
)
158 if (config
.enable_ha
&& GetSize(leaves
) == 2)
160 SigBit A
= SigSpec(leaves
)[0];
161 SigBit B
= SigSpec(leaves
)[1];
164 for (int i
= 0; i
< 4; i
++)
166 bool a_value
= (i
& 1) != 0;
167 bool b_value
= (i
& 2) != 0;
170 ce
.set(A
, a_value
? State::S1
: State::S0
);
171 ce
.set(B
, b_value
? State::S1
: State::S0
);
180 if (sig
== State::S1
)
186 // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root));
188 if (func
== xor2_func
|| func
== xnor2_func
)
189 xorxnor2
.insert(tuple
<SigBit
, SigBit
>(A
, B
));
192 func2
[tuple
<SigBit
, SigBit
>(A
, B
)][func
].insert(root
);
195 if (config
.enable_fa
&& GetSize(leaves
) == 3)
197 SigBit A
= SigSpec(leaves
)[0];
198 SigBit B
= SigSpec(leaves
)[1];
199 SigBit C
= SigSpec(leaves
)[2];
202 for (int i
= 0; i
< 8; i
++)
204 bool a_value
= (i
& 1) != 0;
205 bool b_value
= (i
& 2) != 0;
206 bool c_value
= (i
& 4) != 0;
209 ce
.set(A
, a_value
? State::S1
: State::S0
);
210 ce
.set(B
, b_value
? State::S1
: State::S0
);
211 ce
.set(C
, c_value
? State::S1
: State::S0
);
220 if (sig
== State::S1
)
226 // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root));
228 if (func
== xor3_func
|| func
== xnor3_func
)
229 xorxnor3
.insert(tuple
<SigBit
, SigBit
, SigBit
>(A
, B
, C
));
232 func3
[tuple
<SigBit
, SigBit
, SigBit
>(A
, B
, C
)][func
].insert(root
);
236 void find_partitions(SigBit root
, const pool
<SigBit
> &leaves
, pool
<const pool
<SigBit
>> &cache
, int maxdepth
, int maxbreadth
)
238 if (cache
.count(leaves
))
241 // log("%*s[%d] %s:", 20-maxdepth, "", maxdepth, log_signal(root));
242 // for (auto bit : leaves)
243 // log(" %s", log_signal(bit));
246 cache
.insert(leaves
);
247 check_partition(root
, leaves
);
252 for (SigBit bit
: leaves
)
254 if (driver
.count(bit
) == 0)
257 Cell
*cell
= driver
.at(bit
);
258 pool
<SigBit
> new_leaves
= leaves
;
260 new_leaves
.erase(bit
);
261 if (cell
->hasPort("\\A")) new_leaves
.insert(sigmap(SigBit(cell
->getPort("\\A"))));
262 if (cell
->hasPort("\\B")) new_leaves
.insert(sigmap(SigBit(cell
->getPort("\\B"))));
263 if (cell
->hasPort("\\C")) new_leaves
.insert(sigmap(SigBit(cell
->getPort("\\C"))));
264 if (cell
->hasPort("\\D")) new_leaves
.insert(sigmap(SigBit(cell
->getPort("\\D"))));
266 if (GetSize(new_leaves
) > maxbreadth
)
269 find_partitions(root
, new_leaves
, cache
, maxdepth
-1, maxbreadth
);
273 void assign_new_driver(SigBit bit
, SigBit new_driver
)
275 Cell
*cell
= driver
.at(bit
);
276 if (sigmap(cell
->getPort("\\Y")) == bit
) {
277 cell
->setPort("\\Y", module
->addWire(NEW_ID
));
278 module
->connect(bit
, new_driver
);
284 log("Extracting full/half adders from %s:\n", log_id(module
));
286 for (auto it
: driver
)
288 if (it
.second
->type
.in("$_BUF_", "$_NOT_"))
291 SigBit root
= it
.first
;
292 const pool
<SigBit
> leaves
= { root
};
293 pool
<const pool
<SigBit
>> cache
;
296 log(" checking %s\n", log_signal(it
.first
));
301 find_partitions(root
, leaves
, cache
, config
.maxdepth
, config
.maxbreadth
);
303 if (config
.verbose
&& count_func2
> 0)
304 log(" extracted %d two-input functions\n", count_func2
);
306 if (config
.verbose
&& count_func3
> 0)
307 log(" extracted %d three-input functions\n", count_func3
);
310 for (auto &key
: xorxnor3
)
312 SigBit A
= get
<0>(key
);
313 SigBit B
= get
<1>(key
);
314 SigBit C
= get
<2>(key
);
316 log(" 3-Input XOR/XNOR %s %s %s:\n", log_signal(A
), log_signal(B
), log_signal(C
));
318 for (auto &it
: func3
.at(key
))
320 if (it
.first
!= xor3_func
&& it
.first
!= xnor3_func
)
323 log(" %08d ->", bindec(it
.first
));
324 for (auto bit
: it
.second
)
325 log(" %s", log_signal(bit
));
329 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
331 for (auto &it
: func3_maj_info
)
334 auto f3i
= it
.second
;
336 if (func3
.at(key
).count(func
) == 0)
339 if (func3
.at(key
).count(xor3_func
) == 0 && func3
.at(key
).count(xnor3_func
) != 0) {
340 f3i
.inv_a
= !f3i
.inv_a
;
341 f3i
.inv_b
= !f3i
.inv_b
;
342 f3i
.inv_c
= !f3i
.inv_c
;
343 f3i
.inv_y
= !f3i
.inv_y
;
346 if (!f3i
.inv_a
&& !f3i
.inv_b
&& !f3i
.inv_c
&& !f3i
.inv_y
) {
347 log(" Majority without inversions:\n");
349 log(" Majority with inverted");
350 if (f3i
.inv_a
) log(" A");
351 if (f3i
.inv_b
) log(" B");
352 if (f3i
.inv_c
) log(" C");
353 if (f3i
.inv_y
) log(" Y");
357 log(" %08d ->", bindec(func
));
358 for (auto bit
: func3
.at(key
).at(func
))
359 log(" %s", log_signal(bit
));
363 if (f3i
.inv_a
) fakey
|= 1;
364 if (f3i
.inv_b
) fakey
|= 2;
365 if (f3i
.inv_c
) fakey
|= 4;
367 int fakey_inv
= fakey
^ 7;
368 bool invert_xy
= false;
371 if (facache
.count(fakey
))
373 auto &fa
= facache
.at(fakey
);
376 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
379 if (facache
.count(fakey_inv
))
381 auto &fa
= facache
.at(fakey_inv
);
385 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
389 Cell
*cell
= module
->addCell(NEW_ID
, "$fa");
390 cell
->setParam("\\WIDTH", 1);
392 log(" Created $fa cell %s.\n", log_id(cell
));
394 cell
->setPort("\\A", f3i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
395 cell
->setPort("\\B", f3i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
396 cell
->setPort("\\C", f3i
.inv_c
? module
->NotGate(NEW_ID
, C
) : C
);
398 X
= module
->addWire(NEW_ID
);
399 Y
= module
->addWire(NEW_ID
);
401 cell
->setPort("\\X", X
);
402 cell
->setPort("\\Y", Y
);
404 facache
[fakey
] = make_tuple(X
, Y
, cell
);
407 if (func3
.at(key
).count(xor3_func
)) {
408 SigBit YY
= invert_xy
? module
->NotGate(NEW_ID
, Y
) : Y
;
409 for (auto bit
: func3
.at(key
).at(xor3_func
))
410 assign_new_driver(bit
, YY
);
413 if (func3
.at(key
).count(xnor3_func
)) {
414 SigBit YY
= invert_xy
? Y
: module
->NotGate(NEW_ID
, Y
);
415 for (auto bit
: func3
.at(key
).at(xnor3_func
))
416 assign_new_driver(bit
, YY
);
419 SigBit XX
= invert_xy
!= f3i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
421 for (auto bit
: func3
.at(key
).at(func
))
422 assign_new_driver(bit
, XX
);
426 for (auto &key
: xorxnor2
)
428 SigBit A
= get
<0>(key
);
429 SigBit B
= get
<1>(key
);
431 log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A
), log_signal(B
));
433 for (auto &it
: func2
.at(key
))
435 if (it
.first
!= xor2_func
&& it
.first
!= xnor2_func
)
438 log(" %04d ->", bindec(it
.first
));
439 for (auto bit
: it
.second
)
440 log(" %s", log_signal(bit
));
444 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
446 for (auto &it
: func2_and_info
)
449 auto &f2i
= it
.second
;
451 if (func2
.at(key
).count(func
) == 0)
454 if (!f2i
.inv_a
&& !f2i
.inv_b
&& !f2i
.inv_y
) {
455 log(" AND without inversions:\n");
457 log(" AND with inverted");
458 if (f2i
.inv_a
) log(" A");
459 if (f2i
.inv_b
) log(" B");
460 if (f2i
.inv_y
) log(" Y");
464 log(" %04d ->", bindec(func
));
465 for (auto bit
: func2
.at(key
).at(func
))
466 log(" %s", log_signal(bit
));
470 if (f2i
.inv_a
) fakey
|= 1;
471 if (f2i
.inv_b
) fakey
|= 2;
473 int fakey_inv
= fakey
^ 3;
474 bool invert_xy
= false;
477 if (facache
.count(fakey
))
479 auto &fa
= facache
.at(fakey
);
482 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
485 if (facache
.count(fakey_inv
))
487 auto &fa
= facache
.at(fakey_inv
);
491 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
495 Cell
*cell
= module
->addCell(NEW_ID
, "$fa");
496 cell
->setParam("\\WIDTH", 1);
498 log(" Created $fa cell %s.\n", log_id(cell
));
500 cell
->setPort("\\A", f2i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
501 cell
->setPort("\\B", f2i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
502 cell
->setPort("\\C", State::S0
);
504 X
= module
->addWire(NEW_ID
);
505 Y
= module
->addWire(NEW_ID
);
507 cell
->setPort("\\X", X
);
508 cell
->setPort("\\Y", Y
);
511 if (func2
.at(key
).count(xor2_func
)) {
512 SigBit YY
= invert_xy
? module
->NotGate(NEW_ID
, Y
) : Y
;
513 for (auto bit
: func2
.at(key
).at(xor2_func
))
514 assign_new_driver(bit
, YY
);
517 if (func2
.at(key
).count(xnor2_func
)) {
518 SigBit YY
= invert_xy
? Y
: module
->NotGate(NEW_ID
, Y
);
519 for (auto bit
: func2
.at(key
).at(xnor2_func
))
520 assign_new_driver(bit
, YY
);
523 SigBit XX
= invert_xy
!= f2i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
525 for (auto bit
: func2
.at(key
).at(func
))
526 assign_new_driver(bit
, XX
);
532 struct ExtractFaPass
: public Pass
{
533 ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
534 void help() YS_OVERRIDE
536 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
538 log(" extract_fa [options] [selection]\n");
540 log("This pass extracts full/half adders from a gate-level design.\n");
543 log(" Enable cell types (fa=full adder, ha=half adder)\n");
544 log(" All types are enabled if none of this options is used\n");
547 log(" Set maximum depth for extracted logic cones (default=20)\n");
550 log(" Set maximum breadth for extracted logic cones (default=6)\n");
553 log(" Verbose output\n");
556 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
558 ExtractFaConfig config
;
560 log_header(design
, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
564 for (argidx
= 1; argidx
< args
.size(); argidx
++)
566 if (args
[argidx
] == "-fa") {
567 config
.enable_fa
= true;
570 if (args
[argidx
] == "-ha") {
571 config
.enable_ha
= true;
574 if (args
[argidx
] == "-v") {
575 config
.verbose
= true;
578 if (args
[argidx
] == "-d" && argidx
+2 < args
.size()) {
579 config
.maxdepth
= atoi(args
[++argidx
].c_str());
582 if (args
[argidx
] == "-b" && argidx
+2 < args
.size()) {
583 config
.maxbreadth
= atoi(args
[++argidx
].c_str());
588 extra_args(args
, argidx
, design
);
590 if (!config
.enable_fa
&& !config
.enable_ha
) {
591 config
.enable_fa
= true;
592 config
.enable_ha
= true;
595 for (auto module
: design
->selected_modules())
597 ExtractFaWorker
worker(config
, module
);
605 PRIVATE_NAMESPACE_END