aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/nextpnr.cc137
-rw-r--r--common/nextpnr.h135
-rw-r--r--common/place_common.cc34
-rw-r--r--common/placer1.cc38
-rw-r--r--common/router1.cc1437
-rw-r--r--common/router1.h4
-rw-r--r--common/timing.cc568
-rw-r--r--common/timing.h2
8 files changed, 1468 insertions, 887 deletions
diff --git a/common/nextpnr.cc b/common/nextpnr.cc
index 4e6407b2..be3bfe14 100644
--- a/common/nextpnr.cc
+++ b/common/nextpnr.cc
@@ -18,6 +18,7 @@
*/
#include "nextpnr.h"
+#include "log.h"
NEXTPNR_NAMESPACE_BEGIN
@@ -25,6 +26,7 @@ assertion_failure::assertion_failure(std::string msg, std::string expr_str, std:
: runtime_error("Assertion failure: " + msg + " (" + filename + ":" + std::to_string(line) + ")"), msg(msg),
expr_str(expr_str), filename(filename), line(line)
{
+ log_flush();
}
void IdString::set(const BaseCtx *ctx, const std::string &s)
@@ -51,6 +53,131 @@ void IdString::initialize_add(const BaseCtx *ctx, const char *s, int idx)
ctx->idstring_idx_to_str->push_back(&insert_rc.first->first);
}
+TimingConstrObjectId BaseCtx::timingWildcardObject()
+{
+ TimingConstrObjectId id;
+ id.index = 0;
+ return id;
+}
+
+TimingConstrObjectId BaseCtx::timingClockDomainObject(NetInfo *clockDomain)
+{
+ NPNR_ASSERT(clockDomain->clkconstr != nullptr);
+ if (clockDomain->clkconstr->domain_tmg_id != TimingConstrObjectId()) {
+ return clockDomain->clkconstr->domain_tmg_id;
+ } else {
+ TimingConstraintObject obj;
+ TimingConstrObjectId id;
+ id.index = int(constraintObjects.size());
+ obj.id = id;
+ obj.type = TimingConstraintObject::CLOCK_DOMAIN;
+ obj.entity = clockDomain->name;
+ clockDomain->clkconstr->domain_tmg_id = id;
+ constraintObjects.push_back(obj);
+ return id;
+ }
+}
+
+TimingConstrObjectId BaseCtx::timingNetObject(NetInfo *net)
+{
+ if (net->tmg_id != TimingConstrObjectId()) {
+ return net->tmg_id;
+ } else {
+ TimingConstraintObject obj;
+ TimingConstrObjectId id;
+ id.index = int(constraintObjects.size());
+ obj.id = id;
+ obj.type = TimingConstraintObject::NET;
+ obj.entity = net->name;
+ constraintObjects.push_back(obj);
+ net->tmg_id = id;
+ return id;
+ }
+}
+
+TimingConstrObjectId BaseCtx::timingCellObject(CellInfo *cell)
+{
+ if (cell->tmg_id != TimingConstrObjectId()) {
+ return cell->tmg_id;
+ } else {
+ TimingConstraintObject obj;
+ TimingConstrObjectId id;
+ id.index = int(constraintObjects.size());
+ obj.id = id;
+ obj.type = TimingConstraintObject::CELL;
+ obj.entity = cell->name;
+ constraintObjects.push_back(obj);
+ cell->tmg_id = id;
+ return id;
+ }
+}
+
+TimingConstrObjectId BaseCtx::timingPortObject(CellInfo *cell, IdString port)
+{
+ if (cell->ports.at(port).tmg_id != TimingConstrObjectId()) {
+ return cell->ports.at(port).tmg_id;
+ } else {
+ TimingConstraintObject obj;
+ TimingConstrObjectId id;
+ id.index = int(constraintObjects.size());
+ obj.id = id;
+ obj.type = TimingConstraintObject::CELL_PORT;
+ obj.entity = cell->name;
+ obj.port = port;
+ constraintObjects.push_back(obj);
+ cell->ports.at(port).tmg_id = id;
+ return id;
+ }
+}
+
+void BaseCtx::addConstraint(std::unique_ptr<TimingConstraint> constr)
+{
+ for (auto fromObj : constr->from)
+ constrsFrom.emplace(fromObj, constr.get());
+ for (auto toObj : constr->to)
+ constrsTo.emplace(toObj, constr.get());
+ IdString name = constr->name;
+ constraints[name] = std::move(constr);
+}
+
+void BaseCtx::removeConstraint(IdString constrName)
+{
+ TimingConstraint *constr = constraints[constrName].get();
+ for (auto fromObj : constr->from) {
+ auto fromConstrs = constrsFrom.equal_range(fromObj);
+ constrsFrom.erase(std::find(fromConstrs.first, fromConstrs.second, std::make_pair(fromObj, constr)));
+ }
+ for (auto toObj : constr->to) {
+ auto toConstrs = constrsFrom.equal_range(toObj);
+ constrsFrom.erase(std::find(toConstrs.first, toConstrs.second, std::make_pair(toObj, constr)));
+ }
+ constraints.erase(constrName);
+}
+
+const char *BaseCtx::nameOfBel(BelId bel) const
+{
+ const Context *ctx = getCtx();
+ return ctx->getBelName(bel).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfWire(WireId wire) const
+{
+ const Context *ctx = getCtx();
+ return ctx->getWireName(wire).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfPip(PipId pip) const
+{
+ const Context *ctx = getCtx();
+ return ctx->getPipName(pip).c_str(ctx);
+}
+
+const char *BaseCtx::nameOfGroup(GroupId group) const
+{
+ const Context *ctx = getCtx();
+ return ctx->getGroupName(group).c_str(ctx);
+}
+
WireId Context::getNetinfoSourceWire(const NetInfo *net_info) const
{
if (net_info->driver.cell == nullptr)
@@ -280,4 +407,14 @@ void Context::check() const
}
}
+void BaseCtx::addClock(IdString net, float freq)
+{
+ log_info("constraining clock net '%s' to %.02f MHz\n", net.c_str(this), freq);
+ std::unique_ptr<ClockConstraint> cc(new ClockConstraint());
+ cc->period = getCtx()->getDelayFromNS(1000 / freq);
+ cc->high = getCtx()->getDelayFromNS(500 / freq);
+ cc->low = getCtx()->getDelayFromNS(500 / freq);
+ nets.at(net)->clkconstr = std::move(cc);
+}
+
NEXTPNR_NAMESPACE_END
diff --git a/common/nextpnr.h b/common/nextpnr.h
index 59ae0323..a6617ae4 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -191,7 +191,15 @@ struct Loc
Loc(int x, int y, int z) : x(x), y(y), z(z) {}
bool operator==(const Loc &other) const { return (x == other.x) && (y == other.y) && (z == other.z); }
- bool operator!=(const Loc &other) const { return (x != other.x) || (y != other.y) || (z == other.z); }
+ bool operator!=(const Loc &other) const { return (x != other.x) || (y != other.y) || (z != other.z); }
+};
+
+struct TimingConstrObjectId
+{
+ int32_t index = -1;
+
+ bool operator==(const TimingConstrObjectId &other) const { return index == other.index; }
+ bool operator!=(const TimingConstrObjectId &other) const { return index != other.index; }
};
NEXTPNR_NAMESPACE_END
@@ -208,6 +216,15 @@ template <> struct hash<NEXTPNR_NAMESPACE_PREFIX Loc>
return seed;
}
};
+
+template <> struct hash<NEXTPNR_NAMESPACE_PREFIX TimingConstrObjectId>
+{
+ std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX TimingConstrObjectId &obj) const noexcept
+ {
+ return hash<int>()(obj.index);
+ }
+};
+
} // namespace std
#include "archdefs.h"
@@ -266,10 +283,12 @@ struct PipMap
PlaceStrength strength = STRENGTH_NONE;
};
+struct ClockConstraint;
+
struct NetInfo : ArchNetInfo
{
IdString name;
- int32_t udata;
+ int32_t udata = 0;
PortRef driver;
std::vector<PortRef> users;
@@ -278,6 +297,10 @@ struct NetInfo : ArchNetInfo
// wire -> uphill_pip
std::unordered_map<WireId, PipMap> wires;
+ std::unique_ptr<ClockConstraint> clkconstr;
+
+ TimingConstrObjectId tmg_id;
+
Region *region = nullptr;
};
@@ -293,6 +316,7 @@ struct PortInfo
IdString name;
NetInfo *net;
PortType type;
+ TimingConstrObjectId tmg_id;
};
struct CellInfo : ArchCellInfo
@@ -320,6 +344,7 @@ struct CellInfo : ArchCellInfo
// parent.[xyz] := 0 when (constr_parent == nullptr)
Region *region = nullptr;
+ TimingConstrObjectId tmg_id;
};
enum TimingPortClass
@@ -335,6 +360,68 @@ enum TimingPortClass
TMG_IGNORE, // Asynchronous to all clocks, "don't care", and should be ignored (false path) for analysis
};
+enum ClockEdge
+{
+ RISING_EDGE,
+ FALLING_EDGE
+};
+
+struct TimingClockingInfo
+{
+ IdString clock_port; // Port name of clock domain
+ ClockEdge edge;
+ DelayInfo setup, hold; // Input timing checks
+ DelayInfo clockToQ; // Output clock-to-Q time
+};
+
+struct ClockConstraint
+{
+ DelayInfo high;
+ DelayInfo low;
+ DelayInfo period;
+
+ TimingConstrObjectId domain_tmg_id;
+};
+
+struct TimingConstraintObject
+{
+ TimingConstrObjectId id;
+ enum
+ {
+ ANYTHING,
+ CLOCK_DOMAIN,
+ NET,
+ CELL,
+ CELL_PORT
+ } type;
+ IdString entity; // Name of clock net; net or cell
+ IdString port; // Name of port on a cell
+};
+
+struct TimingConstraint
+{
+ IdString name;
+
+ enum
+ {
+ FALSE_PATH,
+ MIN_DELAY,
+ MAX_DELAY,
+ MULTICYCLE,
+ } type;
+
+ delay_t value;
+
+ std::unordered_set<TimingConstrObjectId> from;
+ std::unordered_set<TimingConstrObjectId> to;
+};
+
+inline bool operator==(const std::pair<const TimingConstrObjectId, TimingConstraint *> &a,
+ const std::pair<TimingConstrObjectId, TimingConstraint *> &b)
+{
+ return a.first == b.first && a.second == b.second;
+}
+
struct DeterministicRNG
{
uint64_t rngstate;
@@ -431,6 +518,11 @@ struct BaseCtx
idstring_idx_to_str = new std::vector<const std::string *>;
IdString::initialize_add(this, "", 0);
IdString::initialize_arch(this);
+
+ TimingConstraintObject wildcard;
+ wildcard.id.index = 0;
+ wildcard.type = TimingConstraintObject::ANYTHING;
+ constraintObjects.push_back(wildcard);
}
~BaseCtx()
@@ -487,13 +579,23 @@ struct BaseCtx
const Context *getCtx() const { return reinterpret_cast<const Context *>(this); }
- template <typename T> const char *nameOf(const T *obj)
+ const char *nameOf(IdString name) const
+ {
+ return name.c_str(this);
+ }
+
+ template <typename T> const char *nameOf(const T *obj) const
{
if (obj == nullptr)
return "";
- return obj->name.c_str(getCtx());
+ return obj->name.c_str(this);
}
+ const char *nameOfBel(BelId bel) const;
+ const char *nameOfWire(WireId wire) const;
+ const char *nameOfPip(PipId pip) const;
+ const char *nameOfGroup(GroupId group) const;
+
// --------------------------------------------------------------
bool allUiReload = true;
@@ -514,6 +616,30 @@ struct BaseCtx
void refreshUiPip(PipId pip) { pipUiReload.insert(pip); }
void refreshUiGroup(GroupId group) { groupUiReload.insert(group); }
+
+ // --------------------------------------------------------------
+
+ // Timing Constraint API
+
+ // constraint name -> constraint
+ std::unordered_map<IdString, std::unique_ptr<TimingConstraint>> constraints;
+ // object ID -> object
+ std::vector<TimingConstraintObject> constraintObjects;
+ // object ID -> constraint
+ std::unordered_multimap<TimingConstrObjectId, TimingConstraint *> constrsFrom;
+ std::unordered_multimap<TimingConstrObjectId, TimingConstraint *> constrsTo;
+
+ TimingConstrObjectId timingWildcardObject();
+ TimingConstrObjectId timingClockDomainObject(NetInfo *clockDomain);
+ TimingConstrObjectId timingNetObject(NetInfo *net);
+ TimingConstrObjectId timingCellObject(CellInfo *cell);
+ TimingConstrObjectId timingPortObject(CellInfo *cell, IdString port);
+
+ void addConstraint(std::unique_ptr<TimingConstraint> constr);
+ void removeConstraint(IdString constrName);
+
+ // Intended to simplify Python API
+ void addClock(IdString net, float freq);
};
NEXTPNR_NAMESPACE_END
@@ -541,6 +667,7 @@ struct Context : Arch, DeterministicRNG
delay_t getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &sink) const;
// provided by router1.cc
+ bool checkRoutedDesign() const;
bool getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay = nullptr,
std::unordered_map<WireId, PipId> *route = nullptr, bool useEstimate = true);
diff --git a/common/place_common.cc b/common/place_common.cc
index da8ab37d..a13a963c 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -28,19 +28,19 @@ NEXTPNR_NAMESPACE_BEGIN
wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type, float &tns)
{
wirelen_t wirelength = 0;
- Loc driver_loc;
- bool driver_gb;
CellInfo *driver_cell = net->driver.cell;
if (!driver_cell)
return 0;
if (driver_cell->bel == BelId())
return 0;
- driver_gb = ctx->getBelGlobalBuf(driver_cell->bel);
- driver_loc = ctx->getBelLocation(driver_cell->bel);
+ bool driver_gb = ctx->getBelGlobalBuf(driver_cell->bel);
if (driver_gb)
return 0;
+ int clock_count;
+ bool timing_driven = ctx->timing_driven && type == MetricType::COST && ctx->getPortTimingClass(driver_cell, net->driver.port, clock_count) != TMG_IGNORE;
delay_t negative_slack = 0;
delay_t worst_slack = std::numeric_limits<delay_t>::max();
+ Loc driver_loc = ctx->getBelLocation(driver_cell->bel);
int xmin = driver_loc.x, xmax = driver_loc.x, ymin = driver_loc.y, ymax = driver_loc.y;
for (auto load : net->users) {
if (load.cell == nullptr)
@@ -48,7 +48,7 @@ wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type
CellInfo *load_cell = load.cell;
if (load_cell->bel == BelId())
continue;
- if (ctx->timing_driven && type == MetricType::COST) {
+ if (timing_driven) {
delay_t net_delay = ctx->predictDelay(net, load);
auto slack = load.budget - net_delay;
if (slack < 0)
@@ -65,7 +65,7 @@ wirelen_t get_net_metric(const Context *ctx, const NetInfo *net, MetricType type
xmax = std::max(xmax, load_loc.x);
ymax = std::max(ymax, load_loc.y);
}
- if (ctx->timing_driven && type == MetricType::COST) {
+ if (timing_driven) {
wirelength = wirelen_t(
(((ymax - ymin) + (xmax - xmin)) * std::min(5.0, (1.0 + std::exp(-ctx->getDelayNS(worst_slack) / 5)))));
} else {
@@ -431,12 +431,12 @@ class ConstraintLegaliseWorker
print_chain(child, depth + 1);
}
- void print_stats(const char *point)
+ unsigned print_stats(const char *point)
{
float distance_sum = 0;
float max_distance = 0;
- int moved_cells = 0;
- int unplaced_cells = 0;
+ unsigned moved_cells = 0;
+ unsigned unplaced_cells = 0;
for (auto orig : oldLocations) {
if (ctx->cells.at(orig.first)->bel == BelId()) {
unplaced_cells++;
@@ -456,9 +456,10 @@ class ConstraintLegaliseWorker
log_info(" average distance %f\n", (distance_sum / moved_cells));
log_info(" maximum distance %f\n", max_distance);
}
+ return moved_cells + unplaced_cells;
}
- bool legalise_constraints()
+ int legalise_constraints()
{
log_info("Legalising relative constraints...\n");
for (auto cell : sorted(ctx->cells)) {
@@ -470,27 +471,28 @@ class ConstraintLegaliseWorker
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;
+ return -1;
}
}
- print_stats("after legalising chains");
+ if (print_stats("legalising chains") == 0)
+ return 0;
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;
+ return -1;
}
}
- print_stats("after replacing ripped up cells");
+ auto score = print_stats("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;
+ return score;
}
};
-bool legalise_relative_constraints(Context *ctx) { return ConstraintLegaliseWorker(ctx).legalise_constraints(); }
+bool legalise_relative_constraints(Context *ctx) { return ConstraintLegaliseWorker(ctx).legalise_constraints() > 0; }
// Get the total distance from satisfied constraints for a cell
int get_constraints_distance(const Context *ctx, const CellInfo *cell)
diff --git a/common/placer1.cc b/common/placer1.cc
index 01f822a5..0fd9a227 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -118,6 +118,12 @@ class SAPlacer
loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
}
+ auto bound_cell = ctx->getBoundBelCell(bel);
+ if (bound_cell) {
+ log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
+ cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
+ }
+
ctx->bindBel(bel, cell, STRENGTH_USER);
locked_bels.insert(bel);
placed_cells++;
@@ -238,21 +244,23 @@ class SAPlacer
}
// Once cooled below legalise threshold, run legalisation and start requiring
// legal moves only
- if (temp < legalise_temp && !require_legal) {
- legalise_relative_constraints(ctx);
- require_legal = true;
- autoplaced.clear();
- for (auto cell : sorted(ctx->cells)) {
- if (cell.second->belStrength < STRENGTH_STRONG)
- autoplaced.push_back(cell.second);
- }
- temp = post_legalise_temp;
- diameter *= post_legalise_dia_scale;
- ctx->shuffle(autoplaced);
+ if (temp < legalise_temp && require_legal) {
+ if (legalise_relative_constraints(ctx)) {
+ // Only increase temperature if something was moved
+ autoplaced.clear();
+ for (auto cell : sorted(ctx->cells)) {
+ if (cell.second->belStrength < STRENGTH_STRONG)
+ autoplaced.push_back(cell.second);
+ }
+ temp = post_legalise_temp;
+ diameter *= post_legalise_dia_scale;
+ ctx->shuffle(autoplaced);
- // Legalisation is a big change so force a slack redistribution here
- if (ctx->slack_redist_iter > 0)
- assign_budget(ctx, true /* quiet */);
+ // Legalisation is a big change so force a slack redistribution here
+ if (ctx->slack_redist_iter > 0)
+ assign_budget(ctx, true /* quiet */);
+ }
+ require_legal = false;
} else if (ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) {
assign_budget(ctx, true /* quiet */);
}
@@ -480,7 +488,7 @@ class SAPlacer
std::unordered_map<IdString, int> bel_types;
std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels;
std::unordered_set<BelId> locked_bels;
- bool require_legal = false;
+ bool require_legal = true;
const float legalise_temp = 1;
const float post_legalise_temp = 10;
const float post_legalise_dia_scale = 1.5;
diff --git a/common/router1.cc b/common/router1.cc
index c4708de7..958c24d4 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -28,24 +28,40 @@ namespace {
USING_NEXTPNR_NAMESPACE
-struct hash_id_wire
+struct arc_key
{
- std::size_t operator()(const std::pair<IdString, WireId> &arg) const noexcept
+ NetInfo *net_info;
+ int user_idx;
+
+ bool operator==(const arc_key &other) const { return (net_info == other.net_info) && (user_idx == other.user_idx); }
+ bool operator<(const arc_key &other) const { return net_info == other.net_info ? user_idx < other.user_idx : net_info->name < other.net_info->name; }
+
+ struct Hash
{
- std::size_t seed = std::hash<IdString>()(arg.first);
- seed ^= std::hash<WireId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
+ std::size_t operator()(const arc_key &arg) const noexcept
+ {
+ std::size_t seed = std::hash<NetInfo *>()(arg.net_info);
+ seed ^= std::hash<int>()(arg.user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ return seed;
+ }
+ };
};
-struct hash_id_pip
+struct arc_entry
{
- std::size_t operator()(const std::pair<IdString, PipId> &arg) const noexcept
+ arc_key arc;
+ delay_t pri;
+ int randtag = 0;
+
+ struct Less
{
- std::size_t seed = std::hash<IdString>()(arg.first);
- seed ^= std::hash<PipId>()(arg.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
- return seed;
- }
+ bool operator()(const arc_entry &lhs, const arc_entry &rhs) const noexcept
+ {
+ if (lhs.pri != rhs.pri)
+ return lhs.pri < rhs.pri;
+ return lhs.randtag < rhs.randtag;
+ }
+ };
};
struct QueuedWire
@@ -53,636 +69,662 @@ struct QueuedWire
WireId wire;
PipId pip;
- delay_t delay = 0, togo = 0;
+ delay_t delay = 0, penalty = 0, bonus = 0, togo = 0;
int randtag = 0;
struct Greater
{
bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept
{
- delay_t l = lhs.delay + lhs.togo, r = rhs.delay + rhs.togo;
+ delay_t l = lhs.delay + lhs.penalty + lhs.togo;
+ delay_t r = rhs.delay + rhs.penalty + rhs.togo;
+ NPNR_ASSERT(l >= 0);
+ NPNR_ASSERT(r >= 0);
+ l -= lhs.bonus;
+ r -= rhs.bonus;
return l == r ? lhs.randtag > rhs.randtag : l > r;
}
};
};
-struct RipupScoreboard
+struct Router1
{
- std::unordered_map<WireId, int> wireScores;
- std::unordered_map<PipId, int> pipScores;
- std::unordered_map<std::pair<IdString, WireId>, int, hash_id_wire> netWireScores;
- std::unordered_map<std::pair<IdString, PipId>, int, hash_id_pip> netPipScores;
-};
+ Context *ctx;
+ const Router1Cfg &cfg;
-void ripup_net(Context *ctx, IdString net_name)
-{
- if (ctx->debug)
- log("Ripping up all routing for net %s.\n", net_name.c_str(ctx));
+ std::priority_queue<arc_entry, std::vector<arc_entry>, arc_entry::Less> arc_queue;
+ std::unordered_map<WireId, std::unordered_set<arc_key, arc_key::Hash>> wire_to_arcs;
+ std::unordered_map<arc_key, std::unordered_set<WireId>, arc_key::Hash> arc_to_wires;
+ std::unordered_set<arc_key, arc_key::Hash> queued_arcs;
- auto net_info = ctx->nets.at(net_name).get();
- std::vector<PipId> pips;
- std::vector<WireId> wires;
+ std::unordered_map<WireId, QueuedWire> visited;
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
- pips.reserve(net_info->wires.size());
- wires.reserve(net_info->wires.size());
+ std::unordered_map<WireId, int> wireScores;
+ std::unordered_map<NetInfo *, int> netScores;
- for (auto &it : net_info->wires) {
- if (it.second.pip != PipId())
- pips.push_back(it.second.pip);
- else
- wires.push_back(it.first);
- }
+ int arcs_with_ripup = 0;
+ int arcs_without_ripup = 0;
+ bool ripup_flag;
- for (auto pip : pips)
- ctx->unbindPip(pip);
+ Router1(Context *ctx, const Router1Cfg &cfg) : ctx(ctx), cfg(cfg) {}
- for (auto wire : wires)
- ctx->unbindWire(wire);
+ void arc_queue_insert(const arc_key &arc, WireId src_wire, WireId dst_wire)
+ {
+ if (queued_arcs.count(arc))
+ return;
- NPNR_ASSERT(net_info->wires.empty());
-}
+ delay_t pri = ctx->estimateDelay(src_wire, dst_wire) - arc.net_info->users[arc.user_idx].budget;
-struct Router
-{
- Context *ctx;
- const Router1Cfg &cfg;
- RipupScoreboard scores;
- IdString net_name;
+ arc_entry entry;
+ entry.arc = arc;
+ entry.pri = pri;
+ entry.randtag = ctx->rng();
- bool ripup;
- delay_t ripup_penalty;
+#if 0
+ if (ctx->debug)
+ log("[arc_queue_insert] %s (%d) %s %s [%d %d]\n", ctx->nameOf(entry.arc.net_info), entry.arc.user_idx,
+ ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire), (int)entry.pri, entry.randtag);
+#endif
- std::unordered_set<IdString> rippedNets;
- std::unordered_map<WireId, QueuedWire> visited;
- int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0;
- bool routedOkay = false;
- delay_t maxDelay = 0.0;
- WireId failedDest;
+ arc_queue.push(entry);
+ queued_arcs.insert(arc);
+ }
- void route(const std::unordered_map<WireId, delay_t> &src_wires, WireId dst_wire)
+ void arc_queue_insert(const arc_key &arc)
{
- std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
+ if (queued_arcs.count(arc))
+ return;
- visited.clear();
+ NetInfo *net_info = arc.net_info;
+ int user_idx = arc.user_idx;
- for (auto &it : src_wires) {
- QueuedWire qw;
- qw.wire = it.first;
- qw.pip = PipId();
- qw.delay = it.second - (it.second / 16);
- if (cfg.useEstimate)
- qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
- qw.randtag = ctx->rng();
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
- queue.push(qw);
- visited[qw.wire] = qw;
- }
+ arc_queue_insert(arc, src_wire, dst_wire);
+ }
- int thisVisitCnt = 0;
- int thisVisitCntLimit = 0;
+ arc_key arc_queue_pop()
+ {
+ arc_entry entry = arc_queue.top();
- while (!queue.empty() && (thisVisitCntLimit == 0 || thisVisitCnt < thisVisitCntLimit)) {
- QueuedWire qw = queue.top();
- queue.pop();
+#if 0
+ if (ctx->debug)
+ log("[arc_queue_pop] %s (%d) [%d %d]\n", ctx->nameOf(entry.arc.net_info), entry.arc.user_idx,
+ (int)entry.pri, entry.randtag);
+#endif
- if (thisVisitCntLimit == 0 && visited.count(dst_wire))
- thisVisitCntLimit = (thisVisitCnt * 3) / 2;
+ arc_queue.pop();
+ queued_arcs.erase(entry.arc);
+ return entry.arc;
+ }
- for (auto pip : ctx->getPipsDownhill(qw.wire)) {
- delay_t next_delay = qw.delay + ctx->getPipDelay(pip).maxDelay();
- WireId next_wire = ctx->getPipDstWire(pip);
- bool foundRipupNet = false;
- thisVisitCnt++;
+ void ripup_net(NetInfo *net)
+ {
+ if (ctx->debug)
+ log(" ripup net %s\n", ctx->nameOf(net));
- next_delay += ctx->getWireDelay(next_wire).maxDelay();
+ netScores[net]++;
- if (!ctx->checkWireAvail(next_wire)) {
- if (!ripup)
- continue;
- NetInfo *ripupWireNet = ctx->getConflictingWireNet(next_wire);
- if (ripupWireNet == nullptr || ripupWireNet->name == net_name)
- continue;
+ std::vector<WireId> wires;
+ for (auto &it : net->wires)
+ wires.push_back(it.first);
- auto it1 = scores.wireScores.find(next_wire);
- if (it1 != scores.wireScores.end())
- next_delay += (it1->second * ripup_penalty) / 8;
+ ctx->sorted_shuffle(wires);
- auto it2 = scores.netWireScores.find(std::make_pair(ripupWireNet->name, next_wire));
- if (it2 != scores.netWireScores.end())
- next_delay += it2->second * ripup_penalty;
+ for (WireId w : wires) {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
- foundRipupNet = true;
- }
+ ctx->sorted_shuffle(arcs);
- if (!ctx->checkPipAvail(pip)) {
- if (!ripup)
- continue;
- NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip);
- if (ripupPipNet == nullptr || ripupPipNet->name == net_name)
- continue;
+ for (auto &it : arcs)
+ arc_queue_insert(it);
- auto it1 = scores.pipScores.find(pip);
- if (it1 != scores.pipScores.end())
- next_delay += (it1->second * ripup_penalty) / 8;
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
- auto it2 = scores.netPipScores.find(std::make_pair(ripupPipNet->name, pip));
- if (it2 != scores.netPipScores.end())
- next_delay += it2->second * ripup_penalty;
+ ctx->unbindWire(w);
+ wireScores[w]++;
+ }
- foundRipupNet = true;
- }
+ ripup_flag = true;
+ }
- if (foundRipupNet)
- next_delay += ripup_penalty;
+ void ripup_wire(WireId wire, int extra_indent = 0)
+ {
+ if (ctx->debug)
+ log(" ripup wire %s\n", ctx->nameOfWire(wire));
- NPNR_ASSERT(next_delay >= 0);
+ WireId w = ctx->getConflictingWireWire(wire);
- if (visited.count(next_wire)) {
- if (visited.at(next_wire).delay <= next_delay + ctx->getDelayEpsilon())
- continue;
-#if 0 // FIXME
- if (ctx->debug)
- log("Found better route to %s. Old vs new delay estimate: %.3f %.3f\n",
- ctx->getWireName(next_wire).c_str(),
- ctx->getDelayNS(visited.at(next_wire).delay),
- ctx->getDelayNS(next_delay));
-#endif
- if (thisVisitCntLimit == 0)
- revisitCnt++;
- else
- overtimeRevisitCnt++;
- }
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingWireNet(wire);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
- QueuedWire next_qw;
- next_qw.wire = next_wire;
- next_qw.pip = pip;
- next_qw.delay = next_delay;
- if (cfg.useEstimate)
- next_qw.togo = ctx->estimateDelay(next_wire, dst_wire);
- next_qw.randtag = ctx->rng();
+ ctx->sorted_shuffle(arcs);
- visited[next_qw.wire] = next_qw;
- queue.push(next_qw);
- }
+ for (auto &it : arcs)
+ arc_queue_insert(it);
+
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
}
- visitCnt += thisVisitCnt;
+ ripup_flag = true;
}
- Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, WireId src_wire, WireId dst_wire,
- bool ripup = false, delay_t ripup_penalty = 0)
- : ctx(ctx), cfg(cfg), scores(scores), ripup(ripup), ripup_penalty(ripup_penalty)
+ void ripup_pip(PipId pip)
{
- std::unordered_map<WireId, delay_t> src_wires;
- src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
- route(src_wires, dst_wire);
- routedOkay = visited.count(dst_wire);
+ if (ctx->debug)
+ log(" ripup pip %s\n", ctx->nameOfPip(pip));
- if (ctx->debug) {
- log("Route (from destination to source):\n");
+ WireId w = ctx->getConflictingPipWire(pip);
+
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingPipNet(pip);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ std::vector<arc_key> arcs;
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arcs.push_back(it);
+ }
+ wire_to_arcs[w].clear();
- WireId cursor = dst_wire;
+ ctx->sorted_shuffle(arcs);
- while (1) {
- log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx));
+ for (auto &it : arcs)
+ arc_queue_insert(it);
- if (cursor == src_wire)
- break;
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->nameOfWire(w));
- cursor = ctx->getPipSrcWire(visited[cursor].pip);
- }
+ ctx->unbindWire(w);
+ wireScores[w]++;
}
+
+ ripup_flag = true;
}
- Router(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores, IdString net_name, int user_idx = -1,
- bool reroute = false, bool ripup = false, delay_t ripup_penalty = 0)
- : ctx(ctx), cfg(cfg), scores(scores), net_name(net_name), ripup(ripup), ripup_penalty(ripup_penalty)
+ bool skip_net(NetInfo *net_info)
{
- auto net_info = ctx->nets.at(net_name).get();
-
- if (ctx->debug)
- log("Routing net %s.\n", net_name.c_str(ctx));
+#ifdef ARCH_ECP5
+ // ECP5 global nets currently appear part-unrouted due to arch database limitations
+ // Don't touch them in the router
+ if (net_info->is_global)
+ return true;
+#endif
+ if (net_info->driver.cell == nullptr)
+ return true;
- if (ctx->debug)
- log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(ctx), net_info->driver.port.c_str(ctx));
+ return false;
+ }
- auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ void check()
+ {
+ std::unordered_set<arc_key, arc_key::Hash> valid_arcs;
- if (src_wire == WireId())
- log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
- net_info->driver.cell->name.c_str(ctx));
+ for (auto &net_it : ctx->nets) {
+ NetInfo *net_info = net_it.second.get();
+ std::unordered_set<WireId> valid_wires_for_net;
- if (ctx->debug)
- log(" Source wire: %s\n", ctx->getWireName(src_wire).c_str(ctx));
-
- std::unordered_map<WireId, delay_t> src_wires;
- std::vector<std::pair<delay_t, int>> users_array;
+ if (skip_net(net_info))
+ continue;
- if (user_idx < 0) {
- // route all users, from worst to best slack
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
- delay_t slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
- users_array.push_back(std::pair<delay_t, int>(slack, user_idx));
- }
- std::sort(users_array.begin(), users_array.end());
- } else {
- // route only the selected user
- users_array.push_back(std::pair<delay_t, int>(delay_t(), user_idx));
- }
+#if 0
+ if (ctx->debug)
+ log("[check] net: %s\n", ctx->nameOf(net_info));
+#endif
- if (reroute) {
- // complete ripup
- ripup_net(ctx, net_name);
- ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
- src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
- } else {
- // re-use existing routes as much as possible
- if (net_info->wires.count(src_wire) == 0)
- ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
- src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ log_assert(src_wire != WireId());
for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ log_assert(dst_wire != WireId());
- if (dst_wire == WireId())
- log_error("No wire found for port %s on destination cell %s.\n",
- net_info->users[user_idx].port.c_str(ctx),
- net_info->users[user_idx].cell->name.c_str(ctx));
-
- std::function<delay_t(WireId)> register_existing_path =
- [ctx, net_info, &src_wires, &register_existing_path](WireId wire) -> delay_t {
- auto it = src_wires.find(wire);
- if (it != src_wires.end())
- return it->second;
-
- PipId pip = net_info->wires.at(wire).pip;
- delay_t delay = register_existing_path(ctx->getPipSrcWire(pip));
- delay += ctx->getPipDelay(pip).maxDelay();
- delay += ctx->getWireDelay(wire).maxDelay();
- src_wires[wire] = delay;
+ arc_key arc;
+ arc.net_info = net_info;
+ arc.user_idx = user_idx;
- return delay;
- };
+ valid_arcs.insert(arc);
+#if 0
+ if (ctx->debug)
+ log("[check] arc: %s %s\n", ctx->nameOfWire(src_wire), ctx->nameOfWire(dst_wire));
+#endif
- WireId cursor = dst_wire;
- while (src_wires.count(cursor) == 0) {
- auto it = net_info->wires.find(cursor);
- if (it == net_info->wires.end())
- goto check_next_user_for_existing_path;
- NPNR_ASSERT(it->second.pip != PipId());
- cursor = ctx->getPipSrcWire(it->second.pip);
+ for (WireId wire : arc_to_wires[arc]) {
+#if 0
+ if (ctx->debug)
+ log("[check] wire: %s\n", ctx->nameOfWire(wire));
+#endif
+ valid_wires_for_net.insert(wire);
+ log_assert(wire_to_arcs[wire].count(arc));
+ log_assert(net_info->wires.count(wire));
}
-
- register_existing_path(dst_wire);
- check_next_user_for_existing_path:;
}
- std::vector<WireId> ripup_wires;
- for (auto &it : net_info->wires)
- if (src_wires.count(it.first) == 0)
- ripup_wires.push_back(it.first);
-
- for (auto &it : ripup_wires) {
- if (ctx->debug)
- log(" Unbind dangling wire for net %s: %s\n", net_name.c_str(ctx),
- ctx->getWireName(it).c_str(ctx));
- ctx->unbindWire(it);
+ for (auto &it : net_info->wires) {
+ WireId w = it.first;
+ log_assert(valid_wires_for_net.count(w));
}
}
- for (auto user_idx_it : users_array) {
- int user_idx = user_idx_it.second;
+ for (auto &it : wire_to_arcs) {
+ for (auto &arc : it.second)
+ log_assert(valid_arcs.count(arc));
+ }
- if (ctx->debug)
- log(" Route to: %s.%s.\n", net_info->users[user_idx].cell->name.c_str(ctx),
- net_info->users[user_idx].port.c_str(ctx));
+ for (auto &it : arc_to_wires) {
+ log_assert(valid_arcs.count(it.first));
+ }
+ }
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ void setup()
+ {
+ std::unordered_map<WireId, NetInfo *> src_to_net;
+ std::unordered_map<WireId, arc_key> dst_to_arc;
- if (dst_wire == WireId())
- log_error("No wire found for port %s on destination cell %s.\n",
- net_info->users[user_idx].port.c_str(ctx), net_info->users[user_idx].cell->name.c_str(ctx));
+ std::vector<IdString> net_names;
+ for (auto &net_it : ctx->nets)
+ net_names.push_back(net_it.first);
- if (ctx->debug) {
- log(" Destination wire: %s\n", ctx->getWireName(dst_wire).c_str(ctx));
- log(" Path delay estimate: %.2f\n", float(ctx->estimateDelay(src_wire, dst_wire)));
- }
+ ctx->sorted_shuffle(net_names);
- route(src_wires, dst_wire);
+ for (IdString net_name : net_names) {
+ NetInfo *net_info = ctx->nets.at(net_name).get();
- if (visited.count(dst_wire) == 0) {
- if (ctx->debug)
- log("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx),
- ctx->getWireName(dst_wire).c_str(ctx));
- else if (ripup)
- log_info("Failed to route %s -> %s.\n", ctx->getWireName(src_wire).c_str(ctx),
- ctx->getWireName(dst_wire).c_str(ctx));
- ripup_net(ctx, net_name);
- failedDest = dst_wire;
- return;
- }
+ if (skip_net(net_info))
+ continue;
- if (ctx->debug)
- log(" Final path delay: %.3f\n", ctx->getDelayNS(visited[dst_wire].delay));
- maxDelay = fmaxf(maxDelay, visited[dst_wire].delay);
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
- if (ctx->debug)
- log(" Route (from destination to source):\n");
+ if (src_wire == WireId())
+ log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(net_info->driver.port),
+ ctx->nameOf(net_info->driver.cell));
- WireId cursor = dst_wire;
+ if (src_to_net.count(src_wire))
+ log_error("Found two nets with same source wire %s: %s vs %s\n", ctx->nameOfWire(src_wire),
+ ctx->nameOf(net_info), ctx->nameOf(src_to_net.at(src_wire)));
- while (1) {
- if (ctx->debug)
- log(" %8.3f %s\n", ctx->getDelayNS(visited[cursor].delay), ctx->getWireName(cursor).c_str(ctx));
+ if (dst_to_arc.count(src_wire))
+ log_error("Wire %s is used as source and sink in different nets: %s vs %s (%d)\n",
+ ctx->nameOfWire(src_wire), ctx->nameOf(net_info),
+ ctx->nameOf(dst_to_arc.at(src_wire).net_info), dst_to_arc.at(src_wire).user_idx);
- if (src_wires.count(cursor))
- break;
+ for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
- NetInfo *conflicting_wire_net = ctx->getConflictingWireNet(cursor);
+ if (dst_wire == WireId())
+ log_error("No wire found for port %s on destination cell %s.\n",
+ ctx->nameOf(net_info->users[user_idx].port),
+ ctx->nameOf(net_info->users[user_idx].cell));
- if (conflicting_wire_net != nullptr) {
- NPNR_ASSERT(ripup);
- NPNR_ASSERT(conflicting_wire_net->name != net_name);
+ if (dst_to_arc.count(dst_wire)) {
+ if (dst_to_arc.at(dst_wire).net_info == net_info)
+ continue;
+ log_error("Found two arcs with same sink wire %s: %s (%d) vs %s (%d)\n",
+ ctx->nameOfWire(dst_wire), ctx->nameOf(net_info), user_idx,
+ ctx->nameOf(dst_to_arc.at(dst_wire).net_info), dst_to_arc.at(dst_wire).user_idx);
+ }
- ctx->unbindWire(cursor);
- if (!ctx->checkWireAvail(cursor))
- ripup_net(ctx, conflicting_wire_net->name);
+ if (src_to_net.count(dst_wire))
+ log_error("Wire %s is used as source and sink in different nets: %s vs %s (%d)\n",
+ ctx->nameOfWire(dst_wire), ctx->nameOf(src_to_net.at(dst_wire)),
+ ctx->nameOf(net_info), user_idx);
- rippedNets.insert(conflicting_wire_net->name);
- scores.wireScores[cursor]++;
- scores.netWireScores[std::make_pair(net_name, cursor)]++;
- scores.netWireScores[std::make_pair(conflicting_wire_net->name, cursor)]++;
- }
+ arc_key arc;
+ arc.net_info = net_info;
+ arc.user_idx = user_idx;
- PipId pip = visited[cursor].pip;
- NetInfo *conflicting_pip_net = ctx->getConflictingPipNet(pip);
+ dst_to_arc[dst_wire] = arc;
- if (conflicting_pip_net != nullptr) {
- NPNR_ASSERT(ripup);
- NPNR_ASSERT(conflicting_pip_net->name != net_name);
+ if (net_info->wires.count(src_wire) == 0) {
+ arc_queue_insert(arc, src_wire, dst_wire);
+ continue;
+ }
- if (ctx->getBoundPipNet(pip) == conflicting_pip_net)
- ctx->unbindPip(pip);
+ WireId cursor = dst_wire;
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
- if (!ctx->checkPipAvail(pip))
- ripup_net(ctx, conflicting_pip_net->name);
+ while (src_wire != cursor) {
+ auto it = net_info->wires.find(cursor);
+ if (it == net_info->wires.end()) {
+ arc_queue_insert(arc, src_wire, dst_wire);
+ break;
+ }
- rippedNets.insert(conflicting_pip_net->name);
- scores.pipScores[visited[cursor].pip]++;
- scores.netPipScores[std::make_pair(net_name, visited[cursor].pip)]++;
- scores.netPipScores[std::make_pair(conflicting_pip_net->name, visited[cursor].pip)]++;
+ NPNR_ASSERT(it->second.pip != PipId());
+ cursor = ctx->getPipSrcWire(it->second.pip);
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
}
-
- ctx->bindPip(visited[cursor].pip, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
- src_wires[cursor] = visited[cursor].delay;
- cursor = ctx->getPipSrcWire(visited[cursor].pip);
}
- }
- routedOkay = true;
- }
-};
+ src_to_net[src_wire] = net_info;
-struct RouteJob
-{
- IdString net;
- int user_idx = -1;
- delay_t slack = 0;
- int randtag = 0;
+ std::vector<WireId> unbind_wires;
- struct Greater
- {
- bool operator()(const RouteJob &lhs, const RouteJob &rhs) const noexcept
- {
- return lhs.slack == rhs.slack ? lhs.randtag > rhs.randtag : lhs.slack > rhs.slack;
- }
- };
-};
+ for (auto &it : net_info->wires)
+ if (it.second.strength < STRENGTH_LOCKED && wire_to_arcs.count(it.first) == 0)
+ unbind_wires.push_back(it.first);
-void addFullNetRouteJob(Context *ctx, const Router1Cfg &cfg, IdString net_name,
- std::unordered_map<IdString, std::vector<bool>> &cache,
- std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue)
-{
- NetInfo *net_info = ctx->nets.at(net_name).get();
+ for (auto it : unbind_wires)
+ ctx->unbindWire(it);
+ }
+ }
- if (net_info->driver.cell == nullptr)
- return;
+ bool route_arc(const arc_key &arc, bool ripup)
+ {
- auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ NetInfo *net_info = arc.net_info;
+ int user_idx = arc.user_idx;
- if (src_wire == WireId())
- log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
- net_info->driver.cell->name.c_str(ctx));
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ ripup_flag = false;
- auto &net_cache = cache[net_name];
+ if (ctx->debug) {
+ log("Routing arc %d on net %s (%d arcs total):\n", user_idx, ctx->nameOf(net_info),
+ int(net_info->users.size()));
+ log(" source ... %s\n", ctx->nameOfWire(src_wire));
+ log(" sink ..... %s\n", ctx->nameOfWire(dst_wire));
+ }
- if (net_cache.empty())
- net_cache.resize(net_info->users.size());
+ // unbind wires that are currently used exclusively by this arc
- RouteJob job;
- job.net = net_name;
- job.user_idx = -1;
- job.slack = 0;
- job.randtag = ctx->rng();
+ std::unordered_set<WireId> old_arc_wires;
+ old_arc_wires.swap(arc_to_wires[arc]);
- bool got_slack = false;
+ for (WireId wire : old_arc_wires) {
+ auto &arc_wires = wire_to_arcs.at(wire);
+ NPNR_ASSERT(arc_wires.count(arc));
+ arc_wires.erase(arc);
+ if (arc_wires.empty()) {
+ if (ctx->debug)
+ log(" unbind %s\n", ctx->nameOfWire(wire));
+ ctx->unbindWire(wire);
+ }
+ }
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- if (net_cache[user_idx])
- continue;
+ // reset wire queue
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ if (!queue.empty()) {
+ std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> new_queue;
+ queue.swap(new_queue);
+ }
+ visited.clear();
- if (dst_wire == WireId())
- log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx),
- net_info->users[user_idx].cell->name.c_str(ctx));
+ // A* main loop
- if (user_idx == 0)
- job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
- else
- job.slack = std::min(job.slack, net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire));
+ int visitCnt = 0;
+ int maxVisitCnt = INT_MAX;
+ delay_t best_est = 0;
+ delay_t best_score = -1;
- WireId cursor = dst_wire;
- while (src_wire != cursor) {
- auto it = net_info->wires.find(cursor);
- if (it == net_info->wires.end()) {
- if (!got_slack)
- job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
- else
- job.slack = std::min(job.slack,
- net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire));
- got_slack = true;
- break;
+ {
+ QueuedWire qw;
+ qw.wire = src_wire;
+ qw.pip = PipId();
+ qw.delay = ctx->getWireDelay(qw.wire).maxDelay();
+ qw.penalty = 0;
+ qw.bonus = 0;
+ if (cfg.useEstimate) {
+ qw.togo = ctx->estimateDelay(qw.wire, dst_wire);
+ best_est = qw.delay + qw.togo;
}
- NPNR_ASSERT(it->second.pip != PipId());
- cursor = ctx->getPipSrcWire(it->second.pip);
+ qw.randtag = ctx->rng();
+
+ queue.push(qw);
+ visited[qw.wire] = qw;
}
- }
- queue.push(job);
+ while (visitCnt++ < maxVisitCnt && !queue.empty()) {
+ QueuedWire qw = queue.top();
+ queue.pop();
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++)
- net_cache[user_idx] = true;
-}
+ for (auto pip : ctx->getPipsDownhill(qw.wire)) {
+ delay_t next_delay = qw.delay + ctx->getPipDelay(pip).maxDelay();
+ delay_t next_penalty = qw.penalty;
+ delay_t next_bonus = qw.bonus;
-void addNetRouteJobs(Context *ctx, const Router1Cfg &cfg, IdString net_name,
- std::unordered_map<IdString, std::vector<bool>> &cache,
- std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &queue)
-{
- NetInfo *net_info = ctx->nets.at(net_name).get();
+ WireId next_wire = ctx->getPipDstWire(pip);
+ next_delay += ctx->getWireDelay(next_wire).maxDelay();
-#ifdef ARCH_ECP5
- // ECP5 global nets currently appear part-unrouted due to arch database limitations
- // Don't touch them in the router
- if (net_info->is_global)
- return;
-#endif
- if (net_info->driver.cell == nullptr)
- return;
+ WireId conflictWireWire = WireId(), conflictPipWire = WireId();
+ NetInfo *conflictWireNet = nullptr, *conflictPipNet = nullptr;
- auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ if (net_info->wires.count(next_wire) && net_info->wires.at(next_wire).pip == pip) {
+ next_bonus += cfg.reuseBonus;
+ } else {
+ if (!ctx->checkWireAvail(next_wire)) {
+ if (!ripup)
+ continue;
+ conflictWireWire = ctx->getConflictingWireWire(next_wire);
+ if (conflictWireWire == WireId()) {
+ conflictWireNet = ctx->getConflictingWireNet(next_wire);
+ if (conflictWireNet == nullptr)
+ continue;
+ }
+ }
- if (src_wire == WireId())
- log_error("No wire found for port %s on source cell %s.\n", net_info->driver.port.c_str(ctx),
- net_info->driver.cell->name.c_str(ctx));
+ if (!ctx->checkPipAvail(pip)) {
+ if (!ripup)
+ continue;
+ conflictPipWire = ctx->getConflictingPipWire(pip);
+ if (conflictPipWire == WireId()) {
+ conflictPipNet = ctx->getConflictingPipNet(pip);
+ if (conflictPipNet == nullptr)
+ continue;
+ }
+ }
- auto &net_cache = cache[net_name];
+ if (conflictWireNet != nullptr && conflictPipWire != WireId() &&
+ conflictWireNet->wires.count(conflictPipWire))
+ conflictPipWire = WireId();
- if (net_cache.empty())
- net_cache.resize(net_info->users.size());
+ if (conflictPipNet != nullptr && conflictWireWire != WireId() &&
+ conflictPipNet->wires.count(conflictWireWire))
+ conflictWireWire = WireId();
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- if (net_cache[user_idx])
- continue;
+ if (conflictWireWire == conflictPipWire)
+ conflictWireWire = WireId();
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ if (conflictWireNet == conflictPipNet)
+ conflictWireNet = nullptr;
- if (dst_wire == WireId())
- log_error("No wire found for port %s on destination cell %s.\n", net_info->users[user_idx].port.c_str(ctx),
- net_info->users[user_idx].cell->name.c_str(ctx));
+ if (conflictWireWire != WireId()) {
+ auto scores_it = wireScores.find(conflictWireWire);
+ if (scores_it != wireScores.end())
+ next_penalty += scores_it->second * cfg.wireRipupPenalty;
+ next_penalty += cfg.wireRipupPenalty;
+ }
- WireId cursor = dst_wire;
- while (src_wire != cursor) {
- auto it = net_info->wires.find(cursor);
- if (it == net_info->wires.end()) {
- RouteJob job;
- job.net = net_name;
- job.user_idx = user_idx;
- job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
- job.randtag = ctx->rng();
- queue.push(job);
- net_cache[user_idx] = true;
- break;
- }
- NPNR_ASSERT(it->second.pip != PipId());
- cursor = ctx->getPipSrcWire(it->second.pip);
- }
- }
-}
+ if (conflictPipWire != WireId()) {
+ auto scores_it = wireScores.find(conflictPipWire);
+ if (scores_it != wireScores.end())
+ next_penalty += scores_it->second * cfg.wireRipupPenalty;
+ next_penalty += cfg.wireRipupPenalty;
+ }
-void cleanupReroute(Context *ctx, const Router1Cfg &cfg, RipupScoreboard &scores,
- std::unordered_set<IdString> &cleanupQueue,
- std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> &jobQueue,
- int &totalVisitCnt, int &totalRevisitCnt, int &totalOvertimeRevisitCnt)
-{
- std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> cleanupJobs;
- std::vector<NetInfo *> allNetinfos;
+ if (conflictWireNet != nullptr) {
+ auto scores_it = netScores.find(conflictWireNet);
+ if (scores_it != netScores.end())
+ next_penalty += scores_it->second * cfg.netRipupPenalty;
+ next_penalty += cfg.netRipupPenalty;
+ next_penalty += conflictWireNet->wires.size() * cfg.wireRipupPenalty;
+ }
- for (auto net_name : cleanupQueue) {
- NetInfo *net_info = ctx->nets.at(net_name).get();
- auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ if (conflictPipNet != nullptr) {
+ auto scores_it = netScores.find(conflictPipNet);
+ if (scores_it != netScores.end())
+ next_penalty += scores_it->second * cfg.netRipupPenalty;
+ next_penalty += cfg.netRipupPenalty;
+ next_penalty += conflictPipNet->wires.size() * cfg.wireRipupPenalty;
+ }
+ }
- if (ctx->verbose)
- allNetinfos.push_back(net_info);
+ delay_t next_score = next_delay + next_penalty;
+ NPNR_ASSERT(next_score >= 0);
- std::unordered_map<WireId, int> useCounters;
- std::vector<int> candidateArcs;
+ if ((best_score >= 0) && (next_score - next_bonus - cfg.estimatePrecision > best_score))
+ continue;
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ auto old_visited_it = visited.find(next_wire);
+ if (old_visited_it != visited.end()) {
+ delay_t old_delay = old_visited_it->second.delay;
+ delay_t old_score = old_delay + old_visited_it->second.penalty;
+ NPNR_ASSERT(old_score >= 0);
- if (dst_wire == src_wire)
- continue;
+ if (next_score + ctx->getDelayEpsilon() >= old_score)
+ continue;
- auto cursor = dst_wire;
- useCounters[cursor]++;
+#if 0
+ if (ctx->debug)
+ log("Found better route to %s. Old vs new delay estimate: %.3f (%.3f) %.3f (%.3f)\n",
+ ctx->nameOfWire(next_wire),
+ ctx->getDelayNS(old_score),
+ ctx->getDelayNS(old_visited_it->second.delay),
+ ctx->getDelayNS(next_score),
+ ctx->getDelayNS(next_delay));
+#endif
+ }
- while (cursor != src_wire) {
- auto it = net_info->wires.find(cursor);
- if (it == net_info->wires.end())
- break;
- cursor = ctx->getPipSrcWire(it->second.pip);
- useCounters[cursor]++;
- }
+ QueuedWire next_qw;
+ next_qw.wire = next_wire;
+ next_qw.pip = pip;
+ next_qw.delay = next_delay;
+ next_qw.penalty = next_penalty;
+ next_qw.bonus = next_bonus;
+ if (cfg.useEstimate) {
+ next_qw.togo = ctx->estimateDelay(next_wire, dst_wire);
+ delay_t this_est = next_qw.delay + next_qw.togo;
+ if (this_est / 2 - cfg.estimatePrecision > best_est)
+ continue;
+ if (best_est > this_est)
+ best_est = this_est;
+ }
+ next_qw.randtag = ctx->rng();
- if (cursor != src_wire)
- continue;
+#if 0
+ if (ctx->debug)
+ log("%s -> %s: %.3f (%.3f)\n",
+ ctx->nameOfWire(qw.wire),
+ ctx->nameOfWire(next_wire),
+ ctx->getDelayNS(next_score),
+ ctx->getDelayNS(next_delay));
+#endif
- candidateArcs.push_back(user_idx);
+ visited[next_qw.wire] = next_qw;
+ queue.push(next_qw);
+
+ if (next_wire == dst_wire) {
+ maxVisitCnt = std::min(maxVisitCnt, 2 * visitCnt + (next_qw.penalty > 0 ? 100 : 0));
+ best_score = next_score - next_bonus;
+ }
+ }
}
- for (int user_idx : candidateArcs) {
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ if (ctx->debug)
+ log(" total number of visited nodes: %d\n", visitCnt);
- if (useCounters.at(dst_wire) != 1)
- continue;
+ if (visited.count(dst_wire) == 0) {
+ if (ctx->debug)
+ log(" no route found for this arc\n");
+ return false;
+ }
- RouteJob job;
- job.net = net_name;
- job.user_idx = user_idx;
- job.slack = net_info->users[user_idx].budget - ctx->estimateDelay(src_wire, dst_wire);
- job.randtag = ctx->rng();
- cleanupJobs.push(job);
+ if (ctx->debug) {
+ log(" final route delay: %8.2f\n", ctx->getDelayNS(visited[dst_wire].delay));
+ log(" final route penalty: %8.2f\n", ctx->getDelayNS(visited[dst_wire].penalty));
+ log(" final route bonus: %8.2f\n", ctx->getDelayNS(visited[dst_wire].bonus));
+ log(" arc budget: %12.2f\n", ctx->getDelayNS(net_info->users[user_idx].budget));
}
- }
- log_info("running cleanup re-route of %d nets (%d arcs).\n", int(cleanupQueue.size()), int(cleanupJobs.size()));
+ // bind resulting route (and maybe unroute other nets)
- cleanupQueue.clear();
+ std::unordered_set<WireId> unassign_wires = arc_to_wires[arc];
- int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0;
- int totalWireCountDelta = 0;
+ WireId cursor = dst_wire;
+ delay_t accumulated_path_delay = 0;
+ delay_t last_path_delay_delta = 0;
+ while (1) {
+ auto pip = visited[cursor].pip;
- if (ctx->verbose) {
- for (auto it : allNetinfos)
- totalWireCountDelta -= it->wires.size();
- }
+ if (ctx->debug) {
+ delay_t path_delay_delta = ctx->estimateDelay(cursor, dst_wire) - accumulated_path_delay;
- while (!cleanupJobs.empty()) {
- RouteJob job = cleanupJobs.top();
- cleanupJobs.pop();
+ log(" node %s (%+.2f %+.2f)\n", ctx->nameOfWire(cursor), ctx->getDelayNS(path_delay_delta),
+ ctx->getDelayNS(path_delay_delta - last_path_delay_delta));
- auto net_name = job.net;
- auto user_idx = job.user_idx;
+ last_path_delay_delta = path_delay_delta;
- NetInfo *net_info = ctx->nets.at(net_name).get();
- auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ if (pip != PipId())
+ accumulated_path_delay += ctx->getPipDelay(pip).maxDelay();
+ accumulated_path_delay += ctx->getWireDelay(cursor).maxDelay();
+ }
- ctx->unbindWire(dst_wire);
+ if (pip == PipId())
+ NPNR_ASSERT(cursor == src_wire);
- Router router(ctx, cfg, scores, net_name, user_idx, false, false);
+ if (!net_info->wires.count(cursor) || net_info->wires.at(cursor).pip != pip) {
+ if (!ctx->checkWireAvail(cursor)) {
+ ripup_wire(cursor);
+ NPNR_ASSERT(ctx->checkWireAvail(cursor));
+ }
- if (!router.routedOkay)
- log_error("Failed to re-route arc %d of net %s.\n", user_idx, net_name.c_str(ctx));
+ if (pip != PipId() && !ctx->checkPipAvail(pip)) {
+ ripup_pip(pip);
+ NPNR_ASSERT(ctx->checkPipAvail(pip));
+ }
- visitCnt += router.visitCnt;
- revisitCnt += router.revisitCnt;
- overtimeRevisitCnt += router.overtimeRevisitCnt;
- }
+ if (pip == PipId()) {
+ if (ctx->debug)
+ log(" bind wire %s\n", ctx->nameOfWire(cursor));
+ ctx->bindWire(cursor, net_info, STRENGTH_WEAK);
+ } else {
+ if (ctx->debug)
+ log(" bind pip %s\n", ctx->nameOfPip(pip));
+ ctx->bindPip(pip, net_info, STRENGTH_WEAK);
+ }
+ }
- if (ctx->verbose) {
- for (auto it : allNetinfos)
- totalWireCountDelta += it->wires.size();
+ wire_to_arcs[cursor].insert(arc);
+ arc_to_wires[arc].insert(cursor);
- log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime), %+d wires.\n", visitCnt,
- (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt, totalWireCountDelta);
- }
+ if (pip == PipId())
+ break;
- totalVisitCnt += visitCnt;
- totalRevisitCnt += revisitCnt;
- totalOvertimeRevisitCnt += overtimeRevisitCnt;
-}
+ cursor = ctx->getPipSrcWire(pip);
+ }
+
+ if (ripup_flag)
+ arcs_with_ripup++;
+ else
+ arcs_without_ripup++;
+
+ return true;
+ }
+};
} // namespace
@@ -694,302 +736,265 @@ Router1Cfg::Router1Cfg(Context *ctx) : Settings(ctx)
cleanupReroute = get<bool>("router1/cleanupReroute", true);
fullCleanupReroute = get<bool>("router1/fullCleanupReroute", true);
useEstimate = get<bool>("router1/useEstimate", true);
+
+ wireRipupPenalty = ctx->getRipupDelayPenalty();
+ netRipupPenalty = 10 * ctx->getRipupDelayPenalty();
+ reuseBonus = wireRipupPenalty / 2;
+
+ estimatePrecision = 100 * ctx->getRipupDelayPenalty();
}
bool router1(Context *ctx, const Router1Cfg &cfg)
{
try {
- int totalVisitCnt = 0, totalRevisitCnt = 0, totalOvertimeRevisitCnt = 0;
- delay_t ripup_penalty = ctx->getRipupDelayPenalty();
- RipupScoreboard scores;
-
log_break();
log_info("Routing..\n");
ctx->lock();
- std::unordered_set<IdString> cleanupQueue;
- std::unordered_map<IdString, std::vector<bool>> jobCache;
- std::priority_queue<RouteJob, std::vector<RouteJob>, RouteJob::Greater> jobQueue;
+ log_info("Setting up routing queue.\n");
- for (auto &net_it : ctx->nets)
- addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
+ Router1 router(ctx, cfg);
+ router.setup();
+#ifndef NDEBUG
+ router.check();
+#endif
- if (jobQueue.empty()) {
- log_info("found no unrouted source-sink pairs. no routing necessary.\n");
- ctx->unlock();
- return true;
- }
+ log_info("Routing %d arcs.\n", int(router.arc_queue.size()));
+
+ int iter_cnt = 0;
+ int last_arcs_with_ripup = 0;
+ int last_arcs_without_ripup = 0;
+
+ log_info(" | (re-)routed arcs | delta | remaining\n");
+ log_info(" IterCnt | w/ripup wo/ripup | w/r wo/r | arcs\n");
+
+ while (!router.arc_queue.empty()) {
+ if (++iter_cnt % 1000 == 0) {
+ log_info("%10d | %8d %10d | %4d %5d | %9d\n", iter_cnt, router.arcs_with_ripup,
+ router.arcs_without_ripup, router.arcs_with_ripup - last_arcs_with_ripup,
+ router.arcs_without_ripup - last_arcs_without_ripup, int(router.arc_queue.size()));
+ last_arcs_with_ripup = router.arcs_with_ripup;
+ last_arcs_without_ripup = router.arcs_without_ripup;
+#ifndef NDEBUG
+ router.check();
+#endif
+ }
- log_info("found %d unrouted source-sink pairs. starting routing procedure.\n", int(jobQueue.size()));
+ if (ctx->debug)
+ log("-- %d --\n", iter_cnt);
- int iterCnt = 0;
+ arc_key arc = router.arc_queue_pop();
- while (!jobQueue.empty()) {
- if (iterCnt == cfg.maxIterCnt) {
- log_warning("giving up after %d iterations.\n", iterCnt);
- log_info("Checksum: 0x%08x\n", ctx->checksum());
+ if (!router.route_arc(arc, true)) {
+ log_warning("Failed to find a route for arc %d of net %s.\n", arc.user_idx, ctx->nameOf(arc.net_info));
#ifndef NDEBUG
+ router.check();
ctx->check();
#endif
ctx->unlock();
return false;
}
+ }
- iterCnt++;
- if (ctx->verbose)
- log_info("-- %d --\n", iterCnt);
-
- int visitCnt = 0, revisitCnt = 0, overtimeRevisitCnt = 0, jobCnt = 0, failedCnt = 0;
+ log_info("%10d | %8d %10d | %4d %5d | %9d\n", iter_cnt, router.arcs_with_ripup, router.arcs_without_ripup,
+ router.arcs_with_ripup - last_arcs_with_ripup, router.arcs_without_ripup - last_arcs_without_ripup,
+ int(router.arc_queue.size()));
+ log_info("Routing complete.\n");
- std::unordered_set<IdString> normalRouteNets, ripupQueue;
+#ifndef NDEBUG
+ router.check();
+ ctx->check();
+ log_assert(ctx->checkRoutedDesign());
+#endif
- if (ctx->verbose || iterCnt == 1)
- log_info("routing queue contains %d jobs.\n", int(jobQueue.size()));
- else if (ctx->slack_redist_iter > 0 && iterCnt % ctx->slack_redist_iter == 0)
- assign_budget(ctx, true /* quiet */);
+ log_info("Checksum: 0x%08x\n", ctx->checksum());
+ timing_analysis(ctx, true /* slack_histogram */, true /* print_fmax */, true /* print_path */);
- bool printNets = ctx->verbose && (jobQueue.size() < 10);
+ ctx->unlock();
+ return true;
+ } catch (log_execution_error_exception) {
+#ifndef NDEBUG
+ ctx->check();
+#endif
+ ctx->unlock();
+ return false;
+ }
+}
- while (!jobQueue.empty()) {
- if (ctx->debug)
- log("Next job slack: %f\n", double(jobQueue.top().slack));
+bool Context::checkRoutedDesign() const
+{
+ const Context *ctx = getCtx();
- auto net_name = jobQueue.top().net;
- auto user_idx = jobQueue.top().user_idx;
- jobQueue.pop();
+ for (auto &net_it : ctx->nets) {
+ NetInfo *net_info = net_it.second.get();
- if (cfg.fullCleanupReroute)
- cleanupQueue.insert(net_name);
+#ifdef ARCH_ECP5
+ if (net_info->is_global)
+ continue;
+#endif
- if (printNets) {
- if (user_idx < 0)
- log_info(" routing all %d users of net %s\n", int(ctx->nets.at(net_name)->users.size()),
- net_name.c_str(ctx));
- else
- log_info(" routing user %d of net %s\n", user_idx, net_name.c_str(ctx));
- }
+ if (ctx->debug)
+ log("checking net %s\n", ctx->nameOf(net_info));
- Router router(ctx, cfg, scores, net_name, user_idx, false, false);
+ if (net_info->users.empty()) {
+ if (ctx->debug)
+ log(" net without sinks\n");
+ log_assert(net_info->wires.empty());
+ continue;
+ }
- jobCnt++;
- visitCnt += router.visitCnt;
- revisitCnt += router.revisitCnt;
- overtimeRevisitCnt += router.overtimeRevisitCnt;
+ bool found_unrouted = false;
+ bool found_loop = false;
+ bool found_stub = false;
- if (!router.routedOkay) {
- if (printNets)
- log_info(" failed to route to %s.\n", ctx->getWireName(router.failedDest).c_str(ctx));
- ripupQueue.insert(net_name);
- failedCnt++;
- } else {
- normalRouteNets.insert(net_name);
- }
+ struct ExtraWireInfo
+ {
+ int order_num = 0;
+ std::unordered_set<WireId> children;
+ };
- if ((ctx->verbose || iterCnt == 1) && !printNets && (jobCnt % 100 == 0)) {
- log_info(" processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt);
- ctx->yield();
- }
- }
+ std::unordered_map<WireId, ExtraWireInfo> db;
- NPNR_ASSERT(jobQueue.empty());
- jobCache.clear();
+ for (auto &it : net_info->wires) {
+ WireId w = it.first;
+ PipId p = it.second.pip;
- if ((ctx->verbose || iterCnt == 1) && (jobCnt % 100 != 0)) {
- log_info(" processed %d jobs. (%d routed, %d failed)\n", jobCnt, jobCnt - failedCnt, failedCnt);
- ctx->yield();
+ if (p != PipId()) {
+ log_assert(ctx->getPipDstWire(p) == w);
+ db[ctx->getPipSrcWire(p)].children.insert(w);
}
+ }
- if (ctx->verbose)
- log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", visitCnt,
- (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
-
- if (!ripupQueue.empty()) {
- if (ctx->verbose || iterCnt == 1)
- log_info("failed to route %d nets. re-routing in ripup mode.\n", int(ripupQueue.size()));
-
- printNets = ctx->verbose && (ripupQueue.size() < 10);
-
- visitCnt = 0;
- revisitCnt = 0;
- overtimeRevisitCnt = 0;
- int netCnt = 0;
- int ripCnt = 0;
-
- std::vector<IdString> ripupArray(ripupQueue.begin(), ripupQueue.end());
- ctx->sorted_shuffle(ripupArray);
-
- for (auto net_name : ripupArray) {
- if (cfg.cleanupReroute)
- cleanupQueue.insert(net_name);
-
- if (printNets)
- log_info(" routing net %s. (%d users)\n", net_name.c_str(ctx),
- int(ctx->nets.at(net_name)->users.size()));
-
- Router router(ctx, cfg, scores, net_name, -1, false, true, ripup_penalty);
-
- netCnt++;
- visitCnt += router.visitCnt;
- revisitCnt += router.revisitCnt;
- overtimeRevisitCnt += router.overtimeRevisitCnt;
+ auto src_wire = ctx->getNetinfoSourceWire(net_info);
+ log_assert(src_wire != WireId());
- if (!router.routedOkay)
- log_error("Net %s is impossible to route.\n", net_name.c_str(ctx));
+ if (net_info->wires.count(src_wire) == 0) {
+ if (ctx->debug)
+ log(" source (%s) not bound to net\n", ctx->nameOfWire(src_wire));
+ found_unrouted = true;
+ }
- for (auto it : router.rippedNets) {
- addFullNetRouteJob(ctx, cfg, it, jobCache, jobQueue);
- if (cfg.cleanupReroute)
- cleanupQueue.insert(it);
- }
+ std::unordered_map<WireId, int> dest_wires;
+ for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
+ auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]);
+ log_assert(dst_wire != WireId());
+ dest_wires[dst_wire] = user_idx;
- if (printNets) {
- if (router.rippedNets.size() < 10) {
- log_info(" ripped up %d other nets:\n", int(router.rippedNets.size()));
- for (auto n : router.rippedNets)
- log_info(" %s (%d users)\n", n.c_str(ctx), int(ctx->nets.at(n)->users.size()));
- } else {
- log_info(" ripped up %d other nets.\n", int(router.rippedNets.size()));
- }
- }
+ if (net_info->wires.count(dst_wire) == 0) {
+ if (ctx->debug)
+ log(" sink %d (%s) not bound to net\n", user_idx, ctx->nameOfWire(dst_wire));
+ found_unrouted = true;
+ }
+ }
- ripCnt += router.rippedNets.size();
+ std::function<void(WireId, int)> setOrderNum;
+ std::unordered_set<WireId> logged_wires;
- if ((ctx->verbose || iterCnt == 1) && !printNets && (netCnt % 100 == 0)) {
- log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt);
- ctx->yield();
- }
+ setOrderNum = [&](WireId w, int num) {
+ auto &db_entry = db[w];
+ if (db_entry.order_num != 0) {
+ found_loop = true;
+ log(" %*s=> loop\n", 2 * num, "");
+ return;
+ }
+ db_entry.order_num = num;
+ for (WireId child : db_entry.children) {
+ if (ctx->debug) {
+ log(" %*s-> %s\n", 2 * num, "", ctx->nameOfWire(child));
+ logged_wires.insert(child);
}
-
- if ((ctx->verbose || iterCnt == 1) && (netCnt % 100 != 0))
- log_info(" routed %d nets, ripped %d nets.\n", netCnt, ripCnt);
-
- if (ctx->verbose)
- log_info(" visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", visitCnt,
- (100.0 * revisitCnt) / visitCnt, (100.0 * overtimeRevisitCnt) / visitCnt);
-
- if (ctx->verbose && !jobQueue.empty())
- log_info(" ripped up %d previously routed nets. continue routing.\n", int(jobQueue.size()));
+ setOrderNum(child, num + 1);
}
+ if (db_entry.children.empty()) {
+ if (dest_wires.count(w) != 0) {
+ if (ctx->debug)
+ log(" %*s=> sink %d\n", 2 * num, "", dest_wires.at(w));
+ } else {
+ if (ctx->debug)
+ log(" %*s=> stub\n", 2 * num, "");
+ found_stub = true;
+ }
+ }
+ };
- if (!ctx->verbose)
- log_info("iteration %d: routed %d nets without ripup, routed %d nets with ripup.\n", iterCnt,
- int(normalRouteNets.size()), int(ripupQueue.size()));
-
- totalVisitCnt += visitCnt;
- totalRevisitCnt += revisitCnt;
- totalOvertimeRevisitCnt += overtimeRevisitCnt;
-
- if (iterCnt == 8 || iterCnt == 16 || iterCnt == 32 || iterCnt == 64 || iterCnt == 128)
- ripup_penalty += ctx->getRipupDelayPenalty();
+ if (ctx->debug) {
+ log(" driver: %s\n", ctx->nameOfWire(src_wire));
+ logged_wires.insert(src_wire);
+ }
+ setOrderNum(src_wire, 1);
- if (jobQueue.empty() || (iterCnt % 5) == 0 || (cfg.fullCleanupReroute && iterCnt == 1))
- cleanupReroute(ctx, cfg, scores, cleanupQueue, jobQueue, totalVisitCnt, totalRevisitCnt,
- totalOvertimeRevisitCnt);
+ std::unordered_set<WireId> dangling_wires;
- ctx->yield();
+ for (auto &it : db) {
+ auto &db_entry = it.second;
+ if (db_entry.order_num == 0)
+ dangling_wires.insert(it.first);
}
- log_info("routing complete after %d iterations.\n", iterCnt);
+ if (ctx->debug) {
+ if (dangling_wires.empty()) {
+ log(" no dangling wires.\n");
+ } else {
+ std::unordered_set<WireId> root_wires = dangling_wires;
+
+ for (WireId w : dangling_wires) {
+ for (WireId c : db[w].children)
+ root_wires.erase(c);
+ }
- log_info("visited %d PIPs (%.2f%% revisits, %.2f%% overtime revisits).\n", totalVisitCnt,
- (100.0 * totalRevisitCnt) / totalVisitCnt, (100.0 * totalOvertimeRevisitCnt) / totalVisitCnt);
+ for (WireId w : root_wires) {
+ log(" dangling wire: %s\n", ctx->nameOfWire(w));
+ logged_wires.insert(w);
+ setOrderNum(w, 1);
+ }
- {
- float tns = 0;
- int tns_net_count = 0;
- int tns_arc_count = 0;
- for (auto &net_it : ctx->nets) {
- bool got_negative_slack = false;
- NetInfo *net_info = ctx->nets.at(net_it.first).get();
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- delay_t arc_delay = ctx->getNetinfoRouteDelay(net_info, net_info->users[user_idx]);
- delay_t arc_budget = net_info->users[user_idx].budget;
- delay_t arc_slack = arc_budget - arc_delay;
- if (arc_slack < 0) {
- if (!got_negative_slack) {
- if (ctx->verbose)
- log_info("net %s has negative slack arcs:\n", net_info->name.c_str(ctx));
- tns_net_count++;
- }
- if (ctx->verbose)
- log_info(" arc %s -> %s has %f ns slack (delay %f, budget %f)\n",
- ctx->getWireName(ctx->getNetinfoSourceWire(net_info)).c_str(ctx),
- ctx->getWireName(ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx]))
- .c_str(ctx),
- ctx->getDelayNS(arc_slack), ctx->getDelayNS(arc_delay),
- ctx->getDelayNS(arc_budget));
- tns += ctx->getDelayNS(arc_slack);
- tns_arc_count++;
- }
+ for (WireId w : dangling_wires) {
+ if (logged_wires.count(w) == 0)
+ log(" loop: %s -> %s\n",
+ ctx->nameOfWire(ctx->getPipSrcWire(net_info->wires.at(w).pip)),
+ ctx->nameOfWire(w));
}
}
- log_info("final tns with respect to arc budgets: %f ns (%d nets, %d arcs)\n", tns, tns_net_count,
- tns_arc_count);
}
- NPNR_ASSERT(jobQueue.empty());
- jobCache.clear();
+ bool fail = false;
- for (auto &net_it : ctx->nets)
- addNetRouteJobs(ctx, cfg, net_it.first, jobCache, jobQueue);
+ if (found_unrouted) {
+ if (ctx->debug)
+ log("check failed: found unrouted arcs\n");
+ fail = true;
+ }
-#ifndef NDEBUG
- if (!jobQueue.empty()) {
- log_info("Design strangely still contains unrouted source-sink pairs:\n");
- while (!jobQueue.empty()) {
- log_info(" user %d on net %s.\n", jobQueue.top().user_idx, jobQueue.top().net.c_str(ctx));
- jobQueue.pop();
- }
- log_info("Checksum: 0x%08x\n", ctx->checksum());
- ctx->check();
- ctx->unlock();
- return false;
+ if (found_loop) {
+ if (ctx->debug)
+ log("check failed: found loops\n");
+ fail = true;
}
-#endif
- log_info("Checksum: 0x%08x\n", ctx->checksum());
-#ifndef NDEBUG
- ctx->check();
-#endif
- timing_analysis(ctx, true /* slack_histogram */, true /* print_path */);
- ctx->unlock();
- return true;
- } catch (log_execution_error_exception) {
-#ifndef NDEBUG
- ctx->check();
-#endif
- ctx->unlock();
- return false;
+ if (found_stub) {
+ if (ctx->debug)
+ log("check failed: found stubs\n");
+ fail = true;
+ }
+
+ if (!dangling_wires.empty()) {
+ if (ctx->debug)
+ log("check failed: found dangling wires\n");
+ fail = true;
+ }
+
+ if (fail)
+ return false;
}
+
+ return true;
}
bool Context::getActualRouteDelay(WireId src_wire, WireId dst_wire, delay_t *delay,
std::unordered_map<WireId, PipId> *route, bool useEstimate)
{
- RipupScoreboard scores;
- Router1Cfg cfg(this);
- cfg.useEstimate = useEstimate;
-
- Router router(this, cfg, scores, src_wire, dst_wire);
-
- if (!router.routedOkay)
- return false;
-
- if (delay != nullptr)
- *delay = router.visited.at(dst_wire).delay;
-
- if (route != nullptr) {
- WireId cursor = dst_wire;
- while (1) {
- PipId pip = router.visited.at(cursor).pip;
- (*route)[cursor] = pip;
- if (pip == PipId())
- break;
- cursor = getPipSrcWire(pip);
- }
- }
-
- return true;
+ // FIXME
+ return false;
}
NEXTPNR_NAMESPACE_END
diff --git a/common/router1.h b/common/router1.h
index a184cbe7..80d7aa96 100644
--- a/common/router1.h
+++ b/common/router1.h
@@ -33,6 +33,10 @@ struct Router1Cfg : Settings
bool cleanupReroute;
bool fullCleanupReroute;
bool useEstimate;
+ delay_t wireRipupPenalty;
+ delay_t netRipupPenalty;
+ delay_t reuseBonus;
+ delay_t estimatePrecision;
};
extern bool router1(Context *ctx, const Router1Cfg &cfg);
diff --git a/common/timing.cc b/common/timing.cc
index d1a85779..40e4d344 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -22,6 +22,7 @@
#include <algorithm>
#include <boost/range/adaptor/reversed.hpp>
#include <deque>
+#include <map>
#include <unordered_map>
#include <utility>
#include "log.h"
@@ -29,17 +30,72 @@
NEXTPNR_NAMESPACE_BEGIN
+namespace {
+struct ClockEvent
+{
+ IdString clock;
+ ClockEdge edge;
+
+ bool operator==(const ClockEvent &other) const { return clock == other.clock && edge == other.edge; }
+};
+
+struct ClockPair
+{
+ ClockEvent start, end;
+
+ bool operator==(const ClockPair &other) const { return start == other.start && end == other.end; }
+};
+} // namespace
+
+NEXTPNR_NAMESPACE_END
+namespace std {
+
+template <> struct hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>
+{
+ std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX ClockEvent &obj) const noexcept
+ {
+ std::size_t seed = 0;
+ boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX IdString>()(obj.clock));
+ boost::hash_combine(seed, hash<int>()(int(obj.edge)));
+ return seed;
+ }
+};
+
+template <> struct hash<NEXTPNR_NAMESPACE_PREFIX ClockPair>
+{
+ std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX ClockPair &obj) const noexcept
+ {
+ std::size_t seed = 0;
+ boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>()(obj.start));
+ boost::hash_combine(seed, hash<NEXTPNR_NAMESPACE_PREFIX ClockEvent>()(obj.start));
+ return seed;
+ }
+};
+
+} // namespace std
+NEXTPNR_NAMESPACE_BEGIN
+
typedef std::vector<const PortRef *> PortRefVector;
typedef std::map<int, unsigned> DelayFrequency;
+struct CriticalPath
+{
+ PortRefVector ports;
+ delay_t path_delay;
+ delay_t path_period;
+};
+
+typedef std::unordered_map<ClockPair, CriticalPath> CriticalPathMap;
+
struct Timing
{
Context *ctx;
bool net_delays;
bool update;
delay_t min_slack;
- PortRefVector *crit_path;
+ CriticalPathMap *crit_path;
DelayFrequency *slack_histogram;
+ IdString async_clock;
struct TimingData
{
@@ -49,23 +105,24 @@ struct Timing
unsigned max_path_length = 0;
delay_t min_remaining_budget;
bool false_startpoint = false;
+ std::unordered_map<ClockEvent, delay_t> arrival_time;
};
- Timing(Context *ctx, bool net_delays, bool update, PortRefVector *crit_path = nullptr,
+ Timing(Context *ctx, bool net_delays, bool update, CriticalPathMap *crit_path = nullptr,
DelayFrequency *slack_histogram = nullptr)
: ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->target_freq),
- crit_path(crit_path), slack_histogram(slack_histogram)
+ crit_path(crit_path), slack_histogram(slack_histogram), async_clock(ctx->id("$async$"))
{
}
delay_t walk_paths()
{
- const auto clk_period = delay_t(1.0e12 / ctx->target_freq);
+ const auto clk_period = ctx->getDelayFromNS(1.0e9 / ctx->target_freq).maxDelay();
// First, compute the topographical order of nets to walk through the circuit, assuming it is a _acyclic_ graph
// TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops
std::vector<NetInfo *> topographical_order;
- std::unordered_map<const NetInfo *, TimingData> net_data;
+ std::unordered_map<const NetInfo *, std::unordered_map<ClockEvent, TimingData>> net_data;
// In lieu of deleting edges from the graph, simply count the number of fanins to each output port
std::unordered_map<const PortInfo *, unsigned> port_fanin;
@@ -84,22 +141,34 @@ struct Timing
}
for (auto o : output_ports) {
- IdString clockPort;
- TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clockPort);
+ int clocks = 0;
+ TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clocks);
// If output port is influenced by a clock (e.g. FF output) then add it to the ordering as a timing
// start-point
if (portClass == TMG_REGISTER_OUTPUT) {
- DelayInfo clkToQ;
- ctx->getCellDelay(cell.second.get(), clockPort, o->name, clkToQ);
topographical_order.emplace_back(o->net);
- net_data.emplace(o->net, TimingData{clkToQ.maxDelay()});
+ for (int i = 0; i < clocks; i++) {
+ TimingClockingInfo clkInfo = ctx->getPortClockingInfo(cell.second.get(), o->name, i);
+ const NetInfo *clknet = get_net_or_empty(cell.second.get(), clkInfo.clock_port);
+ IdString clksig = clknet ? clknet->name : async_clock;
+ net_data[o->net][ClockEvent{clksig, clknet ? clkInfo.edge : RISING_EDGE}] =
+ TimingData{clkInfo.clockToQ.maxDelay()};
+ }
+
} else {
if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) {
topographical_order.emplace_back(o->net);
TimingData td;
td.false_startpoint = (portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE);
- net_data.emplace(o->net, std::move(td));
+ td.max_arrival = 0;
+ net_data[o->net][ClockEvent{async_clock, RISING_EDGE}] = td;
}
+
+ // Don't analyse paths from a clock input to other pins - they will be considered by the
+ // special-case handling register input/output class ports
+ if (portClass == TMG_CLOCK_INPUT)
+ continue;
+
// Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and
// the current output port, increment fanin counter
for (auto i : input_ports) {
@@ -120,14 +189,15 @@ struct Timing
queue.pop_front();
for (auto &usr : net->users) {
- IdString clockPort;
- TimingPortClass usrClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort);
+ int user_clocks;
+ TimingPortClass usrClass = ctx->getPortTimingClass(usr.cell, usr.port, user_clocks);
if (usrClass == TMG_IGNORE || usrClass == TMG_CLOCK_INPUT)
continue;
for (auto &port : usr.cell->ports) {
if (port.second.type != PORT_OUT || !port.second.net)
continue;
- TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, port.first, clockPort);
+ int port_clocks;
+ TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, port.first, port_clocks);
// Skip if this is a clocked output (but allow non-clocked ones)
if (portClass == TMG_REGISTER_OUTPUT || portClass == TMG_STARTPOINT || portClass == TMG_IGNORE ||
@@ -166,142 +236,221 @@ struct Timing
log_info(" remaining fanin includes %s (no net)\n", fanin.first->name.c_str(ctx));
}
}
+ if (ctx->force)
+ log_warning("timing analysis failed due to presence of combinatorial loops, incomplete specification of timing ports, etc.\n");
+ else
+ log_error("timing analysis failed due to presence of combinatorial loops, incomplete specification of timing ports, etc.\n");
}
- NPNR_ASSERT(port_fanin.empty());
// Go forwards topographically to find the maximum arrival time and max path length for each net
for (auto net : topographical_order) {
- auto &nd = net_data.at(net);
- const auto net_arrival = nd.max_arrival;
- const auto net_length_plus_one = nd.max_path_length + 1;
- nd.min_remaining_budget = clk_period;
- for (auto &usr : net->users) {
- IdString clockPort;
- TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort);
- if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE) {
- } else {
+ if (!net_data.count(net))
+ continue;
+ auto &nd_map = net_data.at(net);
+ for (auto &startdomain : nd_map) {
+ ClockEvent start_clk = startdomain.first;
+ auto &nd = startdomain.second;
+ if (nd.false_startpoint)
+ continue;
+ const auto net_arrival = nd.max_arrival;
+ const auto net_length_plus_one = nd.max_path_length + 1;
+ nd.min_remaining_budget = clk_period;
+ for (auto &usr : net->users) {
+ int port_clocks;
+ TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, port_clocks);
auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
- auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
auto usr_arrival = net_arrival + net_delay;
- // Iterate over all output ports on the same cell as the sink
- for (auto port : usr.cell->ports) {
- if (port.second.type != PORT_OUT || !port.second.net)
- continue;
- DelayInfo comb_delay;
- // Look up delay through this path
- bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
- if (!is_path)
- continue;
- auto &data = net_data[port.second.net];
- auto &arrival = data.max_arrival;
- arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay());
- if (!budget_override) { // Do not increment path length if budget overriden since it doesn't
- // require a share of the slack
- auto &path_length = data.max_path_length;
- path_length = std::max(path_length, net_length_plus_one);
+
+ if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE ||
+ portClass == TMG_CLOCK_INPUT) {
+ // Skip
+ } else {
+ auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
+ // Iterate over all output ports on the same cell as the sink
+ for (auto port : usr.cell->ports) {
+ if (port.second.type != PORT_OUT || !port.second.net)
+ continue;
+ DelayInfo comb_delay;
+ // Look up delay through this path
+ bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
+ if (!is_path)
+ continue;
+ auto &data = net_data[port.second.net][start_clk];
+ auto &arrival = data.max_arrival;
+ arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay());
+ if (!budget_override) { // Do not increment path length if budget overriden since it doesn't
+ // require a share of the slack
+ auto &path_length = data.max_path_length;
+ path_length = std::max(path_length, net_length_plus_one);
+ }
}
}
}
}
}
- const NetInfo *crit_net = nullptr;
+ std::unordered_map<ClockPair, std::pair<delay_t, NetInfo *>> crit_nets;
// Now go backwards topographically to determine the minimum path slack, and to distribute all path slack evenly
// between all nets on the path
for (auto net : boost::adaptors::reverse(topographical_order)) {
- auto &nd = net_data.at(net);
- // Ignore false startpoints
- if (nd.false_startpoint) continue;
- const delay_t net_length_plus_one = nd.max_path_length + 1;
- auto &net_min_remaining_budget = nd.min_remaining_budget;
- for (auto &usr : net->users) {
- auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
- auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
- IdString associatedClock;
- TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, associatedClock);
- if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) {
- const auto net_arrival = nd.max_arrival;
- auto path_budget = clk_period - (net_arrival + net_delay);
- if (update) {
- auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
- usr.budget = std::min(usr.budget, net_delay + budget_share);
- net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share);
- }
+ if (!net_data.count(net))
+ continue;
+ auto &nd_map = net_data.at(net);
+ for (auto &startdomain : nd_map) {
+ auto &nd = startdomain.second;
+ // Ignore false startpoints
+ if (nd.false_startpoint)
+ continue;
+ const delay_t net_length_plus_one = nd.max_path_length + 1;
+ auto &net_min_remaining_budget = nd.min_remaining_budget;
+ for (auto &usr : net->users) {
+ auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
+ auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
+ int port_clocks;
+ TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, port_clocks);
+ if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) {
+ auto process_endpoint = [&](IdString clksig, ClockEdge edge, delay_t setup) {
+ const auto net_arrival = nd.max_arrival;
+ const auto endpoint_arrival = net_arrival + net_delay + setup;
+ delay_t period;
+ // Set default period
+ if (edge == startdomain.first.edge) {
+ period = clk_period;
+ } else {
+ period = clk_period / 2;
+ }
+ if (clksig != async_clock) {
+ if (ctx->nets.at(clksig)->clkconstr) {
+ if (edge == startdomain.first.edge) {
+ // same edge
+ period = ctx->nets.at(clksig)->clkconstr->period.minDelay();
+ } else if (edge == RISING_EDGE) {
+ // falling -> rising
+ period = ctx->nets.at(clksig)->clkconstr->low.minDelay();
+ } else if (edge == FALLING_EDGE) {
+ // rising -> falling
+ period = ctx->nets.at(clksig)->clkconstr->high.minDelay();
+ }
+ }
+ }
+ auto path_budget = period - endpoint_arrival;
+
+ if (update) {
+ auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
+ usr.budget = std::min(usr.budget, net_delay + budget_share);
+ net_min_remaining_budget =
+ std::min(net_min_remaining_budget, path_budget - budget_share);
+ }
+
+ if (path_budget < min_slack)
+ min_slack = path_budget;
+
+ if (slack_histogram) {
+ int slack_ps = ctx->getDelayNS(path_budget) * 1000;
+ (*slack_histogram)[slack_ps]++;
+ }
+ ClockEvent dest_ev{clksig, edge};
+ ClockPair clockPair{startdomain.first, dest_ev};
+ nd.arrival_time[dest_ev] = std::max(nd.arrival_time[dest_ev], endpoint_arrival);
+
+ if (crit_path) {
+ if (!crit_nets.count(clockPair) || crit_nets.at(clockPair).first < endpoint_arrival) {
+ crit_nets[clockPair] = std::make_pair(endpoint_arrival, net);
+ (*crit_path)[clockPair].path_delay = endpoint_arrival;
+ (*crit_path)[clockPair].path_period = period;
+ (*crit_path)[clockPair].ports.clear();
+ (*crit_path)[clockPair].ports.push_back(&usr);
+ }
+ }
+ };
+ if (portClass == TMG_REGISTER_INPUT) {
+ for (int i = 0; i < port_clocks; i++) {
+ TimingClockingInfo clkInfo = ctx->getPortClockingInfo(usr.cell, usr.port, i);
+ const NetInfo *clknet = get_net_or_empty(usr.cell, clkInfo.clock_port);
+ IdString clksig = clknet ? clknet->name : async_clock;
+ process_endpoint(clksig, clknet ? clkInfo.edge : RISING_EDGE, clkInfo.setup.maxDelay());
+ }
+ } else {
+ process_endpoint(async_clock, RISING_EDGE, 0);
+ }
- if (path_budget < min_slack) {
- min_slack = path_budget;
- if (crit_path) {
- crit_path->clear();
- crit_path->push_back(&usr);
- crit_net = net;
+ } else if (update) {
+
+ // Iterate over all output ports on the same cell as the sink
+ for (const auto &port : usr.cell->ports) {
+ if (port.second.type != PORT_OUT || !port.second.net)
+ continue;
+ DelayInfo comb_delay;
+ bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
+ if (!is_path)
+ continue;
+ if (net_data.count(port.second.net) &&
+ net_data.at(port.second.net).count(startdomain.first)) {
+ auto path_budget =
+ net_data.at(port.second.net).at(startdomain.first).min_remaining_budget;
+ auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
+ usr.budget = std::min(usr.budget, net_delay + budget_share);
+ net_min_remaining_budget =
+ std::min(net_min_remaining_budget, path_budget - budget_share);
+ }
}
}
- if (slack_histogram) {
- int slack_ps = ctx->getDelayNS(path_budget) * 1000;
- (*slack_histogram)[slack_ps]++;
- }
- } else if (update) {
- // Iterate over all output ports on the same cell as the sink
- for (const auto &port : usr.cell->ports) {
- if (port.second.type != PORT_OUT || !port.second.net)
- continue;
- DelayInfo comb_delay;
- bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
- if (!is_path)
- continue;
- auto path_budget = net_data.at(port.second.net).min_remaining_budget;
- auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
- usr.budget = std::min(usr.budget, net_delay + budget_share);
- net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share);
- }
}
}
}
if (crit_path) {
// Walk backwards from the most critical net
- while (crit_net) {
- const PortInfo *crit_ipin = nullptr;
- delay_t max_arrival = std::numeric_limits<delay_t>::min();
-
- // Look at all input ports on its driving cell
- for (const auto &port : crit_net->driver.cell->ports) {
- if (port.second.type != PORT_IN || !port.second.net)
- continue;
- DelayInfo comb_delay;
- bool is_path =
- ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay);
- if (!is_path)
- continue;
- // If input port is influenced by a clock, skip
- IdString portClock;
- TimingPortClass portClass = ctx->getPortTimingClass(crit_net->driver.cell, port.first, portClock);
- if (portClass == TMG_REGISTER_INPUT || portClass == TMG_CLOCK_INPUT || portClass == TMG_ENDPOINT ||
- portClass == TMG_IGNORE)
- continue;
+ for (auto crit_pair : crit_nets) {
+ NetInfo *crit_net = crit_pair.second.second;
+ auto &cp_ports = (*crit_path)[crit_pair.first].ports;
+ while (crit_net) {
+ const PortInfo *crit_ipin = nullptr;
+ delay_t max_arrival = std::numeric_limits<delay_t>::min();
+
+ // Look at all input ports on its driving cell
+ for (const auto &port : crit_net->driver.cell->ports) {
+ if (port.second.type != PORT_IN || !port.second.net)
+ continue;
+ DelayInfo comb_delay;
+ bool is_path =
+ ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay);
+ if (!is_path)
+ continue;
+ // If input port is influenced by a clock, skip
+ int port_clocks;
+ TimingPortClass portClass =
+ ctx->getPortTimingClass(crit_net->driver.cell, port.first, port_clocks);
+ if (portClass == TMG_REGISTER_INPUT || portClass == TMG_CLOCK_INPUT ||
+ portClass == TMG_ENDPOINT || portClass == TMG_IGNORE)
+ continue;
- // And find the fanin net with the latest arrival time
- const auto net_arrival = net_data.at(port.second.net).max_arrival;
- if (net_arrival > max_arrival) {
- max_arrival = net_arrival;
- crit_ipin = &port.second;
+ // And find the fanin net with the latest arrival time
+ if (net_data.count(port.second.net) &&
+ net_data.at(port.second.net).count(crit_pair.first.start)) {
+ const auto net_arrival = net_data.at(port.second.net).at(crit_pair.first.start).max_arrival;
+ if (net_arrival > max_arrival) {
+ max_arrival = net_arrival;
+ crit_ipin = &port.second;
+ }
+ }
}
- }
-
- if (!crit_ipin)
- break;
- // Now convert PortInfo* into a PortRef*
- for (auto &usr : crit_ipin->net->users) {
- if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) {
- crit_path->push_back(&usr);
+ if (!crit_ipin)
break;
+
+ // Now convert PortInfo* into a PortRef*
+ for (auto &usr : crit_ipin->net->users) {
+ if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) {
+ cp_ports.push_back(&usr);
+ break;
+ }
}
+ crit_net = crit_ipin->net;
}
- crit_net = crit_ipin->net;
+ std::reverse(cp_ports.begin(), cp_ports.end());
}
- std::reverse(crit_path->begin(), crit_path->end());
}
return min_slack;
}
@@ -362,30 +511,106 @@ void assign_budget(Context *ctx, bool quiet)
log_info("Checksum: 0x%08x\n", ctx->checksum());
}
-void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
+void timing_analysis(Context *ctx, bool print_histogram, bool print_fmax, bool print_path)
{
- PortRefVector crit_path;
+ auto format_event = [ctx](const ClockEvent &e, int field_width = 0) {
+ std::string value;
+ if (e.clock == ctx->id("$async$"))
+ value = std::string("<async>");
+ else
+ value = (e.edge == FALLING_EDGE ? std::string("negedge ") : std::string("posedge ")) + e.clock.str(ctx);
+ if (int(value.length()) < field_width)
+ value.insert(value.length(), field_width - int(value.length()), ' ');
+ return value;
+ };
+
+ CriticalPathMap crit_paths;
DelayFrequency slack_histogram;
- Timing timing(ctx, true /* net_delays */, false /* update */, print_path ? &crit_path : nullptr,
+ Timing timing(ctx, true /* net_delays */, false /* update */, (print_path || print_fmax) ? &crit_paths : nullptr,
print_histogram ? &slack_histogram : nullptr);
- auto min_slack = timing.walk_paths();
+ timing.walk_paths();
+ std::map<IdString, std::pair<ClockPair, CriticalPath>> clock_reports;
+ std::map<IdString, double> clock_fmax;
+ std::vector<ClockPair> xclock_paths;
+ std::set<IdString> empty_clocks; // set of clocks with no interior paths
+ if (print_path || print_fmax) {
+ for (auto path : crit_paths) {
+ const ClockEvent &a = path.first.start;
+ const ClockEvent &b = path.first.end;
+ empty_clocks.insert(a.clock);
+ empty_clocks.insert(b.clock);
+ }
+ for (auto path : crit_paths) {
+ const ClockEvent &a = path.first.start;
+ const ClockEvent &b = path.first.end;
+ if (a.clock != b.clock || a.clock == ctx->id("$async$"))
+ continue;
+ double Fmax;
+ empty_clocks.erase(a.clock);
+ if (a.edge == b.edge)
+ Fmax = 1000 / ctx->getDelayNS(path.second.path_delay);
+ else
+ Fmax = 500 / ctx->getDelayNS(path.second.path_delay);
+ if (!clock_fmax.count(a.clock) || Fmax < clock_fmax.at(a.clock)) {
+ clock_reports[a.clock] = path;
+ clock_fmax[a.clock] = Fmax;
+ }
+ }
+
+ for (auto &path : crit_paths) {
+ const ClockEvent &a = path.first.start;
+ const ClockEvent &b = path.first.end;
+ if (a.clock == b.clock && a.clock != ctx->id("$async$"))
+ continue;
+ xclock_paths.push_back(path.first);
+ }
+
+ if (clock_reports.empty()) {
+ log_warning("No clocks found in design");
+ }
+
+ std::sort(xclock_paths.begin(), xclock_paths.end(), [ctx](const ClockPair &a, const ClockPair &b) {
+ if (a.start.clock.str(ctx) < b.start.clock.str(ctx))
+ return true;
+ if (a.start.clock.str(ctx) > b.start.clock.str(ctx))
+ return false;
+ if (a.start.edge < b.start.edge)
+ return true;
+ if (a.start.edge > b.start.edge)
+ return false;
+ if (a.end.clock.str(ctx) < b.end.clock.str(ctx))
+ return true;
+ if (a.end.clock.str(ctx) > b.end.clock.str(ctx))
+ return false;
+ if (a.end.edge < b.end.edge)
+ return true;
+ return false;
+ });
+ }
if (print_path) {
- if (crit_path.empty()) {
- log_info("Design contains no timing paths\n");
- } else {
+ auto print_path_report = [ctx](ClockPair &clocks, PortRefVector &crit_path) {
delay_t total = 0;
- log_break();
- log_info("Critical path report:\n");
- log_info("curr total\n");
-
auto &front = crit_path.front();
auto &front_port = front->cell->ports.at(front->port);
auto &front_driver = front_port.net->driver;
- IdString last_port;
- ctx->getPortTimingClass(front_driver.cell, front_driver.port, last_port);
+ int port_clocks;
+ auto portClass = ctx->getPortTimingClass(front_driver.cell, front_driver.port, port_clocks);
+ IdString last_port = front_driver.port;
+ if (portClass == TMG_REGISTER_OUTPUT) {
+ for (int i = 0; i < port_clocks; i++) {
+ TimingClockingInfo clockInfo = ctx->getPortClockingInfo(front_driver.cell, front_driver.port, i);
+ const NetInfo *clknet = get_net_or_empty(front_driver.cell, clockInfo.clock_port);
+ if (clknet != nullptr && clknet->name == clocks.start.clock &&
+ clockInfo.edge == clocks.start.edge) {
+ last_port = clockInfo.clock_port;
+ }
+ }
+ }
+
+ log_info("curr total\n");
for (auto sink : crit_path) {
auto sink_cell = sink->cell;
auto &port = sink_cell->ports.at(sink->port);
@@ -393,7 +618,12 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
auto &driver = net->driver;
auto driver_cell = driver.cell;
DelayInfo comb_delay;
- ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay);
+ if (last_port == driver.port) {
+ // Case where we start with a STARTPOINT etc
+ comb_delay = ctx->getDelayFromNS(0);
+ } else {
+ ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay);
+ }
total += comb_delay.maxDelay();
log_info("%4.1f %4.1f Source %s.%s\n", ctx->getDelayNS(comb_delay.maxDelay()), ctx->getDelayNS(total),
driver_cell->name.c_str(ctx), driver.port.c_str(ctx));
@@ -404,15 +634,83 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
log_info("%4.1f %4.1f Net %s budget %f ns (%d,%d) -> (%d,%d)\n", ctx->getDelayNS(net_delay),
ctx->getDelayNS(total), net->name.c_str(ctx), ctx->getDelayNS(sink->budget), driver_loc.x,
driver_loc.y, sink_loc.x, sink_loc.y);
- log_info(" Sink %s.%s\n", sink_cell->name.c_str(ctx), sink->port.c_str(ctx));
+ log_info(" Sink %s.%s\n", sink_cell->name.c_str(ctx), sink->port.c_str(ctx));
+ if (ctx->verbose) {
+ auto driver_wire = ctx->getNetinfoSourceWire(net);
+ auto sink_wire = ctx->getNetinfoSinkWire(net, *sink);
+ log_info(" prediction: %f ns estimate: %f ns\n",
+ ctx->getDelayNS(ctx->predictDelay(net, *sink)), ctx->getDelayNS(ctx->estimateDelay(driver_wire, sink_wire)));
+ auto cursor = sink_wire;
+ delay_t delay;
+ while (driver_wire != cursor) {
+ auto it = net->wires.find(cursor);
+ assert(it != net->wires.end());
+ auto pip = it->second.pip;
+ NPNR_ASSERT(pip != PipId());
+ delay = ctx->getPipDelay(pip).maxDelay();
+ log_info(" %1.3f %s\n", ctx->getDelayNS(delay), ctx->getPipName(pip).c_str(ctx));
+ cursor = ctx->getPipSrcWire(pip);
+ }
+ }
last_port = sink->port;
}
+ };
+
+ for (auto &clock : clock_reports) {
log_break();
+ std::string start = clock.second.first.start.edge == FALLING_EDGE ? std::string("negedge") : std::string("posedge");
+ std::string end = clock.second.first.end.edge == FALLING_EDGE ? std::string("negedge") : std::string("posedge");
+ log_info("Critical path report for clock '%s' (%s -> %s):\n", clock.first.c_str(ctx), start.c_str(), end.c_str());
+ auto &crit_path = clock.second.second.ports;
+ print_path_report(clock.second.first, crit_path);
+ }
+
+ for (auto &xclock : xclock_paths) {
+ log_break();
+ std::string start = format_event(xclock.start);
+ std::string end = format_event(xclock.end);
+ log_info("Critical path report for cross-domain path '%s' -> '%s':\n", start.c_str(), end.c_str());
+ auto &crit_path = crit_paths.at(xclock).ports;
+ print_path_report(xclock, crit_path);
}
}
+ if (print_fmax) {
+ log_break();
+ unsigned max_width = 0;
+ for (auto &clock : clock_reports)
+ max_width = std::max<unsigned>(max_width, clock.first.str(ctx).size());
+ for (auto &clock : clock_reports) {
+ const auto &clock_name = clock.first.str(ctx);
+ const int width = max_width - clock_name.size();
+ if (ctx->nets.at(clock.first)->clkconstr) {
+ float target = 1000 / ctx->getDelayNS(ctx->nets.at(clock.first)->clkconstr->period.minDelay());
+ log_info("Max frequency for clock %*s'%s': %.02f MHz (%s at %.02f MHz)\n", width, "", clock_name.c_str(),
+ clock_fmax[clock.first], (target < clock_fmax[clock.first]) ? "PASS" : "FAIL", target);
+ } else {
+ log_info("Max frequency for clock %*s'%s': %.02f MHz\n", width, "", clock_name.c_str(), clock_fmax[clock.first]);
+ }
+ }
+ for (auto &eclock : empty_clocks) {
+ if (eclock != ctx->id("$async$"))
+ log_info("Clock '%s' has no interior paths\n", eclock.c_str(ctx));
+ }
+ log_break();
+
+ int start_field_width = 0, end_field_width = 0;
+ for (auto &xclock : xclock_paths) {
+ start_field_width = std::max((int)format_event(xclock.start).length(), start_field_width);
+ end_field_width = std::max((int)format_event(xclock.end).length(), end_field_width);
+ }
- delay_t default_slack = delay_t((1.0e9 / ctx->getDelayNS(1)) / ctx->target_freq);
- log_info("estimated Fmax = %.2f MHz\n", 1e3 / ctx->getDelayNS(default_slack - min_slack));
+ for (auto &xclock : xclock_paths) {
+ const ClockEvent &a = xclock.start;
+ const ClockEvent &b = xclock.end;
+ auto &path = crit_paths.at(xclock);
+ auto ev_a = format_event(a, start_field_width), ev_b = format_event(b, end_field_width);
+ log_info("Max delay %s -> %s: %0.02f ns\n", ev_a.c_str(), ev_b.c_str(), ctx->getDelayNS(path.path_delay));
+ }
+ log_break();
+ }
if (print_histogram && slack_histogram.size() > 0) {
unsigned num_bins = 20;
diff --git a/common/timing.h b/common/timing.h
index cfb71ae0..1fd76310 100644
--- a/common/timing.h
+++ b/common/timing.h
@@ -29,7 +29,7 @@ void assign_budget(Context *ctx, bool quiet = false);
// Perform timing analysis and print out the fmax, and optionally the
// critical path
-void timing_analysis(Context *ctx, bool slack_histogram = true, bool print_path = false);
+void timing_analysis(Context *ctx, bool slack_histogram = true, bool print_fmax = true, bool print_path = false);
NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-02 09:08:27 +0000