8#ifndef AIE_DIALECT_AIE_TRANSFORMS_AIEBUFFERALLOCATION_H
9#define AIE_DIALECT_AIE_TRANSFORMS_AIEBUFFERALLOCATION_H
14#include "llvm/ADT/ArrayRef.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/IntEqClasses.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Support/MathExtras.h"
36 AIETileType tileType) {
37 if (tileType == AIETileType::MemTile) {
55 uint32_t maxVecAlignBits,
57 if (maxVecAlignBits <= busAlignBits)
59 return sizeBytes * 8 >=
static_cast<int64_t
>(maxVecAlignBits)
73template <
typename Range,
typename BytesFn>
75 llvm::stable_sort(buffers, [&](
const auto &a,
const auto &b) {
76 return bytes(a) > bytes(b);
87 llvm::SmallVector<std::pair<int64_t, int64_t>> pinned;
88 llvm::SmallVector<BufferAllocation *> pending;
89 int64_t highWater = start;
90 for (
auto &buffer : buffers) {
92 pinned.emplace_back(*buffer.address, buffer.size);
93 highWater = std::max(highWater, *buffer.address + buffer.size);
95 pending.push_back(&buffer);
98 llvm::stable_sort(pinned, [](
auto a,
auto b) {
return a.first < b.first; });
100 auto *current = pinned.begin();
101 int64_t address = start;
102 for (
auto *buffer : pending) {
103 address = llvm::alignTo(address, buffer->alignment);
104 while (current != pinned.end() && address + buffer->size > current->first) {
106 llvm::alignTo(current->first + current->second, buffer->alignment);
109 buffer->address = address;
110 address += buffer->size;
112 return std::max(highWater, address);
132inline llvm::SmallVector<unsigned>
134 llvm::SmallVector<unsigned> homes;
135 llvm::SmallVector<llvm::SmallVector<unsigned>> perHome;
136 for (
auto [index, pool] : llvm::enumerate(pools)) {
137 auto *at = llvm::find(homes, pool.home);
138 if (at == homes.end()) {
139 homes.push_back(pool.home);
140 perHome.emplace_back();
141 at = std::prev(homes.end());
143 perHome[at - homes.begin()].push_back(index);
145 for (
auto &list : perHome)
146 llvm::stable_sort(list, [&](
unsigned a,
unsigned b) {
147 if (pools[a].demand != pools[b].demand)
148 return pools[a].demand > pools[b].demand;
149 return pools[a].bytes > pools[b].bytes;
151 llvm::SmallVector<unsigned> order;
152 llvm::SmallVector<size_t> next(perHome.size(), 0);
153 for (
size_t slot = 0; slot < pools.size(); ++slot) {
154 std::optional<size_t> best;
155 for (
size_t home = 0; home < perHome.size(); ++home) {
156 if (next[home] >= perHome[home].size())
158 const SpillPool &pool = pools[perHome[home][next[home]]];
160 best ? &pools[perHome[*best][next[*best]]] :
nullptr;
165 order.push_back(perHome[*best][next[*best]++]);
172inline llvm::SmallVector<TileID, 2>
174 llvm::SmallVector<TileID, 2> neighbours;
175 for (
int col = 0; col < target.
columns(); ++col) {
178 TileID neighbour{col, home.row};
184 neighbours.push_back(neighbour);
193 llvm::ArrayRef<TileID> homes,
194 llvm::function_ref<llvm::SmallVector<TileID, 2>(
TileID)> neighboursOf) {
195 llvm::DenseMap<TileID, unsigned> index;
196 llvm::IntEqClasses eq;
197 auto indexOf = [&](
TileID tile) {
198 auto [it, fresh] = index.try_emplace(tile, index.size());
200 eq.grow(index.size());
203 for (
TileID home : homes) {
204 unsigned at = indexOf(home);
205 for (
TileID neighbour : neighboursOf(home))
206 eq.join(indexOf(neighbour), at);
209 llvm::SmallVector<unsigned> component;
211 component.push_back(eq[indexOf(home)]);
214inline llvm::SmallVector<unsigned>
216 llvm::ArrayRef<TileID> homes) {
233 llvm::SmallVector<BufferAllocation>
fixed;
250 : tiles(std::move(tiles)), planned(this->tiles.size()),
251 alignment(alignment) {
252 weighed.assign(this->tiles.size(),
false);
253 plannedBytes.assign(this->tiles.size(), 0);
254 misaligned.assign(this->tiles.size(), 0);
255 for (
const Tile &tile : this->tiles) {
257 return !b.address && b.size % alignment == 0;
261 bytes += buffer.
size;
262 fixedBytes.push_back(packed ? std::optional<int64_t>(bytes)
268 int64_t
used(
unsigned tile, int64_t bytes = 0,
int count = 0)
const {
271 if (fixedBytes[tile] && !misaligned[tile] && bytes % alignment == 0)
272 return *fixedBytes[tile] + plannedBytes[tile] + count * bytes;
273 llvm::SmallVector<BufferAllocation> layout;
274 for (int64_t size : planned[tile])
275 layout.push_back({size, alignment, std::nullopt});
276 for (
int i = 0; i < count; ++i)
277 layout.push_back({bytes, alignment, std::nullopt});
278 llvm::append_range(layout, tiles[tile].fixed);
281 bool fits(
unsigned tile, int64_t bytes,
int count = 1)
const {
282 return used(tile, bytes, count) <= tiles[tile].capacity;
284 void reserve(
unsigned tile, int64_t bytes,
int count = 1) {
285 for (
int i = 0; i < count; ++i)
298 bool place(llvm::ArrayRef<Buffer> buffers) {
299 llvm::IntEqClasses eq(tiles.size());
300 for (
const Buffer &buffer : buffers)
301 for (
unsigned neighbour : buffer.neighbours)
302 eq.join(neighbour, buffer.home);
304 llvm::MapVector<unsigned, llvm::SmallVector<unsigned>> components;
305 for (
auto [index, buffer] : llvm::enumerate(buffers))
306 components[eq[buffer.home]].push_back(index);
308 llvm::SmallVector<unsigned> placedOn(buffers.size(), 0);
309 size_t firstFailed = buffers.size();
310 int64_t unplaced = 0;
311 for (
auto &[_, members] : components) {
312 llvm::SmallVector<Buffer> component;
313 for (
unsigned index : members)
314 component.push_back(buffers[index]);
316 failed = component.size();
319 if (placeFrom(component, 0, retries)) {
320 for (
auto [index, tile] : llvm::zip_equal(members,
chosen))
321 placedOn[index] = tile;
326 removeLast(
chosen.pop_back_val());
327 firstFailed = std::min<size_t>(
328 firstFailed, members[std::min<size_t>(
failed, members.size() - 1)]);
331 chosen = std::move(placedOn);
334 return firstFailed == buffers.size();
344 llvm::SmallVector<unsigned> spillTargets(
const Buffer &buffer) {
346 llvm::SmallVector<unsigned, 2> neighbours(buffer.
neighbours);
348 if (neighbours.size() == 2) {
349 if (
used(neighbours[1]) <
used(neighbours[0]))
350 std::swap(neighbours[0], neighbours[1]);
352 llvm::stable_sort(neighbours, [&](
unsigned a,
unsigned b) {
356 llvm::SmallVector<unsigned> fitting;
357 for (
unsigned neighbour : neighbours)
359 fitting.push_back(neighbour);
363 bool placeFrom(llvm::ArrayRef<Buffer> buffers,
size_t index,
int &retries) {
364 if (index == buffers.size())
366 const Buffer &buffer = buffers[index];
367 bool fitsHome = buffer.atHome &&
fits(buffer.home, buffer.bytes);
368 llvm::SmallVector<unsigned> candidates;
370 candidates.push_back(buffer.home);
372 candidates = spillTargets(buffer);
373 if (candidates.empty() && index <
failed) {
376 for (
const Buffer &left : buffers.drop_front(index))
379 auto tryTile = [&](
unsigned tile) {
380 add(tile, buffer.bytes);
382 if (placeFrom(buffers, index + 1, retries))
388 for (
auto [i, tile] : llvm::enumerate(candidates)) {
389 if (i > 0 && retries-- <= 0)
396 for (
unsigned tile : spillTargets(buffer)) {
405 void add(
unsigned tile, int64_t bytes) {
406 planned[tile].push_back(bytes);
407 plannedBytes[tile] += bytes;
408 misaligned[tile] += bytes % alignment != 0;
410 void removeLast(
unsigned tile) {
411 int64_t bytes = planned[tile].pop_back_val();
412 plannedBytes[tile] -= bytes;
413 misaligned[tile] -= bytes % alignment != 0;
416 llvm::SmallVector<Tile> tiles;
417 llvm::SmallVector<llvm::SmallVector<int64_t>> planned;
421 llvm::SmallVector<std::optional<int64_t>> fixedBytes;
422 llvm::SmallVector<int64_t> plannedBytes;
423 llvm::SmallVector<int> misaligned;
429 uint32_t maxVecAlignBits) {
430 int64_t sectionAlign = buffer.getSectionAlignment();
431 if (!buffer.getAligned())
435 buffer.getAllocationSize()) /
507 llvm::SmallVector<std::optional<std::pair<int64_t, int>>>
at;
virtual uint32_t getLocalMemorySize() const =0
Return the size (in bytes) of the local data memory of a core.
virtual uint32_t getComputeTileLoadStoreBusWidth() const =0
Return the data bus width (in bits) for load/store operations of a compute core.
virtual bool isValidTile(TileID src) const
Return true if the given tile ID is valid.
virtual uint32_t getComputeTileMaxVectorAlignBits() const
Return the alignment (in bits) required by the widest vector load/store a compute core can issue.
virtual int columns() const =0
Return the number of columns in the device.
virtual uint32_t getMemTileLoadStoreBusWidth() const
Return the data bus width (in bits) for load/store operations of a memory tile.
@ Second
Only the second tile's module.
SharedMemory getSharedMemory(TileID a, TileID b) const
Return the memory module a and b can both reach, if any.
virtual uint32_t getMemTileSize() const =0
Return the size (in bytes) of a MemTile.
void reserve(unsigned tile, int64_t bytes, int count=1)
bool place(llvm::ArrayRef< Buffer > buffers)
Places buffers in order on top of what the tiles hold.
llvm::SmallVector< bool > weighed
Homes a spill from was weighed: aie-objectfifo-allocate gives their neighbours tile ops,...
static constexpr int kRetries
Alternatives the search tries before it gives up.
MemTileSpillSearch(llvm::SmallVector< Tile > tiles, int64_t alignment)
bool fits(unsigned tile, int64_t bytes, int count=1) const
llvm::SmallVector< unsigned > chosen
int64_t used(unsigned tile, int64_t bytes=0, int count=0) const
The bytes tile spans with what it holds and count more of bytes.
void sortLargestBufferFirst(Range &&buffers, BytesFn bytes)
Buffers are laid out, and given a tile, largest buffer first: by the address layout below,...
TileLayout layoutTile(const TileLayoutProblem &problem, TileLayoutStats &stats)
Lays out problem as assign-buffer-addresses does, without touching IR.
TileLayoutBuffer tileLayoutBuffer(BufferOp buffer, const TileMemoryLimits &limits)
What assign-buffer-addresses lays buffer out as, on a tile with limits.
llvm::SmallVector< unsigned > demandFirstOrder(llvm::ArrayRef< SpillPool > pools)
aie-objectfifo-allocate's demand-first packing order of pools, given in its size-first order,...
llvm::SmallVector< TileID, 2 > memTileSpillNeighbours(const AIETargetModel &target, TileID home)
The tiles a mem tile buffer homed at home may spill to: those in its row home shares memory with,...
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
constexpr int64_t kDefaultPlacementBudget
assign-buffer-addresses' placement-budget unless set.
uint32_t requiredBufferAlignBits(uint32_t busAlignBits, uint32_t maxVecAlignBits, int64_t sizeBytes)
Return the alignment (in bits) a buffer of sizeBytes must satisfy.
int64_t assignSequentialBufferAddresses(llvm::MutableArrayRef< BufferAllocation > buffers, int64_t start=0)
The basic address allocator and resource planner share this layout: retain address pins,...
int64_t bufferAlignBytes(BufferOp buffer, uint32_t tileAlignBitWidth, uint32_t maxVecAlignBits)
The alignment assign-buffer-addresses places buffer at, in bytes: the vector rule when aligned,...
TileMemoryLimits tileMemoryLimits(const AIETargetModel &targetModel, AIETileType tileType)
llvm::SmallVector< unsigned > memTileSpillComponents(llvm::ArrayRef< TileID > homes, llvm::function_ref< llvm::SmallVector< TileID, 2 >(TileID)> neighboursOf)
For each of homes, the index of its component: homes whose buffers may spill to a tile in common,...
std::optional< int64_t > address
A buffer of bytes homed on home, which it may take unless atHome is false, and the neighbours it may ...
llvm::SmallVector< unsigned, 2 > neighbours
Buffer(int64_t bytes, unsigned home, bool atHome, llvm::SmallVector< unsigned, 2 > neighbours)
llvm::SmallVector< BufferAllocation > fixed
Tile(int64_t capacity, llvm::SmallVector< BufferAllocation > fixed)
A mem tile pool as aie-objectfifo-allocate packs it: count buffers of bytes homed on home,...
SpillPool(int64_t bytes, int64_t count, unsigned home, int demand)
One buffer of a tile, as assign-buffer-addresses lays it out.
std::optional< int64_t > address
int64_t alignBytes
bufferAlignBytes.
llvm::SmallVector< int, 2 > spaceBanks
The banks the buffer's memory space allows, when it names some.
int64_t sectionAlignBytes
The measured section alignment a pinned address must meet.
std::optional< int32_t > memBank
bool initialized
Whether the buffer has an initial value, which keeps it off TileLayoutProblem::initGuardBytes.
bool aligned
Whether a pinned address must meet the bus width.
A tile's data memory and what it must hold.
llvm::SmallVector< TileLayoutBuffer > buffers
In the order the device holds them.
bool hasCore
Whether the tile runs a core, whose sections need a contiguous region.
MemoryRun stackRun
The core's stack; empty without one.
int64_t maxDataMemorySize
std::optional< int > stackBank
For a stack pinned to a bank but not an address: the bank, and the alignment of the address chosen in...
int64_t budget
Placements each search may try before it gives up.
uint32_t tileAlignBitWidth
int64_t initGuardBytes
Bytes at the start of the tile an initialized buffer must not cover.
What the searches cost, for –mlir-pass-statistics.
assign-buffer-addresses' layout of one tile, or why there is none.
llvm::SmallVector< std::optional< std::pair< int64_t, int > > > at
Address and bank of each buffer placed: every buffer when Placed, and the pinned ones plus the deepes...
@ StackNoRoom
The bank-pinned stack has no room; message says why.
@ NoRoom
Buffer failed fits nowhere once the others are placed.
@ BadPin
Buffer failed has a pin or bank request the tile cannot honour; message says why.
llvm::SmallVector< int, 2 > failedBanks
The banks buffer failed must lie in, and on NoRoom with one bank, the bytes free there.
llvm::SmallVector< size_t > preAllocated
The buffers with an address or bank pin, in the order they were placed, and the others in the order t...
bool exhausted
Whether the search ran out of budget with arrangements untried.
int64_t unplacedBytes
Bytes of the buffers left without an address on NoRoom.
std::optional< int64_t > stackStart
The address chosen for a bank-pinned stack.
llvm::SmallVector< size_t > allocated
A memtile is reached by DMA rather than by core vector load and store, so its bus width also covers t...
int64_t maxDataMemorySize
uint32_t tileAlignBitWidth