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
28namespace mlir {
29namespace 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
37using namespace mlir;
38using namespace mlir::bufferization;
39
40/// Returns true if the given operation implements a known high-level region-
41/// based control-flow interface.
42static 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.
50static 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.
67static 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.
74static bool
75canHoistFromWhile(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.
120static 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.
128static 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.
137static 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.
179static bool
180leavesAllocationScope(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.
196static 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
217namespace {
218
219//===----------------------------------------------------------------------===//
220// BufferAllocationHoisting
221//===----------------------------------------------------------------------===//
222
223/// A base implementation compatible with the `BufferAllocationHoisting` class.
224struct 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.
238template <typename StateT>
239class BufferAllocationHoisting : public BufferPlacementTransformationBase {
240public:
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
297private:
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.
368struct 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.
405struct 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).
454class BufferPlacementPromotion : BufferPlacementTransformationBase {
455public:
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.
497struct 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.
509struct 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.
521class PromoteBuffersToStackPass
522 : public bufferization::impl::PromoteBuffersToStackPassBase<
523 PromoteBuffersToStackPass> {
524 using Base::Base;
525
526public:
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
546private:
547 std::function<bool(Value)> isSmallAlloc;
548};
549
550} // namespace
551
552void mlir::bufferization::hoistBuffersFromLoops(Operation *op) {
553 BufferAllocationHoisting<BufferAllocationLoopHoistingState> optimizer(op);
554 optimizer.hoist();
555}
556
557std::unique_ptr<Pass> mlir::bufferization::createPromoteBuffersToStackPass(
558 std::function<bool(Value)> isSmallAlloc) {
559 return std::make_unique<PromoteBuffersToStackPass>(args: std::move(isSmallAlloc));
560}
561