nexus: Add post-place LUTFF optimisation

Signed-off-by: David Shah <dave@ds0.me>

4 files changed, 200 insertions, 19 deletions

diff --git a/nexus/arch.cc b/nexus/arch.cc
index d5e901eb..f5edaeb9 100644
--- a/nexus/arch.cc
+++ b/nexus/arch.cc
@@ -120,6 +120,21 @@ Arch::Arch(ArchArgs args) : args(args)
     for (size_t i = 0; i < chip_info->num_tiles; i++) {
         tileStatus[i].boundcells.resize(db->loctypes[chip_info->grid[i].loc_type].num_bels);
     }
+    // This structure is needed for a fast getBelByLocation because bels can have an offset
+    for (size_t i = 0; i < chip_info->num_tiles; i++) {
+        auto &loc = db->loctypes[chip_info->grid[i].loc_type];
+        for (unsigned j = 0; j < loc.num_bels; j++) {
+            auto &bel = loc.bels[j];
+            int rel_bel_tile;
+            if (!rel_tile(i, bel.rel_x, bel.rel_y, rel_bel_tile))
+                continue;
+            auto &ts = tileStatus.at(rel_bel_tile);
+            if (int(ts.bels_by_z.size()) <= bel.z)
+                ts.bels_by_z.resize(bel.z + 1);
+            ts.bels_by_z[bel.z].tile = i;
+            ts.bels_by_z[bel.z].index = j;
+        }
+    }
     init_cell_pin_data();
     // Validate and set up package
     package_idx = -1;
@@ -609,13 +624,13 @@ ArcBounds Arch::getRouteBoundingBox(WireId src, WireId dst) const
         bb.y1 = std::max(bb.y1, y);
     };
 
+    extend(dst_x, dst_y);
+
     if (dsp_wires.count(src) || dsp_wires.count(dst)) {
-        bb.x0 -= 5;
-        bb.x1 += 5;
+        bb.x0 = std::max<int>(0, bb.x0 - 6);
+        bb.x1 = std::min<int>(chip_info->width, bb.x1 + 6);
     }
 
-    extend(dst_x, dst_y);
-
     return bb;
 }
 
@@ -634,7 +649,7 @@ bool Arch::place()
         cfg.cellGroups.back().insert(id_OXIDE_COMB);
         cfg.cellGroups.back().insert(id_OXIDE_FF);
 
-        cfg.beta = 0.6;
+        cfg.beta = 0.5;
         cfg.criticalityExponent = 7;
         if (!placer_heap(getCtx(), cfg))
             return false;
@@ -644,6 +659,9 @@ bool Arch::place()
     } else {
         log_error("Nexus architecture does not support placer '%s'\n", placer.c_str());
     }
+
+    post_place_opt();
+
     getCtx()->attrs[getCtx()->id("step")] = std::string("place");
     archInfoToAttributes();
     return true;
diff --git a/nexus/arch.h b/nexus/arch.h
index 1367161c..1d0d38b5 100644
--- a/nexus/arch.h
+++ b/nexus/arch.h
@@ -932,6 +932,7 @@ struct Arch : BaseCtx
     struct TileStatus
     {
         std::vector<CellInfo *> boundcells;
+        std::vector<BelId> bels_by_z;
         LogicTileStatus *lts = nullptr;
         ~TileStatus() { delete lts; }
     };
@@ -1034,8 +1035,8 @@ struct Arch : BaseCtx
     {
         NPNR_ASSERT(bel != BelId());
         Loc loc;
-        loc.x = bel.tile % chip_info->width;
-        loc.y = bel.tile / chip_info->width;
+        loc.x = bel.tile % chip_info->width + bel_data(bel).rel_x;
+        loc.y = bel.tile / chip_info->width + bel_data(bel).rel_y;
         loc.z = bel_data(bel).z;
         return loc;
     }
@@ -1043,17 +1044,10 @@ struct Arch : BaseCtx
     BelId getBelByLocation(Loc loc) const
     {
         BelId ret;
-        auto &t = db->loctypes[chip_info->grid[loc.y * chip_info->width + loc.x].loc_type];
-        if (loc.x >= 0 && loc.x < chip_info->width && loc.y >= 0 && loc.y < chip_info->height) {
-            for (size_t i = 0; i < t.num_bels; i++) {
-                if (t.bels[i].z == loc.z) {
-                    ret.tile = loc.y * chip_info->width + loc.x;
-                    ret.index = i;
-                    break;
-                }
-            }
-        }
-        return ret;
+        auto &t = tileStatus.at(loc.y * chip_info->width + loc.x);
+        if (loc.z >= int(t.bels_by_z.size()))
+            return BelId();
+        return t.bels_by_z.at(loc.z);
     }
 
     BelRange getBelsByTile(int x, int y) const;
@@ -1400,6 +1394,9 @@ struct Arch : BaseCtx
     bool place();
     bool route();
 
+    // arch-specific post-placement optimisations
+    void post_place_opt();
+
     // -------------------------------------------------
     // Assign architecure-specific arguments to nets and cells, which must be
     // called between packing or further
diff --git a/nexus/main.cc b/nexus/main.cc
index 495793a3..cced1b95 100644
--- a/nexus/main.cc
+++ b/nexus/main.cc
@@ -50,6 +50,8 @@ po::options_description NexusCommandHandler::getArchOptions()
     specific.add_options()("device", po::value<std::string>(), "device name");
     specific.add_options()("fasm", po::value<std::string>(), "fasm file to write");
     specific.add_options()("pdc", po::value<std::string>(), "physical constraints file");
+    specific.add_options()("no-post-place-opt", "disable post-place repacking (debugging use only)");
+
     return specific;
 }
 
@@ -71,7 +73,10 @@ std::unique_ptr<Context> NexusCommandHandler::createContext(std::unordered_map<s
         log_error("device must be specified on the command line (e.g. --device LIFCL-40-9BG400CES)\n");
     }
     chipArgs.device = vm["device"].as<std::string>();
-    return std::unique_ptr<Context>(new Context(chipArgs));
+    auto ctx = std::unique_ptr<Context>(new Context(chipArgs));
+    if (vm.count("no-post-place-opt"))
+        ctx->settings[ctx->id("no_post_place_opt")] = Property::State::S1;
+    return ctx;
 }
 
 void NexusCommandHandler::customAfterLoad(Context *ctx)
diff --git a/nexus/post_place.cc b/nexus/post_place.cc
new file mode 100644
index 00000000..65676188
--- /dev/null
+++ b/nexus/post_place.cc
@@ -0,0 +1,161 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2020  David Shah <dave@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.
+ *
+ */
+
+#include "design_utils.h"
+#include "log.h"
+#include "nextpnr.h"
+#include "timing.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct NexusPostPlaceOpt
+{
+    Context *ctx;
+    NetCriticalityMap net_crit;
+
+    NexusPostPlaceOpt(Context *ctx) : ctx(ctx){};
+
+    inline bool is_constrained(CellInfo *cell)
+    {
+        return cell->constr_parent != nullptr || !cell->constr_children.empty();
+    }
+
+    bool swap_cell_placement(CellInfo *cell, BelId new_bel)
+    {
+        if (is_constrained(cell))
+            return false;
+        BelId oldBel = cell->bel;
+        CellInfo *other_cell = ctx->getBoundBelCell(new_bel);
+        if (other_cell != nullptr && (is_constrained(other_cell) || other_cell->belStrength > STRENGTH_WEAK)) {
+            return false;
+        }
+
+        ctx->unbindBel(oldBel);
+        if (other_cell != nullptr) {
+            ctx->unbindBel(new_bel);
+        }
+
+        ctx->bindBel(new_bel, cell, STRENGTH_WEAK);
+
+        if (other_cell != nullptr) {
+            ctx->bindBel(oldBel, other_cell, STRENGTH_WEAK);
+        }
+
+        if (!ctx->isBelLocationValid(new_bel) || ((other_cell != nullptr && !ctx->isBelLocationValid(oldBel)))) {
+            // New placement is not legal.
+            ctx->unbindBel(new_bel);
+            if (other_cell != nullptr)
+                ctx->unbindBel(oldBel);
+
+            // Revert.
+            ctx->bindBel(oldBel, cell, STRENGTH_WEAK);
+            if (other_cell != nullptr)
+                ctx->bindBel(new_bel, other_cell, STRENGTH_WEAK);
+            return false;
+        }
+
+        return true;
+    }
+
+    int get_distance(BelId a, BelId b)
+    {
+        Loc la = ctx->getBelLocation(a);
+        Loc lb = ctx->getBelLocation(b);
+        return std::abs(la.x - lb.x) + std::abs(la.y - lb.y);
+    }
+
+    BelId lut_to_ff(BelId lut)
+    {
+        Loc ff_loc = ctx->getBelLocation(lut);
+        ff_loc.z += (Arch::BEL_FF0 - Arch::BEL_LUT0);
+        return ctx->getBelByLocation(ff_loc);
+    }
+
+    void opt_lutffs()
+    {
+        int moves_made = 0;
+        for (auto cell : sorted(ctx->cells)) {
+            // Search for FF cells
+            CellInfo *ff = cell.second;
+            if (ff->type != id_OXIDE_FF)
+                continue;
+            // Check M ('fabric') input net
+            NetInfo *m = get_net_or_empty(ff, id_M);
+            if (m == nullptr)
+                continue;
+
+            // Ignore FFs that need both DI and M (PRLD mode)
+            if (get_net_or_empty(ff, id_DI) != nullptr)
+                continue;
+
+            const auto &drv = m->driver;
+            // Skip if driver isn't a LUT/MUX2
+            if (drv.cell == nullptr || drv.cell->type != id_OXIDE_COMB || (drv.port != id_F && drv.port != id_OFX))
+                continue;
+            CellInfo *lut = drv.cell;
+            // Check distance to move isn't too far
+            if (get_distance(ff->bel, lut->bel) > lut_ff_radius)
+                continue;
+            // Find the bel we plan to move into
+            BelId dest_ff = lut_to_ff(lut->bel);
+            NPNR_ASSERT(dest_ff != BelId());
+            NPNR_ASSERT(ctx->getBelType(dest_ff) == id_OXIDE_FF);
+            // Ended up in the ideal location by chance
+            if (dest_ff != ff->bel) {
+                // If dest_ff is already placed *and* using direct 'DI' input, don't touch it
+                CellInfo *dest_ff_cell = ctx->getBoundBelCell(dest_ff);
+                if (dest_ff_cell != nullptr && get_net_or_empty(dest_ff_cell, id_DI) != nullptr)
+                    continue;
+                // Attempt the swap
+                bool swap_result = swap_cell_placement(ff, dest_ff);
+                if (!swap_result)
+                    continue;
+            }
+            // Use direct interconnect
+            rename_port(ctx, ff, id_M, id_DI);
+            ff->params[id_SEL] = std::string("DL");
+            ++moves_made;
+            continue;
+        }
+        log_info("     created %d direct LUT-FF pairs\n", moves_made);
+    }
+
+    void operator()()
+    {
+        get_criticalities(ctx, &net_crit);
+        opt_lutffs();
+    }
+
+    // Configuration
+    const int lut_ff_radius = 2;
+    const int lut_lut_radius = 1;
+    const float lut_lut_crit = 0.85;
+};
+
+void Arch::post_place_opt()
+{
+    if (bool_or_default(settings, id("no_post_place_opt")))
+        return;
+    log_info("Running post-place optimisations...\n");
+    NexusPostPlaceOpt opt(getCtx());
+    opt();
+}
+
+NEXTPNR_NAMESPACE_END