Improving post-ripup placement in the legaliser

Signed-off-by: David Shah <davey1576@gmail.com>

5 files changed, 69 insertions, 20 deletions

diff --git a/common/place_common.cc b/common/place_common.cc
index 86060cd8..591985f1 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -79,7 +79,8 @@ wirelen_t get_cell_wirelength(const Context *ctx, const CellInfo *cell)
 {
     std::set<IdString> nets;
     for (auto p : cell->ports) {
-        nets.insert(p.first);
+        if (p.second.net)
+            nets.insert(p.second.net->name);
     }
     wirelen_t wirelength = 0;
     float tns = 0;
@@ -89,4 +90,65 @@ wirelen_t get_cell_wirelength(const Context *ctx, const CellInfo *cell)
     return wirelength;
 }
 
+static wirelen_t get_cell_wirelength_at_bel(const Context *ctx, CellInfo *cell, BelId bel)
+{
+    BelId oldBel = cell->bel;
+    cell->bel = bel;
+    wirelen_t wirelen = get_cell_wirelength(ctx, cell);
+    cell->bel = oldBel;
+    return wirelen;
+}
+
+// Placing a single cell
+bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
+{
+    bool all_placed = false;
+    int iters = 25;
+    while (!all_placed) {
+        BelId best_bel = BelId();
+        wirelen_t best_wirelen = std::numeric_limits<wirelen_t>::max(),
+                  best_ripup_wirelen = std::numeric_limits<wirelen_t>::max();
+        CellInfo *ripup_target = nullptr;
+        BelId ripup_bel = BelId();
+        if (cell->bel != BelId()) {
+            ctx->unbindBel(cell->bel);
+        }
+        BelType targetType = ctx->belTypeFromId(cell->type);
+        for (auto bel : ctx->getBels()) {
+            if (ctx->getBelType(bel) == targetType && (!require_legality || ctx->isValidBelForCell(cell, bel))) {
+                if (ctx->checkBelAvail(bel)) {
+                    wirelen_t wirelen = get_cell_wirelength_at_bel(ctx, cell, bel);
+                    if (wirelen <= best_wirelen) {
+                        best_wirelen = wirelen;
+                        best_bel = bel;
+                    }
+                } else {
+                    wirelen_t wirelen = get_cell_wirelength_at_bel(ctx, cell, bel);
+                    if (wirelen <= best_ripup_wirelen) {
+                        ripup_target = ctx->cells.at(ctx->getBoundBelCell(bel)).get();
+                        if (ripup_target->belStrength < STRENGTH_STRONG) {
+                            best_ripup_wirelen = wirelen;
+                            ripup_bel = bel;
+                        }
+                    }
+                }
+            }
+        }
+        if (best_bel == BelId()) {
+            if (iters == 0 || ripup_bel == BelId()) {
+                log_error("failed to place cell '%s' of type '%s'\n", cell->name.c_str(ctx), cell->type.c_str(ctx));
+            }
+            --iters;
+            ctx->unbindBel(ripup_target->bel);
+            best_bel = ripup_bel;
+        } else {
+            all_placed = true;
+        }
+        ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK);
+
+        cell = ripup_target;
+    }
+    return true;
+}
+
 NEXTPNR_NAMESPACE_END
diff --git a/common/place_common.h b/common/place_common.h
index b81574b9..f58da450 100644
--- a/common/place_common.h
+++ b/common/place_common.h
@@ -33,7 +33,7 @@ wirelen_t get_net_wirelength(const Context *ctx, const NetInfo *net, float &tns)
 wirelen_t get_cell_wirelength(const Context *ctx, const CellInfo *cell);
 
 // Place a single cell in the lowest wirelength Bel available, optionally requiring validity check
-bool place_single_cell(const Context *ctx, CellInfo *cell, bool require_legality);
+bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/common/pybindings.cc b/common/pybindings.cc
index 02c39fa3..6441dc01 100644
--- a/common/pybindings.cc
+++ b/common/pybindings.cc
@@ -129,7 +129,7 @@ BOOST_PYTHON_MODULE(MODULE_NAME)
 
 static wchar_t *program;
 
-void init_python(const char *executable,bool first)
+void init_python(const char *executable, bool first)
 {
 #ifdef MAIN_EXECUTABLE
     program = Py_DecodeLocale(executable, NULL);
@@ -138,8 +138,7 @@ void init_python(const char *executable,bool first)
         exit(1);
     }
     try {
-        if (first)
-        {
+        if (first) {
             PyImport_AppendInittab(TOSTRING(MODULE_NAME), PYINIT_MODULE_NAME);
             emb::append_inittab();
         }
diff --git a/ice40/main.cc b/ice40/main.cc
index f1736fab..c975db24 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -391,7 +391,7 @@ int main(int argc, char *argv[])
             std::vector<std::string> files = vm["run"].as<std::vector<std::string>>();
             for (auto filename : files)
                 execute_python_file(filename.c_str());
-    
+
             deinit_python();
         }
 #endif
diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc
index 4b8a204e..00a57866 100644
--- a/ice40/place_legaliser.cc
+++ b/ice40/place_legaliser.cc
@@ -23,6 +23,7 @@
 #include "cells.h"
 #include "design_utils.h"
 #include "log.h"
+#include "place_common.h"
 #include "util.h"
 
 NEXTPNR_NAMESPACE_BEGIN
@@ -379,7 +380,7 @@ class PlacementLegaliser
         bool success = true;
         for (auto cell : sorted(rippedCells)) {
             CellInfo *ci = ctx->cells.at(cell).get();
-            bool placed = place_single_cell(ci);
+            bool placed = place_single_cell(ctx, ci, true);
             if (!placed) {
                 if (ctx->force) {
                     log_warning("failed to place cell '%s' of type '%s'\n", cell.c_str(ctx), ci->type.c_str(ctx));
@@ -392,19 +393,6 @@ class PlacementLegaliser
         return success;
     }
 
-    // Place a single cell in the first valid location
-    bool place_single_cell(CellInfo *cell)
-    {
-        BelType tgtType = ctx->belTypeFromId(cell->type);
-        for (auto bel : ctx->getBels()) {
-            if (ctx->getBelType(bel) == tgtType && ctx->checkBelAvail(bel) && ctx->isValidBelForCell(cell, bel)) {
-                ctx->bindBel(bel, cell->name, STRENGTH_WEAK);
-                return true;
-            }
-        }
-        return false;
-    }
-
     Context *ctx;
     std::unordered_set<IdString> rippedCells;
     std::unordered_set<IdString> createdCells;