lib/Analysis/InductionVariable.cpp

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