diff options
Diffstat (limited to 'kernel/utils.h')
| -rw-r--r-- | kernel/utils.h | 210 |
1 files changed, 210 insertions, 0 deletions
diff --git a/kernel/utils.h b/kernel/utils.h new file mode 100644 index 000000000..a03caf804 --- /dev/null +++ b/kernel/utils.h @@ -0,0 +1,210 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +// This file contains various c++ utility routines and helper classes that +// do not depend on any other components of yosys (except stuff like log_*). + +#include "kernel/yosys.h" + +#ifndef UTILS_H +#define UTILS_H + +// ------------------------------------------------ +// A map-like container, but you can save and restore the state +// ------------------------------------------------ + +template<typename Key, typename T, typename Compare = std::less<Key>> +struct stackmap +{ +private: + std::vector<std::map<Key, T*, Compare>> backup_state; + std::map<Key, T, Compare> current_state; + static T empty_tuple; + +public: + stackmap() { } + stackmap(const std::map<Key, T, Compare> &other) : current_state(other) { } + + template<typename Other> + void operator=(const Other &other) + { + for (auto &it : current_state) + if (!backup_state.empty() && backup_state.back().count(it.first) == 0) + backup_state.back()[it.first] = new T(it.second); + current_state.clear(); + + for (auto &it : other) + set(it.first, it.second); + } + + bool has(const Key &k) + { + return current_state.count(k) != 0; + } + + void set(const Key &k, const T &v) + { + if (!backup_state.empty() && backup_state.back().count(k) == 0) + backup_state.back()[k] = current_state.count(k) ? new T(current_state.at(k)) : nullptr; + current_state[k] = v; + } + + void unset(const Key &k) + { + if (!backup_state.empty() && backup_state.back().count(k) == 0) + backup_state.back()[k] = current_state.count(k) ? new T(current_state.at(k)) : nullptr; + current_state.erase(k); + } + + const T &get(const Key &k) + { + if (current_state.count(k) == 0) + return empty_tuple; + return current_state.at(k); + } + + void reset(const Key &k) + { + for (int i = SIZE(backup_state)-1; i >= 0; i--) + if (backup_state[i].count(k) != 0) { + if (backup_state[i].at(k) == nullptr) + current_state.erase(k); + else + current_state[k] = *backup_state[i].at(k); + return; + } + current_state.erase(k); + } + + const std::map<Key, T, Compare> &stdmap() + { + return current_state; + } + + void save() + { + backup_state.resize(backup_state.size()+1); + } + + void restore() + { + log_assert(!backup_state.empty()); + for (auto &it : backup_state.back()) + if (it.second != nullptr) { + current_state[it.first] = *it.second; + delete it.second; + } else + current_state.erase(it.first); + backup_state.pop_back(); + } + + ~stackmap() + { + while (!backup_state.empty()) + restore(); + } +}; + + +// ------------------------------------------------ +// A simple class for topological sorting +// ------------------------------------------------ + +template<typename T> +struct TopoSort +{ + bool analyze_loops, found_loops; + std::map<T, std::set<T>> database; + std::set<std::set<T>> loops; + std::vector<T> sorted; + + TopoSort() + { + analyze_loops = true; + found_loops = false; + } + + void node(T n) + { + if (database.count(n) == 0) + database[n] = std::set<T>(); + } + + void edge(T left, T right) + { + node(left); + database[right].insert(left); + } + + void sort_worker(const T &n, std::set<T> &marked_cells, std::set<T> &active_cells, std::vector<T> &active_stack) + { + if (active_cells.count(n)) { + found_loops = true; + if (analyze_loops) { + std::set<T> loop; + for (int i = SIZE(active_stack)-1; i >= 0; i--) { + loop.insert(active_stack[i]); + if (active_stack[i] == n) + break; + } + loops.insert(loop); + } + return; + } + + if (marked_cells.count(n)) + return; + + if (!database.at(n).empty()) + { + if (analyze_loops) + active_stack.push_back(n); + active_cells.insert(n); + + for (auto &left_n : database.at(n)) + sort_worker(left_n, marked_cells, active_cells, active_stack); + + if (analyze_loops) + active_stack.pop_back(); + active_cells.erase(n); + } + + marked_cells.insert(n); + sorted.push_back(n); + } + + bool sort() + { + loops.clear(); + sorted.clear(); + found_loops = false; + + std::set<T> marked_cells; + std::set<T> active_cells; + std::vector<T> active_stack; + + for (auto &it : database) + sort_worker(it.first, marked_cells, active_cells, active_stack); + + log_assert(SIZE(sorted) == SIZE(database)); + return !found_loops; + } +}; + +#endif |