aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--common/nextpnr.h4
-rw-r--r--common/place_common.cc346
-rw-r--r--common/place_common.h5
-rw-r--r--common/placer1.cc42
-rw-r--r--common/placer1.h7
-rw-r--r--common/timing.cc12
-rw-r--r--ecp5/arch.cc2
-rw-r--r--ecp5/config.h2
-rw-r--r--ecp5/main.cc6
-rw-r--r--ecp5/place_legaliser.cc26
-rw-r--r--ecp5/place_legaliser.h31
-rw-r--r--generic/arch.cc2
-rw-r--r--generic/place_legaliser.cc26
-rw-r--r--generic/place_legaliser.h31
-rw-r--r--ice40/arch.cc7
-rw-r--r--ice40/arch.h2
-rw-r--r--ice40/chains.cc287
-rw-r--r--ice40/chains.h (renamed from ice40/place_legaliser.h)8
-rw-r--r--ice40/chipdb.py6
-rw-r--r--ice40/main.cc25
-rw-r--r--ice40/pack.cc6
-rw-r--r--ice40/place_legaliser.cc554
22 files changed, 720 insertions, 717 deletions
diff --git a/common/nextpnr.h b/common/nextpnr.h
index f01173e6..c87a98d9 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -281,7 +281,7 @@ struct CellInfo : ArchCellInfo
std::unordered_map<IdString, IdString> pins;
// placement constraints
- CellInfo *constr_parent;
+ CellInfo *constr_parent = nullptr;
std::vector<CellInfo *> constr_children;
const int UNCONSTR = INT_MIN;
int constr_x = UNCONSTR; // this.x - parent.x
@@ -472,7 +472,7 @@ struct Context : Arch, DeterministicRNG
bool force = false;
bool timing_driven = true;
float target_freq = 12e6;
- bool user_freq = false;
+ bool auto_freq = false;
int slack_redist_iter = 0;
Context(ArchArgs args) : Arch(args) {}
diff --git a/common/place_common.cc b/common/place_common.cc
index fd38429f..1baab8a1 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -155,6 +155,9 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
} else {
all_placed = true;
}
+ if (ctx->verbose)
+ log_info(" placed single cell '%s' at '%s'\n", cell->name.c_str(ctx),
+ ctx->getBelName(best_bel).c_str(ctx));
ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK);
cell = ripup_target;
@@ -162,4 +165,347 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
return true;
}
+class ConstraintLegaliseWorker
+{
+ private:
+ Context *ctx;
+ std::set<IdString> rippedCells;
+ std::unordered_map<IdString, Loc> oldLocations;
+ class IncreasingDiameterSearch
+ {
+ public:
+ IncreasingDiameterSearch() : start(0), min(0), max(-1){};
+ IncreasingDiameterSearch(int x) : start(x), min(x), max(x){};
+ IncreasingDiameterSearch(int start, int min, int max) : start(start), min(min), max(max){};
+ bool done() const { return (diameter > (max - min)); };
+ int get() const
+ {
+ int val = start + sign * diameter;
+ val = std::max(val, min);
+ val = std::min(val, max);
+ return val;
+ }
+
+ void next()
+ {
+ if (sign == 0) {
+ sign = 1;
+ diameter = 1;
+ } else if (sign == -1) {
+ sign = 1;
+ if ((start + sign * diameter) > max)
+ sign = -1;
+ ++diameter;
+ } else {
+ sign = -1;
+ if ((start + sign * diameter) < min) {
+ sign = 1;
+ ++diameter;
+ }
+ }
+ }
+
+ void reset()
+ {
+ sign = 0;
+ diameter = 0;
+ }
+
+ private:
+ int start, min, max;
+ int diameter = 0;
+ int sign = 0;
+ };
+
+ typedef std::unordered_map<IdString, Loc> CellLocations;
+
+ // Check if a location would be suitable for a cell and all its constrained children
+ // This also makes a crude attempt to "solve" unconstrained constraints, that is slow and horrible
+ // and will need to be reworked if mixed constrained/unconstrained chains become common
+ bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set<Loc> &usedLocations)
+ {
+ BelId locBel = ctx->getBelByLocation(loc);
+ if (locBel == BelId()) {
+ return false;
+ }
+ if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) {
+ return false;
+ }
+ if (!ctx->checkBelAvail(locBel)) {
+ IdString confCell = ctx->getConflictingBelCell(locBel);
+ if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) {
+ return false;
+ }
+ }
+ usedLocations.insert(loc);
+ for (auto child : cell->constr_children) {
+ IncreasingDiameterSearch xSearch, ySearch, zSearch;
+ if (child->constr_x == child->UNCONSTR) {
+ xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX() - 1);
+ } else {
+ xSearch = IncreasingDiameterSearch(loc.x + child->constr_x);
+ }
+ if (child->constr_y == child->UNCONSTR) {
+ ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY() - 1);
+ } else {
+ ySearch = IncreasingDiameterSearch(loc.y + child->constr_y);
+ }
+ if (child->constr_z == child->UNCONSTR) {
+ zSearch = IncreasingDiameterSearch(loc.z, 0, ctx->getTileDimZ(loc.x, loc.y));
+ } else {
+ if (child->constr_abs_z) {
+ zSearch = IncreasingDiameterSearch(child->constr_z);
+ } else {
+ zSearch = IncreasingDiameterSearch(loc.z + child->constr_z);
+ }
+ }
+ bool success = false;
+ while (!xSearch.done()) {
+ Loc cloc;
+ cloc.x = xSearch.get();
+ cloc.y = ySearch.get();
+ cloc.z = zSearch.get();
+
+ zSearch.next();
+ if (zSearch.done()) {
+ zSearch.reset();
+ ySearch.next();
+ if (ySearch.done()) {
+ ySearch.reset();
+ xSearch.next();
+ }
+ }
+
+ if (usedLocations.count(cloc))
+ continue;
+ if (valid_loc_for(child, cloc, solution, usedLocations)) {
+ success = true;
+ break;
+ }
+ }
+ if (!success) {
+ usedLocations.erase(loc);
+ return false;
+ }
+ }
+ if (solution.count(cell->name))
+ usedLocations.erase(solution.at(cell->name));
+ solution[cell->name] = loc;
+ return true;
+ }
+
+ // Set the strength to locked on all cells in chain
+ void lockdown_chain(CellInfo *root)
+ {
+ root->belStrength = STRENGTH_LOCKED;
+ for (auto child : root->constr_children)
+ lockdown_chain(child);
+ }
+
+ // Legalise placement constraints on a cell
+ bool legalise_cell(CellInfo *cell)
+ {
+ if (cell->constr_parent != nullptr)
+ return true; // Only process chain roots
+ if (constraints_satisfied(cell)) {
+ if (cell->constr_children.size() > 0 || cell->constr_x != cell->UNCONSTR ||
+ cell->constr_y != cell->UNCONSTR || cell->constr_z != cell->UNCONSTR)
+ lockdown_chain(cell);
+ } else {
+ IncreasingDiameterSearch xRootSearch, yRootSearch, zRootSearch;
+ Loc currentLoc;
+ if (cell->bel != BelId())
+ currentLoc = ctx->getBelLocation(cell->bel);
+ else
+ currentLoc = oldLocations[cell->name];
+ if (cell->constr_x == cell->UNCONSTR)
+ xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1);
+ else
+ xRootSearch = IncreasingDiameterSearch(cell->constr_x);
+
+ if (cell->constr_y == cell->UNCONSTR)
+ yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1);
+ else
+ yRootSearch = IncreasingDiameterSearch(cell->constr_y);
+
+ if (cell->constr_z == cell->UNCONSTR)
+ zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileDimZ(currentLoc.x, currentLoc.y));
+ else
+ zRootSearch = IncreasingDiameterSearch(cell->constr_z);
+ while (!xRootSearch.done()) {
+ Loc rootLoc;
+
+ rootLoc.x = xRootSearch.get();
+ rootLoc.y = yRootSearch.get();
+ rootLoc.z = zRootSearch.get();
+ zRootSearch.next();
+ if (zRootSearch.done()) {
+ zRootSearch.reset();
+ yRootSearch.next();
+ if (yRootSearch.done()) {
+ yRootSearch.reset();
+ xRootSearch.next();
+ }
+ }
+
+ CellLocations solution;
+ std::unordered_set<Loc> used;
+ if (valid_loc_for(cell, rootLoc, solution, used)) {
+ for (auto cp : solution) {
+ // First unbind all cells
+ if (ctx->cells.at(cp.first)->bel != BelId())
+ ctx->unbindBel(ctx->cells.at(cp.first)->bel);
+ }
+ for (auto cp : solution) {
+ if (ctx->verbose)
+ log_info(" placing '%s' at (%d, %d, %d)\n", cp.first.c_str(ctx), cp.second.x,
+ cp.second.y, cp.second.z);
+ BelId target = ctx->getBelByLocation(cp.second);
+ if (!ctx->checkBelAvail(target)) {
+ IdString conflicting = ctx->getConflictingBelCell(target);
+ if (conflicting != IdString()) {
+ CellInfo *confl_cell = ctx->cells.at(conflicting).get();
+ if (ctx->verbose)
+ log_info(" '%s' already placed at '%s'\n", conflicting.c_str(ctx),
+ ctx->getBelName(confl_cell->bel).c_str(ctx));
+ NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG);
+ ctx->unbindBel(target);
+ rippedCells.insert(conflicting);
+ }
+ }
+ ctx->bindBel(target, cp.first, STRENGTH_LOCKED);
+ rippedCells.erase(cp.first);
+ }
+ NPNR_ASSERT(constraints_satisfied(cell));
+ return true;
+ }
+ }
+ return false;
+ }
+ return true;
+ }
+
+ // Check if constraints are currently satisfied on a cell and its children
+ bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; }
+
+ public:
+ ConstraintLegaliseWorker(Context *ctx) : ctx(ctx){};
+
+ void print_chain(CellInfo *cell, int depth = 0)
+ {
+ for (int i = 0; i < depth; i++)
+ log(" ");
+ log("'%s' (", cell->name.c_str(ctx));
+ if (cell->constr_x != cell->UNCONSTR)
+ log("%d, ", cell->constr_x);
+ else
+ log("*, ");
+ if (cell->constr_y != cell->UNCONSTR)
+ log("%d, ", cell->constr_y);
+ else
+ log("*, ");
+ if (cell->constr_z != cell->UNCONSTR)
+ log("%d", cell->constr_z);
+ else
+ log("*");
+ log(")\n");
+ for (auto child : cell->constr_children)
+ print_chain(child, depth + 1);
+ }
+
+ void print_stats(const char *point)
+ {
+ float distance_sum = 0;
+ float max_distance = 0;
+ int moved_cells = 0;
+ int unplaced_cells = 0;
+ for (auto orig : oldLocations) {
+ if (ctx->cells.at(orig.first)->bel == BelId()) {
+ unplaced_cells++;
+ continue;
+ }
+ Loc newLoc = ctx->getBelLocation(ctx->cells.at(orig.first)->bel);
+ if (newLoc != orig.second) {
+ float distance = std::sqrt(std::pow(newLoc.x - orig.second.x, 2) + pow(newLoc.y - orig.second.y, 2));
+ moved_cells++;
+ distance_sum += distance;
+ if (distance > max_distance)
+ max_distance = distance;
+ }
+ }
+ log_info(" moved %d cells, %d unplaced (after %s)\n", moved_cells, unplaced_cells, point);
+ if (moved_cells > 0) {
+ log_info(" average distance %f\n", (distance_sum / moved_cells));
+ log_info(" maximum distance %f\n", max_distance);
+ }
+ }
+
+ bool legalise_constraints()
+ {
+ log_info("Legalising relative constraints...\n");
+ for (auto cell : sorted(ctx->cells)) {
+ oldLocations[cell.first] = ctx->getBelLocation(cell.second->bel);
+ }
+ for (auto cell : sorted(ctx->cells)) {
+ bool res = legalise_cell(cell.second);
+ if (!res) {
+ if (ctx->verbose)
+ print_chain(cell.second);
+ log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx));
+ return false;
+ }
+ }
+ print_stats("after legalising chains");
+ for (auto rippedCell : rippedCells) {
+ bool res = place_single_cell(ctx, ctx->cells.at(rippedCell).get(), true);
+ if (!res) {
+ log_error("failed to place cell '%s' after relative constraint legalisation\n", rippedCell.c_str(ctx));
+ return false;
+ }
+ }
+ print_stats("after replacing ripped up cells");
+ for (auto cell : sorted(ctx->cells))
+ if (get_constraints_distance(ctx, cell.second) != 0)
+ log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx),
+ ctx->getBelName(cell.second->bel).c_str(ctx));
+ return true;
+ }
+};
+
+bool legalise_relative_constraints(Context *ctx) { return ConstraintLegaliseWorker(ctx).legalise_constraints(); }
+
+// Get the total distance from satisfied constraints for a cell
+int get_constraints_distance(const Context *ctx, const CellInfo *cell)
+{
+ int dist = 0;
+ if (cell->bel == BelId())
+ return 100000;
+ Loc loc = ctx->getBelLocation(cell->bel);
+ if (cell->constr_parent == nullptr) {
+ if (cell->constr_x != cell->UNCONSTR)
+ dist += std::abs(cell->constr_x - loc.x);
+ if (cell->constr_y != cell->UNCONSTR)
+ dist += std::abs(cell->constr_y - loc.y);
+ if (cell->constr_z != cell->UNCONSTR)
+ dist += std::abs(cell->constr_z - loc.z);
+ } else {
+ if (cell->constr_parent->bel == BelId())
+ return 100000;
+ Loc parent_loc = ctx->getBelLocation(cell->constr_parent->bel);
+ if (cell->constr_x != cell->UNCONSTR)
+ dist += std::abs(cell->constr_x - (loc.x - parent_loc.x));
+ if (cell->constr_y != cell->UNCONSTR)
+ dist += std::abs(cell->constr_y - (loc.y - parent_loc.y));
+ if (cell->constr_z != cell->UNCONSTR) {
+ if (cell->constr_abs_z)
+ dist += std::abs(cell->constr_z - loc.z);
+ else
+ dist += std::abs(cell->constr_z - (loc.z - parent_loc.z));
+ }
+ }
+ for (auto child : cell->constr_children)
+ dist += get_constraints_distance(ctx, child);
+ return dist;
+}
+
NEXTPNR_NAMESPACE_END
diff --git a/common/place_common.h b/common/place_common.h
index 32250604..79dec067 100644
--- a/common/place_common.h
+++ b/common/place_common.h
@@ -44,6 +44,11 @@ wirelen_t get_cell_metric_at_bel(const Context *ctx, CellInfo *cell, BelId bel,
// Place a single cell in the lowest wirelength Bel available, optionally requiring validity check
bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality);
+// Modify a design s.t. all relative placement constraints are satisfied
+bool legalise_relative_constraints(Context *ctx);
+
+// Get the total distance from satisfied constraints for a cell
+int get_constraints_distance(const Context *ctx, const CellInfo *cell);
NEXTPNR_NAMESPACE_END
#endif
diff --git a/common/placer1.cc b/common/placer1.cc
index fc679b50..32074220 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -38,15 +38,15 @@
#include <vector>
#include "log.h"
#include "place_common.h"
-#include "place_legaliser.h"
#include "timing.h"
#include "util.h"
+
NEXTPNR_NAMESPACE_BEGIN
class SAPlacer
{
public:
- SAPlacer(Context *ctx) : ctx(ctx)
+ SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg)
{
int num_bel_types = 0;
for (auto bel : ctx->getBels()) {
@@ -225,7 +225,7 @@ class SAPlacer
// Once cooled below legalise threshold, run legalisation and start requiring
// legal moves only
if (temp < legalise_temp && !require_legal) {
- legalise_design(ctx);
+ legalise_relative_constraints(ctx);
require_legal = true;
autoplaced.clear();
for (auto cell : sorted(ctx->cells)) {
@@ -272,6 +272,10 @@ class SAPlacer
}
}
}
+ for (auto cell : sorted(ctx->cells))
+ if (get_constraints_distance(ctx, cell.second) != 0)
+ log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx),
+ ctx->getBelName(cell.second->bel).c_str(ctx));
timing_analysis(ctx, true /* print_fmax */);
ctx->unlock();
return true;
@@ -294,7 +298,7 @@ class SAPlacer
}
BelType targetType = ctx->belTypeFromId(cell->type);
for (auto bel : ctx->getBels()) {
- if (ctx->getBelType(bel) == targetType && (ctx->isValidBelForCell(cell, bel) || !require_legal)) {
+ if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) {
if (ctx->checkBelAvail(bel)) {
uint64_t score = ctx->rng64();
if (score <= best_score) {
@@ -343,6 +347,10 @@ class SAPlacer
if (other_cell->belStrength > STRENGTH_WEAK)
return false;
}
+ int old_dist = get_constraints_distance(ctx, cell);
+ int new_dist;
+ if (other != IdString())
+ old_dist += get_constraints_distance(ctx, other_cell);
wirelen_t new_metric = 0, delta;
ctx->unbindBel(oldBel);
if (other != IdString()) {
@@ -364,13 +372,11 @@ class SAPlacer
if (other != IdString()) {
ctx->bindBel(oldBel, other_cell->name, STRENGTH_WEAK);
}
- if (require_legal) {
- if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) {
- ctx->unbindBel(newBel);
- if (other != IdString())
- ctx->unbindBel(oldBel);
- goto swap_fail;
- }
+ if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) {
+ ctx->unbindBel(newBel);
+ if (other != IdString())
+ ctx->unbindBel(oldBel);
+ goto swap_fail;
}
new_metric = curr_metric;
@@ -383,7 +389,12 @@ class SAPlacer
new_metric += net_new_wl;
new_lengths.push_back(std::make_pair(net->name, net_new_wl));
}
+
+ new_dist = get_constraints_distance(ctx, cell);
+ if (other != IdString())
+ new_dist += get_constraints_distance(ctx, other_cell);
delta = new_metric - curr_metric;
+ delta += (cfg.constraintWeight / temp) * (new_dist - old_dist);
n_move++;
// SA acceptance criterea
if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
@@ -444,14 +455,15 @@ class SAPlacer
std::unordered_set<BelId> locked_bels;
bool require_legal = false;
const float legalise_temp = 1;
- const float post_legalise_temp = 20;
- const float post_legalise_dia_scale = 2;
+ const float post_legalise_temp = 10;
+ const float post_legalise_dia_scale = 1.5;
+ Placer1Cfg cfg;
};
-bool placer1(Context *ctx)
+bool placer1(Context *ctx, Placer1Cfg cfg)
{
try {
- SAPlacer placer(ctx);
+ SAPlacer placer(ctx, cfg);
placer.place();
log_info("Checksum: 0x%08x\n", ctx->checksum());
#ifndef NDEBUG
diff --git a/common/placer1.h b/common/placer1.h
index 477fae56..d8f64b84 100644
--- a/common/placer1.h
+++ b/common/placer1.h
@@ -23,7 +23,12 @@
NEXTPNR_NAMESPACE_BEGIN
-extern bool placer1(Context *ctx);
+struct Placer1Cfg
+{
+ float constraintWeight = 10;
+};
+
+extern bool placer1(Context *ctx, Placer1Cfg cfg);
NEXTPNR_NAMESPACE_END
diff --git a/common/timing.cc b/common/timing.cc
index 9777ab7d..f422ee91 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -125,7 +125,7 @@ void assign_budget(Context *ctx, bool quiet)
{
if (!quiet) {
log_break();
- log_info("Annotating ports with timing budgets\n");
+ log_info("Annotating ports with timing budgets for target frequency %.2f MHz\n", ctx->target_freq/1e6);
}
// Clear delays to a very high value first
@@ -142,7 +142,7 @@ void assign_budget(Context *ctx, bool quiet)
for (auto &net : ctx->nets) {
for (auto &user : net.second->users) {
// Post-update check
- if (ctx->user_freq && user.budget < 0)
+ if (!ctx->auto_freq && user.budget < 0)
log_warning("port %s.%s, connected to net '%s', has negative "
"timing budget of %fns\n",
user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
@@ -159,11 +159,11 @@ void assign_budget(Context *ctx, bool quiet)
// For slack redistribution, if user has not specified a frequency
// dynamically adjust the target frequency to be the currently
// achieved maximum
- if (!ctx->user_freq && ctx->slack_redist_iter > 0) {
+ if (ctx->auto_freq && ctx->slack_redist_iter > 0) {
ctx->target_freq = 1e12 / (default_slack - min_slack);
- /*if (ctx->verbose)*/
- log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack,
- ctx->target_freq / 1e6);
+ if (ctx->verbose)
+ log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack,
+ ctx->target_freq / 1e6);
}
if (!quiet)
diff --git a/ecp5/arch.cc b/ecp5/arch.cc
index 262f43fe..377b8665 100644
--- a/ecp5/arch.cc
+++ b/ecp5/arch.cc
@@ -426,7 +426,7 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de
// -----------------------------------------------------------------------
-bool Arch::place() { return placer1(getCtx()); }
+bool Arch::place() { return placer1(getCtx(), Placer1Cfg()); }
bool Arch::route()
{
diff --git a/ecp5/config.h b/ecp5/config.h
index 038ddbf0..3d2ef971 100644
--- a/ecp5/config.h
+++ b/ecp5/config.h
@@ -20,8 +20,8 @@
#ifndef ECP5_CONFIG_H
#define ECP5_CONFIG_H
-#include "nextpnr.h"
#include <map>
+#include "nextpnr.h"
NEXTPNR_NAMESPACE_BEGIN
diff --git a/ecp5/main.cc b/ecp5/main.cc
index f40a5e61..dac7a635 100644
--- a/ecp5/main.cc
+++ b/ecp5/main.cc
@@ -162,12 +162,8 @@ int main(int argc, char *argv[])
if (!ctx->pack() && !ctx->force)
log_error("Packing design failed.\n");
- if (vm.count("freq")) {
+ if (vm.count("freq"))
ctx->target_freq = vm["freq"].as<double>() * 1e6;
- ctx->user_freq = true;
- } else {
- log_warning("Target frequency not specified. Will optimise for max frequency.\n");
- }
assign_budget(ctx.get());
ctx->check();
print_utilisation(ctx.get());
diff --git a/ecp5/place_legaliser.cc b/ecp5/place_legaliser.cc
deleted file mode 100644
index 0d23f15b..00000000
--- a/ecp5/place_legaliser.cc
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * 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.
- *
- */
-
-#include "place_legaliser.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-bool legalise_design(Context *ctx) { return true; }
-
-NEXTPNR_NAMESPACE_END
diff --git a/ecp5/place_legaliser.h b/ecp5/place_legaliser.h
deleted file mode 100644
index 5f4df6aa..00000000
--- a/ecp5/place_legaliser.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * 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.
- *
- */
-
-#ifndef PLACE_LEGALISER_H
-#define PLACE_LEGALISER_H
-
-#include "nextpnr.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-bool legalise_design(Context *ctx);
-
-NEXTPNR_NAMESPACE_END
-
-#endif
diff --git a/generic/arch.cc b/generic/arch.cc
index 1c22dbf7..f9133f9e 100644
--- a/generic/arch.cc
+++ b/generic/arch.cc
@@ -412,7 +412,7 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de
// ---------------------------------------------------------------
-bool Arch::place() { return placer1(getCtx()); }
+bool Arch::place() { return placer1(getCtx()\, Placer1Cfg()); }
bool Arch::route() { return router1(getCtx(), Router1Cfg()); }
diff --git a/generic/place_legaliser.cc b/generic/place_legaliser.cc
deleted file mode 100644
index 0d23f15b..00000000
--- a/generic/place_legaliser.cc
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * 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.
- *
- */
-
-#include "place_legaliser.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-bool legalise_design(Context *ctx) { return true; }
-
-NEXTPNR_NAMESPACE_END
diff --git a/generic/place_legaliser.h b/generic/place_legaliser.h
deleted file mode 100644
index 5f4df6aa..00000000
--- a/generic/place_legaliser.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * 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.
- *
- */
-
-#ifndef PLACE_LEGALISER_H
-#define PLACE_LEGALISER_H
-
-#include "nextpnr.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-bool legalise_design(Context *ctx);
-
-NEXTPNR_NAMESPACE_END
-
-#endif
diff --git a/ice40/arch.cc b/ice40/arch.cc
index ec1a6a65..2430b7ce 100644
--- a/ice40/arch.cc
+++ b/ice40/arch.cc
@@ -698,7 +698,12 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de
// -----------------------------------------------------------------------
-bool Arch::place() { return placer1(getCtx()); }
+bool Arch::place()
+{
+ Placer1Cfg cfg;
+ cfg.constraintWeight = placer_constraintWeight;
+ return placer1(getCtx(), cfg);
+}
bool Arch::route()
{
diff --git a/ice40/arch.h b/ice40/arch.h
index 50905098..0be76296 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -838,6 +838,8 @@ struct Arch : BaseCtx
}
NPNR_ASSERT_FALSE("Expected PLL pin to share an output with an SB_IO D_IN_{0,1}");
}
+
+ float placer_constraintWeight = 10;
};
NEXTPNR_NAMESPACE_END
diff --git a/ice40/chains.cc b/ice40/chains.cc
new file mode 100644
index 00000000..8638a96c
--- /dev/null
+++ b/ice40/chains.cc
@@ -0,0 +1,287 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * 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.
+ *
+ */
+
+#include "chains.h"
+#include <algorithm>
+#include <vector>
+#include "cells.h"
+#include "design_utils.h"
+#include "log.h"
+#include "place_common.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct CellChain
+{
+ std::vector<CellInfo *> cells;
+};
+
+// Generic chain finder
+template <typename F1, typename F2, typename F3>
+std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next,
+ size_t min_length = 2)
+{
+ std::set<IdString> chained;
+ std::vector<CellChain> chains;
+ for (auto cell : sorted(ctx->cells)) {
+ if (chained.find(cell.first) != chained.end())
+ continue;
+ CellInfo *ci = cell.second;
+ if (cell_type_predicate(ctx, ci)) {
+ CellInfo *start = ci;
+ CellInfo *prev_start = ci;
+ while (prev_start != nullptr) {
+ start = prev_start;
+ prev_start = get_previous(ctx, start);
+ }
+ CellChain chain;
+ CellInfo *end = start;
+ while (end != nullptr) {
+ chain.cells.push_back(end);
+ end = get_next(ctx, end);
+ }
+ if (chain.cells.size() >= min_length) {
+ chains.push_back(chain);
+ for (auto c : chain.cells)
+ chained.insert(c->name);
+ }
+ }
+ }
+ return chains;
+}
+
+class ChainConstrainer
+{
+ private:
+ Context *ctx;
+ // Split a carry chain into multiple legal chains
+ std::vector<CellChain> split_carry_chain(CellChain &carryc)
+ {
+ bool start_of_chain = true;
+ std::vector<CellChain> chains;
+ std::vector<const CellInfo *> tile;
+ const int max_length = (ctx->chip_info->height - 2) * 8 - 2;
+ auto curr_cell = carryc.cells.begin();
+ while (curr_cell != carryc.cells.end()) {
+ CellInfo *cell = *curr_cell;
+ if (tile.size() >= 8) {
+ tile.clear();
+ }
+ if (start_of_chain) {
+ tile.clear();
+ chains.emplace_back();
+ start_of_chain = false;
+ if (cell->ports.at(ctx->id("CIN")).net) {
+ // CIN is not constant and not part of a chain. Must feed in from fabric
+ CellInfo *feedin = make_carry_feed_in(cell, cell->ports.at(ctx->id("CIN")));
+ chains.back().cells.push_back(feedin);
+ tile.push_back(feedin);
+ }
+ }
+ tile.push_back(cell);
+ chains.back().cells.push_back(cell);
+ bool split_chain = (!ctx->logicCellsCompatible(tile)) || (int(chains.back().cells.size()) > max_length);
+ if (split_chain) {
+ CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT")));
+ tile.pop_back();
+ chains.back().cells.back() = passout;
+ start_of_chain = true;
+ } else {
+ NetInfo *carry_net = cell->ports.at(ctx->id("COUT")).net;
+ bool at_end = (curr_cell == carryc.cells.end() - 1);
+ if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) {
+ if (carry_net->users.size() > 2 ||
+ (net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), false) !=
+ net_only_drives(ctx, carry_net, is_lc, ctx->id("CIN"), false)) ||
+ (at_end && !net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), true))) {
+ CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT")));
+ chains.back().cells.push_back(passout);
+ tile.push_back(passout);
+ start_of_chain = true;
+ }
+ }
+ ++curr_cell;
+ }
+ }
+ return chains;
+ }
+
+ // Insert a logic cell to legalise a COUT->fabric connection
+ CellInfo *make_carry_pass_out(PortInfo &cout_port)
+ {
+ NPNR_ASSERT(cout_port.net != nullptr);
+ std::unique_ptr<CellInfo> lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC"));
+ lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3
+ lc->params[ctx->id("CARRY_ENABLE")] = "1";
+ lc->ports.at(ctx->id("O")).net = cout_port.net;
+ std::unique_ptr<NetInfo> co_i3_net(new NetInfo());
+ co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3");
+ co_i3_net->driver = cout_port.net->driver;
+ PortRef i3_r;
+ i3_r.port = ctx->id("I3");
+ i3_r.cell = lc.get();
+ co_i3_net->users.push_back(i3_r);
+ PortRef o_r;
+ o_r.port = ctx->id("O");
+ o_r.cell = lc.get();
+ cout_port.net->driver = o_r;
+ lc->ports.at(ctx->id("I3")).net = co_i3_net.get();
+ cout_port.net = co_i3_net.get();
+
+ IdString co_i3_name = co_i3_net->name;
+ NPNR_ASSERT(ctx->nets.find(co_i3_name) == ctx->nets.end());
+ ctx->nets[co_i3_name] = std::move(co_i3_net);
+ IdString name = lc->name;
+ ctx->assignCellInfo(lc.get());
+ ctx->cells[lc->name] = std::move(lc);
+ return ctx->cells[name].get();
+ }
+
+ // Insert a logic cell to legalise a CIN->fabric connection
+ CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port)
+ {
+ NPNR_ASSERT(cin_port.net != nullptr);
+ std::unique_ptr<CellInfo> lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC"));
+ lc->params[ctx->id("CARRY_ENABLE")] = "1";
+ lc->params[ctx->id("CIN_CONST")] = "1";
+ lc->params[ctx->id("CIN_SET")] = "1";
+ lc->ports.at(ctx->id("I1")).net = cin_port.net;
+ cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(),
+ [cin_cell, cin_port](const PortRef &usr) {
+ return usr.cell == cin_cell && usr.port == cin_port.name;
+ }));
+
+ PortRef i1_ref;
+ i1_ref.cell = lc.get();
+ i1_ref.port = ctx->id("I1");
+ lc->ports.at(ctx->id("I1")).net->users.push_back(i1_ref);
+
+ std::unique_ptr<NetInfo> out_net(new NetInfo());
+ out_net->name = ctx->id(lc->name.str(ctx) + "$O");
+
+ PortRef drv_ref;
+ drv_ref.port = ctx->id("COUT");
+ drv_ref.cell = lc.get();
+ out_net->driver = drv_ref;
+ lc->ports.at(ctx->id("COUT")).net = out_net.get();
+
+ PortRef usr_ref;
+ usr_ref.port = cin_port.name;
+ usr_ref.cell = cin_cell;
+ out_net->users.push_back(usr_ref);
+ cin_cell->ports.at(cin_port.name).net = out_net.get();
+
+ IdString out_net_name = out_net->name;
+ NPNR_ASSERT(ctx->nets.find(out_net_name) == ctx->nets.end());
+ ctx->nets[out_net_name] = std::move(out_net);
+
+ IdString name = lc->name;
+ ctx->assignCellInfo(lc.get());
+ ctx->cells[lc->name] = std::move(lc);
+ return ctx->cells[name].get();
+ }
+
+ void process_carries()
+ {
+ std::vector<CellChain> carry_chains =
+ find_chains(ctx, [](const Context *ctx, const CellInfo *cell) { return is_lc(ctx, cell); },
+ [](const Context *ctx, const
+
+ CellInfo *cell) {
+ CellInfo *carry_prev =
+ net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT"));
+ if (carry_prev != nullptr)
+ return carry_prev;
+ /*CellInfo *i3_prev = net_driven_by(ctx, cell->ports.at(ctx->id("I3")).net, is_lc,
+ ctx->id("COUT")); if (i3_prev != nullptr) return i3_prev;*/
+ return (CellInfo *)nullptr;
+ },
+ [](const Context *ctx, const CellInfo *cell) {
+ CellInfo *carry_next = net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc,
+ ctx->id("CIN"), false);
+ if (carry_next != nullptr)
+ return carry_next;
+ /*CellInfo *i3_next =
+ net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("I3"),
+ false); if (i3_next != nullptr) return i3_next;*/
+ return (CellInfo *)nullptr;
+ });
+ std::unordered_set<IdString> chained;
+ for (auto &base_chain : carry_chains) {
+ for (auto c : base_chain.cells)
+ chained.insert(c->name);
+ }
+ // Any cells not in chains, but with carry enabled, must also be put in a single-carry chain
+ // for correct processing
+ for (auto cell : sorted(ctx->cells)) {
+ CellInfo *ci = cell.second;
+ if (chained.find(cell.first) == chained.end() && is_lc(ctx, ci) &&
+ bool_or_default(ci->params, ctx->id("CARRY_ENABLE"))) {
+ CellChain sChain;
+ sChain.cells.push_back(ci);
+ chained.insert(cell.first);
+ carry_chains.push_back(sChain);
+ }
+ }
+ std::vector<CellChain> all_chains;
+ // Chain splitting
+ for (auto &base_chain : carry_chains) {
+ if (ctx->verbose) {
+ log_info("Found carry chain: \n");
+ for (auto entry : base_chain.cells)
+ log_info(" %s\n", entry->name.c_str(ctx));
+ log_info("\n");
+ }
+ std::vector<CellChain> split_chains = split_carry_chain(base_chain);
+ for (auto &chain : split_chains) {
+ all_chains.push_back(chain);
+ }
+ }
+ // Actual chain placement
+ for (auto &chain : all_chains) {
+ if (ctx->verbose)
+ log_info("Placing carry chain starting at '%s'\n", chain.cells.front()->name.c_str(ctx));
+
+ // Place carry chain
+ chain.cells.at(0)->constr_abs_z = true;
+ chain.cells.at(0)->constr_z = 0;
+ for (int i = 1; i < int(chain.cells.size()); i++) {
+ chain.cells.at(i)->constr_x = 0;
+ chain.cells.at(i)->constr_y = (i / 8);
+ chain.cells.at(i)->constr_z = i % 8;
+ chain.cells.at(i)->constr_abs_z = true;
+ chain.cells.at(i)->constr_parent = chain.cells.at(0);
+ chain.cells.at(0)->constr_children.push_back(chain.cells.at(i));
+ }
+ }
+ }
+
+ public:
+ ChainConstrainer(Context *ctx) : ctx(ctx){};
+ void constrain_chains() { process_carries(); }
+};
+
+void constrain_chains(Context *ctx)
+{
+ log_info("Constraining chains...\n");
+ ChainConstrainer(ctx).constrain_chains();
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/ice40/place_legaliser.h b/ice40/chains.h
index 5f4df6aa..98112303 100644
--- a/ice40/place_legaliser.h
+++ b/ice40/chains.h
@@ -17,15 +17,11 @@
*
*/
-#ifndef PLACE_LEGALISER_H
-#define PLACE_LEGALISER_H
-
#include "nextpnr.h"
NEXTPNR_NAMESPACE_BEGIN
-bool legalise_design(Context *ctx);
+// This finds chains, inserts LCs to legalise them as needed, and sets relative constraints as appropriate
+void constrain_chains(Context *ctx);
NEXTPNR_NAMESPACE_END
-
-#endif
diff --git a/ice40/chipdb.py b/ice40/chipdb.py
index 0227ab6a..c1819481 100644
--- a/ice40/chipdb.py
+++ b/ice40/chipdb.py
@@ -787,7 +787,9 @@ tmport_to_portpin = {
"WCLKE": "WCLKE",
"WE": "WE",
"posedge:CLOCK": "CLOCK",
- "posedge:SLEEP": "SLEEP"
+ "posedge:SLEEP": "SLEEP",
+ "USERSIGNALTOGLOBALBUFFER": "USER_SIGNAL_TO_GLOBAL_BUFFER",
+ "GLOBALBUFFEROUTPUT": "GLOBAL_BUFFER_OUTPUT"
}
for i in range(16):
@@ -815,6 +817,8 @@ def add_cell_timingdata(bel_type, timing_cell, fast_db, slow_db):
cell_timings[bel_type] = timing_entries
add_cell_timingdata("ICESTORM_LC", "LogicCell40", fast_timings, slow_timings)
+add_cell_timingdata("SB_GB", "ICE_GB", fast_timings, slow_timings)
+
if dev_name != "384":
add_cell_timingdata("ICESTORM_RAM", "SB_RAM40_4K", fast_timings, slow_timings)
if dev_name == "5k":
diff --git a/ice40/main.cc b/ice40/main.cc
index 4a2e9532..46cdce71 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -40,7 +40,6 @@
#include "log.h"
#include "nextpnr.h"
#include "pcf.h"
-#include "place_legaliser.h"
#include "timing.h"
#include "version.h"
@@ -107,6 +106,9 @@ int main(int argc, char *argv[])
options.add_options()("seed", po::value<int>(), "seed value for random number generator");
options.add_options()("slack_redist_iter", po::value<int>(),
"number of iterations between slack redistribution");
+ options.add_options()("cstrweight", po::value<float>(),
+ "placer weighting for relative constraint satisfaction");
+
options.add_options()("version,V", "show version");
options.add_options()("tmfuzz", "run path delay estimate fuzzer");
options.add_options()("test", "check architecture database integrity");
@@ -317,6 +319,17 @@ int main(int argc, char *argv[])
if (vm.count("slack_redist_iter")) {
ctx->slack_redist_iter = vm["slack_redist_iter"].as<int>();
+ if (vm.count("freq") && vm["freq"].as<double>() == 0) {
+ ctx->auto_freq = true;
+#ifndef NO_GUI
+ if (!vm.count("gui"))
+#endif
+ log_warning("Target frequency not specified. Will optimise for max frequency.\n");
+ }
+ }
+
+ if (vm.count("cstrweight")) {
+ ctx->placer_constraintWeight = vm["cstrweight"].as<float>();
}
if (vm.count("svg")) {
@@ -379,13 +392,9 @@ int main(int argc, char *argv[])
}
if (vm.count("freq")) {
- ctx->target_freq = vm["freq"].as<double>() * 1e6;
- ctx->user_freq = true;
- } else {
-#ifndef NO_GUI
- if (!vm.count("gui"))
-#endif
- log_warning("Target frequency not specified. Will optimise for max frequency.\n");
+ auto freq = vm["freq"].as<double>();
+ if (freq > 0)
+ ctx->target_freq = freq * 1e6;
}
ctx->timing_driven = true;
diff --git a/ice40/pack.cc b/ice40/pack.cc
index fc182e98..e7fdc627 100644
--- a/ice40/pack.cc
+++ b/ice40/pack.cc
@@ -23,6 +23,7 @@
#include <iterator>
#include <unordered_set>
#include "cells.h"
+#include "chains.h"
#include "design_utils.h"
#include "log.h"
#include "util.h"
@@ -444,7 +445,8 @@ static bool is_logic_port(BaseCtx *ctx, const PortRef &port)
{
if (is_clock_port(ctx, port) || is_reset_port(ctx, port) || is_enable_port(ctx, port))
return false;
- return !is_sb_io(ctx, port.cell) && !is_sb_pll40(ctx, port.cell) && !is_sb_pll40_pad(ctx, port.cell) && port.cell->type != ctx->id("SB_GB");
+ return !is_sb_io(ctx, port.cell) && !is_sb_pll40(ctx, port.cell) && !is_sb_pll40_pad(ctx, port.cell) &&
+ port.cell->type != ctx->id("SB_GB");
}
static void insert_global(Context *ctx, NetInfo *net, bool is_reset, bool is_cen, bool is_logic)
@@ -893,6 +895,8 @@ bool Arch::pack()
pack_ram(ctx);
pack_special(ctx);
ctx->assignArchInfo();
+ constrain_chains(ctx);
+ ctx->assignArchInfo();
log_info("Checksum: 0x%08x\n", ctx->checksum());
return true;
} catch (log_execution_error_exception) {
diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc
deleted file mode 100644
index a498e5f4..00000000
--- a/ice40/place_legaliser.cc
+++ /dev/null
@@ -1,554 +0,0 @@
-/*
- * nextpnr -- Next Generation Place and Route
- *
- * 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.
- *
- */
-
-#include "place_legaliser.h"
-#include <algorithm>
-#include <vector>
-#include "cells.h"
-#include "design_utils.h"
-#include "log.h"
-#include "place_common.h"
-#include "util.h"
-
-NEXTPNR_NAMESPACE_BEGIN
-
-struct CellChain
-{
- std::vector<CellInfo *> cells;
- float mid_x = 0, mid_y = 0;
-};
-
-// Generic chain finder
-template <typename F1, typename F2, typename F3>
-std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next,
- size_t min_length = 2)
-{
- std::set<IdString> chained;
- std::vector<CellChain> chains;
- for (auto cell : sorted(ctx->cells)) {
- if (chained.find(cell.first) != chained.end())
- continue;
- CellInfo *ci = cell.second;
- if (cell_type_predicate(ctx, ci)) {
- CellInfo *start = ci;
- CellInfo *prev_start = ci;
- while (prev_start != nullptr) {
- start = prev_start;
- prev_start = get_previous(ctx, start);
- }
- CellChain chain;
- CellInfo *end = start;
- while (end != nullptr) {
- chain.cells.push_back(end);
- end = get_next(ctx, end);
- }
- if (chain.cells.size() >= min_length) {
- chains.push_back(chain);
- for (auto c : chain.cells)
- chained.insert(c->name);
- }
- }
- }
- return chains;
-}
-
-static void get_chain_midpoint(const Context *ctx, const CellChain &chain, float &x, float &y)
-{
- float total_x = 0, total_y = 0;
- int N = 0;
- for (auto cell : chain.cells) {
- if (cell->bel == BelId())
- continue;
- Loc bel_loc = ctx->getBelLocation(cell->bel);
- total_x += bel_loc.x;
- total_y += bel_loc.y;
- N++;
- }
- NPNR_ASSERT(N > 0);
- x = total_x / N;
- y = total_y / N;
-}
-
-static int get_cell_evilness(const Context *ctx, const CellInfo *cell)
-{
- // This returns how "evil" a logic cell is, and thus how likely it is to be ripped up
- // during logic tile legalisation
- int score = 0;
- if (get_net_or_empty(cell, ctx->id_i0))
- ++score;
- if (get_net_or_empty(cell, ctx->id_i1))
- ++score;
- if (get_net_or_empty(cell, ctx->id_i2))
- ++score;
- if (get_net_or_empty(cell, ctx->id_i3))
- ++score;
- if (cell->lcInfo.dffEnable) {
- if (cell->lcInfo.cen)
- score += 10;
- if (cell->lcInfo.sr)
- score += 10;
- if (cell->lcInfo.negClk)
- score += 5;
- }
- return score;
-}
-
-class PlacementLegaliser
-{
- public:
- PlacementLegaliser(Context *ctx) : ctx(ctx){};
-
- void print_stats(const char *point)
- {
- float distance_sum = 0;
- float max_distance = 0;
- int moved_cells = 0;
- int unplaced_cells = 0;
- for (auto orig : originalPositions) {
- if (ctx->cells.at(orig.first)->bel == BelId()) {
- unplaced_cells++;
- continue;
- }
- Loc newLoc = ctx->getBelLocation(ctx->cells.at(orig.first)->bel);
- if (newLoc != orig.second) {
- float distance = std::sqrt(std::pow(newLoc.x - orig.second.x, 2) + pow(newLoc.y - orig.second.y, 2));
- moved_cells++;
- distance_sum += distance;
- if (distance > max_distance)
- max_distance = distance;
- }
- }
- log_info(" moved %d cells, %d unplaced (after %s)\n", moved_cells, unplaced_cells, point);
- if (moved_cells > 0) {
- log_info(" average distance %f\n", (distance_sum / moved_cells));
- log_info(" maximum distance %f\n", max_distance);
- }
- }
-
- bool legalise()
- {
- log_info("Legalising design..\n");
- for (auto &cell : ctx->cells) {
- CellInfo *ci = cell.second.get();
- if (!ctx->getBelGlobalBuf(ci->bel) && cell.second->type == ctx->id("ICESTORM_LC")) {
- originalPositions[cell.first] = ctx->getBelLocation(ci->bel);
- }
- }
- init_logic_cells();
- bool legalised_carries = legalise_carries();
- if (!legalised_carries && !ctx->force)
- return false;
- print_stats("carry legalisation");
- legalise_others();
- print_stats("misc. cell legalisation");
- legalise_logic_tiles();
- print_stats("logic cell legalisation");
- bool replaced_cells = replace_cells();
- print_stats("cell replacement");
-
- ctx->assignArchInfo();
-
- return legalised_carries && replaced_cells;
- }
-
- private:
- void init_logic_cells()
- {
- for (auto bel : ctx->getBels()) {
- // Initialise the logic bels vector with unavailable invalid bels, dimensions [0..width][0..height[0..7]
- logic_bels.resize(ctx->chip_info->width + 1,
- std::vector<std::vector<std::pair<BelId, bool>>>(
- ctx->chip_info->height + 1,
- std::vector<std::pair<BelId, bool>>(8, std::make_pair(BelId(), true))));
- if (ctx->getBelType(bel) == TYPE_ICESTORM_LC) {
- // Using the non-standard API here to get (x, y, z) rather than just (x, y)
- auto bi = ctx->chip_info->bel_data[bel.index];
- int x = bi.x, y = bi.y, z = bi.z;
- IdString cell = ctx->getBoundBelCell(bel);
- if (cell != IdString() && ctx->cells.at(cell)->belStrength >= STRENGTH_FIXED)
- logic_bels.at(x).at(y).at(z) = std::make_pair(bel, true); // locked out of use
- else
- logic_bels.at(x).at(y).at(z) = std::make_pair(bel, false); // available
- }
- }
- }
-
- bool legalise_carries()
- {
- std::vector<CellChain> carry_chains =
- find_chains(ctx, [](const Context *ctx, const CellInfo *cell) { return is_lc(ctx, cell); },
- [](const Context *ctx, const
-
- CellInfo *cell) {
- CellInfo *carry_prev =
- net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT"));
- if (carry_prev != nullptr)
- return carry_prev;
- /*CellInfo *i3_prev = net_driven_by(ctx, cell->ports.at(ctx->id("I3")).net, is_lc,
- ctx->id("COUT")); if (i3_prev != nullptr) return i3_prev;*/
- return (CellInfo *)nullptr;
- },
- [](const Context *ctx, const CellInfo *cell) {
- CellInfo *carry_next = net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc,
- ctx->id("CIN"), false);
- if (carry_next != nullptr)
- return carry_next;
- /*CellInfo *i3_next =
- net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("I3"),
- false); if (i3_next != nullptr) return i3_next;*/
- return (CellInfo *)nullptr;
- });
- std::unordered_set<IdString> chained;
- for (auto &base_chain : carry_chains) {
- for (auto c : base_chain.cells)
- chained.insert(c->name);
- }
- // Any cells not in chains, but with carry enabled, must also be put in a single-carry chain
- // for correct processing
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
- if (chained.find(cell.first) == chained.end() && is_lc(ctx, ci) &&
- bool_or_default(ci->params, ctx->id("CARRY_ENABLE"))) {
- CellChain sChain;
- sChain.cells.push_back(ci);
- chained.insert(cell.first);
- carry_chains.push_back(sChain);
- }
- }
- bool success = true;
- // Find midpoints for all chains, before we start tearing them up
- std::vector<CellChain> all_chains;
- for (auto &base_chain : carry_chains) {
- if (ctx->verbose) {
- log_info("Found carry chain: \n");
- for (auto entry : base_chain.cells)
- log_info(" %s\n", entry->name.c_str(ctx));
- log_info("\n");
- }
- std::vector<CellChain> split_chains = split_carry_chain(base_chain);
- for (auto &chain : split_chains) {
- get_chain_midpoint(ctx, chain, chain.mid_x, chain.mid_y);
- all_chains.push_back(chain);
- }
- }
- // Actual chain placement
- for (auto &chain : all_chains) {
- if (ctx->verbose)
- log_info("Placing carry chain starting at '%s'\n", chain.cells.front()->name.c_str(ctx));
- float base_x = chain.mid_x, base_y = chain.mid_y - (chain.cells.size() / 16.0f);
- // Find Bel meeting requirements closest to the target base, returning location as <x, y, z>
- auto chain_origin_bel = find_closest_bel(base_x, base_y, chain);
- int place_x = std::get<0>(chain_origin_bel), place_y = std::get<1>(chain_origin_bel),
- place_z = std::get<2>(chain_origin_bel);
- if (place_x == -1) {
- if (ctx->force) {
- log_warning("failed to place carry chain, starting with cell '%s', length %d\n",
- chain.cells.front()->name.c_str(ctx), int(chain.cells.size()));
- success = false;
- continue;
- } else {
- log_error("failed to place carry chain, starting with cell '%s', length %d\n",
- chain.cells.front()->name.c_str(ctx), int(chain.cells.size()));
- }
- }
- // Place carry chain
- for (int i = 0; i < int(chain.cells.size()); i++) {
- int target_z = place_y * 8 + place_z + i;
- place_lc(chain.cells.at(i), place_x, target_z / 8, target_z % 8);
- if (ctx->verbose)
- log_info(" Cell '%s' placed at (%d, %d, %d)\n", chain.cells.at(i)->name.c_str(ctx), place_x,
- target_z / 8, target_z % 8);
- }
- }
- return success;
- }
-
- // Find Bel closest to a location, meeting chain requirements
- std::tuple<int, int, int> find_closest_bel(float target_x, float target_y, CellChain &chain)
- {
- std::tuple<int, int, int> best_origin = std::make_tuple(-1, -1, -1);
- wirelen_t best_metric = std::numeric_limits<wirelen_t>::max();
- int width = ctx->chip_info->width, height = ctx->chip_info->height;
- // Slow, should radiate outwards from target position - TODO
- int chain_size = int(chain.cells.size());
- for (int x = 1; x < width; x++) {
- for (int y = 1; y < (height - (chain_size / 8)); y++) {
- bool valid = true;
- wirelen_t wirelen = 0;
- for (int k = 0; k < chain_size; k++) {
- auto &lb = logic_bels.at(x).at(y + k / 8).at(k % 8);
- if (lb.second) {
- valid = false;
- break;
- } else {
- wirelen += get_cell_metric_at_bel(ctx, chain.cells.at(k), lb.first, MetricType::COST);
- }
- }
- if (valid && wirelen < best_metric) {
- best_metric = wirelen;
- best_origin = std::make_tuple(x, y, 0);
- }
- }
- }
- return best_origin;
- }
-
- // Split a carry chain into multiple legal chains
- std::vector<CellChain> split_carry_chain(CellChain &carryc)
- {
- bool start_of_chain = true;
- std::vector<CellChain> chains;
- std::vector<const CellInfo *> tile;
- const int max_length = (ctx->chip_info->height - 2) * 8 - 2;
- auto curr_cell = carryc.cells.begin();
- while (curr_cell != carryc.cells.end()) {
- CellInfo *cell = *curr_cell;
- if (tile.size() >= 8) {
- tile.clear();
- }
- if (start_of_chain) {
- tile.clear();
- chains.emplace_back();
- start_of_chain = false;
- if (cell->ports.at(ctx->id("CIN")).net) {
- // CIN is not constant and not part of a chain. Must feed in from fabric
- CellInfo *feedin = make_carry_feed_in(cell, cell->ports.at(ctx->id("CIN")));
- chains.back().cells.push_back(feedin);
- tile.push_back(feedin);
- }
- }
- tile.push_back(cell);
- chains.back().cells.push_back(cell);
- bool split_chain = (!ctx->logicCellsCompatible(tile)) || (int(chains.back().cells.size()) > max_length);
- if (split_chain) {
- CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT")));
- tile.pop_back();
- chains.back().cells.back() = passout;
- start_of_chain = true;
- } else {
- NetInfo *carry_net = cell->ports.at(ctx->id("COUT")).net;
- bool at_end = (curr_cell == carryc.cells.end() - 1);
- if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) {
- if (carry_net->users.size() > 2 ||
- (net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), false) !=
- net_only_drives(ctx, carry_net, is_lc, ctx->id("CIN"), false)) ||
- (at_end && !net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), true))) {
- CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT")));
- chains.back().cells.push_back(passout);
- tile.push_back(passout);
- start_of_chain = true;
- }
- }
- ++curr_cell;
- }
- }
- return chains;
- }
-
- // Place a logic cell at a given grid location, handling rip-up etc
- void place_lc(CellInfo *cell, int x, int y, int z)
- {
- auto &loc = logic_bels.at(x).at(y).at(z);
- NPNR_ASSERT(!loc.second);
- BelId bel = loc.first;
- // Check if there is a cell presently at the location, which we will need to rip up
- IdString existing = ctx->getBoundBelCell(bel);
- if (existing != IdString()) {
- // TODO: keep track of the previous position of the ripped up cell, as a hint
- rippedCells.insert(existing);
- ctx->unbindBel(bel);
- }
- if (cell->bel != BelId()) {
- ctx->unbindBel(cell->bel);
- }
- ctx->bindBel(bel, cell->name, STRENGTH_LOCKED);
- rippedCells.erase(cell->name); // If cell was ripped up previously, no need to re-place
- loc.second = true; // Bel is now unavailable for further use
- }
-
- // Insert a logic cell to legalise a COUT->fabric connection
- CellInfo *make_carry_pass_out(PortInfo &cout_port)
- {
- NPNR_ASSERT(cout_port.net != nullptr);
- std::unique_ptr<CellInfo> lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC"));
- lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3
- lc->params[ctx->id("CARRY_ENABLE")] = "1";
- lc->ports.at(ctx->id("O")).net = cout_port.net;
- std::unique_ptr<NetInfo> co_i3_net(new NetInfo());
- co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3");
- co_i3_net->driver = cout_port.net->driver;
- PortRef i3_r;
- i3_r.port = ctx->id("I3");
- i3_r.cell = lc.get();
- co_i3_net->users.push_back(i3_r);
- PortRef o_r;
- o_r.port = ctx->id("O");
- o_r.cell = lc.get();
- cout_port.net->driver = o_r;
- lc->ports.at(ctx->id("I3")).net = co_i3_net.get();
- cout_port.net = co_i3_net.get();
-
- IdString co_i3_name = co_i3_net->name;
- NPNR_ASSERT(ctx->nets.find(co_i3_name) == ctx->nets.end());
- ctx->nets[co_i3_name] = std::move(co_i3_net);
- IdString name = lc->name;
- ctx->assignCellInfo(lc.get());
- ctx->cells[lc->name] = std::move(lc);
- createdCells.insert(name);
- return ctx->cells[name].get();
- }
-
- // Insert a logic cell to legalise a CIN->fabric connection
- CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port)
- {
- NPNR_ASSERT(cin_port.net != nullptr);
- std::unique_ptr<CellInfo> lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC"));
- lc->params[ctx->id("CARRY_ENABLE")] = "1";
- lc->params[ctx->id("CIN_CONST")] = "1";
- lc->params[ctx->id("CIN_SET")] = "1";
- lc->ports.at(ctx->id("I1")).net = cin_port.net;
- cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(),
- [cin_cell, cin_port](const PortRef &usr) {
- return usr.cell == cin_cell && usr.port == cin_port.name;
- }));
-
- PortRef i1_ref;
- i1_ref.cell = lc.get();
- i1_ref.port = ctx->id("I1");
- lc->ports.at(ctx->id("I1")).net->users.push_back(i1_ref);
-
- std::unique_ptr<NetInfo> out_net(new NetInfo());
- out_net->name = ctx->id(lc->name.str(ctx) + "$O");
-
- PortRef drv_ref;
- drv_ref.port = ctx->id("COUT");
- drv_ref.cell = lc.get();
- out_net->driver = drv_ref;
- lc->ports.at(ctx->id("COUT")).net = out_net.get();
-
- PortRef usr_ref;
- usr_ref.port = cin_port.name;
- usr_ref.cell = cin_cell;
- out_net->users.push_back(usr_ref);
- cin_cell->ports.at(cin_port.name).net = out_net.get();
-
- IdString out_net_name = out_net->name;
- NPNR_ASSERT(ctx->nets.find(out_net_name) == ctx->nets.end());
- ctx->nets[out_net_name] = std::move(out_net);
-
- IdString name = lc->name;
- ctx->assignCellInfo(lc.get());
- ctx->cells[lc->name] = std::move(lc);
- createdCells.insert(name);
- return ctx->cells[name].get();
- }
-
- // Legalise logic tiles
- void legalise_logic_tiles()
- {
- int width = ctx->chip_info->width, height = ctx->chip_info->height;
- for (int x = 1; x < width; x++) {
- for (int y = 1; y < height; y++) {
- BelId tileBel = logic_bels.at(x).at(y).at(0).first;
- if (tileBel != BelId()) {
- bool changed = true;
- while (!ctx->isBelLocationValid(tileBel) && changed) {
- changed = false;
- int max_score = 0;
- CellInfo *target = nullptr;
- for (int z = 0; z < 8; z++) {
- BelId bel = logic_bels.at(x).at(y).at(z).first;
- IdString cell = ctx->getBoundBelCell(bel);
- if (cell != IdString()) {
- CellInfo *ci = ctx->cells.at(cell).get();
- if (ci->belStrength >= STRENGTH_STRONG)
- continue;
- int score = get_cell_evilness(ctx, ci);
- if (score > max_score) {
- max_score = score;
- target = ci;
- }
- }
- }
- if (target != nullptr) {
- ctx->unbindBel(target->bel);
- rippedCells.insert(target->name);
- changed = true;
- }
- }
- }
- }
- }
- }
-
- // Legalise other tiles
- void legalise_others()
- {
- std::vector<CellInfo *> legalised_others;
- for (auto cell : sorted(ctx->cells)) {
- CellInfo *ci = cell.second;
- if (!is_lc(ctx, ci)) {
- if (ci->belStrength < STRENGTH_STRONG && ci->bel != BelId()) {
- if (!ctx->isValidBelForCell(ci, ci->bel)) {
- place_single_cell(ctx, ci, true);
- }
- legalised_others.push_back(ci);
- }
- }
- }
- // Lock all these cells now, we don't need to move them in SA (don't lock during legalise placement
- // so legalise placement can rip up in case of gbuf contention etc)
- for (auto cell : legalised_others)
- cell->belStrength = STRENGTH_STRONG;
- }
-
- // Replace ripped-up cells
- bool replace_cells()
- {
- bool success = true;
- for (auto cell : sorted(rippedCells)) {
- CellInfo *ci = ctx->cells.at(cell).get();
- bool placed = place_single_cell(ctx, ci, true);
- if (!placed) {
- if (ctx->force) {
- log_warning("failed to place cell '%s' of type '%s'\n", cell.c_str(ctx), ci->type.c_str(ctx));
- success = false;
- } else {
- log_error("failed to place cell '%s' of type '%s'\n", cell.c_str(ctx), ci->type.c_str(ctx));
- }
- }
- }
- return success;
- }
-
- Context *ctx;
- std::unordered_set<IdString> rippedCells;
- std::unordered_set<IdString> createdCells;
- std::unordered_map<IdString, Loc> originalPositions;
- // Go from X and Y position to logic cells, setting occupied to true if a Bel is unavailable
- std::vector<std::vector<std::vector<std::pair<BelId, bool>>>> logic_bels;
-};
-
-bool legalise_design(Context *ctx)
-{
- PlacementLegaliser lg(ctx);
- return lg.legalise();
-}
-
-NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 17:26:18 +0000