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