| 1 | //===- GreedyPatternRewriteDriver.cpp - A greedy rewriter -----------------===// |
| 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 mlir::applyPatternsGreedily. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Transforms/GreedyPatternRewriteDriver.h" |
| 14 | |
| 15 | #include "mlir/Config/mlir-config.h" |
| 16 | #include "mlir/IR/Action.h" |
| 17 | #include "mlir/IR/Dominance.h" |
| 18 | #include "mlir/IR/Matchers.h" |
| 19 | #include "mlir/IR/Operation.h" |
| 20 | #include "mlir/IR/OperationSupport.h" |
| 21 | #include "mlir/IR/Verifier.h" |
| 22 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 23 | #include "mlir/Rewrite/PatternApplicator.h" |
| 24 | #include "mlir/Transforms/CSE.h" |
| 25 | #include "mlir/Transforms/FoldUtils.h" |
| 26 | #include "mlir/Transforms/RegionUtils.h" |
| 27 | #include "llvm/ADT/BitVector.h" |
| 28 | #include "llvm/ADT/DenseMap.h" |
| 29 | #include "llvm/ADT/ScopeExit.h" |
| 30 | #include "llvm/ADT/SetVector.h" |
| 31 | #include "llvm/ADT/SmallPtrSet.h" |
| 32 | #include "llvm/Support/DebugLog.h" |
| 33 | #include "llvm/Support/ScopedPrinter.h" |
| 34 | #include "llvm/Support/raw_ostream.h" |
| 35 | |
| 36 | #ifdef MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 37 | #include <random> |
| 38 | #endif // MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 39 | |
| 40 | using namespace mlir; |
| 41 | |
| 42 | #define DEBUG_TYPE "greedy-rewriter" |
| 43 | |
| 44 | namespace { |
| 45 | |
| 46 | //===----------------------------------------------------------------------===// |
| 47 | // Debugging Infrastructure |
| 48 | //===----------------------------------------------------------------------===// |
| 49 | |
| 50 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 51 | /// A helper struct that performs various "expensive checks" to detect broken |
| 52 | /// rewrite patterns use the rewriter API incorrectly. A rewrite pattern is |
| 53 | /// broken if: |
| 54 | /// * IR does not verify after pattern application / folding. |
| 55 | /// * Pattern returns "failure" but the IR has changed. |
| 56 | /// * Pattern returns "success" but the IR has not changed. |
| 57 | /// |
| 58 | /// This struct stores finger prints of ops to determine whether the IR has |
| 59 | /// changed or not. |
| 60 | struct ExpensiveChecks : public RewriterBase::ForwardingListener { |
| 61 | ExpensiveChecks(RewriterBase::Listener *listener, Operation *topLevel) |
| 62 | : RewriterBase::ForwardingListener(listener), topLevel(topLevel) {} |
| 63 | |
| 64 | /// Compute finger prints of the given op and its nested ops. |
| 65 | void computeFingerPrints(Operation *topLevel) { |
| 66 | this->topLevel = topLevel; |
| 67 | this->topLevelFingerPrint.emplace(topLevel); |
| 68 | topLevel->walk([&](Operation *op) { |
| 69 | fingerprints.try_emplace(op, op, /*includeNested=*/false); |
| 70 | }); |
| 71 | } |
| 72 | |
| 73 | /// Clear all finger prints. |
| 74 | void clear() { |
| 75 | topLevel = nullptr; |
| 76 | topLevelFingerPrint.reset(); |
| 77 | fingerprints.clear(); |
| 78 | } |
| 79 | |
| 80 | void notifyRewriteSuccess() { |
| 81 | if (!topLevel) |
| 82 | return; |
| 83 | |
| 84 | // Make sure that the IR still verifies. |
| 85 | if (failed(verify(topLevel))) |
| 86 | llvm::report_fatal_error("IR failed to verify after pattern application" ); |
| 87 | |
| 88 | // Pattern application success => IR must have changed. |
| 89 | OperationFingerPrint afterFingerPrint(topLevel); |
| 90 | if (*topLevelFingerPrint == afterFingerPrint) { |
| 91 | // Note: Run "mlir-opt -debug" to see which pattern is broken. |
| 92 | llvm::report_fatal_error( |
| 93 | "pattern returned success but IR did not change" ); |
| 94 | } |
| 95 | for (const auto &it : fingerprints) { |
| 96 | // Skip top-level op, its finger print is never invalidated. |
| 97 | if (it.first == topLevel) |
| 98 | continue; |
| 99 | // Note: Finger print computation may crash when an op was erased |
| 100 | // without notifying the rewriter. (Run with ASAN to see where the op was |
| 101 | // erased; the op was probably erased directly, bypassing the rewriter |
| 102 | // API.) Finger print computation does may not crash if a new op was |
| 103 | // created at the same memory location. (But then the finger print should |
| 104 | // have changed.) |
| 105 | if (it.second != |
| 106 | OperationFingerPrint(it.first, /*includeNested=*/false)) { |
| 107 | // Note: Run "mlir-opt -debug" to see which pattern is broken. |
| 108 | llvm::report_fatal_error("operation finger print changed" ); |
| 109 | } |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | void notifyRewriteFailure() { |
| 114 | if (!topLevel) |
| 115 | return; |
| 116 | |
| 117 | // Pattern application failure => IR must not have changed. |
| 118 | OperationFingerPrint afterFingerPrint(topLevel); |
| 119 | if (*topLevelFingerPrint != afterFingerPrint) { |
| 120 | // Note: Run "mlir-opt -debug" to see which pattern is broken. |
| 121 | llvm::report_fatal_error("pattern returned failure but IR did change" ); |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | void notifyFoldingSuccess() { |
| 126 | if (!topLevel) |
| 127 | return; |
| 128 | |
| 129 | // Make sure that the IR still verifies. |
| 130 | if (failed(verify(topLevel))) |
| 131 | llvm::report_fatal_error("IR failed to verify after folding" ); |
| 132 | } |
| 133 | |
| 134 | protected: |
| 135 | /// Invalidate the finger print of the given op, i.e., remove it from the map. |
| 136 | void invalidateFingerPrint(Operation *op) { fingerprints.erase(op); } |
| 137 | |
| 138 | void notifyBlockInserted(Block *block, Region *previous, |
| 139 | Region::iterator previousIt) override { |
| 140 | RewriterBase::ForwardingListener::notifyBlockInserted(block, previous, |
| 141 | previousIt); |
| 142 | |
| 143 | // Inserting or moving a block changes the region structure of both the |
| 144 | // new and previous owners. Either region may be detached. |
| 145 | invalidateFingerPrint(block->getParentOp()); |
| 146 | if (previous) |
| 147 | invalidateFingerPrint(previous->getParentOp()); |
| 148 | } |
| 149 | |
| 150 | void notifyBlockErased(Block *block) override { |
| 151 | RewriterBase::ForwardingListener::notifyBlockErased(block); |
| 152 | |
| 153 | // The block structure (number of blocks, types of block arguments, etc.) |
| 154 | // is part of the fingerprint of the parent op. |
| 155 | // TODO: The parent op fingerprint should also be invalidated when modifying |
| 156 | // the block arguments of a block, but we do not have a |
| 157 | // `notifyBlockModified` callback yet. |
| 158 | invalidateFingerPrint(block->getParentOp()); |
| 159 | } |
| 160 | |
| 161 | void notifyOperationInserted(Operation *op, |
| 162 | OpBuilder::InsertPoint previous) override { |
| 163 | RewriterBase::ForwardingListener::notifyOperationInserted(op, previous); |
| 164 | invalidateFingerPrint(op->getParentOp()); |
| 165 | } |
| 166 | |
| 167 | void notifyOperationModified(Operation *op) override { |
| 168 | RewriterBase::ForwardingListener::notifyOperationModified(op); |
| 169 | invalidateFingerPrint(op); |
| 170 | } |
| 171 | |
| 172 | void notifyOperationErased(Operation *op) override { |
| 173 | RewriterBase::ForwardingListener::notifyOperationErased(op); |
| 174 | op->walk([this](Operation *op) { invalidateFingerPrint(op); }); |
| 175 | } |
| 176 | |
| 177 | /// Operation finger prints to detect invalid pattern API usage. IR is checked |
| 178 | /// against these finger prints after pattern application to detect cases |
| 179 | /// where IR was modified directly, bypassing the rewriter API. |
| 180 | DenseMap<Operation *, OperationFingerPrint> fingerprints; |
| 181 | |
| 182 | /// Top-level operation of the current greedy rewrite. |
| 183 | Operation *topLevel = nullptr; |
| 184 | |
| 185 | /// Finger print of the top-level operation. |
| 186 | std::optional<OperationFingerPrint> topLevelFingerPrint; |
| 187 | }; |
| 188 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 189 | |
| 190 | #ifndef NDEBUG |
| 191 | static Operation *getDumpRootOp(Operation *op) { |
| 192 | // Dump the parent op so that materialized constants are visible. If the op |
| 193 | // is a top-level op, dump it directly. |
| 194 | if (Operation *parentOp = op->getParentOp()) |
| 195 | return parentOp; |
| 196 | return op; |
| 197 | } |
| 198 | static void logSuccessfulFolding(Operation *op) { |
| 199 | LDBG() << "// *** IR Dump After Successful Folding ***\n" |
| 200 | << OpWithFlags(op, OpPrintingFlags().elideLargeElementsAttrs()); |
| 201 | } |
| 202 | #endif // NDEBUG |
| 203 | |
| 204 | //===----------------------------------------------------------------------===// |
| 205 | // Worklist |
| 206 | //===----------------------------------------------------------------------===// |
| 207 | |
| 208 | /// A LIFO worklist of operations with efficient removal and set semantics. |
| 209 | /// |
| 210 | /// This class maintains a vector of operations and a mapping of operations to |
| 211 | /// positions in the vector, so that operations can be removed efficiently at |
| 212 | /// random. When an operation is removed, it is replaced with nullptr. Such |
| 213 | /// nullptr are skipped when pop'ing elements. |
| 214 | class Worklist { |
| 215 | public: |
| 216 | Worklist(); |
| 217 | |
| 218 | /// Clear the worklist. |
| 219 | void clear(); |
| 220 | |
| 221 | /// Return whether the worklist is empty. |
| 222 | bool empty() const; |
| 223 | |
| 224 | /// Push an operation to the end of the worklist, unless the operation is |
| 225 | /// already on the worklist. |
| 226 | void push(Operation *op); |
| 227 | |
| 228 | /// Pop the an operation from the end of the worklist. Only allowed on |
| 229 | /// non-empty worklists. |
| 230 | Operation *pop(); |
| 231 | |
| 232 | /// Remove an operation from the worklist. |
| 233 | void remove(Operation *op); |
| 234 | |
| 235 | /// Reverse the worklist. |
| 236 | void reverse(); |
| 237 | |
| 238 | protected: |
| 239 | /// The worklist of operations. |
| 240 | std::vector<Operation *> list; |
| 241 | |
| 242 | /// A mapping of operations to positions in `list`. |
| 243 | DenseMap<Operation *, unsigned> map; |
| 244 | }; |
| 245 | |
| 246 | Worklist::Worklist() { list.reserve(n: 64); } |
| 247 | |
| 248 | void Worklist::clear() { |
| 249 | list.clear(); |
| 250 | map.clear(); |
| 251 | } |
| 252 | |
| 253 | bool Worklist::empty() const { |
| 254 | // Skip all nullptr. |
| 255 | return !llvm::any_of(Range: list, |
| 256 | P: [](Operation *op) { return static_cast<bool>(op); }); |
| 257 | } |
| 258 | |
| 259 | void Worklist::push(Operation *op) { |
| 260 | assert(op && "cannot push nullptr to worklist" ); |
| 261 | // Check to see if the worklist already contains this op. |
| 262 | if (!map.insert(KV: {op, list.size()}).second) |
| 263 | return; |
| 264 | list.push_back(x: op); |
| 265 | } |
| 266 | |
| 267 | Operation *Worklist::pop() { |
| 268 | assert(!empty() && "cannot pop from empty worklist" ); |
| 269 | // Skip and remove all trailing nullptr. |
| 270 | while (!list.back()) |
| 271 | list.pop_back(); |
| 272 | Operation *op = list.back(); |
| 273 | list.pop_back(); |
| 274 | map.erase(Val: op); |
| 275 | // Cleanup: Remove all trailing nullptr. |
| 276 | while (!list.empty() && !list.back()) |
| 277 | list.pop_back(); |
| 278 | return op; |
| 279 | } |
| 280 | |
| 281 | void Worklist::remove(Operation *op) { |
| 282 | assert(op && "cannot remove nullptr from worklist" ); |
| 283 | auto it = map.find(Val: op); |
| 284 | if (it != map.end()) { |
| 285 | assert(list[it->second] == op && "malformed worklist data structure" ); |
| 286 | list[it->second] = nullptr; |
| 287 | map.erase(I: it); |
| 288 | } |
| 289 | } |
| 290 | |
| 291 | void Worklist::reverse() { |
| 292 | std::reverse(first: list.begin(), last: list.end()); |
| 293 | for (size_t i = 0, e = list.size(); i != e; ++i) |
| 294 | map[list[i]] = i; |
| 295 | } |
| 296 | |
| 297 | #ifdef MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 298 | /// A worklist that pops elements at a random position. This worklist is for |
| 299 | /// testing/debugging purposes only. It can be used to ensure that lowering |
| 300 | /// pipelines work correctly regardless of the order in which ops are processed |
| 301 | /// by the GreedyPatternRewriteDriver. |
| 302 | class RandomizedWorklist : public Worklist { |
| 303 | public: |
| 304 | RandomizedWorklist() : Worklist() { |
| 305 | generator.seed(MLIR_GREEDY_REWRITE_RANDOMIZER_SEED); |
| 306 | } |
| 307 | |
| 308 | /// Pop a random non-empty op from the worklist. |
| 309 | Operation *pop() { |
| 310 | Operation *op = nullptr; |
| 311 | do { |
| 312 | assert(!list.empty() && "cannot pop from empty worklist" ); |
| 313 | int64_t pos = generator() % list.size(); |
| 314 | op = list[pos]; |
| 315 | list.erase(list.begin() + pos); |
| 316 | for (int64_t i = pos, e = list.size(); i < e; ++i) |
| 317 | map[list[i]] = i; |
| 318 | map.erase(op); |
| 319 | } while (!op); |
| 320 | return op; |
| 321 | } |
| 322 | |
| 323 | private: |
| 324 | std::minstd_rand0 generator; |
| 325 | }; |
| 326 | #endif // MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 327 | |
| 328 | //===----------------------------------------------------------------------===// |
| 329 | // GreedyPatternRewriteDriver |
| 330 | //===----------------------------------------------------------------------===// |
| 331 | |
| 332 | /// Tracks which blocks are reachable from their region's entry block while |
| 333 | /// patterns rewrite the CFG, so that the driver can skip operations in blocks |
| 334 | /// that a rewrite disconnected. Notifications only record what changed; the |
| 335 | /// queries, which the driver issues between rewrites, bring the cache up to |
| 336 | /// date. `Block::isReachable` is not used because it traverses the region on |
| 337 | /// every call, while the driver queries once per processed operation. All |
| 338 | /// notifications are forwarded to the wrapped listener. |
| 339 | class ReachabilityListener : public RewriterBase::ForwardingListener { |
| 340 | public: |
| 341 | ReachabilityListener(RewriterBase::Listener *listener, Region *scope) |
| 342 | : RewriterBase::ForwardingListener(listener), scope(scope) {} |
| 343 | |
| 344 | /// Return whether `op` is reachable: its block is reachable from the entry |
| 345 | /// block of its region, and so is every containing block up to `scope`. |
| 346 | /// Must be called between rewrites, when the IR is in a consistent state. |
| 347 | bool isReachable(Operation *op); |
| 348 | |
| 349 | /// Drop all cached reachability information. |
| 350 | void clear() { regionStates.clear(); } |
| 351 | |
| 352 | void notifyBlockInserted(Block *block, Region *previous, |
| 353 | Region::iterator previousIt) override; |
| 354 | void notifyBlockErased(Block *block) override; |
| 355 | void notifyOperationInserted(Operation *op, |
| 356 | OpBuilder::InsertPoint previous) override; |
| 357 | void notifyOperationModified(Operation *op) override; |
| 358 | void notifyOperationErased(Operation *op) override; |
| 359 | |
| 360 | private: |
| 361 | /// The reachability cache of one region. |
| 362 | struct RegionState { |
| 363 | /// The entry block at the time of the traversal. The traversal starts |
| 364 | /// from the entry block, so a different entry block invalidates the cache. |
| 365 | Block *entry = nullptr; |
| 366 | /// The reachable blocks, mapped to their successors within the region as |
| 367 | /// of the last query. The snapshots let the next query tell lost edges |
| 368 | /// from added ones. |
| 369 | DenseMap<Block *, SmallVector<Block *, 2>> reachable; |
| 370 | /// Blocks of `reachable` whose reachability could not be decided |
| 371 | /// incrementally. A query for one of them traverses the region. Marking |
| 372 | /// and traversing both cost O(blocks), so a lost edge into a loop whose |
| 373 | /// target keeps other predecessors costs O(blocks) per rewrite if one of |
| 374 | /// the marked blocks is queried before the next change. Bottom-up |
| 375 | /// processing has usually popped the operations of these blocks already; |
| 376 | /// top-down processing pops them next. |
| 377 | llvm::SmallDenseSet<Block *, 4> uncertain; |
| 378 | /// Blocks whose terminator changed since the last query, in notification |
| 379 | /// order, so that the cache evolves deterministically. |
| 380 | llvm::SmallSetVector<Block *, 4> changedBlocks; |
| 381 | /// Blocks erased from or moved out of the region since the last query. |
| 382 | /// Their pointers are only compared, never dereferenced. |
| 383 | llvm::SmallDenseSet<Block *, 4> removedBlocks; |
| 384 | |
| 385 | /// Rebuild the cache from the entry block of `region`. |
| 386 | void traverse(Region *region); |
| 387 | /// Add `roots` and every block reachable from them to `reachable`. The |
| 388 | /// added blocks are uncertain if `isUncertain` is set. |
| 389 | void addReachable(SmallVector<Block *> roots, bool isUncertain); |
| 390 | /// Mark `block` and every block behind it in the snapshots uncertain. |
| 391 | void markUncertain(Block *block); |
| 392 | /// Apply the pending changes, if any. On failure, the state is |
| 393 | /// inconsistent and the region must be traversed again. |
| 394 | LogicalResult applyChanges(); |
| 395 | }; |
| 396 | |
| 397 | /// Record that the terminator of `block` changed. Only tracked regions |
| 398 | /// record changes, so no pointer to a block of an untracked region is kept. |
| 399 | void markChanged(Block *block) { |
| 400 | if (!block) |
| 401 | return; |
| 402 | auto it = regionStates.find(Val: block->getParent()); |
| 403 | if (it != regionStates.end()) |
| 404 | it->second.changedBlocks.insert(X: block); |
| 405 | } |
| 406 | /// Record that `block` left `region`. |
| 407 | void markRemoved(Region *region, Block *block) { |
| 408 | auto it = regionStates.find(Val: region); |
| 409 | if (it != regionStates.end()) |
| 410 | it->second.removedBlocks.insert(V: block); |
| 411 | } |
| 412 | bool isBlockReachable(Block *block); |
| 413 | |
| 414 | /// The tracked regions. A region without an entry is traversed by the next |
| 415 | /// query that needs it. |
| 416 | DenseMap<Region *, RegionState> regionStates; |
| 417 | |
| 418 | Region *const scope; |
| 419 | }; |
| 420 | |
| 421 | /// Provides cached deadness queries that stay valid across rewriter |
| 422 | /// notifications. All notifications are forwarded to the wrapped listener |
| 423 | /// after invalidating affected cache entries. |
| 424 | class DeadnessListener : public RewriterBase::ForwardingListener { |
| 425 | public: |
| 426 | explicit DeadnessListener(RewriterBase::Listener *listener) |
| 427 | : RewriterBase::ForwardingListener(listener) {} |
| 428 | |
| 429 | /// Return true if the operation is unused and can be erased. |
| 430 | bool isOpTriviallyDead(Operation *op) { return cache.isOpTriviallyDead(op); } |
| 431 | |
| 432 | void notifyBlockInserted(Block *block, Region *previous, |
| 433 | Region::iterator previousIt) override { |
| 434 | // Moving a block can change the context of every operation it contains. |
| 435 | for (Operation &op : *block) |
| 436 | cache.invalidate(op: &op); |
| 437 | if (previous) |
| 438 | if (Operation *parent = previous->getParentOp()) |
| 439 | cache.invalidateAncestors(op: parent); |
| 440 | if (Operation *parent = block->getParentOp()) |
| 441 | cache.invalidateAncestors(op: parent); |
| 442 | ForwardingListener::notifyBlockInserted(block, previous, previousIt); |
| 443 | } |
| 444 | |
| 445 | void notifyBlockErased(Block *block) override { |
| 446 | if (Operation *parent = block->getParentOp()) |
| 447 | cache.invalidateAncestors(op: parent); |
| 448 | ForwardingListener::notifyBlockErased(block); |
| 449 | } |
| 450 | |
| 451 | void notifyOperationInserted(Operation *op, |
| 452 | OpBuilder::InsertPoint previous) override { |
| 453 | // The old parent loses a child, but its remaining descendants are |
| 454 | // unchanged. Scanning them for every move would make block merging |
| 455 | // quadratic. |
| 456 | if (previous.isSet()) |
| 457 | if (Operation *parent = previous.getBlock()->getParentOp()) |
| 458 | cache.invalidateAncestors(op: parent); |
| 459 | cache.invalidate(op); |
| 460 | ForwardingListener::notifyOperationInserted(op, previous); |
| 461 | } |
| 462 | |
| 463 | void notifyOperationModified(Operation *op) override { |
| 464 | cache.invalidate(op); |
| 465 | ForwardingListener::notifyOperationModified(op); |
| 466 | } |
| 467 | |
| 468 | void notifyOperationErased(Operation *op) override { |
| 469 | cache.invalidate(op); |
| 470 | ForwardingListener::notifyOperationErased(op); |
| 471 | } |
| 472 | |
| 473 | private: |
| 474 | DeadnessCache cache; |
| 475 | }; |
| 476 | |
| 477 | /// This is a worklist-driven driver for the PatternMatcher, which repeatedly |
| 478 | /// applies the locally optimal patterns. |
| 479 | /// |
| 480 | /// This abstract class manages the worklist and contains helper methods for |
| 481 | /// rewriting ops on the worklist. Derived classes specify how ops are added |
| 482 | /// to the worklist in the beginning. |
| 483 | class GreedyPatternRewriteDriver : public RewriterBase::Listener { |
| 484 | protected: |
| 485 | explicit GreedyPatternRewriteDriver(MLIRContext *ctx, |
| 486 | const FrozenRewritePatternSet &patterns, |
| 487 | const GreedyRewriteConfig &config); |
| 488 | |
| 489 | /// Add the given operation to the worklist. |
| 490 | void addSingleOpToWorklist(Operation *op); |
| 491 | |
| 492 | /// Add the given operation and its ancestors to the worklist. |
| 493 | void addToWorklist(Operation *op); |
| 494 | |
| 495 | /// Notify the driver that the specified operation may have been modified |
| 496 | /// in-place. The operation is added to the worklist. |
| 497 | void notifyOperationModified(Operation *op) override; |
| 498 | |
| 499 | /// Notify the driver that the specified operation was inserted. Update the |
| 500 | /// worklist as needed: The operation is enqueued depending on scope and |
| 501 | /// strict mode. |
| 502 | void notifyOperationInserted(Operation *op, |
| 503 | OpBuilder::InsertPoint previous) override; |
| 504 | |
| 505 | /// Notify the driver that the specified operation was removed. Update the |
| 506 | /// worklist as needed: The operation and its children are removed from the |
| 507 | /// worklist. |
| 508 | void notifyOperationErased(Operation *op) override; |
| 509 | |
| 510 | /// Notify the driver that the specified operation was replaced. Update the |
| 511 | /// worklist as needed: New users are added enqueued. |
| 512 | void notifyOperationReplaced(Operation *op, ValueRange replacement) override; |
| 513 | |
| 514 | /// Process ops until the worklist is empty or `config.maxNumRewrites` is |
| 515 | /// reached. Skip operations in unreachable blocks. Return `true` if any IR |
| 516 | /// was changed. |
| 517 | bool processWorklist(); |
| 518 | |
| 519 | /// The pattern rewriter that is used for making IR modifications and is |
| 520 | /// passed to rewrite patterns. |
| 521 | PatternRewriter rewriter; |
| 522 | |
| 523 | /// The worklist for this transformation keeps track of the operations that |
| 524 | /// need to be (re)visited. |
| 525 | #ifdef MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 526 | RandomizedWorklist worklist; |
| 527 | #else |
| 528 | Worklist worklist; |
| 529 | #endif // MLIR_GREEDY_REWRITE_RANDOMIZER_SEED |
| 530 | |
| 531 | /// Configuration information for how to simplify. |
| 532 | const GreedyRewriteConfig config; |
| 533 | |
| 534 | /// The list of ops we are restricting our rewrites to. These include the |
| 535 | /// supplied set of ops as well as new ops created while rewriting those ops |
| 536 | /// depending on `strictMode`. This set is not maintained when |
| 537 | /// `config.strictMode` is GreedyRewriteStrictness::AnyOp. |
| 538 | llvm::SmallDenseSet<Operation *, 4> strictModeFilteredOps; |
| 539 | |
| 540 | /// Tracks block reachability while the worklist is processed. The rewriter |
| 541 | /// notifies this listener, which forwards to the driver. |
| 542 | ReachabilityListener reachabilityListener; |
| 543 | |
| 544 | private: |
| 545 | /// Look over the provided operands for any defining operations that should |
| 546 | /// be re-added to the worklist. This function should be called when an |
| 547 | /// operation is modified or removed, as it may trigger further |
| 548 | /// simplifications. |
| 549 | void addOperandsToWorklist(Operation *op); |
| 550 | |
| 551 | /// Notify the driver that the given block was inserted. |
| 552 | void notifyBlockInserted(Block *block, Region *previous, |
| 553 | Region::iterator previousIt) override; |
| 554 | |
| 555 | /// Notify the driver that the given block is about to be removed. |
| 556 | void notifyBlockErased(Block *block) override; |
| 557 | |
| 558 | /// For debugging only: Notify the driver of a pattern match failure. |
| 559 | void |
| 560 | notifyMatchFailure(Location loc, |
| 561 | function_ref<void(Diagnostic &)> reasonCallback) override; |
| 562 | |
| 563 | #ifndef NDEBUG |
| 564 | /// A raw output stream used to prefix the debug log. |
| 565 | |
| 566 | llvm::impl::raw_ldbg_ostream os{(Twine("[" ) + DEBUG_TYPE + ":1] " ).str(), |
| 567 | llvm::dbgs()}; |
| 568 | /// A logger used to emit information during the application process. |
| 569 | llvm::ScopedPrinter logger{os}; |
| 570 | #endif |
| 571 | |
| 572 | /// The low-level pattern applicator. |
| 573 | PatternApplicator matcher; |
| 574 | |
| 575 | DeadnessListener deadnessListener; |
| 576 | |
| 577 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 578 | ExpensiveChecks expensiveChecks; |
| 579 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 580 | }; |
| 581 | } // namespace |
| 582 | |
| 583 | /// Return whether `op` may define successors of its block. |
| 584 | static bool mayDefineSuccessors(Operation *op) { |
| 585 | return op->mightHaveTrait<OpTrait::IsTerminator>() || |
| 586 | op->getNumSuccessors() != 0; |
| 587 | } |
| 588 | |
| 589 | /// Collect the distinct successors of `block` that are in the same region. |
| 590 | /// A successor in another region is invalid IR that cannot make |
| 591 | /// a block of this region reachable. |
| 592 | static SmallPtrSet<Block *, 2> getRegionSuccessors(Block *block) { |
| 593 | SmallPtrSet<Block *, 2> successors; |
| 594 | for (Block *successor : block->getSuccessors()) |
| 595 | if (successor->getParent() == block->getParent()) |
| 596 | successors.insert(Ptr: successor); |
| 597 | return successors; |
| 598 | } |
| 599 | |
| 600 | void ReachabilityListener::RegionState::traverse(Region *region) { |
| 601 | // Clear rather than reassign, to keep the allocations for the next |
| 602 | // traversal. |
| 603 | reachable.clear(); |
| 604 | uncertain.clear(); |
| 605 | changedBlocks.clear(); |
| 606 | removedBlocks.clear(); |
| 607 | entry = ®ion->front(); |
| 608 | addReachable(roots: {entry}, /*isUncertain=*/false); |
| 609 | } |
| 610 | |
| 611 | void ReachabilityListener::RegionState::addReachable(SmallVector<Block *> roots, |
| 612 | bool isUncertain) { |
| 613 | while (!roots.empty()) { |
| 614 | auto [it, inserted] = reachable.try_emplace(Key: roots.pop_back_val()); |
| 615 | if (!inserted) |
| 616 | continue; |
| 617 | auto successors = getRegionSuccessors(block: it->first); |
| 618 | it->second.append(in_start: successors.begin(), in_end: successors.end()); |
| 619 | if (isUncertain) |
| 620 | uncertain.insert(V: it->first); |
| 621 | roots.append(RHS: it->second); |
| 622 | } |
| 623 | } |
| 624 | |
| 625 | void ReachabilityListener::RegionState::markUncertain(Block *block) { |
| 626 | SmallVector<Block *> worklist{block}; |
| 627 | while (!worklist.empty()) { |
| 628 | Block *current = worklist.pop_back_val(); |
| 629 | auto it = reachable.find(Val: current); |
| 630 | if (it == reachable.end() || !uncertain.insert(V: current).second) |
| 631 | continue; |
| 632 | worklist.append(RHS: it->second); |
| 633 | } |
| 634 | } |
| 635 | |
| 636 | LogicalResult ReachabilityListener::RegionState::applyChanges() { |
| 637 | if (changedBlocks.empty() && removedBlocks.empty()) |
| 638 | return success(); |
| 639 | // Blocks are dropped after the loop, so that the snapshot of a lost block |
| 640 | // remains available to every changed block that lost an edge to it. |
| 641 | SmallVector<Block *> unreachable; |
| 642 | for (Block *changed : changedBlocks) { |
| 643 | // A removed block is no longer part of the region, and a change in an |
| 644 | // uncached block cannot make any block reachable. |
| 645 | if (removedBlocks.contains(V: changed)) |
| 646 | continue; |
| 647 | auto it = reachable.find(Val: changed); |
| 648 | if (it == reachable.end()) |
| 649 | continue; |
| 650 | // Keep even a disconnected block's snapshot up to date: a later rewrite |
| 651 | // may reconnect it without querying the block itself. Its added successors |
| 652 | // must remain uncertain until a traversal establishes their reachability. |
| 653 | if (changed != entry && changed->hasNoPredecessors()) |
| 654 | markUncertain(block: changed); |
| 655 | // Keep the snapshot available while marking lost successors uncertain. |
| 656 | // A lost self-edge can make that traversal visit `changed` itself. |
| 657 | const auto &old = it->second; |
| 658 | auto current = getRegionSuccessors(block: changed); |
| 659 | for (Block *lost : old) { |
| 660 | if (current.contains(Ptr: lost)) |
| 661 | continue; |
| 662 | // The successors of a reachable block are reachable, so `lost` has a |
| 663 | // snapshot unless the cache is inconsistent. This is not expected to |
| 664 | // happen; the failure is a safety net that forces a traversal. |
| 665 | auto lostIt = reachable.find(Val: lost); |
| 666 | if (lostIt == reachable.end()) |
| 667 | return failure(); |
| 668 | // `lost` and every block behind it may have become unreachable. When |
| 669 | // `lost` is gone or has no predecessors left, it is unreachable; if all |
| 670 | // of its cached successors are still successors of `changed`, nothing |
| 671 | // else changed. This is the shape left by folding a constant conditional |
| 672 | // branch and by merging a block into its predecessor. Any other lost |
| 673 | // edge leaves the blocks behind `lost` uncertain until a query for one |
| 674 | // of them traverses the region. |
| 675 | bool isGone = removedBlocks.contains(V: lost) || lost->hasNoPredecessors(); |
| 676 | if (isGone && llvm::all_of(Range&: lostIt->second, P: [&](Block *successor) { |
| 677 | return current.contains(Ptr: successor); |
| 678 | })) { |
| 679 | unreachable.push_back(Elt: lost); |
| 680 | continue; |
| 681 | } |
| 682 | markUncertain(block: lost); |
| 683 | } |
| 684 | // Added edges can only make more blocks reachable. Blocks reached from an |
| 685 | // uncertain block are uncertain as well. |
| 686 | SmallVector<Block *> roots; |
| 687 | for (Block *successor : current) |
| 688 | if (!reachable.contains(Val: successor)) |
| 689 | roots.push_back(Elt: successor); |
| 690 | // Nothing was inserted into `reachable` since `it` was looked up. |
| 691 | it->second.assign(in_start: current.begin(), in_end: current.end()); |
| 692 | addReachable(roots: std::move(roots), isUncertain: uncertain.contains(V: changed)); |
| 693 | } |
| 694 | // Drop every block that left the region, so that no stale key can match a |
| 695 | // block inserted later at the same address. |
| 696 | unreachable.append(in_start: removedBlocks.begin(), in_end: removedBlocks.end()); |
| 697 | for (Block *block : unreachable) { |
| 698 | reachable.erase(Val: block); |
| 699 | uncertain.erase(V: block); |
| 700 | } |
| 701 | changedBlocks.clear(); |
| 702 | removedBlocks.clear(); |
| 703 | return success(); |
| 704 | } |
| 705 | |
| 706 | bool ReachabilityListener::isBlockReachable(Block *block) { |
| 707 | Region *region = block->getParent(); |
| 708 | // A detached block is treated as reachable, as is the entry block. |
| 709 | if (!region || block == ®ion->front()) |
| 710 | return true; |
| 711 | if (block->hasNoPredecessors()) |
| 712 | return false; |
| 713 | auto [it, inserted] = regionStates.try_emplace(Key: region); |
| 714 | RegionState &state = it->second; |
| 715 | bool isStale = inserted || state.entry != ®ion->front(); |
| 716 | if (isStale || failed(Result: state.applyChanges()) || |
| 717 | state.uncertain.contains(V: block)) |
| 718 | state.traverse(region); |
| 719 | bool result = state.reachable.contains(Val: block); |
| 720 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 721 | assert(result == region->front().isReachable(block) && |
| 722 | "reachability cache disagrees with a traversal" ); |
| 723 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 724 | return result; |
| 725 | } |
| 726 | |
| 727 | bool ReachabilityListener::isReachable(Operation *op) { |
| 728 | // A nested region can be locally reachable while its owning operation is in |
| 729 | // an unreachable block, so check every containing block up to the scope. |
| 730 | while (Block *block = op->getBlock()) { |
| 731 | if (!isBlockReachable(block)) |
| 732 | return false; |
| 733 | Region *region = block->getParent(); |
| 734 | if (!region || region == scope) |
| 735 | break; |
| 736 | op = region->getParentOp(); |
| 737 | } |
| 738 | return true; |
| 739 | } |
| 740 | |
| 741 | void ReachabilityListener::notifyBlockInserted(Block *block, Region *previous, |
| 742 | Region::iterator previousIt) { |
| 743 | Region *region = block->getParent(); |
| 744 | // A block moved within its region keeps its reachability, unless it becomes |
| 745 | // the entry block, which the next query detects. A block that is new to the |
| 746 | // region is unreachable until a recorded terminator change adds an edge to |
| 747 | // it, but a stale entry from an earlier removal cannot be trusted. |
| 748 | if (previous != region) { |
| 749 | if (previous) |
| 750 | markRemoved(region: previous, block); |
| 751 | auto it = regionStates.find(Val: region); |
| 752 | if (it != regionStates.end() && (it->second.removedBlocks.contains(V: block) || |
| 753 | it->second.reachable.contains(Val: block))) |
| 754 | regionStates.erase(I: it); |
| 755 | } |
| 756 | RewriterBase::ForwardingListener::notifyBlockInserted(block, previous, |
| 757 | previousIt); |
| 758 | } |
| 759 | |
| 760 | void ReachabilityListener::notifyBlockErased(Block *block) { |
| 761 | markRemoved(region: block->getParent(), block); |
| 762 | RewriterBase::ForwardingListener::notifyBlockErased(block); |
| 763 | } |
| 764 | |
| 765 | void ReachabilityListener::notifyOperationInserted( |
| 766 | Operation *op, OpBuilder::InsertPoint previous) { |
| 767 | if (mayDefineSuccessors(op)) { |
| 768 | markChanged(block: op->getBlock()); |
| 769 | if (previous.isSet()) |
| 770 | markChanged(block: previous.getBlock()); |
| 771 | } |
| 772 | RewriterBase::ForwardingListener::notifyOperationInserted(op, previous); |
| 773 | } |
| 774 | |
| 775 | void ReachabilityListener::notifyOperationModified(Operation *op) { |
| 776 | if (mayDefineSuccessors(op)) |
| 777 | markChanged(block: op->getBlock()); |
| 778 | RewriterBase::ForwardingListener::notifyOperationModified(op); |
| 779 | } |
| 780 | |
| 781 | void ReachabilityListener::notifyOperationErased(Operation *op) { |
| 782 | if (mayDefineSuccessors(op)) |
| 783 | markChanged(block: op->getBlock()); |
| 784 | // Do not retain keys for regions that are about to be destroyed. |
| 785 | for (Region ®ion : op->getRegions()) |
| 786 | regionStates.erase(Val: ®ion); |
| 787 | RewriterBase::ForwardingListener::notifyOperationErased(op); |
| 788 | } |
| 789 | |
| 790 | GreedyPatternRewriteDriver::GreedyPatternRewriteDriver( |
| 791 | MLIRContext *ctx, const FrozenRewritePatternSet &patterns, |
| 792 | const GreedyRewriteConfig &config) |
| 793 | : rewriter(ctx), config(config), |
| 794 | reachabilityListener(this, config.getScope()), matcher(patterns), |
| 795 | deadnessListener(&reachabilityListener) |
| 796 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 797 | // clang-format off |
| 798 | , expensiveChecks( |
| 799 | /*listener=*/&deadnessListener, |
| 800 | /*topLevel=*/config.getScope() ? config.getScope()->getParentOp() |
| 801 | : nullptr) |
| 802 | // clang-format on |
| 803 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 804 | { |
| 805 | // Apply a simple cost model based solely on pattern benefit. |
| 806 | matcher.applyDefaultCostModel(); |
| 807 | |
| 808 | // Set up listener. |
| 809 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 810 | // Forward notifications through expensive checks, deadness, reachability, |
| 811 | // and the worklist driver, in that order. |
| 812 | rewriter.setListener(&expensiveChecks); |
| 813 | #else |
| 814 | rewriter.setListener(&deadnessListener); |
| 815 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 816 | } |
| 817 | |
| 818 | bool GreedyPatternRewriteDriver::processWorklist() { |
| 819 | // The cache is only maintained while this worklist pass runs. Between |
| 820 | // passes, the IR changes without notifications, e.g. in region |
| 821 | // simplification and in the unreachable-block sweep. |
| 822 | llvm::scope_exit clearReachability([&] { reachabilityListener.clear(); }); |
| 823 | |
| 824 | #ifndef NDEBUG |
| 825 | const char *logLineComment = |
| 826 | "//===-------------------------------------------===//\n" ; |
| 827 | |
| 828 | /// A utility function to log a process result for the given reason. |
| 829 | auto logResult = [&](StringRef result, const llvm::Twine &msg = {}) { |
| 830 | logger.unindent(); |
| 831 | logger.startLine() << "} -> " << result; |
| 832 | if (!msg.isTriviallyEmpty()) |
| 833 | logger.getOStream() << " : " << msg; |
| 834 | logger.getOStream() << "\n" ; |
| 835 | }; |
| 836 | auto logResultWithLine = [&](StringRef result, const llvm::Twine &msg = {}) { |
| 837 | logResult(result, msg); |
| 838 | logger.startLine() << logLineComment; |
| 839 | }; |
| 840 | #endif |
| 841 | |
| 842 | bool changed = false; |
| 843 | int64_t numRewrites = 0; |
| 844 | while (!worklist.empty() && |
| 845 | (numRewrites < config.getMaxNumRewrites() || |
| 846 | config.getMaxNumRewrites() == GreedyRewriteConfig::kNoLimit)) { |
| 847 | auto *op = worklist.pop(); |
| 848 | if (!reachabilityListener.isReachable(op)) { |
| 849 | LLVM_DEBUG(logger.startLine() << "Skipping unreachable operation : '" |
| 850 | << op->getName() << "'(" << op << ")\n" ); |
| 851 | continue; |
| 852 | } |
| 853 | |
| 854 | LLVM_DEBUG({ |
| 855 | logger.getOStream() << "\n" ; |
| 856 | logger.startLine() << logLineComment; |
| 857 | logger.startLine() << "Processing operation : '" << op->getName() << "'(" |
| 858 | << op << ") {\n" ; |
| 859 | logger.indent(); |
| 860 | |
| 861 | // If the operation has no regions, just print it here. |
| 862 | if (op->getNumRegions() == 0) { |
| 863 | op->print( |
| 864 | logger.startLine(), |
| 865 | OpPrintingFlags().printGenericOpForm().elideLargeElementsAttrs()); |
| 866 | logger.getOStream() << "\n\n" ; |
| 867 | } |
| 868 | }); |
| 869 | |
| 870 | // If the operation is trivially dead - remove it. |
| 871 | if (deadnessListener.isOpTriviallyDead(op)) { |
| 872 | rewriter.eraseOp(op); |
| 873 | changed = true; |
| 874 | |
| 875 | LLVM_DEBUG(logResultWithLine("success" , "operation is trivially dead" )); |
| 876 | continue; |
| 877 | } |
| 878 | |
| 879 | // Try to fold this op. Do not fold constant ops. That would lead to an |
| 880 | // infinite folding loop, as every constant op would be folded to an |
| 881 | // Attribute and then immediately be rematerialized as a constant op, which |
| 882 | // is then put on the worklist. |
| 883 | if (config.isFoldingEnabled() && !op->hasTrait<OpTrait::ConstantLike>()) { |
| 884 | SmallVector<OpFoldResult> foldResults; |
| 885 | if (succeeded(Result: op->fold(results&: foldResults))) { |
| 886 | LLVM_DEBUG(logResultWithLine("success" , "operation was folded" )); |
| 887 | #ifndef NDEBUG |
| 888 | Operation *dumpRootOp = getDumpRootOp(op); |
| 889 | #endif // NDEBUG |
| 890 | if (foldResults.empty()) { |
| 891 | // Folding modified the op without using the rewriter. Notify the |
| 892 | // cache listeners, which forward the modification to the driver. |
| 893 | deadnessListener.notifyOperationModified(op); |
| 894 | changed = true; |
| 895 | LLVM_DEBUG(logSuccessfulFolding(dumpRootOp)); |
| 896 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 897 | expensiveChecks.notifyFoldingSuccess(); |
| 898 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 899 | continue; |
| 900 | } |
| 901 | |
| 902 | // Op results can be replaced with `foldResults`. |
| 903 | assert(foldResults.size() == op->getNumResults() && |
| 904 | "folder produced incorrect number of results" ); |
| 905 | OpBuilder::InsertionGuard g(rewriter); |
| 906 | rewriter.setInsertionPoint(op); |
| 907 | SmallVector<Value> replacements; |
| 908 | bool materializationSucceeded = true; |
| 909 | for (auto [ofr, resultType] : |
| 910 | llvm::zip_equal(t&: foldResults, u: op->getResultTypes())) { |
| 911 | if (auto value = dyn_cast<Value>(Val&: ofr)) { |
| 912 | assert(value.getType() == resultType && |
| 913 | "folder produced value of incorrect type" ); |
| 914 | replacements.push_back(Elt: value); |
| 915 | continue; |
| 916 | } |
| 917 | // Materialize Attributes as SSA values. |
| 918 | Operation *constOp = op->getDialect()->materializeConstant( |
| 919 | builder&: rewriter, value: cast<Attribute>(Val&: ofr), type: resultType, loc: op->getLoc()); |
| 920 | |
| 921 | if (!constOp) { |
| 922 | // If materialization fails, cleanup any operations generated for |
| 923 | // the previous results. |
| 924 | llvm::SmallDenseSet<Operation *> replacementOps; |
| 925 | for (Value replacement : replacements) { |
| 926 | assert(replacement.use_empty() && |
| 927 | "folder reused existing op for one result but constant " |
| 928 | "materialization failed for another result" ); |
| 929 | replacementOps.insert(V: replacement.getDefiningOp()); |
| 930 | } |
| 931 | for (Operation *op : replacementOps) { |
| 932 | rewriter.eraseOp(op); |
| 933 | } |
| 934 | |
| 935 | materializationSucceeded = false; |
| 936 | break; |
| 937 | } |
| 938 | |
| 939 | assert(constOp->hasTrait<OpTrait::ConstantLike>() && |
| 940 | "materializeConstant produced op that is not a ConstantLike" ); |
| 941 | assert(constOp->getResultTypes()[0] == resultType && |
| 942 | "materializeConstant produced incorrect result type" ); |
| 943 | replacements.push_back(Elt: constOp->getResult(idx: 0)); |
| 944 | } |
| 945 | |
| 946 | if (materializationSucceeded) { |
| 947 | rewriter.replaceOp(op, newValues: replacements); |
| 948 | changed = true; |
| 949 | LLVM_DEBUG(logSuccessfulFolding(dumpRootOp)); |
| 950 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 951 | expensiveChecks.notifyFoldingSuccess(); |
| 952 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 953 | continue; |
| 954 | } |
| 955 | } |
| 956 | } |
| 957 | |
| 958 | // Try to match one of the patterns. The rewriter is automatically |
| 959 | // notified of any necessary changes, so there is nothing else to do |
| 960 | // here. |
| 961 | auto canApplyCallback = [&](const Pattern &pattern) { |
| 962 | LLVM_DEBUG({ |
| 963 | logger.getOStream() << "\n" ; |
| 964 | logger.startLine() << "* Pattern " << pattern.getDebugName() << " : '" |
| 965 | << op->getName() << " -> (" ; |
| 966 | llvm::interleaveComma(pattern.getGeneratedOps(), logger.getOStream()); |
| 967 | logger.getOStream() << ")' {\n" ; |
| 968 | logger.indent(); |
| 969 | }); |
| 970 | if (RewriterBase::Listener *listener = config.getListener()) |
| 971 | listener->notifyPatternBegin(pattern, op); |
| 972 | return true; |
| 973 | }; |
| 974 | function_ref<bool(const Pattern &)> canApply = canApplyCallback; |
| 975 | auto onFailureCallback = [&](const Pattern &pattern) { |
| 976 | LLVM_DEBUG(logResult("failure" , "pattern failed to match" )); |
| 977 | if (RewriterBase::Listener *listener = config.getListener()) |
| 978 | listener->notifyPatternEnd(pattern, status: failure()); |
| 979 | }; |
| 980 | function_ref<void(const Pattern &)> onFailure = onFailureCallback; |
| 981 | auto onSuccessCallback = [&](const Pattern &pattern) { |
| 982 | LLVM_DEBUG(logResult("success" , "pattern applied successfully" )); |
| 983 | if (RewriterBase::Listener *listener = config.getListener()) |
| 984 | listener->notifyPatternEnd(pattern, status: success()); |
| 985 | return success(); |
| 986 | }; |
| 987 | function_ref<LogicalResult(const Pattern &)> onSuccess = onSuccessCallback; |
| 988 | |
| 989 | #ifdef NDEBUG |
| 990 | // Optimization: PatternApplicator callbacks are not needed when running in |
| 991 | // optimized mode and without a listener. |
| 992 | if (!config.getListener()) { |
| 993 | canApply = nullptr; |
| 994 | onFailure = nullptr; |
| 995 | onSuccess = nullptr; |
| 996 | } |
| 997 | #endif // NDEBUG |
| 998 | |
| 999 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1000 | if (config.getScope()) { |
| 1001 | expensiveChecks.computeFingerPrints(config.getScope()->getParentOp()); |
| 1002 | } |
| 1003 | llvm::scope_exit clearFingerprints([&]() { expensiveChecks.clear(); }); |
| 1004 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1005 | |
| 1006 | LogicalResult matchResult = |
| 1007 | matcher.matchAndRewrite(op, rewriter, canApply, onFailure, onSuccess); |
| 1008 | |
| 1009 | if (succeeded(Result: matchResult)) { |
| 1010 | LLVM_DEBUG(logResultWithLine("success" , "at least one pattern matched" )); |
| 1011 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1012 | expensiveChecks.notifyRewriteSuccess(); |
| 1013 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1014 | changed = true; |
| 1015 | ++numRewrites; |
| 1016 | } else { |
| 1017 | LLVM_DEBUG(logResultWithLine("failure" , "all patterns failed to match" )); |
| 1018 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1019 | expensiveChecks.notifyRewriteFailure(); |
| 1020 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1021 | } |
| 1022 | } |
| 1023 | |
| 1024 | return changed; |
| 1025 | } |
| 1026 | |
| 1027 | void GreedyPatternRewriteDriver::addToWorklist(Operation *op) { |
| 1028 | assert(op && "expected valid op" ); |
| 1029 | // Gather potential ancestors while looking for a "scope" parent region. |
| 1030 | SmallVector<Operation *, 8> ancestors; |
| 1031 | Region *region = nullptr; |
| 1032 | do { |
| 1033 | ancestors.push_back(Elt: op); |
| 1034 | region = op->getParentRegion(); |
| 1035 | if (config.getScope() == region) { |
| 1036 | // Scope (can be `nullptr`) was reached. Stop traveral and enqueue ops. |
| 1037 | for (Operation *op : ancestors) |
| 1038 | addSingleOpToWorklist(op); |
| 1039 | return; |
| 1040 | } |
| 1041 | if (region == nullptr) |
| 1042 | return; |
| 1043 | } while ((op = region->getParentOp())); |
| 1044 | } |
| 1045 | |
| 1046 | void GreedyPatternRewriteDriver::addSingleOpToWorklist(Operation *op) { |
| 1047 | if (config.getStrictness() == GreedyRewriteStrictness::AnyOp || |
| 1048 | strictModeFilteredOps.contains(V: op)) |
| 1049 | worklist.push(op); |
| 1050 | } |
| 1051 | |
| 1052 | void GreedyPatternRewriteDriver::notifyBlockInserted( |
| 1053 | Block *block, Region *previous, Region::iterator previousIt) { |
| 1054 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1055 | listener->notifyBlockInserted(block, previous, previousIt); |
| 1056 | } |
| 1057 | |
| 1058 | void GreedyPatternRewriteDriver::notifyBlockErased(Block *block) { |
| 1059 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1060 | listener->notifyBlockErased(block); |
| 1061 | } |
| 1062 | |
| 1063 | void GreedyPatternRewriteDriver::notifyOperationInserted( |
| 1064 | Operation *op, OpBuilder::InsertPoint previous) { |
| 1065 | LLVM_DEBUG({ |
| 1066 | logger.startLine() << "** Insert : '" << op->getName() << "'(" << op |
| 1067 | << ")\n" ; |
| 1068 | }); |
| 1069 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1070 | listener->notifyOperationInserted(op, previous); |
| 1071 | if (config.getStrictness() == GreedyRewriteStrictness::ExistingAndNewOps) |
| 1072 | strictModeFilteredOps.insert(V: op); |
| 1073 | addToWorklist(op); |
| 1074 | } |
| 1075 | |
| 1076 | void GreedyPatternRewriteDriver::notifyOperationModified(Operation *op) { |
| 1077 | LLVM_DEBUG({ |
| 1078 | logger.startLine() << "** Modified: '" << op->getName() << "'(" << op |
| 1079 | << ")\n" ; |
| 1080 | }); |
| 1081 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1082 | listener->notifyOperationModified(op); |
| 1083 | addToWorklist(op); |
| 1084 | } |
| 1085 | |
| 1086 | void GreedyPatternRewriteDriver::addOperandsToWorklist(Operation *op) { |
| 1087 | for (Value operand : op->getOperands()) { |
| 1088 | // If this operand currently has at most 2 users, add its defining op to the |
| 1089 | // worklist. Indeed, after the op is deleted, then the operand will have at |
| 1090 | // most 1 user left. If it has 0 users left, it can be deleted too, |
| 1091 | // and if it has 1 user left, there may be further canonicalization |
| 1092 | // opportunities. |
| 1093 | if (!operand) |
| 1094 | continue; |
| 1095 | |
| 1096 | auto *defOp = operand.getDefiningOp(); |
| 1097 | if (!defOp) |
| 1098 | continue; |
| 1099 | |
| 1100 | Operation *otherUser = nullptr; |
| 1101 | bool hasMoreThanTwoUses = false; |
| 1102 | for (auto *user : operand.getUsers()) { |
| 1103 | if (user == op || user == otherUser) |
| 1104 | continue; |
| 1105 | if (!otherUser) { |
| 1106 | otherUser = user; |
| 1107 | continue; |
| 1108 | } |
| 1109 | hasMoreThanTwoUses = true; |
| 1110 | break; |
| 1111 | } |
| 1112 | if (hasMoreThanTwoUses) |
| 1113 | continue; |
| 1114 | |
| 1115 | addToWorklist(op: defOp); |
| 1116 | } |
| 1117 | } |
| 1118 | |
| 1119 | void GreedyPatternRewriteDriver::notifyOperationErased(Operation *op) { |
| 1120 | LLVM_DEBUG({ |
| 1121 | logger.startLine() << "** Erase : '" << op->getName() << "'(" << op |
| 1122 | << ")\n" ; |
| 1123 | }); |
| 1124 | |
| 1125 | #ifndef NDEBUG |
| 1126 | // Only ops that are within the configured scope are added to the worklist of |
| 1127 | // the greedy pattern rewriter. Moreover, the parent op of the scope region is |
| 1128 | // the part of the IR that is taken into account for the "expensive checks". |
| 1129 | // A greedy pattern rewrite is not allowed to erase the parent op of the scope |
| 1130 | // region, as that would break the worklist handling and the expensive checks. |
| 1131 | if (Region *scope = config.getScope(); scope->getParentOp() == op) |
| 1132 | llvm_unreachable( |
| 1133 | "scope region must not be erased during greedy pattern rewrite" ); |
| 1134 | #endif // NDEBUG |
| 1135 | |
| 1136 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1137 | listener->notifyOperationErased(op); |
| 1138 | |
| 1139 | addOperandsToWorklist(op); |
| 1140 | worklist.remove(op); |
| 1141 | |
| 1142 | if (config.getStrictness() != GreedyRewriteStrictness::AnyOp) |
| 1143 | strictModeFilteredOps.erase(V: op); |
| 1144 | } |
| 1145 | |
| 1146 | void GreedyPatternRewriteDriver::notifyOperationReplaced( |
| 1147 | Operation *op, ValueRange replacement) { |
| 1148 | LLVM_DEBUG({ |
| 1149 | logger.startLine() << "** Replace : '" << op->getName() << "'(" << op |
| 1150 | << ")\n" ; |
| 1151 | }); |
| 1152 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1153 | listener->notifyOperationReplaced(op, replacement); |
| 1154 | } |
| 1155 | |
| 1156 | void GreedyPatternRewriteDriver::notifyMatchFailure( |
| 1157 | Location loc, function_ref<void(Diagnostic &)> reasonCallback) { |
| 1158 | LLVM_DEBUG({ |
| 1159 | Diagnostic diag(loc, DiagnosticSeverity::Remark); |
| 1160 | reasonCallback(diag); |
| 1161 | logger.startLine() << "** Match Failure : " << diag.str() << "\n" ; |
| 1162 | }); |
| 1163 | if (RewriterBase::Listener *listener = config.getListener()) |
| 1164 | listener->notifyMatchFailure(loc, reasonCallback); |
| 1165 | } |
| 1166 | |
| 1167 | //===----------------------------------------------------------------------===// |
| 1168 | // RegionPatternRewriteDriver |
| 1169 | //===----------------------------------------------------------------------===// |
| 1170 | |
| 1171 | namespace { |
| 1172 | /// This driver simplfies all ops in a region. If a scope is set in the |
| 1173 | /// config, the provided region must be within that scope. |
| 1174 | class RegionPatternRewriteDriver : public GreedyPatternRewriteDriver { |
| 1175 | public: |
| 1176 | explicit RegionPatternRewriteDriver(MLIRContext *ctx, |
| 1177 | const FrozenRewritePatternSet &patterns, |
| 1178 | const GreedyRewriteConfig &config, |
| 1179 | Region ®ions); |
| 1180 | |
| 1181 | /// Simplify ops inside `region` and simplify the region itself. Return |
| 1182 | /// success if the transformation converged. |
| 1183 | LogicalResult simplify(bool *changed) &&; |
| 1184 | |
| 1185 | private: |
| 1186 | /// The region that is simplified. |
| 1187 | Region ®ion; |
| 1188 | }; |
| 1189 | } // namespace |
| 1190 | |
| 1191 | RegionPatternRewriteDriver::RegionPatternRewriteDriver( |
| 1192 | MLIRContext *ctx, const FrozenRewritePatternSet &patterns, |
| 1193 | const GreedyRewriteConfig &config, Region ®ion) |
| 1194 | : GreedyPatternRewriteDriver(ctx, patterns, config), region(region) { |
| 1195 | // Populate strict mode ops. |
| 1196 | if (config.getStrictness() != GreedyRewriteStrictness::AnyOp) { |
| 1197 | region.walk(callback: [&](Operation *op) { strictModeFilteredOps.insert(V: op); }); |
| 1198 | } |
| 1199 | #ifndef NDEBUG |
| 1200 | // Verify that the region is within the configured scope (if any). |
| 1201 | if (Region *scope = config.getScope()) { |
| 1202 | Region *r = ®ion; |
| 1203 | while (r && r != scope) |
| 1204 | r = r->getParentRegion(); |
| 1205 | assert(r && "provided region is not within the config scope" ); |
| 1206 | } |
| 1207 | #endif |
| 1208 | } |
| 1209 | |
| 1210 | namespace { |
| 1211 | class GreedyPatternRewriteIteration |
| 1212 | : public tracing::ActionImpl<GreedyPatternRewriteIteration> { |
| 1213 | public: |
| 1214 | MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(GreedyPatternRewriteIteration) |
| 1215 | GreedyPatternRewriteIteration(ArrayRef<IRUnit> units, int64_t iteration) |
| 1216 | : tracing::ActionImpl<GreedyPatternRewriteIteration>(units), |
| 1217 | iteration(iteration) {} |
| 1218 | static constexpr StringLiteral tag = "GreedyPatternRewriteIteration" ; |
| 1219 | void print(raw_ostream &os) const override { |
| 1220 | os << "GreedyPatternRewriteIteration(" << iteration << ")" ; |
| 1221 | } |
| 1222 | |
| 1223 | private: |
| 1224 | int64_t iteration = 0; |
| 1225 | }; |
| 1226 | } // namespace |
| 1227 | |
| 1228 | LogicalResult RegionPatternRewriteDriver::simplify(bool *changed) && { |
| 1229 | bool continueRewrites = false; |
| 1230 | bool anyChanged = false; |
| 1231 | int64_t iteration = 0; |
| 1232 | MLIRContext *ctx = rewriter.getContext(); |
| 1233 | do { |
| 1234 | // Check if the iteration limit was reached. |
| 1235 | if (++iteration > config.getMaxIterations() && |
| 1236 | config.getMaxIterations() != GreedyRewriteConfig::kNoLimit) |
| 1237 | break; |
| 1238 | |
| 1239 | // New iteration: start with an empty worklist. |
| 1240 | worklist.clear(); |
| 1241 | |
| 1242 | // `OperationFolder` CSE's constant ops (and may move them into parents |
| 1243 | // regions to enable more aggressive CSE'ing). |
| 1244 | OperationFolder folder(ctx, rewriter.getListener()); |
| 1245 | auto insertKnownConstant = [&](Operation *op) { |
| 1246 | // Check for existing constants when populating the worklist. This avoids |
| 1247 | // accidentally reversing the constant order during processing. |
| 1248 | Attribute constValue; |
| 1249 | if (!matchPattern(op, pattern: m_Constant(bind_value: &constValue))) |
| 1250 | return false; |
| 1251 | auto result = folder.insertKnownConstant(op, constValue); |
| 1252 | anyChanged |= |
| 1253 | result != OperationFolder::ConstantInsertionResult::Unchanged; |
| 1254 | return result == OperationFolder::ConstantInsertionResult::Replaced; |
| 1255 | }; |
| 1256 | |
| 1257 | if (!config.getUseTopDownTraversal()) { |
| 1258 | // Add operations to the worklist in postorder. |
| 1259 | region.walk(callback: [&](Operation *op) { |
| 1260 | if (!config.isConstantCSEEnabled() || !insertKnownConstant(op)) |
| 1261 | addToWorklist(op); |
| 1262 | }); |
| 1263 | } else { |
| 1264 | // Add all nested operations to the worklist in preorder. |
| 1265 | region.walk<WalkOrder::PreOrder>(callback: [&](Operation *op) { |
| 1266 | if (!config.isConstantCSEEnabled() || !insertKnownConstant(op)) { |
| 1267 | addToWorklist(op); |
| 1268 | return WalkResult::advance(); |
| 1269 | } |
| 1270 | return WalkResult::skip(); |
| 1271 | }); |
| 1272 | |
| 1273 | // Reverse the list so our pop-back loop processes them in-order. |
| 1274 | worklist.reverse(); |
| 1275 | } |
| 1276 | |
| 1277 | ctx->executeAction<GreedyPatternRewriteIteration>( |
| 1278 | actionFn: [&] { |
| 1279 | continueRewrites = false; |
| 1280 | |
| 1281 | // Erase unreachable blocks |
| 1282 | // Operations like: |
| 1283 | // %add = arith.addi %add, %add : i64 |
| 1284 | // are legal in unreachable code. Unfortunately many patterns would be |
| 1285 | // unsafe to apply on such IR and can lead to crashes or infinite |
| 1286 | // loops. A rewrite can disconnect more blocks while processWorklist() |
| 1287 | // runs; processWorklist() skips their queued operations until the |
| 1288 | // next sweep, since repeated rewrites on such IR can prevent the |
| 1289 | // worklist pass from returning. |
| 1290 | continueRewrites |= |
| 1291 | succeeded(Result: eraseUnreachableBlocks(rewriter, regions: region)); |
| 1292 | |
| 1293 | continueRewrites |= processWorklist(); |
| 1294 | |
| 1295 | // After applying patterns, make sure that the CFG of each of the |
| 1296 | // regions is kept up to date. |
| 1297 | if (config.getRegionSimplificationLevel() != |
| 1298 | GreedySimplifyRegionLevel::Disabled) { |
| 1299 | continueRewrites |= succeeded(Result: simplifyRegions( |
| 1300 | rewriter, regions: region, |
| 1301 | /*mergeBlocks=*/config.getRegionSimplificationLevel() == |
| 1302 | GreedySimplifyRegionLevel::Aggressive)); |
| 1303 | } |
| 1304 | |
| 1305 | // Optionally run full CSE. If CSE changes the IR we iterate again so |
| 1306 | // that patterns can fire on the deduplicated operations. |
| 1307 | if (config.isCSEBetweenIterationsEnabled()) { |
| 1308 | DominanceInfo domInfo; |
| 1309 | bool cseChanged = false; |
| 1310 | eliminateCommonSubExpressions(rewriter, domInfo, region, |
| 1311 | changed: &cseChanged); |
| 1312 | continueRewrites |= cseChanged; |
| 1313 | } |
| 1314 | }, |
| 1315 | irUnits: {®ion}, args&: iteration); |
| 1316 | anyChanged |= continueRewrites; |
| 1317 | } while (continueRewrites); |
| 1318 | |
| 1319 | if (changed) |
| 1320 | *changed = anyChanged; |
| 1321 | |
| 1322 | // Whether the rewrite converges, i.e. wasn't changed in the last iteration. |
| 1323 | return success(IsSuccess: !continueRewrites); |
| 1324 | } |
| 1325 | |
| 1326 | LogicalResult |
| 1327 | mlir::applyPatternsGreedily(Region ®ion, |
| 1328 | const FrozenRewritePatternSet &patterns, |
| 1329 | GreedyRewriteConfig config, bool *changed) { |
| 1330 | // The top-level operation must be known to be isolated from above to |
| 1331 | // prevent performing canonicalizations on operations defined at or above |
| 1332 | // the region containing 'op'. |
| 1333 | assert(region.getParentOp()->hasTrait<OpTrait::IsIsolatedFromAbove>() && |
| 1334 | "patterns can only be applied to operations IsolatedFromAbove" ); |
| 1335 | |
| 1336 | // Set scope if not specified. |
| 1337 | if (!config.getScope()) |
| 1338 | config.setScope(®ion); |
| 1339 | |
| 1340 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1341 | if (failed(verify(config.getScope()->getParentOp()))) |
| 1342 | llvm::report_fatal_error( |
| 1343 | "greedy pattern rewriter input IR failed to verify" ); |
| 1344 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1345 | |
| 1346 | #ifdef EXPENSIVE_CHECKS |
| 1347 | OperationFingerPrint before(config.getScope()->getParentOp()); |
| 1348 | #endif // EXPENSIVE_CHECKS |
| 1349 | bool rewriteChanged = false; |
| 1350 | |
| 1351 | // Start the pattern driver. |
| 1352 | RegionPatternRewriteDriver driver(region.getContext(), patterns, config, |
| 1353 | region); |
| 1354 | LogicalResult converged = std::move(driver).simplify(changed: &rewriteChanged); |
| 1355 | #ifdef EXPENSIVE_CHECKS |
| 1356 | if (rewriteChanged != |
| 1357 | (before != OperationFingerPrint(config.getScope()->getParentOp()))) |
| 1358 | llvm::report_fatal_error( |
| 1359 | "greedy pattern rewriter changed flag does not match the IR" ); |
| 1360 | #endif // EXPENSIVE_CHECKS |
| 1361 | if (changed) |
| 1362 | *changed = rewriteChanged; |
| 1363 | if (failed(Result: converged)) |
| 1364 | LDBG() << "The pattern rewrite did not converge after scanning " |
| 1365 | << config.getMaxIterations() << " times" ; |
| 1366 | return converged; |
| 1367 | } |
| 1368 | |
| 1369 | //===----------------------------------------------------------------------===// |
| 1370 | // MultiOpPatternRewriteDriver |
| 1371 | //===----------------------------------------------------------------------===// |
| 1372 | |
| 1373 | namespace { |
| 1374 | /// This driver simplfies a list of ops. |
| 1375 | class MultiOpPatternRewriteDriver : public GreedyPatternRewriteDriver { |
| 1376 | public: |
| 1377 | explicit MultiOpPatternRewriteDriver( |
| 1378 | MLIRContext *ctx, const FrozenRewritePatternSet &patterns, |
| 1379 | const GreedyRewriteConfig &config, ArrayRef<Operation *> ops, |
| 1380 | llvm::SmallDenseSet<Operation *, 4> *survivingOps = nullptr); |
| 1381 | |
| 1382 | /// Simplify `ops`. Return `success` if the transformation converged. |
| 1383 | LogicalResult simplify(ArrayRef<Operation *> ops, bool *changed = nullptr) &&; |
| 1384 | |
| 1385 | private: |
| 1386 | void notifyOperationErased(Operation *op) override { |
| 1387 | GreedyPatternRewriteDriver::notifyOperationErased(op); |
| 1388 | if (survivingOps) |
| 1389 | survivingOps->erase(V: op); |
| 1390 | } |
| 1391 | |
| 1392 | /// An optional set of ops that survived the rewrite. This set is populated |
| 1393 | /// at the beginning of `simplifyLocally` with the inititally provided list |
| 1394 | /// of ops. |
| 1395 | llvm::SmallDenseSet<Operation *, 4> *const survivingOps = nullptr; |
| 1396 | }; |
| 1397 | } // namespace |
| 1398 | |
| 1399 | MultiOpPatternRewriteDriver::MultiOpPatternRewriteDriver( |
| 1400 | MLIRContext *ctx, const FrozenRewritePatternSet &patterns, |
| 1401 | const GreedyRewriteConfig &config, ArrayRef<Operation *> ops, |
| 1402 | llvm::SmallDenseSet<Operation *, 4> *survivingOps) |
| 1403 | : GreedyPatternRewriteDriver(ctx, patterns, config), |
| 1404 | survivingOps(survivingOps) { |
| 1405 | if (config.getStrictness() != GreedyRewriteStrictness::AnyOp) |
| 1406 | strictModeFilteredOps.insert_range(R&: ops); |
| 1407 | |
| 1408 | if (survivingOps) { |
| 1409 | survivingOps->clear(); |
| 1410 | survivingOps->insert_range(R&: ops); |
| 1411 | } |
| 1412 | } |
| 1413 | |
| 1414 | LogicalResult MultiOpPatternRewriteDriver::simplify(ArrayRef<Operation *> ops, |
| 1415 | bool *changed) && { |
| 1416 | // Populate the initial worklist. |
| 1417 | for (Operation *op : ops) |
| 1418 | addSingleOpToWorklist(op); |
| 1419 | |
| 1420 | // Process ops on the worklist. |
| 1421 | bool result = processWorklist(); |
| 1422 | if (changed) |
| 1423 | *changed = result; |
| 1424 | |
| 1425 | return success(IsSuccess: worklist.empty()); |
| 1426 | } |
| 1427 | |
| 1428 | /// Find the region that is the closest common ancestor of all given ops. |
| 1429 | /// |
| 1430 | /// Note: This function returns `nullptr` if there is a top-level op among the |
| 1431 | /// given list of ops. |
| 1432 | static Region *findCommonAncestor(ArrayRef<Operation *> ops) { |
| 1433 | assert(!ops.empty() && "expected at least one op" ); |
| 1434 | // Fast path in case there is only one op. |
| 1435 | if (ops.size() == 1) |
| 1436 | return ops.front()->getParentRegion(); |
| 1437 | |
| 1438 | Region *region = ops.front()->getParentRegion(); |
| 1439 | ops = ops.drop_front(); |
| 1440 | int sz = ops.size(); |
| 1441 | llvm::BitVector remainingOps(sz, true); |
| 1442 | while (region) { |
| 1443 | int pos = -1; |
| 1444 | // Iterate over all remaining ops. |
| 1445 | while ((pos = remainingOps.find_first_in(Begin: pos + 1, End: sz)) != -1) { |
| 1446 | // Is this op contained in `region`? |
| 1447 | if (region->findAncestorOpInRegion(op&: *ops[pos])) |
| 1448 | remainingOps.reset(Idx: pos); |
| 1449 | } |
| 1450 | if (remainingOps.none()) |
| 1451 | break; |
| 1452 | region = region->getParentRegion(); |
| 1453 | } |
| 1454 | return region; |
| 1455 | } |
| 1456 | |
| 1457 | LogicalResult mlir::applyOpPatternsGreedily( |
| 1458 | ArrayRef<Operation *> ops, const FrozenRewritePatternSet &patterns, |
| 1459 | GreedyRewriteConfig config, bool *changed, bool *allErased) { |
| 1460 | if (ops.empty()) { |
| 1461 | if (changed) |
| 1462 | *changed = false; |
| 1463 | if (allErased) |
| 1464 | *allErased = true; |
| 1465 | return success(); |
| 1466 | } |
| 1467 | |
| 1468 | // Determine scope of rewrite. |
| 1469 | if (!config.getScope()) { |
| 1470 | // Compute scope if none was provided. The scope will remain `nullptr` if |
| 1471 | // there is a top-level op among `ops`. |
| 1472 | config.setScope(findCommonAncestor(ops)); |
| 1473 | } else { |
| 1474 | // If a scope was provided, make sure that all ops are in scope. |
| 1475 | #ifndef NDEBUG |
| 1476 | bool allOpsInScope = llvm::all_of(ops, [&](Operation *op) { |
| 1477 | return static_cast<bool>(config.getScope()->findAncestorOpInRegion(*op)); |
| 1478 | }); |
| 1479 | assert(allOpsInScope && "ops must be within the specified scope" ); |
| 1480 | #endif // NDEBUG |
| 1481 | } |
| 1482 | |
| 1483 | #if MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1484 | if (config.getScope() && failed(verify(config.getScope()->getParentOp()))) |
| 1485 | llvm::report_fatal_error( |
| 1486 | "greedy pattern rewriter input IR failed to verify" ); |
| 1487 | #endif // MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS |
| 1488 | |
| 1489 | #ifdef EXPENSIVE_CHECKS |
| 1490 | std::optional<OperationFingerPrint> before; |
| 1491 | if (config.getScope()) |
| 1492 | before.emplace(config.getScope()->getParentOp()); |
| 1493 | #endif // EXPENSIVE_CHECKS |
| 1494 | bool rewriteChanged = false; |
| 1495 | |
| 1496 | // Start the pattern driver. |
| 1497 | llvm::SmallDenseSet<Operation *, 4> surviving; |
| 1498 | MultiOpPatternRewriteDriver driver(ops.front()->getContext(), patterns, |
| 1499 | config, ops, |
| 1500 | allErased ? &surviving : nullptr); |
| 1501 | LogicalResult converged = std::move(driver).simplify(ops, changed: &rewriteChanged); |
| 1502 | #ifdef EXPENSIVE_CHECKS |
| 1503 | if (before && |
| 1504 | rewriteChanged != |
| 1505 | (*before != OperationFingerPrint(config.getScope()->getParentOp()))) |
| 1506 | llvm::report_fatal_error( |
| 1507 | "greedy pattern rewriter changed flag does not match the IR" ); |
| 1508 | #endif // EXPENSIVE_CHECKS |
| 1509 | if (changed) |
| 1510 | *changed = rewriteChanged; |
| 1511 | if (allErased) |
| 1512 | *allErased = surviving.empty(); |
| 1513 | if (failed(Result: converged)) |
| 1514 | LDBG() << "The pattern rewrite did not converge after " |
| 1515 | << config.getMaxNumRewrites() << " rewrites" ; |
| 1516 | return converged; |
| 1517 | } |
| 1518 | |