Move general parallel detail place code out of parallel_refine

Signed-off-by: gatecat <gatecat@ds0.me>

1 files changed, 457 insertions, 0 deletions

diff --git a/common/place/detail_place_core.cc b/common/place/detail_place_core.cc
new file mode 100644
index 00000000..bb383639
--- /dev/null
+++ b/common/place/detail_place_core.cc
@@ -0,0 +1,457 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2021-22  gatecat <gatecat@ds0.me>
+ *
+ *  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 "detail_place_core.h"
+#include "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+DetailPlaceCfg::DetailPlaceCfg(Context *ctx)
+{
+    timing_driven = ctx->setting<bool>("timing_driven");
+
+    hpwl_scale_x = 1;
+    hpwl_scale_y = 1;
+}
+
+PlacePartition::PlacePartition(Context *ctx)
+{
+    x0 = ctx->getGridDimX();
+    y0 = ctx->getGridDimY();
+    x1 = 0;
+    y1 = 0;
+    for (auto &cell : ctx->cells) {
+        Loc l = ctx->getBelLocation(cell.second->bel);
+        x0 = std::min(x0, l.x);
+        x1 = std::max(x1, l.x);
+        y0 = std::min(y0, l.y);
+        y1 = std::max(y1, l.y);
+        cells.push_back(cell.second.get());
+    }
+}
+
+void PlacePartition::split(Context *ctx, bool yaxis, float pivot, PlacePartition &l, PlacePartition &r)
+{
+    std::sort(cells.begin(), cells.end(), [&](CellInfo *a, CellInfo *b) {
+        Loc l0 = ctx->getBelLocation(a->bel), l1 = ctx->getBelLocation(b->bel);
+        return yaxis ? (l0.y < l1.y) : (l0.x < l1.x);
+    });
+    size_t pivot_point = size_t(cells.size() * pivot);
+    l.cells.clear();
+    r.cells.clear();
+    l.cells.reserve(pivot_point);
+    r.cells.reserve(cells.size() - pivot_point);
+    int pivot_coord = (pivot_point == 0) ? (yaxis ? y1 : x1)
+                                         : (yaxis ? ctx->getBelLocation(cells.at(pivot_point - 1)->bel).y
+                                                  : ctx->getBelLocation(cells.at(pivot_point - 1)->bel).x);
+    for (size_t i = 0; i < cells.size(); i++) {
+        Loc loc = ctx->getBelLocation(cells.at(i)->bel);
+        ((yaxis ? loc.y : loc.x) <= pivot_coord ? l.cells : r.cells).push_back(cells.at(i));
+    }
+    if (yaxis) {
+        l.x0 = r.x0 = x0;
+        l.x1 = r.x1 = x1;
+        l.y0 = y0;
+        l.y1 = pivot_coord;
+        r.y0 = (pivot_coord == y1) ? y1 : (pivot_coord + 1);
+        r.y1 = y1;
+    } else {
+        l.y0 = r.y0 = y0;
+        l.y1 = r.y1 = y1;
+        l.x0 = x0;
+        l.x1 = pivot_coord;
+        r.x0 = (pivot_coord == x1) ? x1 : (pivot_coord + 1);
+        r.x1 = x1;
+    }
+}
+
+void DetailPlacerState::update_global_costs()
+{
+    last_bounds.resize(flat_nets.size());
+    last_tmg_costs.resize(flat_nets.size());
+    total_wirelen = 0;
+    total_timing_cost = 0;
+    for (size_t i = 0; i < flat_nets.size(); i++) {
+        NetInfo *ni = flat_nets.at(i);
+        if (skip_net(ni))
+            continue;
+        last_bounds.at(i) = NetBB::compute(ctx, ni);
+        total_wirelen += last_bounds.at(i).hpwl(base_cfg);
+        if (!timing_skip_net(ni)) {
+            auto &tc = last_tmg_costs.at(i);
+            tc.resize(ni->users.capacity());
+            for (auto usr : ni->users.enumerate()) {
+                tc.at(usr.index.idx()) = get_timing_cost(ni, usr.index);
+                total_timing_cost += tc.at(usr.index.idx());
+            }
+        }
+    }
+}
+
+NetBB NetBB::compute(const Context *ctx, const NetInfo *net, const dict<IdString, BelId> *cell2bel)
+{
+    NetBB result{};
+    if (!net->driver.cell)
+        return result;
+    auto bel_loc = [&](const CellInfo *cell) {
+        BelId bel = cell2bel ? cell2bel->at(cell->name) : cell->bel;
+        return ctx->getBelLocation(bel);
+    };
+    result.nx0 = result.nx1 = result.ny0 = result.ny1 = 1;
+    Loc drv_loc = bel_loc(net->driver.cell);
+    result.x0 = result.x1 = drv_loc.x;
+    result.y0 = result.y1 = drv_loc.y;
+    for (auto &usr : net->users) {
+        Loc l = bel_loc(usr.cell);
+        if (l.x == result.x0)
+            ++result.nx0; // on the edge
+        else if (l.x < result.x0) {
+            result.x0 = l.x; // extends the edge
+            result.nx0 = 1;
+        }
+        if (l.x == result.x1)
+            ++result.nx1; // on the edge
+        else if (l.x > result.x1) {
+            result.x1 = l.x; // extends the edge
+            result.nx1 = 1;
+        }
+        if (l.y == result.y0)
+            ++result.ny0; // on the edge
+        else if (l.y < result.y0) {
+            result.y0 = l.y; // extends the edge
+            result.ny0 = 1;
+        }
+        if (l.y == result.y1)
+            ++result.ny1; // on the edge
+        else if (l.y > result.y1) {
+            result.y1 = l.y; // extends the edge
+            result.ny1 = 1;
+        }
+    }
+    return result;
+}
+
+void DetailPlacerThreadState::set_partition(const PlacePartition &part)
+{
+    p = part;
+    thread_nets.clear();
+    thread_net_idx.resize(g.flat_nets.size());
+    std::fill(thread_net_idx.begin(), thread_net_idx.end(), -1);
+    // Determine the set of nets that are within the thread; and therefore we care about
+    for (auto thread_cell : part.cells) {
+        for (auto &port : thread_cell->ports) {
+            if (!port.second.net)
+                continue;
+            int global_idx = port.second.net->udata;
+            auto &thread_idx = thread_net_idx.at(global_idx);
+            // Already added to the set
+            if (thread_idx != -1)
+                continue;
+            thread_idx = thread_nets.size();
+            thread_nets.push_back(port.second.net);
+        }
+    }
+    tmg_ignored_nets.clear();
+    ignored_nets.clear();
+    for (auto tn : thread_nets) {
+        ignored_nets.push_back(g.skip_net(tn));
+        tmg_ignored_nets.push_back(g.timing_skip_net(tn));
+    }
+    // Set up the original cell-bel map for all nets inside the thread
+    local_cell2bel.clear();
+    for (NetInfo *net : thread_nets) {
+        if (net->driver.cell)
+            local_cell2bel[net->driver.cell->name] = net->driver.cell->bel;
+        for (auto &usr : net->users)
+            local_cell2bel[usr.cell->name] = usr.cell->bel;
+    }
+}
+
+void DetailPlacerThreadState::setup_initial_state()
+{
+    // Setup initial net bounding boxes and timing costs
+    net_bounds.clear();
+    arc_tmg_cost.clear();
+    for (auto tn : thread_nets) {
+        net_bounds.push_back(g.last_bounds.at(tn->udata));
+        arc_tmg_cost.push_back(g.last_tmg_costs.at(tn->udata));
+    }
+    new_net_bounds = net_bounds;
+    for (int j = 0; j < 2; j++) {
+        auto &a = axes.at(j);
+        a.already_bounds_changed.resize(net_bounds.size());
+    }
+    already_timing_changed.clear();
+    already_timing_changed.resize(net_bounds.size());
+    for (size_t i = 0; i < thread_nets.size(); i++)
+        already_timing_changed.at(i) = std::vector<bool>(thread_nets.at(i)->users.capacity());
+}
+
+bool DetailPlacerThreadState::bounds_check(BelId bel)
+{
+    Loc l = ctx->getBelLocation(bel);
+    if (l.x < p.x0 || l.x > p.x1 || l.y < p.y0 || l.y > p.y1)
+        return false;
+    return true;
+}
+
+bool DetailPlacerThreadState::bind_move()
+{
+#if !defined(__wasm)
+    std::unique_lock<std::shared_timed_mutex> l(g.archapi_mutex);
+#endif
+    for (auto &entry : moved_cells) {
+        ctx->unbindBel(entry.second.first);
+    }
+    bool success = true;
+    for (auto &entry : moved_cells) {
+        // Make sure targets are available before we bind them
+        if (!ctx->checkBelAvail(entry.second.second)) {
+            success = false;
+            break;
+        }
+        ctx->bindBel(entry.second.second, ctx->cells.at(entry.first).get(), STRENGTH_WEAK);
+    }
+    arch_state_dirty = true;
+    return success;
+}
+
+bool DetailPlacerThreadState::check_validity()
+{
+#if !defined(__wasm)
+    std::shared_lock<std::shared_timed_mutex> l(g.archapi_mutex);
+#endif
+    bool result = true;
+    for (auto e : moved_cells) {
+        if (!ctx->isBelLocationValid(e.second.first)) {
+            // Have to check old; too; as unbinding a bel could make a placement illegal by virtue of no longer
+            // enabling dedicated routes to be used
+            result = false;
+            break;
+        }
+        if (!ctx->isBelLocationValid(e.second.second)) {
+            result = false;
+            break;
+        }
+    }
+    return result;
+}
+
+void DetailPlacerThreadState::revert_move()
+{
+    if (arch_state_dirty) {
+        // If changes to the arch state were made, revert them by restoring original cell bindings
+#if !defined(__wasm)
+        std::unique_lock<std::shared_timed_mutex> l(g.archapi_mutex);
+#endif
+        for (auto &entry : moved_cells) {
+            BelId curr_bound = ctx->cells.at(entry.first)->bel;
+            if (curr_bound != BelId())
+                ctx->unbindBel(curr_bound);
+        }
+        for (auto &entry : moved_cells) {
+            ctx->bindBel(entry.second.first, ctx->cells.at(entry.first).get(), STRENGTH_WEAK);
+        }
+        arch_state_dirty = false;
+    }
+    for (auto &entry : moved_cells)
+        local_cell2bel[entry.first] = entry.second.first;
+}
+
+void DetailPlacerThreadState::commit_move()
+{
+    arch_state_dirty = false;
+    for (auto &axis : axes) {
+        for (auto bc : axis.bounds_changed_nets) {
+            // Commit updated net bounds
+            net_bounds.at(bc) = new_net_bounds.at(bc);
+        }
+    }
+    if (g.base_cfg.timing_driven) {
+        NPNR_ASSERT(timing_changed_arcs.size() == new_timing_costs.size());
+        for (size_t i = 0; i < timing_changed_arcs.size(); i++) {
+            auto arc = timing_changed_arcs.at(i);
+            arc_tmg_cost.at(arc.first).at(arc.second.idx()) = new_timing_costs.at(i);
+        }
+    }
+}
+
+void DetailPlacerThreadState::compute_changes_for_cell(CellInfo *cell, BelId old_bel, BelId new_bel)
+{
+    Loc new_loc = ctx->getBelLocation(new_bel);
+    Loc old_loc = ctx->getBelLocation(old_bel);
+    for (const auto &port : cell->ports) {
+        NetInfo *pn = port.second.net;
+        if (!pn)
+            continue;
+        int idx = thread_net_idx.at(pn->udata);
+        if (ignored_nets.at(idx))
+            continue;
+        NetBB &new_bounds = new_net_bounds.at(idx);
+        // For the x-axis (i=0) and y-axis (i=1)
+        for (int i = 0; i < 2; i++) {
+            auto &axis = axes.at(i);
+            // New and old on this axis
+            int new_pos = i ? new_loc.y : new_loc.x, old_pos = i ? old_loc.y : old_loc.x;
+            // References to updated bounding box entries
+            auto &b0 = i ? new_bounds.y0 : new_bounds.x0;
+            auto &n0 = i ? new_bounds.ny0 : new_bounds.nx0;
+            auto &b1 = i ? new_bounds.y1 : new_bounds.x1;
+            auto &n1 = i ? new_bounds.ny1 : new_bounds.nx1;
+            auto &change = axis.already_bounds_changed.at(idx);
+            // Lower bound
+            if (new_pos < b0) {
+                // Further out than current lower bound
+                b0 = new_pos;
+                n0 = 1;
+                if (change == NO_CHANGE) {
+                    change = CELL_MOVED_OUTWARDS;
+                    axis.bounds_changed_nets.push_back(idx);
+                }
+            } else if (new_pos == b0 && old_pos > b0) {
+                // Moved from inside into current bound
+                ++n0;
+                if (change == NO_CHANGE) {
+                    change = CELL_MOVED_OUTWARDS;
+                    axis.bounds_changed_nets.push_back(idx);
+                }
+            } else if (old_pos == b0 && new_pos > b0) {
+                // Moved from current bound to inside
+                if (change == NO_CHANGE)
+                    axis.bounds_changed_nets.push_back(idx);
+                if (n0 == 1) {
+                    // Was the last cell on the bound; have to do a full recompute
+                    change = FULL_RECOMPUTE;
+                } else {
+                    --n0;
+                    if (change == NO_CHANGE)
+                        change = CELL_MOVED_INWARDS;
+                }
+            }
+            // Upper bound
+            if (new_pos > b1) {
+                // Further out than current upper bound
+                b1 = new_pos;
+                n1 = new_pos;
+                if (change == NO_CHANGE) {
+                    change = CELL_MOVED_OUTWARDS;
+                    axis.bounds_changed_nets.push_back(idx);
+                }
+            } else if (new_pos == b1 && old_pos < b1) {
+                // Moved onto current bound
+                ++n1;
+                if (change == NO_CHANGE) {
+                    change = CELL_MOVED_OUTWARDS;
+                    axis.bounds_changed_nets.push_back(idx);
+                }
+            } else if (old_pos == b1 && new_pos < b1) {
+                // Moved from current bound to inside
+                if (change == NO_CHANGE)
+                    axis.bounds_changed_nets.push_back(idx);
+                if (n1 == 1) {
+                    // Was the last cell on the bound; have to do a full recompute
+                    change = FULL_RECOMPUTE;
+                } else {
+                    --n1;
+                    if (change == NO_CHANGE)
+                        change = CELL_MOVED_INWARDS;
+                }
+            }
+        }
+        // Timing updates if timing driven
+        if (g.base_cfg.timing_driven && !tmg_ignored_nets.at(idx)) {
+            if (port.second.type == PORT_OUT) {
+                int cc;
+                TimingPortClass cls = ctx->getPortTimingClass(cell, port.first, cc);
+                if (cls != TMG_IGNORE) {
+                    for (auto usr : pn->users.enumerate())
+                        if (!already_timing_changed.at(idx).at(usr.index.idx())) {
+                            timing_changed_arcs.emplace_back(std::make_pair(idx, usr.index));
+                            already_timing_changed.at(idx).at(usr.index.idx()) = true;
+                        }
+                }
+            } else {
+                auto usr = port.second.user_idx;
+                if (!already_timing_changed.at(idx).at(usr.idx())) {
+                    timing_changed_arcs.emplace_back(std::make_pair(idx, usr));
+                    already_timing_changed.at(idx).at(usr.idx()) = true;
+                }
+            }
+        }
+    }
+}
+
+void DetailPlacerThreadState::compute_total_change()
+{
+    auto &xa = axes.at(0), &ya = axes.at(1);
+    for (auto &bc : xa.bounds_changed_nets)
+        if (xa.already_bounds_changed.at(bc) == FULL_RECOMPUTE)
+            new_net_bounds.at(bc) = NetBB::compute(ctx, thread_nets.at(bc), &local_cell2bel);
+    for (auto &bc : ya.bounds_changed_nets)
+        if (xa.already_bounds_changed.at(bc) != FULL_RECOMPUTE && ya.already_bounds_changed.at(bc) == FULL_RECOMPUTE)
+            new_net_bounds.at(bc) = NetBB::compute(ctx, thread_nets.at(bc), &local_cell2bel);
+    for (auto &bc : xa.bounds_changed_nets)
+        wirelen_delta += (new_net_bounds.at(bc).hpwl(g.base_cfg) - net_bounds.at(bc).hpwl(g.base_cfg));
+    for (auto &bc : ya.bounds_changed_nets)
+        if (xa.already_bounds_changed.at(bc) == NO_CHANGE)
+            wirelen_delta += (new_net_bounds.at(bc).hpwl(g.base_cfg) - net_bounds.at(bc).hpwl(g.base_cfg));
+    if (g.base_cfg.timing_driven) {
+        NPNR_ASSERT(new_timing_costs.empty());
+        for (auto arc : timing_changed_arcs) {
+            double new_cost = g.get_timing_cost(thread_nets.at(arc.first), arc.second, &local_cell2bel);
+            timing_delta += (new_cost - arc_tmg_cost.at(arc.first).at(arc.second.idx()));
+            new_timing_costs.push_back(new_cost);
+        }
+    }
+}
+
+void DetailPlacerThreadState::reset_move_state()
+{
+    moved_cells.clear();
+    cell_rel.clear();
+    for (auto &axis : axes) {
+        for (auto bc : axis.bounds_changed_nets) {
+            new_net_bounds.at(bc) = net_bounds.at(bc);
+            axis.already_bounds_changed[bc] = NO_CHANGE;
+        }
+        axis.bounds_changed_nets.clear();
+    }
+    for (auto &arc : timing_changed_arcs) {
+        already_timing_changed.at(arc.first).at(arc.second.idx()) = false;
+    }
+    timing_changed_arcs.clear();
+    new_timing_costs.clear();
+    wirelen_delta = 0;
+    timing_delta = 0;
+}
+
+bool DetailPlacerThreadState::add_to_move(CellInfo *cell, BelId old_bel, BelId new_bel)
+{
+    if (!bounds_check(old_bel) || !bounds_check(new_bel))
+        return false;
+    if (!ctx->isValidBelForCellType(cell->type, new_bel))
+        return false;
+    NPNR_ASSERT(!moved_cells.count(cell->name));
+    moved_cells[cell->name] = std::make_pair(old_bel, new_bel);
+    local_cell2bel[cell->name] = new_bel;
+    compute_changes_for_cell(cell, old_bel, new_bel);
+    return true;
+}
+
+NEXTPNR_NAMESPACE_END