Merge pull request #637 from litghost/refine_site_router

Refine site router

1 files changed, 376 insertions, 0 deletions

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