MLIR 24.0.0git
StaticMemoryPlannerAnalysis.cpp
Go to the documentation of this file.
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
20#include "mlir/IR/Builders.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
30namespace mlir {
31namespace bufferization {
32#define GEN_PASS_DEF_STATICMEMORYPLANNERANALYSISPASS
33#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
34} // namespace bufferization
35} // namespace mlir
36
37using namespace mlir;
38
39namespace {
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.
44struct 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
71static void collectDeallocs(Value alloc, const BufferViewFlowAnalysis &analysis,
73 for (Value alias : analysis.resolve(alloc))
74 for (Operation *user : alias.getUsers())
75 if (auto dealloc = dyn_cast<memref::DeallocOp>(user))
76 deallocs.push_back(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.
84findFreedAllocs(memref::DeallocOp dealloc,
85 const BufferViewFlowAnalysis &analysis) {
87 for (Value source : analysis.resolveReverse(dealloc.getMemref()))
88 if (auto allocOp = source.getDefiningOp<memref::AllocOp>())
89 allocs.push_back(allocOp);
90 return allocs;
91}
92
93/// Compute the size in bytes for a memref type.
94static 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.
103static int64_t buildAllocInfos(
106 // Build an op-index map with a single pass over the plan block.
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) {
119 info.sizeInBytes = candidate.sizeInBytes;
120 info.alignment = candidate.alignment;
121 info.timeStart = opIndex.lookup(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(*d.getOperation());
128 timeEnd = std::max(timeEnd, opIndex.lookup(anchor));
129 }
130 info.timeEnd = timeEnd;
131 allocInfos.push_back(info);
132 arenaAlignment = std::lcm(arenaAlignment, 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.
140static void filterSharedDeallocCandidates(
141 const BufferViewFlowAnalysis &analysis,
145 for (auto &candidate : candidates) {
146 eligible.insert(candidate.alloc.getOperation());
147 for (memref::DeallocOp dealloc : candidate.deallocs)
148 deallocCandidates[dealloc.getOperation()].push_back(&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.
154 for (const auto &entry : deallocCandidates) {
155 auto dealloc = cast<memref::DeallocOp>(entry.first);
156 if (llvm::any_of(findFreedAllocs(dealloc, analysis),
157 [&](memref::AllocOp alloc) {
158 return !eligible.contains(alloc.getOperation());
159 }))
160 worklist.push_back(dealloc);
161 }
162
164 while (!worklist.empty()) {
165 memref::DeallocOp dealloc = worklist.pop_back_val();
166 if (!visited.insert(dealloc.getOperation()).second)
167 continue;
168 for (AllocationCandidate *candidate :
169 deallocCandidates[dealloc.getOperation()]) {
170 if (eligible.erase(candidate->alloc.getOperation()))
171 worklist.append(candidate->deallocs.begin(), candidate->deallocs.end());
172 }
173 }
174
175 llvm::erase_if(candidates, [&](AllocationCandidate &candidate) {
176 return !eligible.contains(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.
200static LogicalResult
201collectCandidates(FunctionOpInterface funcOp,
202 const BufferViewFlowAnalysis &analysis,
203 llvm::Statistic &numSkipped, llvm::Statistic &numEligible,
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([&](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
238 collectDeallocs(allocOp.getResult(), analysis, deallocs);
239
240 if (deallocs.empty()) {
241 allocOp.emitError("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(*d.getOperation())) {
251 allocOp.emitError("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(1);
262 candidates.push_back(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.
279static 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({totalSize}, builder.getI8Type());
287 auto arenaAlloc =
288 memref::AllocOp::create(builder, loc, arenaType, ValueRange{},
289 builder.getI64IntegerAttr(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 "arena-mode=arg requires at least one function argument");
301
302 Value arenaValue = funcOp.getArgument(0);
303 auto arenaType = dyn_cast<MemRefType>(arenaValue.getType());
304 if (!arenaType || !arenaType.getElementType().isInteger(8) ||
305 arenaType.getRank() != 1)
306 return funcOp->emitError(
307 "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("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.
319static 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, loc, candidate.offset);
332 auto view = memref::ViewOp::create(builder, loc, originalType, arenaValue,
333 offsetIndex, SmallVector<Value>{});
334 candidate.alloc.getResult().replaceAllUsesWith(view.getResult());
335 allocsToErase.push_back(candidate.alloc.getOperation());
336
337 for (memref::DeallocOp d : candidate.deallocs)
338 deallocsToErase.insert(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
354struct StaticMemoryPlannerAnalysisPass
356 StaticMemoryPlannerAnalysisPass> {
357public:
358 using Base = bufferization::impl::StaticMemoryPlannerAnalysisPassBase<
359 StaticMemoryPlannerAnalysisPass>;
360 using Base::Base;
361
362 void runOnOperation() override;
363};
364
365void StaticMemoryPlannerAnalysisPass::runOnOperation() {
366 auto funcOp = llvm::cast<FunctionOpInterface>(getOperation());
367
368 // Step 0: Check for memref return types (not supported)
369 for (Type resultType : funcOp.getResultTypes()) {
370 if (isa<BaseMemRefType>(resultType)) {
371 funcOp->emitError("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(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, allocInfos);
398 break;
399 case bufferization::MemoryPlannerAlgorithm::BestFit:
400 offsets = bufferization::bestFitMemoryPlanner(arenaAlignment, 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(totalSize, 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(arenaValue))
421 return signalPassFailure();
422
423 // Step 6: Replace each alloc with memref.view into the arena.
424 rewriteAllocations(candidates, *arenaValue);
425}
426
427} // end anonymous namespace
return success()
Block represents an ordered list of Operations.
Definition Block.h:34
Operation * findAncestorOpInBlock(Operation &op)
Returns 'op' if 'op' lies in this block, or otherwise finds the ancestor operation of 'op' that lies ...
Definition Block.cpp:74
Operation & front()
Definition Block.h:178
A straight-forward alias analysis which ensures that all dependencies of all values will be determine...
IntegerAttr getI64IntegerAttr(int64_t value)
Definition Builders.cpp:120
IntegerType getI8Type()
Definition Builders.cpp:67
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition Location.h:76
This class helps build Operations.
Definition Builders.h:210
Operation is the basic unit of execution within MLIR.
Definition Operation.h:87
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Definition Operation.h:851
user_range getUsers()
Returns a range of all users.
Definition Operation.h:927
This class provides an abstraction over the different types of ranges over Values.
Definition ValueRange.h:392
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition Value.h:96
Type getType() const
Return the type of this value.
Definition Value.h:105
A utility result that is used to signal how to proceed with an ongoing walk:
Definition WalkResult.h:29
static WalkResult advance()
Definition WalkResult.h:47
static WalkResult interrupt()
Definition WalkResult.h:46
static ConstantIndexOp create(OpBuilder &builder, Location location, int64_t value)
Definition ArithOps.cpp:434
llvm::SmallVector< int64_t > trivialMemoryPlanner(int64_t arenaAlignment, llvm::ArrayRef< MemoryPlannerAlloc > allocs)
Sequential packing without lifetime overlap.
llvm::SmallVector< int64_t > bestFitMemoryPlanner(int64_t arenaAlignment, llvm::ArrayRef< MemoryPlannerAlloc > allocs)
Best-fit packing with lifetime-aware gap reuse.
detail::InFlightRemark failed(Location loc, RemarkOpts opts)
Report an optimization remark that failed.
Definition Remarks.h:853
detail::InFlightRemark analysis(Location loc, RemarkOpts opts)
Report an optimization analysis remark.
Definition Remarks.h:859
Include the generated interface declarations.
llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap
Definition LLVM.h:123
Descriptor for a single allocation to be placed by the memory planner.