1//===- BufferDeallocationSimplification.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// This file implements logic for optimizing `bufferization.dealloc` operations
10// that requires more analysis than what can be supported by regular
11// canonicalization patterns.
12//
13//===----------------------------------------------------------------------===//
14
15#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
16#include "mlir/Dialect/Bufferization/Transforms/BufferViewFlowAnalysis.h"
17#include "mlir/Dialect/Bufferization/Transforms/Passes.h"
18#include "mlir/Dialect/Func/IR/FuncOps.h"
19#include "mlir/Dialect/MemRef/IR/MemRef.h"
20#include "mlir/IR/Matchers.h"
21#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
22#include "llvm/ADT/DenseMap.h"
23
24namespace mlir {
25namespace bufferization {
26#define GEN_PASS_DEF_BUFFERDEALLOCATIONSIMPLIFICATIONPASS
27#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
28} // namespace bufferization
29} // namespace mlir
30
31using namespace mlir;
32using namespace mlir::bufferization;
33
34//===----------------------------------------------------------------------===//
35// Helpers
36//===----------------------------------------------------------------------===//
37
38/// Given a memref value, return the "base" value by skipping over all
39/// ViewLikeOpInterface ops (if any) in the reverse use-def chain.
40static Value getViewBase(Value value) {
41 while (auto viewLikeOp = value.getDefiningOp<ViewLikeOpInterface>()) {
42 if (value != viewLikeOp.getViewDest()) {
43 break;
44 }
45 value = viewLikeOp.getViewSource();
46 }
47 return value;
48}
49
50static LogicalResult updateDeallocIfChanged(DeallocOp deallocOp,
51 ValueRange memrefs,
52 ValueRange conditions,
53 PatternRewriter &rewriter) {
54 if (deallocOp.getMemrefs() == memrefs &&
55 deallocOp.getConditions() == conditions)
56 return failure();
57
58 rewriter.modifyOpInPlace(root: deallocOp, callable: [&]() {
59 deallocOp.getMemrefsMutable().assign(values: memrefs);
60 deallocOp.getConditionsMutable().assign(values: conditions);
61 });
62 return success();
63}
64
65/// Return "true" if the given values are guaranteed to be different (and
66/// non-aliasing) allocations based on the fact that one value is the result
67/// of an allocation and the other value is a block argument of a parent block.
68/// Note: This is a best-effort analysis that will eventually be replaced by a
69/// proper "is same allocation" analysis. This function may return "false" even
70/// though the two values are distinct allocations.
71static bool distinctAllocAndBlockArgument(Value v1, Value v2) {
72 Value v1Base = getViewBase(value: v1);
73 Value v2Base = getViewBase(value: v2);
74 auto areDistinct = [](Value v1, Value v2) {
75 if (Operation *op = v1.getDefiningOp())
76 if (hasEffect<MemoryEffects::Allocate>(op, value: v1))
77 if (auto bbArg = dyn_cast<BlockArgument>(Val&: v2))
78 if (bbArg.getOwner()->findAncestorOpInBlock(op&: *op))
79 return true;
80 return false;
81 };
82 return areDistinct(v1Base, v2Base) || areDistinct(v2Base, v1Base);
83}
84
85/// Checks if `memref` may potentially alias a MemRef in `otherList`. It is
86/// often a requirement of optimization patterns that there cannot be any
87/// aliasing memref in order to perform the desired simplification.
88static bool potentiallyAliasesMemref(BufferOriginAnalysis &analysis,
89 ValueRange otherList, Value memref) {
90 for (auto other : otherList) {
91 if (distinctAllocAndBlockArgument(v1: other, v2: memref))
92 continue;
93 std::optional<bool> analysisResult =
94 analysis.isSameAllocation(v1: other, v2: memref);
95 if (!analysisResult.has_value() || analysisResult == true)
96 return true;
97 }
98 return false;
99}
100
101//===----------------------------------------------------------------------===//
102// Patterns
103//===----------------------------------------------------------------------===//
104
105namespace {
106
107/// Remove values from the `memref` operand list that are also present in the
108/// `retained` list (or a guaranteed alias of it) because they will never
109/// actually be deallocated. However, we also need to be certain about which
110/// other memrefs in the `retained` list can alias, i.e., there must not by any
111/// may-aliasing memref. This is necessary because the `dealloc` operation is
112/// defined to return one `i1` value per memref in the `retained` list which
113/// represents the disjunction of the condition values corresponding to all
114/// aliasing values in the `memref` list. In particular, this means that if
115/// there is some value R in the `retained` list which aliases with a value M in
116/// the `memref` list (but can only be staticaly determined to may-alias) and M
117/// is also present in the `retained` list, then it would be illegal to remove M
118/// because the result corresponding to R would be computed incorrectly
119/// afterwards. Because we require an alias analysis, this pattern cannot be
120/// applied as a regular canonicalization pattern.
121///
122/// Example:
123/// ```mlir
124/// %0:3 = bufferization.dealloc (%m0 : ...) if (%cond0)
125/// retain (%m0, %r0, %r1 : ...)
126/// ```
127/// is canonicalized to
128/// ```mlir
129/// // bufferization.dealloc without memrefs and conditions returns %false for
130/// // every retained value
131/// %0:3 = bufferization.dealloc retain (%m0, %r0, %r1 : ...)
132/// %1 = arith.ori %0#0, %cond0 : i1
133/// // replace %0#0 with %1
134/// ```
135/// given that `%r0` and `%r1` may not alias with `%m0`.
136struct RemoveDeallocMemrefsContainedInRetained
137 : public OpRewritePattern<DeallocOp> {
138 RemoveDeallocMemrefsContainedInRetained(MLIRContext *context,
139 BufferOriginAnalysis &analysis)
140 : OpRewritePattern<DeallocOp>(context), analysis(analysis) {}
141
142 /// The passed 'memref' must not have a may-alias relation to any retained
143 /// memref, and at least one must-alias relation. If there is no must-aliasing
144 /// memref in the retain list, we cannot simply remove the memref as there
145 /// could be situations in which it actually has to be deallocated. If it's
146 /// no-alias, then just proceed, if it's must-alias we need to update the
147 /// updated condition returned by the dealloc operation for that alias.
148 LogicalResult handleOneMemref(DeallocOp deallocOp, Value memref, Value cond,
149 PatternRewriter &rewriter) const {
150 rewriter.setInsertionPointAfter(deallocOp);
151
152 // Check that there is no may-aliasing memref and that at least one memref
153 // in the retain list aliases (because otherwise it might have to be
154 // deallocated in some situations and can thus not be dropped).
155 bool atLeastOneMustAlias = false;
156 for (Value retained : deallocOp.getRetained()) {
157 std::optional<bool> analysisResult =
158 analysis.isSameAllocation(v1: retained, v2: memref);
159 if (!analysisResult.has_value())
160 return failure();
161 if (analysisResult == true)
162 atLeastOneMustAlias = true;
163 }
164 if (!atLeastOneMustAlias)
165 return failure();
166
167 // Insert arith.ori operations to update the corresponding dealloc result
168 // values to incorporate the condition of the must-aliasing memref such that
169 // we can remove that operand later on.
170 for (auto [i, retained] : llvm::enumerate(First: deallocOp.getRetained())) {
171 Value updatedCondition = deallocOp.getUpdatedConditions()[i];
172 std::optional<bool> analysisResult =
173 analysis.isSameAllocation(v1: retained, v2: memref);
174 if (analysisResult == true) {
175 auto disjunction = arith::OrIOp::create(builder&: rewriter, location: deallocOp.getLoc(),
176 lhs: updatedCondition, rhs: cond);
177 rewriter.replaceAllUsesExcept(from: updatedCondition, to: disjunction.getResult(),
178 exceptedUser: disjunction);
179 }
180 }
181
182 return success();
183 }
184
185 LogicalResult matchAndRewrite(DeallocOp deallocOp,
186 PatternRewriter &rewriter) const override {
187 // There must not be any duplicates in the retain list anymore because we
188 // would miss updating one of the result values otherwise.
189 DenseSet<Value> retained(deallocOp.getRetained().begin(),
190 deallocOp.getRetained().end());
191 if (retained.size() != deallocOp.getRetained().size())
192 return failure();
193
194 SmallVector<Value> newMemrefs, newConditions;
195 for (auto [memref, cond] :
196 llvm::zip(t: deallocOp.getMemrefs(), u: deallocOp.getConditions())) {
197
198 if (succeeded(Result: handleOneMemref(deallocOp, memref, cond, rewriter)))
199 continue;
200
201 if (auto extractOp =
202 memref.getDefiningOp<memref::ExtractStridedMetadataOp>())
203 if (succeeded(Result: handleOneMemref(deallocOp, memref: extractOp.getOperand(), cond,
204 rewriter)))
205 continue;
206
207 newMemrefs.push_back(Elt: memref);
208 newConditions.push_back(Elt: cond);
209 }
210
211 // Return failure if we don't change anything such that we don't run into an
212 // infinite loop of pattern applications.
213 return updateDeallocIfChanged(deallocOp, memrefs: newMemrefs, conditions: newConditions,
214 rewriter);
215 }
216
217private:
218 BufferOriginAnalysis &analysis;
219};
220
221/// Remove memrefs from the `retained` list which are guaranteed to not alias
222/// any memref in the `memrefs` list. The corresponding result value can be
223/// replaced with `false` in that case according to the operation description.
224///
225/// Example:
226/// ```mlir
227/// %0:2 = bufferization.dealloc (%m : memref<2xi32>) if (%cond)
228/// retain (%r0, %r1 : memref<2xi32>, memref<2xi32>)
229/// return %0#0, %0#1
230/// ```
231/// can be canonicalized to the following given that `%r0` and `%r1` do not
232/// alias `%m`:
233/// ```mlir
234/// bufferization.dealloc (%m : memref<2xi32>) if (%cond)
235/// return %false, %false
236/// ```
237struct RemoveRetainedMemrefsGuaranteedToNotAlias
238 : public OpRewritePattern<DeallocOp> {
239 RemoveRetainedMemrefsGuaranteedToNotAlias(MLIRContext *context,
240 BufferOriginAnalysis &analysis)
241 : OpRewritePattern<DeallocOp>(context), analysis(analysis) {}
242
243 LogicalResult matchAndRewrite(DeallocOp deallocOp,
244 PatternRewriter &rewriter) const override {
245 SmallVector<Value> newRetainedMemrefs, replacements;
246
247 for (auto retainedMemref : deallocOp.getRetained()) {
248 if (potentiallyAliasesMemref(analysis, otherList: deallocOp.getMemrefs(),
249 memref: retainedMemref)) {
250 newRetainedMemrefs.push_back(Elt: retainedMemref);
251 replacements.push_back(Elt: {});
252 continue;
253 }
254
255 replacements.push_back(Elt: arith::ConstantOp::create(
256 builder&: rewriter, location: deallocOp.getLoc(), value: rewriter.getBoolAttr(value: false)));
257 }
258
259 if (newRetainedMemrefs.size() == deallocOp.getRetained().size())
260 return failure();
261
262 auto newDeallocOp =
263 DeallocOp::create(builder&: rewriter, location: deallocOp.getLoc(), memrefs: deallocOp.getMemrefs(),
264 conditions: deallocOp.getConditions(), retained: newRetainedMemrefs);
265 int i = 0;
266 for (auto &repl : replacements) {
267 if (!repl)
268 repl = newDeallocOp.getUpdatedConditions()[i++];
269 }
270
271 rewriter.replaceOp(op: deallocOp, newValues: replacements);
272 return success();
273 }
274
275private:
276 BufferOriginAnalysis &analysis;
277};
278
279/// Split off memrefs to separate dealloc operations to reduce the number of
280/// runtime checks required and enable further canonicalization of the new and
281/// simpler dealloc operations. A memref can be split off if it is guaranteed to
282/// not alias with any other memref in the `memref` operand list. The results
283/// of the old and the new dealloc operation have to be combined by computing
284/// the element-wise disjunction of them.
285///
286/// Example:
287/// ```mlir
288/// %0:2 = bufferization.dealloc (%m0, %m1 : memref<2xi32>, memref<2xi32>)
289/// if (%cond0, %cond1)
290/// retain (%r0, %r1 : memref<2xi32>, memref<2xi32>)
291/// return %0#0, %0#1
292/// ```
293/// Given that `%m0` is guaranteed to never alias with `%m1`, the above IR is
294/// canonicalized to the following, thus reducing the number of runtime alias
295/// checks by 1 and potentially enabling further canonicalization of the new
296/// split-up dealloc operations.
297/// ```mlir
298/// %0:2 = bufferization.dealloc (%m0 : memref<2xi32>) if (%cond0)
299/// retain (%r0, %r1 : memref<2xi32>, memref<2xi32>)
300/// %1:2 = bufferization.dealloc (%m1 : memref<2xi32>) if (%cond1)
301/// retain (%r0, %r1 : memref<2xi32>, memref<2xi32>)
302/// %2 = arith.ori %0#0, %1#0
303/// %3 = arith.ori %0#1, %1#1
304/// return %2, %3
305/// ```
306struct SplitDeallocWhenNotAliasingAnyOther
307 : public OpRewritePattern<DeallocOp> {
308 SplitDeallocWhenNotAliasingAnyOther(MLIRContext *context,
309 BufferOriginAnalysis &analysis)
310 : OpRewritePattern<DeallocOp>(context), analysis(analysis) {}
311
312 LogicalResult matchAndRewrite(DeallocOp deallocOp,
313 PatternRewriter &rewriter) const override {
314 Location loc = deallocOp.getLoc();
315 if (deallocOp.getMemrefs().size() <= 1)
316 return failure();
317
318 // Fast path: when every operand is an alloc (or a chain of view-like
319 // operations rooted in an alloc), two operands may alias only when their
320 // allocation roots are identical. This avoids quadratic pairwise checks.
321 // Unknown origins retain the original conservative analysis below.
322 SmallVector<Value> knownRoots;
323 knownRoots.reserve(N: deallocOp.getMemrefs().size());
324 llvm::DenseMap<Value, int64_t> rootUseCount;
325 bool allRootsKnown = true;
326 for (Value memref : deallocOp.getMemrefs()) {
327 Value root = getViewBase(value: memref);
328 if (!root.getDefiningOp<memref::AllocOp>()) {
329 allRootsKnown = false;
330 break;
331 }
332 knownRoots.push_back(Elt: root);
333 ++rootUseCount[root];
334 }
335
336 SmallVector<Value> remainingMemrefs, remainingConditions;
337 SmallVector<SmallVector<Value>> updatedConditions;
338 for (int64_t i = 0, e = deallocOp.getMemrefs().size(); i < e; ++i) {
339 Value memref = deallocOp.getMemrefs()[i];
340 Value cond = deallocOp.getConditions()[i];
341 bool mayAlias;
342 if (allRootsKnown) {
343 mayAlias = rootUseCount.lookup(Val: knownRoots[i]) > 1;
344 } else {
345 SmallVector<Value> otherMemrefs(deallocOp.getMemrefs());
346 otherMemrefs.erase(CI: otherMemrefs.begin() + i);
347 mayAlias = potentiallyAliasesMemref(analysis, otherList: otherMemrefs, memref);
348 }
349 // Check if memref can split off into a separate bufferization.dealloc.
350 if (mayAlias) {
351 // `memref` alias with other memrefs, do not split off.
352 remainingMemrefs.push_back(Elt: memref);
353 remainingConditions.push_back(Elt: cond);
354 continue;
355 }
356
357 // Create new bufferization.dealloc op for `memref`.
358 auto newDeallocOp = DeallocOp::create(builder&: rewriter, location: loc, memrefs: memref, conditions: cond,
359 retained: deallocOp.getRetained());
360 updatedConditions.push_back(
361 Elt: llvm::to_vector(Range: ValueRange(newDeallocOp.getUpdatedConditions())));
362 }
363
364 // Fail if no memref was split off.
365 if (remainingMemrefs.size() == deallocOp.getMemrefs().size())
366 return failure();
367
368 // Create bufferization.dealloc op for all remaining memrefs.
369 auto newDeallocOp =
370 DeallocOp::create(builder&: rewriter, location: loc, memrefs: remainingMemrefs, conditions: remainingConditions,
371 retained: deallocOp.getRetained());
372
373 // Bit-or all conditions.
374 SmallVector<Value> replacements =
375 llvm::to_vector(Range: ValueRange(newDeallocOp.getUpdatedConditions()));
376 for (auto additionalConditions : updatedConditions) {
377 assert(replacements.size() == additionalConditions.size() &&
378 "expected same number of updated conditions");
379 for (int64_t i = 0, e = replacements.size(); i < e; ++i) {
380 replacements[i] = arith::OrIOp::create(builder&: rewriter, location: loc, lhs: replacements[i],
381 rhs: additionalConditions[i]);
382 }
383 }
384 rewriter.replaceOp(op: deallocOp, newValues: replacements);
385 return success();
386 }
387
388private:
389 BufferOriginAnalysis &analysis;
390};
391
392/// Check for every retained memref if a must-aliasing memref exists in the
393/// 'memref' operand list with constant 'true' condition. If so, we can replace
394/// the operation result corresponding to that retained memref with 'true'. If
395/// this condition holds for all retained memrefs we can also remove the
396/// aliasing memrefs and their conditions since they will never be deallocated
397/// due to the must-alias and we don't need them to compute the result value
398/// anymore since it got replaced with 'true'.
399///
400/// Example:
401/// ```mlir
402/// %0:2 = bufferization.dealloc (%arg0, %arg1, %arg2 : ...)
403/// if (%true, %true, %true)
404/// retain (%arg0, %arg1 : memref<2xi32>, memref<2xi32>)
405/// ```
406/// becomes
407/// ```mlir
408/// %0:2 = bufferization.dealloc (%arg2 : memref<2xi32>) if (%true)
409/// retain (%arg0, %arg1 : memref<2xi32>, memref<2xi32>)
410/// // replace %0#0 with %true
411/// // replace %0#1 with %true
412/// ```
413/// Note that the dealloc operation will still have the result values, but they
414/// don't have uses anymore.
415struct RetainedMemrefAliasingAlwaysDeallocatedMemref
416 : public OpRewritePattern<DeallocOp> {
417 RetainedMemrefAliasingAlwaysDeallocatedMemref(MLIRContext *context,
418 BufferOriginAnalysis &analysis)
419 : OpRewritePattern<DeallocOp>(context), analysis(analysis) {}
420
421 LogicalResult matchAndRewrite(DeallocOp deallocOp,
422 PatternRewriter &rewriter) const override {
423 BitVector aliasesWithConstTrueMemref(deallocOp.getRetained().size());
424 SmallVector<Value> newMemrefs, newConditions;
425 for (auto [memref, cond] :
426 llvm::zip(t: deallocOp.getMemrefs(), u: deallocOp.getConditions())) {
427 bool canDropMemref = false;
428 for (auto [i, retained, res] : llvm::enumerate(
429 First: deallocOp.getRetained(), Rest: deallocOp.getUpdatedConditions())) {
430 if (!matchPattern(value: cond, pattern: m_One()))
431 continue;
432
433 std::optional<bool> analysisResult =
434 analysis.isSameAllocation(v1: retained, v2: memref);
435 if (analysisResult == true) {
436 rewriter.replaceAllUsesWith(from: res, to: cond);
437 aliasesWithConstTrueMemref[i] = true;
438 canDropMemref = true;
439 continue;
440 }
441
442 // TODO: once our alias analysis is powerful enough we can remove the
443 // rest of this loop body
444 auto extractOp =
445 memref.getDefiningOp<memref::ExtractStridedMetadataOp>();
446 if (!extractOp)
447 continue;
448
449 std::optional<bool> extractAnalysisResult =
450 analysis.isSameAllocation(v1: retained, v2: extractOp.getOperand());
451 if (extractAnalysisResult == true) {
452 rewriter.replaceAllUsesWith(from: res, to: cond);
453 aliasesWithConstTrueMemref[i] = true;
454 canDropMemref = true;
455 }
456 }
457
458 if (!canDropMemref) {
459 newMemrefs.push_back(Elt: memref);
460 newConditions.push_back(Elt: cond);
461 }
462 }
463 if (!aliasesWithConstTrueMemref.all())
464 return failure();
465
466 return updateDeallocIfChanged(deallocOp, memrefs: newMemrefs, conditions: newConditions,
467 rewriter);
468 }
469
470private:
471 BufferOriginAnalysis &analysis;
472};
473
474} // namespace
475
476//===----------------------------------------------------------------------===//
477// BufferDeallocationSimplificationPass
478//===----------------------------------------------------------------------===//
479
480namespace {
481
482/// The actual buffer deallocation pass that inserts and moves dealloc nodes
483/// into the right positions. Furthermore, it inserts additional clones if
484/// necessary. It uses the algorithm described at the top of the file.
485struct BufferDeallocationSimplificationPass
486 : public bufferization::impl::BufferDeallocationSimplificationPassBase<
487 BufferDeallocationSimplificationPass> {
488 void runOnOperation() override {
489 BufferOriginAnalysis analysis(getOperation());
490 RewritePatternSet patterns(&getContext());
491 patterns.add<RemoveDeallocMemrefsContainedInRetained,
492 RemoveRetainedMemrefsGuaranteedToNotAlias,
493 SplitDeallocWhenNotAliasingAnyOther,
494 RetainedMemrefAliasingAlwaysDeallocatedMemref>(arg: &getContext(),
495 args&: analysis);
496
497 // We don't want that the block structure changes invalidating the
498 // `BufferOriginAnalysis` so we apply the rewrites with `Normal` level of
499 // region simplification and disable folding.
500 if (failed(Result: applyPatternsGreedily(
501 op: getOperation(), patterns: std::move(patterns),
502 config: GreedyRewriteConfig()
503 .setRegionSimplificationLevel(GreedySimplifyRegionLevel::Normal)
504 .enableFolding(enable: false))))
505 signalPassFailure();
506
507 // We run canonicalization separately so it can benefit from
508 // folding, which was disabled previously to avoid invalidating
509 // `BufferOriginAnalysis`.
510 RewritePatternSet canonicalizationPatterns(&getContext());
511 populateDeallocOpCanonicalizationPatterns(patterns&: canonicalizationPatterns,
512 context: &getContext());
513 if (failed(Result: applyPatternsGreedily(
514 op: getOperation(), patterns: std::move(canonicalizationPatterns),
515 config: GreedyRewriteConfig().setRegionSimplificationLevel(
516 GreedySimplifyRegionLevel::Normal))))
517 signalPassFailure();
518 }
519};
520
521} // namespace
522