Merge branch 'redist_slack' into 'redist_slack'

Redist slack

See merge request eddiehung/nextpnr!10

1 files changed, 154 insertions, 120 deletions

diff --git a/common/timing.cc b/common/timing.cc
index 0e84dded..afaddbdf 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -26,16 +26,26 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack);
+typedef std::unordered_map<const PortInfo *, delay_t> UpdateMap;
+typedef std::list<const PortRef *> PortRefList;
+
+static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, UpdateMap *updates,
+                          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, UpdateMap *updates,
+                                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;
@@ -48,7 +58,8 @@ 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);
+                        delay_t path_budget = follow_net(ctx, net, path_length, slack - comb_delay, updates, min_slack,
+                                                         current_path, crit_path);
                         value = std::min(value, path_budget);
                     }
                 }
@@ -56,50 +67,107 @@ static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, de
         }
     }
 
-    if (value < user.budget) {
-        user.budget = value;
+    if (updates) {
+        auto ret = updates->emplace(&user.cell->ports.at(user.port), value);
+        if (!ret.second)
+            ret.first->second = std::min(value, ret.first->second);
     }
     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, UpdateMap *updates,
+                          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);
+        }
+        net_budget = std::min(net_budget,
+                              follow_user_port(ctx, usr, pl, slack - ctx->getNetinfoRouteDelay(net, i),
+                                               updates, min_slack, current_path, crit_path));
+        if (crit_path)
+            current_path->pop_back();
     }
     return net_budget;
 }
 
-void assign_budget(Context *ctx)
+static delay_t compute_min_slack(Context *ctx, UpdateMap *updates, 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
+                    delay_t slack = default_slack; // TODO: clock constraints
+                    delay_t clkToQ;
+                    if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ))
+                        slack -= clkToQ;
                     if (port.second.net)
-                        follow_net(ctx, port.second.net, 0, slack);
+                        follow_net(ctx, port.second.net, 0, slack, updates, min_slack, &current_path, crit_path);
                 }
             }
         }
     }
 
-    // Post-allocation check
+    return min_slack;
+}
+
+void assign_budget(Context *ctx)
+{
+    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;
+        }
+    }
+
+    UpdateMap updates;
+    delay_t min_slack = compute_min_slack(ctx, &updates, nullptr);
+
+    // If user has not specified a frequency, adjust the target frequency dynamically
+    // TODO(eddieh): Tune these factors
+    if (!ctx->user_freq) {
+        if (min_slack < 0)
+            ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack);
+        else
+            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);
+    }
+
+    // Update the budgets
     for (auto &net : ctx->nets) {
-        for (auto user : net.second->users) {
-            if (user.budget < 0)
+        for (size_t i = 0; i < net.second->users.size(); ++i) {
+            auto &user = net.second->users[i];
+            auto pi = &user.cell->ports.at(user.port);
+            auto it = updates.find(pi);
+            if (it == updates.end())
+                continue;
+            auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i) - it->second;
+            user.budget = ctx->getBudgetOverride(net.second.get(), i, budget);
+
+            // 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),
@@ -115,112 +183,25 @@ void assign_budget(Context *ctx)
     log_info("Checksum: 0x%08x\n", ctx->checksum());
 }
 
-typedef std::unordered_map<const PortInfo*, delay_t> updates_t;
-typedef std::unordered_map<const PortInfo*, delay_t> delays_t;
-
-static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays, updates_t& updates);
-
-// Follow a path, returning budget to annotate
-static delay_t follow_user_port_update(Context *ctx, PortRef &user, int path_length, delay_t slack, const delays_t& delays, updates_t& updates)
-{
-    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;
-    } else {
-        // Default to the path ending here, if no further paths found
-        value = slack / path_length;
-        // Follow outputs of the user
-        for (auto& port : user.cell->ports) {
-            if (port.second.type == PORT_OUT) {
-                delay_t comb_delay;
-                // Look up delay through this path
-                bool is_path = ctx->getCellDelay(user.cell, user.port, port.first, comb_delay);
-                if (is_path) {
-                    NetInfo *net = port.second.net;
-                    if (net) {
-                        delay_t path_budget = follow_net_update(ctx, net, path_length, slack - comb_delay, delays, updates);
-                        value = std::min(value, path_budget);
-                    }
-                }
-            }
-        }
-    }
-
-    auto ret = updates.emplace(&user.cell->ports.at(user.port), value);
-    if (!ret.second && value < ret.first->second) {
-        ret.first->second = value;
-    }
-    return value;
-}
-
-static delay_t follow_net_update(Context *ctx, NetInfo *net, int path_length, delay_t slack, const delays_t& delays,updates_t& updates)
-{
-    delay_t net_budget = slack / (path_length + 1);
-    for (auto& usr : net->users) {
-        net_budget = std::min(net_budget, follow_user_port_update(ctx, usr, path_length + 1, slack - get_or_default(delays, &usr.cell->ports.at(usr.port), 0.), delays, updates));
-    }
-    return net_budget;
-}
-
-void update_budget(Context *ctx, std::function<delay_t(Context*,WireId,WireId)> delay_fn)
+void update_budget(Context *ctx)
 {
-    delays_t delays;
-    updates_t updates;
-
-    // Compute the delay for every pin on every net
-    for (auto &n : ctx->nets) {
-        auto net = n.second.get();
-
-        int driver_x, driver_y;
-        bool driver_gb;
-        CellInfo *driver_cell = net->driver.cell;
-        if (!driver_cell)
-            continue;
-        if (driver_cell->bel == BelId())
-            continue;
-        ctx->estimatePosition(driver_cell->bel, driver_x, driver_y, driver_gb);
-        WireId drv_wire = ctx->getWireBelPin(driver_cell->bel, ctx->portPinFromId(net->driver.port));
-        if (driver_gb)
-            continue;
-        for (auto& load : net->users) {
-            if (load.cell == nullptr)
-                continue;
-            CellInfo *load_cell = load.cell;
-            if (load_cell->bel == BelId())
-                continue;
-            WireId user_wire = ctx->getWireBelPin(load_cell->bel, ctx->portPinFromId(load.port));
-            delay_t raw_wl = delay_fn(ctx, drv_wire, user_wire);
-            delays.emplace(&load_cell->ports.at(load.port), raw_wl);
-        }
-    }
-
-    // Go through all clocked drivers and distribute the available path slack evenly into every budget
-    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()) {
-                    if (port.second.net)
-                        follow_net_update(ctx, port.second.net, 0, delay_t(1.0e12 / ctx->target_freq) - get_or_default(delays, &port.second, 0.), delays, updates);
-                }
-            }
-        }
-    }
+    UpdateMap updates;
+    delay_t min_slack = compute_min_slack(ctx, &updates, nullptr);
 
     // Update the budgets
     for (auto &net : ctx->nets) {
-        for (auto& user : net.second->users) {
+        for (size_t i = 0; i < net.second->users.size(); ++i) {
+            auto &user = net.second->users[i];
             auto pi = &user.cell->ports.at(user.port);
+            auto budget = ctx->getNetinfoRouteDelay(net.second.get(), i);
             auto it = updates.find(pi);
-            if (it == updates.end()) continue;
-            auto budget = delays.at(pi) + it->second;
-            user.budget = ctx->getBudgetOverride(net.second->driver, budget);
+            if (it != updates.end())
+                budget -= it->second;
+            user.budget = ctx->getBudgetOverride(net.second.get(), i, budget);
 
             // Post-update check
             if (ctx->verbose) {
-                if (user.budget < 0)
+                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),
@@ -233,6 +214,59 @@ void update_budget(Context *ctx, std::function<delay_t(Context*,WireId,WireId)>
             }
         }
     }
+
+    // If user has not specified a frequency, adjust the frequency dynamically:
+    if (!ctx->user_freq) {
+        delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
+        ctx->target_freq = 1e12 / (default_slack - min_slack);
+        if (ctx->verbose)
+            log_info("minimum slack for this update = %d, target Fmax for next update = %.2f MHz\n", min_slack,
+                     ctx->target_freq / 1e6);
+    }
+}
+
+void compute_fmax(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 = compute_min_slack(ctx, nullptr, &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));
 }
 
 NEXTPNR_NAMESPACE_END