X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopIndexSplit.cpp;h=5faec97a9711d1b52fcc1f2016712b340599db38;hb=2a6a6457094e05e5f5ab34f90dbd25c13d61f8b5;hp=9e2f11bb6dea4aa7ce466bbb21fa1c6833988e21;hpb=d15dd8c52595d5040a325052ee021d63844e28f0;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp index 9e2f11bb6de..5faec97a971 100644 --- a/lib/Transforms/Scalar/LoopIndexSplit.cpp +++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Devang Patel and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -151,7 +151,7 @@ namespace { /// Update ExitBB PHINodes' to reflect this change. void updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, BasicBlock *Header, - PHINode *IV, Instruction *IVIncrement); + PHINode *IV, Instruction *IVIncrement, Loop *LP); /// moveExitCondition - Move exit condition EC into split condition block CondBB. void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, @@ -195,11 +195,12 @@ namespace { // Induction variable's final loop exit value operand number in exit condition.. unsigned ExitValueNum; }; - - char LoopIndexSplit::ID = 0; - RegisterPass X ("loop-index-split", "Index Split Loops"); } +char LoopIndexSplit::ID = 0; +static RegisterPass +X("loop-index-split", "Index Split Loops"); + LoopPass *llvm::createLoopIndexSplitPass() { return new LoopIndexSplit(); } @@ -232,8 +233,8 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { return false; // First see if it is possible to eliminate loop itself or not. - for (SmallVector::iterator SI = SplitData.begin(), - E = SplitData.end(); SI != E;) { + for (SmallVector::iterator SI = SplitData.begin(); + SI != SplitData.end();) { SplitInfo &SD = *SI; ICmpInst *CI = dyn_cast(SD.SplitCondition); if (SD.SplitCondition->getOpcode() == Instruction::And) { @@ -244,8 +245,7 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { return Changed; } else { SmallVector::iterator Delete_SI = SI; - ++SI; - SplitData.erase(Delete_SI); + SI = SplitData.erase(Delete_SI); } } else if (CI && CI->getPredicate() == ICmpInst::ICMP_EQ) { @@ -256,8 +256,7 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { return Changed; } else { SmallVector::iterator Delete_SI = SI; - ++SI; - SplitData.erase(Delete_SI); + SI = SplitData.erase(Delete_SI); } } else ++SI; @@ -301,23 +300,23 @@ void LoopIndexSplit::findIndVar(Value *V, Loop *L) { Value *Op0 = I->getOperand(0); Value *Op1 = I->getOperand(1); - if (PHINode *PN = dyn_cast(Op0)) { - if (PN->getParent() == L->getHeader() - && isa(Op1)) { - IndVar = PN; - IndVarIncrement = I; - return; - } - } - - if (PHINode *PN = dyn_cast(Op1)) { - if (PN->getParent() == L->getHeader() - && isa(Op0)) { - IndVar = PN; - IndVarIncrement = I; - return; - } - } + if (PHINode *PN = dyn_cast(Op0)) + if (PN->getParent() == L->getHeader()) + if (ConstantInt *CI = dyn_cast(Op1)) + if (CI->isOne()) { + IndVar = PN; + IndVarIncrement = I; + return; + } + + if (PHINode *PN = dyn_cast(Op1)) + if (PN->getParent() == L->getHeader()) + if (ConstantInt *CI = dyn_cast(Op0)) + if (CI->isOne()) { + IndVar = PN; + IndVarIncrement = I; + return; + } return; } @@ -582,7 +581,7 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) { ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, SD.SplitValue, ExitValue, "lisplit", Terminator); - Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit", + Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", Terminator); SD.SplitCondition->replaceAllUsesWith(NSplitCond); SD.SplitCondition->eraseFromParent(); @@ -597,11 +596,27 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) { if (isa(I) || I == LTerminator) continue; - if (I == IndVarIncrement) - I->replaceAllUsesWith(ExitValue); - else + if (I == IndVarIncrement) { + // Replace induction variable increment if it is not used outside + // the loop. + bool UsedOutsideLoop = false; + for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); + UI != E; ++UI) { + if (Instruction *Use = dyn_cast(UI)) + if (!L->contains(Use->getParent())) { + UsedOutsideLoop = true; + break; + } + } + if (!UsedOutsideLoop) { + I->replaceAllUsesWith(ExitValue); + I->eraseFromParent(); + } + } + else { I->replaceAllUsesWith(UndefValue::get(I->getType())); - I->eraseFromParent(); + I->eraseFromParent(); + } } LPM->deleteLoopFromQueue(L); @@ -676,7 +691,7 @@ bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD, continue; // Check if I is induction variable increment instruction. - if (!IndVarIncrement && I->getOpcode() == Instruction::Add) { + if (I->getOpcode() == Instruction::Add) { Value *Op0 = I->getOperand(0); Value *Op1 = I->getOperand(1); @@ -685,16 +700,23 @@ bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD, if ((PN = dyn_cast(Op0))) { if ((CI = dyn_cast(Op1))) - IndVarIncrement = I; + if (CI->isOne()) { + if (!IndVarIncrement && PN == IndVar) + IndVarIncrement = I; + // else this is another loop induction variable + continue; + } } else if ((PN = dyn_cast(Op1))) { if ((CI = dyn_cast(Op0))) - IndVarIncrement = I; + if (CI->isOne()) { + if (!IndVarIncrement && PN == IndVar) + IndVarIncrement = I; + // else this is another loop induction variable + continue; + } } - - if (IndVarIncrement && PN == IndVar && CI->isOne()) - continue; - } + } // I is an Exit condition if next instruction is block terminator. // Exit condition is OK if it compares loop invariant exit value, @@ -728,6 +750,27 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { else NV = V1; + if (ExitCondition->getPredicate() == ICmpInst::ICMP_SGT + || ExitCondition->getPredicate() == ICmpInst::ICMP_UGT + || ExitCondition->getPredicate() == ICmpInst::ICMP_SGE + || ExitCondition->getPredicate() == ICmpInst::ICMP_UGE) { + ExitCondition->swapOperands(); + if (ExitValueNum) + ExitValueNum = 0; + else + ExitValueNum = 1; + } + + Value *NUB = NULL; + Value *NLB = NULL; + Value *UB = ExitCondition->getOperand(ExitValueNum); + const Type *Ty = NV->getType(); + bool Sign = ExitCondition->isSignedPredicate(); + BasicBlock *Preheader = L->getLoopPreheader(); + Instruction *PHTerminator = Preheader->getTerminator(); + + assert (NV && "Unexpected value"); + switch (CI->getPredicate()) { case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_SLE: @@ -740,9 +783,15 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = LB; i < NUB ; ++i) // LOOP_BODY // - - - + if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT + || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) { + Value *A = BinaryOperator::CreateAdd(NV, ConstantInt::get(Ty, 1, Sign), + "lsplit.add", PHTerminator); + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + A, UB,"lsplit,c", PHTerminator); + NUB = SelectInst::Create(C, A, UB, "lsplit.nub", PHTerminator); + } + // for (i = LB; i <= UB; ++i) // if (i <= NV && ...) // LOOP_BODY @@ -752,6 +801,12 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = LB; i <= NUB ; ++i) // LOOP_BODY // + else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE + || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) { + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + NV, UB, "lsplit.c", PHTerminator); + NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator); + } break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_SLT: @@ -764,8 +819,12 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = LB; i < NUB ; ++i) // LOOP_BODY // - - + if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT + || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) { + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + NV, UB, "lsplit.c", PHTerminator); + NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator); + } // for (i = LB; i <= UB; ++i) // if (i < NV && ...) @@ -776,6 +835,14 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = LB; i <= NUB ; ++i) // LOOP_BODY // + else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE + || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) { + Value *S = BinaryOperator::CreateSub(NV, ConstantInt::get(Ty, 1, Sign), + "lsplit.add", PHTerminator); + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + S, UB, "lsplit.c", PHTerminator); + NUB = SelectInst::Create(C, S, UB, "lsplit.nub", PHTerminator); + } break; case ICmpInst::ICMP_UGE: case ICmpInst::ICMP_SGE: @@ -788,6 +855,11 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = NLB; i (< or <=) UB ; ++i) // LOOP_BODY // + { + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + NV, StartValue, "lsplit.c", PHTerminator); + NLB = SelectInst::Create(C, StartValue, NV, "lsplit.nlb", PHTerminator); + } break; case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_SGT: @@ -800,10 +872,26 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // for (i = NLB; i (< or <=) UB ; ++i) // LOOP_BODY // + { + Value *A = BinaryOperator::CreateAdd(NV, ConstantInt::get(Ty, 1, Sign), + "lsplit.add", PHTerminator); + Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, + A, StartValue, "lsplit.c", PHTerminator); + NLB = SelectInst::Create(C, StartValue, A, "lsplit.nlb", PHTerminator); + } break; default: assert ( 0 && "Unexpected split condition predicate"); } + + if (NLB) { + unsigned i = IndVar->getBasicBlockIndex(Preheader); + IndVar->setIncomingValue(i, NLB); + } + + if (NUB) { + ExitCondition->setOperand(ExitValueNum, NUB); + } } /// updateLoopIterationSpace - Current loop body is covered by an AND /// instruction whose operands compares induction variables with loop @@ -811,6 +899,9 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { /// updating appropriate start and end values for induction variable. bool LoopIndexSplit::updateLoopIterationSpace(SplitInfo &SD) { BasicBlock *Header = L->getHeader(); + BasicBlock *ExitingBlock = ExitCondition->getParent(); + BasicBlock *SplitCondBlock = SD.SplitCondition->getParent(); + ICmpInst *Op0 = cast(SD.SplitCondition->getOperand(0)); ICmpInst *Op1 = cast(SD.SplitCondition->getOperand(1)); @@ -865,11 +956,83 @@ bool LoopIndexSplit::updateLoopIterationSpace(SplitInfo &SD) { // loop may not be eliminated. if (!safeExitingBlock(SD, ExitCondition->getParent())) return false; - + + // Verify that loop exiting block has only two predecessor, where one predecessor + // is split condition block. The other predecessor will become exiting block's + // dominator after CFG is updated. TODO : Handle CFG's where exiting block has + // more then two predecessors. This requires extra work in updating dominator + // information. + BasicBlock *ExitingBBPred = NULL; + for (pred_iterator PI = pred_begin(ExitingBlock), PE = pred_end(ExitingBlock); + PI != PE; ++PI) { + BasicBlock *BB = *PI; + if (SplitCondBlock == BB) + continue; + if (ExitingBBPred) + return false; + else + ExitingBBPred = BB; + } + + // Update loop bounds to absorb Op0 check. updateLoopBounds(Op0); + // Update loop bounds to absorb Op1 check. updateLoopBounds(Op1); + // Update CFG - return false; + + // Unconditionally connect split block to its remaining successor. + BranchInst *SplitTerminator = + cast(SplitCondBlock->getTerminator()); + BasicBlock *Succ0 = SplitTerminator->getSuccessor(0); + BasicBlock *Succ1 = SplitTerminator->getSuccessor(1); + if (Succ0 == ExitCondition->getParent()) + SplitTerminator->setUnconditionalDest(Succ1); + else + SplitTerminator->setUnconditionalDest(Succ0); + + // Remove split condition. + SD.SplitCondition->eraseFromParent(); + if (Op0->use_begin() == Op0->use_end()) + Op0->eraseFromParent(); + if (Op1->use_begin() == Op1->use_end()) + Op1->eraseFromParent(); + + BranchInst *ExitInsn = + dyn_cast(ExitingBlock->getTerminator()); + assert (ExitInsn && "Unable to find suitable loop exit branch"); + BasicBlock *ExitBlock = ExitInsn->getSuccessor(1); + if (L->contains(ExitBlock)) + ExitBlock = ExitInsn->getSuccessor(0); + + // Update domiantor info. Now, ExitingBlock has only one predecessor, + // ExitingBBPred, and it is ExitingBlock's immediate domiantor. + DT->changeImmediateDominator(ExitingBlock, ExitingBBPred); + + // If ExitingBlock is a member of loop BB's DF list then replace it with + // loop header and exit block. + for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); + I != E; ++I) { + BasicBlock *BB = *I; + if (BB == Header || BB == ExitingBlock) + continue; + DominanceFrontier::iterator BBDF = DF->find(BB); + DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin(); + DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end(); + while (DomSetI != DomSetE) { + DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI; + ++DomSetI; + BasicBlock *DFBB = *CurrentItr; + if (DFBB == ExitingBlock) { + BBDF->second.erase(DFBB); + BBDF->second.insert(Header); + if (Header != ExitingBlock) + BBDF->second.insert(ExitBlock); + } + } + } + + return true; } @@ -978,6 +1141,11 @@ bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) { BasicBlock *Succ0 = SplitTerminator->getSuccessor(0); BasicBlock *Succ1 = SplitTerminator->getSuccessor(1); + // If split block does not dominate the latch then this is not a diamond. + // Such loop may not benefit from index split. + if (!DT->dominates(SplitCondBlock, Latch)) + return false; + // Finally this split condition is safe only if merge point for // split condition branch is loop latch. This check along with previous // check, to ensure that exit condition is in either loop latch or header, @@ -1015,8 +1183,13 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { if (ExitCondition->getPredicate() == ICmpInst::ICMP_SGT || ExitCondition->getPredicate() == ICmpInst::ICMP_UGT || ExitCondition->getPredicate() == ICmpInst::ICMP_SGE - || ExitCondition->getPredicate() == ICmpInst::ICMP_UGE) + || ExitCondition->getPredicate() == ICmpInst::ICMP_UGE) { ExitCondition->swapOperands(); + if (ExitValueNum) + ExitValueNum = 0; + else + ExitValueNum = 1; + } switch (ExitCondition->getPredicate()) { case ICmpInst::ICMP_SGT: @@ -1056,7 +1229,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // A; // for (i = max(LB, BSV); i < UB; ++i) // B; - BSV = BinaryOperator::createAdd(SD.SplitValue, + BSV = BinaryOperator::CreateAdd(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.add", PHTerminator); AEV = BSV; @@ -1087,7 +1260,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // B; // for (i = max(LB, BSV); i < UB; ++i) // A; - BSV = BinaryOperator::createAdd(SD.SplitValue, + BSV = BinaryOperator::CreateAdd(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.add", PHTerminator); AEV = BSV; @@ -1115,7 +1288,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // A; // for (i = max(LB, BSV); i <= UB; ++i) // B; - AEV = BinaryOperator::createSub(SD.SplitValue, + AEV = BinaryOperator::CreateSub(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.sub", PHTerminator); break; @@ -1131,7 +1304,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // A; // for (i = max(LB, BSV); i <= UB; ++i) // B; - BSV = BinaryOperator::createAdd(SD.SplitValue, + BSV = BinaryOperator::CreateAdd(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.add", PHTerminator); break; @@ -1147,7 +1320,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // B; // for (i = max(LB, BSV); i <= UB; ++i) // A; - BSV = BinaryOperator::createAdd(SD.SplitValue, + BSV = BinaryOperator::CreateAdd(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.add", PHTerminator); break; @@ -1164,7 +1337,7 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // B; // for (i = max(LB, BSV); i <= UB; ++i) // A; - AEV = BinaryOperator::createSub(SD.SplitValue, + AEV = BinaryOperator::CreateSub(SD.SplitValue, ConstantInt::get(Ty, 1, Sign), "lsplit.sub", PHTerminator); break; @@ -1181,21 +1354,40 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // values in original loop's preheader. // A_ExitValue = min(SplitValue, OrignalLoopExitValue) // B_StartValue = max(SplitValue, OriginalLoopStartValue) + Instruction *InsertPt = L->getHeader()->getFirstNonPHI(); + + // If ExitValue operand is also defined in Loop header then + // insert new ExitValue after this operand definition. + if (Instruction *EVN = + dyn_cast(ExitCondition->getOperand(ExitValueNum))) { + if (!isa(EVN)) + if (InsertPt->getParent() == EVN->getParent()) { + BasicBlock::iterator LHBI = L->getHeader()->begin(); + BasicBlock::iterator LHBE = L->getHeader()->end(); + for(;LHBI != LHBE; ++LHBI) { + Instruction *I = LHBI; + if (I == EVN) + break; + } + InsertPt = ++LHBI; + } + } Value *C1 = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, AEV, ExitCondition->getOperand(ExitValueNum), - "lsplit.ev", PHTerminator); - SD.A_ExitValue = new SelectInst(C1, AEV, - ExitCondition->getOperand(ExitValueNum), - "lsplit.ev", PHTerminator); - + "lsplit.ev", InsertPt); + + SD.A_ExitValue = SelectInst::Create(C1, AEV, + ExitCondition->getOperand(ExitValueNum), + "lsplit.ev", InsertPt); + Value *C2 = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, BSV, StartValue, "lsplit.sv", PHTerminator); - SD.B_StartValue = new SelectInst(C2, StartValue, BSV, - "lsplit.sv", PHTerminator); + SD.B_StartValue = SelectInst::Create(C2, StartValue, BSV, + "lsplit.sv", PHTerminator); } /// splitLoop - Split current loop L in two loops using split information @@ -1225,6 +1417,11 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) { if (!Succ0->getSinglePredecessor() || !Succ1->getSinglePredecessor()) return false; + // If Exiting block includes loop variant instructions then this + // loop may not be split safely. + if (!safeExitingBlock(SD, ExitCondition->getParent())) + return false; + // After loop is cloned there are two loops. // // First loop, referred as ALoop, executes first part of loop's iteration @@ -1288,7 +1485,13 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) { PN->addIncoming(SD.B_StartValue, A_ExitingBlock); else { PHINode *OrigPN = cast(InverseMap[PN]); - Value *V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock); + Value *V2 = NULL; + // If loop header is also loop exiting block then + // OrigPN is incoming value for B loop header. + if (A_ExitingBlock == L->getHeader()) + V2 = OrigPN; + else + V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock); PN->addIncoming(V2, A_ExitingBlock); } } else @@ -1327,7 +1530,7 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) { BI != BE; ++BI) { if (PHINode *PN = dyn_cast(BI)) { Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock); - PHINode *newPHI = new PHINode(PN->getType(), PN->getName()); + PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName()); newPHI->addIncoming(V1, A_ExitingBlock); A_ExitBlock->getInstList().push_front(newPHI); PN->removeIncomingValue(A_ExitBlock); @@ -1402,20 +1605,25 @@ void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, // destination. BranchInst *ExitingBR = cast(ExitingBB->getTerminator()); ExitingBR->moveBefore(CurrentBR); - if (ExitingBR->getSuccessor(0) == ExitBB) + BasicBlock *OrigDestBB = NULL; + if (ExitingBR->getSuccessor(0) == ExitBB) { + OrigDestBB = ExitingBR->getSuccessor(1); ExitingBR->setSuccessor(1, ActiveBB); - else + } + else { + OrigDestBB = ExitingBR->getSuccessor(0); ExitingBR->setSuccessor(0, ActiveBB); + } // Remove split condition and current split condition branch. SC->eraseFromParent(); CurrentBR->eraseFromParent(); - // Connect exiting block to split condition block. - new BranchInst(CondBB, ExitingBB); + // Connect exiting block to original destination. + BranchInst::Create(OrigDestBB, ExitingBB); // Update PHINodes - updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd); + updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP); // Fix dominator info. // ExitBB is now dominated by CondBB @@ -1449,44 +1657,38 @@ void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, /// - ExitBB's single predecessor was Latch /// - Latch's second successor was Header /// Now -/// - ExitBB's single predecessor was Header -/// - Latch's one and only successor was Header +/// - ExitBB's single predecessor is Header +/// - Latch's one and only successor is Header /// /// Update ExitBB PHINodes' to reflect this change. void LoopIndexSplit::updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, BasicBlock *Header, - PHINode *IV, Instruction *IVIncrement) { + PHINode *IV, Instruction *IVIncrement, + Loop *LP) { for (BasicBlock::iterator BI = ExitBB->begin(), BE = ExitBB->end(); - BI != BE; ++BI) { + BI != BE; ) { PHINode *PN = dyn_cast(BI); + ++BI; if (!PN) break; Value *V = PN->getIncomingValueForBlock(Latch); if (PHINode *PHV = dyn_cast(V)) { - // PHV is in Latch. PHV has two uses, one use is in ExitBB PHINode - // (i.e. PN :)). - // The second use is in Header and it is new incoming value for PN. - PHINode *U1 = NULL; - PHINode *U2 = NULL; + // PHV is in Latch. PHV has one use is in ExitBB PHINode. And one use + // in Header which is new incoming value for PN. Value *NewV = NULL; for (Value::use_iterator UI = PHV->use_begin(), E = PHV->use_end(); - UI != E; ++UI) { - if (!U1) - U1 = cast(*UI); - else if (!U2) - U2 = cast(*UI); - else - assert ( 0 && "Unexpected third use of this PHINode"); - } - assert (U1 && U2 && "Unable to find two uses"); - - if (U1->getParent() == Header) - NewV = U1; - else - NewV = U2; - PN->addIncoming(NewV, Header); + UI != E; ++UI) + if (PHINode *U = dyn_cast(*UI)) + if (LP->contains(U->getParent())) { + NewV = U; + break; + } + + // Add incoming value from header only if PN has any use inside the loop. + if (NewV) + PN->addIncoming(NewV, Header); } else if (Instruction *PHI = dyn_cast(V)) { // If this instruction is IVIncrement then IV is new incoming value