12#include "llvm/ADT/DenseSet.h"
13#include "llvm/ADT/IntEqClasses.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/Sequence.h"
22llvm::SmallVector<mlir::Operation *>
24 llvm::SmallVector<mlir::Operation *> owners;
27 owners.push_back(pool);
30 for (
auto segment : pool.getSegmentOps())
31 if (!(segment.getProduceLock() && segment.getConsumeLock()))
32 owners.push_back(segment);
39 llvm::DenseMap<TileID, int> before = used;
40 llvm::SmallVector<Placed> misses;
42 llvm::SmallVector<llvm::SmallVector<unsigned>> eligible;
43 auto findEligible = [&] {
44 if (!eligible.empty() || groups.empty())
47 llvm::SmallVector<unsigned> &tilesOf = eligible.emplace_back();
48 for (
unsigned tile :
group.candidates)
49 if (!llvm::is_contained(tilesOf, tile) &&
50 llvm::all_of(
group.users,
51 [&](
const User &user) { return reaches(user, tile); }))
52 tilesOf.push_back(tile);
55 auto record = [&](
size_t index,
const Placed &at) {
56 result.
tiles[index] = at.tile;
58 if (!at.tile && !result.
failed) {
63 auto firstFit = [&](
bool canonical) {
66 result.
tiles.assign(groups.size(), std::nullopt);
67 misses.assign(groups.size(), {});
69 for (
auto [index,
group] : llvm::enumerate(groups))
74 for (
auto &[index, at] : canonicalFirstFit(groups, eligible))
77 int count = groups.empty() ? 0 : groups.front().count;
79 llvm::any_of(groups, [&](
const Group &g) {
return g.
count != count; });
80 firstFit(!callerOrder);
83 if (callerOrder && mixed) {
85 llvm::SmallVector<Placed> ownMisses = misses;
86 llvm::DenseMap<TileID, int> ownUsed = used;
90 result = std::move(own);
91 misses = std::move(ownMisses);
92 used = std::move(ownUsed);
97 llvm::SmallVector<std::optional<unsigned>> packed;
98 llvm::SmallVector<unsigned> blocked;
101 std::vector<int64_t> key;
104 for (
const llvm::SmallVector<unsigned> &tilesOf : eligible)
105 size += 2 + 3 * tilesOf.size();
107 for (
auto [
group, tilesOf] : llvm::zip(groups, eligible)) {
108 llvm::append_values(key,
group.count, tilesOf.size());
109 for (
unsigned tile : tilesOf) {
110 if (std::optional<TileID> at = tiles[tile].at)
111 llvm::append_values(key, at->col, at->row, before.lookup(*at));
113 llvm::append_values(key, -1, -1, -1);
117 const Outcome *recorded = memo ? memo->
find(key) :
nullptr;
120 packing = recorded->packing;
121 blocked = recorded->blocked;
122 for (
auto [tilesOf, offset] : llvm::zip(eligible, recorded->offsets))
123 packed.push_back(tilesOf[offset]);
124#ifdef EXPENSIVE_CHECKS
125 llvm::SmallVector<std::optional<unsigned>> freshPacked;
126 llvm::SmallVector<unsigned> freshBlocked;
127 assert(pack(groups, eligible, before, freshPacked, freshBlocked) ==
129 freshBlocked == blocked &&
130 (packing != Packing::Found || freshPacked == packed) &&
131 "a recorded packing differs from a fresh one");
134 packing = pack(groups, eligible, before, packed, blocked);
136 Outcome outcome{packing, blocked, {}};
137 if (packing == Packing::Found)
139 for (
auto [tilesOf, tile] : llvm::zip(eligible, packed))
141 outcome.offsets.push_back(llvm::find(tilesOf, *tile) -
143 memo->
record(std::move(key), std::move(outcome));
146 if (packing == Packing::Found) {
147 result.
tiles = std::move(packed);
150 for (
auto [
group, tile] : llvm::zip(groups, result.
tiles))
152 if (std::optional<TileID> at = tiles[*tile].at)
153 used[*at] +=
group.count;
156 result.
stopped = packing == Packing::Stopped;
157 for (
unsigned group : blocked)
166 llvm::DenseMap<TileID, llvm::SmallVector<size_t>> members;
167 auto assignTo = [&](
size_t group,
unsigned tile) {
170 members[*tiles[tile].at].push_back(
group);
172 auto unassign = [&](
size_t group) {
173 if (std::optional<TileID> at = tiles[*result.
tiles[
group]].at)
174 llvm::erase(members[*at],
group);
177 for (
auto [
group, tile] : llvm::enumerate(result.
tiles))
179 if (std::optional<TileID> at = tiles[*tile].at)
180 members[*at].push_back(
group);
181 auto slots = [&](
TileID at) {
182 return (
static_cast<int>(target.getNumLocks(at.col, at.row)) -
186 llvm::DenseSet<TileID> visited;
187 std::function<bool(
size_t)> augment = [&](
size_t group) {
188 for (
unsigned tile : eligible[
group]) {
189 std::optional<TileID> at = tiles[tile].at;
191 assignTo(
group, tile);
194 if (!visited.insert(*at).second)
196 if (
static_cast<int>(members[*at].size()) < slots(*at)) {
197 assignTo(
group, tile);
200 for (
size_t other : llvm::SmallVector<size_t>(members[*at])) {
201 unsigned held = *result.
tiles[other];
203 if (augment(other)) {
204 assignTo(
group, tile);
207 assignTo(other, held);
220 for (std::optional<unsigned> tile : result.
tiles)
222 if (std::optional<TileID> at = tiles[*tile].at)
225 for (
auto [
group, tile] : llvm::enumerate(result.
tiles)) {
229 result.
failure = {std::nullopt, !eligible[
group].empty(),
230 eligible[
group].empty()
232 : std::optional(eligible[
group].back())};
238llvm::SmallVector<std::pair<size_t, LockPlan::Placed>>
239LockPlan::canonicalFirstFit(
240 llvm::ArrayRef<Group> groups,
241 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible) {
242 auto rank = [&](
unsigned tile) {
243 std::optional<TileID> at = tiles[tile].at;
244 return at ? std::make_tuple(1, at->col, at->row) : std::make_tuple(0, 0, 0);
246 llvm::SmallVector<llvm::SmallVector<unsigned>> sorted;
247 llvm::SmallVector<llvm::SmallVector<std::tuple<int, int, int>>> keys;
248 for (
const llvm::SmallVector<unsigned> &tilesOf : eligible) {
249 llvm::SmallVector<unsigned> &order = sorted.emplace_back(tilesOf);
251 order, [&](
unsigned a,
unsigned b) {
return rank(a) < rank(b); });
252 keys.push_back(llvm::map_to_vector(order, rank));
254 llvm::SmallVector<size_t> order =
255 llvm::to_vector(llvm::seq<size_t>(0, groups.size()));
256 llvm::stable_sort(order, [&](
size_t a,
size_t b) {
257 if (groups[a].count != groups[b].count)
258 return groups[a].count > groups[b].count;
259 return keys[a] < keys[b];
261 llvm::SmallVector<std::pair<size_t, Placed>> placed;
262 for (
size_t index : order) {
265 for (
unsigned tile : sorted[index]) {
266 if (
reserve(tile, groups[index].count)) {
274 placed.push_back({index, at});
280LockPlan::pack(llvm::ArrayRef<Group> groups,
281 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible,
282 const llvm::DenseMap<TileID, int> &before,
283 llvm::SmallVectorImpl<std::optional<unsigned>> &chosen,
284 llvm::SmallVectorImpl<unsigned> &blocked)
const {
285 chosen.assign(groups.size(), std::nullopt);
287 llvm::SmallVector<TileID> positions;
288 llvm::SmallVector<llvm::SmallVector<unsigned>> reach(groups.size());
289 for (
auto [
group, tilesOf] : llvm::enumerate(eligible)) {
290 if (tilesOf.empty()) {
291 blocked.push_back(
group);
292 return Packing::None;
294 for (
unsigned tile : tilesOf) {
297 positions.push_back(*tiles[tile].at);
302 llvm::sort(positions);
303 positions.erase(llvm::unique(positions), positions.end());
304 for (
auto [
group, tilesOf] : llvm::enumerate(eligible)) {
305 for (
unsigned tile : tilesOf) {
306 if (!tiles[tile].at) {
307 chosen[
group] = tile;
311 llvm::find(positions, *tiles[tile].at) - positions.begin();
312 if (!llvm::is_contained(reach[
group], position))
313 reach[
group].push_back(position);
315 llvm::sort(reach[
group]);
318 llvm::IntEqClasses component(positions.size());
319 for (
auto [
group, own] : llvm::enumerate(reach))
321 for (
unsigned position : own)
322 component.join(position, own.front());
323 component.compress();
325 bool anyStopped =
false;
326 llvm::SmallVector<bool> seen(component.getNumClasses(),
false);
327 for (
unsigned first : llvm::seq<unsigned>(0, positions.size())) {
328 unsigned top = component[first];
333 bool stopped =
false;
334 llvm::SmallVector<unsigned> local;
335 for (
unsigned position : llvm::seq<unsigned>(0, positions.size()))
336 if (component[position] == top)
337 local.push_back(position);
338 std::vector<int> room;
339 for (
unsigned position : local) {
340 TileID at = positions[position];
342 std::max(0,
static_cast<int>(target.getNumLocks(at.col, at.row)) -
349 llvm::SmallVector<unsigned> reach;
350 llvm::SmallVector<unsigned> members;
352 llvm::SmallVector<Kind> kinds;
353 for (
auto [
group, own] : llvm::enumerate(reach)) {
354 if (chosen[
group] || own.empty() || component[own.front()] != top)
356 llvm::SmallVector<unsigned> at;
357 for (
unsigned position : own)
358 at.push_back(llvm::find(local, position) - local.begin());
359 auto *kind = llvm::find_if(kinds, [&,
group =
group](
const Kind &k) {
360 return k.count == groups[
group].count && k.reach == at;
362 if (kind == kinds.end()) {
363 kinds.push_back({groups[
group].count, at, {}});
364 kind = std::prev(kinds.end());
366 kind->members.push_back(
group);
368 llvm::stable_sort(kinds, [](
const Kind &a,
const Kind &b) {
369 return a.count != b.count ? a.count > b.count : a.reach < b.reach;
374 std::vector<int> open(local.size(), 1), taken(kinds.size(), 0);
375 llvm::SmallVector<llvm::SmallVector<unsigned>> where(kinds.size());
376 std::set<std::pair<std::vector<int>, std::vector<int>>> failed;
379 std::vector<std::vector<int>> flow;
380 std::vector<int> spare;
381 llvm::SmallVector<bool> visited;
382 std::function<int(
unsigned,
int)> augment = [&](
unsigned kind,
int amount) {
383 for (
unsigned position : kinds[kind].reach) {
384 if (!open[position] || visited[position])
386 visited[position] =
true;
387 if (
int direct = std::min(amount, spare[position])) {
388 spare[position] -= direct;
389 flow[kind][position] += direct;
392 for (
unsigned other : llvm::seq<unsigned>(0, kinds.size())) {
393 if (other == kind || !flow[other][position])
396 augment(other, std::min(amount, flow[other][position]))) {
397 flow[other][position] -= moved;
398 flow[kind][position] += moved;
405 auto covers = [&]() {
406 flow.assign(kinds.size(), std::vector<int>(local.size(), 0));
408 for (
auto [kind, k] : llvm::enumerate(kinds)) {
409 int supply = (k.members.size() - taken[kind]) * k.count;
411 visited.assign(local.size(),
false);
412 int moved = augment(kind, supply);
420 std::function<bool()> complete = [&]() {
426 llvm::SmallVector<bool> useful(local.size(),
false);
427 for (
auto [kind, k] : llvm::enumerate(kinds)) {
428 int left = k.members.size() - taken[kind];
431 demand += left * k.count;
433 for (
unsigned position : k.reach)
434 if (open[position]) {
435 useful[position] =
true;
436 fits |= room[position] >= k.count;
443 if (failed.count({open, taken}))
446 for (
unsigned position : llvm::seq<unsigned>(0, local.size()))
447 if (useful[position])
448 capacity += room[position];
449 int slack = capacity - demand;
452 auto unfilled = [&](
unsigned position,
int skip) {
453 std::vector<char> sums(room[position] + 1, 0);
455 for (
auto [kind, k] : llvm::enumerate(kinds)) {
456 if (k.count == skip || !llvm::is_contained(k.reach, position))
458 int copies = std::min<int>(k.members.size() - taken[kind],
459 room[position] / k.count);
460 for (
int copy = 0; copy < copies; ++copy)
461 for (
int sum = room[position]; sum >= k.count; --sum)
462 sums[sum] |= sums[sum - k.count];
464 int most = room[position];
467 return room[position] - most;
469 std::vector<int> least(local.size(), 0);
471 for (
unsigned position : llvm::seq<unsigned>(0, local.size()))
472 if (useful[position]) {
473 least[position] = unfilled(position, 0);
474 wasted += least[position];
479 for (
auto *kind = kinds.begin(); kind != kinds.end();) {
480 int count = kind->count, copies = 0;
481 for (; kind != kinds.end() && kind->count == count; ++kind)
482 copies += kind->members.size() - taken[kind - kinds.begin()];
484 llvm::SmallVector<int> gains;
485 for (
unsigned position : llvm::seq<unsigned>(0, local.size())) {
486 if (!useful[position])
488 int lost = unfilled(position, count);
490 if (lost > least[position])
491 gains.push_back(lost - least[position]);
493 if (copies >=
static_cast<int>(gains.size()))
495 llvm::sort(gains, std::greater<int>());
496 for (
int gain : llvm::ArrayRef(gains).take_front(copies))
498 bound = std::max(bound, without);
500 if (slack < bound || !covers()) {
501 failed.insert({open, taken});
506 auto onlyAt = [&](
const Kind &k,
unsigned position) {
507 return llvm::all_of(k.reach, [&](
unsigned other) {
508 return other == position || !open[other];
511 std::optional<unsigned> best;
513 for (
unsigned position : llvm::seq<unsigned>(0, local.size())) {
514 if (!useful[position])
517 for (
auto [kind, k] : llvm::enumerate(kinds))
518 if (taken[kind] <
static_cast<int>(k.members.size()) &&
519 llvm::is_contained(k.reach, position) && !onlyAt(k, position))
520 choices += k.members.size() - taken[kind];
521 if (!best || choices < bestChoices) {
523 bestChoices = choices;
526 unsigned position = *best;
527 int fill = room[position];
528 llvm::SmallVector<unsigned> free;
529 std::vector<int> held = taken;
530 for (
auto [kind, k] : llvm::enumerate(kinds)) {
531 int left = k.members.size() - taken[kind];
532 if (!left || !llvm::is_contained(k.reach, position))
534 if (onlyAt(k, position)) {
535 fill -= left * k.count;
538 free.push_back(kind);
541 int maxWaste = std::min(slack - wasted + least[position], room[position]);
543 std::vector<std::vector<char>> later(
544 free.size() + 1, std::vector<char>(room[position] + 1, 0));
546 for (
size_t next = free.size(); next-- > 0;) {
547 const Kind &k = kinds[free[next]];
548 later[next] = later[next + 1];
549 int copies = std::min<int>(k.members.size() - taken[free[next]],
550 room[position] / k.count);
551 for (
int copy = 0; copy < copies; ++copy)
552 for (
int sum = room[position]; sum >= k.count; --sum)
553 later[next][sum] |= later[next][sum - k.count];
556 std::function<bool(
size_t,
int)> choose = [&](
size_t next,
int left) {
561 if (left < 0 || llvm::none_of(
562 llvm::seq(std::max(0, left - maxWaste), left + 1),
563 [&](
int fill) {
return later[next][fill]; }))
565 if (next == free.size())
567 unsigned kind = free[next];
568 const Kind &k = kinds[kind];
570 std::min<int>(k.members.size() - taken[kind], left / k.count);
571 for (
int n = most; n >= 0; --n) {
573 bool done = choose(next + 1, left - n * k.count);
576 where[kind].append(n, local[position]);
584 bool done = choose(0, fill);
587 for (
auto [kind, k] : llvm::enumerate(kinds))
588 where[kind].append(taken[kind] - held[kind], local[position]);
590 taken = std::move(held);
591 if (!done && !stopped)
592 failed.insert({open, taken});
600 for (
auto [
group, own] : llvm::enumerate(reach))
601 if (!chosen[
group] && !own.empty() && component[own.front()] == top)
602 blocked.push_back(
group);
603 return Packing::None;
605 for (
auto [kind, k] : llvm::enumerate(kinds))
606 for (
auto [
group, position] : llvm::zip(k.members, where[kind]))
607 chosen[
group] = *llvm::find_if(
608 eligible[
group], [&, position = position](
unsigned tile) {
609 return tiles[tile].at == positions[position];
612 return anyStopped ? Packing::Stopped : Packing::Found;
void record(Key key, Value value)
Records value for key, replacing any result it had, and forgets the least recently used result past c...
const Value * find(const Key &key)
The result recorded for key, now the most recently used, or null.
Placed place(const Group &group)
static llvm::SmallVector< mlir::Operation * > lockOwners(const AIETargetModel &target, ObjectFifoPoolOp pool)
The ops whose locks allocation and the SA each make for pool: with semaphore locks,...
static constexpr int64_t kPackBudget
Steps the exact packing of groups of different counts may take on each connected component.
Assignment assign(llvm::ArrayRef< Group > groups, Memo *memo=nullptr, bool callerOrder=true)
Places groups first fit: with callerOrder, in order on each one's candidates, then in canonical order...
bool reserve(unsigned tile, int count)
Takes count locks on tile, or returns false when it has too few left.
BoundedMemo< std::vector< int64_t >, Outcome > Memo
Packings by what pack() reads, the least recently used dropped first beyond its capacity.
static Group group(int count, unsigned home, bool local, llvm::ArrayRef< unsigned > buffers, llvm::ArrayRef< User > users, llvm::ArrayRef< unsigned > ranked)
A group of count locks a pool's objects are counted by: on home, else, unless the pool must stay loca...
struct TileID { friend std::ostream &operator<<(std::ostream &os, const TileID &s) { os<< "TileID("<< s.col<< ", "<< s.row<< ")"; return os; } friend std::string to_string(const TileID &s) { std::ostringstream ss; ss<< s; return ss.str(); } friend llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const TileID &s) { os<< to_string(s); return os; } inline bool operator<(const TileID &rhs) const { return std::tie(col, row)< std::tie(rhs.col, rhs.row); } bool operator==(const TileID &rhs) const { return std::tie(col, row)==std::tie(rhs.col, rhs.row); } bool operator!=(const TileID &rhs) const { return !(*this==rhs);} int col, row;} TileID
std::optional< size_t > failed
The first group no assignment finds room for: first fit's miss, or, after packing or matching run,...
size_t unassigned
How many groups no assignment finds room for.
llvm::SmallVector< std::optional< unsigned > > tiles
bool stopped
The exact packing ran out of kPackBudget steps before it decided.
bool reachable
Some candidate every user reaches.
A tile using the locks, localOnly when only its own (dmaLocalOnly).