From 8773c645cae199d85d63461614c70854f54ae4db Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 1 Apr 2021 15:19:21 -0700 Subject: [interchange] Prevent site router from generating incorrect LUTs. The previous logic tied LUT input pins to VCC if a wire was unplacable. This missed a case where the net was present to the input of the LUT, but a wire was still not legal. This case is now prevented by tying the output of the LUT to an unused net. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/luts.cc | 18 ++++-- fpga_interchange/luts.h | 6 +- fpga_interchange/site_router.cc | 120 ++++++++++++++++++++++++++++------------ 3 files changed, 102 insertions(+), 42 deletions(-) diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc index 5903630a..3312f8ce 100644 --- a/fpga_interchange/luts.cc +++ b/fpga_interchange/luts.cc @@ -17,11 +17,12 @@ * */ -#include "nextpnr.h" -#include "log.h" #include "luts.h" +#include "nextpnr.h" +#include "log.h" + //#define DEBUG_LUT_ROTATION NEXTPNR_NAMESPACE_BEGIN @@ -167,16 +168,20 @@ uint32_t LutMapper::check_wires(const Context *ctx) const { } } - return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins); + HashTables::HashSet blocked_luts; + return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, + &blocked_luts); } uint32_t LutMapper::check_wires(const std::vector> &bel_to_cell_pin_remaps, - const std::vector &lut_bels, uint32_t used_pins) const + const std::vector &lut_bels, uint32_t used_pins, + HashTables::HashSet *blocked_luts) const { std::vector 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); + blocked_luts->emplace(&lut_bel_pair.second); } } @@ -238,6 +243,7 @@ uint32_t LutMapper::check_wires(const std::vector> &bel_to_ 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; + blocked_luts->erase(lut_bel); } } @@ -250,7 +256,7 @@ uint32_t LutMapper::check_wires(const std::vector> &bel_to_ return vcc_mask; } -bool LutMapper::remap_luts(const Context *ctx) +bool LutMapper::remap_luts(const Context *ctx, HashTables::HashSet *blocked_luts) { std::unordered_map lut_pin_map; std::vector lut_bels; @@ -408,7 +414,7 @@ bool LutMapper::remap_luts(const Context *ctx) // // 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); + uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts); #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) { diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h index 6978c7d2..980fe530 100644 --- a/fpga_interchange/luts.h +++ b/fpga_interchange/luts.h @@ -27,6 +27,7 @@ #include "nextpnr_namespaces.h" #include "dynamic_bitarray.h" +#include "hash_table.h" NEXTPNR_NAMESPACE_BEGIN @@ -91,7 +92,7 @@ struct LutMapper std::vector cells; - bool remap_luts(const Context *ctx); + bool remap_luts(const Context *ctx, HashTables::HashSet *blocked_luts); // Determine which wires given the current mapping must be tied to the // default constant. @@ -99,7 +100,8 @@ struct LutMapper // Returns a bit mask, 1 meaning it must be tied. Otherwise means that // the pin is free to be a signal. uint32_t check_wires(const std::vector> &bel_to_cell_pin_remaps, - const std::vector &lut_bels, uint32_t used_pins) const; + const std::vector &lut_bels, uint32_t used_pins, + HashTables::HashSet *blocked_luts) const; // Version of check_wires that uses current state of cells based on pin // mapping in cells variable. diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 6a066af0..aa82eca9 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -986,6 +986,80 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch) } } +static bool map_luts_in_site(const SiteInformation &site_info, + HashTables::HashSet> *blocked_wires) { + const Context *ctx = site_info.ctx; + const std::vector &lut_elements = ctx->lut_elements.at(site_info.tile_type); + std::vector lut_mappers; + lut_mappers.reserve(lut_elements.size()); + for (size_t i = 0; i < lut_elements.size(); ++i) { + lut_mappers.push_back(LutMapper(lut_elements[i])); + } + + for (CellInfo *cell : site_info.cells_in_site) { + if (cell->lut_cell.pins.empty()) { + continue; + } + + BelId bel = cell->bel; + const auto &bel_data = bel_info(ctx->chip_info, bel); + if (bel_data.lut_element != -1) { + lut_mappers[bel_data.lut_element].cells.push_back(cell); + } + } + + blocked_wires->clear(); + for (LutMapper lut_mapper : lut_mappers) { + if (lut_mapper.cells.empty()) { + continue; + } + + HashTables::HashSet blocked_luts; + if (!lut_mapper.remap_luts(ctx, &blocked_luts)) { + return false; + } + + for(const LutBel * lut_bel : blocked_luts) { + blocked_wires->emplace(std::make_pair(lut_bel->name, lut_bel->output_pin)); + } + } + + return true; +} + + +// Block outputs of unavailable LUTs to prevent site router from using them. +static void block_lut_outputs(SiteArch *site_arch, + const HashTables::HashSet> &blocked_wires) { + const Context * ctx = site_arch->site_info->ctx; + auto &tile_info = ctx->chip_info->tile_types[site_arch->site_info->tile_type]; + NetInfo blocking_net; + blocking_net.name = ctx->id("$nextpnr_blocked_net"); + + SiteNetInfo blocking_site_net; + blocking_site_net.net = &blocking_net; + for(const auto & bel_pin_pair : blocked_wires) { + IdString bel_name = bel_pin_pair.first; + IdString bel_pin = bel_pin_pair.second; + + int32_t bel_index = -1; + for (int32_t i = 0; i < tile_info.bel_data.ssize(); i++) { + if (tile_info.bel_data[i].site == site_arch->site_info->site && tile_info.bel_data[i].name == bel_name.index) { + bel_index = i; + break; + } + } + + NPNR_ASSERT(bel_index != -1); + BelId bel; + bel.tile = site_arch->site_info->tile; + bel.index = bel_index; + + SiteWire lut_output_wire = site_arch->getBelPinWire(bel, bel_pin); + site_arch->bindWire(lut_output_wire, &blocking_site_net); + } +} + bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const { // Overview: @@ -1040,41 +1114,12 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta } } - // At this point all cells should be legal via the constraint system. - // Check to see if the LUT elements contained within the site are legal. - auto tile_type_idx = ctx->chip_info->tiles[tile].type; - const std::vector &lut_elements = ctx->lut_elements.at(tile_type_idx); - std::vector lut_mappers; - lut_mappers.reserve(lut_elements.size()); - for (size_t i = 0; i < lut_elements.size(); ++i) { - lut_mappers.push_back(LutMapper(lut_elements[i])); - } - - for (CellInfo *cell : cells_in_site) { - if (cell->lut_cell.pins.empty()) { - continue; - } - - BelId bel = cell->bel; - const auto &bel_data = bel_info(ctx->chip_info, bel); - if (bel_data.lut_element != -1) { - lut_mappers[bel_data.lut_element].cells.push_back(cell); - } - } - - for (LutMapper lut_mapper : lut_mappers) { - if (lut_mapper.cells.empty()) { - continue; - } - - if (!lut_mapper.remap_luts(ctx)) { - // LUT equation sharing was not possible, fail. - site_ok = false; - return site_ok; - } - } - SiteInformation site_info(ctx, tile, site, cells_in_site); + HashTables::HashSet> blocked_wires; + if(!map_luts_in_site(site_info, &blocked_wires)) { + site_ok = false; + return site_ok; + } // Push from cell pins to the first WireId from each cell pin. // @@ -1093,6 +1138,8 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta // // site_arch.archcheck(); + block_lut_outputs(&site_arch, blocked_wires); + // Do a detailed routing check to see if the site has at least 1 valid // routing solution. site_ok = route_site(&site_arch, &ctx->site_routing_cache, &ctx->node_storage, /*explain=*/false); @@ -1146,8 +1193,13 @@ void SiteRouter::bindSiteRouting(Context *ctx) } SiteInformation site_info(ctx, tile, site, cells_in_site); + HashTables::HashSet> blocked_wires; + NPNR_ASSERT(map_luts_in_site(site_info, &blocked_wires)); + SiteArch site_arch(&site_info); + block_lut_outputs(&site_arch, blocked_wires); 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)) { -- cgit v1.2.3