aboutsummaryrefslogtreecommitdiffstats
path: root/common/route
diff options
context:
space:
mode:
Diffstat (limited to 'common/route')
-rw-r--r--common/route/router1.cc1175
-rw-r--r--common/route/router1.h45
-rw-r--r--common/route/router2.cc1499
-rw-r--r--common/route/router2.h66
4 files changed, 2785 insertions, 0 deletions
diff --git a/common/route/router1.cc b/common/route/router1.cc
new file mode 100644
index 00000000..98132116
--- /dev/null
+++ b/common/route/router1.cc
@@ -0,0 +1,1175 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2018 Claire Xenia Wolf <claire@yosyshq.com>
+ *
+ * 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.
+ *
+ */
+
+#include <chrono>
+#include <cmath>
+#include <queue>
+
+#include "log.h"
+#include "router1.h"
+#include "scope_lock.h"
+#include "timing.h"
+
+namespace {
+
+USING_NEXTPNR_NAMESPACE
+
+struct arc_key
+{
+ NetInfo *net_info;
+ // logical user cell port index
+ store_index<PortRef> user_idx;
+ // physical index into cell->bel pin mapping (usually 0)
+ unsigned phys_idx;
+
+ bool operator==(const arc_key &other) const
+ {
+ return (net_info == other.net_info) && (user_idx == other.user_idx) && (phys_idx == other.phys_idx);
+ }
+ bool operator<(const arc_key &other) const
+ {
+ return net_info == other.net_info
+ ? (user_idx == other.user_idx ? phys_idx < other.phys_idx : user_idx < other.user_idx)
+ : net_info->name < other.net_info->name;
+ }
+
+ unsigned int hash() const
+ {
+ std::size_t seed = std::hash<NetInfo *>()(net_info);
+ seed ^= user_idx.hash() + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ seed ^= std::hash<int>()(phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ return seed;
+ }
+};
+
+struct arc_entry
+{
+ arc_key arc;
+ delay_t pri;
+ int randtag = 0;
+
+ struct Less
+ {
+ bool operator()(const arc_entry &lhs, const arc_entry &rhs) const noexcept
+ {
+ if (lhs.pri != rhs.pri)
+ return lhs.pri < rhs.pri;
+ return lhs.randtag < rhs.randtag;
+ }
+ };
+};
+
+struct QueuedWire
+{
+ WireId wire;
+ PipId pip;
+
+ delay_t delay = 0, penalty = 0, bonus = 0, togo = 0;
+ int randtag = 0;
+
+ struct Greater
+ {
+ bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept
+ {
+ delay_t l = lhs.delay + lhs.penalty + lhs.togo;
+ delay_t r = rhs.delay + rhs.penalty + rhs.togo;
+ NPNR_ASSERT(l >= 0);
+ NPNR_ASSERT(r >= 0);
+ l -= lhs.bonus;
+ r -= rhs.bonus;
+ return l == r ? lhs.randtag > rhs.randtag : l > r;
+ }
+ };
+};
+
+struct Router1
+{
+ Context *ctx;
+ const Router1Cfg &cfg;
+
+ std::priority_queue<arc_entry, std::vector<arc_entry>, arc_entry::Less> arc_queue;
+ dict<WireId, pool<arc_key>> wire_to_arcs;
+ dict<arc_key, pool<WireId>> arc_to_wires;
+ pool<arc_key> queued_arcs;
+
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
+
+ dict<WireId, int> wireScores;
+ dict<NetInfo *, int, hash_ptr_ops> netScores;
+
+ int arcs_with_ripup = 0;
+ int arcs_without_ripup = 0;
+ bool ripup_flag;
+
+ TimingAnalyser tmg;
+
+ bool timing_driven = true;
+
+ Router1(Context *ctx, const Router1Cfg &cfg) : ctx(ctx), cfg(cfg), tmg(ctx)
+ {
+ timing_driven = ctx->setting<bool>("timing_driven");
+ tmg.setup();
+ tmg.run();
+ }
+
+ void arc_queue_insert(const arc_key &arc, WireId src_wire, WireId dst_wire)
+ {
+ if (queued_arcs.count(arc))
+ return;
+
+ delay_t pri = ctx->estimateDelay(src_wire, dst_wire) *
+ (100 * tmg.get_criticality(CellPortKey(arc.net_info->users.at(arc.user_idx))));
+
+ arc_entry entry;
+ entry.arc = arc;
+ entry.pri = pri;
+ entry.randtag = ctx->rng();
+
+#if 0
+ if (ctx->debug)
+ log("[arc_queue_insert] %s (%d) %s %s [%d %d]\n", ctx->nameOf(entry.arc.net_info), entry.arc.user_idx,
+ ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire), (int)entry.pri, entry.randtag);
+#endif
+
+ arc_queue.push(entry);
+ queued_arcs.insert(arc);
+ }
+
+ void arc_queue_insert(const arc_key &arc)
+ {
+ if (queued_arcs.count(arc))
+ return;
+
+ NetInfo *net_info = arc.net_info;
+ auto user_idx = arc.user_idx;
+ unsigned phys_idx = arc.phys_idx;
+
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx], phys_idx);
+
+ arc_queue_insert(arc, src_wire, dst_wire);
+ }
+
+ arc_key arc_queue_pop()
+ {
+ arc_entry entry = arc_queue.top();
+
+#if 0
+ if (ctx->debug)
+ log("[arc_queue_pop] %s (%d) [%d %d]\n", ctx->nameOf(entry.arc.net_info), entry.arc.user_idx,
+ (int)entry.pri, entry.randtag);
+#endif
+
+ arc_queue.pop();
+ queued_arcs.erase(entry.arc);
+ return entry.arc;
+ }
+
+ void ripup_net(NetInfo *net)
+ {
+ if (ctx->debug)
+ log(" ripup net %s\n", ctx->nameOf(net));
+
+ netScores[net]++;
+
+ std::vector<WireId> wires;
+ for (auto &it : net->wires)
+ wires.push_back(it.first);
+
+ ctx->sorted_shuffle(wires);
+
+ for (WireId w : wires) {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
+
+ ctx->sorted_shuffle(arcs);
+
+ for (auto &it : arcs)
+ arc_queue_insert(it);
+
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
+ }
+
+ ripup_flag = true;
+ }
+
+ void ripup_wire(WireId wire, int extra_indent = 0)
+ {
+ if (ctx->debug)
+ log(" ripup wire %s\n", ctx->nameOfWire(wire));
+
+ WireId w = ctx->getConflictingWireWire(wire);
+
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingWireNet(wire);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
+
+ ctx->sorted_shuffle(arcs);
+
+ for (auto &it : arcs)
+ arc_queue_insert(it);
+
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
+ }
+
+ ripup_flag = true;
+ }
+
+ void ripup_pip(PipId pip)
+ {
+ if (ctx->debug)
+ log(" ripup pip %s\n", ctx->nameOfPip(pip));
+
+ WireId w = ctx->getConflictingPipWire(pip);
+
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingPipNet(pip);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
+
+ ctx->sorted_shuffle(arcs);
+
+ for (auto &it : arcs)
+ arc_queue_insert(it);
+
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
+ }
+
+ ripup_flag = true;
+ }
+
+ bool skip_net(NetInfo *net_info)
+ {
+#ifdef ARCH_ECP5
+ // ECP5 global nets currently appear part-unrouted due to arch database limitations
+ // Don't touch them in the router
+ if (net_info->is_global)
+ return true;
+#endif
+ if (net_info->driver.cell == nullptr)
+ return true;
+
+ return false;
+ }
+
+ void check()
+ {
+ pool<arc_key> valid_arcs;
+
+ for (auto &net_it : ctx->nets) {
+ NetInfo *net_info = net_it.second.get();
+ pool<WireId> valid_wires_for_net;
+
+ if (skip_net(net_info))
+ continue;
+
+#if 0
+ if (ctx->debug)
+ log("[check] net: %s\n", ctx->nameOf(net_info));
+#endif
+
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ log_assert(src_wire != WireId());
+
+ for (auto user : net_info->users.enumerate()) {
+ unsigned phys_idx = 0;
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
+ log_assert(dst_wire != WireId());
+
+ arc_key arc;
+ arc.net_info = net_info;
+ arc.user_idx = user.index;
+ arc.phys_idx = phys_idx++;
+ valid_arcs.insert(arc);
+#if 0
+ if (ctx->debug)
+ log("[check] arc: %s %s\n", ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire));
+#endif
+
+ for (WireId wire : arc_to_wires[arc]) {
+#if 0
+ if (ctx->debug)
+ log("[check] wire: %s\n", ctx->nameOfWire(wire));
+#endif
+ valid_wires_for_net.insert(wire);
+ log_assert(wire_to_arcs[wire].count(arc));
+ log_assert(net_info->wires.count(wire));
+ }
+ }
+ }
+
+ for (auto &it : net_info->wires) {
+ WireId w = it.first;
+ log_assert(valid_wires_for_net.count(w));
+ }
+ }
+
+ for (auto &it : wire_to_arcs) {
+ for (auto &arc : it.second)
+ log_assert(valid_arcs.count(arc));
+ }
+
+ for (auto &it : arc_to_wires) {
+ log_assert(valid_arcs.count(it.first));
+ }
+ }
+
+ void setup()
+ {
+ dict<WireId, NetInfo *> src_to_net;
+ dict<WireId, arc_key> dst_to_arc;
+
+ std::vector<IdString> net_names;
+ for (auto &net_it : ctx->nets)
+ net_names.push_back(net_it.first);
+
+ ctx->sorted_shuffle(net_names);
+
+ for (IdString net_name : net_names) {
+ NetInfo *net_info = ctx->nets.at(net_name).get();
+
+ if (skip_net(net_info))
+ continue;
+
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+
+ if (src_wire == WireId())
+ log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(net_info->driver.port),
+ ctx->nameOf(net_info->driver.cell));
+
+ if (src_to_net.count(src_wire))
+ log_error("Found two nets with same source wire %s: %s vs %s\n", ctx->nameOfWire(src_wire),
+ ctx->nameOf(net_info), ctx->nameOf(src_to_net.at(src_wire)));
+
+ if (dst_to_arc.count(src_wire))
+ log_error("Wire %s is used as source and sink in different nets: %s vs %s (%d)\n",
+ ctx->nameOfWire(src_wire), ctx->nameOf(net_info),
+ ctx->nameOf(dst_to_arc.at(src_wire).net_info), dst_to_arc.at(src_wire).user_idx.idx());
+
+ for (auto user : net_info->users.enumerate()) {
+ unsigned phys_idx = 0;
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
+ arc_key arc;
+ arc.net_info = net_info;
+ arc.user_idx = user.index;
+ arc.phys_idx = phys_idx++;
+
+ if (dst_to_arc.count(dst_wire)) {
+ if (dst_to_arc.at(dst_wire).net_info == net_info)
+ continue;
+ log_error("Found two arcs with same sink wire %s: %s (%d) vs %s (%d)\n",
+ ctx->nameOfWire(dst_wire), ctx->nameOf(net_info), user.index.idx(),
+ ctx->nameOf(dst_to_arc.at(dst_wire).net_info),
+ dst_to_arc.at(dst_wire).user_idx.idx());
+ }
+
+ if (src_to_net.count(dst_wire))
+ log_error("Wire %s is used as source and sink in different nets: %s vs %s (%d)\n",
+ ctx->nameOfWire(dst_wire), ctx->nameOf(src_to_net.at(dst_wire)),
+ ctx->nameOf(net_info), user.index.idx());
+
+ dst_to_arc[dst_wire] = arc;
+
+ if (net_info->wires.count(dst_wire) == 0) {
+ arc_queue_insert(arc, src_wire, dst_wire);
+ continue;
+ }
+
+ WireId cursor = dst_wire;
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
+
+ while (src_wire != cursor) {
+ auto it = net_info->wires.find(cursor);
+ if (it == net_info->wires.end()) {
+ arc_queue_insert(arc, src_wire, dst_wire);
+ break;
+ }
+
+ NPNR_ASSERT(it->second.pip != PipId());
+ cursor = ctx->getPipSrcWire(it->second.pip);
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
+ }
+ }
+ // TODO: this matches the situation before supporting multiple cell->bel pins, but do we want to keep
+ // this invariant?
+ if (phys_idx == 0)
+ log_warning("No wires found for port %s on destination cell %s.\n", ctx->nameOf(user.value.port),
+ ctx->nameOf(user.value.cell));
+ }
+
+ src_to_net[src_wire] = net_info;
+
+ std::vector<WireId> unbind_wires;
+
+ for (auto &it : net_info->wires)
+ if (it.second.strength < STRENGTH_LOCKED && wire_to_arcs.count(it.first) == 0)
+ unbind_wires.push_back(it.first);
+
+ for (auto it : unbind_wires)
+ ctx->unbindWire(it);
+ }
+ }
+
+ bool route_arc(const arc_key &arc, bool ripup)
+ {
+
+ NetInfo *net_info = arc.net_info;
+ auto user_idx = arc.user_idx;
+
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx], arc.phys_idx);
+ ripup_flag = false;
+
+ float crit = tmg.get_criticality(CellPortKey(net_info->users.at(user_idx)));
+
+ if (ctx->debug) {
+ log("Routing arc %d on net %s (%d arcs total):\n", user_idx.idx(), ctx->nameOf(net_info),
+ int(net_info->users.capacity()));
+ log(" source ... %s\n", ctx->nameOfWire(src_wire));
+ log(" sink ..... %s\n", ctx->nameOfWire(dst_wire));
+ }
+
+ // unbind wires that are currently used exclusively by this arc
+
+ pool<WireId> old_arc_wires;
+ old_arc_wires.swap(arc_to_wires[arc]);
+
+ for (WireId wire : old_arc_wires) {
+ auto &arc_wires = wire_to_arcs.at(wire);
+ NPNR_ASSERT(arc_wires.count(arc));
+ arc_wires.erase(arc);
+ if (arc_wires.empty()) {
+ if (ctx->debug)
+ log(" unbind %s\n", ctx->nameOfWire(wire));
+ ctx->unbindWire(wire);
+ }
+ }
+
+ // special case
+
+ if (src_wire == dst_wire) {
+ NetInfo *bound = ctx->getBoundWireNet(src_wire);
+ if (bound != nullptr)
+ NPNR_ASSERT(bound == net_info);
+ else {
+ ctx->bindWire(src_wire, net_info, STRENGTH_WEAK);
+ }
+ arc_to_wires[arc].insert(src_wire);
+ wire_to_arcs[src_wire].insert(arc);
+ return true;
+ }
+
+ // reset wire queue
+
+ if (!queue.empty()) {
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> new_queue;
+ queue.swap(new_queue);
+ }
+ dict<WireId, QueuedWire> visited;
+
+ // A* main loop
+
+ int visitCnt = 0;
+ int maxVisitCnt = INT_MAX;
+ delay_t best_est = 0;
+ delay_t best_score = -1;
+
+ {
+ QueuedWire qw;
+ qw.wire = src_wire;
+ qw.pip = PipId();
+ qw.delay = ctx->getWireDelay(qw.wire).maxDelay();
+ qw.penalty = 0;
+ qw.bonus = 0;
+ if (cfg.useEstimate) {
+ qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
+ best_est = qw.delay + qw.togo;
+ }
+ qw.randtag = ctx->rng();
+
+ queue.push(qw);
+ visited[qw.wire] = qw;
+ }
+
+ while (visitCnt++ < maxVisitCnt && !queue.empty()) {
+ QueuedWire qw = queue.top();
+ queue.pop();
+
+ for (auto pip : ctx->getPipsDownhill(qw.wire)) {
+ delay_t next_delay = qw.delay + ctx->getPipDelay(pip).maxDelay();
+ delay_t next_penalty = qw.penalty;
+ delay_t next_bonus = qw.bonus;
+ delay_t penalty_delta = 0;
+
+ WireId next_wire = ctx->getPipDstWire(pip);
+ next_delay += ctx->getWireDelay(next_wire).maxDelay();
+
+ WireId conflictWireWire = WireId(), conflictPipWire = WireId();
+ NetInfo *conflictWireNet = nullptr, *conflictPipNet = nullptr;
+
+ if (net_info->wires.count(next_wire) && net_info->wires.at(next_wire).pip == pip) {
+ next_bonus += cfg.reuseBonus * (1.0 - crit);
+ } else {
+ if (!ctx->checkWireAvail(next_wire)) {
+ if (!ripup)
+ continue;
+ conflictWireWire = ctx->getConflictingWireWire(next_wire);
+ if (conflictWireWire == WireId()) {
+ conflictWireNet = ctx->getConflictingWireNet(next_wire);
+ if (conflictWireNet == nullptr)
+ continue;
+ else {
+ if (conflictWireNet->wires.count(next_wire) &&
+ conflictWireNet->wires.at(next_wire).strength > STRENGTH_STRONG)
+ continue;
+ }
+ } else {
+ NetInfo *conflicting = ctx->getBoundWireNet(conflictWireWire);
+ if (conflicting != nullptr) {
+ if (conflicting->wires.count(conflictWireWire) &&
+ conflicting->wires.at(conflictWireWire).strength > STRENGTH_STRONG)
+ continue;
+ }
+ }
+ }
+
+ if (!ctx->checkPipAvail(pip)) {
+ if (!ripup)
+ continue;
+ conflictPipWire = ctx->getConflictingPipWire(pip);
+ if (conflictPipWire == WireId()) {
+ conflictPipNet = ctx->getConflictingPipNet(pip);
+ if (conflictPipNet == nullptr)
+ continue;
+ else {
+ if (conflictPipNet->wires.count(next_wire) &&
+ conflictPipNet->wires.at(next_wire).strength > STRENGTH_STRONG)
+ continue;
+ }
+ } else {
+ NetInfo *conflicting = ctx->getBoundWireNet(conflictPipWire);
+ if (conflicting != nullptr) {
+ if (conflicting->wires.count(conflictPipWire) &&
+ conflicting->wires.at(conflictPipWire).strength > STRENGTH_STRONG)
+ continue;
+ }
+ }
+ }
+
+ if (conflictWireNet != nullptr && conflictPipWire != WireId() &&
+ conflictWireNet->wires.count(conflictPipWire))
+ conflictPipWire = WireId();
+
+ if (conflictPipNet != nullptr && conflictWireWire != WireId() &&
+ conflictPipNet->wires.count(conflictWireWire))
+ conflictWireWire = WireId();
+
+ if (conflictWireWire == conflictPipWire)
+ conflictWireWire = WireId();
+
+ if (conflictWireNet == conflictPipNet)
+ conflictWireNet = nullptr;
+
+ if (conflictWireWire != WireId()) {
+ auto scores_it = wireScores.find(conflictWireWire);
+ if (scores_it != wireScores.end())
+ penalty_delta += scores_it->second * cfg.wireRipupPenalty;
+ penalty_delta += cfg.wireRipupPenalty;
+ }
+
+ if (conflictPipWire != WireId()) {
+ auto scores_it = wireScores.find(conflictPipWire);
+ if (scores_it != wireScores.end())
+ penalty_delta += scores_it->second * cfg.wireRipupPenalty;
+ penalty_delta += cfg.wireRipupPenalty;
+ }
+
+ if (conflictWireNet != nullptr) {
+ auto scores_it = netScores.find(conflictWireNet);
+ if (scores_it != netScores.end())
+ penalty_delta += scores_it->second * cfg.netRipupPenalty;
+ penalty_delta += cfg.netRipupPenalty;
+ penalty_delta += conflictWireNet->wires.size() * cfg.wireRipupPenalty;
+ }
+
+ if (conflictPipNet != nullptr) {
+ auto scores_it = netScores.find(conflictPipNet);
+ if (scores_it != netScores.end())
+ penalty_delta += scores_it->second * cfg.netRipupPenalty;
+ penalty_delta += cfg.netRipupPenalty;
+ penalty_delta += conflictPipNet->wires.size() * cfg.wireRipupPenalty;
+ }
+ }
+
+ next_penalty += penalty_delta * (timing_driven ? std::max(0.05, (1.0 - crit)) : 1);
+
+ delay_t next_score = next_delay + next_penalty;
+ NPNR_ASSERT(next_score >= 0);
+
+ if ((best_score >= 0) && (next_score - next_bonus - cfg.estimatePrecision > best_score))
+ continue;
+
+ auto old_visited_it = visited.find(next_wire);
+ if (old_visited_it != visited.end()) {
+ delay_t old_delay = old_visited_it->second.delay;
+ delay_t old_score = old_delay + old_visited_it->second.penalty;
+ NPNR_ASSERT(old_score >= 0);
+
+ if (next_score + ctx->getDelayEpsilon() >= old_score)
+ continue;
+
+#if 0
+ if (ctx->debug)
+ log("Found better route to %s. Old vs new delay estimate: %.3f (%.3f) %.3f (%.3f)\n",
+ ctx->nameOfWire(next_wire),
+ ctx->getDelayNS(old_score),
+ ctx->getDelayNS(old_visited_it->second.delay),
+ ctx->getDelayNS(next_score),
+ ctx->getDelayNS(next_delay));
+#endif
+ }
+
+ QueuedWire next_qw;
+ next_qw.wire = next_wire;
+ next_qw.pip = pip;
+ next_qw.delay = next_delay;
+ next_qw.penalty = next_penalty;
+ next_qw.bonus = next_bonus;
+ if (cfg.useEstimate) {
+ next_qw.togo = ctx->estimateDelay(next_wire, dst_wire);
+ delay_t this_est = next_qw.delay + next_qw.togo;
+ if (this_est / 2 - cfg.estimatePrecision > best_est)
+ continue;
+ if (best_est > this_est)
+ best_est = this_est;
+ }
+ next_qw.randtag = ctx->rng();
+
+#if 0
+ if (ctx->debug)
+ log("%s -> %s: %.3f (%.3f)\n",
+ ctx->nameOfWire(qw.wire),
+ ctx->nameOfWire(next_wire),
+ ctx->getDelayNS(next_score),
+ ctx->getDelayNS(next_delay));
+#endif
+
+ visited[next_qw.wire] = next_qw;
+ queue.push(next_qw);
+
+ if (next_wire == dst_wire) {
+ maxVisitCnt = std::min(maxVisitCnt, 2 * visitCnt + (next_qw.penalty > 0 ? 100 : 0));
+ best_score = next_score - next_bonus;
+ }
+ }
+ }
+
+ if (ctx->debug)
+ log(" total number of visited nodes: %d\n", visitCnt);
+
+ if (visited.count(dst_wire) == 0) {
+ if (ctx->debug)
+ log(" no route found for this arc\n");
+ return false;
+ }
+
+ if (ctx->debug) {
+ log(" final route delay: %8.2f\n", ctx->getDelayNS(visited[dst_wire].delay));
+ log(" final route penalty: %8.2f\n", ctx->getDelayNS(visited[dst_wire].penalty));
+ log(" final route bonus: %8.2f\n", ctx->getDelayNS(visited[dst_wire].bonus));
+ log(" arc budget: %12.2f\n", ctx->getDelayNS(net_info->users[user_idx].budget));
+ }
+
+ // bind resulting route (and maybe unroute other nets)
+
+ pool<WireId> unassign_wires = arc_to_wires[arc];
+
+ WireId cursor = dst_wire;
+ delay_t accumulated_path_delay = 0;
+ delay_t last_path_delay_delta = 0;
+ while (1) {
+ auto pip = visited[cursor].pip;
+
+ if (ctx->debug) {
+ delay_t path_delay_delta = ctx->estimateDelay(cursor, dst_wire) - accumulated_path_delay;
+
+ log(" node %s (%+.2f %+.2f)\n", ctx->nameOfWire(cursor), ctx->getDelayNS(path_delay_delta),
+ ctx->getDelayNS(path_delay_delta - last_path_delay_delta));
+
+ last_path_delay_delta = path_delay_delta;
+
+ if (pip != PipId())
+ accumulated_path_delay += ctx->getPipDelay(pip).maxDelay();
+ accumulated_path_delay += ctx->getWireDelay(cursor).maxDelay();
+ }
+
+ if (pip == PipId())
+ NPNR_ASSERT(cursor == src_wire);
+
+ if (!net_info->wires.count(cursor) || net_info->wires.at(cursor).pip != pip) {
+ if (!ctx->checkWireAvail(cursor)) {
+ ripup_wire(cursor);
+ NPNR_ASSERT(ctx->checkWireAvail(cursor));
+ }
+
+ if (pip != PipId() && !ctx->checkPipAvail(pip)) {
+ ripup_pip(pip);
+ NPNR_ASSERT(ctx->checkPipAvail(pip));
+ }
+
+ if (pip == PipId()) {
+ if (ctx->debug)
+ log(" bind wire %s\n", ctx->nameOfWire(cursor));
+ ctx->bindWire(cursor, net_info, STRENGTH_WEAK);
+ } else {
+ if (ctx->debug)
+ log(" bind pip %s\n", ctx->nameOfPip(pip));
+ ctx->bindPip(pip, net_info, STRENGTH_WEAK);
+ }
+ }
+
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
+
+ if (pip == PipId())
+ break;
+
+ cursor = ctx->getPipSrcWire(pip);
+ }
+
+ if (ripup_flag)
+ arcs_with_ripup++;
+ else
+ arcs_without_ripup++;
+
+ return true;
+ }
+
+ delay_t find_slack_thresh()
+ {
+ // If more than 5% of arcs have negative slack; use the 5% threshold as a ripup criteria
+ int arc_count = 0;
+ int failed_count = 0;
+ delay_t default_thresh = ctx->getDelayEpsilon();
+
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
+ if (skip_net(ni))
+ continue;
+ for (auto &usr : ni->users) {
+ ++arc_count;
+ delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
+ if (slack == std::numeric_limits<delay_t>::min())
+ continue;
+ if (slack < default_thresh)
+ ++failed_count;
+ }
+ }
+
+ if (arc_count < 50 || (failed_count < (0.05 * arc_count))) {
+ return default_thresh;
+ }
+
+ std::vector<delay_t> slacks;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
+ if (skip_net(ni))
+ continue;
+ for (auto &usr : ni->users) {
+ delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
+ if (slack == std::numeric_limits<delay_t>::min())
+ continue;
+ slacks.push_back(slack);
+ }
+ }
+ std::sort(slacks.begin(), slacks.end());
+ delay_t thresh = slacks.at(int(slacks.size() * 0.05));
+ log_warning("%.f%% of arcs have failing slack; using %.2fns as ripup threshold. Consider a reduced Fmax "
+ "constraint.\n",
+ (100.0 * failed_count) / arc_count, ctx->getDelayNS(thresh));
+ return thresh;
+ }
+};
+
+} // namespace
+
+NEXTPNR_NAMESPACE_BEGIN
+
+Router1Cfg::Router1Cfg(Context *ctx)
+{
+ maxIterCnt = ctx->setting<int>("router1/maxIterCnt", 200);
+ cleanupReroute = ctx->setting<bool>("router1/cleanupReroute", true);
+ fullCleanupReroute = ctx->setting<bool>("router1/fullCleanupReroute", true);
+ useEstimate = ctx->setting<bool>("router1/useEstimate", true);
+
+ wireRipupPenalty = ctx->getRipupDelayPenalty();
+ netRipupPenalty = 10 * ctx->getRipupDelayPenalty();
+ reuseBonus = wireRipupPenalty / 2;
+
+ estimatePrecision = 100 * ctx->getRipupDelayPenalty();
+}
+
+bool router1(Context *ctx, const Router1Cfg &cfg)
+{
+ try {
+ log_break();
+ log_info("Routing..\n");
+ ScopeLock<Context> lock(ctx);
+ auto rstart = std::chrono::high_resolution_clock::now();
+
+ log_info("Setting up routing queue.\n");
+
+ Router1 router(ctx, cfg);
+ router.setup();
+#ifndef NDEBUG
+ router.check();
+#endif
+
+ log_info("Routing %d arcs.\n", int(router.arc_queue.size()));
+
+ int iter_cnt = 0;
+ int last_arcs_with_ripup = 0;
+ int last_arcs_without_ripup = 0;
+ int timing_fail_count = 0;
+ bool timing_ripup = ctx->setting<bool>("router/tmg_ripup", false);
+ delay_t ripup_slack = 0;
+
+ log_info(" | (re-)routed arcs | delta | remaining| time spent |\n");
+ log_info(" IterCnt | w/ripup wo/ripup | w/r wo/r | arcs| batch(sec) total(sec)|\n");
+
+ auto prev_time = rstart;
+ while (!router.arc_queue.empty()) {
+ if (++iter_cnt % 1000 == 0) {
+ auto curr_time = std::chrono::high_resolution_clock::now();
+ log_info("%10d | %8d %10d | %4d %5d | %9d| %10.02f %10.02f|\n", iter_cnt, router.arcs_with_ripup,
+ router.arcs_without_ripup, router.arcs_with_ripup - last_arcs_with_ripup,
+ router.arcs_without_ripup - last_arcs_without_ripup, int(router.arc_queue.size()),
+ std::chrono::duration<float>(curr_time - prev_time).count(),
+ std::chrono::duration<float>(curr_time - rstart).count());
+ prev_time = curr_time;
+ last_arcs_with_ripup = router.arcs_with_ripup;
+ last_arcs_without_ripup = router.arcs_without_ripup;
+ ctx->yield();
+#ifndef NDEBUG
+ router.check();
+#endif
+ }
+
+ if (ctx->debug)
+ log("-- %d --\n", iter_cnt);
+
+ arc_key arc = router.arc_queue_pop();
+
+ if (!router.route_arc(arc, true)) {
+ log_warning("Failed to find a route for arc %d of net %s.\n", arc.user_idx.idx(),
+ ctx->nameOf(arc.net_info));
+#ifndef NDEBUG
+ router.check();
+ ctx->check();
+#endif
+ return false;
+ }
+ // Timing driven ripup
+ if (timing_ripup && router.arc_queue.empty() && timing_fail_count < 50) {
+ ++timing_fail_count;
+ router.tmg.run();
+ delay_t wns = 0, tns = 0;
+ if (timing_fail_count == 1)
+ ripup_slack = router.find_slack_thresh();
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
+ if (router.skip_net(ni))
+ continue;
+ bool is_locked = false;
+ for (auto &wire : ni->wires) {
+ if (wire.second.strength > STRENGTH_STRONG)
+ is_locked = true;
+ }
+ if (is_locked)
+ continue;
+ for (auto &usr : ni->users) {
+ delay_t slack = router.tmg.get_setup_slack(CellPortKey(usr));
+ if (slack == std::numeric_limits<delay_t>::min())
+ continue;
+ if (slack < 0) {
+ wns = std::min(wns, slack);
+ tns += slack;
+ }
+ if (slack <= ripup_slack) {
+ for (WireId w : ctx->getNetinfoSinkWires(ni, usr)) {
+ if (ctx->checkWireAvail(w))
+ continue;
+ router.ripup_wire(w);
+ }
+ }
+ }
+ }
+ log_info(" %d arcs ripped up due to negative slack WNS=%.02fns TNS=%.02fns.\n",
+ int(router.arc_queue.size()), ctx->getDelayNS(wns), ctx->getDelayNS(tns));
+ iter_cnt = 0;
+ router.wireScores.clear();
+ router.netScores.clear();
+ }
+ }
+ auto rend = std::chrono::high_resolution_clock::now();
+ log_info("%10d | %8d %10d | %4d %5d | %9d| %10.02f %10.02f|\n", iter_cnt, router.arcs_with_ripup,
+ router.arcs_without_ripup, router.arcs_with_ripup - last_arcs_with_ripup,
+ router.arcs_without_ripup - last_arcs_without_ripup, int(router.arc_queue.size()),
+ std::chrono::duration<float>(rend - prev_time).count(),
+ std::chrono::duration<float>(rend - rstart).count());
+ log_info("Routing complete.\n");
+ ctx->yield();
+ log_info("Router1 time %.02fs\n", std::chrono::duration<float>(rend - rstart).count());
+
+#ifndef NDEBUG
+ router.check();
+ ctx->check();
+ log_assert(ctx->checkRoutedDesign());
+#endif
+
+ log_info("Checksum: 0x%08x\n", ctx->checksum());
+ timing_analysis(ctx, true /* slack_histogram */, true /* print_fmax */, true /* print_path */,
+ true /* warn_on_failure */, true /* update_results */);
+
+ return true;
+ } catch (log_execution_error_exception) {
+#ifndef NDEBUG
+ ctx->lock();
+ ctx->check();
+ ctx->unlock();
+#endif
+ return false;
+ }
+}
+
+bool Context::checkRoutedDesign() const
+{
+ const Context *ctx = getCtx();
+
+ for (auto &net_it : ctx->nets) {
+ NetInfo *net_info = net_it.second.get();
+
+#ifdef ARCH_ECP5
+ if (net_info->is_global)
+ continue;
+#endif
+
+ if (ctx->debug)
+ log("checking net %s\n", ctx->nameOf(net_info));
+
+ if (net_info->users.empty()) {
+ if (ctx->debug)
+ log(" net without sinks\n");
+ log_assert(net_info->wires.empty());
+ continue;
+ }
+
+ bool found_unrouted = false;
+ bool found_loop = false;
+ bool found_stub = false;
+
+ struct ExtraWireInfo
+ {
+ int order_num = 0;
+ pool<WireId> children;
+ };
+
+ dict<WireId, std::unique_ptr<ExtraWireInfo>> db;
+
+ for (auto &it : net_info->wires) {
+ WireId w = it.first;
+ PipId p = it.second.pip;
+
+ if (p != PipId()) {
+ log_assert(ctx->getPipDstWire(p) == w);
+ db.emplace(ctx->getPipSrcWire(p), std::make_unique<ExtraWireInfo>()).first->second->children.insert(w);
+ }
+ }
+
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ if (src_wire == WireId()) {
+ log_assert(net_info->driver.cell == nullptr);
+ if (ctx->debug)
+ log(" undriven and unrouted\n");
+ continue;
+ }
+
+ if (net_info->wires.count(src_wire) == 0) {
+ if (ctx->debug)
+ log(" source (%s) not bound to net\n", ctx->nameOfWire(src_wire));
+ found_unrouted = true;
+ }
+
+ dict<WireId, store_index<PortRef>> dest_wires;
+ for (auto user : net_info->users.enumerate()) {
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
+ log_assert(dst_wire != WireId());
+ dest_wires[dst_wire] = user.index;
+
+ if (net_info->wires.count(dst_wire) == 0) {
+ if (ctx->debug)
+ log(" sink %d (%s) not bound to net\n", user.index.idx(), ctx->nameOfWire(dst_wire));
+ found_unrouted = true;
+ }
+ }
+ }
+
+ std::function<void(WireId, int)> setOrderNum;
+ pool<WireId> logged_wires;
+
+ setOrderNum = [&](WireId w, int num) {
+ auto &db_entry = *db.emplace(w, std::make_unique<ExtraWireInfo>()).first->second;
+ if (db_entry.order_num != 0) {
+ found_loop = true;
+ log(" %*s=> loop\n", 2 * num, "");
+ return;
+ }
+ db_entry.order_num = num;
+ for (WireId child : db_entry.children) {
+ if (ctx->debug) {
+ log(" %*s-> %s\n", 2 * num, "", ctx->nameOfWire(child));
+ logged_wires.insert(child);
+ }
+ setOrderNum(child, num + 1);
+ }
+ if (db_entry.children.empty()) {
+ if (dest_wires.count(w) != 0) {
+ if (ctx->debug)
+ log(" %*s=> sink %d\n", 2 * num, "", dest_wires.at(w).idx());
+ } else {
+ if (ctx->debug)
+ log(" %*s=> stub\n", 2 * num, "");
+ found_stub = true;
+ }
+ }
+ };
+
+ if (ctx->debug) {
+ log(" driver: %s\n", ctx->nameOfWire(src_wire));
+ logged_wires.insert(src_wire);
+ }
+ setOrderNum(src_wire, 1);
+
+ pool<WireId> dangling_wires;
+
+ for (auto &it : db) {
+ auto &db_entry = *it.second;
+ if (db_entry.order_num == 0)
+ dangling_wires.insert(it.first);
+ }
+
+ if (ctx->debug) {
+ if (dangling_wires.empty()) {
+ log(" no dangling wires.\n");
+ } else {
+ pool<WireId> root_wires = dangling_wires;
+
+ for (WireId w : dangling_wires) {
+ for (WireId c : db[w]->children)
+ root_wires.erase(c);
+ }
+
+ for (WireId w : root_wires) {
+ log(" dangling wire: %s\n", ctx->nameOfWire(w));
+ logged_wires.insert(w);
+ setOrderNum(w, 1);
+ }
+
+ for (WireId w : dangling_wires) {
+ if (logged_wires.count(w) == 0)
+ log(" loop: %s -> %s\n", ctx->nameOfWire(ctx->getPipSrcWire(net_info->wires.at(w).pip)),
+ ctx->nameOfWire(w));
+ }
+ }
+ }
+
+ bool fail = false;
+
+ if (found_unrouted) {
+ if (ctx->debug)
+ log("check failed: found unrouted arcs\n");
+ fail = true;
+ }
+
+ if (found_loop) {
+ if (ctx->debug)
+ log("check failed: found loops\n");
+ fail = true;
+ }
+
+ if (found_stub) {
+ if (ctx->debug)
+ log("check failed: found stubs\n");
+ fail = true;
+ }
+
+ if (!dangling_wires.empty()) {
+ if (ctx->debug)
+ log("check failed: found dangling wires\n");
+ fail = true;
+ }
+
+ if (fail)
+ return false;
+ }
+
+ return true;
+}
+
+bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, dict<WireId, PipId> *route,
+ bool useEstimate)
+{
+ // FIXME
+ return false;
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/common/route/router1.h b/common/route/router1.h
new file mode 100644
index 00000000..a7ec5bad
--- /dev/null
+++ b/common/route/router1.h
@@ -0,0 +1,45 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2018 Claire Xenia Wolf <claire@yosyshq.com>
+ *
+ * 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.
+ *
+ */
+
+#ifndef ROUTER1_H
+#define ROUTER1_H
+
+#include "log.h"
+#include "nextpnr.h"
+NEXTPNR_NAMESPACE_BEGIN
+
+struct Router1Cfg
+{
+ Router1Cfg(Context *ctx);
+
+ int maxIterCnt;
+ bool cleanupReroute;
+ bool fullCleanupReroute;
+ bool useEstimate;
+ delay_t wireRipupPenalty;
+ delay_t netRipupPenalty;
+ delay_t reuseBonus;
+ delay_t estimatePrecision;
+};
+
+extern bool router1(Context *ctx, const Router1Cfg &cfg);
+
+NEXTPNR_NAMESPACE_END
+
+#endif // ROUTER1_H
diff --git a/common/route/router2.cc b/common/route/router2.cc
new file mode 100644
index 00000000..e943e493
--- /dev/null
+++ b/common/route/router2.cc
@@ -0,0 +1,1499 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2019 gatecat <gatecat@ds0.me>
+ *
+ * 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.
+ *
+ * Core routing algorithm based on CRoute:
+ *
+ * CRoute: A Fast High-quality Timing-driven Connection-based FPGA Router
+ * Dries Vercruyce, Elias Vansteenkiste and Dirk Stroobandt
+ * DOI 10.1109/FCCM.2019.00017 [PDF on SciHub]
+ *
+ * Modified for the nextpnr Arch API and data structures; optimised for
+ * real-world FPGA architectures in particular ECP5 and Xilinx UltraScale+
+ *
+ */
+
+#include "router2.h"
+
+#include <algorithm>
+#include <boost/container/flat_map.hpp>
+#include <chrono>
+#include <deque>
+#include <fstream>
+#include <queue>
+
+#include "log.h"
+#include "nextpnr.h"
+#include "router1.h"
+#include "scope_lock.h"
+#include "timing.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+namespace {
+struct Router2
+{
+
+ struct PerArcData
+ {
+ WireId sink_wire;
+ ArcBounds bb;
+ bool routed = false;
+ };
+
+ // As we allow overlap at first; the nextpnr bind functions can't be used
+ // as the primary relation between arcs and wires/pips
+ struct PerNetData
+ {
+ WireId src_wire;
+ dict<WireId, std::pair<PipId, int>> wires;
+ std::vector<std::vector<PerArcData>> arcs;
+ ArcBounds bb;
+ // Coordinates of the center of the net, used for the weight-to-average
+ int cx, cy, hpwl;
+ int total_route_us = 0;
+ float max_crit = 0;
+ int fail_count = 0;
+ };
+
+ struct WireScore
+ {
+ float cost;
+ float togo_cost;
+ float total() const { return cost + togo_cost; }
+ };
+
+ struct PerWireData
+ {
+ // nextpnr
+ WireId w;
+ // Historical congestion cost
+ int curr_cong = 0;
+ float hist_cong_cost = 1.0;
+ // Wire is unavailable as locked to another arc
+ bool unavailable = false;
+ // This wire has to be used for this net
+ int reserved_net = -1;
+ // The notional location of the wire, to guarantee thread safety
+ int16_t x = 0, y = 0;
+ // Visit data
+ PipId pip_fwd, pip_bwd;
+ bool visited_fwd = false, visited_bwd = false;
+ };
+
+ Context *ctx;
+ Router2Cfg cfg;
+
+ Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg), tmg(ctx) { tmg.setup(); }
+
+ // Use 'udata' for fast net lookups and indexing
+ std::vector<NetInfo *> nets_by_udata;
+ std::vector<PerNetData> nets;
+
+ bool timing_driven, timing_driven_ripup;
+ TimingAnalyser tmg;
+
+ void setup_nets()
+ {
+ // Populate per-net and per-arc structures at start of routing
+ nets.resize(ctx->nets.size());
+ nets_by_udata.resize(ctx->nets.size());
+ size_t i = 0;
+ for (auto &net : ctx->nets) {
+ NetInfo *ni = net.second.get();
+ ni->udata = i;
+ nets_by_udata.at(i) = ni;
+ nets.at(i).arcs.resize(ni->users.capacity());
+
+ // Start net bounding box at overall min/max
+ nets.at(i).bb.x0 = std::numeric_limits<int>::max();
+ nets.at(i).bb.x1 = std::numeric_limits<int>::min();
+ nets.at(i).bb.y0 = std::numeric_limits<int>::max();
+ nets.at(i).bb.y1 = std::numeric_limits<int>::min();
+ nets.at(i).cx = 0;
+ nets.at(i).cy = 0;
+
+ if (ni->driver.cell != nullptr) {
+ Loc drv_loc = ctx->getBelLocation(ni->driver.cell->bel);
+ nets.at(i).cx += drv_loc.x;
+ nets.at(i).cy += drv_loc.y;
+ }
+
+ for (auto usr : ni->users.enumerate()) {
+ WireId src_wire = ctx->getNetinfoSourceWire(ni);
+ for (auto &dst_wire : ctx->getNetinfoSinkWires(ni, usr.value)) {
+ nets.at(i).src_wire = src_wire;
+ if (ni->driver.cell == nullptr)
+ src_wire = dst_wire;
+ if (ni->driver.cell == nullptr && dst_wire == WireId())
+ continue;
+ if (src_wire == WireId())
+ log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(ni->driver.port),
+ ctx->nameOf(ni->driver.cell));
+ if (dst_wire == WireId())
+ log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.value.port),
+ ctx->nameOf(usr.value.cell));
+ nets.at(i).arcs.at(usr.index.idx()).emplace_back();
+ auto &ad = nets.at(i).arcs.at(usr.index.idx()).back();
+ ad.sink_wire = dst_wire;
+ // Set bounding box for this arc
+ ad.bb = ctx->getRouteBoundingBox(src_wire, dst_wire);
+ // Expand net bounding box to include this arc
+ nets.at(i).bb.x0 = std::min(nets.at(i).bb.x0, ad.bb.x0);
+ nets.at(i).bb.x1 = std::max(nets.at(i).bb.x1, ad.bb.x1);
+ nets.at(i).bb.y0 = std::min(nets.at(i).bb.y0, ad.bb.y0);
+ nets.at(i).bb.y1 = std::max(nets.at(i).bb.y1, ad.bb.y1);
+ }
+ // Add location to centroid sum
+ Loc usr_loc = ctx->getBelLocation(usr.value.cell->bel);
+ nets.at(i).cx += usr_loc.x;
+ nets.at(i).cy += usr_loc.y;
+ }
+ nets.at(i).hpwl = std::max(
+ std::abs(nets.at(i).bb.y1 - nets.at(i).bb.y0) + std::abs(nets.at(i).bb.x1 - nets.at(i).bb.x0), 1);
+ nets.at(i).cx /= int(ni->users.entries() + 1);
+ nets.at(i).cy /= int(ni->users.entries() + 1);
+ if (ctx->debug)
+ log_info("%s: bb=(%d, %d)->(%d, %d) c=(%d, %d) hpwl=%d\n", ctx->nameOf(ni), nets.at(i).bb.x0,
+ nets.at(i).bb.y0, nets.at(i).bb.x1, nets.at(i).bb.y1, nets.at(i).cx, nets.at(i).cy,
+ nets.at(i).hpwl);
+ nets.at(i).bb.x0 = std::max(nets.at(i).bb.x0 - cfg.bb_margin_x, 0);
+ nets.at(i).bb.y0 = std::max(nets.at(i).bb.y0 - cfg.bb_margin_y, 0);
+ nets.at(i).bb.x1 = std::min(nets.at(i).bb.x1 + cfg.bb_margin_x, ctx->getGridDimX());
+ nets.at(i).bb.y1 = std::min(nets.at(i).bb.y1 + cfg.bb_margin_y, ctx->getGridDimY());
+ i++;
+ }
+ }
+
+ dict<WireId, int> wire_to_idx;
+ std::vector<PerWireData> flat_wires;
+
+ PerWireData &wire_data(WireId w) { return flat_wires[wire_to_idx.at(w)]; }
+
+ void setup_wires()
+ {
+ // Set up per-wire structures, so that MT parts don't have to do any memory allocation
+ // This is possibly quite wasteful and not cache-optimal; further consideration necessary
+ for (auto wire : ctx->getWires()) {
+ PerWireData pwd;
+ pwd.w = wire;
+ NetInfo *bound = ctx->getBoundWireNet(wire);
+ if (bound != nullptr) {
+ auto iter = bound->wires.find(wire);
+ if (iter != bound->wires.end()) {
+ auto &nd = nets.at(bound->udata);
+ nd.wires[wire] = std::make_pair(bound->wires.at(wire).pip, 0);
+ pwd.curr_cong = 1;
+ if (bound->wires.at(wire).strength == STRENGTH_PLACER) {
+ pwd.reserved_net = bound->udata;
+ } else if (bound->wires.at(wire).strength > STRENGTH_PLACER) {
+ pwd.unavailable = true;
+ }
+ }
+ }
+
+ ArcBounds wire_loc = ctx->getRouteBoundingBox(wire, wire);
+ pwd.x = (wire_loc.x0 + wire_loc.x1) / 2;
+ pwd.y = (wire_loc.y0 + wire_loc.y1) / 2;
+
+ wire_to_idx[wire] = int(flat_wires.size());
+ flat_wires.push_back(pwd);
+ }
+
+ for (auto &net_pair : ctx->nets) {
+ auto *net = net_pair.second.get();
+ auto &nd = nets.at(net->udata);
+ for (auto usr : net->users.enumerate()) {
+ auto &ad = nd.arcs.at(usr.index.idx());
+ for (size_t phys_pin = 0; phys_pin < ad.size(); phys_pin++) {
+ if (check_arc_routing(net, usr.index, phys_pin)) {
+ record_prerouted_net(net, usr.index, phys_pin);
+ }
+ }
+ }
+ }
+ }
+
+ struct QueuedWire
+ {
+
+ explicit QueuedWire(int wire = -1, WireScore score = WireScore{}, int randtag = 0)
+ : wire(wire), score(score), randtag(randtag){};
+
+ int wire;
+ WireScore score;
+ int randtag = 0;
+
+ struct Greater
+ {
+ bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept
+ {
+ float lhs_score = lhs.score.cost + lhs.score.togo_cost,
+ rhs_score = rhs.score.cost + rhs.score.togo_cost;
+ return lhs_score == rhs_score ? lhs.randtag > rhs.randtag : lhs_score > rhs_score;
+ }
+ };
+ };
+
+ bool hit_test_pip(ArcBounds &bb, Loc l) { return l.x >= bb.x0 && l.x <= bb.x1 && l.y >= bb.y0 && l.y <= bb.y1; }
+
+ double curr_cong_weight, hist_cong_weight, estimate_weight;
+
+ struct ThreadContext
+ {
+ // Nets to route
+ std::vector<NetInfo *> route_nets;
+ // Nets that failed routing
+ std::vector<NetInfo *> failed_nets;
+
+ std::vector<std::pair<store_index<PortRef>, size_t>> route_arcs;
+
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> fwd_queue, bwd_queue;
+ // Special case where one net has multiple logical arcs to the same physical sink
+ pool<WireId> processed_sinks;
+
+ std::vector<int> dirty_wires;
+
+ // Thread bounding box
+ ArcBounds bb;
+
+ DeterministicRNG rng;
+
+ // Used to add existing routing to the heap
+ pool<WireId> in_wire_by_loc;
+ dict<std::pair<int, int>, pool<WireId>> wire_by_loc;
+ };
+
+ bool thread_test_wire(ThreadContext &t, PerWireData &w)
+ {
+ return w.x >= t.bb.x0 && w.x <= t.bb.x1 && w.y >= t.bb.y0 && w.y <= t.bb.y1;
+ }
+
+ enum ArcRouteResult
+ {
+ ARC_SUCCESS,
+ ARC_RETRY_WITHOUT_BB,
+ ARC_FATAL,
+ };
+
+// Define to make sure we don't print in a multithreaded context
+#define ARC_LOG_ERR(...) \
+ do { \
+ if (is_mt) \
+ return ARC_FATAL; \
+ else \
+ log_error(__VA_ARGS__); \
+ } while (0)
+#define ROUTE_LOG_DBG(...) \
+ do { \
+ if (!is_mt && ctx->debug) \
+ log(__VA_ARGS__); \
+ } while (0)
+
+ void bind_pip_internal(PerNetData &net, store_index<PortRef> user, int wire, PipId pip)
+ {
+ auto &wd = flat_wires.at(wire);
+ auto found = net.wires.find(wd.w);
+ if (found == net.wires.end()) {
+ // Not yet used for any arcs of this net, add to list
+ net.wires.emplace(wd.w, std::make_pair(pip, 1));
+ // Increase bound count of wire by 1
+ ++wd.curr_cong;
+ } else {
+ // Already used for at least one other arc of this net
+ // Don't allow two uphill PIPs for the same net and wire
+ NPNR_ASSERT(found->second.first == pip);
+ // Increase the count of bound arcs
+ ++found->second.second;
+ }
+ }
+
+ void unbind_pip_internal(PerNetData &net, store_index<PortRef> user, WireId wire)
+ {
+ auto &wd = wire_data(wire);
+ auto &b = net.wires.at(wd.w);
+ --b.second;
+ if (b.second == 0) {
+ // No remaining arcs of this net bound to this wire
+ --wd.curr_cong;
+ net.wires.erase(wd.w);
+ }
+ }
+
+ void ripup_arc(NetInfo *net, store_index<PortRef> user, size_t phys_pin)
+ {
+ auto &nd = nets.at(net->udata);
+ auto &ad = nd.arcs.at(user.idx()).at(phys_pin);
+ if (!ad.routed)
+ return;
+ WireId src = nets.at(net->udata).src_wire;
+ WireId cursor = ad.sink_wire;
+ while (cursor != src) {
+ PipId pip = nd.wires.at(cursor).first;
+ unbind_pip_internal(nd, user, cursor);
+ cursor = ctx->getPipSrcWire(pip);
+ }
+ ad.routed = false;
+ }
+
+ float score_wire_for_arc(NetInfo *net, store_index<PortRef> user, size_t phys_pin, WireId wire, PipId pip,
+ float crit_weight)
+ {
+ auto &wd = wire_data(wire);
+ auto &nd = nets.at(net->udata);
+ float base_cost = cfg.get_base_cost(ctx, wire, pip, crit_weight);
+ int overuse = wd.curr_cong;
+ float hist_cost = 1.0f + crit_weight * (wd.hist_cong_cost - 1.0f);
+ float bias_cost = 0;
+ int source_uses = 0;
+ if (nd.wires.count(wire)) {
+ overuse -= 1;
+ source_uses = nd.wires.at(wire).second;
+ }
+ float present_cost = 1.0f + overuse * curr_cong_weight * crit_weight;
+ if (pip != PipId()) {
+ Loc pl = ctx->getPipLocation(pip);
+ bias_cost = cfg.bias_cost_factor * (base_cost / int(net->users.entries())) *
+ ((std::abs(pl.x - nd.cx) + std::abs(pl.y - nd.cy)) / float(nd.hpwl));
+ }
+ return base_cost * hist_cost * present_cost / (1 + (source_uses * crit_weight)) + bias_cost;
+ }
+
+ float get_togo_cost(NetInfo *net, store_index<PortRef> user, int wire, WireId src_sink, float crit_weight,
+ bool bwd = false)
+ {
+ auto &nd = nets.at(net->udata);
+ auto &wd = flat_wires[wire];
+ int source_uses = 0;
+ if (nd.wires.count(wd.w)) {
+ source_uses = nd.wires.at(wd.w).second;
+ }
+ // FIXME: timing/wirelength balance?
+ delay_t est_delay = ctx->estimateDelay(bwd ? src_sink : wd.w, bwd ? wd.w : src_sink);
+ return (ctx->getDelayNS(est_delay) / (1 + source_uses * crit_weight)) + cfg.ipin_cost_adder;
+ }
+
+ bool check_arc_routing(NetInfo *net, store_index<PortRef> usr, size_t phys_pin)
+ {
+ auto &nd = nets.at(net->udata);
+ auto &ad = nd.arcs.at(usr.idx()).at(phys_pin);
+ WireId src_wire = nets.at(net->udata).src_wire;
+ WireId cursor = ad.sink_wire;
+ while (nd.wires.count(cursor)) {
+ auto &wd = wire_data(cursor);
+ if (wd.curr_cong != 1)
+ return false;
+ auto &uh = nd.wires.at(cursor).first;
+ if (uh == PipId())
+ break;
+ cursor = ctx->getPipSrcWire(uh);
+ }
+ return (cursor == src_wire);
+ }
+
+ void record_prerouted_net(NetInfo *net, store_index<PortRef> usr, size_t phys_pin)
+ {
+ auto &nd = nets.at(net->udata);
+ auto &ad = nd.arcs.at(usr.idx()).at(phys_pin);
+ ad.routed = true;
+
+ WireId src = nets.at(net->udata).src_wire;
+ WireId cursor = ad.sink_wire;
+ while (cursor != src) {
+ size_t wire_idx = wire_to_idx.at(cursor);
+ PipId pip = nd.wires.at(cursor).first;
+ bind_pip_internal(nd, usr, wire_idx, pip);
+ cursor = ctx->getPipSrcWire(pip);
+ }
+ }
+
+ // Returns true if a wire contains no source ports or driving pips
+ bool is_wire_undriveable(WireId wire, const NetInfo *net, int iter_count = 0)
+ {
+ // This is specifically designed to handle a particularly icky case that the current router struggles with in
+ // the nexus device,
+ // C -> C lut input only
+ // C; D; or F from another lut -> D lut input
+ // D or M -> M ff input
+ // without careful reservation of C for C lut input and D for D lut input, there is fighting for D between FF
+ // and LUT
+ if (iter_count > 7)
+ return false; // heuristic to assume we've hit general routing
+ if (wire_data(wire).unavailable)
+ return true;
+ if (wire_data(wire).reserved_net != -1 && wire_data(wire).reserved_net != net->udata)
+ return true; // reserved for another net
+ for (auto bp : ctx->getWireBelPins(wire))
+ if ((net->driver.cell == nullptr || bp.bel == net->driver.cell->bel) &&
+ ctx->getBelPinType(bp.bel, bp.pin) != PORT_IN)
+ return false;
+ for (auto p : ctx->getPipsUphill(wire))
+ if (ctx->checkPipAvail(p)) {
+ if (!is_wire_undriveable(ctx->getPipSrcWire(p), net, iter_count + 1))
+ return false;
+ }
+ return true;
+ }
+
+ // Find all the wires that must be used to route a given arc
+ bool reserve_wires_for_arc(NetInfo *net, store_index<PortRef> i)
+ {
+ bool did_something = false;
+ WireId src = ctx->getNetinfoSourceWire(net);
+ auto &usr = net->users.at(i);
+ for (auto sink : ctx->getNetinfoSinkWires(net, usr)) {
+ pool<WireId> rsv;
+ WireId cursor = sink;
+ bool done = false;
+ if (ctx->debug)
+ log("reserving wires for arc %d (%s.%s) of net %s\n", i.idx(), ctx->nameOf(usr.cell),
+ ctx->nameOf(usr.port), ctx->nameOf(net));
+ while (!done) {
+ auto &wd = wire_data(cursor);
+ if (ctx->debug)
+ log(" %s\n", ctx->nameOfWire(cursor));
+ did_something |= (wd.reserved_net != net->udata);
+ if (wd.reserved_net != -1 && wd.reserved_net != net->udata)
+ log_error("attempting to reserve wire '%s' for nets '%s' and '%s'\n", ctx->nameOfWire(cursor),
+ ctx->nameOf(nets_by_udata.at(wd.reserved_net)), ctx->nameOf(net));
+ wd.reserved_net = net->udata;
+ if (cursor == src)
+ break;
+ WireId next_cursor;
+ for (auto uh : ctx->getPipsUphill(cursor)) {
+ WireId w = ctx->getPipSrcWire(uh);
+ if (is_wire_undriveable(w, net))
+ continue;
+ if (next_cursor != WireId()) {
+ done = true;
+ break;
+ }
+ next_cursor = w;
+ }
+ if (next_cursor == WireId())
+ break;
+ cursor = next_cursor;
+ }
+ }
+ return did_something;
+ }
+
+ void find_all_reserved_wires()
+ {
+ // Run iteratively, as reserving wires for one net might limit choices for another
+ bool did_something = false;
+ do {
+ did_something = false;
+ for (auto net : nets_by_udata) {
+ WireId src = ctx->getNetinfoSourceWire(net);
+ if (src == WireId())
+ continue;
+ for (auto usr : net->users.enumerate())
+ did_something |= reserve_wires_for_arc(net, usr.index);
+ }
+ } while (did_something);
+ }
+
+ void reset_wires(ThreadContext &t)
+ {
+ for (auto w : t.dirty_wires) {
+ flat_wires[w].pip_fwd = PipId();
+ flat_wires[w].pip_bwd = PipId();
+ flat_wires[w].visited_fwd = false;
+ flat_wires[w].visited_bwd = false;
+ }
+ t.dirty_wires.clear();
+ }
+
+ // These nets have very-high-fanout pips and special rules must be followed (only working backwards) to avoid
+ // crippling perf
+ bool is_pseudo_const_net(const NetInfo *net)
+ {
+#ifdef ARCH_NEXUS
+ if (net->driver.cell != nullptr && net->driver.cell->type == id_VCC_DRV)
+ return true;
+#endif
+ return false;
+ }
+
+ void update_wire_by_loc(ThreadContext &t, NetInfo *net, store_index<PortRef> i, size_t phys_pin, bool is_mt)
+ {
+ if (is_pseudo_const_net(net))
+ return;
+ auto &nd = nets.at(net->udata);
+ auto &ad = nd.arcs.at(i.idx()).at(phys_pin);
+ WireId cursor = ad.sink_wire;
+ if (!nd.wires.count(cursor))
+ return;
+ while (cursor != nd.src_wire) {
+ if (!t.in_wire_by_loc.count(cursor)) {
+ t.in_wire_by_loc.insert(cursor);
+ for (auto dh : ctx->getPipsDownhill(cursor)) {
+ Loc dh_loc = ctx->getPipLocation(dh);
+ t.wire_by_loc[std::make_pair(dh_loc.x, dh_loc.y)].insert(cursor);
+ }
+ }
+ cursor = ctx->getPipSrcWire(nd.wires.at(cursor).first);
+ }
+ }
+
+ // Functions for marking wires as visited, and checking if they have already been visited
+ void set_visited_fwd(ThreadContext &t, int wire, PipId pip)
+ {
+ auto &wd = flat_wires.at(wire);
+ if (!wd.visited_fwd && !wd.visited_bwd)
+ t.dirty_wires.push_back(wire);
+ wd.pip_fwd = pip;
+ wd.visited_fwd = true;
+ }
+ void set_visited_bwd(ThreadContext &t, int wire, PipId pip)
+ {
+ auto &wd = flat_wires.at(wire);
+ if (!wd.visited_fwd && !wd.visited_bwd)
+ t.dirty_wires.push_back(wire);
+ wd.pip_bwd = pip;
+ wd.visited_bwd = true;
+ }
+
+ bool was_visited_fwd(int wire) { return flat_wires.at(wire).visited_fwd; }
+ bool was_visited_bwd(int wire) { return flat_wires.at(wire).visited_bwd; }
+
+ float get_arc_crit(NetInfo *net, store_index<PortRef> i)
+ {
+ if (!timing_driven)
+ return 0;
+ return tmg.get_criticality(CellPortKey(net->users.at(i)));
+ }
+
+ bool arc_failed_slack(NetInfo *net, store_index<PortRef> usr_idx)
+ {
+ return timing_driven_ripup &&
+ (tmg.get_setup_slack(CellPortKey(net->users.at(usr_idx))) < (2 * ctx->getDelayEpsilon()));
+ }
+
+ ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, store_index<PortRef> i, size_t phys_pin, bool is_mt,
+ bool is_bb = true)
+ {
+ // Do some initial lookups and checks
+ auto arc_start = std::chrono::high_resolution_clock::now();
+ auto &nd = nets[net->udata];
+ auto &ad = nd.arcs.at(i.idx()).at(phys_pin);
+ auto &usr = net->users.at(i);
+ ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", i.idx(), ctx->nameOf(net), ad.bb.x0,
+ ad.bb.y0, ad.bb.x1, ad.bb.y1);
+ WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr, phys_pin);
+ if (src_wire == WireId())
+ ARC_LOG_ERR("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port),
+ ctx->nameOf(net->driver.cell));
+ if (dst_wire == WireId())
+ ARC_LOG_ERR("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port),
+ ctx->nameOf(usr.cell));
+ int src_wire_idx = wire_to_idx.at(src_wire);
+ int dst_wire_idx = wire_to_idx.at(dst_wire);
+ // Calculate a timing weight based on criticality
+ float crit = get_arc_crit(net, i);
+ float crit_weight = (1.0f - std::pow(crit, 2));
+ ROUTE_LOG_DBG(" crit=%.3f crit_weight=%.3f\n", crit, crit_weight);
+ // Check if arc was already done _in this iteration_
+ if (t.processed_sinks.count(dst_wire))
+ return ARC_SUCCESS;
+
+ // We have two modes:
+ // 0. starting within a small range of existing routing
+ // 1. expanding from all routing
+ int mode = 0;
+ if (net->users.entries() < 4 || nd.wires.empty() || (crit > 0.95))
+ mode = 1;
+
+ // This records the point where forwards and backwards routing met
+ int midpoint_wire = -1;
+ int explored = 1;
+
+ for (; mode < 2; mode++) {
+ // Clear out the queues
+ if (!t.fwd_queue.empty()) {
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> new_queue;
+ t.fwd_queue.swap(new_queue);
+ }
+ if (!t.bwd_queue.empty()) {
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> new_queue;
+ t.bwd_queue.swap(new_queue);
+ }
+ // Unvisit any previously visited wires
+ reset_wires(t);
+
+ ROUTE_LOG_DBG("src_wire = %s -> dst_wire = %s\n", ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire));
+
+ // Add 'forward' direction startpoints to queue
+ auto seed_queue_fwd = [&](WireId wire, float wire_cost = 0) {
+ WireScore base_score;
+ base_score.cost = wire_cost;
+ int wire_idx = wire_to_idx.at(wire);
+ base_score.togo_cost = get_togo_cost(net, i, wire_idx, dst_wire, false, crit_weight);
+ t.fwd_queue.push(QueuedWire(wire_idx, base_score));
+ set_visited_fwd(t, wire_idx, PipId());
+ };
+ auto &dst_data = flat_wires.at(dst_wire_idx);
+ // Look for nearby existing routing
+ for (int dy = -cfg.bb_margin_y; dy <= cfg.bb_margin_y; dy++)
+ for (int dx = -cfg.bb_margin_x; dx <= cfg.bb_margin_x; dx++) {
+ auto fnd = t.wire_by_loc.find(std::make_pair(dst_data.x + dx, dst_data.y + dy));
+ if (fnd == t.wire_by_loc.end())
+ continue;
+ for (WireId wire : fnd->second) {
+ ROUTE_LOG_DBG(" seeding with %s\n", ctx->nameOfWire(wire));
+ seed_queue_fwd(wire);
+ }
+ }
+
+ if (mode == 0 && t.fwd_queue.size() < 4)
+ continue;
+
+ if (mode == 1 && !is_pseudo_const_net(net)) {
+ // Seed forwards with the source wire, if less than 8 existing wires added
+ seed_queue_fwd(src_wire);
+ } else {
+ set_visited_fwd(t, src_wire_idx, PipId());
+ }
+ auto seed_queue_bwd = [&](WireId wire) {
+ WireScore base_score;
+ base_score.cost = 0;
+ int wire_idx = wire_to_idx.at(wire);
+ base_score.togo_cost = get_togo_cost(net, i, wire_idx, src_wire, true, crit_weight);
+ t.bwd_queue.push(QueuedWire(wire_idx, base_score));
+ set_visited_bwd(t, wire_idx, PipId());
+ };
+
+ // Seed backwards with the dest wire
+ seed_queue_bwd(dst_wire);
+
+ int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0));
+ int iter = 0;
+
+ // Mode 0 required both queues to be live
+ while (((mode == 0) ? (!t.fwd_queue.empty() && !t.bwd_queue.empty())
+ : (!t.fwd_queue.empty() || !t.bwd_queue.empty())) &&
+ (!is_bb || iter < toexplore)) {
+ ++iter;
+ if (!t.fwd_queue.empty()) {
+ // Explore forwards
+ auto curr = t.fwd_queue.top();
+ t.fwd_queue.pop();
+ ++explored;
+ if (was_visited_bwd(curr.wire)) {
+ // Meet in the middle; done
+ midpoint_wire = curr.wire;
+ break;
+ }
+ auto &curr_data = flat_wires.at(curr.wire);
+ for (PipId dh : ctx->getPipsDownhill(curr_data.w)) {
+ // Skip pips outside of box in bounding-box mode
+ if (is_bb && !hit_test_pip(nd.bb, ctx->getPipLocation(dh)))
+ continue;
+ if (!ctx->checkPipAvailForNet(dh, net))
+ continue;
+ WireId next = ctx->getPipDstWire(dh);
+ int next_idx = wire_to_idx.at(next);
+ if (was_visited_fwd(next_idx)) {
+ // Don't expand the same node twice.
+ continue;
+ }
+ auto &nwd = flat_wires.at(next_idx);
+ if (nwd.unavailable)
+ continue;
+ // Reserved for another net
+ if (nwd.reserved_net != -1 && nwd.reserved_net != net->udata)
+ continue;
+ // Don't allow the same wire to be bound to the same net with a different driving pip
+ auto fnd_wire = nd.wires.find(next);
+ if (fnd_wire != nd.wires.end() && fnd_wire->second.first != dh)
+ continue;
+ if (!thread_test_wire(t, nwd))
+ continue; // thread safety issue
+ WireScore next_score;
+ next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, dh, crit_weight);
+ next_score.togo_cost =
+ cfg.estimate_weight * get_togo_cost(net, i, next_idx, dst_wire, false, crit_weight);
+ set_visited_fwd(t, next_idx, dh);
+ t.fwd_queue.push(QueuedWire(next_idx, next_score, t.rng.rng()));
+ }
+ }
+ if (!t.bwd_queue.empty()) {
+ // Explore backwards
+ auto curr = t.bwd_queue.top();
+ t.bwd_queue.pop();
+ ++explored;
+ if (was_visited_fwd(curr.wire)) {
+ // Meet in the middle; done
+ midpoint_wire = curr.wire;
+ break;
+ }
+ auto &curr_data = flat_wires.at(curr.wire);
+ // Don't allow the same wire to be bound to the same net with a different driving pip
+ PipId bound_pip;
+ auto fnd_wire = nd.wires.find(curr_data.w);
+ if (fnd_wire != nd.wires.end())
+ bound_pip = fnd_wire->second.first;
+
+ for (PipId uh : ctx->getPipsUphill(curr_data.w)) {
+ if (bound_pip != PipId() && bound_pip != uh)
+ continue;
+ if (is_bb && !hit_test_pip(nd.bb, ctx->getPipLocation(uh)))
+ continue;
+ if (!ctx->checkPipAvailForNet(uh, net))
+ continue;
+ WireId next = ctx->getPipSrcWire(uh);
+ int next_idx = wire_to_idx.at(next);
+ if (was_visited_bwd(next_idx)) {
+ // Don't expand the same node twice.
+ continue;
+ }
+ auto &nwd = flat_wires.at(next_idx);
+ if (nwd.unavailable)
+ continue;
+ // Reserved for another net
+ if (nwd.reserved_net != -1 && nwd.reserved_net != net->udata)
+ continue;
+ if (!thread_test_wire(t, nwd))
+ continue; // thread safety issue
+ WireScore next_score;
+ next_score.cost = curr.score.cost + score_wire_for_arc(net, i, phys_pin, next, uh, crit_weight);
+ next_score.togo_cost =
+ cfg.estimate_weight * get_togo_cost(net, i, next_idx, src_wire, true, crit_weight);
+ set_visited_bwd(t, next_idx, uh);
+ t.bwd_queue.push(QueuedWire(next_idx, next_score, t.rng.rng()));
+ }
+ }
+ }
+ if (midpoint_wire != -1)
+ break;
+ }
+ ArcRouteResult result = ARC_SUCCESS;
+ if (midpoint_wire != -1) {
+ ROUTE_LOG_DBG(" Routed (explored %d wires): ", explored);
+ int cursor_bwd = midpoint_wire;
+ while (was_visited_fwd(cursor_bwd)) {
+ PipId pip = flat_wires.at(cursor_bwd).pip_fwd;
+ if (pip == PipId() && cursor_bwd != src_wire_idx)
+ break;
+ bind_pip_internal(nd, i, cursor_bwd, pip);
+ if (ctx->debug && !is_mt) {
+ auto &wd = flat_wires.at(cursor_bwd);
+ ROUTE_LOG_DBG(" fwd wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(wd.w),
+ wd.curr_cong - 1, wd.hist_cong_cost, nd.wires.at(wd.w).second);
+ }
+ if (pip == PipId()) {
+ break;
+ }
+ ROUTE_LOG_DBG(" fwd pip: %s (%d, %d)\n", ctx->nameOfPip(pip), ctx->getPipLocation(pip).x,
+ ctx->getPipLocation(pip).y);
+ cursor_bwd = wire_to_idx.at(ctx->getPipSrcWire(pip));
+ }
+
+ while (cursor_bwd != src_wire_idx) {
+ // Tack onto existing routing
+ WireId bwd_w = flat_wires.at(cursor_bwd).w;
+ if (!nd.wires.count(bwd_w))
+ break;
+ auto &bound = nd.wires.at(bwd_w);
+ PipId pip = bound.first;
+ if (ctx->debug && !is_mt) {
+ auto &wd = flat_wires.at(cursor_bwd);
+ ROUTE_LOG_DBG(" ext wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(wd.w),
+ wd.curr_cong - 1, wd.hist_cong_cost, bound.second);
+ }
+ bind_pip_internal(nd, i, cursor_bwd, pip);
+ if (pip == PipId())
+ break;
+ cursor_bwd = wire_to_idx.at(ctx->getPipSrcWire(pip));
+ }
+
+ NPNR_ASSERT(cursor_bwd == src_wire_idx);
+
+ int cursor_fwd = midpoint_wire;
+ while (was_visited_bwd(cursor_fwd)) {
+ PipId pip = flat_wires.at(cursor_fwd).pip_bwd;
+ if (pip == PipId()) {
+ break;
+ }
+ ROUTE_LOG_DBG(" bwd pip: %s (%d, %d)\n", ctx->nameOfPip(pip), ctx->getPipLocation(pip).x,
+ ctx->getPipLocation(pip).y);
+ cursor_fwd = wire_to_idx.at(ctx->getPipDstWire(pip));
+ bind_pip_internal(nd, i, cursor_fwd, pip);
+ if (ctx->debug && !is_mt) {
+ auto &wd = flat_wires.at(cursor_fwd);
+ ROUTE_LOG_DBG(" bwd wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(wd.w),
+ wd.curr_cong - 1, wd.hist_cong_cost, nd.wires.at(wd.w).second);
+ }
+ }
+ NPNR_ASSERT(cursor_fwd == dst_wire_idx);
+
+ update_wire_by_loc(t, net, i, phys_pin, is_mt);
+ t.processed_sinks.insert(dst_wire);
+ ad.routed = true;
+ auto arc_end = std::chrono::high_resolution_clock::now();
+ ROUTE_LOG_DBG("Routing arc %d of net '%s' (is_bb = %d) took %02fs\n", i.idx(), ctx->nameOf(net), is_bb,
+ std::chrono::duration<float>(arc_end - arc_start).count());
+ } else {
+ auto arc_end = std::chrono::high_resolution_clock::now();
+ ROUTE_LOG_DBG("Failed routing arc %d of net '%s' (is_bb = %d) took %02fs\n", i.idx(), ctx->nameOf(net),
+ is_bb, std::chrono::duration<float>(arc_end - arc_start).count());
+ result = ARC_RETRY_WITHOUT_BB;
+ }
+ reset_wires(t);
+ return result;
+ }
+#undef ARC_ERR
+
+ bool route_net(ThreadContext &t, NetInfo *net, bool is_mt)
+ {
+
+#ifdef ARCH_ECP5
+ if (net->is_global)
+ return true;
+#endif
+
+ ROUTE_LOG_DBG("Routing net '%s'...\n", ctx->nameOf(net));
+
+ auto rstart = std::chrono::high_resolution_clock::now();
+
+ // Nothing to do if net is undriven
+ if (net->driver.cell == nullptr)
+ return true;
+
+ bool have_failures = false;
+ t.processed_sinks.clear();
+ t.route_arcs.clear();
+ t.wire_by_loc.clear();
+ t.in_wire_by_loc.clear();
+ auto &nd = nets.at(net->udata);
+ bool failed_slack = false;
+ for (auto usr : net->users.enumerate())
+ failed_slack |= arc_failed_slack(net, usr.index);
+ for (auto usr : net->users.enumerate()) {
+ auto &ad = nd.arcs.at(usr.index.idx());
+ for (size_t j = 0; j < ad.size(); j++) {
+ // Ripup failed arcs to start with
+ // Check if arc is already legally routed
+ if (!failed_slack && check_arc_routing(net, usr.index, j)) {
+ update_wire_by_loc(t, net, usr.index, j, true);
+ continue;
+ }
+
+ // Ripup arc to start with
+ ripup_arc(net, usr.index, j);
+ t.route_arcs.emplace_back(usr.index, j);
+ }
+ }
+ // Route most critical arc first
+ std::stable_sort(t.route_arcs.begin(), t.route_arcs.end(),
+ [&](std::pair<store_index<PortRef>, size_t> a, std::pair<store_index<PortRef>, size_t> b) {
+ return get_arc_crit(net, a.first) > get_arc_crit(net, b.first);
+ });
+ for (auto a : t.route_arcs) {
+ auto res1 = route_arc(t, net, a.first, a.second, is_mt, true);
+ if (res1 == ARC_FATAL)
+ return false; // Arc failed irrecoverably
+ else if (res1 == ARC_RETRY_WITHOUT_BB) {
+ if (is_mt) {
+ // Can't break out of bounding box in multi-threaded mode, so mark this arc as a failure
+ have_failures = true;
+ } else {
+ // Attempt a re-route without the bounding box constraint
+ ROUTE_LOG_DBG("Rerouting arc %d.%d of net '%s' without bounding box, possible tricky routing...\n",
+ a.first.idx(), int(a.second), ctx->nameOf(net));
+ auto res2 = route_arc(t, net, a.first, a.second, is_mt, false);
+ // If this also fails, no choice but to give up
+ if (res2 != ARC_SUCCESS) {
+ if (ctx->debug) {
+ log_info("Pre-bound routing: \n");
+ for (auto &wire_pair : net->wires) {
+ log(" %s", ctx->nameOfWire(wire_pair.first));
+ if (wire_pair.second.pip != PipId())
+ log(" %s", ctx->nameOfPip(wire_pair.second.pip));
+ log("\n");
+ }
+ }
+ log_error("Failed to route arc %d.%d of net '%s', from %s to %s.\n", a.first.idx(),
+ int(a.second), ctx->nameOf(net), ctx->nameOfWire(ctx->getNetinfoSourceWire(net)),
+ ctx->nameOfWire(ctx->getNetinfoSinkWire(net, net->users.at(a.first), a.second)));
+ }
+ }
+ }
+ }
+ if (cfg.perf_profile) {
+ auto rend = std::chrono::high_resolution_clock::now();
+ nets.at(net->udata).total_route_us +=
+ (std::chrono::duration_cast<std::chrono::microseconds>(rend - rstart).count());
+ }
+ return !have_failures;
+ }
+#undef ROUTE_LOG_DBG
+
+ int total_wire_use = 0;
+ int overused_wires = 0;
+ int total_overuse = 0;
+ std::vector<int> route_queue;
+ std::set<int> failed_nets;
+
+ void update_congestion()
+ {
+ total_overuse = 0;
+ overused_wires = 0;
+ total_wire_use = 0;
+ failed_nets.clear();
+ pool<WireId> already_updated;
+ for (size_t i = 0; i < nets.size(); i++) {
+ auto &nd = nets.at(i);
+ for (const auto &w : nd.wires) {
+ ++total_wire_use;
+ auto &wd = wire_data(w.first);
+ if (wd.curr_cong > 1) {
+ if (already_updated.count(w.first)) {
+ ++total_overuse;
+ } else {
+ if (curr_cong_weight > 0)
+ wd.hist_cong_cost =
+ std::min(1e9, wd.hist_cong_cost + (wd.curr_cong - 1) * hist_cong_weight);
+ already_updated.insert(w.first);
+ ++overused_wires;
+ }
+ failed_nets.insert(i);
+ }
+ }
+ }
+ for (int n : failed_nets) {
+ auto &net_data = nets.at(n);
+ ++net_data.fail_count;
+ if ((net_data.fail_count % 3) == 0) {
+ // Every three times a net fails to route, expand the bounding box to increase the search space
+#ifndef ARCH_MISTRAL
+ // This patch seems to make thing worse for CycloneV, as it slows down the resolution of TD congestion,
+ // disable it
+ net_data.bb.x0 = std::max(net_data.bb.x0 - 1, 0);
+ net_data.bb.y0 = std::max(net_data.bb.y0 - 1, 0);
+ net_data.bb.x1 = std::min(net_data.bb.x1 + 1, ctx->getGridDimX());
+ net_data.bb.y1 = std::min(net_data.bb.y1 + 1, ctx->getGridDimY());
+#endif
+ }
+ }
+ }
+
+ bool bind_and_check(NetInfo *net, store_index<PortRef> usr_idx, int phys_pin)
+ {
+#ifdef ARCH_ECP5
+ if (net->is_global)
+ return true;
+#endif
+ bool success = true;
+ auto &nd = nets.at(net->udata);
+ auto &ad = nd.arcs.at(usr_idx.idx()).at(phys_pin);
+ auto &usr = net->users.at(usr_idx);
+ WireId src = ctx->getNetinfoSourceWire(net);
+ // Skip routes with no source
+ if (src == WireId())
+ return true;
+ WireId dst = ctx->getNetinfoSinkWire(net, usr, phys_pin);
+ if (dst == WireId())
+ return true;
+
+ // Skip routes where there is no routing (special cases)
+ if (!ad.routed) {
+ if ((src == dst) && ctx->getBoundWireNet(dst) != net)
+ ctx->bindWire(src, net, STRENGTH_WEAK);
+ if (ctx->debug) {
+ log("Net %s not routed, not binding\n", ctx->nameOf(net));
+ }
+ return true;
+ }
+
+ WireId cursor = dst;
+
+ std::vector<PipId> to_bind;
+
+ while (cursor != src) {
+ if (!ctx->checkWireAvail(cursor)) {
+ NetInfo *bound_net = ctx->getBoundWireNet(cursor);
+ if (bound_net != net) {
+ if (ctx->verbose) {
+ if (bound_net != nullptr) {
+ log_info("Failed to bind wire %s to net %s, bound to net %s\n", ctx->nameOfWire(cursor),
+ net->name.c_str(ctx), bound_net->name.c_str(ctx));
+ } else {
+ log_info("Failed to bind wire %s to net %s, bound net nullptr\n", ctx->nameOfWire(cursor),
+ net->name.c_str(ctx));
+ }
+ }
+ success = false;
+ break;
+ }
+ }
+ if (!nd.wires.count(cursor)) {
+ log("Failure details:\n");
+ log(" Cursor: %s\n", ctx->nameOfWire(cursor));
+ log_error("Internal error; incomplete route tree for arc %d of net %s.\n", usr_idx.idx(),
+ ctx->nameOf(net));
+ }
+ PipId p = nd.wires.at(cursor).first;
+ if (ctx->checkPipAvailForNet(p, net)) {
+ NetInfo *bound_net = ctx->getBoundPipNet(p);
+ if (bound_net == nullptr) {
+ to_bind.push_back(p);
+ }
+ } else {
+ if (ctx->verbose) {
+ log_info("Failed to bind pip %s to net %s\n", ctx->nameOfPip(p), net->name.c_str(ctx));
+ }
+ success = false;
+ break;
+ }
+ cursor = ctx->getPipSrcWire(p);
+ }
+
+ if (success) {
+ if (ctx->getBoundWireNet(src) == nullptr)
+ ctx->bindWire(src, net, STRENGTH_WEAK);
+ for (auto tb : to_bind)
+ ctx->bindPip(tb, net, STRENGTH_WEAK);
+ } else {
+ ripup_arc(net, usr_idx, phys_pin);
+ failed_nets.insert(net->udata);
+ }
+ return success;
+ }
+
+ int arch_fail = 0;
+ bool bind_and_check_all()
+ {
+ // Make sure arch is internally consistent before we mess with it.
+ ctx->check();
+
+ bool success = true;
+ std::vector<WireId> net_wires;
+ for (auto net : nets_by_udata) {
+#ifdef ARCH_ECP5
+ if (net->is_global)
+ continue;
+#endif
+ // Ripup wires and pips used by the net in nextpnr's structures
+ net_wires.clear();
+ for (auto &w : net->wires) {
+ if (w.second.strength <= STRENGTH_STRONG) {
+ net_wires.push_back(w.first);
+ } else if (ctx->debug) {
+ log("Net %s didn't rip up wire %s because strength was %d\n", ctx->nameOf(net),
+ ctx->nameOfWire(w.first), w.second.strength);
+ }
+ }
+ for (auto w : net_wires)
+ ctx->unbindWire(w);
+
+ if (ctx->debug) {
+ log("Ripped up %zu wires on net %s\n", net_wires.size(), ctx->nameOf(net));
+ }
+
+ // Bind the arcs using the routes we have discovered
+ for (auto usr : net->users.enumerate()) {
+ for (size_t phys_pin = 0; phys_pin < nets.at(net->udata).arcs.at(usr.index.idx()).size(); phys_pin++) {
+ if (!bind_and_check(net, usr.index, phys_pin)) {
+ ++arch_fail;
+ success = false;
+ }
+ }
+ }
+ }
+
+ // Check that the arch is still internally consistent!
+ ctx->check();
+
+ return success;
+ }
+
+ void write_wiretype_heatmap(std::ostream &out)
+ {
+ dict<IdString, std::vector<int>> cong_by_type;
+ size_t max_cong = 0;
+ // Build histogram
+ for (auto &wd : flat_wires) {
+ size_t val = wd.curr_cong;
+ IdString type = ctx->getWireType(wd.w);
+ max_cong = std::max(max_cong, val);
+ if (cong_by_type[type].size() <= max_cong)
+ cong_by_type[type].resize(max_cong + 1);
+ cong_by_type[type].at(val) += 1;
+ }
+ // Write csv
+ out << "type,";
+ for (size_t i = 0; i <= max_cong; i++)
+ out << "bound=" << i << ",";
+ out << std::endl;
+ for (auto &ty : cong_by_type) {
+ out << ctx->nameOf(ty.first) << ",";
+ for (int count : ty.second)
+ out << count << ",";
+ out << std::endl;
+ }
+ }
+
+ int mid_x = 0, mid_y = 0;
+
+ void partition_nets()
+ {
+ // Create a histogram of positions in X and Y positions
+ std::map<int, int> cxs, cys;
+ for (auto &n : nets) {
+ if (n.cx != -1)
+ ++cxs[n.cx];
+ if (n.cy != -1)
+ ++cys[n.cy];
+ }
+ // 4-way split for now
+ int accum_x = 0, accum_y = 0;
+ int halfway = int(nets.size()) / 2;
+ for (auto &p : cxs) {
+ if (accum_x < halfway && (accum_x + p.second) >= halfway)
+ mid_x = p.first;
+ accum_x += p.second;
+ }
+ for (auto &p : cys) {
+ if (accum_y < halfway && (accum_y + p.second) >= halfway)
+ mid_y = p.first;
+ accum_y += p.second;
+ }
+ if (ctx->verbose) {
+ log_info(" x splitpoint: %d\n", mid_x);
+ log_info(" y splitpoint: %d\n", mid_y);
+ }
+ std::vector<int> bins(5, 0);
+ for (auto &n : nets) {
+ if (n.bb.x0 < mid_x && n.bb.x1 < mid_x && n.bb.y0 < mid_y && n.bb.y1 < mid_y)
+ ++bins[0]; // TL
+ else if (n.bb.x0 >= mid_x && n.bb.x1 >= mid_x && n.bb.y0 < mid_y && n.bb.y1 < mid_y)
+ ++bins[1]; // TR
+ else if (n.bb.x0 < mid_x && n.bb.x1 < mid_x && n.bb.y0 >= mid_y && n.bb.y1 >= mid_y)
+ ++bins[2]; // BL
+ else if (n.bb.x0 >= mid_x && n.bb.x1 >= mid_x && n.bb.y0 >= mid_y && n.bb.y1 >= mid_y)
+ ++bins[3]; // BR
+ else
+ ++bins[4]; // cross-boundary
+ }
+ if (ctx->verbose)
+ for (int i = 0; i < 5; i++)
+ log_info(" bin %d N=%d\n", i, bins[i]);
+ }
+
+ void router_thread(ThreadContext &t, bool is_mt)
+ {
+ for (auto n : t.route_nets) {
+ bool result = route_net(t, n, is_mt);
+ if (!result)
+ t.failed_nets.push_back(n);
+ }
+ }
+
+ void do_route()
+ {
+ // Don't multithread if fewer than 200 nets (heuristic)
+ if (route_queue.size() < 200) {
+ ThreadContext st;
+ st.rng.rngseed(ctx->rng64());
+ st.bb = ArcBounds(0, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
+ for (size_t j = 0; j < route_queue.size(); j++) {
+ route_net(st, nets_by_udata[route_queue[j]], false);
+ }
+ return;
+ }
+ const int Nq = 4, Nv = 2, Nh = 2;
+ const int N = Nq + Nv + Nh;
+ std::vector<ThreadContext> tcs(N + 1);
+ for (auto &th : tcs) {
+ th.rng.rngseed(ctx->rng64());
+ }
+ int le_x = mid_x;
+ int rs_x = mid_x;
+ int le_y = mid_y;
+ int rs_y = mid_y;
+ // Set up thread bounding boxes
+ tcs.at(0).bb = ArcBounds(0, 0, mid_x, mid_y);
+ tcs.at(1).bb = ArcBounds(mid_x + 1, 0, std::numeric_limits<int>::max(), le_y);
+ tcs.at(2).bb = ArcBounds(0, mid_y + 1, mid_x, std::numeric_limits<int>::max());
+ tcs.at(3).bb =
+ ArcBounds(mid_x + 1, mid_y + 1, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
+
+ tcs.at(4).bb = ArcBounds(0, 0, std::numeric_limits<int>::max(), mid_y);
+ tcs.at(5).bb = ArcBounds(0, mid_y + 1, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
+
+ tcs.at(6).bb = ArcBounds(0, 0, mid_x, std::numeric_limits<int>::max());
+ tcs.at(7).bb = ArcBounds(mid_x + 1, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
+
+ tcs.at(8).bb = ArcBounds(0, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
+
+ for (auto n : route_queue) {
+ auto &nd = nets.at(n);
+ auto ni = nets_by_udata.at(n);
+ int bin = N;
+ // Quadrants
+ if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y)
+ bin = 0;
+ else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 < le_y && nd.bb.y1 < le_y)
+ bin = 1;
+ else if (nd.bb.x0 < le_x && nd.bb.x1 < le_x && nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y)
+ bin = 2;
+ else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x && nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y)
+ bin = 3;
+ // Vertical split
+ else if (nd.bb.y0 < le_y && nd.bb.y1 < le_y)
+ bin = Nq + 0;
+ else if (nd.bb.y0 >= rs_y && nd.bb.y1 >= rs_y)
+ bin = Nq + 1;
+ // Horizontal split
+ else if (nd.bb.x0 < le_x && nd.bb.x1 < le_x)
+ bin = Nq + Nv + 0;
+ else if (nd.bb.x0 >= rs_x && nd.bb.x1 >= rs_x)
+ bin = Nq + Nv + 1;
+ tcs.at(bin).route_nets.push_back(ni);
+ }
+ if (ctx->verbose)
+ log_info("%d/%d nets not multi-threadable\n", int(tcs.at(N).route_nets.size()), int(route_queue.size()));
+#ifdef NPNR_DISABLE_THREADS
+ // Singlethreaded routing - quadrants
+ for (int i = 0; i < Nq; i++) {
+ router_thread(tcs.at(i), /*is_mt=*/false);
+ }
+ // Vertical splits
+ for (int i = Nq; i < Nq + Nv; i++) {
+ router_thread(tcs.at(i), /*is_mt=*/false);
+ }
+ // Horizontal splits
+ for (int i = Nq + Nv; i < Nq + Nv + Nh; i++) {
+ router_thread(tcs.at(i), /*is_mt=*/false);
+ }
+#else
+ // Multithreaded part of routing - quadrants
+ std::vector<boost::thread> threads;
+ for (int i = 0; i < Nq; i++) {
+ threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i), /*is_mt=*/true); });
+ }
+ for (auto &t : threads)
+ t.join();
+ threads.clear();
+ // Vertical splits
+ for (int i = Nq; i < Nq + Nv; i++) {
+ threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i), /*is_mt=*/true); });
+ }
+ for (auto &t : threads)
+ t.join();
+ threads.clear();
+ // Horizontal splits
+ for (int i = Nq + Nv; i < Nq + Nv + Nh; i++) {
+ threads.emplace_back([this, &tcs, i]() { router_thread(tcs.at(i), /*is_mt=*/true); });
+ }
+ for (auto &t : threads)
+ t.join();
+ threads.clear();
+#endif
+ // Singlethreaded part of routing - nets that cross partitions
+ // or don't fit within bounding box
+ for (auto st_net : tcs.at(N).route_nets)
+ route_net(tcs.at(N), st_net, false);
+ // Failed nets
+ for (int i = 0; i < N; i++)
+ for (auto fail : tcs.at(i).failed_nets)
+ route_net(tcs.at(N), fail, false);
+ }
+
+ delay_t get_route_delay(int net, store_index<PortRef> usr_idx, int phys_idx)
+ {
+ auto &nd = nets.at(net);
+ auto &ad = nd.arcs.at(usr_idx.idx()).at(phys_idx);
+ WireId cursor = ad.sink_wire;
+ if (cursor == WireId() || nd.src_wire == WireId())
+ return 0;
+ delay_t delay = 0;
+ while (true) {
+ delay += ctx->getWireDelay(cursor).maxDelay();
+ if (!nd.wires.count(cursor))
+ break;
+ auto &bound = nd.wires.at(cursor);
+ if (bound.first == PipId())
+ break;
+ delay += ctx->getPipDelay(bound.first).maxDelay();
+ cursor = ctx->getPipSrcWire(bound.first);
+ }
+ NPNR_ASSERT(cursor == nd.src_wire);
+ return delay;
+ }
+
+ void update_route_delays()
+ {
+ for (int net : route_queue) {
+ NetInfo *ni = nets_by_udata.at(net);
+#ifdef ARCH_ECP5
+ if (ni->is_global)
+ continue;
+#endif
+ auto &nd = nets.at(net);
+ for (auto usr : ni->users.enumerate()) {
+ delay_t arc_delay = 0;
+ for (int j = 0; j < int(nd.arcs.at(usr.index.idx()).size()); j++)
+ arc_delay = std::max(arc_delay, get_route_delay(net, usr.index, j));
+ tmg.set_route_delay(CellPortKey(usr.value), DelayPair(arc_delay));
+ }
+ }
+ }
+
+ void operator()()
+ {
+ log_info("Running router2...\n");
+ log_info("Setting up routing resources...\n");
+ auto rstart = std::chrono::high_resolution_clock::now();
+ setup_nets();
+ setup_wires();
+ find_all_reserved_wires();
+ partition_nets();
+ curr_cong_weight = cfg.init_curr_cong_weight;
+ hist_cong_weight = cfg.hist_cong_weight;
+ ThreadContext st;
+ int iter = 1;
+
+ ScopeLock<Context> lock(ctx);
+
+ for (size_t i = 0; i < nets_by_udata.size(); i++)
+ route_queue.push_back(i);
+
+ timing_driven = ctx->setting<bool>("timing_driven");
+ if (ctx->settings.count(ctx->id("router/tmg_ripup")))
+ timing_driven_ripup = timing_driven && ctx->setting<bool>("router/tmg_ripup");
+ else
+ timing_driven_ripup = false;
+ log_info("Running main router loop...\n");
+ if (timing_driven)
+ tmg.run(true);
+ do {
+ ctx->sorted_shuffle(route_queue);
+
+ if (timing_driven && int(route_queue.size()) >= 30) {
+ for (auto n : route_queue) {
+ NetInfo *ni = nets_by_udata.at(n);
+ auto &net = nets.at(n);
+ net.max_crit = 0;
+ for (auto &usr : ni->users) {
+ float c = tmg.get_criticality(CellPortKey(usr));
+ net.max_crit = std::max(net.max_crit, c);
+ }
+ }
+ std::stable_sort(route_queue.begin(), route_queue.end(),
+ [&](int na, int nb) { return nets.at(na).max_crit > nets.at(nb).max_crit; });
+ }
+
+ do_route();
+ update_route_delays();
+ route_queue.clear();
+ update_congestion();
+
+ if (!cfg.heatmap.empty()) {
+ std::string filename(cfg.heatmap + "_" + std::to_string(iter) + ".csv");
+ std::ofstream cong_map(filename);
+ if (!cong_map)
+ log_error("Failed to open wiretype heatmap %s for writing.\n", filename.c_str());
+ write_wiretype_heatmap(cong_map);
+ log_info(" wrote wiretype heatmap to %s.\n", filename.c_str());
+ }
+ int tmgfail = 0;
+ if (timing_driven)
+ tmg.run(false);
+ if (timing_driven_ripup && iter < 500) {
+ for (size_t i = 0; i < nets_by_udata.size(); i++) {
+ NetInfo *ni = nets_by_udata.at(i);
+ for (auto usr : ni->users.enumerate()) {
+ if (arc_failed_slack(ni, usr.index)) {
+ failed_nets.insert(i);
+ ++tmgfail;
+ }
+ }
+ }
+ }
+ if (overused_wires == 0 && tmgfail == 0) {
+ // Try and actually bind nextpnr Arch API wires
+ bind_and_check_all();
+ }
+ for (auto cn : failed_nets)
+ route_queue.push_back(cn);
+ if (timing_driven_ripup)
+ log_info(" iter=%d wires=%d overused=%d overuse=%d tmgfail=%d archfail=%s\n", iter, total_wire_use,
+ overused_wires, total_overuse, tmgfail,
+ (overused_wires > 0 || tmgfail > 0) ? "NA" : std::to_string(arch_fail).c_str());
+ else
+ log_info(" iter=%d wires=%d overused=%d overuse=%d archfail=%s\n", iter, total_wire_use,
+ overused_wires, total_overuse,
+ (overused_wires > 0 || tmgfail > 0) ? "NA" : std::to_string(arch_fail).c_str());
+ ++iter;
+ if (curr_cong_weight < 1e9)
+ curr_cong_weight += cfg.curr_cong_mult;
+ } while (!failed_nets.empty());
+ if (cfg.perf_profile) {
+ std::vector<std::pair<int, IdString>> nets_by_runtime;
+ for (auto &n : nets_by_udata) {
+ nets_by_runtime.emplace_back(nets.at(n->udata).total_route_us, n->name);
+ }
+ std::sort(nets_by_runtime.begin(), nets_by_runtime.end(), std::greater<std::pair<int, IdString>>());
+ log_info("1000 slowest nets by runtime:\n");
+ for (int i = 0; i < std::min(int(nets_by_runtime.size()), 1000); i++) {
+ log(" %80s %6d %.1fms\n", nets_by_runtime.at(i).second.c_str(ctx),
+ int(ctx->nets.at(nets_by_runtime.at(i).second)->users.entries()),
+ nets_by_runtime.at(i).first / 1000.0);
+ }
+ }
+ auto rend = std::chrono::high_resolution_clock::now();
+ log_info("Router2 time %.02fs\n", std::chrono::duration<float>(rend - rstart).count());
+
+ log_info("Running router1 to check that route is legal...\n");
+
+ lock.unlock_early();
+
+ router1(ctx, Router1Cfg(ctx));
+ }
+};
+} // namespace
+
+void router2(Context *ctx, const Router2Cfg &cfg)
+{
+ Router2 rt(ctx, cfg);
+ rt.ctx = ctx;
+ rt();
+}
+
+Router2Cfg::Router2Cfg(Context *ctx)
+{
+ backwards_max_iter = ctx->setting<int>("router2/bwdMaxIter", 20);
+ global_backwards_max_iter = ctx->setting<int>("router2/glbBwdMaxIter", 200);
+ bb_margin_x = ctx->setting<int>("router2/bbMargin/x", 3);
+ bb_margin_y = ctx->setting<int>("router2/bbMargin/y", 3);
+ ipin_cost_adder = ctx->setting<float>("router2/ipinCostAdder", 0.0f);
+ bias_cost_factor = ctx->setting<float>("router2/biasCostFactor", 0.25f);
+ init_curr_cong_weight = ctx->setting<float>("router2/initCurrCongWeight", 0.5f);
+ hist_cong_weight = ctx->setting<float>("router2/histCongWeight", 1.0f);
+ curr_cong_mult = ctx->setting<float>("router2/currCongWeightMult", 2.0f);
+ estimate_weight = ctx->setting<float>("router2/estimateWeight", 1.25f);
+ perf_profile = ctx->setting<bool>("router2/perfProfile", false);
+ if (ctx->settings.count(ctx->id("router2/heatmap")))
+ heatmap = ctx->settings.at(ctx->id("router2/heatmap")).as_string();
+ else
+ heatmap = "";
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/common/route/router2.h b/common/route/router2.h
new file mode 100644
index 00000000..629453c6
--- /dev/null
+++ b/common/route/router2.h
@@ -0,0 +1,66 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2019 gatecat <gatecat@ds0.me>
+ *
+ * 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.
+ *
+ */
+
+#include "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+inline float default_base_cost(Context *ctx, WireId wire, PipId pip, float crit_weight)
+{
+ (void)crit_weight; // unused
+ return ctx->getDelayNS(ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(wire).maxDelay() +
+ ctx->getDelayEpsilon());
+}
+
+struct Router2Cfg
+{
+ Router2Cfg(Context *ctx);
+
+ // Maximum iterations for backwards routing attempt
+ int backwards_max_iter;
+ // Maximum iterations for backwards routing attempt for global nets
+ int global_backwards_max_iter;
+ // Padding added to bounding boxes to account for imperfect routing,
+ // congestion, etc
+ int bb_margin_x, bb_margin_y;
+ // Cost factor added to input pin wires; effectively reduces the
+ // benefit of sharing interconnect
+ float ipin_cost_adder;
+ // Cost factor for "bias" towards center location of net
+ float bias_cost_factor;
+ // Starting current and historical congestion cost factor
+ float init_curr_cong_weight, hist_cong_weight;
+ // Current congestion cost multiplier
+ float curr_cong_mult;
+
+ // Weight given to delay estimate in A*. Higher values
+ // mean faster and more directed routing, at the risk
+ // of choosing a less congestion/delay-optimal route
+ float estimate_weight;
+
+ // Print additional performance profiling information
+ bool perf_profile = false;
+
+ std::string heatmap;
+ std::function<float(Context *ctx, WireId wire, PipId pip, float crit_weight)> get_base_cost = default_base_cost;
+};
+
+void router2(Context *ctx, const Router2Cfg &cfg);
+
+NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 01:01:55 +0000