gowin: add a separate router for the clocks

A simple router that takes advantage of the fact that in each cell with
DFFs their CLK inputs can directly connect to the global clock network.

Networks with a large number of such sinks are sought and then each
network is assigned to the available independent global clock networks.

There are limited possibilities for routing mixed networks, that is,
when the sinks are not only CLKs: in this case an attempt is made to use
wires such as SN10/20 and EW10/20, that is, one short transition can be
added between the global clock network and the sink.

* At this time, networks with a source other than the I/O pin are not
  supported. This is typical for Tangnano4k and runber boards.

* Router is disabled by default, you need to specify option
  --enable-globals to activate

* No new chip bases are required. This may change in the distant future.

Signed-off-by: YRabbit <rabbit@yrabbit.cyou>

5 files changed, 392 insertions, 1 deletions

diff --git a/gowin/arch.cc b/gowin/arch.cc
index 82f5018b..7b9097c9 100644
--- a/gowin/arch.cc
+++ b/gowin/arch.cc
@@ -25,6 +25,7 @@
 #include <regex>
 #include "embed.h"
 #include "gfx.h"
+#include "globals.h"
 #include "nextpnr.h"
 #include "placer1.h"
 #include "placer_heap.h"
@@ -341,6 +342,14 @@ BelInfo &Arch::bel_info(IdString bel)
     return b->second;
 }
 
+NetInfo &Arch::net_info(IdString net)
+{
+    auto b = nets.find(net);
+    if (b == nets.end())
+        NPNR_ASSERT_FALSE_STR("no net named " + net.str(this));
+    return *b->second;
+}
+
 void Arch::addWire(IdString name, IdString type, int x, int y)
 {
     NPNR_ASSERT(wires.count(name) == 0);
@@ -657,6 +666,7 @@ bool aliasCompare(GlobalAliasPOD i, GlobalAliasPOD j)
     return (i.dest_row < j.dest_row) || (i.dest_row == j.dest_row && i.dest_col < j.dest_col) ||
            (i.dest_row == j.dest_row && i.dest_col == j.dest_col && i.dest_id < j.dest_id);
 }
+
 bool timingCompare(TimingPOD i, TimingPOD j) { return i.name_id < j.name_id; }
 
 template <class T, class C> const T *genericLookup(const T *first, int len, const T val, C compare)
@@ -1865,6 +1875,11 @@ bool Arch::place()
 bool Arch::route()
 {
     std::string router = str_or_default(settings, id_router, defaultRouter);
+
+    if (bool_or_default(settings, id("arch.enable-globals"))) {
+        route_gowin_globals(getCtx());
+    }
+
     bool result;
     if (router == "router1") {
         result = router1(getCtx(), Router1Cfg(getCtx()));
diff --git a/gowin/arch.h b/gowin/arch.h
index 8bbbd514..c59f8eb3 100644
--- a/gowin/arch.h
+++ b/gowin/arch.h
@@ -289,6 +289,7 @@ struct Arch : BaseArch<ArchRanges>
     WireInfo &wire_info(IdString wire);
     PipInfo &pip_info(IdString pip);
     BelInfo &bel_info(IdString bel);
+    NetInfo &net_info(IdString net);
 
     std::vector<IdString> bel_ids, wire_ids, pip_ids;
 
diff --git a/gowin/globals.cc b/gowin/globals.cc
new file mode 100644
index 00000000..5010cf79
--- /dev/null
+++ b/gowin/globals.cc
@@ -0,0 +1,335 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  gatecat <gatecat@ds0.me>
+ *
+ *  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 "globals.h"
+#include <algorithm>
+#include <iomanip>
+#include <iostream>
+#include <queue>
+#include "cells.h"
+#include "log.h"
+#include "nextpnr.h"
+#include "place_common.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+class GowinGlobalRouter
+{
+  public:
+    GowinGlobalRouter(Context *ctx) : ctx(ctx){};
+
+  private:
+    // wire -> clock#
+    dict<WireId, int> used_wires;
+
+    // ordered nets
+    struct onet_t
+    {
+        IdString name;
+        int clock_ports;
+        WireId clock_io_wire; // IO wire if there is one
+
+        onet_t() : name(IdString()), clock_ports(0), clock_io_wire(WireId()) {}
+        onet_t(IdString _name) : name(_name), clock_ports(0), clock_io_wire(WireId()) {}
+
+        // sort
+        bool operator<(const onet_t &other) const
+        {
+            if ((clock_io_wire != WireId()) ^ (other.clock_io_wire != WireId())) {
+                return !(clock_io_wire != WireId());
+            }
+            return clock_ports < other.clock_ports;
+        }
+        // search
+        bool operator==(const onet_t &other) const { return name == other.name; }
+    };
+
+    bool is_clock_port(PortRef const &user)
+    {
+        if (user.cell->type == id_SLICE && user.port == id_CLK) {
+            return true;
+        }
+        return false;
+    }
+
+    WireId clock_io(PortRef const &driver)
+    {
+        // XXX normally all alternative functions of the pins should be passed
+        // in the chip database, but at the moment we find them from aliases/pips
+        // XXX check diff inputs too
+        if (driver.cell == nullptr || driver.cell->bel == BelId()) {
+            return WireId();
+        }
+        // clock IOs have pips output->SPINExx
+        BelInfo &bel = ctx->bels.at(driver.cell->bel);
+        if (bel.type != id_IOB) {
+            return WireId();
+        }
+        WireId wire = bel.pins[id_O].wire;
+        for (auto const &pip : ctx->getPipsDownhill(wire)) {
+            if (ctx->wire_info(ctx->getPipDstWire(pip)).type.str(ctx).rfind("SPINE", 0) == 0) {
+                return wire;
+            }
+        }
+        return WireId();
+    }
+
+    // gather the clock nets
+    void gather_clock_nets(std::vector<onet_t> &clock_nets)
+    {
+        for (auto const &net : ctx->nets) {
+            NetInfo const *ni = net.second.get();
+            auto new_clock = clock_nets.end();
+            WireId clock_wire = clock_io(ni->driver);
+            if (clock_wire != WireId()) {
+                clock_nets.emplace_back(net.first);
+                new_clock = --clock_nets.end();
+                new_clock->clock_io_wire = clock_wire;
+            }
+            for (auto const &user : ni->users) {
+                if (is_clock_port(user)) {
+                    if (new_clock == clock_nets.end()) {
+                        clock_nets.emplace_back(net.first);
+                        new_clock = --clock_nets.end();
+                    }
+                    ++(new_clock->clock_ports);
+                }
+            }
+        }
+        // need to prioritize the nets
+        std::sort(clock_nets.begin(), clock_nets.end());
+
+        if (ctx->verbose) {
+            for (auto const &net : clock_nets) {
+                log_info("  Net:%s, ports:%d, io:%s\n", net.name.c_str(ctx), net.clock_ports,
+                         net.clock_io_wire == WireId() ? "No" : net.clock_io_wire.c_str(ctx));
+            }
+        }
+    }
+
+    // non clock port
+    // returns GB pip
+    IdString route_to_non_clock_port(WireId const dstWire, int clock, pool<IdString> &used_pips,
+                                     pool<IdString> &undo_wires)
+    {
+        static std::vector<IdString> one_hop = {id_S111, id_S121, id_N111, id_N121, id_W111, id_W121, id_E111, id_E121};
+        char buf[40];
+        // uphill pips
+        for (auto const &uphill : ctx->getPipsUphill(dstWire)) {
+            WireId srcWire = ctx->getPipSrcWire(uphill);
+            if (find(one_hop.begin(), one_hop.end(), ctx->wire_info(ctx->getPipSrcWire(uphill)).type) !=
+                one_hop.end()) {
+                // found one hop pip
+                if (used_wires.count(srcWire)) {
+                    if (used_wires[srcWire] != clock) {
+                        continue;
+                    }
+                }
+                WireInfo wi = ctx->wire_info(srcWire);
+                std::string wire_alias = srcWire.str(ctx).substr(srcWire.str(ctx).rfind("_") + 1);
+                snprintf(buf, sizeof(buf), "R%dC%d_GB%d0_%s", wi.y + 1, wi.x + 1, clock, wire_alias.c_str());
+                IdString gb = ctx->id(buf);
+                auto up_pips = ctx->getPipsUphill(srcWire);
+                if (find(up_pips.begin(), up_pips.end(), gb) != up_pips.end()) {
+                    if (!used_wires.count(srcWire)) {
+                        used_wires.insert(std::make_pair(srcWire, clock));
+                        undo_wires.insert(srcWire);
+                    }
+                    used_pips.insert(uphill);
+                    if (ctx->verbose) {
+                        log_info("    1-hop Pip:%s\n", uphill.c_str(ctx));
+                    }
+                    return gb;
+                }
+            }
+        }
+        return IdString();
+    }
+
+    // route one net
+    void route_net(onet_t const &net, int clock)
+    {
+        // For failed routing undo
+        pool<IdString> used_pips;
+        pool<IdString> undo_wires;
+
+        log_info("  Route net %s, use clock #%d.\n", net.name.c_str(ctx), clock);
+        for (auto const &user : ctx->net_info(net.name).users) {
+            // >>> port <- GB<clock>0
+            WireId dstWire = ctx->getNetinfoSinkWire(&ctx->net_info(net.name), user, 0);
+            if (ctx->verbose) {
+                log_info("   Cell:%s, port:%s, wire:%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx),
+                         dstWire.c_str(ctx));
+            }
+
+            char buf[30];
+            PipId gb_pip_id;
+            if (user.port == id_CLK) {
+                WireInfo const wi = ctx->wire_info(dstWire);
+                snprintf(buf, sizeof(buf), "R%dC%d_GB%d0_%s", wi.y + 1, wi.x + 1, clock,
+                         ctx->wire_info(dstWire).type.c_str(ctx));
+                gb_pip_id = ctx->id(buf);
+                // sanity
+                NPNR_ASSERT(find(ctx->getPipsUphill(dstWire).begin(), ctx->getPipsUphill(dstWire).end(), gb_pip_id) !=
+                            ctx->getPipsUphill(dstWire).end());
+            } else {
+                // Non clock port
+                gb_pip_id = route_to_non_clock_port(dstWire, clock, used_pips, undo_wires);
+                if (gb_pip_id == IdString()) {
+                    if (ctx->verbose) {
+                        log_info("  Can't find route to %s, net %s will be routed in a standard way.\n",
+                                 dstWire.c_str(ctx), net.name.c_str(ctx));
+                    }
+                    for (IdString const &undo : undo_wires) {
+                        used_wires.erase(undo);
+                    }
+                    return;
+                }
+            }
+            if (ctx->verbose) {
+                log_info("    GB Pip:%s\n", gb_pip_id.c_str(ctx));
+            }
+
+            if (used_pips.count(gb_pip_id)) {
+                if (ctx->verbose) {
+                    log_info("    ^routed already^\n");
+                }
+                continue;
+            }
+            used_pips.insert(gb_pip_id);
+
+            // >>> GBOx <- GTx0
+            dstWire = ctx->getPipSrcWire(gb_pip_id);
+            WireInfo dstWireInfo = ctx->wire_info(dstWire);
+            int branch_tap_idx = clock > 3 ? 1 : 0;
+            snprintf(buf, sizeof(buf), "R%dC%d_GT%d0_GBO%d", dstWireInfo.y + 1, dstWireInfo.x + 1, branch_tap_idx,
+                     branch_tap_idx);
+            PipId gt_pip_id = ctx->id(buf);
+            if (ctx->verbose) {
+                log_info("     GT Pip:%s\n", buf);
+            }
+            // sanity
+            NPNR_ASSERT(find(ctx->getPipsUphill(dstWire).begin(), ctx->getPipsUphill(dstWire).end(), gt_pip_id) !=
+                        ctx->getPipsUphill(dstWire).end());
+            // if already routed
+            if (used_pips.count(gt_pip_id)) {
+                if (ctx->verbose) {
+                    log_info("     ^routed already^\n");
+                }
+                continue;
+            }
+            used_pips.insert(gt_pip_id);
+
+            // >>> GTx0 <- SPINExx
+            // XXX no optimization here, we need to store
+            // the SPINE <-> clock# correspondence in the database. In the
+            // meantime, we define in run-time in a completely suboptimal way.
+            std::vector<std::string> clock_spine;
+            dstWire = ctx->getPipSrcWire(gt_pip_id);
+            for (auto const &uphill_pip : ctx->getPipsUphill(dstWire)) {
+                std::string name = ctx->wire_info(ctx->getPipSrcWire(uphill_pip)).type.str(ctx);
+                if (name.rfind("SPINE", 0) == 0) {
+                    clock_spine.push_back(name);
+                }
+            }
+            sort(clock_spine.begin(), clock_spine.end(), [](const std::string &a, const std::string &b) -> bool {
+                return (a.size() < b.size()) || (a.size() == b.size() && a < b);
+            });
+            dstWireInfo = ctx->wire_info(dstWire);
+            snprintf(buf, sizeof(buf), "R%dC%d_%s_GT%d0", dstWireInfo.y + 1, dstWireInfo.x + 1,
+                     clock_spine[clock - branch_tap_idx * 4].c_str(), branch_tap_idx);
+            PipId spine_pip_id = ctx->id(buf);
+            if (ctx->verbose) {
+                log_info("      Spine Pip:%s\n", buf);
+            }
+            // sanity
+            NPNR_ASSERT(find(ctx->getPipsUphill(dstWire).begin(), ctx->getPipsUphill(dstWire).end(), spine_pip_id) !=
+                        ctx->getPipsUphill(dstWire).end());
+            // if already routed
+            if (used_pips.count(spine_pip_id)) {
+                if (ctx->verbose) {
+                    log_info("      ^routed already^\n");
+                }
+                continue;
+            }
+            used_pips.insert(spine_pip_id);
+
+            // >>> SPINExx <- IO
+            dstWire = ctx->getPipSrcWire(spine_pip_id);
+            dstWireInfo = ctx->wire_info(dstWire);
+            PipId io_pip_id = PipId();
+            for (auto const &uphill_pip : ctx->getPipsUphill(dstWire)) {
+                if (ctx->getPipSrcWire(uphill_pip) == net.clock_io_wire) {
+                    io_pip_id = uphill_pip;
+                }
+            }
+            NPNR_ASSERT(io_pip_id != PipId());
+            if (ctx->verbose) {
+                log_info("       IO Pip:%s\n", io_pip_id.c_str(ctx));
+            }
+            // if already routed
+            if (used_pips.count(io_pip_id)) {
+                if (ctx->verbose) {
+                    log_info("      ^routed already^\n");
+                }
+                continue;
+            }
+            used_pips.insert(io_pip_id);
+        }
+        log_info("  Net %s is routed.\n", net.name.c_str(ctx));
+        for (auto const pip : used_pips) {
+            ctx->bindPip(pip, &ctx->net_info(net.name), STRENGTH_LOCKED);
+        }
+        ctx->bindWire(net.clock_io_wire, &ctx->net_info(net.name), STRENGTH_LOCKED);
+    }
+
+  public:
+    Context *ctx;
+    void route_globals()
+    {
+        log_info("Routing globals...\n");
+
+        std::vector<onet_t> clock_nets;
+        gather_clock_nets(clock_nets);
+        // XXX we need to use the list of indexes of clocks from the database
+        // use 6 clocks (XXX 3 for GW1NZ-1)
+        int max_clock = 3, cur_clock = -1;
+        for (auto const &net : clock_nets) {
+            // XXX only IO clock for now
+            if (net.clock_io_wire == WireId()) {
+                log_info(" Non IO clock, skip %s.\n", net.name.c_str(ctx));
+                continue;
+            }
+            if (++cur_clock >= max_clock) {
+                log_info(" No more clock wires left, skip the remaining nets.\n");
+                break;
+            }
+            route_net(net, cur_clock);
+        }
+    }
+};
+
+void route_gowin_globals(Context *ctx)
+{
+    GowinGlobalRouter router(ctx);
+    router.route_globals();
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/gowin/globals.h b/gowin/globals.h
new file mode 100644
index 00000000..4731447c
--- /dev/null
+++ b/gowin/globals.h
@@ -0,0 +1,26 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  gatecat <gatecat@ds0.me>
+ *
+ *  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 "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+void route_gowin_globals(Context *ctx);
+
+NEXTPNR_NAMESPACE_END
diff --git a/gowin/main.cc b/gowin/main.cc
index a45a49d4..36bd8656 100644
--- a/gowin/main.cc
+++ b/gowin/main.cc
@@ -51,6 +51,8 @@ po::options_description GowinCommandHandler::getArchOptions()
     specific.add_options()("device", po::value<std::string>(), "device name");
     specific.add_options()("family", po::value<std::string>(), "family name");
     specific.add_options()("cst", po::value<std::string>(), "physical constraints file");
+    specific.add_options()("enable-globals", "separate routing of the clocks");
+    specific.add_options()("enable-auto-longwires", "automatic detection and routing of long wires");
     return specific;
 }
 
@@ -79,7 +81,19 @@ std::unique_ptr<Context> GowinCommandHandler::createContext(dict<std::string, Pr
         chipArgs.family = buf;
     }
     chipArgs.partnumber = match[0];
-    return std::unique_ptr<Context>(new Context(chipArgs));
+
+    auto ctx = std::unique_ptr<Context>(new Context(chipArgs));
+    // routing options
+    // the default values will change in the future
+    ctx->settings[ctx->id("arch.enable-globals")] = 0;
+    ctx->settings[ctx->id("arch.enable-auto-longwires")] = 0;
+    if (vm.count("enable-globals")) {
+        ctx->settings[ctx->id("arch.enable-globals")] = 1;
+    }
+    if (vm.count("enable-auto-longwires")) {
+        ctx->settings[ctx->id("arch.enable-auto-longwires")] = 1;
+    }
+    return ctx;
 }
 
 void GowinCommandHandler::customAfterLoad(Context *ctx)