| 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 | |
| 15 | #include "mlir/Dialect/Bufferization/Transforms/BufferViewFlowAnalysis.h" |
| 16 | #include "mlir/Dialect/Bufferization/Transforms/Passes.h" |
| 17 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 18 | #include "mlir/IR/Dominance.h" |
| 19 | #include "mlir/IR/Operation.h" |
| 20 | #include "mlir/IR/Value.h" |
| 21 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 22 | #include "llvm/Support/DebugLog.h" |
| 23 | |
| 24 | #define DEBUG_TYPE "optimize-allocation-liveness" |
| 25 | |
| 26 | namespace mlir { |
| 27 | namespace bufferization { |
| 28 | #define GEN_PASS_DEF_OPTIMIZEALLOCATIONLIVENESSPASS |
| 29 | #include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc" |
| 30 | } // namespace bufferization |
| 31 | } // namespace mlir |
| 32 | |
| 33 | using namespace mlir; |
| 34 | |
| 35 | namespace { |
| 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`. |
| 42 | static bool happensBefore(Operation *a, Operation *b) { |
| 43 | do { |
| 44 | if (a->isProperAncestor(other: b)) |
| 45 | return false; |
| 46 | if (Operation *bAncestor = a->getBlock()->findAncestorOpInBlock(op&: *b)) { |
| 47 | return a->isBeforeInBlock(other: 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. |
| 55 | Operation *findUserWithFreeSideEffect(Value value) { |
| 56 | Operation *freeOpUser = nullptr; |
| 57 | for (Operation *user : value.getUsers()) { |
| 58 | if (MemoryEffectOpInterface memEffectOp = |
| 59 | dyn_cast<MemoryEffectOpInterface>(Val: user)) { |
| 60 | SmallVector<MemoryEffects::EffectInstance, 2> effects; |
| 61 | memEffectOp.getEffects(effects); |
| 62 | |
| 63 | for (const auto &effect : effects) { |
| 64 | if (isa<MemoryEffects::Free>(Val: 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. |
| 79 | static bool hasMemoryAllocEffect(MemoryEffectOpInterface memEffectOp) { |
| 80 | SmallVector<MemoryEffects::EffectInstance, 2> effects; |
| 81 | memEffectOp.getEffects(effects); |
| 82 | for (const auto &effect : effects) { |
| 83 | if (isa<MemoryEffects::Allocate>(Val: effect.getEffect())) { |
| 84 | return true; |
| 85 | } |
| 86 | } |
| 87 | return false; |
| 88 | } |
| 89 | |
| 90 | /// Extracts OpResult's with Allocate effects from given op |
| 91 | static SmallVector<OpResult> |
| 92 | collectAllocations(MemoryEffectOpInterface allocOp) { |
| 93 | SmallVector<MemoryEffects::EffectInstance> effects; |
| 94 | allocOp.getEffects(effects); |
| 95 | SmallVector<OpResult> allocResults; |
| 96 | for (const MemoryEffects::EffectInstance &it : effects) |
| 97 | if (isa<MemoryEffects::Allocate>(Val: it.getEffect())) |
| 98 | if (auto val = it.getValue(); val && val.getDefiningOp() == allocOp) |
| 99 | allocResults.push_back(Elt: cast<OpResult>(Val&: val)); |
| 100 | return allocResults; |
| 101 | } |
| 102 | |
| 103 | struct OptimizeAllocationLiveness |
| 104 | : public bufferization::impl::OptimizeAllocationLivenessPassBase< |
| 105 | OptimizeAllocationLiveness> { |
| 106 | public: |
| 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(a: target, b: 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(a: target, b: 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(callback: [&](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(value: 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; |
| 194 | const BufferViewFlowAnalysis::ValueSetT &deps = |
| 195 | analysis.resolve(value: allocResult); |
| 196 | for (auto dep : llvm::make_early_inc_range(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(op&: *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(a: lastUser, b: 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: &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(existingOp: target); |
| 231 | LDBG() << "Moved dealloc op before: " << *target; |
| 232 | |
| 233 | return WalkResult::advance(); |
| 234 | }); |
| 235 | } |
| 236 | }; |
| 237 | } // end anonymous namespace |
| 238 | |