60 #include "llvm/ADT/SetOperations.h" 69 for (
Block &block : *region) {
70 Operation *terminator = block.getTerminator();
73 if (
failed(func(terminator)))
96 size_t size = regions.size();
97 if (((size == 1 && !operation->
getResults().empty()) || size > 1) &&
98 !dyn_cast<RegionBranchOpInterface>(operation)) {
99 operation->
emitError(
"All operations with attached regions need to " 100 "implement the RegionBranchOpInterface.");
123 Backedges(
Operation *op) { recurse(op); }
126 size_t size()
const {
return edgeSet.size(); }
129 BackedgeSetT::const_iterator begin()
const {
return edgeSet.begin(); }
132 BackedgeSetT::const_iterator end()
const {
return edgeSet.end(); }
138 bool enter(
Block ¤t,
Block *predecessor) {
139 bool inserted = visited.insert(¤t).second;
141 edgeSet.insert(std::make_pair(predecessor, ¤t));
146 void exit(
Block ¤t) { visited.erase(¤t); }
154 if (isa<BranchOpInterface>(op)) {
156 recurse(*succ, current);
162 recurse(region.
front(), current);
168 void recurse(
Block &block,
Block *predecessor) {
171 if (!enter(block, predecessor))
186 BackedgeSetT edgeSet;
198 using AliasAllocationMapT =
203 postDominators(op) {}
213 Value alloc = std::get<0>(entry);
214 auto allocationInterface =
218 if (!std::get<1>(entry) && !allocationInterface) {
220 "Allocation is not deallocated explicitly nor does the operation " 221 "implement the AllocationOpInterface.");
225 aliasToAllocations[alloc] = allocationInterface;
228 for (
Value alias : aliases.resolve(alloc)) {
232 aliasToAllocations[alias] = allocationInterface;
242 if (
failed(introduceClones()))
246 return placeDeallocs();
256 llvm::SmallDenseSet<std::tuple<Value, Block *>> visitedValues;
263 auto findUnsafeValues = [&](
Value source,
Block *definingBlock) {
264 auto it = aliases.find(source);
265 if (it == aliases.end())
268 if (valuesToFree.count(value) > 0)
275 if (!dominators.dominates(definingBlock, parentBlock) ||
277 toProcess.emplace_back(value, parentBlock);
278 valuesToFree.insert(value);
279 }
else if (visitedValues.insert(std::make_tuple(value, definingBlock))
281 toProcess.emplace_back(value, definingBlock);
287 Value allocValue = std::get<0>(entry);
292 while (!toProcess.empty()) {
293 auto current = toProcess.pop_back_val();
294 findUnsafeValues(std::get<0>(current), std::get<1>(current));
299 aliases.remove(valuesToFree);
305 : introduceValueCopyForRegionResult(
value)))
311 allocs.registerAlloc(std::make_tuple(
value,
nullptr));
326 Operation *terminator = (*it)->getTerminator();
327 auto branchInterface = cast<BranchOpInterface>(terminator);
329 branchInterface.getSuccessorOperands(it.getSuccessorIndex());
338 auto clone = introduceCloneBuffers(sourceValue, terminator);
341 operands.slice(blockArg.
getArgNumber(), 1).assign(*clone);
350 RegionBranchOpInterface regionInterface;
351 if (&argRegion->
front() != block ||
352 !(regionInterface = dyn_cast<RegionBranchOpInterface>(parentOp)))
355 if (
failed(introduceClonesForRegionSuccessors(
359 return successorRegion.getSuccessor() == argRegion;
367 regionInterface.getSuccessorRegions(
llvm::None, successorRegions);
369 llvm::find_if(successorRegions, [&](
RegionSuccessor &successorRegion) {
372 if (it == successorRegions.end())
378 regionInterface.getSuccessorEntryOperands(argRegion->
getRegionNumber());
379 size_t operandIndex =
380 llvm::find(it->getSuccessorInputs(), blockArg).getIndex() +
381 operands.getBeginOperandIndex();
384 operands[operandIndex - operands.getBeginOperandIndex()] &&
385 "region interface operands don't match parentOp operands");
386 auto clone = introduceCloneBuffers(operand, parentOp);
399 auto regionInterface = cast<RegionBranchOpInterface>(operation);
411 return introduceClonesForRegionSuccessors(
418 template <
typename TPredicate>
421 Value argValue,
const TPredicate ®ionPredicate) {
422 for (
Region ®ion : regions) {
430 llvm::find_if(successorRegions, regionPredicate);
431 if (regionSuccessor == successorRegions.end())
435 size_t operandIndex =
449 OperandRange immutableTerminatorOperands = terminatorOperands;
450 Value sourceValue = immutableTerminatorOperands[operandIndex];
452 auto clone = introduceCloneBuffers(sourceValue, terminator);
456 terminatorOperands.slice(operandIndex, 1).assign(*clone);
477 if (clonedValues.contains(sourceValue))
481 auto clone = buildClone(terminator, sourceValue);
484 clonedValues.insert(*clone);
498 Value alloc = std::get<0>(entry);
499 auto aliasesSet = aliases.resolve(alloc);
500 assert(!aliasesSet.empty() &&
"must contain at least one alias");
504 Block *placementBlock =
505 findCommonDominator(alloc, aliasesSet, postDominators);
507 liveness.getLiveness(placementBlock);
513 Operation *endOperation = &placementBlock->front();
517 for (
Value alias : aliasesSet) {
522 if (alias.getDefiningOp() &&
523 !(beforeOp = placementBlock->findAncestorOpInBlock(
524 *alias.getDefiningOp())))
532 if (aliasEndOperation->
getBlock() == placementBlock &&
534 endOperation = aliasEndOperation;
540 Operation *deallocOperation = std::get<1>(entry);
541 if (deallocOperation) {
542 deallocOperation->
moveAfter(endOperation);
546 Operation *nextOp = endOperation->getNextNode();
550 if (
failed(buildDealloc(nextOp, alloc)))
563 auto it = aliasToAllocations.find(alloc);
564 if (it != aliasToAllocations.end()) {
567 auto dealloc = it->second.buildDealloc(builder, alloc);
570 <<
"allocations without compatible deallocations are " 574 builder.
create<memref::DeallocOp>(alloc.
getLoc(), alloc);
585 auto it = aliasToAllocations.find(alloc);
586 if (it != aliasToAllocations.end()) {
589 auto clone = it->second.buildClone(builder, alloc);
593 <<
"allocations without compatible clone ops " 594 "are not supported");
597 return builder.
create<bufferization::CloneOp>(alloc.
getLoc(), alloc)
610 ValueSetT clonedValues;
613 AliasAllocationMapT aliasToAllocations;
620 struct DefaultAllocationInterface
621 :
public bufferization::AllocationOpInterface::ExternalModel<
622 DefaultAllocationInterface, memref::AllocOp> {
624 return builder.
create<memref::DeallocOp>(alloc.
getLoc(), alloc)
628 return builder.
create<bufferization::CloneOp>(alloc.
getLoc(), alloc)
636 struct BufferDeallocationPass : BufferDeallocationBase<BufferDeallocationPass> {
638 registry.
insert<bufferization::BufferizationDialect>();
639 registry.
insert<memref::MemRefDialect>();
643 void runOnOperation()
override {
644 func::FuncOp func = getOperation();
645 if (func.isExternal())
656 if (isa<ModuleOp>(op)) {
666 Backedges backedges(op);
667 if (backedges.size()) {
668 op->
emitError(
"Only structured control-flow loops are supported.");
677 BufferDeallocation deallocation(op);
681 if (
failed(deallocation.prepare()))
685 if (
failed(deallocation.deallocate()))
694 memref::AllocOp::attachInterface<DefaultAllocationInterface>(*ctx);
703 return std::make_unique<BufferDeallocationPass>();
Include the generated interface declarations.
This class contains a list of basic blocks and a link to the parent operation it is attached to...
Operation is a basic unit of execution within MLIR.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Block represents an ordered list of Operations.
std::tuple< Value, Operation * > AllocEntry
Represents a tuple of allocValue and deallocOperation.
static LogicalResult walkReturnOperations(Region *region, llvm::function_ref< LogicalResult(Operation *)> func)
Walks over all immediate return-like terminators in the given region.
This class represents liveness information on block level.
bool wasInterrupted() const
Returns true if the walk was interrupted.
Value getOperand(unsigned idx)
OpListType & getOperations()
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
A class for computing basic dominance information.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value...
bool isRegionReturnLike(Operation *operation)
Returns true if the given operation is either annotated with the ReturnLike trait or implements the R...
unsigned getArgNumber() const
Returns the number of this argument.
Block * getBlock()
Returns the operation block that contains this operation.
std::unique_ptr< Pass > createBufferDeallocationPass()
Creates an instance of the BufferDeallocation pass to free all allocated buffers. ...
OpTy getParentOfType()
Return the closest surrounding parent operation that is of type 'OpTy'.
static bool validateSupportedControlFlow(Operation *op)
Checks if all operations that have at least one attached region implement the RegionBranchOpInterface...
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
static constexpr const bool value
void registerAllocationOpInterfaceExternalModels(DialectRegistry ®istry)
Register external models for AllocationOpInterface.
LogicalResult deallocateBuffers(Operation *op)
Run buffer deallocation.
Region * getSuccessor() const
Return the given region successor.
Block * getOwner() const
Returns the block that owns this argument.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
std::enable_if< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT >::type walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one)...
Operation * create(const OperationState &state)
Creates an operation given the fields represented as an OperationState.
void addExtension(std::unique_ptr< DialectExtensionBase > extension)
Add the given extension to the registry.
This class represents an efficient way to signal success or failure.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Block * getSuccessor(unsigned index)
unsigned getRegionNumber()
Return the number of this region in the parent operation.
This class provides support for representing a failure result, or a valid value of type T...
Block * getParentBlock()
Return the Block in which this Value is defined.
Optional< MutableOperandRange > getMutableRegionBranchSuccessorOperands(Operation *operation, Optional< unsigned > regionIndex)
Returns the mutable operands that are passed to the region with the given regionIndex.
static WalkResult advance()
static WalkResult interrupt()
This class models how operands are forwarded to block arguments in control flow.
A utility result that is used to signal how to proceed with an ongoing walk:
This class represents an argument of a Block.
void setOperand(unsigned idx, Value value)
Location getLoc() const
Return the location of this value.
Operation * getParentOp()
Return the parent operation this region is attached to.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
void moveAfter(Operation *existingOp)
Unlink this operation from its current block and insert it right after existingOp which may be in the...
This class represents a successor of a region.
Operation * getEndOperation(Value value, Operation *startOperation) const
Gets the end operation for the given value using the start operation provided (must be referenced in ...
The DialectRegistry maps a dialect namespace to a constructor for the matching dialect.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
MLIRContext is the top-level object for a collection of MLIR operations.
bool wasSkipped() const
Returns true if the walk was skipped.
This class implements the operand iterators for the Operation class.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region...
SuccessorRange getSuccessors()
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
result_range getResults()
This class helps build Operations.
A class for computing basic postdominance information.
pred_iterator pred_begin()