diff options
author | gatecat <gatecat@ds0.me> | 2021-03-01 10:36:23 +0000 |
---|---|---|
committer | gatecat <gatecat@ds0.me> | 2021-03-04 10:29:36 +0000 |
commit | 7a546b15541a9f3b5be77f13250f3755d4f66e91 (patch) | |
tree | 973ff58f3e280babd1e123327bf47a461b9dc7dc | |
parent | d0772ce1e384609835ef3d918752038d42a8ce34 (diff) | |
download | nextpnr-7a546b15541a9f3b5be77f13250f3755d4f66e91.tar.gz nextpnr-7a546b15541a9f3b5be77f13250f3755d4f66e91.tar.bz2 nextpnr-7a546b15541a9f3b5be77f13250f3755d4f66e91.zip |
timing: Add topological sort from Yosys
Signed-off-by: gatecat <gatecat@ds0.me>
-rw-r--r-- | common/timing.cc | 40 | ||||
-rw-r--r-- | common/timing.h | 8 | ||||
-rw-r--r-- | common/util.h | 82 |
3 files changed, 130 insertions, 0 deletions
diff --git a/common/timing.cc b/common/timing.cc index 785f9e7b..f642153f 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -34,6 +34,7 @@ void TimingAnalyser::setup() { init_ports(); get_cell_delays(); + topo_sort(); } void TimingAnalyser::init_ports() @@ -43,6 +44,7 @@ void TimingAnalyser::init_ports() CellInfo *ci = cell.second; for (auto port : sorted_ref(ci->ports)) { auto &data = ports[CellPortKey(ci->name, port.first)]; + data.type = port.second.type; data.cell_port = CellPortKey(ci->name, port.first); } } @@ -118,6 +120,44 @@ void TimingAnalyser::get_cell_delays() } } +void TimingAnalyser::topo_sort() +{ + TopoSort<CellPortKey> topo; + for (auto &port : ports) { + auto &pd = port.second; + // All ports are nodes + topo.node(port.first); + if (pd.type == PORT_IN) { + // inputs: combinational arcs through the cell are edges + for (auto &arc : pd.cell_arcs) { + if (arc.type != CellArc::COMBINATIONAL) + continue; + topo.edge(port.first, CellPortKey(port.first.cell, arc.other_port)); + } + } else if (pd.type == PORT_OUT) { + // output: routing arcs are edges + const NetInfo *pn = port_info(port.first).net; + if (pn != nullptr) { + for (auto &usr : pn->users) + topo.edge(port.first, CellPortKey(usr)); + } + } + } + bool no_loops = topo.sort(); + if (!no_loops) { + log_info("Found %d combinational loops:\n", int(topo.loops.size())); + int i = 0; + for (auto &loop : topo.loops) { + log_info(" loop %d:\n", ++i); + for (auto &port : loop) { + log_info(" %s.%s (%s)\n", ctx->nameOf(port.cell), ctx->nameOf(port.port), + ctx->nameOf(port_info(port).net)); + } + } + } + std::swap(topological_order, topo.sorted); +} + CellInfo *TimingAnalyser::cell_info(const CellPortKey &key) { return ctx->cells.at(key.cell).get(); } PortInfo &TimingAnalyser::port_info(const CellPortKey &key) { return ctx->cells.at(key.cell)->ports.at(key.port); } diff --git a/common/timing.h b/common/timing.h index 9c15911d..e07dc105 100644 --- a/common/timing.h +++ b/common/timing.h @@ -45,6 +45,10 @@ struct CellPortKey } }; inline bool operator==(const CellPortKey &other) const { return (cell == other.cell) && (port == other.port); } + inline bool operator<(const CellPortKey &other) const + { + return cell == other.cell ? port < other.port : cell < other.cell; + } }; struct NetPortKey @@ -104,6 +108,7 @@ struct TimingAnalyser private: void init_ports(); void get_cell_delays(); + void topo_sort(); // To avoid storing the domain tag structure (which could get large when considering more complex constrained tag // cases), assign each domain an ID and use that instead typedef int domain_id_t; @@ -153,6 +158,7 @@ struct TimingAnalyser { CellPortKey cell_port; NetPortKey net_port; + PortType type; // per domain timings std::unordered_map<domain_id_t, PortDomainData> domains; // cell timing arcs to (outputs)/from (inputs) from this port @@ -168,6 +174,8 @@ struct TimingAnalyser std::unordered_map<ClockDomainKey, domain_id_t, ClockDomainKey::Hash> domain_to_id; std::vector<ClockDomainKey> id_to_domain; + std::vector<CellPortKey> topological_order; + Context *ctx; }; diff --git a/common/util.h b/common/util.h index 55718344..ce2b4da1 100644 --- a/common/util.h +++ b/common/util.h @@ -181,6 +181,88 @@ template <typename ForwardRange> inline auto get_only_value(ForwardRange r) return get_only_value(b, e); } +// From Yosys +// https://github.com/YosysHQ/yosys/blob/0fb4224ebca86156a1296b9210116d9a9cbebeed/kernel/utils.h#L131 +template <typename T, typename C = std::less<T>> struct TopoSort +{ + bool analyze_loops, found_loops; + std::map<T, std::set<T, C>, C> database; + std::set<std::set<T, C>> 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, C>(); + } + + void edge(T left, T right) + { + node(left); + database[right].insert(left); + } + + void sort_worker(const T &n, std::set<T, C> &marked_cells, std::set<T, C> &active_cells, + std::vector<T> &active_stack) + { + if (active_cells.count(n)) { + found_loops = true; + if (analyze_loops) { + std::set<T, C> loop; + for (int i = int(active_stack.size()) - 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, C> marked_cells; + std::set<T, C> active_cells; + std::vector<T> active_stack; + + for (auto &it : database) + sort_worker(it.first, marked_cells, active_cells, active_stack); + + NPNR_ASSERT(sorted.size() == database.size()); + return !found_loops; + } +}; + NEXTPNR_NAMESPACE_END #endif |