<commit_before>/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2018  <NAME> <<EMAIL>>
 *
 *  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 "timing.h"
#include <algorithm>
#include <unordered_map>
#include <utility>
#include "log.h"
#include "util.h"

NEXTPNR_NAMESPACE_BEGIN

typedef std::list<const PortRef *> PortRefList;

static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
                          PortRefList *current_path, PortRefList *crit_path);

// Follow a path, returning budget to annotate
static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, bool update,
                                delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path)
{
    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;
        }
    } 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) {
                delay_t 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(ctx, net, path_length, slack - comb_delay, update, min_slack,
                                                         current_path, crit_path);
                        value = std::min(value, path_budget);
                    }
                }
            }
        }
    }
    return value;
}

static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
                          PortRefList *current_path, PortRefList *crit_path)
{
    delay_t net_budget = slack / (path_length + 1);
    for (unsigned i = 0; i < net->users.size(); ++i) {
        auto &usr = net->users[i];
        if (crit_path)
            current_path->push_back(&usr);
        // If budget override is less than existing budget, then do not increment path length
        int pl = path_length + 1;
        auto budget = ctx->getBudgetOverride(net, i, net_budget);
        if (budget < net_budget) {
            net_budget = budget;
            pl = std::max(1, path_length);
        }
        auto delay = ctx->getNetinfoRouteDelay(net, i);
        net_budget = std::min(
                net_budget, follow_user_port(ctx, usr, pl, slack - delay, update, min_slack, current_path, crit_path));
        if (update)
            usr.budget = std::min(usr.budget, delay + net_budget);
        if (crit_path)
            current_path->pop_back();
    }
    return net_budget;
}

static delay_t walk_paths(Context *ctx, bool update, PortRefList *crit_path)
{
    delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
    delay_t min_slack = default_slack;

    PortRefList current_path;

    // Go through all clocked drivers and distribute the available path
    //   slack evenly into the budget of every sink on the path ---
    //   record this value into the UpdateMap
    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
                    delay_t clkToQ;
                    if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ))
                        slack -= clkToQ;
                    if (port.second.net)
                        follow_net(ctx, port.second.net, 0, slack, update, min_slack, &current_path, crit_path);
                }
            }
        }
    }

    return min_slack;
}

void assign_budget(Context *ctx, bool quiet)
{
    if (!quiet) {
        log_break();
        log_info("Annotating ports with timing budgets\n");
    }

    // 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;
        }
    }

    delay_t min_slack = walk_paths(ctx, true, nullptr);

    if (!quiet || ctx->verbose) {
        for (auto &net : ctx->nets) {
            for (auto &user : net.second->users) {
                // Post-update check
                if (ctx->user_freq && user.budget < 0)
                    log_warning("port %s.%s, connected to net '%s', has negative "
                                "timing budget of %fns\n",
                                user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
                                ctx->getDelayNS(user.budget));
                else if (ctx->verbose)
                    log_info("port %s.%s, connected to net '%s', has "
                             "timing budget of %fns\n",
                             user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
                             ctx->getDelayNS(user.budget));
            }
        }
    }

    // If user has not specified a frequency, adjust the target frequency dynamically
    // TODO(eddieh): Tune these factors
    if (!ctx->user_freq) {
        if (min_slack < 0)
            ctx->target_freq = 1e12 / (default_slack - 0.95 * min_slack);
        else
            ctx->target_freq = 1e12 / (default_slack - 1.2 * min_slack);
        if (ctx->verbose)
            log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack,
                     ctx->target_freq / 1e6);
    }

    if (!quiet)
        log_info("Checksum: 0x%08x\n", ctx->checksum());
}

delay_t timing_analysis(Context *ctx, bool print_fmax, bool print_path)<commit_msg>Keep things simple by not overconstraining Fmax<commit_after>/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2018  <NAME> <<EMAIL>>
 *
 *  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 "timing.h"
#include <algorithm>
#include <unordered_map>
#include <utility>
#include "log.h"
#include "util.h"

NEXTPNR_NAMESPACE_BEGIN

typedef std::list<const PortRef *> PortRefList;

static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
                          PortRefList *current_path, PortRefList *crit_path);

// Follow a path, returning budget to annotate
static delay_t follow_user_port(Context *ctx, PortRef &user, int path_length, delay_t slack, bool update,
                                delay_t &min_slack, PortRefList *current_path, PortRefList *crit_path)
{
    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;
        }
    } 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) {
                delay_t 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(ctx, net, path_length, slack - comb_delay, update, min_slack,
                                                         current_path, crit_path);
                        value = std::min(value, path_budget);
                    }
                }
            }
        }
    }
    return value;
}

static delay_t follow_net(Context *ctx, NetInfo *net, int path_length, delay_t slack, bool update, delay_t &min_slack,
                          PortRefList *current_path, PortRefList *crit_path)
{
    delay_t net_budget = slack / (path_length + 1);
    for (unsigned i = 0; i < net->users.size(); ++i) {
        auto &usr = net->users[i];
        if (crit_path)
            current_path->push_back(&usr);
        // If budget override is less than existing budget, then do not increment path length
        int pl = path_length + 1;
        auto budget = ctx->getBudgetOverride(net, i, net_budget);
        if (budget < net_budget) {
            net_budget = budget;
            pl = std::max(1, path_length);
        }
        auto delay = ctx->getNetinfoRouteDelay(net, i);
        net_budget = std::min(
                net_budget, follow_user_port(ctx, usr, pl, slack - delay, update, min_slack, current_path, crit_path));
        if (update)
            usr.budget = std::min(usr.budget, delay + net_budget);
        if (crit_path)
            current_path->pop_back();
    }
    return net_budget;
}

static delay_t walk_paths(Context *ctx, bool update, PortRefList *crit_path)
{
    delay_t default_slack = delay_t(1.0e12 / ctx->target_freq);
    delay_t min_slack = default_slack;

    PortRefList current_path;

    // Go through all clocked drivers and distribute the available path
    //   slack evenly into the budget of every sink on the path ---
    //   record this value into the UpdateMap
    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
                    delay_t clkToQ;
                    if (ctx->getCellDelay(cell.second.get(), clock_domain, port.first, clkToQ))
                        slack -= clkToQ;
                    if (port.second.net)
                        follow_net(ctx, port.second.net, 0, slack, update, min_slack, &current_path, crit_path);
                }
            }
        }
    }

    return min_slack;
}

void assign_budget(Context *ctx, bool quiet)
{
    if (!quiet) {
        log_break();
        log_info("Annotating ports with timing budgets\n");
    }

    // 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;
        }
    }

    delay_t min_slack = walk_paths(ctx, true, nullptr);

    if (!quiet || ctx->verbose) {
        for (auto &net : ctx->nets) {
            for (auto &user : net.second->users) {
                // Post-update check
                if (ctx->user_freq && user.budget < 0)
                    log_warning("port %s.%s, connected to net '%s', has negative "
                                "timing budget of %fns\n",
                                user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
                                ctx->getDelayNS(user.budget));
                else if (ctx->verbose)
                    log_info("port %s.%s, connected to net '%s', has "
                             "timing budget of %fns\n",
                             user.cell->name.c_str(ctx), user.port.c_str(ctx), net.first.c_str(ctx),
                             ctx->getDelayNS(user.budget));
            }
        }
    }

    // If user has not specified a frequency, dynamically adjust the target 
    //   frequency to be the current maximum
    if (!ctx->user_freq) {
        ctx->target_freq = 1e12 / (default_slack - 1.2 * min_slack);
        if (ctx->verbose)
            log_info("minimum slack for this assign = %d, target Fmax for next update = %.2f MHz\n", min_slack,
                     ctx->target_freq / 1e6);
    }

    if (!quiet)
        log_info("Checksum: 0x%08x\n", ctx->checksum());
}

delay_t timing_analysis(Context *ctx, bool print_fmax, bool print_path)
{'fraction_non_alphanumeric': 0.10116842405243659, 'fraction_numerical': 0.004630948988315759, 'mean_word_length': 1.9657722374815128, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 80, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7509544', 'n_tokens_mistral': 4304, 'n_tokens_neox': 4081, 'n_words': 1227}