kernel/sigtools.h

   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 #ifndef SIGTOOLS_H
  21 #define SIGTOOLS_H
  22
  23 #include "kernel/rtlil.h"
  24 #include "kernel/log.h"
  25 #include <assert.h>
  26 #include <set>
  27
  28 struct SigPool
  29 {
  30         typedef std::pair<RTLIL::Wire*,int> bitDef_t;
  31         std::set<bitDef_t> bits;
  32
  33         void clear()
  34         {
  35                 bits.clear();
  36         }
  37
  38         void add(RTLIL::SigSpec sig)
  39         {
  40                 sig.expand();
  41                 for (auto &c : sig.chunks) {
  42                         if (c.wire == NULL)
  43                                 continue;
  44                         assert(c.width == 1);
  45                         bitDef_t bit(c.wire, c.offset);
  46                         bits.insert(bit);
  47                 }
  48         }
  49
  50         void add(const SigPool &other)
  51         {
  52                 for (auto &bit : other.bits)
  53                         bits.insert(bit);
  54         }
  55
  56         void del(RTLIL::SigSpec sig)
  57         {
  58                 sig.expand();
  59                 for (auto &c : sig.chunks) {
  60                         if (c.wire == NULL)
  61                                 continue;
  62                         assert(c.width == 1);
  63                         bitDef_t bit(c.wire, c.offset);
  64                         bits.erase(bit);
  65                 }
  66         }
  67
  68         void del(const SigPool &other)
  69         {
  70                 for (auto &bit : other.bits)
  71                         bits.insert(bit);
  72         }
  73
  74         void expand(RTLIL::SigSpec from, RTLIL::SigSpec to)
  75         {
  76                 from.expand();
  77                 to.expand();
  78                 assert(from.chunks.size() == to.chunks.size());
  79                 for (size_t i = 0; i < from.chunks.size(); i++) {
  80                         bitDef_t bit_from(from.chunks[i].wire, from.chunks[i].offset);
  81                         bitDef_t bit_to(to.chunks[i].wire, to.chunks[i].offset);
  82                         if (bit_from.first == NULL || bit_to.first == NULL)
  83                                 continue;
  84                         if (bits.count(bit_from) > 0)
  85                                 bits.insert(bit_to);
  86                 }
  87         }
  88
  89         RTLIL::SigSpec extract(RTLIL::SigSpec sig)
  90         {
  91                 RTLIL::SigSpec result;
  92                 sig.expand();
  93                 for (auto &c : sig.chunks) {
  94                         if (c.wire == NULL)
  95                                 continue;
  96                         bitDef_t bit(c.wire, c.offset);
  97                         if (bits.count(bit) > 0)
  98                                 result.append(c);
  99                 }
 100                 return result;
 101         }
 102
 103         RTLIL::SigSpec remove(RTLIL::SigSpec sig)
 104         {
 105                 RTLIL::SigSpec result;
 106                 sig.expand();
 107                 for (auto &c : sig.chunks) {
 108                         if (c.wire == NULL)
 109                                 continue;
 110                         bitDef_t bit(c.wire, c.offset);
 111                         if (bits.count(bit) == 0)
 112                                 result.append(c);
 113                 }
 114                 return result;
 115         }
 116
 117         bool check_any(RTLIL::SigSpec sig)
 118         {
 119                 sig.expand();
 120                 for (auto &c : sig.chunks) {
 121                         if (c.wire == NULL)
 122                                 continue;
 123                         bitDef_t bit(c.wire, c.offset);
 124                         if (bits.count(bit) != 0)
 125                                 return true;
 126                 }
 127                 return false;
 128         }
 129
 130         bool check_all(RTLIL::SigSpec sig)
 131         {
 132                 sig.expand();
 133                 for (auto &c : sig.chunks) {
 134                         if (c.wire == NULL)
 135                                 continue;
 136                         bitDef_t bit(c.wire, c.offset);
 137                         if (bits.count(bit) == 0)
 138                                 return false;
 139                 }
 140                 return true;
 141         }
 142
 143         RTLIL::SigSpec export_one()
 144         {
 145                 RTLIL::SigSpec sig;
 146                 for (auto &bit : bits) {
 147                         sig.append(RTLIL::SigSpec(bit.first, 1, bit.second));
 148                         break;
 149                 }
 150                 return sig;
 151         }
 152
 153         RTLIL::SigSpec export_all()
 154         {
 155                 RTLIL::SigSpec sig;
 156                 for (auto &bit : bits)
 157                         sig.append(RTLIL::SigSpec(bit.first, 1, bit.second));
 158                 sig.sort_and_unify();
 159                 return sig;
 160         }
 161
 162         size_t size()
 163         {
 164                 return bits.size();
 165         }
 166 };
 167
 168 template <typename T>
 169 struct SigSet
 170 {
 171         typedef std::pair<RTLIL::Wire*,int> bitDef_t;
 172         std::map<bitDef_t, std::set<T>> bits;
 173
 174         void clear()
 175         {
 176                 bits.clear();
 177         }
 178
 179         void insert(RTLIL::SigSpec sig, T data)
 180         {
 181                 sig.expand();
 182                 for (auto &c : sig.chunks) {
 183                         if (c.wire == NULL)
 184                                 continue;
 185                         assert(c.width == 1);
 186                         bitDef_t bit(c.wire, c.offset);
 187                         bits[bit].insert(data);
 188                 }
 189         }
 190
 191         void insert(RTLIL::SigSpec sig, const std::set<T> &data)
 192         {
 193                 sig.expand();
 194                 for (auto &c : sig.chunks) {
 195                         if (c.wire == NULL)
 196                                 continue;
 197                         assert(c.width == 1);
 198                         bitDef_t bit(c.wire, c.offset);
 199                         bits[bit].insert(data.begin(), data.end());
 200                 }
 201         }
 202
 203         void erase(RTLIL::SigSpec sig)
 204         {
 205                 sig.expand();
 206                 for (auto &c : sig.chunks) {
 207                         if (c.wire == NULL)
 208                                 continue;
 209                         assert(c.width == 1);
 210                         bitDef_t bit(c.wire, c.offset);
 211                         bits[bit].clear();
 212                 }
 213         }
 214
 215         void erase(RTLIL::SigSpec sig, T data)
 216         {
 217                 sig.expand();
 218                 for (auto &c : sig.chunks) {
 219                         if (c.wire == NULL)
 220                                 continue;
 221                         assert(c.width == 1);
 222                         bitDef_t bit(c.wire, c.offset);
 223                         bits[bit].erase(data);
 224                 }
 225         }
 226
 227         void erase(RTLIL::SigSpec sig, const std::set<T> &data)
 228         {
 229                 sig.expand();
 230                 for (auto &c : sig.chunks) {
 231                         if (c.wire == NULL)
 232                                 continue;
 233                         assert(c.width == 1);
 234                         bitDef_t bit(c.wire, c.offset);
 235                         bits[bit].erase(data.begin(), data.end());
 236                 }
 237         }
 238
 239         void find(RTLIL::SigSpec sig, std::set<T> &result)
 240         {
 241                 sig.expand();
 242                 for (auto &c : sig.chunks) {
 243                         if (c.wire == NULL)
 244                                 continue;
 245                         assert(c.width == 1);
 246                         bitDef_t bit(c.wire, c.offset);
 247                         for (auto &data : bits[bit])
 248                                 result.insert(data);
 249                 }
 250         }
 251
 252         std::set<T> find(RTLIL::SigSpec sig)
 253         {
 254                 std::set<T> result;
 255                 find(sig, result);
 256                 return result;
 257         }
 258
 259         bool has(RTLIL::SigSpec sig)
 260         {
 261                 sig.expand();
 262                 for (auto &c : sig.chunks) {
 263                         if (c.wire == NULL)
 264                                 continue;
 265                         assert(c.width == 1);
 266                         bitDef_t bit(c.wire, c.offset);
 267                         if (bits.count(bit))
 268                                 return true;
 269                 }
 270                 return false;
 271         }
 272 };
 273
 274 struct SigMap
 275 {
 276         typedef std::pair<RTLIL::Wire*,int> bitDef_t;
 277
 278         struct shared_bit_data_t {
 279                 RTLIL::SigChunk chunk;
 280                 std::set<bitDef_t> bits;
 281         };
 282
 283         std::map<bitDef_t, shared_bit_data_t*> bits;
 284
 285         SigMap(RTLIL::Module *module = NULL)
 286         {
 287                 if (module != NULL)
 288                         set(module);
 289         }
 290
 291         SigMap(const SigMap &other)
 292         {
 293                 copy(other);
 294         }
 295
 296         const SigMap &operator=(const SigMap &other)
 297         {
 298                 copy(other);
 299                 return *this;
 300         }
 301
 302         void copy(const SigMap &other)
 303         {
 304                 clear();
 305                 for (auto &bit : other.bits) {
 306                         bits[bit.first] = new shared_bit_data_t;
 307                         bits[bit.first]->chunk = bit.second->chunk;
 308                         bits[bit.first]->bits = bit.second->bits;
 309                 }
 310         }
 311
 312         void swap(SigMap &other)
 313         {
 314                 bits.swap(other.bits);
 315         }
 316
 317         ~SigMap()
 318         {
 319                 clear();
 320         }
 321
 322         void clear()
 323         {
 324                 std::set<shared_bit_data_t*> all_bd_ptr;
 325                 for (auto &it : bits)
 326                         all_bd_ptr.insert(it.second);
 327                 for (auto bd_ptr : all_bd_ptr)
 328                         delete bd_ptr;
 329                 bits.clear();
 330         }
 331
 332         void set(RTLIL::Module *module)
 333         {
 334                 clear();
 335                 for (auto &it : module->connections)
 336                         add(it.first, it.second);
 337         }
 338
 339         // internal helper function
 340         void register_bit(const RTLIL::SigChunk &c)
 341         {
 342                 assert(c.width == 1);
 343                 bitDef_t bit(c.wire, c.offset);
 344                 if (c.wire && bits.count(bit) == 0) {
 345                         shared_bit_data_t *bd = new shared_bit_data_t;
 346                         bd->chunk = c;
 347                         bd->bits.insert(bit);
 348                         bits[bit] = bd;
 349                 }
 350         }
 351
 352         // internal helper function
 353         void unregister_bit(const RTLIL::SigChunk &c)
 354         {
 355                 assert(c.width == 1);
 356                 bitDef_t bit(c.wire, c.offset);
 357                 if (c.wire && bits.count(bit) > 0) {
 358                         shared_bit_data_t *bd = bits[bit];
 359                         bd->bits.erase(bit);
 360                         if (bd->bits.size() == 0)
 361                                 delete bd;
 362                         bits.erase(bit);
 363                 }
 364         }
 365
 366         // internal helper function
 367         void merge_bit(const RTLIL::SigChunk &c1, const RTLIL::SigChunk &c2)
 368         {
 369                 assert(c1.wire != NULL && c2.wire != NULL);
 370                 assert(c1.width == 1 && c2.width == 1);
 371
 372                 bitDef_t b1(c1.wire, c1.offset);
 373                 bitDef_t b2(c2.wire, c2.offset);
 374
 375                 shared_bit_data_t *bd1 = bits[b1];
 376                 shared_bit_data_t *bd2 = bits[b2];
 377                 assert(bd1 != NULL && bd2 != NULL);
 378
 379                 if (bd1 == bd2)
 380                         return;
 381
 382                 if (bd1->bits.size() < bd2->bits.size())
 383                 {
 384                         for (auto &bit : bd1->bits)
 385                                 bits[bit] = bd2;
 386                         bd2->bits.insert(bd1->bits.begin(), bd1->bits.end());
 387                         delete bd1;
 388                 }
 389                 else
 390                 {
 391                         bd1->chunk = bd2->chunk;
 392                         for (auto &bit : bd2->bits)
 393                                 bits[bit] = bd1;
 394                         bd1->bits.insert(bd2->bits.begin(), bd2->bits.end());
 395                         delete bd2;
 396                 }
 397         }
 398
 399         // internal helper function
 400         void set_bit(const RTLIL::SigChunk &c1, const RTLIL::SigChunk &c2)
 401         {
 402                 assert(c1.wire != NULL);
 403                 assert(c1.width == 1 && c2.width == 1);
 404                 bitDef_t bit(c1.wire, c1.offset);
 405                 assert(bits.count(bit) > 0);
 406                 bits[bit]->chunk = c2;
 407         }
 408
 409         // internal helper function
 410         void map_bit(RTLIL::SigChunk &c)
 411         {
 412                 assert(c.width == 1);
 413                 bitDef_t bit(c.wire, c.offset);
 414                 if (c.wire && bits.count(bit) > 0)
 415                         c = bits[bit]->chunk;
 416         }
 417
 418         void add(RTLIL::SigSpec from, RTLIL::SigSpec to)
 419         {
 420                 from.expand();
 421                 to.expand();
 422
 423                 assert(from.chunks.size() == to.chunks.size());
 424                 for (size_t i = 0; i < from.chunks.size(); i++)
 425                 {
 426                         RTLIL::SigChunk &cf = from.chunks[i];
 427                         RTLIL::SigChunk &ct = to.chunks[i];
 428
 429                         if (cf.wire == NULL)
 430                                 continue;
 431
 432                         register_bit(cf);
 433                         register_bit(ct);
 434
 435                         if (ct.wire != NULL)
 436                                 merge_bit(cf, ct);
 437                         else
 438                                 set_bit(cf, ct);
 439                 }
 440         }
 441
 442         void add(RTLIL::SigSpec sig)
 443         {
 444                 sig.expand();
 445                 for (size_t i = 0; i < sig.chunks.size(); i++)
 446                 {
 447                         RTLIL::SigChunk &c = sig.chunks[i];
 448                         if (c.wire != NULL) {
 449                                 register_bit(c);
 450                                 set_bit(c, c);
 451                         }
 452                 }
 453         }
 454
 455         void del(RTLIL::SigSpec sig)
 456         {
 457                 sig.expand();
 458                 for (auto &c : sig.chunks)
 459                         unregister_bit(c);
 460         }
 461
 462         void apply(RTLIL::SigSpec &sig)
 463         {
 464                 sig.expand();
 465                 for (auto &c : sig.chunks)
 466                         map_bit(c);
 467                 sig.optimize();
 468         }
 469
 470         RTLIL::SigSpec operator()(RTLIL::SigSpec sig)
 471         {
 472                 apply(sig);
 473                 return sig;
 474         }
 475 };
 476
 477 #endif /* SIGTOOLS_H */