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