diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp | 1270 |
1 files changed, 0 insertions, 1270 deletions
diff --git a/contrib/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp b/contrib/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp deleted file mode 100644 index a433674..0000000 --- a/contrib/llvm/lib/Transforms/Scalar/LoopIndexSplit.cpp +++ /dev/null @@ -1,1270 +0,0 @@ -//===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements Loop Index Splitting Pass. This pass handles three -// kinds of loops. -// -// [1] A loop may be eliminated if the body is executed exactly once. -// For example, -// -// for (i = 0; i < N; ++i) { -// if (i == X) { -// body; -// } -// } -// -// is transformed to -// -// i = X; -// body; -// -// [2] A loop's iteration space may be shrunk if the loop body is executed -// for a proper sub-range of the loop's iteration space. For example, -// -// for (i = 0; i < N; ++i) { -// if (i > A && i < B) { -// ... -// } -// } -// -// is transformed to iterators from A to B, if A > 0 and B < N. -// -// [3] A loop may be split if the loop body is dominated by a branch. -// For example, -// -// for (i = LB; i < UB; ++i) { if (i < SV) A; else B; } -// -// is transformed into -// -// AEV = BSV = SV -// for (i = LB; i < min(UB, AEV); ++i) -// A; -// for (i = max(LB, BSV); i < UB; ++i); -// B; -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "loop-index-split" -#include "llvm/Transforms/Scalar.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/LLVMContext.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/Statistic.h" - -using namespace llvm; - -STATISTIC(NumIndexSplit, "Number of loop index split"); -STATISTIC(NumIndexSplitRemoved, "Number of loops eliminated by loop index split"); -STATISTIC(NumRestrictBounds, "Number of loop iteration space restricted"); - -namespace { - - class LoopIndexSplit : public LoopPass { - public: - static char ID; // Pass ID, replacement for typeid - LoopIndexSplit() : LoopPass(ID) {} - - // Index split Loop L. Return true if loop is split. - bool runOnLoop(Loop *L, LPPassManager &LPM); - - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addPreserved<ScalarEvolution>(); - AU.addRequiredID(LCSSAID); - AU.addPreservedID(LCSSAID); - AU.addRequired<LoopInfo>(); - AU.addPreserved<LoopInfo>(); - AU.addRequiredID(LoopSimplifyID); - AU.addPreservedID(LoopSimplifyID); - AU.addRequired<DominatorTree>(); - AU.addRequired<DominanceFrontier>(); - AU.addPreserved<DominatorTree>(); - AU.addPreserved<DominanceFrontier>(); - } - - private: - /// processOneIterationLoop -- Eliminate loop if loop body is executed - /// only once. For example, - /// for (i = 0; i < N; ++i) { - /// if ( i == X) { - /// ... - /// } - /// } - /// - bool processOneIterationLoop(); - - // -- Routines used by updateLoopIterationSpace(); - - /// updateLoopIterationSpace -- Update loop's iteration space if loop - /// body is executed for certain IV range only. For example, - /// - /// for (i = 0; i < N; ++i) { - /// if ( i > A && i < B) { - /// ... - /// } - /// } - /// is transformed to iterators from A to B, if A > 0 and B < N. - /// - bool updateLoopIterationSpace(); - - /// restrictLoopBound - Op dominates loop body. Op compares an IV based value - /// with a loop invariant value. Update loop's lower and upper bound based on - /// the loop invariant value. - bool restrictLoopBound(ICmpInst &Op); - - // --- Routines used by splitLoop(). --- / - - bool splitLoop(); - - /// 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. - void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB); - - /// moveExitCondition - Move exit condition EC into split condition block. - void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, - BasicBlock *ExitBB, ICmpInst *EC, ICmpInst *SC, - PHINode *IV, Instruction *IVAdd, Loop *LP, - unsigned); - - /// updatePHINodes - CFG has been changed. - /// Before - /// - 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 - /// - /// Update ExitBB PHINodes' to reflect this change. - void updatePHINodes(BasicBlock *ExitBB, BasicBlock *Latch, - BasicBlock *Header, - PHINode *IV, Instruction *IVIncrement, Loop *LP); - - // --- Utility routines --- / - - /// cleanBlock - A block is considered clean if all non terminal - /// instructions are either PHINodes or IV based values. - bool cleanBlock(BasicBlock *BB); - - /// IVisLT - If Op is comparing IV based value with an loop invariant and - /// IV based value is less than the loop invariant then return the loop - /// invariant. Otherwise return NULL. - Value * IVisLT(ICmpInst &Op); - - /// IVisLE - If Op is comparing IV based value with an loop invariant and - /// IV based value is less than or equal to the loop invariant then - /// return the loop invariant. Otherwise return NULL. - Value * IVisLE(ICmpInst &Op); - - /// IVisGT - If Op is comparing IV based value with an loop invariant and - /// IV based value is greater than the loop invariant then return the loop - /// invariant. Otherwise return NULL. - Value * IVisGT(ICmpInst &Op); - - /// IVisGE - If Op is comparing IV based value with an loop invariant and - /// IV based value is greater than or equal to the loop invariant then - /// return the loop invariant. Otherwise return NULL. - Value * IVisGE(ICmpInst &Op); - - private: - - // Current Loop information. - Loop *L; - LPPassManager *LPM; - LoopInfo *LI; - DominatorTree *DT; - DominanceFrontier *DF; - - PHINode *IndVar; - ICmpInst *ExitCondition; - ICmpInst *SplitCondition; - Value *IVStartValue; - Value *IVExitValue; - Instruction *IVIncrement; - SmallPtrSet<Value *, 4> IVBasedValues; - }; -} - -char LoopIndexSplit::ID = 0; -INITIALIZE_PASS(LoopIndexSplit, "loop-index-split", - "Index Split Loops", false, false); - -Pass *llvm::createLoopIndexSplitPass() { - return new LoopIndexSplit(); -} - -// Index split Loop L. Return true if loop is split. -bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { - L = IncomingLoop; - LPM = &LPM_Ref; - - // If LoopSimplify form is not available, stay out of trouble. - if (!L->isLoopSimplifyForm()) - return false; - - // FIXME - Nested loops make dominator info updates tricky. - if (!L->getSubLoops().empty()) - return false; - - DT = &getAnalysis<DominatorTree>(); - LI = &getAnalysis<LoopInfo>(); - DF = &getAnalysis<DominanceFrontier>(); - - // Initialize loop data. - IndVar = L->getCanonicalInductionVariable(); - if (!IndVar) return false; - - bool P1InLoop = L->contains(IndVar->getIncomingBlock(1)); - IVStartValue = IndVar->getIncomingValue(!P1InLoop); - IVIncrement = dyn_cast<Instruction>(IndVar->getIncomingValue(P1InLoop)); - if (!IVIncrement) return false; - - IVBasedValues.clear(); - IVBasedValues.insert(IndVar); - IVBasedValues.insert(IVIncrement); - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) - for(BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end(); - BI != BE; ++BI) { - if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BI)) - if (BO != IVIncrement - && (BO->getOpcode() == Instruction::Add - || BO->getOpcode() == Instruction::Sub)) - if (IVBasedValues.count(BO->getOperand(0)) - && L->isLoopInvariant(BO->getOperand(1))) - IVBasedValues.insert(BO); - } - - // Reject loop if loop exit condition is not suitable. - BasicBlock *ExitingBlock = L->getExitingBlock(); - if (!ExitingBlock) - return false; - BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); - if (!EBR) return false; - ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition()); - if (!ExitCondition) return false; - if (ExitingBlock != L->getLoopLatch()) return false; - IVExitValue = ExitCondition->getOperand(1); - if (!L->isLoopInvariant(IVExitValue)) - IVExitValue = ExitCondition->getOperand(0); - if (!L->isLoopInvariant(IVExitValue)) - return false; - if (!IVBasedValues.count( - ExitCondition->getOperand(IVExitValue == ExitCondition->getOperand(0)))) - return false; - - // If start value is more then exit value where induction variable - // increments by 1 then we are potentially dealing with an infinite loop. - // Do not index split this loop. - if (ConstantInt *SV = dyn_cast<ConstantInt>(IVStartValue)) - if (ConstantInt *EV = dyn_cast<ConstantInt>(IVExitValue)) - if (SV->getSExtValue() > EV->getSExtValue()) - return false; - - if (processOneIterationLoop()) - return true; - - if (updateLoopIterationSpace()) - return true; - - if (splitLoop()) - return true; - - return false; -} - -// --- Helper routines --- -// isUsedOutsideLoop - Returns true iff V is used outside the loop L. -static bool isUsedOutsideLoop(Value *V, Loop *L) { - for(Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (!L->contains(cast<Instruction>(*UI))) - return true; - return false; -} - -// Return V+1 -static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt, - LLVMContext &Context) { - Constant *One = ConstantInt::get(V->getType(), 1, Sign); - return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt); -} - -// Return V-1 -static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt, - LLVMContext &Context) { - Constant *One = ConstantInt::get(V->getType(), 1, Sign); - return BinaryOperator::CreateSub(V, One, "lsp", InsertPt); -} - -// Return min(V1, V1) -static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) { - - Value *C = new ICmpInst(InsertPt, - Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - V1, V2, "lsp"); - return SelectInst::Create(C, V1, V2, "lsp", InsertPt); -} - -// Return max(V1, V2) -static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) { - - Value *C = new ICmpInst(InsertPt, - Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, - V1, V2, "lsp"); - return SelectInst::Create(C, V2, V1, "lsp", InsertPt); -} - -/// processOneIterationLoop -- Eliminate loop if loop body is executed -/// only once. For example, -/// for (i = 0; i < N; ++i) { -/// if ( i == X) { -/// ... -/// } -/// } -/// -bool LoopIndexSplit::processOneIterationLoop() { - SplitCondition = NULL; - BasicBlock *Latch = L->getLoopLatch(); - BasicBlock *Header = L->getHeader(); - BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator()); - if (!BR) return false; - if (!isa<BranchInst>(Latch->getTerminator())) return false; - if (BR->isUnconditional()) return false; - SplitCondition = dyn_cast<ICmpInst>(BR->getCondition()); - if (!SplitCondition) return false; - if (SplitCondition == ExitCondition) return false; - if (SplitCondition->getPredicate() != ICmpInst::ICMP_EQ) return false; - if (BR->getOperand(1) != Latch) return false; - if (!IVBasedValues.count(SplitCondition->getOperand(0)) - && !IVBasedValues.count(SplitCondition->getOperand(1))) - return false; - - // If IV is used outside the loop then this loop traversal is required. - // FIXME: Calculate and use last IV value. - if (isUsedOutsideLoop(IVIncrement, L)) - return false; - - // If BR operands are not IV or not loop invariants then skip this loop. - Value *OPV = SplitCondition->getOperand(0); - Value *SplitValue = SplitCondition->getOperand(1); - if (!L->isLoopInvariant(SplitValue)) - std::swap(OPV, SplitValue); - if (!L->isLoopInvariant(SplitValue)) - return false; - Instruction *OPI = dyn_cast<Instruction>(OPV); - if (!OPI) - return false; - if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L)) - return false; - Value *StartValue = IVStartValue; - Value *ExitValue = IVExitValue;; - - if (OPV != IndVar) { - // If BR operand is IV based then use this operand to calculate - // effective conditions for loop body. - BinaryOperator *BOPV = dyn_cast<BinaryOperator>(OPV); - if (!BOPV) - return false; - if (BOPV->getOpcode() != Instruction::Add) - return false; - StartValue = BinaryOperator::CreateAdd(OPV, StartValue, "" , BR); - ExitValue = BinaryOperator::CreateAdd(OPV, ExitValue, "" , BR); - } - - if (!cleanBlock(Header)) - return false; - - if (!cleanBlock(Latch)) - return false; - - // If the merge point for BR is not loop latch then skip this loop. - if (BR->getSuccessor(0) != Latch) { - DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); - assert (DF0 != DF->end() && "Unable to find dominance frontier"); - if (!DF0->second.count(Latch)) - return false; - } - - if (BR->getSuccessor(1) != Latch) { - DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); - assert (DF1 != DF->end() && "Unable to find dominance frontier"); - if (!DF1->second.count(Latch)) - return false; - } - - // Now, Current loop L contains compare instruction - // that compares induction variable, IndVar, against loop invariant. And - // entire (i.e. meaningful) loop body is dominated by this compare - // instruction. In such case eliminate - // loop structure surrounding this loop body. For example, - // for (int i = start; i < end; ++i) { - // if ( i == somevalue) { - // loop_body - // } - // } - // can be transformed into - // if (somevalue >= start && somevalue < end) { - // i = somevalue; - // loop_body - // } - - // Replace index variable with split value in loop body. Loop body is executed - // only when index variable is equal to split value. - IndVar->replaceAllUsesWith(SplitValue); - - // Replace split condition in header. - // Transform - // SplitCondition : icmp eq i32 IndVar, SplitValue - // into - // c1 = icmp uge i32 SplitValue, StartValue - // c2 = icmp ult i32 SplitValue, ExitValue - // and i32 c1, c2 - Instruction *C1 = new ICmpInst(BR, ExitCondition->isSigned() ? - ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, - SplitValue, StartValue, "lisplit"); - - CmpInst::Predicate C2P = ExitCondition->getPredicate(); - BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator()); - if (LatchBR->getOperand(1) != Header) - C2P = CmpInst::getInversePredicate(C2P); - Instruction *C2 = new ICmpInst(BR, C2P, SplitValue, ExitValue, "lisplit"); - Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR); - - SplitCondition->replaceAllUsesWith(NSplitCond); - SplitCondition->eraseFromParent(); - - // Remove Latch to Header edge. - BasicBlock *LatchSucc = NULL; - Header->removePredecessor(Latch); - for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch); - SI != E; ++SI) { - if (Header != *SI) - LatchSucc = *SI; - } - - // Clean up latch block. - Value *LatchBRCond = LatchBR->getCondition(); - LatchBR->setUnconditionalDest(LatchSucc); - RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond); - - LPM->deleteLoopFromQueue(L); - - // Update Dominator Info. - // Only CFG change done is to remove Latch to Header edge. This - // does not change dominator tree because Latch did not dominate - // Header. - if (DF) { - DominanceFrontier::iterator HeaderDF = DF->find(Header); - if (HeaderDF != DF->end()) - DF->removeFromFrontier(HeaderDF, Header); - - DominanceFrontier::iterator LatchDF = DF->find(Latch); - if (LatchDF != DF->end()) - DF->removeFromFrontier(LatchDF, Header); - } - - ++NumIndexSplitRemoved; - return true; -} - -/// restrictLoopBound - Op dominates loop body. Op compares an IV based value -/// with a loop invariant value. Update loop's lower and upper bound based on -/// the loop invariant value. -bool LoopIndexSplit::restrictLoopBound(ICmpInst &Op) { - bool Sign = Op.isSigned(); - Instruction *PHTerm = L->getLoopPreheader()->getTerminator(); - - if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) { - BranchInst *EBR = - cast<BranchInst>(ExitCondition->getParent()->getTerminator()); - ExitCondition->setPredicate(ExitCondition->getInversePredicate()); - BasicBlock *T = EBR->getSuccessor(0); - EBR->setSuccessor(0, EBR->getSuccessor(1)); - EBR->setSuccessor(1, T); - } - - LLVMContext &Context = Op.getContext(); - - // New upper and lower bounds. - Value *NLB = NULL; - Value *NUB = NULL; - if (Value *V = IVisLT(Op)) { - // Restrict upper bound. - if (IVisLE(*ExitCondition)) - V = getMinusOne(V, Sign, PHTerm, Context); - NUB = getMin(V, IVExitValue, Sign, PHTerm); - } else if (Value *V = IVisLE(Op)) { - // Restrict upper bound. - if (IVisLT(*ExitCondition)) - V = getPlusOne(V, Sign, PHTerm, Context); - NUB = getMin(V, IVExitValue, Sign, PHTerm); - } else if (Value *V = IVisGT(Op)) { - // Restrict lower bound. - V = getPlusOne(V, Sign, PHTerm, Context); - NLB = getMax(V, IVStartValue, Sign, PHTerm); - } else if (Value *V = IVisGE(Op)) - // Restrict lower bound. - NLB = getMax(V, IVStartValue, Sign, PHTerm); - - if (!NLB && !NUB) - return false; - - if (NLB) { - unsigned i = IndVar->getBasicBlockIndex(L->getLoopPreheader()); - IndVar->setIncomingValue(i, NLB); - } - - if (NUB) { - unsigned i = (ExitCondition->getOperand(0) != IVExitValue); - ExitCondition->setOperand(i, NUB); - } - return true; -} - -/// updateLoopIterationSpace -- Update loop's iteration space if loop -/// body is executed for certain IV range only. For example, -/// -/// for (i = 0; i < N; ++i) { -/// if ( i > A && i < B) { -/// ... -/// } -/// } -/// is transformed to iterators from A to B, if A > 0 and B < N. -/// -bool LoopIndexSplit::updateLoopIterationSpace() { - SplitCondition = NULL; - if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE - || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ) - return false; - BasicBlock *Latch = L->getLoopLatch(); - BasicBlock *Header = L->getHeader(); - BranchInst *BR = dyn_cast<BranchInst>(Header->getTerminator()); - if (!BR) return false; - if (!isa<BranchInst>(Latch->getTerminator())) return false; - if (BR->isUnconditional()) return false; - BinaryOperator *AND = dyn_cast<BinaryOperator>(BR->getCondition()); - if (!AND) return false; - if (AND->getOpcode() != Instruction::And) return false; - ICmpInst *Op0 = dyn_cast<ICmpInst>(AND->getOperand(0)); - ICmpInst *Op1 = dyn_cast<ICmpInst>(AND->getOperand(1)); - if (!Op0 || !Op1) - return false; - IVBasedValues.insert(AND); - IVBasedValues.insert(Op0); - IVBasedValues.insert(Op1); - if (!cleanBlock(Header)) return false; - BasicBlock *ExitingBlock = ExitCondition->getParent(); - if (!cleanBlock(ExitingBlock)) return false; - - // If the merge point for BR is not loop latch then skip this loop. - if (BR->getSuccessor(0) != Latch) { - DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); - assert (DF0 != DF->end() && "Unable to find dominance frontier"); - if (!DF0->second.count(Latch)) - return false; - } - - if (BR->getSuccessor(1) != Latch) { - DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); - assert (DF1 != DF->end() && "Unable to find dominance frontier"); - if (!DF1->second.count(Latch)) - return false; - } - - // Verify that loop exiting block has only two predecessor, where one pred - // 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 (Header == BB) - continue; - if (ExitingBBPred) - return false; - else - ExitingBBPred = BB; - } - - if (!restrictLoopBound(*Op0)) - return false; - - if (!restrictLoopBound(*Op1)) - return false; - - // Update CFG. - if (BR->getSuccessor(0) == ExitingBlock) - BR->setUnconditionalDest(BR->getSuccessor(1)); - else - BR->setUnconditionalDest(BR->getSuccessor(0)); - - AND->eraseFromParent(); - if (Op0->use_empty()) - Op0->eraseFromParent(); - if (Op1->use_empty()) - Op1->eraseFromParent(); - - // Update domiantor info. Now, ExitingBlock has only one predecessor, - // ExitingBBPred, and it is ExitingBlock's immediate domiantor. - DT->changeImmediateDominator(ExitingBlock, ExitingBBPred); - - BasicBlock *ExitBlock = ExitingBlock->getTerminator()->getSuccessor(1); - if (L->contains(ExitBlock)) - ExitBlock = ExitingBlock->getTerminator()->getSuccessor(0); - - // If ExitingBlock is a member of the loop basic blocks' DF list then - // replace ExitingBlock with header and exit block in the DF list - DominanceFrontier::iterator ExitingBlockDF = DF->find(ExitingBlock); - 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); - for (DominanceFrontier::DomSetType::iterator - EBI = ExitingBlockDF->second.begin(), - EBE = ExitingBlockDF->second.end(); EBI != EBE; ++EBI) - BBDF->second.insert(*EBI); - } - } - } - ++NumRestrictBounds; - 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. -void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, - BasicBlock *LiveBB) { - - // First update DeadBB's dominance frontier. - SmallVector<BasicBlock *, 8> FrontierBBs; - DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB); - if (DeadBBDF != DF->end()) { - SmallVector<BasicBlock *, 8> PredBlocks; - - DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second; - for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(), - DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) - { - BasicBlock *FrontierBB = *DeadBBSetI; - FrontierBBs.push_back(FrontierBB); - - // Rremove any PHI incoming edge from blocks dominated by DeadBB. - PredBlocks.clear(); - for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB); - PI != PE; ++PI) { - BasicBlock *P = *PI; - if (DT->dominates(DeadBB, P)) - PredBlocks.push_back(P); - } - - for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end(); - FBI != FBE; ++FBI) { - if (PHINode *PN = dyn_cast<PHINode>(FBI)) { - for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(), - PE = PredBlocks.end(); PI != PE; ++PI) { - BasicBlock *P = *PI; - PN->removeIncomingValue(P); - } - } - else - break; - } - } - } - - // Now remove DeadBB and all nodes dominated by DeadBB in df order. - SmallVector<BasicBlock *, 32> WorkList; - DomTreeNode *DN = DT->getNode(DeadBB); - for (df_iterator<DomTreeNode*> DI = df_begin(DN), - E = df_end(DN); DI != E; ++DI) { - BasicBlock *BB = DI->getBlock(); - WorkList.push_back(BB); - BB->replaceAllUsesWith(UndefValue::get( - Type::getLabelTy(DeadBB->getContext()))); - } - - while (!WorkList.empty()) { - BasicBlock *BB = WorkList.pop_back_val(); - LPM->deleteSimpleAnalysisValue(BB, LP); - for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); - BBI != BBE; ) { - Instruction *I = BBI; - ++BBI; - I->replaceAllUsesWith(UndefValue::get(I->getType())); - LPM->deleteSimpleAnalysisValue(I, LP); - I->eraseFromParent(); - } - DT->eraseNode(BB); - DF->removeBlock(BB); - LI->removeBlock(BB); - BB->eraseFromParent(); - } - - // Update Frontier BBs' dominator info. - while (!FrontierBBs.empty()) { - BasicBlock *FBB = FrontierBBs.pop_back_val(); - BasicBlock *NewDominator = FBB->getSinglePredecessor(); - if (!NewDominator) { - pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB); - NewDominator = *PI; - ++PI; - if (NewDominator != LiveBB) { - for(; PI != PE; ++PI) { - BasicBlock *P = *PI; - if (P == LiveBB) { - NewDominator = LiveBB; - break; - } - NewDominator = DT->findNearestCommonDominator(NewDominator, P); - } - } - } - assert (NewDominator && "Unable to fix dominator info."); - DT->changeImmediateDominator(FBB, NewDominator); - DF->changeImmediateDominator(FBB, NewDominator, DT); - } - -} - -// moveExitCondition - Move exit condition EC into split condition block CondBB. -void LoopIndexSplit::moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB, - BasicBlock *ExitBB, ICmpInst *EC, - ICmpInst *SC, PHINode *IV, - Instruction *IVAdd, Loop *LP, - unsigned ExitValueNum) { - - BasicBlock *ExitingBB = EC->getParent(); - Instruction *CurrentBR = CondBB->getTerminator(); - - // Move exit condition into split condition block. - EC->moveBefore(CurrentBR); - EC->setOperand(ExitValueNum == 0 ? 1 : 0, IV); - - // Move exiting block's branch into split condition block. Update its branch - // destination. - BranchInst *ExitingBR = cast<BranchInst>(ExitingBB->getTerminator()); - ExitingBR->moveBefore(CurrentBR); - BasicBlock *OrigDestBB = NULL; - if (ExitingBR->getSuccessor(0) == ExitBB) { - OrigDestBB = ExitingBR->getSuccessor(1); - ExitingBR->setSuccessor(1, ActiveBB); - } - 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 original destination. - BranchInst::Create(OrigDestBB, ExitingBB); - - // Update PHINodes - updatePHINodes(ExitBB, ExitingBB, CondBB, IV, IVAdd, LP); - - // Fix dominator info. - // ExitBB is now dominated by CondBB - DT->changeImmediateDominator(ExitBB, CondBB); - DF->changeImmediateDominator(ExitBB, CondBB, DT); - - // Blocks outside the loop may have been in the dominance frontier of blocks - // inside the condition; this is now impossible because the blocks inside the - // condition no loger dominate the exit. Remove the relevant blocks from - // the dominance frontiers. - for (Loop::block_iterator I = LP->block_begin(), E = LP->block_end(); - I != E; ++I) { - if (!DT->properlyDominates(CondBB, *I)) continue; - DominanceFrontier::iterator BBDF = DF->find(*I); - 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 (!LP->contains(DFBB)) - BBDF->second.erase(DFBB); - } - } -} - -/// updatePHINodes - CFG has been changed. -/// Before -/// - ExitBB's single predecessor was Latch -/// - Latch's second successor was Header -/// Now -/// - 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, - Loop *LP) { - - for (BasicBlock::iterator BI = ExitBB->begin(), BE = ExitBB->end(); - BI != BE; ) { - PHINode *PN = dyn_cast<PHINode>(BI); - ++BI; - if (!PN) - break; - - Value *V = PN->getIncomingValueForBlock(Latch); - if (PHINode *PHV = dyn_cast<PHINode>(V)) { - // 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 (PHINode *U = dyn_cast<PHINode>(*UI)) - if (LP->contains(U)) { - 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<Instruction>(V)) { - // If this instruction is IVIncrement then IV is new incoming value - // from header otherwise this instruction must be incoming value from - // header because loop is in LCSSA form. - if (PHI == IVIncrement) - PN->addIncoming(IV, Header); - else - PN->addIncoming(V, Header); - } else - // Otherwise this is an incoming value from header because loop is in - // LCSSA form. - PN->addIncoming(V, Header); - - // Remove incoming value from Latch. - PN->removeIncomingValue(Latch); - } -} - -bool LoopIndexSplit::splitLoop() { - SplitCondition = NULL; - if (ExitCondition->getPredicate() == ICmpInst::ICMP_NE - || ExitCondition->getPredicate() == ICmpInst::ICMP_EQ) - return false; - BasicBlock *Header = L->getHeader(); - BasicBlock *Latch = L->getLoopLatch(); - BranchInst *SBR = NULL; // Split Condition Branch - BranchInst *EBR = cast<BranchInst>(ExitCondition->getParent()->getTerminator()); - // If Exiting block includes loop variant instructions then this - // loop may not be split safely. - BasicBlock *ExitingBlock = ExitCondition->getParent(); - if (!cleanBlock(ExitingBlock)) return false; - - LLVMContext &Context = Header->getContext(); - - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) { - BranchInst *BR = dyn_cast<BranchInst>((*I)->getTerminator()); - if (!BR || BR->isUnconditional()) continue; - ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition()); - if (!CI || CI == ExitCondition - || CI->getPredicate() == ICmpInst::ICMP_NE - || CI->getPredicate() == ICmpInst::ICMP_EQ) - continue; - - // Unable to handle triangle 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(). - if (Header == (*I) - && (Latch == BR->getSuccessor(0) || Latch == BR->getSuccessor(1))) - continue; - - // If the block does not dominate the latch then this is not a diamond. - // Such loop may not benefit from index split. - if (!DT->dominates((*I), Latch)) - continue; - - // If split condition branches heads do not have single predecessor, - // SplitCondBlock, then is not possible to remove inactive branch. - if (!BR->getSuccessor(0)->getSinglePredecessor() - || !BR->getSuccessor(1)->getSinglePredecessor()) - return false; - - // If the merge point for BR is not loop latch then skip this condition. - if (BR->getSuccessor(0) != Latch) { - DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0)); - assert (DF0 != DF->end() && "Unable to find dominance frontier"); - if (!DF0->second.count(Latch)) - continue; - } - - if (BR->getSuccessor(1) != Latch) { - DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1)); - assert (DF1 != DF->end() && "Unable to find dominance frontier"); - if (!DF1->second.count(Latch)) - continue; - } - SplitCondition = CI; - SBR = BR; - break; - } - - if (!SplitCondition) - return false; - - // If the predicate sign does not match then skip. - if (ExitCondition->isSigned() != SplitCondition->isSigned()) - return false; - - unsigned EVOpNum = (ExitCondition->getOperand(1) == IVExitValue); - unsigned SVOpNum = IVBasedValues.count(SplitCondition->getOperand(0)); - Value *SplitValue = SplitCondition->getOperand(SVOpNum); - if (!L->isLoopInvariant(SplitValue)) - return false; - if (!IVBasedValues.count(SplitCondition->getOperand(!SVOpNum))) - return false; - - // Check for side effects. - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) { - BasicBlock *BB = *I; - - assert(DT->dominates(Header, BB)); - if (DT->properlyDominates(SplitCondition->getParent(), BB)) - continue; - - for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); - BI != BE; ++BI) { - Instruction *Inst = BI; - - if (!Inst->isSafeToSpeculativelyExecute() && !isa<PHINode>(Inst) - && !isa<BranchInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst)) - return false; - } - } - - // Normalize loop conditions so that it is easier to calculate new loop - // bounds. - if (IVisGT(*ExitCondition) || IVisGE(*ExitCondition)) { - ExitCondition->setPredicate(ExitCondition->getInversePredicate()); - BasicBlock *T = EBR->getSuccessor(0); - EBR->setSuccessor(0, EBR->getSuccessor(1)); - EBR->setSuccessor(1, T); - } - - if (IVisGT(*SplitCondition) || IVisGE(*SplitCondition)) { - SplitCondition->setPredicate(SplitCondition->getInversePredicate()); - BasicBlock *T = SBR->getSuccessor(0); - SBR->setSuccessor(0, SBR->getSuccessor(1)); - SBR->setSuccessor(1, T); - } - - //[*] Calculate new loop bounds. - Value *AEV = SplitValue; - Value *BSV = SplitValue; - bool Sign = SplitCondition->isSigned(); - Instruction *PHTerm = L->getLoopPreheader()->getTerminator(); - - if (IVisLT(*ExitCondition)) { - if (IVisLT(*SplitCondition)) { - /* Do nothing */ - } - else if (IVisLE(*SplitCondition)) { - AEV = getPlusOne(SplitValue, Sign, PHTerm, Context); - BSV = getPlusOne(SplitValue, Sign, PHTerm, Context); - } else { - assert (0 && "Unexpected split condition!"); - } - } - else if (IVisLE(*ExitCondition)) { - if (IVisLT(*SplitCondition)) { - AEV = getMinusOne(SplitValue, Sign, PHTerm, Context); - } - else if (IVisLE(*SplitCondition)) { - BSV = getPlusOne(SplitValue, Sign, PHTerm, Context); - } else { - assert (0 && "Unexpected split condition!"); - } - } else { - assert (0 && "Unexpected exit condition!"); - } - AEV = getMin(AEV, IVExitValue, Sign, PHTerm); - BSV = getMax(BSV, IVStartValue, Sign, PHTerm); - - // [*] Clone Loop - ValueMap<const Value *, Value *> VMap; - Loop *BLoop = CloneLoop(L, LPM, LI, VMap, this); - Loop *ALoop = L; - - // [*] ALoop's exiting edge enters BLoop's header. - // ALoop's original exit block becomes BLoop's exit block. - PHINode *B_IndVar = cast<PHINode>(VMap[IndVar]); - BasicBlock *A_ExitingBlock = ExitCondition->getParent(); - BranchInst *A_ExitInsn = - dyn_cast<BranchInst>(A_ExitingBlock->getTerminator()); - assert (A_ExitInsn && "Unable to find suitable loop exit branch"); - BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1); - BasicBlock *B_Header = BLoop->getHeader(); - if (ALoop->contains(B_ExitBlock)) { - B_ExitBlock = A_ExitInsn->getSuccessor(0); - A_ExitInsn->setSuccessor(0, B_Header); - } else - A_ExitInsn->setSuccessor(1, B_Header); - - // [*] Update ALoop's exit value using new exit value. - ExitCondition->setOperand(EVOpNum, AEV); - - // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from - // original loop's preheader. Add incoming PHINode values from - // ALoop's exiting block. Update BLoop header's domiantor info. - - // Collect inverse map of Header PHINodes. - DenseMap<Value *, Value *> InverseMap; - for (BasicBlock::iterator BI = ALoop->getHeader()->begin(), - BE = ALoop->getHeader()->end(); BI != BE; ++BI) { - if (PHINode *PN = dyn_cast<PHINode>(BI)) { - PHINode *PNClone = cast<PHINode>(VMap[PN]); - InverseMap[PNClone] = PN; - } else - break; - } - - BasicBlock *A_Preheader = ALoop->getLoopPreheader(); - for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); - BI != BE; ++BI) { - if (PHINode *PN = dyn_cast<PHINode>(BI)) { - // Remove incoming value from original preheader. - PN->removeIncomingValue(A_Preheader); - - // Add incoming value from A_ExitingBlock. - if (PN == B_IndVar) - PN->addIncoming(BSV, A_ExitingBlock); - else { - PHINode *OrigPN = cast<PHINode>(InverseMap[PN]); - Value *V2 = NULL; - // If loop header is also loop exiting block then - // OrigPN is incoming value for B loop header. - if (A_ExitingBlock == ALoop->getHeader()) - V2 = OrigPN; - else - V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock); - PN->addIncoming(V2, A_ExitingBlock); - } - } else - break; - } - - DT->changeImmediateDominator(B_Header, A_ExitingBlock); - DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT); - - // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit - // block. Remove incoming PHINode values from ALoop's exiting block. - // Add new incoming values from BLoop's incoming exiting value. - // Update BLoop exit block's dominator info.. - BasicBlock *B_ExitingBlock = cast<BasicBlock>(VMap[A_ExitingBlock]); - for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end(); - BI != BE; ++BI) { - if (PHINode *PN = dyn_cast<PHINode>(BI)) { - PN->addIncoming(VMap[PN->getIncomingValueForBlock(A_ExitingBlock)], - B_ExitingBlock); - PN->removeIncomingValue(A_ExitingBlock); - } else - break; - } - - DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock); - DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT); - - //[*] Split ALoop's exit edge. This creates a new block which - // serves two purposes. First one is to hold PHINode defnitions - // to ensure that ALoop's LCSSA form. Second use it to act - // as a preheader for BLoop. - BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this); - - //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes - // in A_ExitBlock to redefine outgoing PHI definitions from ALoop. - for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); - BI != BE; ++BI) { - if (PHINode *PN = dyn_cast<PHINode>(BI)) { - Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock); - PHINode *newPHI = PHINode::Create(PN->getType(), PN->getName()); - newPHI->addIncoming(V1, A_ExitingBlock); - A_ExitBlock->getInstList().push_front(newPHI); - PN->removeIncomingValue(A_ExitBlock); - PN->addIncoming(newPHI, A_ExitBlock); - } else - break; - } - - //[*] Eliminate split condition's inactive branch from ALoop. - BasicBlock *A_SplitCondBlock = SplitCondition->getParent(); - BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator()); - BasicBlock *A_InactiveBranch = NULL; - BasicBlock *A_ActiveBranch = NULL; - A_ActiveBranch = A_BR->getSuccessor(0); - A_InactiveBranch = A_BR->getSuccessor(1); - A_BR->setUnconditionalDest(A_ActiveBranch); - removeBlocks(A_InactiveBranch, L, A_ActiveBranch); - - //[*] Eliminate split condition's inactive branch in from BLoop. - BasicBlock *B_SplitCondBlock = cast<BasicBlock>(VMap[A_SplitCondBlock]); - BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator()); - BasicBlock *B_InactiveBranch = NULL; - BasicBlock *B_ActiveBranch = NULL; - B_ActiveBranch = B_BR->getSuccessor(1); - B_InactiveBranch = B_BR->getSuccessor(0); - B_BR->setUnconditionalDest(B_ActiveBranch); - removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch); - - BasicBlock *A_Header = ALoop->getHeader(); - if (A_ExitingBlock == A_Header) - return true; - - //[*] Move exit condition into split condition block to avoid - // executing dead loop iteration. - ICmpInst *B_ExitCondition = cast<ICmpInst>(VMap[ExitCondition]); - Instruction *B_IndVarIncrement = cast<Instruction>(VMap[IVIncrement]); - ICmpInst *B_SplitCondition = cast<ICmpInst>(VMap[SplitCondition]); - - moveExitCondition(A_SplitCondBlock, A_ActiveBranch, A_ExitBlock, ExitCondition, - cast<ICmpInst>(SplitCondition), IndVar, IVIncrement, - ALoop, EVOpNum); - - moveExitCondition(B_SplitCondBlock, B_ActiveBranch, - B_ExitBlock, B_ExitCondition, - B_SplitCondition, B_IndVar, B_IndVarIncrement, - BLoop, EVOpNum); - - ++NumIndexSplit; - return true; -} - -/// cleanBlock - A block is considered clean if all non terminal instructions -/// are either, PHINodes, IV based. -bool LoopIndexSplit::cleanBlock(BasicBlock *BB) { - Instruction *Terminator = BB->getTerminator(); - for(BasicBlock::iterator BI = BB->begin(), BE = BB->end(); - BI != BE; ++BI) { - Instruction *I = BI; - - if (isa<PHINode>(I) || I == Terminator || I == ExitCondition - || I == SplitCondition || IVBasedValues.count(I) - || isa<DbgInfoIntrinsic>(I)) - continue; - - if (I->mayHaveSideEffects()) - return false; - - // I is used only inside this block then it is OK. - bool usedOutsideBB = false; - for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); - UI != UE; ++UI) { - Instruction *U = cast<Instruction>(*UI); - if (U->getParent() != BB) - usedOutsideBB = true; - } - if (!usedOutsideBB) - continue; - - // Otherwise we have a instruction that may not allow loop spliting. - return false; - } - return true; -} - -/// IVisLT - If Op is comparing IV based value with an loop invariant and -/// IV based value is less than the loop invariant then return the loop -/// invariant. Otherwise return NULL. -Value * LoopIndexSplit::IVisLT(ICmpInst &Op) { - ICmpInst::Predicate P = Op.getPredicate(); - if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) - && IVBasedValues.count(Op.getOperand(0)) - && L->isLoopInvariant(Op.getOperand(1))) - return Op.getOperand(1); - - if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) - && IVBasedValues.count(Op.getOperand(1)) - && L->isLoopInvariant(Op.getOperand(0))) - return Op.getOperand(0); - - return NULL; -} - -/// IVisLE - If Op is comparing IV based value with an loop invariant and -/// IV based value is less than or equal to the loop invariant then -/// return the loop invariant. Otherwise return NULL. -Value * LoopIndexSplit::IVisLE(ICmpInst &Op) { - ICmpInst::Predicate P = Op.getPredicate(); - if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE) - && IVBasedValues.count(Op.getOperand(0)) - && L->isLoopInvariant(Op.getOperand(1))) - return Op.getOperand(1); - - if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE) - && IVBasedValues.count(Op.getOperand(1)) - && L->isLoopInvariant(Op.getOperand(0))) - return Op.getOperand(0); - - return NULL; -} - -/// IVisGT - If Op is comparing IV based value with an loop invariant and -/// IV based value is greater than the loop invariant then return the loop -/// invariant. Otherwise return NULL. -Value * LoopIndexSplit::IVisGT(ICmpInst &Op) { - ICmpInst::Predicate P = Op.getPredicate(); - if ((P == ICmpInst::ICMP_SGT || P == ICmpInst::ICMP_UGT) - && IVBasedValues.count(Op.getOperand(0)) - && L->isLoopInvariant(Op.getOperand(1))) - return Op.getOperand(1); - - if ((P == ICmpInst::ICMP_SLT || P == ICmpInst::ICMP_ULT) - && IVBasedValues.count(Op.getOperand(1)) - && L->isLoopInvariant(Op.getOperand(0))) - return Op.getOperand(0); - - return NULL; -} - -/// IVisGE - If Op is comparing IV based value with an loop invariant and -/// IV based value is greater than or equal to the loop invariant then -/// return the loop invariant. Otherwise return NULL. -Value * LoopIndexSplit::IVisGE(ICmpInst &Op) { - ICmpInst::Predicate P = Op.getPredicate(); - if ((P == ICmpInst::ICMP_SGE || P == ICmpInst::ICMP_UGE) - && IVBasedValues.count(Op.getOperand(0)) - && L->isLoopInvariant(Op.getOperand(1))) - return Op.getOperand(1); - - if ((P == ICmpInst::ICMP_SLE || P == ICmpInst::ICMP_ULE) - && IVBasedValues.count(Op.getOperand(1)) - && L->isLoopInvariant(Op.getOperand(0))) - return Op.getOperand(0); - - return NULL; -} - |
