yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
memory_share.cc
Go to the documentation of this file.
1 /*
2  * yosys -- Yosys Open SYnthesis Suite
3  *
4  * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5  *
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.
9  *
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.
17  *
18  */
19 
20 #include "kernel/yosys.h"
21 #include "kernel/satgen.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/modtools.h"
24 
27 
29 {
30  if (a->type == "$memrd" && b->type == "$memrd")
31  return a->name < b->name;
32  if (a->type == "$memrd" || b->type == "$memrd")
33  return (a->type == "$memrd") < (b->type == "$memrd");
34  return a->parameters.at("\\PRIORITY").as_int() < b->parameters.at("\\PRIORITY").as_int();
35 }
36 
38 {
44 
45  std::map<RTLIL::SigBit, std::pair<RTLIL::Cell*, int>> sig_to_mux;
46  std::map<std::set<std::map<RTLIL::SigBit, bool>>, RTLIL::SigBit> conditions_logic_cache;
47 
48 
49  // -----------------------------------------------------------------
50  // Converting feedbacks to async read ports to proper enable signals
51  // -----------------------------------------------------------------
52 
53  bool find_data_feedback(const std::set<RTLIL::SigBit> &async_rd_bits, RTLIL::SigBit sig,
54  std::map<RTLIL::SigBit, bool> &state, std::set<std::map<RTLIL::SigBit, bool>> &conditions)
55  {
56  if (async_rd_bits.count(sig)) {
57  conditions.insert(state);
58  return true;
59  }
60 
61  if (sig_to_mux.count(sig) == 0)
62  return false;
63 
64  RTLIL::Cell *cell = sig_to_mux.at(sig).first;
65  int bit_idx = sig_to_mux.at(sig).second;
66 
67  std::vector<RTLIL::SigBit> sig_a = sigmap(cell->getPort("\\A"));
68  std::vector<RTLIL::SigBit> sig_b = sigmap(cell->getPort("\\B"));
69  std::vector<RTLIL::SigBit> sig_s = sigmap(cell->getPort("\\S"));
70  std::vector<RTLIL::SigBit> sig_y = sigmap(cell->getPort("\\Y"));
71  log_assert(sig_y.at(bit_idx) == sig);
72 
73  for (int i = 0; i < int(sig_s.size()); i++)
74  if (state.count(sig_s[i]) && state.at(sig_s[i]) == true) {
75  if (find_data_feedback(async_rd_bits, sig_b.at(bit_idx + i*sig_y.size()), state, conditions)) {
76  RTLIL::SigSpec new_b = cell->getPort("\\B");
77  new_b.replace(bit_idx + i*sig_y.size(), RTLIL::State::Sx);
78  cell->setPort("\\B", new_b);
79  }
80  return false;
81  }
82 
83 
84  for (int i = 0; i < int(sig_s.size()); i++)
85  {
86  if (state.count(sig_s[i]) && state.at(sig_s[i]) == false)
87  continue;
88 
89  std::map<RTLIL::SigBit, bool> new_state = state;
90  new_state[sig_s[i]] = true;
91 
92  if (find_data_feedback(async_rd_bits, sig_b.at(bit_idx + i*sig_y.size()), new_state, conditions)) {
93  RTLIL::SigSpec new_b = cell->getPort("\\B");
94  new_b.replace(bit_idx + i*sig_y.size(), RTLIL::State::Sx);
95  cell->setPort("\\B", new_b);
96  }
97  }
98 
99  std::map<RTLIL::SigBit, bool> new_state = state;
100  for (int i = 0; i < int(sig_s.size()); i++)
101  new_state[sig_s[i]] = false;
102 
103  if (find_data_feedback(async_rd_bits, sig_a.at(bit_idx), new_state, conditions)) {
104  RTLIL::SigSpec new_a = cell->getPort("\\A");
105  new_a.replace(bit_idx, RTLIL::State::Sx);
106  cell->setPort("\\A", new_a);
107  }
108 
109  return false;
110  }
111 
112  RTLIL::SigBit conditions_to_logic(std::set<std::map<RTLIL::SigBit, bool>> &conditions, int &created_conditions)
113  {
114  if (conditions_logic_cache.count(conditions))
115  return conditions_logic_cache.at(conditions);
116 
117  RTLIL::SigSpec terms;
118  for (auto &cond : conditions) {
119  RTLIL::SigSpec sig1, sig2;
120  for (auto &it : cond) {
121  sig1.append_bit(it.first);
122  sig2.append_bit(it.second ? RTLIL::State::S1 : RTLIL::State::S0);
123  }
124  terms.append(module->Ne(NEW_ID, sig1, sig2));
125  created_conditions++;
126  }
127 
128  if (terms.size() > 1)
129  terms = module->ReduceAnd(NEW_ID, terms);
130 
131  return conditions_logic_cache[conditions] = terms;
132  }
133 
134  void translate_rd_feedback_to_en(std::string memid, std::vector<RTLIL::Cell*> &rd_ports, std::vector<RTLIL::Cell*> &wr_ports)
135  {
136  std::map<RTLIL::SigSpec, std::vector<std::set<RTLIL::SigBit>>> async_rd_bits;
137  std::map<RTLIL::SigBit, std::set<RTLIL::SigBit>> muxtree_upstream_map;
138  std::set<RTLIL::SigBit> non_feedback_nets;
139 
140  for (auto wire_it : module->wires_)
141  if (wire_it.second->port_output) {
142  std::vector<RTLIL::SigBit> bits = RTLIL::SigSpec(wire_it.second);
143  non_feedback_nets.insert(bits.begin(), bits.end());
144  }
145 
146  for (auto cell_it : module->cells_)
147  {
148  RTLIL::Cell *cell = cell_it.second;
149  bool ignore_data_port = false;
150 
151  if (cell->type == "$mux" || cell->type == "$pmux")
152  {
153  std::vector<RTLIL::SigBit> sig_a = sigmap(cell->getPort("\\A"));
154  std::vector<RTLIL::SigBit> sig_b = sigmap(cell->getPort("\\B"));
155  std::vector<RTLIL::SigBit> sig_s = sigmap(cell->getPort("\\S"));
156  std::vector<RTLIL::SigBit> sig_y = sigmap(cell->getPort("\\Y"));
157 
158  non_feedback_nets.insert(sig_s.begin(), sig_s.end());
159 
160  for (int i = 0; i < int(sig_y.size()); i++) {
161  muxtree_upstream_map[sig_y[i]].insert(sig_a[i]);
162  for (int j = 0; j < int(sig_s.size()); j++)
163  muxtree_upstream_map[sig_y[i]].insert(sig_b[i + j*sig_y.size()]);
164  }
165 
166  continue;
167  }
168 
169  if ((cell->type == "$memwr" || cell->type == "$memrd") &&
170  cell->parameters.at("\\MEMID").decode_string() == memid)
171  ignore_data_port = true;
172 
173  for (auto conn : cell_it.second->connections())
174  {
175  if (ignore_data_port && conn.first == "\\DATA")
176  continue;
177  std::vector<RTLIL::SigBit> bits = sigmap(conn.second);
178  non_feedback_nets.insert(bits.begin(), bits.end());
179  }
180  }
181 
182  std::set<RTLIL::SigBit> expand_non_feedback_nets = non_feedback_nets;
183  while (!expand_non_feedback_nets.empty())
184  {
185  std::set<RTLIL::SigBit> new_expand_non_feedback_nets;
186 
187  for (auto &bit : expand_non_feedback_nets)
188  if (muxtree_upstream_map.count(bit))
189  for (auto &new_bit : muxtree_upstream_map.at(bit))
190  if (!non_feedback_nets.count(new_bit)) {
191  non_feedback_nets.insert(new_bit);
192  new_expand_non_feedback_nets.insert(new_bit);
193  }
194 
195  expand_non_feedback_nets.swap(new_expand_non_feedback_nets);
196  }
197 
198  for (auto cell : rd_ports)
199  {
200  if (cell->parameters.at("\\CLK_ENABLE").as_bool())
201  continue;
202 
203  RTLIL::SigSpec sig_addr = sigmap(cell->getPort("\\ADDR"));
204  std::vector<RTLIL::SigBit> sig_data = sigmap(cell->getPort("\\DATA"));
205 
206  for (int i = 0; i < int(sig_data.size()); i++)
207  if (non_feedback_nets.count(sig_data[i]))
208  goto not_pure_feedback_port;
209 
210  async_rd_bits[sig_addr].resize(std::max(async_rd_bits.size(), sig_data.size()));
211  for (int i = 0; i < int(sig_data.size()); i++)
212  async_rd_bits[sig_addr][i].insert(sig_data[i]);
213 
214  not_pure_feedback_port:;
215  }
216 
217  if (async_rd_bits.empty())
218  return;
219 
220  log("Populating enable bits on write ports of memory %s.%s with aync read feedback:\n", log_id(module), log_id(memid));
221 
222  for (auto cell : wr_ports)
223  {
224  RTLIL::SigSpec sig_addr = sigmap_xmux(cell->getPort("\\ADDR"));
225  if (!async_rd_bits.count(sig_addr))
226  continue;
227 
228  log(" Analyzing write port %s.\n", log_id(cell));
229 
230  std::vector<RTLIL::SigBit> cell_data = cell->getPort("\\DATA");
231  std::vector<RTLIL::SigBit> cell_en = cell->getPort("\\EN");
232 
233  int created_conditions = 0;
234  for (int i = 0; i < int(cell_data.size()); i++)
235  if (cell_en[i] != RTLIL::SigBit(RTLIL::State::S0))
236  {
237  std::map<RTLIL::SigBit, bool> state;
238  std::set<std::map<RTLIL::SigBit, bool>> conditions;
239 
240  if (cell_en[i].wire != NULL) {
241  state[cell_en[i]] = false;
242  conditions.insert(state);
243  }
244 
245  find_data_feedback(async_rd_bits.at(sig_addr).at(i), cell_data[i], state, conditions);
246  cell_en[i] = conditions_to_logic(conditions, created_conditions);
247  }
248 
249  if (created_conditions) {
250  log(" Added enable logic for %d different cases.\n", created_conditions);
251  cell->setPort("\\EN", cell_en);
252  }
253  }
254  }
255 
256 
257  // ------------------------------------------------------
258  // Consolidate write ports that write to the same address
259  // ------------------------------------------------------
260 
262  {
263  // this is the naive version of the function that does not care about grouping the EN bits.
264 
265  RTLIL::SigSpec inv_mask_bits = module->Not(NEW_ID, mask_bits);
266  RTLIL::SigSpec inv_mask_bits_filtered = module->Mux(NEW_ID, RTLIL::SigSpec(RTLIL::State::S1, bits.size()), inv_mask_bits, do_mask);
267  RTLIL::SigSpec result = module->And(NEW_ID, inv_mask_bits_filtered, bits);
268  return result;
269  }
270 
272  {
273  // this version of the function preserves the bit grouping in the EN bits.
274 
275  std::vector<RTLIL::SigBit> v_bits = bits;
276  std::vector<RTLIL::SigBit> v_mask_bits = mask_bits;
277 
278  std::map<std::pair<RTLIL::SigBit, RTLIL::SigBit>, std::pair<int, std::vector<int>>> groups;
279  RTLIL::SigSpec grouped_bits, grouped_mask_bits;
280 
281  for (int i = 0; i < bits.size(); i++) {
282  std::pair<RTLIL::SigBit, RTLIL::SigBit> key(v_bits[i], v_mask_bits[i]);
283  if (groups.count(key) == 0) {
284  groups[key].first = grouped_bits.size();
285  grouped_bits.append_bit(v_bits[i]);
286  grouped_mask_bits.append_bit(v_mask_bits[i]);
287  }
288  groups[key].second.push_back(i);
289  }
290 
291  std::vector<RTLIL::SigBit> grouped_result = mask_en_naive(do_mask, grouped_bits, grouped_mask_bits);
292  RTLIL::SigSpec result;
293 
294  for (int i = 0; i < bits.size(); i++) {
295  std::pair<RTLIL::SigBit, RTLIL::SigBit> key(v_bits[i], v_mask_bits[i]);
296  result.append_bit(grouped_result.at(groups.at(key).first));
297  }
298 
299  return result;
300  }
301 
302  void merge_en_data(RTLIL::SigSpec &merged_en, RTLIL::SigSpec &merged_data, RTLIL::SigSpec next_en, RTLIL::SigSpec next_data)
303  {
304  std::vector<RTLIL::SigBit> v_old_en = merged_en;
305  std::vector<RTLIL::SigBit> v_next_en = next_en;
306 
307  // The new merged_en signal is just the old merged_en signal and next_en OR'ed together.
308  // But of course we need to preserve the bit grouping..
309 
310  std::map<std::pair<RTLIL::SigBit, RTLIL::SigBit>, int> groups;
311  std::vector<RTLIL::SigBit> grouped_old_en, grouped_next_en;
312  RTLIL::SigSpec new_merged_en;
313 
314  for (int i = 0; i < int(v_old_en.size()); i++) {
315  std::pair<RTLIL::SigBit, RTLIL::SigBit> key(v_old_en[i], v_next_en[i]);
316  if (groups.count(key) == 0) {
317  groups[key] = grouped_old_en.size();
318  grouped_old_en.push_back(key.first);
319  grouped_next_en.push_back(key.second);
320  }
321  }
322 
323  std::vector<RTLIL::SigBit> grouped_new_en = module->Or(NEW_ID, grouped_old_en, grouped_next_en);
324 
325  for (int i = 0; i < int(v_old_en.size()); i++) {
326  std::pair<RTLIL::SigBit, RTLIL::SigBit> key(v_old_en[i], v_next_en[i]);
327  new_merged_en.append_bit(grouped_new_en.at(groups.at(key)));
328  }
329 
330  // Create the new merged_data signal.
331 
332  RTLIL::SigSpec new_merged_data(RTLIL::State::Sx, merged_data.size());
333 
334  RTLIL::SigSpec old_data_set = module->And(NEW_ID, merged_en, merged_data);
335  RTLIL::SigSpec old_data_unset = module->And(NEW_ID, merged_en, module->Not(NEW_ID, merged_data));
336 
337  RTLIL::SigSpec new_data_set = module->And(NEW_ID, next_en, next_data);
338  RTLIL::SigSpec new_data_unset = module->And(NEW_ID, next_en, module->Not(NEW_ID, next_data));
339 
340  new_merged_data = module->Or(NEW_ID, new_merged_data, old_data_set);
341  new_merged_data = module->And(NEW_ID, new_merged_data, module->Not(NEW_ID, old_data_unset));
342 
343  new_merged_data = module->Or(NEW_ID, new_merged_data, new_data_set);
344  new_merged_data = module->And(NEW_ID, new_merged_data, module->Not(NEW_ID, new_data_unset));
345 
346  // Update merged_* signals
347 
348  merged_en = new_merged_en;
349  merged_data = new_merged_data;
350  }
351 
352  void consolidate_wr_by_addr(std::string memid, std::vector<RTLIL::Cell*> &wr_ports)
353  {
354  if (wr_ports.size() <= 1)
355  return;
356 
357  log("Consolidating write ports of memory %s.%s by address:\n", log_id(module), log_id(memid));
358 
359  std::map<RTLIL::SigSpec, int> last_port_by_addr;
360  std::vector<std::vector<bool>> active_bits_on_port;
361 
362  bool cache_clk_enable = false;
363  bool cache_clk_polarity = false;
364  RTLIL::SigSpec cache_clk;
365 
366  for (int i = 0; i < int(wr_ports.size()); i++)
367  {
368  RTLIL::Cell *cell = wr_ports.at(i);
369  RTLIL::SigSpec addr = sigmap_xmux(cell->getPort("\\ADDR"));
370 
371  if (cell->parameters.at("\\CLK_ENABLE").as_bool() != cache_clk_enable ||
372  (cache_clk_enable && (sigmap(cell->getPort("\\CLK")) != cache_clk ||
373  cell->parameters.at("\\CLK_POLARITY").as_bool() != cache_clk_polarity)))
374  {
375  cache_clk_enable = cell->parameters.at("\\CLK_ENABLE").as_bool();
376  cache_clk_polarity = cell->parameters.at("\\CLK_POLARITY").as_bool();
377  cache_clk = sigmap(cell->getPort("\\CLK"));
378  last_port_by_addr.clear();
379 
380  if (cache_clk_enable)
381  log(" New clock domain: %s %s\n", cache_clk_polarity ? "posedge" : "negedge", log_signal(cache_clk));
382  else
383  log(" New clock domain: unclocked\n");
384  }
385 
386  log(" Port %d (%s) has addr %s.\n", i, log_id(cell), log_signal(addr));
387 
388  log(" Active bits: ");
389  std::vector<RTLIL::SigBit> en_bits = sigmap(cell->getPort("\\EN"));
390  active_bits_on_port.push_back(std::vector<bool>(en_bits.size()));
391  for (int k = int(en_bits.size())-1; k >= 0; k--) {
392  active_bits_on_port[i][k] = en_bits[k].wire != NULL || en_bits[k].data != RTLIL::State::S0;
393  log("%c", active_bits_on_port[i][k] ? '1' : '0');
394  }
395  log("\n");
396 
397  if (last_port_by_addr.count(addr))
398  {
399  int last_i = last_port_by_addr.at(addr);
400  log(" Merging port %d into this one.\n", last_i);
401 
402  bool found_overlapping_bits = false;
403  for (int k = 0; k < int(en_bits.size()); k++) {
404  if (active_bits_on_port[i][k] && active_bits_on_port[last_i][k])
405  found_overlapping_bits = true;
406  active_bits_on_port[i][k] = active_bits_on_port[i][k] || active_bits_on_port[last_i][k];
407  }
408 
409  // Force this ports addr input to addr directly (skip don't care muxes)
410 
411  cell->setPort("\\ADDR", addr);
412 
413  // If any of the ports between `last_i' and `i' write to the same address, this
414  // will have priority over whatever `last_i` wrote. So we need to revisit those
415  // ports and mask the EN bits accordingly.
416 
417  RTLIL::SigSpec merged_en = sigmap(wr_ports[last_i]->getPort("\\EN"));
418 
419  for (int j = last_i+1; j < i; j++)
420  {
421  if (wr_ports[j] == NULL)
422  continue;
423 
424  for (int k = 0; k < int(en_bits.size()); k++)
425  if (active_bits_on_port[i][k] && active_bits_on_port[j][k])
426  goto found_overlapping_bits_i_j;
427 
428  if (0) {
429  found_overlapping_bits_i_j:
430  log(" Creating collosion-detect logic for port %d.\n", j);
431  RTLIL::SigSpec is_same_addr = module->addWire(NEW_ID);
432  module->addEq(NEW_ID, addr, wr_ports[j]->getPort("\\ADDR"), is_same_addr);
433  merged_en = mask_en_grouped(is_same_addr, merged_en, sigmap(wr_ports[j]->getPort("\\EN")));
434  }
435  }
436 
437  // Then we need to merge the (masked) EN and the DATA signals.
438 
439  RTLIL::SigSpec merged_data = wr_ports[last_i]->getPort("\\DATA");
440  if (found_overlapping_bits) {
441  log(" Creating logic for merging DATA and EN ports.\n");
442  merge_en_data(merged_en, merged_data, sigmap(cell->getPort("\\EN")), sigmap(cell->getPort("\\DATA")));
443  } else {
444  RTLIL::SigSpec cell_en = sigmap(cell->getPort("\\EN"));
445  RTLIL::SigSpec cell_data = sigmap(cell->getPort("\\DATA"));
446  for (int k = 0; k < int(en_bits.size()); k++)
447  if (!active_bits_on_port[last_i][k]) {
448  merged_en.replace(k, cell_en.extract(k, 1));
449  merged_data.replace(k, cell_data.extract(k, 1));
450  }
451  }
452 
453  // Connect the new EN and DATA signals and remove the old write port.
454 
455  cell->setPort("\\EN", merged_en);
456  cell->setPort("\\DATA", merged_data);
457 
458  module->remove(wr_ports[last_i]);
459  wr_ports[last_i] = NULL;
460 
461  log(" Active bits: ");
462  std::vector<RTLIL::SigBit> en_bits = sigmap(cell->getPort("\\EN"));
463  active_bits_on_port.push_back(std::vector<bool>(en_bits.size()));
464  for (int k = int(en_bits.size())-1; k >= 0; k--)
465  log("%c", active_bits_on_port[i][k] ? '1' : '0');
466  log("\n");
467  }
468 
469  last_port_by_addr[addr] = i;
470  }
471 
472  // Clean up `wr_ports': remove all NULL entries
473 
474  std::vector<RTLIL::Cell*> wr_ports_with_nulls;
475  wr_ports_with_nulls.swap(wr_ports);
476 
477  for (auto cell : wr_ports_with_nulls)
478  if (cell != NULL)
479  wr_ports.push_back(cell);
480  }
481 
482 
483  // --------------------------------------------------------
484  // Consolidate write ports using sat-based resource sharing
485  // --------------------------------------------------------
486 
487  void consolidate_wr_using_sat(std::string memid, std::vector<RTLIL::Cell*> &wr_ports)
488  {
489  if (wr_ports.size() <= 1)
490  return;
491 
493  SatGen satgen(&ez, &modwalker.sigmap);
494 
495  // find list of considered ports and port pairs
496 
497  std::set<int> considered_ports;
498  std::set<int> considered_port_pairs;
499 
500  for (int i = 0; i < int(wr_ports.size()); i++) {
501  std::vector<RTLIL::SigBit> bits = modwalker.sigmap(wr_ports[i]->getPort("\\EN"));
502  for (auto bit : bits)
503  if (bit == RTLIL::State::S1)
504  goto port_is_always_active;
505  if (modwalker.has_drivers(bits))
506  considered_ports.insert(i);
507  port_is_always_active:;
508  }
509 
510  log("Consolidating write ports of memory %s.%s using sat-based resource sharing:\n", log_id(module), log_id(memid));
511 
512  bool cache_clk_enable = false;
513  bool cache_clk_polarity = false;
514  RTLIL::SigSpec cache_clk;
515 
516  for (int i = 0; i < int(wr_ports.size()); i++)
517  {
518  RTLIL::Cell *cell = wr_ports.at(i);
519 
520  if (cell->parameters.at("\\CLK_ENABLE").as_bool() != cache_clk_enable ||
521  (cache_clk_enable && (sigmap(cell->getPort("\\CLK")) != cache_clk ||
522  cell->parameters.at("\\CLK_POLARITY").as_bool() != cache_clk_polarity)))
523  {
524  cache_clk_enable = cell->parameters.at("\\CLK_ENABLE").as_bool();
525  cache_clk_polarity = cell->parameters.at("\\CLK_POLARITY").as_bool();
526  cache_clk = sigmap(cell->getPort("\\CLK"));
527  }
528  else if (i > 0 && considered_ports.count(i-1) && considered_ports.count(i))
529  considered_port_pairs.insert(i);
530 
531  if (cache_clk_enable)
532  log(" Port %d (%s) on %s %s: %s\n", i, log_id(cell),
533  cache_clk_polarity ? "posedge" : "negedge", log_signal(cache_clk),
534  considered_ports.count(i) ? "considered" : "not considered");
535  else
536  log(" Port %d (%s) unclocked: %s\n", i, log_id(cell),
537  considered_ports.count(i) ? "considered" : "not considered");
538  }
539 
540  if (considered_port_pairs.size() < 1) {
541  log(" No two subsequent ports in same clock domain considered -> nothing to consolidate.\n");
542  return;
543  }
544 
545  // create SAT representation of common input cone of all considered EN signals
546 
547  std::set<RTLIL::Cell*> sat_cells;
548  std::set<RTLIL::SigBit> bits_queue;
549  std::map<int, int> port_to_sat_variable;
550 
551  for (int i = 0; i < int(wr_ports.size()); i++)
552  if (considered_port_pairs.count(i) || considered_port_pairs.count(i+1))
553  {
554  RTLIL::SigSpec sig = modwalker.sigmap(wr_ports[i]->getPort("\\EN"));
555  port_to_sat_variable[i] = ez.expression(ez.OpOr, satgen.importSigSpec(sig));
556 
557  std::vector<RTLIL::SigBit> bits = sig;
558  bits_queue.insert(bits.begin(), bits.end());
559  }
560 
561  while (!bits_queue.empty())
562  {
563  std::set<ModWalker::PortBit> portbits;
564  modwalker.get_drivers(portbits, bits_queue);
565  bits_queue.clear();
566 
567  for (auto &pbit : portbits)
568  if (sat_cells.count(pbit.cell) == 0 && cone_ct.cell_known(pbit.cell->type)) {
569  std::set<RTLIL::SigBit> &cell_inputs = modwalker.cell_inputs[pbit.cell];
570  bits_queue.insert(cell_inputs.begin(), cell_inputs.end());
571  sat_cells.insert(pbit.cell);
572  }
573  }
574 
575  log(" Common input cone for all EN signals: %d cells.\n", int(sat_cells.size()));
576 
577  for (auto cell : sat_cells)
578  satgen.importCell(cell);
579 
580  log(" Size of unconstrained SAT problem: %d variables, %d clauses\n", ez.numCnfVariables(), ez.numCnfClauses());
581 
582  // merge subsequent ports if possible
583 
584  for (int i = 0; i < int(wr_ports.size()); i++)
585  {
586  if (!considered_port_pairs.count(i))
587  continue;
588 
589  if (ez.solve(port_to_sat_variable.at(i-1), port_to_sat_variable.at(i))) {
590  log(" According to SAT solver sharing of port %d with port %d is not possible.\n", i-1, i);
591  continue;
592  }
593 
594  log(" Merging port %d into port %d.\n", i-1, i);
595  port_to_sat_variable.at(i) = ez.OR(port_to_sat_variable.at(i-1), port_to_sat_variable.at(i));
596 
597  RTLIL::SigSpec last_addr = wr_ports[i-1]->getPort("\\ADDR");
598  RTLIL::SigSpec last_data = wr_ports[i-1]->getPort("\\DATA");
599  std::vector<RTLIL::SigBit> last_en = modwalker.sigmap(wr_ports[i-1]->getPort("\\EN"));
600 
601  RTLIL::SigSpec this_addr = wr_ports[i]->getPort("\\ADDR");
602  RTLIL::SigSpec this_data = wr_ports[i]->getPort("\\DATA");
603  std::vector<RTLIL::SigBit> this_en = modwalker.sigmap(wr_ports[i]->getPort("\\EN"));
604 
605  RTLIL::SigBit this_en_active = module->ReduceOr(NEW_ID, this_en);
606 
607  wr_ports[i]->setPort("\\ADDR", module->Mux(NEW_ID, last_addr, this_addr, this_en_active));
608  wr_ports[i]->setPort("\\DATA", module->Mux(NEW_ID, last_data, this_data, this_en_active));
609 
610  std::map<std::pair<RTLIL::SigBit, RTLIL::SigBit>, int> groups_en;
611  RTLIL::SigSpec grouped_last_en, grouped_this_en, en;
612  RTLIL::Wire *grouped_en = module->addWire(NEW_ID, 0);
613 
614  for (int j = 0; j < int(this_en.size()); j++) {
615  std::pair<RTLIL::SigBit, RTLIL::SigBit> key(last_en[j], this_en[j]);
616  if (!groups_en.count(key)) {
617  grouped_last_en.append_bit(last_en[j]);
618  grouped_this_en.append_bit(this_en[j]);
619  groups_en[key] = grouped_en->width;
620  grouped_en->width++;
621  }
622  en.append(RTLIL::SigSpec(grouped_en, groups_en[key]));
623  }
624 
625  module->addMux(NEW_ID, grouped_last_en, grouped_this_en, this_en_active, grouped_en);
626  wr_ports[i]->setPort("\\EN", en);
627 
628  module->remove(wr_ports[i-1]);
629  wr_ports[i-1] = NULL;
630  }
631 
632  // Clean up `wr_ports': remove all NULL entries
633 
634  std::vector<RTLIL::Cell*> wr_ports_with_nulls;
635  wr_ports_with_nulls.swap(wr_ports);
636 
637  for (auto cell : wr_ports_with_nulls)
638  if (cell != NULL)
639  wr_ports.push_back(cell);
640  }
641 
642 
643  // -------------
644  // Setup and run
645  // -------------
646 
648  design(design), module(module), sigmap(module)
649  {
650  std::map<std::string, std::pair<std::vector<RTLIL::Cell*>, std::vector<RTLIL::Cell*>>> memindex;
651 
653  for (auto &it : module->cells_)
654  {
655  RTLIL::Cell *cell = it.second;
656 
657  if (cell->type == "$memrd")
658  memindex[cell->parameters.at("\\MEMID").decode_string()].first.push_back(cell);
659 
660  if (cell->type == "$memwr")
661  memindex[cell->parameters.at("\\MEMID").decode_string()].second.push_back(cell);
662 
663  if (cell->type == "$mux")
664  {
665  RTLIL::SigSpec sig_a = sigmap_xmux(cell->getPort("\\A"));
666  RTLIL::SigSpec sig_b = sigmap_xmux(cell->getPort("\\B"));
667 
668  if (sig_a.is_fully_undef())
669  sigmap_xmux.add(cell->getPort("\\Y"), sig_b);
670  else if (sig_b.is_fully_undef())
671  sigmap_xmux.add(cell->getPort("\\Y"), sig_a);
672  }
673 
674  if (cell->type == "$mux" || cell->type == "$pmux")
675  {
676  std::vector<RTLIL::SigBit> sig_y = sigmap(cell->getPort("\\Y"));
677  for (int i = 0; i < int(sig_y.size()); i++)
678  sig_to_mux[sig_y[i]] = std::pair<RTLIL::Cell*, int>(cell, i);
679  }
680  }
681 
682  for (auto &it : memindex) {
683  std::sort(it.second.first.begin(), it.second.first.end(), memcells_cmp);
684  std::sort(it.second.second.begin(), it.second.second.end(), memcells_cmp);
685  translate_rd_feedback_to_en(it.first, it.second.first, it.second.second);
686  consolidate_wr_by_addr(it.first, it.second.second);
687  }
688 
690  cone_ct.cell_types.erase("$mul");
691  cone_ct.cell_types.erase("$mod");
692  cone_ct.cell_types.erase("$div");
693  cone_ct.cell_types.erase("$pow");
694  cone_ct.cell_types.erase("$shl");
695  cone_ct.cell_types.erase("$shr");
696  cone_ct.cell_types.erase("$sshl");
697  cone_ct.cell_types.erase("$sshr");
698  cone_ct.cell_types.erase("$shift");
699  cone_ct.cell_types.erase("$shiftx");
700 
701  modwalker.setup(design, module, &cone_ct);
702 
703  for (auto &it : memindex)
704  consolidate_wr_using_sat(it.first, it.second.second);
705  }
706 };
707 
708 struct MemorySharePass : public Pass {
709  MemorySharePass() : Pass("memory_share", "consolidate memory ports") { }
710  virtual void help()
711  {
712  // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
713  log("\n");
714  log(" memory_share [selection]\n");
715  log("\n");
716  log("This pass merges share-able memory ports into single memory ports.\n");
717  log("\n");
718  log("The following methods are used to consolidate the number of memory ports:\n");
719  log("\n");
720  log(" - When write ports are connected to async read ports accessing the same\n");
721  log(" address, then this feedback path is converted to a write port with\n");
722  log(" byte/part enable signals.\n");
723  log("\n");
724  log(" - When multiple write ports access the same address then this is converted\n");
725  log(" to a single write port with a more complex data and/or enable logic path.\n");
726  log("\n");
727  log(" - When multiple write ports are never accessed at the same time (a SAT\n");
728  log(" solver is used to determine this), then the ports are merged into a single\n");
729  log(" write port.\n");
730  log("\n");
731  log("Note that in addition to the algorithms implemented in this pass, the $memrd\n");
732  log("and $memwr cells are also subject to generic resource sharing passes (and other\n");
733  log("optimizations) such as opt_share.\n");
734  log("\n");
735  }
736  virtual void execute(std::vector<std::string> args, RTLIL::Design *design) {
737  log_header("Executing MEMORY_SHARE pass (consolidating $memrc/$memwr cells).\n");
738  extra_args(args, 1, design);
739  for (auto module : design->selected_modules())
740  MemoryShareWorker(design, module);
741  }
743 
USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN bool memcells_cmp(RTLIL::Cell *a, RTLIL::Cell *b)
Definition: memory_share.cc:28
void translate_rd_feedback_to_en(std::string memid, std::vector< RTLIL::Cell * > &rd_ports, std::vector< RTLIL::Cell * > &wr_ports)
bool is_fully_undef() const
Definition: rtlil.cc:2789
virtual void execute(std::vector< std::string > args, RTLIL::Design *design)
void sort(T *array, int size, LessThan lt)
Definition: Sort.h:57
RTLIL::SigSpec Ne(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, bool is_signed=false)
void consolidate_wr_using_sat(std::string memid, std::vector< RTLIL::Cell * > &wr_ports)
void log_header(const char *format,...)
Definition: log.cc:188
bool has_drivers(const T &sig) const
Definition: modtools.h:407
SigMap sigmap
Definition: modtools.h:202
RTLIL::SigSpec mask_en_naive(RTLIL::SigSpec do_mask, RTLIL::SigSpec bits, RTLIL::SigSpec mask_bits)
std::map< RTLIL::IdString, RTLIL::Wire * > wires_
Definition: rtlil.h:595
const char * log_signal(const RTLIL::SigSpec &sig, bool autoint)
Definition: log.cc:269
ezMiniSAT ez
Definition: puzzle3d.cc:31
void clear()
Definition: sigtools.h:263
RTLIL::IdString name
Definition: rtlil.h:853
void setPort(RTLIL::IdString portname, RTLIL::SigSpec signal)
Definition: rtlil.cc:1789
RTLIL::SigSpec Mux(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, RTLIL::SigSpec sig_s)
int width
Definition: rtlil.h:826
RTLIL::Cell * addEq(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, RTLIL::SigSpec sig_y, bool is_signed=false)
std::vector< int > importSigSpec(RTLIL::SigSpec sig, int timestep=-1)
Definition: satgen.h:78
RTLIL::Module * module
Definition: abc.cc:94
RTLIL::IdString type
Definition: rtlil.h:854
std::map< RTLIL::IdString, RTLIL::Const > parameters
Definition: rtlil.h:856
int size() const
Definition: rtlil.h:1019
bool get_drivers(std::set< PortBit > &result, RTLIL::SigBit bit) const
Definition: modtools.h:289
MemorySharePass MemorySharePass
RTLIL::SigSpec Or(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, bool is_signed=false)
bool find_data_feedback(const std::set< RTLIL::SigBit > &async_rd_bits, RTLIL::SigBit sig, std::map< RTLIL::SigBit, bool > &state, std::set< std::map< RTLIL::SigBit, bool >> &conditions)
Definition: memory_share.cc:53
MemoryShareWorker(RTLIL::Design *design, RTLIL::Module *module)
YOSYS_NAMESPACE_BEGIN typedef ezMiniSAT ezDefaultSAT
Definition: satgen.h:32
std::map< RTLIL::IdString, CellType > cell_types
Definition: celltypes.h:36
virtual void help()
bool cell_known(RTLIL::IdString type)
Definition: celltypes.h:188
void append_bit(const RTLIL::SigBit &bit)
Definition: rtlil.cc:2562
#define PRIVATE_NAMESPACE_BEGIN
Definition: yosys.h:97
const RTLIL::SigSpec & getPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1809
#define log_assert(_assert_expr_)
Definition: log.h:85
RTLIL::Wire * addWire(RTLIL::IdString name, int width=1)
Definition: rtlil.cc:1331
#define NEW_ID
Definition: yosys.h:166
ModWalker modwalker
Definition: memory_share.cc:42
std::map< RTLIL::Cell *, std::set< RTLIL::SigBit > > cell_inputs
Definition: modtools.h:208
#define PRIVATE_NAMESPACE_END
Definition: yosys.h:98
Definition: satgen.h:34
Definition: register.h:27
void consolidate_wr_by_addr(std::string memid, std::vector< RTLIL::Cell * > &wr_ports)
#define USING_YOSYS_NAMESPACE
Definition: yosys.h:102
RTLIL::Design * design
Definition: memory_share.cc:39
void replace(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec &with)
Definition: rtlil.cc:2297
void setup(RTLIL::Design *design, RTLIL::Module *module, CellTypes *filter_ct=NULL)
Definition: modtools.h:265
#define NULL
std::map< RTLIL::IdString, RTLIL::Cell * > cells_
Definition: rtlil.h:596
void remove(const std::set< RTLIL::Wire * > &wires)
Definition: rtlil.cc:1158
RTLIL::SigSpec ReduceOr(RTLIL::IdString name, RTLIL::SigSpec sig_a, bool is_signed=false)
RTLIL::Cell * addMux(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, RTLIL::SigSpec sig_s, RTLIL::SigSpec sig_y)
void log(const char *format,...)
Definition: log.cc:180
void setup_internals()
Definition: celltypes.h:83
RTLIL::SigSpec mask_en_grouped(RTLIL::SigSpec do_mask, RTLIL::SigSpec bits, RTLIL::SigSpec mask_bits)
bool importCell(RTLIL::Cell *cell, int timestep=-1)
Definition: satgen.h:203
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
RTLIL::SigSpec And(RTLIL::IdString name, RTLIL::SigSpec sig_a, RTLIL::SigSpec sig_b, bool is_signed=false)
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
std::vector< RTLIL::Module * > selected_modules() const
Definition: rtlil.cc:416
void add(RTLIL::SigSpec from, RTLIL::SigSpec to)
Definition: sigtools.h:347
std::map< RTLIL::SigBit, std::pair< RTLIL::Cell *, int > > sig_to_mux
Definition: memory_share.cc:45
void merge_en_data(RTLIL::SigSpec &merged_en, RTLIL::SigSpec &merged_data, RTLIL::SigSpec next_en, RTLIL::SigSpec next_data)
void extra_args(std::vector< std::string > args, size_t argidx, RTLIL::Design *design, bool select=true)
Definition: register.cc:128
RTLIL::Module * module
Definition: memory_share.cc:40
RTLIL::SigBit conditions_to_logic(std::set< std::map< RTLIL::SigBit, bool >> &conditions, int &created_conditions)
RTLIL::SigSpec Not(RTLIL::IdString name, RTLIL::SigSpec sig_a, bool is_signed=false)
const char * log_id(RTLIL::IdString str)
Definition: log.cc:283
RTLIL::SigSpec ReduceAnd(RTLIL::IdString name, RTLIL::SigSpec sig_a, bool is_signed=false)
std::map< std::set< std::map< RTLIL::SigBit, bool > >, RTLIL::SigBit > conditions_logic_cache
Definition: memory_share.cc:46