1 /*
2 * yosys -- Yosys Open SYnthesis Suite
3 *
4 * Copyright (C) 2012 Claire Xenia Wolf <claire@yosyshq.com>
5 * 2019 Bogdan Vukobratovic <bogdan.vukobratovic@gmail.com>
6 *
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.
10 *
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.
18 *
19 */
20
21 #include "kernel/log.h"
22 #include "kernel/register.h"
23 #include "kernel/rtlil.h"
24 #include "kernel/sigtools.h"
25 #include <algorithm>
26
27 #include <stdio.h>
28 #include <stdlib.h>
29
30 USING_YOSYS_NAMESPACE
31 PRIVATE_NAMESPACE_BEGIN
32
33 struct OpMuxConn {
34 RTLIL::SigSpec sig;
35 RTLIL::Cell *mux;
36 RTLIL::Cell *op;
37 int mux_port_id;
38 int mux_port_offset;
39 int op_outsig_offset;
40
operator <OpMuxConn41 bool operator<(const OpMuxConn &other) const
42 {
43 if (mux != other.mux)
44 return mux < other.mux;
45
46 if (mux_port_id != other.mux_port_id)
47 return mux_port_id < other.mux_port_id;
48
49 return mux_port_offset < other.mux_port_offset;
50 }
51 };
52
53 // Helper class to track additiona information about a SigSpec, like whether it is signed and the semantics of the port it is connected to
54 struct ExtSigSpec {
55 RTLIL::SigSpec sig;
56 RTLIL::SigSpec sign;
57 bool is_signed;
58 RTLIL::IdString semantics;
59
ExtSigSpecExtSigSpec60 ExtSigSpec() {}
61
ExtSigSpecExtSigSpec62 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) {}
63
emptyExtSigSpec64 bool empty() const { return sig.empty(); }
65
operator <ExtSigSpec66 bool operator<(const ExtSigSpec &other) const
67 {
68 if (sig != other.sig)
69 return sig < other.sig;
70
71 if (sign != other.sign)
72 return sign < other.sign;
73
74 if (is_signed != other.is_signed)
75 return is_signed < other.is_signed;
76
77 return semantics < other.semantics;
78 }
79
operator ==ExtSigSpec80 bool operator==(const RTLIL::SigSpec &other) const { return (sign != RTLIL::Const(0, 1)) ? false : sig == other; }
operator ==ExtSigSpec81 bool operator==(const ExtSigSpec &other) const { return is_signed == other.is_signed && sign == other.sign && sig == other.sig && semantics == other.semantics; }
82 };
83
84 #define FINE_BITWISE_OPS ID($_AND_), ID($_NAND_), ID($_OR_), ID($_NOR_), ID($_XOR_), ID($_XNOR_), ID($_ANDNOT_), ID($_ORNOT_)
85
86 #define BITWISE_OPS FINE_BITWISE_OPS, ID($and), ID($or), ID($xor), ID($xnor)
87
88 #define REDUCTION_OPS ID($reduce_and), ID($reduce_or), ID($reduce_xor), ID($reduce_xnor), ID($reduce_bool), ID($reduce_nand)
89
90 #define LOGICAL_OPS ID($logic_and), ID($logic_or)
91
92 #define SHIFT_OPS ID($shl), ID($shr), ID($sshl), ID($sshr), ID($shift), ID($shiftx)
93
94 #define RELATIONAL_OPS ID($lt), ID($le), ID($eq), ID($ne), ID($eqx), ID($nex), ID($ge), ID($gt)
95
cell_supported(RTLIL::Cell * cell)96 bool cell_supported(RTLIL::Cell *cell)
97 {
98 if (cell->type.in(ID($alu))) {
99 RTLIL::SigSpec sig_bi = cell->getPort(ID::BI);
100 RTLIL::SigSpec sig_ci = cell->getPort(ID::CI);
101
102 if (sig_bi.is_fully_const() && sig_ci.is_fully_const() && sig_bi == sig_ci)
103 return true;
104 } else if (cell->type.in(LOGICAL_OPS, SHIFT_OPS, BITWISE_OPS, RELATIONAL_OPS, ID($add), ID($sub), ID($mul), ID($div), ID($mod), ID($divfloor), ID($modfloor), ID($concat))) {
105 return true;
106 }
107
108 return false;
109 }
110
111 std::map<IdString, IdString> mergeable_type_map;
112
mergeable(RTLIL::Cell * a,RTLIL::Cell * b)113 bool mergeable(RTLIL::Cell *a, RTLIL::Cell *b)
114 {
115 if (mergeable_type_map.empty()) {
116 mergeable_type_map.insert({ID($sub), ID($add)});
117 }
118 auto a_type = a->type;
119 if (mergeable_type_map.count(a_type))
120 a_type = mergeable_type_map.at(a_type);
121
122 auto b_type = b->type;
123 if (mergeable_type_map.count(b_type))
124 b_type = mergeable_type_map.at(b_type);
125
126 return a_type == b_type;
127 }
128
decode_port_semantics(RTLIL::Cell * cell,RTLIL::IdString port_name)129 RTLIL::IdString decode_port_semantics(RTLIL::Cell *cell, RTLIL::IdString port_name)
130 {
131 if (cell->type.in(ID($lt), ID($le), ID($ge), ID($gt), ID($div), ID($mod), ID($divfloor), ID($modfloor), ID($concat), SHIFT_OPS) && port_name == ID::B)
132 return port_name;
133
134 return "";
135 }
136
decode_port_sign(RTLIL::Cell * cell,RTLIL::IdString port_name)137 RTLIL::SigSpec decode_port_sign(RTLIL::Cell *cell, RTLIL::IdString port_name) {
138
139 if (cell->type == ID($alu) && port_name == ID::B)
140 return cell->getPort(ID::BI);
141 else if (cell->type == ID($sub) && port_name == ID::B)
142 return RTLIL::Const(1, 1);
143
144 return RTLIL::Const(0, 1);
145 }
146
decode_port_signed(RTLIL::Cell * cell,RTLIL::IdString port_name)147 bool decode_port_signed(RTLIL::Cell *cell, RTLIL::IdString port_name)
148 {
149 if (cell->type.in(BITWISE_OPS, LOGICAL_OPS))
150 return false;
151
152 if (cell->hasParam(port_name.str() + "_SIGNED"))
153 return cell->getParam(port_name.str() + "_SIGNED").as_bool();
154
155 return false;
156 }
157
decode_port(RTLIL::Cell * cell,RTLIL::IdString port_name,const SigMap & sigmap)158 ExtSigSpec decode_port(RTLIL::Cell *cell, RTLIL::IdString port_name, const SigMap &sigmap)
159 {
160 auto sig = sigmap(cell->getPort(port_name));
161
162 RTLIL::SigSpec sign = decode_port_sign(cell, port_name);
163 RTLIL::IdString semantics = decode_port_semantics(cell, port_name);
164
165 bool is_signed = decode_port_signed(cell, port_name);
166
167 return ExtSigSpec(sig, sign, is_signed, semantics);
168 }
169
merge_operators(RTLIL::Module * module,RTLIL::Cell * mux,const std::vector<OpMuxConn> & ports,const ExtSigSpec & operand,const SigMap & sigmap)170 void merge_operators(RTLIL::Module *module, RTLIL::Cell *mux, const std::vector<OpMuxConn> &ports, const ExtSigSpec &operand, const SigMap &sigmap)
171 {
172 std::vector<ExtSigSpec> muxed_operands;
173 int max_width = 0;
174 for (const auto& p : ports) {
175 auto op = p.op;
176
177 RTLIL::IdString muxed_port_name = ID::A;
178 if (decode_port(op, ID::A, sigmap) == operand)
179 muxed_port_name = ID::B;
180
181 auto operand = decode_port(op, muxed_port_name, sigmap);
182 if (operand.sig.size() > max_width)
183 max_width = operand.sig.size();
184
185 muxed_operands.push_back(operand);
186 }
187
188 auto shared_op = ports[0].op;
189
190 if (std::any_of(muxed_operands.begin(), muxed_operands.end(), [&](ExtSigSpec &op) { return op.sign != muxed_operands[0].sign; }))
191 max_width = std::max(max_width, shared_op->getParam(ID::Y_WIDTH).as_int());
192
193 for (auto &operand : muxed_operands) {
194 operand.sig.extend_u0(max_width, operand.is_signed);
195 if (operand.sign != muxed_operands[0].sign)
196 operand = ExtSigSpec(module->Neg(NEW_ID, operand.sig, operand.is_signed));
197 }
198
199 for (const auto& p : ports) {
200 auto op = p.op;
201 if (op == shared_op)
202 continue;
203 module->remove(op);
204 }
205
206 RTLIL::SigSpec mux_a = mux->getPort(ID::A);
207 RTLIL::SigSpec mux_b = mux->getPort(ID::B);
208 RTLIL::SigSpec mux_s = mux->getPort(ID::S);
209
210 int conn_width = ports[0].sig.size();
211 int conn_mux_offset = ports[0].mux_port_offset;
212 int conn_op_offset = ports[0].op_outsig_offset;
213
214 RTLIL::SigSpec shared_pmux_a = RTLIL::Const(RTLIL::State::Sx, max_width);
215 RTLIL::SigSpec shared_pmux_b;
216 RTLIL::SigSpec shared_pmux_s;
217
218 // Make a new wire to avoid false equivalence with whatever the former shared output was connected to.
219 Wire *new_out = module->addWire(NEW_ID, conn_op_offset + conn_width);
220 SigSpec new_sig_out = SigSpec(new_out, conn_op_offset, conn_width);
221
222 for (int i = 0; i < GetSize(ports); i++) {
223 auto &p = ports[i];
224 auto &op = muxed_operands[i];
225 if (p.mux_port_id == GetSize(mux_s)) {
226 shared_pmux_a = op.sig;
227 mux_a.replace(conn_mux_offset, new_sig_out);
228 } else {
229 shared_pmux_s.append(mux_s[p.mux_port_id]);
230 shared_pmux_b.append(op.sig);
231 mux_b.replace(p.mux_port_id * mux_a.size() + conn_mux_offset, new_sig_out);
232 }
233 }
234
235 mux->setPort(ID::A, mux_a);
236 mux->setPort(ID::B, mux_b);
237 mux->setPort(ID::S, mux_s);
238
239 SigSpec mux_to_oper;
240 if (GetSize(shared_pmux_s) == 1) {
241 mux_to_oper = module->Mux(NEW_ID, shared_pmux_a, shared_pmux_b, shared_pmux_s);
242 } else {
243 mux_to_oper = module->Pmux(NEW_ID, shared_pmux_a, shared_pmux_b, shared_pmux_s);
244 }
245
246 if (shared_op->type.in(ID($alu))) {
247 shared_op->setPort(ID::X, module->addWire(NEW_ID, GetSize(new_out)));
248 shared_op->setPort(ID::CO, module->addWire(NEW_ID, GetSize(new_out)));
249 }
250
251 bool is_fine = shared_op->type.in(FINE_BITWISE_OPS);
252
253 shared_op->setPort(ID::Y, new_out);
254 if (!is_fine)
255 shared_op->setParam(ID::Y_WIDTH, GetSize(new_out));
256
257 if (decode_port(shared_op, ID::A, sigmap) == operand) {
258 shared_op->setPort(ID::B, mux_to_oper);
259 if (!is_fine)
260 shared_op->setParam(ID::B_WIDTH, max_width);
261 } else {
262 shared_op->setPort(ID::A, mux_to_oper);
263 if (!is_fine)
264 shared_op->setParam(ID::A_WIDTH, max_width);
265 }
266 }
267
268 typedef struct {
269 RTLIL::Cell *mux;
270 std::vector<OpMuxConn> ports;
271 ExtSigSpec shared_operand;
272 } merged_op_t;
273
274
check_muxed_operands(std::vector<const OpMuxConn * > & ports,const ExtSigSpec & shared_operand,const SigMap & sigmap)275 void check_muxed_operands(std::vector<const OpMuxConn *> &ports, const ExtSigSpec &shared_operand, const SigMap &sigmap)
276 {
277 auto it = ports.begin();
278 ExtSigSpec seed;
279
280 while (it != ports.end()) {
281 auto p = *it;
282 auto op = p->op;
283
284 RTLIL::IdString muxed_port_name = ID::A;
285 if (decode_port(op, ID::A, sigmap) == shared_operand) {
286 muxed_port_name = ID::B;
287 }
288
289 auto operand = decode_port(op, muxed_port_name, sigmap);
290
291 if (seed.empty())
292 seed = operand;
293
294 if (operand.is_signed != seed.is_signed) {
295 ports.erase(it);
296 } else {
297 ++it;
298 }
299 }
300 }
301
find_shared_operand(const OpMuxConn * seed,std::vector<const OpMuxConn * > & ports,const std::map<ExtSigSpec,std::set<RTLIL::Cell * >> & operand_to_users,const SigMap & sigmap)302 ExtSigSpec find_shared_operand(const OpMuxConn* seed, std::vector<const OpMuxConn *> &ports, const std::map<ExtSigSpec, std::set<RTLIL::Cell *>> &operand_to_users, const SigMap &sigmap)
303 {
304 std::set<RTLIL::Cell *> ops_using_operand;
305 std::set<RTLIL::Cell *> ops_set;
306 for(const auto& p: ports)
307 ops_set.insert(p->op);
308
309 ExtSigSpec oper;
310
311 auto op_a = seed->op;
312
313 for (RTLIL::IdString port_name : {ID::A, ID::B}) {
314 oper = decode_port(op_a, port_name, sigmap);
315 auto operand_users = operand_to_users.at(oper);
316
317 if (operand_users.size() == 1)
318 continue;
319
320 ops_using_operand.clear();
321 for (auto mux_ops: ops_set)
322 if (operand_users.count(mux_ops))
323 ops_using_operand.insert(mux_ops);
324
325 if (ops_using_operand.size() > 1) {
326 ports.erase(std::remove_if(ports.begin(), ports.end(), [&](const OpMuxConn *p) { return !ops_using_operand.count(p->op); }),
327 ports.end());
328 return oper;
329 }
330 }
331
332 return ExtSigSpec();
333 }
334
335 struct OptSharePass : public Pass {
OptSharePassOptSharePass336 OptSharePass() : Pass("opt_share", "merge mutually exclusive cells of the same type that share an input signal") {}
helpOptSharePass337 void help() override
338 {
339 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
340 log("\n");
341 log(" opt_share [selection]\n");
342 log("\n");
343
344 log("This pass identifies mutually exclusive cells of the same type that:\n");
345 log(" (a) share an input signal,\n");
346 log(" (b) drive the same $mux, $_MUX_, or $pmux multiplexing cell,\n");
347 log("\n");
348 log("allowing the cell to be merged and the multiplexer to be moved from\n");
349 log("multiplexing its output to multiplexing the non-shared input signals.\n");
350 log("\n");
351 }
executeOptSharePass352 void execute(std::vector<std::string> args, RTLIL::Design *design) override
353 {
354
355 log_header(design, "Executing OPT_SHARE pass.\n");
356
357 extra_args(args, 1, design);
358 for (auto module : design->selected_modules()) {
359 SigMap sigmap(module);
360
361 dict<RTLIL::SigBit, int> bit_users;
362
363 for (auto cell : module->cells())
364 for (auto conn : cell->connections())
365 for (auto bit : conn.second)
366 bit_users[sigmap(bit)]++;
367
368 for (auto wire : module->wires())
369 if (wire->port_id != 0)
370 for (auto bit : SigSpec(wire))
371 bit_users[sigmap(bit)]++;
372
373 std::map<ExtSigSpec, std::set<RTLIL::Cell *>> operand_to_users;
374 dict<RTLIL::SigBit, std::pair<RTLIL::Cell *, int>> op_outbit_to_outsig;
375 bool any_shared_operands = false;
376
377 for (auto cell : module->selected_cells()) {
378 if (!cell_supported(cell))
379 continue;
380
381 bool skip = false;
382 if (cell->type == ID($alu)) {
383 for (RTLIL::IdString port_name : {ID::X, ID::CO}) {
384 for (auto outbit : sigmap(cell->getPort(port_name)))
385 if (bit_users[outbit] > 1)
386 skip = true;
387 }
388 }
389
390 if (skip)
391 continue;
392
393 auto mux_insig = sigmap(cell->getPort(ID::Y));
394 for (int i = 0; i < GetSize(mux_insig); i++)
395 op_outbit_to_outsig[mux_insig[i]] = std::make_pair(cell, i);
396
397 for (RTLIL::IdString port_name : {ID::A, ID::B}) {
398 auto op_insig = decode_port(cell, port_name, sigmap);
399 operand_to_users[op_insig].insert(cell);
400 if (operand_to_users[op_insig].size() > 1)
401 any_shared_operands = true;
402 }
403 }
404
405 if (!any_shared_operands)
406 continue;
407
408 // Operator outputs need to be exclusively connected to the $mux inputs in order to be mergeable. Hence we count to
409 // how many points are operator output bits connected.
410 std::vector<merged_op_t> merged_ops;
411
412 for (auto mux : module->selected_cells()) {
413 if (!mux->type.in(ID($mux), ID($_MUX_), ID($pmux)))
414 continue;
415
416 int mux_port_size = GetSize(mux->getPort(ID::A));
417 int mux_port_num = GetSize(mux->getPort(ID::S)) + 1;
418
419 RTLIL::SigSpec mux_insig = sigmap(RTLIL::SigSpec{mux->getPort(ID::B), mux->getPort(ID::A)});
420 std::vector<std::set<OpMuxConn>> mux_port_conns(mux_port_num);
421 int found = 0;
422
423 for (int mux_port_id = 0; mux_port_id < mux_port_num; mux_port_id++) {
424 SigSpec mux_insig;
425 if (mux_port_id == mux_port_num - 1) {
426 mux_insig = sigmap(mux->getPort(ID::A));
427 } else {
428 mux_insig = sigmap(mux->getPort(ID::B).extract(mux_port_id * mux_port_size, mux_port_size));
429 }
430
431 for (int mux_port_offset = 0; mux_port_offset < mux_port_size; ++mux_port_offset) {
432 if (!op_outbit_to_outsig.count(mux_insig[mux_port_offset]))
433 continue;
434
435 RTLIL::Cell *cell;
436 int op_outsig_offset;
437 std::tie(cell, op_outsig_offset) = op_outbit_to_outsig.at(mux_insig[mux_port_offset]);
438 SigSpec op_outsig = sigmap(cell->getPort(ID::Y));
439 int op_outsig_size = GetSize(op_outsig);
440 int op_conn_width = 0;
441
442 while (mux_port_offset + op_conn_width < mux_port_size &&
443 op_outsig_offset + op_conn_width < op_outsig_size &&
444 mux_insig[mux_port_offset + op_conn_width] == op_outsig[op_outsig_offset + op_conn_width])
445 op_conn_width++;
446
447 log_assert(op_conn_width >= 1);
448
449 bool skip = false;
450 for (int i = 0; i < op_outsig_size; i++) {
451 int expected = 1;
452 if (i >= op_outsig_offset && i < op_outsig_offset + op_conn_width)
453 expected = 2;
454 if (bit_users[op_outsig[i]] != expected)
455 skip = true;
456 }
457 if (skip) {
458 mux_port_offset += op_conn_width;
459 mux_port_offset--;
460 continue;
461 }
462
463 OpMuxConn inp = {
464 op_outsig.extract(op_outsig_offset, op_conn_width),
465 mux,
466 cell,
467 mux_port_id,
468 mux_port_offset,
469 op_outsig_offset,
470 };
471
472 mux_port_conns[mux_port_id].insert(inp);
473
474 mux_port_offset += op_conn_width;
475 mux_port_offset--;
476
477 found++;
478 }
479 }
480
481 if (found < 2)
482 continue;
483
484 const OpMuxConn *seed = NULL;
485
486 // Look through the bits of the $mux inputs and see which of them are connected to the operator
487 // results. Operator results can be concatenated with other signals before led to the $mux.
488 while (true) {
489
490 // Remove either the merged ports from the last iteration or the seed that failed to yield a merger
491 if (seed != NULL) {
492 mux_port_conns[seed->mux_port_id].erase(*seed);
493 seed = NULL;
494 }
495
496 // For a new merger, find the seed op connection that starts at lowest port offset among port connections
497 for (auto &port_conns : mux_port_conns) {
498 if (!port_conns.size())
499 continue;
500
501 const OpMuxConn *next_p = &(*port_conns.begin());
502
503 if ((seed == NULL) || (seed->mux_port_offset > next_p->mux_port_offset))
504 seed = next_p;
505 }
506
507 // Cannot find the seed -> nothing to do for this $mux anymore
508 if (seed == NULL)
509 break;
510
511 // Find all other op connections that start from the same port offset, and whose ops can be merged with the seed op
512 std::vector<const OpMuxConn *> mergeable_conns;
513 for (auto &port_conns : mux_port_conns) {
514 if (!port_conns.size())
515 continue;
516
517 const OpMuxConn *next_p = &(*port_conns.begin());
518
519 if ((next_p->op_outsig_offset == seed->op_outsig_offset) &&
520 (next_p->mux_port_offset == seed->mux_port_offset) && mergeable(next_p->op, seed->op) &&
521 next_p->sig.size() == seed->sig.size())
522 mergeable_conns.push_back(next_p);
523 }
524
525 // We need at least two mergeable connections for the merger
526 if (mergeable_conns.size() < 2)
527 continue;
528
529 // Filter mergeable connections whose ops share an operand with seed connection's op
530 auto shared_operand = find_shared_operand(seed, mergeable_conns, operand_to_users, sigmap);
531
532 if (shared_operand.empty())
533 continue;
534
535 check_muxed_operands(mergeable_conns, shared_operand, sigmap);
536
537 if (mergeable_conns.size() < 2)
538 continue;
539
540 // Remember the combination for the merger
541 std::vector<OpMuxConn> merged_ports;
542 for (auto p : mergeable_conns) {
543 merged_ports.push_back(*p);
544 mux_port_conns[p->mux_port_id].erase(*p);
545 }
546
547 seed = NULL;
548
549 merged_ops.push_back(merged_op_t{mux, merged_ports, shared_operand});
550
551 design->scratchpad_set_bool("opt.did_something", true);
552 }
553
554 }
555
556 for (auto &shared : merged_ops) {
557 log(" Found cells that share an operand and can be merged by moving the %s %s in front "
558 "of "
559 "them:\n",
560 log_id(shared.mux->type), log_id(shared.mux));
561 for (const auto& op : shared.ports)
562 log(" %s\n", log_id(op.op));
563 log("\n");
564
565 merge_operators(module, shared.mux, shared.ports, shared.shared_operand, sigmap);
566 }
567 }
568 }
569
570 } OptSharePass;
571
572 PRIVATE_NAMESPACE_END
573