lib/Analysis/InductionVariable.cpp

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