In the TD pass, don't iterate over the scalar map to find the globals, iterate over

[oota-llvm.git] / lib / Analysis / InductionVariable.cpp

diff --git a/lib/Analysis/InductionVariable.cpp b/lib/Analysis/InductionVariable.cpp
index 4c53c967863cfb7e01673ed2eb8e9fc787eaf4a7..b602529494809f3fb0034203496f7cbdef89df83 100644 (file)
--- a/lib/Analysis/InductionVariable.cpp
+++ b/lib/Analysis/InductionVariable.cpp
@@ -1,4 +1,11 @@
 //===- InductionVariable.cpp - Induction variable classification ----------===//
+// 
+//                     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 implements identification and classification of induction 
 // variables.  Induction variables must contain a PHI node that exists in a 
@@ -20,14 +27,13 @@
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/Expressions.h"
 #include "llvm/BasicBlock.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOperators.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
 #include "llvm/Type.h"
 #include "llvm/Constants.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Assembly/Writer.h"
 #include "Support/Debug.h"
+using namespace llvm;
 
 static bool isLoopInvariant(const Value *V, const Loop *L) {
   if (const Instruction *I = dyn_cast<Instruction>(V))
@@ -83,8 +89,8 @@ InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
   Value *V2 = Phi->getIncomingValue(1);
 
   if (L == 0) {  // No loop information?  Base everything on expression analysis
-    ExprType E1 = ClassifyExpression(V1);
-    ExprType E2 = ClassifyExpression(V2);
+    ExprType E1 = ClassifyExpr(V1);
+    ExprType E2 = ClassifyExpr(V2);
 
     if (E1.ExprTy > E2.ExprTy)        // Make E1 be the simpler expression
       std::swap(E1, E2);
@@ -116,17 +122,37 @@ InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
     if (V2 == Phi) {  // referencing the PHI directly?  Must have zero step
       Step = Constant::getNullValue(Phi->getType());
     } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
-      // TODO: This could be much better...
       if (I->getOpcode() == Instruction::Add) {
         if (I->getOperand(0) == Phi)
           Step = I->getOperand(1);
         else if (I->getOperand(1) == Phi)
           Step = I->getOperand(0);
+      } else if (I->getOpcode() == Instruction::Sub &&
+                 I->getOperand(0) == Phi) {
+        // If the incoming value is a constant, just form a constant negative
+        // step.  Otherwise, negate the step outside of the loop and use it.
+        Value *V = I->getOperand(1);
+        Constant *Zero = Constant::getNullValue(V->getType());
+        if (Constant *CV = dyn_cast<Constant>(V))
+          Step = ConstantExpr::get(Instruction::Sub, Zero, CV);
+        else if (Instruction *I = dyn_cast<Instruction>(V)) {
+          Step = BinaryOperator::create(Instruction::Sub, Zero, V,
+                                        V->getName()+".neg", I->getNext());
+
+        } else {
+          Step = BinaryOperator::create(Instruction::Sub, Zero, V,
+                                        V->getName()+".neg", 
+                              Phi->getParent()->getParent()->begin()->begin());
+        }
       }
+    } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V2)) {
+      if (GEP->getNumOperands() == 2 &&
+          GEP->getOperand(0) == Phi)
+        Step = GEP->getOperand(1);
     }
 
     if (Step == 0) {                  // Unrecognized step value...
-      ExprType StepE = ClassifyExpression(V2);
+      ExprType StepE = ClassifyExpr(V2);
       if (StepE.ExprTy != ExprType::Linear ||
           StepE.Var != Phi) return;
 
@@ -134,7 +160,7 @@ InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
       if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
       Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
     } else {   // We were able to get a step value, simplify with expr analysis
-      ExprType StepE = ClassifyExpression(Step);
+      ExprType StepE = ClassifyExpr(Step);
       if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
         // No offset from variable?  Grab the variable
         Step = StepE.Var;
@@ -178,7 +204,7 @@ Value *InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
     return 0;
   }
 
-  // Find final node: predecesor of the loop header that's also an exit
+  // Find final node: predecessor of the loop header that's also an exit
   BasicBlock *terminator = 0;
   for (pred_iterator PI = pred_begin(L->getHeader()),
          PE = pred_end(L->getHeader()); PI != PE; ++PI)
@@ -215,10 +241,9 @@ Value *InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
   DEBUG(std::cerr << "sci:" << *SCI);
   Value *condVal0 = SCI->getOperand(0);
   Value *condVal1 = SCI->getOperand(1);
-  Value *indVar = 0;
 
-  // the induction variable is the one coming from the backedge
-  indVar = Phi->getIncomingValue(L->contains(Phi->getIncomingBlock(1)));
+  // The induction variable is the one coming from the backedge
+  Value *indVar = Phi->getIncomingValue(L->contains(Phi->getIncomingBlock(1)));
 
 
   // Check to see if indVar is one of the parameters in SCI and if the other is