| 1 | //======- BufferViewFlowAnalysis.cpp - Buffer alias analysis -*- C++ -*-======// |
| 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/Transforms/BufferViewFlowAnalysis.h" |
| 10 | |
| 11 | #include "mlir/Dialect/Bufferization/IR/BufferViewFlowOpInterface.h" |
| 12 | #include "mlir/Interfaces/CallInterfaces.h" |
| 13 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 14 | #include "mlir/Interfaces/FunctionInterfaces.h" |
| 15 | #include "mlir/Interfaces/ViewLikeInterface.h" |
| 16 | #include "llvm/ADT/SetOperations.h" |
| 17 | |
| 18 | using namespace mlir; |
| 19 | using namespace mlir::bufferization; |
| 20 | |
| 21 | //===----------------------------------------------------------------------===// |
| 22 | // BufferViewFlowAnalysis |
| 23 | //===----------------------------------------------------------------------===// |
| 24 | |
| 25 | /// Constructs a new alias analysis using the op provided. |
| 26 | BufferViewFlowAnalysis::BufferViewFlowAnalysis(Operation *op) { build(op); } |
| 27 | |
| 28 | static BufferViewFlowAnalysis::ValueSetT |
| 29 | resolveValues(const BufferViewFlowAnalysis::ValueMapT &map, Value value) { |
| 30 | BufferViewFlowAnalysis::ValueSetT result; |
| 31 | SmallVector<Value, 8> queue; |
| 32 | queue.push_back(Elt: value); |
| 33 | while (!queue.empty()) { |
| 34 | Value currentValue = queue.pop_back_val(); |
| 35 | if (result.insert(Ptr: currentValue).second) { |
| 36 | auto it = map.find(Val: currentValue); |
| 37 | if (it != map.end()) { |
| 38 | for (Value aliasValue : it->second) |
| 39 | queue.push_back(Elt: aliasValue); |
| 40 | } |
| 41 | } |
| 42 | } |
| 43 | return result; |
| 44 | } |
| 45 | |
| 46 | /// Find all immediate and indirect dependent buffers this value could |
| 47 | /// potentially have. Note that the resulting set will also contain the value |
| 48 | /// provided as it is a dependent alias of itself. |
| 49 | BufferViewFlowAnalysis::ValueSetT |
| 50 | BufferViewFlowAnalysis::resolve(Value rootValue) const { |
| 51 | return resolveValues(map: dependencies, value: rootValue); |
| 52 | } |
| 53 | |
| 54 | BufferViewFlowAnalysis::ValueSetT |
| 55 | BufferViewFlowAnalysis::resolveReverse(Value rootValue) const { |
| 56 | return resolveValues(map: reverseDependencies, value: rootValue); |
| 57 | } |
| 58 | |
| 59 | /// Removes the given values from all alias sets. |
| 60 | void BufferViewFlowAnalysis::remove(const SetVector<Value> &aliasValues) { |
| 61 | for (auto &entry : dependencies) |
| 62 | llvm::set_subtract(S1&: entry.second, S2: aliasValues); |
| 63 | } |
| 64 | |
| 65 | void BufferViewFlowAnalysis::rename(Value from, Value to) { |
| 66 | dependencies[to] = dependencies[from]; |
| 67 | dependencies.erase(Val: from); |
| 68 | |
| 69 | for (auto &[_, value] : dependencies) { |
| 70 | if (value.contains(Ptr: from)) { |
| 71 | value.insert(Ptr: to); |
| 72 | value.erase(Ptr: from); |
| 73 | } |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | /// This function constructs a mapping from values to its immediate |
| 78 | /// dependencies. It iterates over all blocks, gets their predecessors, |
| 79 | /// determines the values that will be passed to the corresponding block |
| 80 | /// arguments and inserts them into the underlying map. Furthermore, it wires |
| 81 | /// successor regions and branch-like return operations from nested regions. |
| 82 | void BufferViewFlowAnalysis::build(Operation *op) { |
| 83 | // Registers all dependencies of the given values. |
| 84 | auto registerDependencies = [&](ValueRange values, ValueRange dependencies) { |
| 85 | for (auto [value, dep] : llvm::zip_equal(t&: values, u&: dependencies)) { |
| 86 | this->dependencies[value].insert(Ptr: dep); |
| 87 | this->reverseDependencies[dep].insert(Ptr: value); |
| 88 | } |
| 89 | }; |
| 90 | |
| 91 | // Mark all buffer results and buffer region entry block arguments of the |
| 92 | // given op as terminals. |
| 93 | auto populateTerminalValues = [&](Operation *op) { |
| 94 | for (Value v : op->getResults()) |
| 95 | if (isa<BaseMemRefType>(Val: v.getType())) |
| 96 | this->terminals.insert(V: v); |
| 97 | for (Region &r : op->getRegions()) |
| 98 | for (BlockArgument v : r.getArguments()) |
| 99 | if (isa<BaseMemRefType>(Val: v.getType())) |
| 100 | this->terminals.insert(V: v); |
| 101 | }; |
| 102 | |
| 103 | op->walk(callback: [&](Operation *op) { |
| 104 | // Query BufferViewFlowOpInterface. If the op does not implement that |
| 105 | // interface, try to infer the dependencies from other interfaces that the |
| 106 | // op may implement. |
| 107 | if (auto bufferViewFlowOp = dyn_cast<BufferViewFlowOpInterface>(Val: op)) { |
| 108 | bufferViewFlowOp.populateDependencies(registerDependenciesFn: registerDependencies); |
| 109 | for (Value v : op->getResults()) |
| 110 | if (isa<BaseMemRefType>(Val: v.getType()) && |
| 111 | bufferViewFlowOp.mayBeTerminalBuffer(value: v)) |
| 112 | this->terminals.insert(V: v); |
| 113 | for (Region &r : op->getRegions()) |
| 114 | for (BlockArgument v : r.getArguments()) |
| 115 | if (isa<BaseMemRefType>(Val: v.getType()) && |
| 116 | bufferViewFlowOp.mayBeTerminalBuffer(value: v)) |
| 117 | this->terminals.insert(V: v); |
| 118 | return WalkResult::advance(); |
| 119 | } |
| 120 | |
| 121 | // Add additional dependencies created by view changes to the alias list. |
| 122 | if (auto viewInterface = dyn_cast<ViewLikeOpInterface>(Val: op)) { |
| 123 | registerDependencies(viewInterface.getViewSource(), |
| 124 | viewInterface.getViewDest()); |
| 125 | return WalkResult::advance(); |
| 126 | } |
| 127 | |
| 128 | if (auto branchInterface = dyn_cast<BranchOpInterface>(Val: op)) { |
| 129 | // Query all branch interfaces to link block argument dependencies. |
| 130 | Block *parentBlock = branchInterface->getBlock(); |
| 131 | for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end(); |
| 132 | it != e; ++it) { |
| 133 | // Query the branch op interface to get the successor operands. |
| 134 | auto successorOperands = |
| 135 | branchInterface.getSuccessorOperands(index: it.getIndex()); |
| 136 | // Build the actual mapping of values to their immediate dependencies. |
| 137 | registerDependencies(successorOperands.getForwardedOperands(), |
| 138 | (*it)->getArguments().drop_front( |
| 139 | N: successorOperands.getProducedOperandCount())); |
| 140 | } |
| 141 | return WalkResult::advance(); |
| 142 | } |
| 143 | |
| 144 | if (auto regionInterface = dyn_cast<RegionBranchOpInterface>(Val: op)) { |
| 145 | // Wire the successor operands with the successor inputs. |
| 146 | DenseMap<OpOperand *, SmallVector<Value>> mapping; |
| 147 | regionInterface.getSuccessorOperandInputMapping(mapping); |
| 148 | for (const auto &[operand, inputs] : mapping) |
| 149 | for (Value input : inputs) |
| 150 | registerDependencies({operand->get()}, {input}); |
| 151 | return WalkResult::advance(); |
| 152 | } |
| 153 | |
| 154 | // Region terminators are handled together with RegionBranchOpInterface. |
| 155 | if (isa<RegionBranchTerminatorOpInterface>(Val: op)) |
| 156 | return WalkResult::advance(); |
| 157 | |
| 158 | if (isa<CallOpInterface>(Val: op)) { |
| 159 | // This is an intra-function analysis. We have no information about other |
| 160 | // functions. Conservatively assume that each memref operand may alias |
| 161 | // with each memref result; a value of any other type is not a view of a |
| 162 | // buffer. Also mark the results are terminals because the function could |
| 163 | // return newly allocated buffers. |
| 164 | populateTerminalValues(op); |
| 165 | for (Value operand : op->getOperands()) |
| 166 | for (Value result : op->getResults()) |
| 167 | if (isa<BaseMemRefType>(Val: operand.getType()) && |
| 168 | isa<BaseMemRefType>(Val: result.getType())) |
| 169 | registerDependencies({operand}, {result}); |
| 170 | return WalkResult::advance(); |
| 171 | } |
| 172 | |
| 173 | // We have no information about unknown ops. |
| 174 | populateTerminalValues(op); |
| 175 | |
| 176 | return WalkResult::advance(); |
| 177 | }); |
| 178 | } |
| 179 | |
| 180 | bool BufferViewFlowAnalysis::mayBeTerminalBuffer(Value value) const { |
| 181 | assert(isa<BaseMemRefType>(value.getType()) && "expected memref" ); |
| 182 | return terminals.contains(V: value); |
| 183 | } |
| 184 | |
| 185 | //===----------------------------------------------------------------------===// |
| 186 | // BufferOriginAnalysis |
| 187 | //===----------------------------------------------------------------------===// |
| 188 | |
| 189 | /// Return "true" if the given value is the result of a memory allocation. |
| 190 | static bool hasAllocateSideEffect(Value v) { |
| 191 | Operation *op = v.getDefiningOp(); |
| 192 | if (!op) |
| 193 | return false; |
| 194 | return hasEffect<MemoryEffects::Allocate>(op, value: v); |
| 195 | } |
| 196 | |
| 197 | /// Return "true" if the given value is a function block argument. |
| 198 | static bool isFunctionArgument(Value v) { |
| 199 | auto bbArg = dyn_cast<BlockArgument>(Val&: v); |
| 200 | if (!bbArg) |
| 201 | return false; |
| 202 | Block *b = bbArg.getOwner(); |
| 203 | auto funcOp = dyn_cast<FunctionOpInterface>(Val: b->getParentOp()); |
| 204 | if (!funcOp) |
| 205 | return false; |
| 206 | return bbArg.getOwner() == &funcOp.getFunctionBody().front(); |
| 207 | } |
| 208 | |
| 209 | /// Given a memref value, return the "base" value by skipping over all |
| 210 | /// ViewLikeOpInterface ops (if any) in the reverse use-def chain. |
| 211 | static Value getViewBase(Value value) { |
| 212 | while (auto viewLikeOp = value.getDefiningOp<ViewLikeOpInterface>()) { |
| 213 | if (value != viewLikeOp.getViewDest()) { |
| 214 | break; |
| 215 | } |
| 216 | value = viewLikeOp.getViewSource(); |
| 217 | } |
| 218 | return value; |
| 219 | } |
| 220 | |
| 221 | BufferOriginAnalysis::BufferOriginAnalysis(Operation *op) : analysis(op) {} |
| 222 | |
| 223 | std::optional<bool> BufferOriginAnalysis::isSameAllocation(Value v1, Value v2) { |
| 224 | assert(isa<BaseMemRefType>(v1.getType()) && "expected buffer" ); |
| 225 | assert(isa<BaseMemRefType>(v2.getType()) && "expected buffer" ); |
| 226 | |
| 227 | // Skip over all view-like ops. |
| 228 | v1 = getViewBase(value: v1); |
| 229 | v2 = getViewBase(value: v2); |
| 230 | |
| 231 | // Fast path: If both buffers are the same SSA value, we can be sure that |
| 232 | // they originate from the same allocation. |
| 233 | if (v1 == v2) |
| 234 | return true; |
| 235 | |
| 236 | // Compute the SSA values from which the buffers `v1` and `v2` originate. |
| 237 | SmallPtrSet<Value, 16> origin1 = analysis.resolveReverse(rootValue: v1); |
| 238 | SmallPtrSet<Value, 16> origin2 = analysis.resolveReverse(rootValue: v2); |
| 239 | |
| 240 | // Originating buffers are "terminal" if they could not be traced back any |
| 241 | // further by the `BufferViewFlowAnalysis`. Examples of terminal buffers: |
| 242 | // - function block arguments |
| 243 | // - values defined by allocation ops such as "memref.alloc" |
| 244 | // - values defined by ops that are unknown to the buffer view flow analysis |
| 245 | // - values that are marked as "terminal" in the `BufferViewFlowOpInterface` |
| 246 | SmallPtrSet<Value, 16> terminal1, terminal2; |
| 247 | |
| 248 | // While gathering terminal buffers, keep track of whether all terminal |
| 249 | // buffers are newly allocated buffer or function entry arguments. |
| 250 | bool allAllocs1 = true, allAllocs2 = true; |
| 251 | bool allAllocsOrFuncEntryArgs1 = true, allAllocsOrFuncEntryArgs2 = true; |
| 252 | |
| 253 | // Helper function that gathers terminal buffers among `origin`. |
| 254 | auto gatherTerminalBuffers = [this](const SmallPtrSet<Value, 16> &origin, |
| 255 | SmallPtrSet<Value, 16> &terminal, |
| 256 | bool &allAllocs, |
| 257 | bool &allAllocsOrFuncEntryArgs) { |
| 258 | for (Value v : origin) { |
| 259 | if (isa<BaseMemRefType>(Val: v.getType()) && analysis.mayBeTerminalBuffer(value: v)) { |
| 260 | terminal.insert(Ptr: v); |
| 261 | allAllocs &= hasAllocateSideEffect(v); |
| 262 | allAllocsOrFuncEntryArgs &= |
| 263 | isFunctionArgument(v) || hasAllocateSideEffect(v); |
| 264 | } |
| 265 | } |
| 266 | assert(!terminal.empty() && "expected non-empty terminal set" ); |
| 267 | }; |
| 268 | |
| 269 | // Gather terminal buffers for `v1` and `v2`. |
| 270 | gatherTerminalBuffers(origin1, terminal1, allAllocs1, |
| 271 | allAllocsOrFuncEntryArgs1); |
| 272 | gatherTerminalBuffers(origin2, terminal2, allAllocs2, |
| 273 | allAllocsOrFuncEntryArgs2); |
| 274 | |
| 275 | // If both `v1` and `v2` have a single matching terminal buffer, they are |
| 276 | // guaranteed to originate from the same buffer allocation. |
| 277 | if (llvm::hasSingleElement(C&: terminal1) && llvm::hasSingleElement(C&: terminal2) && |
| 278 | *terminal1.begin() == *terminal2.begin()) |
| 279 | return true; |
| 280 | |
| 281 | // At least one of the two values has multiple terminals. |
| 282 | |
| 283 | // Check if there is overlap between the terminal buffers of `v1` and `v2`. |
| 284 | bool distinctTerminalSets = true; |
| 285 | for (Value v : terminal1) |
| 286 | distinctTerminalSets &= !terminal2.contains(Ptr: v); |
| 287 | // If there is overlap between the terminal buffers of `v1` and `v2`, we |
| 288 | // cannot make an accurate decision without further analysis. |
| 289 | if (!distinctTerminalSets) |
| 290 | return std::nullopt; |
| 291 | |
| 292 | // If `v1` originates from only allocs, and `v2` is guaranteed to originate |
| 293 | // from different allocations (that is guaranteed if `v2` originates from |
| 294 | // only distinct allocs or function entry arguments), we can be sure that |
| 295 | // `v1` and `v2` originate from different allocations. The same argument can |
| 296 | // be made when swapping `v1` and `v2`. |
| 297 | bool isolatedAlloc1 = allAllocs1 && (allAllocs2 || allAllocsOrFuncEntryArgs2); |
| 298 | bool isolatedAlloc2 = (allAllocs1 || allAllocsOrFuncEntryArgs1) && allAllocs2; |
| 299 | if (isolatedAlloc1 || isolatedAlloc2) |
| 300 | return false; |
| 301 | |
| 302 | // Otherwise: We do not know whether `v1` and `v2` originate from the same |
| 303 | // allocation or not. |
| 304 | // TODO: Function arguments are currently handled conservatively. We assume |
| 305 | // that they could be the same allocation. |
| 306 | // TODO: Terminals other than allocations and function arguments are |
| 307 | // currently handled conservatively. We assume that they could be the same |
| 308 | // allocation. E.g., we currently return "nullopt" for values that originate |
| 309 | // from different "memref.get_global" ops (with different symbols). |
| 310 | return std::nullopt; |
| 311 | } |
| 312 | |