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/ConstantVals.h"
  26
  27 using analysis::ExprType;
  28
  29
  30 static bool isLoopInvariant(const Value *V, const cfg::Loop *L) {
  31   if (isa<Constant>(V) || isa<MethodArgument>(V) || isa<GlobalValue>(V))
  32     return true;
  33
  34   const Instruction *I = cast<Instruction>(V);
  35   const BasicBlock *BB = I->getParent();
  36
  37   return !L->contains(BB);
  38 }
  39
  40 enum InductionVariable::iType
  41 InductionVariable::Classify(const Value *Start, const Value *Step,
  42                             const cfg::Loop *L = 0) {
  43   // Check for cannonical and simple linear expressions now...
  44   if (ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
  45     if (ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
  46       if (CStart->equalsInt(0) && CStep->equalsInt(1))
  47         return Cannonical;
  48       else
  49         return SimpleLinear;
  50     }
  51
  52   // Without loop information, we cannot do any better, so bail now...
  53   if (L == 0) return Unknown;
  54
  55   if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
  56     return Linear;
  57   return Unknown;
  58 }
  59
  60 // Create an induction variable for the specified value.  If it is a PHI, and
  61 // if it's recognizable, classify it and fill in instance variables.
  62 //
  63 InductionVariable::InductionVariable(PHINode *P, cfg::LoopInfo *LoopInfo) {
  64   InductionType = Unknown;     // Assume the worst
  65   Phi = P;
  66
  67   // If the PHI node has more than two predecessors, we don't know how to
  68   // handle it.
  69   //
  70   if (Phi->getNumIncomingValues() != 2) return;
  71
  72   // FIXME: Handle FP induction variables.
  73   if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy)
  74     return;
  75
  76   // If we have loop information, make sure that this PHI node is in the header
  77   // of a loop...
  78   //
  79   const cfg::Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
  80   if (L && L->getHeader() != Phi->getParent())
  81     return;
  82
  83   Value *V1 = Phi->getIncomingValue(0);
  84   Value *V2 = Phi->getIncomingValue(1);
  85
  86   if (L == 0) {  // No loop information?  Base everything on expression analysis
  87     ExprType E1 = analysis::ClassifyExpression(V1);
  88     ExprType E2 = analysis::ClassifyExpression(V2);
  89
  90     if (E1.ExprTy > E2.ExprTy)        // Make E1 be the simpler expression
  91       std::swap(E1, E2);
  92
  93     // E1 must be a constant incoming value, and E2 must be a linear expression
  94     // with respect to the PHI node.
  95     //
  96     if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
  97         E2.Var != Phi)
  98       return;
  99
 100     // Okay, we have found an induction variable. Save the start and step values
 101     const Type *ETy = Phi->getType();
 102     if (ETy->isPointerType()) ETy = Type::ULongTy;
 103
 104     Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0));
 105     Step  = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0));
 106   } else {
 107     // Okay, at this point, we know that we have loop information...
 108
 109     // Make sure that V1 is the incoming value, and V2 is from the backedge of
 110     // the loop.
 111     if (L->contains(Phi->getIncomingBlock(0)))     // Wrong order.  Swap now.
 112       std::swap(V1, V2);
 113
 114     Start = V1;     // We know that Start has to be loop invariant...
 115     Step = 0;
 116
 117     if (V2 == Phi) {  // referencing the PHI directly?  Must have zero step
 118       Step = Constant::getNullConstant(Phi->getType());
 119     } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
 120       // TODO: This could be much better...
 121       if (I->getOpcode() == Instruction::Add) {
 122         if (I->getOperand(0) == Phi)
 123           Step = I->getOperand(1);
 124         else if (I->getOperand(1) == Phi)
 125           Step = I->getOperand(0);
 126       }
 127     }
 128
 129     if (Step == 0) {                  // Unrecognized step value...
 130       ExprType StepE = analysis::ClassifyExpression(V2);
 131       if (StepE.ExprTy != ExprType::Linear ||
 132           StepE.Var != Phi) return;
 133
 134       const Type *ETy = Phi->getType();
 135       if (ETy->isPointerType()) ETy = Type::ULongTy;
 136       Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
 137     } else {   // We were able to get a step value, simplify with expr analysis
 138       ExprType StepE = analysis::ClassifyExpression(Step);
 139       if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
 140         // No offset from variable?  Grab the variable
 141         Step = StepE.Var;
 142       } else if (StepE.ExprTy == ExprType::Constant) {
 143         if (StepE.Offset)
 144           Step = (Value*)StepE.Offset;
 145         else
 146           Step = Constant::getNullConstant(Step->getType());
 147         const Type *ETy = Phi->getType();
 148         if (ETy->isPointerType()) ETy = Type::ULongTy;
 149         Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0));
 150       }
 151     }
 152   }
 153
 154   // Classify the induction variable type now...
 155   InductionType = InductionVariable::Classify(Start, Step, L);
 156 }