diff options
Diffstat (limited to 'fpga_interchange')
25 files changed, 176 insertions, 326 deletions
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 663587fd..8e7fe2a3 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -63,21 +63,8 @@ struct SiteBelPair SiteBelPair(std::string site, IdString bel) : site(site), bel(bel) {} bool operator==(const SiteBelPair &other) const { return site == other.site && bel == other.bel; } + unsigned int hash() const { return mkhash(std::hash<std::string>()(site), bel.hash()); } }; -NEXTPNR_NAMESPACE_END - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SiteBelPair> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SiteBelPair &site_bel) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<std::string>()(site_bel.site)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(site_bel.bel)); - return seed; - } -}; - -NEXTPNR_NAMESPACE_BEGIN static std::pair<std::string, std::string> split_identifier_name_dot(const std::string &name) { @@ -180,7 +167,7 @@ Arch::Arch(ArchArgs args) : args(args), disallow_site_routing(false) } } - std::unordered_set<SiteBelPair> site_bel_pads; + pool<SiteBelPair> site_bel_pads; for (const auto &package_pin : chip_info->packages[package_index].pins) { IdString site(package_pin.site); IdString bel(package_pin.bel); @@ -1951,7 +1938,7 @@ void Arch::unmask_bel_pins() void Arch::remove_site_routing() { - HashTables::HashSet<WireId> wires_to_unbind; + pool<WireId> wires_to_unbind; for (auto &net_pair : nets) { for (auto &wire_pair : net_pair.second->wires) { WireId wire = wire_pair.first; diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 5c7bbc52..c8a61430 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -103,14 +103,14 @@ struct Arch : ArchAPI<ArchRanges> // Guard initialization of "by_name" maps if accessed from multiple // threads on a "const Context *". mutable std::mutex by_name_mutex; - mutable std::unordered_map<IdString, int> tile_by_name; - mutable std::unordered_map<IdString, std::pair<int, int>> site_by_name; + mutable dict<IdString, int> tile_by_name; + mutable dict<IdString, std::pair<int, int>> site_by_name; - std::unordered_map<WireId, NetInfo *> wire_to_net; - std::unordered_map<PipId, NetInfo *> pip_to_net; + dict<WireId, NetInfo *> wire_to_net; + dict<PipId, NetInfo *> pip_to_net; DedicatedInterconnect dedicated_interconnect; - HashTables::HashMap<int32_t, TileStatus> tileStatus; + dict<int32_t, TileStatus> tileStatus; PseudoPipData pseudo_pip_data; ArchArgs args; @@ -685,8 +685,8 @@ struct Arch : ArchAPI<ArchRanges> // ------------------------------------------------- - void place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels, - std::unordered_set<CellInfo *> *placed_cells); + void place_iobufs(WireId pad_wire, NetInfo *net, const pool<CellInfo *, hash_ptr_ops> &tightly_attached_bels, + pool<CellInfo *, hash_ptr_ops> *placed_cells); void pack_ports(); void decode_lut_cells(); @@ -858,7 +858,7 @@ struct Arch : ArchAPI<ArchRanges> IdString get_bel_tiletype(BelId bel) const { return IdString(loc_info(chip_info, bel).name); } - std::unordered_map<WireId, Loc> sink_locs, source_locs; + dict<WireId, Loc> sink_locs, source_locs; // ------------------------------------------------- void assignArchInfo() final {} @@ -875,8 +875,8 @@ struct Arch : ArchAPI<ArchRanges> void write_physical_netlist(const std::string &filename) const; void parse_xdc(const std::string &filename); - std::unordered_set<IdString> io_port_types; - std::unordered_set<BelId> pads; + pool<IdString> io_port_types; + pool<BelId> pads; bool is_site_port(PipId pip) const { @@ -1083,7 +1083,7 @@ struct Arch : ArchAPI<ArchRanges> IdString gnd_cell_pin; IdString vcc_cell_pin; std::vector<std::vector<LutElement>> lut_elements; - std::unordered_map<IdString, const LutCellPOD *> lut_cells; + dict<IdString, const LutCellPOD *> lut_cells; // Of the LUT cells, which is used for wires? // Note: May be null in arch's without wire LUT types. Assumption is diff --git a/fpga_interchange/arch_pack_io.cc b/fpga_interchange/arch_pack_io.cc index 9322d028..fdbb1130 100644 --- a/fpga_interchange/arch_pack_io.cc +++ b/fpga_interchange/arch_pack_io.cc @@ -24,8 +24,8 @@ NEXTPNR_NAMESPACE_BEGIN -void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels, - std::unordered_set<CellInfo *> *placed_cells) +void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const pool<CellInfo *, hash_ptr_ops> &tightly_attached_bels, + pool<CellInfo *, hash_ptr_ops> *placed_cells) { for (BelPin bel_pin : getWireBelPins(pad_wire)) { BelId bel = bel_pin.bel; @@ -57,7 +57,7 @@ void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set< void Arch::pack_ports() { - std::unordered_map<IdString, const TileInstInfoPOD *> tile_type_prototypes; + dict<IdString, const TileInstInfoPOD *> tile_type_prototypes; for (size_t i = 0; i < chip_info->tiles.size(); ++i) { const auto &tile = chip_info->tiles[i]; const auto &tile_type = chip_info->tile_types[tile.type]; @@ -66,9 +66,9 @@ void Arch::pack_ports() } // set(site_types) for package pins - std::unordered_set<IdString> package_sites; + pool<IdString> package_sites; // Package pin -> (Site type -> BelId) - std::unordered_map<IdString, std::vector<std::pair<IdString, BelId>>> package_pin_bels; + dict<IdString, std::vector<std::pair<IdString, BelId>>> package_pin_bels; for (const PackagePinPOD &package_pin : chip_info->packages[package_index].pins) { IdString pin(package_pin.package_pin); IdString bel(package_pin.bel); @@ -78,7 +78,7 @@ void Arch::pack_ports() for (size_t i = 0; i < chip_info->tiles.size(); ++i) { const auto &tile = chip_info->tiles[i]; - std::unordered_set<uint32_t> package_pin_sites; + pool<uint32_t> package_pin_sites; for (size_t j = 0; j < tile.sites.size(); ++j) { auto &site_data = chip_info->sites[tile.sites[j]]; if (site == id(site_data.site_name.get())) { @@ -102,8 +102,8 @@ void Arch::pack_ports() } // Determine for each package site type, which site types are possible. - std::unordered_set<IdString> package_pin_site_types; - std::unordered_map<IdString, std::unordered_set<IdString>> possible_package_site_types; + pool<IdString> package_pin_site_types; + dict<IdString, pool<IdString>> possible_package_site_types; for (const TileInstInfoPOD &tile : chip_info->tiles) { for (size_t site_index : tile.sites) { const SiteInstInfoPOD &site = chip_info->sites[site_index]; @@ -121,7 +121,7 @@ void Arch::pack_ports() for (auto port_pair : port_cells) { IdString port_name = port_pair.first; CellInfo *port_cell = port_pair.second; - std::unordered_set<CellInfo *> tightly_attached_bels; + pool<CellInfo *, hash_ptr_ops> tightly_attached_bels; for (auto port_pair : port_cell->ports) { const PortInfo &port_info = port_pair.second; @@ -145,7 +145,7 @@ void Arch::pack_ports() } NPNR_ASSERT(tightly_attached_bels.erase(port_cell) == 1); - std::unordered_set<IdString> cell_types_in_io_group; + pool<IdString> cell_types_in_io_group; for (CellInfo *cell : tightly_attached_bels) { NPNR_ASSERT(port_cells.find(cell->name) == port_cells.end()); cell_types_in_io_group.emplace(cell->type); @@ -153,7 +153,7 @@ void Arch::pack_ports() // Get possible placement locations for tightly coupled BELs with // port. - std::unordered_set<IdString> possible_site_types; + pool<IdString> possible_site_types; for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) { IdString tile_type_name(tile_type.name); for (const BelInfoPOD &bel_info : tile_type.bel_data) { @@ -195,7 +195,7 @@ void Arch::pack_ports() } } - // std::unordered_map<IdString, std::unordered_map<IdString, BelId>> package_pin_bels; + // dict<IdString, dict<IdString, BelId>> package_pin_bels; IdString package_pin_id = id(iter->second.as_string()); auto pin_iter = package_pin_bels.find(package_pin_id); if (pin_iter == package_pin_bels.end()) { @@ -233,7 +233,7 @@ void Arch::pack_ports() log_info("Binding port %s to BEL %s\n", port_name.c_str(getCtx()), getCtx()->nameOfBel(package_bel)); } - std::unordered_set<CellInfo *> placed_cells; + pool<CellInfo *, hash_ptr_ops> placed_cells; bindBel(package_bel, port_cell, STRENGTH_FIXED); placed_cells.emplace(port_cell); diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h index ba4fe054..2d27cccf 100644 --- a/fpga_interchange/archdefs.h +++ b/fpga_interchange/archdefs.h @@ -24,7 +24,6 @@ #include <boost/functional/hash.hpp> #include <cstdint> -#include "hash_table.h" #include "hashlib.h" #include "luts.h" #include "nextpnr_namespaces.h" @@ -119,9 +118,9 @@ struct ArchNetInfo struct ArchCellInfo { int32_t cell_mapping = -1; - HashTables::HashMap<IdString, std::vector<IdString>> cell_bel_pins; - HashTables::HashMap<IdString, std::vector<IdString>> masked_cell_bel_pins; - HashTables::HashSet<IdString> const_ports; + dict<IdString, std::vector<IdString>> cell_bel_pins; + dict<IdString, std::vector<IdString>> masked_cell_bel_pins; + pool<IdString> const_ports; LutCell lut_cell; }; diff --git a/fpga_interchange/cell_parameters.h b/fpga_interchange/cell_parameters.h index de82e76b..d6d4ccec 100644 --- a/fpga_interchange/cell_parameters.h +++ b/fpga_interchange/cell_parameters.h @@ -25,7 +25,6 @@ #include "chipdb.h" #include "dynamic_bitarray.h" -#include "hash_table.h" #include "nextpnr_namespaces.h" #include "property.h" @@ -42,7 +41,7 @@ struct CellParameters bool compare_property(const Context *ctx, IdString cell_type, IdString parameter, const Property &property, IdString value_to_compare) const; - HashTables::HashMap<std::pair<IdString, IdString>, const CellParameterPOD *, PairHash> parameters; + dict<std::pair<IdString, IdString>, const CellParameterPOD *> parameters; std::regex verilog_binary_re; std::regex verilog_hex_re; diff --git a/fpga_interchange/cost_map.cc b/fpga_interchange/cost_map.cc index 868fdca0..c20ba11b 100644 --- a/fpga_interchange/cost_map.cc +++ b/fpga_interchange/cost_map.cc @@ -121,7 +121,7 @@ delay_t CostMap::get_delay(const Context *ctx, WireId src_wire, WireId dst_wire) } void CostMap::set_cost_map(const Context *ctx, const TypeWirePair &wire_pair, - const HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash> &delays) + const dict<std::pair<int32_t, int32_t>, delay_t> &delays) { CostMapEntry delay_matrix; diff --git a/fpga_interchange/cost_map.h b/fpga_interchange/cost_map.h index 810d0198..88fb97e4 100644 --- a/fpga_interchange/cost_map.h +++ b/fpga_interchange/cost_map.h @@ -24,7 +24,6 @@ #include <boost/multi_array.hpp> #include <mutex> -#include "hash_table.h" #include "lookahead.capnp.h" #include "nextpnr_namespaces.h" #include "nextpnr_types.h" @@ -39,7 +38,7 @@ class CostMap public: delay_t get_delay(const Context *ctx, WireId src, WireId dst) const; void set_cost_map(const Context *ctx, const TypeWirePair &wire_pair, - const HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash> &delays); + const dict<std::pair<int32_t, int32_t>, delay_t> &delays); void from_reader(lookahead_storage::CostMap::Reader reader); void to_builder(lookahead_storage::CostMap::Builder builder) const; @@ -53,7 +52,7 @@ class CostMap }; std::mutex cost_map_mutex_; - HashTables::HashMap<TypeWirePair, CostMapEntry> cost_map_; + dict<TypeWirePair, CostMapEntry> cost_map_; void fill_holes(const Context *ctx, const TypeWirePair &wire_pair, boost::multi_array<delay_t, 2> &matrix, delay_t delay_penality); diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc index 9f7e83ab..2f6fbcd3 100644 --- a/fpga_interchange/dedicated_interconnect.cc +++ b/fpga_interchange/dedicated_interconnect.cc @@ -496,7 +496,7 @@ void DedicatedInterconnect::find_dedicated_interconnect() } } - std::unordered_set<TileTypeBelPin> seen_pins; + pool<TileTypeBelPin> seen_pins; for (auto sink_pair : sinks) { for (auto src : sink_pair.second) { seen_pins.emplace(src.type_bel_pin); @@ -558,7 +558,7 @@ void DedicatedInterconnect::expand_sink_bel(BelId sink_bel, IdString sink_pin, W nodes_to_expand.push_back(wire_node); Loc sink_loc = ctx->getBelLocation(sink_bel); - std::unordered_set<DeltaTileTypeBelPin> srcs; + pool<DeltaTileTypeBelPin> srcs; while (!nodes_to_expand.empty()) { WireNode node_to_expand = nodes_to_expand.back(); @@ -701,7 +701,7 @@ void DedicatedInterconnect::expand_source_bel(BelId src_bel, IdString src_pin, W nodes_to_expand.push_back(wire_node); Loc src_loc = ctx->getBelLocation(src_bel); - std::unordered_set<DeltaTileTypeBelPin> dsts; + pool<DeltaTileTypeBelPin> dsts; while (!nodes_to_expand.empty()) { WireNode node_to_expand = nodes_to_expand.back(); diff --git a/fpga_interchange/dedicated_interconnect.h b/fpga_interchange/dedicated_interconnect.h index 9ddb05fd..085ced26 100644 --- a/fpga_interchange/dedicated_interconnect.h +++ b/fpga_interchange/dedicated_interconnect.h @@ -23,9 +23,9 @@ #include <boost/functional/hash.hpp> #include <cstdint> -#include <unordered_map> #include "archdefs.h" +#include "hashlib.h" #include "idstring.h" #include "nextpnr_namespaces.h" @@ -58,6 +58,7 @@ struct TileTypeBelPin { return tile_type != other.tile_type || bel_index != other.bel_index || bel_pin != other.bel_pin; } + unsigned int hash() const { return mkhash(mkhash(tile_type, bel_index), bel_pin.hash()); } }; struct DeltaTileTypeBelPin @@ -74,36 +75,9 @@ struct DeltaTileTypeBelPin { return delta_x != other.delta_x || delta_y != other.delta_y || type_bel_pin != other.type_bel_pin; } + unsigned int hash() const { return mkhash(mkhash(delta_x, delta_y), type_bel_pin.hash()); } }; -NEXTPNR_NAMESPACE_END - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX TileTypeBelPin> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TileTypeBelPin &type_bel_pin) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<int32_t>()(type_bel_pin.tile_type)); - boost::hash_combine(seed, std::hash<int32_t>()(type_bel_pin.bel_index)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(type_bel_pin.bel_pin)); - return seed; - } -}; - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX DeltaTileTypeBelPin> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX DeltaTileTypeBelPin &delta_bel_pin) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<int32_t>()(delta_bel_pin.delta_x)); - boost::hash_combine(seed, std::hash<int32_t>()(delta_bel_pin.delta_y)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX TileTypeBelPin>()(delta_bel_pin.type_bel_pin)); - return seed; - } -}; - -NEXTPNR_NAMESPACE_BEGIN - struct Context; // This class models dedicated interconnect present in the given fabric. @@ -123,8 +97,8 @@ struct DedicatedInterconnect { const Context *ctx; - std::unordered_map<TileTypeBelPin, std::unordered_set<DeltaTileTypeBelPin>> sinks; - std::unordered_map<TileTypeBelPin, std::unordered_set<DeltaTileTypeBelPin>> sources; + dict<TileTypeBelPin, pool<DeltaTileTypeBelPin>> sinks; + dict<TileTypeBelPin, pool<DeltaTileTypeBelPin>> sources; void init(const Context *ctx); diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index cf89ef1c..1d08b128 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -43,7 +43,7 @@ static void write_message(::capnp::MallocMessageBuilder & message, const std::st struct StringEnumerator { std::vector<std::string> strings; - std::unordered_map<std::string, size_t> string_to_index; + dict<std::string, size_t> string_to_index; size_t get_index(const std::string &s) { auto result = string_to_index.emplace(s, strings.size()); @@ -59,7 +59,7 @@ struct StringEnumerator { static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( const Context * ctx, StringEnumerator * strings, - const std::unordered_map<PipId, PlaceStrength> &pip_place_strength, + const dict<PipId, PlaceStrength> &pip_place_strength, PipId pip, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { if(ctx->is_pip_synthetic(pip)) { @@ -264,10 +264,10 @@ static void init_bel_pin( static void emit_net( const Context * ctx, StringEnumerator * strings, - const std::unordered_map<WireId, std::vector<PipId>> &pip_downhill, - const std::unordered_map<WireId, std::vector<BelPin>> &sinks, - std::unordered_set<PipId> *pips, - const std::unordered_map<PipId, PlaceStrength> &pip_place_strength, + const dict<WireId, std::vector<PipId>> &pip_downhill, + const dict<WireId, std::vector<BelPin>> &sinks, + pool<PipId> *pips, + const dict<PipId, PlaceStrength> &pip_place_strength, WireId wire, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { size_t number_branches = 0; @@ -349,7 +349,7 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder init_local_source( StringEnumerator * strings, PhysicalNetlist::PhysNetlist::RouteBranch::Builder source_branch, PipId root, - const std::unordered_map<PipId, PlaceStrength> &pip_place_strength, + const dict<PipId, PlaceStrength> &pip_place_strength, WireId *root_wire) { WireId source_wire = ctx->getPipSrcWire(root); BelPin source_bel_pin = find_source(ctx, source_wire); @@ -365,7 +365,7 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder init_local_source( } static void find_non_synthetic_edges(const Context * ctx, WireId root_wire, - const std::unordered_map<WireId, std::vector<PipId>> &pip_downhill, + const dict<WireId, std::vector<PipId>> &pip_downhill, std::vector<PipId> *root_pips) { std::vector<WireId> wires_to_expand; @@ -403,7 +403,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str phys_netlist.setPart(ctx->get_part()); - std::unordered_set<IdString> placed_cells; + pool<IdString> placed_cells; for(const auto & cell_pair : ctx->cells) { const CellInfo & cell = *cell_pair.second; if(cell.bel == BelId()) { @@ -444,7 +444,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str std::vector<IdString> ports; - std::unordered_map<std::string, std::string> sites; + dict<std::string, std::string> sites; auto placements = phys_netlist.initPlacements(number_placements); auto placement_iter = placements.begin(); @@ -556,9 +556,9 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str net_out.setName(strings.get_index(net.name.str(ctx))); } - std::unordered_map<WireId, BelPin> root_wires; - std::unordered_map<WireId, std::vector<PipId>> pip_downhill; - std::unordered_set<PipId> pips; + dict<WireId, BelPin> root_wires; + dict<WireId, std::vector<PipId>> pip_downhill; + pool<PipId> pips; if (driver_cell != nullptr && driver_cell->bel != BelId() && ctx->isBelLocationValid(driver_cell->bel)) { for(IdString bel_pin_name : driver_cell->cell_bel_pins.at(net.driver.port)) { @@ -573,7 +573,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str } } - std::unordered_map<WireId, std::vector<BelPin>> sinks; + dict<WireId, std::vector<BelPin>> sinks; for(const auto &port_ref : net.users) { if(port_ref.cell != nullptr && port_ref.cell->bel != BelId() && ctx->isBelLocationValid(port_ref.cell->bel)) { auto pin_iter = port_ref.cell->cell_bel_pins.find(port_ref.port); @@ -598,7 +598,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str } } - std::unordered_map<PipId, PlaceStrength> pip_place_strength; + dict<PipId, PlaceStrength> pip_place_strength; for(auto &wire_pair : net.wires) { WireId downhill_wire = wire_pair.first; @@ -723,23 +723,11 @@ struct PortKey { bool operator == (const PortKey &other) const { return inst_idx == other.inst_idx && port_idx == other.port_idx; } -}; - -NEXTPNR_NAMESPACE_END - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX PortKey> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX PortKey &key) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<int32_t>()(key.inst_idx)); - boost::hash_combine(seed, std::hash<uint32_t>()(key.port_idx)); - return seed; + unsigned int hash() const { + return mkhash(inst_idx, port_idx); } }; -NEXTPNR_NAMESPACE_BEGIN - struct ModuleReader { const LogicalNetlistImpl *root; @@ -748,9 +736,9 @@ struct ModuleReader { LogicalNetlist::Netlist::Cell::Reader cell; LogicalNetlist::Netlist::CellDeclaration::Reader cell_decl; - std::unordered_map<int32_t, LogicalNetlist::Netlist::Net::Reader> net_indicies; - std::unordered_map<int32_t, std::string> disconnected_nets; - std::unordered_map<PortKey, std::vector<int32_t>> connections; + dict<int32_t, LogicalNetlist::Netlist::Net::Reader> net_indicies; + dict<int32_t, std::string> disconnected_nets; + dict<PortKey, std::vector<int32_t>> connections; ModuleReader(const LogicalNetlistImpl *root, LogicalNetlist::Netlist::CellInstance::Reader cell_inst, bool is_top); @@ -834,7 +822,6 @@ struct LogicalNetlistImpl template <typename TFunc> void foreach_netname(const ModuleReader &mod, TFunc Func) const { - // std::unordered_map<int32_t, LogicalNetlist::Netlist::Net::Reader> net_indicies; for(auto net_pair : mod.net_indicies) { NetReader net_reader(&mod, net_pair.first); auto net = net_pair.second; @@ -842,7 +829,6 @@ struct LogicalNetlistImpl Func(strings.at(net.getName()), net_reader); } - // std::unordered_map<int32_t, IdString> disconnected_nets; for(auto net_pair : mod.disconnected_nets) { NetReader net_reader(&mod, net_pair.first); Func(net_pair.second, net_reader); diff --git a/fpga_interchange/globals.cc b/fpga_interchange/globals.cc index 918b916e..ed9f73a6 100644 --- a/fpga_interchange/globals.cc +++ b/fpga_interchange/globals.cc @@ -67,7 +67,7 @@ static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t p WireId startpoint; GlobalVist best_visit; std::queue<WireId> visit_queue; - std::unordered_map<WireId, GlobalVist> visits; + dict<WireId, GlobalVist> visits; visit_queue.push(dest); visits[dest].downhill = PipId(); diff --git a/fpga_interchange/lookahead.cc b/fpga_interchange/lookahead.cc index 6dc8c43a..f1cb13e1 100644 --- a/fpga_interchange/lookahead.cc +++ b/fpga_interchange/lookahead.cc @@ -64,9 +64,9 @@ struct PipAndCost int32_t depth; }; -static void expand_input(const Context *ctx, WireId input_wire, HashTables::HashMap<TypeWireId, delay_t> *input_costs) +static void expand_input(const Context *ctx, WireId input_wire, dict<TypeWireId, delay_t> *input_costs) { - HashTables::HashSet<WireId> seen; + pool<WireId> seen; std::priority_queue<RoutingNode> to_expand; RoutingNode initial; @@ -120,9 +120,8 @@ static void expand_input(const Context *ctx, WireId input_wire, HashTables::Hash } } -static void update_site_to_site_costs(const Context *ctx, WireId first_wire, - const HashTables::HashMap<WireId, PipAndCost> &best_path, - HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost) +static void update_site_to_site_costs(const Context *ctx, WireId first_wire, const dict<WireId, PipAndCost> &best_path, + dict<TypeWirePair, delay_t> *site_to_site_cost) { for (auto &best_pair : best_path) { WireId last_wire = best_pair.first; @@ -161,9 +160,9 @@ static void update_site_to_site_costs(const Context *ctx, WireId first_wire, } static void expand_output(const Context *ctx, WireId output_wire, Lookahead::OutputSiteWireCost *output_cost, - HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost) + dict<TypeWirePair, delay_t> *site_to_site_cost) { - HashTables::HashSet<WireId> seen; + pool<WireId> seen; std::priority_queue<RoutingNode> to_expand; RoutingNode initial; @@ -172,7 +171,7 @@ static void expand_output(const Context *ctx, WireId output_wire, Lookahead::Out to_expand.push(initial); - HashTables::HashMap<WireId, PipAndCost> best_path; + dict<WireId, PipAndCost> best_path; while (!to_expand.empty()) { RoutingNode node = to_expand.top(); @@ -228,7 +227,7 @@ static void expand_output(const Context *ctx, WireId output_wire, Lookahead::Out static void expand_input_type(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type, TypeWireId input_wire, std::vector<Lookahead::InputSiteWireCost> *input_costs) { - HashTables::HashMap<TypeWireId, delay_t> input_costs_map; + dict<TypeWireId, delay_t> input_costs_map; for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) { size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); }); @@ -250,7 +249,7 @@ static void expand_input_type(const Context *ctx, DeterministicRNG *rng, const S struct DelayStorage { - HashTables::HashMap<TypeWirePair, HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash>> storage; + dict<TypeWirePair, dict<std::pair<int32_t, int32_t>, delay_t>> storage; int32_t max_explore_depth; }; @@ -290,7 +289,7 @@ static void update_results(const Context *ctx, const FlatWireMap<PipAndCost> &be // Starting from end of result, walk backwards and record the path into // the delay storage. WireId cursor = sink_wire; - HashTables::HashSet<WireId> seen; + pool<WireId> seen; while (cursor != src_wire) { // No loops allowed in routing! auto result = seen.emplace(cursor); @@ -335,7 +334,7 @@ static void update_results(const Context *ctx, const FlatWireMap<PipAndCost> &be static void expand_routing_graph_from_wire(const Context *ctx, WireId first_wire, FlatWireMap<PipAndCost> *best_path, DelayStorage *storage) { - HashTables::HashSet<WireId> seen; + pool<WireId> seen; std::priority_queue<RoutingNode> to_expand; int src_tile; @@ -436,11 +435,10 @@ static bool has_multiple_outputs(const Context *ctx, WireId wire) } static void expand_routing_graph(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type, - TypeWireId wire_type, HashTables::HashSet<TypeWireSet> *types_explored, - DelayStorage *storage, HashTables::HashSet<TypeWireId> *types_deferred, - FlatWireMap<PipAndCost> *best_path) + TypeWireId wire_type, pool<TypeWireSet> *types_explored, DelayStorage *storage, + pool<TypeWireId> *types_deferred, FlatWireMap<PipAndCost> *best_path) { - HashTables::HashSet<TypeWireSet> new_types_explored; + pool<TypeWireSet> new_types_explored; for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) { size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); }); @@ -562,10 +560,10 @@ static WireId follow_pip_chain_up(const Context *ctx, WireId wire, delay_t *dela } static void expand_deferred_routing_graph(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type, - TypeWireId wire_type, HashTables::HashSet<TypeWireSet> *types_explored, + TypeWireId wire_type, pool<TypeWireSet> *types_explored, DelayStorage *storage, FlatWireMap<PipAndCost> *best_path) { - HashTables::HashSet<TypeWireSet> new_types_explored; + pool<TypeWireSet> new_types_explored; for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) { size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); }); @@ -603,7 +601,7 @@ static void expand_deferred_routing_graph(const Context *ctx, DeterministicRNG * static void expand_output_type(const Context *ctx, DeterministicRNG *rng, const Sampler &tiles_of_type, TypeWireId output_wire, Lookahead::OutputSiteWireCost *output_cost, - HashTables::HashMap<TypeWirePair, delay_t> *site_to_site_cost) + dict<TypeWirePair, delay_t> *site_to_site_cost) { for (size_t region = 0; region < tiles_of_type.number_of_regions(); ++region) { size_t tile = tiles_of_type.get_sample_from_region(region, [rng]() -> int32_t { return rng->rng(); }); @@ -651,8 +649,8 @@ struct ExpandLocals DeterministicRNG *rng; FlatWireMap<PipAndCost> *best_path; DelayStorage *storage; - HashTables::HashSet<TypeWireSet> *explored; - HashTables::HashSet<TypeWireId> *deferred; + pool<TypeWireSet> *explored; + pool<TypeWireId> *deferred; virtual void lock() {} virtual void unlock() {} @@ -698,8 +696,7 @@ static void expand_tile_type(const Context *ctx, int32_t tile_type, ExpandLocals static void expand_tile_type_serial(const Context *ctx, const std::vector<int32_t> &tile_types, const std::vector<Sampler> &tiles_of_type, DeterministicRNG *rng, FlatWireMap<PipAndCost> *best_path, DelayStorage *storage, - HashTables::HashSet<TypeWireSet> *explored, - HashTables::HashSet<TypeWireId> *deferred, HashTables::HashSet<int32_t> *tiles_left) + pool<TypeWireSet> *explored, pool<TypeWireId> *deferred, pool<int32_t> *tiles_left) { for (int32_t tile_type : tile_types) { @@ -725,9 +722,9 @@ struct TbbExpandLocals : public ExpandLocals std::mutex *all_costs_mutex; DelayStorage *all_tiles_storage; - HashTables::HashSet<TypeWireSet> *types_explored; - HashTables::HashSet<TypeWireId> *types_deferred; - HashTables::HashSet<int32_t> *tiles_left; + pool<TypeWireSet> *types_explored; + pool<TypeWireId> *types_deferred; + pool<int32_t> *tiles_left; void lock() override { all_costs_mutex->lock(); } @@ -785,16 +782,15 @@ struct TbbExpandLocals : public ExpandLocals // the data is joined with the global data. static void expand_tile_type_parallel(const Context *ctx, int32_t tile_type, const std::vector<Sampler> &tiles_of_type, DeterministicRNG *rng, std::mutex *all_costs_mutex, - DelayStorage *all_tiles_storage, HashTables::HashSet<TypeWireSet> *types_explored, - HashTables::HashSet<TypeWireId> *types_deferred, - HashTables::HashSet<int32_t> *tiles_left) + DelayStorage *all_tiles_storage, pool<TypeWireSet> *types_explored, + pool<TypeWireId> *types_deferred, pool<int32_t> *tiles_left) { TbbExpandLocals locals; DeterministicRNG rng_copy = *rng; FlatWireMap<PipAndCost> best_path(ctx); - HashTables::HashSet<TypeWireSet> explored; - HashTables::HashSet<TypeWireId> deferred; + pool<TypeWireSet> explored; + pool<TypeWireId> deferred; DelayStorage storage; storage.max_explore_depth = all_tiles_storage->max_explore_depth; @@ -823,7 +819,7 @@ void Lookahead::build_lookahead(const Context *ctx, DeterministicRNG *rng) log_info("Building lookahead, first gathering input and output site wires\n"); } - HashTables::HashSet<TypeWireId> input_site_ports; + pool<TypeWireId> input_site_ports; for (BelId bel : ctx->getBels()) { const auto &bel_data = bel_info(ctx->chip_info, bel); @@ -917,15 +913,15 @@ void Lookahead::build_lookahead(const Context *ctx, DeterministicRNG *rng) all_tiles_storage.max_explore_depth = kInitialExploreDepth; // These are wire types that have been explored. - HashTables::HashSet<TypeWireSet> types_explored; + pool<TypeWireSet> types_explored; // These are wire types that have been deferred because they are trival // copies of another wire type. These can be cheaply computed after the // graph has been explored. - HashTables::HashSet<TypeWireId> types_deferred; + pool<TypeWireId> types_deferred; std::vector<int32_t> tile_types; - HashTables::HashSet<int32_t> tiles_left; + pool<int32_t> tiles_left; tile_types.reserve(ctx->chip_info->tile_types.size()); for (int32_t tile_type = 0; tile_type < ctx->chip_info->tile_types.ssize(); ++tile_type) { tile_types.push_back(tile_type); @@ -994,16 +990,14 @@ void Lookahead::build_lookahead(const Context *ctx, DeterministicRNG *rng) } #if defined(NEXTPNR_USE_TBB) // Run parallely - tbb::parallel_for_each( - all_tiles_storage.storage, - [&](const std::pair<TypeWirePair, HashTables::HashMap<std::pair<int32_t, int32_t>, delay_t, PairHash>> - &type_pair) { + tbb::parallel_for_each(all_tiles_storage.storage, + [&](const std::pair<TypeWirePair, dict<std::pair<int32_t, int32_t>, delay_t>> &type_pair) { #else for (const auto &type_pair : all_tiles_storage.storage) { #endif - cost_map.set_cost_map(ctx, type_pair.first, type_pair.second); + cost_map.set_cost_map(ctx, type_pair.first, type_pair.second); #if defined(NEXTPNR_USE_TBB) // Run parallely - }); + }); #else } #endif diff --git a/fpga_interchange/lookahead.h b/fpga_interchange/lookahead.h index b9d352d5..9655e13e 100644 --- a/fpga_interchange/lookahead.h +++ b/fpga_interchange/lookahead.h @@ -26,7 +26,6 @@ #include "cost_map.h" #include "deterministic_rng.h" -#include "hash_table.h" #include "lookahead.capnp.h" #include "nextpnr_namespaces.h" #include "type_wire.h" @@ -88,9 +87,9 @@ struct Lookahead delay_t cost; }; - HashTables::HashMap<TypeWireId, std::vector<InputSiteWireCost>> input_site_wires; - HashTables::HashMap<TypeWireId, OutputSiteWireCost> output_site_wires; - HashTables::HashMap<TypeWirePair, delay_t> site_to_site_cost; + dict<TypeWireId, std::vector<InputSiteWireCost>> input_site_wires; + dict<TypeWireId, OutputSiteWireCost> output_site_wires; + dict<TypeWirePair, delay_t> site_to_site_cost; CostMap cost_map; }; diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc index 882cc474..0156d379 100644 --- a/fpga_interchange/luts.cc +++ b/fpga_interchange/luts.cc @@ -166,13 +166,13 @@ uint32_t LutMapper::check_wires(const Context *ctx) const } } - HashTables::HashSet<const LutBel *> blocked_luts; + pool<const LutBel *, hash_ptr_ops> blocked_luts; return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, &blocked_luts); } uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_cell_pin_remaps, const std::vector<const LutBel *> &lut_bels, uint32_t used_pins, - HashTables::HashSet<const LutBel *> *blocked_luts) const + pool<const LutBel *, hash_ptr_ops> *blocked_luts) const { std::vector<const LutBel *> unused_luts; for (auto &lut_bel_pair : element.lut_bels) { @@ -253,9 +253,9 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_ return vcc_mask; } -bool LutMapper::remap_luts(const Context *ctx, HashTables::HashSet<const LutBel *> *blocked_luts) +bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts) { - std::unordered_map<NetInfo *, LutPin> lut_pin_map; + dict<NetInfo *, LutPin, hash_ptr_ops> lut_pin_map; std::vector<const LutBel *> lut_bels; lut_bels.resize(cells.size()); @@ -366,7 +366,7 @@ bool LutMapper::remap_luts(const Context *ctx, HashTables::HashSet<const LutBel CellInfo *cell = cells[cell_idx]; auto &lut_bel = *lut_bels[cell_idx]; - std::unordered_map<IdString, IdString> cell_to_bel_map; + dict<IdString, IdString> cell_to_bel_map; for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) { size_t bel_pin_idx = cell_to_bel_pin_remaps[cell_idx][pin_idx]; NPNR_ASSERT(bel_pin_idx < lut_bel.pins.size()); @@ -452,8 +452,8 @@ bool LutMapper::remap_luts(const Context *ctx, HashTables::HashSet<const LutBel return true; } -void check_equation(const LutCell &lut_cell, const std::unordered_map<IdString, IdString> &cell_to_bel_map, - const LutBel &lut_bel, const std::vector<LogicLevel> &equation, uint32_t used_pins) +void check_equation(const LutCell &lut_cell, const dict<IdString, IdString> &cell_to_bel_map, const LutBel &lut_bel, + const std::vector<LogicLevel> &equation, uint32_t used_pins) { std::vector<int8_t> pin_map; pin_map.resize(lut_bel.pins.size(), -1); diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h index df0ac124..cbb817c9 100644 --- a/fpga_interchange/luts.h +++ b/fpga_interchange/luts.h @@ -20,14 +20,11 @@ #ifndef LUTS_H #define LUTS_H -#include <unordered_map> -#include <unordered_set> - #include "idstring.h" #include "nextpnr_namespaces.h" #include "dynamic_bitarray.h" -#include "hash_table.h" +#include "hashlib.h" NEXTPNR_NAMESPACE_BEGIN @@ -45,8 +42,8 @@ struct LutCell { // LUT cell pins for equation, LSB first. std::vector<IdString> pins; - std::unordered_set<IdString> lut_pins; - std::unordered_set<IdString> vcc_pins; + pool<IdString> lut_pins; + pool<IdString> vcc_pins; DynamicBitarray<> equation; }; @@ -56,7 +53,7 @@ struct LutBel // LUT BEL pins to LUT array index. std::vector<IdString> pins; - std::unordered_map<IdString, size_t> pin_to_index; + dict<IdString, size_t> pin_to_index; IdString output_pin; @@ -71,18 +68,18 @@ struct LutBel // Work forward from cell definition and cell -> bel pin map and check that // equation is valid. -void check_equation(const LutCell &lut_cell, const std::unordered_map<IdString, IdString> &cell_to_bel_map, - const LutBel &lut_bel, const std::vector<LogicLevel> &equation, uint32_t used_pins); +void check_equation(const LutCell &lut_cell, const dict<IdString, IdString> &cell_to_bel_map, const LutBel &lut_bel, + const std::vector<LogicLevel> &equation, uint32_t used_pins); struct LutElement { size_t width; - std::unordered_map<IdString, LutBel> lut_bels; + dict<IdString, LutBel> lut_bels; void compute_pin_order(); std::vector<IdString> pins; - std::unordered_map<IdString, size_t> pin_to_index; + dict<IdString, size_t> pin_to_index; }; struct LutMapper @@ -92,7 +89,7 @@ struct LutMapper std::vector<CellInfo *> cells; - bool remap_luts(const Context *ctx, HashTables::HashSet<const LutBel *> *blocked_luts); + bool remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts); // Determine which wires given the current mapping must be tied to the // default constant. @@ -101,7 +98,7 @@ struct LutMapper // the pin is free to be a signal. uint32_t check_wires(const std::vector<std::vector<int32_t>> &bel_to_cell_pin_remaps, const std::vector<const LutBel *> &lut_bels, uint32_t used_pins, - HashTables::HashSet<const LutBel *> *blocked_luts) const; + pool<const LutBel *, hash_ptr_ops> *blocked_luts) const; // Version of check_wires that uses current state of cells based on pin // mapping in cells variable. diff --git a/fpga_interchange/pseudo_pip_model.cc b/fpga_interchange/pseudo_pip_model.cc index 64da4548..2441c8a9 100644 --- a/fpga_interchange/pseudo_pip_model.cc +++ b/fpga_interchange/pseudo_pip_model.cc @@ -44,7 +44,7 @@ void PseudoPipData::init_tile_type(const Context *ctx, int32_t tile_type) max_pseudo_pip_index = pip_idx; } - HashTables::HashSet<size_t> sites; + pool<size_t> sites; std::vector<PseudoPipBel> pseudo_pip_bels; for (int32_t wire_index : pip_data.pseudo_cell_wires) { const TileWireInfoPOD &wire_data = type_data.wire_data[wire_index]; @@ -122,7 +122,7 @@ void PseudoPipData::init_tile_type(const Context *ctx, int32_t tile_type) } if (!pseudo_pip_bels.empty()) { - HashTables::HashSet<int32_t> pseudo_cell_wires; + pool<int32_t> pseudo_cell_wires; pseudo_cell_wires.insert(pip_data.pseudo_cell_wires.begin(), pip_data.pseudo_cell_wires.end()); // For each BEL, find the input bel pin used, and attach it to @@ -195,7 +195,7 @@ void PseudoPipModel::prepare_for_routing(const Context *ctx, const std::vector<S { // First determine which sites have placed cells, these sites are consider // active. - HashTables::HashSet<size_t> active_sites; + pool<size_t> active_sites; for (size_t site = 0; site < sites.size(); ++site) { if (!sites[site].cells_in_site.empty()) { active_sites.emplace(site); @@ -309,7 +309,7 @@ void PseudoPipModel::update_site(const Context *ctx, size_t site) unused_pseudo_pips.clear(); unused_pseudo_pips.reserve(pseudo_pips_for_site.size()); - HashTables::HashMap<int32_t, PseudoPipBel> used_bels; + dict<int32_t, PseudoPipBel> used_bels; for (int32_t pseudo_pip : pseudo_pips_for_site) { if (!active_pseudo_pips.count(pseudo_pip)) { unused_pseudo_pips.push_back(pseudo_pip); diff --git a/fpga_interchange/pseudo_pip_model.h b/fpga_interchange/pseudo_pip_model.h index 1e79071d..b0e28059 100644 --- a/fpga_interchange/pseudo_pip_model.h +++ b/fpga_interchange/pseudo_pip_model.h @@ -24,7 +24,6 @@ #include <tuple> #include "dynamic_bitarray.h" -#include "hash_table.h" #include "nextpnr_namespaces.h" #include "nextpnr_types.h" #include "site_router.h" @@ -58,28 +57,10 @@ struct LogicBelKey bool operator==(const LogicBelKey &other) const { return make_tuple() == other.make_tuple(); } bool operator<(const LogicBelKey &other) const { return make_tuple() < other.make_tuple(); } -}; - -NEXTPNR_NAMESPACE_END -namespace std { -template <> struct hash<NEXTPNR_NAMESPACE_PREFIX LogicBelKey> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX LogicBelKey &key) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, hash<int32_t>()(key.tile_type)); - boost::hash_combine(seed, hash<int32_t>()(key.pip_index)); - boost::hash_combine(seed, hash<int32_t>()(key.site)); - - return seed; - } + unsigned int hash() const { return mkhash(mkhash(tile_type, pip_index), site); } }; -}; // namespace std - -NEXTPNR_NAMESPACE_BEGIN - // Storage for tile type generic pseudo pip data and lookup. struct PseudoPipData { @@ -97,9 +78,9 @@ struct PseudoPipData // This does **not** include site ports or site pips. const std::vector<PseudoPipBel> &get_logic_bels_for_pip(const Context *ctx, int32_t site, PipId pip) const; - HashTables::HashMap<int32_t, size_t> max_pseudo_pip_for_tile_type; - HashTables::HashMap<std::pair<int32_t, int32_t>, std::vector<size_t>, PairHash> possibles_sites_for_pip; - HashTables::HashMap<LogicBelKey, std::vector<PseudoPipBel>> logic_bels_for_pip; + dict<int32_t, size_t> max_pseudo_pip_for_tile_type; + dict<std::pair<int32_t, int32_t>, std::vector<size_t>> possibles_sites_for_pip; + dict<LogicBelKey, std::vector<PseudoPipBel>> logic_bels_for_pip; }; // Tile instance fast pseudo pip lookup. @@ -107,9 +88,9 @@ struct PseudoPipModel { int32_t tile; DynamicBitarray<> allowed_pseudo_pips; - HashTables::HashMap<int32_t, size_t> pseudo_pip_sites; - HashTables::HashMap<size_t, std::vector<int32_t>> site_to_pseudo_pips; - HashTables::HashSet<int32_t> active_pseudo_pips; + dict<int32_t, size_t> pseudo_pip_sites; + dict<size_t, std::vector<int32_t>> site_to_pseudo_pips; + pool<int32_t> active_pseudo_pips; std::vector<int32_t> scratch; // Call when a tile is initialized. diff --git a/fpga_interchange/site_arch.cc b/fpga_interchange/site_arch.cc index ed2f6c8d..6398d858 100644 --- a/fpga_interchange/site_arch.cc +++ b/fpga_interchange/site_arch.cc @@ -24,7 +24,7 @@ NEXTPNR_NAMESPACE_BEGIN SiteInformation::SiteInformation(const Context *ctx, int32_t tile, int32_t site, - const std::unordered_set<CellInfo *> &cells_in_site) + const pool<CellInfo *, hash_ptr_ops> &cells_in_site) : ctx(ctx), tile(tile), tile_type(ctx->chip_info->tiles[tile].type), site(site), cells_in_site(cells_in_site) { } diff --git a/fpga_interchange/site_arch.h b/fpga_interchange/site_arch.h index a7da5c68..54b91a4a 100644 --- a/fpga_interchange/site_arch.h +++ b/fpga_interchange/site_arch.h @@ -22,13 +22,12 @@ #define SITE_ARCH_H #include <cstdint> -#include <unordered_set> #include <vector> #include "PhysicalNetlist.capnp.h" #include "arch_iterators.h" #include "chipdb.h" -#include "hash_table.h" +#include "hashlib.h" #include "log.h" #include "nextpnr_namespaces.h" #include "nextpnr_types.h" @@ -44,10 +43,10 @@ struct SiteInformation const int32_t tile; const int32_t tile_type; const int32_t site; - const std::unordered_set<CellInfo *> &cells_in_site; + const pool<CellInfo *, hash_ptr_ops> &cells_in_site; SiteInformation(const Context *ctx, int32_t tile, int32_t site, - const std::unordered_set<CellInfo *> &cells_in_site); + const pool<CellInfo *, hash_ptr_ops> &cells_in_site); inline const ChipInfoPOD &chip_info() const NPNR_ALWAYS_INLINE; @@ -143,6 +142,7 @@ struct SiteWire WireId wire; PipId pip; NetInfo *net = nullptr; + unsigned int hash() const { return mkhash(mkhash(int(type), wire.hash()), mkhash(pip.hash(), uintptr_t(net))); } }; struct SitePip @@ -214,36 +214,8 @@ struct SitePip { return type != other.type || pip != other.pip || wire != other.wire || other_pip != other.other_pip; } + unsigned int hash() const { return mkhash(mkhash(int(type), pip.hash()), mkhash(wire.hash(), other_pip.hash())); } }; -NEXTPNR_NAMESPACE_END - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SiteWire &site_wire) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(site_wire.type)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX WireId>()(site_wire.wire)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_wire.pip)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX NetInfo *>()(site_wire.net)); - return seed; - } -}; - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SitePip> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SitePip &site_pip) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SitePip::Type>()(site_pip.type)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_pip.pip)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire>()(site_pip.wire)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_pip.other_pip)); - return seed; - } -}; - -NEXTPNR_NAMESPACE_BEGIN struct SitePipDownhillRange; struct SitePipUphillRange; @@ -266,9 +238,9 @@ struct SiteNetInfo { NetInfo *net; SiteWire driver; - HashTables::HashSet<SiteWire> users; + pool<SiteWire> users; - HashTables::HashMap<SiteWire, SitePipMap> wires; + dict<SiteWire, SitePipMap> wires; }; struct SiteArch @@ -276,8 +248,8 @@ struct SiteArch const Context *const ctx; const SiteInformation *const site_info; - HashTables::HashMap<NetInfo *, SiteNetInfo> nets; - HashTables::HashMap<SiteWire, SiteNetMap> wire_to_nets; + dict<NetInfo *, SiteNetInfo, hash_ptr_ops> nets; + dict<SiteWire, SiteNetMap> wire_to_nets; NetInfo blocking_net; SiteNetInfo blocking_site_net; diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 69bd366f..090b9342 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -21,7 +21,6 @@ #include "design_utils.h" #include "dynamic_bitarray.h" -#include "hash_table.h" #include "log.h" #include "site_routing_cache.h" @@ -53,7 +52,7 @@ bool check_initial_wires(const Context *ctx, SiteInformation *site_info) { // Propagate from BEL pins to first wire, checking for trivial routing // conflicts. - HashTables::HashMap<WireId, NetInfo *> wires; + dict<WireId, NetInfo *> wires; for (CellInfo *cell : site_info->cells_in_site) { BelId bel = cell->bel; @@ -132,7 +131,7 @@ struct SiteExpansionLoop bool expand_result; SiteWire net_driver; - HashTables::HashSet<SiteWire> net_users; + pool<SiteWire> net_users; SiteRoutingSolution solution; @@ -206,7 +205,7 @@ struct SiteExpansionLoop auto node = new_node(net->driver, SitePip(), /*parent=*/nullptr); - HashTables::HashSet<SiteWire> targets; + pool<SiteWire> targets; targets.insert(net->users.begin(), net->users.end()); if (verbose_site_router(ctx)) { @@ -722,7 +721,7 @@ static bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, Rout // Create a flat sink list and map. std::vector<SiteWire> sinks; - HashTables::HashMap<SiteWire, size_t> sink_map; + dict<SiteWire, size_t> sink_map; size_t number_solutions = 0; for (const auto *expansion : expansions) { number_solutions += expansion->num_solutions(); @@ -963,8 +962,7 @@ static void apply_constant_routing(Context *ctx, const SiteArch &site_arch, NetI } } -static void apply_routing(Context *ctx, const SiteArch &site_arch, - HashTables::HashSet<std::pair<IdString, int32_t>, PairHash> &lut_thrus) +static void apply_routing(Context *ctx, const SiteArch &site_arch, pool<std::pair<IdString, int32_t>> &lut_thrus) { IdString gnd_net_name(ctx->chip_info->constants->gnd_net_name); NetInfo *gnd_net = ctx->nets.at(gnd_net_name).get(); @@ -1019,8 +1017,7 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch, } } -static bool map_luts_in_site(const SiteInformation &site_info, - HashTables::HashSet<std::pair<IdString, IdString>, PairHash> *blocked_wires) +static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<IdString, IdString>> *blocked_wires) { const Context *ctx = site_info.ctx; const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type); @@ -1048,7 +1045,7 @@ static bool map_luts_in_site(const SiteInformation &site_info, continue; } - HashTables::HashSet<const LutBel *> blocked_luts; + pool<const LutBel *, hash_ptr_ops> blocked_luts; if (!lut_mapper.remap_luts(ctx, &blocked_luts)) { return false; } @@ -1062,8 +1059,7 @@ static bool map_luts_in_site(const SiteInformation &site_info, } // Block outputs of unavailable LUTs to prevent site router from using them. -static void block_lut_outputs(SiteArch *site_arch, - const HashTables::HashSet<std::pair<IdString, IdString>, PairHash> &blocked_wires) +static void block_lut_outputs(SiteArch *site_arch, const pool<std::pair<IdString, IdString>> &blocked_wires) { const Context *ctx = site_arch->site_info->ctx; auto &tile_info = ctx->chip_info->tile_types[site_arch->site_info->tile_type]; @@ -1185,7 +1181,7 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta } SiteInformation site_info(ctx, tile, site, cells_in_site); - HashTables::HashSet<std::pair<IdString, IdString>, PairHash> blocked_wires; + pool<std::pair<IdString, IdString>> blocked_wires; if (!map_luts_in_site(site_info, &blocked_wires)) { site_ok = false; return site_ok; @@ -1263,7 +1259,7 @@ void SiteRouter::bindSiteRouting(Context *ctx) } SiteInformation site_info(ctx, tile, site, cells_in_site); - HashTables::HashSet<std::pair<IdString, IdString>, PairHash> blocked_wires; + pool<std::pair<IdString, IdString>> blocked_wires; NPNR_ASSERT(map_luts_in_site(site_info, &blocked_wires)); SiteArch site_arch(&site_info); diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h index 0328b6b2..ad1cbf66 100644 --- a/fpga_interchange/site_router.h +++ b/fpga_interchange/site_router.h @@ -23,6 +23,7 @@ #include <cstdint> +#include "hashlib.h" #include "nextpnr_namespaces.h" #include "nextpnr_types.h" #include "site_arch.h" @@ -37,9 +38,9 @@ struct SiteRouter { SiteRouter(int16_t site) : site(site), dirty(false), site_ok(true) {} - std::unordered_set<CellInfo *> cells_in_site; + pool<CellInfo *, hash_ptr_ops> cells_in_site; std::vector<PipId> valid_pips; - HashTables::HashSet<std::pair<IdString, int32_t>, PairHash> lut_thrus; + pool<std::pair<IdString, int32_t>> lut_thrus; const int16_t site; mutable bool dirty; diff --git a/fpga_interchange/site_routing_cache.cc b/fpga_interchange/site_routing_cache.cc index e6f4dc70..512ca2ac 100644 --- a/fpga_interchange/site_routing_cache.cc +++ b/fpga_interchange/site_routing_cache.cc @@ -70,7 +70,7 @@ void SiteRoutingSolution::store_solution(const SiteArch *ctx, const RouteNodeSto void SiteRoutingSolution::verify(const SiteArch *ctx, const SiteNetInfo &net) { - HashTables::HashSet<SiteWire> seen_users; + pool<SiteWire> seen_users; for (size_t i = 0; i < num_solutions(); ++i) { SiteWire cursor = solution_sink(i); NPNR_ASSERT(net.users.count(cursor) == 1); diff --git a/fpga_interchange/site_routing_cache.h b/fpga_interchange/site_routing_cache.h index 6ad218c7..b4baf65a 100644 --- a/fpga_interchange/site_routing_cache.h +++ b/fpga_interchange/site_routing_cache.h @@ -22,7 +22,6 @@ #define SITE_ROUTING_CACHE_H #include "PhysicalNetlist.capnp.h" -#include "hash_table.h" #include "nextpnr_namespaces.h" #include "site_arch.h" #include "site_routing_storage.h" @@ -97,35 +96,25 @@ struct SiteRoutingKey } static SiteRoutingKey make(const SiteArch *ctx, const SiteNetInfo &site_net); -}; - -NEXTPNR_NAMESPACE_END -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SiteRoutingKey> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SiteRoutingKey &key) const noexcept + unsigned int hash() const { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<int32_t>()(key.tile_type)); - boost::hash_combine(seed, std::hash<int32_t>()(key.site)); - boost::hash_combine(seed, std::hash<PhysicalNetlist::PhysNetlist::NetType>()(key.net_type)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(key.driver_type)); - boost::hash_combine(seed, std::hash<int32_t>()(key.driver_index)); - boost::hash_combine(seed, std::hash<std::size_t>()(key.user_types.size())); - for (NEXTPNR_NAMESPACE_PREFIX SiteWire::Type user_type : key.user_types) { - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(user_type)); - } - - boost::hash_combine(seed, std::hash<std::size_t>()(key.user_indicies.size())); - for (int32_t index : key.user_indicies) { - boost::hash_combine(seed, std::hash<int32_t>()(index)); - } + unsigned int seed = 0; + seed = mkhash(seed, tile_type); + seed = mkhash(seed, site); + seed = mkhash(seed, int(net_type)); + seed = mkhash(seed, int(driver_type)); + seed = mkhash(seed, driver_index); + seed = mkhash(seed, user_types.size()); + for (auto t : user_types) + seed = mkhash(seed, int(t)); + seed = mkhash(seed, user_indicies.size()); + for (auto i : user_indicies) + seed = mkhash(seed, i); return seed; } }; -NEXTPNR_NAMESPACE_BEGIN - // Provides an LRU cache for site routing solutions. class SiteRoutingCache { @@ -134,7 +123,7 @@ class SiteRoutingCache void add_solutions(const SiteArch *ctx, const SiteNetInfo &net, const SiteRoutingSolution &solution); private: - HashTables::HashMap<SiteRoutingKey, SiteRoutingSolution> cache_; + dict<SiteRoutingKey, SiteRoutingSolution> cache_; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/type_wire.cc b/fpga_interchange/type_wire.cc index a08e024b..d1bdaed0 100644 --- a/fpga_interchange/type_wire.cc +++ b/fpga_interchange/type_wire.cc @@ -54,10 +54,9 @@ TypeWireSet::TypeWireSet(const Context *ctx, WireId wire) std::sort(wire_types_.begin(), wire_types_.end()); - hash_ = 0; - boost::hash_combine(hash_, std::hash<size_t>()(wire_types_.size())); + hash_ = wire_types_.size(); for (const auto &wire : wire_types_) { - boost::hash_combine(hash_, std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWireId>()(wire)); + hash_ = mkhash(hash_, wire.hash()); } } diff --git a/fpga_interchange/type_wire.h b/fpga_interchange/type_wire.h index f2a675ef..a472bccc 100644 --- a/fpga_interchange/type_wire.h +++ b/fpga_interchange/type_wire.h @@ -24,6 +24,7 @@ #include <algorithm> #include <vector> +#include "hashlib.h" #include "nextpnr_namespaces.h" #include "nextpnr_types.h" @@ -48,6 +49,8 @@ struct TypeWireId return type < other.type || (type == other.type && index < other.index); } + unsigned int hash() const { return mkhash(type, index); } + int32_t type; int32_t index; }; @@ -63,49 +66,24 @@ struct TypeWirePair bool operator==(const TypeWirePair &other) const { return src == other.src && dst == other.dst; } bool operator!=(const TypeWirePair &other) const { return src != other.src || dst != other.dst; } + + unsigned int hash() const { return mkhash(src.hash(), dst.hash()); } }; struct TypeWireSet { public: TypeWireSet(const Context *ctx, WireId wire); - std::size_t hash() const { return hash_; } + unsigned int hash() const { return hash_; } bool operator==(const TypeWireSet &other) const { return wire_types_ == other.wire_types_; } bool operator!=(const TypeWireSet &other) const { return wire_types_ != other.wire_types_; } private: - std::size_t hash_; + unsigned int hash_; std::vector<TypeWireId> wire_types_; }; NEXTPNR_NAMESPACE_END -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWireId> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TypeWireId &wire) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<int>()(wire.type)); - boost::hash_combine(seed, std::hash<int>()(wire.index)); - return seed; - } -}; - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWirePair> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TypeWirePair &pair) const noexcept - { - std::size_t seed = 0; - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWireId>()(pair.src)); - boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWireId>()(pair.dst)); - return seed; - } -}; - -template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX TypeWireSet> -{ - std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TypeWireSet &set) const noexcept { return set.hash(); } -}; - #endif /* TYPE_WIRE_H */ |