From 43b8dde923b8cf57a206526fd6e66ebf1c436010 Mon Sep 17 00:00:00 2001 From: gatecat Date: Tue, 1 Jun 2021 17:52:25 +0100 Subject: Use hashlib in placers Signed-off-by: gatecat --- common/fast_bels.h | 4 ++-- common/nextpnr_base_types.h | 1 + common/place_common.cc | 10 +++++----- common/placer1.cc | 20 +++++++++---------- common/placer_heap.cc | 47 ++++++++++++++++++++++----------------------- common/placer_heap.h | 4 ++-- 6 files changed, 43 insertions(+), 43 deletions(-) (limited to 'common') 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 cell_types; + dict cell_types; std::vector> fast_bels_by_cell_type; - std::unordered_map partition_types; + dict partition_types; std::vector> 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 rippedCells; - std::unordered_map oldLocations; - std::unordered_map> cluster2cells; + dict oldLocations; + dict> cluster2cells; class IncreasingDiameterSearch { @@ -227,10 +227,10 @@ class ConstraintLegaliseWorker int sign = 0; }; - typedef std::unordered_map CellLocations; + typedef dict 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 &usedLocations) + bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, pool &usedLocations) { BelId locBel = ctx->getBelByLocation(loc); if (locBel == BelId()) @@ -324,7 +324,7 @@ class ConstraintLegaliseWorker } CellLocations solution; - std::unordered_set used; + pool 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 cell_types_in_use; + pool 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> cell_rel; - std::unordered_set cells; + pool cells; std::vector> moves_made; std::vector> 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>> nets_by_tile; + std::vector>> nets_by_tile; void setup_nets_by_tile() { total_net_share = 0; - nets_by_tile.resize(max_x + 1, std::vector>(max_y + 1)); + nets_by_tile.resize(max_x + 1, std::vector>(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> net_arc_tcost; // Fast lookup for cell port to net user index - std::unordered_map fast_port_to_user; + dict, 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> bel_types; - std::unordered_map region_bounds; + dict> bel_types; + dict region_bounds; FastBels fast_bels; - std::unordered_set locked_bels; + pool locked_bels; std::vector net_by_udata; std::vector 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 #include #include -#include #include "fast_bels.h" #include "log.h" #include "nextpnr.h" @@ -188,14 +187,14 @@ class HeAPPlacer std::vector> solution; - std::vector> heap_runs; - std::unordered_set all_buckets; - std::unordered_map bucket_count; + std::vector> heap_runs; + pool all_buckets; + dict 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{bucket}); + heap_runs.push_back(pool{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 &grp) { return !grp.count(type); })) + [type](const pool &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> bel_types; + dict> bel_types; TimingAnalyser tmg; @@ -370,7 +369,7 @@ class HeAPPlacer int x0 = 0, x1 = 0, y0 = 0, y1 = 0; }; - std::unordered_map constraint_region_bounds; + dict 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 cell_locs; + dict 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 place_cells; @@ -390,8 +389,8 @@ class HeAPPlacer // cells of a certain type) std::vector solve_cells; - std::unordered_map> cluster2cells; - std::unordered_map chain_size; + dict> cluster2cells; + dict 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 cell_types_in_use; - std::unordered_set buckets_in_use; + pool cell_types_in_use; + pool 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 cell_types; + pool cell_types; for (const auto &cell : ctx->cells) { cell_types.insert(cell.second->type); } - std::unordered_set bels_used; - std::unordered_map> available_bels; + pool bels_used; + dict> 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 *buckets = nullptr) + int setup_solve_cells(pool *buckets = nullptr) { int row = 0; solve_cells.clear(); @@ -1106,11 +1105,11 @@ class HeAPPlacer class CutSpreader { public: - CutSpreader(HeAPPlacer *p, const std::unordered_set &buckets) : p(p), ctx(p->ctx), buckets(buckets) + CutSpreader(HeAPPlacer *p, const pool &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 buckets; - std::unordered_map type_index; + pool buckets; + dict type_index; std::vector>> occupancy; std::vector> groups; std::vector> chaines; @@ -1208,7 +1207,7 @@ class HeAPPlacer std::vector>> *> fb; std::vector regions; - std::unordered_set merged_regions; + pool merged_regions; // Cells at a location, sorted by real (not integer) x and y std::vector>> 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 ioBufTypes; + pool ioBufTypes; // These cell types are part of the same unit (e.g. slices split into // components) so will always be spread together - std::vector> cellGroups; + std::vector> cellGroups; }; extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg); -- cgit v1.2.3