diff options
Diffstat (limited to 'common')
| -rw-r--r-- | common/constraints.h | 65 | ||||
| -rw-r--r-- | common/constraints.impl.h | 109 | ||||
| -rw-r--r-- | common/exclusive_state_groups.h | 146 | ||||
| -rw-r--r-- | common/exclusive_state_groups.impl.h | 96 | ||||
| -rw-r--r-- | common/nextpnr.h | 2 |
5 files changed, 418 insertions, 0 deletions
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..548dfe4b --- /dev/null +++ b/common/exclusive_state_groups.h @@ -0,0 +1,146 @@ +/* + * 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 + +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 = __builtin_popcount(value); + if (number_selected == 1) { + // Group is no longer overconstrained. + state = __builtin_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 |