experiment: Simple heuristic-based placer

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

3 files changed, 129 insertions, 3 deletions

diff --git a/common/design_utils.h b/common/design_utils.h
index daf6e050..8d231d4c 100644
--- a/common/design_utils.h
+++ b/common/design_utils.h
@@ -72,7 +72,7 @@ CellInfo *net_only_drives(NetInfo *net, F1 cell_pred, IdString port,
 // If a net is driven by a given port of a cell matching a predicate, return
 // that cell, otherwise nullptr
 template <typename F1>
-CellInfo *net_driven_by(NetInfo *net, F1 cell_pred, IdString port)
+CellInfo *net_driven_by(const NetInfo *net, F1 cell_pred, IdString port)
 {
     if (net == nullptr)
         return nullptr;
diff --git a/common/place.cc b/common/place.cc
index 92c09e78..2b69aa28 100644
--- a/common/place.cc
+++ b/common/place.cc
@@ -17,20 +17,21 @@
  *
  */
 
+#include "place.h"
 #include <iostream>
+#include <limits>
 #include <list>
 #include <map>
 #include <ostream>
+#include <queue>
 #include <set>
 #include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <vector>
-
 #include "arch_place.h"
 #include "log.h"
-#include "place.h"
 
 NEXTPNR_NAMESPACE_BEGIN
 
@@ -122,4 +123,127 @@ void place_design(Design *design)
     }
 }
 
+static void place_cell(Design *design, CellInfo *cell, BelId closeTo,
+                       size_t &placed_cells,
+                       std::queue<CellInfo *> &visit_cells)
+{
+    assert(cell->bel == BelId());
+    float best_distance = std::numeric_limits<float>::infinity();
+    BelId best_bel = BelId();
+    Chip &chip = design->chip;
+    BelType targetType = belTypeFromId(cell->type);
+    PosInfo origin;
+    if (closeTo != BelId()) {
+        origin = chip.getBelPosition(closeTo);
+        for (auto bel : chip.getBelsAtSameTile(closeTo)) {
+            if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) &&
+                isValidBelForCell(design, cell, bel)) {
+                // prefer same tile
+                best_bel = bel;
+                goto placed;
+            }
+        }
+    }
+    for (auto bel : chip.getBels()) {
+        if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) &&
+            isValidBelForCell(design, cell, bel)) {
+            if (closeTo == BelId()) {
+                best_distance = 0;
+                best_bel = bel;
+                goto placed;
+            } else {
+                float distance =
+                        chip.estimateDelay(origin, chip.getBelPosition(bel));
+                if (distance < best_distance) {
+                    best_distance = distance;
+                    best_bel = bel;
+                }
+            }
+        }
+    }
+placed:
+    if (best_bel == BelId()) {
+        log_error("failed to place cell '%s' of type '%s'\n",
+                  cell->name.c_str(), cell->type.c_str());
+    }
+    cell->bel = best_bel;
+    chip.bindBel(cell->bel, cell->name);
+
+    // Back annotate location
+    cell->attrs["BEL"] = chip.getBelName(cell->bel).str();
+    placed_cells++;
+    visit_cells.push(cell);
+}
+
+static void place_cell_neighbours(Design *design, CellInfo *cell,
+                                  size_t &placed_cells,
+                                  std::queue<CellInfo *> &visit_cells)
+{
+    if (cell->bel == BelId())
+        return;
+    for (auto port : cell->ports) {
+        NetInfo *net = port.second.net;
+        if (net != nullptr) {
+            if (net->users.size() > 3) // don't follow high fanout nets
+                continue;
+            for (auto user : net->users) {
+                if (user.cell != nullptr && user.cell->bel == BelId())
+                    place_cell(design, user.cell, cell->bel, placed_cells,
+                               visit_cells);
+            }
+            if (net->driver.cell != nullptr && net->driver.cell->bel == BelId())
+                place_cell(design, net->driver.cell, cell->bel, placed_cells,
+                           visit_cells);
+        }
+    }
+}
+
+void place_design_heuristic(Design *design)
+{
+    size_t total_cells = design->cells.size(), placed_cells = 0;
+    std::queue<CellInfo *> visit_cells;
+    // Initial constraints placer
+    for (auto cell_entry : design->cells) {
+        CellInfo *cell = cell_entry.second;
+        auto loc = cell->attrs.find("BEL");
+        if (loc != cell->attrs.end()) {
+            std::string loc_name = loc->second;
+            BelId bel = design->chip.getBelByName(IdString(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());
+            }
+
+            BelType bel_type = design->chip.getBelType(bel);
+            if (bel_type != belTypeFromId(cell->type)) {
+                log_error("Bel \'%s\' of type \'%s\' does not match cell "
+                          "\'%s\' of type \'%s\'",
+                          loc_name.c_str(), belTypeToId(bel_type).c_str(),
+                          cell->name.c_str(), cell->type.c_str());
+            }
+
+            cell->bel = bel;
+            design->chip.bindBel(bel, cell->name);
+            placed_cells++;
+            visit_cells.push(cell);
+        }
+    }
+    while (placed_cells < total_cells) {
+        if (!visit_cells.empty()) {
+            CellInfo *next = visit_cells.front();
+            visit_cells.pop();
+            place_cell_neighbours(design, next, placed_cells, visit_cells);
+        } else {
+            // Nothing to visit (netlist is split), pick the next unplaced cell
+            for (auto cell : design->cells) {
+                CellInfo *ci = cell.second;
+                if (ci->bel == BelId())
+                    place_cell(design, ci, BelId(), placed_cells, visit_cells);
+            }
+        }
+        log_info("placed %d/%d\n", placed_cells, total_cells);
+    }
+}
+
 NEXTPNR_NAMESPACE_END
diff --git a/common/place.h b/common/place.h
index 7df84873..fd4de534 100644
--- a/common/place.h
+++ b/common/place.h
@@ -25,6 +25,8 @@ NEXTPNR_NAMESPACE_BEGIN
 
 extern void place_design(Design *design);
 
+extern void place_design_heuristic(Design *design);
+
 NEXTPNR_NAMESPACE_END
 
 #endif // PLACE_H