| 1 | //===- BufferOptimizations.cpp - pre-pass optimizations for bufferization -===// |
| 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 | // This file implements logic for three optimization passes. The first two |
| 10 | // passes try to move alloc nodes out of blocks to reduce the number of |
| 11 | // allocations and copies during buffer deallocation. The third pass tries to |
| 12 | // convert heap-based allocations to stack-based allocations, if possible. |
| 13 | |
| 14 | #include "mlir/Dialect/Bufferization/Transforms/Passes.h" |
| 15 | |
| 16 | #include "mlir/Dialect/Bufferization/IR/AllocationOpInterface.h" |
| 17 | #include "mlir/Dialect/Bufferization/Transforms/BufferUtils.h" |
| 18 | #include "mlir/Dialect/Bufferization/Transforms/Transforms.h" |
| 19 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 20 | #include "mlir/Dialect/MemRef/IR/MemRef.h" |
| 21 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 22 | #include "mlir/IR/Operation.h" |
| 23 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 24 | #include "mlir/Interfaces/DataLayoutInterfaces.h" |
| 25 | #include "mlir/Interfaces/LoopLikeInterface.h" |
| 26 | #include "mlir/Pass/Pass.h" |
| 27 | |
| 28 | namespace mlir { |
| 29 | namespace bufferization { |
| 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" |
| 34 | } // namespace bufferization |
| 35 | } // namespace mlir |
| 36 | |
| 37 | using namespace mlir; |
| 38 | using namespace mlir::bufferization; |
| 39 | |
| 40 | /// Returns true if the given operation implements a known high-level region- |
| 41 | /// based control-flow interface. |
| 42 | static bool isKnownControlFlowInterface(Operation *op) { |
| 43 | return isa<LoopLikeOpInterface, RegionBranchOpInterface>(Val: op); |
| 44 | } |
| 45 | |
| 46 | /// Returns true if the given operation represents a loop by testing whether it |
| 47 | /// implements the `LoopLikeOpInterface` or the `RegionBranchOpInterface`. In |
| 48 | /// the case of a `RegionBranchOpInterface`, it checks all region-based control- |
| 49 | /// flow edges for cycles. |
| 50 | static bool isLoop(Operation *op) { |
| 51 | // If the operation implements the `LoopLikeOpInterface` it can be considered |
| 52 | // a loop. |
| 53 | if (isa<LoopLikeOpInterface>(Val: op)) |
| 54 | return true; |
| 55 | |
| 56 | // If the operation does not implement the `RegionBranchOpInterface`, it is |
| 57 | // (currently) not possible to detect a loop. |
| 58 | auto regionInterface = dyn_cast<RegionBranchOpInterface>(Val: op); |
| 59 | if (!regionInterface) |
| 60 | return false; |
| 61 | |
| 62 | return regionInterface.hasLoop(); |
| 63 | } |
| 64 | |
| 65 | /// Return whether the given operation is a loop with sequential execution |
| 66 | /// semantics. |
| 67 | static bool isSequentialLoop(Operation *op) { |
| 68 | return !op->hasTrait<OpTrait::HasParallelRegion>() && isLoop(op); |
| 69 | } |
| 70 | |
| 71 | /// Returns true if an allocation can be reused across iterations when its |
| 72 | /// aliases have a common dominator outside the while loop. |
| 73 | /// `aliases` must contain the complete forward alias set of the allocation. |
| 74 | static bool |
| 75 | canHoistFromWhile(scf::WhileOp loop, |
| 76 | const BufferViewFlowAnalysis::ValueSetT &aliases) { |
| 77 | // Require a parent that stops further loop hoisting. Otherwise, the |
| 78 | // dominator-based path could move the allocation across an enclosing loop |
| 79 | // with unmodeled parallel execution. |
| 80 | if (isSequentialLoop(op: loop->getParentOp())) |
| 81 | return false; |
| 82 | |
| 83 | // Check all aliases, including loop results: memory effects alone do not rule |
| 84 | // out capture or uses that depend on allocation identity or lifetime. |
| 85 | for (Value alias : aliases) { |
| 86 | if (!isa<BaseMemRefType>(Val: alias.getType())) |
| 87 | return false; |
| 88 | for (OpOperand &use : alias.getUses()) { |
| 89 | Operation *user = use.getOwner(); |
| 90 | if (user->getParentOp() != loop && user->getBlock() != loop->getBlock()) |
| 91 | return false; |
| 92 | if (auto load = dyn_cast<memref::LoadOp>(Val: user)) { |
| 93 | // Reusing the allocation across iterations can invalidate invariant |
| 94 | // loads if different iterations store different values to the same |
| 95 | // location. |
| 96 | if (load.getInvariant()) |
| 97 | return false; |
| 98 | continue; |
| 99 | } |
| 100 | if (auto store = dyn_cast<memref::StoreOp>(Val: user)) { |
| 101 | if (store.getMemref() != alias) |
| 102 | return false; |
| 103 | continue; |
| 104 | } |
| 105 | // ViewLikeOpInterface describes aliases but does not guarantee that |
| 106 | // changing allocation identity preserves the view's access semantics. |
| 107 | if (isa<memref::CastOp, memref::SubViewOp>(Val: user)) |
| 108 | continue; |
| 109 | // scf.condition only forwards memrefs to after or to the loop results. |
| 110 | // Reject scf.yield to keep aliases out of the next iteration. |
| 111 | if (user != loop.getConditionOp().getOperation()) |
| 112 | return false; |
| 113 | } |
| 114 | } |
| 115 | return true; |
| 116 | } |
| 117 | |
| 118 | /// Returns true if the given operation implements the AllocationOpInterface |
| 119 | /// and it supports the dominate block hoisting. |
| 120 | static bool allowAllocDominateBlockHoisting(Operation *op) { |
| 121 | auto allocOp = dyn_cast<AllocationOpInterface>(Val: op); |
| 122 | return allocOp && |
| 123 | static_cast<uint8_t>(allocOp.getHoistingKind() & HoistingKind::Block); |
| 124 | } |
| 125 | |
| 126 | /// Returns true if the given operation implements the AllocationOpInterface |
| 127 | /// and it supports the loop hoisting. |
| 128 | static bool allowAllocLoopHoisting(Operation *op) { |
| 129 | auto allocOp = dyn_cast<AllocationOpInterface>(Val: op); |
| 130 | return allocOp && |
| 131 | static_cast<uint8_t>(allocOp.getHoistingKind() & HoistingKind::Loop); |
| 132 | } |
| 133 | |
| 134 | /// Check if the size of the allocation is less than the given size. The |
| 135 | /// transformation is only applied to small buffers since large buffers could |
| 136 | /// exceed the stack space. |
| 137 | static bool defaultIsSmallAlloc(Value alloc, unsigned maximumSizeInBytes, |
| 138 | unsigned maxRankOfAllocatedMemRef) { |
| 139 | auto type = dyn_cast<ShapedType>(Val: alloc.getType()); |
| 140 | if (!type || !alloc.getDefiningOp<memref::AllocOp>()) |
| 141 | return false; |
| 142 | if (!type.hasStaticShape()) { |
| 143 | // Check if the dynamic shape dimension of the alloc is produced by |
| 144 | // `memref.rank`. If this is the case, it is likely to be small. |
| 145 | // Furthermore, the dimension is limited to the maximum rank of the |
| 146 | // allocated memref to avoid large values by multiplying several small |
| 147 | // values. |
| 148 | if (type.getRank() <= maxRankOfAllocatedMemRef) { |
| 149 | return llvm::all_of(Range: alloc.getDefiningOp()->getOperands(), |
| 150 | P: [&](Value operand) { |
| 151 | return operand.getDefiningOp<memref::RankOp>(); |
| 152 | }); |
| 153 | } |
| 154 | return false; |
| 155 | } |
| 156 | // Skip if the element type has no data layout support (e.g., nested memrefs). |
| 157 | Type elemType = type.getElementType(); |
| 158 | if (!elemType.isIntOrFloat() && |
| 159 | !isa<ComplexType, IndexType, VectorType>(Val: elemType) && |
| 160 | !isa<DataLayoutTypeInterface>(Val: elemType)) |
| 161 | return false; |
| 162 | unsigned bitwidth = mlir::DataLayout::closest(op: alloc.getDefiningOp()) |
| 163 | .getTypeSizeInBits(t: elemType); |
| 164 | // Use tryGetNumElements to avoid an assertion on integer overflow (e.g. for |
| 165 | // very large statically-shaped memrefs). If the element count overflows |
| 166 | // int64_t the allocation is certainly not "small", so return false. |
| 167 | std::optional<int64_t> numElements = type.tryGetNumElements(); |
| 168 | if (!numElements) |
| 169 | return false; |
| 170 | // Guard against overflow in the size computation as well. |
| 171 | if (bitwidth != 0 && |
| 172 | *numElements > static_cast<int64_t>(maximumSizeInBytes * 8ULL / bitwidth)) |
| 173 | return false; |
| 174 | return *numElements * bitwidth <= |
| 175 | static_cast<int64_t>(maximumSizeInBytes * 8ULL); |
| 176 | } |
| 177 | |
| 178 | /// Checks whether the given aliases leave the allocation scope. |
| 179 | static bool |
| 180 | leavesAllocationScope(Region *parentRegion, |
| 181 | const BufferViewFlowAnalysis::ValueSetT &aliases) { |
| 182 | for (Value alias : aliases) { |
| 183 | for (auto *use : alias.getUsers()) { |
| 184 | // If there is at least one alias that leaves the parent region, we know |
| 185 | // that this alias escapes the whole region and hence the associated |
| 186 | // allocation leaves allocation scope. |
| 187 | if (isa<RegionBranchTerminatorOpInterface>(Val: use) && |
| 188 | use->getParentRegion() == parentRegion) |
| 189 | return true; |
| 190 | } |
| 191 | } |
| 192 | return false; |
| 193 | } |
| 194 | |
| 195 | /// Checks, if an automated allocation scope for a given alloc value exists. |
| 196 | static bool hasAllocationScope(Value alloc, |
| 197 | const BufferViewFlowAnalysis &aliasAnalysis) { |
| 198 | Region *region = alloc.getParentRegion(); |
| 199 | do { |
| 200 | if (Operation *parentOp = region->getParentOp()) { |
| 201 | // Check if the operation is an automatic allocation scope and whether an |
| 202 | // alias leaves the scope. This means, an allocation yields out of |
| 203 | // this scope and can not be transformed in a stack-based allocation. |
| 204 | if (parentOp->hasTrait<OpTrait::AutomaticAllocationScope>() && |
| 205 | !leavesAllocationScope(parentRegion: region, aliases: aliasAnalysis.resolve(value: alloc))) |
| 206 | return true; |
| 207 | // Check if the operation is a known control flow interface and break the |
| 208 | // loop to avoid transformation in loops. Furthermore skip transformation |
| 209 | // if the operation does not implement a RegionBeanchOpInterface. |
| 210 | if (isLoop(op: parentOp) || !isKnownControlFlowInterface(op: parentOp)) |
| 211 | break; |
| 212 | } |
| 213 | } while ((region = region->getParentRegion())); |
| 214 | return false; |
| 215 | } |
| 216 | |
| 217 | namespace { |
| 218 | |
| 219 | //===----------------------------------------------------------------------===// |
| 220 | // BufferAllocationHoisting |
| 221 | //===----------------------------------------------------------------------===// |
| 222 | |
| 223 | /// A base implementation compatible with the `BufferAllocationHoisting` class. |
| 224 | struct BufferAllocationHoistingStateBase { |
| 225 | /// A pointer to the current dominance info. |
| 226 | DominanceInfo *dominators; |
| 227 | |
| 228 | /// The current placement block (if any). |
| 229 | Block *placementBlock; |
| 230 | |
| 231 | /// Initializes the state base. |
| 232 | BufferAllocationHoistingStateBase(DominanceInfo *dominators, |
| 233 | Block *placementBlock) |
| 234 | : dominators(dominators), placementBlock(placementBlock) {} |
| 235 | }; |
| 236 | |
| 237 | /// Implements the actual hoisting logic for allocation nodes. |
| 238 | template <typename StateT> |
| 239 | class BufferAllocationHoisting : public BufferPlacementTransformationBase { |
| 240 | public: |
| 241 | BufferAllocationHoisting(Operation *op) |
| 242 | : BufferPlacementTransformationBase(op), dominators(op), |
| 243 | postDominators(op), scopeOp(op) {} |
| 244 | |
| 245 | /// Moves allocations upwards. |
| 246 | void hoist() { |
| 247 | SmallVector<Value> allocsAndAllocas; |
| 248 | for (BufferPlacementAllocs::AllocEntry &entry : allocs) |
| 249 | allocsAndAllocas.push_back(Elt: std::get<0>(t&: entry)); |
| 250 | scopeOp->walk([&](memref::AllocaOp op) { |
| 251 | allocsAndAllocas.push_back(Elt: op.getMemref()); |
| 252 | }); |
| 253 | |
| 254 | for (auto allocValue : allocsAndAllocas) { |
| 255 | if (!StateT::shouldHoistOpType(allocValue.getDefiningOp())) |
| 256 | continue; |
| 257 | Operation *definingOp = allocValue.getDefiningOp(); |
| 258 | assert(definingOp && "No defining op" ); |
| 259 | // Skip allocations in blocks that are not reachable from the function |
| 260 | // entry. Such blocks are dead code and the dominator tree analysis may |
| 261 | // not have nodes for them, which would cause crashes below. |
| 262 | if (!dominators.isReachableFromEntry(a: allocValue.getParentBlock())) |
| 263 | continue; |
| 264 | auto operands = definingOp->getOperands(); |
| 265 | auto resultAliases = aliases.resolve(value: allocValue); |
| 266 | // Determine the common dominator block of all aliases. |
| 267 | Block *dominatorBlock = |
| 268 | findCommonDominator(allocValue, resultAliases, dominators); |
| 269 | // Init the initial hoisting state. |
| 270 | StateT state(&dominators, allocValue.getParentBlock(), resultAliases); |
| 271 | // Check for additional allocation dependencies to compute an upper bound |
| 272 | // for hoisting. |
| 273 | Block *dependencyBlock = nullptr; |
| 274 | // If this node has dependencies, check all dependent nodes. This ensures |
| 275 | // that all dependency values have been computed before allocating the |
| 276 | // buffer. |
| 277 | for (Value depValue : operands) { |
| 278 | Block *depBlock = depValue.getParentBlock(); |
| 279 | if (!dependencyBlock || dominators.dominates(a: dependencyBlock, b: depBlock)) |
| 280 | dependencyBlock = depBlock; |
| 281 | } |
| 282 | |
| 283 | // Find the actual placement block and determine the start operation using |
| 284 | // an upper placement-block boundary. The idea is that placement block |
| 285 | // cannot be moved any further upwards than the given upper bound. |
| 286 | Block *placementBlock = findPlacementBlock( |
| 287 | state, upperBound: state.computeUpperBound(dominatorBlock, dependencyBlock)); |
| 288 | Operation *startOperation = BufferPlacementAllocs::getStartOperation( |
| 289 | allocValue, placementBlock, liveness); |
| 290 | |
| 291 | // Move the alloc in front of the start operation. |
| 292 | Operation *allocOperation = allocValue.getDefiningOp(); |
| 293 | allocOperation->moveBefore(existingOp: startOperation); |
| 294 | } |
| 295 | } |
| 296 | |
| 297 | private: |
| 298 | /// Finds a valid placement block by walking upwards in the CFG until we |
| 299 | /// either cannot continue our walk due to constraints (given by the StateT |
| 300 | /// implementation) or we have reached the upper-most dominator block. |
| 301 | Block *findPlacementBlock(StateT &state, Block *upperBound) { |
| 302 | Block *currentBlock = state.placementBlock; |
| 303 | // Walk from the innermost regions/loops to the outermost regions/loops and |
| 304 | // find an appropriate placement block that satisfies the constraint of the |
| 305 | // current StateT implementation. Walk until we reach the upperBound block |
| 306 | // (if any). |
| 307 | |
| 308 | // If we are not able to find a valid parent operation or an associated |
| 309 | // parent block, break the walk loop. |
| 310 | Operation *parentOp; |
| 311 | Block *parentBlock; |
| 312 | while ((parentOp = currentBlock->getParentOp()) && |
| 313 | (parentBlock = parentOp->getBlock()) && |
| 314 | (!upperBound || |
| 315 | dominators.properlyDominates(a: upperBound, b: currentBlock))) { |
| 316 | // A reachable nested region may have an unreachable enclosing block, |
| 317 | // which has no node in the dominator tree. |
| 318 | if (!dominators.isReachableFromEntry(a: currentBlock)) |
| 319 | break; |
| 320 | |
| 321 | // Try to find an immediate dominator and check whether the parent block |
| 322 | // is above the immediate dominator (if any). |
| 323 | DominanceInfoNode *idom = nullptr; |
| 324 | |
| 325 | // DominanceInfo doesn't support getNode queries for single-block regions. |
| 326 | if (!currentBlock->isEntryBlock()) |
| 327 | idom = dominators.getNode(a: currentBlock)->getIDom(); |
| 328 | |
| 329 | if (idom && dominators.properlyDominates(a: parentBlock, b: idom->getBlock())) { |
| 330 | // If the current immediate dominator is below the placement block, move |
| 331 | // to the immediate dominator block. |
| 332 | currentBlock = idom->getBlock(); |
| 333 | state.recordMoveToDominator(currentBlock); |
| 334 | } else { |
| 335 | // The target's parent block is outside the liveness analysis. Keep |
| 336 | // allocations within the target and preserve isolation boundaries. |
| 337 | if (parentOp == scopeOp || |
| 338 | parentOp->hasTrait<OpTrait::IsIsolatedFromAbove>() || |
| 339 | !isKnownControlFlowInterface(op: parentOp) || |
| 340 | !state.isLegalPlacement(parentOp)) |
| 341 | break; |
| 342 | // Move to our parent block by notifying the current StateT |
| 343 | // implementation. |
| 344 | currentBlock = parentBlock; |
| 345 | state.recordMoveToParent(currentBlock); |
| 346 | } |
| 347 | } |
| 348 | // Return the finally determined placement block. |
| 349 | return state.placementBlock; |
| 350 | } |
| 351 | |
| 352 | /// The dominator info to find the appropriate start operation to move the |
| 353 | /// allocs. |
| 354 | DominanceInfo dominators; |
| 355 | |
| 356 | /// The post dominator info to move the dependent allocs in the right |
| 357 | /// position. |
| 358 | PostDominanceInfo postDominators; |
| 359 | |
| 360 | /// The operation that this transformation is working on. It is used to also |
| 361 | /// gather allocas. |
| 362 | Operation *scopeOp; |
| 363 | }; |
| 364 | |
| 365 | /// A state implementation compatible with the `BufferAllocationHoisting` class |
| 366 | /// that hoists allocations into dominator blocks while keeping them inside of |
| 367 | /// loops. |
| 368 | struct BufferAllocationHoistingState : BufferAllocationHoistingStateBase { |
| 369 | BufferAllocationHoistingState(DominanceInfo *dominators, |
| 370 | Block *placementBlock, |
| 371 | const BufferViewFlowAnalysis::ValueSetT &) |
| 372 | : BufferAllocationHoistingStateBase(dominators, placementBlock) {} |
| 373 | |
| 374 | /// Computes the upper bound for the placement block search. |
| 375 | Block *computeUpperBound(Block *dominatorBlock, Block *dependencyBlock) { |
| 376 | // If we do not have a dependency block, the upper bound is given by the |
| 377 | // dominator block. |
| 378 | if (!dependencyBlock) |
| 379 | return dominatorBlock; |
| 380 | |
| 381 | // Find the "lower" block of the dominator and the dependency block to |
| 382 | // ensure that we do not move allocations above this block. |
| 383 | return dominators->properlyDominates(a: dominatorBlock, b: dependencyBlock) |
| 384 | ? dependencyBlock |
| 385 | : dominatorBlock; |
| 386 | } |
| 387 | |
| 388 | /// Returns true if the given operation does not represent a loop. |
| 389 | bool isLegalPlacement(Operation *op) { return !isLoop(op); } |
| 390 | |
| 391 | /// Returns true if the given operation should be considered for hoisting. |
| 392 | static bool shouldHoistOpType(Operation *op) { |
| 393 | return allowAllocDominateBlockHoisting(op); |
| 394 | } |
| 395 | |
| 396 | /// Sets the current placement block to the given block. |
| 397 | void recordMoveToDominator(Block *block) { placementBlock = block; } |
| 398 | |
| 399 | /// Sets the current placement block to the given block. |
| 400 | void recordMoveToParent(Block *block) { recordMoveToDominator(block); } |
| 401 | }; |
| 402 | |
| 403 | /// A state implementation compatible with the `BufferAllocationHoisting` class |
| 404 | /// that hoists allocations out of loops. |
| 405 | struct BufferAllocationLoopHoistingState : BufferAllocationHoistingStateBase { |
| 406 | /// The forward alias closure of the current allocation. |
| 407 | const BufferViewFlowAnalysis::ValueSetT &aliases; |
| 408 | |
| 409 | /// Remembers the dominator block of all aliases. |
| 410 | Block *aliasDominatorBlock = nullptr; |
| 411 | |
| 412 | BufferAllocationLoopHoistingState( |
| 413 | DominanceInfo *dominators, Block *placementBlock, |
| 414 | const BufferViewFlowAnalysis::ValueSetT &aliases) |
| 415 | : BufferAllocationHoistingStateBase(dominators, placementBlock), |
| 416 | aliases(aliases) {} |
| 417 | |
| 418 | /// Computes the upper bound for the placement block search. |
| 419 | Block *computeUpperBound(Block *dominatorBlock, Block *dependencyBlock) { |
| 420 | aliasDominatorBlock = dominatorBlock; |
| 421 | // If there is a dependency block, we have to use this block as an upper |
| 422 | // bound to satisfy all allocation value dependencies. |
| 423 | return dependencyBlock ? dependencyBlock : nullptr; |
| 424 | } |
| 425 | |
| 426 | /// Returns true if the allocation can be moved across the given loop. |
| 427 | bool isLegalPlacement(Operation *op) { |
| 428 | if (!isSequentialLoop(op)) |
| 429 | return false; |
| 430 | if (!dominators->dominates(a: aliasDominatorBlock, b: op->getBlock())) |
| 431 | return true; |
| 432 | auto loop = dyn_cast<scf::WhileOp>(Val: op); |
| 433 | return loop && canHoistFromWhile(loop, aliases); |
| 434 | } |
| 435 | |
| 436 | /// Returns true if the given operation should be considered for hoisting. |
| 437 | static bool shouldHoistOpType(Operation *op) { |
| 438 | return allowAllocLoopHoisting(op); |
| 439 | } |
| 440 | |
| 441 | /// Does not change the internal placement block, as we want to move |
| 442 | /// operations out of loops only. |
| 443 | void recordMoveToDominator(Block *block) {} |
| 444 | |
| 445 | /// Sets the current placement block to the given block. |
| 446 | void recordMoveToParent(Block *block) { placementBlock = block; } |
| 447 | }; |
| 448 | |
| 449 | //===----------------------------------------------------------------------===// |
| 450 | // BufferPlacementPromotion |
| 451 | //===----------------------------------------------------------------------===// |
| 452 | |
| 453 | /// Promotes heap-based allocations to stack-based allocations (if possible). |
| 454 | class BufferPlacementPromotion : BufferPlacementTransformationBase { |
| 455 | public: |
| 456 | BufferPlacementPromotion(Operation *op) |
| 457 | : BufferPlacementTransformationBase(op) {} |
| 458 | |
| 459 | /// Promote buffers to stack-based allocations. |
| 460 | void promote(function_ref<bool(Value)> isSmallAlloc) { |
| 461 | for (BufferPlacementAllocs::AllocEntry &entry : allocs) { |
| 462 | Value alloc = std::get<0>(t&: entry); |
| 463 | Operation *dealloc = std::get<1>(t&: entry); |
| 464 | // Checking several requirements to transform an AllocOp into an AllocaOp. |
| 465 | // The transformation is done if the allocation is limited to a given |
| 466 | // size. Furthermore, a deallocation must not be defined for this |
| 467 | // allocation entry and a parent allocation scope must exist. |
| 468 | if (!isSmallAlloc(alloc) || dealloc || |
| 469 | !hasAllocationScope(alloc, aliasAnalysis: aliases)) |
| 470 | continue; |
| 471 | |
| 472 | Operation *startOperation = BufferPlacementAllocs::getStartOperation( |
| 473 | allocValue: alloc, placementBlock: alloc.getParentBlock(), liveness); |
| 474 | // Build a new alloca that is associated with its parent |
| 475 | // `AutomaticAllocationScope` determined during the initialization phase. |
| 476 | OpBuilder builder(startOperation); |
| 477 | Operation *allocOp = alloc.getDefiningOp(); |
| 478 | if (auto allocInterface = dyn_cast<AllocationOpInterface>(Val: allocOp)) { |
| 479 | std::optional<Operation *> alloca = |
| 480 | allocInterface.buildPromotedAlloc(builder, alloc); |
| 481 | if (!alloca) |
| 482 | continue; |
| 483 | // Replace the original alloc by a newly created alloca. |
| 484 | allocOp->replaceAllUsesWith(values&: alloca.value()); |
| 485 | allocOp->erase(); |
| 486 | } |
| 487 | } |
| 488 | } |
| 489 | }; |
| 490 | |
| 491 | //===----------------------------------------------------------------------===// |
| 492 | // BufferOptimizationPasses |
| 493 | //===----------------------------------------------------------------------===// |
| 494 | |
| 495 | /// The buffer hoisting pass that hoists allocation nodes into dominating |
| 496 | /// blocks. |
| 497 | struct BufferHoistingPass |
| 498 | : public bufferization::impl::BufferHoistingPassBase<BufferHoistingPass> { |
| 499 | |
| 500 | void runOnOperation() override { |
| 501 | // Hoist all allocations into dominator blocks. |
| 502 | BufferAllocationHoisting<BufferAllocationHoistingState> optimizer( |
| 503 | getOperation()); |
| 504 | optimizer.hoist(); |
| 505 | } |
| 506 | }; |
| 507 | |
| 508 | /// The buffer loop hoisting pass that hoists allocation nodes out of loops. |
| 509 | struct BufferLoopHoistingPass |
| 510 | : public bufferization::impl::BufferLoopHoistingPassBase< |
| 511 | BufferLoopHoistingPass> { |
| 512 | |
| 513 | void runOnOperation() override { |
| 514 | // Hoist all allocations out of loops. |
| 515 | hoistBuffersFromLoops(op: getOperation()); |
| 516 | } |
| 517 | }; |
| 518 | |
| 519 | /// The promote buffer to stack pass that tries to convert alloc nodes into |
| 520 | /// alloca nodes. |
| 521 | class PromoteBuffersToStackPass |
| 522 | : public bufferization::impl::PromoteBuffersToStackPassBase< |
| 523 | PromoteBuffersToStackPass> { |
| 524 | using Base::Base; |
| 525 | |
| 526 | public: |
| 527 | explicit PromoteBuffersToStackPass(std::function<bool(Value)> isSmallAlloc) |
| 528 | : isSmallAlloc(std::move(isSmallAlloc)) {} |
| 529 | |
| 530 | LogicalResult initialize(MLIRContext *context) override { |
| 531 | if (isSmallAlloc == nullptr) { |
| 532 | isSmallAlloc = [=](Value alloc) { |
| 533 | return defaultIsSmallAlloc(alloc, maximumSizeInBytes: maxAllocSizeInBytes, |
| 534 | maxRankOfAllocatedMemRef); |
| 535 | }; |
| 536 | } |
| 537 | return success(); |
| 538 | } |
| 539 | |
| 540 | void runOnOperation() override { |
| 541 | // Move all allocation nodes and convert candidates into allocas. |
| 542 | BufferPlacementPromotion optimizer(getOperation()); |
| 543 | optimizer.promote(isSmallAlloc); |
| 544 | } |
| 545 | |
| 546 | private: |
| 547 | std::function<bool(Value)> isSmallAlloc; |
| 548 | }; |
| 549 | |
| 550 | } // namespace |
| 551 | |
| 552 | void mlir::bufferization::hoistBuffersFromLoops(Operation *op) { |
| 553 | BufferAllocationHoisting<BufferAllocationLoopHoistingState> optimizer(op); |
| 554 | optimizer.hoist(); |
| 555 | } |
| 556 | |
| 557 | std::unique_ptr<Pass> mlir::bufferization::createPromoteBuffersToStackPass( |
| 558 | std::function<bool(Value)> isSmallAlloc) { |
| 559 | return std::make_unique<PromoteBuffersToStackPass>(args: std::move(isSmallAlloc)); |
| 560 | } |
| 561 | |