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