From 523ffbaa37a367557da434752cb286643e24b627 Mon Sep 17 00:00:00 2001 From: gatecat Date: Thu, 1 Jul 2021 11:08:36 +0100 Subject: interchange: Reserve site ports only reachable from dedicated routing Signed-off-by: gatecat --- fpga_interchange/arch.cc | 4 +++ fpga_interchange/site_arch.h | 3 ++ fpga_interchange/site_router.cc | 59 ++++++++++++++++++++++++++++++++++ fpga_interchange/site_routing_cache.cc | 2 ++ fpga_interchange/site_routing_cache.h | 1 + 5 files changed, 69 insertions(+) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index de172d90..e9bc4559 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -832,6 +832,10 @@ static void prepare_sites_for_routing(Context *ctx) } } + // Clear the site routing cache. This is because routing at this stage is done with the extra constraint of blocked + // pins to ensure a routeable pin choice. + ctx->site_routing_cache.clear(); + // Have site router bind site routing (via bindPip and bindWire). // This is important so that the pseudo pips are correctly blocked prior // to handing the design to the generalized router algorithms. diff --git a/fpga_interchange/site_arch.h b/fpga_interchange/site_arch.h index 54b91a4a..81c0b96c 100644 --- a/fpga_interchange/site_arch.h +++ b/fpga_interchange/site_arch.h @@ -260,6 +260,9 @@ struct SiteArch std::vector out_of_site_sources; std::vector out_of_site_sinks; + // A site port that is present in this dictionary is blocked for all those nets except any in the attached pool + dict> blocked_site_ports; + SiteArch(const SiteInformation *site_info); inline SiteWire getPipSrcWire(const SitePip &site_pip) const NPNR_ALWAYS_INLINE; diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index fbb87c00..94d7ee17 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -27,6 +27,8 @@ #include "site_arch.h" #include "site_arch.impl.h" +#include + NEXTPNR_NAMESPACE_BEGIN bool verbose_site_router(const Context *ctx) { return ctx->debug; } @@ -97,6 +99,11 @@ bool check_initial_wires(const Context *ctx, SiteInformation *site_info) static bool is_invalid_site_port(const SiteArch *ctx, const SiteNetInfo *net, const SitePip &pip) { + // Blocked ports + auto fnd_rsv = ctx->blocked_site_ports.find(pip.pip); + if (fnd_rsv != ctx->blocked_site_ports.end() && !fnd_rsv->second.count(net->net)) + return true; + // Synthetic pips SyntheticType type = ctx->pip_synthetic_type(pip); PhysicalNetlist::PhysNetlist::NetType net_type = ctx->ctx->get_net_type(net->net); bool is_invalid = false; @@ -1133,6 +1140,57 @@ static void block_cluster_wires(SiteArch *site_arch) } } +// Reserve site ports that are on dedicated rather than general interconnect +static void reserve_site_ports(SiteArch *site_arch) +{ + const Context *ctx = site_arch->site_info->ctx; + site_arch->blocked_site_ports.clear(); + for (PipId in_pip : site_arch->input_site_ports) { + pool dedicated_nets; + const int max_iters = 100; + + std::queue visit_queue; + pool already_visited; + WireId src = ctx->getPipSrcWire(in_pip); + visit_queue.push(src); + already_visited.insert(src); + + int iter = 0; + while (!visit_queue.empty() && iter++ < max_iters) { + WireId next = visit_queue.front(); + visit_queue.pop(); + for (auto bp : ctx->getWireBelPins(next)) { + // Bel pins could mean dedicated routes + CellInfo *bound = ctx->getBoundBelCell(bp.bel); + if (bound == nullptr) + continue; + // Need to find the corresponding cell pin + for (auto &port : bound->ports) { + if (port.second.net == nullptr) + continue; + for (auto bel_pin : ctx->getBelPinsForCellPin(bound, port.first)) { + if (bel_pin == bp.pin) + dedicated_nets.insert(port.second.net); + } + } + } + for (auto pip : ctx->getPipsUphill(next)) { + WireId next_src = ctx->getPipSrcWire(pip); + if (already_visited.count(next_src)) + continue; + visit_queue.push(next_src); + already_visited.insert(next_src); + } + } + if (iter < max_iters) { + if (ctx->debug) + log_info("Blocking PIP %s\n", ctx->nameOfPip(in_pip)); + // If we didn't search up to the iteration limit, assume this node is not reachable from general routing + site_arch->blocked_site_ports[in_pip] = dedicated_nets; + } + } +} + // Recursively visit downhill PIPs until a SITE_PORT_SINK is reached. // Marks all PIPs for all valid paths. static bool visit_downhill_pips(const SiteArch *site_arch, const SiteWire &site_wire, std::vector &valid_pips) @@ -1313,6 +1371,7 @@ void SiteRouter::bindSiteRouting(Context *ctx) SiteArch site_arch(&site_info); block_lut_outputs(&site_arch, blocked_wires); block_cluster_wires(&site_arch); + reserve_site_ports(&site_arch); NPNR_ASSERT(route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/false)); check_routing(site_arch); diff --git a/fpga_interchange/site_routing_cache.cc b/fpga_interchange/site_routing_cache.cc index cd16cfff..82bbbf1b 100644 --- a/fpga_interchange/site_routing_cache.cc +++ b/fpga_interchange/site_routing_cache.cc @@ -204,4 +204,6 @@ void SiteRoutingCache::add_solutions(const SiteArch *ctx, const SiteNetInfo &net cache_[key] = solution; } +void SiteRoutingCache::clear() { cache_.clear(); } + NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/site_routing_cache.h b/fpga_interchange/site_routing_cache.h index a430d206..5f5e7b75 100644 --- a/fpga_interchange/site_routing_cache.h +++ b/fpga_interchange/site_routing_cache.h @@ -121,6 +121,7 @@ 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); + void clear(); private: dict cache_; -- cgit v1.2.3