Use hashlib in placers

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

7 files changed, 43 insertions, 52 deletions

diff --git a/common/fast_bels.h b/common/fast_bels.h
index 0425f92a..b49c4c6c 100644
--- a/common/fast_bels.h
+++ b/common/fast_bels.h
@@ -178,10 +178,10 @@ struct FastBels
     const bool check_bel_available;
     const int minBelsForGridPick;
 
-    std::unordered_map<IdString, TypeData> cell_types;
+    dict<IdString, TypeData> cell_types;
     std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_cell_type;
 
-    std::unordered_map<BelBucketId, TypeData> partition_types;
+    dict<BelBucketId, TypeData> partition_types;
     std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_partition_type;
 };
 
diff --git a/common/nextpnr_base_types.h b/common/nextpnr_base_types.h
index 19786d6e..ba1af68c 100644
--- a/common/nextpnr_base_types.h
+++ b/common/nextpnr_base_types.h
@@ -90,6 +90,7 @@ struct Loc
 
     bool operator==(const Loc &other) const { return (x == other.x) && (y == other.y) && (z == other.z); }
     bool operator!=(const Loc &other) const { return (x != other.x) || (y != other.y) || (z != other.z); }
+    unsigned int hash() const { return mkhash(x, mkhash(y, z)); }
 };
 
 struct ArcBounds
diff --git a/common/place_common.cc b/common/place_common.cc
index ece47b5a..9a6c6158 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -178,8 +178,8 @@ class ConstraintLegaliseWorker
   private:
     Context *ctx;
     std::set<IdString> rippedCells;
-    std::unordered_map<IdString, Loc> oldLocations;
-    std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
+    dict<IdString, Loc> oldLocations;
+    dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
 
     class IncreasingDiameterSearch
     {
@@ -227,10 +227,10 @@ class ConstraintLegaliseWorker
         int sign = 0;
     };
 
-    typedef std::unordered_map<IdString, Loc> CellLocations;
+    typedef dict<IdString, Loc> CellLocations;
 
     // Check if a location would be suitable for a cell and all its constrained children
-    bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set<Loc> &usedLocations)
+    bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, pool<Loc> &usedLocations)
     {
         BelId locBel = ctx->getBelByLocation(loc);
         if (locBel == BelId())
@@ -324,7 +324,7 @@ class ConstraintLegaliseWorker
                 }
 
                 CellLocations solution;
-                std::unordered_set<Loc> used;
+                pool<Loc> used;
                 if (valid_loc_for(cell, rootLoc, solution, used)) {
                     for (auto cp : solution) {
                         // First unbind all cells
diff --git a/common/placer1.cc b/common/placer1.cc
index f9cef92f..e8c6aa64 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -87,7 +87,7 @@ class SAPlacer
         }
         diameter = std::max(max_x, max_y) + 1;
 
-        std::unordered_set<IdString> cell_types_in_use;
+        pool<IdString> cell_types_in_use;
         for (auto &cell : ctx->cells) {
             IdString cell_type = cell.second->type;
             cell_types_in_use.insert(cell_type);
@@ -629,7 +629,7 @@ class SAPlacer
     bool try_swap_chain(CellInfo *cell, BelId newBase)
     {
         std::vector<std::pair<CellInfo *, Loc>> cell_rel;
-        std::unordered_set<IdString> cells;
+        pool<IdString> cells;
         std::vector<std::pair<CellInfo *, BelId>> moves_made;
         std::vector<std::pair<CellInfo *, BelId>> dest_bels;
         double delta = 0;
@@ -1065,7 +1065,7 @@ class SAPlacer
                                 mc.already_changed_arcs[pn->udata][i] = true;
                             }
                 } else if (port.second.type == PORT_IN) {
-                    auto usr = fast_port_to_user.at(&port.second);
+                    auto usr = fast_port_to_user.at(std::make_pair(cell->name, port.first));
                     if (!mc.already_changed_arcs[pn->udata][usr]) {
                         mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr));
                         mc.already_changed_arcs[pn->udata][usr] = true;
@@ -1122,7 +1122,7 @@ class SAPlacer
             NetInfo *ni = net.second.get();
             for (size_t i = 0; i < ni->users.size(); i++) {
                 auto &usr = ni->users.at(i);
-                fast_port_to_user[&(usr.cell->ports.at(usr.port))] = i;
+                fast_port_to_user[std::make_pair(usr.cell->name, usr.port)] = i;
             }
         }
     }
@@ -1130,11 +1130,11 @@ class SAPlacer
     // Simple routeability driven placement
     const int large_cell_thresh = 50;
     int total_net_share = 0;
-    std::vector<std::vector<std::unordered_map<IdString, int>>> nets_by_tile;
+    std::vector<std::vector<dict<IdString, int>>> nets_by_tile;
     void setup_nets_by_tile()
     {
         total_net_share = 0;
-        nets_by_tile.resize(max_x + 1, std::vector<std::unordered_map<IdString, int>>(max_y + 1));
+        nets_by_tile.resize(max_x + 1, std::vector<dict<IdString, int>>(max_y + 1));
         for (auto &cell : ctx->cells) {
             CellInfo *ci = cell.second.get();
             if (int(ci->ports.size()) > large_cell_thresh)
@@ -1194,7 +1194,7 @@ class SAPlacer
     std::vector<std::vector<double>> net_arc_tcost;
 
     // Fast lookup for cell port to net user index
-    std::unordered_map<const PortInfo *, size_t> fast_port_to_user;
+    dict<std::pair<IdString, IdString>, size_t> fast_port_to_user;
 
     // Wirelength and timing cost at last and current iteration
     wirelen_t last_wirelen_cost, curr_wirelen_cost;
@@ -1207,10 +1207,10 @@ class SAPlacer
     bool improved = false;
     int n_move, n_accept;
     int diameter = 35, max_x = 1, max_y = 1;
-    std::unordered_map<IdString, std::tuple<int, int>> bel_types;
-    std::unordered_map<IdString, BoundingBox> region_bounds;
+    dict<IdString, std::tuple<int, int>> bel_types;
+    dict<IdString, BoundingBox> region_bounds;
     FastBels fast_bels;
-    std::unordered_set<BelId> locked_bels;
+    pool<BelId> locked_bels;
     std::vector<NetInfo *> net_by_udata;
     std::vector<decltype(NetInfo::udata)> old_udata;
     bool require_legal = true;
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index c26e1556..f1419bdb 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -43,7 +43,6 @@
 #include <numeric>
 #include <queue>
 #include <tuple>
-#include <unordered_map>
 #include "fast_bels.h"
 #include "log.h"
 #include "nextpnr.h"
@@ -188,14 +187,14 @@ class HeAPPlacer
 
         std::vector<std::tuple<CellInfo *, BelId, PlaceStrength>> solution;
 
-        std::vector<std::unordered_set<BelBucketId>> heap_runs;
-        std::unordered_set<BelBucketId> all_buckets;
-        std::unordered_map<BelBucketId, int> bucket_count;
+        std::vector<pool<BelBucketId>> heap_runs;
+        pool<BelBucketId> all_buckets;
+        dict<BelBucketId, int> bucket_count;
 
         for (auto cell : place_cells) {
             BelBucketId bucket = ctx->getBelBucketForCellType(cell->type);
             if (!all_buckets.count(bucket)) {
-                heap_runs.push_back(std::unordered_set<BelBucketId>{bucket});
+                heap_runs.push_back(pool<BelBucketId>{bucket});
                 all_buckets.insert(bucket);
             }
             bucket_count[bucket]++;
@@ -253,9 +252,9 @@ class HeAPPlacer
                 for (const auto &group : cfg.cellGroups)
                     CutSpreader(this, group).run();
 
-                for (auto type : sorted(run))
+                for (auto type : run)
                     if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(),
-                                    [type](const std::unordered_set<BelBucketId> &grp) { return !grp.count(type); }))
+                                    [type](const pool<BelBucketId> &grp) { return !grp.count(type); }))
                         CutSpreader(this, {type}).run();
 
                 // Run strict legalisation to find a valid bel for all cells
@@ -360,7 +359,7 @@ class HeAPPlacer
 
     int max_x = 0, max_y = 0;
     FastBels fast_bels;
-    std::unordered_map<IdString, std::tuple<int, int>> bel_types;
+    dict<IdString, std::tuple<int, int>> bel_types;
 
     TimingAnalyser tmg;
 
@@ -370,7 +369,7 @@ class HeAPPlacer
         int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
     };
 
-    std::unordered_map<IdString, BoundingBox> constraint_region_bounds;
+    dict<IdString, BoundingBox> constraint_region_bounds;
 
     // In some cases, we can't use bindBel because we allow overlap in the earlier stages. So we use this custom
     // structure instead
@@ -381,7 +380,7 @@ class HeAPPlacer
         double rawx, rawy;
         bool locked, global;
     };
-    std::unordered_map<IdString, CellLocation> cell_locs;
+    dict<IdString, CellLocation> cell_locs;
     // The set of cells that we will actually place. This excludes locked cells and children cells of macros/chains
     // (only the root of each macro is placed.)
     std::vector<CellInfo *> place_cells;
@@ -390,8 +389,8 @@ class HeAPPlacer
     // cells of a certain type)
     std::vector<CellInfo *> solve_cells;
 
-    std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
-    std::unordered_map<ClusterId, int> chain_size;
+    dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
+    dict<ClusterId, int> chain_size;
     // Performance counting
     double solve_time = 0, cl_time = 0, sl_time = 0;
 
@@ -448,8 +447,8 @@ class HeAPPlacer
             max_y = std::max(max_y, loc.y);
         }
 
-        std::unordered_set<IdString> cell_types_in_use;
-        std::unordered_set<BelBucketId> buckets_in_use;
+        pool<IdString> cell_types_in_use;
+        pool<BelBucketId> buckets_in_use;
         for (auto &cell : ctx->cells) {
             IdString cell_type = cell.second->type;
             cell_types_in_use.insert(cell_type);
@@ -515,13 +514,13 @@ class HeAPPlacer
     // FIXME: Are there better approaches to the initial placement (e.g. greedy?)
     void seed_placement()
     {
-        std::unordered_set<IdString> cell_types;
+        pool<IdString> cell_types;
         for (const auto &cell : ctx->cells) {
             cell_types.insert(cell.second->type);
         }
 
-        std::unordered_set<BelId> bels_used;
-        std::unordered_map<IdString, std::deque<BelId>> available_bels;
+        pool<BelId> bels_used;
+        dict<IdString, std::deque<BelId>> available_bels;
 
         for (auto bel : ctx->getBels()) {
             if (!ctx->checkBelAvail(bel)) {
@@ -612,7 +611,7 @@ class HeAPPlacer
     }
 
     // Setup the cells to be solved, returns the number of rows
-    int setup_solve_cells(std::unordered_set<BelBucketId> *buckets = nullptr)
+    int setup_solve_cells(pool<BelBucketId> *buckets = nullptr)
     {
         int row = 0;
         solve_cells.clear();
@@ -1106,11 +1105,11 @@ class HeAPPlacer
     class CutSpreader
     {
       public:
-        CutSpreader(HeAPPlacer *p, const std::unordered_set<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets)
+        CutSpreader(HeAPPlacer *p, const pool<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets)
         {
             // Get fast BELs data for all buckets being Cut/Spread.
             size_t idx = 0;
-            for (BelBucketId bucket : sorted(buckets)) {
+            for (BelBucketId bucket : buckets) {
                 type_index[bucket] = idx;
                 FastBels::FastBelsData *fast_bels;
                 p->fast_bels.getBelsForBelBucket(bucket, &fast_bels);
@@ -1198,8 +1197,8 @@ class HeAPPlacer
       private:
         HeAPPlacer *p;
         Context *ctx;
-        std::unordered_set<BelBucketId> buckets;
-        std::unordered_map<BelBucketId, size_t> type_index;
+        pool<BelBucketId> buckets;
+        dict<BelBucketId, size_t> type_index;
         std::vector<std::vector<std::vector<int>>> occupancy;
         std::vector<std::vector<int>> groups;
         std::vector<std::vector<ChainExtent>> chaines;
@@ -1208,7 +1207,7 @@ class HeAPPlacer
         std::vector<std::vector<std::vector<std::vector<BelId>>> *> fb;
 
         std::vector<SpreaderRegion> regions;
-        std::unordered_set<int> merged_regions;
+        pool<int> merged_regions;
         // Cells at a location, sorted by real (not integer) x and y
         std::vector<std::vector<std::vector<CellInfo *>>> cells_at_location;
 
@@ -1490,7 +1489,7 @@ class HeAPPlacer
                         }
                     }
                     if (!changed) {
-                        for (auto bucket : sorted(buckets)) {
+                        for (auto bucket : buckets) {
                             if (reg.cells > reg.bels) {
                                 IdString bucket_name = ctx->getBelBucketName(bucket);
                                 log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0,
diff --git a/common/placer_heap.h b/common/placer_heap.h
index 00913062..9b3c3ed0 100644
--- a/common/placer_heap.h
+++ b/common/placer_heap.h
@@ -46,10 +46,10 @@ struct PlacerHeapCfg
     int spread_scale_x, spread_scale_y;
 
     // These cell types will be randomly locked to prevent singular matrices
-    std::unordered_set<IdString> ioBufTypes;
+    pool<IdString> ioBufTypes;
     // These cell types are part of the same unit (e.g. slices split into
     // components) so will always be spread together
-    std::vector<std::unordered_set<BelBucketId>> cellGroups;
+    std::vector<pool<BelBucketId>> cellGroups;
 };
 
 extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg);
diff --git a/ecp5/arch_place.cc b/ecp5/arch_place.cc
index 0da20151..a98d96ec 100644
--- a/ecp5/arch_place.cc
+++ b/ecp5/arch_place.cc
@@ -98,15 +98,6 @@ void Arch::permute_luts()
     TimingAnalyser tmg(getCtx());
     tmg.setup();
 
-    std::unordered_map<PortInfo *, size_t> port_to_user;
-    for (auto &net : nets) {
-        NetInfo *ni = net.second.get();
-        for (size_t i = 0; i < ni->users.size(); i++) {
-            auto &usr = ni->users.at(i);
-            port_to_user[&(usr.cell->ports.at(usr.port))] = i;
-        }
-    }
-
     auto proc_lut = [&](CellInfo *ci, int lut) {
         std::vector<IdString> port_names;
         for (int i = 0; i < 4; i++)