diff options
| -rw-r--r-- | fpga_interchange/arch.cc | 32 | ||||
| -rw-r--r-- | fpga_interchange/arch.h | 3 | ||||
| -rw-r--r-- | fpga_interchange/archdefs.h | 7 | ||||
| -rw-r--r-- | fpga_interchange/flat_wire_map.h | 121 | ||||
| -rw-r--r-- | fpga_interchange/site_arch.cc | 376 | ||||
| -rw-r--r-- | fpga_interchange/site_arch.h | 819 | ||||
| -rw-r--r-- | fpga_interchange/site_arch.impl.h | 255 | ||||
| -rw-r--r-- | fpga_interchange/site_router.cc | 1095 | ||||
| -rw-r--r-- | fpga_interchange/site_router.h | 3 | ||||
| -rw-r--r-- | fpga_interchange/site_routing_cache.cc | 193 | ||||
| -rw-r--r-- | fpga_interchange/site_routing_cache.h | 134 | ||||
| -rw-r--r-- | fpga_interchange/site_routing_storage.h | 150 |
12 files changed, 2617 insertions, 571 deletions
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 1cefb6fe..96169cf2 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -723,6 +723,36 @@ bool Arch::route() } } + HashTables::HashSet<WireId> wires_to_unbind; + for (auto &net_pair : nets) { + for (auto &wire_pair : net_pair.second->wires) { + WireId wire = wire_pair.first; + if (wire_pair.second.strength != STRENGTH_PLACER) { + // Only looking for bound placer wires + continue; + } + + const TileWireInfoPOD &wire_data = wire_info(wire); + NPNR_ASSERT(wire_data.site != -1); + + wires_to_unbind.emplace(wire); + } + } + + for (WireId wire : wires_to_unbind) { + unbindWire(wire); + } + + for (auto &tile_pair : tileStatus) { + for (auto &site_router : tile_pair.second.sites) { + if (site_router.cells_in_site.empty()) { + continue; + } + + site_router.bindSiteRouting(getCtx()); + } + } + bool result; if (router == "router1") { result = router1(getCtx(), Router1Cfg(getCtx())); @@ -1727,8 +1757,6 @@ bool Arch::check_pip_avail_for_net(PipId pip, NetInfo *net) const bool Arch::checkPipAvail(PipId pip) const { return check_pip_avail_for_net(pip, nullptr); } -Arch::~Arch() {} - // Instance constraint templates. template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 6a3d7ad1..005bbb41 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -37,6 +37,7 @@ #include "chipdb.h" #include "dedicated_interconnect.h" #include "site_router.h" +#include "site_routing_cache.h" NEXTPNR_NAMESPACE_BEGIN @@ -1037,6 +1038,8 @@ struct Arch : ArchAPI<ArchRanges> std::regex verilog_hex_constant; void read_lut_equation(DynamicBitarray<> *equation, const Property &equation_parameter) const; bool route_vcc_to_unused_lut_pins(); + mutable RouteNodeStorage node_storage; + mutable SiteRoutingCache site_routing_cache; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h index d20c5ea4..8364520d 100644 --- a/fpga_interchange/archdefs.h +++ b/fpga_interchange/archdefs.h @@ -98,11 +98,14 @@ struct BelBucketId bool operator<(const BelBucketId &other) const { return name < other.name; } }; +struct SiteExpansionLoop; + struct ArchNetInfo { -}; + virtual ~ArchNetInfo(); -struct NetInfo; + SiteExpansionLoop *loop = nullptr; +}; struct ArchCellInfo { diff --git a/fpga_interchange/flat_wire_map.h b/fpga_interchange/flat_wire_map.h new file mode 100644 index 00000000..71ecd0b6 --- /dev/null +++ b/fpga_interchange/flat_wire_map.h @@ -0,0 +1,121 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef FLAT_WIRE_MAP_H_ +#define FLAT_WIRE_MAP_H_ + +#include "context.h" +#include "dynamic_bitarray.h" +#include "nextpnr_namespaces.h" +#include "nextpnr_types.h" + +NEXTPNR_NAMESPACE_BEGIN + +template <typename Value> class FlatTileWireMap +{ + public: + std::pair<Value *, bool> emplace(const Context *ctx, WireId wire, const Value &value) + { + if (values_.empty()) { + if (wire.tile == -1) { + resize(ctx->chip_info->nodes.size()); + } else { + resize(loc_info(ctx->chip_info, wire).wire_data.size()); + } + } + + if (set_.get(wire.index)) { + return std::make_pair(&values_[wire.index], false); + } else { + values_[wire.index] = value; + set_.set(wire.index, true); + return std::make_pair(&values_[wire.index], true); + } + } + + const Value &at(WireId wire) const + { + NPNR_ASSERT(!values_.empty()); + NPNR_ASSERT(set_.get(wire.index)); + return values_.at(wire.index); + } + + void clear() + { + if (!values_.empty()) { + set_.fill(false); + } + } + + private: + void resize(size_t count) + { + set_.resize(count); + set_.fill(false); + values_.resize(count); + } + + DynamicBitarray<> set_; + std::vector<Value> values_; +}; + +template <typename Value> class FlatWireMap +{ + public: + FlatWireMap(const Context *ctx) : ctx_(ctx) { tiles_.resize(ctx->chip_info->tiles.size() + 1); } + + std::pair<std::pair<WireId, Value *>, bool> emplace(WireId wire, const Value &value) + { + // Tile = -1 is for node wires. + size_t tile_index = wire.tile + 1; + auto &tile = tiles_.at(tile_index); + + auto result = tile.emplace(ctx_, wire, value); + if (result.second) { + size_ += 1; + } + return std::make_pair(std::make_pair(wire, result.first), result.second); + } + + const Value &at(WireId wire) const + { + const auto &tile = tiles_.at(wire.tile + 1); + return tile.at(wire); + } + + size_t size() const { return size_; } + + void clear() + { + for (auto &tile : tiles_) { + tile.clear(); + } + size_ = 0; + } + + private: + const Context *ctx_; + std::vector<FlatTileWireMap<Value>> tiles_; + size_t size_; +}; + +NEXTPNR_NAMESPACE_END + +#endif /* FLAT_WIRE_MAP_H_ */ diff --git a/fpga_interchange/site_arch.cc b/fpga_interchange/site_arch.cc new file mode 100644 index 00000000..43792eda --- /dev/null +++ b/fpga_interchange/site_arch.cc @@ -0,0 +1,376 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "site_arch.h" +#include "site_arch.impl.h" + +NEXTPNR_NAMESPACE_BEGIN + +SiteInformation::SiteInformation(const Context *ctx, int32_t tile, int32_t site, + const std::unordered_set<CellInfo *> &cells_in_site) + : ctx(ctx), tile(tile), tile_type(ctx->chip_info->tiles[tile].type), site(site), cells_in_site(cells_in_site) +{ +} + +bool SiteArch::bindPip(const SitePip &pip, SiteNetInfo *net) +{ + SiteWire src = getPipSrcWire(pip); + SiteWire dst = getPipDstWire(pip); + + if (!bindWire(src, net)) { + return false; + } + if (!bindWire(dst, net)) { + unbindWire(src); + return false; + } + + auto result = net->wires.emplace(dst, SitePipMap{pip, 1}); + if (!result.second) { + if (result.first->second.pip != pip) { + // Pip conflict! + if (debug()) { + log_info("Pip conflict binding pip %s to wire %s, conflicts with pip %s\n", nameOfPip(pip), + nameOfWire(dst), nameOfPip(result.first->second.pip)); + } + + unbindWire(src); + unbindWire(dst); + return false; + } + + result.first->second.count += 1; + } + + return true; +} + +void SiteArch::unbindPip(const SitePip &pip) +{ + SiteWire src = getPipSrcWire(pip); + SiteWire dst = getPipDstWire(pip); + + SiteNetInfo *src_net = unbindWire(src); + SiteNetInfo *dst_net = unbindWire(dst); + NPNR_ASSERT(src_net == dst_net); + auto iter = dst_net->wires.find(dst); + NPNR_ASSERT(iter != dst_net->wires.end()); + NPNR_ASSERT(iter->second.count >= 1); + iter->second.count -= 1; + + if (iter->second.count == 0) { + dst_net->wires.erase(iter); + } +} + +void SiteArch::archcheck() +{ + for (SiteWire wire : getWires()) { + for (SitePip pip : getPipsDownhill(wire)) { + SiteWire wire2 = getPipSrcWire(pip); + log_assert(wire == wire2); + } + + for (SitePip pip : getPipsUphill(wire)) { + SiteWire wire2 = getPipDstWire(pip); + log_assert(wire == wire2); + } + } +} + +SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site_info(site_info) +{ + // Build list of input and output site ports + // + // FIXME: This doesn't need to be computed over and over, move to + // arch/chip db. + const TileTypeInfoPOD &tile_type = loc_info(&site_info->chip_info(), *site_info); + PipId pip; + pip.tile = site_info->tile; + for (size_t pip_index = 0; pip_index < tile_type.pip_data.size(); ++pip_index) { + if (tile_type.pip_data[pip_index].site != site_info->site) { + continue; + } + + pip.index = pip_index; + + if (!site_info->is_site_port(pip)) { + continue; + } + + WireId src_wire = ctx->getPipSrcWire(pip); + if (site_info->is_wire_in_site(src_wire)) { + output_site_ports.push_back(pip); + } else { + input_site_ports.push_back(pip); + } + } + + // Create list of out of site sources and sinks. + + for (CellInfo *cell : site_info->cells_in_site) { + for (const auto &pin_pair : cell->cell_bel_pins) { + const PortInfo &port = cell->ports.at(pin_pair.first); + if (port.net != nullptr) { + nets.emplace(port.net, SiteNetInfo{port.net}); + } + } + } + + for (auto &net_pair : nets) { + NetInfo *net = net_pair.first; + SiteNetInfo &net_info = net_pair.second; + + // All nets require drivers + NPNR_ASSERT(net->driver.cell != nullptr); + + bool net_driven_out_of_site = false; + if (net->driver.cell->bel == BelId()) { + // The driver of this site hasn't been placed, so treat it as + // out of site. + out_of_site_sources.push_back(SiteWire::make(site_info, PORT_OUT, net)); + net_info.driver = out_of_site_sources.back(); + net_driven_out_of_site = true; + } else { + if (!site_info->is_bel_in_site(net->driver.cell->bel)) { + + // The driver of this site has been placed, it is an out + // of site source. + out_of_site_sources.push_back(SiteWire::make(site_info, PORT_OUT, net)); + // out_of_site_sources.back().wire = ctx->getNetinfoSourceWire(net); + net_info.driver = out_of_site_sources.back(); + + net_driven_out_of_site = true; + } else { + net_info.driver = SiteWire::make(site_info, ctx->getNetinfoSourceWire(net)); + } + } + + if (net_driven_out_of_site) { + // Because this net is driven from a source out of the site, + // no out of site sink is required. + continue; + } + + // Examine net to determine if it has any users not in this site. + bool net_used_out_of_site = false; + for (const PortRef &user : net->users) { + NPNR_ASSERT(user.cell != nullptr); + + if (user.cell->bel == BelId()) { + // Because this net has a user that has not been placed, + // and this net is being driven from this site, make sure + // this net can be routed from this site. + net_used_out_of_site = true; + break; + } + + if (!site_info->is_bel_in_site(user.cell->bel)) { + net_used_out_of_site = true; + break; + } + } + + if (net_used_out_of_site) { + out_of_site_sinks.push_back(SiteWire::make(site_info, PORT_IN, net)); + net_info.users.emplace(out_of_site_sinks.back()); + } + } + + // At this point all nets have a driver SiteWire, but user SiteWire's + // within the site are not present. Add them now. + for (auto &net_pair : nets) { + NetInfo *net = net_pair.first; + SiteNetInfo &net_info = net_pair.second; + + for (const PortRef &user : net->users) { + if (!site_info->is_bel_in_site(user.cell->bel)) { + // Only care about BELs within the site at this point. + continue; + } + + for (IdString bel_pin : ctx->getBelPinsForCellPin(user.cell, user.port)) { + SiteWire wire = getBelPinWire(user.cell->bel, bel_pin); + // Don't add users that are trivially routable! + if (wire != net_info.driver) { +#ifdef DEBUG_SITE_ARCH + if (ctx->debug) { + log_info("Add user %s because it isn't driver %s\n", nameOfWire(wire), + nameOfWire(net_info.driver)); + } +#endif + net_info.users.emplace(wire); + } + } + } + } + + for (auto &net_pair : nets) { + SiteNetInfo *net_info = &net_pair.second; + auto result = wire_to_nets.emplace(net_info->driver, SiteNetMap{net_info, 1}); + // By this point, trivial congestion at sources should already by + // avoided, and there should be no duplicates in the + // driver/users data. + NPNR_ASSERT(result.second); + + for (const auto &user : net_info->users) { + result = wire_to_nets.emplace(user, SiteNetMap{net_info, 1}); + NPNR_ASSERT(result.second); + } + } +} + +SiteWire SiteArch::getBelPinWire(BelId bel, IdString pin) const +{ + WireId wire = ctx->getBelPinWire(bel, pin); + return SiteWire::make(site_info, wire); +} + +PortType SiteArch::getBelPinType(BelId bel, IdString pin) const { return ctx->getBelPinType(bel, pin); } + +const char *SiteArch::nameOfWire(const SiteWire &wire) const +{ + switch (wire.type) { + case SiteWire::SITE_WIRE: + return ctx->nameOfWire(wire.wire); + case SiteWire::SITE_PORT_SINK: + return ctx->nameOfWire(wire.wire); + case SiteWire::SITE_PORT_SOURCE: + return ctx->nameOfWire(wire.wire); + case SiteWire::OUT_OF_SITE_SOURCE: + return "out of site source, implement me!"; + case SiteWire::OUT_OF_SITE_SINK: + return "out of site sink, implement me!"; + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +const char *SiteArch::nameOfPip(const SitePip &pip) const +{ + switch (pip.type) { + case SitePip::SITE_PIP: + return ctx->nameOfPip(pip.pip); + case SitePip::SITE_PORT: + return ctx->nameOfPip(pip.pip); + case SitePip::SOURCE_TO_SITE_PORT: + return "source to site port, implement me!"; + case SitePip::SITE_PORT_TO_SINK: + return "site port to sink, implement me!"; + case SitePip::SITE_PORT_TO_SITE_PORT: + return "site port to site port, implement me!"; + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +const char *SiteArch::nameOfNet(const SiteNetInfo *net) const { return net->net->name.c_str(ctx); } + +bool SiteArch::debug() const { return ctx->debug; } + +SitePipUphillRange::SitePipUphillRange(const SiteArch *site_arch, SiteWire site_wire) + : site_arch(site_arch), site_wire(site_wire) +{ + switch (site_wire.type) { + case SiteWire::SITE_WIRE: + pip_range = site_arch->ctx->getPipsUphill(site_wire.wire); + break; + case SiteWire::OUT_OF_SITE_SOURCE: + // No normal pips! + break; + case SiteWire::OUT_OF_SITE_SINK: + // No normal pips! + break; + case SiteWire::SITE_PORT_SINK: + // No normal pips! + break; + case SiteWire::SITE_PORT_SOURCE: + // No normal pips! + break; + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +SitePip SitePipUphillIterator::operator*() const +{ + switch (state) { + case NORMAL_PIPS: + return SitePip::make(site_arch->site_info, *iter); + case PORT_SRC_TO_PORT_SINK: + return SitePip::make(site_arch->site_info, site_arch->output_site_ports.at(cursor), site_wire.pip); + case OUT_OF_SITE_SOURCES: + return SitePip::make(site_arch->site_info, site_arch->out_of_site_sources.at(cursor), site_wire.pip); + case OUT_OF_SITE_SINK_TO_PORT_SINK: + return SitePip::make(site_arch->site_info, site_arch->output_site_ports.at(cursor), site_wire); + case SITE_PORT: + return SitePip::make(site_arch->site_info, site_wire.pip); + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +SiteWire SiteWireIterator::operator*() const +{ + WireId wire; + PipId pip; + SiteWire site_wire; + switch (state) { + case NORMAL_WIRES: + wire.tile = site_arch->site_info->tile; + wire.index = cursor; + return SiteWire::make(site_arch->site_info, wire); + case INPUT_SITE_PORTS: + pip = site_arch->input_site_ports.at(cursor); + site_wire = SiteWire::make_site_port(site_arch->site_info, pip, /*dst_wire=*/false); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SOURCE); + return site_wire; + case OUTPUT_SITE_PORTS: + pip = site_arch->output_site_ports.at(cursor); + site_wire = SiteWire::make_site_port(site_arch->site_info, pip, /*dst_wire=*/true); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SINK); + return site_wire; + case OUT_OF_SITE_SOURCES: + return site_arch->out_of_site_sources.at(cursor); + case OUT_OF_SITE_SINKS: + return site_arch->out_of_site_sinks.at(cursor); + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +SiteWireIterator SiteWireRange::begin() const +{ + SiteWireIterator b; + + b.state = SiteWireIterator::BEGIN; + b.site_arch = site_arch; + b.tile_type = &loc_info(&site_arch->site_info->chip_info(), *site_arch->site_info); + + ++b; + return b; +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_arch.h b/fpga_interchange/site_arch.h new file mode 100644 index 00000000..f8524586 --- /dev/null +++ b/fpga_interchange/site_arch.h @@ -0,0 +1,819 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SITE_ARCH_H +#define SITE_ARCH_H + +#include <cstdint> +#include <unordered_set> +#include <vector> + +#include "arch_iterators.h" +#include "chipdb.h" +#include "hash_table.h" +#include "log.h" +#include "nextpnr_namespaces.h" +#include "nextpnr_types.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct Context; + +struct SiteInformation +{ + const Context *ctx; + + const int32_t tile; + const int32_t tile_type; + const int32_t site; + const std::unordered_set<CellInfo *> &cells_in_site; + + SiteInformation(const Context *ctx, int32_t tile, int32_t site, + const std::unordered_set<CellInfo *> &cells_in_site); + + inline const ChipInfoPOD &chip_info() const NPNR_ALWAYS_INLINE; + + inline bool is_wire_in_site(WireId wire) const NPNR_ALWAYS_INLINE; + + inline bool is_bel_in_site(BelId bel) const NPNR_ALWAYS_INLINE; + + inline bool is_pip_part_of_site(PipId pip) const NPNR_ALWAYS_INLINE; + + inline bool is_site_port(PipId pip) const NPNR_ALWAYS_INLINE; +}; + +// Site routing needs a modification of the routing graph. Within the site, +// the arch can be consulted for edges. However the rest of the routing graph +// needs to be reduced for analysis purposes. Wires within the site are +// SITE_WIRE's. 4 additional nodes are introduced to model out of site +// routing: +// - OUT_OF_SITE_SOURCE / OUT_OF_SITE_SINK +// - These represent net sources and sinks that are only reachable via the +// routing graph (e.g. outside of the site). +// - SITE_PORT_SOURCE / SITE_PORT_SINK +// - These represent the routing resources connected to other side of site +// ports. +// +// The non-site wire graph is connected like: +// +// ┌─────────────────┐ ┌────────────────────┐ +// │ │ │ │ +// │ OUT_OF_SITE_SRC │ │ OUT_OF_SITE_SINK │◄────┐ +// │ │ │ │ │ +// └┬────────────────┘ └────────────────────┘ │ +// │ │ +// │ ┌─────────────────────────────────────────────────────┤ +// │ │ │ +// │ │ │ +// │ │ │ +// │ │ │ +// │ ▼ │ +// │ ┌─────────────────┐ ┌─────────────┐ ┌────────────────┐ │ +// │ │ │ │ │ │ │ │ +// └─────►│ SITE_PORT_SRC ├──►│ Site ├──────►│ SITE_PORT_SINK ├──┘ +// │ │ │ │ │ │ +// └─────────────────┘ └─────────────┘ └────────────────┘ +// +struct SiteWire +{ + enum Type + { + // This wire is just a plain site wire. + SITE_WIRE = 0, + // This wire is a source that is from outside of the site. + OUT_OF_SITE_SOURCE = 1, + // This wire is a sink that is from outside of the site. + OUT_OF_SITE_SINK = 2, + // This wire is the routing graph wire on the dst side of a site port. + SITE_PORT_SINK = 3, + // This wire is the routing graph wire on the src side of a site port. + SITE_PORT_SOURCE = 4, + NUMBER_SITE_WIRE_TYPES = 5, + }; + + static inline SiteWire make(const SiteInformation *site_info, WireId site_wire) NPNR_ALWAYS_INLINE; + + static SiteWire make(const SiteInformation *site_info, PortType port_type, NetInfo *net) NPNR_ALWAYS_INLINE + { + SiteWire out; + if (port_type == PORT_OUT) { + out.type = OUT_OF_SITE_SOURCE; + out.net = net; + } else { + out.type = OUT_OF_SITE_SINK; + out.net = net; + } + return out; + } + + static inline SiteWire make_site_port(const SiteInformation *site_info, PipId pip, bool dst_wire); + + bool operator==(const SiteWire &other) const + { + return wire == other.wire && type == other.type && pip == other.pip && net == other.net; + } + bool operator!=(const SiteWire &other) const + { + return wire != other.wire || type != other.type || pip != other.pip || net != other.net; + } + bool operator<(const SiteWire &other) const + { + return std::make_tuple(type, wire, pip, net) < std::make_tuple(other.type, other.wire, other.pip, other.net); + } + + Type type = NUMBER_SITE_WIRE_TYPES; + WireId wire; + PipId pip; + NetInfo *net = nullptr; +}; + +struct SitePip +{ + enum Type + { + // This is a plain regular site pip. + SITE_PIP = 0, + // This pip is a site port, and connects a SITE_WIRE to a SITE_PORT_SINK/SITE_PORT_SRC + SITE_PORT = 1, + // This pip connects a OUT_OF_SITE_SOURCE to a SITE_PORT_SRC + SOURCE_TO_SITE_PORT = 2, + // This pip connects a SITE_PORT_SINK to a OUT_OF_SITE_SINK + SITE_PORT_TO_SINK = 3, + // This pip connects a SITE_PORT_SINK to a SITE_PORT_SRC. + SITE_PORT_TO_SITE_PORT = 4, + INVALID_TYPE = 5, + }; + + static inline SitePip make(const SiteInformation *site_info, PipId pip); + + static SitePip make(const SiteInformation *site_info, SiteWire src, PipId dst) + { + NPNR_ASSERT(src.type == SiteWire::OUT_OF_SITE_SOURCE); + + SitePip out; + out.type = SOURCE_TO_SITE_PORT; + out.pip = dst; + out.wire = src; + + return out; + } + + static SitePip make(const SiteInformation *site_info, PipId src, SiteWire dst) + { + NPNR_ASSERT(dst.type == SiteWire::OUT_OF_SITE_SINK); + + SitePip out; + out.type = SITE_PORT_TO_SINK; + out.pip = src; + out.wire = dst; + + return out; + } + + static SitePip make(const SiteInformation *site_info, PipId src_pip, PipId dst_pip) + { + SitePip out; + out.type = SITE_PORT_TO_SITE_PORT; + out.pip = src_pip; + out.other_pip = dst_pip; + + return out; + } + + Type type = INVALID_TYPE; + // For SITE_PORT_TO_SITE_PORT connections, pip is the site -> routing pip. + PipId pip; + SiteWire wire; + // For SITE_PORT_TO_SITE_PORT connections, other_pip is the routing -> + // site pip. + PipId other_pip; + + bool operator==(const SitePip &other) const + { + return type == other.type && pip == other.pip && wire == other.wire && other_pip == other.other_pip; + } + bool operator!=(const SitePip &other) const + { + return type != other.type || pip != other.pip || wire != other.wire || other_pip != other.other_pip; + } +}; +NEXTPNR_NAMESPACE_END + +template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SiteWire &site_wire) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(site_wire.type)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX WireId>()(site_wire.wire)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_wire.pip)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX NetInfo *>()(site_wire.net)); + return seed; + } +}; + +template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SitePip> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SitePip &site_pip) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SitePip::Type>()(site_pip.type)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_pip.pip)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire>()(site_pip.wire)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX PipId>()(site_pip.other_pip)); + return seed; + } +}; + +NEXTPNR_NAMESPACE_BEGIN + +struct SitePipDownhillRange; +struct SitePipUphillRange; +struct SiteWireRange; +struct SiteNetInfo; + +struct SitePipMap +{ + SitePip pip; + size_t count; +}; + +struct SiteNetMap +{ + SiteNetInfo *net; + size_t count; +}; + +struct SiteNetInfo +{ + NetInfo *net; + SiteWire driver; + HashTables::HashSet<SiteWire> users; + + HashTables::HashMap<SiteWire, SitePipMap> wires; +}; + +struct SiteArch +{ + const Context *const ctx; + const SiteInformation *const site_info; + + HashTables::HashMap<NetInfo *, SiteNetInfo> nets; + HashTables::HashMap<SiteWire, SiteNetMap> wire_to_nets; + + std::vector<PipId> input_site_ports; + std::vector<PipId> output_site_ports; + + std::vector<SiteWire> out_of_site_sources; + std::vector<SiteWire> out_of_site_sinks; + + SiteArch(const SiteInformation *site_info); + + inline SiteWire getPipSrcWire(const SitePip &site_pip) const NPNR_ALWAYS_INLINE; + inline SiteWire getPipDstWire(const SitePip &site_pip) const NPNR_ALWAYS_INLINE; + + inline SitePipDownhillRange getPipsDownhill(const SiteWire &site_wire) const NPNR_ALWAYS_INLINE; + inline SitePipUphillRange getPipsUphill(const SiteWire &site_wire) const NPNR_ALWAYS_INLINE; + SiteWireRange getWires() const; + + inline SiteWire getBelPinWire(BelId bel, IdString pin) const NPNR_ALWAYS_INLINE; + inline PortType getBelPinType(BelId bel, IdString pin) const NPNR_ALWAYS_INLINE; + + const char *nameOfWire(const SiteWire &wire) const; + const char *nameOfPip(const SitePip &pip) const; + const char *nameOfNet(const SiteNetInfo *net) const; + + bool debug() const; + + bool bindWire(const SiteWire &wire, SiteNetInfo *net) + { + auto result = wire_to_nets.emplace(wire, SiteNetMap{net, 1}); + if (result.first->second.net != net) { + if (debug()) { + log_info("Net conflict binding wire %s to net %s, conflicts with net %s\n", nameOfWire(wire), + nameOfNet(net), nameOfNet(result.first->second.net)); + } + return false; + } + + if (!result.second) { + result.first->second.count += 1; + } + + return true; + } + + SiteNetInfo *unbindWire(const SiteWire &wire) + { + auto iter = wire_to_nets.find(wire); + NPNR_ASSERT(iter != wire_to_nets.end()); + NPNR_ASSERT(iter->second.count >= 1); + SiteNetInfo *net = iter->second.net; + iter->second.count -= 1; + + if (iter->second.count == 0) { + wire_to_nets.erase(iter); + } + + return net; + } + + bool bindPip(const SitePip &pip, SiteNetInfo *net); + void unbindPip(const SitePip &pip); + + void archcheck(); + + bool is_pip_synthetic(const SitePip &pip) const NPNR_ALWAYS_INLINE; +}; + +struct SitePipDownhillIterator +{ + enum DownhillIteratorState + { + // Initial state + BEGIN = 0, + // Iterating over normal pips. + NORMAL_PIPS = 1, + // Iterating off all site port sources. + PORT_SINK_TO_PORT_SRC = 2, + // Iterating over out of site sinks. + OUT_OF_SITE_SINKS = 3, + // Iterating off all site port sources. + OUT_OF_SITE_SOURCE_TO_PORT_SRC = 4, + SITE_PORT = 5, + END = 6, + NUMBER_STATES = 7, + }; + + DownhillIteratorState state = BEGIN; + const SiteArch *site_arch; + SiteWire site_wire; + const RelSlice<int32_t> *pips_downhill; + size_t cursor; + + bool advance_in_state() NPNR_ALWAYS_INLINE + { + switch (state) { + case BEGIN: + return false; + case NORMAL_PIPS: + ++cursor; + return (cursor < pips_downhill->size()); + case PORT_SINK_TO_PORT_SRC: + ++cursor; + return (cursor < site_arch->input_site_ports.size()); + case OUT_OF_SITE_SINKS: + ++cursor; + return (cursor < site_arch->out_of_site_sinks.size()); + case OUT_OF_SITE_SOURCE_TO_PORT_SRC: + ++cursor; + return (cursor < site_arch->input_site_ports.size()); + case SITE_PORT: + ++cursor; + return false; + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + bool check_first() const NPNR_ALWAYS_INLINE + { + switch (state) { + case BEGIN: + return false; + case NORMAL_PIPS: + return (cursor < pips_downhill->size()); + case PORT_SINK_TO_PORT_SRC: + return (cursor < site_arch->input_site_ports.size()); + case OUT_OF_SITE_SINKS: + return (cursor < site_arch->out_of_site_sinks.size()); + case OUT_OF_SITE_SOURCE_TO_PORT_SRC: + return (cursor < site_arch->input_site_ports.size()); + case SITE_PORT: + return true; + case END: + return true; + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + const std::array<std::array<DownhillIteratorState, NUMBER_STATES>, SiteWire::NUMBER_SITE_WIRE_TYPES> + get_state_table() const + { + std::array<std::array<DownhillIteratorState, NUMBER_STATES>, SiteWire::NUMBER_SITE_WIRE_TYPES> state_table; + for (size_t j = 0; j < SiteWire::NUMBER_SITE_WIRE_TYPES; ++j) { + for (size_t i = 0; i < NUMBER_STATES; ++i) { + state_table[j][i] = NUMBER_STATES; + } + } + + state_table[SiteWire::SITE_WIRE][BEGIN] = NORMAL_PIPS; + state_table[SiteWire::SITE_WIRE][NORMAL_PIPS] = END; + + state_table[SiteWire::OUT_OF_SITE_SOURCE][BEGIN] = OUT_OF_SITE_SOURCE_TO_PORT_SRC; + state_table[SiteWire::OUT_OF_SITE_SOURCE][OUT_OF_SITE_SOURCE_TO_PORT_SRC] = END; + + state_table[SiteWire::OUT_OF_SITE_SINK][BEGIN] = END; + + state_table[SiteWire::SITE_PORT_SINK][BEGIN] = PORT_SINK_TO_PORT_SRC; + state_table[SiteWire::SITE_PORT_SINK][PORT_SINK_TO_PORT_SRC] = OUT_OF_SITE_SINKS; + state_table[SiteWire::SITE_PORT_SINK][OUT_OF_SITE_SINKS] = END; + + state_table[SiteWire::SITE_PORT_SOURCE][BEGIN] = SITE_PORT; + state_table[SiteWire::SITE_PORT_SOURCE][SITE_PORT] = END; + + return state_table; + } + + void advance_state() NPNR_ALWAYS_INLINE + { + state = get_state_table().at(site_wire.type).at(state); + cursor = 0; + NPNR_ASSERT(state >= BEGIN && state <= END); + } + + void operator++() NPNR_ALWAYS_INLINE + { + NPNR_ASSERT(state != END); + while (state != END) { + if (advance_in_state()) { + break; + } else { + advance_state(); + if (check_first()) { + break; + } + } + } + } + + bool operator!=(const SitePipDownhillIterator &other) const + { + return state != other.state || cursor != other.cursor; + } + + inline SitePip operator*() const NPNR_ALWAYS_INLINE; +}; + +struct SitePipDownhillRange +{ + const SiteArch *site_arch; + SiteWire site_wire; + + SitePipDownhillRange(const SiteArch *site_arch, const SiteWire &site_wire) + : site_arch(site_arch), site_wire(site_wire) + { + } + + inline const RelSlice<int32_t> *init_pip_range() const NPNR_ALWAYS_INLINE; + + inline SitePipDownhillIterator begin() const NPNR_ALWAYS_INLINE; + + SitePipDownhillIterator end() const NPNR_ALWAYS_INLINE + { + SitePipDownhillIterator e; + e.state = SitePipDownhillIterator::END; + e.cursor = 0; + + return e; + } +}; + +struct SitePipUphillIterator +{ + enum UphillIteratorState + { + // Initial state + BEGIN = 0, + // Iterating over normal pips. + NORMAL_PIPS = 1, + // Iterating off all site port sources. + PORT_SRC_TO_PORT_SINK = 2, + // Iterating over out of site sinks. + OUT_OF_SITE_SOURCES = 3, + // Iterating off all site port sources. + OUT_OF_SITE_SINK_TO_PORT_SINK = 4, + SITE_PORT = 5, + END = 6, + NUMBER_STATES = 7, + }; + + UphillIteratorState state = BEGIN; + const SiteArch *site_arch; + SiteWire site_wire; + size_t cursor; + UphillPipIterator iter; + UphillPipIterator uphill_end; + + bool advance_in_state() + { + switch (state) { + case BEGIN: + return false; + case NORMAL_PIPS: + while (iter != uphill_end) { + ++iter; + if (!(iter != uphill_end)) { + break; + } + } + + return false; + case PORT_SRC_TO_PORT_SINK: + ++cursor; + return (cursor < site_arch->output_site_ports.size()); + case OUT_OF_SITE_SOURCES: + ++cursor; + return (cursor < site_arch->out_of_site_sources.size()); + case OUT_OF_SITE_SINK_TO_PORT_SINK: + ++cursor; + return (cursor < site_arch->output_site_ports.size()); + case SITE_PORT: + ++cursor; + return false; + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + bool check_first() const + { + switch (state) { + case BEGIN: + return false; + case NORMAL_PIPS: + if (!(iter != uphill_end)) { + return false; + } else { + return true; + } + case PORT_SRC_TO_PORT_SINK: + return (cursor < site_arch->output_site_ports.size()); + case OUT_OF_SITE_SOURCES: + return (cursor < site_arch->out_of_site_sources.size()); + case OUT_OF_SITE_SINK_TO_PORT_SINK: + return (cursor < site_arch->output_site_ports.size()); + case SITE_PORT: + return true; + case END: + return true; + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + const std::array<std::array<UphillIteratorState, NUMBER_STATES>, SiteWire::NUMBER_SITE_WIRE_TYPES> + get_state_table() const + { + std::array<std::array<UphillIteratorState, NUMBER_STATES>, SiteWire::NUMBER_SITE_WIRE_TYPES> state_table; + for (size_t j = 0; j < SiteWire::NUMBER_SITE_WIRE_TYPES; ++j) { + for (size_t i = 0; i < NUMBER_STATES; ++i) { + state_table[j][i] = NUMBER_STATES; + } + } + + state_table[SiteWire::SITE_WIRE][BEGIN] = NORMAL_PIPS; + state_table[SiteWire::SITE_WIRE][NORMAL_PIPS] = END; + + state_table[SiteWire::OUT_OF_SITE_SOURCE][BEGIN] = END; + + state_table[SiteWire::OUT_OF_SITE_SINK][BEGIN] = OUT_OF_SITE_SINK_TO_PORT_SINK; + state_table[SiteWire::OUT_OF_SITE_SINK][OUT_OF_SITE_SINK_TO_PORT_SINK] = END; + + state_table[SiteWire::SITE_PORT_SINK][BEGIN] = SITE_PORT; + state_table[SiteWire::SITE_PORT_SINK][SITE_PORT] = END; + + state_table[SiteWire::SITE_PORT_SOURCE][BEGIN] = PORT_SRC_TO_PORT_SINK; + state_table[SiteWire::SITE_PORT_SOURCE][PORT_SRC_TO_PORT_SINK] = OUT_OF_SITE_SOURCES; + state_table[SiteWire::SITE_PORT_SOURCE][OUT_OF_SITE_SOURCES] = END; + + return state_table; + } + + void advance_state() + { + state = get_state_table().at(site_wire.type).at(state); + cursor = 0; + NPNR_ASSERT(state >= BEGIN && state <= END); + } + + void operator++() + { + NPNR_ASSERT(state != END); + while (state != END) { + if (advance_in_state()) { + break; + } else { + advance_state(); + if (check_first()) { + break; + } + } + } + } + + bool operator!=(const SitePipUphillIterator &other) const + { + return state != other.state || cursor != other.cursor || iter != other.iter; + } + + SitePip operator*() const; +}; + +struct SitePipUphillRange +{ + const SiteArch *site_arch; + SiteWire site_wire; + UphillPipRange pip_range; + + SitePipUphillRange(const SiteArch *site_arch, SiteWire site_wire); + + SitePipUphillIterator begin() const + { + SitePipUphillIterator b; + b.state = SitePipUphillIterator::BEGIN; + b.site_arch = site_arch; + b.site_wire = site_wire; + b.cursor = 0; + b.iter = pip_range.b; + b.uphill_end = pip_range.e; + + ++b; + + return b; + } + + SitePipUphillIterator end() const + { + SitePipUphillIterator e; + e.state = SitePipUphillIterator::END; + e.site_arch = site_arch; + e.site_wire = site_wire; + e.cursor = 0; + e.iter = pip_range.e; + e.uphill_end = pip_range.e; + + return e; + } +}; + +inline SitePipDownhillRange SiteArch::getPipsDownhill(const SiteWire &site_wire) const +{ + return SitePipDownhillRange(this, site_wire); +} + +inline SitePipUphillRange SiteArch::getPipsUphill(const SiteWire &site_wire) const +{ + return SitePipUphillRange(this, site_wire); +} + +struct SiteWireIterator +{ + enum SiteWireIteratorState + { + // Initial state + BEGIN = 0, + NORMAL_WIRES = 1, + INPUT_SITE_PORTS = 2, + OUTPUT_SITE_PORTS = 3, + OUT_OF_SITE_SOURCES = 4, + OUT_OF_SITE_SINKS = 5, + END = 6, + }; + + SiteWireIteratorState state = BEGIN; + const SiteArch *site_arch; + const TileTypeInfoPOD *tile_type; + size_t cursor = 0; + + bool advance_in_state() + { + switch (state) { + case BEGIN: + return false; + case NORMAL_WIRES: + while (true) { + ++cursor; + if (cursor >= tile_type->wire_data.size()) { + return false; + } + if (tile_type->wire_data[cursor].site == site_arch->site_info->site) { + return true; + } + } + case INPUT_SITE_PORTS: + ++cursor; + return (cursor < site_arch->input_site_ports.size()); + case OUTPUT_SITE_PORTS: + ++cursor; + return (cursor < site_arch->output_site_ports.size()); + case OUT_OF_SITE_SOURCES: + ++cursor; + return (cursor < site_arch->out_of_site_sources.size()); + case OUT_OF_SITE_SINKS: + ++cursor; + return (cursor < site_arch->out_of_site_sinks.size()); + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + // See if initial value in state is good. + bool check_first() const + { + switch (state) { + case BEGIN: + return false; + case NORMAL_WIRES: + if (cursor >= tile_type->wire_data.size()) { + return false; + } + return tile_type->wire_data[cursor].site == site_arch->site_info->site; + case INPUT_SITE_PORTS: + return (cursor < site_arch->input_site_ports.size()); + case OUTPUT_SITE_PORTS: + return (cursor < site_arch->output_site_ports.size()); + case OUT_OF_SITE_SOURCES: + return (cursor < site_arch->out_of_site_sources.size()); + case OUT_OF_SITE_SINKS: + return (cursor < site_arch->out_of_site_sinks.size()); + case END: + return true; + default: + // Unreachable! + NPNR_ASSERT(false); + } + } + + void advance_state() + { + NPNR_ASSERT(state >= BEGIN && state < END); + state = static_cast<SiteWireIteratorState>(state + 1); + cursor = 0; + NPNR_ASSERT(state >= BEGIN && state <= END); + } + + void operator++() + { + NPNR_ASSERT(state != END); + while (state != END) { + if (advance_in_state()) { + break; + } else { + advance_state(); + if (check_first()) { + break; + } + } + } + } + + bool operator!=(const SiteWireIterator &other) const { return state != other.state || cursor != other.cursor; } + + SiteWire operator*() const; +}; + +struct SiteWireRange +{ + const SiteArch *site_arch; + SiteWireRange(const SiteArch *site_arch) : site_arch(site_arch) {} + SiteWireIterator begin() const; + + SiteWireIterator end() const + { + SiteWireIterator e; + + e.state = SiteWireIterator::END; + + return e; + } +}; + +inline SiteWireRange SiteArch::getWires() const { return SiteWireRange(this); } + +NEXTPNR_NAMESPACE_END + +#endif /* SITE_ARCH_H */ diff --git a/fpga_interchange/site_arch.impl.h b/fpga_interchange/site_arch.impl.h new file mode 100644 index 00000000..4702b592 --- /dev/null +++ b/fpga_interchange/site_arch.impl.h @@ -0,0 +1,255 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SITE_ARCH_IMPL_H +#define SITE_ARCH_IMPL_H + +#include "context.h" +#include "site_arch.h" + +NEXTPNR_NAMESPACE_BEGIN + +inline const ChipInfoPOD &SiteInformation::chip_info() const { return *ctx->chip_info; } + +inline bool SiteInformation::is_wire_in_site(WireId wire) const +{ + if (wire.tile != tile) { + return false; + } + + return ctx->wire_info(wire).site == site; +} + +inline bool SiteInformation::is_bel_in_site(BelId bel) const +{ + if (bel.tile != tile) { + return false; + } + + return bel_info(ctx->chip_info, bel).site == site; +} + +inline bool SiteInformation::is_pip_part_of_site(PipId pip) const +{ + if (pip.tile != tile) { + return false; + } + + const auto &tile_type_data = ctx->chip_info->tile_types[tile_type]; + const auto &pip_data = tile_type_data.pip_data[pip.index]; + return pip_data.site == site; +} + +inline bool SiteInformation::is_site_port(PipId pip) const +{ + const auto &tile_type_data = ctx->chip_info->tile_types[tile_type]; + const auto &pip_data = tile_type_data.pip_data[pip.index]; + if (pip_data.site == -1) { + return false; + } + auto &bel_data = tile_type_data.bel_data[pip_data.bel]; + return bel_data.category == BEL_CATEGORY_SITE_PORT; +} + +inline SiteWire SiteWire::make(const SiteInformation *site_info, WireId site_wire) +{ + NPNR_ASSERT(site_info->is_wire_in_site(site_wire)); + SiteWire out; + out.type = SITE_WIRE; + out.wire = site_wire; + return out; +} + +inline SiteWire SiteWire::make_site_port(const SiteInformation *site_info, PipId pip, bool dst_wire) +{ + const auto &tile_type_data = site_info->chip_info().tile_types[site_info->tile_type]; + const auto &pip_data = tile_type_data.pip_data[pip.index]; + + // This pip should definitely be part of this site + NPNR_ASSERT(pip_data.site == site_info->site); + + SiteWire out; + + const auto &src_data = tile_type_data.wire_data[pip_data.src_index]; + const auto &dst_data = tile_type_data.wire_data[pip_data.dst_index]; + + if (dst_wire) { + if (src_data.site == site_info->site) { + NPNR_ASSERT(dst_data.site == -1); + out.type = SITE_PORT_SINK; + out.pip = pip; + out.wire = canonical_wire(&site_info->chip_info(), pip.tile, pip_data.dst_index); + } else { + NPNR_ASSERT(src_data.site == -1); + NPNR_ASSERT(dst_data.site == site_info->site); + out.type = SITE_WIRE; + out.wire.tile = pip.tile; + out.wire.index = pip_data.dst_index; + } + } else { + if (src_data.site == site_info->site) { + NPNR_ASSERT(dst_data.site == -1); + out.type = SITE_WIRE; + out.wire.tile = pip.tile; + out.wire.index = pip_data.src_index; + } else { + NPNR_ASSERT(src_data.site == -1); + NPNR_ASSERT(dst_data.site == site_info->site); + out.type = SITE_PORT_SOURCE; + out.pip = pip; + out.wire = canonical_wire(&site_info->chip_info(), pip.tile, pip_data.src_index); + } + } + + return out; +} + +inline SitePip SitePip::make(const SiteInformation *site_info, PipId pip) +{ + SitePip out; + out.pip = pip; + + if (site_info->is_site_port(pip)) { + out.type = SITE_PORT; + } else { + out.type = SITE_PIP; + } + return out; +} + +inline SiteWire SiteArch::getPipSrcWire(const SitePip &site_pip) const +{ + SiteWire site_wire; + switch (site_pip.type) { + case SitePip::Type::SITE_PIP: + return SiteWire::make(site_info, ctx->getPipSrcWire(site_pip.pip)); + case SitePip::Type::SITE_PORT: + return SiteWire::make_site_port(site_info, site_pip.pip, /*dst_wire=*/false); + case SitePip::Type::SOURCE_TO_SITE_PORT: + NPNR_ASSERT(site_pip.wire.type == SiteWire::OUT_OF_SITE_SOURCE); + return site_pip.wire; + case SitePip::Type::SITE_PORT_TO_SINK: + site_wire = SiteWire::make_site_port(site_info, site_pip.pip, /*dst_wire=*/true); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SINK); + return site_wire; + case SitePip::Type::SITE_PORT_TO_SITE_PORT: + site_wire = SiteWire::make_site_port(site_info, site_pip.pip, /*dst_wire=*/true); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SINK); + return site_wire; + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +inline SiteWire SiteArch::getPipDstWire(const SitePip &site_pip) const +{ + switch (site_pip.type) { + case SitePip::Type::SITE_PIP: + return SiteWire::make(site_info, ctx->getPipDstWire(site_pip.pip)); + case SitePip::Type::SITE_PORT: + return SiteWire::make_site_port(site_info, site_pip.pip, /*dst_wire=*/true); + case SitePip::Type::SOURCE_TO_SITE_PORT: { + SiteWire site_wire = SiteWire::make_site_port(site_info, site_pip.pip, /*dst_wire=*/false); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SOURCE); + return site_wire; + } + case SitePip::Type::SITE_PORT_TO_SINK: + NPNR_ASSERT(site_pip.wire.type == SiteWire::OUT_OF_SITE_SINK); + return site_pip.wire; + case SitePip::Type::SITE_PORT_TO_SITE_PORT: { + SiteWire site_wire = SiteWire::make_site_port(site_info, site_pip.other_pip, /*dst_wire=*/false); + NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SOURCE); + return site_wire; + } + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +inline bool SiteArch::is_pip_synthetic(const SitePip &pip) const +{ + if (pip.type != SitePip::SITE_PORT) { + // This isn't a site port, so its valid! + return false; + } + + auto &tile_type = ctx->chip_info->tile_types[site_info->tile_type]; + auto &pip_data = tile_type.pip_data[pip.pip.index]; + if (pip_data.site == -1) { + return pip_data.extra_data == -1; + } else { + auto &bel_data = tile_type.bel_data[pip_data.bel]; + return bel_data.synthetic != 0; + } +} + +inline SitePip SitePipDownhillIterator::operator*() const +{ + switch (state) { + case NORMAL_PIPS: { + PipId pip; + pip.tile = site_arch->site_info->tile; + pip.index = (*pips_downhill)[cursor]; + return SitePip::make(site_arch->site_info, pip); + } + case PORT_SINK_TO_PORT_SRC: + return SitePip::make(site_arch->site_info, site_wire.pip, site_arch->input_site_ports.at(cursor)); + case OUT_OF_SITE_SINKS: + return SitePip::make(site_arch->site_info, site_wire.pip, site_arch->out_of_site_sinks.at(cursor)); + case OUT_OF_SITE_SOURCE_TO_PORT_SRC: + return SitePip::make(site_arch->site_info, site_wire, site_arch->input_site_ports.at(cursor)); + case SITE_PORT: + return SitePip::make(site_arch->site_info, site_wire.pip); + default: + // Unreachable! + NPNR_ASSERT(false); + } +} + +inline const RelSlice<int32_t> *SitePipDownhillRange::init_pip_range() const +{ + NPNR_ASSERT(site_wire.type == SiteWire::SITE_WIRE); + NPNR_ASSERT(site_wire.wire.tile == site_arch->site_info->tile); + return &site_arch->ctx->chip_info->tile_types[site_arch->site_info->tile_type] + .wire_data[site_wire.wire.index] + .pips_downhill; +} + +inline SitePipDownhillIterator SitePipDownhillRange::begin() const +{ + SitePipDownhillIterator b; + b.state = SitePipDownhillIterator::BEGIN; + b.site_arch = site_arch; + b.site_wire = site_wire; + b.cursor = 0; + if (site_wire.type == SiteWire::SITE_WIRE) { + b.pips_downhill = init_pip_range(); + } + + ++b; + + return b; +} + +NEXTPNR_NAMESPACE_END + +#endif /* SITE_ARCH_H */ diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 9d4fc57c..c470f3f6 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -17,13 +17,23 @@ * */ -#include "log.h" #include "nextpnr.h" +#include "dynamic_bitarray.h" +#include "log.h" +#include "site_routing_cache.h" + +#include "hash_table.h" + +#include "site_arch.h" +#include "site_arch.impl.h" + NEXTPNR_NAMESPACE_BEGIN bool verbose_site_router(const Context *ctx) { return ctx->debug; } +bool verbose_site_router(const SiteArch *ctx) { return verbose_site_router(ctx->ctx); } + void SiteRouter::bindBel(CellInfo *cell) { auto result = cells_in_site.emplace(cell); @@ -39,669 +49,597 @@ void SiteRouter::unbindBel(CellInfo *cell) dirty = true; } -struct RouteNode +bool check_initial_wires(const Context *ctx, SiteInformation *site_info) { - void clear() - { - parent = std::list<RouteNode>::iterator(); - leafs.clear(); - pip = PipId(); - wire = WireId(); - } - - using Node = std::list<RouteNode>::iterator; + // Propagate from BEL pins to first wire, checking for trivial routing + // conflicts. + HashTables::HashMap<WireId, NetInfo *> wires; - Node parent; - std::vector<Node> leafs; - - PipId pip; // What pip was taken to reach this node. - WireId wire; // What wire is this routing node located at? - - void print_route(const Context *ctx) const - { - log_info(" %s (via %s)\n", ctx->nameOfWire(wire), ctx->nameOfPip(pip)); + for (CellInfo *cell : site_info->cells_in_site) { + BelId bel = cell->bel; + for (const auto &pin_pair : cell->cell_bel_pins) { + const PortInfo &port = cell->ports.at(pin_pair.first); + NPNR_ASSERT(port.net != nullptr); + + for (IdString bel_pin_name : pin_pair.second) { + BelPin bel_pin; + bel_pin.bel = bel; + bel_pin.pin = bel_pin_name; + + WireId wire = ctx->getBelPinWire(bel_pin.bel, bel_pin.pin); + auto result = wires.emplace(wire, port.net); + if (!result.second) { + // This wire is already in use, make sure the net bound is + // the same net, otherwise there is a trivial net + // conflict. + const NetInfo *other_net = result.first->second; + if (other_net != port.net) { + // We have a direct net conflict at the BEL pin, + // immediately short circuit the site routing check. + if (verbose_site_router(ctx)) { + log_info("Direct net conflict detected for cell %s:%s at bel %s, net %s != %s\n", + cell->name.c_str(ctx), cell->type.c_str(ctx), ctx->nameOfBel(cell->bel), + port.net->name.c_str(ctx), other_net->name.c_str(ctx)); + } - Node node = parent; - while (node != RouteNode::Node()) { - if (node->pip != PipId()) { - log_info(" %s (via %s)\n", ctx->nameOfWire(node->wire), ctx->nameOfPip(node->pip)); - } else { - log_info(" %s\n", ctx->nameOfWire(node->wire)); + return false; + } + } } - - node = node->parent; } } -}; - -struct RouteNodeStorage -{ - // Free list of nodes. - std::list<RouteNode> nodes; - - // Either allocate a new node if no nodes are on the free list, or return - // an element from the free list. - std::list<RouteNode>::iterator alloc_node(std::list<RouteNode> &new_owner) - { - if (nodes.empty()) { - nodes.emplace_front(RouteNode()); - } - - auto ret = nodes.begin(); - new_owner.splice(new_owner.end(), nodes, ret); - ret->clear(); + return true; +} - return ret; +bool is_invalid_site_port(const SiteArch *ctx, const SiteNetInfo *net, const SitePip &pip) +{ + if (ctx->is_pip_synthetic(pip)) { + // FIXME: Not all synthetic pips are for constant networks. + // FIXME: Need to mark if synthetic site ports are for the GND or VCC + // network, and only allow the right one. Otherwise site router + // could route a VCC on a GND only net (or equiv). + IdString gnd_net_name(ctx->ctx->chip_info->constants->gnd_net_name); + IdString vcc_net_name(ctx->ctx->chip_info->constants->vcc_net_name); + return net->net->name != gnd_net_name && net->net->name != vcc_net_name; + } else { + // All non-synthetic site ports are valid + return false; } +} - // Return 1 node from the current owner to the free list. - void free_node(std::list<RouteNode> &owner, std::list<RouteNode>::iterator node) - { - nodes.splice(nodes.end(), owner, node); - } +struct SiteExpansionLoop +{ + RouteNodeStorage *const node_storage; - // Return all node from the current owner to the free list. - void free_nodes(std::list<RouteNode> &owner) + SiteExpansionLoop(RouteNodeStorage *node_storage) : node_storage(node_storage) { - nodes.splice(nodes.end(), owner); - NPNR_ASSERT(owner.empty()); + NPNR_ASSERT(node_storage != nullptr); } -}; - -struct SiteInformation -{ - const Context *ctx; - const std::unordered_set<CellInfo *> &cells_in_site; - - SiteInformation(const Context *ctx, const std::unordered_set<CellInfo *> &cells_in_site) - : ctx(ctx), cells_in_site(cells_in_site) + void clear() { + node_storage->free_nodes(used_nodes); + used_nodes.clear(); + solution.clear(); + net_driver = SiteWire(); } - bool check_bel_pin(CellInfo *cell, const PortInfo &port_info, BelPin bel_pin) - { - WireId wire = ctx->getBelPinWire(bel_pin.bel, bel_pin.pin); - auto result = consumed_wires.emplace(wire, port_info.net); - if (!result.second) { - // This wire is already in use, make sure the net bound is - // the same net, otherwise there is a net conflict. - const NetInfo *other_net = result.first->second; - if (other_net != port_info.net) { - // We have a direct net conflict at the BEL pin, - // immediately short circuit the site routing check. - if (verbose_site_router(ctx)) { - log_info("Direct net conflict detected for cell %s:%s at bel %s, net %s != %s\n", - cell->name.c_str(ctx), cell->type.c_str(ctx), ctx->nameOfBel(cell->bel), - port_info.net->name.c_str(ctx), other_net->name.c_str(ctx)); - } - return false; - } - } + virtual ~SiteExpansionLoop() { node_storage->free_nodes(used_nodes); } - nets_in_site.emplace(port_info.net); + // Storage for nodes + std::vector<size_t> used_nodes; - if (port_info.type == PORT_OUT) { - unrouted_source_wires.emplace(wire, std::unordered_set<WireId>()); - } else { - unrouted_sink_wires.emplace(wire); - } + bool expand_result; + SiteWire net_driver; + HashTables::HashSet<SiteWire> net_users; - return true; - } + SiteRoutingSolution solution; - bool check_initial_wires() + Node new_node(const SiteWire &wire, const SitePip &pip, const Node *parent) { - // Propagate from BEL pins to first wire, checking for trivial routing - // conflicts. - // - // Populate initial consumed wires, and nets_in_site. - for (CellInfo *cell : cells_in_site) { - BelId bel = cell->bel; - for (const auto &pin_pair : cell->cell_bel_pins) { - const PortInfo &port = cell->ports.at(pin_pair.first); - for (IdString bel_pin_name : pin_pair.second) { - BelPin bel_pin; - bel_pin.bel = bel; - bel_pin.pin = bel_pin_name; - - if (!check_bel_pin(cell, port, bel_pin)) { - return false; - } + Node node = node_storage->alloc_node(); + used_nodes.push_back(node.get_index()); + + node->wire = wire; + node->pip = pip; + if (parent != nullptr) { + node->parent = (*parent).get_index(); + node->flags = (*parent)->flags; + node->depth = (*parent)->depth + 1; + } + + if (pip.type == SitePip::SITE_PORT) { + // Site ports should always have a parent! + NPNR_ASSERT(parent != nullptr); + if (wire.type == SiteWire::SITE_PORT_SINK) { + NPNR_ASSERT((*parent)->wire.type == SiteWire::SITE_WIRE); + NPNR_ASSERT(node->can_leave_site()); + node->mark_left_site(); + } else if (wire.type == SiteWire::SITE_PORT_SOURCE) { + // This is a backward walk, so this is considered entering + // the site. + NPNR_ASSERT((*parent)->wire.type == SiteWire::SITE_WIRE); + NPNR_ASSERT(node->can_enter_site()); + node->mark_entered_site(); + } else { + // See if this is a forward or backward walk. + NPNR_ASSERT(wire.type == SiteWire::SITE_WIRE); + if ((*parent)->wire.type == SiteWire::SITE_PORT_SINK) { + // This is a backward walk, so this is considered leaving + // the site. + NPNR_ASSERT(node->can_leave_site()); + node->mark_left_site(); + } else { + NPNR_ASSERT((*parent)->wire.type == SiteWire::SITE_PORT_SOURCE); + NPNR_ASSERT(node->can_enter_site()); + node->mark_entered_site(); } } } - // Populate nets_fully_within_site - for (const NetInfo *net : nets_in_site) { - if (ctx->is_net_within_site(*net)) { - nets_fully_within_site.emplace(net); - } - } + return node; + } - // Remove sinks that are trivially routed. - std::vector<WireId> trivially_routed_sinks; - for (WireId sink_wire : unrouted_sink_wires) { - if (unrouted_source_wires.count(sink_wire) > 0) { - if (verbose_site_router(ctx)) { - log_info("Wire %s is trivially routed!\n", ctx->nameOfWire(sink_wire)); - } - trivially_routed_sinks.push_back(sink_wire); - } + // Expand from wire specified, always downhill. + bool expand_net(const SiteArch *ctx, SiteRoutingCache *site_routing_cache, const SiteNetInfo *net) + { + if (net->driver == net_driver && net->users == net_users) { + return expand_result; } - for (WireId sink_wire : trivially_routed_sinks) { - NPNR_ASSERT(unrouted_sink_wires.erase(sink_wire) == 1); - } + clear(); - // Remove sources that are routed now that trivially routed sinks are - // removed. - std::unordered_set<WireId> trivially_routed_sources; - for (const NetInfo *net : nets_fully_within_site) { - std::unordered_set<WireId> sink_wires_in_net; - bool already_routed = true; - for (const PortRef &user : net->users) { - for (const IdString pin : user.cell->cell_bel_pins.at(user.port)) { - WireId sink_wire = ctx->getBelPinWire(user.cell->bel, pin); - if (unrouted_sink_wires.count(sink_wire) > 0) { - sink_wires_in_net.emplace(sink_wire); - already_routed = false; - } - } - } + net_driver = net->driver; + net_users = net->users; - if (already_routed) { - for (const IdString pin : net->driver.cell->cell_bel_pins.at(net->driver.port)) { - trivially_routed_sources.emplace(ctx->getBelPinWire(net->driver.cell->bel, pin)); - } - } else { - for (const IdString pin : net->driver.cell->cell_bel_pins.at(net->driver.port)) { - WireId source_wire = ctx->getBelPinWire(net->driver.cell->bel, pin); - unrouted_source_wires.at(source_wire) = sink_wires_in_net; - } - } + if (site_routing_cache->get_solution(ctx, *net, &solution)) { + expand_result = true; + return expand_result; } - for (WireId source_wire : trivially_routed_sources) { - NPNR_ASSERT(unrouted_source_wires.erase(source_wire) == 1); + if (verbose_site_router(ctx)) { + log_info("Expanding net %s from %s\n", ctx->nameOfNet(net), ctx->nameOfWire(net->driver)); } - return true; - } - - // Checks if a source wire has been fully routed. - // - // Returns false if this wire is not an unrouted source wire. - bool check_source_routed(WireId wire) const - { - if (unrouted_source_wires.count(wire)) { - bool fully_routed = true; - for (WireId sink_wire : unrouted_source_wires.at(wire)) { - if (unrouted_sink_wires.count(sink_wire)) { - fully_routed = false; - } - } + auto node = new_node(net->driver, SitePip(), /*parent=*/nullptr); - return fully_routed; - } else { - return false; - } - } + HashTables::HashSet<SiteWire> targets; + targets.insert(net->users.begin(), net->users.end()); - // Removes an source wires that have been fully routed. - void remove_routed_sources() - { - std::vector<WireId> routed_wires; - for (auto &source_pair : unrouted_source_wires) { - if (check_source_routed(source_pair.first)) { - routed_wires.push_back(source_pair.first); + if (verbose_site_router(ctx)) { + log_info("%zu targets:\n", targets.size()); + for (auto &target : targets) { + log_info(" - %s\n", ctx->nameOfWire(target)); } } - for (WireId wire : routed_wires) { - NPNR_ASSERT(unrouted_source_wires.erase(wire) == 1); - } - } + int32_t max_depth = 0; + int32_t max_depth_seen = 0; + std::vector<Node> nodes_to_expand; + nodes_to_expand.push_back(node); - bool is_fully_routed() const { return unrouted_sink_wires.empty() && unrouted_source_wires.empty(); } + std::vector<size_t> completed_routes; + while (!nodes_to_expand.empty()) { + Node parent_node = nodes_to_expand.back(); + nodes_to_expand.pop_back(); - bool select_route(WireId first_wire, RouteNode::Node node, const NetInfo *net, - std::unordered_set<WireId> *newly_consumed_wires) - { + max_depth_seen = std::max(max_depth_seen, parent_node->depth); - bool is_last_pip_site_port = ctx->is_site_port(node->pip); - do { - auto result = consumed_wires.emplace(node->wire, net); - if (!result.second && result.first->second != net) { - // Conflict, this wire is already in use and it's not - // doesn't match! - if (verbose_site_router(ctx)) { - log_info("Cannot select route because net %s != net %s\n", result.first->second->name.c_str(ctx), - net->name.c_str(ctx)); + for (SitePip pip : ctx->getPipsDownhill(parent_node->wire)) { + if (is_invalid_site_port(ctx, net, pip)) { + if (verbose_site_router(ctx)) { + log_info("Pip %s is not a valid site port for net %s, skipping\n", ctx->nameOfPip(pip), + ctx->nameOfNet(net)); + } + continue; } - return false; - } - - // By selecting a route, other sinks are potentially now routed. - unrouted_sink_wires.erase(node->wire); - - newly_consumed_wires->emplace(node->wire); + SiteWire wire = ctx->getPipDstWire(pip); + + if (pip.type == SitePip::SITE_PORT) { + if (wire.type == SiteWire::SITE_PORT_SINK) { + if (!parent_node->can_leave_site()) { + // This path has already left the site once, don't leave it again! + if (verbose_site_router(ctx)) { + log_info("Pip %s is not a valid for this path because it has already left the site\n", + ctx->nameOfPip(pip)); + } + continue; + } + } else { + NPNR_ASSERT(parent_node->wire.type == SiteWire::SITE_PORT_SOURCE); + + if (!parent_node->can_enter_site()) { + // This path has already entered the site once, + // don't enter it again! + if (verbose_site_router(ctx)) { + log_info( + "Pip %s is not a valid for this path because it has already entered the site\n", + ctx->nameOfPip(pip)); + } + continue; + } + } + } - node = node->parent; - } while (node != RouteNode::Node()); + auto wire_iter = ctx->wire_to_nets.find(wire); + if (wire_iter != ctx->wire_to_nets.end() && wire_iter->second.net != net) { + if (verbose_site_router(ctx)) { + log_info("Wire %s is already tied to net %s, not exploring for net %s\n", ctx->nameOfWire(wire), + ctx->nameOfNet(wire_iter->second.net), ctx->nameOfNet(net)); + } + continue; + } - if (unrouted_source_wires.count(first_wire)) { - // By selecting a route to a site pip, this source wire is routed. - if (is_last_pip_site_port) { - NPNR_ASSERT(unrouted_source_wires.erase(first_wire)); - } else if (is_net_within_site(net)) { - // For nets that are completely contained within the site, it - // is possible that by selecting this route it is now fully - // routed. Check now. - if (check_source_routed(first_wire)) { - NPNR_ASSERT(unrouted_source_wires.erase(first_wire)); + auto node = new_node(wire, pip, &parent_node); + if (targets.count(wire)) { + completed_routes.push_back(node.get_index()); + max_depth = std::max(max_depth, node->depth); } + + nodes_to_expand.push_back(node); } } - return true; - } + // Make sure expansion reached all targets, otherwise this site is + // already unroutable! + solution.clear(); + solution.store_solution(ctx, node_storage, net->driver, completed_routes); + solution.verify(ctx, *net); + for (size_t route : completed_routes) { + SiteWire wire = node_storage->get_node(route)->wire; + targets.erase(wire); + } - // Map of currently occupied wires and their paired net. - std::unordered_map<WireId, const NetInfo *> consumed_wires; + if (targets.empty()) { + site_routing_cache->add_solutions(ctx, *net, solution); + } - // Set of nets in site - std::unordered_set<const NetInfo *> nets_in_site; + // Return nodes back to the storage system. + node_storage->free_nodes(used_nodes); + used_nodes.clear(); - // Map from source wire to sink wires within this site. - // If all sink wires are routed, the source is also routed! - std::unordered_map<WireId, std::unordered_set<WireId>> unrouted_source_wires; - std::unordered_set<WireId> unrouted_sink_wires; + expand_result = targets.empty(); + return expand_result; + } - // Set of nets are fully contained within the site. - std::unordered_set<const NetInfo *> nets_fully_within_site; + size_t num_solutions() const { return solution.num_solutions(); } - bool is_net_within_site(const NetInfo *net) const { return nets_fully_within_site.count(net); } + const SiteWire &solution_sink(size_t idx) const { return solution.solution_sink(idx); } + std::vector<SitePip>::const_iterator solution_begin(size_t idx) const { return solution.solution_begin(idx); } - void print_current_state() const; + std::vector<SitePip>::const_iterator solution_end(size_t idx) const { return solution.solution_end(idx); } }; -struct SiteExpansionLoop +void print_current_state(const SiteArch *site_arch) { - const Context *const ctx; - RouteNodeStorage *const node_storage; + const Context *ctx = site_arch->ctx; + auto &cells_in_site = site_arch->site_info->cells_in_site; + const CellInfo *cell = *cells_in_site.begin(); + BelId bel = cell->bel; + const auto &bel_data = bel_info(ctx->chip_info, bel); + const auto &site_inst = site_inst_info(ctx->chip_info, bel.tile, bel_data.site); - using Node = RouteNode::Node; + log_info("Site %s\n", site_inst.name.get()); - SiteExpansionLoop(const Context *ctx, RouteNodeStorage *node_storage) : ctx(ctx), node_storage(node_storage) - { - NPNR_ASSERT(node_storage != nullptr); + log_info(" Cells in site:\n"); + for (CellInfo *cell : cells_in_site) { + log_info(" - %s (%s)\n", cell->name.c_str(ctx), cell->type.c_str(ctx)); } - ~SiteExpansionLoop() { node_storage->free_nodes(nodes); } - - // Storage for nodes - std::list<RouteNode> nodes; - - WireId first_wire; - const NetInfo *net_for_wire; - std::unordered_map<RouteNode *, Node> completed_routes; - std::unordered_map<WireId, std::vector<Node>> wire_to_nodes; - - Node new_node(WireId wire, PipId pip, Node parent) - { - auto node = node_storage->alloc_node(nodes); - node->wire = wire; - node->pip = pip; - node->parent = parent; + log_info(" Nets in site:\n"); + for (auto &net_pair : site_arch->nets) { + auto *net = net_pair.first; + log_info(" - %s, pins in site:\n", net->name.c_str(ctx)); + if (net->driver.cell && cells_in_site.count(net->driver.cell)) { + log_info(" - %s/%s (%s)\n", net->driver.cell->name.c_str(ctx), net->driver.port.c_str(ctx), + net->driver.cell->type.c_str(ctx)); + } - return node; + for (const auto user : net->users) { + if (user.cell && cells_in_site.count(user.cell)) { + log_info(" - %s/%s (%s)\n", user.cell->name.c_str(ctx), user.port.c_str(ctx), + user.cell->type.c_str(ctx)); + } + } } - void free_node(Node node) { node_storage->free_node(nodes, node); } + log_info(" Consumed wires:\n"); + for (auto &wire_pair : site_arch->wire_to_nets) { + const SiteWire &site_wire = wire_pair.first; + if (site_wire.type != SiteWire::SITE_WIRE) { + continue; + } + WireId wire = site_wire.wire; + const NetInfo *net = wire_pair.second.net->net; + log_info(" - %s is bound to %s\n", ctx->nameOfWire(wire), net->name.c_str(ctx)); + } +} - // Expand from wire specified, either downhill or uphill. - // - // Expands until it reaches another net of it's own (e.g. source to sink - // within site) or a site port (e.g. out to routing network). - void expand(WireId wire, const SiteInformation *site_info) - { +struct PossibleSolutions +{ + bool tested = false; + SiteNetInfo *net = nullptr; + std::vector<SitePip>::const_iterator pips_begin; + std::vector<SitePip>::const_iterator pips_end; +}; - bool downhill = site_info->unrouted_source_wires.count(wire) != 0; - if (!downhill) { - NPNR_ASSERT(site_info->unrouted_sink_wires.count(wire) != 0); +bool test_solution(SiteArch *ctx, SiteNetInfo *net, std::vector<SitePip>::const_iterator pips_begin, + std::vector<SitePip>::const_iterator pips_end) +{ + bool valid = true; + std::vector<SitePip>::const_iterator good_pip_end = pips_begin; + for (auto iter = pips_begin; iter != pips_end; ++iter) { + if (!ctx->bindPip(*iter, net)) { + valid = false; + break; } - first_wire = wire; - net_for_wire = site_info->consumed_wires.at(first_wire); + good_pip_end = iter; + } - if (verbose_site_router(ctx)) { - log_info("Expanding net %s from %s\n", net_for_wire->name.c_str(ctx), ctx->nameOfWire(first_wire)); + // Unwind a bad solution + if (!valid) { + for (auto iter = pips_begin; iter != good_pip_end; ++iter) { + ctx->unbindPip(*iter); } + } else { + NPNR_ASSERT(net->driver == ctx->getPipSrcWire(*good_pip_end)); + } - completed_routes.clear(); - wire_to_nodes.clear(); - node_storage->free_nodes(nodes); + return valid; +} - auto node = new_node(first_wire, PipId(), /*parent=*/Node()); - wire_to_nodes[first_wire].push_back(node); +void remove_solution(SiteArch *ctx, std::vector<SitePip>::const_iterator pips_begin, + std::vector<SitePip>::const_iterator pips_end) +{ + for (auto iter = pips_begin; iter != pips_end; ++iter) { + ctx->unbindPip(*iter); + } +} - std::vector<Node> nodes_to_expand; - nodes_to_expand.push_back(node); +static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolutions> *solutions, + const std::vector<std::vector<size_t>> &sinks_to_solutions) +{ + std::vector<uint8_t> routed_sinks; + std::vector<size_t> solution_indicies; + std::vector<std::pair<size_t, size_t>> solution_order; + routed_sinks.resize(sinks_to_solutions.size(), 0); + solution_indicies.resize(sinks_to_solutions.size(), 0); + + // Scan solutions, and remove any solutions that are invalid immediately + for (auto &solution : *solutions) { + if (test_solution(ctx, solution.net, solution.pips_begin, solution.pips_end)) { + remove_solution(ctx, solution.pips_begin, solution.pips_end); + } else { + solution.tested = true; + } + } - auto do_expand = [&](Node parent_node, PipId pip, WireId wire) { - if (wire == first_wire) { - // No simple loops - // FIXME: May need to detect more complicated loops! - return; + for (size_t sink_idx = 0; sink_idx < sinks_to_solutions.size(); ++sink_idx) { + size_t solution_count = 0; + for (size_t solution_idx : sinks_to_solutions[sink_idx]) { + if (!(*solutions)[solution_idx].tested) { + solution_count += 1; } + } - if (ctx->is_site_port(pip)) { - if (verbose_site_router(ctx)) { - log_info("Expanded net %s reaches %s\n", net_for_wire->name.c_str(ctx), ctx->nameOfPip(pip)); - } - auto node = new_node(wire, pip, parent_node); - completed_routes.emplace(&*node, node); - return; - } + if (solution_count == 0) { + return false; + } - auto iter = site_info->consumed_wires.find(wire); - if (iter != site_info->consumed_wires.end()) { - // This wire already belongs to a net! - if (iter->second == net_for_wire) { - // If this wire is the same net, this is a valid complete - // route. - if (!downhill && site_info->unrouted_source_wires.count(wire)) { - // This path is from a sink to a source, it is a complete route. - auto node = new_node(wire, pip, parent_node); - if (verbose_site_router(ctx)) { - log_info("Expanded net %s reaches source %s\n", net_for_wire->name.c_str(ctx), - ctx->nameOfWire(wire)); - } - completed_routes.emplace(&*node, node); - } else if (downhill && site_info->is_net_within_site(net_for_wire)) { - // This path is from a sink to a source, it is a complete route to 1 sinks. - auto node = new_node(wire, pip, parent_node); - if (verbose_site_router(ctx)) { - log_info("Expanded net %s reaches sink %s\n", net_for_wire->name.c_str(ctx), - ctx->nameOfWire(wire)); - } - completed_routes.emplace(&*node, node); - } - } else { - // Net conflict, do not expand further. - return; - } - } + solution_order.emplace_back(sink_idx, solution_count); + } - // This wire is not a destination, and is not directly occupied, - // put it on the expansion list. - nodes_to_expand.push_back(new_node(wire, pip, parent_node)); - }; + // Sort solutions by the number of possible solutions first. This allows + // the backtrack to avoid the wide searches first. + std::sort(solution_order.begin(), solution_order.end(), + [](const std::pair<size_t, size_t> &a, const std::pair<size_t, size_t> &b) -> bool { + return a.second < b.second; + }); - while (!nodes_to_expand.empty()) { - Node node_to_expand = nodes_to_expand.back(); - nodes_to_expand.pop_back(); + std::vector<size_t> solution_stack; + solution_stack.reserve(sinks_to_solutions.size()); - if (downhill) { - for (PipId pip : ctx->getPipsDownhill(node_to_expand->wire)) { - WireId wire = ctx->getPipDstWire(pip); - do_expand(node_to_expand, pip, wire); + if (verbose_site_router(ctx)) { + log_info("Solving via backtrace with %zu solutions and %zu sinks\n", solutions->size(), + sinks_to_solutions.size()); + } + + // Simple backtrack explorer: + // - Apply the next solution at stack index. + // - If solution is valid, push solution onto stack, and advance stack + // index at solution 0. + // - If solution is not valid, pop the stack. + // - At this level of the stack, advance to the next solution. If + // there are not more solutions at this level, pop again. + // - If stack is now empty, mark root solution as tested and invalid. + // If root of stack has no more solutions, no solution is possible. + while (true) { + // Which sink is next to be tested? + size_t sink_idx = solution_order[solution_stack.size()].first; + + size_t next_solution_to_test = solution_indicies[sink_idx]; + if (next_solution_to_test >= sinks_to_solutions[sink_idx].size()) { + // We have exausted all solutions at this level of the stack! + if (solution_stack.empty()) { + // Search is done, failed!!! + if (verbose_site_router(ctx)) { + log_info("No solution found via backtrace with %zu solutions and %zu sinks\n", solutions->size(), + sinks_to_solutions.size()); } + return false; } else { - for (PipId pip : ctx->getPipsUphill(node_to_expand->wire)) { - WireId wire = ctx->getPipSrcWire(pip); - do_expand(node_to_expand, pip, wire); - } + // This level of the stack is completely tapped out, pop back + // to the next level up. + size_t solution_idx = solution_stack.back(); + solution_stack.pop_back(); + + // Remove the now tested bad solution at the previous level of + // the stack. + auto &solution = solutions->at(solution_idx); + remove_solution(ctx, solution.pips_begin, solution.pips_end); + + // Because we had to pop up the stack, advance the index at + // the level below us and start again. + sink_idx = solution_order[solution_stack.size()].first; + solution_indicies[sink_idx] += 1; + continue; } } - } - - // Remove any routes that use specified wire. - void remove_wire(WireId wire) - { - auto iter = wire_to_nodes.find(wire); - if (iter == wire_to_nodes.end()) { - // This wire was not in use, done! - return; - } - // We need to prune the tree of nodes starting from any node that - // uses the specified wire. Create a queue of nodes to follow to - // gather all nodes that need to be removed. - std::list<RouteNode> nodes_to_follow; - for (Node node : iter->second) { - nodes_to_follow.splice(nodes_to_follow.end(), nodes, node); + size_t solution_idx = sinks_to_solutions[sink_idx].at(next_solution_to_test); + auto &solution = solutions->at(solution_idx); + if (solution.tested) { + // This solution was already determined to be no good, skip it. + solution_indicies[sink_idx] += 1; + continue; } - // Follow all nodes to their end, mark that node to be eventually removed. - std::list<RouteNode> nodes_to_remove; - while (!nodes_to_follow.empty()) { - Node node = nodes_to_follow.begin(); - nodes_to_remove.splice(nodes_to_remove.end(), nodes_to_follow, node); - - for (Node child_node : node->leafs) { - nodes_to_follow.splice(nodes_to_follow.end(), nodes, child_node); + if (!test_solution(ctx, solution.net, solution.pips_begin, solution.pips_end)) { + // This solution was no good, try the next one at this level of + // the stack. + solution_indicies[sink_idx] += 1; + } else { + // This solution was good, push onto the stack. + solution_stack.push_back(solution_idx); + if (solution_stack.size() == sinks_to_solutions.size()) { + // Found a valid solution, done! + if (verbose_site_router(ctx)) { + log_info("Solved via backtrace with %zu solutions and %zu sinks\n", solutions->size(), + sinks_to_solutions.size()); + } + return true; + } else { + // Because we pushing to a new level of stack, restart the + // search at this level. + sink_idx = solution_order[solution_stack.size()].first; + solution_indicies[sink_idx] = 0; } } - - // Check if any nodes being removed are a completed route. - for (RouteNode &node : nodes_to_remove) { - completed_routes.erase(&node); - } - - // Move all nodes to be removed to the free list. - node_storage->free_nodes(nodes_to_remove); - NPNR_ASSERT(nodes_to_follow.empty()); - NPNR_ASSERT(nodes_to_remove.empty()); } -}; -bool route_site(const Context *ctx, SiteInformation *site_info) + // Unreachable!!! + NPNR_ASSERT(false); +} + +bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeStorage *node_storage) { - // All nets need to route: - // - From sources to an output site pin or sink wire. - // - From sink to an input site pin. + std::vector<SiteExpansionLoop *> expansions; + expansions.reserve(ctx->nets.size()); - std::unordered_set<WireId> unrouted_wires; + for (auto &net_pair : ctx->nets) { + SiteNetInfo *net = &net_pair.second; - for (auto wire_pair : site_info->unrouted_source_wires) { - auto result = unrouted_wires.emplace(wire_pair.first); - NPNR_ASSERT(result.second); - } - for (WireId wire : site_info->unrouted_sink_wires) { - auto result = unrouted_wires.emplace(wire); - if (!result.second) { - log_error("Found sink wire %s already in unrouted_wires set. unrouted_source_wires.count() == %zu\n", - ctx->nameOfWire(wire), site_info->unrouted_source_wires.count(wire)); + if (net->net->loop == nullptr) { + net->net->loop = new SiteExpansionLoop(node_storage); } - } + expansions.push_back(net->net->loop); - // All done! - if (unrouted_wires.empty()) { - return true; - } - - // Expand from first wires to all potential routes (either net pair or - // site pin). - RouteNodeStorage node_storage; - std::vector<SiteExpansionLoop> expansions; - expansions.reserve(unrouted_wires.size()); - - for (WireId wire : unrouted_wires) { - expansions.emplace_back(SiteExpansionLoop(ctx, &node_storage)); - - SiteExpansionLoop &wire_router = expansions.back(); - wire_router.expand(wire, site_info); + SiteExpansionLoop *router = expansions.back(); + if (!router->expand_net(ctx, site_routing_cache, net)) { + if (verbose_site_router(ctx)) { + log_info("Net %s expansion failed to reach all users, site is unroutable!\n", ctx->nameOfNet(net)); + } - // It is not possible to route this wire at all, fail early. - if (wire_router.completed_routes.empty()) { return false; } } - std::unordered_set<WireId> newly_consumed_wires; - std::unordered_map<WireId, SiteExpansionLoop *> wire_to_expansion; - for (auto &expansion : expansions) { - // This is a special case, where the expansion found exactly 1 solution. - // That solution must be conflict free, or the site is unroutable. - if (expansion.completed_routes.size() == 1) { - auto node = expansion.completed_routes.begin()->second; - if (!site_info->select_route(expansion.first_wire, node, expansion.net_for_wire, &newly_consumed_wires)) { - // Conflict! - return false; - } - } else { - auto result = wire_to_expansion.emplace(expansion.first_wire, &expansion); + // First convert remaining solutions into a flat solution set. + std::vector<PossibleSolutions> solutions; + HashTables::HashMap<SiteWire, size_t> sink_map; + std::vector<std::vector<size_t>> sinks_to_solutions; + for (const auto *expansion : expansions) { + for (const SiteWire &unrouted_sink : expansion->net_users) { + auto result = sink_map.emplace(unrouted_sink, sink_map.size()); NPNR_ASSERT(result.second); } } - if (wire_to_expansion.empty()) { - // All routes have been assigned with congestion! + if (sink_map.empty()) { + // All nets are trivially routed! return true; } - // At this point some expansions have multiple results. Build congestion - // information, and pick non-conflicted routes for remaining expansions. - std::vector<WireId> completed_wires; - do { - // Before anything, remove routes that have been consumed in previous - // iteration. - for (auto &expansion_wire : wire_to_expansion) { - auto &expansion = *expansion_wire.second; - for (WireId consumed_wire : newly_consumed_wires) { - const NetInfo *net_for_wire = site_info->consumed_wires.at(consumed_wire); - if (net_for_wire != expansion.net_for_wire) { - expansion.remove_wire(consumed_wire); - } + sinks_to_solutions.resize(sink_map.size()); - // By removing that wire, this expansion now has no solutions! - if (expansion.completed_routes.empty()) { - return false; - } - } - } + for (const auto *expansion : expansions) { + for (size_t idx = 0; idx < expansion->num_solutions(); ++idx) { + SiteWire wire = expansion->solution_sink(idx); + auto begin = expansion->solution_begin(idx); + auto end = expansion->solution_end(idx); + NPNR_ASSERT(begin != end); - // Check if there are any more trivial solutions. - completed_wires.clear(); - newly_consumed_wires.clear(); + size_t sink_idx = sink_map.at(wire); + sinks_to_solutions.at(sink_idx).push_back(solutions.size()); - for (auto &expansion_wire : wire_to_expansion) { - auto &expansion = *expansion_wire.second; - if (expansion.completed_routes.size() == 1) { - auto node = expansion.completed_routes.begin()->second; - if (!site_info->select_route(expansion.first_wire, node, expansion.net_for_wire, - &newly_consumed_wires)) { - // Conflict! - return false; - } + solutions.emplace_back(); + auto &solution = solutions.back(); + solution.net = ctx->wire_to_nets.at(wire).net; + solution.pips_begin = begin; + solution.pips_end = end; - // Mark this expansion as done! - completed_wires.push_back(expansion_wire.first); + for (auto iter = begin; iter != end; ++iter) { + NPNR_ASSERT(ctx->getPipDstWire(*iter) == wire); + wire = ctx->getPipSrcWire(*iter); } - } - // Remove trivial solutions from unsolved routing. - for (WireId wire : completed_wires) { - NPNR_ASSERT(wire_to_expansion.erase(wire) == 1); + NPNR_ASSERT(expansion->net_driver == wire); } + } - // All expansions have been selected for! - if (wire_to_expansion.empty()) { - break; - } - - // At least 1 trivial solution was selected, re-prune. - if (!newly_consumed_wires.empty()) { - // Prune remaining solutions. - continue; - } - - std::unordered_map<WireId, std::unordered_set<const NetInfo *>> wire_congestion; - - for (auto &consumed_wire : site_info->consumed_wires) { - wire_congestion[consumed_wire.first].emplace(consumed_wire.second); - } - - for (auto &expansion_wire : wire_to_expansion) { - auto &expansion = *expansion_wire.second; - - for (auto pair : expansion.completed_routes) { - auto node = pair.second; - - do { - wire_congestion[node->wire].emplace(expansion.net_for_wire); - node = node->parent; - } while (node != RouteNode::Node()); - } - } - - for (auto &expansion_wire : wire_to_expansion) { - auto &expansion = *expansion_wire.second; - - RouteNode::Node uncongestion_route; - - for (auto pair : expansion.completed_routes) { - auto node = pair.second; - uncongestion_route = node; - - do { - if (wire_congestion[node->wire].size() > 1) { - uncongestion_route = RouteNode::Node(); - break; - } - node = node->parent; - } while (node != RouteNode::Node()); + return find_solution_via_backtrack(ctx, &solutions, sinks_to_solutions); +} - if (uncongestion_route != RouteNode::Node()) { - break; +void check_routing(const SiteArch &site_arch) +{ + for (auto &net_pair : site_arch.nets) { + const NetInfo *net = net_pair.first; + const SiteNetInfo &net_info = net_pair.second; + + for (const auto &user : net_info.users) { + NPNR_ASSERT(site_arch.wire_to_nets.at(user).net->net == net); + SiteWire cursor = user; + while (cursor != net_info.driver) { + auto iter = net_info.wires.find(cursor); + if (iter == net_info.wires.end()) { + log_error("Wire %s has no pip, but didn't reach driver wire %s\n", site_arch.nameOfWire(cursor), + site_arch.nameOfWire(net_info.driver)); } + const SitePip &site_pip = iter->second.pip; + cursor = site_arch.getPipSrcWire(site_pip); } - if (uncongestion_route != RouteNode::Node()) { - // Select a trivially uncongested route if possible. - if (!site_info->select_route(expansion.first_wire, uncongestion_route, expansion.net_for_wire, - &newly_consumed_wires)) { - log_info("Failed to bind uncongested path with wire %s on net %s\n", - ctx->nameOfWire(expansion.first_wire), expansion.net_for_wire->name.c_str(ctx)); - uncongestion_route->print_route(ctx); - - site_info->print_current_state(); - NPNR_ASSERT(false); - } - completed_wires.push_back(expansion.first_wire); - } + NPNR_ASSERT(cursor == net_info.driver); + NPNR_ASSERT(site_arch.wire_to_nets.at(cursor).net->net == net); } + } +} - // Remove trivial solutions from unsolved routing. - for (WireId wire : completed_wires) { - NPNR_ASSERT(wire_to_expansion.erase(wire) == 1); +void apply_routing(Context *ctx, const SiteArch &site_arch) +{ + for (auto &net_pair : site_arch.nets) { + NetInfo *net = net_pair.first; + + // If the driver wire is a site wire, bind it. + if (net_pair.second.driver.type == SiteWire::SITE_WIRE) { + WireId driver_wire = net_pair.second.driver.wire; + if (ctx->getBoundWireNet(driver_wire) != net) { + ctx->bindWire(driver_wire, net, STRENGTH_PLACER); + } } - // All expansions have been selected for! - if (wire_to_expansion.empty()) { - break; - } + for (auto &wire_pair : net_pair.second.wires) { + const SitePip &site_pip = wire_pair.second.pip; + if (site_pip.type != SitePip::SITE_PIP && site_pip.type != SitePip::SITE_PORT) { + continue; + } - // At least 1 trivial solution was selected, re-prune. - if (!newly_consumed_wires.empty()) { - // Prune remaining solutions. - continue; + ctx->bindPip(site_pip.pip, net, STRENGTH_PLACER); } - - // FIXME: Actually de-congest non-trivial site routing. - // - // The simplistic solution (only select when 1 solution is available) - // will likely solve initial problems. Once that is show to be wrong, - // come back with something more general. - return false; - - } while (!wire_to_expansion.empty()); - - return true; + } } bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const @@ -780,67 +718,90 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta } if (!lut_mapper.remap_luts(ctx)) { - return false; + site_ok = false; + return site_ok; } } - SiteInformation site_info(ctx, cells_in_site); + SiteInformation site_info(ctx, tile, site, cells_in_site); // Push from cell pins to the first WireId from each cell pin. - if (!site_info.check_initial_wires()) { + if (!check_initial_wires(ctx, &site_info)) { site_ok = false; return site_ok; } - site_ok = route_site(ctx, &site_info); + SiteArch site_arch(&site_info); + // site_arch.archcheck(); + + site_ok = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage); if (verbose_site_router(ctx)) { if (site_ok) { - site_info.remove_routed_sources(); - NPNR_ASSERT(site_info.is_fully_routed()); log_info("Site %s is routable\n", ctx->get_site_name(tile, site)); } else { log_info("Site %s is not routable\n", ctx->get_site_name(tile, site)); } } + if (site_ok) { + check_routing(site_arch); + } return site_ok; } -void SiteInformation::print_current_state() const +void SiteRouter::bindSiteRouting(Context *ctx) { - const CellInfo *cell = *cells_in_site.begin(); - BelId bel = cell->bel; - const auto &bel_data = bel_info(ctx->chip_info, bel); - const auto &site_inst = site_inst_info(ctx->chip_info, bel.tile, bel_data.site); + NPNR_ASSERT(!dirty); + NPNR_ASSERT(site_ok); - log_info("Site %s\n", site_inst.name.get()); + // Make sure all cells in this site belong! + auto iter = cells_in_site.begin(); + NPNR_ASSERT((*iter)->bel != BelId()); - log_info(" Cells in site:\n"); - for (CellInfo *cell : cells_in_site) { - log_info(" - %s (%s)\n", cell->name.c_str(ctx), cell->type.c_str(ctx)); - } + auto tile = (*iter)->bel.tile; + auto &tile_type = loc_info(ctx->chip_info, (*iter)->bel); - log_info(" Nets in site:\n"); - for (auto *net : nets_in_site) { - log_info(" - %s, pins in site:\n", net->name.c_str(ctx)); - if (net->driver.cell && cells_in_site.count(net->driver.cell)) { - log_info(" - %s/%s (%s)\n", net->driver.cell->name.c_str(ctx), net->driver.port.c_str(ctx), - net->driver.cell->type.c_str(ctx)); + // Unbind all bound site wires + WireId wire; + wire.tile = tile; + for (size_t wire_index = 0; wire_index < tile_type.wire_data.size(); ++wire_index) { + const TileWireInfoPOD &wire_data = tile_type.wire_data[wire_index]; + + if (wire_data.site != this->site) { + continue; } - for (const auto user : net->users) { - if (user.cell && cells_in_site.count(user.cell)) { - log_info(" - %s/%s (%s)\n", user.cell->name.c_str(ctx), user.port.c_str(ctx), - user.cell->type.c_str(ctx)); - } + wire.index = wire_index; + + NetInfo *net = ctx->getBoundWireNet(wire); + if (net == nullptr) { + continue; + } + + auto &pip_map = net->wires.at(wire); + if (pip_map.strength <= STRENGTH_STRONG) { + ctx->unbindWire(wire); } } - log_info(" Consumed wires:\n"); - for (auto consumed_wire : consumed_wires) { - WireId wire = consumed_wire.first; - const NetInfo *net = consumed_wire.second; - log_info(" - %s is bound to %s\n", ctx->nameOfWire(wire), net->name.c_str(ctx)); + SiteInformation site_info(ctx, tile, site, cells_in_site); + SiteArch site_arch(&site_info); + NPNR_ASSERT(route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage)); + check_routing(site_arch); + apply_routing(ctx, site_arch); + if (verbose_site_router(ctx)) { + print_current_state(&site_arch); + } +} + +ArchNetInfo::~ArchNetInfo() { delete loop; } + +Arch::~Arch() +{ + for (auto &net_pair : nets) { + if (net_pair.second->loop) { + net_pair.second->loop->clear(); + } } } diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h index c2590728..ebdfbe3b 100644 --- a/fpga_interchange/site_router.h +++ b/fpga_interchange/site_router.h @@ -25,6 +25,8 @@ #include "nextpnr_namespaces.h" #include "nextpnr_types.h" +#include "site_arch.h" +#include "site_routing_storage.h" NEXTPNR_NAMESPACE_BEGIN @@ -44,6 +46,7 @@ struct SiteRouter void bindBel(CellInfo *cell); void unbindBel(CellInfo *cell); bool checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const; + void bindSiteRouting(Context *ctx); }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_routing_cache.cc b/fpga_interchange/site_routing_cache.cc new file mode 100644 index 00000000..f7321a46 --- /dev/null +++ b/fpga_interchange/site_routing_cache.cc @@ -0,0 +1,193 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "site_routing_cache.h" + +#include "context.h" +#include "site_arch.impl.h" + +NEXTPNR_NAMESPACE_BEGIN + +void SiteRoutingSolution::store_solution(const SiteArch *ctx, const RouteNodeStorage *node_storage, + const SiteWire &driver, std::vector<size_t> solutions) +{ + clear(); + + solution_sinks.reserve(solutions.size()); + + for (size_t route : solutions) { + SiteWire wire = node_storage->get_node(route)->wire; + solution_sinks.push_back(wire); + + solution_offsets.push_back(solution_storage.size()); + Node cursor = node_storage->get_node(route); + while (cursor.has_parent()) { + solution_storage.push_back(cursor->pip); + Node parent = cursor.parent(); + NPNR_ASSERT(ctx->getPipDstWire(cursor->pip) == cursor->wire); + NPNR_ASSERT(ctx->getPipSrcWire(cursor->pip) == parent->wire); + cursor = parent; + } + + NPNR_ASSERT(cursor->wire == driver); + } + + solution_offsets.push_back(solution_storage.size()); +} + +void SiteRoutingSolution::verify(const SiteArch *ctx, const SiteNetInfo &net) +{ + HashTables::HashSet<SiteWire> seen_users; + for (size_t i = 0; i < num_solutions(); ++i) { + SiteWire cursor = solution_sink(i); + NPNR_ASSERT(net.users.count(cursor) == 1); + seen_users.emplace(cursor); + + auto begin = solution_begin(i); + auto end = solution_end(i); + + for (auto iter = begin; iter != end; ++iter) { + SitePip pip = *iter; + NPNR_ASSERT(ctx->getPipDstWire(pip) == cursor); + cursor = ctx->getPipSrcWire(pip); + } + + NPNR_ASSERT(net.driver == cursor); + } + + NPNR_ASSERT(seen_users.size() == net.users.size()); +} + +SiteRoutingKey SiteRoutingKey::make(const SiteArch *ctx, const SiteNetInfo &site_net) +{ + SiteRoutingKey out; + + out.tile_type = ctx->site_info->tile_type; + out.site = ctx->site_info->site; + + out.net_type = ctx->ctx->get_net_type(site_net.net); + out.driver_type = site_net.driver.type; + if (site_net.driver.type == SiteWire::SITE_WIRE) { + out.driver_index = site_net.driver.wire.index; + } else { + NPNR_ASSERT(site_net.driver.type == SiteWire::OUT_OF_SITE_SOURCE); + out.driver_index = -1; + } + + out.user_types.reserve(site_net.users.size()); + out.user_indicies.reserve(site_net.users.size()); + + std::vector<SiteWire> users; + users.reserve(site_net.users.size()); + users.insert(users.begin(), site_net.users.begin(), site_net.users.end()); + + std::sort(users.begin(), users.end()); + + for (const SiteWire &user : users) { + out.user_types.push_back(user.type); + + if (user.type == SiteWire::SITE_WIRE) { + out.user_indicies.push_back(user.wire.index); + } else { + NPNR_ASSERT(user.type == SiteWire::OUT_OF_SITE_SINK); + out.user_indicies.push_back(-1); + } + } + + return out; +} + +bool SiteRoutingCache::get_solution(const SiteArch *ctx, const SiteNetInfo &net, SiteRoutingSolution *solution) const +{ + SiteRoutingKey key = SiteRoutingKey::make(ctx, net); + auto iter = cache_.find(key); + if (iter == cache_.end()) { + return false; + } + + *solution = iter->second; + const auto &tile_type_data = ctx->site_info->chip_info().tile_types[ctx->site_info->tile_type]; + + for (SiteWire &wire : solution->solution_sinks) { + switch (wire.type) { + case SiteWire::SITE_WIRE: + wire.wire.tile = ctx->site_info->tile; + break; + case SiteWire::OUT_OF_SITE_SOURCE: + wire.net = net.net; + break; + case SiteWire::OUT_OF_SITE_SINK: + wire.net = net.net; + break; + case SiteWire::SITE_PORT_SINK: { + const auto &pip_data = tile_type_data.pip_data[wire.pip.index]; + wire.pip.tile = ctx->site_info->tile; + wire.wire = canonical_wire(&ctx->site_info->chip_info(), ctx->site_info->tile, pip_data.dst_index); + break; + } + case SiteWire::SITE_PORT_SOURCE: { + const auto &pip_data = tile_type_data.pip_data[wire.pip.index]; + wire.pip.tile = ctx->site_info->tile; + wire.wire = canonical_wire(&ctx->site_info->chip_info(), ctx->site_info->tile, pip_data.src_index); + break; + } + default: + NPNR_ASSERT(false); + } + } + + for (SitePip &pip : solution->solution_storage) { + pip.pip.tile = ctx->site_info->tile; + switch (pip.type) { + case SitePip::SITE_PIP: + // Done! + break; + case SitePip::SITE_PORT: + // Done! + break; + case SitePip::SOURCE_TO_SITE_PORT: + NPNR_ASSERT(pip.wire.type == SiteWire::OUT_OF_SITE_SOURCE); + pip.wire.net = net.net; + break; + case SitePip::SITE_PORT_TO_SINK: + NPNR_ASSERT(pip.wire.type == SiteWire::OUT_OF_SITE_SINK); + pip.wire.net = net.net; + break; + case SitePip::SITE_PORT_TO_SITE_PORT: + pip.other_pip.tile = ctx->site_info->tile; + break; + default: + NPNR_ASSERT(false); + } + } + + solution->verify(ctx, net); + + return true; +} + +void SiteRoutingCache::add_solutions(const SiteArch *ctx, const SiteNetInfo &net, const SiteRoutingSolution &solution) +{ + SiteRoutingKey key = SiteRoutingKey::make(ctx, net); + + cache_[key] = solution; +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_routing_cache.h b/fpga_interchange/site_routing_cache.h new file mode 100644 index 00000000..942375dc --- /dev/null +++ b/fpga_interchange/site_routing_cache.h @@ -0,0 +1,134 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SITE_ROUTING_CACHE_H +#define SITE_ROUTING_CACHE_H + +#include "PhysicalNetlist.capnp.h" +#include "hash_table.h" +#include "nextpnr_namespaces.h" +#include "site_arch.h" +#include "site_routing_storage.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct SiteRoutingSolution +{ + void store_solution(const SiteArch *ctx, const RouteNodeStorage *node_storage, const SiteWire &driver, + std::vector<size_t> solutions); + void verify(const SiteArch *ctx, const SiteNetInfo &net); + + void clear() + { + solution_offsets.clear(); + solution_storage.clear(); + solution_sinks.clear(); + } + + size_t num_solutions() const { return solution_sinks.size(); } + + const SiteWire &solution_sink(size_t solution) const { return solution_sinks.at(solution); } + + std::vector<SitePip>::const_iterator solution_begin(size_t solution) const + { + NPNR_ASSERT(solution + 1 < solution_offsets.size()); + return solution_storage.begin() + solution_offsets.at(solution); + } + + std::vector<SitePip>::const_iterator solution_end(size_t solution) const + { + NPNR_ASSERT(solution + 1 < solution_offsets.size()); + return solution_storage.begin() + solution_offsets.at(solution + 1); + } + + std::vector<size_t> solution_offsets; + std::vector<SitePip> solution_storage; + std::vector<SiteWire> solution_sinks; +}; + +struct SiteRoutingKey +{ + int32_t tile_type; + int32_t site; + // The net type matters for site routing. Legal routes for VCC/GND/SIGNAL + // nets are different. + PhysicalNetlist::PhysNetlist::NetType net_type; + SiteWire::Type driver_type; + int32_t driver_index; + std::vector<SiteWire::Type> user_types; + std::vector<int32_t> user_indicies; + + bool operator==(const SiteRoutingKey &other) const + { + return tile_type == other.tile_type && site == other.site && net_type == other.net_type && + driver_type == other.driver_type && driver_index == other.driver_index && + user_types == other.user_types && user_indicies == other.user_indicies; + } + bool operator!=(const SiteRoutingKey &other) const + { + return tile_type != other.tile_type || site != other.site || net_type != other.net_type || + driver_type != other.driver_type || driver_index != other.driver_index || + user_types != other.user_types || user_indicies != other.user_indicies; + } + + static SiteRoutingKey make(const SiteArch *ctx, const SiteNetInfo &site_net); +}; + +NEXTPNR_NAMESPACE_END + +template <> struct std::hash<NEXTPNR_NAMESPACE_PREFIX SiteRoutingKey> +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX SiteRoutingKey &key) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, std::hash<int32_t>()(key.tile_type)); + boost::hash_combine(seed, std::hash<int32_t>()(key.site)); + boost::hash_combine(seed, std::hash<PhysicalNetlist::PhysNetlist::NetType>()(key.net_type)); + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(key.driver_type)); + boost::hash_combine(seed, std::hash<int32_t>()(key.driver_index)); + boost::hash_combine(seed, std::hash<std::size_t>()(key.user_types.size())); + for (NEXTPNR_NAMESPACE_PREFIX SiteWire::Type user_type : key.user_types) { + boost::hash_combine(seed, std::hash<NEXTPNR_NAMESPACE_PREFIX SiteWire::Type>()(user_type)); + } + + boost::hash_combine(seed, std::hash<std::size_t>()(key.user_indicies.size())); + for (int32_t index : key.user_indicies) { + boost::hash_combine(seed, std::hash<int32_t>()(index)); + } + return seed; + } +}; + +NEXTPNR_NAMESPACE_BEGIN + +// Provides an LRU cache for site routing solutions. +class SiteRoutingCache +{ + public: + bool get_solution(const SiteArch *ctx, const SiteNetInfo &net, SiteRoutingSolution *solution) const; + void add_solutions(const SiteArch *ctx, const SiteNetInfo &net, const SiteRoutingSolution &solution); + + private: + HashTables::HashMap<SiteRoutingKey, SiteRoutingSolution> cache_; +}; + +NEXTPNR_NAMESPACE_END + +#endif /* SITE_ROUTING_CACHE_H */ diff --git a/fpga_interchange/site_routing_storage.h b/fpga_interchange/site_routing_storage.h new file mode 100644 index 00000000..a8ea51f5 --- /dev/null +++ b/fpga_interchange/site_routing_storage.h @@ -0,0 +1,150 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#ifndef SITE_ROUTING_STORAGE +#define SITE_ROUTING_STORAGE + +#include <limits> + +#include "nextpnr_namespaces.h" +#include "site_arch.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct RouteNode +{ + void clear() + { + parent = std::numeric_limits<size_t>::max(); + pip = SitePip(); + wire = SiteWire(); + flags = 0; + depth = 0; + } + + enum Flags + { + // Has this path left the site? + LEFT_SITE = 0, + // Has this path entered the site? + ENTERED_SITE = 1, + }; + + bool has_left_site() const { return (flags & (1 << LEFT_SITE)) != 0; } + + bool can_leave_site() const { return !has_left_site(); } + + void mark_left_site() { flags |= (1 << LEFT_SITE); } + + bool has_entered_site() const { return (flags & (1 << ENTERED_SITE)) != 0; } + + bool can_enter_site() const { return !has_entered_site(); } + + void mark_entered_site() { flags |= (1 << ENTERED_SITE); } + + size_t parent; + + SitePip pip; // What pip was taken to reach this node. + SiteWire wire; // What wire is this routing node located at? + int32_t flags; + int32_t depth; +}; + +struct RouteNodeStorage; + +class Node +{ + public: + Node(RouteNodeStorage *storage, size_t idx) : storage_(storage), idx_(idx) {} + + size_t get_index() const { return idx_; } + + RouteNode &operator*(); + const RouteNode &operator*() const; + RouteNode *operator->(); + const RouteNode *operator->() const; + bool has_parent() const; + Node parent(); + + private: + RouteNodeStorage *storage_; + size_t idx_; +}; + +struct RouteNodeStorage +{ + // Free list of nodes. + std::vector<RouteNode> nodes; + std::vector<size_t> free_list; + + // Either allocate a new node if no nodes are on the free list, or return + // an element from the free list. + Node alloc_node() + { + if (free_list.empty()) { + nodes.emplace_back(); + nodes.back().clear(); + return Node(this, nodes.size() - 1); + } + + size_t idx = free_list.back(); + free_list.pop_back(); + nodes[idx].clear(); + + return Node(this, idx); + } + + Node get_node(size_t idx) + { + NPNR_ASSERT(idx < nodes.size()); + return Node(this, idx); + } + + const Node get_node(size_t idx) const + { + NPNR_ASSERT(idx < nodes.size()); + return Node(const_cast<RouteNodeStorage *>(this), idx); + } + + // Return all node from the current owner to the free list. + void free_nodes(std::vector<size_t> &other_free_list) + { + free_list.insert(free_list.end(), other_free_list.begin(), other_free_list.end()); + } +}; + +inline RouteNode &Node::operator*() { return storage_->nodes[idx_]; } +inline const RouteNode &Node::operator*() const { return storage_->nodes[idx_]; } + +inline RouteNode *Node::operator->() { return &storage_->nodes[idx_]; } +inline const RouteNode *Node::operator->() const { return &storage_->nodes[idx_]; } + +inline bool Node::has_parent() const { return storage_->nodes[idx_].parent < storage_->nodes.size(); } + +inline Node Node::parent() +{ + size_t parent_idx = storage_->nodes[idx_].parent; + NPNR_ASSERT(parent_idx < storage_->nodes.size()); + return Node(storage_, parent_idx); +} + +NEXTPNR_NAMESPACE_END + +#endif /* SITE_ROUTING_STORAGE */ |