3 files changed, 55 insertions, 30 deletions

diff --git a/common/place_sa.cc b/common/place_sa.cc
index 22e750c2..12ca30d8 100644
--- a/common/place_sa.cc
+++ b/common/place_sa.cc
@@ -66,39 +66,64 @@ static float random_float_upto(rnd_state &rnd, float limit)
 
 static int random_int_between(rnd_state &rnd, int a, int b)
 {
-    return a + int(random_float_upto(rnd, b - a));
+    return a + int(random_float_upto(rnd, b - a) - 0.00001);
 }
 
 // Initial random placement
 static void place_initial(Design *design, CellInfo *cell, rnd_state &rnd)
 {
-    BelId best_bel = BelId();
-    float best_score = std::numeric_limits<float>::infinity();
-    Chip &chip = design->chip;
-    if (cell->bel != BelId()) {
-        chip.unbindBel(cell->bel);
-        cell->bel = BelId();
-    }
-    BelType targetType = belTypeFromId(cell->type);
-    for (auto bel : chip.getBels()) {
-        if (chip.getBelType(bel) == targetType && chip.checkBelAvail(bel) &&
-            isValidBelForCell(design, cell, bel)) {
-            float score = random_float_upto(rnd, 1.0);
-            if (score <= best_score) {
-                best_score = score;
-                best_bel = bel;
+    bool all_placed = false;
+    int iters = 25;
+    while (!all_placed) {
+        BelId best_bel = BelId();
+        float best_score = std::numeric_limits<float>::infinity(),
+              best_ripup_score = std::numeric_limits<float>::infinity();
+        Chip &chip = design->chip;
+        CellInfo *ripup_target = nullptr;
+        BelId ripup_bel = BelId();
+        if (cell->bel != BelId()) {
+            chip.unbindBel(cell->bel);
+            cell->bel = BelId();
+        }
+        BelType targetType = belTypeFromId(cell->type);
+        for (auto bel : chip.getBels()) {
+            if (chip.getBelType(bel) == targetType &&
+                isValidBelForCell(design, cell, bel)) {
+                if (chip.checkBelAvail(bel)) {
+                    float score = random_float_upto(rnd, 1.0);
+                    if (score <= best_score) {
+                        best_score = score;
+                        best_bel = bel;
+                    }
+                } else {
+                    float score = random_float_upto(rnd, 1.0);
+                    if (score <= best_ripup_score) {
+                        best_ripup_score = score;
+                        ripup_target =
+                                design->cells.at(chip.getBelCell(bel, true));
+                        ripup_bel = bel;
+                    }
+                }
             }
         }
-    }
-    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);
+        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(), cell->type.c_str());
+            --iters;
+            chip.unbindBel(ripup_target->bel);
+            ripup_target->bel = BelId();
+            best_bel = ripup_bel;
+        } else {
+            all_placed = true;
+        }
+        cell->bel = best_bel;
+        chip.bindBel(cell->bel, cell->name);
 
-    // Back annotate location
-    cell->attrs["BEL"] = chip.getBelName(cell->bel).str();
+        // Back annotate location
+        cell->attrs["BEL"] = chip.getBelName(cell->bel).str();
+        cell = ripup_target;
+    }
 }
 
 // Stores the state of the SA placer
@@ -268,7 +293,7 @@ BelId random_bel_for_cell(Design *design, CellInfo *cell, SAState &state,
     }
 }
 
-void place_design_sa(Design *design)
+void place_design_sa(Design *design, int seed)
 {
     SAState state;
 
@@ -304,7 +329,7 @@ void place_design_sa(Design *design)
     }
     log_info("place_constraints placed %d\n", int(placed_cells));
     rnd_state rnd;
-    rnd.state = 1;
+    rnd.state = seed;
     std::vector<CellInfo *> autoplaced;
     // Sort to-place cells for deterministic initial placement
     for (auto cell : design->cells) {
diff --git a/common/place_sa.h b/common/place_sa.h
index f320111e..944cb97e 100644
--- a/common/place_sa.h
+++ b/common/place_sa.h
@@ -23,7 +23,7 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-extern void place_design_sa(Design *design);
+extern void place_design_sa(Design *design, int seed);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/common/route.cc b/common/route.cc
index 32212c7d..247c8840 100644
--- a/common/route.cc
+++ b/common/route.cc
@@ -440,8 +440,8 @@ void route_design(Design *design, bool verbose)
                          "routing.\n",
                          int(netsQueue.size()));
 
-            ripup_pip_penalty += 5;
-            ripup_wire_penalty += 5;
+            ripup_pip_penalty *= 1.5;
+            ripup_wire_penalty *= 1.5;
         }
     }