30#define GEN_PASS_DEF_BUFFERHOISTINGPASS
31#define GEN_PASS_DEF_BUFFERLOOPHOISTINGPASS
32#define GEN_PASS_DEF_PROMOTEBUFFERSTOSTACKPASS
33#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
43 return isa<LoopLikeOpInterface, RegionBranchOpInterface>(op);
53 if (isa<LoopLikeOpInterface>(op))
58 auto regionInterface = dyn_cast<RegionBranchOpInterface>(op);
62 return regionInterface.hasLoop();
85 for (
Value alias : aliases) {
86 if (!isa<BaseMemRefType>(alias.getType()))
92 if (
auto load = dyn_cast<memref::LoadOp>(user)) {
96 if (
load.getInvariant())
100 if (
auto store = dyn_cast<memref::StoreOp>(user)) {
101 if (store.getMemref() != alias)
107 if (isa<memref::CastOp, memref::SubViewOp>(user))
111 if (user != loop.getConditionOp().getOperation())
121 auto allocOp = dyn_cast<AllocationOpInterface>(op);
129 auto allocOp = dyn_cast<AllocationOpInterface>(op);
138 unsigned maxRankOfAllocatedMemRef) {
139 auto type = dyn_cast<ShapedType>(alloc.
getType());
142 if (!type.hasStaticShape()) {
148 if (type.getRank() <= maxRankOfAllocatedMemRef) {
151 return operand.getDefiningOp<memref::RankOp>();
157 Type elemType = type.getElementType();
159 !isa<ComplexType, IndexType, VectorType>(elemType) &&
160 !isa<DataLayoutTypeInterface>(elemType))
167 std::optional<int64_t> numElements = type.tryGetNumElements();
172 *numElements >
static_cast<int64_t>(maximumSizeInBytes * 8ULL / bitwidth))
174 return *numElements * bitwidth <=
175 static_cast<int64_t>(maximumSizeInBytes * 8ULL);
182 for (
Value alias : aliases) {
183 for (
auto *use : alias.getUsers()) {
187 if (isa<RegionBranchTerminatorOpInterface>(use) &&
188 use->getParentRegion() == parentRegion)
224struct BufferAllocationHoistingStateBase {
226 DominanceInfo *dominators;
229 Block *placementBlock;
232 BufferAllocationHoistingStateBase(DominanceInfo *dominators,
233 Block *placementBlock)
234 : dominators(dominators), placementBlock(placementBlock) {}
238template <
typename StateT>
241 BufferAllocationHoisting(Operation *op)
242 : BufferPlacementTransformationBase(op), dominators(op),
243 postDominators(op), scopeOp(op) {}
247 SmallVector<Value> allocsAndAllocas;
249 allocsAndAllocas.push_back(std::get<0>(entry));
250 scopeOp->walk([&](memref::AllocaOp op) {
251 allocsAndAllocas.push_back(op.getMemref());
254 for (
auto allocValue : allocsAndAllocas) {
255 if (!StateT::shouldHoistOpType(allocValue.getDefiningOp()))
257 Operation *definingOp = allocValue.getDefiningOp();
258 assert(definingOp &&
"No defining op");
262 if (!dominators.isReachableFromEntry(allocValue.getParentBlock()))
265 auto resultAliases = aliases.resolve(allocValue);
267 Block *dominatorBlock =
270 StateT state(&dominators, allocValue.getParentBlock(), resultAliases);
273 Block *dependencyBlock =
nullptr;
277 for (Value depValue : operands) {
278 Block *depBlock = depValue.getParentBlock();
279 if (!dependencyBlock || dominators.dominates(dependencyBlock, depBlock))
280 dependencyBlock = depBlock;
286 Block *placementBlock = findPlacementBlock(
287 state, state.computeUpperBound(dominatorBlock, dependencyBlock));
289 allocValue, placementBlock, liveness);
292 Operation *allocOperation = allocValue.getDefiningOp();
301 Block *findPlacementBlock(StateT &state,
Block *upperBound) {
302 Block *currentBlock = state.placementBlock;
313 (parentBlock = parentOp->
getBlock()) &&
315 dominators.properlyDominates(upperBound, currentBlock))) {
318 if (!dominators.isReachableFromEntry(currentBlock))
327 idom = dominators.getNode(currentBlock)->getIDom();
329 if (idom && dominators.properlyDominates(parentBlock, idom->getBlock())) {
332 currentBlock = idom->getBlock();
333 state.recordMoveToDominator(currentBlock);
337 if (parentOp == scopeOp ||
338 parentOp->
hasTrait<OpTrait::IsIsolatedFromAbove>() ||
340 !state.isLegalPlacement(parentOp))
344 currentBlock = parentBlock;
345 state.recordMoveToParent(currentBlock);
349 return state.placementBlock;
354 DominanceInfo dominators;
358 PostDominanceInfo postDominators;
361 llvm::DenseMap<Value, Block *> placementBlocks;
371struct BufferAllocationHoistingState : BufferAllocationHoistingStateBase {
372 BufferAllocationHoistingState(DominanceInfo *dominators,
373 Block *placementBlock,
375 : BufferAllocationHoistingStateBase(dominators, placementBlock) {}
378 Block *computeUpperBound(
Block *dominatorBlock,
Block *dependencyBlock) {
381 if (!dependencyBlock)
382 return dominatorBlock;
386 return dominators->properlyDominates(dominatorBlock, dependencyBlock)
392 bool isLegalPlacement(Operation *op) {
return !
isLoop(op); }
395 static bool shouldHoistOpType(Operation *op) {
400 void recordMoveToDominator(
Block *block) { placementBlock = block; }
403 void recordMoveToParent(
Block *block) { recordMoveToDominator(block); }
408struct BufferAllocationLoopHoistingState : BufferAllocationHoistingStateBase {
413 Block *aliasDominatorBlock =
nullptr;
415 BufferAllocationLoopHoistingState(
416 DominanceInfo *dominators,
Block *placementBlock,
418 : BufferAllocationHoistingStateBase(dominators, placementBlock),
422 Block *computeUpperBound(
Block *dominatorBlock,
Block *dependencyBlock) {
423 aliasDominatorBlock = dominatorBlock;
426 return dependencyBlock ? dependencyBlock :
nullptr;
430 bool isLegalPlacement(Operation *op) {
433 if (!dominators->dominates(aliasDominatorBlock, op->
getBlock()))
435 auto loop = dyn_cast<scf::WhileOp>(op);
440 static bool shouldHoistOpType(Operation *op) {
446 void recordMoveToDominator(
Block *block) {}
449 void recordMoveToParent(
Block *block) { placementBlock = block; }
459 BufferPlacementPromotion(Operation *op)
460 : BufferPlacementTransformationBase(op) {}
465 Value alloc = std::get<0>(entry);
466 Operation *dealloc = std::get<1>(entry);
471 if (!isSmallAlloc(alloc) || dealloc ||
479 OpBuilder builder(startOperation);
481 if (
auto allocInterface = dyn_cast<AllocationOpInterface>(allocOp)) {
482 std::optional<Operation *> alloca =
483 allocInterface.buildPromotedAlloc(builder, alloc);
500struct BufferHoistingPass
501 :
public bufferization::impl::BufferHoistingPassBase<BufferHoistingPass> {
503 void runOnOperation()
override {
505 BufferAllocationHoisting<BufferAllocationHoistingState> optimizer(
512struct BufferLoopHoistingPass
513 :
public bufferization::impl::BufferLoopHoistingPassBase<
514 BufferLoopHoistingPass> {
516 void runOnOperation()
override {
524class PromoteBuffersToStackPass
525 :
public bufferization::impl::PromoteBuffersToStackPassBase<
526 PromoteBuffersToStackPass> {
530 explicit PromoteBuffersToStackPass(std::function<
bool(Value)> isSmallAlloc)
531 : isSmallAlloc(std::move(isSmallAlloc)) {}
533 LogicalResult
initialize(MLIRContext *context)
override {
534 if (isSmallAlloc ==
nullptr) {
535 isSmallAlloc = [=](Value alloc) {
537 maxRankOfAllocatedMemRef);
543 void runOnOperation()
override {
545 BufferPlacementPromotion optimizer(getOperation());
546 optimizer.promote(isSmallAlloc);
550 std::function<bool(Value)> isSmallAlloc;
556 BufferAllocationHoisting<BufferAllocationLoopHoistingState> optimizer(op);
561 std::function<
bool(
Value)> isSmallAlloc) {
562 return std::make_unique<PromoteBuffersToStackPass>(std::move(isSmallAlloc));
static bool leavesAllocationScope(Region *parentRegion, const BufferViewFlowAnalysis::ValueSetT &aliases)
Checks whether the given aliases leave the allocation scope.
static bool isKnownControlFlowInterface(Operation *op)
Returns true if the given operation implements a known high-level region- based control-flow interfac...
static bool hasAllocationScope(Value alloc, const BufferViewFlowAnalysis &aliasAnalysis)
Checks, if an automated allocation scope for a given alloc value exists.
static bool isSequentialLoop(Operation *op)
Return whether the given operation is a loop with sequential execution semantics.
static bool isLoop(Operation *op)
Returns true if the given operation represents a loop by testing whether it implements the LoopLikeOp...
static bool canHoistFromWhile(scf::WhileOp loop, const BufferViewFlowAnalysis::ValueSetT &aliases)
Returns true if an allocation can be reused across iterations when its aliases have a common dominato...
static bool allowAllocDominateBlockHoisting(Operation *op)
Returns true if the given operation implements the AllocationOpInterface and it supports the dominate...
static bool allowAllocLoopHoisting(Operation *op)
Returns true if the given operation implements the AllocationOpInterface and it supports the loop hoi...
static bool defaultIsSmallAlloc(Value alloc, unsigned maximumSizeInBytes, unsigned maxRankOfAllocatedMemRef)
Check if the size of the allocation is less than the given size.
LogicalResult initialize(unsigned origNumLoops, ArrayRef< ReassociationIndices > foldedIterationDims)
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
A straight-forward alias analysis which ensures that all dependencies of all values will be determine...
SmallPtrSet< Value, 16 > ValueSetT
ValueSetT resolve(Value value) const
Find all immediate and indirect views upon this value.
static DataLayout closest(Operation *op)
Returns the layout of the closest parent operation carrying layout info.
llvm::TypeSize getTypeSizeInBits(Type t) const
Returns the size in bits of the given type in the current scope.
This class represents an operand of an operation.
A trait of region holding operations that define a new scope for automatic allocations,...
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Block * getBlock()
Returns the operation block that contains this operation.
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
operand_range getOperands()
Returns an iterator on the underlying Value's.
void moveBefore(Operation *existingOp)
Unlink this operation from its current block and insert it right before existingOp which may be in th...
void replaceAllUsesWith(ValuesT &&values)
Replace all uses of results of this operation with the provided 'values'.
void erase()
Remove this operation from its parent block and delete it.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
Operation * getParentOp()
Return the parent operation this region is attached to.
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
bool isIntOrFloat() const
Return true if this is an integer (of any signedness) or a float type.
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.
Block * getParentBlock()
Return the Block in which this Value is defined.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Region * getParentRegion()
Return the Region in which this Value is defined.
static Operation * getStartOperation(Value allocValue, Block *placementBlock, const Liveness &liveness)
Get the start operation to place the given alloc value within the specified placement block.
std::tuple< Value, Operation * > AllocEntry
Represents a tuple of allocValue and deallocOperation.
void hoistBuffersFromLoops(Operation *op)
Within the given operation, hoist buffers from loops where possible.
std::unique_ptr< Pass > createPromoteBuffersToStackPass(std::function< bool(Value)> isSmallAlloc)
Creates a pass that promotes heap-based allocations to stack-based ones.
Block * findCommonDominator(Value value, const BufferViewFlowAnalysis::ValueSetT &values, const DominatorT &doms)
Finds a common dominator for the given value while taking the positions of the values in the value se...
LogicalResult promote(RewriterBase &rewriter, scf::ForallOp forallOp)
Promotes the loop body of a scf::ForallOp to its containing block.
Include the generated interface declarations.
llvm::DomTreeNodeBase< Block > DominanceInfoNode
llvm::function_ref< Fn > function_ref