Rewrite code that 1) filters loops and 2) calculates new loop bounds.

This fixes many bugs. I will add more test cases in a separate check-in.

Some day, the code that manipulates CFG and updates dom. info could use refactoring help.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60554 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 715 insertions, 1269 deletions

diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index 8c54ce372e..a73b335526 100644
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -7,8 +7,36 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements Loop Index Splitting Pass.
+// This file implements Loop Index Splitting Pass. This pass handles three
+// kinds of loops.
 //
+// [1] Loop is eliminated when loop body is executed only once. For example,
+// for (i = 0; i < N; ++i) {
+//   if ( i == X) {
+//     ...
+//   }
+// }
+//
+// [2] Loop's iteration space is shrunk if loop body is executed for certain
+//     range only. For example,
+// 
+// for (i = 0; i < N; ++i) {
+//   if ( i > A && i < B) {
+//     ...
+//   }
+// }
+// is trnasformed to iterators from A to B, if A > 0 and B < N.
+//
+// [3] Loop is split if the loop body is dominated by an 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"
@@ -25,7 +53,9 @@
 
 using namespace llvm;
 
-STATISTIC(NumIndexSplit, "Number of loops index split");
+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 {
 
@@ -54,96 +84,50 @@ namespace {
     }
 
   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 trnasformed to iterators from A to B, if A > 0 and B < N.
+    ///
+    bool updateLoopIterationSpace();
 
-    class SplitInfo {
-    public:
-      SplitInfo() : SplitValue(NULL), SplitCondition(NULL), 
-                    UseTrueBranchFirst(true), A_ExitValue(NULL), 
-                    B_StartValue(NULL) {}
-
-      // Induction variable's range is split at this value.
-      Value *SplitValue;
-      
-      // This instruction compares IndVar against SplitValue.
-      Instruction *SplitCondition;
-
-      // True if after loop index split, first loop will execute split condition's
-      // true branch.
-      bool UseTrueBranchFirst;
-
-      // Exit value for first loop after loop split.
-      Value *A_ExitValue;
-
-      // Start value for second loop after loop split.
-      Value *B_StartValue;
-
-      // Clear split info.
-      void clear() {
-        SplitValue = NULL;
-        SplitCondition = NULL;
-        UseTrueBranchFirst = true;
-        A_ExitValue = NULL;
-        B_StartValue = NULL;
-      }
-
-    };
-    
-  private:
-
-    // safeIcmpInst - CI is considered safe instruction if one of the operand
-    // is SCEVAddRecExpr based on induction variable and other operand is
-    // loop invariant. If CI is safe then populate SplitInfo object SD appropriately
-    // and return true;
-    bool safeICmpInst(ICmpInst *CI, SplitInfo &SD);
-
-    /// Find condition inside a loop that is suitable candidate for index split.
-    void findSplitCondition();
+    /// 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);
 
-    /// Find loop's exit condition.
-    void findLoopConditionals();
+    // --- Routines used by splitLoop(). --- /
 
-    /// Return induction variable associated with value V.
-    void findIndVar(Value *V, Loop *L);
+    bool splitLoop();
 
-    /// processOneIterationLoop - Current loop L contains compare instruction
-    /// that compares induction variable, IndVar, agains loop invariant. If
-    /// entire (i.e. meaningful) loop body is dominated by this compare
-    /// 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);
-    
-    /// isOneIterationLoop - Return true if split condition is EQ and 
-    /// the IV is not used outside the loop.
-    bool isOneIterationLoop(ICmpInst *CI);
-
-    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);
-
-    /// If Exiting block includes loop variant instructions then this
-    /// loop may not be eliminated.
-    bool safeExitingBlock(SplitInfo &SD, BasicBlock *BB);
-
-    /// 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.
+    /// 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);
-
-    /// safeSplitCondition - Return true if it is possible to
-    /// split loop using given split condition.
-    bool safeSplitCondition(SplitInfo &SD);
-
-    /// calculateLoopBounds - ALoop exit value and BLoop start values are calculated
-    /// based on split value. 
-    void calculateLoopBounds(SplitInfo &SD);
-
+    
+    /// 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
@@ -157,47 +141,49 @@ namespace {
                         BasicBlock *Header,
                         PHINode *IV, Instruction *IVIncrement, Loop *LP);
 
-    /// moveExitCondition - Move exit condition EC into split condition block CondBB.
-    void moveExitCondition(BasicBlock *CondBB, BasicBlock *ActiveBB,
-                           BasicBlock *ExitBB, ICmpInst *EC, ICmpInst *SC,
-                           PHINode *IV, Instruction *IVAdd, Loop *LP);
-
-    /// splitLoop - Split current loop L in two loops using split information
-    /// SD. Update dominator information. Maintain LCSSA form.
-    bool splitLoop(SplitInfo &SD);
-
-    void initialize() {
-      IndVar = NULL; 
-      IndVarIncrement = NULL;
-      ExitCondition = NULL;
-      StartValue = NULL;
-      ExitValueNum = 0;
-      SplitData.clear();
-    }
+    // --- 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 invaraint 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 invaraint 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 invaraint 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 invaraint 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.
+    // Current Loop information.
     Loop *L;
     LPPassManager *LPM;
     LoopInfo *LI;
     ScalarEvolution *SE;
     DominatorTree *DT;
     DominanceFrontier *DF;
-    SmallVector<SplitInfo, 4> SplitData;
 
-    // Induction variable whose range is being split by this transformation.
     PHINode *IndVar;
-    Instruction *IndVarIncrement;
-      
-    // Loop exit condition.
     ICmpInst *ExitCondition;
-
-    // Induction variable's initial value.
-    Value *StartValue;
-
-    // Induction variable's final loop exit value operand number in exit condition..
-    unsigned ExitValueNum;
+    ICmpInst *SplitCondition;
+    Value *IVStartValue;
+    Value *IVExitValue;
+    Instruction *IVIncrement;
+    SmallPtrSet<Value *, 4> IVBasedValues;
   };
 }
 
@@ -211,7 +197,6 @@ Pass *llvm::createLoopIndexSplitPass() {
 
 // Index split Loop L. Return true if loop is split.
 bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
-  bool Changed = false;
   L = IncomingLoop;
   LPM = &LPM_Ref;
 
@@ -224,370 +209,189 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
   LI = &getAnalysis<LoopInfo>();
   DF = &getAnalysis<DominanceFrontier>();
 
-  initialize();
-
-  findLoopConditionals();
+  // Initialize loop data.
+  IndVar = L->getCanonicalInductionVariable();
+  if (!IndVar) return false;
 
-  if (!ExitCondition)
-    return false;
-
-  findSplitCondition();
-
-  if (SplitData.empty())
-    return false;
-
-  // First see if it is possible to eliminate loop itself or not.
-  for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin();
-       SI != SplitData.end();) {
-    SplitInfo &SD = *SI;
-    ICmpInst *CI = dyn_cast<ICmpInst>(SD.SplitCondition);
-    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<SplitInfo, 4>::iterator Delete_SI = SI;
-        SI = SplitData.erase(Delete_SI);
-      }
-    }
-    else if (isOneIterationLoop(CI)) {
-      Changed = processOneIterationLoop(SD);
-      if (Changed) {
-        ++NumIndexSplit;
-        // If is loop is eliminated then nothing else to do here.
-        return Changed;
-      } else {
-        SmallVector<SplitInfo, 4>::iterator Delete_SI = SI;
-        SI = SplitData.erase(Delete_SI);
-      }
-    } else
-      ++SI;
-  }
-
-  if (SplitData.empty())
-    return false;
-
-  // Split most profitiable condition.
-  // FIXME : Implement cost analysis.
-  unsigned MostProfitableSDIndex = 0;
-  Changed = splitLoop(SplitData[MostProfitableSDIndex]);
-
-  if (Changed)
-    ++NumIndexSplit;
+  bool P1InLoop = L->contains(IndVar->getIncomingBlock(1));
+  IVStartValue = IndVar->getIncomingValue(!P1InLoop);
+  IVIncrement = dyn_cast<Instruction>(IndVar->getIncomingValue(P1InLoop));
+  if (!IVIncrement) return false;
   
-  return Changed;
-}
+  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);
+    }
 
-/// isOneIterationLoop - Return true if split condition is EQ and 
-/// the IV is not used outside the loop.
-bool LoopIndexSplit::isOneIterationLoop(ICmpInst *CI) {
-  if (!CI)
+  // Reject loop if loop exit condition is not suitable.
+  SmallVector<BasicBlock *, 2> EBs;
+  L->getExitingBlocks(EBs);
+  if (EBs.size() != 1)
     return false;
-  if (CI->getPredicate() != ICmpInst::ICMP_EQ)
+  BranchInst *EBR = dyn_cast<BranchInst>(EBs[0]->getTerminator());
+  if (!EBR) return false;
+  ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition());
+  if (!ExitCondition) return false;
+  if (EBs[0] != L->getLoopLatch()) return false;
+  IVExitValue = ExitCondition->getOperand(1);
+  if (!L->isLoopInvariant(IVExitValue))
+    IVExitValue = ExitCondition->getOperand(0);
+  if (!L->isLoopInvariant(IVExitValue))
     return false;
 
-  Value *Incr = IndVar->getIncomingValueForBlock(L->getLoopLatch());
-  for (Value::use_iterator UI = Incr->use_begin(), E = Incr->use_end(); 
-       UI != E; ++UI)
-    if (!L->contains(cast<Instruction>(*UI)->getParent()))
-      return false;
-
-  return true;
-}
-/// Return true if V is a induction variable or induction variable's
-/// increment for loop L.
-void LoopIndexSplit::findIndVar(Value *V, Loop *L) {
-  
-  Instruction *I = dyn_cast<Instruction>(V);
-  if (!I)
-    return;
-
-  // Check if I is a phi node from loop header or not.
-  if (PHINode *PN = dyn_cast<PHINode>(V)) {
-    if (PN->getParent() == L->getHeader()) {
-      IndVar = PN;
-      return;
-    }
-  }
- 
-  // Check if I is a add instruction whose one operand is
-  // phi node from loop header and second operand is constant.
-  if (I->getOpcode() != Instruction::Add)
-    return;
-  
-  Value *Op0 = I->getOperand(0);
-  Value *Op1 = I->getOperand(1);
-  
-  if (PHINode *PN = dyn_cast<PHINode>(Op0)) 
-    if (PN->getParent() == L->getHeader()) 
-      if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) 
-        if (CI->isOne()) {
-          IndVar = PN;
-          IndVarIncrement = I;
-          return;
-        }
-
-  if (PHINode *PN = dyn_cast<PHINode>(Op1)) 
-    if (PN->getParent() == L->getHeader()) 
-      if (ConstantInt *CI = dyn_cast<ConstantInt>(Op0)) 
-        if (CI->isOne()) {
-          IndVar = PN;
-          IndVarIncrement = I;
-          return;
-        }
-  
-  return;
-}
-
-// Find loop's exit condition and associated induction variable.
-void LoopIndexSplit::findLoopConditionals() {
-
-  BasicBlock *ExitingBlock = NULL;
-
-  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
-       I != E; ++I) {
-    BasicBlock *BB = *I;
-    if (!L->isLoopExit(BB))
-      continue;
-    if (ExitingBlock)
-      return;
-    ExitingBlock = BB;
-  }
-
-  if (!ExitingBlock)
-    return;
-
-  // If exiting block is neither loop header nor loop latch then this loop is
-  // not suitable. 
-  if (ExitingBlock != L->getHeader() && ExitingBlock != L->getLoopLatch())
-    return;
-
-  // If exit block's terminator is conditional branch inst then we have found
-  // exit condition.
-  BranchInst *BR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
-  if (!BR || BR->isUnconditional())
-    return;
-  
-  ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition());
-  if (!CI)
-    return;
-
-  // FIXME 
-  if (CI->getPredicate() == ICmpInst::ICMP_EQ
-      || CI->getPredicate() == ICmpInst::ICMP_NE)
-    return;
-
-  ExitCondition = CI;
-
-  // Exit condition's one operand is loop invariant exit value and second 
-  // operand is SCEVAddRecExpr based on induction variable.
-  Value *V0 = CI->getOperand(0);
-  Value *V1 = CI->getOperand(1);
-  
-  SCEVHandle SH0 = SE->getSCEV(V0);
-  SCEVHandle SH1 = SE->getSCEV(V1);
-  
-  if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
-    ExitValueNum = 0;
-    findIndVar(V1, L);
-  }
-  else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
-    ExitValueNum =  1;
-    findIndVar(V0, L);
-  }
-
-  if (!IndVar) 
-    ExitCondition = NULL;
-  else if (IndVar) {
-    BasicBlock *Preheader = L->getLoopPreheader();
-    StartValue = IndVar->getIncomingValueForBlock(Preheader);
-  }
-
   // 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 (ExitCondition) {
-    ConstantInt *SV = dyn_cast<ConstantInt>(StartValue);
-    ConstantInt *EV = 
-      dyn_cast<ConstantInt>(ExitCondition->getOperand(ExitValueNum));
-    if (SV && EV && SV->getSExtValue() > EV->getSExtValue())
-      ExitCondition = NULL;
-    else if (EV && EV->isZero())
-      ExitCondition = NULL;
-  }
-}
-
-/// Find condition inside a loop that is suitable candidate for index split.
-void LoopIndexSplit::findSplitCondition() {
+  if (ConstantInt *SV = dyn_cast<ConstantInt>(IVStartValue))
+    if (ConstantInt *EV = dyn_cast<ConstantInt>(IVExitValue))
+      if (SV->getSExtValue() > EV->getSExtValue())
+        return false;
 
-  SplitInfo SD;
-  // Check all basic block's terminators.
-  for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
-       I != E; ++I) {
-    SD.clear();
-    BasicBlock *BB = *I;
+  if (processOneIterationLoop())
+    return true;
 
-    // If this basic block does not terminate in a conditional branch
-    // then terminator is not a suitable split condition.
-    BranchInst *BR = dyn_cast<BranchInst>(BB->getTerminator());
-    if (!BR)
-      continue;
-    
-    if (BR->isUnconditional())
-      continue;
+  if (updateLoopIterationSpace())
+    return true;
 
-    if (Instruction *AndI = dyn_cast<Instruction>(BR->getCondition())) {
-      if (AndI->getOpcode() == Instruction::And) {
-        ICmpInst *Op0 = dyn_cast<ICmpInst>(AndI->getOperand(0));
-        ICmpInst *Op1 = dyn_cast<ICmpInst>(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<ICmpInst>(BR->getCondition());
-    if (!CI || CI == ExitCondition)
-      continue;
+  if (splitLoop())
+    return true;
 
-    if (CI->getPredicate() == ICmpInst::ICMP_NE)
-      continue;
+  return false;
+}
 
-    // If split condition predicate is GT or GE then first execute
-    // false branch of split condition.
-    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
-    // based on induction variable then CI is a candidate split condition.
-    if (safeICmpInst(CI, SD))
-      SplitData.push_back(SD);
-  }
+// --- 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)->getParent()))
+      return true;
+  return false;
 }
 
-// safeIcmpInst - CI is considered safe instruction if one of the operand
-// is SCEVAddRecExpr based on induction variable and other operand is
-// loop invariant. If CI is safe then populate SplitInfo object SD appropriately
-// and return true;
-bool LoopIndexSplit::safeICmpInst(ICmpInst *CI, SplitInfo &SD) {
+// Return V+1
+static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt) {
+  ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
+  return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt);
+}
 
-  Value *V0 = CI->getOperand(0);
-  Value *V1 = CI->getOperand(1);
-  
-  SCEVHandle SH0 = SE->getSCEV(V0);
-  SCEVHandle SH1 = SE->getSCEV(V1);
-  
-  if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) {
-    SD.SplitValue = V0;
-    SD.SplitCondition = CI;
-    if (PHINode *PN = dyn_cast<PHINode>(V1)) {
-      if (PN == IndVar)
-        return true;
-    }
-    else  if (Instruction *Insn = dyn_cast<Instruction>(V1)) {
-      if (IndVarIncrement && IndVarIncrement == Insn)
-        return true;
-    }
-  }
-  else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) {
-    SD.SplitValue =  V1;
-    SD.SplitCondition = CI;
-    if (PHINode *PN = dyn_cast<PHINode>(V0)) {
-      if (PN == IndVar)
-        return true;
-    }
-    else  if (Instruction *Insn = dyn_cast<Instruction>(V0)) {
-      if (IndVarIncrement && IndVarIncrement == Insn)
-        return true;
-    }
-  }
+// Return V-1
+static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt) {
+  ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
+  return BinaryOperator::CreateSub(V, One, "lsp", InsertPt);
+}
 
-  return false;
+// Return min(V1, V1)
+static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
+ 
+  Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                          V1, V2, "lsp", InsertPt);
+  return SelectInst::Create(C, V1, V2, "lsp", InsertPt);
 }
 
-/// processOneIterationLoop - Current loop L contains compare instruction
-/// that compares induction variable, IndVar, against loop invariant. If
-/// entire (i.e. meaningful) loop body is dominated by this compare
-/// instruction then loop body is executed only once. 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
-///     }
-bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
+// Return max(V1, V2)
+static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
+ 
+  Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+                          V1, V2, "lsp", InsertPt);
+  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();
-
-  // First of all, 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.
-  if (!safeHeader(SD, Header)) 
+  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 Exiting block includes loop variant instructions then this
-  // loop may not be eliminated.
-  if (!safeExitingBlock(SD, ExitCondition->getParent())) 
+  // 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;
 
-  // Filter loops where split condition's false branch is not empty.
-  if (ExitCondition->getParent() != Header->getTerminator()->getSuccessor(1))
+  // 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)) {
+    Value *T = SplitValue;
+    SplitValue = OPV;
+    OPV = T;
+  }
+  if (!L->isLoopInvariant(SplitValue))
     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))
+  Instruction *OPI = dyn_cast<Instruction>(OPV);
+  if (!OPI) return false;
+  if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L))
     return false;
-
-  BasicBlock *Latch = L->getLoopLatch();
-  BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator());
-  if (!BR)
+  
+  if (!cleanBlock(Header))
     return false;
 
-  // Update CFG.
+  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(SD.SplitValue);
-
-  Instruction *LTerminator = Latch->getTerminator();
-  Instruction *Terminator = Header->getTerminator();
-  Value *ExitValue = ExitCondition->getOperand(ExitValueNum);
+  IndVar->replaceAllUsesWith(SplitValue);
 
   // Replace split condition in header.
   // Transform 
@@ -596,21 +400,19 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
   //      c1 = icmp uge i32 SplitValue, StartValue
   //      c2 = icmp ult i32 SplitValue, ExitValue
   //      and i32 c1, c2 
-  bool SignedPredicate = ExitCondition->isSignedPredicate();
-  CmpInst::Predicate C2Predicate = ExitCondition->getPredicate();
-  if (LTerminator->getOperand(0) != Header)
-    C2Predicate = CmpInst::getInversePredicate(C2Predicate);
-  Instruction *C1 = new ICmpInst(SignedPredicate ? 
+  Instruction *C1 = new ICmpInst(ExitCondition->isSignedPredicate() ? 
                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
-                                 SD.SplitValue, StartValue, "lisplit", 
-                                 Terminator);
-  Instruction *C2 = new ICmpInst(C2Predicate,
-                                 SD.SplitValue, ExitValue, "lisplit", 
-                                 Terminator);
-  Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", 
-                                                      Terminator);
-  SD.SplitCondition->replaceAllUsesWith(NSplitCond);
-  SD.SplitCondition->eraseFromParent();
+                                 SplitValue, IVStartValue, "lisplit", BR);
+
+  CmpInst::Predicate C2P  = ExitCondition->getPredicate();
+  BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
+  if (LatchBR->getOperand(0) != Header)
+    C2P = CmpInst::getInversePredicate(C2P);
+  Instruction *C2 = new ICmpInst(C2P, SplitValue, IVExitValue, "lisplit", BR);
+  Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
+
+  SplitCondition->replaceAllUsesWith(NSplitCond);
+  SplitCondition->eraseFromParent();
 
   // Remove Latch to Header edge.
   BasicBlock *LatchSucc = NULL;
@@ -620,40 +422,12 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
     if (Header != *SI)
       LatchSucc = *SI;
   }
-  BR->setUnconditionalDest(LatchSucc);
-
-  // Now, clear latch block. Remove instructions that are responsible
-  // to increment induction variable. 
-  for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end();
-       LB != LE; ) {
-    Instruction *I = LB;
-    ++LB;
-    if (isa<PHINode>(I) || I == LTerminator)
-      continue;
-
-    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<Instruction>(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();
-    }
-  }
+  LatchBR->setUnconditionalDest(LatchSucc);
 
+  // Remove IVIncrement
+  IVIncrement->replaceAllUsesWith(UndefValue::get(IVIncrement->getType()));
+  IVIncrement->eraseFromParent();
+  
   LPM->deleteLoopFromQueue(L);
 
   // Update Dominator Info.
@@ -669,330 +443,99 @@ bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) {
     if (LatchDF != DF->end()) 
       DF->removeFromFrontier(LatchDF, Header);
   }
-  return true;
-}
-
-// If loop header includes loop variant instruction operands then
-// this loop can not be eliminated. This is used by processOneIterationLoop().
-bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) {
-
-  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<PHINode>(I))
-      continue;
-
-    // SplitCondition itself is OK.
-    if (I == SD.SplitCondition)
-      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;
-  }
-  
-  return true;
-}
-
-// If Exiting block includes loop variant instructions then this
-// loop may not be eliminated. This is used by processOneIterationLoop().
-bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD, 
-                                       BasicBlock *ExitingBlock) {
-
-  for (BasicBlock::iterator BI = ExitingBlock->begin(), 
-         BE = ExitingBlock->end(); BI != BE; ++BI) {
-    Instruction *I = BI;
-
-    // PHI Nodes are OK.
-    if (isa<PHINode>(I))
-      continue;
-
-    // Induction variable increment is OK.
-    if (IndVarIncrement && IndVarIncrement == I)
-      continue;
-
-    // Check if I is induction variable increment instruction.
-    if (I->getOpcode() == Instruction::Add) {
-
-      Value *Op0 = I->getOperand(0);
-      Value *Op1 = I->getOperand(1);
-      PHINode *PN = NULL;
-      ConstantInt *CI = NULL;
-
-      if ((PN = dyn_cast<PHINode>(Op0))) {
-        if ((CI = dyn_cast<ConstantInt>(Op1)))
-          if (CI->isOne()) {
-            if (!IndVarIncrement && PN == IndVar)
-              IndVarIncrement = I;
-            // else this is another loop induction variable
-            continue;
-          }
-      } else 
-        if ((PN = dyn_cast<PHINode>(Op1))) {
-          if ((CI = dyn_cast<ConstantInt>(Op0)))
-            if (CI->isOne()) {
-              if (!IndVarIncrement && PN == IndVar)
-                IndVarIncrement = I;
-              // else this is another loop induction variable
-              continue;
-            }
-      }
-    } 
-
-    // I is an Exit condition if next instruction is block terminator.
-    // Exit condition is OK if it compares loop invariant exit value,
-    // which is checked below.
-    else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) {
-      if (EC == ExitCondition)
-        continue;
-    }
-
-    if (I == ExitingBlock->getTerminator())
-      continue;
-
-    // Otherwise we have instruction that may not be safe.
-    return false;
-  }
-
-  // We could not find any reason to consider ExitingBlock unsafe.
+  ++NumIndexSplitRemoved;
   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;
+/// 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