Split up common into kernel,place,route

Signed-off-by: gatecat <gatecat@ds0.me>

1 files changed, 188 insertions, 0 deletions

diff --git a/common/place/fast_bels.h b/common/place/fast_bels.h
new file mode 100644
index 00000000..ba9938c6
--- /dev/null
+++ b/common/place/fast_bels.h
@@ -0,0 +1,188 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Claire Xenia Wolf <claire@yosyshq.com>
+ *  Copyright (C) 2018  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.
+ *
+ */
+
+#pragma once
+
+#include <cstddef>
+#include "nextpnr.h"
+
+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 TypeData
+    {
+        size_t type_index;
+        int number_of_possible_bels;
+    };
+
+    FastBels(Context *ctx, bool check_bel_available, int minBelsForGridPick)
+            : ctx(ctx), check_bel_available(check_bel_available), 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.type_index = type_idx;
+
+        fast_bels_by_cell_type.resize(type_idx + 1);
+        auto &bel_data = fast_bels_by_cell_type.at(type_idx);
+        NPNR_ASSERT(bel_data.get() == nullptr);
+        bel_data = std::make_unique<FastBelsData>();
+
+        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 (check_bel_available && !ctx->checkBelAvail(bel)) {
+                continue;
+            }
+
+            if (!ctx->isValidBelForCellType(cell_type, 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);
+        }
+    }
+
+    void addBelBucket(BelBucketId partition)
+    {
+        auto iter = partition_types.find(partition);
+        if (iter != partition_types.end()) {
+            // This partition has already been added to the fast BEL lookup.
+            return;
+        }
+
+        size_t type_idx = partition_types.size();
+        auto &type_data = partition_types[partition];
+        type_data.type_index = type_idx;
+
+        fast_bels_by_partition_type.resize(type_idx + 1);
+        auto &bel_data = fast_bels_by_partition_type.at(type_idx);
+        NPNR_ASSERT(bel_data.get() == nullptr);
+        bel_data = std::make_unique<FastBelsData>();
+
+        for (auto bel : ctx->getBels()) {
+            if (ctx->getBelBucketForBel(bel) != partition) {
+                continue;
+            }
+
+            type_data.number_of_possible_bels += 1;
+        }
+
+        for (auto bel : ctx->getBels()) {
+            if (check_bel_available && !ctx->checkBelAvail(bel)) {
+                continue;
+            }
+
+            if (ctx->getBelBucketForBel(bel) != partition) {
+                continue;
+            }
+
+            Loc loc = ctx->getBelLocation(bel);
+            if (minBelsForGridPick >= 0 && 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;
+
+    int 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_by_cell_type.at(cell_type_data.type_index).get();
+        return cell_type_data.number_of_possible_bels;
+    }
+
+    size_t getBelsForBelBucket(BelBucketId partition, FastBelsData **data)
+    {
+        auto iter = partition_types.find(partition);
+        if (iter == partition_types.end()) {
+            addBelBucket(partition);
+            iter = partition_types.find(partition);
+            NPNR_ASSERT(iter != partition_types.end());
+        }
+
+        auto type_data = iter->second;
+
+        *data = fast_bels_by_partition_type.at(type_data.type_index).get();
+        return type_data.number_of_possible_bels;
+    }
+
+    Context *ctx;
+    const bool check_bel_available;
+    const int minBelsForGridPick;
+
+    dict<IdString, TypeData> cell_types;
+    std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_cell_type;
+
+    dict<BelBucketId, TypeData> partition_types;
+    std::vector<std::unique_ptr<FastBelsData>> fast_bels_by_partition_type;
+};
+
+NEXTPNR_NAMESPACE_END