From 26c68c4bcc388d49142e2c59d252abdd5daf4ec5 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 10:31:03 +0200 Subject: Remove old place legaliser, set placement constraints instead (currently ignored by placer) Signed-off-by: David Shah --- common/placer1.cc | 4 +- ecp5/config.h | 2 +- ecp5/place_legaliser.cc | 26 --- ecp5/place_legaliser.h | 31 --- generic/place_legaliser.cc | 26 --- generic/place_legaliser.h | 31 --- ice40/chains.cc | 282 +++++++++++++++++++++++ ice40/chains.h | 27 +++ ice40/main.cc | 1 - ice40/place_legaliser.cc | 554 --------------------------------------------- ice40/place_legaliser.h | 31 --- 11 files changed, 312 insertions(+), 703 deletions(-) delete mode 100644 ecp5/place_legaliser.cc delete mode 100644 ecp5/place_legaliser.h delete mode 100644 generic/place_legaliser.cc delete mode 100644 generic/place_legaliser.h create mode 100644 ice40/chains.cc create mode 100644 ice40/chains.h delete mode 100644 ice40/place_legaliser.cc delete mode 100644 ice40/place_legaliser.h diff --git a/common/placer1.cc b/common/placer1.cc index fc679b50..3a25f42c 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -38,7 +38,6 @@ #include #include "log.h" #include "place_common.h" -#include "place_legaliser.h" #include "timing.h" #include "util.h" NEXTPNR_NAMESPACE_BEGIN @@ -225,7 +224,8 @@ class SAPlacer // Once cooled below legalise threshold, run legalisation and start requiring // legal moves only if (temp < legalise_temp && !require_legal) { - legalise_design(ctx); + // legalise_design(ctx); + // FIXME require_legal = true; autoplaced.clear(); for (auto cell : sorted(ctx->cells)) { diff --git a/ecp5/config.h b/ecp5/config.h index 038ddbf0..3d2ef971 100644 --- a/ecp5/config.h +++ b/ecp5/config.h @@ -20,8 +20,8 @@ #ifndef ECP5_CONFIG_H #define ECP5_CONFIG_H -#include "nextpnr.h" #include +#include "nextpnr.h" NEXTPNR_NAMESPACE_BEGIN diff --git a/ecp5/place_legaliser.cc b/ecp5/place_legaliser.cc deleted file mode 100644 index 0d23f15b..00000000 --- a/ecp5/place_legaliser.cc +++ /dev/null @@ -1,26 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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" - -NEXTPNR_NAMESPACE_BEGIN - -bool legalise_design(Context *ctx) { return true; } - -NEXTPNR_NAMESPACE_END diff --git a/ecp5/place_legaliser.h b/ecp5/place_legaliser.h deleted file mode 100644 index 5f4df6aa..00000000 --- a/ecp5/place_legaliser.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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 PLACE_LEGALISER_H -#define PLACE_LEGALISER_H - -#include "nextpnr.h" - -NEXTPNR_NAMESPACE_BEGIN - -bool legalise_design(Context *ctx); - -NEXTPNR_NAMESPACE_END - -#endif diff --git a/generic/place_legaliser.cc b/generic/place_legaliser.cc deleted file mode 100644 index 0d23f15b..00000000 --- a/generic/place_legaliser.cc +++ /dev/null @@ -1,26 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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" - -NEXTPNR_NAMESPACE_BEGIN - -bool legalise_design(Context *ctx) { return true; } - -NEXTPNR_NAMESPACE_END diff --git a/generic/place_legaliser.h b/generic/place_legaliser.h deleted file mode 100644 index 5f4df6aa..00000000 --- a/generic/place_legaliser.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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 PLACE_LEGALISER_H -#define PLACE_LEGALISER_H - -#include "nextpnr.h" - -NEXTPNR_NAMESPACE_BEGIN - -bool legalise_design(Context *ctx); - -NEXTPNR_NAMESPACE_END - -#endif diff --git a/ice40/chains.cc b/ice40/chains.cc new file mode 100644 index 00000000..5b834c07 --- /dev/null +++ b/ice40/chains.cc @@ -0,0 +1,282 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 David Shah + * + * 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 "chains.h" +#include +#include +#include "cells.h" +#include "design_utils.h" +#include "log.h" +#include "place_common.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +struct CellChain +{ + std::vector cells; +}; + +// Generic chain finder +template +std::vector find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next, + size_t min_length = 2) +{ + std::set chained; + std::vector 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; +} + +class ChainConstrainer +{ + private: + Context *ctx; + // Split a carry chain into multiple legal chains + std::vector split_carry_chain(CellChain &carryc) + { + bool start_of_chain = true; + std::vector chains; + std::vector tile; + const int max_length = (ctx->chip_info->height - 2) * 8 - 2; + auto curr_cell = carryc.cells.begin(); + while (curr_cell != carryc.cells.end()) { + CellInfo *cell = *curr_cell; + if (tile.size() >= 8) { + tile.clear(); + } + if (start_of_chain) { + tile.clear(); + chains.emplace_back(); + start_of_chain = false; + if (cell->ports.at(ctx->id("CIN")).net) { + // CIN is not constant and not part of a chain. Must feed in from fabric + CellInfo *feedin = make_carry_feed_in(cell, cell->ports.at(ctx->id("CIN"))); + chains.back().cells.push_back(feedin); + tile.push_back(feedin); + } + } + tile.push_back(cell); + chains.back().cells.push_back(cell); + bool split_chain = (!ctx->logicCellsCompatible(tile)) || (int(chains.back().cells.size()) > max_length); + if (split_chain) { + CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); + tile.pop_back(); + chains.back().cells.back() = passout; + start_of_chain = true; + } else { + NetInfo *carry_net = cell->ports.at(ctx->id("COUT")).net; + bool at_end = (curr_cell == carryc.cells.end() - 1); + if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) { + if (carry_net->users.size() > 2 || + (net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), false) != + net_only_drives(ctx, carry_net, is_lc, ctx->id("CIN"), false)) || + (at_end && !net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), true))) { + CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); + chains.back().cells.push_back(passout); + tile.push_back(passout); + start_of_chain = true; + } + } + ++curr_cell; + } + } + return chains; + } + + // Insert a logic cell to legalise a COUT->fabric connection + CellInfo *make_carry_pass_out(PortInfo &cout_port) + { + NPNR_ASSERT(cout_port.net != nullptr); + std::unique_ptr lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); + lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3 + lc->params[ctx->id("CARRY_ENABLE")] = "1"; + lc->ports.at(ctx->id("O")).net = cout_port.net; + std::unique_ptr co_i3_net(new NetInfo()); + co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3"); + co_i3_net->driver = cout_port.net->driver; + PortRef i3_r; + i3_r.port = ctx->id("I3"); + i3_r.cell = lc.get(); + co_i3_net->users.push_back(i3_r); + PortRef o_r; + o_r.port = ctx->id("O"); + o_r.cell = lc.get(); + cout_port.net->driver = o_r; + lc->ports.at(ctx->id("I3")).net = co_i3_net.get(); + cout_port.net = co_i3_net.get(); + + IdString co_i3_name = co_i3_net->name; + NPNR_ASSERT(ctx->nets.find(co_i3_name) == ctx->nets.end()); + ctx->nets[co_i3_name] = std::move(co_i3_net); + IdString name = lc->name; + ctx->assignCellInfo(lc.get()); + ctx->cells[lc->name] = std::move(lc); + return ctx->cells[name].get(); + } + + // Insert a logic cell to legalise a CIN->fabric connection + CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port) + { + NPNR_ASSERT(cin_port.net != nullptr); + std::unique_ptr lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); + lc->params[ctx->id("CARRY_ENABLE")] = "1"; + lc->params[ctx->id("CIN_CONST")] = "1"; + lc->params[ctx->id("CIN_SET")] = "1"; + lc->ports.at(ctx->id("I1")).net = cin_port.net; + cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(), + [cin_cell, cin_port](const PortRef &usr) { + return usr.cell == cin_cell && usr.port == cin_port.name; + })); + + PortRef i1_ref; + i1_ref.cell = lc.get(); + i1_ref.port = ctx->id("I1"); + lc->ports.at(ctx->id("I1")).net->users.push_back(i1_ref); + + std::unique_ptr out_net(new NetInfo()); + out_net->name = ctx->id(lc->name.str(ctx) + "$O"); + + PortRef drv_ref; + drv_ref.port = ctx->id("COUT"); + drv_ref.cell = lc.get(); + out_net->driver = drv_ref; + lc->ports.at(ctx->id("COUT")).net = out_net.get(); + + PortRef usr_ref; + usr_ref.port = cin_port.name; + usr_ref.cell = cin_cell; + out_net->users.push_back(usr_ref); + cin_cell->ports.at(cin_port.name).net = out_net.get(); + + IdString out_net_name = out_net->name; + NPNR_ASSERT(ctx->nets.find(out_net_name) == ctx->nets.end()); + ctx->nets[out_net_name] = std::move(out_net); + + IdString name = lc->name; + ctx->assignCellInfo(lc.get()); + ctx->cells[lc->name] = std::move(lc); + return ctx->cells[name].get(); + } + + void process_carries() + { + std::vector 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; + }); + std::unordered_set chained; + for (auto &base_chain : carry_chains) { + for (auto c : base_chain.cells) + chained.insert(c->name); + } + // Any cells not in chains, but with carry enabled, must also be put in a single-carry chain + // for correct processing + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (chained.find(cell.first) == chained.end() && is_lc(ctx, ci) && + bool_or_default(ci->params, ctx->id("CARRY_ENABLE"))) { + CellChain sChain; + sChain.cells.push_back(ci); + chained.insert(cell.first); + carry_chains.push_back(sChain); + } + } + std::vector all_chains; + // Chain splitting + 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 split_chains = split_carry_chain(base_chain); + for (auto &chain : split_chains) { + all_chains.push_back(chain); + } + } + // Actual chain placement + for (auto &chain : all_chains) { + if (ctx->verbose) + log_info("Placing carry chain starting at '%s'\n", chain.cells.front()->name.c_str(ctx)); + + // Place carry chain + chain.cells.at(0)->constr_abs_z = 0; + for (int i = 1; i < int(chain.cells.size()); i++) { + chain.cells.at(i)->constr_x = 0; + chain.cells.at(i)->constr_y = (i / 8); + chain.cells.at(i)->constr_z = i % 8; + chain.cells.at(i)->constr_abs_z = true; + chain.cells.at(i)->constr_parent = chain.cells.at(0); + chain.cells.at(0)->constr_children.push_back(chain.cells.at(i)); + } + } + } + + public: + ChainConstrainer(Context *ctx) : ctx(ctx){}; + void constrain_chains() { process_carries(); } +}; + +void constrain_chains(Context *ctx) { ChainConstrainer(ctx).constrain_chains(); } + +NEXTPNR_NAMESPACE_END diff --git a/ice40/chains.h b/ice40/chains.h new file mode 100644 index 00000000..b466cb49 --- /dev/null +++ b/ice40/chains.h @@ -0,0 +1,27 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 David Shah + * + * 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 "nextpnr.h" + +NEXTPNR_NAMESPACE_BEGIN + +// This finds chains, inserts LCs to legalise them as needed, and sets relative constraints as appropriate +void constrain_chains(Context *ctx); + +NEXTPNR_NAMESPACE_END diff --git a/ice40/main.cc b/ice40/main.cc index 4a2e9532..41d264ad 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -40,7 +40,6 @@ #include "log.h" #include "nextpnr.h" #include "pcf.h" -#include "place_legaliser.h" #include "timing.h" #include "version.h" diff --git a/ice40/place_legaliser.cc b/ice40/place_legaliser.cc deleted file mode 100644 index a498e5f4..00000000 --- a/ice40/place_legaliser.cc +++ /dev/null @@ -1,554 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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 -#include -#include "cells.h" -#include "design_utils.h" -#include "log.h" -#include "place_common.h" -#include "util.h" - -NEXTPNR_NAMESPACE_BEGIN - -struct CellChain -{ - std::vector cells; - float mid_x = 0, mid_y = 0; -}; - -// Generic chain finder -template -std::vector find_chains(const Context *ctx, F1 cell_type_predicate, F2 get_previous, F3 get_next, - size_t min_length = 2) -{ - std::set chained; - std::vector 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; - Loc bel_loc = ctx->getBelLocation(cell->bel); - total_x += bel_loc.x; - total_y += bel_loc.y; - N++; - } - NPNR_ASSERT(N > 0); - x = total_x / N; - y = total_y / N; -} - -static int get_cell_evilness(const Context *ctx, const CellInfo *cell) -{ - // This returns how "evil" a logic cell is, and thus how likely it is to be ripped up - // during logic tile legalisation - int score = 0; - if (get_net_or_empty(cell, ctx->id_i0)) - ++score; - if (get_net_or_empty(cell, ctx->id_i1)) - ++score; - if (get_net_or_empty(cell, ctx->id_i2)) - ++score; - if (get_net_or_empty(cell, ctx->id_i3)) - ++score; - if (cell->lcInfo.dffEnable) { - if (cell->lcInfo.cen) - score += 10; - if (cell->lcInfo.sr) - score += 10; - if (cell->lcInfo.negClk) - score += 5; - } - return score; -} - -class PlacementLegaliser -{ - public: - PlacementLegaliser(Context *ctx) : ctx(ctx){}; - - void print_stats(const char *point) - { - float distance_sum = 0; - float max_distance = 0; - int moved_cells = 0; - int unplaced_cells = 0; - for (auto orig : originalPositions) { - if (ctx->cells.at(orig.first)->bel == BelId()) { - unplaced_cells++; - continue; - } - Loc newLoc = ctx->getBelLocation(ctx->cells.at(orig.first)->bel); - if (newLoc != orig.second) { - float distance = std::sqrt(std::pow(newLoc.x - orig.second.x, 2) + pow(newLoc.y - orig.second.y, 2)); - moved_cells++; - distance_sum += distance; - if (distance > max_distance) - max_distance = distance; - } - } - log_info(" moved %d cells, %d unplaced (after %s)\n", moved_cells, unplaced_cells, point); - if (moved_cells > 0) { - log_info(" average distance %f\n", (distance_sum / moved_cells)); - log_info(" maximum distance %f\n", max_distance); - } - } - - bool legalise() - { - log_info("Legalising design..\n"); - for (auto &cell : ctx->cells) { - CellInfo *ci = cell.second.get(); - if (!ctx->getBelGlobalBuf(ci->bel) && cell.second->type == ctx->id("ICESTORM_LC")) { - originalPositions[cell.first] = ctx->getBelLocation(ci->bel); - } - } - init_logic_cells(); - bool legalised_carries = legalise_carries(); - if (!legalised_carries && !ctx->force) - return false; - print_stats("carry legalisation"); - legalise_others(); - print_stats("misc. cell legalisation"); - legalise_logic_tiles(); - print_stats("logic cell legalisation"); - bool replaced_cells = replace_cells(); - print_stats("cell replacement"); - - ctx->assignArchInfo(); - - 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>>( - ctx->chip_info->height + 1, - std::vector>(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 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; - }); - std::unordered_set chained; - for (auto &base_chain : carry_chains) { - for (auto c : base_chain.cells) - chained.insert(c->name); - } - // Any cells not in chains, but with carry enabled, must also be put in a single-carry chain - // for correct processing - for (auto cell : sorted(ctx->cells)) { - CellInfo *ci = cell.second; - if (chained.find(cell.first) == chained.end() && is_lc(ctx, ci) && - bool_or_default(ci->params, ctx->id("CARRY_ENABLE"))) { - CellChain sChain; - sChain.cells.push_back(ci); - chained.insert(cell.first); - carry_chains.push_back(sChain); - } - } - bool success = true; - // Find midpoints for all chains, before we start tearing them up - std::vector 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 split_chains = split_carry_chain(base_chain); - for (auto &chain : split_chains) { - get_chain_midpoint(ctx, chain, chain.mid_x, chain.mid_y); - all_chains.push_back(chain); - } - } - // Actual chain placement - for (auto &chain : all_chains) { - if (ctx->verbose) - log_info("Placing carry chain starting at '%s'\n", chain.cells.front()->name.c_str(ctx)); - float base_x = chain.mid_x, base_y = chain.mid_y - (chain.cells.size() / 16.0f); - // Find Bel meeting requirements closest to the target base, returning location as - auto chain_origin_bel = find_closest_bel(base_x, base_y, chain); - int place_x = std::get<0>(chain_origin_bel), place_y = std::get<1>(chain_origin_bel), - place_z = std::get<2>(chain_origin_bel); - if (place_x == -1) { - if (ctx->force) { - log_warning("failed to place carry chain, starting with cell '%s', length %d\n", - chain.cells.front()->name.c_str(ctx), int(chain.cells.size())); - success = false; - continue; - } else { - log_error("failed to place carry chain, starting with cell '%s', length %d\n", - chain.cells.front()->name.c_str(ctx), int(chain.cells.size())); - } - } - // Place carry chain - for (int i = 0; i < int(chain.cells.size()); i++) { - int target_z = place_y * 8 + place_z + i; - place_lc(chain.cells.at(i), place_x, target_z / 8, target_z % 8); - if (ctx->verbose) - log_info(" Cell '%s' placed at (%d, %d, %d)\n", chain.cells.at(i)->name.c_str(ctx), place_x, - target_z / 8, target_z % 8); - } - } - return success; - } - - // Find Bel closest to a location, meeting chain requirements - std::tuple find_closest_bel(float target_x, float target_y, CellChain &chain) - { - std::tuple best_origin = std::make_tuple(-1, -1, -1); - wirelen_t best_metric = std::numeric_limits::max(); - int width = ctx->chip_info->width, height = ctx->chip_info->height; - // Slow, should radiate outwards from target position - TODO - int chain_size = int(chain.cells.size()); - for (int x = 1; x < width; x++) { - for (int y = 1; y < (height - (chain_size / 8)); y++) { - bool valid = true; - wirelen_t wirelen = 0; - for (int k = 0; k < chain_size; k++) { - auto &lb = logic_bels.at(x).at(y + k / 8).at(k % 8); - if (lb.second) { - valid = false; - break; - } else { - wirelen += get_cell_metric_at_bel(ctx, chain.cells.at(k), lb.first, MetricType::COST); - } - } - if (valid && wirelen < best_metric) { - best_metric = wirelen; - best_origin = std::make_tuple(x, y, 0); - } - } - } - return best_origin; - } - - // Split a carry chain into multiple legal chains - std::vector split_carry_chain(CellChain &carryc) - { - bool start_of_chain = true; - std::vector chains; - std::vector tile; - const int max_length = (ctx->chip_info->height - 2) * 8 - 2; - auto curr_cell = carryc.cells.begin(); - while (curr_cell != carryc.cells.end()) { - CellInfo *cell = *curr_cell; - if (tile.size() >= 8) { - tile.clear(); - } - if (start_of_chain) { - tile.clear(); - chains.emplace_back(); - start_of_chain = false; - if (cell->ports.at(ctx->id("CIN")).net) { - // CIN is not constant and not part of a chain. Must feed in from fabric - CellInfo *feedin = make_carry_feed_in(cell, cell->ports.at(ctx->id("CIN"))); - chains.back().cells.push_back(feedin); - tile.push_back(feedin); - } - } - tile.push_back(cell); - chains.back().cells.push_back(cell); - bool split_chain = (!ctx->logicCellsCompatible(tile)) || (int(chains.back().cells.size()) > max_length); - if (split_chain) { - CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); - tile.pop_back(); - chains.back().cells.back() = passout; - start_of_chain = true; - } else { - NetInfo *carry_net = cell->ports.at(ctx->id("COUT")).net; - bool at_end = (curr_cell == carryc.cells.end() - 1); - if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) { - if (carry_net->users.size() > 2 || - (net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), false) != - net_only_drives(ctx, carry_net, is_lc, ctx->id("CIN"), false)) || - (at_end && !net_only_drives(ctx, carry_net, is_lc, ctx->id("I3"), true))) { - CellInfo *passout = make_carry_pass_out(cell->ports.at(ctx->id("COUT"))); - chains.back().cells.push_back(passout); - tile.push_back(passout); - start_of_chain = true; - } - } - ++curr_cell; - } - } - return chains; - } - - // Place a logic cell at a given grid location, handling rip-up etc - void place_lc(CellInfo *cell, int x, int y, int z) - { - auto &loc = logic_bels.at(x).at(y).at(z); - NPNR_ASSERT(!loc.second); - BelId bel = loc.first; - // Check if there is a cell presently at the location, which we will need to rip up - IdString existing = ctx->getBoundBelCell(bel); - if (existing != IdString()) { - // TODO: keep track of the previous position of the ripped up cell, as a hint - rippedCells.insert(existing); - ctx->unbindBel(bel); - } - if (cell->bel != BelId()) { - ctx->unbindBel(cell->bel); - } - ctx->bindBel(bel, cell->name, STRENGTH_LOCKED); - rippedCells.erase(cell->name); // If cell was ripped up previously, no need to re-place - loc.second = true; // Bel is now unavailable for further use - } - - // Insert a logic cell to legalise a COUT->fabric connection - CellInfo *make_carry_pass_out(PortInfo &cout_port) - { - NPNR_ASSERT(cout_port.net != nullptr); - std::unique_ptr lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); - lc->params[ctx->id("LUT_INIT")] = "65280"; // 0xff00: O = I3 - lc->params[ctx->id("CARRY_ENABLE")] = "1"; - lc->ports.at(ctx->id("O")).net = cout_port.net; - std::unique_ptr co_i3_net(new NetInfo()); - co_i3_net->name = ctx->id(lc->name.str(ctx) + "$I3"); - co_i3_net->driver = cout_port.net->driver; - PortRef i3_r; - i3_r.port = ctx->id("I3"); - i3_r.cell = lc.get(); - co_i3_net->users.push_back(i3_r); - PortRef o_r; - o_r.port = ctx->id("O"); - o_r.cell = lc.get(); - cout_port.net->driver = o_r; - lc->ports.at(ctx->id("I3")).net = co_i3_net.get(); - cout_port.net = co_i3_net.get(); - - IdString co_i3_name = co_i3_net->name; - NPNR_ASSERT(ctx->nets.find(co_i3_name) == ctx->nets.end()); - ctx->nets[co_i3_name] = std::move(co_i3_net); - IdString name = lc->name; - ctx->assignCellInfo(lc.get()); - ctx->cells[lc->name] = std::move(lc); - createdCells.insert(name); - return ctx->cells[name].get(); - } - - // Insert a logic cell to legalise a CIN->fabric connection - CellInfo *make_carry_feed_in(CellInfo *cin_cell, PortInfo &cin_port) - { - NPNR_ASSERT(cin_port.net != nullptr); - std::unique_ptr lc = create_ice_cell(ctx, ctx->id("ICESTORM_LC")); - lc->params[ctx->id("CARRY_ENABLE")] = "1"; - lc->params[ctx->id("CIN_CONST")] = "1"; - lc->params[ctx->id("CIN_SET")] = "1"; - lc->ports.at(ctx->id("I1")).net = cin_port.net; - cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(), - [cin_cell, cin_port](const PortRef &usr) { - return usr.cell == cin_cell && usr.port == cin_port.name; - })); - - PortRef i1_ref; - i1_ref.cell = lc.get(); - i1_ref.port = ctx->id("I1"); - lc->ports.at(ctx->id("I1")).net->users.push_back(i1_ref); - - std::unique_ptr out_net(new NetInfo()); - out_net->name = ctx->id(lc->name.str(ctx) + "$O"); - - PortRef drv_ref; - drv_ref.port = ctx->id("COUT"); - drv_ref.cell = lc.get(); - out_net->driver = drv_ref; - lc->ports.at(ctx->id("COUT")).net = out_net.get(); - - PortRef usr_ref; - usr_ref.port = cin_port.name; - usr_ref.cell = cin_cell; - out_net->users.push_back(usr_ref); - cin_cell->ports.at(cin_port.name).net = out_net.get(); - - IdString out_net_name = out_net->name; - NPNR_ASSERT(ctx->nets.find(out_net_name) == ctx->nets.end()); - ctx->nets[out_net_name] = std::move(out_net); - - IdString name = lc->name; - ctx->assignCellInfo(lc.get()); - ctx->cells[lc->name] = std::move(lc); - createdCells.insert(name); - return ctx->cells[name].get(); - } - - // Legalise logic tiles - void legalise_logic_tiles() - { - int width = ctx->chip_info->width, height = ctx->chip_info->height; - for (int x = 1; x < width; x++) { - for (int y = 1; y < height; y++) { - BelId tileBel = logic_bels.at(x).at(y).at(0).first; - if (tileBel != BelId()) { - bool changed = true; - while (!ctx->isBelLocationValid(tileBel) && changed) { - changed = false; - int max_score = 0; - CellInfo *target = nullptr; - for (int z = 0; z < 8; z++) { - BelId bel = logic_bels.at(x).at(y).at(z).first; - IdString cell = ctx->getBoundBelCell(bel); - if (cell != IdString()) { - CellInfo *ci = ctx->cells.at(cell).get(); - if (ci->belStrength >= STRENGTH_STRONG) - continue; - int score = get_cell_evilness(ctx, ci); - if (score > max_score) { - max_score = score; - target = ci; - } - } - } - if (target != nullptr) { - ctx->unbindBel(target->bel); - rippedCells.insert(target->name); - changed = true; - } - } - } - } - } - } - - // Legalise other tiles - void legalise_others() - { - std::vector legalised_others; - for (auto cell : sorted(ctx->cells)) { - CellInfo *ci = cell.second; - if (!is_lc(ctx, ci)) { - if (ci->belStrength < STRENGTH_STRONG && ci->bel != BelId()) { - if (!ctx->isValidBelForCell(ci, ci->bel)) { - place_single_cell(ctx, ci, true); - } - legalised_others.push_back(ci); - } - } - } - // Lock all these cells now, we don't need to move them in SA (don't lock during legalise placement - // so legalise placement can rip up in case of gbuf contention etc) - for (auto cell : legalised_others) - cell->belStrength = STRENGTH_STRONG; - } - - // Replace ripped-up cells - bool replace_cells() - { - bool success = true; - for (auto cell : sorted(rippedCells)) { - CellInfo *ci = ctx->cells.at(cell).get(); - bool placed = place_single_cell(ctx, ci, true); - if (!placed) { - if (ctx->force) { - log_warning("failed to place cell '%s' of type '%s'\n", cell.c_str(ctx), ci->type.c_str(ctx)); - success = false; - } else { - log_error("failed to place cell '%s' of type '%s'\n", cell.c_str(ctx), ci->type.c_str(ctx)); - } - } - } - return success; - } - - Context *ctx; - std::unordered_set rippedCells; - std::unordered_set createdCells; - std::unordered_map originalPositions; - // Go from X and Y position to logic cells, setting occupied to true if a Bel is unavailable - std::vector>>> logic_bels; -}; - -bool legalise_design(Context *ctx) -{ - PlacementLegaliser lg(ctx); - return lg.legalise(); -} - -NEXTPNR_NAMESPACE_END diff --git a/ice40/place_legaliser.h b/ice40/place_legaliser.h deleted file mode 100644 index 5f4df6aa..00000000 --- a/ice40/place_legaliser.h +++ /dev/null @@ -1,31 +0,0 @@ -/* - * nextpnr -- Next Generation Place and Route - * - * Copyright (C) 2018 David Shah - * - * 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 PLACE_LEGALISER_H -#define PLACE_LEGALISER_H - -#include "nextpnr.h" - -NEXTPNR_NAMESPACE_BEGIN - -bool legalise_design(Context *ctx); - -NEXTPNR_NAMESPACE_END - -#endif -- cgit v1.2.3 From 271979a3bc6b7be683621ac4672e55a4d7449461 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 13:18:16 +0200 Subject: place_common: Helper functions for rel. constraints Signed-off-by: David Shah --- common/place_common.cc | 121 +++++++++++++++++++++++++++++++++++++++++++++++++ common/place_common.h | 5 ++ 2 files changed, 126 insertions(+) diff --git a/common/place_common.cc b/common/place_common.cc index fd38429f..1ada9b04 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -162,4 +162,125 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality) return true; } +class ConstraintLegaliseWorker +{ + private: + Context *ctx; + std::vector rippedCells; + + class IncreasingDiameterSearch + { + public: + IncreasingDiameterSearch() : start(0), min(0), max(-1){}; + IncreasingDiameterSearch(int x) : start(x), min(x), max(x){}; + IncreasingDiameterSearch(int start, int min, int max) : start(start), min(min), max(max){}; + bool done() { return (diameter > (max - min)); }; + int next() + { + int val = start + sign * diameter; + val = std::max(val, min); + val = std::min(val, max); + + if (sign == 0) { + sign = 1; + diameter = 1; + } else if (sign == -1) { + sign = 1; + ++diameter; + } else { + sign = -1; + } + + return val; + } + + private: + int start, min, max; + int diameter = 0; + int sign = 0; + }; + + typedef std::unordered_map CellLocations; + + // Check if a location would be suitable for a cell and all its constrained children + // This also makes a crude attempt to "solve" unconstrained constraints, that is slow and horrible + // and will need to be reworked if mixed constrained/unconstrained chains become common + bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution) + { + BelId locBel = ctx->getBelByLocation(loc); + if (locBel == BelId()) + return false; + if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) + return false; + for (auto child : cell->constr_children) { + IncreasingDiameterSearch xSearch, ySearch, zSearch; + if (child->constr_x == child->UNCONSTR) { + xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX()); + } else { + xSearch = IncreasingDiameterSearch(loc.x + child->constr_x); + } + if (child->constr_y == child->UNCONSTR) { + ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY()); + } else { + ySearch = IncreasingDiameterSearch(loc.y + child->constr_y); + } + if (child->constr_z == child->UNCONSTR) { + zSearch = IncreasingDiameterSearch(loc.z, 0, ctx->getTileDimZ(loc.x, loc.y)); + } else { + if (child->constr_abs_z) { + zSearch = IncreasingDiameterSearch(child->constr_z); + } else { + zSearch = IncreasingDiameterSearch(loc.z + child->constr_z); + } + } + while (!(xSearch.done() && ySearch.done() && zSearch.done())) { + Loc cloc; + cloc.x = xSearch.next(); + cloc.y = ySearch.next(); + cloc.z = zSearch.next(); + if (valid_loc_for(child, cloc, solution)) + return true; + } + return false; + } + + solution[cell->name] = loc; + return true; + } + + // Check if constraints are currently satisfied on a cell and its children + bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; } +}; + +// Get the total distance from satisfied constraints for a cell +int get_constraints_distance(const Context *ctx, const CellInfo *cell) +{ + int dist = 0; + NPNR_ASSERT(cell->bel != BelId()); + Loc loc = ctx->getBelLocation(cell->bel); + if (cell->constr_parent == nullptr) { + if (cell->constr_x != cell->UNCONSTR) + dist += std::abs(cell->constr_x - loc.x); + if (cell->constr_y != cell->UNCONSTR) + dist += std::abs(cell->constr_y - loc.y); + if (cell->constr_z != cell->UNCONSTR) + dist += std::abs(cell->constr_z - loc.z); + } else { + Loc parent_loc = ctx->getBelLocation(cell->constr_parent->bel); + if (cell->constr_x != cell->UNCONSTR) + dist += std::abs(cell->constr_x - (loc.x - parent_loc.x)); + if (cell->constr_y != cell->UNCONSTR) + dist += std::abs(cell->constr_y - (loc.y - parent_loc.y)); + if (cell->constr_z != cell->UNCONSTR) { + if (cell->constr_abs_z) + dist += std::abs(cell->constr_z - loc.z); + else + dist += std::abs(cell->constr_z - (loc.z - parent_loc.z)); + } + } + for (auto child : cell->constr_children) + dist += get_constraints_distance(ctx, child); + return dist; +} + NEXTPNR_NAMESPACE_END diff --git a/common/place_common.h b/common/place_common.h index 32250604..79dec067 100644 --- a/common/place_common.h +++ b/common/place_common.h @@ -44,6 +44,11 @@ wirelen_t get_cell_metric_at_bel(const Context *ctx, CellInfo *cell, BelId bel, // Place a single cell in the lowest wirelength Bel available, optionally requiring validity check bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality); +// Modify a design s.t. all relative placement constraints are satisfied +bool legalise_relative_constraints(Context *ctx); + +// Get the total distance from satisfied constraints for a cell +int get_constraints_distance(const Context *ctx, const CellInfo *cell); NEXTPNR_NAMESPACE_END #endif -- cgit v1.2.3 From e5dea28dbde8a5fbb31bccb347eb0047f6790ebf Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 14:48:40 +0200 Subject: place_common.cc: Working on constraint legalisation Signed-off-by: David Shah --- common/place_common.cc | 146 ++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 133 insertions(+), 13 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index 1ada9b04..b02904ec 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -167,20 +167,23 @@ class ConstraintLegaliseWorker private: Context *ctx; std::vector rippedCells; - + std::unordered_map oldLocations; class IncreasingDiameterSearch { public: IncreasingDiameterSearch() : start(0), min(0), max(-1){}; IncreasingDiameterSearch(int x) : start(x), min(x), max(x){}; IncreasingDiameterSearch(int start, int min, int max) : start(start), min(min), max(max){}; - bool done() { return (diameter > (max - min)); }; - int next() + bool done() const { return (diameter > (max - min)); }; + int get() const { int val = start + sign * diameter; val = std::max(val, min); val = std::min(val, max); + return val; + } + void next() { if (sign == 0) { sign = 1; diameter = 1; @@ -190,8 +193,11 @@ class ConstraintLegaliseWorker } else { sign = -1; } + } - return val; + void reset() { + sign = 0; + diameter = 0; } private: @@ -205,22 +211,28 @@ class ConstraintLegaliseWorker // Check if a location would be suitable for a cell and all its constrained children // This also makes a crude attempt to "solve" unconstrained constraints, that is slow and horrible // and will need to be reworked if mixed constrained/unconstrained chains become common - bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution) + bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set &usedLocations) { BelId locBel = ctx->getBelByLocation(loc); if (locBel == BelId()) return false; if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) return false; + if (!ctx->checkBelAvail(locBel)) { + IdString confCell = ctx->getConflictingBelCell(locBel); + if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) + return false; + } + usedLocations.insert(loc); for (auto child : cell->constr_children) { IncreasingDiameterSearch xSearch, ySearch, zSearch; if (child->constr_x == child->UNCONSTR) { - xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX()); + xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX()-1); } else { xSearch = IncreasingDiameterSearch(loc.x + child->constr_x); } if (child->constr_y == child->UNCONSTR) { - ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY()); + ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY()-1); } else { ySearch = IncreasingDiameterSearch(loc.y + child->constr_y); } @@ -235,28 +247,134 @@ class ConstraintLegaliseWorker } while (!(xSearch.done() && ySearch.done() && zSearch.done())) { Loc cloc; - cloc.x = xSearch.next(); - cloc.y = ySearch.next(); - cloc.z = zSearch.next(); - if (valid_loc_for(child, cloc, solution)) + cloc.x = xSearch.get(); + cloc.y = ySearch.get(); + cloc.z = zSearch.get(); + + zSearch.next(); + if (zSearch.done()) { + zSearch.reset(); + ySearch.next(); + if (ySearch.done()) { + ySearch.reset(); + xSearch.next(); + } + } + + if (usedLocations.count(loc)) + continue; + if (valid_loc_for(child, cloc, solution, usedLocations)) return true; + } + usedLocations.erase(loc); return false; } - + if (solution.count(cell->name)) + usedLocations.erase(solution.at(cell->name)); solution[cell->name] = loc; return true; } + // Set the strength to locked on all cells in chain + void lockdown_chain(CellInfo *root) { + root->belStrength = STRENGTH_LOCKED; + for (auto child : root->constr_children) + lockdown_chain(child); + } + + // Legalise placement constraints on a cell + bool legalise_cell(CellInfo *cell) { + if (cell->constr_parent != nullptr) + return true; // Only process chain roots + if (constraints_satisfied(cell)) { + lockdown_chain(cell); + } else { + IncreasingDiameterSearch xRootSearch, yRootSearch, zRootSearch; + Loc currentLoc; + if (cell->bel != BelId()) + currentLoc = ctx->getBelLocation(cell->bel); + if (cell->constr_x == cell->UNCONSTR) + xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1); + if (cell->constr_y == cell->UNCONSTR) + yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1); + if (cell->constr_z == cell->UNCONSTR) + zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileDimZ(currentLoc.x, currentLoc.y)); + while (!(xRootSearch.done() && yRootSearch.done() && zRootSearch.done())) { + Loc rootLoc; + rootLoc.x = xRootSearch.get(); + rootLoc.y = yRootSearch.get(); + rootLoc.z = zRootSearch.get(); + zRootSearch.next(); + if (zRootSearch.done()) { + zRootSearch.reset(); + yRootSearch.next(); + if (yRootSearch.done()) { + yRootSearch.reset(); + xRootSearch.next(); + } + } + + CellLocations solution; + std::unordered_set used; + if (valid_loc_for(cell, rootLoc, solution, used)) { + for (auto cp : solution) { + BelId target = ctx->getBelByLocation(cp.second); + IdString conflicting = ctx->getConflictingBelCell(target); + if (conflicting != IdString()) { + CellInfo *confl_cell = ctx->cells.at(conflicting).get(); + NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG); + ctx->unbindBel(target); + rippedCells.push_back(confl_cell); + } + ctx->bindBel(target, cp.first, STRENGTH_LOCKED); + } + return true; + } + } + return false; + } + return true; + } + // Check if constraints are currently satisfied on a cell and its children bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; } + +public: + ConstraintLegaliseWorker(Context *ctx) : ctx(ctx) {}; + bool legalise_constraints() { + log_info("Legalising relative constraints...\n"); + for (auto cell : sorted(ctx->cells)) { + oldLocations[cell.first] = ctx->getBelLocation(cell.second->bel); + } + for (auto cell : sorted(ctx->cells)) { + bool res = legalise_cell(cell.second); + if (!res) { + log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx)); + return false; + } + } + for (auto rippedCell : rippedCells) { + bool res = place_single_cell(ctx, rippedCell, STRENGTH_WEAK); + if (!res) { + log_error("failed to place cell '%s' after relative constraint legalisation\n", rippedCell->name.c_str(ctx)); + return false; + } + } + return true; + } }; +bool legalise_relative_constraints(Context *ctx) { + return ConstraintLegaliseWorker(ctx).legalise_constraints(); +} + // Get the total distance from satisfied constraints for a cell int get_constraints_distance(const Context *ctx, const CellInfo *cell) { int dist = 0; - NPNR_ASSERT(cell->bel != BelId()); + if(cell->bel == BelId()) + return 100000; Loc loc = ctx->getBelLocation(cell->bel); if (cell->constr_parent == nullptr) { if (cell->constr_x != cell->UNCONSTR) @@ -266,6 +384,8 @@ int get_constraints_distance(const Context *ctx, const CellInfo *cell) if (cell->constr_z != cell->UNCONSTR) dist += std::abs(cell->constr_z - loc.z); } else { + if(cell->constr_parent->bel == BelId()) + return 100000; Loc parent_loc = ctx->getBelLocation(cell->constr_parent->bel); if (cell->constr_x != cell->UNCONSTR) dist += std::abs(cell->constr_x - (loc.x - parent_loc.x)); -- cgit v1.2.3 From 7e9209878c81730e6374ff555ea2c52f8d20a0ee Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 15:00:32 +0200 Subject: Reworking packer and placer to use new generic rel legaliser Signed-off-by: David Shah --- common/place_common.cc | 6 ++++++ common/placer1.cc | 17 ++++++++--------- ice40/chains.cc | 2 +- ice40/pack.cc | 3 +++ 4 files changed, 18 insertions(+), 10 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index b02904ec..0b7a0352 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -189,9 +189,15 @@ class ConstraintLegaliseWorker diameter = 1; } else if (sign == -1) { sign = 1; + if ((start + sign * diameter) > max) + sign = -1; ++diameter; } else { sign = -1; + if ((start + sign * diameter) > max) { + sign = 1; + ++diameter; + } } } diff --git a/common/placer1.cc b/common/placer1.cc index 3a25f42c..d3665eb6 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -224,7 +224,7 @@ class SAPlacer // Once cooled below legalise threshold, run legalisation and start requiring // legal moves only if (temp < legalise_temp && !require_legal) { - // legalise_design(ctx); + legalise_relative_constraints(ctx); // FIXME require_legal = true; autoplaced.clear(); @@ -294,7 +294,7 @@ class SAPlacer } BelType targetType = ctx->belTypeFromId(cell->type); for (auto bel : ctx->getBels()) { - if (ctx->getBelType(bel) == targetType && (ctx->isValidBelForCell(cell, bel) || !require_legal)) { + if (ctx->getBelType(bel) == targetType && ctx->isValidBelForCell(cell, bel)) { if (ctx->checkBelAvail(bel)) { uint64_t score = ctx->rng64(); if (score <= best_score) { @@ -364,15 +364,14 @@ class SAPlacer if (other != IdString()) { ctx->bindBel(oldBel, other_cell->name, STRENGTH_WEAK); } - if (require_legal) { - if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) { - ctx->unbindBel(newBel); - if (other != IdString()) - ctx->unbindBel(oldBel); - goto swap_fail; - } + if (!ctx->isBelLocationValid(newBel) || ((other != IdString() && !ctx->isBelLocationValid(oldBel)))) { + ctx->unbindBel(newBel); + if (other != IdString()) + ctx->unbindBel(oldBel); + goto swap_fail; } + new_metric = curr_metric; // Recalculate metrics for all nets touched by the peturbation diff --git a/ice40/chains.cc b/ice40/chains.cc index 5b834c07..b1ad1007 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -277,6 +277,6 @@ class ChainConstrainer void constrain_chains() { process_carries(); } }; -void constrain_chains(Context *ctx) { ChainConstrainer(ctx).constrain_chains(); } +void constrain_chains(Context *ctx) { log_info("Constraining chains...\n"); ChainConstrainer(ctx).constrain_chains(); } NEXTPNR_NAMESPACE_END diff --git a/ice40/pack.cc b/ice40/pack.cc index fc182e98..9700bc5d 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -26,6 +26,7 @@ #include "design_utils.h" #include "log.h" #include "util.h" +#include "chains.h" NEXTPNR_NAMESPACE_BEGIN @@ -893,6 +894,8 @@ bool Arch::pack() pack_ram(ctx); pack_special(ctx); ctx->assignArchInfo(); + constrain_chains(ctx); + ctx->assignArchInfo(); log_info("Checksum: 0x%08x\n", ctx->checksum()); return true; } catch (log_execution_error_exception) { -- cgit v1.2.3 From 48e06896a2f86af3ccf7a8b01bf23ac5a522ad8d Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 15:02:42 +0200 Subject: place_common: Fixing rel legaliser search bugs Signed-off-by: David Shah --- common/place_common.cc | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index 0b7a0352..d26a377e 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -251,7 +251,7 @@ class ConstraintLegaliseWorker zSearch = IncreasingDiameterSearch(loc.z + child->constr_z); } } - while (!(xSearch.done() && ySearch.done() && zSearch.done())) { + while (!xSearch.done()) { Loc cloc; cloc.x = xSearch.get(); cloc.y = ySearch.get(); @@ -267,7 +267,7 @@ class ConstraintLegaliseWorker } } - if (usedLocations.count(loc)) + if (usedLocations.count(cloc)) continue; if (valid_loc_for(child, cloc, solution, usedLocations)) return true; @@ -306,7 +306,7 @@ class ConstraintLegaliseWorker yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1); if (cell->constr_z == cell->UNCONSTR) zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileDimZ(currentLoc.x, currentLoc.y)); - while (!(xRootSearch.done() && yRootSearch.done() && zRootSearch.done())) { + while (!xRootSearch.done()) { Loc rootLoc; rootLoc.x = xRootSearch.get(); rootLoc.y = yRootSearch.get(); -- cgit v1.2.3 From 60757a2dd74bdaae6c20f59417a7a2597eb6d3bc Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 15:25:43 +0200 Subject: place_common: Relative constraints working for basic example Signed-off-by: David Shah --- common/place_common.cc | 39 ++++++++++++++++++++++++++++----------- 1 file changed, 28 insertions(+), 11 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index d26a377e..9522624e 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -251,6 +251,7 @@ class ConstraintLegaliseWorker zSearch = IncreasingDiameterSearch(loc.z + child->constr_z); } } + bool success = false; while (!xSearch.done()) { Loc cloc; cloc.x = xSearch.get(); @@ -269,12 +270,15 @@ class ConstraintLegaliseWorker if (usedLocations.count(cloc)) continue; - if (valid_loc_for(child, cloc, solution, usedLocations)) - return true; - + if (valid_loc_for(child, cloc, solution, usedLocations)) { + success = true; + break; + } + } + if (!success) { + usedLocations.erase(loc); + return false; } - usedLocations.erase(loc); - return false; } if (solution.count(cell->name)) usedLocations.erase(solution.at(cell->name)); @@ -325,13 +329,26 @@ class ConstraintLegaliseWorker std::unordered_set used; if (valid_loc_for(cell, rootLoc, solution, used)) { for (auto cp : solution) { + // First unbind all cells + if (ctx->cells.at(cp.first)->bel != BelId()) + ctx->unbindBel(ctx->cells.at(cp.first)->bel); + } + for (auto cp : solution) { + if (ctx->verbose) + log_info(" placing '%s' at (%d, %d, %d)\n", cp.first.c_str(ctx), cp.second.x, cp.second.y, cp.second.z); BelId target = ctx->getBelByLocation(cp.second); - IdString conflicting = ctx->getConflictingBelCell(target); - if (conflicting != IdString()) { - CellInfo *confl_cell = ctx->cells.at(conflicting).get(); - NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG); - ctx->unbindBel(target); - rippedCells.push_back(confl_cell); + if(ctx->verbose) + log_info(" resolved to bel: '%s'\n", ctx->getBelName(target).c_str(ctx)); + if (!ctx->checkBelAvail(target)) { + IdString conflicting = ctx->getConflictingBelCell(target); + if (conflicting != IdString()) { + CellInfo *confl_cell = ctx->cells.at(conflicting).get(); + if (ctx->verbose) + log_info(" '%s' already placed at '%s'\n", conflicting.c_str(ctx), ctx->getBelName(confl_cell->bel).c_str(ctx)); + NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG); + ctx->unbindBel(target); + rippedCells.push_back(confl_cell); + } } ctx->bindBel(target, cp.first, STRENGTH_LOCKED); } -- cgit v1.2.3 From 8c518cb8388df5b50b3c263d5a36d27851764fe4 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 15:40:01 +0200 Subject: Fixing relative constraint implementation Signed-off-by: David Shah --- common/place_common.cc | 9 +++++++++ ice40/chains.cc | 3 ++- 2 files changed, 11 insertions(+), 1 deletion(-) diff --git a/common/place_common.cc b/common/place_common.cc index 9522624e..1d4427ac 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -306,10 +306,18 @@ class ConstraintLegaliseWorker currentLoc = ctx->getBelLocation(cell->bel); if (cell->constr_x == cell->UNCONSTR) xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1); + else + xRootSearch = IncreasingDiameterSearch(cell->constr_x); + if (cell->constr_y == cell->UNCONSTR) yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1); + else + yRootSearch = IncreasingDiameterSearch(cell->constr_y); + if (cell->constr_z == cell->UNCONSTR) zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileDimZ(currentLoc.x, currentLoc.y)); + else + zRootSearch = IncreasingDiameterSearch(cell->constr_z); while (!xRootSearch.done()) { Loc rootLoc; rootLoc.x = xRootSearch.get(); @@ -352,6 +360,7 @@ class ConstraintLegaliseWorker } ctx->bindBel(target, cp.first, STRENGTH_LOCKED); } + NPNR_ASSERT(constraints_satisfied(cell)); return true; } } diff --git a/ice40/chains.cc b/ice40/chains.cc index b1ad1007..54e284af 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -260,7 +260,8 @@ class ChainConstrainer log_info("Placing carry chain starting at '%s'\n", chain.cells.front()->name.c_str(ctx)); // Place carry chain - chain.cells.at(0)->constr_abs_z = 0; + chain.cells.at(0)->constr_abs_z = true; + chain.cells.at(0)->constr_z = 0; for (int i = 1; i < int(chain.cells.size()); i++) { chain.cells.at(i)->constr_x = 0; chain.cells.at(i)->constr_y = (i / 8); -- cgit v1.2.3 From 8081249b92a136dbab203cbc4c57a14a91a86323 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 16:16:20 +0200 Subject: place_common: Debugging bad relative constraint legalisation Signed-off-by: David Shah --- common/place_common.cc | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) diff --git a/common/place_common.cc b/common/place_common.cc index 1d4427ac..7160c642 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -194,7 +194,7 @@ class ConstraintLegaliseWorker ++diameter; } else { sign = -1; - if ((start + sign * diameter) > max) { + if ((start + sign * diameter) < min) { sign = 1; ++diameter; } @@ -257,6 +257,7 @@ class ConstraintLegaliseWorker cloc.x = xSearch.get(); cloc.y = ySearch.get(); cloc.z = zSearch.get(); + log_info(" checking '%s' at (%d, %d, %d)\n", child->name.c_str(ctx), cloc.x, cloc.y, cloc.z); zSearch.next(); if (zSearch.done()) { @@ -304,6 +305,8 @@ class ConstraintLegaliseWorker Loc currentLoc; if (cell->bel != BelId()) currentLoc = ctx->getBelLocation(cell->bel); + else + currentLoc = oldLocations[cell->name]; if (cell->constr_x == cell->UNCONSTR) xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1); else @@ -320,9 +323,12 @@ class ConstraintLegaliseWorker zRootSearch = IncreasingDiameterSearch(cell->constr_z); while (!xRootSearch.done()) { Loc rootLoc; + rootLoc.x = xRootSearch.get(); rootLoc.y = yRootSearch.get(); rootLoc.z = zRootSearch.get(); + if (ctx->verbose) + log_info(" trying (%d, %d, %d)\n", rootLoc.x, rootLoc.y, rootLoc.z); zRootSearch.next(); if (zRootSearch.done()) { zRootSearch.reset(); @@ -374,6 +380,28 @@ class ConstraintLegaliseWorker public: ConstraintLegaliseWorker(Context *ctx) : ctx(ctx) {}; + + void print_chain(CellInfo *cell, int depth = 0) { + for (int i = 0; i < depth; i++) + log(" "); + log("'%s' (", cell->name.c_str(ctx)); + if (cell->constr_x != cell->UNCONSTR) + log("%d, ", cell->constr_x); + else + log("*, "); + if (cell->constr_y != cell->UNCONSTR) + log("%d, ", cell->constr_y); + else + log("*, "); + if (cell->constr_z != cell->UNCONSTR) + log("%d", cell->constr_z); + else + log("*"); + log(")\n"); + for (auto child : cell->constr_children) + print_chain(child, depth+1); + } + bool legalise_constraints() { log_info("Legalising relative constraints...\n"); for (auto cell : sorted(ctx->cells)) { @@ -382,6 +410,8 @@ public: for (auto cell : sorted(ctx->cells)) { bool res = legalise_cell(cell.second); if (!res) { + if(ctx->verbose) + print_chain(cell.second); log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx)); return false; } -- cgit v1.2.3 From fd2174149c3e4654dbe1571e129fadb312f29c33 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 16:29:44 +0200 Subject: Fixing constraint placement bugs Signed-off-by: David Shah --- common/place_common.cc | 72 ++++++++++++++++++++++++++++++++------------------ common/placer1.cc | 1 - ice40/chains.cc | 6 ++++- ice40/gfx.cc | 3 ++- ice40/pack.cc | 5 ++-- 5 files changed, 56 insertions(+), 31 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index 7160c642..8a30f592 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -183,7 +183,8 @@ class ConstraintLegaliseWorker return val; } - void next() { + void next() + { if (sign == 0) { sign = 1; diameter = 1; @@ -201,7 +202,8 @@ class ConstraintLegaliseWorker } } - void reset() { + void reset() + { sign = 0; diameter = 0; } @@ -220,25 +222,34 @@ class ConstraintLegaliseWorker bool valid_loc_for(const CellInfo *cell, Loc loc, CellLocations &solution, std::unordered_set &usedLocations) { BelId locBel = ctx->getBelByLocation(loc); - if (locBel == BelId()) + if (locBel == BelId()) { + if (ctx->verbose) + log_info(" no bel at location\n"); return false; - if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) + } + if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) { + if (ctx->verbose) + log_info(" bel of incorrect type\n"); return false; + } if (!ctx->checkBelAvail(locBel)) { IdString confCell = ctx->getConflictingBelCell(locBel); - if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) + if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) { + if (ctx->verbose) + log_info(" bel already bound strongly to '%s'\n", confCell.c_str(ctx)); return false; + } } usedLocations.insert(loc); for (auto child : cell->constr_children) { IncreasingDiameterSearch xSearch, ySearch, zSearch; if (child->constr_x == child->UNCONSTR) { - xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX()-1); + xSearch = IncreasingDiameterSearch(loc.x, 0, ctx->getGridDimX() - 1); } else { xSearch = IncreasingDiameterSearch(loc.x + child->constr_x); } if (child->constr_y == child->UNCONSTR) { - ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY()-1); + ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY() - 1); } else { ySearch = IncreasingDiameterSearch(loc.y + child->constr_y); } @@ -257,7 +268,9 @@ class ConstraintLegaliseWorker cloc.x = xSearch.get(); cloc.y = ySearch.get(); cloc.z = zSearch.get(); - log_info(" checking '%s' at (%d, %d, %d)\n", child->name.c_str(ctx), cloc.x, cloc.y, cloc.z); + if (ctx->verbose) + log_info(" checking '%s' at (%d, %d, %d)\n", child->name.c_str(ctx), cloc.x, cloc.y, + cloc.z); zSearch.next(); if (zSearch.done()) { @@ -288,18 +301,22 @@ class ConstraintLegaliseWorker } // Set the strength to locked on all cells in chain - void lockdown_chain(CellInfo *root) { + void lockdown_chain(CellInfo *root) + { root->belStrength = STRENGTH_LOCKED; for (auto child : root->constr_children) lockdown_chain(child); } // Legalise placement constraints on a cell - bool legalise_cell(CellInfo *cell) { + bool legalise_cell(CellInfo *cell) + { if (cell->constr_parent != nullptr) return true; // Only process chain roots if (constraints_satisfied(cell)) { - lockdown_chain(cell); + if (cell->constr_children.size() > 0 || cell->constr_x != cell->UNCONSTR || + cell->constr_y != cell->UNCONSTR || cell->constr_z != cell->UNCONSTR) + lockdown_chain(cell); } else { IncreasingDiameterSearch xRootSearch, yRootSearch, zRootSearch; Loc currentLoc; @@ -349,16 +366,18 @@ class ConstraintLegaliseWorker } for (auto cp : solution) { if (ctx->verbose) - log_info(" placing '%s' at (%d, %d, %d)\n", cp.first.c_str(ctx), cp.second.x, cp.second.y, cp.second.z); + log_info(" placing '%s' at (%d, %d, %d)\n", cp.first.c_str(ctx), cp.second.x, + cp.second.y, cp.second.z); BelId target = ctx->getBelByLocation(cp.second); - if(ctx->verbose) + if (ctx->verbose) log_info(" resolved to bel: '%s'\n", ctx->getBelName(target).c_str(ctx)); if (!ctx->checkBelAvail(target)) { IdString conflicting = ctx->getConflictingBelCell(target); if (conflicting != IdString()) { CellInfo *confl_cell = ctx->cells.at(conflicting).get(); if (ctx->verbose) - log_info(" '%s' already placed at '%s'\n", conflicting.c_str(ctx), ctx->getBelName(confl_cell->bel).c_str(ctx)); + log_info(" '%s' already placed at '%s'\n", conflicting.c_str(ctx), + ctx->getBelName(confl_cell->bel).c_str(ctx)); NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG); ctx->unbindBel(target); rippedCells.push_back(confl_cell); @@ -378,10 +397,11 @@ class ConstraintLegaliseWorker // Check if constraints are currently satisfied on a cell and its children bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; } -public: - ConstraintLegaliseWorker(Context *ctx) : ctx(ctx) {}; + public: + ConstraintLegaliseWorker(Context *ctx) : ctx(ctx){}; - void print_chain(CellInfo *cell, int depth = 0) { + void print_chain(CellInfo *cell, int depth = 0) + { for (int i = 0; i < depth; i++) log(" "); log("'%s' (", cell->name.c_str(ctx)); @@ -399,10 +419,11 @@ public: log("*"); log(")\n"); for (auto child : cell->constr_children) - print_chain(child, depth+1); + print_chain(child, depth + 1); } - bool legalise_constraints() { + bool legalise_constraints() + { log_info("Legalising relative constraints...\n"); for (auto cell : sorted(ctx->cells)) { oldLocations[cell.first] = ctx->getBelLocation(cell.second->bel); @@ -410,7 +431,7 @@ public: for (auto cell : sorted(ctx->cells)) { bool res = legalise_cell(cell.second); if (!res) { - if(ctx->verbose) + if (ctx->verbose) print_chain(cell.second); log_error("failed to place chain starting at cell '%s'\n", cell.first.c_str(ctx)); return false; @@ -419,7 +440,8 @@ public: for (auto rippedCell : rippedCells) { bool res = place_single_cell(ctx, rippedCell, STRENGTH_WEAK); if (!res) { - log_error("failed to place cell '%s' after relative constraint legalisation\n", rippedCell->name.c_str(ctx)); + log_error("failed to place cell '%s' after relative constraint legalisation\n", + rippedCell->name.c_str(ctx)); return false; } } @@ -427,15 +449,13 @@ public: } }; -bool legalise_relative_constraints(Context *ctx) { - return ConstraintLegaliseWorker(ctx).legalise_constraints(); -} +bool legalise_relative_constraints(Context *ctx) { return ConstraintLegaliseWorker(ctx).legalise_constraints(); } // Get the total distance from satisfied constraints for a cell int get_constraints_distance(const Context *ctx, const CellInfo *cell) { int dist = 0; - if(cell->bel == BelId()) + if (cell->bel == BelId()) return 100000; Loc loc = ctx->getBelLocation(cell->bel); if (cell->constr_parent == nullptr) { @@ -446,7 +466,7 @@ int get_constraints_distance(const Context *ctx, const CellInfo *cell) if (cell->constr_z != cell->UNCONSTR) dist += std::abs(cell->constr_z - loc.z); } else { - if(cell->constr_parent->bel == BelId()) + if (cell->constr_parent->bel == BelId()) return 100000; Loc parent_loc = ctx->getBelLocation(cell->constr_parent->bel); if (cell->constr_x != cell->UNCONSTR) diff --git a/common/placer1.cc b/common/placer1.cc index d3665eb6..27206139 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -371,7 +371,6 @@ class SAPlacer goto swap_fail; } - new_metric = curr_metric; // Recalculate metrics for all nets touched by the peturbation diff --git a/ice40/chains.cc b/ice40/chains.cc index 54e284af..dce27863 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -278,6 +278,10 @@ class ChainConstrainer void constrain_chains() { process_carries(); } }; -void constrain_chains(Context *ctx) { log_info("Constraining chains...\n"); ChainConstrainer(ctx).constrain_chains(); } +void constrain_chains(Context *ctx) +{ + log_info("Constraining chains...\n"); + ChainConstrainer(ctx).constrain_chains(); +} NEXTPNR_NAMESPACE_END diff --git a/ice40/gfx.cc b/ice40/gfx.cc index 924fe964..d5c6e77f 100644 --- a/ice40/gfx.cc +++ b/ice40/gfx.cc @@ -706,7 +706,8 @@ void gfxTilePip(std::vector &g, int x, int y, GfxTileWireId src, return; } - if (TILE_WIRE_LUTFF_0_IN_0 <= src && src <= TILE_WIRE_LUTFF_7_IN_3 && TILE_WIRE_LUTFF_0_OUT <= dst && dst <= TILE_WIRE_LUTFF_7_OUT) { + if (TILE_WIRE_LUTFF_0_IN_0 <= src && src <= TILE_WIRE_LUTFF_7_IN_3 && TILE_WIRE_LUTFF_0_OUT <= dst && + dst <= TILE_WIRE_LUTFF_7_OUT) { int lut_idx = (src - TILE_WIRE_LUTFF_0_IN_0) / 4; int in_idx = (src - TILE_WIRE_LUTFF_0_IN_0) % 4; diff --git a/ice40/pack.cc b/ice40/pack.cc index 9700bc5d..e7fdc627 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -23,10 +23,10 @@ #include #include #include "cells.h" +#include "chains.h" #include "design_utils.h" #include "log.h" #include "util.h" -#include "chains.h" NEXTPNR_NAMESPACE_BEGIN @@ -445,7 +445,8 @@ static bool is_logic_port(BaseCtx *ctx, const PortRef &port) { if (is_clock_port(ctx, port) || is_reset_port(ctx, port) || is_enable_port(ctx, port)) return false; - return !is_sb_io(ctx, port.cell) && !is_sb_pll40(ctx, port.cell) && !is_sb_pll40_pad(ctx, port.cell) && port.cell->type != ctx->id("SB_GB"); + return !is_sb_io(ctx, port.cell) && !is_sb_pll40(ctx, port.cell) && !is_sb_pll40_pad(ctx, port.cell) && + port.cell->type != ctx->id("SB_GB"); } static void insert_global(Context *ctx, NetInfo *net, bool is_reset, bool is_cen, bool is_logic) -- cgit v1.2.3 From dc4ab55b27a2ada341b060bfe12dade99bf94daf Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 16:59:45 +0200 Subject: Adding constraint satisfaction checks for debugging Signed-off-by: David Shah --- common/nextpnr.h | 2 +- common/place_common.cc | 6 +++++- common/placer1.cc | 19 ++++++++++++------- 3 files changed, 18 insertions(+), 9 deletions(-) diff --git a/common/nextpnr.h b/common/nextpnr.h index f01173e6..f49b982e 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -281,7 +281,7 @@ struct CellInfo : ArchCellInfo std::unordered_map pins; // placement constraints - CellInfo *constr_parent; + CellInfo *constr_parent = nullptr; std::vector constr_children; const int UNCONSTR = INT_MIN; int constr_x = UNCONSTR; // this.x - parent.x diff --git a/common/place_common.cc b/common/place_common.cc index 8a30f592..11823360 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -438,13 +438,17 @@ class ConstraintLegaliseWorker } } for (auto rippedCell : rippedCells) { - bool res = place_single_cell(ctx, rippedCell, STRENGTH_WEAK); + bool res = place_single_cell(ctx, rippedCell, true); if (!res) { log_error("failed to place cell '%s' after relative constraint legalisation\n", rippedCell->name.c_str(ctx)); return false; } } + for (auto cell : sorted(ctx->cells)) + if (get_constraints_distance(ctx, cell.second) != 0) + log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx), + ctx->getBelName(cell.second->bel).c_str(ctx)); return true; } }; diff --git a/common/placer1.cc b/common/placer1.cc index 27206139..601a0245 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -40,11 +40,12 @@ #include "place_common.h" #include "timing.h" #include "util.h" + NEXTPNR_NAMESPACE_BEGIN class SAPlacer { - public: +public: SAPlacer(Context *ctx) : ctx(ctx) { int num_bel_types = 0; @@ -59,11 +60,11 @@ class SAPlacer type_idx = bel_types.at(type); } if (int(fast_bels.size()) < type_idx + 1) - fast_bels.resize(type_idx + 1); + fast_bels.resize(type_idx + 1); if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) - fast_bels.at(type_idx).resize(loc.x + 1); + fast_bels.at(type_idx).resize(loc.x + 1); if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) - fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); + fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); max_x = std::max(max_x, loc.x); max_y = std::max(max_y, loc.y); fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); @@ -272,12 +273,16 @@ class SAPlacer } } } + for (auto cell : sorted(ctx->cells)) + if (get_constraints_distance(ctx, cell.second) != 0) + log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx), + ctx->getBelName(cell.second->bel).c_str(ctx)); timing_analysis(ctx, true /* print_fmax */); ctx->unlock(); return true; } - private: +private: // Initial random placement void place_initial(CellInfo *cell) { @@ -286,7 +291,7 @@ class SAPlacer while (!all_placed) { BelId best_bel = BelId(); uint64_t best_score = std::numeric_limits::max(), - best_ripup_score = std::numeric_limits::max(); + best_ripup_score = std::numeric_limits::max(); CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); if (cell->bel != BelId()) { @@ -397,7 +402,7 @@ class SAPlacer metrics.at(new_wl.first) = new_wl.second; return true; - swap_fail: + swap_fail: ctx->bindBel(oldBel, cell->name, STRENGTH_WEAK); if (other != IdString()) { ctx->bindBel(newBel, other, STRENGTH_WEAK); -- cgit v1.2.3 From 03c2d22ffff6943e072c8a95d454917d5dab4b0d Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 17:07:26 +0200 Subject: place_common: Fixing accidental chain breakage Signed-off-by: David Shah --- common/place_common.cc | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index 11823360..c41f0b4e 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -155,6 +155,8 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality) } else { all_placed = true; } + if (ctx->verbose) + log_info(" placed single cell '%s' at '%s'\n", cell->name.c_str(ctx), ctx->getBelName(best_bel).c_str(ctx)); ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK); cell = ripup_target; @@ -166,7 +168,7 @@ class ConstraintLegaliseWorker { private: Context *ctx; - std::vector rippedCells; + std::set rippedCells; std::unordered_map oldLocations; class IncreasingDiameterSearch { @@ -380,10 +382,11 @@ class ConstraintLegaliseWorker ctx->getBelName(confl_cell->bel).c_str(ctx)); NPNR_ASSERT(confl_cell->belStrength < STRENGTH_STRONG); ctx->unbindBel(target); - rippedCells.push_back(confl_cell); + rippedCells.insert(conflicting); } } ctx->bindBel(target, cp.first, STRENGTH_LOCKED); + rippedCells.erase(cp.first); } NPNR_ASSERT(constraints_satisfied(cell)); return true; @@ -438,10 +441,10 @@ class ConstraintLegaliseWorker } } for (auto rippedCell : rippedCells) { - bool res = place_single_cell(ctx, rippedCell, true); + bool res = place_single_cell(ctx, ctx->cells.at(rippedCell).get(), true); if (!res) { log_error("failed to place cell '%s' after relative constraint legalisation\n", - rippedCell->name.c_str(ctx)); + rippedCell.c_str(ctx)); return false; } } -- cgit v1.2.3 From aa8435df218de50825bdcbcfe4ee88f26c3ff836 Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 17:42:07 +0200 Subject: placer1: Experiment with adding 'constraint distance' metric Signed-off-by: David Shah --- common/placer1.cc | 13 +++++++++++-- 1 file changed, 11 insertions(+), 2 deletions(-) diff --git a/common/placer1.cc b/common/placer1.cc index 601a0245..673e304f 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -348,6 +348,10 @@ private: if (other_cell->belStrength > STRENGTH_WEAK) return false; } + int old_dist = get_constraints_distance(ctx, cell); + int new_dist; + if (other != IdString()) + old_dist += get_constraints_distance(ctx, other_cell); wirelen_t new_metric = 0, delta; ctx->unbindBel(oldBel); if (other != IdString()) { @@ -386,7 +390,12 @@ private: new_metric += net_new_wl; new_lengths.push_back(std::make_pair(net->name, net_new_wl)); } + + new_dist = get_constraints_distance(ctx, cell); + if (other != IdString()) + new_dist += get_constraints_distance(ctx, other_cell); delta = new_metric - curr_metric; + delta += (1 / temp) * (new_dist - old_dist); n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { @@ -447,8 +456,8 @@ private: std::unordered_set locked_bels; bool require_legal = false; const float legalise_temp = 1; - const float post_legalise_temp = 20; - const float post_legalise_dia_scale = 2; + const float post_legalise_temp = 10; + const float post_legalise_dia_scale = 1.5; }; bool placer1(Context *ctx) -- cgit v1.2.3 From 4a751d9aafa0de4f64960bf7e9f16400319259ef Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 18:14:09 +0200 Subject: Add distance moved metrics, changing heuristics Signed-off-by: David Shah --- common/place_common.cc | 30 ++++++++++++++++++++++++++++++ common/placer1.cc | 2 +- 2 files changed, 31 insertions(+), 1 deletion(-) diff --git a/common/place_common.cc b/common/place_common.cc index c41f0b4e..dff989bf 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -425,6 +425,34 @@ class ConstraintLegaliseWorker print_chain(child, depth + 1); } + void print_stats(const char *point) + { + float distance_sum = 0; + float max_distance = 0; + int moved_cells = 0; + int unplaced_cells = 0; + for (auto orig : oldLocations) { + if (ctx->cells.at(orig.first)->bel == BelId()) { + unplaced_cells++; + continue; + } + Loc newLoc = ctx->getBelLocation(ctx->cells.at(orig.first)->bel); + if (newLoc != orig.second) { + float distance = std::sqrt(std::pow(newLoc.x - orig.second.x, 2) + pow(newLoc.y - orig.second.y, 2)); + moved_cells++; + distance_sum += distance; + if (distance > max_distance) + max_distance = distance; + } + } + log_info(" moved %d cells, %d unplaced (after %s)\n", moved_cells, unplaced_cells, point); + if (moved_cells > 0) { + log_info(" average distance %f\n", (distance_sum / moved_cells)); + log_info(" maximum distance %f\n", max_distance); + } + } + + bool legalise_constraints() { log_info("Legalising relative constraints...\n"); @@ -440,6 +468,7 @@ class ConstraintLegaliseWorker return false; } } + print_stats("after legalising chains"); for (auto rippedCell : rippedCells) { bool res = place_single_cell(ctx, ctx->cells.at(rippedCell).get(), true); if (!res) { @@ -448,6 +477,7 @@ class ConstraintLegaliseWorker return false; } } + print_stats("after replacing ripped up cells"); for (auto cell : sorted(ctx->cells)) if (get_constraints_distance(ctx, cell.second) != 0) log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx), diff --git a/common/placer1.cc b/common/placer1.cc index 673e304f..6da8608a 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -395,7 +395,7 @@ private: if (other != IdString()) new_dist += get_constraints_distance(ctx, other_cell); delta = new_metric - curr_metric; - delta += (1 / temp) * (new_dist - old_dist); + delta += (10 / temp) * (new_dist - old_dist); n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { -- cgit v1.2.3 From b937e6defea82c12227b6e00cf19e370b237ea8b Mon Sep 17 00:00:00 2001 From: David Shah Date: Fri, 3 Aug 2018 18:31:54 +0200 Subject: Add constraint weight as a command line option Signed-off-by: David Shah --- common/placer1.cc | 9 +++++---- common/placer1.h | 7 ++++++- ecp5/arch.cc | 2 +- generic/arch.cc | 2 +- ice40/arch.cc | 6 +++++- ice40/arch.h | 3 +++ ice40/main.cc | 6 ++++++ 7 files changed, 27 insertions(+), 8 deletions(-) diff --git a/common/placer1.cc b/common/placer1.cc index 6da8608a..37294dfd 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -46,7 +46,7 @@ NEXTPNR_NAMESPACE_BEGIN class SAPlacer { public: - SAPlacer(Context *ctx) : ctx(ctx) + SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) { int num_bel_types = 0; for (auto bel : ctx->getBels()) { @@ -395,7 +395,7 @@ private: if (other != IdString()) new_dist += get_constraints_distance(ctx, other_cell); delta = new_metric - curr_metric; - delta += (10 / temp) * (new_dist - old_dist); + delta += (cfg.constraintWeight / temp) * (new_dist - old_dist); n_move++; // SA acceptance criterea if (delta < 0 || (temp > 1e-6 && (ctx->rng() / float(0x3fffffff)) <= std::exp(-delta / temp))) { @@ -458,12 +458,13 @@ private: const float legalise_temp = 1; const float post_legalise_temp = 10; const float post_legalise_dia_scale = 1.5; + Placer1Cfg cfg; }; -bool placer1(Context *ctx) +bool placer1(Context *ctx, Placer1Cfg cfg) { try { - SAPlacer placer(ctx); + SAPlacer placer(ctx, cfg); placer.place(); log_info("Checksum: 0x%08x\n", ctx->checksum()); #ifndef NDEBUG diff --git a/common/placer1.h b/common/placer1.h index 477fae56..d8f64b84 100644 --- a/common/placer1.h +++ b/common/placer1.h @@ -23,7 +23,12 @@ NEXTPNR_NAMESPACE_BEGIN -extern bool placer1(Context *ctx); +struct Placer1Cfg +{ + float constraintWeight = 10; +}; + +extern bool placer1(Context *ctx, Placer1Cfg cfg); NEXTPNR_NAMESPACE_END diff --git a/ecp5/arch.cc b/ecp5/arch.cc index 262f43fe..377b8665 100644 --- a/ecp5/arch.cc +++ b/ecp5/arch.cc @@ -426,7 +426,7 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de // ----------------------------------------------------------------------- -bool Arch::place() { return placer1(getCtx()); } +bool Arch::place() { return placer1(getCtx(), Placer1Cfg()); } bool Arch::route() { diff --git a/generic/arch.cc b/generic/arch.cc index 1c22dbf7..f9133f9e 100644 --- a/generic/arch.cc +++ b/generic/arch.cc @@ -412,7 +412,7 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de // --------------------------------------------------------------- -bool Arch::place() { return placer1(getCtx()); } +bool Arch::place() { return placer1(getCtx()\, Placer1Cfg()); } bool Arch::route() { return router1(getCtx(), Router1Cfg()); } diff --git a/ice40/arch.cc b/ice40/arch.cc index eff1d9b9..84856402 100644 --- a/ice40/arch.cc +++ b/ice40/arch.cc @@ -659,7 +659,11 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de // ----------------------------------------------------------------------- -bool Arch::place() { return placer1(getCtx()); } +bool Arch::place() { + Placer1Cfg cfg; + cfg.constraintWeight = placer_constraintWeight; + return placer1(getCtx(), cfg); +} bool Arch::route() { diff --git a/ice40/arch.h b/ice40/arch.h index 98361132..b9b4f3c5 100644 --- a/ice40/arch.h +++ b/ice40/arch.h @@ -797,6 +797,9 @@ struct Arch : BaseCtx } NPNR_ASSERT_FALSE("Expected PLL pin to share an output with an SB_IO D_IN_{0,1}"); } + + float placer_constraintWeight = 10; + }; NEXTPNR_NAMESPACE_END diff --git a/ice40/main.cc b/ice40/main.cc index 41d264ad..60f5b444 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -106,6 +106,8 @@ int main(int argc, char *argv[]) options.add_options()("seed", po::value(), "seed value for random number generator"); options.add_options()("slack_redist_iter", po::value(), "number of iterations between slack redistribution"); + options.add_options()("cstrweight", po::value(), "placer weighting for relative constraint satisfaction"); + options.add_options()("version,V", "show version"); options.add_options()("tmfuzz", "run path delay estimate fuzzer"); options.add_options()("test", "check architecture database integrity"); @@ -318,6 +320,10 @@ int main(int argc, char *argv[]) ctx->slack_redist_iter = vm["slack_redist_iter"].as(); } + if (vm.count("cstrweight")) { + ctx->placer_constraintWeight = vm["cstrweight"].as(); + } + if (vm.count("svg")) { std::cout << "\n"; -- cgit v1.2.3 From 176a23936c8301eb567ea2a0b466dbebc598b18b Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 4 Aug 2018 08:15:49 +0200 Subject: Tidy up Signed-off-by: David Shah --- common/placer1.cc | 1 - ice40/chains.cc | 2 +- ice40/chains.h | 2 +- 3 files changed, 2 insertions(+), 3 deletions(-) diff --git a/common/placer1.cc b/common/placer1.cc index 37294dfd..2ac6602b 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -226,7 +226,6 @@ public: // legal moves only if (temp < legalise_temp && !require_legal) { legalise_relative_constraints(ctx); - // FIXME require_legal = true; autoplaced.clear(); for (auto cell : sorted(ctx->cells)) { diff --git a/ice40/chains.cc b/ice40/chains.cc index dce27863..8638a96c 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -1,7 +1,7 @@ /* * nextpnr -- Next Generation Place and Route * - * Copyright (C) 2018 David Shah + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above diff --git a/ice40/chains.h b/ice40/chains.h index b466cb49..98112303 100644 --- a/ice40/chains.h +++ b/ice40/chains.h @@ -1,7 +1,7 @@ /* * nextpnr -- Next Generation Place and Route * - * Copyright (C) 2018 David Shah + * Copyright (C) 2018 David Shah * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above -- cgit v1.2.3 From 082b8bf272bf09b6ea2ee7aec4682a4eb2e5bfde Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 4 Aug 2018 08:18:04 +0200 Subject: clangformat Signed-off-by: David Shah --- common/place_common.cc | 7 +++---- common/placer1.cc | 14 +++++++------- ice40/arch.cc | 3 ++- ice40/arch.h | 1 - ice40/main.cc | 3 ++- 5 files changed, 14 insertions(+), 14 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index dff989bf..06048c02 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -156,7 +156,8 @@ bool place_single_cell(Context *ctx, CellInfo *cell, bool require_legality) all_placed = true; } if (ctx->verbose) - log_info(" placed single cell '%s' at '%s'\n", cell->name.c_str(ctx), ctx->getBelName(best_bel).c_str(ctx)); + log_info(" placed single cell '%s' at '%s'\n", cell->name.c_str(ctx), + ctx->getBelName(best_bel).c_str(ctx)); ctx->bindBel(best_bel, cell->name, STRENGTH_WEAK); cell = ripup_target; @@ -452,7 +453,6 @@ class ConstraintLegaliseWorker } } - bool legalise_constraints() { log_info("Legalising relative constraints...\n"); @@ -472,8 +472,7 @@ class ConstraintLegaliseWorker for (auto rippedCell : rippedCells) { bool res = place_single_cell(ctx, ctx->cells.at(rippedCell).get(), true); if (!res) { - log_error("failed to place cell '%s' after relative constraint legalisation\n", - rippedCell.c_str(ctx)); + log_error("failed to place cell '%s' after relative constraint legalisation\n", rippedCell.c_str(ctx)); return false; } } diff --git a/common/placer1.cc b/common/placer1.cc index 2ac6602b..32074220 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -45,7 +45,7 @@ NEXTPNR_NAMESPACE_BEGIN class SAPlacer { -public: + public: SAPlacer(Context *ctx, Placer1Cfg cfg) : ctx(ctx), cfg(cfg) { int num_bel_types = 0; @@ -60,11 +60,11 @@ public: type_idx = bel_types.at(type); } if (int(fast_bels.size()) < type_idx + 1) - fast_bels.resize(type_idx + 1); + fast_bels.resize(type_idx + 1); if (int(fast_bels.at(type_idx).size()) < (loc.x + 1)) - fast_bels.at(type_idx).resize(loc.x + 1); + fast_bels.at(type_idx).resize(loc.x + 1); if (int(fast_bels.at(type_idx).at(loc.x).size()) < (loc.y + 1)) - fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); + fast_bels.at(type_idx).at(loc.x).resize(loc.y + 1); max_x = std::max(max_x, loc.x); max_y = std::max(max_y, loc.y); fast_bels.at(type_idx).at(loc.x).at(loc.y).push_back(bel); @@ -281,7 +281,7 @@ public: return true; } -private: + private: // Initial random placement void place_initial(CellInfo *cell) { @@ -290,7 +290,7 @@ private: while (!all_placed) { BelId best_bel = BelId(); uint64_t best_score = std::numeric_limits::max(), - best_ripup_score = std::numeric_limits::max(); + best_ripup_score = std::numeric_limits::max(); CellInfo *ripup_target = nullptr; BelId ripup_bel = BelId(); if (cell->bel != BelId()) { @@ -410,7 +410,7 @@ private: metrics.at(new_wl.first) = new_wl.second; return true; - swap_fail: + swap_fail: ctx->bindBel(oldBel, cell->name, STRENGTH_WEAK); if (other != IdString()) { ctx->bindBel(newBel, other, STRENGTH_WEAK); diff --git a/ice40/arch.cc b/ice40/arch.cc index 84856402..3934e8f0 100644 --- a/ice40/arch.cc +++ b/ice40/arch.cc @@ -659,7 +659,8 @@ delay_t Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, de // ----------------------------------------------------------------------- -bool Arch::place() { +bool Arch::place() +{ Placer1Cfg cfg; cfg.constraintWeight = placer_constraintWeight; return placer1(getCtx(), cfg); diff --git a/ice40/arch.h b/ice40/arch.h index b9b4f3c5..cf78088a 100644 --- a/ice40/arch.h +++ b/ice40/arch.h @@ -799,7 +799,6 @@ struct Arch : BaseCtx } float placer_constraintWeight = 10; - }; NEXTPNR_NAMESPACE_END diff --git a/ice40/main.cc b/ice40/main.cc index 60f5b444..37e18215 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -106,7 +106,8 @@ int main(int argc, char *argv[]) options.add_options()("seed", po::value(), "seed value for random number generator"); options.add_options()("slack_redist_iter", po::value(), "number of iterations between slack redistribution"); - options.add_options()("cstrweight", po::value(), "placer weighting for relative constraint satisfaction"); + options.add_options()("cstrweight", po::value(), + "placer weighting for relative constraint satisfaction"); options.add_options()("version,V", "show version"); options.add_options()("tmfuzz", "run path delay estimate fuzzer"); -- cgit v1.2.3 From 2215ace1dcc9d16f3661c8f95dff56f5f582b6bc Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 4 Aug 2018 08:19:27 +0200 Subject: place_common: Remove excessively verbose debugging Signed-off-by: David Shah --- common/place_common.cc | 13 ------------- 1 file changed, 13 deletions(-) diff --git a/common/place_common.cc b/common/place_common.cc index 06048c02..1baab8a1 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -226,20 +226,14 @@ class ConstraintLegaliseWorker { BelId locBel = ctx->getBelByLocation(loc); if (locBel == BelId()) { - if (ctx->verbose) - log_info(" no bel at location\n"); return false; } if (ctx->getBelType(locBel) != ctx->belTypeFromId(cell->type)) { - if (ctx->verbose) - log_info(" bel of incorrect type\n"); return false; } if (!ctx->checkBelAvail(locBel)) { IdString confCell = ctx->getConflictingBelCell(locBel); if (ctx->cells[confCell]->belStrength >= STRENGTH_STRONG) { - if (ctx->verbose) - log_info(" bel already bound strongly to '%s'\n", confCell.c_str(ctx)); return false; } } @@ -271,9 +265,6 @@ class ConstraintLegaliseWorker cloc.x = xSearch.get(); cloc.y = ySearch.get(); cloc.z = zSearch.get(); - if (ctx->verbose) - log_info(" checking '%s' at (%d, %d, %d)\n", child->name.c_str(ctx), cloc.x, cloc.y, - cloc.z); zSearch.next(); if (zSearch.done()) { @@ -347,8 +338,6 @@ class ConstraintLegaliseWorker rootLoc.x = xRootSearch.get(); rootLoc.y = yRootSearch.get(); rootLoc.z = zRootSearch.get(); - if (ctx->verbose) - log_info(" trying (%d, %d, %d)\n", rootLoc.x, rootLoc.y, rootLoc.z); zRootSearch.next(); if (zRootSearch.done()) { zRootSearch.reset(); @@ -372,8 +361,6 @@ class ConstraintLegaliseWorker log_info(" placing '%s' at (%d, %d, %d)\n", cp.first.c_str(ctx), cp.second.x, cp.second.y, cp.second.z); BelId target = ctx->getBelByLocation(cp.second); - if (ctx->verbose) - log_info(" resolved to bel: '%s'\n", ctx->getBelName(target).c_str(ctx)); if (!ctx->checkBelAvail(target)) { IdString conflicting = ctx->getConflictingBelCell(target); if (conflicting != IdString()) { -- cgit v1.2.3 From affc6da1af7afccba1da8cdf3b9e57a01b1fb5e5 Mon Sep 17 00:00:00 2001 From: David Shah Date: Sat, 4 Aug 2018 08:28:13 +0200 Subject: ice40: Add SB_GB timing to database Signed-off-by: David Shah --- ice40/chipdb.py | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/ice40/chipdb.py b/ice40/chipdb.py index a0d7f03c..d782013f 100644 --- a/ice40/chipdb.py +++ b/ice40/chipdb.py @@ -716,7 +716,9 @@ tmport_to_portpin = { "WCLKE": "WCLKE", "WE": "WE", "posedge:CLOCK": "CLOCK", - "posedge:SLEEP": "SLEEP" + "posedge:SLEEP": "SLEEP", + "USERSIGNALTOGLOBALBUFFER": "USER_SIGNAL_TO_GLOBAL_BUFFER", + "GLOBALBUFFEROUTPUT": "GLOBAL_BUFFER_OUTPUT" } for i in range(16): @@ -744,6 +746,8 @@ def add_cell_timingdata(bel_type, timing_cell, fast_db, slow_db): cell_timings[bel_type] = timing_entries add_cell_timingdata("ICESTORM_LC", "LogicCell40", fast_timings, slow_timings) +add_cell_timingdata("SB_GB", "ICE_GB", fast_timings, slow_timings) + if dev_name != "384": add_cell_timingdata("ICESTORM_RAM", "SB_RAM40_4K", fast_timings, slow_timings) if dev_name == "5k": -- cgit v1.2.3