diff options
| -rw-r--r-- | common/arch_api.h | 4 | ||||
| -rw-r--r-- | common/base_arch.h | 4 | ||||
| -rw-r--r-- | common/basectx.cc | 61 | ||||
| -rw-r--r-- | common/nextpnr_types.cc | 17 | ||||
| -rw-r--r-- | common/nextpnr_types.h | 6 | ||||
| -rw-r--r-- | common/place_common.cc | 208 | ||||
| -rw-r--r-- | common/placer1.cc | 65 | ||||
| -rw-r--r-- | common/placer_heap.cc | 121 | ||||
| -rw-r--r-- | common/timing_opt.cc | 7 | ||||
| -rw-r--r-- | docs/archapi.md | 4 |
10 files changed, 151 insertions, 346 deletions
diff --git a/common/arch_api.h b/common/arch_api.h index f8e6d0ae..01c29a84 100644 --- a/common/arch_api.h +++ b/common/arch_api.h @@ -142,8 +142,8 @@ template <typename R> struct ArchAPI : BaseCtx // Cluster methods virtual CellInfo *getClusterRootCell(ClusterId cluster) const = 0; virtual ArcBounds getClusterBounds(ClusterId cluster) const = 0; - virtual Loc getClusterOffset(CellInfo *cell) const = 0; - virtual bool isClusterStrict(CellInfo *cell) const = 0; + virtual Loc getClusterOffset(const CellInfo *cell) const = 0; + virtual bool isClusterStrict(const CellInfo *cell) const = 0; virtual bool getClusterPlacement(ClusterId cluster, BelId root_bel, std::vector<std::pair<CellInfo *, BelId>> &placement) const = 0; // Flow methods diff --git a/common/base_arch.h b/common/base_arch.h index 35500c1d..8ed77790 100644 --- a/common/base_arch.h +++ b/common/base_arch.h @@ -393,13 +393,13 @@ template <typename R> struct BaseArch : ArchAPI<R> }); } - virtual Loc getClusterOffset(CellInfo *cell) const override + virtual Loc getClusterOffset(const CellInfo *cell) const override { return if_using_basecluster<Loc>(cell, [](const BaseClusterInfo *c) { return Loc(c->constr_x, c->constr_y, 0); }); } - virtual bool isClusterStrict(CellInfo *cell) const override { return true; } + virtual bool isClusterStrict(const CellInfo *cell) const override { return true; } virtual bool getClusterPlacement(ClusterId cluster, BelId root_bel, std::vector<std::pair<CellInfo *, BelId>> &placement) const override diff --git a/common/basectx.cc b/common/basectx.cc index da33eecc..34fb414c 100644 --- a/common/basectx.cc +++ b/common/basectx.cc @@ -152,25 +152,6 @@ void BaseCtx::archInfoToAttributes() ci->attrs[id("NEXTPNR_BEL")] = getCtx()->getBelName(ci->bel).str(getCtx()); ci->attrs[id("BEL_STRENGTH")] = (int)ci->belStrength; } - if (ci->constr_x != ci->UNCONSTR) - ci->attrs[id("CONSTR_X")] = ci->constr_x; - if (ci->constr_y != ci->UNCONSTR) - ci->attrs[id("CONSTR_Y")] = ci->constr_y; - if (ci->constr_z != ci->UNCONSTR) { - ci->attrs[id("CONSTR_Z")] = ci->constr_z; - ci->attrs[id("CONSTR_ABS_Z")] = ci->constr_abs_z ? 1 : 0; - } - if (ci->constr_parent != nullptr) - ci->attrs[id("CONSTR_PARENT")] = ci->constr_parent->name.str(this); - if (!ci->constr_children.empty()) { - std::string constr = ""; - for (auto &item : ci->constr_children) { - if (!constr.empty()) - constr += std::string(";"); - constr += item->name.c_str(this); - } - ci->attrs[id("CONSTR_CHILDREN")] = constr; - } } for (auto &net : getCtx()->nets) { auto ni = net.second.get(); @@ -204,48 +185,6 @@ void BaseCtx::attributesToArchInfo() BelId b = getCtx()->getBelByNameStr(val->second.as_string()); getCtx()->bindBel(b, ci, strength); } - - val = ci->attrs.find(id("CONSTR_PARENT")); - if (val != ci->attrs.end()) { - auto parent = cells.find(id(val->second.str)); - if (parent != cells.end()) - ci->constr_parent = parent->second.get(); - else - continue; - } - - val = ci->attrs.find(id("CONSTR_X")); - if (val != ci->attrs.end()) - ci->constr_x = val->second.as_int64(); - - val = ci->attrs.find(id("CONSTR_Y")); - if (val != ci->attrs.end()) - ci->constr_y = val->second.as_int64(); - - val = ci->attrs.find(id("CONSTR_Z")); - if (val != ci->attrs.end()) - ci->constr_z = val->second.as_int64(); - - val = ci->attrs.find(id("CONSTR_ABS_Z")); - if (val != ci->attrs.end()) - ci->constr_abs_z = val->second.as_int64() == 1; - - val = ci->attrs.find(id("CONSTR_PARENT")); - if (val != ci->attrs.end()) { - auto parent = cells.find(id(val->second.as_string())); - if (parent != cells.end()) - ci->constr_parent = parent->second.get(); - } - val = ci->attrs.find(id("CONSTR_CHILDREN")); - if (val != ci->attrs.end()) { - std::vector<std::string> strs; - auto children = val->second.as_string(); - boost::split(strs, children, boost::is_any_of(";")); - for (auto val : strs) { - if (cells.count(id(val.c_str()))) - ci->constr_children.push_back(cells.find(id(val.c_str()))->second.get()); - } - } } for (auto &net : getCtx()->nets) { auto ni = net.second.get(); diff --git a/common/nextpnr_types.cc b/common/nextpnr_types.cc index a76576de..f55b89e8 100644 --- a/common/nextpnr_types.cc +++ b/common/nextpnr_types.cc @@ -44,26 +44,9 @@ void CellInfo::unsetParam(IdString name) { params.erase(name); } void CellInfo::setAttr(IdString name, Property value) { attrs[name] = value; } void CellInfo::unsetAttr(IdString name) { attrs.erase(name); } -bool CellInfo::isConstrained(bool include_abs_z_constr) const -{ - return constr_parent != nullptr || !constr_children.empty() || (include_abs_z_constr && constr_abs_z); -} - bool CellInfo::testRegion(BelId bel) const { return region == nullptr || !region->constr_bels || region->bels.count(bel); } -Loc CellInfo::getConstrainedLoc(Loc parent_loc) const -{ - NPNR_ASSERT(constr_parent != nullptr); - Loc cloc = parent_loc; - if (constr_x != UNCONSTR) - cloc.x += constr_x; - if (constr_y != UNCONSTR) - cloc.y += constr_y; - if (constr_z != UNCONSTR) - cloc.z = constr_abs_z ? constr_z : (parent_loc.z + constr_z); - return cloc; -} NEXTPNR_NAMESPACE_END diff --git a/common/nextpnr_types.h b/common/nextpnr_types.h index 5fdd82dd..67e60c50 100644 --- a/common/nextpnr_types.h +++ b/common/nextpnr_types.h @@ -178,14 +178,8 @@ struct CellInfo : ArchCellInfo void unsetParam(IdString name); void setAttr(IdString name, Property value); void unsetAttr(IdString name); - - // return true if the cell has placement constraints (optionally excluding the case where the only case is an - // absolute z constraint) - bool isConstrained(bool include_abs_z_constr = true) const; // check whether a bel complies with the cell's region constraint bool testRegion(BelId bel) const; - // get the constrained location for this cell given a provisional location for its parent - Loc getConstrainedLoc(Loc parent_loc) const; }; enum TimingPortClass diff --git a/common/place_common.cc b/common/place_common.cc index 31b93420..7cbeca65 100644 --- a/common/place_common.cc +++ b/common/place_common.cc @@ -179,6 +179,8 @@ class ConstraintLegaliseWorker Context *ctx; std::set<IdString> rippedCells; std::unordered_map<IdString, Loc> oldLocations; + std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells; + class IncreasingDiameterSearch { public: @@ -228,83 +230,52 @@ class ConstraintLegaliseWorker typedef std::unordered_map<IdString, Loc> 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, std::unordered_set<Loc> &usedLocations) { BelId locBel = ctx->getBelByLocation(loc); - if (locBel == BelId()) { - return false; - } - if (!ctx->isValidBelForCellType(cell->type, locBel)) { + if (locBel == BelId()) return false; - } - if (!ctx->checkBelAvail(locBel)) { - CellInfo *confCell = ctx->getConflictingBelCell(locBel); - if (confCell->belStrength >= STRENGTH_STRONG) { - return false; - } - } - // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later - for (auto tilebel : ctx->getBelsByTile(loc.x, loc.y)) { - CellInfo *tcell = ctx->getBoundBelCell(tilebel); - if (tcell && tcell->belStrength >= STRENGTH_STRONG) + + if (cell->cluster == ClusterId()) { + if (!ctx->isValidBelForCellType(cell->type, locBel)) 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); - } else { - xSearch = IncreasingDiameterSearch(loc.x + child->constr_x); - } - if (child->constr_y == child->UNCONSTR) { - ySearch = IncreasingDiameterSearch(loc.y, 0, ctx->getGridDimY() - 1); - } else { - ySearch = IncreasingDiameterSearch(loc.y + child->constr_y); - } - if (child->constr_z == child->UNCONSTR) { - zSearch = IncreasingDiameterSearch(loc.z, 0, ctx->getTileBelDimZ(loc.x, loc.y)); - } else { - if (child->constr_abs_z) { - zSearch = IncreasingDiameterSearch(child->constr_z); - } else { - zSearch = IncreasingDiameterSearch(loc.z + child->constr_z); + if (!ctx->checkBelAvail(locBel)) { + CellInfo *confCell = ctx->getConflictingBelCell(locBel); + if (confCell->belStrength >= STRENGTH_STRONG) { + return false; } } - bool success = false; - while (!xSearch.done()) { - Loc cloc; - 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(); + // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later + for (auto tilebel : ctx->getBelsByTile(loc.x, loc.y)) { + CellInfo *tcell = ctx->getBoundBelCell(tilebel); + if (tcell && tcell->belStrength >= STRENGTH_STRONG) + return false; + } + usedLocations.insert(loc); + solution[cell->name] = loc; + } else { + std::vector<std::pair<CellInfo *, BelId>> placement; + if (!ctx->getClusterPlacement(cell->cluster, locBel, placement)) + return false; + for (auto &p : placement) { + Loc p_loc = ctx->getBelLocation(p.second); + if (!ctx->checkBelAvail(p.second)) { + CellInfo *confCell = ctx->getConflictingBelCell(p.second); + if (confCell->belStrength >= STRENGTH_STRONG) { + return false; } } - - if (usedLocations.count(cloc)) - continue; - if (valid_loc_for(child, cloc, solution, usedLocations)) { - success = true; - break; + // Don't place at tiles where any strongly bound Bels exist, as we might need to rip them up later + for (auto tilebel : ctx->getBelsByTile(p_loc.x, p_loc.y)) { + CellInfo *tcell = ctx->getBoundBelCell(tilebel); + if (tcell && tcell->belStrength >= STRENGTH_STRONG) + return false; } - } - if (!success) { - usedLocations.erase(loc); - return false; + usedLocations.insert(p_loc); + solution[p.first->name] = p_loc; } } - if (solution.count(cell->name)) - usedLocations.erase(solution.at(cell->name)); - solution[cell->name] = loc; + return true; } @@ -312,18 +283,18 @@ class ConstraintLegaliseWorker void lockdown_chain(CellInfo *root) { root->belStrength = STRENGTH_STRONG; - for (auto child : root->constr_children) - lockdown_chain(child); + if (root->cluster != ClusterId()) + for (auto child : cluster2cells.at(root->cluster)) + child->belStrength = STRENGTH_STRONG; } // Legalise placement constraints on a cell bool legalise_cell(CellInfo *cell) { - if (cell->constr_parent != nullptr) + if (cell->cluster != ClusterId() && ctx->getClusterRootCell(cell->cluster) != cell) return true; // Only process chain roots if (constraints_satisfied(cell)) { - if (cell->constr_children.size() > 0 || cell->constr_x != cell->UNCONSTR || - cell->constr_y != cell->UNCONSTR || cell->constr_z != cell->UNCONSTR) + if (cell->cluster != ClusterId()) lockdown_chain(cell); } else { IncreasingDiameterSearch xRootSearch, yRootSearch, zRootSearch; @@ -332,21 +303,10 @@ class ConstraintLegaliseWorker 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 - 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); + xRootSearch = IncreasingDiameterSearch(currentLoc.x, 0, ctx->getGridDimX() - 1); + yRootSearch = IncreasingDiameterSearch(currentLoc.y, 0, ctx->getGridDimY() - 1); + zRootSearch = IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y)); - if (cell->constr_z == cell->UNCONSTR) - zRootSearch = - IncreasingDiameterSearch(currentLoc.z, 0, ctx->getTileBelDimZ(currentLoc.x, currentLoc.y)); - else - zRootSearch = IncreasingDiameterSearch(cell->constr_z); while (!xRootSearch.done()) { Loc rootLoc; @@ -415,29 +375,13 @@ class ConstraintLegaliseWorker bool constraints_satisfied(const CellInfo *cell) { return get_constraints_distance(ctx, cell) == 0; } public: - ConstraintLegaliseWorker(Context *ctx) : ctx(ctx){}; - - void print_chain(CellInfo *cell, int depth = 0) + ConstraintLegaliseWorker(Context *ctx) : ctx(ctx) { - 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); - } + for (auto cell : sorted(ctx->cells)) { + if (cell.second->cluster != ClusterId()) + cluster2cells[cell.second->cluster].push_back(cell.second); + } + }; unsigned print_stats(const char *point) { @@ -476,8 +420,6 @@ class ConstraintLegaliseWorker 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 -1; } @@ -509,30 +451,36 @@ int get_constraints_distance(const Context *ctx, const CellInfo *cell) if (cell->bel == BelId()) return 100000; 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 { - 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)); - 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)); + + if (cell->cluster != ClusterId()) { + CellInfo *root = ctx->getClusterRootCell(cell->cluster); + if (root == cell) { + // parent + std::vector<std::pair<CellInfo *, BelId>> placement; + if (!ctx->getClusterPlacement(cell->cluster, cell->bel, placement)) { + return 100000; + } else { + for (const auto &p : placement) { + if (p.first->bel == BelId()) + return 100000; + Loc c_loc = ctx->getBelLocation(p.first->bel); + Loc p_loc = ctx->getBelLocation(p.second); + dist += std::abs(c_loc.x - p_loc.x); + dist += std::abs(c_loc.y - p_loc.y); + dist += std::abs(c_loc.z - p_loc.z); + } + } + } else { + // child + if (root->bel == BelId()) + return 100000; + Loc root_loc = ctx->getBelLocation(root->bel); + Loc offset = ctx->getClusterOffset(cell); + dist += std::abs((root_loc.x + offset.x) - loc.x); + dist += std::abs((root_loc.y + offset.y) - loc.y); } } - for (auto child : cell->constr_children) - dist += get_constraints_distance(ctx, child); + return dist; } diff --git a/common/placer1.cc b/common/placer1.cc index 1f940dac..a3e7a696 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -225,14 +225,16 @@ class SAPlacer } else { for (auto &cell : ctx->cells) { CellInfo *ci = cell.second.get(); - if (ci->belStrength > STRENGTH_STRONG) + if (ci->belStrength > STRENGTH_STRONG) { continue; - else if (ci->constr_parent != nullptr) - continue; - else if (!ci->constr_children.empty() || ci->constr_z != ci->UNCONSTR) - chain_basis.push_back(ci); - else + } else if (ci->cluster != ClusterId()) { + if (ctx->getClusterRootCell(ci->cluster) == ci) + chain_basis.push_back(ci); + else + continue; + } else { autoplaced.push_back(ci); + } } require_legal = false; diameter = 3; @@ -359,8 +361,8 @@ class SAPlacer autoplaced.clear(); chain_basis.clear(); for (auto cell : sorted(ctx->cells)) { - if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->constr_parent == nullptr && - !cell.second->constr_children.empty()) + if (cell.second->belStrength <= STRENGTH_STRONG && cell.second->cluster != ClusterId() && + ctx->getClusterRootCell(cell.second->cluster) == cell.second) chain_basis.push_back(cell.second); else if (cell.second->belStrength < STRENGTH_STRONG) autoplaced.push_back(cell.second); @@ -507,12 +509,12 @@ class SAPlacer { static const double epsilon = 1e-20; moveChange.reset(this); - if (!require_legal && cell->isConstrained(false)) + if (!require_legal && cell->cluster != ClusterId()) return false; BelId oldBel = cell->bel; CellInfo *other_cell = ctx->getBoundBelCell(newBel); if (!require_legal && other_cell != nullptr && - (other_cell->isConstrained(false) || other_cell->belStrength > STRENGTH_WEAK)) { + (other_cell->cluster != ClusterId() || other_cell->belStrength > STRENGTH_WEAK)) { return false; } int old_dist = get_constraints_distance(ctx, cell); @@ -612,9 +614,9 @@ class SAPlacer if (bound != nullptr) ctx->unbindBel(newBel); ctx->unbindBel(oldBel); - ctx->bindBel(newBel, cell, cell->isConstrained(false) ? STRENGTH_STRONG : STRENGTH_WEAK); + ctx->bindBel(newBel, cell, (cell->cluster != ClusterId()) ? STRENGTH_STRONG : STRENGTH_WEAK); if (bound != nullptr) { - ctx->bindBel(oldBel, bound, bound->isConstrained(false) ? STRENGTH_STRONG : STRENGTH_WEAK); + ctx->bindBel(oldBel, bound, (bound->cluster != ClusterId()) ? STRENGTH_STRONG : STRENGTH_WEAK); if (cfg.netShareWeight > 0) update_nets_by_tile(bound, ctx->getBelLocation(newBel), ctx->getBelLocation(oldBel)); } @@ -623,16 +625,6 @@ class SAPlacer return oldBel; } - // Discover the relative positions of all cells in a chain - void discover_chain(Loc baseLoc, CellInfo *cell, std::vector<std::pair<CellInfo *, Loc>> &cell_rel) - { - Loc cellLoc = ctx->getBelLocation(cell->bel); - Loc rel{cellLoc.x - baseLoc.x, cellLoc.y - baseLoc.y, cellLoc.z}; - cell_rel.emplace_back(std::make_pair(cell, rel)); - for (auto child : cell->constr_children) - discover_chain(baseLoc, child, cell_rel); - } - // Attempt to swap a chain with a non-chain bool try_swap_chain(CellInfo *cell, BelId newBase) { @@ -647,32 +639,23 @@ class SAPlacer if (ctx->debug) log_info("finding cells for chain swap %s\n", cell->name.c_str(ctx)); #endif - Loc baseLoc = ctx->getBelLocation(cell->bel); - discover_chain(baseLoc, cell, cell_rel); - Loc newBaseLoc = ctx->getBelLocation(newBase); - NPNR_ASSERT(newBaseLoc.z == baseLoc.z); - for (const auto &cr : cell_rel) - cells.insert(cr.first->name); - - for (const auto &cr : cell_rel) { - Loc targetLoc = {newBaseLoc.x + cr.second.x, newBaseLoc.y + cr.second.y, cr.second.z}; - BelId targetBel = ctx->getBelByLocation(targetLoc); - if (targetBel == BelId()) - return false; - if (!ctx->isValidBelForCellType(cell->type, targetBel)) - return false; - CellInfo *bound = ctx->getBoundBelCell(targetBel); + if (!ctx->getClusterPlacement(cell->cluster, newBase, dest_bels)) + return false; + + for (const auto &db : dest_bels) + cells.insert(db.first->name); + + for (const auto &db : dest_bels) { + CellInfo *bound = ctx->getBoundBelCell(db.second); // We don't consider swapping chains with other chains, at least for the time being - unless it is // part of this chain if (bound != nullptr && !cells.count(bound->name) && - (bound->belStrength >= STRENGTH_STRONG || bound->isConstrained(false))) + (bound->belStrength >= STRENGTH_STRONG || bound->cluster != ClusterId())) return false; if (bound != nullptr) - if (!ctx->isValidBelForCellType(bound->type, cr.first->bel)) + if (!ctx->isValidBelForCellType(bound->type, db.first->bel)) return false; - - dest_bels.emplace_back(std::make_pair(cr.first, targetBel)); } #if 0 if (ctx->debug) diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 042f3046..2f7c7ccb 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -145,6 +145,10 @@ class HeAPPlacer Eigen::initParallel(); tmg.setup_only = true; tmg.setup(); + + for (auto cell : sorted(ctx->cells)) + if (cell.second->cluster != ClusterId()) + cluster2cells[cell.second->cluster].push_back(cell.second); } bool place() @@ -386,14 +390,8 @@ class HeAPPlacer // cells of a certain type) std::vector<CellInfo *> solve_cells; - // For cells in a chain, this is the ultimate root cell of the chain (sometimes this is not constr_parent - // where chains are within chains - std::unordered_map<IdString, CellInfo *> chain_root; - std::unordered_map<IdString, int> chain_size; - - // The offset from chain_root to a cell in the chain - std::unordered_map<IdString, std::pair<int, int>> cell_offsets; - + std::unordered_map<ClusterId, std::vector<CellInfo *>> cluster2cells; + std::unordered_map<ClusterId, int> chain_size; // Performance counting double solve_time = 0, cl_time = 0, sl_time = 0; @@ -549,7 +547,7 @@ class HeAPPlacer cell_locs[cell.first].y = loc.y; cell_locs[cell.first].locked = true; cell_locs[cell.first].global = ctx->getBelGlobalBuf(ci->bel); - } else if (ci->constr_parent == nullptr) { + } else if (ci->cluster == ClusterId() || ctx->getClusterRootCell(ci->cluster) == ci) { bool placed = false; int attempt_count = 0; while (!placed) { @@ -629,40 +627,27 @@ class HeAPPlacer solve_cells.push_back(cell); } // Finally, update the udata of children - for (auto chained : chain_root) - ctx->cells.at(chained.first)->udata = chained.second->udata; + for (auto &cluster : cluster2cells) + for (auto child : cluster.second) + child->udata = ctx->getClusterRootCell(cluster.first)->udata; return row; } - // Update the location of all children of a chain - void update_chain(CellInfo *cell, CellInfo *root) - { - const auto &base = cell_locs[cell->name]; - for (auto child : cell->constr_children) { - // FIXME: Improve handling of heterogeneous chains - if (child->type == root->type) - chain_size[root->name]++; - if (child->constr_x != child->UNCONSTR) - cell_locs[child->name].x = std::max(0, std::min(max_x, base.x + child->constr_x)); - else - cell_locs[child->name].x = base.x; // better handling of UNCONSTR? - if (child->constr_y != child->UNCONSTR) - cell_locs[child->name].y = std::max(0, std::min(max_y, base.y + child->constr_y)); - else - cell_locs[child->name].y = base.y; // better handling of UNCONSTR? - chain_root[child->name] = root; - if (!child->constr_children.empty()) - update_chain(child, root); - } - } - // Update all chains void update_all_chains() { for (auto cell : place_cells) { chain_size[cell->name] = 1; - if (!cell->constr_children.empty()) - update_chain(cell, cell); + if (cell->cluster != ClusterId()) { + const auto &base = cell_locs[cell->name]; + for (auto child : cluster2cells.at(cell->cluster)) { + if (child->type == cell->type && child != cell) + chain_size[cell->name]++; + Loc offset = ctx->getClusterOffset(child); + cell_locs[child->name].x = std::max(0, std::min(max_x, base.x + offset.x)); + cell_locs[child->name].y = std::max(0, std::min(max_y, base.y + offset.y)); + } + } } } @@ -721,10 +706,9 @@ class HeAPPlacer } else { es.add_rhs(row, -v_pos * weight); } - if (cell_offsets.count(var.cell->name)) { - es.add_rhs(row, -(yaxis ? cell_offsets.at(var.cell->name).second - : cell_offsets.at(var.cell->name).first) * - weight); + if (var.cell->cluster != ClusterId()) { + Loc offset = ctx->getClusterOffset(var.cell); + es.add_rhs(row, -(yaxis ? offset.y : offset.x) * weight); } }; @@ -827,8 +811,9 @@ class HeAPPlacer // Unbind all cells placed in this solution for (auto cell : sorted(ctx->cells)) { CellInfo *ci = cell.second; - if (ci->bel != BelId() && (ci->udata != dont_solve || - (chain_root.count(ci->name) && chain_root.at(ci->name)->udata != dont_solve))) + if (ci->bel != BelId() && + (ci->udata != dont_solve || + (ci->cluster != ClusterId() && ctx->getClusterRootCell(ci->cluster)->udata != dont_solve))) ctx->unbindBel(ci->bel); } @@ -955,7 +940,7 @@ class HeAPPlacer break; } - if (ci->constr_children.empty() && !ci->constr_abs_z) { + if (ci->cluster == ClusterId()) { // The case where we have no relative constraints for (auto sz : fb->at(nx).at(ny)) { // Look through all bels in this tile; checking region constraint if applicable @@ -967,7 +952,7 @@ class HeAPPlacer CellInfo *bound = ctx->getBoundBelCell(sz); if (bound != nullptr) { // Only rip up cells without constraints - if (bound->isConstrained()) + if (bound->cluster != ClusterId()) continue; ctx->unbindBel(bound->bel); } @@ -1019,45 +1004,23 @@ class HeAPPlacer } else { // We do have relative constraints for (auto sz : fb->at(nx).at(ny)) { - Loc loc = ctx->getBelLocation(sz); - // Check that the absolute-z constraint is satisfied if applicable - if (ci->constr_abs_z && loc.z != ci->constr_z) - continue; // List of cells and their destination std::vector<std::pair<CellInfo *, BelId>> targets; // List of bels we placed things at; and the cell that was there before if applicable std::vector<std::pair<BelId, CellInfo *>> swaps_made; - // List of (cell, new location) pairs to check - std::queue<std::pair<CellInfo *, Loc>> visit; - // FIXME: this approach of having a visit queue is designed to deal with recursively chained - // cells. But is this a case we really want to care about given the complexity it adds? Start by - // considering the root cell at the root location - visit.emplace(ci, loc); - while (!visit.empty()) { - CellInfo *vc = visit.front().first; - NPNR_ASSERT(vc->bel == BelId()); - Loc ploc = visit.front().second; - visit.pop(); - // Get the bel we're going to place this cell at - BelId target = ctx->getBelByLocation(ploc); + + if (!ctx->getClusterPlacement(ci->cluster, sz, targets)) + continue; + + for (auto &target : targets) { // Check it satisfies the region constraint if applicable - if (!vc->testRegion(target)) - goto fail; - CellInfo *bound; - // Check that the target bel exists and is of a suitable type - if (target == BelId() || !ctx->isValidBelForCellType(vc->type, target)) + if (!target.first->testRegion(target.second)) goto fail; - bound = ctx->getBoundBelCell(target); + CellInfo *bound = ctx->getBoundBelCell(target.second); // Chains cannot overlap; so if we have to ripup a cell make sure it isn't part of a chain if (bound != nullptr) - if (bound->isConstrained() || bound->belStrength > STRENGTH_WEAK) + if (bound->cluster != ClusterId() || bound->belStrength > STRENGTH_WEAK) goto fail; - targets.emplace_back(vc, target); - for (auto child : vc->constr_children) { - // For all the constrained children; compute the location we need to place them at and - // add them to the queue - visit.emplace(child, child->getConstrainedLoc(ploc)); - } } // Actually perform the move; keeping track of the moves we make so we can revert them if needed for (auto &target : targets) { @@ -1307,10 +1270,8 @@ class HeAPPlacer occupancy.at(cell_loc.second.x).at(cell_loc.second.y).at(cell_index(cell))++; // Compute ultimate extent of each chain root - if (p->chain_root.count(cell_name)) { - set_chain_ext(p->chain_root.at(cell_name)->name, loc.x, loc.y); - } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { - set_chain_ext(cell_name, loc.x, loc.y); + if (cell.cluster != ClusterId()) { + set_chain_ext(ctx->getClusterRootCell(cell.cluster)->name, loc.x, loc.y); } } @@ -1328,10 +1289,8 @@ class HeAPPlacer // Transfer chain extents to the actual chains structure ChainExtent *ce = nullptr; - if (p->chain_root.count(cell_name)) { - ce = &(cell_extents.at(p->chain_root.at(cell_name)->name)); - } else if (!ctx->cells.at(cell_name)->constr_children.empty()) { - ce = &(cell_extents.at(cell_name)); + if (cell.cluster != ClusterId()) { + ce = &(cell_extents.at(ctx->getClusterRootCell(cell.cluster)->name)); } if (ce) { diff --git a/common/timing_opt.cc b/common/timing_opt.cc index dba96bf1..854cbc5b 100644 --- a/common/timing_opt.cc +++ b/common/timing_opt.cc @@ -182,8 +182,7 @@ class TimingOptimiser CellInfo *bound = ctx->getBoundBelCell(bel); if (bound == nullptr) { free_bels_at_loc.push_back(bel); - } else if (bound->belStrength <= STRENGTH_WEAK && bound->constr_parent == nullptr && - bound->constr_children.empty()) { + } else if (bound->belStrength <= STRENGTH_WEAK && bound->cluster == ClusterId()) { bound_bels_at_loc.push_back(bel); } } @@ -378,7 +377,7 @@ class TimingOptimiser if (front_net != nullptr && front_net->driver.cell != nullptr) { auto front_cell = front_net->driver.cell; if (front_cell->belStrength <= STRENGTH_WEAK && cfg.cellTypes.count(front_cell->type) && - front_cell->constr_parent == nullptr && front_cell->constr_children.empty()) { + front_cell->cluster == ClusterId()) { path_cells.push_back(front_cell->name); } } @@ -392,7 +391,7 @@ class TimingOptimiser if (std::find(path_cells.begin(), path_cells.end(), port->cell->name) != path_cells.end()) continue; if (port->cell->belStrength > STRENGTH_WEAK || !cfg.cellTypes.count(port->cell->type) || - port->cell->constr_parent != nullptr || !port->cell->constr_children.empty()) + port->cell->cluster != ClusterId()) continue; if (ctx->debug) log_info(" can move\n"); diff --git a/docs/archapi.md b/docs/archapi.md index 45d77007..6d17f01a 100644 --- a/docs/archapi.md +++ b/docs/archapi.md @@ -736,13 +736,13 @@ Gets the root cell of a cluster, which is used as a datum point when placing the Gets an approximate bounding box of the cluster. This is intended for area allocation in the placer and is permitted to occasionally give incorrect estimates, for example due to irregularities in the fabric depending on cluster placement. `getClusterPlacement` should always be used to get exact locations. -### Loc getClusterOffset(CellInfo \*cell) const +### Loc getClusterOffset(const CellInfo \*cell) const Gets the approximate offset of a cell within its cluster, relative to the root cell. This is intended for global placement usage and is permitted to occasionally give incorrect estimates, for example due to irregularities in the fabric depending on cluster placement. `getClusterPlacement` should always be used to get exact locations. The returned x and y coordinates, when added to the root location of the cluster, should give an approximate location where `cell` will end up placed at. -### bool isClusterStrict(CellInfo *cell) const +### bool isClusterStrict(const CellInfo *cell) const Returns `true` if the cell **must** be placed according to the cluster; for example typical carry chains, and dedicated IO routing. Returns `false` if the cell can be split from the cluster if placement desires, at the expense of a less optimal result (for example dedicated LUT-FF paths where general routing can also be used). |