Merge branch 'master' of github.com:YosysHQ/nextpnr into router_improve

13 files changed, 255 insertions, 45 deletions

diff --git a/common/chain_utils.h b/common/chain_utils.h
new file mode 100644
index 00000000..b783e30b
--- /dev/null
+++ b/common/chain_utils.h
@@ -0,0 +1,68 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  David Shah <david@symbioticeda.com>
+ *
+ *  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 CHAIN_UTILS_H
+#define CHAIN_UTILS_H
+
+#include "nextpnr.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct CellChain
+{
+    std::vector<CellInfo *> cells;
+};
+
+// Generic chain finder
+template <typename F1, typename F2, typename F3>
+std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next,
+                                   size_t min_length = 2)
+{
+    std::set<IdString> chained;
+    std::vector<CellChain> chains;
+    for (auto cell : sorted(ctx->cells)) {
+        if (chained.find(cell.first) != chained.end())
+            continue;
+        CellInfo *ci = cell.second;
+        if (cell_type_predicate(ctx, ci)) {
+            CellInfo *start = ci;
+            CellInfo *prev_start = ci;
+            while (prev_start != nullptr) {
+                start = prev_start;
+                prev_start = get_previous(ctx, start);
+            }
+            CellChain chain;
+            CellInfo *end = start;
+            while (end != nullptr) {
+                chain.cells.push_back(end);
+                end = get_next(ctx, end);
+            }
+            if (chain.cells.size() >= min_length) {
+                chains.push_back(chain);
+                for (auto c : chain.cells)
+                    chained.insert(c->name);
+            }
+        }
+    }
+    return chains;
+}
+
+NEXTPNR_NAMESPACE_END
+#endif
diff --git a/common/command.cc b/common/command.cc
index ab0c92f2..c5c777e8 100644
--- a/common/command.cc
+++ b/common/command.cc
@@ -91,8 +91,14 @@ po::options_description CommandHandler::getGeneralOptions()
     general.add_options()("gui", "start gui");
 #endif
 #ifndef NO_PYTHON
-    general.add_options()("run", po::value<std::vector<std::string>>(), "python file to execute");
+    general.add_options()("run", po::value<std::vector<std::string>>(),
+                          "python file to execute instead of default flow");
     pos.add("run", -1);
+    general.add_options()("pre-pack", po::value<std::vector<std::string>>(), "python file to run before packing");
+    general.add_options()("pre-place", po::value<std::vector<std::string>>(), "python file to run before placement");
+    general.add_options()("pre-route", po::value<std::vector<std::string>>(), "python file to run before routing");
+    general.add_options()("post-route", po::value<std::vector<std::string>>(), "python file to run after routing");
+
 #endif
     general.add_options()("json", po::value<std::string>(), "JSON design file to ingest");
     general.add_options()("seed", po::value<int>(), "seed value for random number generator");
@@ -200,40 +206,48 @@ int CommandHandler::executeMain(std::unique_ptr<Context> ctx)
         customAfterLoad(ctx.get());
     }
 
-    if (vm.count("json") || vm.count("load")) {
+#ifndef NO_PYTHON
+    init_python(argv[0], true);
+    python_export_global("ctx", *ctx);
+
+    if (vm.count("run")) {
+
+        std::vector<std::string> files = vm["run"].as<std::vector<std::string>>();
+        for (auto filename : files)
+            execute_python_file(filename.c_str());
+    } else
+#endif
+            if (vm.count("json") || vm.count("load")) {
+        run_script_hook("pre-pack");
         if (!ctx->pack() && !ctx->force)
             log_error("Packing design failed.\n");
         assign_budget(ctx.get());
         ctx->check();
         print_utilisation(ctx.get());
+        run_script_hook("pre-place");
+
         if (!vm.count("pack-only")) {
             if (!ctx->place() && !ctx->force)
                 log_error("Placing design failed.\n");
             ctx->check();
+            run_script_hook("pre-route");
+
             if (!ctx->route() && !ctx->force)
                 log_error("Routing design failed.\n");
         }
+        run_script_hook("post-route");
 
         customBitstream(ctx.get());
     }
 
-#ifndef NO_PYTHON
-    if (vm.count("run")) {
-        init_python(argv[0], true);
-        python_export_global("ctx", *ctx);
-
-        std::vector<std::string> files = vm["run"].as<std::vector<std::string>>();
-        for (auto filename : files)
-            execute_python_file(filename.c_str());
-
-        deinit_python();
-    }
-#endif
-
     if (vm.count("save")) {
         project.save(ctx.get(), vm["save"].as<std::string>());
     }
 
+#ifndef NO_PYTHON
+    deinit_python();
+#endif
+
     return 0;
 }
 
@@ -270,4 +284,15 @@ int CommandHandler::exec()
     }
 }
 
+void CommandHandler::run_script_hook(const std::string &name)
+{
+#ifndef NO_PYTHON
+    if (vm.count(name)) {
+        std::vector<std::string> files = vm[name].as<std::vector<std::string>>();
+        for (auto filename : files)
+            execute_python_file(filename.c_str());
+    }
+#endif
+}
+
 NEXTPNR_NAMESPACE_END
diff --git a/common/command.h b/common/command.h
index 900cf74b..12f710f6 100644
--- a/common/command.h
+++ b/common/command.h
@@ -53,6 +53,7 @@ class CommandHandler
     void setupContext(Context *ctx);
     int executeMain(std::unique_ptr<Context> ctx);
     po::options_description getGeneralOptions();
+    void run_script_hook(const std::string &name);
 
   protected:
     po::variables_map vm;
diff --git a/common/design_utils.cc b/common/design_utils.cc
index 21c9dcc4..a0b87764 100644
--- a/common/design_utils.cc
+++ b/common/design_utils.cc
@@ -19,6 +19,7 @@
  */
 
 #include "design_utils.h"
+#include <algorithm>
 #include <map>
 #include "log.h"
 #include "util.h"
@@ -73,4 +74,55 @@ void print_utilisation(const Context *ctx)
     log_break();
 }
 
+// Connect a net to a port
+void connect_port(const Context *ctx, NetInfo *net, CellInfo *cell, IdString port_name)
+{
+    if (net == nullptr)
+        return;
+    PortInfo &port = cell->ports.at(port_name);
+    NPNR_ASSERT(port.net == nullptr);
+    port.net = net;
+    if (port.type == PORT_OUT) {
+        NPNR_ASSERT(net->driver.cell == nullptr);
+        net->driver.cell = cell;
+        net->driver.port = port_name;
+    } else if (port.type == PORT_IN) {
+        PortRef user;
+        user.cell = cell;
+        user.port = port_name;
+        net->users.push_back(user);
+    } else {
+        NPNR_ASSERT_FALSE("invalid port type for connect_port");
+    }
+}
+
+void disconnect_port(const Context *ctx, CellInfo *cell, IdString port_name)
+{
+    if (!cell->ports.count(port_name))
+        return;
+    PortInfo &port = cell->ports.at(port_name);
+    if (port.net != nullptr) {
+        port.net->users.erase(std::remove_if(port.net->users.begin(), port.net->users.end(),
+                                             [cell, port_name](const PortRef &user) {
+                                                 return user.cell == cell && user.port == port_name;
+                                             }),
+                              port.net->users.end());
+    }
+}
+
+void connect_ports(Context *ctx, CellInfo *cell1, IdString port1_name, CellInfo *cell2, IdString port2_name)
+{
+    PortInfo &port1 = cell1->ports.at(port1_name);
+    if (port1.net == nullptr) {
+        // No net on port1; need to create one
+        std::unique_ptr<NetInfo> p1net(new NetInfo());
+        p1net->name = ctx->id(cell1->name.str(ctx) + "$conn$" + port1_name.str(ctx));
+        connect_port(ctx, p1net.get(), cell1, port1_name);
+        IdString p1name = p1net->name;
+        NPNR_ASSERT(!ctx->cells.count(p1name));
+        ctx->nets[p1name] = std::move(p1net);
+    }
+    connect_port(ctx, port1.net, cell2, port2_name);
+}
+
 NEXTPNR_NAMESPACE_END
diff --git a/common/design_utils.h b/common/design_utils.h
index 95975179..8a42d21f 100644
--- a/common/design_utils.h
+++ b/common/design_utils.h
@@ -82,6 +82,15 @@ template <typename F1> CellInfo *net_driven_by(const Context *ctx, const NetInfo
     }
 }
 
+// Connect a net to a port
+void connect_port(const Context *ctx, NetInfo *net, CellInfo *cell, IdString port_name);
+
+// Disconnect a net from a port
+void disconnect_port(const Context *ctx, CellInfo *cell, IdString port_name);
+
+// Connect two ports together
+void connect_ports(Context *ctx, CellInfo *cell1, IdString port1_name, CellInfo *cell2, IdString port2_name);
+
 void print_utilisation(const Context *ctx);
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/log.cc b/common/log.cc
index e30449ad..6b2d6065 100644
--- a/common/log.cc
+++ b/common/log.cc
@@ -177,7 +177,8 @@ void log_always(const char *format, ...)
 
 void log(const char *format, ...)
 {
-    if (log_quiet_warnings) return;
+    if (log_quiet_warnings)
+        return;
     va_list ap;
     va_start(ap, format);
     logv(format, ap);
@@ -186,7 +187,8 @@ void log(const char *format, ...)
 
 void log_info(const char *format, ...)
 {
-    if (log_quiet_warnings) return;
+    if (log_quiet_warnings)
+        return;
     va_list ap;
     va_start(ap, format);
     logv_info(format, ap);
@@ -195,7 +197,6 @@ void log_info(const char *format, ...)
 
 void log_warning(const char *format, ...)
 {
-    if (log_quiet_warnings) return;
     va_list ap;
     va_start(ap, format);
     logv_warning(format, ap);
@@ -204,7 +205,6 @@ void log_warning(const char *format, ...)
 
 void log_warning_noprefix(const char *format, ...)
 {
-    if (log_quiet_warnings) return;
     va_list ap;
     va_start(ap, format);
     logv_warning_noprefix(format, ap);
@@ -235,7 +235,8 @@ void log_cmd_error(const char *format, ...)
 
 void log_break()
 {
-    if (log_quiet_warnings) return;
+    if (log_quiet_warnings)
+        return;
     if (log_newline_count < 2)
         log_always("\n");
     if (log_newline_count < 2)
diff --git a/common/nextpnr.cc b/common/nextpnr.cc
index b04679ad..4e6407b2 100644
--- a/common/nextpnr.cc
+++ b/common/nextpnr.cc
@@ -89,6 +89,11 @@ WireId Context::getNetinfoSinkWire(const NetInfo *net_info, const PortRef &user_
 
 delay_t Context::getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &user_info) const
 {
+#ifdef ARCH_ECP5
+    if (net_info->is_global)
+        return 0;
+#endif
+
     WireId src_wire = getNetinfoSourceWire(net_info);
     if (src_wire == WireId())
         return 0;
@@ -99,8 +104,10 @@ delay_t Context::getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &us
 
     while (cursor != WireId() && cursor != src_wire) {
         auto it = net_info->wires.find(cursor);
+
         if (it == net_info->wires.end())
             break;
+
         PipId pip = it->second.pip;
         delay += getPipDelay(pip).maxDelay();
         delay += getWireDelay(cursor).maxDelay();
@@ -238,6 +245,11 @@ void Context::check() const
                 NPNR_ASSERT(ni == getBoundPipNet(w.second.pip));
             }
         }
+        if (ni->driver.cell != nullptr)
+            NPNR_ASSERT(ni->driver.cell->ports.at(ni->driver.port).net == ni);
+        for (auto user : ni->users) {
+            NPNR_ASSERT(user.cell->ports.at(user.port).net == ni);
+        }
     }
 
     for (auto w : getWires()) {
diff --git a/common/nextpnr.h b/common/nextpnr.h
index 29a85a10..59ae0323 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -157,11 +157,25 @@ struct GraphicElement
 
     enum style_t
     {
+        STYLE_GRID,
         STYLE_FRAME,    // Static "frame". Contrast between STYLE_INACTIVE and STYLE_ACTIVE
         STYLE_HIDDEN,   // Only display when object is selected or highlighted
         STYLE_INACTIVE, // Render using low-contrast color
         STYLE_ACTIVE,   // Render using high-contast color
 
+        // UI highlight groups
+        STYLE_HIGHLIGHTED0,
+        STYLE_HIGHLIGHTED1,
+        STYLE_HIGHLIGHTED2,
+        STYLE_HIGHLIGHTED3,
+        STYLE_HIGHLIGHTED4,
+        STYLE_HIGHLIGHTED5,
+        STYLE_HIGHLIGHTED6,
+        STYLE_HIGHLIGHTED7,
+
+        STYLE_SELECTED,
+        STYLE_HOVER,
+
         STYLE_MAX
     } style = STYLE_FRAME;
 
diff --git a/common/place_common.cc b/common/place_common.cc
index 5cdb96ef..da8ab37d 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -237,6 +237,12 @@ class ConstraintLegaliseWorker
                 return false;
             }
         }
+        // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later
+        for (auto tilebel : ctx->getBelsByTile(loc.x, loc.y)) {
+            CellInfo *tcell = ctx->getBoundBelCell(tilebel);
+            if (tcell && tcell->belStrength >= STRENGTH_STRONG)
+                return false;
+        }
         usedLocations.insert(loc);
         for (auto child : cell->constr_children) {
             IncreasingDiameterSearch xSearch, ySearch, zSearch;
@@ -329,7 +335,8 @@ class ConstraintLegaliseWorker
                 yRootSearch = IncreasingDiameterSearch(cell->constr_y);
 
             if (cell->constr_z == cell->UNCONSTR)
-                zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y));
+                zRootSearch =
+                        IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y));
             else
                 zRootSearch = IncreasingDiameterSearch(cell->constr_z);
             while (!xRootSearch.done()) {
diff --git a/common/placer1.cc b/common/placer1.cc
index 363b4d58..0d7c0701 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -81,7 +81,8 @@ class SAPlacer
         }
     }
 
-    ~SAPlacer() {
+    ~SAPlacer()
+    {
         for (auto &net : ctx->nets)
             net.second->udata = old_udata[net.second->udata];
     }
@@ -117,6 +118,12 @@ class SAPlacer
                               loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
                 }
 
+                auto bound_cell = ctx->getBoundBelCell(bel);
+                if (bound_cell) {
+                    log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
+                              cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
+                }
+
                 ctx->bindBel(bel, cell, STRENGTH_USER);
                 locked_bels.insert(bel);
                 placed_cells++;
@@ -351,7 +358,7 @@ class SAPlacer
     // Attempt a SA position swap, return true on success or false on failure
     bool try_swap_position(CellInfo *cell, BelId newBel)
     {
-        static std::vector<NetInfo*> updates;
+        static std::vector<NetInfo *> updates;
         updates.clear();
         BelId oldBel = cell->bel;
         CellInfo *other_cell = ctx->getBoundBelCell(newBel);
@@ -371,7 +378,8 @@ class SAPlacer
         for (const auto &port : cell->ports) {
             if (port.second.net != nullptr) {
                 auto &cost = costs[port.second.net->udata];
-                if (cost.new_cost == 0) continue;
+                if (cost.new_cost == 0)
+                    continue;
                 cost.new_cost = 0;
                 updates.emplace_back(port.second.net);
             }
@@ -381,7 +389,8 @@ class SAPlacer
             for (const auto &port : other_cell->ports)
                 if (port.second.net != nullptr) {
                     auto &cost = costs[port.second.net->udata];
-                    if (cost.new_cost == 0) continue;
+                    if (cost.new_cost == 0)
+                        continue;
                     cost.new_cost = 0;
                     updates.emplace_back(port.second.net);
                 }
@@ -483,7 +492,8 @@ class SAPlacer
     const float post_legalise_dia_scale = 1.5;
     Placer1Cfg cfg;
 
-    struct CostChange {
+    struct CostChange
+    {
         wirelen_t curr_cost;
         wirelen_t new_cost;
     };
diff --git a/common/router1.cc b/common/router1.cc
index e47a9ae3..34554711 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -541,6 +541,12 @@ void addNetRouteJobs(Context *ctx, const Router1Cfg &cfg, IdString net_name,
 {
     NetInfo *net_info = ctx->nets.at(net_name).get();
 
+#ifdef ARCH_ECP5
+    // ECP5 global nets currently appear part-unrouted due to arch database limitations
+    // Don't touch them in the router
+    if (net_info->is_global)
+        return;
+#endif
     if (net_info->driver.cell == nullptr)
         return;
 
diff --git a/common/settings.h b/common/settings.h
index e1f1166a..0c4a67db 100644
--- a/common/settings.h
+++ b/common/settings.h
@@ -38,7 +38,7 @@ class Settings
             if (!pair.second) {
                 return boost::lexical_cast<T>(pair.first->second);
             }
-            
+
         } catch (boost::bad_lexical_cast &) {
             log_error("Problem reading setting %s, using default value\n", name);
         }
@@ -51,7 +51,7 @@ class Settings
         auto pair = ctx->settings.emplace(id, std::to_string(value));
         if (!pair.second) {
             ctx->settings[pair.first->first] = value;
-        }        
+        }
     }
 
   private:
diff --git a/common/timing.cc b/common/timing.cc
index 62697353..d1a85779 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -48,6 +48,7 @@ struct Timing
         delay_t max_arrival;
         unsigned max_path_length = 0;
         delay_t min_remaining_budget;
+        bool false_startpoint = false;
     };
 
     Timing(Context *ctx, bool net_delays, bool update, PortRefVector *crit_path = nullptr,
@@ -93,12 +94,11 @@ struct Timing
                     topographical_order.emplace_back(o->net);
                     net_data.emplace(o->net, TimingData{clkToQ.maxDelay()});
                 } else {
-                    // TODO(eddieh): Generated clocks and ignored ports are currently added into the ordering as if it
-                    // was a regular timing start point in order to enable the full topographical order to be computed,
-                    // however these false nets (and their downstream paths) should not be in the final ordering
                     if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) {
                         topographical_order.emplace_back(o->net);
-                        net_data.emplace(o->net, TimingData{});
+                        TimingData td;
+                        td.false_startpoint = (portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE);
+                        net_data.emplace(o->net, std::move(td));
                     }
                     // Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and
                     // the current output port, increment fanin counter
@@ -112,19 +112,6 @@ struct Timing
             }
         }
 
-        // If these constant nets exist, add them to the topographical ordering too
-        // TODO(eddieh): Also false paths and should be removed from ordering
-        auto it = ctx->nets.find(ctx->id("$PACKER_VCC_NET"));
-        if (it != ctx->nets.end()) {
-            topographical_order.emplace_back(it->second.get());
-            net_data.emplace(it->second.get(), TimingData{});
-        }
-        it = ctx->nets.find(ctx->id("$PACKER_GND_NET"));
-        if (it != ctx->nets.end()) {
-            topographical_order.emplace_back(it->second.get());
-            net_data.emplace(it->second.get(), TimingData{});
-        }
-
         std::deque<NetInfo *> queue(topographical_order.begin(), topographical_order.end());
 
         // Now walk the design, from the start points identified previously, building up a topographical order
@@ -164,6 +151,22 @@ struct Timing
         }
 
         // Sanity check to ensure that all ports where fanins were recorded were indeed visited
+        if (!port_fanin.empty()) {
+            for (auto fanin : port_fanin) {
+                NetInfo *net = fanin.first->net;
+                if (net != nullptr) {
+                    log_info("   remaining fanin includes %s (net %s)\n", fanin.first->name.c_str(ctx),
+                             net->name.c_str(ctx));
+                    if (net->driver.cell != nullptr)
+                        log_info("        driver = %s.%s\n", net->driver.cell->name.c_str(ctx),
+                                 net->driver.port.c_str(ctx));
+                    for (auto net_user : net->users)
+                        log_info("        user: %s.%s\n", net_user.cell->name.c_str(ctx), net_user.port.c_str(ctx));
+                } else {
+                    log_info("   remaining fanin includes %s (no net)\n", fanin.first->name.c_str(ctx));
+                }
+            }
+        }
         NPNR_ASSERT(port_fanin.empty());
 
         // Go forwards topographically to find the maximum arrival time and max path length for each net
@@ -208,6 +211,8 @@ struct Timing
         // between all nets on the path
         for (auto net : boost::adaptors::reverse(topographical_order)) {
             auto &nd = net_data.at(net);
+            // Ignore false startpoints
+            if (nd.false_startpoint) continue;
             const delay_t net_length_plus_one = nd.max_path_length + 1;
             auto &net_min_remaining_budget = nd.min_remaining_budget;
             for (auto &usr : net->users) {