MLIR 24.0.0git
OptimizeAllocationLiveness.cpp
Go to the documentation of this file.
1//===- OptimizeAllocationLiveness.cpp - impl. optimize allocation liveness pass
2//-===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements a pass for optimizing allocation liveness.
11// The pass moves the deallocation operation after the last user of the
12// allocated buffer.
13//===----------------------------------------------------------------------===//
14
18#include "mlir/IR/Dominance.h"
19#include "mlir/IR/Operation.h"
20#include "mlir/IR/Value.h"
22#include "llvm/Support/DebugLog.h"
23
24#define DEBUG_TYPE "optimize-allocation-liveness"
25
26namespace mlir {
27namespace bufferization {
28#define GEN_PASS_DEF_OPTIMIZEALLOCATIONLIVENESSPASS
29#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
30} // namespace bufferization
31} // namespace mlir
32
33using namespace mlir;
34
35namespace {
36//===----------------------------------------------------------------------===//
37// Helper functions
38//===----------------------------------------------------------------------===//
39
40/// Return true if `a` happens before `b`, i.e., `a` or one of its ancestors
41/// properly dominates `b` and `b` is not inside `a`.
42static bool happensBefore(Operation *a, Operation *b) {
43 do {
44 if (a->isProperAncestor(b))
45 return false;
46 if (Operation *bAncestor = a->getBlock()->findAncestorOpInBlock(*b)) {
47 return a->isBeforeInBlock(bAncestor);
48 }
49 } while ((a = a->getParentOp()));
50 return false;
51}
52
53/// This method searches for a user of value that is a dealloc operation.
54/// If multiple users with free effect are found, return nullptr.
55Operation *findUserWithFreeSideEffect(Value value) {
56 Operation *freeOpUser = nullptr;
57 for (Operation *user : value.getUsers()) {
58 if (MemoryEffectOpInterface memEffectOp =
59 dyn_cast<MemoryEffectOpInterface>(user)) {
61 memEffectOp.getEffects(effects);
62
63 for (const auto &effect : effects) {
64 if (isa<MemoryEffects::Free>(effect.getEffect())) {
65 if (freeOpUser) {
66 LDBG() << "Multiple users with free effect found: " << *freeOpUser
67 << " and " << *user;
68 return nullptr;
69 }
70 freeOpUser = user;
71 }
72 }
73 }
74 }
75 return freeOpUser;
76}
77
78/// Checks if the given op allocates memory.
79static bool hasMemoryAllocEffect(MemoryEffectOpInterface memEffectOp) {
81 memEffectOp.getEffects(effects);
82 for (const auto &effect : effects) {
83 if (isa<MemoryEffects::Allocate>(effect.getEffect())) {
84 return true;
85 }
86 }
87 return false;
88}
89
90/// Extracts OpResult's with Allocate effects from given op
92collectAllocations(MemoryEffectOpInterface allocOp) {
94 allocOp.getEffects(effects);
95 SmallVector<OpResult> allocResults;
96 for (const MemoryEffects::EffectInstance &it : effects)
97 if (isa<MemoryEffects::Allocate>(it.getEffect()))
98 if (auto val = it.getValue(); val && val.getDefiningOp() == allocOp)
99 allocResults.push_back(cast<OpResult>(val));
100 return allocResults;
101}
102
103struct OptimizeAllocationLiveness
105 OptimizeAllocationLiveness> {
106public:
107 OptimizeAllocationLiveness() = default;
108
109 /// When moving a dealloc operation to be closer to its companion alloc we
110 /// have to consider the following. The dealloc should be:
111 /// - After all the operand definitions that the dealloc uses
112 /// - Before any ops that consume the results produced by the dealloc
113 /// To do this, we first ensure the "target" position is after all the
114 /// operands. Then we ensure this target dominates all consumers of the
115 /// dealloc's results. If not, no valid position exists and nullptr is
116 /// returned.
117 static Operation *findValidInsertionPoint(DominanceInfo *domInfo,
118 Operation *allocOp,
119 Operation *deallocOp,
120 Operation *lastUser) {
121
122 auto *target = lastUser;
123
124 // Start at the last user of the buffer, then move later if an operand of
125 // the dealloc is defined after it. E.g. target starts at %x but moves to
126 // %w:
127 // %x = memref.load %a[%c0] // lastUser
128 // %w = gpu.wait async [%d] // target
129 // %done = gpu.dealloc async [%w] %a : memref<8xf32> // deallocOp
130 for (Value operand : deallocOp->getOperands()) {
131 auto *definingOp = operand.getDefiningOp();
132 if (!definingOp)
133 continue;
134
135 if (!target || domInfo->properlyDominates(target, definingOp))
136 target = definingOp;
137 }
138
139 if (!target)
140 target = allocOp;
141
142 // Ensure target dominates all result users. Here the realloc is the
143 // deallocOp since it frees %a, and it also produces %b. The first loop
144 // leaves target at the memref.dealloc (the last user of the aliased
145 // buffer), but that op uses %b, so placing the realloc after it is invalid:
146 // %a = memref.alloc() : memref<8xf32>
147 // %b = memref.realloc %a : memref<8xf32> to memref<16xf32> // deallocOp
148 // memref.dealloc %b : memref<16xf32> // target
149 // nullptr is returned as a result.
150 for (Value result : deallocOp->getResults()) {
151 for (Operation *user : result.getUsers()) {
152 if (user == target ||
153 !domInfo->properlyDominates(target, user, /*enclosingOpOk=*/false))
154 return nullptr;
155 }
156 }
157 // Return the op to insert before
158 return target->getNextNode();
159 }
160
161 void runOnOperation() override {
162 func::FuncOp func = getOperation();
163
164 if (func.isExternal())
165 return;
166
167 BufferViewFlowAnalysis analysis = BufferViewFlowAnalysis(func);
168 auto domInfo = DominanceInfo();
169
170 func.walk([&](MemoryEffectOpInterface memEffectOp) -> WalkResult {
171 if (!hasMemoryAllocEffect(memEffectOp))
172 return WalkResult::advance();
173
174 auto allocOp = memEffectOp;
175 LDBG() << "Checking alloc op: " << allocOp;
176
177 SmallVector<OpResult> allocationResults = collectAllocations(allocOp);
178 // Multiple allocations from a single op are not considered here yet.
179 if (allocationResults.size() != 1)
180 return WalkResult::advance();
181
182 OpResult allocResult = allocationResults[0];
183 LDBG() << "On allocation result: " << allocResult;
184
185 auto *deallocOp = findUserWithFreeSideEffect(allocResult);
186 if (!deallocOp || (deallocOp->getBlock() != allocOp->getBlock())) {
187 // The pass handles allocations that have a single dealloc op in the
188 // same block. We also should not hoist the dealloc op out of
189 // conditionals.
190 return WalkResult::advance();
191 }
192
193 Operation *lastUser = nullptr;
195 analysis.resolve(allocResult);
196 for (auto dep : llvm::make_early_inc_range(deps)) {
197 for (auto *user : dep.getUsers()) {
198 // We are looking for a non dealloc op user.
199 // check if user is the dealloc op itself.
200 if (user == deallocOp)
201 continue;
202
203 // find the ancestor of user that is in the same block as the allocOp.
204 auto *topUser = allocOp->getBlock()->findAncestorOpInBlock(*user);
205 // A user outside the block cannot be ordered against the dealloc op.
206 if (!topUser)
207 return WalkResult::advance();
208 if (!lastUser || happensBefore(lastUser, topUser)) {
209 lastUser = topUser;
210 }
211 }
212 }
213 if (lastUser) {
214 LDBG() << "Last user found: " << *lastUser;
215 assert(lastUser->getBlock() == allocOp->getBlock());
216 assert(lastUser->getBlock() == deallocOp->getBlock());
217 } else {
218 LDBG() << "Last not user found";
219 }
220
221 // If no lastUser we can still try to optimize the position of the
222 // deallocOp
223 Operation *target =
224 findValidInsertionPoint(&domInfo, allocOp, deallocOp, lastUser);
225 if (!target) {
226 LDBG() << "No valid insertion point found; skipping move";
227 return WalkResult::advance();
228 }
229
230 deallocOp->moveBefore(target);
231 LDBG() << "Moved dealloc op before: " << *target;
232
233 return WalkResult::advance();
234 });
235 }
236};
237} // end anonymous namespace
static Operation * findValidInsertionPoint(Operation *emptyTensorOp, Operation *user, const SmallVector< Value > &neededValues)
Find a valid insertion point for a replacement of emptyTensorOp's use of user operation,...
b
Return true if permutation is a valid permutation of the outer_dims_perm (case OuterOrInnerPerm::Oute...
static bool happensBefore(Operation *a, Operation *b)
Return true if a happens before b, i.e., a or one of its ancestors properly dominates b and b is not ...
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:74
SmallPtrSet< Value, 16 > ValueSetT
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Operation is the basic unit of execution within MLIR.
Definition Operation.h:87
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
Block * getBlock()
Returns the operation block that contains this operation.
Definition Operation.h:230
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition Operation.h:251
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition Operation.h:405
void moveBefore(Operation *existingOp)
Unlink this operation from its current block and insert it right before existingOp which may be in th...
result_range getResults()
Definition Operation.h:442
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition Value.h:96
user_range getUsers() const
Definition Value.h:218
static WalkResult advance()
Definition WalkResult.h:47
SideEffects::EffectInstance< Effect > EffectInstance
detail::InFlightRemark analysis(Location loc, RemarkOpts opts)
Report an optimization analysis remark.
Definition Remarks.h:859
Include the generated interface declarations.