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_",
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
, 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
);
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)
199 SigBit A
= SigSpec(leaves
)[0];
200 SigBit B
= SigSpec(leaves
)[1];
201 SigBit C
= SigSpec(leaves
)[2];
204 for (int i
= 0; i
< 8; i
++)
206 bool a_value
= (i
& 1) != 0;
207 bool b_value
= (i
& 2) != 0;
208 bool c_value
= (i
& 4) != 0;
211 ce
.set(A
, a_value
? State::S1
: State::S0
);
212 ce
.set(B
, b_value
? State::S1
: State::S0
);
213 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
, pool
<SigBit
> &leaves
, pool
<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 pool
<SigBit
> leaves
= { root
};
293 pool
<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 for (auto &it
: func3_maj_info
)
332 auto f3i
= it
.second
;
334 if (func3
.at(key
).count(func
) == 0)
337 if (func3
.at(key
).count(xor3_func
) == 0 && func3
.at(key
).count(xnor3_func
) != 0) {
338 f3i
.inv_a
= !f3i
.inv_a
;
339 f3i
.inv_b
= !f3i
.inv_b
;
340 f3i
.inv_c
= !f3i
.inv_c
;
341 f3i
.inv_y
= !f3i
.inv_y
;
344 if (!f3i
.inv_a
&& !f3i
.inv_b
&& !f3i
.inv_c
&& !f3i
.inv_y
) {
345 log(" Majority without inversions:\n");
347 log(" Majority with inverted");
348 if (f3i
.inv_a
) log(" A");
349 if (f3i
.inv_b
) log(" B");
350 if (f3i
.inv_c
) log(" C");
351 if (f3i
.inv_y
) log(" Y");
355 log(" %08d ->", bindec(func
));
356 for (auto bit
: func3
.at(key
).at(func
))
357 log(" %s", log_signal(bit
));
360 Cell
*cell
= module
->addCell(NEW_ID
, "$fa");
361 cell
->setParam("\\WIDTH", 1);
363 log(" Created $fa cell %s.\n", log_id(cell
));
365 cell
->setPort("\\A", f3i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
366 cell
->setPort("\\B", f3i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
367 cell
->setPort("\\C", f3i
.inv_c
? module
->NotGate(NEW_ID
, C
) : C
);
369 SigBit X
= module
->addWire(NEW_ID
);
370 SigBit Y
= module
->addWire(NEW_ID
);
372 cell
->setPort("\\X", X
);
373 cell
->setPort("\\Y", Y
);
375 if (func3
.at(key
).count(xor3_func
)) {
376 for (auto bit
: func3
.at(key
).at(xor3_func
))
377 assign_new_driver(bit
, Y
);
380 if (func3
.at(key
).count(xnor3_func
)) {
381 SigBit YN
= module
->NotGate(NEW_ID
, Y
);
382 for (auto bit
: func3
.at(key
).at(xnor3_func
))
383 assign_new_driver(bit
, YN
);
386 SigBit XX
= f3i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
388 for (auto bit
: func3
.at(key
).at(func
))
389 assign_new_driver(bit
, XX
);
393 for (auto &key
: xorxnor2
)
395 SigBit A
= get
<0>(key
);
396 SigBit B
= get
<1>(key
);
398 log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A
), log_signal(B
));
400 for (auto &it
: func2
.at(key
))
402 if (it
.first
!= xor2_func
&& it
.first
!= xnor2_func
)
405 log(" %04d ->", bindec(it
.first
));
406 for (auto bit
: it
.second
)
407 log(" %s", log_signal(bit
));
411 for (auto &it
: func2_and_info
)
414 auto &f2i
= it
.second
;
416 if (func2
.at(key
).count(func
) == 0)
419 if (!f2i
.inv_a
&& !f2i
.inv_b
&& !f2i
.inv_y
) {
420 log(" AND without inversions:\n");
422 log(" AND with inverted");
423 if (f2i
.inv_a
) log(" A");
424 if (f2i
.inv_b
) log(" B");
425 if (f2i
.inv_y
) log(" Y");
429 log(" %04d ->", bindec(func
));
430 for (auto bit
: func2
.at(key
).at(func
))
431 log(" %s", log_signal(bit
));
434 Cell
*cell
= module
->addCell(NEW_ID
, "$fa");
435 cell
->setParam("\\WIDTH", 1);
437 log(" Created $fa cell %s.\n", log_id(cell
));
439 cell
->setPort("\\A", f2i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
440 cell
->setPort("\\B", f2i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
441 cell
->setPort("\\C", State::S0
);
443 SigBit X
= module
->addWire(NEW_ID
);
444 SigBit Y
= module
->addWire(NEW_ID
);
446 cell
->setPort("\\X", X
);
447 cell
->setPort("\\Y", Y
);
449 if (func2
.at(key
).count(xor2_func
)) {
450 for (auto bit
: func2
.at(key
).at(xor2_func
))
451 assign_new_driver(bit
, Y
);
454 if (func2
.at(key
).count(xnor2_func
)) {
455 SigBit YN
= module
->NotGate(NEW_ID
, Y
);
456 for (auto bit
: func2
.at(key
).at(xnor2_func
))
457 assign_new_driver(bit
, YN
);
460 SigBit XX
= f2i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
462 for (auto bit
: func2
.at(key
).at(func
))
463 assign_new_driver(bit
, XX
);
469 struct ExtractFaPass
: public Pass
{
470 ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
473 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
475 log(" extract_fa [options] [selection]\n");
477 log("This pass extracts full/half adders from a gate-level design.\n");
480 log(" Enable cell types (fa=full adder, ha=half adder)\n");
481 log(" All types are enabled if none of this options is used\n");
484 log(" Set maximum depth for extracted logic cones (default=20)\n");
487 log(" Set maximum breadth for extracted logic cones (default=6)\n");
490 log(" Verbose output\n");
493 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
495 ExtractFaConfig config
;
497 log_header(design
, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
501 for (argidx
= 1; argidx
< args
.size(); argidx
++)
503 if (args
[argidx
] == "-fa") {
504 config
.enable_fa
= true;
507 if (args
[argidx
] == "-ha") {
508 config
.enable_ha
= true;
511 if (args
[argidx
] == "-v") {
512 config
.verbose
= true;
515 if (args
[argidx
] == "-d" && argidx
+2 < args
.size()) {
516 config
.maxdepth
= atoi(args
[++argidx
].c_str());
519 if (args
[argidx
] == "-b" && argidx
+2 < args
.size()) {
520 config
.maxbreadth
= atoi(args
[++argidx
].c_str());
525 extra_args(args
, argidx
, design
);
527 if (!config
.enable_fa
&& !config
.enable_ha
) {
528 config
.enable_fa
= true;
529 config
.enable_ha
= true;
532 for (auto module
: design
->selected_modules())
534 ExtractFaWorker
worker(config
, module
);
542 PRIVATE_NAMESPACE_END