Merge pull request #688 from YosysHQ/gatecat/new-cluster-api

New cluster API

10 files changed, 292 insertions, 349 deletions

diff --git a/common/arch_api.h b/common/arch_api.h
index 7ed81434..01c29a84 100644
--- a/common/arch_api.h
+++ b/common/arch_api.h
@@ -139,6 +139,13 @@ template <typename R> struct ArchAPI : BaseCtx
     virtual typename R::CellTypeRangeT getCellTypes() const = 0;
     virtual typename R::BelBucketRangeT getBelBuckets() const = 0;
     virtual typename R::BucketBelRangeT getBelsInBucket(BelBucketId bucket) const = 0;
+    // Cluster methods
+    virtual CellInfo *getClusterRootCell(ClusterId cluster) const = 0;
+    virtual ArcBounds getClusterBounds(ClusterId cluster) const = 0;
+    virtual Loc getClusterOffset(const CellInfo *cell) const = 0;
+    virtual bool isClusterStrict(const CellInfo *cell) const = 0;
+    virtual bool getClusterPlacement(ClusterId cluster, BelId root_bel,
+                                     std::vector<std::pair<CellInfo *, BelId>> &placement) const = 0;
     // Flow methods
     virtual bool pack() = 0;
     virtual bool place() = 0;
diff --git a/common/base_arch.h b/common/base_arch.h
index d4efe9ce..e9cc8cf0 100644
--- a/common/base_arch.h
+++ b/common/base_arch.h
@@ -25,6 +25,7 @@
 #include <vector>
 
 #include "arch_api.h"
+#include "base_clusterinfo.h"
 #include "idstring.h"
 #include "nextpnr_types.h"
 
@@ -80,6 +81,36 @@ typename std::enable_if<!std::is_same<Tret, Tc>::value, Tret>::type return_if_ma
                       "respective range types are 'const std::vector&'");
 }
 
+// Default implementations of the clustering functions
+template <typename Tid>
+typename std::enable_if<std::is_same<Tid, IdString>::value, CellInfo *>::type get_cluster_root(const BaseCtx *ctx,
+                                                                                               Tid cluster)
+{
+    return ctx->cells.at(cluster).get();
+}
+
+template <typename Tid>
+typename std::enable_if<!std::is_same<Tid, IdString>::value, CellInfo *>::type get_cluster_root(const BaseCtx *ctx,
+                                                                                                Tid cluster)
+{
+    NPNR_ASSERT_FALSE("default implementation of getClusterRootCell requires ClusterId to be IdString");
+}
+
+// Executes the lambda with the base cluster data, only if the derivation works
+template <typename Tret, typename Tcell, typename Tfunc>
+typename std::enable_if<std::is_base_of<BaseClusterInfo, Tcell>::value, Tret>::type
+if_using_basecluster(const Tcell *cell, Tfunc func)
+{
+    return func(static_cast<const BaseClusterInfo *>(cell));
+}
+template <typename Tret, typename Tcell, typename Tfunc>
+typename std::enable_if<!std::is_base_of<BaseClusterInfo, Tcell>::value, Tret>::type
+if_using_basecluster(const Tcell *cell, Tfunc func)
+{
+    NPNR_ASSERT_FALSE(
+            "default implementation of cluster functions requires ArchCellInfo to derive from BaseClusterInfo");
+}
+
 } // namespace
 
 // This contains the relevant range types for the default implementations of Arch functions
@@ -343,6 +374,68 @@ template <typename R> struct BaseArch : ArchAPI<R>
         return return_if_match<const std::vector<BelId> &, typename R::BucketBelRangeT>(bucket_bels.at(bucket));
     }
 
+    // Cluster methods
+    virtual CellInfo *getClusterRootCell(ClusterId cluster) const override { return get_cluster_root(this, cluster); }
+
+    virtual ArcBounds getClusterBounds(ClusterId cluster) const override
+    {
+        return if_using_basecluster<ArcBounds>(get_cluster_root(this, cluster), [](const BaseClusterInfo *cluster) {
+            ArcBounds bounds(0, 0, 0, 0);
+            for (auto child : cluster->constr_children) {
+                if_using_basecluster<void>(child, [&](const BaseClusterInfo *child) {
+                    bounds.x0 = std::min(bounds.x0, child->constr_x);
+                    bounds.y0 = std::min(bounds.y0, child->constr_y);
+                    bounds.x1 = std::max(bounds.x1, child->constr_x);
+                    bounds.y1 = std::max(bounds.y1, child->constr_y);
+                });
+            }
+            return bounds;
+        });
+    }
+
+    virtual Loc getClusterOffset(const CellInfo *cell) const override
+    {
+        return if_using_basecluster<Loc>(cell,
+                                         [](const BaseClusterInfo *c) { return Loc(c->constr_x, c->constr_y, 0); });
+    }
+
+    virtual bool isClusterStrict(const CellInfo *cell) const override { return true; }
+
+    virtual bool getClusterPlacement(ClusterId cluster, BelId root_bel,
+                                     std::vector<std::pair<CellInfo *, BelId>> &placement) const override
+    {
+        CellInfo *root_cell = get_cluster_root(this, cluster);
+        return if_using_basecluster<bool>(root_cell, [&](const BaseClusterInfo *cluster) -> bool {
+            placement.clear();
+            NPNR_ASSERT(root_bel != BelId());
+            Loc root_loc = this->getBelLocation(root_bel);
+
+            if (cluster->constr_abs_z) {
+                // Coerce root to absolute z constraint
+                root_loc.z = cluster->constr_z;
+                root_bel = this->getBelByLocation(root_loc);
+                if (root_bel == BelId() || !this->isValidBelForCellType(root_cell->type, root_bel))
+                    return false;
+            }
+            placement.emplace_back(root_cell, root_bel);
+
+            for (auto child : cluster->constr_children) {
+                Loc child_loc = if_using_basecluster<Loc>(child, [&](const BaseClusterInfo *child) {
+                    Loc result;
+                    result.x = root_loc.x + child->constr_x;
+                    result.y = root_loc.y + child->constr_y;
+                    result.z = child->constr_abs_z ? child->constr_z : (root_loc.z + child->constr_z);
+                    return result;
+                });
+                BelId child_bel = this->getBelByLocation(child_loc);
+                if (child_bel == BelId() || !this->isValidBelForCellType(child->type, child_bel))
+                    return false;
+                placement.emplace_back(child, child_bel);
+            }
+            return true;
+        });
+    }
+
     // Flow methods
     virtual void assignArchInfo() override{};
 
diff --git a/common/base_clusterinfo.h b/common/base_clusterinfo.h
new file mode 100644
index 00000000..65e8e6d4
--- /dev/null
+++ b/common/base_clusterinfo.h
@@ -0,0 +1,45 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2021  gatecat <gatecat@ds0.me>
+ *
+ *  Permission to use, copy, modify, and/or distribute this software for any
+ *  purpose with or without fee is hereby granted, provided that the above
+ *  copyright notice and this permission notice appear in all copies.
+ *
+ *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#ifndef BASE_CLUSTERINFO_H
+#define BASE_CLUSTERINFO_H
+
+#include "idstring.h"
+#include "nextpnr_namespaces.h"
+
+#include <vector>
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct CellInfo;
+
+// The 'legacy' cluster data, used for existing arches and to provide a basic implementation for arches without complex
+// clustering requirements
+struct BaseClusterInfo
+{
+    std::vector<CellInfo *> constr_children;
+    int constr_x = 0;          // this.x - parent.x
+    int constr_y = 0;          // this.y - parent.y
+    int constr_z = 0;          // this.z - parent.z
+    bool constr_abs_z = false; // parent.z := 0
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* BASE_ARCH_H */
diff --git a/common/basectx.cc b/common/basectx.cc
index da33eecc..34fb414c 100644
--- a/common/basectx.cc
+++ b/common/basectx.cc
@@ -152,25 +152,6 @@ void BaseCtx::archInfoToAttributes()
             ci->attrs[id("NEXTPNR_BEL")] = getCtx()->getBelName(ci->bel).str(getCtx());
             ci->attrs[id("BEL_STRENGTH")] = (int)ci->belStrength;
         }
-        if (ci->constr_x != ci->UNCONSTR)
-            ci->attrs[id("CONSTR_X")] = ci->constr_x;
-        if (ci->constr_y != ci->UNCONSTR)
-            ci->attrs[id("CONSTR_Y")] = ci->constr_y;
-        if (ci->constr_z != ci->UNCONSTR) {
-            ci->attrs[id("CONSTR_Z")] = ci->constr_z;
-            ci->attrs[id("CONSTR_ABS_Z")] = ci->constr_abs_z ? 1 : 0;
-        }
-        if (ci->constr_parent != nullptr)
-            ci->attrs[id("CONSTR_PARENT")] = ci->constr_parent->name.str(this);
-        if (!ci->constr_children.empty()) {
-            std::string constr = "";
-            for (auto &item : ci->constr_children) {
-                if (!constr.empty())
-                    constr += std::string(";");
-                constr += item->name.c_str(this);
-            }
-            ci->attrs[id("CONSTR_CHILDREN")] = constr;
-        }
     }
     for (auto &net : getCtx()->nets) {
         auto ni = net.second.get();
@@ -204,48 +185,6 @@ void BaseCtx::attributesToArchInfo()
             BelId b = getCtx()->getBelByNameStr(val->second.as_string());
             getCtx()->bindBel(b, ci, strength);
         }
-
-        val = ci->attrs.find(id("CONSTR_PARENT"));
-        if (val != ci->attrs.end()) {
-            auto parent = cells.find(id(val->second.str));
-            if (parent != cells.end())
-                ci->constr_parent = parent->second.get();
-            else
-                continue;
-        }
-
-        val = ci->attrs.find(id("CONSTR_X"));
-        if (val != ci->attrs.end())
-            ci->constr_x = val->second.as_int64();
-
-        val = ci->attrs.find(id("CONSTR_Y"));
-        if (val != ci->attrs.end())
-            ci->constr_y = val->second.as_int64();
-
-        val = ci->attrs.find(id("CONSTR_Z"));
-        if (val != ci->attrs.end())
-            ci->constr_z = val->second.as_int64();
-
-        val = ci->attrs.find(id("CONSTR_ABS_Z"));
-        if (val != ci->attrs.end())
-            ci->constr_abs_z = val->second.as_int64() == 1;
-
-        val = ci->attrs.find(id("CONSTR_PARENT"));
-        if (val != ci->attrs.end()) {
-            auto parent = cells.find(id(val->second.as_string()));
-            if (parent != cells.end())
-                ci->constr_parent = parent->second.get();
-        }
-        val = ci->attrs.find(id("CONSTR_CHILDREN"));
-        if (val != ci->attrs.end()) {
-            std::vector<std::string> strs;
-            auto children = val->second.as_string();
-            boost::split(strs, children, boost::is_any_of(";"));
-            for (auto val : strs) {
-                if (cells.count(id(val.c_str())))
-                    ci->constr_children.push_back(cells.find(id(val.c_str()))->second.get());
-            }
-        }
     }
     for (auto &net : getCtx()->nets) {
         auto ni = net.second.get();
diff --git a/common/nextpnr_types.cc b/common/nextpnr_types.cc
index a76576de..f55b89e8 100644
--- a/common/nextpnr_types.cc
+++ b/common/nextpnr_types.cc
@@ -44,26 +44,9 @@ void CellInfo::unsetParam(IdString name) { params.erase(name); }
 void CellInfo::setAttr(IdString name, Property value) { attrs[name] = value; }
 void CellInfo::unsetAttr(IdString name) { attrs.erase(name); }
 
-bool CellInfo::isConstrained(bool include_abs_z_constr) const
-{
-    return constr_parent != nullptr || !constr_children.empty() || (include_abs_z_constr && constr_abs_z);
-}
-
 bool CellInfo::testRegion(BelId bel) const
 {
     return region == nullptr || !region->constr_bels || region->bels.count(bel);
 }
-Loc CellInfo::getConstrainedLoc(Loc parent_loc) const
-{
-    NPNR_ASSERT(constr_parent != nullptr);
-    Loc cloc = parent_loc;
-    if (constr_x != UNCONSTR)
-        cloc.x += constr_x;
-    if (constr_y != UNCONSTR)
-        cloc.y += constr_y;
-    if (constr_z != UNCONSTR)
-        cloc.z = constr_abs_z ? constr_z : (parent_loc.z + constr_z);
-    return cloc;
-}
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/nextpnr_types.h b/common/nextpnr_types.h
index 8b450297..67e60c50 100644
--- a/common/nextpnr_types.h
+++ b/common/nextpnr_types.h
@@ -165,15 +165,8 @@ struct CellInfo : ArchCellInfo
     BelId bel;
     PlaceStrength belStrength = STRENGTH_NONE;
 
-    // placement constraints
-    CellInfo *constr_parent = nullptr;
-    std::vector<CellInfo *> constr_children;
-    const int UNCONSTR = INT_MIN;
-    int constr_x = UNCONSTR;   // this.x - parent.x
-    int constr_y = UNCONSTR;   // this.y - parent.y
-    int constr_z = UNCONSTR;   // this.z - parent.z
-    bool constr_abs_z = false; // parent.z := 0
-    // parent.[xyz] := 0 when (constr_parent == nullptr)
+    // cell is part of a cluster if != ClusterId
+    ClusterId cluster;
 
     Region *region = nullptr;
 
@@ -185,14 +178,8 @@ struct CellInfo : ArchCellInfo
     void unsetParam(IdString name);
     void setAttr(IdString name, Property value);
     void unsetAttr(IdString name);
-
-    // return true if the cell has placement constraints (optionally excluding the case where the only case is an
-    // absolute z constraint)
-    bool isConstrained(bool include_abs_z_constr = true) const;
     // check whether a bel complies with the cell's region constraint
     bool testRegion(BelId bel) const;
-    // get the constrained location for this cell given a provisional location for its parent
-    Loc getConstrainedLoc(Loc parent_loc) const;
 };
 
 enum TimingPortClass
diff --git a/common/place_common.cc b/common/place_common.cc
index 31b93420..7cbeca65 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -179,6 +179,8 @@ class ConstraintLegaliseWorker
     Context *ctx;
     std::set<IdString> rippedCells;
     std::unordered_map<IdString, Loc> oldLocations;
+    std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
+
     class IncreasingDiameterSearch
     {
       public:
@@ -228,83 +230,52 @@ class ConstraintLegaliseWorker
     typedef std::unordered_map<IdString, Loc> CellLocations;
 
     // Check if a location would be suitable for a cell and all its constrained children
-    // This also makes a crude attempt to "solve" unconstrained constraints, that is slow and horrible
-    // and will need to be reworked if mixed constrained/unconstrained chains become common
     bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set<Loc> &usedLocations)
     {
         BelId locBel = ctx->getBelByLocation(loc);
-        if (locBel == BelId()) {
-            return false;
-        }
-        if (!ctx->isValidBelForCellType(cell->type, locBel)) {
+        if (locBel == BelId())
             return false;
-        }
-        if (!ctx->checkBelAvail(locBel)) {
-            CellInfo *confCell = ctx->getConflictingBelCell(locBel);
-            if (confCell->belStrength >= STRENGTH_STRONG) {
-                return false;
-            }
-        }
-        // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later
-        for (auto tilebel : ctx->getBelsByTile(loc.x, loc.y)) {
-            CellInfo *tcell = ctx->getBoundBelCell(tilebel);
-            if (tcell && tcell->belStrength >= STRENGTH_STRONG)
+
+        if (cell->cluster == ClusterId()) {
+            if (!ctx->isValidBelForCellType(cell->type, locBel))
                 return false;
-        }
-        usedLocations.insert(loc);
-        for (auto child : cell->constr_children) {
-            IncreasingDiameterSearch xSearch, ySearch, zSearch;
-            if (child->constr_x == child->UNCONSTR) {
-                xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX() - 1);
-            } else {
-                xSearch = IncreasingDiameterSearch(loc.x + child->constr_x);
-            }
-            if (child->constr_y == child->UNCONSTR) {
-                ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY() - 1);
-            } else {
-                ySearch = IncreasingDiameterSearch(loc.y + child->constr_y);
-            }
-            if (child->constr_z == child->UNCONSTR) {
-                zSearch = IncreasingDiameterSearch(loc.z, 0, ctx->getTileBelDimZ(loc.x, loc.y));
-            } else {
-                if (child->constr_abs_z) {
-                    zSearch = IncreasingDiameterSearch(child->constr_z);
-                } else {
-                    zSearch = IncreasingDiameterSearch(loc.z + child->constr_z);
+            if (!ctx->checkBelAvail(locBel)) {
+                CellInfo *confCell = ctx->getConflictingBelCell(locBel);
+                if (confCell->belStrength >= STRENGTH_STRONG) {
+                    return false;
                 }
             }
-            bool success = false;
-            while (!xSearch.done()) {
-                Loc cloc;
-                cloc.x = xSearch.get();
-                cloc.y = ySearch.get();
-                cloc.z = zSearch.get();
-
-                zSearch.next();
-                if (zSearch.done()) {
-                    zSearch.reset();
-                    ySearch.next();
-                    if (ySearch.done()) {
-                        ySearch.reset();
-                        xSearch.next();
+            // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later
+            for (auto tilebel : ctx->getBelsByTile(loc.x, loc.y)) {
+                CellInfo *tcell = ctx->getBoundBelCell(tilebel);
+                if (tcell && tcell->belStrength >= STRENGTH_STRONG)
+                    return false;
+            }
+            usedLocations.insert(loc);
+            solution[cell->name] = loc;
+        } else {
+            std::vector<std::pair<CellInfo *, BelId>> placement;
+            if (!ctx->getClusterPlacement(cell->cluster, locBel, placement))
+                return false;
+            for (auto &p : placement) {
+                Loc p_loc = ctx->getBelLocation(p.second);
+                if (!ctx->checkBelAvail(p.second)) {
+                    CellInfo *confCell = ctx->getConflictingBelCell(p.second);
+                    if (confCell->belStrength >= STRENGTH_STRONG) {
+                        return false;
                     }
                 }
-
-                if (usedLocations.count(cloc))
-                    continue;
-                if (valid_loc_for(child, cloc, solution, usedLocations)) {
-                    success = true;
-                    break;
+                // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later
+                for (auto tilebel : ctx->getBelsByTile(p_loc.x, p_loc.y)) {
+                    CellInfo *tcell = ctx->getBoundBelCell(tilebel);
+                    if (tcell && tcell->belStrength >= STRENGTH_STRONG)
+                        return false;
                 }
-            }
-            if (!success) {
-                usedLocations.erase(loc);
-                return false;
+                usedLocations.insert(p_loc);
+                solution[p.first->name] = p_loc;
             }
         }
-        if (solution.count(cell->name))
-            usedLocations.erase(solution.at(cell->name));
-        solution[cell->name] = loc;
+
         return true;
     }
 
@@ -312,18 +283,18 @@ class ConstraintLegaliseWorker
     void lockdown_chain(CellInfo *root)
     {
         root->belStrength = STRENGTH_STRONG;
-        for (auto child : root->constr_children)
-            lockdown_chain(child);
+        if (root->cluster != ClusterId())
+            for (auto child : cluster2cells.at(root->cluster))
+                child->belStrength = STRENGTH_STRONG;
     }
 
     // Legalise placement constraints on a cell
     bool legalise_cell(CellInfo *cell)
     {
-        if (cell->constr_parent != nullptr)
+        if (cell->cluster != ClusterId() && ctx->getClusterRootCell(cell->cluster) != cell)
             return true; // Only process chain roots
         if (constraints_satisfied(cell)) {
-            if (cell->constr_children.size() > 0 || cell->constr_x != cell->UNCONSTR ||
-                cell->constr_y != cell->UNCONSTR || cell->constr_z != cell->UNCONSTR)
+            if (cell->cluster != ClusterId())
                 lockdown_chain(cell);
         } else {
             IncreasingDiameterSearch xRootSearch, yRootSearch, zRootSearch;
@@ -332,21 +303,10 @@ class ConstraintLegaliseWorker
                 currentLoc = ctx->getBelLocation(cell->bel);
             else
                 currentLoc = oldLocations[cell->name];
-            if (cell->constr_x == cell->UNCONSTR)
-                xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1);
-            else
-                xRootSearch = IncreasingDiameterSearch(cell->constr_x);
-
-            if (cell->constr_y == cell->UNCONSTR)
-                yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1);
-            else
-                yRootSearch = IncreasingDiameterSearch(cell->constr_y);
+            xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1);
+            yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1);
+            zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y));
 
-            if (cell->constr_z == cell->UNCONSTR)
-                zRootSearch =
-                        IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y));
-            else
-                zRootSearch = IncreasingDiameterSearch(cell->constr_z);
             while (!xRootSearch.done()) {
                 Loc rootLoc;
 
@@ -415,29 +375,13 @@ class ConstraintLegaliseWorker
     bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; }
 
   public:
-    ConstraintLegaliseWorker(Context *ctx) : ctx(ctx){};
-
-    void print_chain(CellInfo *cell, int depth = 0)
+    ConstraintLegaliseWorker(Context *ctx) : ctx(ctx)
     {
-        for (int i = 0; i < depth; i++)
-            log("    ");
-        log("'%s'   (", cell->name.c_str(ctx));
-        if (cell->constr_x != cell->UNCONSTR)
-            log("%d, ", cell->constr_x);
-        else
-            log("*, ");
-        if (cell->constr_y != cell->UNCONSTR)
-            log("%d, ", cell->constr_y);
-        else
-            log("*, ");
-        if (cell->constr_z != cell->UNCONSTR)
-            log("%d", cell->constr_z);
-        else
-            log("*");
-        log(")\n");
-        for (auto child : cell->constr_children)
-            print_chain(child, depth + 1);
-    }
+        for (auto cell : sorted(ctx->cells)) {
+            if (cell.second->cluster != ClusterId())
+                cluster2cells[cell.second->cluster].push_back(cell.second);
+        }
+    };
 
     unsigned print_stats(const char *point)
     {
@@ -476,8 +420,6 @@ class ConstraintLegaliseWorker
         for (auto cell : sorted(ctx->cells)) {
             bool res = legalise_cell(cell.second);
             if (!res) {
-                if (ctx->verbose)
-                    print_chain(cell.second);
                 log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx));
                 return -1;
             }
@@ -509,30 +451,36 @@ int get_constraints_distance(const Context *ctx, const CellInfo *cell)
     if (cell->bel == BelId())
         return 100000;
     Loc loc = ctx->getBelLocation(cell->bel);
-    if (cell->constr_parent == nullptr) {
-        if (cell->constr_x != cell->UNCONSTR)
-            dist += std::abs(cell->constr_x - loc.x);
-        if (cell->constr_y != cell->UNCONSTR)
-            dist += std::abs(cell->constr_y - loc.y);
-        if (cell->constr_z != cell->UNCONSTR)
-            dist += std::abs(cell->constr_z - loc.z);
-    } else {
-        if (cell->constr_parent->bel == BelId())
-            return 100000;
-        Loc parent_loc = ctx->getBelLocation(cell->constr_parent->bel);
-        if (cell->constr_x != cell->UNCONSTR)
-            dist += std::abs(cell->constr_x - (loc.x - parent_loc.x));
-        if (cell->constr_y != cell->UNCONSTR)
-            dist += std::abs(cell->constr_y - (loc.y - parent_loc.y));
-        if (cell->constr_z != cell->UNCONSTR) {
-            if (cell->constr_abs_z)
-                dist += std::abs(cell->constr_z - loc.z);
-            else
-                dist += std::abs(cell->constr_z - (loc.z - parent_loc.z));
+
+    if (cell->cluster != ClusterId()) {
+        CellInfo *root = ctx->getClusterRootCell(cell->cluster);
+        if (root == cell) {
+            // parent
+            std::vector<std::pair<CellInfo *, BelId>> placement;
+            if (!ctx->getClusterPlacement(cell->cluster, cell->bel, placement)) {
+                return 100000;
+            } else {
+                for (const auto &p : placement) {
+                    if (p.first->bel == BelId())
+                        return 100000;
+                    Loc c_loc = ctx->getBelLocation(p.first->bel);
+                    Loc p_loc = ctx->getBelLocation(p.second);
+                    dist += std::abs(c_loc.x - p_loc.x);
+                    dist += std::abs(c_loc.y - p_loc.y);
+                    dist += std::abs(c_loc.z - p_loc.z);
+                }
+            }
+        } else {
+            // child
+            if (root->bel == BelId())
+                return 100000;
+            Loc root_loc = ctx->getBelLocation(root->bel);
+            Loc offset = ctx->getClusterOffset(cell);
+            dist += std::abs((root_loc.x + offset.x) - loc.x);
+            dist += std::abs((root_loc.y + offset.y) - loc.y);
         }
     }
-    for (auto child : cell->constr_children)
-        dist += get_constraints_distance(ctx, child);
+
     return dist;
 }
 
diff --git a/common/placer1.cc b/common/placer1.cc
index 1f940dac..a3e7a696 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -225,14 +225,16 @@ class SAPlacer
         } else {
             for (auto &cell : ctx->cells) {
                 CellInfo *ci = cell.second.get();
-                if (ci->belStrength > STRENGTH_STRONG)
+                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
+                } else if (ci->cluster != ClusterId()) {
+                    if (ctx->getClusterRootCell(ci->cluster) == ci)
+                        chain_basis.push_back(ci);
+                    else
+                        continue;
+                } else {
                     autoplaced.push_back(ci);
+                }
             }
             require_legal = false;
             diameter = 3;
@@ -359,8 +361,8 @@ class SAPlacer
                     autoplaced.clear();
                     chain_basis.clear();
                     for (auto cell : sorted(ctx->cells)) {
-                        if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->constr_parent == nullptr &&
-                            !cell.second->constr_children.empty())
+                        if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->cluster != ClusterId() &&
+                            ctx->getClusterRootCell(cell.second->cluster) == cell.second)
                             chain_basis.push_back(cell.second);
                         else if (cell.second->belStrength < STRENGTH_STRONG)
                             autoplaced.push_back(cell.second);
@@ -507,12 +509,12 @@ class SAPlacer
     {
         static const double epsilon = 1e-20;
         moveChange.reset(this);
-        if (!require_legal && cell->isConstrained(false))
+        if (!require_legal && cell->cluster != ClusterId())
             return false;
         BelId oldBel = cell->bel;
         CellInfo *other_cell = ctx->getBoundBelCell(newBel);
         if (!require_legal && other_cell != nullptr &&
-            (other_cell->isConstrained(false) || other_cell->belStrength > STRENGTH_WEAK)) {
+            (other_cell->cluster != ClusterId() || other_cell->belStrength > STRENGTH_WEAK)) {
             return false;
         }
         int old_dist = get_constraints_distance(ctx, cell);
@@ -612,9 +614,9 @@ class SAPlacer
         if (bound != nullptr)
             ctx->unbindBel(newBel);
         ctx->unbindBel(oldBel);
-        ctx->bindBel(newBel, cell, cell->isConstrained(false) ? STRENGTH_STRONG : STRENGTH_WEAK);
+        ctx->bindBel(newBel, cell, (cell->cluster != ClusterId()) ? STRENGTH_STRONG : STRENGTH_WEAK);
         if (bound != nullptr) {
-            ctx->bindBel(oldBel, bound, bound->isConstrained(false) ? STRENGTH_STRONG : STRENGTH_WEAK);
+            ctx->bindBel(oldBel, bound, (bound->cluster != ClusterId()) ? STRENGTH_STRONG : STRENGTH_WEAK);
             if (cfg.netShareWeight > 0)
                 update_nets_by_tile(bound, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel));
         }
@@ -623,16 +625,6 @@ class SAPlacer
         return oldBel;
     }
 
-    // Discover the relative positions of all cells in a chain
-    void discover_chain(Loc baseLoc, CellInfo *cell, std::vector<std::pair<CellInfo *, Loc>> &cell_rel)
-    {
-        Loc cellLoc = ctx->getBelLocation(cell->bel);
-        Loc rel{cellLoc.x - baseLoc.x, cellLoc.y - baseLoc.y, cellLoc.z};
-        cell_rel.emplace_back(std::make_pair(cell, rel));
-        for (auto child : cell->constr_children)
-            discover_chain(baseLoc, child, cell_rel);
-    }
-
     // Attempt to swap a chain with a non-chain
     bool try_swap_chain(CellInfo *cell, BelId newBase)
     {
@@ -647,32 +639,23 @@ class SAPlacer
         if (ctx->debug)
             log_info("finding cells for chain swap %s\n", cell->name.c_str(ctx));
 #endif
-        Loc baseLoc = ctx->getBelLocation(cell->bel);
-        discover_chain(baseLoc, cell, cell_rel);
-        Loc newBaseLoc = ctx->getBelLocation(newBase);
-        NPNR_ASSERT(newBaseLoc.z == baseLoc.z);
-        for (const auto &cr : cell_rel)
-            cells.insert(cr.first->name);
-
-        for (const auto &cr : cell_rel) {
-            Loc targetLoc = {newBaseLoc.x + cr.second.x, newBaseLoc.y + cr.second.y, cr.second.z};
-            BelId targetBel = ctx->getBelByLocation(targetLoc);
-            if (targetBel == BelId())
-                return false;
-            if (!ctx->isValidBelForCellType(cell->type, targetBel))
-                return false;
-            CellInfo *bound = ctx->getBoundBelCell(targetBel);
+        if (!ctx->getClusterPlacement(cell->cluster, newBase, dest_bels))
+            return false;
+
+        for (const auto &db : dest_bels)
+            cells.insert(db.first->name);
+
+        for (const auto &db : dest_bels) {
+            CellInfo *bound = ctx->getBoundBelCell(db.second);
             // We don't consider swapping chains with other chains, at least for the time being - unless it is
             // part of this chain
             if (bound != nullptr && !cells.count(bound->name) &&
-                (bound->belStrength >= STRENGTH_STRONG || bound->isConstrained(false)))
+                (bound->belStrength >= STRENGTH_STRONG || bound->cluster != ClusterId()))
                 return false;
 
             if (bound != nullptr)
-                if (!ctx->isValidBelForCellType(bound->type, cr.first->bel))
+                if (!ctx->isValidBelForCellType(bound->type, db.first->bel))
                     return false;
-
-            dest_bels.emplace_back(std::make_pair(cr.first, targetBel));
         }
 #if 0
         if (ctx->debug)
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index 042f3046..2f7c7ccb 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -145,6 +145,10 @@ class HeAPPlacer
         Eigen::initParallel();
         tmg.setup_only = true;
         tmg.setup();
+
+        for (auto cell : sorted(ctx->cells))
+            if (cell.second->cluster != ClusterId())
+                cluster2cells[cell.second->cluster].push_back(cell.second);
     }
 
     bool place()
@@ -386,14 +390,8 @@ class HeAPPlacer
     // cells of a certain type)
     std::vector<CellInfo *> solve_cells;
 
-    // For cells in a chain, this is the ultimate root cell of the chain (sometimes this is not constr_parent
-    // where chains are within chains
-    std::unordered_map<IdString, CellInfo *> chain_root;
-    std::unordered_map<IdString, int> chain_size;
-
-    // The offset from chain_root to a cell in the chain
-    std::unordered_map<IdString, std::pair<int, int>> cell_offsets;
-
+    std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells;
+    std::unordered_map<ClusterId, int> chain_size;
     // Performance counting
     double solve_time = 0, cl_time = 0, sl_time = 0;
 
@@ -549,7 +547,7 @@ class HeAPPlacer
                 cell_locs[cell.first].y = loc.y;
                 cell_locs[cell.first].locked = true;
                 cell_locs[cell.first].global = ctx->getBelGlobalBuf(ci->bel);
-            } else if (ci->constr_parent == nullptr) {
+            } else if (ci->cluster == ClusterId() || ctx->getClusterRootCell(ci->cluster) == ci) {
                 bool placed = false;
                 int attempt_count = 0;
                 while (!placed) {
@@ -629,40 +627,27 @@ class HeAPPlacer
             solve_cells.push_back(cell);
         }
         // Finally, update the udata of children
-        for (auto chained : chain_root)
-            ctx->cells.at(chained.first)->udata = chained.second->udata;
+        for (auto &cluster : cluster2cells)
+            for (auto child : cluster.second)
+                child->udata = ctx->getClusterRootCell(cluster.first)->udata;
         return row;
     }
 
-    // Update the location of all children of a chain
-    void update_chain(CellInfo *cell, CellInfo *root)
-    {
-        const auto &base = cell_locs[cell->name];
-        for (auto child : cell->constr_children) {
-            // 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::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::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;
-            if (!child->constr_children.empty())
-                update_chain(child, root);
-        }
-    }
-
     // Update all chains
     void update_all_chains()
     {
         for (auto cell : place_cells) {
             chain_size[cell->name] = 1;
-            if (!cell->constr_children.empty())
-                update_chain(cell, cell);
+            if (cell->cluster != ClusterId()) {
+                const auto &base = cell_locs[cell->name];
+                for (auto child : cluster2cells.at(cell->cluster)) {
+                    if (child->type == cell->type && child != cell)
+                        chain_size[cell->name]++;
+                    Loc offset = ctx->getClusterOffset(child);
+                    cell_locs[child->name].x = std::max(0, std::min(max_x, base.x + offset.x));
+                    cell_locs[child->name].y = std::max(0, std::min(max_y, base.y + offset.y));
+                }
+            }
         }
     }
 
@@ -721,10 +706,9 @@ class HeAPPlacer
                 } else {
                     es.add_rhs(row, -v_pos * weight);
                 }
-                if (cell_offsets.count(var.cell->name)) {
-                    es.add_rhs(row, -(yaxis ? cell_offsets.at(var.cell->name).second
-                                            : cell_offsets.at(var.cell->name).first) *
-                                            weight);
+                if (var.cell->cluster != ClusterId()) {
+                    Loc offset = ctx->getClusterOffset(var.cell);
+                    es.add_rhs(row, -(yaxis ? offset.y : offset.x) * weight);
                 }
             };
 
@@ -827,8 +811,9 @@ class HeAPPlacer
         // Unbind all cells placed in this solution
         for (auto cell : sorted(ctx->cells)) {
             CellInfo *ci = cell.second;
-            if (ci->bel != BelId() && (ci->udata != dont_solve ||
-                                       (chain_root.count(ci->name) && chain_root.at(ci->name)->udata != dont_solve)))
+            if (ci->bel != BelId() &&
+                (ci->udata != dont_solve ||
+                 (ci->cluster != ClusterId() && ctx->getClusterRootCell(ci->cluster)->udata != dont_solve)))
                 ctx->unbindBel(ci->bel);
         }
 
@@ -955,7 +940,7 @@ class HeAPPlacer
                     break;
                 }
 
-                if (ci->constr_children.empty() && !ci->constr_abs_z) {
+                if (ci->cluster == ClusterId()) {
                     // The case where we have no relative constraints
                     for (auto sz : fb->at(nx).at(ny)) {
                         // Look through all bels in this tile; checking region constraint if applicable
@@ -967,7 +952,7 @@ class HeAPPlacer
                             CellInfo *bound = ctx->getBoundBelCell(sz);
                             if (bound != nullptr) {
                                 // Only rip up cells without constraints
-                                if (bound->isConstrained())
+                                if (bound->cluster != ClusterId())
                                     continue;
                                 ctx->unbindBel(bound->bel);
                             }
@@ -1019,45 +1004,23 @@ class HeAPPlacer
                 } else {
                     // We do have relative constraints
                     for (auto sz : fb->at(nx).at(ny)) {
-                        Loc loc = ctx->getBelLocation(sz);
-                        // Check that the absolute-z constraint is satisfied if applicable
-                        if (ci->constr_abs_z && loc.z != ci->constr_z)
-                            continue;
                         // List of cells and their destination
                         std::vector<std::pair<CellInfo *, BelId>> targets;
                         // List of bels we placed things at; and the cell that was there before if applicable
                         std::vector<std::pair<BelId, CellInfo *>> swaps_made;
-                        // List of (cell, new location) pairs to check
-                        std::queue<std::pair<CellInfo *, Loc>> visit;
-                        // FIXME: this approach of having a visit queue is designed to deal with recursively chained
-                        // cells. But is this a case we really want to care about given the complexity it adds? Start by
-                        // considering the root cell at the root location
-                        visit.emplace(ci, loc);
-                        while (!visit.empty()) {
-                            CellInfo *vc = visit.front().first;
-                            NPNR_ASSERT(vc->bel == BelId());
-                            Loc ploc = visit.front().second;
-                            visit.pop();
-                            // Get the bel we're going to place this cell at
-                            BelId target = ctx->getBelByLocation(ploc);
+
+                        if (!ctx->getClusterPlacement(ci->cluster, sz, targets))
+                            continue;
+
+                        for (auto &target : targets) {
                             // Check it satisfies the region constraint if applicable
-                            if (!vc->testRegion(target))
-                                goto fail;
-                            CellInfo *bound;
-                            // Check that the target bel exists and is of a suitable type
-                            if (target == BelId() || !ctx->isValidBelForCellType(vc->type, target))
+                            if (!target.first->testRegion(target.second))
                                 goto fail;
-                            bound = ctx->getBoundBelCell(target);
+                            CellInfo *bound = ctx->getBoundBelCell(target.second);
                             // Chains cannot overlap; so if we have to ripup a cell make sure it isn't part of a chain
                             if (bound != nullptr)
-                                if (bound->isConstrained() || bound->belStrength > STRENGTH_WEAK)
+                                if (bound->cluster != ClusterId() || bound->belStrength > STRENGTH_WEAK)
                                     goto fail;
-                            targets.emplace_back(vc, target);
-                            for (auto child : vc->constr_children) {
-                                // For all the constrained children; compute the location we need to place them at and
-                                // add them to the queue
-                                visit.emplace(child, child->getConstrainedLoc(ploc));
-                            }
                         }
                         // Actually perform the move; keeping track of the moves we make so we can revert them if needed
                         for (auto &target : targets) {
@@ -1307,10 +1270,8 @@ class HeAPPlacer
                 occupancy.at(cell_loc.second.x).at(cell_loc.second.y).at(cell_index(cell))++;
 
                 // Compute ultimate extent of each chain root
-                if (p->chain_root.count(cell_name)) {
-                    set_chain_ext(p->chain_root.at(cell_name)->name, loc.x, loc.y);
-                } else if (!ctx->cells.at(cell_name)->constr_children.empty()) {
-                    set_chain_ext(cell_name, loc.x, loc.y);
+                if (cell.cluster != ClusterId()) {
+                    set_chain_ext(ctx->getClusterRootCell(cell.cluster)->name, loc.x, loc.y);
                 }
             }
 
@@ -1328,10 +1289,8 @@ class HeAPPlacer
 
                 // Transfer chain extents to the actual chains structure
                 ChainExtent *ce = nullptr;
-                if (p->chain_root.count(cell_name)) {
-                    ce = &(cell_extents.at(p->chain_root.at(cell_name)->name));
-                } else if (!ctx->cells.at(cell_name)->constr_children.empty()) {
-                    ce = &(cell_extents.at(cell_name));
+                if (cell.cluster != ClusterId()) {
+                    ce = &(cell_extents.at(ctx->getClusterRootCell(cell.cluster)->name));
                 }
 
                 if (ce) {
diff --git a/common/timing_opt.cc b/common/timing_opt.cc
index dba96bf1..854cbc5b 100644
--- a/common/timing_opt.cc
+++ b/common/timing_opt.cc
@@ -182,8 +182,7 @@ class TimingOptimiser
                     CellInfo *bound = ctx->getBoundBelCell(bel);
                     if (bound == nullptr) {
                         free_bels_at_loc.push_back(bel);
-                    } else if (bound->belStrength <= STRENGTH_WEAK && bound->constr_parent == nullptr &&
-                               bound->constr_children.empty()) {
+                    } else if (bound->belStrength <= STRENGTH_WEAK && bound->cluster == ClusterId()) {
                         bound_bels_at_loc.push_back(bel);
                     }
                 }
@@ -378,7 +377,7 @@ class TimingOptimiser
         if (front_net != nullptr && front_net->driver.cell != nullptr) {
             auto front_cell = front_net->driver.cell;
             if (front_cell->belStrength <= STRENGTH_WEAK && cfg.cellTypes.count(front_cell->type) &&
-                front_cell->constr_parent == nullptr && front_cell->constr_children.empty()) {
+                front_cell->cluster == ClusterId()) {
                 path_cells.push_back(front_cell->name);
             }
         }
@@ -392,7 +391,7 @@ class TimingOptimiser
             if (std::find(path_cells.begin(), path_cells.end(), port->cell->name) != path_cells.end())
                 continue;
             if (port->cell->belStrength > STRENGTH_WEAK || !cfg.cellTypes.count(port->cell->type) ||
-                port->cell->constr_parent != nullptr || !port->cell->constr_children.empty())
+                port->cell->cluster != ClusterId())
                 continue;
             if (ctx->debug)
                 log_info("        can move\n");