Merge pull request #2 from cliffordwolf/master
[yosys.git] / passes / techmap / dfflibmap.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/register.h"
21 #include "kernel/log.h"
22 #include "libparse.h"
23 #include <string.h>
24
25 using namespace PASS_DFFLIBMAP;
26
27 struct cell_mapping {
28 std::string cell_name;
29 std::map<std::string, char> ports;
30 };
31 static std::map<std::string, cell_mapping> cell_mappings;
32
33 static void logmap(std::string dff)
34 {
35 if (cell_mappings.count(dff) == 0) {
36 log(" unmapped dff cell: %s\n", dff.c_str());
37 } else {
38 log(" %s %s (", cell_mappings[dff].cell_name.c_str(), dff.substr(1).c_str());
39 bool first = true;
40 for (auto &port : cell_mappings[dff].ports) {
41 char arg[3] = { port.second, 0, 0 };
42 if ('a' <= arg[0] && arg[0] <= 'z')
43 arg[1] = arg[0] - ('a' - 'A'), arg[0] = '~';
44 else
45 arg[1] = arg[0], arg[0] = ' ';
46 log("%s.%s(%s)", first ? "" : ", ", port.first.c_str(), arg);
47 first = false;
48 }
49 log(");\n");
50 }
51 }
52
53 static void logmap_all()
54 {
55 logmap("$_DFF_N_");
56 logmap("$_DFF_P_");
57
58 logmap("$_DFF_NN0_");
59 logmap("$_DFF_NN1_");
60 logmap("$_DFF_NP0_");
61 logmap("$_DFF_NP1_");
62 logmap("$_DFF_PN0_");
63 logmap("$_DFF_PN1_");
64 logmap("$_DFF_PP0_");
65 logmap("$_DFF_PP1_");
66
67 logmap("$_DFFSR_NNN_");
68 logmap("$_DFFSR_NNP_");
69 logmap("$_DFFSR_NPN_");
70 logmap("$_DFFSR_NPP_");
71 logmap("$_DFFSR_PNN_");
72 logmap("$_DFFSR_PNP_");
73 logmap("$_DFFSR_PPN_");
74 logmap("$_DFFSR_PPP_");
75 }
76
77 static bool parse_pin(LibertyAst *cell, LibertyAst *attr, std::string &pin_name, bool &pin_pol)
78 {
79 if (cell == NULL || attr == NULL || attr->value.empty())
80 return false;
81
82 std::string value = attr->value;
83
84 for (size_t pos = value.find_first_of("\" \t()"); pos != std::string::npos; pos = value.find_first_of("\" \t()"))
85 value.erase(pos, 1);
86
87 if (value[value.size()-1] == '\'') {
88 pin_name = value.substr(0, value.size()-1);
89 pin_pol = false;
90 } else if (value[0] == '!') {
91 pin_name = value.substr(1, value.size()-1);
92 pin_pol = false;
93 } else {
94 pin_name = value;
95 pin_pol = true;
96 }
97
98 for (auto child : cell->children)
99 if (child->id == "pin" && child->args.size() == 1 && child->args[0] == pin_name)
100 return true;
101 return false;
102 }
103
104 static void find_cell(LibertyAst *ast, std::string cell_type, bool clkpol, bool has_reset, bool rstpol, bool rstval)
105 {
106 LibertyAst *best_cell = NULL;
107 std::map<std::string, char> best_cell_ports;
108 int best_cell_pins = 0;
109 float best_cell_area = 0;
110
111 if (ast->id != "library")
112 log_error("Format error in liberty file.\n");
113
114 for (auto cell : ast->children)
115 {
116 if (cell->id != "cell" || cell->args.size() != 1)
117 continue;
118
119 LibertyAst *ff = cell->find("ff");
120 if (ff == NULL)
121 continue;
122
123 std::string cell_clk_pin, cell_rst_pin, cell_next_pin;
124 bool cell_clk_pol, cell_rst_pol, cell_next_pol;
125
126 if (!parse_pin(cell, ff->find("clocked_on"), cell_clk_pin, cell_clk_pol) || cell_clk_pol != clkpol)
127 continue;
128 if (!parse_pin(cell, ff->find("next_state"), cell_next_pin, cell_next_pol))
129 continue;
130 if (has_reset && rstval == false) {
131 if (!parse_pin(cell, ff->find("clear"), cell_rst_pin, cell_rst_pol) || cell_rst_pol != rstpol)
132 continue;
133 }
134 if (has_reset && rstval == true) {
135 if (!parse_pin(cell, ff->find("preset"), cell_rst_pin, cell_rst_pol) || cell_rst_pol != rstpol)
136 continue;
137 }
138
139 std::map<std::string, char> this_cell_ports;
140 this_cell_ports[cell_clk_pin] = 'C';
141 if (has_reset)
142 this_cell_ports[cell_rst_pin] = 'R';
143 this_cell_ports[cell_next_pin] = 'D';
144
145 float area = 0;
146 LibertyAst *ar = cell->find("area");
147 if (ar != NULL && !ar->value.empty())
148 area = atof(ar->value.c_str());
149
150 int num_pins = 0;
151 bool found_output = false;
152 for (auto pin : cell->children)
153 {
154 if (pin->id != "pin" || pin->args.size() != 1)
155 continue;
156
157 LibertyAst *dir = pin->find("direction");
158 if (dir == NULL || dir->value == "internal")
159 continue;
160 num_pins++;
161
162 if (dir->value == "input" && this_cell_ports.count(pin->args[0]) == 0)
163 goto continue_cell_loop;
164
165 LibertyAst *func = pin->find("function");
166 if (dir->value == "output" && func != NULL) {
167 std::string value = func->value;
168 for (size_t pos = value.find_first_of("\" \t"); pos != std::string::npos; pos = value.find_first_of("\" \t"))
169 value.erase(pos, 1);
170 if ((cell_next_pol == true && value == ff->args[0]) || (cell_next_pol == false && value == ff->args[1])) {
171 this_cell_ports[pin->args[0]] = 'Q';
172 found_output = true;
173 }
174 }
175
176 if (this_cell_ports.count(pin->args[0]) == 0)
177 this_cell_ports[pin->args[0]] = 0;
178 }
179
180 if (!found_output || (best_cell != NULL && num_pins > best_cell_pins))
181 continue;
182
183 if (best_cell != NULL && num_pins == best_cell_pins && area > best_cell_area)
184 continue;
185
186 best_cell = cell;
187 best_cell_pins = num_pins;
188 best_cell_area = area;
189 best_cell_ports.swap(this_cell_ports);
190 continue_cell_loop:;
191 }
192
193 if (best_cell != NULL) {
194 log(" cell %s (pins=%d, area=%.2f) is a direct match for cell type %s.\n", best_cell->args[0].c_str(), best_cell_pins, best_cell_area, cell_type.substr(1).c_str());
195 cell_mappings[cell_type].cell_name = best_cell->args[0];
196 cell_mappings[cell_type].ports = best_cell_ports;
197 }
198 }
199
200 static void find_cell_sr(LibertyAst *ast, std::string cell_type, bool clkpol, bool setpol, bool clrpol)
201 {
202 LibertyAst *best_cell = NULL;
203 std::map<std::string, char> best_cell_ports;
204 int best_cell_pins = 0;
205 float best_cell_area = 0;
206
207 if (ast->id != "library")
208 log_error("Format error in liberty file.\n");
209
210 for (auto cell : ast->children)
211 {
212 if (cell->id != "cell" || cell->args.size() != 1)
213 continue;
214
215 LibertyAst *ff = cell->find("ff");
216 if (ff == NULL)
217 continue;
218
219 std::string cell_clk_pin, cell_set_pin, cell_clr_pin, cell_next_pin;
220 bool cell_clk_pol, cell_set_pol, cell_clr_pol, cell_next_pol;
221
222 if (!parse_pin(cell, ff->find("clocked_on"), cell_clk_pin, cell_clk_pol) || cell_clk_pol != clkpol)
223 continue;
224 if (!parse_pin(cell, ff->find("next_state"), cell_next_pin, cell_next_pol))
225 continue;
226 if (!parse_pin(cell, ff->find("preset"), cell_set_pin, cell_set_pol) || cell_set_pol != setpol)
227 continue;
228 if (!parse_pin(cell, ff->find("clear"), cell_clr_pin, cell_clr_pol) || cell_clr_pol != clrpol)
229 continue;
230
231 std::map<std::string, char> this_cell_ports;
232 this_cell_ports[cell_clk_pin] = 'C';
233 this_cell_ports[cell_set_pin] = 'S';
234 this_cell_ports[cell_clr_pin] = 'R';
235 this_cell_ports[cell_next_pin] = 'D';
236
237 float area = 0;
238 LibertyAst *ar = cell->find("area");
239 if (ar != NULL && !ar->value.empty())
240 area = atof(ar->value.c_str());
241
242 int num_pins = 0;
243 bool found_output = false;
244 for (auto pin : cell->children)
245 {
246 if (pin->id != "pin" || pin->args.size() != 1)
247 continue;
248
249 LibertyAst *dir = pin->find("direction");
250 if (dir == NULL || dir->value == "internal")
251 continue;
252 num_pins++;
253
254 if (dir->value == "input" && this_cell_ports.count(pin->args[0]) == 0)
255 goto continue_cell_loop;
256
257 LibertyAst *func = pin->find("function");
258 if (dir->value == "output" && func != NULL) {
259 std::string value = func->value;
260 for (size_t pos = value.find_first_of("\" \t"); pos != std::string::npos; pos = value.find_first_of("\" \t"))
261 value.erase(pos, 1);
262 if ((cell_next_pol == true && value == ff->args[0]) || (cell_next_pol == false && value == ff->args[1])) {
263 this_cell_ports[pin->args[0]] = 'Q';
264 found_output = true;
265 }
266 }
267
268 if (this_cell_ports.count(pin->args[0]) == 0)
269 this_cell_ports[pin->args[0]] = 0;
270 }
271
272 if (!found_output || (best_cell != NULL && num_pins > best_cell_pins))
273 continue;
274
275 if (best_cell != NULL && num_pins == best_cell_pins && area > best_cell_area)
276 continue;
277
278 best_cell = cell;
279 best_cell_pins = num_pins;
280 best_cell_area = area;
281 best_cell_ports.swap(this_cell_ports);
282 continue_cell_loop:;
283 }
284
285 if (best_cell != NULL) {
286 log(" cell %s (pins=%d, area=%.2f) is a direct match for cell type %s.\n", best_cell->args[0].c_str(), best_cell_pins, best_cell_area, cell_type.substr(1).c_str());
287 cell_mappings[cell_type].cell_name = best_cell->args[0];
288 cell_mappings[cell_type].ports = best_cell_ports;
289 }
290 }
291
292 static bool expand_cellmap_worker(std::string from, std::string to, std::string inv)
293 {
294 if (cell_mappings.count(to) > 0)
295 return false;
296
297 log(" create mapping for %s from mapping for %s.\n", to.c_str(), from.c_str());
298 cell_mappings[to].cell_name = cell_mappings[from].cell_name;
299 cell_mappings[to].ports = cell_mappings[from].ports;
300
301 for (auto &it : cell_mappings[to].ports) {
302 char cmp_ch = it.second;
303 if ('a' <= cmp_ch && cmp_ch <= 'z')
304 cmp_ch -= 'a' - 'A';
305 if (inv.find(cmp_ch) == std::string::npos)
306 continue;
307 if ('a' <= it.second && it.second <= 'z')
308 it.second -= 'a' - 'A';
309 else if ('A' <= it.second && it.second <= 'Z')
310 it.second += 'a' - 'A';
311 }
312 return true;
313 }
314
315 static bool expand_cellmap(std::string pattern, std::string inv)
316 {
317 std::vector<std::pair<std::string, std::string>> from_to_list;
318 bool return_status = false;
319
320 for (auto &it : cell_mappings) {
321 std::string from = it.first, to = it.first;
322 if (from.size() != pattern.size())
323 continue;
324 for (size_t i = 0; i < from.size(); i++) {
325 if (pattern[i] == '*') {
326 to[i] = from[i] == 'P' ? 'N' :
327 from[i] == 'N' ? 'P' :
328 from[i] == '1' ? '0' :
329 from[i] == '0' ? '1' : '*';
330 } else
331 if (pattern[i] != '?' && pattern[i] != from[i])
332 goto pattern_failed;
333 }
334 from_to_list.push_back(std::pair<std::string, std::string>(from, to));
335 pattern_failed:;
336 }
337
338 for (auto &it : from_to_list)
339 return_status = return_status || expand_cellmap_worker(it.first, it.second, inv);
340 return return_status;
341 }
342
343 static void map_sr_to_arst(const char *from, const char *to)
344 {
345 if (cell_mappings.count(to) > 0)
346 return;
347
348 char from_clk_pol = from[8], from_set_pol = from[9], from_clr_pol = from[10];
349 char to_clk_pol = to[6], to_rst_pol = to[7], to_rst_val = to[8];
350
351 log_assert(from_clk_pol == to_clk_pol);
352 log_assert(to_rst_pol == from_set_pol && to_rst_pol == from_clr_pol);
353
354 log(" create mapping for %s from mapping for %s.\n", to, from);
355 cell_mappings[to].cell_name = cell_mappings[from].cell_name;
356 cell_mappings[to].ports = cell_mappings[from].ports;
357
358 for (auto &it : cell_mappings[to].ports)
359 {
360 bool is_set_pin = it.second == 'S' || it.second == 's';
361 bool is_clr_pin = it.second == 'R' || it.second == 'r';
362
363 if (!is_set_pin && !is_clr_pin)
364 continue;
365
366 if ((to_rst_val == '0' && is_set_pin) || (to_rst_val == '1' && is_clr_pin))
367 {
368 // this is the unused set/clr pin -- deactivate it
369 if (is_set_pin)
370 it.second = (from_set_pol == 'P') == (it.second == 'S') ? '0' : '1';
371 else
372 it.second = (from_clr_pol == 'P') == (it.second == 'R') ? '0' : '1';
373 }
374 else
375 {
376 // this is the used set/clr pin -- rename it to 'reset'
377 if (it.second == 'S')
378 it.second = 'R';
379 if (it.second == 's')
380 it.second = 'r';
381 }
382 }
383 }
384
385 static void dfflibmap(RTLIL::Design *design, RTLIL::Module *module)
386 {
387 log("Mapping DFF cells in module `%s':\n", module->name.c_str());
388
389 std::vector<RTLIL::Cell*> cell_list;
390 for (auto &it : module->cells) {
391 if (design->selected(module, it.second) && cell_mappings.count(it.second->type) > 0)
392 cell_list.push_back(it.second);
393 }
394
395 std::map<std::string, int> stats;
396 for (auto cell : cell_list) {
397 cell_mapping &cm = cell_mappings[cell->type];
398 RTLIL::Cell *new_cell = new RTLIL::Cell;
399 new_cell->name = cell->name;
400 new_cell->type = "\\" + cm.cell_name;
401 for (auto &port : cm.ports) {
402 RTLIL::SigSpec sig;
403 if ('A' <= port.second && port.second <= 'Z') {
404 sig = cell->connections[std::string("\\") + port.second];
405 } else
406 if ('a' <= port.second && port.second <= 'z') {
407 sig = cell->connections[std::string("\\") + char(port.second - ('a' - 'A'))];
408 RTLIL::Cell *inv_cell = new RTLIL::Cell;
409 RTLIL::Wire *inv_wire = new RTLIL::Wire;
410 inv_cell->name = stringf("$dfflibmap$inv$%d", RTLIL::autoidx);
411 inv_wire->name = stringf("$dfflibmap$sig$%d", RTLIL::autoidx++);
412 inv_cell->type = "$_INV_";
413 inv_cell->connections[port.second == 'q' ? "\\Y" : "\\A"] = sig;
414 sig = RTLIL::SigSpec(inv_wire);
415 inv_cell->connections[port.second == 'q' ? "\\A" : "\\Y"] = sig;
416 module->cells[inv_cell->name] = inv_cell;
417 module->wires[inv_wire->name] = inv_wire;
418 } else
419 if (port.second == '0' || port.second == '1') {
420 sig = RTLIL::SigSpec(port.second == '0' ? 0 : 1, 1);
421 } else
422 if (port.second != 0)
423 log_abort();
424 new_cell->connections["\\" + port.first] = sig;
425 }
426 stats[stringf(" mapped %%d %s cells to %s cells.\n", cell->type.c_str(), new_cell->type.c_str())]++;
427 module->cells[cell->name] = new_cell;
428 delete cell;
429 }
430
431 for (auto &stat: stats)
432 log(stat.first.c_str(), stat.second);
433 }
434
435 struct DfflibmapPass : public Pass {
436 DfflibmapPass() : Pass("dfflibmap", "technology mapping of flip-flops") { }
437 virtual void help()
438 {
439 log("\n");
440 log(" dfflibmap -liberty <file> [selection]\n");
441 log("\n");
442 log("Map internal flip-flop cells to the flip-flop cells in the technology\n");
443 log("library specified in the given liberty file.\n");
444 log("\n");
445 log("This pass may add inverters as needed. Therefore it is recommended to\n");
446 log("first run this pass and then map the logic paths to the target technology.\n");
447 log("\n");
448 }
449 virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
450 {
451 log_header("Executing DFFLIBMAP pass (mapping DFF cells to sequential cells from liberty file).\n");
452
453 std::string liberty_file;
454
455 size_t argidx;
456 for (argidx = 1; argidx < args.size(); argidx++)
457 {
458 std::string arg = args[argidx];
459 if (arg == "-liberty" && argidx+1 < args.size()) {
460 liberty_file = args[++argidx];
461 continue;
462 }
463 break;
464 }
465 extra_args(args, argidx, design);
466
467 if (liberty_file.empty())
468 log_cmd_error("Missing `-liberty liberty_file' option!\n");
469
470 FILE *f = fopen(liberty_file.c_str(), "r");
471 if (f == NULL)
472 log_cmd_error("Can't open liberty file `%s': %s\n", liberty_file.c_str(), strerror(errno));
473 LibertyParser libparser(f);
474 fclose(f);
475
476 find_cell(libparser.ast, "$_DFF_N_", false, false, false, false);
477 find_cell(libparser.ast, "$_DFF_P_", true, false, false, false);
478
479 find_cell(libparser.ast, "$_DFF_NN0_", false, true, false, false);
480 find_cell(libparser.ast, "$_DFF_NN1_", false, true, false, true);
481 find_cell(libparser.ast, "$_DFF_NP0_", false, true, true, false);
482 find_cell(libparser.ast, "$_DFF_NP1_", false, true, true, true);
483 find_cell(libparser.ast, "$_DFF_PN0_", true, true, false, false);
484 find_cell(libparser.ast, "$_DFF_PN1_", true, true, false, true);
485 find_cell(libparser.ast, "$_DFF_PP0_", true, true, true, false);
486 find_cell(libparser.ast, "$_DFF_PP1_", true, true, true, true);
487
488 find_cell_sr(libparser.ast, "$_DFFSR_NNN_", false, false, false);
489 find_cell_sr(libparser.ast, "$_DFFSR_NNP_", false, false, true);
490 find_cell_sr(libparser.ast, "$_DFFSR_NPN_", false, true, false);
491 find_cell_sr(libparser.ast, "$_DFFSR_NPP_", false, true, true);
492 find_cell_sr(libparser.ast, "$_DFFSR_PNN_", true, false, false);
493 find_cell_sr(libparser.ast, "$_DFFSR_PNP_", true, false, true);
494 find_cell_sr(libparser.ast, "$_DFFSR_PPN_", true, true, false);
495 find_cell_sr(libparser.ast, "$_DFFSR_PPP_", true, true, true);
496
497 // try to implement as many cells as possible just by inverting
498 // the SET and RESET pins. If necessary, implement cell types
499 // by inverting both D and Q. Only invert clock pins if there
500 // is no other way of implementing the cell.
501 while (1)
502 {
503 if (expand_cellmap("$_DFF_?*?_", "R") ||
504 expand_cellmap("$_DFFSR_?*?_", "S") ||
505 expand_cellmap("$_DFFSR_??*_", "R"))
506 continue;
507
508 if (expand_cellmap("$_DFF_??*_", "DQ"))
509 continue;
510
511 if (expand_cellmap("$_DFF_*_", "C") ||
512 expand_cellmap("$_DFF_*??_", "C") ||
513 expand_cellmap("$_DFFSR_*??_", "C"))
514 continue;
515
516 break;
517 }
518
519 map_sr_to_arst("$_DFFSR_NNN_", "$_DFF_NN0_");
520 map_sr_to_arst("$_DFFSR_NNN_", "$_DFF_NN1_");
521 map_sr_to_arst("$_DFFSR_NPP_", "$_DFF_NP0_");
522 map_sr_to_arst("$_DFFSR_NPP_", "$_DFF_NP1_");
523 map_sr_to_arst("$_DFFSR_PNN_", "$_DFF_PN0_");
524 map_sr_to_arst("$_DFFSR_PNN_", "$_DFF_PN1_");
525 map_sr_to_arst("$_DFFSR_PPP_", "$_DFF_PP0_");
526 map_sr_to_arst("$_DFFSR_PPP_", "$_DFF_PP1_");
527
528 log(" final dff cell mappings:\n");
529 logmap_all();
530
531 for (auto &it : design->modules)
532 if (design->selected(it.second) && !it.second->get_bool_attribute("\\blackbox"))
533 dfflibmap(design, it.second);
534
535 cell_mappings.clear();
536 }
537 } DfflibmapPass;
538