[mlir][Affine] Move/expose hasNoInterveningEffect

[makslevental]

Summary

I would like to expose Dialect/Affine/Utils/Utils.cpp#hasNoInterveningEffect for downstream use (particular use case is a lazy implementation of forwardStoreToLoad in CIRCT). This exposes hasNoInterveningEffect and instantiates for the necessary types.

[bondhugula]

I think we shouldn't put so much C++ code in the headers. Just leave these in the C++ file and explicitly instantiate right below (in the C++ file) for the necessary memOp types.

[makslevental]

In D134374#3809493, @bondhugula wrote:

I think we shouldn't put so much C++ code in the headers. Just leave these in the C++ file and explicitly instantiate right below (in the C++ file) for the necessary memOp types.

I've made the changes as I think you intended (I might be wrong). I've also tested with the downstream code (so this formulation is suitable for my needs).

[bondhugula]

mlir/include/mlir/Dialect/Affine/Utils.h

323

The doc comment should come here since this method has been exposed.

mlir/lib/Dialect/Affine/Utils/Utils.cpp

660

Move doc comment to the declaration.

mlir/include/mlir/Dialect/Affine/Utils.h

 #ifndef MLIR_DIALECT_AFFINE_UTILS_H
 #define MLIR_DIALECT_AFFINE_UTILS_H
 
+#include <mlir/Dialect/Affine/Analysis/AffineStructures.h>
 #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
+#include "mlir/Dialect/Affine/Analysis/Utils.h"
+#include "mlir/Dialect/Affine/IR/AffineOps.h"
+#include "llvm/ADT/SmallPtrSet.h"
 
 namespace mlir {
 

                                                Value linearIndex,
                                                ArrayRef<Value> basis);
 
+/// Ensure that all operations that could be executed after `start`
+/// (noninclusive) and prior to `memOp` (e.g. on a control flow/op path
+/// between the operations) do not have the potential memory effect
+/// `EffectType` on `memOp`. `memOp`  is an operation that reads or writes to
+/// a memref. For example, if `EffectType` is MemoryEffects::Write, this method
+/// will check if there is no write to the memory between `start` and `memOp`
+/// that would change the read within `memOp`.
+template <typename EffectType, typename T>
+bool hasNoInterveningEffect(Operation *start, T memOp) {
+  auto isLocallyAllocated = [](Value memref) {
+    auto *defOp = memref.getDefiningOp();
+    return defOp && hasSingleEffect<MemoryEffects::Allocate>(defOp, memref);
+  };
+
+  // A boolean representing whether an intervening operation could have impacted
+  // memOp.
+  bool hasSideEffect = false;
+
+  // Check whether the effect on memOp can be caused by a given operation op.
+  Value memref = memOp.getMemRef();
+  std::function<void(Operation *)> checkOperation = [&](Operation *op) {
+    // If the effect has alreay been found, early exit,
+    if (hasSideEffect)
+      return;
+
+    if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
+      SmallVector<MemoryEffects::EffectInstance, 1> effects;
+      memEffect.getEffects(effects);
+
+      bool opMayHaveEffect = false;
+      for (auto effect : effects) {
+        // If op causes EffectType on a potentially aliasing location for
+        // memOp, mark as having the effect.
+        if (isa<EffectType>(effect.getEffect())) {
+          // TODO: This should be replaced with a check for no aliasing.
+          // Aliasing information should be passed to this method.
+          if (effect.getValue() && effect.getValue() != memref &&
+              isLocallyAllocated(memref) &&
+              isLocallyAllocated(effect.getValue()))
+            continue;
+          opMayHaveEffect = true;
+          break;
+        }
+      }
+
+      if (!opMayHaveEffect)
+        return;
+
+      // If the side effect comes from an affine read or write, try to
+      // prove the side effecting `op` cannot reach `memOp`.
+      if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
+        MemRefAccess srcAccess(op);
+        MemRefAccess destAccess(memOp);
+        // Affine dependence analysis here is applicable only if both ops
+        // operate on the same memref and if `op`, `memOp`, and `start` are in
+        // the same AffineScope.
+        if (srcAccess.memref == destAccess.memref &&
+            getAffineScope(op) == getAffineScope(memOp) &&
+            getAffineScope(op) == getAffineScope(start)) {
+          // Number of loops containing the start op and the ending operation.
+          unsigned minSurroundingLoops =
+              getNumCommonSurroundingLoops(*start, *memOp);
+
+          // Number of loops containing the operation `op` which has the
+          // potential memory side effect and can occur on a path between
+          // `start` and `memOp`.
+          unsigned nsLoops = getNumCommonSurroundingLoops(*op, *memOp);
+
+          // For ease, let's consider the case that `op` is a store and we're
+          // looking for other potential stores (e.g `op`) that overwrite memory
+          // after `start`, and before being read in `memOp`. In this case, we
+          // only need to consider other potential stores with depth >
+          // minSurrounding loops since `start` would overwrite any store with a
+          // smaller number of surrounding loops before.
+          unsigned d;
+          FlatAffineValueConstraints dependenceConstraints;
+          for (d = nsLoops + 1; d > minSurroundingLoops; d--) {
+            DependenceResult result = checkMemrefAccessDependence(
+                srcAccess, destAccess, d, &dependenceConstraints,
+                /*dependenceComponents=*/nullptr);
+            // A dependence failure or the presence of a dependence implies a
+            // side effect.
+            if (!noDependence(result)) {
+              hasSideEffect = true;
+              return;
+            }
+          }
+
+          // No side effect was seen, simply return.
+          return;
+        }
+        // TODO: Check here if the memrefs alias: there is no side effect if
+        // `srcAccess.memref` and `destAccess.memref` don't alias.
+      }
+      // We have an op with a memory effect and we cannot prove if it
+      // intervenes.
+      hasSideEffect = true;
+      return;
+    }
+
+    if (op->hasTrait<OpTrait::HasRecursiveSideEffects>()) {
+      // Recurse into the regions for this op and check whether the internal
+      // operations may have the side effect `EffectType` on memOp.
+      for (Region &region : op->getRegions())
+        for (Block &block : region)
+          for (Operation &op : block)
+            checkOperation(&op);
+      return;
+    }
+
+    // Otherwise, conservatively assume generic operations have the effect
+    // on the operation
+    hasSideEffect = true;
+  };
+
+  // Check all paths from ancestor op `parent` to the operation `to` for the
+  // effect. It is known that `to` must be contained within `parent`.
+  auto until = [&](Operation *parent, Operation *to) {
+    // TODO check only the paths from `parent` to `to`.
+    // Currently we fallback and check the entire parent op, rather than
+    // just the paths from the parent path, stopping after reaching `to`.
+    // This is conservatively correct, but could be made more aggressive.
+    assert(parent->isAncestor(to));
+    checkOperation(parent);
+  };
+
+  // Check for all paths from operation `from` to operation `untilOp` for the
+  // given memory effect.
+  std::function<void(Operation *, Operation *)> recur =
+      [&](Operation *from, Operation *untilOp) {
+        assert(
+            from->getParentRegion()->isAncestor(untilOp->getParentRegion()) &&
+                "Checking for side effect between two operations without a common "
+                "ancestor");
+
+        // If the operations are in different regions, recursively consider all
+        // path from `from` to the parent of `to` and all paths from the parent
+        // of `to` to `to`.
+        if (from->getParentRegion() != untilOp->getParentRegion()) {
+          recur(from, untilOp->getParentOp());
+          until(untilOp->getParentOp(), untilOp);
+          return;
+        }
+
+        // Now, assuming that `from` and `to` exist in the same region, perform
+        // a CFG traversal to check all the relevant operations.
+
+        // Additional blocks to consider.
+        SmallVector<Block *, 2> todoBlocks;
+        {
+          // First consider the parent block of `from` an check all operations
+          // after `from`.
+          for (auto iter = ++from->getIterator(), end = from->getBlock()->end();
+               iter != end && &*iter != untilOp; ++iter) {
+            checkOperation(&*iter);
+          }
+
+          // If the parent of `from` doesn't contain `to`, add the successors
+          // to the list of blocks to check.
+          if (untilOp->getBlock() != from->getBlock())
+            for (Block *succ : from->getBlock()->getSuccessors())
+              todoBlocks.push_back(succ);
+        }
+
+        SmallPtrSet<Block *, 4> done;
+        // Traverse the CFG until hitting `to`.
+        while (!todoBlocks.empty()) {
+          Block *blk = todoBlocks.pop_back_val();
+          if (done.count(blk))
+            continue;
+          done.insert(blk);
+          for (auto &op : *blk) {
+            if (&op == untilOp)
+              break;
+            checkOperation(&op);
+            if (&op == blk->getTerminator())
+              for (Block *succ : blk->getSuccessors())
+                todoBlocks.push_back(succ);
+          }
+        }
+      };
+  recur(start, memOp);
+  return !hasSideEffect;
+}
+
 } // namespace mlir
 
 #endif // MLIR_DIALECT_AFFINE_UTILS_H

mlir/lib/Dialect/Affine/Utils/Utils.cpp

   return success();
 }
 
-/// Ensure that all operations that could be executed after `start`
-/// (noninclusive) and prior to `memOp` (e.g. on a control flow/op path
-/// between the operations) do not have the potential memory effect
-/// `EffectType` on `memOp`. `memOp`  is an operation that reads or writes to
-/// a memref. For example, if `EffectType` is MemoryEffects::Write, this method
-/// will check if there is no write to the memory between `start` and `memOp`
-/// that would change the read within `memOp`.
-template <typename EffectType, typename T>
-static bool hasNoInterveningEffect(Operation *start, T memOp) {
-  auto isLocallyAllocated = [](Value memref) {
-    auto *defOp = memref.getDefiningOp();
-    return defOp && hasSingleEffect<MemoryEffects::Allocate>(defOp, memref);
-  };
-
-  // A boolean representing whether an intervening operation could have impacted
-  // memOp.
-  bool hasSideEffect = false;
-
-  // Check whether the effect on memOp can be caused by a given operation op.
-  Value memref = memOp.getMemRef();
-  std::function<void(Operation *)> checkOperation = [&](Operation *op) {
-    // If the effect has alreay been found, early exit,
-    if (hasSideEffect)
-      return;
-
-    if (auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
-      SmallVector<MemoryEffects::EffectInstance, 1> effects;
-      memEffect.getEffects(effects);
-
-      bool opMayHaveEffect = false;
-      for (auto effect : effects) {
-        // If op causes EffectType on a potentially aliasing location for
-        // memOp, mark as having the effect.
-        if (isa<EffectType>(effect.getEffect())) {
-          // TODO: This should be replaced with a check for no aliasing.
-          // Aliasing information should be passed to this method.
-          if (effect.getValue() && effect.getValue() != memref &&
-              isLocallyAllocated(memref) &&
-              isLocallyAllocated(effect.getValue()))
-            continue;
-          opMayHaveEffect = true;
-          break;
-        }
-      }
-
-      if (!opMayHaveEffect)
-        return;
-
-      // If the side effect comes from an affine read or write, try to
-      // prove the side effecting `op` cannot reach `memOp`.
-      if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
-        MemRefAccess srcAccess(op);
-        MemRefAccess destAccess(memOp);
-        // Affine dependence analysis here is applicable only if both ops
-        // operate on the same memref and if `op`, `memOp`, and `start` are in
-        // the same AffineScope.
-        if (srcAccess.memref == destAccess.memref &&
-            getAffineScope(op) == getAffineScope(memOp) &&
-            getAffineScope(op) == getAffineScope(start)) {
-          // Number of loops containing the start op and the ending operation.
-          unsigned minSurroundingLoops =
-              getNumCommonSurroundingLoops(*start, *memOp);
-
-          // Number of loops containing the operation `op` which has the
-          // potential memory side effect and can occur on a path between
-          // `start` and `memOp`.
-          unsigned nsLoops = getNumCommonSurroundingLoops(*op, *memOp);
-
-          // For ease, let's consider the case that `op` is a store and we're
-          // looking for other potential stores (e.g `op`) that overwrite memory
-          // after `start`, and before being read in `memOp`. In this case, we
-          // only need to consider other potential stores with depth >
-          // minSurrounding loops since `start` would overwrite any store with a
-          // smaller number of surrounding loops before.
-          unsigned d;
-          FlatAffineValueConstraints dependenceConstraints;
-          for (d = nsLoops + 1; d > minSurroundingLoops; d--) {
-            DependenceResult result = checkMemrefAccessDependence(
-                srcAccess, destAccess, d, &dependenceConstraints,
-                /*dependenceComponents=*/nullptr);
-            // A dependence failure or the presence of a dependence implies a
-            // side effect.
-            if (!noDependence(result)) {
-              hasSideEffect = true;
-              return;
-            }
-          }
-
-          // No side effect was seen, simply return.
-          return;
-        }
-        // TODO: Check here if the memrefs alias: there is no side effect if
-        // `srcAccess.memref` and `destAccess.memref` don't alias.
-      }
-      // We have an op with a memory effect and we cannot prove if it
-      // intervenes.
-      hasSideEffect = true;
-      return;
-    }
-
-    if (op->hasTrait<OpTrait::HasRecursiveSideEffects>()) {
-      // Recurse into the regions for this op and check whether the internal
-      // operations may have the side effect `EffectType` on memOp.
-      for (Region &region : op->getRegions())
-        for (Block &block : region)
-          for (Operation &op : block)
-            checkOperation(&op);
-      return;
-    }
-
-    // Otherwise, conservatively assume generic operations have the effect
-    // on the operation
-    hasSideEffect = true;
-  };
-
-  // Check all paths from ancestor op `parent` to the operation `to` for the
-  // effect. It is known that `to` must be contained within `parent`.
-  auto until = [&](Operation *parent, Operation *to) {
-    // TODO check only the paths from `parent` to `to`.
-    // Currently we fallback and check the entire parent op, rather than
-    // just the paths from the parent path, stopping after reaching `to`.
-    // This is conservatively correct, but could be made more aggressive.
-    assert(parent->isAncestor(to));
-    checkOperation(parent);
-  };
-
-  // Check for all paths from operation `from` to operation `untilOp` for the
-  // given memory effect.
-  std::function<void(Operation *, Operation *)> recur =
-      [&](Operation *from, Operation *untilOp) {
-        assert(
-            from->getParentRegion()->isAncestor(untilOp->getParentRegion()) &&
-            "Checking for side effect between two operations without a common "
-            "ancestor");
-
-        // If the operations are in different regions, recursively consider all
-        // path from `from` to the parent of `to` and all paths from the parent
-        // of `to` to `to`.
-        if (from->getParentRegion() != untilOp->getParentRegion()) {
-          recur(from, untilOp->getParentOp());
-          until(untilOp->getParentOp(), untilOp);
-          return;
-        }
-
-        // Now, assuming that `from` and `to` exist in the same region, perform
-        // a CFG traversal to check all the relevant operations.
-
-        // Additional blocks to consider.
-        SmallVector<Block *, 2> todoBlocks;
-        {
-          // First consider the parent block of `from` an check all operations
-          // after `from`.
-          for (auto iter = ++from->getIterator(), end = from->getBlock()->end();
-               iter != end && &*iter != untilOp; ++iter) {
-            checkOperation(&*iter);
-          }
-
-          // If the parent of `from` doesn't contain `to`, add the successors
-          // to the list of blocks to check.
-          if (untilOp->getBlock() != from->getBlock())
-            for (Block *succ : from->getBlock()->getSuccessors())
-              todoBlocks.push_back(succ);
-        }
-
-        SmallPtrSet<Block *, 4> done;
-        // Traverse the CFG until hitting `to`.
-        while (!todoBlocks.empty()) {
-          Block *blk = todoBlocks.pop_back_val();
-          if (done.count(blk))
-            continue;
-          done.insert(blk);
-          for (auto &op : *blk) {
-            if (&op == untilOp)
-              break;
-            checkOperation(&op);
-            if (&op == blk->getTerminator())
-              for (Block *succ : blk->getSuccessors())
-                todoBlocks.push_back(succ);
-          }
-        }
-      };
-  recur(start, memOp);
-  return !hasSideEffect;
-}
-
 /// Attempt to eliminate loadOp by replacing it with a value stored into memory
 /// which the load is guaranteed to retrieve. This check involves three
 /// components: 1) The store and load must be on the same location 2) The store