aboutsummaryrefslogtreecommitdiffstats
path: root/fpga_interchange
diff options
context:
space:
mode:
Diffstat (limited to 'fpga_interchange')
-rw-r--r--fpga_interchange/arch.cc30
-rw-r--r--fpga_interchange/arch.h8
-rw-r--r--fpga_interchange/chipdb.h15
-rw-r--r--fpga_interchange/globals.cc284
4 files changed, 336 insertions, 1 deletions
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index c49a172b..938c4f2c 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -479,6 +479,32 @@ IdString Arch::getWireType(WireId wire) const
return IdString(chip_info->wire_types[wire_type].name);
}
+bool Arch::is_site_wire(WireId wire) const
+{
+ if (wire.tile == -1)
+ return false;
+ const auto &tile_type = loc_info(chip_info, wire);
+ return tile_type.wire_data[wire.index].site != -1;
+}
+
+WireCategory Arch::get_wire_category(WireId wire) const
+{
+ int tile = wire.tile, index = wire.index;
+ if (tile == -1) {
+ // Nodal wire
+ const TileWireRefPOD &wr = chip_info->nodes[wire.index].tile_wires[0];
+ tile = wr.tile;
+ index = wr.index;
+ }
+ auto &w2t = chip_info->tiles[tile].tile_wire_to_type;
+ if (index >= w2t.ssize())
+ return WIRE_CAT_GENERAL;
+ int wire_type = w2t[index];
+ if (wire_type == -1)
+ return WIRE_CAT_GENERAL;
+ return WireCategory(chip_info->wire_types[wire_type].category);
+}
+
std::vector<std::pair<IdString, std::string>> Arch::getWireAttrs(WireId wire) const { return {}; }
// -----------------------------------------------------------------------
@@ -773,6 +799,8 @@ bool Arch::place()
getCtx()->check();
#endif
+ place_globals();
+
std::string placer = str_or_default(settings, id("placer"), defaultPlacer);
if (placer == "heap") {
PlacerHeapCfg cfg(getCtx());
@@ -895,6 +923,8 @@ bool Arch::route()
// terminate at a BEL pin.
disallow_site_routing = true;
+ route_globals();
+
bool result;
if (router == "router1") {
result = router1(getCtx(), Router1Cfg(getCtx()));
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index c7d2544f..7188fd36 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -533,6 +533,9 @@ struct Arch : ArchAPI<ArchRanges>
return range;
}
+ bool is_site_wire(WireId wire) const;
+ WireCategory get_wire_category(WireId wire) const;
+
// -------------------------------------------------
PipId getPipByName(IdStringList name) const final;
@@ -686,6 +689,11 @@ struct Arch : ArchAPI<ArchRanges>
std::unordered_set<CellInfo *> *placed_cells);
void pack_ports();
void decode_lut_cells();
+
+ const GlobalCellPOD *global_cell_info(IdString cell_type) const;
+ void place_globals();
+ void route_globals();
+
bool pack() final;
bool place() final;
bool route() final;
diff --git a/fpga_interchange/chipdb.h b/fpga_interchange/chipdb.h
index e9cac84e..d38e5d2f 100644
--- a/fpga_interchange/chipdb.h
+++ b/fpga_interchange/chipdb.h
@@ -34,7 +34,7 @@ NEXTPNR_NAMESPACE_BEGIN
* kExpectedChipInfoVersion
*/
-static constexpr int32_t kExpectedChipInfoVersion = 8;
+static constexpr int32_t kExpectedChipInfoVersion = 9;
// Flattened site indexing.
//
@@ -320,6 +320,18 @@ NPNR_PACKED_STRUCT(struct WireTypePOD {
int32_t category; // WireCategory
});
+NPNR_PACKED_STRUCT(struct GlobalCellPinPOD {
+ int32_t name; // constid
+ int16_t max_hops; // max routing hops to try
+ int8_t guide_placement;
+ int8_t force_routing;
+});
+
+NPNR_PACKED_STRUCT(struct GlobalCellPOD {
+ int32_t cell_type;
+ RelSlice<GlobalCellPinPOD> pins;
+});
+
NPNR_PACKED_STRUCT(struct ChipInfoPOD {
RelPtr<char> name;
RelPtr<char> generator;
@@ -333,6 +345,7 @@ NPNR_PACKED_STRUCT(struct ChipInfoPOD {
RelSlice<NodeInfoPOD> nodes;
RelSlice<PackagePOD> packages;
RelSlice<WireTypePOD> wire_types;
+ RelSlice<GlobalCellPOD> global_cells;
// BEL bucket constids.
RelSlice<int32_t> bel_buckets;
diff --git a/fpga_interchange/globals.cc b/fpga_interchange/globals.cc
new file mode 100644
index 00000000..66d04f75
--- /dev/null
+++ b/fpga_interchange/globals.cc
@@ -0,0 +1,284 @@
+/*
+ * nextpnr -- Next Generation Place and Route
+ *
+ * Copyright (C) 2021 gatecat <gatecat@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 "log.h"
+#include "nextpnr.h"
+#include "util.h"
+
+#include <queue>
+
+NEXTPNR_NAMESPACE_BEGIN
+
+namespace {
+
+struct GlobalVist
+{
+ PipId downhill = PipId();
+ int total_hops = 0;
+ int global_hops = 0;
+ bool operator<(const GlobalVist &other) const
+ {
+ return (total_hops < other.total_hops) ||
+ ((total_hops == other.total_hops) && (global_hops > other.global_hops));
+ }
+};
+
+// This is our main global routing implementation. It is used both to actually route globals; and also to discover if
+// global buffers have available short routes from their source for auto-placement
+static int route_global_arc(Context *ctx, NetInfo *net, size_t usr_idx, size_t phys_port_idx, int max_hops,
+ bool dry_run)
+{
+ auto &usr = net->users.at(usr_idx);
+ WireId src = ctx->getNetinfoSourceWire(net);
+ WireId dest = ctx->getNetinfoSinkWire(net, usr, phys_port_idx);
+ if (dest == WireId()) {
+ if (dry_run)
+ return -1;
+ else
+ log_error("Arc %d.%d (%s.%s) of net %s has no sink wire!\n", int(usr_idx), int(phys_port_idx),
+ ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net));
+ }
+ // Consider any existing routing put in place by the site router, etc
+ int start_hops = 0;
+ while (net->wires.count(dest) && dest != src) {
+ dest = ctx->getPipSrcWire(net->wires.at(dest).pip);
+ ++start_hops;
+ }
+ // The main BFS implementation
+ // Currently this is a backwards-BFS from sink to source (or pre-existing routing) that avoids general routing. It
+ // currently aims for minimum hops as a primary goal and maximum global resource usage as a secondary goal. More
+ // advanced heuristics will likely be needed for more complex situation
+ WireId startpoint;
+ GlobalVist best_visit;
+ std::queue<WireId> visit_queue;
+ std::unordered_map<WireId, GlobalVist> visits;
+
+ visit_queue.push(dest);
+ visits[dest].downhill = PipId();
+ visits[dest].total_hops = start_hops;
+
+ while (!visit_queue.empty()) {
+ WireId cursor = visit_queue.front();
+ visit_queue.pop();
+ auto &curr_visit = visits.at(cursor);
+ // We're now at least one layer deeper than a valid visit, any further exploration is futile
+ if (startpoint != WireId() && curr_visit.total_hops > best_visit.total_hops)
+ break;
+ // Valid end of routing
+ if ((cursor == src) || (ctx->getBoundWireNet(cursor) == net)) {
+ if (startpoint == WireId() || curr_visit < best_visit) {
+ startpoint = cursor;
+ best_visit = curr_visit;
+ }
+ }
+ // Explore uphill
+ for (auto pip : ctx->getPipsUphill(cursor)) {
+ if (!dry_run && !ctx->checkPipAvailForNet(pip, net))
+ continue;
+ WireId pip_src = ctx->getPipSrcWire(pip);
+ if (!dry_run && !ctx->checkWireAvail(pip_src) && ctx->getBoundWireNet(pip_src) != net)
+ continue;
+ auto cat = ctx->get_wire_category(pip_src);
+ if (!ctx->is_site_wire(pip_src) && cat == WIRE_CAT_GENERAL)
+ continue; // never allow general routing
+ GlobalVist next_visit;
+ next_visit.downhill = pip;
+ next_visit.total_hops = curr_visit.total_hops + 1;
+ if (max_hops != -1 && next_visit.total_hops > max_hops)
+ continue;
+ next_visit.global_hops = curr_visit.global_hops + ((cat == WIRE_CAT_GLOBAL) ? 1 : 0);
+ auto fnd_src = visits.find(pip_src);
+ if (fnd_src == visits.end() || next_visit < fnd_src->second) {
+ visit_queue.push(pip_src);
+ visits[pip_src] = next_visit;
+ }
+ }
+ }
+
+ if (startpoint == WireId())
+ return -1;
+ if (!dry_run) {
+ if (ctx->getBoundWireNet(startpoint) == nullptr)
+ ctx->bindWire(startpoint, net, STRENGTH_LOCKED);
+
+ WireId cursor = startpoint;
+ std::vector<PipId> pips;
+ // Create a list of pips on the routed path
+ while (true) {
+ PipId pip = visits.at(cursor).downhill;
+ if (pip == PipId())
+ break;
+ pips.push_back(pip);
+ cursor = ctx->getPipDstWire(pip);
+ }
+ // Reverse that list
+ std::reverse(pips.begin(), pips.end());
+ // Bind pips until we hit already-bound routing
+ for (PipId pip : pips) {
+ WireId dst = ctx->getPipDstWire(pip);
+ if (ctx->getBoundWireNet(dst) == net)
+ break;
+ ctx->bindPip(pip, net, STRENGTH_LOCKED);
+ }
+ }
+ return visits.at(startpoint).total_hops;
+}
+}; // namespace
+
+const GlobalCellPOD *Arch::global_cell_info(IdString cell_type) const
+{
+ for (const auto &glb_cell : chip_info->global_cells)
+ if (IdString(glb_cell.cell_type) == cell_type)
+ return &glb_cell;
+
+ return nullptr;
+}
+
+void Arch::place_globals()
+{
+ log_info("Placing globals...\n");
+
+ Context *ctx = getCtx();
+ IdString gnd_net_name(chip_info->constants->gnd_net_name);
+ IdString vcc_net_name(chip_info->constants->vcc_net_name);
+
+ // TODO: for more complex PLL type setups, we might want a toposort or iterative loop as the PLL must be placed
+ // before the GBs it drives
+ for (auto cell : sorted(ctx->cells)) {
+ CellInfo *ci = cell.second;
+ const GlobalCellPOD *glb_cell = global_cell_info(ci->type);
+ if (glb_cell == nullptr)
+ continue;
+ // Ignore if already placed
+ if (ci->bel != BelId())
+ continue;
+
+ for (const auto &pin : glb_cell->pins) {
+ if (!pin.guide_placement)
+ continue;
+
+ IdString pin_name(pin.name);
+ if (!ci->ports.count(pin_name))
+ continue;
+ auto &port = ci->ports.at(pin_name);
+
+ // only input ports currently used for placement guidance
+ if (port.type != PORT_IN)
+ continue;
+
+ NetInfo *net = port.net;
+ if (net == nullptr || net->name == gnd_net_name || net->name == vcc_net_name)
+ continue;
+ // Ignore if there is no driver; or the driver is not placed
+ if (net->driver.cell == nullptr || net->driver.cell->bel == BelId())
+ continue;
+ size_t user_idx = 0;
+ bool found_user = false;
+ for (user_idx = 0; user_idx < net->users.size(); user_idx++)
+ if (net->users.at(user_idx).cell == ci && net->users.at(user_idx).port == pin_name) {
+ found_user = true;
+ break;
+ }
+ NPNR_ASSERT(found_user);
+
+ // TODO: substantial performance improvements are probably possible, although of questionable benefit given
+ // the low number of globals in a typical device...
+ BelId best_bel;
+ int shortest_distance = std::numeric_limits<int>::max();
+
+ for (auto bel : getBels()) {
+ int distance;
+ if (!isValidBelForCellType(ci->type, bel))
+ continue;
+ if (!checkBelAvail(bel))
+ continue;
+ // Provisionally place
+ bindBel(bel, ci, STRENGTH_WEAK);
+ if (!isBelLocationValid(bel))
+ goto fail;
+ // Check distance
+ distance = route_global_arc(ctx, net, user_idx, 0, pin.max_hops, true);
+ if (distance != -1 && distance < shortest_distance) {
+ best_bel = bel;
+ shortest_distance = distance;
+ }
+ fail:
+ unbindBel(bel);
+ }
+
+ if (best_bel != BelId()) {
+ bindBel(best_bel, ci, STRENGTH_LOCKED);
+ log_info(" placed %s:%s at %s\n", ctx->nameOf(ci), ctx->nameOf(ci->type), ctx->nameOfBel(best_bel));
+ break;
+ }
+ }
+ }
+}
+
+void Arch::route_globals()
+{
+ log_info("Routing globals...\n");
+
+ Context *ctx = getCtx();
+ IdString gnd_net_name(chip_info->constants->gnd_net_name);
+ IdString vcc_net_name(chip_info->constants->vcc_net_name);
+
+ for (auto cell : sorted(ctx->cells)) {
+ CellInfo *ci = cell.second;
+ const GlobalCellPOD *glb_cell = global_cell_info(ci->type);
+ if (glb_cell == nullptr)
+ continue;
+ for (const auto &pin : glb_cell->pins) {
+ IdString pin_name(pin.name);
+ if (!ci->ports.count(pin_name))
+ continue;
+ auto &port = ci->ports.at(pin_name);
+
+ // TOOD: routing of input ports, too
+ // output ports are generally the first priority though
+ if (port.type != PORT_OUT)
+ continue;
+
+ NetInfo *net = port.net;
+ if (net == nullptr || net->name == gnd_net_name || net->name == vcc_net_name)
+ continue;
+
+ int total_sinks = 0;
+ int global_sinks = 0;
+
+ for (size_t i = 0; i < net->users.size(); i++) {
+ auto &usr = net->users.at(i);
+ for (size_t j = 0; j < ctx->getNetinfoSinkWireCount(net, usr); j++) {
+ int result = route_global_arc(ctx, net, i, j, pin.max_hops, false);
+ ++total_sinks;
+ if (result != -1)
+ ++global_sinks;
+ if ((result == -1) && pin.force_routing)
+ log_error("Failed to route arc %d.%d (%s.%s) of net %s using dedicated global routing!\n",
+ int(i), int(j), ctx->nameOf(usr.cell), ctx->nameOf(usr.port), ctx->nameOf(net));
+ }
+ }
+
+ log_info(" routed %d/%d sinks of net %s using dedicated routing.\n", global_sinks, total_sinks,
+ ctx->nameOf(net));
+ }
+ }
+}
+
+NEXTPNR_NAMESPACE_END
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 00:35:21 +0000