22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/SmallPtrSet.h"
25#include "llvm/Support/Debug.h"
28#define DEBUG_TYPE "static-memory-planner"
32#define GEN_PASS_DEF_STATICMEMORYPLANNERANALYSISPASS
33#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
44struct AllocationCandidate {
45 memref::AllocOp alloc;
46 SmallVector<memref::DeallocOp> deallocs;
48 int64_t sizeInBytes = 0;
49 int64_t alignment = 1;
75 if (
auto dealloc = dyn_cast<memref::DeallocOp>(user))
76 deallocs.push_back(dealloc);
84findFreedAllocs(memref::DeallocOp dealloc,
87 for (
Value source :
analysis.resolveReverse(dealloc.getMemref()))
88 if (
auto allocOp = source.getDefiningOp<memref::AllocOp>())
89 allocs.push_back(allocOp);
94static int64_t computeSizeInBytes(MemRefType memrefType) {
95 int64_t numElements = memrefType.getNumElements();
96 unsigned elementSizeInBits = memrefType.getElementTypeBitWidth();
97 return (numElements * elementSizeInBits + 7) / 8;
108 Block *planBlock =
nullptr;
109 if (!candidates.empty()) {
110 planBlock = candidates.front().alloc->getBlock();
113 opIndex[&op] = idx++;
117 for (
auto &candidate : candidates) {
121 info.
timeStart = opIndex.lookup(candidate.alloc.getOperation());
126 for (memref::DeallocOp d : candidate.deallocs) {
128 timeEnd = std::max(timeEnd, opIndex.lookup(anchor));
131 allocInfos.push_back(info);
132 arenaAlignment = std::lcm(arenaAlignment, candidate.alignment);
134 return arenaAlignment;
140static void filterSharedDeallocCandidates(
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);
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());
160 worklist.push_back(dealloc);
164 while (!worklist.empty()) {
165 memref::DeallocOp dealloc = worklist.pop_back_val();
166 if (!visited.insert(dealloc.getOperation()).second)
168 for (AllocationCandidate *candidate :
169 deallocCandidates[dealloc.getOperation()]) {
170 if (eligible.erase(candidate->alloc.getOperation()))
171 worklist.append(candidate->deallocs.begin(), candidate->deallocs.end());
175 llvm::erase_if(candidates, [&](AllocationCandidate &candidate) {
176 return !eligible.contains(candidate.alloc.getOperation());
201collectCandidates(FunctionOpInterface funcOp,
203 llvm::Statistic &numSkipped, llvm::Statistic &numEligible,
206 if (funcOp.getFunctionBody().empty())
208 Block *planBlock = &funcOp.getFunctionBody().
front();
210 bool walkFailed =
false;
212 MemRefType memrefType = allocOp.getType();
213 if (!memrefType.hasStaticShape()) {
220 if (allocOp->getBlock() != planBlock) {
226 if (!memrefType.getElementType().isIntOrFloat()) {
232 if (!memrefType.getLayout().isIdentity()) {
238 collectDeallocs(allocOp.getResult(), analysis, deallocs);
240 if (deallocs.empty()) {
241 allocOp.emitError(
"no dealloc found; run the deallocation pipeline "
247 for (memref::DeallocOp d : deallocs) {
251 allocOp.emitError(
"unstructured control flow is not supported");
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);
269 size_t initialCandidates = candidates.size();
270 filterSharedDeallocCandidates(analysis, candidates);
271 numSkipped += initialCandidates - candidates.size();
273 numEligible += candidates.size();
279static FailureOr<Value> createArena(
OpBuilder &builder,
280 FunctionOpInterface funcOp,
281 StringRef arenaMode,
int64_t totalSize,
285 if (arenaMode ==
"allocate") {
286 auto arenaType = MemRefType::get({totalSize}, builder.
getI8Type());
288 memref::AllocOp::create(builder, loc, arenaType,
ValueRange{},
290 LLVM_DEBUG(llvm::dbgs()
291 <<
"[static-memory-planner] created arena via AllocOp: size="
292 << totalSize <<
" bytes, alignment=" << arenaAlignment
294 return arenaAlloc.getResult();
297 if (arenaMode ==
"arg") {
298 if (funcOp.getNumArguments() == 0)
299 return funcOp->emitError(
300 "arena-mode=arg requires at least one function argument");
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>");
309 LLVM_DEBUG(llvm::dbgs()
310 <<
"[static-memory-planner] using arena from function arg 0\n");
314 return funcOp->emitError(
"invalid arena-mode: '" + arenaMode +
315 "' (must be 'allocate' or 'arg')");
325 for (
auto &candidate : candidates) {
327 Location loc = candidate.alloc.getLoc();
328 MemRefType originalType = candidate.alloc.getType();
332 auto view = memref::ViewOp::create(builder, loc, originalType, arenaValue,
334 candidate.alloc.getResult().replaceAllUsesWith(view.getResult());
335 allocsToErase.push_back(candidate.alloc.getOperation());
337 for (memref::DeallocOp d : candidate.deallocs)
338 deallocsToErase.insert(d.getOperation());
354struct StaticMemoryPlannerAnalysisPass
356 StaticMemoryPlannerAnalysisPass> {
358 using Base = bufferization::impl::StaticMemoryPlannerAnalysisPassBase<
359 StaticMemoryPlannerAnalysisPass>;
362 void runOnOperation()
override;
365void StaticMemoryPlannerAnalysisPass::runOnOperation() {
366 auto funcOp = llvm::cast<FunctionOpInterface>(getOperation());
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();
380 BufferViewFlowAnalysis
analysis(funcOp);
381 SmallVector<AllocationCandidate> candidates;
382 if (
failed(collectCandidates(funcOp, analysis, numSkipped, numEligible,
384 return signalPassFailure();
386 if (candidates.empty())
390 SmallVector<bufferization::MemoryPlannerAlloc> allocInfos;
391 int64_t arenaAlignment = buildAllocInfos(candidates, allocInfos);
394 SmallVector<int64_t> offsets;
396 case bufferization::MemoryPlannerAlgorithm::Trivial:
399 case bufferization::MemoryPlannerAlgorithm::BestFit:
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");
416 Operation *firstAlloc = candidates.front().alloc;
417 OpBuilder builder(firstAlloc);
418 FailureOr<Value> arenaValue =
419 createArena(builder, funcOp, arenaMode, totalSize, arenaAlignment);
421 return signalPassFailure();
424 rewriteAllocations(candidates, *arenaValue);
Block represents an ordered list of Operations.
Operation * findAncestorOpInBlock(Operation &op)
Returns 'op' if 'op' lies in this block, or otherwise finds the ancestor operation of 'op' that lies ...
A straight-forward alias analysis which ensures that all dependencies of all values will be determine...
IntegerAttr getI64IntegerAttr(int64_t value)
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
This class helps build Operations.
Operation is the basic unit of execution within MLIR.
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),...
user_range getUsers()
Returns a range of all users.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Type getType() const
Return the type of this value.
A utility result that is used to signal how to proceed with an ongoing walk:
static WalkResult advance()
static WalkResult interrupt()
static ConstantIndexOp create(OpBuilder &builder, Location location, int64_t value)
StaticMemoryPlannerAnalysisPassBase Base
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.
Include the generated interface declarations.
llvm::DenseMap< KeyT, ValueT, KeyInfoT, BucketT > DenseMap
Descriptor for a single allocation to be placed by the memory planner.