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 for (auto port
: {ID::A
, ID::B
, ID(C
), ID(D
)}) {
266 if (!cell
->hasPort(port
))
268 auto bit
= sigmap(SigBit(cell
->getPort(port
)));
271 new_leaves
.insert(bit
);
274 if (GetSize(new_leaves
) > maxbreadth
)
277 find_partitions(root
, new_leaves
, cache
, maxdepth
-1, maxbreadth
);
281 void assign_new_driver(SigBit bit
, SigBit new_driver
)
283 Cell
*cell
= driver
.at(bit
);
284 if (sigmap(cell
->getPort(ID::Y
)) == bit
) {
285 cell
->setPort(ID::Y
, module
->addWire(NEW_ID
));
286 module
->connect(bit
, new_driver
);
292 log("Extracting full/half adders from %s:\n", log_id(module
));
294 for (auto it
: driver
)
296 if (it
.second
->type
.in(ID($_BUF_
), ID($_NOT_
)))
299 SigBit root
= it
.first
;
300 pool
<SigBit
> leaves
= { root
};
301 pool
<pool
<SigBit
>> cache
;
304 log(" checking %s\n", log_signal(it
.first
));
309 find_partitions(root
, leaves
, cache
, config
.maxdepth
, config
.maxbreadth
);
311 if (config
.verbose
&& count_func2
> 0)
312 log(" extracted %d two-input functions\n", count_func2
);
314 if (config
.verbose
&& count_func3
> 0)
315 log(" extracted %d three-input functions\n", count_func3
);
318 for (auto &key
: xorxnor3
)
320 SigBit A
= get
<0>(key
);
321 SigBit B
= get
<1>(key
);
322 SigBit C
= get
<2>(key
);
324 log(" 3-Input XOR/XNOR %s %s %s:\n", log_signal(A
), log_signal(B
), log_signal(C
));
326 for (auto &it
: func3
.at(key
))
328 if (it
.first
!= xor3_func
&& it
.first
!= xnor3_func
)
331 log(" %08d ->", bindec(it
.first
));
332 for (auto bit
: it
.second
)
333 log(" %s", log_signal(bit
));
337 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
339 for (auto &it
: func3_maj_info
)
342 auto f3i
= it
.second
;
344 if (func3
.at(key
).count(func
) == 0)
347 if (func3
.at(key
).count(xor3_func
) == 0 && func3
.at(key
).count(xnor3_func
) != 0) {
348 f3i
.inv_a
= !f3i
.inv_a
;
349 f3i
.inv_b
= !f3i
.inv_b
;
350 f3i
.inv_c
= !f3i
.inv_c
;
351 f3i
.inv_y
= !f3i
.inv_y
;
354 if (!f3i
.inv_a
&& !f3i
.inv_b
&& !f3i
.inv_c
&& !f3i
.inv_y
) {
355 log(" Majority without inversions:\n");
357 log(" Majority with inverted");
358 if (f3i
.inv_a
) log(" A");
359 if (f3i
.inv_b
) log(" B");
360 if (f3i
.inv_c
) log(" C");
361 if (f3i
.inv_y
) log(" Y");
365 log(" %08d ->", bindec(func
));
366 for (auto bit
: func3
.at(key
).at(func
))
367 log(" %s", log_signal(bit
));
371 if (f3i
.inv_a
) fakey
|= 1;
372 if (f3i
.inv_b
) fakey
|= 2;
373 if (f3i
.inv_c
) fakey
|= 4;
375 int fakey_inv
= fakey
^ 7;
376 bool invert_xy
= false;
379 if (facache
.count(fakey
))
381 auto &fa
= facache
.at(fakey
);
384 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
387 if (facache
.count(fakey_inv
))
389 auto &fa
= facache
.at(fakey_inv
);
393 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
397 Cell
*cell
= module
->addCell(NEW_ID
, ID($fa
));
398 cell
->setParam(ID(WIDTH
), 1);
400 log(" Created $fa cell %s.\n", log_id(cell
));
402 cell
->setPort(ID::A
, f3i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
403 cell
->setPort(ID::B
, f3i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
404 cell
->setPort(ID(C
), f3i
.inv_c
? module
->NotGate(NEW_ID
, C
) : C
);
406 X
= module
->addWire(NEW_ID
);
407 Y
= module
->addWire(NEW_ID
);
409 cell
->setPort(ID(X
), X
);
410 cell
->setPort(ID::Y
, Y
);
412 facache
[fakey
] = make_tuple(X
, Y
, cell
);
415 if (func3
.at(key
).count(xor3_func
)) {
416 SigBit YY
= invert_xy
? module
->NotGate(NEW_ID
, Y
) : Y
;
417 for (auto bit
: func3
.at(key
).at(xor3_func
))
418 assign_new_driver(bit
, YY
);
421 if (func3
.at(key
).count(xnor3_func
)) {
422 SigBit YY
= invert_xy
? Y
: module
->NotGate(NEW_ID
, Y
);
423 for (auto bit
: func3
.at(key
).at(xnor3_func
))
424 assign_new_driver(bit
, YY
);
427 SigBit XX
= invert_xy
!= f3i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
429 for (auto bit
: func3
.at(key
).at(func
))
430 assign_new_driver(bit
, XX
);
434 for (auto &key
: xorxnor2
)
436 SigBit A
= get
<0>(key
);
437 SigBit B
= get
<1>(key
);
439 log(" 2-Input XOR/XNOR %s %s:\n", log_signal(A
), log_signal(B
));
441 for (auto &it
: func2
.at(key
))
443 if (it
.first
!= xor2_func
&& it
.first
!= xnor2_func
)
446 log(" %04d ->", bindec(it
.first
));
447 for (auto bit
: it
.second
)
448 log(" %s", log_signal(bit
));
452 dict
<int, tuple
<SigBit
, SigBit
, Cell
*>> facache
;
454 for (auto &it
: func2_and_info
)
457 auto &f2i
= it
.second
;
459 if (func2
.at(key
).count(func
) == 0)
462 if (!f2i
.inv_a
&& !f2i
.inv_b
&& !f2i
.inv_y
) {
463 log(" AND without inversions:\n");
465 log(" AND with inverted");
466 if (f2i
.inv_a
) log(" A");
467 if (f2i
.inv_b
) log(" B");
468 if (f2i
.inv_y
) log(" Y");
472 log(" %04d ->", bindec(func
));
473 for (auto bit
: func2
.at(key
).at(func
))
474 log(" %s", log_signal(bit
));
478 if (f2i
.inv_a
) fakey
|= 1;
479 if (f2i
.inv_b
) fakey
|= 2;
481 int fakey_inv
= fakey
^ 3;
482 bool invert_xy
= false;
485 if (facache
.count(fakey
))
487 auto &fa
= facache
.at(fakey
);
490 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
493 if (facache
.count(fakey_inv
))
495 auto &fa
= facache
.at(fakey_inv
);
499 log(" Reusing $fa cell %s.\n", log_id(get
<2>(fa
)));
503 Cell
*cell
= module
->addCell(NEW_ID
, ID($fa
));
504 cell
->setParam(ID(WIDTH
), 1);
506 log(" Created $fa cell %s.\n", log_id(cell
));
508 cell
->setPort(ID::A
, f2i
.inv_a
? module
->NotGate(NEW_ID
, A
) : A
);
509 cell
->setPort(ID::B
, f2i
.inv_b
? module
->NotGate(NEW_ID
, B
) : B
);
510 cell
->setPort(ID(C
), State::S0
);
512 X
= module
->addWire(NEW_ID
);
513 Y
= module
->addWire(NEW_ID
);
515 cell
->setPort(ID(X
), X
);
516 cell
->setPort(ID::Y
, Y
);
519 if (func2
.at(key
).count(xor2_func
)) {
520 SigBit YY
= invert_xy
|| (f2i
.inv_a
&& !f2i
.inv_b
) || (!f2i
.inv_a
&& f2i
.inv_b
) ? module
->NotGate(NEW_ID
, Y
) : Y
;
521 for (auto bit
: func2
.at(key
).at(xor2_func
))
522 assign_new_driver(bit
, YY
);
525 if (func2
.at(key
).count(xnor2_func
)) {
526 SigBit YY
= invert_xy
|| (f2i
.inv_a
&& !f2i
.inv_b
) || (!f2i
.inv_a
&& f2i
.inv_b
) ? Y
: module
->NotGate(NEW_ID
, Y
);
527 for (auto bit
: func2
.at(key
).at(xnor2_func
))
528 assign_new_driver(bit
, YY
);
531 SigBit XX
= invert_xy
!= f2i
.inv_y
? module
->NotGate(NEW_ID
, X
) : X
;
533 for (auto bit
: func2
.at(key
).at(func
))
534 assign_new_driver(bit
, XX
);
540 struct ExtractFaPass
: public Pass
{
541 ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
542 void help() YS_OVERRIDE
544 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
546 log(" extract_fa [options] [selection]\n");
548 log("This pass extracts full/half adders from a gate-level design.\n");
551 log(" Enable cell types (fa=full adder, ha=half adder)\n");
552 log(" All types are enabled if none of this options is used\n");
555 log(" Set maximum depth for extracted logic cones (default=20)\n");
558 log(" Set maximum breadth for extracted logic cones (default=6)\n");
561 log(" Verbose output\n");
564 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
566 ExtractFaConfig config
;
568 log_header(design
, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
572 for (argidx
= 1; argidx
< args
.size(); argidx
++)
574 if (args
[argidx
] == "-fa") {
575 config
.enable_fa
= true;
578 if (args
[argidx
] == "-ha") {
579 config
.enable_ha
= true;
582 if (args
[argidx
] == "-v") {
583 config
.verbose
= true;
586 if (args
[argidx
] == "-d" && argidx
+2 < args
.size()) {
587 config
.maxdepth
= atoi(args
[++argidx
].c_str());
590 if (args
[argidx
] == "-b" && argidx
+2 < args
.size()) {
591 config
.maxbreadth
= atoi(args
[++argidx
].c_str());
596 extra_args(args
, argidx
, design
);
598 if (!config
.enable_fa
&& !config
.enable_ha
) {
599 config
.enable_fa
= true;
600 config
.enable_ha
= true;
603 for (auto module
: design
->selected_modules())
605 ExtractFaWorker
worker(config
, module
);
613 PRIVATE_NAMESPACE_END