Index: lib/Transforms/Scalar/LoopRerollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopRerollPass.cpp +++ lib/Transforms/Scalar/LoopRerollPass.cpp @@ -166,7 +166,10 @@ typedef SmallVector SmallInstructionVector; typedef SmallSet SmallInstructionSet; - // A chain of isomorphic instructions, indentified by a single-use PHI, + Instruction *LoopCtrlOnlyIV; + DenseMap 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 { @@ -335,7 +338,7 @@ // x[i*3+1] = y2 // x[i*3+2] = y3 // - // Base instruction -> i*3 + // Base instruction -> i*3 // +---+----+ // / | \ // ST[y1] +1 +2 <-- Roots @@ -366,8 +369,12 @@ 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, ReductionTracker &Reducs, + DenseMap &IncrMap, + Instruction *LoopCtrlIV) + : Parent(Parent), L(L), SE(SE), AA(AA), TLI(TLI), IV(IV), + Reductions(Reducs), IVToIncMap(IncrMap), + LoopCtrlOnlyIV(LoopCtrlIV) {} /// Stage 1: Find all the DAG roots for the induction variable. bool findRoots(); @@ -377,6 +384,8 @@ /// replacement. /// @param IterCount The maximum iteration count of L. void replace(const SCEV *IterCount); + void replaceIV(Instruction *Inst, Instruction *IV, const SCEV *IterCount); + void replaceNonLoopCtrlIV(); protected: typedef MapVector UsesTy; @@ -417,7 +426,7 @@ // 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. @@ -430,8 +439,21 @@ // they are used in (or specially, IL_All for instructions // used in the loop increment mechanism). UsesTy Uses; + ReductionTracker &Reductions; + DenseMap &IVToIncMap; + Instruction *LoopCtrlOnlyIV; + }; + + // Check if it is a compare-like instruction whose user is a branch + bool isCompareInst(Instruction *I, BasicBlock *Header) { + Instruction *Branch = dyn_cast(Header->getTerminator()); + if (I->hasOneUse() && Branch && + (dyn_cast(*(I->user_begin())) == Branch)) + return true; + return false; }; + bool isLoopCtrlOnlyIV(Loop *L, Instruction *IV); void collectPossibleIVs(Loop *L, SmallInstructionVector &PossibleIVs); void collectPossibleReductions(Loop *L, ReductionTracker &Reductions); @@ -464,6 +486,88 @@ return false; } +static const SCEVConstant *getConstantCoefFromStep(ScalarEvolution *SE, + const SCEV *SCEVExpr, + Instruction *IV) { + const SCEVConstant *CIncSCEV = nullptr; + const SCEVMulExpr *MulSCEV = dyn_cast(SCEVExpr); + + // If StepRecurrence of a SCEVExpr is a constant (c1 * c2, c2 = sizeof(x)), + // Return c1. + if (!MulSCEV && IV->getType()->isPointerTy()) + if (const SCEVConstant *IncSCEV = dyn_cast(SCEVExpr)) { + const PointerType *PTy = dyn_cast(IV->getType()); + Type *ElTy = PTy->getElementType(); + const SCEV *SizeOfExpr = + SE->getSizeOfExpr(SE->getEffectiveSCEVType(IV->getType()), ElTy); + const SCEV *NewSCEV = nullptr; + if (IncSCEV->getValue()->getValue().isNegative()) { + NewSCEV = SE->getUDivExpr(SE->getNegativeSCEV(SCEVExpr), SizeOfExpr); + CIncSCEV = dyn_cast(SE->getNegativeSCEV(NewSCEV)); + } else + CIncSCEV = + dyn_cast(SE->getUDivExpr(SCEVExpr, SizeOfExpr)); + return CIncSCEV; + } + + if (!MulSCEV) + return nullptr; + + // If StepRecurrence of a SCEVExpr is a c * sizeof(x), where c is constant, + // Return c. + for (const SCEV *Operand : MulSCEV->operands()) { + if (const SCEVConstant *Constant = dyn_cast(Operand)) + CIncSCEV = Constant; + else if (const SCEVUnknown *Unknown = dyn_cast(Operand)) { + Type *AllocTy; + if (Unknown->isSizeOf(AllocTy)) { + DEBUG(dbgs() << "LRR: SizeOf SCEVExpr: " << *Unknown << "\n"); + } else + break; + } + } + return CIncSCEV; +} + +// Check if an IV is only for loop control purpose: +// 1. It only has one use which is loop increment, then it is only used +// by compare and PHI, compare is only used by branch. +// 2. It is used by loop increment and compare, loop increment is only +// used by PHI, compare is only used by branch. +bool LoopReroll::isLoopCtrlOnlyIV(Loop *L, Instruction *IV) { + + int64_t Uses = IV->getNumUses(); + if (!(Uses == 2 || Uses == 1)) + return false; + + BasicBlock *Header = L->getHeader(); + for (auto *User : IV->users()) { + Uses = User->getNumUses(); + if (!(Uses == 2 || Uses == 1)) + return false; + // All users of IV must be binary operation or cmp + if (auto *BO = dyn_cast(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(UU)) { + if (PN != IV) + return false; + } + // Must be a CMP + else if (!isCompareInst(dyn_cast(UU), Header)) + return false; + } + } else + return false; + // Compare : can only have one use, and must be branch + } else if (!isCompareInst(dyn_cast(User), Header)) + 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, @@ -473,7 +577,7 @@ IE = Header->getFirstInsertionPt(); I != IE; ++I) { if (!isa(I)) continue; - if (!I->getType()->isIntegerTy()) + if (!(I->getType()->isIntegerTy() || I->getType()->isPointerTy())) continue; if (const SCEVAddRecExpr *PHISCEV = @@ -482,17 +586,42 @@ continue; if (!PHISCEV->isAffine()) continue; - if (const SCEVConstant *IncSCEV = - dyn_cast(PHISCEV->getStepRecurrence(*SE))) { - if (!IncSCEV->getValue()->getValue().isStrictlyPositive()) - continue; + const SCEVConstant *IncSCEV = nullptr; + if (I->getType()->isPointerTy()) { + IncSCEV = + getConstantCoefFromStep(SE, PHISCEV->getStepRecurrence(*SE), I); + } else + IncSCEV = dyn_cast(PHISCEV->getStepRecurrence(*SE)); + + if (!IncSCEV) + return; + + const APInt &AInt = IncSCEV->getValue()->getValue(); + if (AInt.isStrictlyPositive()) { if (IncSCEV->getValue()->uge(MaxInc)) continue; + DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << *PHISCEV + << "\n"); + IVToIncMap[I] = IncSCEV->getValue()->getZExtValue(); + } + + if (AInt.isNegative()) { + const SCEVConstant *PIncSCEV = + dyn_cast(SE->getNegativeSCEV(IncSCEV)); + if (!PIncSCEV || PIncSCEV->getValue()->uge(MaxInc)) + continue; + DEBUG(dbgs() << "LRR: Possible negative IV: " << *I << " = " << *PHISCEV + << "\n"); + IVToIncMap[I] = IncSCEV->getValue()->getSExtValue(); + } - DEBUG(dbgs() << "LRR: Possible IV: " << *I << " = " << - *PHISCEV << "\n"); + if (isLoopCtrlOnlyIV(L, I)) { + assert(!LoopCtrlOnlyIV && "Found two loop control only IV"); + LoopCtrlOnlyIV = I; + DEBUG(dbgs() << "LRR: Possible loop control only IV: " << *I << " = " + << *PHISCEV << "\n"); + } else PossibleIVs.push_back(I); - } } } } @@ -656,14 +785,19 @@ static bool isLoopIncrement(User *U, Instruction *IV) { BinaryOperator *BO = dyn_cast(U); - if (!BO || BO->getOpcode() != Instruction::Add) + + if (BO && BO->getOpcode() != Instruction::Add) return false; - for (auto *UU : BO->users()) { + if (!BO && !isa(U)) + return false; + + for (auto *UU : U->users()) { PHINode *PN = dyn_cast(UU); if (PN && PN == IV) return true; } + return false; } @@ -731,7 +865,7 @@ 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) @@ -744,7 +878,7 @@ } } - return true; + return true; } bool LoopReroll::DAGRootTracker:: @@ -787,7 +921,7 @@ 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); @@ -818,13 +952,10 @@ } bool LoopReroll::DAGRootTracker::findRoots() { - - const SCEVAddRecExpr *RealIVSCEV = cast(SE->getSCEV(IV)); - Inc = cast(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(IVU)); @@ -1026,6 +1157,25 @@ Uses[I].set(IL_All); } + // Make sure we mark the loop ctrl only PHIs as used in all iterations. + // Including loop increment, compares, branches. + BasicBlock *Header = L->getHeader(); + if (LoopCtrlOnlyIV && LoopCtrlOnlyIV != IV) { + for (auto *U : LoopCtrlOnlyIV->users()) { + Instruction *UI = dyn_cast(U); + Uses[UI].set(IL_All); + for (auto *UU : UI->users()) { + Instruction *UUI = dyn_cast(UU); + Uses[UUI].set(IL_All); + if (UUI->hasOneUse()) { + Instruction *UUUI = dyn_cast(*(UUI->user_begin())); + if (UUUI == dyn_cast(Header->getTerminator())) + Uses[UUUI].set(IL_All); + } + } + } + } + // Make sure all instructions in the loop are in one and only one // set. for (auto &KV : Uses) { @@ -1103,15 +1253,15 @@ " 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 @@ -1252,6 +1402,114 @@ return true; } +// For non loop control IVs, we only need to update the last increment +// with right amount. +void LoopReroll::DAGRootTracker::replaceNonLoopCtrlIV() { + const SCEV *NewIncr = nullptr; + for (auto *LoopInc : LoopIncs) { + GetElementPtrInst *GEP = dyn_cast(LoopInc); + const SCEVConstant *COp = nullptr; + if (GEP && LoopInc->getOperand(0)->getType()->isPointerTy()) { + COp = dyn_cast(SE->getSCEV(LoopInc->getOperand(1))); + } else { + COp = dyn_cast(SE->getSCEV(LoopInc->getOperand(0))); + if (!COp) + COp = dyn_cast(SE->getSCEV(LoopInc->getOperand(1))); + } + + if (!COp) + assert(false && "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()) { + NewIncr = SE->getNegativeSCEV(COp); + NewIncr = SE->getUDivExpr(NewIncr, ScaleSCEV); + NewIncr = SE->getNegativeSCEV(NewIncr); + } else + NewIncr = SE->getUDivExpr(COp, ScaleSCEV); + + LoopInc->setOperand(1, dyn_cast(NewIncr)->getValue()); + } +} + +void LoopReroll::DAGRootTracker::replaceIV(Instruction *Inst, + Instruction *InstIV, + const SCEV *IterCount) { + BasicBlock *Header = L->getHeader(); + int64_t Inc = IVToIncMap[InstIV]; + bool NeedNewIV = InstIV == LoopCtrlOnlyIV; + bool Negative = !NeedNewIV && Inc < 0; + + const SCEVAddRecExpr *RealIVSCEV = cast(SE->getSCEV(Inst)); + const SCEV *Start = RealIVSCEV->getStart(); + + if (NeedNewIV) + Start = SE->getConstant(Start->getType(), 0); + + const SCEVAddRecExpr *H = nullptr; + const SCEV *SizeOfExpr = nullptr; + const SCEV *OneExpr = + SE->getConstant(RealIVSCEV->getType(), Negative ? -1 : 1); + if (Inst->getType()->isPointerTy()) { + const PointerType *PTy = dyn_cast(Inst->getType()); + Type *ElTy = PTy->getElementType(); + SizeOfExpr = + SE->getSizeOfExpr(SE->getEffectiveSCEVType(Inst->getType()), ElTy); + + OneExpr = SE->getMulExpr(OneExpr, SizeOfExpr); + } + H = cast( + SE->getAddRecExpr(Start, OneExpr, L, SCEV::FlagAnyWrap)); + // Limit the lifetime of SCEVExpander. + const DataLayout &DL = Header->getModule()->getDataLayout(); + SCEVExpander Expander(*SE, DL, "reroll"); + Value *NewIV = Expander.expandCodeFor(H, InstIV->getType(), Header->begin()); + + for (auto &KV : Uses) + if (KV.second.find_first() == 0) + KV.first->replaceUsesOfWith(Inst, NewIV); + + if (BranchInst *BI = dyn_cast(Header->getTerminator())) { + // FIXME: Why do we need this check? + if (Uses[BI].find_first() == IL_All) { + const SCEV *ICSCEV = nullptr; + + if (NeedNewIV) + ICSCEV = SE->getMulExpr(IterCount, + SE->getConstant(IterCount->getType(), Scale)); + else + ICSCEV = RealIVSCEV->evaluateAtIteration(IterCount, *SE); + + // Iteration count SCEV minus 1 + const SCEV *Minus1SCEV = + SE->getConstant(ICSCEV->getType(), Negative ? -1 : 1); + if (Inst->getType()->isPointerTy()) + Minus1SCEV = SE->getMulExpr(Minus1SCEV, SizeOfExpr); + const SCEV *ICMinus1SCEV = SE->getMinusSCEV(ICSCEV, Minus1SCEV); + + // Iteration count minus 1 + Value *ICMinus1 = nullptr; + if (isa(ICMinus1SCEV)) + ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), BI); + else { + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) + Preheader = InsertPreheaderForLoop(L, Parent); + ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), + Preheader->getTerminator()); + } + + Value *Cond = + new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinus1, "exitcond"); + BI->setCondition(Cond); + + if (BI->getSuccessor(1) != Header) + BI->swapSuccessors(); + } + } +} + void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) { BasicBlock *Header = L->getHeader(); // Remove instructions associated with non-base iterations. @@ -1267,58 +1525,18 @@ ++J; } - 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(SE->getSCEV(DRS.BaseInst)); - const SCEV *Start = RealIVSCEV->getStart(); - const SCEVAddRecExpr *H = cast - (SE->getAddRecExpr(Start, - SE->getConstant(RealIVSCEV->getType(), 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(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)); + bool HasTwoIVs = LoopCtrlOnlyIV && LoopCtrlOnlyIV != IV; - Value *ICMinus1; // Iteration count minus 1 - if (isa(ICMinus1SCEV)) { - ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), BI); - } else { - BasicBlock *Preheader = L->getLoopPreheader(); - if (!Preheader) - Preheader = InsertPreheaderForLoop(L, Parent); - - ICMinus1 = Expander.expandCodeFor(ICMinus1SCEV, NewIV->getType(), - Preheader->getTerminator()); - } - - Value *Cond = - new ICmpInst(BI, CmpInst::ICMP_EQ, NewIV, ICMinus1, "exitcond"); - BI->setCondition(Cond); - - if (BI->getSuccessor(1) != Header) - BI->swapSuccessors(); - } - } - } - } + // We need to handle loop control only IVs + if (HasTwoIVs) { + replaceNonLoopCtrlIV(); + replaceIV(LoopCtrlOnlyIV, LoopCtrlOnlyIV, 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); @@ -1444,13 +1662,14 @@ 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, Reductions, IVToIncMap, + LoopCtrlOnlyIV); 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()) @@ -1497,6 +1716,8 @@ // 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(); + LoopCtrlOnlyIV = nullptr; collectPossibleIVs(L, PossibleIVs); if (PossibleIVs.empty()) { Index: test/Transforms/LoopReroll/complex_reroll.ll =================================================================== --- /dev/null +++ test/Transforms/LoopReroll/complex_reroll.ll @@ -0,0 +1,93 @@ +; 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: %0 = load i8, i8* %buf.021, align 1 +;CHECK-NEXT: %conv = zext i8 %0 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, 15 +;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 +} +