lib/Analysis/ScalarEvolution.cpp

   1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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 // Orthogonal to the analysis of code above, this file also implements the
  37 // ScalarEvolutionRewriter class, which is used to emit code that represents the
  38 // various recurrences present in a loop, in canonical forms.
  39 //
  40 // TODO: We should use these routines and value representations to implement
  41 // dependence analysis!
  42 //
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // There are several good references for the techniques used in this analysis.
  46 //
  47 //  Chains of recurrences -- a method to expedite the evaluation
  48 //  of closed-form functions
  49 //  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
  50 //
  51 //  On computational properties of chains of recurrences
  52 //  Eugene V. Zima
  53 //
  54 //  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
  55 //  Robert A. van Engelen
  56 //
  57 //  Efficient Symbolic Analysis for Optimizing Compilers
  58 //  Robert A. van Engelen
  59 //
  60 //  Using the chains of recurrences algebra for data dependence testing and
  61 //  induction variable substitution
  62 //  MS Thesis, Johnie Birch
  63 //
  64 //===----------------------------------------------------------------------===//
  65
  66 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  67 #include "llvm/Constants.h"
  68 #include "llvm/DerivedTypes.h"
  69 #include "llvm/Instructions.h"
  70 #include "llvm/Type.h"
  71 #include "llvm/Value.h"
  72 #include "llvm/Analysis/LoopInfo.h"
  73 #include "llvm/Assembly/Writer.h"
  74 #include "llvm/Transforms/Scalar.h"
  75 #include "llvm/Transforms/Utils/Local.h"
  76 #include "llvm/Support/CFG.h"
  77 #include "llvm/Support/ConstantRange.h"
  78 #include "llvm/Support/InstIterator.h"
  79 #include "Support/CommandLine.h"
  80 #include "Support/Statistic.h"
  81 #include <cmath>
  82 using namespace llvm;
  83
  84 namespace {
  85   RegisterAnalysis<ScalarEvolution>
  86   R("scalar-evolution", "Scalar Evolution Analysis");
  87
  88   Statistic<>
  89   NumBruteForceEvaluations("scalar-evolution",
  90                            "Number of brute force evaluations needed to calculate high-order polynomial exit values");
  91   Statistic<>
  92   NumTripCountsComputed("scalar-evolution",
  93                         "Number of loops with predictable loop counts");
  94   Statistic<>
  95   NumTripCountsNotComputed("scalar-evolution",
  96                            "Number of loops without predictable loop counts");
  97   Statistic<>
  98   NumBruteForceTripCountsComputed("scalar-evolution",
  99                         "Number of loops with trip counts computed by force");
 100
 101   cl::opt<unsigned>
 102   MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
 103                           cl::desc("Maximum number of iterations SCEV will symbolically execute a constant derived loop"),
 104                           cl::init(100));
 105 }
 106
 107 //===----------------------------------------------------------------------===//
 108 //                           SCEV class definitions
 109 //===----------------------------------------------------------------------===//
 110
 111 //===----------------------------------------------------------------------===//
 112 // Implementation of the SCEV class.
 113 //
 114 namespace {
 115   /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
 116   /// than the complexity of the RHS.  If the SCEVs have identical complexity,
 117   /// order them by their addresses.  This comparator is used to canonicalize
 118   /// expressions.
 119   struct SCEVComplexityCompare {
 120     bool operator()(SCEV *LHS, SCEV *RHS) {
 121       if (LHS->getSCEVType() < RHS->getSCEVType())
 122         return true;
 123       if (LHS->getSCEVType() == RHS->getSCEVType())
 124         return LHS < RHS;
 125       return false;
 126     }
 127   };
 128 }
 129
 130 SCEV::~SCEV() {}
 131 void SCEV::dump() const {
 132   print(std::cerr);
 133 }
 134
 135 /// getValueRange - Return the tightest constant bounds that this value is
 136 /// known to have.  This method is only valid on integer SCEV objects.
 137 ConstantRange SCEV::getValueRange() const {
 138   const Type *Ty = getType();
 139   assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!");
 140   Ty = Ty->getUnsignedVersion();
 141   // Default to a full range if no better information is available.
 142   return ConstantRange(getType());
 143 }
 144
 145
 146 SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
 147
 148 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
 149   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 150   return false;
 151 }
 152
 153 const Type *SCEVCouldNotCompute::getType() const {
 154   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 155   return 0;
 156 }
 157
 158 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
 159   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 160   return false;
 161 }
 162
 163 Value *SCEVCouldNotCompute::expandCodeFor(ScalarEvolutionRewriter &SER,
 164                                           Instruction *InsertPt) {
 165   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 166   return 0;
 167 }
 168
 169
 170 void SCEVCouldNotCompute::print(std::ostream &OS) const {
 171   OS << "***COULDNOTCOMPUTE***";
 172 }
 173
 174 bool SCEVCouldNotCompute::classof(const SCEV *S) {
 175   return S->getSCEVType() == scCouldNotCompute;
 176 }
 177
 178
 179 // SCEVConstants - Only allow the creation of one SCEVConstant for any
 180 // particular value.  Don't use a SCEVHandle here, or else the object will
 181 // never be deleted!
 182 static std::map<ConstantInt*, SCEVConstant*> SCEVConstants;
 183
 184
 185 SCEVConstant::~SCEVConstant() {
 186   SCEVConstants.erase(V);
 187 }
 188
 189 SCEVHandle SCEVConstant::get(ConstantInt *V) {
 190   // Make sure that SCEVConstant instances are all unsigned.
 191   if (V->getType()->isSigned()) {
 192     const Type *NewTy = V->getType()->getUnsignedVersion();
 193     V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy));
 194   }
 195
 196   SCEVConstant *&R = SCEVConstants[V];
 197   if (R == 0) R = new SCEVConstant(V);
 198   return R;
 199 }
 200
 201 ConstantRange SCEVConstant::getValueRange() const {
 202   return ConstantRange(V);
 203 }
 204
 205 const Type *SCEVConstant::getType() const { return V->getType(); }
 206
 207 void SCEVConstant::print(std::ostream &OS) const {
 208   WriteAsOperand(OS, V, false);
 209 }
 210
 211 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
 212 // particular input.  Don't use a SCEVHandle here, or else the object will
 213 // never be deleted!
 214 static std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates;
 215
 216 SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
 217   : SCEV(scTruncate), Op(op), Ty(ty) {
 218   assert(Op->getType()->isInteger() && Ty->isInteger() &&
 219          Ty->isUnsigned() &&
 220          "Cannot truncate non-integer value!");
 221   assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() &&
 222          "This is not a truncating conversion!");
 223 }
 224
 225 SCEVTruncateExpr::~SCEVTruncateExpr() {
 226   SCEVTruncates.erase(std::make_pair(Op, Ty));
 227 }
 228
 229 ConstantRange SCEVTruncateExpr::getValueRange() const {
 230   return getOperand()->getValueRange().truncate(getType());
 231 }
 232
 233 void SCEVTruncateExpr::print(std::ostream &OS) const {
 234   OS << "(truncate " << *Op << " to " << *Ty << ")";
 235 }
 236
 237 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
 238 // particular input.  Don't use a SCEVHandle here, or else the object will never
 239 // be deleted!
 240 static std::map<std::pair<SCEV*, const Type*>,
 241                 SCEVZeroExtendExpr*> SCEVZeroExtends;
 242
 243 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
 244   : SCEV(scTruncate), Op(Op), Ty(ty) {
 245   assert(Op->getType()->isInteger() && Ty->isInteger() &&
 246          Ty->isUnsigned() &&
 247          "Cannot zero extend non-integer value!");
 248   assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() &&
 249          "This is not an extending conversion!");
 250 }
 251
 252 SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
 253   SCEVZeroExtends.erase(std::make_pair(Op, Ty));
 254 }
 255
 256 ConstantRange SCEVZeroExtendExpr::getValueRange() const {
 257   return getOperand()->getValueRange().zeroExtend(getType());
 258 }
 259
 260 void SCEVZeroExtendExpr::print(std::ostream &OS) const {
 261   OS << "(zeroextend " << *Op << " to " << *Ty << ")";
 262 }
 263
 264 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
 265 // particular input.  Don't use a SCEVHandle here, or else the object will never
 266 // be deleted!
 267 static std::map<std::pair<unsigned, std::vector<SCEV*> >,
 268                 SCEVCommutativeExpr*> SCEVCommExprs;
 269
 270 SCEVCommutativeExpr::~SCEVCommutativeExpr() {
 271   SCEVCommExprs.erase(std::make_pair(getSCEVType(),
 272                                      std::vector<SCEV*>(Operands.begin(),
 273                                                         Operands.end())));
 274 }
 275
 276 void SCEVCommutativeExpr::print(std::ostream &OS) const {
 277   assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
 278   const char *OpStr = getOperationStr();
 279   OS << "(" << *Operands[0];
 280   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 281     OS << OpStr << *Operands[i];
 282   OS << ")";
 283 }
 284
 285 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
 286 // input.  Don't use a SCEVHandle here, or else the object will never be
 287 // deleted!
 288 static std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs;
 289
 290 SCEVUDivExpr::~SCEVUDivExpr() {
 291   SCEVUDivs.erase(std::make_pair(LHS, RHS));
 292 }
 293
 294 void SCEVUDivExpr::print(std::ostream &OS) const {
 295   OS << "(" << *LHS << " /u " << *RHS << ")";
 296 }
 297
 298 const Type *SCEVUDivExpr::getType() const {
 299   const Type *Ty = LHS->getType();
 300   if (Ty->isSigned()) Ty = Ty->getUnsignedVersion();
 301   return Ty;
 302 }
 303
 304 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
 305 // particular input.  Don't use a SCEVHandle here, or else the object will never
 306 // be deleted!
 307 static std::map<std::pair<const Loop *, std::vector<SCEV*> >,
 308                 SCEVAddRecExpr*> SCEVAddRecExprs;
 309
 310 SCEVAddRecExpr::~SCEVAddRecExpr() {
 311   SCEVAddRecExprs.erase(std::make_pair(L,
 312                                        std::vector<SCEV*>(Operands.begin(),
 313                                                           Operands.end())));
 314 }
 315
 316 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
 317   // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
 318   // contain L.
 319   return !QueryLoop->contains(L->getHeader());
 320 }
 321
 322
 323 void SCEVAddRecExpr::print(std::ostream &OS) const {
 324   OS << "{" << *Operands[0];
 325   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 326     OS << ",+," << *Operands[i];
 327   OS << "}<" << L->getHeader()->getName() + ">";
 328 }
 329
 330 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
 331 // value.  Don't use a SCEVHandle here, or else the object will never be
 332 // deleted!
 333 static std::map<Value*, SCEVUnknown*> SCEVUnknowns;
 334
 335 SCEVUnknown::~SCEVUnknown() { SCEVUnknowns.erase(V); }
 336
 337 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
 338   // All non-instruction values are loop invariant.  All instructions are loop
 339   // invariant if they are not contained in the specified loop.
 340   if (Instruction *I = dyn_cast<Instruction>(V))
 341     return !L->contains(I->getParent());
 342   return true;
 343 }
 344
 345 const Type *SCEVUnknown::getType() const {
 346   return V->getType();
 347 }
 348
 349 void SCEVUnknown::print(std::ostream &OS) const {
 350   WriteAsOperand(OS, V, false);
 351 }
 352
 353
 354
 355 //===----------------------------------------------------------------------===//
 356 //                      Simple SCEV method implementations
 357 //===----------------------------------------------------------------------===//
 358
 359 /// getIntegerSCEV - Given an integer or FP type, create a constant for the
 360 /// specified signed integer value and return a SCEV for the constant.
 361 static SCEVHandle getIntegerSCEV(int Val, const Type *Ty) {
 362   Constant *C;
 363   if (Val == 0)
 364     C = Constant::getNullValue(Ty);
 365   else if (Ty->isFloatingPoint())
 366     C = ConstantFP::get(Ty, Val);
 367   else if (Ty->isSigned())
 368     C = ConstantSInt::get(Ty, Val);
 369   else {
 370     C = ConstantSInt::get(Ty->getSignedVersion(), Val);
 371     C = ConstantExpr::getCast(C, Ty);
 372   }
 373   return SCEVUnknown::get(C);
 374 }
 375
 376 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
 377 /// input value to the specified type.  If the type must be extended, it is zero
 378 /// extended.
 379 static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) {
 380   const Type *SrcTy = V->getType();
 381   assert(SrcTy->isInteger() && Ty->isInteger() &&
 382          "Cannot truncate or zero extend with non-integer arguments!");
 383   if (SrcTy->getPrimitiveSize() == Ty->getPrimitiveSize())
 384     return V;  // No conversion
 385   if (SrcTy->getPrimitiveSize() > Ty->getPrimitiveSize())
 386     return SCEVTruncateExpr::get(V, Ty);
 387   return SCEVZeroExtendExpr::get(V, Ty);
 388 }
 389
 390 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
 391 ///
 392 static SCEVHandle getNegativeSCEV(const SCEVHandle &V) {
 393   if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
 394     return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue()));
 395
 396   return SCEVMulExpr::get(V, getIntegerSCEV(-1, V->getType()));
 397 }
 398
 399 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
 400 ///
 401 static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) {
 402   // X - Y --> X + -Y
 403   return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS));
 404 }
 405
 406
 407 /// Binomial - Evaluate N!/((N-M)!*M!)  .  Note that N is often large and M is
 408 /// often very small, so we try to reduce the number of N! terms we need to
 409 /// evaluate by evaluating this as  (N!/(N-M)!)/M!
 410 static ConstantInt *Binomial(ConstantInt *N, unsigned M) {
 411   uint64_t NVal = N->getRawValue();
 412   uint64_t FirstTerm = 1;
 413   for (unsigned i = 0; i != M; ++i)
 414     FirstTerm *= NVal-i;
 415
 416   unsigned MFactorial = 1;
 417   for (; M; --M)
 418     MFactorial *= M;
 419
 420   Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial);
 421   Result = ConstantExpr::getCast(Result, N->getType());
 422   assert(isa<ConstantInt>(Result) && "Cast of integer not folded??");
 423   return cast<ConstantInt>(Result);
 424 }
 425
 426 /// PartialFact - Compute V!/(V-NumSteps)!
 427 static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) {
 428   // Handle this case efficiently, it is common to have constant iteration
 429   // counts while computing loop exit values.
 430   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
 431     uint64_t Val = SC->getValue()->getRawValue();
 432     uint64_t Result = 1;
 433     for (; NumSteps; --NumSteps)
 434       Result *= Val-(NumSteps-1);
 435     Constant *Res = ConstantUInt::get(Type::ULongTy, Result);
 436     return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType()));
 437   }
 438
 439   const Type *Ty = V->getType();
 440   if (NumSteps == 0)
 441     return getIntegerSCEV(1, Ty);
 442
 443   SCEVHandle Result = V;
 444   for (unsigned i = 1; i != NumSteps; ++i)
 445     Result = SCEVMulExpr::get(Result, getMinusSCEV(V, getIntegerSCEV(i, Ty)));
 446   return Result;
 447 }
 448
 449
 450 /// evaluateAtIteration - Return the value of this chain of recurrences at
 451 /// the specified iteration number.  We can evaluate this recurrence by
 452 /// multiplying each element in the chain by the binomial coefficient
 453 /// corresponding to it.  In other words, we can evaluate {A,+,B,+,C,+,D} as:
 454 ///
 455 ///   A*choose(It, 0) + B*choose(It, 1) + C*choose(It, 2) + D*choose(It, 3)
 456 ///
 457 /// FIXME/VERIFY: I don't trust that this is correct in the face of overflow.
 458 /// Is the binomial equation safe using modular arithmetic??
 459 ///
 460 SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const {
 461   SCEVHandle Result = getStart();
 462   int Divisor = 1;
 463   const Type *Ty = It->getType();
 464   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
 465     SCEVHandle BC = PartialFact(It, i);
 466     Divisor *= i;
 467     SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
 468                                        getIntegerSCEV(Divisor, Ty));
 469     Result = SCEVAddExpr::get(Result, Val);
 470   }
 471   return Result;
 472 }
 473
 474
 475 //===----------------------------------------------------------------------===//
 476 //                    SCEV Expression folder implementations
 477 //===----------------------------------------------------------------------===//
 478
 479 SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) {
 480   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 481     return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
 482
 483   // If the input value is a chrec scev made out of constants, truncate
 484   // all of the constants.
 485   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
 486     std::vector<SCEVHandle> Operands;
 487     for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
 488       // FIXME: This should allow truncation of other expression types!
 489       if (isa<SCEVConstant>(AddRec->getOperand(i)))
 490         Operands.push_back(get(AddRec->getOperand(i), Ty));
 491       else
 492         break;
 493     if (Operands.size() == AddRec->getNumOperands())
 494       return SCEVAddRecExpr::get(Operands, AddRec->getLoop());
 495   }
 496
 497   SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
 498   if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
 499   return Result;
 500 }
 501
 502 SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
 503   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 504     return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
 505
 506   // FIXME: If the input value is a chrec scev, and we can prove that the value
 507   // did not overflow the old, smaller, value, we can zero extend all of the
 508   // operands (often constants).  This would allow analysis of something like
 509   // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
 510
 511   SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
 512   if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
 513   return Result;
 514 }
 515
 516 // get - Get a canonical add expression, or something simpler if possible.
 517 SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) {
 518   assert(!Ops.empty() && "Cannot get empty add!");
 519   if (Ops.size() == 1) return Ops[0];
 520
 521   // Sort by complexity, this groups all similar expression types together.
 522   std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
 523
 524   // If there are any constants, fold them together.
 525   unsigned Idx = 0;
 526   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 527     ++Idx;
 528     assert(Idx < Ops.size());
 529     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
 530       // We found two constants, fold them together!
 531       Constant *Fold = ConstantExpr::getAdd(LHSC->getValue(), RHSC->getValue());
 532       if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
 533         Ops[0] = SCEVConstant::get(CI);
 534         Ops.erase(Ops.begin()+1);  // Erase the folded element
 535         if (Ops.size() == 1) return Ops[0];
 536       } else {
 537         // If we couldn't fold the expression, move to the next constant.  Note
 538         // that this is impossible to happen in practice because we always
 539         // constant fold constant ints to constant ints.
 540         ++Idx;
 541       }
 542     }
 543
 544     // If we are left with a constant zero being added, strip it off.
 545     if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) {
 546       Ops.erase(Ops.begin());
 547       --Idx;
 548     }
 549   }
 550
 551   if (Ops.size() == 1) return Ops[0];
 552
 553   // Okay, check to see if the same value occurs in the operand list twice.  If
 554   // so, merge them together into an multiply expression.  Since we sorted the
 555   // list, these values are required to be adjacent.
 556   const Type *Ty = Ops[0]->getType();
 557   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
 558     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
 559       // Found a match, merge the two values into a multiply, and add any
 560       // remaining values to the result.
 561       SCEVHandle Two = getIntegerSCEV(2, Ty);
 562       SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two);
 563       if (Ops.size() == 2)
 564         return Mul;
 565       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
 566       Ops.push_back(Mul);
 567       return SCEVAddExpr::get(Ops);
 568     }
 569
 570   // Okay, now we know the first non-constant operand.  If there are add
 571   // operands they would be next.
 572   if (Idx < Ops.size()) {
 573     bool DeletedAdd = false;
 574     while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
 575       // If we have an add, expand the add operands onto the end of the operands
 576       // list.
 577       Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
 578       Ops.erase(Ops.begin()+Idx);
 579       DeletedAdd = true;
 580     }
 581
 582     // If we deleted at least one add, we added operands to the end of the list,
 583     // and they are not necessarily sorted.  Recurse to resort and resimplify
 584     // any operands we just aquired.
 585     if (DeletedAdd)
 586       return get(Ops);
 587   }
 588
 589   // Skip over the add expression until we get to a multiply.
 590   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
 591     ++Idx;
 592
 593   // If we are adding something to a multiply expression, make sure the
 594   // something is not already an operand of the multiply.  If so, merge it into
 595   // the multiply.
 596   for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
 597     SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
 598     for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
 599       SCEV *MulOpSCEV = Mul->getOperand(MulOp);
 600       for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
 601         if (MulOpSCEV == Ops[AddOp] &&
 602             (Mul->getNumOperands() != 2 || !isa<SCEVConstant>(MulOpSCEV))) {
 603           // Fold W + X + (X * Y * Z)  -->  W + (X * ((Y*Z)+1))
 604           SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
 605           if (Mul->getNumOperands() != 2) {
 606             // If the multiply has more than two operands, we must get the
 607             // Y*Z term.
 608             std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
 609             MulOps.erase(MulOps.begin()+MulOp);
 610             InnerMul = SCEVMulExpr::get(MulOps);
 611           }
 612           SCEVHandle One = getIntegerSCEV(1, Ty);
 613           SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One);
 614           SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]);
 615           if (Ops.size() == 2) return OuterMul;
 616           if (AddOp < Idx) {
 617             Ops.erase(Ops.begin()+AddOp);
 618             Ops.erase(Ops.begin()+Idx-1);
 619           } else {
 620             Ops.erase(Ops.begin()+Idx);
 621             Ops.erase(Ops.begin()+AddOp-1);
 622           }
 623           Ops.push_back(OuterMul);
 624           return SCEVAddExpr::get(Ops);
 625         }
 626
 627       // Check this multiply against other multiplies being added together.
 628       for (unsigned OtherMulIdx = Idx+1;
 629            OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
 630            ++OtherMulIdx) {
 631         SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
 632         // If MulOp occurs in OtherMul, we can fold the two multiplies
 633         // together.
 634         for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
 635              OMulOp != e; ++OMulOp)
 636           if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
 637             // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
 638             SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
 639             if (Mul->getNumOperands() != 2) {
 640               std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
 641               MulOps.erase(MulOps.begin()+MulOp);
 642               InnerMul1 = SCEVMulExpr::get(MulOps);
 643             }
 644             SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
 645             if (OtherMul->getNumOperands() != 2) {
 646               std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
 647                                              OtherMul->op_end());
 648               MulOps.erase(MulOps.begin()+OMulOp);
 649               InnerMul2 = SCEVMulExpr::get(MulOps);
 650             }
 651             SCEVHandle InnerMulSum = SCEVAddExpr::get(InnerMul1,InnerMul2);
 652             SCEVHandle OuterMul = SCEVMulExpr::get(MulOpSCEV, InnerMulSum);
 653             if (Ops.size() == 2) return OuterMul;
 654             Ops.erase(Ops.begin()+Idx);
 655             Ops.erase(Ops.begin()+OtherMulIdx-1);
 656             Ops.push_back(OuterMul);
 657             return SCEVAddExpr::get(Ops);
 658           }
 659       }
 660     }
 661   }
 662
 663   // If there are any add recurrences in the operands list, see if any other
 664   // added values are loop invariant.  If so, we can fold them into the
 665   // recurrence.
 666   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
 667     ++Idx;
 668
 669   // Scan over all recurrences, trying to fold loop invariants into them.
 670   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
 671     // Scan all of the other operands to this add and add them to the vector if
 672     // they are loop invariant w.r.t. the recurrence.
 673     std::vector<SCEVHandle> LIOps;
 674     SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
 675     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
 676       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
 677         LIOps.push_back(Ops[i]);
 678         Ops.erase(Ops.begin()+i);
 679         --i; --e;
 680       }
 681
 682     // If we found some loop invariants, fold them into the recurrence.
 683     if (!LIOps.empty()) {
 684       //  NLI + LI + { Start,+,Step}  -->  NLI + { LI+Start,+,Step }
 685       LIOps.push_back(AddRec->getStart());
 686
 687       std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
 688       AddRecOps[0] = SCEVAddExpr::get(LIOps);
 689
 690       SCEVHandle NewRec = SCEVAddRecExpr::get(AddRecOps, AddRec->getLoop());
 691       // If all of the other operands were loop invariant, we are done.
 692       if (Ops.size() == 1) return NewRec;
 693
 694       // Otherwise, add the folded AddRec by the non-liv parts.
 695       for (unsigned i = 0;; ++i)
 696         if (Ops[i] == AddRec) {
 697           Ops[i] = NewRec;
 698           break;
 699         }
 700       return SCEVAddExpr::get(Ops);
 701     }
 702
 703     // Okay, if there weren't any loop invariants to be folded, check to see if
 704     // there are multiple AddRec's with the same loop induction variable being
 705     // added together.  If so, we can fold them.
 706     for (unsigned OtherIdx = Idx+1;
 707          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
 708       if (OtherIdx != Idx) {
 709         SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
 710         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
 711           // Other + {A,+,B} + {C,+,D}  -->  Other + {A+C,+,B+D}
 712           std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
 713           for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
 714             if (i >= NewOps.size()) {
 715               NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
 716                             OtherAddRec->op_end());
 717               break;
 718             }
 719             NewOps[i] = SCEVAddExpr::get(NewOps[i], OtherAddRec->getOperand(i));
 720           }
 721           SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop());
 722
 723           if (Ops.size() == 2) return NewAddRec;
 724
 725           Ops.erase(Ops.begin()+Idx);
 726           Ops.erase(Ops.begin()+OtherIdx-1);
 727           Ops.push_back(NewAddRec);
 728           return SCEVAddExpr::get(Ops);
 729         }
 730       }
 731
 732     // Otherwise couldn't fold anything into this recurrence.  Move onto the
 733     // next one.
 734   }
 735
 736   // Okay, it looks like we really DO need an add expr.  Check to see if we
 737   // already have one, otherwise create a new one.
 738   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
 739   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
 740                                                               SCEVOps)];
 741   if (Result == 0) Result = new SCEVAddExpr(Ops);
 742   return Result;
 743 }
 744
 745
 746 SCEVHandle SCEVMulExpr::get(std::vector<SCEVHandle> &Ops) {
 747   assert(!Ops.empty() && "Cannot get empty mul!");
 748
 749   // Sort by complexity, this groups all similar expression types together.
 750   std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
 751
 752   // If there are any constants, fold them together.
 753   unsigned Idx = 0;
 754   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 755
 756     // C1*(C2+V) -> C1*C2 + C1*V
 757     if (Ops.size() == 2)
 758       if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
 759         if (Add->getNumOperands() == 2 &&
 760             isa<SCEVConstant>(Add->getOperand(0)))
 761           return SCEVAddExpr::get(SCEVMulExpr::get(LHSC, Add->getOperand(0)),
 762                                   SCEVMulExpr::get(LHSC, Add->getOperand(1)));
 763
 764
 765     ++Idx;
 766     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
 767       // We found two constants, fold them together!
 768       Constant *Fold = ConstantExpr::getMul(LHSC->getValue(), RHSC->getValue());
 769       if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
 770         Ops[0] = SCEVConstant::get(CI);
 771         Ops.erase(Ops.begin()+1);  // Erase the folded element
 772         if (Ops.size() == 1) return Ops[0];
 773       } else {
 774         // If we couldn't fold the expression, move to the next constant.  Note
 775         // that this is impossible to happen in practice because we always
 776         // constant fold constant ints to constant ints.
 777         ++Idx;
 778       }
 779     }
 780
 781     // If we are left with a constant one being multiplied, strip it off.
 782     if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
 783       Ops.erase(Ops.begin());
 784       --Idx;
 785     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) {
 786       // If we have a multiply of zero, it will always be zero.
 787       return Ops[0];
 788     }
 789   }
 790
 791   // Skip over the add expression until we get to a multiply.
 792   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
 793     ++Idx;
 794
 795   if (Ops.size() == 1)
 796     return Ops[0];
 797
 798   // If there are mul operands inline them all into this expression.
 799   if (Idx < Ops.size()) {
 800     bool DeletedMul = false;
 801     while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
 802       // If we have an mul, expand the mul operands onto the end of the operands
 803       // list.
 804       Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
 805       Ops.erase(Ops.begin()+Idx);
 806       DeletedMul = true;
 807     }
 808
 809     // If we deleted at least one mul, we added operands to the end of the list,
 810     // and they are not necessarily sorted.  Recurse to resort and resimplify
 811     // any operands we just aquired.
 812     if (DeletedMul)
 813       return get(Ops);
 814   }
 815
 816   // If there are any add recurrences in the operands list, see if any other
 817   // added values are loop invariant.  If so, we can fold them into the
 818   // recurrence.
 819   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
 820     ++Idx;
 821
 822   // Scan over all recurrences, trying to fold loop invariants into them.
 823   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
 824     // Scan all of the other operands to this mul and add them to the vector if
 825     // they are loop invariant w.r.t. the recurrence.
 826     std::vector<SCEVHandle> LIOps;
 827     SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
 828     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
 829       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
 830         LIOps.push_back(Ops[i]);
 831         Ops.erase(Ops.begin()+i);
 832         --i; --e;
 833       }
 834
 835     // If we found some loop invariants, fold them into the recurrence.
 836     if (!LIOps.empty()) {
 837       //  NLI * LI * { Start,+,Step}  -->  NLI * { LI*Start,+,LI*Step }
 838       std::vector<SCEVHandle> NewOps;
 839       NewOps.reserve(AddRec->getNumOperands());
 840       if (LIOps.size() == 1) {
 841         SCEV *Scale = LIOps[0];
 842         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
 843           NewOps.push_back(SCEVMulExpr::get(Scale, AddRec->getOperand(i)));
 844       } else {
 845         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
 846           std::vector<SCEVHandle> MulOps(LIOps);
 847           MulOps.push_back(AddRec->getOperand(i));
 848           NewOps.push_back(SCEVMulExpr::get(MulOps));
 849         }
 850       }
 851
 852       SCEVHandle NewRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop());
 853
 854       // If all of the other operands were loop invariant, we are done.
 855       if (Ops.size() == 1) return NewRec;
 856
 857       // Otherwise, multiply the folded AddRec by the non-liv parts.
 858       for (unsigned i = 0;; ++i)
 859         if (Ops[i] == AddRec) {
 860           Ops[i] = NewRec;
 861           break;
 862         }
 863       return SCEVMulExpr::get(Ops);
 864     }
 865
 866     // Okay, if there weren't any loop invariants to be folded, check to see if
 867     // there are multiple AddRec's with the same loop induction variable being
 868     // multiplied together.  If so, we can fold them.
 869     for (unsigned OtherIdx = Idx+1;
 870          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
 871       if (OtherIdx != Idx) {
 872         SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
 873         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
 874           // F * G  -->  {A,+,B} * {C,+,D}  -->  {A*C,+,F*D + G*B + B*D}
 875           SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
 876           SCEVHandle NewStart = SCEVMulExpr::get(F->getStart(),
 877                                                  G->getStart());
 878           SCEVHandle B = F->getStepRecurrence();
 879           SCEVHandle D = G->getStepRecurrence();
 880           SCEVHandle NewStep = SCEVAddExpr::get(SCEVMulExpr::get(F, D),
 881                                                 SCEVMulExpr::get(G, B),
 882                                                 SCEVMulExpr::get(B, D));
 883           SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewStart, NewStep,
 884                                                      F->getLoop());
 885           if (Ops.size() == 2) return NewAddRec;
 886
 887           Ops.erase(Ops.begin()+Idx);
 888           Ops.erase(Ops.begin()+OtherIdx-1);
 889           Ops.push_back(NewAddRec);
 890           return SCEVMulExpr::get(Ops);
 891         }
 892       }
 893
 894     // Otherwise couldn't fold anything into this recurrence.  Move onto the
 895     // next one.
 896   }
 897
 898   // Okay, it looks like we really DO need an mul expr.  Check to see if we
 899   // already have one, otherwise create a new one.
 900   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
 901   SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
 902                                                               SCEVOps)];
 903   if (Result == 0) Result = new SCEVMulExpr(Ops);
 904   return Result;
 905 }
 906
 907 SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
 908   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
 909     if (RHSC->getValue()->equalsInt(1))
 910       return LHS;                            // X /u 1 --> x
 911     if (RHSC->getValue()->isAllOnesValue())
 912       return getNegativeSCEV(LHS);           // X /u -1  -->  -x
 913
 914     if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
 915       Constant *LHSCV = LHSC->getValue();
 916       Constant *RHSCV = RHSC->getValue();
 917       if (LHSCV->getType()->isSigned())
 918         LHSCV = ConstantExpr::getCast(LHSCV,
 919                                       LHSCV->getType()->getUnsignedVersion());
 920       if (RHSCV->getType()->isSigned())
 921         RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType());
 922       return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV));
 923     }
 924   }
 925
 926   // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
 927
 928   SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
 929   if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
 930   return Result;
 931 }
 932
 933
 934 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
 935 /// specified loop.  Simplify the expression as much as possible.
 936 SCEVHandle SCEVAddRecExpr::get(const SCEVHandle &Start,
 937                                const SCEVHandle &Step, const Loop *L) {
 938   std::vector<SCEVHandle> Operands;
 939   Operands.push_back(Start);
 940   if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
 941     if (StepChrec->getLoop() == L) {
 942       Operands.insert(Operands.end(), StepChrec->op_begin(),
 943                       StepChrec->op_end());
 944       return get(Operands, L);
 945     }
 946
 947   Operands.push_back(Step);
 948   return get(Operands, L);
 949 }
 950
 951 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
 952 /// specified loop.  Simplify the expression as much as possible.
 953 SCEVHandle SCEVAddRecExpr::get(std::vector<SCEVHandle> &Operands,
 954                                const Loop *L) {
 955   if (Operands.size() == 1) return Operands[0];
 956
 957   if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back()))
 958     if (StepC->getValue()->isNullValue()) {
 959       Operands.pop_back();
 960       return get(Operands, L);             // { X,+,0 }  -->  X
 961     }
 962
 963   SCEVAddRecExpr *&Result =
 964     SCEVAddRecExprs[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
 965                                                          Operands.end()))];
 966   if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
 967   return Result;
 968 }
 969
 970 SCEVHandle SCEVUnknown::get(Value *V) {
 971   if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
 972     return SCEVConstant::get(CI);
 973   SCEVUnknown *&Result = SCEVUnknowns[V];
 974   if (Result == 0) Result = new SCEVUnknown(V);
 975   return Result;
 976 }
 977
 978
 979 //===----------------------------------------------------------------------===//
 980 //                  Non-trivial closed-form SCEV Expanders
 981 //===----------------------------------------------------------------------===//
 982
 983 Value *SCEVTruncateExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
 984                                        Instruction *InsertPt) {
 985   Value *V = SER.ExpandCodeFor(getOperand(), InsertPt);
 986   return new CastInst(V, getType(), "tmp.", InsertPt);
 987 }
 988
 989 Value *SCEVZeroExtendExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
 990                                          Instruction *InsertPt) {
 991   Value *V = SER.ExpandCodeFor(getOperand(), InsertPt,
 992                                getOperand()->getType()->getUnsignedVersion());
 993   return new CastInst(V, getType(), "tmp.", InsertPt);
 994 }
 995
 996 Value *SCEVAddExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
 997                                   Instruction *InsertPt) {
 998   const Type *Ty = getType();
 999   Value *V = SER.ExpandCodeFor(getOperand(getNumOperands()-1), InsertPt, Ty);
1000
1001   // Emit a bunch of add instructions
1002   for (int i = getNumOperands()-2; i >= 0; --i)
1003     V = BinaryOperator::create(Instruction::Add, V,
1004                                SER.ExpandCodeFor(getOperand(i), InsertPt, Ty),
1005                                "tmp.", InsertPt);
1006   return V;
1007 }
1008
1009 Value *SCEVMulExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1010                                   Instruction *InsertPt) {
1011   const Type *Ty = getType();
1012   int FirstOp = 0;  // Set if we should emit a subtract.
1013   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getOperand(0)))
1014     if (SC->getValue()->isAllOnesValue())
1015       FirstOp = 1;
1016
1017   int i = getNumOperands()-2;
1018   Value *V = SER.ExpandCodeFor(getOperand(i+1), InsertPt, Ty);
1019
1020   // Emit a bunch of multiply instructions
1021   for (; i >= FirstOp; --i)
1022     V = BinaryOperator::create(Instruction::Mul, V,
1023                                SER.ExpandCodeFor(getOperand(i), InsertPt, Ty),
1024                                "tmp.", InsertPt);
1025   // -1 * ...  --->  0 - ...
1026   if (FirstOp == 1)
1027     V = BinaryOperator::create(Instruction::Sub, Constant::getNullValue(Ty), V,
1028                                "tmp.", InsertPt);
1029   return V;
1030 }
1031
1032 Value *SCEVUDivExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1033                                    Instruction *InsertPt) {
1034   const Type *Ty = getType();
1035   Value *LHS = SER.ExpandCodeFor(getLHS(), InsertPt, Ty);
1036   Value *RHS = SER.ExpandCodeFor(getRHS(), InsertPt, Ty);
1037   return BinaryOperator::create(Instruction::Div, LHS, RHS, "tmp.", InsertPt);
1038 }
1039
1040 Value *SCEVAddRecExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1041                                      Instruction *InsertPt) {
1042   const Type *Ty = getType();
1043   // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
1044   assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!");
1045
1046   // {X,+,F} --> X + {0,+,F}
1047   if (!isa<SCEVConstant>(getStart()) ||
1048       !cast<SCEVConstant>(getStart())->getValue()->isNullValue()) {
1049     Value *Start = SER.ExpandCodeFor(getStart(), InsertPt, Ty);
1050     std::vector<SCEVHandle> NewOps(op_begin(), op_end());
1051     NewOps[0] = getIntegerSCEV(0, getType());
1052     Value *Rest = SER.ExpandCodeFor(SCEVAddRecExpr::get(NewOps, getLoop()),
1053                                     InsertPt, getType());
1054
1055     // FIXME: look for an existing add to use.
1056     return BinaryOperator::create(Instruction::Add, Rest, Start, "tmp.",
1057                                   InsertPt);
1058   }
1059
1060   // {0,+,1} --> Insert a canonical induction variable into the loop!
1061   if (getNumOperands() == 2 && getOperand(1) == getIntegerSCEV(1, getType())) {
1062     // Create and insert the PHI node for the induction variable in the
1063     // specified loop.
1064     BasicBlock *Header = getLoop()->getHeader();
1065     PHINode *PN = new PHINode(Ty, "indvar", Header->begin());
1066     PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
1067
1068     pred_iterator HPI = pred_begin(Header);
1069     assert(HPI != pred_end(Header) && "Loop with zero preds???");
1070     if (!getLoop()->contains(*HPI)) ++HPI;
1071     assert(HPI != pred_end(Header) && getLoop()->contains(*HPI) &&
1072            "No backedge in loop?");
1073
1074     // Insert a unit add instruction right before the terminator corresponding
1075     // to the back-edge.
1076     Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0)
1077       : (Constant*)ConstantInt::get(Ty, 1);
1078     Instruction *Add = BinaryOperator::create(Instruction::Add, PN, One,
1079                                               "indvar.next",
1080                                               (*HPI)->getTerminator());
1081
1082     pred_iterator PI = pred_begin(Header);
1083     if (*PI == L->getLoopPreheader())
1084       ++PI;
1085     PN->addIncoming(Add, *PI);
1086     return PN;
1087   }
1088
1089   // Get the canonical induction variable I for this loop.
1090   Value *I = SER.GetOrInsertCanonicalInductionVariable(getLoop(), Ty);
1091
1092   if (getNumOperands() == 2) {   // {0,+,F} --> i*F
1093     Value *F = SER.ExpandCodeFor(getOperand(1), InsertPt, Ty);
1094     return BinaryOperator::create(Instruction::Mul, I, F, "tmp.", InsertPt);
1095   }
1096
1097   // If this is a chain of recurrences, turn it into a closed form, using the
1098   // folders, then expandCodeFor the closed form.  This allows the folders to
1099   // simplify the expression without having to build a bunch of special code
1100   // into this folder.
1101   SCEVHandle IH = SCEVUnknown::get(I);   // Get I as a "symbolic" SCEV.
1102
1103   SCEVHandle V = evaluateAtIteration(IH);
1104   //std::cerr << "Evaluated: " << *this << "\n     to: " << *V << "\n";
1105
1106   return SER.ExpandCodeFor(V, InsertPt, Ty);
1107 }
1108
1109
1110 //===----------------------------------------------------------------------===//
1111 //             ScalarEvolutionsImpl Definition and Implementation
1112 //===----------------------------------------------------------------------===//
1113 //
1114 /// ScalarEvolutionsImpl - This class implements the main driver for the scalar
1115 /// evolution code.
1116 ///
1117 namespace {
1118   struct ScalarEvolutionsImpl {
1119     /// F - The function we are analyzing.
1120     ///
1121     Function &F;
1122
1123     /// LI - The loop information for the function we are currently analyzing.
1124     ///
1125     LoopInfo &LI;
1126
1127     /// UnknownValue - This SCEV is used to represent unknown trip counts and
1128     /// things.
1129     SCEVHandle UnknownValue;
1130
1131     /// Scalars - This is a cache of the scalars we have analyzed so far.
1132     ///
1133     std::map<Value*, SCEVHandle> Scalars;
1134
1135     /// IterationCounts - Cache the iteration count of the loops for this
1136     /// function as they are computed.
1137     std::map<const Loop*, SCEVHandle> IterationCounts;
1138
1139     /// ConstantEvolutionLoopExitValue - This map contains entries for all of
1140     /// the PHI instructions that we attempt to compute constant evolutions for.
1141     /// This allows us to avoid potentially expensive recomputation of these
1142     /// properties.  An instruction maps to null if we are unable to compute its
1143     /// exit value.
1144     std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
1145
1146   public:
1147     ScalarEvolutionsImpl(Function &f, LoopInfo &li)
1148       : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
1149
1150     /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1151     /// expression and create a new one.
1152     SCEVHandle getSCEV(Value *V);
1153
1154     /// getSCEVAtScope - Compute the value of the specified expression within
1155     /// the indicated loop (which may be null to indicate in no loop).  If the
1156     /// expression cannot be evaluated, return UnknownValue itself.
1157     SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
1158
1159
1160     /// hasLoopInvariantIterationCount - Return true if the specified loop has
1161     /// an analyzable loop-invariant iteration count.
1162     bool hasLoopInvariantIterationCount(const Loop *L);
1163
1164     /// getIterationCount - If the specified loop has a predictable iteration
1165     /// count, return it.  Note that it is not valid to call this method on a
1166     /// loop without a loop-invariant iteration count.
1167     SCEVHandle getIterationCount(const Loop *L);
1168
1169     /// deleteInstructionFromRecords - This method should be called by the
1170     /// client before it removes an instruction from the program, to make sure
1171     /// that no dangling references are left around.
1172     void deleteInstructionFromRecords(Instruction *I);
1173
1174   private:
1175     /// createSCEV - We know that there is no SCEV for the specified value.
1176     /// Analyze the expression.
1177     SCEVHandle createSCEV(Value *V);
1178     SCEVHandle createNodeForCast(CastInst *CI);
1179
1180     /// createNodeForPHI - Provide the special handling we need to analyze PHI
1181     /// SCEVs.
1182     SCEVHandle createNodeForPHI(PHINode *PN);
1183     void UpdatePHIUserScalarEntries(Instruction *I, PHINode *PN,
1184                                     std::set<Instruction*> &UpdatedInsts);
1185
1186     /// ComputeIterationCount - Compute the number of times the specified loop
1187     /// will iterate.
1188     SCEVHandle ComputeIterationCount(const Loop *L);
1189
1190     /// ComputeIterationCountExhaustively - If the trip is known to execute a
1191     /// constant number of times (the condition evolves only from constants),
1192     /// try to evaluate a few iterations of the loop until we get the exit
1193     /// condition gets a value of ExitWhen (true or false).  If we cannot
1194     /// evaluate the trip count of the loop, return UnknownValue.
1195     SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond,
1196                                                  bool ExitWhen);
1197
1198     /// HowFarToZero - Return the number of times a backedge comparing the
1199     /// specified value to zero will execute.  If not computable, return
1200     /// UnknownValue
1201     SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
1202
1203     /// HowFarToNonZero - Return the number of times a backedge checking the
1204     /// specified value for nonzero will execute.  If not computable, return
1205     /// UnknownValue
1206     SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
1207
1208     /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
1209     /// in the header of its containing loop, we know the loop executes a
1210     /// constant number of times, and the PHI node is just a recurrence
1211     /// involving constants, fold it.
1212     Constant *getConstantEvolutionLoopExitValue(PHINode *PN, uint64_t Its,
1213                                                 const Loop *L);
1214   };
1215 }
1216
1217 //===----------------------------------------------------------------------===//
1218 //            Basic SCEV Analysis and PHI Idiom Recognition Code
1219 //
1220
1221 /// deleteInstructionFromRecords - This method should be called by the
1222 /// client before it removes an instruction from the program, to make sure
1223 /// that no dangling references are left around.
1224 void ScalarEvolutionsImpl::deleteInstructionFromRecords(Instruction *I) {
1225   Scalars.erase(I);
1226   if (PHINode *PN = dyn_cast<PHINode>(I))
1227     ConstantEvolutionLoopExitValue.erase(PN);
1228 }
1229
1230
1231 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1232 /// expression and create a new one.
1233 SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
1234   assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
1235
1236   std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
1237   if (I != Scalars.end()) return I->second;
1238   SCEVHandle S = createSCEV(V);
1239   Scalars.insert(std::make_pair(V, S));
1240   return S;
1241 }
1242
1243
1244 /// UpdatePHIUserScalarEntries - After PHI node analysis, we have a bunch of
1245 /// entries in the scalar map that refer to the "symbolic" PHI value instead of
1246 /// the recurrence value.  After we resolve the PHI we must loop over all of the
1247 /// using instructions that have scalar map entries and update them.
1248 void ScalarEvolutionsImpl::UpdatePHIUserScalarEntries(Instruction *I,
1249                                                       PHINode *PN,
1250                                         std::set<Instruction*> &UpdatedInsts) {
1251   std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
1252   if (SI == Scalars.end()) return;   // This scalar wasn't previous processed.
1253   if (UpdatedInsts.insert(I).second) {
1254     Scalars.erase(SI);                 // Remove the old entry
1255     getSCEV(I);                        // Calculate the new entry
1256
1257     for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1258          UI != E; ++UI)
1259       UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN, UpdatedInsts);
1260   }
1261 }
1262
1263
1264 /// createNodeForPHI - PHI nodes have two cases.  Either the PHI node exists in
1265 /// a loop header, making it a potential recurrence, or it doesn't.
1266 ///
1267 SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
1268   if (PN->getNumIncomingValues() == 2)  // The loops have been canonicalized.
1269     if (const Loop *L = LI.getLoopFor(PN->getParent()))
1270       if (L->getHeader() == PN->getParent()) {
1271         // If it lives in the loop header, it has two incoming values, one
1272         // from outside the loop, and one from inside.
1273         unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
1274         unsigned BackEdge     = IncomingEdge^1;
1275
1276         // While we are analyzing this PHI node, handle its value symbolically.
1277         SCEVHandle SymbolicName = SCEVUnknown::get(PN);
1278         assert(Scalars.find(PN) == Scalars.end() &&
1279                "PHI node already processed?");
1280         Scalars.insert(std::make_pair(PN, SymbolicName));
1281
1282         // Using this symbolic name for the PHI, analyze the value coming around
1283         // the back-edge.
1284         SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
1285
1286         // NOTE: If BEValue is loop invariant, we know that the PHI node just
1287         // has a special value for the first iteration of the loop.
1288
1289         // If the value coming around the backedge is an add with the symbolic
1290         // value we just inserted, then we found a simple induction variable!
1291         if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
1292           // If there is a single occurrence of the symbolic value, replace it
1293           // with a recurrence.
1294           unsigned FoundIndex = Add->getNumOperands();
1295           for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1296             if (Add->getOperand(i) == SymbolicName)
1297               if (FoundIndex == e) {
1298                 FoundIndex = i;
1299                 break;
1300               }
1301
1302           if (FoundIndex != Add->getNumOperands()) {
1303             // Create an add with everything but the specified operand.
1304             std::vector<SCEVHandle> Ops;
1305             for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1306               if (i != FoundIndex)
1307                 Ops.push_back(Add->getOperand(i));
1308             SCEVHandle Accum = SCEVAddExpr::get(Ops);
1309
1310             // This is not a valid addrec if the step amount is varying each
1311             // loop iteration, but is not itself an addrec in this loop.
1312             if (Accum->isLoopInvariant(L) ||
1313                 (isa<SCEVAddRecExpr>(Accum) &&
1314                  cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
1315               SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1316               SCEVHandle PHISCEV  = SCEVAddRecExpr::get(StartVal, Accum, L);
1317
1318               // Okay, for the entire analysis of this edge we assumed the PHI
1319               // to be symbolic.  We now need to go back and update all of the
1320               // entries for the scalars that use the PHI (except for the PHI
1321               // itself) to use the new analyzed value instead of the "symbolic"
1322               // value.
1323               Scalars.find(PN)->second = PHISCEV;       // Update the PHI value
1324               std::set<Instruction*> UpdatedInsts;
1325               UpdatedInsts.insert(PN);
1326               for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end();
1327                    UI != E; ++UI)
1328                 UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN,
1329                                            UpdatedInsts);
1330               return PHISCEV;
1331             }
1332           }
1333         }
1334
1335         return SymbolicName;
1336       }
1337
1338   // If it's not a loop phi, we can't handle it yet.
1339   return SCEVUnknown::get(PN);
1340 }
1341
1342 /// createNodeForCast - Handle the various forms of casts that we support.
1343 ///
1344 SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) {
1345   const Type *SrcTy = CI->getOperand(0)->getType();
1346   const Type *DestTy = CI->getType();
1347
1348   // If this is a noop cast (ie, conversion from int to uint), ignore it.
1349   if (SrcTy->isLosslesslyConvertibleTo(DestTy))
1350     return getSCEV(CI->getOperand(0));
1351
1352   if (SrcTy->isInteger() && DestTy->isInteger()) {
1353     // Otherwise, if this is a truncating integer cast, we can represent this
1354     // cast.
1355     if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize())
1356       return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)),
1357                                    CI->getType()->getUnsignedVersion());
1358     if (SrcTy->isUnsigned() &&
1359         SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize())
1360       return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)),
1361                                      CI->getType()->getUnsignedVersion());
1362   }
1363
1364   // If this is an sign or zero extending cast and we can prove that the value
1365   // will never overflow, we could do similar transformations.
1366
1367   // Otherwise, we can't handle this cast!
1368   return SCEVUnknown::get(CI);
1369 }
1370
1371
1372 /// createSCEV - We know that there is no SCEV for the specified value.
1373 /// Analyze the expression.
1374 ///
1375 SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
1376   if (Instruction *I = dyn_cast<Instruction>(V)) {
1377     switch (I->getOpcode()) {
1378     case Instruction::Add:
1379       return SCEVAddExpr::get(getSCEV(I->getOperand(0)),
1380                               getSCEV(I->getOperand(1)));
1381     case Instruction::Mul:
1382       return SCEVMulExpr::get(getSCEV(I->getOperand(0)),
1383                               getSCEV(I->getOperand(1)));
1384     case Instruction::Div:
1385       if (V->getType()->isInteger() && V->getType()->isUnsigned())
1386         return SCEVUDivExpr::get(getSCEV(I->getOperand(0)),
1387                                  getSCEV(I->getOperand(1)));
1388       break;
1389
1390     case Instruction::Sub:
1391       return getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1)));
1392
1393     case Instruction::Shl:
1394       // Turn shift left of a constant amount into a multiply.
1395       if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
1396         Constant *X = ConstantInt::get(V->getType(), 1);
1397         X = ConstantExpr::getShl(X, SA);
1398         return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
1399       }
1400       break;
1401
1402     case Instruction::Shr:
1403       if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
1404         if (V->getType()->isUnsigned()) {
1405           Constant *X = ConstantInt::get(V->getType(), 1);
1406           X = ConstantExpr::getShl(X, SA);
1407           return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
1408         }
1409       break;
1410
1411     case Instruction::Cast:
1412       return createNodeForCast(cast<CastInst>(I));
1413
1414     case Instruction::PHI:
1415       return createNodeForPHI(cast<PHINode>(I));
1416
1417     default: // We cannot analyze this expression.
1418       break;
1419     }
1420   }
1421
1422   return SCEVUnknown::get(V);
1423 }
1424
1425
1426
1427 //===----------------------------------------------------------------------===//
1428 //                   Iteration Count Computation Code
1429 //
1430
1431 /// getIterationCount - If the specified loop has a predictable iteration
1432 /// count, return it.  Note that it is not valid to call this method on a
1433 /// loop without a loop-invariant iteration count.
1434 SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
1435   std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
1436   if (I == IterationCounts.end()) {
1437     SCEVHandle ItCount = ComputeIterationCount(L);
1438     I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
1439     if (ItCount != UnknownValue) {
1440       assert(ItCount->isLoopInvariant(L) &&
1441              "Computed trip count isn't loop invariant for loop!");
1442       ++NumTripCountsComputed;
1443     } else if (isa<PHINode>(L->getHeader()->begin())) {
1444       // Only count loops that have phi nodes as not being computable.
1445       ++NumTripCountsNotComputed;
1446     }
1447   }
1448   return I->second;
1449 }
1450
1451 /// ComputeIterationCount - Compute the number of times the specified loop
1452 /// will iterate.
1453 SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
1454   // If the loop has a non-one exit block count, we can't analyze it.
1455   std::vector<BasicBlock*> ExitBlocks;
1456   L->getExitBlocks(ExitBlocks);
1457   if (ExitBlocks.size() != 1) return UnknownValue;
1458
1459   // Okay, there is one exit block.  Try to find the condition that causes the
1460   // loop to be exited.
1461   BasicBlock *ExitBlock = ExitBlocks[0];
1462
1463   BasicBlock *ExitingBlock = 0;
1464   for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
1465        PI != E; ++PI)
1466     if (L->contains(*PI)) {
1467       if (ExitingBlock == 0)
1468         ExitingBlock = *PI;
1469       else
1470         return UnknownValue;   // More than one block exiting!
1471     }
1472   assert(ExitingBlock && "No exits from loop, something is broken!");
1473
1474   // Okay, we've computed the exiting block.  See what condition causes us to
1475   // exit.
1476   //
1477   // FIXME: we should be able to handle switch instructions (with a single exit)
1478   // FIXME: We should handle cast of int to bool as well
1479   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1480   if (ExitBr == 0) return UnknownValue;
1481   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
1482   SetCondInst *ExitCond = dyn_cast<SetCondInst>(ExitBr->getCondition());
1483   if (ExitCond == 0)  // Not a setcc
1484     return ComputeIterationCountExhaustively(L, ExitBr->getCondition(),
1485                                           ExitBr->getSuccessor(0) == ExitBlock);
1486
1487   SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
1488   SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
1489
1490   // Try to evaluate any dependencies out of the loop.
1491   SCEVHandle Tmp = getSCEVAtScope(LHS, L);
1492   if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
1493   Tmp = getSCEVAtScope(RHS, L);
1494   if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
1495
1496   // If the condition was exit on true, convert the condition to exit on false.
1497   Instruction::BinaryOps Cond;
1498   if (ExitBr->getSuccessor(1) == ExitBlock)
1499     Cond = ExitCond->getOpcode();
1500   else
1501     Cond = ExitCond->getInverseCondition();
1502
1503   // At this point, we would like to compute how many iterations of the loop the
1504   // predicate will return true for these inputs.
1505   if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) {
1506     // If there is a constant, force it into the RHS.
1507     std::swap(LHS, RHS);
1508     Cond = SetCondInst::getSwappedCondition(Cond);
1509   }
1510
1511   // FIXME: think about handling pointer comparisons!  i.e.:
1512   // while (P != P+100) ++P;
1513
1514   // If we have a comparison of a chrec against a constant, try to use value
1515   // ranges to answer this query.
1516   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
1517     if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
1518       if (AddRec->getLoop() == L) {
1519         // Form the comparison range using the constant of the correct type so
1520         // that the ConstantRange class knows to do a signed or unsigned
1521         // comparison.
1522         ConstantInt *CompVal = RHSC->getValue();
1523         const Type *RealTy = ExitCond->getOperand(0)->getType();
1524         CompVal = dyn_cast<ConstantInt>(ConstantExpr::getCast(CompVal, RealTy));
1525         if (CompVal) {
1526           // Form the constant range.
1527           ConstantRange CompRange(Cond, CompVal);
1528
1529           // Now that we have it, if it's signed, convert it to an unsigned
1530           // range.
1531           if (CompRange.getLower()->getType()->isSigned()) {
1532             const Type *NewTy = RHSC->getValue()->getType();
1533             Constant *NewL = ConstantExpr::getCast(CompRange.getLower(), NewTy);
1534             Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy);
1535             CompRange = ConstantRange(NewL, NewU);
1536           }
1537
1538           SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange);
1539           if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
1540         }
1541       }
1542
1543   switch (Cond) {
1544   case Instruction::SetNE:                     // while (X != Y)
1545     // Convert to: while (X-Y != 0)
1546     if (LHS->getType()->isInteger()) {
1547       SCEVHandle TC = HowFarToZero(getMinusSCEV(LHS, RHS), L);
1548       if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1549     }
1550     break;
1551   case Instruction::SetEQ:
1552     // Convert to: while (X-Y == 0)           // while (X == Y)
1553     if (LHS->getType()->isInteger()) {
1554       SCEVHandle TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
1555       if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1556     }
1557     break;
1558   default:
1559 #if 0
1560     std::cerr << "ComputeIterationCount ";
1561     if (ExitCond->getOperand(0)->getType()->isUnsigned())
1562       std::cerr << "[unsigned] ";
1563     std::cerr << *LHS << "   "
1564               << Instruction::getOpcodeName(Cond) << "   " << *RHS << "\n";
1565 #endif
1566     break;
1567   }
1568
1569   return ComputeIterationCountExhaustively(L, ExitCond,
1570                                          ExitBr->getSuccessor(0) == ExitBlock);
1571 }
1572
1573 /// CanConstantFold - Return true if we can constant fold an instruction of the
1574 /// specified type, assuming that all operands were constants.
1575 static bool CanConstantFold(const Instruction *I) {
1576   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I) ||
1577       isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
1578     return true;
1579
1580   if (const CallInst *CI = dyn_cast<CallInst>(I))
1581     if (const Function *F = CI->getCalledFunction())
1582       return canConstantFoldCallTo((Function*)F);  // FIXME: elim cast
1583   return false;
1584 }
1585
1586 /// ConstantFold - Constant fold an instruction of the specified type with the
1587 /// specified constant operands.  This function may modify the operands vector.
1588 static Constant *ConstantFold(const Instruction *I,
1589                               std::vector<Constant*> &Operands) {
1590   if (isa<BinaryOperator>(I) || isa<ShiftInst>(I))
1591     return ConstantExpr::get(I->getOpcode(), Operands[0], Operands[1]);
1592
1593   switch (I->getOpcode()) {
1594   case Instruction::Cast:
1595     return ConstantExpr::getCast(Operands[0], I->getType());
1596   case Instruction::Select:
1597     return ConstantExpr::getSelect(Operands[0], Operands[1], Operands[2]);
1598   case Instruction::Call:
1599     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Operands[0])) {
1600       Operands.erase(Operands.begin());
1601       return ConstantFoldCall(cast<Function>(CPR->getValue()), Operands);
1602     }
1603
1604     return 0;
1605   case Instruction::GetElementPtr:
1606     Constant *Base = Operands[0];
1607     Operands.erase(Operands.begin());
1608     return ConstantExpr::getGetElementPtr(Base, Operands);
1609   }
1610   return 0;
1611 }
1612
1613
1614 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
1615 /// in the loop that V is derived from.  We allow arbitrary operations along the
1616 /// way, but the operands of an operation must either be constants or a value
1617 /// derived from a constant PHI.  If this expression does not fit with these
1618 /// constraints, return null.
1619 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
1620   // If this is not an instruction, or if this is an instruction outside of the
1621   // loop, it can't be derived from a loop PHI.
1622   Instruction *I = dyn_cast<Instruction>(V);
1623   if (I == 0 || !L->contains(I->getParent())) return 0;
1624
1625   if (PHINode *PN = dyn_cast<PHINode>(I))
1626     if (L->getHeader() == I->getParent())
1627       return PN;
1628     else
1629       // We don't currently keep track of the control flow needed to evaluate
1630       // PHIs, so we cannot handle PHIs inside of loops.
1631       return 0;
1632
1633   // If we won't be able to constant fold this expression even if the operands
1634   // are constants, return early.
1635   if (!CanConstantFold(I)) return 0;
1636
1637   // Otherwise, we can evaluate this instruction if all of its operands are
1638   // constant or derived from a PHI node themselves.
1639   PHINode *PHI = 0;
1640   for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
1641     if (!(isa<Constant>(I->getOperand(Op)) ||
1642           isa<GlobalValue>(I->getOperand(Op)))) {
1643       PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
1644       if (P == 0) return 0;  // Not evolving from PHI
1645       if (PHI == 0)
1646         PHI = P;
1647       else if (PHI != P)
1648         return 0;  // Evolving from multiple different PHIs.
1649     }
1650
1651   // This is a expression evolving from a constant PHI!
1652   return PHI;
1653 }
1654
1655 /// EvaluateExpression - Given an expression that passes the
1656 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
1657 /// in the loop has the value PHIVal.  If we can't fold this expression for some
1658 /// reason, return null.
1659 static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
1660   if (isa<PHINode>(V)) return PHIVal;
1661   if (Constant *C = dyn_cast<Constant>(V)) return C;
1662   if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
1663     return ConstantPointerRef::get(GV);
1664   Instruction *I = cast<Instruction>(V);
1665
1666   std::vector<Constant*> Operands;
1667   Operands.resize(I->getNumOperands());
1668
1669   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1670     Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
1671     if (Operands[i] == 0) return 0;
1672   }
1673
1674   return ConstantFold(I, Operands);
1675 }
1676
1677 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
1678 /// in the header of its containing loop, we know the loop executes a
1679 /// constant number of times, and the PHI node is just a recurrence
1680 /// involving constants, fold it.
1681 Constant *ScalarEvolutionsImpl::
1682 getConstantEvolutionLoopExitValue(PHINode *PN, uint64_t Its, const Loop *L) {
1683   std::map<PHINode*, Constant*>::iterator I =
1684     ConstantEvolutionLoopExitValue.find(PN);
1685   if (I != ConstantEvolutionLoopExitValue.end())
1686     return I->second;
1687
1688   if (Its > MaxBruteForceIterations)
1689     return ConstantEvolutionLoopExitValue[PN] = 0;  // Not going to evaluate it.
1690
1691   Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
1692
1693   // Since the loop is canonicalized, the PHI node must have two entries.  One
1694   // entry must be a constant (coming in from outside of the loop), and the
1695   // second must be derived from the same PHI.
1696   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
1697   Constant *StartCST =
1698     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
1699   if (StartCST == 0)
1700     return RetVal = 0;  // Must be a constant.
1701
1702   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
1703   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
1704   if (PN2 != PN)
1705     return RetVal = 0;  // Not derived from same PHI.
1706
1707   // Execute the loop symbolically to determine the exit value.
1708   unsigned IterationNum = 0;
1709   unsigned NumIterations = Its;
1710   if (NumIterations != Its)
1711     return RetVal = 0;  // More than 2^32 iterations??
1712
1713   for (Constant *PHIVal = StartCST; ; ++IterationNum) {
1714     if (IterationNum == NumIterations)
1715       return RetVal = PHIVal;  // Got exit value!
1716
1717     // Compute the value of the PHI node for the next iteration.
1718     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
1719     if (NextPHI == PHIVal)
1720       return RetVal = NextPHI;  // Stopped evolving!
1721     if (NextPHI == 0)
1722       return 0;        // Couldn't evaluate!
1723     PHIVal = NextPHI;
1724   }
1725 }
1726
1727 /// ComputeIterationCountExhaustively - If the trip is known to execute a
1728 /// constant number of times (the condition evolves only from constants),
1729 /// try to evaluate a few iterations of the loop until we get the exit
1730 /// condition gets a value of ExitWhen (true or false).  If we cannot
1731 /// evaluate the trip count of the loop, return UnknownValue.
1732 SCEVHandle ScalarEvolutionsImpl::
1733 ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
1734   PHINode *PN = getConstantEvolvingPHI(Cond, L);
1735   if (PN == 0) return UnknownValue;
1736
1737   // Since the loop is canonicalized, the PHI node must have two entries.  One
1738   // entry must be a constant (coming in from outside of the loop), and the
1739   // second must be derived from the same PHI.
1740   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
1741   Constant *StartCST =
1742     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
1743   if (StartCST == 0) return UnknownValue;  // Must be a constant.
1744
1745   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
1746   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
1747   if (PN2 != PN) return UnknownValue;  // Not derived from same PHI.
1748
1749   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
1750   // the loop symbolically to determine when the condition gets a value of
1751   // "ExitWhen".
1752   unsigned IterationNum = 0;
1753   unsigned MaxIterations = MaxBruteForceIterations;   // Limit analysis.
1754   for (Constant *PHIVal = StartCST;
1755        IterationNum != MaxIterations; ++IterationNum) {
1756     ConstantBool *CondVal =
1757       dyn_cast_or_null<ConstantBool>(EvaluateExpression(Cond, PHIVal));
1758     if (!CondVal) return UnknownValue;     // Couldn't symbolically evaluate.
1759
1760     if (CondVal->getValue() == ExitWhen) {
1761       ConstantEvolutionLoopExitValue[PN] = PHIVal;
1762       ++NumBruteForceTripCountsComputed;
1763       return SCEVConstant::get(ConstantUInt::get(Type::UIntTy, IterationNum));
1764     }
1765
1766     // Compute the value of the PHI node for the next iteration.
1767     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
1768     if (NextPHI == 0 || NextPHI == PHIVal)
1769       return UnknownValue;  // Couldn't evaluate or not making progress...
1770     PHIVal = NextPHI;
1771   }
1772
1773   // Too many iterations were needed to evaluate.
1774   return UnknownValue;
1775 }
1776
1777 /// getSCEVAtScope - Compute the value of the specified expression within the
1778 /// indicated loop (which may be null to indicate in no loop).  If the
1779 /// expression cannot be evaluated, return UnknownValue.
1780 SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
1781   // FIXME: this should be turned into a virtual method on SCEV!
1782
1783   if (isa<SCEVConstant>(V)) return V;
1784
1785   // If this instruction is evolves from a constant-evolving PHI, compute the
1786   // exit value from the loop without using SCEVs.
1787   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
1788     if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
1789       const Loop *LI = this->LI[I->getParent()];
1790       if (LI && LI->getParentLoop() == L)  // Looking for loop exit value.
1791         if (PHINode *PN = dyn_cast<PHINode>(I))
1792           if (PN->getParent() == LI->getHeader()) {
1793             // Okay, there is no closed form solution for the PHI node.  Check
1794             // to see if the loop that contains it has a known iteration count.
1795             // If so, we may be able to force computation of the exit value.
1796             SCEVHandle IterationCount = getIterationCount(LI);
1797             if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) {
1798               // Okay, we know how many times the containing loop executes.  If
1799               // this is a constant evolving PHI node, get the final value at
1800               // the specified iteration number.
1801               Constant *RV = getConstantEvolutionLoopExitValue(PN,
1802                                                ICC->getValue()->getRawValue(),
1803                                                                LI);
1804               if (RV) return SCEVUnknown::get(RV);
1805             }
1806           }
1807
1808       // Okay, this is a some expression that we cannot symbolically evaluate
1809       // into a SCEV.  Check to see if it's possible to symbolically evaluate
1810       // the arguments into constants, and if see, try to constant propagate the
1811       // result.  This is particularly useful for computing loop exit values.
1812       if (CanConstantFold(I)) {
1813         std::vector<Constant*> Operands;
1814         Operands.reserve(I->getNumOperands());
1815         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1816           Value *Op = I->getOperand(i);
1817           if (Constant *C = dyn_cast<Constant>(Op)) {
1818             Operands.push_back(C);
1819           } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Op)) {
1820             Operands.push_back(ConstantPointerRef::get(GV));
1821           } else {
1822             SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
1823             if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
1824               Operands.push_back(ConstantExpr::getCast(SC->getValue(),
1825                                                        Op->getType()));
1826             else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
1827               if (Constant *C = dyn_cast<Constant>(SU->getValue()))
1828                 Operands.push_back(ConstantExpr::getCast(C, Op->getType()));
1829               else
1830                 return V;
1831             } else {
1832               return V;
1833             }
1834           }
1835         }
1836         return SCEVUnknown::get(ConstantFold(I, Operands));
1837       }
1838     }
1839
1840     // This is some other type of SCEVUnknown, just return it.
1841     return V;
1842   }
1843
1844   if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
1845     // Avoid performing the look-up in the common case where the specified
1846     // expression has no loop-variant portions.
1847     for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
1848       SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
1849       if (OpAtScope != Comm->getOperand(i)) {
1850         if (OpAtScope == UnknownValue) return UnknownValue;
1851         // Okay, at least one of these operands is loop variant but might be
1852         // foldable.  Build a new instance of the folded commutative expression.
1853         std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
1854         NewOps.push_back(OpAtScope);
1855
1856         for (++i; i != e; ++i) {
1857           OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
1858           if (OpAtScope == UnknownValue) return UnknownValue;
1859           NewOps.push_back(OpAtScope);
1860         }
1861         if (isa<SCEVAddExpr>(Comm))
1862           return SCEVAddExpr::get(NewOps);
1863         assert(isa<SCEVMulExpr>(Comm) && "Only know about add and mul!");
1864         return SCEVMulExpr::get(NewOps);
1865       }
1866     }
1867     // If we got here, all operands are loop invariant.
1868     return Comm;
1869   }
1870
1871   if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
1872     SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
1873     if (LHS == UnknownValue) return LHS;
1874     SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L);
1875     if (RHS == UnknownValue) return RHS;
1876     if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS())
1877       return UDiv;   // must be loop invariant
1878     return SCEVUDivExpr::get(LHS, RHS);
1879   }
1880
1881   // If this is a loop recurrence for a loop that does not contain L, then we
1882   // are dealing with the final value computed by the loop.
1883   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
1884     if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
1885       // To evaluate this recurrence, we need to know how many times the AddRec
1886       // loop iterates.  Compute this now.
1887       SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
1888       if (IterationCount == UnknownValue) return UnknownValue;
1889       IterationCount = getTruncateOrZeroExtend(IterationCount,
1890                                                AddRec->getType());
1891
1892       // If the value is affine, simplify the expression evaluation to just
1893       // Start + Step*IterationCount.
1894       if (AddRec->isAffine())
1895         return SCEVAddExpr::get(AddRec->getStart(),
1896                                 SCEVMulExpr::get(IterationCount,
1897                                                  AddRec->getOperand(1)));
1898
1899       // Otherwise, evaluate it the hard way.
1900       return AddRec->evaluateAtIteration(IterationCount);
1901     }
1902     return UnknownValue;
1903   }
1904
1905   //assert(0 && "Unknown SCEV type!");
1906   return UnknownValue;
1907 }
1908
1909
1910 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
1911 /// given quadratic chrec {L,+,M,+,N}.  This returns either the two roots (which
1912 /// might be the same) or two SCEVCouldNotCompute objects.
1913 ///
1914 static std::pair<SCEVHandle,SCEVHandle>
1915 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) {
1916   assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
1917   SCEVConstant *L = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
1918   SCEVConstant *M = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
1919   SCEVConstant *N = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
1920
1921   // We currently can only solve this if the coefficients are constants.
1922   if (!L || !M || !N) {
1923     SCEV *CNC = new SCEVCouldNotCompute();
1924     return std::make_pair(CNC, CNC);
1925   }
1926
1927   Constant *Two = ConstantInt::get(L->getValue()->getType(), 2);
1928
1929   // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
1930   Constant *C = L->getValue();
1931   // The B coefficient is M-N/2
1932   Constant *B = ConstantExpr::getSub(M->getValue(),
1933                                      ConstantExpr::getDiv(N->getValue(),
1934                                                           Two));
1935   // The A coefficient is N/2
1936   Constant *A = ConstantExpr::getDiv(N->getValue(), Two);
1937
1938   // Compute the B^2-4ac term.
1939   Constant *SqrtTerm =
1940     ConstantExpr::getMul(ConstantInt::get(C->getType(), 4),
1941                          ConstantExpr::getMul(A, C));
1942   SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm);
1943
1944   // Compute floor(sqrt(B^2-4ac))
1945   ConstantUInt *SqrtVal =
1946     cast<ConstantUInt>(ConstantExpr::getCast(SqrtTerm,
1947                                    SqrtTerm->getType()->getUnsignedVersion()));
1948   uint64_t SqrtValV = SqrtVal->getValue();
1949   uint64_t SqrtValV2 = (uint64_t)sqrt(SqrtValV);
1950   // The square root might not be precise for arbitrary 64-bit integer
1951   // values.  Do some sanity checks to ensure it's correct.
1952   if (SqrtValV2*SqrtValV2 > SqrtValV ||
1953       (SqrtValV2+1)*(SqrtValV2+1) <= SqrtValV) {
1954     SCEV *CNC = new SCEVCouldNotCompute();
1955     return std::make_pair(CNC, CNC);
1956   }
1957
1958   SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2);
1959   SqrtTerm = ConstantExpr::getCast(SqrtVal, SqrtTerm->getType());
1960
1961   Constant *NegB = ConstantExpr::getNeg(B);
1962   Constant *TwoA = ConstantExpr::getMul(A, Two);
1963
1964   // The divisions must be performed as signed divisions.
1965   const Type *SignedTy = NegB->getType()->getSignedVersion();
1966   NegB = ConstantExpr::getCast(NegB, SignedTy);
1967   TwoA = ConstantExpr::getCast(TwoA, SignedTy);
1968   SqrtTerm = ConstantExpr::getCast(SqrtTerm, SignedTy);
1969
1970   Constant *Solution1 =
1971     ConstantExpr::getDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA);
1972   Constant *Solution2 =
1973     ConstantExpr::getDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA);
1974   return std::make_pair(SCEVUnknown::get(Solution1),
1975                         SCEVUnknown::get(Solution2));
1976 }
1977
1978 /// HowFarToZero - Return the number of times a backedge comparing the specified
1979 /// value to zero will execute.  If not computable, return UnknownValue
1980 SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
1981   // If the value is a constant
1982   if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
1983     // If the value is already zero, the branch will execute zero times.
1984     if (C->getValue()->isNullValue()) return C;
1985     return UnknownValue;  // Otherwise it will loop infinitely.
1986   }
1987
1988   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
1989   if (!AddRec || AddRec->getLoop() != L)
1990     return UnknownValue;
1991
1992   if (AddRec->isAffine()) {
1993     // If this is an affine expression the execution count of this branch is
1994     // equal to:
1995     //
1996     //     (0 - Start/Step)    iff   Start % Step == 0
1997     //
1998     // Get the initial value for the loop.
1999     SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
2000     SCEVHandle Step = AddRec->getOperand(1);
2001
2002     Step = getSCEVAtScope(Step, L->getParentLoop());
2003
2004     // Figure out if Start % Step == 0.
2005     // FIXME: We should add DivExpr and RemExpr operations to our AST.
2006     if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
2007       if (StepC->getValue()->equalsInt(1))      // N % 1 == 0
2008         return getNegativeSCEV(Start);  // 0 - Start/1 == -Start
2009       if (StepC->getValue()->isAllOnesValue())  // N % -1 == 0
2010         return Start;                   // 0 - Start/-1 == Start
2011
2012       // Check to see if Start is divisible by SC with no remainder.
2013       if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) {
2014         ConstantInt *StartCC = StartC->getValue();
2015         Constant *StartNegC = ConstantExpr::getNeg(StartCC);
2016         Constant *Rem = ConstantExpr::getRem(StartNegC, StepC->getValue());
2017         if (Rem->isNullValue()) {
2018           Constant *Result =ConstantExpr::getDiv(StartNegC,StepC->getValue());
2019           return SCEVUnknown::get(Result);
2020         }
2021       }
2022     }
2023   } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
2024     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
2025     // the quadratic equation to solve it.
2026     std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec);
2027     SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2028     SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2029     if (R1) {
2030 #if 0
2031       std::cerr << "HFTZ: " << *V << " - sol#1: " << *R1
2032                 << "  sol#2: " << *R2 << "\n";
2033 #endif
2034       // Pick the smallest positive root value.
2035       assert(R1->getType()->isUnsigned()&&"Didn't canonicalize to unsigned?");
2036       if (ConstantBool *CB =
2037           dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
2038                                                         R2->getValue()))) {
2039         if (CB != ConstantBool::True)
2040           std::swap(R1, R2);   // R1 is the minimum root now.
2041
2042         // We can only use this value if the chrec ends up with an exact zero
2043         // value at this index.  When solving for "X*X != 5", for example, we
2044         // should not accept a root of 2.
2045         SCEVHandle Val = AddRec->evaluateAtIteration(R1);
2046         if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val))
2047           if (EvalVal->getValue()->isNullValue())
2048             return R1;  // We found a quadratic root!
2049       }
2050     }
2051   }
2052
2053   return UnknownValue;
2054 }
2055
2056 /// HowFarToNonZero - Return the number of times a backedge checking the
2057 /// specified value for nonzero will execute.  If not computable, return
2058 /// UnknownValue
2059 SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
2060   // Loops that look like: while (X == 0) are very strange indeed.  We don't
2061   // handle them yet except for the trivial case.  This could be expanded in the
2062   // future as needed.
2063
2064   // If the value is a constant, check to see if it is known to be non-zero
2065   // already.  If so, the backedge will execute zero times.
2066   if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2067     Constant *Zero = Constant::getNullValue(C->getValue()->getType());
2068     Constant *NonZero = ConstantExpr::getSetNE(C->getValue(), Zero);
2069     if (NonZero == ConstantBool::True)
2070       return getSCEV(Zero);
2071     return UnknownValue;  // Otherwise it will loop infinitely.
2072   }
2073
2074   // We could implement others, but I really doubt anyone writes loops like
2075   // this, and if they did, they would already be constant folded.
2076   return UnknownValue;
2077 }
2078
2079 static ConstantInt *
2080 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) {
2081   SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C));
2082   SCEVHandle Val = AddRec->evaluateAtIteration(InVal);
2083   assert(isa<SCEVConstant>(Val) &&
2084          "Evaluation of SCEV at constant didn't fold correctly?");
2085   return cast<SCEVConstant>(Val)->getValue();
2086 }
2087
2088
2089 /// getNumIterationsInRange - Return the number of iterations of this loop that
2090 /// produce values in the specified constant range.  Another way of looking at
2091 /// this is that it returns the first iteration number where the value is not in
2092 /// the condition, thus computing the exit count. If the iteration count can't
2093 /// be computed, an instance of SCEVCouldNotCompute is returned.
2094 SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const {
2095   if (Range.isFullSet())  // Infinite loop.
2096     return new SCEVCouldNotCompute();
2097
2098   // If the start is a non-zero constant, shift the range to simplify things.
2099   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
2100     if (!SC->getValue()->isNullValue()) {
2101       std::vector<SCEVHandle> Operands(op_begin(), op_end());
2102       Operands[0] = getIntegerSCEV(0, SC->getType());
2103       SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop());
2104       if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
2105         return ShiftedAddRec->getNumIterationsInRange(
2106                                               Range.subtract(SC->getValue()));
2107       // This is strange and shouldn't happen.
2108       return new SCEVCouldNotCompute();
2109     }
2110
2111   // The only time we can solve this is when we have all constant indices.
2112   // Otherwise, we cannot determine the overflow conditions.
2113   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2114     if (!isa<SCEVConstant>(getOperand(i)))
2115       return new SCEVCouldNotCompute();
2116
2117
2118   // Okay at this point we know that all elements of the chrec are constants and
2119   // that the start element is zero.
2120
2121   // First check to see if the range contains zero.  If not, the first
2122   // iteration exits.
2123   ConstantInt *Zero = ConstantInt::get(getType(), 0);
2124   if (!Range.contains(Zero)) return SCEVConstant::get(Zero);
2125
2126   if (isAffine()) {
2127     // If this is an affine expression then we have this situation:
2128     //   Solve {0,+,A} in Range  ===  Ax in Range
2129
2130     // Since we know that zero is in the range, we know that the upper value of
2131     // the range must be the first possible exit value.  Also note that we
2132     // already checked for a full range.
2133     ConstantInt *Upper = cast<ConstantInt>(Range.getUpper());
2134     ConstantInt *A     = cast<SCEVConstant>(getOperand(1))->getValue();
2135     ConstantInt *One   = ConstantInt::get(getType(), 1);
2136
2137     // The exit value should be (Upper+A-1)/A.
2138     Constant *ExitValue = Upper;
2139     if (A != One) {
2140       ExitValue = ConstantExpr::getSub(ConstantExpr::getAdd(Upper, A), One);
2141       ExitValue = ConstantExpr::getDiv(ExitValue, A);
2142     }
2143     assert(isa<ConstantInt>(ExitValue) &&
2144            "Constant folding of integers not implemented?");
2145
2146     // Evaluate at the exit value.  If we really did fall out of the valid
2147     // range, then we computed our trip count, otherwise wrap around or other
2148     // things must have happened.
2149     ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue);
2150     if (Range.contains(Val))
2151       return new SCEVCouldNotCompute();  // Something strange happened
2152
2153     // Ensure that the previous value is in the range.  This is a sanity check.
2154     assert(Range.contains(EvaluateConstantChrecAtConstant(this,
2155                               ConstantExpr::getSub(ExitValue, One))) &&
2156            "Linear scev computation is off in a bad way!");
2157     return SCEVConstant::get(cast<ConstantInt>(ExitValue));
2158   } else if (isQuadratic()) {
2159     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
2160     // quadratic equation to solve it.  To do this, we must frame our problem in
2161     // terms of figuring out when zero is crossed, instead of when
2162     // Range.getUpper() is crossed.
2163     std::vector<SCEVHandle> NewOps(op_begin(), op_end());
2164     NewOps[0] = getNegativeSCEV(SCEVUnknown::get(Range.getUpper()));
2165     SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop());
2166
2167     // Next, solve the constructed addrec
2168     std::pair<SCEVHandle,SCEVHandle> Roots =
2169       SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec));
2170     SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2171     SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2172     if (R1) {
2173       // Pick the smallest positive root value.
2174       assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?");
2175       if (ConstantBool *CB =
2176           dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
2177                                                         R2->getValue()))) {
2178         if (CB != ConstantBool::True)
2179           std::swap(R1, R2);   // R1 is the minimum root now.
2180
2181         // Make sure the root is not off by one.  The returned iteration should
2182         // not be in the range, but the previous one should be.  When solving
2183         // for "X*X < 5", for example, we should not return a root of 2.
2184         ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
2185                                                              R1->getValue());
2186         if (Range.contains(R1Val)) {
2187           // The next iteration must be out of the range...
2188           Constant *NextVal =
2189             ConstantExpr::getAdd(R1->getValue(),
2190                                  ConstantInt::get(R1->getType(), 1));
2191
2192           R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
2193           if (!Range.contains(R1Val))
2194             return SCEVUnknown::get(NextVal);
2195           return new SCEVCouldNotCompute();  // Something strange happened
2196         }
2197
2198         // If R1 was not in the range, then it is a good return value.  Make
2199         // sure that R1-1 WAS in the range though, just in case.
2200         Constant *NextVal =
2201           ConstantExpr::getSub(R1->getValue(),
2202                                ConstantInt::get(R1->getType(), 1));
2203         R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
2204         if (Range.contains(R1Val))
2205           return R1;
2206         return new SCEVCouldNotCompute();  // Something strange happened
2207       }
2208     }
2209   }
2210
2211   // Fallback, if this is a general polynomial, figure out the progression
2212   // through brute force: evaluate until we find an iteration that fails the
2213   // test.  This is likely to be slow, but getting an accurate trip count is
2214   // incredibly important, we will be able to simplify the exit test a lot, and
2215   // we are almost guaranteed to get a trip count in this case.
2216   ConstantInt *TestVal = ConstantInt::get(getType(), 0);
2217   ConstantInt *One     = ConstantInt::get(getType(), 1);
2218   ConstantInt *EndVal  = TestVal;  // Stop when we wrap around.
2219   do {
2220     ++NumBruteForceEvaluations;
2221     SCEVHandle Val = evaluateAtIteration(SCEVConstant::get(TestVal));
2222     if (!isa<SCEVConstant>(Val))  // This shouldn't happen.
2223       return new SCEVCouldNotCompute();
2224
2225     // Check to see if we found the value!
2226     if (!Range.contains(cast<SCEVConstant>(Val)->getValue()))
2227       return SCEVConstant::get(TestVal);
2228
2229     // Increment to test the next index.
2230     TestVal = cast<ConstantInt>(ConstantExpr::getAdd(TestVal, One));
2231   } while (TestVal != EndVal);
2232
2233   return new SCEVCouldNotCompute();
2234 }
2235
2236
2237
2238 //===----------------------------------------------------------------------===//
2239 //                   ScalarEvolution Class Implementation
2240 //===----------------------------------------------------------------------===//
2241
2242 bool ScalarEvolution::runOnFunction(Function &F) {
2243   Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>());
2244   return false;
2245 }
2246
2247 void ScalarEvolution::releaseMemory() {
2248   delete (ScalarEvolutionsImpl*)Impl;
2249   Impl = 0;
2250 }
2251
2252 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
2253   AU.setPreservesAll();
2254   AU.addRequiredID(LoopSimplifyID);
2255   AU.addRequiredTransitive<LoopInfo>();
2256 }
2257
2258 SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
2259   return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
2260 }
2261
2262 SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
2263   return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
2264 }
2265
2266 bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
2267   return !isa<SCEVCouldNotCompute>(getIterationCount(L));
2268 }
2269
2270 SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
2271   return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
2272 }
2273
2274 void ScalarEvolution::deleteInstructionFromRecords(Instruction *I) const {
2275   return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I);
2276 }
2277
2278
2279 /// shouldSubstituteIndVar - Return true if we should perform induction variable
2280 /// substitution for this variable.  This is a hack because we don't have a
2281 /// strength reduction pass yet.  When we do we will promote all vars, because
2282 /// we can strength reduce them later as desired.
2283 bool ScalarEvolution::shouldSubstituteIndVar(const SCEV *S) const {
2284   // Don't substitute high degree polynomials.
2285   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
2286     if (AddRec->getNumOperands() > 3) return false;
2287   return true;
2288 }
2289
2290
2291 static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
2292                           const Loop *L) {
2293   // Print all inner loops first
2294   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
2295     PrintLoopInfo(OS, SE, *I);
2296
2297   std::cerr << "Loop " << L->getHeader()->getName() << ": ";
2298
2299   std::vector<BasicBlock*> ExitBlocks;
2300   L->getExitBlocks(ExitBlocks);
2301   if (ExitBlocks.size() != 1)
2302     std::cerr << "<multiple exits> ";
2303
2304   if (SE->hasLoopInvariantIterationCount(L)) {
2305     std::cerr << *SE->getIterationCount(L) << " iterations! ";
2306   } else {
2307     std::cerr << "Unpredictable iteration count. ";
2308   }
2309
2310   std::cerr << "\n";
2311 }
2312
2313 void ScalarEvolution::print(std::ostream &OS) const {
2314   Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
2315   LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
2316
2317   OS << "Classifying expressions for: " << F.getName() << "\n";
2318   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
2319     if ((*I)->getType()->isInteger()) {
2320       OS << **I;
2321       OS << "  --> ";
2322       SCEVHandle SV = getSCEV(*I);
2323       SV->print(OS);
2324       OS << "\t\t";
2325
2326       if ((*I)->getType()->isIntegral()) {
2327         ConstantRange Bounds = SV->getValueRange();
2328         if (!Bounds.isFullSet())
2329           OS << "Bounds: " << Bounds << " ";
2330       }
2331
2332       if (const Loop *L = LI.getLoopFor((*I)->getParent())) {
2333         OS << "Exits: ";
2334         SCEVHandle ExitValue = getSCEVAtScope(*I, L->getParentLoop());
2335         if (isa<SCEVCouldNotCompute>(ExitValue)) {
2336           OS << "<<Unknown>>";
2337         } else {
2338           OS << *ExitValue;
2339         }
2340       }
2341
2342
2343       OS << "\n";
2344     }
2345
2346   OS << "Determining loop execution counts for: " << F.getName() << "\n";
2347   for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
2348     PrintLoopInfo(OS, this, *I);
2349 }
2350
2351 //===----------------------------------------------------------------------===//
2352 //                ScalarEvolutionRewriter Class Implementation
2353 //===----------------------------------------------------------------------===//
2354
2355 Value *ScalarEvolutionRewriter::
2356 GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty) {
2357   assert((Ty->isInteger() || Ty->isFloatingPoint()) &&
2358          "Can only insert integer or floating point induction variables!");
2359
2360   // Check to see if we already inserted one.
2361   SCEVHandle H = SCEVAddRecExpr::get(getIntegerSCEV(0, Ty),
2362                                      getIntegerSCEV(1, Ty), L);
2363   return ExpandCodeFor(H, 0, Ty);
2364 }
2365
2366 /// ExpandCodeFor - Insert code to directly compute the specified SCEV
2367 /// expression into the program.  The inserted code is inserted into the
2368 /// specified block.
2369 Value *ScalarEvolutionRewriter::ExpandCodeFor(SCEVHandle SH,
2370                                               Instruction *InsertPt,
2371                                               const Type *Ty) {
2372   std::map<SCEVHandle, Value*>::iterator ExistVal =InsertedExpressions.find(SH);
2373   Value *V;
2374   if (ExistVal != InsertedExpressions.end()) {
2375     V = ExistVal->second;
2376   } else {
2377     // Ask the recurrence object to expand the code for itself.
2378     V = SH->expandCodeFor(*this, InsertPt);
2379     // Cache the generated result.
2380     InsertedExpressions.insert(std::make_pair(SH, V));
2381   }
2382
2383   if (Ty == 0 || V->getType() == Ty)
2384     return V;
2385   if (Constant *C = dyn_cast<Constant>(V))
2386     return ConstantExpr::getCast(C, Ty);
2387   else if (Instruction *I = dyn_cast<Instruction>(V)) {
2388     // Check to see if there is already a cast.  If there is, use it.
2389     for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
2390          UI != E; ++UI) {
2391       if ((*UI)->getType() == Ty)
2392         if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) {
2393           BasicBlock::iterator It = I; ++It;
2394           while (isa<PHINode>(It)) ++It;
2395           if (It != BasicBlock::iterator(CI)) {
2396             // Splice the cast immediately after the operand in question.
2397             I->getParent()->getInstList().splice(It,
2398                                                  CI->getParent()->getInstList(),
2399                                                  CI);
2400           }
2401           return CI;
2402         }
2403     }
2404     BasicBlock::iterator IP = I; ++IP;
2405     if (InvokeInst *II = dyn_cast<InvokeInst>(I))
2406       IP = II->getNormalDest()->begin();
2407     while (isa<PHINode>(IP)) ++IP;
2408     return new CastInst(V, Ty, V->getName(), IP);
2409   } else {
2410     // FIXME: check to see if there is already a cast!
2411     return new CastInst(V, Ty, V->getName(), InsertPt);
2412   }
2413 }