router2: Flatten wire structure

Signed-off-by: David Shah <dave@ds0.me>

1 files changed, 88 insertions, 79 deletions

diff --git a/common/router2.cc b/common/router2.cc
index f7962ae8..05734bec 100644
--- a/common/router2.cc
+++ b/common/router2.cc
@@ -74,6 +74,8 @@ struct Router2
 
     struct PerWireData
     {
+        // nextpnr
+        WireId w;
         // net --> number of arcs; driving pip
         boost::container::flat_map<int, std::pair<int, PipId>> bound_nets;
         // Historical congestion cost
@@ -170,30 +172,37 @@ struct Router2
         }
     }
 
-    std::unordered_map<WireId, PerWireData> wires;
+    std::unordered_map<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()) {
-            wires[wire];
+            PerWireData pwd;
+            pwd.w = wire;
             NetInfo *bound = ctx->getBoundWireNet(wire);
             if (bound != nullptr) {
-                wires[wire].bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip);
+                pwd.bound_nets[bound->udata] = std::make_pair(1, bound->wires.at(wire).pip);
                 if (bound->wires.at(wire).strength > STRENGTH_STRONG)
-                    wires[wire].unavailable = true;
+                    pwd.unavailable = true;
             }
+            wire_to_idx[wire] = int(flat_wires.size());
+            flat_wires.push_back(pwd);
         }
     }
 
     struct QueuedWire
     {
 
-        explicit QueuedWire(WireId wire = WireId(), PipId pip = PipId(), Loc loc = Loc(), WireScore score = WireScore{},
+        explicit QueuedWire(int wire = -1, PipId pip = PipId(), Loc loc = Loc(), WireScore score = WireScore{},
                             int randtag = 0)
                 : wire(wire), pip(pip), loc(loc), score(score), randtag(randtag){};
 
-        WireId wire;
+        int wire;
         PipId pip;
         Loc loc;
         WireScore score;
@@ -233,9 +242,9 @@ struct Router2
         std::unordered_set<WireId> processed_sinks;
 
         // Backwards routing
-        std::queue<WireId> backwards_queue;
+        std::queue<int> backwards_queue;
 
-        std::vector<WireId> dirty_wires;
+        std::vector<int> dirty_wires;
     };
 
     enum ArcRouteResult
@@ -259,9 +268,9 @@ struct Router2
             log(__VA_ARGS__);                                                                                          \
     } while (0)
 
-    void bind_pip_internal(NetInfo *net, size_t user, WireId wire, PipId pip)
+    void bind_pip_internal(NetInfo *net, size_t user, int wire, PipId pip)
     {
-        auto &b = wires.at(wire).bound_nets[net->udata];
+        auto &b = flat_wires.at(wire).bound_nets[net->udata];
         ++b.first;
         if (b.first == 1) {
             b.second = pip;
@@ -272,10 +281,10 @@ struct Router2
 
     void unbind_pip_internal(NetInfo *net, size_t user, WireId wire)
     {
-        auto &b = wires.at(wire).bound_nets.at(net->udata);
+        auto &b = wire_data(wire).bound_nets.at(net->udata);
         --b.first;
         if (b.first == 0) {
-            wires.at(wire).bound_nets.erase(net->udata);
+            wire_data(wire).bound_nets.erase(net->udata);
         }
     }
 
@@ -287,7 +296,7 @@ struct Router2
         WireId src = nets.at(net->udata).src_wire;
         WireId cursor = ad.sink_wire;
         while (cursor != src) {
-            auto &wd = wires.at(cursor);
+            auto &wd = wire_data(cursor);
             PipId pip = wd.bound_nets.at(net->udata).second;
             unbind_pip_internal(net, user, cursor);
             cursor = ctx->getPipSrcWire(pip);
@@ -297,7 +306,7 @@ struct Router2
 
     float score_wire_for_arc(NetInfo *net, size_t user, WireId wire, PipId pip)
     {
-        auto &wd = wires.at(wire);
+        auto &wd = wire_data(wire);
         auto &nd = nets.at(net->udata);
         float base_cost = ctx->getDelayNS(ctx->getPipDelay(pip).maxDelay() + ctx->getWireDelay(wire).maxDelay() +
                                           ctx->getDelayEpsilon());
@@ -315,16 +324,14 @@ struct Router2
         return base_cost * hist_cost * present_cost / (1 + source_uses) + bias_cost;
     }
 
-    float get_togo_cost(NetInfo *net, size_t user, WireId wire, WireId sink)
+    float get_togo_cost(NetInfo *net, size_t user, int wire, WireId sink)
     {
-        auto &wd = wires.at(wire);
+        auto &wd = flat_wires[wire];
         int source_uses = 0;
         if (wd.bound_nets.count(net->udata))
             source_uses = wd.bound_nets.at(net->udata).first;
         // FIXME: timing/wirelength balance?
-        float ipin_cost = ctx->getDelayNS(ctx->getWireDelay(sink).maxDelay() + ctx->getDelayEpsilon());
-        return std::max(0.0f, ctx->getDelayNS(ctx->estimateDelay(wire, sink)) - ipin_cost) / (1 + source_uses) +
-               ipin_cost;
+        return ctx->getDelayNS(ctx->estimateDelay(wd.w, sink)) / (1 + source_uses);
     }
 
     bool check_arc_routing(NetInfo *net, size_t usr)
@@ -332,8 +339,8 @@ struct Router2
         auto &ad = nets.at(net->udata).arcs.at(usr);
         WireId src_wire = nets.at(net->udata).src_wire;
         WireId cursor = ad.sink_wire;
-        while (wires.at(cursor).bound_nets.count(net->udata)) {
-            auto &wd = wires.at(cursor);
+        while (wire_data(cursor).bound_nets.count(net->udata)) {
+            auto &wd = wire_data(cursor);
             if (wd.bound_nets.size() != 1)
                 return false;
             auto &uh = wd.bound_nets.at(net->udata).second;
@@ -368,7 +375,7 @@ struct Router2
         if (ctx->debug)
             log("resevering wires for arc %d of net %s\n", int(i), ctx->nameOf(net));
         while (!done) {
-            auto &wd = wires.at(cursor);
+            auto &wd = wire_data(cursor);
             if (ctx->debug)
                 log("      %s\n", ctx->nameOfWire(cursor));
             wd.reserved_net = net->udata;
@@ -405,17 +412,17 @@ struct Router2
     void reset_wires(ThreadContext &t)
     {
         for (auto w : t.dirty_wires) {
-            wires.at(w).visit.visited = false;
-            wires.at(w).visit.dirty = false;
-            wires.at(w).visit.pip = PipId();
-            wires.at(w).visit.score = WireScore();
+            flat_wires[w].visit.visited = false;
+            flat_wires[w].visit.dirty = false;
+            flat_wires[w].visit.pip = PipId();
+            flat_wires[w].visit.score = WireScore();
         }
         t.dirty_wires.clear();
     }
 
-    void set_visited(ThreadContext &t, WireId wire, PipId pip, WireScore score)
+    void set_visited(ThreadContext &t, int wire, PipId pip, WireScore score)
     {
-        auto &v = wires.at(wire).visit;
+        auto &v = flat_wires.at(wire).visit;
         if (!v.dirty)
             t.dirty_wires.push_back(wire);
         v.dirty = true;
@@ -423,7 +430,7 @@ struct Router2
         v.pip = pip;
         v.score = score;
     }
-    bool was_visited(WireId wire) { return wires.at(wire).visit.visited; }
+    bool was_visited(int wire) { return flat_wires.at(wire).visit.visited; }
 
     ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, bool is_mt, bool is_bb = true)
     {
@@ -434,13 +441,14 @@ struct Router2
         ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", int(i), 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);
-
         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);
         // Check if arc was already done _in this iteration_
         if (t.processed_sinks.count(dst_wire))
             return ARC_SUCCESS;
@@ -450,7 +458,7 @@ struct Router2
             t.queue.swap(new_queue);
         }
         if (!t.backwards_queue.empty()) {
-            std::queue<WireId> new_queue;
+            std::queue<int> new_queue;
             t.backwards_queue.swap(new_queue);
         }
         // First try strongly iteration-limited routing backwards BFS
@@ -460,35 +468,35 @@ struct Router2
         // bidirectional approach
         int backwards_iter = 0;
         int backwards_limit = ctx->getBelGlobalBuf(net->driver.cell->bel) ? 20000 : 15;
-        t.backwards_queue.push(dst_wire);
+        t.backwards_queue.push(wire_to_idx.at(dst_wire));
         while (!t.backwards_queue.empty() && backwards_iter < backwards_limit) {
-            WireId cursor = t.backwards_queue.front();
+            int cursor = t.backwards_queue.front();
             t.backwards_queue.pop();
-            auto &cwd = wires.at(cursor);
+            auto &cwd = flat_wires[cursor];
             PipId cpip;
             if (cwd.bound_nets.count(net->udata)) {
                 // If we can tack onto existing routing; try that
                 // Only do this if the existing routing is uncontented; however
-                WireId cursor2 = cursor;
+                int cursor2 = cursor;
                 bool bwd_merge_fail = false;
-                while (wires.at(cursor2).bound_nets.count(net->udata)) {
-                    if (wires.at(cursor2).bound_nets.size() > 1) {
+                while (flat_wires.at(cursor2).bound_nets.count(net->udata)) {
+                    if (flat_wires.at(cursor2).bound_nets.size() > 1) {
                         bwd_merge_fail = true;
                         break;
                     }
-                    PipId p = wires.at(cursor2).bound_nets.at(net->udata).second;
+                    PipId p = flat_wires.at(cursor2).bound_nets.at(net->udata).second;
                     if (p == PipId())
                         break;
-                    cursor2 = ctx->getPipSrcWire(p);
+                    cursor2 = wire_to_idx.at(ctx->getPipSrcWire(p));
                 }
-                if (!bwd_merge_fail && cursor2 == src_wire) {
+                if (!bwd_merge_fail && cursor2 == src_wire_idx) {
                     // Found a path to merge to existing routing; backwards
                     cursor2 = cursor;
-                    while (wires.at(cursor2).bound_nets.count(net->udata)) {
-                        PipId p = wires.at(cursor2).bound_nets.at(net->udata).second;
+                    while (flat_wires.at(cursor2).bound_nets.count(net->udata)) {
+                        PipId p = flat_wires.at(cursor2).bound_nets.at(net->udata).second;
                         if (p == PipId())
                             break;
-                        cursor2 = ctx->getPipSrcWire(p);
+                        cursor2 = wire_to_idx.at(ctx->getPipSrcWire(p));
                         set_visited(t, cursor2, p, WireScore());
                     }
                     break;
@@ -496,16 +504,16 @@ struct Router2
                 cpip = cwd.bound_nets.at(net->udata).second;
             }
             bool did_something = false;
-            for (auto uh : ctx->getPipsUphill(cursor)) {
+            for (auto uh : ctx->getPipsUphill(flat_wires[cursor].w)) {
                 did_something = true;
                 if (!ctx->checkPipAvail(uh) && ctx->getBoundPipNet(uh) != net)
                     continue;
                 if (cpip != PipId() && cpip != uh)
                     continue; // don't allow multiple pips driving a wire with a net
-                WireId next = ctx->getPipSrcWire(uh);
+                int next = wire_to_idx.at(ctx->getPipSrcWire(uh));
                 if (was_visited(next))
                     continue; // skip wires that have already been visited
-                auto &wd = wires.at(next);
+                auto &wd = flat_wires[next];
                 if (wd.unavailable)
                     continue;
                 if (wd.reserved_net != -1 && wd.reserved_net != net->udata)
@@ -519,21 +527,21 @@ struct Router2
                 ++backwards_iter;
         }
         // Check if backwards routing succeeded in reaching source
-        if (was_visited(src_wire)) {
+        if (was_visited(src_wire_idx)) {
             ROUTE_LOG_DBG("   Routed (backwards): ");
-            WireId cursor_fwd = src_wire;
-            bind_pip_internal(net, i, src_wire, PipId());
+            int cursor_fwd = src_wire_idx;
+            bind_pip_internal(net, i, src_wire_idx, PipId());
             while (was_visited(cursor_fwd)) {
-                auto &v = wires.at(cursor_fwd).visit;
-                cursor_fwd = ctx->getPipDstWire(v.pip);
+                auto &v = flat_wires.at(cursor_fwd).visit;
+                cursor_fwd = wire_to_idx.at(ctx->getPipDstWire(v.pip));
                 bind_pip_internal(net, i, cursor_fwd, v.pip);
                 if (ctx->debug) {
-                    auto &wd = wires.at(cursor_fwd);
-                    ROUTE_LOG_DBG("      wire: %s (curr %d hist %f)\n", ctx->nameOfWire(cursor_fwd),
+                    auto &wd = flat_wires.at(cursor_fwd);
+                    ROUTE_LOG_DBG("      wire: %s (curr %d hist %f)\n", ctx->nameOfWire(wd.w),
                                   int(wd.bound_nets.size()) - 1, wd.hist_cong_cost);
                 }
             }
-            NPNR_ASSERT(cursor_fwd == dst_wire);
+            NPNR_ASSERT(cursor_fwd == dst_wire_idx);
             ad.routed = true;
             t.processed_sinks.insert(dst_wire);
             reset_wires(t);
@@ -545,11 +553,11 @@ struct Router2
         WireScore base_score;
         base_score.cost = 0;
         base_score.delay = ctx->getWireDelay(src_wire).maxDelay();
-        base_score.togo_cost = get_togo_cost(net, i, src_wire, dst_wire);
+        base_score.togo_cost = get_togo_cost(net, i, src_wire_idx, dst_wire);
 
         // Add source wire to queue
-        t.queue.push(QueuedWire(src_wire, PipId(), Loc(), base_score));
-        set_visited(t, src_wire, PipId(), base_score);
+        t.queue.push(QueuedWire(src_wire_idx, PipId(), Loc(), base_score));
+        set_visited(t, src_wire_idx, PipId(), base_score);
 
         int toexplore = 25000 * std::max(1, (ad.bb.x1 - ad.bb.x0) + (ad.bb.y1 - ad.bb.y0));
         int iter = 0;
@@ -559,13 +567,14 @@ struct Router2
                 false;
         while (!t.queue.empty() && (!is_bb || iter < toexplore)) {
             auto curr = t.queue.top();
+            auto &d = flat_wires.at(curr.wire);
             t.queue.pop();
             ++iter;
 #if 0
             ROUTE_LOG_DBG("current wire %s\n", ctx->nameOfWire(curr.wire));
 #endif
             // Explore all pips downhill of cursor
-            for (auto dh : ctx->getPipsDownhill(curr.wire)) {
+            for (auto dh : ctx->getPipsDownhill(d.w)) {
                 // Skip pips outside of box in bounding-box mode
 #if 0
                 ROUTE_LOG_DBG("trying pip %s\n", ctx->nameOfPip(dh));
@@ -582,13 +591,14 @@ struct Router2
 #endif
                 // Evaluate score of next wire
                 WireId next = ctx->getPipDstWire(dh);
-                if (was_visited(next))
+                int next_idx = wire_to_idx.at(next);
+                if (was_visited(next_idx))
                     continue;
 #if 1
                 if (debug_arc)
                     ROUTE_LOG_DBG("   src wire %s\n", ctx->nameOfWire(next));
 #endif
-                auto &nwd = wires.at(next);
+                auto &nwd = flat_wires.at(next_idx);
                 if (nwd.unavailable)
                     continue;
                 if (nwd.reserved_net != -1 && nwd.reserved_net != net->udata)
@@ -599,8 +609,8 @@ struct Router2
                 next_score.cost = curr.score.cost + score_wire_for_arc(net, i, next, dh);
                 next_score.delay =
                         curr.score.delay + ctx->getPipDelay(dh).maxDelay() + ctx->getWireDelay(next).maxDelay();
-                next_score.togo_cost = 1.75 * get_togo_cost(net, i, next, dst_wire);
-                const auto &v = wires.at(next).visit;
+                next_score.togo_cost = 1.75 * get_togo_cost(net, i, next_idx, dst_wire);
+                const auto &v = nwd.visit;
                 if (!v.visited || (v.score.total() > next_score.total())) {
                     ++explored;
 #if 0
@@ -608,33 +618,33 @@ struct Router2
                                   next_score.togo_cost);
 #endif
                     // Add wire to queue if it meets criteria
-                    t.queue.push(QueuedWire(next, dh, ctx->getPipLocation(dh), next_score, ctx->rng()));
-                    set_visited(t, next, dh, next_score);
+                    t.queue.push(QueuedWire(next_idx, dh, ctx->getPipLocation(dh), next_score, ctx->rng()));
+                    set_visited(t, next_idx, dh, next_score);
                     if (next == dst_wire) {
                         toexplore = std::min(toexplore, iter + 5);
                     }
                 }
             }
         }
-        if (was_visited(dst_wire)) {
+        if (was_visited(dst_wire_idx)) {
             ROUTE_LOG_DBG("   Routed (explored %d wires): ", explored);
-            WireId cursor_bwd = dst_wire;
+            int cursor_bwd = dst_wire_idx;
             while (was_visited(cursor_bwd)) {
-                auto &v = wires.at(cursor_bwd).visit;
+                auto &v = flat_wires.at(cursor_bwd).visit;
                 bind_pip_internal(net, i, cursor_bwd, v.pip);
                 if (ctx->debug) {
-                    auto &wd = wires.at(cursor_bwd);
-                    ROUTE_LOG_DBG("      wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(cursor_bwd),
+                    auto &wd = flat_wires.at(cursor_bwd);
+                    ROUTE_LOG_DBG("      wire: %s (curr %d hist %f share %d)\n", ctx->nameOfWire(wd.w),
                                   int(wd.bound_nets.size()) - 1, wd.hist_cong_cost,
                                   wd.bound_nets.count(net->udata) ? wd.bound_nets.at(net->udata).first : 0);
                 }
                 if (v.pip == PipId()) {
-                    NPNR_ASSERT(cursor_bwd == src_wire);
+                    NPNR_ASSERT(cursor_bwd == src_wire_idx);
                     break;
                 }
                 ROUTE_LOG_DBG("         pip: %s (%d, %d)\n", ctx->nameOfPip(v.pip), ctx->getPipLocation(v.pip).x,
                               ctx->getPipLocation(v.pip).y);
-                cursor_bwd = ctx->getPipSrcWire(v.pip);
+                cursor_bwd = wire_to_idx.at(ctx->getPipSrcWire(v.pip));
             }
             t.processed_sinks.insert(dst_wire);
             ad.routed = true;
@@ -724,14 +734,14 @@ struct Router2
         overused_wires = 0;
         total_wire_use = 0;
         failed_nets.clear();
-        for (auto &wire : wires) {
-            total_wire_use += int(wire.second.bound_nets.size());
-            int overuse = int(wire.second.bound_nets.size()) - 1;
+        for (auto &wire : flat_wires) {
+            total_wire_use += int(wire.bound_nets.size());
+            int overuse = int(wire.bound_nets.size()) - 1;
             if (overuse > 0) {
-                wire.second.hist_cong_cost += overuse * hist_cong_weight;
+                wire.hist_cong_cost += overuse * hist_cong_weight;
                 total_overuse += overuse;
                 overused_wires += 1;
-                for (auto &bound : wire.second.bound_nets)
+                for (auto &bound : wire.bound_nets)
                     failed_nets.insert(bound.first);
             }
         }
@@ -772,7 +782,7 @@ struct Router2
                     break;
                 }
             }
-            auto &wd = wires.at(cursor);
+            auto &wd = wire_data(cursor);
             if (!wd.bound_nets.count(net->udata)) {
                 log("Failure details:\n");
                 log("    Cursor: %s\n", ctx->nameOfWire(cursor));
@@ -833,8 +843,7 @@ struct Router2
     {
         std::vector<std::vector<int>> hm_xy;
         int max_x = 0, max_y = 0;
-        for (auto &w : wires) {
-            auto &wd = w.second;
+        for (auto &wd : flat_wires) {
             int val = int(wd.bound_nets.size()) - (congestion ? 1 : 0);
             if (wd.bound_nets.empty())
                 continue;