lib/Analysis/InductionVariable.cpp

   1 //===- llvm/Analysis/InductionVariable.h - Induction variable ----*- C++ -*--=//
   2 //
   3 // This interface is used to identify and classify induction variables that
   4 // exist in the program.  Induction variables must contain a PHI node that
   5 // exists in a loop header.  Because of this, they are identified an managed by
   6 // this PHI node.
   7 //
   8 // Induction variables are classified into a type.  Knowing that an induction
   9 // variable is of a specific type can constrain the values of the start and
  10 // step.  For example, a SimpleLinear induction variable must have a start and
  11 // step values that are constants.
  12 //
  13 // Induction variables can be created with or without loop information.  If no
  14 // loop information is available, induction variables cannot be recognized to be
  15 // more than SimpleLinear variables.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Analysis/InductionVariable.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/Expressions.h"
  22 #include "llvm/iPHINode.h"
  23 #include "llvm/InstrTypes.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/Assembly/Writer.h"
  27
  28 using analysis::ExprType;
  29
  30
  31 static bool isLoopInvariant(const Value *V, const Loop *L) {
  32   if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
  33     return true;
  34
  35   const Instruction *I = cast<Instruction>(V);
  36   const BasicBlock *BB = I->getParent();
  37
  38   return !L->contains(BB);
  39 }
  40
  41 enum InductionVariable::iType
  42 InductionVariable::Classify(const Value *Start, const Value *Step,
  43                             const Loop *L) {
  44   // Check for cannonical and simple linear expressions now...
  45   if (const ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
  46     if (const ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
  47       if (CStart->equalsInt(0) && CStep->equalsInt(1))
  48         return Cannonical;
  49       else
  50         return SimpleLinear;
  51     }
  52
  53   // Without loop information, we cannot do any better, so bail now...
  54   if (L == 0) return Unknown;
  55
  56   if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
  57     return Linear;
  58   return Unknown;
  59 }
  60
  61 // Create an induction variable for the specified value.  If it is a PHI, and
  62 // if it's recognizable, classify it and fill in instance variables.
  63 //
  64 InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo) {
  65   InductionType = Unknown;     // Assume the worst
  66   Phi = P;
  67
  68   // If the PHI node has more than two predecessors, we don't know how to
  69   // handle it.
  70   //
  71   if (Phi->getNumIncomingValues() != 2) return;
  72
  73   // FIXME: Handle FP induction variables.
  74   if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy)
  75     return;
  76
  77   // If we have loop information, make sure that this PHI node is in the header
  78   // of a loop...
  79   //
  80   const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
  81   if (L && L->getHeader() != Phi->getParent())
  82     return;
  83
  84   Value *V1 = Phi->getIncomingValue(0);
  85   Value *V2 = Phi->getIncomingValue(1);
  86
  87   if (L == 0) {  // No loop information?  Base everything on expression analysis
  88     ExprType E1 = analysis::ClassifyExpression(V1);
  89     ExprType E2 = analysis::ClassifyExpression(V2);
  90
  91     if (E1.ExprTy > E2.ExprTy)        // Make E1 be the simpler expression
  92       std::swap(E1, E2);
  93
  94     // E1 must be a constant incoming value, and E2 must be a linear expression
  95     // with respect to the PHI node.
  96     //
  97     if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
  98         E2.Var != Phi)
  99       return;
 100
 101     // Okay, we have found an induction variable. Save the start and step values
 102     const Type *ETy = Phi->getType();
 103     if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 104
 105     Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0));
 106     Step  = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0));
 107   } else {
 108     // Okay, at this point, we know that we have loop information...
 109
 110     // Make sure that V1 is the incoming value, and V2 is from the backedge of
 111     // the loop.
 112     if (L->contains(Phi->getIncomingBlock(0)))     // Wrong order.  Swap now.
 113       std::swap(V1, V2);
 114
 115     Start = V1;     // We know that Start has to be loop invariant...
 116     Step = 0;
 117
 118     if (V2 == Phi) {  // referencing the PHI directly?  Must have zero step
 119       Step = Constant::getNullValue(Phi->getType());
 120     } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
 121       // TODO: This could be much better...
 122       if (I->getOpcode() == Instruction::Add) {
 123         if (I->getOperand(0) == Phi)
 124           Step = I->getOperand(1);
 125         else if (I->getOperand(1) == Phi)
 126           Step = I->getOperand(0);
 127       }
 128     }
 129
 130     if (Step == 0) {                  // Unrecognized step value...
 131       ExprType StepE = analysis::ClassifyExpression(V2);
 132       if (StepE.ExprTy != ExprType::Linear ||
 133           StepE.Var != Phi) return;
 134
 135       const Type *ETy = Phi->getType();
 136       if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 137       Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
 138     } else {   // We were able to get a step value, simplify with expr analysis
 139       ExprType StepE = analysis::ClassifyExpression(Step);
 140       if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
 141         // No offset from variable?  Grab the variable
 142         Step = StepE.Var;
 143       } else if (StepE.ExprTy == ExprType::Constant) {
 144         if (StepE.Offset)
 145           Step = (Value*)StepE.Offset;
 146         else
 147           Step = Constant::getNullValue(Step->getType());
 148         const Type *ETy = Phi->getType();
 149         if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 150         Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0));
 151       }
 152     }
 153   }
 154
 155   // Classify the induction variable type now...
 156   InductionType = InductionVariable::Classify(Start, Step, L);
 157 }
 158
 159 void InductionVariable::print(std::ostream &o) const {
 160   switch (InductionType) {
 161   case InductionVariable::Cannonical:   o << "Cannonical ";   break;
 162   case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
 163   case InductionVariable::Linear:       o << "Linear ";       break;
 164   case InductionVariable::Unknown:      o << "Unrecognized "; break;
 165   }
 166   o << "Induction Variable";
 167   if (Phi) {
 168     WriteAsOperand(o, Phi);
 169     o << ":\n" << Phi;
 170   } else {
 171     o << "\n";
 172   }
 173   if (InductionType == InductionVariable::Unknown) return;
 174
 175   o << "  Start ="; WriteAsOperand(o, Start);
 176   o << "  Step =" ; WriteAsOperand(o, Step);
 177   o << "\n";
 178 }