aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/fast_bels.h105
-rw-r--r--common/place_common.cc4
-rw-r--r--common/placer1.cc47
-rw-r--r--common/placer_heap.cc46
-rw-r--r--common/timing_opt.cc2
5 files changed, 136 insertions, 68 deletions
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 <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 "nextpnr.h"
+#include <cstddef>
+
+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<std::vector<std::vector<BelId>>> 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<IdString, CellTypeData> cell_types;
+ std::vector<FastBelsData> 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<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>>
@@ -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<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;
@@ -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<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..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<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,
@@ -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<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));
@@ -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<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) {
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-15 02:06:52 +0000