X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopIndexSplit.cpp;h=5faec97a9711d1b52fcc1f2016712b340599db38;hb=2a6a6457094e05e5f5ab34f90dbd25c13d61f8b5;hp=f182c9138ca446ae5d51dc7ac98024943b28d8f8;hpb=d35ed2c16d037a7ad3d32ad46d1439a67e5daff7;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp index f182c9138ca..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. // //===----------------------------------------------------------------------===// // @@ -111,7 +111,14 @@ namespace { /// instruction then loop body is executed only for one iteration. In /// such case eliminate loop structure surrounding this loop body. For bool processOneIterationLoop(SplitInfo &SD); - + + void updateLoopBounds(ICmpInst *CI); + /// updateLoopIterationSpace - Current loop body is covered by an AND + /// instruction whose operands compares induction variables with loop + /// invariants. If possible, hoist this check outside the loop by + /// updating appropriate start and end values for induction variable. + bool updateLoopIterationSpace(SplitInfo &SD); + /// If loop header includes loop variant instruction operands then /// this loop may not be eliminated. bool safeHeader(SplitInfo &SD, BasicBlock *BB); @@ -144,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, @@ -188,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(); } @@ -225,11 +233,22 @@ 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 (CI && CI->getPredicate() == ICmpInst::ICMP_EQ) { + if (SD.SplitCondition->getOpcode() == Instruction::And) { + Changed = updateLoopIterationSpace(SD); + if (Changed) { + ++NumIndexSplit; + // If is loop is eliminated then nothing else to do here. + return Changed; + } else { + SmallVector::iterator Delete_SI = SI; + SI = SplitData.erase(Delete_SI); + } + } + else if (CI && CI->getPredicate() == ICmpInst::ICMP_EQ) { Changed = processOneIterationLoop(SD); if (Changed) { ++NumIndexSplit; @@ -237,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; @@ -282,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; } @@ -336,25 +354,11 @@ void LoopIndexSplit::findLoopConditionals() { if (!CI) return; - // FIXME + // FIXME if (CI->getPredicate() == ICmpInst::ICMP_EQ || CI->getPredicate() == ICmpInst::ICMP_NE) return; - if (CI->getPredicate() == ICmpInst::ICMP_SGT - || CI->getPredicate() == ICmpInst::ICMP_UGT - || CI->getPredicate() == ICmpInst::ICMP_SGE - || CI->getPredicate() == ICmpInst::ICMP_UGE) { - - BasicBlock *FirstSuccessor = BR->getSuccessor(0); - // splitLoop() is expecting LT/LE as exit condition predicate. - // Swap operands here if possible to meet this requirement. - if (!L->contains(FirstSuccessor)) - CI->swapOperands(); - else - return; - } - ExitCondition = CI; // Exit condition's one operand is loop invariant exit value and second @@ -401,6 +405,25 @@ void LoopIndexSplit::findSplitCondition() { if (BR->isUnconditional()) continue; + if (Instruction *AndI = dyn_cast(BR->getCondition())) { + if (AndI->getOpcode() == Instruction::And) { + ICmpInst *Op0 = dyn_cast(AndI->getOperand(0)); + ICmpInst *Op1 = dyn_cast(AndI->getOperand(1)); + + if (!Op0 || !Op1) + continue; + + if (!safeICmpInst(Op0, SD)) + continue; + SD.clear(); + if (!safeICmpInst(Op1, SD)) + continue; + SD.clear(); + SD.SplitCondition = AndI; + SplitData.push_back(SD); + continue; + } + } ICmpInst *CI = dyn_cast(BR->getCondition()); if (!CI || CI == ExitCondition) continue; @@ -410,10 +433,10 @@ void LoopIndexSplit::findSplitCondition() { // If split condition predicate is GT or GE then first execute // false branch of split condition. - if (CI->getPredicate() != ICmpInst::ICMP_ULT - && CI->getPredicate() != ICmpInst::ICMP_SLT - && CI->getPredicate() != ICmpInst::ICMP_ULE - && CI->getPredicate() != ICmpInst::ICMP_SLE) + if (CI->getPredicate() == ICmpInst::ICMP_UGT + || CI->getPredicate() == ICmpInst::ICMP_SGT + || CI->getPredicate() == ICmpInst::ICMP_UGE + || CI->getPredicate() == ICmpInst::ICMP_SGE) SD.UseTrueBranchFirst = false; // If one operand is loop invariant and second operand is SCEVAddRecExpr @@ -500,6 +523,29 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) { if (!safeExitingBlock(SD, ExitCondition->getParent())) return false; + // Filter loops where split condition's false branch is not empty. + if (ExitCondition->getParent() != Header->getTerminator()->getSuccessor(1)) + return false; + + // If split condition is not safe then do not process this loop. + // For example, + // for(int i = 0; i < N; i++) { + // if ( i == XYZ) { + // A; + // else + // B; + // } + // C; + // D; + // } + if (!safeSplitCondition(SD)) + return false; + + BasicBlock *Latch = L->getLoopLatch(); + BranchInst *BR = dyn_cast(Latch->getTerminator()); + if (!BR) + return false; + // Update CFG. // Replace index variable with split value in loop body. Loop body is executed @@ -507,11 +553,7 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) { IndVar->replaceAllUsesWith(SD.SplitValue); // Remove Latch to Header edge. - BasicBlock *Latch = L->getLoopLatch(); BasicBlock *LatchSucc = NULL; - BranchInst *BR = dyn_cast(Latch->getTerminator()); - if (!BR) - return false; Header->removePredecessor(Latch); for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch); SI != E; ++SI) { @@ -539,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(); @@ -554,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); @@ -633,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); @@ -642,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, @@ -672,6 +737,305 @@ bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD, return true; } +void LoopIndexSplit::updateLoopBounds(ICmpInst *CI) { + + Value *V0 = CI->getOperand(0); + Value *V1 = CI->getOperand(1); + Value *NV = NULL; + + SCEVHandle SH0 = SE->getSCEV(V0); + + if (SH0->isLoopInvariant(L)) + NV = V0; + 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: + // for (i = LB; i < UB; ++i) + // if (i <= NV && ...) + // LOOP_BODY + // + // is transformed into + // NUB = min (NV+1, UB) + // 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 + // + // is transformed into + // NUB = min (NV, UB) + // 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: + // for (i = LB; i < UB; ++i) + // if (i < NV && ...) + // LOOP_BODY + // + // is transformed into + // NUB = min (NV, UB) + // 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 && ...) + // LOOP_BODY + // + // is transformed into + // NUB = min (NV -1 , UB) + // 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: + // for (i = LB; i (< or <=) UB; ++i) + // if (i >= NV && ...) + // LOOP_BODY + // + // is transformed into + // NLB = max (NV, LB) + // 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: + // for (i = LB; i (< or <=) UB; ++i) + // if (i > NV && ...) + // LOOP_BODY + // + // is transformed into + // NLB = max (NV+1, LB) + // 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 +/// invariants. If possible, hoist this check outside the loop by +/// 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)); + + if (Op0->getPredicate() == ICmpInst::ICMP_EQ + || Op0->getPredicate() == ICmpInst::ICMP_NE + || Op0->getPredicate() == ICmpInst::ICMP_EQ + || Op0->getPredicate() == ICmpInst::ICMP_NE) + return false; + + // Check if SplitCondition dominates entire loop body + // or not. + + // If SplitCondition is not in loop header then this loop is not suitable + // for this transformation. + if (SD.SplitCondition->getParent() != Header) + return false; + + // If loop header includes loop variant instruction operands then + // this loop may not be eliminated. + Instruction *Terminator = Header->getTerminator(); + for(BasicBlock::iterator BI = Header->begin(), BE = Header->end(); + BI != BE; ++BI) { + Instruction *I = BI; + + // PHI Nodes are OK. + if (isa(I)) + continue; + + // SplitCondition itself is OK. + if (I == SD.SplitCondition) + continue; + if (I == Op0 || I == Op1) + continue; + + // Induction variable is OK. + if (I == IndVar) + continue; + + // Induction variable increment is OK. + if (I == IndVarIncrement) + continue; + + // Terminator is also harmless. + if (I == Terminator) + continue; + + // Otherwise we have a instruction that may not be safe. + return false; + } + + // If Exiting block includes loop variant instructions then this + // 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 + + // 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; +} + + /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB. /// This routine is used to remove split condition's dead branch, dominated by /// DeadBB. LiveBB dominates split conidition's other branch. @@ -727,8 +1091,9 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, while (!WorkList.empty()) { BasicBlock *BB = WorkList.back(); WorkList.pop_back(); for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); - BBI != BBE; ++BBI) { + BBI != BBE; ) { Instruction *I = BBI; + ++BBI; I->replaceAllUsesWith(UndefValue::get(I->getType())); I->eraseFromParent(); } @@ -770,23 +1135,15 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) { BasicBlock *SplitCondBlock = SD.SplitCondition->getParent(); - - // Unable to handle triange loops at the moment. - // In triangle loop, split condition is in header and one of the - // the split destination is loop latch. If split condition is EQ - // then such loops are already handle in processOneIterationLoop(). - BasicBlock *Latch = L->getLoopLatch(); + BasicBlock *Latch = L->getLoopLatch(); BranchInst *SplitTerminator = cast(SplitCondBlock->getTerminator()); BasicBlock *Succ0 = SplitTerminator->getSuccessor(0); BasicBlock *Succ1 = SplitTerminator->getSuccessor(1); - if (L->getHeader() == SplitCondBlock - && (Latch == Succ0 || Latch == Succ1)) - return false; - - // If split condition branches heads do not have single predecessor, - // SplitCondBlock, then is not possible to remove inactive branch. - if (!Succ0->getSinglePredecessor() || !Succ1->getSinglePredecessor()) + + // 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 @@ -823,6 +1180,17 @@ void LoopIndexSplit::calculateLoopBounds(SplitInfo &SD) { Value *AEV = SD.SplitValue; Value *BSV = SD.SplitValue; + 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; + } + switch (ExitCondition->getPredicate()) { case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_UGT: @@ -861,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; @@ -892,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; @@ -920,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; @@ -936,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; @@ -952,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; @@ -969,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; @@ -986,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 @@ -1010,6 +1397,31 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) { if (!safeSplitCondition(SD)) return false; + BasicBlock *SplitCondBlock = SD.SplitCondition->getParent(); + + // Unable to handle triange loops at the moment. + // In triangle loop, split condition is in header and one of the + // the split destination is loop latch. If split condition is EQ + // then such loops are already handle in processOneIterationLoop(). + BasicBlock *Latch = L->getLoopLatch(); + BranchInst *SplitTerminator = + cast(SplitCondBlock->getTerminator()); + BasicBlock *Succ0 = SplitTerminator->getSuccessor(0); + BasicBlock *Succ1 = SplitTerminator->getSuccessor(1); + if (L->getHeader() == SplitCondBlock + && (Latch == Succ0 || Latch == Succ1)) + return false; + + // If split condition branches heads do not have single predecessor, + // SplitCondBlock, then is not possible to remove inactive branch. + 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 @@ -1073,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 @@ -1112,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); @@ -1187,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 @@ -1234,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