[LoopFusion] Move instructions from FC0.Latch to FC1.Latch.

[Whitney]

Summary

This PR move instructions from FC0.Latch bottom up to the beginning of FC1.Latch as long as they are proven safe.

To illustrate why this is beneficial, let's consider the following example:
Before Fusion:

header1:
  br header2
header2:
  br header2, latch1
latch1:
  br header1, preheader3
preheader3:
  br header3
header3:
  br header4
header4:
  br header4, latch3
latch3:
  br header3, exit3

After Fusion (before this PR):

header1:
  br header2
header2:
  br header2, latch1
latch1:
  br header3
header3:
  br header4
header4:
  br header4, latch3
latch3:
  br header1, exit3

Note that preheader3 is removed during fusion before this PR.
Notice that we cannot fuse loop2 with loop4 as there exists block latch1 in between.
This PR move instructions from latch1 to beginning of latch3, and remove block latch1. LoopFusion is now able to fuse loop nest recursively.
After Fusion (after this PR):

header1:
  br header2
header2:
  br header3
header3:
  br header4
header4:
  br header2, latch3
latch3:
  br header1, exit3

[Meinersbur]

Is there a mistake in the example? Every execution will end in the infinite loop header4. Why did you mean to move preheader3 instead of latch1?

[Whitney]

Is there a mistake in the example? Every execution will end in the infinite loop header4. Why did you mean to move preheader3 instead of latch1?

Sorry for the confusion, updated the description. The terminator of header4 should also branch to latch3. preheader3 is removed during fusion before this PR, updated the description to clarify that.

[jdoerfert]

I'm generally OK with this. Two comments below, otherwise assume I'm fine with it, I mean no need to wait for me.

We miss a negative test. I mean one with instruction(s) that cannot be moved.

I find it odd to add the same code twice. Please put it in helper functions.

llvm/test/Transforms/LoopFusion/loop_nest.ll

36

Nit: It might be good to commit the renaming of the instructions and the checking for them before as a NFC commit (no need to ask for a review).

[Whitney]

In D71165#1774492, @jdoerfert wrote:

We miss a negative test. I mean one with instruction(s) that cannot be moved.

Will create a new test.

I find it odd to add the same code twice. Please put it in helper functions.

In https://reviews.llvm.org/D65464, @kbarton said he will clean up the similar code between performFusion() and fuseGuardedLoops() in later patches, that's why I left it as duplication. I will still put my new code in helper functions anyways.

[Whitney]

Addressed Johannes's comments. Will do the NFC commit to rename instructions in one of the LITs after https://reviews.llvm.org/D71025 is landed.

[Meinersbur]

LGTM

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1134

[style]

for (Instruction &I : drop_begin(reverse(FromBB), 1))

1135

[suggestion] Can this be hoisted before the loop?

1139–1142

[style] https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

if (!isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
  break;

I.moveBefore(MovePos);

[Whitney]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1134

It need to be incremented before moveBefore as it move instructions out of FromBB.

1135

Is intentionally putted inside, ToBB.getFirstNonPHIOrDbg() returns a different value every iteration, as it will be the previous moved instruction.

1139–1142

I will actually remove the else break; as we want to move as much safe instructions as possible.

[Whitney]

Move moveInstsBottomUp to CodeMoverUtils.

[Meinersbur]

llvm/lib/Transforms/Scalar/LoopFuse.cpp

1134

Could you add a comment about why the Iterator is incremented where it is? I usually try to avoid iterator magic.

[Whitney]

Addressed Michael and Kit's comments.

[kbarton]

LGTM.

llvm/include/llvm/Transforms/Utils/CodeMoverUtils.h

bool isControlFlowEquivalent(const BasicBlock &BB0, const BasicBlock &BB1,
                              const DominatorTree &DT,
                              const PostDominatorTree &PDT);
 
 /// Return true if \p I can be safely moved before \p InsertPoint.
 bool isSafeToMoveBefore(Instruction &I, Instruction &InsertPoint,
                         const DominatorTree &DT, const PostDominatorTree &PDT,
                         DependenceInfo &DI);
 
+/// Move instructions from \p FromBB bottom up to the beginning of \p ToBB
+/// when proven safe.
+void moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
+                       const DominatorTree &DT, const PostDominatorTree &PDT,
+                       DependenceInfo &DI);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CODEMOVERUTILS_H

llvm/lib/Transforms/Scalar/LoopFuse.cpp

bool isEmptyPreheader(const FusionCandidate &FC) const {
     return FC.Preheader->size() == 1;
   }
 
   bool isEmptyExitBlock(const FusionCandidate &FC) const {
     assert(FC.ExitBlock && "Expecting a valid exit block");
     return FC.ExitBlock->size() == 1;
   }
 
+  /// Simplify the condition of the latch branch of \p FC to true, when both of
+  /// its successors are the same.
+  void simplifyLatchBranch(const FusionCandidate &FC) const {
+    BranchInst *FCLatchBranch = dyn_cast<BranchInst>(FC.Latch->getTerminator());
+    if (FCLatchBranch) {
+      assert(FCLatchBranch->isConditional() &&
+             FCLatchBranch->getSuccessor(0) == FCLatchBranch->getSuccessor(1) &&
+             "Expecting the two successors of FCLatchBranch to be the same");
+      FCLatchBranch->setCondition(
+          llvm::ConstantInt::getTrue(FCLatchBranch->getCondition()->getType()));
+    }
+  }
+
+  /// Move instructions from FC0.Latch to FC1.Latch. If FC0.Latch has an unique
+  /// successor, then merge FC0.Latch with its unique successor.
+  void mergeLatch(const FusionCandidate &FC0, const FusionCandidate &FC1) {
+    moveInstsBottomUp(*FC0.Latch, *FC1.Latch, DT, PDT, DI);
+    if (BasicBlock *Succ = FC0.Latch->getUniqueSuccessor()) {
+      MergeBlockIntoPredecessor(Succ, &DTU, &LI);
+      DTU.flush();
+    }
+  }
+
   /// Fuse two fusion candidates, creating a new fused loop.
   ///
   /// This method contains the mechanics of fusing two loops, represented by \p
   /// FC0 and \p FC1. It is assumed that \p FC0 dominates \p FC1 and \p FC1
   /// postdominates \p FC0 (making them control flow equivalent). It also
   /// assumes that the other conditions for fusion have been met: adjacent,
   /// identical trip counts, and no negative distance dependencies exist that
   /// would prevent fusion. Thus, there is no checking for these conditions in
   /// this method.
   ///
   /// Fusion is performed by rewiring the CFG to update successor blocks of the
for (PHINode *LCPHI : OriginalFC0PHIs) {
 
       LCPHI->setIncomingValue(L1LatchBBIdx, L1HeaderPHI);
     }
 
     // Replace latch terminator destinations.
     FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
     FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
 
+    // Change the condition of FC0 latch branch to true, as both successors of
+    // the branch are the same.
+    simplifyLatchBranch(FC0);
+
     // If FC0.Latch and FC0.ExitingBlock are the same then we have already
     // performed the updates above.
     if (FC0.Latch != FC0.ExitingBlock)
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Insert, FC0.Latch, FC1.Header));
 
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                        FC0.Latch, FC0.Header));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Insert,
                                                        FC1.Latch, FC0.Header));
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                        FC1.Latch, FC1.Header));
 
     // Update DT/PDT
     DTU.applyUpdates(TreeUpdates);
 
     LI.removeBlock(FC1.Preheader);
     DTU.deleteBB(FC1.Preheader);
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
+    // Note: Need to forget the loops before merging the loop latches, as
+    // mergeLatch may remove the only block in FC1.
     SE.forgetLoop(FC1.L);
     SE.forgetLoop(FC0.L);
 
+    // Move instructions from FC0.Latch to FC1.Latch.
+    // Note: mergeLatch requires an updated DT.
+    mergeLatch(FC0, FC1);
+
     // Merge the loops.
     SmallVector<BasicBlock *, 8> Blocks(FC1.L->block_begin(),
                                         FC1.L->block_end());
     for (BasicBlock *BB : Blocks) {
       FC0.L->addBlockEntry(BB);
       FC1.L->removeBlockFromLoop(BB);
       if (LI.getLoopFor(BB) != FC1.L)
         continue;
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
     }
 
     // Update the latches
 
     // Replace latch terminator destinations.
     FC0.Latch->getTerminator()->replaceUsesOfWith(FC0.Header, FC1.Header);
     FC1.Latch->getTerminator()->replaceUsesOfWith(FC1.Header, FC0.Header);
 
+    // Change the condition of FC0 latch branch to true, as both successors of
+    // the branch are the same.
+    simplifyLatchBranch(FC0);
+
     // If FC0.Latch and FC0.ExitingBlock are the same then we have already
     // performed the updates above.
     if (FC0.Latch != FC0.ExitingBlock)
       TreeUpdates.emplace_back(DominatorTree::UpdateType(
           DominatorTree::Insert, FC0.Latch, FC1.Header));
 
     TreeUpdates.emplace_back(DominatorTree::UpdateType(DominatorTree::Delete,
                                                        FC0.Latch, FC0.Header));
Loop *fuseGuardedLoops(const FusionCandidate &FC0,
 
     LI.removeBlock(FC1.Preheader);
     DTU.deleteBB(FC1.Preheader);
     DTU.deleteBB(FC0.ExitBlock);
     DTU.flush();
 
     // Is there a way to keep SE up-to-date so we don't need to forget the loops
     // and rebuild the information in subsequent passes of fusion?
+    // Note: Need to forget the loops before merging the loop latches, as
+    // mergeLatch may remove the only block in FC1.
     SE.forgetLoop(FC1.L);
     SE.forgetLoop(FC0.L);
 
+    // Move instructions from FC0.Latch to FC1.Latch.
+    // Note: mergeLatch requires an updated DT.
+    mergeLatch(FC0, FC1);
+
     // Merge the loops.
     SmallVector<BasicBlock *, 8> Blocks(FC1.L->block_begin(),
                                         FC1.L->block_end());
     for (BasicBlock *BB : Blocks) {
       FC0.L->addBlockEntry(BB);
       FC1.L->removeBlockFromLoop(BB);
       if (LI.getLoopFor(BB) != FC1.L)
         continue;

llvm/lib/Transforms/Utils/CodeMoverUtils.cpp

if (!isControlFlowEquivalent(I, InsertPoint, DT, PDT))
     return reportInvalidCandidate(I, NotControlFlowEquivalent);
 
   // As I and InsertPoint are control flow equivalent, if I dominates
   // InsertPoint, then I comes before InsertPoint.
   const bool MoveForward = DT.dominates(&I, &InsertPoint);
   if (MoveForward) {
     // When I is being moved forward, we need to make sure the InsertPoint
     // dominates every users. Or else, a user may be using an undefined I.
-    for (const Value *User : I.users())
-      if (auto *UserInst = dyn_cast<Instruction>(User))
-        if (!DT.dominates(&InsertPoint, UserInst))
+    for (const Use &U : I.uses())
+      if (auto *UserInst = dyn_cast<Instruction>(U.getUser()))
+        if (UserInst != &InsertPoint && !DT.dominates(&InsertPoint, U))
           return false;
   } else {
     // When I is being moved backward, we need to make sure all its opernads
     // dominates the InsertPoint. Or else, an operand may be undefined for I.
     for (const Value *Op : I.operands())
       if (auto *OpInst = dyn_cast<Instruction>(Op))
         if (&InsertPoint == OpInst || !DT.dominates(OpInst, &InsertPoint))
           return false;
if (std::any_of(InstsToCheck.begin(), InstsToCheck.end(),
                          DepResult->isAnti()))
                       return true;
                     return false;
                   }))
     return reportInvalidCandidate(I, HasDependences);
 
   return true;
 }
+
+void llvm::moveInstsBottomUp(BasicBlock &FromBB, BasicBlock &ToBB,
+                             const DominatorTree &DT,
+                             const PostDominatorTree &PDT, DependenceInfo &DI) {
+  for (auto It = ++FromBB.rbegin(); It != FromBB.rend();) {
+    Instruction *MovePos = ToBB.getFirstNonPHIOrDbg();
+    Instruction &I = *It;
+    // Increment the iterator before modifying FromBB.
+    ++It;
+
+    if (isSafeToMoveBefore(I, *MovePos, DT, PDT, DI))
+      I.moveBefore(MovePos);
+  }
+}

llvm/test/Transforms/LoopFusion/four_loops.ll

 ; RUN: opt -S -loop-fusion < %s | FileCheck %s
 
 @A = common global [1024 x i32] zeroinitializer, align 16
 @B = common global [1024 x i32] zeroinitializer, align 16
 @C = common global [1024 x i32] zeroinitializer, align 16
 @D = common global [1024 x i32] zeroinitializer, align 16
 
 ; CHECK: void @dep_free
 ; CHECK-NEXT: bb:
 ; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]+]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]+]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2BODY:bb[0-9]+]], label %[[LOOP2BODY]]
+; CHECK: br label %[[LOOP2BODY:bb[0-9]+]]
 ; CHECK: [[LOOP2BODY]]
-; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
-; CHECK: [[LOOP2LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP3BODY:bb[0-9]+]], label %[[LOOP3BODY]]
+; CHECK: br label %[[LOOP3BODY:bb[0-9]+]]
 ; CHECK: [[LOOP3BODY]]
-; CHECK: br label %[[LOOP3LATCH:bb[0-9]+]]
-; CHECK: [[LOOP3LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP4BODY:bb[0-9]+]], label %[[LOOP4BODY]]
+; CHECK: br label %[[LOOP4BODY:bb[0-9]+]]
 ; CHECK: [[LOOP4BODY]]
-; CHECK: br label %[[LOOP4LATCH:bb[0-9]+]]
-; CHECK: [[LOOP4LATCH]]
+; CHECK: br label %[[LOOP1LATCH:bb[0-9]+]]
+; CHECK: [[LOOP1LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[LOOPEXIT:bb[0-9]+]]
 ; CHECK: ret void
 define void @dep_free() {
 bb:
   br label %bb15
 
 bb25.preheader:                                   ; preds = %bb22
   br label %bb27

llvm/test/Transforms/LoopFusion/guarded.ll

 ; RUN: opt -S -loop-fusion < %s | FileCheck %s
 
 @B = common global [1024 x i32] zeroinitializer, align 16
 
 ; CHECK: void @dep_free_parametric
 ; CHECK-next: entry:
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1PREHEADER:bb[0-9]*]], label %[[LOOP1SUCC:bb[0-9]+]]
 ; CHECK: [[LOOP1PREHEADER]]
 ; CHECK-NEXT: br label %[[LOOP1BODY:bb[0-9]*]]
 ; CHECK: [[LOOP1BODY]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2BODY:bb[0-9]*]], label %[[LOOP2BODY]]
-; CHECK: [[LOOP2BODY]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1BODY]], label %[[LOOP2EXIT:bb[0-9]+]]
 ; CHECK: [[LOOP2EXIT]]
 ; CHECK: br label %[[LOOP1SUCC]]
 ; CHECK: [[LOOP1SUCC]]
 ; CHECK: ret void
 define void @dep_free_parametric(i32* noalias %A, i64 %N) {
 entry:
   %cmp4 = icmp slt i64 0, %N

llvm/test/Transforms/LoopFusion/loop_nest.ll

 @B = common global [1024 x [1024 x i32]] zeroinitializer, align 16
 
 ; CHECK: void @dep_free
 ; CHECK-NEXT: bb:
 ; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]+]]
 ; CHECK: [[LOOP1HEADER]]
 ; CHECK: br label %[[LOOP3HEADER:bb[0-9]+]]
 ; CHECK: [[LOOP3HEADER]]
-; CHECK: br label %[[LOOP3LATCH:bb[0-9]+]]
-; CHECK: [[LOOP3LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP3HEADER]], label %[[LOOP1LATCH:bb[0-9]+]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2PREHEADER:bb[0-9]+]], label %[[LOOP2PREHEADER]]
-; CHECK: [[LOOP2PREHEADER]]
+; CHECK: br label %[[LOOP2HEADER:bb[0-9]+]]
+; CHECK: [[LOOP2HEADER]]
 ; CHECK: br label %[[LOOP4HEADER:bb[0-9]+]]
 ; CHECK: [[LOOP4HEADER]]
-; CHECK: br label %[[LOOP4LATCH:bb[0-9]+]] 
-; CHECK: [[LOOP4LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP4HEADER]], label %[[LOOP2LATCH:bb[0-9]+]]
-; CHECK: [[LOOP2LATCH]]
-; CHECK:  br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[LOOP1EXIT:bb[0-9]*]]
+; CHECK: br i1 %{{.*}}, label %[[LOOP3HEADER]], label %[[LOOP1LATCH:bb[0-9]+]]
+; CHECK: [[LOOP1LATCH]]
+; CHECK-NEXT: %inc.outer.fc0 = add nuw nsw i64 %indvars.iv105, 1
+; CHECK-NEXT: %add.outer.fc0 = add nuw nsw i32 %.06, 1
+; CHECK-NEXT: %cmp.outer.fc0 = icmp ne i64 %inc.outer.fc0, 100
+; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[LOOP1EXIT:bb[0-9]*]]
 ; CHECK: ret void
 
 ; TODO: The current version of loop fusion does not allow the inner loops to be
 ; fused because they are not control flow equivalent and adjacent. These are
 ; limitations that can be addressed in future improvements to fusion.
 define void @dep_free() {
 bb:
   br label %bb16
 
 bb16:                                   ; preds = %bb, %bb27
-  %.06 = phi i32 [ 0, %bb ], [ %tmp28, %bb27 ]
-  %indvars.iv105 = phi i64 [ 0, %bb ], [ %indvars.iv.next11, %bb27 ]
+  %.06 = phi i32 [ 0, %bb ], [ %add.outer.fc0, %bb27 ]
+  %indvars.iv105 = phi i64 [ 0, %bb ], [ %inc.outer.fc0, %bb27 ]
   br label %bb18
 
 bb30:                                   ; preds = %bb27
   br label %bb33
 
 bb18:                                             ; preds = %bb16, %bb25
   %indvars.iv74 = phi i64 [ 0, %bb16 ], [ %indvars.iv.next8, %bb25 ]
   %tmp = add nsw i32 %.06, -3
   %tmp19 = add nuw nsw i64 %indvars.iv105, 3
   %tmp20 = trunc i64 %tmp19 to i32
   %tmp21 = mul nsw i32 %tmp, %tmp20
   %tmp22 = trunc i64 %indvars.iv105 to i32
   %tmp23 = srem i32 %tmp21, %tmp22
   %tmp24 = getelementptr inbounds [1024 x [1024 x i32]], [1024 x [1024 x i32]]* @A, i64 0, i64 %indvars.iv105, i64 %indvars.iv74
   store i32 %tmp23, i32* %tmp24, align 4
   br label %bb25
 
 bb25:                                             ; preds = %bb18
   %indvars.iv.next8 = add nuw nsw i64 %indvars.iv74, 1
   %exitcond9 = icmp ne i64 %indvars.iv.next8, 100
   br i1 %exitcond9, label %bb18, label %bb27
 
 bb27:                                             ; preds = %bb25
-  %indvars.iv.next11 = add nuw nsw i64 %indvars.iv105, 1
-  %tmp28 = add nuw nsw i32 %.06, 1
-  %exitcond12 = icmp ne i64 %indvars.iv.next11, 100
-  br i1 %exitcond12, label %bb16, label %bb30
+  %inc.outer.fc0 = add nuw nsw i64 %indvars.iv105, 1
+  %add.outer.fc0 = add nuw nsw i32 %.06, 1
+  %cmp.outer.fc0 = icmp ne i64 %inc.outer.fc0, 100
+  br i1 %cmp.outer.fc0, label %bb16, label %bb30
 
 bb33:                                   ; preds = %bb30, %bb45
   %.023 = phi i32 [ 0, %bb30 ], [ %tmp46, %bb45 ]
   %indvars.iv42 = phi i64 [ 0, %bb30 ], [ %indvars.iv.next5, %bb45 ]
   br label %bb35
 
 bb31:                                             ; preds = %bb45
   br label %bb47

llvm/test/Transforms/LoopFusion/simple.ll

 ; RUN: opt -S -loop-fusion < %s | FileCheck %s
 
 @B = common global [1024 x i32] zeroinitializer, align 16
 
 ; CHECK: void @dep_free
 ; CHECK-NEXT: bb:
 ; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]*]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2HEADER:bb[0-9]+]], label %[[LOOP2HEADER]]
+; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP2HEADER]]
 ; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
 ; CHECK: [[LOOP2LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
 ; CHECK: ret void
 define void @dep_free(i32* noalias %arg) {
 bb:
   br label %bb7

 }
 
 ; CHECK: void @dep_free_parametric
 ; CHECK-NEXT: bb:
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1PREHEADER:bb[0-9.a-z]*]], label %[[EXITBLOCK:bb[0-9]*]]
 ; CHECK: [[LOOP1PREHEADER]]
 ; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]*]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2HEADER:bb[0-9]*]], label %[[LOOP2HEADER]]
+; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP2HEADER]]
 ; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
 ; CHECK: [[LOOP2LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[EXITBLOCK]]
 ; CHECK: ret void
 define void @dep_free_parametric(i32* noalias %arg, i64 %arg2) {
 bb:
   %tmp3 = icmp slt i64 0, %arg2

 bb27:                                             ; preds = %bb17
   ret void
 }
 
 ; CHECK: void @raw_only
 ; CHECK-NEXT: bb:
 ; CHECK-NEXT: br label %[[LOOP1HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]*]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2HEADER:bb[0-9]+]], label %[[LOOP2HEADER]]
+; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP2HEADER]]
 ; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
 ; CHECK: [[LOOP2LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
 ; CHECK: ret void
 define void @raw_only(i32* noalias %arg) {
 bb:
   br label %bb7

 }
 
 ; CHECK: void @raw_only_parametric
 ; CHECK-NEXT: bb:
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1PREHEADER:bb[0-9.a-z]*]], label %[[EXITBLOCK:bb[0-9]*]]
 ; CHECK: [[LOOP1PREHEADER]]
 ; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2HEADER:bb[0-9]*]], label %[[LOOP2HEADER]]
-; CHECK: [[LOOP2HEADER]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %[[EXITBLOCK]]
 ; CHECK: ret void
 define void @raw_only_parametric(i32* noalias %arg, i32 %arg4) {
 bb:
   %tmp = sext i32 %arg4 to i64
   %tmp64 = icmp sgt i32 %arg4, 0
   br i1 %tmp64, label %bb8, label %bb23
 

 bb23:                                             ; preds = %bb17, %bb
   ret void
 }
 
 ; CHECK: void @forward_dep
 ; CHECK-NEXT: bb:
 ; CHECK: br label %[[LOOP1HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP1HEADER]]
-; CHECK: br label %[[LOOP1LATCH:bb[0-9]*]]
-; CHECK: [[LOOP1LATCH]]
-; CHECK: br i1 %{{.*}}, label %[[LOOP2HEADER:bb[0-9]+]], label %[[LOOP2HEADER]]
+; CHECK: br label %[[LOOP2HEADER:bb[0-9]*]]
 ; CHECK: [[LOOP2HEADER]]
 ; CHECK: br label %[[LOOP2LATCH:bb[0-9]+]]
 ; CHECK: [[LOOP2LATCH]]
 ; CHECK: br i1 %{{.*}}, label %[[LOOP1HEADER]], label %{{.*}}
 ; CHECK: ret void
 define void @forward_dep(i32* noalias %arg) {
 bb:
   br label %bb7

 bb25:                                             ; preds = %bb19
   %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
   %exitcond = icmp ne i64 %indvars.iv.next, 100
   br i1 %exitcond, label %bb19, label %bb26
 
 bb26:                                             ; preds = %bb25
   ret void
 }
+
+; Test that instructions in loop 1 latch are moved to the beginning of loop 2
+; latch iff it is proven safe. %inc.first and %cmp.first are moved, but
+; `store i32 0, i32* %Ai.first` is not.
+
+; CHECK: void @flow_dep
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br label %for.first
+; CHECK-LABEL: for.first:
+; CHECK: store i32 0, i32* %Ai.first
+; CHECK: %Ai.second =
+; CHECK: br label %for.second.latch
+; CHECK-LABEL: for.second.latch:
+; CHECK-NEXT: %inc.first = add nsw i64 %i.first, 1
+; CHECK-NEXT: %cmp.first = icmp slt i64 %inc.first, 100
+; CHECK: br i1 %cmp.second, label %for.first, label %for.end
+; CHECK-LABEL: for.end:
+; CHECK-NEXT: ret void
+
+define void @flow_dep(i32* noalias %A, i32* noalias %B) {
+entry:
+  br label %for.first
+
+for.first:
+  %i.first = phi i64 [ 0, %entry ], [ %inc.first, %for.first ]
+  %Ai.first = getelementptr inbounds i32, i32* %A, i64 %i.first
+  store i32 0, i32* %Ai.first, align 4
+  %inc.first = add nsw i64 %i.first, 1
+  %cmp.first = icmp slt i64 %inc.first, 100
+  br i1 %cmp.first, label %for.first, label %for.second.preheader
+
+for.second.preheader:
+  br label %for.second
+
+for.second:
+  %i.second = phi i64 [ %inc.second, %for.second.latch ], [ 0, %for.second.preheader ]
+  %Ai.second = getelementptr inbounds i32, i32* %A, i64 %i.second
+  %0 = load i32, i32* %Ai.second, align 4
+  %Bi = getelementptr inbounds i32, i32* %B, i64 %i.second
+  store i32 %0, i32* %Bi, align 4
+  br label %for.second.latch
+
+for.second.latch:
+  %inc.second = add nsw i64 %i.second, 1
+  %cmp.second = icmp slt i64 %inc.second, 100
+  br i1 %cmp.second, label %for.second, label %for.end
+
+for.end:
+  ret void
+}