diff options
Diffstat (limited to 'fpga_interchange/pseudo_pip_model.cc')
| -rw-r--r-- | fpga_interchange/pseudo_pip_model.cc | 474 |
1 files changed, 474 insertions, 0 deletions
diff --git a/fpga_interchange/pseudo_pip_model.cc b/fpga_interchange/pseudo_pip_model.cc new file mode 100644 index 00000000..58b4a69b --- /dev/null +++ b/fpga_interchange/pseudo_pip_model.cc @@ -0,0 +1,474 @@ +/* + * 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<size_t> sites; + std::vector<PseudoPipBel> 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<int32_t, int32_t> key{tile_type, pip_idx}; + std::vector<size_t> &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<int32_t> 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<size_t> &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<PseudoPipBel> &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<SiteRouter> & sites) { + // First determine which sites have placed cells, these sites are consider + // active. + HashTables::HashSet<size_t> 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<size_t> &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<int32_t> pseudo_pips_for_site = site_to_pseudo_pips.at(site); + + std::vector<int32_t> &unused_pseudo_pips = scratch; + unused_pseudo_pips.clear(); + unused_pseudo_pips.reserve(pseudo_pips_for_site.size()); + + HashTables::HashMap<int32_t, PseudoPipBel> 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<LutElement> &lut_elements = ctx->lut_elements.at(tile_type); + std::vector<LutMapper> 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<CellInfo> 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; + + 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])); + 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<uint32_t> 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<PseudoPipBel> & 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 |