<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 "place_legaliser.h"
#include <algorithm>
#include <vector>
#include "cells.h"
#include "design_utils.h"
#include "log.h"
#include "place_common.h"
#include "util.h"

NEXTPNR_NAMESPACE_BEGIN

struct CellChain
{
    std::vector<CellInfo *> cells;
    float mid_x = 0, mid_y = 0;
};

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

static void get_chain_midpoint(const Context *ctx, const CellChain &chain, float &x, float &y)
{
    float total_x = 0, total_y = 0;
    int N = 0;
    for (auto cell : chain.cells) {
        if (cell->bel == BelId())
            continue;
        int bel_x, bel_y;
        bool bel_gb;
        ctx->estimatePosition(cell->bel, bel_x, bel_y, bel_gb);
        total_x += bel_x;
        total_y += bel_y;
        N++;
    }
    assert(N > 0);
    x = total_x / N;
    y = total_y / N;
}

class PlacementLegaliser
{
  public:
    PlacementLegaliser(Context *ctx) : ctx(ctx){};

    bool legalise()
    {
        log_info("Legalising design..\n");
        init_logic_cells();
        bool legalised_carries = legalise_carries();
        if (!legalised_carries && !ctx->force)
            return false;
        bool replaced_cells = replace_cells();
        return legalised_carries && replaced_cells;
    }

  private:
    void init_logic_cells()
    {
        for (auto bel : ctx->getBels()) {
            // Initialise the logic bels vector with unavailable invalid bels, dimensions [0..width][0..height[0..7]
            logic_bels.resize(ctx->chip_info->width + 1,
                              std::vector<std::vector<std::pair<BelId, bool>>>(
                                      ctx->chip_info->height + 1,
                                      std::vector<std::pair<BelId, bool>>(8, std::make_pair(BelId(), true))));
            if (ctx->getBelType(bel) == TYPE_ICESTORM_LC) {
                // Using the non-standard API here to get (x, y, z) rather than just (x, y)
                auto bi = ctx->chip_info->bel_data[bel.index];
                int x = bi.x, y = bi.y, z = bi.z;
                IdString cell = ctx->getBoundBelCell(bel);
                if (cell != IdString() && ctx->cells.at(cell)->belStrength >= STRENGTH_FIXED)
                    logic_bels.at(x).at(y).at(z) = std::make_pair(bel, true); // locked out of use
                else
                    logic_bels.at(x).at(y).at(z) = std::make_pair(bel, false); // available
            }
        }
    }

    bool legalise_carries()
    {
        std::vector<CellChain> carry_chains = find_chains(
                ctx, is_lc,
                [](const Context *ctx, const CellInfo *cell) {
                    CellInfo *carry_prev =
                            net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT"));
                    if (carry_prev != nullptr)
                        return carry_prev;
                    CellInfo *i3_prev = net_driven_by(ctx, cell->ports.at(ctx->id("I3")).net, is_lc, ctx->id("COUT"));
                    if (i3_prev != nullptr)
                        return i3_prev;
                    return (CellInfo *)nullptr;
                },
                [](const Context *ctx, const CellInfo *cell) {
                    CellInfo *carry_next =
                            net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false);
                    if (carry_next != nullptr)
                        return carry_next;
                    CellInfo *i3_next =
                            net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("I3"), false);
                    if (i3_next != nullptr)
                        return i3_next;
                    return (CellInfo *)nullptr;
                });
        bool success = true;
        // Find midpoints for all chains, before we start tearing them up
        std::vector<CellChain> all_chains;
        for (auto &base_chain : carry_chains) {
            if (ctx->verbose) {
                log_info("Found carry chain: \n");
                for (auto entry : base_chain.cells)
                    log_info("     %s\n", entry->name.c_str(ctx));
                log_info("\n");
            }
            std::vector<CellChain> split_chains = split_carry_chain(base_chain);
            for (auto &chain : split_chains) {
                get_chain_midpoint(ctx, chain, chain.mid_x, chain.mid_y);<commit_msg>Debugging carry legalisation<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 "place_legaliser.h"
#include <algorithm>
#include <vector>
#include "cells.h"
#include "design_utils.h"
#include "log.h"
#include "place_common.h"
#include "util.h"

NEXTPNR_NAMESPACE_BEGIN

struct CellChain
{
    std::vector<CellInfo *> cells;
    float mid_x = 0, mid_y = 0;
};

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

static void get_chain_midpoint(const Context *ctx, const CellChain &chain, float &x, float &y)
{
    float total_x = 0, total_y = 0;
    int N = 0;
    for (auto cell : chain.cells) {
        if (cell->bel == BelId())
            continue;
        int bel_x, bel_y;
        bool bel_gb;
        ctx->estimatePosition(cell->bel, bel_x, bel_y, bel_gb);
        total_x += bel_x;
        total_y += bel_y;
        N++;
    }
    assert(N > 0);
    x = total_x / N;
    y = total_y / N;
}

class PlacementLegaliser
{
  public:
    PlacementLegaliser(Context *ctx) : ctx(ctx){};

    bool legalise()
    {
        log_info("Legalising design..\n");
        init_logic_cells();
        bool legalised_carries = legalise_carries();
        if (!legalised_carries && !ctx->force)
            return false;
        bool replaced_cells = replace_cells();
        return legalised_carries && replaced_cells;
    }

  private:
    void init_logic_cells()
    {
        for (auto bel : ctx->getBels()) {
            // Initialise the logic bels vector with unavailable invalid bels, dimensions [0..width][0..height[0..7]
            logic_bels.resize(ctx->chip_info->width + 1,
                              std::vector<std::vector<std::pair<BelId, bool>>>(
                                      ctx->chip_info->height + 1,
                                      std::vector<std::pair<BelId, bool>>(8, std::make_pair(BelId(), true))));
            if (ctx->getBelType(bel) == TYPE_ICESTORM_LC) {
                // Using the non-standard API here to get (x, y, z) rather than just (x, y)
                auto bi = ctx->chip_info->bel_data[bel.index];
                int x = bi.x, y = bi.y, z = bi.z;
                IdString cell = ctx->getBoundBelCell(bel);
                if (cell != IdString() && ctx->cells.at(cell)->belStrength >= STRENGTH_FIXED)
                    logic_bels.at(x).at(y).at(z) = std::make_pair(bel, true); // locked out of use
                else
                    logic_bels.at(x).at(y).at(z) = std::make_pair(bel, false); // available
            }
        }
    }

    bool legalise_carries()
    {
        std::vector<CellChain> carry_chains = find_chains(
                ctx,
                [](const Context *ctx, const CellInfo *cell) {
                    return is_lc(ctx, cell);
                },
                [](const Context *ctx, const

                CellInfo *cell) {
                    CellInfo *carry_prev =
                            net_driven_by(ctx, cell->ports.at(ctx->id("CIN")).net, is_lc, ctx->id("COUT"));
                    if (carry_prev != nullptr)
                        return carry_prev;
                    /*CellInfo *i3_prev = net_driven_by(ctx, cell->ports.at(ctx->id("I3")).net, is_lc, ctx->id("COUT"));
                    if (i3_prev != nullptr)
                        return i3_prev;*/
                    return (CellInfo *)nullptr;
                },
                [](const Context *ctx, const CellInfo *cell) {
                    CellInfo *carry_next =
                            net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("CIN"), false);
                    if (carry_next != nullptr)
                        return carry_next;
                    /*CellInfo *i3_next =
                            net_only_drives(ctx, cell->ports.at(ctx->id("COUT")).net, is_lc, ctx->id("I3"), false);
                    if (i3_next != nullptr)
                        return i3_next;*/
                    return (CellInfo *)nullptr;
                });
        bool success = true;
        // Find midpoints for all chains, before we start tearing them up
        std::vector<CellChain> all_chains;
        for (auto &base_chain : carry_chains) {
            if (ctx->verbose) {
                log_info("Found carry chain: \n");
                for (auto entry : base_chain.cells)
                    log_info("     %s\n", entry->name.c_str(ctx));
                log_info("\n");
            }
            std::vector<CellChain> split_chains = split_carry_chain(base_chain);
            for (auto &chain : split_chains) {
                get_chain_midpoint(ctx, chain, chain.mid_x, chain.mid_y);
{'fraction_non_alphanumeric': 0.11670285359801488, 'fraction_numerical': 0.004962779156327543, 'mean_word_length': 1.8208661417322836, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 107, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2938983', 'n_tokens_mistral': 3998, 'n_tokens_neox': 3764, 'n_words': 997}