From 0d41fff3a70a298036aa6fdc103093631998a2bd Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 1 Apr 2021 13:18:07 -0700 Subject: [interchange] Add crude pseudo pip model. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 39 ++- fpga_interchange/arch.h | 16 +- fpga_interchange/luts.cc | 42 +++- fpga_interchange/luts.h | 10 + fpga_interchange/pseudo_pip_model.cc | 470 +++++++++++++++++++++++++++++++++++ fpga_interchange/pseudo_pip_model.h | 147 +++++++++++ 6 files changed, 717 insertions(+), 7 deletions(-) create mode 100644 fpga_interchange/pseudo_pip_model.cc create mode 100644 fpga_interchange/pseudo_pip_model.h diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 0d6cc4de..45d35aa6 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -272,12 +272,25 @@ Arch::Arch(ArchArgs args) : args(args) } // Map lut cell types to their LutCellPOD + wire_lut = nullptr; for (const LutCellPOD &lut_cell : chip_info->cell_map->lut_cells) { IdString cell_type(lut_cell.cell); auto result = lut_cells.emplace(cell_type, &lut_cell); NPNR_ASSERT(result.second); + + if(lut_cell.input_pins.size() == 1) { + // Only really expecting 1 single input LUT type! + NPNR_ASSERT(wire_lut == nullptr); + wire_lut = &lut_cell; + } } + // There should be a cell that is a single input LUT. + // + // Note: This assumption may be not true, revisit if this becomes a + // problem. + NPNR_ASSERT(wire_lut != nullptr); + raw_bin_constant = std::regex("[01]+", std::regex_constants::ECMAScript | std::regex_constants::optimize); verilog_bin_constant = std::regex("([0-9]+)'b([01]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize); @@ -294,6 +307,10 @@ void Arch::init() #endif dedicated_interconnect.init(getCtx()); cell_parameters.init(getCtx()); + + for (size_t tile_type = 0; tile_type < chip_info->tile_types.size(); ++tile_type) { + pseudo_pip_data.init_tile_type(getCtx(), tile_type); + } } // ----------------------------------------------------------------------- @@ -798,6 +815,8 @@ static void prepare_sites_for_routing(Context *ctx) site_router.bindSiteRouting(ctx); } + + tile_pair.second.pseudo_pip_model.prepare_for_routing(ctx, tile_pair.second.sites); } // Fixup LUT vcc pins. @@ -1451,6 +1470,10 @@ void Arch::remove_pip_pseudo_wires(PipId pip, NetInfo *net) iter->second = nullptr; } } + + if(pip_data.pseudo_cell_wires.size() > 0) { + get_tile_status(pip.tile).pseudo_pip_model.unbindPip(getCtx(), pip); + } } void Arch::assign_net_to_wire(WireId wire, NetInfo *net, const char *src, bool require_empty) @@ -1681,6 +1704,18 @@ bool Arch::checkPipAvailForNet(PipId pip, NetInfo *net) const } } + if(pip_data.pseudo_cell_wires.size() > 0) { + // FIXME: This pseudo pip check is incomplete, because constraint + // failures will not be detected. However the current FPGA + // interchange schema does not provide a cell type to place. + auto iter = tileStatus.find(pip.tile); + if(iter != tileStatus.end()) { + if(!iter->second.pseudo_pip_model.checkPipAvail(getCtx(), pip)) { + return false; + } + } + } + if (pip_data.site != -1 && net != nullptr) { // FIXME: This check isn't perfect. If a driver and sink are in the // same site, it is possible for the router to route-thru the site @@ -1744,10 +1779,6 @@ bool Arch::checkPipAvailForNet(PipId pip, NetInfo *net) const } } - // FIXME: This pseudo pip check is incomplete, because constraint - // failures will not be detected. However the current FPGA - // interchange schema does not provide a cell type to place. - return true; } diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index cb137ef6..27d02a5f 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -39,6 +39,7 @@ #include "dedicated_interconnect.h" #include "lookahead.h" #include "site_router.h" +#include "pseudo_pip_model.h" #include "site_routing_cache.h" NEXTPNR_NAMESPACE_BEGIN @@ -90,6 +91,7 @@ struct TileStatus std::vector> tags; std::vector boundcells; std::vector sites; + PseudoPipModel pseudo_pip_model; }; struct Arch : ArchAPI @@ -108,7 +110,8 @@ struct Arch : ArchAPI std::unordered_map pip_to_net; DedicatedInterconnect dedicated_interconnect; - std::unordered_map tileStatus; + HashTables::HashMap tileStatus; + PseudoPipData pseudo_pip_data; ArchArgs args; Arch(ArchArgs args); @@ -175,13 +178,15 @@ struct Arch : ArchAPI auto result = tileStatus.emplace(tile, TileStatus()); if (result.second) { auto &tile_type = chip_info->tile_types[chip_info->tiles[tile].type]; - result.first->second.boundcells.resize(tile_type.bel_data.size()); + result.first->second.boundcells.resize(tile_type.bel_data.size(), nullptr); result.first->second.tags.resize(default_tags.size()); result.first->second.sites.reserve(tile_type.site_types.size()); for (size_t i = 0; i < tile_type.site_types.size(); ++i) { result.first->second.sites.push_back(SiteRouter(i)); } + + result.first->second.pseudo_pip_model.init(getCtx(), tile); } return result.first->second; @@ -547,6 +552,10 @@ struct Arch : ArchAPI wire.index = wire_index; assign_net_to_wire(wire, net, "pseudo", /*require_empty=*/true); } + + if(pip_data.pseudo_cell_wires.size() > 0) { + get_tile_status(pip.tile).pseudo_pip_model.bindPip(getCtx(), pip); + } } void remove_pip_pseudo_wires(PipId pip, NetInfo *net); @@ -1059,6 +1068,9 @@ struct Arch : ArchAPI std::vector> lut_elements; std::unordered_map lut_cells; + // Of the LUT cells, which is used for wires? + const LutCellPOD * wire_lut; + std::regex raw_bin_constant; std::regex verilog_bin_constant; std::regex verilog_hex_constant; diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc index 930e25d1..5903630a 100644 --- a/fpga_interchange/luts.cc +++ b/fpga_interchange/luts.cc @@ -22,6 +22,8 @@ #include "log.h" #include "luts.h" +//#define DEBUG_LUT_ROTATION + NEXTPNR_NAMESPACE_BEGIN bool rotate_and_merge_lut_equation(std::vector *result, const LutBel &lut_bel, @@ -128,7 +130,45 @@ struct LutPin bool operator<(const LutPin &other) const { return max_pin < other.max_pin; } }; -//#define DEBUG_LUT_ROTATION + +uint32_t LutMapper::check_wires(const Context *ctx) const { + // Unlike the 3 argument version of check_wires, this version needs to + // calculate following data based on current cell pin mapping, etc: + // + // - Index map from bel pins to cell pins, -1 for unmapped + // - Mask of used pins + // - Vector of unused LUT BELs. + + uint32_t used_pins = 0; + + std::vector> bel_to_cell_pin_remaps; + std::vector lut_bels; + bel_to_cell_pin_remaps.resize(cells.size()); + lut_bels.resize(cells.size()); + for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) { + const CellInfo *cell = cells[cell_idx]; + + + auto &bel_data = bel_info(ctx->chip_info, cell->bel); + IdString bel_name(bel_data.name); + auto &lut_bel = element.lut_bels.at(bel_name); + lut_bels[cell_idx] = &lut_bel; + + bel_to_cell_pin_remaps[cell_idx].resize(lut_bel.pins.size(), -1); + + for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) { + IdString lut_cell_pin = cell->lut_cell.pins[pin_idx]; + const std::vector bel_pins = cell->cell_bel_pins.at(lut_cell_pin); + NPNR_ASSERT(bel_pins.size() == 1); + + size_t bel_pin_idx = lut_bel.pin_to_index.at(bel_pins[0]); + bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] = pin_idx; + used_pins |= (1 << bel_pin_idx); + } + } + + return check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins); +} uint32_t LutMapper::check_wires(const std::vector> &bel_to_cell_pin_remaps, const std::vector &lut_bels, uint32_t used_pins) const diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h index 5a46b3ed..6978c7d2 100644 --- a/fpga_interchange/luts.h +++ b/fpga_interchange/luts.h @@ -92,8 +92,18 @@ struct LutMapper std::vector cells; bool remap_luts(const Context *ctx); + + // Determine which wires given the current mapping must be tied to the + // default constant. + // + // 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; + + // Version of check_wires that uses current state of cells based on pin + // mapping in cells variable. + uint32_t check_wires(const Context *ctx) const; }; // Rotate and merge a LUT equation into an array of levels. diff --git a/fpga_interchange/pseudo_pip_model.cc b/fpga_interchange/pseudo_pip_model.cc new file mode 100644 index 00000000..c34e3de7 --- /dev/null +++ b/fpga_interchange/pseudo_pip_model.cc @@ -0,0 +1,470 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * 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 "pseudo_pip_model.h" + +#include "context.h" + +//#define DEBUG_PSEUDO_PIP + +NEXTPNR_NAMESPACE_BEGIN + +void PseudoPipData::init_tile_type(const Context *ctx, int32_t tile_type) { + if(max_pseudo_pip_for_tile_type.count(tile_type)) { + return; + } + + const TileTypeInfoPOD & type_data = ctx->chip_info->tile_types[tile_type]; + int32_t max_pseudo_pip_index = -1; + for(int32_t pip_idx = 0; pip_idx < type_data.pip_data.ssize(); ++pip_idx) { + const PipInfoPOD & pip_data = type_data.pip_data[pip_idx]; + if(pip_data.pseudo_cell_wires.size() == 0) { + continue; + } + + if(pip_idx > max_pseudo_pip_index) { + max_pseudo_pip_index = pip_idx; + } + + HashTables::HashSet sites; + std::vector pseudo_pip_bels; + for(int32_t wire_index : pip_data.pseudo_cell_wires) { + const TileWireInfoPOD &wire_data = type_data.wire_data[wire_index]; + if(wire_data.site == -1) { + continue; + } + + // Only use primary site types for psuedo pips + // + // Note: This assumption may be too restrictive. If so, then + // need to update database generators to provide + // pseudo_cell_wires for each site type, not just the primary. + if(wire_data.site_variant != -1) { + continue; + } + + sites.emplace(wire_data.site); + + int32_t driver_bel = -1; + int32_t output_pin = -1; + for(const BelPortPOD & bel_pin : wire_data.bel_pins) { + const BelInfoPOD & bel_data = type_data.bel_data[bel_pin.bel_index]; + if(bel_data.synthetic != NOT_SYNTH) { + // Ignore synthetic BELs + continue; + } + + if(bel_data.category != BEL_CATEGORY_LOGIC) { + // Ignore site ports and site routing + continue; + } + + int32_t bel_pin_idx = -1; + for(int32_t i = 0; i < bel_data.num_bel_wires; ++i) { + if(bel_data.ports[i] == bel_pin.port) { + bel_pin_idx = i; + break; + } + } + + NPNR_ASSERT(bel_pin_idx != -1); + if(bel_data.types[bel_pin_idx] != PORT_OUT) { + // Only care about output ports. Input ports may not be + // part of the pseudo pip. + continue; + } + + // Each site wire should have 1 driver! + NPNR_ASSERT(driver_bel == -1); + driver_bel = bel_pin.bel_index; + output_pin = bel_pin_idx; + } + + if(driver_bel != -1) { + NPNR_ASSERT(output_pin != -1); + PseudoPipBel bel; + bel.bel_index = driver_bel; + bel.output_bel_pin = output_pin; + + pseudo_pip_bels.push_back(bel); + } + } + + std::pair key{tile_type, pip_idx}; + std::vector &sites_for_pseudo_pip = possibles_sites_for_pip[key]; + sites_for_pseudo_pip.clear(); + sites_for_pseudo_pip.insert(sites_for_pseudo_pip.begin(), sites.begin(), sites.end()); + std::sort(sites_for_pseudo_pip.begin(), sites_for_pseudo_pip.end()); + + // Initialize "logic_bels_for_pip" for every site that this pseudo pip + // appears. This means that if there are no pseudo_pip_bels, those + // vectors will be empty. + for(int32_t site : sites_for_pseudo_pip) { + logic_bels_for_pip[LogicBelKey{tile_type, pip_idx, site}].clear(); + } + + if(!pseudo_pip_bels.empty()) { + HashTables::HashSet pseudo_cell_wires; + pseudo_cell_wires.insert(pip_data.pseudo_cell_wires.begin(), pip_data.pseudo_cell_wires.end()); + + // For each BEL, find the input bel pin used, and attach it to + // the vector for that site. + // + // Note: Intentially copying the bel for mutation, and then + // pushing onto vector. + for(PseudoPipBel bel : pseudo_pip_bels) { + const BelInfoPOD & bel_data = type_data.bel_data[bel.bel_index]; + int32_t site = bel_data.site; + + int32_t input_bel_pin = -1; + int32_t output_bel_pin = -1; + for(int32_t i = 0; i < bel_data.num_bel_wires; ++i) { + if(!pseudo_cell_wires.count(bel_data.wires[i])) { + continue; + } + + if(bel_data.types[i] == PORT_OUT) { + NPNR_ASSERT(output_bel_pin == -1); + output_bel_pin = i; + } + + if(bel_data.types[i] == PORT_IN && input_bel_pin == -1) { + // Take first input BEL pin + // + // FIXME: This heuristic feels fragile. + // This data oaught come from the database. + input_bel_pin = i; + } + } + + NPNR_ASSERT(output_bel_pin == bel.output_bel_pin); + NPNR_ASSERT(input_bel_pin != -1); + bel.input_bel_pin = input_bel_pin; + + logic_bels_for_pip[LogicBelKey{tile_type, pip_idx, site}].push_back(bel); + } + } + } + + max_pseudo_pip_for_tile_type[tile_type] = max_pseudo_pip_index; +} + +const std::vector &PseudoPipData::get_possible_sites_for_pip(const Context *ctx, PipId pip) const { + int32_t tile_type = ctx->chip_info->tiles[pip.tile].type; + return possibles_sites_for_pip.at(std::make_pair(tile_type, pip.index)); +} + +size_t PseudoPipData::get_max_pseudo_pip(int32_t tile_type) const { + return max_pseudo_pip_for_tile_type.at(tile_type); +} + +const std::vector &PseudoPipData::get_logic_bels_for_pip(const Context *ctx, int32_t site, PipId pip) const { + int32_t tile_type = ctx->chip_info->tiles[pip.tile].type; + return logic_bels_for_pip.at(LogicBelKey{tile_type, pip.index, site}); +} + +void PseudoPipModel::init(Context *ctx, int32_t tile_idx) { + int32_t tile_type = ctx->chip_info->tiles[tile_idx].type; + + this->tile = tile_idx; + + allowed_pseudo_pips.resize(ctx->pseudo_pip_data.get_max_pseudo_pip(tile_type)+1); + allowed_pseudo_pips.fill(true); +} + +void PseudoPipModel::prepare_for_routing(const Context *ctx, const std::vector & sites) { + // First determine which sites have placed cells, these sites are consider + // active. + HashTables::HashSet active_sites; + for(size_t site = 0; site < sites.size(); ++site) { + if(!sites[site].cells_in_site.empty()) { + active_sites.emplace(site); + } + } + + // Assign each pseudo pip in this tile a site, which is either the active + // site (if the site / alt site is in use) or the first site that pseudo + // pip appears in. + int32_t tile_type = ctx->chip_info->tiles[tile].type; + const TileTypeInfoPOD & type_data = ctx->chip_info->tile_types[tile_type]; + + pseudo_pip_sites.clear(); + site_to_pseudo_pips.clear(); + + for(size_t pip_idx = 0; pip_idx < type_data.pip_data.size(); ++pip_idx) { + const PipInfoPOD & pip_data = type_data.pip_data[pip_idx]; + if(pip_data.pseudo_cell_wires.size() == 0) { + continue; + } + + PipId pip; + pip.tile = tile; + pip.index = pip_idx; + const std::vector &sites = ctx->pseudo_pip_data.get_possible_sites_for_pip(ctx, pip); + + int32_t site_for_pip = -1; + for(size_t possible_site : sites) { + if(active_sites.count(possible_site)) { + site_for_pip = possible_site; + break; + } + } + + if(site_for_pip < 0) { + site_for_pip = sites.at(0); + } + + pseudo_pip_sites[pip_idx] = site_for_pip; + site_to_pseudo_pips[site_for_pip].push_back(pip_idx); + } + + for(auto & site_pair : site_to_pseudo_pips) { + update_site(ctx, site_pair.first); + } +} + +bool PseudoPipModel::checkPipAvail(const Context *ctx, PipId pip) const { + bool allowed = allowed_pseudo_pips.get(pip.index); + if(!allowed) { +#ifdef DEBUG_PSEUDO_PIP + if(ctx->verbose) { + log_info("Pseudo pip %s not allowed\n", ctx->nameOfPip(pip)); + } +#endif + } + + return allowed; +} + +void PseudoPipModel::bindPip(const Context *ctx, PipId pip) { + // If pseudo_pip_sites is empty, then prepare_for_routing was never + // invoked. This is likely because PseudoPipModel was constructed during + // routing. + if(pseudo_pip_sites.empty()) { + prepare_for_routing(ctx, ctx->tileStatus.at(tile).sites); + } + + // Do not allow pseudo pips to be bound if they are not allowed! + NPNR_ASSERT(allowed_pseudo_pips.get(pip.index)); + + // Mark that this pseudo pip is active. + auto result = active_pseudo_pips.emplace(pip.index); + NPNR_ASSERT(result.second); + + // Update the site this pseudo pip is within. + size_t site = pseudo_pip_sites.at(pip.index); + update_site(ctx, site); +} + +void PseudoPipModel::unbindPip(const Context *ctx, PipId pip) { + // It should not be possible for unbindPip to be invoked with + // pseudo_pip_sites being empty. + NPNR_ASSERT(!pseudo_pip_sites.empty()); + + NPNR_ASSERT(active_pseudo_pips.erase(pip.index)); + + // Remove the site this pseudo pip is within. + size_t site = pseudo_pip_sites.at(pip.index); + update_site(ctx, site); +} + +void PseudoPipModel::update_site(const Context *ctx, size_t site) { + // update_site consists of several steps: + // + // - Find all BELs within the site used by pseudo pips. + // - Trivially marking other pseudo pips as unavailable if it requires + // logic BELs used by active pseudo pips (or bound by cells). + // - Determine if remaining pseudo pips can be legally placed. This + // generally consists of: + // - Checking LUT element + // - FIXME: Checking constraints (when metadata is available) + + const std::vector pseudo_pips_for_site = site_to_pseudo_pips.at(site); + + std::vector &unused_pseudo_pips = scratch; + unused_pseudo_pips.clear(); + unused_pseudo_pips.reserve(pseudo_pips_for_site.size()); + + HashTables::HashMap used_bels; + for(int32_t pseudo_pip : pseudo_pips_for_site) { + if(!active_pseudo_pips.count(pseudo_pip)) { + unused_pseudo_pips.push_back(pseudo_pip); + continue; + } + + PipId pip; + pip.tile = tile; + pip.index = pseudo_pip; + for(const PseudoPipBel & bel: ctx->pseudo_pip_data.get_logic_bels_for_pip(ctx, site, pip)) { + used_bels.emplace(bel.bel_index, bel); + } + } + + if(unused_pseudo_pips.empty()) { + return; + } + + int32_t tile_type = ctx->chip_info->tiles[tile].type; + const TileTypeInfoPOD & type_data = ctx->chip_info->tile_types[tile_type]; + + // This section builds up LUT mapping logic to determine which LUT wires + // are availble and which are not. + const std::vector &lut_elements = ctx->lut_elements.at(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])); + } + + const TileStatus & tile_status = ctx->tileStatus.at(tile); + for (CellInfo *cell : tile_status.sites[site].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); + } + } + + std::vector lut_cells; + lut_cells.reserve(used_bels.size()); + for(const auto & bel_pair : used_bels) { + const PseudoPipBel &bel = bel_pair.second; + const BelInfoPOD & bel_data = type_data.bel_data[bel.bel_index]; + + // This used BEL isn't a LUT, skip it! + if(bel_data.lut_element == -1) { + continue; + } + + lut_cells.emplace_back(); + CellInfo &cell = lut_cells.back(); + + cell.bel.tile = tile; + cell.bel.index = bel_pair.first; + + cell.type = IdString(ctx->wire_lut->cell); + NPNR_ASSERT(ctx->wire_lut->input_pins.size() == 1); + cell.lut_cell.pins.push_back(IdString(ctx->wire_lut->input_pins[0])); + cell.lut_cell.equation.resize(2); + cell.lut_cell.equation.set(0, false); + cell.lut_cell.equation.set(1, true); + + // Map LUT input to input wire used by pseudo pip. + IdString input_bel_pin(bel_data.ports[bel.input_bel_pin]); + cell.cell_bel_pins[IdString(ctx->wire_lut->input_pins[0])].push_back(input_bel_pin); + + lut_mappers[bel_data.lut_element].cells.push_back(&cell); + } + + std::vector lut_wires_unavailable; + lut_wires_unavailable.reserve(lut_elements.size()); + for(LutMapper &lut_mapper : lut_mappers) { + lut_wires_unavailable.push_back(lut_mapper.check_wires(ctx)); + } + + // For unused pseudo pips, see if the BEL used is idle. + for(int32_t pseudo_pip : unused_pseudo_pips) { + PipId pip; + pip.tile = tile; + pip.index = pseudo_pip; + + bool blocked_by_bel = false; + const std::vector & bels = ctx->pseudo_pip_data.get_logic_bels_for_pip(ctx, site, pip); + for(const PseudoPipBel & bel: bels) { + if(tile_status.boundcells[bel.bel_index] != nullptr) { + blocked_by_bel = true; + +#ifdef DEBUG_PSEUDO_PIP + if(ctx->verbose) { + BelId abel; + abel.tile = tile; + abel.index = bel.bel_index; + log_info("Pseudo pip %s is block by a bound BEL %s\n", + ctx->nameOfPip(pip), ctx->nameOfBel(abel)); + } +#endif + break; + } + + if(used_bels.count(bel.bel_index)) { +#ifdef DEBUG_PSEUDO_PIP + if(ctx->verbose) { + log_info("Pseudo pip %s is block by another pseudo pip\n", + ctx->nameOfPip(pip)); + } +#endif + blocked_by_bel = true; + break; + } + } + + if(blocked_by_bel) { + allowed_pseudo_pips.set(pseudo_pip, false); + continue; + } + + bool blocked_by_lut_eq = false; + + // See if any BELs are part of a LUT element. If so, see if using + // that pseudo pip violates the LUT element equation. + for(const PseudoPipBel & bel: bels) { + const BelInfoPOD & bel_data = type_data.bel_data[bel.bel_index]; + if(bel_data.lut_element == -1) { + continue; + } + + // FIXME: Check if the pseudo cell satifies the constraint system. + // Will become important for LUT-RAM/SRL testing. + + // FIXME: This lookup is static, consider moving to PseudoPipBel? + IdString bel_name(bel_data.name); + IdString input_bel_pin(bel_data.ports[bel.input_bel_pin]); + size_t pin_idx = lut_elements.at(bel_data.lut_element).lut_bels.at(bel_name).pin_to_index.at(input_bel_pin); + + uint32_t blocked_inputs = lut_wires_unavailable.at(bel_data.lut_element); + if((blocked_inputs & (1 << pin_idx)) != 0) { + blocked_by_lut_eq = true; + break; + } + } + + if(blocked_by_lut_eq) { +#ifdef DEBUG_PSEUDO_PIP + if(ctx->verbose) { + log_info("Pseudo pip %s is blocked by lut eq\n", + ctx->nameOfPip(pip)); + } +#endif + allowed_pseudo_pips.set(pseudo_pip, false); + continue; + } + + // Pseudo pip should be allowed, mark as such. + // + // FIXME: Handle non-LUT constraint cases, as needed. + allowed_pseudo_pips.set(pseudo_pip, true); + } +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/pseudo_pip_model.h b/fpga_interchange/pseudo_pip_model.h new file mode 100644 index 00000000..f0d93909 --- /dev/null +++ b/fpga_interchange/pseudo_pip_model.h @@ -0,0 +1,147 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 Symbiflow Authors + * + * + * 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. + * + */ + +#ifndef PSEUDO_PIP_MODEL_H +#define PSEUDO_PIP_MODEL_H + +#include + +#include "nextpnr_namespaces.h" +#include "nextpnr_types.h" +#include "site_router.h" +#include "dynamic_bitarray.h" +#include "hash_table.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct PseudoPipBel { + // Which BEL in the tile does the pseudo pip use? + int32_t bel_index; + + // What is the index of the input BEL pin that the pseudo pip used? + // + // NOTE: This is **not** the name of the pin. + int32_t input_bel_pin; + + // What is the index of the output BEL pin that the pseudo pip used? + // + // NOTE: This is **not** the name of the pin. + int32_t output_bel_pin; +}; + +struct LogicBelKey { + int32_t tile_type; + int32_t pip_index; + int32_t site; + + std::tuple make_tuple() const { + return std::make_tuple(tile_type, pip_index, site); + } + + bool operator == (const LogicBelKey & other) const { + return make_tuple() == other.make_tuple(); + } + + bool operator < (const LogicBelKey & other) const { + return make_tuple() < other.make_tuple(); + } +}; + +NEXTPNR_NAMESPACE_END + +namespace std { +template <> struct hash +{ + std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX LogicBelKey &key) const noexcept + { + std::size_t seed = 0; + boost::hash_combine(seed, hash()(key.tile_type)); + boost::hash_combine(seed, hash()(key.pip_index)); + boost::hash_combine(seed, hash()(key.site)); + + return seed; + } +}; + +}; + + +NEXTPNR_NAMESPACE_BEGIN + +// Storage for tile type generic pseudo pip data and lookup. +struct PseudoPipData { + // Initial data for specified tile type, if not already initialized. + void init_tile_type(const Context *ctx, int32_t tile_type); + + // Get the highest PipId::index found in a specified tile type. + size_t get_max_pseudo_pip(int32_t tile_type) const; + + // Get the list of possible sites that a pseudo pip might be used in. + const std::vector &get_possible_sites_for_pip(const Context *ctx, PipId pip) const; + + // Get list of BELs the pseudo pip uses, and how it routes through them. + // + // This does **not** include site ports or site pips. + const std::vector &get_logic_bels_for_pip(const Context *ctx, int32_t site, PipId pip) const; + + HashTables::HashMap max_pseudo_pip_for_tile_type; + HashTables::HashMap, std::vector> possibles_sites_for_pip; + HashTables::HashMap> logic_bels_for_pip; +}; + +// Tile instance fast pseudo pip lookup. +struct PseudoPipModel { + int32_t tile; + DynamicBitarray<> allowed_pseudo_pips; + HashTables::HashMap pseudo_pip_sites; + HashTables::HashMap> site_to_pseudo_pips; + HashTables::HashSet active_pseudo_pips; + std::vector scratch; + + // Call when a tile is initialized. + void init(Context *ctx, int32_t tile); + + // Call after placement but before routing to update which pseudo pips are + // legal. This call is important to ensure that checkPipAvail returns the + // correct value. + // + // If the tile has no placed elements, then prepare_for_routing does not + // need to be called after init. + void prepare_for_routing(const Context *ctx, const std::vector & sites); + + // Returns true if the pseudo pip is allowed given current site placements + // and other pseudo pips. + bool checkPipAvail(const Context *ctx, PipId pip) const; + + // Enables a pseudo pip in the model. May cause other pseudo pips to + // become unavailable. + void bindPip(const Context *ctx, PipId pip); + + // Removes a pseudo pip from the model. May cause other pseudo pips to + // become available. + void unbindPip(const Context *ctx, PipId pip); + + // Internal method to update pseudo pips marked as part of a site. + void update_site(const Context *ctx, size_t site); +}; + +NEXTPNR_NAMESPACE_END + +#endif /* PSEUDO_PIP_MODEL_H */ -- cgit v1.2.3 From 90aa1d3b7e822d60aa2437e6939651e55f02ffc4 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 1 Apr 2021 15:12:53 -0700 Subject: [interchange] Disallow site edges during general routing. This prevents the general router from routing through sites, which is not legal in FPGA interchange. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 27 ++++++++++++++++++++++----- fpga_interchange/arch.h | 1 + 2 files changed, 23 insertions(+), 5 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 45d35aa6..5b38a879 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -110,7 +110,7 @@ static std::string sha1_hash(const char *data, size_t size) return buf.str(); } -Arch::Arch(ArchArgs args) : args(args) +Arch::Arch(ArchArgs args) : args(args), disallow_site_routing(false) { try { blob_file.open(args.chipdb); @@ -870,6 +870,15 @@ bool Arch::route() std::string router = str_or_default(settings, id("router"), defaultRouter); + // Disallow site routing during general routing. This is because + // "prepare_sites_for_routing" has already assigned routing for all sites + // in the design, and if the router wants to route-thru a site, it *MUST* + // use a pseudo-pip. + // + // It is not legal in the FPGA interchange to enter a site and not + // terminate at a BEL pin. + disallow_site_routing = true; + bool result; if (router == "router1") { result = router1(getCtx(), Router1Cfg(getCtx())); @@ -880,6 +889,8 @@ bool Arch::route() log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str()); } + disallow_site_routing = false; + getCtx()->attrs[getCtx()->id("step")] = std::string("route"); archInfoToAttributes(); @@ -1717,10 +1728,6 @@ bool Arch::checkPipAvailForNet(PipId pip, NetInfo *net) const } if (pip_data.site != -1 && net != nullptr) { - // FIXME: This check isn't perfect. If a driver and sink are in the - // same site, it is possible for the router to route-thru the site - // ports without hitting a sink, which is not legal in the FPGA - // interchange. NPNR_ASSERT(net->driver.cell != nullptr); NPNR_ASSERT(net->driver.cell->bel != BelId()); @@ -1746,6 +1753,16 @@ bool Arch::checkPipAvailForNet(PipId pip, NetInfo *net) const } } + if(disallow_site_routing && !valid_pip) { + // For now, if driver is not part of this site, and + // disallow_site_routing is set, disallow the edge. + return false; + } + + // FIXME: This check isn't perfect. If a driver and sink are in the + // same site, it is possible for the router to route-thru the site + // ports without hitting a sink, which is not legal in the FPGA + // interchange. if (!valid_pip) { // See if one users can enter this site. if (dst_wire_data.site == -1) { diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 27d02a5f..0b1cfa43 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -1081,6 +1081,7 @@ struct Arch : ArchAPI Lookahead lookahead; mutable RouteNodeStorage node_storage; mutable SiteRoutingCache site_routing_cache; + bool disallow_site_routing; CellParameters cell_parameters; std::string chipdb_hash; -- cgit v1.2.3 From 9b82ded77ba80726acb9b846bdbc7d7b1e963ec6 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 1 Apr 2021 15:17:08 -0700 Subject: [interchange] Fix missing inline methods in site_arch.impl.h getBelPinWire and getBelPinType are marked as always inline, but were not defined in a header. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/site_arch.cc | 8 -------- fpga_interchange/site_arch.impl.h | 9 +++++++++ 2 files changed, 9 insertions(+), 8 deletions(-) diff --git a/fpga_interchange/site_arch.cc b/fpga_interchange/site_arch.cc index 9cf7fa0c..cdb627ca 100644 --- a/fpga_interchange/site_arch.cc +++ b/fpga_interchange/site_arch.cc @@ -271,14 +271,6 @@ SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site } } -SiteWire SiteArch::getBelPinWire(BelId bel, IdString pin) const -{ - WireId wire = ctx->getBelPinWire(bel, pin); - return SiteWire::make(site_info, wire); -} - -PortType SiteArch::getBelPinType(BelId bel, IdString pin) const { return ctx->getBelPinType(bel, pin); } - const char *SiteArch::nameOfWire(const SiteWire &wire) const { switch (wire.type) { diff --git a/fpga_interchange/site_arch.impl.h b/fpga_interchange/site_arch.impl.h index a471b690..3b9d282b 100644 --- a/fpga_interchange/site_arch.impl.h +++ b/fpga_interchange/site_arch.impl.h @@ -314,6 +314,15 @@ inline PhysicalNetlist::PhysNetlist::NetType SiteArch::prefered_constant_net_typ } } +inline SiteWire SiteArch::getBelPinWire(BelId bel, IdString pin) const +{ + WireId wire = ctx->getBelPinWire(bel, pin); + return SiteWire::make(site_info, wire); +} + +inline PortType SiteArch::getBelPinType(BelId bel, IdString pin) const { return ctx->getBelPinType(bel, pin); } + + NEXTPNR_NAMESPACE_END #endif /* SITE_ARCH_H */ -- cgit v1.2.3 From c11ad31393389e0a16d84c2934332ea3755de60c Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Thu, 1 Apr 2021 15:18:17 -0700 Subject: [interchange] Scale edge cost of pseudo pips. Previous pseudo pips were the same cost as regular pips, but this is definitely too fast, and meant that the router was prefering them. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 11 +++++++++++ fpga_interchange/arch.h | 6 +----- 2 files changed, 12 insertions(+), 5 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index 5b38a879..f9209922 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -1959,6 +1959,17 @@ void Arch::explain_bel_status(BelId bel) const site.explain(getCtx()); } +DelayQuad Arch::getPipDelay(PipId pip) const { + // FIXME: Implement when adding timing-driven place and route. + const auto & pip_data = pip_info(chip_info, pip); + + // Scale pseudo-pips by the number of wires they consume to make them + // more expensive than a single edge. This approximation exists soley to + // make the non-timing driven solution avoid thinking that pseudo-pips + // are the same cost as regular pips. + return DelayQuad(100*(1+pip_data.pseudo_cell_wires.size())); +} + // 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 0b1cfa43..a6ea70d8 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -622,11 +622,7 @@ struct Arch : ArchAPI return canonical_wire(chip_info, pip.tile, loc_info(chip_info, pip).pip_data[pip.index].dst_index); } - DelayQuad getPipDelay(PipId pip) const final - { - // FIXME: Implement when adding timing-driven place and route. - return DelayQuad(100); - } + DelayQuad getPipDelay(PipId pip) const final; DownhillPipRange getPipsDownhill(WireId wire) const final { -- cgit v1.2.3 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 From c2a6f6ce62b810b3250167052bf5559d1dae4130 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 2 Apr 2021 16:20:12 -0700 Subject: [interchange] Fix invalid use of local variables due to refactoring. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/site_arch.cc | 3 +++ fpga_interchange/site_arch.h | 3 +++ fpga_interchange/site_router.cc | 7 +------ 3 files changed, 7 insertions(+), 6 deletions(-) diff --git a/fpga_interchange/site_arch.cc b/fpga_interchange/site_arch.cc index cdb627ca..4438193b 100644 --- a/fpga_interchange/site_arch.cc +++ b/fpga_interchange/site_arch.cc @@ -269,6 +269,9 @@ SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site NPNR_ASSERT(result.second); } } + + blocking_net.name = ctx->id("$nextpnr_blocked_net"); + blocking_site_net.net = &blocking_net; } const char *SiteArch::nameOfWire(const SiteWire &wire) const diff --git a/fpga_interchange/site_arch.h b/fpga_interchange/site_arch.h index 91330aa0..a7da5c68 100644 --- a/fpga_interchange/site_arch.h +++ b/fpga_interchange/site_arch.h @@ -279,6 +279,9 @@ struct SiteArch HashTables::HashMap nets; HashTables::HashMap wire_to_nets; + NetInfo blocking_net; + SiteNetInfo blocking_site_net; + std::vector input_site_ports; std::vector output_site_ports; diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index aa82eca9..03d93ce3 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -1033,11 +1033,6 @@ 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; @@ -1056,7 +1051,7 @@ static void block_lut_outputs(SiteArch *site_arch, bel.index = bel_index; SiteWire lut_output_wire = site_arch->getBelPinWire(bel, bel_pin); - site_arch->bindWire(lut_output_wire, &blocking_site_net); + site_arch->bindWire(lut_output_wire, &site_arch->blocking_site_net); } } -- cgit v1.2.3 From 3200026e1f3b305d0d2e0d680eb9df94b9b326b8 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 2 Apr 2021 16:21:41 -0700 Subject: [interchange] Remove requirement to have wire_lut. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 6 ------ fpga_interchange/arch.h | 3 +++ fpga_interchange/pseudo_pip_model.cc | 4 ++++ 3 files changed, 7 insertions(+), 6 deletions(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index f9209922..f1eeae6e 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -285,12 +285,6 @@ Arch::Arch(ArchArgs args) : args(args), disallow_site_routing(false) } } - // There should be a cell that is a single input LUT. - // - // Note: This assumption may be not true, revisit if this becomes a - // problem. - NPNR_ASSERT(wire_lut != nullptr); - raw_bin_constant = std::regex("[01]+", std::regex_constants::ECMAScript | std::regex_constants::optimize); verilog_bin_constant = std::regex("([0-9]+)'b([01]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index a6ea70d8..e9c2802a 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -1065,6 +1065,9 @@ struct Arch : ArchAPI std::unordered_map lut_cells; // Of the LUT cells, which is used for wires? + // Note: May be null in arch's without wire LUT types. Assumption is + // that these arch's don't need wire LUT's because the LUT share is simple + // enough to avoid it. const LutCellPOD * wire_lut; std::regex raw_bin_constant; diff --git a/fpga_interchange/pseudo_pip_model.cc b/fpga_interchange/pseudo_pip_model.cc index c34e3de7..58b4a69b 100644 --- a/fpga_interchange/pseudo_pip_model.cc +++ b/fpga_interchange/pseudo_pip_model.cc @@ -363,6 +363,10 @@ void PseudoPipModel::update_site(const Context *ctx, size_t site) { cell.bel.tile = tile; cell.bel.index = bel_pair.first; + if(ctx->wire_lut == nullptr) { + continue; + } + cell.type = IdString(ctx->wire_lut->cell); NPNR_ASSERT(ctx->wire_lut->input_pins.size() == 1); cell.lut_cell.pins.push_back(IdString(ctx->wire_lut->input_pins[0])); -- cgit v1.2.3 From c43ad2fab6b35a4b9748ce4bb8807a8fe5205b0d Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Mon, 5 Apr 2021 10:10:11 -0700 Subject: Don't fail-fast for GH actions to allow for easier CI debugging. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- .github/workflows/interchange_ci.yml | 3 +++ 1 file changed, 3 insertions(+) diff --git a/.github/workflows/interchange_ci.yml b/.github/workflows/interchange_ci.yml index e72d7378..4c451c30 100644 --- a/.github/workflows/interchange_ci.yml +++ b/.github/workflows/interchange_ci.yml @@ -66,6 +66,9 @@ jobs: runs-on: ubuntu-latest needs: [Build-yosys, Build-nextpnr] strategy: + # Don't terminate jobs when one fails. This is important when + # debugging CI failures. + fail-fast: false matrix: device: [xc7a35t, xc7a100t, xc7a200t, xc7z010, LIFCL-17] steps: -- cgit v1.2.3 From ae2f7551c11ebf24c96b3ac8d1315ff648183a49 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 2 Apr 2021 16:23:29 -0700 Subject: [interchange] Provide estimateDelay when USE_LOOKAHEAD is not defined. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- fpga_interchange/arch.cc | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index f1eeae6e..aab73b4d 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -925,7 +925,22 @@ delay_t Arch::estimateDelay(WireId src, WireId dst) const #ifdef USE_LOOKAHEAD return lookahead.estimateDelay(getCtx(), src, dst); #else - return 0; + // Note: Something is better than nothing when USE_LOOKAHEAD is not + // defined. + int src_tile = src.tile == -1 ? chip_info->nodes[src.index].tile_wires[0].tile : src.tile; + int dst_tile = dst.tile == -1 ? chip_info->nodes[dst.index].tile_wires[0].tile : dst.tile; + + int src_x, src_y; + get_tile_x_y(src_tile, &src_x, &src_y); + + int dst_x, dst_y; + get_tile_x_y(dst_tile, &dst_x, &dst_y); + + delay_t base = 30 * std::min(std::abs(dst_x - src_x), 18) + 10 * std::max(std::abs(dst_x - src_x) - 18, 0) + + 60 * std::min(std::abs(dst_y - src_y), 6) + 20 * std::max(std::abs(dst_y - src_y) - 6, 0) + 300; + + base = (base * 3) / 2; + return base; #endif } -- cgit v1.2.3