X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopIndexSplit.cpp;h=5faec97a9711d1b52fcc1f2016712b340599db38;hb=2a6a6457094e05e5f5ab34f90dbd25c13d61f8b5;hp=8053554c17c12d13764797c19c224ada0dc5a4e5;hpb=4a3c0ac7980be53eb6e5f85c394895ad945fc68e;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp index 8053554c17c..5faec97a971 100644 --- a/lib/Transforms/Scalar/LoopIndexSplit.cpp +++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp @@ -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; @@ -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); @@ -770,11 +785,11 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLT || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) { - Value *A = BinaryOperator::createAdd(NV, ConstantInt::get(Ty, 1, Sign), + 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 = new SelectInst (C, A, UB, "lsplit.nub", PHTerminator); + NUB = SelectInst::Create(C, A, UB, "lsplit.nub", PHTerminator); } // for (i = LB; i <= UB; ++i) @@ -790,7 +805,7 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) { Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, NV, UB, "lsplit.c", PHTerminator); - NUB = new SelectInst (C, NV, UB, "lsplit.nub", PHTerminator); + NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator); } break; case ICmpInst::ICMP_ULT: @@ -808,7 +823,7 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { || ExitCondition->getPredicate() == ICmpInst::ICMP_ULT) { Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, NV, UB, "lsplit.c", PHTerminator); - NUB = new SelectInst (C, NV, UB, "lsplit.nub", PHTerminator); + NUB = SelectInst::Create(C, NV, UB, "lsplit.nub", PHTerminator); } // for (i = LB; i <= UB; ++i) @@ -822,11 +837,11 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // else if (ExitCondition->getPredicate() == ICmpInst::ICMP_SLE || ExitCondition->getPredicate() == ICmpInst::ICMP_ULE) { - Value *S = BinaryOperator::createSub(NV, ConstantInt::get(Ty, 1, Sign), + 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 = new SelectInst (C, S, UB, "lsplit.nub", PHTerminator); + NUB = SelectInst::Create(C, S, UB, "lsplit.nub", PHTerminator); } break; case ICmpInst::ICMP_UGE: @@ -843,7 +858,7 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { { Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, NV, StartValue, "lsplit.c", PHTerminator); - NLB = new SelectInst (C, StartValue, NV, "lsplit.nlb", PHTerminator); + NLB = SelectInst::Create(C, StartValue, NV, "lsplit.nlb", PHTerminator); } break; case ICmpInst::ICMP_UGT: @@ -858,11 +873,11 @@ void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { // LOOP_BODY // { - Value *A = BinaryOperator::createAdd(NV, ConstantInt::get(Ty, 1, Sign), + 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 = new SelectInst (C, StartValue, A, "lsplit.nlb", PHTerminator); + NLB = SelectInst::Create(C, StartValue, A, "lsplit.nlb", PHTerminator); } break; default: @@ -1126,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, @@ -1209,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; @@ -1240,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; @@ -1268,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; @@ -1284,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; @@ -1300,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; @@ -1317,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; @@ -1358,16 +1378,16 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { ExitCondition->getOperand(ExitValueNum), "lsplit.ev", InsertPt); - SD.A_ExitValue = new SelectInst(C1, AEV, - ExitCondition->getOperand(ExitValueNum), - "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 @@ -1510,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); @@ -1600,7 +1620,7 @@ void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, CurrentBR->eraseFromParent(); // Connect exiting block to original destination. - new BranchInst(OrigDestBB, ExitingBB); + BranchInst::Create(OrigDestBB, ExitingBB); // Update PHINodes updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP);