Merge remote-tracking branch 'origin/master' into common_main

# Conflicts:
#	ecp5/main.cc
#	ice40/main.cc

8 files changed, 121 insertions, 86 deletions

diff --git a/common/command.cc b/common/command.cc
index 9eace237..5b30df58 100644
--- a/common/command.cc
+++ b/common/command.cc
@@ -192,6 +192,7 @@ int CommandHandler::executeMain(std::unique_ptr<Context> ctx)
     if (vm.count("json") || vm.count("load")) {
         if (!ctx->pack() && !ctx->force)
             log_error("Packing design failed.\n");
+        assign_budget(ctx.get());
         ctx->check();
         print_utilisation(ctx.get());
         if (!vm.count("pack-only")) {
diff --git a/common/nextpnr.cc b/common/nextpnr.cc
index dbea26d8..3bdca166 100644
--- a/common/nextpnr.cc
+++ b/common/nextpnr.cc
@@ -232,25 +232,26 @@ void Context::check() const
         auto ni = n.second.get();
         NPNR_ASSERT(n.first == ni->name);
         for (auto &w : ni->wires) {
-            NPNR_ASSERT(n.first == getBoundWireNet(w.first));
+            NPNR_ASSERT(ni == getBoundWireNet(w.first));
             if (w.second.pip != PipId()) {
                 NPNR_ASSERT(w.first == getPipDstWire(w.second.pip));
-                NPNR_ASSERT(n.first == getBoundPipNet(w.second.pip));
+                NPNR_ASSERT(ni == getBoundPipNet(w.second.pip));
             }
         }
     }
 
     for (auto w : getWires()) {
-        IdString net = getBoundWireNet(w);
-        if (net != IdString()) {
-            NPNR_ASSERT(nets.at(net)->wires.count(w));
+        auto ni = getBoundWireNet(w);
+        if (ni != nullptr) {
+            NPNR_ASSERT(ni->wires.count(w));
         }
     }
 
     for (auto &c : cells) {
-        NPNR_ASSERT(c.first == c.second->name);
-        if (c.second->bel != BelId())
-            NPNR_ASSERT(getBoundBelCell(c.second->bel) == c.first);
+        auto ci = c.second.get();
+        NPNR_ASSERT(c.first == ci->name);
+        if (ci->bel != BelId())
+            NPNR_ASSERT(getBoundBelCell(c.second->bel) == ci);
         for (auto &port : c.second->ports) {
             NetInfo *net = port.second.net;
             if (net != nullptr) {
diff --git a/common/nextpnr.h b/common/nextpnr.h
index bb55d4ff..3d9a66ca 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -437,6 +437,13 @@ struct BaseCtx
 
     const Context *getCtx() const { return reinterpret_cast<const Context *>(this); }
 
+    template<typename T> const char *nameOf(const T *obj)
+    {
+        if (obj == nullptr)
+            return "";
+        return obj->name.c_str(getCtx());
+    }
+
     // --------------------------------------------------------------
 
     bool allUiReload = true;
diff --git a/common/place_common.cc b/common/place_common.cc
index 1baab8a1..fe9cf03d 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -131,7 +131,7 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
                     if (iters >= 4)
                         wirelen += ctx->rng(25);
                     if (wirelen <= best_ripup_wirelen) {
-                        CellInfo *curr_cell = ctx->cells.at(ctx->getBoundBelCell(bel)).get();
+                        CellInfo *curr_cell = ctx->getBoundBelCell(bel);
                         if (curr_cell->belStrength < STRENGTH_STRONG) {
                             best_ripup_wirelen = wirelen;
                             ripup_bel = bel;
@@ -158,7 +158,7 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
         if (ctx->verbose)
             log_info("   placed single cell '%s' at '%s'\n", cell->name.c_str(ctx),
                      ctx->getBelName(best_bel).c_str(ctx));
-        ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK);
+        ctx->bindBel(best_bel, cell, STRENGTH_WEAK);
 
         cell = ripup_target;
     }
@@ -232,8 +232,8 @@ class ConstraintLegaliseWorker
             return false;
         }
         if (!ctx->checkBelAvail(locBel)) {
-            IdString confCell = ctx->getConflictingBelCell(locBel);
-            if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) {
+            CellInfo *confCell = ctx->getConflictingBelCell(locBel);
+            if (confCell->belStrength >= STRENGTH_STRONG) {
                 return false;
             }
         }
@@ -362,20 +362,31 @@ class ConstraintLegaliseWorker
                                      cp.second.y, cp.second.z);
                         BelId target = ctx->getBelByLocation(cp.second);
                         if (!ctx->checkBelAvail(target)) {
-                            IdString conflicting = ctx->getConflictingBelCell(target);
-                            if (conflicting != IdString()) {
-                                CellInfo *confl_cell = ctx->cells.at(conflicting).get();
+                            CellInfo *confl_cell = ctx->getConflictingBelCell(target);
+                            if (confl_cell != nullptr) {
                                 if (ctx->verbose)
-                                    log_info("       '%s' already placed at '%s'\n", conflicting.c_str(ctx),
+                                    log_info("       '%s' already placed at '%s'\n", ctx->nameOf(confl_cell),
                                              ctx->getBelName(confl_cell->bel).c_str(ctx));
                                 NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG);
                                 ctx->unbindBel(target);
-                                rippedCells.insert(conflicting);
+                                rippedCells.insert(confl_cell->name);
                             }
                         }
-                        ctx->bindBel(target, cp.first, STRENGTH_LOCKED);
+                        ctx->bindBel(target, ctx->cells.at(cp.first).get(), STRENGTH_LOCKED);
                         rippedCells.erase(cp.first);
                     }
+                    for (auto cp : solution) {
+                        for (auto bel : ctx->getBelsByTile(cp.second.x, cp.second.y)) {
+                            CellInfo *belCell = ctx->getBoundBelCell(bel);
+                            if (belCell != nullptr && !solution.count(belCell->name)) {
+                                if (!ctx->isValidBelForCell(belCell, bel)) {
+                                    NPNR_ASSERT(belCell->belStrength < STRENGTH_STRONG);
+                                    ctx->unbindBel(bel);
+                                    rippedCells.insert(belCell->name);
+                                }
+                            }
+                        }
+                    }
                     NPNR_ASSERT(constraints_satisfied(cell));
                     return true;
                 }
diff --git a/common/placer1.cc b/common/placer1.cc
index c4543e2a..1d00e77a 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -105,7 +105,7 @@ class SAPlacer
                               cell->type.c_str(ctx));
                 }
 
-                ctx->bindBel(bel, cell->name, STRENGTH_USER);
+                ctx->bindBel(bel, cell, STRENGTH_USER);
                 locked_bels.insert(bel);
                 placed_cells++;
             }
@@ -138,7 +138,8 @@ class SAPlacer
         if ((placed_cells - constr_placed_cells) % 500 != 0)
             log_info("  initial placement placed %d/%d cells\n", int(placed_cells - constr_placed_cells),
                      int(autoplaced.size()));
-        assign_budget(ctx);
+        if (ctx->slack_redist_iter > 0)
+            assign_budget(ctx);
         ctx->yield();
 
         log_info("Running simulated annealing placer.\n");
@@ -256,11 +257,11 @@ class SAPlacer
         // Final post-pacement validitiy check
         ctx->yield();
         for (auto bel : ctx->getBels()) {
-            IdString cell = ctx->getBoundBelCell(bel);
+            CellInfo *cell = ctx->getBoundBelCell(bel);
             if (!ctx->isBelLocationValid(bel)) {
                 std::string cell_text = "no cell";
-                if (cell != IdString())
-                    cell_text = std::string("cell '") + cell.str(ctx) + "'";
+                if (cell != nullptr)
+                    cell_text = std::string("cell '") + ctx->nameOf(cell) + "'";
                 if (ctx->force) {
                     log_warning("post-placement validity check failed for Bel '%s' "
                                 "(%s)\n",
@@ -309,7 +310,7 @@ class SAPlacer
                         uint64_t score = ctx->rng64();
                         if (score <= best_ripup_score) {
                             best_ripup_score = score;
-                            ripup_target = ctx->cells.at(ctx->getBoundBelCell(bel)).get();
+                            ripup_target = ctx->getBoundBelCell(bel);
                             ripup_bel = bel;
                         }
                     }
@@ -324,7 +325,7 @@ class SAPlacer
             } else {
                 all_placed = true;
             }
-            ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK);
+            ctx->bindBel(best_bel, cell, STRENGTH_WEAK);
 
             // Back annotate location
             cell->attrs[ctx->id("BEL")] = ctx->getBelName(cell->bel).str(ctx);
@@ -340,20 +341,17 @@ class SAPlacer
         new_lengths.clear();
         update.clear();
         BelId oldBel = cell->bel;
-        IdString other = ctx->getBoundBelCell(newBel);
-        CellInfo *other_cell = nullptr;
-        if (other != IdString()) {
-            other_cell = ctx->cells[other].get();
-            if (other_cell->belStrength > STRENGTH_WEAK)
-                return false;
+        CellInfo *other_cell = ctx->getBoundBelCell(newBel);
+        if (other_cell != nullptr && other_cell->belStrength > STRENGTH_WEAK) {
+            return false;
         }
         int old_dist = get_constraints_distance(ctx, cell);
         int new_dist;
-        if (other != IdString())
+        if (other_cell != nullptr)
             old_dist += get_constraints_distance(ctx, other_cell);
         wirelen_t new_metric = 0, delta;
         ctx->unbindBel(oldBel);
-        if (other != IdString()) {
+        if (other_cell != nullptr) {
             ctx->unbindBel(newBel);
         }
 
@@ -361,20 +359,20 @@ class SAPlacer
             if (port.second.net != nullptr)
                 update.insert(port.second.net);
 
-        if (other != IdString()) {
+        if (other_cell != nullptr) {
             for (const auto &port : other_cell->ports)
                 if (port.second.net != nullptr)
                     update.insert(port.second.net);
         }
 
-        ctx->bindBel(newBel, cell->name, STRENGTH_WEAK);
+        ctx->bindBel(newBel, cell, STRENGTH_WEAK);
 
-        if (other != IdString()) {
-            ctx->bindBel(oldBel, other_cell->name, STRENGTH_WEAK);
+        if (other_cell != nullptr) {
+            ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK);
         }
-        if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) {
+        if (!ctx->isBelLocationValid(newBel) || ((other_cell != nullptr && !ctx->isBelLocationValid(oldBel)))) {
             ctx->unbindBel(newBel);
-            if (other != IdString())
+            if (other_cell != nullptr)
                 ctx->unbindBel(oldBel);
             goto swap_fail;
         }
@@ -391,7 +389,7 @@ class SAPlacer
         }
 
         new_dist = get_constraints_distance(ctx, cell);
-        if (other != IdString())
+        if (other_cell != nullptr)
             new_dist += get_constraints_distance(ctx, other_cell);
         delta = new_metric - curr_metric;
         delta += (cfg.constraintWeight / temp) * (new_dist - old_dist);
@@ -400,7 +398,7 @@ class SAPlacer
         if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
             n_accept++;
         } else {
-            if (other != IdString())
+            if (other_cell != nullptr)
                 ctx->unbindBel(oldBel);
             ctx->unbindBel(newBel);
             goto swap_fail;
@@ -411,9 +409,9 @@ class SAPlacer
 
         return true;
     swap_fail:
-        ctx->bindBel(oldBel, cell->name, STRENGTH_WEAK);
-        if (other != IdString()) {
-            ctx->bindBel(newBel, other, STRENGTH_WEAK);
+        ctx->bindBel(oldBel, cell, STRENGTH_WEAK);
+        if (other_cell != nullptr) {
+            ctx->bindBel(newBel, other_cell, STRENGTH_WEAK);
         }
         return false;
     }
diff --git a/common/pywrappers.h b/common/pywrappers.h
index 725caca8..4e463afd 100644
--- a/common/pywrappers.h
+++ b/common/pywrappers.h
@@ -140,6 +140,14 @@ template <typename T> struct deref_and_wrap
     using ret_type = ContextualWrapper<T &>;
 };
 
+template <typename T> struct addr_and_unwrap
+{
+    inline T *operator()(Context *ctx, ContextualWrapper<T &> x) { return &(x.base); }
+
+    using arg_type = ContextualWrapper<T &>;
+    using ret_type = T *;
+};
+
 // Function wrapper
 // Zero parameters, one return
 template <typename Class, typename FuncT, FuncT fn, typename rv_conv> struct fn_wrapper_0a
diff --git a/common/router1.cc b/common/router1.cc
index 77e84696..0733a61e 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -159,15 +159,15 @@ struct Router
                 if (!ctx->checkWireAvail(next_wire)) {
                     if (!ripup)
                         continue;
-                    IdString ripupWireNet = ctx->getConflictingWireNet(next_wire);
-                    if (ripupWireNet == net_name || ripupWireNet == IdString())
+                    NetInfo *ripupWireNet = ctx->getConflictingWireNet(next_wire);
+                    if (ripupWireNet == nullptr || ripupWireNet->name == net_name)
                         continue;
 
                     auto it1 = scores.wireScores.find(next_wire);
                     if (it1 != scores.wireScores.end())
                         next_delay += (it1->second * ripup_penalty) / 8;
 
-                    auto it2 = scores.netWireScores.find(std::make_pair(ripupWireNet, next_wire));
+                    auto it2 = scores.netWireScores.find(std::make_pair(ripupWireNet->name, next_wire));
                     if (it2 != scores.netWireScores.end())
                         next_delay += it2->second * ripup_penalty;
 
@@ -177,15 +177,15 @@ struct Router
                 if (!ctx->checkPipAvail(pip)) {
                     if (!ripup)
                         continue;
-                    IdString ripupPipNet = ctx->getConflictingPipNet(pip);
-                    if (ripupPipNet == net_name || ripupPipNet == IdString())
+                    NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip);
+                    if (ripupPipNet == nullptr || ripupPipNet->name == net_name)
                         continue;
 
                     auto it1 = scores.pipScores.find(pip);
                     if (it1 != scores.pipScores.end())
                         next_delay += (it1->second * ripup_penalty) / 8;
 
-                    auto it2 = scores.netPipScores.find(std::make_pair(ripupPipNet, pip));
+                    auto it2 = scores.netPipScores.find(std::make_pair(ripupPipNet->name, pip));
                     if (it2 != scores.netPipScores.end())
                         next_delay += it2->second * ripup_penalty;
 
@@ -294,12 +294,12 @@ struct Router
         if (reroute) {
             // complete ripup
             ripup_net(ctx, net_name);
-            ctx->bindWire(src_wire, net_name, STRENGTH_WEAK);
+            ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
             src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
         } else {
             // re-use existing routes as much as possible
             if (net_info->wires.count(src_wire) == 0)
-                ctx->bindWire(src_wire, net_name, STRENGTH_WEAK);
+                ctx->bindWire(src_wire, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
             src_wires[src_wire] = ctx->getWireDelay(src_wire).maxDelay();
 
             for (int user_idx = 0; user_idx < int(net_info->users.size()); user_idx++) {
@@ -399,42 +399,42 @@ struct Router
                 if (src_wires.count(cursor))
                     break;
 
-                IdString conflicting_wire_net = ctx->getConflictingWireNet(cursor);
+                NetInfo *conflicting_wire_net = ctx->getConflictingWireNet(cursor);
 
-                if (conflicting_wire_net != IdString()) {
+                if (conflicting_wire_net != nullptr) {
                     NPNR_ASSERT(ripup);
-                    NPNR_ASSERT(conflicting_wire_net != net_name);
+                    NPNR_ASSERT(conflicting_wire_net->name != net_name);
 
                     ctx->unbindWire(cursor);
                     if (!ctx->checkWireAvail(cursor))
-                        ripup_net(ctx, conflicting_wire_net);
+                        ripup_net(ctx, conflicting_wire_net->name);
 
-                    rippedNets.insert(conflicting_wire_net);
+                    rippedNets.insert(conflicting_wire_net->name);
                     scores.wireScores[cursor]++;
                     scores.netWireScores[std::make_pair(net_name, cursor)]++;
-                    scores.netWireScores[std::make_pair(conflicting_wire_net, cursor)]++;
+                    scores.netWireScores[std::make_pair(conflicting_wire_net->name, cursor)]++;
                 }
 
                 PipId pip = visited[cursor].pip;
-                IdString conflicting_pip_net = ctx->getConflictingPipNet(pip);
+                NetInfo *conflicting_pip_net = ctx->getConflictingPipNet(pip);
 
-                if (conflicting_pip_net != IdString()) {
+                if (conflicting_pip_net != nullptr) {
                     NPNR_ASSERT(ripup);
-                    NPNR_ASSERT(conflicting_pip_net != net_name);
+                    NPNR_ASSERT(conflicting_pip_net->name != net_name);
 
                     if (ctx->getBoundPipNet(pip) == conflicting_pip_net)
                         ctx->unbindPip(pip);
 
                     if (!ctx->checkPipAvail(pip))
-                        ripup_net(ctx, conflicting_pip_net);
+                        ripup_net(ctx, conflicting_pip_net->name);
 
-                    rippedNets.insert(conflicting_pip_net);
+                    rippedNets.insert(conflicting_pip_net->name);
                     scores.pipScores[visited[cursor].pip]++;
                     scores.netPipScores[std::make_pair(net_name, visited[cursor].pip)]++;
-                    scores.netPipScores[std::make_pair(conflicting_pip_net, visited[cursor].pip)]++;
+                    scores.netPipScores[std::make_pair(conflicting_pip_net->name, visited[cursor].pip)]++;
                 }
 
-                ctx->bindPip(visited[cursor].pip, net_name, STRENGTH_WEAK);
+                ctx->bindPip(visited[cursor].pip, ctx->nets.at(net_name).get(), STRENGTH_WEAK);
                 src_wires[cursor] = visited[cursor].delay;
                 cursor = ctx->getPipSrcWire(visited[cursor].pip);
             }
diff --git a/common/timing.cc b/common/timing.cc
index f6c5f001..c00e1ba5 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -2,6 +2,7 @@
  *  nextpnr -- Next Generation Place and Route
  *
  *  Copyright (C) 2018  David Shah <david@symbioticeda.com>
+ *  Copyright (C) 2018  Eddie Hung <eddieh@ece.ubc.ca>
  *
  *  Permission to use, copy, modify, and/or distribute this software for any
  *  purpose with or without fee is hereby granted, provided that the above
@@ -32,36 +33,42 @@ typedef std::map<int, unsigned> DelayFrequency;
 struct Timing
 {
     Context *ctx;
+    bool net_delays;
     bool update;
     delay_t min_slack;
     PortRefVector current_path;
     PortRefVector *crit_path;
     DelayFrequency *slack_histogram;
 
-    Timing(Context *ctx, bool update, PortRefVector *crit_path = nullptr, DelayFrequency *slack_histogram = nullptr)
-            : ctx(ctx), update(update), min_slack(1.0e12 / ctx->target_freq), crit_path(crit_path),
-              slack_histogram(slack_histogram)
+    Timing(Context *ctx, bool net_delays, bool update, PortRefVector *crit_path = nullptr,
+           DelayFrequency *slack_histogram = nullptr)
+            : ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->target_freq),
+              crit_path(crit_path), slack_histogram(slack_histogram)
     {
     }
 
     delay_t follow_net(NetInfo *net, int path_length, delay_t slack)
     {
-        delay_t net_budget = slack / (path_length + 1);
+        const delay_t default_budget = slack / (path_length + 1);
+        delay_t net_budget = default_budget;
         for (auto &usr : net->users) {
+            auto delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
             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, usr, net_budget);
-            if (budget < net_budget) {
-                net_budget = budget;
-                pl = std::max(1, path_length);
+            // If budget override exists, use that value and do not increment path_length
+            auto budget = default_budget;
+            if (ctx->getBudgetOverride(net, usr, budget)) {
+                if (update)
+                    usr.budget = std::min(usr.budget, budget);
+                budget = follow_user_port(usr, path_length, slack - budget);
+                net_budget = std::min(net_budget, budget);
+            }
+            else {
+                budget = follow_user_port(usr, path_length + 1, slack - delay);
+                net_budget = std::min(net_budget, budget);
+                if (update)
+                    usr.budget = std::min(usr.budget, delay + budget);
             }
-            auto delay = ctx->getNetinfoRouteDelay(net, usr);
-            net_budget = std::min(net_budget, follow_user_port(usr, pl, slack - delay));
-            if (update)
-                usr.budget = std::min(usr.budget, delay + net_budget);
             if (crit_path)
                 current_path.pop_back();
         }
@@ -149,10 +156,10 @@ void assign_budget(Context *ctx, bool quiet)
 {
     if (!quiet) {
         log_break();
-        log_info("Annotating ports with timing budgets for target frequency %.2f MHz\n", ctx->target_freq/1e6);
+        log_info("Annotating ports with timing budgets for target frequency %.2f MHz\n", ctx->target_freq / 1e6);
     }
 
-    Timing timing(ctx, true /* update */);
+    Timing timing(ctx, ctx->slack_redist_iter > 0 /* net_delays */, true /* update */);
     timing.assign_budget();
 
     if (!quiet || ctx->verbose) {
@@ -194,7 +201,7 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
     PortRefVector crit_path;
     DelayFrequency slack_histogram;
 
-    Timing timing(ctx, false /* update */, print_path ? &crit_path : nullptr,
+    Timing timing(ctx, true /* net_delays */, false /* update */, print_path ? &crit_path : nullptr,
                   print_histogram ? &slack_histogram : nullptr);
     auto min_slack = timing.walk_paths();
 
@@ -238,7 +245,7 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
     delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
     log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack));
 
-    if (print_histogram) {
+    if (print_histogram && slack_histogram.size() > 0) {
         constexpr unsigned num_bins = 20;
         unsigned bar_width = 60;
         auto min_slack = slack_histogram.begin()->first;
@@ -256,9 +263,11 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
         log_break();
         log_info("Slack histogram:\n");
         log_info(" legend: * represents %d endpoint(s)\n", max_freq / bar_width);
+        log_info("         + represents [1,%d) endpoint(s)\n", max_freq / bar_width);
         for (unsigned i = 0; i < bins.size(); ++i)
-            log_info("%6d < ps < %6d |%s\n", min_slack + bin_size * i, min_slack + bin_size * (i + 1),
-                     std::string(bins[i] * bar_width / max_freq, '*').c_str());
+            log_info("[%6d, %6d) |%s%c\n", min_slack + bin_size * i, min_slack + bin_size * (i + 1),
+                     std::string(bins[i] * bar_width / max_freq, '*').c_str(),
+                     (bins[i] * bar_width) % max_freq > 0 ? '+' : ' ');
     }
 }