Add A*-like optimizations to router

Signed-off-by: Clifford Wolf <clifford@clifford.at>

8 files changed, 97 insertions, 31 deletions

diff --git a/common/place.cc b/common/place.cc
index 007fc748..92c09e78 100644
--- a/common/place.cc
+++ b/common/place.cc
@@ -40,6 +40,8 @@ void place_design(Design *design)
     std::set<IdString>::iterator not_found, element;
     std::set<BelType> used_bels;
 
+    log_info("Placing..\n");
+
     // Initial constraints placer
     for (auto cell_entry : design->cells) {
         CellInfo *cell = cell_entry.second;
diff --git a/common/route.cc b/common/route.cc
index ca76024f..4af5f60f 100644
--- a/common/route.cc
+++ b/common/route.cc
@@ -17,6 +17,7 @@
  *
  */
 
+#include <cmath>
 #include <queue>
 
 #include "log.h"
@@ -28,21 +29,26 @@ struct QueuedWire
 {
     WireId wire;
     PipId pip;
-    DelayInfo delay;
+
+    float delay = 0, togo = 0;
 
     struct Greater
     {
         bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const
                 noexcept
         {
-            return lhs.delay.avgDelay() > rhs.delay.avgDelay();
+            return (lhs.delay + lhs.togo) > (rhs.delay + rhs.togo);
         }
     };
 };
 
-void route_design(Design *design)
+void route_design(Design *design, bool verbose)
 {
     auto &chip = design->chip;
+    int itercnt = 0, netcnt = 0;
+    float maxDelay = 0.0;
+
+    log_info("Routing..\n");
 
     for (auto &net_it : design->nets) {
         auto net_name = net_it.first;
@@ -51,17 +57,22 @@ void route_design(Design *design)
         if (net_info->driver.cell == nullptr)
             continue;
 
-        log("Routing net %s.\n", net_name.c_str());
+        if (verbose)
+            log("Routing net %s.\n", net_name.c_str());
+        netcnt++;
 
-        log("  Source: %s.%s.\n", net_info->driver.cell->name.c_str(),
-            net_info->driver.port.c_str());
+        if (verbose)
+            log("  Source: %s.%s.\n", net_info->driver.cell->name.c_str(),
+                net_info->driver.port.c_str());
 
         auto src_bel = net_info->driver.cell->bel;
+        auto src_pos = chip.getBelPosition(src_bel);
 
         if (src_bel == BelId())
             log_error("Source cell is not mapped to a bel.\n");
 
-        log("    Source bel: %s\n", chip.getBelName(src_bel).c_str());
+        if (verbose)
+            log("    Source bel: %s\n", chip.getBelName(src_bel).c_str());
 
         auto src_wire = chip.getWireBelPin(
                 src_bel, portPinFromId(net_info->driver.port));
@@ -70,7 +81,8 @@ void route_design(Design *design)
             log_error("No wire found for port %s on source bel.\n",
                       net_info->driver.port.c_str());
 
-        log("    Source wire: %s\n", chip.getWireName(src_wire).c_str());
+        if (verbose)
+            log("    Source wire: %s\n", chip.getWireName(src_wire).c_str());
 
         std::unordered_map<WireId, DelayInfo> src_wires;
         src_wires[src_wire] = DelayInfo();
@@ -78,15 +90,22 @@ void route_design(Design *design)
         chip.bindWire(src_wire, net_name);
 
         for (auto &user_it : net_info->users) {
-            log("  Route to: %s.%s.\n", user_it.cell->name.c_str(),
-                user_it.port.c_str());
+            if (verbose)
+                log("  Route to: %s.%s.\n", user_it.cell->name.c_str(),
+                    user_it.port.c_str());
 
             auto dst_bel = user_it.cell->bel;
+            auto dst_pos = chip.getBelPosition(dst_bel);
 
             if (dst_bel == BelId())
                 log_error("Destination cell is not mapped to a bel.\n");
 
-            log("    Destination bel: %s\n", chip.getBelName(dst_bel).c_str());
+            if (verbose) {
+                log("    Destination bel: %s\n",
+                    chip.getBelName(dst_bel).c_str());
+                log("    Path delay estimate: %.2f\n",
+                    chip.estimateDelay(src_pos, dst_pos));
+            }
 
             auto dst_wire =
                     chip.getWireBelPin(dst_bel, portPinFromId(user_it.port));
@@ -95,8 +114,9 @@ void route_design(Design *design)
                 log_error("No wire found for port %s on destination bel.\n",
                           user_it.port.c_str());
 
-            log("    Destination wire: %s\n",
-                chip.getWireName(dst_wire).c_str());
+            if (verbose)
+                log("    Destination wire: %s\n",
+                    chip.getWireName(dst_wire).c_str());
 
             std::unordered_map<WireId, QueuedWire> visited;
             std::priority_queue<QueuedWire, std::vector<QueuedWire>,
@@ -107,13 +127,16 @@ void route_design(Design *design)
                 QueuedWire qw;
                 qw.wire = it.first;
                 qw.pip = PipId();
-                qw.delay = it.second;
+                qw.delay = it.second.avgDelay();
+                qw.togo = chip.estimateDelay(chip.getWirePosition(qw.wire),
+                                             dst_pos);
 
                 queue.push(qw);
                 visited[qw.wire] = qw;
             }
 
             while (!queue.empty()) {
+                itercnt++;
                 QueuedWire qw = queue.top();
                 queue.pop();
 
@@ -122,15 +145,28 @@ void route_design(Design *design)
                         continue;
 
                     WireId next_wire = chip.getPipDstWire(pip);
+                    float next_delay =
+                            qw.delay + chip.getPipDelay(pip).avgDelay();
+
+                    if (visited.count(next_wire)) {
+                        if (visited.at(next_wire).delay <= next_delay + 1e-3)
+                            continue;
+                        if (verbose)
+                            log("Found better route to %s. Old vs new delay "
+                                "estimate: %.2f %.2f\n",
+                                chip.getWireName(next_wire).c_str(),
+                                visited.at(next_wire).delay, next_delay);
+                    }
 
-                    if (visited.count(next_wire) ||
-                        !chip.checkWireAvail(next_wire))
+                    if (!chip.checkWireAvail(next_wire))
                         continue;
 
                     QueuedWire next_qw;
                     next_qw.wire = next_wire;
                     next_qw.pip = pip;
-                    next_qw.delay = qw.delay + chip.getPipDelay(pip);
+                    next_qw.delay = next_delay;
+                    next_qw.togo = chip.estimateDelay(
+                            chip.getWirePosition(next_wire), dst_pos);
                     visited[next_qw.wire] = next_qw;
                     queue.push(next_qw);
 
@@ -149,13 +185,19 @@ void route_design(Design *design)
                           chip.getWireName(src_wire).c_str(),
                           chip.getWireName(dst_wire).c_str());
 
-            log("      Route (from destination to source):\n");
+            if (verbose)
+                log("    Final path delay: %.2f\n", visited[dst_wire].delay);
+            maxDelay = fmaxf(maxDelay, visited[dst_wire].delay);
+
+            if (verbose)
+                log("    Route (from destination to source):\n");
 
             WireId cursor = dst_wire;
 
             while (1) {
-                log("      %8.2f %s\n", visited[cursor].delay.avgDelay(),
-                    chip.getWireName(cursor).c_str());
+                if (verbose)
+                    log("    %8.2f %s\n", visited[cursor].delay,
+                        chip.getWireName(cursor).c_str());
 
                 if (src_wires.count(cursor))
                     break;
@@ -164,11 +206,14 @@ void route_design(Design *design)
                 chip.bindWire(cursor, net_name);
                 chip.bindPip(visited[cursor].pip, net_name);
 
-                src_wires[cursor] = visited[cursor].delay;
+                src_wires[cursor] = chip.getPipDelay(visited[cursor].pip);
                 cursor = chip.getPipSrcWire(visited[cursor].pip);
             }
         }
     }
+
+    log_info("routed %d nets, visited %d wires.\n", netcnt, itercnt);
+    log_info("longest path delay: %.2f\n", maxDelay);
 }
 
 NEXTPNR_NAMESPACE_END
diff --git a/common/route.h b/common/route.h
index d9c240b3..edb9a53e 100644
--- a/common/route.h
+++ b/common/route.h
@@ -24,7 +24,7 @@
 
 NEXTPNR_NAMESPACE_BEGIN
 
-extern void route_design(Design *design);
+extern void route_design(Design *design, bool verbose = false);
 
 NEXTPNR_NAMESPACE_END
 
diff --git a/ice40/cells.cc b/ice40/cells.cc
index 604baccb..a8200d76 100644
--- a/ice40/cells.cc
+++ b/ice40/cells.cc
@@ -166,7 +166,8 @@ void nxio_to_sb(CellInfo *nxio, CellInfo *sbio)
     }
 }
 
-bool is_global_net(NetInfo *net) {
+bool is_global_net(NetInfo *net)
+{
     return bool(net_driven_by(net, is_gbuf, "GLOBAL_BUFFER_OUTPUT"));
 }
 
diff --git a/ice40/cells.h b/ice40/cells.h
index 660c7265..db0aa3d1 100644
--- a/ice40/cells.h
+++ b/ice40/cells.h
@@ -51,7 +51,7 @@ inline bool is_ff(const CellInfo *cell)
 inline bool is_sb_io(const CellInfo *cell) { return cell->type == "SB_IO"; }
 
 // Return true if a cell is a global buffer
-inline bool is_gbuf(const CellInfo *cell) {return cell->type == "SB_GB"; }
+inline bool is_gbuf(const CellInfo *cell) { return cell->type == "SB_GB"; }
 
 // Convert a SB_LUT primitive to (part of) an ICESTORM_LC, swapping ports
 // as needed. Set no_dff if a DFF is not being used, so that the output
diff --git a/ice40/chip.cc b/ice40/chip.cc
index 8bbdf5a4..87428339 100644
--- a/ice40/chip.cc
+++ b/ice40/chip.cc
@@ -304,7 +304,7 @@ PosInfo Chip::getPipPosition(PipId pip) const
 
 float Chip::estimateDelay(PosInfo src, PosInfo dst) const
 {
-    return fabsf(src.x - dst.x) + fabsf(src.x - dst.x);
+    return fabsf(src.x - dst.x) + fabsf(src.y - dst.y);
 }
 
 // -----------------------------------------------------------------------
diff --git a/ice40/main.cc b/ice40/main.cc
index 8ccec77b..094e6a75 100644
--- a/ice40/main.cc
+++ b/ice40/main.cc
@@ -60,12 +60,14 @@ int main(int argc, char *argv[])
 {
     namespace po = boost::program_options;
     int rc = 0;
+    bool verbose = false;
     std::string str;
 
     log_files.push_back(stdout);
 
     po::options_description options("Allowed options");
     options.add_options()("help,h", "show help");
+    options.add_options()("verbose,v", "verbose output");
     options.add_options()("gui", "start gui");
     options.add_options()("svg", "dump SVG file");
     options.add_options()("pack-only",
@@ -125,6 +127,10 @@ int main(int argc, char *argv[])
         return 1;
     }
 
+    if (vm.count("verbose")) {
+        verbose = true;
+    }
+
     ChipArgs chipArgs;
 
     if (vm.count("lp384")) {
@@ -217,7 +223,7 @@ int main(int argc, char *argv[])
         pack_design(&design);
         if (!vm.count("pack-only")) {
             place_design(&design);
-            route_design(&design);
+            route_design(&design, verbose);
         }
     }
 
diff --git a/ice40/pack.cc b/ice40/pack.cc
index e8876283..853ef8ca 100644
--- a/ice40/pack.cc
+++ b/ice40/pack.cc
@@ -30,6 +30,8 @@ NEXTPNR_NAMESPACE_BEGIN
 // Pack LUTs and LUT-FF pairs
 static void pack_lut_lutffs(Design *design)
 {
+    log_info("Packing LUT-FFs..\n");
+
     std::unordered_set<IdString> packed_cells;
     std::vector<CellInfo *> new_cells;
     for (auto cell : design->cells) {
@@ -85,6 +87,8 @@ static void pack_lut_lutffs(Design *design)
 // Pack FFs not packed as LUTFFs
 static void pack_nonlut_ffs(Design *design)
 {
+    log_info("Packing non-LUT FFs..\n");
+
     std::unordered_set<IdString> packed_cells;
     std::vector<CellInfo *> new_cells;
 
@@ -132,6 +136,8 @@ static void set_net_constant(NetInfo *orig, NetInfo *constnet, bool constval)
 // Pack constants (simple implementation)
 static void pack_constants(Design *design)
 {
+    log_info("Packing constants..\n");
+
     CellInfo *gnd_cell = create_ice_cell(design, "ICESTORM_LC", "$PACKER_GND");
     gnd_cell->params["LUT_INIT"] = "0";
     NetInfo *gnd_net = new NetInfo;
@@ -180,6 +186,8 @@ static void pack_io(Design *design)
     std::unordered_set<IdString> packed_cells;
     std::vector<CellInfo *> new_cells;
 
+    log_info("Packing IOs..\n");
+
     for (auto cell : design->cells) {
         CellInfo *ci = cell.second;
         if (is_nextpnr_iob(ci)) {
@@ -225,21 +233,25 @@ static void pack_io(Design *design)
 // Simple global promoter (clock only)
 static void promote_globals(Design *design)
 {
+    log_info("Promoting globals..\n");
+
     std::unordered_map<IdString, int> clock_count;
     for (auto net : design->nets) {
         NetInfo *ni = net.second;
         if (ni->driver.cell != nullptr && !is_global_net(ni)) {
             clock_count[net.first] = 0;
             for (auto user : ni->users) {
-                if (user.cell != nullptr && is_ff(user.cell) && user.port == "C")
+                if (user.cell != nullptr && is_ff(user.cell) &&
+                    user.port == "C")
                     clock_count[net.first]++;
             }
         }
     }
-    auto global_clock = std::max_element(clock_count.begin(), clock_count.end(), [](
-            const std::pair<IdString, int> &a, const std::pair<IdString, int> &b) {
-       return a.second < b.second;
-    });
+    auto global_clock = std::max_element(clock_count.begin(), clock_count.end(),
+                                         [](const std::pair<IdString, int> &a,
+                                            const std::pair<IdString, int> &b) {
+                                             return a.second < b.second;
+                                         });
     if (global_clock->second > 0) {
         NetInfo *clknet = design->nets[global_clock->first];
         CellInfo *gb = create_ice_cell(design, "SB_GB");