[mlir] Introduce CloneOp and adapt test cases in BufferDeallocation.

[dfki-jugr]

Summary

Add a new clone operation to the memref dialect. This operation implicitly
copies data from a source buffer to a new buffer. In contrast to the linalg.copy
operation, this operation does not accept a target buffer as an argument.
Instead, this operation performs a conceptual allocation which does not need to
be performed manually.

Furthermore, this operation resolves the dependency from the linalg-dialect
in the BufferDeallocation pass. In addition, we also extended the canonicalization
patterns to fold clone operations. This is a competitive alternative to the
copy removal pass which is more expensive.

[herhut]

Nice!

mlir/docs/BufferDeallocationInternals.md

312

Nit, should we keep the comment that explains the reason for the clone?

696

Is this pass still needed? The copy removal as described here relies on the fact that source and destination of the copy are not mutated after the copy operation. While this is true for memref.clone, it is not true for copy operations. So to do this kind of optimization, one would need to analyse the program first.

As the bufferization pass no longer introduces copy operations, maybe we should rather drop the incomplete pass for now.

816

This is no longer true.

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td

351

Can you add a remark that mutating the source and result of clone after the clone operation has executed has undefined behavior? This is a requirement to making the bufferization logic work.

And while at it, could you also add a similar comment to tensor_load (the source may not be mutated afterwards, at least when used in the context of bufferization) and memref.buffer_cast (the result may not be mutated).

As we are restricting the existing tensor_load here, maybe it would be better to have a new operation with the restricted semantics but that is outside of the scope of this diff.

mlir/include/mlir/Dialect/MemRef/Utils/MemRefUtils.h

25

With the guarantee that the cloned buffer cannot be mutated, is this actually required?

29

This only finds one dealloc. For its use, would it not be OK to find the dealloc in the current block (can only be one).

mlir/lib/Dialect/MemRef/Utils/MemRefUtils.cpp

21

should this be &&?

mlir/lib/Transforms/BufferDeallocation.cpp

405

Is this still true?

mlir/test/Transforms/canonicalize.mlir

1122

Why does this remain?

1184

It is not clear to me what these tests are testing.

[dfki-jugr]

Addressed comments.

mlir/lib/Transforms/BufferDeallocation.cpp

405

Yes,
it can still happens that there are clones of clones.

mlir/test/Transforms/canonicalize.mlir

1122

%3 results from the scf.if. The canonicalization pattern only checks, if %3 is an alloc operation.
Since this is not the case, this clone remains.

[herhut]

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td

359

nit: source or result.

1151

nit: source source

mlir/include/mlir/Dialect/MemRef/Utils/MemRefUtils.h

26

These are only used for the canonicalization pattern, so I'd prefer to make them local.

mlir/test/Transforms/canonicalize.mlir

1122

Now that the operand to clone is required to not be mutated, why do we need to see the alloc? Is it not good enough if a clone has a following dealloc of the source, if the clone itself does not have an earlier dealloc?

We can land it like it is (which is quite restricted) but this should be revisited again to make it apply more broadly.

[dfki-jugr]

Addressed comments.

mlir/include/mlir/Dialect/MemRef/Utils/MemRefUtils.h

26

findDealloc is also used in BufferDeallocation.

[pifon2a]

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td

356

nit: arg 1 -> arg1

[bondhugula]

@dfki-jugr But why does this revision remove the copy removal pass when there are things that generate copies? The extension to canonicalization done eliminates clone ops, but IR with copy ops will no longer have a way to remove copies? For eg. -linalg-bufferize would still generate copy operations, right? @silvas

[herhut]

In D99172#2670712, @bondhugula wrote:

@dfki-jugr But why does this revision remove the copy removal pass when there are things that generate copies? The extension to canonicalization done eliminates clone ops, but IR with copy ops will no longer have a way to remove copies? For eg. -linalg-bufferize would still generate copy operations, right? @silvas

I asked for it to be removed, as I was unaware of where it got used. I assumed it was only used for copies created by the bufferization pass itself. The copy removal pass was created for bufferization and only works if all assumptions that bufferization makes about copies hold. We had reports where this was not the case. So instead of keeping the broken one, I thought it would be better to remove it for now and implement a proper one.

[silvas]

In D99172#2670712, @bondhugula wrote:

@dfki-jugr But why does this revision remove the copy removal pass when there are things that generate copies? The extension to canonicalization done eliminates clone ops, but IR with copy ops will no longer have a way to remove copies? For eg. -linalg-bufferize would still generate copy operations, right? @silvas

I believe all uses of copy in linalg-bufferize can be replaced with memref.clone easily -- it's a much more natural representation and we should do that cleanup.

[bondhugula]

In D99172#2672229, @silvas wrote:

In D99172#2670712, @bondhugula wrote:

@dfki-jugr But why does this revision remove the copy removal pass when there are things that generate copies? The extension to canonicalization done eliminates clone ops, but IR with copy ops will no longer have a way to remove copies? For eg. -linalg-bufferize would still generate copy operations, right? @silvas

I believe all uses of copy in linalg-bufferize can be replaced with memref.clone easily -- it's a much more natural representation and we should do that cleanup.

Yes, but I wish -copy-removal was removed *after* this cleanup was done --- since there are now common copy patterns for which there is no longer anything in the infrastructure to eliminate/optimize.

[silvas]

In D99172#2674514, @bondhugula wrote:

In D99172#2672229, @silvas wrote:

In D99172#2670712, @bondhugula wrote:

@dfki-jugr But why does this revision remove the copy removal pass when there are things that generate copies? The extension to canonicalization done eliminates clone ops, but IR with copy ops will no longer have a way to remove copies? For eg. -linalg-bufferize would still generate copy operations, right? @silvas

I believe all uses of copy in linalg-bufferize can be replaced with memref.clone easily -- it's a much more natural representation and we should do that cleanup.

Yes, but I wish -copy-removal was removed *after* this cleanup was done --- since there are now common copy patterns for which there is no longer anything in the infrastructure to eliminate/optimize.

If this patch is breaking you please revert it, by all means! If you concern is hypothetical though, I tend to trust that the patch authors did their homework on this to make sure it isn't an issue in practice (AFAIK they are well in tune with all users of this code).

[mehdi_amini]

I have concerns about this kind of restriction on an operation that is named so broadly: a "memref.clone" shouldn't impose anything about mutability!
Can you rename this into something really unambiguously tied to bufferization, like memref.__bufferize__clone or something like that please?

mlir/docs/BufferDeallocationInternals.md

func @condBranch(%arg0: i1, %arg1: memref<2xf32>) {
   %0 = memref.alloc() : memref<2xf32>
   cond_br %arg0, ^bb1, ^bb2
 ^bb1:
   br ^bb3()
 ^bb2:
   partial_write(%0, %0)
   br ^bb3()
 ^bb3():
-  "linalg.copy"(%0, %arg1) : (memref<2xf32>, memref<2xf32>) -> ()
+  test.copy(%0, %arg1) : (memref<2xf32>, memref<2xf32>) -> ()
   return
 }
 ```
 
 The maintenance of the SSA like properties is only needed in the bufferization
 process. Afterwards, for example in optimization processes, the property is no
 longer needed.
 

 ![branch_example_pre_move](/includes/img/branch_example_pre_move.svg)
 
 ```mlir
 func @condBranch(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) {
   cond_br %arg0, ^bb1, ^bb2
 ^bb1:
   br ^bb3(%arg1 : memref<2xf32>)
 ^bb2:
-  %0 = alloc() : memref<2xf32>  // aliases: %1
+  %0 = memref.alloc() : memref<2xf32>  // aliases: %1
   use(%0)
   br ^bb3(%0 : memref<2xf32>)
 ^bb3(%1: memref<2xf32>):  // %1 could be %0 or %arg1
-  "linalg.copy"(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> ()
+  test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> ()
   return
 }
 ```
 
 Applying the BufferHoisting pass on this program results in the following piece
 of code:
 
 ![branch_example_post_move](/includes/img/branch_example_post_move.svg)
 
 ```mlir
 func @condBranch(%arg0: i1, %arg1: memref<2xf32>, %arg2: memref<2xf32>) {
-  %0 = alloc() : memref<2xf32>  // moved to bb0
+  %0 = memref.alloc() : memref<2xf32>  // moved to bb0
   cond_br %arg0, ^bb1, ^bb2
 ^bb1:
   br ^bb3(%arg1 : memref<2xf32>)
 ^bb2:
    use(%0)
    br ^bb3(%0 : memref<2xf32>)
 ^bb3(%1: memref<2xf32>):
-  "linalg.copy"(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> ()
+  test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>) -> ()
   return
 }
 ```
 
 The alloc is moved from bb2 to the beginning and it is passed as an argument to
 bb3.
 
 The following example demonstrates an allocation using dynamically shaped
 types. Due to the data dependency of the allocation to %0, we cannot move the
 allocation out of bb2 in this case:
 
 ```mlir
 func @condBranchDynamicType(
   %arg0: i1,
   %arg1: memref<?xf32>,
   %arg2: memref<?xf32>,
   %arg3: index) {
   cond_br %arg0, ^bb1, ^bb2(%arg3: index)
 ^bb1:
   br ^bb3(%arg1 : memref<?xf32>)
 ^bb2(%0: index):
-  %1 = alloc(%0) : memref<?xf32>   // cannot be moved upwards to the data
+  %1 = memref.alloc(%0) : memref<?xf32>   // cannot be moved upwards to the data
                                    // dependency to %0
   use(%1)
   br ^bb3(%1 : memref<?xf32>)
 ^bb3(%2: memref<?xf32>):
-  "linalg.copy"(%2, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
+  test.copy(%2, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
   return
 }
 ```
 
-## Introduction of Copies
+## Introduction of Clones
 
 In order to guarantee that all allocated buffers are freed properly, we have to
 pay attention to the control flow and all potential aliases a buffer allocation
 can have. Since not all allocations can be safely freed with respect to their
 aliases (see the following code snippet), it is often required to introduce
 copies to eliminate them. Consider the following example in which the
 allocations have already been placed:
 
 ```mlir
 func @branch(%arg0: i1) {
-  %0 = alloc() : memref<2xf32>  // aliases: %2
+  %0 = memref.alloc() : memref<2xf32>  // aliases: %2
   cond_br %arg0, ^bb1, ^bb2
 ^bb1:
-  %1 = alloc() : memref<2xf32>  // resides here for demonstration purposes
+  %1 = memref.alloc() : memref<2xf32>  // resides here for demonstration purposes
                                 // aliases: %2
   br ^bb3(%1 : memref<2xf32>)
 ^bb2:
   use(%0)
   br ^bb3(%0 : memref<2xf32>)
 ^bb3(%2: memref<2xf32>):
   …
   return

 allocations can be safely freed in their associated post-dominator blocks.
 Instead, we have to pay attention to all of their aliases.
 
 Applying the BufferDeallocation pass to the program above yields the following
 result:
 
 ```mlir
 func @branch(%arg0: i1) {
-  %0 = alloc() : memref<2xf32>
+  %0 = memref.alloc() : memref<2xf32>
   cond_br %arg0, ^bb1, ^bb2
 ^bb1:
-  %1 = alloc() : memref<2xf32>
-  %3 = alloc() : memref<2xf32>  // temp copy for %1
-  "linalg.copy"(%1, %3) : (memref<2xf32>, memref<2xf32>) -> ()
-  dealloc %1 : memref<2xf32> // %1 can be safely freed here
+  %1 = memref.alloc() : memref<2xf32>
+  %3 = memref.clone %1 : (memref<2xf32>) -> (memref<2xf32>)
+  memref.dealloc %1 : memref<2xf32> // %1 can be safely freed here
   br ^bb3(%3 : memref<2xf32>)
 ^bb2:
   use(%0)
-  %4 = alloc() : memref<2xf32>  // temp copy for %0
-  "linalg.copy"(%0, %4) : (memref<2xf32>, memref<2xf32>) -> ()
+  %4 = memref.clone %0 : (memref<2xf32>) -> (memref<2xf32>)
   br ^bb3(%4 : memref<2xf32>)
 ^bb3(%2: memref<2xf32>):
   …
-  dealloc %2 : memref<2xf32> // free temp buffer %2
-  dealloc %0 : memref<2xf32> // %0 can be safely freed here
+  memref.dealloc %2 : memref<2xf32> // free temp buffer %2
+  memref.dealloc %0 : memref<2xf32> // %0 can be safely freed here
   return
 }
 ```
 
 Note that a temporary buffer for %2 was introduced to free all allocations
 properly. Note further that the unnecessary allocation of %3 can be easily
-removed using one of the post-pass transformations.
-
-Reconsider the previously introduced sample demonstrating dynamically shaped
-types:
+removed using one of the post-pass transformations or the canonicalization
+pass.
 
-```mlir
-func @condBranchDynamicType(
-  %arg0: i1,
-  %arg1: memref<?xf32>,
-  %arg2: memref<?xf32>,
-  %arg3: index) {
-  cond_br %arg0, ^bb1, ^bb2(%arg3: index)
-^bb1:
-  br ^bb3(%arg1 : memref<?xf32>)
-^bb2(%0: index):
-  %1 = alloc(%0) : memref<?xf32>  // aliases: %2
-  use(%1)
-  br ^bb3(%1 : memref<?xf32>)
-^bb3(%2: memref<?xf32>):
-  "linalg.copy"(%2, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
-  return
-}
-```
-
-In the presence of DSTs, we have to parameterize the allocations with
-additional dimension information of the source buffers, we want to copy from.
-BufferDeallocation automatically introduces all required operations to extract
-dimension specifications and wires them with the associated allocations:
-
-```mlir
-func @condBranchDynamicType(
-  %arg0: i1,
-  %arg1: memref<?xf32>,
-  %arg2: memref<?xf32>,
-  %arg3: index) {
-  cond_br %arg0, ^bb1, ^bb2(%arg3 : index)
-^bb1:
-  %c0 = constant 0 : index
-  %0 = dim %arg1, %c0 : memref<?xf32>   // dimension operation to parameterize
-                                        // the following temp allocation
-  %1 = alloc(%0) : memref<?xf32>
-  "linalg.copy"(%arg1, %1) : (memref<?xf32>, memref<?xf32>) -> ()
-  br ^bb3(%1 : memref<?xf32>)
-^bb2(%2: index):
-  %3 = alloc(%2) : memref<?xf32>
-  use(%3)
-  %c0_0 = constant 0 : index
-  %4 = dim %3, %c0_0 : memref<?xf32>  // dimension operation to parameterize
-                                      // the following temp allocation
-  %5 = alloc(%4) : memref<?xf32>
-  "linalg.copy"(%3, %5) : (memref<?xf32>, memref<?xf32>) -> ()
-  dealloc %3 : memref<?xf32>  // %3 can be safely freed here
-  br ^bb3(%5 : memref<?xf32>)
-^bb3(%6: memref<?xf32>):
-  "linalg.copy"(%6, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
-  dealloc %6 : memref<?xf32>  // %6 can be safely freed here
-  return
-}
-```
+The presented example also works with dynamically shaped types.
 
 BufferDeallocation performs a fix-point iteration taking all aliases of all
 tracked allocations into account. We initialize the general iteration process
 using all tracked allocations and their associated aliases. As soon as we
 encounter an alias that is not properly dominated by our allocation, we mark
 this alias as _critical_ (needs to be freed and tracked by the internal
 fix-point iteration). The following sample demonstrates the presence of
 critical and non-critical aliases:
 
 ![nested_branch_example_pre_move](/includes/img/nested_branch_example_pre_move.svg)
 
 ```mlir
 func @condBranchDynamicTypeNested(
   %arg0: i1,
   %arg1: memref<?xf32>,  // aliases: %3, %4
   %arg2: memref<?xf32>,
   %arg3: index) {
   cond_br %arg0, ^bb1, ^bb2(%arg3: index)
 ^bb1:
   br ^bb6(%arg1 : memref<?xf32>)
 ^bb2(%0: index):
-  %1 = alloc(%0) : memref<?xf32>   // cannot be moved upwards due to the data
+  %1 = memref.alloc(%0) : memref<?xf32>   // cannot be moved upwards due to the data
                                    // dependency to %0
                                    // aliases: %2, %3, %4
   use(%1)
   cond_br %arg0, ^bb3, ^bb4
 ^bb3:
   br ^bb5(%1 : memref<?xf32>)
 ^bb4:
   br ^bb5(%1 : memref<?xf32>)
 ^bb5(%2: memref<?xf32>):  // non-crit. alias of %1, since %1 dominates %2
   br ^bb6(%2 : memref<?xf32>)
 ^bb6(%3: memref<?xf32>):  // crit. alias of %arg1 and %2 (in other words %1)
   br ^bb7(%3 : memref<?xf32>)
 ^bb7(%4: memref<?xf32>):  // non-crit. alias of %3, since %3 dominates %4
-  "linalg.copy"(%4, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
+  test.copy(%4, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
   return
 }
 ```
 
 Applying BufferDeallocation yields the following output:
 
 ![nested_branch_example_post_move](/includes/img/nested_branch_example_post_move.svg)
 
 ```mlir
 func @condBranchDynamicTypeNested(
   %arg0: i1,
   %arg1: memref<?xf32>,
   %arg2: memref<?xf32>,
   %arg3: index) {
   cond_br %arg0, ^bb1, ^bb2(%arg3 : index)
 ^bb1:
-  %c0 = constant 0 : index
-  %d0 = dim %arg1, %c0 : memref<?xf32>
-  %5 = alloc(%d0) : memref<?xf32>  // temp buffer required due to alias %3
-  "linalg.copy"(%arg1, %5) : (memref<?xf32>, memref<?xf32>) -> ()
+  %5 = memref.clone %arg1 : (memref<?xf32>) -> (memref<?xf32>)
   br ^bb6(%5 : memref<?xf32>)
 ^bb2(%0: index):
-  %1 = alloc(%0) : memref<?xf32>
+  %1 = memref.alloc(%0) : memref<?xf32>
   use(%1)
   cond_br %arg0, ^bb3, ^bb4
 ^bb3:
   br ^bb5(%1 : memref<?xf32>)
 ^bb4:
   br ^bb5(%1 : memref<?xf32>)
 ^bb5(%2: memref<?xf32>):
-  %c0_0 = constant 0 : index
-  %d1 = dim %2, %c0_0 : memref<?xf32>
-  %6 = alloc(%d1) : memref<?xf32>  // temp buffer required due to alias %3
-  "linalg.copy"(%1, %6) : (memref<?xf32>, memref<?xf32>) -> ()
-  dealloc %1 : memref<?xf32>
+  %6 = memref.clone %1 : (memref<?xf32>) -> (memref<?xf32>)
+  memref.dealloc %1 : memref<?xf32>
   br ^bb6(%6 : memref<?xf32>)
 ^bb6(%3: memref<?xf32>):
   br ^bb7(%3 : memref<?xf32>)
 ^bb7(%4: memref<?xf32>):
-  "linalg.copy"(%4, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
-  dealloc %3 : memref<?xf32>  // free %3, since %4 is a non-crit. alias of %3
+  test.copy(%4, %arg2) : (memref<?xf32>, memref<?xf32>) -> ()
+  memref.dealloc %3 : memref<?xf32>  // free %3, since %4 is a non-crit. alias of %3
   return
 }
 ```
 
 Since %3 is a critical alias, BufferDeallocation introduces an additional
 temporary copy in all predecessor blocks. %3 has an additional (non-critical)
 alias %4 that extends the live range until the end of bb7. Therefore, we can
 free %3 after its last use, while taking all aliases into account. Note that %4
- does not need to be freed, since we did not introduce a copy for it.
 
 The actual introduction of buffer copies is done after the fix-point iteration
 has been terminated and all critical aliases have been detected. A critical
 alias can be either a block argument or another value that is returned by an
 operation. Copies for block arguments are handled by analyzing all predecessor
 blocks. This is primarily done by querying the `BranchOpInterface` of the
 associated branch terminators that can jump to the current block. Consider the
 following example which involves a simple branch and the critical block

 operation returns a result to the parent operation. This sample demonstrates
 the use of the `RegionBranchOpInterface` to determine predecessors in order to
 infer the high-level control flow:
 
 ```mlir
 func @inner_region_control_flow(
   %arg0 : index,
   %arg1 : index) -> memref<?x?xf32> {
-  %0 = alloc(%arg0, %arg0) : memref<?x?xf32>
+  %0 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
   %1 = custom.region_if %0 : memref<?x?xf32> -> (memref<?x?xf32>)
    then(%arg2 : memref<?x?xf32>) {  // aliases: %arg4, %1
     custom.region_if_yield %arg2 : memref<?x?xf32>
    } else(%arg3 : memref<?x?xf32>) {  // aliases: %arg4, %1
     custom.region_if_yield %arg3 : memref<?x?xf32>
    } join(%arg4 : memref<?x?xf32>) {  // aliases: %1
     custom.region_if_yield %arg4 : memref<?x?xf32>
    }
   return %1 : memref<?x?xf32>
 }
 ```
 
 ![region_branch_example_pre_move](/includes/img/region_branch_example_pre_move.svg)
 
 Non-block arguments (other values) can become aliases when they are returned by
 dialect-specific operations. BufferDeallocation supports this behavior via the
 `RegionBranchOpInterface`. Consider the following example that uses an “scf.if”
 operation to determine the value of %2 at runtime which creates an alias:
 
 ```mlir
 func @nested_region_control_flow(%arg0 : index, %arg1 : index) -> memref<?x?xf32> {
   %0 = cmpi "eq", %arg0, %arg1 : index
-  %1 = alloc(%arg0, %arg0) : memref<?x?xf32>
+  %1 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
   %2 = scf.if %0 -> (memref<?x?xf32>) {
     scf.yield %1 : memref<?x?xf32>   // %2 will be an alias of %1
   } else {
-    %3 = alloc(%arg0, %arg1) : memref<?x?xf32>  // nested allocation in a div.
+    %3 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>  // nested allocation in a div.
                                                 // branch
     use(%3)
     scf.yield %1 : memref<?x?xf32>   // %2 will be an alias of %1
   }
   return %2 : memref<?x?xf32>
 }
 ```
 
 In this example, a dealloc is inserted to release the buffer within the else
 block since it cannot be accessed by the remainder of the program. Accessing
 the `RegionBranchOpInterface`, allows us to infer that %2 is a non-critical
 alias of %1 which does not need to be tracked.
 
 ```mlir
 func @nested_region_control_flow(%arg0: index, %arg1: index) -> memref<?x?xf32> {
     %0 = cmpi "eq", %arg0, %arg1 : index
-    %1 = alloc(%arg0, %arg0) : memref<?x?xf32>
+    %1 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
     %2 = scf.if %0 -> (memref<?x?xf32>) {
       scf.yield %1 : memref<?x?xf32>
     } else {
-      %3 = alloc(%arg0, %arg1) : memref<?x?xf32>
+      %3 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
       use(%3)
-      dealloc %3 : memref<?x?xf32>  // %3 can be safely freed here
+      memref.dealloc %3 : memref<?x?xf32>  // %3 can be safely freed here
       scf.yield %1 : memref<?x?xf32>
     }
     return %2 : memref<?x?xf32>
 }
 ```
 
 Analogous to the previous case, we have to detect all terminator operations in
 all attached regions of “scf.if” that provides a value to its parent operation
 (in this sample via scf.yield). Querying the `RegionBranchOpInterface` allows
 us to determine the regions that “return” a result to their parent operation.
 Like before, we have to update all `ReturnLike` terminators as described above.
 Reconsider a slightly adapted version of the “custom.region_if” example from
 above that uses a nested allocation:
 
 ```mlir
 func @inner_region_control_flow_div(
   %arg0 : index,
   %arg1 : index) -> memref<?x?xf32> {
-  %0 = alloc(%arg0, %arg0) : memref<?x?xf32>
+  %0 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
   %1 = custom.region_if %0 : memref<?x?xf32> -> (memref<?x?xf32>)
    then(%arg2 : memref<?x?xf32>) {  // aliases: %arg4, %1
     custom.region_if_yield %arg2 : memref<?x?xf32>
    } else(%arg3 : memref<?x?xf32>) {
-    %2 = alloc(%arg0, %arg1) : memref<?x?xf32>  // aliases: %arg4, %1
+    %2 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>  // aliases: %arg4, %1
     custom.region_if_yield %2 : memref<?x?xf32>
    } join(%arg4 : memref<?x?xf32>) {  // aliases: %1
     custom.region_if_yield %arg4 : memref<?x?xf32>
    }
   return %1 : memref<?x?xf32>
 }
 ```
 
 Since the allocation %2 happens in a divergent branch and cannot be safely
 deallocated in a post-dominator, %arg4 will be considered a critical alias.
 Furthermore, %arg4 is returned to its parent operation and has an alias %1.
 This causes BufferDeallocation to introduce additional copies:
 
 ```mlir
 func @inner_region_control_flow_div(
   %arg0 : index,
   %arg1 : index) -> memref<?x?xf32> {
-  %0 = alloc(%arg0, %arg0) : memref<?x?xf32>
+  %0 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
   %1 = custom.region_if %0 : memref<?x?xf32> -> (memref<?x?xf32>)
    then(%arg2 : memref<?x?xf32>) {
-    %c0 = constant 0 : index  // determine dimension extents for temp allocation
-    %2 = dim %arg2, %c0 : memref<?x?xf32>
-    %c1 = constant 1 : index
-    %3 = dim %arg2, %c1 : memref<?x?xf32>
-    %4 = alloc(%2, %3) : memref<?x?xf32>  // temp buffer required due to critic.
-                                          // alias %arg4
-    linalg.copy(%arg2, %4) : memref<?x?xf32>, memref<?x?xf32>
+    %4 = memref.clone %arg2 : (memref<?x?xf32>) -> (memref<?x?xf32>)
     custom.region_if_yield %4 : memref<?x?xf32>
    } else(%arg3 : memref<?x?xf32>) {
-    %2 = alloc(%arg0, %arg1) : memref<?x?xf32>
-    %c0 = constant 0 : index  // determine dimension extents for temp allocation
-    %3 = dim %2, %c0 : memref<?x?xf32>
-    %c1 = constant 1 : index
-    %4 = dim %2, %c1 : memref<?x?xf32>
-    %5 = alloc(%3, %4) : memref<?x?xf32>  // temp buffer required due to critic.
-                                          // alias %arg4
-    linalg.copy(%2, %5) : memref<?x?xf32>, memref<?x?xf32>
-    dealloc %2 : memref<?x?xf32>
+    %2 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
+    %5 = memref.clone %2 : (memref<?x?xf32>) -> (memref<?x?xf32>)
+    memref.dealloc %2 : memref<?x?xf32>
     custom.region_if_yield %5 : memref<?x?xf32>
    } join(%arg4: memref<?x?xf32>) {
-    %c0 = constant 0 : index  // determine dimension extents for temp allocation
-    %2 = dim %arg4, %c0 : memref<?x?xf32>
-    %c1 = constant 1 : index
-    %3 = dim %arg4, %c1 : memref<?x?xf32>
-    %4 = alloc(%2, %3) : memref<?x?xf32>  // this allocation will be removed by
-                                          // applying the copy removal pass
-    linalg.copy(%arg4, %4) : memref<?x?xf32>, memref<?x?xf32>
-    dealloc %arg4 : memref<?x?xf32>
+    %4 = memref.clone %arg4 : (memref<?x?xf32>) -> (memref<?x?xf32>)
+    memref.dealloc %arg4 : memref<?x?xf32>
     custom.region_if_yield %4 : memref<?x?xf32>
    }
-  dealloc %0 : memref<?x?xf32>  // %0 can be safely freed here
+  memref.dealloc %0 : memref<?x?xf32>  // %0 can be safely freed here
   return %1 : memref<?x?xf32>
 }
 ```
 
 ## Placement of Deallocs
 
 After introducing allocs and copies, deallocs have to be placed to free
 allocated memory and avoid memory leaks. The deallocation needs to take place
func @loop_nested_if(
   %ub: index,
   %step: index,
   %buf: memref<2xf32>,
   %res: memref<2xf32>) {
   %0 = scf.for %i = %lb to %ub step %step
     iter_args(%iterBuf = %buf) -> memref<2xf32> {
     %1 = cmpi "eq", %i, %ub : index
     %2 = scf.if %1 -> (memref<2xf32>) {
-      %3 = alloc() : memref<2xf32>  // makes %2 a critical alias due to a
+      %3 = memref.alloc() : memref<2xf32>  // makes %2 a critical alias due to a
                                     // divergent allocation
       use(%3)
       scf.yield %3 : memref<2xf32>
     } else {
       scf.yield %iterBuf : memref<2xf32>
     }
     scf.yield %2 : memref<2xf32>
   }
-  "linalg.copy"(%0, %res) : (memref<2xf32>, memref<2xf32>) -> ()
+  test.copy(%0, %res) : (memref<2xf32>, memref<2xf32>) -> ()
   return
 }
 ```
 
 In this example, the _then_ branch of the nested “scf.if” operation returns a
 newly allocated buffer.
 
 Since this allocation happens in the scope of a divergent branch, %2 becomes a
 critical alias that needs to be handled. As before, we have to insert
 additional copies to eliminate this alias using copies of %3 and %iterBuf. This
 guarantees that %2 will be a newly allocated buffer that is returned in each
 iteration. However, “returning” %2 to its alias %iterBuf turns %iterBuf into a
 critical alias as well. In other words, we have to create a copy of %2 to pass
 it to %iterBuf. Since this jump represents a back edge, and %2 will always be a
 new buffer, we have to free the buffer from the previous iteration to avoid
 memory leaks:
 
 ```mlir
 func @loop_nested_if(
   %lb: index,
   %ub: index,
   %step: index,
   %buf: memref<2xf32>,
   %res: memref<2xf32>) {
-  %4 = alloc() : memref<2xf32>
-  "linalg.copy"(%buf, %4) : (memref<2xf32>, memref<2xf32>) -> ()
+  %4 = memref.clone %buf : (memref<2xf32>) -> (memref<2xf32>)
   %0 = scf.for %i = %lb to %ub step %step
     iter_args(%iterBuf = %4) -> memref<2xf32> {
     %1 = cmpi "eq", %i, %ub : index
     %2 = scf.if %1 -> (memref<2xf32>) {
-      %3 = alloc() : memref<2xf32> // makes %2 a critical alias
+      %3 = memref.alloc() : memref<2xf32> // makes %2 a critical alias
       use(%3)
-      %5 = alloc() : memref<2xf32> // temp copy due to crit. alias %2
-      "linalg.copy"(%3, %5) : memref<2xf32>, memref<2xf32>
-      dealloc %3 : memref<2xf32>
+      %5 = memref.clone %3 : (memref<2xf32>) -> (memref<2xf32>)
+      memref.dealloc %3 : memref<2xf32>
       scf.yield %5 : memref<2xf32>
     } else {
-      %6 = alloc() : memref<2xf32> // temp copy due to crit. alias %2
-      "linalg.copy"(%iterBuf, %6) : memref<2xf32>, memref<2xf32>
+      %6 = memref.clone %iterBuf : (memref<2xf32>) -> (memref<2xf32>)
       scf.yield %6 : memref<2xf32>
     }
-    %7 = alloc() : memref<2xf32> // temp copy due to crit. alias %iterBuf
-    "linalg.copy"(%2, %7) : memref<2xf32>, memref<2xf32>
-    dealloc %2 : memref<2xf32>
-    dealloc %iterBuf : memref<2xf32> // free backedge iteration variable
+    %7 = memref.clone %2 : (memref<2xf32>) -> (memref<2xf32>)
+    memref.dealloc %2 : memref<2xf32>
+    memref.dealloc %iterBuf : memref<2xf32> // free backedge iteration variable
     scf.yield %7 : memref<2xf32>
   }
-  "linalg.copy"(%0, %res) : (memref<2xf32>, memref<2xf32>) -> ()
-  dealloc %0 : memref<2xf32> // free temp copy %0
+  test.copy(%0, %res) : (memref<2xf32>, memref<2xf32>) -> ()
+  memref.dealloc %0 : memref<2xf32> // free temp copy %0
   return
 }
 ```
 
 Example for loop-like control flow. The CFG contains back edges that have to be
 handled to avoid memory leaks. The bufferization is able to free the backedge
 iteration variable %iterBuf.
 

 placed in front of this position. However, the most important analysis is the
 alias analysis that is needed to introduce copies and to place all
 deallocations.
 
 # Post Phase
 
 In order to limit the complexity of the BufferDeallocation transformation, some
 tiny code-polishing/optimization transformations are not applied on-the-fly
-during placement. Currently, there is only the CopyRemoval transformation to
-remove unnecessary copy and allocation operations.
+during placement. Currently, there is the CopyRemoval transformation to
+remove unnecessary copy and allocation operations. Furthermore, a
+canonicalization pattern is added to the clone operation to reduce the
+appearance of unnecessary clones.
 
 Note: further transformations might be added to the post-pass phase in the
 future.
 
+## Clone Canonicalization
+
+During placement of clones it may happen, that unnecessary clones are inserted.
+If these clones appear with their corresponding dealloc operation within the
+same block, we can use the canonicalizer to remove these unnecessary operations.
+Note, that this step needs to take place after the insertion of clones and
+deallocs in the buffer deallocation step. The canonicalization inludes both,
+the newly created target value from the clone operation and the source
+operation.
+
+## Canonicalization of the Source Buffer of the Clone Operation
+
+In this case, the source of the clone operation can be used instead of its
+target. The unused allocation and deallocation operations that are defined for
+this clone operation are also removed. Here is a working example generated by
+the BufferDeallocation pass that allocates a buffer with dynamic size. A deeper
+analysis of this sample reveals that the highlighted operations are redundant
+and can be removed.
+
+```mlir
+func @dynamic_allocation(%arg0: index, %arg1: index) -> memref<?x?xf32> {
+  %1 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
+  %2 = memref.clone %1 : (memref<?x?xf32>) -> (memref<?x?xf32>)
+  memref.dealloc %1 : memref<?x?xf32>
+  return %2 : memref<?x?xf32>
+}
+```
+
+Will be transformed to:
+
+```mlir
+func @dynamic_allocation(%arg0: index, %arg1: index) -> memref<?x?xf32> {
+  %1 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
+  return %1 : memref<?x?xf32>
+}
+```
+
+In this case, the additional copy %2 can be replaced with its original source
+buffer %1. This also applies to the associated dealloc operation of %1.
+
+## Canonicalization of the Target Buffer of the Clone Operation
+
+In this case, the target buffer of the clone operation can be used instead of
+its source. The unused deallocation operation that is defined for this clone
+operation is also removed.
+
+Consider the following example where a generic test operation writes the result
+to %temp and then copies %temp to %result. However, these two operations
+can be merged into a single step. Canonicalization removes the clone operation
+and %temp, and replaces the uses of %temp with %result:
+
+```mlir
+func @reuseTarget(%arg0: memref<2xf32>, %result: memref<2xf32>){
+  %temp = memref.alloc() : memref<2xf32>
+  test.generic {
+    args_in = 1 : i64,
+    args_out = 1 : i64,
+    indexing_maps = [#map0, #map0],
+    iterator_types = ["parallel"]} %arg0, %temp {
+  ^bb0(%gen2_arg0: f32, %gen2_arg1: f32):
+    %tmp2 = exp %gen2_arg0 : f32
+    test.yield %tmp2 : f32
+  }: memref<2xf32>, memref<2xf32>
+  %result = memref.clone %temp : (memref<2xf32>) -> (memref<2xf32>)
+  memref.dealloc %temp : memref<2xf32>
+  return
+}
+```
+
+Will be transformed to:
+
+```mlir
+func @reuseTarget(%arg0: memref<2xf32>, %result: memref<2xf32>){
+  test.generic {
+    args_in = 1 : i64,
+    args_out = 1 : i64,
+    indexing_maps = [#map0, #map0],
+    iterator_types = ["parallel"]} %arg0, %result {
+  ^bb0(%gen2_arg0: f32, %gen2_arg1: f32):
+    %tmp2 = exp %gen2_arg0 : f32
+    test.yield %tmp2 : f32
+  }: memref<2xf32>, memref<2xf32>
+  return
+}
+```
+
 ## CopyRemoval Pass
 
 A common pattern that arises during placement is the introduction of
 unnecessary temporary copies that are used instead of the original source
 buffer. For this reason, there is a post-pass transformation that removes these
 allocations and copies via `-copy-removal`. This pass, besides removing
 unnecessary copy operations, will also remove the dead allocations and their
 corresponding deallocation operations. The CopyRemoval pass can currently be
 applied to operations that implement the `CopyOpInterface` in any of these two

 Consider the following example where a generic linalg operation writes the
 result to %temp and then copies %temp to %result. However, these two operations
 can be merged into a single step. Copy removal removes the copy operation and
 %temp, and replaces the uses of %temp with %result:
 
 ```mlir
 func @reuseTarget(%arg0: memref<2xf32>, %result: memref<2xf32>){
   %temp = alloc() : memref<2xf32>
-  linalg.generic {
+  test.generic {
     args_in = 1 : i64,
     args_out = 1 : i64,
     indexing_maps = [#map0, #map0],
     iterator_types = ["parallel"]} %arg0, %temp {
   ^bb0(%gen2_arg0: f32, %gen2_arg1: f32):
     %tmp2 = exp %gen2_arg0 : f32
-    linalg.yield %tmp2 : f32
+    test.yield %tmp2 : f32
   }: memref<2xf32>, memref<2xf32>
-  "linalg.copy"(%temp, %result) : (memref<2xf32>, memref<2xf32>) -> ()
+  test.copy(%temp, %result) : (memref<2xf32>, memref<2xf32>) -> ()
   dealloc %temp : memref<2xf32>
   return
 }
 ```
 
 Will be transformed to:
 
 ```mlir
 func @reuseTarget(%arg0: memref<2xf32>, %result: memref<2xf32>){
-  linalg.generic {
+  test.generic {
     args_in = 1 : i64,
     args_out = 1 : i64,
     indexing_maps = [#map0, #map0],
     iterator_types = ["parallel"]} %arg0, %result {
   ^bb0(%gen2_arg0: f32, %gen2_arg1: f32):
     %tmp2 = exp %gen2_arg0 : f32
-    linalg.yield %tmp2 : f32
+    test.yield %tmp2 : f32
   }: memref<2xf32>, memref<2xf32>
   return
 }
 ```
 
 Like before, several constraints to use the transformation apply:
 
 * The copy operation, the defining operation of the source value, and the
 deallocation of the source value lie in the same block.
 * There are no users/aliases of the target value between the defining operation
 of the source value and the copy operation.
 * There are no users/aliases of the source value between the copy operation and
 the deallocation of the source value.
 
 ## Known Limitations
 
 BufferDeallocation introduces additional copies using allocations from the
 “memref” dialect (“memref.alloc”). Analogous, all deallocations use the
 “memref” dialect-free operation “memref.dealloc”. The actual copy process is
-realized using “linalg.copy”. Furthermore, buffers are essentially immutable
+realized using “test.copy”. Furthermore, buffers are essentially immutable
 after their creation in a block. Another limitations are known in the case
 using unstructered control flow.

mlir/include/mlir/Dialect/MemRef/IR/MemRef.h

 //===- MemRef.h - MemRef dialect --------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_DIALECT_MEMREF_IR_MEMREF_H_
 #define MLIR_DIALECT_MEMREF_IR_MEMREF_H_
 
 #include "mlir/IR/Dialect.h"
 #include "mlir/Interfaces/CallInterfaces.h"
 #include "mlir/Interfaces/CastInterfaces.h"
+#include "mlir/Interfaces/CopyOpInterface.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Interfaces/ViewLikeInterface.h"
 
 namespace mlir {
 
 class Location;
 class OpBuilder;
 

mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td

 //===- MemRefOps.td - MemRef op definitions ----------------*- tablegen -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MEMREF_OPS
 #define MEMREF_OPS
 
 include "mlir/Dialect/MemRef/IR/MemRefBase.td"
 include "mlir/Interfaces/CastInterfaces.td"
+include "mlir/Interfaces/CopyOpInterface.td"
 include "mlir/Interfaces/SideEffectInterfaces.td"
 include "mlir/Interfaces/ViewLikeInterface.td"
 include "mlir/IR/SymbolInterfaces.td"
 
 class MemRef_Op<string mnemonic, list<OpTrait> traits = []>
     : Op<MemRef_Dialect, mnemonic, traits> {
   let printer = [{ return ::print(p, *this); }];
   let verifier = [{ return ::verify(*this); }];
let extraClassDeclaration = [{
 
     Value getViewSource() { return source(); }
   }];
 
   let hasFolder = 1;
 }
 
 //===----------------------------------------------------------------------===//
+// CloneOp
+//===----------------------------------------------------------------------===//
+
+def CloneOp : MemRef_Op<"clone", [
+    CopyOpInterface,
+    DeclareOpInterfaceMethods<MemoryEffectsOpInterface>
+  ]> {
+  let builders = [
+    OpBuilder<(ins "Value":$value), [{
+      return build($_builder, $_state, value.getType(), value);
+    }]>];
+
+  let description = [{
+    Clones the data in the input view into an implicitly defined output view.
+
+    Usage:
+
+    ```mlir
+    %arg 1 = memref.clone %arg0 : memref<?xf32> to memref<?xf32>
+    ```
+  }];
+
+  let arguments = (ins Arg<AnyMemRef, "", []>:$input);
+  let results = (outs Arg<AnyMemRef, "", []>:$output);
+
+  let extraClassDeclaration = [{
+    Value getSource() { return input();}
+    Value getTarget() { return output(); }
+  }];
+
+  let assemblyFormat = "$input attr-dict `:` type($input) `to` type($output)";
+
+  let hasFolder = 1;
+  let hasCanonicalizer = 1;
+}
+
+//===----------------------------------------------------------------------===//
 // DeallocOp
 //===----------------------------------------------------------------------===//
 
 def MemRef_DeallocOp : MemRef_Op<"dealloc", [MemRefsNormalizable]> {
   let summary = "memory deallocation operation";
   let description = [{
     The `dealloc` operation frees the region of memory referenced by a memref
     which was originally created by the `alloc` operation.
let description = [{
 
     Example:
 
     ```mlir
     // Produces a value of tensor<4x?xf32> type.
     %12 = memref.tensor_load %10 : memref<4x?xf32, #layout, memspace0>
     ```
   }];
 
   let arguments = (ins Arg<AnyRankedOrUnrankedMemRef,
                        "the reference to load from", [MemRead]>:$memref);
   let results = (outs AnyTensor:$result);
   // TensorLoadOp is fully verified by traits.
   let verifier = ?;
 
   let builders = [
     OpBuilder<(ins "Value":$memref), [{

mlir/include/mlir/Dialect/MemRef/Utils/MemRefUtils.h

+//===- MemRefUtils.h - MemRef transformation utilities ----------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file defines prototypes for various transformation utilities for
+// the MemRefOps dialect. These are not passes by themselves but are used
+// either by passes, optimization sequences, or in turn by other transformation
+// utilities.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_DIALECT_MEMREFOPS_UTILS_MEMREFUTILS_H
+#define MLIR_DIALECT_MEMREFOPS_UTILS_MEMREFUTILS_H
+
+#include "mlir/Dialect/MemRef/IR/MemRef.h"
+
+namespace mlir {
+
+/// Returns true if `val` value has at least a user between `start` and
+/// `end` operations.
+bool hasUsersBetween(Value val, Operation *start, Operation *end);
+
+/// Finds associated deallocs that can be linked to our allocation nodes (if
+/// any).
+Operation *findDealloc(Value allocValue);
+
+/// Returns the allocation operation for `value` in `block` if it exists.
+/// nullptr otherwise.
+Operation *findAlloc(Value value, Block *block);
+
+} // end namespace mlir
+
+#endif // MLIR_DIALECT_MEMREFOPS_UTILS_MEMREFUTILS_H

mlir/include/mlir/Transforms/BufferUtils.h

public:
   /// Represents a list containing all alloc entries.
   using AllocEntryList = SmallVector<AllocEntry, 8>;
 
   /// Get the start operation to place the given alloc value within the
   /// specified placement block.
   static Operation *getStartOperation(Value allocValue, Block *placementBlock,
                                       const Liveness &liveness);
 
-  /// Find an associated dealloc operation that is linked to the given
-  /// allocation node (if any).
-  static Operation *findDealloc(Value allocValue);
-
 public:
   /// Initializes the internal list by discovering all supported allocation
   /// nodes.
   BufferPlacementAllocs(Operation *op);
 
   /// Returns the begin iterator to iterate over all allocations.
   AllocEntryList::const_iterator begin() const { return allocs.begin(); }
 

mlir/include/mlir/Transforms/Passes.td

module {
         return
       }
 
     }
     ```
 
   }];
   let constructor = "mlir::createBufferDeallocationPass()";
-  // TODO: this pass likely shouldn't depend on Linalg?
-  let dependentDialects = ["linalg::LinalgDialect"];
 }
 
 def BufferHoisting : FunctionPass<"buffer-hoisting"> {
   let summary = "Optimizes placement of allocation operations by moving them "
                 "into common dominators and out of nested regions";
   let description = [{
     This pass implements an approach to aggressively move allocations upwards
     into common dominators and out of nested regions.

mlir/lib/Dialect/MemRef/CMakeLists.txt

-add_subdirectory(IR)
+add_mlir_dialect_library(MLIRMemRef
+  IR/MemRefDialect.cpp
+  IR/MemRefOps.cpp
+  Utils/MemRefUtils.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${PROJECT_SOURCE_DIR}/inlude/mlir/Dialect/MemRefDialect
+
+  DEPENDS
+  MLIRStandardOpsIncGen
+  MLIRMemRefOpsIncGen
+
+  LINK_COMPONENTS
+  Core
+
+  LINK_LIBS PUBLIC
+  MLIRDialect
+  MLIRIR
+  MLIRStandard
+  MLIRTensor
+  MLIRViewLikeInterface
+)

mlir/lib/Dialect/MemRef/IR/CMakeLists.txt

-add_mlir_dialect_library(MLIRMemRef
-  MemRefDialect.cpp
-  MemRefOps.cpp
-
-  ADDITIONAL_HEADER_DIRS
-  ${PROJECT_SOURCE_DIR}/inlude/mlir/Dialect/MemRefDialect
-
-  DEPENDS
-  MLIRStandardOpsIncGen
-  MLIRMemRefOpsIncGen
-
-  LINK_COMPONENTS
-  Core
-
-  LINK_LIBS PUBLIC
-  MLIRDialect
-  MLIRIR
-  MLIRStandard
-  MLIRTensor
-  MLIRViewLikeInterface
-)

mlir/lib/Dialect/MemRef/IR/MemRefOps.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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/Dialect/MemRef/IR/MemRef.h"
+#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
 #include "mlir/Dialect/StandardOps/IR/Ops.h"
 #include "mlir/Dialect/StandardOps/Utils/Utils.h"
 #include "mlir/Dialect/Tensor/IR/Tensor.h"
 #include "mlir/IR/AffineMap.h"
 #include "mlir/IR/Builders.h"
 #include "mlir/IR/BuiltinTypes.h"
 #include "mlir/IR/Matchers.h"
 #include "mlir/IR/PatternMatch.h"
bool CastOp::areCastCompatible(TypeRange inputs, TypeRange outputs) {
   return false;
 }
 
 OpFoldResult CastOp::fold(ArrayRef<Attribute> operands) {
   return succeeded(foldMemRefCast(*this)) ? getResult() : Value();
 }
 
 //===----------------------------------------------------------------------===//
+// CloneOp
+//===----------------------------------------------------------------------===//
+
+static LogicalResult verify(CloneOp op) { return success(); }
+
+void CloneOp::getEffects(
+    SmallVectorImpl<SideEffects::EffectInstance<MemoryEffects::Effect>>
+        &effects) {
+  effects.emplace_back(MemoryEffects::Read::get(), input(),
+                       SideEffects::DefaultResource::get());
+  effects.emplace_back(MemoryEffects::Write::get(), output(),
+                       SideEffects::DefaultResource::get());
+}
+
+namespace {
+
+/// Fold Dealloc operations that are deallocating an AllocOp that is only used
+/// by other Dealloc operations.
+struct SimplifyClones : public OpRewritePattern<CloneOp> {
+  using OpRewritePattern<CloneOp>::OpRewritePattern;
+
+  LogicalResult matchAndRewrite(CloneOp cloneOp,
+                                PatternRewriter &rewriter) const override {
+    if (cloneOp.use_empty()) {
+      rewriter.eraseOp(cloneOp);
+      return success();
+    }
+
+    Value source = cloneOp.input();
+    Operation *clone = cloneOp.getOperation();
+    Operation *deallocOp = mlir::findDealloc(cloneOp.output());
+    Operation *sourceOp = source.getDefiningOp();
+    if (sourceOp && deallocOp &&
+        sourceOp->getBlock() == deallocOp->getBlock() &&
+        !mlir::hasUsersBetween(source, clone, deallocOp)) {
+      rewriter.replaceOp(cloneOp, source);
+      rewriter.eraseOp(deallocOp);
+      return success();
+    }
+
+    deallocOp = mlir::findDealloc(source);
+    Operation *allocOp = mlir::findAlloc(source, clone->getBlock());
+    if (sourceOp && deallocOp && allocOp &&
+        allocOp->getBlock() == deallocOp->getBlock() &&
+        !mlir::hasUsersBetween(source, allocOp, cloneOp) &&
+        !mlir::hasUsersBetween(source, cloneOp, deallocOp)) {
+      rewriter.replaceOp(cloneOp, source);
+      rewriter.eraseOp(deallocOp);
+      return success();
+    }
+    return failure();
+  }
+};
+
+} // end anonymous namespace.
+
+void CloneOp::getCanonicalizationPatterns(OwningRewritePatternList &results,
+                                          MLIRContext *context) {
+  results.insert<SimplifyClones>(context);
+}
+
+OpFoldResult CloneOp::fold(ArrayRef<Attribute> operands) {
+  return succeeded(foldMemRefCast(*this)) ? getResult() : Value();
+}
+
+//===----------------------------------------------------------------------===//
 // DeallocOp
 //===----------------------------------------------------------------------===//
 namespace {
 /// Fold Dealloc operations that are deallocating an AllocOp that is only used
 /// by other Dealloc operations.
 struct SimplifyDeadDealloc : public OpRewritePattern<DeallocOp> {
   using OpRewritePattern<DeallocOp>::OpRewritePattern;
 

mlir/lib/Dialect/MemRef/Utils/MemRefUtils.cpp

+//===- Utils.cpp - Utilities to support the MemRef dialect ----------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements utilities for the MemRef dialect.
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
+#include "mlir/Dialect/MemRef/IR/MemRef.h"
+
+using namespace mlir;
+
+/// Returns true if `val` value has at least a user between `start` and
+/// `end` operations.
+bool mlir::hasUsersBetween(Value val, Operation *start, Operation *end) {
+  assert((start || end) && "Start and end operations cannot be null");
+  Block *block = start->getBlock();
+  assert(block == end->getBlock() &&
+         "Start and end operations should be in the same block.");
+  return llvm::any_of(val.getUsers(), [&](Operation *op) {
+    return op->getBlock() == block && start->isBeforeInBlock(op) &&
+           op->isBeforeInBlock(end);
+  });
+};
+
+/// Finds associated deallocs that can be linked to our allocation nodes (if
+/// any).
+Operation *mlir::findDealloc(Value allocValue) {
+  auto userIt = llvm::find_if(allocValue.getUsers(), [&](Operation *user) {
+    auto effectInterface = dyn_cast<MemoryEffectOpInterface>(user);
+    if (!effectInterface)
+      return false;
+    // Try to find a free effect that is applied to one of our values
+    // that will be automatically freed by our pass.
+    SmallVector<MemoryEffects::EffectInstance, 2> effects;
+    effectInterface.getEffectsOnValue(allocValue, effects);
+    return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &it) {
+      return isa<MemoryEffects::Free>(it.getEffect());
+    });
+  });
+  // Assign the associated dealloc operation (if any).
+  return userIt != allocValue.user_end() ? *userIt : nullptr;
+}
+
+/// Returns the allocation operation for `value` in `block` if it exists.
+/// nullptr otherwise.
+Operation *mlir::findAlloc(Value value, Block *block) {
+  Operation *op = value.getDefiningOp();
+  if (op && op->getBlock() == block) {
+    auto effects = dyn_cast<MemoryEffectOpInterface>(op);
+    if (effects && effects.hasEffect<MemoryEffects::Allocate>())
+      return op;
+  }
+  return nullptr;
+}

mlir/lib/Transforms/BufferDeallocation.cpp

 //===- BufferDeallocation.cpp - the impl for buffer deallocation ----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements logic for computing correct alloc and dealloc positions.
-// Furthermore, buffer placement also adds required new alloc and copy
-// operations to ensure that all buffers are deallocated. The main class is the
+// Furthermore, buffer deallocation also adds required new clone operations to
+// ensure that all buffers are deallocated. The main class is the
 // BufferDeallocationPass class that implements the underlying algorithm. In
 // order to put allocations and deallocations at safe positions, it is
 // significantly important to put them into the correct blocks. However, the
 // liveness analysis does not pay attention to aliases, which can occur due to
 // branches (and their associated block arguments) in general. For this purpose,
 // BufferDeallocation firstly finds all possible aliases for a single value
-// (using the BufferAliasAnalysis class). Consider the following
-// example:
+// (using the BufferAliasAnalysis class). Consider the following example:
 //
 // ^bb0(%arg0):
 //   cond_br %cond, ^bb1, ^bb2
 // ^bb1:
 //   br ^exit(%arg0)
 // ^bb2:
 //   %new_value = ...
 //   br ^exit(%new_value)
 // ^exit(%arg1):
 //   return %arg1;
 //
 // We should place the dealloc for %new_value in exit. However, we have to free
 // the buffer in the same block, because it cannot be freed in the post
-// dominator. However, this requires a new copy buffer for %arg1 that will
+// dominator. However, this requires a new clone buffer for %arg1 that will
 // contain the actual contents. Using the class BufferAliasAnalysis, we
 // will find out that %new_value has a potential alias %arg1. In order to find
 // the dealloc position we have to find all potential aliases, iterate over
 // their uses and find the common post-dominator block (note that additional
-// copies and buffers remove potential aliases and will influence the placement
+// clones and buffers remove potential aliases and will influence the placement
 // of the deallocs). In all cases, the computed block can be safely used to free
 // the %new_value buffer (may be exit or bb2) as it will die and we can use
 // liveness information to determine the exact operation after which we have to
-// insert the dealloc. However, the algorithm supports introducing copy buffers
+// insert the dealloc. However, the algorithm supports introducing clone buffers
 // and placing deallocs in safe locations to ensure that all buffers will be
 // freed in the end.
 //
 // TODO:
 // The current implementation does not support explicit-control-flow loops and
 // the resulting code will be invalid with respect to program semantics.
 // However, structured control-flow loops are fully supported. Furthermore, it
 // doesn't accept functions which return buffers already.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PassDetail.h"
-#include "mlir/Dialect/Linalg/IR/LinalgOps.h"
 #include "mlir/Dialect/MemRef/IR/MemRef.h"
 #include "mlir/Dialect/StandardOps/IR/Ops.h"
-#include "mlir/Dialect/StandardOps/Utils/Utils.h"
 #include "mlir/IR/Operation.h"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/LoopLikeInterface.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Transforms/BufferUtils.h"
 #include "mlir/Transforms/Passes.h"
 #include "llvm/ADT/SetOperations.h"
 

 };
 
 //===----------------------------------------------------------------------===//
 // BufferDeallocation
 //===----------------------------------------------------------------------===//
 
 /// The buffer deallocation transformation which ensures that all allocs in the
 /// program have a corresponding de-allocation. As a side-effect, it might also
-/// introduce copies that in turn leads to additional allocs and de-allocations.
+/// introduce clones that in turn leads to additional deallocations.
 class BufferDeallocation : BufferPlacementTransformationBase {
 public:
   BufferDeallocation(Operation *op)
       : BufferPlacementTransformationBase(op), dominators(op),
         postDominators(op) {}
 
-  /// Performs the actual placement/creation of all temporary alloc, copy and
-  /// dealloc nodes.
+  /// Performs the actual placement/creation of all temporary clone and dealloc
+  /// nodes.
   void deallocate() {
-    // Add additional allocations and copies that are required.
-    introduceCopies();
+    // Add additional clones that are required.
+    introduceClones();
     // Place deallocations for all allocation entries.
     placeDeallocs();
   }
 
 private:
-  /// Introduces required allocs and copy operations to avoid memory leaks.
-  void introduceCopies() {
+  /// Introduces required clone operations to avoid memory leaks.
+  void introduceClones() {
     // Initialize the set of values that require a dedicated memory free
     // operation since their operands cannot be safely deallocated in a post
     // dominator.
     SmallPtrSet<Value, 8> valuesToFree;
     llvm::SmallDenseSet<std::tuple<Value, Block *>> visitedValues;
     SmallVector<std::tuple<Value, Block *>, 8> toProcess;
 
     // Check dominance relation for proper dominance properties. If the given
-    // value node does not dominate an alias, we will have to create a copy in
+    // value node does not dominate an alias, we will have to create a clone in
     // order to free all buffers that can potentially leak into a post
     // dominator.
     auto findUnsafeValues = [&](Value source, Block *definingBlock) {
       auto it = aliases.find(source);
       if (it == aliases.end())
         return;
       for (Value value : it->second) {
         if (valuesToFree.count(value) > 0)
while (!toProcess.empty()) {
       auto current = toProcess.pop_back_val();
       findUnsafeValues(std::get<0>(current), std::get<1>(current));
     }
 
     // Update buffer aliases to ensure that we free all buffers and block
     // arguments at the correct locations.
     aliases.remove(valuesToFree);
 
-    // Add new allocs and additional copy operations.
+    // Add new allocs and additional clone operations.
     for (Value value : valuesToFree) {
       if (auto blockArg = value.dyn_cast<BlockArgument>())
         introduceBlockArgCopy(blockArg);
       else
         introduceValueCopyForRegionResult(value);
 
       // Register the value to require a final dealloc. Note that we do not have
       // to assign a block here since we do not want to move the allocation node
       // to another location.
       allocs.registerAlloc(std::make_tuple(value, nullptr));
     }
   }
 
-  /// Introduces temporary allocs in all predecessors and copies the source
+  /// Introduces temporary clones in all predecessors and copies the source
   /// values into the newly allocated buffers.
   void introduceBlockArgCopy(BlockArgument blockArg) {
     // Allocate a buffer for the current block argument in the block of
     // the associated value (which will be a predecessor block by
     // definition).
     Block *block = blockArg.getOwner();
     for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
       // Get the terminator and the value that will be passed to our
       // argument.
       Operation *terminator = (*it)->getTerminator();
       auto branchInterface = cast<BranchOpInterface>(terminator);
       // Query the associated source value.
       Value sourceValue =
           branchInterface.getSuccessorOperands(it.getSuccessorIndex())
               .getValue()[blockArg.getArgNumber()];
-      // Create a new alloc and copy at the current location of the terminator.
-      Value alloc = introduceBufferCopy(sourceValue, terminator);
-      // Wire new alloc and successor operand.
+      // Create a new clone at the current location of the terminator.
+      Value clone = introduceCloneBuffers(sourceValue, terminator);
+      // Wire new clone and successor operand.
       auto mutableOperands =
           branchInterface.getMutableSuccessorOperands(it.getSuccessorIndex());
       if (!mutableOperands.hasValue())
         terminator->emitError() << "terminators with immutable successor "
                                    "operands are not supported";
       else
         mutableOperands.getValue()
             .slice(blockArg.getArgNumber(), 1)
-            .assign(alloc);
+            .assign(clone);
     }
 
     // Check whether the block argument has implicitly defined predecessors via
     // the RegionBranchOpInterface. This can be the case if the current block
     // argument belongs to the first block in a region and the parent operation
     // implements the RegionBranchOpInterface.
     Region *argRegion = block->getParent();
     Operation *parentOp = argRegion->getParentOp();
     RegionBranchOpInterface regionInterface;
     if (!argRegion || &argRegion->front() != block ||
         !(regionInterface = dyn_cast<RegionBranchOpInterface>(parentOp)))
       return;
 
-    introduceCopiesForRegionSuccessors(
+    introduceClonesForRegionSuccessors(
         regionInterface, argRegion->getParentOp()->getRegions(), blockArg,
         [&](RegionSuccessor &successorRegion) {
           // Find a predecessor of our argRegion.
           return successorRegion.getSuccessor() == argRegion;
         });
 
     // Check whether the block argument belongs to an entry region of the
-    // parent operation. In this case, we have to introduce an additional copy
+    // parent operation. In this case, we have to introduce an additional clone
     // for buffer that is passed to the argument.
     SmallVector<RegionSuccessor, 2> successorRegions;
     regionInterface.getSuccessorRegions(/*index=*/llvm::None, successorRegions);
     auto *it =
         llvm::find_if(successorRegions, [&](RegionSuccessor &successorRegion) {
           return successorRegion.getSuccessor() == argRegion;
         });
     if (it == successorRegions.end())
       return;
 
-    // Determine the actual operand to introduce a copy for and rewire the
-    // operand to point to the copy instead.
+    // Determine the actual operand to introduce a clone for and rewire the
+    // operand to point to the clone instead.
     Value operand =
         regionInterface.getSuccessorEntryOperands(argRegion->getRegionNumber())
             [llvm::find(it->getSuccessorInputs(), blockArg).getIndex()];
-    Value copy = introduceBufferCopy(operand, parentOp);
+    Value clone = introduceCloneBuffers(operand, parentOp);
 
     auto op = llvm::find(parentOp->getOperands(), operand);
     assert(op != parentOp->getOperands().end() &&
            "parentOp does not contain operand");
-    parentOp->setOperand(op.getIndex(), copy);
+    parentOp->setOperand(op.getIndex(), clone);
   }
 
-  /// Introduces temporary allocs in front of all associated nested-region
+  /// Introduces temporary clones in front of all associated nested-region
   /// terminators and copies the source values into the newly allocated buffers.
   void introduceValueCopyForRegionResult(Value value) {
     // Get the actual result index in the scope of the parent terminator.
     Operation *operation = value.getDefiningOp();
     auto regionInterface = cast<RegionBranchOpInterface>(operation);
     // Filter successors that return to the parent operation.
     auto regionPredicate = [&](RegionSuccessor &successorRegion) {
       // If the RegionSuccessor has no associated successor, it will return to
       // its parent operation.
       return !successorRegion.getSuccessor();
     };
-    // Introduce a copy for all region "results" that are returned to the parent
-    // operation. This is required since the parent's result value has been
-    // considered critical. Therefore, the algorithm assumes that a copy of a
-    // previously allocated buffer is returned by the operation (like in the
-    // case of a block argument).
-    introduceCopiesForRegionSuccessors(regionInterface, operation->getRegions(),
+    // Introduce a clone for all region "results" that are returned to the
+    // parent operation. This is required since the parent's result value has
+    // been considered critical. Therefore, the algorithm assumes that a clone
+    // of a previously allocated buffer is returned by the operation (like in
+    // the case of a block argument).
+    introduceClonesForRegionSuccessors(regionInterface, operation->getRegions(),
                                        value, regionPredicate);
   }
 
-  /// Introduces buffer copies for all terminators in the given regions. The
+  /// Introduces buffer clones for all terminators in the given regions. The
   /// regionPredicate is applied to every successor region in order to restrict
-  /// the copies to specific regions.
+  /// the clones to specific regions.
   template <typename TPredicate>
-  void introduceCopiesForRegionSuccessors(
+  void introduceClonesForRegionSuccessors(
       RegionBranchOpInterface regionInterface, MutableArrayRef<Region> regions,
       Value argValue, const TPredicate &regionPredicate) {
     for (Region &region : regions) {
       // Query the regionInterface to get all successor regions of the current
       // one.
       SmallVector<RegionSuccessor, 2> successorRegions;
       regionInterface.getSuccessorRegions(region.getRegionNumber(),
                                           successorRegions);
for (Region &region : regions) {
               .getIndex();
 
       // Iterate over all immediate terminator operations to introduce
       // new buffer allocations. Thereby, the appropriate terminator operand
       // will be adjusted to point to the newly allocated buffer instead.
       walkReturnOperations(&region, [&](Operation *terminator) {
         // Extract the source value from the current terminator.
         Value sourceValue = terminator->getOperand(operandIndex);
-        // Create a new alloc at the current location of the terminator.
-        Value alloc = introduceBufferCopy(sourceValue, terminator);
-        // Wire alloc and terminator operand.
-        terminator->setOperand(operandIndex, alloc);
+        // Create a new clone at the current location of the terminator.
+        Value clone = introduceCloneBuffers(sourceValue, terminator);
+        // Wire clone and terminator operand.
+        terminator->setOperand(operandIndex, clone);
       });
     }
   }
 
-  /// Creates a new memory allocation for the given source value and copies
+  /// Creates a new memory allocation for the given source value and clones
   /// its content into the newly allocated buffer. The terminator operation is
-  /// used to insert the alloc and copy operations at the right places.
-  Value introduceBufferCopy(Value sourceValue, Operation *terminator) {
-    // Avoid multiple copies of the same source value. This can happen in the
+  /// used to insert the clone operation at the right place.
+  Value introduceCloneBuffers(Value sourceValue, Operation *terminator) {
+    // Avoid multiple clones of the same source value. This can happen in the
     // presence of loops when a branch acts as a backedge while also having
     // another successor that returns to its parent operation. Note: that
     // copying copied buffers can introduce memory leaks since the invariant of
-    // BufferPlacement assumes that a buffer will be only copied once into a
-    // temporary buffer. Hence, the construction of copy chains introduces
+    // BufferDeallocation assumes that a buffer will be only cloned once into a
+    // temporary buffer. Hence, the construction of clone chains introduces
     // additional allocations that are not tracked automatically by the
     // algorithm.
-    if (copiedValues.contains(sourceValue))
+    if (clonedValues.contains(sourceValue))
       return sourceValue;
-    // Create a new alloc at the current location of the terminator.
-    auto memRefType = sourceValue.getType().cast<MemRefType>();
+    // Create a new clone operation that copies the contents of the old
+    // buffer to the new one.
     OpBuilder builder(terminator);
+    auto cloneOp =
+        builder.create<memref::CloneOp>(terminator->getLoc(), sourceValue);
 
-    // Extract information about dynamically shaped types by
-    // extracting their dynamic dimensions.
-    auto dynamicOperands =
-        getDynOperands(terminator->getLoc(), sourceValue, builder);
-
-    // TODO: provide a generic interface to create dialect-specific
-    // Alloc and CopyOp nodes.
-    auto alloc = builder.create<memref::AllocOp>(terminator->getLoc(),
-                                                 memRefType, dynamicOperands);
-
-    // Create a new copy operation that copies to contents of the old
-    // allocation to the new one.
-    builder.create<linalg::CopyOp>(terminator->getLoc(), sourceValue, alloc);
-
-    // Remember the copy of original source value.
-    copiedValues.insert(alloc);
-    return alloc;
+    // Remember the clone of original source value.
+    clonedValues.insert(cloneOp);
+    return cloneOp;
   }
 
   /// Finds correct dealloc positions according to the algorithm described at
   /// the top of the file for all alloc nodes and block arguments that can be
   /// handled by this analysis.
   void placeDeallocs() const {
     // Move or insert deallocs using the previously computed information.
     // These deallocations will be linked to their associated allocation nodes
private:
   /// The dominator info to find the appropriate start operation to move the
   /// allocs.
   DominanceInfo dominators;
 
   /// The post dominator info to move the dependent allocs in the right
   /// position.
   PostDominanceInfo postDominators;
 
-  /// Stores already copied allocations to avoid additional copies of copies.
-  ValueSetT copiedValues;
+  /// Stores already cloned buffers to avoid additional clones of clones.
+  ValueSetT clonedValues;
 };
 
 //===----------------------------------------------------------------------===//
 // BufferDeallocationPass
 //===----------------------------------------------------------------------===//
 
 /// The actual buffer deallocation pass that inserts and moves dealloc nodes
-/// into the right positions. Furthermore, it inserts additional allocs and
-/// copies if necessary. It uses the algorithm described at the top of the file.
+/// into the right positions. Furthermore, it inserts additional clones if
+/// necessary. It uses the algorithm described at the top of the file.
 struct BufferDeallocationPass : BufferDeallocationBase<BufferDeallocationPass> {
 
   void runOnFunction() override {
     // Ensure that there are supported loops only.
     Backedges backedges(getFunction());
     if (backedges.size()) {
       getFunction().emitError(
           "Structured control-flow loops are supported only.");
       return signalPassFailure();
     }
 
     // Check that the control flow structures are supported.
     if (!validateSupportedControlFlow(getFunction().getRegion())) {
       return signalPassFailure();
     }
 
-    // Place all required temporary alloc, copy and dealloc nodes.
+    // Place all required temporary clone and dealloc nodes.
     BufferDeallocation deallocation(getFunction());
     deallocation.deallocate();
   }
 };
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // BufferDeallocationPass construction
 //===----------------------------------------------------------------------===//
 
 std::unique_ptr<Pass> mlir::createBufferDeallocationPass() {
   return std::make_unique<BufferDeallocationPass>();
 }

mlir/lib/Transforms/BufferUtils.cpp

 //===- BufferUtils.cpp - buffer transformation utilities ------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements utilities for buffer optimization passes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Transforms/BufferUtils.h"
 #include "PassDetail.h"
-#include "mlir/Dialect/Linalg/IR/LinalgOps.h"
+#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
 #include "mlir/Dialect/StandardOps/IR/Ops.h"
 #include "mlir/IR/Operation.h"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/LoopLikeInterface.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Transforms/Passes.h"
 #include "llvm/ADT/SetOperations.h"
 
Operation *opInPlacementBlock =
         placementBlock->findAncestorOpInBlock(*startOperation);
     startOperation = opInPlacementBlock ? opInPlacementBlock
                                         : placementBlock->getTerminator();
   }
 
   return startOperation;
 }
 
-/// Finds associated deallocs that can be linked to our allocation nodes (if
-/// any).
-Operation *BufferPlacementAllocs::findDealloc(Value allocValue) {
-  auto userIt = llvm::find_if(allocValue.getUsers(), [&](Operation *user) {
-    auto effectInterface = dyn_cast<MemoryEffectOpInterface>(user);
-    if (!effectInterface)
-      return false;
-    // Try to find a free effect that is applied to one of our values
-    // that will be automatically freed by our pass.
-    SmallVector<MemoryEffects::EffectInstance, 2> effects;
-    effectInterface.getEffectsOnValue(allocValue, effects);
-    return llvm::any_of(effects, [&](MemoryEffects::EffectInstance &it) {
-      return isa<MemoryEffects::Free>(it.getEffect());
-    });
-  });
-  // Assign the associated dealloc operation (if any).
-  return userIt != allocValue.user_end() ? *userIt : nullptr;
-}
-
 /// Initializes the internal list by discovering all supported allocation
 /// nodes.
 BufferPlacementAllocs::BufferPlacementAllocs(Operation *op) { build(op); }
 
 /// Searches for and registers all supported allocation entries.
 void BufferPlacementAllocs::build(Operation *op) {
   op->walk([&](MemoryEffectOpInterface opInterface) {
     // Try to find a single allocation result.

mlir/lib/Transforms/CopyRemoval.cpp

 //===- CopyRemoval.cpp - Removing the redundant copies --------------------===//
 //
 // 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/Dialect/MemRef/Utils/MemRefUtils.h"
 #include "mlir/Interfaces/CopyOpInterface.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Pass/Pass.h"
 #include "mlir/Transforms/Passes.h"
 
 using namespace mlir;
 using namespace MemoryEffects;
 

 
 private:
   /// List of operations that need to be removed.
   llvm::SmallPtrSet<Operation *, 4> eraseList;
 
   /// List of values that need to be replaced with their counterparts.
   llvm::SmallDenseSet<std::pair<Value, Value>, 4> replaceList;
 
-  /// Returns the allocation operation for `value` in `block` if it exists.
-  /// nullptr otherwise.
-  Operation *getAllocationOpInBlock(Value value, Block *block) {
-    assert(block && "Block cannot be null");
-    Operation *op = value.getDefiningOp();
-    if (op && op->getBlock() == block) {
-      auto effects = dyn_cast<MemoryEffectOpInterface>(op);
-      if (effects && effects.hasEffect<Allocate>())
-        return op;
-    }
-    return nullptr;
-  }
-
   /// Returns the deallocation operation for `value` in `block` if it exists.
   /// nullptr otherwise.
   Operation *getDeallocationOpInBlock(Value value, Block *block) {
     assert(block && "Block cannot be null");
     auto valueUsers = value.getUsers();
     auto it = llvm::find_if(valueUsers, [&](Operation *op) {
       auto effects = dyn_cast<MemoryEffectOpInterface>(op);
       return effects && op->getBlock() == block && effects.hasEffect<Free>();
bool hasMemoryEffectOpBetween(Operation *start, Operation *end) {
     while (op->isBeforeInBlock(end)) {
       if (isa<MemoryEffectOpInterface>(op))
         return true;
       op = op->getNextNode();
     }
     return false;
   };
 
-  /// Returns true if `val` value has at least a user between `start` and
-  /// `end` operations.
-  bool hasUsersBetween(Value val, Operation *start, Operation *end) {
-    assert((start || end) && "Start and end operations cannot be null");
-    Block *block = start->getBlock();
-    assert(block == end->getBlock() &&
-           "Start and end operations should be in the same block.");
-    return llvm::any_of(val.getUsers(), [&](Operation *op) {
-      return op->getBlock() == block && start->isBeforeInBlock(op) &&
-             op->isBeforeInBlock(end);
-    });
-  };
-
   bool areOpsInTheSameBlock(ArrayRef<Operation *> operations) {
     assert(!operations.empty() &&
            "The operations list should contain at least a single operation");
     Block *block = operations.front()->getBlock();
     return llvm::none_of(
         operations, [&](Operation *op) { return block != op->getBlock(); });
   }
 
void reuseCopySourceAsTarget(CopyOpInterface copyOp) {
 
     Value from = copyOp.getSource();
     Value to = copyOp.getTarget();
 
     Operation *copy = copyOp.getOperation();
     Block *copyBlock = copy->getBlock();
     Operation *fromDefiningOp = from.getDefiningOp();
     Operation *fromFreeingOp = getDeallocationOpInBlock(from, copyBlock);
-    Operation *toDefiningOp = getAllocationOpInBlock(to, copyBlock);
+    Operation *toDefiningOp = findAlloc(to, copyBlock);
     if (!fromDefiningOp || !fromFreeingOp || !toDefiningOp ||
         !areOpsInTheSameBlock({fromFreeingOp, toDefiningOp, copy}) ||
         hasUsersBetween(to, toDefiningOp, copy) ||
         hasUsersBetween(from, copy, fromFreeingOp) ||
         hasMemoryEffectOpBetween(copy, fromFreeingOp))
       return;
 
     replaceList.insert({to, from});
void reuseCopyTargetAsSource(CopyOpInterface copyOp) {
     if (eraseList.count(copyOp))
       return;
 
     Value from = copyOp.getSource();
     Value to = copyOp.getTarget();
 
     Operation *copy = copyOp.getOperation();
     Block *copyBlock = copy->getBlock();
-    Operation *fromDefiningOp = getAllocationOpInBlock(from, copyBlock);
+    Operation *fromDefiningOp = findAlloc(from, copyBlock);
     Operation *fromFreeingOp = getDeallocationOpInBlock(from, copyBlock);
     if (!fromDefiningOp || !fromFreeingOp ||
         !areOpsInTheSameBlock({fromFreeingOp, fromDefiningOp, copy}) ||
         hasUsersBetween(to, fromDefiningOp, copy) ||
         hasUsersBetween(from, copy, fromFreeingOp) ||
         hasMemoryEffectOpBetween(copy, fromFreeingOp))
       return;
 

mlir/test/Transforms/buffer-deallocation.mlir

^bb2:
   test.buffer_based in(%arg1: memref<2xf32>) out(%0: memref<2xf32>)
   br ^bb3(%0 : memref<2xf32>)
 ^bb3(%1: memref<2xf32>):
   test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>)
   return
 }
 
 // CHECK-NEXT: cond_br
-//      CHECK: %[[ALLOC0:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+//      CHECK: %[[ALLOC0:.*]] = memref.clone
 // CHECK-NEXT: br ^bb3(%[[ALLOC0]]
-//      CHECK: %[[ALLOC1:.*]] = memref.alloc()
+//      CHECK: %[[ALLOC1:.*]] = memref.alloc
 // CHECK-NEXT: test.buffer_based
-//      CHECK: %[[ALLOC2:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.clone %[[ALLOC1]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC1]]
 // CHECK-NEXT: br ^bb3(%[[ALLOC2]]
 //      CHECK: test.copy
 // CHECK-NEXT: memref.dealloc
 // CHECK-NEXT: return
 
 // -----
 
^bb2(%0: index):
   test.buffer_based in(%arg1: memref<?xf32>) out(%1: memref<?xf32>)
   br ^bb3(%1 : memref<?xf32>)
 ^bb3(%2: memref<?xf32>):
   test.copy(%2, %arg2) : (memref<?xf32>, memref<?xf32>)
   return
 }
 
 // CHECK-NEXT: cond_br
-//      CHECK: %[[DIM0:.*]] = memref.dim
-// CHECK-NEXT: %[[ALLOC0:.*]] = memref.alloc(%[[DIM0]])
-// CHECK-NEXT: linalg.copy(%{{.*}}, %[[ALLOC0]])
+//      CHECK: %[[ALLOC0:.*]] = memref.clone
 // CHECK-NEXT: br ^bb3(%[[ALLOC0]]
 //      CHECK: ^bb2(%[[IDX:.*]]:{{.*}})
 // CHECK-NEXT: %[[ALLOC1:.*]] = memref.alloc(%[[IDX]])
 // CHECK-NEXT: test.buffer_based
-//      CHECK: %[[DIM1:.*]] = memref.dim %[[ALLOC1]]
-// CHECK-NEXT: %[[ALLOC2:.*]] = memref.alloc(%[[DIM1]])
-// CHECK-NEXT: linalg.copy(%[[ALLOC1]], %[[ALLOC2]])
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.clone
 // CHECK-NEXT: memref.dealloc %[[ALLOC1]]
 // CHECK-NEXT: br ^bb3
 // CHECK-NEXT: ^bb3(%[[ALLOC3:.*]]:{{.*}})
 //      CHECK: test.copy(%[[ALLOC3]],
 // CHECK-NEXT: memref.dealloc %[[ALLOC3]]
 // CHECK-NEXT: return
 
 // -----
^bb5(%2: memref<?xf32>):
   br ^bb6(%2 : memref<?xf32>)
 ^bb6(%3: memref<?xf32>):
   br ^bb7(%3 : memref<?xf32>)
 ^bb7(%4: memref<?xf32>):
   test.copy(%4, %arg2) : (memref<?xf32>, memref<?xf32>)
   return
 }
 
-// CHECK-NEXT: cond_br
-//      CHECK: ^bb1
-//      CHECK: %[[DIM0:.*]] = memref.dim
-// CHECK-NEXT: %[[ALLOC0:.*]] = memref.alloc(%[[DIM0]])
-// CHECK-NEXT: linalg.copy(%{{.*}}, %[[ALLOC0]])
-// CHECK-NEXT: br ^bb6
+// CHECK-NEXT: cond_br{{.*}}
+// CHECK-NEXT: ^bb1
+// CHECK-NEXT: %[[ALLOC0:.*]] = memref.clone
+// CHECK-NEXT: br ^bb6(%[[ALLOC0]]
 //      CHECK: ^bb2(%[[IDX:.*]]:{{.*}})
 // CHECK-NEXT: %[[ALLOC1:.*]] = memref.alloc(%[[IDX]])
 // CHECK-NEXT: test.buffer_based
 //      CHECK: cond_br
 //      CHECK: ^bb3:
 // CHECK-NEXT: br ^bb5(%[[ALLOC1]]{{.*}})
 //      CHECK: ^bb4:
 // CHECK-NEXT: br ^bb5(%[[ALLOC1]]{{.*}})
 // CHECK-NEXT: ^bb5(%[[ALLOC2:.*]]:{{.*}})
-//      CHECK: %[[DIM2:.*]] = memref.dim %[[ALLOC2]]
-// CHECK-NEXT: %[[ALLOC3:.*]] = memref.alloc(%[[DIM2]])
-// CHECK-NEXT: linalg.copy(%[[ALLOC2]], %[[ALLOC3]])
+// CHECK-NEXT: %[[ALLOC3:.*]] = memref.clone %[[ALLOC2]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC1]]
 // CHECK-NEXT: br ^bb6(%[[ALLOC3]]{{.*}})
 // CHECK-NEXT: ^bb6(%[[ALLOC4:.*]]:{{.*}})
 // CHECK-NEXT: br ^bb7(%[[ALLOC4]]{{.*}})
 // CHECK-NEXT: ^bb7(%[[ALLOC5:.*]]:{{.*}})
 //      CHECK: test.copy(%[[ALLOC5]],
 // CHECK-NEXT: memref.dealloc %[[ALLOC4]]
 // CHECK-NEXT: return
^bb1:
   %0 = memref.alloc() : memref<2xf32>
   test.buffer_based in(%arg1: memref<2xf32>) out(%0: memref<2xf32>)
   br ^bb2(%0 : memref<2xf32>)
 ^bb2(%1: memref<2xf32>):
   test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>)
   return
 }
 
-// CHECK-NEXT: %[[ALLOC0:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+// CHECK-NEXT: %[[ALLOC0:.*]] = memref.clone
 // CHECK-NEXT: cond_br
 //      CHECK: %[[ALLOC1:.*]] = memref.alloc()
 // CHECK-NEXT: test.buffer_based
-//      CHECK: %[[ALLOC2:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.clone %[[ALLOC1]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC1]]
 //      CHECK: test.copy
 // CHECK-NEXT: memref.dealloc
 // CHECK-NEXT: return
 
 // -----
 
 // Test Case:
^bb2:
   %1 = memref.alloc() : memref<2xf32>
   test.buffer_based in(%arg0: memref<2xf32>) out(%1: memref<2xf32>)
   br ^exit(%1 : memref<2xf32>)
 ^exit(%arg2: memref<2xf32>):
   test.copy(%arg2, %arg1) : (memref<2xf32>, memref<2xf32>)
   return
 }
 
-// CHECK-NEXT: cond_br
-//      CHECK: ^bb1
-//      CHECK: ^bb1
+// CHECK-NEXT: cond_br{{.*}}
+// CHECK-NEXT: ^bb1
 //      CHECK: %[[ALLOC0:.*]] = memref.alloc()
 // CHECK-NEXT: test.buffer_based
-//      CHECK: %[[ALLOC1:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.clone %[[ALLOC0]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC0]]
 // CHECK-NEXT: br ^bb3(%[[ALLOC1]]
 // CHECK-NEXT: ^bb2
 // CHECK-NEXT: %[[ALLOC2:.*]] = memref.alloc()
 // CHECK-NEXT: test.buffer_based
-//      CHECK: %[[ALLOC3:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+// CHECK-NEXT: %[[ALLOC3:.*]] = memref.clone %[[ALLOC2]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC2]]
 // CHECK-NEXT: br ^bb3(%[[ALLOC3]]
 // CHECK-NEXT: ^bb3(%[[ALLOC4:.*]]:{{.*}})
 //      CHECK: test.copy
 // CHECK-NEXT: memref.dealloc %[[ALLOC4]]
 // CHECK-NEXT: return
 
 // -----
^bb2:
   }
   br ^bb3(%0 : memref<2xf32>)
 ^bb3(%1: memref<2xf32>):
   test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>)
   return
 }
 //      CHECK: (%[[cond:.*]]: {{.*}}, %[[ARG1:.*]]: {{.*}}, %{{.*}}: {{.*}})
 // CHECK-NEXT:   cond_br %[[cond]], ^[[BB1:.*]], ^[[BB2:.*]]
-//      CHECK:   %[[ALLOC0:.*]] = memref.alloc()
-// CHECK-NEXT:   linalg.copy(%[[ARG1]], %[[ALLOC0]])
+//      CHECK:   %[[ALLOC0:.*]] = memref.clone %[[ARG1]]
 //      CHECK: ^[[BB2]]:
 //      CHECK:   %[[ALLOC1:.*]] = memref.alloc()
 // CHECK-NEXT:   test.region_buffer_based in(%[[ARG1]]{{.*}}out(%[[ALLOC1]]
 //      CHECK:     %[[ALLOC2:.*]] = memref.alloc()
 // CHECK-NEXT:     test.buffer_based in(%[[ARG1]]{{.*}}out(%[[ALLOC2]]
 //      CHECK:     memref.dealloc %[[ALLOC2]]
 // CHECK-NEXT:     %{{.*}} = math.exp
-//      CHECK:   %[[ALLOC3:.*]] = memref.alloc()
-// CHECK-NEXT:   linalg.copy(%[[ALLOC1]], %[[ALLOC3]])
+//      CHECK:   %[[ALLOC3:.*]] = memref.clone %[[ALLOC1]]
 // CHECK-NEXT:   memref.dealloc %[[ALLOC1]]
 //      CHECK:  ^[[BB3:.*]]({{.*}}):
 //      CHECK:  test.copy
-// CHECK-NEXT:  dealloc
+// CHECK-NEXT:  memref.dealloc
 
 // -----
 
 // Test Case: buffer deallocation escaping
 // BufferDeallocation expected behavior: It must not dealloc %arg1 and %x
 // since they are operands of return operation and should escape from
 // deallocating. It should dealloc %y after CopyOp.
 
%2 = scf.if %0 -> (memref<?x?xf32>) {
     %3 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
     scf.yield %3 : memref<?x?xf32>
   }
   return %2 : memref<?x?xf32>
 }
 
 //      CHECK: %[[ALLOC0:.*]] = memref.alloc(%arg0, %arg0)
 // CHECK-NEXT: %[[ALLOC1:.*]] = scf.if
-//      CHECK: %[[ALLOC2:.*]] = memref.alloc
-// CHECK-NEXT: linalg.copy(%[[ALLOC0]], %[[ALLOC2]])
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.clone %[[ALLOC0]]
 //      CHECK: scf.yield %[[ALLOC2]]
 //      CHECK: %[[ALLOC3:.*]] = memref.alloc(%arg0, %arg1)
-//      CHECK: %[[ALLOC4:.*]] = memref.alloc
-// CHECK-NEXT: linalg.copy(%[[ALLOC3]], %[[ALLOC4]])
+// CHECK-NEXT: %[[ALLOC4:.*]] = memref.clone %[[ALLOC3]]
 //      CHECK: memref.dealloc %[[ALLOC3]]
 //      CHECK: scf.yield %[[ALLOC4]]
 //      CHECK: memref.dealloc %[[ALLOC0]]
 // CHECK-NEXT: return %[[ALLOC1]]
 
 // -----
 
 // Test Case: nested region control flow within a region interface.
^bb2:
   br ^bb3(%0 : memref<2xf32>)
 ^bb3(%1: memref<2xf32>):
   test.copy(%1, %arg2) : (memref<2xf32>, memref<2xf32>)
   return
 }
 //      CHECK: (%[[cond:.*]]: {{.*}}, %[[ARG1:.*]]: {{.*}}, %{{.*}}: {{.*}})
 // CHECK-NEXT:   cond_br %[[cond]], ^[[BB1:.*]], ^[[BB2:.*]]
 //      CHECK: ^[[BB1]]:
-//      CHECK: %[[ALLOC0:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy
+//      CHECK: %[[ALLOC0:.*]] = memref.clone
 //      CHECK: ^[[BB2]]:
 //      CHECK:   %[[ALLOC1:.*]] = memref.alloc()
 // CHECK-NEXT:   test.region_buffer_based in(%[[ARG1]]{{.*}}out(%[[ALLOC1]]
 //      CHECK:     %[[ALLOCA:.*]] = memref.alloca()
 // CHECK-NEXT:     test.buffer_based in(%[[ARG1]]{{.*}}out(%[[ALLOCA]]
 //      CHECK:     %{{.*}} = math.exp
-//      CHECK:  %[[ALLOC2:.*]] = memref.alloc()
-// CHECK-NEXT:  linalg.copy
+//      CHECK:  %[[ALLOC2:.*]] = memref.clone %[[ALLOC1]]
 // CHECK-NEXT:  memref.dealloc %[[ALLOC1]]
 //      CHECK:  ^[[BB3:.*]]({{.*}}):
 //      CHECK:  test.copy
-// CHECK-NEXT:  dealloc
+// CHECK-NEXT:  memref.dealloc
 
 // -----
 
 // CHECK-LABEL: func @nestedRegionControlFlowAlloca
 func @nestedRegionControlFlowAlloca(
   %arg0 : index,
   %arg1 : index) -> memref<?x?xf32> {
   %0 = cmpi eq, %arg0, %arg1 : index
%1 = scf.for %i = %lb to %ub step %step
     scf.yield %3 : memref<2xf32>
   }
   test.copy(%1, %res) : (memref<2xf32>, memref<2xf32>)
   return
 }
 
 //      CHECK: %[[ALLOC0:.*]] = memref.alloc()
 // CHECK-NEXT: memref.dealloc %[[ALLOC0]]
-// CHECK-NEXT: %[[ALLOC1:.*]] = memref.alloc()
-//      CHECK: linalg.copy(%arg3, %[[ALLOC1]])
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.clone %arg3
 //      CHECK: %[[ALLOC2:.*]] = scf.for {{.*}} iter_args
 // CHECK-SAME: (%[[IALLOC:.*]] = %[[ALLOC1]]
 //      CHECK:    cmpi
 //      CHECK:    memref.dealloc %[[IALLOC]]
 //      CHECK:    %[[ALLOC3:.*]] = memref.alloc()
-//      CHECK:    %[[ALLOC4:.*]] = memref.alloc()
-//      CHECK:    linalg.copy(%[[ALLOC3]], %[[ALLOC4]])
+//      CHECK:    %[[ALLOC4:.*]] = memref.clone %[[ALLOC3]]
 //      CHECK:    memref.dealloc %[[ALLOC3]]
 //      CHECK:    scf.yield %[[ALLOC4]]
 //      CHECK: }
 //      CHECK: test.copy(%[[ALLOC2]], %arg4)
 // CHECK-NEXT: memref.dealloc %[[ALLOC2]]
 
 // -----
 
%3 = scf.if %2 -> (memref<2xf32>) {
       scf.yield %0 : memref<2xf32>
     }
     scf.yield %3 : memref<2xf32>
   }
   return %1 : memref<2xf32>
 }
 
 //      CHECK: %[[ALLOC0:.*]] = memref.alloc()
-//      CHECK: %[[ALLOC1:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%arg3, %[[ALLOC1]])
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.clone %arg3
 // CHECK-NEXT: %[[ALLOC2:.*]] = scf.for {{.*}} iter_args
 // CHECK-SAME: (%[[IALLOC:.*]] = %[[ALLOC1]]
 //      CHECK: memref.dealloc %[[IALLOC]]
 //      CHECK: %[[ALLOC3:.*]] = scf.if
 
 //      CHECK: %[[ALLOC4:.*]] = memref.alloc()
-// CHECK-NEXT: %[[ALLOC5:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC4]], %[[ALLOC5]])
+// CHECK-NEXT: %[[ALLOC5:.*]] = memref.clone %[[ALLOC4]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC4]]
 // CHECK-NEXT: scf.yield %[[ALLOC5]]
 
-//      CHECK: %[[ALLOC6:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC0]], %[[ALLOC6]])
+//      CHECK: %[[ALLOC6:.*]] = memref.clone %[[ALLOC0]]
 // CHECK-NEXT: scf.yield %[[ALLOC6]]
 
-//      CHECK: %[[ALLOC7:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC3:.*]], %[[ALLOC7]])
+//      CHECK: %[[ALLOC7:.*]] = memref.clone %[[ALLOC3]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC3]]
 // CHECK-NEXT: scf.yield %[[ALLOC7]]
 
 //      CHECK: memref.dealloc %[[ALLOC0]]
 // CHECK-NEXT: return %[[ALLOC2]]
 
 // -----
 
%1 = scf.for %i = %lb to %ub step %step
     scf.yield %2 : memref<2xf32>
   }
   test.copy(%1, %res) : (memref<2xf32>, memref<2xf32>)
   return
 }
 
 //      CHECK: %[[ALLOC0:.*]] = memref.alloc()
 // CHECK-NEXT: memref.dealloc %[[ALLOC0]]
-// CHECK-NEXT: %[[ALLOC1:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%arg3, %[[ALLOC1]])
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.clone %arg3
 // CHECK-NEXT: %[[VAL_7:.*]] = scf.for {{.*}} iter_args
 // CHECK-SAME: (%[[IALLOC0:.*]] = %[[ALLOC1]])
-//      CHECK: %[[ALLOC2:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[IALLOC0]], %[[ALLOC2]])
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.clone %[[IALLOC0]]
 // CHECK-NEXT: memref.dealloc %[[IALLOC0]]
 // CHECK-NEXT: %[[ALLOC3:.*]] = scf.for {{.*}} iter_args
 // CHECK-SAME: (%[[IALLOC1:.*]] = %[[ALLOC2]])
-//      CHECK: %[[ALLOC5:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[IALLOC1]], %[[ALLOC5]])
+// CHECK-NEXT: %[[ALLOC5:.*]] = memref.clone %[[IALLOC1]]
 // CHECK-NEXT: memref.dealloc %[[IALLOC1]]
 
 //      CHECK: %[[ALLOC6:.*]] = scf.for {{.*}} iter_args
 // CHECK-SAME: (%[[IALLOC2:.*]] = %[[ALLOC5]])
 //      CHECK: %[[ALLOC8:.*]] = memref.alloc()
 // CHECK-NEXT: memref.dealloc %[[ALLOC8]]
 //      CHECK: %[[ALLOC9:.*]] = scf.if
 
 //      CHECK: %[[ALLOC11:.*]] = memref.alloc()
-// CHECK-NEXT: %[[ALLOC12:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC11]], %[[ALLOC12]])
+// CHECK-NEXT: %[[ALLOC12:.*]] = memref.clone %[[ALLOC11]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC11]]
 // CHECK-NEXT: scf.yield %[[ALLOC12]]
 
-//      CHECK: %[[ALLOC13:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[IALLOC2]], %[[ALLOC13]])
+//      CHECK: %[[ALLOC13:.*]] = memref.clone %[[IALLOC2]]
 // CHECK-NEXT: scf.yield %[[ALLOC13]]
 
 //      CHECK: memref.dealloc %[[IALLOC2]]
-// CHECK-NEXT: %[[ALLOC10:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC9]], %[[ALLOC10]])
+// CHECK-NEXT: %[[ALLOC10:.*]] = memref.clone %[[ALLOC9]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC9]]
 // CHECK-NEXT: scf.yield %[[ALLOC10]]
 
-//      CHECK: %[[ALLOC7:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC6]], %[[ALLOC7]])
+//      CHECK: %[[ALLOC7:.*]] = memref.clone %[[ALLOC6]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC6]]
 // CHECK-NEXT: scf.yield %[[ALLOC7]]
 
-//      CHECK: %[[ALLOC4:.*]] = memref.alloc()
-// CHECK-NEXT: linalg.copy(%[[ALLOC3]], %[[ALLOC4]])
+//      CHECK: %[[ALLOC4:.*]] = memref.clone %[[ALLOC3]]
 // CHECK-NEXT: memref.dealloc %[[ALLOC3]]
 // CHECK-NEXT: scf.yield %[[ALLOC4]]
 
 //      CHECK: test.copy(%[[VAL_7]], %arg4)
 // CHECK-NEXT: memref.dealloc %[[VAL_7]]
 
 // -----
 

 // CHECK-SAME: %[[ARG1:.*]]: {{.*}},
 // CHECK-SAME: %[[ARG2:.*]]: {{.*}}
 //      CHECK: %[[UNUSED_RESULT:.*]] = shape.assuming %[[ARG0]]
 // CHECK-NEXT:    %[[ALLOC0:.*]] = memref.alloc()
 // CHECK-NEXT:    memref.dealloc %[[ALLOC0]]
 // CHECK-NEXT:    shape.assuming_yield %[[ARG1]]
 //      CHECK: %[[ASSUMING_RESULT:.*]] = shape.assuming %[[ARG0]]
 // CHECK-NEXT:    %[[TMP_ALLOC:.*]] = memref.alloc()
-// CHECK-NEXT:    %[[RETURNING_ALLOC:.*]] = memref.alloc()
-// CHECK-NEXT:    linalg.copy(%[[TMP_ALLOC]], %[[RETURNING_ALLOC]])
+// CHECK-NEXT:    %[[RETURNING_ALLOC:.*]] = memref.clone %[[TMP_ALLOC]]
 // CHECK-NEXT:    memref.dealloc %[[TMP_ALLOC]]
 // CHECK-NEXT:    shape.assuming_yield %[[RETURNING_ALLOC]]
 //      CHECK: test.copy(%[[ASSUMING_RESULT:.*]], %[[ARG2]])
 // CHECK-NEXT: memref.dealloc %[[ASSUMING_RESULT]]
 
 // -----
 
 // Test Case: The op "test.bar" does not implement the RegionBranchOpInterface.

mlir/test/Transforms/canonicalize.mlir

func @subtensor(%t: tensor<8x16x4xf32>, %arg0 : index, %arg1 : index)
   // CHECK-SAME: tensor<7x11x2xf32> to tensor<2x?x2xf32>
   // CHECK: tensor.cast %{{.*}} : tensor<2x?x2xf32> to tensor<?x?x?xf32>
   %2 = subtensor %1[%c0, %c0, %c0] [%c2, %arg0, %c2] [%c1, %c1, %c1]
     : tensor<?x?x?xf32> to tensor<?x?x?xf32>
 
   return %2 : tensor<?x?x?xf32>
 }
 
+// -----
+
+// CHECK-LABEL: func @simple_clone_elimination
+func @simple_clone_elimination() -> memref<5xf32> {
+  %ret = memref.alloc() : memref<5xf32>
+  %temp = memref.clone %ret : memref<5xf32> to memref<5xf32>
+  memref.dealloc %temp : memref<5xf32>
+  return %ret : memref<5xf32>
+}
+// CHECK-NEXT: %[[ret:.*]] = memref.alloc()
+// CHECK-NOT: %[[temp:.*]] = memref.clone
+// CHECK-NOT: memref.dealloc %[[temp]]
+// CHECK: return %[[ret]]
+
+// -----
+
+// CHECK-LABEL: func @clone_loop_alloc
+func @clone_loop_alloc(%arg0: index, %arg1: index, %arg2: index, %arg3: memref<2xf32>, %arg4: memref<2xf32>) {
+  %0 = memref.alloc() : memref<2xf32>
+  memref.dealloc %0 : memref<2xf32>
+  %1 = memref.clone %arg3 : memref<2xf32> to memref<2xf32>
+  %2 = scf.for %arg5 = %arg0 to %arg1 step %arg2 iter_args(%arg6 = %1) -> (memref<2xf32>) {
+    %3 = cmpi eq, %arg5, %arg1 : index
+    memref.dealloc %arg6 : memref<2xf32>
+    %4 = memref.alloc() : memref<2xf32>
+    %5 = memref.clone %4 : memref<2xf32> to memref<2xf32>
+    memref.dealloc %4 : memref<2xf32>
+    %6 = memref.clone %5 : memref<2xf32> to memref<2xf32>
+    memref.dealloc %5 : memref<2xf32>
+    scf.yield %6 : memref<2xf32>
+  }
+  linalg.copy(%2, %arg4) : memref<2xf32>, memref<2xf32>
+  memref.dealloc %2 : memref<2xf32>
+  return
+}
+
+// CHECK-NEXT: %[[ALLOC0:.*]] = memref.clone
+// CHECK-NEXT: %[[ALLOC1:.*]] = scf.for
+// CHECK-NEXT: memref.dealloc
+// CHECK-NEXT: %[[ALLOC2:.*]] = memref.alloc
+// CHECK-NEXT: scf.yield %[[ALLOC2]]
+// CHECK: linalg.copy(%[[ALLOC1]]
+// CHECK-NEXT: memref.dealloc %[[ALLOC1]]
+
+// -----
+
+// CHECK-LABEL: func @clone_nested_region
+func @clone_nested_region(%arg0: index, %arg1: index) -> memref<?x?xf32> {
+  %0 = cmpi eq, %arg0, %arg1 : index
+  %1 = memref.alloc(%arg0, %arg0) : memref<?x?xf32>
+  %2 = scf.if %0 -> (memref<?x?xf32>) {
+    %3 = scf.if %0 -> (memref<?x?xf32>) {
+      %9 = memref.clone %1 : memref<?x?xf32> to memref<?x?xf32>
+      scf.yield %9 : memref<?x?xf32>
+    } else {
+      %7 = memref.alloc(%arg0, %arg1) : memref<?x?xf32>
+      %10 = memref.clone %7 : memref<?x?xf32> to memref<?x?xf32>
+      memref.dealloc %7 : memref<?x?xf32>
+      scf.yield %10 : memref<?x?xf32>
+    }
+    %6 = memref.clone %3 : memref<?x?xf32> to memref<?x?xf32>
+    memref.dealloc %3 : memref<?x?xf32>
+    scf.yield %6 : memref<?x?xf32>
+  } else {
+    %3 = memref.alloc(%arg1, %arg1) : memref<?x?xf32>
+    %6 = memref.clone %3 : memref<?x?xf32> to memref<?x?xf32>
+    memref.dealloc %3 : memref<?x?xf32>
+    scf.yield %6 : memref<?x?xf32>
+  }
+  memref.dealloc %1 : memref<?x?xf32>
+  return %2 : memref<?x?xf32>
+}
+
+//      CHECK: %[[ALLOC1:.*]] = memref.alloc
+// CHECK-NEXT: %[[ALLOC2:.*]] = scf.if
+// CHECK-NEXT: %[[ALLOC3:.*]] = scf.if
+// CHECK-NEXT: %[[ALLOC5:.*]] = memref.clone %[[ALLOC1]]
+// CHECK-NEXT: scf.yield %[[ALLOC5]]
+//      CHECK: %[[ALLOC0:.*]] = memref.alloc
+// CHECK-NEXT: scf.yield %[[ALLOC0]]
+//      CHECK: %[[ALLOC4:.*]] = memref.clone %[[ALLOC3]]
+// CHECK-NEXT: memref.dealloc %[[ALLOC3]]
+// CHECK-NEXT: scf.yield %[[ALLOC4]]
+//      CHECK: %[[ALLOC6:.*]] = memref.alloc
+// CHECK-NEXT: scf.yield %[[ALLOC6]]
+//      CHECK: memref.dealloc %[[ALLOC1]]
+// CHECK-NEXT: return %[[ALLOC2]]
+
+// -----
+
+// CHECK-LABEL: func @clone_ret_usage_before_copy
+func @clone_ret_usage_before_copy() -> memref<5xf32> {
+  %ret = memref.alloc() : memref<5xf32>
+  %c0 = constant 0 : index
+  %dimension = memref.dim %ret, %c0 : memref<5xf32>
+  %temp = memref.clone %ret : memref<5xf32> to memref<5xf32>
+  memref.dealloc %ret : memref<5xf32>
+  return %temp : memref<5xf32>
+}
+
+//      CHECK: %[[ALLOC0:.*]] = memref.alloc
+// CHECK-NEXT: return %[[ALLOC0]]
+
+// -----
+
+// CHECK-LABEL: func @clone_ret_usage_after_copy
+func @clone_ret_usage_after_copy() -> memref<?xf32> {
+  %ret = memref.alloc() : memref<5xf32>
+  %temp = memref.clone %ret : memref<5xf32> to memref<5xf32>
+  %c0 = constant 0 : index
+  %dimension = memref.dim %ret, %c0 : memref<5xf32>
+  memref.dealloc %ret : memref<5xf32>
+  %ret2 = memref.alloc(%dimension) : memref<?xf32>
+  return %ret2 : memref<?xf32>
+}
+
+//      CHECK: %[[ALLOC0:.*]] = memref.alloc
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.cast
+// CHECK-NEXT: return %[[ALLOC1]]
+
+// -----
+
+// CHECK-LABEL: func @clone_temp_usage_after_copy
+func @clone_temp_usage_after_copy() -> memref<?xf32> {
+  %ret = memref.alloc() : memref<5xf32>
+  %temp = memref.clone %ret : memref<5xf32> to memref<5xf32>
+  %c0 = constant 0 : index
+  %dimension = memref.dim %temp, %c0 : memref<5xf32>
+  memref.dealloc %ret : memref<5xf32>
+  %ret2 = memref.alloc(%dimension) : memref<?xf32>
+  return %ret2 : memref<?xf32>
+}
+
+//      CHECK: %[[ALLOC0:.*]] = memref.alloc
+// CHECK-NEXT: %[[ALLOC1:.*]] = memref.cast
+// CHECK-NEXT: return %[[ALLOC1]]