diff options
| -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 | ||||
| -rw-r--r-- | docs/archapi.md | 72 | ||||
| -rw-r--r-- | docs/coding.md | 46 | ||||
| -rw-r--r-- | docs/faq.md | 1 | ||||
| -rw-r--r-- | ecp5/arch.cc | 13 | ||||
| -rw-r--r-- | ecp5/arch.h | 43 | ||||
| -rw-r--r-- | ecp5/arch_pybindings.cc | 2 | ||||
| -rw-r--r-- | ecp5/arch_pybindings.h | 12 | ||||
| -rw-r--r-- | ecp5/archdefs.h | 19 | ||||
| -rw-r--r-- | generic/arch.h | 33 | ||||
| -rw-r--r-- | generic/arch_pybindings.cc | 22 | ||||
| -rw-r--r-- | generic/archdefs.h | 1 | ||||
| -rw-r--r-- | gowin/arch.cc | 9 | ||||
| -rw-r--r-- | gowin/arch.h | 27 | ||||
| -rw-r--r-- | gowin/archdefs.h | 1 | ||||
| -rw-r--r-- | ice40/arch.cc | 13 | ||||
| -rw-r--r-- | ice40/arch.h | 44 | ||||
| -rw-r--r-- | ice40/arch_pybindings.cc | 3 | ||||
| -rw-r--r-- | ice40/arch_pybindings.h | 12 | ||||
| -rw-r--r-- | ice40/archdefs.h | 20 | ||||
| -rw-r--r-- | nexus/arch.cc | 17 | ||||
| -rw-r--r-- | nexus/arch.h | 44 | ||||
| -rw-r--r-- | nexus/arch_pybindings.cc | 3 | ||||
| -rw-r--r-- | nexus/arch_pybindings.h | 12 | ||||
| -rw-r--r-- | nexus/archdefs.h | 20 |
32 files changed, 975 insertions, 204 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) { diff --git a/docs/archapi.md b/docs/archapi.md index a9c38589..49183c63 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -40,6 +40,10 @@ A type representing a wire name. `WireId()` must construct a unique null-value. A type representing a pip name. `PipId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash<PipId>`. +### BelBucketId + +A type representing a bel bucket. `BelBucketId()` must construct a unique null-value. Must provide `==`, `!=`, and `<` operators and a specialization for `std::hash<BelBucketId>`. + ### GroupId A type representing a group name. `GroupId()` must construct a unique null-value. Must provide `==` and `!=` operators and a specialization for `std::hash<GroupId>`. @@ -88,6 +92,14 @@ Get Z dimension for the specified tile for bels. All bels with at specified X an Get Z dimension for the specified tile for pips. All pips with at specified X and Y coordinates must have a Z coordinate in the range `0 .. getTileDimZ(X,Y)-1` (inclusive). +Cell Methods +----------- + +### const\_range\<IdString\> getCellTypes() const + +Get list of cell types that this architecture accepts. + + Bel Methods ----------- @@ -377,7 +389,7 @@ the given dst wire. This should return a low upper bound for the fastest route from `src` to `dst`. Or in other words it should assume an otherwise unused chip (thus "fastest route"). -But it only produces an estimate for that fastest route, not an exact +But it only produces an estimate for that fastest route, not an exact result, and for that estimate it is considered more acceptable to return a slightly too high result and it is considered less acceptable to return a too low result (thus "low upper bound"). @@ -463,21 +475,74 @@ Cell Delay Methods Returns the delay for the specified path through a cell in the `&delay` argument. The method returns false if there is no timing relationship from `fromPort` to `toPort`. -### TimingPortClass getPortTimingClass(const CellInfo *cell, IdString port, int &clockInfoCount) const +### TimingPortClass getPortTimingClass(const CellInfo \*cell, IdString port, int &clockInfoCount) const Return the _timing port class_ of a port. This can be a register or combinational input or output; clock input or output; general startpoint or endpoint; or a port ignored for timing purposes. For register ports, clockInfoCount is set to the number of associated _clock edges_ that can be queried by getPortClockingInfo. -### TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const +### TimingClockingInfo getPortClockingInfo(const CellInfo \*cell, IdString port, int index) const Return the _clocking info_ (including port name of clock, clock polarity and setup/hold/clock-to-out times) of a port. Where ports have more than one clock edge associated with them (such as DDR outputs), `index` can be used to obtain information for all edges. `index` must be in [0, clockInfoCount), behaviour is undefined otherwise. +Bel Buckets Methods +------------------- + +Bel buckets are subsets of BelIds and cell types used by analytic placer to +seperate types of bels during placement. The buckets should form an exact +cover over all BelIds and cell types. + +Each bel bucket should be BelIds and cell types that are roughly +interchangable during placement. Typical buckets are: + - All LUT bels + - All FF bels + - All multipliers bels + - All block RAM bels + - etc. + +The bel buckets will be used during analytic placement for spreading prior to +strict legality enforcement. It is not required that all bels within a bucket +are strictly equivelant. + +Strict legality step will enforce those differences, along with additional +local constraints. `isValidBelForCell`, `isValidBelForCellType`, and +`isBelLocationValid` are used to enforce strict legality checks. + +### const\_range\<BelBucketId\> getBelBuckets() const + +Return a list of all bel buckets on the device. + +### IdString getBelBucketName(BelBucketId bucket) const + +Return the name of this bel bucket. + +### BelBucketId getBelBucketByName(IdString bucket\_name) const + +Return the BelBucketId for the specified bucket name. + +### BelBucketId getBelBucketForBel(BelId bel) const + +Returns the bucket for a particular bel. + +### BelBucketId getBelBucketForCell(IdString cell\_type) const + +Returns the bel bucket for a particular cell type. + +### const\_range\<BelId\> getBelsInBucket(BelBucketId bucket) const + +Return the list of bels within a bucket. + Placer Methods -------------- +### bool isValidBelForCellType(IdString cell\_type, BelId bel) const + +Returns true if the given cell can be bound to the given bel. This check +should be fast, compared with isValidBelForCell. This check should always +return the same value regardless if other cells are placed within the fabric. + ### bool isValidBelForCell(CellInfo \*cell, BelId bel) const Returns true if the given cell can be bound to the given bel, considering @@ -489,7 +554,6 @@ a certain number of different clock signals allowed for a group of bels. Returns true if a bell in the current configuration is valid, i.e. if `isValidBelForCell()` would return true for the current mapping. - ### static const std::string defaultPlacer Name of the default placement algorithm for the architecture, if diff --git a/docs/coding.md b/docs/coding.md index b8025f8b..5cbaef01 100644 --- a/docs/coding.md +++ b/docs/coding.md @@ -14,9 +14,9 @@ This document aims to provide an overview into the philosophy behind nextpnr's c An architecture in nextpnr is described first and foremost as code. The exact details are given in the [Arch API reference](archapi.md); this aims to explain the core concept. -By choosing this approach; this gives architectures significant flexibility to use more advanced database representations than a simple flat database - for example deduplicated approaches that store similar tiles only once. +By choosing this approach; this gives architectures significant flexibility to use more advanced database representations than a simple flat database - for example deduplicated approaches that store similar tiles only once. -Architectures can also implement custom algorithms for packing (or other initial netlist transformations) and specialized parts of placement and routing such as global clock networks. This is because architectures provide the `pack()`, `place()` and `route()` functions, although the latter two will normally use generic algorithms (such as HeAP and router1) to do most of the work. +Architectures can also implement custom algorithms for packing (or other initial netlist transformations) and specialized parts of placement and routing such as global clock networks. This is because architectures provide the `pack()`, `place()` and `route()` functions, although the latter two will normally use generic algorithms (such as HeAP and router1) to do most of the work. Another important function provided by architectures is placement validity checking. This allows the placer to check whether or not a given cell placement is valid. An example of this is for iCE40, where 8 logic cells in a tile share one clock signal - this is checked here. @@ -24,13 +24,13 @@ This function allows architectures in nextpnr to do significantly less packing t Additionally to this; architectures provide functions for checking the availability and conflicts between resources (e.g. `checkBelAvail`, `checkPipAvail`, etc). This enables arbitrary constraints between resource availability to be defined, for example: - - where a group of Pips share bitstream bits, only one can be used at a time + - where a group of pips share bitstream bits, only one can be used at a time - Pips that represent LUT permutation are not available when the LUT is in memory mode - - only a certain total number of Pips in a switchbox can be used at once due to power supply limitations + - only a certain total number of pips in a switchbox can be used at once due to power supply limitations ## `IdString`s -To avoid the high cost of using strings as identifiers directly; almost all "string" identifiers in nextpnr (such as cell names and types) use an indexed string pool type named `IdString`. Unlike Yosys, which has a global garbage collected pool, nextpnr has a per-Context pool without any garbage collection. +To avoid the high cost of using strings as identifiers directly; almost all "string" identifiers in nextpnr (such as cell names and types) use an indexed string pool type named `IdString`. Unlike Yosys, which has a global garbage collected pool, nextpnr has a per-Context pool without any garbage collection. `IdString`s can be created in two ways. Architectures can add `IdString`s with constant indices - allowing `IdString` constants to be provided too - using `initialize_add` at startup. See how `constids.inc` is used in iCE40 for an example of this. The main way to create `IdString`s, however, is at runtime using the `id` member function of `BaseCtx` given the string to create from (if an `IdString` of that string already exists, the existing `IdString` will be returned). @@ -42,15 +42,36 @@ Packing in nextpnr could be done in two ways (if significant packing is done at - replacing multiple cells with a single larger cell that corresponds to a bel - combining smaller cells using relative placement constraints -In flows with minimal packing the main task of the packer is to transform cells into common types that correspond to a bel (e.g. convert multiple flipflop primitives to a single common type with some extra parameters). The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades. +The packer will also have to add relative constraints for fixed structures such as carry chains or LUT-MUX cascades. There are several helper functions that are useful for developing packers and other passes that perform significant netlist modifications in `util.h`. It is often preferable to use these compared to direct modification of the netlist structures due to the "double linking" nextpnr does - e.g. when connecting a port you must update both the `net` field of the ports and the `driver`/`users` of the net. +### Cell to bel mapping + +There is an Arch API choice when it comes to representing the relationship +between cell types and bel types. One option is to transform cells into +common types that correspond to a bel (e.g. convert multiple flipflop +primitives to a single common type with some extra parameters). In Arch APIs +designed like this, packer transformations are required to convert input cell +types into nextpnr specific cell types that have a 1 to 1 relationship with +bel types. + +For Arch APIs of this type, the method `isValidBelForCellType` reduces to: + +``` +bool isValidBelForCellType(IdString cell_type, BelId bel) const { + return cell_type == getBelType(bel); +} +``` + +The alternative is to implement a fast `isValidBelForCellType` method that +determines if this cell type can be bound to this bel. + ## Developing CAD algorithms - placement The job of the placer in nextpnr is to find a suitable bel for each cell in the design; while respecting legality and relative constraints. -Placers might want to create their own indices of bels (for example, bels by type and location) to speed up the search. +Placers might want to create their own indices of bels (for example, bels by type and location) to speed up the search. As nextpnr allows arbitrary constraints on bels for more advanced packer-free flows and complex real-world architectures; placements must be checked for legality using `isValidBelForCell` (before placement) or `isBelLocationValid` (after placement) and the placement rejected if invalid. For analytical placement algorithms; after creating a spread-out AP solution the legality of placing each cell needs to be checked. In practice, the cost of this is fairly low as the architecture should ensure these functions are as fast as possible. @@ -59,6 +80,17 @@ There are several routes for timing information in the placer: - sink ports can have a criticality (value between 0 and 1 where 1 is the critical path) associated with them by using `get_criticalities` and a `NetCriticalityMap` - `predictDelay` returns an estimated delay for a sink port based on placement information + +### Bel Buckets + +The bel Bucket Arch APIs can be used by an analytical placer (AP) for getting +groups of bels and cell types placed together. This grouping is important for +algorithms like HeAP which typically want to do operate on subsets of the +design for some portions of the placement. + +The HeAP implementation allows for multiple bel buckets to be placed on +together, see the "cellGroups" field. + ## Routing The job of the router is to ensure that the `wires` map for each net contains a complete routing tree; populated using the Arch functions to bind wires and pips. The ripup invariants in the [FAQ](faq.md) are important to bear in mind; as there may be complex constraints on the usage of wires and pips in some architectures. diff --git a/docs/faq.md b/docs/faq.md index 8a1b3f6a..085b2bd7 100644 --- a/docs/faq.md +++ b/docs/faq.md @@ -23,6 +23,7 @@ For nextpnr we are using the following terminology. - **Wire**: a fixed physical connection inside the FPGA between Pips and/or Bel pins. - **Alias**: a special automatic-on Pip to represent a permanent connection between two wires - **Group**: a collection of bels, pips, wires, and/or other groups +- **BelBucket**: a collection of bels and cell types. All of the bel buckets form a set cover of bels and cell types. ### Flow Terminology diff --git a/ecp5/arch.cc b/ecp5/arch.cc index 74a1b17f..25f95c53 100644 --- a/ecp5/arch.cc +++ b/ecp5/arch.cc @@ -115,6 +115,19 @@ Arch::Arch(ArchArgs args) : args(args) log_error("Unsupported package '%s' for '%s'.\n", args.package.c_str(), getChipName().c_str()); bel_to_cell.resize(chip_info->height * chip_info->width * max_loc_bels, nullptr); + + std::unordered_set<IdString> bel_types; + for (BelId bel : getBels()) { + bel_types.insert(getBelType(bel)); + } + + for (IdString bel_type : bel_types) { + cell_types.push_back(bel_type); + + BelBucketId bucket; + bucket.name = bel_type; + buckets.push_back(bucket); + } } // ----------------------------------------------------------------------- diff --git a/ecp5/arch.h b/ecp5/arch.h index 58373157..18a70fe8 100644 --- a/ecp5/arch.h +++ b/ecp5/arch.h @@ -950,6 +950,46 @@ struct Arch : BaseCtx // ------------------------------------------------- // Placement validity checks + bool isValidBelForCellType(IdString cell_type, BelId bel) const { return cell_type == getBelType(bel); } + + const std::vector<IdString> &getCellTypes() const { return cell_types; } + + std::vector<BelBucketId> getBelBuckets() const { return buckets; } + + IdString getBelBucketName(BelBucketId bucket) const { return bucket.name; } + + BelBucketId getBelBucketByName(IdString name) const + { + BelBucketId bucket; + bucket.name = name; + return bucket; + } + + BelBucketId getBelBucketForBel(BelId bel) const + { + BelBucketId bucket; + bucket.name = getBelType(bel); + return bucket; + } + + BelBucketId getBelBucketForCellType(IdString cell_type) const + { + BelBucketId bucket; + bucket.name = cell_type; + return bucket; + } + + std::vector<BelId> getBelsInBucket(BelBucketId bucket) const + { + std::vector<BelId> bels; + for (BelId bel : getBels()) { + if (getBelType(bel) == bucket.name) { + bels.push_back(bel); + } + } + return bels; + } + bool isValidBelForCell(CellInfo *cell, BelId bel) const; bool isBelLocationValid(BelId bel) const; @@ -1022,6 +1062,9 @@ struct Arch : BaseCtx static const std::vector<std::string> availablePlacers; static const std::string defaultRouter; static const std::vector<std::string> availableRouters; + + std::vector<IdString> cell_types; + std::vector<BelBucketId> buckets; }; NEXTPNR_NAMESPACE_END diff --git a/ecp5/arch_pybindings.cc b/ecp5/arch_pybindings.cc index 8618bec1..e1adbb46 100644 --- a/ecp5/arch_pybindings.cc +++ b/ecp5/arch_pybindings.cc @@ -59,6 +59,8 @@ void arch_wrap_python(py::module &m) typedef const PipRange UphillPipRange; typedef const PipRange DownhillPipRange; + typedef const std::vector<BelBucketId> &BelBucketRange; + typedef const std::vector<BelId> &BelRangeForBelBucket; #include "arch_pybindings_shared.h" WRAP_RANGE(m, Bel, conv_to_str<BelId>); diff --git a/ecp5/arch_pybindings.h b/ecp5/arch_pybindings.h index cf343976..dd3161ae 100644 --- a/ecp5/arch_pybindings.h +++ b/ecp5/arch_pybindings.h @@ -76,6 +76,18 @@ template <> struct string_converter<PipId> } }; +template <> struct string_converter<BelBucketId> +{ + BelBucketId from_str(Context *ctx, std::string name) { return ctx->getBelBucketByName(ctx->id(name)); } + + std::string to_str(Context *ctx, BelBucketId id) + { + if (id == BelBucketId()) + throw bad_wrap(); + return ctx->getBelBucketName(id).str(ctx); + } +}; + template <> struct string_converter<BelPin> { BelPin from_str(Context *ctx, std::string name) diff --git a/ecp5/archdefs.h b/ecp5/archdefs.h index 586c385f..3bc75ab4 100644 --- a/ecp5/archdefs.h +++ b/ecp5/archdefs.h @@ -126,6 +126,15 @@ struct PipId } }; +struct BelBucketId +{ + IdString name; + + bool operator==(const BelBucketId &other) const { return (name == other.name); } + bool operator!=(const BelBucketId &other) const { return (name != other.name); } + bool operator<(const BelBucketId &other) const { return name < other.name; } +}; + struct GroupId { enum : int8_t @@ -262,4 +271,14 @@ template <> struct hash<NEXTPNR_NAMESPACE_PREFIX DecalId> } }; +template <> struct hash<NEXTPNR_NAMESPACE_PREFIX BelBucketId> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX BelBucketId &partition) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(partition.name)); + return seed; + } +}; + } // namespace std diff --git a/generic/arch.h b/generic/arch.h index 011d7d45..f3e26bb5 100644 --- a/generic/arch.h +++ b/generic/arch.h @@ -271,6 +271,38 @@ struct Arch : BaseCtx bool place(); bool route(); + std::vector<IdString> getCellTypes() const + { + std::vector<IdString> cell_types; + cell_types.reserve(bels.size()); + for (auto bel : bels) { + cell_types.push_back(bel.first); + } + + return cell_types; + } + + std::vector<BelBucketId> getBelBuckets() const { return getCellTypes(); } + + IdString getBelBucketName(BelBucketId bucket) const { return bucket; } + + BelBucketId getBelBucketByName(IdString bucket) const { return bucket; } + + BelBucketId getBelBucketForBel(BelId bel) const { return getBelType(bel); } + + BelBucketId getBelBucketForCellType(IdString cell_type) const { return cell_type; } + + std::vector<BelId> getBelsInBucket(BelBucketId bucket) const + { + std::vector<BelId> bels; + for (BelId bel : getBels()) { + if (bucket == getBelBucketForBel(bel)) { + bels.push_back(bel); + } + } + return bels; + } + const std::vector<GraphicElement> &getDecalGraphics(DecalId decal) const; DecalXY getBelDecal(BelId bel) const; DecalXY getWireDecal(WireId wire) const; @@ -283,6 +315,7 @@ struct Arch : BaseCtx // Get the TimingClockingInfo of a port TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const; + bool isValidBelForCellType(IdString cell_type, BelId bel) const { return cell_type == getBelType(bel); } bool isValidBelForCell(CellInfo *cell, BelId bel) const; bool isBelLocationValid(BelId bel) const; diff --git a/generic/arch_pybindings.cc b/generic/arch_pybindings.cc index 7f7229fd..23f2c05c 100644 --- a/generic/arch_pybindings.cc +++ b/generic/arch_pybindings.cc @@ -226,6 +226,28 @@ void arch_wrap_python(py::module &m) pass_through<DelayInfo>>::def_wrap(ctx_cls, "addCellTimingClockToOut", "cell"_a, "port"_a, "clock"_a, "clktoq"_a); + // const\_range\<BelBucketId\> getBelBuckets() const + fn_wrapper_0a<Context, decltype(&Context::getBelBuckets), &Context::getBelBuckets, + wrap_context<const std::vector<BelBucketId> &>>::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<const std::vector<BelId> &>, 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"); + WRAP_MAP_UPTR(m, CellMap, "IdCellMap"); WRAP_MAP_UPTR(m, NetMap, "IdNetMap"); WRAP_MAP(m, HierarchyMap, wrap_context<HierarchicalCell &>, "HierarchyMap"); diff --git a/generic/archdefs.h b/generic/archdefs.h index 978c9c9b..7623bf40 100644 --- a/generic/archdefs.h +++ b/generic/archdefs.h @@ -51,6 +51,7 @@ typedef IdString WireId; typedef IdString PipId; typedef IdString GroupId; typedef IdString DecalId; +typedef IdString BelBucketId; struct ArchNetInfo { diff --git a/gowin/arch.cc b/gowin/arch.cc index b3a6a47d..5a1a56e3 100644 --- a/gowin/arch.cc +++ b/gowin/arch.cc @@ -739,6 +739,15 @@ Arch::Arch(ArchArgs args) : args(args) } // Dummy for empty decals decal_graphics[IdString()]; + + std::unordered_set<IdString> bel_types; + for (BelId bel : getBels()) { + bel_types.insert(getBelType(bel)); + } + + for (IdString bel_type : bel_types) { + cell_types.push_back(bel_type); + } } void IdString::initialize_arch(const BaseCtx *ctx) diff --git a/gowin/arch.h b/gowin/arch.h index 5591744d..f12c604e 100644 --- a/gowin/arch.h +++ b/gowin/arch.h @@ -422,6 +422,31 @@ struct Arch : BaseCtx // Get the TimingClockingInfo of a port TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const; + bool isValidBelForCellType(IdString cell_type, BelId bel) const { return cell_type == getBelType(bel); } + + const std::vector<IdString> &getCellTypes() const { return cell_types; } + + std::vector<BelBucketId> getBelBuckets() const { return cell_types; } + + IdString getBelBucketName(BelBucketId bucket) const { return bucket; } + + BelBucketId getBelBucketByName(IdString name) const { return name; } + + BelBucketId getBelBucketForBel(BelId bel) const { return getBelType(bel); } + + BelBucketId getBelBucketForCellType(IdString cell_type) const { return cell_type; } + + std::vector<BelId> getBelsInBucket(BelBucketId bucket) const + { + std::vector<BelId> bels; + for (BelId bel : getBels()) { + if (getBelType(bel) == bucket) { + bels.push_back(bel); + } + } + return bels; + } + bool isValidBelForCell(CellInfo *cell, BelId bel) const; bool isBelLocationValid(BelId bel) const; @@ -434,6 +459,8 @@ struct Arch : BaseCtx // Internal usage void assignArchInfo(); bool cellsCompatible(const CellInfo **cells, int count) const; + + std::vector<IdString> cell_types; }; NEXTPNR_NAMESPACE_END diff --git a/gowin/archdefs.h b/gowin/archdefs.h index adeb8a0d..2efe1437 100644 --- a/gowin/archdefs.h +++ b/gowin/archdefs.h @@ -72,6 +72,7 @@ typedef IdString WireId; typedef IdString PipId; typedef IdString GroupId; typedef IdString DecalId; +typedef IdString BelBucketId; struct ArchNetInfo { diff --git a/ice40/arch.cc b/ice40/arch.cc index e450e682..6fe77e4b 100644 --- a/ice40/arch.cc +++ b/ice40/arch.cc @@ -115,6 +115,19 @@ Arch::Arch(ArchArgs args) : args(args) wire_to_net.resize(chip_info->wire_data.size()); pip_to_net.resize(chip_info->pip_data.size()); switches_locked.resize(chip_info->num_switches); + + std::unordered_set<IdString> bel_types; + for (BelId bel : getBels()) { + bel_types.insert(getBelType(bel)); + } + + for (IdString bel_type : bel_types) { + cell_types.push_back(bel_type); + + BelBucketId bucket; + bucket.name = bel_type; + buckets.push_back(bucket); + } } // ----------------------------------------------------------------------- diff --git a/ice40/arch.h b/ice40/arch.h index fbf26e78..fd92d988 100644 --- a/ice40/arch.h +++ b/ice40/arch.h @@ -821,6 +821,47 @@ struct Arch : BaseCtx // Perform placement validity checks, returning false on failure (all // implemented in arch_place.cc) + // Whether this cell type can be placed at this BEL. + bool isValidBelForCellType(IdString cell_type, BelId bel) const { return cell_type == getBelType(bel); } + + const std::vector<IdString> &getCellTypes() const { return cell_types; } + + std::vector<BelBucketId> getBelBuckets() const { return buckets; } + + IdString getBelBucketName(BelBucketId bucket) const { return bucket.name; } + + BelBucketId getBelBucketByName(IdString name) const + { + BelBucketId bucket; + bucket.name = name; + return bucket; + } + + BelBucketId getBelBucketForBel(BelId bel) const + { + BelBucketId bucket; + bucket.name = getBelType(bel); + return bucket; + } + + BelBucketId getBelBucketForCellType(IdString cell_type) const + { + BelBucketId bucket; + bucket.name = cell_type; + return bucket; + } + + std::vector<BelId> getBelsInBucket(BelBucketId bucket) const + { + std::vector<BelId> bels; + for (BelId bel : getBels()) { + if (getBelType(bel) == bucket.name) { + bels.push_back(bel); + } + } + return bels; + } + // Whether or not a given cell can be placed at a given Bel // This is not intended for Bel type checks, but finer-grained constraints // such as conflicting set/reset signals, etc @@ -862,6 +903,9 @@ struct Arch : BaseCtx static const std::vector<std::string> availablePlacers; static const std::string defaultRouter; static const std::vector<std::string> availableRouters; + + std::vector<IdString> cell_types; + std::vector<BelBucketId> buckets; }; void ice40DelayFuzzerMain(Context *ctx); diff --git a/ice40/arch_pybindings.cc b/ice40/arch_pybindings.cc index 921956e8..76ce7590 100644 --- a/ice40/arch_pybindings.cc +++ b/ice40/arch_pybindings.cc @@ -75,6 +75,8 @@ void arch_wrap_python(py::module &m) typedef const PipRange UphillPipRange; typedef const PipRange DownhillPipRange; + typedef const std::vector<BelBucketId> &BelBucketRange; + typedef const std::vector<BelId> &BelRangeForBelBucket; #include "arch_pybindings_shared.h" WRAP_RANGE(m, Bel, conv_to_str<BelId>); @@ -83,7 +85,6 @@ void arch_wrap_python(py::module &m) WRAP_RANGE(m, Pip, conv_to_str<PipId>); WRAP_RANGE(m, BelPin, wrap_context<BelPin>); - WRAP_MAP_UPTR(m, CellMap, "IdCellMap"); WRAP_MAP_UPTR(m, NetMap, "IdNetMap"); WRAP_MAP(m, HierarchyMap, wrap_context<HierarchicalCell &>, "HierarchyMap"); diff --git a/ice40/arch_pybindings.h b/ice40/arch_pybindings.h index cf343976..dd3161ae 100644 --- a/ice40/arch_pybindings.h +++ b/ice40/arch_pybindings.h @@ -76,6 +76,18 @@ template <> struct string_converter<PipId> } }; +template <> struct string_converter<BelBucketId> +{ + BelBucketId from_str(Context *ctx, std::string name) { return ctx->getBelBucketByName(ctx->id(name)); } + + std::string to_str(Context *ctx, BelBucketId id) + { + if (id == BelBucketId()) + throw bad_wrap(); + return ctx->getBelBucketName(id).str(ctx); + } +}; + template <> struct string_converter<BelPin> { BelPin from_str(Context *ctx, std::string name) diff --git a/ice40/archdefs.h b/ice40/archdefs.h index e95953f1..c0a6ac66 100644 --- a/ice40/archdefs.h +++ b/ice40/archdefs.h @@ -170,6 +170,15 @@ struct ArchCellInfo }; }; +struct BelBucketId +{ + IdString name; + + bool operator==(const BelBucketId &other) const { return (name == other.name); } + bool operator!=(const BelBucketId &other) const { return (name != other.name); } + bool operator<(const BelBucketId &other) const { return name < other.name; } +}; + NEXTPNR_NAMESPACE_END namespace std { @@ -213,4 +222,15 @@ template <> struct hash<NEXTPNR_NAMESPACE_PREFIX DecalId> return seed; } }; + +template <> struct hash<NEXTPNR_NAMESPACE_PREFIX BelBucketId> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX BelBucketId &bucket) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(bucket.name)); + return seed; + } +}; + } // namespace std diff --git a/nexus/arch.cc b/nexus/arch.cc index eadfaa4b..95b409bf 100644 --- a/nexus/arch.cc +++ b/nexus/arch.cc @@ -171,6 +171,19 @@ Arch::Arch(ArchArgs args) : args(args) } if (!speed_grade) log_error("Unknown speed grade '%s'.\n", speed.c_str()); + + std::unordered_set<IdString> bel_types; + for (BelId bel : getBels()) { + bel_types.insert(getBelType(bel)); + } + + for (IdString bel_type : bel_types) { + cell_types.push_back(bel_type); + + BelBucketId bucket; + bucket.name = bel_type; + buckets.push_back(bucket); + } } // ----------------------------------------------------------------------- @@ -635,8 +648,8 @@ bool Arch::place() cfg.ioBufTypes.insert(id_SEIO18_CORE); cfg.ioBufTypes.insert(id_OSC_CORE); cfg.cellGroups.emplace_back(); - cfg.cellGroups.back().insert(id_OXIDE_COMB); - cfg.cellGroups.back().insert(id_OXIDE_FF); + cfg.cellGroups.back().insert({id_OXIDE_COMB}); + cfg.cellGroups.back().insert({id_OXIDE_FF}); cfg.beta = 0.5; cfg.criticalityExponent = 7; diff --git a/nexus/arch.h b/nexus/arch.h index 56b48bf3..ee66599a 100644 --- a/nexus/arch.h +++ b/nexus/arch.h @@ -1335,6 +1335,47 @@ struct Arch : BaseCtx // Perform placement validity checks, returning false on failure (all // implemented in arch_place.cc) + // Whether this cell type can be placed at this BEL. + bool isValidBelForCellType(IdString cell_type, BelId bel) const { return cell_type == getBelType(bel); } + + const std::vector<IdString> &getCellTypes() const { return cell_types; } + + std::vector<BelBucketId> getBelBuckets() const { return buckets; } + + IdString getBelBucketName(BelBucketId bucket) const { return bucket.name; } + + BelBucketId getBelBucketByName(IdString name) const + { + BelBucketId bucket; + bucket.name = name; + return bucket; + } + + BelBucketId getBelBucketForBel(BelId bel) const + { + BelBucketId bucket; + bucket.name = getBelType(bel); + return bucket; + } + + BelBucketId getBelBucketForCellType(IdString cell_type) const + { + BelBucketId bucket; + bucket.name = cell_type; + return bucket; + } + + std::vector<BelId> getBelsInBucket(BelBucketId bucket) const + { + std::vector<BelId> bels; + for (BelId bel : getBels()) { + if (getBelType(bel) == bucket.name) { + bels.push_back(bel); + } + } + return bels; + } + // Whether or not a given cell can be placed at a given Bel // This is not intended for Bel type checks, but finer-grained constraints // such as conflicting set/reset signals, etc @@ -1536,6 +1577,9 @@ struct Arch : BaseCtx // ------------------------------------------------- void write_fasm(std::ostream &out) const; + + std::vector<IdString> cell_types; + std::vector<BelBucketId> buckets; }; NEXTPNR_NAMESPACE_END diff --git a/nexus/arch_pybindings.cc b/nexus/arch_pybindings.cc index 1a3890ff..b07031f7 100644 --- a/nexus/arch_pybindings.cc +++ b/nexus/arch_pybindings.cc @@ -55,6 +55,9 @@ void arch_wrap_python(py::module &m) typedef UpDownhillPipRange DownhillPipRange; typedef WireBelPinRange BelPinRange; + typedef const std::vector<BelBucketId> &BelBucketRange; + typedef const std::vector<BelId> &BelRangeForBelBucket; + #include "arch_pybindings_shared.h" WRAP_RANGE(m, Bel, conv_to_str<BelId>); diff --git a/nexus/arch_pybindings.h b/nexus/arch_pybindings.h index 326af306..7694090b 100644 --- a/nexus/arch_pybindings.h +++ b/nexus/arch_pybindings.h @@ -76,6 +76,18 @@ template <> struct string_converter<PipId> } }; +template <> struct string_converter<BelBucketId> +{ + BelBucketId from_str(Context *ctx, std::string name) { return ctx->getBelBucketByName(ctx->id(name)); } + + std::string to_str(Context *ctx, BelBucketId id) + { + if (id == BelBucketId()) + throw bad_wrap(); + return ctx->getBelBucketName(id).str(ctx); + } +}; + template <> struct string_converter<BelPin> { BelPin from_str(Context *ctx, std::string name) diff --git a/nexus/archdefs.h b/nexus/archdefs.h index adc1342c..7e427e06 100644 --- a/nexus/archdefs.h +++ b/nexus/archdefs.h @@ -114,6 +114,15 @@ struct PipId } }; +struct BelBucketId +{ + IdString name; + + bool operator==(const BelBucketId &other) const { return (name == other.name); } + bool operator!=(const BelBucketId &other) const { return (name != other.name); } + bool operator<(const BelBucketId &other) const { return name < other.name; } +}; + struct GroupId { enum : int8_t @@ -250,4 +259,15 @@ template <> struct hash<NEXTPNR_NAMESPACE_PREFIX DecalId> return seed; } }; + +template <> struct hash<NEXTPNR_NAMESPACE_PREFIX BelBucketId> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX BelBucketId &bucket) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(bucket.name)); + return seed; + } +}; + } // namespace std |