15#include "mlir/IR/Attributes.h"
17#include "llvm/ADT/BitVector.h"
24#define GEN_PASS_DEF_AIEASSIGNBUFFERADDRESSES
25#define GEN_PASS_DEF_AIEPREPAREBUFFERS
26#include "aie/Dialect/AIE/Transforms/AIEPasses.h.inc"
29#define DEBUG_TYPE "aie-assign-buffers"
36static std::optional<int64_t> getMeasuredStackSize(TileOp tile) {
37 CoreOp core = tile.getCoreOp();
41 if (
auto measured = core.getMeasuredStackSize()) {
42 return static_cast<int64_t
>(*measured);
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();
59static std::string bufferLabel(BufferOp buffer) {
60 if (buffer.getCoreData()) {
61 return "this core's data sections (data_size)";
63 if (buffer.getBankReserved()) {
64 return "this core's static data pinned to bank " +
65 std::to_string(buffer.getMemBank().value_or(0));
68 if (!buffer.hasName()) {
69 return "an unnamed buffer";
71 return (
"buffer \"" + buffer.name().getValue() +
"\"").str();
75static StringRef mapLabel(BufferOp buffer) {
76 if (buffer.getCoreData()) {
77 return StringRef(
"(core data sections)");
79 if (buffer.getBankReserved()) {
80 return StringRef(
"(bank-pinned static data)");
82 if (!buffer.hasName()) {
83 return StringRef(
"(unnamed buffer)");
85 return buffer.name().getValue();
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()) {
100 auto tile = dyn_cast_or_null<TileOp>(core.getTile().getDefiningOp());
102 return core.emitOpError(
103 "reserves memory for its own sections, but its tile is not placed; "
104 "run --aie-place-tiles first");
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)) {
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);
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()))
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";
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(),
141 held.kind == Kind::Prebaked ? builder.getI32IntegerAttr(held.at)
145 held.kind == Kind::Bank ? builder.getI32IntegerAttr(held.at)
147 held.kind == Kind::DataRegion,
148 held.kind != Kind::DataRegion,
150 buffer->setAttr(SymbolTable::getSymbolAttrName(),
151 builder.getStringAttr(name));
165static void applySignatureBankConstraints(DeviceOp device) {
166 device.walk([&](BufferOp buffer) {
168 if (banks.size() == 1 && !buffer.getMemBank())
169 buffer.setMemBankAttr(IntegerAttr::get(
170 IntegerType::get(device.getContext(), 32), banks.front()));
174static bool isBufferPreAllocated(BufferOp buffer) {
175 auto addr = buffer.getAddress();
176 auto memBank = buffer.getMemBank();
177 return (addr != std::nullopt || memBank != std::nullopt);
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;
194 uint32_t reqAlignBits =
195 isBufferPreAllocated(cur)
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
211 if (cur.getAllocationSize() == 0) {
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) {
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)";
234static bool checkAndPrintOverlapStackframe(
MemoryRun stackRun,
235 ArrayRef<BufferOp> buffers) {
236 for (
auto buf : buffers) {
238 if (buf.getAllocationSize() == 0) {
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) <<
")";
258static void printMemoryMapEntry(Diagnostic ¬e, StringRef name,
259 int64_t address, int64_t size,
int indent,
260 StringRef suffix =
"") {
261 for (
int i = 0; i < indent; ++i) {
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";
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});
284class MemoryOccupancy {
286 explicit MemoryOccupancy(int64_t size) : occupied(size, false) {}
288 int64_t size()
const {
return occupied.size(); }
291 bool isRangeFree(int64_t start, int64_t end)
const {
292 if (start < 0 || end > size() || start > end) {
295 return start == end || occupied.find_first_in(start, end) == -1;
298 void markOccupied(int64_t start, int64_t end) {
299 assert(start >= 0 && end <= size() && start <= end &&
300 "range must lie inside the tile");
302 occupied.set(start, end);
309 void markFree(int64_t start, int64_t end) {
310 assert(start >= 0 && end <= size() && start <= end &&
311 "range must lie inside the tile");
313 occupied.reset(start, end);
324 std::optional<int64_t> findLeastFragmentingGap(int64_t lo, int64_t hi,
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());
335 if (run > bestRun || (run == bestRun && best && start < *best)) {
340 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
341 int64_t low = llvm::alignTo(gapStart, alignBytes);
342 if (low + size > gapEnd) {
348 std::max<int64_t>(llvm::alignDown(gapEnd - size, alignBytes), low));
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) {
366 int64_t slack = (gapEnd - gapStart) - size;
367 if (!best || slack < bestSlack) {
377 int64_t freeBytes(int64_t lo, int64_t hi)
const {
379 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
380 total += gapEnd - gapStart;
387 int64_t slackAt(int64_t addr, int64_t size)
const {
389 forEachGap(0, this->size(), [&](int64_t gapStart, int64_t gapEnd) {
390 if (addr >= gapStart && addr + size <= gapEnd) {
391 slack = (gapEnd - gapStart) - size;
398 MemoryRun gapAt(int64_t addr)
const {
400 forEachGap(0, this->size(), [&](int64_t gapStart, int64_t gapEnd) {
401 if (addr >= gapStart && addr < gapEnd) {
402 found = {gapStart, gapEnd - gapStart};
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;
418 }
else if (run > second) {
422 return {first, second};
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});
437 int64_t largestGap(int64_t lo, int64_t hi)
const {
439 forEachGap(lo, hi, [&](int64_t gapStart, int64_t gapEnd) {
440 best = std::max(best, gapEnd - gapStart);
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) {
456 int nextTaken = occupied.find_first_in(gapStart, hi);
458 int64_t gapEnd = nextTaken == -1 ? hi : nextTaken;
459 fn(gapStart, gapEnd);
464 llvm::BitVector occupied;
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)) {
497static void placeBuffer(
size_t i, int64_t startAddr,
int bank,
500 layout.
at[i] = {startAddr, bank};
501 occupancy.markOccupied(startAddr, startAddr + ctx.
buffers[i].size);
505static LogicalResult failPin(
TileLayout &layout,
size_t i,
506 const llvm::Twine &message) {
509 layout.
message = message.str();
517static FailureOr<bool> checkAndAddBufferWithAddress(
size_t i,
519 MemoryOccupancy &occupancy,
526 int64_t addr = *buffer.
address;
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");
538 return failPin(layout, i,
539 "address attribute value must be aligned to " +
541 " bits when the aligned attribute is set");
551 return failPin(layout, i,
552 "address attribute does not fall within any bank range");
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");
563 int lastBank = buffer.
size == 0 ? bank
564 : getBankContaining(endAddr - 1, ctx.
numBanks,
566 for (
int touched = bank; !buffer.
spaceBanks.empty() && touched <= lastBank;
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");
576 return failPin(layout, i,
577 "address attribute lies in bank " + llvm::Twine(bank) +
578 ", but mem_bank requests bank " +
584 if (!occupancy.isRangeFree(addr, endAddr)) {
585 return failPin(layout, i,
"would override allocated address");
588 placeBuffer(i, addr, bank, ctx, occupancy, layout);
598static LogicalResult recordRequiredBank(
size_t i,
const BankAwareContext &ctx,
604 return failPin(layout, i,
"mem_bank attribute value is out of range");
606 SmallVector<int, 2> banks = buffer.
spaceBanks;
609 if (!banks.empty()) {
611 return failPin(layout, i,
612 "memory space requests a bank that does not exist");
614 requiredBanks[i] = std::move(banks);
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 ¬e = 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, 2, suffix);
633 if (stackRun.
size == 0) {
634 note <<
"\t(no stack allocated)\n";
636 if (
auto measured = getMeasuredStackSize(tile)) {
637 note <<
"\t(aiecc measured this core's stack requirement as " << *measured
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";
645 if (stackRun.
size > 0 && bankLimits[bank].contains(stackRun.
start)) {
646 printbuffer(
"(stack)", stackRun.
start, stackRun.
size);
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) {
659 BufferOp buffer = buffers[index];
660 int64_t address = at[index]->first;
661 int64_t size = buffer.getAllocationSize();
665 if (address + size > bankLimits[bank].end()) {
667 (
" (straddles into bank " + llvm::Twine(bank + 1) +
")").str();
669 printbuffer(mapLabel(buffer), address, size, suffix);
672 printPlaced(preAllocated);
673 printPlaced(allocated);
680constexpr int64_t kFallbackRank = std::numeric_limits<int64_t>::max();
695 int64_t banksTouched;
696 int64_t negLargestRunLeft;
700 std::tuple<int64_t, int64_t, int64_t, int64_t, int64_t> rank()
const {
701 return {banksTouched, negLargestRunLeft, rrDistance, slack, addr};
711static SmallVector<Placement>
712rankedPlacements(
size_t buffer,
const BankAwareContext &ctx,
int startBankIndex,
714 const MemoryOccupancy &tileOccupancy, int64_t contiguityCap) {
715 assert(startBankIndex < ctx.
numBanks &&
716 "Unexpected input value for startBankIndex");
719 std::optional<MemoryOccupancy> guarded;
721 guarded = tileOccupancy;
722 guarded->markOccupied(0, std::min(ctx.
initGuardBytes, guarded->size()));
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;
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)
740 if (banks.size() == 2 && banks.back() == banks.front() + 1)
741 ranges.push_back({ctx.
bankLimits[banks.front()].start,
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()) {
751 {low, std::max<int64_t>(
752 llvm::alignDown(gap.end() - size, alignBytes), low)}) {
753 MemoryOccupancy trial = occupancy;
754 trial.markOccupied(addr, addr + size);
756 if (!llvm::is_contained(banks, bank))
758 int lastBank = size == 0
760 : getBankContaining(addr + size - 1, ctx.
numBanks,
762 out.push_back({addr, bank, lastBank - bank + 1,
763 -trial.largestGap(0, trial.size()), 0,
769 if (out.empty() && size == 0) {
770 int bank = banks.front();
771 out.push_back({ctx.
bankLimits[bank].start, bank, 1, 0, 0, 0});
774 int64_t bankedEnd = ctx.
bankLimits.back().end();
775 int64_t bankSize = bankedEnd / ctx.
numBanks;
780 std::pair<int64_t, int64_t> topGaps =
782 int64_t largestRun = topGaps.first, secondRun = topGaps.second;
783 auto consider = [&](std::optional<int64_t> addr) {
792 size == 0 ? 1 : (*addr + size - 1) / bankSize - *addr / bankSize + 1;
797 int64_t elsewhere = gap.
size == largestRun ? secondRun : largestRun;
798 int64_t leftPiece = *addr - gap.
start;
799 int64_t rightPiece = gap.
end() - (*addr + size);
801 std::min(std::max({elsewhere, leftPiece, rightPiece}), contiguityCap);
802 out.push_back({*addr, bank, touched, ctx.
hasCore ? -runLeft : 0,
804 occupancy.slackAt(*addr, size)});
807 for (
int i = 0; i < ctx.
numBanks; i++) {
808 consider(occupancy.findGap(ctx.
bankLimits[i].start,
813 consider(occupancy.findGap(0, bankedEnd, size, alignBytes));
816 if (bankSize % alignBytes == 0) {
817 consider(occupancy.findGap(0, bankedEnd, size, bankSize));
820 if (out.empty() && size == 0) {
821 out.push_back({0, 0, 1, 0, 0, 0});
825 llvm::stable_sort(out, [](
const Placement &a,
const Placement &b) {
826 return a.rank() < b.rank();
835 if (size > 0 && requiredBanks.find(buffer) == requiredBanks.end()) {
837 int64_t low = llvm::alignTo(gap.
start, alignBytes);
838 if (low + size > gap.
end()) {
842 {low, std::max<int64_t>(
843 llvm::alignDown(gap.
end() - size, alignBytes), low)}) {
848 out.push_back({addr, bank, kFallbackRank, 0, 0, 0});
858 llvm::stable_sort(out, [](
const Placement &a,
const Placement &b) {
859 return a.addr < b.addr;
862 llvm::unique(out, [](
const Placement &a,
863 const Placement &b) {
return a.addr == b.addr; }),
865 llvm::stable_sort(out, [](
const Placement &a,
const Placement &b) {
866 return a.rank() < b.rank();
879struct PlacementSearch {
880 ArrayRef<size_t> order;
881 const BankAwareContext &ctx;
883 MemoryOccupancy &occupancy;
884 SmallVectorImpl<size_t> &placed;
885 TileLayoutStats &stats;
896 bool exhausted =
false;
904 size_t deepestIndex = 0;
905 std::optional<size_t> deepest = std::nullopt;
906 SmallVector<std::pair<size_t, Placement>> deepestLayout = {};
913 std::set<SmallVector<int64_t>> failedStates = {};
915 bool run(
size_t index,
int startBankIndex, int64_t remaining) {
916 if (index == order.size()) {
919 SmallVector<int64_t> state = {
static_cast<int64_t
>(index)};
920 for (MemoryRun gap : occupancy.gapsIn(0, occupancy.size())) {
923 if (failedStates.count(state)) {
926 size_t buffer = order[index];
927 int64_t size = ctx.buffers[buffer].size;
928 int64_t rest = remaining - size;
930 SmallVector<Placement> candidates = rankedPlacements(
931 buffer, ctx, startBankIndex, requiredBanks, occupancy, rest);
932 if (candidates.empty() && (!deepest || index > deepestIndex)) {
933 recordDeepest(index, buffer);
935 for (
const Placement &candidate : candidates) {
939 if (!deepest || index > deepestIndex) {
940 recordDeepest(index, buffer);
946 placeBuffer(buffer, candidate.addr, candidate.bank, ctx, occupancy,
948 placed.push_back(buffer);
950 int nextBank = requiredBanks.count(buffer)
952 : (candidate.bank + 1) % ctx.numBanks;
953 if (run(index + 1, nextBank, rest)) {
958 occupancy.markFree(candidate.addr, candidate.addr + size);
959 layout.at[buffer] = std::nullopt;
962 failedStates.insert(std::move(state));
969 void restoreDeepest() {
970 for (
auto &[buffer, at] : deepestLayout) {
971 placeBuffer(buffer, at.addr, at.bank, ctx, occupancy, layout);
972 placed.push_back(buffer);
977 void recordDeepest(
size_t index,
size_t buffer) {
978 deepestIndex = index;
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}});
1003struct CompactionSearch {
1004 ArrayRef<size_t> order;
1005 const BankAwareContext &ctx;
1006 SmallVector<MemoryRun> gaps;
1009 SmallVector<int64_t> sizes, aligns;
1010 SmallVector<SmallVector<MemoryRun, 2>> ranges;
1011 SmallVector<unsigned> classes;
1012 SmallVector<int64_t> addrs;
1014 SmallVector<int64_t> freeAbove, runAbove;
1015 llvm::DenseSet<std::pair<int64_t, llvm::BitVector>> failed;
1017 bool exhausted =
false;
1019 CompactionSearch(ArrayRef<size_t> order,
const BankAwareContext &ctx,
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});
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}};
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});
1055 allowed = std::move(clamped);
1057 ranges.push_back(allowed);
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) {
1068 classes.push_back(cls);
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);
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))
1092 llvm::BitVector left(order.size());
1094 for (
size_t i = 0; i < order.size(); ++i) {
1095 if (sizes[i] == 0) {
1097 for (
size_t g = 0; g < gaps.size() && addrs[i] < 0; ++g)
1098 if (
auto at = lowest(i, g, gaps[g].start))
1101 addrs[i] = ranges[i].front().start;
1107 return gaps.empty() ? left.none()
1108 : place(0, gaps.front().start, left, bytes);
1112 bool place(
size_t g, int64_t from, llvm::BitVector &left, int64_t bytes) {
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}))
1123 SmallVector<unsigned> tried;
1124 for (
int i : left.set_bits()) {
1125 if (llvm::is_contained(tried, classes[i]))
1127 tried.push_back(classes[i]);
1128 std::optional<int64_t> at = lowest(i, g, from);
1131 if (budget-- <= 0) {
1137 bool done = place(g, *at + sizes[i], left, bytes - sizes[i]);
1144 if (g + 1 < gaps.size() && place(g + 1, gaps[g + 1].start, left, bytes))
1147 failed.insert({from, left});
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,
1160 int64_t remaining = 0;
1161 for (
size_t buffer : buffersToAlloc) {
1162 remaining += ctx.
buffers[buffer].size;
1164 PlacementSearch search{buffersToAlloc, ctx, requiredBanks, occupancy,
1165 placed, stats, layout, budget};
1167 bool solved = search.run(0, 0, remaining);
1172 return std::nullopt;
1176 CompactionSearch complete(buffersToAlloc, ctx, requiredBanks, occupancy,
1178 if (complete.run()) {
1180 for (
auto [buffer, addr] : llvm::zip(buffersToAlloc, complete.addrs)) {
1181 placeBuffer(buffer, addr,
1184 placed.push_back(buffer);
1186 return std::nullopt;
1188 search.restoreDeepest();
1189 exhausted = complete.exhausted;
1190 if (complete.exhausted) {
1193 return search.deepest;
1200static LogicalResult placePreAllocatedBuffers(
1203 SmallVectorImpl<size_t> &buffersToAlloc,
TileLayout &layout) {
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();
1213 return a_addr.has_value() && !b_addr.has_value();
1216 for (
size_t buffer : preAllocatedBuffers) {
1218 checkAndAddBufferWithAddress(buffer, ctx, occupancy, layout);
1219 if (failed(has_addr)) {
1228 if (failed(recordRequiredBank(buffer, ctx, requiredBanks, layout))) {
1231 buffersToAlloc.push_back(buffer);
1238static SmallVector<size_t> placementOrder(ArrayRef<size_t> buffersToAlloc,
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);
1246 if (requiredBanks.count(a) &&
1247 requiredBanks.lookup(a).size() != requiredBanks.lookup(b).size())
1248 return requiredBanks.lookup(a).size() < requiredBanks.lookup(b).size();
1256 return {buffer.getAllocationSize(),
1259 buffer.getSectionAlignment(),
1260 buffer.getAligned(),
1261 buffer.getAddress(),
1262 buffer.getMemBank(),
1264 buffer.getInitialValue().has_value()};
1273 if (held.
kind == Kind::Prebaked)
1274 return {held.
bytes, 1, 1,
false, held.
at,
1275 std::nullopt, {},
false};
1276 int64_t vectorAlign =
1280 std::optional<int32_t> bank;
1281 if (held.
kind == Kind::Bank)
1296 layout.
at.resize(problem.
buffers.size());
1298 std::vector<MemoryRun> bankLimits;
1300 fillBankLimits(problem.
numBanks, bankSize, bankLimits);
1308 if (std::optional<int> bank = problem.
stackBank) {
1316 int64_t start = *buffer.
address;
1317 int64_t end = start + buffer.
size;
1319 stackOccupancy.markOccupied(start, end);
1321 std::optional<int64_t> at = stackOccupancy.findLeastFragmentingGap(
1322 bankLimits[*bank].start, bankLimits[*bank].end(), stackRun.
size,
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 "
1334 stackRun.
start = *at;
1337 occupancy.markOccupied(stackRun.
start,
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);
1352 preAllocatedBuffers.push_back(i);
1356 if (failed(placePreAllocatedBuffers(preAllocatedBuffers, ctx, occupancy,
1357 requiredBanks, buffersToAlloc, layout))) {
1368 SmallVector<size_t> order =
1369 placementOrder(buffersToAlloc, requiredBanks, ctx);
1370 std::optional<size_t> failedBuffer =
1371 placeFreeBuffers(order, ctx, requiredBanks, occupancy, layout.
allocated,
1373 if (!failedBuffer) {
1374 assert(layout.
allocated.size() == buffersToAlloc.size());
1378 layout.
failed = *failedBuffer;
1379 if (
auto required = requiredBanks.find(*failedBuffer);
1380 required != requiredBanks.end()) {
1382 int bank = required->second.front();
1384 occupancy.freeBytes(bankLimits[bank].start, bankLimits[bank].end());
1386 for (
size_t buffer : buffersToAlloc)
1387 if (!layout.
at[buffer])
1392static LogicalResult allocateTile(TileOp tile, int64_t budget,
1394 auto device = tile->getParentOfType<AIE::DeviceOp>();
1405 problem.
numBanks = targetModel.getNumBanks(tile.getCol(), tile.getRow());
1407 CoreOp coreOp = tile.getCoreOp();
1408 problem.
hasCore =
static_cast<bool>(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);
1428 if (tile.isMemTile() && tile.getCol() == 0 &&
1430 targetModel.getTargetArch() == AIEArch::AIE2p) {
1434 SmallVector<BufferOp> buffers;
1435 device.walk<WalkOrder::PreOrder>([&](BufferOp buffer) {
1436 if (buffer.getTileOp() != tile)
1438 buffers.push_back(buffer);
1444 coreOp.emitOpError(layout.message);
1447 if (layout.stackStart) {
1448 coreOp.setStackAddress(*layout.stackStart);
1451 buffers[layout.failed].emitOpError(layout.message);
1455 if (layout.stackStart)
1456 stackRun.
start = *layout.stackStart;
1459 BufferOp failed = buffers[layout.failed];
1460 std::vector<MemoryRun> bankLimits;
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 "
1473 << banks.front() <<
" and " << banks.back();
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)";
1484 failed->emitOpError(
"")
1485 << bufferLabel(failed) <<
" requires " << need <<
" bytes in bank "
1486 << bank <<
", but only " << layout.freeInFailedBank <<
" of "
1487 << bankCapacity <<
" bytes are free there";
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())
1501 << FlatSymbolRefAttr::get(device.getSymNameAttr()) <<
")";
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)";
1509 printMemMap(tile, buffers, layout.at, layout.preAllocated, layout.allocated,
1510 problem.
numBanks, bankLimits, stackRun);
1514 for (
auto [buffer, at] : llvm::zip_equal(buffers, layout.at)) {
1516 buffer.setAddress(at->first);
1517 buffer.setMemBank(at->second);
1520 sortBuffersByAddress(buffers);
1523 if (!checkAndPrintOverlapStackframe(stackRun, buffers) ||
1531static LogicalResult checkBufferScope(BufferOp buffer, DeviceOp device) {
1536 Operation *parent = buffer->getParentOp();
1537 if (!isa<DeviceOp>(parent) && !isa<MemTileDMAOp>(parent)) {
1538 auto tile = buffer.getTileOp();
1539 tile->emitOpError(
"Buffer '")
1541 <<
"' must be defined directly under the device scope. Currently it "
1542 "is nested inside a core tile.";
1549struct AIEAssignBufferAddressesPass
1550 : xilinx::AIE::impl::AIEAssignBufferAddressesBase<
1551 AIEAssignBufferAddressesPass> {
1553 AIEAssignBufferAddressesPass() =
default;
1555 AIEAssignBufferAddressesPass(
const AIEAssignBufferAddressesOptions &options)
1556 : AIEAssignBufferAddressesBase(options) {}
1558 void getDependentDialects(DialectRegistry ®istry)
const override {
1559 registry.insert<func::FuncDialect>();
1560 registry.insert<AIEDialect>();
1563 void runOnOperation()
override {
1564 DeviceOp device = getOperation();
1565 int64_t budget = clPlacementBudget;
1567 device.emitError(
"placement-budget must be positive, got ") << budget;
1568 return signalPassFailure();
1570 applySignatureBankConstraints(device);
1571 if (failed(materializeCoreSections(device))) {
1572 return signalPassFailure();
1580 TileLayoutStats stats;
1581 bool ok = llvm::all_of(device.getOps<TileOp>(), [&](TileOp tile) {
1582 return succeeded(allocateTile(tile, budget, stats));
1590 signalPassFailure();
1596struct AIEPrepareBuffersPass
1597 : xilinx::AIE::impl::AIEPrepareBuffersBase<AIEPrepareBuffersPass> {
1598 void getDependentDialects(DialectRegistry ®istry)
const override {
1599 registry.insert<func::FuncDialect>();
1600 registry.insert<AIEDialect>();
1603 void runOnOperation()
override {
1604 DeviceOp device = getOperation();
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()) {
1614 SymbolTable::getSymbolAttrName(),
1615 builder.getStringAttr(names.uniqueName(
"_anonymous", counter)));
1618 device.walk<WalkOrder::PreOrder>([&](BufferOp buffer) {
1619 if (failed(checkBufferScope(buffer, device))) {
1620 return signalPassFailure();
1628 return std::make_unique<AIEPrepareBuffersPass>();
1631std::unique_ptr<OperationPass<DeviceOp>>
1633 return std::make_unique<AIEAssignBufferAddressesPass>();
1636std::unique_ptr<OperationPass<DeviceOp>>
1638 const AIEAssignBufferAddressesOptions &options) {
1639 return std::make_unique<AIEAssignBufferAddressesPass>(options);
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,...
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
uint32_t tileAlignBitWidth
int64_t maxDataMemorySize
ArrayRef< TileLayoutBuffer > buffers
ArrayRef< MemoryRun > bankLimits
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.
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