Rework FPGA interchange site router.

The new site router should be robust to most situations, and isn't
significantly slower with the use of caching.

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

1 files changed, 150 insertions, 0 deletions

diff --git a/fpga_interchange/site_routing_storage.h b/fpga_interchange/site_routing_storage.h
new file mode 100644
index 00000000..a8ea51f5
--- /dev/null
+++ b/fpga_interchange/site_routing_storage.h
@@ -0,0 +1,150 @@
+/*
+ *  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 SITE_ROUTING_STORAGE
+#define SITE_ROUTING_STORAGE
+
+#include <limits>
+
+#include "nextpnr_namespaces.h"
+#include "site_arch.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct RouteNode
+{
+    void clear()
+    {
+        parent = std::numeric_limits<size_t>::max();
+        pip = SitePip();
+        wire = SiteWire();
+        flags = 0;
+        depth = 0;
+    }
+
+    enum Flags
+    {
+        // Has this path left the site?
+        LEFT_SITE = 0,
+        // Has this path entered the site?
+        ENTERED_SITE = 1,
+    };
+
+    bool has_left_site() const { return (flags & (1 << LEFT_SITE)) != 0; }
+
+    bool can_leave_site() const { return !has_left_site(); }
+
+    void mark_left_site() { flags |= (1 << LEFT_SITE); }
+
+    bool has_entered_site() const { return (flags & (1 << ENTERED_SITE)) != 0; }
+
+    bool can_enter_site() const { return !has_entered_site(); }
+
+    void mark_entered_site() { flags |= (1 << ENTERED_SITE); }
+
+    size_t parent;
+
+    SitePip pip;   // What pip was taken to reach this node.
+    SiteWire wire; // What wire is this routing node located at?
+    int32_t flags;
+    int32_t depth;
+};
+
+struct RouteNodeStorage;
+
+class Node
+{
+  public:
+    Node(RouteNodeStorage *storage, size_t idx) : storage_(storage), idx_(idx) {}
+
+    size_t get_index() const { return idx_; }
+
+    RouteNode &operator*();
+    const RouteNode &operator*() const;
+    RouteNode *operator->();
+    const RouteNode *operator->() const;
+    bool has_parent() const;
+    Node parent();
+
+  private:
+    RouteNodeStorage *storage_;
+    size_t idx_;
+};
+
+struct RouteNodeStorage
+{
+    // Free list of nodes.
+    std::vector<RouteNode> nodes;
+    std::vector<size_t> free_list;
+
+    // Either allocate a new node if no nodes are on the free list, or return
+    // an element from the free list.
+    Node alloc_node()
+    {
+        if (free_list.empty()) {
+            nodes.emplace_back();
+            nodes.back().clear();
+            return Node(this, nodes.size() - 1);
+        }
+
+        size_t idx = free_list.back();
+        free_list.pop_back();
+        nodes[idx].clear();
+
+        return Node(this, idx);
+    }
+
+    Node get_node(size_t idx)
+    {
+        NPNR_ASSERT(idx < nodes.size());
+        return Node(this, idx);
+    }
+
+    const Node get_node(size_t idx) const
+    {
+        NPNR_ASSERT(idx < nodes.size());
+        return Node(const_cast<RouteNodeStorage *>(this), idx);
+    }
+
+    // Return all node from the current owner to the free list.
+    void free_nodes(std::vector<size_t> &other_free_list)
+    {
+        free_list.insert(free_list.end(), other_free_list.begin(), other_free_list.end());
+    }
+};
+
+inline RouteNode &Node::operator*() { return storage_->nodes[idx_]; }
+inline const RouteNode &Node::operator*() const { return storage_->nodes[idx_]; }
+
+inline RouteNode *Node::operator->() { return &storage_->nodes[idx_]; }
+inline const RouteNode *Node::operator->() const { return &storage_->nodes[idx_]; }
+
+inline bool Node::has_parent() const { return storage_->nodes[idx_].parent < storage_->nodes.size(); }
+
+inline Node Node::parent()
+{
+    size_t parent_idx = storage_->nodes[idx_].parent;
+    NPNR_ASSERT(parent_idx < storage_->nodes.size());
+    return Node(storage_, parent_idx);
+}
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* SITE_ROUTING_STORAGE */