Merge branch 'redist_slack' into 'redist_slack'

# Conflicts:
#   common/timing.cc

13 files changed, 205 insertions, 42 deletions

diff --git a/common/nextpnr.h b/common/nextpnr.h
index 908b8266..38a313fd 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -475,6 +475,7 @@ struct Context : Arch, DeterministicRNG
     bool force = false;
     bool timing_driven = true;
     float target_freq = 12e6;
+    bool user_freq = false;
 
     Context(ArchArgs args) : Arch(args) {}
 
diff --git a/common/placer1.cc b/common/placer1.cc
index ee7225b5..c677a22a 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -152,6 +152,7 @@ class SAPlacer
         }
 
         int n_no_progress = 0;
+        wirelen_t min_metric = curr_metric;
         double avg_metric = curr_metric;
         temp = 10000;
 
@@ -177,6 +178,11 @@ class SAPlacer
                 }
             }
 
+            if (curr_metric < min_metric) {
+                min_metric = curr_metric;
+                improved = true;
+            }
+
             // Heuristic to improve placement on the 8k
             if (improved)
                 n_no_progress = 0;
@@ -230,6 +236,8 @@ class SAPlacer
                 diameter *= post_legalise_dia_scale;
                 ctx->shuffle(autoplaced);
                 assign_budget(ctx);
+            } else {
+                assign_budget(ctx, true /* quiet */);
             }
 
             // Recalculate total metric entirely to avoid rounding errors
@@ -264,6 +272,7 @@ class SAPlacer
                 }
             }
         }
+        timing_analysis(ctx, true /* print_fmax */);
         ctx->unlock();
         return true;
     }
@@ -379,8 +388,6 @@ class SAPlacer
         // SA acceptance criterea
         if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
             n_accept++;
-            if (delta < 2)
-                improved = true;
         } else {
             if (other != IdString())
                 ctx->unbindBel(oldBel);
diff --git a/common/router1.cc b/common/router1.cc
index 4ef7df64..0bd257fd 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -22,6 +22,7 @@
 
 #include "log.h"
 #include "router1.h"
+#include "timing.h"
 
 namespace {
 
@@ -615,6 +616,8 @@ bool router1(Context *ctx)
             if (ctx->verbose || iterCnt == 1)
                 log_info("routing queue contains %d jobs.\n", int(jobQueue.size()));
 
+            assign_budget(ctx, true /* quiet */);
+
             bool printNets = ctx->verbose && (jobQueue.size() < 10);
 
             while (!jobQueue.empty()) {
@@ -811,6 +814,7 @@ bool router1(Context *ctx)
 #ifndef NDEBUG
         ctx->check();
 #endif
+        timing_analysis(ctx, true /* print_fmax */, true /* print_path */);
         ctx->unlock();
         return true;
     } catch (log_execution_error_exception) {
diff --git a/common/timing.cc b/common/timing.cc
index 4486fc24..b1a5619d 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -22,19 +22,29 @@
 #include <unordered_map>
 #include <utility>
 #include "log.h"
+#include "util.h"
 
 NEXTPNR_NAMESPACE_BEGIN
 
-static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack);
+typedef std::list<const PortRef *> PortRefList;
+
+static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
+                          PortRefList *current_path, PortRefList *crit_path);
 
 // Follow a path, returning budget to annotate
-static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack)
+static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, bool update,
+                                delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path)
 {
     delay_t value;
     if (ctx->getPortClock(user.cell, user.port) != IdString()) {
         // At the end of a timing path (arguably, should check setup time
         // here too)
         value = slack / path_length;
+        if (slack < min_slack) {
+            min_slack = slack;
+            if (crit_path)
+                *crit_path = *current_path;
+        }
     } else {
         // Default to the path ending here, if no further paths found
         value = slack / path_length;
@@ -47,74 +57,165 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de
                 if (is_path) {
                     NetInfo *net = port.second.net;
                     if (net) {
-                        delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay.maxDelay());
+                        delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay, update, min_slack,
+                                                         current_path, crit_path);
                         value = std::min(value, path_budget);
                     }
                 }
             }
         }
     }
-
-    if (value < user.budget) {
-        user.budget = value;
-    }
     return value;
 }
 
-static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack)
+static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
+                          PortRefList *current_path, PortRefList *crit_path)
 {
     delay_t net_budget = slack / (path_length + 1);
-    for (auto &usr : net->users) {
-        net_budget = std::min(net_budget, follow_user_port(ctx, usr, path_length + 1, slack));
+    for (unsigned i = 0; i < net->users.size(); ++i) {
+        auto &usr = net->users[i];
+        if (crit_path)
+            current_path->push_back(&usr);
+        // If budget override is less than existing budget, then do not increment path length
+        int pl = path_length + 1;
+        auto budget = ctx->getBudgetOverride(net, i, net_budget);
+        if (budget < net_budget) {
+            net_budget = budget;
+            pl = std::max(1, path_length);
+        }
+        auto delay = ctx->getNetinfoRouteDelay(net, i);
+        net_budget = std::min(
+                net_budget, follow_user_port(ctx, usr, pl, slack - delay, update, min_slack, current_path, crit_path));
+        if (update)
+            usr.budget = std::min(usr.budget, delay + net_budget);
+        if (crit_path)
+            current_path->pop_back();
     }
     return net_budget;
 }
 
-void assign_budget(Context *ctx)
+static delay_t walk_paths(Context *ctx, bool update, PortRefList *crit_path)
 {
-    log_break();
-    log_info("Annotating ports with timing budgets\n");
-    // Clear delays to a very high value first
     delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
-    for (auto &net : ctx->nets) {
-        for (auto &usr : net.second->users) {
-            usr.budget = default_slack;
-        }
-    }
-    // Go through all clocked drivers and set up paths
+    delay_t min_slack = default_slack;
+
+    PortRefList current_path;
+
+    // Go through all clocked drivers and distribute the available path
+    //   slack evenly into the budget of every sink on the path ---
+    //   record this value into the UpdateMap
     for (auto &cell : ctx->cells) {
         for (auto port : cell.second->ports) {
             if (port.second.type == PORT_OUT) {
                 IdString clock_domain = ctx->getPortClock(cell.second.get(), port.first);
                 if (clock_domain != IdString()) {
-                    delay_t slack = delay_t(1.0e12 / ctx->target_freq); // TODO: clock constraints
-                    DelayInfo clkToQ;
+                    delay_t slack = default_slack; // TODO: clock constraints
+                    delay_t clkToQ;
                     if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ))
                         slack -= clkToQ.maxDelay();
                     if (port.second.net)
-                        follow_net(ctx, port.second.net, 0, slack);
+                        follow_net(ctx, port.second.net, 0, slack, update, min_slack, &current_path, crit_path);
                 }
             }
         }
     }
 
-    // Post-allocation check
+    return min_slack;
+}
+
+void assign_budget(Context *ctx, bool quiet)
+{
+    if (!quiet) {
+        log_break();
+        log_info("Annotating ports with timing budgets\n");
+    }
+
+    // Clear delays to a very high value first
+    delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
     for (auto &net : ctx->nets) {
-        for (auto user : net.second->users) {
-            if (user.budget < 0)
-                log_warning("port %s.%s, connected to net '%s', has negative "
-                            "timing budget of %fns\n",
-                            user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
-                            ctx->getDelayNS(user.budget));
-            if (ctx->verbose)
-                log_info("port %s.%s, connected to net '%s', has "
-                         "timing budget of %fns\n",
-                         user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
-                         ctx->getDelayNS(user.budget));
+        for (auto &usr : net.second->users) {
+            usr.budget = default_slack;
+        }
+    }
+
+    delay_t min_slack = walk_paths(ctx, true, nullptr);
+
+    if (!quiet || ctx->verbose) {
+        for (auto &net : ctx->nets) {
+            for (auto &user : net.second->users) {
+                // Post-update check
+                if (ctx->user_freq && user.budget < 0)
+                    log_warning("port %s.%s, connected to net '%s', has negative "
+                                "timing budget of %fns\n",
+                                user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
+                                ctx->getDelayNS(user.budget));
+                else if (ctx->verbose)
+                    log_info("port %s.%s, connected to net '%s', has "
+                             "timing budget of %fns\n",
+                             user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
+                             ctx->getDelayNS(user.budget));
+            }
         }
     }
 
-    log_info("Checksum: 0x%08x\n", ctx->checksum());
+    // If user has not specified a frequency, dynamically adjust the target 
+    //   frequency to be the current maximum
+    if (!ctx->user_freq) {
+        ctx->target_freq = 1e12 / (default_slack - 1.2 * min_slack);
+        if (ctx->verbose)
+            log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack,
+                     ctx->target_freq / 1e6);
+    }
+
+    if (!quiet)
+        log_info("Checksum: 0x%08x\n", ctx->checksum());
+}
+
+delay_t timing_analysis(Context *ctx, bool print_fmax, bool print_path)
+{
+    delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
+    PortRefList crit_path;
+    delay_t min_slack = walk_paths(ctx, false, &crit_path);
+    if (print_path) {
+        delay_t total = 0;
+        log_break();
+        log_info("Critical path report:\n");
+        log_info("curr total\n");
+        auto &front = crit_path.front();
+        auto &front_port = front->cell->ports.at(front->port);
+        auto &front_driver = front_port.net->driver;
+        auto last_port = ctx->getPortClock(front_driver.cell, front_driver.port);
+        for (auto sink : crit_path) {
+            auto sink_cell = sink->cell;
+            auto &port = sink_cell->ports.at(sink->port);
+            auto net = port.net;
+            unsigned i = 0;
+            for (auto &usr : net->users)
+                if (&usr == sink)
+                    break;
+                else
+                    ++i;
+            auto &driver = net->driver;
+            auto driver_cell = driver.cell;
+            delay_t comb_delay;
+            ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay);
+            total += comb_delay;
+            log_info("%4d %4d  Source %s.%s\n", comb_delay, total, driver_cell->name.c_str(ctx),
+                     driver.port.c_str(ctx));
+            delay_t net_delay = ctx->getNetinfoRouteDelay(net, i);
+            total += net_delay;
+            auto driver_loc = ctx->getBelLocation(driver_cell->bel);
+            auto sink_loc = ctx->getBelLocation(sink_cell->bel);
+            log_info("%4d %4d    Net %s budget %d (%d,%d) -> (%d,%d)\n", net_delay, total, net->name.c_str(ctx),
+                     sink->budget, driver_loc.x, driver_loc.y, sink_loc.x, sink_loc.y);
+            log_info("                Sink %s.%s\n", sink_cell->name.c_str(ctx), sink->port.c_str(ctx));
+            last_port = sink->port;
+        }
+        log_break();
+    }
+    if (print_fmax)
+        log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack));
+    return min_slack;
 }
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/timing.h b/common/timing.h
index 025e4a76..d0159d5c 100644
--- a/common/timing.h
+++ b/common/timing.h
@@ -24,8 +24,12 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-// Assign "budget" values for all user ports in the design
-void assign_budget(Context *ctx);
+// Evenly redistribute the total path slack amongst all sinks on each path
+void assign_budget(Context *ctx, bool quiet = false);
+
+// Perform timing analysis and return the minimum path slack,
+//   optionally, print out the fmax and critical path
+delay_t timing_analysis(Context *ctx, bool print_fmax = false, bool print_path = false);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/ecp5/arch.cc b/ecp5/arch.cc
index 2b40e79a..36cefded 100644
--- a/ecp5/arch.cc
+++ b/ecp5/arch.cc
@@ -413,6 +413,8 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const
     return 200 * (abs(src.location.x - dst.location.x) + abs(src.location.y - dst.location.y));
 }
 
+delay_t Arch::getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const { return budget; }
+
 // -----------------------------------------------------------------------
 
 bool Arch::place() { return placer1(getCtx()); }
diff --git a/ecp5/arch.h b/ecp5/arch.h
index 2421428f..df0df311 100644
--- a/ecp5/arch.h
+++ b/ecp5/arch.h
@@ -780,6 +780,7 @@ struct Arch : BaseCtx
     delay_t getRipupDelayPenalty() const { return 200; }
     float getDelayNS(delay_t v) const { return v * 0.001; }
     uint32_t getDelayChecksum(delay_t v) const { return v; }
+    delay_t getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const;
 
     // -------------------------------------------------
 
diff --git a/ecp5/main.cc b/ecp5/main.cc
index 90096855..68660ced 100644
--- a/ecp5/main.cc
+++ b/ecp5/main.cc
@@ -169,8 +169,12 @@ int main(int argc, char *argv[])
 
             if (!ctx->pack() && !ctx->force)
                 log_error("Packing design failed.\n");
-            if (vm.count("freq"))
+            if (vm.count("freq")) {
                 ctx->target_freq = vm["freq"].as<double>() * 1e6;
+                ctx->user_freq = true;
+            } else {
+                log_warning("Target frequency not specified. Will optimise for max frequency.\n");
+            }
             assign_budget(ctx.get());
             ctx->check();
             print_utilisation(ctx.get());
diff --git a/generic/arch.cc b/generic/arch.cc
index 892bb0fd..daaa8118 100644
--- a/generic/arch.cc
+++ b/generic/arch.cc
@@ -403,6 +403,8 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const
     return (dx + dy) * grid_distance_to_delay;
 }
 
+delay_t Arch::getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const { return budget; }
+
 // ---------------------------------------------------------------
 
 bool Arch::place() { return placer1(getCtx()); }
diff --git a/generic/arch.h b/generic/arch.h
index 9a0da75b..de06f730 100644
--- a/generic/arch.h
+++ b/generic/arch.h
@@ -198,6 +198,7 @@ struct Arch : BaseCtx
     delay_t getRipupDelayPenalty() const { return 1.0; }
     float getDelayNS(delay_t v) const { return v; }
     uint32_t getDelayChecksum(delay_t v) const { return 0; }
+    delay_t getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const;
 
     bool pack() { return true; }
     bool place();
diff --git a/ice40/arch.cc b/ice40/arch.cc
index f3004155..e15abdd1 100644
--- a/ice40/arch.cc
+++ b/ice40/arch.cc
@@ -618,9 +618,40 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const
     //     offset = 500;
     // }
 
+    // Estimate for output mux
+    for (const auto &bp : getWireBelPins(src)) {
+        if (bp.pin == PIN_O && getBelType(bp.bel) == TYPE_ICESTORM_LC) {
+            offset += 330;
+            break;
+        }
+    }
+
+    // Estimate for input mux
+    for (const auto &bp : getWireBelPins(dst)) {
+        if ((bp.pin == PIN_I0 || bp.pin == PIN_I1 || bp.pin == PIN_I2 || bp.pin == PIN_I3) &&
+            getBelType(bp.bel) == TYPE_ICESTORM_LC) {
+            offset += 260;
+            break;
+        }
+    }
+
     return xscale * abs(xd) + yscale * abs(yd) + offset;
 }
 
+delay_t Arch::getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const
+{
+    const auto &driver = net_info->driver;
+    if (driver.port == id_cout) {
+        const auto &sink = net_info->users[user_idx];
+        auto driver_loc = getBelLocation(driver.cell->bel);
+        auto sink_loc = getBelLocation(sink.cell->bel);
+        if (driver_loc.y == sink_loc.y)
+            return 0;
+        return 250;
+    }
+    return budget;
+}
+
 // -----------------------------------------------------------------------
 
 bool Arch::place() { return placer1(getCtx()); }
diff --git a/ice40/arch.h b/ice40/arch.h
index 7efa733c..f81fd21d 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -701,6 +701,7 @@ struct Arch : BaseCtx
     delay_t getRipupDelayPenalty() const { return 200; }
     float getDelayNS(delay_t v) const { return v * 0.001; }
     uint32_t getDelayChecksum(delay_t v) const { return v; }
+    delay_t getBudgetOverride(NetInfo *net_info, int user_idx, delay_t budget) const;
 
     // -------------------------------------------------
 
diff --git a/ice40/main.cc b/ice40/main.cc
index 32815b26..865eea9e 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -363,8 +363,12 @@ int main(int argc, char *argv[])
             }
         }
 
-        if (vm.count("freq"))
+        if (vm.count("freq")) {
             ctx->target_freq = vm["freq"].as<double>() * 1e6;
+            ctx->user_freq = true;
+        } else {
+            log_warning("Target frequency not specified. Will optimise for max frequency.\n");
+        }
 
         ctx->timing_driven = true;
         if (vm.count("no-tmdriv"))