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 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 121 insertions(+) (limited to 'common/place_common.cc') 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 -- 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(-) (limited to 'common/place_common.cc') 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 ++++++ 1 file changed, 6 insertions(+) (limited to 'common/place_common.cc') 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; + } } } -- 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(-) (limited to 'common/place_common.cc') 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(-) (limited to 'common/place_common.cc') 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 +++++++++ 1 file changed, 9 insertions(+) (limited to 'common/place_common.cc') 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; } } -- 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(-) (limited to 'common/place_common.cc') 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 ++++++++++++++++++++++++++++++++------------------ 1 file changed, 46 insertions(+), 26 deletions(-) (limited to 'common/place_common.cc') 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) -- 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/place_common.cc | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'common/place_common.cc') 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; } }; -- 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(-) (limited to 'common/place_common.cc') 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 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 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) (limited to 'common/place_common.cc') 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), -- 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 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'common/place_common.cc') 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; } } -- 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(-) (limited to 'common/place_common.cc') 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