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