2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 * 2019 Bogdan Vukobratovic <bogdan.vukobratovic@gmail.com>
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 #include "kernel/log.h"
22 #include "kernel/register.h"
23 #include "kernel/rtlil.h"
24 #include "kernel/sigtools.h"
31 PRIVATE_NAMESPACE_BEGIN
43 bool operator<(const OpMuxConn
&other
) const
46 return mux
< other
.mux
;
48 if (mux_port_id
!= other
.mux_port_id
)
49 return mux_port_id
< other
.mux_port_id
;
51 return mux_port_offset
< other
.mux_port_offset
;
55 // Helper class to track additiona information about a SigSpec, like whether it is signed and the semantics of the port it is connected to
60 RTLIL::IdString semantics
;
64 ExtSigSpec(RTLIL::SigSpec s
, RTLIL::SigSpec sign
= RTLIL::Const(0, 1), bool is_signed
= false, RTLIL::IdString semantics
= RTLIL::IdString()) : sig(s
), sign(sign
), is_signed(is_signed
), semantics(semantics
) {}
66 bool empty() const { return sig
.empty(); }
68 bool operator<(const ExtSigSpec
&other
) const
71 return sig
< other
.sig
;
73 if (sign
!= other
.sign
)
74 return sign
< other
.sign
;
76 if (is_signed
!= other
.is_signed
)
77 return is_signed
< other
.is_signed
;
79 return semantics
< other
.semantics
;
82 bool operator==(const RTLIL::SigSpec
&other
) const { return (sign
!= RTLIL::Const(0, 1)) ? false : sig
== other
; }
83 bool operator==(const ExtSigSpec
&other
) const { return is_signed
== other
.is_signed
&& sign
== other
.sign
&& sig
== other
.sig
&& semantics
== other
.semantics
; }
86 #define FINE_BITWISE_OPS ID($_AND_), ID($_NAND_), ID($_OR_), ID($_NOR_), ID($_XOR_), ID($_XNOR_), ID($_ANDNOT_), ID($_ORNOT_)
88 #define BITWISE_OPS FINE_BITWISE_OPS, ID($and), ID($or), ID($xor), ID($xnor)
90 #define REDUCTION_OPS ID($reduce_and), ID($reduce_or), ID($reduce_xor), ID($reduce_xnor), ID($reduce_bool), ID($reduce_nand)
92 #define LOGICAL_OPS ID($logic_and), ID($logic_or)
94 #define SHIFT_OPS ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx)
96 #define RELATIONAL_OPS ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt)
98 bool cell_supported(RTLIL::Cell
*cell
)
100 if (cell
->type
.in(ID($alu
))) {
101 RTLIL::SigSpec sig_bi
= cell
->getPort(ID::BI
);
102 RTLIL::SigSpec sig_ci
= cell
->getPort(ID::CI
);
104 if (sig_bi
.is_fully_const() && sig_ci
.is_fully_const() && sig_bi
== sig_ci
)
106 } else if (cell
->type
.in(LOGICAL_OPS
, SHIFT_OPS
, BITWISE_OPS
, RELATIONAL_OPS
, ID($add
), ID($sub
), ID($mul
), ID($div
), ID($mod
), ID($concat
))) {
113 std::map
<IdString
, IdString
> mergeable_type_map
;
115 bool mergeable(RTLIL::Cell
*a
, RTLIL::Cell
*b
)
117 if (mergeable_type_map
.empty()) {
118 mergeable_type_map
.insert({ID($sub
), ID($add
)});
120 auto a_type
= a
->type
;
121 if (mergeable_type_map
.count(a_type
))
122 a_type
= mergeable_type_map
.at(a_type
);
124 auto b_type
= b
->type
;
125 if (mergeable_type_map
.count(b_type
))
126 b_type
= mergeable_type_map
.at(b_type
);
128 return a_type
== b_type
;
131 RTLIL::IdString
decode_port_semantics(RTLIL::Cell
*cell
, RTLIL::IdString port_name
)
133 if (cell
->type
.in(ID($lt
), ID($le
), ID($ge
), ID($gt
), ID($div
), ID($mod
), ID($concat
), SHIFT_OPS
) && port_name
== ID::B
)
139 RTLIL::SigSpec
decode_port_sign(RTLIL::Cell
*cell
, RTLIL::IdString port_name
) {
141 if (cell
->type
== ID($alu
) && port_name
== ID::B
)
142 return cell
->getPort(ID::BI
);
143 else if (cell
->type
== ID($sub
) && port_name
== ID::B
)
144 return RTLIL::Const(1, 1);
146 return RTLIL::Const(0, 1);
149 bool decode_port_signed(RTLIL::Cell
*cell
, RTLIL::IdString port_name
)
151 if (cell
->type
.in(BITWISE_OPS
, LOGICAL_OPS
))
154 if (cell
->hasParam(port_name
.str() + "_SIGNED"))
155 return cell
->getParam(port_name
.str() + "_SIGNED").as_bool();
160 ExtSigSpec
decode_port(RTLIL::Cell
*cell
, RTLIL::IdString port_name
, SigMap
*sigmap
)
162 auto sig
= (*sigmap
)(cell
->getPort(port_name
));
164 RTLIL::SigSpec sign
= decode_port_sign(cell
, port_name
);
165 RTLIL::IdString semantics
= decode_port_semantics(cell
, port_name
);
167 bool is_signed
= decode_port_signed(cell
, port_name
);
169 return ExtSigSpec(sig
, sign
, is_signed
, semantics
);
172 void merge_operators(RTLIL::Module
*module
, RTLIL::Cell
*mux
, const std::vector
<OpMuxConn
> &ports
, const ExtSigSpec
&operand
)
174 std::vector
<ExtSigSpec
> muxed_operands
;
176 for (const auto& p
: ports
) {
179 RTLIL::IdString muxed_port_name
= ID::A
;
180 if (decode_port(op
, ID::A
, &assign_map
) == operand
)
181 muxed_port_name
= ID::B
;
183 auto operand
= decode_port(op
, muxed_port_name
, &assign_map
);
184 if (operand
.sig
.size() > max_width
)
185 max_width
= operand
.sig
.size();
187 muxed_operands
.push_back(operand
);
190 auto shared_op
= ports
[0].op
;
192 if (std::any_of(muxed_operands
.begin(), muxed_operands
.end(), [&](ExtSigSpec
&op
) { return op
.sign
!= muxed_operands
[0].sign
; }))
193 max_width
= std::max(max_width
, shared_op
->getParam(ID::Y_WIDTH
).as_int());
196 for (auto &operand
: muxed_operands
)
197 operand
.sig
.extend_u0(max_width
, operand
.is_signed
);
199 for (const auto& p
: ports
) {
206 for (auto &muxed_op
: muxed_operands
)
207 if (muxed_op
.sign
!= muxed_operands
[0].sign
)
208 muxed_op
= ExtSigSpec(module
->Neg(NEW_ID
, muxed_op
.sig
, muxed_op
.is_signed
));
210 RTLIL::SigSpec mux_y
= mux
->getPort(ID::Y
);
211 RTLIL::SigSpec mux_a
= mux
->getPort(ID::A
);
212 RTLIL::SigSpec mux_b
= mux
->getPort(ID::B
);
213 RTLIL::SigSpec mux_s
= mux
->getPort(ID::S
);
215 RTLIL::SigSpec shared_pmux_a
= RTLIL::Const(RTLIL::State::Sx
, max_width
);
216 RTLIL::SigSpec shared_pmux_b
;
217 RTLIL::SigSpec shared_pmux_s
;
219 int conn_width
= ports
[0].sig
.size();
220 int conn_offset
= ports
[0].mux_port_offset
;
222 shared_op
->setPort(ID::Y
, shared_op
->getPort(ID::Y
).extract(0, conn_width
));
224 if (mux
->type
== ID($pmux
)) {
225 shared_pmux_s
= RTLIL::SigSpec();
227 for (const auto &p
: ports
) {
228 shared_pmux_s
.append(mux_s
[p
.mux_port_id
]);
229 mux_b
.replace(p
.mux_port_id
* mux_a
.size() + conn_offset
, shared_op
->getPort(ID::Y
));
232 shared_pmux_s
= RTLIL::SigSpec
{mux_s
, module
->Not(NEW_ID
, mux_s
)};
233 mux_a
.replace(conn_offset
, shared_op
->getPort(ID::Y
));
234 mux_b
.replace(conn_offset
, shared_op
->getPort(ID::Y
));
237 mux
->setPort(ID::A
, mux_a
);
238 mux
->setPort(ID::B
, mux_b
);
239 mux
->setPort(ID::Y
, mux_y
);
240 mux
->setPort(ID::S
, mux_s
);
242 for (const auto &op
: muxed_operands
)
243 shared_pmux_b
.append(op
.sig
);
245 auto mux_to_oper
= module
->Pmux(NEW_ID
, shared_pmux_a
, shared_pmux_b
, shared_pmux_s
);
247 if (shared_op
->type
.in(ID($alu
))) {
248 RTLIL::SigSpec alu_x
= shared_op
->getPort(ID::X
);
249 RTLIL::SigSpec alu_co
= shared_op
->getPort(ID::CO
);
251 shared_op
->setPort(ID::X
, alu_x
.extract(0, conn_width
));
252 shared_op
->setPort(ID::CO
, alu_co
.extract(0, conn_width
));
255 bool is_fine
= shared_op
->type
.in(FINE_BITWISE_OPS
);
258 shared_op
->setParam(ID::Y_WIDTH
, conn_width
);
260 if (decode_port(shared_op
, ID::A
, &assign_map
) == operand
) {
261 shared_op
->setPort(ID::B
, mux_to_oper
);
263 shared_op
->setParam(ID::B_WIDTH
, max_width
);
265 shared_op
->setPort(ID::A
, mux_to_oper
);
267 shared_op
->setParam(ID::A_WIDTH
, max_width
);
273 std::vector
<OpMuxConn
> ports
;
274 ExtSigSpec shared_operand
;
278 template <typename T
> void remove_val(std::vector
<T
> &v
, const std::vector
<T
> &vals
)
280 auto val_iter
= vals
.rbegin();
281 for (auto i
= v
.rbegin(); i
!= v
.rend(); ++i
)
282 if ((val_iter
!= vals
.rend()) && (*i
== *val_iter
)) {
283 v
.erase(i
.base() - 1);
288 void check_muxed_operands(std::vector
<const OpMuxConn
*> &ports
, const ExtSigSpec
&shared_operand
)
290 auto it
= ports
.begin();
293 while (it
!= ports
.end()) {
297 RTLIL::IdString muxed_port_name
= ID::A
;
298 if (decode_port(op
, ID::A
, &assign_map
) == shared_operand
) {
299 muxed_port_name
= ID::B
;
302 auto operand
= decode_port(op
, muxed_port_name
, &assign_map
);
307 if (operand
.is_signed
!= seed
.is_signed
) {
315 ExtSigSpec
find_shared_operand(const OpMuxConn
* seed
, std::vector
<const OpMuxConn
*> &ports
, const std::map
<ExtSigSpec
, std::set
<RTLIL::Cell
*>> &operand_to_users
)
317 std::set
<RTLIL::Cell
*> ops_using_operand
;
318 std::set
<RTLIL::Cell
*> ops_set
;
319 for(const auto& p
: ports
)
320 ops_set
.insert(p
->op
);
324 auto op_a
= seed
->op
;
326 for (RTLIL::IdString port_name
: {ID::A
, ID::B
}) {
327 oper
= decode_port(op_a
, port_name
, &assign_map
);
328 auto operand_users
= operand_to_users
.at(oper
);
330 if (operand_users
.size() == 1)
333 ops_using_operand
.clear();
334 for (auto mux_ops
: ops_set
)
335 if (operand_users
.count(mux_ops
))
336 ops_using_operand
.insert(mux_ops
);
338 if (ops_using_operand
.size() > 1) {
339 ports
.erase(std::remove_if(ports
.begin(), ports
.end(), [&](const OpMuxConn
*p
) { return !ops_using_operand
.count(p
->op
); }),
348 dict
<RTLIL::SigSpec
, OpMuxConn
> find_valid_op_mux_conns(RTLIL::Module
*module
, dict
<RTLIL::SigBit
, RTLIL::SigSpec
> &op_outbit_to_outsig
,
349 dict
<RTLIL::SigSpec
, RTLIL::Cell
*> outsig_to_operator
,
350 dict
<RTLIL::SigBit
, RTLIL::SigSpec
> &op_aux_to_outsig
)
352 dict
<RTLIL::SigSpec
, int> op_outsig_user_track
;
353 dict
<RTLIL::SigSpec
, OpMuxConn
> op_mux_conn_map
;
355 std::function
<void(RTLIL::SigSpec
)> remove_outsig
= [&](RTLIL::SigSpec outsig
) {
356 for (auto op_outbit
: outsig
)
357 op_outbit_to_outsig
.erase(op_outbit
);
359 if (op_mux_conn_map
.count(outsig
))
360 op_mux_conn_map
.erase(outsig
);
363 std::function
<void(RTLIL::SigBit
)> remove_outsig_from_aux_bit
= [&](RTLIL::SigBit auxbit
) {
364 auto aux_outsig
= op_aux_to_outsig
.at(auxbit
);
365 auto op
= outsig_to_operator
.at(aux_outsig
);
366 auto op_outsig
= assign_map(op
->getPort(ID::Y
));
367 remove_outsig(op_outsig
);
369 for (auto aux_outbit
: aux_outsig
)
370 op_aux_to_outsig
.erase(aux_outbit
);
373 std::function
<void(RTLIL::Cell
*)> find_op_mux_conns
= [&](RTLIL::Cell
*mux
) {
377 if (mux
->type
.in(ID($mux
), ID($_MUX_
))) {
378 mux_port_size
= mux
->getPort(ID::A
).size();
379 sig
= RTLIL::SigSpec
{mux
->getPort(ID::B
), mux
->getPort(ID::A
)};
381 mux_port_size
= mux
->getPort(ID::A
).size();
382 sig
= mux
->getPort(ID::B
);
385 auto mux_insig
= assign_map(sig
);
387 for (int i
= 0; i
< mux_insig
.size(); ++i
) {
388 if (op_aux_to_outsig
.count(mux_insig
[i
])) {
389 remove_outsig_from_aux_bit(mux_insig
[i
]);
393 if (!op_outbit_to_outsig
.count(mux_insig
[i
]))
396 auto op_outsig
= op_outbit_to_outsig
.at(mux_insig
[i
]);
398 if (op_mux_conn_map
.count(op_outsig
)) {
399 remove_outsig(op_outsig
);
403 int mux_port_id
= i
/ mux_port_size
;
404 int mux_port_offset
= i
% mux_port_size
;
406 int op_outsig_offset
;
407 for (op_outsig_offset
= 0; op_outsig
[op_outsig_offset
] != mux_insig
[i
]; ++op_outsig_offset
)
410 int j
= op_outsig_offset
;
412 if (!op_outbit_to_outsig
.count(mux_insig
[i
]))
415 if (op_outbit_to_outsig
.at(mux_insig
[i
]) != op_outsig
)
420 } while ((i
/ mux_port_size
== mux_port_id
) && (j
< op_outsig
.size()));
422 int op_conn_width
= j
- op_outsig_offset
;
424 op_outsig
.extract(op_outsig_offset
, op_conn_width
),
426 outsig_to_operator
.at(op_outsig
),
432 op_mux_conn_map
[op_outsig
] = inp
;
438 std::function
<void(RTLIL::SigSpec
)> remove_connected_ops
= [&](RTLIL::SigSpec sig
) {
439 auto mux_insig
= assign_map(sig
);
440 for (auto outbit
: mux_insig
) {
441 if (op_aux_to_outsig
.count(outbit
)) {
442 remove_outsig_from_aux_bit(outbit
);
446 if (!op_outbit_to_outsig
.count(outbit
))
449 remove_outsig(op_outbit_to_outsig
.at(outbit
));
453 for (auto cell
: module
->cells()) {
454 if (cell
->type
.in(ID($mux
), ID($_MUX_
), ID($pmux
))) {
455 remove_connected_ops(cell
->getPort(ID::S
));
456 find_op_mux_conns(cell
);
458 for (auto &conn
: cell
->connections())
459 if (cell
->input(conn
.first
))
460 remove_connected_ops(conn
.second
);
464 for (auto w
: module
->wires()) {
468 remove_connected_ops(w
);
471 return op_mux_conn_map
;
474 struct OptSharePass
: public Pass
{
475 OptSharePass() : Pass("opt_share", "merge mutually exclusive cells of the same type that share an input signal") {}
476 void help() YS_OVERRIDE
478 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
480 log(" opt_share [selection]\n");
483 log("This pass identifies mutually exclusive cells of the same type that:\n");
484 log(" (a) share an input signal,\n");
485 log(" (b) drive the same $mux, $_MUX_, or $pmux multiplexing cell,\n");
487 log("allowing the cell to be merged and the multiplexer to be moved from\n");
488 log("multiplexing its output to multiplexing the non-shared input signals.\n");
491 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
494 log_header(design
, "Executing OPT_SHARE pass.\n");
496 extra_args(args
, 1, design
);
497 for (auto module
: design
->selected_modules()) {
499 assign_map
.set(module
);
501 std::map
<ExtSigSpec
, std::set
<RTLIL::Cell
*>> operand_to_users
;
502 dict
<RTLIL::SigSpec
, RTLIL::Cell
*> outsig_to_operator
;
503 dict
<RTLIL::SigBit
, RTLIL::SigSpec
> op_outbit_to_outsig
;
504 dict
<RTLIL::SigBit
, RTLIL::SigSpec
> op_aux_to_outsig
;
505 bool any_shared_operands
= false;
506 std::vector
<ExtSigSpec
> op_insigs
;
508 for (auto cell
: module
->cells()) {
509 if (!cell_supported(cell
))
512 if (cell
->type
== ID($alu
)) {
513 for (RTLIL::IdString port_name
: {ID::X
, ID::CO
}) {
514 auto mux_insig
= assign_map(cell
->getPort(port_name
));
515 outsig_to_operator
[mux_insig
] = cell
;
516 for (auto outbit
: mux_insig
)
517 op_aux_to_outsig
[outbit
] = mux_insig
;
521 auto mux_insig
= assign_map(cell
->getPort(ID::Y
));
522 outsig_to_operator
[mux_insig
] = cell
;
523 for (auto outbit
: mux_insig
)
524 op_outbit_to_outsig
[outbit
] = mux_insig
;
526 for (RTLIL::IdString port_name
: {ID::A
, ID::B
}) {
527 auto op_insig
= decode_port(cell
, port_name
, &assign_map
);
528 op_insigs
.push_back(op_insig
);
529 operand_to_users
[op_insig
].insert(cell
);
530 if (operand_to_users
[op_insig
].size() > 1)
531 any_shared_operands
= true;
535 if (!any_shared_operands
)
538 // Operator outputs need to be exclusively connected to the $mux inputs in order to be mergeable. Hence we count to
539 // how many points are operator output bits connected.
540 dict
<RTLIL::SigSpec
, OpMuxConn
> op_mux_conn_map
=
541 find_valid_op_mux_conns(module
, op_outbit_to_outsig
, outsig_to_operator
, op_aux_to_outsig
);
543 // Group op connections connected to same ports of the same $mux. Sort them in ascending order of their port offset
544 dict
<RTLIL::Cell
*, std::vector
<std::set
<OpMuxConn
>>> mux_port_op_conns
;
545 for (auto& val
: op_mux_conn_map
) {
546 OpMuxConn p
= val
.second
;
547 auto& mux_port_conns
= mux_port_op_conns
[p
.mux
];
549 if (mux_port_conns
.size() == 0) {
552 if (p
.mux
->type
.in(ID($mux
), ID($_MUX_
)))
555 mux_port_num
= p
.mux
->getPort(ID::S
).size();
557 mux_port_conns
.resize(mux_port_num
);
560 mux_port_conns
[p
.mux_port_id
].insert(p
);
563 std::vector
<merged_op_t
> merged_ops
;
564 for (auto& val
: mux_port_op_conns
) {
566 RTLIL::Cell
* cell
= val
.first
;
567 auto &mux_port_conns
= val
.second
;
569 const OpMuxConn
*seed
= NULL
;
571 // Look through the bits of the $mux inputs and see which of them are connected to the operator
572 // results. Operator results can be concatenated with other signals before led to the $mux.
575 // Remove either the merged ports from the last iteration or the seed that failed to yield a merger
577 mux_port_conns
[seed
->mux_port_id
].erase(*seed
);
581 // For a new merger, find the seed op connection that starts at lowest port offset among port connections
582 for (auto &port_conns
: mux_port_conns
) {
583 if (!port_conns
.size())
586 const OpMuxConn
*next_p
= &(*port_conns
.begin());
588 if ((seed
== NULL
) || (seed
->mux_port_offset
> next_p
->mux_port_offset
))
592 // Cannot find the seed -> nothing to do for this $mux anymore
596 // Find all other op connections that start from the same port offset, and whose ops can be merged with the seed op
597 std::vector
<const OpMuxConn
*> mergeable_conns
;
598 for (auto &port_conns
: mux_port_conns
) {
599 if (!port_conns
.size())
602 const OpMuxConn
*next_p
= &(*port_conns
.begin());
604 if ((next_p
->op_outsig_offset
== seed
->op_outsig_offset
) &&
605 (next_p
->mux_port_offset
== seed
->mux_port_offset
) && mergeable(next_p
->op
, seed
->op
) &&
606 next_p
->sig
.size() == seed
->sig
.size())
607 mergeable_conns
.push_back(next_p
);
610 // We need at least two mergeable connections for the merger
611 if (mergeable_conns
.size() < 2)
614 // Filter mergeable connections whose ops share an operand with seed connection's op
615 auto shared_operand
= find_shared_operand(seed
, mergeable_conns
, operand_to_users
);
617 if (shared_operand
.empty())
620 check_muxed_operands(mergeable_conns
, shared_operand
);
622 if (mergeable_conns
.size() < 2)
625 // Remember the combination for the merger
626 std::vector
<OpMuxConn
> merged_ports
;
627 for (auto p
: mergeable_conns
) {
628 merged_ports
.push_back(*p
);
629 mux_port_conns
[p
->mux_port_id
].erase(*p
);
634 merged_ops
.push_back(merged_op_t
{cell
, merged_ports
, shared_operand
});
636 design
->scratchpad_set_bool("opt.did_something", true);
641 for (auto &shared
: merged_ops
) {
642 log(" Found cells that share an operand and can be merged by moving the %s %s in front "
645 log_id(shared
.mux
->type
), log_id(shared
.mux
));
646 for (const auto& op
: shared
.ports
)
647 log(" %s\n", log_id(op
.op
));
650 merge_operators(module
, shared
.mux
, shared
.ports
, shared
.shared_operand
);
657 PRIVATE_NAMESPACE_END