MLIR-AIE 1.4.6.dev
AIEAssignBuffers.cpp
Go to the documentation of this file.
1//===- AIEAssignBuffers.cpp -------------------------------------*- C++ -*-===//
2//
3// Copyright (C) 2019-2022 Xilinx, Inc.
4// Copyright (C) 2022-2026 Advanced Micro Devices, Inc.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
14
15#include "mlir/IR/Attributes.h"
16
17#include "llvm/ADT/BitVector.h"
18
19#include <limits>
20#include <optional>
21#include <set>
22
23namespace xilinx::AIE {
24#define GEN_PASS_DEF_AIEASSIGNBUFFERADDRESSES
25#define GEN_PASS_DEF_AIEPREPAREBUFFERS
26#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
27} // namespace xilinx::AIE
28
29#define DEBUG_TYPE "aie-assign-buffers"
30
31using namespace mlir;
32using namespace xilinx;
33using namespace xilinx::AIE;
34
35// Absent unless aiecc measured the core.
36static std::optional<int64_t> getMeasuredStackSize(TileOp tile) {
37 CoreOp core = tile.getCoreOp();
38 if (!core) {
39 return std::nullopt;
40 }
41 if (auto measured = core.getMeasuredStackSize()) {
42 return static_cast<int64_t>(*measured);
43 }
44 return std::nullopt;
45}
46
47// Every buffer must already have an address.
48static void sortBuffersByAddress(SmallVectorImpl<BufferOp> &buffers) {
49 llvm::sort(buffers, [](BufferOp a, BufferOp b) {
50 assert(a.getAddress().has_value() && "buffer must have address assigned");
51 assert(b.getAddress().has_value() && "buffer must have address assigned");
52 return a.getAddress().value() < b.getAddress().value();
53 });
54}
55
56// How a diagnostic names an extent. The allocator creates the core_data and
57// bank_reserved buffers itself, so their symbols appear in no user source and
58// naming them would send the reader looking for something they never wrote.
59static std::string bufferLabel(BufferOp buffer) {
60 if (buffer.getCoreData()) {
61 return "this core's data sections (data_size)";
62 }
63 if (buffer.getBankReserved()) {
64 return "this core's static data pinned to bank " +
65 std::to_string(buffer.getMemBank().value_or(0));
66 }
67 // aie-prepare-buffers names every buffer, but this pass also runs alone.
68 if (!buffer.hasName()) {
69 return "an unnamed buffer";
70 }
71 return ("buffer \"" + buffer.name().getValue() + "\"").str();
72}
73
74// The name a memory map prints for an extent.
75static StringRef mapLabel(BufferOp buffer) {
76 if (buffer.getCoreData()) {
77 return StringRef("(core data sections)");
78 }
79 if (buffer.getBankReserved()) {
80 return StringRef("(bank-pinned static data)");
81 }
82 if (!buffer.hasName()) {
83 return StringRef("(unnamed buffer)");
84 }
85 return buffer.name().getValue();
86}
87
88// Gives each CoreOp::getSectionReservations extent an aie.buffer so placement
89// fits around it. Idempotent: this pass runs standalone and inside larger
90// pipelines.
91static LogicalResult materializeCoreSections(DeviceOp device) {
93 OpBuilder builder = OpBuilder::atBlockTerminator(device.getBody());
94 for (auto core : llvm::to_vector(device.getOps<CoreOp>())) {
95 SmallVector<CoreSectionReservation> reservations =
96 core.getSectionReservations();
97 if (reservations.empty()) {
98 continue;
99 }
100 auto tile = dyn_cast_or_null<TileOp>(core.getTile().getDefiningOp());
101 if (!tile) {
102 return core.emitOpError(
103 "reserves memory for its own sections, but its tile is not placed; "
104 "run --aie-place-tiles first");
105 }
106 std::string at =
107 std::to_string(tile.getCol()) + "_" + std::to_string(tile.getRow());
108 SmallVector<BufferOp> holders =
109 core.getSectionReservationBuffers(reservations);
110 for (auto [held, holder] : llvm::zip_equal(reservations, holders)) {
111 if (holder) {
112 continue;
113 }
114 std::string name =
115 held.kind == Kind::DataRegion ? "core_data_" + at
116 : held.kind == Kind::Bank
117 ? "bank_reserved_" + at + "_" + std::to_string(held.at)
118 : "prebaked_" + at + "_" + std::to_string(held.at);
119 // A buffer that is not the reservation's exact extent cannot stand in
120 // for it, and a second one cannot be made beside it.
121 BufferOp clash;
122 bool dataRegion = held.kind == Kind::DataRegion;
123 device.walk([&](BufferOp buffer) {
124 if (buffer.getSymName() == StringRef(name) ||
125 (dataRegion && buffer.getCoreData() &&
126 buffer.getTile() == tile.getResult()))
127 clash = buffer;
128 });
129 if (clash) {
130 return clash.emitOpError("has the name or role of core (")
131 << tile.getCol() << ", " << tile.getRow() << ")'s " << held.bytes
132 << "-byte section reservation but not its extent; remove it "
133 "and let this pass create it";
134 }
135 builder.setInsertionPoint(core);
136 auto type = MemRefType::get({held.bytes}, builder.getI8Type());
137 auto buffer = BufferOp::create(
138 builder, core.getLoc(), type, tile.getResult(),
139 /*sym_name=*/nullptr,
140 /*address=*/
141 held.kind == Kind::Prebaked ? builder.getI32IntegerAttr(held.at)
142 : nullptr,
143 /*initial_value=*/nullptr,
144 /*mem_bank=*/
145 held.kind == Kind::Bank ? builder.getI32IntegerAttr(held.at)
146 : nullptr,
147 /*core_data=*/held.kind == Kind::DataRegion,
148 /*bank_reserved=*/held.kind != Kind::DataRegion,
149 /*aligned=*/held.aligned());
150 buffer->setAttr(SymbolTable::getSymbolAttrName(),
151 builder.getStringAttr(name));
152 }
153 }
154 return success();
155}
156
157// A singleton address space supplies the bank pin (BufferOp::verify has
158// already checked an explicit pin against it); pairs stay flexible until
159// placement.
160//
161// The buffer carries the space rather than the kernel's declaration doing so
162// alone, because `func.call` already requires operand types to match the
163// callee's signature exactly, so all that is left is to place the buffer where
164// its type says it lives.
165static void applySignatureBankConstraints(DeviceOp device) {
166 device.walk([&](BufferOp buffer) {
167 SmallVector<int, 2> banks = banksFromMemorySpace(buffer.getType());
168 if (banks.size() == 1 && !buffer.getMemBank())
169 buffer.setMemBankAttr(IntegerAttr::get(
170 IntegerType::get(device.getContext(), 32), banks.front()));
171 });
172}
173
174static bool isBufferPreAllocated(BufferOp buffer) {
175 auto addr = buffer.getAddress();
176 auto memBank = buffer.getMemBank();
177 return (addr != std::nullopt || memBank != std::nullopt);
178}
179
180// Check alignment (when `aligned` is set) and that no two buffers overlap. The
181// input vector must be sorted by ascending address. Returns false and emits an
182// error on the first offending buffer; true otherwise.
183static bool checkAndPrintBufferOverlap(ArrayRef<BufferOp> sortedBuffers,
184 uint32_t tileAlignBitWidth,
185 uint32_t maxVecAlignBits) {
186 BufferOp prev = nullptr;
187 for (auto cur : sortedBuffers) {
188 auto curAddrOpt = cur.getAddress();
189 assert(curAddrOpt.has_value() && "buffer must have address assigned");
190 int64_t curAddr = *curAddrOpt;
191
192 // A pinned buffer must satisfy the bus width. The stricter vector
193 // requirement applies to the addresses this pass chooses.
194 uint32_t reqAlignBits =
195 isBufferPreAllocated(cur)
196 ? tileAlignBitWidth
197 : requiredBufferAlignBits(tileAlignBitWidth, maxVecAlignBits,
198 cur.getAllocationSize());
199 uint32_t alignByteWidth = reqAlignBits / 8;
200 if (cur.getAligned() && alignByteWidth != 0 &&
201 curAddr % alignByteWidth != 0) {
202 cur.emitOpError("") << bufferLabel(cur) << " at address 0x"
203 << llvm::utohexstr(curAddr)
204 << " is not aligned to the required " << reqAlignBits
205 << " bits";
206 return false;
207 }
208
209 // A zero-sized buffer covers no bytes; skip it to avoid a false overlap
210 // when it shares an address.
211 if (cur.getAllocationSize() == 0) {
212 continue;
213 }
214
215 if (prev) {
216 auto prevAddrOpt = prev.getAddress();
217 assert(prevAddrOpt.has_value() && "buffer must have address assigned");
218 int64_t prevAddr = *prevAddrOpt;
219 int64_t prevEnd = prevAddr + prev.getAllocationSize();
220 if (curAddr < prevEnd) {
221 cur.emitOpError("")
222 << bufferLabel(cur) << " at address 0x" << llvm::utohexstr(curAddr)
223 << " overlaps with " << bufferLabel(prev) << " at address 0x"
224 << llvm::utohexstr(prevAddr)
225 << " (size: " << prev.getAllocationSize() << " bytes)";
226 return false;
227 }
228 }
229 prev = cur;
230 }
231 return true;
232}
233
234static bool checkAndPrintOverlapStackframe(MemoryRun stackRun,
235 ArrayRef<BufferOp> buffers) {
236 for (auto buf : buffers) {
237 // A zero-sized buffer covers no bytes, so it cannot overlap the stack.
238 if (buf.getAllocationSize() == 0) {
239 continue;
240 }
241 auto bufAddrOpt = buf.getAddress();
242 assert(bufAddrOpt.has_value() && "buffer must have address assigned");
243 int64_t bufAddr = *bufAddrOpt;
244 int64_t bufEnd = bufAddr + buf.getAllocationSize();
245 if (bufAddr < stackRun.end() && stackRun.start < bufEnd) {
246 buf.emitOpError("") << bufferLabel(buf) << " at address 0x"
247 << llvm::utohexstr(bufAddr) << " overlaps the stack ("
248 << stackRun.size << " bytes at 0x"
249 << llvm::utohexstr(stackRun.start) << ")";
250 return false;
251 }
252 }
253 return true;
254}
255
256// One line of a memory-map diagnostic. Both diagnostics below call this, so
257// they format their lines identically.
258static void printMemoryMapEntry(Diagnostic &note, StringRef name,
259 int64_t address, int64_t size, int indent,
260 StringRef suffix = "") {
261 for (int i = 0; i < indent; ++i) {
262 note << "\t";
263 }
264 int64_t end = size == 0 ? address : address + size - 1;
265 note << name << " \t"
266 << ": 0x" << llvm::utohexstr(address) << "-0x" << llvm::utohexstr(end)
267 << " \t(" << size << " bytes)" << suffix << "\n";
268}
269
270//===----------------------------------------------------------------------===//
271// SimpleBankAwareAllocation : round-robin each alloc over available banks
272//===----------------------------------------------------------------------===//
273// Compute the extent of each bank.
274static void fillBankLimits(int numBanks, int64_t bankSize,
275 std::vector<MemoryRun> &bankLimits) {
276 for (int i = 0; i < numBanks; i++) {
277 bankLimits.push_back({bankSize * i, bankSize});
278 }
279}
280
281namespace {
282// Which bytes of one tile's data memory are taken. Byte-granular, because a
283// buffer marked `aligned = false` is packed at an unaligned offset.
284class MemoryOccupancy {
285public:
286 explicit MemoryOccupancy(int64_t size) : occupied(size, false) {}
287
288 int64_t size() const { return occupied.size(); }
289
290 // True when [start, end) lies inside the tile and no byte of it is taken.
291 bool isRangeFree(int64_t start, int64_t end) const {
292 if (start < 0 || end > size() || start > end) {
293 return false;
294 }
295 return start == end || occupied.find_first_in(start, end) == -1;
296 }
297
298 void markOccupied(int64_t start, int64_t end) {
299 assert(start >= 0 && end <= size() && start <= end &&
300 "range must lie inside the tile");
301 if (start < end) {
302 occupied.set(start, end);
303 }
304 }
305
306 // Undo a markOccupied. The caller lifts the core's data-region placeholder
307 // once every buffer is placed. No buffer lies inside the placeholder's range,
308 // so clearing exactly that range is exact.
309 void markFree(int64_t start, int64_t end) {
310 assert(start >= 0 && end <= size() && start <= end &&
311 "range must lie inside the tile");
312 if (start < end) {
313 occupied.reset(start, end);
314 }
315 }
316
317 // Placement for `size` bytes in [lo, hi) that leaves the largest single free
318 // run behind anywhere in [0, size()), or nullopt when nothing fits. An object
319 // placed before the unconstrained buffers -- the core's data region, a
320 // bank-pinned buffer -- keeps more contiguous space when it sits flush
321 // against occupied space. Only the two flush positions of each hole are
322 // candidates, because an interior placement leaves strictly less contiguous
323 // space.
324 std::optional<int64_t> findLeastFragmentingGap(int64_t lo, int64_t hi,
325 int64_t size,
326 int64_t alignBytes) const {
327 assert(alignBytes > 0 && "alignment must be positive");
328 std::optional<int64_t> best;
329 int64_t bestRun = -1;
330 auto consider = [&](int64_t start) {
331 MemoryOccupancy trial = *this;
332 trial.markOccupied(start, start + size);
333 int64_t run = trial.largestGap(0, this->size());
334 // Ties to the lowest address, for determinism.
335 if (run > bestRun || (run == bestRun && best && start < *best)) {
336 bestRun = run;
337 best = start;
338 }
339 };
340 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
341 int64_t low = llvm::alignTo(gapStart, alignBytes);
342 if (low + size > gapEnd) {
343 return;
344 }
345 consider(low);
346 // Flush to the top, aligned down but never below `low`.
347 consider(
348 std::max<int64_t>(llvm::alignDown(gapEnd - size, alignBytes), low));
349 });
350 return best;
351 }
352
353 // Start of the tightest gap in [lo, hi) that holds `size` bytes, or nullopt.
354 // Each candidate start is aligned up before the fit test, so a misaligned
355 // first free byte does not reject a gap.
356 std::optional<int64_t> findGap(int64_t lo, int64_t hi, int64_t size,
357 int64_t alignBytes) const {
358 assert(alignBytes > 0 && "alignment must be positive");
359 std::optional<int64_t> best;
360 int64_t bestSlack = 0;
361 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
362 int64_t start = llvm::alignTo(gapStart, alignBytes);
363 if (start + size <= gapEnd) {
364 // Waste measured across the whole gap, so front-alignment padding
365 // counts and a padded hole does not rank as a tight fit.
366 int64_t slack = (gapEnd - gapStart) - size;
367 if (!best || slack < bestSlack) {
368 best = start;
369 bestSlack = slack;
370 }
371 }
372 });
373 return best;
374 }
375
376 // Total free bytes in [lo, hi).
377 int64_t freeBytes(int64_t lo, int64_t hi) const {
378 int64_t total = 0;
379 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
380 total += gapEnd - gapStart;
381 });
382 return total;
383 }
384
385 // Bytes of the enclosing free run that `size` bytes at `addr` would leave
386 // unused; placement scoring prefers a tight fit to keep large runs whole.
387 int64_t slackAt(int64_t addr, int64_t size) const {
388 int64_t slack = 0;
389 forEachGap(0, this->size(), [&](int64_t gapStart, int64_t gapEnd) {
390 if (addr >= gapStart && addr + size <= gapEnd) {
391 slack = (gapEnd - gapStart) - size;
392 }
393 });
394 return slack;
395 }
396
397 // The free run enclosing `addr`, or a zero-length run if it is taken.
398 MemoryRun gapAt(int64_t addr) const {
399 MemoryRun found;
400 forEachGap(0, this->size(), [&](int64_t gapStart, int64_t gapEnd) {
401 if (addr >= gapStart && addr < gapEnd) {
402 found = {gapStart, gapEnd - gapStart};
403 }
404 });
405 return found;
406 }
407
408 // The two largest free runs by size, duplicates kept, so two equal runs give
409 // {n, n}. A placement consumes one run and leaves the other whole, which lets
410 // a candidate score the run it leaves behind in constant time.
411 std::pair<int64_t, int64_t> topTwoGaps(int64_t lo, int64_t hi) const {
412 int64_t first = 0, second = 0;
413 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
414 int64_t run = gapEnd - gapStart;
415 if (run > first) {
416 second = first;
417 first = run;
418 } else if (run > second) {
419 second = run;
420 }
421 });
422 return {first, second};
423 }
424
425 // Every maximal free run in [lo, hi), lowest first. The search enumerates
426 // candidate placements from these rather than taking the single best run.
427 SmallVector<MemoryRun> gapsIn(int64_t lo, int64_t hi) const {
428 SmallVector<MemoryRun> runs;
429 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
430 runs.push_back({gapStart, gapEnd - gapStart});
431 });
432 return runs;
433 }
434
435 // Largest single free run in [lo, hi). A reservation needs one contiguous
436 // run, which freeBytes does not measure.
437 int64_t largestGap(int64_t lo, int64_t hi) const {
438 int64_t best = 0;
439 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
440 best = std::max(best, gapEnd - gapStart);
441 });
442 return best;
443 }
444
445private:
446 // Calls fn(gapStart, gapEnd) for every maximal free run in [lo, hi).
447 template <typename Fn>
448 void forEachGap(int64_t lo, int64_t hi, Fn fn) const {
449 lo = std::max<int64_t>(lo, 0);
450 hi = std::min(hi, size());
451 for (int64_t cursor = lo; cursor < hi;) {
452 int gapStart = occupied.find_first_unset_in(cursor, hi);
453 if (gapStart == -1) {
454 break;
455 }
456 int nextTaken = occupied.find_first_in(gapStart, hi);
457 // gapStart is clear, so gapEnd > gapStart >= cursor: the cursor advances.
458 int64_t gapEnd = nextTaken == -1 ? hi : nextTaken;
459 fn(gapStart, gapEnd);
460 cursor = gapEnd;
461 }
462 }
463
464 llvm::BitVector occupied;
465};
466} // namespace
467
468// Index of the bank owning `addr`, or -1 when it falls outside every bank.
469static int getBankContaining(int64_t addr, int numBanks,
470 ArrayRef<MemoryRun> bankLimits) {
471 for (int i = 0; i < numBanks; i++) {
472 if (bankLimits[i].contains(addr)) {
473 return i;
474 }
475 }
476 return -1;
477}
478
479// Tile-level constants shared by every bank-aware helper below.
483 ArrayRef<MemoryRun> bankLimits;
486 // Whether this tile has a core, and so compiled sections that need a
487 // contiguous region. A memtile has none.
489 ArrayRef<TileLayoutBuffer> buffers;
490 // Bytes at the start of the tile an initialized buffer must not cover; see
491 // allocateTile. Other buffers may still use them.
492 int64_t initGuardBytes = 0;
493};
494
495// Records buffer `i` at `startAddr` in `bank` and marks the bytes it covers as
496// taken.
497static void placeBuffer(size_t i, int64_t startAddr, int bank,
498 const BankAwareContext &ctx, MemoryOccupancy &occupancy,
499 TileLayout &layout) {
500 layout.at[i] = {startAddr, bank};
501 occupancy.markOccupied(startAddr, startAddr + ctx.buffers[i].size);
502}
503
504// Fails `layout` on buffer `i` with `message`.
505static LogicalResult failPin(TileLayout &layout, size_t i,
506 const llvm::Twine &message) {
508 layout.failed = i;
509 layout.message = message.str();
510 return failure();
511}
512
513// Places a buffer carrying an explicit `address`, and checks that the space is
514// free and that any `mem_bank` agrees. Returns false when the buffer has no
515// address, which leaves it to the mem_bank or free-placement path. Failure is
516// terminal: it fails `layout` and the caller must not retry another scheme.
517static FailureOr<bool> checkAndAddBufferWithAddress(size_t i,
518 const BankAwareContext &ctx,
519 MemoryOccupancy &occupancy,
520 TileLayout &layout) {
521 const TileLayoutBuffer &buffer = ctx.buffers[i];
522 if (!buffer.address) {
523 return false;
524 }
525
526 int64_t addr = *buffer.address;
527 int64_t measuredAlign = buffer.sectionAlignBytes;
528 if (addr % measuredAlign != 0) {
529 return failPin(layout, i,
530 "data reservation address must be aligned to " +
531 llvm::Twine(measuredAlign) +
532 " bytes to satisfy its measured section alignment");
533 }
534
535 // A pinned address must satisfy the bus width. The stricter vector alignment
536 // applies to the addresses this pass chooses.
537 if (buffer.aligned && addr % (ctx.tileAlignBitWidth / 8) != 0) {
538 return failPin(layout, i,
539 "address attribute value must be aligned to " +
540 llvm::Twine(ctx.tileAlignBitWidth) +
541 " bits when the aligned attribute is set");
542 }
543
544 int bank = getBankContaining(addr, ctx.numBanks, ctx.bankLimits);
545 if (bank < 0) {
546 // A zero-sized buffer pinned one past the last bank is legal. Assign it the
547 // last bank, where nothing can conflict with it.
548 if (buffer.size == 0 && addr == ctx.bankLimits.back().end()) {
549 bank = ctx.numBanks - 1;
550 } else {
551 return failPin(layout, i,
552 "address attribute does not fall within any bank range");
553 }
554 }
555
556 int64_t endAddr = addr + buffer.size;
557 if (endAddr > occupancy.size()) {
558 return failPin(layout, i,
559 "address attribute would place the buffer past the end of "
560 "the tile's memory");
561 }
562
563 int lastBank = buffer.size == 0 ? bank
564 : getBankContaining(endAddr - 1, ctx.numBanks,
565 ctx.bankLimits);
566 for (int touched = bank; !buffer.spaceBanks.empty() && touched <= lastBank;
567 ++touched) {
568 if (!llvm::is_contained(buffer.spaceBanks, touched)) {
569 return failPin(layout, i,
570 "address attribute places the buffer in bank " +
571 llvm::Twine(touched) +
572 ", which is excluded by its memory space");
573 }
574 }
575 if (buffer.memBank && *buffer.memBank != bank) {
576 return failPin(layout, i,
577 "address attribute lies in bank " + llvm::Twine(bank) +
578 ", but mem_bank requests bank " +
579 llvm::Twine(*buffer.memBank));
580 }
581
582 // Only a real collision is invalid. The hardware lets a buffer straddle a
583 // bank boundary, so a pinned buffer may extend past `bank`.
584 if (!occupancy.isRangeFree(addr, endAddr)) {
585 return failPin(layout, i, "would override allocated address");
586 }
587
588 placeBuffer(i, addr, bank, ctx, occupancy, layout);
589 return true;
590}
591
592// Banks a buffer may live in because the user requested them, by the
593// buffer's index in the problem.
594using RequiredBanks = DenseMap<size_t, SmallVector<int, 2>>;
595
596// Record the allowed banks, intersected with any explicit mem_bank request.
597// BufferOp::verify has already checked that the intersection is nonempty.
598static LogicalResult recordRequiredBank(size_t i, const BankAwareContext &ctx,
599 RequiredBanks &requiredBanks,
600 TileLayout &layout) {
601 const TileLayoutBuffer &buffer = ctx.buffers[i];
602 if (buffer.memBank &&
603 (*buffer.memBank < 0 || *buffer.memBank >= ctx.numBanks)) {
604 return failPin(layout, i, "mem_bank attribute value is out of range");
605 }
606 SmallVector<int, 2> banks = buffer.spaceBanks;
607 if (buffer.memBank)
608 banks = {*buffer.memBank};
609 if (!banks.empty()) {
610 if (banks.back() >= ctx.numBanks) {
611 return failPin(layout, i,
612 "memory space requests a bank that does not exist");
613 }
614 requiredBanks[i] = std::move(banks);
615 }
616 return success();
617}
618
619static void printMemMap(TileOp tile, ArrayRef<BufferOp> buffers,
620 ArrayRef<std::optional<std::pair<int64_t, int>>> at,
621 ArrayRef<size_t> preAllocated,
622 ArrayRef<size_t> allocated, int numBanks,
623 ArrayRef<MemoryRun> bankLimits, MemoryRun stackRun) {
624 InFlightDiagnostic error = tile.emitWarning(
625 "Not all requested buffers fit in the available memory.\n");
626 auto &note = error.attachNote()
627 << "Current configuration of buffers in bank(s) : ";
628 note << "MemoryMap:\n";
629 auto printbuffer = [&](StringRef name, int64_t address, int64_t size,
630 StringRef suffix = "") {
631 printMemoryMapEntry(note, name, address, size, /*indent=*/2, suffix);
632 };
633 if (stackRun.size == 0) {
634 note << "\t(no stack allocated)\n";
635 }
636 if (auto measured = getMeasuredStackSize(tile)) {
637 note << "\t(aiecc measured this core's stack requirement as " << *measured
638 << " bytes)\n";
639 }
640 for (int bank = 0; bank < numBanks; bank++) {
641 note << "\t" << "bank : " << bank << "\t" << "0x"
642 << llvm::utohexstr(bankLimits[bank].start) << "-0x"
643 << llvm::utohexstr(bankLimits[bank].end() - 1) << "\n";
644 // Under whichever bank holds it, rather than always under bank 0.
645 if (stackRun.size > 0 && bankLimits[bank].contains(stackRun.start)) {
646 printbuffer("(stack)", stackRun.start, stackRun.size);
647 }
648 // This runs on the failure path, where some buffers have no address yet.
649 // A mem_bank-only buffer appears in both lists -- it is pre-allocated in
650 // the sense that its bank was given, but this pass still chose its address
651 // -- so listing it once takes a filter.
652 llvm::DenseSet<size_t> listed;
653 auto printPlaced = [&](ArrayRef<size_t> indices) {
654 for (size_t index : indices) {
655 if (!at[index] || at[index]->second != bank ||
656 !listed.insert(index).second) {
657 continue;
658 }
659 BufferOp buffer = buffers[index];
660 int64_t address = at[index]->first;
661 int64_t size = buffer.getAllocationSize();
662 // Listed under its start bank. A buffer too big for one bank straddles,
663 // so its range can extend past the bank printed above it.
664 std::string suffix;
665 if (address + size > bankLimits[bank].end()) {
666 suffix =
667 (" (straddles into bank " + llvm::Twine(bank + 1) + ")").str();
668 }
669 printbuffer(mapLabel(buffer), address, size, suffix);
670 }
671 };
672 printPlaced(preAllocated);
673 printPlaced(allocated);
674 }
675}
676
677namespace {
678// Sentinel first key for an unscored fallback, so it sorts behind every
679// scored candidate however those score.
680constexpr int64_t kFallbackRank = std::numeric_limits<int64_t>::max();
681
682// Candidate address ordering, lower ranks first:
683// 1. banks touched, fewest first (each spanned bank costs DMA bandwidth);
684// 2. largest free run left behind, biggest first, capped by contiguityCap --
685// the bytes still to place. A run wider than that serves nothing, so past
686// the cap every candidate ties and criterion 3 takes over;
687// 3. round-robin distance from the cursor, nearest first (spreads for DMA);
688// 4. slack, tightest first, which leaves the large runs unbroken;
689// 5. address, lowest first, for determinism.
690// A memtile has no core, so criterion 2 is neutralized there and round-robin
691// governs throughout.
692struct Placement {
693 int64_t addr;
694 int bank;
695 int64_t banksTouched;
696 int64_t negLargestRunLeft;
697 int64_t rrDistance;
698 int64_t slack;
699
700 std::tuple<int64_t, int64_t, int64_t, int64_t, int64_t> rank() const {
701 return {banksTouched, negLargestRunLeft, rrDistance, slack, addr};
702 }
703};
704} // namespace
705
706// Every address `buffer` could take in the current occupancy, best first.
707//
708// The head of this list is the address a single-pass greedy would have chosen,
709// so a design that placed before places identically; the tail is where the
710// search goes when a later buffer is left with nowhere to sit.
711static SmallVector<Placement>
712rankedPlacements(size_t buffer, const BankAwareContext &ctx, int startBankIndex,
713 const RequiredBanks &requiredBanks,
714 const MemoryOccupancy &tileOccupancy, int64_t contiguityCap) {
715 assert(startBankIndex < ctx.numBanks &&
716 "Unexpected input value for startBankIndex");
717 // An initialized buffer sees the guarded bytes as taken, so none of its
718 // candidates cover them. Every other buffer may still be placed there.
719 std::optional<MemoryOccupancy> guarded;
720 if (ctx.initGuardBytes > 0 && ctx.buffers[buffer].initialized) {
721 guarded = tileOccupancy;
722 guarded->markOccupied(0, std::min(ctx.initGuardBytes, guarded->size()));
723 }
724 const MemoryOccupancy &occupancy = guarded ? *guarded : tileOccupancy;
725 int64_t size = ctx.buffers[buffer].size;
726 int64_t alignBytes = ctx.buffers[buffer].alignBytes;
727 SmallVector<Placement> out;
728
729 // A requested bank set is a hard constraint, and the round-robin cursor stays
730 // put. Only the two flush ends of each hole are worth trying, because an
731 // interior start leaves strictly less behind.
732 auto required = requiredBanks.find(buffer);
733 if (required != requiredBanks.end()) {
734 auto &banks = required->second;
735 SmallVector<MemoryRun> ranges;
736 for (int bank : banks)
737 ranges.push_back(ctx.bankLimits[bank]);
738 // Adjacent allowed banks can hold one spanning buffer; a disjoint pair
739 // cannot use the intervening, forbidden bank.
740 if (banks.size() == 2 && banks.back() == banks.front() + 1)
741 ranges.push_back({ctx.bankLimits[banks.front()].start,
742 ctx.bankLimits[banks.front()].size +
743 ctx.bankLimits[banks.back()].size});
744 for (MemoryRun limits : ranges) {
745 for (MemoryRun gap : occupancy.gapsIn(limits.start, limits.end())) {
746 int64_t low = llvm::alignTo(gap.start, alignBytes);
747 if (low + size > gap.end()) {
748 continue;
749 }
750 for (int64_t addr :
751 {low, std::max<int64_t>(
752 llvm::alignDown(gap.end() - size, alignBytes), low)}) {
753 MemoryOccupancy trial = occupancy;
754 trial.markOccupied(addr, addr + size);
755 int bank = getBankContaining(addr, ctx.numBanks, ctx.bankLimits);
756 if (!llvm::is_contained(banks, bank))
757 continue;
758 int lastBank = size == 0
759 ? bank
760 : getBankContaining(addr + size - 1, ctx.numBanks,
761 ctx.bankLimits);
762 out.push_back({addr, bank, /*banksTouched=*/lastBank - bank + 1,
763 -trial.largestGap(0, trial.size()), /*rrDistance=*/0,
764 /*slack=*/0});
765 }
766 }
767 }
768 // A zero-sized buffer needs no free byte, so every bank holds it.
769 if (out.empty() && size == 0) {
770 int bank = banks.front();
771 out.push_back({ctx.bankLimits[bank].start, bank, 1, 0, 0, 0});
772 }
773 } else {
774 int64_t bankedEnd = ctx.bankLimits.back().end();
775 int64_t bankSize = bankedEnd / ctx.numBanks;
776 // Computed once per buffer, not per candidate: every candidate splits one
777 // run, so the largest run left elsewhere is one of these two. Named
778 // separately, because C++17 cannot capture a structured binding in the
779 // lambda below.
780 std::pair<int64_t, int64_t> topGaps =
781 occupancy.topTwoGaps(0, ctx.maxDataMemorySize);
782 int64_t largestRun = topGaps.first, secondRun = topGaps.second;
783 auto consider = [&](std::optional<int64_t> addr) {
784 if (!addr) {
785 return;
786 }
787 int bank = getBankContaining(*addr, ctx.numBanks, ctx.bankLimits);
788 if (bank < 0) {
789 return;
790 }
791 int64_t touched =
792 size == 0 ? 1 : (*addr + size - 1) / bankSize - *addr / bankSize + 1;
793 // This placement splits one run into the piece below and the piece above.
794 // Every other run stays whole, so the biggest of those is whichever of
795 // the top two this candidate does not consume.
796 MemoryRun gap = occupancy.gapAt(*addr);
797 int64_t elsewhere = gap.size == largestRun ? secondRun : largestRun;
798 int64_t leftPiece = *addr - gap.start;
799 int64_t rightPiece = gap.end() - (*addr + size);
800 int64_t runLeft =
801 std::min(std::max({elsewhere, leftPiece, rightPiece}), contiguityCap);
802 out.push_back({*addr, bank, touched, ctx.hasCore ? -runLeft : 0,
803 (bank - startBankIndex + ctx.numBanks) % ctx.numBanks,
804 occupancy.slackAt(*addr, size)});
805 };
806
807 for (int i = 0; i < ctx.numBanks; i++) {
808 consider(occupancy.findGap(ctx.bankLimits[i].start,
809 ctx.bankLimits[i].end(), size, alignBytes));
810 }
811 // Allow straddling when nothing fits one bank. The banked region maps to a
812 // bank, so the result always has one.
813 consider(occupancy.findGap(0, bankedEnd, size, alignBytes));
814 // Try bank-boundary starts only when a boundary also satisfies the buffer's
815 // own alignment, because otherwise this searches on an unintended stride.
816 if (bankSize % alignBytes == 0) {
817 consider(occupancy.findGap(0, bankedEnd, size, bankSize));
818 }
819 // A zero-sized buffer needs no free byte, so a full tile still holds it.
820 if (out.empty() && size == 0) {
821 out.push_back({0, 0, 1, 0, 0, 0});
822 }
823 }
824
825 llvm::stable_sort(out, [](const Placement &a, const Placement &b) {
826 return a.rank() < b.rank();
827 });
828
829 // The probes above ask each hole only for its tightest fit, so a layout
830 // needing some other position in one is unreachable -- and unreachable reads
831 // as "no room". Both flush ends of every hole cover that. Appended after the
832 // sort, never scored: ranking them would move addresses that already work.
833 // Unpinned only; the mem_bank branch above already does this within its bank,
834 // and widening it here would place the buffer outside that bank.
835 if (size > 0 && requiredBanks.find(buffer) == requiredBanks.end()) {
836 for (MemoryRun gap : occupancy.gapsIn(0, ctx.maxDataMemorySize)) {
837 int64_t low = llvm::alignTo(gap.start, alignBytes);
838 if (low + size > gap.end()) {
839 continue;
840 }
841 for (int64_t addr :
842 {low, std::max<int64_t>(
843 llvm::alignDown(gap.end() - size, alignBytes), low)}) {
844 int bank = getBankContaining(addr, ctx.numBanks, ctx.bankLimits);
845 if (bank >= 0) {
846 // Ranks last by construction, so it is only ever reached by
847 // backtracking past every scored candidate.
848 out.push_back({addr, bank, kFallbackRank, 0, 0, 0});
849 }
850 }
851 }
852 }
853
854 // The probes overlap: a gap that is the tightest in its bank is often also
855 // the tightest overall, and the fallbacks repeat whichever of those was a
856 // flush end. Equal addresses are the same placement, and trying one twice
857 // only costs budget. Stable, so the ranked entry survives its duplicate.
858 llvm::stable_sort(out, [](const Placement &a, const Placement &b) {
859 return a.addr < b.addr;
860 });
861 out.erase(
862 llvm::unique(out, [](const Placement &a,
863 const Placement &b) { return a.addr == b.addr; }),
864 out.end());
865 llvm::stable_sort(out, [](const Placement &a, const Placement &b) {
866 return a.rank() < b.rank();
867 });
868 return out;
869}
870
871// Depth-first placement over `order`, trying each buffer's addresses in rank
872// order and undoing a choice that leaves a later buffer nowhere to go.
873//
874// The first descent is exactly what a single-pass greedy produces, so this only
875// does extra work where that pass used to fail outright. On failure `deepest`
876// names the buffer that ran out of addresses furthest into the order, which is
877// the one whose demand the tile could not meet.
878namespace {
879struct PlacementSearch {
880 ArrayRef<size_t> order;
881 const BankAwareContext &ctx;
882 const RequiredBanks &requiredBanks;
883 MemoryOccupancy &occupancy;
884 SmallVectorImpl<size_t> &placed;
885 TileLayoutStats &stats;
886 TileLayout &layout;
887 // How many placements the search may still try on this tile before giving
888 // up and reporting the deepest failure it reached; the pass's
889 // placement-budget option. Packing around fixed obstacles is NP-hard, so the
890 // tree has no useful worst-case bound; this keeps a design the search cannot
891 // solve to bounded compile time instead of exponential. A node count rather
892 // than a time limit, so a build stays reproducible.
893 int64_t budget;
894 // Set when the node budget ran out with candidates still untried, so the
895 // caller can say "gave up" rather than "no such layout exists".
896 bool exhausted = false;
897
898 // The furthest the search reached, kept so a failure can report the layout it
899 // got closest with rather than the empty tile backtracking leaves behind.
900 // First arrangement to reach a given depth wins, not the last: the first
901 // comes down the highest-ranked path, so the map a user sees is the one the
902 // ranking preferred rather than whichever branch happened to be explored
903 // last.
904 size_t deepestIndex = 0;
905 std::optional<size_t> deepest = std::nullopt;
906 SmallVector<std::pair<size_t, Placement>> deepestLayout = {};
907
908 // Subproblems already searched in full without a layout, keyed by the next
909 // buffer's index and the free runs left. The candidates a buffer gets depend
910 // on nothing else -- the cursor only orders them -- so one of these can never
911 // succeed. Same-sized buffers reach the same free runs in every order they
912 // are placed in; without this the search retries each order.
913 std::set<SmallVector<int64_t>> failedStates = {};
914
915 bool run(size_t index, int startBankIndex, int64_t remaining) {
916 if (index == order.size()) {
917 return true;
918 }
919 SmallVector<int64_t> state = {static_cast<int64_t>(index)};
920 for (MemoryRun gap : occupancy.gapsIn(0, occupancy.size())) {
921 state.append({gap.start, gap.size});
922 }
923 if (failedStates.count(state)) {
924 return false;
925 }
926 size_t buffer = order[index];
927 int64_t size = ctx.buffers[buffer].size;
928 int64_t rest = remaining - size; // Placement's criterion 2 cap.
929
930 SmallVector<Placement> candidates = rankedPlacements(
931 buffer, ctx, startBankIndex, requiredBanks, occupancy, rest);
932 if (candidates.empty() && (!deepest || index > deepestIndex)) {
933 recordDeepest(index, buffer);
934 }
935 for (const Placement &candidate : candidates) {
936 if (budget <= 0) {
937 // Out of budget before this buffer had an address: it is where the
938 // search stopped, so it is the one to report.
939 if (!deepest || index > deepestIndex) {
940 recordDeepest(index, buffer);
941 }
942 exhausted = true;
943 break;
944 }
945 --budget;
946 placeBuffer(buffer, candidate.addr, candidate.bank, ctx, occupancy,
947 layout);
948 placed.push_back(buffer);
949 // A pinned buffer leaves the cursor alone; see rankedPlacements.
950 int nextBank = requiredBanks.count(buffer)
951 ? startBankIndex
952 : (candidate.bank + 1) % ctx.numBanks;
953 if (run(index + 1, nextBank, rest)) {
954 return true;
955 }
956 placed.pop_back();
957 ++stats.backtracks;
958 occupancy.markFree(candidate.addr, candidate.addr + size);
959 layout.at[buffer] = std::nullopt;
960 }
961 if (!exhausted) {
962 failedStates.insert(std::move(state));
963 }
964 return false;
965 }
966
967 // Re-apply the best partial layout so the caller's memory map describes the
968 // closest the search came, not the tile it unwound to.
969 void restoreDeepest() {
970 for (auto &[buffer, at] : deepestLayout) {
971 placeBuffer(buffer, at.addr, at.bank, ctx, occupancy, layout);
972 placed.push_back(buffer);
973 }
974 }
975
976private:
977 void recordDeepest(size_t index, size_t buffer) {
978 deepestIndex = index;
979 deepest = buffer;
980 deepestLayout.clear();
981 for (size_t done : placed) {
982 const auto &at = layout.at[done];
983 assert(at && "placed buffer must have an address and bank");
984 auto [address, bank] = *at;
985 deepestLayout.push_back({done, Placement{address, bank, 0, 0, 0, 0}});
986 }
987 }
988};
989} // namespace
990
991// Exhaustive placement, for when the ranked search fails. The ranked search
992// only tries positions flush against what is already placed, so a buffer that
993// must sit against one placed after it is out of its reach in any order.
994//
995// Any layout can be slid down, one buffer at a time in address order, until
996// each buffer sits at the lowest address its alignment and banks allow above
997// the one before it. Walking the free runs upward and choosing which buffer
998// comes next therefore reaches every layout that exists, and a tile this
999// rejects within budget has none. What can follow an address depends only on
1000// the address and the buffers left, so a failed pair is never tried twice,
1001// which collapses the orders of one set of buffers into a single visit.
1002namespace {
1003struct CompactionSearch {
1004 ArrayRef<size_t> order;
1005 const BankAwareContext &ctx;
1006 SmallVector<MemoryRun> gaps;
1007 // Per buffer in `order`: size, alignment, the ranges it may lie in, and a
1008 // class shared with every buffer it could swap with.
1009 SmallVector<int64_t> sizes, aligns;
1010 SmallVector<SmallVector<MemoryRun, 2>> ranges;
1011 SmallVector<unsigned> classes;
1012 SmallVector<int64_t> addrs;
1013 // Free bytes and the largest run from each gap to the top of the tile.
1014 SmallVector<int64_t> freeAbove, runAbove;
1015 llvm::DenseSet<std::pair<int64_t, llvm::BitVector>> failed;
1016 int64_t budget;
1017 bool exhausted = false;
1018
1019 CompactionSearch(ArrayRef<size_t> order, const BankAwareContext &ctx,
1020 const RequiredBanks &requiredBanks,
1021 const MemoryOccupancy &occupancy, int64_t budget)
1022 : order(order), ctx(ctx),
1023 gaps(occupancy.gapsIn(0, ctx.maxDataMemorySize)),
1024 addrs(order.size(), -1), budget(budget) {
1025 for (size_t i = 0; i < order.size(); ++i) {
1026 size_t buffer = order[i];
1027 sizes.push_back(ctx.buffers[buffer].size);
1028 aligns.push_back(ctx.buffers[buffer].alignBytes);
1029 SmallVector<MemoryRun, 2> allowed;
1030 auto required = requiredBanks.find(buffer);
1031 if (required == requiredBanks.end()) {
1032 allowed.push_back({0, ctx.maxDataMemorySize});
1033 } else {
1034 auto &banks = required->second;
1035 for (int bank : banks)
1036 allowed.push_back(ctx.bankLimits[bank]);
1037 if (banks.size() == 2 && banks.back() == banks.front() + 1)
1038 allowed = {{ctx.bankLimits[banks.front()].start,
1039 ctx.bankLimits[banks.front()].size +
1040 ctx.bankLimits[banks.back()].size}};
1041 }
1042 // An initialized buffer must dodge the guarded bytes at the foot of
1043 // the tile, the same restriction rankedPlacements enforces (see the
1044 // npu2 column-0 memtile comment in allocateTile). Clamping the ranges
1045 // here, before the equivalence classes below are computed, keeps a
1046 // guarded buffer out of any class an unguarded one of the same size
1047 // could also join.
1048 if (ctx.initGuardBytes > 0 && ctx.buffers[buffer].initialized) {
1049 SmallVector<MemoryRun, 2> clamped;
1050 for (MemoryRun range : allowed) {
1051 int64_t start = std::max(range.start, ctx.initGuardBytes);
1052 if (start < range.end())
1053 clamped.push_back({start, range.end() - start});
1054 }
1055 allowed = std::move(clamped);
1056 }
1057 ranges.push_back(allowed);
1058 unsigned cls = i;
1059 for (size_t j = 0; j < i; ++j) {
1060 if (sizes[j] == sizes[i] && aligns[j] == aligns[i] &&
1061 llvm::equal(ranges[j], ranges[i], [](MemoryRun a, MemoryRun b) {
1062 return a.start == b.start && a.size == b.size;
1063 })) {
1064 cls = classes[j];
1065 break;
1066 }
1067 }
1068 classes.push_back(cls);
1069 }
1070 freeAbove.assign(gaps.size() + 1, 0);
1071 runAbove.assign(gaps.size() + 1, 0);
1072 for (size_t g = gaps.size(); g-- > 0;) {
1073 freeAbove[g] = freeAbove[g + 1] + gaps[g].size;
1074 runAbove[g] = std::max(runAbove[g + 1], gaps[g].size);
1075 }
1076 }
1077
1078 // Lowest address at or above `from` in gap `g` where buffer `i` fits.
1079 std::optional<int64_t> lowest(size_t i, size_t g, int64_t from) const {
1080 std::optional<int64_t> best;
1081 for (MemoryRun range : ranges[i]) {
1082 int64_t at = llvm::alignTo(std::max(from, range.start), aligns[i]);
1083 if (at + sizes[i] <= std::min(gaps[g].end(), range.end()) &&
1084 getBankContaining(at, ctx.numBanks, ctx.bankLimits) >= 0 &&
1085 (!best || at < *best))
1086 best = at;
1087 }
1088 return best;
1089 }
1090
1091 bool run() {
1092 llvm::BitVector left(order.size());
1093 int64_t bytes = 0;
1094 for (size_t i = 0; i < order.size(); ++i) {
1095 if (sizes[i] == 0) {
1096 // Covers no byte, so it goes in the first gap its banks reach.
1097 for (size_t g = 0; g < gaps.size() && addrs[i] < 0; ++g)
1098 if (auto at = lowest(i, g, gaps[g].start))
1099 addrs[i] = *at;
1100 if (addrs[i] < 0)
1101 addrs[i] = ranges[i].front().start;
1102 continue;
1103 }
1104 left.set(i);
1105 bytes += sizes[i];
1106 }
1107 return gaps.empty() ? left.none()
1108 : place(0, gaps.front().start, left, bytes);
1109 }
1110
1111private:
1112 bool place(size_t g, int64_t from, llvm::BitVector &left, int64_t bytes) {
1113 if (left.none())
1114 return true;
1115 int64_t largest = 0;
1116 for (int i : left.set_bits())
1117 largest = std::max(largest, sizes[i]);
1118 int64_t here = gaps[g].end() - from;
1119 if (bytes > here + freeAbove[g + 1] ||
1120 largest > std::max(here, runAbove[g + 1]) ||
1121 failed.contains({from, left}))
1122 return false;
1123 SmallVector<unsigned> tried;
1124 for (int i : left.set_bits()) {
1125 if (llvm::is_contained(tried, classes[i]))
1126 continue;
1127 tried.push_back(classes[i]);
1128 std::optional<int64_t> at = lowest(i, g, from);
1129 if (!at)
1130 continue;
1131 if (budget-- <= 0) {
1132 exhausted = true;
1133 return false;
1134 }
1135 addrs[i] = *at;
1136 left.reset(i);
1137 bool done = place(g, *at + sizes[i], left, bytes - sizes[i]);
1138 left.set(i);
1139 if (done)
1140 return true;
1141 if (exhausted)
1142 return false;
1143 }
1144 if (g + 1 < gaps.size() && place(g + 1, gaps[g + 1].start, left, bytes))
1145 return true;
1146 if (!exhausted)
1147 failed.insert({from, left});
1148 return false;
1149 }
1150};
1151} // namespace
1152
1153// Places every buffer in `buffersToAlloc`. Returns the buffer that could not be
1154// placed, or nothing when they all were; `placed` collects what was assigned.
1155static std::optional<size_t>
1156placeFreeBuffers(ArrayRef<size_t> buffersToAlloc, const BankAwareContext &ctx,
1157 const RequiredBanks &requiredBanks, MemoryOccupancy &occupancy,
1158 SmallVectorImpl<size_t> &placed, int64_t budget,
1159 bool &exhausted, TileLayoutStats &stats, TileLayout &layout) {
1160 int64_t remaining = 0;
1161 for (size_t buffer : buffersToAlloc) {
1162 remaining += ctx.buffers[buffer].size;
1163 }
1164 PlacementSearch search{buffersToAlloc, ctx, requiredBanks, occupancy,
1165 placed, stats, layout, budget};
1166 int64_t before = stats.backtracks;
1167 bool solved = search.run(/*index=*/0, /*startBankIndex=*/0, remaining);
1168 if (stats.backtracks > before) {
1169 ++stats.tilesSearched;
1170 }
1171 if (solved) {
1172 return std::nullopt;
1173 }
1174 // The ranked search unwinds everything it tried, so the tile is back to its
1175 // pinned buffers alone.
1176 CompactionSearch complete(buffersToAlloc, ctx, requiredBanks, occupancy,
1177 budget);
1178 if (complete.run()) {
1179 ++stats.tilesCompacted;
1180 for (auto [buffer, addr] : llvm::zip(buffersToAlloc, complete.addrs)) {
1181 placeBuffer(buffer, addr,
1182 getBankContaining(addr, ctx.numBanks, ctx.bankLimits), ctx,
1183 occupancy, layout);
1184 placed.push_back(buffer);
1185 }
1186 return std::nullopt;
1187 }
1188 search.restoreDeepest();
1189 exhausted = complete.exhausted;
1190 if (complete.exhausted) {
1191 ++stats.budgetExhausted;
1192 }
1193 return search.deepest;
1194}
1195
1196// Places every buffer carrying an explicit `address`, address pins first, so a
1197// mem_bank-only buffer cannot carve up space an address pin needs. A
1198// mem_bank-only buffer enters `requiredBanks` and queues into
1199// `buffersToAlloc`. Failure is terminal.
1200static LogicalResult placePreAllocatedBuffers(
1201 SmallVectorImpl<size_t> &preAllocatedBuffers, const BankAwareContext &ctx,
1202 MemoryOccupancy &occupancy, RequiredBanks &requiredBanks,
1203 SmallVectorImpl<size_t> &buffersToAlloc, TileLayout &layout) {
1204 // Address buffers first (ascending), then mem_bank-only buffers. The sort is
1205 // stable, so the mem_bank-only tail, whose elements all compare equal, keeps
1206 // program order and places identically from one run to the next.
1207 llvm::stable_sort(preAllocatedBuffers, [&](size_t a, size_t b) -> bool {
1208 auto a_addr = ctx.buffers[a].address;
1209 auto b_addr = ctx.buffers[b].address;
1210 if (a_addr.has_value() && b_addr.has_value()) {
1211 return a_addr.value() < b_addr.value();
1212 }
1213 return a_addr.has_value() && !b_addr.has_value();
1214 });
1215
1216 for (size_t buffer : preAllocatedBuffers) {
1217 auto has_addr =
1218 checkAndAddBufferWithAddress(buffer, ctx, occupancy, layout);
1219 if (failed(has_addr)) {
1220 return failure();
1221 }
1222 // NOLINTNEXTLINE(bugprone-unchecked-optional-access)
1223 if (*has_addr) {
1224 continue;
1225 }
1226 // Only a mem_bank: this pass still chooses the address, so queue the
1227 // buffer with the rest.
1228 if (failed(recordRequiredBank(buffer, ctx, requiredBanks, layout))) {
1229 return failure();
1230 }
1231 buffersToAlloc.push_back(buffer);
1232 }
1233 return success();
1234}
1235
1236// Order buffers for placement: fewest allowed banks first, then largest first,
1237// so a small buffer does not split the run a large one needs.
1238static SmallVector<size_t> placementOrder(ArrayRef<size_t> buffersToAlloc,
1239 const RequiredBanks &requiredBanks,
1240 const BankAwareContext &ctx) {
1241 SmallVector<size_t> order(buffersToAlloc.begin(), buffersToAlloc.end());
1242 llvm::stable_sort(order, [&](size_t a, size_t b) {
1243 if (requiredBanks.count(a) != requiredBanks.count(b)) {
1244 return requiredBanks.count(a) > requiredBanks.count(b);
1245 }
1246 if (requiredBanks.count(a) &&
1247 requiredBanks.lookup(a).size() != requiredBanks.lookup(b).size())
1248 return requiredBanks.lookup(a).size() < requiredBanks.lookup(b).size();
1249 return ctx.buffers[a].size > ctx.buffers[b].size;
1250 });
1251 return order;
1252}
1253
1255 const TileMemoryLimits &limits) {
1256 return {buffer.getAllocationSize(),
1257 bufferAlignBytes(buffer, limits.tileAlignBitWidth,
1258 limits.maxVecAlignBits),
1259 buffer.getSectionAlignment(),
1260 buffer.getAligned(),
1261 buffer.getAddress(),
1262 buffer.getMemBank(),
1263 banksFromMemorySpace(buffer.getType()),
1264 buffer.getInitialValue().has_value()};
1265}
1266
1267// The buffer materializeCoreSections makes for `held`, as tileLayoutBuffer
1268// above reads it back.
1271 const TileMemoryLimits &limits) {
1272 using Kind = CoreSectionReservation::Kind;
1273 if (held.kind == Kind::Prebaked)
1274 return {held.bytes, 1, 1, /*aligned=*/false, held.at,
1275 std::nullopt, {}, false};
1276 int64_t vectorAlign =
1278 held.bytes) /
1279 8;
1280 std::optional<int32_t> bank;
1281 if (held.kind == Kind::Bank)
1282 bank = held.at;
1283 return {held.bytes,
1284 std::max(vectorAlign, held.alignBytes),
1285 held.alignBytes,
1286 /*aligned=*/true,
1287 std::nullopt,
1288 bank,
1289 {},
1290 false};
1291}
1292
1294 TileLayoutStats &stats) {
1295 TileLayout layout;
1296 layout.at.resize(problem.buffers.size());
1297
1298 std::vector<MemoryRun> bankLimits;
1299 int64_t bankSize = problem.maxDataMemorySize / problem.numBanks;
1300 fillBankLimits(problem.numBanks, bankSize, bankLimits);
1301
1302 // A stack_bank-only core has no address yet. Its bank is a hard constraint,
1303 // so reserve inside that bank before anything unconstrained is placed, and
1304 // record the address the way a mem_bank-only buffer gets one.
1305 MemoryRun stackRun = problem.stackRun;
1306 MemoryOccupancy occupancy(problem.maxDataMemorySize);
1307 if (problem.hasCore) {
1308 if (std::optional<int> bank = problem.stackBank) {
1309 // Address-pinned buffers cannot move, whereas a bank-only stack can.
1310 // Account for those pins before choosing the stack's address. The normal
1311 // buffer placement below still validates each pin and records occupancy.
1312 MemoryOccupancy stackOccupancy(problem.maxDataMemorySize);
1313 for (const TileLayoutBuffer &buffer : problem.buffers) {
1314 if (!buffer.address)
1315 continue;
1316 int64_t start = *buffer.address;
1317 int64_t end = start + buffer.size;
1318 if (start >= 0 && end <= problem.maxDataMemorySize)
1319 stackOccupancy.markOccupied(start, end);
1320 }
1321 std::optional<int64_t> at = stackOccupancy.findLeastFragmentingGap(
1322 bankLimits[*bank].start, bankLimits[*bank].end(), stackRun.size,
1323 problem.stackAlignBytes);
1324 if (!at) {
1326 layout.message =
1327 ("requires a " + llvm::Twine(stackRun.size) +
1328 "-byte stack in bank " + llvm::Twine(*bank) +
1329 ", but no contiguous aligned space remains after address-pinned "
1330 "buffers")
1331 .str();
1332 return layout;
1333 }
1334 stackRun.start = *at;
1335 layout.stackStart = at;
1336 }
1337 occupancy.markOccupied(stackRun.start,
1338 std::min(stackRun.end(), problem.maxDataMemorySize));
1339 }
1340 BankAwareContext ctx{problem.numBanks, problem.tileAlignBitWidth,
1341 bankLimits, problem.maxDataMemorySize,
1342 stackRun, problem.hasCore,
1343 problem.buffers};
1344
1345 RequiredBanks requiredBanks;
1346 SmallVector<size_t> preAllocatedBuffers;
1347 SmallVector<size_t> buffersToAlloc;
1348 for (auto [i, buffer] : llvm::enumerate(problem.buffers)) {
1349 if (!buffer.address && !buffer.memBank && buffer.spaceBanks.empty()) {
1350 buffersToAlloc.push_back(i);
1351 } else {
1352 preAllocatedBuffers.push_back(i);
1353 }
1354 }
1355
1356 if (failed(placePreAllocatedBuffers(preAllocatedBuffers, ctx, occupancy,
1357 requiredBanks, buffersToAlloc, layout))) {
1358 return layout;
1359 }
1360 layout.preAllocated = preAllocatedBuffers;
1361 ctx.initGuardBytes = problem.initGuardBytes;
1362
1363 // Bank-pinned buffers lead the order, then the core's data region, then the
1364 // unconstrained ones -- most-constrained first, since a pin has one candidate
1365 // bank. They are searched together rather than in separate passes: where a
1366 // pin's position inside its bank decides whether a later buffer fits, only a
1367 // single search can revisit it.
1368 SmallVector<size_t> order =
1369 placementOrder(buffersToAlloc, requiredBanks, ctx);
1370 std::optional<size_t> failedBuffer =
1371 placeFreeBuffers(order, ctx, requiredBanks, occupancy, layout.allocated,
1372 problem.budget, layout.exhausted, stats, layout);
1373 if (!failedBuffer) {
1374 assert(layout.allocated.size() == buffersToAlloc.size());
1375 return layout;
1376 }
1378 layout.failed = *failedBuffer;
1379 if (auto required = requiredBanks.find(*failedBuffer);
1380 required != requiredBanks.end()) {
1381 layout.failedBanks = required->second;
1382 int bank = required->second.front();
1383 layout.freeInFailedBank =
1384 occupancy.freeBytes(bankLimits[bank].start, bankLimits[bank].end());
1385 }
1386 for (size_t buffer : buffersToAlloc)
1387 if (!layout.at[buffer])
1388 layout.unplacedBytes += problem.buffers[buffer].size;
1389 return layout;
1390}
1391
1392static LogicalResult allocateTile(TileOp tile, int64_t budget,
1393 TileLayoutStats &stats) {
1394 auto device = tile->getParentOfType<AIE::DeviceOp>();
1395 if (!device) {
1396 return failure();
1397 }
1398
1399 const auto &targetModel = getTargetModel(tile);
1400 TileMemoryLimits limits = tileMemoryLimits(targetModel, tile.getTileType());
1401 TileLayoutProblem problem;
1402 problem.maxDataMemorySize = limits.maxDataMemorySize;
1403 problem.tileAlignBitWidth = limits.tileAlignBitWidth;
1404 problem.maxVecAlignBits = limits.maxVecAlignBits;
1405 problem.numBanks = targetModel.getNumBanks(tile.getCol(), tile.getRow());
1406 problem.budget = budget;
1407 CoreOp coreOp = tile.getCoreOp();
1408 problem.hasCore = static_cast<bool>(coreOp);
1409 if (coreOp) {
1410 problem.stackRun = coreOp.getStackRun();
1411 std::optional<uint32_t> stackBank = coreOp.getStackBank();
1412 if (!coreOp.getStackAddress() && stackBank) {
1413 problem.stackBank = static_cast<int>(*stackBank);
1414 problem.stackAlignBytes = targetModel.getCoreStackAlignment();
1415 }
1416 }
1417 // On npu2, the first word of the column-0 memtile reads back as 0x00CD0CD0
1418 // on every dispatch after the first, though nothing in the design writes it.
1419 // A buffer that DMA refills each dispatch is unaffected, but an initialized
1420 // one is loaded only once and keeps the bad word, so keep initialized buffers
1421 // off that word. Other buffers may still take it, and a buffer the user
1422 // pinned there keeps its address.
1423 //
1424 // TODO: Investigate. This is a low-confidence workaround for a cause nobody
1425 // has found: the word may be reserved by the firmware or driver, or clobbered
1426 // by something else. The value predates initialized buffers dropping their
1427 // locks (#3608 saw it first), so that change is not the cause.
1428 if (tile.isMemTile() && tile.getCol() == 0 &&
1429 targetModel.hasProperty(AIETargetModel::IsNPU) &&
1430 targetModel.getTargetArch() == AIEArch::AIE2p) {
1431 problem.initGuardBytes = problem.tileAlignBitWidth / 8;
1432 }
1433
1434 SmallVector<BufferOp> buffers;
1435 device.walk<WalkOrder::PreOrder>([&](BufferOp buffer) {
1436 if (buffer.getTileOp() != tile)
1437 return;
1438 buffers.push_back(buffer);
1439 problem.buffers.push_back(tileLayoutBuffer(buffer, limits));
1440 });
1441
1442 TileLayout layout = layoutTile(problem, stats);
1443 if (layout.status == TileLayout::Status::StackNoRoom) {
1444 coreOp.emitOpError(layout.message);
1445 return failure();
1446 }
1447 if (layout.stackStart) {
1448 coreOp.setStackAddress(*layout.stackStart);
1449 }
1450 if (layout.status == TileLayout::Status::BadPin) {
1451 buffers[layout.failed].emitOpError(layout.message);
1452 return failure();
1453 }
1454 MemoryRun stackRun = problem.stackRun;
1455 if (layout.stackStart)
1456 stackRun.start = *layout.stackStart;
1457
1458 if (layout.status == TileLayout::Status::NoRoom) {
1459 BufferOp failed = buffers[layout.failed];
1460 std::vector<MemoryRun> bankLimits;
1461 fillBankLimits(problem.numBanks,
1462 problem.maxDataMemorySize / problem.numBanks, bankLimits);
1463 // A buffer pinned to a bank that cannot hold it is a user constraint, not
1464 // an out-of-room tile: give it its own error and no memory map. Unless the
1465 // search merely ran out of budget, in which case the bank may have room.
1466 if (!layout.exhausted && !layout.failedBanks.empty()) {
1467 auto banks = layout.failedBanks;
1468 if (banks.size() > 1) {
1469 failed.emitOpError("")
1470 << bufferLabel(failed) << " requires " << failed.getAllocationSize()
1471 << " bytes, but no contiguous aligned space remains within allowed "
1472 "banks "
1473 << banks.front() << " and " << banks.back();
1474 return failure();
1475 }
1476 int bank = banks.front();
1477 int64_t need = failed.getAllocationSize();
1478 int64_t bankCapacity = bankLimits[bank].size;
1479 if (need > bankCapacity) {
1480 failed->emitOpError("") << bufferLabel(failed) << " requires " << need
1481 << " bytes, which cannot fit in bank " << bank
1482 << " (" << bankCapacity << " bytes total)";
1483 } else {
1484 failed->emitOpError("")
1485 << bufferLabel(failed) << " requires " << need << " bytes in bank "
1486 << bank << ", but only " << layout.freeInFailedBank << " of "
1487 << bankCapacity << " bytes are free there";
1488 }
1489 return failure();
1490 }
1491 InFlightDiagnostic diag = failed.emitOpError(kNoTileRoom)
1492 << bufferLabel(failed) << " needs "
1493 << failed.getAllocationSize()
1494 << " bytes and this tile has no room left for it";
1495 if (CoreOp core = tile.getCoreOp())
1496 if (int64_t data = core.getDataSize().value_or(
1497 static_cast<int64_t>(core.getMeasuredDataSize().value_or(0)))) {
1498 auto device = core->getParentOfType<DeviceOp>();
1499 diag.attachNote(core.getLoc())
1500 << kCoreSectionsNote << data << " bytes (device "
1501 << FlatSymbolRefAttr::get(device.getSymNameAttr()) << ")";
1502 }
1503 if (layout.exhausted) {
1504 diag.attachNote() << "the search hit its " << budget
1505 << "-placement budget with arrangements still untried, "
1506 "so a layout may exist that it did not reach (raise "
1507 "it with placement-budget)";
1508 }
1509 printMemMap(tile, buffers, layout.at, layout.preAllocated, layout.allocated,
1510 problem.numBanks, bankLimits, stackRun);
1511 return failure();
1512 }
1513
1514 for (auto [buffer, at] : llvm::zip_equal(buffers, layout.at)) {
1515 if (at) {
1516 buffer.setAddress(at->first);
1517 buffer.setMemBank(at->second);
1518 }
1519 }
1520 sortBuffersByAddress(buffers);
1521 // Every placement came from free space in the tile, so overflow cannot happen
1522 // here. The stack and overlap checks remain as a backstop.
1523 if (!checkAndPrintOverlapStackframe(stackRun, buffers) ||
1524 !checkAndPrintBufferOverlap(buffers, problem.tileAlignBitWidth,
1525 problem.maxVecAlignBits)) {
1526 return failure();
1527 }
1528 return success();
1529}
1530
1531static LogicalResult checkBufferScope(BufferOp buffer, DeviceOp device) {
1532 // collectBuffers walks the device's own operations, so the linker script and
1533 // the BCF describe a buffer only at that depth. A buffer nested anywhere else
1534 // reaches the core as an undefined symbol. MemTileDMA is the exception: a
1535 // memtile links no core, so nothing refers to the buffer by name.
1536 Operation *parent = buffer->getParentOp();
1537 if (!isa<DeviceOp>(parent) && !isa<MemTileDMAOp>(parent)) {
1538 auto tile = buffer.getTileOp();
1539 tile->emitOpError("Buffer '")
1540 << buffer.name()
1541 << "' must be defined directly under the device scope. Currently it "
1542 "is nested inside a core tile.";
1543 return failure();
1544 }
1545 return success();
1546}
1547
1548namespace {
1549struct AIEAssignBufferAddressesPass
1550 : xilinx::AIE::impl::AIEAssignBufferAddressesBase<
1551 AIEAssignBufferAddressesPass> {
1552
1553 AIEAssignBufferAddressesPass() = default;
1554
1555 AIEAssignBufferAddressesPass(const AIEAssignBufferAddressesOptions &options)
1556 : AIEAssignBufferAddressesBase(options) {}
1557
1558 void getDependentDialects(DialectRegistry &registry) const override {
1559 registry.insert<func::FuncDialect>();
1560 registry.insert<AIEDialect>();
1561 }
1562
1563 void runOnOperation() override {
1564 DeviceOp device = getOperation();
1565 int64_t budget = clPlacementBudget;
1566 if (budget <= 0) {
1567 device.emitError("placement-budget must be positive, got ") << budget;
1568 return signalPassFailure();
1569 }
1570 applySignatureBankConstraints(device);
1571 if (failed(materializeCoreSections(device))) {
1572 return signalPassFailure();
1573 }
1574
1575 // One allocator, one answer. There used to be two schemes and a fallback
1576 // between them, which meant a tile that ran out of room reported twice and
1577 // explained itself once, and a `mem_bank` pin could be dropped on the way
1578 // from one scheme to the other. Placement now either finds a layout or says
1579 // why it could not.
1580 TileLayoutStats stats;
1581 bool ok = llvm::all_of(device.getOps<TileOp>(), [&](TileOp tile) {
1582 return succeeded(allocateTile(tile, budget, stats));
1583 });
1584 // Recorded on failure too, where budget-exhausted is the one that matters.
1585 numTilesSearched += stats.tilesSearched;
1586 numBacktracks += stats.backtracks;
1587 numBudgetExhausted += stats.budgetExhausted;
1588 numTilesCompacted += stats.tilesCompacted;
1589 if (!ok)
1590 signalPassFailure();
1591 }
1592};
1593} // namespace
1594
1595namespace {
1596struct AIEPrepareBuffersPass
1597 : xilinx::AIE::impl::AIEPrepareBuffersBase<AIEPrepareBuffersPass> {
1598 void getDependentDialects(DialectRegistry &registry) const override {
1599 registry.insert<func::FuncDialect>();
1600 registry.insert<AIEDialect>();
1601 }
1602
1603 void runOnOperation() override {
1604 DeviceOp device = getOperation();
1605 // A buffer's name becomes a symbol in its core's object, so every buffer
1606 // needs a name before the cores are lowered. Naming runs first, because a
1607 // diagnostic below names the buffer it rejects.
1608 OpBuilder builder = OpBuilder::atBlockTerminator(device.getBody());
1609 unsigned counter = 0;
1610 NamedOpTable names(device);
1611 device.walk<WalkOrder::PreOrder>([&](BufferOp buffer) {
1612 if (!buffer.hasName()) {
1613 buffer->setAttr(
1614 SymbolTable::getSymbolAttrName(),
1615 builder.getStringAttr(names.uniqueName("_anonymous", counter)));
1616 }
1617 });
1618 device.walk<WalkOrder::PreOrder>([&](BufferOp buffer) {
1619 if (failed(checkBufferScope(buffer, device))) {
1620 return signalPassFailure();
1621 }
1622 });
1623 }
1624};
1625} // namespace
1626
1627std::unique_ptr<OperationPass<DeviceOp>> AIE::createAIEPrepareBuffersPass() {
1628 return std::make_unique<AIEPrepareBuffersPass>();
1629}
1630
1631std::unique_ptr<OperationPass<DeviceOp>>
1633 return std::make_unique<AIEAssignBufferAddressesPass>();
1634}
1635
1636std::unique_ptr<OperationPass<DeviceOp>>
1638 const AIEAssignBufferAddressesOptions &options) {
1639 return std::make_unique<AIEAssignBufferAddressesPass>(options);
1640}
DenseMap< size_t, SmallVector< int, 2 > > RequiredBanks
TileLayout layoutTile(const TileLayoutProblem &problem, TileLayoutStats &stats)
Lays out problem as assign-buffer-addresses does, without touching IR.
constexpr llvm::StringLiteral kNoTileRoom
How --aie-assign-buffer-addresses says a buffer fits no tile memory left, and the note it adds,...
Definition AIEPasses.h:52
TileLayoutBuffer tileLayoutBuffer(BufferOp buffer, const TileMemoryLimits &limits)
What assign-buffer-addresses lays buffer out as, on a tile with limits.
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEPrepareBuffersPass()
llvm::SmallVector< int, 2 > banksFromMemorySpace(mlir::Type type)
const AIETargetModel & getTargetModel(mlir::Operation *op)
std::unique_ptr< mlir::OperationPass< DeviceOp > > createAIEAssignBufferAddressesPass()
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 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)
constexpr llvm::StringLiteral kCoreSectionsNote
Definition AIEPasses.h:53
ArrayRef< TileLayoutBuffer > buffers
ArrayRef< MemoryRun > bankLimits
int64_t end() const
One buffer of a tile, as assign-buffer-addresses lays it out.
std::optional< int64_t > address
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 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.
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.
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...