[interchange] Add crude pseudo pip model.

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

1 files changed, 147 insertions, 0 deletions

diff --git a/fpga_interchange/pseudo_pip_model.h b/fpga_interchange/pseudo_pip_model.h
new file mode 100644
index 00000000..f0d93909
--- /dev/null
+++ b/fpga_interchange/pseudo_pip_model.h
@@ -0,0 +1,147 @@
+/*
+ *  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.
+ *
+ */
+
+#ifndef PSEUDO_PIP_MODEL_H
+#define PSEUDO_PIP_MODEL_H
+
+#include <tuple>
+
+#include "nextpnr_namespaces.h"
+#include "nextpnr_types.h"
+#include "site_router.h"
+#include "dynamic_bitarray.h"
+#include "hash_table.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct PseudoPipBel {
+    // Which BEL in the tile does the pseudo pip use?
+    int32_t bel_index;
+
+    // What is the index of the input BEL pin that the pseudo pip used?
+    //
+    // NOTE: This is **not** the name of the pin.
+    int32_t input_bel_pin;
+
+    // What is the index of the output BEL pin that the pseudo pip used?
+    //
+    // NOTE: This is **not** the name of the pin.
+    int32_t output_bel_pin;
+};
+
+struct LogicBelKey {
+    int32_t tile_type;
+    int32_t pip_index;
+    int32_t site;
+
+    std::tuple<int32_t, int32_t, int32_t> make_tuple() const {
+        return std::make_tuple(tile_type, pip_index, site);
+    }
+
+    bool operator == (const LogicBelKey & other) const {
+        return make_tuple() == other.make_tuple();
+    }
+
+    bool operator < (const LogicBelKey & other) const {
+        return make_tuple() < other.make_tuple();
+    }
+};
+
+NEXTPNR_NAMESPACE_END
+
+namespace std {
+template <> struct hash<NEXTPNR_NAMESPACE_PREFIX LogicBelKey>
+{
+    std::size_t operator()(const NEXTPNR_NAMESPACE_PREFIX LogicBelKey &key) const noexcept
+    {
+        std::size_t seed = 0;
+        boost::hash_combine(seed, hash<int32_t>()(key.tile_type));
+        boost::hash_combine(seed, hash<int32_t>()(key.pip_index));
+        boost::hash_combine(seed, hash<int32_t>()(key.site));
+
+        return seed;
+    }
+};
+
+};
+
+
+NEXTPNR_NAMESPACE_BEGIN
+
+// Storage for tile type generic pseudo pip data and lookup.
+struct PseudoPipData {
+    // Initial data for specified tile type, if not already initialized.
+    void init_tile_type(const Context *ctx, int32_t tile_type);
+
+    // Get the highest PipId::index found in a specified tile type.
+    size_t get_max_pseudo_pip(int32_t tile_type) const;
+
+    // Get the list of possible sites that a pseudo pip might be used in.
+    const std::vector<size_t> &get_possible_sites_for_pip(const Context *ctx, PipId pip) const;
+
+    // Get list of BELs the pseudo pip uses, and how it routes through them.
+    //
+    // This does **not** include site ports or site pips.
+    const std::vector<PseudoPipBel> &get_logic_bels_for_pip(const Context *ctx, int32_t site, PipId pip) const;
+
+    HashTables::HashMap<int32_t, size_t> max_pseudo_pip_for_tile_type;
+    HashTables::HashMap<std::pair<int32_t, int32_t>, std::vector<size_t>> possibles_sites_for_pip;
+    HashTables::HashMap<LogicBelKey, std::vector<PseudoPipBel>> logic_bels_for_pip;
+};
+
+// Tile instance fast pseudo pip lookup.
+struct PseudoPipModel {
+    int32_t tile;
+    DynamicBitarray<> allowed_pseudo_pips;
+    HashTables::HashMap<int32_t, size_t> pseudo_pip_sites;
+    HashTables::HashMap<size_t, std::vector<int32_t>> site_to_pseudo_pips;
+    HashTables::HashSet<int32_t> active_pseudo_pips;
+    std::vector<int32_t> scratch;
+
+    // Call when a tile is initialized.
+    void init(Context *ctx, int32_t tile);
+
+    // Call after placement but before routing to update which pseudo pips are
+    // legal.  This call is important to ensure that checkPipAvail returns the
+    // correct value.
+    //
+    // If the tile has no placed elements, then prepare_for_routing does not
+    // need to be called after init.
+    void prepare_for_routing(const Context *ctx, const std::vector<SiteRouter> & sites);
+
+    // Returns true if the pseudo pip is allowed given current site placements
+    // and other pseudo pips.
+    bool checkPipAvail(const Context *ctx, PipId pip) const;
+
+    // Enables a pseudo pip in the model.  May cause other pseudo pips to
+    // become unavailable.
+    void bindPip(const Context *ctx, PipId pip);
+
+    // Removes a pseudo pip from the model.  May cause other pseudo pips to
+    // become available.
+    void unbindPip(const Context *ctx, PipId pip);
+
+    // Internal method to update pseudo pips marked as part of a site.
+    void update_site(const Context *ctx, size_t site);
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* PSEUDO_PIP_MODEL_H */