X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopIndexSplit.cpp;h=5faec97a9711d1b52fcc1f2016712b340599db38;hb=2a6a6457094e05e5f5ab34f90dbd25c13d61f8b5;hp=6582f368a739f8de1fb3d121309cecfa7eec062a;hpb=1c01350f0fa65771c626227dc00d6055a940a869;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp index 6582f368a73..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, @@ -763,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) @@ -783,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: @@ -801,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) @@ -815,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: @@ -836,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: @@ -851,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: @@ -1119,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, @@ -1156,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: @@ -1197,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; @@ -1228,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; @@ -1256,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; @@ -1272,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; @@ -1288,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; @@ -1305,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; @@ -1323,22 +1355,39 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { // 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", 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 @@ -1368,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 @@ -1431,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 @@ -1470,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); @@ -1545,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 @@ -1592,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