From a7421399f776ed9aebfa7b940bbaf5f327244f17 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Fri, 5 Feb 2021 14:18:38 -0800 Subject: Working on standing up initial constraints system. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/constraints.h | 65 ++++++++++++++++ common/constraints.impl.h | 109 ++++++++++++++++++++++++++ common/exclusive_state_groups.h | 146 +++++++++++++++++++++++++++++++++++ common/exclusive_state_groups.impl.h | 96 +++++++++++++++++++++++ common/nextpnr.h | 2 + 5 files changed, 418 insertions(+) create mode 100644 common/constraints.h create mode 100644 common/constraints.impl.h create mode 100644 common/exclusive_state_groups.h create mode 100644 common/exclusive_state_groups.impl.h (limited to 'common') 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 struct Constraints +{ + using ConstraintStateType = StateType; + using ConstraintCountType = CountType; + + enum ConstraintType + { + CONSTRAINT_TAG_IMPLIES = 0, + CONSTRAINT_TAG_REQUIRES = 1, + }; + + template 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 TagState; + std::unordered_map> definitions; + + template void bindBel(TagState *tags, const ConstraintRange constraints); + + template void unbindBel(TagState *tags, const ConstraintRange constraints); + + template + 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 +template +void Constraints::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 +template +void Constraints::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 +template +bool Constraints::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 struct ExclusiveStateGroup +{ + ExclusiveStateGroup() : state(kNoSelected) { count.fill(0); } + struct Definition + { + IdString prefix; + IdString default_state; + std::vector states; + }; + + static_assert(StateCount < std::numeric_limits::max(), "StateType cannot store max StateType"); + static_assert(std::numeric_limits::is_signed, "StateType must be signed"); + + std::bitset selected_states; + StateType state; + std::array count; + + static constexpr StateType kNoSelected = -1; + static constexpr StateType kOverConstrained = -2; + + std::pair 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 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 + 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 +void ExclusiveStateGroup::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 +void ExclusiveStateGroup::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 +template +void ExclusiveStateGroup::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 -- cgit v1.2.3 From 558a753d3da5a2243a74b8d4e1c24044bdfb5c2e Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 10:18:24 -0800 Subject: Refactor "get only from iterator" to a utility. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/util.h | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'common') 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 +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 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 -- cgit v1.2.3 From 8f668f06ca033e8b4292b4ceeb87f3078a996742 Mon Sep 17 00:00:00 2001 From: Keith Rothman <537074+litghost@users.noreply.github.com> Date: Wed, 17 Feb 2021 10:49:19 -0800 Subject: Use Bits library for bit instrisics. Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com> --- common/exclusive_state_groups.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'common') diff --git a/common/exclusive_state_groups.h b/common/exclusive_state_groups.h index 548dfe4b..c9b0df66 100644 --- a/common/exclusive_state_groups.h +++ b/common/exclusive_state_groups.h @@ -24,6 +24,8 @@ #error Include after "nextpnr.h" only. #endif +#include "bits.h" + NEXTPNR_NAMESPACE_BEGIN // Implementation for exclusive state groups, used to implement generic @@ -103,10 +105,10 @@ template