MLIR  16.0.0git
BufferDeallocation.cpp
Go to the documentation of this file.
1 //===- BufferDeallocation.cpp - the impl for buffer deallocation ----------===//
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 computing correct alloc and dealloc positions.
10 // Furthermore, buffer deallocation also adds required new clone operations to
11 // ensure that all buffers are deallocated. The main class is the
12 // BufferDeallocationPass class that implements the underlying algorithm. In
13 // order to put allocations and deallocations at safe positions, it is
14 // significantly important to put them into the correct blocks. However, the
15 // liveness analysis does not pay attention to aliases, which can occur due to
16 // branches (and their associated block arguments) in general. For this purpose,
17 // BufferDeallocation firstly finds all possible aliases for a single value
18 // (using the BufferViewFlowAnalysis class). Consider the following example:
19 //
20 // ^bb0(%arg0):
21 // cf.cond_br %cond, ^bb1, ^bb2
22 // ^bb1:
23 // cf.br ^exit(%arg0)
24 // ^bb2:
25 // %new_value = ...
26 // cf.br ^exit(%new_value)
27 // ^exit(%arg1):
28 // return %arg1;
29 //
30 // We should place the dealloc for %new_value in exit. However, we have to free
31 // the buffer in the same block, because it cannot be freed in the post
32 // dominator. However, this requires a new clone buffer for %arg1 that will
33 // contain the actual contents. Using the class BufferViewFlowAnalysis, we
34 // will find out that %new_value has a potential alias %arg1. In order to find
35 // the dealloc position we have to find all potential aliases, iterate over
36 // their uses and find the common post-dominator block (note that additional
37 // clones and buffers remove potential aliases and will influence the placement
38 // of the deallocs). In all cases, the computed block can be safely used to free
39 // the %new_value buffer (may be exit or bb2) as it will die and we can use
40 // liveness information to determine the exact operation after which we have to
41 // insert the dealloc. However, the algorithm supports introducing clone buffers
42 // and placing deallocs in safe locations to ensure that all buffers will be
43 // freed in the end.
44 //
45 // TODO:
46 // The current implementation does not support explicit-control-flow loops and
47 // the resulting code will be invalid with respect to program semantics.
48 // However, structured control-flow loops are fully supported. Furthermore, it
49 // doesn't accept functions which return buffers already.
50 //
51 //===----------------------------------------------------------------------===//
52 
54 
60 #include "llvm/ADT/SetOperations.h"
61 
62 namespace mlir {
63 namespace bufferization {
64 #define GEN_PASS_DEF_BUFFERDEALLOCATION
65 #include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
66 } // namespace bufferization
67 } // namespace mlir
68 
69 using namespace mlir;
70 using namespace mlir::bufferization;
71 
72 /// Walks over all immediate return-like terminators in the given region.
73 static LogicalResult
76  for (Block &block : *region) {
77  Operation *terminator = block.getTerminator();
78  // Skip non region-return-like terminators.
79  if (isRegionReturnLike(terminator)) {
80  if (failed(func(terminator)))
81  return failure();
82  }
83  }
84  return success();
85 }
86 
87 /// Checks if all operations that have at least one attached region implement
88 /// the RegionBranchOpInterface. This is not required in edge cases, where we
89 /// have a single attached region and the parent operation has no results.
91  WalkResult result = op->walk([&](Operation *operation) {
92  // Only check ops that are inside a function.
93  if (!operation->getParentOfType<func::FuncOp>())
94  return WalkResult::advance();
95 
96  auto regions = operation->getRegions();
97  // Walk over all operations in a region and check if the operation has at
98  // least one region and implements the RegionBranchOpInterface. If there
99  // is an operation that does not fulfill this condition, we cannot apply
100  // the deallocation steps. Furthermore, we accept cases, where we have a
101  // region that returns no results, since, in that case, the intra-region
102  // control flow does not affect the transformation.
103  size_t size = regions.size();
104  if (((size == 1 && !operation->getResults().empty()) || size > 1) &&
105  !dyn_cast<RegionBranchOpInterface>(operation)) {
106  operation->emitError("All operations with attached regions need to "
107  "implement the RegionBranchOpInterface.");
108  }
109 
110  return WalkResult::advance();
111  });
112  return !result.wasSkipped();
113 }
114 
115 namespace {
116 
117 //===----------------------------------------------------------------------===//
118 // Backedges analysis
119 //===----------------------------------------------------------------------===//
120 
121 /// A straight-forward program analysis which detects loop backedges induced by
122 /// explicit control flow.
123 class Backedges {
124 public:
125  using BlockSetT = SmallPtrSet<Block *, 16>;
126  using BackedgeSetT = llvm::DenseSet<std::pair<Block *, Block *>>;
127 
128 public:
129  /// Constructs a new backedges analysis using the op provided.
130  Backedges(Operation *op) { recurse(op); }
131 
132  /// Returns the number of backedges formed by explicit control flow.
133  size_t size() const { return edgeSet.size(); }
134 
135  /// Returns the start iterator to loop over all backedges.
136  BackedgeSetT::const_iterator begin() const { return edgeSet.begin(); }
137 
138  /// Returns the end iterator to loop over all backedges.
139  BackedgeSetT::const_iterator end() const { return edgeSet.end(); }
140 
141 private:
142  /// Enters the current block and inserts a backedge into the `edgeSet` if we
143  /// have already visited the current block. The inserted edge links the given
144  /// `predecessor` with the `current` block.
145  bool enter(Block &current, Block *predecessor) {
146  bool inserted = visited.insert(&current).second;
147  if (!inserted)
148  edgeSet.insert(std::make_pair(predecessor, &current));
149  return inserted;
150  }
151 
152  /// Leaves the current block.
153  void exit(Block &current) { visited.erase(&current); }
154 
155  /// Recurses into the given operation while taking all attached regions into
156  /// account.
157  void recurse(Operation *op) {
158  Block *current = op->getBlock();
159  // If the current op implements the `BranchOpInterface`, there can be
160  // cycles in the scope of all successor blocks.
161  if (isa<BranchOpInterface>(op)) {
162  for (Block *succ : current->getSuccessors())
163  recurse(*succ, current);
164  }
165  // Recurse into all distinct regions and check for explicit control-flow
166  // loops.
167  for (Region &region : op->getRegions()) {
168  if (!region.empty())
169  recurse(region.front(), current);
170  }
171  }
172 
173  /// Recurses into explicit control-flow structures that are given by
174  /// the successor relation defined on the block level.
175  void recurse(Block &block, Block *predecessor) {
176  // Try to enter the current block. If this is not possible, we are
177  // currently processing this block and can safely return here.
178  if (!enter(block, predecessor))
179  return;
180 
181  // Recurse into all operations and successor blocks.
182  for (Operation &op : block.getOperations())
183  recurse(&op);
184 
185  // Leave the current block.
186  exit(block);
187  }
188 
189  /// Stores all blocks that are currently visited and on the processing stack.
190  BlockSetT visited;
191 
192  /// Stores all backedges in the format (source, target).
193  BackedgeSetT edgeSet;
194 };
195 
196 //===----------------------------------------------------------------------===//
197 // BufferDeallocation
198 //===----------------------------------------------------------------------===//
199 
200 /// The buffer deallocation transformation which ensures that all allocs in the
201 /// program have a corresponding de-allocation. As a side-effect, it might also
202 /// introduce clones that in turn leads to additional deallocations.
203 class BufferDeallocation : public BufferPlacementTransformationBase {
204 public:
205  using AliasAllocationMapT =
207 
208  BufferDeallocation(Operation *op)
209  : BufferPlacementTransformationBase(op), dominators(op),
210  postDominators(op) {}
211 
212  /// Checks if all allocation operations either provide an already existing
213  /// deallocation operation or implement the AllocationOpInterface. In
214  /// addition, this method initializes the internal alias to
215  /// AllocationOpInterface mapping in order to get compatible
216  /// AllocationOpInterface implementations for aliases.
217  LogicalResult prepare() {
218  for (const BufferPlacementAllocs::AllocEntry &entry : allocs) {
219  // Get the defining allocation operation.
220  Value alloc = std::get<0>(entry);
221  auto allocationInterface =
222  alloc.getDefiningOp<bufferization::AllocationOpInterface>();
223  // If there is no existing deallocation operation and no implementation of
224  // the AllocationOpInterface, we cannot apply the BufferDeallocation pass.
225  if (!std::get<1>(entry) && !allocationInterface) {
226  return alloc.getDefiningOp()->emitError(
227  "Allocation is not deallocated explicitly nor does the operation "
228  "implement the AllocationOpInterface.");
229  }
230 
231  // Register the current allocation interface implementation.
232  aliasToAllocations[alloc] = allocationInterface;
233 
234  // Get the alias information for the current allocation node.
235  for (Value alias : aliases.resolve(alloc)) {
236  // TODO: check for incompatible implementations of the
237  // AllocationOpInterface. This could be realized by promoting the
238  // AllocationOpInterface to a DialectInterface.
239  aliasToAllocations[alias] = allocationInterface;
240  }
241  }
242  return success();
243  }
244 
245  /// Performs the actual placement/creation of all temporary clone and dealloc
246  /// nodes.
247  LogicalResult deallocate() {
248  // Add additional clones that are required.
249  if (failed(introduceClones()))
250  return failure();
251 
252  // Place deallocations for all allocation entries.
253  return placeDeallocs();
254  }
255 
256 private:
257  /// Introduces required clone operations to avoid memory leaks.
258  LogicalResult introduceClones() {
259  // Initialize the set of values that require a dedicated memory free
260  // operation since their operands cannot be safely deallocated in a post
261  // dominator.
262  SmallPtrSet<Value, 8> valuesToFree;
263  llvm::SmallDenseSet<std::tuple<Value, Block *>> visitedValues;
265 
266  // Check dominance relation for proper dominance properties. If the given
267  // value node does not dominate an alias, we will have to create a clone in
268  // order to free all buffers that can potentially leak into a post
269  // dominator.
270  auto findUnsafeValues = [&](Value source, Block *definingBlock) {
271  auto it = aliases.find(source);
272  if (it == aliases.end())
273  return;
274  for (Value value : it->second) {
275  if (valuesToFree.count(value) > 0)
276  continue;
277  Block *parentBlock = value.getParentBlock();
278  // Check whether we have to free this particular block argument or
279  // generic value. We have to free the current alias if it is either
280  // defined in a non-dominated block or it is defined in the same block
281  // but the current value is not dominated by the source value.
282  if (!dominators.dominates(definingBlock, parentBlock) ||
283  (definingBlock == parentBlock && value.isa<BlockArgument>())) {
284  toProcess.emplace_back(value, parentBlock);
285  valuesToFree.insert(value);
286  } else if (visitedValues.insert(std::make_tuple(value, definingBlock))
287  .second)
288  toProcess.emplace_back(value, definingBlock);
289  }
290  };
291 
292  // Detect possibly unsafe aliases starting from all allocations.
293  for (BufferPlacementAllocs::AllocEntry &entry : allocs) {
294  Value allocValue = std::get<0>(entry);
295  findUnsafeValues(allocValue, allocValue.getDefiningOp()->getBlock());
296  }
297  // Try to find block arguments that require an explicit free operation
298  // until we reach a fix point.
299  while (!toProcess.empty()) {
300  auto current = toProcess.pop_back_val();
301  findUnsafeValues(std::get<0>(current), std::get<1>(current));
302  }
303 
304  // Update buffer aliases to ensure that we free all buffers and block
305  // arguments at the correct locations.
306  aliases.remove(valuesToFree);
307 
308  // Add new allocs and additional clone operations.
309  for (Value value : valuesToFree) {
310  if (failed(value.isa<BlockArgument>()
311  ? introduceBlockArgCopy(value.cast<BlockArgument>())
312  : introduceValueCopyForRegionResult(value)))
313  return failure();
314 
315  // Register the value to require a final dealloc. Note that we do not have
316  // to assign a block here since we do not want to move the allocation node
317  // to another location.
318  allocs.registerAlloc(std::make_tuple(value, nullptr));
319  }
320  return success();
321  }
322 
323  /// Introduces temporary clones in all predecessors and copies the source
324  /// values into the newly allocated buffers.
325  LogicalResult introduceBlockArgCopy(BlockArgument blockArg) {
326  // Allocate a buffer for the current block argument in the block of
327  // the associated value (which will be a predecessor block by
328  // definition).
329  Block *block = blockArg.getOwner();
330  for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
331  // Get the terminator and the value that will be passed to our
332  // argument.
333  Operation *terminator = (*it)->getTerminator();
334  auto branchInterface = cast<BranchOpInterface>(terminator);
335  SuccessorOperands operands =
336  branchInterface.getSuccessorOperands(it.getSuccessorIndex());
337 
338  // Query the associated source value.
339  Value sourceValue = operands[blockArg.getArgNumber()];
340  if (!sourceValue) {
341  return failure();
342  }
343  // Wire new clone and successor operand.
344  // Create a new clone at the current location of the terminator.
345  auto clone = introduceCloneBuffers(sourceValue, terminator);
346  if (failed(clone))
347  return failure();
348  operands.slice(blockArg.getArgNumber(), 1).assign(*clone);
349  }
350 
351  // Check whether the block argument has implicitly defined predecessors via
352  // the RegionBranchOpInterface. This can be the case if the current block
353  // argument belongs to the first block in a region and the parent operation
354  // implements the RegionBranchOpInterface.
355  Region *argRegion = block->getParent();
356  Operation *parentOp = argRegion->getParentOp();
357  RegionBranchOpInterface regionInterface;
358  if (&argRegion->front() != block ||
359  !(regionInterface = dyn_cast<RegionBranchOpInterface>(parentOp)))
360  return success();
361 
362  if (failed(introduceClonesForRegionSuccessors(
363  regionInterface, argRegion->getParentOp()->getRegions(), blockArg,
364  [&](RegionSuccessor &successorRegion) {
365  // Find a predecessor of our argRegion.
366  return successorRegion.getSuccessor() == argRegion;
367  })))
368  return failure();
369 
370  // Check whether the block argument belongs to an entry region of the
371  // parent operation. In this case, we have to introduce an additional clone
372  // for buffer that is passed to the argument.
373  SmallVector<RegionSuccessor, 2> successorRegions;
374  regionInterface.getSuccessorRegions(/*index=*/llvm::None, successorRegions);
375  auto *it =
376  llvm::find_if(successorRegions, [&](RegionSuccessor &successorRegion) {
377  return successorRegion.getSuccessor() == argRegion;
378  });
379  if (it == successorRegions.end())
380  return success();
381 
382  // Determine the actual operand to introduce a clone for and rewire the
383  // operand to point to the clone instead.
384  auto operands =
385  regionInterface.getSuccessorEntryOperands(argRegion->getRegionNumber());
386  size_t operandIndex =
387  llvm::find(it->getSuccessorInputs(), blockArg).getIndex() +
388  operands.getBeginOperandIndex();
389  Value operand = parentOp->getOperand(operandIndex);
390  assert(operand ==
391  operands[operandIndex - operands.getBeginOperandIndex()] &&
392  "region interface operands don't match parentOp operands");
393  auto clone = introduceCloneBuffers(operand, parentOp);
394  if (failed(clone))
395  return failure();
396 
397  parentOp->setOperand(operandIndex, *clone);
398  return success();
399  }
400 
401  /// Introduces temporary clones in front of all associated nested-region
402  /// terminators and copies the source values into the newly allocated buffers.
403  LogicalResult introduceValueCopyForRegionResult(Value value) {
404  // Get the actual result index in the scope of the parent terminator.
405  Operation *operation = value.getDefiningOp();
406  auto regionInterface = cast<RegionBranchOpInterface>(operation);
407  // Filter successors that return to the parent operation.
408  auto regionPredicate = [&](RegionSuccessor &successorRegion) {
409  // If the RegionSuccessor has no associated successor, it will return to
410  // its parent operation.
411  return !successorRegion.getSuccessor();
412  };
413  // Introduce a clone for all region "results" that are returned to the
414  // parent operation. This is required since the parent's result value has
415  // been considered critical. Therefore, the algorithm assumes that a clone
416  // of a previously allocated buffer is returned by the operation (like in
417  // the case of a block argument).
418  return introduceClonesForRegionSuccessors(
419  regionInterface, operation->getRegions(), value, regionPredicate);
420  }
421 
422  /// Introduces buffer clones for all terminators in the given regions. The
423  /// regionPredicate is applied to every successor region in order to restrict
424  /// the clones to specific regions.
425  template <typename TPredicate>
426  LogicalResult introduceClonesForRegionSuccessors(
427  RegionBranchOpInterface regionInterface, MutableArrayRef<Region> regions,
428  Value argValue, const TPredicate &regionPredicate) {
429  for (Region &region : regions) {
430  // Query the regionInterface to get all successor regions of the current
431  // one.
432  SmallVector<RegionSuccessor, 2> successorRegions;
433  regionInterface.getSuccessorRegions(region.getRegionNumber(),
434  successorRegions);
435  // Try to find a matching region successor.
436  RegionSuccessor *regionSuccessor =
437  llvm::find_if(successorRegions, regionPredicate);
438  if (regionSuccessor == successorRegions.end())
439  continue;
440  // Get the operand index in the context of the current successor input
441  // bindings.
442  size_t operandIndex =
443  llvm::find(regionSuccessor->getSuccessorInputs(), argValue)
444  .getIndex();
445 
446  // Iterate over all immediate terminator operations to introduce
447  // new buffer allocations. Thereby, the appropriate terminator operand
448  // will be adjusted to point to the newly allocated buffer instead.
449  if (failed(walkReturnOperations(&region, [&](Operation *terminator) {
450  // Get the actual mutable operands for this terminator op.
451  auto terminatorOperands = *getMutableRegionBranchSuccessorOperands(
452  terminator, region.getRegionNumber());
453  // Extract the source value from the current terminator.
454  // This conversion needs to exist on a separate line due to a bug in
455  // GCC conversion analysis.
456  OperandRange immutableTerminatorOperands = terminatorOperands;
457  Value sourceValue = immutableTerminatorOperands[operandIndex];
458  // Create a new clone at the current location of the terminator.
459  auto clone = introduceCloneBuffers(sourceValue, terminator);
460  if (failed(clone))
461  return failure();
462  // Wire clone and terminator operand.
463  terminatorOperands.slice(operandIndex, 1).assign(*clone);
464  return success();
465  })))
466  return failure();
467  }
468  return success();
469  }
470 
471  /// Creates a new memory allocation for the given source value and clones
472  /// its content into the newly allocated buffer. The terminator operation is
473  /// used to insert the clone operation at the right place.
474  FailureOr<Value> introduceCloneBuffers(Value sourceValue,
475  Operation *terminator) {
476  // Avoid multiple clones of the same source value. This can happen in the
477  // presence of loops when a branch acts as a backedge while also having
478  // another successor that returns to its parent operation. Note: that
479  // copying copied buffers can introduce memory leaks since the invariant of
480  // BufferDeallocation assumes that a buffer will be only cloned once into a
481  // temporary buffer. Hence, the construction of clone chains introduces
482  // additional allocations that are not tracked automatically by the
483  // algorithm.
484  if (clonedValues.contains(sourceValue))
485  return sourceValue;
486  // Create a new clone operation that copies the contents of the old
487  // buffer to the new one.
488  auto clone = buildClone(terminator, sourceValue);
489  if (succeeded(clone)) {
490  // Remember the clone of original source value.
491  clonedValues.insert(*clone);
492  }
493  return clone;
494  }
495 
496  /// Finds correct dealloc positions according to the algorithm described at
497  /// the top of the file for all alloc nodes and block arguments that can be
498  /// handled by this analysis.
499  LogicalResult placeDeallocs() {
500  // Move or insert deallocs using the previously computed information.
501  // These deallocations will be linked to their associated allocation nodes
502  // since they don't have any aliases that can (potentially) increase their
503  // liveness.
504  for (const BufferPlacementAllocs::AllocEntry &entry : allocs) {
505  Value alloc = std::get<0>(entry);
506  auto aliasesSet = aliases.resolve(alloc);
507  assert(!aliasesSet.empty() && "must contain at least one alias");
508 
509  // Determine the actual block to place the dealloc and get liveness
510  // information.
511  Block *placementBlock =
512  findCommonDominator(alloc, aliasesSet, postDominators);
513  const LivenessBlockInfo *livenessInfo =
514  liveness.getLiveness(placementBlock);
515 
516  // We have to ensure that the dealloc will be after the last use of all
517  // aliases of the given value. We first assume that there are no uses in
518  // the placementBlock and that we can safely place the dealloc at the
519  // beginning.
520  Operation *endOperation = &placementBlock->front();
521 
522  // Iterate over all aliases and ensure that the endOperation will point
523  // to the last operation of all potential aliases in the placementBlock.
524  for (Value alias : aliasesSet) {
525  // Ensure that the start operation is at least the defining operation of
526  // the current alias to avoid invalid placement of deallocs for aliases
527  // without any uses.
528  Operation *beforeOp = endOperation;
529  if (alias.getDefiningOp() &&
530  !(beforeOp = placementBlock->findAncestorOpInBlock(
531  *alias.getDefiningOp())))
532  continue;
533 
534  Operation *aliasEndOperation =
535  livenessInfo->getEndOperation(alias, beforeOp);
536  // Check whether the aliasEndOperation lies in the desired block and
537  // whether it is behind the current endOperation. If yes, this will be
538  // the new endOperation.
539  if (aliasEndOperation->getBlock() == placementBlock &&
540  endOperation->isBeforeInBlock(aliasEndOperation))
541  endOperation = aliasEndOperation;
542  }
543  // endOperation is the last operation behind which we can safely store
544  // the dealloc taking all potential aliases into account.
545 
546  // If there is an existing dealloc, move it to the right place.
547  Operation *deallocOperation = std::get<1>(entry);
548  if (deallocOperation) {
549  deallocOperation->moveAfter(endOperation);
550  } else {
551  // If the Dealloc position is at the terminator operation of the
552  // block, then the value should escape from a deallocation.
553  Operation *nextOp = endOperation->getNextNode();
554  if (!nextOp)
555  continue;
556  // If there is no dealloc node, insert one in the right place.
557  if (failed(buildDealloc(nextOp, alloc)))
558  return failure();
559  }
560  }
561  return success();
562  }
563 
564  /// Builds a deallocation operation compatible with the given allocation
565  /// value. If there is no registered AllocationOpInterface implementation for
566  /// the given value (e.g. in the case of a function parameter), this method
567  /// builds a memref::DeallocOp.
568  LogicalResult buildDealloc(Operation *op, Value alloc) {
569  OpBuilder builder(op);
570  auto it = aliasToAllocations.find(alloc);
571  if (it != aliasToAllocations.end()) {
572  // Call the allocation op interface to build a supported and
573  // compatible deallocation operation.
574  auto dealloc = it->second.buildDealloc(builder, alloc);
575  if (!dealloc)
576  return op->emitError()
577  << "allocations without compatible deallocations are "
578  "not supported";
579  } else {
580  // Build a "default" DeallocOp for unknown allocation sources.
581  builder.create<memref::DeallocOp>(alloc.getLoc(), alloc);
582  }
583  return success();
584  }
585 
586  /// Builds a clone operation compatible with the given allocation value. If
587  /// there is no registered AllocationOpInterface implementation for the given
588  /// value (e.g. in the case of a function parameter), this method builds a
589  /// bufferization::CloneOp.
590  FailureOr<Value> buildClone(Operation *op, Value alloc) {
591  OpBuilder builder(op);
592  auto it = aliasToAllocations.find(alloc);
593  if (it != aliasToAllocations.end()) {
594  // Call the allocation op interface to build a supported and
595  // compatible clone operation.
596  auto clone = it->second.buildClone(builder, alloc);
597  if (clone)
598  return *clone;
599  return (LogicalResult)(op->emitError()
600  << "allocations without compatible clone ops "
601  "are not supported");
602  }
603  // Build a "default" CloneOp for unknown allocation sources.
604  return builder.create<bufferization::CloneOp>(alloc.getLoc(), alloc)
605  .getResult();
606  }
607 
608  /// The dominator info to find the appropriate start operation to move the
609  /// allocs.
610  DominanceInfo dominators;
611 
612  /// The post dominator info to move the dependent allocs in the right
613  /// position.
614  PostDominanceInfo postDominators;
615 
616  /// Stores already cloned buffers to avoid additional clones of clones.
617  ValueSetT clonedValues;
618 
619  /// Maps aliases to their source allocation interfaces (inverse mapping).
620  AliasAllocationMapT aliasToAllocations;
621 };
622 
623 //===----------------------------------------------------------------------===//
624 // BufferDeallocationPass
625 //===----------------------------------------------------------------------===//
626 
627 struct DefaultAllocationInterface
628  : public bufferization::AllocationOpInterface::ExternalModel<
629  DefaultAllocationInterface, memref::AllocOp> {
630  static Optional<Operation *> buildDealloc(OpBuilder &builder, Value alloc) {
631  return builder.create<memref::DeallocOp>(alloc.getLoc(), alloc)
632  .getOperation();
633  }
634  static Optional<Value> buildClone(OpBuilder &builder, Value alloc) {
635  return builder.create<bufferization::CloneOp>(alloc.getLoc(), alloc)
636  .getResult();
637  }
638 };
639 
640 /// The actual buffer deallocation pass that inserts and moves dealloc nodes
641 /// into the right positions. Furthermore, it inserts additional clones if
642 /// necessary. It uses the algorithm described at the top of the file.
643 struct BufferDeallocationPass
644  : public bufferization::impl::BufferDeallocationBase<
645  BufferDeallocationPass> {
646  void getDependentDialects(DialectRegistry &registry) const override {
647  registry.insert<bufferization::BufferizationDialect>();
648  registry.insert<memref::MemRefDialect>();
650  }
651 
652  void runOnOperation() override {
653  func::FuncOp func = getOperation();
654  if (func.isExternal())
655  return;
656 
657  if (failed(deallocateBuffers(func)))
658  signalPassFailure();
659  }
660 };
661 
662 } // namespace
663 
665  if (isa<ModuleOp>(op)) {
666  WalkResult result = op->walk([&](func::FuncOp funcOp) {
667  if (failed(deallocateBuffers(funcOp)))
668  return WalkResult::interrupt();
669  return WalkResult::advance();
670  });
671  return success(!result.wasInterrupted());
672  }
673 
674  // Ensure that there are supported loops only.
675  Backedges backedges(op);
676  if (backedges.size()) {
677  op->emitError("Only structured control-flow loops are supported.");
678  return failure();
679  }
680 
681  // Check that the control flow structures are supported.
683  return failure();
684 
685  // Gather all required allocation nodes and prepare the deallocation phase.
686  BufferDeallocation deallocation(op);
687 
688  // Check for supported AllocationOpInterface implementations and prepare the
689  // internal deallocation pass.
690  if (failed(deallocation.prepare()))
691  return failure();
692 
693  // Place all required temporary clone and dealloc nodes.
694  if (failed(deallocation.deallocate()))
695  return failure();
696 
697  return success();
698 }
699 
701  DialectRegistry &registry) {
702  registry.addExtension(+[](MLIRContext *ctx, memref::MemRefDialect *dialect) {
703  memref::AllocOp::attachInterface<DefaultAllocationInterface>(*ctx);
704  });
705 }
706 
707 //===----------------------------------------------------------------------===//
708 // BufferDeallocationPass construction
709 //===----------------------------------------------------------------------===//
710 
712  return std::make_unique<BufferDeallocationPass>();
713 }
static bool validateSupportedControlFlow(Operation *op)
Checks if all operations that have at least one attached region implement the RegionBranchOpInterface...
static LogicalResult walkReturnOperations(Region *region, llvm::function_ref< LogicalResult(Operation *)> func)
Walks over all immediate return-like terminators in the given region.
static constexpr const bool value
This class represents an argument of a Block.
Definition: Value.h:296
Block * getOwner() const
Returns the block that owns this argument.
Definition: Value.h:305
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:308
Block represents an ordered list of Operations.
Definition: Block.h:30
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:62
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
pred_iterator pred_begin()
Definition: Block.h:219
SuccessorRange getSuccessors()
Definition: Block.h:253
OpListType & getOperations()
Definition: Block.h:126
Operation & front()
Definition: Block.h:142
pred_iterator pred_end()
Definition: Block.h:222
The DialectRegistry maps a dialect namespace to a constructor for the matching dialect.
void addExtension(std::unique_ptr< DialectExtensionBase > extension)
Add the given extension to the registry.
A class for computing basic dominance information.
Definition: Dominance.h:117
This class provides support for representing a failure result, or a valid value of type T.
Definition: LogicalResult.h:78
This class represents liveness information on block level.
Definition: Liveness.h:99
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
Definition: Liveness.cpp:375
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:56
void assign(ValueRange values)
Assign this range to the given values.
This class helps build Operations.
Definition: Builders.h:198
Operation * create(const OperationState &state)
Creates an operation given the fields represented as an OperationState.
Definition: Builders.cpp:422
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:41
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
Value getOperand(unsigned idx)
Definition: Operation.h:267
void setOperand(unsigned idx, Value value)
Definition: Operation.h:268
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
Definition: Operation.cpp:265
static Operation * create(Location location, OperationName name, TypeRange resultTypes, ValueRange operands, NamedAttrList &&attributes, BlockRange successors, unsigned numRegions)
Create a new Operation with the specific fields.
Definition: Operation.cpp:49
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Definition: Operation.cpp:225
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:144
OpTy getParentOfType()
Return the closest surrounding parent operation that is of type 'OpTy'.
Definition: Operation.h:169
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
result_range getResults()
Definition: Operation.h:332
void moveAfter(Operation *existingOp)
Unlink this operation from its current block and insert it right after existingOp which may be in the...
Definition: Operation.cpp:448
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:574
A class for computing basic postdominance information.
Definition: Dominance.h:176
This class represents a successor of a region.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
Region * getSuccessor() const
Return the given region successor.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
Operation * getParentOp()
Return the parent operation this region is attached to.
Definition: Region.h:200
bool empty()
Definition: Region.h:60
Block & front()
Definition: Region.h:65
This class models how operands are forwarded to block arguments in control flow.
MutableOperandRange slice(unsigned subStart, unsigned subLen) const
Get a slice of the operands forwarded to the successor.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
Location getLoc() const
Return the location of this value.
Definition: Value.cpp:26
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
A utility result that is used to signal how to proceed with an ongoing walk:
Definition: Visitors.h:34
bool wasSkipped() const
Returns true if the walk was skipped.
Definition: Visitors.h:58
static WalkResult advance()
Definition: Visitors.h:51
bool wasInterrupted() const
Returns true if the walk was interrupted.
Definition: Visitors.h:55
static WalkResult interrupt()
Definition: Visitors.h:50
std::tuple< Value, Operation * > AllocEntry
Represents a tuple of allocValue and deallocOperation.
Definition: BufferUtils.h:37
The base class for all BufferPlacement transformations.
Definition: BufferUtils.h:77
void registerAllocationOpInterfaceExternalModels(DialectRegistry &registry)
Register external models for AllocationOpInterface.
LogicalResult deallocateBuffers(Operation *op)
Run buffer deallocation.
std::unique_ptr< Pass > createBufferDeallocationPass()
Creates an instance of the BufferDeallocation pass to free all allocated buffers.
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
Definition: LogicalResult.h:68
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
bool isRegionReturnLike(Operation *operation)
Returns true if the given operation is either annotated with the ReturnLike trait or implements the R...
Optional< MutableOperandRange > getMutableRegionBranchSuccessorOperands(Operation *operation, Optional< unsigned > regionIndex)
Returns the mutable operands that are passed to the region with the given regionIndex.
Operation * clone(OpBuilder &b, Operation *op, TypeRange newResultTypes, ValueRange newOperands)
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26