Expand loop reroll to handle loop with multiple induction variables and negative increment -part 1/3

[• hulx2000]

Summary

Handle loop with negtive induction variable increment

This patch extends LoopReroll pass to hand the loops which
are similar to the following:

      while (len > 1) {
            sum4 += buf[len];
            sum4 += buf[len-1];
            len -= 2;
        }

Basically, negative loop increment.

The original patch will be split into 3, that's the first one.

[• hulx2000]

handle some of Ana's comments

[hfinkel]

Please enhance your patch description to explain, not just what he patch enables (which you've done), but generically how it does it. There is a bunch of new code here, and it will be good to get a high-level overview of what it does (and I'd expect such a description to appear in the commit message anyway, so this is not "just for review").

Please upload the patch with full context, see:

http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

for instructions.

lib/Transforms/Scalar/LoopRerollPass.cpp

447

We generally abbreviate Instruction to Inst, not Insn. Please rename this function.

Also, please comment what this function does. It is certainly more than just determining if the instruction is a comparison of some kind.

[• hulx2000]

Thanks, Hal, sorry for the delay, just saw your comments this morning

[jmolloy]

Hi,

I'm afraid there are too many different changes bundled together here for me to really review. Please could you split this out into:

1. Adding negative offset support
2. Adding pointer induction variable support
3. Adding multiple induction variable support.

Cheers,

James

[• hulx2000]

Hi, James:

Thank you very much for your comment.

Those patches are bundled together because they are strongly correlated, for an example, if I add support for pointer induction variable, I must support multiple induction variable, otherwise a lot of test will be broken.

I will see if I can split it into three with some extra safety check.

Regards

Lawrence Hu

[• hulx2000]

remove white spaces

[• hulx2000]

upload the full context diff

[jmolloy]

Hi,

Thanks for making these changes - it looks much better now. A few comments still.

Cheers,

James

lib/Transforms/Scalar/LoopRerollPass.cpp

500

I think this line and line 503 can both be merged, and put on line 505. There's no need to ZExt this one and SExt the other - both can be SExted.

503

This can be much simpler. You can just use APInt::abs():

AInt = AInt.abs();
if (AInt.isZero() || AInt.uge(MaxInc))
  continue;
IVToIncMap[I] = AInt.getSExtValue();

668

I'm not sure how adding GEP support here relates to negative values. Was this an accidentally added hunk?

713

I think you need to use std::abs() above, on line 721 too. Otherwise the guard on line 721 is useless.

1268

Double semicolon (;;).

Also, you can squash this into just one statement:

bool Negative = IVToIncMap[IV] < 0;

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

668

Ｏｈ，　ｓｏｒｒｙ，　ｔｈｉｓ　ｉｓ　ｌｅｆｔ　ｏｖｅｒ　ｗｈｅｎ　Ｉ　ｓｐｌｉｔ　ｍｙ　ｐａｔｃｈ，　ｉｔ　ｉｓ　ｒｅｑｕｉｒｅ　ｆｏｒ　ｐｏｉｎｔｅｒ　ｉｎｄｕｃｔｉｏｎ　ｖａｒｉａｂｌｅ　ｔｈｏｕｇｈ，　ｂｕｔ　Ｉ　ｃａｎ　ｒｅｍｏｖｅ　ｉｔ　ｆｏｒ　ｎｏｗ．

Ｗｉｌｌ　ｆｉｘ　ｔｈｅ　ｒｅｓｔ，　ｔｈａｎｋｓ．``

[• hulx2000]

Thanks, James for your valuable comments.

I have updated my patch.

[jmolloy]

Hi,

This is looking a lot better, thanks!

James

lib/Transforms/Scalar/LoopRerollPass.cpp

373

This should be const, to notify a user that it is not captured or modified.

438

Please add a docstring, like all other variables.

666

I think this is still relating to adding GEP support, is it not?

test/Transforms/LoopReroll/negative.ll

17

This test will fail in release builds because registers will lose their names. Please either make it not rely on named variables or add a

; REQUIRES: asserts

to the top (please also check the line above is actually correct, I've just pasted it from memory!)

[• hulx2000]

Thanks Jame.

Sorry that missed a few thing last time, this time should be better.

Best, I didn't change the const thing, compiler complains, and I didn't see testcase asset in release build, I tried pass, it is fine, are yours a special build?

Regards

Lawrence Hu

[• hulx2000]

lib/Transforms/Scalar/LoopRerollPass.cpp

373

unfortunately, compiler always contains if I do that.

[jmolloy]

LGTM, thanks for making those changes.

If you don't add REQUIRES: asserts, you'll get complaints on the list when this goes in. I forget exactly which cmake variable you change to remove value names completely, but rest assured there are people who use it - I've found that out myself :)

Cheers,

James

[• hulx2000]

Great, Thanks, James.

I will add Assert from the next test and on.

Would you mind to commit it for you so I can start the next one? I don't have commit right yet.

[• hulx2000]

typo: for me.

[mzolotukhin]

lib/Transforms/Scalar/LoopRerollPass.cpp

169–172

s/it's/its/

172

I'd rather commit this typo fix immediately when I found it (no pre-commit review is required for this kind of changes).

438

s/it's/its/

665

No need to add a blank line here.

1267

Redundant whitespaces.

test/Transforms/LoopReroll/negative.ll

20–28

Do we really need to check that we generate *exactly* these statements? Would it be possible to look for, say, a specific branch (or absence of the branch) - this would make the test much more stable.

30–39

Do we really need to have this body, or would the test work with almost empty loop?
Like this:

while (len > 1) {
            len -= 2;
        }

instead of

while (len > 1) {
            sum4 += buf[len];
            sum4 += buf[len-1];
            len -= 2;
        }

Since you only run loop-reroll, it shouldn't be collapsed to nop.

54–55

Maybe just return i32 %sum4.0.lcssa to get rid of the goo function?

[• hulx2000]

test/Transforms/LoopReroll/negative.ll

30–39

The simple loop won't do enough test for the logic in LoopReroll

[• hulx2000]

Addressed Michael's comment

[• hulx2000]

Hi, Michael

Could you please accept it if you have now further comment? It will be easier for me to prepare next two patches.

Thanks.

Lawrence Hu

[• hulx2000]

Hi, Hal:

Do you have any other comments about this patch, could you please accept it if not?

Thanks

Lawrence Hu

[hfinkel]

lib/Transforms/Scalar/LoopRerollPass.cpp

1275–1276

Line is too long.

1294–1295

Line is too long.

test/Transforms/LoopReroll/negative.ll

3

Remove this. There is no valid reason why a test like this needs to be asserts-mode only. And it is really important that we have as much testing as possible for the NDEBUG builds (even if that were to require using more regexes in the test). That having been said, what James said was not quite right. The NDEBUG opt does not remove all variable names (certain passes did that, or used to, but that's another matter). What is true is that NDEBUG Clang does not produce variable names for locals.

[• hulx2000]

Thanks, Hal,

Updated.

Regards

[hfinkel]

LGTM now too, thanks!

[• hulx2000]

committed as git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243171 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Transforms/Scalar/LoopRerollPass.cpp

protected:
     LoopInfo *LI;
     ScalarEvolution *SE;
     TargetLibraryInfo *TLI;
     DominatorTree *DT;
 
     typedef SmallVector<Instruction *, 16> SmallInstructionVector;
     typedef SmallSet<Instruction *, 16>   SmallInstructionSet;
 
-    // A chain of isomorphic instructions, indentified by a single-use PHI,
+    // Map between induction variable and its increment
+    DenseMap<Instruction *, int64_t> IVToIncMap;
+
+    // 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");
         add(L);
       }
protected:
 
     // A DAGRootSet models an induction variable being used in a rerollable
     // loop. For example,
     //
     //   x[i*3+0] = y1
     //   x[i*3+1] = y2
     //   x[i*3+2] = y3
     //
-    //   Base instruction -> i*3               
+    //   Base instruction -> i*3
     //                    +---+----+
     //                   /    |     \
     //               ST[y1]  +1     +2  <-- Roots
     //                        |      |
     //                      ST[y2] ST[y3]
     //
     // There may be multiple DAGRoots, for example:
     //
struct DAGRootSet {
       SmallInstructionSet SubsumedInsts;
     };
 
     // 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)
-          : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV) {}
+                     TargetLibraryInfo *TLI,
+                     DenseMap<Instruction *, int64_t> &IncrMap)
+          : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV),
+            IVToIncMap(IncrMap) {}
 
       /// 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:
       Loop *L;
       ScalarEvolution *SE;
       AliasAnalysis *AA;
       TargetLibraryInfo *TLI;
 
       // The loop induction variable.
       Instruction *IV;
       // Loop step amount.
-      uint64_t Inc;
+      int64_t Inc;
       // Loop reroll count; if Inc == 1, this records the scaling applied
       // to the indvar: a[i*2+0] = ...; a[i*2+1] = ... ;
       // If Inc is not 1, Scale = Inc.
       uint64_t Scale;
       // The roots themselves.
       SmallVector<DAGRootSet,16> RootSets;
       // 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;
     };
 
     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);
   };
 }
 
 char LoopReroll::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopReroll, "loop-reroll", "Reroll loops", false, false)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
for (BasicBlock::iterator I = Header->begin(),
     if (const SCEVAddRecExpr *PHISCEV =
         dyn_cast<SCEVAddRecExpr>(SE->getSCEV(I))) {
       if (PHISCEV->getLoop() != L)
         continue;
       if (!PHISCEV->isAffine())
         continue;
       if (const SCEVConstant *IncSCEV =
           dyn_cast<SCEVConstant>(PHISCEV->getStepRecurrence(*SE))) {
-        if (!IncSCEV->getValue()->getValue().isStrictlyPositive())
-          continue;
-        if (IncSCEV->getValue()->uge(MaxInc))
+        const APInt &AInt = IncSCEV->getValue()->getValue().abs();
+        if (IncSCEV->getValue()->isZero() || AInt.uge(MaxInc))
           continue;
-
-        DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " <<
-              *PHISCEV << "\n");
+        IVToIncMap[I] = IncSCEV->getValue()->getSExtValue();
+        DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV
+                     << "\n");
         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.
 void LoopReroll::SimpleLoopReduction::add(Loop *L) {
   assert(!Valid && "Cannot add to an already-valid chain");
 
case Instruction::SExt:
       return true;
     }
   }
   return false;
 }
 
 static bool isLoopIncrement(User *U, Instruction *IV) {
   BinaryOperator *BO = dyn_cast<BinaryOperator>(U);
   if (!BO || BO->getOpcode() != Instruction::Add)
     return false;
 
   for (auto *UU : BO->users()) {
     PHINode *PN = dyn_cast<PHINode>(UU);
     if (PN && PN == IV)
       return true;
   }
   return false;
 }
 
 bool LoopReroll::DAGRootTracker::
if (!CI) {
         BaseUsers.push_back(II);
         continue;
       } else {
         DEBUG(dbgs() << "LRR: Aborting due to non-instruction: " << *I << "\n");
         return false;
       }
     }
 
-    int64_t V = CI->getValue().getSExtValue();
+    int64_t V = std::abs(CI->getValue().getSExtValue());
     if (Roots.find(V) != Roots.end())
       // No duplicates, please.
       return false;
 
-    // FIXME: Add support for negative values.
-    if (V < 0) {
-      DEBUG(dbgs() << "LRR: Aborting due to negative value: " << V << "\n");
-      return false;
-    }
-
     Roots[V] = cast<Instruction>(I);
   }
 
   if (Roots.empty())
     return false;
 
   // If we found non-loop-inc, non-root users of Base, assume they are
   // for the zeroth root index. This is because "add %a, 0" gets optimized
   // away.
   if (BaseUsers.size()) {
     if (Roots.find(0) != Roots.end()) {
       DEBUG(dbgs() << "LRR: Multiple roots found for base - aborting!\n");
       return false;
     }
     Roots[0] = Base;
   }
 
   // Calculate the number of users of the base, or lowest indexed, iteration.
   unsigned NumBaseUses = BaseUsers.size();
   if (NumBaseUses == 0)
     NumBaseUses = Roots.begin()->second->getNumUses();
-  
   // Check that every node has the same number of users.
   for (auto &KV : Roots) {
     if (KV.first == 0)
       continue;
     if (KV.second->getNumUses() != NumBaseUses) {
       DEBUG(dbgs() << "LRR: Aborting - Root and Base #users not the same: "
             << "#Base=" << NumBaseUses << ", #Root=" <<
             KV.second->getNumUses() << "\n");
       return false;
     }
   }
 
-  return true; 
+  return true;
 }
 
 bool LoopReroll::DAGRootTracker::
 findRootsRecursive(Instruction *I, SmallInstructionSet SubsumedInsts) {
   // Does the user look like it could be part of a root set?
   // All its users must be simple arithmetic ops.
   if (I->getNumUses() > IL_MaxRerollIterations)
     return false;
findRootsBase(Instruction *IVU, SmallInstructionSet SubsumedInsts) {
   if (IVU->getOpcode() != Instruction::Mul &&
       IVU->getOpcode() != Instruction::PHI)
     return false;
 
   std::map<int64_t, Instruction*> V;
   if (!collectPossibleRoots(IVU, V))
     return false;
 
-  // If we didn't get a root for index zero, then IVU must be 
+  // If we didn't get a root for index zero, then IVU must be
   // subsumed.
   if (V.find(0) == V.end())
     SubsumedInsts.insert(IVU);
 
   // Partition the vector into monotonically increasing indexes.
   DAGRootSet DRS;
   DRS.BaseInst = nullptr;
 
for (auto &KV : V) {
     }
   }
   RootSets.push_back(DRS);
 
   return true;
 }
 
 bool LoopReroll::DAGRootTracker::findRoots() {
-
-  const SCEVAddRecExpr *RealIVSCEV = cast<SCEVAddRecExpr>(SE->getSCEV(IV));
-  Inc = cast<SCEVConstant>(RealIVSCEV->getOperand(1))->
-    getValue()->getZExtValue();
+  Inc = IVToIncMap[IV];
 
   assert(RootSets.empty() && "Unclean state!");
-  if (Inc == 1) {
+  if (std::abs(Inc) == 1) {
     for (auto *IVU : IV->users()) {
       if (isLoopIncrement(IVU, IV))
         LoopIncs.push_back(cast<Instruction>(IVU));
     }
     if (!findRootsRecursive(IV, SmallInstructionSet()))
       return false;
     LoopIncs.push_back(IV);
   } else {
while (BaseIt != Uses.end() && RootIt != Uses.end()) {
         }
 
         if (TryIt == Uses.end() || TryIt == RootIt ||
             instrDependsOn(TryIt->first, RootIt, TryIt)) {
           DEBUG(dbgs() << "LRR: iteration root match failed at " << *BaseInst <<
                 " vs. " << *RootInst << "\n");
           return false;
         }
-        
         RootIt = TryIt;
         RootInst = TryIt->first;
       }
 
       // All instructions between the last root and this root
-      // may belong to some other iteration. If they belong to a 
+      // may belong to some other iteration. If they belong to a
       // future iteration, then they're dangerous to alias with.
-      // 
+      //
       // Note that because we allow a limited amount of flexibility in the order
       // that we visit nodes, LastRootIt might be *before* RootIt, in which
       // case we've already checked this set of instructions so we shouldn't
       // do anything.
       for (; LastRootIt < RootIt; ++LastRootIt) {
         Instruction *I = LastRootIt->first;
         if (LastRootIt->second.find_first() < (int)Iter)
           continue;
if (I > 0 && I < IL_All) {
       Instruction *D = &*J;
       DEBUG(dbgs() << "LRR: removing: " << *D << "\n");
       D->eraseFromParent();
       continue;
     }
 
     ++J;
   }
+  bool Negative = IVToIncMap[IV] < 0;
   const DataLayout &DL = Header->getModule()->getDataLayout();
 
   // We need to create a new induction variable for each different BaseInst.
   for (auto &DRS : RootSets) {
     // Insert the new induction variable.
     const SCEVAddRecExpr *RealIVSCEV =
       cast<SCEVAddRecExpr>(SE->getSCEV(DRS.BaseInst));
     const SCEV *Start = RealIVSCEV->getStart();
-    const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>
-      (SE->getAddRecExpr(Start,
-                         SE->getConstant(RealIVSCEV->getType(), 1),
-                         L, SCEV::FlagAnyWrap));
+    const SCEVAddRecExpr *H = cast<SCEVAddRecExpr>(SE->getAddRecExpr(
+        Start, SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1), L,
+        SCEV::FlagAnyWrap));
     { // Limit the lifetime of SCEVExpander.
       SCEVExpander Expander(*SE, DL, "reroll");
       Value *NewIV = Expander.expandCodeFor(H, IV->getType(), Header->begin());
 
       for (auto &KV : Uses) {
         if (KV.second.find_first() == 0)
           KV.first->replaceUsesOfWith(DRS.BaseInst, 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);
 
           // Iteration count SCEV minus 1
-          const SCEV *ICMinus1SCEV =
-            SE->getMinusSCEV(ICSCEV, SE->getConstant(ICSCEV->getType(), 1));
+          const SCEV *ICMinus1SCEV = SE->getMinusSCEV(
+              ICSCEV, SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1));
 
           Value *ICMinus1; // Iteration count minus 1
           if (isa<SCEVConstant>(ICMinus1SCEV)) {
             ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), BI);
           } else {
             BasicBlock *Preheader = L->getLoopPreheader();
             if (!Preheader)
               Preheader = InsertPreheaderForLoop(L, Parent);

 //
 // 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);
+  DAGRootTracker DAGRoots(this, L, IV, SE, AA, TLI, IVToIncMap);
 
   if (!DAGRoots.findRoots())
     return false;
   DEBUG(dbgs() << "LRR: Found all root induction increments for: " <<
                   *IV << "\n");
-  
   if (!DAGRoots.validate(Reductions))
     return false;
   if (!Reductions.validateSelected())
     return false;
   // At this point, we've validated the rerolling, and we're committed to
   // making changes!
 
   Reductions.replaceSelected();
bool LoopReroll::runOnLoop(Loop *L, LPPassManager &LPM) {
   const SCEV *LIBETC = SE->getBackedgeTakenCount(L);
   const SCEV *IterCount =
     SE->getAddExpr(LIBETC, SE->getConstant(LIBETC->getType(), 1));
   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();
   collectPossibleIVs(L, PossibleIVs);
 
   if (PossibleIVs.empty()) {
     DEBUG(dbgs() << "LRR: No possible IVs found\n");
     return Changed;
   }
 
   ReductionTracker Reductions;

test/Transforms/LoopReroll/negative.ll

+; RUN: opt -S  -loop-reroll   %s | FileCheck %s
+target triple = "aarch64--linux-gnu"
+@buf = global [16 x i8] c"\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A\0A", align 1
+
+define i32 @test1(i32 %len, i8* nocapture readonly %buf) #0 {
+entry:
+  %cmp.13 = icmp sgt i32 %len, 1
+  br i1 %cmp.13, label %while.body.lr.ph, label %while.end
+
+while.body.lr.ph:                                 ; preds = %entry
+  br label %while.body
+
+while.body:
+;CHECK-LABEL: while.body:
+;CHECK-NEXT:    %indvar = phi i32 [ %indvar.next, %while.body ], [ 0, %while.body.lr.ph ]
+;CHECK-NEXT:    %sum4.015 = phi i64 [ 0, %while.body.lr.ph ], [ %add, %while.body ]
+;CHECK-NOT:     %sub5 = add nsw i32 %len.addr.014, -1
+;CHECK-NOT:     %sub5 = add nsw i32 %len.addr.014, -2
+;CHECK:    br i1 %exitcond, label %while.cond.while.end_crit_edge, label %while.body
+
+  %sum4.015 = phi i64 [ 0, %while.body.lr.ph ], [ %add4, %while.body ]
+  %len.addr.014 = phi i32 [ %len, %while.body.lr.ph ], [ %sub5, %while.body ]
+  %idxprom = sext i32 %len.addr.014 to i64
+  %arrayidx = getelementptr inbounds i8, i8* %buf, i64 %idxprom
+  %0 = load i8, i8* %arrayidx, align 1
+  %conv = zext i8 %0 to i64
+  %add = add i64 %conv, %sum4.015
+  %sub = add nsw i32 %len.addr.014, -1
+  %idxprom1 = sext i32 %sub to i64
+  %arrayidx2 = getelementptr inbounds i8, i8* %buf, i64 %idxprom1
+  %1 = load i8, i8* %arrayidx2, align 1
+  %conv3 = zext i8 %1 to i64
+  %add4 = add i64 %add, %conv3
+  %sub5 = add nsw i32 %len.addr.014, -2
+  %cmp = icmp sgt i32 %sub5, 1
+  br i1 %cmp, label %while.body, label %while.cond.while.end_crit_edge
+
+while.cond.while.end_crit_edge:                   ; preds = %while.body
+  %add4.lcssa = phi i64 [ %add4, %while.body ]
+  %phitmp = trunc i64 %add4.lcssa to i32
+  br label %while.end
+
+while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
+  %sum4.0.lcssa = phi i32 [ %phitmp, %while.cond.while.end_crit_edge ], [ 0, %entry ]
+  ret i32 %sum4.0.lcssa
+  unreachable
+}
+