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"
24 PRIVATE_NAMESPACE_BEGIN
31 bool initialized
= false;
33 pool
<SigBit
> init_ones
;
34 dict
<SigSpec
, pool
<SigSpec
>> sig_sources_db
;
35 dict
<SigSpec
, bool> sig_onehot_cache
;
36 pool
<SigSpec
> recursion_guard
;
38 OnehotDatabase(Module
*module
, const SigMap
&sigmap
) : module(module
), sigmap(sigmap
)
44 log_assert(!initialized
);
47 for (auto wire
: module
->wires())
49 auto it
= wire
->attributes
.find("\\init");
50 if (it
== wire
->attributes
.end())
53 auto &val
= it
->second
;
54 int width
= std::max(GetSize(wire
), GetSize(val
));
56 for (int i
= 0; i
< width
; i
++)
57 if (val
[i
] == State::S1
)
58 init_ones
.insert(sigmap(SigBit(wire
, i
)));
61 for (auto cell
: module
->cells())
63 vector
<SigSpec
> inputs
;
66 if (cell
->type
.in("$adff", "$dff", "$dffe", "$dlatch", "$ff"))
68 output
= cell
->getPort("\\Q");
69 if (cell
->type
== "$adff")
70 inputs
.push_back(cell
->getParam("\\ARST_VALUE"));
71 inputs
.push_back(cell
->getPort("\\D"));
74 if (cell
->type
.in("$mux", "$pmux"))
76 output
= cell
->getPort("\\Y");
77 inputs
.push_back(cell
->getPort("\\A"));
78 SigSpec B
= cell
->getPort("\\B");
79 for (int i
= 0; i
< GetSize(B
); i
+= GetSize(output
))
80 inputs
.push_back(B
.extract(i
, GetSize(output
)));
85 output
= sigmap(output
);
86 auto &srcs
= sig_sources_db
[output
];
87 for (auto src
: inputs
) {
88 while (!src
.empty() && src
[GetSize(src
)-1] == State::S0
)
89 src
.remove(GetSize(src
)-1);
90 srcs
.insert(sigmap(src
));
96 void query_worker(const SigSpec
&sig
, bool &retval
, bool &cache
, int indent
)
99 log("%*s %s\n", indent
, "", log_signal(sig
));
102 if (recursion_guard
.count(sig
)) {
104 log("%*s - recursion\n", indent
, "");
109 auto it
= sig_onehot_cache
.find(sig
);
110 if (it
!= sig_onehot_cache
.end()) {
112 log("%*s - cached (%s)\n", indent
, "", it
->second
? "true" : "false");
118 bool found_init_ones
= false;
119 for (auto bit
: sig
) {
120 if (init_ones
.count(bit
)) {
121 if (found_init_ones
) {
123 log("%*s - non-onehot init value\n", indent
, "");
127 found_init_ones
= true;
133 if (sig
.is_fully_const())
135 bool found_ones
= false;
136 for (auto bit
: sig
) {
137 if (bit
== State::S1
) {
140 log("%*s - non-onehot constant\n", indent
, "");
150 auto srcs
= sig_sources_db
.find(sig
);
151 if (srcs
== sig_sources_db
.end()) {
153 log("%*s - no sources for non-const signal\n", indent
, "");
156 for (auto &src
: srcs
->second
) {
157 bool child_cache
= true;
158 recursion_guard
.insert(sig
);
159 query_worker(src
, retval
, child_cache
, indent
+4);
160 recursion_guard
.erase(sig
);
170 // it is always safe to cache a negative result
171 if (cache
|| !retval
)
172 sig_onehot_cache
[sig
] = retval
;
175 bool query(const SigSpec
&sig
)
181 log("** ONEHOT QUERY START (%s)\n", log_signal(sig
));
186 query_worker(sig
, retval
, cache
, 3);
189 log("** ONEHOT QUERY RESULT = %s\n", retval
? "true" : "false");
191 // it is always safe to cache the root result of a query
193 sig_onehot_cache
[sig
] = retval
;
199 struct Pmux2ShiftxPass
: public Pass
{
200 Pmux2ShiftxPass() : Pass("pmux2shiftx", "transform $pmux cells to $shiftx cells") { }
201 void help() YS_OVERRIDE
203 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
205 log(" pmux2shiftx [options] [selection]\n");
207 log("This pass transforms $pmux cells to $shiftx cells.\n");
210 log(" verbose output\n");
212 log(" -min_density <percentage>\n");
213 log(" specifies the minimum density for the shifter\n");
214 log(" default: 50\n");
216 log(" -min_choices <int>\n");
217 log(" specified the minimum number of choices for a control signal\n");
218 log(" default: 3\n");
220 log(" -onehot ignore|pmux|shiftx\n");
221 log(" select strategy for one-hot encoded control signals\n");
222 log(" default: pmux\n");
225 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
227 int min_density
= 50;
229 bool allow_onehot
= false;
230 bool optimize_onehot
= true;
231 bool verbose
= false;
232 bool verbose_onehot
= false;
234 log_header(design
, "Executing PMUX2SHIFTX pass.\n");
237 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
238 if (args
[argidx
] == "-min_density" && argidx
+1 < args
.size()) {
239 min_density
= atoi(args
[++argidx
].c_str());
242 if (args
[argidx
] == "-min_choices" && argidx
+1 < args
.size()) {
243 min_choices
= atoi(args
[++argidx
].c_str());
246 if (args
[argidx
] == "-onehot" && argidx
+1 < args
.size() && args
[argidx
+1] == "ignore") {
248 allow_onehot
= false;
249 optimize_onehot
= false;
252 if (args
[argidx
] == "-onehot" && argidx
+1 < args
.size() && args
[argidx
+1] == "pmux") {
254 allow_onehot
= false;
255 optimize_onehot
= true;
258 if (args
[argidx
] == "-onehot" && argidx
+1 < args
.size() && args
[argidx
+1] == "shiftx") {
261 optimize_onehot
= false;
264 if (args
[argidx
] == "-v") {
268 if (args
[argidx
] == "-vv") {
270 verbose_onehot
= true;
275 extra_args(args
, argidx
, design
);
277 for (auto module
: design
->selected_modules())
279 SigMap
sigmap(module
);
280 OnehotDatabase
onehot_db(module
, sigmap
);
281 onehot_db
.verbose
= verbose_onehot
;
283 dict
<SigBit
, pair
<SigSpec
, Const
>> eqdb
;
285 for (auto cell
: module
->cells())
287 if (cell
->type
== "$eq")
289 dict
<SigBit
, State
> bits
;
291 SigSpec A
= sigmap(cell
->getPort("\\A"));
292 SigSpec B
= sigmap(cell
->getPort("\\B"));
294 int a_width
= cell
->getParam("\\A_WIDTH").as_int();
295 int b_width
= cell
->getParam("\\B_WIDTH").as_int();
297 if (a_width
< b_width
) {
298 bool a_signed
= cell
->getParam("\\A_SIGNED").as_int();
299 A
.extend_u0(b_width
, a_signed
);
302 if (b_width
< a_width
) {
303 bool b_signed
= cell
->getParam("\\B_SIGNED").as_int();
304 B
.extend_u0(a_width
, b_signed
);
307 for (int i
= 0; i
< GetSize(A
); i
++) {
308 SigBit a_bit
= A
[i
], b_bit
= B
[i
];
309 if (b_bit
.wire
&& !a_bit
.wire
) {
310 std::swap(a_bit
, b_bit
);
312 if (!a_bit
.wire
|| b_bit
.wire
)
314 if (bits
.count(a_bit
))
316 bits
[a_bit
] = b_bit
.data
;
319 if (GetSize(bits
) > 20)
323 pair
<SigSpec
, Const
> entry
;
325 for (auto it
: bits
) {
326 entry
.first
.append_bit(it
.first
);
327 entry
.second
.bits
.push_back(it
.second
);
330 eqdb
[sigmap(cell
->getPort("\\Y")[0])] = entry
;
334 if (cell
->type
== "$logic_not")
336 dict
<SigBit
, State
> bits
;
338 SigSpec A
= sigmap(cell
->getPort("\\A"));
340 for (int i
= 0; i
< GetSize(A
); i
++)
341 bits
[A
[i
]] = State::S0
;
344 pair
<SigSpec
, Const
> entry
;
346 for (auto it
: bits
) {
347 entry
.first
.append_bit(it
.first
);
348 entry
.second
.bits
.push_back(it
.second
);
351 eqdb
[sigmap(cell
->getPort("\\Y")[0])] = entry
;
357 for (auto cell
: module
->selected_cells())
359 if (cell
->type
!= "$pmux")
362 string src
= cell
->get_src_attribute();
363 int width
= cell
->getParam("\\WIDTH").as_int();
364 int width_bits
= ceil_log2(width
);
365 int extwidth
= width
;
367 while (extwidth
& (extwidth
-1))
370 dict
<SigSpec
, pool
<int>> seldb
;
372 SigSpec A
= cell
->getPort("\\A");
373 SigSpec B
= cell
->getPort("\\B");
374 SigSpec S
= sigmap(cell
->getPort("\\S"));
375 for (int i
= 0; i
< GetSize(S
); i
++)
377 if (!eqdb
.count(S
[i
]))
380 auto &entry
= eqdb
.at(S
[i
]);
381 seldb
[entry
.first
].insert(i
);
387 bool printed_pmux_header
= false;
390 printed_pmux_header
= true;
391 log("Inspecting $pmux cell %s/%s.\n", log_id(module
), log_id(cell
));
392 log(" data width: %d (next power-of-2 = %d, log2 = %d)\n", width
, extwidth
, width_bits
);
395 SigSpec updated_S
= cell
->getPort("\\S");
396 SigSpec updated_B
= cell
->getPort("\\B");
398 while (!seldb
.empty())
400 // pick the largest entry in seldb
401 SigSpec sig
= seldb
.begin()->first
;
402 for (auto &it
: seldb
) {
403 if (GetSize(sig
) < GetSize(it
.first
))
405 else if (GetSize(seldb
.at(sig
)) < GetSize(it
.second
))
409 // find the relevant choices
410 bool is_onehot
= GetSize(sig
) > 2;
411 dict
<Const
, int> choices
;
412 for (int i
: seldb
.at(sig
)) {
413 Const val
= eqdb
.at(S
[i
]).second
;
415 for (auto b
: val
.bits
)
423 bool full_pmux
= GetSize(choices
) == GetSize(S
);
425 // TBD: also find choices that are using signals that are subsets of the bits in "sig"
429 if (is_onehot
&& !allow_onehot
&& !optimize_onehot
) {
434 if (GetSize(choices
) < min_choices
) {
440 if (!printed_pmux_header
) {
441 printed_pmux_header
= true;
442 log("Inspecting $pmux cell %s/%s.\n", log_id(module
), log_id(cell
));
443 log(" data width: %d (next power-of-2 = %d, log2 = %d)\n", width
, extwidth
, width_bits
);
446 log(" checking ctrl signal %s\n", log_signal(sig
));
448 auto print_choices
= [&]() {
449 log(" table of choices:\n");
450 for (auto &it
: choices
)
451 log(" %3d: %s: %s\n", it
.second
, log_signal(it
.first
),
452 log_signal(B
.extract(it
.second
*width
, width
)));
457 if (is_onehot
&& !allow_onehot
&& !optimize_onehot
) {
459 log(" ignoring one-hot encoding.\n");
464 if (GetSize(choices
) < min_choices
) {
466 log(" insufficient choices.\n");
472 if (is_onehot
&& optimize_onehot
)
475 if (!onehot_db
.query(sig
))
477 log(" failed to detect onehot driver. do not optimize.\n");
481 log(" optimizing one-hot encoding.\n");
482 for (auto &it
: choices
)
484 const Const
&val
= it
.first
;
487 for (int i
= 0; i
< GetSize(val
); i
++)
488 if (val
[i
] == State::S1
) {
489 log_assert(index
< 0);
494 log(" %3d: zero encoding.\n", it
.second
);
498 SigBit new_ctrl
= sig
[index
];
499 log(" %3d: new crtl signal is %s.\n", it
.second
, log_signal(new_ctrl
));
500 updated_S
[it
.second
] = new_ctrl
;
507 // find the best permutation
508 vector
<int> perm_new_from_old(GetSize(sig
));
509 Const
perm_xormask(State::S0
, GetSize(sig
));
511 vector
<int> values(GetSize(choices
));
512 vector
<bool> used_src_columns(GetSize(sig
));
513 vector
<vector
<bool>> columns(GetSize(sig
), vector
<bool>(GetSize(values
)));
515 for (int i
= 0; i
< GetSize(choices
); i
++) {
516 Const val
= choices
.element(i
)->first
;
517 for (int k
= 0; k
< GetSize(val
); k
++)
518 if (val
[k
] == State::S1
)
519 columns
[k
][i
] = true;
522 for (int dst_col
= GetSize(sig
)-1; dst_col
>= 0; dst_col
--)
524 int best_src_col
= -1;
525 bool best_inv
= false;
529 // find best src column for this dst column
530 for (int src_col
= 0; src_col
< GetSize(sig
); src_col
++)
532 if (used_src_columns
[src_col
])
536 int this_minval
= 1 << 30;
538 int this_inv_maxval
= 0;
539 int this_inv_minval
= 1 << 30;
541 for (int i
= 0; i
< GetSize(values
); i
++)
546 if (columns
[src_col
][i
])
549 inv_val
|= 1 << dst_col
;
551 this_maxval
= std::max(this_maxval
, val
);
552 this_minval
= std::min(this_minval
, val
);
554 this_inv_maxval
= std::max(this_inv_maxval
, inv_val
);
555 this_inv_minval
= std::min(this_inv_minval
, inv_val
);
558 int this_delta
= this_maxval
- this_minval
;
559 int this_inv_delta
= this_maxval
- this_minval
;
560 bool this_inv
= false;
562 if (this_delta
!= this_inv_delta
)
563 this_inv
= this_inv_delta
< this_delta
;
564 else if (this_maxval
!= this_inv_maxval
)
565 this_inv
= this_inv_maxval
< this_maxval
;
568 this_delta
= this_inv_delta
;
569 this_maxval
= this_inv_maxval
;
570 this_minval
= this_inv_minval
;
573 bool this_is_better
= false;
575 if (best_src_col
< 0)
576 this_is_better
= true;
577 else if (this_delta
!= best_delta
)
578 this_is_better
= this_delta
< best_delta
;
579 else if (this_maxval
!= best_maxval
)
580 this_is_better
= this_maxval
< best_maxval
;
582 this_is_better
= sig
[best_src_col
] < sig
[src_col
];
584 if (this_is_better
) {
585 best_src_col
= src_col
;
587 best_maxval
= this_maxval
;
588 best_delta
= this_delta
;
592 used_src_columns
[best_src_col
] = true;
593 perm_new_from_old
[dst_col
] = best_src_col
;
594 perm_xormask
[dst_col
] = best_inv
? State::S1
: State::S0
;
599 SigSpec
perm_sig(State::S0
, GetSize(sig
));
600 for (int i
= 0; i
< GetSize(sig
); i
++)
601 perm_sig
[i
] = sig
[perm_new_from_old
[i
]];
603 log(" best permutation: %s\n", log_signal(perm_sig
));
604 log(" best xor mask: %s\n", log_signal(perm_xormask
));
606 // permutated choices
607 int min_choice
= 1 << 30;
609 dict
<Const
, int> perm_choices
;
611 for (auto &it
: choices
)
613 Const
&old_c
= it
.first
;
614 Const
new_c(State::S0
, GetSize(old_c
));
616 for (int i
= 0; i
< GetSize(old_c
); i
++)
617 new_c
[i
] = old_c
[perm_new_from_old
[i
]];
619 Const new_c_before_xor
= new_c
;
620 new_c
= const_xor(new_c
, perm_xormask
, false, false, GetSize(new_c
));
622 perm_choices
[new_c
] = it
.second
;
624 min_choice
= std::min(min_choice
, new_c
.as_int());
625 max_choice
= std::max(max_choice
, new_c
.as_int());
627 log(" %3d: %s -> %s -> %s: %s\n", it
.second
, log_signal(old_c
), log_signal(new_c_before_xor
),
628 log_signal(new_c
), log_signal(B
.extract(it
.second
*width
, width
)));
631 int range_density
= 100*GetSize(choices
) / (max_choice
-min_choice
+1);
632 int absolute_density
= 100*GetSize(choices
) / (max_choice
+1);
634 log(" choices: %d\n", GetSize(choices
));
635 log(" min choice: %d\n", min_choice
);
636 log(" max choice: %d\n", max_choice
);
637 log(" range density: %d%%\n", range_density
);
638 log(" absolute density: %d%%\n", absolute_density
);
641 int full_density
= 100*GetSize(choices
) / (1 << GetSize(sig
));
642 log(" full density: %d%%\n", full_density
);
643 if (full_density
< min_density
) {
647 max_choice
= (1 << GetSize(sig
))-1;
648 log(" update to full case.\n");
649 log(" new min choice: %d\n", min_choice
);
650 log(" new max choice: %d\n", max_choice
);
654 bool full_case
= (min_choice
== 0) && (max_choice
== (1 << GetSize(sig
))-1) && (full_pmux
|| max_choice
+1 == GetSize(choices
));
655 log(" full case: %s\n", full_case
? "true" : "false");
657 // check density percentages
658 Const
offset(State::S0
, GetSize(sig
));
659 if (absolute_density
< min_density
&& range_density
>= min_density
)
661 offset
= Const(min_choice
, GetSize(sig
));
662 log(" offset: %s\n", log_signal(offset
));
664 min_choice
-= offset
.as_int();
665 max_choice
-= offset
.as_int();
667 dict
<Const
, int> new_perm_choices
;
668 for (auto &it
: perm_choices
)
669 new_perm_choices
[const_sub(it
.first
, offset
, false, false, GetSize(sig
))] = it
.second
;
670 perm_choices
.swap(new_perm_choices
);
672 if (absolute_density
< min_density
) {
673 log(" insufficient density.\n");
679 SigSpec cmp
= perm_sig
;
680 if (perm_xormask
.as_bool())
681 cmp
= module
->Xor(NEW_ID
, cmp
, perm_xormask
, false, src
);
682 if (offset
.as_bool())
683 cmp
= module
->Sub(NEW_ID
, cmp
, offset
, false, src
);
685 // create enable signal
686 SigBit en
= State::S1
;
688 Const
enable_mask(State::S0
, max_choice
+1);
689 for (auto &it
: perm_choices
)
690 enable_mask
[it
.first
.as_int()] = State::S1
;
691 en
= module
->addWire(NEW_ID
);
692 module
->addShift(NEW_ID
, enable_mask
, cmp
, en
, false, src
);
695 // create data signal
696 SigSpec
data(State::Sx
, (max_choice
+1)*extwidth
);
698 for (int i
= 0; i
<= max_choice
; i
++)
699 data
.replace(i
*extwidth
, A
);
701 for (auto &it
: perm_choices
) {
702 int position
= it
.first
.as_int()*extwidth
;
703 int data_index
= it
.second
;
704 data
.replace(position
, B
.extract(data_index
*width
, width
));
705 updated_S
[data_index
] = State::S0
;
706 updated_B
.replace(data_index
*width
, SigSpec(State::Sx
, width
));
709 // create shiftx cell
710 SigSpec shifted_cmp
= {cmp
, SigSpec(State::S0
, width_bits
)};
711 SigSpec outsig
= module
->addWire(NEW_ID
, width
);
712 Cell
*c
= module
->addShiftx(NEW_ID
, data
, shifted_cmp
, outsig
, false, src
);
713 updated_S
.append(en
);
714 updated_B
.append(outsig
);
715 log(" created $shiftx cell %s.\n", log_id(c
));
717 // remove this sig and continue with the next block
722 cell
->setPort("\\S", updated_S
);
723 cell
->setPort("\\B", updated_B
);
724 cell
->setParam("\\S_WIDTH", GetSize(updated_S
));
730 struct OnehotPass
: public Pass
{
731 OnehotPass() : Pass("onehot", "optimize $eq cells for onehot signals") { }
732 void help() YS_OVERRIDE
734 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
736 log(" onehot [options] [selection]\n");
738 log("This pass optimizes $eq cells that compare one-hot signals against constants\n");
741 log(" verbose output\n");
744 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
746 bool verbose
= false;
747 bool verbose_onehot
= false;
749 log_header(design
, "Executing ONEHOT pass.\n");
752 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
753 if (args
[argidx
] == "-v") {
757 if (args
[argidx
] == "-vv") {
759 verbose_onehot
= true;
764 extra_args(args
, argidx
, design
);
766 for (auto module
: design
->selected_modules())
768 SigMap
sigmap(module
);
769 OnehotDatabase
onehot_db(module
, sigmap
);
770 onehot_db
.verbose
= verbose_onehot
;
772 for (auto cell
: module
->selected_cells())
774 if (cell
->type
!= "$eq")
777 SigSpec A
= sigmap(cell
->getPort("\\A"));
778 SigSpec B
= sigmap(cell
->getPort("\\B"));
780 int a_width
= cell
->getParam("\\A_WIDTH").as_int();
781 int b_width
= cell
->getParam("\\B_WIDTH").as_int();
783 if (a_width
< b_width
) {
784 bool a_signed
= cell
->getParam("\\A_SIGNED").as_int();
785 A
.extend_u0(b_width
, a_signed
);
788 if (b_width
< a_width
) {
789 bool b_signed
= cell
->getParam("\\B_SIGNED").as_int();
790 B
.extend_u0(a_width
, b_signed
);
793 if (A
.is_fully_const())
796 if (!B
.is_fully_const())
800 log("Checking $eq(%s, %s) cell %s/%s.\n", log_signal(A
), log_signal(B
), log_id(module
), log_id(cell
));
802 if (!onehot_db
.query(A
)) {
804 log(" onehot driver test on %s failed.\n", log_signal(A
));
809 bool not_onehot
= false;
811 for (int i
= 0; i
< GetSize(B
); i
++) {
812 if (B
[i
] != State::S1
)
821 log(" not optimizing the zero pattern.\n");
825 SigSpec Y
= cell
->getPort("\\Y");
830 log(" replacing with constant 0 driver.\n");
832 log("Replacing one-hot $eq(%s, %s) cell %s/%s with constant 0 driver.\n", log_signal(A
), log_signal(B
), log_id(module
), log_id(cell
));
833 module
->connect(Y
, SigSpec(1, GetSize(Y
)));
837 SigSpec sig
= A
[index
];
839 log(" replacing with signal %s.\n", log_signal(sig
));
841 log("Replacing one-hot $eq(%s, %s) cell %s/%s with signal %s.\n",log_signal(A
), log_signal(B
), log_id(module
), log_id(cell
), log_signal(sig
));
842 sig
.extend_u0(GetSize(Y
));
843 module
->connect(Y
, sig
);
846 module
->remove(cell
);
852 PRIVATE_NAMESPACE_END