Merge branch 'master' of github.com:YosysHQ/nextpnr into constids

7 files changed, 732 insertions, 89 deletions

diff --git a/common/command.cc b/common/command.cc
new file mode 100644
index 00000000..736f6201
--- /dev/null
+++ b/common/command.cc
@@ -0,0 +1,263 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Clifford Wolf <clifford@symbioticeda.com>
+ *  Copyright (C) 2018  Miodrag Milanovic <miodrag@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 NO_GUI
+#include <QApplication>
+#include "application.h"
+#include "mainwindow.h"
+#endif
+#ifndef NO_PYTHON
+#include "pybindings.h"
+#endif
+
+#include <boost/filesystem/convenience.hpp>
+#include <boost/program_options.hpp>
+#include <fstream>
+#include <iostream>
+#include "command.h"
+#include "design_utils.h"
+#include "jsonparse.h"
+#include "log.h"
+#include "timing.h"
+#include "version.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+CommandHandler::CommandHandler(int argc, char **argv) : argc(argc), argv(argv) { log_files.push_back(stdout); }
+
+bool CommandHandler::parseOptions()
+{
+    options.add(getGeneralOptions()).add(getArchOptions());
+    try {
+        po::parsed_options parsed =
+                po::command_line_parser(argc, argv)
+                        .style(po::command_line_style::default_style ^ po::command_line_style::allow_guessing)
+                        .options(options)
+                        .positional(pos)
+                        .run();
+        po::store(parsed, vm);
+        po::notify(vm);
+        return true;
+    } catch (std::exception &e) {
+        std::cout << e.what() << "\n";
+        return false;
+    }
+}
+
+bool CommandHandler::executeBeforeContext()
+{
+    if (vm.count("help") || argc == 1) {
+        std::cout << boost::filesystem::basename(argv[0])
+                  << " -- Next Generation Place and Route (git sha1 " GIT_COMMIT_HASH_STR ")\n";
+        std::cout << options << "\n";
+        return argc != 1;
+    }
+
+    if (vm.count("version")) {
+        std::cout << boost::filesystem::basename(argv[0])
+                  << " -- Next Generation Place and Route (git sha1 " GIT_COMMIT_HASH_STR ")\n";
+        return true;
+    }
+    validate();
+    return false;
+}
+
+po::options_description CommandHandler::getGeneralOptions()
+{
+    po::options_description general("General options");
+    general.add_options()("help,h", "show help");
+    general.add_options()("verbose,v", "verbose output");
+    general.add_options()("debug", "debug output");
+    general.add_options()("force,f", "keep running after errors");
+#ifndef NO_GUI
+    general.add_options()("gui", "start gui");
+#endif
+#ifndef NO_PYTHON
+    general.add_options()("run", po::value<std::vector<std::string>>(), "python file to execute");
+    pos.add("run", -1);
+#endif
+    general.add_options()("json", po::value<std::string>(), "JSON design file to ingest");
+    general.add_options()("seed", po::value<int>(), "seed value for random number generator");
+    general.add_options()("slack_redist_iter", po::value<int>(), "number of iterations between slack redistribution");
+    general.add_options()("cstrweight", po::value<float>(), "placer weighting for relative constraint satisfaction");
+    general.add_options()("pack-only", "pack design only without placement or routing");
+
+    general.add_options()("version,V", "show version");
+    general.add_options()("test", "check architecture database integrity");
+    general.add_options()("freq", po::value<double>(), "set target frequency for design in MHz");
+    general.add_options()("no-tmdriv", "disable timing-driven placement");
+    general.add_options()("save", po::value<std::string>(), "project file to write");
+    general.add_options()("load", po::value<std::string>(), "project file to read");
+    return general;
+}
+
+void CommandHandler::setupContext(Context *ctx)
+{
+    if (vm.count("verbose")) {
+        ctx->verbose = true;
+    }
+
+    if (vm.count("debug")) {
+        ctx->verbose = true;
+        ctx->debug = true;
+    }
+
+    if (vm.count("force")) {
+        ctx->force = true;
+    }
+
+    if (vm.count("seed")) {
+        ctx->rngseed(vm["seed"].as<int>());
+    }
+
+    if (vm.count("slack_redist_iter")) {
+        ctx->slack_redist_iter = vm["slack_redist_iter"].as<int>();
+        if (vm.count("freq") && vm["freq"].as<double>() == 0) {
+            ctx->auto_freq = true;
+#ifndef NO_GUI
+            if (!vm.count("gui"))
+#endif
+                log_warning("Target frequency not specified. Will optimise for max frequency.\n");
+        }
+    }
+
+    if (vm.count("cstrweight")) {
+        // ctx->placer_constraintWeight = vm["cstrweight"].as<float>();
+    }
+
+    if (vm.count("freq")) {
+        auto freq = vm["freq"].as<double>();
+        if (freq > 0)
+            ctx->target_freq = freq * 1e6;
+    }
+
+    ctx->timing_driven = true;
+    if (vm.count("no-tmdriv"))
+        ctx->timing_driven = false;
+}
+
+int CommandHandler::executeMain(std::unique_ptr<Context> ctx)
+{
+    if (vm.count("test")) {
+        ctx->archcheck();
+        return 0;
+    }
+
+#ifndef NO_GUI
+    if (vm.count("gui")) {
+        Application a(argc, argv);
+        MainWindow w(std::move(ctx), chipArgs);
+        try {
+            if (vm.count("json")) {
+                std::string filename = vm["json"].as<std::string>();
+                std::ifstream f(filename);
+                if (!parse_json_file(f, filename, w.getContext()))
+                    log_error("Loading design failed.\n");
+
+                customAfterLoad(w.getContext());
+                w.updateJsonLoaded();
+            }
+        } catch (log_execution_error_exception) {
+            // show error is handled by gui itself
+        }
+        w.show();
+
+        return a.exec();
+    }
+#endif
+    if (vm.count("json")) {
+        std::string filename = vm["json"].as<std::string>();
+        std::ifstream f(filename);
+        if (!parse_json_file(f, filename, ctx.get()))
+            log_error("Loading design failed.\n");
+
+        customAfterLoad(ctx.get());
+    }
+
+    if (vm.count("json") || vm.count("load")) {
+        if (!ctx->pack() && !ctx->force)
+            log_error("Packing design failed.\n");
+        assign_budget(ctx.get());
+        ctx->check();
+        print_utilisation(ctx.get());
+        if (!vm.count("pack-only")) {
+            if (!ctx->place() && !ctx->force)
+                log_error("Placing design failed.\n");
+            ctx->check();
+            if (!ctx->route() && !ctx->force)
+                log_error("Routing design failed.\n");
+        }
+
+        customBitstream(ctx.get());
+    }
+
+#ifndef NO_PYTHON
+    if (vm.count("run")) {
+        init_python(argv[0], true);
+        python_export_global("ctx", *ctx);
+
+        std::vector<std::string> files = vm["run"].as<std::vector<std::string>>();
+        for (auto filename : files)
+            execute_python_file(filename.c_str());
+
+        deinit_python();
+    }
+#endif
+
+    if (vm.count("save")) {
+        project.save(ctx.get(), vm["save"].as<std::string>());
+    }
+
+    return 0;
+}
+
+void CommandHandler::conflicting_options(const boost::program_options::variables_map &vm, const char *opt1,
+                                         const char *opt2)
+{
+    if (vm.count(opt1) && !vm[opt1].defaulted() && vm.count(opt2) && !vm[opt2].defaulted()) {
+        std::string msg = "Conflicting options '" + std::string(opt1) + "' and '" + std::string(opt2) + "'.";
+        log_error("%s\n", msg.c_str());
+    }
+}
+
+int CommandHandler::exec()
+{
+    try {
+        if (!parseOptions())
+            return -1;
+
+        if (executeBeforeContext())
+            return 0;
+
+        std::unique_ptr<Context> ctx;
+        if (vm.count("load")) {
+            ctx = project.load(vm["load"].as<std::string>());
+        } else {
+            ctx = createContext();
+        }
+        setupContext(ctx.get());
+        setupArchContext(ctx.get());
+        return executeMain(std::move(ctx));
+    } catch (log_execution_error_exception) {
+        return -1;
+    }
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/common/command.h b/common/command.h
new file mode 100644
index 00000000..13d5a250
--- /dev/null
+++ b/common/command.h
@@ -0,0 +1,70 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Clifford Wolf <clifford@symbioticeda.com>
+ *  Copyright (C) 2018  Miodrag Milanovic <miodrag@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 COMMAND_H
+#define COMMAND_H
+
+#include <boost/program_options.hpp>
+#include "nextpnr.h"
+#include "project.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+namespace po = boost::program_options;
+
+class CommandHandler
+{
+  public:
+    CommandHandler(int argc, char **argv);
+    virtual ~CommandHandler(){};
+
+    int exec();
+
+  protected:
+    virtual void setupArchContext(Context *ctx) = 0;
+    virtual std::unique_ptr<Context> createContext() = 0;
+    virtual po::options_description getArchOptions() = 0;
+    virtual void validate(){};
+    virtual void customAfterLoad(Context *ctx){};
+    virtual void customBitstream(Context *ctx){};
+    void conflicting_options(const boost::program_options::variables_map &vm, const char *opt1, const char *opt2);
+
+  private:
+    bool parseOptions();
+    bool executeBeforeContext();
+    void setupContext(Context *ctx);
+    int executeMain(std::unique_ptr<Context> ctx);
+    po::options_description getGeneralOptions();
+
+  protected:
+    po::variables_map vm;
+    ArchArgs chipArgs;
+
+  private:
+    po::options_description options;
+    po::positional_options_description pos;
+    int argc;
+    char **argv;
+    ProjectHandler project;
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif // COMMAND_H
diff --git a/common/nextpnr.h b/common/nextpnr.h
index f231f1b8..e588f47b 100644
--- a/common/nextpnr.h
+++ b/common/nextpnr.h
@@ -291,6 +291,19 @@ struct CellInfo : ArchCellInfo
     // parent.[xyz] := 0 when (constr_parent == nullptr)
 };
 
+enum TimingPortClass
+{
+    TMG_CLOCK_INPUT,     // Clock input to a sequential cell
+    TMG_GEN_CLOCK,       // Generated clock output (PLL, DCC, etc)
+    TMG_REGISTER_INPUT,  // Input to a register, with an associated clock (may also have comb. fanout too)
+    TMG_REGISTER_OUTPUT, // Output from a register
+    TMG_COMB_INPUT,      // Combinational input, no paths end here
+    TMG_COMB_OUTPUT,     // Combinational output, no paths start here
+    TMG_STARTPOINT,      // Unclocked primary startpoint, such as an IO cell output
+    TMG_ENDPOINT,        // Unclocked primary endpoint, such as an IO cell input
+    TMG_IGNORE,          // Asynchronous to all clocks, "don't care", and should be ignored (false path) for analysis
+};
+
 struct DeterministicRNG
 {
     uint64_t rngstate;
@@ -371,6 +384,9 @@ struct BaseCtx
     mutable std::unordered_map<std::string, int> *idstring_str_to_idx;
     mutable std::vector<const std::string *> *idstring_idx_to_str;
 
+    // Project settings and config switches
+    std::unordered_map<IdString, std::string> settings;
+
     // Placed nets and cells.
     std::unordered_map<IdString, std::unique_ptr<NetInfo>> nets;
     std::unordered_map<IdString, std::unique_ptr<CellInfo>> cells;
@@ -437,7 +453,7 @@ struct BaseCtx
 
     const Context *getCtx() const { return reinterpret_cast<const Context *>(this); }
 
-    template<typename T> const char *nameOf(const T *obj)
+    template <typename T> const char *nameOf(const T *obj)
     {
         if (obj == nullptr)
             return "";
diff --git a/common/placer1.cc b/common/placer1.cc
index 36a607d7..91320240 100644
--- a/common/placer1.cc
+++ b/common/placer1.cc
@@ -236,7 +236,10 @@ class SAPlacer
                 temp = post_legalise_temp;
                 diameter *= post_legalise_dia_scale;
                 ctx->shuffle(autoplaced);
-                assign_budget(ctx);
+
+                // Legalisation is a big change so force a slack redistribution here
+                if (ctx->slack_redist_iter > 0)
+                    assign_budget(ctx, true /* quiet */);
             } else if (ctx->slack_redist_iter > 0 && iter % ctx->slack_redist_iter == 0) {
                 assign_budget(ctx, true /* quiet */);
             }
diff --git a/common/project.cc b/common/project.cc
new file mode 100644
index 00000000..244ca761
--- /dev/null
+++ b/common/project.cc
@@ -0,0 +1,86 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Miodrag Milanovic <miodrag@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.
+ *
+ */
+
+#include "project.h"
+#include <boost/filesystem/convenience.hpp>
+#include <boost/property_tree/json_parser.hpp>
+#include <fstream>
+#include "jsonparse.h"
+#include "log.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+void ProjectHandler::save(Context *ctx, std::string filename)
+{
+    std::ofstream f(filename);
+    pt::ptree root;
+    root.put("project.version", 1);
+    root.put("project.name", boost::filesystem::basename(filename));
+    root.put("project.arch.name", ctx->archId().c_str(ctx));
+    root.put("project.arch.type", ctx->archArgsToId(ctx->archArgs()).c_str(ctx));
+    /*  root.put("project.input.json", );*/
+    root.put("project.params.freq", int(ctx->target_freq / 1e6));
+    root.put("project.params.seed", ctx->rngstate);
+    saveArch(ctx, root);
+    pt::write_json(f, root);
+}
+
+std::unique_ptr<Context> ProjectHandler::load(std::string filename)
+{
+    std::unique_ptr<Context> ctx;
+    try {
+        pt::ptree root;
+        boost::filesystem::path proj(filename);
+        pt::read_json(filename, root);
+        log_info("Loading project %s...\n", filename.c_str());
+        log_break();
+
+        int version = root.get<int>("project.version");
+        if (version != 1)
+            log_error("Wrong project format version.\n");
+
+        ctx = createContext(root);
+
+        std::string arch_name = root.get<std::string>("project.arch.name");
+        if (arch_name != ctx->archId().c_str(ctx.get()))
+            log_error("Unsuported project architecture.\n");
+
+        auto project = root.get_child("project");
+        auto input = project.get_child("input");
+        std::string filename = input.get<std::string>("json");
+        boost::filesystem::path json = proj.parent_path() / filename;
+        std::ifstream f(json.string());
+        if (!parse_json_file(f, filename, ctx.get()))
+            log_error("Loading design failed.\n");
+
+        if (project.count("params")) {
+            auto params = project.get_child("params");
+            if (params.count("freq"))
+                ctx->target_freq = params.get<double>("freq") * 1e6;
+            if (params.count("seed"))
+                ctx->rngseed(params.get<uint64_t>("seed"));
+        }
+        loadArch(ctx.get(), root, proj.parent_path().string());
+    } catch (...) {
+        log_error("Error loading project file.\n");
+    }
+    return ctx;
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/common/project.h b/common/project.h
new file mode 100644
index 00000000..14f03ecd
--- /dev/null
+++ b/common/project.h
@@ -0,0 +1,42 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2018  Miodrag Milanovic <miodrag@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 PROJECT_H
+#define PROJECT_H
+
+#include <boost/property_tree/ptree.hpp>
+#include "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+namespace pt = boost::property_tree;
+
+struct ProjectHandler
+{
+    void save(Context *ctx, std::string filename);
+    std::unique_ptr<Context> load(std::string filename);
+    // implemented per arch
+    void saveArch(Context *ctx, pt::ptree &root);
+    std::unique_ptr<Context> createContext(pt::ptree &root);
+    void loadArch(Context *ctx, pt::ptree &root, std::string path);
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif // PROJECT_H
diff --git a/common/timing.cc b/common/timing.cc
index c00e1ba5..aadd8381 100644
--- a/common/timing.cc
+++ b/common/timing.cc
@@ -20,6 +20,7 @@
 
 #include "timing.h"
 #include <algorithm>
+#include <boost/range/adaptor/reversed.hpp>
 #include <unordered_map>
 #include <utility>
 #include "log.h"
@@ -36,10 +37,18 @@ struct Timing
     bool net_delays;
     bool update;
     delay_t min_slack;
-    PortRefVector current_path;
     PortRefVector *crit_path;
     DelayFrequency *slack_histogram;
 
+    struct TimingData
+    {
+        TimingData() : max_arrival(), max_path_length(), min_remaining_budget() {}
+        TimingData(delay_t max_arrival) : max_arrival(max_arrival), max_path_length(), min_remaining_budget() {}
+        delay_t max_arrival;
+        unsigned max_path_length = 0;
+        delay_t min_remaining_budget;
+    };
+
     Timing(Context *ctx, bool net_delays, bool update, PortRefVector *crit_path = nullptr,
            DelayFrequency *slack_histogram = nullptr)
             : ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->target_freq),
@@ -47,93 +56,246 @@ struct Timing
     {
     }
 
-    delay_t follow_net(NetInfo *net, int path_length, delay_t slack)
+    delay_t walk_paths()
     {
-        const delay_t default_budget = slack / (path_length + 1);
-        delay_t net_budget = default_budget;
-        for (auto &usr : net->users) {
-            auto delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
-            if (crit_path)
-                current_path.push_back(&usr);
-            // If budget override exists, use that value and do not increment path_length
-            auto budget = default_budget;
-            if (ctx->getBudgetOverride(net, usr, budget)) {
-                if (update)
-                    usr.budget = std::min(usr.budget, budget);
-                budget = follow_user_port(usr, path_length, slack - budget);
-                net_budget = std::min(net_budget, budget);
+        const auto clk_period = delay_t(1.0e12 / ctx->target_freq);
+
+        // First, compute the topographical order of nets to walk through the circuit, assuming it is a _acyclic_ graph
+        // TODO(eddieh): Handle the case where it is cyclic, e.g. combinatorial loops
+        std::vector<NetInfo *> topographical_order;
+        std::unordered_map<const NetInfo *, TimingData> net_data;
+        // In lieu of deleting edges from the graph, simply count the number of fanins to each output port
+        std::unordered_map<const PortInfo *, unsigned> port_fanin;
+
+        std::vector<IdString> input_ports;
+        std::vector<const PortInfo *> output_ports;
+        for (auto &cell : ctx->cells) {
+            input_ports.clear();
+            output_ports.clear();
+            for (auto &port : cell.second->ports) {
+                if (!port.second.net)
+                    continue;
+                if (port.second.type == PORT_OUT)
+                    output_ports.push_back(&port.second);
+                else
+                    input_ports.push_back(port.first);
             }
-            else {
-                budget = follow_user_port(usr, path_length + 1, slack - delay);
-                net_budget = std::min(net_budget, budget);
-                if (update)
-                    usr.budget = std::min(usr.budget, delay + budget);
+
+            for (auto o : output_ports) {
+                IdString clockPort;
+                TimingPortClass portClass = ctx->getPortTimingClass(cell.second.get(), o->name, clockPort);
+                // If output port is influenced by a clock (e.g. FF output) then add it to the ordering as a timing
+                // start-point
+                if (portClass == TMG_REGISTER_OUTPUT) {
+                    DelayInfo clkToQ;
+                    ctx->getCellDelay(cell.second.get(), clockPort, o->name, clkToQ);
+                    topographical_order.emplace_back(o->net);
+                    net_data.emplace(o->net, TimingData{clkToQ.maxDelay()});
+                } else {
+                    // TODO(eddieh): Generated clocks and ignored ports are currently added into the ordering as if it
+                    // was a regular timing start point in order to enable the full topographical order to be computed,
+                    // however these false nets (and their downstream paths) should not be in the final ordering
+                    if (portClass == TMG_STARTPOINT || portClass == TMG_GEN_CLOCK || portClass == TMG_IGNORE) {
+                        topographical_order.emplace_back(o->net);
+                        net_data.emplace(o->net, TimingData{});
+                    }
+                    // Otherwise, for all driven input ports on this cell, if a timing arc exists between the input and
+                    // the current output port, increment fanin counter
+                    for (auto i : input_ports) {
+                        DelayInfo comb_delay;
+                        bool is_path = ctx->getCellDelay(cell.second.get(), i, o->name, comb_delay);
+                        if (is_path)
+                            port_fanin[o]++;
+                    }
+                }
             }
-            if (crit_path)
-                current_path.pop_back();
         }
-        return net_budget;
-    }
 
-    // Follow a path, returning budget to annotate
-    delay_t follow_user_port(PortRef &user, int path_length, delay_t slack)
-    {
-        delay_t value;
-        if (ctx->getPortClock(user.cell, user.port) != IdString()) {
-            // At the end of a timing path (arguably, should check setup time
-            // here too)
-            value = slack / path_length;
-            if (slack < min_slack) {
-                min_slack = slack;
-                if (crit_path)
-                    *crit_path = current_path;
+        // If these constant nets exist, add them to the topographical ordering too
+        // TODO(eddieh): Also false paths and should be removed from ordering
+        auto it = ctx->nets.find(ctx->id("$PACKER_VCC_NET"));
+        if (it != ctx->nets.end()) {
+            topographical_order.emplace_back(it->second.get());
+            net_data.emplace(it->second.get(), TimingData{});
+        }
+        it = ctx->nets.find(ctx->id("$PACKER_GND_NET"));
+        if (it != ctx->nets.end()) {
+            topographical_order.emplace_back(it->second.get());
+            net_data.emplace(it->second.get(), TimingData{});
+        }
+
+        std::deque<NetInfo *> queue(topographical_order.begin(), topographical_order.end());
+
+        // Now walk the design, from the start points identified previously, building up a topographical order
+        while (!queue.empty()) {
+            const auto net = queue.front();
+            queue.pop_front();
+
+            for (auto &usr : net->users) {
+                IdString clockPort;
+                TimingPortClass usrClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort);
+                if (usrClass == TMG_IGNORE || usrClass == TMG_CLOCK_INPUT)
+                    continue;
+                for (auto &port : usr.cell->ports) {
+                    if (port.second.type != PORT_OUT || !port.second.net)
+                        continue;
+                    TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, port.first, clockPort);
+
+                    // Skip if this is a clocked output (but allow non-clocked ones)
+                    if (portClass == TMG_REGISTER_OUTPUT || portClass == TMG_STARTPOINT || portClass == TMG_IGNORE ||
+                        portClass == TMG_GEN_CLOCK)
+                        continue;
+                    DelayInfo comb_delay;
+                    bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
+                    if (!is_path)
+                        continue;
+                    // Decrement the fanin count, and only add to topographical order if all its fanins have already
+                    // been visited
+                    auto it = port_fanin.find(&port.second);
+                    NPNR_ASSERT(it != port_fanin.end());
+                    if (--it->second == 0) {
+                        topographical_order.emplace_back(port.second.net);
+                        queue.emplace_back(port.second.net);
+                        port_fanin.erase(it);
+                    }
+                }
             }
-            if (slack_histogram) {
-                int slack_ps = ctx->getDelayNS(slack) * 1000;
-                (*slack_histogram)[slack_ps]++;
+        }
+
+        // Sanity check to ensure that all ports where fanins were recorded were indeed visited
+        NPNR_ASSERT(port_fanin.empty());
+
+        // Go forwards topographically to find the maximum arrival time and max path length for each net
+        for (auto net : topographical_order) {
+            auto &nd = net_data.at(net);
+            const auto net_arrival = nd.max_arrival;
+            const auto net_length_plus_one = nd.max_path_length + 1;
+            nd.min_remaining_budget = clk_period;
+            for (auto &usr : net->users) {
+                IdString clockPort;
+                TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, clockPort);
+                if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT || portClass == TMG_IGNORE) {
+                } else {
+                    auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
+                    auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
+                    auto usr_arrival = net_arrival + net_delay;
+                    // Iterate over all output ports on the same cell as the sink
+                    for (auto port : usr.cell->ports) {
+                        if (port.second.type != PORT_OUT || !port.second.net)
+                            continue;
+                        DelayInfo comb_delay;
+                        // Look up delay through this path
+                        bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
+                        if (!is_path)
+                            continue;
+                        auto &data = net_data[port.second.net];
+                        auto &arrival = data.max_arrival;
+                        arrival = std::max(arrival, usr_arrival + comb_delay.maxDelay());
+                        if (!budget_override) { // Do not increment path length if budget overriden since it doesn't
+                                                // require a share of the slack
+                            auto &path_length = data.max_path_length;
+                            path_length = std::max(path_length, net_length_plus_one);
+                        }
+                    }
+                }
             }
-        } else {
-            // Default to the path ending here, if no further paths found
-            value = slack / path_length;
-            // Follow outputs of the user
-            for (auto port : user.cell->ports) {
-                if (port.second.type == PORT_OUT) {
-                    DelayInfo comb_delay;
-                    // Look up delay through this path
-                    bool is_path = ctx->getCellDelay(user.cell, user.port, port.first, comb_delay);
-                    if (is_path) {
-                        NetInfo *net = port.second.net;
-                        if (net) {
-                            delay_t path_budget = follow_net(net, path_length, slack - comb_delay.maxDelay());
-                            value = std::min(value, path_budget);
+        }
+
+        const NetInfo *crit_net = nullptr;
+
+        // Now go backwards topographically to determine the minimum path slack, and to distribute all path slack evenly
+        // between all nets on the path
+        for (auto net : boost::adaptors::reverse(topographical_order)) {
+            auto &nd = net_data.at(net);
+            const delay_t net_length_plus_one = nd.max_path_length + 1;
+            auto &net_min_remaining_budget = nd.min_remaining_budget;
+            for (auto &usr : net->users) {
+                auto net_delay = net_delays ? ctx->getNetinfoRouteDelay(net, usr) : delay_t();
+                auto budget_override = ctx->getBudgetOverride(net, usr, net_delay);
+                IdString associatedClock;
+                TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, associatedClock);
+                if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) {
+                    const auto net_arrival = nd.max_arrival;
+                    auto path_budget = clk_period - (net_arrival + net_delay);
+                    if (update) {
+                        auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
+                        usr.budget = std::min(usr.budget, net_delay + budget_share);
+                        net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share);
+                    }
+
+                    if (path_budget < min_slack) {
+                        min_slack = path_budget;
+                        if (crit_path) {
+                            crit_path->clear();
+                            crit_path->push_back(&usr);
+                            crit_net = net;
                         }
                     }
+                    if (slack_histogram) {
+                        int slack_ps = ctx->getDelayNS(path_budget) * 1000;
+                        (*slack_histogram)[slack_ps]++;
+                    }
+                } else if (update) {
+                    // Iterate over all output ports on the same cell as the sink
+                    for (const auto &port : usr.cell->ports) {
+                        if (port.second.type != PORT_OUT || !port.second.net)
+                            continue;
+                        DelayInfo comb_delay;
+                        bool is_path = ctx->getCellDelay(usr.cell, usr.port, port.first, comb_delay);
+                        if (!is_path)
+                            continue;
+                        auto path_budget = net_data.at(port.second.net).min_remaining_budget;
+                        auto budget_share = budget_override ? 0 : path_budget / net_length_plus_one;
+                        usr.budget = std::min(usr.budget, net_delay + budget_share);
+                        net_min_remaining_budget = std::min(net_min_remaining_budget, path_budget - budget_share);
+                    }
                 }
             }
         }
-        return value;
-    }
 
-    delay_t walk_paths()
-    {
-        delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
+        if (crit_path) {
+            // Walk backwards from the most critical net
+            while (crit_net) {
+                const PortInfo *crit_ipin = nullptr;
+                delay_t max_arrival = std::numeric_limits<delay_t>::min();
 
-        // Go through all clocked drivers and distribute the available path
-        //   slack evenly into the budget of every sink on the path
-        for (auto &cell : ctx->cells) {
-            for (auto port : cell.second->ports) {
-                if (port.second.type == PORT_OUT) {
-                    IdString clock_domain = ctx->getPortClock(cell.second.get(), port.first);
-                    if (clock_domain != IdString()) {
-                        delay_t slack = default_slack; // TODO: clock constraints
-                        DelayInfo clkToQ;
-                        if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ))
-                            slack -= clkToQ.maxDelay();
-                        if (port.second.net)
-                            follow_net(port.second.net, 0, slack);
+                // Look at all input ports on its driving cell
+                for (const auto &port : crit_net->driver.cell->ports) {
+                    if (port.second.type != PORT_IN || !port.second.net)
+                        continue;
+                    DelayInfo comb_delay;
+                    bool is_path =
+                            ctx->getCellDelay(crit_net->driver.cell, port.first, crit_net->driver.port, comb_delay);
+                    if (!is_path)
+                        continue;
+                    // If input port is influenced by a clock, skip
+                    IdString portClock;
+                    TimingPortClass portClass = ctx->getPortTimingClass(crit_net->driver.cell, port.first, portClock);
+                    if (portClass == TMG_REGISTER_INPUT || portClass == TMG_CLOCK_INPUT || portClass == TMG_ENDPOINT ||
+                        portClass == TMG_IGNORE)
+                        continue;
+
+                    // And find the fanin net with the latest arrival time
+                    const auto net_arrival = net_data.at(port.second.net).max_arrival;
+                    if (net_arrival > max_arrival) {
+                        max_arrival = net_arrival;
+                        crit_ipin = &port.second;
                     }
                 }
+
+                if (!crit_ipin)
+                    break;
+
+                // Now convert PortInfo* into a PortRef*
+                for (auto &usr : crit_ipin->net->users) {
+                    if (usr.cell->name == crit_net->driver.cell->name && usr.port == crit_ipin->name) {
+                        crit_path->push_back(&usr);
+                        break;
+                    }
+                }
+                crit_net = crit_ipin->net;
             }
+            std::reverse(crit_path->begin(), crit_path->end());
         }
         return min_slack;
     }
@@ -141,10 +303,9 @@ struct Timing
     void assign_budget()
     {
         // Clear delays to a very high value first
-        delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
         for (auto &net : ctx->nets) {
             for (auto &usr : net.second->users) {
-                usr.budget = default_slack;
+                usr.budget = std::numeric_limits<delay_t>::max();
             }
         }
 
@@ -180,16 +341,15 @@ void assign_budget(Context *ctx, bool quiet)
         }
     }
 
-    // For slack redistribution, if user has not specified a frequency
-    //   dynamically adjust the target frequency to be the currently
-    //   achieved maximum
+    // For slack redistribution, if user has not specified a frequency dynamically adjust the target frequency to be the
+    // currently achieved maximum
     if (ctx->auto_freq && ctx->slack_redist_iter > 0) {
-        delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
-        ctx->target_freq = 1e12 / (default_slack - timing.min_slack);
+        delay_t default_slack = delay_t((1.0e9 / ctx->getDelayNS(1)) / ctx->target_freq);
+        ctx->target_freq = 1.0e9 / ctx->getDelayNS(default_slack - timing.min_slack);
         if (ctx->verbose)
-            log_info("minimum slack for this assign = %d, target Fmax for next "
+            log_info("minimum slack for this assign = %.2f ns, target Fmax for next "
                      "update = %.2f MHz\n",
-                     timing.min_slack, ctx->target_freq / 1e6);
+                     ctx->getDelayNS(timing.min_slack), ctx->target_freq / 1e6);
     }
 
     if (!quiet)
@@ -217,7 +377,9 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
             auto &front = crit_path.front();
             auto &front_port = front->cell->ports.at(front->port);
             auto &front_driver = front_port.net->driver;
-            auto last_port = ctx->getPortClock(front_driver.cell, front_driver.port);
+
+            IdString last_port;
+            ctx->getPortTimingClass(front_driver.cell, front_driver.port, last_port);
             for (auto sink : crit_path) {
                 auto sink_cell = sink->cell;
                 auto &port = sink_cell->ports.at(sink->port);
@@ -227,14 +389,15 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
                 DelayInfo comb_delay;
                 ctx->getCellDelay(sink_cell, last_port, driver.port, comb_delay);
                 total += comb_delay.maxDelay();
-                log_info("%4d %4d  Source %s.%s\n", comb_delay.maxDelay(), total, driver_cell->name.c_str(ctx),
-                         driver.port.c_str(ctx));
+                log_info("%4.1f %4.1f  Source %s.%s\n", ctx->getDelayNS(comb_delay.maxDelay()), ctx->getDelayNS(total),
+                         driver_cell->name.c_str(ctx), driver.port.c_str(ctx));
                 auto net_delay = ctx->getNetinfoRouteDelay(net, *sink);
                 total += net_delay;
                 auto driver_loc = ctx->getBelLocation(driver_cell->bel);
                 auto sink_loc = ctx->getBelLocation(sink_cell->bel);
-                log_info("%4d %4d    Net %s budget %d (%d,%d) -> (%d,%d)\n", net_delay, total, net->name.c_str(ctx),
-                         sink->budget, driver_loc.x, driver_loc.y, sink_loc.x, sink_loc.y);
+                log_info("%4.1f %4.1f    Net %s budget %f ns (%d,%d) -> (%d,%d)\n", ctx->getDelayNS(net_delay),
+                         ctx->getDelayNS(total), net->name.c_str(ctx), ctx->getDelayNS(sink->budget), driver_loc.x,
+                         driver_loc.y, sink_loc.x, sink_loc.y);
                 log_info("                Sink %s.%s\n", sink_cell->name.c_str(ctx), sink->port.c_str(ctx));
                 last_port = sink->port;
             }
@@ -242,8 +405,8 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_path)
         }
     }
 
-    delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
-    log_info("estimated Fmax = %.2f MHz\n", 1e6 / (default_slack - min_slack));
+    delay_t default_slack = delay_t((1.0e9 / ctx->getDelayNS(1)) / ctx->target_freq);
+    log_info("estimated Fmax = %.2f MHz\n", 1e3 / ctx->getDelayNS(default_slack - min_slack));
 
     if (print_histogram && slack_histogram.size() > 0) {
         constexpr unsigned num_bins = 20;