From 6b94102e5ad32d82f826b8335c2cba7d580d95b1 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 10 Nov 2018 21:14:50 +0100 Subject: Add checkers and assertions to router1 and other improvements Signed-off-by: Clifford Wolf --- common/nextpnr.h | 3 +- common/router1.cc | 319 +++++++++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 280 insertions(+), 42 deletions(-) diff --git a/common/nextpnr.h b/common/nextpnr.h index 59ae0323..5a0bd4b1 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -269,7 +269,7 @@ struct PipMap struct NetInfo : ArchNetInfo { IdString name; - int32_t udata; + int32_t udata = 0; PortRef driver; std::vector users; @@ -541,6 +541,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 *route = nullptr, bool useEstimate = true); diff --git a/common/router1.cc b/common/router1.cc index 7fed2729..958edf7d 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -91,7 +91,8 @@ struct Router1 const Router1Cfg &cfg; std::priority_queue, arc_entry::Greater> arc_queue; - std::unordered_map> wire_to_arc; + std::unordered_map> wire_to_arcs; + std::unordered_map, arc_key::Hash> arc_to_wires; std::unordered_set queued_arcs; std::unordered_map visited; @@ -143,30 +144,32 @@ struct Router1 void ripup_net(NetInfo *net) { if (ctx->debug) - log(" ripup net %s\n", net->name.c_str(ctx)); + log(" ripup net %s\n", net->name.c_str(ctx)); auto net_wires_copy = net->wires; for (auto &it : net_wires_copy) { if (it.second.pip == PipId()) - ripup_wire(it.first); + ripup_wire(it.first, true); else - ripup_pip(it.second.pip); + ripup_pip(it.second.pip, true); } ripup_flag = true; } - void ripup_wire(WireId wire) + void ripup_wire(WireId wire, bool extra_indent = false) { if (ctx->debug) - log(" ripup wire %s\n", ctx->getWireName(wire).c_str(ctx)); + log(" %sripup wire %s\n", extra_indent ? " " : "", ctx->getWireName(wire).c_str(ctx)); wireScores[wire]++; if (ctx->getBoundWireNet(wire)) { - for (auto &it : wire_to_arc[wire]) + for (auto &it : wire_to_arcs[wire]) { + arc_to_wires[it].erase(wire); arc_queue_insert(it); - wire_to_arc[wire].clear(); + } + wire_to_arcs[wire].clear(); ctx->unbindWire(wire); } @@ -179,20 +182,33 @@ struct Router1 ripup_flag = true; } - void ripup_pip(PipId pip) + void ripup_pip(PipId pip, bool extra_indent = false) { + WireId wire = ctx->getPipDstWire(pip); + if (ctx->debug) - log(" ripup pip %s\n", ctx->getPipName(pip).c_str(ctx)); + log(" %sripup pip %s (%s)\n", extra_indent ? " " : "", ctx->getPipName(pip).c_str(ctx), ctx->getWireName(wire).c_str(ctx)); - WireId wire = ctx->getPipDstWire(pip); wireScores[wire]++; pipScores[pip]++; if (ctx->getBoundPipNet(pip)) { - for (auto &it : wire_to_arc[wire]) - arc_queue_insert(it); - wire_to_arc[wire].clear(); ctx->unbindPip(pip); + goto remove_wire_arcs; + } + + if (ctx->getBoundWireNet(wire)) { + ctx->unbindWire(wire); + goto remove_wire_arcs; + } + + if (0) { +remove_wire_arcs: + for (auto &it : wire_to_arcs[wire]) { + arc_to_wires[it].erase(wire); + arc_queue_insert(it); + } + wire_to_arcs[wire].clear(); } NetInfo *net = ctx->getConflictingPipNet(pip); @@ -205,19 +221,75 @@ struct Router1 ripup_flag = true; } - void setup() + bool skip_net(NetInfo *net_info) + { +#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; + + return false; + } + + void check() { + std::unordered_set valid_arcs; + for (auto &net_it : ctx->nets) { NetInfo *net_info = net_it.second.get(); + std::unordered_set valid_wires_for_net; -#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) + if (skip_net(net_info)) continue; -#endif - if (net_info->driver.cell == nullptr) + + 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()); + + arc_key arc; + arc.net_info = net_info; + arc.user_idx = user_idx; + + valid_arcs.insert(arc); + + for (WireId wire : arc_to_wires[arc]) { + valid_wires_for_net.insert(wire); + log_assert(wire_to_arcs[wire].count(arc)); + log_assert(net_info->wires.count(wire)); + } + } + + for (auto &it : net_info->wires) { + WireId w = it.first; + log_assert(valid_wires_for_net.count(w)); + } + } + + for (auto &it : wire_to_arcs) { + for (auto &arc : it.second) + log_assert(valid_arcs.count(arc)); + } + + for (auto &it : arc_to_wires) { + log_assert(valid_arcs.count(it.first)); + } + } + + void setup() + { + for (auto &net_it : ctx->nets) + { + NetInfo *net_info = net_it.second.get(); + + if (skip_net(net_info)) continue; auto src_wire = ctx->getNetinfoSourceWire(net_info); @@ -237,8 +309,14 @@ struct Router1 arc.net_info = net_info; arc.user_idx = user_idx; + if (net_info->wires.count(src_wire) == 0) { + arc_queue_insert(arc, src_wire, dst_wire); + continue; + } + WireId cursor = dst_wire; - wire_to_arc[cursor].insert(arc); + wire_to_arcs[cursor].insert(arc); + arc_to_wires[arc].insert(cursor); while (src_wire != cursor) { auto it = net_info->wires.find(cursor); @@ -249,14 +327,15 @@ struct Router1 NPNR_ASSERT(it->second.pip != PipId()); cursor = ctx->getPipSrcWire(it->second.pip); - wire_to_arc[cursor].insert(arc); + wire_to_arcs[cursor].insert(arc); + arc_to_wires[arc].insert(cursor); } } std::vector unbind_wires; for (auto &it : net_info->wires) - if (it.second.strength < STRENGTH_LOCKED && wire_to_arc.count(it.first) == 0) + if (it.second.strength < STRENGTH_LOCKED && wire_to_arcs.count(it.first) == 0) unbind_wires.push_back(it.first); for (auto it : unbind_wires) @@ -282,21 +361,20 @@ struct Router1 // unbind wires that are currently used exclusively by this arc - std::vector unbind_wires; - - for (auto &wire_it : net_info->wires) { - auto wire = wire_it.first; - auto wire_to_arc_it = wire_to_arc.find(wire); - NPNR_ASSERT(wire_to_arc_it != wire_to_arc.end()); + std::unordered_set old_arc_wires; + old_arc_wires.swap(arc_to_wires[arc]); - wire_to_arc_it->second.erase(arc); - if (wire_to_arc_it->second.empty()) - unbind_wires.push_back(wire); + 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->getWireName(wire).c_str(ctx)); + ctx->unbindWire(wire); + } } - for (auto it : unbind_wires) - ctx->unbindWire(it); - // reset wire queue if (!queue.empty()) { @@ -305,6 +383,8 @@ struct Router1 } visited.clear(); + // A* main loop + int visitCnt = 0; int maxVisitCnt = INT_MAX; delay_t best_est = 0; @@ -454,6 +534,10 @@ struct Router1 return false; } + // bind resulting route (and maybe unroute other nets) + + std::unordered_set unassign_wires = arc_to_wires[arc]; + WireId cursor = dst_wire; while (1) { if (ctx->debug) @@ -463,8 +547,10 @@ struct Router1 NetInfo *ripupWireNet = ctx->getConflictingWireNet(cursor); NPNR_ASSERT(ripupWireNet != nullptr); - if (ripupWireNet != net_info) + if (ripupWireNet != net_info) { ripup_wire(cursor); + NPNR_ASSERT(ctx->checkWireAvail(cursor)); + } } auto pip = visited[cursor].pip; @@ -476,19 +562,25 @@ struct Router1 NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip); NPNR_ASSERT(ripupPipNet != nullptr); - if (ripupPipNet != net_info) + if (ripupPipNet != net_info || net_info->wires.at(cursor).pip != pip) ripup_pip(pip); } } if (ctx->checkWireAvail(cursor)) { - if (pip == PipId()) + if (pip == PipId()) { + if (ctx->debug) + log(" bind %s\n", ctx->getWireName(cursor).c_str(ctx)); ctx->bindWire(cursor, net_info, STRENGTH_WEAK); - else if (ctx->checkPipAvail(pip)) + } else if (ctx->checkPipAvail(pip)) { + if (ctx->debug) + log(" bind %s\n", ctx->getPipName(pip).c_str(ctx)); ctx->bindPip(pip, net_info, STRENGTH_WEAK); + } } - wire_to_arc[cursor].insert(arc); + wire_to_arcs[cursor].insert(arc); + arc_to_wires[arc].insert(cursor); if (pip == PipId()) break; @@ -536,6 +628,9 @@ bool router1(Context *ctx, const Router1Cfg &cfg) Router1 router(ctx, cfg); router.setup(); +#ifndef NDEBUG + router.check(); +#endif log_info("Routing %d arcs.\n", int(router.arc_queue.size())); @@ -554,6 +649,7 @@ bool router1(Context *ctx, const Router1Cfg &cfg) 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; + router.check(); } arc_key arc = router.arc_queue_pop(); @@ -573,8 +669,12 @@ bool router1(Context *ctx, const Router1Cfg &cfg) 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())); +#ifndef NDEBUG + router.check(); +#endif log_info("Routing complete.\n"); + ctx->checkRoutedDesign(); log_info("Checksum: 0x%08x\n", ctx->checksum()); #ifndef NDEBUG @@ -592,6 +692,143 @@ bool router1(Context *ctx, const Router1Cfg &cfg) } } +bool Context::checkRoutedDesign() const +{ + const Context *ctx = getCtx(); + + for (auto &net_it : ctx->nets) { + NetInfo *net_info = net_it.second.get(); + + if (ctx->debug) + log("checking net %s\n", net_info->name.c_str(ctx)); + + if (net_info->users.empty()) { + if (ctx->debug) + log(" net without sinks\n"); + log_assert(net_info->wires.empty()); + continue; + } + + bool found_unrouted = false; + bool found_loop = false; + bool found_stub = false; + + struct ExtraWireInfo { + int order_num = 0; + std::unordered_set children; + }; + + std::unordered_map db; + + for (auto &it : net_info->wires) { + WireId w = it.first; + PipId p = it.second.pip; + + if (p != PipId()) { + log_assert(ctx->getPipDstWire(p) == w); + db[ctx->getPipSrcWire(p)].children.insert(w); + } + } + + auto src_wire = ctx->getNetinfoSourceWire(net_info); + log_assert(src_wire != WireId()); + + if (net_info->wires.count(src_wire) == 0) { + if (ctx->debug) + log(" source (%s) not bound to net\n", ctx->getWireName(src_wire).c_str(ctx)); + found_unrouted = true; + } + + std::unordered_map 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 (net_info->wires.count(dst_wire) == 0) { + if (ctx->debug) + log(" sink %d (%s) not bound to net\n", user_idx, ctx->getWireName(dst_wire).c_str(ctx)); + found_unrouted = true; + } + } + + std::function setOrderNum; + std::unordered_set logged_wires; + + 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->getWireName(child).c_str(ctx)); + logged_wires.insert(child); + } + setOrderNum(child, num+1); + } + if (db_entry.children.empty()) { + if (dest_wires.count(w) != 0) { + log(" %*s=> sink %d\n", 2*num, "", dest_wires.at(w)); + } else { + log(" %*s=> stub\n", 2*num, ""); + found_stub = true; + } + } + }; + + if (ctx->debug) { + log(" driver: %s\n", ctx->getWireName(src_wire).c_str(ctx)); + logged_wires.insert(src_wire); + } + setOrderNum(src_wire, 1); + + std::unordered_set dangling_wires; + + for (auto &it : db) { + auto &db_entry = it.second; + if (db_entry.order_num == 0) + dangling_wires.insert(it.first); + } + + if (ctx->debug) { + if (dangling_wires.empty()) { + log(" no dangling wires.\n"); + } else { + std::unordered_set root_wires = dangling_wires; + + for (WireId w : dangling_wires) { + for (WireId c : db[w].children) + root_wires.erase(c); + } + + for (WireId w : root_wires) { + log(" dangling wire: %s\n", ctx->getWireName(w).c_str(ctx)); + logged_wires.insert(w); + setOrderNum(w, 1); + } + + for (WireId w : dangling_wires) { + if (logged_wires.count(w) == 0) + log(" loop: %s -> %s\n", + ctx->getWireName(ctx->getPipSrcWire(net_info->wires.at(w).pip)).c_str(ctx), + ctx->getWireName(w).c_str(ctx)); + } + } + } + + log_assert(!found_unrouted); + log_assert(!found_loop); + log_assert(!found_stub); + log_assert(dangling_wires.empty()); + } + + return true; +} + bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, std::unordered_map *route, bool useEstimate) { -- cgit v1.2.3