- Somehow I forgot about one / une.
[oota-llvm.git] / lib / Transforms / Scalar / IndVarSimplify.cpp
index 8042d62581bfc1151e3847e5a2e6254c38bae343..13be455c4d0b590c0ca017865367536b775dc2ce 100644 (file)
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by the LLVM research group 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.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -70,14 +70,14 @@ namespace {
   public:
 
    static char ID; // Pass identification, replacement for typeid
-   IndVarSimplify() : LoopPass((intptr_t)&ID) {}
+   IndVarSimplify() : LoopPass(&ID) {}
 
    bool runOnLoop(Loop *L, LPPassManager &LPM);
    bool doInitialization(Loop *L, LPPassManager &LPM);
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+     AU.addRequired<ScalarEvolution>();
      AU.addRequiredID(LCSSAID);
      AU.addRequiredID(LoopSimplifyID);
-     AU.addRequired<ScalarEvolution>();
      AU.addRequired<LoopInfo>();
      AU.addPreservedID(LoopSimplifyID);
      AU.addPreservedID(LCSSAID);
@@ -90,15 +90,18 @@ namespace {
                                     std::set<Instruction*> &DeadInsts);
     Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
                                            SCEVExpander &RW);
-    void RewriteLoopExitValues(Loop *L);
+    void RewriteLoopExitValues(Loop *L, SCEV *IterationCount);
 
     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
-  };
 
-  char IndVarSimplify::ID = 0;
-  RegisterPass<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
+    void OptimizeCanonicalIVType(Loop *L);
+  };
 }
 
+char IndVarSimplify::ID = 0;
+static RegisterPass<IndVarSimplify>
+X("indvars", "Canonicalize Induction Variables");
+
 LoopPass *llvm::createIndVarSimplifyPass() {
   return new IndVarSimplify();
 }
@@ -115,7 +118,7 @@ DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
           Insts.insert(U);
-      SE->deleteInstructionFromRecords(I);
+      SE->deleteValueFromRecords(I);
       DOUT << "INDVARS: Deleting: " << *I;
       I->eraseFromParent();
       Changed = true;
@@ -145,12 +148,12 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
       Value *AddedVal = GEPI->getOperand(1);
 
       // Insert a new integer PHI node into the top of the block.
-      PHINode *NewPhi = new PHINode(AddedVal->getType(),
-                                    PN->getName()+".rec", PN);
+      PHINode *NewPhi = PHINode::Create(AddedVal->getType(),
+                                        PN->getName()+".rec", PN);
       NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);
 
       // Create the new add instruction.
-      Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal,
+      Value *NewAdd = BinaryOperator::CreateAdd(NewPhi, AddedVal,
                                                 GEPI->getName()+".rec", GEPI);
       NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));
 
@@ -178,10 +181,13 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
               Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0),
                                                              &CEIdxs[0],
                                                              CEIdxs.size());
-              GetElementPtrInst *NGEPI = new GetElementPtrInst(
-                  NCE, Constant::getNullValue(Type::Int32Ty), NewAdd, 
+              Value *Idx[2];
+              Idx[0] = Constant::getNullValue(Type::Int32Ty);
+              Idx[1] = NewAdd;
+              GetElementPtrInst *NGEPI = GetElementPtrInst::Create(
+                  NCE, Idx, Idx + 2, 
                   GEPI->getName(), GEPI);
-              SE->deleteInstructionFromRecords(GEPI);
+              SE->deleteValueFromRecords(GEPI);
               GEPI->replaceAllUsesWith(NGEPI);
               GEPI->eraseFromParent();
               GEPI = NGEPI;
@@ -197,8 +203,8 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
         BasicBlock::iterator InsertPos = PN; ++InsertPos;
         while (isa<PHINode>(InsertPos)) ++InsertPos;
         Value *PreInc =
-          new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx),
-                                NewPhi, "", InsertPos);
+          GetElementPtrInst::Create(PN->getIncomingValue(PreheaderIdx),
+                                    NewPhi, "", InsertPos);
         PreInc->takeName(PN);
         PN->replaceAllUsesWith(PreInc);
       }
@@ -224,7 +230,7 @@ Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
                                                        SCEVExpander &RW) {
   // Find the exit block for the loop.  We can currently only handle loops with
   // a single exit.
-  std::vector<BasicBlock*> ExitBlocks;
+  SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getExitBlocks(ExitBlocks);
   if (ExitBlocks.size() != 1) return 0;
   BasicBlock *ExitBlock = ExitBlocks[0];
@@ -264,8 +270,8 @@ Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
     // The IterationCount expression contains the number of times that the
     // backedge actually branches to the loop header.  This is one less than the
     // number of times the loop executes, so add one to it.
-    Constant *OneC = ConstantInt::get(IterationCount->getType(), 1);
-    TripCount = SCEVAddExpr::get(IterationCount, SCEVUnknown::get(OneC));
+    ConstantInt *OneC = ConstantInt::get(IterationCount->getType(), 1);
+    TripCount = SE->getAddExpr(IterationCount, SE->getConstant(OneC));
     IndVar = L->getCanonicalInductionVariableIncrement();
   } else {
     // We have to use the preincremented value...
@@ -277,8 +283,7 @@ Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 
   // Expand the code for the iteration count into the preheader of the loop.
   BasicBlock *Preheader = L->getLoopPreheader();
-  Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator(),
-                                    IndVar->getType());
+  Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator());
 
   // Insert a new icmp_ne or icmp_eq instruction before the branch.
   ICmpInst::Predicate Opcode;
@@ -300,7 +305,7 @@ Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 /// final value of any expressions that are recurrent in the loop, and
 /// substitute the exit values from the loop into any instructions outside of
 /// the loop that use the final values of the current expressions.
-void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
+void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEV *IterationCount) {
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Scan all of the instructions in the loop, looking at those that have
@@ -310,16 +315,15 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
   // We insert the code into the preheader of the loop if the loop contains
   // multiple exit blocks, or in the exit block if there is exactly one.
   BasicBlock *BlockToInsertInto;
-  std::vector<BasicBlock*> ExitBlocks;
+  SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
   if (ExitBlocks.size() == 1)
     BlockToInsertInto = ExitBlocks[0];
   else
     BlockToInsertInto = Preheader;
-  BasicBlock::iterator InsertPt = BlockToInsertInto->begin();
-  while (isa<PHINode>(InsertPt)) ++InsertPt;
+  BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
 
-  bool HasConstantItCount = isa<SCEVConstant>(SE->getIterationCount(L));
+  bool HasConstantItCount = isa<SCEVConstant>(IterationCount);
 
   std::set<Instruction*> InstructionsToDelete;
   std::map<Instruction*, Value*> ExitValues;
@@ -383,7 +387,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
         // just reuse it.
         Value *&ExitVal = ExitValues[Inst];
         if (!ExitVal)
-          ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt,Inst->getType());
+          ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt);
         
         DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
              << "  LoopVal = " << *Inst << "\n";
@@ -399,7 +403,7 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
         // the PHI entirely.  This is safe, because the NewVal won't be variant
         // in the loop, so we don't need an LCSSA phi node anymore.
         if (NumPreds == 1) {
-          SE->deleteInstructionFromRecords(PN);
+          SE->deleteValueFromRecords(PN);
           PN->replaceAllUsesWith(ExitVal);
           PN->eraseFromParent();
           break;
@@ -456,7 +460,7 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   //
   SCEVHandle IterationCount = SE->getIterationCount(L);
   if (!isa<SCEVCouldNotCompute>(IterationCount))
-    RewriteLoopExitValues(L);
+    RewriteLoopExitValues(L, IterationCount);
 
   // Next, analyze all of the induction variables in the loop, canonicalizing
   // auxillary induction variables.
@@ -519,15 +523,16 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
   Changed = true;
   DOUT << "INDVARS: New CanIV: " << *IndVar;
 
-  if (!isa<SCEVCouldNotCompute>(IterationCount))
+  if (!isa<SCEVCouldNotCompute>(IterationCount)) {
+    IterationCount = SE->getTruncateOrZeroExtend(IterationCount, LargestType);
     if (Instruction *DI = LinearFunctionTestReplace(L, IterationCount,Rewriter))
       DeadInsts.insert(DI);
+  }
 
   // Now that we have a canonical induction variable, we can rewrite any
   // recurrences in terms of the induction variable.  Start with the auxillary
   // induction variables, and recursively rewrite any of their uses.
-  BasicBlock::iterator InsertPt = Header->begin();
-  while (isa<PHINode>(InsertPt)) ++InsertPt;
+  BasicBlock::iterator InsertPt = Header->getFirstNonPHI();
 
   // If there were induction variables of other sizes, cast the primary
   // induction variable to the right size for them, avoiding the need for the
@@ -552,11 +557,9 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   // Rewrite all induction variables in terms of the canonical induction
   // variable.
-  std::map<unsigned, Value*> InsertedSizes;
   while (!IndVars.empty()) {
     PHINode *PN = IndVars.back().first;
-    Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt,
-                                           PN->getType());
+    Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt);
     DOUT << "INDVARS: Rewrote IV '" << *IndVars.back().second << "' " << *PN
          << "   into = " << *NewVal << "\n";
     NewVal->takeName(PN);
@@ -572,9 +575,10 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 #if 0
   // Now replace all derived expressions in the loop body with simpler
   // expressions.
-  for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
-    if (LI->getLoopFor(L->getBlocks()[i]) == L) {  // Not in a subloop...
-      BasicBlock *BB = L->getBlocks()[i];
+  for (LoopInfo::block_iterator I = L->block_begin(), E = L->block_end();
+       I != E; ++I) {
+    BasicBlock *BB = *I;
+    if (LI->getLoopFor(BB) == L) {  // Not in a subloop...
       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
         if (I->getType()->isInteger() &&      // Is an integer instruction
             !I->use_empty() &&
@@ -591,10 +595,126 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
           }
         }
     }
+  }
 #endif
 
   DeleteTriviallyDeadInstructions(DeadInsts);
-  
+  OptimizeCanonicalIVType(L);
   assert(L->isLCSSAForm());
   return Changed;
 }
+
+/// OptimizeCanonicalIVType - If loop induction variable is always
+/// sign or zero extended then extend the type of the induction 
+/// variable.
+void IndVarSimplify::OptimizeCanonicalIVType(Loop *L) {
+  PHINode *PH = L->getCanonicalInductionVariable();
+  if (!PH) return;
+  
+  // Check loop iteration count.
+  SCEVHandle IC = SE->getIterationCount(L);
+  if (isa<SCEVCouldNotCompute>(IC)) return;
+  SCEVConstant *IterationCount = dyn_cast<SCEVConstant>(IC);
+  if (!IterationCount) return;
+
+  unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
+  unsigned BackEdge     = IncomingEdge^1;
+  
+  // Check IV uses. If all IV uses are either SEXT or ZEXT (except
+  // IV increment instruction) then this IV is suitable for this
+  // transformation.
+  bool isSEXT = false;
+  BinaryOperator *Incr = NULL;
+  const Type *NewType = NULL;
+  for(Value::use_iterator UI = PH->use_begin(), UE = PH->use_end(); 
+      UI != UE; ++UI) {
+    const Type *CandidateType = NULL;
+    if (ZExtInst *ZI = dyn_cast<ZExtInst>(UI))
+      CandidateType = ZI->getDestTy();
+    else if (SExtInst *SI = dyn_cast<SExtInst>(UI)) {
+      CandidateType = SI->getDestTy();
+      isSEXT = true;
+    }
+    else if ((Incr = dyn_cast<BinaryOperator>(UI))) {
+      // Validate IV increment instruction.
+      if (PH->getIncomingValue(BackEdge) == Incr)
+        continue;
+    }
+    if (!CandidateType) {
+      NewType = NULL;
+      break;
+    }
+    if (!NewType)
+      NewType = CandidateType;
+    else if (NewType != CandidateType) {
+      NewType = NULL;
+      break;
+    }
+  }
+
+  // IV uses are not suitable then avoid this transformation.
+  if (!NewType || !Incr)
+    return;
+
+  // IV increment instruction has two uses, one is loop exit condition
+  // and second is the IV (phi node) itself.
+  ICmpInst *Exit = NULL;
+  for(Value::use_iterator II = Incr->use_begin(), IE = Incr->use_end();
+      II != IE; ++II) {
+    if (PH == *II)  continue;
+    Exit = dyn_cast<ICmpInst>(*II);
+    break;
+  }
+  if (!Exit) return;
+  ConstantInt *EV = dyn_cast<ConstantInt>(Exit->getOperand(0));
+  if (!EV) 
+    EV = dyn_cast<ConstantInt>(Exit->getOperand(1));
+  if (!EV) return;
+
+  // Check iteration count max value to avoid loops that wrap around IV.
+  APInt ICount = IterationCount->getValue()->getValue();
+  if (ICount.isNegative()) return;
+  uint32_t BW = PH->getType()->getPrimitiveSizeInBits();
+  APInt Max = (isSEXT ? APInt::getSignedMaxValue(BW) : APInt::getMaxValue(BW));
+  if (ICount.getZExtValue() > Max.getZExtValue())  return;                         
+
+  // Extend IV type.
+
+  SCEVExpander Rewriter(*SE, *LI);
+  Value *NewIV = Rewriter.getOrInsertCanonicalInductionVariable(L,NewType);
+  PHINode *NewPH = cast<PHINode>(NewIV);
+  Instruction *NewIncr = cast<Instruction>(NewPH->getIncomingValue(BackEdge));
+
+  // Replace all SEXT or ZEXT uses.
+  SmallVector<Instruction *, 4> PHUses;
+  for(Value::use_iterator UI = PH->use_begin(), UE = PH->use_end(); 
+      UI != UE; ++UI) {
+      Instruction *I = cast<Instruction>(UI);
+      PHUses.push_back(I);
+  }
+  while (!PHUses.empty()){
+    Instruction *Use = PHUses.back(); PHUses.pop_back();
+    if (Incr == Use) continue;
+    
+    SE->deleteValueFromRecords(Use);
+    Use->replaceAllUsesWith(NewIV);
+    Use->eraseFromParent();
+  }
+
+  // Replace exit condition.
+  ConstantInt *NEV = ConstantInt::get(NewType, EV->getZExtValue());
+  Instruction *NE = new ICmpInst(Exit->getPredicate(),
+                                 NewIncr, NEV, "new.exit", 
+                                 Exit->getParent()->getTerminator());
+  SE->deleteValueFromRecords(Exit);
+  Exit->replaceAllUsesWith(NE);
+  Exit->eraseFromParent();
+  
+  // Remove old IV and increment instructions.
+  SE->deleteValueFromRecords(PH);
+  PH->removeIncomingValue((unsigned)0);
+  PH->removeIncomingValue((unsigned)0);
+  SE->deleteValueFromRecords(Incr);
+  Incr->eraseFromParent();
+}
+