Merge pull request #576 from litghost/add_cell_bel_pin_mapping

Complete FPGA interchange Arch to the point where it can route a wire

6 files changed, 443 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..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