11 files changed, 194 insertions, 72 deletions

diff --git a/common/fast_bels.h b/common/fast_bels.h
new file mode 100644
index 00000000..1b769baf
--- /dev/null
+++ b/common/fast_bels.h
@@ -0,0 +1,105 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Clifford Wolf <clifford@symbioticeda.com>
+ *  Copyright (C) 2018  David Shah <david@symbioticeda.com>
+ *
+ *  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.
+ *
+ */
+
+#pragma once
+
+#include "nextpnr.h"
+#include <cstddef>
+
+NEXTPNR_NAMESPACE_BEGIN
+
+// FastBels is a lookup class that provides a fast lookup for finding BELs
+// that support a given cell type.
+struct FastBels {
+    struct CellTypeData {
+        size_t cell_type_index;
+        size_t number_of_possible_bels;
+    };
+
+    FastBels(Context *ctx, int minBelsForGridPick) : ctx(ctx), minBelsForGridPick(minBelsForGridPick) {}
+
+    void addCellType(IdString cell_type) {
+        auto iter = cell_types.find(cell_type);
+        if(iter != cell_types.end()) {
+            // This cell type has already been added to the fast BEL lookup.
+            return;
+        }
+
+        size_t type_idx = cell_types.size();
+        auto &cell_type_data = cell_types[cell_type];
+        cell_type_data.cell_type_index = type_idx;
+
+        fast_bels.resize(type_idx + 1);
+        auto &bel_data = fast_bels.at(type_idx);
+
+        for (auto bel : ctx->getBels()) {
+            if(!ctx->isValidBelForCellType(cell_type, bel)) {
+                continue;
+            }
+
+            cell_type_data.number_of_possible_bels += 1;
+        }
+
+        for (auto bel : ctx->getBels()) {
+            if(!ctx->checkBelAvail(bel)) {
+                continue;
+            }
+
+            Loc loc = ctx->getBelLocation(bel);
+            if (minBelsForGridPick >= 0 && cell_type_data.number_of_possible_bels < minBelsForGridPick) {
+                loc.x = loc.y = 0;
+            }
+
+            if (int(bel_data.size()) < (loc.x + 1)) {
+                bel_data.resize(loc.x + 1);
+            }
+
+            if (int(bel_data.at(loc.x).size()) < (loc.y + 1)) {
+                bel_data.at(loc.x).resize(loc.y + 1);
+            }
+
+            bel_data.at(loc.x).at(loc.y).push_back(bel);
+        }
+    }
+
+    typedef std::vector<std::vector<std::vector<BelId>>> FastBelsData;
+
+    size_t getBelsForCellType(IdString cell_type, FastBelsData **data) {
+        auto iter = cell_types.find(cell_type);
+        if(iter == cell_types.end()) {
+            addCellType(cell_type);
+            iter = cell_types.find(cell_type);
+            NPNR_ASSERT(iter != cell_types.end());
+        }
+
+        auto cell_type_data = iter->second;
+
+        *data = &fast_bels.at(cell_type_data.cell_type_index);
+        return cell_type_data.number_of_possible_bels;
+    }
+
+    Context *ctx;
+    int minBelsForGridPick;
+
+    std::unordered_map<IdString, CellTypeData> cell_types;
+    std::vector<FastBelsData> fast_bels;
+};
+
+NEXTPNR_NAMESPACE_END
diff --git a/common/place_common.cc b/common/place_common.cc
index cb9799b5..fb973e2c 100644
--- a/common/place_common.cc
+++ b/common/place_common.cc
@@ -118,7 +118,7 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality)
         }
         IdString targetType = cell->type;
         for (auto bel : ctx->getBels()) {
-            if (ctx->getBelType(bel) == targetType && (!require_legality || ctx->isValidBelForCell(cell, bel))) {
+            if (ctx->isValidBelForCellType(targetType, bel) && (!require_legality || ctx->isValidBelForCell(cell, bel))) {
                 if (ctx->checkBelAvail(bel)) {
                     wirelen_t wirelen = get_cell_metric_at_bel(ctx, cell, bel, MetricType::COST);
                     if (iters >= 4)
@@ -229,7 +229,7 @@ class ConstraintLegaliseWorker
         if (locBel == BelId()) {
             return false;
         }
-        if (ctx->getBelType(locBel) != cell->type) {
+        if (!ctx->isValidBelForCellType(cell->type, locBel)) {
             return false;
         }
         if (!ctx->checkBelAvail(locBel)) {
diff --git a/common/placer1.cc b/common/placer1.cc
index 49f556f7..e2c3dd22 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -43,6 +43,7 @@
 #include "place_common.h"
 #include "timing.h"
 #include "util.h"
+#include "fast_bels.h"
 
 namespace std {
 template <> struct hash<std::pair<NEXTPNR_NAMESPACE_PREFIX IdString, std::size_t>>
@@ -75,33 +76,12 @@ class SAPlacer
     };
 
   public:
-    SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg)
+    SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), fast_bels(ctx, cfg.minBelsForGridPick), cfg(cfg)
     {
-        int num_bel_types = 0;
-        for (auto bel : ctx->getBels()) {
-            IdString type = ctx->getBelType(bel);
-            if (bel_types.find(type) == bel_types.end()) {
-                bel_types[type] = std::tuple<int, int>(num_bel_types++, 1);
-            } else {
-                std::get<1>(bel_types.at(type))++;
-            }
-        }
         for (auto bel : ctx->getBels()) {
             Loc loc = ctx->getBelLocation(bel);
-            IdString type = ctx->getBelType(bel);
-            int type_idx = std::get<0>(bel_types.at(type));
-            int type_cnt = std::get<1>(bel_types.at(type));
-            if (type_cnt < cfg.minBelsForGridPick)
-                loc.x = loc.y = 0;
-            if (int(fast_bels.size()) < type_idx + 1)
-                fast_bels.resize(type_idx + 1);
-            if (int(fast_bels.at(type_idx).size()) < (loc.x + 1))
-                fast_bels.at(type_idx).resize(loc.x + 1);
-            if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1))
-                fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1);
             max_x = std::max(max_x, loc.x);
             max_y = std::max(max_y, loc.y);
-            fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel);
         }
         diameter = std::max(max_x, max_y) + 1;
 
@@ -170,13 +150,14 @@ class SAPlacer
                                   loc_name.c_str(), cell->name.c_str(ctx));
                     }
 
-                    IdString bel_type = ctx->getBelType(bel);
-                    if (bel_type != cell->type) {
+                    if (!ctx->isValidBelForCellType(cell->type, bel)) {
+                        IdString bel_type = ctx->getBelType(bel);
                         log_error("Bel \'%s\' of type \'%s\' does not match cell "
                                   "\'%s\' of type \'%s\'\n",
                                   loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
                     }
                     if (!ctx->isValidBelForCell(cell, bel)) {
+                        IdString bel_type = ctx->getBelType(bel);
                         log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
                                   "\'%s\' of type \'%s\'\n",
                                   loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
@@ -452,7 +433,7 @@ class SAPlacer
             IdString targetType = cell->type;
 
             auto proc_bel = [&](BelId bel) {
-                if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) {
+                if (ctx->isValidBelForCellType(targetType, bel) && ctx->isValidBelForCell(cell, bel)) {
                     if (ctx->checkBelAvail(bel)) {
                         uint64_t score = ctx->rng64();
                         if (score <= best_score) {
@@ -651,7 +632,7 @@ class SAPlacer
             BelId targetBel = ctx->getBelByLocation(targetLoc);
             if (targetBel == BelId())
                 return false;
-            if (ctx->getBelType(targetBel) != cell->type)
+            if (!ctx->isValidBelForCellType(cell->type, targetBel))
                 return false;
             CellInfo *bound = ctx->getBoundBelCell(targetBel);
             // We don't consider swapping chains with other chains, at least for the time being - unless it is
@@ -733,15 +714,15 @@ class SAPlacer
         while (true) {
             int nx = ctx->rng(2 * dx + 1) + std::max(curr_loc.x - dx, 0);
             int ny = ctx->rng(2 * dy + 1) + std::max(curr_loc.y - dy, 0);
-            int beltype_idx, beltype_cnt;
-            std::tie(beltype_idx, beltype_cnt) = bel_types.at(targetType);
-            if (beltype_cnt < cfg.minBelsForGridPick)
+            FastBels::FastBelsData *bel_data;
+            auto type_cnt = fast_bels.getBelsForCellType(targetType, &bel_data);
+            if (cfg.minBelsForGridPick >= 0 && type_cnt < cfg.minBelsForGridPick)
                 nx = ny = 0;
-            if (nx >= int(fast_bels.at(beltype_idx).size()))
+            if (nx >= int(bel_data->size()))
                 continue;
-            if (ny >= int(fast_bels.at(beltype_idx).at(nx).size()))
+            if (ny >= int(bel_data->at(nx).size()))
                 continue;
-            const auto &fb = fast_bels.at(beltype_idx).at(nx).at(ny);
+            const auto &fb = bel_data->at(nx).at(ny);
             if (fb.size() == 0)
                 continue;
             BelId bel = fb.at(ctx->rng(int(fb.size())));
@@ -1217,7 +1198,7 @@ class SAPlacer
     int diameter = 35, max_x = 1, max_y = 1;
     std::unordered_map<IdString, std::tuple<int, int>> bel_types;
     std::unordered_map<IdString, BoundingBox> region_bounds;
-    std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels;
+    FastBels fast_bels;
     std::unordered_set<BelId> locked_bels;
     std::vector<NetInfo *> net_by_udata;
     std::vector<decltype(NetInfo::udata)> old_udata;
diff --git a/common/placer_heap.cc b/common/placer_heap.cc
index f10d4139..4f71577f 100644
--- a/common/placer_heap.cc
+++ b/common/placer_heap.cc
@@ -318,7 +318,7 @@ class HeAPPlacer
     PlacerHeapCfg cfg;
 
     int max_x = 0, max_y = 0;
-    std::vector<std::vector<std::vector<std::vector<BelId>>>> fast_bels;
+    FastBels fast_bels;
     std::unordered_map<IdString, std::tuple<int, int>> bel_types;
 
     // For fast handling of heterogeneity during initial placement without full legalisation,
@@ -384,13 +384,14 @@ class HeAPPlacer
                               loc_name.c_str(), cell->name.c_str(ctx));
                 }
 
-                IdString bel_type = ctx->getBelType(bel);
-                if (bel_type != cell->type) {
+                if (!ctx->isValidBelForCellType(cell->type, bel)) {
+                    IdString bel_type = ctx->getBelType(bel);
                     log_error("Bel \'%s\' of type \'%s\' does not match cell "
                               "\'%s\' of type \'%s\'\n",
                               loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
                 }
                 if (!ctx->isValidBelForCell(cell, bel)) {
+                    IdString bel_type = ctx->getBelType(bel);
                     log_error("Bel \'%s\' of type \'%s\' is not valid for cell "
                               "\'%s\' of type \'%s\'\n",
                               loc_name.c_str(), bel_type.c_str(ctx), cell->name.c_str(ctx), cell->type.c_str(ctx));
@@ -413,31 +414,12 @@ class HeAPPlacer
     // Construct the fast_bels, nearest_row_with_bel and nearest_col_with_bel
     void build_fast_bels()
     {
-
-        int num_bel_types = 0;
-        for (auto bel : ctx->getBels()) {
-            IdString type = ctx->getBelType(bel);
-            if (bel_types.find(type) == bel_types.end()) {
-                bel_types[type] = std::tuple<int, int>(num_bel_types++, 1);
-            } else {
-                std::get<1>(bel_types.at(type))++;
-            }
-        }
         for (auto bel : ctx->getBels()) {
             if (!ctx->checkBelAvail(bel))
                 continue;
             Loc loc = ctx->getBelLocation(bel);
-            IdString type = ctx->getBelType(bel);
-            int type_idx = std::get<0>(bel_types.at(type));
-            if (int(fast_bels.size()) < type_idx + 1)
-                fast_bels.resize(type_idx + 1);
-            if (int(fast_bels.at(type_idx).size()) < (loc.x + 1))
-                fast_bels.at(type_idx).resize(loc.x + 1);
-            if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1))
-                fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1);
             max_x = std::max(max_x, loc.x);
             max_y = std::max(max_y, loc.y);
-            fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel);
         }
 
         nearest_row_with_bel.resize(num_bel_types, std::vector<int>(max_y + 1, -1));
@@ -814,8 +796,8 @@ class HeAPPlacer
             if (ci->bel != BelId())
                 continue;
             // log_info("   Legalising %s (%s)\n", top.second.c_str(ctx), ci->type.c_str(ctx));
-            int bt = std::get<0>(bel_types.at(ci->type));
-            auto &fb = fast_bels.at(bt);
+            FastBels::FastBelsData *fb;
+            fast_bels.getBelsForCellType(ci->type, &fb);
             int radius = 0;
             int iter = 0;
             int iter_at_radius = 0;
@@ -864,13 +846,13 @@ class HeAPPlacer
                     while (radius < std::max(max_x, max_y)) {
                         for (int x = std::max(0, cell_locs.at(ci->name).x - radius);
                              x <= std::min(max_x, cell_locs.at(ci->name).x + radius); x++) {
-                            if (x >= int(fb.size()))
+                            if (x >= int(fb->size()))
                                 break;
                             for (int y = std::max(0, cell_locs.at(ci->name).y - radius);
                                  y <= std::min(max_y, cell_locs.at(ci->name).y + radius); y++) {
-                                if (y >= int(fb.at(x).size()))
+                                if (y >= int(fb->at(x).size()))
                                     break;
-                                if (fb.at(x).at(y).size() > 0)
+                                if (fb->at(x).at(y).size() > 0)
                                     goto notempty;
                             }
                         }
@@ -888,11 +870,11 @@ class HeAPPlacer
                 // ny = nearest_row_with_bel.at(bt).at(ny);
                 // nx = nearest_col_with_bel.at(bt).at(nx);
 
-                if (nx >= int(fb.size()))
+                if (nx >= int(fb->size()))
                     continue;
-                if (ny >= int(fb.at(nx).size()))
+                if (ny >= int(fb->at(nx).size()))
                     continue;
-                if (fb.at(nx).at(ny).empty())
+                if (fb->at(nx).at(ny).empty())
                     continue;
 
                 int need_to_explore = 2 * radius;
@@ -912,7 +894,7 @@ class HeAPPlacer
                 }
 
                 if (ci->constr_children.empty() && !ci->constr_abs_z) {
-                    for (auto sz : fb.at(nx).at(ny)) {
+                    for (auto sz : fb->at(nx).at(ny)) {
                         if (ci->region != nullptr && ci->region->constr_bels && !ci->region->bels.count(sz))
                             continue;
                         if (ctx->checkBelAvail(sz) || (radius > ripup_radius || ctx->rng(20000) < 10)) {
@@ -962,7 +944,7 @@ class HeAPPlacer
                         }
                     }
                 } else {
-                    for (auto sz : fb.at(nx).at(ny)) {
+                    for (auto sz : fb->at(nx).at(ny)) {
                         Loc loc = ctx->getBelLocation(sz);
                         if (ci->constr_abs_z && loc.z != ci->constr_z)
                             continue;
diff --git a/common/timing_opt.cc b/common/timing_opt.cc
index eae15fb2..025084b7 100644
--- a/common/timing_opt.cc
+++ b/common/timing_opt.cc
@@ -215,7 +215,7 @@ class TimingOptimiser
                 std::vector<BelId> free_bels_at_loc;
                 std::vector<BelId> bound_bels_at_loc;
                 for (auto bel : ctx->getBelsByTile(curr_loc.x + dx, curr_loc.y + dy)) {
-                    if (ctx->getBelType(bel) != cell->type)
+                    if (!ctx->isValidBelForCellType(cell->type, bel))
                         continue;
                     CellInfo *bound = ctx->getBoundBelCell(bel);
                     if (bound == nullptr) {
diff --git a/docs/archapi.md b/docs/archapi.md
index a9c38589..481448e3 100644
--- a/docs/archapi.md
+++ b/docs/archapi.md
@@ -377,7 +377,7 @@ the given dst wire.
 This should return a low upper bound for the fastest route from `src` to `dst`.
 
 Or in other words it should assume an otherwise unused chip (thus "fastest route").
-But it only produces an estimate for that fastest route, not an exact 
+But it only produces an estimate for that fastest route, not an exact
 result, and for that estimate it is considered more acceptable to return a
 slightly too high result and it is considered less acceptable to return a
 too low result (thus "low upper bound").
@@ -463,21 +463,57 @@ Cell Delay Methods
 Returns the delay for the specified path through a cell in the `&delay` argument. The method returns
 false if there is no timing relationship from `fromPort` to `toPort`.
 
-### TimingPortClass getPortTimingClass(const CellInfo *cell, IdString port, int &clockInfoCount) const
+### TimingPortClass getPortTimingClass(const CellInfo \*cell, IdString port, int &clockInfoCount) const
 
 Return the _timing port class_ of a port. This can be a register or combinational input or output; clock input or
 output; general startpoint or endpoint; or a port ignored for timing purposes. For register ports, clockInfoCount is set
 to the number of associated _clock edges_ that can be queried by getPortClockingInfo.
 
-### TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const
+### TimingClockingInfo getPortClockingInfo(const CellInfo \*cell, IdString port, int index) const
 
 Return the _clocking info_ (including port name of clock, clock polarity and setup/hold/clock-to-out times) of a
 port. Where ports have more than one clock edge associated with them (such as DDR outputs), `index` can be used to obtain
 information for all edges. `index` must be in [0, clockInfoCount), behaviour is undefined otherwise.
 
+Partition Methods
+-----------------
+
+Partitions are used by analytic placement to seperate types of BELs during
+placement.  Typical partitions are:
+ - All LUT BELs
+ - All FF BELs
+ - All multipliers BELs
+ - All block RAM BELs
+ - etc.
+
+The general rule here is to include all BELs that are roughly interchangable
+during placement.
+
+### const\_range\<PartitionId\> getPartitions() const
+
+Return a list of all partitions on the device.
+
+### IdString partitionName(PartitionId partition) const
+
+Return the name of the partition.
+
+### PartitionId partitionForBel(BelId bel) const
+
+Returns the partition for a particular cell type.
+
+### const\_range\<BelId\> partitionForBel(PartitionId partition) const
+
+Return the list of BELs within a partition.
+
 Placer Methods
 --------------
 
+### bool isValidBelForCellType(IdString cell\_type, BelId bel) const
+
+Returns true if the given cell can be bound to the given BEL.  This check
+should be fast, compared with isValidBelForCell.  This check should always
+return the same value regardless if other cells are placed within the fabric.
+
 ### bool isValidBelForCell(CellInfo \*cell, BelId bel) const
 
 Returns true if the given cell can be bound to the given bel, considering
@@ -489,7 +525,6 @@ a certain number of different clock signals allowed for a group of bels.
 Returns true if a bell in the current configuration is valid, i.e. if
 `isValidBelForCell()` would return true for the current mapping.
 
-
 ### static const std::string defaultPlacer
 
 Name of the default placement algorithm for the architecture, if
diff --git a/ecp5/arch.h b/ecp5/arch.h
index 58373157..5c543cb3 100644
--- a/ecp5/arch.h
+++ b/ecp5/arch.h
@@ -950,6 +950,9 @@ struct Arch : BaseCtx
 
     // -------------------------------------------------
     // Placement validity checks
+    bool isValidBelForCellType(IdString cell_type, BelId bel) const {
+        return cell_type == getBelType(bel);
+    }
     bool isValidBelForCell(CellInfo *cell, BelId bel) const;
     bool isBelLocationValid(BelId bel) const;
 
diff --git a/generic/arch.h b/generic/arch.h
index 011d7d45..abe7ff7d 100644
--- a/generic/arch.h
+++ b/generic/arch.h
@@ -283,6 +283,9 @@ struct Arch : BaseCtx
     // Get the TimingClockingInfo of a port
     TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const;
 
+    bool isValidBelForCellType(IdString cell_type, BelId bel) const {
+        return cell_type == getBelType(bel);
+    }
     bool isValidBelForCell(CellInfo *cell, BelId bel) const;
     bool isBelLocationValid(BelId bel) const;
 
diff --git a/gowin/arch.h b/gowin/arch.h
index 5591744d..100ba5ba 100644
--- a/gowin/arch.h
+++ b/gowin/arch.h
@@ -422,6 +422,9 @@ struct Arch : BaseCtx
     // Get the TimingClockingInfo of a port
     TimingClockingInfo getPortClockingInfo(const CellInfo *cell, IdString port, int index) const;
 
+    bool isValidBelForCellType(IdString cell_type, BelId bel) const {
+        return cell_type == getBelType(bel);
+    }
     bool isValidBelForCell(CellInfo *cell, BelId bel) const;
     bool isBelLocationValid(BelId bel) const;
 
diff --git a/ice40/arch.h b/ice40/arch.h
index fbf26e78..60171a4c 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -821,6 +821,11 @@ struct Arch : BaseCtx
     // Perform placement validity checks, returning false on failure (all
     // implemented in arch_place.cc)
 
+    // Whether this cell type can be placed at this BEL.
+    bool isValidBelForCellType(IdString cell_type, BelId bel) const {
+        return cell_type == getBelType(bel);
+    }
+
     // Whether or not a given cell can be placed at a given Bel
     // This is not intended for Bel type checks, but finer-grained constraints
     // such as conflicting set/reset signals, etc
diff --git a/nexus/arch.h b/nexus/arch.h
index 56b48bf3..31bfa603 100644
--- a/nexus/arch.h
+++ b/nexus/arch.h
@@ -1335,6 +1335,11 @@ struct Arch : BaseCtx
     // Perform placement validity checks, returning false on failure (all
     // implemented in arch_place.cc)
 
+    // Whether this cell type can be placed at this BEL.
+    bool isValidBelForCellType(IdString cell_type, BelId bel) const {
+        return cell_type == getBelType(bel);
+    }
+
     // Whether or not a given cell can be placed at a given Bel
     // This is not intended for Bel type checks, but finer-grained constraints
     // such as conflicting set/reset signals, etc