[MLIR][Affine] Add utility to check if the slice is valid

[vinayaka-polymage]

Summary

Fixes a bug in affine fusion pipeline where an incorrect slice is computed.
After the slice computation is done, original domain of the the source is
compared with the new domain that will result if the fusion succeeds. If the
new domain must be a subset of the original domain for the slice to be
valid. If the slice computed is incorrect, fusion based on such a slice is
avoided.

Relevant test cases are added/edited.

Fixes https://bugs.llvm.org/show_bug.cgi?id=49203

[vinayaka-polymage]

If this change/approach is acceptable, we can also change ComputationSliceState::isMaximal() to use the set difference the other way (source - slice), reusing these computations.

[dcaballe]

Thanks for fixing this bug, Vinayaka! The direction looks good to me. Adding some comments.

If this change/approach is acceptable, we can also change ComputationSliceState::isMaximal() to use the set difference the other way (source - slice), reusing these computations.

That sounds great! We could refactor the code to utilities that would serve both cases, depending on the order of the inputs. I wonder if the fast checks that we introduced for isMaximal (isSliceMaximalFastCheck) would also be applicable to isSliceValid. If so, we should be able to refactor all the code!

mlir/lib/Analysis/Utils.cpp

68

please, add message to the assert.

215

My English probably falls short here :). For my education, is determinastically ok? or should it be deterministically?

220

This looks good to me! For the isMaximal method we implemented a fast check (isSliceMaximalFastCheck) to avoid the Presburger computation for trivial cases, since it's very expensive. The fast check ended up covering the vast majority of the cases. Could we please do something similar here?

254

Could you please also dump a small comment before each constraint set so that we can easily identify them?

961

nit: drop braces

mlir/lib/Transforms/Utils/LoopFusionUtils.cpp

531

is there an API to check this instead of creating a null AffineMap? Maybe !map?

mlir/test/Transforms/loop-fusion-slice-computation.mlir

70

These remarks are no longer needed because we now bail out before they are emitted? Would it possible to emit a new remark for cases where the slice is invalid and update the remarks instead of removing them?

mlir/test/Transforms/loop-fusion.mlir

3083

Adding a comment about what is the resulting slice and why is invalid would be very useful.

[sgrechanik]

mlir/lib/Analysis/Utils.cpp

960

Shouldn't we conservatively assume that the slice is invalid if we cannot determine if it's valid here (and return failure())?

[vinayaka-polymage]

Addressing easy comments and suggestions, some important ones
still pending.

[vinayaka-polymage]

Thanks for the review and suggestions !! I have completed the easy ones, and I will continue exploring the pending ones.

mlir/lib/Analysis/Utils.cpp

215

Your English is fine, bad typo by me :) Corrected.

220

That is crucial, thanks for pointing it out. I will definitely explore this.

960

This is an important comment, thanks for bringing this up. I have added as comments on why I went this way. But I would like to hear your and others' thoughts on this.
@bondhugula @dcaballe

mlir/test/Transforms/loop-fusion-slice-computation.mlir

70

Definitely makes sense. I will explore this.

mlir/test/Transforms/loop-fusion.mlir

3083

I have added descriptive comments as you suggested. Please review if this looks OK ?

[dcaballe]

mlir/lib/Analysis/Utils.cpp

960

Do we have many fusion tests that wouldn't be fused if we returned failure? Maybe the fast checks could also help reduce the impact on tests that wouldn't be fused and we could be more conservative here and return failure?

[vinayaka-polymage]

mlir/lib/Analysis/Utils.cpp

960

About the first question:
In loop-fusion.mlir, test case @fuse_symbolic_bounds is an example that would fail. It currently results in fusion when -affine-loop-fusion=fusion-maximal is used. I think, this is because fusion profit computing utilities do not work with symbolic bounds well either.
About the second suggestion:
Yes, fast checks should be designed keeping such cases in mind. Then, returning failure in undetermined cases makes sense.

[bondhugula]

mlir/lib/Analysis/Utils.cpp

220

Agree with @dcaballe here. It's key to have a fast check for the simpler cases which are going to be a vast majority. Being an upstream pass, speed is quite important here. One can of course later create versions that handle more complex/advanced cases as needed but those may not be on the default/standard path/pass.

[bondhugula]

Some minor comments.

mlir/include/mlir/Analysis/Utils.h

95–99

All of these should have been triple /// comments. I believe doxygen won't pick them up otherwise.

119

Likewise.

mlir/lib/Analysis/Utils.cpp

959

undetermined -> indeterminate

[vinayaka-polymage]

Added back the slice computation remarks in tests, marked them incorrect slices.
Added a fast check, reused the utility - isSliceMaximalFastCheck.

[vinayaka-polymage]

I have addressed the remaining comments:

1. Instead of not printing the slice at all if it is incorrect, this change prints them but with a remark : "Incorrect slice" during testing.
2. Fast check is being done, and is reusing the bounds checking utility function isSliceMaximalFastCheck. I have verified that with today's test file loop-fusion.mlir, of 156 calls to isSliceValid, 107 calls are returned after the this fast check itself.

Please review.

mlir/lib/Analysis/Utils.cpp

220

Done. Reused fast check isSliceMaximalFastCheck that verifies slice and destination bounds.

960

This is done.

mlir/test/Transforms/loop-fusion-slice-computation.mlir

70

New remarks added.

[bondhugula]

Looks great with the fast check. Relatively minor comments.

mlir/include/mlir/Analysis/Utils.h

57

exit statuses -> result statuses?

99

MLIR later changed to pass by reference for output parameters if the parameters are never going to be null. So, FlatAffineConstraints &cst. Some of the older methods are only updated when they are touched again.

124

Nit: slice -> the slice

128

This TODO has already been addressed?

mlir/lib/Analysis/AffineStructures.cpp

2132

that the source loop

2141

No else after return. Please see the auto warnings.

mlir/lib/Analysis/Utils.cpp

67

Pass by reference.

231

return true;

242

Nit: > 0

[vinayaka-polymage]

Addressing recent comments, minor.

[vinayaka-polymage]

Addressing minor comments.

[vinayaka-polymage]

Recent suggestions incorporated. I have asked for clarification on one comment.

mlir/lib/Analysis/AffineStructures.cpp

2141

This else is functional, and cannot be removed because of the nesting, right ?

[bondhugula]

mlir/lib/Analysis/AffineStructures.cpp

2141

Sorry, I missed that.

mlir/include/mlir/Analysis/Utils.h

 /// surrounding this operation.
 unsigned getNestingDepth(Operation *op);
 
 /// Returns in 'sequentialLoops' all sequential loops in loop nest rooted
 /// at 'forOp'.
 void getSequentialLoops(AffineForOp forOp,
                         llvm::SmallDenseSet<Value, 8> *sequentialLoops);
 
+/// Enumerates different result statuses of slice computation by
+/// `computeSliceUnion`
+// TODO: Identify and add different kinds of failures during slice computation.
+struct SliceComputationResult {
+  enum ResultEnum {
+    Success,
+    IncorrectSliceFailure, // Slice is computed, but it is incorrect.
+    GenericFailure,        // Unable to compute src loop computation slice.
+  } value;
+  SliceComputationResult(ResultEnum v) : value(v) {}
+};
+
 /// ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their
 /// associated operands for a set of loops within a loop nest (typically the
 /// set of loops surrounding a store operation). Loop bound AffineMaps which
 /// are non-null represent slices of that loop's iteration space.
 struct ComputationSliceState {
   // List of sliced loop IVs (ordered from outermost to innermost).
   // EX: 'ivs[i]' has lower bound 'lbs[i]' and upper bound 'ubs[i]'.
   SmallVector<Value, 4> ivs;
struct ComputationSliceState {
   // Adds to 'cst' with constraints which represent the slice bounds on 'ivs'
   // in 'this'. Specifically, the values in 'ivs' are added to 'cst' as dim
   // identifiers and the values in 'lb/ubOperands' are added as symbols.
   // Constraints are added for all loop IV bounds (dim or symbol), and
   // constraints are added for slice bounds in 'lbs'/'ubs'.
   // Returns failure if we cannot add loop bounds because of unsupported cases.
   LogicalResult getAsConstraints(FlatAffineConstraints *cst);
 
+  /// Adds to 'cst' constraints which represent the original loop bounds on
+  /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest
+  /// from which the slice is being computed. Returns failure if we cannot add
+  /// loop bounds because of unsupported cases.
+  LogicalResult getSourceAsConstraints(FlatAffineConstraints &cst);
+
   // Clears all bounds and operands in slice state.
   void clearBounds();
 
   /// Returns true if the computation slice is empty.
   bool isEmpty() const { return ivs.empty(); }
 
   /// Returns true if the computation slice encloses all the iterations of the
   /// sliced loop nest. Returns false if it does not. Returns llvm::None if it
   /// cannot determine if the slice is maximal or not.
   // TODO: Cache 'isMaximal' so that we don't recompute it when the slice
   // information hasn't changed.
   Optional<bool> isMaximal() const;
 
+  /// Checks the validity of the slice computed. This is done using the
+  /// following steps:
+  /// 1. Get the new domain of the slice that would be created if fusion
+  /// succeeds. This domain gets constructed with source loop IVS and
+  /// destination loop IVS as dimensions.
+  /// 2. Project out the dimensions of the destination loop from the domain
+  /// above calculated in step(1) to express it purely in terms of the source
+  /// loop IVs.
+  /// 3. Calculate a set difference between the iterations of the new domain and
+  /// the original domain of the source loop.
+  /// If this difference is empty, the slice is declared to be valid. Otherwise,
+  /// return false as it implies that the effective fusion results in at least
+  /// one iteration of the slice that was not originally in the source's domain.
+  /// If the validity cannot be determined, returns llvm:None.
+  Optional<bool> isSliceValid();
+
   void dump() const;
 
 private:
   /// Fast check to determine if the computation slice is maximal. Returns true
   /// if each slice dimension maps to an existing dst dimension and both the src
   /// and the dst loops for those dimensions have the same bounds. Returns false
   /// if both the src and the dst loops don't have the same bounds. Returns
   /// llvm::None if none of the above can be proven.

 //    }
 //
 void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp,
                               FlatAffineConstraints *dependenceConstraints,
                               unsigned loopDepth, bool isBackwardSlice,
                               ComputationSliceState *sliceState);
 
 /// Computes in 'sliceUnion' the union of all slice bounds computed at
-/// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB'.
-/// The parameter 'numCommonLoops' is the number of loops common to the
-/// operations in 'opsA' and 'opsB'.
-/// If 'isBackwardSlice' is true, computes slice bounds for loop nest
-/// surrounding ops in 'opsA', as a function of IVs and symbols of loop nest
-/// surrounding ops in 'opsB' at 'loopDepth'.
-/// If 'isBackwardSlice' is false, computes slice bounds for loop nest
-/// surrounding ops in 'opsB', as a function of IVs and symbols of loop nest
-/// surrounding ops in 'opsA' at 'loopDepth'.
-/// Returns 'success' if union was computed, 'failure' otherwise.
+/// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
+/// then verifies if it is valid. The parameter 'numCommonLoops' is the number
+/// of loops common to the operations in 'opsA' and 'opsB'. If 'isBackwardSlice'
+/// is true, computes slice bounds for loop nest surrounding ops in 'opsA', as a
+/// function of IVs and symbols of loop nest surrounding ops in 'opsB' at
+/// 'loopDepth'. If 'isBackwardSlice' is false, computes slice bounds for loop
+/// nest surrounding ops in 'opsB', as a function of IVs and symbols of loop
+/// nest surrounding ops in 'opsA' at 'loopDepth'. Returns
+/// 'SliceComputationResult::Success' if union was computed correctly, an
+/// appropriate 'failure' otherwise.
 // TODO: Change this API to take 'forOpA'/'forOpB'.
-LogicalResult computeSliceUnion(ArrayRef<Operation *> opsA,
-                                ArrayRef<Operation *> opsB, unsigned loopDepth,
-                                unsigned numCommonLoops, bool isBackwardSlice,
-                                ComputationSliceState *sliceUnion);
+SliceComputationResult
+computeSliceUnion(ArrayRef<Operation *> opsA, ArrayRef<Operation *> opsB,
+                  unsigned loopDepth, unsigned numCommonLoops,
+                  bool isBackwardSlice, ComputationSliceState *sliceUnion);
 
 /// Creates a clone of the computation contained in the loop nest surrounding
 /// 'srcOpInst', slices the iteration space of src loop based on slice bounds
 /// in 'sliceState', and inserts the computation slice at the beginning of the
 /// operation block of the loop at 'dstLoopDepth' in the loop nest surrounding
 /// 'dstOpInst'. Returns the top-level loop of the computation slice on
 /// success, returns nullptr otherwise.
 // Loop depth is a crucial optimization choice that determines where to

mlir/include/mlir/Transforms/LoopFusionUtils.h

 
 struct FusionResult {
   enum ResultEnum {
     Success,
     FailPrecondition,     // Failed precondition for fusion. (e.g. same block).
     FailBlockDependence,  // Fusion would violate another dependence in block.
     FailFusionDependence, // Fusion would reverse dependences between loops.
     FailComputationSlice, // Unable to compute src loop computation slice.
+    FailIncorrectSlice,   // Slice is computed, but it is incorrect.
   } value;
   FusionResult(ResultEnum v) : value(v) {}
 };
 
 /// Describes the fusion strategy to be used in the Affine loop fusion
 /// utilities. Currently, it is used to specialized the loop fusion utilities
 /// with the assumptions made in the AffineLoopFusion pass for producer-consumer
 /// and sibling fusion, while sharing a single implementation. The latter

mlir/lib/Analysis/AffineStructures.cpp

if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
         ubMap.getNumResults() == 1 &&
         lbMap.getResult(0) + 1 == ubMap.getResult(0)) {
       if (failed(addLowerOrUpperBound(pos, lbMap, operands, /*eq=*/true,
                                       /*lower=*/true)))
         return failure();
       continue;
     }
 
-    if (lbMap && failed(addLowerOrUpperBound(pos, lbMap, operands, /*eq=*/false,
-                                             /*lower=*/true)))
+    // If lower or upper bound maps are null or provide no results, it implies
+    // that the source loop was not at all sliced, and the entire loop will be a
+    // part of the slice.
+    if (lbMap && lbMap.getNumResults() != 0 && ubMap &&
+        ubMap.getNumResults() != 0) {
+      if (failed(addLowerOrUpperBound(pos, lbMap, operands, /*eq=*/false,
         return failure();
-
-    if (ubMap && failed(addLowerOrUpperBound(pos, ubMap, operands, /*eq=*/false,
-                                             /*lower=*/false)))
+      if (failed(addLowerOrUpperBound(pos, ubMap, operands, /*eq=*/false,
         return failure();
+    } else {
+      auto loop = getForInductionVarOwner(values[i]);
+      if (failed(this->addAffineForOpDomain(loop)))
+        return failure();
+    }
   }
   return success();
 }
 
 void FlatAffineConstraints::addEquality(ArrayRef<int64_t> eq) {
   assert(eq.size() == getNumCols());
   unsigned offset = equalities.size();
   equalities.resize(equalities.size() + numReservedCols);

mlir/lib/Analysis/Utils.cpp

void mlir::getEnclosingAffineForAndIfOps(Operation &op,
   // operations.
   while (currOp && (isa<AffineIfOp, AffineForOp>(currOp))) {
     ops->push_back(currOp);
     currOp = currOp->getParentOp();
   }
   std::reverse(ops->begin(), ops->end());
 }
 
+// Populates 'cst' with FlatAffineConstraints which represent original domain of
+// the loop bounds that define 'ivs'.
+LogicalResult
+ComputationSliceState::getSourceAsConstraints(FlatAffineConstraints &cst) {
+  assert(!ivs.empty() && "Cannot have a slice without its IVs");
+  cst.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0, /*numLocals=*/0, ivs);
+  for (Value iv : ivs) {
+    AffineForOp loop = getForInductionVarOwner(iv);
+    assert(loop && "Expected affine for");
+    if (failed(cst.addAffineForOpDomain(loop)))
+      return failure();
+  }
+  return success();
+}
+
 // Populates 'cst' with FlatAffineConstraints which represent slice bounds.
 LogicalResult
 ComputationSliceState::getAsConstraints(FlatAffineConstraints *cst) {
   assert(!lbOperands.empty());
   // Adds src 'ivs' as dimension identifiers in 'cst'.
   unsigned numDims = ivs.size();
   // Adds operands (dst ivs and symbols) as symbols in 'cst'.
   unsigned numSymbols = lbOperands[0].size();
 
   SmallVector<Value, 4> values(ivs);
   // Append 'ivs' then 'operands' to 'values'.
   values.append(lbOperands[0].begin(), lbOperands[0].end());
   cst->reset(numDims, numSymbols, 0, values);
 
-  // Add loop bound constraints for values which are loop IVs and equality
-  // constraints for symbols which are constants.
-  for (const auto &value : values) {
+  // Add loop bound constraints for values which are loop IVs of the destination
+  // of fusion and equality constraints for symbols which are constants.
+  for (unsigned i = numDims, end = values.size(); i < end; ++i) {
+    Value value = values[i];
     assert(cst->containsId(value) && "value expected to be present");
     if (isValidSymbol(value)) {
       // Check if the symbol is a constant.
       if (auto cOp = value.getDefiningOp<ConstantIndexOp>())
         cst->setIdToConstant(value, cOp.getValue());
     } else if (auto loop = getForInductionVarOwner(value)) {
       if (failed(cst->addAffineForOpDomain(loop)))
         return failure();
for (unsigned i = 0, end = lbs.size(); i < end; ++i) {
     // that the slice is not maximal.
     if (srcLbResult != dstLbResult || srcUbResult != dstUbResult)
       return false;
   }
 
   return true;
 }
 
+/// Returns true if it is deterministically verified that the original iteration
+/// space of the slice is contained within the new iteration space that is
+/// created after fusing 'this' slice into its destination.
+Optional<bool> ComputationSliceState::isSliceValid() {
+  // Fast check to determine if the slice is valid. If the following conditions
+  // are verified to be true, slice is declared valid by the fast check:
+  // 1. Each slice loop is a single iteration loop bound in terms of a single
+  //    destination loop IV.
+  // 2. Loop bounds of the destination loop IV (from above) and those of the
+  //    source loop IV are exactly the same.
+  // If the fast check is inconclusive or false, we proceed with a more
+  // expensive analysis.
+  // TODO: Store the result of the fast check, as it might be used again in
+  // `canRemoveSrcNodeAfterFusion`.
+  Optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
+  if (isValidFastCheck.hasValue() && isValidFastCheck.getValue())
+    return true;
+
+  // Create constraints for the source loop nest using which slice is computed.
+  FlatAffineConstraints srcConstraints;
+  // TODO: Store the source's domain to avoid computation at each depth.
+  if (failed(getSourceAsConstraints(srcConstraints))) {
+    LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n");
+    return llvm::None;
+  }
+  // As the set difference utility currently cannot handle symbols in its
+  // operands, validity of the slice cannot be determined.
+  if (srcConstraints.getNumSymbolIds() > 0) {
+    LLVM_DEBUG(llvm::dbgs() << "Cannot handle symbols in source domain\n");
+    return llvm::None;
+  }
+  // TODO: Handle local ids in the source domains while using the 'projectOut'
+  // utility below. Currently, aligning is not done assuming that there will be
+  // no local ids in the source domain.
+  if (srcConstraints.getNumLocalIds() != 0) {
+    LLVM_DEBUG(llvm::dbgs() << "Cannot handle locals in source domain\n");
+    return llvm::None;
+  }
+
+  // Create constraints for the slice loop nest that would be created if the
+  // fusion succeeds.
+  FlatAffineConstraints sliceConstraints;
+  if (failed(getAsConstraints(&sliceConstraints))) {
+    LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n");
+    return llvm::None;
+  }
+
+  // Projecting out every dimension other than the 'ivs' to express slice's
+  // domain completely in terms of source's IVs.
+  sliceConstraints.projectOut(ivs.size(),
+                              sliceConstraints.getNumIds() - ivs.size());
+
+  LLVM_DEBUG(llvm::dbgs() << "Domain of the source of the slice:\n");
+  LLVM_DEBUG(srcConstraints.dump());
+  LLVM_DEBUG(llvm::dbgs() << "Domain of the slice if this fusion succeeds "
+                             "(expressed in terms of its source's IVs):\n");
+  LLVM_DEBUG(sliceConstraints.dump());
+
+  // TODO: Store 'srcSet' to avoid recalculating for each depth.
+  PresburgerSet srcSet(srcConstraints);
+  PresburgerSet sliceSet(sliceConstraints);
+  PresburgerSet diffSet = sliceSet.subtract(srcSet);
+
+  if (!diffSet.isIntegerEmpty()) {
+    LLVM_DEBUG(llvm::dbgs() << "Incorrect slice\n");
+    return false;
+  }
+  return true;
+}
+
 /// Returns true if the computation slice encloses all the iterations of the
 /// sliced loop nest. Returns false if it does not. Returns llvm::None if it
 /// cannot determine if the slice is maximal or not.
 Optional<bool> ComputationSliceState::isMaximal() const {
   // Fast check to determine if the computation slice is maximal. If the result
   // is inconclusive, we proceed with a more expensive analysis.
   Optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
   if (isMaximalFastCheck.hasValue())
for (unsigned d = 0; d < loopDepthLimit; ++d) {
     if (surroundingLoops)
       surroundingLoops->push_back(loops[i - 1][d]);
     ++loopDepth;
   }
   return loopDepth;
 }
 
 /// Computes in 'sliceUnion' the union of all slice bounds computed at
-/// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB'.
-/// Returns 'Success' if union was computed, 'failure' otherwise.
-LogicalResult mlir::computeSliceUnion(ArrayRef<Operation *> opsA,
-                                      ArrayRef<Operation *> opsB,
-                                      unsigned loopDepth,
-                                      unsigned numCommonLoops,
-                                      bool isBackwardSlice,
-                                      ComputationSliceState *sliceUnion) {
+/// 'loopDepth' between all dependent pairs of ops in 'opsA' and 'opsB', and
+/// then verifies if it is valid. Returns 'SliceComputationResult::Success' if
+/// union was computed correctly, an appropriate failure otherwise.
+SliceComputationResult
+mlir::computeSliceUnion(ArrayRef<Operation *> opsA, ArrayRef<Operation *> opsB,
+                        unsigned loopDepth, unsigned numCommonLoops,
   // Compute the union of slice bounds between all pairs in 'opsA' and
   // 'opsB' in 'sliceUnionCst'.
   FlatAffineConstraints sliceUnionCst;
   assert(sliceUnionCst.getNumDimAndSymbolIds() == 0);
   std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
   for (unsigned i = 0, numOpsA = opsA.size(); i < numOpsA; ++i) {
     MemRefAccess srcAccess(opsA[i]);
     for (unsigned j = 0, numOpsB = opsB.size(); j < numOpsB; ++j) {
       MemRefAccess dstAccess(opsB[j]);
       if (srcAccess.memref != dstAccess.memref)
         continue;
       // Check if 'loopDepth' exceeds nesting depth of src/dst ops.
       if ((!isBackwardSlice && loopDepth > getNestingDepth(opsA[i])) ||
           (isBackwardSlice && loopDepth > getNestingDepth(opsB[j]))) {
         LLVM_DEBUG(llvm::dbgs() << "Invalid loop depth\n");
-        return failure();
+        return SliceComputationResult::GenericFailure;
       }
 
       bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.opInst) &&
                               isa<AffineReadOpInterface>(dstAccess.opInst);
       FlatAffineConstraints dependenceConstraints;
       // Check dependence between 'srcAccess' and 'dstAccess'.
       DependenceResult result = checkMemrefAccessDependence(
           srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1,
           &dependenceConstraints, /*dependenceComponents=*/nullptr,
           /*allowRAR=*/readReadAccesses);
       if (result.value == DependenceResult::Failure) {
         LLVM_DEBUG(llvm::dbgs() << "Dependence check failed\n");
-        return failure();
+        return SliceComputationResult::GenericFailure;
       }
       if (result.value == DependenceResult::NoDependence)
         continue;
       dependentOpPairs.push_back({opsA[i], opsB[j]});
 
       // Compute slice bounds for 'srcAccess' and 'dstAccess'.
       ComputationSliceState tmpSliceState;
       mlir::getComputationSliceState(opsA[i], opsB[j], &dependenceConstraints,
                                      loopDepth, isBackwardSlice,
                                      &tmpSliceState);
 
       if (sliceUnionCst.getNumDimAndSymbolIds() == 0) {
         // Initialize 'sliceUnionCst' with the bounds computed in previous step.
         if (failed(tmpSliceState.getAsConstraints(&sliceUnionCst))) {
           LLVM_DEBUG(llvm::dbgs()
                      << "Unable to compute slice bound constraints\n");
-          return failure();
+          return SliceComputationResult::GenericFailure;
         }
         assert(sliceUnionCst.getNumDimAndSymbolIds() > 0);
         continue;
       }
 
       // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'.
       FlatAffineConstraints tmpSliceCst;
       if (failed(tmpSliceState.getAsConstraints(&tmpSliceCst))) {
         LLVM_DEBUG(llvm::dbgs()
                    << "Unable to compute slice bound constraints\n");
-        return failure();
+        return SliceComputationResult::GenericFailure;
       }
 
       // Align coordinate spaces of 'sliceUnionCst' and 'tmpSliceCst' if needed.
       if (!sliceUnionCst.areIdsAlignedWithOther(tmpSliceCst)) {
 
         // Pre-constraint id alignment: record loop IVs used in each constraint
         // system.
         SmallPtrSet<Value, 8> sliceUnionIVs;
         for (unsigned k = 0, l = sliceUnionCst.getNumDimIds(); k < l; ++k)
           sliceUnionIVs.insert(sliceUnionCst.getIdValue(k));
         SmallPtrSet<Value, 8> tmpSliceIVs;
         for (unsigned k = 0, l = tmpSliceCst.getNumDimIds(); k < l; ++k)
           tmpSliceIVs.insert(tmpSliceCst.getIdValue(k));
 
         sliceUnionCst.mergeAndAlignIdsWithOther(/*offset=*/0, &tmpSliceCst);
 
         // Post-constraint id alignment: add loop IV bounds missing after
         // id alignment to constraint systems. This can occur if one constraint
         // system uses an loop IV that is not used by the other. The call
         // to unionBoundingBox below expects constraints for each Loop IV, even
         // if they are the unsliced full loop bounds added here.
         if (failed(addMissingLoopIVBounds(sliceUnionIVs, &sliceUnionCst)))
-          return failure();
+          return SliceComputationResult::GenericFailure;
         if (failed(addMissingLoopIVBounds(tmpSliceIVs, &tmpSliceCst)))
-          return failure();
+          return SliceComputationResult::GenericFailure;
       }
       // Compute union bounding box of 'sliceUnionCst' and 'tmpSliceCst'.
       if (sliceUnionCst.getNumLocalIds() > 0 ||
           tmpSliceCst.getNumLocalIds() > 0 ||
           failed(sliceUnionCst.unionBoundingBox(tmpSliceCst))) {
         LLVM_DEBUG(llvm::dbgs()
                    << "Unable to compute union bounding box of slice bounds\n");
-        return failure();
+        return SliceComputationResult::GenericFailure;
       }
     }
   }
 
   // Empty union.
   if (sliceUnionCst.getNumDimAndSymbolIds() == 0)
-    return failure();
+    return SliceComputationResult::GenericFailure;
 
   // Gather loops surrounding ops from loop nest where slice will be inserted.
   SmallVector<Operation *, 4> ops;
   for (auto &dep : dependentOpPairs) {
     ops.push_back(isBackwardSlice ? dep.second : dep.first);
   }
   SmallVector<AffineForOp, 4> surroundingLoops;
   unsigned innermostCommonLoopDepth =
       getInnermostCommonLoopDepth(ops, &surroundingLoops);
   if (loopDepth > innermostCommonLoopDepth) {
     LLVM_DEBUG(llvm::dbgs() << "Exceeds max loop depth\n");
-    return failure();
+    return SliceComputationResult::GenericFailure;
   }
 
   // Store 'numSliceLoopIVs' before converting dst loop IVs to dims.
   unsigned numSliceLoopIVs = sliceUnionCst.getNumDimIds();
 
   // Convert any dst loop IVs which are symbol identifiers to dim identifiers.
   sliceUnionCst.convertLoopIVSymbolsToDims();
   sliceUnion->clearBounds();
sliceUnion->insertPoint =
       isBackwardSlice
           ? surroundingLoops[loopDepth - 1].getBody()->begin()
           : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
 
   // Give each bound its own copy of 'sliceBoundOperands' for subsequent
   // canonicalization.
   sliceUnion->lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
   sliceUnion->ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
-  return success();
+
+  // Check if the slice computed is valid. Return success only if it is verified
+  // that the slice is valid, otherwise return appropriate failure status.
+  Optional<bool> isSliceValid = sliceUnion->isSliceValid();
+  if (!isSliceValid.hasValue()) {
+    LLVM_DEBUG(llvm::dbgs() << "Cannot determine if the slice is valid\n");
+    return SliceComputationResult::GenericFailure;
+  }
+  if (!isSliceValid.getValue())
+    return SliceComputationResult::IncorrectSliceFailure;
+
+  return SliceComputationResult::Success;
 }
 
 const char *const kSliceFusionBarrierAttrName = "slice_fusion_barrier";
 // Computes slice bounds by projecting out any loop IVs from
 // 'dependenceConstraints' at depth greater than 'loopDepth', and computes slice
 // bounds in 'sliceState' which represent the one loop nest's IVs in terms of
 // the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice').
 void mlir::getComputationSliceState(

mlir/lib/Transforms/Utils/LoopFusionUtils.cpp

for (Operation *op : opsA) {
       if (load && load.getMemRef() == fusionStrategy.getSiblingFusionMemRef())
         strategyOpsA.push_back(op);
     }
     break;
   }
 
   // Compute union of computation slices computed between all pairs of ops
   // from 'forOpA' and 'forOpB'.
-  if (failed(mlir::computeSliceUnion(strategyOpsA, opsB, dstLoopDepth,
-                                     numCommonLoops, isSrcForOpBeforeDstForOp,
-                                     srcSlice))) {
+  SliceComputationResult sliceComputationResult =
+      mlir::computeSliceUnion(strategyOpsA, opsB, dstLoopDepth, numCommonLoops,
+                              isSrcForOpBeforeDstForOp, srcSlice);
+  if (sliceComputationResult.value == SliceComputationResult::GenericFailure) {
     LLVM_DEBUG(llvm::dbgs() << "computeSliceUnion failed\n");
     return FusionResult::FailPrecondition;
   }
+  if (sliceComputationResult.value ==
+      SliceComputationResult::IncorrectSliceFailure) {
+    LLVM_DEBUG(llvm::dbgs() << "Incorrect slice computation\n");
+    return FusionResult::FailIncorrectSlice;
+  }
 
   return FusionResult::Success;
 }
 
 /// Fuses 'srcForOp' into 'dstForOp' with destination loop block insertion point
 /// and source slice loop bounds specified in 'srcSlice'.
 void mlir::fuseLoops(AffineForOp srcForOp, AffineForOp dstForOp,
                      const ComputationSliceState &srcSlice) {

 /// in 'stats' for loop nest rooted at 'forOp'. Returns true on success,
 /// returns false otherwise.
 bool mlir::getLoopNestStats(AffineForOp forOpRoot, LoopNestStats *stats) {
   auto walkResult = forOpRoot.walk([&](AffineForOp forOp) {
     auto *childForOp = forOp.getOperation();
     auto *parentForOp = forOp->getParentOp();
     if (!llvm::isa<FuncOp>(parentForOp)) {
       if (!isa<AffineForOp>(parentForOp)) {
-        LLVM_DEBUG(llvm::dbgs() << "Expected parent AffineForOp");
+        LLVM_DEBUG(llvm::dbgs() << "Expected parent AffineForOp\n");
         return WalkResult::interrupt();
       }
       // Add mapping to 'forOp' from its parent AffineForOp.
       stats->loopMap[parentForOp].push_back(forOp);
     }
 
     // Record the number of op operations in the body of 'forOp'.
     unsigned count = 0;
     stats->opCountMap[childForOp] = 0;
     for (auto &op : *forOp.getBody()) {
       if (!isa<AffineForOp, AffineIfOp>(op))
         ++count;
     }
     stats->opCountMap[childForOp] = count;
 
     // Record trip count for 'forOp'. Set flag if trip count is not
     // constant.
     Optional<uint64_t> maybeConstTripCount = getConstantTripCount(forOp);
     if (!maybeConstTripCount.hasValue()) {
       // Currently only constant trip count loop nests are supported.
-      LLVM_DEBUG(llvm::dbgs() << "Non-constant trip count unsupported");
+      LLVM_DEBUG(llvm::dbgs() << "Non-constant trip count unsupported\n");
       return WalkResult::interrupt();
     }
 
     stats->tripCountMap[childForOp] = maybeConstTripCount.getValue();
     return WalkResult::advance();
   });
   return !walkResult.wasInterrupted();
 }
static bool buildSliceTripCountMap(
     llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
   unsigned numSrcLoopIVs = slice.ivs.size();
   // Populate map from AffineForOp -> trip count
   for (unsigned i = 0; i < numSrcLoopIVs; ++i) {
     AffineForOp forOp = getForInductionVarOwner(slice.ivs[i]);
     auto *op = forOp.getOperation();
     AffineMap lbMap = slice.lbs[i];
     AffineMap ubMap = slice.ubs[i];
-    if (lbMap == AffineMap() || ubMap == AffineMap()) {
+    // If lower or upper bound maps are null or provide no results, it implies
+    // that source loop was not at all sliced, and the entire loop will be a
+    // part of the slice.
+    if (!lbMap || lbMap.getNumResults() == 0 || !ubMap ||
+        ubMap.getNumResults() == 0) {
       // The iteration of src loop IV 'i' was not sliced. Use full loop bounds.
       if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
         (*tripCountMap)[op] =
             forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
         continue;
       }
       Optional<uint64_t> maybeConstTripCount = getConstantTripCount(forOp);
       if (maybeConstTripCount.hasValue()) {

mlir/test/Transforms/loop-fusion-slice-computation.mlir

 // RUN: mlir-opt %s -test-loop-fusion -test-loop-fusion-slice-computation -split-input-file -verify-diagnostics | FileCheck %s
 
 // -----
 
 // CHECK-LABEL: func @slice_depth1_loop_nest() {
 func @slice_depth1_loop_nest() {
   %0 = memref.alloc() : memref<100xf32>
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] )}}
     affine.store %cst, %0[%i0] : memref<100xf32>
   }
   affine.for %i1 = 0 to 5 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] )}}
     %1 = affine.load %0[%i1] : memref<100xf32>
   }
   return
 }
 
 // -----
 
+// CHECK-LABEL: func @forward_slice_slice_depth1_loop_nest() {
+func @forward_slice_slice_depth1_loop_nest() {
+  %0 = memref.alloc() : memref<100xf32>
+  %cst = constant 7.000000e+00 : f32
+  affine.for %i0 = 0 to 5 {
+    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] )}}
+    affine.store %cst, %0[%i0] : memref<100xf32>
+  }
+  affine.for %i1 = 0 to 16 {
+    // expected-remark@-1 {{Incorrect slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] )}}
+    %1 = affine.load %0[%i1] : memref<100xf32>
+  }
+  return
+}
+
+// -----
+
 // Loop %i0 writes to locations [2, 17] and loop %i0 reads from locations [3, 6]
 // Slice loop bounds should be adjusted such that the load/store are for the
 // same location.
 // CHECK-LABEL: func @slice_depth1_loop_nest_with_offsets() {
 func @slice_depth1_loop_nest_with_offsets() {
   %0 = memref.alloc() : memref<100xf32>
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 2) loop bounds: [(d0) -> (d0 + 3), (d0) -> (d0 + 4)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 2) loop bounds: [(d0) -> (d0 + 3), (d0) -> (d0 + 4)] )}}
     %a0 = affine.apply affine_map<(d0) -> (d0 + 2)>(%i0)
     affine.store %cst, %0[%a0] : memref<100xf32>
   }
   affine.for %i1 = 4 to 8 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0 - 3), (d0) -> (d0 - 2)] )}}
     %a1 = affine.apply affine_map<(d0) -> (d0 - 1)>(%i1)
     %1 = affine.load %0[%a1] : memref<100xf32>
   }
   return
 }
 
 // -----
 
 // Slices at loop depth 1 should only slice the loop bounds of the first scf.
 // Slices at loop depth 2 should slice loop bounds of both loops.
 // CHECK-LABEL: func @slice_depth2_loop_nest() {
 func @slice_depth2_loop_nest() {
   %0 = memref.alloc() : memref<100x100xf32>
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
-    // expected-remark@-2 {{slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
+    // expected-remark@-2 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
     affine.for %i1 = 0 to 16 {
       affine.store %cst, %0[%i0, %i1] : memref<100x100xf32>
     }
   }
   affine.for %i2 = 0 to 10 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
     // expected-remark@-2 {{slice ( src loop: 0, dst loop: 1, depth: 2 : insert point: (2, 0) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
     affine.for %i3 = 0 to 8 {
       %1 = affine.load %0[%i2, %i3] : memref<100x100xf32>
     }
   }
   return
 }
 
 // -----
 
 // The load at depth 1 in loop nest %i2 prevents slicing loop nest %i0 at depths
 // greater than 1. However, loop nest %i2 can be sliced into loop nest %i0 at
 // depths 1 and 2 because the dependent store in loop nest %i0 is at depth 2.
 // CHECK-LABEL: func @slice_depth2_loop_nest_two_loads() {
 func @slice_depth2_loop_nest_two_loads() {
   %0 = memref.alloc() : memref<100x100xf32>
   %c0 = constant 0 : index
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
-    // expected-remark@-2 {{slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (0), (d0, d1) -> (8)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
+    // expected-remark@-2 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (0), (d0, d1) -> (16)] )}}
     affine.for %i1 = 0 to 16 {
       affine.store %cst, %0[%i0, %i1] : memref<100x100xf32>
     }
   }
   affine.for %i2 = 0 to 10 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
     affine.for %i3 = 0 to 8 {
       %1 = affine.load %0[%i2, %i3] : memref<100x100xf32>

 // sliced into loop nest %i2 at depths 1 and 2 because the dependent load in
 // loop nest %i2 is at depth 2.
 // CHECK-LABEL: func @slice_depth2_loop_nest_two_stores() {
 func @slice_depth2_loop_nest_two_stores() {
   %0 = memref.alloc() : memref<100x100xf32>
   %c0 = constant 0 : index
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 2) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 2) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (8)] )}}
     affine.for %i1 = 0 to 16 {
       affine.store %cst, %0[%i0, %i1] : memref<100x100xf32>
     }
     affine.store %cst, %0[%i0, %c0] : memref<100x100xf32>
   }
   affine.for %i2 = 0 to 10 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (16)] )}}
     // expected-remark@-2 {{slice ( src loop: 0, dst loop: 1, depth: 2 : insert point: (2, 0) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (0), (d0, d1) -> (16)] )}}
     affine.for %i3 = 0 to 8 {
       %1 = affine.load %0[%i2, %i3] : memref<100x100xf32>
     }
   }
   return
 }
 
 // -----
 
 // Test loop nest which has a smaller outer trip count than its inner scf.
 // CHECK-LABEL: func @slice_loop_nest_with_smaller_outer_trip_count() {
 func @slice_loop_nest_with_smaller_outer_trip_count() {
   %0 = memref.alloc() : memref<100x100xf32>
   %c0 = constant 0 : index
   %cst = constant 7.000000e+00 : f32
   affine.for %i0 = 0 to 16 {
-    // expected-remark@-1 {{slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (10)] )}}
-    // expected-remark@-2 {{slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
+    // expected-remark@-1 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 1 : insert point: (1, 1) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (10)] )}}
+    // expected-remark@-2 {{Incorrect slice ( src loop: 1, dst loop: 0, depth: 2 : insert point: (2, 1) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
     affine.for %i1 = 0 to 16 {
       affine.store %cst, %0[%i0, %i1] : memref<100x100xf32>
     }
   }
   affine.for %i2 = 0 to 8 {
     // expected-remark@-1 {{slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0) loop bounds: [(d0) -> (d0), (d0) -> (d0 + 1)] [(d0) -> (0), (d0) -> (10)] )}}
     // expected-remark@-2 {{slice ( src loop: 0, dst loop: 1, depth: 2 : insert point: (2, 0) loop bounds: [(d0, d1) -> (d0), (d0, d1) -> (d0 + 1)] [(d0, d1) -> (d1), (d0, d1) -> (d1 + 1)] )}}
     affine.for %i3 = 0 to 10 {
       %1 = affine.load %0[%i2, %i3] : memref<100x100xf32>
     }
   }
   return
 }

mlir/test/Transforms/loop-fusion.mlir

affine.for %arg1 = 0 to 16 {
     %b = addf %cst_1, %a : f32
     affine.store %b, %B[%arg1] : memref<16xf32>
   }
   return
 }
 // CHECK-LABEL: func @call_op_does_not_prevent_fusion
 // CHECK:         affine.for
 // CHECK-NOT:     affine.for
+
+// -----
+
+// Fusion is avoided when the slice computed is invalid. Comments below describe
+// incorrect backward slice computation. Similar logic applies for forward slice
+// as well.
+func @no_fusion_cannot_compute_valid_slice() {
+  %A = memref.alloc() : memref<5xf32>
+  %B = memref.alloc() : memref<6xf32>
+  %C = memref.alloc() : memref<5xf32>
+  %cst = constant 0. : f32
+
+  affine.for %arg0 = 0 to 5 {
+    %a = affine.load %A[%arg0] : memref<5xf32>
+    affine.store %a, %B[%arg0 + 1] : memref<6xf32>
+  }
+
+  affine.for %arg0 = 0 to 5 {
+    // Backward slice computed will be:
+    // slice ( src loop: 0, dst loop: 1, depth: 1 : insert point: (1, 0)
+    // loop bounds: [(d0) -> (d0 - 1), (d0) -> (d0)] )
+
+    // Resulting fusion would be as below. It is easy to note the out-of-bounds
+    // access by 'affine.load'.
+
+    // #map0 = affine_map<(d0) -> (d0 - 1)>
+    // #map1 = affine_map<(d0) -> (d0)>
+    // affine.for %arg1 = #map0(%arg0) to #map1(%arg0) {
+    //   %5 = affine.load %1[%arg1] : memref<5xf32>
+    //   ...
+    //   ...
+    // }
+
+    %a = affine.load %B[%arg0] : memref<6xf32>
+    %b = mulf %a, %cst : f32
+    affine.store %b, %C[%arg0] : memref<5xf32>
+  }
+  return
+}
+// CHECK-LABEL: func @no_fusion_cannot_compute_valid_slice
+// CHECK:         affine.for
+// CHECK-NEXT:      affine.load
+// CHECK-NEXT:      affine.store
+// CHECK:         affine.for
+// CHECK-NEXT:      affine.load
+// CHECK-NEXT:      mulf
+// CHECK-NEXT:      affine.store

mlir/test/lib/Transforms/TestLoopFusion.cpp

for (unsigned k = 0, e = sliceUnion.lbs.size(); k < e; ++k) {
     sliceUnion.lbs[k].print(os);
     os << ", ";
     sliceUnion.ubs[k].print(os);
     os << "] ";
   }
   return os.str();
 }
 
-// Computes fusion slice union on 'loops[i]' and 'loops[j]' at loop depths
-// in range ['loopDepth' + 1, 'maxLoopDepth'].
-// Emits a string representation of the slice union as a remark on 'loops[j]'.
-// Returns false as IR is not transformed.
+/// Computes fusion slice union on 'loops[i]' and 'loops[j]' at loop depths
+/// in range ['loopDepth' + 1, 'maxLoopDepth'].
+/// Emits a string representation of the slice union as a remark on 'loops[j]'
+/// and marks this as incorrect slice if the slice is invalid. Returns false as
+/// IR is not transformed.
 static bool testSliceComputation(AffineForOp forOpA, AffineForOp forOpB,
                                  unsigned i, unsigned j, unsigned loopDepth,
                                  unsigned maxLoopDepth) {
   for (unsigned d = loopDepth + 1; d <= maxLoopDepth; ++d) {
     mlir::ComputationSliceState sliceUnion;
     FusionResult result = mlir::canFuseLoops(forOpA, forOpB, d, &sliceUnion);
     if (result.value == FusionResult::Success) {
       forOpB->emitRemark("slice (")
           << " src loop: " << i << ", dst loop: " << j << ", depth: " << d
           << " : " << getSliceStr(sliceUnion) << ")";
+    } else if (result.value == FusionResult::FailIncorrectSlice) {
+      forOpB->emitRemark("Incorrect slice (")
+          << " src loop: " << i << ", dst loop: " << j << ", depth: " << d
+          << " : " << getSliceStr(sliceUnion) << ")";
     }
   }
   return false;
 }
 
 // Attempts to fuse 'forOpA' into 'forOpB' at loop depths in range
 // ['loopDepth' + 1, 'maxLoopDepth'].
 // Returns true if loops were successfully fused, false otherwise.