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
));
86 for (auto &port
: mem
.rd_ports
) {
87 if (GetSize(port
.addr
) > abits
)
88 abits
= GetSize(port
.addr
);
90 for (int i
= 0; i
< GetSize(mem
.rd_ports
); i
++)
92 auto &port1
= mem
.rd_ports
[i
];
95 for (int j
= i
+ 1; j
< GetSize(mem
.rd_ports
); j
++)
97 auto &port2
= mem
.rd_ports
[j
];
100 if (port1
.clk_enable
!= port2
.clk_enable
)
102 if (port1
.clk_enable
) {
103 if (port1
.clk
!= port2
.clk
)
105 if (port1
.clk_polarity
!= port2
.clk_polarity
)
108 if (port1
.en
!= port2
.en
)
110 if (port1
.arst
!= port2
.arst
)
112 if (port1
.srst
!= port2
.srst
)
114 if (port1
.ce_over_srst
!= port2
.ce_over_srst
)
116 // If the width of the ports doesn't match, they can still be
117 // merged by widening the narrow one. Check if the conditions
119 int wide_log2
= std::max(port1
.wide_log2
, port2
.wide_log2
);
120 SigSpec addr1
= sigmap_xmux(port1
.addr
);
121 SigSpec addr2
= sigmap_xmux(port2
.addr
);
122 addr1
.extend_u0(abits
);
123 addr2
.extend_u0(abits
);
124 if (GetSize(addr1
) <= wide_log2
)
126 if (GetSize(addr2
) <= wide_log2
)
128 if (!addr1
.extract(0, wide_log2
).is_fully_const())
130 if (!addr2
.extract(0, wide_log2
).is_fully_const())
132 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
)) {
133 // Incompatible addresses after widening. Last chance — widen both
134 // ports by one more bit to merge them.
138 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
))
140 if (!addr1
.extract(0, wide_log2
).is_fully_const())
142 if (!addr2
.extract(0, wide_log2
).is_fully_const())
145 // Combine init/reset values.
146 SigSpec sub1_c
= port1
.addr
.extract(0, wide_log2
);
147 log_assert(sub1_c
.is_fully_const());
148 int sub1
= sub1_c
.as_int();
149 SigSpec sub2_c
= port2
.addr
.extract(0, wide_log2
);
150 log_assert(sub2_c
.is_fully_const());
151 int sub2
= sub2_c
.as_int();
152 Const init_value
, arst_value
, srst_value
;
153 if (!merge_rst_value(mem
, init_value
, wide_log2
, port1
.init_value
, sub1
, port2
.init_value
, sub2
))
155 if (!merge_rst_value(mem
, arst_value
, wide_log2
, port1
.arst_value
, sub1
, port2
.arst_value
, sub2
))
157 if (!merge_rst_value(mem
, srst_value
, wide_log2
, port1
.srst_value
, sub1
, port2
.srst_value
, sub2
))
159 // At this point we are committed to the merge.
161 log(" Merging ports %d, %d (address %s).\n", i
, j
, log_signal(port1
.addr
));
164 mem
.prepare_rd_merge(i
, j
, &initvals
);
165 mem
.widen_prep(wide_log2
);
166 SigSpec new_data
= module
->addWire(NEW_ID
, mem
.width
<< wide_log2
);
167 module
->connect(port1
.data
, new_data
.extract(sub1
* mem
.width
, mem
.width
<< port1
.wide_log2
));
168 module
->connect(port2
.data
, new_data
.extract(sub2
* mem
.width
, mem
.width
<< port2
.wide_log2
));
169 for (int k
= 0; k
< wide_log2
; k
++)
170 port1
.addr
[k
] = State::S0
;
171 port1
.init_value
= init_value
;
172 port1
.arst_value
= arst_value
;
173 port1
.srst_value
= srst_value
;
174 port1
.wide_log2
= wide_log2
;
175 port1
.data
= new_data
;
176 port2
.removed
= true;
189 // ------------------------------------------------------
190 // Consolidate write ports that write to the same address
191 // (or close enough to be merged to wide ports)
192 // ------------------------------------------------------
194 bool consolidate_wr_by_addr(Mem
&mem
)
196 if (GetSize(mem
.wr_ports
) <= 1)
199 log("Consolidating write ports of memory %s.%s by address:\n", log_id(module
), log_id(mem
.memid
));
201 bool changed
= false;
203 for (auto &port
: mem
.wr_ports
) {
204 if (GetSize(port
.addr
) > abits
)
205 abits
= GetSize(port
.addr
);
207 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
209 auto &port1
= mem
.wr_ports
[i
];
212 if (!port1
.clk_enable
)
214 for (int j
= i
+ 1; j
< GetSize(mem
.wr_ports
); j
++)
216 auto &port2
= mem
.wr_ports
[j
];
219 if (!port2
.clk_enable
)
221 if (port1
.clk
!= port2
.clk
)
223 if (port1
.clk_polarity
!= port2
.clk_polarity
)
225 // If the width of the ports doesn't match, they can still be
226 // merged by widening the narrow one. Check if the conditions
228 int wide_log2
= std::max(port1
.wide_log2
, port2
.wide_log2
);
229 SigSpec addr1
= sigmap_xmux(port1
.addr
);
230 SigSpec addr2
= sigmap_xmux(port2
.addr
);
231 addr1
.extend_u0(abits
);
232 addr2
.extend_u0(abits
);
233 if (GetSize(addr1
) <= wide_log2
)
235 if (GetSize(addr2
) <= wide_log2
)
237 if (!addr1
.extract(0, wide_log2
).is_fully_const())
239 if (!addr2
.extract(0, wide_log2
).is_fully_const())
241 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
)) {
242 // Incompatible addresses after widening. Last chance — widen both
243 // ports by one more bit to merge them.
247 if (addr1
.extract_end(wide_log2
) != addr2
.extract_end(wide_log2
))
249 if (!addr1
.extract(0, wide_log2
).is_fully_const())
251 if (!addr2
.extract(0, wide_log2
).is_fully_const())
254 log(" Merging ports %d, %d (address %s).\n", i
, j
, log_signal(addr1
));
257 mem
.prepare_wr_merge(i
, j
, &initvals
);
258 mem
.widen_wr_port(i
, wide_log2
);
259 mem
.widen_wr_port(j
, wide_log2
);
261 while (pos
< GetSize(port1
.data
)) {
263 while (epos
< GetSize(port1
.data
) && port1
.en
[epos
] == port1
.en
[pos
] && port2
.en
[epos
] == port2
.en
[pos
])
265 int width
= epos
- pos
;
267 if (port2
.en
[pos
] == State::S0
) {
268 new_en
= port1
.en
[pos
];
269 } else if (port1
.en
[pos
] == State::S0
) {
270 port1
.data
.replace(pos
, port2
.data
.extract(pos
, width
));
271 new_en
= port2
.en
[pos
];
273 port1
.data
.replace(pos
, module
->Mux(NEW_ID
, port1
.data
.extract(pos
, width
), port2
.data
.extract(pos
, width
), port2
.en
[pos
]));
274 new_en
= module
->Or(NEW_ID
, port1
.en
[pos
], port2
.en
[pos
]);
276 for (int k
= pos
; k
< epos
; k
++)
277 port1
.en
[k
] = new_en
;
281 port2
.removed
= true;
292 // --------------------------------------------------------
293 // Consolidate write ports using sat-based resource sharing
294 // --------------------------------------------------------
296 void consolidate_wr_using_sat(Mem
&mem
)
298 if (GetSize(mem
.wr_ports
) <= 1)
301 // Get a list of ports that have any chance of being mergeable.
303 pool
<int> eligible_ports
;
305 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++) {
306 auto &port
= mem
.wr_ports
[i
];
307 std::vector
<RTLIL::SigBit
> bits
= modwalker
.sigmap(port
.en
);
308 for (auto bit
: bits
)
309 if (bit
== RTLIL::State::S1
)
310 goto port_is_always_active
;
311 eligible_ports
.insert(i
);
312 port_is_always_active
:;
315 if (eligible_ports
.size() <= 1)
318 log("Consolidating write ports of memory %s.%s using sat-based resource sharing:\n", log_id(module
), log_id(mem
.memid
));
320 // Group eligible ports by clock domain and width.
322 pool
<int> checked_ports
;
323 std::vector
<std::vector
<int>> groups
;
324 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
326 auto &port1
= mem
.wr_ports
[i
];
327 if (!eligible_ports
.count(i
))
329 if (checked_ports
.count(i
))
332 std::vector
<int> group
;
335 for (int j
= i
+ 1; j
< GetSize(mem
.wr_ports
); j
++)
337 auto &port2
= mem
.wr_ports
[j
];
338 if (!eligible_ports
.count(j
))
340 if (checked_ports
.count(j
))
342 if (port1
.clk_enable
!= port2
.clk_enable
)
344 if (port1
.clk_enable
) {
345 if (port1
.clk
!= port2
.clk
)
347 if (port1
.clk_polarity
!= port2
.clk_polarity
)
350 if (port1
.wide_log2
!= port2
.wide_log2
)
356 checked_ports
.insert(j
);
358 if (group
.size() <= 1)
361 groups
.push_back(group
);
364 bool changed
= false;
365 for (auto &group
: groups
) {
366 auto &some_port
= mem
.wr_ports
[group
[0]];
368 for (auto idx
: group
) {
371 ports
+= std::to_string(idx
);
373 if (!some_port
.clk_enable
) {
374 log(" Checking unclocked group, width %d: ports %s.\n", mem
.width
<< some_port
.wide_log2
, ports
.c_str());
376 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());
379 // Okay, time to actually run the SAT solver.
381 QuickConeSat
qcsat(modwalker
);
383 // create SAT representation of common input cone of all considered EN signals
385 dict
<int, int> port_to_sat_variable
;
387 for (auto idx
: group
)
388 port_to_sat_variable
[idx
] = qcsat
.ez
->expression(qcsat
.ez
->OpOr
, qcsat
.importSig(mem
.wr_ports
[idx
].en
));
392 log(" Common input cone for all EN signals: %d cells.\n", GetSize(qcsat
.imported_cells
));
394 log(" Size of unconstrained SAT problem: %d variables, %d clauses\n", qcsat
.ez
->numCnfVariables(), qcsat
.ez
->numCnfClauses());
396 // now try merging the ports.
398 for (int ii
= 0; ii
< GetSize(group
); ii
++) {
399 int idx1
= group
[ii
];
400 auto &port1
= mem
.wr_ports
[idx1
];
403 for (int jj
= ii
+ 1; jj
< GetSize(group
); jj
++) {
404 int idx2
= group
[jj
];
405 auto &port2
= mem
.wr_ports
[idx2
];
409 if (qcsat
.ez
->solve(port_to_sat_variable
.at(idx1
), port_to_sat_variable
.at(idx2
))) {
410 log(" According to SAT solver sharing of port %d with port %d is not possible.\n", idx1
, idx2
);
414 log(" Merging port %d into port %d.\n", idx2
, idx1
);
415 mem
.prepare_wr_merge(idx1
, idx2
, &initvals
);
416 port_to_sat_variable
.at(idx1
) = qcsat
.ez
->OR(port_to_sat_variable
.at(idx1
), port_to_sat_variable
.at(idx2
));
418 RTLIL::SigSpec last_addr
= port1
.addr
;
419 RTLIL::SigSpec last_data
= port1
.data
;
420 std::vector
<RTLIL::SigBit
> last_en
= modwalker
.sigmap(port1
.en
);
422 RTLIL::SigSpec this_addr
= port2
.addr
;
423 RTLIL::SigSpec this_data
= port2
.data
;
424 std::vector
<RTLIL::SigBit
> this_en
= modwalker
.sigmap(port2
.en
);
426 RTLIL::SigBit this_en_active
= module
->ReduceOr(NEW_ID
, this_en
);
428 if (GetSize(last_addr
) < GetSize(this_addr
))
429 last_addr
.extend_u0(GetSize(this_addr
));
431 this_addr
.extend_u0(GetSize(last_addr
));
433 SigSpec new_addr
= module
->Mux(NEW_ID
, last_addr
.extract_end(port1
.wide_log2
), this_addr
.extract_end(port1
.wide_log2
), this_en_active
);
435 port1
.addr
= SigSpec({new_addr
, port1
.addr
.extract(0, port1
.wide_log2
)});
436 port1
.data
= module
->Mux(NEW_ID
, last_data
, this_data
, this_en_active
);
438 std::map
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>, int> groups_en
;
439 RTLIL::SigSpec grouped_last_en
, grouped_this_en
, en
;
440 RTLIL::Wire
*grouped_en
= module
->addWire(NEW_ID
, 0);
442 for (int j
= 0; j
< int(this_en
.size()); j
++) {
443 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(last_en
[j
], this_en
[j
]);
444 if (!groups_en
.count(key
)) {
445 grouped_last_en
.append(last_en
[j
]);
446 grouped_this_en
.append(this_en
[j
]);
447 groups_en
[key
] = grouped_en
->width
;
450 en
.append(RTLIL::SigSpec(grouped_en
, groups_en
[key
]));
453 module
->addMux(NEW_ID
, grouped_last_en
, grouped_this_en
, this_en_active
, grouped_en
);
456 port2
.removed
= true;
471 MemoryShareWorker(RTLIL::Design
*design
, bool flag_widen
, bool flag_sat
) : design(design
), modwalker(design
), flag_widen(flag_widen
), flag_sat(flag_sat
) {}
473 void operator()(RTLIL::Module
* module
)
475 std::vector
<Mem
> memories
= Mem::get_selected_memories(module
);
477 this->module
= module
;
479 initvals
.set(&sigmap
, module
);
481 sigmap_xmux
= sigmap
;
482 for (auto cell
: module
->cells())
484 if (cell
->type
== ID($mux
))
486 RTLIL::SigSpec sig_a
= sigmap_xmux(cell
->getPort(ID::A
));
487 RTLIL::SigSpec sig_b
= sigmap_xmux(cell
->getPort(ID::B
));
489 if (sig_a
.is_fully_undef())
490 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_b
);
491 else if (sig_b
.is_fully_undef())
492 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_a
);
496 for (auto &mem
: memories
) {
497 while (consolidate_rd_by_addr(mem
));
498 while (consolidate_wr_by_addr(mem
));
504 modwalker
.setup(module
);
506 for (auto &mem
: memories
)
507 consolidate_wr_using_sat(mem
);
511 struct MemorySharePass
: public Pass
{
512 MemorySharePass() : Pass("memory_share", "consolidate memory ports") { }
515 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
517 log(" memory_share [-nosat] [-nowiden] [selection]\n");
519 log("This pass merges share-able memory ports into single memory ports.\n");
521 log("The following methods are used to consolidate the number of memory ports:\n");
523 log(" - When multiple write ports access the same address then this is converted\n");
524 log(" to a single write port with a more complex data and/or enable logic path.\n");
526 log(" - When multiple read or write ports access adjacent aligned addresses, they are\n");
527 log(" merged to a single wide read or write port. This transformation can be\n");
528 log(" disabled with the \"-nowiden\" option.\n");
530 log(" - When multiple write ports are never accessed at the same time (a SAT\n");
531 log(" solver is used to determine this), then the ports are merged into a single\n");
532 log(" write port. This transformation can be disabled with the \"-nosat\" option.\n");
534 log("Note that in addition to the algorithms implemented in this pass, the $memrd\n");
535 log("and $memwr cells are also subject to generic resource sharing passes (and other\n");
536 log("optimizations) such as \"share\" and \"opt_merge\".\n");
539 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) override
{
540 bool flag_widen
= true;
541 bool flag_sat
= true;
542 log_header(design
, "Executing MEMORY_SHARE pass (consolidating $memrd/$memwr cells).\n");
544 for (argidx
= 1; argidx
< args
.size(); argidx
++)
546 if (args
[argidx
] == "-nosat")
551 if (args
[argidx
] == "-nowiden")
558 extra_args(args
, argidx
, design
);
559 MemoryShareWorker
msw(design
, flag_widen
, flag_sat
);
561 for (auto module
: design
->selected_modules())
566 PRIVATE_NAMESPACE_END