Re-work LUT mapping logic to only put VCC pins when required.

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

5 files changed, 174 insertions, 104 deletions

diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index ceb023d4..e6e784f7 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -794,89 +794,11 @@ static void prepare_sites_for_routing(Context *ctx)
             site_router.bindSiteRouting(ctx);
         }
     }
-}
-
-bool Arch::route()
-{
-    getCtx()->check();
-    prepare_sites_for_routing(getCtx());
-    getCtx()->check();
-#ifdef IDEMPOTENT_CHECK
-    prepare_sites_for_routing(getCtx());
-    getCtx()->check();
-#endif
-
-    std::string router = str_or_default(settings, id("router"), defaultRouter);
-
-    bool result;
-    if (router == "router1") {
-        result = router1(getCtx(), Router1Cfg(getCtx()));
-    } else if (router == "router2") {
-        router2(getCtx(), Router2Cfg(getCtx()));
-        result = true;
-    } else {
-        log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str());
-    }
-
-    if (result) {
-        result = route_vcc_to_unused_lut_pins();
-    }
-
-    getCtx()->attrs[getCtx()->id("step")] = std::string("route");
-    archInfoToAttributes();
-
-    getCtx()->check();
-
-    // Now that routing is complete, unmask BEL pins.
-    unmask_bel_pins();
-
-    getCtx()->check();
-
-    return result;
-}
-
-bool Arch::route_vcc_to_unused_lut_pins()
-{
-    std::string router = str_or_default(settings, id("router"), defaultRouter);
-
-    HashTables::HashMap<WireId, const NetInfo *> bound_wires;
-    for (auto &net_pair : nets) {
-        const NetInfo *net = net_pair.second.get();
-        for (auto &wire_pair : net->wires) {
-            auto result = bound_wires.emplace(wire_pair.first, net);
-            NPNR_ASSERT(result.first->second == net);
-
-            PipId pip = wire_pair.second.pip;
-            if (pip == PipId()) {
-                continue;
-            }
-
-            const PipInfoPOD &pip_data = pip_info(chip_info, pip);
-#ifdef DEBUG_LUT_MAPPING
-            if (getCtx()->verbose) {
-                log_info("Pip %s in use, has %zu pseudo wires!\n", nameOfPip(pip), pip_data.pseudo_cell_wires.size());
-            }
-#endif
-
-            WireId wire;
-            wire.tile = pip.tile;
-            for (int32_t wire_index : pip_data.pseudo_cell_wires) {
-                wire.index = wire_index;
-#ifdef DEBUG_LUT_MAPPING
-                if (getCtx()->verbose) {
-                    log_info("Marking wire %s as in use due to pseudo pip\n", nameOfWire(wire));
-                }
-#endif
-                auto result = bound_wires.emplace(wire, net);
-                NPNR_ASSERT(result.first->second == net);
-            }
-        }
-    }
 
     // Fixup LUT vcc pins.
-    IdString vcc_net_name(chip_info->constants->vcc_net_name);
-    for (BelId bel : getBels()) {
-        CellInfo *cell = getBoundBelCell(bel);
+    IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name);
+    for (BelId bel : ctx->getBels()) {
+        CellInfo *cell = ctx->getBoundBelCell(bel);
         if (cell == nullptr) {
             continue;
         }
@@ -891,45 +813,60 @@ bool Arch::route_vcc_to_unused_lut_pins()
             port_info.type = PORT_IN;
             port_info.net = nullptr;
 
-            WireId lut_pin_wire = getBelPinWire(bel, bel_pin);
-            auto iter = bound_wires.find(lut_pin_wire);
-            if (iter != bound_wires.end()) {
-#ifdef DEBUG_LUT_MAPPING
-                if (getCtx()->verbose) {
-                    log_info("%s is now used as a LUT route-through, not tying to VCC\n", nameOfWire(lut_pin_wire));
-                }
-#endif
-                continue;
-            }
-
 #ifdef DEBUG_LUT_MAPPING
-            if (getCtx()->verbose) {
-                log_info("%s is an unused LUT pin, tying to VCC\n", nameOfWire(lut_pin_wire));
+            if (ctx->verbose) {
+                log_info("%s must be tied to VCC, tying now\n", ctx->nameOfWire(lut_pin_wire));
             }
 #endif
 
             auto result = cell->ports.emplace(bel_pin, port_info);
             if (result.second) {
                 cell->cell_bel_pins[bel_pin].push_back(bel_pin);
-                connectPort(vcc_net_name, cell->name, bel_pin);
+                ctx->connectPort(vcc_net_name, cell->name, bel_pin);
                 cell->const_ports.emplace(bel_pin);
             } else {
-                NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name));
+                NPNR_ASSERT(result.first->second.net == ctx->getNetByAlias(vcc_net_name));
                 auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector<IdString>({bel_pin}));
                 NPNR_ASSERT(result2.first->second.at(0) == bel_pin);
                 NPNR_ASSERT(result2.first->second.size() == 1);
             }
         }
     }
+}
+
+bool Arch::route()
+{
+    getCtx()->check();
+    prepare_sites_for_routing(getCtx());
+    getCtx()->check();
+#ifdef IDEMPOTENT_CHECK
+    prepare_sites_for_routing(getCtx());
+    getCtx()->check();
+#endif
+
+    std::string router = str_or_default(settings, id("router"), defaultRouter);
 
+    bool result;
     if (router == "router1") {
-        return router1(getCtx(), Router1Cfg(getCtx()));
+        result = router1(getCtx(), Router1Cfg(getCtx()));
     } else if (router == "router2") {
         router2(getCtx(), Router2Cfg(getCtx()));
-        return true;
+        result = true;
     } else {
         log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str());
     }
+
+    getCtx()->attrs[getCtx()->id("step")] = std::string("route");
+    archInfoToAttributes();
+
+    getCtx()->check();
+
+    // Now that routing is complete, unmask BEL pins.
+    unmask_bel_pins();
+
+    getCtx()->check();
+
+    return result;
 }
 
 // -----------------------------------------------------------------------
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index 23aed6bc..f6a8f0eb 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -1064,7 +1064,6 @@ struct Arch : ArchAPI<ArchRanges>
     std::regex verilog_bin_constant;
     std::regex verilog_hex_constant;
     void read_lut_equation(DynamicBitarray<> *equation, const Property &equation_parameter) const;
-    bool route_vcc_to_unused_lut_pins();
 
     IdString id_GND;
     IdString id_VCC;
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index bdf728fd..75459393 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -124,6 +124,81 @@ struct LutPin
 
 //#define DEBUG_LUT_ROTATION
 
+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
+{
+    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);
+        }
+    }
+
+    uint32_t vcc_mask = 0;
+
+    DynamicBitarray<> wire_equation;
+    wire_equation.resize(2);
+    wire_equation.set(0, false);
+    wire_equation.set(1, true);
+
+    std::vector<int32_t> wire_bel_to_cell_pin_map;
+    std::vector<LogicLevel> equation_result;
+    for (int32_t pin_idx = 0; pin_idx < (int32_t)element.pins.size(); ++pin_idx) {
+        if (used_pins & (1 << pin_idx)) {
+            // This pin is already used, so it cannot be used for a wire.
+            continue;
+        }
+
+        bool valid_pin_for_wire = false;
+        bool invalid_pin_for_wire = false;
+
+        for (const LutBel *lut_bel : unused_luts) {
+            if (pin_idx < lut_bel->min_pin) {
+                continue;
+            }
+
+            if (pin_idx > lut_bel->max_pin) {
+                continue;
+            }
+
+            wire_bel_to_cell_pin_map.clear();
+            wire_bel_to_cell_pin_map.resize(lut_bel->pins.size(), -1);
+            wire_bel_to_cell_pin_map[lut_bel->pin_to_index.at(element.pins[pin_idx])] = 0;
+
+            equation_result.clear();
+            equation_result.resize(element.width, LL_DontCare);
+
+            uint32_t used_pins_with_wire = used_pins | (1 << pin_idx);
+
+            for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+                const CellInfo *cell = cells[cell_idx];
+                auto &lut_bel_for_cell = *lut_bels[cell_idx];
+                if (!rotate_and_merge_lut_equation(&equation_result, lut_bel_for_cell, cell->lut_cell.equation,
+                                                   bel_to_cell_pin_remaps[cell_idx], used_pins_with_wire)) {
+                    invalid_pin_for_wire = true;
+                    break;
+                }
+            }
+
+            if (invalid_pin_for_wire) {
+                break;
+            }
+
+            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;
+            }
+        }
+
+        bool good_for_wire = valid_pin_for_wire && !invalid_pin_for_wire;
+        if (!good_for_wire) {
+            vcc_mask |= (1 << pin_idx);
+        }
+    }
+
+    return vcc_mask;
+}
+
 bool LutMapper::remap_luts(const Context *ctx)
 {
     std::unordered_map<NetInfo *, LutPin> lut_pin_map;
@@ -259,12 +334,43 @@ bool LutMapper::remap_luts(const Context *ctx)
             bel_pins.clear();
             bel_pins.push_back(lut_bel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]]);
         }
+    }
 
-        cell->lut_cell.vcc_pins.clear();
-        for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
-            if ((used_pins & (1 << bel_pin_idx)) == 0) {
-                NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
-                cell->lut_cell.vcc_pins.emplace(lut_bel.pins.at(bel_pin_idx));
+    if (cells.size() == element.lut_bels.size()) {
+        for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+            CellInfo *cell = cells[cell_idx];
+            auto &lut_bel = *lut_bels[cell_idx];
+            cell->lut_cell.vcc_pins.clear();
+            for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
+                if ((used_pins & (1 << bel_pin_idx)) == 0) {
+                    NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
+                    cell->lut_cell.vcc_pins.emplace(lut_bel.pins.at(bel_pin_idx));
+                }
+            }
+        }
+    } else {
+        // Look to see if wires can be run from element inputs to unused
+        // outputs. If not, block the BEL pin by tying to VCC.
+        uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins);
+#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) {
+            CellInfo *cell = cells[cell_idx];
+            log(", %s => %s", ctx->nameOfBel(cell->bel), cell->name.c_str(ctx));
+        }
+        log("\n");
+#endif
+
+        for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+            CellInfo *cell = cells[cell_idx];
+            auto &lut_bel = *lut_bels[cell_idx];
+            cell->lut_cell.vcc_pins.clear();
+            for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
+                if ((vcc_pins & (1 << bel_pin_idx)) != 0) {
+                    NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
+                    auto pin = lut_bel.pins.at(bel_pin_idx);
+                    cell->lut_cell.vcc_pins.emplace(pin);
+                }
             }
         }
     }
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
index 3500c9d3..dec5a9d6 100644
--- a/fpga_interchange/luts.h
+++ b/fpga_interchange/luts.h
@@ -88,6 +88,8 @@ struct LutMapper
     std::vector<CellInfo *> cells;
 
     bool remap_luts(const Context *ctx);
+    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;
 };
 
 // Rotate and merge a LUT equation into an array of levels.
diff --git a/fpga_interchange/site_arch.cc b/fpga_interchange/site_arch.cc
index 43792eda..711bef44 100644
--- a/fpga_interchange/site_arch.cc
+++ b/fpga_interchange/site_arch.cc
@@ -125,6 +125,7 @@ SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site
 
     // Create list of out of site sources and sinks.
 
+    bool have_vcc_pins = false;
     for (CellInfo *cell : site_info->cells_in_site) {
         for (const auto &pin_pair : cell->cell_bel_pins) {
             const PortInfo &port = cell->ports.at(pin_pair.first);
@@ -132,6 +133,10 @@ SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site
                 nets.emplace(port.net, SiteNetInfo{port.net});
             }
         }
+
+        if (!cell->lut_cell.vcc_pins.empty()) {
+            have_vcc_pins = true;
+        }
     }
 
     for (auto &net_pair : nets) {
@@ -222,6 +227,27 @@ SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site
         }
     }
 
+    IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name);
+    NetInfo *vcc_net = ctx->nets.at(vcc_net_name).get();
+    auto iter = nets.find(vcc_net);
+    if (iter == nets.end() && have_vcc_pins) {
+        // VCC net isn't present, add it.
+        SiteNetInfo net_info;
+        net_info.net = vcc_net;
+        net_info.driver.type = SiteWire::OUT_OF_SITE_SOURCE;
+        net_info.driver.net = vcc_net;
+        auto result = nets.emplace(vcc_net, net_info);
+        NPNR_ASSERT(result.second);
+        iter = result.first;
+    }
+
+    for (CellInfo *cell : site_info->cells_in_site) {
+        for (IdString vcc_pin : cell->lut_cell.vcc_pins) {
+            SiteWire wire = getBelPinWire(cell->bel, vcc_pin);
+            iter->second.users.emplace(wire);
+        }
+    }
+
     for (auto &net_pair : nets) {
         SiteNetInfo *net_info = &net_pair.second;
         auto result = wire_to_nets.emplace(net_info->driver, SiteNetMap{net_info, 1});