passes/cmds/bugpoint.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2018  whitequark <whitequark@whitequark.org>
   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 "backends/ilang/ilang_backend.h"
  22
  23 USING_YOSYS_NAMESPACE
  24 using namespace ILANG_BACKEND;
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct BugpointPass : public Pass {
  28         BugpointPass() : Pass("bugpoint", "minimize testcases") { }
  29         void help() YS_OVERRIDE
  30         {
  31                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
  32                 log("\n");
  33                 log("    bugpoint [options] -script <filename>\n");
  34                 log("\n");
  35                 log("This command minimizes the current design that is known to crash Yosys with the\n");
  36                 log("given script into a smaller testcase. It does this by removing an arbitrary part\n");
  37                 log("of the design and recursively invokes a new Yosys process with this modified design\n");
  38                 log("and the same script, repeating these steps while it can find a smaller design that\n");
  39                 log("still causes a crash. Once this command finishes, it replaces the current design\n");
  40                 log("with the smallest testcase it was able to produce.\n");
  41                 log("\n");
  42                 log("    -script <filename>\n");
  43                 log("        use this script to crash Yosys. required.\n");
  44                 log("\n");
  45                 log("    -yosys <filename>\n");
  46                 log("        use this Yosys binary. if not specified, `yosys` is used.\n");
  47                 log("\n");
  48                 log("    -grep <string>\n");
  49                 log("        only consider crashes that place this string in the log file.\n");
  50                 log("\n");
  51                 log("    -fast\n");
  52                 log("        run `proc_clean; clean -purge` after each minimization step. converges\n");
  53                 log("        faster, but produces larger testcases, and may fail to produce any\n");
  54                 log("        testcase at all if the crash is related to dangling wires.\n");
  55                 log("\n");
  56                 log("    -clean\n");
  57                 log("        run `proc_clean; clean -purge` before checking testcase and after\n");
  58                 log("        finishing. produces smaller and more useful testcases, but may fail to\n");
  59                 log("        produce any testcase at all if the crash is related to dangling wires.\n");
  60                 log("\n");
  61                 log("It is possible to constrain which parts of the design will be considered for\n");
  62                 log("removal. Unless one or more of the following options are specified, all parts\n");
  63                 log("will be considered.\n");
  64                 log("\n");
  65                 log("    -modules\n");
  66                 log("        try to remove modules. modules with a (* bugpoint_keep *) attribute\n");
  67                 log("        will be skipped.\n");
  68                 log("\n");
  69                 log("    -ports\n");
  70                 log("        try to remove module ports. ports with a (* bugpoint_keep *) attribute\n");
  71                 log("        will be skipped (useful for clocks, resets, etc.)\n");
  72                 log("\n");
  73                 log("    -cells\n");
  74                 log("        try to remove cells. cells with a (* bugpoint_keep *) attribute will\n");
  75                 log("        be skipped.\n");
  76                 log("\n");
  77                 log("    -connections\n");
  78                 log("        try to reconnect ports to 'x.\n");
  79                 log("\n");
  80                 log("    -assigns\n");
  81                 log("        try to remove process assigns from cases.\n");
  82                 log("\n");
  83                 log("    -updates\n");
  84                 log("        try to remove process updates from syncs.\n");
  85                 log("\n");
  86         }
  87
  88         bool run_yosys(RTLIL::Design *design, string yosys_cmd, string script)
  89         {
  90                 design->sort();
  91
  92                 std::ofstream f("bugpoint-case.il");
  93                 ILANG_BACKEND::dump_design(f, design, /*only_selected=*/false, /*flag_m=*/true, /*flag_n=*/false);
  94                 f.close();
  95
  96                 string yosys_cmdline = stringf("%s -qq -L bugpoint-case.log -s %s bugpoint-case.il", yosys_cmd.c_str(), script.c_str());
  97                 return run_command(yosys_cmdline) == 0;
  98         }
  99
 100         bool check_logfile(string grep)
 101         {
 102                 if (grep.empty())
 103                         return true;
 104
 105                 std::ifstream f("bugpoint-case.log");
 106                 while (!f.eof())
 107                 {
 108                         string line;
 109                         getline(f, line);
 110                         if (line.find(grep) != std::string::npos)
 111                                 return true;
 112                 }
 113                 return false;
 114         }
 115
 116         RTLIL::Design *clean_design(RTLIL::Design *design, bool do_clean = true, bool do_delete = false)
 117         {
 118                 if (!do_clean)
 119                         return design;
 120
 121                 RTLIL::Design *design_copy = new RTLIL::Design;
 122                 for (auto module : design->modules())
 123                         design_copy->add(module->clone());
 124                 Pass::call(design_copy, "proc_clean -quiet");
 125                 Pass::call(design_copy, "clean -purge");
 126
 127                 if (do_delete)
 128                         delete design;
 129                 return design_copy;
 130         }
 131
 132         RTLIL::Design *simplify_something(RTLIL::Design *design, int &seed, bool stage2, bool modules, bool ports, bool cells, bool connections, bool assigns, bool updates)
 133         {
 134                 RTLIL::Design *design_copy = new RTLIL::Design;
 135                 for (auto module : design->modules())
 136                         design_copy->add(module->clone());
 137
 138                 int index = 0;
 139                 if (modules)
 140                 {
 141                         Module *removed_module = nullptr;
 142                         for (auto module : design_copy->modules())
 143                         {
 144                                 if (module->get_blackbox_attribute())
 145                                         continue;
 146
 147                                 if (module->get_bool_attribute(ID::bugpoint_keep))
 148                                     continue;
 149
 150                                 if (index++ == seed)
 151                                 {
 152                                         log_header(design, "Trying to remove module %s.\n", log_id(module));
 153                                         removed_module = module;
 154                                         break;
 155                                 }
 156                         }
 157                         if (removed_module) {
 158                                 design_copy->remove(removed_module);
 159                                 return design_copy;
 160                         }
 161                 }
 162                 if (ports)
 163                 {
 164                         for (auto mod : design_copy->modules())
 165                         {
 166                                 if (mod->get_blackbox_attribute())
 167                                         continue;
 168
 169                                 for (auto wire : mod->wires())
 170                                 {
 171                                         if (!wire->port_id)
 172                                                 continue;
 173
 174                                         if (!stage2 && wire->get_bool_attribute(ID($bugpoint)))
 175                                                 continue;
 176
 177                                         if (wire->get_bool_attribute(ID::bugpoint_keep))
 178                                                 continue;
 179
 180                                         if (index++ == seed)
 181                                         {
 182                                                 log_header(design, "Trying to remove module port %s.\n", log_id(wire));
 183                                                 wire->port_input = wire->port_output = false;
 184                                                 mod->fixup_ports();
 185                                                 return design_copy;
 186                                         }
 187                                 }
 188                         }
 189                 }
 190                 if (cells)
 191                 {
 192                         for (auto mod : design_copy->modules())
 193                         {
 194                                 if (mod->get_blackbox_attribute())
 195                                         continue;
 196
 197
 198                                 Cell *removed_cell = nullptr;
 199                                 for (auto cell : mod->cells())
 200                                 {
 201                                         if (cell->get_bool_attribute(ID::bugpoint_keep))
 202                                                 continue;
 203
 204                                         if (index++ == seed)
 205                                         {
 206                                                 log_header(design, "Trying to remove cell %s.%s.\n", log_id(mod), log_id(cell));
 207                                                 removed_cell = cell;
 208                                                 break;
 209                                         }
 210                                 }
 211                                 if (removed_cell) {
 212                                         mod->remove(removed_cell);
 213                                         return design_copy;
 214                                 }
 215                         }
 216                 }
 217                 if (connections)
 218                 {
 219                         for (auto mod : design_copy->modules())
 220                         {
 221                                 if (mod->get_blackbox_attribute())
 222                                         continue;
 223
 224                                 for (auto cell : mod->cells())
 225                                 {
 226                                         for (auto it : cell->connections_)
 227                                         {
 228                                                 RTLIL::SigSpec port = cell->getPort(it.first);
 229                                                 bool is_undef = port.is_fully_undef();
 230                                                 bool is_port = port.is_wire() && (port.as_wire()->port_input || port.as_wire()->port_output);
 231
 232                                                 if(is_undef || (!stage2 && is_port))
 233                                                         continue;
 234
 235                                                 if (index++ == seed)
 236                                                 {
 237                                                         log_header(design, "Trying to remove cell port %s.%s.%s.\n", log_id(mod), log_id(cell), log_id(it.first));
 238                                                         RTLIL::SigSpec port_x(State::Sx, port.size());
 239                                                         cell->unsetPort(it.first);
 240                                                         cell->setPort(it.first, port_x);
 241                                                         return design_copy;
 242                                                 }
 243
 244                                                 if (!stage2 && (cell->input(it.first) || cell->output(it.first)) && index++ == seed)
 245                                                 {
 246                                                         log_header(design, "Trying to expose cell port %s.%s.%s as module port.\n", log_id(mod), log_id(cell), log_id(it.first));
 247                                                         RTLIL::Wire *wire = mod->addWire(NEW_ID, port.size());
 248                                                         wire->set_bool_attribute(ID($bugpoint));
 249                                                         wire->port_input = cell->input(it.first);
 250                                                         wire->port_output = cell->output(it.first);
 251                                                         cell->unsetPort(it.first);
 252                                                         cell->setPort(it.first, wire);
 253                                                         mod->fixup_ports();
 254                                                         return design_copy;
 255                                                 }
 256                                         }
 257                                 }
 258                         }
 259                 }
 260                 if (assigns)
 261                 {
 262                         for (auto mod : design_copy->modules())
 263                         {
 264                                 if (mod->get_blackbox_attribute())
 265                                         continue;
 266
 267                                 for (auto &pr : mod->processes)
 268                                 {
 269                                         vector<RTLIL::CaseRule*> cases = {&pr.second->root_case};
 270                                         while (!cases.empty())
 271                                         {
 272                                                 RTLIL::CaseRule *cs = cases[0];
 273                                                 cases.erase(cases.begin());
 274                                                 for (auto it = cs->actions.begin(); it != cs->actions.end(); ++it)
 275                                                 {
 276                                                         if (index++ == seed)
 277                                                         {
 278                                                                 log_header(design, "Trying to remove assign %s %s in %s.%s.\n", log_signal(it->first), log_signal(it->second), log_id(mod), log_id(pr.first));
 279                                                                 cs->actions.erase(it);
 280                                                                 return design_copy;
 281                                                         }
 282                                                 }
 283                                                 for (auto &sw : cs->switches)
 284                                                         cases.insert(cases.end(), sw->cases.begin(), sw->cases.end());
 285                                         }
 286                                 }
 287                         }
 288                 }
 289                 if (updates)
 290                 {
 291                         for (auto mod : design_copy->modules())
 292                         {
 293                                 if (mod->get_blackbox_attribute())
 294                                         continue;
 295
 296                                 for (auto &pr : mod->processes)
 297                                 {
 298                                         for (auto &sy : pr.second->syncs)
 299                                         {
 300                                                 for (auto it = sy->actions.begin(); it != sy->actions.end(); ++it)
 301                                                 {
 302                                                         if (index++ == seed)
 303                                                         {
 304                                                                 log_header(design, "Trying to remove sync %s update %s %s in %s.%s.\n", log_signal(sy->signal), log_signal(it->first), log_signal(it->second), log_id(mod), log_id(pr.first));
 305                                                                 sy->actions.erase(it);
 306                                                                 return design_copy;
 307                                                         }
 308                                                 }
 309                                         }
 310                                 }
 311                         }
 312                 }
 313                 return nullptr;
 314         }
 315
 316         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 317         {
 318                 string yosys_cmd = "yosys", script, grep;
 319                 bool fast = false, clean = false;
 320                 bool modules = false, ports = false, cells = false, connections = false, assigns = false, updates = false, has_part = false;
 321
 322                 log_header(design, "Executing BUGPOINT pass (minimize testcases).\n");
 323                 log_push();
 324
 325                 size_t argidx;
 326                 for (argidx = 1; argidx < args.size(); argidx++)
 327                 {
 328                         if (args[argidx] == "-yosys" && argidx + 1 < args.size()) {
 329                                 yosys_cmd = args[++argidx];
 330                                 continue;
 331                         }
 332                         if (args[argidx] == "-script" && argidx + 1 < args.size()) {
 333                                 script = args[++argidx];
 334                                 continue;
 335                         }
 336                         if (args[argidx] == "-grep" && argidx + 1 < args.size()) {
 337                                 grep = args[++argidx];
 338                                 continue;
 339                         }
 340                         if (args[argidx] == "-fast") {
 341                                 fast = true;
 342                                 continue;
 343                         }
 344                         if (args[argidx] == "-clean") {
 345                                 clean = true;
 346                                 continue;
 347                         }
 348                         if (args[argidx] == "-modules") {
 349                                 modules = true;
 350                                 has_part = true;
 351                                 continue;
 352                         }
 353                         if (args[argidx] == "-ports") {
 354                                 ports = true;
 355                                 has_part = true;
 356                                 continue;
 357                         }
 358                         if (args[argidx] == "-cells") {
 359                                 cells = true;
 360                                 has_part = true;
 361                                 continue;
 362                         }
 363                         if (args[argidx] == "-connections") {
 364                                 connections = true;
 365                                 has_part = true;
 366                                 continue;
 367                         }
 368                         if (args[argidx] == "-assigns") {
 369                                 assigns = true;
 370                                 has_part = true;
 371                                 continue;
 372                         }
 373                         if (args[argidx] == "-updates") {
 374                                 updates = true;
 375                                 has_part = true;
 376                                 continue;
 377                         }
 378                         break;
 379                 }
 380                 extra_args(args, argidx, design);
 381
 382                 if (script.empty())
 383                         log_cmd_error("Missing -script option.\n");
 384
 385                 if (!has_part)
 386                 {
 387                         modules = true;
 388                         ports = true;
 389                         cells = true;
 390                         connections = true;
 391                         assigns = true;
 392                         updates = true;
 393                 }
 394
 395                 if (!design->full_selection())
 396                         log_cmd_error("This command only operates on fully selected designs!\n");
 397
 398                 RTLIL::Design *crashing_design = clean_design(design, clean);
 399                 if (run_yosys(crashing_design, yosys_cmd, script))
 400                         log_cmd_error("The provided script file and Yosys binary do not crash on this design!\n");
 401                 if (!check_logfile(grep))
 402                         log_cmd_error("The provided grep string is not found in the log file!\n");
 403
 404                 int seed = 0;
 405                 bool found_something = false, stage2 = false;
 406                 while (true)
 407                 {
 408                         if (RTLIL::Design *simplified = simplify_something(crashing_design, seed, stage2, modules, ports, cells, connections, assigns, updates))
 409                         {
 410                                 simplified = clean_design(simplified, fast, /*do_delete=*/true);
 411
 412                                 bool crashes;
 413                                 if (clean)
 414                                 {
 415                                         RTLIL::Design *testcase = clean_design(simplified);
 416                                         crashes = !run_yosys(testcase, yosys_cmd, script);
 417                                         delete testcase;
 418                                 }
 419                                 else
 420                                 {
 421                                         crashes = !run_yosys(simplified, yosys_cmd, script);
 422                                 }
 423
 424                                 if (crashes && check_logfile(grep))
 425                                 {
 426                                         log("Testcase crashes.\n");
 427                                         if (crashing_design != design)
 428                                                 delete crashing_design;
 429                                         crashing_design = simplified;
 430                                         found_something = true;
 431                                 }
 432                                 else
 433                                 {
 434                                         log("Testcase does not crash.\n");
 435                                         delete simplified;
 436                                         seed++;
 437                                 }
 438                         }
 439                         else
 440                         {
 441                                 seed = 0;
 442                                 if (found_something)
 443                                         found_something = false;
 444                                 else
 445                                 {
 446                                         if (!stage2)
 447                                         {
 448                                                 log("Demoting introduced module ports.\n");
 449                                                 stage2 = true;
 450                                         }
 451                                         else
 452                                         {
 453                                                 log("Simplifications exhausted.\n");
 454                                                 break;
 455                                         }
 456                                 }
 457                         }
 458                 }
 459
 460                 if (crashing_design != design)
 461                 {
 462                         Pass::call(design, "design -reset");
 463                         crashing_design = clean_design(crashing_design, clean, /*do_delete=*/true);
 464                         for (auto module : crashing_design->modules())
 465                                 design->add(module->clone());
 466                         delete crashing_design;
 467                 }
 468
 469                 log_pop();
 470         }
 471 } BugpointPass;
 472
 473 PRIVATE_NAMESPACE_END