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/satgen.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/modtools.h"
24 #include "kernel/utils.h"
25 #include "kernel/macc.h"
28 PRIVATE_NAMESPACE_BEGIN
30 typedef RTLIL::IdString::compare_ptr_by_name
<RTLIL::Cell
> cell_ptr_cmp
;
31 typedef std::pair
<RTLIL::SigSpec
, RTLIL::Const
> ssc_pair_t
;
33 struct ShareWorkerConfig
39 pool
<RTLIL::IdString
> generic_uni_ops
, generic_bin_ops
, generic_cbin_ops
, generic_other_ops
;
44 ShareWorkerConfig config
;
45 pool
<RTLIL::IdString
> generic_ops
;
47 RTLIL::Design
*design
;
48 RTLIL::Module
*module
;
50 CellTypes fwd_ct
, cone_ct
;
54 pool
<RTLIL::Cell
*> cells_to_remove
;
55 pool
<RTLIL::Cell
*> recursion_state
;
58 std::map
<RTLIL::Cell
*, std::set
<RTLIL::Cell
*, cell_ptr_cmp
>, cell_ptr_cmp
> topo_cell_drivers
;
59 std::map
<RTLIL::SigBit
, std::set
<RTLIL::Cell
*, cell_ptr_cmp
>> topo_bit_drivers
;
61 std::vector
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>> exclusive_ctrls
;
64 // ------------------------------------------------------------------------------
65 // Find terminal bits -- i.e. bits that do not (exclusively) feed into a mux tree
66 // ------------------------------------------------------------------------------
68 pool
<RTLIL::SigBit
> terminal_bits
;
70 void find_terminal_bits()
72 pool
<RTLIL::SigBit
> queue_bits
;
73 pool
<RTLIL::Cell
*> visited_cells
;
75 queue_bits
.insert(modwalker
.signal_outputs
.begin(), modwalker
.signal_outputs
.end());
77 for (auto &it
: module
->cells_
)
78 if (!fwd_ct
.cell_known(it
.second
->type
)) {
79 pool
<RTLIL::SigBit
> &bits
= modwalker
.cell_inputs
[it
.second
];
80 queue_bits
.insert(bits
.begin(), bits
.end());
83 terminal_bits
.insert(queue_bits
.begin(), queue_bits
.end());
85 while (!queue_bits
.empty())
87 pool
<ModWalker::PortBit
> portbits
;
88 modwalker
.get_drivers(portbits
, queue_bits
);
91 for (auto &pbit
: portbits
) {
92 if (pbit
.cell
->type
== "$mux" || pbit
.cell
->type
== "$pmux") {
93 pool
<RTLIL::SigBit
> bits
= modwalker
.sigmap(pbit
.cell
->getPort("\\S")).to_sigbit_pool();
94 terminal_bits
.insert(bits
.begin(), bits
.end());
95 queue_bits
.insert(bits
.begin(), bits
.end());
96 visited_cells
.insert(pbit
.cell
);
98 if (fwd_ct
.cell_known(pbit
.cell
->type
) && visited_cells
.count(pbit
.cell
) == 0) {
99 pool
<RTLIL::SigBit
> &bits
= modwalker
.cell_inputs
[pbit
.cell
];
100 terminal_bits
.insert(bits
.begin(), bits
.end());
101 queue_bits
.insert(bits
.begin(), bits
.end());
102 visited_cells
.insert(pbit
.cell
);
109 // ---------------------------------------------------
110 // Code for sharing and comparing MACC cells
111 // ---------------------------------------------------
113 static int bits_macc_port(const Macc::port_t
&p
, int width
)
115 if (GetSize(p
.in_a
) == 0 || GetSize(p
.in_b
) == 0)
116 return min(max(GetSize(p
.in_a
), GetSize(p
.in_b
)), width
);
117 return min(GetSize(p
.in_a
), width
) * min(GetSize(p
.in_b
), width
) / 2;
120 static int bits_macc(const Macc
&m
, int width
)
122 int bits
= GetSize(m
.bit_ports
);
123 for (auto &p
: m
.ports
)
124 bits
+= bits_macc_port(p
, width
);
128 static int bits_macc(RTLIL::Cell
*c
)
131 int width
= GetSize(c
->getPort("\\Y"));
132 return bits_macc(m
, width
);
135 static bool cmp_macc_ports(const Macc::port_t
&p1
, const Macc::port_t
&p2
)
137 bool mul1
= GetSize(p1
.in_a
) && GetSize(p1
.in_b
);
138 bool mul2
= GetSize(p2
.in_a
) && GetSize(p2
.in_b
);
140 int w1
= mul1
? GetSize(p1
.in_a
) * GetSize(p1
.in_b
) : GetSize(p1
.in_a
) + GetSize(p1
.in_b
);
141 int w2
= mul2
? GetSize(p2
.in_a
) * GetSize(p2
.in_b
) : GetSize(p2
.in_a
) + GetSize(p2
.in_b
);
149 if (p1
.is_signed
!= p2
.is_signed
)
150 return p1
.is_signed
< p2
.is_signed
;
152 if (p1
.do_subtract
!= p2
.do_subtract
)
153 return p1
.do_subtract
< p2
.do_subtract
;
155 if (p1
.in_a
!= p2
.in_a
)
156 return p1
.in_a
< p2
.in_a
;
158 if (p1
.in_b
!= p2
.in_b
)
159 return p1
.in_b
< p2
.in_b
;
164 int share_macc_ports(Macc::port_t
&p1
, Macc::port_t
&p2
, int w1
, int w2
,
165 RTLIL::SigSpec act
= RTLIL::SigSpec(), Macc
*supermacc
= nullptr, pool
<RTLIL::Cell
*> *supercell_aux
= nullptr)
167 if (p1
.do_subtract
!= p2
.do_subtract
)
170 bool mul1
= GetSize(p1
.in_a
) && GetSize(p1
.in_b
);
171 bool mul2
= GetSize(p2
.in_a
) && GetSize(p2
.in_b
);
176 bool force_signed
= false, force_not_signed
= false;
178 if ((GetSize(p1
.in_a
) && GetSize(p1
.in_a
) < w1
) || (GetSize(p1
.in_b
) && GetSize(p1
.in_b
) < w1
)) {
182 force_not_signed
= true;
185 if ((GetSize(p2
.in_a
) && GetSize(p2
.in_a
) < w2
) || (GetSize(p2
.in_b
) && GetSize(p2
.in_b
) < w2
)) {
189 force_not_signed
= true;
192 if (force_signed
&& force_not_signed
)
197 RTLIL::SigSpec sig_a1
= p1
.in_a
, sig_b1
= p1
.in_b
;
198 RTLIL::SigSpec sig_a2
= p2
.in_a
, sig_b2
= p2
.in_b
;
200 RTLIL::SigSpec sig_a
= GetSize(sig_a1
) > GetSize(sig_a2
) ? sig_a1
: sig_a2
;
201 RTLIL::SigSpec sig_b
= GetSize(sig_b1
) > GetSize(sig_b2
) ? sig_b1
: sig_b2
;
203 sig_a1
.extend_u0(GetSize(sig_a
), p1
.is_signed
);
204 sig_b1
.extend_u0(GetSize(sig_b
), p1
.is_signed
);
206 sig_a2
.extend_u0(GetSize(sig_a
), p2
.is_signed
);
207 sig_b2
.extend_u0(GetSize(sig_b
), p2
.is_signed
);
209 if (supercell_aux
&& GetSize(sig_a
)) {
210 sig_a
= module
->addWire(NEW_ID
, GetSize(sig_a
));
211 supercell_aux
->insert(module
->addMux(NEW_ID
, sig_a2
, sig_a1
, act
, sig_a
));
214 if (supercell_aux
&& GetSize(sig_b
)) {
215 sig_b
= module
->addWire(NEW_ID
, GetSize(sig_b
));
216 supercell_aux
->insert(module
->addMux(NEW_ID
, sig_b2
, sig_b1
, act
, sig_b
));
222 p
.is_signed
= force_signed
;
223 p
.do_subtract
= p1
.do_subtract
;
224 supermacc
->ports
.push_back(p
);
227 int score
= 1000 + abs(GetSize(p1
.in_a
) - GetSize(p2
.in_a
)) * max(abs(GetSize(p1
.in_b
) - GetSize(p2
.in_b
)), 1);
229 for (int i
= 0; i
< min(GetSize(p1
.in_a
), GetSize(p2
.in_a
)); i
++)
230 if (p1
.in_a
[i
] == p2
.in_a
[i
] && score
> 0)
233 for (int i
= 0; i
< min(GetSize(p1
.in_b
), GetSize(p2
.in_b
)); i
++)
234 if (p1
.in_b
[i
] == p2
.in_b
[i
] && score
> 0)
240 int share_macc(RTLIL::Cell
*c1
, RTLIL::Cell
*c2
,
241 RTLIL::SigSpec act
= RTLIL::SigSpec(), RTLIL::Cell
*supercell
= nullptr, pool
<RTLIL::Cell
*> *supercell_aux
= nullptr)
243 Macc
m1(c1
), m2(c2
), supermacc
;
245 int w1
= GetSize(c1
->getPort("\\Y")), w2
= GetSize(c2
->getPort("\\Y"));
246 int width
= max(w1
, w2
);
251 std::sort(m1
.ports
.begin(), m1
.ports
.end(), cmp_macc_ports
);
252 std::sort(m2
.ports
.begin(), m2
.ports
.end(), cmp_macc_ports
);
254 std::set
<int> m1_unmapped
, m2_unmapped
;
256 for (int i
= 0; i
< GetSize(m1
.ports
); i
++)
257 m1_unmapped
.insert(i
);
259 for (int i
= 0; i
< GetSize(m2
.ports
); i
++)
260 m2_unmapped
.insert(i
);
264 int best_i
= -1, best_j
= -1, best_score
= 0;
266 for (int i
: m1_unmapped
)
267 for (int j
: m2_unmapped
) {
268 int score
= share_macc_ports(m1
.ports
[i
], m2
.ports
[j
], w1
, w2
);
269 if (score
>= 0 && (best_i
< 0 || best_score
> score
))
270 best_i
= i
, best_j
= j
, best_score
= score
;
274 m1_unmapped
.erase(best_i
);
275 m2_unmapped
.erase(best_j
);
276 share_macc_ports(m1
.ports
[best_i
], m2
.ports
[best_j
], w1
, w2
, act
, &supermacc
, supercell_aux
);
281 for (int i
: m1_unmapped
)
283 RTLIL::SigSpec sig_a
= m1
.ports
[i
].in_a
;
284 RTLIL::SigSpec sig_b
= m1
.ports
[i
].in_b
;
286 if (supercell_aux
&& GetSize(sig_a
)) {
287 sig_a
= module
->addWire(NEW_ID
, GetSize(sig_a
));
288 supercell_aux
->insert(module
->addMux(NEW_ID
, RTLIL::SigSpec(0, GetSize(sig_a
)), m1
.ports
[i
].in_a
, act
, sig_a
));
291 if (supercell_aux
&& GetSize(sig_b
)) {
292 sig_b
= module
->addWire(NEW_ID
, GetSize(sig_b
));
293 supercell_aux
->insert(module
->addMux(NEW_ID
, RTLIL::SigSpec(0, GetSize(sig_b
)), m1
.ports
[i
].in_b
, act
, sig_b
));
299 p
.is_signed
= m1
.ports
[i
].is_signed
;
300 p
.do_subtract
= m1
.ports
[i
].do_subtract
;
301 supermacc
.ports
.push_back(p
);
304 for (int i
: m2_unmapped
)
306 RTLIL::SigSpec sig_a
= m2
.ports
[i
].in_a
;
307 RTLIL::SigSpec sig_b
= m2
.ports
[i
].in_b
;
309 if (supercell_aux
&& GetSize(sig_a
)) {
310 sig_a
= module
->addWire(NEW_ID
, GetSize(sig_a
));
311 supercell_aux
->insert(module
->addMux(NEW_ID
, m2
.ports
[i
].in_a
, RTLIL::SigSpec(0, GetSize(sig_a
)), act
, sig_a
));
314 if (supercell_aux
&& GetSize(sig_b
)) {
315 sig_b
= module
->addWire(NEW_ID
, GetSize(sig_b
));
316 supercell_aux
->insert(module
->addMux(NEW_ID
, m2
.ports
[i
].in_b
, RTLIL::SigSpec(0, GetSize(sig_b
)), act
, sig_b
));
322 p
.is_signed
= m2
.ports
[i
].is_signed
;
323 p
.do_subtract
= m2
.ports
[i
].do_subtract
;
324 supermacc
.ports
.push_back(p
);
329 RTLIL::SigSpec sig_y
= module
->addWire(NEW_ID
, width
);
331 supercell_aux
->insert(module
->addPos(NEW_ID
, sig_y
, c1
->getPort("\\Y")));
332 supercell_aux
->insert(module
->addPos(NEW_ID
, sig_y
, c2
->getPort("\\Y")));
334 supercell
->setParam("\\Y_WIDTH", width
);
335 supercell
->setPort("\\Y", sig_y
);
337 supermacc
.optimize(width
);
338 supermacc
.to_cell(supercell
);
341 return bits_macc(supermacc
, width
);
345 // ---------------------------------------------------
346 // Find shareable cells and compatible groups of cells
347 // ---------------------------------------------------
349 pool
<RTLIL::Cell
*> shareable_cells
;
351 void find_shareable_cells()
353 for (auto cell
: module
->cells())
355 if (!design
->selected(module
, cell
) || !modwalker
.ct
.cell_known(cell
->type
))
358 for (auto &bit
: modwalker
.cell_outputs
[cell
])
359 if (terminal_bits
.count(bit
))
360 goto not_a_muxed_cell
;
366 if (config
.opt_force
) {
367 shareable_cells
.insert(cell
);
371 if (cell
->type
== "$memrd") {
372 if (cell
->parameters
.at("\\CLK_ENABLE").as_bool())
374 if (config
.opt_aggressive
|| !modwalker
.sigmap(cell
->getPort("\\ADDR")).is_fully_const())
375 shareable_cells
.insert(cell
);
379 if (cell
->type
== "$mul" || cell
->type
== "$div" || cell
->type
== "$mod") {
380 if (config
.opt_aggressive
|| cell
->parameters
.at("\\Y_WIDTH").as_int() >= 4)
381 shareable_cells
.insert(cell
);
385 if (cell
->type
== "$shl" || cell
->type
== "$shr" || cell
->type
== "$sshl" || cell
->type
== "$sshr") {
386 if (config
.opt_aggressive
|| cell
->parameters
.at("\\Y_WIDTH").as_int() >= 8)
387 shareable_cells
.insert(cell
);
391 if (generic_ops
.count(cell
->type
)) {
392 if (config
.opt_aggressive
)
393 shareable_cells
.insert(cell
);
399 bool is_shareable_pair(RTLIL::Cell
*c1
, RTLIL::Cell
*c2
)
401 if (c1
->type
!= c2
->type
)
404 if (c1
->type
== "$memrd")
406 if (c1
->parameters
.at("\\MEMID").decode_string() != c2
->parameters
.at("\\MEMID").decode_string())
412 if (config
.generic_uni_ops
.count(c1
->type
))
414 if (!config
.opt_aggressive
)
416 int a1_width
= c1
->parameters
.at("\\A_WIDTH").as_int();
417 int y1_width
= c1
->parameters
.at("\\Y_WIDTH").as_int();
419 int a2_width
= c2
->parameters
.at("\\A_WIDTH").as_int();
420 int y2_width
= c2
->parameters
.at("\\Y_WIDTH").as_int();
422 if (max(a1_width
, a2_width
) > 2 * min(a1_width
, a2_width
)) return false;
423 if (max(y1_width
, y2_width
) > 2 * min(y1_width
, y2_width
)) return false;
429 if (config
.generic_bin_ops
.count(c1
->type
) || c1
->type
== "$alu")
431 if (!config
.opt_aggressive
)
433 int a1_width
= c1
->parameters
.at("\\A_WIDTH").as_int();
434 int b1_width
= c1
->parameters
.at("\\B_WIDTH").as_int();
435 int y1_width
= c1
->parameters
.at("\\Y_WIDTH").as_int();
437 int a2_width
= c2
->parameters
.at("\\A_WIDTH").as_int();
438 int b2_width
= c2
->parameters
.at("\\B_WIDTH").as_int();
439 int y2_width
= c2
->parameters
.at("\\Y_WIDTH").as_int();
441 if (max(a1_width
, a2_width
) > 2 * min(a1_width
, a2_width
)) return false;
442 if (max(b1_width
, b2_width
) > 2 * min(b1_width
, b2_width
)) return false;
443 if (max(y1_width
, y2_width
) > 2 * min(y1_width
, y2_width
)) return false;
449 if (config
.generic_cbin_ops
.count(c1
->type
))
451 if (!config
.opt_aggressive
)
453 int a1_width
= c1
->parameters
.at("\\A_WIDTH").as_int();
454 int b1_width
= c1
->parameters
.at("\\B_WIDTH").as_int();
455 int y1_width
= c1
->parameters
.at("\\Y_WIDTH").as_int();
457 int a2_width
= c2
->parameters
.at("\\A_WIDTH").as_int();
458 int b2_width
= c2
->parameters
.at("\\B_WIDTH").as_int();
459 int y2_width
= c2
->parameters
.at("\\Y_WIDTH").as_int();
461 int min1_width
= min(a1_width
, b1_width
);
462 int max1_width
= max(a1_width
, b1_width
);
464 int min2_width
= min(a2_width
, b2_width
);
465 int max2_width
= max(a2_width
, b2_width
);
467 if (max(min1_width
, min2_width
) > 2 * min(min1_width
, min2_width
)) return false;
468 if (max(max1_width
, max2_width
) > 2 * min(max1_width
, max2_width
)) return false;
469 if (max(y1_width
, y2_width
) > 2 * min(y1_width
, y2_width
)) return false;
475 if (c1
->type
== "$macc")
477 if (!config
.opt_aggressive
)
478 if (share_macc(c1
, c2
) > 2 * min(bits_macc(c1
), bits_macc(c2
))) return false;
483 for (auto &it
: c1
->parameters
)
484 if (c2
->parameters
.count(it
.first
) == 0 || c2
->parameters
.at(it
.first
) != it
.second
)
487 for (auto &it
: c2
->parameters
)
488 if (c1
->parameters
.count(it
.first
) == 0 || c1
->parameters
.at(it
.first
) != it
.second
)
494 void find_shareable_partners(std::vector
<RTLIL::Cell
*> &results
, RTLIL::Cell
*cell
)
497 for (auto c
: shareable_cells
)
498 if (c
!= cell
&& is_shareable_pair(c
, cell
))
499 results
.push_back(c
);
503 // -----------------------
504 // Create replacement cell
505 // -----------------------
507 RTLIL::Cell
*make_supercell(RTLIL::Cell
*c1
, RTLIL::Cell
*c2
, RTLIL::SigSpec act
, pool
<RTLIL::Cell
*> &supercell_aux
)
509 log_assert(c1
->type
== c2
->type
);
511 if (config
.generic_uni_ops
.count(c1
->type
))
513 if (c1
->parameters
.at("\\A_SIGNED").as_bool() != c2
->parameters
.at("\\A_SIGNED").as_bool())
515 RTLIL::Cell
*unsigned_cell
= c1
->parameters
.at("\\A_SIGNED").as_bool() ? c2
: c1
;
516 if (unsigned_cell
->getPort("\\A").to_sigbit_vector().back() != RTLIL::State::S0
) {
517 unsigned_cell
->parameters
.at("\\A_WIDTH") = unsigned_cell
->parameters
.at("\\A_WIDTH").as_int() + 1;
518 RTLIL::SigSpec new_a
= unsigned_cell
->getPort("\\A");
519 new_a
.append_bit(RTLIL::State::S0
);
520 unsigned_cell
->setPort("\\A", new_a
);
522 unsigned_cell
->parameters
.at("\\A_SIGNED") = true;
523 unsigned_cell
->check();
526 bool a_signed
= c1
->parameters
.at("\\A_SIGNED").as_bool();
527 log_assert(a_signed
== c2
->parameters
.at("\\A_SIGNED").as_bool());
529 RTLIL::SigSpec a1
= c1
->getPort("\\A");
530 RTLIL::SigSpec y1
= c1
->getPort("\\Y");
532 RTLIL::SigSpec a2
= c2
->getPort("\\A");
533 RTLIL::SigSpec y2
= c2
->getPort("\\Y");
535 int a_width
= max(a1
.size(), a2
.size());
536 int y_width
= max(y1
.size(), y2
.size());
538 a1
.extend_u0(a_width
, a_signed
);
539 a2
.extend_u0(a_width
, a_signed
);
541 RTLIL::SigSpec a
= module
->addWire(NEW_ID
, a_width
);
542 supercell_aux
.insert(module
->addMux(NEW_ID
, a2
, a1
, act
, a
));
544 RTLIL::Wire
*y
= module
->addWire(NEW_ID
, y_width
);
546 RTLIL::Cell
*supercell
= module
->addCell(NEW_ID
, c1
->type
);
547 supercell
->parameters
["\\A_SIGNED"] = a_signed
;
548 supercell
->parameters
["\\A_WIDTH"] = a_width
;
549 supercell
->parameters
["\\Y_WIDTH"] = y_width
;
550 supercell
->setPort("\\A", a
);
551 supercell
->setPort("\\Y", y
);
553 supercell_aux
.insert(module
->addPos(NEW_ID
, y
, y1
));
554 supercell_aux
.insert(module
->addPos(NEW_ID
, y
, y2
));
556 supercell_aux
.insert(supercell
);
560 if (config
.generic_bin_ops
.count(c1
->type
) || config
.generic_cbin_ops
.count(c1
->type
) || c1
->type
== "$alu")
562 bool modified_src_cells
= false;
564 if (config
.generic_cbin_ops
.count(c1
->type
))
566 int score_unflipped
= max(c1
->parameters
.at("\\A_WIDTH").as_int(), c2
->parameters
.at("\\A_WIDTH").as_int()) +
567 max(c1
->parameters
.at("\\B_WIDTH").as_int(), c2
->parameters
.at("\\B_WIDTH").as_int());
569 int score_flipped
= max(c1
->parameters
.at("\\A_WIDTH").as_int(), c2
->parameters
.at("\\B_WIDTH").as_int()) +
570 max(c1
->parameters
.at("\\B_WIDTH").as_int(), c2
->parameters
.at("\\A_WIDTH").as_int());
572 if (score_flipped
< score_unflipped
)
574 RTLIL::SigSpec tmp
= c2
->getPort("\\A");
575 c2
->setPort("\\A", c2
->getPort("\\B"));
576 c2
->setPort("\\B", tmp
);
578 std::swap(c2
->parameters
.at("\\A_WIDTH"), c2
->parameters
.at("\\B_WIDTH"));
579 std::swap(c2
->parameters
.at("\\A_SIGNED"), c2
->parameters
.at("\\B_SIGNED"));
580 modified_src_cells
= true;
584 if (c1
->parameters
.at("\\A_SIGNED").as_bool() != c2
->parameters
.at("\\A_SIGNED").as_bool())
587 RTLIL::Cell
*unsigned_cell
= c1
->parameters
.at("\\A_SIGNED").as_bool() ? c2
: c1
;
588 if (unsigned_cell
->getPort("\\A").to_sigbit_vector().back() != RTLIL::State::S0
) {
589 unsigned_cell
->parameters
.at("\\A_WIDTH") = unsigned_cell
->parameters
.at("\\A_WIDTH").as_int() + 1;
590 RTLIL::SigSpec new_a
= unsigned_cell
->getPort("\\A");
591 new_a
.append_bit(RTLIL::State::S0
);
592 unsigned_cell
->setPort("\\A", new_a
);
594 unsigned_cell
->parameters
.at("\\A_SIGNED") = true;
595 modified_src_cells
= true;
598 if (c1
->parameters
.at("\\B_SIGNED").as_bool() != c2
->parameters
.at("\\B_SIGNED").as_bool())
600 RTLIL::Cell
*unsigned_cell
= c1
->parameters
.at("\\B_SIGNED").as_bool() ? c2
: c1
;
601 if (unsigned_cell
->getPort("\\B").to_sigbit_vector().back() != RTLIL::State::S0
) {
602 unsigned_cell
->parameters
.at("\\B_WIDTH") = unsigned_cell
->parameters
.at("\\B_WIDTH").as_int() + 1;
603 RTLIL::SigSpec new_b
= unsigned_cell
->getPort("\\B");
604 new_b
.append_bit(RTLIL::State::S0
);
605 unsigned_cell
->setPort("\\B", new_b
);
607 unsigned_cell
->parameters
.at("\\B_SIGNED") = true;
608 modified_src_cells
= true;
611 if (modified_src_cells
) {
616 bool a_signed
= c1
->parameters
.at("\\A_SIGNED").as_bool();
617 bool b_signed
= c1
->parameters
.at("\\B_SIGNED").as_bool();
619 log_assert(a_signed
== c2
->parameters
.at("\\A_SIGNED").as_bool());
620 log_assert(b_signed
== c2
->parameters
.at("\\B_SIGNED").as_bool());
622 if (c1
->type
== "$shl" || c1
->type
== "$shr" || c1
->type
== "$sshl" || c1
->type
== "$sshr")
625 RTLIL::SigSpec a1
= c1
->getPort("\\A");
626 RTLIL::SigSpec b1
= c1
->getPort("\\B");
627 RTLIL::SigSpec y1
= c1
->getPort("\\Y");
629 RTLIL::SigSpec a2
= c2
->getPort("\\A");
630 RTLIL::SigSpec b2
= c2
->getPort("\\B");
631 RTLIL::SigSpec y2
= c2
->getPort("\\Y");
633 int a_width
= max(a1
.size(), a2
.size());
634 int b_width
= max(b1
.size(), b2
.size());
635 int y_width
= max(y1
.size(), y2
.size());
637 if (c1
->type
== "$shr" && a_signed
)
639 a_width
= max(y_width
, a_width
);
641 if (a1
.size() < y1
.size()) a1
.extend_u0(y1
.size(), true);
642 if (a2
.size() < y2
.size()) a2
.extend_u0(y2
.size(), true);
644 a1
.extend_u0(a_width
, false);
645 a2
.extend_u0(a_width
, false);
649 a1
.extend_u0(a_width
, a_signed
);
650 a2
.extend_u0(a_width
, a_signed
);
653 b1
.extend_u0(b_width
, b_signed
);
654 b2
.extend_u0(b_width
, b_signed
);
656 RTLIL::SigSpec a
= module
->addWire(NEW_ID
, a_width
);
657 RTLIL::SigSpec b
= module
->addWire(NEW_ID
, b_width
);
659 supercell_aux
.insert(module
->addMux(NEW_ID
, a2
, a1
, act
, a
));
660 supercell_aux
.insert(module
->addMux(NEW_ID
, b2
, b1
, act
, b
));
662 RTLIL::Wire
*y
= module
->addWire(NEW_ID
, y_width
);
663 RTLIL::Wire
*x
= c1
->type
== "$alu" ? module
->addWire(NEW_ID
, y_width
) : nullptr;
664 RTLIL::Wire
*co
= c1
->type
== "$alu" ? module
->addWire(NEW_ID
, y_width
) : nullptr;
666 RTLIL::Cell
*supercell
= module
->addCell(NEW_ID
, c1
->type
);
667 supercell
->parameters
["\\A_SIGNED"] = a_signed
;
668 supercell
->parameters
["\\B_SIGNED"] = b_signed
;
669 supercell
->parameters
["\\A_WIDTH"] = a_width
;
670 supercell
->parameters
["\\B_WIDTH"] = b_width
;
671 supercell
->parameters
["\\Y_WIDTH"] = y_width
;
672 supercell
->setPort("\\A", a
);
673 supercell
->setPort("\\B", b
);
674 supercell
->setPort("\\Y", y
);
675 if (c1
->type
== "$alu") {
676 RTLIL::Wire
*ci
= module
->addWire(NEW_ID
), *bi
= module
->addWire(NEW_ID
);
677 supercell_aux
.insert(module
->addMux(NEW_ID
, c2
->getPort("\\CI"), c1
->getPort("\\CI"), act
, ci
));
678 supercell_aux
.insert(module
->addMux(NEW_ID
, c2
->getPort("\\BI"), c1
->getPort("\\BI"), act
, bi
));
679 supercell
->setPort("\\CI", ci
);
680 supercell
->setPort("\\BI", bi
);
681 supercell
->setPort("\\CO", co
);
682 supercell
->setPort("\\X", x
);
686 supercell_aux
.insert(module
->addPos(NEW_ID
, y
, y1
));
687 supercell_aux
.insert(module
->addPos(NEW_ID
, y
, y2
));
688 if (c1
->type
== "$alu") {
689 supercell_aux
.insert(module
->addPos(NEW_ID
, co
, c1
->getPort("\\CO")));
690 supercell_aux
.insert(module
->addPos(NEW_ID
, co
, c2
->getPort("\\CO")));
691 supercell_aux
.insert(module
->addPos(NEW_ID
, x
, c1
->getPort("\\X")));
692 supercell_aux
.insert(module
->addPos(NEW_ID
, x
, c2
->getPort("\\X")));
695 supercell_aux
.insert(supercell
);
699 if (c1
->type
== "$macc")
701 RTLIL::Cell
*supercell
= module
->addCell(NEW_ID
, c1
->type
);
702 supercell_aux
.insert(supercell
);
703 share_macc(c1
, c2
, act
, supercell
, &supercell_aux
);
708 if (c1
->type
== "$memrd")
710 RTLIL::Cell
*supercell
= module
->addCell(NEW_ID
, c1
);
711 RTLIL::SigSpec addr1
= c1
->getPort("\\ADDR");
712 RTLIL::SigSpec addr2
= c2
->getPort("\\ADDR");
714 supercell
->setPort("\\ADDR", module
->Mux(NEW_ID
, addr2
, addr1
, act
));
715 supercell_aux
.insert(module
->addPos(NEW_ID
, supercell
->getPort("\\DATA"), c2
->getPort("\\DATA")));
716 supercell_aux
.insert(supercell
);
724 // -------------------------------------------
725 // Finding forbidden control inputs for a cell
726 // -------------------------------------------
728 std::map
<RTLIL::Cell
*, pool
<RTLIL::SigBit
>, cell_ptr_cmp
> forbidden_controls_cache
;
730 const pool
<RTLIL::SigBit
> &find_forbidden_controls(RTLIL::Cell
*cell
)
732 if (recursion_state
.count(cell
)) {
733 static pool
<RTLIL::SigBit
> empty_controls_set
;
734 return empty_controls_set
;
737 if (forbidden_controls_cache
.count(cell
))
738 return forbidden_controls_cache
.at(cell
);
740 pool
<ModWalker::PortBit
> pbits
;
741 pool
<RTLIL::Cell
*> consumer_cells
;
743 modwalker
.get_consumers(pbits
, modwalker
.cell_outputs
[cell
]);
745 for (auto &bit
: pbits
) {
746 if ((bit
.cell
->type
== "$mux" || bit
.cell
->type
== "$pmux") && bit
.port
== "\\S")
747 forbidden_controls_cache
[cell
].insert(bit
.cell
->getPort("\\S").extract(bit
.offset
, 1));
748 consumer_cells
.insert(bit
.cell
);
751 recursion_state
.insert(cell
);
753 for (auto c
: consumer_cells
)
754 if (fwd_ct
.cell_known(c
->type
)) {
755 const pool
<RTLIL::SigBit
> &bits
= find_forbidden_controls(c
);
756 forbidden_controls_cache
[cell
].insert(bits
.begin(), bits
.end());
759 log_assert(recursion_state
.count(cell
) != 0);
760 recursion_state
.erase(cell
);
762 return forbidden_controls_cache
[cell
];
766 // --------------------------------------------------------
767 // Finding control inputs and activation pattern for a cell
768 // --------------------------------------------------------
770 std::map
<RTLIL::Cell
*, pool
<ssc_pair_t
>, cell_ptr_cmp
> activation_patterns_cache
;
772 bool sort_check_activation_pattern(ssc_pair_t
&p
)
774 std::map
<RTLIL::SigBit
, RTLIL::State
> p_bits
;
776 std::vector
<RTLIL::SigBit
> p_first_bits
= p
.first
;
777 for (int i
= 0; i
< GetSize(p_first_bits
); i
++) {
778 RTLIL::SigBit b
= p_first_bits
[i
];
779 RTLIL::State v
= p
.second
.bits
[i
];
780 if (p_bits
.count(b
) && p_bits
.at(b
) != v
)
785 p
.first
= RTLIL::SigSpec();
786 p
.second
.bits
.clear();
788 for (auto &it
: p_bits
) {
789 p
.first
.append_bit(it
.first
);
790 p
.second
.bits
.push_back(it
.second
);
796 void optimize_activation_patterns(pool
<ssc_pair_t
> &patterns
)
798 // TODO: Remove patterns that are contained in other patterns
800 dict
<SigSpec
, pool
<Const
>> db
;
801 bool did_something
= false;
803 for (auto const &p
: patterns
)
806 auto &val
= p
.second
;
807 int len
= GetSize(sig
);
809 for (int i
= 0; i
< len
; i
++)
813 if (otherval
.bits
[i
] == State::S0
)
814 otherval
.bits
[i
] = State::S1
;
815 else if (otherval
.bits
[i
] == State::S1
)
816 otherval
.bits
[i
] = State::S0
;
820 if (db
[sig
].count(otherval
))
826 newval
.bits
.erase(newval
.bits
.begin() + i
);
828 db
[newsig
].insert(newval
);
829 db
[sig
].erase(otherval
);
831 did_something
= true;
845 for (auto &val
: it
.second
)
846 patterns
.insert(make_pair(it
.first
, val
));
848 optimize_activation_patterns(patterns
);
851 const pool
<ssc_pair_t
> &find_cell_activation_patterns(RTLIL::Cell
*cell
, const char *indent
)
853 if (recursion_state
.count(cell
)) {
854 static pool
<ssc_pair_t
> empty_patterns_set
;
855 return empty_patterns_set
;
858 if (activation_patterns_cache
.count(cell
))
859 return activation_patterns_cache
.at(cell
);
861 const pool
<RTLIL::SigBit
> &cell_out_bits
= modwalker
.cell_outputs
[cell
];
862 pool
<RTLIL::Cell
*> driven_cells
, driven_data_muxes
;
864 for (auto &bit
: cell_out_bits
)
866 if (terminal_bits
.count(bit
)) {
867 // Terminal cells are always active: unconditional activation pattern
868 activation_patterns_cache
[cell
].insert(ssc_pair_t());
869 return activation_patterns_cache
.at(cell
);
871 for (auto &pbit
: modwalker
.signal_consumers
[bit
]) {
872 log_assert(fwd_ct
.cell_known(pbit
.cell
->type
));
873 if ((pbit
.cell
->type
== "$mux" || pbit
.cell
->type
== "$pmux") && (pbit
.port
== "\\A" || pbit
.port
== "\\B"))
874 driven_data_muxes
.insert(pbit
.cell
);
876 driven_cells
.insert(pbit
.cell
);
880 recursion_state
.insert(cell
);
882 for (auto c
: driven_data_muxes
)
884 const pool
<ssc_pair_t
> &c_patterns
= find_cell_activation_patterns(c
, indent
);
886 bool used_in_a
= false;
887 std::set
<int> used_in_b_parts
;
889 int width
= c
->parameters
.at("\\WIDTH").as_int();
890 std::vector
<RTLIL::SigBit
> sig_a
= modwalker
.sigmap(c
->getPort("\\A"));
891 std::vector
<RTLIL::SigBit
> sig_b
= modwalker
.sigmap(c
->getPort("\\B"));
892 std::vector
<RTLIL::SigBit
> sig_s
= modwalker
.sigmap(c
->getPort("\\S"));
894 for (auto &bit
: sig_a
)
895 if (cell_out_bits
.count(bit
))
898 for (int i
= 0; i
< GetSize(sig_b
); i
++)
899 if (cell_out_bits
.count(sig_b
[i
]))
900 used_in_b_parts
.insert(i
/ width
);
903 for (auto p
: c_patterns
) {
904 for (int i
= 0; i
< GetSize(sig_s
); i
++)
905 p
.first
.append_bit(sig_s
[i
]), p
.second
.bits
.push_back(RTLIL::State::S0
);
906 if (sort_check_activation_pattern(p
))
907 activation_patterns_cache
[cell
].insert(p
);
910 for (int idx
: used_in_b_parts
)
911 for (auto p
: c_patterns
) {
912 p
.first
.append_bit(sig_s
[idx
]), p
.second
.bits
.push_back(RTLIL::State::S1
);
913 if (sort_check_activation_pattern(p
))
914 activation_patterns_cache
[cell
].insert(p
);
918 for (auto c
: driven_cells
) {
919 const pool
<ssc_pair_t
> &c_patterns
= find_cell_activation_patterns(c
, indent
);
920 activation_patterns_cache
[cell
].insert(c_patterns
.begin(), c_patterns
.end());
923 log_assert(recursion_state
.count(cell
) != 0);
924 recursion_state
.erase(cell
);
926 optimize_activation_patterns(activation_patterns_cache
[cell
]);
927 if (activation_patterns_cache
[cell
].empty()) {
928 log("%sFound cell that is never activated: %s\n", indent
, log_id(cell
));
929 RTLIL::SigSpec cell_outputs
= modwalker
.cell_outputs
[cell
];
930 module
->connect(RTLIL::SigSig(cell_outputs
, RTLIL::SigSpec(RTLIL::State::Sx
, cell_outputs
.size())));
931 cells_to_remove
.insert(cell
);
934 return activation_patterns_cache
[cell
];
937 RTLIL::SigSpec
bits_from_activation_patterns(const pool
<ssc_pair_t
> &activation_patterns
)
939 std::set
<RTLIL::SigBit
> all_bits
;
940 for (auto &it
: activation_patterns
) {
941 std::vector
<RTLIL::SigBit
> bits
= it
.first
;
942 all_bits
.insert(bits
.begin(), bits
.end());
945 RTLIL::SigSpec signal
;
946 for (auto &bit
: all_bits
)
947 signal
.append_bit(bit
);
952 void filter_activation_patterns(pool
<ssc_pair_t
> &out
,
953 const pool
<ssc_pair_t
> &in
, const std::set
<RTLIL::SigBit
> &filter_bits
)
957 std::vector
<RTLIL::SigBit
> p_first
= p
.first
;
960 for (int i
= 0; i
< GetSize(p_first
); i
++)
961 if (filter_bits
.count(p_first
[i
]) == 0) {
962 new_p
.first
.append_bit(p_first
[i
]);
963 new_p
.second
.bits
.push_back(p
.second
.bits
.at(i
));
970 RTLIL::SigSpec
make_cell_activation_logic(const pool
<ssc_pair_t
> &activation_patterns
, pool
<RTLIL::Cell
*> &supercell_aux
)
972 RTLIL::Wire
*all_cases_wire
= module
->addWire(NEW_ID
, 0);
974 for (auto &p
: activation_patterns
) {
975 all_cases_wire
->width
++;
976 supercell_aux
.insert(module
->addEq(NEW_ID
, p
.first
, p
.second
, RTLIL::SigSpec(all_cases_wire
, all_cases_wire
->width
- 1)));
979 if (all_cases_wire
->width
== 1)
980 return all_cases_wire
;
982 RTLIL::Wire
*result_wire
= module
->addWire(NEW_ID
);
983 supercell_aux
.insert(module
->addReduceOr(NEW_ID
, all_cases_wire
, result_wire
));
988 // -------------------------------------------------------------------------------------
989 // Helper functions used to make sure that this pass does not introduce new logic loops.
990 // -------------------------------------------------------------------------------------
992 bool module_has_scc()
995 ct
.setup_internals();
998 TopoSort
<RTLIL::Cell
*, cell_ptr_cmp
> toposort
;
999 toposort
.analyze_loops
= false;
1001 topo_sigmap
.set(module
);
1002 topo_bit_drivers
.clear();
1004 dict
<RTLIL::Cell
*, pool
<RTLIL::SigBit
>> cell_to_bits
;
1005 dict
<RTLIL::SigBit
, pool
<RTLIL::Cell
*>> bit_to_cells
;
1007 for (auto cell
: module
->cells())
1008 if (ct
.cell_known(cell
->type
))
1009 for (auto &conn
: cell
->connections()) {
1010 if (ct
.cell_output(cell
->type
, conn
.first
))
1011 for (auto bit
: topo_sigmap(conn
.second
)) {
1012 cell_to_bits
[cell
].insert(bit
);
1013 topo_bit_drivers
[bit
].insert(cell
);
1016 for (auto bit
: topo_sigmap(conn
.second
))
1017 bit_to_cells
[bit
].insert(cell
);
1020 for (auto &it
: cell_to_bits
)
1022 RTLIL::Cell
*c1
= it
.first
;
1024 for (auto bit
: it
.second
)
1025 for (auto c2
: bit_to_cells
[bit
])
1026 toposort
.edge(c1
, c2
);
1029 bool found_scc
= !toposort
.sort();
1030 topo_cell_drivers
= std::move(toposort
.database
);
1032 if (found_scc
&& toposort
.analyze_loops
)
1033 for (auto &loop
: toposort
.loops
) {
1034 log("### loop ###\n");
1035 for (auto &c
: loop
)
1036 log("%s (%s)\n", log_id(c
), log_id(c
->type
));
1042 bool find_in_input_cone_worker(RTLIL::Cell
*root
, RTLIL::Cell
*needle
, pool
<RTLIL::Cell
*> &stop
)
1047 if (stop
.count(root
))
1052 for (auto c
: topo_cell_drivers
[root
])
1053 if (find_in_input_cone_worker(c
, needle
, stop
))
1058 bool find_in_input_cone(RTLIL::Cell
*root
, RTLIL::Cell
*needle
)
1060 pool
<RTLIL::Cell
*> stop
;
1061 return find_in_input_cone_worker(root
, needle
, stop
);
1064 bool is_part_of_scc(RTLIL::Cell
*cell
)
1067 ct
.setup_internals();
1068 ct
.setup_stdcells();
1070 pool
<RTLIL::Cell
*> queue
, covered
;
1073 while (!queue
.empty())
1075 pool
<RTLIL::Cell
*> new_queue
;
1077 for (auto c
: queue
) {
1078 if (!ct
.cell_known(c
->type
))
1080 for (auto &conn
: c
->connections())
1081 if (ct
.cell_input(c
->type
, conn
.first
))
1082 for (auto bit
: conn
.second
)
1083 for (auto &pi
: mi
.query_ports(bit
))
1084 if (ct
.cell_known(pi
.cell
->type
) && ct
.cell_output(pi
.cell
->type
, pi
.port
))
1085 new_queue
.insert(pi
.cell
);
1090 for (auto c
: new_queue
) {
1091 if (cells_to_remove
.count(c
))
1095 if (!covered
.count(c
))
1108 void remove_cell(Cell
*cell
)
1110 shareable_cells
.erase(cell
);
1111 forbidden_controls_cache
.erase(cell
);
1112 activation_patterns_cache
.erase(cell
);
1113 module
->remove(cell
);
1116 ShareWorker(ShareWorkerConfig config
, RTLIL::Design
*design
, RTLIL::Module
*module
) :
1117 config(config
), design(design
), module(module
), mi(module
)
1120 bool before_scc
= module_has_scc();
1123 generic_ops
.insert(config
.generic_uni_ops
.begin(), config
.generic_uni_ops
.end());
1124 generic_ops
.insert(config
.generic_bin_ops
.begin(), config
.generic_bin_ops
.end());
1125 generic_ops
.insert(config
.generic_cbin_ops
.begin(), config
.generic_cbin_ops
.end());
1126 generic_ops
.insert(config
.generic_other_ops
.begin(), config
.generic_other_ops
.end());
1128 fwd_ct
.setup_internals();
1130 cone_ct
.setup_internals();
1131 cone_ct
.cell_types
.erase("$mul");
1132 cone_ct
.cell_types
.erase("$mod");
1133 cone_ct
.cell_types
.erase("$div");
1134 cone_ct
.cell_types
.erase("$pow");
1135 cone_ct
.cell_types
.erase("$shl");
1136 cone_ct
.cell_types
.erase("$shr");
1137 cone_ct
.cell_types
.erase("$sshl");
1138 cone_ct
.cell_types
.erase("$sshr");
1140 modwalker
.setup(design
, module
);
1142 find_terminal_bits();
1143 find_shareable_cells();
1145 if (shareable_cells
.size() < 2)
1148 log("Found %d cells in module %s that may be considered for resource sharing.\n",
1149 GetSize(shareable_cells
), log_id(module
));
1151 for (auto cell
: module
->cells())
1152 if (cell
->type
== "$pmux")
1153 for (auto bit
: cell
->getPort("\\S"))
1154 for (auto other_bit
: cell
->getPort("\\S"))
1155 if (bit
< other_bit
)
1156 exclusive_ctrls
.push_back(std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>(bit
, other_bit
));
1158 while (!shareable_cells
.empty() && config
.limit
!= 0)
1160 RTLIL::Cell
*cell
= *shareable_cells
.begin();
1161 shareable_cells
.erase(cell
);
1163 log(" Analyzing resource sharing options for %s (%s):\n", log_id(cell
), log_id(cell
->type
));
1165 const pool
<ssc_pair_t
> &cell_activation_patterns
= find_cell_activation_patterns(cell
, " ");
1166 RTLIL::SigSpec cell_activation_signals
= bits_from_activation_patterns(cell_activation_patterns
);
1168 if (cell_activation_patterns
.empty()) {
1169 log(" Cell is never active. Sharing is pointless, we simply remove it.\n");
1170 cells_to_remove
.insert(cell
);
1174 if (cell_activation_patterns
.count(ssc_pair_t())) {
1175 log(" Cell is always active. Therefore no sharing is possible.\n");
1179 log(" Found %d activation_patterns using ctrl signal %s.\n", GetSize(cell_activation_patterns
), log_signal(cell_activation_signals
));
1181 std::vector
<RTLIL::Cell
*> candidates
;
1182 find_shareable_partners(candidates
, cell
);
1184 if (candidates
.empty()) {
1185 log(" No candidates found.\n");
1189 log(" Found %d candidates:", GetSize(candidates
));
1190 for (auto c
: candidates
)
1191 log(" %s", log_id(c
));
1194 for (auto other_cell
: candidates
)
1196 log(" Analyzing resource sharing with %s (%s):\n", log_id(other_cell
), log_id(other_cell
->type
));
1198 const pool
<ssc_pair_t
> &other_cell_activation_patterns
= find_cell_activation_patterns(other_cell
, " ");
1199 RTLIL::SigSpec other_cell_activation_signals
= bits_from_activation_patterns(other_cell_activation_patterns
);
1201 if (other_cell_activation_patterns
.empty()) {
1202 log(" Cell is never active. Sharing is pointless, we simply remove it.\n");
1203 shareable_cells
.erase(other_cell
);
1204 cells_to_remove
.insert(other_cell
);
1208 if (other_cell_activation_patterns
.count(ssc_pair_t())) {
1209 log(" Cell is always active. Therefore no sharing is possible.\n");
1210 shareable_cells
.erase(other_cell
);
1214 log(" Found %d activation_patterns using ctrl signal %s.\n",
1215 GetSize(other_cell_activation_patterns
), log_signal(other_cell_activation_signals
));
1217 const pool
<RTLIL::SigBit
> &cell_forbidden_controls
= find_forbidden_controls(cell
);
1218 const pool
<RTLIL::SigBit
> &other_cell_forbidden_controls
= find_forbidden_controls(other_cell
);
1220 std::set
<RTLIL::SigBit
> union_forbidden_controls
;
1221 union_forbidden_controls
.insert(cell_forbidden_controls
.begin(), cell_forbidden_controls
.end());
1222 union_forbidden_controls
.insert(other_cell_forbidden_controls
.begin(), other_cell_forbidden_controls
.end());
1224 if (!union_forbidden_controls
.empty())
1225 log(" Forbidden control signals for this pair of cells: %s\n", log_signal(union_forbidden_controls
));
1227 pool
<ssc_pair_t
> filtered_cell_activation_patterns
;
1228 pool
<ssc_pair_t
> filtered_other_cell_activation_patterns
;
1230 filter_activation_patterns(filtered_cell_activation_patterns
, cell_activation_patterns
, union_forbidden_controls
);
1231 filter_activation_patterns(filtered_other_cell_activation_patterns
, other_cell_activation_patterns
, union_forbidden_controls
);
1233 optimize_activation_patterns(filtered_cell_activation_patterns
);
1234 optimize_activation_patterns(filtered_other_cell_activation_patterns
);
1237 SatGen
satgen(ez
.get(), &modwalker
.sigmap
);
1239 pool
<RTLIL::Cell
*> sat_cells
;
1240 std::set
<RTLIL::SigBit
> bits_queue
;
1242 std::vector
<int> cell_active
, other_cell_active
;
1243 RTLIL::SigSpec all_ctrl_signals
;
1245 for (auto &p
: filtered_cell_activation_patterns
) {
1246 log(" Activation pattern for cell %s: %s = %s\n", log_id(cell
), log_signal(p
.first
), log_signal(p
.second
));
1247 cell_active
.push_back(ez
->vec_eq(satgen
.importSigSpec(p
.first
), satgen
.importSigSpec(p
.second
)));
1248 all_ctrl_signals
.append(p
.first
);
1251 for (auto &p
: filtered_other_cell_activation_patterns
) {
1252 log(" Activation pattern for cell %s: %s = %s\n", log_id(other_cell
), log_signal(p
.first
), log_signal(p
.second
));
1253 other_cell_active
.push_back(ez
->vec_eq(satgen
.importSigSpec(p
.first
), satgen
.importSigSpec(p
.second
)));
1254 all_ctrl_signals
.append(p
.first
);
1257 for (auto &bit
: cell_activation_signals
.to_sigbit_vector())
1258 bits_queue
.insert(bit
);
1260 for (auto &bit
: other_cell_activation_signals
.to_sigbit_vector())
1261 bits_queue
.insert(bit
);
1263 while (!bits_queue
.empty())
1265 pool
<ModWalker::PortBit
> portbits
;
1266 modwalker
.get_drivers(portbits
, bits_queue
);
1269 for (auto &pbit
: portbits
)
1270 if (sat_cells
.count(pbit
.cell
) == 0 && cone_ct
.cell_known(pbit
.cell
->type
)) {
1271 if (config
.opt_fast
&& modwalker
.cell_outputs
[pbit
.cell
].size() >= 4)
1273 // log(" Adding cell %s (%s) to SAT problem.\n", log_id(pbit.cell), log_id(pbit.cell->type));
1274 bits_queue
.insert(modwalker
.cell_inputs
[pbit
.cell
].begin(), modwalker
.cell_inputs
[pbit
.cell
].end());
1275 satgen
.importCell(pbit
.cell
);
1276 sat_cells
.insert(pbit
.cell
);
1279 if (config
.opt_fast
&& sat_cells
.size() > 100)
1283 for (auto it
: exclusive_ctrls
)
1284 if (satgen
.importedSigBit(it
.first
) && satgen
.importedSigBit(it
.second
)) {
1285 log(" Adding exclusive control bits: %s vs. %s\n", log_signal(it
.first
), log_signal(it
.second
));
1286 int sub1
= satgen
.importSigBit(it
.first
);
1287 int sub2
= satgen
.importSigBit(it
.second
);
1288 ez
->assume(ez
->NOT(ez
->AND(sub1
, sub2
)));
1291 if (!ez
->solve(ez
->expression(ez
->OpOr
, cell_active
))) {
1292 log(" According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(cell
));
1293 cells_to_remove
.insert(cell
);
1297 if (!ez
->solve(ez
->expression(ez
->OpOr
, other_cell_active
))) {
1298 log(" According to the SAT solver the cell %s is never active. Sharing is pointless, we simply remove it.\n", log_id(other_cell
));
1299 cells_to_remove
.insert(other_cell
);
1300 shareable_cells
.erase(other_cell
);
1304 ez
->non_incremental();
1306 all_ctrl_signals
.sort_and_unify();
1307 std::vector
<int> sat_model
= satgen
.importSigSpec(all_ctrl_signals
);
1308 std::vector
<bool> sat_model_values
;
1310 int sub1
= ez
->expression(ez
->OpOr
, cell_active
);
1311 int sub2
= ez
->expression(ez
->OpOr
, other_cell_active
);
1312 ez
->assume(ez
->AND(sub1
, sub2
));
1314 log(" Size of SAT problem: %d cells, %d variables, %d clauses\n",
1315 GetSize(sat_cells
), ez
->numCnfVariables(), ez
->numCnfClauses());
1317 if (ez
->solve(sat_model
, sat_model_values
)) {
1318 log(" According to the SAT solver this pair of cells can not be shared.\n");
1319 log(" Model from SAT solver: %s = %d'", log_signal(all_ctrl_signals
), GetSize(sat_model_values
));
1320 for (int i
= GetSize(sat_model_values
)-1; i
>= 0; i
--)
1321 log("%c", sat_model_values
[i
] ? '1' : '0');
1326 log(" According to the SAT solver this pair of cells can be shared.\n");
1328 if (find_in_input_cone(cell
, other_cell
)) {
1329 log(" Sharing not possible: %s is in input cone of %s.\n", log_id(other_cell
), log_id(cell
));
1333 if (find_in_input_cone(other_cell
, cell
)) {
1334 log(" Sharing not possible: %s is in input cone of %s.\n", log_id(cell
), log_id(other_cell
));
1338 shareable_cells
.erase(other_cell
);
1340 int cell_select_score
= 0;
1341 int other_cell_select_score
= 0;
1343 for (auto &p
: filtered_cell_activation_patterns
)
1344 cell_select_score
+= p
.first
.size();
1346 for (auto &p
: filtered_other_cell_activation_patterns
)
1347 other_cell_select_score
+= p
.first
.size();
1349 RTLIL::Cell
*supercell
;
1350 pool
<RTLIL::Cell
*> supercell_aux
;
1351 if (cell_select_score
<= other_cell_select_score
) {
1352 RTLIL::SigSpec act
= make_cell_activation_logic(filtered_cell_activation_patterns
, supercell_aux
);
1353 supercell
= make_supercell(cell
, other_cell
, act
, supercell_aux
);
1354 log(" Activation signal for %s: %s\n", log_id(cell
), log_signal(act
));
1356 RTLIL::SigSpec act
= make_cell_activation_logic(filtered_other_cell_activation_patterns
, supercell_aux
);
1357 supercell
= make_supercell(other_cell
, cell
, act
, supercell_aux
);
1358 log(" Activation signal for %s: %s\n", log_id(other_cell
), log_signal(act
));
1361 log(" New cell: %s (%s)\n", log_id(supercell
), log_id(supercell
->type
));
1363 cells_to_remove
.insert(cell
);
1364 cells_to_remove
.insert(other_cell
);
1366 for (auto c
: supercell_aux
)
1367 if (is_part_of_scc(c
))
1372 log(" New topology contains loops! Rolling back..\n");
1373 cells_to_remove
.erase(cell
);
1374 cells_to_remove
.erase(other_cell
);
1375 shareable_cells
.insert(other_cell
);
1376 for (auto cc
: supercell_aux
)
1381 pool
<ssc_pair_t
> supercell_activation_patterns
;
1382 supercell_activation_patterns
.insert(filtered_cell_activation_patterns
.begin(), filtered_cell_activation_patterns
.end());
1383 supercell_activation_patterns
.insert(filtered_other_cell_activation_patterns
.begin(), filtered_other_cell_activation_patterns
.end());
1384 optimize_activation_patterns(supercell_activation_patterns
);
1385 activation_patterns_cache
[supercell
] = supercell_activation_patterns
;
1386 shareable_cells
.insert(supercell
);
1388 for (auto bit
: topo_sigmap(all_ctrl_signals
))
1389 for (auto c
: topo_bit_drivers
[bit
])
1390 topo_cell_drivers
[supercell
].insert(c
);
1392 topo_cell_drivers
[supercell
].insert(topo_cell_drivers
[cell
].begin(), topo_cell_drivers
[cell
].end());
1393 topo_cell_drivers
[supercell
].insert(topo_cell_drivers
[other_cell
].begin(), topo_cell_drivers
[other_cell
].end());
1395 topo_cell_drivers
[cell
] = { supercell
};
1396 topo_cell_drivers
[other_cell
] = { supercell
};
1398 if (config
.limit
> 0)
1405 if (!cells_to_remove
.empty()) {
1406 log("Removing %d cells in module %s:\n", GetSize(cells_to_remove
), log_id(module
));
1407 for (auto c
: cells_to_remove
) {
1408 log(" Removing cell %s (%s).\n", log_id(c
), log_id(c
->type
));
1413 log_assert(recursion_state
.empty());
1416 bool after_scc
= before_scc
|| module_has_scc();
1417 log_assert(before_scc
== after_scc
);
1422 struct SharePass
: public Pass
{
1423 SharePass() : Pass("share", "perform sat-based resource sharing") { }
1426 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
1428 log(" share [options] [selection]\n");
1430 log("This pass merges shareable resources into a single resource. A SAT solver\n");
1431 log("is used to determine if two resources are share-able.\n");
1434 log(" Per default the selection of cells that is considered for sharing is\n");
1435 log(" narrowed using a list of cell types. With this option all selected\n");
1436 log(" cells are considered for resource sharing.\n");
1438 log(" IMPORTANT NOTE: If the -all option is used then no cells with internal\n");
1439 log(" state must be selected!\n");
1441 log(" -aggressive\n");
1442 log(" Per default some heuristics are used to reduce the number of cells\n");
1443 log(" considered for resource sharing to only large resources. This options\n");
1444 log(" turns this heuristics off, resulting in much more cells being considered\n");
1445 log(" for resource sharing.\n");
1448 log(" Only consider the simple part of the control logic in SAT solving, resulting\n");
1449 log(" in much easier SAT problems at the cost of maybe missing some opportunities\n");
1450 log(" for resource sharing.\n");
1453 log(" Only perform the first N merges, then stop. This is useful for debugging.\n");
1456 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
1458 ShareWorkerConfig config
;
1461 config
.opt_force
= false;
1462 config
.opt_aggressive
= false;
1463 config
.opt_fast
= false;
1465 config
.generic_uni_ops
.insert("$not");
1466 // config.generic_uni_ops.insert("$pos");
1467 config
.generic_uni_ops
.insert("$neg");
1469 config
.generic_cbin_ops
.insert("$and");
1470 config
.generic_cbin_ops
.insert("$or");
1471 config
.generic_cbin_ops
.insert("$xor");
1472 config
.generic_cbin_ops
.insert("$xnor");
1474 config
.generic_bin_ops
.insert("$shl");
1475 config
.generic_bin_ops
.insert("$shr");
1476 config
.generic_bin_ops
.insert("$sshl");
1477 config
.generic_bin_ops
.insert("$sshr");
1479 config
.generic_bin_ops
.insert("$lt");
1480 config
.generic_bin_ops
.insert("$le");
1481 config
.generic_bin_ops
.insert("$eq");
1482 config
.generic_bin_ops
.insert("$ne");
1483 config
.generic_bin_ops
.insert("$eqx");
1484 config
.generic_bin_ops
.insert("$nex");
1485 config
.generic_bin_ops
.insert("$ge");
1486 config
.generic_bin_ops
.insert("$gt");
1488 config
.generic_cbin_ops
.insert("$add");
1489 config
.generic_cbin_ops
.insert("$mul");
1491 config
.generic_bin_ops
.insert("$sub");
1492 config
.generic_bin_ops
.insert("$div");
1493 config
.generic_bin_ops
.insert("$mod");
1494 // config.generic_bin_ops.insert("$pow");
1496 config
.generic_uni_ops
.insert("$logic_not");
1497 config
.generic_cbin_ops
.insert("$logic_and");
1498 config
.generic_cbin_ops
.insert("$logic_or");
1500 config
.generic_other_ops
.insert("$alu");
1501 config
.generic_other_ops
.insert("$macc");
1503 log_header(design
, "Executing SHARE pass (SAT-based resource sharing).\n");
1506 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
1507 if (args
[argidx
] == "-force") {
1508 config
.opt_force
= true;
1511 if (args
[argidx
] == "-aggressive") {
1512 config
.opt_aggressive
= true;
1515 if (args
[argidx
] == "-fast") {
1516 config
.opt_fast
= true;
1519 if (args
[argidx
] == "-limit" && argidx
+1 < args
.size()) {
1520 config
.limit
= atoi(args
[++argidx
].c_str());
1525 extra_args(args
, argidx
, design
);
1527 for (auto &mod_it
: design
->modules_
)
1528 if (design
->selected(mod_it
.second
))
1529 ShareWorker(config
, design
, mod_it
.second
);
1533 PRIVATE_NAMESPACE_END