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/BasicBlock.h"
  23 #include "llvm/iPHINode.h"
  24 #include "llvm/iOperators.h"
  25 #include "llvm/iTerminators.h"
  26 #include "llvm/Type.h"
  27 #include "llvm/Constants.h"
  28 #include "llvm/Support/CFG.h"
  29 #include "llvm/Assembly/Writer.h"
  30 #include "Support/Statistic.h"
  31
  32 static bool isLoopInvariant(const Value *V, const Loop *L) {
  33   if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
  34     return true;
  35
  36   const Instruction *I = cast<Instruction>(V);
  37   const BasicBlock *BB = I->getParent();
  38
  39   return !L->contains(BB);
  40 }
  41
  42 enum InductionVariable::iType
  43 InductionVariable::Classify(const Value *Start, const Value *Step,
  44                             const Loop *L) {
  45   // Check for cannonical and simple linear expressions now...
  46   if (const ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
  47     if (const ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
  48       if (CStart->equalsInt(0) && CStep->equalsInt(1))
  49         return Cannonical;
  50       else
  51         return SimpleLinear;
  52     }
  53
  54   // Without loop information, we cannot do any better, so bail now...
  55   if (L == 0) return Unknown;
  56
  57   if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
  58     return Linear;
  59   return Unknown;
  60 }
  61
  62 // Create an induction variable for the specified value.  If it is a PHI, and
  63 // if it's recognizable, classify it and fill in instance variables.
  64 //
  65 InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
  66   InductionType = Unknown;     // Assume the worst
  67   Phi = P;
  68
  69   // If the PHI node has more than two predecessors, we don't know how to
  70   // handle it.
  71   //
  72   if (Phi->getNumIncomingValues() != 2) return;
  73
  74   // FIXME: Handle FP induction variables.
  75   if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy)
  76     return;
  77
  78   // If we have loop information, make sure that this PHI node is in the header
  79   // of a loop...
  80   //
  81   const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
  82   if (L && L->getHeader() != Phi->getParent())
  83     return;
  84
  85   Value *V1 = Phi->getIncomingValue(0);
  86   Value *V2 = Phi->getIncomingValue(1);
  87
  88   if (L == 0) {  // No loop information?  Base everything on expression analysis
  89     ExprType E1 = ClassifyExpression(V1);
  90     ExprType E2 = ClassifyExpression(V2);
  91
  92     if (E1.ExprTy > E2.ExprTy)        // Make E1 be the simpler expression
  93       std::swap(E1, E2);
  94
  95     // E1 must be a constant incoming value, and E2 must be a linear expression
  96     // with respect to the PHI node.
  97     //
  98     if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
  99         E2.Var != Phi)
 100       return;
 101
 102     // Okay, we have found an induction variable. Save the start and step values
 103     const Type *ETy = Phi->getType();
 104     if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 105
 106     Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0));
 107     Step  = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0));
 108   } else {
 109     // Okay, at this point, we know that we have loop information...
 110
 111     // Make sure that V1 is the incoming value, and V2 is from the backedge of
 112     // the loop.
 113     if (L->contains(Phi->getIncomingBlock(0)))     // Wrong order.  Swap now.
 114       std::swap(V1, V2);
 115
 116     Start = V1;     // We know that Start has to be loop invariant...
 117     Step = 0;
 118
 119     if (V2 == Phi) {  // referencing the PHI directly?  Must have zero step
 120       Step = Constant::getNullValue(Phi->getType());
 121     } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
 122       // TODO: This could be much better...
 123       if (I->getOpcode() == Instruction::Add) {
 124         if (I->getOperand(0) == Phi)
 125           Step = I->getOperand(1);
 126         else if (I->getOperand(1) == Phi)
 127           Step = I->getOperand(0);
 128       }
 129     }
 130
 131     if (Step == 0) {                  // Unrecognized step value...
 132       ExprType StepE = ClassifyExpression(V2);
 133       if (StepE.ExprTy != ExprType::Linear ||
 134           StepE.Var != Phi) return;
 135
 136       const Type *ETy = Phi->getType();
 137       if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 138       Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
 139     } else {   // We were able to get a step value, simplify with expr analysis
 140       ExprType StepE = ClassifyExpression(Step);
 141       if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
 142         // No offset from variable?  Grab the variable
 143         Step = StepE.Var;
 144       } else if (StepE.ExprTy == ExprType::Constant) {
 145         if (StepE.Offset)
 146           Step = (Value*)StepE.Offset;
 147         else
 148           Step = Constant::getNullValue(Step->getType());
 149         const Type *ETy = Phi->getType();
 150         if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
 151         Step  = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0));
 152       }
 153     }
 154   }
 155
 156   // Classify the induction variable type now...
 157   InductionType = InductionVariable::Classify(Start, Step, L);
 158 }
 159
 160
 161 Value* InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
 162   DEBUG(std::cerr << "entering getExecutionCount\n");
 163
 164   // Don't recompute if already available
 165   if (End) {
 166     DEBUG(std::cerr << "returning cached End value.\n");
 167     return End;
 168   }
 169
 170   const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
 171   if (!L) {
 172     DEBUG(std::cerr << "null loop. oops\n");
 173     return NULL;
 174   }
 175
 176   // >1 backedge => cannot predict number of iterations
 177   if (Phi->getNumIncomingValues() != 2) {
 178     DEBUG(std::cerr << ">2 incoming values. oops\n");
 179     return NULL;
 180   }
 181
 182   // Find final node: predecesor of the loop header that's also an exit
 183   BasicBlock *terminator = 0;
 184   BasicBlock *header = L->getHeader();
 185   for (pred_iterator PI = pred_begin(header), PE = pred_end(header);
 186        PI != PE; ++PI) {
 187     if (L->isLoopExit(*PI)) {
 188       terminator = *PI;
 189       break;
 190     }
 191   }
 192
 193   // Break in the loop => cannot predict number of iterations
 194   // break: any block which is an exit node whose successor is not in loop,
 195   // and this block is not marked as the terminator
 196   //
 197   const std::vector<BasicBlock*> &blocks = L->getBlocks();
 198   for (std::vector<BasicBlock*>::const_iterator i = blocks.begin(), e = blocks.end();
 199        i != e; ++i) {
 200     if (L->isLoopExit(*i) && (*i != terminator)) {
 201       for (succ_iterator SI = succ_begin(*i), SE = succ_end(*i); SI != SE; ++SI) {
 202         if (! L->contains(*SI)) {
 203           DEBUG(std::cerr << "break found in loop");
 204           return NULL;
 205         }
 206       }
 207     }
 208   }
 209
 210   BranchInst *B = dyn_cast<BranchInst>(terminator->getTerminator());
 211   if (!B) {
 212     // this really should not happen
 213     DEBUG(std::cerr << "no terminator instruction!");
 214     return NULL;
 215   }
 216   SetCondInst *SCI = dyn_cast<SetCondInst>(&*B->getCondition());
 217
 218   if (SCI && InductionType == Cannonical) {
 219     DEBUG(std::cerr << "sci:" << *SCI);
 220     Value *condVal0 = SCI->getOperand(0);
 221     Value *condVal1 = SCI->getOperand(1);
 222     Value *indVar = 0;
 223
 224     // the induction variable is the one coming from the backedge
 225     if (L->contains(Phi->getIncomingBlock(0))) {
 226       indVar = Phi->getIncomingValue(0);
 227     } else {
 228       indVar = Phi->getIncomingValue(1);
 229     }
 230
 231     // check to see if indVar is one of the parameters in SCI
 232     // and if the other is loop-invariant, it is the UB
 233     if (indVar == condVal0) {
 234       if (isLoopInvariant(condVal1, L)) {
 235         End = condVal1;
 236       } else {
 237         DEBUG(std::cerr << "not loop invariant 1\n");
 238       }
 239     } else if (indVar == condVal1) {
 240       if (isLoopInvariant(condVal0, L)) {
 241         End = condVal0;
 242       } else {
 243         DEBUG(std::cerr << "not loop invariant 0\n");
 244       }
 245     }
 246
 247     if (End) {
 248       switch (SCI->getOpcode()) {
 249       case Instruction::SetLT:
 250       case Instruction::SetNE: break; // already done
 251       case Instruction::SetLE: {
 252         // if compared to a constant int N, then predict N+1 iterations
 253         if (ConstantSInt *ubSigned = dyn_cast<ConstantSInt>(End)) {
 254           End = ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1);
 255           DEBUG(std::cerr << "signed int constant\n");
 256         } else if (ConstantUInt *ubUnsigned = dyn_cast<ConstantUInt>(End)) {
 257           End = ConstantUInt::get(ubUnsigned->getType(), ubUnsigned->getValue()+1);
 258           DEBUG(std::cerr << "unsigned int constant\n");
 259         } else {
 260           DEBUG(std::cerr << "symbolic bound\n");
 261           //End = NULL;
 262           // new expression N+1
 263           End = BinaryOperator::create(Instruction::Add, End,
 264                                        ConstantUInt::get(ubUnsigned->getType(), 1));
 265         }
 266         break;
 267       }
 268       default: End = NULL; // cannot predict
 269       }
 270     }
 271     return End;
 272   } else {
 273     DEBUG(std::cerr << "SCI null or non-cannonical ind var\n");
 274   }
 275   return NULL;
 276 }
 277
 278
 279 void InductionVariable::print(std::ostream &o) const {
 280   switch (InductionType) {
 281   case InductionVariable::Cannonical:   o << "Cannonical ";   break;
 282   case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
 283   case InductionVariable::Linear:       o << "Linear ";       break;
 284   case InductionVariable::Unknown:      o << "Unrecognized "; break;
 285   }
 286   o << "Induction Variable: ";
 287   if (Phi) {
 288     WriteAsOperand(o, Phi);
 289     o << ":\n" << Phi;
 290   } else {
 291     o << "\n";
 292   }
 293   if (InductionType == InductionVariable::Unknown) return;
 294
 295   o << "  Start = "; WriteAsOperand(o, Start);
 296   o << "  Step = " ; WriteAsOperand(o, Step);
 297   if (End) {
 298     o << "  End = " ; WriteAsOperand(o, End);
 299   }
 300   o << "\n";
 301 }