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