aboutsummaryrefslogtreecommitdiffstats
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/context.cc14
-rw-r--r--common/design_utils.h14
-rw-r--r--common/indexed_store.h47
-rw-r--r--common/nextpnr_types.cc25
-rw-r--r--common/nextpnr_types.h3
-rw-r--r--common/placer1.cc68
-rw-r--r--common/placer_heap.cc14
-rw-r--r--common/pybindings.cc4
-rw-r--r--common/pycontainers.h57
-rw-r--r--common/router1.cc62
-rw-r--r--common/router2.cc139
-rw-r--r--common/timing.cc10
-rw-r--r--common/timing.h23
-rw-r--r--common/timing_opt.cc65
14 files changed, 285 insertions, 260 deletions
diff --git a/common/context.cc b/common/context.cc
index faddf825..e35d3e49 100644
--- a/common/context.cc
+++ b/common/context.cc
@@ -334,13 +334,13 @@ void Context::check() const
nameOf(port.first), nameOf(net));
}
} else if (port.second.type == PORT_IN) {
- int usr_count = std::count_if(net->users.begin(), net->users.end(), [&](const PortRef &pr) {
- return pr.cell == c.second.get() && pr.port == port.first;
- });
- if (usr_count != 1)
- CHECK_FAIL("input cell port '%s.%s' appears %d rather than expected 1 times in users vector of "
- "net '%s'\n",
- nameOf(c.first), nameOf(port.first), usr_count, nameOf(net));
+ if (!port.second.user_idx)
+ CHECK_FAIL("input cell port '%s.%s' on net '%s' has no user index\n", nameOf(c.first),
+ nameOf(port.first), nameOf(net));
+ auto net_user = net->users.at(port.second.user_idx);
+ if (net_user.cell != c.second.get() || net_user.port != port.first)
+ CHECK_FAIL("input cell port '%s.%s' not in associated user entry of net '%s'\n",
+ nameOf(c.first), nameOf(port.first), nameOf(net));
}
}
}
diff --git a/common/design_utils.h b/common/design_utils.h
index 63cb71d7..069600b5 100644
--- a/common/design_utils.h
+++ b/common/design_utils.h
@@ -47,14 +47,18 @@ CellInfo *net_only_drives(const Context *ctx, NetInfo *net, F1 cell_pred, IdStri
return nullptr;
if (exclusive) {
if (exclude == nullptr) {
- if (net->users.size() != 1)
+ if (net->users.entries() != 1)
return nullptr;
} else {
- if (net->users.size() > 2) {
+ if (net->users.entries() > 2) {
return nullptr;
- } else if (net->users.size() == 2) {
- if (std::find_if(net->users.begin(), net->users.end(),
- [exclude](const PortRef &ref) { return ref.cell == exclude; }) == net->users.end())
+ } else if (net->users.entries() == 2) {
+ bool found = false;
+ for (auto &usr : net->users) {
+ if (usr.cell == exclude)
+ found = true;
+ }
+ if (!found)
return nullptr;
}
}
diff --git a/common/indexed_store.h b/common/indexed_store.h
index 5579b039..df607c13 100644
--- a/common/indexed_store.h
+++ b/common/indexed_store.h
@@ -22,6 +22,7 @@
#include <algorithm>
#include <limits>
+#include <type_traits>
#include <vector>
#include "nextpnr_assertions.h"
@@ -43,6 +44,7 @@ template <typename T> struct store_index
unsigned int hash() const { return m_index; }
operator bool() const { return !empty(); }
+ operator int() const = delete;
bool operator!() const { return empty(); }
};
@@ -62,13 +64,19 @@ template <typename T> class indexed_store
friend class indexed_store<T>;
public:
- slot() : active(false), next_free(std::numeric_limits<int32_t>::max()){};
- slot(slot &&other) : active(other.active), next_free(other.next_free)
+ slot() : next_free(std::numeric_limits<int32_t>::max()), active(false){};
+ slot(slot &&other) : next_free(other.next_free), active(other.active)
{
if (active)
::new (static_cast<void *>(&storage)) T(std::move(other.obj()));
};
+ slot(const slot &other) : next_free(other.next_free), active(other.active)
+ {
+ if (active)
+ ::new (static_cast<void *>(&storage)) T(other.obj());
+ };
+
template <class... Args> void create(Args &&...args)
{
NPNR_ASSERT(!active);
@@ -131,8 +139,16 @@ template <typename T> class indexed_store
first_free = idx.m_index;
}
+ void clear()
+ {
+ active_count = 0;
+ first_free = 0;
+ slots.clear();
+ }
+
// Number of live entries
int32_t entries() const { return active_count; }
+ bool empty() const { return (entries() == 0); }
// Reserve a certain amount of space
void reserve(int32_t size) { slots.reserve(size); }
@@ -155,6 +171,8 @@ template <typename T> class indexed_store
int32_t capacity() const { return int32_t(slots.size()); }
// Iterate over items
+ template <typename It, typename S> class enumerated_iterator;
+
class iterator
{
private:
@@ -182,9 +200,14 @@ template <typename T> class indexed_store
return prior;
}
T &operator*() { return base->at(store_index<T>(index)); }
- template <typename It, typename S> friend class enumerated_iterator;
+ template <typename It, typename S> friend class indexed_store::enumerated_iterator;
};
- iterator begin() { return iterator{this, 0}; }
+ iterator begin()
+ {
+ auto it = iterator{this, -1};
+ ++it;
+ return it;
+ }
iterator end() { return iterator{this, int32_t(slots.size())}; }
class const_iterator
@@ -214,15 +237,20 @@ template <typename T> class indexed_store
return prior;
}
const T &operator*() { return base->at(store_index<T>(index)); }
- template <typename It, typename S> friend class enumerated_iterator;
+ template <typename It, typename S> friend class indexed_store::enumerated_iterator;
};
- const_iterator begin() const { return const_iterator{this, 0}; }
+ const_iterator begin() const
+ {
+ auto it = const_iterator{this, -1};
+ ++it;
+ return it;
+ }
const_iterator end() const { return const_iterator{this, int32_t(slots.size())}; }
template <typename S> struct enumerated_item
{
enumerated_item(int32_t index, T &value) : index(index), value(value){};
- store_index<std::remove_const<S>> index;
+ store_index<std::remove_cv_t<S>> index;
S &value;
};
@@ -258,7 +286,10 @@ template <typename T> class indexed_store
};
enumerated_range<iterator, T> enumerate() { return enumerated_range<iterator, T>{begin(), end()}; }
- enumerated_range<const_iterator, const T> enumerate() const { return enumerated_range<iterator, T>{begin(), end()}; }
+ enumerated_range<const_iterator, const T> enumerate() const
+ {
+ return enumerated_range<iterator, T>{begin(), end()};
+ }
};
NEXTPNR_NAMESPACE_END
diff --git a/common/nextpnr_types.cc b/common/nextpnr_types.cc
index c89a0071..57d816c0 100644
--- a/common/nextpnr_types.cc
+++ b/common/nextpnr_types.cc
@@ -66,7 +66,7 @@ void CellInfo::connectPort(IdString port_name, NetInfo *net)
PortRef user;
user.cell = this;
user.port = port_name;
- net->users.push_back(user);
+ port.user_idx = net->users.add(user);
} else {
NPNR_ASSERT_FALSE("invalid port type for connect_port");
}
@@ -78,11 +78,8 @@ void CellInfo::disconnectPort(IdString port_name)
return;
PortInfo &port = ports.at(port_name);
if (port.net != nullptr) {
- port.net->users.erase(std::remove_if(port.net->users.begin(), port.net->users.end(),
- [this, port_name](const PortRef &user) {
- return user.cell == this && user.port == port_name;
- }),
- port.net->users.end());
+ if (port.user_idx)
+ port.net->users.remove(port.user_idx);
if (port.net->driver.cell == this && port.net->driver.port == port_name)
port.net->driver.cell = nullptr;
port.net = nullptr;
@@ -116,7 +113,9 @@ void CellInfo::movePortTo(IdString port, CellInfo *other, IdString other_port)
NPNR_ASSERT(old.type == rep.type);
rep.net = old.net;
+ rep.user_idx = old.user_idx;
old.net = nullptr;
+ old.user_idx = store_index<PortRef>{};
if (rep.type == PORT_OUT) {
if (rep.net != nullptr) {
rep.net->driver.cell = other;
@@ -124,12 +123,9 @@ void CellInfo::movePortTo(IdString port, CellInfo *other, IdString other_port)
}
} else if (rep.type == PORT_IN) {
if (rep.net != nullptr) {
- for (PortRef &load : rep.net->users) {
- if (load.cell == this && load.port == port) {
- load.cell = other;
- load.port = other_port;
- }
- }
+ auto &load = rep.net->users.at(rep.user_idx);
+ load.cell = other;
+ load.port = other_port;
}
} else {
NPNR_ASSERT(false);
@@ -144,9 +140,8 @@ void CellInfo::renamePort(IdString old_name, IdString new_name)
if (pi.net != nullptr) {
if (pi.net->driver.cell == this && pi.net->driver.port == old_name)
pi.net->driver.port = new_name;
- for (auto &usr : pi.net->users)
- if (usr.cell == this && usr.port == old_name)
- usr.port = new_name;
+ if (pi.user_idx)
+ pi.net->users.at(pi.user_idx).port = new_name;
}
ports.erase(old_name);
pi.name = new_name;
diff --git a/common/nextpnr_types.h b/common/nextpnr_types.h
index 4e5432ce..c21182cc 100644
--- a/common/nextpnr_types.h
+++ b/common/nextpnr_types.h
@@ -130,7 +130,7 @@ struct NetInfo : ArchNetInfo
int32_t udata = 0;
PortRef driver;
- std::vector<PortRef> users;
+ indexed_store<PortRef> users;
dict<IdString, Property> attrs;
// wire -> uphill_pip
@@ -155,6 +155,7 @@ struct PortInfo
IdString name;
NetInfo *net;
PortType type;
+ store_index<PortRef> user_idx{};
};
struct Context;
diff --git a/common/placer1.cc b/common/placer1.cc
index 6de035b4..a6ba3895 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -91,7 +91,7 @@ class SAPlacer
decltype(NetInfo::udata) n = 0;
for (auto &net : ctx->nets) {
old_udata.emplace_back(net.second->udata);
- net_arc_tcost.at(n).resize(net.second->users.size());
+ net_arc_tcost.at(n).resize(net.second->users.capacity());
net.second->udata = n++;
net_by_udata.push_back(net.second.get());
}
@@ -118,7 +118,6 @@ class SAPlacer
}
region_bounds[r->name] = bb;
}
- build_port_index();
for (auto &cell : ctx->cells) {
CellInfo *ci = cell.second.get();
if (ci->cluster == ClusterId())
@@ -858,7 +857,7 @@ class SAPlacer
}
// Get the timing cost for an arc of a net
- inline double get_timing_cost(NetInfo *net, size_t user)
+ inline double get_timing_cost(NetInfo *net, const PortRef &user)
{
int cc;
if (net->driver.cell == nullptr)
@@ -866,11 +865,11 @@ class SAPlacer
if (ctx->getPortTimingClass(net->driver.cell, net->driver.port, cc) == TMG_IGNORE)
return 0;
if (cfg.budgetBased) {
- double delay = ctx->getDelayNS(ctx->predictArcDelay(net, net->users.at(user)));
- return std::min(10.0, std::exp(delay - ctx->getDelayNS(net->users.at(user).budget) / 10));
+ double delay = ctx->getDelayNS(ctx->predictArcDelay(net, user));
+ return std::min(10.0, std::exp(delay - ctx->getDelayNS(user.budget) / 10));
} else {
- float crit = tmg.get_criticality(CellPortKey(net->users.at(user)));
- double delay = ctx->getDelayNS(ctx->predictArcDelay(net, net->users.at(user)));
+ float crit = tmg.get_criticality(CellPortKey(user));
+ double delay = ctx->getDelayNS(ctx->predictArcDelay(net, user));
return delay * std::pow(crit, crit_exp);
}
}
@@ -883,9 +882,9 @@ class SAPlacer
if (ignore_net(ni))
continue;
net_bounds[ni->udata] = get_net_bounds(ni);
- if (cfg.timing_driven && int(ni->users.size()) < cfg.timingFanoutThresh)
- for (size_t i = 0; i < ni->users.size(); i++)
- net_arc_tcost[ni->udata][i] = get_timing_cost(ni, i);
+ if (cfg.timing_driven && int(ni->users.entries()) < cfg.timingFanoutThresh)
+ for (auto usr : ni->users.enumerate())
+ net_arc_tcost[ni->udata][usr.index.idx()] = get_timing_cost(ni, usr.value);
}
}
@@ -923,13 +922,13 @@ class SAPlacer
};
std::vector<decltype(NetInfo::udata)> bounds_changed_nets_x, bounds_changed_nets_y;
- std::vector<std::pair<decltype(NetInfo::udata), size_t>> changed_arcs;
+ std::vector<std::pair<decltype(NetInfo::udata), store_index<PortRef>>> changed_arcs;
std::vector<BoundChangeType> already_bounds_changed_x, already_bounds_changed_y;
std::vector<std::vector<bool>> already_changed_arcs;
std::vector<BoundingBox> new_net_bounds;
- std::vector<std::pair<std::pair<decltype(NetInfo::udata), size_t>, double>> new_arc_costs;
+ std::vector<std::pair<std::pair<decltype(NetInfo::udata), store_index<PortRef>>, double>> new_arc_costs;
wirelen_t wirelen_delta = 0;
double timing_delta = 0;
@@ -940,7 +939,7 @@ class SAPlacer
already_bounds_changed_y.resize(p->ctx->nets.size());
already_changed_arcs.resize(p->ctx->nets.size());
for (auto &net : p->ctx->nets) {
- already_changed_arcs.at(net.second->udata).resize(net.second->users.size());
+ already_changed_arcs.at(net.second->udata).resize(net.second->users.capacity());
}
new_net_bounds = p->net_bounds;
}
@@ -956,7 +955,7 @@ class SAPlacer
already_bounds_changed_y[bc] = NO_CHANGE;
}
for (const auto &tc : changed_arcs)
- already_changed_arcs[tc.first][tc.second] = false;
+ already_changed_arcs[tc.first][tc.second.idx()] = false;
bounds_changed_nets_x.clear();
bounds_changed_nets_y.clear();
changed_arcs.clear();
@@ -1100,22 +1099,22 @@ class SAPlacer
}
}
- if (cfg.timing_driven && int(pn->users.size()) < cfg.timingFanoutThresh) {
+ if (cfg.timing_driven && int(pn->users.entries()) < cfg.timingFanoutThresh) {
// Output ports - all arcs change timing
if (port.second.type == PORT_OUT) {
int cc;
TimingPortClass cls = ctx->getPortTimingClass(cell, port.first, cc);
if (cls != TMG_IGNORE)
- for (size_t i = 0; i < pn->users.size(); i++)
- if (!mc.already_changed_arcs[pn->udata][i]) {
- mc.changed_arcs.emplace_back(std::make_pair(pn->udata, i));
- mc.already_changed_arcs[pn->udata][i] = true;
+ for (auto usr : pn->users.enumerate())
+ if (!mc.already_changed_arcs[pn->udata][usr.index.idx()]) {
+ mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr.index));
+ mc.already_changed_arcs[pn->udata][usr.index.idx()] = true;
}
} else if (port.second.type == PORT_IN) {
- auto usr = fast_port_to_user.at(std::make_pair(cell->name, port.first));
- if (!mc.already_changed_arcs[pn->udata][usr]) {
- mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr));
- mc.already_changed_arcs[pn->udata][usr] = true;
+ auto usr_idx = port.second.user_idx;
+ if (!mc.already_changed_arcs[pn->udata][usr_idx.idx()]) {
+ mc.changed_arcs.emplace_back(std::make_pair(pn->udata, usr_idx));
+ mc.already_changed_arcs[pn->udata][usr_idx.idx()] = true;
}
}
}
@@ -1142,11 +1141,12 @@ class SAPlacer
if (cfg.timing_driven) {
for (const auto &tc : md.changed_arcs) {
- double old_cost = net_arc_tcost.at(tc.first).at(tc.second);
- double new_cost = get_timing_cost(net_by_udata.at(tc.first), tc.second);
+ double old_cost = net_arc_tcost.at(tc.first).at(tc.second.idx());
+ double new_cost =
+ get_timing_cost(net_by_udata.at(tc.first), net_by_udata.at(tc.first)->users.at(tc.second));
md.new_arc_costs.emplace_back(std::make_pair(tc, new_cost));
md.timing_delta += (new_cost - old_cost);
- md.already_changed_arcs[tc.first][tc.second] = false;
+ md.already_changed_arcs[tc.first][tc.second.idx()] = false;
}
}
}
@@ -1158,21 +1158,10 @@ class SAPlacer
for (const auto &bc : md.bounds_changed_nets_y)
net_bounds[bc] = md.new_net_bounds[bc];
for (const auto &tc : md.new_arc_costs)
- net_arc_tcost[tc.first.first].at(tc.first.second) = tc.second;
+ net_arc_tcost[tc.first.first].at(tc.first.second.idx()) = tc.second;
curr_wirelen_cost += md.wirelen_delta;
curr_timing_cost += md.timing_delta;
}
- // Build the cell port -> user index
- void build_port_index()
- {
- for (auto &net : ctx->nets) {
- NetInfo *ni = net.second.get();
- for (size_t i = 0; i < ni->users.size(); i++) {
- auto &usr = ni->users.at(i);
- fast_port_to_user[std::make_pair(usr.cell->name, usr.port)] = i;
- }
- }
- }
// Simple routeability driven placement
const int large_cell_thresh = 50;
@@ -1240,9 +1229,6 @@ class SAPlacer
// Map net arcs to their timing cost (criticality * delay ns)
std::vector<std::vector<double>> net_arc_tcost;
- // Fast lookup for cell port to net user index
- dict<std::pair<IdString, IdString>, size_t> fast_port_to_user;
-
// Fast lookup for cell to clusters
dict<ClusterId, std::vector<CellInfo *>> cluster2cell;
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index f8385cef..5b43dc72 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -655,9 +655,9 @@ class HeAPPlacer
template <typename Tf> void foreach_port(NetInfo *net, Tf func)
{
if (net->driver.cell != nullptr)
- func(net->driver, -1);
- for (size_t i = 0; i < net->users.size(); i++)
- func(net->users.at(i), i);
+ func(net->driver, store_index<PortRef>());
+ for (auto usr : net->users.enumerate())
+ func(usr.value, usr.index);
}
// Build the system of equations for either X or Y
@@ -682,7 +682,7 @@ class HeAPPlacer
// Find the bounds of the net in this axis, and the ports that correspond to these bounds
PortRef *lbport = nullptr, *ubport = nullptr;
int lbpos = std::numeric_limits<int>::max(), ubpos = std::numeric_limits<int>::min();
- foreach_port(ni, [&](PortRef &port, int user_idx) {
+ foreach_port(ni, [&](PortRef &port, store_index<PortRef> user_idx) {
int pos = cell_pos(port.cell);
if (pos < lbpos) {
lbpos = pos;
@@ -713,17 +713,17 @@ class HeAPPlacer
};
// Add all relevant connections to the matrix
- foreach_port(ni, [&](PortRef &port, int user_idx) {
+ foreach_port(ni, [&](PortRef &port, store_index<PortRef> user_idx) {
int this_pos = cell_pos(port.cell);
auto process_arc = [&](PortRef *other) {
if (other == &port)
return;
int o_pos = cell_pos(other->cell);
- double weight = 1.0 / (ni->users.size() *
+ double weight = 1.0 / (ni->users.entries() *
std::max<double>(1, (yaxis ? cfg.hpwl_scale_y : cfg.hpwl_scale_x) *
std::abs(o_pos - this_pos)));
- if (user_idx != -1) {
+ if (user_idx) {
weight *= (1.0 + cfg.timingWeight * std::pow(tmg.get_criticality(CellPortKey(port)),
cfg.criticalityExponent));
}
diff --git a/common/pybindings.cc b/common/pybindings.cc
index eef460ce..9a783eb4 100644
--- a/common/pybindings.cc
+++ b/common/pybindings.cc
@@ -220,7 +220,7 @@ PYBIND11_EMBEDDED_MODULE(MODULE_NAME, m)
readwrite_wrapper<PortInfo &, decltype(&PortInfo::type), &PortInfo::type, pass_through<PortType>,
pass_through<PortType>>::def_wrap(pi_cls, "type");
- typedef std::vector<PortRef> PortRefVector;
+ typedef indexed_store<PortRef> PortRefVector;
typedef dict<WireId, PipMap> WireMap;
typedef pool<BelId> BelSet;
typedef pool<WireId> WireSet;
@@ -288,7 +288,7 @@ PYBIND11_EMBEDDED_MODULE(MODULE_NAME, m)
WRAP_MAP(m, WireMap, wrap_context<PipMap &>, "WireMap");
WRAP_MAP_UPTR(m, RegionMap, "RegionMap");
- WRAP_VECTOR(m, PortRefVector, wrap_context<PortRef>);
+ WRAP_INDEXSTORE(m, PortRefVector, wrap_context<PortRef>);
typedef dict<IdString, ClockFmax> ClockFmaxMap;
WRAP_MAP(m, ClockFmaxMap, pass_through<ClockFmax>, "ClockFmaxMap");
diff --git a/common/pycontainers.h b/common/pycontainers.h
index a93230ab..ff49c34c 100644
--- a/common/pycontainers.h
+++ b/common/pycontainers.h
@@ -186,6 +186,63 @@ struct vector_wrapper
#define WRAP_VECTOR(m, t, conv) vector_wrapper<t, py::return_value_policy::copy, conv>().wrap(m, #t, #t "Iterator")
+template <typename T, py::return_value_policy P = py::return_value_policy::copy,
+ typename value_conv = PythonConversion::pass_through<T>>
+struct indexed_store_wrapper
+{
+ typedef decltype(std::declval<T>().begin()) iterator_t;
+ typedef decltype(*(std::declval<iterator_t>())) value_t;
+ typedef typename PythonConversion::ContextualWrapper<T &> wrapped_vector;
+ typedef typename PythonConversion::ContextualWrapper<std::pair<iterator_t, iterator_t>> wrapped_pair;
+ using return_t = typename value_conv::ret_type;
+ static wrapped_pair iter(wrapped_vector &range)
+ {
+ return wrapped_pair(range.ctx, std::make_pair(range.base.begin(), range.base.end()));
+ }
+
+ static std::string repr(wrapped_vector &range)
+ {
+ PythonConversion::string_converter<value_t> conv;
+ bool first = true;
+ std::stringstream ss;
+ ss << "[";
+ for (const auto &item : range.base) {
+ if (!first)
+ ss << ", ";
+ ss << "'" << conv.to_str(range.ctx, item) << "'";
+ first = false;
+ }
+ ss << "]";
+ return ss.str();
+ }
+
+ static int len(wrapped_vector &range) { return range.base.capacity(); }
+
+ static py::object getitem(wrapped_vector &range, int i)
+ {
+ store_index<std::remove_reference_t<value_t>> idx(i);
+ if (!range.base.count(idx))
+ throw py::none();
+ return py::cast(value_conv()(range.ctx, boost::ref(range.base.at(idx))));
+ }
+
+ static void wrap(py::module &m, const char *range_name, const char *iter_name)
+ {
+ py::class_<wrapped_vector>(m, range_name)
+ .def("__iter__", iter)
+ .def("__repr__", repr)
+ .def("__len__", len)
+ .def("__getitem__", getitem);
+
+ iterator_wrapper<iterator_t, P, value_conv>().wrap(m, iter_name);
+ }
+
+ typedef iterator_wrapper<iterator_t, P, value_conv> iter_wrap;
+};
+
+#define WRAP_INDEXSTORE(m, t, conv) \
+ indexed_store_wrapper<t, py::return_value_policy::copy, conv>().wrap(m, #t, #t "Iterator")
+
/*
Wrapper for a pair, allows accessing either using C++-style members (.first and
.second) or as a Python iterable and indexable object
diff --git a/common/router1.cc b/common/router1.cc
index f387aee1..98132116 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -34,7 +34,7 @@ struct arc_key
{
NetInfo *net_info;
// logical user cell port index
- int user_idx;
+ store_index<PortRef> user_idx;
// physical index into cell->bel pin mapping (usually 0)
unsigned phys_idx;
@@ -52,7 +52,7 @@ struct arc_key
unsigned int hash() const
{
std::size_t seed = std::hash<NetInfo *>()(net_info);
- seed ^= std::hash<int>()(user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
+ seed ^= user_idx.hash() + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= std::hash<int>()(phys_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
@@ -157,7 +157,7 @@ struct Router1
return;
NetInfo *net_info = arc.net_info;
- int user_idx = arc.user_idx;
+ auto user_idx = arc.user_idx;
unsigned phys_idx = arc.phys_idx;
auto src_wire = ctx->getNetinfoSourceWire(net_info);
@@ -318,14 +318,14 @@ struct Router1
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++) {
+ for (auto user : net_info->users.enumerate()) {
unsigned phys_idx = 0;
- for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, net_info->users[user_idx])) {
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
log_assert(dst_wire != WireId());
arc_key arc;
arc.net_info = net_info;
- arc.user_idx = user_idx;
+ arc.user_idx = user.index;
arc.phys_idx = phys_idx++;
valid_arcs.insert(arc);
#if 0
@@ -391,28 +391,29 @@ struct Router1
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);
+ ctx->nameOf(dst_to_arc.at(src_wire).net_info), dst_to_arc.at(src_wire).user_idx.idx());
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
+ for (auto user : net_info->users.enumerate()) {
unsigned phys_idx = 0;
- for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, net_info->users[user_idx])) {
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
arc_key arc;
arc.net_info = net_info;
- arc.user_idx = user_idx;
+ arc.user_idx = user.index;
arc.phys_idx = phys_idx++;
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->nameOfWire(dst_wire), ctx->nameOf(net_info), user.index.idx(),
+ ctx->nameOf(dst_to_arc.at(dst_wire).net_info),
+ dst_to_arc.at(dst_wire).user_idx.idx());
}
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);
+ ctx->nameOf(net_info), user.index.idx());
dst_to_arc[dst_wire] = arc;
@@ -441,9 +442,8 @@ struct Router1
// TODO: this matches the situation before supporting multiple cell->bel pins, but do we want to keep
// this invariant?
if (phys_idx == 0)
- log_warning("No wires 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));
+ log_warning("No wires found for port %s on destination cell %s.\n", ctx->nameOf(user.value.port),
+ ctx->nameOf(user.value.cell));
}
src_to_net[src_wire] = net_info;
@@ -463,7 +463,7 @@ struct Router1
{
NetInfo *net_info = arc.net_info;
- int user_idx = arc.user_idx;
+ auto user_idx = arc.user_idx;
auto src_wire = ctx->getNetinfoSourceWire(net_info);
auto dst_wire = ctx->getNetinfoSinkWire(net_info, net_info->users[user_idx], arc.phys_idx);
@@ -472,8 +472,8 @@ struct Router1
float crit = tmg.get_criticality(CellPortKey(net_info->users.at(user_idx)));
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("Routing arc %d on net %s (%d arcs total):\n", user_idx.idx(), ctx->nameOf(net_info),
+ int(net_info->users.capacity()));
log(" source ... %s\n", ctx->nameOfWire(src_wire));
log(" sink ..... %s\n", ctx->nameOfWire(dst_wire));
}
@@ -805,8 +805,7 @@ struct Router1
NetInfo *ni = net.second.get();
if (skip_net(ni))
continue;
- for (size_t i = 0; i < ni->users.size(); i++) {
- auto &usr = ni->users.at(i);
+ for (auto &usr : ni->users) {
++arc_count;
delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
if (slack == std::numeric_limits<delay_t>::min())
@@ -825,8 +824,7 @@ struct Router1
NetInfo *ni = net.second.get();
if (skip_net(ni))
continue;
- for (size_t i = 0; i < ni->users.size(); i++) {
- auto &usr = ni->users.at(i);
+ for (auto &usr : ni->users) {
delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
if (slack == std::numeric_limits<delay_t>::min())
continue;
@@ -912,7 +910,8 @@ bool router1(Context *ctx, const Router1Cfg &cfg)
arc_key arc = router.arc_queue_pop();
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));
+ log_warning("Failed to find a route for arc %d of net %s.\n", arc.user_idx.idx(),
+ ctx->nameOf(arc.net_info));
#ifndef NDEBUG
router.check();
ctx->check();
@@ -937,8 +936,7 @@ bool router1(Context *ctx, const Router1Cfg &cfg)
}
if (is_locked)
continue;
- for (size_t i = 0; i < ni->users.size(); i++) {
- auto &usr = ni->users.at(i);
+ for (auto &usr : ni->users) {
delay_t slack = router.tmg.get_setup_slack(CellPortKey(usr));
if (slack == std::numeric_limits<delay_t>::min())
continue;
@@ -1051,15 +1049,15 @@ bool Context::checkRoutedDesign() const
found_unrouted = true;
}
- dict<WireId, int> dest_wires;
- for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
- for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, net_info->users[user_idx])) {
+ dict<WireId, store_index<PortRef>> dest_wires;
+ for (auto user : net_info->users.enumerate()) {
+ for (auto dst_wire : ctx->getNetinfoSinkWires(net_info, user.value)) {
log_assert(dst_wire != WireId());
- dest_wires[dst_wire] = user_idx;
+ dest_wires[dst_wire] = user.index;
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));
+ log(" sink %d (%s) not bound to net\n", user.index.idx(), ctx->nameOfWire(dst_wire));
found_unrouted = true;
}
}
@@ -1086,7 +1084,7 @@ bool Context::checkRoutedDesign() const
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));
+ log(" %*s=> sink %d\n", 2 * num, "", dest_wires.at(w).idx());
} else {
if (ctx->debug)
log(" %*s=> stub\n", 2 * num, "");
diff --git a/common/router2.cc b/common/router2.cc
index c76e1f61..e943e493 100644
--- a/common/router2.cc
+++ b/common/router2.cc
@@ -117,7 +117,7 @@ struct Router2
NetInfo *ni = net.second.get();
ni->udata = i;
nets_by_udata.at(i) = ni;
- nets.at(i).arcs.resize(ni->users.size());
+ nets.at(i).arcs.resize(ni->users.capacity());
// Start net bounding box at overall min/max
nets.at(i).bb.x0 = std::numeric_limits<int>::max();
@@ -133,10 +133,9 @@ struct Router2
nets.at(i).cy += drv_loc.y;
}
- for (size_t j = 0; j < ni->users.size(); j++) {
- auto &usr = ni->users.at(j);
+ for (auto usr : ni->users.enumerate()) {
WireId src_wire = ctx->getNetinfoSourceWire(ni);
- for (auto &dst_wire : ctx->getNetinfoSinkWires(ni, usr)) {
+ for (auto &dst_wire : ctx->getNetinfoSinkWires(ni, usr.value)) {
nets.at(i).src_wire = src_wire;
if (ni->driver.cell == nullptr)
src_wire = dst_wire;
@@ -146,10 +145,10 @@ struct Router2
log_error("No wire found for port %s on source cell %s.\n", ctx->nameOf(ni->driver.port),
ctx->nameOf(ni->driver.cell));
if (dst_wire == WireId())
- log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.port),
- ctx->nameOf(usr.cell));
- nets.at(i).arcs.at(j).emplace_back();
- auto &ad = nets.at(i).arcs.at(j).back();
+ log_error("No wire found for port %s on destination cell %s.\n", ctx->nameOf(usr.value.port),
+ ctx->nameOf(usr.value.cell));
+ nets.at(i).arcs.at(usr.index.idx()).emplace_back();
+ auto &ad = nets.at(i).arcs.at(usr.index.idx()).back();
ad.sink_wire = dst_wire;
// Set bounding box for this arc
ad.bb = ctx->getRouteBoundingBox(src_wire, dst_wire);
@@ -160,14 +159,14 @@ struct Router2
nets.at(i).bb.y1 = std::max(nets.at(i).bb.y1, ad.bb.y1);
}
// Add location to centroid sum
- Loc usr_loc = ctx->getBelLocation(usr.cell->bel);
+ Loc usr_loc = ctx->getBelLocation(usr.value.cell->bel);
nets.at(i).cx += usr_loc.x;
nets.at(i).cy += usr_loc.y;
}
nets.at(i).hpwl = std::max(
std::abs(nets.at(i).bb.y1 - nets.at(i).bb.y0) + std::abs(nets.at(i).bb.x1 - nets.at(i).bb.x0), 1);
- nets.at(i).cx /= int(ni->users.size() + 1);
- nets.at(i).cy /= int(ni->users.size() + 1);
+ nets.at(i).cx /= int(ni->users.entries() + 1);
+ nets.at(i).cy /= int(ni->users.entries() + 1);
if (ctx->debug)
log_info("%s: bb=(%d, %d)->(%d, %d) c=(%d, %d) hpwl=%d\n", ctx->nameOf(ni), nets.at(i).bb.x0,
nets.at(i).bb.y0, nets.at(i).bb.x1, nets.at(i).bb.y1, nets.at(i).cx, nets.at(i).cy,
@@ -218,11 +217,11 @@ struct Router2
for (auto &net_pair : ctx->nets) {
auto *net = net_pair.second.get();
auto &nd = nets.at(net->udata);
- for (size_t usr = 0; usr < net->users.size(); usr++) {
- auto &ad = nd.arcs.at(usr);
+ for (auto usr : net->users.enumerate()) {
+ auto &ad = nd.arcs.at(usr.index.idx());
for (size_t phys_pin = 0; phys_pin < ad.size(); phys_pin++) {
- if (check_arc_routing(net, usr, phys_pin)) {
- record_prerouted_net(net, usr, phys_pin);
+ if (check_arc_routing(net, usr.index, phys_pin)) {
+ record_prerouted_net(net, usr.index, phys_pin);
}
}
}
@@ -261,7 +260,7 @@ struct Router2
// Nets that failed routing
std::vector<NetInfo *> failed_nets;
- std::vector<std::pair<size_t, size_t>> route_arcs;
+ std::vector<std::pair<store_index<PortRef>, size_t>> route_arcs;
std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> fwd_queue, bwd_queue;
// Special case where one net has multiple logical arcs to the same physical sink
@@ -305,7 +304,7 @@ struct Router2
log(__VA_ARGS__); \
} while (0)
- void bind_pip_internal(PerNetData &net, size_t user, int wire, PipId pip)
+ void bind_pip_internal(PerNetData &net, store_index<PortRef> user, int wire, PipId pip)
{
auto &wd = flat_wires.at(wire);
auto found = net.wires.find(wd.w);
@@ -323,7 +322,7 @@ struct Router2
}
}
- void unbind_pip_internal(PerNetData &net, size_t user, WireId wire)
+ void unbind_pip_internal(PerNetData &net, store_index<PortRef> user, WireId wire)
{
auto &wd = wire_data(wire);
auto &b = net.wires.at(wd.w);
@@ -335,10 +334,10 @@ struct Router2
}
}
- void ripup_arc(NetInfo *net, size_t user, size_t phys_pin)
+ void ripup_arc(NetInfo *net, store_index<PortRef> user, size_t phys_pin)
{
auto &nd = nets.at(net->udata);
- auto &ad = nd.arcs.at(user).at(phys_pin);
+ auto &ad = nd.arcs.at(user.idx()).at(phys_pin);
if (!ad.routed)
return;
WireId src = nets.at(net->udata).src_wire;
@@ -351,7 +350,8 @@ struct Router2
ad.routed = false;
}
- float score_wire_for_arc(NetInfo *net, size_t user, size_t phys_pin, WireId wire, PipId pip, float crit_weight)
+ float score_wire_for_arc(NetInfo *net, store_index<PortRef> user, size_t phys_pin, WireId wire, PipId pip,
+ float crit_weight)
{
auto &wd = wire_data(wire);
auto &nd = nets.at(net->udata);
@@ -367,13 +367,14 @@ struct Router2
float present_cost = 1.0f + overuse * curr_cong_weight * crit_weight;
if (pip != PipId()) {
Loc pl = ctx->getPipLocation(pip);
- bias_cost = cfg.bias_cost_factor * (base_cost / int(net->users.size())) *
+ bias_cost = cfg.bias_cost_factor * (base_cost / int(net->users.entries())) *
((std::abs(pl.x - nd.cx) + std::abs(pl.y - nd.cy)) / float(nd.hpwl));
}
return base_cost * hist_cost * present_cost / (1 + (source_uses * crit_weight)) + bias_cost;
}
- float get_togo_cost(NetInfo *net, size_t user, int wire, WireId src_sink, float crit_weight, bool bwd = false)
+ float get_togo_cost(NetInfo *net, store_index<PortRef> user, int wire, WireId src_sink, float crit_weight,
+ bool bwd = false)
{
auto &nd = nets.at(net->udata);
auto &wd = flat_wires[wire];
@@ -386,10 +387,10 @@ struct Router2
return (ctx->getDelayNS(est_delay) / (1 + source_uses * crit_weight)) + cfg.ipin_cost_adder;
}
- bool check_arc_routing(NetInfo *net, size_t usr, size_t phys_pin)
+ bool check_arc_routing(NetInfo *net, store_index<PortRef> usr, size_t phys_pin)
{
auto &nd = nets.at(net->udata);
- auto &ad = nd.arcs.at(usr).at(phys_pin);
+ auto &ad = nd.arcs.at(usr.idx()).at(phys_pin);
WireId src_wire = nets.at(net->udata).src_wire;
WireId cursor = ad.sink_wire;
while (nd.wires.count(cursor)) {
@@ -404,10 +405,10 @@ struct Router2
return (cursor == src_wire);
}
- void record_prerouted_net(NetInfo *net, size_t usr, size_t phys_pin)
+ void record_prerouted_net(NetInfo *net, store_index<PortRef> usr, size_t phys_pin)
{
auto &nd = nets.at(net->udata);
- auto &ad = nd.arcs.at(usr).at(phys_pin);
+ auto &ad = nd.arcs.at(usr.idx()).at(phys_pin);
ad.routed = true;
WireId src = nets.at(net->udata).src_wire;
@@ -449,7 +450,7 @@ struct Router2
}
// Find all the wires that must be used to route a given arc
- bool reserve_wires_for_arc(NetInfo *net, size_t i)
+ bool reserve_wires_for_arc(NetInfo *net, store_index<PortRef> i)
{
bool did_something = false;
WireId src = ctx->getNetinfoSourceWire(net);
@@ -459,7 +460,7 @@ struct Router2
WireId cursor = sink;
bool done = false;
if (ctx->debug)
- log("reserving wires for arc %d (%s.%s) of net %s\n", int(i), ctx->nameOf(usr.cell),
+ log("reserving wires for arc %d (%s.%s) of net %s\n", i.idx(), ctx->nameOf(usr.cell),
ctx->nameOf(usr.port), ctx->nameOf(net));
while (!done) {
auto &wd = wire_data(cursor);
@@ -501,8 +502,8 @@ struct Router2
WireId src = ctx->getNetinfoSourceWire(net);
if (src == WireId())
continue;
- for (size_t i = 0; i < net->users.size(); i++)
- did_something |= reserve_wires_for_arc(net, i);
+ for (auto usr : net->users.enumerate())
+ did_something |= reserve_wires_for_arc(net, usr.index);
}
} while (did_something);
}
@@ -529,12 +530,12 @@ struct Router2
return false;
}
- void update_wire_by_loc(ThreadContext &t, NetInfo *net, size_t i, size_t phys_pin, bool is_mt)
+ void update_wire_by_loc(ThreadContext &t, NetInfo *net, store_index<PortRef> i, size_t phys_pin, bool is_mt)
{
if (is_pseudo_const_net(net))
return;
auto &nd = nets.at(net->udata);
- auto &ad = nd.arcs.at(i).at(phys_pin);
+ auto &ad = nd.arcs.at(i.idx()).at(phys_pin);
WireId cursor = ad.sink_wire;
if (!nd.wires.count(cursor))
return;
@@ -571,28 +572,29 @@ struct Router2
bool was_visited_fwd(int wire) { return flat_wires.at(wire).visited_fwd; }
bool was_visited_bwd(int wire) { return flat_wires.at(wire).visited_bwd; }
- float get_arc_crit(NetInfo *net, size_t i)
+ float get_arc_crit(NetInfo *net, store_index<PortRef> i)
{
if (!timing_driven)
return 0;
return tmg.get_criticality(CellPortKey(net->users.at(i)));
}
- bool arc_failed_slack(NetInfo *net, size_t usr_idx)
+ bool arc_failed_slack(NetInfo *net, store_index<PortRef> usr_idx)
{
return timing_driven_ripup &&
(tmg.get_setup_slack(CellPortKey(net->users.at(usr_idx))) < (2 * ctx->getDelayEpsilon()));
}
- ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, size_t i, size_t phys_pin, bool is_mt, bool is_bb = true)
+ ArcRouteResult route_arc(ThreadContext &t, NetInfo *net, store_index<PortRef> i, size_t phys_pin, bool is_mt,
+ bool is_bb = true)
{
// Do some initial lookups and checks
auto arc_start = std::chrono::high_resolution_clock::now();
auto &nd = nets[net->udata];
- auto &ad = nd.arcs.at(i).at(phys_pin);
+ auto &ad = nd.arcs.at(i.idx()).at(phys_pin);
auto &usr = net->users.at(i);
- ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", int(i), ctx->nameOf(net), ad.bb.x0, ad.bb.y0,
- ad.bb.x1, ad.bb.y1);
+ ROUTE_LOG_DBG("Routing arc %d of net '%s' (%d, %d) -> (%d, %d)\n", i.idx(), ctx->nameOf(net), ad.bb.x0,
+ ad.bb.y0, ad.bb.x1, ad.bb.y1);
WireId src_wire = ctx->getNetinfoSourceWire(net), dst_wire = ctx->getNetinfoSinkWire(net, usr, phys_pin);
if (src_wire == WireId())
ARC_LOG_ERR("No wire found for port %s on source cell %s.\n", ctx->nameOf(net->driver.port),
@@ -614,7 +616,7 @@ struct Router2
// 0. starting within a small range of existing routing
// 1. expanding from all routing
int mode = 0;
- if (net->users.size() < 4 || nd.wires.empty() || (crit > 0.95))
+ if (net->users.entries() < 4 || nd.wires.empty() || (crit > 0.95))
mode = 1;
// This records the point where forwards and backwards routing met
@@ -844,11 +846,11 @@ struct Router2
t.processed_sinks.insert(dst_wire);
ad.routed = true;
auto arc_end = std::chrono::high_resolution_clock::now();
- ROUTE_LOG_DBG("Routing arc %d of net '%s' (is_bb = %d) took %02fs\n", int(i), ctx->nameOf(net), is_bb,
+ ROUTE_LOG_DBG("Routing arc %d of net '%s' (is_bb = %d) took %02fs\n", i.idx(), ctx->nameOf(net), is_bb,
std::chrono::duration<float>(arc_end - arc_start).count());
} else {
auto arc_end = std::chrono::high_resolution_clock::now();
- ROUTE_LOG_DBG("Failed routing arc %d of net '%s' (is_bb = %d) took %02fs\n", int(i), ctx->nameOf(net),
+ ROUTE_LOG_DBG("Failed routing arc %d of net '%s' (is_bb = %d) took %02fs\n", i.idx(), ctx->nameOf(net),
is_bb, std::chrono::duration<float>(arc_end - arc_start).count());
result = ARC_RETRY_WITHOUT_BB;
}
@@ -880,26 +882,26 @@ struct Router2
t.in_wire_by_loc.clear();
auto &nd = nets.at(net->udata);
bool failed_slack = false;
- for (size_t i = 0; i < net->users.size(); i++)
- failed_slack |= arc_failed_slack(net, i);
- for (size_t i = 0; i < net->users.size(); i++) {
- auto &ad = nd.arcs.at(i);
+ for (auto usr : net->users.enumerate())
+ failed_slack |= arc_failed_slack(net, usr.index);
+ for (auto usr : net->users.enumerate()) {
+ auto &ad = nd.arcs.at(usr.index.idx());
for (size_t j = 0; j < ad.size(); j++) {
// Ripup failed arcs to start with
// Check if arc is already legally routed
- if (!failed_slack && check_arc_routing(net, i, j)) {
- update_wire_by_loc(t, net, i, j, true);
+ if (!failed_slack && check_arc_routing(net, usr.index, j)) {
+ update_wire_by_loc(t, net, usr.index, j, true);
continue;
}
// Ripup arc to start with
- ripup_arc(net, i, j);
- t.route_arcs.emplace_back(i, j);
+ ripup_arc(net, usr.index, j);
+ t.route_arcs.emplace_back(usr.index, j);
}
}
// Route most critical arc first
std::stable_sort(t.route_arcs.begin(), t.route_arcs.end(),
- [&](std::pair<size_t, size_t> a, std::pair<size_t, size_t> b) {
+ [&](std::pair<store_index<PortRef>, size_t> a, std::pair<store_index<PortRef>, size_t> b) {
return get_arc_crit(net, a.first) > get_arc_crit(net, b.first);
});
for (auto a : t.route_arcs) {
@@ -913,7 +915,7 @@ struct Router2
} else {
// Attempt a re-route without the bounding box constraint
ROUTE_LOG_DBG("Rerouting arc %d.%d of net '%s' without bounding box, possible tricky routing...\n",
- int(a.first), int(a.second), ctx->nameOf(net));
+ a.first.idx(), int(a.second), ctx->nameOf(net));
auto res2 = route_arc(t, net, a.first, a.second, is_mt, false);
// If this also fails, no choice but to give up
if (res2 != ARC_SUCCESS) {
@@ -926,7 +928,7 @@ struct Router2
log("\n");
}
}
- log_error("Failed to route arc %d.%d of net '%s', from %s to %s.\n", int(a.first),
+ log_error("Failed to route arc %d.%d of net '%s', from %s to %s.\n", a.first.idx(),
int(a.second), ctx->nameOf(net), ctx->nameOfWire(ctx->getNetinfoSourceWire(net)),
ctx->nameOfWire(ctx->getNetinfoSinkWire(net, net->users.at(a.first), a.second)));
}
@@ -991,7 +993,7 @@ struct Router2
}
}
- bool bind_and_check(NetInfo *net, int usr_idx, int phys_pin)
+ bool bind_and_check(NetInfo *net, store_index<PortRef> usr_idx, int phys_pin)
{
#ifdef ARCH_ECP5
if (net->is_global)
@@ -999,7 +1001,7 @@ struct Router2
#endif
bool success = true;
auto &nd = nets.at(net->udata);
- auto &ad = nd.arcs.at(usr_idx).at(phys_pin);
+ auto &ad = nd.arcs.at(usr_idx.idx()).at(phys_pin);
auto &usr = net->users.at(usr_idx);
WireId src = ctx->getNetinfoSourceWire(net);
// Skip routes with no source
@@ -1043,7 +1045,8 @@ struct Router2
if (!nd.wires.count(cursor)) {
log("Failure details:\n");
log(" Cursor: %s\n", ctx->nameOfWire(cursor));
- log_error("Internal error; incomplete route tree for arc %d of net %s.\n", usr_idx, ctx->nameOf(net));
+ log_error("Internal error; incomplete route tree for arc %d of net %s.\n", usr_idx.idx(),
+ ctx->nameOf(net));
}
PipId p = nd.wires.at(cursor).first;
if (ctx->checkPipAvailForNet(p, net)) {
@@ -1104,9 +1107,9 @@ struct Router2
}
// Bind the arcs using the routes we have discovered
- for (size_t i = 0; i < net->users.size(); i++) {
- for (size_t phys_pin = 0; phys_pin < nets.at(net->udata).arcs.at(i).size(); phys_pin++) {
- if (!bind_and_check(net, i, phys_pin)) {
+ for (auto usr : net->users.enumerate()) {
+ for (size_t phys_pin = 0; phys_pin < nets.at(net->udata).arcs.at(usr.index.idx()).size(); phys_pin++) {
+ if (!bind_and_check(net, usr.index, phys_pin)) {
++arch_fail;
success = false;
}
@@ -1313,10 +1316,10 @@ struct Router2
route_net(tcs.at(N), fail, false);
}
- delay_t get_route_delay(int net, int usr_idx, int phys_idx)
+ delay_t get_route_delay(int net, store_index<PortRef> usr_idx, int phys_idx)
{
auto &nd = nets.at(net);
- auto &ad = nd.arcs.at(usr_idx).at(phys_idx);
+ auto &ad = nd.arcs.at(usr_idx.idx()).at(phys_idx);
WireId cursor = ad.sink_wire;
if (cursor == WireId() || nd.src_wire == WireId())
return 0;
@@ -1344,11 +1347,11 @@ struct Router2
continue;
#endif
auto &nd = nets.at(net);
- for (int i = 0; i < int(nd.arcs.size()); i++) {
+ for (auto usr : ni->users.enumerate()) {
delay_t arc_delay = 0;
- for (int j = 0; j < int(nd.arcs.at(i).size()); j++)
- arc_delay = std::max(arc_delay, get_route_delay(net, i, j));
- tmg.set_route_delay(CellPortKey(ni->users.at(i)), DelayPair(arc_delay));
+ for (int j = 0; j < int(nd.arcs.at(usr.index.idx()).size()); j++)
+ arc_delay = std::max(arc_delay, get_route_delay(net, usr.index, j));
+ tmg.set_route_delay(CellPortKey(usr.value), DelayPair(arc_delay));
}
}
}
@@ -1416,8 +1419,8 @@ struct Router2
if (timing_driven_ripup && iter < 500) {
for (size_t i = 0; i < nets_by_udata.size(); i++) {
NetInfo *ni = nets_by_udata.at(i);
- for (size_t j = 0; j < ni->users.size(); j++) {
- if (arc_failed_slack(ni, j)) {
+ for (auto usr : ni->users.enumerate()) {
+ if (arc_failed_slack(ni, usr.index)) {
failed_nets.insert(i);
++tmgfail;
}
@@ -1451,7 +1454,7 @@ struct Router2
log_info("1000 slowest nets by runtime:\n");
for (int i = 0; i < std::min(int(nets_by_runtime.size()), 1000); i++) {
log(" %80s %6d %.1fms\n", nets_by_runtime.at(i).second.c_str(ctx),
- int(ctx->nets.at(nets_by_runtime.at(i).second)->users.size()),
+ int(ctx->nets.at(nets_by_runtime.at(i).second)->users.entries()),
nets_by_runtime.at(i).first / 1000.0);
}
}
diff --git a/common/timing.cc b/common/timing.cc
index f30d4fc5..834785fb 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -60,14 +60,6 @@ void TimingAnalyser::init_ports()
data.cell_port = CellPortKey(ci->name, port.first);
}
}
- // Cell port to net port mapping
- for (auto &net : ctx->nets) {
- NetInfo *ni = net.second.get();
- if (ni->driver.cell != nullptr)
- ports[CellPortKey(ni->driver)].net_port = NetPortKey(ni->name);
- for (size_t i = 0; i < ni->users.size(); i++)
- ports[CellPortKey(ni->users.at(i))].net_port = NetPortKey(ni->name, i);
- }
}
void TimingAnalyser::get_cell_delays()
@@ -79,7 +71,7 @@ void TimingAnalyser::get_cell_delays()
IdString name = port.first.port;
// Ignore dangling ports altogether for timing purposes
- if (pd.net_port.net == IdString())
+ if (!pi.net)
continue;
pd.cell_arcs.clear();
int clkInfoCount = 0;
diff --git a/common/timing.h b/common/timing.h
index b34fd636..fe1bcaa8 100644
--- a/common/timing.h
+++ b/common/timing.h
@@ -44,28 +44,6 @@ struct CellPortKey
}
};
-struct NetPortKey
-{
- IdString net;
- size_t idx;
- NetPortKey(){};
- explicit NetPortKey(IdString net) : net(net), idx(DRIVER_IDX){}; // driver
- explicit NetPortKey(IdString net, size_t user) : net(net), idx(user){}; // user
-
- static const size_t DRIVER_IDX = std::numeric_limits<size_t>::max();
-
- inline bool is_driver() const { return (idx == DRIVER_IDX); }
- inline size_t user_idx() const
- {
- NPNR_ASSERT(idx != DRIVER_IDX);
- return idx;
- }
-
- unsigned int hash() const { return mkhash(net.hash(), idx); }
-
- inline bool operator==(const NetPortKey &other) const { return (net == other.net) && (idx == other.idx); }
-};
-
struct ClockDomainKey
{
IdString clock;
@@ -194,7 +172,6 @@ struct TimingAnalyser
struct PerPort
{
CellPortKey cell_port;
- NetPortKey net_port;
PortType type;
// per domain timings
dict<domain_id_t, ArrivReqTime> arrival;
diff --git a/common/timing_opt.cc b/common/timing_opt.cc
index a73a70cf..f9246292 100644
--- a/common/timing_opt.cc
+++ b/common/timing_opt.cc
@@ -73,8 +73,7 @@ class TimingOptimiser
for (auto usr : ni->users) {
max_net_delay[std::make_pair(usr.cell->name, usr.port)] = std::numeric_limits<delay_t>::max();
}
- for (size_t i = 0; i < ni->users.size(); i++) {
- auto &usr = ni->users.at(i);
+ for (auto usr : ni->users) {
delay_t net_delay = ctx->getNetinfoRouteDelay(ni, usr);
delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
delay_t domain_slack = tmg.get_domain_setup_slack(CellPortKey(usr));
@@ -234,7 +233,7 @@ class TimingOptimiser
std::vector<std::vector<PortRef *>> find_crit_paths(float crit_thresh, size_t max_count)
{
std::vector<std::vector<PortRef *>> crit_paths;
- std::vector<std::pair<NetInfo *, int>> crit_nets;
+ std::vector<std::pair<NetInfo *, store_index<PortRef>>> crit_nets;
std::vector<IdString> netnames;
std::transform(ctx->nets.begin(), ctx->nets.end(), std::back_inserter(netnames),
[](const std::pair<IdString, std::unique_ptr<NetInfo>> &kv) { return kv.first; });
@@ -243,28 +242,19 @@ class TimingOptimiser
if (crit_nets.size() >= max_count)
break;
float highest_crit = 0;
- size_t crit_user_idx = 0;
+ store_index<PortRef> crit_user_idx{};
NetInfo *ni = ctx->nets.at(net).get();
- for (size_t i = 0; i < ni->users.size(); i++) {
- float crit = tmg.get_criticality(CellPortKey(ni->users.at(i)));
+ for (auto usr : ni->users.enumerate()) {
+ float crit = tmg.get_criticality(CellPortKey(usr.value));
if (crit > highest_crit) {
highest_crit = crit;
- crit_user_idx = i;
+ crit_user_idx = usr.index;
}
}
if (highest_crit > crit_thresh)
- crit_nets.push_back(std::make_pair(ni, crit_user_idx));
+ crit_nets.emplace_back(ni, crit_user_idx);
}
- auto port_user_index = [](CellInfo *cell, PortInfo &port) -> size_t {
- NPNR_ASSERT(port.net != nullptr);
- for (size_t i = 0; i < port.net->users.size(); i++) {
- auto &usr = port.net->users.at(i);
- if (usr.cell == cell && usr.port == port.name)
- return i;
- }
- NPNR_ASSERT_FALSE("port user not found on net");
- };
pool<PortRef *, hash_ptr_ops> used_ports;
for (auto crit_net : crit_nets) {
@@ -280,7 +270,7 @@ class TimingOptimiser
NetInfo *back_cursor = crit_net.first;
while (back_cursor != nullptr) {
float max_crit = 0;
- std::pair<NetInfo *, size_t> crit_sink{nullptr, 0};
+ std::pair<NetInfo *, store_index<PortRef>> crit_sink{nullptr, {}};
CellInfo *cell = back_cursor->driver.cell;
if (cell == nullptr)
break;
@@ -298,13 +288,12 @@ class TimingOptimiser
bool is_path = ctx->getCellDelay(cell, port.first, back_cursor->driver.port, combDelay);
if (!is_path)
continue;
- size_t user_idx = port_user_index(cell, port.second);
float usr_crit = tmg.get_criticality(CellPortKey(cell->name, port.first));
- if (used_ports.count(&(pn->users.at(user_idx))))
+ if (used_ports.count(&(pn->users.at(port.second.user_idx))))
continue;
if (usr_crit >= max_crit) {
max_crit = usr_crit;
- crit_sink = std::make_pair(pn, user_idx);
+ crit_sink = std::make_pair(pn, port.second.user_idx);
}
}
@@ -319,7 +308,7 @@ class TimingOptimiser
while (fwd_cursor != nullptr) {
crit_path.push_back(fwd_cursor);
float max_crit = 0;
- std::pair<NetInfo *, size_t> crit_sink{nullptr, 0};
+ std::pair<NetInfo *, store_index<PortRef>> crit_sink{nullptr, {}};
CellInfo *cell = fwd_cursor->cell;
for (auto port : cell->ports) {
if (port.second.type != PORT_OUT)
@@ -336,13 +325,13 @@ class TimingOptimiser
bool is_path = ctx->getCellDelay(cell, fwd_cursor->port, port.first, combDelay);
if (!is_path)
continue;
- for (size_t i = 0; i < pn->users.size(); i++) {
- if (used_ports.count(&(pn->users.at(i))))
+ for (auto usr : pn->users.enumerate()) {
+ if (used_ports.count(&(pn->users.at(usr.index))))
continue;
- float crit = tmg.get_criticality(CellPortKey(pn->users.at(i)));
+ float crit = tmg.get_criticality(CellPortKey(usr.value));
if (crit >= max_crit) {
max_crit = crit;
- crit_sink = std::make_pair(pn, i);
+ crit_sink = std::make_pair(pn, usr.index);
}
}
}
@@ -409,14 +398,10 @@ class TimingOptimiser
delay_t original_delay = 0;
for (size_t i = 0; i < path.size(); i++) {
- NetInfo *pn = path.at(i)->cell->ports.at(path.at(i)->port).net;
- for (size_t j = 0; j < pn->users.size(); j++) {
- auto &usr = pn->users.at(j);
- if (usr.cell == path.at(i)->cell && usr.port == path.at(i)->port) {
- original_delay += ctx->predictArcDelay(pn, usr);
- break;
- }
- }
+ auto &port = path.at(i)->cell->ports.at(path.at(i)->port);
+ NetInfo *pn = port.net;
+ if (port.user_idx)
+ original_delay += ctx->predictArcDelay(pn, pn->users.at(port.user_idx));
}
IdString last_cell;
@@ -493,14 +478,10 @@ class TimingOptimiser
delay_t total_delay = 0;
for (size_t i = 0; i < path.size(); i++) {
- NetInfo *pn = path.at(i)->cell->ports.at(path.at(i)->port).net;
- for (size_t j = 0; j < pn->users.size(); j++) {
- auto &usr = pn->users.at(j);
- if (usr.cell == path.at(i)->cell && usr.port == path.at(i)->port) {
- total_delay += ctx->predictArcDelay(pn, usr);
- break;
- }
- }
+ auto &port = path.at(i)->cell->ports.at(path.at(i)->port);
+ NetInfo *pn = port.net;
+ if (port.user_idx)
+ total_delay += ctx->predictArcDelay(pn, pn->users.at(port.user_idx));
if (path.at(i)->cell == next_cell)
break;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 18:46:57 +0000