ceea725d8cadbe92cc5fdb63f8386c50620b8f3e
2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Claire Xenia Wolf <claire@yosyshq.com>
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/qcsat.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/modtools.h"
24 #include "kernel/mem.h"
25 #include "kernel/ffinit.h"
28 PRIVATE_NAMESPACE_BEGIN
30 struct MemoryShareWorker
32 RTLIL::Design
*design
;
33 RTLIL::Module
*module
;
34 SigMap sigmap
, sigmap_xmux
;
40 // --------------------------------------------------
41 // Consolidate read ports that read the same address
42 // (or close enough to be merged to wide ports)
43 // --------------------------------------------------
45 // A simple function to detect ports that couldn't possibly collide
46 // because of opposite const address bits (simplistic, but enough
47 // to fix problems with inferring wide ports).
48 bool rdwr_can_collide(Mem
&mem
, int ridx
, int widx
) {
49 auto &rport
= mem
.rd_ports
[ridx
];
50 auto &wport
= mem
.wr_ports
[widx
];
51 for (int i
= std::max(rport
.wide_log2
, wport
.wide_log2
); i
< GetSize(rport
.addr
) && i
< GetSize(wport
.addr
); i
++) {
52 if (rport
.addr
[i
] == State::S1
&& wport
.addr
[i
] == State::S0
)
54 if (rport
.addr
[i
] == State::S0
&& wport
.addr
[i
] == State::S1
)
60 bool merge_rst_value(Mem
&mem
, Const
&res
, int wide_log2
, const Const
&src1
, int sub1
, const Const
&src2
, int sub2
) {
61 res
= Const(State::Sx
, mem
.width
<< wide_log2
);
62 for (int i
= 0; i
< GetSize(src1
); i
++)
63 res
[i
+ sub1
* mem
.width
] = src1
[i
];
64 for (int i
= 0; i
< GetSize(src2
); i
++) {
65 if (src2
[i
] == State::Sx
)
67 auto &dst
= res
[i
+ sub2
* mem
.width
];
77 bool consolidate_rd_by_addr(Mem
&mem
)
79 if (GetSize(mem
.rd_ports
) <= 1)
82 log("Consolidating read ports of memory %s.%s by address:\n", log_id(module
), log_id(mem
.memid
));
85 for (int i
= 0; i
< GetSize(mem
.rd_ports
); i
++)
87 auto &port1
= mem
.rd_ports
[i
];
90 for (int j
= i
+ 1; j
< GetSize(mem
.rd_ports
); j
++)
92 auto &port2
= mem
.rd_ports
[j
];
95 if (port1
.clk_enable
!= port2
.clk_enable
)
97 if (port1
.clk_enable
) {
98 if (port1
.clk
!= port2
.clk
)
100 if (port1
.clk_polarity
!= port2
.clk_polarity
)
103 if (port1
.en
!= port2
.en
)
105 if (port1
.arst
!= port2
.arst
)
107 if (port1
.srst
!= port2
.srst
)
109 if (port1
.ce_over_srst
!= port2
.ce_over_srst
)
111 // If the width of the ports doesn't match, they can still be
112 // merged by widening the narrow one. Check if the conditions
114 int wide_log2
= std::max(port1
.wide_log2
, port2
.wide_log2
);
115 SigSpec addr1
= sigmap_xmux(port1
.addr
);
116 SigSpec addr2
= sigmap_xmux(port2
.addr
);
117 if (GetSize(addr1
) <= wide_log2
)
119 if (GetSize(addr2
) <= wide_log2
)
121 if (!addr1
.extract(0, wide_log2
).is_fully_const())
123 if (!addr2
.extract(0, wide_log2
).is_fully_const())
125 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
)) {
126 // Incompatible addresses after widening. Last chance — widen both
127 // ports by one more bit to merge them.
131 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
))
133 if (!addr1
.extract(0, wide_log2
).is_fully_const())
135 if (!addr2
.extract(0, wide_log2
).is_fully_const())
138 // Combine init/reset values.
139 SigSpec sub1_c
= port1
.addr
.extract(0, wide_log2
);
140 log_assert(sub1_c
.is_fully_const());
141 int sub1
= sub1_c
.as_int();
142 SigSpec sub2_c
= port2
.addr
.extract(0, wide_log2
);
143 log_assert(sub2_c
.is_fully_const());
144 int sub2
= sub2_c
.as_int();
145 Const init_value
, arst_value
, srst_value
;
146 if (!merge_rst_value(mem
, init_value
, wide_log2
, port1
.init_value
, sub1
, port2
.init_value
, sub2
))
148 if (!merge_rst_value(mem
, arst_value
, wide_log2
, port1
.arst_value
, sub1
, port2
.arst_value
, sub2
))
150 if (!merge_rst_value(mem
, srst_value
, wide_log2
, port1
.srst_value
, sub1
, port2
.srst_value
, sub2
))
152 // At this point we are committed to the merge.
154 log(" Merging ports %d, %d (address %s).\n", i
, j
, log_signal(port1
.addr
));
157 mem
.prepare_rd_merge(i
, j
, &initvals
);
158 mem
.widen_prep(wide_log2
);
159 SigSpec new_data
= module
->addWire(NEW_ID
, mem
.width
<< wide_log2
);
160 module
->connect(port1
.data
, new_data
.extract(sub1
* mem
.width
, mem
.width
<< port1
.wide_log2
));
161 module
->connect(port2
.data
, new_data
.extract(sub2
* mem
.width
, mem
.width
<< port2
.wide_log2
));
162 for (int k
= 0; k
< wide_log2
; k
++)
163 port1
.addr
[k
] = State::S0
;
164 port1
.init_value
= init_value
;
165 port1
.arst_value
= arst_value
;
166 port1
.srst_value
= srst_value
;
167 port1
.wide_log2
= wide_log2
;
168 port1
.data
= new_data
;
169 port2
.removed
= true;
182 // ------------------------------------------------------
183 // Consolidate write ports that write to the same address
184 // (or close enough to be merged to wide ports)
185 // ------------------------------------------------------
187 bool consolidate_wr_by_addr(Mem
&mem
)
189 if (GetSize(mem
.wr_ports
) <= 1)
192 log("Consolidating write ports of memory %s.%s by address:\n", log_id(module
), log_id(mem
.memid
));
194 bool changed
= false;
195 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
197 auto &port1
= mem
.wr_ports
[i
];
200 if (!port1
.clk_enable
)
202 for (int j
= i
+ 1; j
< GetSize(mem
.wr_ports
); j
++)
204 auto &port2
= mem
.wr_ports
[j
];
207 if (!port2
.clk_enable
)
209 if (port1
.clk
!= port2
.clk
)
211 if (port1
.clk_polarity
!= port2
.clk_polarity
)
213 // If the width of the ports doesn't match, they can still be
214 // merged by widening the narrow one. Check if the conditions
216 int wide_log2
= std::max(port1
.wide_log2
, port2
.wide_log2
);
217 SigSpec addr1
= sigmap_xmux(port1
.addr
);
218 SigSpec addr2
= sigmap_xmux(port2
.addr
);
219 if (GetSize(addr1
) <= wide_log2
)
221 if (GetSize(addr2
) <= wide_log2
)
223 if (!addr1
.extract(0, wide_log2
).is_fully_const())
225 if (!addr2
.extract(0, wide_log2
).is_fully_const())
227 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
)) {
228 // Incompatible addresses after widening. Last chance — widen both
229 // ports by one more bit to merge them.
233 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
))
235 if (!addr1
.extract(0, wide_log2
).is_fully_const())
237 if (!addr2
.extract(0, wide_log2
).is_fully_const())
240 log(" Merging ports %d, %d (address %s).\n", i
, j
, log_signal(addr1
));
243 mem
.prepare_wr_merge(i
, j
, &initvals
);
244 mem
.widen_wr_port(i
, wide_log2
);
245 mem
.widen_wr_port(j
, wide_log2
);
247 while (pos
< GetSize(port1
.data
)) {
249 while (epos
< GetSize(port1
.data
) && port1
.en
[epos
] == port1
.en
[pos
] && port2
.en
[epos
] == port2
.en
[pos
])
251 int width
= epos
- pos
;
253 if (port2
.en
[pos
] == State::S0
) {
254 new_en
= port1
.en
[pos
];
255 } else if (port1
.en
[pos
] == State::S0
) {
256 port1
.data
.replace(pos
, port2
.data
.extract(pos
, width
));
257 new_en
= port2
.en
[pos
];
259 port1
.data
.replace(pos
, module
->Mux(NEW_ID
, port1
.data
.extract(pos
, width
), port2
.data
.extract(pos
, width
), port2
.en
[pos
]));
260 new_en
= module
->Or(NEW_ID
, port1
.en
[pos
], port2
.en
[pos
]);
262 for (int k
= pos
; k
< epos
; k
++)
263 port1
.en
[k
] = new_en
;
267 port2
.removed
= true;
278 // --------------------------------------------------------
279 // Consolidate write ports using sat-based resource sharing
280 // --------------------------------------------------------
282 void consolidate_wr_using_sat(Mem
&mem
)
284 if (GetSize(mem
.wr_ports
) <= 1)
287 // Get a list of ports that have any chance of being mergeable.
289 pool
<int> eligible_ports
;
291 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++) {
292 auto &port
= mem
.wr_ports
[i
];
293 std::vector
<RTLIL::SigBit
> bits
= modwalker
.sigmap(port
.en
);
294 for (auto bit
: bits
)
295 if (bit
== RTLIL::State::S1
)
296 goto port_is_always_active
;
297 eligible_ports
.insert(i
);
298 port_is_always_active
:;
301 if (eligible_ports
.size() <= 1)
304 log("Consolidating write ports of memory %s.%s using sat-based resource sharing:\n", log_id(module
), log_id(mem
.memid
));
306 // Group eligible ports by clock domain and width.
308 pool
<int> checked_ports
;
309 std::vector
<std::vector
<int>> groups
;
310 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
312 auto &port1
= mem
.wr_ports
[i
];
313 if (!eligible_ports
.count(i
))
315 if (checked_ports
.count(i
))
318 std::vector
<int> group
;
321 for (int j
= i
+ 1; j
< GetSize(mem
.wr_ports
); j
++)
323 auto &port2
= mem
.wr_ports
[j
];
324 if (!eligible_ports
.count(j
))
326 if (checked_ports
.count(j
))
328 if (port1
.clk_enable
!= port2
.clk_enable
)
330 if (port1
.clk_enable
) {
331 if (port1
.clk
!= port2
.clk
)
333 if (port1
.clk_polarity
!= port2
.clk_polarity
)
336 if (port1
.wide_log2
!= port2
.wide_log2
)
342 checked_ports
.insert(j
);
344 if (group
.size() <= 1)
347 groups
.push_back(group
);
350 bool changed
= false;
351 for (auto &group
: groups
) {
352 auto &some_port
= mem
.wr_ports
[group
[0]];
354 for (auto idx
: group
) {
357 ports
+= std::to_string(idx
);
359 if (!some_port
.clk_enable
) {
360 log(" Checking unclocked group, width %d: ports %s.\n", mem
.width
<< some_port
.wide_log2
, ports
.c_str());
362 log(" Checking group clocked with %sedge %s, width %d: ports %s.\n", some_port
.clk_polarity
? "pos" : "neg", log_signal(some_port
.clk
), mem
.width
<< some_port
.wide_log2
, ports
.c_str());
365 // Okay, time to actually run the SAT solver.
367 QuickConeSat
qcsat(modwalker
);
369 // create SAT representation of common input cone of all considered EN signals
371 dict
<int, int> port_to_sat_variable
;
373 for (auto idx
: group
)
374 port_to_sat_variable
[idx
] = qcsat
.ez
->expression(qcsat
.ez
->OpOr
, qcsat
.importSig(mem
.wr_ports
[idx
].en
));
378 log(" Common input cone for all EN signals: %d cells.\n", GetSize(qcsat
.imported_cells
));
380 log(" Size of unconstrained SAT problem: %d variables, %d clauses\n", qcsat
.ez
->numCnfVariables(), qcsat
.ez
->numCnfClauses());
382 // now try merging the ports.
384 for (int ii
= 0; ii
< GetSize(group
); ii
++) {
385 int idx1
= group
[ii
];
386 auto &port1
= mem
.wr_ports
[idx1
];
389 for (int jj
= ii
+ 1; jj
< GetSize(group
); jj
++) {
390 int idx2
= group
[jj
];
391 auto &port2
= mem
.wr_ports
[idx2
];
395 if (qcsat
.ez
->solve(port_to_sat_variable
.at(idx1
), port_to_sat_variable
.at(idx2
))) {
396 log(" According to SAT solver sharing of port %d with port %d is not possible.\n", idx1
, idx2
);
400 log(" Merging port %d into port %d.\n", idx2
, idx1
);
401 mem
.prepare_wr_merge(idx1
, idx2
, &initvals
);
402 port_to_sat_variable
.at(idx1
) = qcsat
.ez
->OR(port_to_sat_variable
.at(idx1
), port_to_sat_variable
.at(idx2
));
404 RTLIL::SigSpec last_addr
= port1
.addr
;
405 RTLIL::SigSpec last_data
= port1
.data
;
406 std::vector
<RTLIL::SigBit
> last_en
= modwalker
.sigmap(port1
.en
);
408 RTLIL::SigSpec this_addr
= port2
.addr
;
409 RTLIL::SigSpec this_data
= port2
.data
;
410 std::vector
<RTLIL::SigBit
> this_en
= modwalker
.sigmap(port2
.en
);
412 RTLIL::SigBit this_en_active
= module
->ReduceOr(NEW_ID
, this_en
);
414 if (GetSize(last_addr
) < GetSize(this_addr
))
415 last_addr
.extend_u0(GetSize(this_addr
));
417 this_addr
.extend_u0(GetSize(last_addr
));
419 SigSpec new_addr
= module
->Mux(NEW_ID
, last_addr
.extract_end(port1
.wide_log2
), this_addr
.extract_end(port1
.wide_log2
), this_en_active
);
421 port1
.addr
= SigSpec({new_addr
, port1
.addr
.extract(0, port1
.wide_log2
)});
422 port1
.data
= module
->Mux(NEW_ID
, last_data
, this_data
, this_en_active
);
424 std::map
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>, int> groups_en
;
425 RTLIL::SigSpec grouped_last_en
, grouped_this_en
, en
;
426 RTLIL::Wire
*grouped_en
= module
->addWire(NEW_ID
, 0);
428 for (int j
= 0; j
< int(this_en
.size()); j
++) {
429 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(last_en
[j
], this_en
[j
]);
430 if (!groups_en
.count(key
)) {
431 grouped_last_en
.append(last_en
[j
]);
432 grouped_this_en
.append(this_en
[j
]);
433 groups_en
[key
] = grouped_en
->width
;
436 en
.append(RTLIL::SigSpec(grouped_en
, groups_en
[key
]));
439 module
->addMux(NEW_ID
, grouped_last_en
, grouped_this_en
, this_en_active
, grouped_en
);
442 port2
.removed
= true;
457 MemoryShareWorker(RTLIL::Design
*design
, bool flag_widen
, bool flag_sat
) : design(design
), modwalker(design
), flag_widen(flag_widen
), flag_sat(flag_sat
) {}
459 void operator()(RTLIL::Module
* module
)
461 std::vector
<Mem
> memories
= Mem::get_selected_memories(module
);
463 this->module
= module
;
465 initvals
.set(&sigmap
, module
);
467 sigmap_xmux
= sigmap
;
468 for (auto cell
: module
->cells())
470 if (cell
->type
== ID($mux
))
472 RTLIL::SigSpec sig_a
= sigmap_xmux(cell
->getPort(ID::A
));
473 RTLIL::SigSpec sig_b
= sigmap_xmux(cell
->getPort(ID::B
));
475 if (sig_a
.is_fully_undef())
476 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_b
);
477 else if (sig_b
.is_fully_undef())
478 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_a
);
482 for (auto &mem
: memories
) {
483 while (consolidate_rd_by_addr(mem
));
484 while (consolidate_wr_by_addr(mem
));
490 modwalker
.setup(module
);
492 for (auto &mem
: memories
)
493 consolidate_wr_using_sat(mem
);
497 struct MemorySharePass
: public Pass
{
498 MemorySharePass() : Pass("memory_share", "consolidate memory ports") { }
501 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
503 log(" memory_share [-nosat] [-nowiden] [selection]\n");
505 log("This pass merges share-able memory ports into single memory ports.\n");
507 log("The following methods are used to consolidate the number of memory ports:\n");
509 log(" - When multiple write ports access the same address then this is converted\n");
510 log(" to a single write port with a more complex data and/or enable logic path.\n");
512 log(" - When multiple read or write ports access adjacent aligned addresses, they are\n");
513 log(" merged to a single wide read or write port. This transformation can be\n");
514 log(" disabled with the \"-nowiden\" option.\n");
516 log(" - When multiple write ports are never accessed at the same time (a SAT\n");
517 log(" solver is used to determine this), then the ports are merged into a single\n");
518 log(" write port. This transformation can be disabled with the \"-nosat\" option.\n");
520 log("Note that in addition to the algorithms implemented in this pass, the $memrd\n");
521 log("and $memwr cells are also subject to generic resource sharing passes (and other\n");
522 log("optimizations) such as \"share\" and \"opt_merge\".\n");
525 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) override
{
526 bool flag_widen
= true;
527 bool flag_sat
= true;
528 log_header(design
, "Executing MEMORY_SHARE pass (consolidating $memrd/$memwr cells).\n");
530 for (argidx
= 1; argidx
< args
.size(); argidx
++)
532 if (args
[argidx
] == "-nosat")
537 if (args
[argidx
] == "-nowiden")
544 extra_args(args
, 1, design
);
545 MemoryShareWorker
msw(design
, flag_widen
, flag_sat
);
547 for (auto module
: design
->selected_modules())
552 PRIVATE_NAMESPACE_END