1//===- BufferDeallocationOpInterface.cpp ----------------------------------===//
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#include "mlir/Dialect/Bufferization/IR/BufferDeallocationOpInterface.h"
10#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
11#include "mlir/Dialect/MemRef/IR/MemRef.h"
12#include "mlir/IR/AsmState.h"
13#include "mlir/IR/Operation.h"
14#include "mlir/IR/TypeUtilities.h"
15#include "mlir/IR/Value.h"
16#include "llvm/ADT/SetOperations.h"
17
18//===----------------------------------------------------------------------===//
19// BufferDeallocationOpInterface
20//===----------------------------------------------------------------------===//
21
22namespace mlir {
23namespace bufferization {
24
25#include "mlir/Dialect/Bufferization/IR/BufferDeallocationOpInterface.cpp.inc"
26
27} // namespace bufferization
28} // namespace mlir
29
30using namespace mlir;
31using namespace bufferization;
32
33//===----------------------------------------------------------------------===//
34// Helpers
35//===----------------------------------------------------------------------===//
36
37static Value buildBoolValue(OpBuilder &builder, Location loc, bool value) {
38 return arith::ConstantOp::create(builder, location: loc, value: builder.getBoolAttr(value));
39}
40
41static bool isMemref(Value v) { return isa<BaseMemRefType>(Val: v.getType()); }
42
43//===----------------------------------------------------------------------===//
44// Ownership
45//===----------------------------------------------------------------------===//
46
47Ownership::Ownership(Value indicator)
48 : indicator(indicator), state(State::Unique) {}
49
50Ownership Ownership::getUnknown() {
51 Ownership unknown;
52 unknown.indicator = Value();
53 unknown.state = State::Unknown;
54 return unknown;
55}
56Ownership Ownership::getUnique(Value indicator) { return Ownership(indicator); }
57Ownership Ownership::getUninitialized() { return Ownership(); }
58
59bool Ownership::isUninitialized() const {
60 return state == State::Uninitialized;
61}
62bool Ownership::isUnique() const { return state == State::Unique; }
63bool Ownership::isUnknown() const { return state == State::Unknown; }
64
65Value Ownership::getIndicator() const {
66 assert(isUnique() && "must have unique ownership to get the indicator");
67 return indicator;
68}
69
70Ownership Ownership::getCombined(Ownership other) const {
71 if (other.isUninitialized())
72 return *this;
73 if (isUninitialized())
74 return other;
75
76 if (!isUnique() || !other.isUnique())
77 return getUnknown();
78
79 // Since we create a new constant i1 value for (almost) each use-site, we
80 // should compare the actual value rather than just the SSA Value to avoid
81 // unnecessary invalidations.
82 if (isEqualConstantIntOrValue(ofr1: indicator, ofr2: other.indicator))
83 return *this;
84
85 // Return the join of the lattice if the indicator of both ownerships cannot
86 // be merged.
87 return getUnknown();
88}
89
90void Ownership::combine(Ownership other) { *this = getCombined(other); }
91
92//===----------------------------------------------------------------------===//
93// DeallocationState
94//===----------------------------------------------------------------------===//
95
96DeallocationState::DeallocationState(Operation *op,
97 SymbolTableCollection &symbolTables)
98 : symbolTable(symbolTables), liveness(op) {}
99
100void DeallocationState::updateOwnership(Value memref, Ownership ownership,
101 Block *block) {
102 // In most cases we care about the block where the value is defined.
103 if (block == nullptr)
104 block = memref.getParentBlock();
105
106 // Update ownership of current memref itself.
107 ownershipMap[{memref, block}].combine(other: ownership);
108}
109
110void DeallocationState::resetOwnerships(ValueRange memrefs, Block *block) {
111 for (Value val : memrefs)
112 ownershipMap[{val, block}] = Ownership::getUninitialized();
113}
114
115Ownership DeallocationState::getOwnership(Value memref, Block *block) const {
116 return ownershipMap.lookup(Val: {memref, block});
117}
118
119void DeallocationState::addMemrefToDeallocate(Value memref, Block *block) {
120 memrefsToDeallocatePerBlock[block].push_back(Elt: memref);
121}
122
123void DeallocationState::dropMemrefToDeallocate(Value memref, Block *block) {
124 llvm::erase(C&: memrefsToDeallocatePerBlock[block], V: memref);
125}
126
127void DeallocationState::mapValue(Value oldValue, Value newValue) {
128 valueMapping[oldValue] = newValue;
129}
130
131void DeallocationState::getLiveMemrefsIn(Block *block,
132 SmallVectorImpl<Value> &memrefs) {
133 SmallVector<Value> liveMemrefs;
134 for (Value val : liveness.getLiveIn(block)) {
135 // Translate any value that was replaced (e.g., by appendOpResults) to its
136 // current equivalent before checking whether it is a MemRef.
137 if (Value mapped = valueMapping.lookup(Val: val))
138 val = mapped;
139 if (isMemref(v: val))
140 liveMemrefs.push_back(Elt: val);
141 }
142 llvm::sort(C&: liveMemrefs, Comp: ValueComparator());
143 memrefs.append(RHS: liveMemrefs);
144}
145
146std::pair<Value, Value>
147DeallocationState::getMemrefWithUniqueOwnership(OpBuilder &builder,
148 Value memref, Block *block) {
149 auto iter = ownershipMap.find(Val: {memref, block});
150 assert(iter != ownershipMap.end() &&
151 "Value must already have been registered in the ownership map");
152
153 Ownership ownership = iter->second;
154 if (ownership.isUnique())
155 return {memref, ownership.getIndicator()};
156
157 // Instead of inserting a clone operation we could also insert a dealloc
158 // operation earlier in the block and use the updated ownerships returned by
159 // the op for the retained values. Alternatively, we could insert code to
160 // check aliasing at runtime and use this information to combine two unique
161 // ownerships more intelligently to not end up with an 'Unknown' ownership in
162 // the first place.
163 auto cloneOp =
164 bufferization::CloneOp::create(builder, location: memref.getLoc(), value: memref);
165 Value condition = buildBoolValue(builder, loc: memref.getLoc(), value: true);
166 Value newMemref = cloneOp.getResult();
167 updateOwnership(memref: newMemref, ownership: condition);
168 memrefsToDeallocatePerBlock[newMemref.getParentBlock()].push_back(Elt: newMemref);
169 return {newMemref, condition};
170}
171
172void DeallocationState::getMemrefsToRetain(
173 Block *fromBlock, Block *toBlock, ValueRange destOperands,
174 SmallVectorImpl<Value> &toRetain) const {
175 for (Value operand : destOperands) {
176 if (!isMemref(v: operand))
177 continue;
178 toRetain.push_back(Elt: operand);
179 }
180
181 // Translate any value replaced during the transformation (e.g., when an op
182 // was cloned with extra results via appendOpResults) before checking whether
183 // it is a MemRef. The liveness analysis is computed once and may contain
184 // stale values after IR modifications.
185 auto translateValue = [&](Value val) -> Value {
186 if (Value mapped = valueMapping.lookup(Val: val))
187 return mapped;
188 return val;
189 };
190
191 SmallPtrSet<Value, 16> liveOut;
192 for (auto val : liveness.getLiveOut(block: fromBlock)) {
193 val = translateValue(val);
194 if (isMemref(v: val))
195 liveOut.insert(Ptr: val);
196 }
197
198 if (toBlock) {
199 SmallPtrSet<Value, 16> liveIn;
200 for (auto val : liveness.getLiveIn(block: toBlock)) {
201 val = translateValue(val);
202 if (isMemref(v: val))
203 liveIn.insert(Ptr: val);
204 }
205 llvm::set_intersect(S1&: liveOut, S2: liveIn);
206 }
207
208 // liveOut has non-deterministic order because it was constructed by iterating
209 // over a hash-set.
210 SmallVector<Value> retainedByLiveness(liveOut.begin(), liveOut.end());
211 llvm::sort(C&: retainedByLiveness, Comp: ValueComparator());
212 toRetain.append(RHS: retainedByLiveness);
213}
214
215LogicalResult DeallocationState::getMemrefsAndConditionsToDeallocate(
216 OpBuilder &builder, Location loc, Block *block,
217 SmallVectorImpl<Value> &memrefs, SmallVectorImpl<Value> &conditions) const {
218
219 for (auto [i, memref] :
220 llvm::enumerate(First: memrefsToDeallocatePerBlock.lookup(Val: block))) {
221 Ownership ownership = ownershipMap.lookup(Val: {memref, block});
222 if (!ownership.isUnique())
223 return emitError(loc: memref.getLoc(),
224 message: "MemRef value does not have valid ownership");
225
226 // Simply cast unranked MemRefs to ranked memrefs with 0 dimensions such
227 // that we can call extract_strided_metadata on it.
228 if (auto unrankedMemRefTy = dyn_cast<UnrankedMemRefType>(Val: memref.getType()))
229 memref = memref::ReinterpretCastOp::create(
230 builder, location: loc, source: memref,
231 /*offset=*/builder.getIndexAttr(value: 0),
232 /*sizes=*/ArrayRef<OpFoldResult>{},
233 /*strides=*/ArrayRef<OpFoldResult>{});
234
235 // Use the `memref.extract_strided_metadata` operation to get the base
236 // memref. This is needed because the same MemRef that was produced by the
237 // alloc operation has to be passed to the dealloc operation. Passing
238 // subviews, etc. to a dealloc operation is not allowed.
239 memrefs.push_back(
240 Elt: memref::ExtractStridedMetadataOp::create(builder, location: loc, source: memref)
241 .getResult(i: 0));
242 conditions.push_back(Elt: ownership.getIndicator());
243 }
244
245 return success();
246}
247
248//===----------------------------------------------------------------------===//
249// ValueComparator
250//===----------------------------------------------------------------------===//
251
252bool ValueComparator::operator()(const Value &lhs, const Value &rhs) const {
253 if (lhs == rhs)
254 return false;
255
256 // Block arguments are less than results.
257 bool lhsIsBBArg = isa<BlockArgument>(Val: lhs);
258 if (lhsIsBBArg != isa<BlockArgument>(Val: rhs)) {
259 return lhsIsBBArg;
260 }
261
262 Region *lhsRegion;
263 Region *rhsRegion;
264 if (lhsIsBBArg) {
265 auto lhsBBArg = llvm::cast<BlockArgument>(Val: lhs);
266 auto rhsBBArg = llvm::cast<BlockArgument>(Val: rhs);
267 if (lhsBBArg.getArgNumber() != rhsBBArg.getArgNumber()) {
268 return lhsBBArg.getArgNumber() < rhsBBArg.getArgNumber();
269 }
270 lhsRegion = lhsBBArg.getParentRegion();
271 rhsRegion = rhsBBArg.getParentRegion();
272 assert(lhsRegion != rhsRegion &&
273 "lhsRegion == rhsRegion implies lhs == rhs");
274 } else if (lhs.getDefiningOp() == rhs.getDefiningOp()) {
275 return llvm::cast<OpResult>(Val: lhs).getResultNumber() <
276 llvm::cast<OpResult>(Val: rhs).getResultNumber();
277 } else {
278 lhsRegion = lhs.getDefiningOp()->getParentRegion();
279 rhsRegion = rhs.getDefiningOp()->getParentRegion();
280 if (lhsRegion == rhsRegion) {
281 Block *lhsBlock = lhs.getDefiningOp()->getBlock();
282 Block *rhsBlock = rhs.getDefiningOp()->getBlock();
283 if (lhsBlock == rhsBlock) {
284 return lhs.getDefiningOp()->isBeforeInBlock(other: rhs.getDefiningOp());
285 }
286 return lhsBlock->computeBlockNumber() < rhsBlock->computeBlockNumber();
287 }
288 }
289
290 // lhsRegion != rhsRegion, so if we look at their ancestor chain, they
291 // - have different heights
292 // - or there's a spot where their region numbers differ
293 // - or their parent regions are the same and their parent ops are
294 // different.
295 while (lhsRegion && rhsRegion) {
296 if (lhsRegion->getRegionNumber() != rhsRegion->getRegionNumber()) {
297 return lhsRegion->getRegionNumber() < rhsRegion->getRegionNumber();
298 }
299 if (lhsRegion->getParentRegion() == rhsRegion->getParentRegion()) {
300 Block *lhsParentOpBlock = lhsRegion->getParentOp()->getBlock();
301 Block *rhsParentOpBlock = rhsRegion->getParentOp()->getBlock();
302 if (lhsParentOpBlock == rhsParentOpBlock) {
303 return lhsRegion->getParentOp()->isBeforeInBlock(
304 other: rhsRegion->getParentOp());
305 }
306 return lhsParentOpBlock->computeBlockNumber() <
307 rhsParentOpBlock->computeBlockNumber();
308 }
309 lhsRegion = lhsRegion->getParentRegion();
310 rhsRegion = rhsRegion->getParentRegion();
311 }
312 if (rhsRegion)
313 return true;
314 assert(lhsRegion && "this should only happen if lhs == rhs");
315 return false;
316}
317
318//===----------------------------------------------------------------------===//
319// Implementation utilities
320//===----------------------------------------------------------------------===//
321
322FailureOr<Operation *> deallocation_impl::insertDeallocOpForReturnLike(
323 DeallocationState &state, Operation *op, ValueRange operands,
324 SmallVectorImpl<Value> &updatedOperandOwnerships) {
325 assert(op->hasTrait<OpTrait::IsTerminator>() && "must be a terminator");
326 assert(!op->hasSuccessors() && "must not have any successors");
327 // Collect the values to deallocate and retain and use them to create the
328 // dealloc operation.
329 OpBuilder builder(op);
330 Block *block = op->getBlock();
331 SmallVector<Value> memrefs, conditions, toRetain;
332 if (failed(Result: state.getMemrefsAndConditionsToDeallocate(
333 builder, loc: op->getLoc(), block, memrefs, conditions)))
334 return failure();
335
336 state.getMemrefsToRetain(fromBlock: block, /*toBlock=*/nullptr, destOperands: operands, toRetain);
337 if (memrefs.empty() && toRetain.empty())
338 return op;
339
340 auto deallocOp = bufferization::DeallocOp::create(
341 builder, location: op->getLoc(), memrefs, conditions, retained: toRetain);
342
343 // We want to replace the current ownership of the retained values with the
344 // result values of the dealloc operation as they are always unique.
345 state.resetOwnerships(memrefs: deallocOp.getRetained(), block);
346 for (auto [retained, ownership] :
347 llvm::zip(t: deallocOp.getRetained(), u: deallocOp.getUpdatedConditions()))
348 state.updateOwnership(memref: retained, ownership, block);
349
350 unsigned numMemrefOperands = llvm::count_if(Range&: operands, P: isMemref);
351 auto newOperandOwnerships =
352 deallocOp.getUpdatedConditions().take_front(n: numMemrefOperands);
353 updatedOperandOwnerships.append(in_start: newOperandOwnerships.begin(),
354 in_end: newOperandOwnerships.end());
355
356 return op;
357}
358