From 27a79a3a4f464f2d038f66737d78aaa2fb6f2703 Mon Sep 17 00:00:00 2001
From: Eddie Hung <e.hung@imperial.ac.uk>
Date: Sat, 21 Jul 2018 01:55:20 -0700
Subject: Update comment

---
 common/timing.cc | 118 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 118 insertions(+)

diff --git a/common/timing.cc b/common/timing.cc
index 3a48935f..479dba26 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -22,6 +22,7 @@
 #include <unordered_map>
 #include <utility>
 #include "log.h"
+#include "util.h"
 
 NEXTPNR_NAMESPACE_BEGIN
 
@@ -114,4 +115,121 @@ 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)
+{
+    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 = ctx->estimateDelay(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);
+                }
+            }
+        }
+    }
+
+    // Update the budgets
+    for (auto &net : ctx->nets) {
+        for (auto& user : net.second->users) {
+            auto pi = &user.cell->ports.at(user.port);
+            auto it = updates.find(pi);
+            if (it == updates.end()) continue;
+            user.budget = delays.at(pi) + it->second;
+
+            // Post-update check
+//            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));
+        }
+    }
+}
+
 NEXTPNR_NAMESPACE_END
-- 
cgit v1.2.3