LoopIndexSplit needs to inform the loop pass manager of the instructions it is

[oota-llvm.git] / lib / Transforms / Scalar / LoopIndexSplit.cpp

diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index cbe507cfa99edf91ea6c9d9b6ebefb45db6ad827..9f5f2cfd39d807082f3e8130ee8071818efd5eed 100644 (file)
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -42,11 +42,13 @@
 #define DEBUG_TYPE "loop-index-split"
 
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/IntrinsicInst.h"
 #include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.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/Support/Compiler.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Statistic.h"
@@ -69,7 +71,6 @@ namespace {
     bool runOnLoop(Loop *L, LPPassManager &LPM);
 
     void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.addRequired<ScalarEvolution>();
       AU.addPreserved<ScalarEvolution>();
       AU.addRequiredID(LCSSAID);
       AU.addPreservedID(LCSSAID);
@@ -173,7 +174,6 @@ namespace {
     Loop *L;
     LPPassManager *LPM;
     LoopInfo *LI;
-    ScalarEvolution *SE;
     DominatorTree *DT;
     DominanceFrontier *DF;
 
@@ -204,7 +204,6 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
   if (!L->getSubLoops().empty())
     return false;
 
-  SE = &getAnalysis<ScalarEvolution>();
   DT = &getAnalysis<DominatorTree>();
   LI = &getAnalysis<LoopInfo>();
   DF = &getAnalysis<DominanceFrontier>();
@@ -235,15 +234,14 @@ bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) {
     }
 
   // Reject loop if loop exit condition is not suitable.
-  SmallVector<BasicBlock *, 2> EBs;
-  L->getExitingBlocks(EBs);
-  if (EBs.size() != 1)
+  BasicBlock *ExitingBlock = L->getExitingBlock();
+  if (!ExitingBlock)
     return false;
-  BranchInst *EBR = dyn_cast<BranchInst>(EBs[0]->getTerminator());
+  BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
   if (!EBR) return false;
   ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition());
   if (!ExitCondition) return false;
-  if (EBs[0] != L->getLoopLatch()) return false;
+  if (ExitingBlock != L->getLoopLatch()) return false;
   IVExitValue = ExitCondition->getOperand(1);
   if (!L->isLoopInvariant(IVExitValue))
     IVExitValue = ExitCondition->getOperand(0);
@@ -348,10 +346,25 @@ bool LoopIndexSplit::processOneIterationLoop() {
   if (!L->isLoopInvariant(SplitValue))
     return false;
   Instruction *OPI = dyn_cast<Instruction>(OPV);
-  if (!OPI) return false;
+  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;
 
@@ -402,13 +415,13 @@ bool LoopIndexSplit::processOneIterationLoop() {
   //      and i32 c1, c2 
   Instruction *C1 = new ICmpInst(ExitCondition->isSignedPredicate() ? 
                                  ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
-                                 SplitValue, IVStartValue, "lisplit", BR);
+                                 SplitValue, StartValue, "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 *C2 = new ICmpInst(C2P, SplitValue, ExitValue, "lisplit", BR);
   Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
 
   SplitCondition->replaceAllUsesWith(NSplitCond);
@@ -422,11 +435,11 @@ bool LoopIndexSplit::processOneIterationLoop() {
     if (Header != *SI)
       LatchSucc = *SI;
   }
-  LatchBR->setUnconditionalDest(LatchSucc);
 
-  // Remove IVIncrement
-  IVIncrement->replaceAllUsesWith(UndefValue::get(IVIncrement->getType()));
-  IVIncrement->eraseFromParent();
+  // Clean up latch block.
+  Value *LatchBRCond = LatchBR->getCondition();
+  LatchBR->setUnconditionalDest(LatchSucc);
+  RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond);
   
   LPM->deleteLoopFromQueue(L);
 
@@ -535,6 +548,21 @@ bool LoopIndexSplit::updateLoopIterationSpace() {
   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
@@ -661,14 +689,15 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
 
   while (!WorkList.empty()) {
     BasicBlock *BB = WorkList.back(); WorkList.pop_back();
+    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();
     }
-    LPM->deleteSimpleAnalysisValue(BB, LP);
     DT->eraseNode(BB);
     DF->removeBlock(BB);
     LI->removeBlock(BB);
@@ -1104,7 +1133,8 @@ bool LoopIndexSplit::cleanBlock(BasicBlock *BB) {
     Instruction *I = BI;
 
     if (isa<PHINode>(I) || I == Terminator || I == ExitCondition
-        || I == SplitCondition || IVBasedValues.count(I))
+        || I == SplitCondition || IVBasedValues.count(I) 
+        || isa<DbgInfoIntrinsic>(I))
       continue;
 
     if (I->mayWriteToMemory())