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.  These classes are reference counted, managed by the const SCEV*
  18 // class.  We only create one SCEV of a particular shape, so pointer-comparisons
  19 // for equality are legal.
  20 //
  21 // One important aspect of the SCEV objects is that they are never cyclic, even
  22 // if there is a cycle in the dataflow for an expression (ie, a PHI node).  If
  23 // the PHI node is one of the idioms that we can represent (e.g., a polynomial
  24 // recurrence) then we represent it directly as a recurrence node, otherwise we
  25 // represent it as a SCEVUnknown node.
  26 //
  27 // In addition to being able to represent expressions of various types, we also
  28 // have folders that are used to build the *canonical* representation for a
  29 // particular expression.  These folders are capable of using a variety of
  30 // rewrite rules to simplify the expressions.
  31 //
  32 // Once the folders are defined, we can implement the more interesting
  33 // higher-level code, such as the code that recognizes PHI nodes of various
  34 // types, computes the execution count of a loop, etc.
  35 //
  36 // TODO: We should use these routines and value representations to implement
  37 // dependence analysis!
  38 //
  39 //===----------------------------------------------------------------------===//
  40 //
  41 // There are several good references for the techniques used in this analysis.
  42 //
  43 //  Chains of recurrences -- a method to expedite the evaluation
  44 //  of closed-form functions
  45 //  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
  46 //
  47 //  On computational properties of chains of recurrences
  48 //  Eugene V. Zima
  49 //
  50 //  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
  51 //  Robert A. van Engelen
  52 //
  53 //  Efficient Symbolic Analysis for Optimizing Compilers
  54 //  Robert A. van Engelen
  55 //
  56 //  Using the chains of recurrences algebra for data dependence testing and
  57 //  induction variable substitution
  58 //  MS Thesis, Johnie Birch
  59 //
  60 //===----------------------------------------------------------------------===//
  61
  62 #define DEBUG_TYPE "scalar-evolution"
  63 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  64 #include "llvm/Constants.h"
  65 #include "llvm/DerivedTypes.h"
  66 #include "llvm/GlobalVariable.h"
  67 #include "llvm/Instructions.h"
  68 #include "llvm/Analysis/ConstantFolding.h"
  69 #include "llvm/Analysis/Dominators.h"
  70 #include "llvm/Analysis/LoopInfo.h"
  71 #include "llvm/Analysis/ValueTracking.h"
  72 #include "llvm/Assembly/Writer.h"
  73 #include "llvm/Target/TargetData.h"
  74 #include "llvm/Support/CommandLine.h"
  75 #include "llvm/Support/Compiler.h"
  76 #include "llvm/Support/ConstantRange.h"
  77 #include "llvm/Support/GetElementPtrTypeIterator.h"
  78 #include "llvm/Support/InstIterator.h"
  79 #include "llvm/Support/MathExtras.h"
  80 #include "llvm/Support/raw_ostream.h"
  81 #include "llvm/ADT/Statistic.h"
  82 #include "llvm/ADT/STLExtras.h"
  83 #include <algorithm>
  84 using namespace llvm;
  85
  86 STATISTIC(NumArrayLenItCounts,
  87           "Number of trip counts computed with array length");
  88 STATISTIC(NumTripCountsComputed,
  89           "Number of loops with predictable loop counts");
  90 STATISTIC(NumTripCountsNotComputed,
  91           "Number of loops without predictable loop counts");
  92 STATISTIC(NumBruteForceTripCountsComputed,
  93           "Number of loops with trip counts computed by force");
  94
  95 static cl::opt<unsigned>
  96 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
  97                         cl::desc("Maximum number of iterations SCEV will "
  98                                  "symbolically execute a constant derived loop"),
  99                         cl::init(100));
 100
 101 static RegisterPass<ScalarEvolution>
 102 R("scalar-evolution", "Scalar Evolution Analysis", false, true);
 103 char ScalarEvolution::ID = 0;
 104
 105 //===----------------------------------------------------------------------===//
 106 //                           SCEV class definitions
 107 //===----------------------------------------------------------------------===//
 108
 109 //===----------------------------------------------------------------------===//
 110 // Implementation of the SCEV class.
 111 //
 112 SCEV::~SCEV() {}
 113 void SCEV::dump() const {
 114   print(errs());
 115   errs() << '\n';
 116 }
 117
 118 void SCEV::print(std::ostream &o) const {
 119   raw_os_ostream OS(o);
 120   print(OS);
 121 }
 122
 123 bool SCEV::isZero() const {
 124   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
 125     return SC->getValue()->isZero();
 126   return false;
 127 }
 128
 129 bool SCEV::isOne() const {
 130   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
 131     return SC->getValue()->isOne();
 132   return false;
 133 }
 134
 135 SCEVCouldNotCompute::SCEVCouldNotCompute() :
 136   SCEV(scCouldNotCompute) {}
 137
 138 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
 139   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 140   return false;
 141 }
 142
 143 const Type *SCEVCouldNotCompute::getType() const {
 144   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 145   return 0;
 146 }
 147
 148 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
 149   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 150   return false;
 151 }
 152
 153 const SCEV* SCEVCouldNotCompute::
 154 replaceSymbolicValuesWithConcrete(const SCEV* Sym,
 155                                   const SCEV* Conc,
 156                                   ScalarEvolution &SE) const {
 157   return this;
 158 }
 159
 160 void SCEVCouldNotCompute::print(raw_ostream &OS) const {
 161   OS << "***COULDNOTCOMPUTE***";
 162 }
 163
 164 bool SCEVCouldNotCompute::classof(const SCEV *S) {
 165   return S->getSCEVType() == scCouldNotCompute;
 166 }
 167
 168
 169 // SCEVConstants - Only allow the creation of one SCEVConstant for any
 170 // particular value.  Don't use a const SCEV* here, or else the object will
 171 // never be deleted!
 172
 173 const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
 174   SCEVConstant *&R = SCEVConstants[V];
 175   if (R == 0) R = new SCEVConstant(V);
 176   return R;
 177 }
 178
 179 const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
 180   return getConstant(ConstantInt::get(Val));
 181 }
 182
 183 const SCEV*
 184 ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
 185   return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
 186 }
 187
 188 const Type *SCEVConstant::getType() const { return V->getType(); }
 189
 190 void SCEVConstant::print(raw_ostream &OS) const {
 191   WriteAsOperand(OS, V, false);
 192 }
 193
 194 SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
 195                            const SCEV* op, const Type *ty)
 196   : SCEV(SCEVTy), Op(op), Ty(ty) {}
 197
 198 bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 199   return Op->dominates(BB, DT);
 200 }
 201
 202 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
 203 // particular input.  Don't use a const SCEV* here, or else the object will
 204 // never be deleted!
 205
 206 SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
 207   : SCEVCastExpr(scTruncate, op, ty) {
 208   assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
 209          (Ty->isInteger() || isa<PointerType>(Ty)) &&
 210          "Cannot truncate non-integer value!");
 211 }
 212
 213
 214 void SCEVTruncateExpr::print(raw_ostream &OS) const {
 215   OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 216 }
 217
 218 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
 219 // particular input.  Don't use a const SCEV* here, or else the object will never
 220 // be deleted!
 221
 222 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEV* op, const Type *ty)
 223   : SCEVCastExpr(scZeroExtend, op, ty) {
 224   assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
 225          (Ty->isInteger() || isa<PointerType>(Ty)) &&
 226          "Cannot zero extend non-integer value!");
 227 }
 228
 229 void SCEVZeroExtendExpr::print(raw_ostream &OS) const {
 230   OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 231 }
 232
 233 // SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
 234 // particular input.  Don't use a const SCEV* here, or else the object will never
 235 // be deleted!
 236
 237 SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEV* op, const Type *ty)
 238   : SCEVCastExpr(scSignExtend, op, ty) {
 239   assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
 240          (Ty->isInteger() || isa<PointerType>(Ty)) &&
 241          "Cannot sign extend non-integer value!");
 242 }
 243
 244 void SCEVSignExtendExpr::print(raw_ostream &OS) const {
 245   OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")";
 246 }
 247
 248 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
 249 // particular input.  Don't use a const SCEV* here, or else the object will never
 250 // be deleted!
 251
 252 void SCEVCommutativeExpr::print(raw_ostream &OS) const {
 253   assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
 254   const char *OpStr = getOperationStr();
 255   OS << "(" << *Operands[0];
 256   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 257     OS << OpStr << *Operands[i];
 258   OS << ")";
 259 }
 260
 261 const SCEV* SCEVCommutativeExpr::
 262 replaceSymbolicValuesWithConcrete(const SCEV* Sym,
 263                                   const SCEV* Conc,
 264                                   ScalarEvolution &SE) const {
 265   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 266     const SCEV* H =
 267       getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 268     if (H != getOperand(i)) {
 269       SmallVector<const SCEV*, 8> NewOps;
 270       NewOps.reserve(getNumOperands());
 271       for (unsigned j = 0; j != i; ++j)
 272         NewOps.push_back(getOperand(j));
 273       NewOps.push_back(H);
 274       for (++i; i != e; ++i)
 275         NewOps.push_back(getOperand(i)->
 276                          replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
 277
 278       if (isa<SCEVAddExpr>(this))
 279         return SE.getAddExpr(NewOps);
 280       else if (isa<SCEVMulExpr>(this))
 281         return SE.getMulExpr(NewOps);
 282       else if (isa<SCEVSMaxExpr>(this))
 283         return SE.getSMaxExpr(NewOps);
 284       else if (isa<SCEVUMaxExpr>(this))
 285         return SE.getUMaxExpr(NewOps);
 286       else
 287         assert(0 && "Unknown commutative expr!");
 288     }
 289   }
 290   return this;
 291 }
 292
 293 bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 294   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 295     if (!getOperand(i)->dominates(BB, DT))
 296       return false;
 297   }
 298   return true;
 299 }
 300
 301
 302 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
 303 // input.  Don't use a const SCEV* here, or else the object will never be
 304 // deleted!
 305
 306 bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
 307   return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
 308 }
 309
 310 void SCEVUDivExpr::print(raw_ostream &OS) const {
 311   OS << "(" << *LHS << " /u " << *RHS << ")";
 312 }
 313
 314 const Type *SCEVUDivExpr::getType() const {
 315   // In most cases the types of LHS and RHS will be the same, but in some
 316   // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
 317   // depend on the type for correctness, but handling types carefully can
 318   // avoid extra casts in the SCEVExpander. The LHS is more likely to be
 319   // a pointer type than the RHS, so use the RHS' type here.
 320   return RHS->getType();
 321 }
 322
 323 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
 324 // particular input.  Don't use a const SCEV* here, or else the object will never
 325 // be deleted!
 326
 327 const SCEV* SCEVAddRecExpr::
 328 replaceSymbolicValuesWithConcrete(const SCEV* Sym,
 329                                   const SCEV* Conc,
 330                                   ScalarEvolution &SE) const {
 331   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 332     const SCEV* H =
 333       getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 334     if (H != getOperand(i)) {
 335       SmallVector<const SCEV*, 8> NewOps;
 336       NewOps.reserve(getNumOperands());
 337       for (unsigned j = 0; j != i; ++j)
 338         NewOps.push_back(getOperand(j));
 339       NewOps.push_back(H);
 340       for (++i; i != e; ++i)
 341         NewOps.push_back(getOperand(i)->
 342                          replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
 343
 344       return SE.getAddRecExpr(NewOps, L);
 345     }
 346   }
 347   return this;
 348 }
 349
 350
 351 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
 352   // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
 353   // contain L and if the start is invariant.
 354   // Add recurrences are never invariant in the function-body (null loop).
 355   return QueryLoop &&
 356          !QueryLoop->contains(L->getHeader()) &&
 357          getOperand(0)->isLoopInvariant(QueryLoop);
 358 }
 359
 360
 361 void SCEVAddRecExpr::print(raw_ostream &OS) const {
 362   OS << "{" << *Operands[0];
 363   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 364     OS << ",+," << *Operands[i];
 365   OS << "}<" << L->getHeader()->getName() + ">";
 366 }
 367
 368 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
 369 // value.  Don't use a const SCEV* here, or else the object will never be
 370 // deleted!
 371
 372 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
 373   // All non-instruction values are loop invariant.  All instructions are loop
 374   // invariant if they are not contained in the specified loop.
 375   // Instructions are never considered invariant in the function body
 376   // (null loop) because they are defined within the "loop".
 377   if (Instruction *I = dyn_cast<Instruction>(V))
 378     return L && !L->contains(I->getParent());
 379   return true;
 380 }
 381
 382 bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const {
 383   if (Instruction *I = dyn_cast<Instruction>(getValue()))
 384     return DT->dominates(I->getParent(), BB);
 385   return true;
 386 }
 387
 388 const Type *SCEVUnknown::getType() const {
 389   return V->getType();
 390 }
 391
 392 void SCEVUnknown::print(raw_ostream &OS) const {
 393   WriteAsOperand(OS, V, false);
 394 }
 395
 396 //===----------------------------------------------------------------------===//
 397 //                               SCEV Utilities
 398 //===----------------------------------------------------------------------===//
 399
 400 namespace {
 401   /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
 402   /// than the complexity of the RHS.  This comparator is used to canonicalize
 403   /// expressions.
 404   class VISIBILITY_HIDDEN SCEVComplexityCompare {
 405     LoopInfo *LI;
 406   public:
 407     explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {}
 408
 409     bool operator()(const SCEV *LHS, const SCEV *RHS) const {
 410       // Primarily, sort the SCEVs by their getSCEVType().
 411       if (LHS->getSCEVType() != RHS->getSCEVType())
 412         return LHS->getSCEVType() < RHS->getSCEVType();
 413
 414       // Aside from the getSCEVType() ordering, the particular ordering
 415       // isn't very important except that it's beneficial to be consistent,
 416       // so that (a + b) and (b + a) don't end up as different expressions.
 417
 418       // Sort SCEVUnknown values with some loose heuristics. TODO: This is
 419       // not as complete as it could be.
 420       if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) {
 421         const SCEVUnknown *RU = cast<SCEVUnknown>(RHS);
 422
 423         // Order pointer values after integer values. This helps SCEVExpander
 424         // form GEPs.
 425         if (isa<PointerType>(LU->getType()) && !isa<PointerType>(RU->getType()))
 426           return false;
 427         if (isa<PointerType>(RU->getType()) && !isa<PointerType>(LU->getType()))
 428           return true;
 429
 430         // Compare getValueID values.
 431         if (LU->getValue()->getValueID() != RU->getValue()->getValueID())
 432           return LU->getValue()->getValueID() < RU->getValue()->getValueID();
 433
 434         // Sort arguments by their position.
 435         if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) {
 436           const Argument *RA = cast<Argument>(RU->getValue());
 437           return LA->getArgNo() < RA->getArgNo();
 438         }
 439
 440         // For instructions, compare their loop depth, and their opcode.
 441         // This is pretty loose.
 442         if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) {
 443           Instruction *RV = cast<Instruction>(RU->getValue());
 444
 445           // Compare loop depths.
 446           if (LI->getLoopDepth(LV->getParent()) !=
 447               LI->getLoopDepth(RV->getParent()))
 448             return LI->getLoopDepth(LV->getParent()) <
 449                    LI->getLoopDepth(RV->getParent());
 450
 451           // Compare opcodes.
 452           if (LV->getOpcode() != RV->getOpcode())
 453             return LV->getOpcode() < RV->getOpcode();
 454
 455           // Compare the number of operands.
 456           if (LV->getNumOperands() != RV->getNumOperands())
 457             return LV->getNumOperands() < RV->getNumOperands();
 458         }
 459
 460         return false;
 461       }
 462
 463       // Compare constant values.
 464       if (const SCEVConstant *LC = dyn_cast<SCEVConstant>(LHS)) {
 465         const SCEVConstant *RC = cast<SCEVConstant>(RHS);
 466         return LC->getValue()->getValue().ult(RC->getValue()->getValue());
 467       }
 468
 469       // Compare addrec loop depths.
 470       if (const SCEVAddRecExpr *LA = dyn_cast<SCEVAddRecExpr>(LHS)) {
 471         const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
 472         if (LA->getLoop()->getLoopDepth() != RA->getLoop()->getLoopDepth())
 473           return LA->getLoop()->getLoopDepth() < RA->getLoop()->getLoopDepth();
 474       }
 475
 476       // Lexicographically compare n-ary expressions.
 477       if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) {
 478         const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS);
 479         for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) {
 480           if (i >= RC->getNumOperands())
 481             return false;
 482           if (operator()(LC->getOperand(i), RC->getOperand(i)))
 483             return true;
 484           if (operator()(RC->getOperand(i), LC->getOperand(i)))
 485             return false;
 486         }
 487         return LC->getNumOperands() < RC->getNumOperands();
 488       }
 489
 490       // Lexicographically compare udiv expressions.
 491       if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) {
 492         const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS);
 493         if (operator()(LC->getLHS(), RC->getLHS()))
 494           return true;
 495         if (operator()(RC->getLHS(), LC->getLHS()))
 496           return false;
 497         if (operator()(LC->getRHS(), RC->getRHS()))
 498           return true;
 499         if (operator()(RC->getRHS(), LC->getRHS()))
 500           return false;
 501         return false;
 502       }
 503
 504       // Compare cast expressions by operand.
 505       if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) {
 506         const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS);
 507         return operator()(LC->getOperand(), RC->getOperand());
 508       }
 509
 510       assert(0 && "Unknown SCEV kind!");
 511       return false;
 512     }
 513   };
 514 }
 515
 516 /// GroupByComplexity - Given a list of SCEV objects, order them by their
 517 /// complexity, and group objects of the same complexity together by value.
 518 /// When this routine is finished, we know that any duplicates in the vector are
 519 /// consecutive and that complexity is monotonically increasing.
 520 ///
 521 /// Note that we go take special precautions to ensure that we get determinstic
 522 /// results from this routine.  In other words, we don't want the results of
 523 /// this to depend on where the addresses of various SCEV objects happened to
 524 /// land in memory.
 525 ///
 526 static void GroupByComplexity(SmallVectorImpl<const SCEV*> &Ops,
 527                               LoopInfo *LI) {
 528   if (Ops.size() < 2) return;  // Noop
 529   if (Ops.size() == 2) {
 530     // This is the common case, which also happens to be trivially simple.
 531     // Special case it.
 532     if (SCEVComplexityCompare(LI)(Ops[1], Ops[0]))
 533       std::swap(Ops[0], Ops[1]);
 534     return;
 535   }
 536
 537   // Do the rough sort by complexity.
 538   std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI));
 539
 540   // Now that we are sorted by complexity, group elements of the same
 541   // complexity.  Note that this is, at worst, N^2, but the vector is likely to
 542   // be extremely short in practice.  Note that we take this approach because we
 543   // do not want to depend on the addresses of the objects we are grouping.
 544   for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
 545     const SCEV *S = Ops[i];
 546     unsigned Complexity = S->getSCEVType();
 547
 548     // If there are any objects of the same complexity and same value as this
 549     // one, group them.
 550     for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
 551       if (Ops[j] == S) { // Found a duplicate.
 552         // Move it to immediately after i'th element.
 553         std::swap(Ops[i+1], Ops[j]);
 554         ++i;   // no need to rescan it.
 555         if (i == e-2) return;  // Done!
 556       }
 557     }
 558   }
 559 }
 560
 561
 562
 563 //===----------------------------------------------------------------------===//
 564 //                      Simple SCEV method implementations
 565 //===----------------------------------------------------------------------===//
 566
 567 /// BinomialCoefficient - Compute BC(It, K).  The result has width W.
 568 /// Assume, K > 0.
 569 static const SCEV* BinomialCoefficient(const SCEV* It, unsigned K,
 570                                       ScalarEvolution &SE,
 571                                       const Type* ResultTy) {
 572   // Handle the simplest case efficiently.
 573   if (K == 1)
 574     return SE.getTruncateOrZeroExtend(It, ResultTy);
 575
 576   // We are using the following formula for BC(It, K):
 577   //
 578   //   BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
 579   //
 580   // Suppose, W is the bitwidth of the return value.  We must be prepared for
 581   // overflow.  Hence, we must assure that the result of our computation is
 582   // equal to the accurate one modulo 2^W.  Unfortunately, division isn't
 583   // safe in modular arithmetic.
 584   //
 585   // However, this code doesn't use exactly that formula; the formula it uses
 586   // is something like the following, where T is the number of factors of 2 in
 587   // K! (i.e. trailing zeros in the binary representation of K!), and ^ is
 588   // exponentiation:
 589   //
 590   //   BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T)
 591   //
 592   // This formula is trivially equivalent to the previous formula.  However,
 593   // this formula can be implemented much more efficiently.  The trick is that
 594   // K! / 2^T is odd, and exact division by an odd number *is* safe in modular
 595   // arithmetic.  To do exact division in modular arithmetic, all we have
 596   // to do is multiply by the inverse.  Therefore, this step can be done at
 597   // width W.
 598   //
 599   // The next issue is how to safely do the division by 2^T.  The way this
 600   // is done is by doing the multiplication step at a width of at least W + T
 601   // bits.  This way, the bottom W+T bits of the product are accurate. Then,
 602   // when we perform the division by 2^T (which is equivalent to a right shift
 603   // by T), the bottom W bits are accurate.  Extra bits are okay; they'll get
 604   // truncated out after the division by 2^T.
 605   //
 606   // In comparison to just directly using the first formula, this technique
 607   // is much more efficient; using the first formula requires W * K bits,
 608   // but this formula less than W + K bits. Also, the first formula requires
 609   // a division step, whereas this formula only requires multiplies and shifts.
 610   //
 611   // It doesn't matter whether the subtraction step is done in the calculation
 612   // width or the input iteration count's width; if the subtraction overflows,
 613   // the result must be zero anyway.  We prefer here to do it in the width of
 614   // the induction variable because it helps a lot for certain cases; CodeGen
 615   // isn't smart enough to ignore the overflow, which leads to much less
 616   // efficient code if the width of the subtraction is wider than the native
 617   // register width.
 618   //
 619   // (It's possible to not widen at all by pulling out factors of 2 before
 620   // the multiplication; for example, K=2 can be calculated as
 621   // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires
 622   // extra arithmetic, so it's not an obvious win, and it gets
 623   // much more complicated for K > 3.)
 624
 625   // Protection from insane SCEVs; this bound is conservative,
 626   // but it probably doesn't matter.
 627   if (K > 1000)
 628     return SE.getCouldNotCompute();
 629
 630   unsigned W = SE.getTypeSizeInBits(ResultTy);
 631
 632   // Calculate K! / 2^T and T; we divide out the factors of two before
 633   // multiplying for calculating K! / 2^T to avoid overflow.
 634   // Other overflow doesn't matter because we only care about the bottom
 635   // W bits of the result.
 636   APInt OddFactorial(W, 1);
 637   unsigned T = 1;
 638   for (unsigned i = 3; i <= K; ++i) {
 639     APInt Mult(W, i);
 640     unsigned TwoFactors = Mult.countTrailingZeros();
 641     T += TwoFactors;
 642     Mult = Mult.lshr(TwoFactors);
 643     OddFactorial *= Mult;
 644   }
 645
 646   // We need at least W + T bits for the multiplication step
 647   unsigned CalculationBits = W + T;
 648
 649   // Calcuate 2^T, at width T+W.
 650   APInt DivFactor = APInt(CalculationBits, 1).shl(T);
 651
 652   // Calculate the multiplicative inverse of K! / 2^T;
 653   // this multiplication factor will perform the exact division by
 654   // K! / 2^T.
 655   APInt Mod = APInt::getSignedMinValue(W+1);
 656   APInt MultiplyFactor = OddFactorial.zext(W+1);
 657   MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod);
 658   MultiplyFactor = MultiplyFactor.trunc(W);
 659
 660   // Calculate the product, at width T+W
 661   const IntegerType *CalculationTy = IntegerType::get(CalculationBits);
 662   const SCEV* Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy);
 663   for (unsigned i = 1; i != K; ++i) {
 664     const SCEV* S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType()));
 665     Dividend = SE.getMulExpr(Dividend,
 666                              SE.getTruncateOrZeroExtend(S, CalculationTy));
 667   }
 668
 669   // Divide by 2^T
 670   const SCEV* DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor));
 671
 672   // Truncate the result, and divide by K! / 2^T.
 673
 674   return SE.getMulExpr(SE.getConstant(MultiplyFactor),
 675                        SE.getTruncateOrZeroExtend(DivResult, ResultTy));
 676 }
 677
 678 /// evaluateAtIteration - Return the value of this chain of recurrences at
 679 /// the specified iteration number.  We can evaluate this recurrence by
 680 /// multiplying each element in the chain by the binomial coefficient
 681 /// corresponding to it.  In other words, we can evaluate {A,+,B,+,C,+,D} as:
 682 ///
 683 ///   A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
 684 ///
 685 /// where BC(It, k) stands for binomial coefficient.
 686 ///
 687 const SCEV* SCEVAddRecExpr::evaluateAtIteration(const SCEV* It,
 688                                                ScalarEvolution &SE) const {
 689   const SCEV* Result = getStart();
 690   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
 691     // The computation is correct in the face of overflow provided that the
 692     // multiplication is performed _after_ the evaluation of the binomial
 693     // coefficient.
 694     const SCEV* Coeff = BinomialCoefficient(It, i, SE, getType());
 695     if (isa<SCEVCouldNotCompute>(Coeff))
 696       return Coeff;
 697
 698     Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff));
 699   }
 700   return Result;
 701 }
 702
 703 //===----------------------------------------------------------------------===//
 704 //                    SCEV Expression folder implementations
 705 //===----------------------------------------------------------------------===//
 706
 707 const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
 708                                             const Type *Ty) {
 709   assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
 710          "This is not a truncating conversion!");
 711   assert(isSCEVable(Ty) &&
 712          "This is not a conversion to a SCEVable type!");
 713   Ty = getEffectiveSCEVType(Ty);
 714
 715   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 716     return getUnknown(
 717         ConstantExpr::getTrunc(SC->getValue(), Ty));
 718
 719   // trunc(trunc(x)) --> trunc(x)
 720   if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
 721     return getTruncateExpr(ST->getOperand(), Ty);
 722
 723   // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing
 724   if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
 725     return getTruncateOrSignExtend(SS->getOperand(), Ty);
 726
 727   // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing
 728   if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
 729     return getTruncateOrZeroExtend(SZ->getOperand(), Ty);
 730
 731   // If the input value is a chrec scev, truncate the chrec's operands.
 732   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
 733     SmallVector<const SCEV*, 4> Operands;
 734     for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
 735       Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
 736     return getAddRecExpr(Operands, AddRec->getLoop());
 737   }
 738
 739   SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
 740   if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
 741   return Result;
 742 }
 743
 744 const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
 745                                               const Type *Ty) {
 746   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
 747          "This is not an extending conversion!");
 748   assert(isSCEVable(Ty) &&
 749          "This is not a conversion to a SCEVable type!");
 750   Ty = getEffectiveSCEVType(Ty);
 751
 752   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
 753     const Type *IntTy = getEffectiveSCEVType(Ty);
 754     Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
 755     if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
 756     return getUnknown(C);
 757   }
 758
 759   // zext(zext(x)) --> zext(x)
 760   if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
 761     return getZeroExtendExpr(SZ->getOperand(), Ty);
 762
 763   // If the input value is a chrec scev, and we can prove that the value
 764   // did not overflow the old, smaller, value, we can zero extend all of the
 765   // operands (often constants).  This allows analysis of something like
 766   // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
 767   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
 768     if (AR->isAffine()) {
 769       // Check whether the backedge-taken count is SCEVCouldNotCompute.
 770       // Note that this serves two purposes: It filters out loops that are
 771       // simply not analyzable, and it covers the case where this code is
 772       // being called from within backedge-taken count analysis, such that
 773       // attempting to ask for the backedge-taken count would likely result
 774       // in infinite recursion. In the later case, the analysis code will
 775       // cope with a conservative value, and it will take care to purge
 776       // that value once it has finished.
 777       const SCEV* MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
 778       if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
 779         // Manually compute the final value for AR, checking for
 780         // overflow.
 781         const SCEV* Start = AR->getStart();
 782         const SCEV* Step = AR->getStepRecurrence(*this);
 783
 784         // Check whether the backedge-taken count can be losslessly casted to
 785         // the addrec's type. The count is always unsigned.
 786         const SCEV* CastedMaxBECount =
 787           getTruncateOrZeroExtend(MaxBECount, Start->getType());
 788         const SCEV* RecastedMaxBECount =
 789           getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
 790         if (MaxBECount == RecastedMaxBECount) {
 791           const Type *WideTy =
 792             IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
 793           // Check whether Start+Step*MaxBECount has no unsigned overflow.
 794           const SCEV* ZMul =
 795             getMulExpr(CastedMaxBECount,
 796                        getTruncateOrZeroExtend(Step, Start->getType()));
 797           const SCEV* Add = getAddExpr(Start, ZMul);
 798           const SCEV* OperandExtendedAdd =
 799             getAddExpr(getZeroExtendExpr(Start, WideTy),
 800                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 801                                   getZeroExtendExpr(Step, WideTy)));
 802           if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
 803             // Return the expression with the addrec on the outside.
 804             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 805                                  getZeroExtendExpr(Step, Ty),
 806                                  AR->getLoop());
 807
 808           // Similar to above, only this time treat the step value as signed.
 809           // This covers loops that count down.
 810           const SCEV* SMul =
 811             getMulExpr(CastedMaxBECount,
 812                        getTruncateOrSignExtend(Step, Start->getType()));
 813           Add = getAddExpr(Start, SMul);
 814           OperandExtendedAdd =
 815             getAddExpr(getZeroExtendExpr(Start, WideTy),
 816                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 817                                   getSignExtendExpr(Step, WideTy)));
 818           if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd)
 819             // Return the expression with the addrec on the outside.
 820             return getAddRecExpr(getZeroExtendExpr(Start, Ty),
 821                                  getSignExtendExpr(Step, Ty),
 822                                  AR->getLoop());
 823         }
 824       }
 825     }
 826
 827   SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
 828   if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
 829   return Result;
 830 }
 831
 832 const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
 833                                               const Type *Ty) {
 834   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
 835          "This is not an extending conversion!");
 836   assert(isSCEVable(Ty) &&
 837          "This is not a conversion to a SCEVable type!");
 838   Ty = getEffectiveSCEVType(Ty);
 839
 840   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
 841     const Type *IntTy = getEffectiveSCEVType(Ty);
 842     Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
 843     if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
 844     return getUnknown(C);
 845   }
 846
 847   // sext(sext(x)) --> sext(x)
 848   if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op))
 849     return getSignExtendExpr(SS->getOperand(), Ty);
 850
 851   // If the input value is a chrec scev, and we can prove that the value
 852   // did not overflow the old, smaller, value, we can sign extend all of the
 853   // operands (often constants).  This allows analysis of something like
 854   // this:  for (signed char X = 0; X < 100; ++X) { int Y = X; }
 855   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op))
 856     if (AR->isAffine()) {
 857       // Check whether the backedge-taken count is SCEVCouldNotCompute.
 858       // Note that this serves two purposes: It filters out loops that are
 859       // simply not analyzable, and it covers the case where this code is
 860       // being called from within backedge-taken count analysis, such that
 861       // attempting to ask for the backedge-taken count would likely result
 862       // in infinite recursion. In the later case, the analysis code will
 863       // cope with a conservative value, and it will take care to purge
 864       // that value once it has finished.
 865       const SCEV* MaxBECount = getMaxBackedgeTakenCount(AR->getLoop());
 866       if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
 867         // Manually compute the final value for AR, checking for
 868         // overflow.
 869         const SCEV* Start = AR->getStart();
 870         const SCEV* Step = AR->getStepRecurrence(*this);
 871
 872         // Check whether the backedge-taken count can be losslessly casted to
 873         // the addrec's type. The count is always unsigned.
 874         const SCEV* CastedMaxBECount =
 875           getTruncateOrZeroExtend(MaxBECount, Start->getType());
 876         const SCEV* RecastedMaxBECount =
 877           getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType());
 878         if (MaxBECount == RecastedMaxBECount) {
 879           const Type *WideTy =
 880             IntegerType::get(getTypeSizeInBits(Start->getType()) * 2);
 881           // Check whether Start+Step*MaxBECount has no signed overflow.
 882           const SCEV* SMul =
 883             getMulExpr(CastedMaxBECount,
 884                        getTruncateOrSignExtend(Step, Start->getType()));
 885           const SCEV* Add = getAddExpr(Start, SMul);
 886           const SCEV* OperandExtendedAdd =
 887             getAddExpr(getSignExtendExpr(Start, WideTy),
 888                        getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy),
 889                                   getSignExtendExpr(Step, WideTy)));
 890           if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd)
 891             // Return the expression with the addrec on the outside.
 892             return getAddRecExpr(getSignExtendExpr(Start, Ty),
 893                                  getSignExtendExpr(Step, Ty),
 894                                  AR->getLoop());
 895         }
 896       }
 897     }
 898
 899   SCEVSignExtendExpr *&Result = SCEVSignExtends[std::make_pair(Op, Ty)];
 900   if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
 901   return Result;
 902 }
 903
 904 /// getAnyExtendExpr - Return a SCEV for the given operand extended with
 905 /// unspecified bits out to the given type.
 906 ///
 907 const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* Op,
 908                                              const Type *Ty) {
 909   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
 910          "This is not an extending conversion!");
 911   assert(isSCEVable(Ty) &&
 912          "This is not a conversion to a SCEVable type!");
 913   Ty = getEffectiveSCEVType(Ty);
 914
 915   // Sign-extend negative constants.
 916   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 917     if (SC->getValue()->getValue().isNegative())
 918       return getSignExtendExpr(Op, Ty);
 919
 920   // Peel off a truncate cast.
 921   if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) {
 922     const SCEV* NewOp = T->getOperand();
 923     if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty))
 924       return getAnyExtendExpr(NewOp, Ty);
 925     return getTruncateOrNoop(NewOp, Ty);
 926   }
 927
 928   // Next try a zext cast. If the cast is folded, use it.
 929   const SCEV* ZExt = getZeroExtendExpr(Op, Ty);
 930   if (!isa<SCEVZeroExtendExpr>(ZExt))
 931     return ZExt;
 932
 933   // Next try a sext cast. If the cast is folded, use it.
 934   const SCEV* SExt = getSignExtendExpr(Op, Ty);
 935   if (!isa<SCEVSignExtendExpr>(SExt))
 936     return SExt;
 937
 938   // If the expression is obviously signed, use the sext cast value.
 939   if (isa<SCEVSMaxExpr>(Op))
 940     return SExt;
 941
 942   // Absent any other information, use the zext cast value.
 943   return ZExt;
 944 }
 945
 946 /// CollectAddOperandsWithScales - Process the given Ops list, which is
 947 /// a list of operands to be added under the given scale, update the given
 948 /// map. This is a helper function for getAddRecExpr. As an example of
 949 /// what it does, given a sequence of operands that would form an add
 950 /// expression like this:
 951 ///
 952 ///    m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r)
 953 ///
 954 /// where A and B are constants, update the map with these values:
 955 ///
 956 ///    (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
 957 ///
 958 /// and add 13 + A*B*29 to AccumulatedConstant.
 959 /// This will allow getAddRecExpr to produce this:
 960 ///
 961 ///    13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
 962 ///
 963 /// This form often exposes folding opportunities that are hidden in
 964 /// the original operand list.
 965 ///
 966 /// Return true iff it appears that any interesting folding opportunities
 967 /// may be exposed. This helps getAddRecExpr short-circuit extra work in
 968 /// the common case where no interesting opportunities are present, and
 969 /// is also used as a check to avoid infinite recursion.
 970 ///
 971 static bool
 972 CollectAddOperandsWithScales(DenseMap<const SCEV*, APInt> &M,
 973                              SmallVector<const SCEV*, 8> &NewOps,
 974                              APInt &AccumulatedConstant,
 975                              const SmallVectorImpl<const SCEV*> &Ops,
 976                              const APInt &Scale,
 977                              ScalarEvolution &SE) {
 978   bool Interesting = false;
 979
 980   // Iterate over the add operands.
 981   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
 982     const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]);
 983     if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) {
 984       APInt NewScale =
 985         Scale * cast<SCEVConstant>(Mul->getOperand(0))->getValue()->getValue();
 986       if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) {
 987         // A multiplication of a constant with another add; recurse.
 988         Interesting |=
 989           CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
 990                                        cast<SCEVAddExpr>(Mul->getOperand(1))
 991                                          ->getOperands(),
 992                                        NewScale, SE);
 993       } else {
 994         // A multiplication of a constant with some other value. Update
 995         // the map.
 996         SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
 997         const SCEV* Key = SE.getMulExpr(MulOps);
 998         std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
 999           M.insert(std::make_pair(Key, APInt()));
1000         if (Pair.second) {
1001           Pair.first->second = NewScale;
1002           NewOps.push_back(Pair.first->first);
1003         } else {
1004           Pair.first->second += NewScale;
1005           // The map already had an entry for this value, which may indicate
1006           // a folding opportunity.
1007           Interesting = true;
1008         }
1009       }
1010     } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1011       // Pull a buried constant out to the outside.
1012       if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
1013         Interesting = true;
1014       AccumulatedConstant += Scale * C->getValue()->getValue();
1015     } else {
1016       // An ordinary operand. Update the map.
1017       std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
1018         M.insert(std::make_pair(Ops[i], APInt()));
1019       if (Pair.second) {
1020         Pair.first->second = Scale;
1021         NewOps.push_back(Pair.first->first);
1022       } else {
1023         Pair.first->second += Scale;
1024         // The map already had an entry for this value, which may indicate
1025         // a folding opportunity.
1026         Interesting = true;
1027       }
1028     }
1029   }
1030
1031   return Interesting;
1032 }
1033
1034 namespace {
1035   struct APIntCompare {
1036     bool operator()(const APInt &LHS, const APInt &RHS) const {
1037       return LHS.ult(RHS);
1038     }
1039   };
1040 }
1041
1042 /// getAddExpr - Get a canonical add expression, or something simpler if
1043 /// possible.
1044 const SCEV* ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV*> &Ops) {
1045   assert(!Ops.empty() && "Cannot get empty add!");
1046   if (Ops.size() == 1) return Ops[0];
1047 #ifndef NDEBUG
1048   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1049     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1050            getEffectiveSCEVType(Ops[0]->getType()) &&
1051            "SCEVAddExpr operand types don't match!");
1052 #endif
1053
1054   // Sort by complexity, this groups all similar expression types together.
1055   GroupByComplexity(Ops, LI);
1056
1057   // If there are any constants, fold them together.
1058   unsigned Idx = 0;
1059   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1060     ++Idx;
1061     assert(Idx < Ops.size());
1062     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1063       // We found two constants, fold them together!
1064       Ops[0] = getConstant(LHSC->getValue()->getValue() +
1065                            RHSC->getValue()->getValue());
1066       if (Ops.size() == 2) return Ops[0];
1067       Ops.erase(Ops.begin()+1);  // Erase the folded element
1068       LHSC = cast<SCEVConstant>(Ops[0]);
1069     }
1070
1071     // If we are left with a constant zero being added, strip it off.
1072     if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
1073       Ops.erase(Ops.begin());
1074       --Idx;
1075     }
1076   }
1077
1078   if (Ops.size() == 1) return Ops[0];
1079
1080   // Okay, check to see if the same value occurs in the operand list twice.  If
1081   // so, merge them together into an multiply expression.  Since we sorted the
1082   // list, these values are required to be adjacent.
1083   const Type *Ty = Ops[0]->getType();
1084   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1085     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
1086       // Found a match, merge the two values into a multiply, and add any
1087       // remaining values to the result.
1088       const SCEV* Two = getIntegerSCEV(2, Ty);
1089       const SCEV* Mul = getMulExpr(Ops[i], Two);
1090       if (Ops.size() == 2)
1091         return Mul;
1092       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
1093       Ops.push_back(Mul);
1094       return getAddExpr(Ops);
1095     }
1096
1097   // Check for truncates. If all the operands are truncated from the same
1098   // type, see if factoring out the truncate would permit the result to be
1099   // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n)
1100   // if the contents of the resulting outer trunc fold to something simple.
1101   for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
1102     const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]);
1103     const Type *DstType = Trunc->getType();
1104     const Type *SrcType = Trunc->getOperand()->getType();
1105     SmallVector<const SCEV*, 8> LargeOps;
1106     bool Ok = true;
1107     // Check all the operands to see if they can be represented in the
1108     // source type of the truncate.
1109     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1110       if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) {
1111         if (T->getOperand()->getType() != SrcType) {
1112           Ok = false;
1113           break;
1114         }
1115         LargeOps.push_back(T->getOperand());
1116       } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1117         // This could be either sign or zero extension, but sign extension
1118         // is much more likely to be foldable here.
1119         LargeOps.push_back(getSignExtendExpr(C, SrcType));
1120       } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
1121         SmallVector<const SCEV*, 8> LargeMulOps;
1122         for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
1123           if (const SCEVTruncateExpr *T =
1124                 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
1125             if (T->getOperand()->getType() != SrcType) {
1126               Ok = false;
1127               break;
1128             }
1129             LargeMulOps.push_back(T->getOperand());
1130           } else if (const SCEVConstant *C =
1131                        dyn_cast<SCEVConstant>(M->getOperand(j))) {
1132             // This could be either sign or zero extension, but sign extension
1133             // is much more likely to be foldable here.
1134             LargeMulOps.push_back(getSignExtendExpr(C, SrcType));
1135           } else {
1136             Ok = false;
1137             break;
1138           }
1139         }
1140         if (Ok)
1141           LargeOps.push_back(getMulExpr(LargeMulOps));
1142       } else {
1143         Ok = false;
1144         break;
1145       }
1146     }
1147     if (Ok) {
1148       // Evaluate the expression in the larger type.
1149       const SCEV* Fold = getAddExpr(LargeOps);
1150       // If it folds to something simple, use it. Otherwise, don't.
1151       if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
1152         return getTruncateExpr(Fold, DstType);
1153     }
1154   }
1155
1156   // Skip past any other cast SCEVs.
1157   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
1158     ++Idx;
1159
1160   // If there are add operands they would be next.
1161   if (Idx < Ops.size()) {
1162     bool DeletedAdd = false;
1163     while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
1164       // If we have an add, expand the add operands onto the end of the operands
1165       // list.
1166       Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
1167       Ops.erase(Ops.begin()+Idx);
1168       DeletedAdd = true;
1169     }
1170
1171     // If we deleted at least one add, we added operands to the end of the list,
1172     // and they are not necessarily sorted.  Recurse to resort and resimplify
1173     // any operands we just aquired.
1174     if (DeletedAdd)
1175       return getAddExpr(Ops);
1176   }
1177
1178   // Skip over the add expression until we get to a multiply.
1179   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
1180     ++Idx;
1181
1182   // Check to see if there are any folding opportunities present with
1183   // operands multiplied by constant values.
1184   if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
1185     uint64_t BitWidth = getTypeSizeInBits(Ty);
1186     DenseMap<const SCEV*, APInt> M;
1187     SmallVector<const SCEV*, 8> NewOps;
1188     APInt AccumulatedConstant(BitWidth, 0);
1189     if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
1190                                      Ops, APInt(BitWidth, 1), *this)) {
1191       // Some interesting folding opportunity is present, so its worthwhile to
1192       // re-generate the operands list. Group the operands by constant scale,
1193       // to avoid multiplying by the same constant scale multiple times.
1194       std::map<APInt, SmallVector<const SCEV*, 4>, APIntCompare> MulOpLists;
1195       for (SmallVector<const SCEV*, 8>::iterator I = NewOps.begin(),
1196            E = NewOps.end(); I != E; ++I)
1197         MulOpLists[M.find(*I)->second].push_back(*I);
1198       // Re-generate the operands list.
1199       Ops.clear();
1200       if (AccumulatedConstant != 0)
1201         Ops.push_back(getConstant(AccumulatedConstant));
1202       for (std::map<APInt, SmallVector<const SCEV*, 4>, APIntCompare>::iterator I =
1203            MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I)
1204         if (I->first != 0)
1205           Ops.push_back(getMulExpr(getConstant(I->first), getAddExpr(I->second)));
1206       if (Ops.empty())
1207         return getIntegerSCEV(0, Ty);
1208       if (Ops.size() == 1)
1209         return Ops[0];
1210       return getAddExpr(Ops);
1211     }
1212   }
1213
1214   // If we are adding something to a multiply expression, make sure the
1215   // something is not already an operand of the multiply.  If so, merge it into
1216   // the multiply.
1217   for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
1218     const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
1219     for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
1220       const SCEV *MulOpSCEV = Mul->getOperand(MulOp);
1221       for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
1222         if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) {
1223           // Fold W + X + (X * Y * Z)  -->  W + (X * ((Y*Z)+1))
1224           const SCEV* InnerMul = Mul->getOperand(MulOp == 0);
1225           if (Mul->getNumOperands() != 2) {
1226             // If the multiply has more than two operands, we must get the
1227             // Y*Z term.
1228             SmallVector<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
1229             MulOps.erase(MulOps.begin()+MulOp);
1230             InnerMul = getMulExpr(MulOps);
1231           }
1232           const SCEV* One = getIntegerSCEV(1, Ty);
1233           const SCEV* AddOne = getAddExpr(InnerMul, One);
1234           const SCEV* OuterMul = getMulExpr(AddOne, Ops[AddOp]);
1235           if (Ops.size() == 2) return OuterMul;
1236           if (AddOp < Idx) {
1237             Ops.erase(Ops.begin()+AddOp);
1238             Ops.erase(Ops.begin()+Idx-1);
1239           } else {
1240             Ops.erase(Ops.begin()+Idx);
1241             Ops.erase(Ops.begin()+AddOp-1);
1242           }
1243           Ops.push_back(OuterMul);
1244           return getAddExpr(Ops);
1245         }
1246
1247       // Check this multiply against other multiplies being added together.
1248       for (unsigned OtherMulIdx = Idx+1;
1249            OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
1250            ++OtherMulIdx) {
1251         const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
1252         // If MulOp occurs in OtherMul, we can fold the two multiplies
1253         // together.
1254         for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
1255              OMulOp != e; ++OMulOp)
1256           if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
1257             // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
1258             const SCEV* InnerMul1 = Mul->getOperand(MulOp == 0);
1259             if (Mul->getNumOperands() != 2) {
1260               SmallVector<const SCEV*, 4> MulOps(Mul->op_begin(), Mul->op_end());
1261               MulOps.erase(MulOps.begin()+MulOp);
1262               InnerMul1 = getMulExpr(MulOps);
1263             }
1264             const SCEV* InnerMul2 = OtherMul->getOperand(OMulOp == 0);
1265             if (OtherMul->getNumOperands() != 2) {
1266               SmallVector<const SCEV*, 4> MulOps(OtherMul->op_begin(),
1267                                              OtherMul->op_end());
1268               MulOps.erase(MulOps.begin()+OMulOp);
1269               InnerMul2 = getMulExpr(MulOps);
1270             }
1271             const SCEV* InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
1272             const SCEV* OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
1273             if (Ops.size() == 2) return OuterMul;
1274             Ops.erase(Ops.begin()+Idx);
1275             Ops.erase(Ops.begin()+OtherMulIdx-1);
1276             Ops.push_back(OuterMul);
1277             return getAddExpr(Ops);
1278           }
1279       }
1280     }
1281   }
1282
1283   // If there are any add recurrences in the operands list, see if any other
1284   // added values are loop invariant.  If so, we can fold them into the
1285   // recurrence.
1286   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1287     ++Idx;
1288
1289   // Scan over all recurrences, trying to fold loop invariants into them.
1290   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1291     // Scan all of the other operands to this add and add them to the vector if
1292     // they are loop invariant w.r.t. the recurrence.
1293     SmallVector<const SCEV*, 8> LIOps;
1294     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1295     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1296       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1297         LIOps.push_back(Ops[i]);
1298         Ops.erase(Ops.begin()+i);
1299         --i; --e;
1300       }
1301
1302     // If we found some loop invariants, fold them into the recurrence.
1303     if (!LIOps.empty()) {
1304       //  NLI + LI + {Start,+,Step}  -->  NLI + {LI+Start,+,Step}
1305       LIOps.push_back(AddRec->getStart());
1306
1307       SmallVector<const SCEV*, 4> AddRecOps(AddRec->op_begin(),
1308                                            AddRec->op_end());
1309       AddRecOps[0] = getAddExpr(LIOps);
1310
1311       const SCEV* NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
1312       // If all of the other operands were loop invariant, we are done.
1313       if (Ops.size() == 1) return NewRec;
1314
1315       // Otherwise, add the folded AddRec by the non-liv parts.
1316       for (unsigned i = 0;; ++i)
1317         if (Ops[i] == AddRec) {
1318           Ops[i] = NewRec;
1319           break;
1320         }
1321       return getAddExpr(Ops);
1322     }
1323
1324     // Okay, if there weren't any loop invariants to be folded, check to see if
1325     // there are multiple AddRec's with the same loop induction variable being
1326     // added together.  If so, we can fold them.
1327     for (unsigned OtherIdx = Idx+1;
1328          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1329       if (OtherIdx != Idx) {
1330         const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1331         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1332           // Other + {A,+,B} + {C,+,D}  -->  Other + {A+C,+,B+D}
1333           SmallVector<const SCEV*, 4> NewOps(AddRec->op_begin(), AddRec->op_end());
1334           for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
1335             if (i >= NewOps.size()) {
1336               NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
1337                             OtherAddRec->op_end());
1338               break;
1339             }
1340             NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
1341           }
1342           const SCEV* NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
1343
1344           if (Ops.size() == 2) return NewAddRec;
1345
1346           Ops.erase(Ops.begin()+Idx);
1347           Ops.erase(Ops.begin()+OtherIdx-1);
1348           Ops.push_back(NewAddRec);
1349           return getAddExpr(Ops);
1350         }
1351       }
1352
1353     // Otherwise couldn't fold anything into this recurrence.  Move onto the
1354     // next one.
1355   }
1356
1357   // Okay, it looks like we really DO need an add expr.  Check to see if we
1358   // already have one, otherwise create a new one.
1359   std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1360   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
1361                                                                  SCEVOps)];
1362   if (Result == 0) Result = new SCEVAddExpr(Ops);
1363   return Result;
1364 }
1365
1366
1367 /// getMulExpr - Get a canonical multiply expression, or something simpler if
1368 /// possible.
1369 const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
1370   assert(!Ops.empty() && "Cannot get empty mul!");
1371 #ifndef NDEBUG
1372   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1373     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1374            getEffectiveSCEVType(Ops[0]->getType()) &&
1375            "SCEVMulExpr operand types don't match!");
1376 #endif
1377
1378   // Sort by complexity, this groups all similar expression types together.
1379   GroupByComplexity(Ops, LI);
1380
1381   // If there are any constants, fold them together.
1382   unsigned Idx = 0;
1383   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1384
1385     // C1*(C2+V) -> C1*C2 + C1*V
1386     if (Ops.size() == 2)
1387       if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
1388         if (Add->getNumOperands() == 2 &&
1389             isa<SCEVConstant>(Add->getOperand(0)))
1390           return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
1391                             getMulExpr(LHSC, Add->getOperand(1)));
1392
1393
1394     ++Idx;
1395     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1396       // We found two constants, fold them together!
1397       ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
1398                                            RHSC->getValue()->getValue());
1399       Ops[0] = getConstant(Fold);
1400       Ops.erase(Ops.begin()+1);  // Erase the folded element
1401       if (Ops.size() == 1) return Ops[0];
1402       LHSC = cast<SCEVConstant>(Ops[0]);
1403     }
1404
1405     // If we are left with a constant one being multiplied, strip it off.
1406     if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
1407       Ops.erase(Ops.begin());
1408       --Idx;
1409     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
1410       // If we have a multiply of zero, it will always be zero.
1411       return Ops[0];
1412     }
1413   }
1414
1415   // Skip over the add expression until we get to a multiply.
1416   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
1417     ++Idx;
1418
1419   if (Ops.size() == 1)
1420     return Ops[0];
1421
1422   // If there are mul operands inline them all into this expression.
1423   if (Idx < Ops.size()) {
1424     bool DeletedMul = false;
1425     while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
1426       // If we have an mul, expand the mul operands onto the end of the operands
1427       // list.
1428       Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
1429       Ops.erase(Ops.begin()+Idx);
1430       DeletedMul = true;
1431     }
1432
1433     // If we deleted at least one mul, we added operands to the end of the list,
1434     // and they are not necessarily sorted.  Recurse to resort and resimplify
1435     // any operands we just aquired.
1436     if (DeletedMul)
1437       return getMulExpr(Ops);
1438   }
1439
1440   // If there are any add recurrences in the operands list, see if any other
1441   // added values are loop invariant.  If so, we can fold them into the
1442   // recurrence.
1443   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1444     ++Idx;
1445
1446   // Scan over all recurrences, trying to fold loop invariants into them.
1447   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1448     // Scan all of the other operands to this mul and add them to the vector if
1449     // they are loop invariant w.r.t. the recurrence.
1450     SmallVector<const SCEV*, 8> LIOps;
1451     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1452     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1453       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1454         LIOps.push_back(Ops[i]);
1455         Ops.erase(Ops.begin()+i);
1456         --i; --e;
1457       }
1458
1459     // If we found some loop invariants, fold them into the recurrence.
1460     if (!LIOps.empty()) {
1461       //  NLI * LI * {Start,+,Step}  -->  NLI * {LI*Start,+,LI*Step}
1462       SmallVector<const SCEV*, 4> NewOps;
1463       NewOps.reserve(AddRec->getNumOperands());
1464       if (LIOps.size() == 1) {
1465         const SCEV *Scale = LIOps[0];
1466         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
1467           NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
1468       } else {
1469         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
1470           SmallVector<const SCEV*, 4> MulOps(LIOps.begin(), LIOps.end());
1471           MulOps.push_back(AddRec->getOperand(i));
1472           NewOps.push_back(getMulExpr(MulOps));
1473         }
1474       }
1475
1476       const SCEV* NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
1477
1478       // If all of the other operands were loop invariant, we are done.
1479       if (Ops.size() == 1) return NewRec;
1480
1481       // Otherwise, multiply the folded AddRec by the non-liv parts.
1482       for (unsigned i = 0;; ++i)
1483         if (Ops[i] == AddRec) {
1484           Ops[i] = NewRec;
1485           break;
1486         }
1487       return getMulExpr(Ops);
1488     }
1489
1490     // Okay, if there weren't any loop invariants to be folded, check to see if
1491     // there are multiple AddRec's with the same loop induction variable being
1492     // multiplied together.  If so, we can fold them.
1493     for (unsigned OtherIdx = Idx+1;
1494          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1495       if (OtherIdx != Idx) {
1496         const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1497         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1498           // F * G  -->  {A,+,B} * {C,+,D}  -->  {A*C,+,F*D + G*B + B*D}
1499           const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
1500           const SCEV* NewStart = getMulExpr(F->getStart(),
1501                                                  G->getStart());
1502           const SCEV* B = F->getStepRecurrence(*this);
1503           const SCEV* D = G->getStepRecurrence(*this);
1504           const SCEV* NewStep = getAddExpr(getMulExpr(F, D),
1505                                           getMulExpr(G, B),
1506                                           getMulExpr(B, D));
1507           const SCEV* NewAddRec = getAddRecExpr(NewStart, NewStep,
1508                                                F->getLoop());
1509           if (Ops.size() == 2) return NewAddRec;
1510
1511           Ops.erase(Ops.begin()+Idx);
1512           Ops.erase(Ops.begin()+OtherIdx-1);
1513           Ops.push_back(NewAddRec);
1514           return getMulExpr(Ops);
1515         }
1516       }
1517
1518     // Otherwise couldn't fold anything into this recurrence.  Move onto the
1519     // next one.
1520   }
1521
1522   // Okay, it looks like we really DO need an mul expr.  Check to see if we
1523   // already have one, otherwise create a new one.
1524   std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1525   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
1526                                                                  SCEVOps)];
1527   if (Result == 0)
1528     Result = new SCEVMulExpr(Ops);
1529   return Result;
1530 }
1531
1532 /// getUDivExpr - Get a canonical multiply expression, or something simpler if
1533 /// possible.
1534 const SCEV* ScalarEvolution::getUDivExpr(const SCEV* LHS,
1535                                         const SCEV* RHS) {
1536   assert(getEffectiveSCEVType(LHS->getType()) ==
1537          getEffectiveSCEVType(RHS->getType()) &&
1538          "SCEVUDivExpr operand types don't match!");
1539
1540   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
1541     if (RHSC->getValue()->equalsInt(1))
1542       return LHS;                            // X udiv 1 --> x
1543     if (RHSC->isZero())
1544       return getIntegerSCEV(0, LHS->getType()); // value is undefined
1545
1546     // Determine if the division can be folded into the operands of
1547     // its operands.
1548     // TODO: Generalize this to non-constants by using known-bits information.
1549     const Type *Ty = LHS->getType();
1550     unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
1551     unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ;
1552     // For non-power-of-two values, effectively round the value up to the
1553     // nearest power of two.
1554     if (!RHSC->getValue()->getValue().isPowerOf2())
1555       ++MaxShiftAmt;
1556     const IntegerType *ExtTy =
1557       IntegerType::get(getTypeSizeInBits(Ty) + MaxShiftAmt);
1558     // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
1559     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS))
1560       if (const SCEVConstant *Step =
1561             dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this)))
1562         if (!Step->getValue()->getValue()
1563               .urem(RHSC->getValue()->getValue()) &&
1564             getZeroExtendExpr(AR, ExtTy) ==
1565             getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy),
1566                           getZeroExtendExpr(Step, ExtTy),
1567                           AR->getLoop())) {
1568           SmallVector<const SCEV*, 4> Operands;
1569           for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
1570             Operands.push_back(getUDivExpr(AR->getOperand(i), RHS));
1571           return getAddRecExpr(Operands, AR->getLoop());
1572         }
1573     // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
1574     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
1575       SmallVector<const SCEV*, 4> Operands;
1576       for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
1577         Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy));
1578       if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands))
1579         // Find an operand that's safely divisible.
1580         for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
1581           const SCEV* Op = M->getOperand(i);
1582           const SCEV* Div = getUDivExpr(Op, RHSC);
1583           if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
1584             const SmallVectorImpl<const SCEV*> &MOperands = M->getOperands();
1585             Operands = SmallVector<const SCEV*, 4>(MOperands.begin(),
1586                                                   MOperands.end());
1587             Operands[i] = Div;
1588             return getMulExpr(Operands);
1589           }
1590         }
1591     }
1592     // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
1593     if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) {
1594       SmallVector<const SCEV*, 4> Operands;
1595       for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i)
1596         Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy));
1597       if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
1598         Operands.clear();
1599         for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {
1600           const SCEV* Op = getUDivExpr(A->getOperand(i), RHS);
1601           if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i))
1602             break;
1603           Operands.push_back(Op);
1604         }
1605         if (Operands.size() == A->getNumOperands())
1606           return getAddExpr(Operands);
1607       }
1608     }
1609
1610     // Fold if both operands are constant.
1611     if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1612       Constant *LHSCV = LHSC->getValue();
1613       Constant *RHSCV = RHSC->getValue();
1614       return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
1615     }
1616   }
1617
1618   SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
1619   if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
1620   return Result;
1621 }
1622
1623
1624 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
1625 /// Simplify the expression as much as possible.
1626 const SCEV* ScalarEvolution::getAddRecExpr(const SCEV* Start,
1627                                const SCEV* Step, const Loop *L) {
1628   SmallVector<const SCEV*, 4> Operands;
1629   Operands.push_back(Start);
1630   if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
1631     if (StepChrec->getLoop() == L) {
1632       Operands.insert(Operands.end(), StepChrec->op_begin(),
1633                       StepChrec->op_end());
1634       return getAddRecExpr(Operands, L);
1635     }
1636
1637   Operands.push_back(Step);
1638   return getAddRecExpr(Operands, L);
1639 }
1640
1641 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
1642 /// Simplify the expression as much as possible.
1643 const SCEV* ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands,
1644                                           const Loop *L) {
1645   if (Operands.size() == 1) return Operands[0];
1646 #ifndef NDEBUG
1647   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
1648     assert(getEffectiveSCEVType(Operands[i]->getType()) ==
1649            getEffectiveSCEVType(Operands[0]->getType()) &&
1650            "SCEVAddRecExpr operand types don't match!");
1651 #endif
1652
1653   if (Operands.back()->isZero()) {
1654     Operands.pop_back();
1655     return getAddRecExpr(Operands, L);             // {X,+,0}  -->  X
1656   }
1657
1658   // Canonicalize nested AddRecs in by nesting them in order of loop depth.
1659   if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
1660     const Loop* NestedLoop = NestedAR->getLoop();
1661     if (L->getLoopDepth() < NestedLoop->getLoopDepth()) {
1662       SmallVector<const SCEV*, 4> NestedOperands(NestedAR->op_begin(),
1663                                                 NestedAR->op_end());
1664       Operands[0] = NestedAR->getStart();
1665       NestedOperands[0] = getAddRecExpr(Operands, L);
1666       return getAddRecExpr(NestedOperands, NestedLoop);
1667     }
1668   }
1669
1670   std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
1671   SCEVAddRecExpr *&Result = SCEVAddRecExprs[std::make_pair(L, SCEVOps)];
1672   if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
1673   return Result;
1674 }
1675
1676 const SCEV* ScalarEvolution::getSMaxExpr(const SCEV* LHS,
1677                                         const SCEV* RHS) {
1678   SmallVector<const SCEV*, 2> Ops;
1679   Ops.push_back(LHS);
1680   Ops.push_back(RHS);
1681   return getSMaxExpr(Ops);
1682 }
1683
1684 const SCEV*
1685 ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
1686   assert(!Ops.empty() && "Cannot get empty smax!");
1687   if (Ops.size() == 1) return Ops[0];
1688 #ifndef NDEBUG
1689   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1690     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1691            getEffectiveSCEVType(Ops[0]->getType()) &&
1692            "SCEVSMaxExpr operand types don't match!");
1693 #endif
1694
1695   // Sort by complexity, this groups all similar expression types together.
1696   GroupByComplexity(Ops, LI);
1697
1698   // If there are any constants, fold them together.
1699   unsigned Idx = 0;
1700   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1701     ++Idx;
1702     assert(Idx < Ops.size());
1703     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1704       // We found two constants, fold them together!
1705       ConstantInt *Fold = ConstantInt::get(
1706                               APIntOps::smax(LHSC->getValue()->getValue(),
1707                                              RHSC->getValue()->getValue()));
1708       Ops[0] = getConstant(Fold);
1709       Ops.erase(Ops.begin()+1);  // Erase the folded element
1710       if (Ops.size() == 1) return Ops[0];
1711       LHSC = cast<SCEVConstant>(Ops[0]);
1712     }
1713
1714     // If we are left with a constant -inf, strip it off.
1715     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
1716       Ops.erase(Ops.begin());
1717       --Idx;
1718     }
1719   }
1720
1721   if (Ops.size() == 1) return Ops[0];
1722
1723   // Find the first SMax
1724   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
1725     ++Idx;
1726
1727   // Check to see if one of the operands is an SMax. If so, expand its operands
1728   // onto our operand list, and recurse to simplify.
1729   if (Idx < Ops.size()) {
1730     bool DeletedSMax = false;
1731     while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
1732       Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
1733       Ops.erase(Ops.begin()+Idx);
1734       DeletedSMax = true;
1735     }
1736
1737     if (DeletedSMax)
1738       return getSMaxExpr(Ops);
1739   }
1740
1741   // Okay, check to see if the same value occurs in the operand list twice.  If
1742   // so, delete one.  Since we sorted the list, these values are required to
1743   // be adjacent.
1744   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1745     if (Ops[i] == Ops[i+1]) {      //  X smax Y smax Y  -->  X smax Y
1746       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1747       --i; --e;
1748     }
1749
1750   if (Ops.size() == 1) return Ops[0];
1751
1752   assert(!Ops.empty() && "Reduced smax down to nothing!");
1753
1754   // Okay, it looks like we really DO need an smax expr.  Check to see if we
1755   // already have one, otherwise create a new one.
1756   std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1757   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scSMaxExpr,
1758                                                                  SCEVOps)];
1759   if (Result == 0) Result = new SCEVSMaxExpr(Ops);
1760   return Result;
1761 }
1762
1763 const SCEV* ScalarEvolution::getUMaxExpr(const SCEV* LHS,
1764                                         const SCEV* RHS) {
1765   SmallVector<const SCEV*, 2> Ops;
1766   Ops.push_back(LHS);
1767   Ops.push_back(RHS);
1768   return getUMaxExpr(Ops);
1769 }
1770
1771 const SCEV*
1772 ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV*> &Ops) {
1773   assert(!Ops.empty() && "Cannot get empty umax!");
1774   if (Ops.size() == 1) return Ops[0];
1775 #ifndef NDEBUG
1776   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
1777     assert(getEffectiveSCEVType(Ops[i]->getType()) ==
1778            getEffectiveSCEVType(Ops[0]->getType()) &&
1779            "SCEVUMaxExpr operand types don't match!");
1780 #endif
1781
1782   // Sort by complexity, this groups all similar expression types together.
1783   GroupByComplexity(Ops, LI);
1784
1785   // If there are any constants, fold them together.
1786   unsigned Idx = 0;
1787   if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1788     ++Idx;
1789     assert(Idx < Ops.size());
1790     while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1791       // We found two constants, fold them together!
1792       ConstantInt *Fold = ConstantInt::get(
1793                               APIntOps::umax(LHSC->getValue()->getValue(),
1794                                              RHSC->getValue()->getValue()));
1795       Ops[0] = getConstant(Fold);
1796       Ops.erase(Ops.begin()+1);  // Erase the folded element
1797       if (Ops.size() == 1) return Ops[0];
1798       LHSC = cast<SCEVConstant>(Ops[0]);
1799     }
1800
1801     // If we are left with a constant zero, strip it off.
1802     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
1803       Ops.erase(Ops.begin());
1804       --Idx;
1805     }
1806   }
1807
1808   if (Ops.size() == 1) return Ops[0];
1809
1810   // Find the first UMax
1811   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
1812     ++Idx;
1813
1814   // Check to see if one of the operands is a UMax. If so, expand its operands
1815   // onto our operand list, and recurse to simplify.
1816   if (Idx < Ops.size()) {
1817     bool DeletedUMax = false;
1818     while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
1819       Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
1820       Ops.erase(Ops.begin()+Idx);
1821       DeletedUMax = true;
1822     }
1823
1824     if (DeletedUMax)
1825       return getUMaxExpr(Ops);
1826   }
1827
1828   // Okay, check to see if the same value occurs in the operand list twice.  If
1829   // so, delete one.  Since we sorted the list, these values are required to
1830   // be adjacent.
1831   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1832     if (Ops[i] == Ops[i+1]) {      //  X umax Y umax Y  -->  X umax Y
1833       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1834       --i; --e;
1835     }
1836
1837   if (Ops.size() == 1) return Ops[0];
1838
1839   assert(!Ops.empty() && "Reduced umax down to nothing!");
1840
1841   // Okay, it looks like we really DO need a umax expr.  Check to see if we
1842   // already have one, otherwise create a new one.
1843   std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1844   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scUMaxExpr,
1845                                                                  SCEVOps)];
1846   if (Result == 0) Result = new SCEVUMaxExpr(Ops);
1847   return Result;
1848 }
1849
1850 const SCEV* ScalarEvolution::getSMinExpr(const SCEV* LHS,
1851                                         const SCEV* RHS) {
1852   // ~smax(~x, ~y) == smin(x, y).
1853   return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
1854 }
1855
1856 const SCEV* ScalarEvolution::getUMinExpr(const SCEV* LHS,
1857                                         const SCEV* RHS) {
1858   // ~umax(~x, ~y) == umin(x, y)
1859   return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
1860 }
1861
1862 const SCEV* ScalarEvolution::getUnknown(Value *V) {
1863   if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
1864     return getConstant(CI);
1865   if (isa<ConstantPointerNull>(V))
1866     return getIntegerSCEV(0, V->getType());
1867   SCEVUnknown *&Result = SCEVUnknowns[V];
1868   if (Result == 0) Result = new SCEVUnknown(V);
1869   return Result;
1870 }
1871
1872 //===----------------------------------------------------------------------===//
1873 //            Basic SCEV Analysis and PHI Idiom Recognition Code
1874 //
1875
1876 /// isSCEVable - Test if values of the given type are analyzable within
1877 /// the SCEV framework. This primarily includes integer types, and it
1878 /// can optionally include pointer types if the ScalarEvolution class
1879 /// has access to target-specific information.
1880 bool ScalarEvolution::isSCEVable(const Type *Ty) const {
1881   // Integers are always SCEVable.
1882   if (Ty->isInteger())
1883     return true;
1884
1885   // Pointers are SCEVable if TargetData information is available
1886   // to provide pointer size information.
1887   if (isa<PointerType>(Ty))
1888     return TD != NULL;
1889
1890   // Otherwise it's not SCEVable.
1891   return false;
1892 }
1893
1894 /// getTypeSizeInBits - Return the size in bits of the specified type,
1895 /// for which isSCEVable must return true.
1896 uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const {
1897   assert(isSCEVable(Ty) && "Type is not SCEVable!");
1898
1899   // If we have a TargetData, use it!
1900   if (TD)
1901     return TD->getTypeSizeInBits(Ty);
1902
1903   // Otherwise, we support only integer types.
1904   assert(Ty->isInteger() && "isSCEVable permitted a non-SCEVable type!");
1905   return Ty->getPrimitiveSizeInBits();
1906 }
1907
1908 /// getEffectiveSCEVType - Return a type with the same bitwidth as
1909 /// the given type and which represents how SCEV will treat the given
1910 /// type, for which isSCEVable must return true. For pointer types,
1911 /// this is the pointer-sized integer type.
1912 const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const {
1913   assert(isSCEVable(Ty) && "Type is not SCEVable!");
1914
1915   if (Ty->isInteger())
1916     return Ty;
1917
1918   assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
1919   return TD->getIntPtrType();
1920 }
1921
1922 const SCEV* ScalarEvolution::getCouldNotCompute() {
1923   return CouldNotCompute;
1924 }
1925
1926 /// hasSCEV - Return true if the SCEV for this value has already been
1927 /// computed.
1928 bool ScalarEvolution::hasSCEV(Value *V) const {
1929   return Scalars.count(V);
1930 }
1931
1932 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1933 /// expression and create a new one.
1934 const SCEV* ScalarEvolution::getSCEV(Value *V) {
1935   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
1936
1937   std::map<SCEVCallbackVH, const SCEV*>::iterator I = Scalars.find(V);
1938   if (I != Scalars.end()) return I->second;
1939   const SCEV* S = createSCEV(V);
1940   Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S));
1941   return S;
1942 }
1943
1944 /// getIntegerSCEV - Given an integer or FP type, create a constant for the
1945 /// specified signed integer value and return a SCEV for the constant.
1946 const SCEV* ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
1947   Ty = getEffectiveSCEVType(Ty);
1948   Constant *C;
1949   if (Val == 0)
1950     C = Constant::getNullValue(Ty);
1951   else if (Ty->isFloatingPoint())
1952     C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
1953                                 APFloat::IEEEdouble, Val));
1954   else
1955     C = ConstantInt::get(Ty, Val);
1956   return getUnknown(C);
1957 }
1958
1959 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
1960 ///
1961 const SCEV* ScalarEvolution::getNegativeSCEV(const SCEV* V) {
1962   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
1963     return getUnknown(ConstantExpr::getNeg(VC->getValue()));
1964
1965   const Type *Ty = V->getType();
1966   Ty = getEffectiveSCEVType(Ty);
1967   return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(Ty)));
1968 }
1969
1970 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
1971 const SCEV* ScalarEvolution::getNotSCEV(const SCEV* V) {
1972   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
1973     return getUnknown(ConstantExpr::getNot(VC->getValue()));
1974
1975   const Type *Ty = V->getType();
1976   Ty = getEffectiveSCEVType(Ty);
1977   const SCEV* AllOnes = getConstant(ConstantInt::getAllOnesValue(Ty));
1978   return getMinusSCEV(AllOnes, V);
1979 }
1980
1981 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
1982 ///
1983 const SCEV* ScalarEvolution::getMinusSCEV(const SCEV* LHS,
1984                                          const SCEV* RHS) {
1985   // X - Y --> X + -Y
1986   return getAddExpr(LHS, getNegativeSCEV(RHS));
1987 }
1988
1989 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
1990 /// input value to the specified type.  If the type must be extended, it is zero
1991 /// extended.
1992 const SCEV*
1993 ScalarEvolution::getTruncateOrZeroExtend(const SCEV* V,
1994                                          const Type *Ty) {
1995   const Type *SrcTy = V->getType();
1996   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
1997          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
1998          "Cannot truncate or zero extend with non-integer arguments!");
1999   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2000     return V;  // No conversion
2001   if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
2002     return getTruncateExpr(V, Ty);
2003   return getZeroExtendExpr(V, Ty);
2004 }
2005
2006 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the
2007 /// input value to the specified type.  If the type must be extended, it is sign
2008 /// extended.
2009 const SCEV*
2010 ScalarEvolution::getTruncateOrSignExtend(const SCEV* V,
2011                                          const Type *Ty) {
2012   const Type *SrcTy = V->getType();
2013   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
2014          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
2015          "Cannot truncate or zero extend with non-integer arguments!");
2016   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2017     return V;  // No conversion
2018   if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty))
2019     return getTruncateExpr(V, Ty);
2020   return getSignExtendExpr(V, Ty);
2021 }
2022
2023 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the
2024 /// input value to the specified type.  If the type must be extended, it is zero
2025 /// extended.  The conversion must not be narrowing.
2026 const SCEV*
2027 ScalarEvolution::getNoopOrZeroExtend(const SCEV* V, const Type *Ty) {
2028   const Type *SrcTy = V->getType();
2029   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
2030          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
2031          "Cannot noop or zero extend with non-integer arguments!");
2032   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2033          "getNoopOrZeroExtend cannot truncate!");
2034   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2035     return V;  // No conversion
2036   return getZeroExtendExpr(V, Ty);
2037 }
2038
2039 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the
2040 /// input value to the specified type.  If the type must be extended, it is sign
2041 /// extended.  The conversion must not be narrowing.
2042 const SCEV*
2043 ScalarEvolution::getNoopOrSignExtend(const SCEV* V, const Type *Ty) {
2044   const Type *SrcTy = V->getType();
2045   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
2046          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
2047          "Cannot noop or sign extend with non-integer arguments!");
2048   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2049          "getNoopOrSignExtend cannot truncate!");
2050   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2051     return V;  // No conversion
2052   return getSignExtendExpr(V, Ty);
2053 }
2054
2055 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of
2056 /// the input value to the specified type. If the type must be extended,
2057 /// it is extended with unspecified bits. The conversion must not be
2058 /// narrowing.
2059 const SCEV*
2060 ScalarEvolution::getNoopOrAnyExtend(const SCEV* V, const Type *Ty) {
2061   const Type *SrcTy = V->getType();
2062   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
2063          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
2064          "Cannot noop or any extend with non-integer arguments!");
2065   assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) &&
2066          "getNoopOrAnyExtend cannot truncate!");
2067   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2068     return V;  // No conversion
2069   return getAnyExtendExpr(V, Ty);
2070 }
2071
2072 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the
2073 /// input value to the specified type.  The conversion must not be widening.
2074 const SCEV*
2075 ScalarEvolution::getTruncateOrNoop(const SCEV* V, const Type *Ty) {
2076   const Type *SrcTy = V->getType();
2077   assert((SrcTy->isInteger() || (TD && isa<PointerType>(SrcTy))) &&
2078          (Ty->isInteger() || (TD && isa<PointerType>(Ty))) &&
2079          "Cannot truncate or noop with non-integer arguments!");
2080   assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) &&
2081          "getTruncateOrNoop cannot extend!");
2082   if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty))
2083     return V;  // No conversion
2084   return getTruncateExpr(V, Ty);
2085 }
2086
2087 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of
2088 /// the types using zero-extension, and then perform a umax operation
2089 /// with them.
2090 const SCEV* ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV* LHS,
2091                                                        const SCEV* RHS) {
2092   const SCEV* PromotedLHS = LHS;
2093   const SCEV* PromotedRHS = RHS;
2094
2095   if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
2096     PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
2097   else
2098     PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
2099
2100   return getUMaxExpr(PromotedLHS, PromotedRHS);
2101 }
2102
2103 /// getUMinFromMismatchedTypes - Promote the operands to the wider of
2104 /// the types using zero-extension, and then perform a umin operation
2105 /// with them.
2106 const SCEV* ScalarEvolution::getUMinFromMismatchedTypes(const SCEV* LHS,
2107                                                        const SCEV* RHS) {
2108   const SCEV* PromotedLHS = LHS;
2109   const SCEV* PromotedRHS = RHS;
2110
2111   if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType()))
2112     PromotedRHS = getZeroExtendExpr(RHS, LHS->getType());
2113   else
2114     PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType());
2115
2116   return getUMinExpr(PromotedLHS, PromotedRHS);
2117 }
2118
2119 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
2120 /// the specified instruction and replaces any references to the symbolic value
2121 /// SymName with the specified value.  This is used during PHI resolution.
2122 void ScalarEvolution::
2123 ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEV* SymName,
2124                                  const SCEV* NewVal) {
2125   std::map<SCEVCallbackVH, const SCEV*>::iterator SI =
2126     Scalars.find(SCEVCallbackVH(I, this));
2127   if (SI == Scalars.end()) return;
2128
2129   const SCEV* NV =
2130     SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, *this);
2131   if (NV == SI->second) return;  // No change.
2132
2133   SI->second = NV;       // Update the scalars map!
2134
2135   // Any instruction values that use this instruction might also need to be
2136   // updated!
2137   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
2138        UI != E; ++UI)
2139     ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
2140 }
2141
2142 /// createNodeForPHI - PHI nodes have two cases.  Either the PHI node exists in
2143 /// a loop header, making it a potential recurrence, or it doesn't.
2144 ///
2145 const SCEV* ScalarEvolution::createNodeForPHI(PHINode *PN) {
2146   if (PN->getNumIncomingValues() == 2)  // The loops have been canonicalized.
2147     if (const Loop *L = LI->getLoopFor(PN->getParent()))
2148       if (L->getHeader() == PN->getParent()) {
2149         // If it lives in the loop header, it has two incoming values, one
2150         // from outside the loop, and one from inside.
2151         unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
2152         unsigned BackEdge     = IncomingEdge^1;
2153
2154         // While we are analyzing this PHI node, handle its value symbolically.
2155         const SCEV* SymbolicName = getUnknown(PN);
2156         assert(Scalars.find(PN) == Scalars.end() &&
2157                "PHI node already processed?");
2158         Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName));
2159
2160         // Using this symbolic name for the PHI, analyze the value coming around
2161         // the back-edge.
2162         const SCEV* BEValue = getSCEV(PN->getIncomingValue(BackEdge));
2163
2164         // NOTE: If BEValue is loop invariant, we know that the PHI node just
2165         // has a special value for the first iteration of the loop.
2166
2167         // If the value coming around the backedge is an add with the symbolic
2168         // value we just inserted, then we found a simple induction variable!
2169         if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
2170           // If there is a single occurrence of the symbolic value, replace it
2171           // with a recurrence.
2172           unsigned FoundIndex = Add->getNumOperands();
2173           for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
2174             if (Add->getOperand(i) == SymbolicName)
2175               if (FoundIndex == e) {
2176                 FoundIndex = i;
2177                 break;
2178               }
2179
2180           if (FoundIndex != Add->getNumOperands()) {
2181             // Create an add with everything but the specified operand.
2182             SmallVector<const SCEV*, 8> Ops;
2183             for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
2184               if (i != FoundIndex)
2185                 Ops.push_back(Add->getOperand(i));
2186             const SCEV* Accum = getAddExpr(Ops);
2187
2188             // This is not a valid addrec if the step amount is varying each
2189             // loop iteration, but is not itself an addrec in this loop.
2190             if (Accum->isLoopInvariant(L) ||
2191                 (isa<SCEVAddRecExpr>(Accum) &&
2192                  cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
2193               const SCEV* StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
2194               const SCEV* PHISCEV  = getAddRecExpr(StartVal, Accum, L);
2195
2196               // Okay, for the entire analysis of this edge we assumed the PHI
2197               // to be symbolic.  We now need to go back and update all of the
2198               // entries for the scalars that use the PHI (except for the PHI
2199               // itself) to use the new analyzed value instead of the "symbolic"
2200               // value.
2201               ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
2202               return PHISCEV;
2203             }
2204           }
2205         } else if (const SCEVAddRecExpr *AddRec =
2206                      dyn_cast<SCEVAddRecExpr>(BEValue)) {
2207           // Otherwise, this could be a loop like this:
2208           //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
2209           // In this case, j = {1,+,1}  and BEValue is j.
2210           // Because the other in-value of i (0) fits the evolution of BEValue
2211           // i really is an addrec evolution.
2212           if (AddRec->getLoop() == L && AddRec->isAffine()) {
2213             const SCEV* StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
2214
2215             // If StartVal = j.start - j.stride, we can use StartVal as the
2216             // initial step of the addrec evolution.
2217             if (StartVal == getMinusSCEV(AddRec->getOperand(0),
2218                                             AddRec->getOperand(1))) {
2219               const SCEV* PHISCEV =
2220                  getAddRecExpr(StartVal, AddRec->getOperand(1), L);
2221
2222               // Okay, for the entire analysis of this edge we assumed the PHI
2223               // to be symbolic.  We now need to go back and update all of the
2224               // entries for the scalars that use the PHI (except for the PHI
2225               // itself) to use the new analyzed value instead of the "symbolic"
2226               // value.
2227               ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
2228               return PHISCEV;
2229             }
2230           }
2231         }
2232
2233         return SymbolicName;
2234       }
2235
2236   // If it's not a loop phi, we can't handle it yet.
2237   return getUnknown(PN);
2238 }
2239
2240 /// createNodeForGEP - Expand GEP instructions into add and multiply
2241 /// operations. This allows them to be analyzed by regular SCEV code.
2242 ///
2243 const SCEV* ScalarEvolution::createNodeForGEP(User *GEP) {
2244
2245   const Type *IntPtrTy = TD->getIntPtrType();
2246   Value *Base = GEP->getOperand(0);
2247   // Don't attempt to analyze GEPs over unsized objects.
2248   if (!cast<PointerType>(Base->getType())->getElementType()->isSized())
2249     return getUnknown(GEP);
2250   const SCEV* TotalOffset = getIntegerSCEV(0, IntPtrTy);
2251   gep_type_iterator GTI = gep_type_begin(GEP);
2252   for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()),
2253                                       E = GEP->op_end();
2254        I != E; ++I) {
2255     Value *Index = *I;
2256     // Compute the (potentially symbolic) offset in bytes for this index.
2257     if (const StructType *STy = dyn_cast<StructType>(*GTI++)) {
2258       // For a struct, add the member offset.
2259       const StructLayout &SL = *TD->getStructLayout(STy);
2260       unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
2261       uint64_t Offset = SL.getElementOffset(FieldNo);
2262       TotalOffset = getAddExpr(TotalOffset,
2263                                   getIntegerSCEV(Offset, IntPtrTy));
2264     } else {
2265       // For an array, add the element offset, explicitly scaled.
2266       const SCEV* LocalOffset = getSCEV(Index);
2267       if (!isa<PointerType>(LocalOffset->getType()))
2268         // Getelementptr indicies are signed.
2269         LocalOffset = getTruncateOrSignExtend(LocalOffset,
2270                                               IntPtrTy);
2271       LocalOffset =
2272         getMulExpr(LocalOffset,
2273                    getIntegerSCEV(TD->getTypeAllocSize(*GTI),
2274                                   IntPtrTy));
2275       TotalOffset = getAddExpr(TotalOffset, LocalOffset);
2276     }
2277   }
2278   return getAddExpr(getSCEV(Base), TotalOffset);
2279 }
2280
2281 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
2282 /// guaranteed to end in (at every loop iteration).  It is, at the same time,
2283 /// the minimum number of times S is divisible by 2.  For example, given {4,+,8}
2284 /// it returns 2.  If S is guaranteed to be 0, it returns the bitwidth of S.
2285 uint32_t
2286 ScalarEvolution::GetMinTrailingZeros(const SCEV* S) {
2287   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
2288     return C->getValue()->getValue().countTrailingZeros();
2289
2290   if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
2291     return std::min(GetMinTrailingZeros(T->getOperand()),
2292                     (uint32_t)getTypeSizeInBits(T->getType()));
2293
2294   if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
2295     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
2296     return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
2297              getTypeSizeInBits(E->getType()) : OpRes;
2298   }
2299
2300   if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
2301     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
2302     return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ?
2303              getTypeSizeInBits(E->getType()) : OpRes;
2304   }
2305
2306   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
2307     // The result is the min of all operands results.
2308     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
2309     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
2310       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
2311     return MinOpRes;
2312   }
2313
2314   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
2315     // The result is the sum of all operands results.
2316     uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
2317     uint32_t BitWidth = getTypeSizeInBits(M->getType());
2318     for (unsigned i = 1, e = M->getNumOperands();
2319          SumOpRes != BitWidth && i != e; ++i)
2320       SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
2321                           BitWidth);
2322     return SumOpRes;
2323   }
2324
2325   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
2326     // The result is the min of all operands results.
2327     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
2328     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
2329       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
2330     return MinOpRes;
2331   }
2332
2333   if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
2334     // The result is the min of all operands results.
2335     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
2336     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
2337       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
2338     return MinOpRes;
2339   }
2340
2341   if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
2342     // The result is the min of all operands results.
2343     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
2344     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
2345       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
2346     return MinOpRes;
2347   }
2348
2349   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2350     // For a SCEVUnknown, ask ValueTracking.
2351     unsigned BitWidth = getTypeSizeInBits(U->getType());
2352     APInt Mask = APInt::getAllOnesValue(BitWidth);
2353     APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
2354     ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones);
2355     return Zeros.countTrailingOnes();
2356   }
2357
2358   // SCEVUDivExpr
2359   return 0;
2360 }
2361
2362 uint32_t
2363 ScalarEvolution::GetMinLeadingZeros(const SCEV* S) {
2364   // TODO: Handle other SCEV expression types here.
2365
2366   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
2367     return C->getValue()->getValue().countLeadingZeros();
2368
2369   if (const SCEVZeroExtendExpr *C = dyn_cast<SCEVZeroExtendExpr>(S)) {
2370     // A zero-extension cast adds zero bits.
2371     return GetMinLeadingZeros(C->getOperand()) +
2372            (getTypeSizeInBits(C->getType()) -
2373             getTypeSizeInBits(C->getOperand()->getType()));
2374   }
2375
2376   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2377     // For a SCEVUnknown, ask ValueTracking.
2378     unsigned BitWidth = getTypeSizeInBits(U->getType());
2379     APInt Mask = APInt::getAllOnesValue(BitWidth);
2380     APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
2381     ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD);
2382     return Zeros.countLeadingOnes();
2383   }
2384
2385   return 1;
2386 }
2387
2388 uint32_t
2389 ScalarEvolution::GetMinSignBits(const SCEV* S) {
2390   // TODO: Handle other SCEV expression types here.
2391
2392   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
2393     const APInt &A = C->getValue()->getValue();
2394     return A.isNegative() ? A.countLeadingOnes() :
2395                             A.countLeadingZeros();
2396   }
2397
2398   if (const SCEVSignExtendExpr *C = dyn_cast<SCEVSignExtendExpr>(S)) {
2399     // A sign-extension cast adds sign bits.
2400     return GetMinSignBits(C->getOperand()) +
2401            (getTypeSizeInBits(C->getType()) -
2402             getTypeSizeInBits(C->getOperand()->getType()));
2403   }
2404
2405   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2406     // For a SCEVUnknown, ask ValueTracking.
2407     return ComputeNumSignBits(U->getValue(), TD);
2408   }
2409
2410   return 1;
2411 }
2412
2413 /// createSCEV - We know that there is no SCEV for the specified value.
2414 /// Analyze the expression.
2415 ///
2416 const SCEV* ScalarEvolution::createSCEV(Value *V) {
2417   if (!isSCEVable(V->getType()))
2418     return getUnknown(V);
2419
2420   unsigned Opcode = Instruction::UserOp1;
2421   if (Instruction *I = dyn_cast<Instruction>(V))
2422     Opcode = I->getOpcode();
2423   else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
2424     Opcode = CE->getOpcode();
2425   else
2426     return getUnknown(V);
2427
2428   User *U = cast<User>(V);
2429   switch (Opcode) {
2430   case Instruction::Add:
2431     return getAddExpr(getSCEV(U->getOperand(0)),
2432                       getSCEV(U->getOperand(1)));
2433   case Instruction::Mul:
2434     return getMulExpr(getSCEV(U->getOperand(0)),
2435                       getSCEV(U->getOperand(1)));
2436   case Instruction::UDiv:
2437     return getUDivExpr(getSCEV(U->getOperand(0)),
2438                        getSCEV(U->getOperand(1)));
2439   case Instruction::Sub:
2440     return getMinusSCEV(getSCEV(U->getOperand(0)),
2441                         getSCEV(U->getOperand(1)));
2442   case Instruction::And:
2443     // For an expression like x&255 that merely masks off the high bits,
2444     // use zext(trunc(x)) as the SCEV expression.
2445     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
2446       if (CI->isNullValue())
2447         return getSCEV(U->getOperand(1));
2448       if (CI->isAllOnesValue())
2449         return getSCEV(U->getOperand(0));
2450       const APInt &A = CI->getValue();
2451
2452       // Instcombine's ShrinkDemandedConstant may strip bits out of
2453       // constants, obscuring what would otherwise be a low-bits mask.
2454       // Use ComputeMaskedBits to compute what ShrinkDemandedConstant
2455       // knew about to reconstruct a low-bits mask value.
2456       unsigned LZ = A.countLeadingZeros();
2457       unsigned BitWidth = A.getBitWidth();
2458       APInt AllOnes = APInt::getAllOnesValue(BitWidth);
2459       APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
2460       ComputeMaskedBits(U->getOperand(0), AllOnes, KnownZero, KnownOne, TD);
2461
2462       APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ);
2463
2464       if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
2465         return
2466           getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)),
2467                                             IntegerType::get(BitWidth - LZ)),
2468                             U->getType());
2469     }
2470     break;
2471
2472   case Instruction::Or:
2473     // If the RHS of the Or is a constant, we may have something like:
2474     // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
2475     // optimizations will transparently handle this case.
2476     //
2477     // In order for this transformation to be safe, the LHS must be of the
2478     // form X*(2^n) and the Or constant must be less than 2^n.
2479     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
2480       const SCEV* LHS = getSCEV(U->getOperand(0));
2481       const APInt &CIVal = CI->getValue();
2482       if (GetMinTrailingZeros(LHS) >=
2483           (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
2484         return getAddExpr(LHS, getSCEV(U->getOperand(1)));
2485     }
2486     break;
2487   case Instruction::Xor:
2488     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
2489       // If the RHS of the xor is a signbit, then this is just an add.
2490       // Instcombine turns add of signbit into xor as a strength reduction step.
2491       if (CI->getValue().isSignBit())
2492         return getAddExpr(getSCEV(U->getOperand(0)),
2493                           getSCEV(U->getOperand(1)));
2494
2495       // If the RHS of xor is -1, then this is a not operation.
2496       if (CI->isAllOnesValue())
2497         return getNotSCEV(getSCEV(U->getOperand(0)));
2498
2499       // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
2500       // This is a variant of the check for xor with -1, and it handles
2501       // the case where instcombine has trimmed non-demanded bits out
2502       // of an xor with -1.
2503       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U->getOperand(0)))
2504         if (ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1)))
2505           if (BO->getOpcode() == Instruction::And &&
2506               LCI->getValue() == CI->getValue())
2507             if (const SCEVZeroExtendExpr *Z =
2508                   dyn_cast<SCEVZeroExtendExpr>(getSCEV(U->getOperand(0)))) {
2509               const Type *UTy = U->getType();
2510               const SCEV* Z0 = Z->getOperand();
2511               const Type *Z0Ty = Z0->getType();
2512               unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
2513
2514               // If C is a low-bits mask, the zero extend is zerving to
2515               // mask off the high bits. Complement the operand and
2516               // re-apply the zext.
2517               if (APIntOps::isMask(Z0TySize, CI->getValue()))
2518                 return getZeroExtendExpr(getNotSCEV(Z0), UTy);
2519
2520               // If C is a single bit, it may be in the sign-bit position
2521               // before the zero-extend. In this case, represent the xor
2522               // using an add, which is equivalent, and re-apply the zext.
2523               APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize);
2524               if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
2525                   Trunc.isSignBit())
2526                 return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)),
2527                                          UTy);
2528             }
2529     }
2530     break;
2531
2532   case Instruction::Shl:
2533     // Turn shift left of a constant amount into a multiply.
2534     if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
2535       uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2536       Constant *X = ConstantInt::get(
2537         APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
2538       return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
2539     }
2540     break;
2541
2542   case Instruction::LShr:
2543     // Turn logical shift right of a constant into a unsigned divide.
2544     if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
2545       uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
2546       Constant *X = ConstantInt::get(
2547         APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
2548       return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
2549     }
2550     break;
2551
2552   case Instruction::AShr:
2553     // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression.
2554     if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1)))
2555       if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0)))
2556         if (L->getOpcode() == Instruction::Shl &&
2557             L->getOperand(1) == U->getOperand(1)) {
2558           unsigned BitWidth = getTypeSizeInBits(U->getType());
2559           uint64_t Amt = BitWidth - CI->getZExtValue();
2560           if (Amt == BitWidth)
2561             return getSCEV(L->getOperand(0));       // shift by zero --> noop
2562           if (Amt > BitWidth)
2563             return getIntegerSCEV(0, U->getType()); // value is undefined
2564           return
2565             getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)),
2566                                                       IntegerType::get(Amt)),
2567                                  U->getType());
2568         }
2569     break;
2570
2571   case Instruction::Trunc:
2572     return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
2573
2574   case Instruction::ZExt:
2575     return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
2576
2577   case Instruction::SExt:
2578     return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
2579
2580   case Instruction::BitCast:
2581     // BitCasts are no-op casts so we just eliminate the cast.
2582     if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType()))
2583       return getSCEV(U->getOperand(0));
2584     break;
2585
2586   case Instruction::IntToPtr:
2587     if (!TD) break; // Without TD we can't analyze pointers.
2588     return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
2589                                    TD->getIntPtrType());
2590
2591   case Instruction::PtrToInt:
2592     if (!TD) break; // Without TD we can't analyze pointers.
2593     return getTruncateOrZeroExtend(getSCEV(U->getOperand(0)),
2594                                    U->getType());
2595
2596   case Instruction::GetElementPtr:
2597     if (!TD) break; // Without TD we can't analyze pointers.
2598     return createNodeForGEP(U);
2599
2600   case Instruction::PHI:
2601     return createNodeForPHI(cast<PHINode>(U));
2602
2603   case Instruction::Select:
2604     // This could be a smax or umax that was lowered earlier.
2605     // Try to recover it.
2606     if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
2607       Value *LHS = ICI->getOperand(0);
2608       Value *RHS = ICI->getOperand(1);
2609       switch (ICI->getPredicate()) {
2610       case ICmpInst::ICMP_SLT:
2611       case ICmpInst::ICMP_SLE:
2612         std::swap(LHS, RHS);
2613         // fall through
2614       case ICmpInst::ICMP_SGT:
2615       case ICmpInst::ICMP_SGE:
2616         if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
2617           return getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
2618         else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
2619           return getSMinExpr(getSCEV(LHS), getSCEV(RHS));
2620         break;
2621       case ICmpInst::ICMP_ULT:
2622       case ICmpInst::ICMP_ULE:
2623         std::swap(LHS, RHS);
2624         // fall through
2625       case ICmpInst::ICMP_UGT:
2626       case ICmpInst::ICMP_UGE:
2627         if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
2628           return getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
2629         else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
2630           return getUMinExpr(getSCEV(LHS), getSCEV(RHS));
2631         break;
2632       case ICmpInst::ICMP_NE:
2633         // n != 0 ? n : 1  ->  umax(n, 1)
2634         if (LHS == U->getOperand(1) &&
2635             isa<ConstantInt>(U->getOperand(2)) &&
2636             cast<ConstantInt>(U->getOperand(2))->isOne() &&
2637             isa<ConstantInt>(RHS) &&
2638             cast<ConstantInt>(RHS)->isZero())
2639           return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(2)));
2640         break;
2641       case ICmpInst::ICMP_EQ:
2642         // n == 0 ? 1 : n  ->  umax(n, 1)
2643         if (LHS == U->getOperand(2) &&
2644             isa<ConstantInt>(U->getOperand(1)) &&
2645             cast<ConstantInt>(U->getOperand(1))->isOne() &&
2646             isa<ConstantInt>(RHS) &&
2647             cast<ConstantInt>(RHS)->isZero())
2648           return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(1)));
2649         break;
2650       default:
2651         break;
2652       }
2653     }
2654
2655   default: // We cannot analyze this expression.
2656     break;
2657   }
2658
2659   return getUnknown(V);
2660 }
2661
2662
2663
2664 //===----------------------------------------------------------------------===//
2665 //                   Iteration Count Computation Code
2666 //
2667
2668 /// getBackedgeTakenCount - If the specified loop has a predictable
2669 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute
2670 /// object. The backedge-taken count is the number of times the loop header
2671 /// will be branched to from within the loop. This is one less than the
2672 /// trip count of the loop, since it doesn't count the first iteration,
2673 /// when the header is branched to from outside the loop.
2674 ///
2675 /// Note that it is not valid to call this method on a loop without a
2676 /// loop-invariant backedge-taken count (see
2677 /// hasLoopInvariantBackedgeTakenCount).
2678 ///
2679 const SCEV* ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
2680   return getBackedgeTakenInfo(L).Exact;
2681 }
2682
2683 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
2684 /// return the least SCEV value that is known never to be less than the
2685 /// actual backedge taken count.
2686 const SCEV* ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
2687   return getBackedgeTakenInfo(L).Max;
2688 }
2689
2690 const ScalarEvolution::BackedgeTakenInfo &
2691 ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
2692   // Initially insert a CouldNotCompute for this loop. If the insertion
2693   // succeeds, procede to actually compute a backedge-taken count and
2694   // update the value. The temporary CouldNotCompute value tells SCEV
2695   // code elsewhere that it shouldn't attempt to request a new
2696   // backedge-taken count, which could result in infinite recursion.
2697   std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2698     BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2699   if (Pair.second) {
2700     BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
2701     if (ItCount.Exact != CouldNotCompute) {
2702       assert(ItCount.Exact->isLoopInvariant(L) &&
2703              ItCount.Max->isLoopInvariant(L) &&
2704              "Computed trip count isn't loop invariant for loop!");
2705       ++NumTripCountsComputed;
2706
2707       // Update the value in the map.
2708       Pair.first->second = ItCount;
2709     } else {
2710       if (ItCount.Max != CouldNotCompute)
2711         // Update the value in the map.
2712         Pair.first->second = ItCount;
2713       if (isa<PHINode>(L->getHeader()->begin()))
2714         // Only count loops that have phi nodes as not being computable.
2715         ++NumTripCountsNotComputed;
2716     }
2717
2718     // Now that we know more about the trip count for this loop, forget any
2719     // existing SCEV values for PHI nodes in this loop since they are only
2720     // conservative estimates made without the benefit
2721     // of trip count information.
2722     if (ItCount.hasAnyInfo())
2723       forgetLoopPHIs(L);
2724   }
2725   return Pair.first->second;
2726 }
2727
2728 /// forgetLoopBackedgeTakenCount - This method should be called by the
2729 /// client when it has changed a loop in a way that may effect
2730 /// ScalarEvolution's ability to compute a trip count, or if the loop
2731 /// is deleted.
2732 void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) {
2733   BackedgeTakenCounts.erase(L);
2734   forgetLoopPHIs(L);
2735 }
2736
2737 /// forgetLoopPHIs - Delete the memoized SCEVs associated with the
2738 /// PHI nodes in the given loop. This is used when the trip count of
2739 /// the loop may have changed.
2740 void ScalarEvolution::forgetLoopPHIs(const Loop *L) {
2741   BasicBlock *Header = L->getHeader();
2742
2743   // Push all Loop-header PHIs onto the Worklist stack, except those
2744   // that are presently represented via a SCEVUnknown. SCEVUnknown for
2745   // a PHI either means that it has an unrecognized structure, or it's
2746   // a PHI that's in the progress of being computed by createNodeForPHI.
2747   // In the former case, additional loop trip count information isn't
2748   // going to change anything. In the later case, createNodeForPHI will
2749   // perform the necessary updates on its own when it gets to that point.
2750   SmallVector<Instruction *, 16> Worklist;
2751   for (BasicBlock::iterator I = Header->begin();
2752        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
2753     std::map<SCEVCallbackVH, const SCEV*>::iterator It = Scalars.find((Value*)I);
2754     if (It != Scalars.end() && !isa<SCEVUnknown>(It->second))
2755       Worklist.push_back(PN);
2756   }
2757
2758   while (!Worklist.empty()) {
2759     Instruction *I = Worklist.pop_back_val();
2760     if (Scalars.erase(I))
2761       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
2762            UI != UE; ++UI)
2763         Worklist.push_back(cast<Instruction>(UI));
2764   }
2765 }
2766
2767 /// ComputeBackedgeTakenCount - Compute the number of times the backedge
2768 /// of the specified loop will execute.
2769 ScalarEvolution::BackedgeTakenInfo
2770 ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2771   SmallVector<BasicBlock*, 8> ExitingBlocks;
2772   L->getExitingBlocks(ExitingBlocks);
2773
2774   // Examine all exits and pick the most conservative values.
2775   const SCEV* BECount = CouldNotCompute;
2776   const SCEV* MaxBECount = CouldNotCompute;
2777   bool CouldNotComputeBECount = false;
2778   bool CouldNotComputeMaxBECount = false;
2779   for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2780     BackedgeTakenInfo NewBTI =
2781       ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
2782
2783     if (NewBTI.Exact == CouldNotCompute) {
2784       // We couldn't compute an exact value for this exit, so
2785       // we won't be able to compute an exact value for the loop.
2786       CouldNotComputeBECount = true;
2787       BECount = CouldNotCompute;
2788     } else if (!CouldNotComputeBECount) {
2789       if (BECount == CouldNotCompute)
2790         BECount = NewBTI.Exact;
2791       else {
2792         // TODO: More analysis could be done here. For example, a
2793         // loop with a short-circuiting && operator has an exact count
2794         // of the min of both sides.
2795         CouldNotComputeBECount = true;
2796         BECount = CouldNotCompute;
2797       }
2798     }
2799     if (NewBTI.Max == CouldNotCompute) {
2800       // We couldn't compute an maximum value for this exit, so
2801       // we won't be able to compute an maximum value for the loop.
2802       CouldNotComputeMaxBECount = true;
2803       MaxBECount = CouldNotCompute;
2804     } else if (!CouldNotComputeMaxBECount) {
2805       if (MaxBECount == CouldNotCompute)
2806         MaxBECount = NewBTI.Max;
2807       else
2808         MaxBECount = getUMaxFromMismatchedTypes(MaxBECount, NewBTI.Max);
2809     }
2810   }
2811
2812   return BackedgeTakenInfo(BECount, MaxBECount);
2813 }
2814
2815 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
2816 /// of the specified loop will execute if it exits via the specified block.
2817 ScalarEvolution::BackedgeTakenInfo
2818 ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
2819                                                    BasicBlock *ExitingBlock) {
2820
2821   // Okay, we've chosen an exiting block.  See what condition causes us to
2822   // exit at this block.
2823   //
2824   // FIXME: we should be able to handle switch instructions (with a single exit)
2825   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2826   if (ExitBr == 0) return CouldNotCompute;
2827   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2828
2829   // At this point, we know we have a conditional branch that determines whether
2830   // the loop is exited.  However, we don't know if the branch is executed each
2831   // time through the loop.  If not, then the execution count of the branch will
2832   // not be equal to the trip count of the loop.
2833   //
2834   // Currently we check for this by checking to see if the Exit branch goes to
2835   // the loop header.  If so, we know it will always execute the same number of
2836   // times as the loop.  We also handle the case where the exit block *is* the
2837   // loop header.  This is common for un-rotated loops.
2838   //
2839   // If both of those tests fail, walk up the unique predecessor chain to the
2840   // header, stopping if there is an edge that doesn't exit the loop. If the
2841   // header is reached, the execution count of the branch will be equal to the
2842   // trip count of the loop.
2843   //
2844   //  More extensive analysis could be done to handle more cases here.
2845   //
2846   if (ExitBr->getSuccessor(0) != L->getHeader() &&
2847       ExitBr->getSuccessor(1) != L->getHeader() &&
2848       ExitBr->getParent() != L->getHeader()) {
2849     // The simple checks failed, try climbing the unique predecessor chain
2850     // up to the header.
2851     bool Ok = false;
2852     for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
2853       BasicBlock *Pred = BB->getUniquePredecessor();
2854       if (!Pred)
2855         return CouldNotCompute;
2856       TerminatorInst *PredTerm = Pred->getTerminator();
2857       for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
2858         BasicBlock *PredSucc = PredTerm->getSuccessor(i);
2859         if (PredSucc == BB)
2860           continue;
2861         // If the predecessor has a successor that isn't BB and isn't
2862         // outside the loop, assume the worst.
2863         if (L->contains(PredSucc))
2864           return CouldNotCompute;
2865       }
2866       if (Pred == L->getHeader()) {
2867         Ok = true;
2868         break;
2869       }
2870       BB = Pred;
2871     }
2872     if (!Ok)
2873       return CouldNotCompute;
2874   }
2875
2876   // Procede to the next level to examine the exit condition expression.
2877   return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
2878                                                ExitBr->getSuccessor(0),
2879                                                ExitBr->getSuccessor(1));
2880 }
2881
2882 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
2883 /// backedge of the specified loop will execute if its exit condition
2884 /// were a conditional branch of ExitCond, TBB, and FBB.
2885 ScalarEvolution::BackedgeTakenInfo
2886 ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
2887                                                        Value *ExitCond,
2888                                                        BasicBlock *TBB,
2889                                                        BasicBlock *FBB) {
2890   // Check if the controlling expression for this loop is an and or or. In
2891   // such cases, an exact backedge-taken count may be infeasible, but a
2892   // maximum count may still be feasible.
2893   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
2894     if (BO->getOpcode() == Instruction::And) {
2895       // Recurse on the operands of the and.
2896       BackedgeTakenInfo BTI0 =
2897         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
2898       BackedgeTakenInfo BTI1 =
2899         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
2900       const SCEV* BECount = CouldNotCompute;
2901       const SCEV* MaxBECount = CouldNotCompute;
2902       if (L->contains(TBB)) {
2903         // Both conditions must be true for the loop to continue executing.
2904         // Choose the less conservative count.
2905         if (BTI0.Exact == CouldNotCompute)
2906           BECount = BTI1.Exact;
2907         else if (BTI1.Exact == CouldNotCompute)
2908           BECount = BTI0.Exact;
2909         else
2910           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2911         if (BTI0.Max == CouldNotCompute)
2912           MaxBECount = BTI1.Max;
2913         else if (BTI1.Max == CouldNotCompute)
2914           MaxBECount = BTI0.Max;
2915         else
2916           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
2917       } else {
2918         // Both conditions must be true for the loop to exit.
2919         assert(L->contains(FBB) && "Loop block has no successor in loop!");
2920         if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
2921           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2922         if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
2923           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
2924       }
2925
2926       return BackedgeTakenInfo(BECount, MaxBECount);
2927     }
2928     if (BO->getOpcode() == Instruction::Or) {
2929       // Recurse on the operands of the or.
2930       BackedgeTakenInfo BTI0 =
2931         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
2932       BackedgeTakenInfo BTI1 =
2933         ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
2934       const SCEV* BECount = CouldNotCompute;
2935       const SCEV* MaxBECount = CouldNotCompute;
2936       if (L->contains(FBB)) {
2937         // Both conditions must be false for the loop to continue executing.
2938         // Choose the less conservative count.
2939         if (BTI0.Exact == CouldNotCompute)
2940           BECount = BTI1.Exact;
2941         else if (BTI1.Exact == CouldNotCompute)
2942           BECount = BTI0.Exact;
2943         else
2944           BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2945         if (BTI0.Max == CouldNotCompute)
2946           MaxBECount = BTI1.Max;
2947         else if (BTI1.Max == CouldNotCompute)
2948           MaxBECount = BTI0.Max;
2949         else
2950           MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
2951       } else {
2952         // Both conditions must be false for the loop to exit.
2953         assert(L->contains(TBB) && "Loop block has no successor in loop!");
2954         if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
2955           BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2956         if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
2957           MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
2958       }
2959
2960       return BackedgeTakenInfo(BECount, MaxBECount);
2961     }
2962   }
2963
2964   // With an icmp, it may be feasible to compute an exact backedge-taken count.
2965   // Procede to the next level to examine the icmp.
2966   if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
2967     return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB);
2968
2969   // If it's not an integer or pointer comparison then compute it the hard way.
2970   return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
2971 }
2972
2973 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the
2974 /// backedge of the specified loop will execute if its exit condition
2975 /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
2976 ScalarEvolution::BackedgeTakenInfo
2977 ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
2978                                                            ICmpInst *ExitCond,
2979                                                            BasicBlock *TBB,
2980                                                            BasicBlock *FBB) {
2981
2982   // If the condition was exit on true, convert the condition to exit on false
2983   ICmpInst::Predicate Cond;
2984   if (!L->contains(FBB))
2985     Cond = ExitCond->getPredicate();
2986   else
2987     Cond = ExitCond->getInversePredicate();
2988
2989   // Handle common loops like: for (X = "string"; *X; ++X)
2990   if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
2991     if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
2992       const SCEV* ItCnt =
2993         ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond);
2994       if (!isa<SCEVCouldNotCompute>(ItCnt)) {
2995         unsigned BitWidth = getTypeSizeInBits(ItCnt->getType());
2996         return BackedgeTakenInfo(ItCnt,
2997                                  isa<SCEVConstant>(ItCnt) ? ItCnt :
2998                                    getConstant(APInt::getMaxValue(BitWidth)-1));
2999       }
3000     }
3001
3002   const SCEV* LHS = getSCEV(ExitCond->getOperand(0));
3003   const SCEV* RHS = getSCEV(ExitCond->getOperand(1));
3004
3005   // Try to evaluate any dependencies out of the loop.
3006   LHS = getSCEVAtScope(LHS, L);
3007   RHS = getSCEVAtScope(RHS, L);
3008
3009   // At this point, we would like to compute how many iterations of the
3010   // loop the predicate will return true for these inputs.
3011   if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
3012     // If there is a loop-invariant, force it into the RHS.
3013     std::swap(LHS, RHS);
3014     Cond = ICmpInst::getSwappedPredicate(Cond);
3015   }
3016
3017   // If we have a comparison of a chrec against a constant, try to use value
3018   // ranges to answer this query.
3019   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
3020     if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
3021       if (AddRec->getLoop() == L) {
3022         // Form the constant range.
3023         ConstantRange CompRange(
3024             ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
3025
3026         const SCEV* Ret = AddRec->getNumIterationsInRange(CompRange, *this);
3027         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
3028       }
3029
3030   switch (Cond) {
3031   case ICmpInst::ICMP_NE: {                     // while (X != Y)
3032     // Convert to: while (X-Y != 0)
3033     const SCEV* TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
3034     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
3035     break;
3036   }
3037   case ICmpInst::ICMP_EQ: {
3038     // Convert to: while (X-Y == 0)           // while (X == Y)
3039     const SCEV* TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
3040     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
3041     break;
3042   }
3043   case ICmpInst::ICMP_SLT: {
3044     BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, true);
3045     if (BTI.hasAnyInfo()) return BTI;
3046     break;
3047   }
3048   case ICmpInst::ICMP_SGT: {
3049     BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
3050                                              getNotSCEV(RHS), L, true);
3051     if (BTI.hasAnyInfo()) return BTI;
3052     break;
3053   }
3054   case ICmpInst::ICMP_ULT: {
3055     BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, false);
3056     if (BTI.hasAnyInfo()) return BTI;
3057     break;
3058   }
3059   case ICmpInst::ICMP_UGT: {
3060     BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS),
3061                                              getNotSCEV(RHS), L, false);
3062     if (BTI.hasAnyInfo()) return BTI;
3063     break;
3064   }
3065   default:
3066 #if 0
3067     errs() << "ComputeBackedgeTakenCount ";
3068     if (ExitCond->getOperand(0)->getType()->isUnsigned())
3069       errs() << "[unsigned] ";
3070     errs() << *LHS << "   "
3071          << Instruction::getOpcodeName(Instruction::ICmp)
3072          << "   " << *RHS << "\n";
3073 #endif
3074     break;
3075   }
3076   return
3077     ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
3078 }
3079
3080 static ConstantInt *
3081 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
3082                                 ScalarEvolution &SE) {
3083   const SCEV* InVal = SE.getConstant(C);
3084   const SCEV* Val = AddRec->evaluateAtIteration(InVal, SE);
3085   assert(isa<SCEVConstant>(Val) &&
3086          "Evaluation of SCEV at constant didn't fold correctly?");
3087   return cast<SCEVConstant>(Val)->getValue();
3088 }
3089
3090 /// GetAddressedElementFromGlobal - Given a global variable with an initializer
3091 /// and a GEP expression (missing the pointer index) indexing into it, return
3092 /// the addressed element of the initializer or null if the index expression is
3093 /// invalid.
3094 static Constant *
3095 GetAddressedElementFromGlobal(GlobalVariable *GV,
3096                               const std::vector<ConstantInt*> &Indices) {
3097   Constant *Init = GV->getInitializer();
3098   for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
3099     uint64_t Idx = Indices[i]->getZExtValue();
3100     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
3101       assert(Idx < CS->getNumOperands() && "Bad struct index!");
3102       Init = cast<Constant>(CS->getOperand(Idx));
3103     } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
3104       if (Idx >= CA->getNumOperands()) return 0;  // Bogus program
3105       Init = cast<Constant>(CA->getOperand(Idx));
3106     } else if (isa<ConstantAggregateZero>(Init)) {
3107       if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
3108         assert(Idx < STy->getNumElements() && "Bad struct index!");
3109         Init = Constant::getNullValue(STy->getElementType(Idx));
3110       } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
3111         if (Idx >= ATy->getNumElements()) return 0;  // Bogus program
3112         Init = Constant::getNullValue(ATy->getElementType());
3113       } else {
3114         assert(0 && "Unknown constant aggregate type!");
3115       }
3116       return 0;
3117     } else {
3118       return 0; // Unknown initializer type
3119     }
3120   }
3121   return Init;
3122 }
3123
3124 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of
3125 /// 'icmp op load X, cst', try to see if we can compute the backedge
3126 /// execution count.
3127 const SCEV* ScalarEvolution::
3128 ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS,
3129                                              const Loop *L,
3130                                              ICmpInst::Predicate predicate) {
3131   if (LI->isVolatile()) return CouldNotCompute;
3132
3133   // Check to see if the loaded pointer is a getelementptr of a global.
3134   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3135   if (!GEP) return CouldNotCompute;
3136
3137   // Make sure that it is really a constant global we are gepping, with an
3138   // initializer, and make sure the first IDX is really 0.
3139   GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
3140   if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
3141       GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
3142       !cast<Constant>(GEP->getOperand(1))->isNullValue())
3143     return CouldNotCompute;
3144
3145   // Okay, we allow one non-constant index into the GEP instruction.
3146   Value *VarIdx = 0;
3147   std::vector<ConstantInt*> Indexes;
3148   unsigned VarIdxNum = 0;
3149   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
3150     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
3151       Indexes.push_back(CI);
3152     } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
3153       if (VarIdx) return CouldNotCompute;  // Multiple non-constant idx's.
3154       VarIdx = GEP->getOperand(i);
3155       VarIdxNum = i-2;
3156       Indexes.push_back(0);
3157     }
3158
3159   // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
3160   // Check to see if X is a loop variant variable value now.
3161   const SCEV* Idx = getSCEV(VarIdx);
3162   Idx = getSCEVAtScope(Idx, L);
3163
3164   // We can only recognize very limited forms of loop index expressions, in
3165   // particular, only affine AddRec's like {C1,+,C2}.
3166   const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
3167   if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
3168       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
3169       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
3170     return CouldNotCompute;
3171
3172   unsigned MaxSteps = MaxBruteForceIterations;
3173   for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
3174     ConstantInt *ItCst =
3175       ConstantInt::get(cast<IntegerType>(IdxExpr->getType()), IterationNum);
3176     ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
3177
3178     // Form the GEP offset.
3179     Indexes[VarIdxNum] = Val;
3180
3181     Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
3182     if (Result == 0) break;  // Cannot compute!
3183
3184     // Evaluate the condition for this iteration.
3185     Result = ConstantExpr::getICmp(predicate, Result, RHS);
3186     if (!isa<ConstantInt>(Result)) break;  // Couldn't decide for sure
3187     if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
3188 #if 0
3189       errs() << "\n***\n*** Computed loop count " << *ItCst
3190              << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
3191              << "***\n";
3192 #endif
3193       ++NumArrayLenItCounts;
3194       return getConstant(ItCst);   // Found terminating iteration!
3195     }
3196   }
3197   return CouldNotCompute;
3198 }
3199
3200
3201 /// CanConstantFold - Return true if we can constant fold an instruction of the
3202 /// specified type, assuming that all operands were constants.
3203 static bool CanConstantFold(const Instruction *I) {
3204   if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
3205       isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
3206     return true;
3207
3208   if (const CallInst *CI = dyn_cast<CallInst>(I))
3209     if (const Function *F = CI->getCalledFunction())
3210       return canConstantFoldCallTo(F);
3211   return false;
3212 }
3213
3214 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
3215 /// in the loop that V is derived from.  We allow arbitrary operations along the
3216 /// way, but the operands of an operation must either be constants or a value
3217 /// derived from a constant PHI.  If this expression does not fit with these
3218 /// constraints, return null.
3219 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
3220   // If this is not an instruction, or if this is an instruction outside of the
3221   // loop, it can't be derived from a loop PHI.
3222   Instruction *I = dyn_cast<Instruction>(V);
3223   if (I == 0 || !L->contains(I->getParent())) return 0;
3224
3225   if (PHINode *PN = dyn_cast<PHINode>(I)) {
3226     if (L->getHeader() == I->getParent())
3227       return PN;
3228     else
3229       // We don't currently keep track of the control flow needed to evaluate
3230       // PHIs, so we cannot handle PHIs inside of loops.
3231       return 0;
3232   }
3233
3234   // If we won't be able to constant fold this expression even if the operands
3235   // are constants, return early.
3236   if (!CanConstantFold(I)) return 0;
3237
3238   // Otherwise, we can evaluate this instruction if all of its operands are
3239   // constant or derived from a PHI node themselves.
3240   PHINode *PHI = 0;
3241   for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
3242     if (!(isa<Constant>(I->getOperand(Op)) ||
3243           isa<GlobalValue>(I->getOperand(Op)))) {
3244       PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
3245       if (P == 0) return 0;  // Not evolving from PHI
3246       if (PHI == 0)
3247         PHI = P;
3248       else if (PHI != P)
3249         return 0;  // Evolving from multiple different PHIs.
3250     }
3251
3252   // This is a expression evolving from a constant PHI!
3253   return PHI;
3254 }
3255
3256 /// EvaluateExpression - Given an expression that passes the
3257 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
3258 /// in the loop has the value PHIVal.  If we can't fold this expression for some
3259 /// reason, return null.
3260 static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
3261   if (isa<PHINode>(V)) return PHIVal;
3262   if (Constant *C = dyn_cast<Constant>(V)) return C;
3263   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV;
3264   Instruction *I = cast<Instruction>(V);
3265
3266   std::vector<Constant*> Operands;
3267   Operands.resize(I->getNumOperands());
3268
3269   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3270     Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
3271     if (Operands[i] == 0) return 0;
3272   }
3273
3274   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
3275     return ConstantFoldCompareInstOperands(CI->getPredicate(),
3276                                            &Operands[0], Operands.size());
3277   else
3278     return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
3279                                     &Operands[0], Operands.size());
3280 }
3281
3282 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
3283 /// in the header of its containing loop, we know the loop executes a
3284 /// constant number of times, and the PHI node is just a recurrence
3285 /// involving constants, fold it.
3286 Constant *ScalarEvolution::
3287 getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L){
3288   std::map<PHINode*, Constant*>::iterator I =
3289     ConstantEvolutionLoopExitValue.find(PN);
3290   if (I != ConstantEvolutionLoopExitValue.end())
3291     return I->second;
3292
3293   if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations)))
3294     return ConstantEvolutionLoopExitValue[PN] = 0;  // Not going to evaluate it.
3295
3296   Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
3297
3298   // Since the loop is canonicalized, the PHI node must have two entries.  One
3299   // entry must be a constant (coming in from outside of the loop), and the
3300   // second must be derived from the same PHI.
3301   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
3302   Constant *StartCST =
3303     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
3304   if (StartCST == 0)
3305     return RetVal = 0;  // Must be a constant.
3306
3307   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3308   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3309   if (PN2 != PN)
3310     return RetVal = 0;  // Not derived from same PHI.
3311
3312   // Execute the loop symbolically to determine the exit value.
3313   if (BEs.getActiveBits() >= 32)
3314     return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
3315
3316   unsigned NumIterations = BEs.getZExtValue(); // must be in range
3317   unsigned IterationNum = 0;
3318   for (Constant *PHIVal = StartCST; ; ++IterationNum) {
3319     if (IterationNum == NumIterations)
3320       return RetVal = PHIVal;  // Got exit value!
3321
3322     // Compute the value of the PHI node for the next iteration.
3323     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
3324     if (NextPHI == PHIVal)
3325       return RetVal = NextPHI;  // Stopped evolving!
3326     if (NextPHI == 0)
3327       return 0;        // Couldn't evaluate!
3328     PHIVal = NextPHI;
3329   }
3330 }
3331
3332 /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
3333 /// constant number of times (the condition evolves only from constants),
3334 /// try to evaluate a few iterations of the loop until we get the exit
3335 /// condition gets a value of ExitWhen (true or false).  If we cannot
3336 /// evaluate the trip count of the loop, return CouldNotCompute.
3337 const SCEV* ScalarEvolution::
3338 ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
3339   PHINode *PN = getConstantEvolvingPHI(Cond, L);
3340   if (PN == 0) return CouldNotCompute;
3341
3342   // Since the loop is canonicalized, the PHI node must have two entries.  One
3343   // entry must be a constant (coming in from outside of the loop), and the
3344   // second must be derived from the same PHI.
3345   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
3346   Constant *StartCST =
3347     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
3348   if (StartCST == 0) return CouldNotCompute;  // Must be a constant.
3349
3350   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3351   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3352   if (PN2 != PN) return CouldNotCompute;  // Not derived from same PHI.
3353
3354   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
3355   // the loop symbolically to determine when the condition gets a value of
3356   // "ExitWhen".
3357   unsigned IterationNum = 0;
3358   unsigned MaxIterations = MaxBruteForceIterations;   // Limit analysis.
3359   for (Constant *PHIVal = StartCST;
3360        IterationNum != MaxIterations; ++IterationNum) {
3361     ConstantInt *CondVal =
3362       dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
3363
3364     // Couldn't symbolically evaluate.
3365     if (!CondVal) return CouldNotCompute;
3366
3367     if (CondVal->getValue() == uint64_t(ExitWhen)) {
3368       ConstantEvolutionLoopExitValue[PN] = PHIVal;
3369       ++NumBruteForceTripCountsComputed;
3370       return getConstant(Type::Int32Ty, IterationNum);
3371     }
3372
3373     // Compute the value of the PHI node for the next iteration.
3374     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
3375     if (NextPHI == 0 || NextPHI == PHIVal)
3376       return CouldNotCompute;   // Couldn't evaluate or not making progress...
3377     PHIVal = NextPHI;
3378   }
3379
3380   // Too many iterations were needed to evaluate.
3381   return CouldNotCompute;
3382 }
3383
3384 /// getSCEVAtScope - Return a SCEV expression handle for the specified value
3385 /// at the specified scope in the program.  The L value specifies a loop
3386 /// nest to evaluate the expression at, where null is the top-level or a
3387 /// specified loop is immediately inside of the loop.
3388 ///
3389 /// This method can be used to compute the exit value for a variable defined
3390 /// in a loop by querying what the value will hold in the parent loop.
3391 ///
3392 /// In the case that a relevant loop exit value cannot be computed, the
3393 /// original value V is returned.
3394 const SCEV* ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
3395   // FIXME: this should be turned into a virtual method on SCEV!
3396
3397   if (isa<SCEVConstant>(V)) return V;
3398
3399   // If this instruction is evolved from a constant-evolving PHI, compute the
3400   // exit value from the loop without using SCEVs.
3401   if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
3402     if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
3403       const Loop *LI = (*this->LI)[I->getParent()];
3404       if (LI && LI->getParentLoop() == L)  // Looking for loop exit value.
3405         if (PHINode *PN = dyn_cast<PHINode>(I))
3406           if (PN->getParent() == LI->getHeader()) {
3407             // Okay, there is no closed form solution for the PHI node.  Check
3408             // to see if the loop that contains it has a known backedge-taken
3409             // count.  If so, we may be able to force computation of the exit
3410             // value.
3411             const SCEV* BackedgeTakenCount = getBackedgeTakenCount(LI);
3412             if (const SCEVConstant *BTCC =
3413                   dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
3414               // Okay, we know how many times the containing loop executes.  If
3415               // this is a constant evolving PHI node, get the final value at
3416               // the specified iteration number.
3417               Constant *RV = getConstantEvolutionLoopExitValue(PN,
3418                                                    BTCC->getValue()->getValue(),
3419                                                                LI);
3420               if (RV) return getUnknown(RV);
3421             }
3422           }
3423
3424       // Okay, this is an expression that we cannot symbolically evaluate
3425       // into a SCEV.  Check to see if it's possible to symbolically evaluate
3426       // the arguments into constants, and if so, try to constant propagate the
3427       // result.  This is particularly useful for computing loop exit values.
3428       if (CanConstantFold(I)) {
3429         // Check to see if we've folded this instruction at this loop before.
3430         std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
3431         std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
3432           Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
3433         if (!Pair.second)
3434           return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
3435
3436         std::vector<Constant*> Operands;
3437         Operands.reserve(I->getNumOperands());
3438         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3439           Value *Op = I->getOperand(i);
3440           if (Constant *C = dyn_cast<Constant>(Op)) {
3441             Operands.push_back(C);
3442           } else {
3443             // If any of the operands is non-constant and if they are
3444             // non-integer and non-pointer, don't even try to analyze them
3445             // with scev techniques.
3446             if (!isSCEVable(Op->getType()))
3447               return V;
3448
3449             const SCEV* OpV = getSCEVAtScope(getSCEV(Op), L);
3450             if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) {
3451               Constant *C = SC->getValue();
3452               if (C->getType() != Op->getType())
3453                 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
3454                                                                   Op->getType(),
3455                                                                   false),
3456                                           C, Op->getType());
3457               Operands.push_back(C);
3458             } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
3459               if (Constant *C = dyn_cast<Constant>(SU->getValue())) {
3460                 if (C->getType() != Op->getType())
3461                   C =
3462                     ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
3463                                                                   Op->getType(),
3464                                                                   false),
3465                                           C, Op->getType());
3466                 Operands.push_back(C);
3467               } else
3468                 return V;
3469             } else {
3470               return V;
3471             }
3472           }
3473         }
3474
3475         Constant *C;
3476         if (const CmpInst *CI = dyn_cast<CmpInst>(I))
3477           C = ConstantFoldCompareInstOperands(CI->getPredicate(),
3478                                               &Operands[0], Operands.size());
3479         else
3480           C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
3481                                        &Operands[0], Operands.size());
3482         Pair.first->second = C;
3483         return getUnknown(C);
3484       }
3485     }
3486
3487     // This is some other type of SCEVUnknown, just return it.
3488     return V;
3489   }
3490
3491   if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
3492     // Avoid performing the look-up in the common case where the specified
3493     // expression has no loop-variant portions.
3494     for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
3495       const SCEV* OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
3496       if (OpAtScope != Comm->getOperand(i)) {
3497         // Okay, at least one of these operands is loop variant but might be
3498         // foldable.  Build a new instance of the folded commutative expression.
3499         SmallVector<const SCEV*, 8> NewOps(Comm->op_begin(), Comm->op_begin()+i);
3500         NewOps.push_back(OpAtScope);
3501
3502         for (++i; i != e; ++i) {
3503           OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
3504           NewOps.push_back(OpAtScope);
3505         }
3506         if (isa<SCEVAddExpr>(Comm))
3507           return getAddExpr(NewOps);
3508         if (isa<SCEVMulExpr>(Comm))
3509           return getMulExpr(NewOps);
3510         if (isa<SCEVSMaxExpr>(Comm))
3511           return getSMaxExpr(NewOps);
3512         if (isa<SCEVUMaxExpr>(Comm))
3513           return getUMaxExpr(NewOps);
3514         assert(0 && "Unknown commutative SCEV type!");
3515       }
3516     }
3517     // If we got here, all operands are loop invariant.
3518     return Comm;
3519   }
3520
3521   if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
3522     const SCEV* LHS = getSCEVAtScope(Div->getLHS(), L);
3523     const SCEV* RHS = getSCEVAtScope(Div->getRHS(), L);
3524     if (LHS == Div->getLHS() && RHS == Div->getRHS())
3525       return Div;   // must be loop invariant
3526     return getUDivExpr(LHS, RHS);
3527   }
3528
3529   // If this is a loop recurrence for a loop that does not contain L, then we
3530   // are dealing with the final value computed by the loop.
3531   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3532     if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3533       // To evaluate this recurrence, we need to know how many times the AddRec
3534       // loop iterates.  Compute this now.
3535       const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
3536       if (BackedgeTakenCount == CouldNotCompute) return AddRec;
3537
3538       // Then, evaluate the AddRec.
3539       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3540     }
3541     return AddRec;
3542   }
3543
3544   if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
3545     const SCEV* Op = getSCEVAtScope(Cast->getOperand(), L);
3546     if (Op == Cast->getOperand())
3547       return Cast;  // must be loop invariant
3548     return getZeroExtendExpr(Op, Cast->getType());
3549   }
3550
3551   if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) {
3552     const SCEV* Op = getSCEVAtScope(Cast->getOperand(), L);
3553     if (Op == Cast->getOperand())
3554       return Cast;  // must be loop invariant
3555     return getSignExtendExpr(Op, Cast->getType());
3556   }
3557
3558   if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) {
3559     const SCEV* Op = getSCEVAtScope(Cast->getOperand(), L);
3560     if (Op == Cast->getOperand())
3561       return Cast;  // must be loop invariant
3562     return getTruncateExpr(Op, Cast->getType());
3563   }
3564
3565   assert(0 && "Unknown SCEV type!");
3566   return 0;
3567 }
3568
3569 /// getSCEVAtScope - This is a convenience function which does
3570 /// getSCEVAtScope(getSCEV(V), L).
3571 const SCEV* ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
3572   return getSCEVAtScope(getSCEV(V), L);
3573 }
3574
3575 /// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the
3576 /// following equation:
3577 ///
3578 ///     A * X = B (mod N)
3579 ///
3580 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of
3581 /// A and B isn't important.
3582 ///
3583 /// If the equation does not have a solution, SCEVCouldNotCompute is returned.
3584 static const SCEV* SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
3585                                                ScalarEvolution &SE) {
3586   uint32_t BW = A.getBitWidth();
3587   assert(BW == B.getBitWidth() && "Bit widths must be the same.");
3588   assert(A != 0 && "A must be non-zero.");
3589
3590   // 1. D = gcd(A, N)
3591   //
3592   // The gcd of A and N may have only one prime factor: 2. The number of
3593   // trailing zeros in A is its multiplicity
3594   uint32_t Mult2 = A.countTrailingZeros();
3595   // D = 2^Mult2
3596
3597   // 2. Check if B is divisible by D.
3598   //
3599   // B is divisible by D if and only if the multiplicity of prime factor 2 for B
3600   // is not less than multiplicity of this prime factor for D.
3601   if (B.countTrailingZeros() < Mult2)
3602     return SE.getCouldNotCompute();
3603
3604   // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
3605   // modulo (N / D).
3606   //
3607   // (N / D) may need BW+1 bits in its representation.  Hence, we'll use this
3608   // bit width during computations.
3609   APInt AD = A.lshr(Mult2).zext(BW + 1);  // AD = A / D
3610   APInt Mod(BW + 1, 0);
3611   Mod.set(BW - Mult2);  // Mod = N / D
3612   APInt I = AD.multiplicativeInverse(Mod);
3613
3614   // 4. Compute the minimum unsigned root of the equation:
3615   // I * (B / D) mod (N / D)
3616   APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod);
3617
3618   // The result is guaranteed to be less than 2^BW so we may truncate it to BW
3619   // bits.
3620   return SE.getConstant(Result.trunc(BW));
3621 }
3622
3623 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
3624 /// given quadratic chrec {L,+,M,+,N}.  This returns either the two roots (which
3625 /// might be the same) or two SCEVCouldNotCompute objects.
3626 ///
3627 static std::pair<const SCEV*,const SCEV*>
3628 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
3629   assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
3630   const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
3631   const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
3632   const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
3633
3634   // We currently can only solve this if the coefficients are constants.
3635   if (!LC || !MC || !NC) {
3636     const SCEV *CNC = SE.getCouldNotCompute();
3637     return std::make_pair(CNC, CNC);
3638   }
3639
3640   uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
3641   const APInt &L = LC->getValue()->getValue();
3642   const APInt &M = MC->getValue()->getValue();
3643   const APInt &N = NC->getValue()->getValue();
3644   APInt Two(BitWidth, 2);
3645   APInt Four(BitWidth, 4);
3646
3647   {
3648     using namespace APIntOps;
3649     const APInt& C = L;
3650     // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
3651     // The B coefficient is M-N/2
3652     APInt B(M);
3653     B -= sdiv(N,Two);
3654
3655     // The A coefficient is N/2
3656     APInt A(N.sdiv(Two));
3657
3658     // Compute the B^2-4ac term.
3659     APInt SqrtTerm(B);
3660     SqrtTerm *= B;
3661     SqrtTerm -= Four * (A * C);
3662
3663     // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
3664     // integer value or else APInt::sqrt() will assert.
3665     APInt SqrtVal(SqrtTerm.sqrt());
3666
3667     // Compute the two solutions for the quadratic formula.
3668     // The divisions must be performed as signed divisions.
3669     APInt NegB(-B);
3670     APInt TwoA( A << 1 );
3671     if (TwoA.isMinValue()) {
3672       const SCEV *CNC = SE.getCouldNotCompute();
3673       return std::make_pair(CNC, CNC);
3674     }
3675
3676     ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
3677     ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
3678
3679     return std::make_pair(SE.getConstant(Solution1),
3680                           SE.getConstant(Solution2));
3681     } // end APIntOps namespace
3682 }
3683
3684 /// HowFarToZero - Return the number of times a backedge comparing the specified
3685 /// value to zero will execute.  If not computable, return CouldNotCompute.
3686 const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3687   // If the value is a constant
3688   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3689     // If the value is already zero, the branch will execute zero times.
3690     if (C->getValue()->isZero()) return C;
3691     return CouldNotCompute;  // Otherwise it will loop infinitely.
3692   }
3693
3694   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3695   if (!AddRec || AddRec->getLoop() != L)
3696     return CouldNotCompute;
3697
3698   if (AddRec->isAffine()) {
3699     // If this is an affine expression, the execution count of this branch is
3700     // the minimum unsigned root of the following equation:
3701     //
3702     //     Start + Step*N = 0 (mod 2^BW)
3703     //
3704     // equivalent to:
3705     //
3706     //             Step*N = -Start (mod 2^BW)
3707     //
3708     // where BW is the common bit width of Start and Step.
3709
3710     // Get the initial value for the loop.
3711     const SCEV* Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
3712     const SCEV* Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
3713
3714     if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
3715       // For now we handle only constant steps.
3716
3717       // First, handle unitary steps.
3718       if (StepC->getValue()->equalsInt(1))      // 1*N = -Start (mod 2^BW), so:
3719         return getNegativeSCEV(Start);       //   N = -Start (as unsigned)
3720       if (StepC->getValue()->isAllOnesValue())  // -1*N = -Start (mod 2^BW), so:
3721         return Start;                           //    N = Start (as unsigned)
3722
3723       // Then, try to solve the above equation provided that Start is constant.
3724       if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
3725         return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
3726                                             -StartC->getValue()->getValue(),
3727                                             *this);
3728     }
3729   } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
3730     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
3731     // the quadratic equation to solve it.
3732     std::pair<const SCEV*,const SCEV*> Roots = SolveQuadraticEquation(AddRec,
3733                                                                     *this);
3734     const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
3735     const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
3736     if (R1) {
3737 #if 0
3738       errs() << "HFTZ: " << *V << " - sol#1: " << *R1
3739              << "  sol#2: " << *R2 << "\n";
3740 #endif
3741       // Pick the smallest positive root value.
3742       if (ConstantInt *CB =
3743           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
3744                                    R1->getValue(), R2->getValue()))) {
3745         if (CB->getZExtValue() == false)
3746           std::swap(R1, R2);   // R1 is the minimum root now.
3747
3748         // We can only use this value if the chrec ends up with an exact zero
3749         // value at this index.  When solving for "X*X != 5", for example, we
3750         // should not accept a root of 2.
3751         const SCEV* Val = AddRec->evaluateAtIteration(R1, *this);
3752         if (Val->isZero())
3753           return R1;  // We found a quadratic root!
3754       }
3755     }
3756   }
3757
3758   return CouldNotCompute;
3759 }
3760
3761 /// HowFarToNonZero - Return the number of times a backedge checking the
3762 /// specified value for nonzero will execute.  If not computable, return
3763 /// CouldNotCompute
3764 const SCEV* ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3765   // Loops that look like: while (X == 0) are very strange indeed.  We don't
3766   // handle them yet except for the trivial case.  This could be expanded in the
3767   // future as needed.
3768
3769   // If the value is a constant, check to see if it is known to be non-zero
3770   // already.  If so, the backedge will execute zero times.
3771   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3772     if (!C->getValue()->isNullValue())
3773       return getIntegerSCEV(0, C->getType());
3774     return CouldNotCompute;  // Otherwise it will loop infinitely.
3775   }
3776
3777   // We could implement others, but I really doubt anyone writes loops like
3778   // this, and if they did, they would already be constant folded.
3779   return CouldNotCompute;
3780 }
3781
3782 /// getLoopPredecessor - If the given loop's header has exactly one unique
3783 /// predecessor outside the loop, return it. Otherwise return null.
3784 ///
3785 BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3786   BasicBlock *Header = L->getHeader();
3787   BasicBlock *Pred = 0;
3788   for (pred_iterator PI = pred_begin(Header), E = pred_end(Header);
3789        PI != E; ++PI)
3790     if (!L->contains(*PI)) {
3791       if (Pred && Pred != *PI) return 0; // Multiple predecessors.
3792       Pred = *PI;
3793     }
3794   return Pred;
3795 }
3796
3797 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
3798 /// (which may not be an immediate predecessor) which has exactly one
3799 /// successor from which BB is reachable, or null if no such block is
3800 /// found.
3801 ///
3802 BasicBlock *
3803 ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) {
3804   // If the block has a unique predecessor, then there is no path from the
3805   // predecessor to the block that does not go through the direct edge
3806   // from the predecessor to the block.
3807   if (BasicBlock *Pred = BB->getSinglePredecessor())
3808     return Pred;
3809
3810   // A loop's header is defined to be a block that dominates the loop.
3811   // If the header has a unique predecessor outside the loop, it must be
3812   // a block that has exactly one successor that can reach the loop.
3813   if (Loop *L = LI->getLoopFor(BB))
3814     return getLoopPredecessor(L);
3815
3816   return 0;
3817 }
3818
3819 /// HasSameValue - SCEV structural equivalence is usually sufficient for
3820 /// testing whether two expressions are equal, however for the purposes of
3821 /// looking for a condition guarding a loop, it can be useful to be a little
3822 /// more general, since a front-end may have replicated the controlling
3823 /// expression.
3824 ///
3825 static bool HasSameValue(const SCEV* A, const SCEV* B) {
3826   // Quick check to see if they are the same SCEV.
3827   if (A == B) return true;
3828
3829   // Otherwise, if they're both SCEVUnknown, it's possible that they hold
3830   // two different instructions with the same value. Check for this case.
3831   if (const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A))
3832     if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
3833       if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
3834         if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
3835           if (AI->isIdenticalTo(BI))
3836             return true;
3837
3838   // Otherwise assume they may have a different value.
3839   return false;
3840 }
3841
3842 /// isLoopGuardedByCond - Test whether entry to the loop is protected by
3843 /// a conditional between LHS and RHS.  This is used to help avoid max
3844 /// expressions in loop trip counts.
3845 bool ScalarEvolution::isLoopGuardedByCond(const Loop *L,
3846                                           ICmpInst::Predicate Pred,
3847                                           const SCEV *LHS, const SCEV *RHS) {
3848   // Interpret a null as meaning no loop, where there is obviously no guard
3849   // (interprocedural conditions notwithstanding).
3850   if (!L) return false;
3851
3852   BasicBlock *Predecessor = getLoopPredecessor(L);
3853   BasicBlock *PredecessorDest = L->getHeader();
3854
3855   // Starting at the loop predecessor, climb up the predecessor chain, as long
3856   // as there are predecessors that can be found that have unique successors
3857   // leading to the original header.
3858   for (; Predecessor;
3859        PredecessorDest = Predecessor,
3860        Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) {
3861
3862     BranchInst *LoopEntryPredicate =
3863       dyn_cast<BranchInst>(Predecessor->getTerminator());
3864     if (!LoopEntryPredicate ||
3865         LoopEntryPredicate->isUnconditional())
3866       continue;
3867
3868     ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
3869     if (!ICI) continue;
3870
3871     // Now that we found a conditional branch that dominates the loop, check to
3872     // see if it is the comparison we are looking for.
3873     Value *PreCondLHS = ICI->getOperand(0);
3874     Value *PreCondRHS = ICI->getOperand(1);
3875     ICmpInst::Predicate Cond;
3876     if (LoopEntryPredicate->getSuccessor(0) == PredecessorDest)
3877       Cond = ICI->getPredicate();
3878     else
3879       Cond = ICI->getInversePredicate();
3880
3881     if (Cond == Pred)
3882       ; // An exact match.
3883     else if (!ICmpInst::isTrueWhenEqual(Cond) && Pred == ICmpInst::ICMP_NE)
3884       ; // The actual condition is beyond sufficient.
3885     else
3886       // Check a few special cases.
3887       switch (Cond) {
3888       case ICmpInst::ICMP_UGT:
3889         if (Pred == ICmpInst::ICMP_ULT) {
3890           std::swap(PreCondLHS, PreCondRHS);
3891           Cond = ICmpInst::ICMP_ULT;
3892           break;
3893         }
3894         continue;
3895       case ICmpInst::ICMP_SGT:
3896         if (Pred == ICmpInst::ICMP_SLT) {
3897           std::swap(PreCondLHS, PreCondRHS);
3898           Cond = ICmpInst::ICMP_SLT;
3899           break;
3900         }
3901         continue;
3902       case ICmpInst::ICMP_NE:
3903         // Expressions like (x >u 0) are often canonicalized to (x != 0),
3904         // so check for this case by checking if the NE is comparing against
3905         // a minimum or maximum constant.
3906         if (!ICmpInst::isTrueWhenEqual(Pred))
3907           if (ConstantInt *CI = dyn_cast<ConstantInt>(PreCondRHS)) {
3908             const APInt &A = CI->getValue();
3909             switch (Pred) {
3910             case ICmpInst::ICMP_SLT:
3911               if (A.isMaxSignedValue()) break;
3912               continue;
3913             case ICmpInst::ICMP_SGT:
3914               if (A.isMinSignedValue()) break;
3915               continue;
3916             case ICmpInst::ICMP_ULT:
3917               if (A.isMaxValue()) break;
3918               continue;
3919             case ICmpInst::ICMP_UGT:
3920               if (A.isMinValue()) break;
3921               continue;
3922             default:
3923               continue;
3924             }
3925             Cond = ICmpInst::ICMP_NE;
3926             // NE is symmetric but the original comparison may not be. Swap
3927             // the operands if necessary so that they match below.
3928             if (isa<SCEVConstant>(LHS))
3929               std::swap(PreCondLHS, PreCondRHS);
3930             break;
3931           }
3932         continue;
3933       default:
3934         // We weren't able to reconcile the condition.
3935         continue;
3936       }
3937
3938     if (!PreCondLHS->getType()->isInteger()) continue;
3939
3940     const SCEV* PreCondLHSSCEV = getSCEV(PreCondLHS);
3941     const SCEV* PreCondRHSSCEV = getSCEV(PreCondRHS);
3942     if ((HasSameValue(LHS, PreCondLHSSCEV) &&
3943          HasSameValue(RHS, PreCondRHSSCEV)) ||
3944         (HasSameValue(LHS, getNotSCEV(PreCondRHSSCEV)) &&
3945          HasSameValue(RHS, getNotSCEV(PreCondLHSSCEV))))
3946       return true;
3947   }
3948
3949   return false;
3950 }
3951
3952 /// getBECount - Subtract the end and start values and divide by the step,
3953 /// rounding up, to get the number of times the backedge is executed. Return
3954 /// CouldNotCompute if an intermediate computation overflows.
3955 const SCEV* ScalarEvolution::getBECount(const SCEV* Start,
3956                                        const SCEV* End,
3957                                        const SCEV* Step) {
3958   const Type *Ty = Start->getType();
3959   const SCEV* NegOne = getIntegerSCEV(-1, Ty);
3960   const SCEV* Diff = getMinusSCEV(End, Start);
3961   const SCEV* RoundUp = getAddExpr(Step, NegOne);
3962
3963   // Add an adjustment to the difference between End and Start so that
3964   // the division will effectively round up.
3965   const SCEV* Add = getAddExpr(Diff, RoundUp);
3966
3967   // Check Add for unsigned overflow.
3968   // TODO: More sophisticated things could be done here.
3969   const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
3970   const SCEV* OperandExtendedAdd =
3971     getAddExpr(getZeroExtendExpr(Diff, WideTy),
3972                getZeroExtendExpr(RoundUp, WideTy));
3973   if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
3974     return CouldNotCompute;
3975
3976   return getUDivExpr(Add, Step);
3977 }
3978
3979 /// HowManyLessThans - Return the number of times a backedge containing the
3980 /// specified less-than comparison will execute.  If not computable, return
3981 /// CouldNotCompute.
3982 ScalarEvolution::BackedgeTakenInfo ScalarEvolution::
3983 HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
3984                  const Loop *L, bool isSigned) {
3985   // Only handle:  "ADDREC < LoopInvariant".
3986   if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
3987
3988   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
3989   if (!AddRec || AddRec->getLoop() != L)
3990     return CouldNotCompute;
3991
3992   if (AddRec->isAffine()) {
3993     // FORNOW: We only support unit strides.
3994     unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
3995     const SCEV* Step = AddRec->getStepRecurrence(*this);
3996
3997     // TODO: handle non-constant strides.
3998     const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
3999     if (!CStep || CStep->isZero())
4000       return CouldNotCompute;
4001     if (CStep->isOne()) {
4002       // With unit stride, the iteration never steps past the limit value.
4003     } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
4004       if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
4005         // Test whether a positive iteration iteration can step past the limit
4006         // value and past the maximum value for its type in a single step.
4007         if (isSigned) {
4008           APInt Max = APInt::getSignedMaxValue(BitWidth);
4009           if ((Max - CStep->getValue()->getValue())
4010                 .slt(CLimit->getValue()->getValue()))
4011             return CouldNotCompute;
4012         } else {
4013           APInt Max = APInt::getMaxValue(BitWidth);
4014           if ((Max - CStep->getValue()->getValue())
4015                 .ult(CLimit->getValue()->getValue()))
4016             return CouldNotCompute;
4017         }
4018       } else
4019         // TODO: handle non-constant limit values below.
4020         return CouldNotCompute;
4021     } else
4022       // TODO: handle negative strides below.
4023       return CouldNotCompute;
4024
4025     // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
4026     // m.  So, we count the number of iterations in which {n,+,s} < m is true.
4027     // Note that we cannot simply return max(m-n,0)/s because it's not safe to
4028     // treat m-n as signed nor unsigned due to overflow possibility.
4029
4030     // First, we get the value of the LHS in the first iteration: n
4031     const SCEV* Start = AddRec->getOperand(0);
4032
4033     // Determine the minimum constant start value.
4034     const SCEV* MinStart = isa<SCEVConstant>(Start) ? Start :
4035       getConstant(isSigned ? APInt::getSignedMinValue(BitWidth) :
4036                              APInt::getMinValue(BitWidth));
4037
4038     // If we know that the condition is true in order to enter the loop,
4039     // then we know that it will run exactly (m-n)/s times. Otherwise, we
4040     // only know that it will execute (max(m,n)-n)/s times. In both cases,
4041     // the division must round up.
4042     const SCEV* End = RHS;
4043     if (!isLoopGuardedByCond(L,
4044                              isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
4045                              getMinusSCEV(Start, Step), RHS))
4046       End = isSigned ? getSMaxExpr(RHS, Start)
4047                      : getUMaxExpr(RHS, Start);
4048
4049     // Determine the maximum constant end value.
4050     const SCEV* MaxEnd =
4051       isa<SCEVConstant>(End) ? End :
4052       getConstant(isSigned ? APInt::getSignedMaxValue(BitWidth)
4053                                .ashr(GetMinSignBits(End) - 1) :
4054                              APInt::getMaxValue(BitWidth)
4055                                .lshr(GetMinLeadingZeros(End)));
4056
4057     // Finally, we subtract these two values and divide, rounding up, to get
4058     // the number of times the backedge is executed.
4059     const SCEV* BECount = getBECount(Start, End, Step);
4060
4061     // The maximum backedge count is similar, except using the minimum start
4062     // value and the maximum end value.
4063     const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);;
4064
4065     return BackedgeTakenInfo(BECount, MaxBECount);
4066   }
4067
4068   return CouldNotCompute;
4069 }
4070
4071 /// getNumIterationsInRange - Return the number of iterations of this loop that
4072 /// produce values in the specified constant range.  Another way of looking at
4073 /// this is that it returns the first iteration number where the value is not in
4074 /// the condition, thus computing the exit count. If the iteration count can't
4075 /// be computed, an instance of SCEVCouldNotCompute is returned.
4076 const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
4077                                                    ScalarEvolution &SE) const {
4078   if (Range.isFullSet())  // Infinite loop.
4079     return SE.getCouldNotCompute();
4080
4081   // If the start is a non-zero constant, shift the range to simplify things.
4082   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
4083     if (!SC->getValue()->isZero()) {
4084       SmallVector<const SCEV*, 4> Operands(op_begin(), op_end());
4085       Operands[0] = SE.getIntegerSCEV(0, SC->getType());
4086       const SCEV* Shifted = SE.getAddRecExpr(Operands, getLoop());
4087       if (const SCEVAddRecExpr *ShiftedAddRec =
4088             dyn_cast<SCEVAddRecExpr>(Shifted))
4089         return ShiftedAddRec->getNumIterationsInRange(
4090                            Range.subtract(SC->getValue()->getValue()), SE);
4091       // This is strange and shouldn't happen.
4092       return SE.getCouldNotCompute();
4093     }
4094
4095   // The only time we can solve this is when we have all constant indices.
4096   // Otherwise, we cannot determine the overflow conditions.
4097   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
4098     if (!isa<SCEVConstant>(getOperand(i)))
4099       return SE.getCouldNotCompute();
4100
4101
4102   // Okay at this point we know that all elements of the chrec are constants and
4103   // that the start element is zero.
4104
4105   // First check to see if the range contains zero.  If not, the first
4106   // iteration exits.
4107   unsigned BitWidth = SE.getTypeSizeInBits(getType());
4108   if (!Range.contains(APInt(BitWidth, 0)))
4109     return SE.getIntegerSCEV(0, getType());
4110
4111   if (isAffine()) {
4112     // If this is an affine expression then we have this situation:
4113     //   Solve {0,+,A} in Range  ===  Ax in Range
4114
4115     // We know that zero is in the range.  If A is positive then we know that
4116     // the upper value of the range must be the first possible exit value.
4117     // If A is negative then the lower of the range is the last possible loop
4118     // value.  Also note that we already checked for a full range.
4119     APInt One(BitWidth,1);
4120     APInt A     = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
4121     APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
4122
4123     // The exit value should be (End+A)/A.
4124     APInt ExitVal = (End + A).udiv(A);
4125     ConstantInt *ExitValue = ConstantInt::get(ExitVal);
4126
4127     // Evaluate at the exit value.  If we really did fall out of the valid
4128     // range, then we computed our trip count, otherwise wrap around or other
4129     // things must have happened.
4130     ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
4131     if (Range.contains(Val->getValue()))
4132       return SE.getCouldNotCompute();  // Something strange happened
4133
4134     // Ensure that the previous value is in the range.  This is a sanity check.
4135     assert(Range.contains(
4136            EvaluateConstantChrecAtConstant(this,
4137            ConstantInt::get(ExitVal - One), SE)->getValue()) &&
4138            "Linear scev computation is off in a bad way!");
4139     return SE.getConstant(ExitValue);
4140   } else if (isQuadratic()) {
4141     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
4142     // quadratic equation to solve it.  To do this, we must frame our problem in
4143     // terms of figuring out when zero is crossed, instead of when
4144     // Range.getUpper() is crossed.
4145     SmallVector<const SCEV*, 4> NewOps(op_begin(), op_end());
4146     NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
4147     const SCEV* NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
4148
4149     // Next, solve the constructed addrec
4150     std::pair<const SCEV*,const SCEV*> Roots =
4151       SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
4152     const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
4153     const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
4154     if (R1) {
4155       // Pick the smallest positive root value.
4156       if (ConstantInt *CB =
4157           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
4158                                    R1->getValue(), R2->getValue()))) {
4159         if (CB->getZExtValue() == false)
4160           std::swap(R1, R2);   // R1 is the minimum root now.
4161
4162         // Make sure the root is not off by one.  The returned iteration should
4163         // not be in the range, but the previous one should be.  When solving
4164         // for "X*X < 5", for example, we should not return a root of 2.
4165         ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
4166                                                              R1->getValue(),
4167                                                              SE);
4168         if (Range.contains(R1Val->getValue())) {
4169           // The next iteration must be out of the range...
4170           ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1);
4171
4172           R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
4173           if (!Range.contains(R1Val->getValue()))
4174             return SE.getConstant(NextVal);
4175           return SE.getCouldNotCompute();  // Something strange happened
4176         }
4177
4178         // If R1 was not in the range, then it is a good return value.  Make
4179         // sure that R1-1 WAS in the range though, just in case.
4180         ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1);
4181         R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
4182         if (Range.contains(R1Val->getValue()))
4183           return R1;
4184         return SE.getCouldNotCompute();  // Something strange happened
4185       }
4186     }
4187   }
4188
4189   return SE.getCouldNotCompute();
4190 }
4191
4192
4193
4194 //===----------------------------------------------------------------------===//
4195 //                   SCEVCallbackVH Class Implementation
4196 //===----------------------------------------------------------------------===//
4197
4198 void ScalarEvolution::SCEVCallbackVH::deleted() {
4199   assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
4200   if (PHINode *PN = dyn_cast<PHINode>(getValPtr()))
4201     SE->ConstantEvolutionLoopExitValue.erase(PN);
4202   if (Instruction *I = dyn_cast<Instruction>(getValPtr()))
4203     SE->ValuesAtScopes.erase(I);
4204   SE->Scalars.erase(getValPtr());
4205   // this now dangles!
4206 }
4207
4208 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) {
4209   assert(SE && "SCEVCallbackVH called with a non-null ScalarEvolution!");
4210
4211   // Forget all the expressions associated with users of the old value,
4212   // so that future queries will recompute the expressions using the new
4213   // value.
4214   SmallVector<User *, 16> Worklist;
4215   Value *Old = getValPtr();
4216   bool DeleteOld = false;
4217   for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
4218        UI != UE; ++UI)
4219     Worklist.push_back(*UI);
4220   while (!Worklist.empty()) {
4221     User *U = Worklist.pop_back_val();
4222     // Deleting the Old value will cause this to dangle. Postpone
4223     // that until everything else is done.
4224     if (U == Old) {
4225       DeleteOld = true;
4226       continue;
4227     }
4228     if (PHINode *PN = dyn_cast<PHINode>(U))
4229       SE->ConstantEvolutionLoopExitValue.erase(PN);
4230     if (Instruction *I = dyn_cast<Instruction>(U))
4231       SE->ValuesAtScopes.erase(I);
4232     if (SE->Scalars.erase(U))
4233       for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
4234            UI != UE; ++UI)
4235         Worklist.push_back(*UI);
4236   }
4237   if (DeleteOld) {
4238     if (PHINode *PN = dyn_cast<PHINode>(Old))
4239       SE->ConstantEvolutionLoopExitValue.erase(PN);
4240     if (Instruction *I = dyn_cast<Instruction>(Old))
4241       SE->ValuesAtScopes.erase(I);
4242     SE->Scalars.erase(Old);
4243     // this now dangles!
4244   }
4245   // this may dangle!
4246 }
4247
4248 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
4249   : CallbackVH(V), SE(se) {}
4250
4251 //===----------------------------------------------------------------------===//
4252 //                   ScalarEvolution Class Implementation
4253 //===----------------------------------------------------------------------===//
4254
4255 ScalarEvolution::ScalarEvolution()
4256   : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
4257 }
4258
4259 bool ScalarEvolution::runOnFunction(Function &F) {
4260   this->F = &F;
4261   LI = &getAnalysis<LoopInfo>();
4262   TD = getAnalysisIfAvailable<TargetData>();
4263   return false;
4264 }
4265
4266 void ScalarEvolution::releaseMemory() {
4267   Scalars.clear();
4268   BackedgeTakenCounts.clear();
4269   ConstantEvolutionLoopExitValue.clear();
4270   ValuesAtScopes.clear();
4271
4272   for (std::map<ConstantInt*, SCEVConstant*>::iterator
4273        I = SCEVConstants.begin(), E = SCEVConstants.end(); I != E; ++I)
4274     delete I->second;
4275   for (std::map<std::pair<const SCEV*, const Type*>,
4276        SCEVTruncateExpr*>::iterator I = SCEVTruncates.begin(),
4277        E = SCEVTruncates.end(); I != E; ++I)
4278     delete I->second;
4279   for (std::map<std::pair<const SCEV*, const Type*>,
4280        SCEVZeroExtendExpr*>::iterator I = SCEVZeroExtends.begin(),
4281        E = SCEVZeroExtends.end(); I != E; ++I)
4282     delete I->second;
4283   for (std::map<std::pair<unsigned, std::vector<const SCEV*> >,
4284        SCEVCommutativeExpr*>::iterator I = SCEVCommExprs.begin(),
4285        E = SCEVCommExprs.end(); I != E; ++I)
4286     delete I->second;
4287   for (std::map<std::pair<const SCEV*, const SCEV*>, SCEVUDivExpr*>::iterator
4288        I = SCEVUDivs.begin(), E = SCEVUDivs.end(); I != E; ++I)
4289     delete I->second;
4290   for (std::map<std::pair<const SCEV*, const Type*>,
4291        SCEVSignExtendExpr*>::iterator I =  SCEVSignExtends.begin(),
4292        E = SCEVSignExtends.end(); I != E; ++I)
4293     delete I->second;
4294   for (std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
4295        SCEVAddRecExpr*>::iterator I = SCEVAddRecExprs.begin(),
4296        E = SCEVAddRecExprs.end(); I != E; ++I)
4297     delete I->second;
4298   for (std::map<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
4299        E = SCEVUnknowns.end(); I != E; ++I)
4300     delete I->second;
4301
4302   SCEVConstants.clear();
4303   SCEVTruncates.clear();
4304   SCEVZeroExtends.clear();
4305   SCEVCommExprs.clear();
4306   SCEVUDivs.clear();
4307   SCEVSignExtends.clear();
4308   SCEVAddRecExprs.clear();
4309   SCEVUnknowns.clear();
4310 }
4311
4312 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
4313   AU.setPreservesAll();
4314   AU.addRequiredTransitive<LoopInfo>();
4315 }
4316
4317 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
4318   return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L));
4319 }
4320
4321 static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
4322                           const Loop *L) {
4323   // Print all inner loops first
4324   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
4325     PrintLoopInfo(OS, SE, *I);
4326
4327   OS << "Loop " << L->getHeader()->getName() << ": ";
4328
4329   SmallVector<BasicBlock*, 8> ExitBlocks;
4330   L->getExitBlocks(ExitBlocks);
4331   if (ExitBlocks.size() != 1)
4332     OS << "<multiple exits> ";
4333
4334   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
4335     OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L);
4336   } else {
4337     OS << "Unpredictable backedge-taken count. ";
4338   }
4339
4340   OS << "\n";
4341 }
4342
4343 void ScalarEvolution::print(raw_ostream &OS, const Module* ) const {
4344   // ScalarEvolution's implementaiton of the print method is to print
4345   // out SCEV values of all instructions that are interesting. Doing
4346   // this potentially causes it to create new SCEV objects though,
4347   // which technically conflicts with the const qualifier. This isn't
4348   // observable from outside the class though (the hasSCEV function
4349   // notwithstanding), so casting away the const isn't dangerous.
4350   ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this);
4351
4352   OS << "Classifying expressions for: " << F->getName() << "\n";
4353   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
4354     if (isSCEVable(I->getType())) {
4355       OS << *I;
4356       OS << "  -->  ";
4357       const SCEV* SV = SE.getSCEV(&*I);
4358       SV->print(OS);
4359
4360       const Loop *L = LI->getLoopFor((*I).getParent());
4361
4362       const SCEV* AtUse = SE.getSCEVAtScope(SV, L);
4363       if (AtUse != SV) {
4364         OS << "  -->  ";
4365         AtUse->print(OS);
4366       }
4367
4368       if (L) {
4369         OS << "\t\t" "Exits: ";
4370         const SCEV* ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop());
4371         if (!ExitValue->isLoopInvariant(L)) {
4372           OS << "<<Unknown>>";
4373         } else {
4374           OS << *ExitValue;
4375         }
4376       }
4377
4378       OS << "\n";
4379     }
4380
4381   OS << "Determining loop execution counts for: " << F->getName() << "\n";
4382   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
4383     PrintLoopInfo(OS, &SE, *I);
4384 }
4385
4386 void ScalarEvolution::print(std::ostream &o, const Module *M) const {
4387   raw_os_ostream OS(o);
4388   print(OS, M);
4389 }