[LoopBoundSplit] Handle the case in which exiting block is loop header

[jaykang10]

Summary

If exiting block is loop header, phi node could be AddRecValue. Handle the case.

It is for fixing https://bugs.llvm.org/show_bug.cgi?id=51866.

[mkazantsev]

I completely don't understand neither what happened nor the fix. Could you please give more details on how and why this bug is happening?

[jaykang10]

In D110060#3011621, @mkazantsev wrote:

I completely don't understand neither what happened nor the fix. Could you please give more details on how and why this bug is happening?

Sorry for poor explanation... Let me try to explain something more.

We need to update the IV's start value in post loop. In the example from https://bugs.llvm.org/show_bug.cgi?id=51866, the IV's start value in post loop is not updated correctly as below.
%i.0.split = phi i16 [ %inc.split, %for.inc.split ], [ 0, %for.cond.split.preheader ].
As @uabelho mentioned, it should be [ 5, %for.cond.split.preheader ].

The code has expected the ExitingCond.AddRecValue is add instruction like %inc = add nuw nsw i16 %i.0, 1. The ExitingCond.AddRecValue is calculated from exiting block's condition. For example,

for.inc:
  %inc = add nuw nsw i64 %iv, 1
  %cond = icmp sgt i64 %inc, %n
  br i1 %cond, label %exit, label %loop

In above example, the latch is exiting block and the ExitingCond.AddRecValue is %inc = add nuw nsw i64 %iv, 1.

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i16 [ 0, %entry ], [ %inc, %for.inc ]
  %exitcond.not = icmp eq i16 %i.0, 10
  br i1 %exitcond.not, label %for.end, label %for.body

In above example, the header is exiting block and the ExitingCond.AddRecValue is %i.0 = phi i16 [ 0, %entry ], [ %inc, %for.inc ]. Previously, the code missed this case.

This patch detects this case and update the IV's start value in post loop correctly. If you feel something wrong, please let me know.

[mkazantsev]

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

64

Could you please add one more Phi next to it (starting from different value, say 10) and make sure it's also properly updated? I don't understand how it will be done.

[jaykang10]

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

64

You are right! Multiple IVs are not updated with this patch. Let me try to handle it. Thanks @mkazantsev

[jaykang10]

https://reviews.llvm.org/D110060 is merged into this patch.

Following the comment of @mkazantsev, updated patch.

• If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with value from backedge.
• Use Cond.NonPHIAddRecValue when the start value of IV in post loop is updated.

[jaykang10]

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

64

I have added %i.1 = phi i16 [ 10, %entry ], [ %inc, %for.inc ]. It is not updated because it is not SCEVAddRecExpr.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

81

You can use L.getLoopPreheader or L.getLoopPredecessor to find a block from which a non-loop value is coming.

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

39

Why is it 10 again?

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

81

Yep, let me update it.

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

39

Ah, you are right! I made a mistake. The incoming value from preheader in post-loop should be new bound. Let me update it.

[jaykang10]

Following comments from @mkazantsev, updated patch.

[mkazantsev]

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

39

And why is it 5?.. It should be 15, no?

[jaykang10]

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

39

um... The %i.1 is not AddRecExpr...

for.cond: 
  %i.0 = phi i16 [ 0, %entry ], [ %inc, %for.inc ]
  %i.1 = phi i16 [ 10, %entry ], [ %inc, %for.inc ]
...
for.inc:                                          ; preds = %if.else, %if.then
  %inc = add nuw nsw i16 %i.0, 1

The value of %i.1 will be 10 at first iteration and it will follow %inc at next iterations. In this case, the start value of %i.1 in post loop is 5. If %i.1 is AddRecExpr as below, the start value will be 15.

for.cond: 
  %i.0 = phi i16 [ 0, %entry ], [ %inc, %for.inc ]
  %i.1 = phi i16 [ 10, %entry ], [ %inc.1, %for.inc ]
...
for.inc:                                          ; preds = %if.else, %if.then
  %inc = add nuw nsw i16 %i.0, 1
  %inc.1 = add nuw nsw i16 %i.1, 1

I think you mention the case where the phi is AddRecExpr and the code is missing the case. Let me check and update the code. Thanks for the detailed review.

[jaykang10]

Update the incoming value of phi nodes in header of post-loop correctly.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

417

This is fundamentally wrong for two reasons.

First - we should never base our logic on SCEV's ability to prove some fact, even if we know this for sure and SCEV was able to prove the very same thing in the past.

In particular - we should not even rely on (quite obvious) assumption that SCEV will always be able to prove that something that is increases by a constant has AddRecSCEV. It is likely to happen, but SCEV has *no guarantees* that it will surely prove things.

Second - and what about phis that are not addrecs? Do they not need update? For example, imagine code

for (i = 2; i < N; i = i * i) {...}

The phi here won't be an addrec. But it will still need an update when you change the iteration space, or at least I don't see any reason why it won't.

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

417

You are right. Let me think about how to handle the phis.

[jaykang10]

Update phi nodes in header of post-loop using LCSSA.

We can say that the start value of phi node in post-loop is the value of phi node at last iteration in pre-loop. Let's see a simple example.

for.body:
  %i = phi i16 [ 0, %entry ], [ %add, %cond.end ]
  %cmp1 = icmp ult i16 %i, 3
  br i1 %cmp1, label %cond.true, label %cond.false

cond.true:
  br label %cond.end

cond.false:
  br label %cond.end

cond.end:
  %call = call i16 @foo()
  %add = add nuw nsw i16 %i, 1
  %cmp2 = icmp ult i16 %i, 11
  br i1 %cmp2, label %for.body, label %end

In above example, we can add a LCSSA Phi node in exit block of pre-loop and update the start value of the phi node with the LCSSA one as below.

entry.split.split:
  %i.lcssa = phi i16 [ %add, %cond.end ]
...
for.body.split.preheader:
  br label %for.body.split
...
for.body.split:
  %i.split = phi i16 [ %add.split, %cond.end.split ], [ %i.lcssa, %for.body.split.preheader ]

In this example, the value of phi node at last iteration is %add because the exiting condition uses it.

If the exiting block is not loop latch, we need to update the phi node differently. Let's see other example.

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i16 [ 0, %entry ], [ %inc.0, %for.inc ]
  %exitcond.not = icmp eq i16 %i.0, 10
  br i1 %exitcond.not, label %for.end, label %for.body

for.body:
  %cmp1 = icmp ult i16 %i.0, 5
  %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 %i.0
  %0 = load i16, i16* %arrayidx, align 1
  br i1 %cmp1, label %if.then, label %if.else

if.then:
  br label %for.inc

if.else:
  br label %for.inc

for.inc:
  %inc.0 = add nuw nsw i16 %i.0, 1

For above example, we can add the LCSSA phi node as below.

entry.split.split:
  %i.0.lcssa = phi i16 [ %i.0, %for.cond ]
...
for.cond.split.preheader:
  br label %for.cond.split
...
for.cond.split:
  %i.0.split = phi i16 [ %inc.0.split, %for.inc.split ], [ %i.0.lcssa, %for.cond.split.preheader ]

In this example, the value of phi node at last iteration is %i.0 because the exiting condition uses it.

Based on this logic, the patch is updated. @mkazantsev If you feel something wrong, please let me know.

[jaykang10]

Sorry for ping.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

48

Please split out SCEV -> SCEVAddRecExpr refactoring in a separate NFC patch. It can go before the others.

66

Cast not needed.

66

Ignore this, I misread the code.

69

I guess this is impossible after you've ensured that AddRecSCEV is an addrec actually. Or can it be null?

69

Ignore this too.

396

What happens if there is more than one phi that will fit?

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

39

Got it, I misread this IR and didn't notice the entry block was %inc. Thanks for clarification.

[mkazantsev]

Look fine as far as I can tell, but please split out the SCEV->AddRec refactoring into a separate NFC patch to reduce the scope of change here.

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

48

Yep, let me split this patch into two patches.

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

396

um... you are right. It will pick up just last phi node which could be wrong... Let me update the code.

[jaykang10]

Following comments of @mkazantsev, updated patch

• Split the patch into two
• Find PHI with exiting condition from pre-loop correctly

[jaykang10]

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

396

I have added code to check whether the phi node is SCEVAddRecExpr or not. After that, we can see below expected output.

; CHECK-NEXT:    [[EXITCOND_NOT_SPLIT:%.*]] = icmp eq i16 [[I_0_SPLIT]], 10

Previously, it was I_1_SPLIT intead of I_0_SPLIT.

The PHIs can have same incoming value from backedge but only one can be SCEVAddRecExpr as below.

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i16 [ 0, %entry ], [ %inc.0, %for.inc ]
  %i.1 = phi i16 [ 10, %entry ], [ %inc.0, %for.inc ]
...
for.inc:                                          ; preds = %if.else, %if.then
  %inc.0 = add nuw nsw i16 %i.0, 1
...

@mkazantsev if you feel something wrong, please let me know. If it is correct, let me push this patch.

llvm/lib/Transforms/Scalar/LoopBoundSplit.cpp

struct ConditionInfo {
   /// Branch instruction with this condition
   BranchInst *BI;
   /// ICmp instruction with this condition
   ICmpInst *ICmp;
   /// Preciate info
   ICmpInst::Predicate Pred;
   /// AddRec llvm value
   Value *AddRecValue;
+  /// Non PHI AddRec llvm value
+  Value *NonPHIAddRecValue;
   /// Bound llvm value
   Value *BoundValue;
   /// AddRec SCEV
-  const SCEV *AddRecSCEV;
+  const SCEVAddRecExpr *AddRecSCEV;
   /// Bound SCEV
   const SCEV *BoundSCEV;
 
   ConditionInfo()
       : BI(nullptr), ICmp(nullptr), Pred(ICmpInst::BAD_ICMP_PREDICATE),
         AddRecValue(nullptr), BoundValue(nullptr), AddRecSCEV(nullptr),
         BoundSCEV(nullptr) {}
 };
 } // namespace
 
 static void analyzeICmp(ScalarEvolution &SE, ICmpInst *ICmp,
-                        ConditionInfo &Cond) {
+                        ConditionInfo &Cond, const Loop &L) {
   Cond.ICmp = ICmp;
   if (match(ICmp, m_ICmp(Cond.Pred, m_Value(Cond.AddRecValue),
                          m_Value(Cond.BoundValue)))) {
-    Cond.AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
-    Cond.BoundSCEV = SE.getSCEV(Cond.BoundValue);
+    const SCEV *AddRecSCEV = SE.getSCEV(Cond.AddRecValue);
+    const SCEV *BoundSCEV = SE.getSCEV(Cond.BoundValue);
+    const SCEVAddRecExpr *LHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
+    const SCEVAddRecExpr *RHSAddRecSCEV = dyn_cast<SCEVAddRecExpr>(BoundSCEV);
     // Locate AddRec in LHSSCEV and Bound in RHSSCEV.
-    if (isa<SCEVAddRecExpr>(Cond.BoundSCEV) &&
-        !isa<SCEVAddRecExpr>(Cond.AddRecSCEV)) {
+    if (!LHSAddRecSCEV && RHSAddRecSCEV) {
       std::swap(Cond.AddRecValue, Cond.BoundValue);
-      std::swap(Cond.AddRecSCEV, Cond.BoundSCEV);
+      std::swap(AddRecSCEV, BoundSCEV);
       Cond.Pred = ICmpInst::getSwappedPredicate(Cond.Pred);
     }
+
+    Cond.AddRecSCEV = dyn_cast<SCEVAddRecExpr>(AddRecSCEV);
+    Cond.BoundSCEV = BoundSCEV;
+    Cond.NonPHIAddRecValue = Cond.AddRecValue;
+
+    // If the Cond.AddRecValue is PHI node, update Cond.NonPHIAddRecValue with
+    // value from backedge.
+    if (Cond.AddRecSCEV && isa<PHINode>(Cond.AddRecValue)) {
+      PHINode *PN = cast<PHINode>(Cond.AddRecValue);
+      for (auto i : seq<int>(0, PN->getNumOperands())) {
+        if (L.contains(PN->getIncomingBlock(i))) {
+          Cond.NonPHIAddRecValue = PN->getIncomingValue(i);
+          break;
+        }
+      }
+    }
   }
 }
 
 static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
                                 ConditionInfo &Cond, bool IsExitCond) {
   if (IsExitCond) {
     const SCEV *ExitCount = SE.getExitCount(&L, Cond.ICmp->getParent());
     if (isa<SCEVCouldNotCompute>(ExitCount))
static bool calculateUpperBound(const Loop &L, ScalarEvolution &SE,
   // ToDo: Support ICMP_NE/EQ.
 
   return false;
 }
 
 static bool hasProcessableCondition(const Loop &L, ScalarEvolution &SE,
                                     ICmpInst *ICmp, ConditionInfo &Cond,
                                     bool IsExitCond) {
-  analyzeICmp(SE, ICmp, Cond);
+  analyzeICmp(SE, ICmp, Cond, L);
 
   // The BoundSCEV should be evaluated at loop entry.
   if (!SE.isAvailableAtLoopEntry(Cond.BoundSCEV, &L))
     return false;
 
-  const SCEVAddRecExpr *AddRecSCEV = dyn_cast<SCEVAddRecExpr>(Cond.AddRecSCEV);
   // Allowed AddRec as induction variable.
-  if (!AddRecSCEV)
+  if (!Cond.AddRecSCEV)
     return false;
 
-  if (!AddRecSCEV->isAffine())
+  if (!Cond.AddRecSCEV->isAffine())
     return false;
 
-  const SCEV *StepRecSCEV = AddRecSCEV->getStepRecurrence(SE);
+  const SCEV *StepRecSCEV = Cond.AddRecSCEV->getStepRecurrence(SE);
   // Allowed constant step.
   if (!isa<SCEVConstant>(StepRecSCEV))
     return false;
 
   ConstantInt *StepCI = cast<SCEVConstant>(StepRecSCEV)->getValue();
   // Allowed positive step for now.
   // TODO: Support negative step.
   if (StepCI->isNegative() || StepCI->isZero())
for (auto *BB : L.blocks()) {
 
     if (ExitingCond.BoundSCEV->getType() !=
         SplitCandidateCond.BoundSCEV->getType())
       continue;
 
     // After transformation, we assume the split condition of the pre-loop is
     // always true. In order to guarantee it, we need to check the start value
     // of the split cond AddRec satisfies the split condition.
-    const SCEV *SplitAddRecStartSCEV =
-        cast<SCEVAddRecExpr>(SplitCandidateCond.AddRecSCEV)->getStart();
-    if (!SE.isKnownPredicate(SplitCandidateCond.Pred, SplitAddRecStartSCEV,
+    if (!SE.isLoopEntryGuardedByCond(&L, SplitCandidateCond.Pred,
+                                     SplitCandidateCond.AddRecSCEV->getStart(),
                                      SplitCandidateCond.BoundSCEV))
       continue;
 
     SplitCandidateCond.BI = BI;
     return BI;
   }
 
   return nullptr;
 }
static bool splitLoopBound(Loop &L, DominatorTree &DT, LoopInfo &LI,
   SCEVExpander Expander(
       SE, L.getHeader()->getParent()->getParent()->getDataLayout(), "split");
   Instruction *InsertPt = SplitLoopPH->getTerminator();
   Value *NewBoundValue =
       Expander.expandCodeFor(NewBoundSCEV, NewBoundSCEV->getType(), InsertPt);
   NewBoundValue->setName("new.bound");
 
   // Replace exiting bound value of pre-loop NewBound.
   ExitingCond.ICmp->setOperand(1, NewBoundValue);
 
   // Replace IV's start value of post-loop by NewBound.
   for (PHINode &PN : L.getHeader()->phis()) {
     // Find PHI with exiting condition from pre-loop.
     if (SE.isSCEVable(PN.getType()) && isa<SCEVAddRecExpr>(SE.getSCEV(&PN))) {
       for (Value *Op : PN.incoming_values()) {
-        if (Op == ExitingCond.AddRecValue) {
+        if (Op == ExitingCond.NonPHIAddRecValue) {
           // Find cloned PHI for post-loop.
           PHINode *PostLoopPN = cast<PHINode>(VMap[&PN]);
           PostLoopPN->setIncomingValueForBlock(PostLoopPreHeader,
                                                NewBoundValue);
         }
       }
     }
   }
 
   // Replace SplitCandidateCond.BI's condition of pre-loop by True.
   LLVMContext &Context = PreHeader->getContext();
   SplitCandidateCond.BI->setCondition(ConstantInt::getTrue(Context));
 
   // Replace cloned SplitCandidateCond.BI's condition in post-loop by False.
   BranchInst *ClonedSplitCandidateBI =
       cast<BranchInst>(VMap[SplitCandidateCond.BI]);
   ClonedSplitCandidateBI->setCondition(ConstantInt::getFalse(Context));
 
   // Replace exit branch target of pre-loop by post-loop's preheader.
   if (L.getExitBlock() == ExitingCond.BI->getSuccessor(0))
     ExitingCond.BI->setSuccessor(0, PostLoopPreHeader);
   else

llvm/test/Transforms/LoopBoundSplit/bug-loop-bound-split-phi-in-exit-block.ll

 ; CHECK:       entry.split.split:
 ; CHECK-NEXT:    [[CALL_LCSSA1:%.*]] = phi i16 [ [[CALL]], [[COND_END]] ]
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i16 [ [[I]], [[COND_END]] ]
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ne i16 [[I_LCSSA]], 11
 ; CHECK-NEXT:    br i1 [[TMP0]], label [[FOR_BODY_SPLIT_PREHEADER:%.*]], label [[END:%.*]]
 ; CHECK:       for.body.split.preheader:
 ; CHECK-NEXT:    br label [[FOR_BODY_SPLIT:%.*]]
 ; CHECK:       for.body.split:
-; CHECK-NEXT:    [[I_SPLIT:%.*]] = phi i16 [ [[ADD_SPLIT:%.*]], [[COND_END_SPLIT:%.*]] ], [ 0, [[FOR_BODY_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[I_SPLIT:%.*]] = phi i16 [ [[ADD_SPLIT:%.*]], [[COND_END_SPLIT:%.*]] ], [ 3, [[FOR_BODY_SPLIT_PREHEADER]] ]
 ; CHECK-NEXT:    [[CMP1_SPLIT:%.*]] = icmp ult i16 [[I_SPLIT]], 3
 ; CHECK-NEXT:    br i1 false, label [[COND_TRUE_SPLIT:%.*]], label [[COND_FALSE_SPLIT:%.*]]
 ; CHECK:       cond.false.split:
 ; CHECK-NEXT:    br label [[COND_END_SPLIT]]
 ; CHECK:       cond.true.split:
 ; CHECK-NEXT:    br label [[COND_END_SPLIT]]
 ; CHECK:       cond.end.split:
 ; CHECK-NEXT:    [[CALL_SPLIT:%.*]] = call i16 @foo()

llvm/test/Transforms/LoopBoundSplit/bug51866.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt  -passes=loop-bound-split -S < %s | FileCheck %s
+
+@B = external global [10 x i16], align 1
+
+define void @test() {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[ENTRY_SPLIT:%.*]]
+; CHECK:       entry.split:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[I_0:%.*]] = phi i16 [ 0, [[ENTRY_SPLIT]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_1:%.*]] = phi i16 [ 10, [[ENTRY_SPLIT]] ], [ [[INC]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i16 [[I_0]], 5
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[ENTRY_SPLIT_SPLIT:%.*]], label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i16 [[I_0]], 5
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 [[I_0]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, i16* [[ARRAYIDX]], align 1
+; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    call void @foo(i16 [[TMP0]])
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @bar(i16 [[TMP0]])
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       entry.split.split:
+; CHECK-NEXT:    [[I_0_LCSSA:%.*]] = phi i16 [ [[I_0]], [[FOR_COND]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i16 [[I_0_LCSSA]], 10
+; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_COND_SPLIT_PREHEADER:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.cond.split.preheader:
+; CHECK-NEXT:    br label [[FOR_COND_SPLIT:%.*]]
+; CHECK:       for.cond.split:
+; CHECK-NEXT:    [[I_0_SPLIT:%.*]] = phi i16 [ [[INC_SPLIT:%.*]], [[FOR_INC_SPLIT:%.*]] ], [ 5, [[FOR_COND_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[I_1_SPLIT:%.*]] = phi i16 [ [[INC_SPLIT]], [[FOR_INC_SPLIT]] ], [ 10, [[FOR_COND_SPLIT_PREHEADER]] ]
+; CHECK-NEXT:    [[EXITCOND_NOT_SPLIT:%.*]] = icmp eq i16 [[I_0_SPLIT]], 10
+; CHECK-NEXT:    br i1 [[EXITCOND_NOT_SPLIT]], label [[FOR_END_LOOPEXIT:%.*]], label [[FOR_BODY_SPLIT:%.*]]
+; CHECK:       for.body.split:
+; CHECK-NEXT:    [[CMP1_SPLIT:%.*]] = icmp ult i16 [[I_0_SPLIT]], 5
+; CHECK-NEXT:    [[ARRAYIDX_SPLIT:%.*]] = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 [[I_0_SPLIT]]
+; CHECK-NEXT:    [[TMP2:%.*]] = load i16, i16* [[ARRAYIDX_SPLIT]], align 1
+; CHECK-NEXT:    br i1 false, label [[IF_THEN_SPLIT:%.*]], label [[IF_ELSE_SPLIT:%.*]]
+; CHECK:       if.else.split:
+; CHECK-NEXT:    call void @bar(i16 [[TMP2]])
+; CHECK-NEXT:    br label [[FOR_INC_SPLIT]]
+; CHECK:       if.then.split:
+; CHECK-NEXT:    call void @foo(i16 [[TMP2]])
+; CHECK-NEXT:    br label [[FOR_INC_SPLIT]]
+; CHECK:       for.inc.split:
+; CHECK-NEXT:    [[INC_SPLIT]] = add nuw nsw i16 [[I_0_SPLIT]], 1
+; CHECK-NEXT:    br label [[FOR_COND_SPLIT]]
+; CHECK:       for.end.loopexit:
+; CHECK-NEXT:    br label [[FOR_END]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %i.0 = phi i16 [ 0, %entry ], [ %inc, %for.inc ]
+  %i.1 = phi i16 [ 10, %entry ], [ %inc, %for.inc ]
+  %exitcond.not = icmp eq i16 %i.0, 10
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.body:                                         ; preds = %for.cond
+  %cmp1 = icmp ult i16 %i.0, 5
+  %arrayidx = getelementptr inbounds [10 x i16], [10 x i16]* @B, i16 0, i16 %i.0
+  %0 = load i16, i16* %arrayidx, align 1
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  call void @foo(i16 %0)
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  call void @bar(i16 %0)
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.else, %if.then
+  %inc = add nuw nsw i16 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @foo(i16)
+declare void @bar(i16)