[interchange] Prevent site router from generating incorrect LUTs.

The previous logic tied LUT input pins to VCC if a wire was unplacable.
This missed a case where the net was present to the input of the LUT,
but a wire was still not legal.  This case is now prevented by tying the
output of the LUT to an unused net.

Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>

3 files changed, 102 insertions, 42 deletions

diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index 5903630a..3312f8ce 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -17,11 +17,12 @@
  *
  */
 
-#include "nextpnr.h"
 
-#include "log.h"
 #include "luts.h"
 
+#include "nextpnr.h"
+#include "log.h"
+
 //#define DEBUG_LUT_ROTATION
 
 NEXTPNR_NAMESPACE_BEGIN
@@ -167,16 +168,20 @@ uint32_t LutMapper::check_wires(const Context *ctx) const {
         }
     }
 
-    return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins);
+    HashTables::HashSet<const LutBel *> blocked_luts;
+    return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins,
+            &blocked_luts);
 }
 
 uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_cell_pin_remaps,
-                                const std::vector<const LutBel *> &lut_bels, uint32_t used_pins) const
+                                const std::vector<const LutBel *> &lut_bels, uint32_t used_pins,
+                                HashTables::HashSet<const LutBel *> *blocked_luts) const
 {
     std::vector<const LutBel *> unused_luts;
     for (auto &lut_bel_pair : element.lut_bels) {
         if (std::find(lut_bels.begin(), lut_bels.end(), &lut_bel_pair.second) == lut_bels.end()) {
             unused_luts.push_back(&lut_bel_pair.second);
+            blocked_luts->emplace(&lut_bel_pair.second);
         }
     }
 
@@ -238,6 +243,7 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_
             if (rotate_and_merge_lut_equation(&equation_result, *lut_bel, wire_equation, wire_bel_to_cell_pin_map,
                                               used_pins_with_wire)) {
                 valid_pin_for_wire = true;
+                blocked_luts->erase(lut_bel);
             }
         }
 
@@ -250,7 +256,7 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_
     return vcc_mask;
 }
 
-bool LutMapper::remap_luts(const Context *ctx)
+bool LutMapper::remap_luts(const Context *ctx, HashTables::HashSet<const LutBel *> *blocked_luts)
 {
     std::unordered_map<NetInfo *, LutPin> lut_pin_map;
     std::vector<const LutBel *> lut_bels;
@@ -408,7 +414,7 @@ bool LutMapper::remap_luts(const Context *ctx)
         //
         // Use Arch::prefered_constant_net_type to determine what
         // constant net should be used for unused pins.
-        uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins);
+        uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts);
 #if defined(DEBUG_LUT_ROTATION)
         log_info("vcc_pins = 0x%x", vcc_pins);
         for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
index 6978c7d2..980fe530 100644
--- a/fpga_interchange/luts.h
+++ b/fpga_interchange/luts.h
@@ -27,6 +27,7 @@
 #include "nextpnr_namespaces.h"
 
 #include "dynamic_bitarray.h"
+#include "hash_table.h"
 
 NEXTPNR_NAMESPACE_BEGIN
 
@@ -91,7 +92,7 @@ struct LutMapper
 
     std::vector<CellInfo *> cells;
 
-    bool remap_luts(const Context *ctx);
+    bool remap_luts(const Context *ctx, HashTables::HashSet<const LutBel *> *blocked_luts);
 
     // Determine which wires given the current mapping must be tied to the
     // default constant.
@@ -99,7 +100,8 @@ struct LutMapper
     // Returns a bit mask, 1 meaning it must be tied.   Otherwise means that
     // the pin is free to be a signal.
     uint32_t check_wires(const std::vector<std::vector<int32_t>> &bel_to_cell_pin_remaps,
-                         const std::vector<const LutBel *> &lut_bels, uint32_t used_pins) const;
+                         const std::vector<const LutBel *> &lut_bels, uint32_t used_pins,
+                        HashTables::HashSet<const LutBel *> *blocked_luts) const;
 
     // Version of check_wires that uses current state of cells based on pin
     // mapping in cells variable.
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index 6a066af0..aa82eca9 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -986,6 +986,80 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch)
     }
 }
 
+static bool map_luts_in_site(const SiteInformation &site_info,
+        HashTables::HashSet<std::pair<IdString, IdString>> *blocked_wires) {
+    const Context *ctx = site_info.ctx;
+    const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
+    std::vector<LutMapper> lut_mappers;
+    lut_mappers.reserve(lut_elements.size());
+    for (size_t i = 0; i < lut_elements.size(); ++i) {
+        lut_mappers.push_back(LutMapper(lut_elements[i]));
+    }
+
+    for (CellInfo *cell : site_info.cells_in_site) {
+        if (cell->lut_cell.pins.empty()) {
+            continue;
+        }
+
+        BelId bel = cell->bel;
+        const auto &bel_data = bel_info(ctx->chip_info, bel);
+        if (bel_data.lut_element != -1) {
+            lut_mappers[bel_data.lut_element].cells.push_back(cell);
+        }
+    }
+
+    blocked_wires->clear();
+    for (LutMapper lut_mapper : lut_mappers) {
+        if (lut_mapper.cells.empty()) {
+            continue;
+        }
+
+        HashTables::HashSet<const LutBel *> blocked_luts;
+        if (!lut_mapper.remap_luts(ctx, &blocked_luts)) {
+            return false;
+        }
+
+        for(const LutBel * lut_bel : blocked_luts) {
+            blocked_wires->emplace(std::make_pair(lut_bel->name, lut_bel->output_pin));
+        }
+    }
+
+    return true;
+}
+
+
+// Block outputs of unavailable LUTs to prevent site router from using them.
+static void block_lut_outputs(SiteArch *site_arch,
+        const HashTables::HashSet<std::pair<IdString, IdString>> &blocked_wires) {
+    const Context * ctx = site_arch->site_info->ctx;
+    auto &tile_info = ctx->chip_info->tile_types[site_arch->site_info->tile_type];
+    NetInfo blocking_net;
+    blocking_net.name = ctx->id("$nextpnr_blocked_net");
+
+    SiteNetInfo blocking_site_net;
+    blocking_site_net.net = &blocking_net;
+    for(const auto & bel_pin_pair : blocked_wires) {
+        IdString bel_name = bel_pin_pair.first;
+        IdString bel_pin = bel_pin_pair.second;
+
+        int32_t bel_index = -1;
+        for (int32_t i = 0; i < tile_info.bel_data.ssize(); i++) {
+            if (tile_info.bel_data[i].site == site_arch->site_info->site && tile_info.bel_data[i].name == bel_name.index) {
+                bel_index = i;
+                break;
+            }
+        }
+
+        NPNR_ASSERT(bel_index != -1);
+        BelId bel;
+        bel.tile = site_arch->site_info->tile;
+        bel.index = bel_index;
+
+        SiteWire lut_output_wire = site_arch->getBelPinWire(bel, bel_pin);
+        site_arch->bindWire(lut_output_wire, &blocking_site_net);
+    }
+}
+
 bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const
 {
     // Overview:
@@ -1040,41 +1114,12 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta
         }
     }
 
-    // At this point all cells should be legal via the constraint system.
-    // Check to see if the LUT elements contained within the site are legal.
-    auto tile_type_idx = ctx->chip_info->tiles[tile].type;
-    const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(tile_type_idx);
-    std::vector<LutMapper> lut_mappers;
-    lut_mappers.reserve(lut_elements.size());
-    for (size_t i = 0; i < lut_elements.size(); ++i) {
-        lut_mappers.push_back(LutMapper(lut_elements[i]));
-    }
-
-    for (CellInfo *cell : cells_in_site) {
-        if (cell->lut_cell.pins.empty()) {
-            continue;
-        }
-
-        BelId bel = cell->bel;
-        const auto &bel_data = bel_info(ctx->chip_info, bel);
-        if (bel_data.lut_element != -1) {
-            lut_mappers[bel_data.lut_element].cells.push_back(cell);
-        }
-    }
-
-    for (LutMapper lut_mapper : lut_mappers) {
-        if (lut_mapper.cells.empty()) {
-            continue;
-        }
-
-        if (!lut_mapper.remap_luts(ctx)) {
-            // LUT equation sharing was not possible, fail.
-            site_ok = false;
-            return site_ok;
-        }
-    }
-
     SiteInformation site_info(ctx, tile, site, cells_in_site);
+    HashTables::HashSet<std::pair<IdString, IdString>> blocked_wires;
+    if(!map_luts_in_site(site_info, &blocked_wires)) {
+        site_ok = false;
+        return site_ok;
+    }
 
     // Push from cell pins to the first WireId from each cell pin.
     //
@@ -1093,6 +1138,8 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta
     //
     // site_arch.archcheck();
 
+    block_lut_outputs(&site_arch, blocked_wires);
+
     // Do a detailed routing check to see if the site has at least 1 valid
     // routing solution.
     site_ok = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/false);
@@ -1146,8 +1193,13 @@ void SiteRouter::bindSiteRouting(Context *ctx)
     }
 
     SiteInformation site_info(ctx, tile, site, cells_in_site);
+    HashTables::HashSet<std::pair<IdString, IdString>> blocked_wires;
+    NPNR_ASSERT(map_luts_in_site(site_info, &blocked_wires));
+
     SiteArch site_arch(&site_info);
+    block_lut_outputs(&site_arch, blocked_wires);
     NPNR_ASSERT(route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/false));
+
     check_routing(site_arch);
     apply_routing(ctx, site_arch);
     if (verbose_site_router(ctx)) {