From 2285c8dbbdbc5b7e718fa849952c560bef69a8fc Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 15:40:26 -0800 Subject: Initial refactoring of placer API. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/fast_bels.h | 105 +++++++++++++++++++++++++++++++++++++++++++++++++ common/place_common.cc | 4 +- common/placer1.cc | 47 +++++++--------------- common/placer_heap.cc | 46 +++++++--------------- common/timing_opt.cc | 2 +- 5 files changed, 136 insertions(+), 68 deletions(-) create mode 100644 common/fast_bels.h (limited to 'common') diff --git a/common/fast_bels.h b/common/fast_bels.h new file mode 100644 index 00000000..1b769baf --- /dev/null +++ b/common/fast_bels.h @@ -0,0 +1,105 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf + * Copyright (C) 2018 David Shah + * + * 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 "nextpnr.h" +#include + +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 CellTypeData { + size_t cell_type_index; + size_t number_of_possible_bels; + }; + + FastBels(Context *ctx, int minBelsForGridPick) : ctx(ctx), 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.cell_type_index = type_idx; + + fast_bels.resize(type_idx + 1); + auto &bel_data = fast_bels.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(!ctx->checkBelAvail(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); + } + } + + typedef std::vector>> FastBelsData; + + size_t 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.at(cell_type_data.cell_type_index); + return cell_type_data.number_of_possible_bels; + } + + Context *ctx; + int minBelsForGridPick; + + std::unordered_map cell_types; + std::vector fast_bels; +}; + +NEXTPNR_NAMESPACE_END diff --git a/common/place_common.cc b/common/place_common.cc index cb9799b5..fb973e2c 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -118,7 +118,7 @@ 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 +229,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..e2c3dd22 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -43,6 +43,7 @@ #include "place_common.h" #include "timing.h" #include "util.h" +#include "fast_bels.h" namespace std { template <> struct hash> @@ -75,33 +76,12 @@ class SAPlacer }; public: - SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) + SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, 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(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; @@ -170,13 +150,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 +433,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 +632,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 @@ -733,15 +714,15 @@ class SAPlacer 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) + FastBels::FastBelsData *bel_data; + auto type_cnt = fast_bels.getBelsForCellType(targetType, &bel_data); + 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 +1198,7 @@ class SAPlacer int diameter = 35, max_x = 1, max_y = 1; std::unordered_map> bel_types; std::unordered_map region_bounds; - std::vector>>> fast_bels; + FastBels fast_bels; std::unordered_set locked_bels; std::vector net_by_udata; std::vector old_udata; diff --git a/common/placer_heap.cc b/common/placer_heap.cc index f10d4139..4f71577f 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -318,7 +318,7 @@ class HeAPPlacer PlacerHeapCfg cfg; int max_x = 0, max_y = 0; - std::vector>>> fast_bels; + FastBels fast_bels; std::unordered_map> bel_types; // For fast handling of heterogeneity during initial placement without full legalisation, @@ -384,13 +384,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)); @@ -413,31 +414,12 @@ class HeAPPlacer // 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(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(max_y + 1, -1)); @@ -814,8 +796,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 +846,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; } } @@ -888,11 +870,11 @@ class HeAPPlacer // 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 +894,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 +944,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; 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 free_bels_at_loc; std::vector 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) { -- cgit v1.2.3 From b4160c228e789639dc9f434100976c5eb1f95d8d Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 16:48:22 -0800 Subject: Add archcheck for partition methods. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/archcheck.cc | 64 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 64 insertions(+) (limited to 'common') diff --git a/common/archcheck.cc b/common/archcheck.cc index 3c4c3133..1c5d57a0 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 partition names..\n"); + for(PartitionId partition : ctx->getPartitions()) { + IdString name = ctx->getPartitionName(partition); + PartitionId partition2 = ctx->getPartitionByName(name); + if (partition != partition2) { + log_error("partition != partition2, 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_partitions(const Context *ctx) +{ + log_info("Checking partition data.\n"); + + // Partitions should be subsets of BELs that form an exact cover. + // In particular that means cell types in a partition should only be + // placable in that partition. + for(PartitionId partition : ctx->getPartitions()) { + + // Find out which cell types are in this partition. + std::unordered_set cell_types_in_partition; + for(IdString cell_type : ctx->getCellTypes()) { + if(ctx->getPartitionForCellType(cell_type) == partition) { + cell_types_in_partition.insert(cell_type); + } + } + + // Make sure that all cell types in this partition have at least one + // BelId they can be placed at. + std::unordered_set cell_types_unused; + + std::unordered_set bels_in_partition; + for(BelId bel : ctx->getBelsForPartition(partition)) { + PartitionId partition2 = ctx->getPartitionForBel(bel); + log_assert(partition == partition2); + + bels_in_partition.insert(bel); + + // Check to see if a cell type not in this partition can be + // placed at a BEL in this partition. + for(IdString cell_type : ctx->getCellTypes()) { + if(ctx->getPartitionForCellType(cell_type) == partition) { + 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 partition reports a different + // partition. + for(BelId bel : ctx->getBels()) { + if(ctx->getPartitionForBel(bel) != partition) { + log_assert(bels_in_partition.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_partitions(this); } NEXTPNR_NAMESPACE_END -- cgit v1.2.3 From 878fcdd22dfab32234f2537892ae844b2b4495f3 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 18:32:42 -0800 Subject: Implement partitioning in placer_heap. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/fast_bels.h | 85 +++++++++++++-- common/placer_heap.cc | 286 +++++++++++++++++++++++++++++--------------------- common/placer_heap.h | 2 +- 3 files changed, 243 insertions(+), 130 deletions(-) (limited to 'common') diff --git a/common/fast_bels.h b/common/fast_bels.h index 1b769baf..54ac97d9 100644 --- a/common/fast_bels.h +++ b/common/fast_bels.h @@ -28,8 +28,8 @@ 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 CellTypeData { - size_t cell_type_index; + struct TypeData { + size_t type_index; size_t number_of_possible_bels; }; @@ -44,10 +44,10 @@ struct FastBels { size_t type_idx = cell_types.size(); auto &cell_type_data = cell_types[cell_type]; - cell_type_data.cell_type_index = type_idx; + cell_type_data.type_index = type_idx; - fast_bels.resize(type_idx + 1); - auto &bel_data = fast_bels.at(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)) { @@ -62,6 +62,10 @@ struct FastBels { 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; @@ -79,6 +83,54 @@ struct FastBels { } } + void addPartition(PartitionId 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->getPartitionForBel(bel) != partition) { + continue; + } + + type_data.number_of_possible_bels += 1; + } + + for (auto bel : ctx->getBels()) { + if(!ctx->checkBelAvail(bel)) { + continue; + } + + if(ctx->getPartitionForBel(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>> FastBelsData; size_t getBelsForCellType(IdString cell_type, FastBelsData **data) { @@ -91,15 +143,32 @@ struct FastBels { auto cell_type_data = iter->second; - *data = &fast_bels.at(cell_type_data.cell_type_index); + *data = &fast_bels_by_cell_type.at(cell_type_data.type_index); return cell_type_data.number_of_possible_bels; } + size_t getBelsForPartition(PartitionId partition, FastBelsData **data) { + auto iter = partition_types.find(partition); + if(iter == partition_types.end()) { + addPartition(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; int minBelsForGridPick; - std::unordered_map cell_types; - std::vector fast_bels; + std::unordered_map cell_types; + std::vector fast_bels_by_cell_type; + + std::unordered_map partition_types; + std::vector fast_bels_by_partition_type; }; NEXTPNR_NAMESPACE_END diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 4f71577f..d0771fc3 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -50,6 +50,8 @@ #include "placer1.h" #include "timing.h" #include "util.h" +#include "fast_bels.h" + NEXTPNR_NAMESPACE_BEGIN namespace { @@ -136,7 +138,7 @@ template 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, -1) { Eigen::initParallel(); } bool place() { @@ -144,7 +146,7 @@ class HeAPPlacer ctx->lock(); place_constraints(); - build_fast_bels(); + setup_grid(); seed_placement(); update_all_chains(); wirelen_t hpwl = total_hpwl(); @@ -175,24 +177,26 @@ class HeAPPlacer std::vector> solution; - std::vector> heap_runs; - std::unordered_set all_celltypes; - std::unordered_map ct_count; + std::vector> heap_runs; + std::unordered_set all_partitions; + std::unordered_map partition_count; for (auto cell : place_cells) { - if (!all_celltypes.count(cell->type)) { - heap_runs.push_back(std::unordered_set{cell->type}); - all_celltypes.insert(cell->type); + PartitionId partition = ctx->getPartitionForCellType(cell->type); + if (!all_partitions.count(partition)) { + heap_runs.push_back(std::unordered_set{partition}); + all_partitions.insert(partition); } - ct_count[cell->type]++; + partition_count[cell->type]++; } // 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 : partition_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 +205,7 @@ class HeAPPlacer heap_runs.clear(); } - heap_runs.push_back(all_celltypes); + heap_runs.push_back(all_partitions); // The main HeAP placer loop log_info("Running main analytical placer.\n"); while (stalled < 5 && (solved_hpwl <= legal_hpwl * 0.8)) { @@ -238,7 +242,7 @@ class HeAPPlacer for (auto type : sorted(run)) if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(), - [type](const std::unordered_set &grp) { return !grp.count(type); })) + [type](const std::unordered_set &grp) { return !grp.count(type); })) CutSpreader(this, {type}).run(); update_all_chains(); @@ -321,13 +325,6 @@ class HeAPPlacer FastBels fast_bels; std::unordered_map> 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> nearest_row_with_bel; - std::vector> nearest_col_with_bel; - struct BoundingBox { // Actual bounding box @@ -411,8 +408,7 @@ class HeAPPlacer ctx->yield(); } - // Construct the fast_bels, nearest_row_with_bel and nearest_col_with_bel - void build_fast_bels() + void setup_grid() { for (auto bel : ctx->getBels()) { if (!ctx->checkBelAvail(bel)) @@ -422,38 +418,6 @@ class HeAPPlacer max_y = std::max(max_y, loc.y); } - nearest_row_with_bel.resize(num_bel_types, std::vector(max_y + 1, -1)); - nearest_col_with_bel.resize(num_bel_types, std::vector(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; - } - } - // Determine bounding boxes of region constraints for (auto ®ion : sorted(ctx->region)) { Region *r = region.second; @@ -505,15 +469,30 @@ class HeAPPlacer // FIXME: Are there better approaches to the initial placement (e.g. greedy?) void seed_placement() { + std::unordered_set cell_types; + for (const auto &cell : ctx->cells) { + cell_types.insert(cell.second->type); + } + + std::unordered_set bels_used; std::unordered_map> 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()) { @@ -526,21 +505,41 @@ 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)); + if (!available_bels.count(ci->type) || available_bels.at(ci->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)); + } ++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(); + } + + // Find an unused BEL from bels_for_cell_type. + auto &bels_for_cell_type = available_bels.at(ci->type); + BelId bel; + while(true) { + 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 { @@ -548,6 +547,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); } @@ -867,9 +867,6 @@ 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())) continue; if (ny >= int(fb->at(nx).size())) @@ -961,7 +958,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 @@ -1063,13 +1060,17 @@ class HeAPPlacer class CutSpreader { public: - CutSpreader(HeAPPlacer *p, const std::unordered_set &beltype) : p(p), ctx(p->ctx), beltype(beltype) + CutSpreader(HeAPPlacer *p, const std::unordered_set &partitions) : p(p), ctx(p->ctx), partitions(partitions) { + // Get fast BELs data for all partitions being Cut/Spread. 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))))); + for (PartitionId partition : sorted(partitions)) { + type_index[partition] = idx; + FastBels::FastBelsData *fast_bels; + p->fast_bels.getBelsForPartition(partition, &fast_bels); + fb.push_back(fast_bels); ++idx; + NPNR_ASSERT(fb.size() == idx); } } static int seq; @@ -1151,8 +1152,8 @@ class HeAPPlacer private: HeAPPlacer *p; Context *ctx; - std::unordered_set beltype; - std::unordered_map type_index; + std::unordered_set partitions; + std::unordered_map type_index; std::vector>> occupancy; std::vector> groups; std::vector> chaines; @@ -1174,16 +1175,24 @@ class HeAPPlacer return int(fb.at(type)->at(x).at(y).size()); } + bool is_cell_fixed(const CellInfo & cell) const { + return partitions.count(ctx->getPartitionForCellType(cell.type)) == 0; + } + + size_t cell_index(const CellInfo & cell) const { + return type_index.at(ctx->getPartitionForCellType(cell.type)); + } + void init() { occupancy.resize(p->max_x + 1, - std::vector>(p->max_y + 1, std::vector(beltype.size(), 0))); + std::vector>(p->max_y + 1, std::vector(partitions.size(), 0))); groups.resize(p->max_x + 1, std::vector(p->max_y + 1, -1)); chaines.resize(p->max_x + 1, std::vector(p->max_y + 1)); cells_at_location.resize(p->max_x + 1, std::vector>(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(partitions.size()); t++) { occupancy.at(x).at(y).at(t) = 0; } groups.at(x).at(y) = -1; @@ -1201,55 +1210,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 < partitions.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); } @@ -1268,11 +1299,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 < partitions.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; @@ -1302,12 +1334,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 < partitions.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)); @@ -1317,7 +1350,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 < partitions.size(); t++) { reg.bels.push_back(bels_at(x, y, t)); reg.cells.push_back(occ_at(x, y, t)); } @@ -1334,7 +1367,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 < partitions.size(); t++) { if (occ_at(reg.x1 + 1, y1, t) > bels_at(reg.x1 + 1, y1, t)) { over_occ_x = true; break; @@ -1350,7 +1383,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 < partitions.size(); t++) { if (occ_at(x1, reg.y1 + 1, t) > bels_at(x1, reg.y1 + 1, t)) { over_occ_y = true; break; @@ -1412,10 +1445,13 @@ class HeAPPlacer } } if (!changed) { - for (auto bt : sorted(beltype)) { - if (reg.cells > reg.bels) + for (auto partition : sorted(partitions)) { + if (reg.cells > reg.bels) { + IdString partition_name = ctx->getPartitionName(partition); 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(partition)), + partition_name.c_str(ctx)); + } } break; } @@ -1436,7 +1472,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 < partitions.size(); t++) total_bels += bels_at(x, y, t); } } @@ -1488,26 +1524,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 < partitions.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 < partitions.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); @@ -1515,27 +1559,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 left_cells_v(beltype.size(), 0), right_cells_v(beltype.size(), 0); - std::vector left_bels_v(beltype.size(), 0), right_bels_v(r.bels); + std::vector left_cells_v(partitions.size(), 0), right_cells_v(partitions.size(), 0); + std::vector left_bels_v(partitions.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::max(); // std::pair target_cut_bels; - std::vector slither_bels(beltype.size(), 0); + std::vector slither_bels(partitions.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 < partitions.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 < partitions.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 < partitions.size(); t++) { left_bels_v.at(t) += slither_bels.at(t); right_bels_v.at(t) -= slither_bels.at(t); } @@ -1543,7 +1587,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 < partitions.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))); @@ -1557,19 +1601,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 < partitions.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 < partitions.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 < partitions.size(); t++) { right_bels_v.at(t) += bels_at(x, y, t); } } @@ -1589,15 +1633,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..1fc0c6c4 100644 --- a/common/placer_heap.h +++ b/common/placer_heap.h @@ -49,7 +49,7 @@ struct PlacerHeapCfg std::unordered_set 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 From d03d9d839b7e49a4bf3428e949bda85574adf403 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 19:08:14 -0800 Subject: Working compile of ECP5. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/placer_heap.cc | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/placer_heap.cc b/common/placer_heap.cc index d0771fc3..af073873 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -187,7 +187,7 @@ class HeAPPlacer heap_runs.push_back(std::unordered_set{partition}); all_partitions.insert(partition); } - partition_count[cell->type]++; + partition_count[partition]++; } // If more than 98% of cells are one cell type, always solve all at once // Otherwise, follow full HeAP strategy of rotate&all @@ -252,8 +252,10 @@ class HeAPPlacer legal_hpwl = total_hpwl(); auto run_stopt = std::chrono::high_resolution_clock::now(); + + IdString partition_name = ctx->getPartitionName(*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" : partition_name.c_str(ctx)), int(solved_hpwl), int(spread_hpwl), int(legal_hpwl), std::chrono::duration(run_stopt - run_startt).count()); } @@ -558,7 +560,7 @@ class HeAPPlacer } // Setup the cells to be solved, returns the number of rows - int setup_solve_cells(std::unordered_set *celltypes = nullptr) + int setup_solve_cells(std::unordered_set *partitions = nullptr) { int row = 0; solve_cells.clear(); @@ -567,7 +569,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 (partitions && !partitions->count(ctx->getPartitionForCellType(cell->type))) continue; cell->udata = row++; solve_cells.push_back(cell); @@ -958,7 +960,7 @@ class HeAPPlacer if (vc->region != nullptr && vc->region->constr_bels && !vc->region->bels.count(target)) goto fail; CellInfo *bound; - if (target == BelId() || ctx->isValidBelForCellType(vc->type, target)) + if (target == BelId() || !ctx->isValidBelForCellType(vc->type, target)) goto fail; bound = ctx->getBoundBelCell(target); // Chains cannot overlap -- cgit v1.2.3 From 0338368afa369d097dfb35e0705fef10baa3d20e Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 28 Jan 2021 19:24:00 -0800 Subject: Add Partition APIs to ice40, nexus, gowin archs. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/fast_bels.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'common') diff --git a/common/fast_bels.h b/common/fast_bels.h index 54ac97d9..bc8e39bf 100644 --- a/common/fast_bels.h +++ b/common/fast_bels.h @@ -30,7 +30,7 @@ NEXTPNR_NAMESPACE_BEGIN struct FastBels { struct TypeData { size_t type_index; - size_t number_of_possible_bels; + int number_of_possible_bels; }; FastBels(Context *ctx, int minBelsForGridPick) : ctx(ctx), minBelsForGridPick(minBelsForGridPick) {} @@ -133,7 +133,7 @@ struct FastBels { typedef std::vector>> FastBelsData; - size_t getBelsForCellType(IdString cell_type, FastBelsData **data) { + int getBelsForCellType(IdString cell_type, FastBelsData **data) { auto iter = cell_types.find(cell_type); if(iter == cell_types.end()) { addCellType(cell_type); -- cgit v1.2.3 From 16394d3158f6dc608f8fcbbcac96f851824915bd Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 29 Jan 2021 10:02:12 -0800 Subject: Address some compiler warnings. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/placer_heap.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'common') diff --git a/common/placer_heap.cc b/common/placer_heap.cc index af073873..cc9f5c36 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -1065,7 +1065,7 @@ class HeAPPlacer CutSpreader(HeAPPlacer *p, const std::unordered_set &partitions) : p(p), ctx(p->ctx), partitions(partitions) { // Get fast BELs data for all partitions being Cut/Spread. - int idx = 0; + size_t idx = 0; for (PartitionId partition : sorted(partitions)) { type_index[partition] = idx; FastBels::FastBelsData *fast_bels; -- cgit v1.2.3 From 8d9390fc460bf98932afa5ef8362f932b48cf744 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 29 Jan 2021 11:11:05 -0800 Subject: Fix regression in use of FastBels. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/fast_bels.h | 9 +++++---- common/placer1.cc | 17 ++++++++++++++--- common/placer_heap.cc | 22 +++++++++++++++++++--- 3 files changed, 38 insertions(+), 10 deletions(-) (limited to 'common') diff --git a/common/fast_bels.h b/common/fast_bels.h index bc8e39bf..33eb4952 100644 --- a/common/fast_bels.h +++ b/common/fast_bels.h @@ -33,7 +33,7 @@ struct FastBels { int number_of_possible_bels; }; - FastBels(Context *ctx, int minBelsForGridPick) : ctx(ctx), minBelsForGridPick(minBelsForGridPick) {} + 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); @@ -58,7 +58,7 @@ struct FastBels { } for (auto bel : ctx->getBels()) { - if(!ctx->checkBelAvail(bel)) { + if(check_bel_available && !ctx->checkBelAvail(bel)) { continue; } @@ -106,7 +106,7 @@ struct FastBels { } for (auto bel : ctx->getBels()) { - if(!ctx->checkBelAvail(bel)) { + if(check_bel_available && !ctx->checkBelAvail(bel)) { continue; } @@ -162,7 +162,8 @@ struct FastBels { } Context *ctx; - int minBelsForGridPick; + const bool check_bel_available; + const int minBelsForGridPick; std::unordered_map cell_types; std::vector fast_bels_by_cell_type; diff --git a/common/placer1.cc b/common/placer1.cc index e2c3dd22..2d63ea42 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -76,7 +76,7 @@ class SAPlacer }; public: - SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, cfg.minBelsForGridPick), cfg(cfg) + SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg) { for (auto bel : ctx->getBels()) { Loc loc = ctx->getBelLocation(bel); @@ -85,6 +85,16 @@ class SAPlacer } diameter = std::max(max_x, max_y) + 1; + std::unordered_set 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()); @@ -711,11 +721,12 @@ 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); - FastBels::FastBelsData *bel_data; - auto type_cnt = fast_bels.getBelsForCellType(targetType, &bel_data); if (cfg.minBelsForGridPick >= 0 && type_cnt < cfg.minBelsForGridPick) nx = ny = 0; if (nx >= int(bel_data->size())) diff --git a/common/placer_heap.cc b/common/placer_heap.cc index cc9f5c36..00700388 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -138,7 +138,7 @@ template struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, -1) { Eigen::initParallel(); } + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) { Eigen::initParallel(); } bool place() { @@ -146,7 +146,7 @@ class HeAPPlacer ctx->lock(); place_constraints(); - setup_grid(); + build_fast_bels(); seed_placement(); update_all_chains(); wirelen_t hpwl = total_hpwl(); @@ -410,7 +410,7 @@ class HeAPPlacer ctx->yield(); } - void setup_grid() + void build_fast_bels() { for (auto bel : ctx->getBels()) { if (!ctx->checkBelAvail(bel)) @@ -420,6 +420,22 @@ class HeAPPlacer max_y = std::max(max_y, loc.y); } + std::unordered_set cell_types_in_use; + std::unordered_set partitions_in_use; + for (auto cell : sorted(ctx->cells)) { + IdString cell_type = cell.second->type; + cell_types_in_use.insert(cell_type); + PartitionId partition = ctx->getPartitionForCellType(cell_type); + partitions_in_use.insert(partition); + } + + for(auto cell_type : cell_types_in_use) { + fast_bels.addCellType(cell_type); + } + for(auto partition : partitions_in_use) { + fast_bels.addPartition(partition); + } + // Determine bounding boxes of region constraints for (auto ®ion : sorted(ctx->region)) { Region *r = region.second; -- cgit v1.2.3 From 9fe546f279cd643a308322ffa6af622630892315 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 29 Jan 2021 14:55:10 -0800 Subject: Rename Partition -> BelBucket. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/archcheck.cc | 60 ++++++++++++++-------------- common/fast_bels.h | 12 +++--- common/placer_heap.cc | 108 +++++++++++++++++++++++++------------------------- common/placer_heap.h | 2 +- 4 files changed, 91 insertions(+), 91 deletions(-) (limited to 'common') diff --git a/common/archcheck.cc b/common/archcheck.cc index 1c5d57a0..585fcfee 100644 --- a/common/archcheck.cc +++ b/common/archcheck.cc @@ -52,12 +52,12 @@ void archcheck_names(const Context *ctx) } } - log_info("Checking partition names..\n"); - for(PartitionId partition : ctx->getPartitions()) { - IdString name = ctx->getPartitionName(partition); - PartitionId partition2 = ctx->getPartitionByName(name); - if (partition != partition2) { - log_error("partition != partition2, 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)); } } @@ -197,38 +197,38 @@ void archcheck_conn(const Context *ctx) } } -void archcheck_partitions(const Context *ctx) +void archcheck_buckets(const Context *ctx) { - log_info("Checking partition data.\n"); + log_info("Checking bucket data.\n"); - // Partitions should be subsets of BELs that form an exact cover. - // In particular that means cell types in a partition should only be - // placable in that partition. - for(PartitionId partition : ctx->getPartitions()) { + // 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 partition. - std::unordered_set cell_types_in_partition; + // Find out which cell types are in this bucket. + std::unordered_set cell_types_in_bucket; for(IdString cell_type : ctx->getCellTypes()) { - if(ctx->getPartitionForCellType(cell_type) == partition) { - cell_types_in_partition.insert(cell_type); + if(ctx->getBelBucketForCellType(cell_type) == bucket) { + cell_types_in_bucket.insert(cell_type); } } - // Make sure that all cell types in this partition have at least one + // Make sure that all cell types in this bucket have at least one // BelId they can be placed at. std::unordered_set cell_types_unused; - std::unordered_set bels_in_partition; - for(BelId bel : ctx->getBelsForPartition(partition)) { - PartitionId partition2 = ctx->getPartitionForBel(bel); - log_assert(partition == partition2); + std::unordered_set bels_in_bucket; + for(BelId bel : ctx->getBelsInBucket(bucket)) { + BelBucketId bucket2 = ctx->getBelBucketForBel(bel); + log_assert(bucket == bucket2); - bels_in_partition.insert(bel); + bels_in_bucket.insert(bel); - // Check to see if a cell type not in this partition can be - // placed at a BEL in this partition. + // 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->getPartitionForCellType(cell_type) == partition) { + if(ctx->getBelBucketForCellType(cell_type) == bucket) { if(ctx->isValidBelForCellType(cell_type, bel)) { cell_types_unused.erase(cell_type); } @@ -238,11 +238,11 @@ void archcheck_partitions(const Context *ctx) } } - // Verify that any BEL not in this partition reports a different - // partition. + // Verify that any BEL not in this bucket reports a different + // bucket. for(BelId bel : ctx->getBels()) { - if(ctx->getPartitionForBel(bel) != partition) { - log_assert(bels_in_partition.count(bel) == 0); + if(ctx->getBelBucketForBel(bel) != bucket) { + log_assert(bels_in_bucket.count(bel) == 0); } } @@ -262,7 +262,7 @@ void Context::archcheck() const archcheck_names(this); archcheck_locs(this); archcheck_conn(this); - archcheck_partitions(this); + archcheck_buckets(this); } NEXTPNR_NAMESPACE_END diff --git a/common/fast_bels.h b/common/fast_bels.h index 33eb4952..2301bc7d 100644 --- a/common/fast_bels.h +++ b/common/fast_bels.h @@ -83,7 +83,7 @@ struct FastBels { } } - void addPartition(PartitionId partition) { + 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. @@ -98,7 +98,7 @@ struct FastBels { auto &bel_data = fast_bels_by_partition_type.at(type_idx); for (auto bel : ctx->getBels()) { - if(ctx->getPartitionForBel(bel) != partition) { + if(ctx->getBelBucketForBel(bel) != partition) { continue; } @@ -110,7 +110,7 @@ struct FastBels { continue; } - if(ctx->getPartitionForBel(bel) != partition) { + if(ctx->getBelBucketForBel(bel) != partition) { continue; } @@ -147,10 +147,10 @@ struct FastBels { return cell_type_data.number_of_possible_bels; } - size_t getBelsForPartition(PartitionId partition, FastBelsData **data) { + size_t getBelsForBelBucket(BelBucketId partition, FastBelsData **data) { auto iter = partition_types.find(partition); if(iter == partition_types.end()) { - addPartition(partition); + addBelBucket(partition); iter = partition_types.find(partition); NPNR_ASSERT(iter != partition_types.end()); } @@ -168,7 +168,7 @@ struct FastBels { std::unordered_map cell_types; std::vector fast_bels_by_cell_type; - std::unordered_map partition_types; + std::unordered_map partition_types; std::vector fast_bels_by_partition_type; }; diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 00700388..9b581bb1 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -177,21 +177,21 @@ class HeAPPlacer std::vector> solution; - std::vector> heap_runs; - std::unordered_set all_partitions; - std::unordered_map partition_count; + std::vector> heap_runs; + std::unordered_set all_buckets; + std::unordered_map bucket_count; for (auto cell : place_cells) { - PartitionId partition = ctx->getPartitionForCellType(cell->type); - if (!all_partitions.count(partition)) { - heap_runs.push_back(std::unordered_set{partition}); - all_partitions.insert(partition); + BelBucketId bucket = ctx->getBelBucketForCellType(cell->type); + if (!all_buckets.count(bucket)) { + heap_runs.push_back(std::unordered_set{bucket}); + all_buckets.insert(bucket); } - partition_count[partition]++; + 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 : partition_count) { + for (auto &c : bucket_count) { if (c.second >= 0.98 * int(place_cells.size())) { heap_runs.clear(); break; @@ -205,7 +205,7 @@ class HeAPPlacer heap_runs.clear(); } - heap_runs.push_back(all_partitions); + 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)) { @@ -242,7 +242,7 @@ class HeAPPlacer for (auto type : sorted(run)) if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(), - [type](const std::unordered_set &grp) { return !grp.count(type); })) + [type](const std::unordered_set &grp) { return !grp.count(type); })) CutSpreader(this, {type}).run(); update_all_chains(); @@ -253,9 +253,9 @@ class HeAPPlacer legal_hpwl = total_hpwl(); auto run_stopt = std::chrono::high_resolution_clock::now(); - IdString partition_name = ctx->getPartitionName(*run.begin()); + 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" : partition_name.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(run_stopt - run_startt).count()); } @@ -421,19 +421,19 @@ class HeAPPlacer } std::unordered_set cell_types_in_use; - std::unordered_set partitions_in_use; + std::unordered_set buckets_in_use; for (auto cell : sorted(ctx->cells)) { IdString cell_type = cell.second->type; cell_types_in_use.insert(cell_type); - PartitionId partition = ctx->getPartitionForCellType(cell_type); - partitions_in_use.insert(partition); + 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 partition : partitions_in_use) { - fast_bels.addPartition(partition); + for(auto bucket : buckets_in_use) { + fast_bels.addBelBucket(bucket); } // Determine bounding boxes of region constraints @@ -576,7 +576,7 @@ class HeAPPlacer } // Setup the cells to be solved, returns the number of rows - int setup_solve_cells(std::unordered_set *partitions = nullptr) + int setup_solve_cells(std::unordered_set *buckets = nullptr) { int row = 0; solve_cells.clear(); @@ -585,7 +585,7 @@ class HeAPPlacer cell.second->udata = dont_solve; // Then update cells to be placed, which excludes cell children for (auto cell : place_cells) { - if (partitions && !partitions->count(ctx->getPartitionForCellType(cell->type))) + if (buckets && !buckets->count(ctx->getBelBucketForCellType(cell->type))) continue; cell->udata = row++; solve_cells.push_back(cell); @@ -1078,14 +1078,14 @@ class HeAPPlacer class CutSpreader { public: - CutSpreader(HeAPPlacer *p, const std::unordered_set &partitions) : p(p), ctx(p->ctx), partitions(partitions) + CutSpreader(HeAPPlacer *p, const std::unordered_set &buckets) : p(p), ctx(p->ctx), buckets(buckets) { - // Get fast BELs data for all partitions being Cut/Spread. + // Get fast BELs data for all buckets being Cut/Spread. size_t idx = 0; - for (PartitionId partition : sorted(partitions)) { - type_index[partition] = idx; + for (BelBucketId bucket : sorted(buckets)) { + type_index[bucket] = idx; FastBels::FastBelsData *fast_bels; - p->fast_bels.getBelsForPartition(partition, &fast_bels); + p->fast_bels.getBelsForBelBucket(bucket, &fast_bels); fb.push_back(fast_bels); ++idx; NPNR_ASSERT(fb.size() == idx); @@ -1170,8 +1170,8 @@ class HeAPPlacer private: HeAPPlacer *p; Context *ctx; - std::unordered_set partitions; - std::unordered_map type_index; + std::unordered_set buckets; + std::unordered_map type_index; std::vector>> occupancy; std::vector> groups; std::vector> chaines; @@ -1194,23 +1194,23 @@ class HeAPPlacer } bool is_cell_fixed(const CellInfo & cell) const { - return partitions.count(ctx->getPartitionForCellType(cell.type)) == 0; + return buckets.count(ctx->getBelBucketForCellType(cell.type)) == 0; } size_t cell_index(const CellInfo & cell) const { - return type_index.at(ctx->getPartitionForCellType(cell.type)); + return type_index.at(ctx->getBelBucketForCellType(cell.type)); } void init() { occupancy.resize(p->max_x + 1, - std::vector>(p->max_y + 1, std::vector(partitions.size(), 0))); + std::vector>(p->max_y + 1, std::vector(buckets.size(), 0))); groups.resize(p->max_x + 1, std::vector(p->max_y + 1, -1)); chaines.resize(p->max_x + 1, std::vector(p->max_y + 1)); cells_at_location.resize(p->max_x + 1, std::vector>(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(partitions.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; @@ -1292,7 +1292,7 @@ class HeAPPlacer // 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 < partitions.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); } @@ -1317,7 +1317,7 @@ class HeAPPlacer auto process_location = [&](int x, int y) { // Merge with any overlapping regions if (groups.at(x).at(y) == -1) { - for (size_t t = 0; t < partitions.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); } @@ -1352,7 +1352,7 @@ class HeAPPlacer if (groups.at(x).at(y) != -1) continue; bool overutilised = false; - for (size_t t = 0; t < partitions.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; @@ -1368,7 +1368,7 @@ class HeAPPlacer reg.id = id; reg.x0 = reg.x1 = x; reg.y0 = reg.y1 = y; - for (size_t t = 0; t < partitions.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)); } @@ -1385,7 +1385,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 < partitions.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; @@ -1401,7 +1401,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 < partitions.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; @@ -1463,12 +1463,12 @@ class HeAPPlacer } } if (!changed) { - for (auto partition : sorted(partitions)) { + for (auto bucket : sorted(buckets)) { if (reg.cells > reg.bels) { - IdString partition_name = ctx->getPartitionName(partition); + 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(partition)), - partition_name.c_str(ctx)); + reg.x1, reg.y1, reg.cells.at(type_index.at(bucket)), + bucket_name.c_str(ctx)); } } break; @@ -1490,7 +1490,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 < partitions.size(); t++) + for (size_t t = 0; t < buckets.size(); t++) total_bels += bels_at(x, y, t); } } @@ -1543,7 +1543,7 @@ class HeAPPlacer 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 < partitions.size(); t++) { + 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; @@ -1559,7 +1559,7 @@ class HeAPPlacer 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 < partitions.size(); t++) { + 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; @@ -1577,8 +1577,8 @@ class HeAPPlacer return {}; // Now find the initial target cut that minimises utilisation imbalance, whilst // meeting the clearance requirements for any large macros - std::vector left_cells_v(partitions.size(), 0), right_cells_v(partitions.size(), 0); - std::vector left_bels_v(partitions.size(), 0), right_bels_v(r.bels); + std::vector left_cells_v(buckets.size(), 0), right_cells_v(buckets.size(), 0); + std::vector left_bels_v(buckets.size(), 0), right_bels_v(r.bels); for (int i = 0; i <= pivot; i++) 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; @@ -1589,15 +1589,15 @@ class HeAPPlacer int best_tgt_cut = -1; double best_deltaU = std::numeric_limits::max(); // std::pair target_cut_bels; - std::vector slither_bels(partitions.size(), 0); + std::vector slither_bels(buckets.size(), 0); for (int i = trimmed_l; i <= trimmed_r; i++) { - for (size_t t = 0; t < partitions.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 < partitions.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 < partitions.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); } @@ -1605,7 +1605,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 < partitions.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))); @@ -1619,19 +1619,19 @@ class HeAPPlacer return {}; // left_bels = target_cut_bels.first; // right_bels = target_cut_bels.second; - for (size_t t = 0; t < partitions.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 < partitions.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 < partitions.size(); t++) { + for (size_t t = 0; t < buckets.size(); t++) { right_bels_v.at(t) += bels_at(x, y, t); } } diff --git a/common/placer_heap.h b/common/placer_heap.h index 1fc0c6c4..00913062 100644 --- a/common/placer_heap.h +++ b/common/placer_heap.h @@ -49,7 +49,7 @@ struct PlacerHeapCfg std::unordered_set 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 From 9089ee2d1631fe2346143823c2896a2a85a27e8b Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 29 Jan 2021 15:35:00 -0800 Subject: Add pybindings for new APIs. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/arch_pybindings_shared.h | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'common') diff --git a/common/arch_pybindings_shared.h b/common/arch_pybindings_shared.h index 88f95020..b8ea7b17 100644 --- a/common/arch_pybindings_shared.h +++ b/common/arch_pybindings_shared.h @@ -110,3 +110,19 @@ fn_wrapper_0a, pass_through>::def_wrap(ctx_cls, "writeSVG"); + +// const\_range\ getBelBuckets() const +fn_wrapper_0a>::def_wrap(ctx_cls, + "getBelBuckets"); +// BelBucketId getBelBucketForBel(BelId bel) const +fn_wrapper_1a, + conv_from_str>::def_wrap(ctx_cls, "getBelBucketForBel"); +// BelBucketId getBelBucketForCellType(IdString cell\_type) const +fn_wrapper_1a, + conv_from_str>::def_wrap(ctx_cls, "getBelBucketForCellType"); +// const\_range\ getBelsInBucket(BelBucketId bucket) const +fn_wrapper_1a, + conv_from_str>::def_wrap(ctx_cls, "getBelsInBucket"); +// bool isValidBelForCellType(IdString cell\_type, BelId bel) const +fn_wrapper_2a, + conv_from_str, conv_from_str>::def_wrap(ctx_cls, "isValidBelForCellType"); -- cgit v1.2.3 From 1deab29b0591dd23da0c1d5c2c4fd8190abd6920 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 1 Feb 2021 07:26:54 -0800 Subject: Moving missing empty check into initial placement loop. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/placer_heap.cc | 19 ++++++++++++++----- 1 file changed, 14 insertions(+), 5 deletions(-) (limited to 'common') diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 9b581bb1..e14a4660 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -523,20 +523,29 @@ 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 to implement cell type '%s'\n", - ci->name.c_str(ctx), - ci->type.c_str(ctx)); - } ++attempt_count; if (attempt_count > 25000) { log_error("Unable to find a placement location for cell '%s'\n", ci->name.c_str(ctx)); } + // 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)) { -- cgit v1.2.3 From da74a425d23352d7cddf9d1c4b0b7c86dd567c40 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 1 Feb 2021 14:28:32 -0800 Subject: Run "make clangformat". Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/arch_pybindings_shared.h | 12 +++++----- common/archcheck.cc | 20 ++++++++--------- common/fast_bels.h | 45 ++++++++++++++++++++++--------------- common/place_common.cc | 3 ++- common/placer1.cc | 7 +++--- common/placer_heap.cc | 49 ++++++++++++++++++++--------------------- 6 files changed, 73 insertions(+), 63 deletions(-) (limited to 'common') diff --git a/common/arch_pybindings_shared.h b/common/arch_pybindings_shared.h index b8ea7b17..5295c6ab 100644 --- a/common/arch_pybindings_shared.h +++ b/common/arch_pybindings_shared.h @@ -112,17 +112,17 @@ fn_wrapper_2a_v>::def_wrap(ctx_cls, "writeSVG"); // const\_range\ getBelBuckets() const -fn_wrapper_0a>::def_wrap(ctx_cls, - "getBelBuckets"); +fn_wrapper_0a>::def_wrap(ctx_cls, "getBelBuckets"); // BelBucketId getBelBucketForBel(BelId bel) const fn_wrapper_1a, conv_from_str>::def_wrap(ctx_cls, "getBelBucketForBel"); // BelBucketId getBelBucketForCellType(IdString cell\_type) const -fn_wrapper_1a, - conv_from_str>::def_wrap(ctx_cls, "getBelBucketForCellType"); +fn_wrapper_1a, conv_from_str>::def_wrap(ctx_cls, "getBelBucketForCellType"); // const\_range\ getBelsInBucket(BelBucketId bucket) const -fn_wrapper_1a, - conv_from_str>::def_wrap(ctx_cls, "getBelsInBucket"); +fn_wrapper_1a, conv_from_str>::def_wrap(ctx_cls, "getBelsInBucket"); // bool isValidBelForCellType(IdString cell\_type, BelId bel) const fn_wrapper_2a, conv_from_str, conv_from_str>::def_wrap(ctx_cls, "isValidBelForCellType"); diff --git a/common/archcheck.cc b/common/archcheck.cc index 585fcfee..f5760c88 100644 --- a/common/archcheck.cc +++ b/common/archcheck.cc @@ -53,7 +53,7 @@ void archcheck_names(const Context *ctx) } log_info("Checking bucket names..\n"); - for(BelBucketId bucket : ctx->getBelBuckets()) { + for (BelBucketId bucket : ctx->getBelBuckets()) { IdString name = ctx->getBelBucketName(bucket); BelBucketId bucket2 = ctx->getBelBucketByName(name); if (bucket != bucket2) { @@ -204,12 +204,12 @@ void archcheck_buckets(const Context *ctx) // 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()) { + for (BelBucketId bucket : ctx->getBelBuckets()) { // Find out which cell types are in this bucket. std::unordered_set cell_types_in_bucket; - for(IdString cell_type : ctx->getCellTypes()) { - if(ctx->getBelBucketForCellType(cell_type) == bucket) { + for (IdString cell_type : ctx->getCellTypes()) { + if (ctx->getBelBucketForCellType(cell_type) == bucket) { cell_types_in_bucket.insert(cell_type); } } @@ -219,7 +219,7 @@ void archcheck_buckets(const Context *ctx) std::unordered_set cell_types_unused; std::unordered_set bels_in_bucket; - for(BelId bel : ctx->getBelsInBucket(bucket)) { + for (BelId bel : ctx->getBelsInBucket(bucket)) { BelBucketId bucket2 = ctx->getBelBucketForBel(bel); log_assert(bucket == bucket2); @@ -227,9 +227,9 @@ void archcheck_buckets(const Context *ctx) // 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)) { + 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 { @@ -240,8 +240,8 @@ void archcheck_buckets(const Context *ctx) // Verify that any BEL not in this bucket reports a different // bucket. - for(BelId bel : ctx->getBels()) { - if(ctx->getBelBucketForBel(bel) != bucket) { + for (BelId bel : ctx->getBels()) { + if (ctx->getBelBucketForBel(bel) != bucket) { log_assert(bels_in_bucket.count(bel) == 0); } } diff --git a/common/fast_bels.h b/common/fast_bels.h index 2301bc7d..be2852cd 100644 --- a/common/fast_bels.h +++ b/common/fast_bels.h @@ -20,24 +20,30 @@ #pragma once -#include "nextpnr.h" #include +#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 { +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) {} + FastBels(Context *ctx, bool check_bel_available, int minBelsForGridPick) + : ctx(ctx), check_bel_available(check_bel_available), minBelsForGridPick(minBelsForGridPick) + { + } - void addCellType(IdString cell_type) { + void addCellType(IdString cell_type) + { auto iter = cell_types.find(cell_type); - if(iter != cell_types.end()) { + if (iter != cell_types.end()) { // This cell type has already been added to the fast BEL lookup. return; } @@ -50,7 +56,7 @@ struct FastBels { auto &bel_data = fast_bels_by_cell_type.at(type_idx); for (auto bel : ctx->getBels()) { - if(!ctx->isValidBelForCellType(cell_type, bel)) { + if (!ctx->isValidBelForCellType(cell_type, bel)) { continue; } @@ -58,11 +64,11 @@ struct FastBels { } for (auto bel : ctx->getBels()) { - if(check_bel_available && !ctx->checkBelAvail(bel)) { + if (check_bel_available && !ctx->checkBelAvail(bel)) { continue; } - if(!ctx->isValidBelForCellType(cell_type, bel)) { + if (!ctx->isValidBelForCellType(cell_type, bel)) { continue; } @@ -83,9 +89,10 @@ struct FastBels { } } - void addBelBucket(BelBucketId partition) { + void addBelBucket(BelBucketId partition) + { auto iter = partition_types.find(partition); - if(iter != partition_types.end()) { + if (iter != partition_types.end()) { // This partition has already been added to the fast BEL lookup. return; } @@ -98,7 +105,7 @@ struct FastBels { auto &bel_data = fast_bels_by_partition_type.at(type_idx); for (auto bel : ctx->getBels()) { - if(ctx->getBelBucketForBel(bel) != partition) { + if (ctx->getBelBucketForBel(bel) != partition) { continue; } @@ -106,11 +113,11 @@ struct FastBels { } for (auto bel : ctx->getBels()) { - if(check_bel_available && !ctx->checkBelAvail(bel)) { + if (check_bel_available && !ctx->checkBelAvail(bel)) { continue; } - if(ctx->getBelBucketForBel(bel) != partition) { + if (ctx->getBelBucketForBel(bel) != partition) { continue; } @@ -133,9 +140,10 @@ struct FastBels { typedef std::vector>> FastBelsData; - int getBelsForCellType(IdString cell_type, FastBelsData **data) { + int getBelsForCellType(IdString cell_type, FastBelsData **data) + { auto iter = cell_types.find(cell_type); - if(iter == cell_types.end()) { + if (iter == cell_types.end()) { addCellType(cell_type); iter = cell_types.find(cell_type); NPNR_ASSERT(iter != cell_types.end()); @@ -147,9 +155,10 @@ struct FastBels { return cell_type_data.number_of_possible_bels; } - size_t getBelsForBelBucket(BelBucketId partition, FastBelsData **data) { + size_t getBelsForBelBucket(BelBucketId partition, FastBelsData **data) + { auto iter = partition_types.find(partition); - if(iter == partition_types.end()) { + if (iter == partition_types.end()) { addBelBucket(partition); iter = partition_types.find(partition); NPNR_ASSERT(iter != partition_types.end()); diff --git a/common/place_common.cc b/common/place_common.cc index fb973e2c..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->isValidBelForCellType(targetType, bel) && (!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) diff --git a/common/placer1.cc b/common/placer1.cc index 2d63ea42..1c039090 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -39,11 +39,11 @@ #include #include #include +#include "fast_bels.h" #include "log.h" #include "place_common.h" #include "timing.h" #include "util.h" -#include "fast_bels.h" namespace std { template <> struct hash> @@ -76,7 +76,8 @@ class SAPlacer }; public: - SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg) + SAPlacer(Context *ctx, Placer1Cfg cfg) + : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg) { for (auto bel : ctx->getBels()) { Loc loc = ctx->getBelLocation(bel); @@ -91,7 +92,7 @@ class SAPlacer cell_types_in_use.insert(cell_type); } - for(auto cell_type : cell_types_in_use) { + for (auto cell_type : cell_types_in_use) { fast_bels.addCellType(cell_type); } diff --git a/common/placer_heap.cc b/common/placer_heap.cc index e14a4660..d149a5b0 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -44,13 +44,13 @@ #include #include #include +#include "fast_bels.h" #include "log.h" #include "nextpnr.h" #include "place_common.h" #include "placer1.h" #include "timing.h" #include "util.h" -#include "fast_bels.h" NEXTPNR_NAMESPACE_BEGIN @@ -138,7 +138,10 @@ template struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) { Eigen::initParallel(); } + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) + { + Eigen::initParallel(); + } bool place() { @@ -429,10 +432,10 @@ class HeAPPlacer buckets_in_use.insert(bucket); } - for(auto cell_type : cell_types_in_use) { + for (auto cell_type : cell_types_in_use) { fast_bels.addCellType(cell_type); } - for(auto bucket : buckets_in_use) { + for (auto bucket : buckets_in_use) { fast_bels.addBelBucket(bucket); } @@ -500,8 +503,8 @@ class HeAPPlacer continue; } - for(auto cell_type : cell_types) { - if(ctx->isValidBelForCellType(cell_type, bel)) { + for (auto cell_type : cell_types) { + if (ctx->isValidBelForCellType(cell_type, bel)) { available_bels[cell_type].push_back(bel); } } @@ -532,23 +535,21 @@ class HeAPPlacer // 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)); + 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) { + 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)); + 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)) { + if (bels_used.count(candidate_bel)) { // candidate_bel has already been used by another // cell type, skip it. continue; @@ -1202,13 +1203,12 @@ class HeAPPlacer return int(fb.at(type)->at(x).at(y).size()); } - bool is_cell_fixed(const CellInfo & cell) const { + 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)); - } + size_t cell_index(const CellInfo &cell) const { return type_index.at(ctx->getBelBucketForCellType(cell.type)); } void init() { @@ -1239,9 +1239,9 @@ class HeAPPlacer 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)) { + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; } @@ -1261,9 +1261,9 @@ class HeAPPlacer 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)) { + const CellInfo &cell = *ctx->cells.at(cell_name); + const CellLocation &loc = cell_loc.second; + if (is_cell_fixed(cell)) { continue; } @@ -1285,7 +1285,7 @@ class HeAPPlacer } for (auto cell : p->solve_cells) { - if(is_cell_fixed(*cell)) { + if (is_cell_fixed(*cell)) { continue; } @@ -1476,8 +1476,7 @@ class HeAPPlacer 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(bucket)), - bucket_name.c_str(ctx)); + reg.x1, reg.y1, reg.cells.at(type_index.at(bucket)), bucket_name.c_str(ctx)); } } break; -- cgit v1.2.3