From 86699b42f619960bfefd4d0b479dd44a90527ea4 Mon Sep 17 00:00:00 2001 From: gatecat Date: Sat, 26 Feb 2022 15:17:46 +0000 Subject: Switch to potentially-sparse net users array This uses a new data structure for net.users that allows gaps, so removing a port from a net is no longer an O(n) operation on the number of users the net has. Signed-off-by: gatecat --- common/context.cc | 14 ++-- common/design_utils.h | 14 ++-- common/indexed_store.h | 47 +++++++++-- common/nextpnr_types.cc | 25 +++--- common/nextpnr_types.h | 3 +- common/placer1.cc | 68 +++++++--------- common/placer_heap.cc | 14 ++-- common/pybindings.cc | 4 +- common/pycontainers.h | 57 ++++++++++++++ common/router1.cc | 62 +++++++-------- common/router2.cc | 139 +++++++++++++++++---------------- common/timing.cc | 10 +-- common/timing.h | 23 ------ common/timing_opt.cc | 65 ++++++--------- ecp5/cells.cc | 7 +- ecp5/globals.cc | 22 +++--- ecp5/pack.cc | 56 ++++++------- fpga_interchange/arch.cc | 4 +- fpga_interchange/arch_pack_clusters.cc | 6 +- fpga_interchange/globals.cc | 26 +++--- frontend/frontend_base.h | 2 +- generic/cells.cc | 2 +- generic/pack.cc | 7 +- generic/viaduct/okami/okami.cc | 2 +- generic/viaduct_helpers.cc | 4 +- gowin/pack.cc | 11 +-- ice40/bitstream.cc | 2 +- ice40/cells.cc | 2 +- ice40/chains.cc | 61 ++++----------- ice40/pack.cc | 81 +++++++++---------- machxo2/pack.cc | 2 +- mistral/pack.cc | 14 ++-- nexus/global.cc | 8 +- nexus/pack.cc | 43 +++++----- 34 files changed, 442 insertions(+), 465 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 #include +#include #include #include "nextpnr_assertions.h" @@ -43,6 +44,7 @@ template 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 class indexed_store friend class indexed_store; public: - slot() : active(false), next_free(std::numeric_limits::max()){}; - slot(slot &&other) : active(other.active), next_free(other.next_free) + slot() : next_free(std::numeric_limits::max()), active(false){}; + slot(slot &&other) : next_free(other.next_free), active(other.active) { if (active) ::new (static_cast(&storage)) T(std::move(other.obj())); }; + slot(const slot &other) : next_free(other.next_free), active(other.active) + { + if (active) + ::new (static_cast(&storage)) T(other.obj()); + }; + template void create(Args &&...args) { NPNR_ASSERT(!active); @@ -131,8 +139,16 @@ template 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 class indexed_store int32_t capacity() const { return int32_t(slots.size()); } // Iterate over items + template class enumerated_iterator; + class iterator { private: @@ -182,9 +200,14 @@ template class indexed_store return prior; } T &operator*() { return base->at(store_index(index)); } - template friend class enumerated_iterator; + template 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 class indexed_store return prior; } const T &operator*() { return base->at(store_index(index)); } - template friend class enumerated_iterator; + template 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 struct enumerated_item { enumerated_item(int32_t index, T &value) : index(index), value(value){}; - store_index> index; + store_index> index; S &value; }; @@ -258,7 +286,10 @@ template class indexed_store }; enumerated_range enumerate() { return enumerated_range{begin(), end()}; } - enumerated_range enumerate() const { return enumerated_range{begin(), end()}; } + enumerated_range enumerate() const + { + return enumerated_range{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{}; 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 users; + indexed_store users; dict attrs; // wire -> uphill_pip @@ -155,6 +155,7 @@ struct PortInfo IdString name; NetInfo *net; PortType type; + store_index 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 bounds_changed_nets_x, bounds_changed_nets_y; - std::vector> changed_arcs; + std::vector>> changed_arcs; std::vector already_bounds_changed_x, already_bounds_changed_y; std::vector> already_changed_arcs; std::vector new_net_bounds; - std::vector, double>> new_arc_costs; + std::vector>, 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> net_arc_tcost; - // Fast lookup for cell port to net user index - dict, size_t> fast_port_to_user; - // Fast lookup for cell to clusters dict> 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 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()); + 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::max(), ubpos = std::numeric_limits::min(); - foreach_port(ni, [&](PortRef &port, int user_idx) { + foreach_port(ni, [&](PortRef &port, store_index 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 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(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, pass_through>::def_wrap(pi_cls, "type"); - typedef std::vector PortRefVector; + typedef indexed_store PortRefVector; typedef dict WireMap; typedef pool BelSet; typedef pool WireSet; @@ -288,7 +288,7 @@ PYBIND11_EMBEDDED_MODULE(MODULE_NAME, m) WRAP_MAP(m, WireMap, wrap_context, "WireMap"); WRAP_MAP_UPTR(m, RegionMap, "RegionMap"); - WRAP_VECTOR(m, PortRefVector, wrap_context); + WRAP_INDEXSTORE(m, PortRefVector, wrap_context); typedef dict ClockFmaxMap; WRAP_MAP(m, ClockFmaxMap, pass_through, "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().wrap(m, #t, #t "Iterator") +template > +struct indexed_store_wrapper +{ + typedef decltype(std::declval().begin()) iterator_t; + typedef decltype(*(std::declval())) value_t; + typedef typename PythonConversion::ContextualWrapper wrapped_vector; + typedef typename PythonConversion::ContextualWrapper> 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 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> 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_(m, range_name) + .def("__iter__", iter) + .def("__repr__", repr) + .def("__len__", len) + .def("__getitem__", getitem); + + iterator_wrapper().wrap(m, iter_name); + } + + typedef iterator_wrapper iter_wrap; +}; + +#define WRAP_INDEXSTORE(m, t, conv) \ + indexed_store_wrapper().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 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()(net_info); - seed ^= std::hash()(user_idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + seed ^= user_idx.hash() + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= std::hash()(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::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::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::min()) continue; @@ -1051,15 +1049,15 @@ bool Context::checkRoutedDesign() const found_unrouted = true; } - dict 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> 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::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 failed_nets; - std::vector> route_arcs; + std::vector, size_t>> route_arcs; std::priority_queue, 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 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 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 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 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 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 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 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 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 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 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 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 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(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(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 a, std::pair b) { + [&](std::pair, size_t> a, std::pair, 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 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 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::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 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::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> find_crit_paths(float crit_thresh, size_t max_count) { std::vector> crit_paths; - std::vector> crit_nets; + std::vector>> crit_nets; std::vector netnames; std::transform(ctx->nets.begin(), ctx->nets.end(), std::back_inserter(netnames), [](const std::pair> &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 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 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 crit_sink{nullptr, 0}; + std::pair> 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 crit_sink{nullptr, 0}; + std::pair> 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; } diff --git a/ecp5/cells.cc b/ecp5/cells.cc index a5d484ff..2c5f96d3 100644 --- a/ecp5/cells.cc +++ b/ecp5/cells.cc @@ -212,10 +212,7 @@ static void replace_port_safe(bool has_ff, CellInfo *ff, IdString ff_port, CellI NPNR_ASSERT(lc->ports.at(lc_port).net == ff->ports.at(ff_port).net); NetInfo *ffnet = ff->ports.at(ff_port).net; if (ffnet != nullptr) - ffnet->users.erase( - std::remove_if(ffnet->users.begin(), ffnet->users.end(), - [ff, ff_port](PortRef port) { return port.cell == ff && port.port == ff_port; }), - ffnet->users.end()); + ffnet->users.remove(ff->ports.at(ff_port).user_idx); } else { ff->movePortTo(ff_port, lc, lc_port); } @@ -477,7 +474,7 @@ void nxio_to_tr(Context *ctx, CellInfo *nxio, CellInfo *trio, std::vectorconnectPorts(id_Z, trio, id_T); created_cells.push_back(std::move(inv_lut)); - if (donet->users.size() > 1) { + if (donet->users.entries() > 1) { for (auto user : donet->users) log_info(" remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); log_error("unsupported tristate IO pattern for IO buffer '%s', " diff --git a/ecp5/globals.cc b/ecp5/globals.cc index 7b48e693..71188aa0 100644 --- a/ecp5/globals.cc +++ b/ecp5/globals.cc @@ -472,17 +472,15 @@ class Ecp5GlobalRouter } else if (is_logic_port(user)) { keep_users.push_back(user); } else { - glbptr->users.push_back(user); user.cell->ports.at(user.port).net = glbptr; + user.cell->ports.at(user.port).user_idx = glbptr->users.add(user); } } - net->users = keep_users; + net->users.clear(); + for (auto &usr : keep_users) + usr.cell->ports.at(usr.port).user_idx = net->users.add(usr); - dcc->ports[id_CLKI].net = net; - PortRef clki_pr; - clki_pr.port = id_CLKI; - clki_pr.cell = dcc.get(); - net->users.push_back(clki_pr); + dcc->connectPort(id_CLKI, net); if (net->clkconstr) { glbptr->clkconstr = std::unique_ptr(new ClockConstraint()); glbptr->clkconstr->low = net->clkconstr->low; @@ -556,9 +554,13 @@ class Ecp5GlobalRouter if (ci->type == id_DCCA || ci->type == id_DCSC) { NetInfo *clock = ci->ports.at((ci->type == id_DCSC) ? id_DCSOUT : id_CLKO).net; NPNR_ASSERT(clock != nullptr); - bool drives_fabric = std::any_of(clock->users.begin(), clock->users.end(), - [this](const PortRef &port) { return !is_clock_port(port); }); - + bool drives_fabric = false; + for (auto &usr : clock->users) { + if (!is_clock_port(usr)) { + drives_fabric = true; + break; + } + } int glbid; if (drives_fabric) { if (fab_globals.empty()) diff --git a/ecp5/pack.cc b/ecp5/pack.cc index 2b069db0..8c442843 100644 --- a/ecp5/pack.cc +++ b/ecp5/pack.cc @@ -326,14 +326,14 @@ class Ecp5Packer } // Pack LUTs feeding the same CCU2, RAM or DFF into a SLICE - if (znet != nullptr && znet->users.size() < 10) { + if (znet != nullptr && znet->users.entries() < 10) { for (auto user : znet->users) { if (is_lc(ctx, user.cell) || user.cell->type == id_DP16KD || is_ff(ctx, user.cell)) { for (auto port : user.cell->ports) { if (port.second.type != PORT_IN || port.second.net == nullptr || port.second.net == znet) continue; - if (port.second.net->users.size() > 10) + if (port.second.net->users.entries() > 10) continue; CellInfo *drv = port.second.net->driver.cell; if (drv == nullptr) @@ -355,11 +355,11 @@ class Ecp5Packer if (!ci->ports.count(ctx->id(inp))) continue; NetInfo *innet = ci->ports.at(ctx->id(inp)).net; - if (innet != nullptr && innet->users.size() < 5 && innet->users.size() > 1) + if (innet != nullptr && innet->users.entries() < 5 && innet->users.entries() > 1) inpnets.push_back(innet); } std::sort(inpnets.begin(), inpnets.end(), - [&](const NetInfo *a, const NetInfo *b) { return a->users.size() < b->users.size(); }); + [&](const NetInfo *a, const NetInfo *b) { return a->users.entries() < b->users.entries(); }); for (auto inet : inpnets) { for (auto &user : inet->users) { if (user.cell == nullptr || user.cell == ci || !is_lut(ctx, user.cell)) @@ -412,7 +412,7 @@ class Ecp5Packer return false; for (auto user : net->users) { if (is_top_port(user)) { - if (net->users.size() > 1) + if (net->users.entries() > 1) log_error(" port %s.%s must be connected to (and only to) a top level pin\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); tp = user; @@ -420,7 +420,7 @@ class Ecp5Packer } } if (net->driver.cell != nullptr && is_top_port(net->driver)) { - if (net->users.size() > 1) + if (net->users.entries() > 1) log_error(" port %s.%s must be connected to (and only to) a top level pin\n", net->driver.cell->name.c_str(ctx), net->driver.port.c_str(ctx)); tp = net->driver; @@ -460,9 +460,9 @@ class Ecp5Packer NetInfo *net = trio->ports.at(id_B).net; if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) && - net->users.size() > 1) || + net->users.entries() > 1) || (ci->type == ctx->id("$nextpnr_obuf") && - (net->users.size() > 2 || net->driver.cell != nullptr)) || + (net->users.entries() > 2 || net->driver.cell != nullptr)) || (ci->type == ctx->id("$nextpnr_iobuf") && ci->ports.at(id_I).net != nullptr && ci->ports.at(id_I).net->driver.cell != nullptr)) log_error("Pin B of %s '%s' connected to more than a single top level IO.\n", @@ -742,16 +742,14 @@ class Ecp5Packer feedin->params[id_INJECT1_0] = std::string("NO"); feedin->params[id_INJECT1_1] = std::string("YES"); - carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(), - [chain_in](const PortRef &user) { - return user.port == chain_in.port && user.cell == chain_in.cell; - }), - carry->users.end()); + carry->users.remove(chain_in.cell->ports.at(chain_in.port).user_idx); feedin->connectPort(id_A0, carry); NetInfo *new_carry = ctx->createNet(ctx->id(feedin->name.str(ctx) + "$COUT")); feedin->connectPort(id_COUT, new_carry); chain_in.cell->ports[chain_in.port].net = nullptr; + chain_in.cell->ports[chain_in.port].user_idx = {}; + chain_in.cell->connectPort(chain_in.port, new_carry); CellInfo *feedin_ptr = feedin.get(); @@ -782,12 +780,8 @@ class Ecp5Packer if (chain_next) { // Loop back into LUT4_1 for feedthrough feedout->connectPort(id_A1, carry); - - carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(), - [chain_next](const PortRef &user) { - return user.port == chain_next->port && user.cell == chain_next->cell; - }), - carry->users.end()); + if (chain_next->cell && chain_next->cell->ports.at(chain_next->port).user_idx) + carry->users.remove(chain_next->cell->ports.at(chain_next->port).user_idx); NetInfo *new_cout = ctx->createNet(ctx->id(feedout->name.str(ctx) + "$COUT")); feedout->connectPort(id_COUT, new_cout); @@ -833,7 +827,7 @@ class Ecp5Packer } else { NetInfo *carry_net = cell->ports.at(id_COUT).net; bool at_end = (curr_cell == carryc.cells.end() - 1); - if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) { + if (carry_net != nullptr && (carry_net->users.entries() > 1 || at_end)) { boost::optional nextport; if (!at_end) { auto next_cell = *(curr_cell + 1); @@ -1123,7 +1117,7 @@ class Ecp5Packer if (pn == nullptr) continue; // Skip high-fanout nets that are unlikely to be relevant - if (pn->users.size() > 25) + if (pn->users.entries() > 25) continue; // Add other ports on this net if not already visited auto visit_port = [&](const PortRef &port) { @@ -1304,11 +1298,11 @@ class Ecp5Packer } else { // Not allowed to change to a tie-high uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } else if (is_ff(ctx, uc) && user.port == id_LSR && ((!constval && str_or_default(uc->params, id_LSRMUX, "LSR") == "LSR") || @@ -1335,7 +1329,7 @@ class Ecp5Packer user.port.str(ctx).substr(0, 6) == "SOURCE" || user.port.str(ctx).substr(0, 6) == "SIGNED" || user.port.str(ctx).substr(0, 2) == "OP") { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } else { // Connected to CIB ABCD. Default state is bitstream configurable uc->params[ctx->id(user.port.str(ctx) + "MUX")] = std::string(constval ? "1" : "0"); @@ -1343,7 +1337,7 @@ class Ecp5Packer } } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } } @@ -2037,7 +2031,7 @@ class Ecp5Packer CellInfo *ci = cell.second.get(); if (ci->type == id_DQSBUFM) { CellInfo *pio = net_driven_by(ctx, ci->ports.at(id_DQSI).net, is_trellis_io, id_O); - if (pio == nullptr || ci->ports.at(id_DQSI).net->users.size() > 1) + if (pio == nullptr || ci->ports.at(id_DQSI).net->users.entries() > 1) log_error("DQSBUFM '%s' DQSI input must be connected only to a top level input\n", ci->name.c_str(ctx)); if (!pio->attrs.count(id_BEL)) @@ -2273,7 +2267,7 @@ class Ecp5Packer CellInfo *i_pio = net_driven_by(ctx, ci->ports.at(id_A).net, is_trellis_io, id_O); CellInfo *o_pio = net_only_drives(ctx, ci->ports.at(id_Z).net, is_trellis_io, id_I, true); CellInfo *iol = nullptr; - if (i_pio != nullptr && ci->ports.at(id_A).net->users.size() == 1) { + if (i_pio != nullptr && ci->ports.at(id_A).net->users.entries() == 1) { iol = create_pio_iologic(i_pio, ci); set_iologic_mode(iol, "IREG_OREG"); bool drives_iologic = false; @@ -2356,7 +2350,7 @@ class Ecp5Packer CellInfo *ci = cell.second.get(); if (ci->type == id_IDDRX1F) { CellInfo *pio = net_driven_by(ctx, ci->ports.at(id_D).net, is_trellis_io, id_O); - if (pio == nullptr || ci->ports.at(id_D).net->users.size() > 1) + if (pio == nullptr || ci->ports.at(id_D).net->users.entries() > 1) log_error("IDDRX1F '%s' D input must be connected only to a top level input\n", ci->name.c_str(ctx)); CellInfo *iol; @@ -2438,7 +2432,7 @@ class Ecp5Packer packed_cells.insert(cell.first); } else if (ci->type == id_IDDRX2F || ci->type == id_IDDR71B) { CellInfo *pio = net_driven_by(ctx, ci->ports.at(id_D).net, is_trellis_io, id_O); - if (pio == nullptr || ci->ports.at(id_D).net->users.size() > 1) + if (pio == nullptr || ci->ports.at(id_D).net->users.entries() > 1) log_error("%s '%s' D input must be connected only to a top level input\n", ci->type.c_str(ctx), ci->name.c_str(ctx)); CellInfo *iol; @@ -2530,7 +2524,7 @@ class Ecp5Packer packed_cells.insert(cell.first); } else if (ci->type == id_IDDRX2DQA) { CellInfo *pio = net_driven_by(ctx, ci->ports.at(id_D).net, is_trellis_io, id_O); - if (pio == nullptr || ci->ports.at(id_D).net->users.size() > 1) + if (pio == nullptr || ci->ports.at(id_D).net->users.entries() > 1) log_error("IDDRX2DQA '%s' D input must be connected only to a top level input\n", ci->name.c_str(ctx)); CellInfo *iol; @@ -2597,7 +2591,7 @@ class Ecp5Packer // See if it can be packed as an input ff NetInfo *d = ci->getPort(id_DI); CellInfo *pio = net_driven_by(ctx, d, is_trellis_io, id_O); - if (pio != nullptr && d->users.size() == 1) { + if (pio != nullptr && d->users.entries() == 1) { // Input FF CellInfo *iol; if (pio_iologic.count(pio->name)) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 917af85e..a5e802d3 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -1377,7 +1377,7 @@ void Arch::merge_constant_nets() } NPNR_ASSERT(net->driver.port == gnd_cell_port); - std::vector users_copy = net->users; + indexed_store users_copy = net->users; for (const PortRef &port_ref : users_copy) { IdString cell = port_ref.cell->name; disconnectPort(cell, port_ref.port); @@ -1400,7 +1400,7 @@ void Arch::merge_constant_nets() } NPNR_ASSERT(net->driver.port == vcc_cell_port); - std::vector users_copy = net->users; + indexed_store users_copy = net->users; for (const PortRef &port_ref : users_copy) { IdString cell = port_ref.cell->name; disconnectPort(cell, port_ref.port); diff --git a/fpga_interchange/arch_pack_clusters.cc b/fpga_interchange/arch_pack_clusters.cc index 31e0522b..97a3e1a5 100644 --- a/fpga_interchange/arch_pack_clusters.cc +++ b/fpga_interchange/arch_pack_clusters.cc @@ -945,10 +945,10 @@ void Arch::prepare_cluster(const ClusterPOD *cluster, uint32_t index) if (port_info.type == PORT_OUT) { exclude_nets.insert(port_info.net->name); auto &users = port_info.net->users; - if (users.size() != 1) + if (users.entries() != 1) continue; - CellInfo *user_cell = users[0].cell; + CellInfo *user_cell = (*users.begin()).cell; if (user_cell == nullptr) continue; @@ -978,7 +978,7 @@ void Arch::prepare_cluster(const ClusterPOD *cluster, uint32_t index) } else if (port_info.type == PORT_IN) { auto &driver = port_info.net->driver; auto &users = port_info.net->users; - if (users.size() != 1) + if (users.entries() != 1) continue; CellInfo *driver_cell = driver.cell; diff --git a/fpga_interchange/globals.cc b/fpga_interchange/globals.cc index ed9f73a6..6efd1d89 100644 --- a/fpga_interchange/globals.cc +++ b/fpga_interchange/globals.cc @@ -41,8 +41,8 @@ struct GlobalVist // This is our main global routing implementation. It is used both to actually route globals; and also to discover if // global buffers have available short routes from their source for auto-placement -static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t phys_port_idx, int max_hops, - bool dry_run) +static int route_global_arc(Context *ctx, NetInfo *net, store_index usr_idx, size_t phys_port_idx, + int max_hops, bool dry_run) { auto &usr = net->users.at(usr_idx); WireId src = ctx->getNetinfoSourceWire(net); @@ -51,7 +51,7 @@ static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t p if (dry_run) return -1; else - log_error("Arc %d.%d (%s.%s) of net %s has no sink wire!\n", int(usr_idx), int(phys_port_idx), + log_error("Arc %d.%d (%s.%s) of net %s has no sink wire!\n", usr_idx.idx(), int(phys_port_idx), ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net)); } // Consider any existing routing put in place by the site router, etc @@ -188,14 +188,6 @@ void Arch::place_globals() // Ignore if there is no driver; or the driver is not placed if (net->driver.cell == nullptr || net->driver.cell->bel == BelId()) continue; - size_t user_idx = 0; - bool found_user = false; - for (user_idx = 0; user_idx < net->users.size(); user_idx++) - if (net->users.at(user_idx).cell == ci && net->users.at(user_idx).port == pin_name) { - found_user = true; - break; - } - NPNR_ASSERT(found_user); // TODO: substantial performance improvements are probably possible, although of questionable benefit given // the low number of globals in a typical device... @@ -213,7 +205,7 @@ void Arch::place_globals() if (!isBelLocationValid(bel)) goto fail; // Check distance - distance = route_global_arc(ctx, net, user_idx, 0, pin.max_hops, true); + distance = route_global_arc(ctx, net, port.user_idx, 0, pin.max_hops, true); if (distance != -1 && distance < shortest_distance) { best_bel = bel; shortest_distance = distance; @@ -262,16 +254,16 @@ void Arch::route_globals() int total_sinks = 0; int global_sinks = 0; - for (size_t i = 0; i < net->users.size(); i++) { - auto &usr = net->users.at(i); - for (size_t j = 0; j < ctx->getNetinfoSinkWireCount(net, usr); j++) { - int result = route_global_arc(ctx, net, i, j, pin.max_hops, false); + for (auto usr : net->users.enumerate()) { + for (size_t j = 0; j < ctx->getNetinfoSinkWireCount(net, usr.value); j++) { + int result = route_global_arc(ctx, net, usr.index, j, pin.max_hops, false); ++total_sinks; if (result != -1) ++global_sinks; if ((result == -1) && pin.force_routing) log_error("Failed to route arc %d.%d (%s.%s) of net %s using dedicated global routing!\n", - int(i), int(j), ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net)); + usr.index.idx(), int(j), ctx->nameOf(usr.value.cell), ctx->nameOf(usr.value.port), + ctx->nameOf(net)); } } diff --git a/frontend/frontend_base.h b/frontend/frontend_base.h index 8ac61bbe..a2ac219c 100644 --- a/frontend/frontend_base.h +++ b/frontend/frontend_base.h @@ -690,7 +690,7 @@ template struct GenericFrontend // Combine users for (auto &usr : mergee->users) { usr.cell->ports[usr.port].net = base; - base->users.push_back(usr); + usr.cell->ports[usr.port].user_idx = base->users.add(usr); } // Point aliases to the new net for (IdString alias : mergee->aliases) { diff --git a/generic/cells.cc b/generic/cells.cc index 76d6474f..e4a24767 100644 --- a/generic/cells.cc +++ b/generic/cells.cc @@ -121,7 +121,7 @@ void nxio_to_iob(Context *ctx, CellInfo *nxio, CellInfo *iob, pool &to tbuf->movePortTo(ctx->id("A"), iob, ctx->id("I")); tbuf->movePortTo(ctx->id("E"), iob, ctx->id("EN")); - if (donet->users.size() > 1) { + if (donet->users.entries() > 1) { for (auto user : donet->users) log_info(" remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); log_error("unsupported tristate IO pattern for IO buffer '%s', " diff --git a/generic/pack.cc b/generic/pack.cc index cb3f5897..428d6642 100644 --- a/generic/pack.cc +++ b/generic/pack.cc @@ -124,9 +124,10 @@ static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constne log_info("%s user %s\n", orig->name.c_str(ctx), uc->name.c_str(ctx)); if ((is_lut(ctx, uc) || is_lc(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } } @@ -224,8 +225,8 @@ static void pack_io(Context *ctx) ci->type.c_str(ctx), ci->name.c_str(ctx)); NetInfo *net = iob->ports.at(ctx->id("PAD")).net; if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) && - net->users.size() > 1) || - (ci->type == ctx->id("$nextpnr_obuf") && (net->users.size() > 2 || net->driver.cell != nullptr))) + net->users.entries() > 1) || + (ci->type == ctx->id("$nextpnr_obuf") && (net->users.entries() > 2 || net->driver.cell != nullptr))) log_error("PAD of %s '%s' connected to more than a single top level IO.\n", iob->type.c_str(ctx), iob->name.c_str(ctx)); diff --git a/generic/viaduct/okami/okami.cc b/generic/viaduct/okami/okami.cc index bcb34e84..864bdb45 100644 --- a/generic/viaduct/okami/okami.cc +++ b/generic/viaduct/okami/okami.cc @@ -511,7 +511,7 @@ struct OkamiImpl : ViaductAPI const auto &ff_data = fast_cell_info.at(ff->flat_index); // In our example arch; the FF D can either be driven from LUT F or LUT I3 // so either; FF D must equal LUT F or LUT I3 must be unused - if (ff_data.ff_d == lut_data.lut_f && lut_data.lut_f->users.size() == 1) + if (ff_data.ff_d == lut_data.lut_f && lut_data.lut_f->users.entries() == 1) return true; // Can't route FF and LUT output separately return false; diff --git a/generic/viaduct_helpers.cc b/generic/viaduct_helpers.cc index 10c3b802..a92d0de1 100644 --- a/generic/viaduct_helpers.cc +++ b/generic/viaduct_helpers.cc @@ -96,7 +96,7 @@ int ViaductHelpers::constrain_cell_pairs(const pool &src_ports, co continue; if (!src_ports.count(CellTypePort(ci.type, port.first))) continue; - if (!allow_fanout && port.second.net->users.size() > 1) + if (!allow_fanout && port.second.net->users.entries() > 1) continue; for (auto &usr : port.second.net->users) { if (!sink_ports.count(CellTypePort(usr))) @@ -151,7 +151,7 @@ void ViaductHelpers::replace_constants(CellTypePort vcc_driver, CellTypePort gnd NetInfo *replace = (ni.driver.cell->type == ctx->id("VCC")) ? vcc_net : gnd_net; for (auto &usr : ni.users) { usr.cell->ports.at(usr.port).net = replace; - replace->users.push_back(usr); + usr.cell->ports.at(usr.port).user_idx = replace->users.add(usr); } trim_cells.push_back(ni.driver.cell->name); trim_nets.push_back(ni.name); diff --git a/gowin/pack.cc b/gowin/pack.cc index cc715864..c17a20c7 100644 --- a/gowin/pack.cc +++ b/gowin/pack.cc @@ -68,7 +68,7 @@ static void pack_alus(Context *ctx) continue; } - if (!is_alu(ctx, cin_ci) || cin->users.size() > 1) { + if (!is_alu(ctx, cin_ci) || cin->users.entries() > 1) { if (ctx->verbose) { log_info("ALU head found %s. CIN net is %s\n", ctx->nameOf(ci), ctx->nameOf(cin)); } @@ -177,9 +177,9 @@ static void pack_alus(Context *ctx) new_cells.push_back(std::move(packed)); - if (cout != nullptr && cout->users.size() > 0) { + if (cout != nullptr && cout->users.entries() > 0) { // if COUT used by logic - if ((cout->users.size() > 1) || (!is_alu(ctx, cout->users.at(0).cell))) { + if ((cout->users.entries() > 1) || (!is_alu(ctx, (*cout->users.begin()).cell))) { if (ctx->verbose) { log_info("COUT is used by logic\n"); } @@ -204,7 +204,7 @@ static void pack_alus(Context *ctx) break; } // next ALU - ci = cout->users.at(0).cell; + ci = (*cout->users.begin()).cell; // if ALU is too big if (alu_idx == (ctx->gridDimX - 2) * 6 - 1) { log_error("ALU %s is the %dth in the chain. Such long chains are not supported.\n", ctx->nameOf(ci), @@ -596,9 +596,10 @@ static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constne log_info("%s user %s\n", ctx->nameOf(orig), ctx->nameOf(uc)); if ((is_lut(ctx, uc) || is_lc(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } } diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc index 89f84262..48fbc132 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.cc @@ -1146,7 +1146,7 @@ bool read_asc(Context *ctx, std::istream &in) if (port.second.type == PORT_OUT) net->driver = ref; else - net->users.push_back(ref); + port.second.user_idx = net->users.add(ref); } } } diff --git a/ice40/cells.cc b/ice40/cells.cc index b5f759b2..9166b41b 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -466,7 +466,7 @@ void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, pool &to tbuf->movePortTo(id_A, sbio, id_D_OUT_0); tbuf->movePortTo(id_E, sbio, id_OUTPUT_ENABLE); - if (donet->users.size() > 1) { + if (donet->users.entries() > 1) { for (auto user : donet->users) log_info(" remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); log_error("unsupported tristate IO pattern for IO buffer '%s', " diff --git a/ice40/chains.cc b/ice40/chains.cc index e6a37044..6ea261de 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -73,8 +73,8 @@ class ChainConstrainer } else { NetInfo *carry_net = cell->ports.at(id_COUT).net; bool at_end = (curr_cell == carryc.cells.end() - 1); - if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) { - if (carry_net->users.size() > 2 || + if (carry_net != nullptr && (carry_net->users.entries() > 1 || at_end)) { + if (carry_net->users.entries() > 2 || (net_only_drives(ctx, carry_net, is_lc, id_I3, false) != net_only_drives(ctx, carry_net, is_lc, id_CIN, false)) || (at_end && !net_only_drives(ctx, carry_net, is_lc, id_I3, true))) { @@ -116,15 +116,11 @@ class ChainConstrainer lc->ports.at(id_O).net = cout_port.net; NetInfo *co_i3_net = ctx->createNet(ctx->id(lc->name.str(ctx) + "$I3")); co_i3_net->driver = cout_port.net->driver; - PortRef i3_r; - i3_r.port = id_I3; - i3_r.cell = lc.get(); - co_i3_net->users.push_back(i3_r); + lc->connectPort(id_I3, co_i3_net); PortRef o_r; o_r.port = id_O; o_r.cell = lc.get(); cout_port.net->driver = o_r; - lc->ports.at(id_I3).net = co_i3_net; cout_port.net = co_i3_net; // If COUT also connects to a CIN; preserve the carry chain @@ -133,34 +129,21 @@ class ChainConstrainer // Connect I1 to 1 to preserve carry chain NetInfo *vcc = ctx->nets.at(ctx->id("$PACKER_VCC_NET")).get(); - lc->ports.at(id_I1).net = vcc; - PortRef i1_r; - i1_r.port = id_I1; - i1_r.cell = lc.get(); - vcc->users.push_back(i1_r); + lc->connectPort(id_I1, vcc); // Connect co_cin_net to the COUT of the LC - PortRef co_r; - co_r.port = id_COUT; - co_r.cell = lc.get(); - co_cin_net->driver = co_r; - lc->ports.at(id_COUT).net = co_cin_net; + lc->connectPort(id_COUT, co_cin_net); // Find the user corresponding to the next CIN int replaced_ports = 0; if (ctx->debug) log_info("cell: %s\n", cin_cell->name.c_str(ctx)); for (auto port : {id_CIN, id_I3}) { - auto &usr = lc->ports.at(id_O).net->users; - if (ctx->debug) - for (auto user : usr) - log_info("%s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); - auto fnd_user = std::find_if(usr.begin(), usr.end(), - [&](const PortRef &pr) { return pr.cell == cin_cell && pr.port == port; }); - if (fnd_user != usr.end()) { - co_cin_net->users.push_back(*fnd_user); - usr.erase(fnd_user); - cin_cell->ports.at(port).net = co_cin_net; + NetInfo *out_net = lc->ports.at(id_O).net; + auto &cin_p = cin_cell->ports.at(port); + if (cin_p.net == out_net) { + cin_cell->disconnectPort(port); + cin_cell->connectPort(port, co_cin_net); ++replaced_ports; } } @@ -181,30 +164,16 @@ class ChainConstrainer lc->params[id_CARRY_ENABLE] = Property::State::S1; lc->params[id_CIN_CONST] = Property::State::S1; lc->params[id_CIN_SET] = Property::State::S1; - lc->ports.at(id_I1).net = cin_port.net; - cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(), - [cin_cell, cin_port](const PortRef &usr) { - return usr.cell == cin_cell && usr.port == cin_port.name; - })); - PortRef i1_ref; - i1_ref.cell = lc.get(); - i1_ref.port = id_I1; - lc->ports.at(id_I1).net->users.push_back(i1_ref); + lc->connectPort(id_I1, cin_port.net); + cin_port.net->users.remove(cin_port.user_idx); NetInfo *out_net = ctx->createNet(ctx->id(lc->name.str(ctx) + "$O")); - PortRef drv_ref; - drv_ref.port = id_COUT; - drv_ref.cell = lc.get(); - out_net->driver = drv_ref; - lc->ports.at(id_COUT).net = out_net; + lc->connectPort(id_COUT, out_net); - PortRef usr_ref; - usr_ref.port = cin_port.name; - usr_ref.cell = cin_cell; - out_net->users.push_back(usr_ref); - cin_cell->ports.at(cin_port.name).net = out_net; + cin_port.net = nullptr; + cin_cell->connectPort(cin_port.name, out_net); IdString name = lc->name; ctx->assignCellInfo(lc.get()); diff --git a/ice40/pack.cc b/ice40/pack.cc index 4244f192..c32e346f 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -214,14 +214,14 @@ static void pack_carries(Context *ctx) PortRef pr; pr.cell = created_lc.get(); pr.port = id_I1; - i0_net->users.push_back(pr); + created_lc->ports.at(id_I1).user_idx = i0_net->users.add(pr); } created_lc->ports.at(id_I2).net = i1_net; if (i1_net) { PortRef pr; pr.cell = created_lc.get(); pr.port = id_I2; - i1_net->users.push_back(pr); + created_lc->ports.at(id_I2).user_idx = i1_net->users.add(pr); } new_cells.push_back(std::move(created_lc)); ++carry_only; @@ -230,16 +230,12 @@ static void pack_carries(Context *ctx) ci->movePortTo(id_CI, carry_lc, id_CIN); ci->movePortTo(id_CO, carry_lc, id_COUT); if (i0_net) { - auto &i0_usrs = i0_net->users; - i0_usrs.erase(std::remove_if(i0_usrs.begin(), i0_usrs.end(), [ci, ctx](const PortRef &pr) { - return pr.cell == ci && pr.port == id_I0; - })); + if (ci->ports.count(id_I0) && ci->ports.at(id_I0).user_idx) + i0_net->users.remove(ci->ports.at(id_I0).user_idx); } if (i1_net) { - auto &i1_usrs = i1_net->users; - i1_usrs.erase(std::remove_if(i1_usrs.begin(), i1_usrs.end(), [ci, ctx](const PortRef &pr) { - return pr.cell == ci && pr.port == id_I1; - })); + if (ci->ports.count(id_I1) && ci->ports.at(id_I1).user_idx) + i1_net->users.remove(ci->ports.at(id_I1).user_idx); } // Check for constant driver on CIN @@ -251,10 +247,7 @@ static void pack_carries(Context *ctx) cin_net == ctx->id("$PACKER_VCC_NET") ? Property::State::S1 : Property::State::S0; carry_lc->ports.at(id_CIN).net = nullptr; auto &cin_users = ctx->nets.at(cin_net)->users; - cin_users.erase( - std::remove_if(cin_users.begin(), cin_users.end(), [carry_lc, ctx](const PortRef &pr) { - return pr.cell == carry_lc && pr.port == id_CIN; - })); + cin_users.remove(carry_lc->ports.at(id_CIN).user_idx); } } exhausted_cells.insert(carry_lc->name); @@ -326,17 +319,20 @@ static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constne if ((is_lut(ctx, uc) || is_lc(ctx, uc) || is_carry(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else if ((is_sb_mac16(ctx, uc) || uc->type == id_ICESTORM_DSP) && (user.port != id_CLK && ((constval && user.port == id_CE) || (!constval && user.port != id_CE)))) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else if (is_ram(ctx, uc) && !constval && user.port != id_RCLK && user.port != id_RCLKN && user.port != id_WCLK && user.port != id_WCLKN && user.port != id_RCLKE && user.port != id_WCLKE) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } } @@ -486,8 +482,8 @@ static void pack_io(Context *ctx) ci->type.c_str(ctx), ci->name.c_str(ctx)); NetInfo *net = sb->ports.at(id_PACKAGE_PIN).net; if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) && - net->users.size() > 1) || - (ci->type == ctx->id("$nextpnr_obuf") && (net->users.size() > 2 || net->driver.cell != nullptr))) + net->users.entries() > 1) || + (ci->type == ctx->id("$nextpnr_obuf") && (net->users.entries() > 2 || net->driver.cell != nullptr))) log_error("PACKAGE_PIN of %s '%s' connected to more than a single top level IO.\n", sb->type.c_str(ctx), sb->name.c_str(ctx)); @@ -531,9 +527,9 @@ static void pack_io(Context *ctx) sb->attrs[attr.first] = attr.second; } else if (is_sb_io(ctx, ci) || is_sb_gb_io(ctx, ci)) { NetInfo *net = ci->ports.at(id_PACKAGE_PIN).net; - if ((net != nullptr) && ((net->users.size() > 2) || + if ((net != nullptr) && ((net->users.entries() > 2) || (net->driver.cell != nullptr && - net->driver.cell->type == ctx->id("$nextpnr_obuf") && net->users.size() > 1))) + net->driver.cell->type == ctx->id("$nextpnr_obuf") && net->users.entries() > 1))) log_error("PACKAGE_PIN of %s '%s' connected to more than a single top level IO.\n", ci->type.c_str(ctx), ci->name.c_str(ctx)); } @@ -554,11 +550,11 @@ static void pack_io(Context *ctx) NetInfo *net_in0 = ci->ports.count(id_D_IN_0) ? ci->ports[id_D_IN_0].net : nullptr; NetInfo *net_in1 = ci->ports.count(id_D_IN_1) ? ci->ports[id_D_IN_1].net : nullptr; - if (net_in0 != nullptr && net_in0->users.size() == 0) { + if (net_in0 != nullptr && net_in0->users.entries() == 0) { delete_nets.insert(net_in0->name); ci->ports[id_D_IN_0].net = nullptr; } - if (net_in1 != nullptr && net_in1->users.size() == 0) { + if (net_in1 != nullptr && net_in1->users.entries() == 0) { delete_nets.insert(net_in1->name); ci->ports[id_D_IN_1].net = nullptr; } @@ -591,28 +587,23 @@ static void insert_global(Context *ctx, NetInfo *net, bool is_reset, bool is_cen std::string glb_name = net->name.str(ctx) + std::string("_$glb_") + (is_reset ? "sr" : (is_cen ? "ce" : "clk")); std::unique_ptr gb = create_ice_cell(ctx, id_SB_GB, "$gbuf_" + glb_name); - gb->ports[id_USER_SIGNAL_TO_GLOBAL_BUFFER].net = net; - PortRef pr; - pr.cell = gb.get(); - pr.port = id_USER_SIGNAL_TO_GLOBAL_BUFFER; - net->users.push_back(pr); - - pr.cell = gb.get(); - pr.port = id_GLOBAL_BUFFER_OUTPUT; + gb->connectPort(id_USER_SIGNAL_TO_GLOBAL_BUFFER, net); NetInfo *glbnet = ctx->createNet(ctx->id(glb_name)); - glbnet->driver = pr; - gb->ports[id_GLOBAL_BUFFER_OUTPUT].net = glbnet; + gb->connectPort(id_GLOBAL_BUFFER_OUTPUT, glbnet); + std::vector keep_users; for (auto user : net->users) { if (is_clock_port(ctx, user) || (is_reset && is_reset_port(ctx, user)) || (is_cen && is_enable_port(ctx, user)) || (is_logic && is_logic_port(ctx, user))) { user.cell->ports[user.port].net = glbnet; - glbnet->users.push_back(user); + user.cell->ports[user.port].user_idx = glbnet->users.add(user); } else { keep_users.push_back(user); } } - net->users = keep_users; + net->users.clear(); + for (auto &user : keep_users) + user.cell->ports[user.port].user_idx = net->users.add(user); if (net->clkconstr) { glbnet->clkconstr = std::unique_ptr(new ClockConstraint()); @@ -809,7 +800,7 @@ static void place_plls(Context *ctx) log_error("PLL '%s' has a PACKAGEPIN driven by an %s, should be directly connected to an input " "SB_IO.D_IN_0 port\n", ci->name.c_str(ctx), io_cell->type.c_str(ctx)); - if (ni->users.size() != 1) + if (ni->users.entries() != 1) log_error("PLL '%s' clock input '%s' can only drive PLL\n", ci->name.c_str(ctx), ni->name.c_str(ctx)); if (!io_cell->attrs.count(id_BEL)) log_error("PLL '%s' PACKAGEPIN SB_IO '%s' is unconstrained\n", ci->name.c_str(ctx), @@ -911,10 +902,10 @@ static void place_plls(Context *ctx) // Used global connections bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.entries() > 0); bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.entries() > 0); // Check for conflict BelPin pll_io_a, pll_io_b; @@ -954,15 +945,15 @@ static void place_plls(Context *ctx) // Used global connections bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.entries() > 0); bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.entries() > 0); // Could this be a PAD PLL ? bool could_be_pad = false; BelId pad_bel; - if (ni->users.size() == 1 && is_sb_io(ctx, ni->driver.cell) && ni->driver.cell->attrs.count(id_BEL)) + if (ni->users.entries() == 1 && is_sb_io(ctx, ni->driver.cell) && ni->driver.cell->attrs.count(id_BEL)) pad_bel = ctx->getBelByNameStr(ni->driver.cell->attrs[id_BEL].as_string()); // Find a BEL for it @@ -1035,7 +1026,7 @@ static std::unique_ptr spliceLUT(Context *ctx, CellInfo *ci, IdString PortRef pr; pr.cell = user.cell; pr.port = user.port; - out_net->users.push_back(pr); + user.cell->ports[user.port].user_idx = out_net->users.add(pr); } // Add LUT to new users. @@ -1045,8 +1036,10 @@ static std::unique_ptr spliceLUT(Context *ctx, CellInfo *ci, IdString new_users.push_back(pr); pt->ports.at(id_I3).net = port.net; - // Replace users of the original net. - port.net->users = new_users; + // Replace users of the original net + port.net->users.clear(); + for (auto &usr : new_users) + usr.cell->ports.at(usr.port).user_idx = port.net->users.add(usr); return pt; } @@ -1235,7 +1228,7 @@ static void pack_special(Context *ctx) if ((pi.name != id_RGB0) && (pi.name != id_RGB1) && (pi.name != id_RGB2)) continue; - if (net->users.size() > 0) + if (net->users.entries() > 0) log_error("SB_RGB_DRV/SB_RGBA_DRV port connected to more than just package pin !\n"); ctx->nets.erase(net->name); @@ -1585,7 +1578,7 @@ void pack_plls(Context *ctx) // Only if there is actually a net ... if (pi.net != nullptr) { // ... and it's used - if (pi.net->users.size() > 0) { + if (pi.net->users.entries() > 0) { std::unique_ptr gb = create_padin_gbuf(ctx, packed.get(), pi.name, "$gbuf_" + ci->name.str(ctx) + "_pllout_" + (is_b_port ? "b" : "a")); diff --git a/machxo2/pack.cc b/machxo2/pack.cc index 5051a981..56efb63f 100644 --- a/machxo2/pack.cc +++ b/machxo2/pack.cc @@ -160,7 +160,7 @@ static void set_net_constant(Context *ctx, NetInfo *orig, NetInfo *constnet, boo uc->ports[user.port].net = constnet; } - constnet->users.push_back(user); + user.cell->ports.at(user.port).user_idx = constnet->users.add(user); } } orig->users.clear(); diff --git a/mistral/pack.cc b/mistral/pack.cc index c4b3afe3..703fa386 100644 --- a/mistral/pack.cc +++ b/mistral/pack.cc @@ -200,10 +200,10 @@ struct MistralPacker NetInfo *o = ci->getPort(id_O); if (o == nullptr) ; - else if (o->users.size() > 1) + else if (o->users.entries() > 1) log_error("Top level pin '%s' has multiple input buffers\n", ctx->nameOf(port.first)); - else if (o->users.size() == 1) - top_port = o->users.at(0); + else if (o->users.entries() == 1) + top_port = *o->users.begin(); } if (ci->type == ctx->id("$nextpnr_obuf") || ci->type == ctx->id("$nextpnr_iobuf")) { // Might have an output buffer (OB etc) connected to it @@ -215,9 +215,9 @@ struct MistralPacker top_port = i->driver; } // Edge case of a bidirectional buffer driving an output pin - if (i->users.size() > 2) { + if (i->users.entries() > 2) { log_error("Top level pin '%s' has illegal buffer configuration\n", ctx->nameOf(port.first)); - } else if (i->users.size() == 2) { + } else if (i->users.entries() == 2) { if (top_port.cell != nullptr) log_error("Top level pin '%s' has illegal buffer configuration\n", ctx->nameOf(port.first)); for (auto &usr : i->users) { @@ -300,9 +300,9 @@ struct MistralPacker const NetInfo *co = cursor->getPort(id_CO); if (co == nullptr || co->users.empty()) break; - if (co->users.size() > 1) + if (co->users.entries() > 1) log_error("Carry net %s has more than one sink!\n", ctx->nameOf(co)); - auto &usr = co->users.at(0); + auto &usr = *co->users.begin(); if (usr.port != id_CI) log_error("Carry net %s drives port %s, expected CI\n", ctx->nameOf(co), ctx->nameOf(usr.port)); cursor = usr.cell; diff --git a/nexus/global.cc b/nexus/global.cc index 1c763a31..31bf0a6b 100644 --- a/nexus/global.cc +++ b/nexus/global.cc @@ -72,7 +72,7 @@ struct NexusGlobalRouter // Dedicated backwards BFS routing for global networks template - bool backwards_bfs_route(NetInfo *net, size_t user_idx, int iter_limit, bool strict, Tfilt pip_filter) + bool backwards_bfs_route(NetInfo *net, store_index user_idx, int iter_limit, bool strict, Tfilt pip_filter) { // Queue of wires to visit std::queue visit; @@ -178,9 +178,9 @@ struct NexusGlobalRouter void route_clk_net(NetInfo *net) { - for (size_t i = 0; i < net->users.size(); i++) - backwards_bfs_route(net, i, 1000000, true, [&](PipId pip) { - return (is_relaxed_sink(net->users.at(i)) || global_pip_filter(pip)) && routeability_pip_filter(pip); + for (auto usr : net->users.enumerate()) + backwards_bfs_route(net, usr.index, 1000000, true, [&](PipId pip) { + return (is_relaxed_sink(usr.value) || global_pip_filter(pip)) && routeability_pip_filter(pip); }); log_info(" routed net '%s' using global resources\n", ctx->nameOf(net)); } diff --git a/nexus/pack.cc b/nexus/pack.cc index 5509d997..a769c05a 100644 --- a/nexus/pack.cc +++ b/nexus/pack.cc @@ -489,10 +489,10 @@ struct NexusPacker NetInfo *o = ci->getPort(id_O); if (o == nullptr) ; - else if (o->users.size() > 1) + else if (o->users.entries() > 1) log_error("Top level pin '%s' has multiple input buffers\n", ctx->nameOf(port.first)); - else if (o->users.size() == 1) - top_port = o->users.at(0); + else if (o->users.entries() == 1) + top_port = *o->users.begin(); } if (ci->type == ctx->id("$nextpnr_obuf") || ci->type == ctx->id("$nextpnr_iobuf")) { // Might have an output buffer (OB etc) connected to it @@ -504,9 +504,9 @@ struct NexusPacker top_port = i->driver; } // Edge case of a bidirectional buffer driving an output pin - if (i->users.size() > 2) { + if (i->users.entries() > 2) { log_error("Top level pin '%s' has illegal buffer configuration\n", ctx->nameOf(port.first)); - } else if (i->users.size() == 2) { + } else if (i->users.entries() == 2) { if (top_port.cell != nullptr) log_error("Top level pin '%s' has illegal buffer configuration\n", ctx->nameOf(port.first)); for (auto &usr : i->users) { @@ -834,13 +834,15 @@ struct NexusPacker for (auto &usr : net->users) { if (pred(usr)) { usr.cell->ports[usr.port].net = buffered_net; - buffered_net->users.push_back(usr); + usr.cell->ports[usr.port].user_idx = buffered_net->users.add(usr); } else { remaining_users.push_back(usr); } } - std::swap(net->users, remaining_users); + net->users.clear(); + for (auto &usr : remaining_users) + usr.cell->ports.at(usr.port).user_idx = net->users.add(usr); // Connect buffer input to original net buffer->connectPort(i, net); @@ -1195,11 +1197,11 @@ struct NexusPacker if (di != nullptr && di->driver.cell != nullptr) iob = di->driver.cell; NetInfo *dout = ci->getPort(id_DOUT); - if (dout != nullptr && dout->users.size() == 1) - iob = dout->users.at(0).cell; + if (dout != nullptr && dout->users.entries() == 1) + iob = (*dout->users.begin()).cell; NetInfo *tout = ci->getPort(id_TOUT); - if (tout != nullptr && tout->users.size() == 1) - iob = tout->users.at(0).cell; + if (tout != nullptr && tout->users.entries() == 1) + iob = (*tout->users.begin()).cell; if (iob == nullptr || (iob->type != id_SEIO18_CORE && iob->type != id_SEIO33_CORE && iob->type != id_DIFFIO18_CORE)) log_error("Failed to find associated IOB for IOLOGIC %s\n", ctx->nameOf(ci)); @@ -1358,11 +1360,12 @@ struct NexusPacker NetInfo *fco = combs[1]->getPort(id_FCO); ci = nullptr; if (fco != nullptr) { - if (fco->users.size() > 1) + if (fco->users.entries() > 1) log_error("Carry cell '%s' has multiple fanout on FCO\n", ctx->nameOf(combs[1])); - else if (fco->users.size() == 1) { - NPNR_ASSERT(fco->users.at(0).port == id_CIN); - ci = fco->users.at(0).cell; + else if (fco->users.entries() == 1) { + auto &u0 = *fco->users.begin(); + NPNR_ASSERT(u0.port == id_CIN); + ci = u0.cell; } } } while (ci != nullptr); @@ -2161,13 +2164,13 @@ struct NexusPacker isIDDR = true; } NetInfo *dout = iol->getPort(id_DOUT); - if (dout != nullptr && dout->users.size() == 1) { - iob = dout->users.at(0).cell; + if (dout != nullptr && dout->users.entries() == 1) { + iob = (*dout->users.begin()).cell; isODDR = true; } NetInfo *tout = iol->getPort(id_TOUT); - if (tout != nullptr && tout->users.size() == 1) { - iob = tout->users.at(0).cell; + if (tout != nullptr && tout->users.entries() == 1) { + iob = (*tout->users.begin()).cell; isODDR = true; // FIXME: Not sure } NPNR_ASSERT(iob != nullptr); @@ -2359,7 +2362,7 @@ struct NexusPacker } // Skip if there are multiple sinks on that net - if (di->users.size() != 1) { + if (di->users.entries() != 1) { continue; } -- cgit v1.2.3