router2: Reserve wires in more complex cases

Signed-off-by: gatecat <gatecat@ds0.me>

1 files changed, 39 insertions, 13 deletions

diff --git a/common/router2.cc b/common/router2.cc
index 24bccec7..b62873c0 100644
--- a/common/router2.cc
+++ b/common/router2.cc
@@ -434,20 +434,35 @@ struct Router2
     }
 
     // Returns true if a wire contains no source ports or driving pips
-    bool is_wire_undriveable(WireId wire)
+    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).reserved_net != -1 && wire_data(wire).reserved_net != net->udata)
+            return true; // reserved for another net
         for (auto bp : ctx->getWireBelPins(wire))
-            if (ctx->getBelPinType(bp.bel, bp.pin) != PORT_IN)
+            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))
-                return false;
+            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
-    void reserve_wires_for_arc(NetInfo *net, size_t i)
+    bool reserve_wires_for_arc(NetInfo *net, size_t i)
     {
+        bool did_something = false;
         WireId src = ctx->getNetinfoSourceWire(net);
         for (auto sink : ctx->getNetinfoSinkWires(net, net->users.at(i))) {
             std::unordered_set<WireId> rsv;
@@ -459,13 +474,14 @@ struct Router2
                 auto &wd = wire_data(cursor);
                 if (ctx->debug)
                     log("      %s\n", ctx->nameOfWire(cursor));
+                did_something |= (wd.reserved_net != net->udata);
                 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))
+                    if (is_wire_undriveable(w, net))
                         continue;
                     if (next_cursor != WireId()) {
                         done = true;
@@ -478,17 +494,23 @@ struct Router2
                 cursor = next_cursor;
             }
         }
+        return did_something;
     }
 
     void find_all_reserved_wires()
     {
-        for (auto net : nets_by_udata) {
-            WireId src = ctx->getNetinfoSourceWire(net);
-            if (src == WireId())
-                continue;
-            for (size_t i = 0; i < net->users.size(); i++)
-                reserve_wires_for_arc(net, i);
-        }
+        // 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 (size_t i = 0; i < net->users.size(); i++)
+                    did_something |= reserve_wires_for_arc(net, i);
+            }
+        } while (did_something);
     }
 
     void reset_wires(ThreadContext &t)
@@ -720,6 +742,7 @@ struct Router2
                 next_score.delay =
                         curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay();
                 next_score.togo_cost = cfg.estimate_weight * get_togo_cost(net, i, next_idx, dst_wire, &forward);
+#if 0
                 ROUTE_LOG_DBG(
                         "src_wire = %s -> next %s -> dst_wire = %s (backward: %s, forward: %s, sum: %s, cost = %f, "
                         "togo_cost = %f, total = %f), dt = %02fs\n",
@@ -728,6 +751,7 @@ struct Router2
                         std::to_string(next_score.delay + forward).c_str(), next_score.cost, next_score.togo_cost,
                         next_score.cost + next_score.togo_cost,
                         std::chrono::duration<float>(std::chrono::high_resolution_clock::now() - arc_start).count());
+#endif
                 const auto &v = nwd.visit;
                 if (!v.visited || (v.score.total() > next_score.total())) {
                     ++explored;
@@ -809,7 +833,9 @@ struct Router2
                 // Ripup failed arcs to start with
                 // Check if arc is already legally routed
                 if (check_arc_routing(net, i, j)) {
+#if 0
                     ROUTE_LOG_DBG("Arc '%s' (user %zu, arc %zu) already routed skipping.\n", ctx->nameOf(net), i, j);
+#endif
                     continue;
                 }