[mlir][IR] Trigger operation/block notification for nested clones in the correct order

[springerm]

Summary

Fixes an inconsistency where cloneRegionBefore did not notify the listener of "op insertion" (whereas OpBuilder::clone does). Various parts of the core infrastructure such as the GreedyPatternRewriteDriver depend on such notifications.

Also fixes a bug where no notifications were sent about block creation when cloning IR.

Ops/blocks are notified in such an order in which they could have been created one-by-one with an OpBuilder. This ensures that when a listener is notified about an op being created, it was already notified about the defining ops of the operands (unless there is a block cycle/graph region).

As a consequence, this allows us to use the same cloneRegionBefore implementation in the dialect conversion. This makes it possible to make the function non-virtual and to move this function to the OpBuilder (instead of RewriterBase).

Note: This revision subsumes D144194, D144266 and D144000.

Depends On: D144193

[springerm]

mlir/lib/IR/Builders.cpp

532–533

Note: An alternative would be to not even clone dead blocks. But this would require a different Operation::clone implementation.

mlir/include/mlir/IR/Builders.h

public:
 
   /// Add new block with 'argTypes' arguments and set the insertion point to the
   /// end of it. The block is placed before 'insertBefore'. `locs` contains the
   /// locations of the inserted arguments, and should match the size of
   /// `argTypes`.
   Block *createBlock(Block *insertBefore, TypeRange argTypes = std::nullopt,
                      ArrayRef<Location> locs = std::nullopt);
 
+  /// Clone the blocks that belong to "region" before the given position in
+  /// another region "parent". The two regions must be different. The caller is
+  /// responsible for creating or updating the operation transferring flow of
+  /// control to the region and passing it the correct block arguments.
+  void cloneRegionBefore(Region &region, Region &parent,
+                         Region::iterator before, IRMapping &mapping);
+  void cloneRegionBefore(Region &region, Region &parent,
+                         Region::iterator before);
+  void cloneRegionBefore(Region &region, Block *before);
+
   //===--------------------------------------------------------------------===//
   // Operation Creation
   //===--------------------------------------------------------------------===//
 
   /// Insert the given operation at the current insertion point and return it.
   Operation *insert(Operation *op);
 
   /// Creates an operation given the fields represented as an OperationState.

mlir/include/mlir/IR/PatternMatch.h

public:
   /// Move the blocks that belong to "region" before the given position in
   /// another region "parent". The two regions must be different. The caller
   /// is responsible for creating or updating the operation transferring flow
   /// of control to the region and passing it the correct block arguments.
   virtual void inlineRegionBefore(Region &region, Region &parent,
                                   Region::iterator before);
   void inlineRegionBefore(Region &region, Block *before);
 
-  /// Clone the blocks that belong to "region" before the given position in
-  /// another region "parent". The two regions must be different. The caller is
-  /// responsible for creating or updating the operation transferring flow of
-  /// control to the region and passing it the correct block arguments.
-  virtual void cloneRegionBefore(Region &region, Region &parent,
-                                 Region::iterator before, IRMapping &mapping);
-  void cloneRegionBefore(Region &region, Region &parent,
-                         Region::iterator before);
-  void cloneRegionBefore(Region &region, Block *before);
-
   /// This method replaces the uses of the results of `op` with the values in
   /// `newValues` when the provided `functor` returns true for a specific use.
   /// The number of values in `newValues` is required to match the number of
   /// results of `op`. `allUsesReplaced`, if non-null, is set to true if all of
   /// the uses of `op` were replaced. Note that in some rewriters, the given
   /// 'functor' may be stored beyond the lifetime of the rewrite being applied.
   /// As such, the function should not capture by reference and instead use
   /// value capture as necessary.

mlir/include/mlir/Transforms/DialectConversion.h

void inlineBlockBefore(Block *source, Block *dest, Block::iterator before,
                          ValueRange argValues = std::nullopt) override;
   using PatternRewriter::inlineBlockBefore;
 
   /// PatternRewriter hook for moving blocks out of a region.
   void inlineRegionBefore(Region &region, Region &parent,
                           Region::iterator before) override;
   using PatternRewriter::inlineRegionBefore;
 
-  /// PatternRewriter hook for cloning blocks of one region into another. The
-  /// given region to clone *must* not have been modified as part of conversion
-  /// yet, i.e. it must be within an operation that is either in the process of
-  /// conversion, or has not yet been converted.
-  void cloneRegionBefore(Region &region, Region &parent,
-                         Region::iterator before, IRMapping &mapping) override;
-  using PatternRewriter::cloneRegionBefore;
-
   /// PatternRewriter hook for inserting a new operation.
   void notifyOperationInserted(Operation *op) override;
 
   /// PatternRewriter hook for updating the root operation in-place.
   /// Note: These methods only track updates to the top-level operation itself,
   /// and not nested regions. Updates to regions will still require notification
   /// through other more specific hooks above.
   void startRootUpdate(Operation *op) override;

mlir/lib/IR/Builders.cpp

 //===- Builders.cpp - Helpers for constructing MLIR Classes ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/IR/Builders.h"
 #include "mlir/IR/AffineExpr.h"
 #include "mlir/IR/AffineMap.h"
 #include "mlir/IR/BuiltinTypes.h"
 #include "mlir/IR/Dialect.h"
 #include "mlir/IR/IRMapping.h"
 #include "mlir/IR/IntegerSet.h"
 #include "mlir/IR/Matchers.h"
+#include "mlir/IR/RegionGraphTraits.h"
 #include "mlir/IR/SymbolTable.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace mlir;
 
 //===----------------------------------------------------------------------===//
 // Locations.
 //===----------------------------------------------------------------------===//
 
LogicalResult OpBuilder::tryFold(Operation *op,
 
   // If we were successful, insert any generated constants.
   for (Operation *cst : generatedConstants)
     insert(cst);
 
   return success();
 }
 
+static void notifyOperationCloned(Operation *op, OpBuilder::Listener *listener);
+
+/// Notify the listener that the given range of regions was cloned.
+///
+/// Blocks and operations are emumerated in a order in which they could have
+/// been created separately (without using the `clone` API): Within a region,
+/// blocks are notified according to their successor relationship. Within a
+/// block, operations are notified in forward mode. This ensures that defining
+/// ops are notified before ops that use their results (unless there are
+/// cycles/graph regions).
+static void notifyRegionsCloned(iterator_range<Region::iterator> range,
+                                OpBuilder::Listener *listener) {
+  // Maintain a set of blocks that were not notified yet. This is needed because
+  // the inverse_post_order iterator does not enumerate dead blocks.
+  llvm::SetVector<Block *> remainingBlocks;
+  // The order in which the set is initialized does not matter for correctness,
+  // for better performance, "leaf" blocks with no successors should be starting
+  // point for the block traversal.
+  for (Block &b : llvm::reverse(range))
+    remainingBlocks.insert(&b);
+  // Set of visited blocks that is shared among all inverse_post_order
+  // iterations. This is to avoid that the same block is enumerated multiple
+  // times.
+  llvm::SmallPtrSet<Block *, 4> visited;
+  while (!remainingBlocks.empty()) {
+    // Enumerate predecessors before successors. I.e., reverse post-order.
+    for (Block *b :
+         llvm::inverse_post_order_ext(remainingBlocks.front(), visited)) {
+      auto it = llvm::find(remainingBlocks, b);
+      assert(it != remainingBlocks.end() &&
+             "expected that only remaining blocks are visited");
+      listener->notifyBlockCreated(b);
+      remainingBlocks.erase(it);
+      for (Operation &op : *b)
+        notifyOperationCloned(&op, listener);
+    }
+  }
+}
+
+/// Notify the listener that the given op was cloned.
+static void notifyOperationCloned(Operation *op,
+                                  OpBuilder::Listener *listener) {
+  listener->notifyOperationInserted(op);
+  for (Region &r : op->getRegions())
+    notifyRegionsCloned(r.getBlocks(), listener);
+}
+
 Operation *OpBuilder::clone(Operation &op, IRMapping &mapper) {
   Operation *newOp = op.clone(mapper);
-  // The `insert` call below handles the notification for inserting `newOp`
-  // itself. But if `newOp` has any regions, we need to notify the listener
-  // about any ops that got inserted inside those regions as part of cloning.
-  if (listener) {
-    auto walkFn = [&](Operation *walkedOp) {
-      listener->notifyOperationInserted(walkedOp);
-    };
-    for (Region &region : newOp->getRegions())
-      region.walk(walkFn);
-  }
+
+  // Fast path: If no listener is attached, the op can be inserted directly.
+  if (!listener)
+    return insert(newOp);
+
+  // The `insert` call below handles the notification for inserting `newOp`.
+  // Just notify about nested op/block insertion.
+  for (Region &r : newOp->getRegions())
+    notifyRegionsCloned(r.getBlocks(), listener);
   return insert(newOp);
 }
 
 Operation *OpBuilder::clone(Operation &op) {
   IRMapping mapper;
   return clone(op, mapper);
 }
+
+void OpBuilder::cloneRegionBefore(Region &region, Region &parent,
+                                  Region::iterator before, IRMapping &mapping) {
+  region.cloneInto(&parent, before, mapping);
+
+  // Fast path: If no listener is attached, there is no more work to do.
+  if (!listener)
+    return;
+
+  // Notify about op/block insertion.
+  Region::iterator clonedBeginIt =
+      mapping.lookup(&region.front())->getIterator();
+  notifyRegionsCloned(llvm::make_range(clonedBeginIt, before), listener);
+}
+
+void OpBuilder::cloneRegionBefore(Region &region, Region &parent,
+                                  Region::iterator before) {
+  IRMapping mapping;
+  cloneRegionBefore(region, parent, before, mapping);
+}
+
+void OpBuilder::cloneRegionBefore(Region &region, Block *before) {
+  cloneRegionBefore(region, *before->getParent(), before->getIterator());
+}

mlir/lib/IR/PatternMatch.cpp

 /// region and pass it the correct block arguments.
 void RewriterBase::inlineRegionBefore(Region &region, Region &parent,
                                       Region::iterator before) {
   parent.getBlocks().splice(before, region.getBlocks());
 }
 void RewriterBase::inlineRegionBefore(Region &region, Block *before) {
   inlineRegionBefore(region, *before->getParent(), before->getIterator());
 }
-
-/// Clone the blocks that belong to "region" before the given position in
-/// another region "parent". The two regions must be different. The caller is
-/// responsible for creating or updating the operation transferring flow of
-/// control to the region and passing it the correct block arguments.
-void RewriterBase::cloneRegionBefore(Region &region, Region &parent,
-                                     Region::iterator before,
-                                     IRMapping &mapping) {
-  region.cloneInto(&parent, before, mapping);
-}
-void RewriterBase::cloneRegionBefore(Region &region, Region &parent,
-                                     Region::iterator before) {
-  IRMapping mapping;
-  cloneRegionBefore(region, parent, before, mapping);
-}
-void RewriterBase::cloneRegionBefore(Region &region, Block *before) {
-  cloneRegionBefore(region, *before->getParent(), before->getIterator());
-}

mlir/lib/Transforms/Utils/DialectConversion.cpp

 
 void ConversionPatternRewriter::inlineRegionBefore(Region &region,
                                                    Region &parent,
                                                    Region::iterator before) {
   impl->notifyRegionIsBeingInlinedBefore(region, parent, before);
   PatternRewriter::inlineRegionBefore(region, parent, before);
 }
 
-void ConversionPatternRewriter::cloneRegionBefore(Region &region,
-                                                  Region &parent,
-                                                  Region::iterator before,
-                                                  IRMapping &mapping) {
-  if (region.empty())
-    return;
-
-  PatternRewriter::cloneRegionBefore(region, parent, before, mapping);
-
-  for (Block &b : ForwardDominanceIterator<>::makeIterable(region)) {
-    Block *cloned = mapping.lookup(&b);
-    impl->notifyCreatedBlock(cloned);
-    cloned->walk<WalkOrder::PreOrder, ForwardDominanceIterator<>>(
-        [&](Operation *op) { notifyOperationInserted(op); });
-  }
-}
-
 void ConversionPatternRewriter::notifyOperationInserted(Operation *op) {
   LLVM_DEBUG({
     impl->logger.startLine()
         << "** Insert  : '" << op->getName() << "'(" << op << ")\n";
   });
   impl->createdOps.push_back(op);
 }
 

mlir/test/Transforms/test-strict-pattern-driver.mlir

 // CHECK-EN-LABEL: func @test_erase
 //  CHECK-EN-SAME:     pattern_driver_all_erased = true, pattern_driver_changed = true}
 //       CHECK-EN:   "test.arg0"
 //       CHECK-EN:   "test.arg1"
 //   CHECK-EN-NOT:   "test.erase_op"
 func.func @test_erase() {
   %0 = "test.arg0"() : () -> (i32)
   %1 = "test.arg1"() : () -> (i32)
-  %erase = "test.erase_op"(%0, %1) : (i32, i32) -> (i32)
+  %erase = "test.erase_op"(%0, %1) {worklist} : (i32, i32) -> (i32)
   return
 }
 
 // -----
 
 // CHECK-EN-LABEL: func @test_insert_same_op
 //  CHECK-EN-SAME:     {pattern_driver_all_erased = false, pattern_driver_changed = true}
 //       CHECK-EN:   "test.insert_same_op"() {skip = true}
 //       CHECK-EN:   "test.insert_same_op"() {skip = true}
 func.func @test_insert_same_op() {
-  %0 = "test.insert_same_op"() : () -> (i32)
+  %0 = "test.insert_same_op"() {worklist} : () -> (i32)
   return
 }
 
 // -----
 
 // CHECK-EN-LABEL: func @test_replace_with_new_op
 //  CHECK-EN-SAME:     {pattern_driver_all_erased = true, pattern_driver_changed = true}
 //       CHECK-EN:   %[[n:.*]] = "test.new_op"
 //       CHECK-EN:   "test.dummy_user"(%[[n]])
 //       CHECK-EN:   "test.dummy_user"(%[[n]])
 func.func @test_replace_with_new_op() {
-  %0 = "test.replace_with_new_op"() : () -> (i32)
+  %0 = "test.replace_with_new_op"() {worklist} : () -> (i32)
   %1 = "test.dummy_user"(%0) : (i32) -> (i32)
   %2 = "test.dummy_user"(%0) : (i32) -> (i32)
   return
 }
 
 // -----
 
 // CHECK-EN-LABEL: func @test_replace_with_erase_op
 //  CHECK-EN-SAME:     {pattern_driver_all_erased = true, pattern_driver_changed = true}
 //   CHECK-EN-NOT:   "test.replace_with_new_op"
 //   CHECK-EN-NOT:   "test.erase_op"
 
 // CHECK-EX-LABEL: func @test_replace_with_erase_op
 //  CHECK-EX-SAME:     {pattern_driver_all_erased = true, pattern_driver_changed = true}
 //   CHECK-EX-NOT:   "test.replace_with_new_op"
 //       CHECK-EX:   "test.erase_op"
 func.func @test_replace_with_erase_op() {
-  "test.replace_with_new_op"() {create_erase_op} : () -> ()
+  "test.replace_with_new_op"() {create_erase_op, worklist} : () -> ()
   return
 }
 
 // -----
 
 // CHECK-AN-LABEL: func @test_trigger_rewrite_through_block
 //       CHECK-AN: "test.change_block_op"()[^[[BB0:.*]], ^[[BB0]]]
 //       CHECK-AN: return
 //       CHECK-AN: ^[[BB1:[^:]*]]:
 //       CHECK-AN: "test.implicit_change_op"()[^[[BB1]]]
 func.func @test_trigger_rewrite_through_block() {
   return
 ^bb1:
   // Uses bb1. ChangeBlockOp replaces that and all other usages of bb1 with bb2.
-  "test.change_block_op"() [^bb1, ^bb2] : () -> ()
+  "test.change_block_op"() [^bb1, ^bb2] {worklist} : () -> ()
 ^bb2:
   return
 ^bb3:
   // Also uses bb1. ChangeBlockOp replaces that usage with bb2. This triggers
   // this op being put on the worklist, which triggers ImplicitChangeOp, which,
   // in turn, replaces the successor with bb3.
-  "test.implicit_change_op"() [^bb1] : () -> ()
+  "test.implicit_change_op"() [^bb1] {worklist} : () -> ()
 }
 
 // -----
 
 // CHECK-AN: notifyOperationRemoved: test.foo_b
 // CHECK-AN: notifyOperationRemoved: test.foo_a
 // CHECK-AN: notifyOperationRemoved: test.graph_region
 // CHECK-AN: notifyOperationRemoved: test.erase_op
 // CHECK-AN-LABEL: func @test_remove_graph_region()
 //  CHECK-AN-NEXT:   return
 func.func @test_remove_graph_region() {
   "test.erase_op"() ({
     test.graph_region {
       %0 = "test.foo_a"(%1) : (i1) -> (i1)
       %1 = "test.foo_b"(%0) : (i1) -> (i1)
     }
-  }) : () -> ()
+  }) {worklist} : () -> ()
   return
 }
 
 // -----
 
 // CHECK-AN: notifyOperationRemoved: cf.br
 // CHECK-AN: notifyOperationRemoved: test.bar
 // CHECK-AN: notifyOperationRemoved: cf.br
 // CHECK-AN: notifyOperationRemoved: test.foo
 // CHECK-AN: notifyOperationRemoved: cf.br
 // CHECK-AN: notifyOperationRemoved: test.dummy_op
 // CHECK-AN: notifyOperationRemoved: test.erase_op
 // CHECK-AN-LABEL: func @test_remove_cyclic_blocks()
 //  CHECK-AN-NEXT:   return
 func.func @test_remove_cyclic_blocks() {
   "test.erase_op"() ({
     %x = "test.dummy_op"() : () -> (i1)
     cf.br ^bb1(%x: i1)
   ^bb1(%arg0: i1):
     "test.foo"(%x) : (i1) -> ()
     cf.br ^bb2(%arg0: i1)
   ^bb2(%arg1: i1):
     "test.bar"(%x) : (i1) -> ()
     cf.br ^bb1(%arg1: i1)
-  }) : () -> ()
+  }) {worklist} : () -> ()
   return
 }
 
 // -----
 
 // CHECK-AN: notifyOperationRemoved: test.dummy_op
 // CHECK-AN: notifyOperationRemoved: test.bar
 // CHECK-AN: notifyOperationRemoved: test.qux
func.func @test_remove_dead_blocks() {
   ^bb2(%arg1: i1):
     "test.nested_dummy"() ({
       "test.qux"() : () -> ()
     // The following block is unreachable.
     ^bb3:
       "test.qux_unreachable"() : () -> ()
     }) : () -> ()
     "test.bar"() : () -> ()
-  }) : () -> ()
+  }) {worklist} : () -> ()
   return
 }
 
 // -----
 
 // test.nested_* must be deleted before test.foo.
 // test.bar must be deleted before test.foo.
 
^bb1(%arg0: i1):
     ^dead3:
       "test.nested_e"() : () -> ()
       cf.br ^dead2
     }) : () -> ()
     cf.br ^bb2(%arg0: i1)
   ^bb2(%arg1: i1):
     "test.bar"(%x) : (i1) -> ()
     cf.br ^bb1(%arg1: i1)
-  }) : () -> ()
+  }) {worklist} : () -> ()
   return
 }
 
 // -----
 
 // CHECK-AN: notifyOperationRemoved: test.qux
 // CHECK-AN: notifyOperationRemoved: cf.br
 // CHECK-AN: notifyOperationRemoved: test.foo
 // CHECK-AN: notifyOperationRemoved: cf.br
 // CHECK-AN: notifyOperationRemoved: test.bar
 // CHECK-AN: notifyOperationRemoved: cf.cond_br
 // CHECK-AN-LABEL: func @test_remove_diamond(
 //  CHECK-AN-NEXT:   return
 func.func @test_remove_diamond(%c: i1) {
   "test.erase_op"() ({
     cf.cond_br %c, ^bb1, ^bb2
   ^bb1:
     "test.foo"() : () -> ()
     cf.br ^bb3
   ^bb2:
     "test.bar"() : () -> ()
     cf.br ^bb3
   ^bb3:
     "test.qux"() : () -> ()
+  }) {worklist} : () -> ()
+  return
+}
+
+// -----
+
+// Make sure that test.erase_op is deleted.
+
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.inner_op
+// CHECK-AN: notifyOperationInserted: test.erase_op
+// CHECK-AN: notifyOperationRemoved: test.erase_op
+// CHECK-AN: notifyOperationRemoved: test.inner_op
+// CHECK-AN: notifyOperationRemoved: test.clone_region_in_parent
+// CHECK-AN: notifyOperationRemoved: test.erase_op
+// CHECK-AN-LABEL: func @test_add_cloned_ops_to_worklist
+
+// CHECK-EN-LABEL: func @test_add_cloned_ops_to_worklist
+//  CHECK-EN-NEXT:   "test.dummy_op"() ({
+//  CHECK-EN-NEXT:     "test.another_op"() : () -> ()
+//  CHECK-EN-NEXT:   ^bb1:  // no predecessors
+//  CHECK-EN-NEXT:     "test.inner_op"() : () -> ()
+//  CHECK-EN-NEXT:   }) : () -> ()
+//  CHECK-EN-NEXT:  }
+
+// When strictness=ExistingOps, test.erase_op is not deleted because it was not
+// on the initial worklist.
+
+// CHECK-EX-LABEL: func @test_add_cloned_ops_to_worklist
+//  CHECK-EX-NEXT:   "test.dummy_op"() ({
+//  CHECK-EX-NEXT:     "test.another_op"() : () -> ()
+//  CHECK-EX-NEXT:   ^bb1:  // no predecessors
+//  CHECK-EX-NEXT:     "test.inner_op"() : () -> ()
+//  CHECK-EX-NEXT:     "test.erase_op"() : () -> ()
+//  CHECK-EX-NEXT:   }) : () -> ()
+//  CHECK-EX-NEXT:  }
+func.func @test_add_cloned_ops_to_worklist() {
+  "test.dummy_op"() ({
+    ^bb0():
+    "test.clone_region_in_parent"() ({
+    ^bb1():
+      "test.inner_op"() : () -> ()
+      "test.erase_op"() {worklist} : () -> ()
+    }) {worklist} : () -> ()
+    "test.another_op"() : () -> ()
+  }) {worklist} : () -> ()
+}
+
+// -----
+
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.inner_op
+// CHECK-AN: notifyBlockCreated: block ^bb0 from region 0 from operation 'test.inner_op'
+// CHECK-AN: notifyOperationInserted: test.graph_region
+// CHECK-AN: notifyBlockCreated: block ^bb0 from region 0 from operation 'test.graph_region'
+// CHECK-AN: notifyOperationInserted: test.foo_a
+// CHECK-AN: notifyOperationInserted: test.foo_b
+// CHECK-AN: notifyOperationInserted: test.foo_c
+// The original op is removed.
+// CHECK-AN: notifyOperationRemoved: test.foo_c
+// CHECK-AN: notifyOperationRemoved: test.foo_b
+// CHECK-AN: notifyOperationRemoved: test.foo_a
+// CHECK-AN: notifyOperationRemoved: test.graph_region
+// CHECK-AN: notifyOperationRemoved: test.inner_op
+// CHECK-AN: notifyOperationRemoved: test.clone_region_in_parent
+// CHECK-AN-LABEL: func @test_clone_nested_graph_region
+//       CHECK-AN:   "test.dummy_op"() ({
+//  CHECK-AN-NEXT:     "test.another_op"() : () -> ()
+//  CHECK-AN-NEXT:     ^bb1:  // no predecessors
+//  CHECK-AN-NEXT:       "test.inner_op"() ({
+//  CHECK-AN-NEXT:         test.graph_region {
+//  CHECK-AN-NEXT:           %{{.*}} = "test.foo_a"(%{{.*}}) : (i1) -> i1
+//  CHECK-AN-NEXT:           %{{.*}} = "test.foo_b"(%{{.*}}) : (i1) -> i1
+//  CHECK-AN-NEXT:         }
+//  CHECK-AN-NEXT:         "test.foo_c"() : () -> ()
+//  CHECK-AN-NEXT:       }) : () -> ()
+//  CHECK-AN-NEXT:     }) : () -> ()
+func.func @test_clone_nested_graph_region() {
+  "test.dummy_op"() ({
+    ^bb0():
+    "test.clone_region_in_parent"() ({
+    ^bb1():
+      "test.inner_op"() ({
+        test.graph_region {
+          %0 = "test.foo_a"(%1) : (i1) -> (i1)
+          %1 = "test.foo_b"(%0) : (i1) -> (i1)
+        }
+        "test.foo_c"() : () -> ()
+      }): () -> ()
+    }) {worklist} : () -> ()
+    "test.another_op"() : () -> ()
+  }) {worklist} : () -> ()
+}
+
+// -----
+
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.dummy_op
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb2 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.foo
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb3 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.bar
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.bar
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.foo
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.dummy_op
+// CHECK-AN: notifyOperationRemoved: test.clone_region_in_parent
+// CHECK-AN-LABEL: func @test_clone_cyclic_blocks
+func.func @test_clone_cyclic_blocks() {
+  "test.dummy_op"() ({
+    ^bb0():
+    "test.clone_region_in_parent"() ({
+      %x = "test.dummy_op"() : () -> (i1)
+      cf.br ^bb1(%x: i1)
+      ^bb1(%arg0: i1):
+        "test.foo"(%x) : (i1) -> ()
+        cf.br ^bb2(%arg0: i1)
+      ^bb2(%arg1: i1):
+        "test.bar"(%x) : (i1) -> ()
+        cf.br ^bb1(%arg1: i1)
+      }) {worklist} : () -> ()
+      "test.qux"() : () -> ()
+    }) : () -> ()
+    "test.another_op"() : () -> ()
+  return
+}
+
+// -----
+
+// CHECK-AN: notifyBlockCreated: block ^bb3 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.nested_dummy
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.nested_dummy'
+// CHECK-AN: notifyOperationInserted: test.qux_unreachable
+// CHECK-AN: notifyBlockCreated: block ^bb0 from region 0 from operation 'test.nested_dummy'
+// CHECK-AN: notifyOperationInserted: test.qux_reachable
+// CHECK-AN: notifyOperationInserted: test.bar
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb2 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.foo
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.dummy_op
+// CHECK-AN: notifyOperationRemoved: test.dummy_op
+// CHECK-AN: notifyOperationRemoved: test.foo
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.bar
+// CHECK-AN: notifyOperationRemoved: test.qux_reachable
+// CHECK-AN: notifyOperationRemoved: test.qux_unreachable
+// CHECK-AN: notifyOperationRemoved: test.nested_dummy
+// CHECK-AN: notifyOperationRemoved: test.clone_region_in_parent
+// CHECK-AN-LABEL: func @test_clone_dead_blocks
+func.func @test_clone_dead_blocks() {
+  "test.dummy_op"() ({
+    ^bb0():
+    "test.clone_region_in_parent"() ({
+      "test.dummy_op"() : () -> (i1)
+      // The following blocks are not reachable. Still, ^bb2 should be notified
+      // before ^bb1.
+      ^bb1(%arg0: i1):
+        "test.foo"() : () -> ()
+      ^bb2(%arg1: i1):
+        "test.nested_dummy"() ({
+          "test.qux_reachable"() : () -> ()
+        // The following block is unreachable.
+        ^bb3:
+          "test.qux_unreachable"() : () -> ()
+        }) : () -> ()
+        "test.bar"() : () -> ()
+        cf.br ^bb1(%arg0: i1)
+      }) {worklist} : () -> ()
+      "test.qux"() : () -> ()
     }) : () -> ()
+    "test.another_op"() : () -> ()
   return
 }
+
+// -----
+
+// CHECK-AN: notifyBlockCreated: block ^bb1 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb5 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: cf.cond_br
+// CHECK-AN: notifyBlockCreated: block ^bb4 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.bar
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb3 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.foo
+// CHECK-AN: notifyOperationInserted: cf.br
+// CHECK-AN: notifyBlockCreated: block ^bb2 from region 0 from operation 'test.dummy_op'
+// CHECK-AN: notifyOperationInserted: test.qux
+// CHECK-AN: notifyOperationRemoved: test.qux
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.foo
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.bar
+// CHECK-AN: notifyOperationRemoved: cf.cond_br
+// CHECK-AN: notifyOperationRemoved: cf.br
+// CHECK-AN: notifyOperationRemoved: test.clone_region_in_parent
+// CHECK-AN-LABEL: func @test_clone_reverse_diamond
+func.func @test_clone_reverse_diamond(%c: i1) {
+  "test.dummy_op"() ({
+    "test.clone_region_in_parent"() ({
+      cf.br ^bb3
+    ^bb0:
+      "test.qux"() : () -> ()
+    ^bb1:
+      "test.foo"() : () -> ()
+      cf.br ^bb0
+    ^bb2:
+      "test.bar"() : () -> ()
+      cf.br ^bb0
+    ^bb3:
+      cf.cond_br %c, ^bb1, ^bb2
+    }) {worklist} : () -> ()
+    "test.another_op"() : () -> ()
+  }) {worklist} : () -> ()
+}

mlir/test/lib/Dialect/Test/TestPatterns.cpp

Option<bool> useTopDownTraversal{
       llvm::cl::desc("Seed the worklist in general top-down order"),
       llvm::cl::init(GreedyRewriteConfig().useTopDownTraversal)};
   Option<int> maxIterations{
       *this, "max-iterations",
       llvm::cl::desc("Max. iterations in the GreedyRewriteConfig"),
       llvm::cl::init(GreedyRewriteConfig().maxIterations)};
 };
 
+static void printRegion(Region *region) {
+  llvm::outs() << "region " << region->getRegionNumber() << " from operation '"
+               << region->getParentOp()->getName() << "'";
+}
+
+static void printBlock(Block *block) {
+  llvm::outs() << "block ";
+  block->printAsOperand(llvm::outs(), /*printType=*/false);
+  llvm::outs() << " from ";
+  printRegion(block->getParent());
+}
+
 struct DumpNotifications : public RewriterBase::Listener {
+  void notifyOperationInserted(Operation *op) override {
+    llvm::outs() << "notifyOperationInserted: " << op->getName() << "\n";
+  }
+  void notifyBlockCreated(Block *b) override {
+    llvm::outs() << "notifyBlockCreated: ";
+    printBlock(b);
+    llvm::outs() << "\n";
+  }
   void notifyOperationRemoved(Operation *op) override {
     llvm::outs() << "notifyOperationRemoved: " << op->getName() << "\n";
   }
 };
 
 struct TestStrictPatternDriver
     : public PassWrapper<TestStrictPatternDriver, OperationPass<func::FuncOp>> {
 public:
void runOnOperation() override {
     MLIRContext *ctx = &getContext();
     mlir::RewritePatternSet patterns(ctx);
     patterns.add<
         // clang-format off
         InsertSameOp,
         ReplaceWithNewOp,
         EraseOp,
         ChangeBlockOp,
+        CloneRegionInParentOp,
         ImplicitChangeOp
         // clang-format on
         >(ctx);
     SmallVector<Operation *> ops;
     getOperation()->walk([&](Operation *op) {
-      StringRef opName = op->getName().getStringRef();
-      if (opName == "test.insert_same_op" || opName == "test.change_block_op" ||
-          opName == "test.replace_with_new_op" || opName == "test.erase_op") {
+      if (op->hasAttr("worklist")) {
+        op->removeAttr("worklist");
         ops.push_back(op);
       }
     });
 
     DumpNotifications dumpNotifications;
     GreedyRewriteConfig config;
     config.listener = &dumpNotifications;
     if (strictMode == "AnyOp") {
public:
   }
 
   Option<std::string> strictMode{
       *this, "strictness",
       llvm::cl::desc("Can be {AnyOp, ExistingAndNewOps, ExistingOps}"),
       llvm::cl::init("AnyOp")};
 
 private:
+  // Clone region into parent op.
+  class CloneRegionInParentOp : public RewritePattern {
+  public:
+    CloneRegionInParentOp(MLIRContext *context)
+        : RewritePattern("test.clone_region_in_parent", /*benefit=*/1,
+                         context) {}
+
+    LogicalResult matchAndRewrite(Operation *op,
+                                  PatternRewriter &rewriter) const override {
+      auto &parentRegion = *op->getParentRegion();
+      auto &opRegion = op->getRegion(0);
+      rewriter.cloneRegionBefore(opRegion, parentRegion, parentRegion.end());
+      rewriter.eraseOp(op);
+      return success();
+    }
+  };
+
   // New inserted operation is valid for further transformation.
   class InsertSameOp : public RewritePattern {
   public:
     InsertSameOp(MLIRContext *context)
         : RewritePattern("test.insert_same_op", /*benefit=*/1, context) {}
 
     LogicalResult matchAndRewrite(Operation *op,
                                   PatternRewriter &rewriter) const override {