diff options
Diffstat (limited to 'common')
| -rw-r--r-- | common/arch_pybindings_shared.h | 16 | ||||
| -rw-r--r-- | common/archcheck.cc | 64 | ||||
| -rw-r--r-- | common/fast_bels.h | 184 | ||||
| -rw-r--r-- | common/place_common.cc | 5 | ||||
| -rw-r--r-- | common/placer1.cc | 59 | ||||
| -rw-r--r-- | common/placer_heap.cc | 358 | ||||
| -rw-r--r-- | common/placer_heap.h | 2 | ||||
| -rw-r--r-- | common/timing_opt.cc | 2 |
8 files changed, 500 insertions, 190 deletions
diff --git a/common/arch_pybindings_shared.h b/common/arch_pybindings_shared.h index 88f95020..5295c6ab 100644 --- a/common/arch_pybindings_shared.h +++ b/common/arch_pybindings_shared.h @@ -110,3 +110,19 @@ fn_wrapper_0a<Context, decltype(&Context::archId), &Context::archId, conv_to_str fn_wrapper_2a_v<Context, decltype(&Context::writeSVG), &Context::writeSVG, pass_through<std::string>, pass_through<std::string>>::def_wrap(ctx_cls, "writeSVG"); + +// const\_range\<BelBucketId\> getBelBuckets() const +fn_wrapper_0a<Context, decltype(&Context::getBelBuckets), &Context::getBelBuckets, + wrap_context<BelBucketRange>>::def_wrap(ctx_cls, "getBelBuckets"); +// BelBucketId getBelBucketForBel(BelId bel) const +fn_wrapper_1a<Context, decltype(&Context::getBelBucketForBel), &Context::getBelBucketForBel, conv_to_str<BelBucketId>, + conv_from_str<BelId>>::def_wrap(ctx_cls, "getBelBucketForBel"); +// BelBucketId getBelBucketForCellType(IdString cell\_type) const +fn_wrapper_1a<Context, decltype(&Context::getBelBucketForCellType), &Context::getBelBucketForCellType, + conv_to_str<BelBucketId>, conv_from_str<IdString>>::def_wrap(ctx_cls, "getBelBucketForCellType"); +// const\_range\<BelId\> getBelsInBucket(BelBucketId bucket) const +fn_wrapper_1a<Context, decltype(&Context::getBelsInBucket), &Context::getBelsInBucket, + wrap_context<BelRangeForBelBucket>, conv_from_str<BelBucketId>>::def_wrap(ctx_cls, "getBelsInBucket"); +// bool isValidBelForCellType(IdString cell\_type, BelId bel) const +fn_wrapper_2a<Context, decltype(&Context::isValidBelForCellType), &Context::isValidBelForCellType, pass_through<bool>, + conv_from_str<IdString>, conv_from_str<BelId>>::def_wrap(ctx_cls, "isValidBelForCellType"); diff --git a/common/archcheck.cc b/common/archcheck.cc index 3c4c3133..f5760c88 100644 --- a/common/archcheck.cc +++ b/common/archcheck.cc @@ -51,6 +51,16 @@ void archcheck_names(const Context *ctx) log_error("wire != wire2, name = %s\n", name.c_str(ctx)); } } + + log_info("Checking bucket names..\n"); + for (BelBucketId bucket : ctx->getBelBuckets()) { + IdString name = ctx->getBelBucketName(bucket); + BelBucketId bucket2 = ctx->getBelBucketByName(name); + if (bucket != bucket2) { + log_error("bucket != bucket2, name = %s\n", name.c_str(ctx)); + } + } + #ifndef ARCH_ECP5 log_info("Checking pip names..\n"); for (PipId pip : ctx->getPips()) { @@ -187,6 +197,59 @@ void archcheck_conn(const Context *ctx) } } +void archcheck_buckets(const Context *ctx) +{ + log_info("Checking bucket data.\n"); + + // BEL buckets should be subsets of BELs that form an exact cover. + // In particular that means cell types in a bucket should only be + // placable in that bucket. + for (BelBucketId bucket : ctx->getBelBuckets()) { + + // Find out which cell types are in this bucket. + std::unordered_set<IdString> cell_types_in_bucket; + for (IdString cell_type : ctx->getCellTypes()) { + if (ctx->getBelBucketForCellType(cell_type) == bucket) { + cell_types_in_bucket.insert(cell_type); + } + } + + // Make sure that all cell types in this bucket have at least one + // BelId they can be placed at. + std::unordered_set<IdString> cell_types_unused; + + std::unordered_set<BelId> bels_in_bucket; + for (BelId bel : ctx->getBelsInBucket(bucket)) { + BelBucketId bucket2 = ctx->getBelBucketForBel(bel); + log_assert(bucket == bucket2); + + bels_in_bucket.insert(bel); + + // Check to see if a cell type not in this bucket can be + // placed at a BEL in this bucket. + for (IdString cell_type : ctx->getCellTypes()) { + if (ctx->getBelBucketForCellType(cell_type) == bucket) { + if (ctx->isValidBelForCellType(cell_type, bel)) { + cell_types_unused.erase(cell_type); + } + } else { + log_assert(!ctx->isValidBelForCellType(cell_type, bel)); + } + } + } + + // Verify that any BEL not in this bucket reports a different + // bucket. + for (BelId bel : ctx->getBels()) { + if (ctx->getBelBucketForBel(bel) != bucket) { + log_assert(bels_in_bucket.count(bel) == 0); + } + } + + log_assert(cell_types_unused.empty()); + } +} + } // namespace NEXTPNR_NAMESPACE_BEGIN @@ -199,6 +262,7 @@ void Context::archcheck() const archcheck_names(this); archcheck_locs(this); archcheck_conn(this); + archcheck_buckets(this); } NEXTPNR_NAMESPACE_END diff --git a/common/fast_bels.h b/common/fast_bels.h new file mode 100644 index 00000000..be2852cd --- /dev/null +++ b/common/fast_bels.h @@ -0,0 +1,184 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@symbioticeda.com> + * Copyright (C) 2018 David Shah <david@symbioticeda.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#pragma once + +#include <cstddef> +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +// FastBels is a lookup class that provides a fast lookup for finding BELs +// that support a given cell type. +struct FastBels +{ + struct TypeData + { + size_t type_index; + int number_of_possible_bels; + }; + + FastBels(Context *ctx, bool check_bel_available, int minBelsForGridPick) + : ctx(ctx), check_bel_available(check_bel_available), minBelsForGridPick(minBelsForGridPick) + { + } + + void addCellType(IdString cell_type) + { + auto iter = cell_types.find(cell_type); + if (iter != cell_types.end()) { + // This cell type has already been added to the fast BEL lookup. + return; + } + + size_t type_idx = cell_types.size(); + auto &cell_type_data = cell_types[cell_type]; + cell_type_data.type_index = type_idx; + + fast_bels_by_cell_type.resize(type_idx + 1); + auto &bel_data = fast_bels_by_cell_type.at(type_idx); + + for (auto bel : ctx->getBels()) { + if (!ctx->isValidBelForCellType(cell_type, bel)) { + continue; + } + + cell_type_data.number_of_possible_bels += 1; + } + + for (auto bel : ctx->getBels()) { + if (check_bel_available && !ctx->checkBelAvail(bel)) { + continue; + } + + if (!ctx->isValidBelForCellType(cell_type, bel)) { + continue; + } + + Loc loc = ctx->getBelLocation(bel); + if (minBelsForGridPick >= 0 && cell_type_data.number_of_possible_bels < minBelsForGridPick) { + loc.x = loc.y = 0; + } + + if (int(bel_data.size()) < (loc.x + 1)) { + bel_data.resize(loc.x + 1); + } + + if (int(bel_data.at(loc.x).size()) < (loc.y + 1)) { + bel_data.at(loc.x).resize(loc.y + 1); + } + + bel_data.at(loc.x).at(loc.y).push_back(bel); + } + } + + void addBelBucket(BelBucketId partition) + { + auto iter = partition_types.find(partition); + if (iter != partition_types.end()) { + // This partition has already been added to the fast BEL lookup. + return; + } + + size_t type_idx = partition_types.size(); + auto &type_data = partition_types[partition]; + type_data.type_index = type_idx; + + fast_bels_by_partition_type.resize(type_idx + 1); + auto &bel_data = fast_bels_by_partition_type.at(type_idx); + + for (auto bel : ctx->getBels()) { + if (ctx->getBelBucketForBel(bel) != partition) { + continue; + } + + type_data.number_of_possible_bels += 1; + } + + for (auto bel : ctx->getBels()) { + if (check_bel_available && !ctx->checkBelAvail(bel)) { + continue; + } + + if (ctx->getBelBucketForBel(bel) != partition) { + continue; + } + + Loc loc = ctx->getBelLocation(bel); + if (minBelsForGridPick >= 0 && type_data.number_of_possible_bels < minBelsForGridPick) { + loc.x = loc.y = 0; + } + + if (int(bel_data.size()) < (loc.x + 1)) { + bel_data.resize(loc.x + 1); + } + + if (int(bel_data.at(loc.x).size()) < (loc.y + 1)) { + bel_data.at(loc.x).resize(loc.y + 1); + } + + bel_data.at(loc.x).at(loc.y).push_back(bel); + } + } + + typedef std::vector<std::vector<std::vector<BelId>>> FastBelsData; + + int getBelsForCellType(IdString cell_type, FastBelsData **data) + { + auto iter = cell_types.find(cell_type); + if (iter == cell_types.end()) { + addCellType(cell_type); + iter = cell_types.find(cell_type); + NPNR_ASSERT(iter != cell_types.end()); + } + + auto cell_type_data = iter->second; + + *data = &fast_bels_by_cell_type.at(cell_type_data.type_index); + return cell_type_data.number_of_possible_bels; + } + + size_t getBelsForBelBucket(BelBucketId partition, FastBelsData **data) + { + auto iter = partition_types.find(partition); + if (iter == partition_types.end()) { + addBelBucket(partition); + iter = partition_types.find(partition); + NPNR_ASSERT(iter != partition_types.end()); + } + + auto type_data = iter->second; + + *data = &fast_bels_by_partition_type.at(type_data.type_index); + return type_data.number_of_possible_bels; + } + + Context *ctx; + const bool check_bel_available; + const int minBelsForGridPick; + + std::unordered_map<IdString, TypeData> cell_types; + std::vector<FastBelsData> fast_bels_by_cell_type; + + std::unordered_map<BelBucketId, TypeData> partition_types; + std::vector<FastBelsData> fast_bels_by_partition_type; +}; + +NEXTPNR_NAMESPACE_END diff --git a/common/place_common.cc b/common/place_common.cc index cb9799b5..3f89169a 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -118,7 +118,8 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality) } IdString targetType = cell->type; for (auto bel : ctx->getBels()) { - if (ctx->getBelType(bel) == targetType && (!require_legality || ctx->isValidBelForCell(cell, bel))) { + if (ctx->isValidBelForCellType(targetType, bel) && + (!require_legality || ctx->isValidBelForCell(cell, bel))) { if (ctx->checkBelAvail(bel)) { wirelen_t wirelen = get_cell_metric_at_bel(ctx, cell, bel, MetricType::COST); if (iters >= 4) @@ -229,7 +230,7 @@ class ConstraintLegaliseWorker if (locBel == BelId()) { return false; } - if (ctx->getBelType(locBel) != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, locBel)) { return false; } if (!ctx->checkBelAvail(locBel)) { diff --git a/common/placer1.cc b/common/placer1.cc index 49f556f7..1c039090 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -39,6 +39,7 @@ #include <stdlib.h> #include <string.h> #include <vector> +#include "fast_bels.h" #include "log.h" #include "place_common.h" #include "timing.h" @@ -75,36 +76,26 @@ class SAPlacer }; public: - SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) + SAPlacer(Context *ctx, Placer1Cfg cfg) + : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg) { - int num_bel_types = 0; - for (auto bel : ctx->getBels()) { - IdString type = ctx->getBelType(bel); - if (bel_types.find(type) == bel_types.end()) { - bel_types[type] = std::tuple<int, int>(num_bel_types++, 1); - } else { - std::get<1>(bel_types.at(type))++; - } - } for (auto bel : ctx->getBels()) { Loc loc = ctx->getBelLocation(bel); - IdString type = ctx->getBelType(bel); - int type_idx = std::get<0>(bel_types.at(type)); - int type_cnt = std::get<1>(bel_types.at(type)); - if (type_cnt < cfg.minBelsForGridPick) - loc.x = loc.y = 0; - if (int(fast_bels.size()) < type_idx + 1) - fast_bels.resize(type_idx + 1); - if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) - fast_bels.at(type_idx).resize(loc.x + 1); - if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) - fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); max_x = std::max(max_x, loc.x); max_y = std::max(max_y, loc.y); - fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); } diameter = std::max(max_x, max_y) + 1; + std::unordered_set<IdString> cell_types_in_use; + for (auto cell : sorted(ctx->cells)) { + IdString cell_type = cell.second->type; + cell_types_in_use.insert(cell_type); + } + + for (auto cell_type : cell_types_in_use) { + fast_bels.addCellType(cell_type); + } + net_bounds.resize(ctx->nets.size()); net_arc_tcost.resize(ctx->nets.size()); old_udata.reserve(ctx->nets.size()); @@ -170,13 +161,14 @@ class SAPlacer loc_name.c_str(), cell->name.c_str(ctx)); } - IdString bel_type = ctx->getBelType(bel); - if (bel_type != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, bel)) { + IdString bel_type = ctx->getBelType(bel); log_error("Bel \'%s\' of type \'%s\' does not match cell " "\'%s\' of type \'%s\'\n", loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); } if (!ctx->isValidBelForCell(cell, bel)) { + IdString bel_type = ctx->getBelType(bel); log_error("Bel \'%s\' of type \'%s\' is not valid for cell " "\'%s\' of type \'%s\'\n", loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); @@ -452,7 +444,7 @@ class SAPlacer IdString targetType = cell->type; auto proc_bel = [&](BelId bel) { - if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) { + if (ctx->isValidBelForCellType(targetType, bel) && ctx->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); if (score <= best_score) { @@ -651,7 +643,7 @@ class SAPlacer BelId targetBel = ctx->getBelByLocation(targetLoc); if (targetBel == BelId()) return false; - if (ctx->getBelType(targetBel) != cell->type) + if (!ctx->isValidBelForCellType(cell->type, targetBel)) return false; CellInfo *bound = ctx->getBoundBelCell(targetBel); // We don't consider swapping chains with other chains, at least for the time being - unless it is @@ -730,18 +722,19 @@ class SAPlacer curr_loc.y = std::min(region_bounds[cell->region->name].y1, curr_loc.y); } + FastBels::FastBelsData *bel_data; + auto type_cnt = fast_bels.getBelsForCellType(targetType, &bel_data); + while (true) { int nx = ctx->rng(2 * dx + 1) + std::max(curr_loc.x - dx, 0); int ny = ctx->rng(2 * dy + 1) + std::max(curr_loc.y - dy, 0); - int beltype_idx, beltype_cnt; - std::tie(beltype_idx, beltype_cnt) = bel_types.at(targetType); - if (beltype_cnt < cfg.minBelsForGridPick) + if (cfg.minBelsForGridPick >= 0 && type_cnt < cfg.minBelsForGridPick) nx = ny = 0; - if (nx >= int(fast_bels.at(beltype_idx).size())) + if (nx >= int(bel_data->size())) continue; - if (ny >= int(fast_bels.at(beltype_idx).at(nx).size())) + if (ny >= int(bel_data->at(nx).size())) continue; - const auto &fb = fast_bels.at(beltype_idx).at(nx).at(ny); + const auto &fb = bel_data->at(nx).at(ny); if (fb.size() == 0) continue; BelId bel = fb.at(ctx->rng(int(fb.size()))); @@ -1217,7 +1210,7 @@ class SAPlacer 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; - std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels; + FastBels fast_bels; std::unordered_set<BelId> locked_bels; std::vector<NetInfo *> net_by_udata; std::vector<decltype(NetInfo::udata)> old_udata; diff --git a/common/placer_heap.cc b/common/placer_heap.cc index f10d4139..d149a5b0 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -44,12 +44,14 @@ #include <queue> #include <tuple> #include <unordered_map> +#include "fast_bels.h" #include "log.h" #include "nextpnr.h" #include "place_common.h" #include "placer1.h" #include "timing.h" #include "util.h" + NEXTPNR_NAMESPACE_BEGIN namespace { @@ -136,7 +138,10 @@ template <typename T> struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg) { Eigen::initParallel(); } + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) + { + Eigen::initParallel(); + } bool place() { @@ -175,24 +180,26 @@ class HeAPPlacer std::vector<std::tuple<CellInfo *, BelId, PlaceStrength>> solution; - std::vector<std::unordered_set<IdString>> heap_runs; - std::unordered_set<IdString> all_celltypes; - std::unordered_map<IdString, int> ct_count; + std::vector<std::unordered_set<BelBucketId>> heap_runs; + std::unordered_set<BelBucketId> all_buckets; + std::unordered_map<BelBucketId, int> bucket_count; for (auto cell : place_cells) { - if (!all_celltypes.count(cell->type)) { - heap_runs.push_back(std::unordered_set<IdString>{cell->type}); - all_celltypes.insert(cell->type); + BelBucketId bucket = ctx->getBelBucketForCellType(cell->type); + if (!all_buckets.count(bucket)) { + heap_runs.push_back(std::unordered_set<BelBucketId>{bucket}); + all_buckets.insert(bucket); } - ct_count[cell->type]++; + bucket_count[bucket]++; } // If more than 98% of cells are one cell type, always solve all at once // Otherwise, follow full HeAP strategy of rotate&all - for (auto &c : ct_count) + for (auto &c : bucket_count) { if (c.second >= 0.98 * int(place_cells.size())) { heap_runs.clear(); break; } + } if (cfg.placeAllAtOnce) { // Never want to deal with LUTs, FFs, MUXFxs separately, @@ -201,7 +208,7 @@ class HeAPPlacer heap_runs.clear(); } - heap_runs.push_back(all_celltypes); + heap_runs.push_back(all_buckets); // The main HeAP placer loop log_info("Running main analytical placer.\n"); while (stalled < 5 && (solved_hpwl <= legal_hpwl * 0.8)) { @@ -238,7 +245,7 @@ class HeAPPlacer for (auto type : sorted(run)) if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(), - [type](const std::unordered_set<IdString> &grp) { return !grp.count(type); })) + [type](const std::unordered_set<BelBucketId> &grp) { return !grp.count(type); })) CutSpreader(this, {type}).run(); update_all_chains(); @@ -248,8 +255,10 @@ class HeAPPlacer legal_hpwl = total_hpwl(); auto run_stopt = std::chrono::high_resolution_clock::now(); + + IdString bucket_name = ctx->getBelBucketName(*run.begin()); log_info(" at iteration #%d, type %s: wirelen solved = %d, spread = %d, legal = %d; time = %.02fs\n", - iter + 1, (run.size() > 1 ? "ALL" : run.begin()->c_str(ctx)), int(solved_hpwl), + iter + 1, (run.size() > 1 ? "ALL" : bucket_name.c_str(ctx)), int(solved_hpwl), int(spread_hpwl), int(legal_hpwl), std::chrono::duration<double>(run_stopt - run_startt).count()); } @@ -318,16 +327,9 @@ class HeAPPlacer PlacerHeapCfg cfg; int max_x = 0, max_y = 0; - std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels; + FastBels fast_bels; std::unordered_map<IdString, std::tuple<int, int>> bel_types; - // For fast handling of heterogeneity during initial placement without full legalisation, - // for each Bel type this goes from x or y to the nearest x or y where a Bel of a given type exists - // This is particularly important for the iCE40 architecture, where multipliers and BRAM only exist at the - // edges and corners respectively - std::vector<std::vector<int>> nearest_row_with_bel; - std::vector<std::vector<int>> nearest_col_with_bel; - struct BoundingBox { // Actual bounding box @@ -384,13 +386,14 @@ class HeAPPlacer loc_name.c_str(), cell->name.c_str(ctx)); } - IdString bel_type = ctx->getBelType(bel); - if (bel_type != cell->type) { + if (!ctx->isValidBelForCellType(cell->type, bel)) { + IdString bel_type = ctx->getBelType(bel); log_error("Bel \'%s\' of type \'%s\' does not match cell " "\'%s\' of type \'%s\'\n", loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); } if (!ctx->isValidBelForCell(cell, bel)) { + IdString bel_type = ctx->getBelType(bel); log_error("Bel \'%s\' of type \'%s\' is not valid for cell " "\'%s\' of type \'%s\'\n", loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx)); @@ -410,66 +413,30 @@ class HeAPPlacer ctx->yield(); } - // Construct the fast_bels, nearest_row_with_bel and nearest_col_with_bel void build_fast_bels() { - - int num_bel_types = 0; - for (auto bel : ctx->getBels()) { - IdString type = ctx->getBelType(bel); - if (bel_types.find(type) == bel_types.end()) { - bel_types[type] = std::tuple<int, int>(num_bel_types++, 1); - } else { - std::get<1>(bel_types.at(type))++; - } - } for (auto bel : ctx->getBels()) { if (!ctx->checkBelAvail(bel)) continue; Loc loc = ctx->getBelLocation(bel); - IdString type = ctx->getBelType(bel); - int type_idx = std::get<0>(bel_types.at(type)); - if (int(fast_bels.size()) < type_idx + 1) - fast_bels.resize(type_idx + 1); - if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) - fast_bels.at(type_idx).resize(loc.x + 1); - if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) - fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); max_x = std::max(max_x, loc.x); max_y = std::max(max_y, loc.y); - fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); } - nearest_row_with_bel.resize(num_bel_types, std::vector<int>(max_y + 1, -1)); - nearest_col_with_bel.resize(num_bel_types, std::vector<int>(max_x + 1, -1)); - for (auto bel : ctx->getBels()) { - if (!ctx->checkBelAvail(bel)) - continue; - Loc loc = ctx->getBelLocation(bel); - int type_idx = std::get<0>(bel_types.at(ctx->getBelType(bel))); - auto &nr = nearest_row_with_bel.at(type_idx), &nc = nearest_col_with_bel.at(type_idx); - // Traverse outwards through nearest_row_with_bel and nearest_col_with_bel, stopping once - // another row/col is already recorded as being nearer - for (int x = loc.x; x <= max_x; x++) { - if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (x - loc.x)) - break; - nc.at(x) = loc.x; - } - for (int x = loc.x - 1; x >= 0; x--) { - if (nc.at(x) != -1 && std::abs(loc.x - nc.at(x)) <= (loc.x - x)) - break; - nc.at(x) = loc.x; - } - for (int y = loc.y; y <= max_y; y++) { - if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (y - loc.y)) - break; - nr.at(y) = loc.y; - } - for (int y = loc.y - 1; y >= 0; y--) { - if (nr.at(y) != -1 && std::abs(loc.y - nr.at(y)) <= (loc.y - y)) - break; - nr.at(y) = loc.y; - } + std::unordered_set<IdString> cell_types_in_use; + std::unordered_set<BelBucketId> buckets_in_use; + for (auto cell : sorted(ctx->cells)) { + IdString cell_type = cell.second->type; + cell_types_in_use.insert(cell_type); + BelBucketId bucket = ctx->getBelBucketForCellType(cell_type); + buckets_in_use.insert(bucket); + } + + for (auto cell_type : cell_types_in_use) { + fast_bels.addCellType(cell_type); + } + for (auto bucket : buckets_in_use) { + fast_bels.addBelBucket(bucket); } // Determine bounding boxes of region constraints @@ -523,15 +490,30 @@ class HeAPPlacer // FIXME: Are there better approaches to the initial placement (e.g. greedy?) void seed_placement() { + std::unordered_set<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; + for (auto bel : ctx->getBels()) { - if (!ctx->checkBelAvail(bel)) + if (!ctx->checkBelAvail(bel)) { continue; - available_bels[ctx->getBelType(bel)].push_back(bel); + } + + for (auto cell_type : cell_types) { + if (ctx->isValidBelForCellType(cell_type, bel)) { + available_bels[cell_type].push_back(bel); + } + } } + for (auto &t : available_bels) { ctx->shuffle(t.second.begin(), t.second.end()); } + for (auto cell : sorted(ctx->cells)) { CellInfo *ci = cell.second; if (ci->bel != BelId()) { @@ -544,21 +526,48 @@ class HeAPPlacer bool placed = false; int attempt_count = 0; while (!placed) { - if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty()) - log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx), - ci->type.c_str(ctx)); ++attempt_count; - if (attempt_count > 25000) + if (attempt_count > 25000) { log_error("Unable to find a placement location for cell '%s'\n", ci->name.c_str(ctx)); - BelId bel = available_bels.at(ci->type).back(); - available_bels.at(ci->type).pop_back(); + } + + // Make sure this cell type is in the available BEL map at + // all. + if (!available_bels.count(ci->type)) { + log_error("Unable to place cell '%s', no BELs remaining to implement cell type '%s'\n", + ci->name.c_str(ctx), ci->type.c_str(ctx)); + } + + // Find an unused BEL from bels_for_cell_type. + auto &bels_for_cell_type = available_bels.at(ci->type); + BelId bel; + while (true) { + if (bels_for_cell_type.empty()) { + log_error("Unable to place cell '%s', no BELs remaining to implement cell type '%s'\n", + ci->name.c_str(ctx), ci->type.c_str(ctx)); + } + + BelId candidate_bel = bels_for_cell_type.back(); + bels_for_cell_type.pop_back(); + if (bels_used.count(candidate_bel)) { + // candidate_bel has already been used by another + // cell type, skip it. + continue; + } + + bel = candidate_bel; + break; + } + Loc loc = ctx->getBelLocation(bel); cell_locs[cell.first].x = loc.x; cell_locs[cell.first].y = loc.y; cell_locs[cell.first].locked = false; cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel); + // FIXME if (has_connectivity(cell.second) && !cfg.ioBufTypes.count(ci->type)) { + bels_used.insert(bel); place_cells.push_back(ci); placed = true; } else { @@ -566,6 +575,7 @@ class HeAPPlacer ctx->bindBel(bel, ci, STRENGTH_STRONG); cell_locs[cell.first].locked = true; placed = true; + bels_used.insert(bel); } else { available_bels.at(ci->type).push_front(bel); } @@ -576,7 +586,7 @@ class HeAPPlacer } // Setup the cells to be solved, returns the number of rows - int setup_solve_cells(std::unordered_set<IdString> *celltypes = nullptr) + int setup_solve_cells(std::unordered_set<BelBucketId> *buckets = nullptr) { int row = 0; solve_cells.clear(); @@ -585,7 +595,7 @@ class HeAPPlacer cell.second->udata = dont_solve; // Then update cells to be placed, which excludes cell children for (auto cell : place_cells) { - if (celltypes && !celltypes->count(cell->type)) + if (buckets && !buckets->count(ctx->getBelBucketForCellType(cell->type))) continue; cell->udata = row++; solve_cells.push_back(cell); @@ -814,8 +824,8 @@ class HeAPPlacer if (ci->bel != BelId()) continue; // log_info(" Legalising %s (%s)\n", top.second.c_str(ctx), ci->type.c_str(ctx)); - int bt = std::get<0>(bel_types.at(ci->type)); - auto &fb = fast_bels.at(bt); + FastBels::FastBelsData *fb; + fast_bels.getBelsForCellType(ci->type, &fb); int radius = 0; int iter = 0; int iter_at_radius = 0; @@ -864,13 +874,13 @@ class HeAPPlacer while (radius < std::max(max_x, max_y)) { for (int x = std::max(0, cell_locs.at(ci->name).x - radius); x <= std::min(max_x, cell_locs.at(ci->name).x + radius); x++) { - if (x >= int(fb.size())) + if (x >= int(fb->size())) break; for (int y = std::max(0, cell_locs.at(ci->name).y - radius); y <= std::min(max_y, cell_locs.at(ci->name).y + radius); y++) { - if (y >= int(fb.at(x).size())) + if (y >= int(fb->at(x).size())) break; - if (fb.at(x).at(y).size() > 0) + if (fb->at(x).at(y).size() > 0) goto notempty; } } @@ -885,14 +895,11 @@ class HeAPPlacer if (ny < 0 || ny > max_y) continue; - // ny = nearest_row_with_bel.at(bt).at(ny); - // nx = nearest_col_with_bel.at(bt).at(nx); - - if (nx >= int(fb.size())) + if (nx >= int(fb->size())) continue; - if (ny >= int(fb.at(nx).size())) + if (ny >= int(fb->at(nx).size())) continue; - if (fb.at(nx).at(ny).empty()) + if (fb->at(nx).at(ny).empty()) continue; int need_to_explore = 2 * radius; @@ -912,7 +919,7 @@ class HeAPPlacer } if (ci->constr_children.empty() && !ci->constr_abs_z) { - for (auto sz : fb.at(nx).at(ny)) { + for (auto sz : fb->at(nx).at(ny)) { if (ci->region != nullptr && ci->region->constr_bels && !ci->region->bels.count(sz)) continue; if (ctx->checkBelAvail(sz) || (radius > ripup_radius || ctx->rng(20000) < 10)) { @@ -962,7 +969,7 @@ class HeAPPlacer } } } else { - for (auto sz : fb.at(nx).at(ny)) { + for (auto sz : fb->at(nx).at(ny)) { Loc loc = ctx->getBelLocation(sz); if (ci->constr_abs_z && loc.z != ci->constr_z) continue; @@ -979,7 +986,7 @@ class HeAPPlacer if (vc->region != nullptr && vc->region->constr_bels && !vc->region->bels.count(target)) goto fail; CellInfo *bound; - if (target == BelId() || ctx->getBelType(target) != vc->type) + if (target == BelId() || !ctx->isValidBelForCellType(vc->type, target)) goto fail; bound = ctx->getBoundBelCell(target); // Chains cannot overlap @@ -1081,13 +1088,17 @@ class HeAPPlacer class CutSpreader { public: - CutSpreader(HeAPPlacer *p, const std::unordered_set<IdString> &beltype) : p(p), ctx(p->ctx), beltype(beltype) + CutSpreader(HeAPPlacer *p, const std::unordered_set<BelBucketId> &buckets) : p(p), ctx(p->ctx), buckets(buckets) { - int idx = 0; - for (IdString type : sorted(beltype)) { - type_index[type] = idx; - fb.emplace_back(&(p->fast_bels.at(std::get<0>(p->bel_types.at(type))))); + // Get fast BELs data for all buckets being Cut/Spread. + size_t idx = 0; + for (BelBucketId bucket : sorted(buckets)) { + type_index[bucket] = idx; + FastBels::FastBelsData *fast_bels; + p->fast_bels.getBelsForBelBucket(bucket, &fast_bels); + fb.push_back(fast_bels); ++idx; + NPNR_ASSERT(fb.size() == idx); } } static int seq; @@ -1169,8 +1180,8 @@ class HeAPPlacer private: HeAPPlacer *p; Context *ctx; - std::unordered_set<IdString> beltype; - std::unordered_map<IdString, int> type_index; + std::unordered_set<BelBucketId> buckets; + std::unordered_map<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; @@ -1192,16 +1203,23 @@ class HeAPPlacer return int(fb.at(type)->at(x).at(y).size()); } + bool is_cell_fixed(const CellInfo &cell) const + { + return buckets.count(ctx->getBelBucketForCellType(cell.type)) == 0; + } + + size_t cell_index(const CellInfo &cell) const { return type_index.at(ctx->getBelBucketForCellType(cell.type)); } + void init() { occupancy.resize(p->max_x + 1, - std::vector<std::vector<int>>(p->max_y + 1, std::vector<int>(beltype.size(), 0))); + std::vector<std::vector<int>>(p->max_y + 1, std::vector<int>(buckets.size(), 0))); groups.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, -1)); chaines.resize(p->max_x + 1, std::vector<ChainExtent>(p->max_y + 1)); cells_at_location.resize(p->max_x + 1, std::vector<std::vector<CellInfo *>>(p->max_y + 1)); for (int x = 0; x <= p->max_x; x++) for (int y = 0; y <= p->max_y; y++) { - for (int t = 0; t < int(beltype.size()); t++) { + for (int t = 0; t < int(buckets.size()); t++) { occupancy.at(x).at(y).at(t) = 0; } groups.at(x).at(y) = -1; @@ -1219,55 +1237,77 @@ class HeAPPlacer } }; - for (auto &cell : p->cell_locs) { - if (!beltype.count(ctx->cells.at(cell.first)->type)) + for (auto &cell_loc : p->cell_locs) { + IdString cell_name = cell_loc.first; + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; - if (ctx->cells.at(cell.first)->belStrength > STRENGTH_STRONG) + } + + if (cell.belStrength > STRENGTH_STRONG) { continue; - occupancy.at(cell.second.x).at(cell.second.y).at(type_index.at(ctx->cells.at(cell.first)->type))++; + } + + occupancy.at(cell_loc.second.x).at(cell_loc.second.y).at(cell_index(cell))++; + // Compute ultimate extent of each chain root - if (p->chain_root.count(cell.first)) { - set_chain_ext(p->chain_root.at(cell.first)->name, cell.second.x, cell.second.y); - } else if (!ctx->cells.at(cell.first)->constr_children.empty()) { - set_chain_ext(cell.first, cell.second.x, cell.second.y); + if (p->chain_root.count(cell_name)) { + set_chain_ext(p->chain_root.at(cell_name)->name, loc.x, loc.y); + } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { + set_chain_ext(cell_name, loc.x, loc.y); } } - for (auto &cell : p->cell_locs) { - if (!beltype.count(ctx->cells.at(cell.first)->type)) + + for (auto &cell_loc : p->cell_locs) { + IdString cell_name = cell_loc.first; + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; - // Transfer chain extents to the actual chaines structure + } + + // Transfer chain extents to the actual chains structure ChainExtent *ce = nullptr; - if (p->chain_root.count(cell.first)) - ce = &(cell_extents.at(p->chain_root.at(cell.first)->name)); - else if (!ctx->cells.at(cell.first)->constr_children.empty()) - ce = &(cell_extents.at(cell.first)); + if (p->chain_root.count(cell_name)) { + ce = &(cell_extents.at(p->chain_root.at(cell_name)->name)); + } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { + ce = &(cell_extents.at(cell_name)); + } + if (ce) { - auto &lce = chaines.at(cell.second.x).at(cell.second.y); + auto &lce = chaines.at(loc.x).at(loc.y); lce.x0 = std::min(lce.x0, ce->x0); lce.y0 = std::min(lce.y0, ce->y0); lce.x1 = std::max(lce.x1, ce->x1); lce.y1 = std::max(lce.y1, ce->y1); } } + for (auto cell : p->solve_cells) { - if (!beltype.count(cell->type)) + if (is_cell_fixed(*cell)) { continue; + } + cells_at_location.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell); } } + void merge_regions(SpreaderRegion &merged, SpreaderRegion &mergee) { // Prevent grow_region from recursing while doing this - for (int x = mergee.x0; x <= mergee.x1; x++) + for (int x = mergee.x0; x <= mergee.x1; x++) { for (int y = mergee.y0; y <= mergee.y1; y++) { // log_info("%d %d\n", groups.at(x).at(y), mergee.id); NPNR_ASSERT(groups.at(x).at(y) == mergee.id); groups.at(x).at(y) = merged.id; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { merged.cells.at(t) += occ_at(x, y, t); merged.bels.at(t) += bels_at(x, y, t); } } + } + merged_regions.insert(mergee.id); grow_region(merged, mergee.x0, mergee.y0, mergee.x1, mergee.y1); } @@ -1286,11 +1326,12 @@ class HeAPPlacer auto process_location = [&](int x, int y) { // Merge with any overlapping regions if (groups.at(x).at(y) == -1) { - for (int t = 0; t < int(beltype.size()); t++) { + for (size_t t = 0; t < buckets.size(); t++) { r.bels.at(t) += bels_at(x, y, t); r.cells.at(t) += occ_at(x, y, t); } } + if (groups.at(x).at(y) != -1 && groups.at(x).at(y) != r.id) merge_regions(r, regions.at(groups.at(x).at(y))); groups.at(x).at(y) = r.id; @@ -1320,12 +1361,13 @@ class HeAPPlacer if (groups.at(x).at(y) != -1) continue; bool overutilised = false; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(x, y, t) > bels_at(x, y, t)) { overutilised = true; break; } } + if (!overutilised) continue; // log_info("%d %d %d\n", x, y, occ_at(x, y)); @@ -1335,7 +1377,7 @@ class HeAPPlacer reg.id = id; reg.x0 = reg.x1 = x; reg.y0 = reg.y1 = y; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { reg.bels.push_back(bels_at(x, y, t)); reg.cells.push_back(occ_at(x, y, t)); } @@ -1352,7 +1394,7 @@ class HeAPPlacer if (reg.x1 < p->max_x) { bool over_occ_x = false; for (int y1 = reg.y0; y1 <= reg.y1; y1++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(reg.x1 + 1, y1, t) > bels_at(reg.x1 + 1, y1, t)) { over_occ_x = true; break; @@ -1368,7 +1410,7 @@ class HeAPPlacer if (reg.y1 < p->max_y) { bool over_occ_y = false; for (int x1 = reg.x0; x1 <= reg.x1; x1++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { if (occ_at(x1, reg.y1 + 1, t) > bels_at(x1, reg.y1 + 1, t)) { over_occ_y = true; break; @@ -1430,10 +1472,12 @@ class HeAPPlacer } } if (!changed) { - for (auto bt : sorted(beltype)) { - if (reg.cells > reg.bels) + for (auto bucket : sorted(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, - reg.x1, reg.y1, reg.cells.at(type_index.at(bt)), bt.c_str(ctx)); + reg.x1, reg.y1, reg.cells.at(type_index.at(bucket)), bucket_name.c_str(ctx)); + } } break; } @@ -1454,7 +1498,7 @@ class HeAPPlacer for (int x = r.x0; x <= r.x1; x++) { for (int y = r.y0; y <= r.y1; y++) { std::copy(cal.at(x).at(y).begin(), cal.at(x).at(y).end(), std::back_inserter(cut_cells)); - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) total_bels += bels_at(x, y, t); } } @@ -1506,26 +1550,34 @@ class HeAPPlacer int trimmed_l = dir ? r.y0 : r.x0, trimmed_r = dir ? r.y1 : r.x1; while (trimmed_l < (dir ? r.y1 : r.x1)) { bool have_bels = false; - for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) - for (size_t t = 0; t < beltype.size(); t++) + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) { + for (size_t t = 0; t < buckets.size(); t++) { if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i, t) > 0) { have_bels = true; break; } + } + } + if (have_bels) break; + trimmed_l++; } while (trimmed_r > (dir ? r.y0 : r.x0)) { bool have_bels = false; - for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) - for (size_t t = 0; t < beltype.size(); t++) + for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++) { + for (size_t t = 0; t < buckets.size(); t++) { if (bels_at(dir ? i : trimmed_r, dir ? trimmed_r : i, t) > 0) { have_bels = true; break; } + } + } + if (have_bels) break; + trimmed_r--; } // log_info("tl %d tr %d cl %d cr %d\n", trimmed_l, trimmed_r, clearance_l, clearance_r); @@ -1533,27 +1585,27 @@ class HeAPPlacer return {}; // Now find the initial target cut that minimises utilisation imbalance, whilst // meeting the clearance requirements for any large macros - std::vector<int> left_cells_v(beltype.size(), 0), right_cells_v(beltype.size(), 0); - std::vector<int> left_bels_v(beltype.size(), 0), right_bels_v(r.bels); + std::vector<int> left_cells_v(buckets.size(), 0), right_cells_v(buckets.size(), 0); + std::vector<int> left_bels_v(buckets.size(), 0), right_bels_v(r.bels); for (int i = 0; i <= pivot; i++) - left_cells_v.at(type_index.at(cut_cells.at(i)->type)) += + left_cells_v.at(cell_index(*cut_cells.at(i))) += p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1; for (int i = pivot + 1; i < int(cut_cells.size()); i++) - right_cells_v.at(type_index.at(cut_cells.at(i)->type)) += + right_cells_v.at(cell_index(*cut_cells.at(i))) += p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1; int best_tgt_cut = -1; double best_deltaU = std::numeric_limits<double>::max(); // std::pair<int, int> target_cut_bels; - std::vector<int> slither_bels(beltype.size(), 0); + std::vector<int> slither_bels(buckets.size(), 0); for (int i = trimmed_l; i <= trimmed_r; i++) { - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) slither_bels.at(t) = 0; for (int j = dir ? r.x0 : r.y0; j <= (dir ? r.x1 : r.y1); j++) { - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) slither_bels.at(t) += dir ? bels_at(j, i, t) : bels_at(i, j, t); } - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) += slither_bels.at(t); right_bels_v.at(t) -= slither_bels.at(t); } @@ -1561,7 +1613,7 @@ class HeAPPlacer if (((i - trimmed_l) + 1) >= clearance_l && ((trimmed_r - i) + 1) >= clearance_r) { // Solution is potentially valid double aU = 0; - for (size_t t = 0; t < beltype.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) aU += (left_cells_v.at(t) + right_cells_v.at(t)) * std::abs(double(left_cells_v.at(t)) / double(std::max(left_bels_v.at(t), 1)) - double(right_cells_v.at(t)) / double(std::max(right_bels_v.at(t), 1))); @@ -1575,19 +1627,19 @@ class HeAPPlacer return {}; // left_bels = target_cut_bels.first; // right_bels = target_cut_bels.second; - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) = 0; right_bels_v.at(t) = 0; } for (int x = r.x0; x <= (dir ? r.x1 : best_tgt_cut); x++) for (int y = r.y0; y <= (dir ? best_tgt_cut : r.y1); y++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { left_bels_v.at(t) += bels_at(x, y, t); } } for (int x = dir ? r.x0 : (best_tgt_cut + 1); x <= r.x1; x++) for (int y = dir ? (best_tgt_cut + 1) : r.y0; y <= r.y1; y++) { - for (size_t t = 0; t < beltype.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { right_bels_v.at(t) += bels_at(x, y, t); } } @@ -1607,15 +1659,15 @@ class HeAPPlacer while (pivot > 0 && is_part_overutil(false)) { auto &move_cell = cut_cells.at(pivot); int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; - left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size; - right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size; + left_cells_v.at(cell_index(*cut_cells.at(pivot))) -= size; + right_cells_v.at(cell_index(*cut_cells.at(pivot))) += size; pivot--; } while (pivot < int(cut_cells.size()) - 1 && is_part_overutil(true)) { auto &move_cell = cut_cells.at(pivot + 1); int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1; - left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size; - right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size; + left_cells_v.at(cell_index(*cut_cells.at(pivot))) += size; + right_cells_v.at(cell_index(*cut_cells.at(pivot))) -= size; pivot++; } diff --git a/common/placer_heap.h b/common/placer_heap.h index 46c00503..00913062 100644 --- a/common/placer_heap.h +++ b/common/placer_heap.h @@ -49,7 +49,7 @@ struct PlacerHeapCfg std::unordered_set<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<IdString>> cellGroups; + std::vector<std::unordered_set<BelBucketId>> cellGroups; }; extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg); diff --git a/common/timing_opt.cc b/common/timing_opt.cc index eae15fb2..025084b7 100644 --- a/common/timing_opt.cc +++ b/common/timing_opt.cc @@ -215,7 +215,7 @@ class TimingOptimiser std::vector<BelId> free_bels_at_loc; std::vector<BelId> bound_bels_at_loc; for (auto bel : ctx->getBelsByTile(curr_loc.x + dx, curr_loc.y + dy)) { - if (ctx->getBelType(bel) != cell->type) + if (!ctx->isValidBelForCellType(cell->type, bel)) continue; CellInfo *bound = ctx->getBoundBelCell(bel); if (bound == nullptr) { |