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