[Loop Fusion] Sink/hoist memory instructions between loop fusion candidates

[aaronkintel]

Summary

Currently, instructions in the preheader of the second of two fusion candidates are sunk and hoisted whenever possible, to try to allow the loops to fuse. Memory instructions are skipped, and are never sunk or hoisted. This change adds memory instructions for sinking/hoisting consideration.

This change uses DependenceAnalysis to check if a mem inst in the preheader of FC1 depends on an instruction in FC0's header, across which it will be hoisted, or FC1's header, across which it will be sunk. We reject cases where the dependency is a data hazard.

[Whitney]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1042

Please add a description of this function and the expected result/meaning of the arguments.

1046

This comment no longer needed in this context, as this function is for checking if the instruction can be hoisted.

1065

No need braces for single instruction block.

1082

Why only considering instructions in the header and not any other blocks in FC0 loop?

1097

Please add a description of this function.

1111

Please remove braces.

1115

Why only considering instructions in the header and not any other blocks in FC1 loop?

1152

nit: add a period at the end of a sentence.

1170–1174

Should we also skip other non-store instructions if they are volatile or atomic?

I can see that LLVM::Instruction has function isVolatile() and isAtomic() to check those.

llvm/test/Transforms/LoopFusion/no_sink_hoist_load.ll

2

Do we have test case for volatile or atomic?

llvm/test/Transforms/LoopFusion/no_sink_hoist_unknown_function.ll

13–14

; CHECK-NOT: call void @unknown_func()?

27–28

; CHECK-NOT: call void @unknown_func()?

llvm/test/Transforms/LoopFusion/simple.ll

512 ↗

(On Diff #451576)

How is this change related to this patch?

llvm/test/Transforms/LoopFusion/sink_load.ll

2

do we have test cases for hoist memory instructions?

[bmahjour]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1065

why the call to mayHaveSideEffects has been removed?

1111

why the call to mayHaveSideEffects has been removed?

[aaronkintel]

Responding to comments

[aaronkintel]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1065

mayHaveSideEffects() returns mayWriteToMemory() || mayThrow() || !willReturn(), but we don't want to reject cases that may read to memory anymore.

1082

In a canonical LLVM loop,

1111

As above.

1170–1174

sUnordered() calls isVolatile() and checks atomicity under the hood.

llvm/test/Transforms/LoopFusion/simple.ll

512 ↗

(On Diff #451576)

Lit test was otherwise broken.

[Whitney]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1042

please add \p before parameters. e.g., instruction \p I.

1042

You may want to specific is the end of the preheader.

1065

Can combine !I.mayReadFromMemory() && !I.mayWriteToMemory() to !I.mayReadOrWriteMemory().

1082

In a canonical LLVM loop,

Not sure what you mean by that. I can see that you changed it to traverse memory reads and writes, LGTM.

1103

You may want to specify is to the beginning of the exit block.

1170–1174

Right, but isUnordered() is not a member function of LLVM::Instruction. Your new change for this comment LGTM.

llvm/test/Transforms/LoopFusion/simple.ll

512 ↗

(On Diff #451576)

Can you please elaborate more on why it was broken?

[congzhe]

The changes made in this patch, notably canHoistInst() and canSinkInst() seems to have duplicate functionality from CodeMoverUtils.cpp. I'm wondering if we can reuse the code from CodeMoverUtils.cpp? Or is there something that canHoistInst() and canSinkInst() can do but functions from CodeMoverUtils.cpp cannot do?

llvm/test/Transforms/LoopFusion/simple.ll

537 ↗

(On Diff #455332)

Why change from adding 1 to adding %add?

[aaronkintel]

In D131606#3747037, @congzhe wrote:

The changes made in this patch, notably canHoistInst() and canSinkInst() seems to have duplicate functionality from CodeMoverUtils.cpp. I'm wondering if we can reuse the code from CodeMoverUtils.cpp? Or is there something that canHoistInst() and canSinkInst() can do but functions from CodeMoverUtils.cpp cannot do?

The difficulty I see with utilizing isSafeToMove{Before, After}() from CodeMoverUtils in this context is that when determining if an instruction in the preheader of FC1 can be sunk/hoisted, we need to take into account other instructions in the preheader of FC1 which are eligible for sinking/hoisting.

Consider this example:

define void @sink_preheader(i32 %N) {
pre1:
  br label %body1

body1:  ; preds = %pre1, %body1
  ...
  br i1 %cond, label %body1, label %pre2

pre2:
  %i1 = add i32 1, %N
  %i2 = add i32 1, %i1
  br label %body2

....
}

Both %i1 and %i2 can be hoisted, though isSafeToMoveBefore() would presumably not believe %i2 should be moved to the end of pre1. If you're seeing something I'm not, let me know and I'd be happy to simplify the code.

llvm/test/Transforms/LoopFusion/simple.ll

512 ↗

(On Diff #451576)

In fact, it should still work without any changes. Will fix

[aaronkintel]

Responding to comments.

[congzhe]

In D131606#3747152, @aaronkintel wrote:

In D131606#3747037, @congzhe wrote:

The changes made in this patch, notably canHoistInst() and canSinkInst() seems to have duplicate functionality from CodeMoverUtils.cpp. I'm wondering if we can reuse the code from CodeMoverUtils.cpp? Or is there something that canHoistInst() and canSinkInst() can do but functions from CodeMoverUtils.cpp cannot do?

The difficulty I see with utilizing isSafeToMove{Before, After}() from CodeMoverUtils in this context is that when determining if an instruction in the preheader of FC1 can be sunk/hoisted, we need to take into account other instructions in the preheader of FC1 which are eligible for sinking/hoisting.

Consider this example:

define void @sink_preheader(i32 %N) {
pre1:
  br label %body1

body1:  ; preds = %pre1, %body1
  ...
  br i1 %cond, label %body1, label %pre2

pre2:
  %i1 = add i32 1, %N
  %i2 = add i32 1, %i1
  br label %body2

....
}

Both %i1 and %i2 can be hoisted, though isSafeToMoveBefore() would presumably not believe %i2 should be moved to the end of pre1. If you're seeing something I'm not, let me know and I'd be happy to simplify the code.

IIUC the problem you described has been addressed and handled in CodeMoverUtils already.

The function isSafeToMoveBefore() has the following signature where the last argument CheckForEntireBlock can be set to true such that previous instructions (before the current instruction that is under consideration) would be considered when checking if it is legal to move it. If I'm not mistaken, for the IR you posted we can actually move both %i1 and %i2 (by setting CheckForEntireBlock=true). You might want to check out this patch https://reviews.llvm.org/D110378, which introduced CheckForEntireBlock.

bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                        DominatorTree &DT,
                        const PostDominatorTree *PDT = nullptr,
                        DependenceInfo *DI = nullptr,
                        bool CheckForEntireBlock = false);

If I'm not mistaken (please correct me if I'm wrong), I wish we could reuse CodeMoverUtils since it could simplify things.

[aaronkintel]

In D131606#3747208, @congzhe wrote:

IIUC the problem you described has been addressed and handled in CodeMoverUtils already.

The function isSafeToMoveBefore() has the following signature where the last argument CheckForEntireBlock can be set to true such that previous instructions (before the current instruction that is under consideration) would be considered when checking if it is legal to move it. If I'm not mistaken, for the IR you posted we can actually move both %i1 and %i2 (by setting CheckForEntireBlock=true). You might want to check out this patch https://reviews.llvm.org/D110378, which introduced CheckForEntireBlock.

bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                        DominatorTree &DT,
                        const PostDominatorTree *PDT = nullptr,
                        DependenceInfo *DI = nullptr,
                        bool CheckForEntireBlock = false);

If I'm not mistaken (please correct me if I'm wrong), I wish we could reuse CodeMoverUtils since it could simplify things.

I tried some tests with isSafeToMoveBefore(). The sink_preheader.ll test fails, since %sinkme can be sunk but then %sinkme2 cannot sink, because isSafeToMoveBefore() apparently does not ignore users in the same block like it ignores operands in the same block when hoisting. The condition CheckForEntireBlock for sinking could be added, to mirror the case with hoisting, but I foresee other issues. For example, %sinkme3 in sink_preheader.ll should not be hoisted, though the only obstacle for hoisting it (%sinkme1 ) is within the same block as %sinkme3 itself; we need to know that %sinkme1 also cannot be hoisted, and it is insufficient to just ignore variable.

[congzhe]

In D131606#3750026, @aaronkintel wrote:

In D131606#3747208, @congzhe wrote:

IIUC the problem you described has been addressed and handled in CodeMoverUtils already.

The function isSafeToMoveBefore() has the following signature where the last argument CheckForEntireBlock can be set to true such that previous instructions (before the current instruction that is under consideration) would be considered when checking if it is legal to move it. If I'm not mistaken, for the IR you posted we can actually move both %i1 and %i2 (by setting CheckForEntireBlock=true). You might want to check out this patch https://reviews.llvm.org/D110378, which introduced CheckForEntireBlock.

bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                        DominatorTree &DT,
                        const PostDominatorTree *PDT = nullptr,
                        DependenceInfo *DI = nullptr,
                        bool CheckForEntireBlock = false);

If I'm not mistaken (please correct me if I'm wrong), I wish we could reuse CodeMoverUtils since it could simplify things.

I tried some tests with isSafeToMoveBefore(). The sink_preheader.ll test fails, since %sinkme can be sunk but then %sinkme2 cannot sink, because isSafeToMoveBefore() apparently does not ignore users in the same block like it ignores operands in the same block when hoisting. The condition CheckForEntireBlock for sinking could be added, to mirror the case with hoisting, but I foresee other issues. For example, %sinkme3 in sink_preheader.ll should not be hoisted, though the only obstacle for hoisting it (%sinkme1 ) is within the same block as %sinkme3 itself; we need to know that %sinkme1 also cannot be hoisted, and it is insufficient to just ignore variable.

IMHO I don't think %sinkme3 will be hoisted. Maybe I should have made it more clear in my last comment: in loop fusion we would usually want to move an entire BB, for example moving the preheader of the second loop to the first loop in order to create an empty preheader. The API from CodeMoverUtils for this purpose is the following, where the first argument is BasicBlock&. Maybe it should be renamed to something like "isSafeToMoveBBBefore()" to be more clear.

bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                              DominatorTree &DT, const PostDominatorTree *PDT,
                              DependenceInfo *DI) {
  return llvm::all_of(BB, [&](Instruction &I) {
    if (BB.getTerminator() == &I)
      return true;

    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
                              /*CheckForEntireBlock=*/true);
  });
}

%sinkme3 won't be hoisted because %sinkme1 won't be hoisted at the first place since %barrier does not dominate the insertion point, and llvm::all_of() would bail out early. Therefore IIUC this would not be an issue.

I did not mean to block or suspend this patch, although I think it might be cleaner and simpler to add some code in isSafeToMoveBefore() to mirror the case with hoisting and then reuse isSafeToMoveBefore(), which seems sufficient to fullfil your purposes. I quickly looked at the logic in isSafeToMoveBefore() and it looks like adding some code under the if (isReachedBefore(&I, &InsertPoint, &DT, PDT)) condition to enable stronger sinking capability might just do the work, similar to the code added under if (isReachedBefore(&InsertPoint, &I, &DT, PDT)) that enabled stronger hoisting.

Again I'm open to any possible solution, let it be this patch or other approaches - just trying to provide some input.

[aaronkintel]

In D131606#3750451, @congzhe wrote:

IMHO I don't think %sinkme3 will be hoisted. Maybe I should have made it more clear in my last comment: in loop fusion we would usually want to move an entire BB, for example moving the preheader of the second loop to the first loop in order to create an empty preheader. The API from CodeMoverUtils for this purpose is the following, where the first argument is BasicBlock&. Maybe it should be renamed to something like "isSafeToMoveBBBefore()" to be more clear.

bool llvm::isSafeToMoveBefore(BasicBlock &BB, Instruction &InsertPoint,
                              DominatorTree &DT, const PostDominatorTree *PDT,
                              DependenceInfo *DI) {
  return llvm::all_of(BB, [&](Instruction &I) {
    if (BB.getTerminator() == &I)
      return true;

    return isSafeToMoveBefore(I, InsertPoint, DT, PDT, DI,
                              /*CheckForEntireBlock=*/true);
  });
}

%sinkme3 won't be hoisted because %sinkme1 won't be hoisted at the first place since %barrier does not dominate the insertion point, and llvm::all_of() would bail out early. Therefore IIUC this would not be an issue.

I did not mean to block or suspend this patch, although I think it might be cleaner and simpler to add some code in isSafeToMoveBefore() to mirror the case with hoisting and then reuse isSafeToMoveBefore(), which seems sufficient to fullfil your purposes. I quickly looked at the logic in isSafeToMoveBefore() and it looks like adding some code under the if (isReachedBefore(&I, &InsertPoint, &DT, PDT)) condition to enable stronger sinking capability might just do the work, similar to the code added under if (isReachedBefore(&InsertPoint, &I, &DT, PDT)) that enabled stronger hoisting.

Again I'm open to any possible solution, let it be this patch or other approaches - just trying to provide some input.

Ok, I think I see what you're getting at. The function isSafeToMoveBefore() could be used to sink/hoist the entire preheader of FC1 atomically, but it cannot handle the situation where some instructions can be sunk and some can be hoisted safely.

[aaronkintel]

Fixing clang-format issues

[aaronkintel]

This change is building successfully. Are there any more reviewer comments?

[aaronkintel]

Adding TODO to add the canSinkInst/canHoistInsts to codeMoverUtils.

[congzhe]

Like I said I won't block the patch, I'm fine if other reviewers accept this patch.

For me personally I would suggest the // TODO: Move functionality into CodeMoverUtils really be done before I would accept it myself, since CodeMoverUtils looks like the place that fits better for the functionality that is added in this patch.

[Whitney]

I agree with @congzhe that CodeMoverUtils fits better for the functionality that is added in this patch. I am ok that this being a 2-steps process, where you first add the functionality in loop fusion pass, and then improve CodeMoverUtils.
Given that @aaronkintel added the TODOs, I can approve it, but please do improve CodeMoverUtils.

[eopXD]

May you have the new added tests be separated to a pre-commit patch so the effect of this patch can be more clear?

llvm/lib/Transforms/Scalar/LoopFuse.cpp

#endif
   /// This function will return a pair of values. The first is a boolean,
   /// stating whether or not the two candidates are known at compile time to
   /// have the same TripCount. The second is the difference in the two
   /// TripCounts. This information can be used later to determine whether or not
   /// peeling can be performed on either one of the candidates.
   std::pair<bool, Optional<unsigned>>
   haveIdenticalTripCounts(const FusionCandidate &FC0,
                           const FusionCandidate &FC1) const {
-
     const SCEV *TripCount0 = SE.getBackedgeTakenCount(FC0.L);
     if (isa<SCEVCouldNotCompute>(TripCount0)) {
       UncomputableTripCount++;
       LLVM_DEBUG(dbgs() << "Trip count of first loop could not be computed!");
       return {false, None};
     }
 
     const SCEV *TripCount1 = SE.getBackedgeTakenCount(FC1.L);
for (auto &CandidateSet : FusionCandidates) {
 
           Fused = true;
         }
       }
     }
     return Fused;
   }
 
+  // Returns true if the instruction I can be hoisted to the preheader of FC0.
+  // SafeToHoist contains the instructions that are known to be safe to hoist.
+  // The instructions encountered that cannot be hoisted are in NotHoisting.
+  bool canHoistInst(Instruction &I,
+                    const SmallVector<Instruction *, 4> &SafeToHoist,
+                    const SmallVector<Instruction *, 4> &NotHoisting,
+                    const FusionCandidate &FC0) const {
+    const BasicBlock *FC0PreheaderTarget = FC0.Preheader->getSingleSuccessor();
+    assert(FC0PreheaderTarget &&
+           "Expected single successor for loop preheader.");
+
+    for (Use &Op : I.operands()) {
+      if (auto *OpInst = dyn_cast<Instruction>(Op)) {
+        bool OpHoisted = is_contained(SafeToHoist, OpInst);
+        // Check if we have already decided to hoist this operand. In this
+        // case, it does not dominate FC0 *yet*, but will after we hoist it.
+        if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {
+          return false;
+        }
+      }
+    }
+
+    // If this isn't a memory inst, hoisting is safe
+    if (!I.mayReadFromMemory() && !I.mayWriteToMemory())
+      return true;
+
+    LLVM_DEBUG(dbgs() << "Checking if this mem inst can be hoisted.\n");
+    for (Instruction *NotHoistedInst : NotHoisting) {
+      if (auto D = DI.depends(&I, NotHoistedInst, true)) {
+        // Dependency is not read-before-write, write-before-read or
+        // write-before-write
+        if (D->isFlow() || D->isAnti() || D->isOutput()) {
+          LLVM_DEBUG(dbgs() << "Inst depends on an instruction in FC1's "
+                               "preheader that is not being hoisted.\n");
+          return false;
+        }
+      }
+    }
+
+    for (Instruction *ReadInst : FC0.MemReads) {
+      if (auto D = DI.depends(ReadInst, &I, true)) {
+        // Dependency is not read-before-write
+        if (D->isAnti()) {
+          LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC0.\n");
+          return false;
+        }
+      }
+    }
+
+    for (Instruction *WriteInst : FC0.MemWrites) {
+      if (auto D = DI.depends(WriteInst, &I, true)) {
+        // Dependency is not write-before-read or write-before-write
+        if (D->isFlow() || D->isOutput()) {
+          LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC0.\n");
+          return false;
+        }
+      }
+    }
+    return true;
+  }
+
+  // Returns true if the instruction I can be sunk to the exit block of FC1.
+  bool canSinkInst(Instruction &I, const FusionCandidate &FC1) const {
+    for (User *U : I.users()) {
+      if (auto *UI{dyn_cast<Instruction>(U)}) {
+        // Cannot sink if user in loop
+        // If FC1 has phi users of this value, we cannot sink it into FC1.
+        if (FC1.L->contains(UI)) {
+          // Cannot hoist or sink this instruction. No hoisting/sinking
+          // should take place, loops should not fuse
+          return false;
+        }
+      }
+    }
+
+    // If this isn't a memory inst, sinking is safe
+    if (!I.mayReadFromMemory() && !I.mayWriteToMemory())
+      return true;
+
+    for (Instruction *ReadInst : FC1.MemReads) {
+      if (auto D = DI.depends(&I, ReadInst, true)) {
+        // Dependency is not write-before-read
+        if (D->isFlow()) {
+          LLVM_DEBUG(dbgs() << "Inst depends on a read instruction in FC1.\n");
+          return false;
+        }
+      }
+    }
+
+    for (Instruction *WriteInst : FC1.MemWrites) {
+      if (auto D = DI.depends(&I, WriteInst, true)) {
+        // Dependency is not write-before-write or read-before-write
+        if (D->isOutput() || D->isAnti()) {
+          LLVM_DEBUG(dbgs() << "Inst depends on a write instruction in FC1.\n");
+          return false;
+        }
+      }
+    }
+
+    return true;
+  }
+
   /// Collect instructions in the \p FC1 Preheader that can be hoisted
   /// to the \p FC0 Preheader or sunk into the \p FC1 Body
   bool collectMovablePreheaderInsts(
       const FusionCandidate &FC0, const FusionCandidate &FC1,
       SmallVector<Instruction *, 4> &SafeToHoist,
       SmallVector<Instruction *, 4> &SafeToSink) const {
     BasicBlock *FC1Preheader = FC1.Preheader;
+    // Save the instructions that are not being hoisted, so we know not to hoist
+    // mem insts that they dominate.
+    SmallVector<Instruction *, 4> NotHoisting;
+
     for (Instruction &I : *FC1Preheader) {
       // Can't move a branch
       if (&I == FC1Preheader->getTerminator())
         continue;
       // If the instruction has side-effects, give up.
       // TODO: The case of mayReadFromMemory we can handle but requires
       // additional work with a dependence analysis so for now we give
       // up on memory reads.
-      if (I.mayHaveSideEffects() || I.mayReadFromMemory()) {
-        LLVM_DEBUG(dbgs() << "Inst: " << I << " may have side-effects.\n");
+      if (I.mayThrow() || !I.willReturn()) {
+        LLVM_DEBUG(dbgs() << "Inst: " << I << " may throw or won't return.\n");
         return false;
       }
 
       LLVM_DEBUG(dbgs() << "Checking Inst: " << I << "\n");
 
-      // First check if can be hoisted
-      // If the operands of this instruction dominate the FC0 Preheader
-      // target block, then it is safe to move them to the end of the FC0
-      const BasicBlock *FC0PreheaderTarget =
-          FC0.Preheader->getSingleSuccessor();
-      assert(FC0PreheaderTarget &&
-             "Expected single successor for loop preheader.");
-      bool CanHoistInst = true;
-      for (Use &Op : I.operands()) {
-        if (auto *OpInst = dyn_cast<Instruction>(Op)) {
-          bool OpHoisted = is_contained(SafeToHoist, OpInst);
-          // Check if we have already decided to hoist this operand. In this
-          // case, it does not dominate FC0 *yet*, but will after we hoist it.
-          if (!(OpHoisted || DT.dominates(OpInst, FC0PreheaderTarget))) {
-            CanHoistInst = false;
-            break;
-          }
-        }
+        if (I.isAtomic() || I.isVolatile()) {
+          LLVM_DEBUG(
+              dbgs()
+              << "\tInstruction is volatile or atomic. Cannot move it.\n");
+          return false;
         }
-      if (CanHoistInst) {
+
+      if (canHoistInst(I, SafeToHoist, NotHoisting, FC0)) {
         SafeToHoist.push_back(&I);
         LLVM_DEBUG(dbgs() << "\tSafe to hoist.\n");
       } else {
         LLVM_DEBUG(dbgs() << "\tCould not hoist. Trying to sink...\n");
+        NotHoisting.push_back(&I);
 
-        for (User *U : I.users()) {
-          if (auto *UI{dyn_cast<Instruction>(U)}) {
-            // Cannot sink if user in loop
-            // If FC1 has phi users of this value, we cannot sink it into FC1.
-            if (FC1.L->contains(UI)) {
-              // Cannot hoist or sink this instruction. No hoisting/sinking
-              // should take place, loops should not fuse
-              LLVM_DEBUG(dbgs() << "\tCould not sink.\n");
-              return false;
-            }
-          }
-        }
-        SafeToSink.push_back(&I);
-        LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");
-      }
-    }
+        if (canSinkInst(I, FC1)) {
+          SafeToSink.push_back(&I);
+          LLVM_DEBUG(dbgs() << "\tSafe to sink.\n");
+        } else {
     LLVM_DEBUG(
         dbgs() << "All preheader instructions could be sunk or hoisted!\n");
     return true;
   }
 
   /// Rewrite all additive recurrences in a SCEV to use a new loop.
   class AddRecLoopReplacer : public SCEVRewriteVisitor<AddRecLoopReplacer> {
   public:
#endif
   }
 
   /// Hoist \p FC1 Preheader instructions to \p FC0 Preheader
   /// and sink others into the body of \p FC1.
   void movePreheaderInsts(const FusionCandidate &FC0,
                           const FusionCandidate &FC1,
                           SmallVector<Instruction *, 4> &HoistInsts,
                           SmallVector<Instruction *, 4> &SinkInsts) const {
-
     // All preheader instructions except the branch must be hoisted or sunk
     assert(HoistInsts.size() + SinkInsts.size() == FC1.Preheader->size() - 1 &&
            "Attempting to sink and hoist preheader instructions, but not all "
            "the preheader instructions are accounted for.");
 
     NumHoistedInsts += HoistInsts.size();
     NumSunkInsts += SinkInsts.size();
 

llvm/test/Transforms/LoopFusion/hoist_load.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Safe to hoist.
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @hoist_preheader(i32 %N) {
+; CHECK-LABEL: @hoist_preheader(
+; CHECK-NEXT:  pre1:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[PTR]], align 4
+; CHECK-NEXT:    br label [[BODY1:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[BODY1]] ], [ 0, [[PRE1:%.*]] ]
+; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ [[I_NEXT2:%.*]], [[BODY1]] ], [ 0, [[PRE1]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[I]], [[N:%.*]]
+; CHECK-NEXT:    [[I_NEXT2]] = add i32 1, [[I2]]
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ne i32 [[I2]], [[N]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[BODY1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  %b = load i32, i32 * %ptr
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/hoist_store.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Safe to hoist.
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @hoist_preheader(i32 %N) {
+; CHECK-LABEL: @hoist_preheader(
+; CHECK-NEXT:  pre1:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 3, i32* [[PTR]], align 4
+; CHECK-NEXT:    br label [[BODY1:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[BODY1]] ], [ 0, [[PRE1:%.*]] ]
+; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ [[I_NEXT2:%.*]], [[BODY1]] ], [ 0, [[PRE1]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[I]], [[N:%.*]]
+; CHECK-NEXT:    [[I_NEXT2]] = add i32 1, [[I2]]
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ne i32 [[I2]], [[N]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[BODY1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  store i32 3, i32* %ptr
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_atomic.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Could not hoist/sink all instructions
+
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:   %ptr = alloca i32
+; CHECK-NEXT:  br label %body1
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT: store atomic i32 3, i32* %ptr seq_cst, align 4
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK-NEXT: store atomic i32 3, i32* %ptr seq_cst, align 4
+pre2:
+  store atomic i32 3, i32* %ptr seq_cst, align 4
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT:  store atomic i32 3, i32* %ptr seq_cst, align 4
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_load.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Could not hoist/sink all instructions
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  %ptr = alloca i32, align 4
+; CHECK-NEXT:  br label %body1
+pre1:
+  %ptr = alloca i32, align 4
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT:  %stay =
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  store i32 3, i32* %ptr
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK-NEXT: %stay = load i32, i32* %ptr
+pre2:
+  %stay = load i32, i32* %ptr
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: %stay =
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  store i32 3, i32* %ptr
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+; CHECK-NOT: %stay =
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/no_sink_hoist_store.ll

 ; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
 ; REQUIRES: asserts
-; CHECK: have side-effects.
 ; CHECK: Could not hoist/sink all instructions
 
 @A = common global [100 x i32] zeroinitializer, align 16
 define void @sink_preheader(i32 %N) {
 ; CHECK:pre1:
 ; CHECK-NEXT:  %ptr = alloca i32, align 4
 ; CHECK-NEXT:  br label %body1
 pre1:
-  %ptr = alloca i32
+  %ptr = alloca i32, align 4
   br label %body1
 
 ; CHECK:body1: 
-; CHECK-NOT:  %stay =
+; CHECK-NOT:  store i32 3, i32* %ptr
 body1:  ; preds = %pre1, %body1
   %i = phi i32 [%i_next, %body1], [0, %pre1]
   %i_next = add i32 1, %i
   %cond = icmp ne i32 %i, %N
+  %load1 = load i32, i32* %ptr
   br i1 %cond, label %body1, label %pre2
 
 ; CHECK:pre2:
 ; CHECK-NEXT: store i32 3, i32* %ptr
 pre2:
   store i32 3, i32* %ptr
   br label %body2
 
 ; CHECK: body2:
-; CHECK-NOT: %stay =
+; CHECK-NOT: store i32 3, i32* %ptr
 body2:  ; preds = %pre2, %body2
   %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
   %i_next2 = add i32 1, %i2
   %cond2 = icmp ne i32 %i2, %N
+  %load2 = load i32, i32* %ptr
   br i1 %cond2, label %body2, label %exit
 
 ; CHECK: exit:
-; CHECK-NOT: %stay =
+; CHECK-NOT: store i32 3, i32* %ptr
 exit:
   ret void
 }

llvm/test/Transforms/LoopFusion/no_sink_hoist_unknown_function.ll

 ; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
 ; REQUIRES: asserts
-; CHECK: may have side-effects
 ; CHECK: Could not hoist/sink all instructions
 
 declare void @unknown_func()
 
 define void @sink_preheader(i32 %N) {
 ; CHECK:pre1:
 ; CHECK-NEXT:  br label %body1
 pre1:
   br label %body1
 
 ; CHECK:body1: 
-; CHECK-NOT:  %stay =
+; CHECK-NOT: call void @unknown_func()
 body1:  ; preds = %pre1, %body1
   %i = phi i32 [%i_next, %body1], [0, %pre1]
   %i_next = add i32 1, %i
   %cond = icmp ne i32 %i, %N
   br i1 %cond, label %body1, label %pre2
 
 ; CHECK:pre2:
 ; CHECK-NEXT: call void @unknown_func()
 pre2:
   call void @unknown_func()
   br label %body2
 
 ; CHECK: body2:
-; CHECK-NOT: %stay =
+; CHECK-NOT: call void @unknown_func()
 body2:  ; preds = %pre2, %body2
   %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
   %i_next2 = add i32 1, %i2
   %cond2 = icmp ne i32 %i2, %N
   br i1 %cond2, label %body2, label %exit
 
 ; CHECK: exit:
-; CHECK-NOT: %stay =
 exit:
   ret void
 }

llvm/test/Transforms/LoopFusion/no_sink_hoist_volatile.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Could not hoist/sink all instructions
+
+declare void @unknown_func()
+
+define void @sink_preheader(i32 %N) {
+; CHECK:pre1:
+; CHECK-NEXT:  %ptr = alloca i32
+; CHECK-NEXT:  br label %body1
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+; CHECK:body1: 
+; CHECK-NOT: store volatile i32 3, i32* %ptr
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  br i1 %cond, label %body1, label %pre2
+
+; CHECK:pre2:
+; CHECK-NEXT: store volatile i32 3, i32* %ptr
+pre2:
+  store volatile i32 3, i32* %ptr
+  br label %body2
+
+; CHECK: body2:
+; CHECK-NOT: store volatile i32 3, i32* %ptr
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+; CHECK: exit:
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/sink_load.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+; CHECK: Safe to sink.
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @sink_preheader(i32 %N) {
+; CHECK-LABEL: @sink_preheader(
+; CHECK-NEXT:  pre1:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BODY1:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[BODY1]] ], [ 0, [[PRE1:%.*]] ]
+; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ [[I_NEXT2:%.*]], [[BODY1]] ], [ 0, [[PRE1]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[I]], [[N:%.*]]
+; CHECK-NEXT:    store i32 3, i32* [[PTR]], align 4
+; CHECK-NEXT:    [[I_NEXT2]] = add i32 1, [[I2]]
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ne i32 [[I2]], [[N]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[BODY1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[PTR]], align 4
+; CHECK-NEXT:    ret void
+;
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  store i32 3, i32* %ptr
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  %b = load i32, i32 * %ptr
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}

llvm/test/Transforms/LoopFusion/sink_store.ll

+; RUN: opt -S -loop-simplify -loop-fusion -debug-only=loop-fusion < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+@A = common global [100 x i32] zeroinitializer, align 16
+define void @sink_preheader(i32 %N) {
+; CHECK-LABEL: @sink_preheader(
+; CHECK-NEXT:  pre1:
+; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    br label [[BODY1:%.*]]
+; CHECK:       body1:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ [[I_NEXT:%.*]], [[BODY1]] ], [ 0, [[PRE1:%.*]] ]
+; CHECK-NEXT:    [[I2:%.*]] = phi i32 [ [[I_NEXT2:%.*]], [[BODY1]] ], [ 0, [[PRE1]] ]
+; CHECK-NEXT:    [[I_NEXT]] = add i32 1, [[I]]
+; CHECK-NEXT:    [[COND:%.*]] = icmp ne i32 [[I]], [[N:%.*]]
+; CHECK-NEXT:    [[B:%.*]] = load i32, i32* [[PTR]], align 4
+; CHECK-NEXT:    [[I_NEXT2]] = add i32 1, [[I2]]
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ne i32 [[I2]], [[N]]
+; CHECK-NEXT:    br i1 [[COND2]], label [[BODY1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    store i32 3, i32* [[PTR]], align 4
+; CHECK-NEXT:    ret void
+;
+pre1:
+  %ptr = alloca i32
+  br label %body1
+
+body1:  ; preds = %pre1, %body1
+  %i = phi i32 [%i_next, %body1], [0, %pre1]
+  %i_next = add i32 1, %i
+  %cond = icmp ne i32 %i, %N
+  %b = load i32, i32 * %ptr
+  br i1 %cond, label %body1, label %pre2
+
+pre2:
+  store i32 3, i32* %ptr
+  br label %body2
+
+body2:  ; preds = %pre2, %body2
+  %i2 = phi i32 [%i_next2, %body2], [0, %pre2]
+  %i_next2 = add i32 1, %i2
+  %cond2 = icmp ne i32 %i2, %N
+  br i1 %cond2, label %body2, label %exit
+
+exit:
+  ret void
+}