kernel/rtlil.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/rtlil.h"
  21 #include "kernel/log.h"
  22 #include <assert.h>
  23 #include <algorithm>
  24
  25 int RTLIL::autoidx = 1;
  26
  27 RTLIL::Const::Const(std::string str) : str(str)
  28 {
  29         for (size_t i = 0; i < str.size(); i++) {
  30                 unsigned char ch = str[i];
  31                 for (int j = 0; j < 8; j++) {
  32                         bits.push_back((ch & 1) != 0 ? RTLIL::S1 : RTLIL::S0);
  33                         ch = ch >> 1;
  34                 }
  35         }
  36 }
  37
  38 RTLIL::Const::Const(int val, int width)
  39 {
  40         for (int i = 0; i < width; i++) {
  41                 bits.push_back((val & 1) != 0 ? RTLIL::S1 : RTLIL::S0);
  42                 val = val >> 1;
  43         }
  44 }
  45
  46 RTLIL::Const::Const(RTLIL::State bit, int width)
  47 {
  48         for (int i = 0; i < width; i++)
  49                 bits.push_back(bit);
  50 }
  51
  52 bool RTLIL::Const::operator <(const RTLIL::Const &other) const
  53 {
  54         if (bits.size() != other.bits.size())
  55                 return bits.size() < other.bits.size();
  56         for (size_t i = 0; i < bits.size(); i++)
  57                 if (bits[i] != other.bits[i])
  58                         return bits[i] < other.bits[i];
  59         return false;
  60 }
  61
  62 bool RTLIL::Const::operator ==(const RTLIL::Const &other) const
  63 {
  64         return bits == other.bits;
  65 }
  66
  67 bool RTLIL::Const::operator !=(const RTLIL::Const &other) const
  68 {
  69         return bits != other.bits;
  70 }
  71
  72 bool RTLIL::Const::as_bool() const
  73 {
  74         for (size_t i = 0; i < bits.size(); i++)
  75                 if (bits[i] == RTLIL::S1)
  76                         return true;
  77         return false;
  78 }
  79
  80 int RTLIL::Const::as_int() const
  81 {
  82         int ret = 0;
  83         for (size_t i = 0; i < bits.size() && i < 32; i++)
  84                 if (bits[i] == RTLIL::S1)
  85                         ret |= 1 << i;
  86         return ret;
  87 }
  88
  89 std::string RTLIL::Const::as_string() const
  90 {
  91         std::string ret;
  92         for (size_t i = bits.size(); i > 0; i--)
  93                 switch (bits[i-1]) {
  94                         case S0: ret += "0"; break;
  95                         case S1: ret += "1"; break;
  96                         case Sx: ret += "x"; break;
  97                         case Sz: ret += "z"; break;
  98                         case Sa: ret += "-"; break;
  99                         case Sm: ret += "m"; break;
 100                 }
 101         return ret;
 102 }
 103
 104 bool RTLIL::Selection::selected_module(RTLIL::IdString mod_name) const
 105 {
 106         if (full_selection)
 107                 return true;
 108         if (selected_modules.count(mod_name) > 0)
 109                 return true;
 110         if (selected_members.count(mod_name) > 0)
 111                 return true;
 112         return false;
 113 }
 114
 115 bool RTLIL::Selection::selected_whole_module(RTLIL::IdString mod_name) const
 116 {
 117         if (full_selection)
 118                 return true;
 119         if (selected_modules.count(mod_name) > 0)
 120                 return true;
 121         return false;
 122 }
 123
 124 bool RTLIL::Selection::selected_member(RTLIL::IdString mod_name, RTLIL::IdString memb_name) const
 125 {
 126         if (full_selection)
 127                 return true;
 128         if (selected_modules.count(mod_name) > 0)
 129                 return true;
 130         if (selected_members.count(mod_name) > 0)
 131                 if (selected_members.at(mod_name).count(memb_name) > 0)
 132                         return true;
 133         return false;
 134 }
 135
 136 void RTLIL::Selection::optimize(RTLIL::Design *design)
 137 {
 138         if (full_selection) {
 139                 selected_modules.clear();
 140                 selected_members.clear();
 141                 return;
 142         }
 143
 144         std::vector<RTLIL::IdString> del_list, add_list;
 145
 146         del_list.clear();
 147         for (auto mod_name : selected_modules) {
 148                 if (design->modules.count(mod_name) == 0)
 149                         del_list.push_back(mod_name);
 150                 selected_members.erase(mod_name);
 151         }
 152         for (auto mod_name : del_list)
 153                 selected_modules.erase(mod_name);
 154
 155         del_list.clear();
 156         for (auto &it : selected_members)
 157                 if (design->modules.count(it.first) == 0)
 158                         del_list.push_back(it.first);
 159         for (auto mod_name : del_list)
 160                 selected_members.erase(mod_name);
 161
 162         for (auto &it : selected_members) {
 163                 del_list.clear();
 164                 for (auto memb_name : it.second)
 165                         if (design->modules[it.first]->count_id(memb_name) == 0)
 166                                 del_list.push_back(memb_name);
 167                 for (auto memb_name : del_list)
 168                         it.second.erase(memb_name);
 169         }
 170
 171         del_list.clear();
 172         add_list.clear();
 173         for (auto &it : selected_members)
 174                 if (it.second.size() == 0)
 175                         del_list.push_back(it.first);
 176                 else if (it.second.size() == design->modules[it.first]->wires.size() + design->modules[it.first]->memories.size() +
 177                                 design->modules[it.first]->cells.size() + design->modules[it.first]->processes.size())
 178                         add_list.push_back(it.first);
 179         for (auto mod_name : del_list)
 180                 selected_members.erase(mod_name);
 181         for (auto mod_name : add_list) {
 182                 selected_members.erase(mod_name);
 183                 selected_modules.insert(mod_name);
 184         }
 185
 186         if (selected_modules.size() == design->modules.size()) {
 187                 full_selection = true;
 188                 selected_modules.clear();
 189                 selected_members.clear();
 190         }
 191 }
 192
 193 RTLIL::Design::~Design()
 194 {
 195         for (auto it = modules.begin(); it != modules.end(); it++)
 196                 delete it->second;
 197 }
 198
 199 void RTLIL::Design::check()
 200 {
 201 #ifndef NDEBUG
 202         for (auto &it : modules) {
 203                 assert(it.first == it.second->name);
 204                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 205                 it.second->check();
 206         }
 207 #endif
 208 }
 209
 210 void RTLIL::Design::optimize()
 211 {
 212         for (auto &it : modules)
 213                 it.second->optimize();
 214         for (auto &it : selection_stack)
 215                 it.optimize(this);
 216         for (auto &it : selection_vars)
 217                 it.second.optimize(this);
 218 }
 219
 220 bool RTLIL::Design::selected_module(RTLIL::IdString mod_name) const
 221 {
 222         if (!selected_active_module.empty() && mod_name != selected_active_module)
 223                 return false;
 224         if (selection_stack.size() == 0)
 225                 return true;
 226         return selection_stack.back().selected_module(mod_name);
 227 }
 228
 229 bool RTLIL::Design::selected_whole_module(RTLIL::IdString mod_name) const
 230 {
 231         if (!selected_active_module.empty() && mod_name != selected_active_module)
 232                 return false;
 233         if (selection_stack.size() == 0)
 234                 return true;
 235         return selection_stack.back().selected_whole_module(mod_name);
 236 }
 237
 238 bool RTLIL::Design::selected_member(RTLIL::IdString mod_name, RTLIL::IdString memb_name) const
 239 {
 240         if (!selected_active_module.empty() && mod_name != selected_active_module)
 241                 return false;
 242         if (selection_stack.size() == 0)
 243                 return true;
 244         return selection_stack.back().selected_member(mod_name, memb_name);
 245 }
 246
 247 RTLIL::Module::~Module()
 248 {
 249         for (auto it = wires.begin(); it != wires.end(); it++)
 250                 delete it->second;
 251         for (auto it = memories.begin(); it != memories.end(); it++)
 252                 delete it->second;
 253         for (auto it = cells.begin(); it != cells.end(); it++)
 254                 delete it->second;
 255         for (auto it = processes.begin(); it != processes.end(); it++)
 256                 delete it->second;
 257 }
 258
 259 RTLIL::IdString RTLIL::Module::derive(RTLIL::Design*, std::map<RTLIL::IdString, RTLIL::Const>)
 260 {
 261         log_error("Module `%s' is used with parameters but is not parametric!\n", id2cstr(name));
 262 }
 263
 264 void RTLIL::Module::update_auto_wires(std::map<RTLIL::IdString, int>)
 265 {
 266         log_error("Module `%s' has automatic wires bu no HDL backend to handle it!\n", id2cstr(name));
 267 }
 268
 269 size_t RTLIL::Module::count_id(RTLIL::IdString id)
 270 {
 271         return wires.count(id) + memories.count(id) + cells.count(id) + processes.count(id);
 272 }
 273
 274 void RTLIL::Module::check()
 275 {
 276 #ifndef NDEBUG
 277         for (auto &it : wires) {
 278                 assert(it.first == it.second->name);
 279                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 280                 assert(it.second->width >= 0);
 281                 assert(it.second->port_id >= 0);
 282                 for (auto &it2 : it.second->attributes) {
 283                         assert(it2.first.size() > 0 && (it2.first[0] == '\\' || it2.first[0] == '$'));
 284                 }
 285         }
 286
 287         for (auto &it : memories) {
 288                 assert(it.first == it.second->name);
 289                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 290                 assert(it.second->width >= 0);
 291                 assert(it.second->size >= 0);
 292                 for (auto &it2 : it.second->attributes) {
 293                         assert(it2.first.size() > 0 && (it2.first[0] == '\\' || it2.first[0] == '$'));
 294                 }
 295         }
 296
 297         for (auto &it : cells) {
 298                 assert(it.first == it.second->name);
 299                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 300                 assert(it.second->type.size() > 0 && (it.second->type[0] == '\\' || it.second->type[0] == '$'));
 301                 for (auto &it2 : it.second->connections) {
 302                         assert(it2.first.size() > 0 && (it2.first[0] == '\\' || it2.first[0] == '$'));
 303                         it2.second.check();
 304                 }
 305                 for (auto &it2 : it.second->attributes) {
 306                         assert(it2.first.size() > 0 && (it2.first[0] == '\\' || it2.first[0] == '$'));
 307                 }
 308                 for (auto &it2 : it.second->parameters) {
 309                         assert(it2.first.size() > 0 && (it2.first[0] == '\\' || it2.first[0] == '$'));
 310                 }
 311         }
 312
 313         for (auto &it : processes) {
 314                 assert(it.first == it.second->name);
 315                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 316                 // FIXME: More checks here..
 317         }
 318
 319         for (auto &it : connections) {
 320                 assert(it.first.width == it.second.width);
 321                 it.first.check();
 322                 it.second.check();
 323         }
 324
 325         for (auto &it : attributes) {
 326                 assert(it.first.size() > 0 && (it.first[0] == '\\' || it.first[0] == '$'));
 327         }
 328 #endif
 329 }
 330
 331 void RTLIL::Module::optimize()
 332 {
 333         for (auto &it : cells)
 334                 it.second->optimize();
 335         for (auto &it : processes)
 336                 it.second->optimize();
 337         for (auto &it : connections) {
 338                 it.first.optimize();
 339                 it.second.optimize();
 340         }
 341 }
 342
 343 void RTLIL::Module::add(RTLIL::Wire *wire) {
 344         assert(!wire->name.empty());
 345         assert(count_id(wire->name) == 0);
 346         wires[wire->name] = wire;
 347 }
 348
 349 void RTLIL::Module::add(RTLIL::Cell *cell) {
 350         assert(!cell->name.empty());
 351         assert(count_id(cell->name) == 0);
 352         cells[cell->name] = cell;
 353 }
 354
 355 RTLIL::Wire::Wire()
 356 {
 357         width = 1;
 358         start_offset = 0;
 359         port_id = 0;
 360         port_input = false;
 361         port_output = false;
 362         auto_width = false;
 363 }
 364
 365 RTLIL::Memory::Memory()
 366 {
 367         width = 1;
 368         size = 0;
 369 }
 370
 371 void RTLIL::Cell::optimize()
 372 {
 373         for (auto &it : connections)
 374                 it.second.optimize();
 375 }
 376
 377 RTLIL::SigChunk::SigChunk()
 378 {
 379         wire = NULL;
 380         width = 0;
 381         offset = 0;
 382 }
 383
 384 RTLIL::SigChunk::SigChunk(const RTLIL::Const &data)
 385 {
 386         wire = NULL;
 387         this->data = data;
 388         width = data.bits.size();
 389         offset = 0;
 390 }
 391
 392 RTLIL::SigChunk::SigChunk(RTLIL::Wire *wire, int width, int offset)
 393 {
 394         this->wire = wire;
 395         this->width = width >= 0 ? width : wire->width;
 396         this->offset = offset;
 397 }
 398
 399 RTLIL::SigChunk::SigChunk(const std::string &str)
 400 {
 401         wire = NULL;
 402         data = RTLIL::Const(str);
 403         width = data.bits.size();
 404         offset = 0;
 405 }
 406
 407 RTLIL::SigChunk::SigChunk(int val, int width)
 408 {
 409         wire = NULL;
 410         data = RTLIL::Const(val, width);
 411         this->width = data.bits.size();
 412         offset = 0;
 413 }
 414
 415 RTLIL::SigChunk::SigChunk(RTLIL::State bit, int width)
 416 {
 417         wire = NULL;
 418         data = RTLIL::Const(bit, width);
 419         this->width = data.bits.size();
 420         offset = 0;
 421 }
 422
 423 RTLIL::SigChunk RTLIL::SigChunk::extract(int offset, int length) const
 424 {
 425         RTLIL::SigChunk ret;
 426         if (wire) {
 427                 ret.wire = wire;
 428                 ret.offset = this->offset + offset;
 429                 ret.width = length;
 430         } else {
 431                 for (int i = 0; i < length; i++)
 432                         ret.data.bits.push_back(data.bits[offset+i]);
 433                 ret.width = length;
 434         }
 435         return ret;
 436 }
 437
 438 bool RTLIL::SigChunk::operator <(const RTLIL::SigChunk &other) const
 439 {
 440         if (wire && other.wire)
 441                 if (wire->name != other.wire->name)
 442                         return wire->name < other.wire->name;
 443         if (wire != other.wire)
 444                 return wire < other.wire;
 445
 446         if (offset != other.offset)
 447                 return offset < other.offset;
 448
 449         if (width != other.width)
 450                 return width < other.width;
 451
 452         if (data.bits != other.data.bits)
 453                 return data.bits < other.data.bits;
 454
 455         return false;
 456 }
 457
 458 bool RTLIL::SigChunk::operator ==(const RTLIL::SigChunk &other) const
 459 {
 460         if (wire != other.wire || width != other.width || offset != other.offset)
 461                 return false;
 462         if (data.bits != other.data.bits)
 463                 return false;
 464         return true;
 465 }
 466
 467 bool RTLIL::SigChunk::operator !=(const RTLIL::SigChunk &other) const
 468 {
 469         if (*this == other)
 470                 return false;
 471         return true;
 472 }
 473
 474 RTLIL::SigSpec::SigSpec()
 475 {
 476         width = 0;
 477 }
 478
 479 RTLIL::SigSpec::SigSpec(const RTLIL::Const &data)
 480 {
 481         chunks.push_back(RTLIL::SigChunk(data));
 482         width = chunks.back().width;
 483         check();
 484 }
 485
 486 RTLIL::SigSpec::SigSpec(const RTLIL::SigChunk &chunk)
 487 {
 488         chunks.push_back(chunk);
 489         width = chunks.back().width;
 490         check();
 491 }
 492
 493 RTLIL::SigSpec::SigSpec(RTLIL::Wire *wire, int width, int offset)
 494 {
 495         chunks.push_back(RTLIL::SigChunk(wire, width, offset));
 496         this->width = chunks.back().width;
 497         check();
 498 }
 499
 500 RTLIL::SigSpec::SigSpec(const std::string &str)
 501 {
 502         chunks.push_back(RTLIL::SigChunk(str));
 503         width = chunks.back().width;
 504         check();
 505 }
 506
 507 RTLIL::SigSpec::SigSpec(int val, int width)
 508 {
 509         chunks.push_back(RTLIL::SigChunk(val, width));
 510         this->width = chunks.back().width;
 511         check();
 512 }
 513
 514 RTLIL::SigSpec::SigSpec(RTLIL::State bit, int width)
 515 {
 516         chunks.push_back(RTLIL::SigChunk(bit, width));
 517         this->width = chunks.back().width;
 518         check();
 519 }
 520
 521 void RTLIL::SigSpec::expand()
 522 {
 523         std::vector<RTLIL::SigChunk> new_chunks;
 524         for (size_t i = 0; i < chunks.size(); i++) {
 525                 assert(chunks[i].data.str.empty());
 526                 for (int j = 0; j < chunks[i].width; j++)
 527                         new_chunks.push_back(chunks[i].extract(j, 1));
 528         }
 529         chunks.swap(new_chunks);
 530         check();
 531 }
 532
 533 void RTLIL::SigSpec::optimize()
 534 {
 535         for (size_t i = 0; i < chunks.size(); i++) {
 536                 if (chunks[i].wire && chunks[i].wire->auto_width)
 537                         continue;
 538                 if (chunks[i].width == 0)
 539                         chunks.erase(chunks.begin()+i--);
 540         }
 541         for (size_t i = 1; i < chunks.size(); i++) {
 542                 RTLIL::SigChunk &ch1 = chunks[i-1];
 543                 RTLIL::SigChunk &ch2 = chunks[i];
 544                 if (ch1.wire && ch1.wire->auto_width)
 545                         continue;
 546                 if (ch2.wire && ch2.wire->auto_width)
 547                         continue;
 548                 if (ch1.wire == ch2.wire) {
 549                         if (ch1.wire != NULL && ch1.offset+ch1.width == ch2.offset) {
 550                                 ch1.width += ch2.width;
 551                                 goto merged_with_next_chunk;
 552                         }
 553                         if (ch1.wire == NULL && ch1.data.str.empty() == ch2.data.str.empty()) {
 554                                 ch1.data.str = ch2.data.str + ch1.data.str;
 555                                 ch1.data.bits.insert(ch1.data.bits.end(), ch2.data.bits.begin(), ch2.data.bits.end());
 556                                 ch1.width += ch2.width;
 557                                 goto merged_with_next_chunk;
 558                         }
 559                 }
 560                 if (0) {
 561         merged_with_next_chunk:
 562                         chunks.erase(chunks.begin()+i);
 563                         i--;
 564                 }
 565         }
 566         check();
 567 }
 568
 569 bool RTLIL::SigChunk::compare(const RTLIL::SigChunk &a, const RTLIL::SigChunk &b)
 570 {
 571         if (a.wire != b.wire) {
 572                 if (a.wire == NULL || b.wire == NULL)
 573                         return a.wire < b.wire;
 574                 else if (a.wire->name != b.wire->name)
 575                         return a.wire->name < b.wire->name;
 576                 else
 577                         return a.wire < b.wire;
 578         }
 579         if (a.offset != b.offset)
 580                 return a.offset < b.offset;
 581         if (a.width != b.width)
 582                 return a.width < b.width;
 583         return a.data.bits < b.data.bits;
 584 }
 585
 586 void RTLIL::SigSpec::sort()
 587 {
 588         expand();
 589         std::sort(chunks.begin(), chunks.end(), RTLIL::SigChunk::compare);
 590         optimize();
 591 }
 592
 593 void RTLIL::SigSpec::sort_and_unify()
 594 {
 595         expand();
 596         std::sort(chunks.begin(), chunks.end(), RTLIL::SigChunk::compare);
 597         for (size_t i = 1; i < chunks.size(); i++) {
 598                 RTLIL::SigChunk &ch1 = chunks[i-1];
 599                 RTLIL::SigChunk &ch2 = chunks[i];
 600                 if (!RTLIL::SigChunk::compare(ch1, ch2) && !RTLIL::SigChunk::compare(ch2, ch1)) {
 601                         chunks.erase(chunks.begin()+i);
 602                         width -= chunks[i].width;
 603                         i--;
 604                 }
 605         }
 606         optimize();
 607 }
 608
 609 void RTLIL::SigSpec::replace(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec &with)
 610 {
 611         replace(pattern, with, this);
 612 }
 613
 614 void RTLIL::SigSpec::replace(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec &with, RTLIL::SigSpec *other) const
 615 {
 616         int pos = 0, restart_pos = 0;
 617         assert(other == NULL || width == other->width);
 618         for (size_t i = 0; i < chunks.size(); i++) {
 619 restart:
 620                 const RTLIL::SigChunk &ch1 = chunks[i];
 621                 if (chunks[i].wire != NULL && pos >= restart_pos)
 622                         for (size_t j = 0, poff = 0; j < pattern.chunks.size(); j++) {
 623                                 const RTLIL::SigChunk &ch2 = pattern.chunks[j];
 624                                 assert(ch2.wire != NULL);
 625                                 if (ch1.wire == ch2.wire) {
 626                                         int lower = std::max(ch1.offset, ch2.offset);
 627                                         int upper = std::min(ch1.offset + ch1.width, ch2.offset + ch2.width);
 628                                         if (lower < upper) {
 629                                                 restart_pos = pos+upper-ch1.offset;
 630                                                 other->replace(pos+lower-ch1.offset, with.extract(poff+lower-ch2.offset, upper-lower));
 631                                                 goto restart;
 632                                         }
 633                                 }
 634                                 poff += ch2.width;
 635                         }
 636                 pos += chunks[i].width;
 637         }
 638         check();
 639 }
 640
 641 void RTLIL::SigSpec::remove(const RTLIL::SigSpec &pattern)
 642 {
 643         remove2(pattern, NULL);
 644 }
 645
 646 void RTLIL::SigSpec::remove(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other) const
 647 {
 648         RTLIL::SigSpec tmp = *this;
 649         tmp.remove2(pattern, other);
 650 }
 651
 652 void RTLIL::SigSpec::remove2(const RTLIL::SigSpec &pattern, RTLIL::SigSpec *other)
 653 {
 654         int pos = 0;
 655         assert(other == NULL || width == other->width);
 656         for (size_t i = 0; i < chunks.size(); i++) {
 657 restart:
 658                 const RTLIL::SigChunk &ch1 = chunks[i];
 659                 if (chunks[i].wire != NULL)
 660                         for (size_t j = 0; j < pattern.chunks.size(); j++) {
 661                                 const RTLIL::SigChunk &ch2 = pattern.chunks[j];
 662                                 assert(ch2.wire != NULL);
 663                                 if (ch1.wire == ch2.wire) {
 664                                         int lower = std::max(ch1.offset, ch2.offset);
 665                                         int upper = std::min(ch1.offset + ch1.width, ch2.offset + ch2.width);
 666                                         if (lower < upper) {
 667                                                 if (other)
 668                                                         other->remove(pos+lower-ch1.offset, upper-lower);
 669                                                 remove(pos+lower-ch1.offset, upper-lower);
 670                                                 if (i == chunks.size())
 671                                                         break;
 672                                                 goto restart;
 673                                         }
 674                                 }
 675                         }
 676                 pos += chunks[i].width;
 677         }
 678         check();
 679 }
 680
 681 RTLIL::SigSpec RTLIL::SigSpec::extract(RTLIL::SigSpec pattern, RTLIL::SigSpec *other) const
 682 {
 683         int pos = 0;
 684         RTLIL::SigSpec ret;
 685         pattern.sort_and_unify();
 686         assert(other == NULL || width == other->width);
 687         for (size_t i = 0; i < chunks.size(); i++) {
 688                 const RTLIL::SigChunk &ch1 = chunks[i];
 689                 if (chunks[i].wire != NULL)
 690                         for (size_t j = 0; j < pattern.chunks.size(); j++) {
 691                                 RTLIL::SigChunk &ch2 = pattern.chunks[j];
 692                                 assert(ch2.wire != NULL);
 693                                 if (ch1.wire == ch2.wire) {
 694                                         int lower = std::max(ch1.offset, ch2.offset);
 695                                         int upper = std::min(ch1.offset + ch1.width, ch2.offset + ch2.width);
 696                                         if (lower < upper) {
 697                                                 if (other)
 698                                                         ret.append(other->extract(pos+lower-ch1.offset, upper-lower));
 699                                                 else
 700                                                         ret.append(extract(pos+lower-ch1.offset, upper-lower));
 701                                         }
 702                                 }
 703                         }
 704                 pos += chunks[i].width;
 705         }
 706         ret.check();
 707         return ret;
 708 }
 709
 710 void RTLIL::SigSpec::replace(int offset, const RTLIL::SigSpec &with)
 711 {
 712         int pos = 0;
 713         assert(offset >= 0);
 714         assert(with.width >= 0);
 715         assert(offset+with.width <= width);
 716         remove(offset, with.width);
 717         for (size_t i = 0; i < chunks.size(); i++) {
 718                 if (pos == offset) {
 719                         chunks.insert(chunks.begin()+i, with.chunks.begin(), with.chunks.end());
 720                         width += with.width;
 721                         check();
 722                         return;
 723                 }
 724                 pos += chunks[i].width;
 725         }
 726         assert(pos == offset);
 727         chunks.insert(chunks.end(), with.chunks.begin(), with.chunks.end());
 728         width += with.width;
 729         check();
 730 }
 731
 732 void RTLIL::SigSpec::remove_const()
 733 {
 734         for (size_t i = 0; i < chunks.size(); i++) {
 735                 if (chunks[i].wire != NULL)
 736                         continue;
 737                 width -= chunks[i].width;
 738                 chunks.erase(chunks.begin() + (i--));
 739         }
 740         check();
 741 }
 742
 743 void RTLIL::SigSpec::remove(int offset, int length)
 744 {
 745         int pos = 0;
 746         assert(offset >= 0);
 747         assert(length >= 0);
 748         assert(offset+length <= width);
 749         for (size_t i = 0; i < chunks.size(); i++) {
 750                 int orig_width = chunks[i].width;
 751                 if (pos+chunks[i].width > offset && pos < offset+length) {
 752                         int off = offset - pos;
 753                         int len = length;
 754                         if (off < 0) {
 755                                 len += off;
 756                                 off = 0;
 757                         }
 758                         if (len > chunks[i].width-off)
 759                                 len = chunks[i].width-off;
 760                         RTLIL::SigChunk lsb_chunk = chunks[i].extract(0, off);
 761                         RTLIL::SigChunk msb_chunk = chunks[i].extract(off+len, chunks[i].width-off-len);
 762                         if (lsb_chunk.width == 0 && msb_chunk.width == 0) {
 763                                 chunks.erase(chunks.begin()+i);
 764                                 i--;
 765                         } else if (lsb_chunk.width == 0 && msb_chunk.width != 0) {
 766                                 chunks[i] = msb_chunk;
 767                         } else if (lsb_chunk.width != 0 && msb_chunk.width == 0) {
 768                                 chunks[i] = lsb_chunk;
 769                         } else if (lsb_chunk.width != 0 && msb_chunk.width != 0) {
 770                                 chunks[i] = lsb_chunk;
 771                                 chunks.insert(chunks.begin()+i+1, msb_chunk);
 772                                 i++;
 773                         } else
 774                                 assert(0);
 775                         width -= len;
 776                 }
 777                 pos += orig_width;
 778         }
 779         check();
 780 }
 781
 782 RTLIL::SigSpec RTLIL::SigSpec::extract(int offset, int length) const
 783 {
 784         int pos = 0;
 785         RTLIL::SigSpec ret;
 786         assert(offset >= 0);
 787         assert(length >= 0);
 788         assert(offset+length <= width);
 789         for (size_t i = 0; i < chunks.size(); i++) {
 790                 if (pos+chunks[i].width > offset && pos < offset+length) {
 791                         int off = offset - pos;
 792                         int len = length;
 793                         if (off < 0) {
 794                                 len += off;
 795                                 off = 0;
 796                         }
 797                         if (len > chunks[i].width-off)
 798                                 len = chunks[i].width-off;
 799                         ret.chunks.push_back(chunks[i].extract(off, len));
 800                         ret.width += len;
 801                         offset += len;
 802                         length -= len;
 803                 }
 804                 pos += chunks[i].width;
 805         }
 806         assert(length == 0);
 807         ret.check();
 808         return ret;
 809 }
 810
 811 void RTLIL::SigSpec::append(const RTLIL::SigSpec &signal)
 812 {
 813         for (size_t i = 0; i < signal.chunks.size(); i++) {
 814                 chunks.push_back(signal.chunks[i]);
 815                 width += signal.chunks[i].width;
 816         }
 817         check();
 818 }
 819
 820 bool RTLIL::SigSpec::combine(RTLIL::SigSpec signal, RTLIL::State freeState, bool override)
 821 {
 822         bool no_collisions = true;
 823
 824         assert(width == signal.width);
 825         expand();
 826         signal.expand();
 827
 828         for (size_t i = 0; i < chunks.size(); i++) {
 829                 bool self_free = chunks[i].wire == NULL && chunks[i].data.bits[0] == freeState;
 830                 bool other_free = signal.chunks[i].wire == NULL && signal.chunks[i].data.bits[0] == freeState;
 831                 if (!self_free && !other_free) {
 832                         if (override)
 833                                 chunks[i] = signal.chunks[i];
 834                         else
 835                                 chunks[i] = RTLIL::SigChunk(RTLIL::State::Sx, 1);
 836                         no_collisions = false;
 837                 }
 838                 if (self_free && !other_free)
 839                         chunks[i] = signal.chunks[i];
 840         }
 841
 842         optimize();
 843         return no_collisions;
 844 }
 845
 846 void RTLIL::SigSpec::extend(int width, bool is_signed)
 847 {
 848         if (this->width > width)
 849                 remove(width, this->width - width);
 850
 851         if (this->width < width) {
 852                 RTLIL::SigSpec padding = this->width > 0 ? extract(this->width - 1, 1) : RTLIL::SigSpec(RTLIL::State::S0);
 853                 if (!is_signed && padding != RTLIL::SigSpec(RTLIL::State::Sx) && padding != RTLIL::SigSpec(RTLIL::State::Sz) &&
 854                                 padding != RTLIL::SigSpec(RTLIL::State::Sa) && padding != RTLIL::SigSpec(RTLIL::State::Sm))
 855                         padding = RTLIL::SigSpec(RTLIL::State::S0);
 856                 while (this->width < width)
 857                         append(padding);
 858         }
 859
 860         optimize();
 861 }
 862
 863 void RTLIL::SigSpec::check() const
 864 {
 865         int w = 0;
 866         for (size_t i = 0; i < chunks.size(); i++) {
 867                 const RTLIL::SigChunk chunk = chunks[i];
 868                 if (chunk.wire == NULL) {
 869                         assert(chunk.offset == 0);
 870                         assert(chunk.data.bits.size() == (size_t)chunk.width);
 871                         assert(chunk.data.str.size() == 0 || chunk.data.str.size()*8 == chunk.data.bits.size());
 872                 } else {
 873                         assert(chunk.offset >= 0);
 874                         assert(chunk.width >= 0);
 875                         assert(chunk.offset + chunk.width <= chunk.wire->width);
 876                         assert(chunk.data.bits.size() == 0);
 877                         assert(chunk.data.str.size() == 0);
 878                 }
 879                 w += chunk.width;
 880         }
 881         assert(w == width);
 882 }
 883
 884 bool RTLIL::SigSpec::operator <(const RTLIL::SigSpec &other) const
 885 {
 886         if (width != other.width)
 887                 return width < other.width;
 888
 889         RTLIL::SigSpec a = *this, b = other;
 890         a.optimize();
 891         b.optimize();
 892
 893         if (a.chunks.size() != b.chunks.size())
 894                 return a.chunks.size() < b.chunks.size();
 895
 896         for (size_t i = 0; i < a.chunks.size(); i++)
 897                 if (a.chunks[i] != b.chunks[i])
 898                         return a.chunks[i] < b.chunks[i];
 899
 900         return false;
 901 }
 902
 903 bool RTLIL::SigSpec::operator ==(const RTLIL::SigSpec &other) const
 904 {
 905         if (width != other.width)
 906                 return false;
 907
 908         RTLIL::SigSpec a = *this, b = other;
 909         a.optimize();
 910         b.optimize();
 911
 912         if (a.chunks.size() != b.chunks.size())
 913                 return false;
 914
 915         for (size_t i = 0; i < a.chunks.size(); i++)
 916                 if (a.chunks[i] != b.chunks[i])
 917                         return false;
 918
 919         return true;
 920 }
 921
 922 bool RTLIL::SigSpec::operator !=(const RTLIL::SigSpec &other) const
 923 {
 924         if (*this == other)
 925                 return false;
 926         return true;
 927 }
 928
 929 bool RTLIL::SigSpec::is_fully_const() const
 930 {
 931         for (auto it = chunks.begin(); it != chunks.end(); it++)
 932                 if (it->width > 0 && it->wire != NULL)
 933                         return false;
 934         return true;
 935 }
 936
 937 bool RTLIL::SigSpec::is_fully_def() const
 938 {
 939         for (auto it = chunks.begin(); it != chunks.end(); it++) {
 940                 if (it->width > 0 && it->wire != NULL)
 941                         return false;
 942                 for (size_t i = 0; i < it->data.bits.size(); i++)
 943                         if (it->data.bits[i] != RTLIL::State::S0 && it->data.bits[i] != RTLIL::State::S1)
 944                                 return false;
 945         }
 946         return true;
 947 }
 948
 949 bool RTLIL::SigSpec::is_fully_undef() const
 950 {
 951         for (auto it = chunks.begin(); it != chunks.end(); it++) {
 952                 if (it->width > 0 && it->wire != NULL)
 953                         return false;
 954                 for (size_t i = 0; i < it->data.bits.size(); i++)
 955                         if (it->data.bits[i] != RTLIL::State::Sx && it->data.bits[i] != RTLIL::State::Sz)
 956                                 return false;
 957         }
 958         return true;
 959 }
 960
 961 bool RTLIL::SigSpec::has_marked_bits() const
 962 {
 963         for (auto it = chunks.begin(); it != chunks.end(); it++)
 964                 if (it->width > 0 && it->wire == NULL) {
 965                         for (size_t i = 0; i < it->data.bits.size(); i++)
 966                                 if (it->data.bits[i] == RTLIL::State::Sm)
 967                                         return true;
 968                 }
 969         return false;
 970 }
 971
 972 bool RTLIL::SigSpec::as_bool() const
 973 {
 974         assert(is_fully_const());
 975         SigSpec sig = *this;
 976         sig.optimize();
 977         if (sig.width)
 978                 return sig.chunks[0].data.as_bool();
 979         return false;
 980 }
 981
 982 int RTLIL::SigSpec::as_int() const
 983 {
 984         assert(is_fully_const());
 985         SigSpec sig = *this;
 986         sig.optimize();
 987         if (sig.width)
 988                 return sig.chunks[0].data.as_int();
 989         return 0;
 990 }
 991
 992 std::string RTLIL::SigSpec::as_string() const
 993 {
 994         std::string str;
 995         for (size_t i = chunks.size(); i > 0; i--) {
 996                 const RTLIL::SigChunk &chunk = chunks[i-1];
 997                 if (chunk.wire != NULL)
 998                         for (int j = 0; j < chunk.width; j++)
 999                                 str += "?";
1000                 else
1001                         str += chunk.data.as_string();
1002         }
1003         return str;
1004 }
1005
1006 RTLIL::Const RTLIL::SigSpec::as_const() const
1007 {
1008         assert(is_fully_const());
1009         SigSpec sig = *this;
1010         sig.optimize();
1011         if (sig.width)
1012                 return sig.chunks[0].data;
1013         return RTLIL::Const();
1014 }
1015
1016 bool RTLIL::SigSpec::match(std::string pattern) const
1017 {
1018         std::string str = as_string();
1019         assert(pattern.size() == str.size());
1020
1021         for (size_t i = 0; i < pattern.size(); i++) {
1022                 if (pattern[i] == ' ')
1023                         continue;
1024                 if (pattern[i] == '*') {
1025                         if (str[i] != 'z' && str[i] != 'x')
1026                                 return false;
1027                         continue;
1028                 }
1029                 if (pattern[i] != str[i])
1030                         return false;
1031         }
1032
1033         return true;
1034 }
1035
1036 RTLIL::CaseRule::~CaseRule()
1037 {
1038         for (auto it = switches.begin(); it != switches.end(); it++)
1039                 delete *it;
1040 }
1041
1042 void RTLIL::CaseRule::optimize()
1043 {
1044         for (auto it : switches)
1045                 it->optimize();
1046         for (auto &it : compare)
1047                 it.optimize();
1048         for (auto &it : actions) {
1049                 it.first.optimize();
1050                 it.second.optimize();
1051         }
1052 }
1053
1054 RTLIL::SwitchRule::~SwitchRule()
1055 {
1056         for (auto it = cases.begin(); it != cases.end(); it++)
1057                 delete *it;
1058 }
1059
1060 void RTLIL::SwitchRule::optimize()
1061 {
1062         signal.optimize();
1063         for (auto it : cases)
1064                 it->optimize();
1065 }
1066
1067 void RTLIL::SyncRule::optimize()
1068 {
1069         signal.optimize();
1070         for (auto &it : actions) {
1071                 it.first.optimize();
1072                 it.second.optimize();
1073         }
1074 }
1075
1076 RTLIL::Process::~Process()
1077 {
1078         for (auto it = syncs.begin(); it != syncs.end(); it++)
1079                 delete *it;
1080 }
1081
1082 void RTLIL::Process::optimize()
1083 {
1084         root_case.optimize();
1085         for (auto it : syncs)
1086                 it->optimize();
1087 }
1088