Refactor chain finder to its own file

Signed-off-by: David Shah <davey1576@gmail.com>

4 files changed, 90 insertions, 61 deletions

diff --git a/common/chain_utils.h b/common/chain_utils.h
new file mode 100644
index 00000000..b783e30b
--- /dev/null
+++ b/common/chain_utils.h
@@ -0,0 +1,68 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  David Shah <david@symbioticeda.com>
+ *
+ *  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 CHAIN_UTILS_H
+#define CHAIN_UTILS_H
+
+#include "nextpnr.h"
+#include "util.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct CellChain
+{
+    std::vector<CellInfo *> cells;
+};
+
+// Generic chain finder
+template <typename F1, typename F2, typename F3>
+std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next,
+                                   size_t min_length = 2)
+{
+    std::set<IdString> chained;
+    std::vector<CellChain> chains;
+    for (auto cell : sorted(ctx->cells)) {
+        if (chained.find(cell.first) != chained.end())
+            continue;
+        CellInfo *ci = cell.second;
+        if (cell_type_predicate(ctx, ci)) {
+            CellInfo *start = ci;
+            CellInfo *prev_start = ci;
+            while (prev_start != nullptr) {
+                start = prev_start;
+                prev_start = get_previous(ctx, start);
+            }
+            CellChain chain;
+            CellInfo *end = start;
+            while (end != nullptr) {
+                chain.cells.push_back(end);
+                end = get_next(ctx, end);
+            }
+            if (chain.cells.size() >= min_length) {
+                chains.push_back(chain);
+                for (auto c : chain.cells)
+                    chained.insert(c->name);
+            }
+        }
+    }
+    return chains;
+}
+
+NEXTPNR_NAMESPACE_END
+#endif
diff --git a/common/design_utils.cc b/common/design_utils.cc
index 0976d6dd..7ad7f749 100644
--- a/common/design_utils.cc
+++ b/common/design_utils.cc
@@ -74,7 +74,8 @@ void print_utilisation(const Context *ctx)
 }
 
 // Connect a net to a port
-void connect_port(const Context *ctx, NetInfo *net, CellInfo *cell, IdString port_name) {
+void connect_port(const Context *ctx, NetInfo *net, CellInfo *cell, IdString port_name)
+{
     PortInfo &port = cell->ports.at(port_name);
     NPNR_ASSERT(port.net == nullptr);
     port.net = net;
diff --git a/ecp5/pack.cc b/ecp5/pack.cc
index 694fd4d9..e2bc3875 100644
--- a/ecp5/pack.cc
+++ b/ecp5/pack.cc
@@ -18,13 +18,13 @@
  */
 
 #include <algorithm>
+#include <boost/optional.hpp>
 #include <iterator>
 #include <unordered_set>
 #include "cells.h"
 #include "design_utils.h"
 #include "log.h"
 #include "util.h"
-#include <boost/optional.hpp>
 NEXTPNR_NAMESPACE_BEGIN
 
 static bool is_nextpnr_iob(Context *ctx, CellInfo *cell)
@@ -313,9 +313,9 @@ class Ecp5Packer
     }
 
     // Create a feed in to the carry chain
-    CellInfo *make_carry_feed_in(NetInfo *carry, PortRef chain_in) {
-        std::unique_ptr<CellInfo> feedin =
-                create_ecp5_cell(ctx, ctx->id("TRELLIS_SLICE"));
+    CellInfo *make_carry_feed_in(NetInfo *carry, PortRef chain_in)
+    {
+        std::unique_ptr<CellInfo> feedin = create_ecp5_cell(ctx, ctx->id("TRELLIS_SLICE"));
 
         feedin->params[ctx->id("MODE")] = "CCU2";
         feedin->params[ctx->id("LUT0_INITVAL")] = "10"; // LUT4 = 0; LUT2 = A
@@ -323,9 +323,11 @@ class Ecp5Packer
         feedin->params[ctx->id("INJECT1_0")] = "NO";
         feedin->params[ctx->id("INJECT1_1")] = "YES";
 
-        carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(), [chain_in](const PortRef &user) {
-            return user.port == chain_in.port && user.cell == chain_in.cell;
-        }), carry->users.end());
+        carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(),
+                                          [chain_in](const PortRef &user) {
+                                              return user.port == chain_in.port && user.cell == chain_in.cell;
+                                          }),
+                           carry->users.end());
         connect_port(ctx, carry, feedin.get(), id_A0);
 
         std::unique_ptr<NetInfo> new_carry(new NetInfo());
@@ -341,9 +343,9 @@ class Ecp5Packer
     }
 
     // Create a feed out and loop through from the carry chain
-    CellInfo *make_carry_feed_out(NetInfo *carry, boost::optional<PortRef> chain_next) {
-        std::unique_ptr<CellInfo> feedout =
-                create_ecp5_cell(ctx, ctx->id("TRELLIS_SLICE"));
+    CellInfo *make_carry_feed_out(NetInfo *carry, boost::optional<PortRef> chain_next)
+    {
+        std::unique_ptr<CellInfo> feedout = create_ecp5_cell(ctx, ctx->id("TRELLIS_SLICE"));
         feedout->params[ctx->id("MODE")] = "CCU2";
         feedout->params[ctx->id("LUT0_INITVAL")] = "0";
         feedout->params[ctx->id("LUT1_INITVAL")] = "10"; // LUT4 = 0; LUT2 = A
@@ -364,9 +366,11 @@ class Ecp5Packer
             // Loop back into LUT4_1 for feedthrough
             connect_port(ctx, carry, feedout.get(), id_A1);
 
-            carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(), [chain_next](const PortRef &user) {
-                return user.port == chain_next->port && user.cell == chain_next->cell;
-            }), carry->users.end());
+            carry->users.erase(std::remove_if(carry->users.begin(), carry->users.end(),
+                                              [chain_next](const PortRef &user) {
+                                                  return user.port == chain_next->port && user.cell == chain_next->cell;
+                                              }),
+                               carry->users.end());
 
             std::unique_ptr<NetInfo> new_cout(new NetInfo());
             new_cout->name = ctx->id(feedout->name.str(ctx) + "$FCO");
@@ -376,8 +380,7 @@ class Ecp5Packer
 
             IdString new_cout_name = new_cout->name;
             ctx->nets[new_cout_name] = std::move(new_cout);
-
-       }
+        }
 
         CellInfo *feedout_ptr = feedout.get();
         new_cells.push_back(std::move(feedout));
@@ -386,15 +389,10 @@ class Ecp5Packer
         ctx->nets[new_cin_name] = std::move(new_cin);
 
         return feedout_ptr;
-
     }
 
     // Pack carries and set up appropriate relative constraints
-    void pack_carries()
-    {
-        log_info("Packing carries...\n");
-
-    }
+    void pack_carries() { log_info("Packing carries...\n"); }
 
     // Pack LUTs that have been paired together
     void pack_lut_pairs()
diff --git a/ice40/chains.cc b/ice40/chains.cc
index e8a7ab17..fb361d2d 100644
--- a/ice40/chains.cc
+++ b/ice40/chains.cc
@@ -21,6 +21,7 @@
 #include <algorithm>
 #include <vector>
 #include "cells.h"
+#include "chain_utils.h"
 #include "design_utils.h"
 #include "log.h"
 #include "place_common.h"
@@ -28,45 +29,6 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-struct CellChain
-{
-    std::vector<CellInfo *> cells;
-};
-
-// Generic chain finder
-template <typename F1, typename F2, typename F3>
-std::vector<CellChain> find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next,
-                                   size_t min_length = 2)
-{
-    std::set<IdString> chained;
-    std::vector<CellChain> chains;
-    for (auto cell : sorted(ctx->cells)) {
-        if (chained.find(cell.first) != chained.end())
-            continue;
-        CellInfo *ci = cell.second;
-        if (cell_type_predicate(ctx, ci)) {
-            CellInfo *start = ci;
-            CellInfo *prev_start = ci;
-            while (prev_start != nullptr) {
-                start = prev_start;
-                prev_start = get_previous(ctx, start);
-            }
-            CellChain chain;
-            CellInfo *end = start;
-            while (end != nullptr) {
-                chain.cells.push_back(end);
-                end = get_next(ctx, end);
-            }
-            if (chain.cells.size() >= min_length) {
-                chains.push_back(chain);
-                for (auto c : chain.cells)
-                    chained.insert(c->name);
-            }
-        }
-    }
-    return chains;
-}
-
 class ChainConstrainer
 {
   private: