Merge pull request #718 from YosysHQ/gatecat/hashlib

Moving from unordered_{map, set} to hashlib

11 files changed, 72 insertions, 110 deletions

diff --git a/ice40/arch.h b/ice40/arch.h
index 29396f49..9c9a118f 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -400,10 +400,10 @@ struct Arch : BaseArch<ArchRanges>
     const ChipInfoPOD *chip_info;
     const PackageInfoPOD *package_info;
 
-    mutable std::unordered_map<IdStringList, int> bel_by_name;
-    mutable std::unordered_map<IdStringList, int> wire_by_name;
-    mutable std::unordered_map<IdStringList, int> pip_by_name;
-    mutable std::unordered_map<Loc, int> bel_by_loc;
+    mutable dict<IdStringList, int> bel_by_name;
+    mutable dict<IdStringList, int> wire_by_name;
+    mutable dict<IdStringList, int> pip_by_name;
+    mutable dict<Loc, int> bel_by_loc;
 
     std::vector<bool> bel_carry;
     std::vector<CellInfo *> bel_to_cell;
@@ -414,7 +414,7 @@ struct Arch : BaseArch<ArchRanges>
     // fast access to  X and Y IdStrings for building object names
     std::vector<IdString> x_ids, y_ids;
     // inverse of the above for name->object mapping
-    std::unordered_map<IdString, int> id_to_x, id_to_y;
+    dict<IdString, int> id_to_x, id_to_y;
 
     ArchArgs args;
     Arch(ArchArgs args);
diff --git a/ice40/arch_pybindings.cc b/ice40/arch_pybindings.cc
index 6922887d..41c97b1b 100644
--- a/ice40/arch_pybindings.cc
+++ b/ice40/arch_pybindings.cc
@@ -60,10 +60,10 @@ void arch_wrap_python(py::module &m)
                            .def("place", &Context::place)
                            .def("route", &Context::route);
 
-    typedef std::unordered_map<IdString, std::unique_ptr<CellInfo>> CellMap;
-    typedef std::unordered_map<IdString, std::unique_ptr<NetInfo>> NetMap;
-    typedef std::unordered_map<IdString, IdString> AliasMap;
-    typedef std::unordered_map<IdString, HierarchicalCell> HierarchyMap;
+    typedef dict<IdString, std::unique_ptr<CellInfo>> CellMap;
+    typedef dict<IdString, std::unique_ptr<NetInfo>> NetMap;
+    typedef dict<IdString, IdString> AliasMap;
+    typedef dict<IdString, HierarchicalCell> HierarchyMap;
 
     auto belpin_cls = py::class_<ContextualWrapper<BelPin>>(m, "BelPin");
     readonly_wrapper<BelPin, decltype(&BelPin::bel), &BelPin::bel, conv_to_str<BelId>>::def_wrap(belpin_cls, "bel");
diff --git a/ice40/archdefs.h b/ice40/archdefs.h
index c2b7019c..6ef5432f 100644
--- a/ice40/archdefs.h
+++ b/ice40/archdefs.h
@@ -20,9 +20,8 @@
 #ifndef ICE40_ARCHDEFS_H
 #define ICE40_ARCHDEFS_H
 
-#include <boost/functional/hash.hpp>
-
 #include "base_clusterinfo.h"
+#include "hashlib.h"
 #include "idstring.h"
 #include "nextpnr_namespaces.h"
 
@@ -55,6 +54,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; }
+    unsigned int hash() const { return index; }
 };
 
 struct WireId
@@ -64,6 +64,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; }
+    unsigned int hash() const { return index; }
 };
 
 struct PipId
@@ -73,6 +74,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; }
+    unsigned int hash() const { return index; }
 };
 
 struct GroupId
@@ -96,6 +98,7 @@ struct GroupId
 
     bool operator==(const GroupId &other) const { return (type == other.type) && (x == other.x) && (y == other.y); }
     bool operator!=(const GroupId &other) const { return (type != other.type) || (x != other.x) || (y == other.y); }
+    unsigned int hash() const { return mkhash(mkhash(x, y), int(type)); }
 };
 
 struct DecalId
@@ -113,6 +116,7 @@ struct DecalId
 
     bool operator==(const DecalId &other) const { return (type == other.type) && (index == other.index); }
     bool operator!=(const DecalId &other) const { return (type != other.type) || (index != other.index); }
+    unsigned int hash() const { return mkhash(index, int(type)); }
 };
 
 struct ArchNetInfo
@@ -159,48 +163,4 @@ typedef IdString ClusterId;
 
 NEXTPNR_NAMESPACE_END
 
-namespace std {
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX BelId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX BelId &bel) const noexcept { return hash<int>()(bel.index); }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX WireId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX WireId &wire) const noexcept
-    {
-        return hash<int>()(wire.index);
-    }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX PipId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX PipId &pip) const noexcept { return hash<int>()(pip.index); }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX GroupId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX GroupId &group) const noexcept
-    {
-        std::size_t seed = 0;
-        boost::hash_combine(seed, hash<int>()(group.type));
-        boost::hash_combine(seed, hash<int>()(group.x));
-        boost::hash_combine(seed, hash<int>()(group.y));
-        return seed;
-    }
-};
-
-template <> struct hash<NEXTPNR_NAMESPACE_PREFIX DecalId>
-{
-    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX DecalId &decal) const noexcept
-    {
-        std::size_t seed = 0;
-        boost::hash_combine(seed, hash<int>()(decal.type));
-        boost::hash_combine(seed, hash<int>()(decal.index));
-        return seed;
-    }
-};
-
-} // namespace std
-
 #endif /* ICE40_ARCHDEFS_H */
diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc
index 6b625b6a..56b5561c 100644
--- a/ice40/bitstream.cc
+++ b/ice40/bitstream.cc
@@ -252,7 +252,7 @@ static BelPin get_one_bel_pin(const Context *ctx, WireId wire)
 }
 
 // Permute LUT init value given map (LUT input -> ext input)
-unsigned permute_lut(unsigned orig_init, const std::unordered_map<int, int> &input_permute)
+unsigned permute_lut(unsigned orig_init, const dict<int, int> &input_permute)
 {
     unsigned new_init = 0;
 
@@ -387,8 +387,8 @@ void write_asc(const Context *ctx, std::ostream &out)
     }
 
     // Scan for PLL and collects the affected SB_IOs
-    std::unordered_set<Loc> sb_io_used_by_pll_out;
-    std::unordered_set<Loc> sb_io_used_by_pll_pad;
+    pool<Loc> sb_io_used_by_pll_out;
+    pool<Loc> sb_io_used_by_pll_pad;
 
     for (auto &cell : ctx->cells) {
         if (cell.second->type != ctx->id("ICESTORM_PLL"))
@@ -447,7 +447,7 @@ void write_asc(const Context *ctx, std::ostream &out)
             std::vector<bool> lc(20, false);
 
             // Discover permutation
-            std::unordered_map<int, int> input_perm;
+            dict<int, int> input_perm;
             std::set<int> unused;
             for (int i = 0; i < 4; i++)
                 unused.insert(i);
diff --git a/ice40/cells.cc b/ice40/cells.cc
index d23b6c49..9517c590 100644
--- a/ice40/cells.cc
+++ b/ice40/cells.cc
@@ -412,7 +412,7 @@ void dff_to_lc(const Context *ctx, CellInfo *dff, CellInfo *lc, bool pass_thru_l
     replace_port(dff, ctx->id("Q"), lc, ctx->id("O"));
 }
 
-void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, std::unordered_set<IdString> &todelete_cells)
+void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, pool<IdString> &todelete_cells)
 {
     if (nxio->type == ctx->id("$nextpnr_ibuf")) {
         sbio->params[ctx->id("PIN_TYPE")] = 1;
diff --git a/ice40/cells.h b/ice40/cells.h
index 777ca3e2..d4c0edf4 100644
--- a/ice40/cells.h
+++ b/ice40/cells.h
@@ -130,7 +130,7 @@ void lut_to_lc(const Context *ctx, CellInfo *lut, CellInfo *lc, bool no_dff = tr
 void dff_to_lc(const Context *ctx, CellInfo *dff, CellInfo *lc, bool pass_thru_lut = false);
 
 // Convert a nextpnr IO buffer to a SB_IO
-void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, std::unordered_set<IdString> &todelete_cells);
+void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, pool<IdString> &todelete_cells);
 
 // Return true if a port is a clock port
 bool is_clock_port(const BaseCtx *ctx, const PortRef &port);
diff --git a/ice40/chains.cc b/ice40/chains.cc
index 2607959a..cfc8b4a1 100644
--- a/ice40/chains.cc
+++ b/ice40/chains.cc
@@ -253,15 +253,15 @@ class ChainConstrainer
                         return i3_next;
                     return (CellInfo *)nullptr;
                 });
-        std::unordered_set<IdString> chained;
+        pool<IdString> chained;
         for (auto &base_chain : carry_chains) {
             for (auto c : base_chain.cells)
                 chained.insert(c->name);
         }
         // Any cells not in chains, but with carry enabled, must also be put in a single-carry chain
         // for correct processing
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (chained.find(cell.first) == chained.end() && is_lc(ctx, ci) &&
                 bool_or_default(ci->params, ctx->id("CARRY_ENABLE"))) {
                 CellChain sChain;
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<WireId, PipId> route;
+        dict<WireId, PipId> route;
 
 #if NUM_FUZZ_ROUTES <= 1000
         if (!ctx->getActualRouteDelay(src, dst, nullptr, &route, false))
diff --git a/ice40/main.cc b/ice40/main.cc
index e537c2f4..28e6de9a 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -35,7 +35,7 @@ class Ice40CommandHandler : public CommandHandler
   public:
     Ice40CommandHandler(int argc, char **argv);
     virtual ~Ice40CommandHandler(){};
-    std::unique_ptr<Context> createContext(std::unordered_map<std::string, Property> &values) override;
+    std::unique_ptr<Context> createContext(dict<std::string, Property> &values) override;
     void setupArchContext(Context *ctx) override;
     void validate() override;
     void customAfterLoad(Context *ctx) override;
@@ -129,7 +129,7 @@ void Ice40CommandHandler::setupArchContext(Context *ctx)
     }
 }
 
-std::unique_ptr<Context> Ice40CommandHandler::createContext(std::unordered_map<std::string, Property> &values)
+std::unique_ptr<Context> Ice40CommandHandler::createContext(dict<std::string, Property> &values)
 {
     ArchArgs chipArgs;
     chipArgs.type = ArchArgs::NONE;
diff --git a/ice40/pack.cc b/ice40/pack.cc
index 51138a22..62b08534 100644
--- a/ice40/pack.cc
+++ b/ice40/pack.cc
@@ -21,7 +21,6 @@
 
 #include <algorithm>
 #include <iterator>
-#include <unordered_set>
 #include "cells.h"
 #include "chains.h"
 #include "design_utils.h"
@@ -35,15 +34,16 @@ static void pack_lut_lutffs(Context *ctx)
 {
     log_info("Packing LUT-FFs..\n");
     int lut_only = 0, lut_and_ff = 0;
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (ctx->verbose)
             log_info("cell '%s' is of type '%s'\n", ci->name.c_str(ctx), ci->type.c_str(ctx));
         if (is_lut(ctx, ci)) {
             std::unique_ptr<CellInfo> packed = create_ice_cell(ctx, ctx->id("ICESTORM_LC"), ci->name.str(ctx) + "_LC");
-            std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(packed->attrs, packed->attrs.begin()));
+            for (auto &attr : ci->attrs)
+                packed->attrs[attr.first] = attr.second;
             packed_cells.insert(ci->name);
             if (ctx->verbose)
                 log_info("packed cell %s into %s\n", ci->name.c_str(ctx), packed->name.c_str(ctx));
@@ -99,16 +99,17 @@ static void pack_nonlut_ffs(Context *ctx)
 {
     log_info("Packing non-LUT FFs..\n");
 
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
     int ff_only = 0;
 
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_ff(ctx, ci)) {
             std::unique_ptr<CellInfo> packed =
                     create_ice_cell(ctx, ctx->id("ICESTORM_LC"), ci->name.str(ctx) + "_DFFLC");
-            std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(packed->attrs, packed->attrs.begin()));
+            for (auto &attr : ci->attrs)
+                packed->attrs[attr.first] = attr.second;
             if (ctx->verbose)
                 log_info("packed cell %s into %s\n", ci->name.c_str(ctx), packed->name.c_str(ctx));
             packed_cells.insert(ci->name);
@@ -142,13 +143,13 @@ static bool net_is_constant(const Context *ctx, NetInfo *net, bool &value)
 static void pack_carries(Context *ctx)
 {
     log_info("Packing carries..\n");
-    std::unordered_set<IdString> exhausted_cells;
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> exhausted_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
     int carry_only = 0;
 
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_carry(ctx, ci)) {
             packed_cells.insert(cell.first);
 
@@ -272,11 +273,11 @@ static void pack_ram(Context *ctx)
 {
     log_info("Packing RAMs..\n");
 
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
 
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_ram(ctx, ci)) {
             std::unique_ptr<CellInfo> packed =
                     create_ice_cell(ctx, ctx->id("ICESTORM_RAM"), ci->name.str(ctx) + "_RAM");
@@ -379,8 +380,8 @@ static void pack_constants(Context *ctx)
 
     bool gnd_used = false;
 
-    for (auto net : sorted(ctx->nets)) {
-        NetInfo *ni = net.second;
+    for (auto &net : ctx->nets) {
+        NetInfo *ni = net.second.get();
         if (ni->driver.cell != nullptr && ni->driver.cell->type == ctx->id("GND")) {
             IdString drv_cell = ni->driver.cell->name;
             set_net_constant(ctx, ni, gnd_net_info, false);
@@ -464,13 +465,13 @@ static bool is_ice_iob(const Context *ctx, const CellInfo *cell)
 // Pack IO buffers
 static void pack_io(Context *ctx)
 {
-    std::unordered_set<IdString> packed_cells;
-    std::unordered_set<IdString> delete_nets;
+    pool<IdString> packed_cells;
+    pool<IdString> delete_nets;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
     log_info("Packing IOs..\n");
 
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_nextpnr_iob(ctx, ci)) {
             CellInfo *sb = nullptr, *rgb = nullptr;
             if (ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) {
@@ -531,7 +532,8 @@ static void pack_io(Context *ctx)
             for (auto port : ci->ports)
                 disconnect_port(ctx, ci, port.first);
             packed_cells.insert(ci->name);
-            std::copy(ci->attrs.begin(), ci->attrs.end(), std::inserter(sb->attrs, sb->attrs.begin()));
+            for (auto &attr : ci->attrs)
+                sb->attrs[attr.first] = attr.second;
         } else if (is_sb_io(ctx, ci) || is_sb_gb_io(ctx, ci)) {
             NetInfo *net = ci->ports.at(ctx->id("PACKAGE_PIN")).net;
             if ((net != nullptr) && ((net->users.size() > 2) ||
@@ -541,8 +543,8 @@ static void pack_io(Context *ctx)
                           ci->name.c_str(ctx));
         }
     }
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_sb_gb_io(ctx, ci)) {
             // If something is connecto the GLOBAL OUTPUT, create the fake 'matching' SB_GB
             std::unique_ptr<CellInfo> gb =
@@ -637,8 +639,8 @@ static void promote_globals(Context *ctx)
     const int enable_fanout_thresh = 15;
     const int reset_fanout_thresh = 15;
     std::map<IdString, int> clock_count, reset_count, cen_count, logic_count;
-    for (auto net : sorted(ctx->nets)) {
-        NetInfo *ni = net.second;
+    for (auto &net : ctx->nets) {
+        NetInfo *ni = net.second.get();
         if (ni->driver.cell != nullptr && !ctx->is_global_net(ni)) {
             clock_count[net.first] = 0;
             reset_count[net.first] = 0;
@@ -778,8 +780,8 @@ static void place_plls(Context *ctx)
     }
 
     // Find all the PLLs cells we need to place and do pre-checks
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (!is_sb_pll40(ctx, ci))
             continue;
 
@@ -861,8 +863,8 @@ static void place_plls(Context *ctx)
     }
 
     // Scan all SB_IOs to check for conflict with PLL BELs
-    for (auto io_cell : sorted(ctx->cells)) {
-        CellInfo *io_ci = io_cell.second;
+    for (auto &io_cell : ctx->cells) {
+        CellInfo *io_ci = io_cell.second.get();
         if (!is_sb_io(ctx, io_ci))
             continue;
 
@@ -899,8 +901,8 @@ static void place_plls(Context *ctx)
     }
 
     // Scan all SB_GBs to check for conflicts with PLL BELs
-    for (auto gb_cell : sorted(ctx->cells)) {
-        CellInfo *gb_ci = gb_cell.second;
+    for (auto &gb_cell : ctx->cells) {
+        CellInfo *gb_ci = gb_cell.second.get();
         if (!is_gbuf(ctx, gb_ci))
             continue;
 
@@ -1116,12 +1118,12 @@ static void pack_special(Context *ctx)
 {
     log_info("Packing special functions..\n");
 
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
 
     // Handle LED_DRV_CUR first to set the ledCurConnected flag before RGB_DRV is handled below.
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_sb_led_drv_cur(ctx, ci)) {
             /* Force placement (no choices anyway) */
             cell_place_unique(ctx, ci);
@@ -1139,8 +1141,8 @@ static void pack_special(Context *ctx)
             ctx->nets.erase(ledpu_net->name);
         }
     }
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_sb_lfosc(ctx, ci)) {
             std::unique_ptr<CellInfo> packed =
                     create_ice_cell(ctx, ctx->id("ICESTORM_LFOSC"), ci->name.str(ctx) + "_OSC");
@@ -1296,10 +1298,10 @@ void pack_plls(Context *ctx)
 {
     log_info("Packing PLLs..\n");
 
-    std::unordered_set<IdString> packed_cells;
+    pool<IdString> packed_cells;
     std::vector<std::unique_ptr<CellInfo>> new_cells;
-    for (auto cell : sorted(ctx->cells)) {
-        CellInfo *ci = cell.second;
+    for (auto &cell : ctx->cells) {
+        CellInfo *ci = cell.second.get();
         if (is_sb_pll40(ctx, ci)) {
             bool is_pad = is_sb_pll40_pad(ctx, ci);
             bool is_core = !is_pad;
diff --git a/ice40/pcf.cc b/ice40/pcf.cc
index 56a4a336..c6289892 100644
--- a/ice40/pcf.cc
+++ b/ice40/pcf.cc
@@ -108,8 +108,8 @@ bool apply_pcf(Context *ctx, std::string filename, std::istream &in)
                 log_error("unsupported PCF command '%s' (on line %d)\n", cmd.c_str(), lineno);
             }
         }
-        for (auto cell : sorted(ctx->cells)) {
-            CellInfo *ci = cell.second;
+        for (auto &cell : ctx->cells) {
+            CellInfo *ci = cell.second.get();
             if (ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_obuf") ||
                 ci->type == ctx->id("$nextpnr_iobuf")) {
                 if (!ci->attrs.count(ctx->id("BEL"))) {