kernel/utils.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 // This file contains various c++ utility routines and helper classes that
  21 // do not depend on any other components of yosys (except stuff like log_*).
  22
  23 #include "kernel/yosys.h"
  24
  25 #ifndef UTILS_H
  26 #define UTILS_H
  27
  28 YOSYS_NAMESPACE_BEGIN
  29
  30 // ------------------------------------------------
  31 // A map-like container, but you can save and restore the state
  32 // ------------------------------------------------
  33
  34 template<typename Key, typename T, typename OPS = hash_ops<Key>>
  35 struct stackmap
  36 {
  37 private:
  38         std::vector<dict<Key, T*, OPS>> backup_state;
  39         dict<Key, T, OPS> current_state;
  40         static T empty_tuple;
  41
  42 public:
  43         stackmap() { }
  44         stackmap(const dict<Key, T, OPS> &other) : current_state(other) { }
  45
  46         template<typename Other>
  47         void operator=(const Other &other)
  48         {
  49                 for (auto &it : current_state)
  50                         if (!backup_state.empty() && backup_state.back().count(it.first) == 0)
  51                                 backup_state.back()[it.first] = new T(it.second);
  52                 current_state.clear();
  53
  54                 for (auto &it : other)
  55                         set(it.first, it.second);
  56         }
  57
  58         bool has(const Key &k)
  59         {
  60                 return current_state.count(k) != 0;
  61         }
  62
  63         void set(const Key &k, const T &v)
  64         {
  65                 if (!backup_state.empty() && backup_state.back().count(k) == 0)
  66                         backup_state.back()[k] = current_state.count(k) ? new T(current_state.at(k)) : nullptr;
  67                 current_state[k] = v;
  68         }
  69
  70         void unset(const Key &k)
  71         {
  72                 if (!backup_state.empty() && backup_state.back().count(k) == 0)
  73                         backup_state.back()[k] = current_state.count(k) ? new T(current_state.at(k)) : nullptr;
  74                 current_state.erase(k);
  75         }
  76
  77         const T &get(const Key &k)
  78         {
  79                 if (current_state.count(k) == 0)
  80                         return empty_tuple;
  81                 return current_state.at(k);
  82         }
  83
  84         void reset(const Key &k)
  85         {
  86                 for (int i = GetSize(backup_state)-1; i >= 0; i--)
  87                         if (backup_state[i].count(k) != 0) {
  88                                 if (backup_state[i].at(k) == nullptr)
  89                                         current_state.erase(k);
  90                                 else
  91                                         current_state[k] = *backup_state[i].at(k);
  92                                 return;
  93                         }
  94                 current_state.erase(k);
  95         }
  96
  97         const dict<Key, T, OPS> &stdmap()
  98         {
  99                 return current_state;
 100         }
 101
 102         void save()
 103         {
 104                 backup_state.resize(backup_state.size()+1);
 105         }
 106
 107         void restore()
 108         {
 109                 log_assert(!backup_state.empty());
 110                 for (auto &it : backup_state.back())
 111                         if (it.second != nullptr) {
 112                                 current_state[it.first] = *it.second;
 113                                 delete it.second;
 114                         } else
 115                                 current_state.erase(it.first);
 116                 backup_state.pop_back();
 117         }
 118
 119         ~stackmap()
 120         {
 121                 while (!backup_state.empty())
 122                         restore();
 123         }
 124 };
 125
 126
 127 // ------------------------------------------------
 128 // A simple class for topological sorting
 129 // ------------------------------------------------
 130
 131 template<typename T, typename C = std::less<T>>
 132 struct TopoSort
 133 {
 134         bool analyze_loops, found_loops;
 135         std::map<T, std::set<T, C>, C> database;
 136         std::set<std::set<T, C>> loops;
 137         std::vector<T> sorted;
 138
 139         TopoSort()
 140         {
 141                 analyze_loops = true;
 142                 found_loops = false;
 143         }
 144
 145         void node(T n)
 146         {
 147                 if (database.count(n) == 0)
 148                         database[n] = std::set<T, C>();
 149         }
 150
 151         void edge(T left, T right)
 152         {
 153                 node(left);
 154                 database[right].insert(left);
 155         }
 156
 157         void sort_worker(const T &n, std::set<T, C> &marked_cells, std::set<T, C> &active_cells, std::vector<T> &active_stack)
 158         {
 159                 if (active_cells.count(n)) {
 160                         found_loops = true;
 161                         if (analyze_loops) {
 162                                 std::set<T, C> loop;
 163                                 for (int i = GetSize(active_stack)-1; i >= 0; i--) {
 164                                         loop.insert(active_stack[i]);
 165                                         if (active_stack[i] == n)
 166                                                 break;
 167                                 }
 168                                 loops.insert(loop);
 169                         }
 170                         return;
 171                 }
 172
 173                 if (marked_cells.count(n))
 174                         return;
 175
 176                 if (!database.at(n).empty())
 177                 {
 178                         if (analyze_loops)
 179                                 active_stack.push_back(n);
 180                         active_cells.insert(n);
 181
 182                         for (auto &left_n : database.at(n))
 183                                 sort_worker(left_n, marked_cells, active_cells, active_stack);
 184
 185                         if (analyze_loops)
 186                                 active_stack.pop_back();
 187                         active_cells.erase(n);
 188                 }
 189
 190                 marked_cells.insert(n);
 191                 sorted.push_back(n);
 192         }
 193
 194         bool sort()
 195         {
 196                 loops.clear();
 197                 sorted.clear();
 198                 found_loops = false;
 199
 200                 std::set<T, C> marked_cells;
 201                 std::set<T, C> active_cells;
 202                 std::vector<T> active_stack;
 203
 204                 for (auto &it : database)
 205                         sort_worker(it.first, marked_cells, active_cells, active_stack);
 206
 207                 log_assert(GetSize(sorted) == GetSize(database));
 208                 return !found_loops;
 209         }
 210 };
 211
 212 YOSYS_NAMESPACE_END
 213
 214 #endif