From f4fed62c05a9595e22a8ec54add5531225911741 Mon Sep 17 00:00:00 2001 From: gatecat Date: Wed, 2 Jun 2021 09:28:53 +0100 Subject: Use hashlib in routers Signed-off-by: gatecat --- common/context.h | 2 +- common/router1.cc | 63 ++++++++++++++++++++++++++----------------------------- common/router2.cc | 11 +++++----- ice40/delay.cc | 2 +- 4 files changed, 37 insertions(+), 41 deletions(-) diff --git a/common/context.h b/common/context.h index a5553422..102dc221 100644 --- a/common/context.h +++ b/common/context.h @@ -50,7 +50,7 @@ struct Context : Arch, DeterministicRNG // 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); + dict *route = nullptr, bool useEstimate = true); // -------------------------------------------------------------- // call after changing hierpath or adding/removing nets and cells diff --git a/common/router1.cc b/common/router1.cc index 11107a40..374f7455 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -49,16 +49,13 @@ struct arc_key : net_info->name < other.net_info->name; } - struct Hash + unsigned int hash() const { - std::size_t operator()(const arc_key &arg) const noexcept - { - std::size_t seed = std::hash()(arg.net_info); - seed ^= std::hash()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); - seed ^= std::hash()(arg.phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); - return seed; - } - }; + std::size_t seed = std::hash()(net_info); + seed ^= std::hash()(user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + seed ^= std::hash()(phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } }; struct arc_entry @@ -107,15 +104,15 @@ struct Router1 const Router1Cfg &cfg; std::priority_queue, arc_entry::Less> arc_queue; - std::unordered_map> wire_to_arcs; - std::unordered_map, arc_key::Hash> arc_to_wires; - std::unordered_set queued_arcs; + dict> wire_to_arcs; + dict> arc_to_wires; + pool queued_arcs; - std::unordered_map visited; + dict visited; std::priority_queue, QueuedWire::Greater> queue; - std::unordered_map wireScores; - std::unordered_map netScores; + dict wireScores; + dict netScores; int arcs_with_ripup = 0; int arcs_without_ripup = 0; @@ -295,11 +292,11 @@ struct Router1 void check() { - std::unordered_set valid_arcs; + pool valid_arcs; for (auto &net_it : ctx->nets) { NetInfo *net_info = net_it.second.get(); - std::unordered_set valid_wires_for_net; + pool valid_wires_for_net; if (skip_net(net_info)) continue; @@ -357,8 +354,8 @@ struct Router1 void setup() { - std::unordered_map src_to_net; - std::unordered_map dst_to_arc; + dict src_to_net; + dict dst_to_arc; std::vector net_names; for (auto &net_it : ctx->nets) @@ -472,7 +469,7 @@ struct Router1 // unbind wires that are currently used exclusively by this arc - std::unordered_set old_arc_wires; + pool old_arc_wires; old_arc_wires.swap(arc_to_wires[arc]); for (WireId wire : old_arc_wires) { @@ -720,7 +717,7 @@ struct Router1 // bind resulting route (and maybe unroute other nets) - std::unordered_set unassign_wires = arc_to_wires[arc]; + pool unassign_wires = arc_to_wires[arc]; WireId cursor = dst_wire; delay_t accumulated_path_delay = 0; @@ -919,10 +916,10 @@ bool Context::checkRoutedDesign() const struct ExtraWireInfo { int order_num = 0; - std::unordered_set children; + pool children; }; - std::unordered_map db; + dict> db; for (auto &it : net_info->wires) { WireId w = it.first; @@ -930,7 +927,7 @@ bool Context::checkRoutedDesign() const if (p != PipId()) { log_assert(ctx->getPipDstWire(p) == w); - db[ctx->getPipSrcWire(p)].children.insert(w); + db.emplace(ctx->getPipSrcWire(p), std::make_unique()).first->second->children.insert(w); } } @@ -948,7 +945,7 @@ bool Context::checkRoutedDesign() const found_unrouted = true; } - std::unordered_map dest_wires; + dict dest_wires; for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) { for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, net_info->users[user_idx])) { log_assert(dst_wire != WireId()); @@ -963,10 +960,10 @@ bool Context::checkRoutedDesign() const } std::function setOrderNum; - std::unordered_set logged_wires; + pool logged_wires; setOrderNum = [&](WireId w, int num) { - auto &db_entry = db[w]; + auto &db_entry = *db.emplace(w, std::make_unique()).first->second; if (db_entry.order_num != 0) { found_loop = true; log(" %*s=> loop\n", 2 * num, ""); @@ -998,10 +995,10 @@ bool Context::checkRoutedDesign() const } setOrderNum(src_wire, 1); - std::unordered_set dangling_wires; + pool dangling_wires; for (auto &it : db) { - auto &db_entry = it.second; + auto &db_entry = *it.second; if (db_entry.order_num == 0) dangling_wires.insert(it.first); } @@ -1010,10 +1007,10 @@ bool Context::checkRoutedDesign() const if (dangling_wires.empty()) { log(" no dangling wires.\n"); } else { - std::unordered_set root_wires = dangling_wires; + pool root_wires = dangling_wires; for (WireId w : dangling_wires) { - for (WireId c : db[w].children) + for (WireId c : db[w]->children) root_wires.erase(c); } @@ -1064,8 +1061,8 @@ bool Context::checkRoutedDesign() const return true; } -bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, - std::unordered_map *route, bool useEstimate) +bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay, dict *route, + bool useEstimate) { // FIXME return false; diff --git a/common/router2.cc b/common/router2.cc index b0f53ce1..e1d3e75b 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -35,7 +35,6 @@ #include #include -#include "hash_table.h" #include "log.h" #include "nextpnr.h" #include "router1.h" @@ -198,7 +197,7 @@ struct Router2 } } - HashTables::HashMap wire_to_idx; + dict wire_to_idx; std::vector flat_wires; PerWireData &wire_data(WireId w) { return flat_wires[wire_to_idx.at(w)]; } @@ -284,7 +283,7 @@ struct Router2 std::priority_queue, QueuedWire::Greater> queue; // Special case where one net has multiple logical arcs to the same physical sink - std::unordered_set processed_sinks; + pool processed_sinks; // Backwards routing std::queue backwards_queue; @@ -465,7 +464,7 @@ struct Router2 bool did_something = false; WireId src = ctx->getNetinfoSourceWire(net); for (auto sink : ctx->getNetinfoSinkWires(net, net->users.at(i))) { - std::unordered_set rsv; + pool rsv; WireId cursor = sink; bool done = false; if (ctx->debug) @@ -1083,7 +1082,7 @@ struct Router2 void write_wiretype_heatmap(std::ostream &out) { - std::unordered_map> cong_by_type; + dict> cong_by_type; size_t max_cong = 0; // Build histogram for (auto &wd : flat_wires) { @@ -1099,7 +1098,7 @@ struct Router2 for (size_t i = 0; i <= max_cong; i++) out << "bound=" << i << ","; out << std::endl; - for (auto &ty : sorted_ref(cong_by_type)) { + for (auto &ty : cong_by_type) { out << ctx->nameOf(ty.first) << ","; for (int count : ty.second) out << count << ","; diff --git a/ice40/delay.cc b/ice40/delay.cc index a3469876..0bcab160 100644 --- a/ice40/delay.cc +++ b/ice40/delay.cc @@ -62,7 +62,7 @@ void ice40DelayFuzzerMain(Context *ctx) WireId src = srcWires[index]; WireId dst = dstWires[index++]; - std::unordered_map route; + dict route; #if NUM_FUZZ_ROUTES <= 1000 if (!ctx->getActualRouteDelay(src, dst, nullptr, &route, false)) -- cgit v1.2.3