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