1//===- OwnershipBasedBufferDeallocation.cpp - impl. for buffer dealloc. ---===//
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 logic for computing correct `bufferization.dealloc`
10// positions. Furthermore, buffer deallocation also adds required new clone
11// operations to ensure that memrefs returned by functions never alias an
12// argument.
13//
14// TODO:
15// The current implementation does not support explicit-control-flow loops and
16// the resulting code will be invalid with respect to program semantics.
17// However, structured control-flow loops are fully supported.
18//
19//===----------------------------------------------------------------------===//
20
21#include "mlir/Dialect/Bufferization/IR/BufferDeallocationOpInterface.h"
22#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
23#include "mlir/Dialect/Bufferization/Transforms/Passes.h"
24#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
25#include "mlir/Dialect/Func/IR/FuncOps.h"
26#include "mlir/Dialect/MemRef/IR/MemRef.h"
27#include "mlir/Dialect/SCF/IR/SCF.h"
28#include "mlir/IR/Iterators.h"
29#include "mlir/Interfaces/ControlFlowInterfaces.h"
30
31namespace mlir {
32namespace bufferization {
33#define GEN_PASS_DEF_OWNERSHIPBASEDBUFFERDEALLOCATIONPASS
34#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
35} // namespace bufferization
36} // namespace mlir
37
38using namespace mlir;
39using namespace mlir::bufferization;
40
41//===----------------------------------------------------------------------===//
42// Helpers
43//===----------------------------------------------------------------------===//
44
45static Value buildBoolValue(OpBuilder &builder, Location loc, bool value) {
46 return arith::ConstantOp::create(builder, location: loc, value: builder.getBoolAttr(value));
47}
48
49static bool isMemref(Value v) { return isa<BaseMemRefType>(Val: v.getType()); }
50
51/// Return "true" if the given op is guaranteed to have neither "Allocate" nor
52/// "Free" side effects.
53static bool hasNeitherAllocateNorFreeSideEffect(Operation *op) {
54 return !mightHaveEffect<MemoryEffects::Allocate>(op) &&
55 !mightHaveEffect<MemoryEffects::Free>(op);
56}
57
58/// Return "true" if the given op has buffer semantics. I.e., it has buffer
59/// operands, buffer results and/or buffer region entry block arguments.
60static bool hasBufferSemantics(Operation *op) {
61 if (llvm::any_of(Range: op->getOperands(), P: isMemref) ||
62 llvm::any_of(Range: op->getResults(), P: isMemref))
63 return true;
64 for (Region &region : op->getRegions())
65 if (!region.empty())
66 if (llvm::any_of(Range: region.front().getArguments(), P: isMemref))
67 return true;
68 return false;
69}
70
71//===----------------------------------------------------------------------===//
72// Backedges analysis
73//===----------------------------------------------------------------------===//
74
75namespace {
76
77/// A straight-forward program analysis which detects loop backedges induced by
78/// explicit control flow.
79class Backedges {
80public:
81 using BlockSetT = SmallPtrSet<Block *, 16>;
82 using BackedgeSetT = llvm::DenseSet<std::pair<Block *, Block *>>;
83
84public:
85 /// Constructs a new backedges analysis using the op provided.
86 Backedges(Operation *op) { recurse(op); }
87
88 /// Returns the number of backedges formed by explicit control flow.
89 size_t size() const { return edgeSet.size(); }
90
91 /// Returns the start iterator to loop over all backedges.
92 BackedgeSetT::const_iterator begin() const { return edgeSet.begin(); }
93
94 /// Returns the end iterator to loop over all backedges.
95 BackedgeSetT::const_iterator end() const { return edgeSet.end(); }
96
97private:
98 /// Enters the current block and inserts a backedge into the `edgeSet` if we
99 /// have already visited the current block. The inserted edge links the given
100 /// `predecessor` with the `current` block.
101 bool enter(Block &current, Block *predecessor) {
102 bool inserted = visited.insert(Ptr: &current).second;
103 if (!inserted)
104 edgeSet.insert(V: std::make_pair(x&: predecessor, y: &current));
105 return inserted;
106 }
107
108 /// Leaves the current block.
109 void exit(Block &current) { visited.erase(Ptr: &current); }
110
111 /// Recurses into the given operation while taking all attached regions into
112 /// account.
113 void recurse(Operation *op) {
114 Block *current = op->getBlock();
115 // If the current op implements the `BranchOpInterface`, there can be
116 // cycles in the scope of all successor blocks.
117 if (isa<BranchOpInterface>(Val: op)) {
118 for (Block *succ : current->getSuccessors())
119 recurse(block&: *succ, predecessor: current);
120 }
121 // Recurse into all distinct regions and check for explicit control-flow
122 // loops.
123 for (Region &region : op->getRegions()) {
124 if (!region.empty())
125 recurse(block&: region.front(), predecessor: current);
126 }
127 }
128
129 /// Recurses into explicit control-flow structures that are given by
130 /// the successor relation defined on the block level.
131 void recurse(Block &block, Block *predecessor) {
132 // Try to enter the current block. If this is not possible, we are
133 // currently processing this block and can safely return here.
134 if (!enter(current&: block, predecessor))
135 return;
136
137 // Recurse into all operations and successor blocks.
138 for (Operation &op : block.getOperations())
139 recurse(op: &op);
140
141 // Leave the current block.
142 exit(current&: block);
143 }
144
145 /// Stores all blocks that are currently visited and on the processing stack.
146 BlockSetT visited;
147
148 /// Stores all backedges in the format (source, target).
149 BackedgeSetT edgeSet;
150};
151
152} // namespace
153
154//===----------------------------------------------------------------------===//
155// BufferDeallocation
156//===----------------------------------------------------------------------===//
157
158namespace {
159/// The buffer deallocation transformation which ensures that all allocs in the
160/// program have a corresponding de-allocation.
161class BufferDeallocation {
162public:
163 BufferDeallocation(Operation *op, DeallocationOptions options,
164 SymbolTableCollection &symbolTables)
165 : state(op, symbolTables), options(options) {}
166
167 /// Performs the actual placement/creation of all dealloc operations.
168 LogicalResult deallocate(FunctionOpInterface op);
169
170private:
171 /// The base case for the recursive template below.
172 template <typename... T>
173 typename std::enable_if<sizeof...(T) == 0, FailureOr<Operation *>>::type
174 handleOp(Operation *op) {
175 return op;
176 }
177
178 /// Applies all the handlers of the interfaces in the template list
179 /// implemented by 'op'. In particular, if an operation implements more than
180 /// one of the interfaces in the template list, all the associated handlers
181 /// will be applied to the operation in the same order as the template list
182 /// specifies. If a handler reports a failure or removes the operation without
183 /// replacement (indicated by returning 'nullptr'), no further handlers are
184 /// applied and the return value is propagated to the caller of 'handleOp'.
185 ///
186 /// The interface handlers job is to update the deallocation state, most
187 /// importantly the ownership map and list of memrefs to potentially be
188 /// deallocated per block, but also to insert `bufferization.dealloc`
189 /// operations where needed. Obviously, no MemRefs that may be used at a later
190 /// point in the control-flow may be deallocated and the ownership map has to
191 /// be updated to reflect potential ownership changes caused by the dealloc
192 /// operation (e.g., if two interfaces on the same op insert a dealloc
193 /// operation each, the second one should query the ownership map and use them
194 /// as deallocation condition such that MemRefs already deallocated in the
195 /// first dealloc operation are not deallocated a second time (double-free)).
196 /// Note that currently only the interfaces on terminators may insert dealloc
197 /// operations and it is verified as a precondition that a terminator op must
198 /// implement exactly one of the interfaces handling dealloc insertion.
199 ///
200 /// The return value of the 'handleInterface' functions should be a
201 /// FailureOr<Operation *> indicating whether there was a failure or otherwise
202 /// returning the operation itself or a replacement operation.
203 ///
204 /// Note: The difference compared to `TypeSwitch` is that all
205 /// matching cases are applied instead of just the first match.
206 template <typename InterfaceT, typename... InterfacesU>
207 FailureOr<Operation *> handleOp(Operation *op) {
208 Operation *next = op;
209 if (auto concreteOp = dyn_cast<InterfaceT>(op)) {
210 FailureOr<Operation *> result = handleInterface(concreteOp);
211 if (failed(Result: result))
212 return failure();
213 next = *result;
214 }
215 if (!next)
216 return FailureOr<Operation *>(nullptr);
217 return handleOp<InterfacesU...>(next);
218 }
219
220 /// Apply all supported interface handlers to the given op.
221 FailureOr<Operation *> handleAllInterfaces(Operation *op) {
222 if (auto deallocOpInterface = dyn_cast<BufferDeallocationOpInterface>(Val: op))
223 return deallocOpInterface.process(state, options);
224
225 if (failed(Result: verifyOperationPreconditions(op)))
226 return failure();
227
228 return handleOp<MemoryEffectOpInterface, RegionBranchOpInterface,
229 CallOpInterface, BranchOpInterface,
230 RegionBranchTerminatorOpInterface>(op);
231 }
232
233 /// Make sure that for each forwarded MemRef value, an ownership indicator
234 /// `i1` value is forwarded as well such that the successor block knows
235 /// whether the MemRef has to be deallocated.
236 ///
237 /// Example:
238 /// ```
239 /// ^bb1:
240 /// <more ops...>
241 /// cf.br ^bb2(<forward-to-bb2>)
242 /// ```
243 /// becomes
244 /// ```
245 /// // let (m, c) = getMemrefsAndConditionsToDeallocate(bb1)
246 /// // let r = getMemrefsToRetain(bb1, bb2, <forward-to-bb2>)
247 /// ^bb1:
248 /// <more ops...>
249 /// o = bufferization.dealloc m if c retain r
250 /// // replace ownership(r) with o element-wise
251 /// cf.br ^bb2(<forward-to-bb2>, o)
252 /// ```
253 FailureOr<Operation *> handleInterface(BranchOpInterface op);
254
255 /// Add an ownership indicator for every forwarding MemRef operand and result.
256 /// Nested regions never take ownership of MemRefs owned by a parent region
257 /// (neither via forwarding operand nor when captured implicitly when the
258 /// region is not isolated from above). Ownerships will only be passed to peer
259 /// regions (when an operation has multiple regions, such as scf.while), or to
260 /// parent regions.
261 /// Note that the block arguments in the nested region are currently handled
262 /// centrally in the 'dealloc' function, but better interface support could
263 /// allow us to do this here for the nested region specifically to reduce the
264 /// amount of assumptions we make on the structure of ops implementing this
265 /// interface.
266 ///
267 /// Example:
268 /// ```
269 /// %ret = scf.for %i = %c0 to %c10 step %c1 iter_args(%m = %memref) {
270 /// <more ops...>
271 /// scf.yield %m : memref<2xi32>, i1
272 /// }
273 /// ```
274 /// becomes
275 /// ```
276 /// %ret:2 = scf.for %i = %c0 to %c10 step %c1
277 /// iter_args(%m = %memref, %own = %false) {
278 /// <more ops...>
279 /// // Note that the scf.yield is handled by the
280 /// // RegionBranchTerminatorOpInterface (not this handler)
281 /// // let o = getMemrefWithUniqueOwnership(%own)
282 /// scf.yield %m, o : memref<2xi32>, i1
283 /// }
284 /// ```
285 FailureOr<Operation *> handleInterface(RegionBranchOpInterface op);
286
287 /// If the private-function-dynamic-ownership pass option is enabled and the
288 /// called function is private, additional results are added for each MemRef
289 /// result to pass the dynamic ownership indicator along. Otherwise, updates
290 /// the ownership map and list of memrefs to be deallocated according to the
291 /// function boundary ABI, i.e., assume ownership of all returned MemRefs.
292 ///
293 /// Example (assume `private-function-dynamic-ownership` is enabled):
294 /// ```
295 /// func.func @f(%arg0: memref<2xi32>) -> memref<2xi32> {...}
296 /// func.func private @g(%arg0: memref<2xi32>) -> memref<2xi32> {...}
297 ///
298 /// %ret_f = func.call @f(%memref) : (memref<2xi32>) -> memref<2xi32>
299 /// %ret_g = func.call @g(%memref) : (memref<2xi32>) -> memref<2xi32>
300 /// ```
301 /// becomes
302 /// ```
303 /// func.func @f(%arg0: memref<2xi32>) -> memref<2xi32> {...}
304 /// func.func private @g(%arg0: memref<2xi32>) -> (memref<2xi32>, i1) {...}
305 ///
306 /// %ret_f = func.call @f(%memref) : (memref<2xi32>) -> memref<2xi32>
307 /// // set ownership(%ret_f) := true
308 /// // remember to deallocate %ret_f
309 ///
310 /// %ret_g:2 = func.call @g(%memref) : (memref<2xi32>) -> (memref<2xi32>, i1)
311 /// // set ownership(%ret_g#0) := %ret_g#1
312 /// // remember to deallocate %ret_g if it comes with ownership
313 /// ```
314 FailureOr<Operation *> handleInterface(CallOpInterface op);
315
316 /// Takes care of allocation and free side-effects. It collects allocated
317 /// MemRefs that we have to add to manually deallocate, but also removes
318 /// values again that are already deallocated before the end of the block. It
319 /// also updates the ownership map accordingly.
320 ///
321 /// Example:
322 /// ```
323 /// %alloc = memref.alloc()
324 /// %alloca = memref.alloca()
325 /// ```
326 /// becomes
327 /// ```
328 /// %alloc = memref.alloc()
329 /// %alloca = memref.alloca()
330 /// // set ownership(alloc) := true
331 /// // set ownership(alloca) := false
332 /// // remember to deallocate %alloc
333 /// ```
334 FailureOr<Operation *> handleInterface(MemoryEffectOpInterface op);
335
336 /// Takes care that the function boundary ABI is adhered to if the parent
337 /// operation implements FunctionOpInterface, inserting a
338 /// `bufferization.clone` if necessary, and inserts the
339 /// `bufferization.dealloc` operation according to the ops operands.
340 ///
341 /// Example:
342 /// ```
343 /// ^bb1:
344 /// <more ops...>
345 /// func.return <return-vals>
346 /// ```
347 /// becomes
348 /// ```
349 /// // let (m, c) = getMemrefsAndConditionsToDeallocate(bb1)
350 /// // let r = getMemrefsToRetain(bb1, nullptr, <return-vals>)
351 /// ^bb1:
352 /// <more ops...>
353 /// o = bufferization.dealloc m if c retain r
354 /// func.return <return-vals>
355 /// (if !isFunctionWithoutDynamicOwnership: append o)
356 /// ```
357 FailureOr<Operation *> handleInterface(RegionBranchTerminatorOpInterface op);
358
359 /// Construct a new operation which is exactly the same as the passed 'op'
360 /// except that the OpResults list is appended by new results of the passed
361 /// 'types'.
362 /// TODO: ideally, this would be implemented using an OpInterface because it
363 /// is used to append function results, loop iter_args, etc. and thus makes
364 /// some assumptions that the variadic list of those is at the end of the
365 /// OpResults range.
366 Operation *appendOpResults(Operation *op, ArrayRef<Type> types);
367
368 /// A convenience template for the generic 'appendOpResults' function above to
369 /// avoid manual casting of the result.
370 template <typename OpTy>
371 OpTy appendOpResults(OpTy op, ArrayRef<Type> types) {
372 return cast<OpTy>(appendOpResults(op.getOperation(), types));
373 }
374
375 /// Performs deallocation of a single basic block. This is a private function
376 /// because some internal data structures have to be set up beforehand and
377 /// this function has to be called on blocks in a region in dominance order.
378 LogicalResult deallocate(Block *block);
379
380 /// After all relevant interfaces of an operation have been processed by the
381 /// 'handleInterface' functions, this function sets the ownership of operation
382 /// results that have not been set yet by the 'handleInterface' functions. It
383 /// generally assumes that each result can alias with every operand of the
384 /// operation, if there are MemRef typed results but no MemRef operands it
385 /// assigns 'false' as ownership. This happens, e.g., for the
386 /// memref.get_global operation. It would also be possible to query some alias
387 /// analysis to get more precise ownerships, however, the analysis would have
388 /// to be updated according to the IR modifications this pass performs (e.g.,
389 /// re-building operations to have more result values, inserting clone
390 /// operations, etc.).
391 void populateRemainingOwnerships(Operation *op);
392
393 /// Given an SSA value of MemRef type, returns the same of a new SSA value
394 /// which has 'Unique' ownership where the ownership indicator is guaranteed
395 /// to be always 'true'.
396 Value materializeMemrefWithGuaranteedOwnership(OpBuilder &builder,
397 Value memref, Block *block);
398
399 /// Returns whether the given operation implements FunctionOpInterface, has
400 /// private visibility, and the private-function-dynamic-ownership pass option
401 /// is enabled.
402 bool isFunctionWithoutDynamicOwnership(Operation *op);
403
404 /// Given an SSA value of MemRef type, this function queries the
405 /// BufferDeallocationOpInterface of the defining operation of 'memref' for a
406 /// materialized ownership indicator for 'memref'. If the op does not
407 /// implement the interface or if the block for which the materialized value
408 /// is requested does not match the block in which 'memref' is defined, the
409 /// default implementation in
410 /// `DeallocationState::getMemrefWithUniqueOwnership` is queried instead.
411 std::pair<Value, Value>
412 materializeUniqueOwnership(OpBuilder &builder, Value memref, Block *block);
413
414 /// Checks all the preconditions for operations implementing the
415 /// FunctionOpInterface that have to hold for the deallocation to be
416 /// applicable:
417 /// (1) Checks that there are not explicit control flow loops.
418 static LogicalResult verifyFunctionPreconditions(FunctionOpInterface op);
419
420 /// Checks all the preconditions for operations inside the region of
421 /// operations implementing the FunctionOpInterface that have to hold for the
422 /// deallocation to be applicable:
423 /// (1) Checks if all operations that have at least one attached region
424 /// implement the RegionBranchOpInterface. This is not required in edge cases,
425 /// where we have a single attached region and the parent operation has no
426 /// results.
427 /// (2) Checks that no deallocations already exist. Especially deallocations
428 /// in nested regions are not properly supported yet since this requires
429 /// ownership of the memref to be transferred to the nested region, which does
430 /// not happen by default. This constrained can be lifted in the future.
431 /// (3) Checks that terminators with more than one successor except
432 /// `cf.cond_br` are not present and that either BranchOpInterface or
433 /// RegionBranchTerminatorOpInterface is implemented.
434 static LogicalResult verifyOperationPreconditions(Operation *op);
435
436 /// When the 'private-function-dynamic-ownership' pass option is enabled,
437 /// additional `i1` return values are added for each MemRef result in the
438 /// function signature. This function takes care of updating the
439 /// `function_type` attribute of the function according to the actually
440 /// returned values from the terminators.
441 static LogicalResult updateFunctionSignature(FunctionOpInterface op);
442
443private:
444 /// Collects all analysis state and including liveness, caches, ownerships of
445 /// already processed values and operations, and the MemRefs that have to be
446 /// deallocated at the end of each block.
447 DeallocationState state;
448
449 /// Collects all pass options in a single place.
450 DeallocationOptions options;
451};
452
453} // namespace
454
455//===----------------------------------------------------------------------===//
456// BufferDeallocation Implementation
457//===----------------------------------------------------------------------===//
458
459std::pair<Value, Value>
460BufferDeallocation::materializeUniqueOwnership(OpBuilder &builder, Value memref,
461 Block *block) {
462 // The interface can only materialize ownership indicators in the same block
463 // as the defining op.
464 if (memref.getParentBlock() != block)
465 return state.getMemrefWithUniqueOwnership(builder, memref, block);
466
467 Operation *owner = memref.getDefiningOp();
468 if (!owner)
469 owner = memref.getParentBlock()->getParentOp();
470
471 // If the op implements the interface, query it for a materialized ownership
472 // value.
473 if (auto deallocOpInterface = dyn_cast<BufferDeallocationOpInterface>(Val: owner))
474 return deallocOpInterface.materializeUniqueOwnershipForMemref(
475 state, options, builder, memref);
476
477 // Otherwise use the default implementation.
478 return state.getMemrefWithUniqueOwnership(builder, memref, block);
479}
480
481LogicalResult
482BufferDeallocation::verifyFunctionPreconditions(FunctionOpInterface op) {
483 // (1) Ensure that there are supported loops only (no explicit control flow
484 // loops).
485 Backedges backedges(op);
486 if (backedges.size()) {
487 op->emitError(message: "Only structured control-flow loops are supported.");
488 return failure();
489 }
490
491 return success();
492}
493
494LogicalResult BufferDeallocation::verifyOperationPreconditions(Operation *op) {
495 // We do not care about ops that do not operate on buffers and have no
496 // Allocate/Free side effect.
497 if (!hasBufferSemantics(op) && hasNeitherAllocateNorFreeSideEffect(op))
498 return success();
499
500 // (1) The pass does not work properly when deallocations are already present.
501 // Alternatively, we could also remove all deallocations as a pre-pass.
502 if (isa<DeallocOp>(Val: op))
503 return op->emitError(
504 message: "No deallocation operations must be present when running this pass!");
505
506 // (2) Memory side effects of unregistered ops are unknown. In particular, we
507 // do not know whether an unregistered op allocates memory or not.
508 // - Ops with recursive memory effects are allowed. All nested ops in the
509 // regions of `op` will be analyzed separately.
510 // - Call ops are allowed even though they typically do not implement the
511 // MemoryEffectOpInterface. They usually do not have side effects apart
512 // from the callee, which will be analyzed separately. (This is similar to
513 // "recursive memory effects".)
514 if (hasUnknownEffects(op) && !isa<CallOpInterface>(Val: op))
515 return op->emitError(
516 message: "ops with unknown memory side effects are not supported");
517
518 // (3) Check that the control flow structures are supported.
519 auto regions = op->getRegions();
520 // Check that if the operation has at
521 // least one region it implements the RegionBranchOpInterface. If there
522 // is an operation that does not fulfill this condition, we cannot apply
523 // the deallocation steps. Furthermore, we accept cases, where we have a
524 // region that returns no results, since, in that case, the intra-region
525 // control flow does not affect the transformation.
526 size_t size = regions.size();
527 if (((size == 1 && !op->getResults().empty()) || size > 1) &&
528 !dyn_cast<RegionBranchOpInterface>(Val: op)) {
529 return op->emitError(message: "All operations with attached regions need to "
530 "implement the RegionBranchOpInterface.");
531 }
532
533 // (3) Check that terminators with more than one successor except `cf.cond_br`
534 // are not present and that either BranchOpInterface or
535 // RegionBranchTerminatorOpInterface is implemented.
536 if (op->hasTrait<OpTrait::NoTerminator>())
537 return op->emitError(message: "NoTerminator trait is not supported");
538
539 if (op->hasTrait<OpTrait::IsTerminator>()) {
540 // Either one of those interfaces has to be implemented on terminators, but
541 // not both.
542 if (!isa<BranchOpInterface, RegionBranchTerminatorOpInterface>(Val: op) ||
543 (isa<BranchOpInterface>(Val: op) &&
544 isa<RegionBranchTerminatorOpInterface>(Val: op)))
545
546 return op->emitError(
547 message: "Terminators must implement either BranchOpInterface or "
548 "RegionBranchTerminatorOpInterface (but not both)!");
549
550 // We only support terminators with 0 or 1 successors for now and
551 // special-case the conditional branch op.
552 if (op->getSuccessors().size() > 1)
553
554 return op->emitError(message: "Terminators with more than one successor "
555 "are not supported!");
556 }
557
558 return success();
559}
560
561LogicalResult
562BufferDeallocation::updateFunctionSignature(FunctionOpInterface op) {
563 SmallVector<TypeRange> returnOperandTypes(llvm::map_range(
564 C: op.getFunctionBody().getOps<RegionBranchTerminatorOpInterface>(),
565 F: [&](RegionBranchTerminatorOpInterface branchOp) {
566 return branchOp.getSuccessorOperands(successor: RegionSuccessor(op.getOperation()))
567 .getTypes();
568 }));
569 if (!llvm::all_equal(Range&: returnOperandTypes))
570 return op->emitError(
571 message: "there are multiple return operations with different operand types");
572
573 TypeRange resultTypes = op.getResultTypes();
574 // Check if we found a return operation because that doesn't necessarily
575 // always have to be the case, e.g., consider a function with one block that
576 // has a cf.br at the end branching to itself again (i.e., an infinite loop).
577 // In that case we don't want to crash but just not update the return types.
578 if (!returnOperandTypes.empty())
579 resultTypes = returnOperandTypes[0];
580
581 op.setFunctionTypeAttr(TypeAttr::get(type: FunctionType::get(
582 context: op->getContext(), inputs: op.getFunctionBody().front().getArgumentTypes(),
583 results: resultTypes)));
584
585 return success();
586}
587
588LogicalResult BufferDeallocation::deallocate(FunctionOpInterface op) {
589 // Stop and emit a proper error message if we don't support the input IR.
590 if (failed(Result: verifyFunctionPreconditions(op)))
591 return failure();
592
593 // Process the function block by block.
594 auto result = op->walk<WalkOrder::PostOrder, ForwardDominanceIterator<>>(
595 callback: [&](Block *block) {
596 if (failed(Result: deallocate(block)))
597 return WalkResult::interrupt();
598 return WalkResult::advance();
599 });
600 if (result.wasInterrupted())
601 return failure();
602
603 // Update the function signature if the function is private, dynamic ownership
604 // is enabled, and the function has memrefs as arguments or results.
605 return updateFunctionSignature(op);
606}
607
608LogicalResult BufferDeallocation::deallocate(Block *block) {
609 OpBuilder builder = OpBuilder::atBlockBegin(block);
610
611 // Compute liveness transfers of ownership to this block.
612 SmallVector<Value> liveMemrefs;
613 state.getLiveMemrefsIn(block, memrefs&: liveMemrefs);
614 for (auto li : liveMemrefs) {
615 // Ownership of implicitly captured memrefs from other regions is never
616 // taken, but ownership of memrefs in the same region (but different block)
617 // is taken.
618 if (li.getParentRegion() == block->getParent()) {
619 state.updateOwnership(memref: li, ownership: state.getOwnership(memref: li, block: li.getParentBlock()),
620 block);
621 state.addMemrefToDeallocate(memref: li, block);
622 continue;
623 }
624
625 if (li.getParentRegion()->isProperAncestor(other: block->getParent())) {
626 Value falseVal = buildBoolValue(builder, loc: li.getLoc(), value: false);
627 state.updateOwnership(memref: li, ownership: falseVal, block);
628 }
629 }
630
631 for (unsigned i = 0, e = block->getNumArguments(); i < e; ++i) {
632 BlockArgument arg = block->getArgument(i);
633 if (!isMemref(v: arg))
634 continue;
635
636 // Adhere to function boundary ABI: no ownership of function argument
637 // MemRefs is taken.
638 if (isa<FunctionOpInterface>(Val: block->getParentOp()) &&
639 block->isEntryBlock()) {
640 Value newArg = buildBoolValue(builder, loc: arg.getLoc(), value: false);
641 state.updateOwnership(memref: arg, ownership: newArg);
642 state.addMemrefToDeallocate(memref: arg, block);
643 continue;
644 }
645
646 // Pass MemRef ownerships along via `i1` values.
647 Value newArg = block->addArgument(type: builder.getI1Type(), loc: arg.getLoc());
648 state.updateOwnership(memref: arg, ownership: newArg);
649 state.addMemrefToDeallocate(memref: arg, block);
650 }
651
652 // For each operation in the block, handle the interfaces that affect aliasing
653 // and ownership of memrefs.
654 for (Operation &op : llvm::make_early_inc_range(Range&: *block)) {
655 FailureOr<Operation *> result = handleAllInterfaces(op: &op);
656 if (failed(Result: result))
657 return failure();
658 if (!*result)
659 continue;
660
661 populateRemainingOwnerships(op: *result);
662 }
663
664 // TODO: if block has no terminator, handle dealloc insertion here.
665 return success();
666}
667
668Operation *BufferDeallocation::appendOpResults(Operation *op,
669 ArrayRef<Type> types) {
670 SmallVector<Type> newTypes(op->getResultTypes());
671 // Save the old result values before appendOpResults erases the op. The
672 // liveness analysis holds references to these values and they may be queried
673 // later (e.g., from handleInterface(BranchOpInterface) in the same block).
674 SmallVector<Value> oldResults(op->getResults());
675
676 newTypes.append(in_start: types.begin(), in_end: types.end());
677 auto *newOp = Operation::create(
678 location: op->getLoc(), name: op->getName(), resultTypes: newTypes, operands: op->getOperands(),
679 attributes: op->getDiscardableAttrDictionary(), properties: op->getPropertiesStorage(),
680 successors: op->getSuccessors(), numRegions: op->getNumRegions());
681 for (auto [oldRegion, newRegion] :
682 llvm::zip(t: op->getRegions(), u: newOp->getRegions()))
683 newRegion.takeBody(other&: oldRegion);
684
685 OpBuilder(op).insert(op: newOp);
686 op->replaceAllUsesWith(values: newOp->getResults().take_front(n: op->getNumResults()));
687 op->erase();
688
689 // Register the replacement of each old result with the corresponding new
690 // result so that stale liveness entries can be translated on demand.
691 for (auto [oldResult, newResult] :
692 llvm::zip(t&: oldResults, u: newOp->getResults().take_front(n: oldResults.size())))
693 state.mapValue(oldValue: oldResult, newValue: newResult);
694
695 return newOp;
696}
697
698FailureOr<Operation *>
699BufferDeallocation::handleInterface(RegionBranchOpInterface op) {
700 OpBuilder builder = OpBuilder::atBlockBegin(block: op->getBlock());
701
702 // TODO: the RegionBranchOpInterface does not provide all the necessary
703 // methods to perform this transformation without additional assumptions on
704 // the structure. In particular, that
705 // * additional values to be passed to the next region can be added to the end
706 // of the operand list, the end of the block argument list, and the end of
707 // the result value list. However, it seems to be the general guideline for
708 // operations implementing this interface to follow this structure.
709 // * and that the block arguments and result values match the forwarded
710 // operands one-to-one (i.e., that there are no other values appended to the
711 // front).
712 // These assumptions are satisfied by the `scf.if`, `scf.for`, and `scf.while`
713 // operations.
714
715 SmallVector<RegionSuccessor> regions;
716 op.getSuccessorRegions(point: RegionBranchPoint::parent(), regions);
717 assert(!regions.empty() && "Must have at least one successor region");
718 SmallVector<Value> entryOperands(
719 op.getEntrySuccessorOperands(successor: regions.front()));
720 unsigned numMemrefOperands = llvm::count_if(Range&: entryOperands, P: isMemref);
721
722 // No ownership is acquired for any MemRefs that are passed to the region from
723 // the outside.
724 Value falseVal = buildBoolValue(builder, loc: op.getLoc(), value: false);
725 op->insertOperands(index: op->getNumOperands(),
726 operands: Repeated<Value>(numMemrefOperands, falseVal));
727
728 int counter = op->getNumResults();
729 unsigned numMemrefResults = llvm::count_if(Range: op->getResults(), P: isMemref);
730 SmallVector<Type> ownershipResults(numMemrefResults, builder.getI1Type());
731 RegionBranchOpInterface newOp = appendOpResults(op, types: ownershipResults);
732
733 for (auto result : llvm::make_filter_range(Range: newOp->getResults(), Pred: isMemref)) {
734 state.updateOwnership(memref: result, ownership: newOp->getResult(idx: counter++));
735 state.addMemrefToDeallocate(memref: result, block: newOp->getBlock());
736 }
737
738 return newOp.getOperation();
739}
740
741Value BufferDeallocation::materializeMemrefWithGuaranteedOwnership(
742 OpBuilder &builder, Value memref, Block *block) {
743 // First, make sure we at least have 'Unique' ownership already.
744 std::pair<Value, Value> newMemrefAndOnwership =
745 materializeUniqueOwnership(builder, memref, block);
746 Value newMemref = newMemrefAndOnwership.first;
747 Value condition = newMemrefAndOnwership.second;
748
749 // Avoid inserting additional IR if ownership is already guaranteed. In
750 // particular, this is already the case when we had 'Unknown' ownership
751 // initially and a clone was inserted to get to 'Unique' ownership.
752 if (matchPattern(value: condition, pattern: m_One()))
753 return newMemref;
754
755 // Insert a runtime check and only clone if we still don't have ownership at
756 // runtime.
757 Value maybeClone = scf::IfOp::create(
758 builder, location: memref.getLoc(), cond: condition,
759 thenBuilder: [&](OpBuilder &builder, Location loc) {
760 scf::YieldOp::create(builder, location: loc, results: newMemref);
761 },
762 elseBuilder: [&](OpBuilder &builder, Location loc) {
763 Value clone = bufferization::CloneOp::create(
764 builder, location: loc, value: newMemref);
765 scf::YieldOp::create(builder, location: loc, results: clone);
766 })
767 .getResult(i: 0);
768 Value trueVal = buildBoolValue(builder, loc: memref.getLoc(), value: true);
769 state.updateOwnership(memref: maybeClone, ownership: trueVal);
770 state.addMemrefToDeallocate(memref: maybeClone, block: maybeClone.getParentBlock());
771 return maybeClone;
772}
773
774FailureOr<Operation *>
775BufferDeallocation::handleInterface(BranchOpInterface op) {
776 if (op->getNumSuccessors() > 1)
777 return op->emitError(message: "BranchOpInterface operations with multiple "
778 "successors are not supported yet");
779
780 if (op->getNumSuccessors() != 1)
781 return emitError(loc: op.getLoc(),
782 message: "only BranchOpInterface operations with exactly "
783 "one successor are supported yet");
784
785 if (op.getSuccessorOperands(index: 0).getProducedOperandCount() > 0)
786 return op.emitError(message: "produced operands are not supported");
787
788 // Collect the values to deallocate and retain and use them to create the
789 // dealloc operation.
790 Block *block = op->getBlock();
791 OpBuilder builder(op);
792 SmallVector<Value> memrefs, conditions, toRetain;
793 if (failed(Result: state.getMemrefsAndConditionsToDeallocate(
794 builder, loc: op.getLoc(), block, memrefs, conditions)))
795 return failure();
796
797 OperandRange forwardedOperands =
798 op.getSuccessorOperands(index: 0).getForwardedOperands();
799 state.getMemrefsToRetain(fromBlock: block, toBlock: op->getSuccessor(index: 0), destOperands: forwardedOperands,
800 toRetain);
801
802 auto deallocOp = bufferization::DeallocOp::create(
803 builder, location: op.getLoc(), memrefs, conditions, retained: toRetain);
804
805 // We want to replace the current ownership of the retained values with the
806 // result values of the dealloc operation as they are always unique.
807 state.resetOwnerships(memrefs: deallocOp.getRetained(), block);
808 for (auto [retained, ownership] :
809 llvm::zip(t: deallocOp.getRetained(), u: deallocOp.getUpdatedConditions())) {
810 state.updateOwnership(memref: retained, ownership, block);
811 }
812
813 unsigned numAdditionalReturns = llvm::count_if(Range&: forwardedOperands, P: isMemref);
814 SmallVector<Value> newOperands(forwardedOperands);
815 auto additionalConditions =
816 deallocOp.getUpdatedConditions().take_front(n: numAdditionalReturns);
817 newOperands.append(in_start: additionalConditions.begin(), in_end: additionalConditions.end());
818 op.getSuccessorOperands(index: 0).getMutableForwardedOperands().assign(values: newOperands);
819
820 return op.getOperation();
821}
822
823FailureOr<Operation *> BufferDeallocation::handleInterface(CallOpInterface op) {
824 OpBuilder builder(op);
825
826 // Lookup the function operation and check if it has private visibility. If
827 // the function is referenced by SSA value instead of a Symbol, it's assumed
828 // to be public. (And we cannot easily change the type of the SSA value
829 // anyway.)
830 Operation *funcOp = op.resolveCallableInTable(symbolTable: state.getSymbolTable());
831 bool isPrivate = false;
832 if (auto symbol = dyn_cast_or_null<SymbolOpInterface>(Val: funcOp))
833 isPrivate = symbol.isPrivate() && !symbol.isDeclaration();
834
835 // If the private-function-dynamic-ownership option is enabled and we are
836 // calling a private function, we need to add an additional `i1` result for
837 // each MemRef result to dynamically pass the current ownership indicator
838 // rather than adhering to the function boundary ABI.
839 if (options.privateFuncDynamicOwnership && isPrivate) {
840 unsigned numMemrefs = llvm::count_if(Range: op->getResults(), P: isMemref);
841 SmallVector<Type> ownershipTypesToAppend(numMemrefs, builder.getI1Type());
842 unsigned ownershipCounter = op->getNumResults();
843 op = appendOpResults(op, types: ownershipTypesToAppend);
844
845 for (auto result : llvm::make_filter_range(Range: op->getResults(), Pred: isMemref)) {
846 state.updateOwnership(memref: result, ownership: op->getResult(idx: ownershipCounter++));
847 state.addMemrefToDeallocate(memref: result, block: result.getParentBlock());
848 }
849
850 return op.getOperation();
851 }
852
853 // According to the function boundary ABI we are guaranteed to get ownership
854 // of all MemRefs returned by the function. Thus we set ownership to constant
855 // 'true' and remember to deallocate it.
856 Value trueVal = buildBoolValue(builder, loc: op.getLoc(), value: true);
857 for (auto result : llvm::make_filter_range(Range: op->getResults(), Pred: isMemref)) {
858 state.updateOwnership(memref: result, ownership: trueVal);
859 state.addMemrefToDeallocate(memref: result, block: result.getParentBlock());
860 }
861
862 return op.getOperation();
863}
864
865FailureOr<Operation *>
866BufferDeallocation::handleInterface(MemoryEffectOpInterface op) {
867 auto *block = op->getBlock();
868 OpBuilder builder = OpBuilder::atBlockBegin(block);
869
870 for (auto operand : llvm::make_filter_range(Range: op->getOperands(), Pred: isMemref)) {
871 if (op.getEffectOnValue<MemoryEffects::Free>(value: operand).has_value()) {
872 // The bufferization.manual_deallocation attribute can be attached to ops
873 // with an allocation and/or deallocation side effect. It indicates that
874 // the op is under a "manual deallocation" scheme. Deallocation ops are
875 // usually forbidden in the input IR (not supported by the buffer
876 // deallocation pass). However, if they are under manual deallocation,
877 // they can be safely ignored by the buffer deallocation pass.
878 if (!op->hasDiscardableAttr(name: BufferizationDialect::kManualDeallocation))
879 return op->emitError(
880 message: "memory free side-effect on MemRef value not supported!");
881
882 // Buffers that were allocated under "manual deallocation" may be
883 // manually deallocated. We insert a runtime assertion to cover certain
884 // cases of invalid IR where an automatically managed buffer allocation
885 // is manually deallocated. This is not a bulletproof check!
886 OpBuilder::InsertionGuard g(builder);
887 builder.setInsertionPoint(op);
888 Ownership ownership = state.getOwnership(memref: operand, block);
889 if (ownership.isUnique()) {
890 Value ownershipInverted = arith::XOrIOp::create(
891 builder, location: op.getLoc(), lhs: ownership.getIndicator(),
892 rhs: buildBoolValue(builder, loc: op.getLoc(), value: true));
893 cf::AssertOp::create(builder, location: op.getLoc(), arg: ownershipInverted,
894 msg: "expected that the block does not have ownership");
895 }
896 }
897 }
898
899 for (auto res : llvm::make_filter_range(Range: op->getResults(), Pred: isMemref)) {
900 auto allocEffect = op.getEffectOnValue<MemoryEffects::Allocate>(value: res);
901 if (allocEffect.has_value()) {
902 if (isa<SideEffects::AutomaticAllocationScopeResource>(
903 Val: allocEffect->getResource())) {
904 // Make sure that the ownership of auto-managed allocations is set to
905 // false. This is important for operations that have at least one memref
906 // typed operand. E.g., consider an operation like `bufferization.clone`
907 // that lowers to a `memref.alloca + memref.copy` instead of a
908 // `memref.alloc`. If we wouldn't set the ownership of the result here,
909 // the default ownership population in `populateRemainingOwnerships`
910 // would assume aliasing with the MemRef operand.
911 state.resetOwnerships(memrefs: res, block);
912 state.updateOwnership(memref: res, ownership: buildBoolValue(builder, loc: op.getLoc(), value: false));
913 continue;
914 }
915
916 if (op->hasDiscardableAttr(name: BufferizationDialect::kManualDeallocation)) {
917 // This allocation will be deallocated manually. Assign an ownership of
918 // "false", so that it will never be deallocated by the buffer
919 // deallocation pass.
920 state.resetOwnerships(memrefs: res, block);
921 state.updateOwnership(memref: res, ownership: buildBoolValue(builder, loc: op.getLoc(), value: false));
922 continue;
923 }
924
925 state.updateOwnership(memref: res, ownership: buildBoolValue(builder, loc: op.getLoc(), value: true));
926 state.addMemrefToDeallocate(memref: res, block);
927 }
928 }
929
930 return op.getOperation();
931}
932
933FailureOr<Operation *>
934BufferDeallocation::handleInterface(RegionBranchTerminatorOpInterface op) {
935 OpBuilder builder(op);
936
937 // If this is a return operation of a function that is not private or the
938 // dynamic function boundary ownership is disabled, we need to return memref
939 // values for which we have guaranteed ownership to pass on to adhere to the
940 // function boundary ABI.
941 bool funcWithoutDynamicOwnership =
942 isFunctionWithoutDynamicOwnership(op: op->getParentOp());
943 if (funcWithoutDynamicOwnership) {
944 for (OpOperand &val : op->getOpOperands()) {
945 if (!isMemref(v: val.get()))
946 continue;
947
948 val.set(materializeMemrefWithGuaranteedOwnership(builder, memref: val.get(),
949 block: op->getBlock()));
950 }
951 }
952
953 // TODO: getSuccessorRegions is not implemented by all operations we care
954 // about, but we would need to check how many successors there are and under
955 // which condition they are taken, etc.
956
957 MutableOperandRange operands =
958 op.getMutableSuccessorOperands(point: RegionSuccessor(op->getParentOp()));
959
960 SmallVector<Value> updatedOwnerships;
961 auto result = deallocation_impl::insertDeallocOpForReturnLike(
962 state, op, operands: operands.getAsOperandRange(), updatedOperandOwnerships&: updatedOwnerships);
963 if (failed(Result: result) || !*result)
964 return result;
965
966 // Add an additional operand for every MemRef for the ownership indicator.
967 if (!funcWithoutDynamicOwnership) {
968 SmallVector<Value> newOperands{operands.getAsOperandRange()};
969 newOperands.append(in_start: updatedOwnerships.begin(), in_end: updatedOwnerships.end());
970 operands.assign(values: newOperands);
971 }
972
973 return op.getOperation();
974}
975
976bool BufferDeallocation::isFunctionWithoutDynamicOwnership(Operation *op) {
977 auto funcOp = dyn_cast<FunctionOpInterface>(Val: op);
978 return funcOp && (!options.privateFuncDynamicOwnership ||
979 !funcOp.isPrivate() || funcOp.isExternal());
980}
981
982void BufferDeallocation::populateRemainingOwnerships(Operation *op) {
983 for (auto res : op->getResults()) {
984 if (!isMemref(v: res))
985 continue;
986 if (!state.getOwnership(memref: res, block: op->getBlock()).isUninitialized())
987 continue;
988
989 // The op does not allocate memory, otherwise, it would have been assigned
990 // an ownership during `handleInterface`. Assume the result may alias with
991 // any memref operand and thus combine all their ownerships.
992 for (auto operand : op->getOperands()) {
993 if (!isMemref(v: operand))
994 continue;
995
996 state.updateOwnership(
997 memref: res, ownership: state.getOwnership(memref: operand, block: operand.getParentBlock()),
998 block: op->getBlock());
999 }
1000
1001 // If the ownership value is still uninitialized (e.g., because the op has
1002 // no memref operands), assume that no ownership is taken. E.g., this is the
1003 // case for "memref.get_global".
1004 //
1005 // Note: This can lead to memory leaks if memory side effects are not
1006 // properly specified on the op.
1007 if (state.getOwnership(memref: res, block: op->getBlock()).isUninitialized()) {
1008 OpBuilder builder(op);
1009 state.updateOwnership(memref: res, ownership: buildBoolValue(builder, loc: op->getLoc(), value: false));
1010 }
1011 }
1012}
1013
1014//===----------------------------------------------------------------------===//
1015// OwnershipBasedBufferDeallocationPass
1016//===----------------------------------------------------------------------===//
1017
1018namespace {
1019
1020/// The actual buffer deallocation pass that inserts and moves dealloc nodes
1021/// into the right positions. Furthermore, it inserts additional clones if
1022/// necessary. It uses the algorithm described at the top of the file.
1023struct OwnershipBasedBufferDeallocationPass
1024 : public bufferization::impl::OwnershipBasedBufferDeallocationPassBase<
1025 OwnershipBasedBufferDeallocationPass> {
1026 using Base::Base;
1027
1028 void runOnOperation() override {
1029 DeallocationOptions options;
1030 options.privateFuncDynamicOwnership = privateFuncDynamicOwnership;
1031
1032 mlir::SymbolTableCollection symbolTables;
1033
1034 auto status = getOperation()->walk(callback: [&](func::FuncOp func) {
1035 if (func.isExternal())
1036 return WalkResult::skip();
1037
1038 if (failed(Result: deallocateBuffersOwnershipBased(op: func, options, symbolTables)))
1039 return WalkResult::interrupt();
1040
1041 return WalkResult::advance();
1042 });
1043 if (status.wasInterrupted())
1044 signalPassFailure();
1045 }
1046};
1047
1048} // namespace
1049
1050//===----------------------------------------------------------------------===//
1051// Implement bufferization API
1052//===----------------------------------------------------------------------===//
1053
1054LogicalResult bufferization::deallocateBuffersOwnershipBased(
1055 FunctionOpInterface op, DeallocationOptions options,
1056 SymbolTableCollection &symbolTables) {
1057 // Gather all required allocation nodes and prepare the deallocation phase.
1058 BufferDeallocation deallocation(op, options, symbolTables);
1059
1060 // Place all required temporary clone and dealloc nodes.
1061 return deallocation.deallocate(op);
1062}
1063