projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Add comment as per @cliffordwolf
[yosys.git] / passes / techmap / shregmap.cc
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/sigtools.h"
22
23 USING_YOSYS_NAMESPACE
24 PRIVATE_NAMESPACE_BEGIN
25
26 struct ShregmapTech
27 {
28 virtual ~ShregmapTech() { }
29 virtual bool analyze(vector<int> &taps) = 0;
30 virtual bool fixup(Cell *cell, dict<int, SigBit> &taps) = 0;
31 };
32
33 struct ShregmapOptions
34 {
35 int minlen, maxlen;
36 int keep_before, keep_after;
37 bool zinit, init, params, ffe;
38 dict<IdString, pair<IdString, IdString>> ffcells;
39 ShregmapTech *tech;
40
41 ShregmapOptions()
42 {
43 minlen = 2;
44 maxlen = 0;
45 keep_before = 0;
46 keep_after = 0;
47 zinit = false;
48 init = false;
49 params = false;
50 ffe = false;
51 tech = nullptr;
52 }
53 };
54
55 struct ShregmapTechGreenpak4 : ShregmapTech
56 {
57 bool analyze(vector<int> &taps)
58 {
59 if (GetSize(taps) > 2 && taps[0] == 0 && taps[2] < 17) {
60 taps.clear();
61 return true;
62 }
63
64 if (GetSize(taps) > 2)
65 return false;
66
67 if (taps.back() > 16) return false;
68
69 return true;
70 }
71
72 bool fixup(Cell *cell, dict<int, SigBit> &taps)
73 {
74 auto D = cell->getPort(ID(D));
75 auto C = cell->getPort(ID(C));
76
77 auto newcell = cell->module->addCell(NEW_ID, ID(GP_SHREG));
78 newcell->setPort(ID(nRST), State::S1);
79 newcell->setPort(ID(CLK), C);
80 newcell->setPort(ID(IN), D);
81
82 int i = 0;
83 for (auto tap : taps) {
84 newcell->setPort(i ? ID(OUTB) : ID(OUTA), tap.second);
85 newcell->setParam(i ? ID(OUTB_TAP) : ID(OUTA_TAP), tap.first + 1);
86 i++;
87 }
88
89 cell->setParam(ID(OUTA_INVERT), 0);
90 return false;
91 }
92 };
93
94 struct ShregmapWorker
95 {
96 Module *module;
97 SigMap sigmap;
98
99 const ShregmapOptions &opts;
100 int dff_count, shreg_count;
101
102 pool<Cell*> remove_cells;
103 pool<SigBit> remove_init;
104
105 dict<SigBit, bool> sigbit_init;
106 dict<SigBit, Cell*> sigbit_chain_next;
107 dict<SigBit, Cell*> sigbit_chain_prev;
108 pool<SigBit> sigbit_with_non_chain_users;
109 pool<Cell*> chain_start_cells;
110
111 void make_sigbit_chain_next_prev()
112 {
113 for (auto wire : module->wires())
114 {
115 if (wire->port_output || wire->get_bool_attribute(ID::keep)) {
116 for (auto bit : sigmap(wire))
117 sigbit_with_non_chain_users.insert(bit);
118 }
119
120 if (wire->attributes.count(ID(init))) {
121 SigSpec initsig = sigmap(wire);
122 Const initval = wire->attributes.at(ID(init));
123 for (int i = 0; i < GetSize(initsig) && i < GetSize(initval); i++)
124 if (initval[i] == State::S0 && !opts.zinit)
125 sigbit_init[initsig[i]] = false;
126 else if (initval[i] == State::S1)
127 sigbit_init[initsig[i]] = true;
128 }
129 }
130
131 for (auto cell : module->cells())
132 {
133 if (opts.ffcells.count(cell->type) && !cell->get_bool_attribute(ID::keep))
134 {
135 IdString d_port = opts.ffcells.at(cell->type).first;
136 IdString q_port = opts.ffcells.at(cell->type).second;
137
138 SigBit d_bit = sigmap(cell->getPort(d_port).as_bit());
139 SigBit q_bit = sigmap(cell->getPort(q_port).as_bit());
140
141 if (opts.init || sigbit_init.count(q_bit) == 0)
142 {
143 auto r = sigbit_chain_next.insert(std::make_pair(d_bit, cell));
144 if (!r.second) {
145 // Insertion not successful means that d_bit is already
146 // connected to another register, thus mark it as a
147 // non chain user ...
148 sigbit_with_non_chain_users.insert(d_bit);
149 // ... and clone d_bit into another wire, and use that
150 // wire as a different key in the d_bit-to-cell dictionary
151 // so that it can be identified as another chain
152 // (omitting this common flop)
153 // Link: https://github.com/YosysHQ/yosys/pull/1085
154 // NB: This relies on us not updating sigmap with this
155 // alias otherwise it would think they are the same
156 // wire
157 Wire *wire = module->addWire(NEW_ID);
158 module->connect(wire, d_bit);
159 sigbit_chain_next.insert(std::make_pair(wire, cell));
160 }
161
162 sigbit_chain_prev[q_bit] = cell;
163 continue;
164 }
165 }
166
167 for (auto conn : cell->connections())
168 if (cell->input(conn.first))
169 for (auto bit : sigmap(conn.second))
170 sigbit_with_non_chain_users.insert(bit);
171 }
172 }
173
174 void find_chain_start_cells()
175 {
176 for (auto it : sigbit_chain_next)
177 {
178 if (opts.tech == nullptr && sigbit_with_non_chain_users.count(it.first))
179 goto start_cell;
180
181 if (sigbit_chain_prev.count(it.first) != 0)
182 {
183 Cell *c1 = sigbit_chain_prev.at(it.first);
184 Cell *c2 = it.second;
185
186 if (c1->type != c2->type)
187 goto start_cell;
188
189 if (c1->parameters != c2->parameters)
190 goto start_cell;
191
192 IdString d_port = opts.ffcells.at(c1->type).first;
193 IdString q_port = opts.ffcells.at(c1->type).second;
194
195 auto c1_conn = c1->connections();
196 auto c2_conn = c1->connections();
197
198 c1_conn.erase(d_port);
199 c1_conn.erase(q_port);
200
201 c2_conn.erase(d_port);
202 c2_conn.erase(q_port);
203
204 if (c1_conn != c2_conn)
205 goto start_cell;
206
207 continue;
208 }
209
210 start_cell:
211 chain_start_cells.insert(it.second);
212 }
213 }
214
215 vector<Cell*> create_chain(Cell *start_cell)
216 {
217 vector<Cell*> chain;
218
219 Cell *c = start_cell;
220 while (c != nullptr)
221 {
222 chain.push_back(c);
223
224 IdString q_port = opts.ffcells.at(c->type).second;
225 SigBit q_bit = sigmap(c->getPort(q_port).as_bit());
226
227 if (sigbit_chain_next.count(q_bit) == 0)
228 break;
229
230 c = sigbit_chain_next.at(q_bit);
231 if (chain_start_cells.count(c) != 0)
232 break;
233 }
234
235 return chain;
236 }
237
238 void process_chain(vector<Cell*> &chain)
239 {
240 if (GetSize(chain) < opts.keep_before + opts.minlen + opts.keep_after)
241 return;
242
243 int cursor = opts.keep_before;
244 while (cursor < GetSize(chain) - opts.keep_after)
245 {
246 int depth = GetSize(chain) - opts.keep_after - cursor;
247
248 if (opts.maxlen > 0)
249 depth = std::min(opts.maxlen, depth);
250
251 Cell *first_cell = chain[cursor];
252 IdString q_port = opts.ffcells.at(first_cell->type).second;
253 dict<int, SigBit> taps_dict;
254
255 if (opts.tech)
256 {
257 vector<SigBit> qbits;
258 vector<int> taps;
259
260 for (int i = 0; i < depth; i++)
261 {
262 Cell *cell = chain[cursor+i];
263 auto qbit = sigmap(cell->getPort(q_port));
264 qbits.push_back(qbit);
265
266 if (sigbit_with_non_chain_users.count(qbit))
267 taps.push_back(i);
268 }
269
270 while (depth > 0)
271 {
272 if (taps.empty() || taps.back() < depth-1)
273 taps.push_back(depth-1);
274
275 if (opts.tech->analyze(taps))
276 break;
277
278 taps.pop_back();
279 depth--;
280 }
281
282 depth = 0;
283 for (auto tap : taps) {
284 taps_dict[tap] = qbits.at(tap);
285 log_assert(depth < tap+1);
286 depth = tap+1;
287 }
288 }
289
290 if (depth < 2) {
291 cursor++;
292 continue;
293 }
294
295 Cell *last_cell = chain[cursor+depth-1];
296
297 log("Converting %s.%s ... %s.%s to a shift register with depth %d.\n",
298 log_id(module), log_id(first_cell), log_id(module), log_id(last_cell), depth);
299
300 dff_count += depth;
301 shreg_count += 1;
302
303 string shreg_cell_type_str = "$__SHREG";
304 if (opts.params) {
305 shreg_cell_type_str += "_";
306 } else {
307 if (first_cell->type[1] != '_')
308 shreg_cell_type_str += "_";
309 shreg_cell_type_str += first_cell->type.substr(1);
310 }
311
312 if (opts.init) {
313 vector<State> initval;
314 for (int i = depth-1; i >= 0; i--) {
315 SigBit bit = sigmap(chain[cursor+i]->getPort(q_port).as_bit());
316 if (sigbit_init.count(bit) == 0)
317 initval.push_back(State::Sx);
318 else if (sigbit_init.at(bit))
319 initval.push_back(State::S1);
320 else
321 initval.push_back(State::S0);
322 remove_init.insert(bit);
323 }
324 first_cell->setParam(ID(INIT), initval);
325 }
326
327 if (opts.zinit)
328 for (int i = depth-1; i >= 0; i--) {
329 SigBit bit = sigmap(chain[cursor+i]->getPort(q_port).as_bit());
330 remove_init.insert(bit);
331 }
332
333 if (opts.params)
334 {
335 int param_clkpol = -1;
336 int param_enpol = 2;
337
338 if (first_cell->type == ID($_DFF_N_)) param_clkpol = 0;
339 if (first_cell->type == ID($_DFF_P_)) param_clkpol = 1;
340
341 if (first_cell->type == ID($_DFFE_NN_)) param_clkpol = 0, param_enpol = 0;
342 if (first_cell->type == ID($_DFFE_NP_)) param_clkpol = 0, param_enpol = 1;
343 if (first_cell->type == ID($_DFFE_PN_)) param_clkpol = 1, param_enpol = 0;
344 if (first_cell->type == ID($_DFFE_PP_)) param_clkpol = 1, param_enpol = 1;
345
346 log_assert(param_clkpol >= 0);
347 first_cell->setParam(ID(CLKPOL), param_clkpol);
348 if (opts.ffe) first_cell->setParam(ID(ENPOL), param_enpol);
349 }
350
351 first_cell->type = shreg_cell_type_str;
352 first_cell->setPort(q_port, last_cell->getPort(q_port));
353 first_cell->setParam(ID(DEPTH), depth);
354
355 if (opts.tech != nullptr && !opts.tech->fixup(first_cell, taps_dict))
356 remove_cells.insert(first_cell);
357
358 for (int i = 1; i < depth; i++)
359 remove_cells.insert(chain[cursor+i]);
360 cursor += depth;
361 }
362 }
363
364 void cleanup()
365 {
366 for (auto cell : remove_cells)
367 module->remove(cell);
368
369 for (auto wire : module->wires())
370 {
371 if (wire->attributes.count(ID(init)) == 0)
372 continue;
373
374 SigSpec initsig = sigmap(wire);
375 Const &initval = wire->attributes.at(ID(init));
376
377 for (int i = 0; i < GetSize(initsig) && i < GetSize(initval); i++)
378 if (remove_init.count(initsig[i]))
379 initval[i] = State::Sx;
380
381 if (SigSpec(initval).is_fully_undef())
382 wire->attributes.erase(ID(init));
383 }
384
385 remove_cells.clear();
386 sigbit_chain_next.clear();
387 sigbit_chain_prev.clear();
388 chain_start_cells.clear();
389 }
390
391 ShregmapWorker(Module *module, const ShregmapOptions &opts) :
392 module(module), sigmap(module), opts(opts), dff_count(0), shreg_count(0)
393 {
394 make_sigbit_chain_next_prev();
395 find_chain_start_cells();
396
397 for (auto c : chain_start_cells) {
398 vector<Cell*> chain = create_chain(c);
399 process_chain(chain);
400 }
401
402 cleanup();
403 }
404 };
405
406 struct ShregmapPass : public Pass {
407 ShregmapPass() : Pass("shregmap", "map shift registers") { }
408 void help() YS_OVERRIDE
409 {
410 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
411 log("\n");
412 log(" shregmap [options] [selection]\n");
413 log("\n");
414 log("This pass converts chains of $_DFF_[NP]_ gates to target specific shift register\n");
415 log("primitives. The generated shift register will be of type $__SHREG_DFF_[NP]_ and\n");
416 log("will use the same interface as the original $_DFF_*_ cells. The cell parameter\n");
417 log("'DEPTH' will contain the depth of the shift register. Use a target-specific\n");
418 log("'techmap' map file to convert those cells to the actual target cells.\n");
419 log("\n");
420 log(" -minlen N\n");
421 log(" minimum length of shift register (default = 2)\n");
422 log(" (this is the length after -keep_before and -keep_after)\n");
423 log("\n");
424 log(" -maxlen N\n");
425 log(" maximum length of shift register (default = no limit)\n");
426 log(" larger chains will be mapped to multiple shift register instances\n");
427 log("\n");
428 log(" -keep_before N\n");
429 log(" number of DFFs to keep before the shift register (default = 0)\n");
430 log("\n");
431 log(" -keep_after N\n");
432 log(" number of DFFs to keep after the shift register (default = 0)\n");
433 log("\n");
434 log(" -clkpol pos|neg|any\n");
435 log(" limit match to only positive or negative edge clocks. (default = any)\n");
436 log("\n");
437 log(" -enpol pos|neg|none|any_or_none|any\n");
438 log(" limit match to FFs with the specified enable polarity. (default = none)\n");
439 log("\n");
440 log(" -match <cell_type>[:<d_port_name>:<q_port_name>]\n");
441 log(" match the specified cells instead of $_DFF_N_ and $_DFF_P_. If\n");
442 log(" ':<d_port_name>:<q_port_name>' is omitted then 'D' and 'Q' is used\n");
443 log(" by default. E.g. the option '-clkpol pos' is just an alias for\n");
444 log(" '-match $_DFF_P_', which is an alias for '-match $_DFF_P_:D:Q'.\n");
445 log("\n");
446 log(" -params\n");
447 log(" instead of encoding the clock and enable polarity in the cell name by\n");
448 log(" deriving from the original cell name, simply name all generated cells\n");
449 log(" $__SHREG_ and use CLKPOL and ENPOL parameters. An ENPOL value of 2 is\n");
450 log(" used to denote cells without enable input. The ENPOL parameter is\n");
451 log(" omitted when '-enpol none' (or no -enpol option) is passed.\n");
452 log("\n");
453 log(" -zinit\n");
454 log(" assume the shift register is automatically zero-initialized, so it\n");
455 log(" becomes legal to merge zero initialized FFs into the shift register.\n");
456 log("\n");
457 log(" -init\n");
458 log(" map initialized registers to the shift reg, add an INIT parameter to\n");
459 log(" generated cells with the initialization value. (first bit to shift out\n");
460 log(" in LSB position)\n");
461 log("\n");
462 log(" -tech greenpak4\n");
463 log(" map to greenpak4 shift registers.\n");
464 log("\n");
465 }
466 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
467 {
468 ShregmapOptions opts;
469 string clkpol, enpol;
470
471 log_header(design, "Executing SHREGMAP pass (map shift registers).\n");
472
473 size_t argidx;
474 for (argidx = 1; argidx < args.size(); argidx++)
475 {
476 if (args[argidx] == "-clkpol" && argidx+1 < args.size()) {
477 clkpol = args[++argidx];
478 continue;
479 }
480 if (args[argidx] == "-enpol" && argidx+1 < args.size()) {
481 enpol = args[++argidx];
482 continue;
483 }
484 if (args[argidx] == "-match" && argidx+1 < args.size()) {
485 vector<string> match_args = split_tokens(args[++argidx], ":");
486 if (GetSize(match_args) < 2)
487 match_args.push_back("D");
488 if (GetSize(match_args) < 3)
489 match_args.push_back("Q");
490 IdString id_cell_type(RTLIL::escape_id(match_args[0]));
491 IdString id_d_port_name(RTLIL::escape_id(match_args[1]));
492 IdString id_q_port_name(RTLIL::escape_id(match_args[2]));
493 opts.ffcells[id_cell_type] = make_pair(id_d_port_name, id_q_port_name);
494 continue;
495 }
496 if (args[argidx] == "-minlen" && argidx+1 < args.size()) {
497 opts.minlen = atoi(args[++argidx].c_str());
498 continue;
499 }
500 if (args[argidx] == "-maxlen" && argidx+1 < args.size()) {
501 opts.maxlen = atoi(args[++argidx].c_str());
502 continue;
503 }
504 if (args[argidx] == "-keep_before" && argidx+1 < args.size()) {
505 opts.keep_before = atoi(args[++argidx].c_str());
506 continue;
507 }
508 if (args[argidx] == "-keep_after" && argidx+1 < args.size()) {
509 opts.keep_after = atoi(args[++argidx].c_str());
510 continue;
511 }
512 if (args[argidx] == "-tech" && argidx+1 < args.size() && opts.tech == nullptr) {
513 string tech = args[++argidx];
514 if (tech == "greenpak4") {
515 clkpol = "pos";
516 opts.zinit = true;
517 opts.tech = new ShregmapTechGreenpak4;
518 } else {
519 argidx--;
520 break;
521 }
522 continue;
523 }
524 if (args[argidx] == "-zinit") {
525 opts.zinit = true;
526 continue;
527 }
528 if (args[argidx] == "-init") {
529 opts.init = true;
530 continue;
531 }
532 if (args[argidx] == "-params") {
533 opts.params = true;
534 continue;
535 }
536 break;
537 }
538 extra_args(args, argidx, design);
539
540 if (opts.zinit && opts.init)
541 log_cmd_error("Options -zinit and -init are exclusive!\n");
542
543 if (opts.ffcells.empty())
544 {
545 bool clk_pos = clkpol == "" || clkpol == "pos" || clkpol == "any";
546 bool clk_neg = clkpol == "" || clkpol == "neg" || clkpol == "any";
547
548 bool en_none = enpol == "" || enpol == "none" || enpol == "any_or_none";
549 bool en_pos = enpol == "pos" || enpol == "any" || enpol == "any_or_none";
550 bool en_neg = enpol == "neg" || enpol == "any" || enpol == "any_or_none";
551
552 if (clk_pos && en_none)
553 opts.ffcells[ID($_DFF_P_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
554 if (clk_neg && en_none)
555 opts.ffcells[ID($_DFF_N_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
556
557 if (clk_pos && en_pos)
558 opts.ffcells[ID($_DFFE_PP_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
559 if (clk_pos && en_neg)
560 opts.ffcells[ID($_DFFE_PN_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
561
562 if (clk_neg && en_pos)
563 opts.ffcells[ID($_DFFE_NP_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
564 if (clk_neg && en_neg)
565 opts.ffcells[ID($_DFFE_NN_)] = make_pair(IdString(ID(D)), IdString(ID(Q)));
566
567 if (en_pos || en_neg)
568 opts.ffe = true;
569 }
570 else
571 {
572 if (!clkpol.empty())
573 log_cmd_error("Options -clkpol and -match are exclusive!\n");
574 if (!enpol.empty())
575 log_cmd_error("Options -enpol and -match are exclusive!\n");
576 if (opts.params)
577 log_cmd_error("Options -params and -match are exclusive!\n");
578 }
579
580 int dff_count = 0;
581 int shreg_count = 0;
582
583 for (auto module : design->selected_modules()) {
584 ShregmapWorker worker(module, opts);
585 dff_count += worker.dff_count;
586 shreg_count += worker.shreg_count;
587 }
588
589 log("Converted %d dff cells into %d shift registers.\n", dff_count, shreg_count);
590
591 if (opts.tech != nullptr) {
592 delete opts.tech;
593 opts.tech = nullptr;
594 }
595 }
596 } ShregmapPass;
597
598 PRIVATE_NAMESPACE_END