diff options
28 files changed, 2251 insertions, 86 deletions
@@ -37,3 +37,7 @@ install_manifest.txt /ImportExecutables.cmake *-coverage/ *-coverage.info +*.netlist +*.phys +*.dcp +*.bit diff --git a/common/constraints.h b/common/constraints.h new file mode 100644 index 00000000..dfb108f8 --- /dev/null +++ b/common/constraints.h @@ -0,0 +1,65 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 The 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 CONSTRAINTS_H +#define CONSTRAINTS_H + +#ifndef NEXTPNR_H +#error Include after "nextpnr.h" only. +#endif + +#include "exclusive_state_groups.h" + +NEXTPNR_NAMESPACE_BEGIN + +template <size_t StateCount, typename StateType = int8_t, typename CountType = uint8_t> struct Constraints +{ + using ConstraintStateType = StateType; + using ConstraintCountType = CountType; + + enum ConstraintType + { + CONSTRAINT_TAG_IMPLIES = 0, + CONSTRAINT_TAG_REQUIRES = 1, + }; + + template <typename StateRange> struct Constraint + { + virtual size_t tag() const = 0; + virtual ConstraintType constraint_type() const = 0; + virtual StateType state() const = 0; + virtual StateRange states() const = 0; + }; + + typedef ExclusiveStateGroup<StateCount, StateType, CountType> TagState; + std::unordered_map<uint32_t, std::vector<typename TagState::Definition>> definitions; + + template <typename ConstraintRange> void bindBel(TagState *tags, const ConstraintRange constraints); + + template <typename ConstraintRange> void unbindBel(TagState *tags, const ConstraintRange constraints); + + template <typename ConstraintRange> + bool isValidBelForCellType(const Context *ctx, uint32_t prototype, const TagState *tags, + const ConstraintRange constraints, IdString object, IdString cell, BelId bel, + bool explain_constraints) const; +}; + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/common/constraints.impl.h b/common/constraints.impl.h new file mode 100644 index 00000000..9c978411 --- /dev/null +++ b/common/constraints.impl.h @@ -0,0 +1,109 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 The 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 CONSTRAINTS_IMPL_H +#define CONSTRAINTS_IMPL_H + +#include "exclusive_state_groups.impl.h" + +NEXTPNR_NAMESPACE_BEGIN + +template <size_t StateCount, typename StateType, typename CountType> +template <typename ConstraintRange> +void Constraints<StateCount, StateType, CountType>::bindBel(TagState *tags, const ConstraintRange constraints) +{ + for (const auto &constraint : constraints) { + switch (constraint.constraint_type()) { + case CONSTRAINT_TAG_IMPLIES: + tags[constraint.tag()].add_implies(constraint.state()); + break; + case CONSTRAINT_TAG_REQUIRES: + break; + default: + NPNR_ASSERT(false); + } + } +} + +template <size_t StateCount, typename StateType, typename CountType> +template <typename ConstraintRange> +void Constraints<StateCount, StateType, CountType>::unbindBel(TagState *tags, const ConstraintRange constraints) +{ + for (const auto &constraint : constraints) { + switch (constraint.constraint_type()) { + case CONSTRAINT_TAG_IMPLIES: + tags[constraint.tag()].remove_implies(constraint.state()); + break; + case CONSTRAINT_TAG_REQUIRES: + break; + default: + NPNR_ASSERT(false); + } + } +} + +template <size_t StateCount, typename StateType, typename CountType> +template <typename ConstraintRange> +bool Constraints<StateCount, StateType, CountType>::isValidBelForCellType(const Context *ctx, uint32_t prototype, + const TagState *tags, + const ConstraintRange constraints, + IdString object, IdString cell, BelId bel, + bool explain_constraints) const +{ + if (explain_constraints) { + auto &state_definition = definitions.at(prototype); + for (const auto &constraint : constraints) { + switch (constraint.constraint_type()) { + case CONSTRAINT_TAG_IMPLIES: + tags[constraint.tag()].explain_implies(ctx, object, cell, state_definition.at(constraint.tag()), bel, + constraint.state()); + break; + case CONSTRAINT_TAG_REQUIRES: + tags[constraint.tag()].explain_requires(ctx, object, cell, state_definition.at(constraint.tag()), bel, + constraint.states()); + break; + default: + NPNR_ASSERT(false); + } + } + } + + for (const auto &constraint : constraints) { + switch (constraint.constraint_type()) { + case CONSTRAINT_TAG_IMPLIES: + if (!tags[constraint.tag()].check_implies(constraint.state())) { + return false; + } + break; + case CONSTRAINT_TAG_REQUIRES: + if (!tags[constraint.tag()].requires(constraint.states())) { + return false; + } + break; + default: + NPNR_ASSERT(false); + } + } + + return true; +} + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/common/exclusive_state_groups.h b/common/exclusive_state_groups.h new file mode 100644 index 00000000..c9b0df66 --- /dev/null +++ b/common/exclusive_state_groups.h @@ -0,0 +1,148 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 The 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 EXCLUSIVE_STATE_GROUPS_H +#define EXCLUSIVE_STATE_GROUPS_H + +#ifndef NEXTPNR_H +#error Include after "nextpnr.h" only. +#endif + +#include "bits.h" + +NEXTPNR_NAMESPACE_BEGIN + +// Implementation for exclusive state groups, used to implement generic +// constraint system. +template <size_t StateCount, typename StateType = int8_t, typename CountType = uint8_t> struct ExclusiveStateGroup +{ + ExclusiveStateGroup() : state(kNoSelected) { count.fill(0); } + struct Definition + { + IdString prefix; + IdString default_state; + std::vector<IdString> states; + }; + + static_assert(StateCount < std::numeric_limits<StateType>::max(), "StateType cannot store max StateType"); + static_assert(std::numeric_limits<StateType>::is_signed, "StateType must be signed"); + + std::bitset<StateCount> selected_states; + StateType state; + std::array<CountType, StateCount> count; + + static constexpr StateType kNoSelected = -1; + static constexpr StateType kOverConstrained = -2; + + std::pair<bool, IdString> current_state(const Definition &definition) const + { + if (state <= 0) { + return std::make_pair(state == kNoSelected, definition.default_state); + } else { + NPNR_ASSERT(state <= definition.states.size()); + return std::make_pair(true, definition.states[state]); + } + } + + bool check_implies(int32_t next_state) const + { + // Implies can be satified if either that state is + // selected, or no state is currently selected. + return state == next_state || state == kNoSelected; + } + + bool add_implies(int32_t next_state) + { + NPNR_ASSERT(next_state < StateCount); + + // Increment and mark the state as selected. + count[next_state] += 1; + selected_states[next_state] = true; + + if (state == next_state) { + // State was already selected, state group is still satified. + return true; + } else if (selected_states.count() == 1) { + // State was not select selected, state is now selected. + // State group is satified. + state = next_state; + return true; + } else { + // State group is now overconstrained. + state = kOverConstrained; + return false; + } + }; + + void remove_implies(int32_t next_state) + { + NPNR_ASSERT(next_state < StateCount); + NPNR_ASSERT(selected_states[next_state]); + + count[next_state] -= 1; + NPNR_ASSERT(count[next_state] >= 0); + + // Check if next_state is now unselected. + if (count[next_state] == 0) { + // next_state is not longer selected + selected_states[next_state] = false; + + // Check whether the state group is now unselected or satified. + auto value = selected_states.to_ulong(); + auto number_selected = nextpnr::Bits::popcount(value); + if (number_selected == 1) { + // Group is no longer overconstrained. + state = nextpnr::Bits::ctz(value); + NPNR_ASSERT(selected_states[state]); + } else if (number_selected == 0) { + // Group is unselected. + state = kNoSelected; + } else { + state = kOverConstrained; + } + } + } + + template <typename StateRange> bool requires(const StateRange &state_range) const + { + if (state < 0) { + return false; + } + + for (const auto required_state : state_range) { + if (state == required_state) { + return true; + } + } + + return false; + } + + void print_debug(const Context *ctx, IdString object, const Definition &definition) const; + void explain_implies(const Context *ctx, IdString object, IdString cell, const Definition &definition, BelId bel, + int32_t next_state) const; + + template <typename StateRange> + void explain_requires(const Context *ctx, IdString object, IdString cell, const Definition &definition, BelId bel, + const StateRange state_range) const; +}; + +NEXTPNR_NAMESPACE_END + +#endif diff --git a/common/exclusive_state_groups.impl.h b/common/exclusive_state_groups.impl.h new file mode 100644 index 00000000..864e16c6 --- /dev/null +++ b/common/exclusive_state_groups.impl.h @@ -0,0 +1,96 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2021 The 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. + * + */ + +#pragma once + +#include "nextpnr.h" + +// This header must be included after "nextpnr.h", otherwise circular header +// import insanity occurs. +#ifndef NEXTPNR_H_COMPLETE +#error This header cannot be used until after "nextpnr.h" is included +#endif + +#include "log.h" + +NEXTPNR_NAMESPACE_BEGIN + +template <size_t StateCount, typename StateType, typename CountType> +void ExclusiveStateGroup<StateCount, StateType, CountType>::print_debug(const Context *ctx, IdString object, + const Definition &definition) const +{ + if (state == kNoSelected) { + NPNR_ASSERT(selected_states.count() == 0); + log_info("%s.%s is currently unselected\n", object.c_str(ctx), definition.prefix.c_str(ctx)); + } else if (state >= 0) { + log_info("%s.%s = %s, count = %d\n", object.c_str(ctx), definition.prefix.c_str(ctx), + definition.states[state].c_str(ctx), count[state]); + } else { + NPNR_ASSERT(state == kOverConstrained); + log_info("%s.%s is currently overconstrained, states selected:\n", object.c_str(ctx), + definition.prefix.c_str(ctx)); + for (size_t i = 0; i < definition.states.size(); ++i) { + if (selected_states[i]) { + log_info(" - %s, count = %d\n", definition.states[i].c_str(ctx), count[i]); + } + } + } +} + +template <size_t StateCount, typename StateType, typename CountType> +void ExclusiveStateGroup<StateCount, StateType, CountType>::explain_implies(const Context *ctx, IdString object, + IdString cell, const Definition &definition, + BelId bel, int32_t next_state) const +{ + if (check_implies(next_state)) { + log_info("Placing cell %s at bel %s does not violate %s.%s\n", cell.c_str(ctx), ctx->nameOfBel(bel), + object.c_str(ctx), definition.prefix.c_str(ctx)); + } else { + NPNR_ASSERT(next_state < definition.states.size()); + log_info("Placing cell %s at bel %s does violates %s.%s.\n", cell.c_str(ctx), ctx->nameOfBel(bel), + object.c_str(ctx), definition.prefix.c_str(ctx)); + print_debug(ctx, object, definition); + } +} + +template <size_t StateCount, typename StateType, typename CountType> +template <typename StateRange> +void ExclusiveStateGroup<StateCount, StateType, CountType>::explain_requires(const Context *ctx, IdString object, + IdString cell, + const Definition &definition, BelId bel, + const StateRange state_range) const +{ + if (requires(state_range)) { + log_info("Placing cell %s at bel %s does not violate %s.%s\n", cell.c_str(ctx), ctx->nameOfBel(bel), + object.c_str(ctx), definition.prefix.c_str(ctx)); + } else { + log_info("Placing cell %s at bel %s does violates %s.%s, because current state is %s, constraint requires one " + "of:\n", + cell.c_str(ctx), ctx->nameOfBel(bel), object.c_str(ctx), definition.prefix.c_str(ctx), + definition.states[state].c_str(ctx)); + + for (const auto required_state : state_range) { + NPNR_ASSERT(required_state < definition.states.size()); + log_info(" - %s\n", definition.states[required_state].c_str(ctx)); + } + print_debug(ctx, object, definition); + } +} + +NEXTPNR_NAMESPACE_END diff --git a/common/nextpnr.h b/common/nextpnr.h index 4ddf8fef..f2bcb90d 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -1559,4 +1559,6 @@ struct Context : Arch, DeterministicRNG NEXTPNR_NAMESPACE_END +#define NEXTPNR_H_COMPLETE + #endif diff --git a/common/util.h b/common/util.h index 07ebac75..55718344 100644 --- a/common/util.h +++ b/common/util.h @@ -158,6 +158,29 @@ inline NetInfo *get_net_or_empty(CellInfo *cell, const IdString port) return nullptr; } +// Get only value from a forward iterator begin/end pair. +// +// Generates assertion failure if std::distance(begin, end) != 1. +template <typename ForwardIterator> +inline const typename ForwardIterator::reference get_only_value(ForwardIterator begin, ForwardIterator end) +{ + NPNR_ASSERT(begin != end); + const typename ForwardIterator::reference ret = *begin; + ++begin; + NPNR_ASSERT(begin == end); + return ret; +} + +// Get only value from a forward iterator range pair. +// +// Generates assertion failure if std::distance(r.begin(), r.end()) != 1. +template <typename ForwardRange> inline auto get_only_value(ForwardRange r) +{ + auto b = r.begin(); + auto e = r.end(); + return get_only_value(b, e); +} + NEXTPNR_NAMESPACE_END #endif diff --git a/fpga_interchange/README.md b/fpga_interchange/README.md index d0c4f2bf..df832b94 100644 --- a/fpga_interchange/README.md +++ b/fpga_interchange/README.md @@ -36,28 +36,11 @@ library. The current implementation is missing essential features for place and route. As these features are added, this implementation will become more useful. - - [ ] Placement constraints are unimplemented, meaning invalid or unroutable - designs can be generated from the placer. - [ ] Logical netlist macro expansion is not implemented, meaning that any macro primitives are unplaceable. Common macro primitives examples are differential IO buffers (IBUFDS) and some LUT RAM (e.g. RAM64X1D). - - [ ] Cell -> BEL pin mapping is not in place, meaning any primitives that - have different BEL pins with respect to their cell pins will not be - routable. - - [ ] Nextpnr only allows for cell -> BEL pin maps that are 1 to 1. The - FPGA interchange accommodates cell -> BEL pin maps that include 1 to - many relationships for sinks. A common primitives that uses 1 to many - maps are the RAMB18E1. - [ ] The router lookahead is missing, meaning that router runtime performance will be terrible. - - [ ] Physical netlist backend is missing, so even if - `nextpnr-fpga_interchange` completes successfully, there is no way to - generate output that can be consumed by downstream tools. - - [ ] XDC parsing and port constraints are unimplemented, so IO pins cannot - be fixed. The chipdb BBA output is also missing package pin data, so - only site constraints are currently possible. Eventually the chipdb BBA - should also include package pin data to allow for ports to be bound to - package pins. - [ ] The routing graph that is currently emitted does not have ground and VCC networks, so all signals must currently be tied to an IO signal. Site pins being tied to constants also needs handling so that site @@ -72,6 +55,10 @@ As these features are added, this implementation will become more useful. database, so it is also currently missing from the FPGA interchange architecture. Once timing information is added to the device database schema, it needs to be added to the architecture. + - [ ] Implemented site router lacks important features for tight packing, + namely LUT rotation. Also the current site router is relatively + untested, so legal configurations may be rejected and illegal + configurations may be accepted. #### FPGA interchange fabrics @@ -80,6 +67,48 @@ device database generator, via [RapidWright](https://github.com/Xilinx/RapidWrig ##### Artix 35T example +Install capnproto if not already installed: +``` +# Or equivalent for your local system. +sudo apt-get install capnproto libcapnp-dev +``` + +Install capnproto-java if not already installed: +``` +git clone https://github.com/capnproto/capnproto-java.git +cd capnproto-java +make +sudo make install +``` + +##### Makefile-driven BBA creation + +In `${NEXTPNR_DIR}/fpga_interchange/examples/create_bba` is a Makefile that +should compile nextpnr and create a Xilinx A35 chipdb if java, capnproto and +capnproto-java are installed. + +Instructions: +``` +cd ${NEXTPNR_DIR}/fpga_interchange/examples/create_bba +make +``` + +This will create a virtual env in +`${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/env` that has the +python-fpga-interchange library installed. Before running the design examples, +enter the virtual env, e.g.: + +``` +source ${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/env/bin/activate +``` + +The chipdb will be written to `${NEXTPNR_DIR}/fpga_interchange/examples/create_bba/build/xc7a35.bin` +once completed. + +##### Manual BBA creation + +This covers the manual set of steps to create a Xilinx A35 chipdb. + Download RapidWright and generate the device database. ``` # FIXME: Use main branch once interchange branch is merged. @@ -95,7 +124,11 @@ mv rapidwright-api-lib-2020.2.1_update1.jar jars/rapidwright-api-lib-2020.2.0.ja ./scripts/invoke_rapidwright.sh com.xilinx.rapidwright.interchange.DeviceResourcesExample xc7a35tcpg236-1 export RAPIDWRIGHT_PATH=$(pwd) -export INTERCHANGE_DIR=$(pwd)/interchange +``` + +Set `INTERCHANGE_DIR` to point to 3rdparty/fpga-interchange-schema: +``` +export INTERCHANGE_DIR=$(NEXTPNR_DIR)/3rdparty/fpga-interchange-schema/interchange ``` Install python FPGA interchange library. @@ -130,7 +163,8 @@ Generate nextpnr BBA and constids.inc from device database: python3 -mfpga_interchange.nextpnr_emit \ --schema_dir ${INTERCHANGE_DIR} \ --output_dir ${NEXTPNR_DIR}/fpga_interchange/ \ - --device xc7a35tcpg236-1_constraints_luts.device + --bel_bucket_seeds test_data/series7_bel_buckets.yaml \ + --device xc7a35tcpg236-1_constraints_luts.device \ ``` Build nextpnr: diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index c24ec660..71ba46e4 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -25,6 +25,7 @@ #include <cmath> #include <cstring> #include <queue> +#include "constraints.impl.h" #include "fpga_interchange.h" #include "log.h" #include "nextpnr.h" @@ -89,11 +90,8 @@ Arch::Arch(ArchArgs args) : args(args) log_error("Unable to read chipdb %s\n", args.chipdb.c_str()); } - tileStatus.resize(chip_info->tiles.size()); - for (int i = 0; i < chip_info->tiles.ssize(); i++) { - tileStatus[i].boundcells.resize(chip_info->tile_types[chip_info->tiles[i].type].bel_data.size()); - } - + // Read strings from constids into IdString database, checking that list + // is unique and matches expected constid value. const RelSlice<RelPtr<char>> &constids = *chip_info->constids; for (size_t i = 0; i < constids.size(); ++i) { IdString::initialize_add(this, constids[i].get(), i + 1); @@ -149,12 +147,52 @@ Arch::Arch(ArchArgs args) : args(args) for (BelId bel : getBels()) { auto &bel_data = bel_info(chip_info, bel); - const SiteInstInfoPOD &site = chip_info->sites[chip_info->tiles[bel.tile].sites[bel_data.site]]; + const SiteInstInfoPOD &site = get_site_inst(bel); auto iter = site_bel_pads.find(SiteBelPair(site.site_name.get(), IdString(bel_data.name))); if (iter != site_bel_pads.end()) { pads.emplace(bel); } } + + explain_constraints = false; + + int tile_type_index = 0; + size_t max_tag_count = 0; + for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) { + max_tag_count = std::max(max_tag_count, tile_type.tags.size()); + + auto &type_definition = constraints.definitions[tile_type_index++]; + for (const ConstraintTagPOD &tag : tile_type.tags) { + type_definition.emplace_back(); + auto &definition = type_definition.back(); + definition.prefix = IdString(tag.tag_prefix); + definition.default_state = IdString(tag.default_state); + NPNR_ASSERT(tag.states.size() < kMaxState); + + definition.states.reserve(tag.states.size()); + for (auto state : tag.states) { + definition.states.push_back(IdString(state)); + } + } + + // Logic BELs (e.g. placable BELs) should always appear first in the + // bel data list. + // + // When iterating over BELs this property is depended on to skip + // non-placable BELs (e.g. routing BELs and site ports). + bool in_logic_bels = true; + for (const BelInfoPOD &bel_info : tile_type.bel_data) { + if (in_logic_bels && bel_info.category != BEL_CATEGORY_LOGIC) { + in_logic_bels = false; + } + + if (!in_logic_bels) { + NPNR_ASSERT(bel_info.category != BEL_CATEGORY_LOGIC); + } + } + } + + default_tags.resize(max_tag_count); } // ----------------------------------------------------------------------- @@ -470,7 +508,7 @@ IdStringList Arch::getPipName(PipId pip) const auto &pip_info = tile_type.pip_data[pip.index]; if (pip_info.site != -1) { // This is either a site pin or a site pip. - auto &site = chip_info->sites[tile.sites[pip_info.site]]; + auto &site = get_site_inst(pip); auto &bel = tile_type.bel_data[pip_info.bel]; IdString bel_name(bel.name); if (bel.category == BEL_CATEGORY_LOGIC) { @@ -563,20 +601,55 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay bool Arch::pack() { - // FIXME: Implement this - return false; + pack_ports(); + return true; } bool Arch::place() { - // FIXME: Implement this - return false; + std::string placer = str_or_default(settings, id("placer"), defaultPlacer); + + if (placer == "heap") { + PlacerHeapCfg cfg(getCtx()); + cfg.criticalityExponent = 7; + cfg.alpha = 0.08; + cfg.beta = 0.4; + cfg.placeAllAtOnce = true; + cfg.hpwl_scale_x = 1; + cfg.hpwl_scale_y = 2; + cfg.spread_scale_x = 2; + cfg.spread_scale_y = 1; + cfg.solverTolerance = 0.6e-6; + if (!placer_heap(getCtx(), cfg)) + return false; + } else if (placer == "sa") { + if (!placer1(getCtx(), Placer1Cfg(getCtx()))) + return false; + } else { + log_error("FPGA interchange architecture does not support placer '%s'\n", placer.c_str()); + } + + getCtx()->attrs[getCtx()->id("step")] = std::string("place"); + archInfoToAttributes(); + return true; } bool Arch::route() { - // FIXME: Implement this - return false; + std::string router = str_or_default(settings, id("router"), defaultRouter); + + bool result; + if (router == "router1") { + result = router1(getCtx(), Router1Cfg(getCtx())); + } else if (router == "router2") { + router2(getCtx(), Router2Cfg(getCtx())); + result = true; + } else { + log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str()); + } + getCtx()->attrs[getCtx()->id("step")] = std::string("route"); + archInfoToAttributes(); + return result; } // ----------------------------------------------------------------------- @@ -733,11 +806,8 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping) const void Arch::map_port_pins(BelId bel, CellInfo *cell) const { IdStringRange pins = getBelPins(bel); - NPNR_ASSERT(pins.begin() != pins.end()); - auto b = pins.begin(); - IdString pin = *b; - ++b; - NPNR_ASSERT(b == pins.end()); + IdString pin = get_only_value(pins); + NPNR_ASSERT(cell->ports.size() == 1); cell->cell_bel_pins[cell->ports.begin()->first].clear(); cell->cell_bel_pins[cell->ports.begin()->first].push_back(pin); @@ -771,4 +841,24 @@ bool Arch::is_net_within_site(const NetInfo &net) const return true; } +size_t Arch::get_cell_type_index(IdString cell_type) const +{ + const CellMapPOD &cell_map = *chip_info->cell_map; + int cell_offset = cell_type.index - cell_map.cell_names[0]; + if ((cell_offset < 0 || cell_offset >= cell_map.cell_names.ssize())) { + log_error("Cell %s is not a placable element.\n", cell_type.c_str(this)); + } + NPNR_ASSERT(cell_map.cell_names[cell_offset] == cell_type.index); + + return cell_offset; +} + +// 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); +template bool Arch::ArchConstraints::isValidBelForCellType(const Context *, uint32_t, + const Arch::ArchConstraints::TagState *, + const Arch::ConstraintRange, IdString, IdString, BelId, + bool) const; + NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 638855cd..76497d6d 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -28,6 +28,8 @@ #include <iostream> +#include "constraints.h" + NEXTPNR_NAMESPACE_BEGIN /**** Everything in this section must be kept in sync with chipdb.py ****/ @@ -251,6 +253,11 @@ inline const PipInfoPOD &pip_info(const ChipInfoPOD *chip_info, PipId pip) return loc_info(chip_info, pip).pip_data[pip.index]; } +inline const SiteInstInfoPOD &site_inst_info(const ChipInfoPOD *chip_info, int32_t tile, int32_t site) +{ + return chip_info->sites[chip_info->tiles[tile].sites[site]]; +} + struct BelIterator { const ChipInfoPOD *chip; @@ -654,7 +661,11 @@ struct BelPinRange BelPinIterator end() const { return e; } }; -struct IdStringIterator +struct IdStringIterator : std::iterator<std::forward_iterator_tag, + /*T=*/IdString, + /*Distance=*/ptrdiff_t, + /*pointer=*/IdString *, + /*reference=*/IdString> { const int32_t *cursor; @@ -751,12 +762,32 @@ struct Arch : ArchAPI<ArchRanges> std::unordered_map<WireId, std::pair<int, int>> driving_pip_loc; std::unordered_map<WireId, NetInfo *> reserved_wires; + static constexpr size_t kMaxState = 8; + + struct TileStatus; + struct SiteRouter + { + SiteRouter(int16_t site) : site(site), dirty(false), site_ok(true) {} + + std::unordered_set<CellInfo *> cells_in_site; + const int16_t site; + + mutable bool dirty; + mutable bool site_ok; + + void bindBel(CellInfo *cell); + void unbindBel(CellInfo *cell); + bool checkSiteRouting(const Context *ctx, const TileStatus &tile_status) const; + }; + struct TileStatus { + std::vector<ExclusiveStateGroup<kMaxState>> tags; std::vector<CellInfo *> boundcells; + std::vector<SiteRouter> sites; }; - std::vector<TileStatus> tileStatus; + std::unordered_map<int32_t, TileStatus> tileStatus; ArchArgs args; Arch(ArchArgs args); @@ -806,9 +837,7 @@ struct Arch : ArchAPI<ArchRanges> IdStringList getBelName(BelId bel) const override { NPNR_ASSERT(bel != BelId()); - int site_index = bel_info(chip_info, bel).site; - NPNR_ASSERT(site_index >= 0); - const SiteInstInfoPOD &site = chip_info->sites[chip_info->tiles[bel.tile].sites[site_index]]; + const SiteInstInfoPOD &site = get_site_inst(bel); std::array<IdString, 2> ids{id(site.name.get()), IdString(bel_info(chip_info, bel).name)}; return IdStringList(ids); } @@ -818,12 +847,39 @@ struct Arch : ArchAPI<ArchRanges> void map_cell_pins(CellInfo *cell, int32_t mapping) const; void map_port_pins(BelId bel, CellInfo *cell) const; + TileStatus &get_tile_status(int32_t tile) + { + 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.tags.resize(default_tags.size()); + + result.first->second.sites.reserve(tile_type.number_sites); + for (size_t i = 0; i < (size_t)tile_type.number_sites; ++i) { + result.first->second.sites.push_back(SiteRouter(i)); + } + } + + return result.first->second; + } + + const SiteRouter &get_site_status(const TileStatus &tile_status, const BelInfoPOD &bel_data) const + { + return tile_status.sites.at(bel_data.site); + } + + SiteRouter &get_site_status(TileStatus &tile_status, const BelInfoPOD &bel_data) + { + return tile_status.sites.at(bel_data.site); + } + void bindBel(BelId bel, CellInfo *cell, PlaceStrength strength) override { NPNR_ASSERT(bel != BelId()); - NPNR_ASSERT(tileStatus[bel.tile].boundcells[bel.index] == nullptr); - tileStatus[bel.tile].boundcells[bel.index] = cell; + TileStatus &tile_status = get_tile_status(bel.tile); + NPNR_ASSERT(tile_status.boundcells[bel.index] == nullptr); const auto &bel_data = bel_info(chip_info, bel); NPNR_ASSERT(bel_data.category == BEL_CATEGORY_LOGIC); @@ -835,36 +891,74 @@ struct Arch : ArchAPI<ArchRanges> if (cell->cell_mapping != mapping) { map_cell_pins(cell, mapping); } + constraints.bindBel(tile_status.tags.data(), get_cell_constraints(bel, cell->type)); } else { map_port_pins(bel, cell); + // FIXME: Probably need to actually constraint io port cell/bel, + // but the current BBA emission doesn't support that. This only + // really matters if the placer can choose IO port locations. } + + get_site_status(tile_status, bel_data).bindBel(cell); + + tile_status.boundcells[bel.index] = cell; + cell->bel = bel; cell->belStrength = strength; + refreshUiBel(bel); } void unbindBel(BelId bel) override { NPNR_ASSERT(bel != BelId()); - NPNR_ASSERT(tileStatus[bel.tile].boundcells[bel.index] != nullptr); - tileStatus[bel.tile].boundcells[bel.index]->bel = BelId(); - tileStatus[bel.tile].boundcells[bel.index]->belStrength = STRENGTH_NONE; - tileStatus[bel.tile].boundcells[bel.index] = nullptr; + + TileStatus &tile_status = get_tile_status(bel.tile); + NPNR_ASSERT(tile_status.boundcells[bel.index] != nullptr); + + CellInfo *cell = tile_status.boundcells[bel.index]; + tile_status.boundcells[bel.index] = nullptr; + + cell->bel = BelId(); + cell->belStrength = STRENGTH_NONE; + + // FIXME: Probably need to actually constraint io port cell/bel, + // but the current BBA emission doesn't support that. This only + // really matters if the placer can choose IO port locations. + if (io_port_types.count(cell->type) == 0) { + constraints.unbindBel(tile_status.tags.data(), get_cell_constraints(bel, cell->type)); + } + + const auto &bel_data = bel_info(chip_info, bel); + get_site_status(tile_status, bel_data).unbindBel(cell); + refreshUiBel(bel); } - bool checkBelAvail(BelId bel) const override { return tileStatus[bel.tile].boundcells[bel.index] == nullptr; } + bool checkBelAvail(BelId bel) const override + { + // FIXME: This could consult the constraint system to see if this BEL + // is blocked (e.g. site type is wrong). + return getBoundBelCell(bel) == nullptr; + } CellInfo *getBoundBelCell(BelId bel) const override { NPNR_ASSERT(bel != BelId()); - return tileStatus[bel.tile].boundcells[bel.index]; + auto iter = tileStatus.find(bel.tile); + if (iter == tileStatus.end()) { + return nullptr; + } else { + return iter->second.boundcells[bel.index]; + } } CellInfo *getConflictingBelCell(BelId bel) const override { NPNR_ASSERT(bel != BelId()); - return tileStatus[bel.tile].boundcells[bel.index]; + // FIXME: This could consult the constraint system to see why this BEL + // is blocked. + return getBoundBelCell(bel); } BelRange getBels() const override @@ -964,8 +1058,7 @@ struct Arch : ArchAPI<ArchRanges> if (wire.tile != -1) { const auto &tile_type = loc_info(chip_info, wire); if (tile_type.wire_data[wire.index].site != -1) { - int site_index = tile_type.wire_data[wire.index].site; - const SiteInstInfoPOD &site = chip_info->sites[chip_info->tiles[wire.tile].sites[site_index]]; + const SiteInstInfoPOD &site = get_site_inst(wire); std::array<IdString, 2> ids{id(site.name.get()), IdString(tile_type.wire_data[wire.index].name)}; return IdStringList(ids); } @@ -1251,6 +1344,9 @@ struct Arch : ArchAPI<ArchRanges> // ------------------------------------------------- + void place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels, + std::unordered_set<CellInfo *> *placed_cells); + void pack_ports(); bool pack() override; bool place() override; bool route() override; @@ -1315,15 +1411,7 @@ struct Arch : ArchAPI<ArchRanges> return BelBucketId(); } - size_t get_cell_type_index(IdString cell_type) const - { - const CellMapPOD &cell_map = *chip_info->cell_map; - int cell_offset = cell_type.index - cell_map.cell_names[0]; - NPNR_ASSERT(cell_offset >= 0 && cell_offset < cell_map.cell_names.ssize()); - NPNR_ASSERT(cell_map.cell_names[cell_offset] == cell_type.index); - - return cell_offset; - } + size_t get_cell_type_index(IdString cell_type) const; BelBucketId getBelBucketForCellType(IdString cell_type) const override { @@ -1352,16 +1440,57 @@ struct Arch : ArchAPI<ArchRanges> { if (io_port_types.count(cell_type)) { return pads.count(bel) > 0; - } else { - return bel_info(chip_info, bel).pin_map[get_cell_type_index(cell_type)] > 0; } + + const auto &bel_data = bel_info(chip_info, bel); + if (bel_data.category != BEL_CATEGORY_LOGIC) { + return false; + } + + auto cell_type_index = get_cell_type_index(cell_type); + return bel_data.pin_map[cell_type_index] != -1; + } + + bool is_cell_valid_constraints(const CellInfo *cell, const TileStatus &tile_status, bool explain) const + { + if (io_port_types.count(cell->type)) { + return true; + } + + BelId bel = cell->bel; + NPNR_ASSERT(bel != BelId()); + + return constraints.isValidBelForCellType(getCtx(), get_constraint_prototype(bel), tile_status.tags.data(), + get_cell_constraints(bel, cell->type), + id(chip_info->tiles[bel.tile].name.get()), cell->name, bel, explain); } // Return true whether all Bels at a given location are valid bool isBelLocationValid(BelId bel) const override { - // FIXME: Implement this - return true; + auto iter = tileStatus.find(bel.tile); + if (iter == tileStatus.end()) { + return true; + } + const TileStatus &tile_status = iter->second; + const CellInfo *cell = tile_status.boundcells[bel.index]; + if (cell == nullptr) { + return true; + } else { + if (io_port_types.count(cell->type)) { + // FIXME: Probably need to actually constraint io port cell/bel, + // but the current BBA emission doesn't support that. This only + // really matters if the placer can choose IO port locations. + return true; + } + + if (!is_cell_valid_constraints(cell, tile_status, explain_constraints)) { + return false; + } + + auto &bel_data = bel_info(chip_info, bel); + return get_site_status(tile_status, bel_data).checkSiteRouting(getCtx(), tile_status); + } } IdString get_bel_tiletype(BelId bel) const { return IdString(loc_info(chip_info, bel).name); } @@ -1406,6 +1535,123 @@ struct Arch : ArchAPI<ArchRanges> // // Returns false if any element of the net is not placed. bool is_net_within_site(const NetInfo &net) const; + + using ArchConstraints = Constraints<kMaxState>; + ArchConstraints constraints; + std::vector<ArchConstraints::TagState> default_tags; + bool explain_constraints; + + struct StateRange + { + const int32_t *b; + const int32_t *e; + + const int32_t *begin() const { return b; } + const int32_t *end() const { return e; } + }; + + struct Constraint : ArchConstraints::Constraint<StateRange> + { + const CellConstraintPOD *constraint; + Constraint(const CellConstraintPOD *constraint) : constraint(constraint) {} + + size_t tag() const override { return constraint->tag; } + + ArchConstraints::ConstraintType constraint_type() const override + { + return Constraints<kMaxState>::ConstraintType(constraint->constraint_type); + } + + ArchConstraints::ConstraintStateType state() const override + { + NPNR_ASSERT(constraint_type() == Constraints<kMaxState>::CONSTRAINT_TAG_IMPLIES); + NPNR_ASSERT(constraint->states.size() == 1); + return constraint->states[0]; + } + + StateRange states() const override + { + StateRange range; + range.b = constraint->states.get(); + range.e = range.b + constraint->states.size(); + + return range; + } + }; + + struct ConstraintIterator + { + const CellConstraintPOD *constraint; + ConstraintIterator() {} + + ConstraintIterator operator++() + { + ++constraint; + return *this; + } + + bool operator!=(const ConstraintIterator &other) const { return constraint != other.constraint; } + + bool operator==(const ConstraintIterator &other) const { return constraint == other.constraint; } + + Constraint operator*() const { return Constraint(constraint); } + }; + + struct ConstraintRange + { + ConstraintIterator b, e; + + ConstraintIterator begin() const { return b; } + ConstraintIterator end() const { return e; } + }; + + uint32_t get_constraint_prototype(BelId bel) const { return chip_info->tiles[bel.tile].type; } + + ConstraintRange get_cell_constraints(BelId bel, IdString cell_type) const + { + const auto &bel_data = bel_info(chip_info, bel); + NPNR_ASSERT(bel_data.category == BEL_CATEGORY_LOGIC); + + int32_t mapping = bel_data.pin_map[get_cell_type_index(cell_type)]; + NPNR_ASSERT(mapping >= 0); + + auto &cell_bel_map = chip_info->cell_map->cell_bel_map[mapping]; + ConstraintRange range; + range.b.constraint = cell_bel_map.constraints.get(); + range.e.constraint = range.b.constraint + cell_bel_map.constraints.size(); + + return range; + } + + const char *get_site_name(int32_t tile, size_t site) const + { + return site_inst_info(chip_info, tile, site).name.get(); + } + + const char *get_site_name(BelId bel) const + { + auto &bel_data = bel_info(chip_info, bel); + return get_site_name(bel.tile, bel_data.site); + } + + const SiteInstInfoPOD &get_site_inst(BelId bel) const + { + auto &bel_data = bel_info(chip_info, bel); + return site_inst_info(chip_info, bel.tile, bel_data.site); + } + + const SiteInstInfoPOD &get_site_inst(WireId wire) const + { + auto &wire_data = wire_info(wire); + NPNR_ASSERT(wire_data.site != -1); + return site_inst_info(chip_info, wire.tile, wire_data.site); + } + + const SiteInstInfoPOD &get_site_inst(PipId pip) const + { + auto &pip_data = pip_info(chip_info, pip); + return site_inst_info(chip_info, pip.tile, pip_data.site); + } }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/arch_pack_io.cc b/fpga_interchange/arch_pack_io.cc new file mode 100644 index 00000000..6a0ffe0b --- /dev/null +++ b/fpga_interchange/arch_pack_io.cc @@ -0,0 +1,251 @@ +/* + * 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 "log.h" +#include "nextpnr.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +void Arch::place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels, + std::unordered_set<CellInfo *> *placed_cells) +{ + for (BelPin bel_pin : getWireBelPins(pad_wire)) { + BelId bel = bel_pin.bel; + for (CellInfo *cell : tightly_attached_bels) { + if (isValidBelForCellType(cell->type, bel)) { + NPNR_ASSERT(cell->bel == BelId()); + NPNR_ASSERT(placed_cells->count(cell) == 0); + + bindBel(bel, cell, STRENGTH_FIXED); + placed_cells->emplace(cell); + + IdString cell_port; + for (auto pin_pair : cell->cell_bel_pins) { + for (IdString a_bel_pin : pin_pair.second) { + if (a_bel_pin == bel_pin.pin) { + NPNR_ASSERT(cell_port == IdString()); + cell_port = pin_pair.first; + } + } + } + NPNR_ASSERT(cell_port != IdString()); + + const PortInfo &port = cell->ports.at(cell_port); + NPNR_ASSERT(port.net == net); + } + } + } +} + +void Arch::pack_ports() +{ + std::unordered_map<IdString, const TileInstInfoPOD *> tile_type_prototypes; + for (size_t i = 0; i < chip_info->tiles.size(); ++i) { + const auto &tile = chip_info->tiles[i]; + const auto &tile_type = chip_info->tile_types[tile.type]; + IdString tile_type_name(tile_type.name); + tile_type_prototypes.emplace(tile_type_name, &tile); + } + + // set(site_types) for package pins + std::unordered_set<IdString> package_sites; + // Package pin -> (Site type -> BelId) + std::unordered_map<IdString, std::vector<std::pair<IdString, BelId>>> package_pin_bels; + for (const PackagePinPOD &package_pin : chip_info->packages[package_index].pins) { + IdString pin(package_pin.package_pin); + IdString bel(package_pin.bel); + + IdString site(package_pin.site); + package_sites.emplace(site); + + for (size_t i = 0; i < chip_info->tiles.size(); ++i) { + const auto &tile = chip_info->tiles[i]; + std::unordered_set<uint32_t> package_pin_sites; + for (size_t j = 0; j < tile.sites.size(); ++j) { + auto &site_data = chip_info->sites[tile.sites[j]]; + if (site == id(site_data.site_name.get())) { + package_pin_sites.emplace(j); + } + } + + const auto &tile_type = chip_info->tile_types[tile.type]; + for (size_t j = 0; j < tile_type.bel_data.size(); ++j) { + const BelInfoPOD &bel_data = tile_type.bel_data[j]; + if (bel == IdString(bel_data.name) && package_pin_sites.count(bel_data.site)) { + auto &site_data = chip_info->sites[tile.sites[bel_data.site]]; + IdString site_type(site_data.site_type); + BelId bel; + bel.tile = i; + bel.index = j; + package_pin_bels[pin].push_back(std::make_pair(site_type, bel)); + } + } + } + } + + // Determine for each package site type, which site types are possible. + std::unordered_set<IdString> package_pin_site_types; + std::unordered_map<IdString, std::unordered_set<IdString>> possible_package_site_types; + for (const TileInstInfoPOD &tile : chip_info->tiles) { + for (size_t site_index : tile.sites) { + const SiteInstInfoPOD &site = chip_info->sites[site_index]; + IdString site_name = getCtx()->id(site.site_name.get()); + if (package_sites.count(site_name) == 1) { + possible_package_site_types[site_name].emplace(IdString(site.site_type)); + package_pin_site_types.emplace(IdString(site.site_type)); + } + } + } + + // IO sites are usually pretty weird, so see if we can define some + // constraints between the port cell create by nextpnr and cells that are + // immediately attached to that port cell. + for (auto port_pair : port_cells) { + IdString port_name = port_pair.first; + CellInfo *port_cell = port_pair.second; + std::unordered_set<CellInfo *> tightly_attached_bels; + + for (auto port_pair : port_cell->ports) { + const PortInfo &port_info = port_pair.second; + const NetInfo *net = port_info.net; + if (net->driver.cell) { + tightly_attached_bels.emplace(net->driver.cell); + } + + for (const PortRef &port_ref : net->users) { + if (port_ref.cell) { + tightly_attached_bels.emplace(port_ref.cell); + } + } + } + + if (getCtx()->verbose) { + log_info("Tightly attached BELs for port %s\n", port_name.c_str(getCtx())); + for (CellInfo *cell : tightly_attached_bels) { + log_info(" - %s : %s\n", cell->name.c_str(getCtx()), cell->type.c_str(getCtx())); + } + } + + NPNR_ASSERT(tightly_attached_bels.erase(port_cell) == 1); + std::unordered_set<IdString> cell_types_in_io_group; + for (CellInfo *cell : tightly_attached_bels) { + NPNR_ASSERT(port_cells.find(cell->name) == port_cells.end()); + cell_types_in_io_group.emplace(cell->type); + } + + // Get possible placement locations for tightly coupled BELs with + // port. + std::unordered_set<IdString> possible_site_types; + for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) { + IdString tile_type_name(tile_type.name); + for (const BelInfoPOD &bel_info : tile_type.bel_data) { + if (bel_info.category != BEL_CATEGORY_LOGIC) { + break; + } + + for (IdString cell_type : cell_types_in_io_group) { + size_t cell_type_index = get_cell_type_index(cell_type); + if (bel_info.category == BEL_CATEGORY_LOGIC && bel_info.pin_map[cell_type_index] != -1) { + auto *tile = tile_type_prototypes.at(tile_type_name); + const SiteInstInfoPOD &site = chip_info->sites[tile->sites[bel_info.site]]; + + IdString site_type(site.site_type); + if (package_pin_site_types.count(site_type)) { + possible_site_types.emplace(site_type); + } + } + } + } + } + + if (possible_site_types.empty()) { + log_error("Port '%s' has no possible site types!\n", port_name.c_str(getCtx())); + } + + if (getCtx()->verbose) { + log_info("Possible site types for port %s\n", port_name.c_str(getCtx())); + for (IdString site_type : possible_site_types) { + log_info(" - %s\n", site_type.c_str(getCtx())); + } + } + + auto iter = port_cell->attrs.find(id("PACKAGE_PIN")); + if (iter == port_cell->attrs.end()) { + // FIXME: Relax this constraint + log_error("Port '%s' is missing PACKAGE_PIN property\n", port_cell->name.c_str(getCtx())); + } + + // std::unordered_map<IdString, std::unordered_map<IdString, BelId>> package_pin_bels; + IdString package_pin_id = id(iter->second.as_string()); + auto pin_iter = package_pin_bels.find(package_pin_id); + if (pin_iter == package_pin_bels.end()) { + log_error("Package pin '%s' not found in part %s\n", package_pin_id.c_str(getCtx()), get_part().c_str()); + } + NPNR_ASSERT(pin_iter != package_pin_bels.end()); + + // Select the first BEL from package_bel_pins that is a legal site + // type. + // + // This is likely the most generic (versus specialized) site type. + BelId package_bel; + for (auto site_type_and_bel : pin_iter->second) { + IdString legal_site_type = site_type_and_bel.first; + BelId bel = site_type_and_bel.second; + + if (possible_site_types.count(legal_site_type)) { + // FIXME: Need to handle case where a port can be in multiple + // modes, but only one of the modes works. + package_bel = bel; + break; + } + } + + if (package_bel == BelId()) { + log_info("Failed to find BEL for package pin '%s' in any possible site types:\n", + package_pin_id.c_str(getCtx())); + for (IdString site_type : possible_site_types) { + log_info(" - %s\n", site_type.c_str(getCtx())); + } + log_error("Failed to find BEL for package pin '%s'\n", package_pin_id.c_str(getCtx())); + } + + if (getCtx()->verbose) { + log_info("Binding port %s to BEL %s\n", port_name.c_str(getCtx()), getCtx()->nameOfBel(package_bel)); + } + + std::unordered_set<CellInfo *> placed_cells; + bindBel(package_bel, port_cell, STRENGTH_FIXED); + placed_cells.emplace(port_cell); + + IdStringRange package_bel_pins = getBelPins(package_bel); + IdString pad_pin = get_only_value(package_bel_pins); + + WireId pad_wire = getBelPinWire(package_bel, pad_pin); + place_iobufs(pad_wire, ports[port_pair.first].net, tightly_attached_bels, &placed_cells); + + for (CellInfo *cell : placed_cells) { + NPNR_ASSERT(cell->bel != BelId()); + NPNR_ASSERT(isBelLocationValid(cell->bel)); + } + } +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/examples/archcheck/Makefile b/fpga_interchange/examples/archcheck/Makefile new file mode 100644 index 00000000..cf82013b --- /dev/null +++ b/fpga_interchange/examples/archcheck/Makefile @@ -0,0 +1,16 @@ +include ../common.mk + +PACKAGE := csg324 + +.PHONY: check check_test_data + +check: check_test_data + $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --package $(PACKAGE) \ + --test + +check_test_data: + $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --run $(NEXTPNR_PATH)/python/check_arch_api.py diff --git a/fpga_interchange/examples/archcheck/test_data.yaml b/fpga_interchange/examples/archcheck/test_data.yaml new file mode 100644 index 00000000..b41112cf --- /dev/null +++ b/fpga_interchange/examples/archcheck/test_data.yaml @@ -0,0 +1,7 @@ +pip_test: + - src_wire: CLBLM_R_X11Y93/CLBLM_L_D3 + dst_wire: SLICE_X15Y93.SLICEL/D3 +bel_pin_test: + - bel: SLICE_X15Y93.SLICEL/D6LUT + pin: A3 + wire: SLICE_X15Y93.SLICEL/D3 diff --git a/fpga_interchange/examples/common.mk b/fpga_interchange/examples/common.mk new file mode 100644 index 00000000..ce558472 --- /dev/null +++ b/fpga_interchange/examples/common.mk @@ -0,0 +1,8 @@ +NEXTPNR_PATH := $(realpath ../../..) +NEXTPNR_BIN := $(NEXTPNR_PATH)/build/nextpnr-fpga_interchange +BBA_PATH := $(realpath ..)/create_bba/build/xc7a35.bin + +RAPIDWRIGHT_PATH := $(realpath ..)/create_bba/build/RapidWright +INTERCHANGE_PATH := $(realpath ..)/create_bba/build/fpga-interchange-schema/interchange + +DEVICE := $(realpath ..)/create_bba/build/python-fpga-interchange/xc7a35tcpg236-1_constraints_luts.device diff --git a/fpga_interchange/examples/create_bba/Makefile b/fpga_interchange/examples/create_bba/Makefile new file mode 100644 index 00000000..3033daca --- /dev/null +++ b/fpga_interchange/examples/create_bba/Makefile @@ -0,0 +1,91 @@ +# +# 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. + + +# This Makefile provides a streamlined way to create an example +# FPGA interchange BBA suitable for placing and routing on Xilinx A35 parts. +# +# FPGA interchange device database is generated via RapidWright. +# +# Currently FPGA interchange physical netlist (e.g. place and route route) to +# FASM support is not done, so bitstream generation relies on RapidWright to +# convert FPGA interchange logical and physical netlist into a Vivado DCP. + +include ../common.mk + +.DELETE_ON_ERROR: + +.PHONY: all chipdb + +all: chipdb + +build: + mkdir build + +build/RapidWright: | build + # FIXME: Update URL / branch as fixes are merged upstream and / or + # interchange branch on Xilinx/RapidWright is merged to master branch. + # + #cd build && git clone -b interchange https://github.com/Xilinx/RapidWright.git + cd build && git clone -b move_strlist https://github.com/litghost/RapidWright.git + +build/env: | build + python3 -mvenv build/env + +build/python-fpga-interchange: | build + cd build && git clone https://github.com/SymbiFlow/python-fpga-interchange.git + +build/fpga-interchange-schema: | build + cd build && git clone https://github.com/SymbiFlow/fpga-interchange-schema.git + +build/.setup: | build/env build/fpga-interchange-schema build/python-fpga-interchange build/RapidWright + source build/env/bin/activate && \ + cd build/python-fpga-interchange/ && \ + pip install -r requirements.txt + touch build/.setup + +$(NEXTPNR_PATH)/build: + mkdir $(NEXTPNR_PATH)/build + +$(NEXTPNR_PATH)/build/bba/bbasm: | $(NEXTPNR_PATH)/build + cd $(NEXTPNR_PATH)/build && cmake -DARCH=fpga_interchange .. + make -j -C $(NEXTPNR_PATH)/build + +$(NEXTPNR_PATH)/fpga_interchange/chipdb.bba: build/.setup + mkdir -p build/nextpnr/fpga_interchange + source build/env/bin/activate && \ + cd build/python-fpga-interchange/ && \ + make \ + -f Makefile.rapidwright \ + NEXTPNR_PATH=$(realpath .)/build/nextpnr \ + RAPIDWRIGHT_PATH=$(RAPIDWRIGHT_PATH) \ + INTERCHANGE_PATH=$(INTERCHANGE_PATH) + +$(BBA_PATH): $(NEXTPNR_PATH)/build/bba/bbasm $(NEXTPNR_PATH)/fpga_interchange/chipdb.bba + $(NEXTPNR_PATH)/build/bba/bbasm -l build/nextpnr/fpga_interchange/chipdb.bba $(BBA_PATH) + +chipdb: $(BBA_PATH) + +test: chipdb + $(NEXTPNR_PATH)/build/nextpnr-fpga_interchange \ + --chipdb $(BBA_PATH) \ + --package csg324 \ + --test + +clean: + rm -rf build diff --git a/fpga_interchange/examples/create_bba/README.md b/fpga_interchange/examples/create_bba/README.md new file mode 100644 index 00000000..d2ca5188 --- /dev/null +++ b/fpga_interchange/examples/create_bba/README.md @@ -0,0 +1,40 @@ +## Makefile-driven BBA creation + +This Makefile will generate a Xilinx A35 chipdb if java, capnproto and +capnproto-java are installed. + +### Installing dependencies + +Install java and javac if not already installed: +``` +# Or equivalent for your local system. +sudo apt-get install openjdk-10-jdk +``` + +Install capnproto if not already installed: +``` +# Or equivalent for your local system. +sudo apt-get install capnproto libcapnp-dev +``` + +Install capnproto-java if not already installed: +``` +git clone https://github.com/capnproto/capnproto-java.git +cd capnproto-java +make +sudo make install +``` + +### Instructions + +Once dependencies are installed, just run "make". This should download +remaining dependencies and build the chipdb and build nextpnr if not built. + +#### Re-building the chipdb + +``` +# Remove the text BBA +rm build/nextpnr/fpga_interchange/chipdb.bba +# Build the BBA +make +``` diff --git a/fpga_interchange/examples/lut/Makefile b/fpga_interchange/examples/lut/Makefile new file mode 100644 index 00000000..54fc8994 --- /dev/null +++ b/fpga_interchange/examples/lut/Makefile @@ -0,0 +1,8 @@ +DESIGN := lut +DESIGN_TOP := top +PACKAGE := csg324 + +include ../template.mk + +build/lut.json: lut.v | build + yosys -c run.tcl diff --git a/fpga_interchange/examples/lut/lut.v b/fpga_interchange/examples/lut/lut.v new file mode 100644 index 00000000..ca18e665 --- /dev/null +++ b/fpga_interchange/examples/lut/lut.v @@ -0,0 +1,5 @@ +module top(input i0, input i1, output o); + +assign o = i0 | i1; + +endmodule diff --git a/fpga_interchange/examples/lut/lut.xdc b/fpga_interchange/examples/lut/lut.xdc new file mode 100644 index 00000000..4f390f25 --- /dev/null +++ b/fpga_interchange/examples/lut/lut.xdc @@ -0,0 +1,7 @@ +set_property PACKAGE_PIN N16 [get_ports i0] +set_property PACKAGE_PIN N15 [get_ports i1] +set_property PACKAGE_PIN M17 [get_ports o] + +set_property IOSTANDARD LVCMOS33 [get_ports i0] +set_property IOSTANDARD LVCMOS33 [get_ports i1] +set_property IOSTANDARD LVCMOS33 [get_ports o] diff --git a/fpga_interchange/examples/lut/run.tcl b/fpga_interchange/examples/lut/run.tcl new file mode 100644 index 00000000..1edd8bb7 --- /dev/null +++ b/fpga_interchange/examples/lut/run.tcl @@ -0,0 +1,14 @@ +yosys -import + +read_verilog lut.v + +synth_xilinx -nolutram -nowidelut -nosrl -nocarry -nodsp + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json build/lut.json diff --git a/fpga_interchange/examples/template.mk b/fpga_interchange/examples/template.mk new file mode 100644 index 00000000..819cdb1f --- /dev/null +++ b/fpga_interchange/examples/template.mk @@ -0,0 +1,64 @@ +include ../common.mk + +.DELETE_ON_ERROR: +.PHONY: all debug clean netlist_yaml phys_yaml + +all: build/$(DESIGN).dcp + +build: + mkdir build + +build/$(DESIGN).netlist: build/$(DESIGN).json + /usr/bin/time -v python3 -mfpga_interchange.yosys_json \ + --schema_dir $(INTERCHANGE_PATH) \ + --device $(DEVICE) \ + --top $(DESIGN_TOP) \ + build/$(DESIGN).json \ + build/$(DESIGN).netlist + +build/$(DESIGN)_netlist.yaml: build/$(DESIGN).netlist + /usr/bin/time -v python3 -mfpga_interchange.convert \ + --schema_dir $(INTERCHANGE_PATH) \ + --schema logical \ + --input_format capnp \ + --output_format yaml \ + build/$(DESIGN).netlist \ + build/$(DESIGN)_netlist.yaml + +netlist_yaml: build/$(DESIGN)_netlist.yaml + +build/$(DESIGN).phys: build/$(DESIGN).netlist + $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --xdc $(DESIGN).xdc \ + --netlist build/$(DESIGN).netlist \ + --phys build/$(DESIGN).phys \ + --package $(PACKAGE) \ + +build/$(DESIGN)_phys.yaml: build/$(DESIGN).phys + /usr/bin/time -v python3 -mfpga_interchange.convert \ + --schema_dir $(INTERCHANGE_PATH) \ + --schema physical \ + --input_format capnp \ + --output_format yaml \ + build/$(DESIGN).phys \ + build/$(DESIGN)_phys.yaml + +phys_yaml: build/$(DESIGN)_phys.yaml + +debug: build/$(DESIGN).netlist + gdb --args $(NEXTPNR_BIN) \ + --chipdb $(BBA_PATH) \ + --xdc $(DESIGN).xdc \ + --netlist build/$(DESIGN).netlist \ + --phys build/$(DESIGN).phys \ + --package $(PACKAGE) + +build/$(DESIGN).dcp: build/$(DESIGN).netlist build/$(DESIGN).phys $(DESIGN).xdc + RAPIDWRIGHT_PATH=$(RAPIDWRIGHT_PATH) \ + $(RAPIDWRIGHT_PATH)/scripts/invoke_rapidwright.sh \ + com.xilinx.rapidwright.interchange.PhysicalNetlistToDcp \ + build/$(DESIGN).netlist build/$(DESIGN).phys $(DESIGN).xdc build/$(DESIGN).dcp + +clean: + rm -rf build diff --git a/fpga_interchange/examples/wire/Makefile b/fpga_interchange/examples/wire/Makefile new file mode 100644 index 00000000..49194f53 --- /dev/null +++ b/fpga_interchange/examples/wire/Makefile @@ -0,0 +1,8 @@ +DESIGN := wire +DESIGN_TOP := top +PACKAGE := csg324 + +include ../template.mk + +build/wire.json: wire.v | build + yosys -c run.tcl diff --git a/fpga_interchange/examples/wire/run.tcl b/fpga_interchange/examples/wire/run.tcl new file mode 100644 index 00000000..9127be20 --- /dev/null +++ b/fpga_interchange/examples/wire/run.tcl @@ -0,0 +1,14 @@ +yosys -import + +read_verilog wire.v + +synth_xilinx -nolutram -nowidelut -nosrl -nocarry -nodsp + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json build/wire.json diff --git a/fpga_interchange/examples/wire/wire.v b/fpga_interchange/examples/wire/wire.v new file mode 100644 index 00000000..429d05ff --- /dev/null +++ b/fpga_interchange/examples/wire/wire.v @@ -0,0 +1,5 @@ +module top(input i, output o); + +assign o = i; + +endmodule diff --git a/fpga_interchange/examples/wire/wire.xdc b/fpga_interchange/examples/wire/wire.xdc new file mode 100644 index 00000000..e1fce5f0 --- /dev/null +++ b/fpga_interchange/examples/wire/wire.xdc @@ -0,0 +1,2 @@ +set_property PACKAGE_PIN N16 [get_ports i] +set_property PACKAGE_PIN N15 [get_ports o] diff --git a/fpga_interchange/fpga_interchange.cpp b/fpga_interchange/fpga_interchange.cpp index 98580261..566524b6 100644 --- a/fpga_interchange/fpga_interchange.cpp +++ b/fpga_interchange/fpga_interchange.cpp @@ -37,7 +37,7 @@ static void write_message(::capnp::MallocMessageBuilder & message, const std::st gzFile file = gzopen(filename.c_str(), "w"); NPNR_ASSERT(file != Z_NULL); - NPNR_ASSERT(gzwrite(file, &bytes[0], bytes.size()) == bytes.size()); + NPNR_ASSERT(gzwrite(file, &bytes[0], bytes.size()) == (int)bytes.size()); NPNR_ASSERT(gzclose(file) == Z_OK); } @@ -59,6 +59,7 @@ struct StringEnumerator { static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( const Context * ctx, StringEnumerator * strings, + const std::unordered_map<PipId, PlaceStrength> &pip_place_strength, PipId pip, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { const PipInfoPOD & pip_data = pip_info(ctx->chip_info, pip); @@ -67,8 +68,8 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( if(pip_data.site == -1) { // This is a PIP - auto pip = branch.getRouteSegment().initPip(); - pip.setTile(strings->get_index(tile.name.get())); + auto pip_obj = branch.getRouteSegment().initPip(); + pip_obj.setTile(strings->get_index(tile.name.get())); // FIXME: This might be broken for reverse bi-pips. Re-visit this one. // @@ -81,9 +82,10 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( // IdString src_wire_name = IdString(tile_type.wire_data[pip_data.src_index].name); IdString dst_wire_name = IdString(tile_type.wire_data[pip_data.dst_index].name); - pip.setWire0(strings->get_index(src_wire_name.str(ctx))); - pip.setWire1(strings->get_index(dst_wire_name.str(ctx))); - pip.setForward(true); + pip_obj.setWire0(strings->get_index(src_wire_name.str(ctx))); + pip_obj.setWire1(strings->get_index(dst_wire_name.str(ctx))); + pip_obj.setForward(true); + pip_obj.setIsFixed(pip_place_strength.at(pip) >= STRENGTH_FIXED); return branch; } else { @@ -129,6 +131,7 @@ static PhysicalNetlist::PhysNetlist::RouteBranch::Builder emit_branch( site_pip.setSite(site_idx); site_pip.setBel(strings->get_index(pip_name[1].str(ctx))); site_pip.setPin(strings->get_index(pip_name[2].str(ctx))); + site_pip.setIsFixed(pip_place_strength.at(pip) >= STRENGTH_FIXED); // FIXME: Mark inverter state. // This is required for US/US+ inverters, because those inverters @@ -207,6 +210,7 @@ static void emit_net( const std::unordered_map<WireId, std::vector<PipId>> &pip_downhill, const std::unordered_map<WireId, std::vector<BelPin>> &sinks, std::unordered_set<PipId> *pips, + const std::unordered_map<PipId, PlaceStrength> &pip_place_strength, WireId wire, PhysicalNetlist::PhysNetlist::RouteBranch::Builder branch) { size_t number_branches = 0; @@ -229,9 +233,10 @@ static void emit_net( PipId pip = wire_pips.at(i); NPNR_ASSERT(pips->erase(pip) == 1); PhysicalNetlist::PhysNetlist::RouteBranch::Builder leaf_branch = emit_branch( - ctx, strings, pip, branches[branch_index++]); + ctx, strings, pip_place_strength, pip, branches[branch_index++]); emit_net(ctx, strings, pip_downhill, sinks, pips, + pip_place_strength, ctx->getPipDstWire(pip), leaf_branch); } } @@ -304,6 +309,8 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str size_t bel_index = strings.get_index(bel_name[1].str(ctx)); placement.setBel(bel_index); + placement.setIsBelFixed(cell.belStrength >= STRENGTH_FIXED); + placement.setIsSiteFixed(cell.belStrength >= STRENGTH_FIXED); size_t pin_count = 0; for(const auto & pin : cell.cell_bel_pins) { @@ -371,9 +378,13 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str } } + std::unordered_map<PipId, PlaceStrength> pip_place_strength; + for(auto &wire_pair : net.wires) { WireId downhill_wire = wire_pair.first; PipId pip = wire_pair.second.pip; + PlaceStrength strength = wire_pair.second.strength; + pip_place_strength[pip] = strength; if(pip != PipId()) { pips.emplace(pip); @@ -396,7 +407,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str PhysicalNetlist::PhysNetlist::RouteBranch::Builder source_branch = *source_iter++; init_bel_pin(ctx, &strings, src_bel_pin, source_branch); - emit_net(ctx, &strings, pip_downhill, sinks, &pips, root_wire, source_branch); + emit_net(ctx, &strings, pip_downhill, sinks, &pips, pip_place_strength, root_wire, source_branch); } // Any pips that were not part of a tree starting from the source are @@ -404,7 +415,7 @@ void FpgaInterchange::write_physical_netlist(const Context * ctx, const std::str auto stubs = net_out.initStubs(pips.size()); auto stub_iter = stubs.begin(); for(PipId pip : pips) { - emit_branch(ctx, &strings, pip, *stub_iter++); + emit_branch(ctx, &strings, pip_place_strength, pip, *stub_iter++); } } @@ -478,6 +489,8 @@ struct ModuleReader { LogicalNetlist::Netlist::Cell::Reader cell; LogicalNetlist::Netlist::CellDeclaration::Reader cell_decl; + std::unordered_map<int32_t, LogicalNetlist::Netlist::Net::Reader> net_indicies; + std::unordered_map<int32_t, std::string> disconnected_nets; std::unordered_map<PortKey, std::vector<int32_t>> connections; ModuleReader(const LogicalNetlistImpl *root, @@ -502,6 +515,7 @@ struct NetReader { const ModuleReader * module; size_t net_idx; + LogicalNetlist::Netlist::PropertyMap::Reader property_map; std::vector<int32_t> scratch; }; @@ -559,12 +573,19 @@ struct LogicalNetlistImpl template <typename TFunc> void foreach_netname(const ModuleReader &mod, TFunc Func) const { - auto nets = mod.cell.getNets(); - for(size_t net_idx = 0; net_idx < nets.size(); ++net_idx) { - NetReader net_reader(&mod, net_idx); - auto net = nets[net_idx]; + // std::unordered_map<int32_t, LogicalNetlist::Netlist::Net::Reader> net_indicies; + for(auto net_pair : mod.net_indicies) { + NetReader net_reader(&mod, net_pair.first); + auto net = net_pair.second; + net_reader.property_map = net.getPropMap(); Func(strings.at(net.getName()), net_reader); } + + // std::unordered_map<int32_t, IdString> disconnected_nets; + for(auto net_pair : mod.disconnected_nets) { + NetReader net_reader(&mod, net_pair.first); + Func(net_pair.second, net_reader); + } } PortType get_port_type_for_direction(LogicalNetlist::Netlist::Direction dir) const { @@ -639,8 +660,7 @@ struct LogicalNetlistImpl } template <typename TFunc> void foreach_attr(const NetReader &net_reader, TFunc Func) const { - auto net = net_reader.module->cell.getNets()[net_reader.net_idx]; - foreach_prop_map(net.getPropMap(), Func); + foreach_prop_map(net_reader.property_map, Func); } template <typename TFunc> void foreach_param(const CellReader &cell_reader, TFunc Func) const @@ -734,6 +754,10 @@ ModuleReader::ModuleReader(const LogicalNetlistImpl *root, cell = root->root.getCellList()[cell_inst.getCell()]; cell_decl = root->root.getCellDecls()[cell.getIndex()]; + // Auto-assign all ports to a net index, and then re-assign based on the + // nets. + int net_idx = 2; + auto ports = root->root.getPortList(); for(auto port_idx : cell_decl.getPorts()) { auto port = ports[port_idx]; @@ -744,7 +768,10 @@ ModuleReader::ModuleReader(const LogicalNetlistImpl *root, NPNR_ASSERT(result.second); std::vector<int32_t> & port_connections = result.first->second; - port_connections.resize(port_width, -1); + port_connections.resize(port_width); + for(size_t i = 0; i < port_width; ++i) { + port_connections[i] = net_idx++; + } } for(auto inst_idx : cell.getInsts()) { @@ -762,13 +789,17 @@ ModuleReader::ModuleReader(const LogicalNetlistImpl *root, size_t port_width = get_port_width(inst_port); std::vector<int32_t> & port_connections = result.first->second; - port_connections.resize(port_width, -1); + port_connections.resize(port_width); + for(size_t i = 0; i < port_width; ++i) { + port_connections[i] = net_idx++; + } } } auto nets = cell.getNets(); - for(size_t net_idx = 0; net_idx < nets.size(); ++net_idx) { - auto net = nets[net_idx]; + for(size_t i = 0; i < nets.size(); ++i, ++net_idx) { + auto net = nets[i]; + net_indicies[net_idx] = net; for(auto port_inst : net.getPortInsts()) { int32_t inst_idx = -1; @@ -786,6 +817,25 @@ ModuleReader::ModuleReader(const LogicalNetlistImpl *root, } } } + + for(const auto & port_connections : connections) { + for(size_t i = 0; i < port_connections.second.size(); ++i) { + int32_t net_idx = port_connections.second[i]; + + auto iter = net_indicies.find(net_idx); + if(iter == net_indicies.end()) { + PortKey port_key = port_connections.first; + auto port = ports[port_key.port_idx]; + if(port_key.inst_idx != -1 && port.getDir() != LogicalNetlist::Netlist::Direction::OUTPUT) { + log_error("Cell instance %s port %s is disconnected!\n", + root->strings.at(root->root.getInstList()[port_key.inst_idx].getName()).c_str(), + root->strings.at(ports[port_key.port_idx].getName()).c_str() + ); + } + disconnected_nets[net_idx] = stringf("%s.%d", root->strings.at(port.getName()).c_str(), i); + } + } + } } void FpgaInterchange::read_logical_netlist(Context * ctx, const std::string &filename) { @@ -814,7 +864,9 @@ void FpgaInterchange::read_logical_netlist(Context * ctx, const std::string &fil sstream.seekg(0); kj::std::StdInputStream istream(sstream); - capnp::InputStreamMessageReader message_reader(istream); + capnp::ReaderOptions reader_options; + reader_options.traversalLimitInWords = 32llu*1024llu*1024llu*1024llu; + capnp::InputStreamMessageReader message_reader(istream, reader_options); LogicalNetlist::Netlist::Reader netlist = message_reader.getRoot<LogicalNetlist::Netlist>(); LogicalNetlistImpl netlist_reader(netlist); diff --git a/fpga_interchange/main.cc b/fpga_interchange/main.cc index 48b07584..5a49cbdc 100644 --- a/fpga_interchange/main.cc +++ b/fpga_interchange/main.cc @@ -20,7 +20,9 @@ #ifdef MAIN_EXECUTABLE +#include <chrono> #include <fstream> + #include "command.h" #include "design_utils.h" #include "jsonwrite.h" @@ -67,6 +69,7 @@ void FpgaInterchangeCommandHandler::customBitstream(Context *ctx) std::unique_ptr<Context> FpgaInterchangeCommandHandler::createContext(std::unordered_map<std::string, Property> &values) { + auto start = std::chrono::high_resolution_clock::now(); ArchArgs chipArgs; if (!vm.count("chipdb")) { log_error("chip database binary must be provided\n"); @@ -88,6 +91,9 @@ std::unique_ptr<Context> FpgaInterchangeCommandHandler::createContext(std::unord } } + auto end = std::chrono::high_resolution_clock::now(); + log_info("createContext time %.02fs\n", std::chrono::duration<float>(end - start).count()); + return ctx; } diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc new file mode 100644 index 00000000..09e01507 --- /dev/null +++ b/fpga_interchange/site_router.cc @@ -0,0 +1,750 @@ +/* + * 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 "log.h" +#include "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +bool verbose_site_router(const Context *ctx) { return ctx->verbose; } + +void Arch::SiteRouter::bindBel(CellInfo *cell) +{ + auto result = cells_in_site.emplace(cell); + NPNR_ASSERT(result.second); + + dirty = true; +} + +void Arch::SiteRouter::unbindBel(CellInfo *cell) +{ + NPNR_ASSERT(cells_in_site.erase(cell) == 1); + + dirty = true; +} + +struct RouteNode +{ + void clear() + { + parent = std::list<RouteNode>::iterator(); + leafs.clear(); + pip = PipId(); + wire = WireId(); + } + + using Node = std::list<RouteNode>::iterator; + + Node parent; + std::vector<Node> leafs; + + PipId pip; // What pip was taken to reach this node. + WireId wire; // What wire is this routing node located at? +}; + +struct RouteNodeStorage +{ + // Free list of nodes. + std::list<RouteNode> nodes; + + // Either allocate a new node if no nodes are on the free list, or return + // an element from the free list. + std::list<RouteNode>::iterator alloc_node(std::list<RouteNode> &new_owner) + { + if (nodes.empty()) { + nodes.emplace_front(RouteNode()); + } + + auto ret = nodes.begin(); + new_owner.splice(new_owner.end(), nodes, ret); + + ret->clear(); + + return ret; + } + + // Return 1 node from the current owner to the free list. + void free_node(std::list<RouteNode> &owner, std::list<RouteNode>::iterator node) + { + nodes.splice(nodes.end(), owner, node); + } + + // Return all node from the current owner to the free list. + void free_nodes(std::list<RouteNode> &owner) + { + nodes.splice(nodes.end(), owner); + NPNR_ASSERT(owner.empty()); + } +}; + +struct SiteInformation +{ + const Context *ctx; + + const std::unordered_set<CellInfo *> &cells_in_site; + + SiteInformation(const Context *ctx, const std::unordered_set<CellInfo *> &cells_in_site) + : ctx(ctx), cells_in_site(cells_in_site) + { + } + + bool check_bel_pin(CellInfo *cell, const PortInfo &port_info, BelPin bel_pin) + { + WireId wire = ctx->getBelPinWire(bel_pin.bel, bel_pin.pin); + auto result = consumed_wires.emplace(wire, port_info.net); + if (!result.second) { + // This wire is already in use, make sure the net bound is + // the same net, otherwise there is a net conflict. + const NetInfo *other_net = result.first->second; + if (other_net != port_info.net) { + // We have a direct net conflict at the BEL pin, + // immediately short circuit the site routing check. + if (verbose_site_router(ctx)) { + log_info("Direct net conflict detected for cell %s:%s at bel %s, net %s != %s\n", + cell->name.c_str(ctx), cell->type.c_str(ctx), ctx->nameOfBel(cell->bel), + port_info.net->name.c_str(ctx), other_net->name.c_str(ctx)); + } + return false; + } + } + + nets_in_site.emplace(port_info.net); + + if (port_info.type == PORT_OUT) { + unrouted_source_wires.emplace(wire, std::unordered_set<WireId>()); + } else { + unrouted_sink_wires.emplace(wire); + } + + return true; + } + + bool check_initial_wires() + { + // Propagate from BEL pins to first wire, checking for trivial routing + // conflicts. + // + // Populate initial consumed wires, and nets_in_site. + for (CellInfo *cell : cells_in_site) { + BelId bel = cell->bel; + for (const auto &pin_pair : cell->cell_bel_pins) { + const PortInfo &port = cell->ports.at(pin_pair.first); + for (IdString bel_pin_name : pin_pair.second) { + BelPin bel_pin; + bel_pin.bel = bel; + bel_pin.pin = bel_pin_name; + + if (!check_bel_pin(cell, port, bel_pin)) { + return false; + } + } + } + } + + // Populate nets_fully_within_site + for (const NetInfo *net : nets_in_site) { + if (ctx->is_net_within_site(*net)) { + nets_fully_within_site.emplace(net); + } + } + + // Remove sinks that are trivially routed. + std::vector<WireId> trivially_routed_sinks; + for (WireId sink_wire : unrouted_sink_wires) { + if (unrouted_source_wires.count(sink_wire) > 0) { + if (verbose_site_router(ctx)) { + log_info("Wire %s is trivially routed!\n", ctx->nameOfWire(sink_wire)); + } + trivially_routed_sinks.push_back(sink_wire); + } + } + + for (WireId sink_wire : trivially_routed_sinks) { + NPNR_ASSERT(unrouted_sink_wires.erase(sink_wire) == 1); + } + + // Remove sources that are routed now that trivially routed sinks are + // removed. + std::unordered_set<WireId> trivially_routed_sources; + for (const NetInfo *net : nets_fully_within_site) { + std::unordered_set<WireId> sink_wires_in_net; + bool already_routed = true; + for (const PortRef &user : net->users) { + for (const IdString pin : user.cell->cell_bel_pins.at(user.port)) { + WireId sink_wire = ctx->getBelPinWire(user.cell->bel, pin); + if (unrouted_sink_wires.count(sink_wire) > 0) { + sink_wires_in_net.emplace(sink_wire); + already_routed = false; + } + } + } + + if (already_routed) { + for (const IdString pin : net->driver.cell->cell_bel_pins.at(net->driver.port)) { + trivially_routed_sources.emplace(ctx->getBelPinWire(net->driver.cell->bel, pin)); + } + } else { + for (const IdString pin : net->driver.cell->cell_bel_pins.at(net->driver.port)) { + WireId source_wire = ctx->getBelPinWire(net->driver.cell->bel, pin); + unrouted_source_wires.at(source_wire) = sink_wires_in_net; + } + } + } + + for (WireId source_wire : trivially_routed_sources) { + NPNR_ASSERT(unrouted_source_wires.erase(source_wire) == 1); + } + + return true; + } + + // Checks if a source wire has been fully routed. + // + // Returns false if this wire is not an unrouted source wire. + bool check_source_routed(WireId wire) const + { + if (unrouted_source_wires.count(wire)) { + bool fully_routed = true; + for (WireId sink_wire : unrouted_source_wires.at(wire)) { + if (unrouted_sink_wires.count(sink_wire)) { + fully_routed = false; + } + } + + return fully_routed; + } else { + return false; + } + } + + // Removes an source wires that have been fully routed. + void remove_routed_sources() + { + std::vector<WireId> routed_wires; + for (auto &source_pair : unrouted_source_wires) { + if (check_source_routed(source_pair.first)) { + routed_wires.push_back(source_pair.first); + } + } + + for (WireId wire : routed_wires) { + NPNR_ASSERT(unrouted_source_wires.erase(wire) == 1); + } + } + + bool is_fully_routed() const { return unrouted_sink_wires.empty() && unrouted_source_wires.empty(); } + + bool select_route(WireId first_wire, RouteNode::Node node, const NetInfo *net, + std::unordered_set<WireId> *newly_consumed_wires) + { + + bool is_last_pip_site_port = ctx->is_site_port(node->pip); + do { + auto result = consumed_wires.emplace(node->wire, net); + if (!result.second && result.first->second != net) { + // Conflict, this wire is already in use and it's not + // doesn't match! + return false; + } + + // By selecting a route, other sinks are potentially now routed. + unrouted_sink_wires.erase(node->wire); + + newly_consumed_wires->emplace(node->wire); + + node = node->parent; + } while (node != RouteNode::Node()); + + if (unrouted_source_wires.count(first_wire)) { + // By selecting a route to a site pip, this source wire is routed. + if (is_last_pip_site_port) { + NPNR_ASSERT(unrouted_source_wires.erase(first_wire)); + } else if (is_net_within_site(net)) { + // For nets that are completely contained within the site, it + // is possible that by selecting this route it is now fully + // routed. Check now. + if (check_source_routed(first_wire)) { + NPNR_ASSERT(unrouted_source_wires.erase(first_wire)); + } + } + } + + return true; + } + + // Map of currently occupied wires and their paired net. + std::unordered_map<WireId, const NetInfo *> consumed_wires; + + // Set of nets in site + std::unordered_set<const NetInfo *> nets_in_site; + + // Map from source wire to sink wires within this site. + // If all sink wires are routed, the source is also routed! + std::unordered_map<WireId, std::unordered_set<WireId>> unrouted_source_wires; + std::unordered_set<WireId> unrouted_sink_wires; + + // Set of nets are fully contained within the site. + std::unordered_set<const NetInfo *> nets_fully_within_site; + + bool is_net_within_site(const NetInfo *net) const { return nets_fully_within_site.count(net); } +}; + +struct SiteExpansionLoop +{ + const Context *const ctx; + RouteNodeStorage *const node_storage; + + using Node = RouteNode::Node; + + SiteExpansionLoop(const Context *ctx, RouteNodeStorage *node_storage) : ctx(ctx), node_storage(node_storage) + { + NPNR_ASSERT(node_storage != nullptr); + } + + ~SiteExpansionLoop() { node_storage->free_nodes(nodes); } + + // Storage for nodes + std::list<RouteNode> nodes; + + WireId first_wire; + const NetInfo *net_for_wire; + std::unordered_map<RouteNode *, Node> completed_routes; + std::unordered_map<WireId, std::vector<Node>> wire_to_nodes; + + Node new_node(WireId wire, PipId pip, Node parent) + { + auto node = node_storage->alloc_node(nodes); + node->wire = wire; + node->pip = pip; + node->parent = parent; + + return node; + } + + void free_node(Node node) { node_storage->free_node(nodes, node); } + + // Expand from wire specified, either downhill or uphill. + // + // Expands until it reaches another net of it's own (e.g. source to sink + // within site) or a site port (e.g. out to routing network). + void expand(WireId wire, const SiteInformation *site_info) + { + + bool downhill = site_info->unrouted_source_wires.count(wire) != 0; + if (!downhill) { + NPNR_ASSERT(site_info->unrouted_sink_wires.count(wire) != 0); + } + + first_wire = wire; + net_for_wire = site_info->consumed_wires.at(first_wire); + + if (verbose_site_router(ctx)) { + log_info("Expanding net %s from %s\n", net_for_wire->name.c_str(ctx), ctx->nameOfWire(first_wire)); + } + + completed_routes.clear(); + wire_to_nodes.clear(); + node_storage->free_nodes(nodes); + + auto node = new_node(first_wire, PipId(), /*parent=*/Node()); + wire_to_nodes[first_wire].push_back(node); + + std::vector<Node> nodes_to_expand; + nodes_to_expand.push_back(node); + + auto do_expand = [&](Node parent_node, PipId pip, WireId wire) { + if (wire == first_wire) { + // No simple loops + // FIXME: May need to detect more complicated loops! + return; + } + + if (ctx->is_site_port(pip)) { + if (verbose_site_router(ctx)) { + log_info("Expanded net %s reaches %s\n", net_for_wire->name.c_str(ctx), ctx->nameOfPip(pip)); + } + auto node = new_node(wire, pip, parent_node); + completed_routes.emplace(&*node, node); + return; + } + + auto iter = site_info->consumed_wires.find(wire); + if (iter != site_info->consumed_wires.end()) { + // This wire already belongs to a net! + if (iter->second == net_for_wire) { + // If this wire is the same net, this is a valid complete + // route. + if (!downhill && site_info->unrouted_source_wires.count(wire)) { + // This path is from a sink to a source, it is a complete route. + auto node = new_node(wire, pip, parent_node); + if (verbose_site_router(ctx)) { + log_info("Expanded net %s reaches source %s\n", net_for_wire->name.c_str(ctx), + ctx->nameOfWire(wire)); + } + completed_routes.emplace(&*node, node); + } else if (downhill && site_info->is_net_within_site(net_for_wire)) { + // This path is from a sink to a source, it is a complete route to 1 sinks. + auto node = new_node(wire, pip, parent_node); + if (verbose_site_router(ctx)) { + log_info("Expanded net %s reaches sink %s\n", net_for_wire->name.c_str(ctx), + ctx->nameOfWire(wire)); + } + completed_routes.emplace(&*node, node); + } + } else { + // Net conflict, do not expand further. + return; + } + } + + // This wire is not a destination, and is not directly occupied, + // put it on the expansion list. + nodes_to_expand.push_back(new_node(wire, pip, parent_node)); + }; + + while (!nodes_to_expand.empty()) { + Node node_to_expand = nodes_to_expand.back(); + nodes_to_expand.pop_back(); + + if (downhill) { + for (PipId pip : ctx->getPipsDownhill(node_to_expand->wire)) { + WireId wire = ctx->getPipDstWire(pip); + do_expand(node_to_expand, pip, wire); + } + } else { + for (PipId pip : ctx->getPipsUphill(node_to_expand->wire)) { + WireId wire = ctx->getPipSrcWire(pip); + do_expand(node_to_expand, pip, wire); + } + } + } + } + + // Remove any routes that use specified wire. + void remove_wire(WireId wire) + { + auto iter = wire_to_nodes.find(wire); + if (iter == wire_to_nodes.end()) { + // This wire was not in use, done! + return; + } + + // We need to prune the tree of nodes starting from any node that + // uses the specified wire. Create a queue of nodes to follow to + // gather all nodes that need to be removed. + std::list<RouteNode> nodes_to_follow; + for (Node node : iter->second) { + nodes_to_follow.splice(nodes_to_follow.end(), nodes, node); + } + + // Follow all nodes to their end, mark that node to be eventually removed. + std::list<RouteNode> nodes_to_remove; + while (!nodes_to_follow.empty()) { + Node node = nodes_to_follow.begin(); + nodes_to_remove.splice(nodes_to_remove.end(), nodes_to_follow, node); + + for (Node child_node : node->leafs) { + nodes_to_follow.splice(nodes_to_follow.end(), nodes, child_node); + } + } + + // Check if any nodes being removed are a completed route. + for (RouteNode &node : nodes_to_remove) { + completed_routes.erase(&node); + } + + // Move all nodes to be removed to the free list. + node_storage->free_nodes(nodes_to_remove); + NPNR_ASSERT(nodes_to_follow.empty()); + NPNR_ASSERT(nodes_to_remove.empty()); + } +}; + +bool route_site(const Context *ctx, SiteInformation *site_info) +{ + // All nets need to route: + // - From sources to an output site pin or sink wire. + // - From sink to an input site pin. + + std::unordered_set<WireId> unrouted_wires; + + for (auto wire_pair : site_info->unrouted_source_wires) { + auto result = unrouted_wires.emplace(wire_pair.first); + NPNR_ASSERT(result.second); + } + for (WireId wire : site_info->unrouted_sink_wires) { + auto result = unrouted_wires.emplace(wire); + if (!result.second) { + log_error("Found sink wire %s already in unrouted_wires set. unrouted_source_wires.count() == %zu\n", + ctx->nameOfWire(wire), site_info->unrouted_source_wires.count(wire)); + } + } + + // All done! + if (unrouted_wires.empty()) { + return true; + } + + // Expand from first wires to all potential routes (either net pair or + // site pin). + RouteNodeStorage node_storage; + std::vector<SiteExpansionLoop> expansions; + expansions.reserve(unrouted_wires.size()); + + for (WireId wire : unrouted_wires) { + expansions.emplace_back(SiteExpansionLoop(ctx, &node_storage)); + + SiteExpansionLoop &wire_router = expansions.back(); + wire_router.expand(wire, site_info); + + // It is not possible to route this wire at all, fail early. + if (wire_router.completed_routes.empty()) { + return false; + } + } + + std::unordered_set<WireId> newly_consumed_wires; + std::unordered_map<WireId, SiteExpansionLoop *> wire_to_expansion; + for (auto &expansion : expansions) { + // This is a special case, where the expansion found exactly 1 solution. + // That solution must be conflict free, or the site is unroutable. + if (expansion.completed_routes.size() == 1) { + auto node = expansion.completed_routes.begin()->second; + if (!site_info->select_route(expansion.first_wire, node, expansion.net_for_wire, &newly_consumed_wires)) { + // Conflict! + return false; + } + } else { + auto result = wire_to_expansion.emplace(expansion.first_wire, &expansion); + NPNR_ASSERT(result.second); + } + } + + if (wire_to_expansion.empty()) { + // All routes have been assigned with congestion! + return true; + } + + // At this point some expansions have multiple results. Build congestion + // information, and pick non-conflicted routes for remaining expansions. + std::vector<WireId> completed_wires; + do { + // Before anything, remove routes that have been consumed in previous + // iteration. + for (auto &expansion_wire : wire_to_expansion) { + auto &expansion = *expansion_wire.second; + for (WireId consumed_wire : newly_consumed_wires) { + const NetInfo *net_for_wire = site_info->consumed_wires.at(consumed_wire); + if (net_for_wire != expansion.net_for_wire) { + expansion.remove_wire(consumed_wire); + } + + // By removing that wire, this expansion now has no solutions! + if (expansion.completed_routes.empty()) { + return false; + } + } + } + + // Check if there are any more trivial solutions. + completed_wires.clear(); + newly_consumed_wires.clear(); + + for (auto &expansion_wire : wire_to_expansion) { + auto &expansion = *expansion_wire.second; + if (expansion.completed_routes.size() == 1) { + auto node = expansion.completed_routes.begin()->second; + if (!site_info->select_route(expansion.first_wire, node, expansion.net_for_wire, + &newly_consumed_wires)) { + // Conflict! + return false; + } + + // Mark this expansion as done! + completed_wires.push_back(expansion_wire.first); + } + } + + // Remove trivial solutions from unsolved routing. + for (WireId wire : completed_wires) { + NPNR_ASSERT(wire_to_expansion.erase(wire) == 1); + } + + // All expansions have been selected for! + if (wire_to_expansion.empty()) { + break; + } + + // At least 1 trivial solution was selected, re-prune. + if (!newly_consumed_wires.empty()) { + // Prune remaining solutions. + continue; + } + + std::unordered_map<WireId, std::unordered_set<const NetInfo *>> wire_congestion; + + for (auto &expansion_wire : wire_to_expansion) { + auto &expansion = *expansion_wire.second; + + for (auto pair : expansion.completed_routes) { + auto node = pair.second; + + do { + wire_congestion[node->wire].emplace(expansion.net_for_wire); + node = node->parent; + } while (node != RouteNode::Node()); + } + } + + for (auto &expansion_wire : wire_to_expansion) { + auto &expansion = *expansion_wire.second; + + RouteNode::Node uncongestion_route; + + for (auto pair : expansion.completed_routes) { + auto node = pair.second; + uncongestion_route = node; + + do { + if (wire_congestion[node->wire].size() > 1) { + uncongestion_route = RouteNode::Node(); + break; + } + node = node->parent; + } while (node != RouteNode::Node()); + + if (uncongestion_route != RouteNode::Node()) { + break; + } + } + + if (uncongestion_route != RouteNode::Node()) { + // Select a trivially uncongested route if possible. + NPNR_ASSERT(site_info->select_route(expansion.first_wire, uncongestion_route, expansion.net_for_wire, + &newly_consumed_wires)); + completed_wires.push_back(expansion.first_wire); + } + } + + // Remove trivial solutions from unsolved routing. + for (WireId wire : completed_wires) { + NPNR_ASSERT(wire_to_expansion.erase(wire) == 1); + } + + // All expansions have been selected for! + if (wire_to_expansion.empty()) { + break; + } + + // At least 1 trivial solution was selected, re-prune. + if (!newly_consumed_wires.empty()) { + // Prune remaining solutions. + continue; + } + + // FIXME: Actually de-congest non-trivial site routing. + // + // The simplistic solution (only select when 1 solution is available) + // will likely solve initial problems. Once that is show to be wrong, + // come back with something more general. + NPNR_ASSERT(false); + + } while (!wire_to_expansion.empty()); + + return true; +} + +bool Arch::SiteRouter::checkSiteRouting(const Context *ctx, const Arch::TileStatus &tile_status) const +{ + if (!dirty) { + return site_ok; + } + + dirty = false; + + if (cells_in_site.size() == 0) { + site_ok = true; + return site_ok; + } + + site_ok = false; + + // Make sure all cells in this site belong! + auto iter = cells_in_site.begin(); + NPNR_ASSERT((*iter)->bel != BelId()); + auto tile = (*iter)->bel.tile; + + if (verbose_site_router(ctx)) { + log_info("Checking site routing for site %s\n", ctx->get_site_name(tile, site)); + } + + for (CellInfo *cell : cells_in_site) { + // All cells in the site must be placed. + NPNR_ASSERT(cell->bel != BelId()); + + // Sanity check that all cells in this site are part of the same site. + NPNR_ASSERT(tile == cell->bel.tile); + NPNR_ASSERT(site == bel_info(ctx->chip_info, cell->bel).site); + + // As a first pass make sure each assigned cell in site is valid by + // constraints. + if (!ctx->is_cell_valid_constraints(cell, tile_status, verbose_site_router(ctx))) { + if (verbose_site_router(ctx)) { + log_info("Sanity check failed, cell_type %s at %s has an invalid constraints, so site is not good\n", + cell->type.c_str(ctx), ctx->nameOfBel(cell->bel)); + } + site_ok = false; + return site_ok; + } + } + // + // FIXME: Populate "consumed_wires" with all VCC/GND tied in the site. + // This will allow route_site to leverage site local constant sources. + // + // FIXME: Handle case where a constant is requested, but use of an + // inverter is possible. This is the place to handle "bestConstant" + // (e.g. route VCC's over GND's, etc). + // + // FIXME: Enable some LUT rotation! + // Default cell/bel pin map always uses high pins, which will generate + // conflicts where there are none!!! + + SiteInformation site_info(ctx, cells_in_site); + + // Push from cell pins to the first WireId from each cell pin. + if (!site_info.check_initial_wires()) { + site_ok = false; + return site_ok; + } + + site_ok = route_site(ctx, &site_info); + if (verbose_site_router(ctx)) { + if (site_ok) { + site_info.remove_routed_sources(); + NPNR_ASSERT(site_info.is_fully_routed()); + log_info("Site %s is routable\n", ctx->get_site_name(tile, site)); + } else { + log_info("Site %s is not routable\n", ctx->get_site_name(tile, site)); + } + } + + return site_ok; +} + +NEXTPNR_NAMESPACE_END |