Merge pull request #393 from YosysHQ/dave/xilinx-place-backport

Backporting some placer changes from nextpnr-xilinx

4 files changed, 348 insertions, 127 deletions

diff --git a/common/placer1.cc b/common/placer1.cc
index 96424957..1ba50e28 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -68,7 +68,10 @@ class SAPlacer
         int x0 = 0, x1 = 0, y0 = 0, y1 = 0;
         // Number of cells at each extremity
         int nx0 = 0, nx1 = 0, ny0 = 0, ny1 = 0;
-        wirelen_t hpwl() const { return wirelen_t((x1 - x0) + (y1 - y0)); }
+        wirelen_t hpwl(const Placer1Cfg &cfg) const
+        {
+            return wirelen_t(cfg.hpwl_scale_x * (x1 - x0) + cfg.hpwl_scale_y * (y1 - y0));
+        }
     };
 
   public:
@@ -256,6 +259,9 @@ class SAPlacer
         last_wirelen_cost = curr_wirelen_cost;
         last_timing_cost = curr_timing_cost;
 
+        if (cfg.netShareWeight > 0)
+            setup_nets_by_tile();
+
         wirelen_t avg_wirelen = curr_wirelen_cost;
         wirelen_t min_wirelen = curr_wirelen_cost;
 
@@ -510,6 +516,11 @@ class SAPlacer
         if (other_cell != nullptr)
             old_dist += get_constraints_distance(ctx, other_cell);
         double delta = 0;
+
+        int net_delta_score = 0;
+        if (cfg.netShareWeight > 0)
+            net_delta_score += update_nets_by_tile(cell, ctx->getBelLocation(cell->bel), ctx->getBelLocation(newBel));
+
         ctx->unbindBel(oldBel);
         if (other_cell != nullptr) {
             ctx->unbindBel(newBel);
@@ -519,6 +530,9 @@ class SAPlacer
 
         if (other_cell != nullptr) {
             ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK);
+            if (cfg.netShareWeight > 0)
+                net_delta_score +=
+                        update_nets_by_tile(other_cell, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel));
         }
 
         add_move_cell(moveChange, cell, oldBel);
@@ -543,6 +557,8 @@ class SAPlacer
         delta = lambda * (moveChange.timing_delta / std::max<double>(last_timing_cost, epsilon)) +
                 (1 - lambda) * (double(moveChange.wirelen_delta) / std::max<double>(last_wirelen_cost, epsilon));
         delta += (cfg.constraintWeight / temp) * (new_dist - old_dist) / last_wirelen_cost;
+        if (cfg.netShareWeight > 0)
+            delta += -cfg.netShareWeight * (net_delta_score / std::max<double>(total_net_share, epsilon));
         n_move++;
         // SA acceptance criterea
         if (delta < 0 || (temp > 1e-8 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
@@ -564,7 +580,11 @@ class SAPlacer
         ctx->bindBel(oldBel, cell, STRENGTH_WEAK);
         if (other_cell != nullptr) {
             ctx->bindBel(newBel, other_cell, STRENGTH_WEAK);
+            if (cfg.netShareWeight > 0)
+                update_nets_by_tile(other_cell, ctx->getBelLocation(oldBel), ctx->getBelLocation(newBel));
         }
+        if (cfg.netShareWeight > 0)
+            update_nets_by_tile(cell, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel));
         return false;
     }
 
@@ -585,8 +605,13 @@ class SAPlacer
             ctx->unbindBel(newBel);
         ctx->unbindBel(oldBel);
         ctx->bindBel(newBel, cell, is_constrained(cell) ? STRENGTH_STRONG : STRENGTH_WEAK);
-        if (bound != nullptr)
+        if (bound != nullptr) {
             ctx->bindBel(oldBel, bound, is_constrained(bound) ? STRENGTH_STRONG : STRENGTH_WEAK);
+            if (cfg.netShareWeight > 0)
+                update_nets_by_tile(bound, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel));
+        }
+        if (cfg.netShareWeight > 0)
+            update_nets_by_tile(cell, ctx->getBelLocation(oldBel), ctx->getBelLocation(newBel));
         return oldBel;
     }
 
@@ -608,6 +633,7 @@ class SAPlacer
         std::vector<std::pair<CellInfo *, BelId>> moves_made;
         std::vector<std::pair<CellInfo *, BelId>> dest_bels;
         double delta = 0;
+        int orig_share_cost = total_net_share;
         moveChange.reset(this);
 #if 0
         if (ctx->debug)
@@ -660,6 +686,10 @@ class SAPlacer
         compute_cost_changes(moveChange);
         delta = lambda * (moveChange.timing_delta / last_timing_cost) +
                 (1 - lambda) * (double(moveChange.wirelen_delta) / last_wirelen_cost);
+        if (cfg.netShareWeight > 0) {
+            delta +=
+                    cfg.netShareWeight * (orig_share_cost - total_net_share) / std::max<double>(total_net_share, 1e-20);
+        }
         n_move++;
         // SA acceptance criterea
         if (delta < 0 || (temp > 1e-9 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) {
@@ -689,8 +719,10 @@ class SAPlacer
 
         int dx = diameter, dy = diameter;
         if (cell->region != nullptr && cell->region->constr_bels) {
-            dx = std::min(diameter, (region_bounds[cell->region->name].x1 - region_bounds[cell->region->name].x0) + 1);
-            dy = std::min(diameter, (region_bounds[cell->region->name].y1 - region_bounds[cell->region->name].y0) + 1);
+            dx = std::min(cfg.hpwl_scale_x * diameter,
+                          (region_bounds[cell->region->name].x1 - region_bounds[cell->region->name].x0) + 1);
+            dy = std::min(cfg.hpwl_scale_y * diameter,
+                          (region_bounds[cell->region->name].y1 - region_bounds[cell->region->name].y0) + 1);
             // Clamp location to within bounds
             curr_loc.x = std::max(region_bounds[cell->region->name].x0, curr_loc.x);
             curr_loc.x = std::min(region_bounds[cell->region->name].x1, curr_loc.x);
@@ -820,7 +852,7 @@ class SAPlacer
     {
         wirelen_t cost = 0;
         for (const auto &net : net_bounds)
-            cost += net.hpwl();
+            cost += net.hpwl(cfg);
         return cost;
     }
 
@@ -1061,10 +1093,10 @@ class SAPlacer
         }
 
         for (const auto &bc : md.bounds_changed_nets_x)
-            md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl();
+            md.wirelen_delta += md.new_net_bounds[bc].hpwl(cfg) - net_bounds[bc].hpwl(cfg);
         for (const auto &bc : md.bounds_changed_nets_y)
             if (md.already_bounds_changed_x[bc] == MoveChangeData::NO_CHANGE)
-                md.wirelen_delta += md.new_net_bounds[bc].hpwl() - net_bounds[bc].hpwl();
+                md.wirelen_delta += md.new_net_bounds[bc].hpwl(cfg) - net_bounds[bc].hpwl(cfg);
 
         if (cfg.timing_driven) {
             for (const auto &tc : md.changed_arcs) {
@@ -1100,8 +1132,66 @@ class SAPlacer
         }
     }
 
+    // Simple routeability driven placement
+    const int large_cell_thresh = 50;
+    int total_net_share = 0;
+    std::vector<std::vector<std::unordered_map<IdString, int>>> nets_by_tile;
+    void setup_nets_by_tile()
+    {
+        total_net_share = 0;
+        nets_by_tile.resize(max_x + 1, std::vector<std::unordered_map<IdString, int>>(max_y + 1));
+        for (auto cell : sorted(ctx->cells)) {
+            CellInfo *ci = cell.second;
+            if (int(ci->ports.size()) > large_cell_thresh)
+                continue;
+            Loc loc = ctx->getBelLocation(ci->bel);
+            auto &nbt = nets_by_tile.at(loc.x).at(loc.y);
+            for (const auto &port : ci->ports) {
+                if (port.second.net == nullptr)
+                    continue;
+                if (port.second.net->driver.cell == nullptr || ctx->getBelGlobalBuf(port.second.net->driver.cell->bel))
+                    continue;
+                int &s = nbt[port.second.net->name];
+                if (s > 0)
+                    ++total_net_share;
+                ++s;
+            }
+        }
+    }
+
+    int update_nets_by_tile(CellInfo *ci, Loc old_loc, Loc new_loc)
+    {
+        if (int(ci->ports.size()) > large_cell_thresh)
+            return 0;
+        int loss = 0, gain = 0;
+        auto &nbt_old = nets_by_tile.at(old_loc.x).at(old_loc.y);
+        auto &nbt_new = nets_by_tile.at(new_loc.x).at(new_loc.y);
+
+        for (const auto &port : ci->ports) {
+            if (port.second.net == nullptr)
+                continue;
+            if (port.second.net->driver.cell == nullptr || ctx->getBelGlobalBuf(port.second.net->driver.cell->bel))
+                continue;
+            int &o = nbt_old[port.second.net->name];
+            --o;
+            NPNR_ASSERT(o >= 0);
+            if (o > 0)
+                ++loss;
+            int &n = nbt_new[port.second.net->name];
+            if (n > 0)
+                ++gain;
+            ++n;
+        }
+        int delta = gain - loss;
+        total_net_share += delta;
+        return delta;
+    }
+
     // Get the combined wirelen/timing metric
-    inline double curr_metric() { return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost; }
+    inline double curr_metric()
+    {
+        return lambda * curr_timing_cost + (1 - lambda) * curr_wirelen_cost - cfg.netShareWeight * total_net_share;
+    }
 
     // Map nets to their bounding box (so we can skip recompute for moves that do not exceed the bounds
     std::vector<BoundingBox> net_bounds;
@@ -1139,12 +1229,15 @@ class SAPlacer
 Placer1Cfg::Placer1Cfg(Context *ctx)
 {
     constraintWeight = ctx->setting<float>("placer1/constraintWeight", 10);
+    netShareWeight = ctx->setting<float>("placer1/netShareWeight", 0);
     minBelsForGridPick = ctx->setting<int>("placer1/minBelsForGridPick", 64);
     budgetBased = ctx->setting<bool>("placer1/budgetBased", false);
     startTemp = ctx->setting<float>("placer1/startTemp", 1);
     timingFanoutThresh = std::numeric_limits<int>::max();
     timing_driven = ctx->setting<bool>("timing_driven");
     slack_redist_iter = ctx->setting<int>("slack_redist_iter");
+    hpwl_scale_x = 1;
+    hpwl_scale_y = 1;
 }
 
 bool placer1(Context *ctx, Placer1Cfg cfg)
diff --git a/common/placer1.h b/common/placer1.h
index 1356db3e..cf66151c 100644
--- a/common/placer1.h
+++ b/common/placer1.h
@@ -27,13 +27,14 @@ NEXTPNR_NAMESPACE_BEGIN
 struct Placer1Cfg
 {
     Placer1Cfg(Context *ctx);
-    float constraintWeight;
+    float constraintWeight, netShareWeight;
     int minBelsForGridPick;
     bool budgetBased;
     float startTemp;
     int timingFanoutThresh;
     bool timing_driven;
     int slack_redist_iter;
+    int hpwl_scale_x, hpwl_scale_y;
 };
 
 extern bool placer1(Context *ctx, Placer1Cfg cfg);
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index f336f6e4..c04e7091 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -97,7 +97,7 @@ template <typename T> struct EquationSystem
 
     void add_rhs(int row, T val) { rhs[row] += val; }
 
-    void solve(std::vector<T> &x)
+    void solve(std::vector<T> &x, float tolerance)
     {
         using namespace Eigen;
         if (x.empty())
@@ -123,7 +123,7 @@ template <typename T> struct EquationSystem
             vb[i] = rhs.at(i);
 
         ConjugateGradient<SparseMatrix<T>, Lower | Upper> solver;
-        solver.setTolerance(1e-5);
+        solver.setTolerance(tolerance);
         VectorXd xr = solver.compute(mat).solveWithGuess(vb, vx);
         for (int i = 0; i < int(x.size()); i++)
             x.at(i) = xr[i];
@@ -190,6 +190,13 @@ class HeAPPlacer
                 break;
             }
 
+        if (cfg.placeAllAtOnce) {
+            // Never want to deal with LUTs, FFs, MUXFxs seperately,
+            // for now disable all single-cell-type runs and only have heteregenous
+            // runs
+            heap_runs.clear();
+        }
+
         heap_runs.push_back(all_celltypes);
         // The main HeAP placer loop
         log_info("Running main analytical placer.\n");
@@ -218,8 +225,14 @@ class HeAPPlacer
                 solved_hpwl = total_hpwl();
 
                 update_all_chains();
+
+                for (const auto &group : cfg.cellGroups)
+                    CutSpreader(this, group).run();
+
                 for (auto type : sorted(run))
-                    CutSpreader(this, type).run();
+                    if (std::all_of(cfg.cellGroups.begin(), cfg.cellGroups.end(),
+                                    [type](const std::unordered_set<IdString> &grp) { return !grp.count(type); }))
+                        CutSpreader(this, {type}).run();
 
                 update_all_chains();
                 spread_hpwl = total_hpwl();
@@ -577,13 +590,15 @@ class HeAPPlacer
     {
         const auto &base = cell_locs[cell->name];
         for (auto child : cell->constr_children) {
-            chain_size[root->name]++;
+            // FIXME: Improve handling of heterogeneous chains
+            if (child->type == root->type)
+                chain_size[root->name]++;
             if (child->constr_x != child->UNCONSTR)
-                cell_locs[child->name].x = std::min(max_x, base.x + child->constr_x);
+                cell_locs[child->name].x = std::max(0, std::min(max_x, base.x + child->constr_x));
             else
                 cell_locs[child->name].x = base.x; // better handling of UNCONSTR?
             if (child->constr_y != child->UNCONSTR)
-                cell_locs[child->name].y = std::min(max_y, base.y + child->constr_y);
+                cell_locs[child->name].y = std::max(0, std::min(max_y, base.y + child->constr_y));
             else
                 cell_locs[child->name].y = base.y; // better handling of UNCONSTR?
             chain_root[child->name] = root;
@@ -671,7 +686,9 @@ class HeAPPlacer
                     if (other == &port)
                         return;
                     int o_pos = cell_pos(other->cell);
-                    double weight = 1.0 / (ni->users.size() * std::max<double>(1, std::abs(o_pos - this_pos)));
+                    double weight = 1.0 / (ni->users.size() *
+                                           std::max<double>(1, (yaxis ? cfg.hpwl_scale_y : cfg.hpwl_scale_x) *
+                                                                       std::abs(o_pos - this_pos)));
 
                     if (user_idx != -1 && net_crit.count(ni->name)) {
                         auto &nc = net_crit.at(ni->name);
@@ -697,7 +714,9 @@ class HeAPPlacer
                 int l_pos = legal_pos(solve_cells.at(row));
                 int c_pos = cell_pos(solve_cells.at(row));
 
-                double weight = alpha * iter / std::max<double>(1, std::abs(l_pos - c_pos));
+                double weight =
+                        alpha * iter /
+                        std::max<double>(1, (yaxis ? cfg.hpwl_scale_y : cfg.hpwl_scale_x) * std::abs(l_pos - c_pos));
                 // Add an arc from legalised to current position
                 es.add_coeff(row, row, weight);
                 es.add_rhs(row, weight * l_pos);
@@ -712,7 +731,7 @@ class HeAPPlacer
         auto cell_pos = [&](CellInfo *cell) { return yaxis ? cell_locs.at(cell->name).y : cell_locs.at(cell->name).x; };
         std::vector<double> vals;
         std::transform(solve_cells.begin(), solve_cells.end(), std::back_inserter(vals), cell_pos);
-        es.solve(vals);
+        es.solve(vals, cfg.solverTolerance);
         for (size_t i = 0; i < vals.size(); i++)
             if (yaxis) {
                 cell_locs.at(solve_cells.at(i)->name).rawy = vals.at(i);
@@ -748,7 +767,7 @@ class HeAPPlacer
                 ymin = std::min(ymin, usrloc.y);
                 ymax = std::max(ymax, usrloc.y);
             }
-            hpwl += (xmax - xmin) + (ymax - ymin);
+            hpwl += cfg.hpwl_scale_x * (xmax - xmin) + cfg.hpwl_scale_y * (ymax - ymin);
         }
         return hpwl;
     }
@@ -1013,7 +1032,6 @@ class HeAPPlacer
         sl_time += std::chrono::duration<float>(endt - startt).count();
     }
     // Implementation of the cut-based spreading as described in the HeAP/SimPL papers
-    static constexpr float beta = 0.9;
 
     template <typename T> T limit_to_reg(Region *reg, T val, bool dir)
     {
@@ -1033,22 +1051,33 @@ class HeAPPlacer
     {
         int id;
         int x0, y0, x1, y1;
-        int cells, bels;
-        bool overused() const
+        std::vector<int> cells, bels;
+        bool overused(float beta) const
         {
-            if (bels < 4)
-                return cells > bels;
-            else
-                return cells > beta * bels;
+            for (size_t t = 0; t < cells.size(); t++) {
+                if (bels.at(t) < 4) {
+                    if (cells.at(t) > bels.at(t))
+                        return true;
+                } else {
+                    if (cells.at(t) > beta * bels.at(t))
+                        return true;
+                }
+            }
+            return false;
         }
     };
 
     class CutSpreader
     {
       public:
-        CutSpreader(HeAPPlacer *p, IdString beltype)
-                : p(p), ctx(p->ctx), beltype(beltype), fb(p->fast_bels.at(std::get<0>(p->bel_types.at(beltype))))
+        CutSpreader(HeAPPlacer *p, const std::unordered_set<IdString> &beltype) : p(p), ctx(p->ctx), beltype(beltype)
         {
+            int idx = 0;
+            for (IdString type : sorted(beltype)) {
+                type_index[type] = idx;
+                fb.emplace_back(&(p->fast_bels.at(std::get<0>(p->bel_types.at(type)))));
+                ++idx;
+            }
         }
         static int seq;
         void run()
@@ -1076,8 +1105,11 @@ class HeAPPlacer
                 if (merged_regions.count(r.id))
                     continue;
 #if 0
-                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);
+                for (auto t : sorted(beltype)) {
+                    log_info("%s (%d, %d) |_> (%d, %d) %d/%d\n", t.c_str(ctx), r.x0, r.y0, r.x1, r.y1,
+                             r.cells.at(type_index.at(t)), r.bels.at(type_index.at(t)));
+                }
+
 #endif
                 workqueue.emplace(r.id, false);
                 // cut_region(r, false);
@@ -1086,7 +1118,7 @@ class HeAPPlacer
                 auto front = workqueue.front();
                 workqueue.pop();
                 auto &r = regions.at(front.first);
-                if (r.cells == 0)
+                if (std::all_of(r.cells.begin(), r.cells.end(), [](int x) { return x == 0; }))
                     continue;
                 auto res = cut_region(r, front.second);
                 if (res) {
@@ -1128,37 +1160,41 @@ class HeAPPlacer
       private:
         HeAPPlacer *p;
         Context *ctx;
-        IdString beltype;
-        std::vector<std::vector<int>> occupancy;
+        std::unordered_set<IdString> beltype;
+        std::unordered_map<IdString, int> type_index;
+        std::vector<std::vector<std::vector<int>>> occupancy;
         std::vector<std::vector<int>> groups;
         std::vector<std::vector<ChainExtent>> chaines;
         std::map<IdString, ChainExtent> cell_extents;
 
-        std::vector<std::vector<std::vector<BelId>>> &fb;
+        std::vector<std::vector<std::vector<std::vector<BelId>>> *> fb;
 
         std::vector<SpreaderRegion> regions;
         std::unordered_set<int> merged_regions;
         // Cells at a location, sorted by real (not integer) x and y
         std::vector<std::vector<std::vector<CellInfo *>>> cells_at_location;
 
-        int occ_at(int x, int y) { return occupancy.at(x).at(y); }
+        int occ_at(int x, int y, int type) { return occupancy.at(x).at(y).at(type); }
 
-        int bels_at(int x, int y)
+        int bels_at(int x, int y, int type)
         {
-            if (x >= int(fb.size()) || y >= int(fb.at(x).size()))
+            if (x >= int(fb.at(type)->size()) || y >= int(fb.at(type)->at(x).size()))
                 return 0;
-            return int(fb.at(x).at(y).size());
+            return int(fb.at(type)->at(x).at(y).size());
         }
 
         void init()
         {
-            occupancy.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, 0));
+            occupancy.resize(p->max_x + 1,
+                             std::vector<std::vector<int>>(p->max_y + 1, std::vector<int>(beltype.size(), 0)));
             groups.resize(p->max_x + 1, std::vector<int>(p->max_y + 1, -1));
             chaines.resize(p->max_x + 1, std::vector<ChainExtent>(p->max_y + 1));
             cells_at_location.resize(p->max_x + 1, std::vector<std::vector<CellInfo *>>(p->max_y + 1));
             for (int x = 0; x <= p->max_x; x++)
                 for (int y = 0; y <= p->max_y; y++) {
-                    occupancy.at(x).at(y) = 0;
+                    for (int t = 0; t < int(beltype.size()); t++) {
+                        occupancy.at(x).at(y).at(t) = 0;
+                    }
                     groups.at(x).at(y) = -1;
                     chaines.at(x).at(y) = {x, y, x, y};
                 }
@@ -1175,11 +1211,11 @@ class HeAPPlacer
             };
 
             for (auto &cell : p->cell_locs) {
-                if (ctx->cells.at(cell.first)->type != beltype)
+                if (!beltype.count(ctx->cells.at(cell.first)->type))
                     continue;
                 if (ctx->cells.at(cell.first)->belStrength > STRENGTH_STRONG)
                     continue;
-                occupancy.at(cell.second.x).at(cell.second.y)++;
+                occupancy.at(cell.second.x).at(cell.second.y).at(type_index.at(ctx->cells.at(cell.first)->type))++;
                 // Compute ultimate extent of each chain root
                 if (p->chain_root.count(cell.first)) {
                     set_chain_ext(p->chain_root.at(cell.first)->name, cell.second.x, cell.second.y);
@@ -1188,7 +1224,7 @@ class HeAPPlacer
                 }
             }
             for (auto &cell : p->cell_locs) {
-                if (ctx->cells.at(cell.first)->type != beltype)
+                if (!beltype.count(ctx->cells.at(cell.first)->type))
                     continue;
                 // Transfer chain extents to the actual chaines structure
                 ChainExtent *ce = nullptr;
@@ -1205,7 +1241,7 @@ class HeAPPlacer
                 }
             }
             for (auto cell : p->solve_cells) {
-                if (cell->type != beltype)
+                if (!beltype.count(cell->type))
                     continue;
                 cells_at_location.at(p->cell_locs.at(cell->name).x).at(p->cell_locs.at(cell->name).y).push_back(cell);
             }
@@ -1218,8 +1254,10 @@ class HeAPPlacer
                     // log_info("%d %d\n", groups.at(x).at(y), mergee.id);
                     NPNR_ASSERT(groups.at(x).at(y) == mergee.id);
                     groups.at(x).at(y) = merged.id;
-                    merged.cells += occ_at(x, y);
-                    merged.bels += bels_at(x, y);
+                    for (size_t t = 0; t < beltype.size(); t++) {
+                        merged.cells.at(t) += occ_at(x, y, t);
+                        merged.bels.at(t) += bels_at(x, y, t);
+                    }
                 }
             merged_regions.insert(mergee.id);
             grow_region(merged, mergee.x0, mergee.y0, mergee.x1, mergee.y1);
@@ -1239,8 +1277,10 @@ class HeAPPlacer
             auto process_location = [&](int x, int y) {
                 // Merge with any overlapping regions
                 if (groups.at(x).at(y) == -1) {
-                    r.bels += bels_at(x, y);
-                    r.cells += occ_at(x, y);
+                    for (int t = 0; t < int(beltype.size()); t++) {
+                        r.bels.at(t) += bels_at(x, y, t);
+                        r.cells.at(t) += occ_at(x, y, t);
+                    }
                 }
                 if (groups.at(x).at(y) != -1 && groups.at(x).at(y) != r.id)
                     merge_regions(r, regions.at(groups.at(x).at(y)));
@@ -1268,7 +1308,16 @@ class HeAPPlacer
             for (int x = 0; x <= p->max_x; x++)
                 for (int y = 0; y <= p->max_y; y++) {
                     // Either already in a group, or not overutilised. Ignore
-                    if (groups.at(x).at(y) != -1 || (occ_at(x, y) <= bels_at(x, y)))
+                    if (groups.at(x).at(y) != -1)
+                        continue;
+                    bool overutilised = false;
+                    for (size_t t = 0; t < beltype.size(); t++) {
+                        if (occ_at(x, y, t) > bels_at(x, y, t)) {
+                            overutilised = true;
+                            break;
+                        }
+                    }
+                    if (!overutilised)
                         continue;
                     // log_info("%d %d %d\n", x, y, occ_at(x, y));
                     int id = int(regions.size());
@@ -1277,8 +1326,10 @@ class HeAPPlacer
                     reg.id = id;
                     reg.x0 = reg.x1 = x;
                     reg.y0 = reg.y1 = y;
-                    reg.bels = bels_at(x, y);
-                    reg.cells = occ_at(x, y);
+                    for (size_t t = 0; t < beltype.size(); t++) {
+                        reg.bels.push_back(bels_at(x, y, t));
+                        reg.cells.push_back(occ_at(x, y, t));
+                    }
                     // Make sure we cover carries, etc
                     grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1, true);
 
@@ -1292,11 +1343,13 @@ class HeAPPlacer
                         if (reg.x1 < p->max_x) {
                             bool over_occ_x = false;
                             for (int y1 = reg.y0; y1 <= reg.y1; y1++) {
-                                if (occ_at(reg.x1 + 1, y1) > bels_at(reg.x1 + 1, y1)) {
-                                    // log_info("(%d, %d) occ %d bels %d\n", reg.x1+ 1, y1, occ_at(reg.x1 + 1, y1),
-                                    // bels_at(reg.x1 + 1, y1));
-                                    over_occ_x = true;
-                                    break;
+                                for (size_t t = 0; t < beltype.size(); t++) {
+                                    if (occ_at(reg.x1 + 1, y1, t) > bels_at(reg.x1 + 1, y1, t)) {
+                                        // log_info("(%d, %d) occ %d bels %d\n", reg.x1+ 1, y1, occ_at(reg.x1 + 1, y1),
+                                        // bels_at(reg.x1 + 1, y1));
+                                        over_occ_x = true;
+                                        break;
+                                    }
                                 }
                             }
                             if (over_occ_x) {
@@ -1308,11 +1361,13 @@ class HeAPPlacer
                         if (reg.y1 < p->max_y) {
                             bool over_occ_y = false;
                             for (int x1 = reg.x0; x1 <= reg.x1; x1++) {
-                                if (occ_at(x1, reg.y1 + 1) > bels_at(x1, reg.y1 + 1)) {
-                                    // log_info("(%d, %d) occ %d bels %d\n", x1, reg.y1 + 1, occ_at(x1, reg.y1 + 1),
-                                    // bels_at(x1, reg.y1 + 1));
-                                    over_occ_y = true;
-                                    break;
+                                for (size_t t = 0; t < beltype.size(); t++) {
+                                    if (occ_at(x1, reg.y1 + 1, t) > bels_at(x1, reg.y1 + 1, t)) {
+                                        // log_info("(%d, %d) occ %d bels %d\n", x1, reg.y1 + 1, occ_at(x1, reg.y1 + 1),
+                                        // bels_at(x1, reg.y1 + 1));
+                                        over_occ_y = true;
+                                        break;
+                                    }
                                 }
                             }
                             if (over_occ_y) {
@@ -1328,8 +1383,9 @@ class HeAPPlacer
         void expand_regions()
         {
             std::queue<int> overu_regions;
+            float beta = p->cfg.beta;
             for (auto &r : regions) {
-                if (!merged_regions.count(r.id) && r.overused())
+                if (!merged_regions.count(r.id) && r.overused(beta))
                     overu_regions.push(r.id);
             }
             while (!overu_regions.empty()) {
@@ -1338,38 +1394,43 @@ class HeAPPlacer
                 if (merged_regions.count(rid))
                     continue;
                 auto &reg = regions.at(rid);
-                while (reg.overused()) {
+                while (reg.overused(beta)) {
                     bool changed = false;
-                    if (reg.x0 > 0) {
-                        grow_region(reg, reg.x0 - 1, reg.y0, reg.x1, reg.y1);
-                        changed = true;
-                        if (!reg.overused())
-                            break;
-                    }
-                    if (reg.x1 < p->max_x) {
-                        grow_region(reg, reg.x0, reg.y0, reg.x1 + 1, reg.y1);
-                        changed = true;
-                        if (!reg.overused())
-                            break;
-                    }
-                    if (reg.y0 > 0) {
-                        grow_region(reg, reg.x0, reg.y0 - 1, reg.x1, reg.y1);
-                        changed = true;
-                        if (!reg.overused())
-                            break;
+                    for (int j = 0; j < p->cfg.spread_scale_x; j++) {
+                        if (reg.x0 > 0) {
+                            grow_region(reg, reg.x0 - 1, reg.y0, reg.x1, reg.y1);
+                            changed = true;
+                            if (!reg.overused(beta))
+                                break;
+                        }
+                        if (reg.x1 < p->max_x) {
+                            grow_region(reg, reg.x0, reg.y0, reg.x1 + 1, reg.y1);
+                            changed = true;
+                            if (!reg.overused(beta))
+                                break;
+                        }
                     }
-                    if (reg.y1 < p->max_y) {
-                        grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1 + 1);
-                        changed = true;
-                        if (!reg.overused())
-                            break;
+                    for (int j = 0; j < p->cfg.spread_scale_y; j++) {
+                        if (reg.y0 > 0) {
+                            grow_region(reg, reg.x0, reg.y0 - 1, reg.x1, reg.y1);
+                            changed = true;
+                            if (!reg.overused(beta))
+                                break;
+                        }
+                        if (reg.y1 < p->max_y) {
+                            grow_region(reg, reg.x0, reg.y0, reg.x1, reg.y1 + 1);
+                            changed = true;
+                            if (!reg.overused(beta))
+                                break;
+                        }
                     }
                     if (!changed) {
-                        if (reg.cells > reg.bels)
-                            log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0,
-                                      reg.x1, reg.y1, reg.cells, beltype.c_str(ctx));
-                        else
-                            break;
+                        for (auto bt : sorted(beltype)) {
+                            if (reg.cells > reg.bels)
+                                log_error("Failed to expand region (%d, %d) |_> (%d, %d) of %d %ss\n", reg.x0, reg.y0,
+                                          reg.x1, reg.y1, reg.cells.at(type_index.at(bt)), bt.c_str(ctx));
+                        }
+                        break;
                     }
                 }
             }
@@ -1388,7 +1449,8 @@ class HeAPPlacer
             for (int x = r.x0; x <= r.x1; x++) {
                 for (int y = r.y0; y <= r.y1; y++) {
                     std::copy(cal.at(x).at(y).begin(), cal.at(x).at(y).end(), std::back_inserter(cut_cells));
-                    total_bels += bels_at(x, y);
+                    for (size_t t = 0; t < beltype.size(); t++)
+                        total_bels += bels_at(x, y, t);
                 }
             }
             for (auto &cell : cut_cells) {
@@ -1410,9 +1472,11 @@ class HeAPPlacer
                     break;
                 pivot++;
             }
-            if (pivot == int(cut_cells.size()))
+            if (pivot >= int(cut_cells.size())) {
                 pivot = int(cut_cells.size()) - 1;
-            // log_info("orig pivot %d lc %d rc %d\n", pivot, pivot_cells, r.cells - pivot_cells);
+            }
+            // log_info("orig pivot %d/%d lc %d rc %d\n", pivot, int(cut_cells.size()), pivot_cells, total_cells -
+            // pivot_cells);
 
             // Find the clearance required either side of the pivot
             int clearance_l = 0, clearance_r = 0;
@@ -1438,10 +1502,11 @@ class HeAPPlacer
             while (trimmed_l < (dir ? r.y1 : r.x1)) {
                 bool have_bels = false;
                 for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++)
-                    if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i) > 0) {
-                        have_bels = true;
-                        break;
-                    }
+                    for (size_t t = 0; t < beltype.size(); t++)
+                        if (bels_at(dir ? i : trimmed_l, dir ? trimmed_l : i, t) > 0) {
+                            have_bels = true;
+                            break;
+                        }
                 if (have_bels)
                     break;
                 trimmed_l++;
@@ -1449,10 +1514,11 @@ class HeAPPlacer
             while (trimmed_r > (dir ? r.y0 : r.x0)) {
                 bool have_bels = false;
                 for (int i = dir ? r.x0 : r.y0; i <= (dir ? r.x1 : r.y1); i++)
-                    if (bels_at(dir ? i : trimmed_r, dir ? trimmed_r : i) > 0) {
-                        have_bels = true;
-                        break;
-                    }
+                    for (size_t t = 0; t < beltype.size(); t++)
+                        if (bels_at(dir ? i : trimmed_r, dir ? trimmed_r : i, t) > 0) {
+                            have_bels = true;
+                            break;
+                        }
                 if (have_bels)
                     break;
                 trimmed_r--;
@@ -1462,50 +1528,94 @@ class HeAPPlacer
                 return {};
             // Now find the initial target cut that minimises utilisation imbalance, whilst
             // meeting the clearance requirements for any large macros
-            int left_cells = pivot_cells, right_cells = total_cells - pivot_cells;
-            int left_bels = 0, right_bels = total_bels;
+            std::vector<int> left_cells_v(beltype.size(), 0), right_cells_v(beltype.size(), 0);
+            std::vector<int> left_bels_v(beltype.size(), 0), right_bels_v(r.bels);
+            for (int i = 0; i <= pivot; i++)
+                left_cells_v.at(type_index.at(cut_cells.at(i)->type)) +=
+                        p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1;
+            for (int i = pivot + 1; i < int(cut_cells.size()); i++)
+                right_cells_v.at(type_index.at(cut_cells.at(i)->type)) +=
+                        p->chain_size.count(cut_cells.at(i)->name) ? p->chain_size.at(cut_cells.at(i)->name) : 1;
+
             int best_tgt_cut = -1;
             double best_deltaU = std::numeric_limits<double>::max();
-            std::pair<int, int> target_cut_bels;
+            // std::pair<int, int> target_cut_bels;
+            std::vector<int> slither_bels(beltype.size(), 0);
             for (int i = trimmed_l; i <= trimmed_r; i++) {
-                int slither_bels = 0;
+                for (size_t t = 0; t < beltype.size(); t++)
+                    slither_bels.at(t) = 0;
                 for (int j = dir ? r.x0 : r.y0; j <= (dir ? r.x1 : r.y1); j++) {
-                    slither_bels += dir ? bels_at(j, i) : bels_at(i, j);
+                    for (size_t t = 0; t < beltype.size(); t++)
+                        slither_bels.at(t) += dir ? bels_at(j, i, t) : bels_at(i, j, t);
                 }
-                left_bels += slither_bels;
-                right_bels -= slither_bels;
+                for (size_t t = 0; t < beltype.size(); t++) {
+                    left_bels_v.at(t) += slither_bels.at(t);
+                    right_bels_v.at(t) -= slither_bels.at(t);
+                }
+
                 if (((i - trimmed_l) + 1) >= clearance_l && ((trimmed_r - i) + 1) >= clearance_r) {
                     // Solution is potentially valid
-                    double aU =
-                            std::abs(double(left_cells) / double(left_bels) - double(right_cells) / double(right_bels));
+                    double aU = 0;
+                    for (size_t t = 0; t < beltype.size(); t++)
+                        aU += (left_cells_v.at(t) + right_cells_v.at(t)) *
+                              std::abs(double(left_cells_v.at(t)) / double(std::max(left_bels_v.at(t), 1)) -
+                                       double(right_cells_v.at(t)) / double(std::max(right_bels_v.at(t), 1)));
                     if (aU < best_deltaU) {
                         best_deltaU = aU;
                         best_tgt_cut = i;
-                        target_cut_bels = std::make_pair(left_bels, right_bels);
                     }
                 }
             }
             if (best_tgt_cut == -1)
                 return {};
-            left_bels = target_cut_bels.first;
-            right_bels = target_cut_bels.second;
-            // log_info("pivot %d target cut %d lc %d lb %d rc %d rb %d\n", pivot, best_tgt_cut, left_cells, left_bels,
-            // right_cells, right_bels);
+            // left_bels = target_cut_bels.first;
+            // right_bels = target_cut_bels.second;
+            for (size_t t = 0; t < beltype.size(); t++) {
+                left_bels_v.at(t) = 0;
+                right_bels_v.at(t) = 0;
+            }
+            for (int x = r.x0; x <= (dir ? r.x1 : best_tgt_cut); x++)
+                for (int y = r.y0; y <= (dir ? best_tgt_cut : r.y1); y++) {
+                    for (size_t t = 0; t < beltype.size(); t++) {
+                        left_bels_v.at(t) += bels_at(x, y, t);
+                    }
+                }
+            for (int x = dir ? r.x0 : (best_tgt_cut + 1); x <= r.x1; x++)
+                for (int y = dir ? (best_tgt_cut + 1) : r.y0; y <= r.y1; y++) {
+                    for (size_t t = 0; t < beltype.size(); t++) {
+                        right_bels_v.at(t) += bels_at(x, y, t);
+                    }
+                }
+            if (std::accumulate(left_bels_v.begin(), left_bels_v.end(), 0) == 0 ||
+                std::accumulate(right_bels_v.begin(), right_bels_v.end(), 0) == 0)
+                return {};
+            // log_info("pivot %d target cut %d lc %d lb %d rc %d rb %d\n", pivot, best_tgt_cut,
+            // std::accumulate(left_cells_v.begin(), left_cells_v.end(), 0), std::accumulate(left_bels_v.begin(),
+            // left_bels_v.end(), 0),
+            //          std::accumulate(right_cells_v.begin(), right_cells_v.end(), 0),
+            //          std::accumulate(right_bels_v.begin(), right_bels_v.end(), 0));
 
             // Peturb the source cut to eliminate overutilisation
-            while (pivot > 0 && (double(left_cells) / double(left_bels) > double(right_cells) / double(right_bels))) {
+            auto is_part_overutil = [&](bool r) {
+                double delta = 0;
+                for (size_t t = 0; t < left_cells_v.size(); t++) {
+                    delta += double(left_cells_v.at(t)) / double(std::max(left_bels_v.at(t), 1)) -
+                             double(right_cells_v.at(t)) / double(std::max(right_bels_v.at(t), 1));
+                }
+                return r ? delta < 0 : delta > 0;
+            };
+            while (pivot > 0 && is_part_overutil(false)) {
                 auto &move_cell = cut_cells.at(pivot);
                 int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1;
-                left_cells -= size;
-                right_cells += size;
+                left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size;
+                right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size;
                 pivot--;
             }
-            while (pivot < int(cut_cells.size()) - 1 &&
-                   (double(left_cells) / double(left_bels) < double(right_cells) / double(right_bels))) {
+            while (pivot < int(cut_cells.size()) - 1 && is_part_overutil(true)) {
                 auto &move_cell = cut_cells.at(pivot + 1);
                 int size = p->chain_size.count(move_cell->name) ? p->chain_size.at(move_cell->name) : 1;
-                left_cells += size;
-                right_cells -= size;
+                left_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) += size;
+                right_cells_v.at(type_index.at(cut_cells.at(pivot)->type)) -= size;
                 pivot++;
             }
             // log_info("peturbed pivot %d lc %d lb %d rc %d rb %d\n", pivot, left_cells, left_bels, right_cells,
@@ -1577,15 +1687,15 @@ class HeAPPlacer
             rl.y0 = r.y0;
             rl.x1 = dir ? r.x1 : best_tgt_cut;
             rl.y1 = dir ? best_tgt_cut : r.y1;
-            rl.cells = left_cells;
-            rl.bels = left_bels;
+            rl.cells = left_cells_v;
+            rl.bels = left_bels_v;
             rr.id = int(regions.size()) + 1;
             rr.x0 = dir ? r.x0 : (best_tgt_cut + 1);
             rr.y0 = dir ? (best_tgt_cut + 1) : r.y0;
             rr.x1 = r.x1;
             rr.y1 = r.y1;
-            rr.cells = right_cells;
-            rr.bels = right_bels;
+            rr.cells = right_cells_v;
+            rr.bels = right_bels_v;
             regions.push_back(rl);
             regions.push_back(rr);
             for (int x = rl.x0; x <= rl.x1; x++)
@@ -1607,9 +1717,17 @@ bool placer_heap(Context *ctx, PlacerHeapCfg cfg) { return HeAPPlacer(ctx, cfg).
 PlacerHeapCfg::PlacerHeapCfg(Context *ctx)
 {
     alpha = ctx->setting<float>("placerHeap/alpha", 0.1);
+    beta = ctx->setting<float>("placerHeap/beta", 0.9);
     criticalityExponent = ctx->setting<int>("placerHeap/criticalityExponent", 2);
     timingWeight = ctx->setting<int>("placerHeap/timingWeight", 10);
     timing_driven = ctx->setting<bool>("timing_driven");
+    solverTolerance = 1e-5;
+    placeAllAtOnce = false;
+
+    hpwl_scale_x = 1;
+    hpwl_scale_y = 1;
+    spread_scale_x = 1;
+    spread_scale_y = 1;
 }
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/placer_heap.h b/common/placer_heap.h
index a018aef8..46c00503 100644
--- a/common/placer_heap.h
+++ b/common/placer_heap.h
@@ -35,12 +35,21 @@ struct PlacerHeapCfg
 {
     PlacerHeapCfg(Context *ctx);
 
-    float alpha;
+    float alpha, beta;
     float criticalityExponent;
     float timingWeight;
     bool timing_driven;
+    float solverTolerance;
+    bool placeAllAtOnce;
 
+    int hpwl_scale_x, hpwl_scale_y;
+    int spread_scale_x, spread_scale_y;
+
+    // These cell types will be randomly locked to prevent singular matrices
     std::unordered_set<IdString> ioBufTypes;
+    // These cell types are part of the same unit (e.g. slices split into
+    // components) so will always be spread together
+    std::vector<std::unordered_set<IdString>> cellGroups;
 };
 
 extern bool placer_heap(Context *ctx, PlacerHeapCfg cfg);