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
40using namespace mlir;
41
42#define DEBUG_TYPE "greedy-rewriter"
43
44namespace {
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.
60struct 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
134protected:
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
191static 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}
198static 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.
214class Worklist {
215public:
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
238protected:
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
246Worklist::Worklist() { list.reserve(n: 64); }
247
248void Worklist::clear() {
249 list.clear();
250 map.clear();
251}
252
253bool 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
259void 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
267Operation *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
281void 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
291void 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.
302class RandomizedWorklist : public Worklist {
303public:
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
323private:
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.
339class ReachabilityListener : public RewriterBase::ForwardingListener {
340public:
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
360private:
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.
424class DeadnessListener : public RewriterBase::ForwardingListener {
425public:
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
473private:
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.
483class GreedyPatternRewriteDriver : public RewriterBase::Listener {
484protected:
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
544private:
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.
584static 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.
592static 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
600void 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 = &region->front();
608 addReachable(roots: {entry}, /*isUncertain=*/false);
609}
610
611void 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
625void 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
636LogicalResult 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
706bool 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 == &region->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 != &region->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
727bool 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
741void 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
760void ReachabilityListener::notifyBlockErased(Block *block) {
761 markRemoved(region: block->getParent(), block);
762 RewriterBase::ForwardingListener::notifyBlockErased(block);
763}
764
765void 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
775void ReachabilityListener::notifyOperationModified(Operation *op) {
776 if (mayDefineSuccessors(op))
777 markChanged(block: op->getBlock());
778 RewriterBase::ForwardingListener::notifyOperationModified(op);
779}
780
781void 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 &region : op->getRegions())
786 regionStates.erase(Val: &region);
787 RewriterBase::ForwardingListener::notifyOperationErased(op);
788}
789
790GreedyPatternRewriteDriver::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
818bool 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
1027void 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
1046void GreedyPatternRewriteDriver::addSingleOpToWorklist(Operation *op) {
1047 if (config.getStrictness() == GreedyRewriteStrictness::AnyOp ||
1048 strictModeFilteredOps.contains(V: op))
1049 worklist.push(op);
1050}
1051
1052void 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
1058void GreedyPatternRewriteDriver::notifyBlockErased(Block *block) {
1059 if (RewriterBase::Listener *listener = config.getListener())
1060 listener->notifyBlockErased(block);
1061}
1062
1063void 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
1076void 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
1086void 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
1119void 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
1146void 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
1156void 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
1171namespace {
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.
1174class RegionPatternRewriteDriver : public GreedyPatternRewriteDriver {
1175public:
1176 explicit RegionPatternRewriteDriver(MLIRContext *ctx,
1177 const FrozenRewritePatternSet &patterns,
1178 const GreedyRewriteConfig &config,
1179 Region &regions);
1180
1181 /// Simplify ops inside `region` and simplify the region itself. Return
1182 /// success if the transformation converged.
1183 LogicalResult simplify(bool *changed) &&;
1184
1185private:
1186 /// The region that is simplified.
1187 Region &region;
1188};
1189} // namespace
1190
1191RegionPatternRewriteDriver::RegionPatternRewriteDriver(
1192 MLIRContext *ctx, const FrozenRewritePatternSet &patterns,
1193 const GreedyRewriteConfig &config, Region &region)
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 = &region;
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
1210namespace {
1211class GreedyPatternRewriteIteration
1212 : public tracing::ActionImpl<GreedyPatternRewriteIteration> {
1213public:
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
1223private:
1224 int64_t iteration = 0;
1225};
1226} // namespace
1227
1228LogicalResult 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: {&region}, 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
1326LogicalResult
1327mlir::applyPatternsGreedily(Region &region,
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(&region);
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
1373namespace {
1374/// This driver simplfies a list of ops.
1375class MultiOpPatternRewriteDriver : public GreedyPatternRewriteDriver {
1376public:
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
1385private:
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
1399MultiOpPatternRewriteDriver::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
1414LogicalResult 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.
1432static 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
1457LogicalResult 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