Add A*-like optimizations to router

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

5 files changed, 28 insertions, 9 deletions

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");