passes/sat/sim.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 #include "kernel/celltypes.h"
  23
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct SimShared
  28 {
  29         bool debug = false;
  30         bool hide_internal = true;
  31         bool writeback = false;
  32 };
  33
  34 struct SimInstance
  35 {
  36         SimShared *shared;
  37
  38         Module *module;
  39         Cell *instance;
  40
  41         SimInstance *parent;
  42         dict<Cell*, SimInstance*> children;
  43
  44         SigMap sigmap;
  45         dict<SigBit, State> state_nets;
  46         dict<SigBit, pool<Cell*>> upd_cells;
  47         dict<SigBit, pool<Wire*>> upd_outports;
  48
  49         pool<SigBit> dirty_bits;
  50         pool<SimInstance*, hash_ptr_ops> dirty_children;
  51
  52         struct ff_state_t
  53         {
  54                 State past_clock;
  55                 Const past_d;
  56         };
  57
  58         struct mem_state_t
  59         {
  60                 Const past_wr_clk;
  61                 Const past_wr_en;
  62                 Const past_wr_addr;
  63                 Const past_wr_data;
  64                 Const data;
  65         };
  66
  67         dict<Cell*, ff_state_t> ff_database;
  68         dict<Cell*, mem_state_t> mem_database;
  69         pool<Cell*> formal_database;
  70
  71         dict<Wire*, pair<int, Const>> vcd_database;
  72
  73         SimInstance(SimShared *shared, Module *module, Cell *instance = nullptr, SimInstance *parent = nullptr) :
  74                         shared(shared), module(module), instance(instance), parent(parent), sigmap(module)
  75         {
  76                 if (parent) {
  77                         log_assert(parent->children.count(instance) == 0);
  78                         parent->children[instance] = this;
  79                 }
  80
  81                 for (auto wire : module->wires())
  82                 {
  83                         SigSpec sig = sigmap(wire);
  84
  85                         for (int i = 0; i < GetSize(sig); i++) {
  86                                 if (state_nets.count(sig[i]) == 0)
  87                                         state_nets[sig[i]] = State::Sx;
  88                                 if (wire->port_output) {
  89                                         upd_outports[sig[i]].insert(wire);
  90                                         dirty_bits.insert(sig[i]);
  91                                 }
  92                         }
  93
  94                         if (wire->attributes.count("\\init")) {
  95                                 Const initval = wire->attributes.at("\\init");
  96                                 for (int i = 0; i < GetSize(sig) && i < GetSize(initval); i++)
  97                                         if (initval[i] == State::S0 || initval[i] == State::S1) {
  98                                                 state_nets[sig[i]] = initval[i];
  99                                                 dirty_bits.insert(sig[i]);
 100                                         }
 101                         }
 102                 }
 103
 104                 for (auto cell : module->cells())
 105                 {
 106                         Module *mod = module->design->module(cell->type);
 107
 108                         if (mod != nullptr) {
 109                                 dirty_children.insert(new SimInstance(shared, mod, cell, this));
 110                         }
 111
 112                         for (auto &port : cell->connections()) {
 113                                 if (cell->input(port.first))
 114                                         for (auto bit : sigmap(port.second))
 115                                                 upd_cells[bit].insert(cell);
 116                         }
 117
 118                         if (cell->type.in("$dff")) {
 119                                 ff_state_t ff;
 120                                 ff.past_clock = State::Sx;
 121                                 ff.past_d = Const(State::Sx, cell->getParam("\\WIDTH").as_int());
 122                                 ff_database[cell] = ff;
 123                         }
 124
 125                         if (cell->type.in("$assert", "$cover", "$assume")) {
 126                                 formal_database.insert(cell);
 127                         }
 128                 }
 129         }
 130
 131         ~SimInstance()
 132         {
 133                 for (auto child : children)
 134                         delete child.second;
 135         }
 136
 137         IdString name() const
 138         {
 139                 if (instance != nullptr)
 140                         return instance->name;
 141                 return module->name;
 142         }
 143
 144         std::string hiername() const
 145         {
 146                 if (instance != nullptr)
 147                         return parent->hiername() + "." + log_id(instance->name);
 148
 149                 return log_id(module->name);
 150         }
 151
 152         Const get_state(SigSpec sig)
 153         {
 154                 Const value;
 155
 156                 for (auto bit : sigmap(sig))
 157                         if (bit.wire == nullptr)
 158                                 value.bits.push_back(bit.data);
 159                         else if (state_nets.count(bit))
 160                                 value.bits.push_back(state_nets.at(bit));
 161                         else
 162                                 value.bits.push_back(State::Sz);
 163
 164                 if (shared->debug)
 165                         log("[%s] get %s: %s\n", hiername().c_str(), log_signal(sig), log_signal(value));
 166                 return value;
 167         }
 168
 169         bool set_state(SigSpec sig, Const value)
 170         {
 171                 bool did_something = false;
 172
 173                 sig = sigmap(sig);
 174                 log_assert(GetSize(sig) == GetSize(value));
 175
 176                 for (int i = 0; i < GetSize(sig); i++)
 177                         if (state_nets.at(sig[i]) != value[i]) {
 178                                 state_nets.at(sig[i]) = value[i];
 179                                 dirty_bits.insert(sig[i]);
 180                                 did_something = true;
 181                         }
 182
 183                 if (shared->debug)
 184                         log("[%s] set %s: %s\n", hiername().c_str(), log_signal(sig), log_signal(value));
 185                 return did_something;
 186         }
 187
 188         void update_cell(Cell *cell)
 189         {
 190                 if (ff_database.count(cell))
 191                         return;
 192
 193                 if (formal_database.count(cell))
 194                         return;
 195
 196                 if (children.count(cell))
 197                 {
 198                         auto child = children.at(cell);
 199                         for (auto &conn: cell->connections())
 200                                 if (cell->input(conn.first)) {
 201                                         Const value = get_state(conn.second);
 202                                         child->set_state(child->module->wire(conn.first), value);
 203                                 }
 204                         dirty_children.insert(child);
 205                         return;
 206                 }
 207
 208                 if (yosys_celltypes.cell_evaluable(cell->type))
 209                 {
 210                         RTLIL::SigSpec sig_a, sig_b, sig_c, sig_d, sig_s, sig_y;
 211                         bool has_a, has_b, has_c, has_d, has_s, has_y;
 212
 213                         has_a = cell->hasPort("\\A");
 214                         has_b = cell->hasPort("\\B");
 215                         has_c = cell->hasPort("\\C");
 216                         has_d = cell->hasPort("\\D");
 217                         has_s = cell->hasPort("\\S");
 218                         has_y = cell->hasPort("\\Y");
 219
 220                         if (has_a) sig_a = cell->getPort("\\A");
 221                         if (has_b) sig_b = cell->getPort("\\B");
 222                         if (has_c) sig_c = cell->getPort("\\C");
 223                         if (has_d) sig_d = cell->getPort("\\D");
 224                         if (has_s) sig_s = cell->getPort("\\S");
 225                         if (has_y) sig_y = cell->getPort("\\Y");
 226
 227                         if (shared->debug)
 228                                 log("[%s] eval %s (%s)\n", hiername().c_str(), log_id(cell), log_id(cell->type));
 229
 230                         // Simple (A -> Y) and (A,B -> Y) cells
 231                         if (has_a && !has_c && !has_d && !has_s && has_y) {
 232                                 set_state(sig_y, CellTypes::eval(cell, get_state(sig_a), get_state(sig_b)));
 233                                 return;
 234                         }
 235
 236                         // (A,B,C -> Y) cells
 237                         if (has_a && has_b && has_c && !has_d && !has_s && has_y) {
 238                                 set_state(sig_y, CellTypes::eval(cell, get_state(sig_a), get_state(sig_b), get_state(sig_c)));
 239                                 return;
 240                         }
 241
 242                         // (A,B,S -> Y) cells
 243                         if (has_a && has_b && !has_c && !has_d && has_s && has_y) {
 244                                 set_state(sig_y, CellTypes::eval(cell, get_state(sig_a), get_state(sig_b), get_state(sig_s)));
 245                                 return;
 246                         }
 247
 248                         log_warning("Unsupported evaluable cell type: %s (%s.%s)\n", log_id(cell->type), log_id(module), log_id(cell));
 249                         return;
 250                 }
 251
 252                 // FIXME
 253
 254                 log_error("Unsupported cell type: %s (%s.%s)\n", log_id(cell->type), log_id(module), log_id(cell));
 255         }
 256
 257         void update_ph1()
 258         {
 259                 pool<Cell*> queue_cells;
 260                 pool<Wire*> queue_outports;
 261
 262                 while (1)
 263                 {
 264                         for (auto bit : dirty_bits)
 265                         {
 266                                 if (upd_cells.count(bit))
 267                                         for (auto cell : upd_cells.at(bit))
 268                                                 queue_cells.insert(cell);
 269
 270                                 if (upd_outports.count(bit) && parent != nullptr)
 271                                         for (auto wire : upd_outports.at(bit))
 272                                                 queue_outports.insert(wire);
 273                         }
 274
 275                         dirty_bits.clear();
 276
 277                         if (!queue_cells.empty())
 278                         {
 279                                 for (auto cell : queue_cells)
 280                                         update_cell(cell);
 281
 282                                 queue_cells.clear();
 283                                 continue;
 284                         }
 285
 286                         for (auto wire : queue_outports)
 287                                 if (instance->hasPort(wire->name)) {
 288                                         Const value = get_state(wire);
 289                                         parent->set_state(instance->getPort(wire->name), value);
 290                                 }
 291
 292                         queue_outports.clear();
 293
 294                         for (auto child : dirty_children)
 295                                 child->update_ph1();
 296
 297                         dirty_children.clear();
 298
 299                         if (dirty_bits.empty())
 300                                 break;
 301                 }
 302         }
 303
 304         bool update_ph2()
 305         {
 306                 bool did_something = false;
 307
 308                 for (auto &it : ff_database)
 309                 {
 310                         Cell *cell = it.first;
 311                         ff_state_t &ff = it.second;
 312
 313                         if (cell->type.in("$dff"))
 314                         {
 315                                 bool clkpol = cell->getParam("\\CLK_POLARITY").as_bool();
 316                                 State current_clock = get_state(cell->getPort("\\CLK"))[0];
 317
 318                                 if (clkpol ? (ff.past_clock == State::S1 || current_clock != State::S1) :
 319                                                 (ff.past_clock == State::S0 || current_clock != State::S0))
 320                                         continue;
 321
 322                                 if (set_state(cell->getPort("\\Q"), ff.past_d))
 323                                         did_something = true;
 324                         }
 325                 }
 326
 327                 for (auto it : children)
 328                         if (it.second->update_ph2()) {
 329                                 dirty_children.insert(it.second);
 330                                 did_something = true;
 331                         }
 332
 333                 return did_something;
 334         }
 335
 336         void update_ph3()
 337         {
 338                 for (auto &it : ff_database)
 339                 {
 340                         Cell *cell = it.first;
 341                         ff_state_t &ff = it.second;
 342
 343                         if (cell->type.in("$dff")) {
 344                                 ff.past_clock = get_state(cell->getPort("\\CLK"))[0];
 345                                 ff.past_d = get_state(cell->getPort("\\D"));
 346                         }
 347                 }
 348
 349                 for (auto cell : formal_database)
 350                 {
 351                         string label = log_id(cell);
 352                         if (cell->attributes.count("\\src"))
 353                                 label = cell->attributes.at("\\src").decode_string();
 354
 355                         State a = get_state(cell->getPort("\\A"))[0];
 356                         State en = get_state(cell->getPort("\\EN"))[0];
 357
 358                         if (cell->type == "$cover" && en == State::S1 && a != State::S1)
 359                                 log("Cover %s.%s (%s) reached.\n", hiername().c_str(), log_id(cell), label.c_str());
 360
 361                         if (cell->type == "$assume" && en == State::S1 && a != State::S1)
 362                                 log("Assumption %s.%s (%s) failed.\n", hiername().c_str(), log_id(cell), label.c_str());
 363
 364                         if (cell->type == "$assert" && en == State::S1 && a != State::S1)
 365                                 log_warning("Assert %s.%s (%s) failed.\n", hiername().c_str(), log_id(cell), label.c_str());
 366                 }
 367
 368                 for (auto it : children)
 369                         it.second->update_ph3();
 370         }
 371
 372         void writeback(pool<Module*> &wbmods)
 373         {
 374                 if (wbmods.count(module))
 375                         log_error("Instance %s of module %s is not unique: Writeback not possible. (Fix by running 'singleton'.)\n", hiername().c_str(), log_id(module));
 376
 377                 wbmods.insert(module);
 378
 379                 for (auto wire : module->wires())
 380                         wire->attributes.erase("\\init");
 381
 382                 for (auto &it : ff_database)
 383                 {
 384                         Cell *cell = it.first;
 385                         SigSpec sig_q = cell->getPort("\\Q");
 386                         Const initval = get_state(sig_q);
 387
 388                         for (int i = 0; i < GetSize(sig_q); i++)
 389                         {
 390                                 Wire *w = sig_q[i].wire;
 391
 392                                 if (w->attributes.count("\\init") == 0)
 393                                         w->attributes["\\init"] = Const(State::Sx, GetSize(w));
 394
 395                                 w->attributes["\\init"][sig_q[i].offset] = initval[i];
 396                         }
 397                 }
 398
 399                 for (auto it : children)
 400                         it.second->writeback(wbmods);
 401         }
 402
 403         void write_vcd_header(std::ofstream &f, int &id)
 404         {
 405                 f << stringf("$scope module %s $end\n", log_id(name()));
 406
 407                 for (auto wire : module->wires())
 408                 {
 409                         if (shared->hide_internal && wire->name[0] == '$')
 410                                 continue;
 411
 412                         f << stringf("$var wire %d n%d %s%s $end\n", GetSize(wire), id, wire->name[0] == '$' ? "\\" : "", log_id(wire));
 413                         vcd_database[wire] = make_pair(id++, Const());
 414                 }
 415
 416                 for (auto child : children)
 417                         child.second->write_vcd_header(f, id);
 418
 419                 f << stringf("$upscope $end\n");
 420         }
 421
 422         void write_vcd_step(std::ofstream &f)
 423         {
 424                 for (auto &it : vcd_database)
 425                 {
 426                         Wire *wire = it.first;
 427                         Const value = get_state(wire);
 428                         int id = it.second.first;
 429
 430                         if (it.second.second == value)
 431                                 continue;
 432
 433                         it.second.second = value;
 434
 435                         f << "b";
 436                         for (int i = GetSize(value)-1; i >= 0; i--) {
 437                                 switch (value[i]) {
 438                                         case State::S0: f << "0"; break;
 439                                         case State::S1: f << "1"; break;
 440                                         case State::Sx: f << "x"; break;
 441                                         default: f << "z";
 442                                 }
 443                         }
 444
 445                         f << stringf(" n%d\n", id);
 446                 }
 447
 448                 for (auto child : children)
 449                         child.second->write_vcd_step(f);
 450         }
 451 };
 452
 453 struct SimWorker : SimShared
 454 {
 455         SimInstance *top = nullptr;
 456         std::ofstream vcdfile;
 457         pool<IdString> clock, clockn, reset, resetn;
 458
 459         ~SimWorker()
 460         {
 461                 delete top;
 462         }
 463
 464         void write_vcd_header()
 465         {
 466                 if (!vcdfile.is_open())
 467                         return;
 468
 469                 int id = 1;
 470                 top->write_vcd_header(vcdfile, id);
 471
 472                 vcdfile << stringf("$enddefinitions $end\n");
 473         }
 474
 475         void write_vcd_step(int t)
 476         {
 477                 if (!vcdfile.is_open())
 478                         return;
 479
 480                 vcdfile << stringf("#%d\n", t);
 481                 top->write_vcd_step(vcdfile);
 482         }
 483
 484         void update()
 485         {
 486                 while (1)
 487                 {
 488                         if (debug)
 489                                 log("\n-- ph1 --\n");
 490
 491                         top->update_ph1();
 492
 493                         if (debug)
 494                                 log("\n-- ph2 --\n");
 495
 496                         if (!top->update_ph2())
 497                                 break;
 498                 }
 499
 500                 if (debug)
 501                         log("\n-- ph3 --\n");
 502
 503                 top->update_ph3();
 504         }
 505
 506         void set_inports(pool<IdString> ports, State value)
 507         {
 508                 for (auto portname : ports)
 509                 {
 510                         Wire *w = top->module->wire(portname);
 511
 512                         if (w == nullptr)
 513                                 log_error("Can't find port %s on module %s.\n", log_id(portname), log_id(top->module));
 514
 515                         top->set_state(w, value);
 516                 }
 517         }
 518
 519         void run(Module *topmod, int numcycles)
 520         {
 521                 log_assert(top == nullptr);
 522                 top = new SimInstance(this, topmod);
 523
 524                 if (debug)
 525                         log("\n===== 0 =====\n");
 526                 else
 527                         log("Simulating cycle 0.\n");
 528
 529                 set_inports(reset, State::S1);
 530                 set_inports(resetn, State::S0);
 531
 532                 update();
 533
 534                 write_vcd_header();
 535                 write_vcd_step(0);
 536
 537                 for (int cycle = 0; cycle < numcycles; cycle++)
 538                 {
 539                         if (debug)
 540                                 log("\n===== %d =====\n", 10*cycle + 5);
 541
 542                         set_inports(clock, State::S0);
 543                         set_inports(clockn, State::S1);
 544
 545                         update();
 546                         write_vcd_step(10*cycle + 5);
 547
 548                         if (debug)
 549                                 log("\n===== %d =====\n", 10*cycle + 10);
 550                         else
 551                                 log("Simulating cycle %d.\n", cycle+1);
 552
 553                         set_inports(clock, State::S1);
 554                         set_inports(clockn, State::S0);
 555
 556                         if (cycle == 0) {
 557                                 set_inports(reset, State::S0);
 558                                 set_inports(resetn, State::S1);
 559                         }
 560
 561                         update();
 562                         write_vcd_step(10*cycle + 10);
 563                 }
 564
 565                 write_vcd_step(10*numcycles + 2);
 566
 567                 if (writeback) {
 568                         pool<Module*> wbmods;
 569                         top->writeback(wbmods);
 570                 }
 571         }
 572 };
 573
 574 struct SimPass : public Pass {
 575         SimPass() : Pass("sim", "simulate the circuit") { }
 576         virtual void help()
 577         {
 578                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 579                 log("\n");
 580                 log("    sim [options] [top-level]\n");
 581                 log("\n");
 582                 log("This command simulates the circuit using the given top-level module.\n");
 583                 log("\n");
 584                 log("    -vcd <filename>\n");
 585                 log("        write the simulation results to the given VCD file\n");
 586                 log("\n");
 587                 log("    -clock <portname>\n");
 588                 log("        name of top-level clock input\n");
 589                 log("\n");
 590                 log("    -clockn <portname>\n");
 591                 log("        name of top-level clock input (inverse polarity)\n");
 592                 log("\n");
 593                 log("    -reset <portname>\n");
 594                 log("        name of top-level reset input (active high)\n");
 595                 log("\n");
 596                 log("    -resetn <portname>\n");
 597                 log("        name of top-level inverted reset input (active low)\n");
 598                 log("\n");
 599                 log("    -n <integer>\n");
 600                 log("        number of cycles to simulate (default: 20)\n");
 601                 log("\n");
 602                 log("    -a\n");
 603                 log("        include all nets in VCD output, nut just those with public names\n");
 604                 log("\n");
 605                 log("    -w\n");
 606                 log("        writeback mode: use final simulation state as new init state\n");
 607                 log("\n");
 608                 log("    -d\n");
 609                 log("        enable debug output\n");
 610                 log("\n");
 611         }
 612         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 613         {
 614                 SimWorker worker;
 615                 int numcycles = 20;
 616
 617                 log_header(design, "Executing SIM pass (simulate the circuit).\n");
 618
 619                 size_t argidx;
 620                 for (argidx = 1; argidx < args.size(); argidx++) {
 621                         if (args[argidx] == "-vcd" && argidx+1 < args.size()) {
 622                                 worker.vcdfile.open(args[++argidx].c_str());
 623                                 continue;
 624                         }
 625                         if (args[argidx] == "-n" && argidx+1 < args.size()) {
 626                                 numcycles = atoi(args[++argidx].c_str());
 627                                 continue;
 628                         }
 629                         if (args[argidx] == "-clock" && argidx+1 < args.size()) {
 630                                 worker.clock.insert(RTLIL::escape_id(args[++argidx]));
 631                                 continue;
 632                         }
 633                         if (args[argidx] == "-clockn" && argidx+1 < args.size()) {
 634                                 worker.clockn.insert(RTLIL::escape_id(args[++argidx]));
 635                                 continue;
 636                         }
 637                         if (args[argidx] == "-reset" && argidx+1 < args.size()) {
 638                                 worker.reset.insert(RTLIL::escape_id(args[++argidx]));
 639                                 continue;
 640                         }
 641                         if (args[argidx] == "-resetn" && argidx+1 < args.size()) {
 642                                 worker.resetn.insert(RTLIL::escape_id(args[++argidx]));
 643                                 continue;
 644                         }
 645                         if (args[argidx] == "-a") {
 646                                 worker.hide_internal = false;
 647                                 continue;
 648                         }
 649                         if (args[argidx] == "-d") {
 650                                 worker.debug = true;
 651                                 continue;
 652                         }
 653                         if (args[argidx] == "-w") {
 654                                 worker.writeback = true;
 655                                 continue;
 656                         }
 657                         break;
 658                 }
 659                 extra_args(args, argidx, design);
 660
 661                 Module *top_mod = nullptr;
 662
 663                 if (design->full_selection()) {
 664                         top_mod = design->top_module();
 665                 } else {
 666                         auto mods = design->selected_whole_modules();
 667                         if (GetSize(mods) != 1)
 668                                 log_cmd_error("Only one top module must be selected.\n");
 669                         top_mod = mods.front();
 670                 }
 671
 672                 worker.run(top_mod, numcycles);
 673         }
 674 } SimPass;
 675
 676 PRIVATE_NAMESPACE_END