18 files changed, 940 insertions, 762 deletions

diff --git a/common/nextpnr.cc b/common/nextpnr.cc
index 8e8a8d19..514017c6 100644
--- a/common/nextpnr.cc
+++ b/common/nextpnr.cc
@@ -18,6 +18,7 @@
  */
 
 #include "nextpnr.h"
+#include "log.h"
 
 NEXTPNR_NAMESPACE_BEGIN
 
@@ -25,6 +26,7 @@ assertion_failure::assertion_failure(std::string msg, std::string expr_str, std:
         : runtime_error("Assertion failure: " + msg + " (" + filename + ":" + std::to_string(line) + ")"), msg(msg),
           expr_str(expr_str), filename(filename), line(line)
 {
+    log_flush();
 }
 
 void IdString::set(const BaseCtx *ctx, const std::string &s)
@@ -152,6 +154,30 @@ void BaseCtx::removeConstraint(IdString constrName)
     constraints.erase(constrName);
 }
 
+const char *BaseCtx::nameOfBel(BelId bel) const
+{
+    const Context *ctx = getCtx();
+    return ctx->getBelName(bel).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfWire(WireId wire) const
+{
+    const Context *ctx = getCtx();
+    return ctx->getWireName(wire).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfPip(PipId pip) const
+{
+    const Context *ctx = getCtx();
+    return ctx->getPipName(pip).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfGroup(GroupId group) const
+{
+    const Context *ctx = getCtx();
+    return ctx->getGroupName(group).c_str(ctx);
+}
+
 WireId Context::getNetinfoSourceWire(const NetInfo *net_info) const
 {
     if (net_info->driver.cell == nullptr)
diff --git a/common/nextpnr.h b/common/nextpnr.h
index 70af6c71..5704e258 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -288,7 +288,7 @@ struct ClockConstraint;
 struct NetInfo : ArchNetInfo
 {
     IdString name;
-    int32_t udata;
+    int32_t udata = 0;
 
     PortRef driver;
     std::vector<PortRef> users;
@@ -579,13 +579,23 @@ struct BaseCtx
 
     const Context *getCtx() const { return reinterpret_cast<const Context *>(this); }
 
-    template <typename T> const char *nameOf(const T *obj)
+    const char *nameOf(IdString name) const
+    {
+        return name.c_str(this);
+    }
+
+    template <typename T> const char *nameOf(const T *obj) const
     {
         if (obj == nullptr)
             return "";
-        return obj->name.c_str(getCtx());
+        return obj->name.c_str(this);
     }
 
+    const char *nameOfBel(BelId bel) const;
+    const char *nameOfWire(WireId wire) const;
+    const char *nameOfPip(PipId pip) const;
+    const char *nameOfGroup(GroupId group) const;
+
     // --------------------------------------------------------------
 
     bool allUiReload = true;
@@ -657,6 +667,7 @@ struct Context : Arch, DeterministicRNG
     delay_t getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &sink) const;
 
     // provided by router1.cc
+    bool checkRoutedDesign() const;
     bool getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay = nullptr,
                              std::unordered_map<WireId, PipId> *route = nullptr, bool useEstimate = true);
 
diff --git a/common/place_common.cc b/common/place_common.cc
index da8ab37d..1c262c6f 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -28,19 +28,19 @@ NEXTPNR_NAMESPACE_BEGIN
 wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type, float &tns)
 {
     wirelen_t wirelength = 0;
-    Loc driver_loc;
-    bool driver_gb;
     CellInfo *driver_cell = net->driver.cell;
     if (!driver_cell)
         return 0;
     if (driver_cell->bel == BelId())
         return 0;
-    driver_gb = ctx->getBelGlobalBuf(driver_cell->bel);
-    driver_loc = ctx->getBelLocation(driver_cell->bel);
+    bool driver_gb = ctx->getBelGlobalBuf(driver_cell->bel);
     if (driver_gb)
         return 0;
+    IdString clock_port;
+    bool timing_driven = ctx->timing_driven && type == MetricType::COST && ctx->getPortTimingClass(driver_cell, net->driver.port, clock_port) != TMG_IGNORE;
     delay_t negative_slack = 0;
     delay_t worst_slack = std::numeric_limits<delay_t>::max();
+    Loc driver_loc = ctx->getBelLocation(driver_cell->bel);
     int xmin = driver_loc.x, xmax = driver_loc.x, ymin = driver_loc.y, ymax = driver_loc.y;
     for (auto load : net->users) {
         if (load.cell == nullptr)
@@ -48,7 +48,7 @@ wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type
         CellInfo *load_cell = load.cell;
         if (load_cell->bel == BelId())
             continue;
-        if (ctx->timing_driven && type == MetricType::COST) {
+        if (timing_driven) {
             delay_t net_delay = ctx->predictDelay(net, load);
             auto slack = load.budget - net_delay;
             if (slack < 0)
@@ -65,7 +65,7 @@ wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type
         xmax = std::max(xmax, load_loc.x);
         ymax = std::max(ymax, load_loc.y);
     }
-    if (ctx->timing_driven && type == MetricType::COST) {
+    if (timing_driven) {
         wirelength = wirelen_t(
                 (((ymax - ymin) + (xmax - xmin)) * std::min(5.0, (1.0 + std::exp(-ctx->getDelayNS(worst_slack) / 5)))));
     } else {
diff --git a/common/router1.cc b/common/router1.cc
index 08c9d701..958c24d4 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -28,24 +28,40 @@ namespace {
 
 USING_NEXTPNR_NAMESPACE
 
-struct hash_id_wire
+struct arc_key
 {
-    std::size_t operator()(const std::pair<IdString, WireId> &arg) const noexcept
+    NetInfo *net_info;
+    int user_idx;
+
+    bool operator==(const arc_key &other) const { return (net_info == other.net_info) && (user_idx == other.user_idx); }
+    bool operator<(const arc_key &other) const { return net_info == other.net_info ? user_idx < other.user_idx : net_info->name < other.net_info->name; }
+
+    struct Hash
     {
-        std::size_t seed = std::hash<IdString>()(arg.first);
-        seed ^= std::hash<WireId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
-        return seed;
-    }
+        std::size_t operator()(const arc_key &arg) const noexcept
+        {
+            std::size_t seed = std::hash<NetInfo *>()(arg.net_info);
+            seed ^= std::hash<int>()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+            return seed;
+        }
+    };
 };
 
-struct hash_id_pip
+struct arc_entry
 {
-    std::size_t operator()(const std::pair<IdString, PipId> &arg) const noexcept
+    arc_key arc;
+    delay_t pri;
+    int randtag = 0;
+
+    struct Less
     {
-        std::size_t seed = std::hash<IdString>()(arg.first);
-        seed ^= std::hash<PipId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
-        return seed;
-    }
+        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
@@ -53,636 +69,662 @@ struct QueuedWire
     WireId wire;
     PipId pip;
 
-    delay_t delay = 0, togo = 0;
+    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.togo, r = rhs.delay + rhs.togo;
+            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 RipupScoreboard
+struct Router1
 {
-    std::unordered_map<WireId, int> wireScores;
-    std::unordered_map<PipId, int> pipScores;
-    std::unordered_map<std::pair<IdString, WireId>, int, hash_id_wire> netWireScores;
-    std::unordered_map<std::pair<IdString, PipId>, int, hash_id_pip> netPipScores;
-};
+    Context *ctx;
+    const Router1Cfg &cfg;
 
-void ripup_net(Context *ctx, IdString net_name)
-{
-    if (ctx->debug)
-        log("Ripping up all routing for net %s.\n", net_name.c_str(ctx));
+    std::priority_queue<arc_entry, std::vector<arc_entry>, arc_entry::Less> arc_queue;
+    std::unordered_map<WireId, std::unordered_set<arc_key, arc_key::Hash>> wire_to_arcs;
+    std::unordered_map<arc_key, std::unordered_set<WireId>, arc_key::Hash> arc_to_wires;
+    std::unordered_set<arc_key, arc_key::Hash> queued_arcs;
 
-    auto net_info = ctx->nets.at(net_name).get();
-    std::vector<PipId> pips;
-    std::vector<WireId> wires;
+    std::unordered_map<WireId, QueuedWire> visited;
+    std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
 
-    pips.reserve(net_info->wires.size());
-    wires.reserve(net_info->wires.size());
+    std::unordered_map<WireId, int> wireScores;
+    std::unordered_map<NetInfo *, int> netScores;
 
-    for (auto &it : net_info->wires) {
-        if (it.second.pip != PipId())
-            pips.push_back(it.second.pip);
-        else
-            wires.push_back(it.first);
-    }
+    int arcs_with_ripup = 0;
+    int arcs_without_ripup = 0;
+    bool ripup_flag;
 
-    for (auto pip : pips)
-        ctx->unbindPip(pip);
+    Router1(Context *ctx, const Router1Cfg &cfg) : ctx(ctx), cfg(cfg) {}
 
-    for (auto wire : wires)
-        ctx->unbindWire(wire);
+    void arc_queue_insert(const arc_key &arc, WireId src_wire, WireId dst_wire)
+    {
+        if (queued_arcs.count(arc))
+            return;
 
-    NPNR_ASSERT(net_info->wires.empty());
-}
+        delay_t pri = ctx->estimateDelay(src_wire, dst_wire) - arc.net_info->users[arc.user_idx].budget;
 
-struct Router
-{
-    Context *ctx;
-    const Router1Cfg &cfg;
-    RipupScoreboard scores;
-    IdString net_name;
+        arc_entry entry;
+        entry.arc = arc;
+        entry.pri = pri;
+        entry.randtag = ctx->rng();
 
-    bool ripup;
-    delay_t ripup_penalty;
+#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
 
-    std::unordered_set<IdString> rippedNets;
-    std::unordered_map<WireId, QueuedWire> visited;
-    int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0;
-    bool routedOkay = false;
-    delay_t maxDelay = 0.0;
-    WireId failedDest;
+        arc_queue.push(entry);
+        queued_arcs.insert(arc);
+    }
 
-    void route(const std::unordered_map<WireId, delay_t> &src_wires, WireId dst_wire)
+    void arc_queue_insert(const arc_key &arc)
     {
-        std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
+        if (queued_arcs.count(arc))
+            return;
 
-        visited.clear();
+        NetInfo *net_info = arc.net_info;
+        int user_idx = arc.user_idx;
 
-        for (auto &it : src_wires) {
-            QueuedWire qw;
-            qw.wire = it.first;
-            qw.pip = PipId();
-            qw.delay = it.second - (it.second / 16);
-            if (cfg.useEstimate)
-                qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
-            qw.randtag = ctx->rng();
+        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
 
-            queue.push(qw);
-            visited[qw.wire] = qw;
-        }
+        arc_queue_insert(arc, src_wire, dst_wire);
+    }
 
-        int thisVisitCnt = 0;
-        int thisVisitCntLimit = 0;
+    arc_key arc_queue_pop()
+    {
+        arc_entry entry = arc_queue.top();
 
-        while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) {
-            QueuedWire qw = queue.top();
-            queue.pop();
+#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
 
-            if (thisVisitCntLimit == 0 && visited.count(dst_wire))
-                thisVisitCntLimit = (thisVisitCnt * 3) / 2;
+        arc_queue.pop();
+        queued_arcs.erase(entry.arc);
+        return entry.arc;
+    }
 
-            for (auto pip : ctx->getPipsDownhill(qw.wire)) {
-                delay_t next_delay = qw.delay + ctx->getPipDelay(pip).maxDelay();
-                WireId next_wire = ctx->getPipDstWire(pip);
-                bool foundRipupNet = false;
-                thisVisitCnt++;
+    void ripup_net(NetInfo *net)
+    {
+        if (ctx->debug)
+            log("      ripup net %s\n", ctx->nameOf(net));
 
-                next_delay += ctx->getWireDelay(next_wire).maxDelay();
+        netScores[net]++;
 
-                if (!ctx->checkWireAvail(next_wire)) {
-                    if (!ripup)
-                        continue;
-                    NetInfo *ripupWireNet = ctx->getConflictingWireNet(next_wire);
-                    if (ripupWireNet == nullptr || ripupWireNet->name == net_name)
-                        continue;
+        std::vector<WireId> wires;
+        for (auto &it : net->wires)
+            wires.push_back(it.first);
 
-                    auto it1 = scores.wireScores.find(next_wire);
-                    if (it1 != scores.wireScores.end())
-                        next_delay += (it1->second * ripup_penalty) / 8;
+        ctx->sorted_shuffle(wires);
 
-                    auto it2 = scores.netWireScores.find(std::make_pair(ripupWireNet->name, next_wire));
-                    if (it2 != scores.netWireScores.end())
-                        next_delay += it2->second * ripup_penalty;
+        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();
 
-                    foundRipupNet = true;
-                }
+            ctx->sorted_shuffle(arcs);
 
-                if (!ctx->checkPipAvail(pip)) {
-                    if (!ripup)
-                        continue;
-                    NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip);
-                    if (ripupPipNet == nullptr || ripupPipNet->name == net_name)
-                        continue;
+            for (auto &it : arcs)
+                arc_queue_insert(it);
 
-                    auto it1 = scores.pipScores.find(pip);
-                    if (it1 != scores.pipScores.end())
-                        next_delay += (it1->second * ripup_penalty) / 8;
+            if (ctx->debug)
+                log("        unbind wire %s\n", ctx->nameOfWire(w));
 
-                    auto it2 = scores.netPipScores.find(std::make_pair(ripupPipNet->name, pip));
-                    if (it2 != scores.netPipScores.end())
-                        next_delay += it2->second * ripup_penalty;
+            ctx->unbindWire(w);
+            wireScores[w]++;
+        }
 
-                    foundRipupNet = true;
-                }
+        ripup_flag = true;
+    }
 
-                if (foundRipupNet)
-                    next_delay += ripup_penalty;
+    void ripup_wire(WireId wire, int extra_indent = 0)
+    {
+        if (ctx->debug)
+            log("    ripup wire %s\n", ctx->nameOfWire(wire));
 
-                NPNR_ASSERT(next_delay >= 0);
+        WireId w = ctx->getConflictingWireWire(wire);
 
-                if (visited.count(next_wire)) {
-                    if (visited.at(next_wire).delay <= next_delay + ctx->getDelayEpsilon())
-                        continue;
-#if 0 // FIXME
-                    if (ctx->debug)
-                        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));
-#endif
-                    if (thisVisitCntLimit == 0)
-                        revisitCnt++;
-                    else
-                        overtimeRevisitCnt++;
-                }
+        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();
 
-                QueuedWire next_qw;
-                next_qw.wire = next_wire;
-                next_qw.pip = pip;
-                next_qw.delay = next_delay;
-                if (cfg.useEstimate)
-                    next_qw.togo = ctx->estimateDelay(next_wire, dst_wire);
-                next_qw.randtag = ctx->rng();
+            ctx->sorted_shuffle(arcs);
 
-                visited[next_qw.wire] = next_qw;
-                queue.push(next_qw);
-            }
+            for (auto &it : arcs)
+                arc_queue_insert(it);
+
+            if (ctx->debug)
+                log("      unbind wire %s\n", ctx->nameOfWire(w));
+
+            ctx->unbindWire(w);
+            wireScores[w]++;
         }
 
-        visitCnt += thisVisitCnt;
+        ripup_flag = true;
     }
 
-    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)
+    void ripup_pip(PipId pip)
     {
-        std::unordered_map<WireId, delay_t> src_wires;
-        src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
-        route(src_wires, dst_wire);
-        routedOkay = visited.count(dst_wire);
+        if (ctx->debug)
+            log("    ripup pip %s\n", ctx->nameOfPip(pip));
 
-        if (ctx->debug) {
-            log("Route (from destination to source):\n");
+        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();
 
-            WireId cursor = dst_wire;
+            ctx->sorted_shuffle(arcs);
 
-            while (1) {
-                log("  %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx));
+            for (auto &it : arcs)
+                arc_queue_insert(it);
 
-                if (cursor == src_wire)
-                    break;
+            if (ctx->debug)
+                log("      unbind wire %s\n", ctx->nameOfWire(w));
 
-                cursor = ctx->getPipSrcWire(visited[cursor].pip);
-            }
+            ctx->unbindWire(w);
+            wireScores[w]++;
         }
+
+        ripup_flag = true;
     }
 
-    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)
+    bool skip_net(NetInfo *net_info)
     {
-        auto net_info = ctx->nets.at(net_name).get();
-
-        if (ctx->debug)
-            log("Routing net %s.\n", net_name.c_str(ctx));
-
-        if (ctx->debug)
-            log("  Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx), net_info->driver.port.c_str(ctx));
+#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;
 
-        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+        return false;
+    }
 
-        if (src_wire == WireId())
-            log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
-                      net_info->driver.cell->name.c_str(ctx));
+    void check()
+    {
+        std::unordered_set<arc_key, arc_key::Hash> valid_arcs;
 
-        if (ctx->debug)
-            log("    Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx));
+        for (auto &net_it : ctx->nets) {
+            NetInfo *net_info = net_it.second.get();
+            std::unordered_set<WireId> valid_wires_for_net;
 
-        std::unordered_map<WireId, delay_t> src_wires;
-        std::vector<std::pair<delay_t, int>> users_array;
+            if (skip_net(net_info))
+                continue;
 
-        if (user_idx < 0) {
-            // 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(std::pair<delay_t, int>(delay_t(), user_idx));
-        }
+#if 0
+            if (ctx->debug)
+                log("[check] net: %s\n", ctx->nameOf(net_info));
+#endif
 
-        if (reroute) {
-            // complete ripup
-            ripup_net(ctx, net_name);
-            ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
-            src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
-        } else {
-            // re-use existing routes as much as possible
-            if (net_info->wires.count(src_wire) == 0)
-                ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
-            src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
+            auto src_wire = ctx->getNetinfoSourceWire(net_info);
+            log_assert(src_wire != WireId());
 
             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]);
+                log_assert(dst_wire != WireId());
 
-                if (dst_wire == WireId())
-                    log_error("No wire found for port %s on destination cell %s.\n",
-                              net_info->users[user_idx].port.c_str(ctx),
-                              net_info->users[user_idx].cell->name.c_str(ctx));
-
-                std::function<delay_t(WireId)> register_existing_path =
-                        [ctx, net_info, &src_wires, &register_existing_path](WireId wire) -> delay_t {
-                    auto it = src_wires.find(wire);
-                    if (it != src_wires.end())
-                        return it->second;
-
-                    PipId pip = net_info->wires.at(wire).pip;
-                    delay_t delay = register_existing_path(ctx->getPipSrcWire(pip));
-                    delay += ctx->getPipDelay(pip).maxDelay();
-                    delay += ctx->getWireDelay(wire).maxDelay();
-                    src_wires[wire] = delay;
+                arc_key arc;
+                arc.net_info = net_info;
+                arc.user_idx = user_idx;
 
-                    return delay;
-                };
+                valid_arcs.insert(arc);
+#if 0
+                if (ctx->debug)
+                    log("[check]   arc: %s %s\n", ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire));
+#endif
 
-                WireId cursor = dst_wire;
-                while (src_wires.count(cursor) == 0) {
-                    auto it = net_info->wires.find(cursor);
-                    if (it == net_info->wires.end())
-                        goto check_next_user_for_existing_path;
-                    NPNR_ASSERT(it->second.pip != PipId());
-                    cursor = ctx->getPipSrcWire(it->second.pip);
+                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));
                 }
-
-                register_existing_path(dst_wire);
-            check_next_user_for_existing_path:;
             }
 
-            std::vector<WireId> ripup_wires;
-            for (auto &it : net_info->wires)
-                if (src_wires.count(it.first) == 0)
-                    ripup_wires.push_back(it.first);
-
-            for (auto &it : ripup_wires) {
-                if (ctx->debug)
-                    log("  Unbind dangling wire for net %s: %s\n", net_name.c_str(ctx),
-                        ctx->getWireName(it).c_str(ctx));
-                ctx->unbindWire(it);
+            for (auto &it : net_info->wires) {
+                WireId w = it.first;
+                log_assert(valid_wires_for_net.count(w));
             }
         }
 
-        for (auto user_idx_it : users_array) {
-            int user_idx = user_idx_it.second;
+        for (auto &it : wire_to_arcs) {
+            for (auto &arc : it.second)
+                log_assert(valid_arcs.count(arc));
+        }
 
-            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));
+        for (auto &it : arc_to_wires) {
+            log_assert(valid_arcs.count(it.first));
+        }
+    }
 
-            auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+    void setup()
+    {
+        std::unordered_map<WireId, NetInfo *> src_to_net;
+        std::unordered_map<WireId, arc_key> dst_to_arc;
 
-            if (dst_wire == WireId())
-                log_error("No wire found for port %s on destination cell %s.\n",
-                          net_info->users[user_idx].port.c_str(ctx), net_info->users[user_idx].cell->name.c_str(ctx));
+        std::vector<IdString> net_names;
+        for (auto &net_it : ctx->nets)
+            net_names.push_back(net_it.first);
 
-            if (ctx->debug) {
-                log("    Destination wire: %s\n", ctx->getWireName(dst_wire).c_str(ctx));
-                log("    Path delay estimate: %.2f\n", float(ctx->estimateDelay(src_wire, dst_wire)));
-            }
+        ctx->sorted_shuffle(net_names);
 
-            route(src_wires, dst_wire);
+        for (IdString net_name : net_names) {
+            NetInfo *net_info = ctx->nets.at(net_name).get();
 
-            if (visited.count(dst_wire) == 0) {
-                if (ctx->debug)
-                    log("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx),
-                        ctx->getWireName(dst_wire).c_str(ctx));
-                else if (ripup)
-                    log_info("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx),
-                             ctx->getWireName(dst_wire).c_str(ctx));
-                ripup_net(ctx, net_name);
-                failedDest = dst_wire;
-                return;
-            }
+            if (skip_net(net_info))
+                continue;
 
-            if (ctx->debug)
-                log("    Final path delay: %.3f\n", ctx->getDelayNS(visited[dst_wire].delay));
-            maxDelay = fmaxf(maxDelay, visited[dst_wire].delay);
+            auto src_wire = ctx->getNetinfoSourceWire(net_info);
 
-            if (ctx->debug)
-                log("    Route (from destination to source):\n");
+            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));
 
-            WireId cursor = dst_wire;
+            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)));
 
-            while (1) {
-                if (ctx->debug)
-                    log("    %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx));
+            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);
 
-                if (src_wires.count(cursor))
-                    break;
+            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]);
 
-                NetInfo *conflicting_wire_net = ctx->getConflictingWireNet(cursor);
+                if (dst_wire == WireId())
+                    log_error("No wire found for port %s on destination cell %s.\n",
+                              ctx->nameOf(net_info->users[user_idx].port),
+                              ctx->nameOf(net_info->users[user_idx].cell));
 
-                if (conflicting_wire_net != nullptr) {
-                    NPNR_ASSERT(ripup);
-                    NPNR_ASSERT(conflicting_wire_net->name != net_name);
+                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_idx,
+                              ctx->nameOf(dst_to_arc.at(dst_wire).net_info), dst_to_arc.at(dst_wire).user_idx);
+                }
 
-                    ctx->unbindWire(cursor);
-                    if (!ctx->checkWireAvail(cursor))
-                        ripup_net(ctx, conflicting_wire_net->name);
+                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_idx);
 
-                    rippedNets.insert(conflicting_wire_net->name);
-                    scores.wireScores[cursor]++;
-                    scores.netWireScores[std::make_pair(net_name, cursor)]++;
-                    scores.netWireScores[std::make_pair(conflicting_wire_net->name, cursor)]++;
-                }
+                arc_key arc;
+                arc.net_info = net_info;
+                arc.user_idx = user_idx;
 
-                PipId pip = visited[cursor].pip;
-                NetInfo *conflicting_pip_net = ctx->getConflictingPipNet(pip);
+                dst_to_arc[dst_wire] = arc;
 
-                if (conflicting_pip_net != nullptr) {
-                    NPNR_ASSERT(ripup);
-                    NPNR_ASSERT(conflicting_pip_net->name != net_name);
+                if (net_info->wires.count(src_wire) == 0) {
+                    arc_queue_insert(arc, src_wire, dst_wire);
+                    continue;
+                }
 
-                    if (ctx->getBoundPipNet(pip) == conflicting_pip_net)
-                        ctx->unbindPip(pip);
+                WireId cursor = dst_wire;
+                wire_to_arcs[cursor].insert(arc);
+                arc_to_wires[arc].insert(cursor);
 
-                    if (!ctx->checkPipAvail(pip))
-                        ripup_net(ctx, conflicting_pip_net->name);
+                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;
+                    }
 
-                    rippedNets.insert(conflicting_pip_net->name);
-                    scores.pipScores[visited[cursor].pip]++;
-                    scores.netPipScores[std::make_pair(net_name, visited[cursor].pip)]++;
-                    scores.netPipScores[std::make_pair(conflicting_pip_net->name, visited[cursor].pip)]++;
+                    NPNR_ASSERT(it->second.pip != PipId());
+                    cursor = ctx->getPipSrcWire(it->second.pip);
+                    wire_to_arcs[cursor].insert(arc);
+                    arc_to_wires[arc].insert(cursor);
                 }
-
-                ctx->bindPip(visited[cursor].pip, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
-                src_wires[cursor] = visited[cursor].delay;
-                cursor = ctx->getPipSrcWire(visited[cursor].pip);
             }
-        }
 
-        routedOkay = true;
-    }
-};
+            src_to_net[src_wire] = net_info;
 
-struct RouteJob
-{
-    IdString net;
-    int user_idx = -1;
-    delay_t slack = 0;
-    int randtag = 0;
+            std::vector<WireId> unbind_wires;
 
-    struct Greater
-    {
-        bool operator()(const RouteJob &lhs, const RouteJob &rhs) const noexcept
-        {
-            return lhs.slack == rhs.slack ? lhs.randtag > rhs.randtag : lhs.slack > rhs.slack;
-        }
-    };
-};
+            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);
 
-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();
+            for (auto it : unbind_wires)
+                ctx->unbindWire(it);
+        }
+    }
 
-    if (net_info->driver.cell == nullptr)
-        return;
+    bool route_arc(const arc_key &arc, bool ripup)
+    {
 
-    auto src_wire = ctx->getNetinfoSourceWire(net_info);
+        NetInfo *net_info = arc.net_info;
+        int user_idx = arc.user_idx;
 
-    if (src_wire == WireId())
-        log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
-                  net_info->driver.cell->name.c_str(ctx));
+        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+        ripup_flag = false;
 
-    auto &net_cache = cache[net_name];
+        if (ctx->debug) {
+            log("Routing arc %d on net %s (%d arcs total):\n", user_idx, ctx->nameOf(net_info),
+                int(net_info->users.size()));
+            log("  source ... %s\n", ctx->nameOfWire(src_wire));
+            log("  sink ..... %s\n", ctx->nameOfWire(dst_wire));
+        }
 
-    if (net_cache.empty())
-        net_cache.resize(net_info->users.size());
+        // unbind wires that are currently used exclusively by this arc
 
-    RouteJob job;
-    job.net = net_name;
-    job.user_idx = -1;
-    job.slack = 0;
-    job.randtag = ctx->rng();
+        std::unordered_set<WireId> old_arc_wires;
+        old_arc_wires.swap(arc_to_wires[arc]);
 
-    bool got_slack = false;
+        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);
+            }
+        }
 
-    for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
-        if (net_cache[user_idx])
-            continue;
+        // reset wire queue
 
-        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+        if (!queue.empty()) {
+            std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> new_queue;
+            queue.swap(new_queue);
+        }
+        visited.clear();
 
-        if (dst_wire == WireId())
-            log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx),
-                      net_info->users[user_idx].cell->name.c_str(ctx));
+        // A* main loop
 
-        if (user_idx == 0)
-            job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
-        else
-            job.slack = std::min(job.slack, net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire));
+        int visitCnt = 0;
+        int maxVisitCnt = INT_MAX;
+        delay_t best_est = 0;
+        delay_t best_score = -1;
 
-        WireId cursor = dst_wire;
-        while (src_wire != cursor) {
-            auto it = net_info->wires.find(cursor);
-            if (it == net_info->wires.end()) {
-                if (!got_slack)
-                    job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
-                else
-                    job.slack = std::min(job.slack,
-                                         net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire));
-                got_slack = true;
-                break;
+        {
+            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;
             }
-            NPNR_ASSERT(it->second.pip != PipId());
-            cursor = ctx->getPipSrcWire(it->second.pip);
+            qw.randtag = ctx->rng();
+
+            queue.push(qw);
+            visited[qw.wire] = qw;
         }
-    }
 
-    queue.push(job);
+        while (visitCnt++ < maxVisitCnt && !queue.empty()) {
+            QueuedWire qw = queue.top();
+            queue.pop();
 
-    for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++)
-        net_cache[user_idx] = true;
-}
+            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;
 
-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();
+                WireId next_wire = ctx->getPipDstWire(pip);
+                next_delay += ctx->getWireDelay(next_wire).maxDelay();
 
-#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;
-#endif
-    if (net_info->driver.cell == nullptr)
-        return;
+                WireId conflictWireWire = WireId(), conflictPipWire = WireId();
+                NetInfo *conflictWireNet = nullptr, *conflictPipNet = nullptr;
 
-    auto src_wire = ctx->getNetinfoSourceWire(net_info);
+                if (net_info->wires.count(next_wire) && net_info->wires.at(next_wire).pip == pip) {
+                    next_bonus += cfg.reuseBonus;
+                } 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;
+                        }
+                    }
 
-    if (src_wire == WireId())
-        log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
-                  net_info->driver.cell->name.c_str(ctx));
+                    if (!ctx->checkPipAvail(pip)) {
+                        if (!ripup)
+                            continue;
+                        conflictPipWire = ctx->getConflictingPipWire(pip);
+                        if (conflictPipWire == WireId()) {
+                            conflictPipNet = ctx->getConflictingPipNet(pip);
+                            if (conflictPipNet == nullptr)
+                                continue;
+                        }
+                    }
 
-    auto &net_cache = cache[net_name];
+                    if (conflictWireNet != nullptr && conflictPipWire != WireId() &&
+                        conflictWireNet->wires.count(conflictPipWire))
+                        conflictPipWire = WireId();
 
-    if (net_cache.empty())
-        net_cache.resize(net_info->users.size());
+                    if (conflictPipNet != nullptr && conflictWireWire != WireId() &&
+                        conflictPipNet->wires.count(conflictWireWire))
+                        conflictWireWire = WireId();
 
-    for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
-        if (net_cache[user_idx])
-            continue;
+                    if (conflictWireWire == conflictPipWire)
+                        conflictWireWire = WireId();
 
-        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+                    if (conflictWireNet == conflictPipNet)
+                        conflictWireNet = nullptr;
 
-        if (dst_wire == WireId())
-            log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx),
-                      net_info->users[user_idx].cell->name.c_str(ctx));
+                    if (conflictWireWire != WireId()) {
+                        auto scores_it = wireScores.find(conflictWireWire);
+                        if (scores_it != wireScores.end())
+                            next_penalty += scores_it->second * cfg.wireRipupPenalty;
+                        next_penalty += cfg.wireRipupPenalty;
+                    }
 
-        WireId cursor = dst_wire;
-        while (src_wire != cursor) {
-            auto it = net_info->wires.find(cursor);
-            if (it == net_info->wires.end()) {
-                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();
-                queue.push(job);
-                net_cache[user_idx] = true;
-                break;
-            }
-            NPNR_ASSERT(it->second.pip != PipId());
-            cursor = ctx->getPipSrcWire(it->second.pip);
-        }
-    }
-}
+                    if (conflictPipWire != WireId()) {
+                        auto scores_it = wireScores.find(conflictPipWire);
+                        if (scores_it != wireScores.end())
+                            next_penalty += scores_it->second * cfg.wireRipupPenalty;
+                        next_penalty += cfg.wireRipupPenalty;
+                    }
 
-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;
+                    if (conflictWireNet != nullptr) {
+                        auto scores_it = netScores.find(conflictWireNet);
+                        if (scores_it != netScores.end())
+                            next_penalty += scores_it->second * cfg.netRipupPenalty;
+                        next_penalty += cfg.netRipupPenalty;
+                        next_penalty += conflictWireNet->wires.size() * cfg.wireRipupPenalty;
+                    }
 
-    for (auto net_name : cleanupQueue) {
-        NetInfo *net_info = ctx->nets.at(net_name).get();
-        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+                    if (conflictPipNet != nullptr) {
+                        auto scores_it = netScores.find(conflictPipNet);
+                        if (scores_it != netScores.end())
+                            next_penalty += scores_it->second * cfg.netRipupPenalty;
+                        next_penalty += cfg.netRipupPenalty;
+                        next_penalty += conflictPipNet->wires.size() * cfg.wireRipupPenalty;
+                    }
+                }
 
-        if (ctx->verbose)
-            allNetinfos.push_back(net_info);
+                delay_t next_score = next_delay + next_penalty;
+                NPNR_ASSERT(next_score >= 0);
 
-        std::unordered_map<WireId, int> useCounters;
-        std::vector<int> candidateArcs;
+                if ((best_score >= 0) && (next_score - next_bonus - cfg.estimatePrecision > best_score))
+                    continue;
 
-        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]);
+                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 (dst_wire == src_wire)
-                continue;
+                    if (next_score + ctx->getDelayEpsilon() >= old_score)
+                        continue;
 
-            auto cursor = dst_wire;
-            useCounters[cursor]++;
+#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
+                }
 
-            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]++;
-            }
+                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 (cursor != src_wire)
-                continue;
+#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);
 
-            candidateArcs.push_back(user_idx);
+                if (next_wire == dst_wire) {
+                    maxVisitCnt = std::min(maxVisitCnt, 2 * visitCnt + (next_qw.penalty > 0 ? 100 : 0));
+                    best_score = next_score - next_bonus;
+                }
+            }
         }
 
-        for (int user_idx : candidateArcs) {
-            auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+        if (ctx->debug)
+            log("  total number of visited nodes: %d\n", visitCnt);
 
-            if (useCounters.at(dst_wire) != 1)
-                continue;
+        if (visited.count(dst_wire) == 0) {
+            if (ctx->debug)
+                log("  no route found for this arc\n");
+            return false;
+        }
 
-            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);
+        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));
         }
-    }
 
-    log_info("running cleanup re-route of %d nets (%d arcs).\n", int(cleanupQueue.size()), int(cleanupJobs.size()));
+        // bind resulting route (and maybe unroute other nets)
 
-    cleanupQueue.clear();
+        std::unordered_set<WireId> unassign_wires = arc_to_wires[arc];
 
-    int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0;
-    int totalWireCountDelta = 0;
+        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->verbose) {
-        for (auto it : allNetinfos)
-            totalWireCountDelta -= it->wires.size();
-    }
+            if (ctx->debug) {
+                delay_t path_delay_delta = ctx->estimateDelay(cursor, dst_wire) - accumulated_path_delay;
 
-    while (!cleanupJobs.empty()) {
-        RouteJob job = cleanupJobs.top();
-        cleanupJobs.pop();
+                log("  node %s (%+.2f %+.2f)\n", ctx->nameOfWire(cursor), ctx->getDelayNS(path_delay_delta),
+                    ctx->getDelayNS(path_delay_delta - last_path_delay_delta));
 
-        auto net_name = job.net;
-        auto user_idx = job.user_idx;
+                last_path_delay_delta = path_delay_delta;
 
-        NetInfo *net_info = ctx->nets.at(net_name).get();
-        auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+                if (pip != PipId())
+                    accumulated_path_delay += ctx->getPipDelay(pip).maxDelay();
+                accumulated_path_delay += ctx->getWireDelay(cursor).maxDelay();
+            }
 
-        ctx->unbindWire(dst_wire);
+            if (pip == PipId())
+                NPNR_ASSERT(cursor == src_wire);
 
-        Router router(ctx, cfg, scores, net_name, user_idx, false, false);
+            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 (!router.routedOkay)
-            log_error("Failed to re-route arc %d of net %s.\n", user_idx, net_name.c_str(ctx));
+                if (pip != PipId() && !ctx->checkPipAvail(pip)) {
+                    ripup_pip(pip);
+                    NPNR_ASSERT(ctx->checkPipAvail(pip));
+                }
 
-        visitCnt += router.visitCnt;
-        revisitCnt += router.revisitCnt;
-        overtimeRevisitCnt += router.overtimeRevisitCnt;
-    }
+                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);
+                }
+            }
 
-    if (ctx->verbose) {
-        for (auto it : allNetinfos)
-            totalWireCountDelta += it->wires.size();
+            wire_to_arcs[cursor].insert(arc);
+            arc_to_wires[arc].insert(cursor);
 
-        log_info("  visited %d PIPs (%.2f%% revisits, %.2f%% overtime), %+d wires.\n", visitCnt,
-                 (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt, totalWireCountDelta);
-    }
+            if (pip == PipId())
+                break;
 
-    totalVisitCnt += visitCnt;
-    totalRevisitCnt += revisitCnt;
-    totalOvertimeRevisitCnt += overtimeRevisitCnt;
-}
+            cursor = ctx->getPipSrcWire(pip);
+        }
+
+        if (ripup_flag)
+            arcs_with_ripup++;
+        else
+            arcs_without_ripup++;
+
+        return true;
+    }
+};
 
 } // namespace
 
@@ -694,302 +736,265 @@ Router1Cfg::Router1Cfg(Context *ctx) : Settings(ctx)
     cleanupReroute = get<bool>("router1/cleanupReroute", true);
     fullCleanupReroute = get<bool>("router1/fullCleanupReroute", true);
     useEstimate = get<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 {
-        int totalVisitCnt = 0, totalRevisitCnt = 0, totalOvertimeRevisitCnt = 0;
-        delay_t ripup_penalty = ctx->getRipupDelayPenalty();
-        RipupScoreboard scores;
-
         log_break();
         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;
+        log_info("Setting up routing queue.\n");
 
-        for (auto &net_it : ctx->nets)
-            addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
+        Router1 router(ctx, cfg);
+        router.setup();
+#ifndef NDEBUG
+        router.check();
+#endif
 
-        if (jobQueue.empty()) {
-            log_info("found no unrouted source-sink pairs. no routing necessary.\n");
-            ctx->unlock();
-            return true;
-        }
+        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;
+
+        log_info("           |   (re-)routed arcs  |   delta    | remaining\n");
+        log_info("   IterCnt |  w/ripup   wo/ripup |  w/r  wo/r |      arcs\n");
+
+        while (!router.arc_queue.empty()) {
+            if (++iter_cnt % 1000 == 0) {
+                log_info("%10d | %8d %10d | %4d %5d | %9d\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()));
+                last_arcs_with_ripup = router.arcs_with_ripup;
+                last_arcs_without_ripup = router.arcs_without_ripup;
+#ifndef NDEBUG
+                router.check();
+#endif
+            }
 
-        log_info("found %d unrouted source-sink pairs. starting routing procedure.\n", int(jobQueue.size()));
+            if (ctx->debug)
+                log("-- %d --\n", iter_cnt);
 
-        int iterCnt = 0;
+            arc_key arc = router.arc_queue_pop();
 
-        while (!jobQueue.empty()) {
-            if (iterCnt == cfg.maxIterCnt) {
-                log_warning("giving up after %d iterations.\n", iterCnt);
-                log_info("Checksum: 0x%08x\n", ctx->checksum());
+            if (!router.route_arc(arc, true)) {
+                log_warning("Failed to find a route for arc %d of net %s.\n", arc.user_idx, ctx->nameOf(arc.net_info));
 #ifndef NDEBUG
+                router.check();
                 ctx->check();
 #endif
                 ctx->unlock();
                 return false;
             }
+        }
 
-            iterCnt++;
-            if (ctx->verbose)
-                log_info("-- %d --\n", iterCnt);
-
-            int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, jobCnt = 0, failedCnt = 0;
+        log_info("%10d | %8d %10d | %4d %5d | %9d\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()));
+        log_info("Routing complete.\n");
 
-            std::unordered_set<IdString> normalRouteNets, ripupQueue;
+#ifndef NDEBUG
+        router.check();
+        ctx->check();
+        log_assert(ctx->checkRoutedDesign());
+#endif
 
-            if (ctx->verbose || iterCnt == 1)
-                log_info("routing queue contains %d jobs.\n", int(jobQueue.size()));
-            else if (ctx->slack_redist_iter > 0 && iterCnt % ctx->slack_redist_iter == 0)
-                assign_budget(ctx, true /* quiet */);
+        log_info("Checksum: 0x%08x\n", ctx->checksum());
+        timing_analysis(ctx, true /* slack_histogram */, true /* print_fmax */, true /* print_path */);
 
-            bool printNets = ctx->verbose && (jobQueue.size() < 10);
+        ctx->unlock();
+        return true;
+    } catch (log_execution_error_exception) {
+#ifndef NDEBUG
+        ctx->check();
+#endif
+        ctx->unlock();
+        return false;
+    }
+}
 
-            while (!jobQueue.empty()) {
-                if (ctx->debug)
-                    log("Next job slack: %f\n", double(jobQueue.top().slack));
+bool Context::checkRoutedDesign() const
+{
+    const Context *ctx = getCtx();
 
-                auto net_name = jobQueue.top().net;
-                auto user_idx = jobQueue.top().user_idx;
-                jobQueue.pop();
+    for (auto &net_it : ctx->nets) {
+        NetInfo *net_info = net_it.second.get();
 
-                if (cfg.fullCleanupReroute)
-                    cleanupQueue.insert(net_name);
+#ifdef ARCH_ECP5
+        if (net_info->is_global)
+            continue;
+#endif
 
-                if (printNets) {
-                    if (user_idx < 0)
-                        log_info("  routing all %d users of net %s\n", int(ctx->nets.at(net_name)->users.size()),
-                                 net_name.c_str(ctx));
-                    else
-                        log_info("  routing user %d of net %s\n", user_idx, net_name.c_str(ctx));
-                }
+        if (ctx->debug)
+            log("checking net %s\n", ctx->nameOf(net_info));
 
-                Router router(ctx, cfg, scores, net_name, user_idx, false, false);
+        if (net_info->users.empty()) {
+            if (ctx->debug)
+                log("  net without sinks\n");
+            log_assert(net_info->wires.empty());
+            continue;
+        }
 
-                jobCnt++;
-                visitCnt += router.visitCnt;
-                revisitCnt += router.revisitCnt;
-                overtimeRevisitCnt += router.overtimeRevisitCnt;
+        bool found_unrouted = false;
+        bool found_loop = false;
+        bool found_stub = false;
 
-                if (!router.routedOkay) {
-                    if (printNets)
-                        log_info("    failed to route to %s.\n", ctx->getWireName(router.failedDest).c_str(ctx));
-                    ripupQueue.insert(net_name);
-                    failedCnt++;
-                } else {
-                    normalRouteNets.insert(net_name);
-                }
+        struct ExtraWireInfo
+        {
+            int order_num = 0;
+            std::unordered_set<WireId> children;
+        };
 
-                if ((ctx->verbose || iterCnt == 1) && !printNets && (jobCnt % 100 == 0)) {
-                    log_info("  processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt);
-                    ctx->yield();
-                }
-            }
+        std::unordered_map<WireId, ExtraWireInfo> db;
 
-            NPNR_ASSERT(jobQueue.empty());
-            jobCache.clear();
+        for (auto &it : net_info->wires) {
+            WireId w = it.first;
+            PipId p = it.second.pip;
 
-            if ((ctx->verbose || iterCnt == 1) && (jobCnt % 100 != 0)) {
-                log_info("  processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt);
-                ctx->yield();
+            if (p != PipId()) {
+                log_assert(ctx->getPipDstWire(p) == w);
+                db[ctx->getPipSrcWire(p)].children.insert(w);
             }
+        }
 
-            if (ctx->verbose)
-                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()));
-
-                printNets = ctx->verbose && (ripupQueue.size() < 10);
-
-                visitCnt = 0;
-                revisitCnt = 0;
-                overtimeRevisitCnt = 0;
-                int netCnt = 0;
-                int ripCnt = 0;
-
-                std::vector<IdString> ripupArray(ripupQueue.begin(), ripupQueue.end());
-                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, cfg, scores, net_name, -1, false, true, ripup_penalty);
-
-                    netCnt++;
-                    visitCnt += router.visitCnt;
-                    revisitCnt += router.revisitCnt;
-                    overtimeRevisitCnt += router.overtimeRevisitCnt;
+        auto src_wire = ctx->getNetinfoSourceWire(net_info);
+        log_assert(src_wire != WireId());
 
-                    if (!router.routedOkay)
-                        log_error("Net %s is impossible to route.\n", net_name.c_str(ctx));
+        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;
+        }
 
-                    for (auto it : router.rippedNets) {
-                        addFullNetRouteJob(ctx, cfg, it, jobCache, jobQueue);
-                        if (cfg.cleanupReroute)
-                            cleanupQueue.insert(it);
-                    }
+        std::unordered_map<WireId, int> dest_wires;
+        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]);
+            log_assert(dst_wire != WireId());
+            dest_wires[dst_wire] = user_idx;
 
-                    if (printNets) {
-                        if (router.rippedNets.size() < 10) {
-                            log_info("    ripped up %d other nets:\n", int(router.rippedNets.size()));
-                            for (auto n : router.rippedNets)
-                                log_info("      %s (%d users)\n", n.c_str(ctx), int(ctx->nets.at(n)->users.size()));
-                        } else {
-                            log_info("    ripped up %d other nets.\n", int(router.rippedNets.size()));
-                        }
-                    }
+            if (net_info->wires.count(dst_wire) == 0) {
+                if (ctx->debug)
+                    log("  sink %d (%s) not bound to net\n", user_idx, ctx->nameOfWire(dst_wire));
+                found_unrouted = true;
+            }
+        }
 
-                    ripCnt += router.rippedNets.size();
+        std::function<void(WireId, int)> setOrderNum;
+        std::unordered_set<WireId> logged_wires;
 
-                    if ((ctx->verbose || iterCnt == 1) && !printNets && (netCnt % 100 == 0)) {
-                        log_info("  routed %d nets, ripped %d nets.\n", netCnt, ripCnt);
-                        ctx->yield();
-                    }
+        setOrderNum = [&](WireId w, int num) {
+            auto &db_entry = db[w];
+            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);
                 }
-
-                if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0))
-                    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);
-
-                if (ctx->verbose && !jobQueue.empty())
-                    log_info("  ripped up %d previously routed nets. continue routing.\n", int(jobQueue.size()));
+                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));
+                } else {
+                    if (ctx->debug)
+                        log("  %*s=> stub\n", 2 * num, "");
+                    found_stub = true;
+                }
+            }
+        };
 
-            if (!ctx->verbose)
-                log_info("iteration %d: routed %d nets without ripup, routed %d nets with ripup.\n", iterCnt,
-                         int(normalRouteNets.size()), int(ripupQueue.size()));
-
-            totalVisitCnt += visitCnt;
-            totalRevisitCnt += revisitCnt;
-            totalOvertimeRevisitCnt += overtimeRevisitCnt;
-
-            if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || iterCnt == 128)
-                ripup_penalty += ctx->getRipupDelayPenalty();
+        if (ctx->debug) {
+            log("  driver: %s\n", ctx->nameOfWire(src_wire));
+            logged_wires.insert(src_wire);
+        }
+        setOrderNum(src_wire, 1);
 
-            if (jobQueue.empty() || (iterCnt % 5) == 0 || (cfg.fullCleanupReroute && iterCnt == 1))
-                cleanupReroute(ctx, cfg, scores, cleanupQueue, jobQueue, totalVisitCnt, totalRevisitCnt,
-                               totalOvertimeRevisitCnt);
+        std::unordered_set<WireId> dangling_wires;
 
-            ctx->yield();
+        for (auto &it : db) {
+            auto &db_entry = it.second;
+            if (db_entry.order_num == 0)
+                dangling_wires.insert(it.first);
         }
 
-        log_info("routing complete after %d iterations.\n", iterCnt);
+        if (ctx->debug) {
+            if (dangling_wires.empty()) {
+                log("  no dangling wires.\n");
+            } else {
+                std::unordered_set<WireId> root_wires = dangling_wires;
+
+                for (WireId w : dangling_wires) {
+                    for (WireId c : db[w].children)
+                        root_wires.erase(c);
+                }
 
-        log_info("visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", totalVisitCnt,
-                 (100.0 * totalRevisitCnt) / totalVisitCnt, (100.0 * totalOvertimeRevisitCnt) / totalVisitCnt);
+                for (WireId w : root_wires) {
+                    log("  dangling wire: %s\n", ctx->nameOfWire(w));
+                    logged_wires.insert(w);
+                    setOrderNum(w, 1);
+                }
 
-        {
-            float tns = 0;
-            int tns_net_count = 0;
-            int tns_arc_count = 0;
-            for (auto &net_it : ctx->nets) {
-                bool got_negative_slack = false;
-                NetInfo *net_info = ctx->nets.at(net_it.first).get();
-                for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
-                    delay_t arc_delay = ctx->getNetinfoRouteDelay(net_info, net_info->users[user_idx]);
-                    delay_t arc_budget = net_info->users[user_idx].budget;
-                    delay_t arc_slack = arc_budget - arc_delay;
-                    if (arc_slack < 0) {
-                        if (!got_negative_slack) {
-                            if (ctx->verbose)
-                                log_info("net %s has negative slack arcs:\n", net_info->name.c_str(ctx));
-                            tns_net_count++;
-                        }
-                        if (ctx->verbose)
-                            log_info("  arc %s -> %s has %f ns slack (delay %f, budget %f)\n",
-                                     ctx->getWireName(ctx->getNetinfoSourceWire(net_info)).c_str(ctx),
-                                     ctx->getWireName(ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]))
-                                             .c_str(ctx),
-                                     ctx->getDelayNS(arc_slack), ctx->getDelayNS(arc_delay),
-                                     ctx->getDelayNS(arc_budget));
-                        tns += ctx->getDelayNS(arc_slack);
-                        tns_arc_count++;
-                    }
+                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));
                 }
             }
-            log_info("final tns with respect to arc budgets: %f ns (%d nets, %d arcs)\n", tns, tns_net_count,
-                     tns_arc_count);
         }
 
-        NPNR_ASSERT(jobQueue.empty());
-        jobCache.clear();
+        bool fail = false;
 
-        for (auto &net_it : ctx->nets)
-            addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
+        if (found_unrouted) {
+            if (ctx->debug)
+                log("check failed: found unrouted arcs\n");
+            fail = true;
+        }
 
-#ifndef NDEBUG
-        if (!jobQueue.empty()) {
-            log_info("Design strangely still contains unrouted source-sink pairs:\n");
-            while (!jobQueue.empty()) {
-                log_info("  user %d on net %s.\n", jobQueue.top().user_idx, jobQueue.top().net.c_str(ctx));
-                jobQueue.pop();
-            }
-            log_info("Checksum: 0x%08x\n", ctx->checksum());
-            ctx->check();
-            ctx->unlock();
-            return false;
+        if (found_loop) {
+            if (ctx->debug)
+                log("check failed: found loops\n");
+            fail = true;
         }
-#endif
 
-        log_info("Checksum: 0x%08x\n", ctx->checksum());
-#ifndef NDEBUG
-        ctx->check();
-#endif
-        timing_analysis(ctx, true /* slack_histogram */, true /* print_fmax */, true /* print_path */);
-        ctx->unlock();
-        return true;
-    } catch (log_execution_error_exception) {
-#ifndef NDEBUG
-        ctx->check();
-#endif
-        ctx->unlock();
-        return false;
+        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,
                                   std::unordered_map<WireId, PipId> *route, bool useEstimate)
 {
-    RipupScoreboard scores;
-    Router1Cfg cfg(this);
-    cfg.useEstimate = useEstimate;
-
-    Router router(this, cfg, scores, src_wire, dst_wire);
-
-    if (!router.routedOkay)
-        return false;
-
-    if (delay != nullptr)
-        *delay = router.visited.at(dst_wire).delay;
-
-    if (route != nullptr) {
-        WireId cursor = dst_wire;
-        while (1) {
-            PipId pip = router.visited.at(cursor).pip;
-            (*route)[cursor] = pip;
-            if (pip == PipId())
-                break;
-            cursor = getPipSrcWire(pip);
-        }
-    }
-
-    return true;
+    // FIXME
+    return false;
 }
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/router1.h b/common/router1.h
index a184cbe7..80d7aa96 100644
--- a/common/router1.h
+++ b/common/router1.h
@@ -33,6 +33,10 @@ struct Router1Cfg : Settings
     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);
diff --git a/docs/archapi.md b/docs/archapi.md
index fd3bfb3a..3c938865 100644
--- a/docs/archapi.md
+++ b/docs/archapi.md
@@ -30,15 +30,15 @@ delay_t maxDelay() const { return delay; }
 
 ### BelId
 
-A type representing a bel name. `BelId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash<BelId>`.
+A type representing a bel name. `BelId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash<BelId>`.
 
 ### WireId
 
-A type representing a wire name. `WireId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash<WireId>`.
+A type representing a wire name. `WireId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash<WireId>`.
 
 ### PipId
 
-A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash<PipId>`.
+A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash<PipId>`.
 
 ### GroupId
 
@@ -215,14 +215,15 @@ Return true if the wire is available, i.e. can be bound to a net.
 
 Return the net a wire is bound to.
 
-### NetInfo \*getConflictingWireNet(WireId wire) const
+### WireId getConflictingWireWire(WireId wire) const
 
-If this returns a non-nullptr, then unbinding that net
+If this returns a non-WireId(), then unbinding that wire
 will make the given wire available.
 
-This returns nullptr if the wire is already available,
-or if there is no single net that can be unbound to make this
-wire available.
+### NetInfo \*getConflictingWireNet(WireId wire) const
+
+If this returns a non-nullptr, then unbinding that entire net
+will make the given wire available.
 
 ### DelayInfo getWireDelay(WireId wire) const
 
@@ -282,18 +283,23 @@ This method must also update `NetInfo::wires`.
 
 Returns true if the given pip is available to be bound to a net.
 
+Users must also check if the pip destination wire is available
+with `checkWireAvail(getPipDstWire(pip))` before binding the
+pip to a net.
+
 ### NetInfo \*getBoundPipNet(PipId pip) const
 
 Return the net this pip is bound to.
 
-### NetInfo \*getConflictingPipNet(PipId pip) const
+### WireId getConflictingPipWire(PipId pip) const
 
-Return the net that needs to be unbound in order to make this
-pip available.
+If this returns a non-WireId(), then unbinding that wire
+will make the given pip available.
+
+### NetInfo \*getConflictingPipNet(PipId pip) const
 
-This does not need to (but may) return the conflicting wire if the conflict is
-limited to the conflicting wire being bound to the destination wire for this
-pip.
+If this returns a non-nullptr, then unbinding that entire net
+will make the given pip available.
 
 ### const\_range\<PipId\> getPips() const
 
diff --git a/docs/faq.md b/docs/faq.md
index d440bba6..7b358187 100644
--- a/docs/faq.md
+++ b/docs/faq.md
@@ -38,7 +38,94 @@ For nextpnr we are using the following terminology.
 Adding new architectures to nextpnr
 -----------------------------------
 
-TBD
+### Implementing new architectures
+
+Each nextpnr architecture must implement the *nextpnr architecture API*.
+See [archapi.md](archapi.md) for a complete reference of the architecture API.
+
+### Delay Estimates
+
+Each architecture must implement a `estimateDelay()` method that estimates the expected delay for a path from given `src` to `dst` wires.
+*It is very important that this method slightly overestimates the expected delay.* Furthermore, it should overestimate the expected delay
+by a slightly larger margin for longer paths than for shorter paths. Otherwise there will be performance issues with the router.
+
+The delays estimates returned by that method should also be as fine-grain as possible. It definitely pays off to spend some time improving the `estimateDelay()`
+for your architecture once implementing small designs work.
+
+### Ripup Information
+
+The `getConflictingWireWire()`, `getConflictingWireNet()`, `getConflictingPipWire()`, and `getConflictingPipNet()` methods are used by the router
+to determine which resources to rip up in order to make a given routing resource (wire or pip) available.
+
+The architecture must guanrantee that the following invariants hold.
+
+**Invariant 1:**
+
+```
+    if (!ctx->checkWireAvail(wire)) {
+        WireId w = getConflictingWireWire(wire);
+        if (w != WireId()) {
+            ctx->unbindWire(w);
+            assert(ctx->checkWireAvail(wire));
+        }
+    }
+```
+
+**Invariant 2:**
+
+```
+    if (!ctx->checkWireAvail(wire)) {
+        NetInfo *n = getConflictingWireNet(wire);
+        if (n != nullptr) {
+            for (auto &it : n->wires)
+                ctx->unbindWire(it.first);
+            assert(ctx->checkWireAvail(wire));
+        }
+    }
+```
+
+**Invariant 3:**
+
+```
+    if (!ctx->checkPipAvail(pip)) {
+        WireId w = getConflictingPipWire(pip);
+        if (w != WireId()) {
+            ctx->unbindWire(w);
+            assert(ctx->checkPipAvail(pip));
+        }
+    }
+```
+
+**Invariant 4:**
+
+```
+    if (!ctx->checkPipAvail(pip)) {
+        NetInfo *n = getConflictingPipNet(pip);
+        if (n != nullptr) {
+            for (auto &it : n->wires)
+                ctx->unbindWire(it.first);
+            assert(ctx->checkPipAvail(pip));
+        }
+    }
+```
+
+**Invariant 5:**
+
+```
+    if (ctx->checkWireAvail(wire)) {
+        // bind is guaranteed to succeed
+        ctx->bindWire(wire, net, strength);
+    }
+```
+
+**Invariant 6:**
+
+```
+    if (ctx->checkPipAvail(pip) && ctx->checkWireAvail(ctx->getPipDstWire(pip))) {
+        // bind is guaranteed to succeed
+        ctx->bindPip(pip, net, strength);
+    }
+```
 
 Nextpnr and other tools
 -----------------------
diff --git a/ecp5/arch.cc b/ecp5/arch.cc
index e035c0f4..fe6a9545 100644
--- a/ecp5/arch.cc
+++ b/ecp5/arch.cc
@@ -400,7 +400,7 @@ BelId Arch::getBelByLocation(Loc loc) const
 
 delay_t Arch::estimateDelay(WireId src, WireId dst) const
 {
-    return 100 * (abs(src.location.x - dst.location.x) + abs(src.location.y - dst.location.y));
+    return 170 * (abs(src.location.x - dst.location.x) + abs(src.location.y - dst.location.y));
 }
 
 delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const
@@ -409,7 +409,7 @@ delay_t Arch::predictDelay(const NetInfo *net_info, const PortRef &sink) const
     auto driver_loc = getBelLocation(driver.cell->bel);
     auto sink_loc = getBelLocation(sink.cell->bel);
 
-    return 100 * (abs(driver_loc.x - sink_loc.x) + abs(driver_loc.y - sink_loc.y));
+    return 170 * (abs(driver_loc.x - sink_loc.x) + abs(driver_loc.y - sink_loc.y));
 }
 
 bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay_t &budget) const { return false; }
diff --git a/ecp5/arch.h b/ecp5/arch.h
index 07b1e65d..aa3c5348 100644
--- a/ecp5/arch.h
+++ b/ecp5/arch.h
@@ -619,6 +619,8 @@ struct Arch : BaseCtx
             return wire_to_net.at(wire);
     }
 
+    WireId getConflictingWireWire(WireId wire) const { return wire; }
+
     NetInfo *getConflictingWireNet(WireId wire) const
     {
         NPNR_ASSERT(wire != WireId());
@@ -724,6 +726,8 @@ struct Arch : BaseCtx
             return pip_to_net.at(pip);
     }
 
+    WireId getConflictingPipWire(PipId pip) const { return WireId(); }
+
     NetInfo *getConflictingPipNet(PipId pip) const
     {
         NPNR_ASSERT(pip != PipId());
diff --git a/ecp5/archdefs.h b/ecp5/archdefs.h
index b85852c2..01cbad46 100644
--- a/ecp5/archdefs.h
+++ b/ecp5/archdefs.h
@@ -75,6 +75,7 @@ struct Location
 
     bool operator==(const Location &other) const { return x == other.x && y == other.y; }
     bool operator!=(const Location &other) const { return x != other.x || y != other.y; }
+    bool operator<(const Location &other) const { return y == other.y ? x < other.x : y < other.y; }
 };
 
 inline Location operator+(const Location &a, const Location &b) { return Location(a.x + b.x, a.y + b.y); }
@@ -86,6 +87,7 @@ struct BelId
 
     bool operator==(const BelId &other) const { return index == other.index && location == other.location; }
     bool operator!=(const BelId &other) const { return index != other.index || location != other.location; }
+    bool operator<(const BelId &other) const { return location == other.location ? index < other.index : location < other.location; }
 };
 
 struct WireId
@@ -95,6 +97,7 @@ struct WireId
 
     bool operator==(const WireId &other) const { return index == other.index && location == other.location; }
     bool operator!=(const WireId &other) const { return index != other.index || location != other.location; }
+    bool operator<(const WireId &other) const { return location == other.location ? index < other.index : location < other.location; }
 };
 
 struct PipId
@@ -104,6 +107,7 @@ struct PipId
 
     bool operator==(const PipId &other) const { return index == other.index && location == other.location; }
     bool operator!=(const PipId &other) const { return index != other.index || location != other.location; }
+    bool operator<(const PipId &other) const { return location == other.location ? index < other.index : location < other.location; }
 };
 
 struct GroupId
diff --git a/ecp5/main.cc b/ecp5/main.cc
index c444f96f..cc004df3 100644
--- a/ecp5/main.cc
+++ b/ecp5/main.cc
@@ -40,7 +40,7 @@ class ECP5CommandHandler : public CommandHandler
     void customBitstream(Context *ctx) override;
 
   protected:
-    po::options_description getArchOptions();
+    po::options_description getArchOptions() override;
 };
 
 ECP5CommandHandler::ECP5CommandHandler(int argc, char **argv) : CommandHandler(argc, argv) {}
diff --git a/generic/arch.cc b/generic/arch.cc
index 4439f517..77417d27 100644
--- a/generic/arch.cc
+++ b/generic/arch.cc
@@ -373,6 +373,8 @@ NetInfo *Arch::getBoundPipNet(PipId pip) const { return pips.at(pip).bound_net;
 
 NetInfo *Arch::getConflictingPipNet(PipId pip) const { return pips.at(pip).bound_net; }
 
+WireId Arch::getConflictingPipWire(PipId pip) const { return pips.at(pip).bound_net ? pips.at(pip).dstWire : WireId(); }
+
 const std::vector<PipId> &Arch::getPips() const { return pip_ids; }
 
 Loc Arch::getPipLocation(PipId pip) const { return pips.at(pip).loc; }
diff --git a/generic/arch.h b/generic/arch.h
index 1eca9701..dc4258cc 100644
--- a/generic/arch.h
+++ b/generic/arch.h
@@ -172,6 +172,7 @@ struct Arch : BaseCtx
     void unbindWire(WireId wire);
     bool checkWireAvail(WireId wire) const;
     NetInfo *getBoundWireNet(WireId wire) const;
+    WireId getConflictingWireWire(WireId wire) const { return wire; }
     NetInfo *getConflictingWireNet(WireId wire) const;
     DelayInfo getWireDelay(WireId wire) const { return DelayInfo(); }
     const std::vector<WireId> &getWires() const;
@@ -186,6 +187,7 @@ struct Arch : BaseCtx
     void unbindPip(PipId pip);
     bool checkPipAvail(PipId pip) const;
     NetInfo *getBoundPipNet(PipId pip) const;
+    WireId getConflictingPipWire(PipId pip) const;
     NetInfo *getConflictingPipNet(PipId pip) const;
     const std::vector<PipId> &getPips() const;
     Loc getPipLocation(PipId pip) const;
diff --git a/generic/main.cc b/generic/main.cc
index 412a28ac..08b0b348 100644
--- a/generic/main.cc
+++ b/generic/main.cc
@@ -37,7 +37,7 @@ class GenericCommandHandler : public CommandHandler
     void customBitstream(Context *ctx) override;
 
   protected:
-    po::options_description getArchOptions();
+    po::options_description getArchOptions() override;
 };
 
 GenericCommandHandler::GenericCommandHandler(int argc, char **argv) : CommandHandler(argc, argv) {}
diff --git a/gui/designwidget.cc b/gui/designwidget.cc
index 20a81a7d..9895cad1 100644
--- a/gui/designwidget.cc
+++ b/gui/designwidget.cc
@@ -638,6 +638,8 @@ void DesignWidget::onSelectionChanged(int num, const QItemSelection &, const QIt
         addProperty(topItem, QVariant::String, "Type", ctx->getWireType(wire).c_str(ctx));

         addProperty(topItem, QVariant::Bool, "Available", ctx->checkWireAvail(wire));

         addProperty(topItem, QVariant::String, "Bound Net", ctx->nameOf(ctx->getBoundWireNet(wire)), ElementType::NET);

+        addProperty(topItem, QVariant::String, "Conflicting Wire",

+                    ctx->getWireName(ctx->getConflictingWireWire(wire)).c_str(ctx), ElementType::WIRE);

         addProperty(topItem, QVariant::String, "Conflicting Net", ctx->nameOf(ctx->getConflictingWireNet(wire)),

                     ElementType::NET);

 

@@ -698,6 +700,8 @@ void DesignWidget::onSelectionChanged(int num, const QItemSelection &, const QIt
         addProperty(topItem, QVariant::String, "Type", ctx->getPipType(pip).c_str(ctx));

         addProperty(topItem, QVariant::Bool, "Available", ctx->checkPipAvail(pip));

         addProperty(topItem, QVariant::String, "Bound Net", ctx->nameOf(ctx->getBoundPipNet(pip)), ElementType::NET);

+        addProperty(topItem, QVariant::String, "Conflicting Wire",

+                    ctx->getWireName(ctx->getConflictingPipWire(pip)).c_str(ctx), ElementType::WIRE);

         addProperty(topItem, QVariant::String, "Conflicting Net", ctx->nameOf(ctx->getConflictingPipNet(pip)),

                     ElementType::NET);

         addProperty(topItem, QVariant::String, "Src Wire", ctx->getWireName(ctx->getPipSrcWire(pip)).c_str(ctx),

diff --git a/ice40/arch.h b/ice40/arch.h
index 80fcf761..e9ec8130 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -404,7 +404,7 @@ struct Arch : BaseCtx
     std::vector<CellInfo *> bel_to_cell;
     std::vector<NetInfo *> wire_to_net;
     std::vector<NetInfo *> pip_to_net;
-    std::vector<NetInfo *> switches_locked;
+    std::vector<WireId> switches_locked;
 
     ArchArgs args;
     Arch(ArchArgs args);
@@ -546,7 +546,7 @@ struct Arch : BaseCtx
         auto pip = it->second.pip;
         if (pip != PipId()) {
             pip_to_net[pip.index] = nullptr;
-            switches_locked[chip_info->pip_data[pip.index].switch_index] = nullptr;
+            switches_locked[chip_info->pip_data[pip.index].switch_index] = WireId();
         }
 
         net_wires.erase(it);
@@ -566,6 +566,8 @@ struct Arch : BaseCtx
         return wire_to_net[wire.index];
     }
 
+    WireId getConflictingWireWire(WireId wire) const { return wire; }
+
     NetInfo *getConflictingWireNet(WireId wire) const
     {
         NPNR_ASSERT(wire != WireId());
@@ -608,14 +610,15 @@ struct Arch : BaseCtx
     {
         NPNR_ASSERT(pip != PipId());
         NPNR_ASSERT(pip_to_net[pip.index] == nullptr);
-        NPNR_ASSERT(switches_locked[chip_info->pip_data[pip.index].switch_index] == nullptr);
-
-        pip_to_net[pip.index] = net;
-        switches_locked[chip_info->pip_data[pip.index].switch_index] = net;
+        NPNR_ASSERT(switches_locked[chip_info->pip_data[pip.index].switch_index] == WireId());
 
         WireId dst;
         dst.index = chip_info->pip_data[pip.index].dst;
         NPNR_ASSERT(wire_to_net[dst.index] == nullptr);
+
+        pip_to_net[pip.index] = net;
+        switches_locked[chip_info->pip_data[pip.index].switch_index] = dst;
+
         wire_to_net[dst.index] = net;
         net->wires[dst].pip = pip;
         net->wires[dst].strength = strength;
@@ -627,7 +630,7 @@ struct Arch : BaseCtx
     {
         NPNR_ASSERT(pip != PipId());
         NPNR_ASSERT(pip_to_net[pip.index] != nullptr);
-        NPNR_ASSERT(switches_locked[chip_info->pip_data[pip.index].switch_index] != nullptr);
+        NPNR_ASSERT(switches_locked[chip_info->pip_data[pip.index].switch_index] != WireId());
 
         WireId dst;
         dst.index = chip_info->pip_data[pip.index].dst;
@@ -636,33 +639,39 @@ struct Arch : BaseCtx
         pip_to_net[pip.index]->wires.erase(dst);
 
         pip_to_net[pip.index] = nullptr;
-        switches_locked[chip_info->pip_data[pip.index].switch_index] = nullptr;
+        switches_locked[chip_info->pip_data[pip.index].switch_index] = WireId();
         refreshUiPip(pip);
         refreshUiWire(dst);
     }
 
-    bool checkPipAvail(PipId pip) const
+    bool ice40_pip_hard_unavail(PipId pip) const
     {
         NPNR_ASSERT(pip != PipId());
         auto &pi = chip_info->pip_data[pip.index];
         auto &si = chip_info->bits_info->switches[pi.switch_index];
 
-        if (switches_locked[pi.switch_index] != nullptr)
-            return false;
-
         if (pi.flags & PipInfoPOD::FLAG_ROUTETHRU) {
             NPNR_ASSERT(si.bel >= 0);
             if (bel_to_cell[si.bel] != nullptr)
-                return false;
+                return true;
         }
 
         if (pi.flags & PipInfoPOD::FLAG_NOCARRY) {
             NPNR_ASSERT(si.bel >= 0);
             if (bel_carry[si.bel])
-                return false;
+                return true;
         }
 
-        return true;
+        return false;
+    }
+
+    bool checkPipAvail(PipId pip) const
+    {
+        if (ice40_pip_hard_unavail(pip))
+            return false;
+
+        auto &pi = chip_info->pip_data[pip.index];
+        return switches_locked[pi.switch_index] == WireId();
     }
 
     NetInfo *getBoundPipNet(PipId pip) const
@@ -671,12 +680,23 @@ struct Arch : BaseCtx
         return pip_to_net[pip.index];
     }
 
-    NetInfo *getConflictingPipNet(PipId pip) const
+    WireId getConflictingPipWire(PipId pip) const
     {
-        NPNR_ASSERT(pip != PipId());
+        if (ice40_pip_hard_unavail(pip))
+            return WireId();
+
         return switches_locked[chip_info->pip_data[pip.index].switch_index];
     }
 
+    NetInfo *getConflictingPipNet(PipId pip) const
+    {
+        if (ice40_pip_hard_unavail(pip))
+            return nullptr;
+
+        WireId wire = switches_locked[chip_info->pip_data[pip.index].switch_index];
+        return wire == WireId() ? nullptr : wire_to_net[wire.index];
+    }
+
     AllPipRange getPips() const
     {
         AllPipRange range;
diff --git a/ice40/archdefs.h b/ice40/archdefs.h
index c04033e7..b9614c07 100644
--- a/ice40/archdefs.h
+++ b/ice40/archdefs.h
@@ -66,6 +66,7 @@ struct BelId
 
     bool operator==(const BelId &other) const { return index == other.index; }
     bool operator!=(const BelId &other) const { return index != other.index; }
+    bool operator<(const BelId &other) const { return index < other.index; }
 };
 
 struct WireId
@@ -74,6 +75,7 @@ struct WireId
 
     bool operator==(const WireId &other) const { return index == other.index; }
     bool operator!=(const WireId &other) const { return index != other.index; }
+    bool operator<(const WireId &other) const { return index < other.index; }
 };
 
 struct PipId
@@ -82,6 +84,7 @@ struct PipId
 
     bool operator==(const PipId &other) const { return index == other.index; }
     bool operator!=(const PipId &other) const { return index != other.index; }
+    bool operator<(const PipId &other) const { return index < other.index; }
 };
 
 struct GroupId
diff --git a/ice40/main.cc b/ice40/main.cc
index 8bab360d..fcc56d04 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -43,7 +43,7 @@ class Ice40CommandHandler : public CommandHandler
     void customBitstream(Context *ctx) override;
 
   protected:
-    po::options_description getArchOptions();
+    po::options_description getArchOptions() override;
 };
 
 Ice40CommandHandler::Ice40CommandHandler(int argc, char **argv) : CommandHandler(argc, argv) {}