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/mem.h"
27 PRIVATE_NAMESPACE_BEGIN
29 struct MemoryShareWorker
31 RTLIL::Design
*design
;
32 RTLIL::Module
*module
;
33 SigMap sigmap
, sigmap_xmux
;
38 // ------------------------------------------------------
39 // Consolidate write ports that write to the same address
40 // ------------------------------------------------------
42 RTLIL::SigSpec
mask_en_naive(RTLIL::SigSpec do_mask
, RTLIL::SigSpec bits
, RTLIL::SigSpec mask_bits
)
44 // this is the naive version of the function that does not care about grouping the EN bits.
46 RTLIL::SigSpec inv_mask_bits
= module
->Not(NEW_ID
, mask_bits
);
47 RTLIL::SigSpec inv_mask_bits_filtered
= module
->Mux(NEW_ID
, RTLIL::SigSpec(RTLIL::State::S1
, bits
.size()), inv_mask_bits
, do_mask
);
48 RTLIL::SigSpec result
= module
->And(NEW_ID
, inv_mask_bits_filtered
, bits
);
52 RTLIL::SigSpec
mask_en_grouped(RTLIL::SigSpec do_mask
, RTLIL::SigSpec bits
, RTLIL::SigSpec mask_bits
)
54 // this version of the function preserves the bit grouping in the EN bits.
56 std::vector
<RTLIL::SigBit
> v_bits
= bits
;
57 std::vector
<RTLIL::SigBit
> v_mask_bits
= mask_bits
;
59 std::map
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>, std::pair
<int, std::vector
<int>>> groups
;
60 RTLIL::SigSpec grouped_bits
, grouped_mask_bits
;
62 for (int i
= 0; i
< bits
.size(); i
++) {
63 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(v_bits
[i
], v_mask_bits
[i
]);
64 if (groups
.count(key
) == 0) {
65 groups
[key
].first
= grouped_bits
.size();
66 grouped_bits
.append(v_bits
[i
]);
67 grouped_mask_bits
.append(v_mask_bits
[i
]);
69 groups
[key
].second
.push_back(i
);
72 std::vector
<RTLIL::SigBit
> grouped_result
= mask_en_naive(do_mask
, grouped_bits
, grouped_mask_bits
);
73 RTLIL::SigSpec result
;
75 for (int i
= 0; i
< bits
.size(); i
++) {
76 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(v_bits
[i
], v_mask_bits
[i
]);
77 result
.append(grouped_result
.at(groups
.at(key
).first
));
83 void merge_en_data(RTLIL::SigSpec
&merged_en
, RTLIL::SigSpec
&merged_data
, RTLIL::SigSpec next_en
, RTLIL::SigSpec next_data
)
85 std::vector
<RTLIL::SigBit
> v_old_en
= merged_en
;
86 std::vector
<RTLIL::SigBit
> v_next_en
= next_en
;
88 // The new merged_en signal is just the old merged_en signal and next_en OR'ed together.
89 // But of course we need to preserve the bit grouping..
91 std::map
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>, int> groups
;
92 std::vector
<RTLIL::SigBit
> grouped_old_en
, grouped_next_en
;
93 RTLIL::SigSpec new_merged_en
;
95 for (int i
= 0; i
< int(v_old_en
.size()); i
++) {
96 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(v_old_en
[i
], v_next_en
[i
]);
97 if (groups
.count(key
) == 0) {
98 groups
[key
] = grouped_old_en
.size();
99 grouped_old_en
.push_back(key
.first
);
100 grouped_next_en
.push_back(key
.second
);
104 std::vector
<RTLIL::SigBit
> grouped_new_en
= module
->Or(NEW_ID
, grouped_old_en
, grouped_next_en
);
106 for (int i
= 0; i
< int(v_old_en
.size()); i
++) {
107 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(v_old_en
[i
], v_next_en
[i
]);
108 new_merged_en
.append(grouped_new_en
.at(groups
.at(key
)));
111 // Create the new merged_data signal.
113 RTLIL::SigSpec
new_merged_data(RTLIL::State::Sx
, merged_data
.size());
115 RTLIL::SigSpec old_data_set
= module
->And(NEW_ID
, merged_en
, merged_data
);
116 RTLIL::SigSpec old_data_unset
= module
->And(NEW_ID
, merged_en
, module
->Not(NEW_ID
, merged_data
));
118 RTLIL::SigSpec new_data_set
= module
->And(NEW_ID
, next_en
, next_data
);
119 RTLIL::SigSpec new_data_unset
= module
->And(NEW_ID
, next_en
, module
->Not(NEW_ID
, next_data
));
121 new_merged_data
= module
->Or(NEW_ID
, new_merged_data
, old_data_set
);
122 new_merged_data
= module
->And(NEW_ID
, new_merged_data
, module
->Not(NEW_ID
, old_data_unset
));
124 new_merged_data
= module
->Or(NEW_ID
, new_merged_data
, new_data_set
);
125 new_merged_data
= module
->And(NEW_ID
, new_merged_data
, module
->Not(NEW_ID
, new_data_unset
));
127 // Update merged_* signals
129 merged_en
= new_merged_en
;
130 merged_data
= new_merged_data
;
133 void consolidate_wr_by_addr(Mem
&mem
)
135 if (GetSize(mem
.wr_ports
) <= 1)
138 log("Consolidating write ports of memory %s.%s by address:\n", log_id(module
), log_id(mem
.memid
));
140 std::map
<RTLIL::SigSpec
, int> last_port_by_addr
;
141 std::vector
<std::vector
<bool>> active_bits_on_port
;
143 bool cache_clk_enable
= false;
144 bool cache_clk_polarity
= false;
145 RTLIL::SigSpec cache_clk
;
146 int cache_wide_log2
= 0;
148 bool changed
= false;
150 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
152 auto &port
= mem
.wr_ports
[i
];
153 RTLIL::SigSpec addr
= sigmap_xmux(port
.addr
);
155 if (port
.clk_enable
!= cache_clk_enable
||
156 port
.wide_log2
!= cache_wide_log2
||
157 (cache_clk_enable
&& (sigmap(port
.clk
) != cache_clk
||
158 port
.clk_polarity
!= cache_clk_polarity
)))
160 cache_clk_enable
= port
.clk_enable
;
161 cache_clk_polarity
= port
.clk_polarity
;
162 cache_clk
= sigmap(port
.clk
);
163 cache_wide_log2
= port
.wide_log2
;
164 last_port_by_addr
.clear();
166 if (cache_clk_enable
)
167 log(" New clock domain: %s %s\n", cache_clk_polarity
? "posedge" : "negedge", log_signal(cache_clk
));
169 log(" New clock domain: unclocked\n");
172 log(" Port %d has addr %s.\n", i
, log_signal(addr
));
174 log(" Active bits: ");
175 std::vector
<RTLIL::SigBit
> en_bits
= sigmap(port
.en
);
176 active_bits_on_port
.push_back(std::vector
<bool>(en_bits
.size()));
177 for (int k
= int(en_bits
.size())-1; k
>= 0; k
--) {
178 active_bits_on_port
[i
][k
] = en_bits
[k
].wire
!= NULL
|| en_bits
[k
].data
!= RTLIL::State::S0
;
179 log("%c", active_bits_on_port
[i
][k
] ? '1' : '0');
183 if (last_port_by_addr
.count(addr
))
185 int last_i
= last_port_by_addr
.at(addr
);
186 log(" Merging port %d into this one.\n", last_i
);
188 bool found_overlapping_bits
= false;
189 for (int k
= 0; k
< int(en_bits
.size()); k
++) {
190 if (active_bits_on_port
[i
][k
] && active_bits_on_port
[last_i
][k
])
191 found_overlapping_bits
= true;
192 active_bits_on_port
[i
][k
] = active_bits_on_port
[i
][k
] || active_bits_on_port
[last_i
][k
];
195 // Force this ports addr input to addr directly (skip don't care muxes)
199 // If any of the ports between `last_i' and `i' write to the same address, this
200 // will have priority over whatever `last_i` wrote. So we need to revisit those
201 // ports and mask the EN bits accordingly.
203 RTLIL::SigSpec merged_en
= sigmap(mem
.wr_ports
[last_i
].en
);
205 for (int j
= last_i
+1; j
< i
; j
++)
207 if (mem
.wr_ports
[j
].removed
)
210 for (int k
= 0; k
< int(en_bits
.size()); k
++)
211 if (active_bits_on_port
[i
][k
] && active_bits_on_port
[j
][k
])
212 goto found_overlapping_bits_i_j
;
215 found_overlapping_bits_i_j
:
216 log(" Creating collosion-detect logic for port %d.\n", j
);
217 RTLIL::SigSpec is_same_addr
= module
->addWire(NEW_ID
);
218 module
->addEq(NEW_ID
, addr
, mem
.wr_ports
[j
].addr
, is_same_addr
);
219 merged_en
= mask_en_grouped(is_same_addr
, merged_en
, sigmap(mem
.wr_ports
[j
].en
));
223 // Then we need to merge the (masked) EN and the DATA signals.
225 RTLIL::SigSpec merged_data
= mem
.wr_ports
[last_i
].data
;
226 if (found_overlapping_bits
) {
227 log(" Creating logic for merging DATA and EN ports.\n");
228 merge_en_data(merged_en
, merged_data
, sigmap(port
.en
), sigmap(port
.data
));
230 RTLIL::SigSpec cell_en
= sigmap(port
.en
);
231 RTLIL::SigSpec cell_data
= sigmap(port
.data
);
232 for (int k
= 0; k
< int(en_bits
.size()); k
++)
233 if (!active_bits_on_port
[last_i
][k
]) {
234 merged_en
.replace(k
, cell_en
.extract(k
, 1));
235 merged_data
.replace(k
, cell_data
.extract(k
, 1));
239 // Connect the new EN and DATA signals and remove the old write port.
242 port
.data
= merged_data
;
244 mem
.wr_ports
[last_i
].removed
= true;
247 log(" Active bits: ");
248 std::vector
<RTLIL::SigBit
> en_bits
= sigmap(port
.en
);
249 active_bits_on_port
.push_back(std::vector
<bool>(en_bits
.size()));
250 for (int k
= int(en_bits
.size())-1; k
>= 0; k
--)
251 log("%c", active_bits_on_port
[i
][k
] ? '1' : '0');
255 last_port_by_addr
[addr
] = i
;
263 // --------------------------------------------------------
264 // Consolidate write ports using sat-based resource sharing
265 // --------------------------------------------------------
267 void consolidate_wr_using_sat(Mem
&mem
)
269 if (GetSize(mem
.wr_ports
) <= 1)
273 SatGen
satgen(ez
.get(), &modwalker
.sigmap
);
275 // find list of considered ports and port pairs
277 std::set
<int> considered_ports
;
278 std::set
<int> considered_port_pairs
;
280 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++) {
281 auto &port
= mem
.wr_ports
[i
];
282 std::vector
<RTLIL::SigBit
> bits
= modwalker
.sigmap(port
.en
);
283 for (auto bit
: bits
)
284 if (bit
== RTLIL::State::S1
)
285 goto port_is_always_active
;
286 if (modwalker
.has_drivers(bits
))
287 considered_ports
.insert(i
);
288 port_is_always_active
:;
291 log("Consolidating write ports of memory %s.%s using sat-based resource sharing:\n", log_id(module
), log_id(mem
.memid
));
293 bool cache_clk_enable
= false;
294 bool cache_clk_polarity
= false;
295 RTLIL::SigSpec cache_clk
;
296 int cache_wide_log2
= 0;
298 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
300 auto &port
= mem
.wr_ports
[i
];
302 if (port
.clk_enable
!= cache_clk_enable
||
303 port
.wide_log2
!= cache_wide_log2
||
304 (cache_clk_enable
&& (sigmap(port
.clk
) != cache_clk
||
305 port
.clk_polarity
!= cache_clk_polarity
)))
307 cache_clk_enable
= port
.clk_enable
;
308 cache_clk_polarity
= port
.clk_polarity
;
309 cache_clk
= sigmap(port
.clk
);
310 cache_wide_log2
= port
.wide_log2
;
312 else if (i
> 0 && considered_ports
.count(i
-1) && considered_ports
.count(i
))
313 considered_port_pairs
.insert(i
);
315 if (cache_clk_enable
)
316 log(" Port %d on %s %s: %s\n", i
,
317 cache_clk_polarity
? "posedge" : "negedge", log_signal(cache_clk
),
318 considered_ports
.count(i
) ? "considered" : "not considered");
320 log(" Port %d unclocked: %s\n", i
,
321 considered_ports
.count(i
) ? "considered" : "not considered");
324 if (considered_port_pairs
.size() < 1) {
325 log(" No two subsequent ports in same clock domain considered -> nothing to consolidate.\n");
329 // create SAT representation of common input cone of all considered EN signals
331 pool
<Wire
*> one_hot_wires
;
332 std::set
<RTLIL::Cell
*> sat_cells
;
333 std::set
<RTLIL::SigBit
> bits_queue
;
334 std::map
<int, int> port_to_sat_variable
;
336 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
337 if (considered_port_pairs
.count(i
) || considered_port_pairs
.count(i
+1))
339 RTLIL::SigSpec sig
= modwalker
.sigmap(mem
.wr_ports
[i
].en
);
340 port_to_sat_variable
[i
] = ez
->expression(ez
->OpOr
, satgen
.importSigSpec(sig
));
342 std::vector
<RTLIL::SigBit
> bits
= sig
;
343 bits_queue
.insert(bits
.begin(), bits
.end());
346 while (!bits_queue
.empty())
348 for (auto bit
: bits_queue
)
349 if (bit
.wire
&& bit
.wire
->get_bool_attribute(ID::onehot
))
350 one_hot_wires
.insert(bit
.wire
);
352 pool
<ModWalker::PortBit
> portbits
;
353 modwalker
.get_drivers(portbits
, bits_queue
);
356 for (auto &pbit
: portbits
)
357 if (sat_cells
.count(pbit
.cell
) == 0 && cone_ct
.cell_known(pbit
.cell
->type
)) {
358 pool
<RTLIL::SigBit
> &cell_inputs
= modwalker
.cell_inputs
[pbit
.cell
];
359 bits_queue
.insert(cell_inputs
.begin(), cell_inputs
.end());
360 sat_cells
.insert(pbit
.cell
);
364 for (auto wire
: one_hot_wires
) {
365 log(" Adding one-hot constraint for wire %s.\n", log_id(wire
));
366 vector
<int> ez_wire_bits
= satgen
.importSigSpec(wire
);
367 for (int i
: ez_wire_bits
)
368 for (int j
: ez_wire_bits
)
369 if (i
!= j
) ez
->assume(ez
->NOT(i
), j
);
372 log(" Common input cone for all EN signals: %d cells.\n", int(sat_cells
.size()));
374 for (auto cell
: sat_cells
)
375 satgen
.importCell(cell
);
377 log(" Size of unconstrained SAT problem: %d variables, %d clauses\n", ez
->numCnfVariables(), ez
->numCnfClauses());
379 // merge subsequent ports if possible
381 bool changed
= false;
382 for (int i
= 0; i
< GetSize(mem
.wr_ports
); i
++)
384 if (!considered_port_pairs
.count(i
))
387 if (ez
->solve(port_to_sat_variable
.at(i
-1), port_to_sat_variable
.at(i
))) {
388 log(" According to SAT solver sharing of port %d with port %d is not possible.\n", i
-1, i
);
392 log(" Merging port %d into port %d.\n", i
-1, i
);
393 port_to_sat_variable
.at(i
) = ez
->OR(port_to_sat_variable
.at(i
-1), port_to_sat_variable
.at(i
));
395 RTLIL::SigSpec last_addr
= mem
.wr_ports
[i
-1].addr
;
396 RTLIL::SigSpec last_data
= mem
.wr_ports
[i
-1].data
;
397 std::vector
<RTLIL::SigBit
> last_en
= modwalker
.sigmap(mem
.wr_ports
[i
-1].en
);
399 RTLIL::SigSpec this_addr
= mem
.wr_ports
[i
].addr
;
400 RTLIL::SigSpec this_data
= mem
.wr_ports
[i
].data
;
401 std::vector
<RTLIL::SigBit
> this_en
= modwalker
.sigmap(mem
.wr_ports
[i
].en
);
403 RTLIL::SigBit this_en_active
= module
->ReduceOr(NEW_ID
, this_en
);
405 if (GetSize(last_addr
) < GetSize(this_addr
))
406 last_addr
.extend_u0(GetSize(this_addr
));
408 this_addr
.extend_u0(GetSize(last_addr
));
410 mem
.wr_ports
[i
].addr
= module
->Mux(NEW_ID
, last_addr
, this_addr
, this_en_active
);
411 mem
.wr_ports
[i
].data
= module
->Mux(NEW_ID
, last_data
, this_data
, this_en_active
);
413 std::map
<std::pair
<RTLIL::SigBit
, RTLIL::SigBit
>, int> groups_en
;
414 RTLIL::SigSpec grouped_last_en
, grouped_this_en
, en
;
415 RTLIL::Wire
*grouped_en
= module
->addWire(NEW_ID
, 0);
417 for (int j
= 0; j
< int(this_en
.size()); j
++) {
418 std::pair
<RTLIL::SigBit
, RTLIL::SigBit
> key(last_en
[j
], this_en
[j
]);
419 if (!groups_en
.count(key
)) {
420 grouped_last_en
.append(last_en
[j
]);
421 grouped_this_en
.append(this_en
[j
]);
422 groups_en
[key
] = grouped_en
->width
;
425 en
.append(RTLIL::SigSpec(grouped_en
, groups_en
[key
]));
428 module
->addMux(NEW_ID
, grouped_last_en
, grouped_this_en
, this_en_active
, grouped_en
);
429 mem
.wr_ports
[i
].en
= en
;
431 mem
.wr_ports
[i
-1].removed
= true;
444 MemoryShareWorker(RTLIL::Design
*design
) : design(design
), modwalker(design
) {}
446 void operator()(RTLIL::Module
* module
)
448 std::vector
<Mem
> memories
= Mem::get_selected_memories(module
);
450 this->module
= module
;
453 sigmap_xmux
= sigmap
;
454 for (auto cell
: module
->cells())
456 if (cell
->type
== ID($mux
))
458 RTLIL::SigSpec sig_a
= sigmap_xmux(cell
->getPort(ID::A
));
459 RTLIL::SigSpec sig_b
= sigmap_xmux(cell
->getPort(ID::B
));
461 if (sig_a
.is_fully_undef())
462 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_b
);
463 else if (sig_b
.is_fully_undef())
464 sigmap_xmux
.add(cell
->getPort(ID::Y
), sig_a
);
468 for (auto &mem
: memories
)
469 consolidate_wr_by_addr(mem
);
471 cone_ct
.setup_internals();
472 cone_ct
.cell_types
.erase(ID($mul
));
473 cone_ct
.cell_types
.erase(ID($mod
));
474 cone_ct
.cell_types
.erase(ID($div
));
475 cone_ct
.cell_types
.erase(ID($modfloor
));
476 cone_ct
.cell_types
.erase(ID($divfloor
));
477 cone_ct
.cell_types
.erase(ID($pow
));
478 cone_ct
.cell_types
.erase(ID($shl
));
479 cone_ct
.cell_types
.erase(ID($shr
));
480 cone_ct
.cell_types
.erase(ID($sshl
));
481 cone_ct
.cell_types
.erase(ID($sshr
));
482 cone_ct
.cell_types
.erase(ID($shift
));
483 cone_ct
.cell_types
.erase(ID($shiftx
));
485 modwalker
.setup(module
, &cone_ct
);
487 for (auto &mem
: memories
)
488 consolidate_wr_using_sat(mem
);
492 struct MemorySharePass
: public Pass
{
493 MemorySharePass() : Pass("memory_share", "consolidate memory ports") { }
496 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
498 log(" memory_share [selection]\n");
500 log("This pass merges share-able memory ports into single memory ports.\n");
502 log("The following methods are used to consolidate the number of memory ports:\n");
504 log(" - When multiple write ports access the same address then this is converted\n");
505 log(" to a single write port with a more complex data and/or enable logic path.\n");
507 log(" - When multiple write ports are never accessed at the same time (a SAT\n");
508 log(" solver is used to determine this), then the ports are merged into a single\n");
509 log(" write port.\n");
511 log("Note that in addition to the algorithms implemented in this pass, the $memrd\n");
512 log("and $memwr cells are also subject to generic resource sharing passes (and other\n");
513 log("optimizations) such as \"share\" and \"opt_merge\".\n");
516 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) override
{
517 log_header(design
, "Executing MEMORY_SHARE pass (consolidating $memrd/$memwr cells).\n");
518 extra_args(args
, 1, design
);
519 MemoryShareWorker
msw(design
);
521 for (auto module
: design
->selected_modules())
526 PRIVATE_NAMESPACE_END