8#ifndef AIE_DIALECT_AIE_TRANSFORMS_AIELOCKPLAN_H
9#define AIE_DIALECT_AIE_TRANSFORMS_AIELOCKPLAN_H
14#include "llvm/ADT/ArrayRef.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallVector.h"
28class ObjectFifoPoolOp;
37 std::optional<TileID>
at;
50 std::optional<unsigned>
tile;
54 std::optional<unsigned>
full;
58 enum class Packing { Found,
None, Stopped };
64 llvm::SmallVector<unsigned> blocked;
65 llvm::SmallVector<unsigned> offsets;
80 int64_t depth,
int owners) {
82 return llvm::SmallVector<int>(owners, 2);
85 return {
static_cast<int>(depth)};
91 return type != AIETileType::MemTile;
97 static llvm::SmallVector<mlir::Operation *>
101 tiles.push_back(std::move(tile));
102 return tiles.size() - 1;
110 TileID at = *tiles[tile].at;
111 int &taken = used[at];
112 if (taken + count >
static_cast<int>(target.getNumLocks(at.col, at.row)))
121 llvm::ArrayRef<TileID> memory,
bool localOnly) {
124 if (localOnly && u != m)
126 auto shared = target.getSharedMemory(u, m);
134 return user.
tile == tile ||
reaches(target, tiles[user.
tile].positions,
142 llvm::ArrayRef<unsigned> buffers,
143 llvm::ArrayRef<User> users,
144 llvm::ArrayRef<unsigned> ranked) {
145 Group group{count, {home}, llvm::to_vector(users)};
147 llvm::append_range(
group.candidates, buffers);
148 for (
const User &user : users)
149 group.candidates.push_back(user.tile);
150 llvm::append_range(
group.candidates, ranked);
157 for (
unsigned tile :
group.candidates) {
158 if (!llvm::all_of(
group.users,
159 [&](
const User &user) { return reaches(user, tile); }))
173 llvm::SmallVector<std::optional<unsigned>>
tiles;
192 bool callerOrder =
true);
205 llvm::SmallVector<std::pair<size_t, Placed>>
206 canonicalFirstFit(llvm::ArrayRef<Group> groups,
207 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible);
220 Packing pack(llvm::ArrayRef<Group> groups,
221 llvm::ArrayRef<llvm::SmallVector<unsigned>> eligible,
222 const llvm::DenseMap<TileID, int> &before,
223 llvm::SmallVectorImpl<std::optional<unsigned>> &chosen,
224 llvm::SmallVectorImpl<unsigned> &blocked)
const;
227 llvm::SmallVector<Tile> tiles;
228 llvm::DenseMap<TileID, int> used;
@ Second
Only the second tile's module.
A memo that keeps its capacity most recently used results, each key stored once.
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 llvm::SmallVector< int > groupCounts(const AIETargetModel &target, int64_t depth, int owners)
The lock groups owners lock owners of a pool of depth objects take, by count.
bool reaches(const User &user, unsigned tile) const
static constexpr int64_t kPackBudget
Steps the exact packing of groups of different counts may take on each connected component.
unsigned addTile(Tile tile)
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...
static bool dmaLocalOnly(AIETileType type)
Whether a DMA on a tile of type uses only its own tile's locks: every DMA does but a mem tile's.
bool reserve(unsigned tile, int count)
Takes count locks on tile, or returns false when it has too few left.
LockPlan(const AIETargetModel &target)
BoundedMemo< std::vector< int64_t >, Outcome > Memo
Packings by what pack() reads, the least recently used dropped first beyond its capacity.
static bool reaches(const AIETargetModel &target, llvm::ArrayRef< TileID > user, llvm::ArrayRef< TileID > memory, bool localOnly)
Whether a tile at one of user reaches memory at one of memory; with localOnly, only at its own positi...
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.
llvm::SmallVector< User > users
llvm::SmallVector< unsigned > candidates
std::optional< unsigned > tile
bool reachable
Some candidate every user reaches.
std::optional< unsigned > full
The last such candidate, when all were full.
A tile's candidate positions, and the one placement chose, once it has.
llvm::SmallVector< TileID, 1 > positions
std::optional< TileID > at
A tile using the locks, localOnly when only its own (dmaLocalOnly).