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/exclusive_state_groups.h | 146 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 146 insertions(+) create mode 100644 common/exclusive_state_groups.h (limited to 'common/exclusive_state_groups.h') 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 -- 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/exclusive_state_groups.h') 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