| 1 | //===- StaticMemoryPlannerAnalysis.cpp - Static memory planning -----------===// |
| 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 | // Transforms memref.alloc/memref.dealloc pairs into a single arena allocation |
| 10 | // with memref.view. Delegates offset computation to planning algorithms in |
| 11 | // StaticMemoryPlanning.h. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 16 | #include "mlir/Dialect/Bufferization/Transforms/BufferViewFlowAnalysis.h" |
| 17 | #include "mlir/Dialect/Bufferization/Transforms/Passes.h" |
| 18 | #include "mlir/Dialect/Bufferization/Transforms/StaticMemoryPlanning.h" |
| 19 | #include "mlir/Dialect/MemRef/IR/MemRef.h" |
| 20 | #include "mlir/IR/Builders.h" |
| 21 | #include "mlir/Interfaces/FunctionInterfaces.h" |
| 22 | #include "llvm/ADT/DenseMap.h" |
| 23 | #include "llvm/ADT/STLExtras.h" |
| 24 | #include "llvm/ADT/SmallPtrSet.h" |
| 25 | #include "llvm/Support/Debug.h" |
| 26 | #include <numeric> |
| 27 | |
| 28 | #define DEBUG_TYPE "static-memory-planner" |
| 29 | |
| 30 | namespace mlir { |
| 31 | namespace bufferization { |
| 32 | #define GEN_PASS_DEF_STATICMEMORYPLANNERANALYSISPASS |
| 33 | #include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc" |
| 34 | } // namespace bufferization |
| 35 | } // namespace mlir |
| 36 | |
| 37 | using namespace mlir; |
| 38 | |
| 39 | namespace { |
| 40 | |
| 41 | /// A candidate allocation with its matching deallocation(s) and assigned |
| 42 | /// offset. An alloc may be freed indirectly through arith.select chains, |
| 43 | /// yielding multiple potential deallocs — all must be in the same block. |
| 44 | struct AllocationCandidate { |
| 45 | memref::AllocOp alloc; |
| 46 | SmallVector<memref::DeallocOp> deallocs; |
| 47 | int64_t offset = 0; // Offset in bytes from arena start (assigned by planner) |
| 48 | int64_t sizeInBytes = 0; // Size in bytes |
| 49 | int64_t alignment = 1; // Required alignment in bytes |
| 50 | }; |
| 51 | |
| 52 | //===----------------------------------------------------------------------===// |
| 53 | // Helper utilities |
| 54 | //===----------------------------------------------------------------------===// |
| 55 | |
| 56 | /// Collect all dealloc ops that might free the given alloc value. Instead of a |
| 57 | /// bespoke traversal, this uses the shared `BufferViewFlowAnalysis`, which |
| 58 | /// already models all the ways a buffer can flow to a dealloc: |
| 59 | /// - `arith.select` (via BufferViewFlowOpInterface) |
| 60 | /// - `scf.if`/`scf.for` (via RegionBranchOpInterface region/result wiring) |
| 61 | /// - `cf.br`/`cf.cond_br` (via BranchOpInterface block arguments) |
| 62 | /// - `memref.view`/subview (via ViewLikeOpInterface) |
| 63 | /// `analysis.resolve(alloc)` returns the forward alias set (the alloc plus |
| 64 | /// every value it may flow into); a dealloc on any of those aliases frees the |
| 65 | /// alloc. For example: |
| 66 | /// %0 = memref.alloc() |
| 67 | /// %2 = arith.select %c, %0, %1 |
| 68 | /// memref.dealloc %2 <- covers %0 conditionally (via alias set) |
| 69 | /// %3 = scf.if %c { yield %0 } else { yield %1 } |
| 70 | /// memref.dealloc %3 <- also covers %0 conditionally |
| 71 | static void collectDeallocs(Value alloc, const BufferViewFlowAnalysis &analysis, |
| 72 | SmallVectorImpl<memref::DeallocOp> &deallocs) { |
| 73 | for (Value alias : analysis.resolve(value: alloc)) |
| 74 | for (Operation *user : alias.getUsers()) |
| 75 | if (auto dealloc = dyn_cast<memref::DeallocOp>(Val: user)) |
| 76 | deallocs.push_back(Elt: dealloc); |
| 77 | } |
| 78 | |
| 79 | /// Return the set of allocation ops whose buffer may be freed by `dealloc`, |
| 80 | /// i.e. the terminal `memref.alloc` sources that flow into the dealloc operand. |
| 81 | /// Uses the reverse alias set so that a dealloc reached through a `scf.if` |
| 82 | /// result or `arith.select` is attributed to every alloc it may free. |
| 83 | static SmallVector<memref::AllocOp> |
| 84 | findFreedAllocs(memref::DeallocOp dealloc, |
| 85 | const BufferViewFlowAnalysis &analysis) { |
| 86 | SmallVector<memref::AllocOp> allocs; |
| 87 | for (Value source : analysis.resolveReverse(value: dealloc.getMemref())) |
| 88 | if (auto allocOp = source.getDefiningOp<memref::AllocOp>()) |
| 89 | allocs.push_back(Elt: allocOp); |
| 90 | return allocs; |
| 91 | } |
| 92 | |
| 93 | /// Compute the size in bytes for a memref type. |
| 94 | static int64_t computeSizeInBytes(MemRefType memrefType) { |
| 95 | int64_t numElements = memrefType.getNumElements(); |
| 96 | unsigned elementSizeInBits = memrefType.getElementTypeBitWidth(); |
| 97 | return (numElements * elementSizeInBits + 7) / 8; // Round up to bytes |
| 98 | } |
| 99 | |
| 100 | /// Build lifetime-annotated allocation descriptors from candidates. |
| 101 | /// Returns the arena alignment (LCM of all individual alignments). |
| 102 | /// Uses a single block scan (O(n+m)) instead of one scan per candidate. |
| 103 | static int64_t buildAllocInfos( |
| 104 | MutableArrayRef<AllocationCandidate> candidates, |
| 105 | SmallVectorImpl<bufferization::MemoryPlannerAlloc> &allocInfos) { |
| 106 | // Build an op-index map with a single pass over the plan block. |
| 107 | DenseMap<Operation *, int64_t> opIndex; |
| 108 | Block *planBlock = nullptr; |
| 109 | if (!candidates.empty()) { |
| 110 | planBlock = candidates.front().alloc->getBlock(); |
| 111 | int64_t idx = 0; |
| 112 | for (Operation &op : *planBlock) |
| 113 | opIndex[&op] = idx++; |
| 114 | } |
| 115 | |
| 116 | int64_t arenaAlignment = 1; |
| 117 | for (auto &candidate : candidates) { |
| 118 | bufferization::MemoryPlannerAlloc info; |
| 119 | info.sizeInBytes = candidate.sizeInBytes; |
| 120 | info.alignment = candidate.alignment; |
| 121 | info.timeStart = opIndex.lookup(Val: candidate.alloc.getOperation()); |
| 122 | // Conservative: timeEnd = latest dealloc position among all potential |
| 123 | // deallocs. A dealloc may be nested (e.g. inside an scf.if body); its |
| 124 | // lifetime contribution is bounded by the enclosing op in the plan block. |
| 125 | int64_t timeEnd = info.timeStart; |
| 126 | for (memref::DeallocOp d : candidate.deallocs) { |
| 127 | Operation *anchor = planBlock->findAncestorOpInBlock(op&: *d.getOperation()); |
| 128 | timeEnd = std::max(a: timeEnd, b: opIndex.lookup(Val: anchor)); |
| 129 | } |
| 130 | info.timeEnd = timeEnd; |
| 131 | allocInfos.push_back(Elt: info); |
| 132 | arenaAlignment = std::lcm(m: arenaAlignment, n: candidate.alignment); |
| 133 | } |
| 134 | return arenaAlignment; |
| 135 | } |
| 136 | |
| 137 | /// Remove candidates that share a dealloc with an ineligible allocation. |
| 138 | /// Exclusion propagates through shared deallocs: removing one candidate may |
| 139 | /// prevent erasing another dealloc, which in turn excludes more candidates. |
| 140 | static void filterSharedDeallocCandidates( |
| 141 | const BufferViewFlowAnalysis &analysis, |
| 142 | SmallVectorImpl<AllocationCandidate> &candidates) { |
| 143 | SmallPtrSet<Operation *, 16> eligible; |
| 144 | DenseMap<Operation *, SmallVector<AllocationCandidate *>> deallocCandidates; |
| 145 | for (auto &candidate : candidates) { |
| 146 | eligible.insert(Ptr: candidate.alloc.getOperation()); |
| 147 | for (memref::DeallocOp dealloc : candidate.deallocs) |
| 148 | deallocCandidates[dealloc.getOperation()].push_back(Elt: &candidate); |
| 149 | } |
| 150 | |
| 151 | // Seed deallocs that may release an allocation rejected by the initial |
| 152 | // eligibility checks, such as a dynamic or nested allocation. |
| 153 | SmallVector<memref::DeallocOp> worklist; |
| 154 | for (const auto &entry : deallocCandidates) { |
| 155 | auto dealloc = cast<memref::DeallocOp>(Val: entry.first); |
| 156 | if (llvm::any_of(Range: findFreedAllocs(dealloc, analysis), |
| 157 | P: [&](memref::AllocOp alloc) { |
| 158 | return !eligible.contains(Ptr: alloc.getOperation()); |
| 159 | })) |
| 160 | worklist.push_back(Elt: dealloc); |
| 161 | } |
| 162 | |
| 163 | SmallPtrSet<Operation *, 16> visited; |
| 164 | while (!worklist.empty()) { |
| 165 | memref::DeallocOp dealloc = worklist.pop_back_val(); |
| 166 | if (!visited.insert(Ptr: dealloc.getOperation()).second) |
| 167 | continue; |
| 168 | for (AllocationCandidate *candidate : |
| 169 | deallocCandidates[dealloc.getOperation()]) { |
| 170 | if (eligible.erase(Ptr: candidate->alloc.getOperation())) |
| 171 | worklist.append(in_start: candidate->deallocs.begin(), in_end: candidate->deallocs.end()); |
| 172 | } |
| 173 | } |
| 174 | |
| 175 | llvm::erase_if(C&: candidates, P: [&](AllocationCandidate &candidate) { |
| 176 | return !eligible.contains(Ptr: candidate.alloc.getOperation()); |
| 177 | }); |
| 178 | } |
| 179 | |
| 180 | /// Collect alloc/dealloc groups eligible for arena placement. |
| 181 | /// |
| 182 | /// Eligibility uses the shared `BufferViewFlowAnalysis` so that buffers flowing |
| 183 | /// through `arith.select`, `scf.if`/`scf.for` results, `cf` branches, or view |
| 184 | /// ops are handled uniformly. An allocation is eligible when: |
| 185 | /// - it has a static shape (dynamic shapes are silently skipped), and |
| 186 | /// - its element type is an integer or float, and |
| 187 | /// - its layout is identity, and |
| 188 | /// - it lives directly in the function's entry block (allocs nested in a |
| 189 | /// region are skipped for now), and |
| 190 | /// - every dealloc that may free it is anchored in that same entry block -- |
| 191 | /// either directly, or nested inside an op of that block (e.g. an |
| 192 | /// `scf.if` body), which conservatively bounds the lifetime. |
| 193 | /// A dealloc that escapes the entry block entirely (e.g. lives in a sibling |
| 194 | /// `cf` block) is reported as an error, as is an alloc with no dealloc. |
| 195 | /// |
| 196 | /// To keep the rewrite safe, a dealloc is only accepted if *all* allocs it may |
| 197 | /// free (per the reverse alias set) are themselves candidates in this block; |
| 198 | /// otherwise erasing it during the rewrite could leak or double-free a buffer |
| 199 | /// that is not managed by the arena. |
| 200 | static LogicalResult |
| 201 | collectCandidates(FunctionOpInterface funcOp, |
| 202 | const BufferViewFlowAnalysis &analysis, |
| 203 | llvm::Statistic &numSkipped, llvm::Statistic &numEligible, |
| 204 | SmallVector<AllocationCandidate> &candidates) { |
| 205 | // All candidates are planned relative to the function's entry block. |
| 206 | if (funcOp.getFunctionBody().empty()) |
| 207 | return success(); |
| 208 | Block *planBlock = &funcOp.getFunctionBody().front(); |
| 209 | |
| 210 | bool walkFailed = false; |
| 211 | funcOp->walk(callback: [&](memref::AllocOp allocOp) -> WalkResult { |
| 212 | MemRefType memrefType = allocOp.getType(); |
| 213 | if (!memrefType.hasStaticShape()) { |
| 214 | ++numSkipped; |
| 215 | return WalkResult::advance(); |
| 216 | } |
| 217 | |
| 218 | // Only plan allocs that live directly in the entry block. Allocs nested in |
| 219 | // a region (loop/conditional body) are skipped for now. |
| 220 | if (allocOp->getBlock() != planBlock) { |
| 221 | ++numSkipped; |
| 222 | return WalkResult::advance(); |
| 223 | } |
| 224 | |
| 225 | // computeSizeInBytes only supports integer and floating-point elements. |
| 226 | if (!memrefType.getElementType().isIntOrFloat()) { |
| 227 | ++numSkipped; |
| 228 | return WalkResult::advance(); |
| 229 | } |
| 230 | |
| 231 | // memref.view requires an identity layout for its result. |
| 232 | if (!memrefType.getLayout().isIdentity()) { |
| 233 | ++numSkipped; |
| 234 | return WalkResult::advance(); |
| 235 | } |
| 236 | |
| 237 | SmallVector<memref::DeallocOp> deallocs; |
| 238 | collectDeallocs(alloc: allocOp.getResult(), analysis, deallocs); |
| 239 | |
| 240 | if (deallocs.empty()) { |
| 241 | allocOp.emitError(message: "no dealloc found; run the deallocation pipeline " |
| 242 | "before this pass" ); |
| 243 | walkFailed = true; |
| 244 | return WalkResult::interrupt(); |
| 245 | } |
| 246 | |
| 247 | for (memref::DeallocOp d : deallocs) { |
| 248 | // The dealloc must be anchored in the plan block (directly or via an |
| 249 | // enclosing op such as an scf.if). A dealloc in a sibling block escapes. |
| 250 | if (!planBlock->findAncestorOpInBlock(op&: *d.getOperation())) { |
| 251 | allocOp.emitError(message: "unstructured control flow is not supported" ); |
| 252 | walkFailed = true; |
| 253 | return WalkResult::interrupt(); |
| 254 | } |
| 255 | } |
| 256 | |
| 257 | AllocationCandidate candidate; |
| 258 | candidate.alloc = allocOp; |
| 259 | candidate.deallocs = deallocs; |
| 260 | candidate.sizeInBytes = computeSizeInBytes(memrefType); |
| 261 | candidate.alignment = allocOp.getAlignment().value_or(u: 1); |
| 262 | candidates.push_back(Elt: candidate); |
| 263 | return WalkResult::advance(); |
| 264 | }); |
| 265 | |
| 266 | if (walkFailed) |
| 267 | return failure(); |
| 268 | |
| 269 | size_t initialCandidates = candidates.size(); |
| 270 | filterSharedDeallocCandidates(analysis, candidates); |
| 271 | numSkipped += initialCandidates - candidates.size(); |
| 272 | |
| 273 | numEligible += candidates.size(); |
| 274 | return success(); |
| 275 | } |
| 276 | |
| 277 | /// Create or obtain the arena buffer based on the arena mode. |
| 278 | /// Returns failure if the mode is invalid or preconditions aren't met. |
| 279 | static FailureOr<Value> createArena(OpBuilder &builder, |
| 280 | FunctionOpInterface funcOp, |
| 281 | StringRef arenaMode, int64_t totalSize, |
| 282 | int64_t arenaAlignment) { |
| 283 | Location loc = funcOp->getLoc(); |
| 284 | |
| 285 | if (arenaMode == "allocate" ) { |
| 286 | auto arenaType = MemRefType::get(shape: {totalSize}, elementType: builder.getI8Type()); |
| 287 | auto arenaAlloc = |
| 288 | memref::AllocOp::create(builder, location: loc, memrefType: arenaType, dynamicSizes: ValueRange{}, |
| 289 | alignment: builder.getI64IntegerAttr(value: arenaAlignment)); |
| 290 | LLVM_DEBUG(llvm::dbgs() |
| 291 | << "[static-memory-planner] created arena via AllocOp: size=" |
| 292 | << totalSize << " bytes, alignment=" << arenaAlignment |
| 293 | << " bytes\n" ); |
| 294 | return arenaAlloc.getResult(); |
| 295 | } |
| 296 | |
| 297 | if (arenaMode == "arg" ) { |
| 298 | if (funcOp.getNumArguments() == 0) |
| 299 | return funcOp->emitError( |
| 300 | message: "arena-mode=arg requires at least one function argument" ); |
| 301 | |
| 302 | Value arenaValue = funcOp.getArgument(idx: 0); |
| 303 | auto arenaType = dyn_cast<MemRefType>(Val: arenaValue.getType()); |
| 304 | if (!arenaType || !arenaType.getElementType().isInteger(width: 8) || |
| 305 | arenaType.getRank() != 1) |
| 306 | return funcOp->emitError( |
| 307 | message: "arena-mode=arg requires first argument to be memref<...xi8>" ); |
| 308 | |
| 309 | LLVM_DEBUG(llvm::dbgs() |
| 310 | << "[static-memory-planner] using arena from function arg 0\n" ); |
| 311 | return arenaValue; |
| 312 | } |
| 313 | |
| 314 | return funcOp->emitError(message: "invalid arena-mode: '" + arenaMode + |
| 315 | "' (must be 'allocate' or 'arg')" ); |
| 316 | } |
| 317 | |
| 318 | /// Replace each alloc/dealloc pair with a memref.view into the arena. |
| 319 | static void rewriteAllocations(MutableArrayRef<AllocationCandidate> candidates, |
| 320 | Value arenaValue) { |
| 321 | SmallPtrSet<Operation *, 8> deallocsToErase; |
| 322 | SmallVector<Operation *> allocsToErase; |
| 323 | |
| 324 | // Replace all alloc results with views (rewires selects too). |
| 325 | for (auto &candidate : candidates) { |
| 326 | OpBuilder builder(candidate.alloc); |
| 327 | Location loc = candidate.alloc.getLoc(); |
| 328 | MemRefType originalType = candidate.alloc.getType(); |
| 329 | |
| 330 | Value offsetIndex = |
| 331 | arith::ConstantIndexOp::create(builder, location: loc, value: candidate.offset); |
| 332 | auto view = memref::ViewOp::create(builder, location: loc, resultType0: originalType, source: arenaValue, |
| 333 | byte_shift: offsetIndex, sizes: SmallVector<Value>{}); |
| 334 | candidate.alloc.getResult().replaceAllUsesWith(newValue: view.getResult()); |
| 335 | allocsToErase.push_back(Elt: candidate.alloc.getOperation()); |
| 336 | |
| 337 | for (memref::DeallocOp d : candidate.deallocs) |
| 338 | deallocsToErase.insert(Ptr: d.getOperation()); |
| 339 | } |
| 340 | |
| 341 | // Erase deallocs first (they may reference alloc results via selects). |
| 342 | for (Operation *d : deallocsToErase) |
| 343 | d->erase(); |
| 344 | |
| 345 | // Erase allocs last (no users remain after replaceAllUsesWith). |
| 346 | for (Operation *allocOp : allocsToErase) |
| 347 | allocOp->erase(); |
| 348 | } |
| 349 | |
| 350 | //===----------------------------------------------------------------------===// |
| 351 | // StaticMemoryPlannerAnalysisPass |
| 352 | //===----------------------------------------------------------------------===// |
| 353 | |
| 354 | struct StaticMemoryPlannerAnalysisPass |
| 355 | : public bufferization::impl::StaticMemoryPlannerAnalysisPassBase< |
| 356 | StaticMemoryPlannerAnalysisPass> { |
| 357 | public: |
| 358 | using Base = bufferization::impl::StaticMemoryPlannerAnalysisPassBase< |
| 359 | StaticMemoryPlannerAnalysisPass>; |
| 360 | using Base::Base; |
| 361 | |
| 362 | void runOnOperation() override; |
| 363 | }; |
| 364 | |
| 365 | void StaticMemoryPlannerAnalysisPass::runOnOperation() { |
| 366 | auto funcOp = llvm::cast<FunctionOpInterface>(Val: getOperation()); |
| 367 | |
| 368 | // Step 0: Check for memref return types (not supported) |
| 369 | for (Type resultType : funcOp.getResultTypes()) { |
| 370 | if (isa<BaseMemRefType>(Val: resultType)) { |
| 371 | funcOp->emitError(message: "static-memory-planner does not support functions " |
| 372 | "with memref return types" ); |
| 373 | return signalPassFailure(); |
| 374 | } |
| 375 | } |
| 376 | |
| 377 | // Step 1: Collect eligible allocation candidates. The buffer view-flow |
| 378 | // analysis models how buffers flow through selects, scf.if results, branches, |
| 379 | // and view ops so we can find deallocs and freed allocs uniformly. |
| 380 | BufferViewFlowAnalysis analysis(funcOp); |
| 381 | SmallVector<AllocationCandidate> candidates; |
| 382 | if (failed(Result: collectCandidates(funcOp, analysis, numSkipped, numEligible, |
| 383 | candidates))) |
| 384 | return signalPassFailure(); |
| 385 | |
| 386 | if (candidates.empty()) |
| 387 | return; |
| 388 | |
| 389 | // Step 2: Build allocation descriptors with lifetime info. |
| 390 | SmallVector<bufferization::MemoryPlannerAlloc> allocInfos; |
| 391 | int64_t arenaAlignment = buildAllocInfos(candidates, allocInfos); |
| 392 | |
| 393 | // Step 3: Run the planning algorithm. |
| 394 | SmallVector<int64_t> offsets; |
| 395 | switch (algorithm) { |
| 396 | case bufferization::MemoryPlannerAlgorithm::Trivial: |
| 397 | offsets = bufferization::trivialMemoryPlanner(arenaAlignment, allocs: allocInfos); |
| 398 | break; |
| 399 | case bufferization::MemoryPlannerAlgorithm::BestFit: |
| 400 | offsets = bufferization::bestFitMemoryPlanner(arenaAlignment, allocs: allocInfos); |
| 401 | break; |
| 402 | } |
| 403 | |
| 404 | // Step 4: Compute total arena size and assign offsets. |
| 405 | int64_t totalSize = 0; |
| 406 | for (size_t i = 0; i < candidates.size(); ++i) { |
| 407 | candidates[i].offset = offsets[i]; |
| 408 | totalSize = std::max(a: totalSize, b: offsets[i] + candidates[i].sizeInBytes); |
| 409 | LLVM_DEBUG(llvm::dbgs() |
| 410 | << "[static-memory-planner] offset=" << candidates[i].offset |
| 411 | << " size=" << candidates[i].sizeInBytes |
| 412 | << " alignment=" << candidates[i].alignment << "\n" ); |
| 413 | } |
| 414 | |
| 415 | // Step 5: Obtain arena based on arena mode. |
| 416 | Operation *firstAlloc = candidates.front().alloc; |
| 417 | OpBuilder builder(firstAlloc); |
| 418 | FailureOr<Value> arenaValue = |
| 419 | createArena(builder, funcOp, arenaMode, totalSize, arenaAlignment); |
| 420 | if (failed(Result: arenaValue)) |
| 421 | return signalPassFailure(); |
| 422 | |
| 423 | // Step 6: Replace each alloc with memref.view into the arena. |
| 424 | rewriteAllocations(candidates, arenaValue: *arenaValue); |
| 425 | } |
| 426 | |
| 427 | } // end anonymous namespace |
| 428 | |