diff options
Diffstat (limited to 'fpga_interchange')
22 files changed, 1218 insertions, 335 deletions
diff --git a/fpga_interchange/README.md b/fpga_interchange/README.md index 78dd23ce..f5530c0e 100644 --- a/fpga_interchange/README.md +++ b/fpga_interchange/README.md @@ -25,7 +25,7 @@ island based FPGA. It consists of three primary file formats: design, a partially or fully placed design, and a partially or fully routed design. -### Current status +### Current development status This architecture implementation can be compiled in conjunction with a FPGA interchange device database, and the outputs from @@ -36,157 +36,43 @@ library. The current implementation is missing essential features for place and route. As these features are added, this implementation will become more useful. - - [ ] The router lookahead is missing, meaning that router runtime - performance will be terrible. - - [ ] Pseudo pips (e.g. pips that consume BELs and or site resources) should - block their respective resources. This effects designs that have some - routing in place before placement. - - [ ] Pseudo site pips (e.g. site pips that route through BELs) should block - their respective resources. Without this, using some pseudo site pips - could result in invalid placements. - - [ ] Implemented site router lacks important features for tight packing. - Also the current site router is relatively untested, so legal - configurations may be rejected and illegal configurations may be - accepted. - [ ] Logical netlist macro expansion is not implemented, meaning that any macro primitives are unplaceable. Common macro primitives examples are differential IO buffers (IBUFDS) and some LUT RAM (e.g. RAM64X1D). - [ ] Timing information is missing from the FPGA interchange device database, so it is also currently missing from the FPGA interchange architecture. Once timing information is added to the device database - schema, it needs to be added to the architecture. -#### FPGA interchange fabrics - -Currently only Xilinx 7-series, UltraScale and UltraScale+ fabrics have a +#### Weaknesses of current implementation + +Initial development on the following features is started, but needs more +refinement. + + - [ ] BEL validity checking is too expensive. The majority of the runtime + is currently in the LUT rotation. Profiling, optimization and + algorithm review is likely required to bring strict legalisation + runtimes into expected levels. + - [ ] The router lookahead is disabled by default. Without the lookahead, + router runtime is terrible. However the current lookahead + implementation is slow to compute and memory intensive, hence why it is + disabled by default. + - [ ] Pseudo pips (e.g. pips that consume BELs and or site resources) and + pseudo site pips (e.g. site pips that route through BELs) consume site + wires to indicate that they block some resources. This covers many + validity check cases, but misses some. In particular, when a pseudo + pip / pseudo site pip has an implication on the constraint system (e.g. + LUT on a LUT-RAM BEL), an edge may be allowed incorrectly, resulting + in an illegal design. + +### FPGA interchange fabrics + +Xilinx 7-series, UltraScale and UltraScale+ fabrics have a device database generator, via [RapidWright](https://github.com/Xilinx/RapidWright). -##### Artix 35T example - -Install capnproto if not already installed: -``` -# Or equivalent for your local system. -sudo apt-get install capnproto libcapnp-dev -``` - -Install capnproto-java if not already installed: -``` -git clone https://github.com/capnproto/capnproto-java.git -cd capnproto-java -make -sudo make install -``` - -##### Makefile-driven BBA creation - -In `${NEXTPNR_DIR}/fpga_interchange/examples/create_bba` is a Makefile that -should compile nextpnr and create a Xilinx A35 chipdb if java, capnproto and -capnproto-java are installed. - -Instructions: -``` -cd ${NEXTPNR_DIR}/fpga_interchange/examples/create_bba -make -``` - -This will create a virtual env in -`${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/env` that has the -python-fpga-interchange library installed. Before running the design examples, -enter the virtual env, e.g.: - -``` -source ${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/env/bin/activate -``` - -The chipdb will be written to `${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/xc7a35.bin` -once completed. - -##### Manual BBA creation - -This covers the manual set of steps to create a Xilinx A35 chipdb. - -Download RapidWright and generate the device database. -``` -# FIXME: Use main branch once interchange branch is merged. -git clone -b interchange https://github.com/Xilinx/RapidWright.git -cd RapidWright -make update_jars - -# FIXME: Current RapidWright jars generate database with duplicate PIPs -# https://github.com/Xilinx/RapidWright/issues/127 -# Remove this wget once the latest RapidWright JAR is published. -wget https://github.com/Xilinx/RapidWright/releases/download/v2020.2.1-beta/rapidwright-api-lib-2020.2.1_update1.jar -mv rapidwright-api-lib-2020.2.1_update1.jar jars/rapidwright-api-lib-2020.2.0.jar - -./scripts/invoke_rapidwright.sh com.xilinx.rapidwright.interchange.DeviceResourcesExample xc7a35tcpg236-1 -export RAPIDWRIGHT_PATH=$(pwd) -``` - -Set `INTERCHANGE_DIR` to point to 3rdparty/fpga-interchange-schema: -``` -export INTERCHANGE_DIR=$(NEXTPNR_DIR)/3rdparty/fpga-interchange-schema/interchange -``` - -Install python FPGA interchange library. -``` -git clone https://github.com/SymbiFlow/python-fpga-interchange.git -cd python-fpga-interchange -pip install -r requirements.txt -``` - -Patch device database with cell constraints and LUT annotations: -``` -python3 -mfpga_interchange.patch \ - --schema_dir ${INTERCHANGE_DIR} \ - --schema device \ - --patch_path constraints \ - --patch_format yaml \ - ${RAPIDWRIGHT_PATH}/xc7a35tcpg236-1.device \ - test_data/series7_constraints.yaml \ - xc7a35tcpg236-1_constraints.device -python3 -mfpga_interchange.patch \ - --schema_dir ${INTERCHANGE_DIR} \ - --schema device \ - --patch_path lutDefinitions \ - --patch_format yaml \ - xc7a35tcpg236-1_constraints.device \ - test_data/series7_luts.yaml \ - xc7a35tcpg236-1_constraints_luts.device -``` - -Generate nextpnr BBA and constids.inc from device database: -``` -python3 -mfpga_interchange.nextpnr_emit \ - --schema_dir ${INTERCHANGE_DIR} \ - --output_dir ${NEXTPNR_DIR}/fpga_interchange/ \ - --bel_bucket_seeds test_data/series7_bel_buckets.yaml \ - --device xc7a35tcpg236-1_constraints_luts.device \ -``` - -Build nextpnr: - -``` -cd ${NEXTPNR_DIR} -cmake -DARCH=fpga_interchange . -make -j -``` - -Compile generated BBA: -``` -bba/bbasm -l fpga_interchange/chipdb.bba fpga_interchange/chipdb.bin -``` - -Run nextpnr archcheck: -``` -./nextpnr-fpga_interchange --chipdb fpga_interchange/chipdb.bin --test -``` - -Once nextpnr can complete the place and route task and output the physical -netlist, RapidWright can be used to generate a DCP suitable for bitstream -output and DRC checks. - -``` -${RAPIDWRIGHT_PATH}/scripts/invoke_rapidwright.sh \ - com.xilinx.rapidwright.interchange.PhysicalNetlistToDcp \ - <logical netlist file> <physical netlist file> <XDC file> <output DCP> -``` +A Lattice Nexus device database is being worked on, via +[prjoxide](https://github.com/gatecat/prjoxide). + +### FPGA interchange build system + +Construction of chipdb's is currently integrated into nextpnr's CMake build +system. See fpga\_interchange/examples/README.md for more details. diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index a8b62f95..09e539e2 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -49,6 +49,10 @@ //#define USE_LOOKAHEAD //#define DEBUG_CELL_PIN_MAPPING +// Define to enable some idempotent sanity checks for some important +// operations prior to placement and routing. +#define IDEMPOTENT_CHECK + NEXTPNR_NAMESPACE_BEGIN struct SiteBelPair { @@ -144,6 +148,7 @@ Arch::Arch(ArchArgs args) : args(args) io_port_types.emplace(this->id("$nextpnr_ibuf")); io_port_types.emplace(this->id("$nextpnr_obuf")); io_port_types.emplace(this->id("$nextpnr_iobuf")); + io_port_types.emplace(this->id("$nextpnr_inv")); if (!this->args.package.empty()) { IdString package = this->id(this->args.package); @@ -709,18 +714,32 @@ bool Arch::pack() return true; } -bool Arch::place() +static void prepare_for_placement(Context *ctx) { - std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + ctx->remove_site_routing(); // Re-map BEL pins without constant pins - for (BelId bel : getBels()) { - CellInfo *cell = getBoundBelCell(bel); + for (BelId bel : ctx->getBels()) { + CellInfo *cell = ctx->getBoundBelCell(bel); if (cell != nullptr && cell->cell_mapping != -1) { - map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/false); + ctx->map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/false); } } +} +bool Arch::place() +{ + // Before placement, ripup placement specific bindings and unmask all cell + // pins. + getCtx()->check(); + prepare_for_placement(getCtx()); + getCtx()->check(); +#ifdef IDEMPOTENT_CHECK + prepare_for_placement(getCtx()); + getCtx()->check(); +#endif + + std::string placer = str_or_default(settings, id("placer"), defaultPlacer); if (placer == "heap") { PlacerHeapCfg cfg(getCtx()); cfg.criticalityExponent = 7; @@ -743,113 +762,43 @@ bool Arch::place() getCtx()->attrs[getCtx()->id("step")] = std::string("place"); archInfoToAttributes(); + + getCtx()->check(); + return true; } -bool Arch::route() +static void prepare_sites_for_routing(Context *ctx) { - std::string router = str_or_default(settings, id("router"), defaultRouter); + // Reset site routing and remove masked cell pins from previous router run + // (if any). + ctx->remove_site_routing(); // Re-map BEL pins with constant pins - for (BelId bel : getBels()) { - CellInfo *cell = getBoundBelCell(bel); + for (BelId bel : ctx->getBels()) { + CellInfo *cell = ctx->getBoundBelCell(bel); if (cell != nullptr && cell->cell_mapping != -1) { - map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/true); - } - } - - HashTables::HashSet<WireId> wires_to_unbind; - for (auto &net_pair : nets) { - for (auto &wire_pair : net_pair.second->wires) { - WireId wire = wire_pair.first; - if (wire_pair.second.strength != STRENGTH_PLACER) { - // Only looking for bound placer wires - continue; - } - - const TileWireInfoPOD &wire_data = wire_info(wire); - NPNR_ASSERT(wire_data.site != -1); - - wires_to_unbind.emplace(wire); + ctx->map_cell_pins(cell, cell->cell_mapping, /*bind_constants=*/true); } } - for (WireId wire : wires_to_unbind) { - unbindWire(wire); - } - - for (auto &tile_pair : tileStatus) { + // Have site router bind site routing (via bindPip and bindWire). + // This is important so that the pseudo pips are correctly blocked prior + // to handing the design to the generalized router algorithms. + for (auto &tile_pair : ctx->tileStatus) { for (auto &site_router : tile_pair.second.sites) { if (site_router.cells_in_site.empty()) { continue; } - site_router.bindSiteRouting(getCtx()); - } - } - - 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(); - - 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); - } + site_router.bindSiteRouting(ctx); } } // 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; } @@ -864,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; } // ----------------------------------------------------------------------- @@ -1020,6 +984,7 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) cell->cell_mapping = mapping; if (cell->lut_cell.pins.empty()) { cell->cell_bel_pins.clear(); + cell->masked_cell_bel_pins.clear(); } else { std::vector<IdString> cell_pin_to_remove; for (auto port_pair : cell->cell_bel_pins) { @@ -1032,7 +997,9 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) NPNR_ASSERT(cell->cell_bel_pins.erase(cell_pin)); } } + for (IdString const_port : cell->const_ports) { + disconnectPort(cell->name, const_port); NPNR_ASSERT(cell->ports.erase(const_port)); } @@ -1799,6 +1766,131 @@ bool Arch::can_invert(PipId pip) const return bel_data.non_inverting_pin == pip_info.extra_data && bel_data.inverting_pin == pip_info.extra_data; } +void Arch::mask_bel_pins_on_site_wire(NetInfo *net, WireId wire) +{ + std::vector<size_t> bel_pins_to_mask; + for (const PortRef &port_ref : net->users) { + if (port_ref.cell->bel == BelId()) { + continue; + } + + NPNR_ASSERT(port_ref.cell != nullptr); + auto iter = port_ref.cell->cell_bel_pins.find(port_ref.port); + if (iter == port_ref.cell->cell_bel_pins.end()) { + continue; + } + + std::vector<IdString> &cell_bel_pins = iter->second; + bel_pins_to_mask.clear(); + + for (size_t bel_pin_idx = 0; bel_pin_idx < cell_bel_pins.size(); ++bel_pin_idx) { + IdString bel_pin = cell_bel_pins.at(bel_pin_idx); + WireId bel_pin_wire = getBelPinWire(port_ref.cell->bel, bel_pin); + if (bel_pin_wire == wire) { + bel_pins_to_mask.push_back(bel_pin_idx); + } + } + + if (!bel_pins_to_mask.empty()) { + std::vector<IdString> &masked_cell_bel_pins = port_ref.cell->masked_cell_bel_pins[port_ref.port]; + // Remove in reverse order to preserve indicies. + for (auto riter = bel_pins_to_mask.rbegin(); riter != bel_pins_to_mask.rend(); ++riter) { + size_t bel_pin_idx = *riter; + masked_cell_bel_pins.push_back(cell_bel_pins.at(bel_pin_idx)); + cell_bel_pins.erase(cell_bel_pins.begin() + bel_pin_idx); + } + } + } +} + +void Arch::unmask_bel_pins() +{ + for (auto &cell_pair : cells) { + CellInfo *cell = cell_pair.second.get(); + if (cell->masked_cell_bel_pins.empty()) { + continue; + } + + for (auto &mask_pair : cell->masked_cell_bel_pins) { + IdString cell_port = mask_pair.first; + const std::vector<IdString> &bel_pins = mask_pair.second; + std::vector<IdString> &cell_bel_pins = cell->cell_bel_pins[cell_port]; + cell_bel_pins.insert(cell_bel_pins.begin(), bel_pins.begin(), bel_pins.end()); + } + + cell->masked_cell_bel_pins.clear(); + } +} + +void Arch::remove_site_routing() +{ + HashTables::HashSet<WireId> wires_to_unbind; + for (auto &net_pair : nets) { + for (auto &wire_pair : net_pair.second->wires) { + WireId wire = wire_pair.first; + if (wire_pair.second.strength != STRENGTH_PLACER) { + // Only looking for bound placer wires + continue; + } + wires_to_unbind.emplace(wire); + } + } + + for (WireId wire : wires_to_unbind) { + unbindWire(wire); + } + + unmask_bel_pins(); + + IdString id_NEXTPNR_INV = id("$nextpnr_inv"); + IdString id_I = id("I"); + std::vector<IdString> cells_to_remove; + for (auto &cell_pair : cells) { + CellInfo *cell = cell_pair.second.get(); + if (cell->type != id_NEXTPNR_INV) { + continue; + } + + disconnectPort(cell_pair.first, id_I); + cells_to_remove.push_back(cell_pair.first); + tileStatus.at(cell->bel.tile).boundcells[cell->bel.index] = nullptr; + } + + for (IdString cell_name : cells_to_remove) { + NPNR_ASSERT(cells.erase(cell_name) == 1); + } +} + +void Arch::explain_bel_status(BelId bel) const +{ + if (isBelLocationValid(bel)) { + log_info("BEL %s is valid!\n", nameOfBel(bel)); + return; + } + + auto iter = tileStatus.find(bel.tile); + NPNR_ASSERT(iter != tileStatus.end()); + const TileStatus &tile_status = iter->second; + const CellInfo *cell = tile_status.boundcells[bel.index]; + if (!dedicated_interconnect.isBelLocationValid(bel, cell)) { + dedicated_interconnect.explain_bel_status(bel, cell); + return; + } + + if (io_port_types.count(cell->type)) { + return; + } + + if (!is_cell_valid_constraints(cell, tile_status, /*explain_constraints=*/true)) { + return; + } + + auto &bel_data = bel_info(chip_info, bel); + const SiteRouter &site = get_site_status(tile_status, bel_data); + NPNR_ASSERT(!site.checkSiteRouting(getCtx(), tile_status)); + site.explain(getCtx()); +} + // Instance constraint templates. template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index ece8be7f..642060cc 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -217,10 +217,15 @@ struct Arch : ArchAPI<ArchRanges> PhysicalNetlist::PhysNetlist::NetType get_net_type(NetInfo *net) const { - NPNR_ASSERT(net->driver.cell != nullptr); - if (net->driver.cell->bel == get_gnd_bel()) { + NPNR_ASSERT(net != nullptr); + IdString gnd_cell_name(chip_info->constants->gnd_cell_name); + IdString gnd_cell_port(chip_info->constants->gnd_cell_port); + + IdString vcc_cell_name(chip_info->constants->vcc_cell_name); + IdString vcc_cell_port(chip_info->constants->vcc_cell_port); + if (net->driver.cell->type == gnd_cell_name && net->driver.port == gnd_cell_port) { return PhysicalNetlist::PhysNetlist::NetType::GND; - } else if (net->driver.cell->bel == get_vcc_bel()) { + } else if (net->driver.cell->type == vcc_cell_name && net->driver.port == vcc_cell_port) { return PhysicalNetlist::PhysNetlist::NetType::VCC; } else { return PhysicalNetlist::PhysNetlist::NetType::SIGNAL; @@ -1059,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; @@ -1070,6 +1074,21 @@ struct Arch : ArchAPI<ArchRanges> std::string chipdb_hash; std::string get_chipdb_hash() const; + + // Masking moves BEL pins from cell_bel_pins to masked_cell_bel_pins for + // the purposes routing. The idea is that masked BEL pins are already + // handled during site routing, and they shouldn't be visible to the + // router. + void mask_bel_pins_on_site_wire(NetInfo *net, WireId wire); + + // This removes pips and wires bound by the site router, and unmasks all + // BEL pins masked during site routing. + void remove_site_routing(); + + // This unmasks any BEL pins that were masked when site routing was bound. + void unmask_bel_pins(); + + void explain_bel_status(BelId bel) const; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h index 8364520d..23bff4f3 100644 --- a/fpga_interchange/archdefs.h +++ b/fpga_interchange/archdefs.h @@ -109,10 +109,9 @@ struct ArchNetInfo struct ArchCellInfo { - ArchCellInfo() : cell_mapping(-1) {} - - int32_t cell_mapping; + int32_t cell_mapping = -1; HashTables::HashMap<IdString, std::vector<IdString>> cell_bel_pins; + HashTables::HashMap<IdString, std::vector<IdString>> masked_cell_bel_pins; HashTables::HashSet<IdString> const_ports; LutCell lut_cell; }; diff --git a/fpga_interchange/dedicated_interconnect.cc b/fpga_interchange/dedicated_interconnect.cc index 988b13ab..1038ed1f 100644 --- a/fpga_interchange/dedicated_interconnect.cc +++ b/fpga_interchange/dedicated_interconnect.cc @@ -365,6 +365,35 @@ bool DedicatedInterconnect::isBelLocationValid(BelId bel, const CellInfo *cell) return true; } +void DedicatedInterconnect::explain_bel_status(BelId bel, const CellInfo *cell) const +{ + NPNR_ASSERT(bel != BelId()); + + for (const auto &port_pair : cell->ports) { + IdString port_name = port_pair.first; + NetInfo *net = port_pair.second.net; + if (net == nullptr) { + continue; + } + + // This net doesn't have a driver, probably not valid? + NPNR_ASSERT(net->driver.cell != nullptr); + + // Only check sink BELs. + if (net->driver.cell == cell && net->driver.port == port_name) { + if (!is_driver_on_net_valid(bel, cell, port_name, net)) { + log_info("Driver %s/%s is not valid on net '%s'", cell->name.c_str(ctx), port_name.c_str(ctx), + net->name.c_str(ctx)); + } + } else { + if (!is_sink_on_net_valid(bel, cell, port_name, net)) { + log_info("Sink %s/%s is not valid on net '%s'", cell->name.c_str(ctx), port_name.c_str(ctx), + net->name.c_str(ctx)); + } + } + } +} + void DedicatedInterconnect::print_dedicated_interconnect() const { log_info("Found %zu sinks with dedicated interconnect\n", sinks.size()); diff --git a/fpga_interchange/dedicated_interconnect.h b/fpga_interchange/dedicated_interconnect.h index 41adea15..900a82f3 100644 --- a/fpga_interchange/dedicated_interconnect.h +++ b/fpga_interchange/dedicated_interconnect.h @@ -133,6 +133,7 @@ struct DedicatedInterconnect // // Note: Only BEL pin sinks are checked. bool isBelLocationValid(BelId bel, const CellInfo *cell) const; + void explain_bel_status(BelId bel, const CellInfo *cell) const; void find_dedicated_interconnect(); void print_dedicated_interconnect() const; diff --git a/fpga_interchange/examples/README.md b/fpga_interchange/examples/README.md index c7df6d5a..6c1da117 100644 --- a/fpga_interchange/examples/README.md +++ b/fpga_interchange/examples/README.md @@ -29,6 +29,13 @@ Install python-fpga-interchange if not already installed: ``` git clone https://github.com/SymbiFlow/python-fpga-interchange.git cd python-fpga-interchange.git +# +# Note: Recommend checking out a specific release, for example: +# +# git checkout v0.0.5 +# +# Release of python-fpga-interchange library does have to match nextpnr +# implementation. python -m pip install -e . ``` diff --git a/fpga_interchange/examples/chipdb.cmake b/fpga_interchange/examples/chipdb.cmake index 3cca7840..4705c0bc 100644 --- a/fpga_interchange/examples/chipdb.cmake +++ b/fpga_interchange/examples/chipdb.cmake @@ -51,6 +51,17 @@ function(create_rapidwright_device_db) add_custom_target(rapidwright-${device}-device DEPENDS ${rapidwright_device_db}) set_property(TARGET rapidwright-${device}-device PROPERTY LOCATION ${rapidwright_device_db}) + add_custom_target(rapidwright-${device}-device-yaml + COMMAND + ${PYTHON_EXECUTABLE} -mfpga_interchange.convert + --schema_dir ${INTERCHANGE_SCHEMA_PATH} + --schema device + --input_format capnp + --output_format yaml + ${rapidwright_device_db} + ${rapidwright_device_db}.yaml + DEPENDS ${rapidwright_device_db}) + if (DEFINED output_target) set(${output_target} rapidwright-${device}-device PARENT_SCOPE) endif() @@ -129,6 +140,17 @@ function(create_patched_device_db) add_custom_target(${patch_name}-${device}-device DEPENDS ${output_device_file}) set_property(TARGET ${patch_name}-${device}-device PROPERTY LOCATION ${output_device_file}) + add_custom_target(${patch_name}-${device}-device-yaml + COMMAND + ${PYTHON_EXECUTABLE} -mfpga_interchange.convert + --schema_dir ${INTERCHANGE_SCHEMA_PATH} + --schema device + --input_format capnp + --output_format yaml + ${output_device_file} + ${output_device_file}.yaml + DEPENDS ${output_device_file}) + if (DEFINED output_target) set(${output_target} ${patch_name}-${device}-device PARENT_SCOPE) endif() diff --git a/fpga_interchange/examples/tests/CMakeLists.txt b/fpga_interchange/examples/tests/CMakeLists.txt index f0c6c53d..40ec8a75 100644 --- a/fpga_interchange/examples/tests/CMakeLists.txt +++ b/fpga_interchange/examples/tests/CMakeLists.txt @@ -1,6 +1,6 @@ add_subdirectory(wire) add_subdirectory(const_wire) -# FIXME: re-enable counter test as soon as post placement validity check completes successfully. -#add_subdirectory(counter) +add_subdirectory(counter) +add_subdirectory(ram) add_subdirectory(ff) add_subdirectory(lut) diff --git a/fpga_interchange/examples/tests/ram/CMakeLists.txt b/fpga_interchange/examples/tests/ram/CMakeLists.txt new file mode 100644 index 00000000..4625edb3 --- /dev/null +++ b/fpga_interchange/examples/tests/ram/CMakeLists.txt @@ -0,0 +1,10 @@ +add_interchange_test( + name ram_basys3 + family ${family} + device xc7a35t + package cpg236 + tcl run.tcl + xdc basys3.xdc + sources ram.v +) + diff --git a/fpga_interchange/examples/tests/ram/basys3.pcf b/fpga_interchange/examples/tests/ram/basys3.pcf new file mode 100644 index 00000000..cb4191cc --- /dev/null +++ b/fpga_interchange/examples/tests/ram/basys3.pcf @@ -0,0 +1,41 @@ +# basys3 100 MHz CLK +set_io clk W5 + +set_io tx A18 +set_io rx B18 +# +# in[0:15] correspond with SW0-SW15 on the basys3 +set_io sw[0] V17 +set_io sw[1] V16 +set_io sw[2] W16 +set_io sw[3] W17 +set_io sw[4] W15 +set_io sw[5] V15 +set_io sw[6] W14 +set_io sw[7] W13 +set_io sw[8] V2 +set_io sw[9] T3 +set_io sw[10] T2 +set_io sw[11] R3 +set_io sw[12] W2 +set_io sw[13] U1 +set_io sw[14] T1 +set_io sw[15] R2 + +# out[0:15] correspond with LD0-LD15 on the basys3 +set_io led[0] U16 +set_io led[1] E19 +set_io led[2] U19 +set_io led[3] V19 +set_io led[4] W18 +set_io led[5] U15 +set_io led[6] U14 +set_io led[7] V14 +set_io led[8] V13 +set_io led[9] V3 +set_io led[10] W3 +set_io led[11] U3 +set_io led[12] P3 +set_io led[13] N3 +set_io led[14] P1 +set_io led[15] L1 diff --git a/fpga_interchange/examples/tests/ram/basys3.xdc b/fpga_interchange/examples/tests/ram/basys3.xdc new file mode 100644 index 00000000..58e1859c --- /dev/null +++ b/fpga_interchange/examples/tests/ram/basys3.xdc @@ -0,0 +1,80 @@ +# basys3 100 MHz CLK +set_property PACKAGE_PIN W5 [get_ports clk] + +set_property PACKAGE_PIN A18 [get_ports tx] +set_property PACKAGE_PIN B18 [get_ports rx] +# +# in[0:15] correspond with SW0-SW15 on the basys3 +set_property PACKAGE_PIN V17 [get_ports sw[0]] +set_property PACKAGE_PIN V16 [get_ports sw[1]] +set_property PACKAGE_PIN W16 [get_ports sw[2]] +set_property PACKAGE_PIN W17 [get_ports sw[3]] +set_property PACKAGE_PIN W15 [get_ports sw[4]] +set_property PACKAGE_PIN V15 [get_ports sw[5]] +set_property PACKAGE_PIN W14 [get_ports sw[6]] +set_property PACKAGE_PIN W13 [get_ports sw[7]] +set_property PACKAGE_PIN V2 [get_ports sw[8]] +set_property PACKAGE_PIN T3 [get_ports sw[9]] +set_property PACKAGE_PIN T2 [get_ports sw[10]] +set_property PACKAGE_PIN R3 [get_ports sw[11]] +set_property PACKAGE_PIN W2 [get_ports sw[12]] +set_property PACKAGE_PIN U1 [get_ports sw[13]] +set_property PACKAGE_PIN T1 [get_ports sw[14]] +set_property PACKAGE_PIN R2 [get_ports sw[15]] + +# out[0:15] correspond with LD0-LD15 on the basys3 +set_property PACKAGE_PIN U16 [get_ports led[0]] +set_property PACKAGE_PIN E19 [get_ports led[1]] +set_property PACKAGE_PIN U19 [get_ports led[2]] +set_property PACKAGE_PIN V19 [get_ports led[3]] +set_property PACKAGE_PIN W18 [get_ports led[4]] +set_property PACKAGE_PIN U15 [get_ports led[5]] +set_property PACKAGE_PIN U14 [get_ports led[6]] +set_property PACKAGE_PIN V14 [get_ports led[7]] +set_property PACKAGE_PIN V13 [get_ports led[8]] +set_property PACKAGE_PIN V3 [get_ports led[9]] +set_property PACKAGE_PIN W3 [get_ports led[10]] +set_property PACKAGE_PIN U3 [get_ports led[11]] +set_property PACKAGE_PIN P3 [get_ports led[12]] +set_property PACKAGE_PIN N3 [get_ports led[13]] +set_property PACKAGE_PIN P1 [get_ports led[14]] +set_property PACKAGE_PIN L1 [get_ports led[15]] + +set_property IOSTANDARD LVCMOS33 [get_ports clk] + +set_property IOSTANDARD LVCMOS33 [get_ports tx] +set_property IOSTANDARD LVCMOS33 [get_ports rx] +# +set_property IOSTANDARD LVCMOS33 [get_ports sw[0]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[1]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[2]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[3]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[4]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[5]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[6]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[7]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[8]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[9]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[10]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[11]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[12]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[13]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[14]] +set_property IOSTANDARD LVCMOS33 [get_ports sw[15]] + +set_property IOSTANDARD LVCMOS33 [get_ports led[0]] +set_property IOSTANDARD LVCMOS33 [get_ports led[1]] +set_property IOSTANDARD LVCMOS33 [get_ports led[2]] +set_property IOSTANDARD LVCMOS33 [get_ports led[3]] +set_property IOSTANDARD LVCMOS33 [get_ports led[4]] +set_property IOSTANDARD LVCMOS33 [get_ports led[5]] +set_property IOSTANDARD LVCMOS33 [get_ports led[6]] +set_property IOSTANDARD LVCMOS33 [get_ports led[7]] +set_property IOSTANDARD LVCMOS33 [get_ports led[8]] +set_property IOSTANDARD LVCMOS33 [get_ports led[9]] +set_property IOSTANDARD LVCMOS33 [get_ports led[10]] +set_property IOSTANDARD LVCMOS33 [get_ports led[11]] +set_property IOSTANDARD LVCMOS33 [get_ports led[12]] +set_property IOSTANDARD LVCMOS33 [get_ports led[13]] +set_property IOSTANDARD LVCMOS33 [get_ports led[14]] +set_property IOSTANDARD LVCMOS33 [get_ports led[15]] diff --git a/fpga_interchange/examples/tests/ram/ram.v b/fpga_interchange/examples/tests/ram/ram.v new file mode 100644 index 00000000..aec5c4d1 --- /dev/null +++ b/fpga_interchange/examples/tests/ram/ram.v @@ -0,0 +1,134 @@ +module ram0( + // Write port + input wrclk, + input [15:0] di, + input wren, + input [9:0] wraddr, + // Read port + input rdclk, + input rden, + input [9:0] rdaddr, + output reg [15:0] do); + + (* ram_style = "block" *) reg [15:0] ram[0:1023]; + + initial begin + ram[0] = 16'b00000000_00000001; + ram[1] = 16'b10101010_10101010; + ram[2] = 16'b01010101_01010101; + ram[3] = 16'b11111111_11111111; + ram[4] = 16'b11110000_11110000; + ram[5] = 16'b00001111_00001111; + ram[6] = 16'b11001100_11001100; + ram[7] = 16'b00110011_00110011; + ram[8] = 16'b00000000_00000010; + ram[9] = 16'b00000000_00000100; + end + + always @ (posedge wrclk) begin + if(wren == 1) begin + ram[wraddr] <= di; + end + end + + always @ (posedge rdclk) begin + if(rden == 1) begin + do <= ram[rdaddr]; + end + end + +endmodule + +module top ( + input wire clk, + + input wire rx, + output wire tx, + + input wire [15:0] sw, + output wire [15:0] led +); + wire rden; + reg wren; + wire [9:0] rdaddr; + wire [9:0] wraddr; + wire [15:0] di; + wire [15:0] do; + ram0 ram( + .wrclk(clk), + .di(di), + .wren(wren), + .wraddr(wraddr), + .rdclk(clk), + .rden(rden), + .rdaddr(rdaddr), + .do(do) + ); + + reg [9:0] address_reg; + reg [15:0] data_reg; + reg [15:0] out_reg; + + assign rdaddr = address_reg; + assign wraddr = address_reg; + + // display_mode == 00 -> ram[address_reg] + // display_mode == 01 -> address_reg + // display_mode == 10 -> data_reg + wire [1:0] display_mode; + + // input_mode == 00 -> in[9:0] -> address_reg + // input_mode == 01 -> in[7:0] -> data_reg[7:0] + // input_mode == 10 -> in[7:0] -> data_reg[15:8] + // input_mode == 11 -> data_reg -> ram[address_reg] + wire [1:0] input_mode; + + // WE == 0 -> address_reg and data_reg unchanged. + // WE == 1 -> address_reg or data_reg is updated because on input_mode. + wire we; + + assign display_mode[0] = sw[14]; + assign display_mode[1] = sw[15]; + + assign input_mode[0] = sw[12]; + assign input_mode[1] = sw[13]; + + assign we = sw[11]; + assign led = out_reg; + assign di = data_reg; + assign rden = 1; + + initial begin + address_reg = 10'b0; + data_reg = 16'b0; + out_reg = 16'b0; + end + + always @ (posedge clk) begin + if(display_mode == 0) begin + out_reg <= do; + end else if(display_mode == 1) begin + out_reg <= address_reg; + end else if(display_mode == 2) begin + out_reg <= data_reg; + end + + if(we == 1) begin + if(input_mode == 0) begin + address_reg <= sw[9:0]; + wren <= 0; + end else if(input_mode == 1) begin + data_reg[7:0] <= sw[7:0]; + wren <= 0; + end else if(input_mode == 2) begin + data_reg[15:8] <= sw[7:0]; + wren <= 0; + end else if(input_mode == 3) begin + wren <= 1; + end + end + end + + // Uart loopback + assign tx = rx; +endmodule diff --git a/fpga_interchange/examples/tests/ram/run.tcl b/fpga_interchange/examples/tests/ram/run.tcl new file mode 100644 index 00000000..79321139 --- /dev/null +++ b/fpga_interchange/examples/tests/ram/run.tcl @@ -0,0 +1,17 @@ +yosys -import + +foreach src $::env(SOURCES) { + read_verilog $src +} + +synth_xilinx -flatten -nolutram -nowidelut -nosrl -nocarry -nodsp +techmap -map $::env(TECHMAP) + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json $::env(OUT_JSON) diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index 1be1dfde..52d49fa2 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -220,11 +220,25 @@ static void init_bel_pin( std::string site_name = site_and_type.substr(0, pos); - auto out_bel_pin = branch.getRouteSegment().initBelPin(); - - out_bel_pin.setSite(strings->get_index(site_name)); - out_bel_pin.setBel(strings->get_index(bel_name[1].str(ctx))); - out_bel_pin.setPin(strings->get_index(pin_name.str(ctx))); + const BelInfoPOD & bel_data = bel_info(ctx->chip_info, bel); + if(bel_data.category == BEL_CATEGORY_LOGIC) { + // This is a boring old logic BEL. + auto out_bel_pin = branch.getRouteSegment().initBelPin(); + + out_bel_pin.setSite(strings->get_index(site_name)); + out_bel_pin.setBel(strings->get_index(bel_name[1].str(ctx))); + out_bel_pin.setPin(strings->get_index(pin_name.str(ctx))); + } else { + // This is a local site inverter. This is represented with a + // $nextpnr_inv, and this BEL pin is the input to that inverter. + NPNR_ASSERT(bel_data.category == BEL_CATEGORY_ROUTING); + auto out_pip = branch.getRouteSegment().initSitePIP(); + + out_pip.setSite(strings->get_index(site_name)); + out_pip.setBel(strings->get_index(bel_name[1].str(ctx))); + out_pip.setPin(strings->get_index(pin_name.str(ctx))); + out_pip.setIsInverting(true); + } } @@ -383,10 +397,16 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str StringEnumerator strings; + IdString nextpnr_inv = ctx->id("$nextpnr_inv"); + size_t number_placements = 0; for(auto & cell_name : placed_cells) { const CellInfo & cell = *ctx->cells.at(cell_name); + if(cell.type == nextpnr_inv) { + continue; + } + if(cell.bel == BelId()) { continue; } @@ -412,6 +432,10 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str for(auto & cell_name : placed_cells) { const CellInfo & cell = *ctx->cells.at(cell_name); + if(cell.type == nextpnr_inv) { + continue; + } + if(cell.bel == BelId()) { continue; } @@ -513,8 +537,6 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str net_out.setName(strings.get_index(net.name.str(ctx))); } - // FIXME: Also vcc/gnd nets needs to get special handling through - // inverters. std::unordered_map<WireId, BelPin> root_wires; std::unordered_map<WireId, std::vector<PipId>> pip_downhill; std::unordered_set<PipId> pips; diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc index bdf728fd..930e25d1 100644 --- a/fpga_interchange/luts.cc +++ b/fpga_interchange/luts.cc @@ -45,6 +45,12 @@ bool rotate_and_merge_lut_equation(std::vector<LogicLevel> *result, const LutBel if ((bel_address & (1 << bel_pin_idx)) == 0) { // This pin is unused, so the line will be tied high, this // address is unreachable. + // + // FIXME: The assumption is that unused pins are tied VCC. + // This is not generally true. + // + // Use Arch::prefered_constant_net_type to determine what + // constant net should be used for unused pins. if ((used_pins & (1 << bel_pin_idx)) == 0) { address_reachable = false; break; @@ -124,6 +130,86 @@ 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); + } + } + + // FIXME: The assumption is that unused pins are tied VCC. + // This is not generally true. + // + // Use Arch::prefered_constant_net_type to determine what + // constant net should be used for unused pins. + 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 +345,49 @@ 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. + // + // FIXME: The assumption is that unused pins are tied VCC. + // This is not generally true. + // + // 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); +#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..9cf7fa0c 100644 --- a/fpga_interchange/site_arch.cc +++ b/fpga_interchange/site_arch.cc @@ -59,6 +59,10 @@ bool SiteArch::bindPip(const SitePip &pip, SiteNetInfo *net) result.first->second.count += 1; } + if (debug()) { + log_info("Bound pip %s to wire %s\n", nameOfPip(pip), nameOfWire(dst)); + } + return true; } @@ -67,6 +71,10 @@ void SiteArch::unbindPip(const SitePip &pip) SiteWire src = getPipSrcWire(pip); SiteWire dst = getPipDstWire(pip); + if (debug()) { + log_info("Unbinding pip %s from wire %s\n", nameOfPip(pip), nameOfWire(dst)); + } + SiteNetInfo *src_net = unbindWire(src); SiteNetInfo *dst_net = unbindWire(dst); NPNR_ASSERT(src_net == dst_net); @@ -125,6 +133,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 +141,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 +235,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}); @@ -254,10 +288,16 @@ const char *SiteArch::nameOfWire(const SiteWire &wire) const return ctx->nameOfWire(wire.wire); case SiteWire::SITE_PORT_SOURCE: return ctx->nameOfWire(wire.wire); - case SiteWire::OUT_OF_SITE_SOURCE: - return "out of site source, implement me!"; - case SiteWire::OUT_OF_SITE_SINK: - return "out of site sink, implement me!"; + case SiteWire::OUT_OF_SITE_SOURCE: { + std::string &str = ctx->log_strs.next(); + str = stringf("Out of site source for net %s", wire.net->name.c_str(ctx)); + return str.c_str(); + } + case SiteWire::OUT_OF_SITE_SINK: { + std::string &str = ctx->log_strs.next(); + str = stringf("Out of sink source for net %s", wire.net->name.c_str(ctx)); + return str.c_str(); + } default: // Unreachable! NPNR_ASSERT(false); @@ -271,12 +311,24 @@ const char *SiteArch::nameOfPip(const SitePip &pip) const return ctx->nameOfPip(pip.pip); case SitePip::SITE_PORT: return ctx->nameOfPip(pip.pip); - case SitePip::SOURCE_TO_SITE_PORT: - return "source to site port, implement me!"; - case SitePip::SITE_PORT_TO_SINK: - return "site port to sink, implement me!"; - case SitePip::SITE_PORT_TO_SITE_PORT: - return "site port to site port, implement me!"; + case SitePip::SOURCE_TO_SITE_PORT: { + std::string &str = ctx->log_strs.next(); + str = stringf("Out of site source for net %s => %s", pip.wire.net->name.c_str(ctx), + ctx->nameOfWire(ctx->getPipSrcWire(pip.pip))); + return str.c_str(); + } + case SitePip::SITE_PORT_TO_SINK: { + std::string &str = ctx->log_strs.next(); + str = stringf("%s => Out of site sink for net %s", ctx->nameOfWire(ctx->getPipDstWire(pip.pip)), + pip.wire.net->name.c_str(ctx)); + return str.c_str(); + } + case SitePip::SITE_PORT_TO_SITE_PORT: { + std::string &str = ctx->log_strs.next(); + str = stringf("%s => %s", ctx->nameOfWire(ctx->getPipSrcWire(pip.pip)), + ctx->nameOfWire(ctx->getPipDstWire(pip.other_pip))); + return str.c_str(); + } default: // Unreachable! NPNR_ASSERT(false); diff --git a/fpga_interchange/site_arch.h b/fpga_interchange/site_arch.h index 95b6fcba..91330aa0 100644 --- a/fpga_interchange/site_arch.h +++ b/fpga_interchange/site_arch.h @@ -25,6 +25,7 @@ #include <unordered_set> #include <vector> +#include "PhysicalNetlist.capnp.h" #include "arch_iterators.h" #include "chipdb.h" #include "hash_table.h" @@ -295,6 +296,11 @@ struct SiteArch // Can this site pip optional invert its signal? inline bool canInvert(const SitePip &site_pip) const NPNR_ALWAYS_INLINE; + // For a site port, returns the preferred constant net type. + // + // If no preference, then NetType is SIGNAL. + inline PhysicalNetlist::PhysNetlist::NetType prefered_constant_net_type(const SitePip &site_pip) const; + inline SitePipDownhillRange getPipsDownhill(const SiteWire &site_wire) const NPNR_ALWAYS_INLINE; inline SitePipUphillRange getPipsUphill(const SiteWire &site_wire) const NPNR_ALWAYS_INLINE; SiteWireRange getWires() const; diff --git a/fpga_interchange/site_arch.impl.h b/fpga_interchange/site_arch.impl.h index 0be298c9..a471b690 100644 --- a/fpga_interchange/site_arch.impl.h +++ b/fpga_interchange/site_arch.impl.h @@ -295,6 +295,25 @@ inline bool SiteArch::canInvert(const SitePip &site_pip) const return bel_data.non_inverting_pin == pip_data.extra_data && bel_data.inverting_pin == pip_data.extra_data; } +inline PhysicalNetlist::PhysNetlist::NetType SiteArch::prefered_constant_net_type(const SitePip &site_pip) const +{ + // FIXME: Implement site port overrides from chipdb once available. + IdString prefered_constant_net(ctx->chip_info->constants->best_constant_net); + IdString gnd_net_name(ctx->chip_info->constants->gnd_net_name); + IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name); + + if (prefered_constant_net == IdString()) { + return PhysicalNetlist::PhysNetlist::NetType::SIGNAL; + } else if (prefered_constant_net == gnd_net_name) { + return PhysicalNetlist::PhysNetlist::NetType::GND; + } else if (prefered_constant_net == vcc_net_name) { + return PhysicalNetlist::PhysNetlist::NetType::VCC; + } else { + log_error("prefered_constant_net %s is not the GND (%s) or VCC(%s) net?\n", prefered_constant_net.c_str(ctx), + gnd_net_name.c_str(ctx), vcc_net_name.c_str(ctx)); + } +} + NEXTPNR_NAMESPACE_END #endif /* SITE_ARCH_H */ diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 630db37f..8870fa32 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -19,12 +19,12 @@ #include "nextpnr.h" +#include "design_utils.h" #include "dynamic_bitarray.h" +#include "hash_table.h" #include "log.h" #include "site_routing_cache.h" -#include "hash_table.h" - #include "site_arch.h" #include "site_arch.impl.h" @@ -98,15 +98,15 @@ bool check_initial_wires(const Context *ctx, SiteInformation *site_info) static bool is_invalid_site_port(const SiteArch *ctx, const SiteNetInfo *net, const SitePip &pip) { SyntheticType type = ctx->pip_synthetic_type(pip); + PhysicalNetlist::PhysNetlist::NetType net_type = ctx->ctx->get_net_type(net->net); + bool is_invalid = false; if (type == SYNTH_GND) { - IdString gnd_net_name(ctx->ctx->chip_info->constants->gnd_net_name); - return net->net->name != gnd_net_name; + is_invalid = net_type != PhysicalNetlist::PhysNetlist::NetType::GND; } else if (type == SYNTH_VCC) { - IdString vcc_net_name(ctx->ctx->chip_info->constants->vcc_net_name); - return net->net->name != vcc_net_name; - } else { - return false; + is_invalid = net_type != PhysicalNetlist::PhysNetlist::NetType::VCC; } + + return is_invalid; } struct SiteExpansionLoop @@ -328,7 +328,7 @@ void print_current_state(const SiteArch *site_arch) log_info(" Cells in site:\n"); for (CellInfo *cell : cells_in_site) { - log_info(" - %s (%s)\n", cell->name.c_str(ctx), cell->type.c_str(ctx)); + log_info(" - %s (%s) => %s\n", cell->name.c_str(ctx), cell->type.c_str(ctx), ctx->nameOfBel(cell->bel)); } log_info(" Nets in site:\n"); @@ -368,6 +368,7 @@ struct PossibleSolutions std::vector<SitePip>::const_iterator pips_end; bool inverted = false; bool can_invert = false; + PhysicalNetlist::PhysNetlist::NetType prefered_constant_net_type = PhysicalNetlist::PhysNetlist::NetType::SIGNAL; }; bool test_solution(SiteArch *ctx, SiteNetInfo *net, std::vector<SitePip>::const_iterator pips_begin, @@ -375,12 +376,16 @@ bool test_solution(SiteArch *ctx, SiteNetInfo *net, std::vector<SitePip>::const_ { bool valid = true; std::vector<SitePip>::const_iterator good_pip_end = pips_begin; - for (auto iter = pips_begin; iter != pips_end; ++iter) { - if (!ctx->bindPip(*iter, net)) { + std::vector<SitePip>::const_iterator iter = pips_begin; + SitePip pip; + while (iter != pips_end) { + pip = *iter; + if (!ctx->bindPip(pip, net)) { valid = false; break; } + ++iter; good_pip_end = iter; } @@ -390,7 +395,7 @@ bool test_solution(SiteArch *ctx, SiteNetInfo *net, std::vector<SitePip>::const_ ctx->unbindPip(*iter); } } else { - NPNR_ASSERT(net->driver == ctx->getPipSrcWire(*good_pip_end)); + NPNR_ASSERT(net->driver == ctx->getPipSrcWire(pip)); } return valid; @@ -404,8 +409,92 @@ void remove_solution(SiteArch *ctx, std::vector<SitePip>::const_iterator pips_be } } +struct SolutionPreference +{ + const SiteArch *ctx; + const std::vector<PossibleSolutions> &solutions; + + SolutionPreference(const SiteArch *ctx, const std::vector<PossibleSolutions> &solutions) + : ctx(ctx), solutions(solutions) + { + } + + bool non_inverting_preference(const PossibleSolutions &lhs, const PossibleSolutions &rhs) const + { + // If the LHS is non-inverting and the RHS is inverting, then put the + // LHS first. + if (!lhs.inverted && rhs.inverted) { + return true; + } + + // Better to have a path that can invert over a path that has no + // option to invert. + return (!lhs.can_invert) < (!rhs.can_invert); + } + + bool inverting_preference(const PossibleSolutions &lhs, const PossibleSolutions &rhs) const + { + // If the LHS is inverting and the RHS is non-inverting, then put the + // LHS first (because this is the inverting preferred case). + if (lhs.inverted && !rhs.inverted) { + return true; + } + + // Better to have a path that can invert over a path that has no + // option to invert. + return (!lhs.can_invert) < (!rhs.can_invert); + } + + bool operator()(size_t lhs_solution_idx, size_t rhs_solution_idx) const + { + const PossibleSolutions &lhs = solutions.at(lhs_solution_idx); + const PossibleSolutions &rhs = solutions.at(rhs_solution_idx); + + NPNR_ASSERT(lhs.net == rhs.net); + + PhysicalNetlist::PhysNetlist::NetType net_type = ctx->ctx->get_net_type(lhs.net->net); + if (net_type == PhysicalNetlist::PhysNetlist::NetType::SIGNAL) { + return non_inverting_preference(lhs, rhs); + } + + // All GND/VCC nets use out of site sources. Local constant sources + // are still connected via synthetic edges to the global GND/VCC + // network. + NPNR_ASSERT(lhs.net->driver.type == SiteWire::OUT_OF_SITE_SOURCE); + + bool lhs_match_preference = net_type == lhs.prefered_constant_net_type; + bool rhs_match_preference = net_type == rhs.prefered_constant_net_type; + + if (lhs_match_preference && !rhs_match_preference) { + // Prefer solutions where the net type already matches the + // prefered constant type. + return true; + } + + if (!lhs_match_preference && rhs_match_preference) { + // Prefer solutions where the net type already matches the + // prefered constant type. In this case the RHS is better, which + // means that RHS < LHS, hence false here. + return false; + } + + NPNR_ASSERT(lhs_match_preference == rhs_match_preference); + + if (!lhs_match_preference) { + // If the net type does not match the preference, then prefer + // inverted solutions. + return inverting_preference(lhs, rhs); + } else { + // If the net type does match the preference, then prefer + // non-inverted solutions. + return non_inverting_preference(lhs, rhs); + } + } +}; + static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolutions> *solutions, - const std::vector<std::vector<size_t>> &sinks_to_solutions) + std::vector<std::vector<size_t>> sinks_to_solutions, + const std::vector<SiteWire> &sinks, bool explain) { std::vector<uint8_t> routed_sinks; std::vector<size_t> solution_indicies; @@ -414,14 +503,43 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut solution_indicies.resize(sinks_to_solutions.size(), 0); // Scan solutions, and remove any solutions that are invalid immediately - for (auto &solution : *solutions) { + for (size_t solution_idx = 0; solution_idx < solutions->size(); ++solution_idx) { + PossibleSolutions &solution = (*solutions)[solution_idx]; + if (verbose_site_router(ctx) || explain) { + log_info("Testing solution %zu\n", solution_idx); + } if (test_solution(ctx, solution.net, solution.pips_begin, solution.pips_end)) { + if (verbose_site_router(ctx) || explain) { + log_info("Solution %zu is good\n", solution_idx); + } remove_solution(ctx, solution.pips_begin, solution.pips_end); } else { + if (verbose_site_router(ctx) || explain) { + log_info("Solution %zu is not useable\n", solution_idx); + } solution.tested = true; } } + // Sort sinks_to_solutions so that preferred solutions are tested earlier + // than less preferred solutions. + for (size_t sink_idx = 0; sink_idx < sinks_to_solutions.size(); ++sink_idx) { + std::vector<size_t> &solutions_for_sink = sinks_to_solutions.at(sink_idx); + std::stable_sort(solutions_for_sink.begin(), solutions_for_sink.end(), SolutionPreference(ctx, *solutions)); + + if (verbose_site_router(ctx) || explain) { + log_info("Solutions for sink %s (%zu)\n", ctx->nameOfWire(sinks.at(sink_idx)), sink_idx); + for (size_t solution_idx : solutions_for_sink) { + const PossibleSolutions &solution = solutions->at(solution_idx); + log_info("%zu: inverted = %d, can_invert = %d, tested = %d\n", solution_idx, solution.inverted, + solution.can_invert, solution.tested); + for (auto iter = solution.pips_begin; iter != solution.pips_end; ++iter) { + log_info(" - %s\n", ctx->nameOfPip(*iter)); + } + } + } + } + for (size_t sink_idx = 0; sink_idx < sinks_to_solutions.size(); ++sink_idx) { size_t solution_count = 0; for (size_t solution_idx : sinks_to_solutions[sink_idx]) { @@ -431,6 +549,9 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut } if (solution_count == 0) { + if (verbose_site_router(ctx) || explain) { + log_info("Sink %s has no solution in site\n", ctx->nameOfWire(sinks.at(sink_idx))); + } return false; } @@ -466,11 +587,14 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut size_t sink_idx = solution_order[solution_stack.size()].first; size_t next_solution_to_test = solution_indicies[sink_idx]; + if (verbose_site_router(ctx) || explain) { + log_info("next %zu : %zu (of %zu)\n", sink_idx, next_solution_to_test, sinks_to_solutions[sink_idx].size()); + } if (next_solution_to_test >= sinks_to_solutions[sink_idx].size()) { // We have exausted all solutions at this level of the stack! if (solution_stack.empty()) { // Search is done, failed!!! - if (verbose_site_router(ctx)) { + if (verbose_site_router(ctx) || explain) { log_info("No solution found via backtrace with %zu solutions and %zu sinks\n", solutions->size(), sinks_to_solutions.size()); } @@ -478,7 +602,11 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut } else { // This level of the stack is completely tapped out, pop back // to the next level up. + size_t sink_idx = solution_order[solution_stack.size() - 1].first; size_t solution_idx = solution_stack.back(); + if (verbose_site_router(ctx) || explain) { + log_info("pop %zu : %zu\n", sink_idx, solution_idx); + } solution_stack.pop_back(); // Remove the now tested bad solution at the previous level of @@ -488,7 +616,6 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut // Because we had to pop up the stack, advance the index at // the level below us and start again. - sink_idx = solution_order[solution_stack.size()].first; solution_indicies[sink_idx] += 1; continue; } @@ -498,16 +625,26 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut auto &solution = solutions->at(solution_idx); if (solution.tested) { // This solution was already determined to be no good, skip it. + if (verbose_site_router(ctx) || explain) { + log_info("skip %zu : %zu\n", sink_idx, solution_idx); + } solution_indicies[sink_idx] += 1; continue; } + if (verbose_site_router(ctx) || explain) { + log_info("test %zu : %zu\n", sink_idx, solution_idx); + } + if (!test_solution(ctx, solution.net, solution.pips_begin, solution.pips_end)) { // This solution was no good, try the next one at this level of // the stack. solution_indicies[sink_idx] += 1; } else { // This solution was good, push onto the stack. + if (verbose_site_router(ctx) || explain) { + log_info("push %zu : %zu\n", sink_idx, solution_idx); + } solution_stack.push_back(solution_idx); if (solution_stack.size() == sinks_to_solutions.size()) { // Found a valid solution, done! @@ -529,7 +666,7 @@ static bool find_solution_via_backtrack(SiteArch *ctx, std::vector<PossibleSolut NPNR_ASSERT(false); } -bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeStorage *node_storage) +bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeStorage *node_storage, bool explain) { std::vector<SiteExpansionLoop *> expansions; expansions.reserve(ctx->nets.size()); @@ -544,7 +681,7 @@ bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeSt SiteExpansionLoop *router = expansions.back(); if (!router->expand_net(ctx, site_routing_cache, net)) { - if (verbose_site_router(ctx)) { + if (verbose_site_router(ctx) || explain) { log_info("Net %s expansion failed to reach all users, site is unroutable!\n", ctx->nameOfNet(net)); } @@ -554,12 +691,14 @@ bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeSt // First convert remaining solutions into a flat solution set. std::vector<PossibleSolutions> solutions; + std::vector<SiteWire> sinks; HashTables::HashMap<SiteWire, size_t> sink_map; std::vector<std::vector<size_t>> sinks_to_solutions; for (const auto *expansion : expansions) { for (const SiteWire &unrouted_sink : expansion->net_users) { auto result = sink_map.emplace(unrouted_sink, sink_map.size()); NPNR_ASSERT(result.second); + sinks.push_back(unrouted_sink); } } @@ -572,12 +711,6 @@ bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeSt for (const auto *expansion : expansions) { for (size_t idx = 0; idx < expansion->num_solutions(); ++idx) { - if (expansion->solution_inverted(idx)) { - // FIXME: May prefer an inverted solution if constant net - // type. - continue; - } - SiteWire wire = expansion->solution_sink(idx); auto begin = expansion->solution_begin(idx); auto end = expansion->solution_end(idx); @@ -595,15 +728,22 @@ bool route_site(SiteArch *ctx, SiteRoutingCache *site_routing_cache, RouteNodeSt solution.can_invert = expansion->solution_can_invert(idx); for (auto iter = begin; iter != end; ++iter) { - NPNR_ASSERT(ctx->getPipDstWire(*iter) == wire); - wire = ctx->getPipSrcWire(*iter); + const SitePip &site_pip = *iter; + NPNR_ASSERT(ctx->getPipDstWire(site_pip) == wire); + wire = ctx->getPipSrcWire(site_pip); + + // If there is a input site port, mark on the solution what the + // prefered constant net type is for this site port. + if (site_pip.type == SitePip::SITE_PORT && wire.type == SiteWire::SITE_PORT_SOURCE) { + solution.prefered_constant_net_type = ctx->prefered_constant_net_type(site_pip); + } } NPNR_ASSERT(expansion->net_driver == wire); } } - return find_solution_via_backtrack(ctx, &solutions, sinks_to_solutions); + return find_solution_via_backtrack(ctx, &solutions, sinks_to_solutions, sinks, explain); } void check_routing(const SiteArch &site_arch) @@ -631,26 +771,192 @@ void check_routing(const SiteArch &site_arch) } } -void apply_routing(Context *ctx, const SiteArch &site_arch) +static void apply_simple_routing(Context *ctx, const SiteArch &site_arch, NetInfo *net, const SiteNetInfo *site_net, + const SiteWire &user) { - for (auto &net_pair : site_arch.nets) { - NetInfo *net = net_pair.first; + SiteWire wire = user; + while (wire != site_net->driver) { + SitePip site_pip = site_net->wires.at(wire).pip; + NPNR_ASSERT(site_arch.getPipDstWire(site_pip) == wire); + + if (site_pip.type == SitePip::SITE_PIP || site_pip.type == SitePip::SITE_PORT) { + NetInfo *bound_net = ctx->getBoundPipNet(site_pip.pip); + if (bound_net == nullptr) { + ctx->bindPip(site_pip.pip, net, STRENGTH_PLACER); + } else { + NPNR_ASSERT(bound_net == net); + } + } + + wire = site_arch.getPipSrcWire(site_pip); + } +} - // If the driver wire is a site wire, bind it. - if (net_pair.second.driver.type == SiteWire::SITE_WIRE) { - WireId driver_wire = net_pair.second.driver.wire; - if (ctx->getBoundWireNet(driver_wire) != net) { - ctx->bindWire(driver_wire, net, STRENGTH_PLACER); +static void apply_constant_routing(Context *ctx, const SiteArch &site_arch, NetInfo *net, const SiteNetInfo *site_net) +{ + IdString gnd_net_name(ctx->chip_info->constants->gnd_net_name); + NetInfo *gnd_net = ctx->nets.at(gnd_net_name).get(); + + IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name); + NetInfo *vcc_net = ctx->nets.at(vcc_net_name).get(); + + // This function is designed to operate only on the gnd or vcc net, and + // assumes that the GND and VCC nets have been unified. + NPNR_ASSERT(net == vcc_net || net == gnd_net); + + for (auto &user : site_net->users) { + // FIXME: Handle case where pip is "can_invert", and that + // inversion helps with accomidating "best constant". + bool is_path_inverting = false; + + SiteWire wire = user; + PipId inverting_pip; + while (wire != site_net->driver) { + SitePip pip = site_net->wires.at(wire).pip; + NPNR_ASSERT(site_arch.getPipDstWire(pip) == wire); + + if (site_arch.isInverting(pip)) { + // FIXME: Should be able to handle the general case of + // multiple inverters, but that is harder (and annoying). Also + // most sites won't allow for a double inversion, so just + // disallow for now. + NPNR_ASSERT(!is_path_inverting); + is_path_inverting = true; + NPNR_ASSERT(pip.type == SitePip::SITE_PIP); + inverting_pip = pip.pip; } + + wire = site_arch.getPipSrcWire(pip); } - for (auto &wire_pair : net_pair.second.wires) { - const SitePip &site_pip = wire_pair.second.pip; - if (site_pip.type != SitePip::SITE_PIP && site_pip.type != SitePip::SITE_PORT) { - continue; + if (!is_path_inverting) { + // This routing is boring, use base logic. + apply_simple_routing(ctx, site_arch, net, site_net, user); + continue; + } + + NPNR_ASSERT(inverting_pip != PipId()); + + // This net is going to become two nets. + // The portion of the net prior to the inverter is going to be bound + // to the opposite net. For example, if the original net was gnd_net, + // the portion prior to the inverter will not be the vcc_net. + // + // A new cell will be generated to sink the connection from the + // opposite net. + NetInfo *net_before_inverter; + if (net == gnd_net) { + net_before_inverter = vcc_net; + } else { + NPNR_ASSERT(net == vcc_net); + net_before_inverter = gnd_net; + } + + // First find a name for the new cell + int count = 0; + CellInfo *new_cell = nullptr; + while (true) { + std::string new_cell_name = stringf("%s_%s.%d", net->name.c_str(ctx), site_arch.nameOfWire(user), count); + IdString new_cell_id = ctx->id(new_cell_name); + if (ctx->cells.count(new_cell_id)) { + count += 1; + } else { + new_cell = ctx->createCell(new_cell_id, ctx->id("$nextpnr_inv")); + break; } + } - ctx->bindPip(site_pip.pip, net, STRENGTH_PLACER); + auto &tile_type = loc_info(ctx->chip_info, inverting_pip); + auto &pip_data = tile_type.pip_data[inverting_pip.index]; + NPNR_ASSERT(pip_data.site != -1); + auto &bel_data = tile_type.bel_data[pip_data.bel]; + + BelId inverting_bel; + inverting_bel.tile = inverting_pip.tile; + inverting_bel.index = pip_data.bel; + + IdString in_port(bel_data.ports[pip_data.extra_data]); + NPNR_ASSERT(bel_data.types[pip_data.extra_data] == PORT_IN); + + IdString id_I = ctx->id("I"); + new_cell->addInput(id_I); + new_cell->cell_bel_pins[id_I].push_back(in_port); + + new_cell->bel = inverting_bel; + new_cell->belStrength = STRENGTH_PLACER; + ctx->tileStatus.at(inverting_bel.tile).boundcells[inverting_bel.index] = new_cell; + + connect_port(ctx, net_before_inverter, new_cell, id_I); + + // The original BEL pin is now routed, but only through the inverter. + // Because the cell/net model doesn't allow for multiple source pins + // and the fact that the portion of the net after the inverter is + // currently routed, all BEL pins on this site wire are going to be + // masked from the router. + NPNR_ASSERT(user.type == SiteWire::SITE_WIRE); + ctx->mask_bel_pins_on_site_wire(net, user.wire); + + // Bind wires and pips to the two nets. + bool after_inverter = true; + wire = user; + while (wire != site_net->driver) { + SitePip site_pip = site_net->wires.at(wire).pip; + NPNR_ASSERT(site_arch.getPipDstWire(site_pip) == wire); + + if (site_arch.isInverting(site_pip)) { + NPNR_ASSERT(after_inverter); + after_inverter = false; + + // Because this wire is just after the inverter, bind it to + // the net without the pip, as this is a "source". + NPNR_ASSERT(wire.type == SiteWire::SITE_WIRE); + ctx->bindWire(wire.wire, net, STRENGTH_PLACER); + } else { + if (site_pip.type == SitePip::SITE_PIP || site_pip.type == SitePip::SITE_PORT) { + if (after_inverter) { + ctx->bindPip(site_pip.pip, net, STRENGTH_PLACER); + } else { + ctx->bindPip(site_pip.pip, net_before_inverter, STRENGTH_PLACER); + } + } + } + + wire = site_arch.getPipSrcWire(site_pip); + } + } +} + +static void apply_routing(Context *ctx, const SiteArch &site_arch) +{ + IdString gnd_net_name(ctx->chip_info->constants->gnd_net_name); + NetInfo *gnd_net = ctx->nets.at(gnd_net_name).get(); + + IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name); + NetInfo *vcc_net = ctx->nets.at(vcc_net_name).get(); + + for (auto &net_pair : site_arch.nets) { + NetInfo *net = net_pair.first; + const SiteNetInfo *site_net = &net_pair.second; + + if (net == gnd_net || net == vcc_net) { + apply_constant_routing(ctx, site_arch, net, site_net); + } else { + // If the driver wire is a site wire, bind it. + if (site_net->driver.type == SiteWire::SITE_WIRE) { + WireId driver_wire = site_net->driver.wire; + if (ctx->getBoundWireNet(driver_wire) != net) { + ctx->bindWire(driver_wire, net, STRENGTH_PLACER); + } + } + + for (auto &wire_pair : site_net->wires) { + const SitePip &site_pip = wire_pair.second.pip; + if (site_pip.type != SitePip::SITE_PIP && site_pip.type != SitePip::SITE_PORT) { + continue; + } + + ctx->bindPip(site_pip.pip, net, STRENGTH_PLACER); + } } } } @@ -699,12 +1005,6 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta } } - // FIXME: Populate "consumed_wires" with all VCC/GND tied in the site. - // This will allow route_site to leverage site local constant sources. - // - // FIXME: Handle case where a constant is requested, but use of an - // inverter is possible. This is the place to handle "bestConstant" - // (e.g. route VCC's over GND's, etc). 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; @@ -747,7 +1047,7 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta SiteArch site_arch(&site_info); // site_arch.archcheck(); - site_ok = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage); + site_ok = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/false); if (verbose_site_router(ctx)) { if (site_ok) { log_info("Site %s is routable\n", ctx->get_site_name(tile, site)); @@ -799,7 +1099,7 @@ void SiteRouter::bindSiteRouting(Context *ctx) SiteInformation site_info(ctx, tile, site, cells_in_site); SiteArch site_arch(&site_info); - NPNR_ASSERT(route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage)); + 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)) { @@ -807,6 +1107,27 @@ void SiteRouter::bindSiteRouting(Context *ctx) } } +void SiteRouter::explain(const Context *ctx) const +{ + NPNR_ASSERT(!dirty); + if (site_ok) { + return; + } + + // Make sure all cells in this site belong! + auto iter = cells_in_site.begin(); + NPNR_ASSERT((*iter)->bel != BelId()); + + auto tile = (*iter)->bel.tile; + + SiteInformation site_info(ctx, tile, site, cells_in_site); + SiteArch site_arch(&site_info); + bool route_status = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/true); + if (!route_status) { + print_current_state(&site_arch); + } +} + ArchNetInfo::~ArchNetInfo() { delete loop; } Arch::~Arch() diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h index ebdfbe3b..cf17026d 100644 --- a/fpga_interchange/site_router.h +++ b/fpga_interchange/site_router.h @@ -47,6 +47,7 @@ struct SiteRouter void unbindBel(CellInfo *cell); bool checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const; void bindSiteRouting(Context *ctx); + void explain(const Context *ctx) const; }; NEXTPNR_NAMESPACE_END |