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