/* * yosys -- Yosys Open SYnthesis Suite * * Copyright (C) 2012 Clifford Wolf * * 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 YOSYS_NAMESPACE_BEGIN // ------------------------------------------------ // A map-like container, but you can save and restore the state // ------------------------------------------------ template> struct stackmap { private: std::vector> backup_state; std::map current_state; static T empty_tuple; public: stackmap() { } stackmap(const std::map &other) : current_state(other) { } template 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 = GetSize(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 &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 struct TopoSort { bool analyze_loops, found_loops; std::map> database; std::set> loops; std::vector sorted; TopoSort() { analyze_loops = true; found_loops = false; } void node(T n) { if (database.count(n) == 0) database[n] = std::set(); } void edge(T left, T right) { node(left); database[right].insert(left); } void sort_worker(const T &n, std::set &marked_cells, std::set &active_cells, std::vector &active_stack) { if (active_cells.count(n)) { found_loops = true; if (analyze_loops) { std::set loop; for (int i = GetSize(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 marked_cells; std::set active_cells; std::vector active_stack; for (auto &it : database) sort_worker(it.first, marked_cells, active_cells, active_stack); log_assert(GetSize(sorted) == GetSize(database)); return !found_loops; } }; YOSYS_NAMESPACE_END #endif