lib/Analysis/ScalarEvolution.cpp

   1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the implementation of the scalar evolution analysis
  11 // engine, which is used primarily to analyze expressions involving induction
  12 // variables in loops.
  13 //
  14 // There are several aspects to this library.  First is the representation of
  15 // scalar expressions, which are represented as subclasses of the SCEV class.
  16 // These classes are used to represent certain types of subexpressions that we
  17 // can handle. We only create one SCEV of a particular shape, so
  18 // pointer-comparisons for equality are legal.
  19 //
  20 // One important aspect of the SCEV objects is that they are never cyclic, even
  21 // if there is a cycle in the dataflow for an expression (ie, a PHI node).  If
  22 // the PHI node is one of the idioms that we can represent (e.g., a polynomial
  23 // recurrence) then we represent it directly as a recurrence node, otherwise we
  24 // represent it as a SCEVUnknown node.
  25 //
  26 // In addition to being able to represent expressions of various types, we also
  27 // have folders that are used to build the *canonical* representation for a
  28 // particular expression.  These folders are capable of using a variety of
  29 // rewrite rules to simplify the expressions.
  30 //
  31 // Once the folders are defined, we can implement the more interesting
  32 // higher-level code, such as the code that recognizes PHI nodes of various
  33 // types, computes the execution count of a loop, etc.
  34 //
  35 // TODO: We should use these routines and value representations to implement
  36 // dependence analysis!
  37 //
  38 //===----------------------------------------------------------------------===//
  39 //
  40 // There are several good references for the techniques used in this analysis.
  41 //
  42 //  Chains of recurrences -- a method to expedite the evaluation
  43 //  of closed-form functions
  44 //  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
  45 //
  46 //  On computational properties of chains of recurrences
  47 //  Eugene V. Zima
  48 //
  49 //  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
  50 //  Robert A. van Engelen
  51 //
  52 //  Efficient Symbolic Analysis for Optimizing Compilers
  53 //  Robert A. van Engelen
  54 //
  55 //  Using the chains of recurrences algebra for data dependence testing and
  56 //  induction variable substitution
  57 //  MS Thesis, Johnie Birch
  58 //
  59 //===----------------------------------------------------------------------===//
  60
  61 #define DEBUG_TYPE "scalar-evolution"
  62 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  63 #include "llvm/Constants.h"
  64 #include "llvm/DerivedTypes.h"
  65 #include "llvm/GlobalVariable.h"
  66 #include "llvm/GlobalAlias.h"
  67 #include "llvm/Instructions.h"
  68 #include "llvm/LLVMContext.h"
  69 #include "llvm/Operator.h"
  70 #include "llvm/Analysis/ConstantFolding.h"
  71 #include "llvm/Analysis/Dominators.h"
  72 #include "llvm/Analysis/LoopInfo.h"
  73 #include "llvm/Analysis/ValueTracking.h"
  74 #include "llvm/Assembly/Writer.h"
  75 #include "llvm/Target/TargetData.h"
  76 #include "llvm/Support/CommandLine.h"
  77 #include "llvm/Support/ConstantRange.h"
  78 #include "llvm/Support/Debug.h"
  79 #include "llvm/Support/ErrorHandling.h"
  80 #include "llvm/Support/GetElementPtrTypeIterator.h"
  81 #include "llvm/Support/InstIterator.h"
  82 #include "llvm/Support/MathExtras.h"
  83 #include "llvm/Support/raw_ostream.h"
  84 #include "llvm/ADT/Statistic.h"
  85 #include "llvm/ADT/STLExtras.h"
  86 #include "llvm/ADT/SmallPtrSet.h"
  87 #include <algorithm>
  88 using namespace llvm;
  89
  90 STATISTIC(NumArrayLenItCounts,
  91           "Number of trip counts computed with array length");
  92 STATISTIC(NumTripCountsComputed,
  93           "Number of loops with predictable loop counts");
  94 STATISTIC(NumTripCountsNotComputed,
  95           "Number of loops without predictable loop counts");
  96 STATISTIC(NumBruteForceTripCountsComputed,
  97           "Number of loops with trip counts computed by force");
  98
  99 static cl::opt<unsigned>
 100 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
 101                         cl::desc("Maximum number of iterations SCEV will "
 102                                  "symbolically execute a constant "
 103                                  "derived loop"),
 104                         cl::init(100));
 105
 106 static RegisterPass<ScalarEvolution>
 107 R("scalar-evolution", "Scalar Evolution Analysis", false, true);
 108 char ScalarEvolution::ID = 0;
 109
 110 //===----------------------------------------------------------------------===//
 111 //                           SCEV class definitions
 112 //===----------------------------------------------------------------------===//
 113
 114 //===----------------------------------------------------------------------===//
 115 // Implementation of the SCEV class.
 116 //
 117
 118 SCEV::~SCEV() {}
 119
 120 void SCEV::dump() const {
 121   print(dbgs());
 122   dbgs() << '\n';
 123 }
 124
 125 bool SCEV::isZero() const {
 126   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
 127     return SC->getValue()->isZero();
 128   return false;
 129 }
 130
 131 bool SCEV::isOne() const {
 132   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
 133     return SC->getValue()->isOne();
 134   return false;
 135 }
 136
 137 bool SCEV::isAllOnesValue() const {
 138   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
 139     return SC->getValue()->isAllOnesValue();
 140   return false;
 141 }
 142
 143 SCEVCouldNotCompute::SCEVCouldNotCompute() :
 144   SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
 145
 146 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
 147   llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
 148   return false;
 149 }
 150
 151 const Type *SCEVCouldNotCompute::getType() const {
 152   llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
 153   return 0;
 154 }
 155
 156 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
 157   llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
 158   return false;
 159 }
 160
 161 bool SCEVCouldNotCompute::hasOperand(const SCEV *) const {
 162   llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
 163   return false;
 164 }
 165
 166 void SCEVCouldNotCompute::print(raw_ostream &OS) const {
 167   OS << "***COULDNOTCOMPUTE***";
 168 }
 169
 170 bool SCEVCouldNotCompute::classof(const SCEV *S) {
 171   return S->getSCEVType() == scCouldNotCompute;
 172 }
 173
 174 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
 175   FoldingSetNodeID ID;
 176   ID.AddInteger(scConstant);
 177   ID.AddPointer(V);
 178   void *IP = 0;
 179   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 180   SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V);
 181   UniqueSCEVs.InsertNode(S, IP);
 182   return S;
 183 }
 184
 185 const SCEV *ScalarEvolution::getConstant(const APInt& Val) {
 186   return getConstant(ConstantInt::get(getContext(), Val));
 187 }
 188
 189 const SCEV *
 190 ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
 191   const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
 192   return getConstant(ConstantInt::get(ITy, V, isSigned));
 193 }
 194
 195 const Type *SCEVConstant::getType() const { return V->getType(); }
 196
 197 void SCEVConstant::print(raw_ostream &OS) const {
 198   WriteAsOperand(OS, V, false);
 199 }
 200
 201 SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
 202                            unsigned SCEVTy, const SCEV *op, const Type *ty)
 203   : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
 204
 205 bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 206   return Op->dominates(BB, DT);
 207 }
 208
 209 bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 210   return Op->properlyDominates(BB, DT);
 211 }
 212
 213 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
 214                                    const SCEV *op, const Type *ty)
 215   : SCEVCastExpr(ID, scTruncate, op, ty) {
 216   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
 217          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
 218          "Cannot truncate non-integer value!");
 219 }
 220
 221 void SCEVTruncateExpr::print(raw_ostream &OS) const {
 222   OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 223 }
 224
 225 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
 226                                        const SCEV *op, const Type *ty)
 227   : SCEVCastExpr(ID, scZeroExtend, op, ty) {
 228   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
 229          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
 230          "Cannot zero extend non-integer value!");
 231 }
 232
 233 void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
 234   OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 235 }
 236
 237 SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
 238                                        const SCEV *op, const Type *ty)
 239   : SCEVCastExpr(ID, scSignExtend, op, ty) {
 240   assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) &&
 241          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
 242          "Cannot sign extend non-integer value!");
 243 }
 244
 245 void SCEVSignExtendExpr::print(raw_ostream &OS) const {
 246   OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 247 }
 248
 249 void SCEVCommutativeExpr::print(raw_ostream &OS) const {
 250   const char *OpStr = getOperationStr();
 251   OS << "(";
 252   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) {
 253     OS << **I;
 254     if (next(I) != E)
 255       OS << OpStr;
 256   }
 257   OS << ")";
 258 }
 259
 260 bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 261   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 262     if (!getOperand(i)->dominates(BB, DT))
 263       return false;
 264   }
 265   return true;
 266 }
 267
 268 bool SCEVNAryExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 269   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 270     if (!getOperand(i)->properlyDominates(BB, DT))
 271       return false;
 272   }
 273   return true;
 274 }
 275
 276 bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 277   return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
 278 }
 279
 280 bool SCEVUDivExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 281   return LHS->properlyDominates(BB, DT) && RHS->properlyDominates(BB, DT);
 282 }
 283
 284 void SCEVUDivExpr::print(raw_ostream &OS) const {
 285   OS << "(" << *LHS << " /u " << *RHS << ")";
 286 }
 287
 288 const Type *SCEVUDivExpr::getType() const {
 289   // In most cases the types of LHS and RHS will be the same, but in some
 290   // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
 291   // depend on the type for correctness, but handling types carefully can
 292   // avoid extra casts in the SCEVExpander. The LHS is more likely to be
 293   // a pointer type than the RHS, so use the RHS' type here.
 294   return RHS->getType();
 295 }
 296
 297 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
 298   // Add recurrences are never invariant in the function-body (null loop).
 299   if (!QueryLoop)
 300     return false;
 301
 302   // This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L.
 303   if (QueryLoop->contains(L))
 304     return false;
 305
 306   // This recurrence is variant w.r.t. QueryLoop if any of its operands
 307   // are variant.
 308   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 309     if (!getOperand(i)->isLoopInvariant(QueryLoop))
 310       return false;
 311
 312   // Otherwise it's loop-invariant.
 313   return true;
 314 }
 315
 316 bool
 317 SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 318   return DT->dominates(L->getHeader(), BB) &&
 319          SCEVNAryExpr::dominates(BB, DT);
 320 }
 321
 322 bool
 323 SCEVAddRecExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 324   // This uses a "dominates" query instead of "properly dominates" query because
 325   // the instruction which produces the addrec's value is a PHI, and a PHI
 326   // effectively properly dominates its entire containing block.
 327   return DT->dominates(L->getHeader(), BB) &&
 328          SCEVNAryExpr::properlyDominates(BB, DT);
 329 }
 330
 331 void SCEVAddRecExpr::print(raw_ostream &OS) const {
 332   OS << "{" << *Operands[0];
 333   for (unsigned i = 1, e = NumOperands; i != e; ++i)
 334     OS << ",+," << *Operands[i];
 335   OS << "}<";
 336   WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
 337   OS << ">";
 338 }
 339
 340 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
 341   // All non-instruction values are loop invariant.  All instructions are loop
 342   // invariant if they are not contained in the specified loop.
 343   // Instructions are never considered invariant in the function body
 344   // (null loop) because they are defined within the "loop".
 345   if (Instruction *I = dyn_cast<Instruction>(V))
 346     return L && !L->contains(I);
 347   return true;
 348 }
 349
 350 bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const {
 351   if (Instruction *I = dyn_cast<Instruction>(getValue()))
 352     return DT->dominates(I->getParent(), BB);
 353   return true;
 354 }
 355
 356 bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const {
 357   if (Instruction *I = dyn_cast<Instruction>(getValue()))
 358     return DT->properlyDominates(I->getParent(), BB);
 359   return true;
 360 }
 361
 362 const Type *SCEVUnknown::getType() const {
 363   return V->getType();
 364 }
 365
 366 bool SCEVUnknown::isSizeOf(const Type *&AllocTy) const {
 367   if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
 368     if (VCE->getOpcode() == Instruction::PtrToInt)
 369       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
 370         if (CE->getOpcode() == Instruction::GetElementPtr &&
 371             CE->getOperand(0)->isNullValue() &&
 372             CE->getNumOperands() == 2)
 373           if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(1)))
 374             if (CI->isOne()) {
 375               AllocTy = cast<PointerType>(CE->getOperand(0)->getType())
 376                                  ->getElementType();
 377               return true;
 378             }
 379
 380   return false;
 381 }
 382
 383 bool SCEVUnknown::isAlignOf(const Type *&AllocTy) const {
 384   if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
 385     if (VCE->getOpcode() == Instruction::PtrToInt)
 386       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
 387         if (CE->getOpcode() == Instruction::GetElementPtr &&
 388             CE->getOperand(0)->isNullValue()) {
 389           const Type *Ty =
 390             cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
 391           if (const StructType *STy = dyn_cast<StructType>(Ty))
 392             if (!STy->isPacked() &&
 393                 CE->getNumOperands() == 3 &&
 394                 CE->getOperand(1)->isNullValue()) {
 395               if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(2)))
 396                 if (CI->isOne() &&
 397                     STy->getNumElements() == 2 &&
 398                     STy->getElementType(0)->isIntegerTy(1)) {
 399                   AllocTy = STy->getElementType(1);
 400                   return true;
 401                 }
 402             }
 403         }
 404
 405   return false;
 406 }
 407
 408 bool SCEVUnknown::isOffsetOf(const Type *&CTy, Constant *&FieldNo) const {
 409   if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(V))
 410     if (VCE->getOpcode() == Instruction::PtrToInt)
 411       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
 412         if (CE->getOpcode() == Instruction::GetElementPtr &&
 413             CE->getNumOperands() == 3 &&
 414             CE->getOperand(0)->isNullValue() &&
 415             CE->getOperand(1)->isNullValue()) {
 416           const Type *Ty =
 417             cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
 418           // Ignore vector types here so that ScalarEvolutionExpander doesn't
 419           // emit getelementptrs that index into vectors.
 420           if (Ty->isStructTy() || Ty->isArrayTy()) {
 421             CTy = Ty;
 422             FieldNo = CE->getOperand(2);
 423             return true;
 424           }
 425         }
 426
 427   return false;
 428 }
 429
 430 void SCEVUnknown::print(raw_ostream &OS) const {
 431   const Type *AllocTy;
 432   if (isSizeOf(AllocTy)) {
 433     OS << "sizeof(" << *AllocTy << ")";
 434     return;
 435   }
 436   if (isAlignOf(AllocTy)) {
 437     OS << "alignof(" << *AllocTy << ")";
 438     return;
 439   }
 440
 441   const Type *CTy;
 442   Constant *FieldNo;
 443   if (isOffsetOf(CTy, FieldNo)) {
 444     OS << "offsetof(" << *CTy << ", ";
 445     WriteAsOperand(OS, FieldNo, false);
 446     OS << ")";
 447     return;
 448   }
 449
 450   // Otherwise just print it normally.
 451   WriteAsOperand(OS, V, false);
 452 }
 453
 454 //===----------------------------------------------------------------------===//
 455 //                               SCEV Utilities
 456 //===----------------------------------------------------------------------===//
 457
 458 static bool CompareTypes(const Type *A, const Type *B) {
 459   if (A->getTypeID() != B->getTypeID())
 460     return A->getTypeID() < B->getTypeID();
 461   if (const IntegerType *AI = dyn_cast<IntegerType>(A)) {
 462     const IntegerType *BI = cast<IntegerType>(B);
 463     return AI->getBitWidth() < BI->getBitWidth();
 464   }
 465   if (const PointerType *AI = dyn_cast<PointerType>(A)) {
 466     const PointerType *BI = cast<PointerType>(B);
 467     return CompareTypes(AI->getElementType(), BI->getElementType());
 468   }
 469   if (const ArrayType *AI = dyn_cast<ArrayType>(A)) {
 470     const ArrayType *BI = cast<ArrayType>(B);
 471     if (AI->getNumElements() != BI->getNumElements())
 472       return AI->getNumElements() < BI->getNumElements();
 473     return CompareTypes(AI->getElementType(), BI->getElementType());
 474   }
 475   if (const VectorType *AI = dyn_cast<VectorType>(A)) {
 476     const VectorType *BI = cast<VectorType>(B);
 477     if (AI->getNumElements() != BI->getNumElements())
 478       return AI->getNumElements() < BI->getNumElements();
 479     return CompareTypes(AI->getElementType(), BI->getElementType());
 480   }
 481   if (const StructType *AI = dyn_cast<StructType>(A)) {
 482     const StructType *BI = cast<StructType>(B);
 483     if (AI->getNumElements() != BI->getNumElements())
 484       return AI->getNumElements() < BI->getNumElements();
 485     for (unsigned i = 0, e = AI->getNumElements(); i != e; ++i)
 486       if (CompareTypes(AI->getElementType(i), BI->getElementType(i)) ||
 487           CompareTypes(BI->getElementType(i), AI->getElementType(i)))
 488         return CompareTypes(AI->getElementType(i), BI->getElementType(i));
 489   }
 490   return false;
 491 }
 492
 493 namespace {
 494   /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
 495   /// than the complexity of the RHS.  This comparator is used to canonicalize
 496   /// expressions.
 497   class SCEVComplexityCompare {
 498     LoopInfo *LI;
 499   public:
 500     explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
 501
 502     bool operator()(const SCEV *LHS, const SCEV *RHS) const {
 503       // Fast-path: SCEVs are uniqued so we can do a quick equality check.
 504       if (LHS == RHS)
 505         return false;
 506
 507       // Primarily, sort the SCEVs by their getSCEVType().
 508       if (LHS->getSCEVType() != RHS->getSCEVType())
 509         return LHS->getSCEVType() < RHS->getSCEVType();
 510
 511       // Then, pick an arbitrary sort. Use the profiling data for speed.
 512       const FoldingSetNodeIDRef &L = LHS->getProfile();
 513       const FoldingSetNodeIDRef &R = RHS->getProfile();
 514       size_t LSize = L.getSize();
 515       size_t RSize = R.getSize();
 516       if (LSize != RSize)
 517         return LSize < RSize;
 518       return memcmp(L.getData(), R.getData(),
 519                     LSize * sizeof(*L.getData())) < 0;
 520     }
 521   };
 522 }
 523
 524 /// GroupByComplexity - Given a list of SCEV objects, order them by their
 525 /// complexity, and group objects of the same complexity together by value.
 526 /// When this routine is finished, we know that any duplicates in the vector are
 527 /// consecutive and that complexity is monotonically increasing.
 528 ///
 529 /// Note that we go take special precautions to ensure that we get deterministic
 530 /// results from this routine.  In other words, we don't want the results of
 531 /// this to depend on where the addresses of various SCEV objects happened to
 532 /// land in memory.
 533 ///
 534 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
 535                               LoopInfo *LI) {
 536   if (Ops.size() < 2) return;  // Noop
 537
 538   SCEVComplexityCompare Comp(LI);
 539
 540   if (Ops.size() == 2) {
 541     // This is the common case, which also happens to be trivially simple.
 542     // Special case it.
 543     if (Comp(Ops[1], Ops[0]))
 544       std::swap(Ops[0], Ops[1]);
 545     return;
 546   }
 547
 548   std::stable_sort(Ops.begin(), Ops.end(), Comp);
 549 }
 550
 551
 552
 553 //===----------------------------------------------------------------------===//
 554 //                      Simple SCEV method implementations
 555 //===----------------------------------------------------------------------===//
 556
 557 /// BinomialCoefficient - Compute BC(It, K).  The result has width W.
 558 /// Assume, K > 0.
 559 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
 560                                        ScalarEvolution &SE,
 561                                        const Type* ResultTy) {
 562   // Handle the simplest case efficiently.
 563   if (K == 1)
 564     return SE.getTruncateOrZeroExtend(It, ResultTy);
 565
 566   // We are using the following formula for BC(It, K):
 567   //
 568   //   BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
 569   //
 570   // Suppose, W is the bitwidth of the return value.  We must be prepared for
 571   // overflow.  Hence, we must assure that the result of our computation is
 572   // equal to the accurate one modulo 2^W.  Unfortunately, division isn't
 573   // safe in modular arithmetic.
 574   //
 575   // However, this code doesn't use exactly that formula; the formula it uses
 576   // is something like the following, where T is the number of factors of 2 in
 577   // K! (i.e. trailing zeros in the binary representation of K!), and ^ is
 578   // exponentiation:
 579   //
 580   //   BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T)
 581   //
 582   // This formula is trivially equivalent to the previous formula.  However,
 583   // this formula can be implemented much more efficiently.  The trick is that
 584   // K! / 2^T is odd, and exact division by an odd number *is* safe in modular
 585   // arithmetic.  To do exact division in modular arithmetic, all we have
 586   // to do is multiply by the inverse.  Therefore, this step can be done at
 587   // width W.
 588   //
 589   // The next issue is how to safely do the division by 2^T.  The way this
 590   // is done is by doing the multiplication step at a width of at least W + T
 591   // bits.  This way, the bottom W+T bits of the product are accurate. Then,
 592   // when we perform the division by 2^T (which is equivalent to a right shift
 593   // by T), the bottom W bits are accurate.  Extra bits are okay; they'll get
 594   // truncated out after the division by 2^T.
 595   //
 596   // In comparison to just directly using the first formula, this technique
 597   // is much more efficient; using the first formula requires W * K bits,
 598   // but this formula less than W + K bits. Also, the first formula requires
 599   // a division step, whereas this formula only requires multiplies and shifts.
 600   //
 601   // It doesn't matter whether the subtraction step is done in the calculation
 602   // width or the input iteration count's width; if the subtraction overflows,
 603   // the result must be zero anyway.  We prefer here to do it in the width of
 604   // the induction variable because it helps a lot for certain cases; CodeGen
 605   // isn't smart enough to ignore the overflow, which leads to much less
 606   // efficient code if the width of the subtraction is wider than the native
 607   // register width.
 608   //
 609   // (It's possible to not widen at all by pulling out factors of 2 before
 610   // the multiplication; for example, K=2 can be calculated as
 611   // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires
 612   // extra arithmetic, so it's not an obvious win, and it gets
 613   // much more complicated for K > 3.)
 614
 615   // Protection from insane SCEVs; this bound is conservative,
 616   // but it probably doesn't matter.
 617   if (K > 1000)
 618     return SE.getCouldNotCompute();
 619
 620   unsigned W = SE.getTypeSizeInBits(ResultTy);
 621
 622   // Calculate K! / 2^T and T; we divide out the factors of two before
 623   // multiplying for calculating K! / 2^T to avoid overflow.
 624   // Other overflow doesn't matter because we only care about the bottom
 625   // W bits of the result.
 626   APInt OddFactorial(W, 1);
 627   unsigned T = 1;
 628   for (unsigned i = 3; i <= K; ++i) {
 629     APInt Mult(W, i);
 630     unsigned TwoFactors = Mult.countTrailingZeros();
 631     T += TwoFactors;
 632     Mult = Mult.lshr(TwoFactors);
 633     OddFactorial *= Mult;
 634   }
 635
 636   // We need at least W + T bits for the multiplication step
 637   unsigned CalculationBits = W + T;
 638
 639   // Calculate 2^T, at width T+W.
 640   APInt DivFactor = APInt(CalculationBits, 1).shl(T);
 641
 642   // Calculate the multiplicative inverse of K! / 2^T;
 643   // this multiplication factor will perform the exact division by
 644   // K! / 2^T.
 645   APInt Mod = APInt::getSignedMinValue(W+1);
 646   APInt MultiplyFactor = OddFactorial.zext(W+1);
 647   MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod);
 648   MultiplyFactor = MultiplyFactor.trunc(W);
 649
 650   // Calculate the product, at width T+W
 651   const IntegerType *CalculationTy = IntegerType::get(SE.getContext(),
 652                                                       CalculationBits);
 653   const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
 654   for (unsigned i = 1; i != K; ++i) {
 655     const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i));
 656     Dividend = SE.getMulExpr(Dividend,
 657                              SE.getTruncateOrZeroExtend(S, CalculationTy));
 658   }
 659
 660   // Divide by 2^T
 661   const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
 662
 663   // Truncate the result, and divide by K! / 2^T.
 664
 665   return SE.getMulExpr(SE.getConstant(MultiplyFactor),
 666                        SE.getTruncateOrZeroExtend(DivResult, ResultTy));
 667 }
 668
 669 /// evaluateAtIteration - Return the value of this chain of recurrences at
 670 /// the specified iteration number.  We can evaluate this recurrence by
 671 /// multiplying each element in the chain by the binomial coefficient
 672 /// corresponding to it.  In other words, we can evaluate {A,+,B,+,C,+,D} as:
 673 ///
 674 ///   A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
 675 ///
 676 /// where BC(It, k) stands for binomial coefficient.
 677 ///
 678 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
 679                                                 ScalarEvolution &SE) const {
 680   const SCEV *Result = getStart();
 681   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
 682     // The computation is correct in the face of overflow provided that the
 683     // multiplication is performed _after_ the evaluation of the binomial
 684     // coefficient.
 685     const SCEV *Coeff = BinomialCoefficient(It, i, SE, getType());
 686     if (isa<SCEVCouldNotCompute>(Coeff))
 687       return Coeff;
 688
 689     Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
 690   }
 691   return Result;
 692 }
 693
 694 //===----------------------------------------------------------------------===//
 695 //                    SCEV Expression folder implementations
 696 //===----------------------------------------------------------------------===//
 697
 698 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op,
 699                                              const Type *Ty) {
 700   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
 701          "This is not a truncating conversion!");
 702   assert(isSCEVable(Ty) &&
 703          "This is not a conversion to a SCEVable type!");
 704   Ty = getEffectiveSCEVType(Ty);
 705
 706   FoldingSetNodeID ID;
 707   ID.AddInteger(scTruncate);
 708   ID.AddPointer(Op);
 709   ID.AddPointer(Ty);
 710   void *IP = 0;
 711   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 712
 713   // Fold if the operand is constant.
 714   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 715     return getConstant(
 716       cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
 717
 718   // trunc(trunc(x)) --> trunc(x)
 719   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
 720     return getTruncateExpr(ST->getOperand(), Ty);
 721
 722   // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
 723   if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
 724     return getTruncateOrSignExtend(SS->getOperand(), Ty);
 725
 726   // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
 727   if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
 728     return getTruncateOrZeroExtend(SZ->getOperand(), Ty);
 729
 730   // If the input value is a chrec scev, truncate the chrec's operands.
 731   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
 732     SmallVector<const SCEV *, 4> Operands;
 733     for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
 734       Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
 735     return getAddRecExpr(Operands, AddRec->getLoop());
 736   }
 737
 738   // The cast wasn't folded; create an explicit cast node.
 739   // Recompute the insert position, as it may have been invalidated.
 740   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 741   SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
 742                                                  Op, Ty);
 743   UniqueSCEVs.InsertNode(S, IP);
 744   return S;
 745 }
 746
 747 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op,
 748                                                const Type *Ty) {
 749   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
 750          "This is not an extending conversion!");
 751   assert(isSCEVable(Ty) &&
 752          "This is not a conversion to a SCEVable type!");
 753   Ty = getEffectiveSCEVType(Ty);
 754
 755   // Fold if the operand is constant.
 756   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
 757     const Type *IntTy = getEffectiveSCEVType(Ty);
 758     Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
 759     if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
 760     return getConstant(cast<ConstantInt>(C));
 761   }
 762
 763   // zext(zext(x)) --> zext(x)
 764   if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
 765     return getZeroExtendExpr(SZ->getOperand(), Ty);
 766
 767   // Before doing any expensive analysis, check to see if we've already
 768   // computed a SCEV for this Op and Ty.
 769   FoldingSetNodeID ID;
 770   ID.AddInteger(scZeroExtend);
 771   ID.AddPointer(Op);
 772   ID.AddPointer(Ty);
 773   void *IP = 0;
 774   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 775
 776   // If the input value is a chrec scev, and we can prove that the value
 777   // did not overflow the old, smaller, value, we can zero extend all of the
 778   // operands (often constants).  This allows analysis of something like
 779   // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
 780   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
 781     if (AR->isAffine()) {
 782       const SCEV *Start = AR->getStart();
 783       const SCEV *Step = AR->getStepRecurrence(*this);
 784       unsigned BitWidth = getTypeSizeInBits(AR->getType());
 785       const Loop *L = AR->getLoop();
 786
 787       // If we have special knowledge that this addrec won't overflow,
 788       // we don't need to do any further analysis.
 789       if (AR->hasNoUnsignedWrap())
 790         return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 791                              getZeroExtendExpr(Step, Ty),
 792                              L);
 793
 794       // Check whether the backedge-taken count is SCEVCouldNotCompute.
 795       // Note that this serves two purposes: It filters out loops that are
 796       // simply not analyzable, and it covers the case where this code is
 797       // being called from within backedge-taken count analysis, such that
 798       // attempting to ask for the backedge-taken count would likely result
 799       // in infinite recursion. In the later case, the analysis code will
 800       // cope with a conservative value, and it will take care to purge
 801       // that value once it has finished.
 802       const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
 803       if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
 804         // Manually compute the final value for AR, checking for
 805         // overflow.
 806
 807         // Check whether the backedge-taken count can be losslessly casted to
 808         // the addrec's type. The count is always unsigned.
 809         const SCEV *CastedMaxBECount =
 810           getTruncateOrZeroExtend(MaxBECount, Start->getType());
 811         const SCEV *RecastedMaxBECount =
 812           getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
 813         if (MaxBECount == RecastedMaxBECount) {
 814           const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
 815           // Check whether Start+Step*MaxBECount has no unsigned overflow.
 816           const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step);
 817           const SCEV *Add = getAddExpr(Start, ZMul);
 818           const SCEV *OperandExtendedAdd =
 819             getAddExpr(getZeroExtendExpr(Start, WideTy),
 820                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 821                                   getZeroExtendExpr(Step, WideTy)));
 822           if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
 823             // Return the expression with the addrec on the outside.
 824             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 825                                  getZeroExtendExpr(Step, Ty),
 826                                  L);
 827
 828           // Similar to above, only this time treat the step value as signed.
 829           // This covers loops that count down.
 830           const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
 831           Add = getAddExpr(Start, SMul);
 832           OperandExtendedAdd =
 833             getAddExpr(getZeroExtendExpr(Start, WideTy),
 834                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 835                                   getSignExtendExpr(Step, WideTy)));
 836           if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
 837             // Return the expression with the addrec on the outside.
 838             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 839                                  getSignExtendExpr(Step, Ty),
 840                                  L);
 841         }
 842
 843         // If the backedge is guarded by a comparison with the pre-inc value
 844         // the addrec is safe. Also, if the entry is guarded by a comparison
 845         // with the start value and the backedge is guarded by a comparison
 846         // with the post-inc value, the addrec is safe.
 847         if (isKnownPositive(Step)) {
 848           const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
 849                                       getUnsignedRange(Step).getUnsignedMax());
 850           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) ||
 851               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
 852                isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT,
 853                                            AR->getPostIncExpr(*this), N)))
 854             // Return the expression with the addrec on the outside.
 855             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 856                                  getZeroExtendExpr(Step, Ty),
 857                                  L);
 858         } else if (isKnownNegative(Step)) {
 859           const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
 860                                       getSignedRange(Step).getSignedMin());
 861           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
 862               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
 863                isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT,
 864                                            AR->getPostIncExpr(*this), N)))
 865             // Return the expression with the addrec on the outside.
 866             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 867                                  getSignExtendExpr(Step, Ty),
 868                                  L);
 869         }
 870       }
 871     }
 872
 873   // The cast wasn't folded; create an explicit cast node.
 874   // Recompute the insert position, as it may have been invalidated.
 875   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 876   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
 877                                                    Op, Ty);
 878   UniqueSCEVs.InsertNode(S, IP);
 879   return S;
 880 }
 881
 882 const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op,
 883                                                const Type *Ty) {
 884   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
 885          "This is not an extending conversion!");
 886   assert(isSCEVable(Ty) &&
 887          "This is not a conversion to a SCEVable type!");
 888   Ty = getEffectiveSCEVType(Ty);
 889
 890   // Fold if the operand is constant.
 891   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
 892     const Type *IntTy = getEffectiveSCEVType(Ty);
 893     Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
 894     if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
 895     return getConstant(cast<ConstantInt>(C));
 896   }
 897
 898   // sext(sext(x)) --> sext(x)
 899   if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
 900     return getSignExtendExpr(SS->getOperand(), Ty);
 901
 902   // Before doing any expensive analysis, check to see if we've already
 903   // computed a SCEV for this Op and Ty.
 904   FoldingSetNodeID ID;
 905   ID.AddInteger(scSignExtend);
 906   ID.AddPointer(Op);
 907   ID.AddPointer(Ty);
 908   void *IP = 0;
 909   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
 910
 911   // If the input value is a chrec scev, and we can prove that the value
 912   // did not overflow the old, smaller, value, we can sign extend all of the
 913   // operands (often constants).  This allows analysis of something like
 914   // this:  for (signed char X = 0; X < 100; ++X) { int Y = X; }
 915   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
 916     if (AR->isAffine()) {
 917       const SCEV *Start = AR->getStart();
 918       const SCEV *Step = AR->getStepRecurrence(*this);
 919       unsigned BitWidth = getTypeSizeInBits(AR->getType());
 920       const Loop *L = AR->getLoop();
 921
 922       // If we have special knowledge that this addrec won't overflow,
 923       // we don't need to do any further analysis.
 924       if (AR->hasNoSignedWrap())
 925         return getAddRecExpr(getSignExtendExpr(Start, Ty),
 926                              getSignExtendExpr(Step, Ty),
 927                              L);
 928
 929       // Check whether the backedge-taken count is SCEVCouldNotCompute.
 930       // Note that this serves two purposes: It filters out loops that are
 931       // simply not analyzable, and it covers the case where this code is
 932       // being called from within backedge-taken count analysis, such that
 933       // attempting to ask for the backedge-taken count would likely result
 934       // in infinite recursion. In the later case, the analysis code will
 935       // cope with a conservative value, and it will take care to purge
 936       // that value once it has finished.
 937       const SCEV *MaxBECount = getMaxBackedgeTakenCount(L);
 938       if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
 939         // Manually compute the final value for AR, checking for
 940         // overflow.
 941
 942         // Check whether the backedge-taken count can be losslessly casted to
 943         // the addrec's type. The count is always unsigned.
 944         const SCEV *CastedMaxBECount =
 945           getTruncateOrZeroExtend(MaxBECount, Start->getType());
 946         const SCEV *RecastedMaxBECount =
 947           getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
 948         if (MaxBECount == RecastedMaxBECount) {
 949           const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2);
 950           // Check whether Start+Step*MaxBECount has no signed overflow.
 951           const SCEV *SMul = getMulExpr(CastedMaxBECount, Step);
 952           const SCEV *Add = getAddExpr(Start, SMul);
 953           const SCEV *OperandExtendedAdd =
 954             getAddExpr(getSignExtendExpr(Start, WideTy),
 955                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 956                                   getSignExtendExpr(Step, WideTy)));
 957           if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
 958             // Return the expression with the addrec on the outside.
 959             return getAddRecExpr(getSignExtendExpr(Start, Ty),
 960                                  getSignExtendExpr(Step, Ty),
 961                                  L);
 962
 963           // Similar to above, only this time treat the step value as unsigned.
 964           // This covers loops that count up with an unsigned step.
 965           const SCEV *UMul = getMulExpr(CastedMaxBECount, Step);
 966           Add = getAddExpr(Start, UMul);
 967           OperandExtendedAdd =
 968             getAddExpr(getSignExtendExpr(Start, WideTy),
 969                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 970                                   getZeroExtendExpr(Step, WideTy)));
 971           if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
 972             // Return the expression with the addrec on the outside.
 973             return getAddRecExpr(getSignExtendExpr(Start, Ty),
 974                                  getZeroExtendExpr(Step, Ty),
 975                                  L);
 976         }
 977
 978         // If the backedge is guarded by a comparison with the pre-inc value
 979         // the addrec is safe. Also, if the entry is guarded by a comparison
 980         // with the start value and the backedge is guarded by a comparison
 981         // with the post-inc value, the addrec is safe.
 982         if (isKnownPositive(Step)) {
 983           const SCEV *N = getConstant(APInt::getSignedMinValue(BitWidth) -
 984                                       getSignedRange(Step).getSignedMax());
 985           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR, N) ||
 986               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) &&
 987                isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT,
 988                                            AR->getPostIncExpr(*this), N)))
 989             // Return the expression with the addrec on the outside.
 990             return getAddRecExpr(getSignExtendExpr(Start, Ty),
 991                                  getSignExtendExpr(Step, Ty),
 992                                  L);
 993         } else if (isKnownNegative(Step)) {
 994           const SCEV *N = getConstant(APInt::getSignedMaxValue(BitWidth) -
 995                                       getSignedRange(Step).getSignedMin());
 996           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR, N) ||
 997               (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) &&
 998                isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT,
 999                                            AR->getPostIncExpr(*this), N)))
1000             // Return the expression with the addrec on the outside.
1001             return getAddRecExpr(getSignExtendExpr(Start, Ty),
1002                                  getSignExtendExpr(Step, Ty),
1003                                  L);
1004         }
1005       }
1006     }
1007
1008   // The cast wasn't folded; create an explicit cast node.
1009   // Recompute the insert position, as it may have been invalidated.
1010   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1011   SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
1012                                                    Op, Ty);
1013   UniqueSCEVs.InsertNode(S, IP);
1014   return S;
1015 }
1016
1017 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
1018 /// unspecified bits out to the given type.
1019 ///
1020 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
1021                                               const Type *Ty) {
1022   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
1023          "This is not an extending conversion!");
1024   assert(isSCEVable(Ty) &&
1025          "This is not a conversion to a SCEVable type!");
1026   Ty = getEffectiveSCEVType(Ty);
1027
1028   // Sign-extend negative constants.
1029   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
1030     if (SC->getValue()->getValue().isNegative())
1031       return getSignExtendExpr(Op, Ty);
1032
1033   // Peel off a truncate cast.
1034   if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
1035     const SCEV *NewOp = T->getOperand();
1036     if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
1037       return getAnyExtendExpr(NewOp, Ty);
1038     return getTruncateOrNoop(NewOp, Ty);
1039   }
1040
1041   // Next try a zext cast. If the cast is folded, use it.
1042   const SCEV *ZExt = getZeroExtendExpr(Op, Ty);
1043   if (!isa<SCEVZeroExtendExpr>(ZExt))
1044     return ZExt;
1045
1046   // Next try a sext cast. If the cast is folded, use it.
1047   const SCEV *SExt = getSignExtendExpr(Op, Ty);
1048   if (!isa<SCEVSignExtendExpr>(SExt))
1049     return SExt;
1050
1051   // Force the cast to be folded into the operands of an addrec.
1052   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) {
1053     SmallVector<const SCEV *, 4> Ops;
1054     for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end();
1055          I != E; ++I)
1056       Ops.push_back(getAnyExtendExpr(*I, Ty));
1057     return getAddRecExpr(Ops, AR->getLoop());
1058   }
1059
1060   // If the expression is obviously signed, use the sext cast value.
1061   if (isa<SCEVSMaxExpr>(Op))
1062     return SExt;
1063
1064   // Absent any other information, use the zext cast value.
1065   return ZExt;
1066 }
1067
1068 /// CollectAddOperandsWithScales - Process the given Ops list, which is
1069 /// a list of operands to be added under the given scale, update the given
1070 /// map. This is a helper function for getAddRecExpr. As an example of
1071 /// what it does, given a sequence of operands that would form an add
1072 /// expression like this:
1073 ///
1074 ///    m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r)
1075 ///
1076 /// where A and B are constants, update the map with these values:
1077 ///
1078 ///    (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
1079 ///
1080 /// and add 13 + A*B*29 to AccumulatedConstant.
1081 /// This will allow getAddRecExpr to produce this:
1082 ///
1083 ///    13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
1084 ///
1085 /// This form often exposes folding opportunities that are hidden in
1086 /// the original operand list.
1087 ///
1088 /// Return true iff it appears that any interesting folding opportunities
1089 /// may be exposed. This helps getAddRecExpr short-circuit extra work in
1090 /// the common case where no interesting opportunities are present, and
1091 /// is also used as a check to avoid infinite recursion.
1092 ///
1093 static bool
1094 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
1095                              SmallVector<const SCEV *, 8> &NewOps,
1096                              APInt &AccumulatedConstant,
1097                              const SCEV *const *Ops, size_t NumOperands,
1098                              const APInt &Scale,
1099                              ScalarEvolution &SE) {
1100   bool Interesting = false;
1101
1102   // Iterate over the add operands.
1103   for (unsigned i = 0, e = NumOperands; i != e; ++i) {
1104     const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]);
1105     if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
1106       APInt NewScale =
1107         Scale * cast<SCEVConstant>(Mul->getOperand(0))->getValue()->getValue();
1108       if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
1109         // A multiplication of a constant with another add; recurse.
1110         const SCEVAddExpr *Add = cast<SCEVAddExpr>(Mul->getOperand(1));
1111         Interesting |=
1112           CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
1113                                        Add->op_begin(), Add->getNumOperands(),
1114                                        NewScale, SE);
1115       } else {
1116         // A multiplication of a constant with some other value. Update
1117         // the map.
1118         SmallVector<const SCEV *, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
1119         const SCEV *Key = SE.getMulExpr(MulOps);
1120         std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
1121           M.insert(std::make_pair(Key, NewScale));
1122         if (Pair.second) {
1123           NewOps.push_back(Pair.first->first);
1124         } else {
1125           Pair.first->second += NewScale;
1126           // The map already had an entry for this value, which may indicate
1127           // a folding opportunity.
1128           Interesting = true;
1129         }
1130       }
1131     } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1132       // Pull a buried constant out to the outside.
1133       if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero())
1134         Interesting = true;
1135       AccumulatedConstant += Scale * C->getValue()->getValue();
1136     } else {
1137       // An ordinary operand. Update the map.
1138       std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair =
1139         M.insert(std::make_pair(Ops[i], Scale));
1140       if (Pair.second) {
1141         NewOps.push_back(Pair.first->first);
1142       } else {
1143         Pair.first->second += Scale;
1144         // The map already had an entry for this value, which may indicate
1145         // a folding opportunity.
1146         Interesting = true;
1147       }
1148     }
1149   }
1150
1151   return Interesting;
1152 }
1153
1154 namespace {
1155   struct APIntCompare {
1156     bool operator()(const APInt &LHS, const APInt &RHS) const {
1157       return LHS.ult(RHS);
1158     }
1159   };
1160 }
1161
1162 /// getAddExpr - Get a canonical add expression, or something simpler if
1163 /// possible.
1164 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
1165                                         bool HasNUW, bool HasNSW) {
1166   assert(!Ops.empty() && "Cannot get empty add!");
1167   if (Ops.size() == 1) return Ops[0];
1168 #ifndef NDEBUG
1169   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1170     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1171            getEffectiveSCEVType(Ops[0]->getType()) &&
1172            "SCEVAddExpr operand types don't match!");
1173 #endif
1174
1175   // If HasNSW is true and all the operands are non-negative, infer HasNUW.
1176   if (!HasNUW && HasNSW) {
1177     bool All = true;
1178     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1179       if (!isKnownNonNegative(Ops[i])) {
1180         All = false;
1181         break;
1182       }
1183     if (All) HasNUW = true;
1184   }
1185
1186   // Sort by complexity, this groups all similar expression types together.
1187   GroupByComplexity(Ops, LI);
1188
1189   // If there are any constants, fold them together.
1190   unsigned Idx = 0;
1191   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1192     ++Idx;
1193     assert(Idx < Ops.size());
1194     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1195       // We found two constants, fold them together!
1196       Ops[0] = getConstant(LHSC->getValue()->getValue() +
1197                            RHSC->getValue()->getValue());
1198       if (Ops.size() == 2) return Ops[0];
1199       Ops.erase(Ops.begin()+1);  // Erase the folded element
1200       LHSC = cast<SCEVConstant>(Ops[0]);
1201     }
1202
1203     // If we are left with a constant zero being added, strip it off.
1204     if (LHSC->getValue()->isZero()) {
1205       Ops.erase(Ops.begin());
1206       --Idx;
1207     }
1208
1209     if (Ops.size() == 1) return Ops[0];
1210   }
1211
1212   // Okay, check to see if the same value occurs in the operand list twice.  If
1213   // so, merge them together into an multiply expression.  Since we sorted the
1214   // list, these values are required to be adjacent.
1215   const Type *Ty = Ops[0]->getType();
1216   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1217     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
1218       // Found a match, merge the two values into a multiply, and add any
1219       // remaining values to the result.
1220       const SCEV *Two = getConstant(Ty, 2);
1221       const SCEV *Mul = getMulExpr(Ops[i], Two);
1222       if (Ops.size() == 2)
1223         return Mul;
1224       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
1225       Ops.push_back(Mul);
1226       return getAddExpr(Ops, HasNUW, HasNSW);
1227     }
1228
1229   // Check for truncates. If all the operands are truncated from the same
1230   // type, see if factoring out the truncate would permit the result to be
1231   // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n)
1232   // if the contents of the resulting outer trunc fold to something simple.
1233   for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
1234     const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
1235     const Type *DstType = Trunc->getType();
1236     const Type *SrcType = Trunc->getOperand()->getType();
1237     SmallVector<const SCEV *, 8> LargeOps;
1238     bool Ok = true;
1239     // Check all the operands to see if they can be represented in the
1240     // source type of the truncate.
1241     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1242       if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) {
1243         if (T->getOperand()->getType() != SrcType) {
1244           Ok = false;
1245           break;
1246         }
1247         LargeOps.push_back(T->getOperand());
1248       } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1249         LargeOps.push_back(getAnyExtendExpr(C, SrcType));
1250       } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
1251         SmallVector<const SCEV *, 8> LargeMulOps;
1252         for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
1253           if (const SCEVTruncateExpr *T =
1254                 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
1255             if (T->getOperand()->getType() != SrcType) {
1256               Ok = false;
1257               break;
1258             }
1259             LargeMulOps.push_back(T->getOperand());
1260           } else if (const SCEVConstant *C =
1261                        dyn_cast<SCEVConstant>(M->getOperand(j))) {
1262             LargeMulOps.push_back(getAnyExtendExpr(C, SrcType));
1263           } else {
1264             Ok = false;
1265             break;
1266           }
1267         }
1268         if (Ok)
1269           LargeOps.push_back(getMulExpr(LargeMulOps));
1270       } else {
1271         Ok = false;
1272         break;
1273       }
1274     }
1275     if (Ok) {
1276       // Evaluate the expression in the larger type.
1277       const SCEV *Fold = getAddExpr(LargeOps, HasNUW, HasNSW);
1278       // If it folds to something simple, use it. Otherwise, don't.
1279       if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
1280         return getTruncateExpr(Fold, DstType);
1281     }
1282   }
1283
1284   // Skip past any other cast SCEVs.
1285   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
1286     ++Idx;
1287
1288   // If there are add operands they would be next.
1289   if (Idx < Ops.size()) {
1290     bool DeletedAdd = false;
1291     while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
1292       // If we have an add, expand the add operands onto the end of the operands
1293       // list.
1294       Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
1295       Ops.erase(Ops.begin()+Idx);
1296       DeletedAdd = true;
1297     }
1298
1299     // If we deleted at least one add, we added operands to the end of the list,
1300     // and they are not necessarily sorted.  Recurse to resort and resimplify
1301     // any operands we just acquired.
1302     if (DeletedAdd)
1303       return getAddExpr(Ops);
1304   }
1305
1306   // Skip over the add expression until we get to a multiply.
1307   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
1308     ++Idx;
1309
1310   // Check to see if there are any folding opportunities present with
1311   // operands multiplied by constant values.
1312   if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
1313     uint64_t BitWidth = getTypeSizeInBits(Ty);
1314     DenseMap<const SCEV *, APInt> M;
1315     SmallVector<const SCEV *, 8> NewOps;
1316     APInt AccumulatedConstant(BitWidth, 0);
1317     if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
1318                                      Ops.data(), Ops.size(),
1319                                      APInt(BitWidth, 1), *this)) {
1320       // Some interesting folding opportunity is present, so its worthwhile to
1321       // re-generate the operands list. Group the operands by constant scale,
1322       // to avoid multiplying by the same constant scale multiple times.
1323       std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
1324       for (SmallVector<const SCEV *, 8>::iterator I = NewOps.begin(),
1325            E = NewOps.end(); I != E; ++I)
1326         MulOpLists[M.find(*I)->second].push_back(*I);
1327       // Re-generate the operands list.
1328       Ops.clear();
1329       if (AccumulatedConstant != 0)
1330         Ops.push_back(getConstant(AccumulatedConstant));
1331       for (std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare>::iterator
1332            I = MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
1333         if (I->first != 0)
1334           Ops.push_back(getMulExpr(getConstant(I->first),
1335                                    getAddExpr(I->second)));
1336       if (Ops.empty())
1337         return getConstant(Ty, 0);
1338       if (Ops.size() == 1)
1339         return Ops[0];
1340       return getAddExpr(Ops);
1341     }
1342   }
1343
1344   // If we are adding something to a multiply expression, make sure the
1345   // something is not already an operand of the multiply.  If so, merge it into
1346   // the multiply.
1347   for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
1348     const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
1349     for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
1350       const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
1351       for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
1352         if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) {
1353           // Fold W + X + (X * Y * Z)  -->  W + (X * ((Y*Z)+1))
1354           const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
1355           if (Mul->getNumOperands() != 2) {
1356             // If the multiply has more than two operands, we must get the
1357             // Y*Z term.
1358             SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(), Mul->op_end());
1359             MulOps.erase(MulOps.begin()+MulOp);
1360             InnerMul = getMulExpr(MulOps);
1361           }
1362           const SCEV *One = getConstant(Ty, 1);
1363           const SCEV *AddOne = getAddExpr(InnerMul, One);
1364           const SCEV *OuterMul = getMulExpr(AddOne, Ops[AddOp]);
1365           if (Ops.size() == 2) return OuterMul;
1366           if (AddOp < Idx) {
1367             Ops.erase(Ops.begin()+AddOp);
1368             Ops.erase(Ops.begin()+Idx-1);
1369           } else {
1370             Ops.erase(Ops.begin()+Idx);
1371             Ops.erase(Ops.begin()+AddOp-1);
1372           }
1373           Ops.push_back(OuterMul);
1374           return getAddExpr(Ops);
1375         }
1376
1377       // Check this multiply against other multiplies being added together.
1378       for (unsigned OtherMulIdx = Idx+1;
1379            OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
1380            ++OtherMulIdx) {
1381         const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
1382         // If MulOp occurs in OtherMul, we can fold the two multiplies
1383         // together.
1384         for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
1385              OMulOp != e; ++OMulOp)
1386           if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
1387             // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
1388             const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
1389             if (Mul->getNumOperands() != 2) {
1390               SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
1391                                                   Mul->op_end());
1392               MulOps.erase(MulOps.begin()+MulOp);
1393               InnerMul1 = getMulExpr(MulOps);
1394             }
1395             const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
1396             if (OtherMul->getNumOperands() != 2) {
1397               SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(),
1398                                                   OtherMul->op_end());
1399               MulOps.erase(MulOps.begin()+OMulOp);
1400               InnerMul2 = getMulExpr(MulOps);
1401             }
1402             const SCEV *InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
1403             const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
1404             if (Ops.size() == 2) return OuterMul;
1405             Ops.erase(Ops.begin()+Idx);
1406             Ops.erase(Ops.begin()+OtherMulIdx-1);
1407             Ops.push_back(OuterMul);
1408             return getAddExpr(Ops);
1409           }
1410       }
1411     }
1412   }
1413
1414   // If there are any add recurrences in the operands list, see if any other
1415   // added values are loop invariant.  If so, we can fold them into the
1416   // recurrence.
1417   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1418     ++Idx;
1419
1420   // Scan over all recurrences, trying to fold loop invariants into them.
1421   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1422     // Scan all of the other operands to this add and add them to the vector if
1423     // they are loop invariant w.r.t. the recurrence.
1424     SmallVector<const SCEV *, 8> LIOps;
1425     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1426     const Loop *AddRecLoop = AddRec->getLoop();
1427     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1428       if (Ops[i]->isLoopInvariant(AddRecLoop)) {
1429         LIOps.push_back(Ops[i]);
1430         Ops.erase(Ops.begin()+i);
1431         --i; --e;
1432       }
1433
1434     // If we found some loop invariants, fold them into the recurrence.
1435     if (!LIOps.empty()) {
1436       //  NLI + LI + {Start,+,Step}  -->  NLI + {LI+Start,+,Step}
1437       LIOps.push_back(AddRec->getStart());
1438
1439       SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(),
1440                                              AddRec->op_end());
1441       AddRecOps[0] = getAddExpr(LIOps);
1442
1443       // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition
1444       // is not associative so this isn't necessarily safe.
1445       const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop);
1446
1447       // If all of the other operands were loop invariant, we are done.
1448       if (Ops.size() == 1) return NewRec;
1449
1450       // Otherwise, add the folded AddRec by the non-liv parts.
1451       for (unsigned i = 0;; ++i)
1452         if (Ops[i] == AddRec) {
1453           Ops[i] = NewRec;
1454           break;
1455         }
1456       return getAddExpr(Ops);
1457     }
1458
1459     // Okay, if there weren't any loop invariants to be folded, check to see if
1460     // there are multiple AddRec's with the same loop induction variable being
1461     // added together.  If so, we can fold them.
1462     for (unsigned OtherIdx = Idx+1;
1463          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1464       if (OtherIdx != Idx) {
1465         const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1466         if (AddRecLoop == OtherAddRec->getLoop()) {
1467           // Other + {A,+,B} + {C,+,D}  -->  Other + {A+C,+,B+D}
1468           SmallVector<const SCEV *, 4> NewOps(AddRec->op_begin(),
1469                                               AddRec->op_end());
1470           for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
1471             if (i >= NewOps.size()) {
1472               NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
1473                             OtherAddRec->op_end());
1474               break;
1475             }
1476             NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
1477           }
1478           const SCEV *NewAddRec = getAddRecExpr(NewOps, AddRecLoop);
1479
1480           if (Ops.size() == 2) return NewAddRec;
1481
1482           Ops.erase(Ops.begin()+Idx);
1483           Ops.erase(Ops.begin()+OtherIdx-1);
1484           Ops.push_back(NewAddRec);
1485           return getAddExpr(Ops);
1486         }
1487       }
1488
1489     // Otherwise couldn't fold anything into this recurrence.  Move onto the
1490     // next one.
1491   }
1492
1493   // Okay, it looks like we really DO need an add expr.  Check to see if we
1494   // already have one, otherwise create a new one.
1495   FoldingSetNodeID ID;
1496   ID.AddInteger(scAddExpr);
1497   ID.AddInteger(Ops.size());
1498   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1499     ID.AddPointer(Ops[i]);
1500   void *IP = 0;
1501   SCEVAddExpr *S =
1502     static_cast<SCEVAddExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1503   if (!S) {
1504     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
1505     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
1506     S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator),
1507                                         O, Ops.size());
1508     UniqueSCEVs.InsertNode(S, IP);
1509   }
1510   if (HasNUW) S->setHasNoUnsignedWrap(true);
1511   if (HasNSW) S->setHasNoSignedWrap(true);
1512   return S;
1513 }
1514
1515 /// getMulExpr - Get a canonical multiply expression, or something simpler if
1516 /// possible.
1517 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
1518                                         bool HasNUW, bool HasNSW) {
1519   assert(!Ops.empty() && "Cannot get empty mul!");
1520   if (Ops.size() == 1) return Ops[0];
1521 #ifndef NDEBUG
1522   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1523     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1524            getEffectiveSCEVType(Ops[0]->getType()) &&
1525            "SCEVMulExpr operand types don't match!");
1526 #endif
1527
1528   // If HasNSW is true and all the operands are non-negative, infer HasNUW.
1529   if (!HasNUW && HasNSW) {
1530     bool All = true;
1531     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1532       if (!isKnownNonNegative(Ops[i])) {
1533         All = false;
1534         break;
1535       }
1536     if (All) HasNUW = true;
1537   }
1538
1539   // Sort by complexity, this groups all similar expression types together.
1540   GroupByComplexity(Ops, LI);
1541
1542   // If there are any constants, fold them together.
1543   unsigned Idx = 0;
1544   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1545
1546     // C1*(C2+V) -> C1*C2 + C1*V
1547     if (Ops.size() == 2)
1548       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
1549         if (Add->getNumOperands() == 2 &&
1550             isa<SCEVConstant>(Add->getOperand(0)))
1551           return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
1552                             getMulExpr(LHSC, Add->getOperand(1)));
1553
1554     ++Idx;
1555     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1556       // We found two constants, fold them together!
1557       ConstantInt *Fold = ConstantInt::get(getContext(),
1558                                            LHSC->getValue()->getValue() *
1559                                            RHSC->getValue()->getValue());
1560       Ops[0] = getConstant(Fold);
1561       Ops.erase(Ops.begin()+1);  // Erase the folded element
1562       if (Ops.size() == 1) return Ops[0];
1563       LHSC = cast<SCEVConstant>(Ops[0]);
1564     }
1565
1566     // If we are left with a constant one being multiplied, strip it off.
1567     if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
1568       Ops.erase(Ops.begin());
1569       --Idx;
1570     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
1571       // If we have a multiply of zero, it will always be zero.
1572       return Ops[0];
1573     } else if (Ops[0]->isAllOnesValue()) {
1574       // If we have a mul by -1 of an add, try distributing the -1 among the
1575       // add operands.
1576       if (Ops.size() == 2)
1577         if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
1578           SmallVector<const SCEV *, 4> NewOps;
1579           bool AnyFolded = false;
1580           for (SCEVAddRecExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
1581                I != E; ++I) {
1582             const SCEV *Mul = getMulExpr(Ops[0], *I);
1583             if (!isa<SCEVMulExpr>(Mul)) AnyFolded = true;
1584             NewOps.push_back(Mul);
1585           }
1586           if (AnyFolded)
1587             return getAddExpr(NewOps);
1588         }
1589     }
1590
1591     if (Ops.size() == 1)
1592       return Ops[0];
1593   }
1594
1595   // Skip over the add expression until we get to a multiply.
1596   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
1597     ++Idx;
1598
1599   // If there are mul operands inline them all into this expression.
1600   if (Idx < Ops.size()) {
1601     bool DeletedMul = false;
1602     while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
1603       // If we have an mul, expand the mul operands onto the end of the operands
1604       // list.
1605       Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
1606       Ops.erase(Ops.begin()+Idx);
1607       DeletedMul = true;
1608     }
1609
1610     // If we deleted at least one mul, we added operands to the end of the list,
1611     // and they are not necessarily sorted.  Recurse to resort and resimplify
1612     // any operands we just acquired.
1613     if (DeletedMul)
1614       return getMulExpr(Ops);
1615   }
1616
1617   // If there are any add recurrences in the operands list, see if any other
1618   // added values are loop invariant.  If so, we can fold them into the
1619   // recurrence.
1620   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1621     ++Idx;
1622
1623   // Scan over all recurrences, trying to fold loop invariants into them.
1624   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1625     // Scan all of the other operands to this mul and add them to the vector if
1626     // they are loop invariant w.r.t. the recurrence.
1627     SmallVector<const SCEV *, 8> LIOps;
1628     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1629     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1630       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1631         LIOps.push_back(Ops[i]);
1632         Ops.erase(Ops.begin()+i);
1633         --i; --e;
1634       }
1635
1636     // If we found some loop invariants, fold them into the recurrence.
1637     if (!LIOps.empty()) {
1638       //  NLI * LI * {Start,+,Step}  -->  NLI * {LI*Start,+,LI*Step}
1639       SmallVector<const SCEV *, 4> NewOps;
1640       NewOps.reserve(AddRec->getNumOperands());
1641       if (LIOps.size() == 1) {
1642         const SCEV *Scale = LIOps[0];
1643         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
1644           NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
1645       } else {
1646         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
1647           SmallVector<const SCEV *, 4> MulOps(LIOps.begin(), LIOps.end());
1648           MulOps.push_back(AddRec->getOperand(i));
1649           NewOps.push_back(getMulExpr(MulOps));
1650         }
1651       }
1652
1653       // It's tempting to propagate the NSW flag here, but nsw multiplication
1654       // is not associative so this isn't necessarily safe.
1655       const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(),
1656                                          HasNUW && AddRec->hasNoUnsignedWrap(),
1657                                          /*HasNSW=*/false);
1658
1659       // If all of the other operands were loop invariant, we are done.
1660       if (Ops.size() == 1) return NewRec;
1661
1662       // Otherwise, multiply the folded AddRec by the non-liv parts.
1663       for (unsigned i = 0;; ++i)
1664         if (Ops[i] == AddRec) {
1665           Ops[i] = NewRec;
1666           break;
1667         }
1668       return getMulExpr(Ops);
1669     }
1670
1671     // Okay, if there weren't any loop invariants to be folded, check to see if
1672     // there are multiple AddRec's with the same loop induction variable being
1673     // multiplied together.  If so, we can fold them.
1674     for (unsigned OtherIdx = Idx+1;
1675          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1676       if (OtherIdx != Idx) {
1677         const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1678         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1679           // F * G  -->  {A,+,B} * {C,+,D}  -->  {A*C,+,F*D + G*B + B*D}
1680           const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
1681           const SCEV *NewStart = getMulExpr(F->getStart(),
1682                                                  G->getStart());
1683           const SCEV *B = F->getStepRecurrence(*this);
1684           const SCEV *D = G->getStepRecurrence(*this);
1685           const SCEV *NewStep = getAddExpr(getMulExpr(F, D),
1686                                           getMulExpr(G, B),
1687                                           getMulExpr(B, D));
1688           const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep,
1689                                                F->getLoop());
1690           if (Ops.size() == 2) return NewAddRec;
1691
1692           Ops.erase(Ops.begin()+Idx);
1693           Ops.erase(Ops.begin()+OtherIdx-1);
1694           Ops.push_back(NewAddRec);
1695           return getMulExpr(Ops);
1696         }
1697       }
1698
1699     // Otherwise couldn't fold anything into this recurrence.  Move onto the
1700     // next one.
1701   }
1702
1703   // Okay, it looks like we really DO need an mul expr.  Check to see if we
1704   // already have one, otherwise create a new one.
1705   FoldingSetNodeID ID;
1706   ID.AddInteger(scMulExpr);
1707   ID.AddInteger(Ops.size());
1708   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1709     ID.AddPointer(Ops[i]);
1710   void *IP = 0;
1711   SCEVMulExpr *S =
1712     static_cast<SCEVMulExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1713   if (!S) {
1714     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
1715     std::uninitialized_copy(Ops.begin(), Ops.end(), O);
1716     S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator),
1717                                         O, Ops.size());
1718     UniqueSCEVs.InsertNode(S, IP);
1719   }
1720   if (HasNUW) S->setHasNoUnsignedWrap(true);
1721   if (HasNSW) S->setHasNoSignedWrap(true);
1722   return S;
1723 }
1724
1725 /// getUDivExpr - Get a canonical unsigned division expression, or something
1726 /// simpler if possible.
1727 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
1728                                          const SCEV *RHS) {
1729   assert(getEffectiveSCEVType(LHS->getType()) ==
1730          getEffectiveSCEVType(RHS->getType()) &&
1731          "SCEVUDivExpr operand types don't match!");
1732
1733   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
1734     if (RHSC->getValue()->equalsInt(1))
1735       return LHS;                               // X udiv 1 --> x
1736     // If the denominator is zero, the result of the udiv is undefined. Don't
1737     // try to analyze it, because the resolution chosen here may differ from
1738     // the resolution chosen in other parts of the compiler.
1739     if (!RHSC->getValue()->isZero()) {
1740       // Determine if the division can be folded into the operands of
1741       // its operands.
1742       // TODO: Generalize this to non-constants by using known-bits information.
1743       const Type *Ty = LHS->getType();
1744       unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
1745       unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ;
1746       // For non-power-of-two values, effectively round the value up to the
1747       // nearest power of two.
1748       if (!RHSC->getValue()->getValue().isPowerOf2())
1749         ++MaxShiftAmt;
1750       const IntegerType *ExtTy =
1751         IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt);
1752       // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
1753       if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
1754         if (const SCEVConstant *Step =
1755               dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this)))
1756           if (!Step->getValue()->getValue()
1757                 .urem(RHSC->getValue()->getValue()) &&
1758               getZeroExtendExpr(AR, ExtTy) ==
1759               getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
1760                             getZeroExtendExpr(Step, ExtTy),
1761                             AR->getLoop())) {
1762             SmallVector<const SCEV *, 4> Operands;
1763             for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
1764               Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
1765             return getAddRecExpr(Operands, AR->getLoop());
1766           }
1767       // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
1768       if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
1769         SmallVector<const SCEV *, 4> Operands;
1770         for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
1771           Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
1772         if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
1773           // Find an operand that's safely divisible.
1774           for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
1775             const SCEV *Op = M->getOperand(i);
1776             const SCEV *Div = getUDivExpr(Op, RHSC);
1777             if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
1778               Operands = SmallVector<const SCEV *, 4>(M->op_begin(),
1779                                                       M->op_end());
1780               Operands[i] = Div;
1781               return getMulExpr(Operands);
1782             }
1783           }
1784       }
1785       // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
1786       if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) {
1787         SmallVector<const SCEV *, 4> Operands;
1788         for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
1789           Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
1790         if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
1791           Operands.clear();
1792           for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
1793             const SCEV *Op = getUDivExpr(A->getOperand(i), RHS);
1794             if (isa<SCEVUDivExpr>(Op) ||
1795                 getMulExpr(Op, RHS) != A->getOperand(i))
1796               break;
1797             Operands.push_back(Op);
1798           }
1799           if (Operands.size() == A->getNumOperands())
1800             return getAddExpr(Operands);
1801         }
1802       }
1803
1804       // Fold if both operands are constant.
1805       if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1806         Constant *LHSCV = LHSC->getValue();
1807         Constant *RHSCV = RHSC->getValue();
1808         return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
1809                                                                    RHSCV)));
1810       }
1811     }
1812   }
1813
1814   FoldingSetNodeID ID;
1815   ID.AddInteger(scUDivExpr);
1816   ID.AddPointer(LHS);
1817   ID.AddPointer(RHS);
1818   void *IP = 0;
1819   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1820   SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator),
1821                                              LHS, RHS);
1822   UniqueSCEVs.InsertNode(S, IP);
1823   return S;
1824 }
1825
1826
1827 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
1828 /// Simplify the expression as much as possible.
1829 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start,
1830                                            const SCEV *Step, const Loop *L,
1831                                            bool HasNUW, bool HasNSW) {
1832   SmallVector<const SCEV *, 4> Operands;
1833   Operands.push_back(Start);
1834   if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
1835     if (StepChrec->getLoop() == L) {
1836       Operands.insert(Operands.end(), StepChrec->op_begin(),
1837                       StepChrec->op_end());
1838       return getAddRecExpr(Operands, L);
1839     }
1840
1841   Operands.push_back(Step);
1842   return getAddRecExpr(Operands, L, HasNUW, HasNSW);
1843 }
1844
1845 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
1846 /// Simplify the expression as much as possible.
1847 const SCEV *
1848 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
1849                                const Loop *L,
1850                                bool HasNUW, bool HasNSW) {
1851   if (Operands.size() == 1) return Operands[0];
1852 #ifndef NDEBUG
1853   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
1854     assert(getEffectiveSCEVType(Operands[i]->getType()) ==
1855            getEffectiveSCEVType(Operands[0]->getType()) &&
1856            "SCEVAddRecExpr operand types don't match!");
1857 #endif
1858
1859   if (Operands.back()->isZero()) {
1860     Operands.pop_back();
1861     return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0}  -->  X
1862   }
1863
1864   // It's tempting to want to call getMaxBackedgeTakenCount count here and
1865   // use that information to infer NUW and NSW flags. However, computing a
1866   // BE count requires calling getAddRecExpr, so we may not yet have a
1867   // meaningful BE count at this point (and if we don't, we'd be stuck
1868   // with a SCEVCouldNotCompute as the cached BE count).
1869
1870   // If HasNSW is true and all the operands are non-negative, infer HasNUW.
1871   if (!HasNUW && HasNSW) {
1872     bool All = true;
1873     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
1874       if (!isKnownNonNegative(Operands[i])) {
1875         All = false;
1876         break;
1877       }
1878     if (All) HasNUW = true;
1879   }
1880
1881   // Canonicalize nested AddRecs in by nesting them in order of loop depth.
1882   if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
1883     const Loop *NestedLoop = NestedAR->getLoop();
1884     if (L->contains(NestedLoop->getHeader()) ?
1885         (L->getLoopDepth() < NestedLoop->getLoopDepth()) :
1886         (!NestedLoop->contains(L->getHeader()) &&
1887          DT->dominates(L->getHeader(), NestedLoop->getHeader()))) {
1888       SmallVector<const SCEV *, 4> NestedOperands(NestedAR->op_begin(),
1889                                                   NestedAR->op_end());
1890       Operands[0] = NestedAR->getStart();
1891       // AddRecs require their operands be loop-invariant with respect to their
1892       // loops. Don't perform this transformation if it would break this
1893       // requirement.
1894       bool AllInvariant = true;
1895       for (unsigned i = 0, e = Operands.size(); i != e; ++i)
1896         if (!Operands[i]->isLoopInvariant(L)) {
1897           AllInvariant = false;
1898           break;
1899         }
1900       if (AllInvariant) {
1901         NestedOperands[0] = getAddRecExpr(Operands, L);
1902         AllInvariant = true;
1903         for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i)
1904           if (!NestedOperands[i]->isLoopInvariant(NestedLoop)) {
1905             AllInvariant = false;
1906             break;
1907           }
1908         if (AllInvariant)
1909           // Ok, both add recurrences are valid after the transformation.
1910           return getAddRecExpr(NestedOperands, NestedLoop, HasNUW, HasNSW);
1911       }
1912       // Reset Operands to its original state.
1913       Operands[0] = NestedAR;
1914     }
1915   }
1916
1917   // Okay, it looks like we really DO need an addrec expr.  Check to see if we
1918   // already have one, otherwise create a new one.
1919   FoldingSetNodeID ID;
1920   ID.AddInteger(scAddRecExpr);
1921   ID.AddInteger(Operands.size());
1922   for (unsigned i = 0, e = Operands.size(); i != e; ++i)
1923     ID.AddPointer(Operands[i]);
1924   ID.AddPointer(L);
1925   void *IP = 0;
1926   SCEVAddRecExpr *S =
1927     static_cast<SCEVAddRecExpr *>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1928   if (!S) {
1929     const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Operands.size());
1930     std::uninitialized_copy(Operands.begin(), Operands.end(), O);
1931     S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator),
1932                                            O, Operands.size(), L);
1933     UniqueSCEVs.InsertNode(S, IP);
1934   }
1935   if (HasNUW) S->setHasNoUnsignedWrap(true);
1936   if (HasNSW) S->setHasNoSignedWrap(true);
1937   return S;
1938 }
1939
1940 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
1941                                          const SCEV *RHS) {
1942   SmallVector<const SCEV *, 2> Ops;
1943   Ops.push_back(LHS);
1944   Ops.push_back(RHS);
1945   return getSMaxExpr(Ops);
1946 }
1947
1948 const SCEV *
1949 ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
1950   assert(!Ops.empty() && "Cannot get empty smax!");
1951   if (Ops.size() == 1) return Ops[0];
1952 #ifndef NDEBUG
1953   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1954     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1955            getEffectiveSCEVType(Ops[0]->getType()) &&
1956            "SCEVSMaxExpr operand types don't match!");
1957 #endif
1958
1959   // Sort by complexity, this groups all similar expression types together.
1960   GroupByComplexity(Ops, LI);
1961
1962   // If there are any constants, fold them together.
1963   unsigned Idx = 0;
1964   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1965     ++Idx;
1966     assert(Idx < Ops.size());
1967     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1968       // We found two constants, fold them together!
1969       ConstantInt *Fold = ConstantInt::get(getContext(),
1970                               APIntOps::smax(LHSC->getValue()->getValue(),
1971                                              RHSC->getValue()->getValue()));
1972       Ops[0] = getConstant(Fold);
1973       Ops.erase(Ops.begin()+1);  // Erase the folded element
1974       if (Ops.size() == 1) return Ops[0];
1975       LHSC = cast<SCEVConstant>(Ops[0]);
1976     }
1977
1978     // If we are left with a constant minimum-int, strip it off.
1979     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
1980       Ops.erase(Ops.begin());
1981       --Idx;
1982     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) {
1983       // If we have an smax with a constant maximum-int, it will always be
1984       // maximum-int.
1985       return Ops[0];
1986     }
1987
1988     if (Ops.size() == 1) return Ops[0];
1989   }
1990
1991   // Find the first SMax
1992   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
1993     ++Idx;
1994
1995   // Check to see if one of the operands is an SMax. If so, expand its operands
1996   // onto our operand list, and recurse to simplify.
1997   if (Idx < Ops.size()) {
1998     bool DeletedSMax = false;
1999     while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
2000       Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
2001       Ops.erase(Ops.begin()+Idx);
2002       DeletedSMax = true;
2003     }
2004
2005     if (DeletedSMax)
2006       return getSMaxExpr(Ops);
2007   }
2008
2009   // Okay, check to see if the same value occurs in the operand list twice.  If
2010   // so, delete one.  Since we sorted the list, these values are required to
2011   // be adjacent.
2012   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
2013     //  X smax Y smax Y  -->  X smax Y
2014     //  X smax Y         -->  X, if X is always greater than Y
2015     if (Ops[i] == Ops[i+1] ||
2016         isKnownPredicate(ICmpInst::ICMP_SGE, Ops[i], Ops[i+1])) {
2017       Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
2018       --i; --e;
2019     } else if (isKnownPredicate(ICmpInst::ICMP_SLE, Ops[i], Ops[i+1])) {
2020       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
2021       --i; --e;
2022     }
2023
2024   if (Ops.size() == 1) return Ops[0];
2025
2026   assert(!Ops.empty() && "Reduced smax down to nothing!");
2027
2028   // Okay, it looks like we really DO need an smax expr.  Check to see if we
2029   // already have one, otherwise create a new one.
2030   FoldingSetNodeID ID;
2031   ID.AddInteger(scSMaxExpr);
2032   ID.AddInteger(Ops.size());
2033   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
2034     ID.AddPointer(Ops[i]);
2035   void *IP = 0;
2036   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2037   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
2038   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
2039   SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator),
2040                                              O, Ops.size());
2041   UniqueSCEVs.InsertNode(S, IP);
2042   return S;
2043 }
2044
2045 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
2046                                          const SCEV *RHS) {
2047   SmallVector<const SCEV *, 2> Ops;
2048   Ops.push_back(LHS);
2049   Ops.push_back(RHS);
2050   return getUMaxExpr(Ops);
2051 }
2052
2053 const SCEV *
2054 ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) {
2055   assert(!Ops.empty() && "Cannot get empty umax!");
2056   if (Ops.size() == 1) return Ops[0];
2057 #ifndef NDEBUG
2058   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
2059     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
2060            getEffectiveSCEVType(Ops[0]->getType()) &&
2061            "SCEVUMaxExpr operand types don't match!");
2062 #endif
2063
2064   // Sort by complexity, this groups all similar expression types together.
2065   GroupByComplexity(Ops, LI);
2066
2067   // If there are any constants, fold them together.
2068   unsigned Idx = 0;
2069   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2070     ++Idx;
2071     assert(Idx < Ops.size());
2072     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
2073       // We found two constants, fold them together!
2074       ConstantInt *Fold = ConstantInt::get(getContext(),
2075                               APIntOps::umax(LHSC->getValue()->getValue(),
2076                                              RHSC->getValue()->getValue()));
2077       Ops[0] = getConstant(Fold);
2078       Ops.erase(Ops.begin()+1);  // Erase the folded element
2079       if (Ops.size() == 1) return Ops[0];
2080       LHSC = cast<SCEVConstant>(Ops[0]);
2081     }
2082
2083     // If we are left with a constant minimum-int, strip it off.
2084     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
2085       Ops.erase(Ops.begin());
2086       --Idx;
2087     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) {
2088       // If we have an umax with a constant maximum-int, it will always be
2089       // maximum-int.
2090       return Ops[0];
2091     }
2092
2093     if (Ops.size() == 1) return Ops[0];
2094   }
2095
2096   // Find the first UMax
2097   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
2098     ++Idx;
2099
2100   // Check to see if one of the operands is a UMax. If so, expand its operands
2101   // onto our operand list, and recurse to simplify.
2102   if (Idx < Ops.size()) {
2103     bool DeletedUMax = false;
2104     while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
2105       Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
2106       Ops.erase(Ops.begin()+Idx);
2107       DeletedUMax = true;
2108     }
2109
2110     if (DeletedUMax)
2111       return getUMaxExpr(Ops);
2112   }
2113
2114   // Okay, check to see if the same value occurs in the operand list twice.  If
2115   // so, delete one.  Since we sorted the list, these values are required to
2116   // be adjacent.
2117   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
2118     //  X umax Y umax Y  -->  X umax Y
2119     //  X umax Y         -->  X, if X is always greater than Y
2120     if (Ops[i] == Ops[i+1] ||
2121         isKnownPredicate(ICmpInst::ICMP_UGE, Ops[i], Ops[i+1])) {
2122       Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2);
2123       --i; --e;
2124     } else if (isKnownPredicate(ICmpInst::ICMP_ULE, Ops[i], Ops[i+1])) {
2125       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
2126       --i; --e;
2127     }
2128
2129   if (Ops.size() == 1) return Ops[0];
2130
2131   assert(!Ops.empty() && "Reduced umax down to nothing!");
2132
2133   // Okay, it looks like we really DO need a umax expr.  Check to see if we
2134   // already have one, otherwise create a new one.
2135   FoldingSetNodeID ID;
2136   ID.AddInteger(scUMaxExpr);
2137   ID.AddInteger(Ops.size());
2138   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
2139     ID.AddPointer(Ops[i]);
2140   void *IP = 0;
2141   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2142   const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size());
2143   std::uninitialized_copy(Ops.begin(), Ops.end(), O);
2144   SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator),
2145                                              O, Ops.size());
2146   UniqueSCEVs.InsertNode(S, IP);
2147   return S;
2148 }
2149
2150 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
2151                                          const SCEV *RHS) {
2152   // ~smax(~x, ~y) == smin(x, y).
2153   return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
2154 }
2155
2156 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS,
2157                                          const SCEV *RHS) {
2158   // ~umax(~x, ~y) == umin(x, y)
2159   return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
2160 }
2161
2162 const SCEV *ScalarEvolution::getSizeOfExpr(const Type *AllocTy) {
2163   // If we have TargetData, we can bypass creating a target-independent
2164   // constant expression and then folding it back into a ConstantInt.
2165   // This is just a compile-time optimization.
2166   if (TD)
2167     return getConstant(TD->getIntPtrType(getContext()),
2168                        TD->getTypeAllocSize(AllocTy));
2169
2170   Constant *C = ConstantExpr::getSizeOf(AllocTy);
2171   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
2172     if (Constant *Folded = ConstantFoldConstantExpression(CE, TD))
2173       C = Folded;
2174   const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy));
2175   return getTruncateOrZeroExtend(getSCEV(C), Ty);
2176 }
2177
2178 const SCEV *ScalarEvolution::getAlignOfExpr(const Type *AllocTy) {
2179   Constant *C = ConstantExpr::getAlignOf(AllocTy);
2180   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
2181     if (Constant *Folded = ConstantFoldConstantExpression(CE, TD))
2182       C = Folded;
2183   const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy));
2184   return getTruncateOrZeroExtend(getSCEV(C), Ty);
2185 }
2186
2187 const SCEV *ScalarEvolution::getOffsetOfExpr(const StructType *STy,
2188                                              unsigned FieldNo) {
2189   // If we have TargetData, we can bypass creating a target-independent
2190   // constant expression and then folding it back into a ConstantInt.
2191   // This is just a compile-time optimization.
2192   if (TD)
2193     return getConstant(TD->getIntPtrType(getContext()),
2194                        TD->getStructLayout(STy)->getElementOffset(FieldNo));
2195
2196   Constant *C = ConstantExpr::getOffsetOf(STy, FieldNo);
2197   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
2198     if (Constant *Folded = ConstantFoldConstantExpression(CE, TD))
2199       C = Folded;
2200   const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy));
2201   return getTruncateOrZeroExtend(getSCEV(C), Ty);
2202 }
2203
2204 const SCEV *ScalarEvolution::getOffsetOfExpr(const Type *CTy,
2205                                              Constant *FieldNo) {
2206   Constant *C = ConstantExpr::getOffsetOf(CTy, FieldNo);
2207   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
2208     if (Constant *Folded = ConstantFoldConstantExpression(CE, TD))
2209       C = Folded;
2210   const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(CTy));
2211   return getTruncateOrZeroExtend(getSCEV(C), Ty);
2212 }
2213
2214 const SCEV *ScalarEvolution::getUnknown(Value *V) {
2215   // Don't attempt to do anything other than create a SCEVUnknown object
2216   // here.  createSCEV only calls getUnknown after checking for all other
2217   // interesting possibilities, and any other code that calls getUnknown
2218   // is doing so in order to hide a value from SCEV canonicalization.
2219
2220   FoldingSetNodeID ID;
2221   ID.AddInteger(scUnknown);
2222   ID.AddPointer(V);
2223   void *IP = 0;
2224   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
2225   SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V);
2226   UniqueSCEVs.InsertNode(S, IP);
2227   return S;
2228 }
2229
2230 //===----------------------------------------------------------------------===//
2231 //            Basic SCEV Analysis and PHI Idiom Recognition Code
2232 //
2233
2234 /// isSCEVable - Test if values of the given type are analyzable within
2235 /// the SCEV framework. This primarily includes integer types, and it
2236 /// can optionally include pointer types if the ScalarEvolution class
2237 /// has access to target-specific information.
2238 bool ScalarEvolution::isSCEVable(const Type *Ty) const {
2239   // Integers and pointers are always SCEVable.
2240   return Ty->isIntegerTy() || Ty->isPointerTy();
2241 }
2242
2243 /// getTypeSizeInBits - Return the size in bits of the specified type,
2244 /// for which isSCEVable must return true.
2245 uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const {
2246   assert(isSCEVable(Ty) && "Type is not SCEVable!");
2247
2248   // If we have a TargetData, use it!
2249   if (TD)
2250     return TD->getTypeSizeInBits(Ty);
2251
2252   // Integer types have fixed sizes.
2253   if (Ty->isIntegerTy())
2254     return Ty->getPrimitiveSizeInBits();
2255
2256   // The only other support type is pointer. Without TargetData, conservatively
2257   // assume pointers are 64-bit.
2258   assert(Ty->isPointerTy() && "isSCEVable permitted a non-SCEVable type!");
2259   return 64;
2260 }
2261
2262 /// getEffectiveSCEVType - Return a type with the same bitwidth as
2263 /// the given type and which represents how SCEV will treat the given
2264 /// type, for which isSCEVable must return true. For pointer types,
2265 /// this is the pointer-sized integer type.
2266 const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const {
2267   assert(isSCEVable(Ty) && "Type is not SCEVable!");
2268
2269   if (Ty->isIntegerTy())
2270     return Ty;
2271
2272   // The only other support type is pointer.
2273   assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!");
2274   if (TD) return TD->getIntPtrType(getContext());
2275
2276   // Without TargetData, conservatively assume pointers are 64-bit.
2277   return Type::getInt64Ty(getContext());
2278 }
2279
2280 const SCEV *ScalarEvolution::getCouldNotCompute() {
2281   return &CouldNotCompute;
2282 }
2283
2284 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
2285 /// expression and create a new one.
2286 const SCEV *ScalarEvolution::getSCEV(Value *V) {
2287   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
2288
2289   std::map<SCEVCallbackVH, const SCEV *>::iterator I = Scalars.find(V);
2290   if (I != Scalars.end()) return I->second;
2291   const SCEV *S = createSCEV(V);
2292   Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
2293   return S;
2294 }
2295
2296 /// getIntegerSCEV - Given a SCEVable type, create a constant for the
2297 /// specified signed integer value and return a SCEV for the constant.
2298 const SCEV *ScalarEvolution::getIntegerSCEV(int64_t Val, const Type *Ty) {
2299   const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
2300   return getConstant(ConstantInt::get(ITy, Val));
2301 }
2302
2303 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
2304 ///
2305 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) {
2306   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
2307     return getConstant(
2308                cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));
2309
2310   const Type *Ty = V->getType();
2311   Ty = getEffectiveSCEVType(Ty);
2312   return getMulExpr(V,
2313                   getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))));
2314 }
2315
2316 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
2317 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
2318   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
2319     return getConstant(
2320                 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue())));
2321
2322   const Type *Ty = V->getType();
2323   Ty = getEffectiveSCEVType(Ty);
2324   const SCEV *AllOnes =
2325                    getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
2326   return getMinusSCEV(AllOnes, V);
2327 }
2328
2329 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
2330 ///
2331 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS,
2332                                           const SCEV *RHS) {
2333   // X - Y --> X + -Y
2334   return getAddExpr(LHS, getNegativeSCEV(RHS));
2335 }
2336
2337 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
2338 /// input value to the specified type.  If the type must be extended, it is zero
2339 /// extended.
2340 const SCEV *
2341 ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V,
2342                                          const Type *Ty) {
2343   const Type *SrcTy = V->getType();
2344   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2345          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2346          "Cannot truncate or zero extend with non-integer arguments!");
2347   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2348     return V;  // No conversion
2349   if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
2350     return getTruncateExpr(V, Ty);
2351   return getZeroExtendExpr(V, Ty);
2352 }
2353
2354 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the
2355 /// input value to the specified type.  If the type must be extended, it is sign
2356 /// extended.
2357 const SCEV *
2358 ScalarEvolution::getTruncateOrSignExtend(const SCEV *V,
2359                                          const Type *Ty) {
2360   const Type *SrcTy = V->getType();
2361   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2362          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2363          "Cannot truncate or zero extend with non-integer arguments!");
2364   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2365     return V;  // No conversion
2366   if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
2367     return getTruncateExpr(V, Ty);
2368   return getSignExtendExpr(V, Ty);
2369 }
2370
2371 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the
2372 /// input value to the specified type.  If the type must be extended, it is zero
2373 /// extended.  The conversion must not be narrowing.
2374 const SCEV *
2375 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, const Type *Ty) {
2376   const Type *SrcTy = V->getType();
2377   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2378          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2379          "Cannot noop or zero extend with non-integer arguments!");
2380   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2381          "getNoopOrZeroExtend cannot truncate!");
2382   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2383     return V;  // No conversion
2384   return getZeroExtendExpr(V, Ty);
2385 }
2386
2387 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the
2388 /// input value to the specified type.  If the type must be extended, it is sign
2389 /// extended.  The conversion must not be narrowing.
2390 const SCEV *
2391 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, const Type *Ty) {
2392   const Type *SrcTy = V->getType();
2393   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2394          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2395          "Cannot noop or sign extend with non-integer arguments!");
2396   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2397          "getNoopOrSignExtend cannot truncate!");
2398   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2399     return V;  // No conversion
2400   return getSignExtendExpr(V, Ty);
2401 }
2402
2403 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
2404 /// the input value to the specified type. If the type must be extended,
2405 /// it is extended with unspecified bits. The conversion must not be
2406 /// narrowing.
2407 const SCEV *
2408 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, const Type *Ty) {
2409   const Type *SrcTy = V->getType();
2410   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2411          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2412          "Cannot noop or any extend with non-integer arguments!");
2413   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2414          "getNoopOrAnyExtend cannot truncate!");
2415   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2416     return V;  // No conversion
2417   return getAnyExtendExpr(V, Ty);
2418 }
2419
2420 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
2421 /// input value to the specified type.  The conversion must not be widening.
2422 const SCEV *
2423 ScalarEvolution::getTruncateOrNoop(const SCEV *V, const Type *Ty) {
2424   const Type *SrcTy = V->getType();
2425   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
2426          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
2427          "Cannot truncate or noop with non-integer arguments!");
2428   assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
2429          "getTruncateOrNoop cannot extend!");
2430   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2431     return V;  // No conversion
2432   return getTruncateExpr(V, Ty);
2433 }
2434
2435 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
2436 /// the types using zero-extension, and then perform a umax operation
2437 /// with them.
2438 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
2439                                                         const SCEV *RHS) {
2440   const SCEV *PromotedLHS = LHS;
2441   const SCEV *PromotedRHS = RHS;
2442
2443   if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
2444     PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
2445   else
2446     PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
2447
2448   return getUMaxExpr(PromotedLHS, PromotedRHS);
2449 }
2450
2451 /// getUMinFromMismatchedTypes - Promote the operands to the wider of
2452 /// the types using zero-extension, and then perform a umin operation
2453 /// with them.
2454 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
2455                                                         const SCEV *RHS) {
2456   const SCEV *PromotedLHS = LHS;
2457   const SCEV *PromotedRHS = RHS;
2458
2459   if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
2460     PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
2461   else
2462     PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
2463
2464   return getUMinExpr(PromotedLHS, PromotedRHS);
2465 }
2466
2467 /// PushDefUseChildren - Push users of the given Instruction
2468 /// onto the given Worklist.
2469 static void
2470 PushDefUseChildren(Instruction *I,
2471                    SmallVectorImpl<Instruction *> &Worklist) {
2472   // Push the def-use children onto the Worklist stack.
2473   for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
2474        UI != UE; ++UI)
2475     Worklist.push_back(cast<Instruction>(UI));
2476 }
2477
2478 /// ForgetSymbolicValue - This looks up computed SCEV values for all
2479 /// instructions that depend on the given instruction and removes them from
2480 /// the Scalars map if they reference SymName. This is used during PHI
2481 /// resolution.
2482 void
2483 ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) {
2484   SmallVector<Instruction *, 16> Worklist;
2485   PushDefUseChildren(PN, Worklist);
2486
2487   SmallPtrSet<Instruction *, 8> Visited;
2488   Visited.insert(PN);
2489   while (!Worklist.empty()) {
2490     Instruction *I = Worklist.pop_back_val();
2491     if (!Visited.insert(I)) continue;
2492
2493     std::map<SCEVCallbackVH, const SCEV *>::iterator It =
2494       Scalars.find(static_cast<Value *>(I));
2495     if (It != Scalars.end()) {
2496       // Short-circuit the def-use traversal if the symbolic name
2497       // ceases to appear in expressions.
2498       if (It->second != SymName && !It->second->hasOperand(SymName))
2499         continue;
2500
2501       // SCEVUnknown for a PHI either means that it has an unrecognized
2502       // structure, it's a PHI that's in the progress of being computed
2503       // by createNodeForPHI, or it's a single-value PHI. In the first case,
2504       // additional loop trip count information isn't going to change anything.
2505       // In the second case, createNodeForPHI will perform the necessary
2506       // updates on its own when it gets to that point. In the third, we do
2507       // want to forget the SCEVUnknown.
2508       if (!isa<PHINode>(I) ||
2509           !isa<SCEVUnknown>(It->second) ||
2510           (I != PN && It->second == SymName)) {
2511         ValuesAtScopes.erase(It->second);
2512         Scalars.erase(It);
2513       }
2514     }
2515
2516     PushDefUseChildren(I, Worklist);
2517   }
2518 }
2519
2520 /// createNodeForPHI - PHI nodes have two cases.  Either the PHI node exists in
2521 /// a loop header, making it a potential recurrence, or it doesn't.
2522 ///
2523 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
2524   if (const Loop *L = LI->getLoopFor(PN->getParent()))
2525     if (L->getHeader() == PN->getParent()) {
2526       // The loop may have multiple entrances or multiple exits; we can analyze
2527       // this phi as an addrec if it has a unique entry value and a unique
2528       // backedge value.
2529       Value *BEValueV = 0, *StartValueV = 0;
2530       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
2531         Value *V = PN->getIncomingValue(i);
2532         if (L->contains(PN->getIncomingBlock(i))) {
2533           if (!BEValueV) {
2534             BEValueV = V;
2535           } else if (BEValueV != V) {
2536             BEValueV = 0;
2537             break;
2538           }
2539         } else if (!StartValueV) {
2540           StartValueV = V;
2541         } else if (StartValueV != V) {
2542           StartValueV = 0;
2543           break;
2544         }
2545       }
2546       if (BEValueV && StartValueV) {
2547         // While we are analyzing this PHI node, handle its value symbolically.
2548         const SCEV *SymbolicName = getUnknown(PN);
2549         assert(Scalars.find(PN) == Scalars.end() &&
2550                "PHI node already processed?");
2551         Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
2552
2553         // Using this symbolic name for the PHI, analyze the value coming around
2554         // the back-edge.
2555         const SCEV *BEValue = getSCEV(BEValueV);
2556
2557         // NOTE: If BEValue is loop invariant, we know that the PHI node just
2558         // has a special value for the first iteration of the loop.
2559
2560         // If the value coming around the backedge is an add with the symbolic
2561         // value we just inserted, then we found a simple induction variable!
2562         if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
2563           // If there is a single occurrence of the symbolic value, replace it
2564           // with a recurrence.
2565           unsigned FoundIndex = Add->getNumOperands();
2566           for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
2567             if (Add->getOperand(i) == SymbolicName)
2568               if (FoundIndex == e) {
2569                 FoundIndex = i;
2570                 break;
2571               }
2572
2573           if (FoundIndex != Add->getNumOperands()) {
2574             // Create an add with everything but the specified operand.
2575             SmallVector<const SCEV *, 8> Ops;
2576             for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
2577               if (i != FoundIndex)
2578                 Ops.push_back(Add->getOperand(i));
2579             const SCEV *Accum = getAddExpr(Ops);
2580
2581             // This is not a valid addrec if the step amount is varying each
2582             // loop iteration, but is not itself an addrec in this loop.
2583             if (Accum->isLoopInvariant(L) ||
2584                 (isa<SCEVAddRecExpr>(Accum) &&
2585                  cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
2586               bool HasNUW = false;
2587               bool HasNSW = false;
2588
2589               // If the increment doesn't overflow, then neither the addrec nor
2590               // the post-increment will overflow.
2591               if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
2592                 if (OBO->hasNoUnsignedWrap())
2593                   HasNUW = true;
2594                 if (OBO->hasNoSignedWrap())
2595                   HasNSW = true;
2596               }
2597
2598               const SCEV *StartVal = getSCEV(StartValueV);
2599               const SCEV *PHISCEV =
2600                 getAddRecExpr(StartVal, Accum, L, HasNUW, HasNSW);
2601
2602               // Since the no-wrap flags are on the increment, they apply to the
2603               // post-incremented value as well.
2604               if (Accum->isLoopInvariant(L))
2605                 (void)getAddRecExpr(getAddExpr(StartVal, Accum),
2606                                     Accum, L, HasNUW, HasNSW);
2607
2608               // Okay, for the entire analysis of this edge we assumed the PHI
2609               // to be symbolic.  We now need to go back and purge all of the
2610               // entries for the scalars that use the symbolic expression.
2611               ForgetSymbolicName(PN, SymbolicName);
2612               Scalars[SCEVCallbackVH(PN, this)] = PHISCEV;
2613               return PHISCEV;
2614             }
2615           }
2616         } else if (const SCEVAddRecExpr *AddRec =
2617                      dyn_cast<SCEVAddRecExpr>(BEValue)) {
2618           // Otherwise, this could be a loop like this:
2619           //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
2620           // In this case, j = {1,+,1}  and BEValue is j.
2621           // Because the other in-value of i (0) fits the evolution of BEValue
2622           // i really is an addrec evolution.
2623           if (AddRec->getLoop() == L && AddRec->isAffine()) {
2624             const SCEV *StartVal = getSCEV(StartValueV);
2625
2626             // If StartVal = j.start - j.stride, we can use StartVal as the
2627             // initial step of the addrec evolution.
2628             if (StartVal == getMinusSCEV(AddRec->getOperand(0),
2629                                          AddRec->getOperand(1))) {
2630               const SCEV *PHISCEV =
2631                  getAddRecExpr(StartVal, AddRec->getOperand(1), L);
2632
2633               // Okay, for the entire analysis of this edge we assumed the PHI
2634               // to be symbolic.  We now need to go back and purge all of the
2635               // entries for the scalars that use the symbolic expression.
2636               ForgetSymbolicName(PN, SymbolicName);
2637               Scalars[SCEVCallbackVH(PN, this)] = PHISCEV;
2638               return PHISCEV;
2639             }
2640           }
2641         }
2642       }
2643     }
2644
2645   // If the PHI has a single incoming value, follow that value, unless the
2646   // PHI's incoming blocks are in a different loop, in which case doing so
2647   // risks breaking LCSSA form. Instcombine would normally zap these, but
2648   // it doesn't have DominatorTree information, so it may miss cases.
2649   if (Value *V = PN->hasConstantValue(DT)) {
2650     bool AllSameLoop = true;
2651     Loop *PNLoop = LI->getLoopFor(PN->getParent());
2652     for (size_t i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
2653       if (LI->getLoopFor(PN->getIncomingBlock(i)) != PNLoop) {
2654         AllSameLoop = false;
2655         break;
2656       }
2657     if (AllSameLoop)
2658       return getSCEV(V);
2659   }
2660
2661   // If it's not a loop phi, we can't handle it yet.
2662   return getUnknown(PN);
2663 }
2664
2665 /// createNodeForGEP - Expand GEP instructions into add and multiply
2666 /// operations. This allows them to be analyzed by regular SCEV code.
2667 ///
2668 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) {
2669
2670   bool InBounds = GEP->isInBounds();
2671   const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType());
2672   Value *Base = GEP->getOperand(0);
2673   // Don't attempt to analyze GEPs over unsized objects.
2674   if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
2675     return getUnknown(GEP);
2676   const SCEV *TotalOffset = getConstant(IntPtrTy, 0);
2677   gep_type_iterator GTI = gep_type_begin(GEP);
2678   for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()),
2679                                       E = GEP->op_end();
2680        I != E; ++I) {
2681     Value *Index = *I;
2682     // Compute the (potentially symbolic) offset in bytes for this index.
2683     if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
2684       // For a struct, add the member offset.
2685       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
2686       TotalOffset = getAddExpr(TotalOffset,
2687                                getOffsetOfExpr(STy, FieldNo),
2688                                /*HasNUW=*/false, /*HasNSW=*/InBounds);
2689     } else {
2690       // For an array, add the element offset, explicitly scaled.
2691       const SCEV *LocalOffset = getSCEV(Index);
2692       // Getelementptr indices are signed.
2693       LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy);
2694       // Lower "inbounds" GEPs to NSW arithmetic.
2695       LocalOffset = getMulExpr(LocalOffset, getSizeOfExpr(*GTI),
2696                                /*HasNUW=*/false, /*HasNSW=*/InBounds);
2697       TotalOffset = getAddExpr(TotalOffset, LocalOffset,
2698                                /*HasNUW=*/false, /*HasNSW=*/InBounds);
2699     }
2700   }
2701   return getAddExpr(getSCEV(Base), TotalOffset,
2702                     /*HasNUW=*/false, /*HasNSW=*/InBounds);
2703 }
2704
2705 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
2706 /// guaranteed to end in (at every loop iteration).  It is, at the same time,
2707 /// the minimum number of times S is divisible by 2.  For example, given {4,+,8}
2708 /// it returns 2.  If S is guaranteed to be 0, it returns the bitwidth of S.
2709 uint32_t
2710 ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
2711   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
2712     return C->getValue()->getValue().countTrailingZeros();
2713
2714   if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
2715     return std::min(GetMinTrailingZeros(T->getOperand()),
2716                     (uint32_t)getTypeSizeInBits(T->getType()));
2717
2718   if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
2719     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
2720     return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
2721              getTypeSizeInBits(E->getType()) : OpRes;
2722   }
2723
2724   if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
2725     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
2726     return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
2727              getTypeSizeInBits(E->getType()) : OpRes;
2728   }
2729
2730   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
2731     // The result is the min of all operands results.
2732     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
2733     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
2734       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
2735     return MinOpRes;
2736   }
2737
2738   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
2739     // The result is the sum of all operands results.
2740     uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
2741     uint32_t BitWidth = getTypeSizeInBits(M->getType());
2742     for (unsigned i = 1, e = M->getNumOperands();
2743          SumOpRes != BitWidth && i != e; ++i)
2744       SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
2745                           BitWidth);
2746     return SumOpRes;
2747   }
2748
2749   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
2750     // The result is the min of all operands results.
2751     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
2752     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
2753       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
2754     return MinOpRes;
2755   }
2756
2757   if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
2758     // The result is the min of all operands results.
2759     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
2760     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
2761       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
2762     return MinOpRes;
2763   }
2764
2765   if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
2766     // The result is the min of all operands results.
2767     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
2768     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
2769       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
2770     return MinOpRes;
2771   }
2772
2773   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2774     // For a SCEVUnknown, ask ValueTracking.
2775     unsigned BitWidth = getTypeSizeInBits(U->getType());
2776     APInt Mask = APInt::getAllOnesValue(BitWidth);
2777     APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
2778     ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones);
2779     return Zeros.countTrailingOnes();
2780   }
2781
2782   // SCEVUDivExpr
2783   return 0;
2784 }
2785
2786 /// getUnsignedRange - Determine the unsigned range for a particular SCEV.
2787 ///
2788 ConstantRange
2789 ScalarEvolution::getUnsignedRange(const SCEV *S) {
2790
2791   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
2792     return ConstantRange(C->getValue()->getValue());
2793
2794   unsigned BitWidth = getTypeSizeInBits(S->getType());
2795   ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
2796
2797   // If the value has known zeros, the maximum unsigned value will have those
2798   // known zeros as well.
2799   uint32_t TZ = GetMinTrailingZeros(S);
2800   if (TZ != 0)
2801     ConservativeResult =
2802       ConstantRange(APInt::getMinValue(BitWidth),
2803                     APInt::getMaxValue(BitWidth).lshr(TZ).shl(TZ) + 1);
2804
2805   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
2806     ConstantRange X = getUnsignedRange(Add->getOperand(0));
2807     for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
2808       X = X.add(getUnsignedRange(Add->getOperand(i)));
2809     return ConservativeResult.intersectWith(X);
2810   }
2811
2812   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
2813     ConstantRange X = getUnsignedRange(Mul->getOperand(0));
2814     for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
2815       X = X.multiply(getUnsignedRange(Mul->getOperand(i)));
2816     return ConservativeResult.intersectWith(X);
2817   }
2818
2819   if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
2820     ConstantRange X = getUnsignedRange(SMax->getOperand(0));
2821     for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
2822       X = X.smax(getUnsignedRange(SMax->getOperand(i)));
2823     return ConservativeResult.intersectWith(X);
2824   }
2825
2826   if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
2827     ConstantRange X = getUnsignedRange(UMax->getOperand(0));
2828     for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
2829       X = X.umax(getUnsignedRange(UMax->getOperand(i)));
2830     return ConservativeResult.intersectWith(X);
2831   }
2832
2833   if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
2834     ConstantRange X = getUnsignedRange(UDiv->getLHS());
2835     ConstantRange Y = getUnsignedRange(UDiv->getRHS());
2836     return ConservativeResult.intersectWith(X.udiv(Y));
2837   }
2838
2839   if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
2840     ConstantRange X = getUnsignedRange(ZExt->getOperand());
2841     return ConservativeResult.intersectWith(X.zeroExtend(BitWidth));
2842   }
2843
2844   if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
2845     ConstantRange X = getUnsignedRange(SExt->getOperand());
2846     return ConservativeResult.intersectWith(X.signExtend(BitWidth));
2847   }
2848
2849   if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
2850     ConstantRange X = getUnsignedRange(Trunc->getOperand());
2851     return ConservativeResult.intersectWith(X.truncate(BitWidth));
2852   }
2853
2854   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
2855     // If there's no unsigned wrap, the value will never be less than its
2856     // initial value.
2857     if (AddRec->hasNoUnsignedWrap())
2858       if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart()))
2859         if (!C->getValue()->isZero())
2860           ConservativeResult =
2861             ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0));
2862
2863     // TODO: non-affine addrec
2864     if (AddRec->isAffine()) {
2865       const Type *Ty = AddRec->getType();
2866       const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
2867       if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
2868           getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
2869         MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
2870
2871         const SCEV *Start = AddRec->getStart();
2872         const SCEV *Step = AddRec->getStepRecurrence(*this);
2873
2874         ConstantRange StartRange = getUnsignedRange(Start);
2875         ConstantRange StepRange = getSignedRange(Step);
2876         ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
2877         ConstantRange EndRange =
2878           StartRange.add(MaxBECountRange.multiply(StepRange));
2879
2880         // Check for overflow. This must be done with ConstantRange arithmetic
2881         // because we could be called from within the ScalarEvolution overflow
2882         // checking code.
2883         ConstantRange ExtStartRange = StartRange.zextOrTrunc(BitWidth*2+1);
2884         ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1);
2885         ConstantRange ExtMaxBECountRange =
2886           MaxBECountRange.zextOrTrunc(BitWidth*2+1);
2887         ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1);
2888         if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) !=
2889             ExtEndRange)
2890           return ConservativeResult;
2891
2892         APInt Min = APIntOps::umin(StartRange.getUnsignedMin(),
2893                                    EndRange.getUnsignedMin());
2894         APInt Max = APIntOps::umax(StartRange.getUnsignedMax(),
2895                                    EndRange.getUnsignedMax());
2896         if (Min.isMinValue() && Max.isMaxValue())
2897           return ConservativeResult;
2898         return ConservativeResult.intersectWith(ConstantRange(Min, Max+1));
2899       }
2900     }
2901
2902     return ConservativeResult;
2903   }
2904
2905   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2906     // For a SCEVUnknown, ask ValueTracking.
2907     APInt Mask = APInt::getAllOnesValue(BitWidth);
2908     APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
2909     ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD);
2910     if (Ones == ~Zeros + 1)
2911       return ConservativeResult;
2912     return ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1));
2913   }
2914
2915   return ConservativeResult;
2916 }
2917
2918 /// getSignedRange - Determine the signed range for a particular SCEV.
2919 ///
2920 ConstantRange
2921 ScalarEvolution::getSignedRange(const SCEV *S) {
2922
2923   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
2924     return ConstantRange(C->getValue()->getValue());
2925
2926   unsigned BitWidth = getTypeSizeInBits(S->getType());
2927   ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
2928
2929   // If the value has known zeros, the maximum signed value will have those
2930   // known zeros as well.
2931   uint32_t TZ = GetMinTrailingZeros(S);
2932   if (TZ != 0)
2933     ConservativeResult =
2934       ConstantRange(APInt::getSignedMinValue(BitWidth),
2935                     APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
2936
2937   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
2938     ConstantRange X = getSignedRange(Add->getOperand(0));
2939     for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
2940       X = X.add(getSignedRange(Add->getOperand(i)));
2941     return ConservativeResult.intersectWith(X);
2942   }
2943
2944   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
2945     ConstantRange X = getSignedRange(Mul->getOperand(0));
2946     for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
2947       X = X.multiply(getSignedRange(Mul->getOperand(i)));
2948     return ConservativeResult.intersectWith(X);
2949   }
2950
2951   if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
2952     ConstantRange X = getSignedRange(SMax->getOperand(0));
2953     for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
2954       X = X.smax(getSignedRange(SMax->getOperand(i)));
2955     return ConservativeResult.intersectWith(X);
2956   }
2957
2958   if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
2959     ConstantRange X = getSignedRange(UMax->getOperand(0));
2960     for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
2961       X = X.umax(getSignedRange(UMax->getOperand(i)));
2962     return ConservativeResult.intersectWith(X);
2963   }
2964
2965   if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
2966     ConstantRange X = getSignedRange(UDiv->getLHS());
2967     ConstantRange Y = getSignedRange(UDiv->getRHS());
2968     return ConservativeResult.intersectWith(X.udiv(Y));
2969   }
2970
2971   if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) {
2972     ConstantRange X = getSignedRange(ZExt->getOperand());
2973     return ConservativeResult.intersectWith(X.zeroExtend(BitWidth));
2974   }
2975
2976   if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) {
2977     ConstantRange X = getSignedRange(SExt->getOperand());
2978     return ConservativeResult.intersectWith(X.signExtend(BitWidth));
2979   }
2980
2981   if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) {
2982     ConstantRange X = getSignedRange(Trunc->getOperand());
2983     return ConservativeResult.intersectWith(X.truncate(BitWidth));
2984   }
2985
2986   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
2987     // If there's no signed wrap, and all the operands have the same sign or
2988     // zero, the value won't ever change sign.
2989     if (AddRec->hasNoSignedWrap()) {
2990       bool AllNonNeg = true;
2991       bool AllNonPos = true;
2992       for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
2993         if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false;
2994         if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false;
2995       }
2996       if (AllNonNeg)
2997         ConservativeResult = ConservativeResult.intersectWith(
2998           ConstantRange(APInt(BitWidth, 0),
2999                         APInt::getSignedMinValue(BitWidth)));
3000       else if (AllNonPos)
3001         ConservativeResult = ConservativeResult.intersectWith(
3002           ConstantRange(APInt::getSignedMinValue(BitWidth),
3003                         APInt(BitWidth, 1)));
3004     }
3005
3006     // TODO: non-affine addrec
3007     if (AddRec->isAffine()) {
3008       const Type *Ty = AddRec->getType();
3009       const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop());
3010       if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
3011           getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) {
3012         MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty);
3013
3014         const SCEV *Start = AddRec->getStart();
3015         const SCEV *Step = AddRec->getStepRecurrence(*this);
3016
3017         ConstantRange StartRange = getSignedRange(Start);
3018         ConstantRange StepRange = getSignedRange(Step);
3019         ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount);
3020         ConstantRange EndRange =
3021           StartRange.add(MaxBECountRange.multiply(StepRange));
3022
3023         // Check for overflow. This must be done with ConstantRange arithmetic
3024         // because we could be called from within the ScalarEvolution overflow
3025         // checking code.
3026         ConstantRange ExtStartRange = StartRange.sextOrTrunc(BitWidth*2+1);
3027         ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1);
3028         ConstantRange ExtMaxBECountRange =
3029           MaxBECountRange.zextOrTrunc(BitWidth*2+1);
3030         ConstantRange ExtEndRange = EndRange.sextOrTrunc(BitWidth*2+1);
3031         if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) !=
3032             ExtEndRange)
3033           return ConservativeResult;
3034
3035         APInt Min = APIntOps::smin(StartRange.getSignedMin(),
3036                                    EndRange.getSignedMin());
3037         APInt Max = APIntOps::smax(StartRange.getSignedMax(),
3038                                    EndRange.getSignedMax());
3039         if (Min.isMinSignedValue() && Max.isMaxSignedValue())
3040           return ConservativeResult;
3041         return ConservativeResult.intersectWith(ConstantRange(Min, Max+1));
3042       }
3043     }
3044
3045     return ConservativeResult;
3046   }
3047
3048   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
3049     // For a SCEVUnknown, ask ValueTracking.
3050     if (!U->getValue()->getType()->isIntegerTy() && !TD)
3051       return ConservativeResult;
3052     unsigned NS = ComputeNumSignBits(U->getValue(), TD);
3053     if (NS == 1)
3054       return ConservativeResult;
3055     return ConservativeResult.intersectWith(
3056       ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1),
3057                     APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1));
3058   }
3059
3060   return ConservativeResult;
3061 }
3062
3063 /// createSCEV - We know that there is no SCEV for the specified value.
3064 /// Analyze the expression.
3065 ///
3066 const SCEV *ScalarEvolution::createSCEV(Value *V) {
3067   if (!isSCEVable(V->getType()))
3068     return getUnknown(V);
3069
3070   unsigned Opcode = Instruction::UserOp1;
3071   if (Instruction *I = dyn_cast<Instruction>(V)) {
3072     Opcode = I->getOpcode();
3073
3074     // Don't attempt to analyze instructions in blocks that aren't
3075     // reachable. Such instructions don't matter, and they aren't required
3076     // to obey basic rules for definitions dominating uses which this
3077     // analysis depends on.
3078     if (!DT->isReachableFromEntry(I->getParent()))
3079       return getUnknown(V);
3080   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
3081     Opcode = CE->getOpcode();
3082   else if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
3083     return getConstant(CI);
3084   else if (isa<ConstantPointerNull>(V))
3085     return getConstant(V->getType(), 0);
3086   else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
3087     return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee());
3088   else
3089     return getUnknown(V);
3090
3091   Operator *U = cast<Operator>(V);
3092   switch (Opcode) {
3093   case Instruction::Add:
3094     // Don't transfer the NSW and NUW bits from the Add instruction to the
3095     // Add expression, because the Instruction may be guarded by control
3096     // flow and the no-overflow bits may not be valid for the expression in
3097     // any context.
3098     return getAddExpr(getSCEV(U->getOperand(0)),
3099                       getSCEV(U->getOperand(1)));
3100   case Instruction::Mul:
3101     // Don't transfer the NSW and NUW bits from the Mul instruction to the
3102     // Mul expression, as with Add.
3103     return getMulExpr(getSCEV(U->getOperand(0)),
3104                       getSCEV(U->getOperand(1)));
3105   case Instruction::UDiv:
3106     return getUDivExpr(getSCEV(U->getOperand(0)),
3107                        getSCEV(U->getOperand(1)));
3108   case Instruction::Sub:
3109     return getMinusSCEV(getSCEV(U->getOperand(0)),
3110                         getSCEV(U->getOperand(1)));
3111   case Instruction::And:
3112     // For an expression like x&255 that merely masks off the high bits,
3113     // use zext(trunc(x)) as the SCEV expression.
3114     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
3115       if (CI->isNullValue())
3116         return getSCEV(U->getOperand(1));
3117       if (CI->isAllOnesValue())
3118         return getSCEV(U->getOperand(0));
3119       const APInt &A = CI->getValue();
3120
3121       // Instcombine's ShrinkDemandedConstant may strip bits out of
3122       // constants, obscuring what would otherwise be a low-bits mask.
3123       // Use ComputeMaskedBits to compute what ShrinkDemandedConstant
3124       // knew about to reconstruct a low-bits mask value.
3125       unsigned LZ = A.countLeadingZeros();
3126       unsigned BitWidth = A.getBitWidth();
3127       APInt AllOnes = APInt::getAllOnesValue(BitWidth);
3128       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
3129       ComputeMaskedBits(U->getOperand(0), AllOnes, KnownZero, KnownOne, TD);
3130
3131       APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ);
3132
3133       if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
3134         return
3135           getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
3136                                 IntegerType::get(getContext(), BitWidth - LZ)),
3137                             U->getType());
3138     }
3139     break;
3140
3141   case Instruction::Or:
3142     // If the RHS of the Or is a constant, we may have something like:
3143     // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
3144     // optimizations will transparently handle this case.
3145     //
3146     // In order for this transformation to be safe, the LHS must be of the
3147     // form X*(2^n) and the Or constant must be less than 2^n.
3148     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
3149       const SCEV *LHS = getSCEV(U->getOperand(0));
3150       const APInt &CIVal = CI->getValue();
3151       if (GetMinTrailingZeros(LHS) >=
3152           (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
3153         // Build a plain add SCEV.
3154         const SCEV *S = getAddExpr(LHS, getSCEV(CI));
3155         // If the LHS of the add was an addrec and it has no-wrap flags,
3156         // transfer the no-wrap flags, since an or won't introduce a wrap.
3157         if (const SCEVAddRecExpr *NewAR = dyn_cast<SCEVAddRecExpr>(S)) {
3158           const SCEVAddRecExpr *OldAR = cast<SCEVAddRecExpr>(LHS);
3159           if (OldAR->hasNoUnsignedWrap())
3160             const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoUnsignedWrap(true);
3161           if (OldAR->hasNoSignedWrap())
3162             const_cast<SCEVAddRecExpr *>(NewAR)->setHasNoSignedWrap(true);
3163         }
3164         return S;
3165       }
3166     }
3167     break;
3168   case Instruction::Xor:
3169     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
3170       // If the RHS of the xor is a signbit, then this is just an add.
3171       // Instcombine turns add of signbit into xor as a strength reduction step.
3172       if (CI->getValue().isSignBit())
3173         return getAddExpr(getSCEV(U->getOperand(0)),
3174                           getSCEV(U->getOperand(1)));
3175
3176       // If the RHS of xor is -1, then this is a not operation.
3177       if (CI->isAllOnesValue())
3178         return getNotSCEV(getSCEV(U->getOperand(0)));
3179
3180       // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
3181       // This is a variant of the check for xor with -1, and it handles
3182       // the case where instcombine has trimmed non-demanded bits out
3183       // of an xor with -1.
3184       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U->getOperand(0)))
3185         if (ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1)))
3186           if (BO->getOpcode() == Instruction::And &&
3187               LCI->getValue() == CI->getValue())
3188             if (const SCEVZeroExtendExpr *Z =
3189                   dyn_cast<SCEVZeroExtendExpr>(getSCEV(U->getOperand(0)))) {
3190               const Type *UTy = U->getType();
3191               const SCEV *Z0 = Z->getOperand();
3192               const Type *Z0Ty = Z0->getType();
3193               unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
3194
3195               // If C is a low-bits mask, the zero extend is serving to
3196               // mask off the high bits. Complement the operand and
3197               // re-apply the zext.
3198               if (APIntOps::isMask(Z0TySize, CI->getValue()))
3199                 return getZeroExtendExpr(getNotSCEV(Z0), UTy);
3200
3201               // If C is a single bit, it may be in the sign-bit position
3202               // before the zero-extend. In this case, represent the xor
3203               // using an add, which is equivalent, and re-apply the zext.
3204               APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize);
3205               if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
3206                   Trunc.isSignBit())
3207                 return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
3208                                          UTy);
3209             }
3210     }
3211     break;
3212
3213   case Instruction::Shl:
3214     // Turn shift left of a constant amount into a multiply.
3215     if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
3216       uint32_t BitWidth = cast<IntegerType>(U->getType())->getBitWidth();
3217
3218       // If the shift count is not less than the bitwidth, the result of
3219       // the shift is undefined. Don't try to analyze it, because the
3220       // resolution chosen here may differ from the resolution chosen in
3221       // other parts of the compiler.
3222       if (SA->getValue().uge(BitWidth))
3223         break;
3224
3225       Constant *X = ConstantInt::get(getContext(),
3226         APInt(BitWidth, 1).shl(SA->getZExtValue()));
3227       return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
3228     }
3229     break;
3230
3231   case Instruction::LShr:
3232     // Turn logical shift right of a constant into a unsigned divide.
3233     if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
3234       uint32_t BitWidth = cast<IntegerType>(U->getType())->getBitWidth();
3235
3236       // If the shift count is not less than the bitwidth, the result of
3237       // the shift is undefined. Don't try to analyze it, because the
3238       // resolution chosen here may differ from the resolution chosen in
3239       // other parts of the compiler.
3240       if (SA->getValue().uge(BitWidth))
3241         break;
3242
3243       Constant *X = ConstantInt::get(getContext(),
3244         APInt(BitWidth, 1).shl(SA->getZExtValue()));
3245       return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
3246     }
3247     break;
3248
3249   case Instruction::AShr:
3250     // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression.
3251     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1)))
3252       if (Operator *L = dyn_cast<Operator>(U->getOperand(0)))
3253         if (L->getOpcode() == Instruction::Shl &&
3254             L->getOperand(1) == U->getOperand(1)) {
3255           uint64_t BitWidth = getTypeSizeInBits(U->getType());
3256
3257           // If the shift count is not less than the bitwidth, the result of
3258           // the shift is undefined. Don't try to analyze it, because the
3259           // resolution chosen here may differ from the resolution chosen in
3260           // other parts of the compiler.
3261           if (CI->getValue().uge(BitWidth))
3262             break;
3263
3264           uint64_t Amt = BitWidth - CI->getZExtValue();
3265           if (Amt == BitWidth)
3266             return getSCEV(L->getOperand(0));       // shift by zero --> noop
3267           return
3268             getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
3269                                               IntegerType::get(getContext(),
3270                                                                Amt)),
3271                               U->getType());
3272         }
3273     break;
3274
3275   case Instruction::Trunc:
3276     return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
3277
3278   case Instruction::ZExt:
3279     return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
3280
3281   case Instruction::SExt:
3282     return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
3283
3284   case Instruction::BitCast:
3285     // BitCasts are no-op casts so we just eliminate the cast.
3286     if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
3287       return getSCEV(U->getOperand(0));
3288     break;
3289
3290   // It's tempting to handle inttoptr and ptrtoint as no-ops, however this can
3291   // lead to pointer expressions which cannot safely be expanded to GEPs,
3292   // because ScalarEvolution doesn't respect the GEP aliasing rules when
3293   // simplifying integer expressions.
3294
3295   case Instruction::GetElementPtr:
3296     return createNodeForGEP(cast<GEPOperator>(U));
3297
3298   case Instruction::PHI:
3299     return createNodeForPHI(cast<PHINode>(U));
3300
3301   case Instruction::Select:
3302     // This could be a smax or umax that was lowered earlier.
3303     // Try to recover it.
3304     if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
3305       Value *LHS = ICI->getOperand(0);
3306       Value *RHS = ICI->getOperand(1);
3307       switch (ICI->getPredicate()) {
3308       case ICmpInst::ICMP_SLT:
3309       case ICmpInst::ICMP_SLE:
3310         std::swap(LHS, RHS);
3311         // fall through
3312       case ICmpInst::ICMP_SGT:
3313       case ICmpInst::ICMP_SGE:
3314         // a >s b ? a+x : b+x  ->  smax(a, b)+x
3315         // a >s b ? b+x : a+x  ->  smin(a, b)+x
3316         if (LHS->getType() == U->getType()) {
3317           const SCEV *LS = getSCEV(LHS);
3318           const SCEV *RS = getSCEV(RHS);
3319           const SCEV *LA = getSCEV(U->getOperand(1));
3320           const SCEV *RA = getSCEV(U->getOperand(2));
3321           const SCEV *LDiff = getMinusSCEV(LA, LS);
3322           const SCEV *RDiff = getMinusSCEV(RA, RS);
3323           if (LDiff == RDiff)
3324             return getAddExpr(getSMaxExpr(LS, RS), LDiff);
3325           LDiff = getMinusSCEV(LA, RS);
3326           RDiff = getMinusSCEV(RA, LS);
3327           if (LDiff == RDiff)
3328             return getAddExpr(getSMinExpr(LS, RS), LDiff);
3329         }
3330         break;
3331       case ICmpInst::ICMP_ULT:
3332       case ICmpInst::ICMP_ULE:
3333         std::swap(LHS, RHS);
3334         // fall through
3335       case ICmpInst::ICMP_UGT:
3336       case ICmpInst::ICMP_UGE:
3337         // a >u b ? a+x : b+x  ->  umax(a, b)+x
3338         // a >u b ? b+x : a+x  ->  umin(a, b)+x
3339         if (LHS->getType() == U->getType()) {
3340           const SCEV *LS = getSCEV(LHS);
3341           const SCEV *RS = getSCEV(RHS);
3342           const SCEV *LA = getSCEV(U->getOperand(1));
3343           const SCEV *RA = getSCEV(U->getOperand(2));
3344           const SCEV *LDiff = getMinusSCEV(LA, LS);
3345           const SCEV *RDiff = getMinusSCEV(RA, RS);
3346           if (LDiff == RDiff)
3347             return getAddExpr(getUMaxExpr(LS, RS), LDiff);
3348           LDiff = getMinusSCEV(LA, RS);
3349           RDiff = getMinusSCEV(RA, LS);
3350           if (LDiff == RDiff)
3351             return getAddExpr(getUMinExpr(LS, RS), LDiff);
3352         }
3353         break;
3354       case ICmpInst::ICMP_NE:
3355         // n != 0 ? n+x : 1+x  ->  umax(n, 1)+x
3356         if (LHS->getType() == U->getType() &&
3357             isa<ConstantInt>(RHS) &&
3358             cast<ConstantInt>(RHS)->isZero()) {
3359           const SCEV *One = getConstant(LHS->getType(), 1);
3360           const SCEV *LS = getSCEV(LHS);
3361           const SCEV *LA = getSCEV(U->getOperand(1));
3362           const SCEV *RA = getSCEV(U->getOperand(2));
3363           const SCEV *LDiff = getMinusSCEV(LA, LS);
3364           const SCEV *RDiff = getMinusSCEV(RA, One);
3365           if (LDiff == RDiff)
3366             return getAddExpr(getUMaxExpr(LS, One), LDiff);
3367         }
3368         break;
3369       case ICmpInst::ICMP_EQ:
3370         // n == 0 ? 1+x : n+x  ->  umax(n, 1)+x
3371         if (LHS->getType() == U->getType() &&
3372             isa<ConstantInt>(RHS) &&
3373             cast<ConstantInt>(RHS)->isZero()) {
3374           const SCEV *One = getConstant(LHS->getType(), 1);
3375           const SCEV *LS = getSCEV(LHS);
3376           const SCEV *LA = getSCEV(U->getOperand(1));
3377           const SCEV *RA = getSCEV(U->getOperand(2));
3378           const SCEV *LDiff = getMinusSCEV(LA, One);
3379           const SCEV *RDiff = getMinusSCEV(RA, LS);
3380           if (LDiff == RDiff)
3381             return getAddExpr(getUMaxExpr(LS, One), LDiff);
3382         }
3383         break;
3384       default:
3385         break;
3386       }
3387     }
3388
3389   default: // We cannot analyze this expression.
3390     break;
3391   }
3392
3393   return getUnknown(V);
3394 }
3395
3396
3397
3398 //===----------------------------------------------------------------------===//
3399 //                   Iteration Count Computation Code
3400 //
3401
3402 /// getBackedgeTakenCount - If the specified loop has a predictable
3403 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
3404 /// object. The backedge-taken count is the number of times the loop header
3405 /// will be branched to from within the loop. This is one less than the
3406 /// trip count of the loop, since it doesn't count the first iteration,
3407 /// when the header is branched to from outside the loop.
3408 ///
3409 /// Note that it is not valid to call this method on a loop without a
3410 /// loop-invariant backedge-taken count (see
3411 /// hasLoopInvariantBackedgeTakenCount).
3412 ///
3413 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
3414   return getBackedgeTakenInfo(L).Exact;
3415 }
3416
3417 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
3418 /// return the least SCEV value that is known never to be less than the
3419 /// actual backedge taken count.
3420 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
3421   return getBackedgeTakenInfo(L).Max;
3422 }
3423
3424 /// PushLoopPHIs - Push PHI nodes in the header of the given loop
3425 /// onto the given Worklist.
3426 static void
3427 PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
3428   BasicBlock *Header = L->getHeader();
3429
3430   // Push all Loop-header PHIs onto the Worklist stack.
3431   for (BasicBlock::iterator I = Header->begin();
3432        PHINode *PN = dyn_cast<PHINode>(I); ++I)
3433     Worklist.push_back(PN);
3434 }
3435
3436 const ScalarEvolution::BackedgeTakenInfo &
3437 ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
3438   // Initially insert a CouldNotCompute for this loop. If the insertion
3439   // succeeds, proceed to actually compute a backedge-taken count and
3440   // update the value. The temporary CouldNotCompute value tells SCEV
3441   // code elsewhere that it shouldn't attempt to request a new
3442   // backedge-taken count, which could result in infinite recursion.
3443   std::pair<std::map<const Loop *, BackedgeTakenInfo>::iterator, bool> Pair =
3444     BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
3445   if (Pair.second) {
3446     BackedgeTakenInfo BECount = ComputeBackedgeTakenCount(L);
3447     if (BECount.Exact != getCouldNotCompute()) {
3448       assert(BECount.Exact->isLoopInvariant(L) &&
3449              BECount.Max->isLoopInvariant(L) &&
3450              "Computed backedge-taken count isn't loop invariant for loop!");
3451       ++NumTripCountsComputed;
3452
3453       // Update the value in the map.
3454       Pair.first->second = BECount;
3455     } else {
3456       if (BECount.Max != getCouldNotCompute())
3457         // Update the value in the map.
3458         Pair.first->second = BECount;
3459       if (isa<PHINode>(L->getHeader()->begin()))
3460         // Only count loops that have phi nodes as not being computable.
3461         ++NumTripCountsNotComputed;
3462     }
3463
3464     // Now that we know more about the trip count for this loop, forget any
3465     // existing SCEV values for PHI nodes in this loop since they are only
3466     // conservative estimates made without the benefit of trip count
3467     // information. This is similar to the code in forgetLoop, except that
3468     // it handles SCEVUnknown PHI nodes specially.
3469     if (BECount.hasAnyInfo()) {
3470       SmallVector<Instruction *, 16> Worklist;
3471       PushLoopPHIs(L, Worklist);
3472
3473       SmallPtrSet<Instruction *, 8> Visited;
3474       while (!Worklist.empty()) {
3475         Instruction *I = Worklist.pop_back_val();
3476         if (!Visited.insert(I)) continue;
3477
3478         std::map<SCEVCallbackVH, const SCEV *>::iterator It =
3479           Scalars.find(static_cast<Value *>(I));
3480         if (It != Scalars.end()) {
3481           // SCEVUnknown for a PHI either means that it has an unrecognized
3482           // structure, or it's a PHI that's in the progress of being computed
3483           // by createNodeForPHI.  In the former case, additional loop trip
3484           // count information isn't going to change anything. In the later
3485           // case, createNodeForPHI will perform the necessary updates on its
3486           // own when it gets to that point.
3487           if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) {
3488             ValuesAtScopes.erase(It->second);
3489             Scalars.erase(It);
3490           }
3491           if (PHINode *PN = dyn_cast<PHINode>(I))
3492             ConstantEvolutionLoopExitValue.erase(PN);
3493         }
3494
3495         PushDefUseChildren(I, Worklist);
3496       }
3497     }
3498   }
3499   return Pair.first->second;
3500 }
3501
3502 /// forgetLoop - This method should be called by the client when it has
3503 /// changed a loop in a way that may effect ScalarEvolution's ability to
3504 /// compute a trip count, or if the loop is deleted.
3505 void ScalarEvolution::forgetLoop(const Loop *L) {
3506   // Drop any stored trip count value.
3507   BackedgeTakenCounts.erase(L);
3508
3509   // Drop information about expressions based on loop-header PHIs.
3510   SmallVector<Instruction *, 16> Worklist;
3511   PushLoopPHIs(L, Worklist);
3512
3513   SmallPtrSet<Instruction *, 8> Visited;
3514   while (!Worklist.empty()) {
3515     Instruction *I = Worklist.pop_back_val();
3516     if (!Visited.insert(I)) continue;
3517
3518     std::map<SCEVCallbackVH, const SCEV *>::iterator It =
3519       Scalars.find(static_cast<Value *>(I));
3520     if (It != Scalars.end()) {
3521       ValuesAtScopes.erase(It->second);
3522       Scalars.erase(It);
3523       if (PHINode *PN = dyn_cast<PHINode>(I))
3524         ConstantEvolutionLoopExitValue.erase(PN);
3525     }
3526
3527     PushDefUseChildren(I, Worklist);
3528   }
3529 }
3530
3531 /// forgetValue - This method should be called by the client when it has
3532 /// changed a value in a way that may effect its value, or which may
3533 /// disconnect it from a def-use chain linking it to a loop.
3534 void ScalarEvolution::forgetValue(Value *V) {
3535   Instruction *I = dyn_cast<Instruction>(V);
3536   if (!I) return;
3537
3538   // Drop information about expressions based on loop-header PHIs.
3539   SmallVector<Instruction *, 16> Worklist;
3540   Worklist.push_back(I);
3541
3542   SmallPtrSet<Instruction *, 8> Visited;
3543   while (!Worklist.empty()) {
3544     I = Worklist.pop_back_val();
3545     if (!Visited.insert(I)) continue;
3546
3547     std::map<SCEVCallbackVH, const SCEV *>::iterator It =
3548       Scalars.find(static_cast<Value *>(I));
3549     if (It != Scalars.end()) {
3550       ValuesAtScopes.erase(It->second);
3551       Scalars.erase(It);
3552       if (PHINode *PN = dyn_cast<PHINode>(I))
3553         ConstantEvolutionLoopExitValue.erase(PN);
3554     }
3555
3556     PushDefUseChildren(I, Worklist);
3557   }
3558 }
3559
3560 /// ComputeBackedgeTakenCount - Compute the number of times the backedge
3561 /// of the specified loop will execute.
3562 ScalarEvolution::BackedgeTakenInfo
3563 ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
3564   SmallVector<BasicBlock *, 8> ExitingBlocks;
3565   L->getExitingBlocks(ExitingBlocks);
3566
3567   // Examine all exits and pick the most conservative values.
3568   const SCEV *BECount = getCouldNotCompute();
3569   const SCEV *MaxBECount = getCouldNotCompute();
3570   bool CouldNotComputeBECount = false;
3571   for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
3572     BackedgeTakenInfo NewBTI =
3573       ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
3574
3575     if (NewBTI.Exact == getCouldNotCompute()) {
3576       // We couldn't compute an exact value for this exit, so
3577       // we won't be able to compute an exact value for the loop.
3578       CouldNotComputeBECount = true;
3579       BECount = getCouldNotCompute();
3580     } else if (!CouldNotComputeBECount) {
3581       if (BECount == getCouldNotCompute())
3582         BECount = NewBTI.Exact;
3583       else
3584         BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
3585     }
3586     if (MaxBECount == getCouldNotCompute())
3587       MaxBECount = NewBTI.Max;
3588     else if (NewBTI.Max != getCouldNotCompute())
3589       MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
3590   }
3591
3592   return BackedgeTakenInfo(BECount, MaxBECount);
3593 }
3594
3595 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
3596 /// of the specified loop will execute if it exits via the specified block.
3597 ScalarEvolution::BackedgeTakenInfo
3598 ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
3599                                                    BasicBlock *ExitingBlock) {
3600
3601   // Okay, we've chosen an exiting block.  See what condition causes us to
3602   // exit at this block.
3603   //
3604   // FIXME: we should be able to handle switch instructions (with a single exit)
3605   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
3606   if (ExitBr == 0) return getCouldNotCompute();
3607   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
3608
3609   // At this point, we know we have a conditional branch that determines whether
3610   // the loop is exited.  However, we don't know if the branch is executed each
3611   // time through the loop.  If not, then the execution count of the branch will
3612   // not be equal to the trip count of the loop.
3613   //
3614   // Currently we check for this by checking to see if the Exit branch goes to
3615   // the loop header.  If so, we know it will always execute the same number of
3616   // times as the loop.  We also handle the case where the exit block *is* the
3617   // loop header.  This is common for un-rotated loops.
3618   //
3619   // If both of those tests fail, walk up the unique predecessor chain to the
3620   // header, stopping if there is an edge that doesn't exit the loop. If the
3621   // header is reached, the execution count of the branch will be equal to the
3622   // trip count of the loop.
3623   //
3624   //  More extensive analysis could be done to handle more cases here.
3625   //
3626   if (ExitBr->getSuccessor(0) != L->getHeader() &&
3627       ExitBr->getSuccessor(1) != L->getHeader() &&
3628       ExitBr->getParent() != L->getHeader()) {
3629     // The simple checks failed, try climbing the unique predecessor chain
3630     // up to the header.
3631     bool Ok = false;
3632     for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
3633       BasicBlock *Pred = BB->getUniquePredecessor();
3634       if (!Pred)
3635         return getCouldNotCompute();
3636       TerminatorInst *PredTerm = Pred->getTerminator();
3637       for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
3638         BasicBlock *PredSucc = PredTerm->getSuccessor(i);
3639         if (PredSucc == BB)
3640           continue;
3641         // If the predecessor has a successor that isn't BB and isn't
3642         // outside the loop, assume the worst.
3643         if (L->contains(PredSucc))
3644           return getCouldNotCompute();
3645       }
3646       if (Pred == L->getHeader()) {
3647         Ok = true;
3648         break;
3649       }
3650       BB = Pred;
3651     }
3652     if (!Ok)
3653       return getCouldNotCompute();
3654   }
3655
3656   // Proceed to the next level to examine the exit condition expression.
3657   return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
3658                                                ExitBr->getSuccessor(0),
3659                                                ExitBr->getSuccessor(1));
3660 }
3661
3662 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
3663 /// backedge of the specified loop will execute if its exit condition
3664 /// were a conditional branch of ExitCond, TBB, and FBB.
3665 ScalarEvolution::BackedgeTakenInfo
3666 ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
3667                                                        Value *ExitCond,
3668                                                        BasicBlock *TBB,
3669                                                        BasicBlock *FBB) {
3670   // Check if the controlling expression for this loop is an And or Or.
3671   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
3672     if (BO->getOpcode() == Instruction::And) {
3673       // Recurse on the operands of the and.
3674       BackedgeTakenInfo BTI0 =
3675         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3676       BackedgeTakenInfo BTI1 =
3677         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3678       const SCEV *BECount = getCouldNotCompute();
3679       const SCEV *MaxBECount = getCouldNotCompute();
3680       if (L->contains(TBB)) {
3681         // Both conditions must be true for the loop to continue executing.
3682         // Choose the less conservative count.
3683         if (BTI0.Exact == getCouldNotCompute() ||
3684             BTI1.Exact == getCouldNotCompute())
3685           BECount = getCouldNotCompute();
3686         else
3687           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3688         if (BTI0.Max == getCouldNotCompute())
3689           MaxBECount = BTI1.Max;
3690         else if (BTI1.Max == getCouldNotCompute())
3691           MaxBECount = BTI0.Max;
3692         else
3693           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3694       } else {
3695         // Both conditions must be true for the loop to exit.
3696         assert(L->contains(FBB) && "Loop block has no successor in loop!");
3697         if (BTI0.Exact != getCouldNotCompute() &&
3698             BTI1.Exact != getCouldNotCompute())
3699           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3700         if (BTI0.Max != getCouldNotCompute() &&
3701             BTI1.Max != getCouldNotCompute())
3702           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3703       }
3704
3705       return BackedgeTakenInfo(BECount, MaxBECount);
3706     }
3707     if (BO->getOpcode() == Instruction::Or) {
3708       // Recurse on the operands of the or.
3709       BackedgeTakenInfo BTI0 =
3710         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3711       BackedgeTakenInfo BTI1 =
3712         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3713       const SCEV *BECount = getCouldNotCompute();
3714       const SCEV *MaxBECount = getCouldNotCompute();
3715       if (L->contains(FBB)) {
3716         // Both conditions must be false for the loop to continue executing.
3717         // Choose the less conservative count.
3718         if (BTI0.Exact == getCouldNotCompute() ||
3719             BTI1.Exact == getCouldNotCompute())
3720           BECount = getCouldNotCompute();
3721         else
3722           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3723         if (BTI0.Max == getCouldNotCompute())
3724           MaxBECount = BTI1.Max;
3725         else if (BTI1.Max == getCouldNotCompute())
3726           MaxBECount = BTI0.Max;
3727         else
3728           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3729       } else {
3730         // Both conditions must be false for the loop to exit.
3731         assert(L->contains(TBB) && "Loop block has no successor in loop!");
3732         if (BTI0.Exact != getCouldNotCompute() &&
3733             BTI1.Exact != getCouldNotCompute())
3734           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3735         if (BTI0.Max != getCouldNotCompute() &&
3736             BTI1.Max != getCouldNotCompute())
3737           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3738       }
3739
3740       return BackedgeTakenInfo(BECount, MaxBECount);
3741     }
3742   }
3743
3744   // With an icmp, it may be feasible to compute an exact backedge-taken count.
3745   // Proceed to the next level to examine the icmp.
3746   if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
3747     return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB);
3748
3749   // Check for a constant condition. These are normally stripped out by
3750   // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to
3751   // preserve the CFG and is temporarily leaving constant conditions
3752   // in place.
3753   if (ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
3754     if (L->contains(FBB) == !CI->getZExtValue())
3755       // The backedge is always taken.
3756       return getCouldNotCompute();
3757     else
3758       // The backedge is never taken.
3759       return getConstant(CI->getType(), 0);
3760   }
3761
3762   // If it's not an integer or pointer comparison then compute it the hard way.
3763   return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
3764 }
3765
3766 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the
3767 /// backedge of the specified loop will execute if its exit condition
3768 /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
3769 ScalarEvolution::BackedgeTakenInfo
3770 ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
3771                                                            ICmpInst *ExitCond,
3772                                                            BasicBlock *TBB,
3773                                                            BasicBlock *FBB) {
3774
3775   // If the condition was exit on true, convert the condition to exit on false
3776   ICmpInst::Predicate Cond;
3777   if (!L->contains(FBB))
3778     Cond = ExitCond->getPredicate();
3779   else
3780     Cond = ExitCond->getInversePredicate();
3781
3782   // Handle common loops like: for (X = "string"; *X; ++X)
3783   if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
3784     if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
3785       BackedgeTakenInfo ItCnt =
3786         ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
3787       if (ItCnt.hasAnyInfo())
3788         return ItCnt;
3789     }
3790
3791   const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
3792   const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
3793
3794   // Try to evaluate any dependencies out of the loop.
3795   LHS = getSCEVAtScope(LHS, L);
3796   RHS = getSCEVAtScope(RHS, L);
3797
3798   // At this point, we would like to compute how many iterations of the
3799   // loop the predicate will return true for these inputs.
3800   if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
3801     // If there is a loop-invariant, force it into the RHS.
3802     std::swap(LHS, RHS);
3803     Cond = ICmpInst::getSwappedPredicate(Cond);
3804   }
3805
3806   // Simplify the operands before analyzing them.
3807   (void)SimplifyICmpOperands(Cond, LHS, RHS);
3808
3809   // If we have a comparison of a chrec against a constant, try to use value
3810   // ranges to answer this query.
3811   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
3812     if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
3813       if (AddRec->getLoop() == L) {
3814         // Form the constant range.
3815         ConstantRange CompRange(
3816             ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
3817
3818         const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
3819         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
3820       }
3821
3822   switch (Cond) {
3823   case ICmpInst::ICMP_NE: {                     // while (X != Y)
3824     // Convert to: while (X-Y != 0)
3825     BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEV(LHS, RHS), L);
3826     if (BTI.hasAnyInfo()) return BTI;
3827     break;
3828   }
3829   case ICmpInst::ICMP_EQ: {                     // while (X == Y)
3830     // Convert to: while (X-Y == 0)
3831     BackedgeTakenInfo BTI = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
3832     if (BTI.hasAnyInfo()) return BTI;
3833     break;
3834   }
3835   case ICmpInst::ICMP_SLT: {
3836     BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, true);
3837     if (BTI.hasAnyInfo()) return BTI;
3838     break;
3839   }
3840   case ICmpInst::ICMP_SGT: {
3841     BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
3842                                              getNotSCEV(RHS), L, true);
3843     if (BTI.hasAnyInfo()) return BTI;
3844     break;
3845   }
3846   case ICmpInst::ICMP_ULT: {
3847     BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, false);
3848     if (BTI.hasAnyInfo()) return BTI;
3849     break;
3850   }
3851   case ICmpInst::ICMP_UGT: {
3852     BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
3853                                              getNotSCEV(RHS), L, false);
3854     if (BTI.hasAnyInfo()) return BTI;
3855     break;
3856   }
3857   default:
3858 #if 0
3859     dbgs() << "ComputeBackedgeTakenCount ";
3860     if (ExitCond->getOperand(0)->getType()->isUnsigned())
3861       dbgs() << "[unsigned] ";
3862     dbgs() << *LHS << "   "
3863          << Instruction::getOpcodeName(Instruction::ICmp)
3864          << "   " << *RHS << "\n";
3865 #endif
3866     break;
3867   }
3868   return
3869     ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
3870 }
3871
3872 static ConstantInt *
3873 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
3874                                 ScalarEvolution &SE) {
3875   const SCEV *InVal = SE.getConstant(C);
3876   const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE);
3877   assert(isa<SCEVConstant>(Val) &&
3878          "Evaluation of SCEV at constant didn't fold correctly?");
3879   return cast<SCEVConstant>(Val)->getValue();
3880 }
3881
3882 /// GetAddressedElementFromGlobal - Given a global variable with an initializer
3883 /// and a GEP expression (missing the pointer index) indexing into it, return
3884 /// the addressed element of the initializer or null if the index expression is
3885 /// invalid.
3886 static Constant *
3887 GetAddressedElementFromGlobal(GlobalVariable *GV,
3888                               const std::vector<ConstantInt*> &Indices) {
3889   Constant *Init = GV->getInitializer();
3890   for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
3891     uint64_t Idx = Indices[i]->getZExtValue();
3892     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
3893       assert(Idx < CS->getNumOperands() && "Bad struct index!");
3894       Init = cast<Constant>(CS->getOperand(Idx));
3895     } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
3896       if (Idx >= CA->getNumOperands()) return 0;  // Bogus program
3897       Init = cast<Constant>(CA->getOperand(Idx));
3898     } else if (isa<ConstantAggregateZero>(Init)) {
3899       if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
3900         assert(Idx < STy->getNumElements() && "Bad struct index!");
3901         Init = Constant::getNullValue(STy->getElementType(Idx));
3902       } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
3903         if (Idx >= ATy->getNumElements()) return 0;  // Bogus program
3904         Init = Constant::getNullValue(ATy->getElementType());
3905       } else {
3906         llvm_unreachable("Unknown constant aggregate type!");
3907       }
3908       return 0;
3909     } else {
3910       return 0; // Unknown initializer type
3911     }
3912   }
3913   return Init;
3914 }
3915
3916 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
3917 /// 'icmp op load X, cst', try to see if we can compute the backedge
3918 /// execution count.
3919 ScalarEvolution::BackedgeTakenInfo
3920 ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
3921                                                 LoadInst *LI,
3922                                                 Constant *RHS,
3923                                                 const Loop *L,
3924                                                 ICmpInst::Predicate predicate) {
3925   if (LI->isVolatile()) return getCouldNotCompute();
3926
3927   // Check to see if the loaded pointer is a getelementptr of a global.
3928   // TODO: Use SCEV instead of manually grubbing with GEPs.
3929   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3930   if (!GEP) return getCouldNotCompute();
3931
3932   // Make sure that it is really a constant global we are gepping, with an
3933   // initializer, and make sure the first IDX is really 0.
3934   GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
3935   if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() ||
3936       GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
3937       !cast<Constant>(GEP->getOperand(1))->isNullValue())
3938     return getCouldNotCompute();
3939
3940   // Okay, we allow one non-constant index into the GEP instruction.
3941   Value *VarIdx = 0;
3942   std::vector<ConstantInt*> Indexes;
3943   unsigned VarIdxNum = 0;
3944   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
3945     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
3946       Indexes.push_back(CI);
3947     } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
3948       if (VarIdx) return getCouldNotCompute();  // Multiple non-constant idx's.
3949       VarIdx = GEP->getOperand(i);
3950       VarIdxNum = i-2;
3951       Indexes.push_back(0);
3952     }
3953
3954   // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
3955   // Check to see if X is a loop variant variable value now.
3956   const SCEV *Idx = getSCEV(VarIdx);
3957   Idx = getSCEVAtScope(Idx, L);
3958
3959   // We can only recognize very limited forms of loop index expressions, in
3960   // particular, only affine AddRec's like {C1,+,C2}.
3961   const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
3962   if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
3963       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
3964       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
3965     return getCouldNotCompute();
3966
3967   unsigned MaxSteps = MaxBruteForceIterations;
3968   for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
3969     ConstantInt *ItCst = ConstantInt::get(
3970                            cast<IntegerType>(IdxExpr->getType()), IterationNum);
3971     ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
3972
3973     // Form the GEP offset.
3974     Indexes[VarIdxNum] = Val;
3975
3976     Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
3977     if (Result == 0) break;  // Cannot compute!
3978
3979     // Evaluate the condition for this iteration.
3980     Result = ConstantExpr::getICmp(predicate, Result, RHS);
3981     if (!isa<ConstantInt>(Result)) break;  // Couldn't decide for sure
3982     if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
3983 #if 0
3984       dbgs() << "\n***\n*** Computed loop count " << *ItCst
3985              << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
3986              << "***\n";
3987 #endif
3988       ++NumArrayLenItCounts;
3989       return getConstant(ItCst);   // Found terminating iteration!
3990     }
3991   }
3992   return getCouldNotCompute();
3993 }
3994
3995
3996 /// CanConstantFold - Return true if we can constant fold an instruction of the
3997 /// specified type, assuming that all operands were constants.
3998 static bool CanConstantFold(const Instruction *I) {
3999   if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
4000       isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
4001     return true;
4002
4003   if (const CallInst *CI = dyn_cast<CallInst>(I))
4004     if (const Function *F = CI->getCalledFunction())
4005       return canConstantFoldCallTo(F);
4006   return false;
4007 }
4008
4009 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
4010 /// in the loop that V is derived from.  We allow arbitrary operations along the
4011 /// way, but the operands of an operation must either be constants or a value
4012 /// derived from a constant PHI.  If this expression does not fit with these
4013 /// constraints, return null.
4014 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
4015   // If this is not an instruction, or if this is an instruction outside of the
4016   // loop, it can't be derived from a loop PHI.
4017   Instruction *I = dyn_cast<Instruction>(V);
4018   if (I == 0 || !L->contains(I)) return 0;
4019
4020   if (PHINode *PN = dyn_cast<PHINode>(I)) {
4021     if (L->getHeader() == I->getParent())
4022       return PN;
4023     else
4024       // We don't currently keep track of the control flow needed to evaluate
4025       // PHIs, so we cannot handle PHIs inside of loops.
4026       return 0;
4027   }
4028
4029   // If we won't be able to constant fold this expression even if the operands
4030   // are constants, return early.
4031   if (!CanConstantFold(I)) return 0;
4032
4033   // Otherwise, we can evaluate this instruction if all of its operands are
4034   // constant or derived from a PHI node themselves.
4035   PHINode *PHI = 0;
4036   for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
4037     if (!(isa<Constant>(I->getOperand(Op)) ||
4038           isa<GlobalValue>(I->getOperand(Op)))) {
4039       PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
4040       if (P == 0) return 0;  // Not evolving from PHI
4041       if (PHI == 0)
4042         PHI = P;
4043       else if (PHI != P)
4044         return 0;  // Evolving from multiple different PHIs.
4045     }
4046
4047   // This is a expression evolving from a constant PHI!
4048   return PHI;
4049 }
4050
4051 /// EvaluateExpression - Given an expression that passes the
4052 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
4053 /// in the loop has the value PHIVal.  If we can't fold this expression for some
4054 /// reason, return null.
4055 static Constant *EvaluateExpression(Value *V, Constant *PHIVal,
4056                                     const TargetData *TD) {
4057   if (isa<PHINode>(V)) return PHIVal;
4058   if (Constant *C = dyn_cast<Constant>(V)) return C;
4059   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
4060   Instruction *I = cast<Instruction>(V);
4061
4062   std::vector<Constant*> Operands;
4063   Operands.resize(I->getNumOperands());
4064
4065   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
4066     Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal, TD);
4067     if (Operands[i] == 0) return 0;
4068   }
4069
4070   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
4071     return ConstantFoldCompareInstOperands(CI->getPredicate(), Operands[0],
4072                                            Operands[1], TD);
4073   return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
4074                                   &Operands[0], Operands.size(), TD);
4075 }
4076
4077 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
4078 /// in the header of its containing loop, we know the loop executes a
4079 /// constant number of times, and the PHI node is just a recurrence
4080 /// involving constants, fold it.
4081 Constant *
4082 ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
4083                                                    const APInt &BEs,
4084                                                    const Loop *L) {
4085   std::map<PHINode*, Constant*>::iterator I =
4086     ConstantEvolutionLoopExitValue.find(PN);
4087   if (I != ConstantEvolutionLoopExitValue.end())
4088     return I->second;
4089
4090   if (BEs.ugt(MaxBruteForceIterations))
4091     return ConstantEvolutionLoopExitValue[PN] = 0;  // Not going to evaluate it.
4092
4093   Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
4094
4095   // Since the loop is canonicalized, the PHI node must have two entries.  One
4096   // entry must be a constant (coming in from outside of the loop), and the
4097   // second must be derived from the same PHI.
4098   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
4099   Constant *StartCST =
4100     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
4101   if (StartCST == 0)
4102     return RetVal = 0;  // Must be a constant.
4103
4104   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
4105   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
4106   if (PN2 != PN)
4107     return RetVal = 0;  // Not derived from same PHI.
4108
4109   // Execute the loop symbolically to determine the exit value.
4110   if (BEs.getActiveBits() >= 32)
4111     return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
4112
4113   unsigned NumIterations = BEs.getZExtValue(); // must be in range
4114   unsigned IterationNum = 0;
4115   for (Constant *PHIVal = StartCST; ; ++IterationNum) {
4116     if (IterationNum == NumIterations)
4117       return RetVal = PHIVal;  // Got exit value!
4118
4119     // Compute the value of the PHI node for the next iteration.
4120     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD);
4121     if (NextPHI == PHIVal)
4122       return RetVal = NextPHI;  // Stopped evolving!
4123     if (NextPHI == 0)
4124       return 0;        // Couldn't evaluate!
4125     PHIVal = NextPHI;
4126   }
4127 }
4128
4129 /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute a
4130 /// constant number of times (the condition evolves only from constants),
4131 /// try to evaluate a few iterations of the loop until we get the exit
4132 /// condition gets a value of ExitWhen (true or false).  If we cannot
4133 /// evaluate the trip count of the loop, return getCouldNotCompute().
4134 const SCEV *
4135 ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
4136                                                        Value *Cond,
4137                                                        bool ExitWhen) {
4138   PHINode *PN = getConstantEvolvingPHI(Cond, L);
4139   if (PN == 0) return getCouldNotCompute();
4140
4141   // Since the loop is canonicalized, the PHI node must have two entries.  One
4142   // entry must be a constant (coming in from outside of the loop), and the
4143   // second must be derived from the same PHI.
4144   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
4145   Constant *StartCST =
4146     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
4147   if (StartCST == 0) return getCouldNotCompute();  // Must be a constant.
4148
4149   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
4150   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
4151   if (PN2 != PN) return getCouldNotCompute();  // Not derived from same PHI.
4152
4153   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
4154   // the loop symbolically to determine when the condition gets a value of
4155   // "ExitWhen".
4156   unsigned IterationNum = 0;
4157   unsigned MaxIterations = MaxBruteForceIterations;   // Limit analysis.
4158   for (Constant *PHIVal = StartCST;
4159        IterationNum != MaxIterations; ++IterationNum) {
4160     ConstantInt *CondVal =
4161       dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal, TD));
4162
4163     // Couldn't symbolically evaluate.
4164     if (!CondVal) return getCouldNotCompute();
4165
4166     if (CondVal->getValue() == uint64_t(ExitWhen)) {
4167       ++NumBruteForceTripCountsComputed;
4168       return getConstant(Type::getInt32Ty(getContext()), IterationNum);
4169     }
4170
4171     // Compute the value of the PHI node for the next iteration.
4172     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal, TD);
4173     if (NextPHI == 0 || NextPHI == PHIVal)
4174       return getCouldNotCompute();// Couldn't evaluate or not making progress...
4175     PHIVal = NextPHI;
4176   }
4177
4178   // Too many iterations were needed to evaluate.
4179   return getCouldNotCompute();
4180 }
4181
4182 /// getSCEVAtScope - Return a SCEV expression for the specified value
4183 /// at the specified scope in the program.  The L value specifies a loop
4184 /// nest to evaluate the expression at, where null is the top-level or a
4185 /// specified loop is immediately inside of the loop.
4186 ///
4187 /// This method can be used to compute the exit value for a variable defined
4188 /// in a loop by querying what the value will hold in the parent loop.
4189 ///
4190 /// In the case that a relevant loop exit value cannot be computed, the
4191 /// original value V is returned.
4192 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
4193   // Check to see if we've folded this expression at this loop before.
4194   std::map<const Loop *, const SCEV *> &Values = ValuesAtScopes[V];
4195   std::pair<std::map<const Loop *, const SCEV *>::iterator, bool> Pair =
4196     Values.insert(std::make_pair(L, static_cast<const SCEV *>(0)));
4197   if (!Pair.second)
4198     return Pair.first->second ? Pair.first->second : V;
4199
4200   // Otherwise compute it.
4201   const SCEV *C = computeSCEVAtScope(V, L);
4202   ValuesAtScopes[V][L] = C;
4203   return C;
4204 }
4205
4206 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
4207   if (isa<SCEVConstant>(V)) return V;
4208
4209   // If this instruction is evolved from a constant-evolving PHI, compute the
4210   // exit value from the loop without using SCEVs.
4211   if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
4212     if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
4213       const Loop *LI = (*this->LI)[I->getParent()];
4214       if (LI && LI->getParentLoop() == L)  // Looking for loop exit value.
4215         if (PHINode *PN = dyn_cast<PHINode>(I))
4216           if (PN->getParent() == LI->getHeader()) {
4217             // Okay, there is no closed form solution for the PHI node.  Check
4218             // to see if the loop that contains it has a known backedge-taken
4219             // count.  If so, we may be able to force computation of the exit
4220             // value.
4221             const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI);
4222             if (const SCEVConstant *BTCC =
4223                   dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
4224               // Okay, we know how many times the containing loop executes.  If
4225               // this is a constant evolving PHI node, get the final value at
4226               // the specified iteration number.
4227               Constant *RV = getConstantEvolutionLoopExitValue(PN,
4228                                                    BTCC->getValue()->getValue(),
4229                                                                LI);
4230               if (RV) return getSCEV(RV);
4231             }
4232           }
4233
4234       // Okay, this is an expression that we cannot symbolically evaluate
4235       // into a SCEV.  Check to see if it's possible to symbolically evaluate
4236       // the arguments into constants, and if so, try to constant propagate the
4237       // result.  This is particularly useful for computing loop exit values.
4238       if (CanConstantFold(I)) {
4239         std::vector<Constant*> Operands;
4240         Operands.reserve(I->getNumOperands());
4241         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
4242           Value *Op = I->getOperand(i);
4243           if (Constant *C = dyn_cast<Constant>(Op)) {
4244             Operands.push_back(C);
4245           } else {
4246             // If any of the operands is non-constant and if they are
4247             // non-integer and non-pointer, don't even try to analyze them
4248             // with scev techniques.
4249             if (!isSCEVable(Op->getType()))
4250               return V;
4251
4252             const SCEV *OpV = getSCEVAtScope(Op, L);
4253             if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
4254               Constant *C = SC->getValue();
4255               if (C->getType() != Op->getType())
4256                 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
4257                                                                   Op->getType(),
4258                                                                   false),
4259                                           C, Op->getType());
4260               Operands.push_back(C);
4261             } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
4262               if (Constant *C = dyn_cast<Constant>(SU->getValue())) {
4263                 if (C->getType() != Op->getType())
4264                   C =
4265                     ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
4266                                                                   Op->getType(),
4267                                                                   false),
4268                                           C, Op->getType());
4269                 Operands.push_back(C);
4270               } else
4271                 return V;
4272             } else {
4273               return V;
4274             }
4275           }
4276         }
4277
4278         Constant *C = 0;
4279         if (const CmpInst *CI = dyn_cast<CmpInst>(I))
4280           C = ConstantFoldCompareInstOperands(CI->getPredicate(),
4281                                               Operands[0], Operands[1], TD);
4282         else
4283           C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
4284                                        &Operands[0], Operands.size(), TD);
4285         if (C)
4286           return getSCEV(C);
4287       }
4288     }
4289
4290     // This is some other type of SCEVUnknown, just return it.
4291     return V;
4292   }
4293
4294   if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
4295     // Avoid performing the look-up in the common case where the specified
4296     // expression has no loop-variant portions.
4297     for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
4298       const SCEV *OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
4299       if (OpAtScope != Comm->getOperand(i)) {
4300         // Okay, at least one of these operands is loop variant but might be
4301         // foldable.  Build a new instance of the folded commutative expression.
4302         SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(),
4303                                             Comm->op_begin()+i);
4304         NewOps.push_back(OpAtScope);
4305
4306         for (++i; i != e; ++i) {
4307           OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
4308           NewOps.push_back(OpAtScope);
4309         }
4310         if (isa<SCEVAddExpr>(Comm))
4311           return getAddExpr(NewOps);
4312         if (isa<SCEVMulExpr>(Comm))
4313           return getMulExpr(NewOps);
4314         if (isa<SCEVSMaxExpr>(Comm))
4315           return getSMaxExpr(NewOps);
4316         if (isa<SCEVUMaxExpr>(Comm))
4317           return getUMaxExpr(NewOps);
4318         llvm_unreachable("Unknown commutative SCEV type!");
4319       }
4320     }
4321     // If we got here, all operands are loop invariant.
4322     return Comm;
4323   }
4324
4325   if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
4326     const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L);
4327     const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L);
4328     if (LHS == Div->getLHS() && RHS == Div->getRHS())
4329       return Div;   // must be loop invariant
4330     return getUDivExpr(LHS, RHS);
4331   }
4332
4333   // If this is a loop recurrence for a loop that does not contain L, then we
4334   // are dealing with the final value computed by the loop.
4335   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
4336     if (!L || !AddRec->getLoop()->contains(L)) {
4337       // To evaluate this recurrence, we need to know how many times the AddRec
4338       // loop iterates.  Compute this now.
4339       const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
4340       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
4341
4342       // Then, evaluate the AddRec.
4343       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
4344     }
4345     return AddRec;
4346   }
4347
4348   if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
4349     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
4350     if (Op == Cast->getOperand())
4351       return Cast;  // must be loop invariant
4352     return getZeroExtendExpr(Op, Cast->getType());
4353   }
4354
4355   if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
4356     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
4357     if (Op == Cast->getOperand())
4358       return Cast;  // must be loop invariant
4359     return getSignExtendExpr(Op, Cast->getType());
4360   }
4361
4362   if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
4363     const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L);
4364     if (Op == Cast->getOperand())
4365       return Cast;  // must be loop invariant
4366     return getTruncateExpr(Op, Cast->getType());
4367   }
4368
4369   llvm_unreachable("Unknown SCEV type!");
4370   return 0;
4371 }
4372
4373 /// getSCEVAtScope - This is a convenience function which does
4374 /// getSCEVAtScope(getSCEV(V), L).
4375 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
4376   return getSCEVAtScope(getSCEV(V), L);
4377 }
4378
4379 /// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the
4380 /// following equation:
4381 ///
4382 ///     A * X = B (mod N)
4383 ///
4384 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of
4385 /// A and B isn't important.
4386 ///
4387 /// If the equation does not have a solution, SCEVCouldNotCompute is returned.
4388 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
4389                                                ScalarEvolution &SE) {
4390   uint32_t BW = A.getBitWidth();
4391   assert(BW == B.getBitWidth() && "Bit widths must be the same.");
4392   assert(A != 0 && "A must be non-zero.");
4393
4394   // 1. D = gcd(A, N)
4395   //
4396   // The gcd of A and N may have only one prime factor: 2. The number of
4397   // trailing zeros in A is its multiplicity
4398   uint32_t Mult2 = A.countTrailingZeros();
4399   // D = 2^Mult2
4400
4401   // 2. Check if B is divisible by D.
4402   //
4403   // B is divisible by D if and only if the multiplicity of prime factor 2 for B
4404   // is not less than multiplicity of this prime factor for D.
4405   if (B.countTrailingZeros() < Mult2)
4406     return SE.getCouldNotCompute();
4407
4408   // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
4409   // modulo (N / D).
4410   //
4411   // (N / D) may need BW+1 bits in its representation.  Hence, we'll use this
4412   // bit width during computations.
4413   APInt AD = A.lshr(Mult2).zext(BW + 1);  // AD = A / D
4414   APInt Mod(BW + 1, 0);
4415   Mod.set(BW - Mult2);  // Mod = N / D
4416   APInt I = AD.multiplicativeInverse(Mod);
4417
4418   // 4. Compute the minimum unsigned root of the equation:
4419   // I * (B / D) mod (N / D)
4420   APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod);
4421
4422   // The result is guaranteed to be less than 2^BW so we may truncate it to BW
4423   // bits.
4424   return SE.getConstant(Result.trunc(BW));
4425 }
4426
4427 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
4428 /// given quadratic chrec {L,+,M,+,N}.  This returns either the two roots (which
4429 /// might be the same) or two SCEVCouldNotCompute objects.
4430 ///
4431 static std::pair<const SCEV *,const SCEV *>
4432 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
4433   assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
4434   const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
4435   const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
4436   const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
4437
4438   // We currently can only solve this if the coefficients are constants.
4439   if (!LC || !MC || !NC) {
4440     const SCEV *CNC = SE.getCouldNotCompute();
4441     return std::make_pair(CNC, CNC);
4442   }
4443
4444   uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
4445   const APInt &L = LC->getValue()->getValue();
4446   const APInt &M = MC->getValue()->getValue();
4447   const APInt &N = NC->getValue()->getValue();
4448   APInt Two(BitWidth, 2);
4449   APInt Four(BitWidth, 4);
4450
4451   {
4452     using namespace APIntOps;
4453     const APInt& C = L;
4454     // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
4455     // The B coefficient is M-N/2
4456     APInt B(M);
4457     B -= sdiv(N,Two);
4458
4459     // The A coefficient is N/2
4460     APInt A(N.sdiv(Two));
4461
4462     // Compute the B^2-4ac term.
4463     APInt SqrtTerm(B);
4464     SqrtTerm *= B;
4465     SqrtTerm -= Four * (A * C);
4466
4467     // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
4468     // integer value or else APInt::sqrt() will assert.
4469     APInt SqrtVal(SqrtTerm.sqrt());
4470
4471     // Compute the two solutions for the quadratic formula.
4472     // The divisions must be performed as signed divisions.
4473     APInt NegB(-B);
4474     APInt TwoA( A << 1 );
4475     if (TwoA.isMinValue()) {
4476       const SCEV *CNC = SE.getCouldNotCompute();
4477       return std::make_pair(CNC, CNC);
4478     }
4479
4480     LLVMContext &Context = SE.getContext();
4481
4482     ConstantInt *Solution1 =
4483       ConstantInt::get(Context, (NegB + SqrtVal).sdiv(TwoA));
4484     ConstantInt *Solution2 =
4485       ConstantInt::get(Context, (NegB - SqrtVal).sdiv(TwoA));
4486
4487     return std::make_pair(SE.getConstant(Solution1),
4488                           SE.getConstant(Solution2));
4489     } // end APIntOps namespace
4490 }
4491
4492 /// HowFarToZero - Return the number of times a backedge comparing the specified
4493 /// value to zero will execute.  If not computable, return CouldNotCompute.
4494 ScalarEvolution::BackedgeTakenInfo
4495 ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
4496   // If the value is a constant
4497   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
4498     // If the value is already zero, the branch will execute zero times.
4499     if (C->getValue()->isZero()) return C;
4500     return getCouldNotCompute();  // Otherwise it will loop infinitely.
4501   }
4502
4503   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
4504   if (!AddRec || AddRec->getLoop() != L)
4505     return getCouldNotCompute();
4506
4507   if (AddRec->isAffine()) {
4508     // If this is an affine expression, the execution count of this branch is
4509     // the minimum unsigned root of the following equation:
4510     //
4511     //     Start + Step*N = 0 (mod 2^BW)
4512     //
4513     // equivalent to:
4514     //
4515     //             Step*N = -Start (mod 2^BW)
4516     //
4517     // where BW is the common bit width of Start and Step.
4518
4519     // Get the initial value for the loop.
4520     const SCEV *Start = getSCEVAtScope(AddRec->getStart(),
4521                                        L->getParentLoop());
4522     const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1),
4523                                       L->getParentLoop());
4524
4525     if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
4526       // For now we handle only constant steps.
4527
4528       // First, handle unitary steps.
4529       if (StepC->getValue()->equalsInt(1))      // 1*N = -Start (mod 2^BW), so:
4530         return getNegativeSCEV(Start);          //   N = -Start (as unsigned)
4531       if (StepC->getValue()->isAllOnesValue())  // -1*N = -Start (mod 2^BW), so:
4532         return Start;                           //    N = Start (as unsigned)
4533
4534       // Then, try to solve the above equation provided that Start is constant.
4535       if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
4536         return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
4537                                             -StartC->getValue()->getValue(),
4538                                             *this);
4539     }
4540   } else if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
4541     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
4542     // the quadratic equation to solve it.
4543     std::pair<const SCEV *,const SCEV *> Roots = SolveQuadraticEquation(AddRec,
4544                                                                     *this);
4545     const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
4546     const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
4547     if (R1) {
4548 #if 0
4549       dbgs() << "HFTZ: " << *V << " - sol#1: " << *R1
4550              << "  sol#2: " << *R2 << "\n";
4551 #endif
4552       // Pick the smallest positive root value.
4553       if (ConstantInt *CB =
4554           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
4555                                    R1->getValue(), R2->getValue()))) {
4556         if (CB->getZExtValue() == false)
4557           std::swap(R1, R2);   // R1 is the minimum root now.
4558
4559         // We can only use this value if the chrec ends up with an exact zero
4560         // value at this index.  When solving for "X*X != 5", for example, we
4561         // should not accept a root of 2.
4562         const SCEV *Val = AddRec->evaluateAtIteration(R1, *this);
4563         if (Val->isZero())
4564           return R1;  // We found a quadratic root!
4565       }
4566     }
4567   }
4568
4569   return getCouldNotCompute();
4570 }
4571
4572 /// HowFarToNonZero - Return the number of times a backedge checking the
4573 /// specified value for nonzero will execute.  If not computable, return
4574 /// CouldNotCompute
4575 ScalarEvolution::BackedgeTakenInfo
4576 ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
4577   // Loops that look like: while (X == 0) are very strange indeed.  We don't
4578   // handle them yet except for the trivial case.  This could be expanded in the
4579   // future as needed.
4580
4581   // If the value is a constant, check to see if it is known to be non-zero
4582   // already.  If so, the backedge will execute zero times.
4583   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
4584     if (!C->getValue()->isNullValue())
4585       return getConstant(C->getType(), 0);
4586     return getCouldNotCompute();  // Otherwise it will loop infinitely.
4587   }
4588
4589   // We could implement others, but I really doubt anyone writes loops like
4590   // this, and if they did, they would already be constant folded.
4591   return getCouldNotCompute();
4592 }
4593
4594 /// getLoopPredecessor - If the given loop's header has exactly one unique
4595 /// predecessor outside the loop, return it. Otherwise return null.
4596 /// This is less strict that the loop "preheader" concept, which requires
4597 /// the predecessor to have only one single successor.
4598 ///
4599 BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
4600   BasicBlock *Header = L->getHeader();
4601   BasicBlock *Pred = 0;
4602   for (pred_iterator PI = pred_begin(Header), E = pred_end(Header);
4603        PI != E; ++PI)
4604     if (!L->contains(*PI)) {
4605       if (Pred && Pred != *PI) return 0; // Multiple predecessors.
4606       Pred = *PI;
4607     }
4608   return Pred;
4609 }
4610
4611 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
4612 /// (which may not be an immediate predecessor) which has exactly one
4613 /// successor from which BB is reachable, or null if no such block is
4614 /// found.
4615 ///
4616 std::pair<BasicBlock *, BasicBlock *>
4617 ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
4618   // If the block has a unique predecessor, then there is no path from the
4619   // predecessor to the block that does not go through the direct edge
4620   // from the predecessor to the block.
4621   if (BasicBlock *Pred = BB->getSinglePredecessor())
4622     return std::make_pair(Pred, BB);
4623
4624   // A loop's header is defined to be a block that dominates the loop.
4625   // If the header has a unique predecessor outside the loop, it must be
4626   // a block that has exactly one successor that can reach the loop.
4627   if (Loop *L = LI->getLoopFor(BB))
4628     return std::make_pair(getLoopPredecessor(L), L->getHeader());
4629
4630   return std::pair<BasicBlock *, BasicBlock *>();
4631 }
4632
4633 /// HasSameValue - SCEV structural equivalence is usually sufficient for
4634 /// testing whether two expressions are equal, however for the purposes of
4635 /// looking for a condition guarding a loop, it can be useful to be a little
4636 /// more general, since a front-end may have replicated the controlling
4637 /// expression.
4638 ///
4639 static bool HasSameValue(const SCEV *A, const SCEV *B) {
4640   // Quick check to see if they are the same SCEV.
4641   if (A == B) return true;
4642
4643   // Otherwise, if they're both SCEVUnknown, it's possible that they hold
4644   // two different instructions with the same value. Check for this case.
4645   if (const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A))
4646     if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
4647       if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
4648         if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
4649           if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory())
4650             return true;
4651
4652   // Otherwise assume they may have a different value.
4653   return false;
4654 }
4655
4656 /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
4657 /// predicate Pred. Return true iff any changes were made.
4658 ///
4659 bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
4660                                            const SCEV *&LHS, const SCEV *&RHS) {
4661   bool Changed = false;
4662
4663   // Canonicalize a constant to the right side.
4664   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
4665     // Check for both operands constant.
4666     if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
4667       if (ConstantExpr::getICmp(Pred,
4668                                 LHSC->getValue(),
4669                                 RHSC->getValue())->isNullValue())
4670         goto trivially_false;
4671       else
4672         goto trivially_true;
4673     }
4674     // Otherwise swap the operands to put the constant on the right.
4675     std::swap(LHS, RHS);
4676     Pred = ICmpInst::getSwappedPredicate(Pred);
4677     Changed = true;
4678   }
4679
4680   // If we're comparing an addrec with a value which is loop-invariant in the
4681   // addrec's loop, put the addrec on the left. Also make a dominance check,
4682   // as both operands could be addrecs loop-invariant in each other's loop.
4683   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS)) {
4684     const Loop *L = AR->getLoop();
4685     if (LHS->isLoopInvariant(L) && LHS->properlyDominates(L->getHeader(), DT)) {
4686       std::swap(LHS, RHS);
4687       Pred = ICmpInst::getSwappedPredicate(Pred);
4688       Changed = true;
4689     }
4690   }
4691
4692   // If there's a constant operand, canonicalize comparisons with boundary
4693   // cases, and canonicalize *-or-equal comparisons to regular comparisons.
4694   if (const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS)) {
4695     const APInt &RA = RC->getValue()->getValue();
4696     switch (Pred) {
4697     default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
4698     case ICmpInst::ICMP_EQ:
4699     case ICmpInst::ICMP_NE:
4700       break;
4701     case ICmpInst::ICMP_UGE:
4702       if ((RA - 1).isMinValue()) {
4703         Pred = ICmpInst::ICMP_NE;
4704         RHS = getConstant(RA - 1);
4705         Changed = true;
4706         break;
4707       }
4708       if (RA.isMaxValue()) {
4709         Pred = ICmpInst::ICMP_EQ;
4710         Changed = true;
4711         break;
4712       }
4713       if (RA.isMinValue()) goto trivially_true;
4714
4715       Pred = ICmpInst::ICMP_UGT;
4716       RHS = getConstant(RA - 1);
4717       Changed = true;
4718       break;
4719     case ICmpInst::ICMP_ULE:
4720       if ((RA + 1).isMaxValue()) {
4721         Pred = ICmpInst::ICMP_NE;
4722         RHS = getConstant(RA + 1);
4723         Changed = true;
4724         break;
4725       }
4726       if (RA.isMinValue()) {
4727         Pred = ICmpInst::ICMP_EQ;
4728         Changed = true;
4729         break;
4730       }
4731       if (RA.isMaxValue()) goto trivially_true;
4732
4733       Pred = ICmpInst::ICMP_ULT;
4734       RHS = getConstant(RA + 1);
4735       Changed = true;
4736       break;
4737     case ICmpInst::ICMP_SGE:
4738       if ((RA - 1).isMinSignedValue()) {
4739         Pred = ICmpInst::ICMP_NE;
4740         RHS = getConstant(RA - 1);
4741         Changed = true;
4742         break;
4743       }
4744       if (RA.isMaxSignedValue()) {
4745         Pred = ICmpInst::ICMP_EQ;
4746         Changed = true;
4747         break;
4748       }
4749       if (RA.isMinSignedValue()) goto trivially_true;
4750
4751       Pred = ICmpInst::ICMP_SGT;
4752       RHS = getConstant(RA - 1);
4753       Changed = true;
4754       break;
4755     case ICmpInst::ICMP_SLE:
4756       if ((RA + 1).isMaxSignedValue()) {
4757         Pred = ICmpInst::ICMP_NE;
4758         RHS = getConstant(RA + 1);
4759         Changed = true;
4760         break;
4761       }
4762       if (RA.isMinSignedValue()) {
4763         Pred = ICmpInst::ICMP_EQ;
4764         Changed = true;
4765         break;
4766       }
4767       if (RA.isMaxSignedValue()) goto trivially_true;
4768
4769       Pred = ICmpInst::ICMP_SLT;
4770       RHS = getConstant(RA + 1);
4771       Changed = true;
4772       break;
4773     case ICmpInst::ICMP_UGT:
4774       if (RA.isMinValue()) {
4775         Pred = ICmpInst::ICMP_NE;
4776         Changed = true;
4777         break;
4778       }
4779       if ((RA + 1).isMaxValue()) {
4780         Pred = ICmpInst::ICMP_EQ;
4781         RHS = getConstant(RA + 1);
4782         Changed = true;
4783         break;
4784       }
4785       if (RA.isMaxValue()) goto trivially_false;
4786       break;
4787     case ICmpInst::ICMP_ULT:
4788       if (RA.isMaxValue()) {
4789         Pred = ICmpInst::ICMP_NE;
4790         Changed = true;
4791         break;
4792       }
4793       if ((RA - 1).isMinValue()) {
4794         Pred = ICmpInst::ICMP_EQ;
4795         RHS = getConstant(RA - 1);
4796         Changed = true;
4797         break;
4798       }
4799       if (RA.isMinValue()) goto trivially_false;
4800       break;
4801     case ICmpInst::ICMP_SGT:
4802       if (RA.isMinSignedValue()) {
4803         Pred = ICmpInst::ICMP_NE;
4804         Changed = true;
4805         break;
4806       }
4807       if ((RA + 1).isMaxSignedValue()) {
4808         Pred = ICmpInst::ICMP_EQ;
4809         RHS = getConstant(RA + 1);
4810         Changed = true;
4811         break;
4812       }
4813       if (RA.isMaxSignedValue()) goto trivially_false;
4814       break;
4815     case ICmpInst::ICMP_SLT:
4816       if (RA.isMaxSignedValue()) {
4817         Pred = ICmpInst::ICMP_NE;
4818         Changed = true;
4819         break;
4820       }
4821       if ((RA - 1).isMinSignedValue()) {
4822        Pred = ICmpInst::ICMP_EQ;
4823        RHS = getConstant(RA - 1);
4824         Changed = true;
4825        break;
4826       }
4827       if (RA.isMinSignedValue()) goto trivially_false;
4828       break;
4829     }
4830   }
4831
4832   // Check for obvious equality.
4833   if (HasSameValue(LHS, RHS)) {
4834     if (ICmpInst::isTrueWhenEqual(Pred))
4835       goto trivially_true;
4836     if (ICmpInst::isFalseWhenEqual(Pred))
4837       goto trivially_false;
4838   }
4839
4840   // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by
4841   // adding or subtracting 1 from one of the operands.
4842   switch (Pred) {
4843   case ICmpInst::ICMP_SLE:
4844     if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) {
4845       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
4846                        /*HasNUW=*/false, /*HasNSW=*/true);
4847       Pred = ICmpInst::ICMP_SLT;
4848       Changed = true;
4849     } else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) {
4850       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
4851                        /*HasNUW=*/false, /*HasNSW=*/true);
4852       Pred = ICmpInst::ICMP_SLT;
4853       Changed = true;
4854     }
4855     break;
4856   case ICmpInst::ICMP_SGE:
4857     if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) {
4858       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
4859                        /*HasNUW=*/false, /*HasNSW=*/true);
4860       Pred = ICmpInst::ICMP_SGT;
4861       Changed = true;
4862     } else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) {
4863       LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
4864                        /*HasNUW=*/false, /*HasNSW=*/true);
4865       Pred = ICmpInst::ICMP_SGT;
4866       Changed = true;
4867     }
4868     break;
4869   case ICmpInst::ICMP_ULE:
4870     if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) {
4871       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
4872                        /*HasNUW=*/true, /*HasNSW=*/false);
4873       Pred = ICmpInst::ICMP_ULT;
4874       Changed = true;
4875     } else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) {
4876       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
4877                        /*HasNUW=*/true, /*HasNSW=*/false);
4878       Pred = ICmpInst::ICMP_ULT;
4879       Changed = true;
4880     }
4881     break;
4882   case ICmpInst::ICMP_UGE:
4883     if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) {
4884       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
4885                        /*HasNUW=*/true, /*HasNSW=*/false);
4886       Pred = ICmpInst::ICMP_UGT;
4887       Changed = true;
4888     } else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) {
4889       LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
4890                        /*HasNUW=*/true, /*HasNSW=*/false);
4891       Pred = ICmpInst::ICMP_UGT;
4892       Changed = true;
4893     }
4894     break;
4895   default:
4896     break;
4897   }
4898
4899   // TODO: More simplifications are possible here.
4900
4901   return Changed;
4902
4903 trivially_true:
4904   // Return 0 == 0.
4905   LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0);
4906   Pred = ICmpInst::ICMP_EQ;
4907   return true;
4908
4909 trivially_false:
4910   // Return 0 != 0.
4911   LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0);
4912   Pred = ICmpInst::ICMP_NE;
4913   return true;
4914 }
4915
4916 bool ScalarEvolution::isKnownNegative(const SCEV *S) {
4917   return getSignedRange(S).getSignedMax().isNegative();
4918 }
4919
4920 bool ScalarEvolution::isKnownPositive(const SCEV *S) {
4921   return getSignedRange(S).getSignedMin().isStrictlyPositive();
4922 }
4923
4924 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) {
4925   return !getSignedRange(S).getSignedMin().isNegative();
4926 }
4927
4928 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) {
4929   return !getSignedRange(S).getSignedMax().isStrictlyPositive();
4930 }
4931
4932 bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
4933   return isKnownNegative(S) || isKnownPositive(S);
4934 }
4935
4936 bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
4937                                        const SCEV *LHS, const SCEV *RHS) {
4938   // Canonicalize the inputs first.
4939   (void)SimplifyICmpOperands(Pred, LHS, RHS);
4940
4941   // If LHS or RHS is an addrec, check to see if the condition is true in
4942   // every iteration of the loop.
4943   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
4944     if (isLoopEntryGuardedByCond(
4945           AR->getLoop(), Pred, AR->getStart(), RHS) &&
4946         isLoopBackedgeGuardedByCond(
4947           AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS))
4948       return true;
4949   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(RHS))
4950     if (isLoopEntryGuardedByCond(
4951           AR->getLoop(), Pred, LHS, AR->getStart()) &&
4952         isLoopBackedgeGuardedByCond(
4953           AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this)))
4954       return true;
4955
4956   // Otherwise see what can be done with known constant ranges.
4957   return isKnownPredicateWithRanges(Pred, LHS, RHS);
4958 }
4959
4960 bool
4961 ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred,
4962                                             const SCEV *LHS, const SCEV *RHS) {
4963   if (HasSameValue(LHS, RHS))
4964     return ICmpInst::isTrueWhenEqual(Pred);
4965
4966   // This code is split out from isKnownPredicate because it is called from
4967   // within isLoopEntryGuardedByCond.
4968   switch (Pred) {
4969   default:
4970     llvm_unreachable("Unexpected ICmpInst::Predicate value!");
4971     break;
4972   case ICmpInst::ICMP_SGT:
4973     Pred = ICmpInst::ICMP_SLT;
4974     std::swap(LHS, RHS);
4975   case ICmpInst::ICMP_SLT: {
4976     ConstantRange LHSRange = getSignedRange(LHS);
4977     ConstantRange RHSRange = getSignedRange(RHS);
4978     if (LHSRange.getSignedMax().slt(RHSRange.getSignedMin()))
4979       return true;
4980     if (LHSRange.getSignedMin().sge(RHSRange.getSignedMax()))
4981       return false;
4982     break;
4983   }
4984   case ICmpInst::ICMP_SGE:
4985     Pred = ICmpInst::ICMP_SLE;
4986     std::swap(LHS, RHS);
4987   case ICmpInst::ICMP_SLE: {
4988     ConstantRange LHSRange = getSignedRange(LHS);
4989     ConstantRange RHSRange = getSignedRange(RHS);
4990     if (LHSRange.getSignedMax().sle(RHSRange.getSignedMin()))
4991       return true;
4992     if (LHSRange.getSignedMin().sgt(RHSRange.getSignedMax()))
4993       return false;
4994     break;
4995   }
4996   case ICmpInst::ICMP_UGT:
4997     Pred = ICmpInst::ICMP_ULT;
4998     std::swap(LHS, RHS);
4999   case ICmpInst::ICMP_ULT: {
5000     ConstantRange LHSRange = getUnsignedRange(LHS);
5001     ConstantRange RHSRange = getUnsignedRange(RHS);
5002     if (LHSRange.getUnsignedMax().ult(RHSRange.getUnsignedMin()))
5003       return true;
5004     if (LHSRange.getUnsignedMin().uge(RHSRange.getUnsignedMax()))
5005       return false;
5006     break;
5007   }
5008   case ICmpInst::ICMP_UGE:
5009     Pred = ICmpInst::ICMP_ULE;
5010     std::swap(LHS, RHS);
5011   case ICmpInst::ICMP_ULE: {
5012     ConstantRange LHSRange = getUnsignedRange(LHS);
5013     ConstantRange RHSRange = getUnsignedRange(RHS);
5014     if (LHSRange.getUnsignedMax().ule(RHSRange.getUnsignedMin()))
5015       return true;
5016     if (LHSRange.getUnsignedMin().ugt(RHSRange.getUnsignedMax()))
5017       return false;
5018     break;
5019   }
5020   case ICmpInst::ICMP_NE: {
5021     if (getUnsignedRange(LHS).intersectWith(getUnsignedRange(RHS)).isEmptySet())
5022       return true;
5023     if (getSignedRange(LHS).intersectWith(getSignedRange(RHS)).isEmptySet())
5024       return true;
5025
5026     const SCEV *Diff = getMinusSCEV(LHS, RHS);
5027     if (isKnownNonZero(Diff))
5028       return true;
5029     break;
5030   }
5031   case ICmpInst::ICMP_EQ:
5032     // The check at the top of the function catches the case where
5033     // the values are known to be equal.
5034     break;
5035   }
5036   return false;
5037 }
5038
5039 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
5040 /// protected by a conditional between LHS and RHS.  This is used to
5041 /// to eliminate casts.
5042 bool
5043 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
5044                                              ICmpInst::Predicate Pred,
5045                                              const SCEV *LHS, const SCEV *RHS) {
5046   // Interpret a null as meaning no loop, where there is obviously no guard
5047   // (interprocedural conditions notwithstanding).
5048   if (!L) return true;
5049
5050   BasicBlock *Latch = L->getLoopLatch();
5051   if (!Latch)
5052     return false;
5053
5054   BranchInst *LoopContinuePredicate =
5055     dyn_cast<BranchInst>(Latch->getTerminator());
5056   if (!LoopContinuePredicate ||
5057       LoopContinuePredicate->isUnconditional())
5058     return false;
5059
5060   return isImpliedCond(LoopContinuePredicate->getCondition(), Pred, LHS, RHS,
5061                        LoopContinuePredicate->getSuccessor(0) != L->getHeader());
5062 }
5063
5064 /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
5065 /// by a conditional between LHS and RHS.  This is used to help avoid max
5066 /// expressions in loop trip counts, and to eliminate casts.
5067 bool
5068 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
5069                                           ICmpInst::Predicate Pred,
5070                                           const SCEV *LHS, const SCEV *RHS) {
5071   // Interpret a null as meaning no loop, where there is obviously no guard
5072   // (interprocedural conditions notwithstanding).
5073   if (!L) return false;
5074
5075   // Starting at the loop predecessor, climb up the predecessor chain, as long
5076   // as there are predecessors that can be found that have unique successors
5077   // leading to the original header.
5078   for (std::pair<BasicBlock *, BasicBlock *>
5079          Pair(getLoopPredecessor(L), L->getHeader());
5080        Pair.first;
5081        Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
5082
5083     BranchInst *LoopEntryPredicate =
5084       dyn_cast<BranchInst>(Pair.first->getTerminator());
5085     if (!LoopEntryPredicate ||
5086         LoopEntryPredicate->isUnconditional())
5087       continue;
5088
5089     if (isImpliedCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS,
5090                       LoopEntryPredicate->getSuccessor(0) != Pair.second))
5091       return true;
5092   }
5093
5094   return false;
5095 }
5096
5097 /// isImpliedCond - Test whether the condition described by Pred, LHS,
5098 /// and RHS is true whenever the given Cond value evaluates to true.
5099 bool ScalarEvolution::isImpliedCond(Value *CondValue,
5100                                     ICmpInst::Predicate Pred,
5101                                     const SCEV *LHS, const SCEV *RHS,
5102                                     bool Inverse) {
5103   // Recursively handle And and Or conditions.
5104   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CondValue)) {
5105     if (BO->getOpcode() == Instruction::And) {
5106       if (!Inverse)
5107         return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
5108                isImpliedCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
5109     } else if (BO->getOpcode() == Instruction::Or) {
5110       if (Inverse)
5111         return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) ||
5112                isImpliedCond(BO->getOperand(1), Pred, LHS, RHS, Inverse);
5113     }
5114   }
5115
5116   ICmpInst *ICI = dyn_cast<ICmpInst>(CondValue);
5117   if (!ICI) return false;
5118
5119   // Bail if the ICmp's operands' types are wider than the needed type
5120   // before attempting to call getSCEV on them. This avoids infinite
5121   // recursion, since the analysis of widening casts can require loop
5122   // exit condition information for overflow checking, which would
5123   // lead back here.
5124   if (getTypeSizeInBits(LHS->getType()) <
5125       getTypeSizeInBits(ICI->getOperand(0)->getType()))
5126     return false;
5127
5128   // Now that we found a conditional branch that dominates the loop, check to
5129   // see if it is the comparison we are looking for.
5130   ICmpInst::Predicate FoundPred;
5131   if (Inverse)
5132     FoundPred = ICI->getInversePredicate();
5133   else
5134     FoundPred = ICI->getPredicate();
5135
5136   const SCEV *FoundLHS = getSCEV(ICI->getOperand(0));
5137   const SCEV *FoundRHS = getSCEV(ICI->getOperand(1));
5138
5139   // Balance the types. The case where FoundLHS' type is wider than
5140   // LHS' type is checked for above.
5141   if (getTypeSizeInBits(LHS->getType()) >
5142       getTypeSizeInBits(FoundLHS->getType())) {
5143     if (CmpInst::isSigned(Pred)) {
5144       FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType());
5145       FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType());
5146     } else {
5147       FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType());
5148       FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType());
5149     }
5150   }
5151
5152   // Canonicalize the query to match the way instcombine will have
5153   // canonicalized the comparison.
5154   if (SimplifyICmpOperands(Pred, LHS, RHS))
5155     if (LHS == RHS)
5156       return CmpInst::isTrueWhenEqual(Pred);
5157   if (SimplifyICmpOperands(FoundPred, FoundLHS, FoundRHS))
5158     if (FoundLHS == FoundRHS)
5159       return CmpInst::isFalseWhenEqual(Pred);
5160
5161   // Check to see if we can make the LHS or RHS match.
5162   if (LHS == FoundRHS || RHS == FoundLHS) {
5163     if (isa<SCEVConstant>(RHS)) {
5164       std::swap(FoundLHS, FoundRHS);
5165       FoundPred = ICmpInst::getSwappedPredicate(FoundPred);
5166     } else {
5167       std::swap(LHS, RHS);
5168       Pred = ICmpInst::getSwappedPredicate(Pred);
5169     }
5170   }
5171
5172   // Check whether the found predicate is the same as the desired predicate.
5173   if (FoundPred == Pred)
5174     return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
5175
5176   // Check whether swapping the found predicate makes it the same as the
5177   // desired predicate.
5178   if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) {
5179     if (isa<SCEVConstant>(RHS))
5180       return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
5181     else
5182       return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred),
5183                                    RHS, LHS, FoundLHS, FoundRHS);
5184   }
5185
5186   // Check whether the actual condition is beyond sufficient.
5187   if (FoundPred == ICmpInst::ICMP_EQ)
5188     if (ICmpInst::isTrueWhenEqual(Pred))
5189       if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
5190         return true;
5191   if (Pred == ICmpInst::ICMP_NE)
5192     if (!ICmpInst::isTrueWhenEqual(FoundPred))
5193       if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))
5194         return true;
5195
5196   // Otherwise assume the worst.
5197   return false;
5198 }
5199
5200 /// isImpliedCondOperands - Test whether the condition described by Pred,
5201 /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
5202 /// and FoundRHS is true.
5203 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
5204                                             const SCEV *LHS, const SCEV *RHS,
5205                                             const SCEV *FoundLHS,
5206                                             const SCEV *FoundRHS) {
5207   return isImpliedCondOperandsHelper(Pred, LHS, RHS,
5208                                      FoundLHS, FoundRHS) ||
5209          // ~x < ~y --> x > y
5210          isImpliedCondOperandsHelper(Pred, LHS, RHS,
5211                                      getNotSCEV(FoundRHS),
5212                                      getNotSCEV(FoundLHS));
5213 }
5214
5215 /// isImpliedCondOperandsHelper - Test whether the condition described by
5216 /// Pred, LHS, and RHS is true whenever the condition described by Pred,
5217 /// FoundLHS, and FoundRHS is true.
5218 bool
5219 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
5220                                              const SCEV *LHS, const SCEV *RHS,
5221                                              const SCEV *FoundLHS,
5222                                              const SCEV *FoundRHS) {
5223   switch (Pred) {
5224   default: llvm_unreachable("Unexpected ICmpInst::Predicate value!");
5225   case ICmpInst::ICMP_EQ:
5226   case ICmpInst::ICMP_NE:
5227     if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS))
5228       return true;
5229     break;
5230   case ICmpInst::ICMP_SLT:
5231   case ICmpInst::ICMP_SLE:
5232     if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) &&
5233         isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS))
5234       return true;
5235     break;
5236   case ICmpInst::ICMP_SGT:
5237   case ICmpInst::ICMP_SGE:
5238     if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) &&
5239         isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS))
5240       return true;
5241     break;
5242   case ICmpInst::ICMP_ULT:
5243   case ICmpInst::ICMP_ULE:
5244     if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) &&
5245         isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS))
5246       return true;
5247     break;
5248   case ICmpInst::ICMP_UGT:
5249   case ICmpInst::ICMP_UGE:
5250     if (isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, LHS, FoundLHS) &&
5251         isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, RHS, FoundRHS))
5252       return true;
5253     break;
5254   }
5255
5256   return false;
5257 }
5258
5259 /// getBECount - Subtract the end and start values and divide by the step,
5260 /// rounding up, to get the number of times the backedge is executed. Return
5261 /// CouldNotCompute if an intermediate computation overflows.
5262 const SCEV *ScalarEvolution::getBECount(const SCEV *Start,
5263                                         const SCEV *End,
5264                                         const SCEV *Step,
5265                                         bool NoWrap) {
5266   assert(!isKnownNegative(Step) &&
5267          "This code doesn't handle negative strides yet!");
5268
5269   const Type *Ty = Start->getType();
5270   const SCEV *NegOne = getConstant(Ty, (uint64_t)-1);
5271   const SCEV *Diff = getMinusSCEV(End, Start);
5272   const SCEV *RoundUp = getAddExpr(Step, NegOne);
5273
5274   // Add an adjustment to the difference between End and Start so that
5275   // the division will effectively round up.
5276   const SCEV *Add = getAddExpr(Diff, RoundUp);
5277
5278   if (!NoWrap) {
5279     // Check Add for unsigned overflow.
5280     // TODO: More sophisticated things could be done here.
5281     const Type *WideTy = IntegerType::get(getContext(),
5282                                           getTypeSizeInBits(Ty) + 1);
5283     const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy);
5284     const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy);
5285     const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp);
5286     if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
5287       return getCouldNotCompute();
5288   }
5289
5290   return getUDivExpr(Add, Step);
5291 }
5292
5293 /// HowManyLessThans - Return the number of times a backedge containing the
5294 /// specified less-than comparison will execute.  If not computable, return
5295 /// CouldNotCompute.
5296 ScalarEvolution::BackedgeTakenInfo
5297 ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
5298                                   const Loop *L, bool isSigned) {
5299   // Only handle:  "ADDREC < LoopInvariant".
5300   if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
5301
5302   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
5303   if (!AddRec || AddRec->getLoop() != L)
5304     return getCouldNotCompute();
5305
5306   // Check to see if we have a flag which makes analysis easy.
5307   bool NoWrap = isSigned ? AddRec->hasNoSignedWrap() :
5308                            AddRec->hasNoUnsignedWrap();
5309
5310   if (AddRec->isAffine()) {
5311     unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
5312     const SCEV *Step = AddRec->getStepRecurrence(*this);
5313
5314     if (Step->isZero())
5315       return getCouldNotCompute();
5316     if (Step->isOne()) {
5317       // With unit stride, the iteration never steps past the limit value.
5318     } else if (isKnownPositive(Step)) {
5319       // Test whether a positive iteration can step past the limit
5320       // value and past the maximum value for its type in a single step.
5321       // Note that it's not sufficient to check NoWrap here, because even
5322       // though the value after a wrap is undefined, it's not undefined
5323       // behavior, so if wrap does occur, the loop could either terminate or
5324       // loop infinitely, but in either case, the loop is guaranteed to
5325       // iterate at least until the iteration where the wrapping occurs.
5326       const SCEV *One = getConstant(Step->getType(), 1);
5327       if (isSigned) {
5328         APInt Max = APInt::getSignedMaxValue(BitWidth);
5329         if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax())
5330               .slt(getSignedRange(RHS).getSignedMax()))
5331           return getCouldNotCompute();
5332       } else {
5333         APInt Max = APInt::getMaxValue(BitWidth);
5334         if ((Max - getUnsignedRange(getMinusSCEV(Step, One)).getUnsignedMax())
5335               .ult(getUnsignedRange(RHS).getUnsignedMax()))
5336           return getCouldNotCompute();
5337       }
5338     } else
5339       // TODO: Handle negative strides here and below.
5340       return getCouldNotCompute();
5341
5342     // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
5343     // m.  So, we count the number of iterations in which {n,+,s} < m is true.
5344     // Note that we cannot simply return max(m-n,0)/s because it's not safe to
5345     // treat m-n as signed nor unsigned due to overflow possibility.
5346
5347     // First, we get the value of the LHS in the first iteration: n
5348     const SCEV *Start = AddRec->getOperand(0);
5349
5350     // Determine the minimum constant start value.
5351     const SCEV *MinStart = getConstant(isSigned ?
5352       getSignedRange(Start).getSignedMin() :
5353       getUnsignedRange(Start).getUnsignedMin());
5354
5355     // If we know that the condition is true in order to enter the loop,
5356     // then we know that it will run exactly (m-n)/s times. Otherwise, we
5357     // only know that it will execute (max(m,n)-n)/s times. In both cases,
5358     // the division must round up.
5359     const SCEV *End = RHS;
5360     if (!isLoopEntryGuardedByCond(L,
5361                                   isSigned ? ICmpInst::ICMP_SLT :
5362                                              ICmpInst::ICMP_ULT,
5363                                   getMinusSCEV(Start, Step), RHS))
5364       End = isSigned ? getSMaxExpr(RHS, Start)
5365                      : getUMaxExpr(RHS, Start);
5366
5367     // Determine the maximum constant end value.
5368     const SCEV *MaxEnd = getConstant(isSigned ?
5369       getSignedRange(End).getSignedMax() :
5370       getUnsignedRange(End).getUnsignedMax());
5371
5372     // If MaxEnd is within a step of the maximum integer value in its type,
5373     // adjust it down to the minimum value which would produce the same effect.
5374     // This allows the subsequent ceiling division of (N+(step-1))/step to
5375     // compute the correct value.
5376     const SCEV *StepMinusOne = getMinusSCEV(Step,
5377                                             getConstant(Step->getType(), 1));
5378     MaxEnd = isSigned ?
5379       getSMinExpr(MaxEnd,
5380                   getMinusSCEV(getConstant(APInt::getSignedMaxValue(BitWidth)),
5381                                StepMinusOne)) :
5382       getUMinExpr(MaxEnd,
5383                   getMinusSCEV(getConstant(APInt::getMaxValue(BitWidth)),
5384                                StepMinusOne));
5385
5386     // Finally, we subtract these two values and divide, rounding up, to get
5387     // the number of times the backedge is executed.
5388     const SCEV *BECount = getBECount(Start, End, Step, NoWrap);
5389
5390     // The maximum backedge count is similar, except using the minimum start
5391     // value and the maximum end value.
5392     const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step, NoWrap);
5393
5394     return BackedgeTakenInfo(BECount, MaxBECount);
5395   }
5396
5397   return getCouldNotCompute();
5398 }
5399
5400 /// getNumIterationsInRange - Return the number of iterations of this loop that
5401 /// produce values in the specified constant range.  Another way of looking at
5402 /// this is that it returns the first iteration number where the value is not in
5403 /// the condition, thus computing the exit count. If the iteration count can't
5404 /// be computed, an instance of SCEVCouldNotCompute is returned.
5405 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
5406                                                     ScalarEvolution &SE) const {
5407   if (Range.isFullSet())  // Infinite loop.
5408     return SE.getCouldNotCompute();
5409
5410   // If the start is a non-zero constant, shift the range to simplify things.
5411   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
5412     if (!SC->getValue()->isZero()) {
5413       SmallVector<const SCEV *, 4> Operands(op_begin(), op_end());
5414       Operands[0] = SE.getConstant(SC->getType(), 0);
5415       const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop());
5416       if (const SCEVAddRecExpr *ShiftedAddRec =
5417             dyn_cast<SCEVAddRecExpr>(Shifted))
5418         return ShiftedAddRec->getNumIterationsInRange(
5419                            Range.subtract(SC->getValue()->getValue()), SE);
5420       // This is strange and shouldn't happen.
5421       return SE.getCouldNotCompute();
5422     }
5423
5424   // The only time we can solve this is when we have all constant indices.
5425   // Otherwise, we cannot determine the overflow conditions.
5426   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
5427     if (!isa<SCEVConstant>(getOperand(i)))
5428       return SE.getCouldNotCompute();
5429
5430
5431   // Okay at this point we know that all elements of the chrec are constants and
5432   // that the start element is zero.
5433
5434   // First check to see if the range contains zero.  If not, the first
5435   // iteration exits.
5436   unsigned BitWidth = SE.getTypeSizeInBits(getType());
5437   if (!Range.contains(APInt(BitWidth, 0)))
5438     return SE.getConstant(getType(), 0);
5439
5440   if (isAffine()) {
5441     // If this is an affine expression then we have this situation:
5442     //   Solve {0,+,A} in Range  ===  Ax in Range
5443
5444     // We know that zero is in the range.  If A is positive then we know that
5445     // the upper value of the range must be the first possible exit value.
5446     // If A is negative then the lower of the range is the last possible loop
5447     // value.  Also note that we already checked for a full range.
5448     APInt One(BitWidth,1);
5449     APInt A     = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
5450     APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
5451
5452     // The exit value should be (End+A)/A.
5453     APInt ExitVal = (End + A).udiv(A);
5454     ConstantInt *ExitValue = ConstantInt::get(SE.getContext(), ExitVal);
5455
5456     // Evaluate at the exit value.  If we really did fall out of the valid
5457     // range, then we computed our trip count, otherwise wrap around or other
5458     // things must have happened.
5459     ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
5460     if (Range.contains(Val->getValue()))
5461       return SE.getCouldNotCompute();  // Something strange happened
5462
5463     // Ensure that the previous value is in the range.  This is a sanity check.
5464     assert(Range.contains(
5465            EvaluateConstantChrecAtConstant(this,
5466            ConstantInt::get(SE.getContext(), ExitVal - One), SE)->getValue()) &&
5467            "Linear scev computation is off in a bad way!");
5468     return SE.getConstant(ExitValue);
5469   } else if (isQuadratic()) {
5470     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
5471     // quadratic equation to solve it.  To do this, we must frame our problem in
5472     // terms of figuring out when zero is crossed, instead of when
5473     // Range.getUpper() is crossed.
5474     SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end());
5475     NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
5476     const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
5477
5478     // Next, solve the constructed addrec
5479     std::pair<const SCEV *,const SCEV *> Roots =
5480       SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
5481     const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
5482     const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
5483     if (R1) {
5484       // Pick the smallest positive root value.
5485       if (ConstantInt *CB =
5486           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
5487                          R1->getValue(), R2->getValue()))) {
5488         if (CB->getZExtValue() == false)
5489           std::swap(R1, R2);   // R1 is the minimum root now.
5490
5491         // Make sure the root is not off by one.  The returned iteration should
5492         // not be in the range, but the previous one should be.  When solving
5493         // for "X*X < 5", for example, we should not return a root of 2.
5494         ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
5495                                                              R1->getValue(),
5496                                                              SE);
5497         if (Range.contains(R1Val->getValue())) {
5498           // The next iteration must be out of the range...
5499           ConstantInt *NextVal =
5500                 ConstantInt::get(SE.getContext(), R1->getValue()->getValue()+1);
5501
5502           R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
5503           if (!Range.contains(R1Val->getValue()))
5504             return SE.getConstant(NextVal);
5505           return SE.getCouldNotCompute();  // Something strange happened
5506         }
5507
5508         // If R1 was not in the range, then it is a good return value.  Make
5509         // sure that R1-1 WAS in the range though, just in case.
5510         ConstantInt *NextVal =
5511                ConstantInt::get(SE.getContext(), R1->getValue()->getValue()-1);
5512         R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
5513         if (Range.contains(R1Val->getValue()))
5514           return R1;
5515         return SE.getCouldNotCompute();  // Something strange happened
5516       }
5517     }
5518   }
5519
5520   return SE.getCouldNotCompute();
5521 }
5522
5523
5524
5525 //===----------------------------------------------------------------------===//
5526 //                   SCEVCallbackVH Class Implementation
5527 //===----------------------------------------------------------------------===//
5528
5529 void ScalarEvolution::SCEVCallbackVH::deleted() {
5530   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
5531   if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
5532     SE->ConstantEvolutionLoopExitValue.erase(PN);
5533   SE->Scalars.erase(getValPtr());
5534   // this now dangles!
5535 }
5536
5537 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) {
5538   assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!");
5539
5540   // Forget all the expressions associated with users of the old value,
5541   // so that future queries will recompute the expressions using the new
5542   // value.
5543   SmallVector<User *, 16> Worklist;
5544   SmallPtrSet<User *, 8> Visited;
5545   Value *Old = getValPtr();
5546   bool DeleteOld = false;
5547   for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
5548        UI != UE; ++UI)
5549     Worklist.push_back(*UI);
5550   while (!Worklist.empty()) {
5551     User *U = Worklist.pop_back_val();
5552     // Deleting the Old value will cause this to dangle. Postpone
5553     // that until everything else is done.
5554     if (U == Old) {
5555       DeleteOld = true;
5556       continue;
5557     }
5558     if (!Visited.insert(U))
5559       continue;
5560     if (PHINode *PN = dyn_cast<PHINode>(U))
5561       SE->ConstantEvolutionLoopExitValue.erase(PN);
5562     SE->Scalars.erase(U);
5563     for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
5564          UI != UE; ++UI)
5565       Worklist.push_back(*UI);
5566   }
5567   // Delete the Old value if it (indirectly) references itself.
5568   if (DeleteOld) {
5569     if (PHINode *PN = dyn_cast<PHINode>(Old))
5570       SE->ConstantEvolutionLoopExitValue.erase(PN);
5571     SE->Scalars.erase(Old);
5572     // this now dangles!
5573   }
5574   // this may dangle!
5575 }
5576
5577 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
5578   : CallbackVH(V), SE(se) {}
5579
5580 //===----------------------------------------------------------------------===//
5581 //                   ScalarEvolution Class Implementation
5582 //===----------------------------------------------------------------------===//
5583
5584 ScalarEvolution::ScalarEvolution()
5585   : FunctionPass(&ID) {
5586 }
5587
5588 bool ScalarEvolution::runOnFunction(Function &F) {
5589   this->F = &F;
5590   LI = &getAnalysis<LoopInfo>();
5591   TD = getAnalysisIfAvailable<TargetData>();
5592   DT = &getAnalysis<DominatorTree>();
5593   return false;
5594 }
5595
5596 void ScalarEvolution::releaseMemory() {
5597   Scalars.clear();
5598   BackedgeTakenCounts.clear();
5599   ConstantEvolutionLoopExitValue.clear();
5600   ValuesAtScopes.clear();
5601   UniqueSCEVs.clear();
5602   SCEVAllocator.Reset();
5603 }
5604
5605 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
5606   AU.setPreservesAll();
5607   AU.addRequiredTransitive<LoopInfo>();
5608   AU.addRequiredTransitive<DominatorTree>();
5609 }
5610
5611 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
5612   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
5613 }
5614
5615 static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
5616                           const Loop *L) {
5617   // Print all inner loops first
5618   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
5619     PrintLoopInfo(OS, SE, *I);
5620
5621   OS << "Loop ";
5622   WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
5623   OS << ": ";
5624
5625   SmallVector<BasicBlock *, 8> ExitBlocks;
5626   L->getExitBlocks(ExitBlocks);
5627   if (ExitBlocks.size() != 1)
5628     OS << "<multiple exits> ";
5629
5630   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
5631     OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L);
5632   } else {
5633     OS << "Unpredictable backedge-taken count. ";
5634   }
5635
5636   OS << "\n"
5637         "Loop ";
5638   WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false);
5639   OS << ": ";
5640
5641   if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) {
5642     OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L);
5643   } else {
5644     OS << "Unpredictable max backedge-taken count. ";
5645   }
5646
5647   OS << "\n";
5648 }
5649
5650 void ScalarEvolution::print(raw_ostream &OS, const Module *) const {
5651   // ScalarEvolution's implementation of the print method is to print
5652   // out SCEV values of all instructions that are interesting. Doing
5653   // this potentially causes it to create new SCEV objects though,
5654   // which technically conflicts with the const qualifier. This isn't
5655   // observable from outside the class though, so casting away the
5656   // const isn't dangerous.
5657   ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this);
5658
5659   OS << "Classifying expressions for: ";
5660   WriteAsOperand(OS, F, /*PrintType=*/false);
5661   OS << "\n";
5662   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
5663     if (isSCEVable(I->getType()) && !isa<CmpInst>(*I)) {
5664       OS << *I << '\n';
5665       OS << "  -->  ";
5666       const SCEV *SV = SE.getSCEV(&*I);
5667       SV->print(OS);
5668
5669       const Loop *L = LI->getLoopFor((*I).getParent());
5670
5671       const SCEV *AtUse = SE.getSCEVAtScope(SV, L);
5672       if (AtUse != SV) {
5673         OS << "  -->  ";
5674         AtUse->print(OS);
5675       }
5676
5677       if (L) {
5678         OS << "\t\t" "Exits: ";
5679         const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
5680         if (!ExitValue->isLoopInvariant(L)) {
5681           OS << "<<Unknown>>";
5682         } else {
5683           OS << *ExitValue;
5684         }
5685       }
5686
5687       OS << "\n";
5688     }
5689
5690   OS << "Determining loop execution counts for: ";
5691   WriteAsOperand(OS, F, /*PrintType=*/false);
5692   OS << "\n";
5693   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
5694     PrintLoopInfo(OS, &SE, *I);
5695 }
5696