Merge pull request #756 from acomodi/fix-clustering-runtime

interchange: reduce run-time to check dedicated interconnect

4 files changed, 68 insertions, 6 deletions

diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index 896a603a..630c4480 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -855,7 +855,7 @@ struct Arch : ArchAPI<ArchRanges>
         const CellInfo *cell = tile_status.boundcells[bel.index];
 
         if (cell != nullptr) {
-            if (cell->cluster == ClusterId() && !dedicated_interconnect.isBelLocationValid(bel, cell))
+            if (!dedicated_interconnect.isBelLocationValid(bel, cell))
                 return false;
 
             if (io_port_types.count(cell->type)) {
diff --git a/fpga_interchange/arch_pack_clusters.cc b/fpga_interchange/arch_pack_clusters.cc
index 18162aa4..f4e50233 100644
--- a/fpga_interchange/arch_pack_clusters.cc
+++ b/fpga_interchange/arch_pack_clusters.cc
@@ -193,6 +193,8 @@ bool Arch::getClusterPlacement(ClusterId cluster, BelId root_bel,
     const Context *ctx = getCtx();
     const Cluster &packed_cluster = clusters.at(cluster);
 
+    auto &cluster_data = cluster_info(chip_info, packed_cluster.index);
+
     CellInfo *root_cell = getClusterRootCell(cluster);
     if (!ctx->isValidBelForCellType(root_cell->type, root_bel))
         return false;
@@ -205,8 +207,6 @@ bool Arch::getClusterPlacement(ClusterId cluster, BelId root_bel,
             next_bel = root_bel;
         } else {
             // Find next chained cluster node
-            auto &cluster_data = cluster_info(chip_info, packed_cluster.index);
-
             IdString next_bel_pin(cluster_data.chainable_ports[0].bel_source);
             WireId next_bel_pin_wire = ctx->getBelPinWire(next_bel, next_bel_pin);
             next_bel = BelId();
@@ -256,7 +256,8 @@ bool Arch::getClusterPlacement(ClusterId cluster, BelId root_bel,
                 WireId bel_pin_wire = ctx->getBelPinWire(next_bel, bel_pin);
 
                 ExpansionDirection direction = port_type == PORT_IN ? CLUSTER_UPHILL_DIR : CLUSTER_DOWNHILL_DIR;
-                pool<BelId> cluster_bels = find_cluster_bels(ctx, bel_pin_wire, direction);
+                pool<BelId> cluster_bels =
+                        find_cluster_bels(ctx, bel_pin_wire, direction, (bool)cluster_data.out_of_site_clusters);
 
                 if (cluster_bels.size() == 0)
                     continue;
diff --git a/fpga_interchange/chipdb.h b/fpga_interchange/chipdb.h
index fde35e7f..15ef8b07 100644
--- a/fpga_interchange/chipdb.h
+++ b/fpga_interchange/chipdb.h
@@ -34,7 +34,7 @@ NEXTPNR_NAMESPACE_BEGIN
  * kExpectedChipInfoVersion
  */
 
-static constexpr int32_t kExpectedChipInfoVersion = 11;
+static constexpr int32_t kExpectedChipInfoVersion = 12;
 
 // Flattened site indexing.
 //
@@ -421,6 +421,7 @@ NPNR_PACKED_STRUCT(struct ClusterPOD {
     RelSlice<uint32_t> root_cell_types;
     RelSlice<ChainablePortPOD> chainable_ports;
     RelSlice<ClusterCellPortPOD> cluster_cells_map;
+    uint32_t out_of_site_clusters;
 });
 
 NPNR_PACKED_STRUCT(struct ChipInfoPOD {
diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc
index 1254b367..7658d579 100644
--- a/fpga_interchange/dedicated_interconnect.cc
+++ b/fpga_interchange/dedicated_interconnect.cc
@@ -39,6 +39,12 @@ enum WireNodeState
     IN_SOURCE_SITE = 2
 };
 
+enum ExpansionDirection
+{
+    EXPAND_DOWNHILL = 0,
+    EXPAND_UPHILL = 1
+};
+
 struct WireNode
 {
     WireId wire;
@@ -52,6 +58,50 @@ struct WireNode
 // interconnect.
 constexpr int kMaxDepth = 6;
 
+static uint32_t get_num_pips(const Context *ctx, WireId wire, ExpansionDirection direction)
+{
+    uint32_t num_pips = 0;
+
+    if (direction == EXPAND_DOWNHILL) {
+        for (PipId pip : ctx->getPipsDownhill(wire)) {
+            auto &pip_data = pip_info(ctx->chip_info, pip);
+            if (pip_data.pseudo_cell_wires.size() > 0)
+                continue;
+
+            if (ctx->getPipDstWire(pip) == WireId())
+                continue;
+
+            if (ctx->is_pip_synthetic(pip))
+                continue;
+
+            if (ctx->is_site_port(pip))
+                continue;
+
+            num_pips++;
+        }
+    } else {
+        NPNR_ASSERT(direction == EXPAND_UPHILL);
+        for (PipId pip : ctx->getPipsUphill(wire)) {
+            auto &pip_data = pip_info(ctx->chip_info, pip);
+            if (pip_data.pseudo_cell_wires.size() > 0)
+                continue;
+
+            if (ctx->getPipSrcWire(pip) == WireId())
+                continue;
+
+            if (ctx->is_pip_synthetic(pip))
+                continue;
+
+            if (ctx->is_site_port(pip))
+                continue;
+
+            num_pips++;
+        }
+    }
+
+    return num_pips;
+}
+
 void DedicatedInterconnect::init(const Context *ctx)
 {
     this->ctx = ctx;
@@ -99,6 +149,16 @@ bool DedicatedInterconnect::check_routing(BelId src_bel, IdString src_bel_pin, B
         WireNode node_to_expand = nodes_to_expand.back();
         nodes_to_expand.pop_back();
 
+        auto num_pips = get_num_pips(ctx, node_to_expand.wire, EXPAND_DOWNHILL);
+
+        // Usually, dedicated interconnects do not have more than one PIPs in the out-of-site
+        if (node_to_expand.depth > 1 && node_to_expand.state == IN_ROUTING && num_pips > 1) {
+            if (ctx->verbose)
+                log_info("Wire %s is on a non-dedicated path (number of pips %d)\n",
+                         ctx->nameOfWire(node_to_expand.wire), num_pips);
+            continue;
+        }
+
         for (PipId pip : ctx->getPipsDownhill(node_to_expand.wire)) {
             if (ctx->is_pip_synthetic(pip)) {
                 continue;
@@ -147,7 +207,7 @@ bool DedicatedInterconnect::check_routing(BelId src_bel, IdString src_bel_pin, B
 #ifdef DEBUG_EXPANSION
                         log_info(" - Not dedicated site routing because loop!");
 #endif
-                        return false;
+                        continue;
                     }
                     next_node.state = IN_SINK_SITE;
                     break;