| 1 | //===- StaticMemoryPlanning.cpp - Memory planning algorithms --------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #include "mlir/Dialect/Bufferization/Transforms/StaticMemoryPlanning.h" |
| 10 | #include "llvm/Support/MathExtras.h" |
| 11 | #include <numeric> |
| 12 | |
| 13 | using namespace mlir::bufferization; |
| 14 | |
| 15 | /// Align an offset to the specified alignment. |
| 16 | static int64_t alignOffset(int64_t offset, int64_t alignment) { |
| 17 | return llvm::alignTo(Value: offset, Align: alignment); |
| 18 | } |
| 19 | |
| 20 | /// Trivial sequential packing: places each allocation immediately after the |
| 21 | /// previous one with alignment padding. Does not consider lifetimes, so no |
| 22 | /// memory is reused. This gives a simple upper bound on arena size. |
| 23 | /// Complexity: O(n) where n is the number of allocations. |
| 24 | llvm::SmallVector<int64_t> mlir::bufferization::trivialMemoryPlanner( |
| 25 | int64_t arenaAlignment, llvm::ArrayRef<MemoryPlannerAlloc> allocs) { |
| 26 | llvm::SmallVector<int64_t> offsets; |
| 27 | int64_t currentOffset = 0; |
| 28 | |
| 29 | for (const auto &alloc : allocs) { |
| 30 | currentOffset = alignOffset(offset: currentOffset, alignment: alloc.alignment); |
| 31 | assert((arenaAlignment + currentOffset) % alloc.alignment == 0 && |
| 32 | "invalid alignment" ); |
| 33 | offsets.push_back(Elt: currentOffset); |
| 34 | currentOffset += alloc.sizeInBytes; |
| 35 | } |
| 36 | |
| 37 | return offsets; |
| 38 | } |
| 39 | |
| 40 | /// Best-fit lifetime-aware packing: processes allocations in start-time order |
| 41 | /// and places each one in the smallest gap left by allocations whose lifetimes |
| 42 | /// have ended. If no existing gap is large enough, the arena is extended. |
| 43 | /// This minimizes peak memory usage when allocations have non-overlapping |
| 44 | /// lifetimes. |
| 45 | /// Complexity: O(n^2) where n is the number of allocations. |
| 46 | llvm::SmallVector<int64_t> mlir::bufferization::bestFitMemoryPlanner( |
| 47 | int64_t arenaAlignment, llvm::ArrayRef<MemoryPlannerAlloc> allocs) { |
| 48 | // Tracks where each allocation was placed. We only need timeEnd because |
| 49 | // allocations are processed in timeStart order — by the time we place a new |
| 50 | // allocation, all earlier placements already started, so we only need to |
| 51 | // check which ones are still live. |
| 52 | struct Placement { |
| 53 | int64_t offset; |
| 54 | int64_t size; |
| 55 | int64_t timeEnd; |
| 56 | }; |
| 57 | |
| 58 | // Process allocations in order of start time. |
| 59 | llvm::SmallVector<unsigned> order(allocs.size()); |
| 60 | std::iota(first: order.begin(), last: order.end(), value: 0); |
| 61 | llvm::sort(C&: order, Comp: [&](unsigned a, unsigned b) { |
| 62 | return allocs[a].timeStart < allocs[b].timeStart; |
| 63 | }); |
| 64 | |
| 65 | llvm::SmallVector<Placement> placements; |
| 66 | llvm::SmallVector<int64_t> offsets(allocs.size(), 0); |
| 67 | int64_t arenaEnd = 0; |
| 68 | |
| 69 | // Loop over all required allocations and fit them into best gaps. |
| 70 | for (unsigned idx : order) { |
| 71 | const MemoryPlannerAlloc &alloc = allocs[idx]; |
| 72 | |
| 73 | // Collect allocations that are still live at this alloc's start time. |
| 74 | // occupied is pairs of <offset_start, offset_end>. |
| 75 | llvm::SmallVector<std::pair<int64_t, int64_t>> occupied; |
| 76 | for (const auto &p : placements) { |
| 77 | if (p.timeEnd > alloc.timeStart) |
| 78 | occupied.push_back(Elt: {p.offset, p.offset + p.size}); |
| 79 | } |
| 80 | llvm::sort(C&: occupied); |
| 81 | |
| 82 | // Find the best (smallest) gap that fits this allocation. |
| 83 | int64_t bestOffset = -1; |
| 84 | int64_t bestGapSize = INT64_MAX; |
| 85 | |
| 86 | int64_t gapStart = 0; |
| 87 | for (const auto &[occStart, occEnd] : occupied) { |
| 88 | int64_t alignedStart = alignOffset(offset: gapStart, alignment: alloc.alignment); |
| 89 | if (alignedStart >= occStart) { |
| 90 | gapStart = std::max(a: gapStart, b: occEnd); |
| 91 | continue; |
| 92 | } |
| 93 | int64_t gapEnd = occStart; |
| 94 | int64_t gapSize = gapEnd - alignedStart; |
| 95 | // Gap is large enough to fit this allocation (after alignment). |
| 96 | if (gapSize >= alloc.sizeInBytes) { |
| 97 | // Track the smallest sufficient gap (best-fit strategy). |
| 98 | if (gapSize < bestGapSize) { |
| 99 | bestGapSize = gapSize; |
| 100 | bestOffset = alignedStart; |
| 101 | } |
| 102 | } |
| 103 | gapStart = std::max(a: gapStart, b: occEnd); |
| 104 | } |
| 105 | |
| 106 | // Check the trailing gap (between last occupied region and arena end). |
| 107 | // This is only a reuse candidate if the allocation fits within the current |
| 108 | // arena bounds. If it doesn't fit, placing here would extend the arena — |
| 109 | // that case is handled by the fallback below (bestOffset < 0). |
| 110 | int64_t alignedTrailing = alignOffset(offset: gapStart, alignment: alloc.alignment); |
| 111 | if (alignedTrailing + alloc.sizeInBytes <= arenaEnd) { |
| 112 | int64_t trailingSize = arenaEnd - alignedTrailing; |
| 113 | if (trailingSize < bestGapSize) { |
| 114 | bestGapSize = trailingSize; |
| 115 | bestOffset = alignedTrailing; |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | // If no existing gap worked, append at the end. |
| 120 | if (bestOffset < 0) |
| 121 | bestOffset = alignedTrailing; |
| 122 | |
| 123 | assert((arenaAlignment + bestOffset) % alloc.alignment == 0 && |
| 124 | "invalid alignment" ); |
| 125 | offsets[idx] = bestOffset; |
| 126 | placements.push_back(Elt: {.offset: bestOffset, .size: alloc.sizeInBytes, .timeEnd: alloc.timeEnd}); |
| 127 | arenaEnd = std::max(a: arenaEnd, b: bestOffset + alloc.sizeInBytes); |
| 128 | } |
| 129 | |
| 130 | return offsets; |
| 131 | } |
| 132 | |