Merge pull request #739 from YosysHQ/gatecat/usp-io-macro

interchange: Place entire IO macro based on routeability

5 files changed, 91 insertions, 1 deletions

diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index fc3ea637..6e77054f 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -1152,6 +1152,7 @@ struct Arch : ArchAPI<ArchRanges>
     const DefaultCellConnsPOD *get_default_conns(IdString cell_type) const;
     void pack_default_conns();
 
+    dict<IdString, std::vector<CellInfo *>> macro_to_cells;
     void expand_macros();
 };
 
diff --git a/fpga_interchange/arch_pack_io.cc b/fpga_interchange/arch_pack_io.cc
index fdbb1130..7b8e9f80 100644
--- a/fpga_interchange/arch_pack_io.cc
+++ b/fpga_interchange/arch_pack_io.cc
@@ -22,8 +22,49 @@
 #include "nextpnr.h"
 #include "util.h"
 
+#include <queue>
+
 NEXTPNR_NAMESPACE_BEGIN
 
+namespace {
+bool search_routing_for_placement(Arch *arch, WireId start_wire, CellInfo *cell, IdString cell_pin)
+{
+    std::queue<WireId> visit_queue;
+    pool<WireId> already_visited;
+    visit_queue.push(start_wire);
+    already_visited.insert(start_wire);
+    int iter = 0;
+    while (!visit_queue.empty() && iter++ < 1000) {
+        WireId next = visit_queue.front();
+        visit_queue.pop();
+        for (auto bp : arch->getWireBelPins(next)) {
+            if (!arch->isValidBelForCellType(cell->type, bp.bel))
+                continue;
+            if (!arch->checkBelAvail(bp.bel))
+                continue;
+            // We need to do a test placement to update the bel pin map
+            arch->bindBel(bp.bel, cell, STRENGTH_FIXED);
+            for (IdString bel_pin : arch->getBelPinsForCellPin(cell, cell_pin)) {
+                if (bel_pin == bp.pin)
+                    return true;
+            }
+            // Bel pin doesn't match
+            arch->unbindBel(bp.bel);
+        }
+        for (auto pip : arch->getPipsDownhill(next)) {
+            WireId dst = arch->getPipDstWire(pip);
+            if (already_visited.count(dst))
+                continue;
+            if (!arch->is_site_wire(dst) && arch->get_wire_category(dst) == WIRE_CAT_GENERAL)
+                continue; // this pass only considers dedicated routing
+            visit_queue.push(dst);
+            already_visited.insert(dst);
+        }
+    }
+    return false;
+}
+} // namespace
+
 void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const pool<CellInfo *, hash_ptr_ops> &tightly_attached_bels,
                         pool<CellInfo *, hash_ptr_ops> *placed_cells)
 {
@@ -53,6 +94,44 @@ void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const pool<CellInfo *, ha
             }
         }
     }
+
+    // Also try, on a best-effort basis, to preplace other cells in the macro based on downstream routing. This is
+    // needed for the split INBUF+IBUFCTRL arrangement in the UltraScale+, as just placing the INBUF will result in an
+    // unrouteable site and illegal placement.
+    Context *ctx = getCtx();
+    std::queue<CellInfo *> place_queue;
+    for (auto pc : *placed_cells)
+        place_queue.push(pc);
+    while (!place_queue.empty()) {
+        CellInfo *cursor = place_queue.front();
+        place_queue.pop();
+        // Ignore cells not part of a macro
+        if (cursor->macro_parent == IdString())
+            continue;
+        for (auto &port : cursor->ports) {
+            // Only consider routing downstream from outputs for now
+            if (port.second.type != PORT_OUT || port.second.net == nullptr)
+                continue;
+            NetInfo *ni = port.second.net;
+            WireId src_wire = ctx->getNetinfoSourceWire(ni);
+            for (auto &usr : ni->users) {
+                // Look for unplaced users in the same macro
+                if (usr.cell->bel != BelId() || usr.cell->macro_parent != cursor->macro_parent)
+                    continue;
+                // Try and place using dedicated routing
+                if (search_routing_for_placement(this, src_wire, usr.cell, usr.port)) {
+                    // Successful
+                    placed_cells->insert(usr.cell);
+                    place_queue.push(usr.cell);
+                    if (ctx->verbose)
+                        log_info("Placed %s at %s based on dedicated IO macro routing.\n", ctx->nameOf(usr.cell),
+                                 ctx->nameOfBel(usr.cell->bel));
+                }
+            }
+        }
+    }
+    // TODO: for even more complex cases, if any future devices hit them, we probably should do a full validity check of
+    // all placed cells here, and backtrack and try a different placement if the first one we choose isn't legal overall
 }
 
 void Arch::pack_ports()
diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h
index 057de934..4a196c29 100644
--- a/fpga_interchange/archdefs.h
+++ b/fpga_interchange/archdefs.h
@@ -120,6 +120,7 @@ struct ArchCellInfo
     dict<IdString, std::vector<IdString>> cell_bel_pins;
     dict<IdString, std::vector<IdString>> masked_cell_bel_pins;
     pool<IdString> const_ports;
+    IdString macro_parent = IdString();
     LutCell lut_cell;
 };
 
diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc
index d78743ac..6a2d16bb 100644
--- a/fpga_interchange/dedicated_interconnect.cc
+++ b/fpga_interchange/dedicated_interconnect.cc
@@ -87,7 +87,10 @@ bool DedicatedInterconnect::check_routing(BelId src_bel, IdString src_bel_pin, B
 
     WireNode wire_node;
     wire_node.wire = src_wire;
-    wire_node.state = IN_SOURCE_SITE;
+    if (src_wire.tile == dst_wire.tile && src_wire_data.site == dst_wire_data.site)
+        wire_node.state = IN_SINK_SITE;
+    else
+        wire_node.state = IN_SOURCE_SITE;
     wire_node.depth = 0;
 
     nodes_to_expand.push_back(wire_node);
diff --git a/fpga_interchange/macros.cc b/fpga_interchange/macros.cc
index 8339829f..42c8e1ba 100644
--- a/fpga_interchange/macros.cc
+++ b/fpga_interchange/macros.cc
@@ -66,6 +66,8 @@ void Arch::expand_macros()
             const MacroPOD *macro = lookup_macro(chip_info, exp ? IdString(exp->macro_name) : cell->type);
             if (macro == nullptr)
                 continue;
+            // Get the ultimate root of this macro expansion
+            IdString parent = (cell->macro_parent == IdString()) ? cell->name : cell->macro_parent;
             // Create child instances
             for (const auto &inst : macro->cell_insts) {
                 CellInfo *inst_cell =
@@ -73,6 +75,7 @@ void Arch::expand_macros()
                 for (const auto &param : inst.parameters) {
                     inst_cell->params[IdString(param.key)] = IdString(param.value).str(ctx);
                 }
+                inst_cell->macro_parent = parent;
                 next_cells.push_back(inst_cell);
             }
             // Create and connect nets
@@ -156,6 +159,9 @@ void Arch::expand_macros()
         std::swap(next_cells, cells);
         next_cells.clear();
     } while (!cells.empty());
+    // Do this at the end, otherwise we might add cells that are later destroyed
+    for (auto &cell : ctx->cells)
+        macro_to_cells[cell.second->macro_parent].push_back(cell.second.get());
 }
 
 NEXTPNR_NAMESPACE_END