Merge pull request #16 from YosysHQ/reroute

Add cleanup reroute passes to router1, improve reuse of wires

5 files changed, 178 insertions, 48 deletions

diff --git a/common/router1.cc b/common/router1.cc
index 46be444e..6e352866 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -105,6 +105,7 @@ void ripup_net(Context *ctx, IdString net_name)
 struct Router
 {
     Context *ctx;
+    const Router1Cfg &cfg;
     RipupScoreboard scores;
     IdString net_name;
 
@@ -128,7 +129,7 @@ struct Router
             QueuedWire qw;
             qw.wire = it.first;
             qw.pip = PipId();
-            qw.delay = it.second;
+            qw.delay = it.second - (it.second / 16);
             qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
             qw.randtag = ctx->rng();
 
@@ -200,8 +201,7 @@ struct Router
                         continue;
 #if 0 // FIXME
                     if (ctx->debug)
-                        log("Found better route to %s. Old vs new delay "
-                            "estimate: %.3f %.3f\n",
+                        log("Found better route to %s. Old vs new delay estimate: %.3f %.3f\n",
                             ctx->getWireName(next_wire).c_str(),
                             ctx->getDelayNS(visited.at(next_wire).delay),
                             ctx->getDelayNS(next_delay));
@@ -227,9 +227,9 @@ struct Router
         visitCnt += thisVisitCnt;
     }
 
-    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)
+    Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, WireId src_wire, WireId dst_wire,
+           bool ripup = false, delay_t ripup_penalty = 0)
+            : ctx(ctx), cfg(cfg), scores(scores), ripup(ripup), ripup_penalty(ripup_penalty)
     {
         std::unordered_map<WireId, delay_t> src_wires;
         src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
@@ -252,9 +252,9 @@ struct Router
         }
     }
 
-    Router(Context *ctx, RipupScoreboard &scores, IdString net_name, int user_idx = -1, bool reroute = false,
-           bool ripup = false, delay_t ripup_penalty = 0)
-            : ctx(ctx), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty)
+    Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, IdString net_name, int user_idx = -1,
+           bool reroute = false, bool ripup = false, delay_t ripup_penalty = 0)
+            : ctx(ctx), cfg(cfg), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty)
     {
         auto net_info = ctx->nets.at(net_name).get();
 
@@ -274,16 +274,19 @@ struct Router
             log("    Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx));
 
         std::unordered_map<WireId, delay_t> src_wires;
-        std::vector<int> users_array;
+        std::vector<std::pair<delay_t, int>> users_array;
 
         if (user_idx < 0) {
-            // route all users
-            for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++)
-                users_array.push_back(user_idx);
-            ctx->shuffle(users_array);
+            // route all users, from worst to best slack
+            for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
+                auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+                delay_t slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
+                users_array.push_back(std::pair<delay_t, int>(slack, user_idx));
+            }
+            std::sort(users_array.begin(), users_array.end());
         } else {
             // route only the selected user
-            users_array.push_back(user_idx);
+            users_array.push_back(std::pair<delay_t, int>(delay_t(), user_idx));
         }
 
         if (reroute) {
@@ -315,7 +318,6 @@ struct Router
                     delay_t delay = register_existing_path(ctx->getPipSrcWire(pip));
                     delay += ctx->getPipDelay(pip).maxDelay();
                     delay += ctx->getWireDelay(wire).maxDelay();
-                    delay -= 2 * ctx->getDelayEpsilon();
                     src_wires[wire] = delay;
 
                     return delay;
@@ -347,7 +349,9 @@ struct Router
             }
         }
 
-        for (int user_idx : users_array) {
+        for (auto user_idx_it : users_array) {
+            int user_idx = user_idx_it.second;
+
             if (ctx->debug)
                 log("  Route to: %s.%s.\n", net_info->users[user_idx].cell->name.c_str(ctx),
                     net_info->users[user_idx].port.c_str(ctx));
@@ -452,7 +456,8 @@ struct RouteJob
     };
 };
 
-void addFullNetRouteJob(Context *ctx, IdString net_name, std::unordered_map<IdString, std::vector<bool>> &cache,
+void addFullNetRouteJob(Context *ctx, const Router1Cfg &cfg, IdString net_name,
+                        std::unordered_map<IdString, std::vector<bool>> &cache,
                         std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue)
 {
     NetInfo *net_info = ctx->nets.at(net_name).get();
@@ -517,7 +522,8 @@ void addFullNetRouteJob(Context *ctx, IdString net_name, std::unordered_map<IdSt
         net_cache[user_idx] = true;
 }
 
-void addNetRouteJobs(Context *ctx, IdString net_name, std::unordered_map<IdString, std::vector<bool>> &cache,
+void addNetRouteJobs(Context *ctx, const Router1Cfg &cfg, IdString net_name,
+                     std::unordered_map<IdString, std::vector<bool>> &cache,
                      std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue)
 {
     NetInfo *net_info = ctx->nets.at(net_name).get();
@@ -565,11 +571,114 @@ void addNetRouteJobs(Context *ctx, IdString net_name, std::unordered_map<IdStrin
     }
 }
 
+void cleanupReroute(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores,
+                    std::unordered_set<IdString> &cleanupQueue,
+                    std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &jobQueue,
+                    int &totalVisitCnt, int &totalRevisitCnt, int &totalOvertimeRevisitCnt)
+{
+    std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> cleanupJobs;
+    std::vector<NetInfo *> allNetinfos;
+
+    for (auto net_name : cleanupQueue) {
+        NetInfo *net_info = ctx->nets.at(net_name).get();
+        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+
+        if (ctx->verbose)
+            allNetinfos.push_back(net_info);
+
+        std::unordered_map<WireId, int> useCounters;
+        std::vector<int> candidateArcs;
+
+        for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
+            auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+
+            if (dst_wire == src_wire)
+                continue;
+
+            auto cursor = dst_wire;
+            useCounters[cursor]++;
+
+            while (cursor != src_wire) {
+                auto it = net_info->wires.find(cursor);
+                if (it == net_info->wires.end())
+                    break;
+                cursor = ctx->getPipSrcWire(it->second.pip);
+                useCounters[cursor]++;
+            }
+
+            if (cursor != src_wire)
+                continue;
+
+            candidateArcs.push_back(user_idx);
+        }
+
+        for (int user_idx : candidateArcs) {
+            auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+
+            if (useCounters.at(dst_wire) != 1)
+                continue;
+
+            RouteJob job;
+            job.net = net_name;
+            job.user_idx = user_idx;
+            job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
+            job.randtag = ctx->rng();
+            cleanupJobs.push(job);
+        }
+    }
+
+    log_info("running cleanup re-route of %d nets (%d arcs).\n", int(cleanupQueue.size()), int(cleanupJobs.size()));
+
+    cleanupQueue.clear();
+
+    int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0;
+    int totalWireCountDelta = 0;
+
+    if (ctx->verbose) {
+        for (auto it : allNetinfos)
+            totalWireCountDelta -= it->wires.size();
+    }
+
+    while (!cleanupJobs.empty()) {
+        RouteJob job = cleanupJobs.top();
+        cleanupJobs.pop();
+
+        auto net_name = job.net;
+        auto user_idx = job.user_idx;
+
+        NetInfo *net_info = ctx->nets.at(net_name).get();
+        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+
+        ctx->unbindWire(dst_wire);
+
+        Router router(ctx, cfg, scores, net_name, user_idx, false, false);
+
+        if (!router.routedOkay)
+            log_error("Failed to re-route arc %d of net %s.\n", user_idx, net_name.c_str(ctx));
+
+        visitCnt += router.visitCnt;
+        revisitCnt += router.revisitCnt;
+        overtimeRevisitCnt += router.overtimeRevisitCnt;
+    }
+
+    if (ctx->verbose) {
+        for (auto it : allNetinfos)
+            totalWireCountDelta += it->wires.size();
+
+        log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% overtime), %+d wires.\n", visitCnt,
+                 (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt, totalWireCountDelta);
+    }
+
+    totalVisitCnt += visitCnt;
+    totalRevisitCnt += revisitCnt;
+    totalOvertimeRevisitCnt += overtimeRevisitCnt;
+}
+
 } // namespace
 
 NEXTPNR_NAMESPACE_BEGIN
 
-bool router1(Context *ctx)
+bool router1(Context *ctx, const Router1Cfg &cfg)
 {
     try {
         int totalVisitCnt = 0, totalRevisitCnt = 0, totalOvertimeRevisitCnt = 0;
@@ -580,11 +689,12 @@ bool router1(Context *ctx)
         log_info("Routing..\n");
         ctx->lock();
 
+        std::unordered_set<IdString> cleanupQueue;
         std::unordered_map<IdString, std::vector<bool>> jobCache;
         std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> jobQueue;
 
         for (auto &net_it : ctx->nets)
-            addNetRouteJobs(ctx, net_it.first, jobCache, jobQueue);
+            addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
 
         if (jobQueue.empty()) {
             log_info("found no unrouted source-sink pairs. no routing necessary.\n");
@@ -597,7 +707,7 @@ bool router1(Context *ctx)
         int iterCnt = 0;
 
         while (!jobQueue.empty()) {
-            if (iterCnt == 200) {
+            if (iterCnt == cfg.maxIterCnt) {
                 log_warning("giving up after %d iterations.\n", iterCnt);
                 log_info("Checksum: 0x%08x\n", ctx->checksum());
 #ifndef NDEBUG
@@ -630,6 +740,9 @@ bool router1(Context *ctx)
                 auto user_idx = jobQueue.top().user_idx;
                 jobQueue.pop();
 
+                if (cfg.fullCleanupReroute)
+                    cleanupQueue.insert(net_name);
+
                 if (printNets) {
                     if (user_idx < 0)
                         log_info("  routing all %d users of net %s\n", int(ctx->nets.at(net_name)->users.size()),
@@ -638,7 +751,7 @@ bool router1(Context *ctx)
                         log_info("  routing user %d of net %s\n", user_idx, net_name.c_str(ctx));
                 }
 
-                Router router(ctx, scores, net_name, user_idx, false, false);
+                Router router(ctx, cfg, scores, net_name, user_idx, false, false);
 
                 jobCnt++;
                 visitCnt += router.visitCnt;
@@ -669,15 +782,12 @@ bool router1(Context *ctx)
             }
 
             if (ctx->verbose)
-                log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% overtime "
-                         "revisits).\n",
-                         visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
+                log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", visitCnt,
+                         (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
 
             if (!ripupQueue.empty()) {
                 if (ctx->verbose || iterCnt == 1)
-                    log_info("failed to route %d nets. re-routing in ripup "
-                             "mode.\n",
-                             int(ripupQueue.size()));
+                    log_info("failed to route %d nets. re-routing in ripup mode.\n", int(ripupQueue.size()));
 
                 printNets = ctx->verbose && (ripupQueue.size() < 10);
 
@@ -691,11 +801,14 @@ bool router1(Context *ctx)
                 ctx->sorted_shuffle(ripupArray);
 
                 for (auto net_name : ripupArray) {
+                    if (cfg.cleanupReroute)
+                        cleanupQueue.insert(net_name);
+
                     if (printNets)
                         log_info("  routing net %s. (%d users)\n", net_name.c_str(ctx),
                                  int(ctx->nets.at(net_name)->users.size()));
 
-                    Router router(ctx, scores, net_name, -1, false, true, ripup_penalty);
+                    Router router(ctx, cfg, scores, net_name, -1, false, true, ripup_penalty);
 
                     netCnt++;
                     visitCnt += router.visitCnt;
@@ -705,8 +818,11 @@ bool router1(Context *ctx)
                     if (!router.routedOkay)
                         log_error("Net %s is impossible to route.\n", net_name.c_str(ctx));
 
-                    for (auto it : router.rippedNets)
-                        addFullNetRouteJob(ctx, it, jobCache, jobQueue);
+                    for (auto it : router.rippedNets) {
+                        addFullNetRouteJob(ctx, cfg, it, jobCache, jobQueue);
+                        if (cfg.cleanupReroute)
+                            cleanupQueue.insert(it);
+                    }
 
                     if (printNets) {
                         if (router.rippedNets.size() < 10) {
@@ -730,14 +846,11 @@ bool router1(Context *ctx)
                     log_info("  routed %d nets, ripped %d nets.\n", netCnt, ripCnt);
 
                 if (ctx->verbose)
-                    log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% "
-                             "overtime revisits).\n",
-                             visitCnt, (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
+                    log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", visitCnt,
+                             (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
 
                 if (ctx->verbose && !jobQueue.empty())
-                    log_info("  ripped up %d previously routed nets. continue "
-                             "routing.\n",
-                             int(jobQueue.size()));
+                    log_info("  ripped up %d previously routed nets. continue routing.\n", int(jobQueue.size()));
             }
 
             if (!ctx->verbose)
@@ -751,15 +864,17 @@ bool router1(Context *ctx)
             if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || iterCnt == 128)
                 ripup_penalty += ctx->getRipupDelayPenalty();
 
+            if (jobQueue.empty() || (iterCnt % 5) == 0 || (cfg.fullCleanupReroute && iterCnt == 1))
+                cleanupReroute(ctx, cfg, scores, cleanupQueue, jobQueue, totalVisitCnt, totalRevisitCnt,
+                               totalOvertimeRevisitCnt);
+
             ctx->yield();
         }
 
         log_info("routing complete after %d iterations.\n", iterCnt);
 
-        log_info("visited %d PIPs (%.2f%% revisits, %.2f%% "
-                 "overtime revisits).\n",
-                 totalVisitCnt, (100.0 * totalRevisitCnt) / totalVisitCnt,
-                 (100.0 * totalOvertimeRevisitCnt) / totalVisitCnt);
+        log_info("visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", totalVisitCnt,
+                 (100.0 * totalRevisitCnt) / totalVisitCnt, (100.0 * totalOvertimeRevisitCnt) / totalVisitCnt);
 
         {
             float tns = 0;
@@ -798,7 +913,7 @@ bool router1(Context *ctx)
         jobCache.clear();
 
         for (auto &net_it : ctx->nets)
-            addNetRouteJobs(ctx, net_it.first, jobCache, jobQueue);
+            addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
 
 #ifndef NDEBUG
         if (!jobQueue.empty()) {
@@ -833,7 +948,7 @@ bool router1(Context *ctx)
 bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t &delay)
 {
     RipupScoreboard scores;
-    Router router(this, scores, src_wire, dst_wire);
+    Router router(this, Router1Cfg(), scores, src_wire, dst_wire);
     if (router.routedOkay)
         delay = router.visited.at(dst_wire).delay;
     return router.routedOkay;
diff --git a/common/router1.h b/common/router1.h
index 38552c58..a9e84b6b 100644
--- a/common/router1.h
+++ b/common/router1.h
@@ -24,7 +24,14 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-extern bool router1(Context *ctx);
+struct Router1Cfg
+{
+    int maxIterCnt = 200;
+    bool cleanupReroute = true;
+    bool fullCleanupReroute = true;
+};
+
+extern bool router1(Context *ctx, const Router1Cfg &cfg);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/ecp5/arch.cc b/ecp5/arch.cc
index bf05c15d..262f43fe 100644
--- a/ecp5/arch.cc
+++ b/ecp5/arch.cc
@@ -428,7 +428,11 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de
 
 bool Arch::place() { return placer1(getCtx()); }
 
-bool Arch::route() { return router1(getCtx()); }
+bool Arch::route()
+{
+    Router1Cfg cfg;
+    return router1(getCtx(), cfg);
+}
 
 // -----------------------------------------------------------------------
 
diff --git a/generic/arch.cc b/generic/arch.cc
index 66fbd1ff..cff638df 100644
--- a/generic/arch.cc
+++ b/generic/arch.cc
@@ -420,7 +420,7 @@ delay_t getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t
 
 bool Arch::place() { return placer1(getCtx()); }
 
-bool Arch::route() { return router1(getCtx()); }
+bool Arch::route() { return router1(getCtx(), Router1Cfg()); }
 
 // ---------------------------------------------------------------
 
diff --git a/ice40/arch.cc b/ice40/arch.cc
index b3d514b5..2867f591 100644
--- a/ice40/arch.cc
+++ b/ice40/arch.cc
@@ -661,7 +661,11 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de
 
 bool Arch::place() { return placer1(getCtx()); }
 
-bool Arch::route() { return router1(getCtx()); }
+bool Arch::route()
+{
+    Router1Cfg cfg;
+    return router1(getCtx(), cfg);
+}
 
 // -----------------------------------------------------------------------