Working on standing up initial constraints system.

Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>

8 files changed, 886 insertions, 25 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
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index c24ec660..41659861 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);
@@ -155,6 +153,30 @@ Arch::Arch(ArchArgs args) : args(args)
             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));
+            }
+        }
+    }
+
+    default_tags.resize(max_tag_count);
 }
 
 // -----------------------------------------------------------------------
@@ -563,20 +585,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;
 }
 
 // -----------------------------------------------------------------------
@@ -771,4 +828,12 @@ bool Arch::is_net_within_site(const NetInfo &net) const
     return true;
 }
 
+// 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..88f35df4 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 ****/
@@ -751,12 +753,14 @@ 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
     {
+        std::vector<ExclusiveStateGroup<kMaxState>> tags;
         std::vector<CellInfo *> boundcells;
     };
 
-    std::vector<TileStatus> tileStatus;
+    std::unordered_map<int32_t, TileStatus> tileStatus;
 
     ArchArgs args;
     Arch(ArchArgs args);
@@ -818,12 +822,24 @@ 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());
+        }
+
+        return result.first->second;
+    }
+
     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 +851,69 @@ 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.
         }
+
+        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));
+        }
+
         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
@@ -1251,6 +1300,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;
@@ -1352,16 +1404,40 @@ 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;
         }
+
+        auto cell_type_index = get_cell_type_index(cell_type);
+        const auto &bel_data = bel_info(chip_info, bel);
+        if (bel_data.category != BEL_CATEGORY_LOGIC) {
+            return false;
+        }
+        return bel_data.pin_map[cell_type_index] != -1;
     }
 
     // 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;
+            }
+
+            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_constraints);
+        }
     }
 
     IdString get_bel_tiletype(BelId bel) const { return IdString(loc_info(chip_info, bel).name); }
@@ -1406,6 +1482,93 @@ 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;
+    }
 };
 
 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..cc1cfb93
--- /dev/null
+++ b/fpga_interchange/arch_pack_io.cc
@@ -0,0 +1,215 @@
+/*
+ *  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
+
+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::unordered_map<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][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) {
+        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);
+                }
+            }
+        }
+
+        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) {
+                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);
+                        }
+                    }
+                }
+            }
+        }
+
+        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());
+
+        BelId package_bel;
+        for (IdString site_type : possible_site_types) {
+            auto site_iter = pin_iter->second.find(site_type);
+            if (site_iter != pin_iter->second.end()) {
+                // FIXME: Need to handle case where a port can be in multiple
+                // modes, but only one of the modes works.
+                //
+                // NPNR_ASSERT(package_bel == BelId());
+                package_bel = site_iter->second;
+            }
+        }
+        NPNR_ASSERT(package_bel != BelId());
+
+        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);
+        // NPNR_ASSERT(std::distance(package_bel_pins.begin(), package_bel_pins.end()) == 1);
+        IdStringIterator b = package_bel_pins.begin();
+        NPNR_ASSERT(b != package_bel_pins.end());
+        ++b;
+        NPNR_ASSERT(b == package_bel_pins.end());
+        IdString pad_pin = *package_bel_pins.begin();
+
+        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(isValidBelForCell(cell, cell->bel));
+        }
+    }
+}
+
+NEXTPNR_NAMESPACE_END