MLIR  17.0.0git
BufferUtils.cpp
Go to the documentation of this file.
1 //===- BufferUtils.cpp - buffer transformation utilities ------------------===//
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 utilities for buffer optimization passes.
10 //
11 //===----------------------------------------------------------------------===//
12 
17 #include "mlir/IR/Operation.h"
20 #include "mlir/Pass/Pass.h"
21 #include "llvm/ADT/SetOperations.h"
22 #include "llvm/ADT/SmallString.h"
23 #include <optional>
24 
25 using namespace mlir;
26 using namespace mlir::bufferization;
27 
28 //===----------------------------------------------------------------------===//
29 // BufferPlacementAllocs
30 //===----------------------------------------------------------------------===//
31 
32 /// Get the start operation to place the given alloc value withing the
33 // specified placement block.
35  Block *placementBlock,
36  const Liveness &liveness) {
37  // We have to ensure that we place the alloc before its first use in this
38  // block.
39  const LivenessBlockInfo &livenessInfo = *liveness.getLiveness(placementBlock);
40  Operation *startOperation = livenessInfo.getStartOperation(allocValue);
41  // Check whether the start operation lies in the desired placement block.
42  // If not, we will use the terminator as this is the last operation in
43  // this block.
44  if (startOperation->getBlock() != placementBlock) {
45  Operation *opInPlacementBlock =
46  placementBlock->findAncestorOpInBlock(*startOperation);
47  startOperation = opInPlacementBlock ? opInPlacementBlock
48  : placementBlock->getTerminator();
49  }
50 
51  return startOperation;
52 }
53 
54 /// Initializes the internal list by discovering all supported allocation
55 /// nodes.
57 
58 /// Searches for and registers all supported allocation entries.
59 void BufferPlacementAllocs::build(Operation *op) {
60  op->walk([&](MemoryEffectOpInterface opInterface) {
61  // Try to find a single allocation result.
63  opInterface.getEffects(effects);
64 
66  llvm::copy_if(
67  effects, std::back_inserter(allocateResultEffects),
69  Value value = it.getValue();
70  return isa<MemoryEffects::Allocate>(it.getEffect()) && value &&
71  value.isa<OpResult>() &&
72  it.getResource() !=
74  });
75  // If there is one result only, we will be able to move the allocation and
76  // (possibly existing) deallocation ops.
77  if (allocateResultEffects.size() != 1)
78  return;
79  // Get allocation result.
80  Value allocValue = allocateResultEffects[0].getValue();
81  // Find the associated dealloc value and register the allocation entry.
82  std::optional<Operation *> dealloc = memref::findDealloc(allocValue);
83  // If the allocation has > 1 dealloc associated with it, skip handling it.
84  if (!dealloc)
85  return;
86  allocs.push_back(std::make_tuple(allocValue, *dealloc));
87  });
88 }
89 
90 //===----------------------------------------------------------------------===//
91 // BufferPlacementTransformationBase
92 //===----------------------------------------------------------------------===//
93 
94 /// Constructs a new transformation base using the given root operation.
96  Operation *op)
97  : aliases(op), allocs(op), liveness(op) {}
98 
99 /// Returns true if the given operation represents a loop by testing whether it
100 /// implements the `LoopLikeOpInterface` or the `RegionBranchOpInterface`. In
101 /// the case of a `RegionBranchOpInterface`, it checks all region-based control-
102 /// flow edges for cycles.
104  // If the operation implements the `LoopLikeOpInterface` it can be considered
105  // a loop.
106  if (isa<LoopLikeOpInterface>(op))
107  return true;
108 
109  // If the operation does not implement the `RegionBranchOpInterface`, it is
110  // (currently) not possible to detect a loop.
111  RegionBranchOpInterface regionInterface;
112  if (!(regionInterface = dyn_cast<RegionBranchOpInterface>(op)))
113  return false;
114 
115  // Recurses into a region using the current region interface to find potential
116  // cycles.
117  SmallPtrSet<Region *, 4> visitedRegions;
118  std::function<bool(Region *)> recurse = [&](Region *current) {
119  if (!current)
120  return false;
121  // If we have found a back edge, the parent operation induces a loop.
122  if (!visitedRegions.insert(current).second)
123  return true;
124  // Recurses into all region successors.
126  regionInterface.getSuccessorRegions(current->getRegionNumber(), successors);
127  for (RegionSuccessor &regionEntry : successors)
128  if (recurse(regionEntry.getSuccessor()))
129  return true;
130  return false;
131  };
132 
133  // Start with all entry regions and test whether they induce a loop.
134  SmallVector<RegionSuccessor, 2> successorRegions;
135  regionInterface.getSuccessorRegions(/*index=*/std::nullopt, successorRegions);
136  for (RegionSuccessor &regionEntry : successorRegions) {
137  if (recurse(regionEntry.getSuccessor()))
138  return true;
139  visitedRegions.clear();
140  }
141 
142  return false;
143 }
144 
145 //===----------------------------------------------------------------------===//
146 // BufferPlacementTransformationBase
147 //===----------------------------------------------------------------------===//
148 
150 bufferization::getGlobalFor(arith::ConstantOp constantOp, uint64_t alignment) {
151  auto type = constantOp.getType().cast<RankedTensorType>();
152  auto moduleOp = constantOp->getParentOfType<ModuleOp>();
153  if (!moduleOp)
154  return failure();
155 
156  // If we already have a global for this constant value, no need to do
157  // anything else.
158  for (Operation &op : moduleOp.getRegion().getOps()) {
159  auto globalOp = dyn_cast<memref::GlobalOp>(&op);
160  if (!globalOp)
161  continue;
162  if (!globalOp.getInitialValue().has_value())
163  continue;
164  uint64_t opAlignment = globalOp.getAlignment().value_or(0);
165  Attribute initialValue = globalOp.getInitialValue().value();
166  if (opAlignment == alignment && initialValue == constantOp.getValue())
167  return globalOp;
168  }
169 
170  // Create a builder without an insertion point. We will insert using the
171  // symbol table to guarantee unique names.
172  OpBuilder globalBuilder(moduleOp.getContext());
173  SymbolTable symbolTable(moduleOp);
174 
175  // Create a pretty name.
176  SmallString<64> buf;
177  llvm::raw_svector_ostream os(buf);
178  interleave(type.getShape(), os, "x");
179  os << "x" << type.getElementType();
180 
181  // Add an optional alignment to the global memref.
182  IntegerAttr memrefAlignment =
183  alignment > 0 ? IntegerAttr::get(globalBuilder.getI64Type(), alignment)
184  : IntegerAttr();
185 
186  BufferizeTypeConverter typeConverter;
187  auto global = globalBuilder.create<memref::GlobalOp>(
188  constantOp.getLoc(), (Twine("__constant_") + os.str()).str(),
189  /*sym_visibility=*/globalBuilder.getStringAttr("private"),
190  /*type=*/typeConverter.convertType(type).cast<MemRefType>(),
191  /*initial_value=*/constantOp.getValue().cast<ElementsAttr>(),
192  /*constant=*/true,
193  /*alignment=*/memrefAlignment);
194  symbolTable.insert(global);
195  // The symbol table inserts at the end of the module, but globals are a bit
196  // nicer if they are at the beginning.
197  global->moveBefore(&moduleOp.front());
198  return global;
199 }
Attributes are known-constant values of operations.
Definition: Attributes.h:25
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
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:232
IntegerType getI64Type()
Definition: Builders.cpp:70
StringAttr getStringAttr(const Twine &bytes)
Definition: Builders.cpp:243
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 * getStartOperation(Value value) const
Gets the start operation for the given value.
Definition: Liveness.cpp:364
Represents an analysis for computing liveness information from a given top-level operation.
Definition: Liveness.h:47
const LivenessBlockInfo * getLiveness(Block *block) const
Gets liveness info (if any) for the block.
Definition: Liveness.cpp:225
This class helps build Operations.
Definition: Builders.h:199
Operation * create(const OperationState &state)
Creates an operation given the fields represented as an OperationState.
Definition: Builders.cpp:422
This is a value defined by a result of an operation.
Definition: Value.h:450
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:75
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:188
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:532
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:620
This class represents a successor of a region.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
iterator_range< OpIterator > getOps()
Definition: Region.h:172
This class represents a specific instance of an effect.
Resource * getResource() const
Return the resource that the effect applies to.
EffectT * getEffect() const
Return the effect being applied.
Value getValue() const
Return the value the effect is applied on, or nullptr if there isn't a known value being affected.
static AutomaticAllocationScopeResource * get()
Returns a unique instance for the given effect class.
This class allows for representing and managing the symbol table used by operations with the 'SymbolT...
Definition: SymbolTable.h:23
StringAttr insert(Operation *symbol, Block::iterator insertPt={})
Insert a new symbol into the table, and rename it as necessary to avoid collisions.
LogicalResult convertType(Type t, SmallVectorImpl< Type > &results)
Convert the given type.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:93
bool isa() const
Definition: Value.h:98
static Operation * getStartOperation(Value allocValue, Block *placementBlock, const Liveness &liveness)
Get the start operation to place the given alloc value within the specified placement block.
Definition: BufferUtils.cpp:34
BufferPlacementAllocs(Operation *op)
Initializes the internal list by discovering all supported allocation nodes.
Definition: BufferUtils.cpp:56
static bool isLoop(Operation *op)
Returns true if the given operation represents a loop by testing whether it implements the LoopLikeOp...
BufferPlacementTransformationBase(Operation *op)
Constructs a new operation base using the given root operation.
Definition: BufferUtils.cpp:95
A helper type converter class that automatically populates the relevant materializations and type con...
Definition: Bufferize.h:43
FailureOr< memref::GlobalOp > getGlobalFor(arith::ConstantOp constantOp, uint64_t alignment)
std::optional< Operation * > findDealloc(Value allocValue)
Finds a single dealloc operation for the given allocated value.
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62