MLIR  14.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 
14 #include "PassDetail.h"
17 #include "mlir/IR/Operation.h"
20 #include "mlir/Pass/Pass.h"
21 #include "mlir/Transforms/Passes.h"
22 #include "llvm/ADT/SetOperations.h"
23 
24 using namespace mlir;
25 
26 //===----------------------------------------------------------------------===//
27 // BufferPlacementAllocs
28 //===----------------------------------------------------------------------===//
29 
30 /// Get the start operation to place the given alloc value withing the
31 // specified placement block.
33  Block *placementBlock,
34  const Liveness &liveness) {
35  // We have to ensure that we place the alloc before its first use in this
36  // block.
37  const LivenessBlockInfo &livenessInfo = *liveness.getLiveness(placementBlock);
38  Operation *startOperation = livenessInfo.getStartOperation(allocValue);
39  // Check whether the start operation lies in the desired placement block.
40  // If not, we will use the terminator as this is the last operation in
41  // this block.
42  if (startOperation->getBlock() != placementBlock) {
43  Operation *opInPlacementBlock =
44  placementBlock->findAncestorOpInBlock(*startOperation);
45  startOperation = opInPlacementBlock ? opInPlacementBlock
46  : placementBlock->getTerminator();
47  }
48 
49  return startOperation;
50 }
51 
52 /// Initializes the internal list by discovering all supported allocation
53 /// nodes.
55 
56 /// Searches for and registers all supported allocation entries.
57 void BufferPlacementAllocs::build(Operation *op) {
58  op->walk([&](MemoryEffectOpInterface opInterface) {
59  // Try to find a single allocation result.
61  opInterface.getEffects(effects);
62 
64  llvm::copy_if(
65  effects, std::back_inserter(allocateResultEffects),
67  Value value = it.getValue();
68  return isa<MemoryEffects::Allocate>(it.getEffect()) && value &&
69  value.isa<OpResult>() &&
70  it.getResource() !=
72  });
73  // If there is one result only, we will be able to move the allocation and
74  // (possibly existing) deallocation ops.
75  if (allocateResultEffects.size() != 1)
76  return;
77  // Get allocation result.
78  Value allocValue = allocateResultEffects[0].getValue();
79  // Find the associated dealloc value and register the allocation entry.
80  llvm::Optional<Operation *> dealloc = findDealloc(allocValue);
81  // If the allocation has > 1 dealloc associated with it, skip handling it.
82  if (!dealloc.hasValue())
83  return;
84  allocs.push_back(std::make_tuple(allocValue, *dealloc));
85  });
86 }
87 
88 //===----------------------------------------------------------------------===//
89 // BufferPlacementTransformationBase
90 //===----------------------------------------------------------------------===//
91 
92 /// Constructs a new transformation base using the given root operation.
94  Operation *op)
95  : aliases(op), allocs(op), liveness(op) {}
96 
97 /// Returns true if the given operation represents a loop by testing whether it
98 /// implements the `LoopLikeOpInterface` or the `RegionBranchOpInterface`. In
99 /// the case of a `RegionBranchOpInterface`, it checks all region-based control-
100 /// flow edges for cycles.
102  // If the operation implements the `LoopLikeOpInterface` it can be considered
103  // a loop.
104  if (isa<LoopLikeOpInterface>(op))
105  return true;
106 
107  // If the operation does not implement the `RegionBranchOpInterface`, it is
108  // (currently) not possible to detect a loop.
109  RegionBranchOpInterface regionInterface;
110  if (!(regionInterface = dyn_cast<RegionBranchOpInterface>(op)))
111  return false;
112 
113  // Recurses into a region using the current region interface to find potential
114  // cycles.
115  SmallPtrSet<Region *, 4> visitedRegions;
116  std::function<bool(Region *)> recurse = [&](Region *current) {
117  if (!current)
118  return false;
119  // If we have found a back edge, the parent operation induces a loop.
120  if (!visitedRegions.insert(current).second)
121  return true;
122  // Recurses into all region successors.
124  regionInterface.getSuccessorRegions(current->getRegionNumber(), successors);
125  for (RegionSuccessor &regionEntry : successors)
126  if (recurse(regionEntry.getSuccessor()))
127  return true;
128  return false;
129  };
130 
131  // Start with all entry regions and test whether they induce a loop.
132  SmallVector<RegionSuccessor, 2> successorRegions;
133  regionInterface.getSuccessorRegions(/*index=*/llvm::None, successorRegions);
134  for (RegionSuccessor &regionEntry : successorRegions) {
135  if (recurse(regionEntry.getSuccessor()))
136  return true;
137  visitedRegions.clear();
138  }
139 
140  return false;
141 }
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
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:423
EffectT * getEffect() const
Return the effect being applied.
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:351
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:96
static constexpr const bool value
static AutomaticAllocationScopeResource * get()
Returns a unique instance for the given effect class.
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)...
Definition: Operation.h:515
BufferPlacementTransformationBase(Operation *op)
Constructs a new operation base using the given root operation.
Definition: BufferUtils.cpp:93
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:224
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:32
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:84
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:230
Resource * getResource() const
Return the resource that the effect applies to.
bool isa() const
Definition: Value.h:89
This class represents a successor of a region.
BufferPlacementAllocs(Operation *op)
Initializes the internal list by discovering all supported allocation nodes.
Definition: BufferUtils.cpp:54
llvm::Optional< Operation * > findDealloc(Value allocValue)
Finds a single dealloc operation for the given allocated value.
Definition: MemRefUtils.cpp:19
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
static bool isLoop(Operation *op)
Returns true if the given operation represents a loop by testing whether it implements the LoopLikeOp...