prefine: Do full-tile swaps, too

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

2 files changed, 100 insertions, 1 deletions

diff --git a/common/place/detail_place_core.cc b/common/place/detail_place_core.cc
index bb383639..7e629f24 100644
--- a/common/place/detail_place_core.cc
+++ b/common/place/detail_place_core.cc
@@ -348,7 +348,7 @@ void DetailPlacerThreadState::compute_changes_for_cell(CellInfo *cell, BelId old
             if (new_pos > b1) {
                 // Further out than current upper bound
                 b1 = new_pos;
-                n1 = new_pos;
+                n1 = 1;
                 if (change == NO_CHANGE) {
                     change = CELL_MOVED_OUTWARDS;
                     axis.bounds_changed_nets.push_back(idx);
diff --git a/common/place/parallel_refine.cc b/common/place/parallel_refine.cc
index a2de5b13..de71b8e0 100644
--- a/common/place/parallel_refine.cc
+++ b/common/place/parallel_refine.cc
@@ -39,6 +39,8 @@ struct GlobalState : DetailPlacerState
 {
     explicit GlobalState(Context *ctx, ParallelRefineCfg cfg) : DetailPlacerState(ctx, this->cfg), cfg(cfg){};
 
+    dict<ClusterId, std::vector<CellInfo *>> cluster2cells;
+
     ParallelRefineCfg cfg;
     double temperature = 1e-7;
     int radius = 3;
@@ -52,6 +54,8 @@ struct ThreadState : DetailPlacerThreadState
     GlobalState &g;
     int n_move = 0, n_accept = 0;
 
+    dict<std::pair<int, int>, std::vector<CellInfo *>> tile2cell;
+
     bool accept_move()
     {
         static constexpr double epsilon = 1e-20;
@@ -218,6 +222,97 @@ struct ThreadState : DetailPlacerThreadState
         }
     }
 
+    bool cluster_inside_tile(ClusterId cluster, int x, int y)
+    {
+        for (auto &c : g.cluster2cells.at(cluster)) {
+            Loc l = ctx->getBelLocation(c->bel);
+            if (l.x != x || l.y != y)
+                return false;
+        }
+        return true;
+    }
+
+    bool do_tile_swap(int x, int y, int xn, int yn)
+    {
+        if (xn < p.x0 || xn > p.x1)
+            return false;
+        if (yn < p.y0 || yn > p.y1)
+            return false;
+        if ((x == xn) && (y == yn))
+            return false;
+
+        NPNR_ASSERT(moved_cells.empty());
+
+        auto move_tile = [&](int sx, int sy, int dx, int dy) -> bool {
+            for (auto c : tile2cell[std::make_pair(sx, sy)]) {
+                if (c->belStrength > STRENGTH_STRONG ||
+                    ((c->cluster != ClusterId()) && !cluster_inside_tile(c->cluster, sx, sy)))
+                    return false; // check clusters before we start moving stuff
+            }
+            for (auto c : tile2cell[std::make_pair(sx, sy)]) {
+                Loc l = ctx->getBelLocation(c->bel);
+                l.x = dx;
+                l.y = dy;
+                BelId new_bel = ctx->getBelByLocation(l);
+                if (new_bel == BelId() || !ctx->isValidBelForCellType(c->type, new_bel))
+                    return false;
+                if (!add_to_move(c, c->bel, new_bel))
+                    return false;
+            }
+            return true;
+        };
+
+        if (!move_tile(x, y, xn, yn))
+            goto fail;
+        if (!move_tile(xn, yn, x, y))
+            goto fail;
+
+        compute_total_change();
+        // SA acceptance criteria
+        if (!accept_move()) {
+            // SA fail
+            goto fail;
+        }
+        // Check validity rules
+        if (!bind_move())
+            goto fail;
+        if (!check_validity())
+            goto fail;
+        // Accepted!
+        commit_move();
+        reset_move_state();
+        std::swap(tile2cell[std::make_pair(x, y)], tile2cell[std::make_pair(xn, yn)]);
+        return true;
+    fail:
+        revert_move();
+        reset_move_state();
+        return false;
+    }
+
+    void do_tile_swaps()
+    {
+        tile2cell.clear();
+        for (auto c : p.cells) {
+            auto loc = ctx->getBelLocation(c->bel);
+            tile2cell[std::make_pair(loc.x, loc.y)].push_back(c);
+        }
+        std::vector<std::pair<int, int>> tiles;
+        for (auto &t : tile2cell)
+            tiles.push_back(t.first);
+        rng.shuffle(tiles);
+        for (auto &t : tiles) {
+            int x = t.first, y = t.second;
+            int lx = std::max(x - g.radius, p.x0), rx = std::min(x + g.radius, p.x1);
+            int by = std::max(y - g.radius, p.y0), ty = std::min(y + g.radius, p.y1);
+            int xn = lx + ctx->rng((rx - lx) + 1);
+            int yn = by + ctx->rng((ty - by) + 1);
+            ++n_move;
+            if (do_tile_swap(x, y, xn, yn)) {
+                ++n_accept;
+            }
+        }
+    }
+
     void run_iter()
     {
         setup_initial_state();
@@ -246,6 +341,8 @@ struct ThreadState : DetailPlacerThreadState
                         ++n_accept;
                 }
             }
+            if ((m % 2) == 0)
+                do_tile_swaps();
         }
     }
 };
@@ -295,6 +392,8 @@ struct ParallelRefine
         for (auto &cell : ctx->cells) {
             IdString cell_type = cell.second->type;
             cell_types_in_use.insert(cell_type);
+            if (cell.second->cluster != ClusterId())
+                g.cluster2cells[cell.second->cluster].push_back(cell.second.get());
         }
 
         for (auto cell_type : cell_types_in_use) {