[mlir] Split BufferAliasAnalysis into 2 classes

[tpopp]

Summary

The previous behavior is unmodified as BufferDependencyAnalysis. The new
BufferAliasAnalysis differs by finding all aliases of a buffer rather
than only subviews of the current value.

For example, given a sequence of subviews that create values
A -> B -> C -> d:
BufferDependencyAnalysis::resolve(B) => {B, C, D}
BufferAliasAnalysis::resolve(B) => {A, B, C, D}

The old behavior is needed by BufferDeallocation. The new behavior is
needed by transformations that are not looking for aliases relative to
the original AllocOp.

[tpopp]

Update cmake file and remove friendliness between Analyses

[tpopp]

Friendly ping.

[herhut]

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

mlir/lib/Analysis/BufferDependencyAnalysis.cpp

22

nit: dependency here, as well?

mlir/lib/Transforms/BufferOptimizations.cpp

330

Why is this needed?

[dfki-mako]

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

mlir/lib/Transforms/BufferOptimizations.cpp

330

Is there a specific use case where the current implementation is failing?

[dfki-mako]

mlir/lib/Analysis/BufferAliasAnalysis.cpp

53

nit: Comment does not match the implementation.

[tpopp]

In D100838#2724997, @herhut wrote:

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

I agree. I can't think of a good name though for "Alias analysis but only for aliases not provably earlier in control flow"

Possible names:
BufferSubviewAliasAnalysis
BufferForwardAliasAnalysis
BufferFlowAnalysis
BufferReferenceAnalysis

In D100838#2725321, @dfki-mako wrote:

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

Disclaimer:I'm not an expert on this topic, but the following was what I expected BufferAliasing to refer to and is what Wikipedia implies also. I don't think the current BufferAliasAnalysis (BufferDependencyAnalysis in this patch) should exist, if my view on aliases does turn out to be the common definition, but it was just hard or impossible to remove in the current Dealloc pass implementation.

Aliasing is a symmetric property(https://en.wikipedia.org/wiki/Alias_analysis). This AliasAnalysis is fundamentally broken when it thinks that B aliasing A does not have to imply A aliasing B. We should not think of this in terms of "B aliases A" but in terms of "A and B are potential aliases of the same memory location" or "A and B are not guaranteed to be disjoint memory locations".

mlir/lib/Transforms/BufferOptimizations.cpp

330

There was some memory issue at one point, but it's no longer happening as i am using the same structure as previously, so I'll remove this.

330

I was trying to update BufferAliasAnalysis before without BufferDependencyAnalysis and there was some memory issue if I remember correctly(maybe I had some other bug). It's no longer needed though, so I'll revert it.

[tpopp]

I agree though that "Dependency" is a bad name. I'm just struggling to find a name to encode this concept of BufferViewFlowAnalysis.

[rriddle]

In D100838#2728187, @tpopp wrote:

In D100838#2724997, @herhut wrote:

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

I agree. I can't think of a good name though for "Alias analysis but only for aliases not provably earlier in control flow"

Possible names:
BufferSubviewAliasAnalysis
BufferForwardAliasAnalysis
BufferFlowAnalysis
BufferReferenceAnalysis

In D100838#2725321, @dfki-mako wrote:

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

Disclaimer:I'm not an expert on this topic, but the following was what I expected BufferAliasing to refer to and is what Wikipedia implies also. I don't think the current BufferAliasAnalysis (BufferDependencyAnalysis in this patch) should exist, if my view on aliases does turn out to be the common definition, but it was just hard or impossible to remove in the current Dealloc pass implementation.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly (i.e. it is hard coded for very specific types of input). This analysis should really be phased out in favor of the stuff in AliasAnalysis.h, but that is currently missing a few things (namely noalias tags for function arguments, which is one thing that the analysis in this file hard codes).

Aliasing is a symmetric property(https://en.wikipedia.org/wiki/Alias_analysis). This AliasAnalysis is fundamentally broken when it thinks that B aliasing A does not have to imply A aliasing B. We should not think of this in terms of "B aliases A" but in terms of "A and B are potential aliases of the same memory location" or "A and B are not guaranteed to be disjoint memory locations".

This is correct.

[dfki-mako]

I have to admit that my comment regarding all aliases of A was a bit misleading :-( At the time of writing, I accidentally had the "flow"-property (required by the BufferDeallocation phase) in mind. My comment was meant to address potentially "inconsistent" results of two "alias analyses" (of course, aliasing is a symmetric property!) :-)

Regarding the name: I really like BufferViewFlowAnalysis, as it expresses the property of data flow between different Value nodes.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly

This also sounds a bit misleading. At the time of implementing, we had to introduce a specialized and domain-specific version that collects all aliases depending on the "flow" of a given value. This analysis was never intended to serve as a universal global program analysis. However, I agree that it might be beneficial to replace this analysis implementation by the ones available right now.

[tpopp]

In D100838#2738299, @dfki-mako wrote:

I have to admit that my comment regarding all aliases of A was a bit misleading :-( At the time of writing, I accidentally had the "flow"-property (required by the BufferDeallocation phase) in mind. My comment was meant to address potentially "inconsistent" results of two "alias analyses" (of course, aliasing is a symmetric property!) :-)

Regarding the name: I really like BufferViewFlowAnalysis, as it expresses the property of data flow between different Value nodes.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly

This also sounds a bit misleading. At the time of implementing, we had to introduce a specialized and domain-specific version that collects all aliases depending on the "flow" of a given value. This analysis was never intended to serve as a universal global program analysis. However, I agree that it might be beneficial to replace this analysis implementation by the ones available right now.

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

[herhut]

In D100838#2741904, @tpopp wrote:

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

+1 to renaming it to avoid confusion in the future.

[dfki-mako]

In D100838#2743994, @herhut wrote:

In D100838#2741904, @tpopp wrote:

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

+1 to renaming it to avoid confusion in the future.

+1 to renaming :)

[tpopp]

Change this patch to just a rename and expanded documentation.

[dfki-mako]

Awesome work, thanks a lot :-)

mlir/include/mlir/Analysis/BufferAliasAnalysis.h

 //===- BufferAliasAnalysis.h - Buffer alias analysis for MLIR ---*- 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_ANALYSIS_BUFFERALIASANALYSIS_H
 #define MLIR_ANALYSIS_BUFFERALIASANALYSIS_H
 
+#include "mlir/Analysis/BufferDependencyAnalysis.h"
 #include "mlir/IR/Operation.h"
 #include "llvm/ADT/SmallPtrSet.h"
 
 namespace mlir {
 
 /// A straight-forward alias analysis which ensures that all aliases of all
 /// values will be determined. This is a requirement for the BufferPlacement
 /// class since you need to determine safe positions to place alloc and
 /// deallocs.
 class BufferAliasAnalysis {
 public:
   using ValueSetT = SmallPtrSet<Value, 16>;
   using ValueMapT = llvm::DenseMap<Value, ValueSetT>;
 
 public:
   /// Constructs a new alias analysis using the op provided.
   BufferAliasAnalysis(Operation *op);
 
-  /// Find all immediate aliases this value could potentially have.
-  ValueMapT::const_iterator find(Value value) const {
-    return aliases.find(value);
-  }
-
-  /// Returns the begin iterator to iterate over all aliases.
-  ValueMapT::const_iterator begin() const { return aliases.begin(); }
-
-  /// Returns the end iterator that can be used in combination with find.
-  ValueMapT::const_iterator end() const { return aliases.end(); }
-
   /// Find all immediate and indirect aliases this value could potentially
-  /// have. Note that the resulting set will also contain the value provided as
-  /// it is an alias of itself.
+  /// have, including preceding values that this value might have aliased (such
+  /// if `value` is created by a subview, this will return the parent view).
+  /// Note that the resulting set will also contain the value provided as it is
+  /// an alias of itself.
+  ///
+  /// A = *
+  /// B = subview(A)
+  /// C = B
+  ///
+  /// Results in resolve(B) returning {A, B, C}
   ValueSetT resolve(Value value) const;
 
   /// Removes the given values from all alias sets.
   void remove(const SmallPtrSetImpl<Value> &aliasValues);
 
 private:
   /// This function constructs a mapping from values to its immediate aliases.
   void build(Operation *op);
 
   /// Maps values to all immediate aliases this value can have.
-  ValueMapT aliases;
+  BufferDependencyAnalysis dependentAliases;
+  ValueMapT reversedDependencies;
 };
 
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_BUFFERALIASANALYSIS_H

mlir/include/mlir/Analysis/BufferDependencyAnalysis.h

+//===- BufferDependencyAnalysis.h - Buffer dependency analysis ---*- 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_ANALYSIS_BUFFERDEPENDENCYANALYSIS_H
+#define MLIR_ANALYSIS_BUFFERDEPENDENCYANALYSIS_H
+
+#include "mlir/IR/Operation.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace mlir {
+
+/// A straight-forward alias analysis which ensures that all dependencies of all
+/// values will be determined. This is a requirement for the BufferPlacement
+/// class since you need to determine safe positions to place alloc and
+/// deallocs. This alias analysis only finds aliases that might have been
+/// created on top of the specified view. To receive all aliases, use
+/// BufferAliasAnalysis.
+class BufferDependencyAnalysis {
+public:
+  using ValueSetT = SmallPtrSet<Value, 16>;
+  using ValueMapT = llvm::DenseMap<Value, ValueSetT>;
+
+  /// Constructs a new alias analysis using the op provided.
+  BufferDependencyAnalysis(Operation *op);
+
+  /// Find all immediate dependencies this value could potentially have.
+  ValueMapT::const_iterator find(Value value) const {
+    return dependencies.find(value);
+  }
+
+  /// Returns the begin iterator to iterate over all dependencies.
+  ValueMapT::const_iterator begin() const { return dependencies.begin(); }
+
+  /// Returns the end iterator that can be used in combination with find.
+  ValueMapT::const_iterator end() const { return dependencies.end(); }
+
+  /// Find all immediate and indirect views upong this value. This will find all
+  /// dependencies on this value that can potentially be later in the execution
+  /// of the program, but will not return values that this alias might have been
+  /// created from (such as if `value is created by a subview, this will not
+  /// return the parent view if there is no cyclic behavior). Note that the
+  /// resulting set will also contain the value provided as it is an alias of
+  /// itself.
+  ///
+  /// A = *
+  /// B = subview(A)
+  /// C = B
+  ///
+  /// Results in resolve(B) returning {B, C}
+  ValueSetT resolve(Value value) const;
+
+  /// Removes the given values from all alias sets.
+  void remove(const SmallPtrSetImpl<Value> &aliasValues);
+
+private:
+  /// This function constructs a mapping from values to its immediate
+  /// dependencies.
+  void build(Operation *op);
+
+  /// Maps values to all immediate dependencies this value can have.
+  ValueMapT dependencies;
+};
+
+} // namespace mlir
+
+#endif // MLIR_ANALYSIS_BUFFERDEPENDENCYANALYSIS_H

mlir/include/mlir/Transforms/BufferUtils.h

 //===- BufferUtils.h - Buffer optimization 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 file provides utilities for passes optimizing code that has already
 // been converted to buffers.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_TRANSFORMS_BUFFERUTILS_H
 #define MLIR_TRANSFORMS_BUFFERUTILS_H
 
-#include "mlir/Analysis/BufferAliasAnalysis.h"
+#include "mlir/Analysis/BufferDependencyAnalysis.h"
 #include "mlir/Analysis/Liveness.h"
 #include "mlir/Dialect/StandardOps/IR/Ops.h"
 #include "mlir/IR/Builders.h"
 #include "mlir/IR/BuiltinOps.h"
 #include "mlir/IR/Dominance.h"
 #include "mlir/IR/Operation.h"
 #include "mlir/Transforms/DialectConversion.h"
 

 private:
   /// Maps allocation nodes to their associated blocks.
   AllocEntryList allocs;
 };
 
 /// The base class for all BufferPlacement transformations.
 class BufferPlacementTransformationBase {
 public:
-  using ValueSetT = BufferAliasAnalysis::ValueSetT;
+  using ValueSetT = BufferDependencyAnalysis::ValueSetT;
 
   /// Finds a common dominator for the given value while taking the positions
   /// of the values in the value set into account. It supports dominator and
   /// post-dominator analyses via template arguments.
   template <typename DominatorT>
   static Block *findCommonDominator(Value value, const ValueSetT &values,
                                     const DominatorT &doms) {
     // Start with the current block the value is defined in.
public:
   /// control-flow edges for cycles.
   static bool isLoop(Operation *op);
 
   /// Constructs a new operation base using the given root operation.
   BufferPlacementTransformationBase(Operation *op);
 
 protected:
   /// Alias information that can be updated during the insertion of copies.
-  BufferAliasAnalysis aliases;
+  BufferDependencyAnalysis aliases;
 
   /// Stores all internally managed allocations.
   BufferPlacementAllocs allocs;
 
   /// The underlying liveness analysis to compute fine grained information
   /// about alloc and dealloc positions.
   Liveness liveness;
 };

mlir/lib/Analysis/BufferAliasAnalysis.cpp

 
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/ViewLikeInterface.h"
 #include "llvm/ADT/SetOperations.h"
 
 using namespace mlir;
 
 /// Constructs a new alias analysis using the op provided.
-BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) { build(op); }
+BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) : dependentAliases(op) {
+  build(op);
+}
 
 /// Find all immediate and indirect aliases this value could potentially
 /// have. Note that the resulting set will also contain the value provided as
 /// it is an alias of itself.
 BufferAliasAnalysis::ValueSetT
 BufferAliasAnalysis::resolve(Value rootValue) const {
   ValueSetT result;
   SmallVector<Value, 8> queue;
   queue.push_back(rootValue);
   while (!queue.empty()) {
     Value currentValue = queue.pop_back_val();
     if (result.insert(currentValue).second) {
-      auto it = aliases.find(currentValue);
-      if (it != aliases.end()) {
+      auto it = reversedDependencies.find(currentValue);
+      if (it != reversedDependencies.end()) {
         for (Value aliasValue : it->second)
           queue.push_back(aliasValue);
       }
     }
   }
+  auto resultForward = dependentAliases.resolve(rootValue);
+  result.insert(resultForward.begin(), resultForward.end());
+
   return result;
 }
 
 /// Removes the given values from all alias sets.
 void BufferAliasAnalysis::remove(const SmallPtrSetImpl<Value> &aliasValues) {
-  for (auto &entry : aliases)
+  dependentAliases.remove(aliasValues);
+  for (auto &entry : reversedDependencies)
     llvm::set_subtract(entry.second, aliasValues);
 }
 
 /// This function constructs a mapping from values to its immediate aliases.
 /// It iterates over all blocks, gets their predecessors, determines the
 /// values that will be passed to the corresponding block arguments and
 /// inserts them into the underlying map. Furthermore, it wires successor
 /// regions and branch-like return operations from nested regions.
 void BufferAliasAnalysis::build(Operation *op) {
-  // Registers all aliases of the given values.
-  auto registerAliases = [&](auto values, auto aliases) {
-    for (auto entry : llvm::zip(values, aliases))
-      this->aliases[std::get<0>(entry)].insert(std::get<1>(entry));
-  };
-
-  // Add additional aliases created by view changes to the alias list.
-  op->walk([&](ViewLikeOpInterface viewInterface) {
-    aliases[viewInterface.getViewSource()].insert(viewInterface->getResult(0));
-  });
-
-  // Query all branch interfaces to link block argument aliases.
-  op->walk([&](BranchOpInterface branchInterface) {
-    Block *parentBlock = branchInterface->getBlock();
-    for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end();
-         it != e; ++it) {
-      // Query the branch op interface to get the successor operands.
-      auto successorOperands =
-          branchInterface.getSuccessorOperands(it.getIndex());
-      if (!successorOperands.hasValue())
-        continue;
-      // Build the actual mapping of values to their immediate aliases.
-      registerAliases(successorOperands.getValue(), (*it)->getArguments());
-    }
-  });
-
-  // Query the RegionBranchOpInterface to find potential successor regions.
-  op->walk([&](RegionBranchOpInterface regionInterface) {
-    // Extract all entry regions and wire all initial entry successor inputs.
-    SmallVector<RegionSuccessor, 2> entrySuccessors;
-    regionInterface.getSuccessorRegions(/*index=*/llvm::None, entrySuccessors);
-    for (RegionSuccessor &entrySuccessor : entrySuccessors) {
-      // Wire the entry region's successor arguments with the initial
-      // successor inputs.
-      assert(entrySuccessor.getSuccessor() &&
-             "Invalid entry region without an attached successor region");
-      registerAliases(regionInterface.getSuccessorEntryOperands(
-                          entrySuccessor.getSuccessor()->getRegionNumber()),
-                      entrySuccessor.getSuccessorInputs());
-    }
-
-    // Wire flow between regions and from region exits.
-    for (Region &region : regionInterface->getRegions()) {
-      // Iterate over all successor region entries that are reachable from the
-      // current region.
-      SmallVector<RegionSuccessor, 2> successorRegions;
-      regionInterface.getSuccessorRegions(region.getRegionNumber(),
-                                          successorRegions);
-      for (RegionSuccessor &successorRegion : successorRegions) {
-        // Iterate over all immediate terminator operations and wire the
-        // successor inputs with the operands of each terminator.
-        for (Block &block : region) {
-          for (Operation &operation : block) {
-            if (operation.hasTrait<OpTrait::ReturnLike>())
-              registerAliases(operation.getOperands(),
-                              successorRegion.getSuccessorInputs());
-          }
-        }
-      }
-    }
-  });
+  for (auto i : dependentAliases) {
+    for (auto j : i.getSecond())
+      reversedDependencies[j].insert(i.getFirst());
 }

mlir/lib/Analysis/BufferDependencyAnalysis.cpp

-//===- BufferAliasAnalysis.cpp - Buffer alias analysis for MLIR -*- C++ -*-===//
+//======- BufferDependencyAnalysis.cpp - Buffer alias analysis -*- 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
 //
 //===----------------------------------------------------------------------===//
 
-#include "mlir/Analysis/BufferAliasAnalysis.h"
+#include "mlir/Analysis/BufferDependencyAnalysis.h"
 
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/ViewLikeInterface.h"
 #include "llvm/ADT/SetOperations.h"
 
 using namespace mlir;
 
 /// Constructs a new alias analysis using the op provided.
-BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) { build(op); }
+BufferDependencyAnalysis::BufferDependencyAnalysis(Operation *op) { build(op); }
 
-/// Find all immediate and indirect aliases this value could potentially
+/// Find all immediate and indirect dependencies this value could potentially
 /// have. Note that the resulting set will also contain the value provided as
 /// it is an alias of itself.
-BufferAliasAnalysis::ValueSetT
-BufferAliasAnalysis::resolve(Value rootValue) const {
+BufferDependencyAnalysis::ValueSetT
+BufferDependencyAnalysis::resolve(Value rootValue) const {
   ValueSetT result;
   SmallVector<Value, 8> queue;
   queue.push_back(rootValue);
   while (!queue.empty()) {
     Value currentValue = queue.pop_back_val();
     if (result.insert(currentValue).second) {
-      auto it = aliases.find(currentValue);
-      if (it != aliases.end()) {
+      auto it = dependencies.find(currentValue);
+      if (it != dependencies.end()) {
         for (Value aliasValue : it->second)
           queue.push_back(aliasValue);
       }
     }
   }
   return result;
 }
 
 /// Removes the given values from all alias sets.
-void BufferAliasAnalysis::remove(const SmallPtrSetImpl<Value> &aliasValues) {
-  for (auto &entry : aliases)
+void BufferDependencyAnalysis::remove(
+    const SmallPtrSetImpl<Value> &aliasValues) {
+  for (auto &entry : dependencies)
     llvm::set_subtract(entry.second, aliasValues);
 }
 
-/// This function constructs a mapping from values to its immediate aliases.
-/// It iterates over all blocks, gets their predecessors, determines the
-/// values that will be passed to the corresponding block arguments and
-/// inserts them into the underlying map. Furthermore, it wires successor
-/// regions and branch-like return operations from nested regions.
-void BufferAliasAnalysis::build(Operation *op) {
-  // Registers all aliases of the given values.
-  auto registerAliases = [&](auto values, auto aliases) {
-    for (auto entry : llvm::zip(values, aliases))
-      this->aliases[std::get<0>(entry)].insert(std::get<1>(entry));
+/// This function constructs a mapping from values to its immediate
+/// dependencies. It iterates over all blocks, gets their predecessors,
+/// determines the values that will be passed to the corresponding block
+/// arguments and inserts them into the underlying map. Furthermore, it wires
+/// successor regions and branch-like return operations from nested regions.
+void BufferDependencyAnalysis::build(Operation *op) {
+  // Registers all dependencies of the given values.
+  auto registerDependencies = [&](auto values, auto dependencies) {
+    for (auto entry : llvm::zip(values, dependencies))
+      this->dependencies[std::get<0>(entry)].insert(std::get<1>(entry));
   };
 
-  // Add additional aliases created by view changes to the alias list.
+  // Add additional dependencies created by view changes to the alias list.
   op->walk([&](ViewLikeOpInterface viewInterface) {
-    aliases[viewInterface.getViewSource()].insert(viewInterface->getResult(0));
+    dependencies[viewInterface.getViewSource()].insert(
+        viewInterface->getResult(0));
   });
 
-  // Query all branch interfaces to link block argument aliases.
+  // Query all branch interfaces to link block argument dependencies.
   op->walk([&](BranchOpInterface branchInterface) {
     Block *parentBlock = branchInterface->getBlock();
     for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end();
          it != e; ++it) {
       // Query the branch op interface to get the successor operands.
       auto successorOperands =
           branchInterface.getSuccessorOperands(it.getIndex());
       if (!successorOperands.hasValue())
         continue;
-      // Build the actual mapping of values to their immediate aliases.
-      registerAliases(successorOperands.getValue(), (*it)->getArguments());
+      // Build the actual mapping of values to their immediate dependencies.
+      registerDependencies(successorOperands.getValue(), (*it)->getArguments());
     }
   });
 
   // Query the RegionBranchOpInterface to find potential successor regions.
   op->walk([&](RegionBranchOpInterface regionInterface) {
     // Extract all entry regions and wire all initial entry successor inputs.
     SmallVector<RegionSuccessor, 2> entrySuccessors;
     regionInterface.getSuccessorRegions(/*index=*/llvm::None, entrySuccessors);
     for (RegionSuccessor &entrySuccessor : entrySuccessors) {
       // Wire the entry region's successor arguments with the initial
       // successor inputs.
       assert(entrySuccessor.getSuccessor() &&
              "Invalid entry region without an attached successor region");
-      registerAliases(regionInterface.getSuccessorEntryOperands(
-                          entrySuccessor.getSuccessor()->getRegionNumber()),
-                      entrySuccessor.getSuccessorInputs());
+      registerDependencies(
+          regionInterface.getSuccessorEntryOperands(
     }
 
     // Wire flow between regions and from region exits.
     for (Region &region : regionInterface->getRegions()) {
       // Iterate over all successor region entries that are reachable from the
       // current region.
       SmallVector<RegionSuccessor, 2> successorRegions;
       regionInterface.getSuccessorRegions(region.getRegionNumber(),
                                           successorRegions);
       for (RegionSuccessor &successorRegion : successorRegions) {
         // Iterate over all immediate terminator operations and wire the
         // successor inputs with the operands of each terminator.
         for (Block &block : region) {
           for (Operation &operation : block) {
             if (operation.hasTrait<OpTrait::ReturnLike>())
-              registerAliases(operation.getOperands(),
+              registerDependencies(operation.getOperands(),
                                    successorRegion.getSuccessorInputs());
           }
         }
       }
     }
   });
 }

mlir/lib/Analysis/CMakeLists.txt

 set(LLVM_OPTIONAL_SOURCES
   AliasAnalysis.cpp
   AffineAnalysis.cpp
   AffineStructures.cpp
   BufferAliasAnalysis.cpp
+  BufferDependencyAnalysis.cpp
   CallGraph.cpp
   LinearTransform.cpp
   Liveness.cpp
   LoopAnalysis.cpp
   NestedMatcher.cpp
   NumberOfExecutions.cpp
   PresburgerSet.cpp
   SliceAnalysis.cpp
   Utils.cpp
 
   AliasAnalysis/LocalAliasAnalysis.cpp
   )
 
 add_mlir_library(MLIRAnalysis
   AliasAnalysis.cpp
   BufferAliasAnalysis.cpp
+  BufferDependencyAnalysis.cpp
   CallGraph.cpp
   Liveness.cpp
   NumberOfExecutions.cpp
   SliceAnalysis.cpp
 
   AliasAnalysis/LocalAliasAnalysis.cpp
 
   ADDITIONAL_HEADER_DIRS

mlir/lib/Transforms/BufferDeallocation.cpp

 // 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 BufferDependencyAnalysis 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 clone buffer for %arg1 that will
-// contain the actual contents. Using the class BufferAliasAnalysis, we
+// contain the actual contents. Using the class BufferDependencyAnalysis, 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
 // 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 clone buffers

mlir/lib/Transforms/BufferOptimizations.cpp

unsigned int bitwidth = type.getElementType().isIndex()
                               ? bitwidthOfIndexType
                               : type.getElementTypeBitWidth();
   return type.getNumElements() * bitwidth <= maximumSizeInBytes * 8;
 }
 
 /// Checks whether the given aliases leave the allocation scope.
 static bool
 leavesAllocationScope(Region *parentRegion,
-                      const BufferAliasAnalysis::ValueSetT &aliases) {
+                      const BufferDependencyAnalysis::ValueSetT &aliases) {
   for (Value alias : aliases) {
     for (auto *use : alias.getUsers()) {
       // If there is at least one alias that leaves the parent region, we know
       // that this alias escapes the whole region and hence the associated
       // allocation leaves allocation scope.
       if (use->hasTrait<OpTrait::ReturnLike>() &&
           use->getParentRegion() == parentRegion)
         return true;
     }
   }
   return false;
 }
 
 /// Checks, if an automated allocation scope for a given alloc value exists.
 static bool hasAllocationScope(Value alloc,
-                               const BufferAliasAnalysis &aliasAnalysis) {
+                               const BufferDependencyAnalysis &aliasAnalysis) {
   Region *region = alloc.getParentRegion();
   do {
     if (Operation *parentOp = region->getParentOp()) {
       // Check if the operation is an automatic allocation scope and whether an
       // alias leaves the scope. This means, an allocation yields out of
       // this scope and can not be transformed in a stack-based allocation.
       if (parentOp->hasTrait<OpTrait::AutomaticAllocationScope>() &&
           !leavesAllocationScope(region, aliasAnalysis.resolve(alloc)))

 /// Promotes heap-based allocations to stack-based allocations (if possible).
 class BufferPlacementPromotion : BufferPlacementTransformationBase {
 public:
   BufferPlacementPromotion(Operation *op)
       : BufferPlacementTransformationBase(op) {}
 
   /// Promote buffers to stack-based allocations.
   void promote(function_ref<bool(Value)> isSmallAlloc) {
+    llvm::SmallVector<Operation *> toErase;
     for (BufferPlacementAllocs::AllocEntry &entry : allocs) {
       Value alloc = std::get<0>(entry);
       Operation *dealloc = std::get<1>(entry);
       // Checking several requirements to transform an AllocOp into an AllocaOp.
       // The transformation is done if the allocation is limited to a given
       // size. Furthermore, a deallocation must not be defined for this
       // allocation entry and a parent allocation scope must exist.
       if (!isSmallAlloc(alloc) || dealloc ||
           !hasAllocationScope(alloc, aliases))
         continue;
 
       Operation *startOperation = BufferPlacementAllocs::getStartOperation(
           alloc, alloc.getParentBlock(), liveness);
       // Build a new alloca that is associated with its parent
       // `AutomaticAllocationScope` determined during the initialization phase.
       OpBuilder builder(startOperation);
       Operation *allocOp = alloc.getDefiningOp();
       Operation *alloca = builder.create<memref::AllocaOp>(
           alloc.getLoc(), alloc.getType().cast<MemRefType>(),
           allocOp->getOperands());
 
       // Replace the original alloc by a newly created alloca.
       allocOp->replaceAllUsesWith(alloca);
-      allocOp->erase();
+      toErase.push_back(allocOp);
     }
+    for (auto *allocOp : toErase)
+      allocOp->erase();
   }
 };
 
 //===----------------------------------------------------------------------===//
 // BufferOptimizationPasses
 //===----------------------------------------------------------------------===//
 
 /// The buffer hoisting pass that hoists allocation nodes into dominating