Reroll loops with multiple IV and negative step part 3/3 -- support multiple induction variables

[• hulx2000]

Summary

This patch enable loop reroll for the following case:
    for(int i=0;  i<N; i += 2) {
       S += *a++;
       S += *a++;
    };

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

1421

Empty line is not needed

1517

Empty line is not needed

[• hulx2000]

ping

[jmolloy]

Hi,

I've got a bunch of comments - I think it'll be easier to review if you address these first, then I can continue to the end of the patch.

James

lib/Transforms/Scalar/LoopRerollPass.cpp

430

I don't see the need for the "Only" here. Simply "LoopControlIV" ? (no need for "ctrl" instead of "control" - be verbose when possible).

434

The name should include "branch" - like "isCompareUsedByBranch" or something.

It can also be made simpler:

bool isCompareUsedByBranch(Instruction *I) {
  auto *TI = I->getParent()->getTerminator();
  if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
    return false;
  return I->hasOneUse() && TI->getOperand(0) == I;
}

518

Can't you just use InductionInfo::isInduction() here? You'd be looking for an induction with a step of 1 that is used by the loop latch. It seems this could remove a lot of code.

520

Use "unsigned" here. There's no need to fix this to a specific bitwidth and no need for it to be signed.

521

Please fold the ! inside the brackets for readability:

if (IVUses != 2 && IVUses != 1)
  return false;

528

IsCompInst

528

isCompareInst doesn't handle nullptr. This should either use cast<Instruction>() or check that dyn_cast<Instruction>() is not nullptr.

531

Same as line 531.

536

You can fold these two if's together.

599

No need for brackets: &*I.

1155

This is really nasty. Please come up with a more concise way of expressing this.

(If you used InductionDescriptor to represent LoopControlIV, this should be fairly easy I think?)

[• hulx2000]

Thanks, James.

Caught by tight release schedule again, will address your comment after freed up.

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

518

Here I am checking if an induction PHI is only used to control loop iteration, no other uses such as A[i], normally, an Induction PHI will have other uses other than controlling loop iteration, e.g. Used as an index to access array.

So InductionDescriptor::isInductionPHI is not enough here.

1155

Here I am trying to mark the Loop Control Only IV and it's related instructions such as increment, compare and branches as used, InductionDescriptor can't help much here.

And there seems no other way around it without adding more code, may be I could add more comments instead?

[• hulx2000]

Hi, James:

Patch updated, could you please continue your review?

Thanks a lot.

Lawrence Hu

[• hulx2000]

ping

[jmolloy]

Hi Lawrence,

Sorry, I'll look at this tomorrow.

Cheers,

James

[• hulx2000]

Thanks, James.

Did you get time on this?

Have a nice weekend.

Lawrence Hu

[• hulx2000]

ping

[• hulx2000]

Thanks James for the update, have a a nice vacation then.

Hal, could you please find some time to review it then? I have another reroll patch pending on this, and I will transfer to another team in May 21st.

Have a nice day.

Lawrence HU

[• hulx2000]

Thanks a lot Hal.

Regards

Lawrence Hu

[hfinkel]

lib/Transforms/Scalar/LoopRerollPass.cpp

167

// For a loop with multiple induction variables, remember the one used only to control the loop.

513

// Check if an IV is only used to control the loop. There are two cases:

514

// 1. It has only one use which is the loop increment, and the increment is only used by the comparison and the PHI, and the comparison is used only by the branch.

516

// 2. It is used only by the loop increment and the comparison, the loop increment is only used by the PHI, and the comparison is used only by the branch.

534

be the loop increment

535

The loop increment

544

// The users of the IV must be a binary operation or a comparison.

1152

// Make sure we mark loop-control-only PHIs as used in all iterations. See comment above LoopReroll::isLoopControlIV for more information.

[Don't repeat the comment text from above LoopReroll::isLoopControlIV here.]

1170

You don't need the parenthesis around UUser->user_begin() - '->' has higher precedence than '*'.

1171

Do you need, or intend, the dyn_cast here? I think you don't, because you don't want the condition to be true if both sides are nullptr.

1431

non-loop-control IVs

1447

assert(COp && "Didn't find constant operand of LoopInc!");

1451

It does not look like there are test cases covering this logic, please add some.

[• hulx2000]

Hi, Hal.

Thanks a lot for reviewing, patch updated.

[hfinkel]

LGTM

lib/Transforms/Scalar/LoopRerollPass.cpp

166

variable -> variables

[jmolloy]

Hi Lawrence,

Hal's happy so I'm happy.

Cheers,

James

lib/Transforms/Scalar/LoopRerollPass.cpp

protected:
     DominatorTree *DT;
     bool PreserveLCSSA;
 
     typedef SmallVector<Instruction *, 16> SmallInstructionVector;
     typedef SmallSet<Instruction *, 16>   SmallInstructionSet;
 
     // Map between induction variable and its increment
     DenseMap<Instruction *, int64_t> IVToIncMap;
+    // For loop with multiple induction variable, remember the one used only to
+    // control the loop.
+    Instruction *LoopControlIV;
 
     // A chain of isomorphic instructions, identified by a single-use PHI
     // representing a reduction. Only the last value may be used outside the
     // loop.
     struct SimpleLoopReduction {
       SimpleLoopReduction(Instruction *P, Loop *L)
         : Valid(false), Instructions(1, P) {
         assert(isa<PHINode>(P) && "First reduction instruction must be a PHI");
protected:
 
     // The set of all DAG roots, and state tracking of all roots
     // for a particular induction variable.
     struct DAGRootTracker {
       DAGRootTracker(LoopReroll *Parent, Loop *L, Instruction *IV,
                      ScalarEvolution *SE, AliasAnalysis *AA,
                      TargetLibraryInfo *TLI, DominatorTree *DT, LoopInfo *LI,
                      bool PreserveLCSSA,
-                     DenseMap<Instruction *, int64_t> &IncrMap)
+                     DenseMap<Instruction *, int64_t> &IncrMap,
+                     Instruction *LoopCtrlIV)
           : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), DT(DT), LI(LI),
-            PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap) {}
+            PreserveLCSSA(PreserveLCSSA), IV(IV), IVToIncMap(IncrMap),
+            LoopControlIV(LoopCtrlIV) {}
 
       /// Stage 1: Find all the DAG roots for the induction variable.
       bool findRoots();
       /// Stage 2: Validate if the found roots are valid.
       bool validate(ReductionTracker &Reductions);
       /// Stage 3: Assuming validate() returned true, perform the
       /// replacement.
       /// @param IterCount The maximum iteration count of L.
protected:
                                  const SmallInstructionSet &Exclude,
                                  UsesTy::iterator *StartI=nullptr);
       bool isBaseInst(Instruction *I);
       bool isRootInst(Instruction *I);
       bool instrDependsOn(Instruction *I,
                           UsesTy::iterator Start,
                           UsesTy::iterator End);
       void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount);
+      void updateNonLoopCtrlIncr();
 
       LoopReroll *Parent;
 
       // Members of Parent, replicated here for brevity.
       Loop *L;
       ScalarEvolution *SE;
       AliasAnalysis *AA;
       TargetLibraryInfo *TLI;
protected:
       // All increment instructions for IV.
       SmallInstructionVector LoopIncs;
       // Map of all instructions in the loop (in order) to the iterations
       // they are used in (or specially, IL_All for instructions
       // used in the loop increment mechanism).
       UsesTy Uses;
       // Map between induction variable and its increment
       DenseMap<Instruction *, int64_t> &IVToIncMap;
+      Instruction *LoopControlIV;
     };
 
+    // Check if it is a compare-like instruction whose user is a branch
+    bool isCompareUsedByBranch(Instruction *I) {
+      auto *TI = I->getParent()->getTerminator();
+      if (!isa<BranchInst>(TI) || !isa<CmpInst>(I))
+        return false;
+      return I->hasOneUse() && TI->getOperand(0) == I;
+    };
+
+    bool isLoopControlIV(Loop *L, Instruction *IV);
     void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs);
     void collectPossibleReductions(Loop *L,
            ReductionTracker &Reductions);
     bool reroll(Instruction *IV, Loop *L, BasicBlock *Header, const SCEV *IterCount,
                 ReductionTracker &Reductions);
   };
 }
 
if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Operand)) {
         break;
     } else {
       return nullptr;
     }
   }
   return CIncSCEV;
 }
 
+// Check if an IV is only used to control the loop. There are two cases:
+// 1. It only has one use which is loop increment, and the increment is only
+// used by comparison and the PHI, and the comparison is only used by branch.
+// 2. It is used by loop increment and the comparison, the loop increment is
+// only used by the PHI, and the comparison is used only by the branch.
+bool LoopReroll::isLoopControlIV(Loop *L, Instruction *IV) {
+
+  unsigned IVUses = IV->getNumUses();
+  if (IVUses != 2 && IVUses != 1)
+    return false;
+
+  for (auto *User : IV->users()) {
+    int32_t IncOrCmpUses = User->getNumUses();
+    bool IsCompInst = isCompareUsedByBranch(cast<Instruction>(User));
+
+    // User can only have one or two uses.
+    if (IncOrCmpUses != 2 && IncOrCmpUses != 1)
+      return false;
+
+    // Case 1
+    if (IVUses == 1) {
+      // The only user must be the loop increment.
+      // The loop increment must have two uses.
+      if (IsCompInst || IncOrCmpUses != 2)
+        return false;
+    }
+
+    // Case 2
+    if (IVUses == 2 && IncOrCmpUses != 1)
+      return false;
+
+    // The users of the IV must be a binary operation or a comparison
+    if (auto *BO = dyn_cast<BinaryOperator>(User)) {
+      if (BO->getOpcode() == Instruction::Add) {
+        // Loop Increment
+        // User of Loop Increment should be either PHI or CMP
+        for (auto *UU : User->users()) {
+          if (PHINode *PN = dyn_cast<PHINode>(UU)) {
+            if (PN != IV)
+              return false;
+          }
+          // Must be a CMP
+          else if (!isCompareUsedByBranch(dyn_cast<Instruction>(UU)))
+            return false;
+        }
+      } else
+        return false;
+      // Compare : can only have one use, and must be branch
+    } else if (!IsCompInst)
+      return false;
+  }
+  return true;
+}
+
 // Collect the list of loop induction variables with respect to which it might
 // be possible to reroll the loop.
 void LoopReroll::collectPossibleIVs(Loop *L,
                                     SmallInstructionVector &PossibleIVs) {
   BasicBlock *Header = L->getHeader();
   for (BasicBlock::iterator I = Header->begin(),
        IE = Header->getFirstInsertionPt(); I != IE; ++I) {
     if (!isa<PHINode>(I))
if (const SCEVAddRecExpr *PHISCEV =
         IncSCEV = dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE));
       if (IncSCEV) {
         const APInt &AInt = IncSCEV->getValue()->getValue().abs();
         if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
           continue;
         IVToIncMap[&*I] = IncSCEV->getValue()->getSExtValue();
         DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
                      << "\n");
+
+        if (isLoopControlIV(L, &*I)) {
+          assert(!LoopControlIV && "Found two loop control only IV");
+          LoopControlIV = &(*I);
+          DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I << " = "
+                       << *PHISCEV << "\n");
+        } else
           PossibleIVs.push_back(&*I);
       }
     }
   }
 }
 
 // Add the remainder of the reduction-variable chain to the instruction vector
 // (the initial PHINode has already been added). If successful, the object is
 // marked as valid.
bool LoopReroll::DAGRootTracker::validate(ReductionTracker &Reductions) {
   if (!collectUsedInstructions(PossibleRedSet))
     return false;
 
   // Make sure we mark the reduction PHIs as used in all iterations.
   for (auto *I : PossibleRedPHISet) {
     Uses[I].set(IL_All);
   }
 
+  // Make sure we mark loop-control-only PHIs as used in all iterations. See
+  // comment above LoopReroll::isLoopControlIV for more information.
+  BasicBlock *Header = L->getHeader();
+  if (LoopControlIV && LoopControlIV != IV) {
+    for (auto *U : LoopControlIV->users()) {
+      Instruction *IVUser = dyn_cast<Instruction>(U);
+      // IVUser could be loop increment or compare
+      Uses[IVUser].set(IL_All);
+      for (auto *UU : IVUser->users()) {
+        Instruction *UUser = dyn_cast<Instruction>(UU);
+        // UUser could be compare, PHI or branch
+        Uses[UUser].set(IL_All);
+        // Is UUser a compare instruction?
+        if (UU->hasOneUse()) {
+          Instruction *BI = dyn_cast<BranchInst>(*UUser->user_begin());
+          if (BI == cast<BranchInst>(Header->getTerminator()))
+            Uses[BI].set(IL_All);
+        }
+      }
+    }
+  }
+
   // Make sure all instructions in the loop are in one and only one
   // set.
   for (auto &KV : Uses) {
     if (KV.second.count() != 1 && !isIgnorableInst(KV.first)) {
       DEBUG(dbgs() << "LRR: Aborting - instruction is not used in 1 iteration: "
             << *KV.first << " (#uses=" << KV.second.count() << ")\n");
       return false;
     }
if (I > 0 && I < IL_All) {
       DEBUG(dbgs() << "LRR: removing: " << *D << "\n");
       D->eraseFromParent();
       continue;
     }
 
     ++J;
   }
 
+  bool HasTwoIVs = LoopControlIV && LoopControlIV != IV;
+
+  if (HasTwoIVs) {
+    updateNonLoopCtrlIncr();
+    replaceIV(LoopControlIV, LoopControlIV, IterCount);
+  } else
     // We need to create a new induction variable for each different BaseInst.
     for (auto &DRS : RootSets)
       // Insert the new induction variable.
       replaceIV(DRS.BaseInst, IV, IterCount);
 
   SimplifyInstructionsInBlock(Header, TLI);
   DeleteDeadPHIs(Header, TLI);
 }
 
+// For non-loop-control IVs, we only need to update the last increment
+// with right amount, then we are done.
+void LoopReroll::DAGRootTracker::updateNonLoopCtrlIncr() {
+  const SCEV *NewInc = nullptr;
+  for (auto *LoopInc : LoopIncs) {
+    GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LoopInc);
+    const SCEVConstant *COp = nullptr;
+    if (GEP && LoopInc->getOperand(0)->getType()->isPointerTy()) {
+      COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
+    } else {
+      COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(0)));
+      if (!COp)
+        COp = dyn_cast<SCEVConstant>(SE->getSCEV(LoopInc->getOperand(1)));
+    }
+
+    assert(COp && "Didn't find constant operand of LoopInc!\n");
+
+    const APInt &AInt = COp->getValue()->getValue();
+    const SCEV *ScaleSCEV = SE->getConstant(COp->getType(), Scale);
+    if (AInt.isNegative()) {
+      NewInc = SE->getNegativeSCEV(COp);
+      NewInc = SE->getUDivExpr(NewInc, ScaleSCEV);
+      NewInc = SE->getNegativeSCEV(NewInc);
+    } else
+      NewInc = SE->getUDivExpr(COp, ScaleSCEV);
+
+    LoopInc->setOperand(1, dyn_cast<SCEVConstant>(NewInc)->getValue());
+  }
+}
+
 void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst,
                                            Instruction *InstIV,
                                            const SCEV *IterCount) {
   BasicBlock *Header = L->getHeader();
   int64_t Inc = IVToIncMap[InstIV];
-  bool Negative = Inc < 0;
+  bool NeedNewIV = InstIV == LoopControlIV;
+  bool Negative = !NeedNewIV && Inc < 0;
 
   const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(Inst));
   const SCEV *Start = RealIVSCEV->getStart();
 
+  if (NeedNewIV)
+    Start = SE->getConstant(Start->getType(), 0);
+
   const SCEV *SizeOfExpr = nullptr;
   const SCEV *IncrExpr =
       SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1);
   if (auto *PTy = dyn_cast<PointerType>(Inst->getType())) {
     Type *ElTy = PTy->getElementType();
     SizeOfExpr =
         SE->getSizeOfExpr(SE->getEffectiveSCEVType(Inst->getType()), ElTy);
     IncrExpr = SE->getMulExpr(IncrExpr, SizeOfExpr);
for (auto &KV : Uses)
       if (KV.second.find_first() == 0)
         KV.first->replaceUsesOfWith(Inst, NewIV);
 
     if (BranchInst *BI = dyn_cast<BranchInst>(Header->getTerminator())) {
       // FIXME: Why do we need this check?
       if (Uses[BI].find_first() == IL_All) {
         const SCEV *ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
 
+        if (NeedNewIV)
+          ICSCEV = SE->getMulExpr(IterCount,
+                                  SE->getConstant(IterCount->getType(), Scale));
+        else
+          ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE);
+
         // Iteration count SCEV minus or plus 1
         const SCEV *MinusPlus1SCEV =
             SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1);
         if (Inst->getType()->isPointerTy()) {
           assert(SizeOfExpr && "SizeOfExpr is not initialized");
           MinusPlus1SCEV = SE->getMulExpr(MinusPlus1SCEV, SizeOfExpr);
         }
 
         const SCEV *ICMinusPlus1SCEV = SE->getMinusSCEV(ICSCEV, MinusPlus1SCEV);
         // Iteration count minus 1
         Value *ICMinusPlus1 = nullptr;
         if (isa<SCEVConstant>(ICMinusPlus1SCEV)) {
           ICMinusPlus1 =
               Expander.expandCodeFor(ICMinusPlus1SCEV, NewIV->getType(), BI);
         } else {
           BasicBlock *Preheader = L->getLoopPreheader();
           if (!Preheader)
             Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA);

 // Finally, we make sure that all loop instructions are either loop increment
 // roots, belong to simple latch code, parts of validated reductions, part of
 // f(%iv) or part of some f(%iv.i). If all of that is true (and all reductions
 // have been validated), then we reroll the loop.
 bool LoopReroll::reroll(Instruction *IV, Loop *L, BasicBlock *Header,
                         const SCEV *IterCount,
                         ReductionTracker &Reductions) {
   DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, DT, LI, PreserveLCSSA,
-                          IVToIncMap);
+                          IVToIncMap, LoopControlIV);
 
   if (!DAGRoots.findRoots())
     return false;
   DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<
                   *IV << "\n");
 
   if (!DAGRoots.validate(Reductions))
     return false;
bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
   const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
   const SCEV *IterCount = SE->getAddExpr(LIBETC, SE->getOne(LIBETC->getType()));
   DEBUG(dbgs() << "LRR: iteration count = " << *IterCount << "\n");
 
   // First, we need to find the induction variable with respect to which we can
   // reroll (there may be several possible options).
   SmallInstructionVector PossibleIVs;
   IVToIncMap.clear();
+  LoopControlIV = nullptr;
   collectPossibleIVs(L, PossibleIVs);
 
   if (PossibleIVs.empty()) {
     DEBUG(dbgs() << "LRR: No possible IVs found\n");
     return false;
   }
 
   ReductionTracker Reductions;

test/Transforms/LoopReroll/complex_reroll.ll

+; RUN: opt -S  -loop-reroll   %s | FileCheck %s
+declare i32 @goo(i32, i32)
+
+@buf = external global i8*
+@aaa = global [16 x i8] c"\01\02\03\04\05\06\07\08\09\0A\0B\0C\0D\0E\0F\10", align 1
+
+define i32 @test1(i32 %len) {
+entry:
+  br label %while.body
+
+while.body:
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:    %indvar = phi i32 [ %indvar.next, %while.body ], [ 0, %entry ]
+;CHECK-NEXT:    %buf.021 = phi i8* [ getelementptr inbounds ([16 x i8], [16 x i8]* @aaa, i64 0, i64 0), %entry ], [ %add.ptr, %while.body ]
+;CHECK-NEXT:    %sum44.020 = phi i64 [ 0, %entry ], [ %add, %while.body ]
+;CHECK-NEXT:    [[T2:%[0-9]+]] = load i8, i8* %buf.021, align 1
+;CHECK-NEXT:    %conv = zext i8 [[T2]] to i64
+;CHECK-NEXT:    %add = add i64 %conv, %sum44.020
+;CHECK-NEXT:    %add.ptr = getelementptr inbounds i8, i8* %buf.021, i64 1
+;CHECK-NEXT:    %indvar.next = add i32 %indvar, 1
+;CHECK-NEXT:    %exitcond = icmp eq i32 %indvar, 1
+;CHECK-NEXT:    br i1 %exitcond, label %while.end, label %while.body
+
+  %dec22 = phi i32 [ 4, %entry ], [ %dec, %while.body ]
+  %buf.021 = phi i8* [ getelementptr inbounds ([16 x i8], [16 x i8]* @aaa, i64 0, i64 0), %entry ], [ %add.ptr, %while.body ]
+  %sum44.020 = phi i64 [ 0, %entry ], [ %add9, %while.body ]
+  %0 = load i8, i8* %buf.021, align 1
+  %conv = zext i8 %0 to i64
+  %add = add i64 %conv, %sum44.020
+  %arrayidx1 = getelementptr inbounds i8, i8* %buf.021, i64 1
+  %1 = load i8, i8* %arrayidx1, align 1
+  %conv2 = zext i8 %1 to i64
+  %add3 = add i64 %add, %conv2
+  %arrayidx4 = getelementptr inbounds i8, i8* %buf.021, i64 2
+  %2 = load i8, i8* %arrayidx4, align 1
+  %conv5 = zext i8 %2 to i64
+  %add6 = add i64 %add3, %conv5
+  %arrayidx7 = getelementptr inbounds i8, i8* %buf.021, i64 3
+  %3 = load i8, i8* %arrayidx7, align 1
+  %conv8 = zext i8 %3 to i64
+  %add9 = add i64 %add6, %conv8
+  %add.ptr = getelementptr inbounds i8, i8* %buf.021, i64 4
+  %dec = add nsw i32 %dec22, -1
+  %tobool = icmp eq i32 %dec, 0
+  br i1 %tobool, label %while.end, label %while.body
+
+while.end:                                        ; preds = %while.body
+  %conv11 = trunc i64 %add9 to i32
+  %call = tail call i32 @goo(i32 0, i32 %conv11)
+  unreachable
+}
+
+define i32 @test2(i32 %N, i32* nocapture readonly %a, i32 %S) {
+entry:
+  %cmp.9 = icmp sgt i32 %N, 0
+  br i1 %cmp.9, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:
+  br label %for.body
+
+for.cond.for.cond.cleanup_crit_edge:
+  br label %for.cond.cleanup
+
+for.cond.cleanup:
+  %S.addr.0.lcssa = phi i32 [ %add2, %for.cond.for.cond.cleanup_crit_edge ], [ %S, %entry ]
+  ret i32 %S.addr.0.lcssa
+
+for.body:
+;CHECK-LABEL: for.body:
+;CHECK-NEXT:    %indvar = phi i32 [ %indvar.next, %for.body ], [ 0, %for.body.lr.ph ]
+;CHECK-NEXT:    %S.addr.011 = phi i32 [ %S, %for.body.lr.ph ], [ %add, %for.body ]
+;CHECK-NEXT:    %a.addr.010 = phi i32* [ %a, %for.body.lr.ph ], [ %incdec.ptr1, %for.body ]
+;CHECK-NEXT:    %4 = load i32, i32* %a.addr.010, align 4
+;CHECK-NEXT:    %add = add nsw i32 %4, %S.addr.011
+;CHECK-NEXT:    %incdec.ptr1 = getelementptr inbounds i32, i32* %a.addr.010, i64 1
+;CHECK-NEXT:    %indvar.next = add i32 %indvar, 1
+;CHECK-NEXT:    %exitcond = icmp eq i32 %indvar, %3
+;CHECK-NEXT:    br i1 %exitcond, label %for.cond.for.cond.cleanup_crit_edge, label %for.body
+
+  %i.012 = phi i32 [ 0, %for.body.lr.ph ], [ %add3, %for.body ]
+  %S.addr.011 = phi i32 [ %S, %for.body.lr.ph ], [ %add2, %for.body ]
+  %a.addr.010 = phi i32* [ %a, %for.body.lr.ph ], [ %incdec.ptr1, %for.body ]
+  %incdec.ptr = getelementptr inbounds i32, i32* %a.addr.010, i64 1
+  %0 = load i32, i32* %a.addr.010, align 4
+  %add = add nsw i32 %0, %S.addr.011
+  %incdec.ptr1 = getelementptr inbounds i32, i32* %a.addr.010, i64 2
+  %1 = load i32, i32* %incdec.ptr, align 4
+  %add2 = add nsw i32 %add, %1
+  %add3 = add nsw i32 %i.012, 2
+  %cmp = icmp slt i32 %add3, %N
+  br i1 %cmp, label %for.body, label %for.cond.for.cond.cleanup_crit_edge
+}
+
+define i32 @test3(i32* nocapture readonly %buf, i32 %len) #0 {
+entry:
+  %cmp10 = icmp sgt i32 %len, 1
+  br i1 %cmp10, label %while.body.preheader, label %while.end
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.preheader, %while.body
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:  %indvar = phi i32 [ %indvar.next, %while.body ], [ 0, %while.body.preheader ]
+;CHECK-NEXT:  %S.012 = phi i32 [ %add, %while.body ], [ undef, %while.body.preheader ]
+;CHECK-NEXT:  %buf.addr.011 = phi i32* [ %add.ptr, %while.body ], [ %buf, %while.body.preheader ]
+;CHECK-NEXT:  %4 = load i32, i32* %buf.addr.011, align 4
+;CHECK-NEXT:  %add = add nsw i32 %4, %S.012
+;CHECK-NEXT:  %add.ptr = getelementptr inbounds i32, i32* %buf.addr.011, i64 -1
+;CHECK-NEXT:  %indvar.next = add i32 %indvar, 1
+;CHECK-NEXT:  %exitcond = icmp eq i32 %indvar, %3
+;CHECK-NEXT:  br i1 %exitcond, label %while.end.loopexit, label %while.body
+
+  %i.013 = phi i32 [ %sub, %while.body ], [ %len, %while.body.preheader ]
+  %S.012 = phi i32 [ %add2, %while.body ], [ undef, %while.body.preheader ]
+  %buf.addr.011 = phi i32* [ %add.ptr, %while.body ], [ %buf, %while.body.preheader ]
+  %0 = load i32, i32* %buf.addr.011, align 4
+  %add = add nsw i32 %0, %S.012
+  %arrayidx1 = getelementptr inbounds i32, i32* %buf.addr.011, i64 -1
+  %1 = load i32, i32* %arrayidx1, align 4
+  %add2 = add nsw i32 %add, %1
+  %add.ptr = getelementptr inbounds i32, i32* %buf.addr.011, i64 -2
+  %sub = add nsw i32 %i.013, -2
+  %cmp = icmp sgt i32 %sub, 1
+  br i1 %cmp, label %while.body, label %while.end.loopexit
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  %S.0.lcssa = phi i32 [ undef, %entry ], [ %add2, %while.end.loopexit ]
+  ret i32 %S.0.lcssa
+}
+