Improvements in router

Signed-off-by: Clifford Wolf <clifford@clifford.at>

2 files changed, 149 insertions, 64 deletions

diff --git a/common/nextpnr.h b/common/nextpnr.h
index 5ccbf057..db6901fe 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -289,6 +289,7 @@ NEXTPNR_NAMESPACE_BEGIN
 struct Context : Arch
 {
     bool verbose = false;
+    bool debug = false;
     bool force = false;
 
     Context(ArchArgs args) : Arch(args) {}
diff --git a/common/route.cc b/common/route.cc
index 6a410397..cf87ebaa 100644
--- a/common/route.cc
+++ b/common/route.cc
@@ -23,6 +23,38 @@
 #include "log.h"
 #include "route.h"
 
+namespace std {
+template <>
+struct hash<pair<NEXTPNR_NAMESPACE_PREFIX IdString,
+                 NEXTPNR_NAMESPACE_PREFIX WireId>>
+{
+    std::size_t
+    operator()(const pair<NEXTPNR_NAMESPACE_PREFIX IdString,
+                          NEXTPNR_NAMESPACE_PREFIX WireId> &arg) const noexcept
+    {
+        std::size_t seed = hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(arg.first);
+        seed ^= hash<NEXTPNR_NAMESPACE_PREFIX WireId>()(arg.second) +
+                0x9e3779b9 + (seed << 6) + (seed >> 2);
+        return seed;
+    }
+};
+
+template <>
+struct hash<
+        pair<NEXTPNR_NAMESPACE_PREFIX IdString, NEXTPNR_NAMESPACE_PREFIX PipId>>
+{
+    std::size_t
+    operator()(const pair<NEXTPNR_NAMESPACE_PREFIX IdString,
+                          NEXTPNR_NAMESPACE_PREFIX PipId> &arg) const noexcept
+    {
+        std::size_t seed = hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(arg.first);
+        seed ^= hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(arg.second) +
+                0x9e3779b9 + (seed << 6) + (seed >> 2);
+        return seed;
+    }
+};
+} // namespace std
+
 namespace {
 
 USING_NEXTPNR_NAMESPACE
@@ -46,6 +78,12 @@ struct QueuedWire
     };
 };
 
+struct RipupScoreboard
+{
+    std::unordered_map<std::pair<IdString, WireId>, int> wireScores;
+    std::unordered_map<std::pair<IdString, PipId>, int> pipScores;
+};
+
 void ripup_net(Context *ctx, IdString net_name)
 {
     auto net_info = ctx->nets.at(net_name);
@@ -62,7 +100,9 @@ void ripup_net(Context *ctx, IdString net_name)
 struct Router
 {
     Context *ctx;
+    RipupScoreboard scores;
     IdString net_name;
+
     bool ripup;
     delay_t ripup_penalty;
 
@@ -99,31 +139,41 @@ struct Router
             queue.pop();
 
             for (auto pip : ctx->getPipsDownhill(qw.wire)) {
-                delay_t next_delay = qw.delay;
-                IdString ripupNet = net_name;
+                delay_t next_delay =
+                        qw.delay + ctx->getPipDelay(pip).avgDelay();
+                WireId next_wire = ctx->getPipDstWire(pip);
+                bool foundRipupNet = false;
                 visitCnt++;
 
-                if (!ctx->checkPipAvail(pip)) {
+                if (!ctx->checkWireAvail(next_wire)) {
                     if (!ripup)
                         continue;
-                    ripupNet = ctx->getPipNet(pip, true);
-                    if (ripupNet == net_name)
+                    IdString ripupWireNet = ctx->getWireNet(next_wire, true);
+                    if (ripupWireNet == net_name || ripupWireNet == IdString())
                         continue;
+                    auto it = scores.wireScores.find(
+                            std::make_pair(ripupWireNet, next_wire));
+                    if (it != scores.wireScores.end())
+                        next_delay += it->second * ripup_penalty;
+                    foundRipupNet = true;
                 }
 
-                WireId next_wire = ctx->getPipDstWire(pip);
-                next_delay += ctx->getPipDelay(pip).avgDelay();
-
-                if (!ctx->checkWireAvail(next_wire)) {
+                if (!ctx->checkPipAvail(pip)) {
                     if (!ripup)
                         continue;
-                    ripupNet = ctx->getWireNet(next_wire, true);
-                    if (ripupNet == net_name)
+                    IdString ripupPipNet = ctx->getPipNet(pip, true);
+                    if (ripupPipNet == net_name || ripupPipNet == IdString())
                         continue;
+                    auto it = scores.pipScores.find(
+                            std::make_pair(ripupPipNet, pip));
+                    if (it != scores.pipScores.end())
+                        next_delay += it->second * ripup_penalty;
+                    foundRipupNet = true;
                 }
 
-                if (ripupNet != net_name)
+                if (foundRipupNet)
                     next_delay += ripup_penalty;
+
                 assert(next_delay >= 0);
 
                 if (visited.count(next_wire)) {
@@ -131,7 +181,7 @@ struct Router
                         next_delay + ctx->getDelayEpsilon())
                         continue;
 #if 0 // FIXME
-                    if (ctx->verbose)
+                    if (ctx->debug)
                         log("Found better route to %s. Old vs new delay "
                             "estimate: %.3f %.3f\n",
                             ctx->getWireName(next_wire).c_str(),
@@ -154,16 +204,17 @@ struct Router
         }
     }
 
-    Router(Context *ctx, WireId src_wire, WireId dst_wire, bool ripup = false,
-           delay_t ripup_penalty = 0)
-            : ctx(ctx), ripup(ripup), ripup_penalty(ripup_penalty)
+    Router(Context *ctx, RipupScoreboard &scores, WireId src_wire,
+           WireId dst_wire, bool ripup = false, delay_t ripup_penalty = 0)
+            : ctx(ctx), scores(scores), ripup(ripup),
+              ripup_penalty(ripup_penalty)
     {
         std::unordered_map<WireId, delay_t> src_wires;
         src_wires[src_wire] = 0;
         route(src_wires, dst_wire);
         routedOkay = visited.count(dst_wire);
 
-        if (ctx->verbose) {
+        if (ctx->debug) {
             log("Route (from destination to source):\n");
 
             WireId cursor = dst_wire;
@@ -180,17 +231,17 @@ struct Router
         }
     }
 
-    Router(Context *ctx, IdString net_name, bool ripup = false,
-           delay_t ripup_penalty = 0)
-            : ctx(ctx), net_name(net_name), ripup(ripup),
+    Router(Context *ctx, RipupScoreboard &scores, IdString net_name,
+           bool ripup = false, delay_t ripup_penalty = 0)
+            : ctx(ctx), scores(scores), net_name(net_name), ripup(ripup),
               ripup_penalty(ripup_penalty)
     {
         auto net_info = ctx->nets.at(net_name);
 
-        if (ctx->verbose)
+        if (ctx->debug)
             log("Routing net %s.\n", net_name.c_str(ctx));
 
-        if (ctx->verbose)
+        if (ctx->debug)
             log("  Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx),
                 net_info->driver.port.c_str(ctx));
 
@@ -201,7 +252,7 @@ struct Router
                       net_info->driver.cell->name.c_str(ctx),
                       net_info->driver.cell->type.c_str(ctx));
 
-        if (ctx->verbose)
+        if (ctx->debug)
             log("    Source bel: %s\n", ctx->getBelName(src_bel).c_str(ctx));
 
         IdString driver_port = net_info->driver.port;
@@ -220,7 +271,7 @@ struct Router
                       net_info->driver.cell->name.c_str(ctx),
                       ctx->getBelName(src_bel).c_str(ctx));
 
-        if (ctx->verbose)
+        if (ctx->debug)
             log("    Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx));
 
         std::unordered_map<WireId, delay_t> src_wires;
@@ -232,7 +283,7 @@ struct Router
         ctx->shuffle(users_array);
 
         for (auto &user_it : users_array) {
-            if (ctx->verbose)
+            if (ctx->debug)
                 log("  Route to: %s.%s.\n", user_it.cell->name.c_str(ctx),
                     user_it.port.c_str(ctx));
 
@@ -243,7 +294,7 @@ struct Router
                           user_it.cell->name.c_str(ctx),
                           user_it.cell->type.c_str(ctx));
 
-            if (ctx->verbose)
+            if (ctx->debug)
                 log("    Destination bel: %s\n",
                     ctx->getBelName(dst_bel).c_str(ctx));
 
@@ -264,7 +315,7 @@ struct Router
                           user_it.cell->name.c_str(ctx),
                           ctx->getBelName(dst_bel).c_str(ctx));
 
-            if (ctx->verbose) {
+            if (ctx->debug) {
                 log("    Destination wire: %s\n",
                     ctx->getWireName(dst_wire).c_str(ctx));
                 log("    Path delay estimate: %.2f\n",
@@ -274,7 +325,7 @@ struct Router
             route(src_wires, dst_wire);
 
             if (visited.count(dst_wire) == 0) {
-                if (ctx->verbose)
+                if (ctx->debug)
                     log("Failed to route %s -> %s.\n",
                         ctx->getWireName(src_wire).c_str(ctx),
                         ctx->getWireName(dst_wire).c_str(ctx));
@@ -287,18 +338,18 @@ struct Router
                 return;
             }
 
-            if (ctx->verbose)
+            if (ctx->debug)
                 log("    Final path delay: %.3f\n",
                     ctx->getDelayNS(visited[dst_wire].delay));
             maxDelay = fmaxf(maxDelay, visited[dst_wire].delay);
 
-            if (ctx->verbose)
+            if (ctx->debug)
                 log("    Route (from destination to source):\n");
 
             WireId cursor = dst_wire;
 
             while (1) {
-                if (ctx->verbose)
+                if (ctx->debug)
                     log("    %8.3f %s\n",
                         ctx->getDelayNS(visited[cursor].delay),
                         ctx->getWireName(cursor).c_str(ctx));
@@ -306,22 +357,31 @@ struct Router
                 if (src_wires.count(cursor))
                     break;
 
-                IdString conflicting_net = ctx->getWireNet(cursor, true);
+                IdString conflicting_wire_net = ctx->getWireNet(cursor, true);
+                IdString conflicting_pip_net =
+                        ctx->getPipNet(visited[cursor].pip, true);
 
-                if (conflicting_net != IdString()) {
+                if (conflicting_wire_net != IdString()) {
                     assert(ripup);
-                    assert(conflicting_net != net_name);
-                    ripup_net(ctx, conflicting_net);
-                    rippedNets.insert(conflicting_net);
+                    assert(conflicting_wire_net != net_name);
+                    ripup_net(ctx, conflicting_wire_net);
+                    rippedNets.insert(conflicting_wire_net);
+                    scores.wireScores[std::make_pair(net_name, cursor)]++;
+                    scores.wireScores[std::make_pair(conflicting_wire_net,
+                                                     cursor)]++;
                 }
 
-                conflicting_net = ctx->getPipNet(visited[cursor].pip, true);
-
-                if (conflicting_net != IdString()) {
+                if (conflicting_pip_net != IdString()) {
                     assert(ripup);
-                    assert(conflicting_net != net_name);
-                    ripup_net(ctx, conflicting_net);
-                    rippedNets.insert(conflicting_net);
+                    assert(conflicting_pip_net != net_name);
+                    if (conflicting_wire_net != conflicting_pip_net) {
+                        ripup_net(ctx, conflicting_pip_net);
+                        rippedNets.insert(conflicting_pip_net);
+                    }
+                    scores.pipScores[std::make_pair(net_name,
+                                                    visited[cursor].pip)]++;
+                    scores.pipScores[std::make_pair(conflicting_pip_net,
+                                                    visited[cursor].pip)]++;
                 }
 
                 net_info->wires[cursor] = visited[cursor].pip;
@@ -343,7 +403,8 @@ NEXTPNR_NAMESPACE_BEGIN
 
 bool route_design(Context *ctx)
 {
-    delay_t ripup_penalty = 5;
+    delay_t ripup_penalty = ctx->getRipupDelayPenalty();
+    RipupScoreboard scores;
 
     log_info("Routing..\n");
 
@@ -425,17 +486,23 @@ bool route_design(Context *ctx)
 
     while (!netsQueue.empty()) {
         if (iterCnt == 200) {
-            log_info("giving up after %d iterations.\n", iterCnt);
+            log_warning("giving up after %d iterations.\n", iterCnt);
             return false;
         }
-        log_info("-- %d --\n", ++iterCnt);
+
+        iterCnt++;
+        if (ctx->verbose)
+            log_info("-- %d --\n", iterCnt);
 
         int visitCnt = 0, revisitCnt = 0, netCnt = 0;
 
         std::unordered_set<IdString> ripupQueue;
 
-        log_info("routing queue contains %d nets.\n", int(netsQueue.size()));
-        bool printNets = netsQueue.size() < 10;
+        if (ctx->verbose || iterCnt == 1)
+            log_info("routing queue contains %d nets.\n",
+                     int(netsQueue.size()));
+
+        bool printNets = ctx->verbose && (netsQueue.size() < 10);
 
         std::vector<IdString> netsArray(netsQueue.begin(), netsQueue.end());
         ctx->sorted_shuffle(netsArray);
@@ -446,7 +513,7 @@ bool route_design(Context *ctx)
                 log_info("  routing net %s. (%d users)\n", net_name.c_str(ctx),
                          int(ctx->nets.at(net_name)->users.size()));
 
-            Router router(ctx, net_name, false);
+            Router router(ctx, scores, net_name, false);
 
             netCnt++;
             visitCnt += router.visitCnt;
@@ -459,23 +526,29 @@ bool route_design(Context *ctx)
                 ripupQueue.insert(net_name);
             }
 
-            if (!printNets && netCnt % 100 == 0)
+            if ((ctx->verbose || iterCnt == 1) && !printNets &&
+                (netCnt % 100 == 0))
                 log_info("  processed %d nets. (%d routed, %d failed)\n",
                          netCnt, netCnt - int(ripupQueue.size()),
                          int(ripupQueue.size()));
         }
 
-        if (netCnt % 100 != 0)
+        int normalRouteCnt = netCnt - int(ripupQueue.size());
+
+        if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0))
             log_info("  processed %d nets. (%d routed, %d failed)\n", netCnt,
-                     netCnt - int(ripupQueue.size()), int(ripupQueue.size()));
-        log_info("  routing pass visited %d PIPs (%.2f%% revisits).\n",
-                 visitCnt, (100.0 * revisitCnt) / visitCnt);
+                     normalRouteCnt, int(ripupQueue.size()));
+
+        if (ctx->verbose)
+            log_info("  routing pass visited %d PIPs (%.2f%% revisits).\n",
+                     visitCnt, (100.0 * revisitCnt) / visitCnt);
 
         if (!ripupQueue.empty()) {
-            log_info("failed to route %d nets. re-routing in ripup mode.\n",
-                     int(ripupQueue.size()));
+            if (ctx->verbose || iterCnt == 1)
+                log_info("failed to route %d nets. re-routing in ripup mode.\n",
+                         int(ripupQueue.size()));
 
-            printNets = ripupQueue.size() < 10;
+            printNets = ctx->verbose && (ripupQueue.size() < 10);
 
             visitCnt = 0;
             revisitCnt = 0;
@@ -492,8 +565,7 @@ bool route_design(Context *ctx)
                              net_name.c_str(ctx),
                              int(ctx->nets.at(net_name)->users.size()));
 
-                Router router(ctx, net_name, true,
-                              ripup_penalty * (iterCnt - 1));
+                Router router(ctx, scores, net_name, true, ripup_penalty);
 
                 netCnt++;
                 visitCnt += router.visitCnt;
@@ -521,22 +593,33 @@ bool route_design(Context *ctx)
 
                 ripCnt += router.rippedNets.size();
 
-                if (!printNets && netCnt % 100 == 0)
+                if ((ctx->verbose || iterCnt == 1) && !printNets &&
+                    (netCnt % 100 == 0))
                     log_info("  routed %d nets, ripped %d nets.\n", netCnt,
                              ripCnt);
             }
 
-            if (netCnt % 100 != 0)
+            if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0))
                 log_info("  routed %d nets, ripped %d nets.\n", netCnt, ripCnt);
 
-            log_info("  routing pass visited %d PIPs (%.2f%% revisits).\n",
-                     visitCnt, (100.0 * revisitCnt) / visitCnt);
+            if (ctx->verbose)
+                log_info("  routing pass visited %d PIPs (%.2f%% revisits).\n",
+                         visitCnt, (100.0 * revisitCnt) / visitCnt);
 
-            if (!netsQueue.empty())
+            if (ctx->verbose && !netsQueue.empty())
                 log_info("  ripped up %d previously routed nets. continue "
                          "routing.\n",
                          int(netsQueue.size()));
         }
+
+        if (!ctx->verbose)
+            log_info("iteration %d: routed %d nets without ripup, routed %d "
+                     "nets with ripup.\n",
+                     iterCnt, normalRouteCnt, int(ripupQueue.size()));
+
+        if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 ||
+            iterCnt == 128)
+            ripup_penalty += ctx->getRipupDelayPenalty();
     }
 
     log_info("routing complete after %d iterations.\n", iterCnt);
@@ -546,7 +629,8 @@ bool route_design(Context *ctx)
 bool get_actual_route_delay(Context *ctx, WireId src_wire, WireId dst_wire,
                             delay_t &delay)
 {
-    Router router(ctx, src_wire, dst_wire);
+    RipupScoreboard scores;
+    Router router(ctx, scores, src_wire, dst_wire);
     if (router.routedOkay)
         delay = router.visited.at(dst_wire).delay;
     return router.routedOkay;