timing: Replace all users of criticality with new engine

Signed-off-by: gatecat <gatecat@ds0.me>

4 files changed, 52 insertions, 229 deletions

diff --git a/common/router2.cc b/common/router2.cc
index 1b7a6fed..b2c5d9ba 100644
--- a/common/router2.cc
+++ b/common/router2.cc
@@ -112,16 +112,14 @@ struct Router2
     Context *ctx;
     Router2Cfg cfg;
 
-    Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg) {}
+    Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg), tmg(ctx) { tmg.setup(); }
 
     // Use 'udata' for fast net lookups and indexing
     std::vector<NetInfo *> nets_by_udata;
     std::vector<PerNetData> nets;
 
     bool timing_driven;
-
-    // Criticality data from timing analysis
-    NetCriticalityMap net_crit;
+    TimingAnalyser tmg;
 
     void setup_nets()
     {
@@ -1175,18 +1173,13 @@ struct Router2
             if (timing_driven && (int(route_queue.size()) > (int(nets_by_udata.size()) / 50))) {
                 // Heuristic: reduce runtime by skipping STA in the case of a "long tail" of a few
                 // congested nodes
-                get_criticalities(ctx, &net_crit);
+                tmg.run();
                 for (auto n : route_queue) {
-                    IdString name = nets_by_udata.at(n)->name;
-                    auto fnd = net_crit.find(name);
+                    NetInfo *ni = nets_by_udata.at(n);
                     auto &net = nets.at(n);
                     net.max_crit = 0;
-                    if (fnd == net_crit.end())
-                        continue;
-                    for (int i = 0; i < int(fnd->second.criticality.size()); i++) {
-                        float c = fnd->second.criticality.at(i);
-                        for (auto &a : net.arcs.at(i))
-                            a.arc_crit = c;
+                    for (auto &usr : ni->users) {
+                        float c = tmg.get_criticality(CellPortKey(usr));
                         net.max_crit = std::max(net.max_crit, c);
                     }
                 }
diff --git a/common/timing.cc b/common/timing.cc
index f4c0d297..dd38ee45 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -273,6 +273,8 @@ void TimingAnalyser::reset_times()
             dp.second.budget = 0;
         }
         port.second.worst_crit = 0;
+        port.second.worst_setup_slack = std::numeric_limits<delay_t>::max();
+        port.second.worst_hold_slack = std::numeric_limits<delay_t>::max();
     }
 }
 
@@ -440,9 +442,12 @@ void TimingAnalyser::compute_slack()
             if (!setup_only)
                 pdp.second.hold_slack = arr.value.minDelay() - req.value.maxDelay();
             pdp.second.max_path_length = arr.path_length + req.path_length;
+            pd.worst_setup_slack = std::min(pd.worst_setup_slack, pdp.second.setup_slack);
             dp.worst_setup_slack = std::min(dp.worst_setup_slack, pdp.second.setup_slack);
-            if (!setup_only)
+            if (!setup_only) {
+                pd.worst_hold_slack = std::min(pd.worst_hold_slack, pdp.second.hold_slack);
                 dp.worst_hold_slack = std::min(dp.worst_hold_slack, pdp.second.hold_slack);
+            }
         }
     }
 }
@@ -615,7 +620,6 @@ struct CriticalPath
 };
 
 typedef std::unordered_map<ClockPair, CriticalPath> CriticalPathMap;
-typedef std::unordered_map<IdString, NetCriticalityInfo> NetCriticalityMap;
 
 struct Timing
 {
@@ -625,7 +629,6 @@ struct Timing
     delay_t min_slack;
     CriticalPathMap *crit_path;
     DelayFrequency *slack_histogram;
-    NetCriticalityMap *net_crit;
     IdString async_clock;
 
     struct TimingData
@@ -641,10 +644,9 @@ struct Timing
     };
 
     Timing(Context *ctx, bool net_delays, bool update, CriticalPathMap *crit_path = nullptr,
-           DelayFrequency *slack_histogram = nullptr, NetCriticalityMap *net_crit = nullptr)
+           DelayFrequency *slack_histogram = nullptr)
             : ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->setting<float>("target_freq")),
-              crit_path(crit_path), slack_histogram(slack_histogram), net_crit(net_crit),
-              async_clock(ctx->id("$async$"))
+              crit_path(crit_path), slack_histogram(slack_histogram), async_clock(ctx->id("$async$"))
     {
     }
 
@@ -1025,156 +1027,6 @@ struct Timing
                 std::reverse(cp_ports.begin(), cp_ports.end());
             }
         }
-
-        if (net_crit) {
-            NPNR_ASSERT(crit_path);
-            // Go through in reverse topological order to set required times
-            for (auto net : boost::adaptors::reverse(topological_order)) {
-                if (!net_data.count(net))
-                    continue;
-                auto &nd_map = net_data.at(net);
-                for (auto &startdomain : nd_map) {
-                    auto &nd = startdomain.second;
-                    if (nd.false_startpoint)
-                        continue;
-                    if (startdomain.first.clock == async_clock)
-                        continue;
-                    if (nd.min_required.empty())
-                        nd.min_required.resize(net->users.size(), std::numeric_limits<delay_t>::max());
-                    delay_t net_min_required = std::numeric_limits<delay_t>::max();
-                    for (size_t i = 0; i < net->users.size(); i++) {
-                        auto &usr = net->users.at(i);
-                        auto net_delay = ctx->getNetinfoRouteDelay(net, usr);
-                        int port_clocks;
-                        TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, port_clocks);
-                        if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) {
-                            auto process_endpoint = [&](IdString clksig, ClockEdge edge, delay_t setup) {
-                                delay_t period;
-                                // Set default period
-                                if (edge == startdomain.first.edge) {
-                                    period = clk_period;
-                                } else {
-                                    period = clk_period / 2;
-                                }
-                                if (clksig != async_clock) {
-                                    if (ctx->nets.at(clksig)->clkconstr) {
-                                        if (edge == startdomain.first.edge) {
-                                            // same edge
-                                            period = ctx->nets.at(clksig)->clkconstr->period.minDelay();
-                                        } else if (edge == RISING_EDGE) {
-                                            // falling -> rising
-                                            period = ctx->nets.at(clksig)->clkconstr->low.minDelay();
-                                        } else if (edge == FALLING_EDGE) {
-                                            // rising -> falling
-                                            period = ctx->nets.at(clksig)->clkconstr->high.minDelay();
-                                        }
-                                    }
-                                }
-                                nd.min_required.at(i) = std::min(period - setup, nd.min_required.at(i));
-                            };
-                            if (portClass == TMG_REGISTER_INPUT) {
-                                for (int j = 0; j < port_clocks; j++) {
-                                    TimingClockingInfo clkInfo = ctx->getPortClockingInfo(usr.cell, usr.port, j);
-                                    const NetInfo *clknet = get_net_or_empty(usr.cell, clkInfo.clock_port);
-                                    IdString clksig = clknet ? clknet->name : async_clock;
-                                    process_endpoint(clksig, clknet ? clkInfo.edge : RISING_EDGE,
-                                                     clkInfo.setup.maxDelay());
-                                }
-                            } else {
-                                process_endpoint(async_clock, RISING_EDGE, 0);
-                            }
-                        }
-                        net_min_required = std::min(net_min_required, nd.min_required.at(i) - net_delay);
-                    }
-                    PortRef &drv = net->driver;
-                    if (drv.cell == nullptr)
-                        continue;
-                    for (const auto &port : drv.cell->ports) {
-                        if (port.second.type != PORT_IN || !port.second.net)
-                            continue;
-                        DelayQuad comb_delay;
-                        bool is_path = ctx->getCellDelay(drv.cell, port.first, drv.port, comb_delay);
-                        if (!is_path)
-                            continue;
-                        int cc;
-                        auto pclass = ctx->getPortTimingClass(drv.cell, port.first, cc);
-                        if (pclass != TMG_COMB_INPUT)
-                            continue;
-                        NetInfo *sink_net = port.second.net;
-                        if (net_data.count(sink_net) && net_data.at(sink_net).count(startdomain.first)) {
-                            auto &sink_nd = net_data.at(sink_net).at(startdomain.first);
-                            if (sink_nd.min_required.empty())
-                                sink_nd.min_required.resize(sink_net->users.size(),
-                                                            std::numeric_limits<delay_t>::max());
-                            for (size_t i = 0; i < sink_net->users.size(); i++) {
-                                auto &user = sink_net->users.at(i);
-                                if (user.cell == drv.cell && user.port == port.first) {
-                                    sink_nd.min_required.at(i) = std::min(sink_nd.min_required.at(i),
-                                                                          net_min_required - comb_delay.maxDelay());
-                                    break;
-                                }
-                            }
-                        }
-                    }
-                }
-            }
-            std::unordered_map<ClockEvent, delay_t> worst_slack;
-
-            // Assign slack values
-            for (auto &net_entry : net_data) {
-                const NetInfo *net = net_entry.first;
-                for (auto &startdomain : net_entry.second) {
-                    auto &nd = startdomain.second;
-                    if (startdomain.first.clock == async_clock)
-                        continue;
-                    if (nd.min_required.empty())
-                        continue;
-                    auto &nc = (*net_crit)[net->name];
-                    if (nc.slack.empty())
-                        nc.slack.resize(net->users.size(), std::numeric_limits<delay_t>::max());
-
-                    for (size_t i = 0; i < net->users.size(); i++) {
-                        delay_t slack = nd.min_required.at(i) -
-                                        (nd.max_arrival + ctx->getNetinfoRouteDelay(net, net->users.at(i)));
-
-                        if (worst_slack.count(startdomain.first))
-                            worst_slack.at(startdomain.first) = std::min(worst_slack.at(startdomain.first), slack);
-                        else
-                            worst_slack[startdomain.first] = slack;
-                        nc.slack.at(i) = slack;
-                    }
-                    if (ctx->debug)
-                        log_break();
-                }
-            }
-            // Assign criticality values
-            for (auto &net_entry : net_data) {
-                const NetInfo *net = net_entry.first;
-                for (auto &startdomain : net_entry.second) {
-                    if (startdomain.first.clock == async_clock)
-                        continue;
-                    auto &nd = startdomain.second;
-                    if (nd.min_required.empty())
-                        continue;
-                    auto &nc = (*net_crit)[net->name];
-                    if (nc.slack.empty())
-                        continue;
-                    if (nc.criticality.empty())
-                        nc.criticality.resize(net->users.size(), 0);
-                    // Only consider intra-clock paths for criticality
-                    if (!crit_path->count(ClockPair{startdomain.first, startdomain.first}))
-                        continue;
-                    delay_t dmax = crit_path->at(ClockPair{startdomain.first, startdomain.first}).path_delay;
-                    for (size_t i = 0; i < net->users.size(); i++) {
-                        float criticality =
-                                1.0f - ((float(nc.slack.at(i)) - float(worst_slack.at(startdomain.first))) / dmax);
-                        nc.criticality.at(i) = std::min<double>(1.0, std::max<double>(0.0, criticality));
-                    }
-                    nc.max_path_length = nd.max_path_length;
-                    nc.cd_worst_slack = worst_slack.at(startdomain.first);
-                }
-            }
-        }
         return min_slack;
     }
 
@@ -1528,16 +1380,4 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_fmax, bool p
     }
 }
 
-void get_criticalities(Context *ctx, NetCriticalityMap *net_crit)
-{
-    CriticalPathMap crit_paths;
-    net_crit->clear();
-    Timing timing(ctx, true, true, &crit_paths, nullptr, net_crit);
-    timing.walk_paths();
-
-    // Test the new timing analyser, too
-    TimingAnalyser sta_v2(ctx);
-    sta_v2.setup();
-}
-
 NEXTPNR_NAMESPACE_END
diff --git a/common/timing.h b/common/timing.h
index b7880667..0ba1d479 100644
--- a/common/timing.h
+++ b/common/timing.h
@@ -131,6 +131,14 @@ struct TimingAnalyser
     void print_report();
 
     float get_criticality(CellPortKey port) const { return ports.at(port).worst_crit; }
+    float get_setup_slack(CellPortKey port) const { return ports.at(port).worst_setup_slack; }
+    float get_domain_setup_slack(CellPortKey port) const
+    {
+        delay_t slack = std::numeric_limits<delay_t>::max();
+        for (const auto &dp : ports.at(port).domain_pairs)
+            slack = std::min(slack, domain_pairs.at(dp.first).worst_setup_slack);
+        return slack;
+    }
 
     bool setup_only = false;
 
@@ -219,8 +227,9 @@ struct TimingAnalyser
         std::vector<CellArc> cell_arcs;
         // routing delay into this port (input ports only)
         DelayPair route_delay;
-        // worst criticality across domain pairs
+        // worst criticality and slack across domain pairs
         float worst_crit;
+        delay_t worst_setup_slack, worst_hold_slack;
     };
 
     struct PerDomain
@@ -267,19 +276,6 @@ void assign_budget(Context *ctx, bool quiet = false);
 void timing_analysis(Context *ctx, bool slack_histogram = true, bool print_fmax = true, bool print_path = false,
                      bool warn_on_failure = false);
 
-// Data for the timing optimisation algorithm
-struct NetCriticalityInfo
-{
-    // One each per user
-    std::vector<delay_t> slack;
-    std::vector<float> criticality;
-    unsigned max_path_length = 0;
-    delay_t cd_worst_slack = std::numeric_limits<delay_t>::max();
-};
-
-typedef std::unordered_map<IdString, NetCriticalityInfo> NetCriticalityMap;
-void get_criticalities(Context *ctx, NetCriticalityMap *net_crit);
-
 NEXTPNR_NAMESPACE_END
 
 #endif
diff --git a/common/timing_opt.cc b/common/timing_opt.cc
index 28b7f2cf..51c27cc6 100644
--- a/common/timing_opt.cc
+++ b/common/timing_opt.cc
@@ -79,16 +79,17 @@ NEXTPNR_NAMESPACE_BEGIN
 class TimingOptimiser
 {
   public:
-    TimingOptimiser(Context *ctx, TimingOptCfg cfg) : ctx(ctx), cfg(cfg){};
+    TimingOptimiser(Context *ctx, TimingOptCfg cfg) : ctx(ctx), cfg(cfg), tmg(ctx){};
     bool optimise()
     {
         log_info("Running timing-driven placement optimisation...\n");
         ctx->lock();
         if (ctx->verbose)
             timing_analysis(ctx, false, true, false, false);
+        tmg.setup();
         for (int i = 0; i < 30; i++) {
             log_info("   Iteration %d...\n", i);
-            get_criticalities(ctx, &net_crit);
+            tmg.run();
             setup_delay_limits();
             auto crit_paths = find_crit_paths(0.98, 50000);
             for (auto &path : crit_paths)
@@ -109,18 +110,14 @@ class TimingOptimiser
             for (auto usr : ni->users) {
                 max_net_delay[std::make_pair(usr.cell->name, usr.port)] = std::numeric_limits<delay_t>::max();
             }
-            if (!net_crit.count(net.first))
-                continue;
-            auto &nc = net_crit.at(net.first);
-            if (nc.slack.empty())
-                continue;
             for (size_t i = 0; i < ni->users.size(); i++) {
                 auto &usr = ni->users.at(i);
                 delay_t net_delay = ctx->getNetinfoRouteDelay(ni, usr);
-                if (nc.max_path_length != 0) {
-                    max_net_delay[std::make_pair(usr.cell->name, usr.port)] =
-                            net_delay + ((nc.slack.at(i) - nc.cd_worst_slack) / 10);
-                }
+                delay_t slack = tmg.get_setup_slack(CellPortKey(usr));
+                delay_t domain_slack = tmg.get_domain_setup_slack(CellPortKey(usr));
+                if (slack == std::numeric_limits<delay_t>::max())
+                    continue;
+                max_net_delay[std::make_pair(usr.cell->name, usr.port)] = net_delay + ((slack - domain_slack) / 10);
             }
         }
     }
@@ -283,12 +280,18 @@ class TimingOptimiser
         for (auto net : netnames) {
             if (crit_nets.size() >= max_count)
                 break;
-            if (!net_crit.count(net))
-                continue;
-            auto crit_user = std::max_element(net_crit[net].criticality.begin(), net_crit[net].criticality.end());
-            if (*crit_user > crit_thresh)
-                crit_nets.push_back(
-                        std::make_pair(ctx->nets[net].get(), crit_user - net_crit[net].criticality.begin()));
+            float highest_crit = 0;
+            size_t crit_user_idx = 0;
+            NetInfo *ni = ctx->nets.at(net).get();
+            for (size_t i = 0; i < ni->users.size(); i++) {
+                float crit = tmg.get_criticality(CellPortKey(ni->users.at(i)));
+                if (crit > highest_crit) {
+                    highest_crit = crit;
+                    crit_user_idx = i;
+                }
+            }
+            if (highest_crit > crit_thresh)
+                crit_nets.push_back(std::make_pair(ni, crit_user_idx));
         }
 
         auto port_user_index = [](CellInfo *cell, PortInfo &port) -> size_t {
@@ -325,8 +328,6 @@ class TimingOptimiser
                     NetInfo *pn = port.second.net;
                     if (pn == nullptr)
                         continue;
-                    if (!net_crit.count(pn->name) || net_crit.at(pn->name).criticality.empty())
-                        continue;
                     int ccount;
                     DelayQuad combDelay;
                     TimingPortClass tpclass = ctx->getPortTimingClass(cell, port.first, ccount);
@@ -336,7 +337,7 @@ class TimingOptimiser
                     if (!is_path)
                         continue;
                     size_t user_idx = port_user_index(cell, port.second);
-                    float usr_crit = net_crit.at(pn->name).criticality.at(user_idx);
+                    float usr_crit = tmg.get_criticality(CellPortKey(cell->name, port.first));
                     if (used_ports.count(&(pn->users.at(user_idx))))
                         continue;
                     if (usr_crit >= max_crit) {
@@ -364,8 +365,7 @@ class TimingOptimiser
                     NetInfo *pn = port.second.net;
                     if (pn == nullptr)
                         continue;
-                    if (!net_crit.count(pn->name) || net_crit.at(pn->name).criticality.empty())
-                        continue;
+
                     int ccount;
                     DelayQuad combDelay;
                     TimingPortClass tpclass = ctx->getPortTimingClass(cell, port.first, ccount);
@@ -374,12 +374,12 @@ class TimingOptimiser
                     bool is_path = ctx->getCellDelay(cell, fwd_cursor->port, port.first, combDelay);
                     if (!is_path)
                         continue;
-                    auto &crits = net_crit.at(pn->name).criticality;
-                    for (size_t i = 0; i < crits.size(); i++) {
+                    for (size_t i = 0; i < pn->users.size(); i++) {
                         if (used_ports.count(&(pn->users.at(i))))
                             continue;
-                        if (crits.at(i) >= max_crit) {
-                            max_crit = crits.at(i);
+                        float crit = tmg.get_criticality(CellPortKey(pn->users.at(i)));
+                        if (crit >= max_crit) {
+                            max_crit = crit;
                             crit_sink = std::make_pair(pn, i);
                         }
                     }
@@ -420,12 +420,7 @@ class TimingOptimiser
 
         for (auto port : path) {
             if (ctx->debug) {
-                float crit = 0;
-                NetInfo *pn = port->cell->ports.at(port->port).net;
-                if (net_crit.count(pn->name) && !net_crit.at(pn->name).criticality.empty())
-                    for (size_t i = 0; i < pn->users.size(); i++)
-                        if (pn->users.at(i).cell == port->cell && pn->users.at(i).port == port->port)
-                            crit = net_crit.at(pn->name).criticality.at(i);
+                float crit = tmg.get_criticality(CellPortKey(*port));
                 log_info("    %s.%s at %s crit %0.02f\n", port->cell->name.c_str(ctx), port->port.c_str(ctx),
                          ctx->nameOfBel(port->cell->bel), crit);
             }
@@ -613,10 +608,9 @@ class TimingOptimiser
     std::unordered_map<BelId, std::unordered_set<IdString>> bel_candidate_cells;
     // Map cell ports to net delay limit
     std::unordered_map<std::pair<IdString, IdString>, delay_t> max_net_delay;
-    // Criticality data from timing analysis
-    NetCriticalityMap net_crit;
     Context *ctx;
     TimingOptCfg cfg;
+    TimingAnalyser tmg;
 };
 
 bool timing_opt(Context *ctx, TimingOptCfg cfg) { return TimingOptimiser(ctx, cfg).optimise(); }