| 1 | //===- CSE.cpp - Common Sub-expression Elimination ------------------------===// |
| 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 common sub-expression elimination as a library utility. |
| 10 | // The matching CSE pass is a thin wrapper over the APIs declared here. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "mlir/Transforms/CSE.h" |
| 15 | |
| 16 | #include "mlir/IR/Dominance.h" |
| 17 | #include "mlir/IR/PatternMatch.h" |
| 18 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 19 | #include "llvm/ADT/DenseMapInfo.h" |
| 20 | #include "llvm/ADT/ScopedHashTable.h" |
| 21 | #include "llvm/Support/Allocator.h" |
| 22 | #include "llvm/Support/RecyclingAllocator.h" |
| 23 | #include <deque> |
| 24 | |
| 25 | using namespace mlir; |
| 26 | |
| 27 | namespace { |
| 28 | struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> { |
| 29 | static unsigned getHashValue(const Operation *opC) { |
| 30 | return OperationEquivalence::computeHash( |
| 31 | op: const_cast<Operation *>(opC), |
| 32 | /*hashOperands=*/OperationEquivalence::directHashValue, |
| 33 | /*hashResults=*/OperationEquivalence::ignoreHashValue, |
| 34 | flags: OperationEquivalence::IgnoreLocations); |
| 35 | } |
| 36 | static bool isEqual(const Operation *lhsC, const Operation *rhsC) { |
| 37 | auto *lhs = const_cast<Operation *>(lhsC); |
| 38 | auto *rhs = const_cast<Operation *>(rhsC); |
| 39 | if (lhs == rhs) |
| 40 | return true; |
| 41 | return OperationEquivalence::isEquivalentTo( |
| 42 | lhs: const_cast<Operation *>(lhsC), rhs: const_cast<Operation *>(rhsC), |
| 43 | flags: OperationEquivalence::IgnoreLocations); |
| 44 | } |
| 45 | }; |
| 46 | } // namespace |
| 47 | |
| 48 | namespace { |
| 49 | /// Simple common sub-expression elimination. |
| 50 | class CSEDriver { |
| 51 | public: |
| 52 | CSEDriver(RewriterBase &rewriter, DominanceInfo *domInfo) |
| 53 | : rewriter(rewriter), domInfo(domInfo) {} |
| 54 | |
| 55 | /// Simplify all operations within the given op. |
| 56 | void simplify(Operation *op, bool *changed = nullptr); |
| 57 | |
| 58 | /// Simplify operations within the given region. |
| 59 | void simplify(Region ®ion, bool *changed = nullptr); |
| 60 | |
| 61 | int64_t getNumCSE() const { return numCSE; } |
| 62 | int64_t getNumDCE() const { return numDCE; } |
| 63 | |
| 64 | private: |
| 65 | /// Shared implementation of operation elimination and scoped map definitions. |
| 66 | using AllocatorTy = llvm::RecyclingAllocator< |
| 67 | llvm::BumpPtrAllocator, |
| 68 | llvm::ScopedHashTableVal<Operation *, Operation *>>; |
| 69 | using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *, |
| 70 | SimpleOperationInfo, AllocatorTy>; |
| 71 | |
| 72 | /// Cache holding MemoryEffects information between two operations. The first |
| 73 | /// operation is stored has the key. The second operation is stored inside a |
| 74 | /// pair in the value. The pair also hold the MemoryEffects between those |
| 75 | /// two operations. If the MemoryEffects is nullptr then we assume there is |
| 76 | /// no operation with MemoryEffects::Write between the two operations. |
| 77 | using MemEffectsCache = |
| 78 | DenseMap<Operation *, std::pair<Operation *, MemoryEffects::Effect *>>; |
| 79 | |
| 80 | /// Represents a single entry in the depth first traversal of a CFG. |
| 81 | struct CFGStackNode { |
| 82 | CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node) |
| 83 | : scope(knownValues), node(node), childIterator(node->begin()) {} |
| 84 | |
| 85 | /// Scope for the known values. |
| 86 | ScopedMapTy::ScopeTy scope; |
| 87 | |
| 88 | DominanceInfoNode *node; |
| 89 | DominanceInfoNode::const_iterator childIterator; |
| 90 | |
| 91 | /// If this node has been fully processed yet or not. |
| 92 | bool processed = false; |
| 93 | }; |
| 94 | |
| 95 | /// Attempt to eliminate a redundant operation. Returns success if the |
| 96 | /// operation was marked for removal, failure otherwise. |
| 97 | LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op, |
| 98 | bool hasSSADominance); |
| 99 | void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance); |
| 100 | void simplifyRegion(ScopedMapTy &knownValues, Region ®ion); |
| 101 | |
| 102 | /// Erase opertion that were marked as dead during simplification, and remove |
| 103 | /// their associated dominator trees. |
| 104 | void eraseDeadOp(Operation *op); |
| 105 | |
| 106 | void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op, |
| 107 | Operation *existing, bool hasSSADominance); |
| 108 | |
| 109 | /// Check if there is side-effecting operations other than the given effect |
| 110 | /// between the two operations. |
| 111 | bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp); |
| 112 | |
| 113 | /// A rewriter for modifying the IR. |
| 114 | RewriterBase &rewriter; |
| 115 | |
| 116 | DominanceInfo *domInfo = nullptr; |
| 117 | MemEffectsCache memEffectsCache; |
| 118 | |
| 119 | // Various statistics. |
| 120 | int64_t numCSE = 0; |
| 121 | int64_t numDCE = 0; |
| 122 | }; |
| 123 | } // namespace |
| 124 | |
| 125 | void CSEDriver::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op, |
| 126 | Operation *existing, |
| 127 | bool hasSSADominance) { |
| 128 | // If the existing operation has an unknown location and the current |
| 129 | // operation doesn't, then set the existing op's location to that of the |
| 130 | // current op. |
| 131 | if (isa<UnknownLoc>(Val: existing->getLoc()) && !isa<UnknownLoc>(Val: op->getLoc())) |
| 132 | existing->setLoc(op->getLoc()); |
| 133 | |
| 134 | ++numCSE; |
| 135 | |
| 136 | // If we find one then replace all uses of the current operation with the |
| 137 | // existing one and delete it. |
| 138 | if (hasSSADominance) { |
| 139 | // If the region has SSA dominance, then we are guaranteed to have not |
| 140 | // visited any use of the current operation. |
| 141 | // Replace all uses, but do not remove the operation yet. |
| 142 | rewriter.replaceAllOpUsesWith(from: op, to: existing->getResults()); |
| 143 | eraseDeadOp(op); |
| 144 | return; |
| 145 | } |
| 146 | |
| 147 | // When the region does not have SSA dominance, we need to check if we |
| 148 | // have visited a use before replacing any use. |
| 149 | auto wasVisited = [&](OpOperand &operand) { |
| 150 | return !knownValues.count(Key: operand.getOwner()); |
| 151 | }; |
| 152 | if (auto *rewriteListener = |
| 153 | dyn_cast_if_present<RewriterBase::Listener>(Val: rewriter.getListener())) |
| 154 | for (Value v : op->getResults()) |
| 155 | if (all_of(Range: v.getUses(), P: wasVisited)) |
| 156 | rewriteListener->notifyOperationReplaced(op, replacement: existing); |
| 157 | |
| 158 | // Replace all uses, but do not remove the operation yet. This does not |
| 159 | // notify the listener because the original op is not erased. |
| 160 | rewriter.replaceUsesWithIf(from: op->getResults(), to: existing->getResults(), |
| 161 | functor: wasVisited); |
| 162 | |
| 163 | // There may be some remaining uses of the operation. |
| 164 | if (op->use_empty()) |
| 165 | eraseDeadOp(op); |
| 166 | } |
| 167 | |
| 168 | bool CSEDriver::hasOtherSideEffectingOpInBetween(Operation *fromOp, |
| 169 | Operation *toOp) { |
| 170 | assert(fromOp->getBlock() == toOp->getBlock()); |
| 171 | assert(hasEffect<MemoryEffects::Read>(fromOp) && |
| 172 | "expected read effect on fromOp" ); |
| 173 | assert(hasEffect<MemoryEffects::Read>(toOp) && |
| 174 | "expected read effect on toOp" ); |
| 175 | |
| 176 | // Collect the read effects of fromOp. A write can only block CSE if it |
| 177 | // can conflict with one of these reads. |
| 178 | SmallVector<MemoryEffects::EffectInstance> readEffects; |
| 179 | if (auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: fromOp)) { |
| 180 | SmallVector<MemoryEffects::EffectInstance> fromEffects; |
| 181 | memOp.getEffects(effects&: fromEffects); |
| 182 | for (MemoryEffects::EffectInstance &e : fromEffects) |
| 183 | if (isa<MemoryEffects::Read>(Val: e.getEffect())) |
| 184 | readEffects.push_back(Elt: e); |
| 185 | } |
| 186 | |
| 187 | Operation *nextOp = fromOp->getNextNode(); |
| 188 | auto result = |
| 189 | memEffectsCache.try_emplace(Key: fromOp, Args: std::make_pair(x&: fromOp, y: nullptr)); |
| 190 | if (!result.second) { |
| 191 | auto memEffectsCachePair = result.first->second; |
| 192 | if (memEffectsCachePair.second == nullptr) { |
| 193 | // No MemoryEffects::Write has been detected until the cached operation. |
| 194 | // Continue looking from the cached operation to toOp. |
| 195 | nextOp = memEffectsCachePair.first; |
| 196 | } else { |
| 197 | // MemoryEffects::Write has been detected before so there is no need to |
| 198 | // check further. |
| 199 | return true; |
| 200 | } |
| 201 | } |
| 202 | while (nextOp && nextOp != toOp) { |
| 203 | std::optional<SmallVector<MemoryEffects::EffectInstance>> effects = |
| 204 | getEffectsRecursively(rootOp: nextOp); |
| 205 | if (!effects) { |
| 206 | // TODO: Do we need to handle other effects generically? |
| 207 | // If the operation does not implement the MemoryEffectOpInterface we |
| 208 | // conservatively assume it writes. |
| 209 | result.first->second = |
| 210 | std::make_pair(x&: nextOp, y: MemoryEffects::Write::get()); |
| 211 | return true; |
| 212 | } |
| 213 | |
| 214 | for (const MemoryEffects::EffectInstance &effect : *effects) { |
| 215 | if (isa<MemoryEffects::Write>(Val: effect.getEffect())) { |
| 216 | // A write on a resource disjoint from all read resources cannot |
| 217 | // conflict with the reads being CSE'd. |
| 218 | SideEffects::Resource *writeResource = effect.getResource(); |
| 219 | bool canConflict = |
| 220 | llvm::any_of(Range&: readEffects, P: [&](const auto &readEffect) { |
| 221 | SideEffects::Resource *readResource = readEffect.getResource(); |
| 222 | if (writeResource->isDisjointFrom(other: readResource)) |
| 223 | return false; |
| 224 | // A pointer-based access to an addressable resource cannot |
| 225 | // conflict with a non-addressable resource. |
| 226 | if (readEffect.getValue() && !writeResource->isAddressable()) |
| 227 | return false; |
| 228 | if (effect.getValue() && !readResource->isAddressable()) |
| 229 | return false; |
| 230 | return true; |
| 231 | }); |
| 232 | if (canConflict) { |
| 233 | result.first->second = {nextOp, MemoryEffects::Write::get()}; |
| 234 | return true; |
| 235 | } |
| 236 | } |
| 237 | } |
| 238 | nextOp = nextOp->getNextNode(); |
| 239 | } |
| 240 | // Record the previous op of `toOp` as the insertion point, since `toOp` |
| 241 | // will be erased immediately after this. Using `toOp` itself would leave |
| 242 | // a dangling pointer, so its predecessor is sufficient to reconstruct |
| 243 | // the position. |
| 244 | result.first->second = std::make_pair(x: toOp->getPrevNode(), y: nullptr); |
| 245 | return false; |
| 246 | } |
| 247 | |
| 248 | /// Attempt to eliminate a redundant operation. |
| 249 | LogicalResult CSEDriver::simplifyOperation(ScopedMapTy &knownValues, |
| 250 | Operation *op, |
| 251 | bool hasSSADominance) { |
| 252 | // Don't simplify terminator operations. |
| 253 | if (op->hasTrait<OpTrait::IsTerminator>()) |
| 254 | return failure(); |
| 255 | |
| 256 | // Don't simplify operations with regions that have multiple blocks. |
| 257 | // TODO: We need additional tests to verify that we handle such IR correctly. |
| 258 | if (!llvm::all_of(Range: op->getRegions(), |
| 259 | P: [](Region &r) { return r.empty() || r.hasOneBlock(); })) |
| 260 | return failure(); |
| 261 | |
| 262 | // Some simple use case of operation with memory side-effect are dealt with |
| 263 | // here. Operations with no side-effect are done after. |
| 264 | if (!isMemoryEffectFree(op)) { |
| 265 | // TODO: Only basic use case for operations with MemoryEffects::Read can be |
| 266 | // eleminated now. More work needs to be done for more complicated patterns |
| 267 | // and other side-effects. |
| 268 | if (!hasSingleEffect<MemoryEffects::Read>(op)) |
| 269 | return failure(); |
| 270 | |
| 271 | // Look for an existing definition for the operation. |
| 272 | if (auto *existing = knownValues.lookup(Key: op)) { |
| 273 | if (existing->getBlock() == op->getBlock() && |
| 274 | !hasOtherSideEffectingOpInBetween(fromOp: existing, toOp: op)) { |
| 275 | // The operation that can be deleted has been reach with no |
| 276 | // side-effecting operations in between the existing operation and |
| 277 | // this one so we can remove the duplicate. |
| 278 | replaceUsesAndDelete(knownValues, op, existing, hasSSADominance); |
| 279 | return success(); |
| 280 | } |
| 281 | } |
| 282 | knownValues.insert(Key: op, Val: op); |
| 283 | return failure(); |
| 284 | } |
| 285 | |
| 286 | // Look for an existing definition for the operation. |
| 287 | if (auto *existing = knownValues.lookup(Key: op)) { |
| 288 | replaceUsesAndDelete(knownValues, op, existing, hasSSADominance); |
| 289 | return success(); |
| 290 | } |
| 291 | |
| 292 | // Otherwise, we add this operation to the known values map. |
| 293 | knownValues.insert(Key: op, Val: op); |
| 294 | return failure(); |
| 295 | } |
| 296 | |
| 297 | void CSEDriver::simplifyBlock(ScopedMapTy &knownValues, Block *bb, |
| 298 | bool hasSSADominance) { |
| 299 | for (auto &op : llvm::make_early_inc_range(Range&: *bb)) { |
| 300 | // If the operation is already trivially dead just add it to the erase list. |
| 301 | // This also avoids calling `simplifyRegion` on dead region ops |
| 302 | // unnecessarily. |
| 303 | if (isOpTriviallyDead(op: &op)) { |
| 304 | eraseDeadOp(op: &op); |
| 305 | ++numDCE; |
| 306 | continue; |
| 307 | } |
| 308 | |
| 309 | // Most operations don't have regions, so fast path that case. |
| 310 | if (op.getNumRegions() != 0) { |
| 311 | // If this operation is isolated above, we can't process nested regions |
| 312 | // with the given 'knownValues' map. This would cause the insertion of |
| 313 | // implicit captures in explicit capture only regions. |
| 314 | if (op.mightHaveTrait<OpTrait::IsIsolatedFromAbove>()) { |
| 315 | ScopedMapTy nestedKnownValues; |
| 316 | for (auto ®ion : op.getRegions()) |
| 317 | simplifyRegion(knownValues&: nestedKnownValues, region); |
| 318 | } else { |
| 319 | // Otherwise, process nested regions normally. |
| 320 | for (auto ®ion : op.getRegions()) |
| 321 | simplifyRegion(knownValues, region); |
| 322 | } |
| 323 | } |
| 324 | |
| 325 | // If the operation is simplified, we don't process any held regions. |
| 326 | if (succeeded(Result: simplifyOperation(knownValues, op: &op, hasSSADominance))) |
| 327 | continue; |
| 328 | } |
| 329 | // Clear the MemoryEffects cache since its usage is by block only. |
| 330 | memEffectsCache.clear(); |
| 331 | } |
| 332 | |
| 333 | void CSEDriver::simplifyRegion(ScopedMapTy &knownValues, Region ®ion) { |
| 334 | // If the region is empty there is nothing to do. |
| 335 | if (region.empty()) |
| 336 | return; |
| 337 | |
| 338 | bool hasSSADominance = domInfo->hasSSADominance(region: ®ion); |
| 339 | |
| 340 | // If the region only contains one block, then simplify it directly. |
| 341 | if (region.hasOneBlock()) { |
| 342 | ScopedMapTy::ScopeTy scope(knownValues); |
| 343 | simplifyBlock(knownValues, bb: ®ion.front(), hasSSADominance); |
| 344 | return; |
| 345 | } |
| 346 | |
| 347 | // If the region does not have dominanceInfo, then skip it. |
| 348 | // TODO: Regions without SSA dominance should define a different |
| 349 | // traversal order which is appropriate and can be used here. |
| 350 | if (!hasSSADominance) |
| 351 | return; |
| 352 | |
| 353 | // Note, deque is being used here because there was significant performance |
| 354 | // gains over vector when the container becomes very large due to the |
| 355 | // specific access patterns. If/when these performance issues are no |
| 356 | // longer a problem we can change this to vector. For more information see |
| 357 | // the llvm mailing list discussion on this: |
| 358 | // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html |
| 359 | std::deque<std::unique_ptr<CFGStackNode>> stack; |
| 360 | |
| 361 | // Process the nodes of the dom tree for this region. |
| 362 | stack.emplace_back(args: std::make_unique<CFGStackNode>( |
| 363 | args&: knownValues, args: domInfo->getRootNode(region: ®ion))); |
| 364 | |
| 365 | while (!stack.empty()) { |
| 366 | auto ¤tNode = stack.back(); |
| 367 | |
| 368 | // Check to see if we need to process this node. |
| 369 | if (!currentNode->processed) { |
| 370 | currentNode->processed = true; |
| 371 | simplifyBlock(knownValues, bb: currentNode->node->getBlock(), |
| 372 | hasSSADominance); |
| 373 | } |
| 374 | |
| 375 | // Otherwise, check to see if we need to process a child node. |
| 376 | if (currentNode->childIterator != currentNode->node->end()) { |
| 377 | auto *childNode = *(currentNode->childIterator++); |
| 378 | stack.emplace_back( |
| 379 | args: std::make_unique<CFGStackNode>(args&: knownValues, args&: childNode)); |
| 380 | } else { |
| 381 | // Finally, if the node and all of its children have been processed |
| 382 | // then we delete the node. |
| 383 | stack.pop_back(); |
| 384 | } |
| 385 | } |
| 386 | } |
| 387 | |
| 388 | void CSEDriver::eraseDeadOp(Operation *op) { |
| 389 | for (Region ®ion : op->getRegions()) |
| 390 | domInfo->invalidate(region: ®ion); |
| 391 | rewriter.eraseOp(op); |
| 392 | |
| 393 | // Note: CSE only removes ops within blocks, without adding or removing |
| 394 | // blocks themselves. Since DominanceInfo captures relationships between |
| 395 | // the direct blocks of the region being analyzed, not the blocks inside |
| 396 | // any nested regions of those ops, it remains valid after CSE. |
| 397 | } |
| 398 | |
| 399 | void CSEDriver::simplify(Operation *op, bool *changed) { |
| 400 | // Simplify all regions. |
| 401 | ScopedMapTy knownValues; |
| 402 | for (auto ®ion : op->getRegions()) |
| 403 | simplifyRegion(knownValues, region); |
| 404 | if (changed) |
| 405 | *changed = numCSE || numDCE; |
| 406 | } |
| 407 | |
| 408 | void CSEDriver::simplify(Region ®ion, bool *changed) { |
| 409 | ScopedMapTy knownValues; |
| 410 | simplifyRegion(knownValues, region); |
| 411 | if (changed) |
| 412 | *changed = numCSE || numDCE; |
| 413 | } |
| 414 | |
| 415 | void mlir::eliminateCommonSubExpressions(RewriterBase &rewriter, |
| 416 | DominanceInfo &domInfo, Operation *op, |
| 417 | bool *changed, int64_t *numCSE, |
| 418 | int64_t *numDCE) { |
| 419 | CSEDriver driver(rewriter, &domInfo); |
| 420 | driver.simplify(op, changed); |
| 421 | if (numCSE) |
| 422 | *numCSE = driver.getNumCSE(); |
| 423 | if (numDCE) |
| 424 | *numDCE = driver.getNumDCE(); |
| 425 | } |
| 426 | |
| 427 | void mlir::eliminateCommonSubExpressions(RewriterBase &rewriter, |
| 428 | DominanceInfo &domInfo, Region ®ion, |
| 429 | bool *changed) { |
| 430 | CSEDriver driver(rewriter, &domInfo); |
| 431 | driver.simplify(region, changed); |
| 432 | } |
| 433 | |