HeAP: Add SA-based iterative refinement after AP

Signed-off-by: David Shah <dave@ds0.me>

3 files changed, 143 insertions, 87 deletions

diff --git a/common/placer1.cc b/common/placer1.cc
index 767dbae6..ffa3aa75 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -147,85 +147,102 @@ class SAPlacer
             net.second->udata = old_udata[net.second->udata];
     }
 
-    bool place()
+    bool place(bool refine = false)
     {
         log_break();
         ctx->lock();
 
         size_t placed_cells = 0;
-        // Initial constraints placer
-        for (auto &cell_entry : ctx->cells) {
-            CellInfo *cell = cell_entry.second.get();
-            auto loc = cell->attrs.find(ctx->id("BEL"));
-            if (loc != cell->attrs.end()) {
-                std::string loc_name = loc->second;
-                BelId bel = ctx->getBelByName(ctx->id(loc_name));
-                if (bel == BelId()) {
-                    log_error("No Bel named \'%s\' located for "
-                              "this chip (processing BEL attribute on \'%s\')\n",
-                              loc_name.c_str(), cell->name.c_str(ctx));
-                }
+        std::vector<CellInfo *> autoplaced;
+        std::vector<CellInfo *> chain_basis;
+        if (!refine) {
+            // Initial constraints placer
+            for (auto &cell_entry : ctx->cells) {
+                CellInfo *cell = cell_entry.second.get();
+                auto loc = cell->attrs.find(ctx->id("BEL"));
+                if (loc != cell->attrs.end()) {
+                    std::string loc_name = loc->second;
+                    BelId bel = ctx->getBelByName(ctx->id(loc_name));
+                    if (bel == BelId()) {
+                        log_error("No Bel named \'%s\' located for "
+                                  "this chip (processing BEL attribute on \'%s\')\n",
+                                  loc_name.c_str(), cell->name.c_str(ctx));
+                    }
 
-                IdString bel_type = ctx->getBelType(bel);
-                if (bel_type != cell->type) {
-                    log_error("Bel \'%s\' of type \'%s\' does not match cell "
-                              "\'%s\' of type \'%s\'\n",
-                              loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
-                }
-                if (!ctx->isValidBelForCell(cell, bel)) {
-                    log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
-                              "\'%s\' of type \'%s\'\n",
-                              loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
-                }
+                    IdString bel_type = ctx->getBelType(bel);
+                    if (bel_type != cell->type) {
+                        log_error("Bel \'%s\' of type \'%s\' does not match cell "
+                                  "\'%s\' of type \'%s\'\n",
+                                  loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
+                    }
+                    if (!ctx->isValidBelForCell(cell, bel)) {
+                        log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
+                                  "\'%s\' of type \'%s\'\n",
+                                  loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
+                    }
 
-                auto bound_cell = ctx->getBoundBelCell(bel);
-                if (bound_cell) {
-                    log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
-                              cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
-                }
+                    auto bound_cell = ctx->getBoundBelCell(bel);
+                    if (bound_cell) {
+                        log_error("Cell \'%s\' cannot be bound to bel \'%s\' since it is already bound to cell \'%s\'\n",
+                                  cell->name.c_str(ctx), loc_name.c_str(), bound_cell->name.c_str(ctx));
+                    }
 
-                ctx->bindBel(bel, cell, STRENGTH_USER);
-                locked_bels.insert(bel);
-                placed_cells++;
+                    ctx->bindBel(bel, cell, STRENGTH_USER);
+                    locked_bels.insert(bel);
+                    placed_cells++;
+                }
             }
-        }
-        int constr_placed_cells = placed_cells;
-        log_info("Placed %d cells based on constraints.\n", int(placed_cells));
-        ctx->yield();
+            int constr_placed_cells = placed_cells;
+            log_info("Placed %d cells based on constraints.\n", int(placed_cells));
+            ctx->yield();
+
+            // Sort to-place cells for deterministic initial placement
 
-        // Sort to-place cells for deterministic initial placement
-        std::vector<CellInfo *> autoplaced;
-        std::vector<CellInfo *> chain_basis;
 
-        for (auto &cell : ctx->cells) {
-            CellInfo *ci = cell.second.get();
-            if (ci->bel == BelId()) {
-                autoplaced.push_back(cell.second.get());
+            for (auto &cell : ctx->cells) {
+                CellInfo *ci = cell.second.get();
+                if (ci->bel == BelId()) {
+                    autoplaced.push_back(cell.second.get());
+                }
             }
-        }
-        std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; });
-        ctx->shuffle(autoplaced);
-        auto iplace_start = std::chrono::high_resolution_clock::now();
-        // Place cells randomly initially
-        log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size()));
-
-        for (auto cell : autoplaced) {
-            place_initial(cell);
-            placed_cells++;
-            if ((placed_cells - constr_placed_cells) % 500 == 0)
+            std::sort(autoplaced.begin(), autoplaced.end(), [](CellInfo *a, CellInfo *b) { return a->name < b->name; });
+            ctx->shuffle(autoplaced);
+            auto iplace_start = std::chrono::high_resolution_clock::now();
+            // Place cells randomly initially
+            log_info("Creating initial placement for remaining %d cells.\n", int(autoplaced.size()));
+
+            for (auto cell : autoplaced) {
+                place_initial(cell);
+                placed_cells++;
+                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()));
+            }
+            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()));
+            if (cfg.budgetBased && ctx->slack_redist_iter > 0)
+                assign_budget(ctx);
+            ctx->yield();
+            auto iplace_end = std::chrono::high_resolution_clock::now();
+            log_info("Initial placement time %.02fs\n", std::chrono::duration<float>(iplace_end - iplace_start).count());
+            log_info("Running simulated annealing placer.\n");
+        } else {
+            for (auto &cell : ctx->cells) {
+                CellInfo *ci = cell.second.get();
+                if (ci->belStrength > STRENGTH_STRONG)
+                    continue;
+                else if (ci->constr_parent != nullptr)
+                    continue;
+                else if (!ci->constr_children.empty() || ci->constr_z != ci->UNCONSTR)
+                    chain_basis.push_back(ci);
+                else
+                    autoplaced.push_back(ci);
+            }
+            require_legal = false;
+            diameter = 3;
         }
-        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()));
-        if (cfg.budgetBased && ctx->slack_redist_iter > 0)
-            assign_budget(ctx);
-        ctx->yield();
-        auto iplace_end = std::chrono::high_resolution_clock::now();
-        log_info("Initial placement time %.02fs\n", std::chrono::duration<float>(iplace_end - iplace_start).count());
         auto saplace_start = std::chrono::high_resolution_clock::now();
-        log_info("Running simulated annealing placer.\n");
 
         // Invoke timing analysis to obtain criticalities
         if (!cfg.budgetBased)
@@ -242,7 +259,7 @@ class SAPlacer
         wirelen_t min_wirelen = curr_wirelen_cost;
 
         int n_no_progress = 0;
-        temp = cfg.startTemp;
+        temp = refine ? 1e-8 : cfg.startTemp;
 
         // Main simulated annealing loop
         for (int iter = 1;; iter++) {
@@ -284,7 +301,7 @@ class SAPlacer
             else
                 n_no_progress++;
 
-            if (temp <= 1e-7 && n_no_progress >= 5) {
+            if (temp <= 1e-7 && n_no_progress >= (refine ? 1 : 5)) {
                 log_info("  at iteration #%d: temp = %f, timing cost = "
                          "%.0f, wirelen = %.0f \n",
                          iter, temp, double(curr_timing_cost), double(curr_wirelen_cost));
@@ -934,4 +951,24 @@ bool placer1(Context *ctx, Placer1Cfg cfg)
     }
 }
 
+bool placer1_refine(Context *ctx, Placer1Cfg cfg) {
+    try {
+        SAPlacer placer(ctx, cfg);
+        placer.place(true);
+        log_info("Checksum: 0x%08x\n", ctx->checksum());
+#ifndef NDEBUG
+        ctx->lock();
+        ctx->check();
+        ctx->unlock();
+#endif
+        return true;
+    } catch (log_execution_error_exception) {
+#ifndef NDEBUG
+        ctx->check();
+#endif
+        return false;
+    }
+}
+
+
 NEXTPNR_NAMESPACE_END
diff --git a/common/placer1.h b/common/placer1.h
index a0eabbb0..4c7c7339 100644
--- a/common/placer1.h
+++ b/common/placer1.h
@@ -35,6 +35,7 @@ struct Placer1Cfg : public Settings
 };
 
 extern bool placer1(Context *ctx, Placer1Cfg cfg);
+extern bool placer1_refine(Context *ctx, Placer1Cfg cfg);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index 3e98b937..7e8323ca 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -34,6 +34,7 @@
 #include "nextpnr.h"
 #include "place_common.h"
 #include "placer_math.h"
+#include "placer1.h"
 #include "util.h"
 NEXTPNR_NAMESPACE_BEGIN
 
@@ -191,6 +192,9 @@ class HeAPPlacer
             ++iter;
         }
         ctx->unlock();
+
+        placer1_refine(ctx, Placer1Cfg(ctx));
+
         return true;
     }
 
@@ -355,14 +359,17 @@ class HeAPPlacer
     // FIXME: Are there better approaches to the initial placement (e.g. greedy?)
     void seed_placement()
     {
-        std::unordered_map<IdString, std::vector<BelId>> available_bels;
+        std::unordered_map<IdString, std::deque<BelId>> available_bels;
         for (auto bel : ctx->getBels()) {
             if (!ctx->checkBelAvail(bel))
                 continue;
             available_bels[ctx->getBelType(bel)].push_back(bel);
         }
-        for (auto &ab : available_bels)
-            ctx->shuffle(ab.second);
+        for (auto &t : available_bels) {
+            std::random_shuffle(t.second.begin(), t.second.end(), [&](size_t n){
+                return ctx->rng(int(n));
+            });
+        }
         for (auto cell : sorted(ctx->cells)) {
             CellInfo *ci = cell.second;
             if (ci->bel != BelId()) {
@@ -372,23 +379,34 @@ class HeAPPlacer
                 cell_locs[cell.first].locked = true;
                 cell_locs[cell.first].global = ctx->getBelGlobalBuf(ci->bel);
             } else if (ci->constr_parent == nullptr) {
-                if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty())
-                    log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx),
-                              ci->type.c_str(ctx));
-                BelId bel = available_bels.at(ci->type).back();
-                available_bels.at(ci->type).pop_back();
-                Loc loc = ctx->getBelLocation(bel);
-                cell_locs[cell.first].x = loc.x;
-                cell_locs[cell.first].y = loc.y;
-                cell_locs[cell.first].locked = false;
-                cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel);
-                // FIXME
-                if (has_connectivity(cell.second) && cell.second->type != ctx->id("SB_IO")) {
-                    place_cells.push_back(ci);
-                } else {
-                    ctx->bindBel(bel, ci, STRENGTH_STRONG);
-                    cell_locs[cell.first].locked = true;
+                bool placed = false;
+                while (!placed) {
+                    if (!available_bels.count(ci->type) || available_bels.at(ci->type).empty())
+                        log_error("Unable to place cell '%s', no Bels remaining of type '%s'\n", ci->name.c_str(ctx),
+                                  ci->type.c_str(ctx));
+                    BelId bel = available_bels.at(ci->type).back();
+                    available_bels.at(ci->type).pop_back();
+                    Loc loc = ctx->getBelLocation(bel);
+                    cell_locs[cell.first].x = loc.x;
+                    cell_locs[cell.first].y = loc.y;
+                    cell_locs[cell.first].locked = false;
+                    cell_locs[cell.first].global = ctx->getBelGlobalBuf(bel);
+                    // FIXME
+                    if (has_connectivity(cell.second) && cell.second->type != ctx->id("SB_IO")) {
+                        place_cells.push_back(ci);
+                        placed = true;
+                    } else {
+                        if (ctx->isValidBelForCell(ci, bel)) {
+                            ctx->bindBel(bel, ci, STRENGTH_STRONG);
+                            cell_locs[cell.first].locked = true;
+                            placed = true;
+                        } else {
+                            available_bels.at(ci->type).push_front(bel);
+                        }
+
+                    }
                 }
+
             }
         }
     }
@@ -728,8 +746,8 @@ class HeAPPlacer
             for (auto &r : regions) {
                 if (merged_regions.count(r.id))
                     continue;
-                /*log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells,
-                         r.bels);*/
+                log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", beltype.c_str(ctx), r.x0, r.y0, r.x1, r.y1, r.cells,
+                         r.bels);
                 workqueue.emplace(r.id, false);
                 //cut_region(r, false);
             }
@@ -865,7 +883,7 @@ class HeAPPlacer
 
             auto process_location = [&](int x, int y) {
                 // Merge with any overlapping regions
-                if (groups.at(x).at(y) != r.id) {
+                if (groups.at(x).at(y) == -1) {
                     r.bels += bels_at(x, y);
                     r.cells += occ_at(x, y);
                 }