lib/Analysis/ScalarEvolution.cpp

   1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the implementation of the scalar evolution analysis
  11 // engine, which is used primarily to analyze expressions involving induction
  12 // variables in loops.
  13 //
  14 // There are several aspects to this library.  First is the representation of
  15 // scalar expressions, which are represented as subclasses of the SCEV class.
  16 // These classes are used to represent certain types of subexpressions that we
  17 // can handle.  These classes are reference counted, managed by the SCEVHandle
  18 // class.  We only create one SCEV of a particular shape, so pointer-comparisons
  19 // for equality are legal.
  20 //
  21 // One important aspect of the SCEV objects is that they are never cyclic, even
  22 // if there is a cycle in the dataflow for an expression (ie, a PHI node).  If
  23 // the PHI node is one of the idioms that we can represent (e.g., a polynomial
  24 // recurrence) then we represent it directly as a recurrence node, otherwise we
  25 // represent it as a SCEVUnknown node.
  26 //
  27 // In addition to being able to represent expressions of various types, we also
  28 // have folders that are used to build the *canonical* representation for a
  29 // particular expression.  These folders are capable of using a variety of
  30 // rewrite rules to simplify the expressions.
  31 //
  32 // Once the folders are defined, we can implement the more interesting
  33 // higher-level code, such as the code that recognizes PHI nodes of various
  34 // types, computes the execution count of a loop, etc.
  35 //
  36 // TODO: We should use these routines and value representations to implement
  37 // dependence analysis!
  38 //
  39 //===----------------------------------------------------------------------===//
  40 //
  41 // There are several good references for the techniques used in this analysis.
  42 //
  43 //  Chains of recurrences -- a method to expedite the evaluation
  44 //  of closed-form functions
  45 //  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
  46 //
  47 //  On computational properties of chains of recurrences
  48 //  Eugene V. Zima
  49 //
  50 //  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
  51 //  Robert A. van Engelen
  52 //
  53 //  Efficient Symbolic Analysis for Optimizing Compilers
  54 //  Robert A. van Engelen
  55 //
  56 //  Using the chains of recurrences algebra for data dependence testing and
  57 //  induction variable substitution
  58 //  MS Thesis, Johnie Birch
  59 //
  60 //===----------------------------------------------------------------------===//
  61
  62 #define DEBUG_TYPE "scalar-evolution"
  63 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  64 #include "llvm/Constants.h"
  65 #include "llvm/DerivedTypes.h"
  66 #include "llvm/GlobalVariable.h"
  67 #include "llvm/Instructions.h"
  68 #include "llvm/Analysis/ConstantFolding.h"
  69 #include "llvm/Analysis/LoopInfo.h"
  70 #include "llvm/Assembly/Writer.h"
  71 #include "llvm/Transforms/Scalar.h"
  72 #include "llvm/Support/CFG.h"
  73 #include "llvm/Support/CommandLine.h"
  74 #include "llvm/Support/Compiler.h"
  75 #include "llvm/Support/ConstantRange.h"
  76 #include "llvm/Support/InstIterator.h"
  77 #include "llvm/Support/ManagedStatic.h"
  78 #include "llvm/Support/MathExtras.h"
  79 #include "llvm/Support/Streams.h"
  80 #include "llvm/ADT/Statistic.h"
  81 #include <ostream>
  82 #include <algorithm>
  83 #include <cmath>
  84 using namespace llvm;
  85
  86 STATISTIC(NumBruteForceEvaluations,
  87           "Number of brute force evaluations needed to "
  88           "calculate high-order polynomial exit values");
  89 STATISTIC(NumArrayLenItCounts,
  90           "Number of trip counts computed with array length");
  91 STATISTIC(NumTripCountsComputed,
  92           "Number of loops with predictable loop counts");
  93 STATISTIC(NumTripCountsNotComputed,
  94           "Number of loops without predictable loop counts");
  95 STATISTIC(NumBruteForceTripCountsComputed,
  96           "Number of loops with trip counts computed by force");
  97
  98 cl::opt<unsigned>
  99 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
 100                         cl::desc("Maximum number of iterations SCEV will "
 101                                  "symbolically execute a constant derived loop"),
 102                         cl::init(100));
 103
 104 namespace {
 105   RegisterPass<ScalarEvolution>
 106   R("scalar-evolution", "Scalar Evolution Analysis");
 107 }
 108 char ScalarEvolution::ID = 0;
 109
 110 //===----------------------------------------------------------------------===//
 111 //                           SCEV class definitions
 112 //===----------------------------------------------------------------------===//
 113
 114 //===----------------------------------------------------------------------===//
 115 // Implementation of the SCEV class.
 116 //
 117 SCEV::~SCEV() {}
 118 void SCEV::dump() const {
 119   print(cerr);
 120 }
 121
 122 /// getValueRange - Return the tightest constant bounds that this value is
 123 /// known to have.  This method is only valid on integer SCEV objects.
 124 ConstantRange SCEV::getValueRange() const {
 125   const Type *Ty = getType();
 126   assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!");
 127   // Default to a full range if no better information is available.
 128   return ConstantRange(getBitWidth());
 129 }
 130
 131 uint32_t SCEV::getBitWidth() const {
 132   if (const IntegerType* ITy = dyn_cast<IntegerType>(getType()))
 133     return ITy->getBitWidth();
 134   return 0;
 135 }
 136
 137
 138 SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
 139
 140 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
 141   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 142   return false;
 143 }
 144
 145 const Type *SCEVCouldNotCompute::getType() const {
 146   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 147   return 0;
 148 }
 149
 150 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
 151   assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
 152   return false;
 153 }
 154
 155 SCEVHandle SCEVCouldNotCompute::
 156 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 157                                   const SCEVHandle &Conc,
 158                                   ScalarEvolution &SE) const {
 159   return this;
 160 }
 161
 162 void SCEVCouldNotCompute::print(std::ostream &OS) const {
 163   OS << "***COULDNOTCOMPUTE***";
 164 }
 165
 166 bool SCEVCouldNotCompute::classof(const SCEV *S) {
 167   return S->getSCEVType() == scCouldNotCompute;
 168 }
 169
 170
 171 // SCEVConstants - Only allow the creation of one SCEVConstant for any
 172 // particular value.  Don't use a SCEVHandle here, or else the object will
 173 // never be deleted!
 174 static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants;
 175
 176
 177 SCEVConstant::~SCEVConstant() {
 178   SCEVConstants->erase(V);
 179 }
 180
 181 SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
 182   SCEVConstant *&R = (*SCEVConstants)[V];
 183   if (R == 0) R = new SCEVConstant(V);
 184   return R;
 185 }
 186
 187 SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
 188   return getConstant(ConstantInt::get(Val));
 189 }
 190
 191 ConstantRange SCEVConstant::getValueRange() const {
 192   return ConstantRange(V->getValue());
 193 }
 194
 195 const Type *SCEVConstant::getType() const { return V->getType(); }
 196
 197 void SCEVConstant::print(std::ostream &OS) const {
 198   WriteAsOperand(OS, V, false);
 199 }
 200
 201 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
 202 // particular input.  Don't use a SCEVHandle here, or else the object will
 203 // never be deleted!
 204 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
 205                      SCEVTruncateExpr*> > SCEVTruncates;
 206
 207 SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
 208   : SCEV(scTruncate), Op(op), Ty(ty) {
 209   assert(Op->getType()->isInteger() && Ty->isInteger() &&
 210          "Cannot truncate non-integer value!");
 211   assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()
 212          && "This is not a truncating conversion!");
 213 }
 214
 215 SCEVTruncateExpr::~SCEVTruncateExpr() {
 216   SCEVTruncates->erase(std::make_pair(Op, Ty));
 217 }
 218
 219 ConstantRange SCEVTruncateExpr::getValueRange() const {
 220   return getOperand()->getValueRange().truncate(getBitWidth());
 221 }
 222
 223 void SCEVTruncateExpr::print(std::ostream &OS) const {
 224   OS << "(truncate " << *Op << " to " << *Ty << ")";
 225 }
 226
 227 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
 228 // particular input.  Don't use a SCEVHandle here, or else the object will never
 229 // be deleted!
 230 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
 231                      SCEVZeroExtendExpr*> > SCEVZeroExtends;
 232
 233 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
 234   : SCEV(scZeroExtend), Op(op), Ty(ty) {
 235   assert(Op->getType()->isInteger() && Ty->isInteger() &&
 236          "Cannot zero extend non-integer value!");
 237   assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
 238          && "This is not an extending conversion!");
 239 }
 240
 241 SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
 242   SCEVZeroExtends->erase(std::make_pair(Op, Ty));
 243 }
 244
 245 ConstantRange SCEVZeroExtendExpr::getValueRange() const {
 246   return getOperand()->getValueRange().zeroExtend(getBitWidth());
 247 }
 248
 249 void SCEVZeroExtendExpr::print(std::ostream &OS) const {
 250   OS << "(zeroextend " << *Op << " to " << *Ty << ")";
 251 }
 252
 253 // SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
 254 // particular input.  Don't use a SCEVHandle here, or else the object will never
 255 // be deleted!
 256 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
 257                      SCEVSignExtendExpr*> > SCEVSignExtends;
 258
 259 SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
 260   : SCEV(scSignExtend), Op(op), Ty(ty) {
 261   assert(Op->getType()->isInteger() && Ty->isInteger() &&
 262          "Cannot sign extend non-integer value!");
 263   assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
 264          && "This is not an extending conversion!");
 265 }
 266
 267 SCEVSignExtendExpr::~SCEVSignExtendExpr() {
 268   SCEVSignExtends->erase(std::make_pair(Op, Ty));
 269 }
 270
 271 ConstantRange SCEVSignExtendExpr::getValueRange() const {
 272   return getOperand()->getValueRange().signExtend(getBitWidth());
 273 }
 274
 275 void SCEVSignExtendExpr::print(std::ostream &OS) const {
 276   OS << "(signextend " << *Op << " to " << *Ty << ")";
 277 }
 278
 279 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
 280 // particular input.  Don't use a SCEVHandle here, or else the object will never
 281 // be deleted!
 282 static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
 283                      SCEVCommutativeExpr*> > SCEVCommExprs;
 284
 285 SCEVCommutativeExpr::~SCEVCommutativeExpr() {
 286   SCEVCommExprs->erase(std::make_pair(getSCEVType(),
 287                                       std::vector<SCEV*>(Operands.begin(),
 288                                                          Operands.end())));
 289 }
 290
 291 void SCEVCommutativeExpr::print(std::ostream &OS) const {
 292   assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
 293   const char *OpStr = getOperationStr();
 294   OS << "(" << *Operands[0];
 295   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 296     OS << OpStr << *Operands[i];
 297   OS << ")";
 298 }
 299
 300 SCEVHandle SCEVCommutativeExpr::
 301 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 302                                   const SCEVHandle &Conc,
 303                                   ScalarEvolution &SE) const {
 304   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 305     SCEVHandle H =
 306       getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 307     if (H != getOperand(i)) {
 308       std::vector<SCEVHandle> NewOps;
 309       NewOps.reserve(getNumOperands());
 310       for (unsigned j = 0; j != i; ++j)
 311         NewOps.push_back(getOperand(j));
 312       NewOps.push_back(H);
 313       for (++i; i != e; ++i)
 314         NewOps.push_back(getOperand(i)->
 315                          replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
 316
 317       if (isa<SCEVAddExpr>(this))
 318         return SE.getAddExpr(NewOps);
 319       else if (isa<SCEVMulExpr>(this))
 320         return SE.getMulExpr(NewOps);
 321       else if (isa<SCEVSMaxExpr>(this))
 322         return SE.getSMaxExpr(NewOps);
 323       else if (isa<SCEVUMaxExpr>(this))
 324         return SE.getUMaxExpr(NewOps);
 325       else
 326         assert(0 && "Unknown commutative expr!");
 327     }
 328   }
 329   return this;
 330 }
 331
 332
 333 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
 334 // input.  Don't use a SCEVHandle here, or else the object will never be
 335 // deleted!
 336 static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
 337                      SCEVUDivExpr*> > SCEVUDivs;
 338
 339 SCEVUDivExpr::~SCEVUDivExpr() {
 340   SCEVUDivs->erase(std::make_pair(LHS, RHS));
 341 }
 342
 343 void SCEVUDivExpr::print(std::ostream &OS) const {
 344   OS << "(" << *LHS << " /u " << *RHS << ")";
 345 }
 346
 347 const Type *SCEVUDivExpr::getType() const {
 348   return LHS->getType();
 349 }
 350
 351 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
 352 // particular input.  Don't use a SCEVHandle here, or else the object will never
 353 // be deleted!
 354 static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
 355                      SCEVAddRecExpr*> > SCEVAddRecExprs;
 356
 357 SCEVAddRecExpr::~SCEVAddRecExpr() {
 358   SCEVAddRecExprs->erase(std::make_pair(L,
 359                                         std::vector<SCEV*>(Operands.begin(),
 360                                                            Operands.end())));
 361 }
 362
 363 SCEVHandle SCEVAddRecExpr::
 364 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 365                                   const SCEVHandle &Conc,
 366                                   ScalarEvolution &SE) const {
 367   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 368     SCEVHandle H =
 369       getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 370     if (H != getOperand(i)) {
 371       std::vector<SCEVHandle> NewOps;
 372       NewOps.reserve(getNumOperands());
 373       for (unsigned j = 0; j != i; ++j)
 374         NewOps.push_back(getOperand(j));
 375       NewOps.push_back(H);
 376       for (++i; i != e; ++i)
 377         NewOps.push_back(getOperand(i)->
 378                          replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
 379
 380       return SE.getAddRecExpr(NewOps, L);
 381     }
 382   }
 383   return this;
 384 }
 385
 386
 387 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
 388   // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
 389   // contain L and if the start is invariant.
 390   return !QueryLoop->contains(L->getHeader()) &&
 391          getOperand(0)->isLoopInvariant(QueryLoop);
 392 }
 393
 394
 395 void SCEVAddRecExpr::print(std::ostream &OS) const {
 396   OS << "{" << *Operands[0];
 397   for (unsigned i = 1, e = Operands.size(); i != e; ++i)
 398     OS << ",+," << *Operands[i];
 399   OS << "}<" << L->getHeader()->getName() + ">";
 400 }
 401
 402 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
 403 // value.  Don't use a SCEVHandle here, or else the object will never be
 404 // deleted!
 405 static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns;
 406
 407 SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); }
 408
 409 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
 410   // All non-instruction values are loop invariant.  All instructions are loop
 411   // invariant if they are not contained in the specified loop.
 412   if (Instruction *I = dyn_cast<Instruction>(V))
 413     return !L->contains(I->getParent());
 414   return true;
 415 }
 416
 417 const Type *SCEVUnknown::getType() const {
 418   return V->getType();
 419 }
 420
 421 void SCEVUnknown::print(std::ostream &OS) const {
 422   WriteAsOperand(OS, V, false);
 423 }
 424
 425 //===----------------------------------------------------------------------===//
 426 //                               SCEV Utilities
 427 //===----------------------------------------------------------------------===//
 428
 429 namespace {
 430   /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
 431   /// than the complexity of the RHS.  This comparator is used to canonicalize
 432   /// expressions.
 433   struct VISIBILITY_HIDDEN SCEVComplexityCompare {
 434     bool operator()(SCEV *LHS, SCEV *RHS) {
 435       return LHS->getSCEVType() < RHS->getSCEVType();
 436     }
 437   };
 438 }
 439
 440 /// GroupByComplexity - Given a list of SCEV objects, order them by their
 441 /// complexity, and group objects of the same complexity together by value.
 442 /// When this routine is finished, we know that any duplicates in the vector are
 443 /// consecutive and that complexity is monotonically increasing.
 444 ///
 445 /// Note that we go take special precautions to ensure that we get determinstic
 446 /// results from this routine.  In other words, we don't want the results of
 447 /// this to depend on where the addresses of various SCEV objects happened to
 448 /// land in memory.
 449 ///
 450 static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
 451   if (Ops.size() < 2) return;  // Noop
 452   if (Ops.size() == 2) {
 453     // This is the common case, which also happens to be trivially simple.
 454     // Special case it.
 455     if (Ops[0]->getSCEVType() > Ops[1]->getSCEVType())
 456       std::swap(Ops[0], Ops[1]);
 457     return;
 458   }
 459
 460   // Do the rough sort by complexity.
 461   std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
 462
 463   // Now that we are sorted by complexity, group elements of the same
 464   // complexity.  Note that this is, at worst, N^2, but the vector is likely to
 465   // be extremely short in practice.  Note that we take this approach because we
 466   // do not want to depend on the addresses of the objects we are grouping.
 467   for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
 468     SCEV *S = Ops[i];
 469     unsigned Complexity = S->getSCEVType();
 470
 471     // If there are any objects of the same complexity and same value as this
 472     // one, group them.
 473     for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
 474       if (Ops[j] == S) { // Found a duplicate.
 475         // Move it to immediately after i'th element.
 476         std::swap(Ops[i+1], Ops[j]);
 477         ++i;   // no need to rescan it.
 478         if (i == e-2) return;  // Done!
 479       }
 480     }
 481   }
 482 }
 483
 484
 485
 486 //===----------------------------------------------------------------------===//
 487 //                      Simple SCEV method implementations
 488 //===----------------------------------------------------------------------===//
 489
 490 /// getIntegerSCEV - Given an integer or FP type, create a constant for the
 491 /// specified signed integer value and return a SCEV for the constant.
 492 SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
 493   Constant *C;
 494   if (Val == 0)
 495     C = Constant::getNullValue(Ty);
 496   else if (Ty->isFloatingPoint())
 497     C = ConstantFP::get(Ty, APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
 498                             APFloat::IEEEdouble, Val));
 499   else
 500     C = ConstantInt::get(Ty, Val);
 501   return getUnknown(C);
 502 }
 503
 504 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
 505 /// input value to the specified type.  If the type must be extended, it is zero
 506 /// extended.
 507 static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty,
 508                                           ScalarEvolution &SE) {
 509   const Type *SrcTy = V->getType();
 510   assert(SrcTy->isInteger() && Ty->isInteger() &&
 511          "Cannot truncate or zero extend with non-integer arguments!");
 512   if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
 513     return V;  // No conversion
 514   if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
 515     return SE.getTruncateExpr(V, Ty);
 516   return SE.getZeroExtendExpr(V, Ty);
 517 }
 518
 519 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
 520 ///
 521 SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
 522   if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
 523     return getUnknown(ConstantExpr::getNeg(VC->getValue()));
 524
 525   return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
 526 }
 527
 528 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
 529 SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
 530   if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
 531     return getUnknown(ConstantExpr::getNot(VC->getValue()));
 532
 533   SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
 534   return getMinusSCEV(AllOnes, V);
 535 }
 536
 537 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
 538 ///
 539 SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
 540                                          const SCEVHandle &RHS) {
 541   // X - Y --> X + -Y
 542   return getAddExpr(LHS, getNegativeSCEV(RHS));
 543 }
 544
 545
 546 /// BinomialCoefficient - Compute BC(It, K).  The result is of the same type as
 547 /// It.  Assume, K > 0.
 548 static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
 549                                       ScalarEvolution &SE) {
 550   // We are using the following formula for BC(It, K):
 551   //
 552   //   BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
 553   //
 554   // Suppose, W is the bitwidth of It (and of the return value as well).  We
 555   // must be prepared for overflow.  Hence, we must assure that the result of
 556   // our computation is equal to the accurate one modulo 2^W.  Unfortunately,
 557   // division isn't safe in modular arithmetic.  This means we must perform the
 558   // whole computation accurately and then truncate the result to W bits.
 559   //
 560   // The dividend of the formula is a multiplication of K integers of bitwidth
 561   // W.  K*W bits suffice to compute it accurately.
 562   //
 563   // FIXME: We assume the divisor can be accurately computed using 16-bit
 564   // unsigned integer type. It is true up to K = 8 (AddRecs of length 9). In
 565   // future we may use APInt to use the minimum number of bits necessary to
 566   // compute it accurately.
 567   //
 568   // It is safe to use unsigned division here: the dividend is nonnegative and
 569   // the divisor is positive.
 570
 571   // Handle the simplest case efficiently.
 572   if (K == 1)
 573     return It;
 574
 575   assert(K < 9 && "We cannot handle such long AddRecs yet.");
 576
 577   // FIXME: A temporary hack to remove in future.  Arbitrary precision integers
 578   // aren't supported by the code generator yet.  For the dividend, the bitwidth
 579   // we use is the smallest power of 2 greater or equal to K*W and less or equal
 580   // to 64.  Note that setting the upper bound for bitwidth may still lead to
 581   // miscompilation in some cases.
 582   unsigned DividendBits = 1U << Log2_32_Ceil(K * It->getBitWidth());
 583   if (DividendBits > 64)
 584     DividendBits = 64;
 585 #if 0 // Waiting for the APInt support in the code generator...
 586   unsigned DividendBits = K * It->getBitWidth();
 587 #endif
 588
 589   const IntegerType *DividendTy = IntegerType::get(DividendBits);
 590   const SCEVHandle ExIt = SE.getZeroExtendExpr(It, DividendTy);
 591
 592   // The final number of bits we need to perform the division is the maximum of
 593   // dividend and divisor bitwidths.
 594   const IntegerType *DivisionTy =
 595     IntegerType::get(std::max(DividendBits, 16U));
 596
 597   // Compute K!  We know K >= 2 here.
 598   unsigned F = 2;
 599   for (unsigned i = 3; i <= K; ++i)
 600     F *= i;
 601   APInt Divisor(DivisionTy->getBitWidth(), F);
 602
 603   // Handle this case efficiently, it is common to have constant iteration
 604   // counts while computing loop exit values.
 605   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(ExIt)) {
 606     const APInt& N = SC->getValue()->getValue();
 607     APInt Dividend(N.getBitWidth(), 1);
 608     for (; K; --K)
 609       Dividend *= N-(K-1);
 610     if (DividendTy != DivisionTy)
 611       Dividend = Dividend.zext(DivisionTy->getBitWidth());
 612     return SE.getConstant(Dividend.udiv(Divisor).trunc(It->getBitWidth()));
 613   }
 614
 615   SCEVHandle Dividend = ExIt;
 616   for (unsigned i = 1; i != K; ++i)
 617     Dividend =
 618       SE.getMulExpr(Dividend,
 619                     SE.getMinusSCEV(ExIt, SE.getIntegerSCEV(i, DividendTy)));
 620   if (DividendTy != DivisionTy)
 621     Dividend = SE.getZeroExtendExpr(Dividend, DivisionTy);
 622   return
 623     SE.getTruncateExpr(SE.getUDivExpr(Dividend, SE.getConstant(Divisor)),
 624                        It->getType());
 625 }
 626
 627 /// evaluateAtIteration - Return the value of this chain of recurrences at
 628 /// the specified iteration number.  We can evaluate this recurrence by
 629 /// multiplying each element in the chain by the binomial coefficient
 630 /// corresponding to it.  In other words, we can evaluate {A,+,B,+,C,+,D} as:
 631 ///
 632 ///   A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
 633 ///
 634 /// where BC(It, k) stands for binomial coefficient.
 635 ///
 636 SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
 637                                                ScalarEvolution &SE) const {
 638   SCEVHandle Result = getStart();
 639   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
 640     // The computation is correct in the face of overflow provided that the
 641     // multiplication is performed _after_ the evaluation of the binomial
 642     // coefficient.
 643     SCEVHandle Val = SE.getMulExpr(getOperand(i),
 644                                    BinomialCoefficient(It, i, SE));
 645     Result = SE.getAddExpr(Result, Val);
 646   }
 647   return Result;
 648 }
 649
 650 //===----------------------------------------------------------------------===//
 651 //                    SCEV Expression folder implementations
 652 //===----------------------------------------------------------------------===//
 653
 654 SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) {
 655   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 656     return getUnknown(
 657         ConstantExpr::getTrunc(SC->getValue(), Ty));
 658
 659   // If the input value is a chrec scev made out of constants, truncate
 660   // all of the constants.
 661   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
 662     std::vector<SCEVHandle> Operands;
 663     for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
 664       // FIXME: This should allow truncation of other expression types!
 665       if (isa<SCEVConstant>(AddRec->getOperand(i)))
 666         Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
 667       else
 668         break;
 669     if (Operands.size() == AddRec->getNumOperands())
 670       return getAddRecExpr(Operands, AddRec->getLoop());
 671   }
 672
 673   SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
 674   if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
 675   return Result;
 676 }
 677
 678 SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) {
 679   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 680     return getUnknown(
 681         ConstantExpr::getZExt(SC->getValue(), Ty));
 682
 683   // FIXME: If the input value is a chrec scev, and we can prove that the value
 684   // did not overflow the old, smaller, value, we can zero extend all of the
 685   // operands (often constants).  This would allow analysis of something like
 686   // this:  for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
 687
 688   SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
 689   if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
 690   return Result;
 691 }
 692
 693 SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
 694   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
 695     return getUnknown(
 696         ConstantExpr::getSExt(SC->getValue(), Ty));
 697
 698   // FIXME: If the input value is a chrec scev, and we can prove that the value
 699   // did not overflow the old, smaller, value, we can sign extend all of the
 700   // operands (often constants).  This would allow analysis of something like
 701   // this:  for (signed char X = 0; X < 100; ++X) { int Y = X; }
 702
 703   SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
 704   if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
 705   return Result;
 706 }
 707
 708 // get - Get a canonical add expression, or something simpler if possible.
 709 SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
 710   assert(!Ops.empty() && "Cannot get empty add!");
 711   if (Ops.size() == 1) return Ops[0];
 712
 713   // Sort by complexity, this groups all similar expression types together.
 714   GroupByComplexity(Ops);
 715
 716   // If there are any constants, fold them together.
 717   unsigned Idx = 0;
 718   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 719     ++Idx;
 720     assert(Idx < Ops.size());
 721     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
 722       // We found two constants, fold them together!
 723       ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
 724                                            RHSC->getValue()->getValue());
 725       Ops[0] = getConstant(Fold);
 726       Ops.erase(Ops.begin()+1);  // Erase the folded element
 727       if (Ops.size() == 1) return Ops[0];
 728       LHSC = cast<SCEVConstant>(Ops[0]);
 729     }
 730
 731     // If we are left with a constant zero being added, strip it off.
 732     if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
 733       Ops.erase(Ops.begin());
 734       --Idx;
 735     }
 736   }
 737
 738   if (Ops.size() == 1) return Ops[0];
 739
 740   // Okay, check to see if the same value occurs in the operand list twice.  If
 741   // so, merge them together into an multiply expression.  Since we sorted the
 742   // list, these values are required to be adjacent.
 743   const Type *Ty = Ops[0]->getType();
 744   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
 745     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
 746       // Found a match, merge the two values into a multiply, and add any
 747       // remaining values to the result.
 748       SCEVHandle Two = getIntegerSCEV(2, Ty);
 749       SCEVHandle Mul = getMulExpr(Ops[i], Two);
 750       if (Ops.size() == 2)
 751         return Mul;
 752       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
 753       Ops.push_back(Mul);
 754       return getAddExpr(Ops);
 755     }
 756
 757   // Now we know the first non-constant operand.  Skip past any cast SCEVs.
 758   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
 759     ++Idx;
 760
 761   // If there are add operands they would be next.
 762   if (Idx < Ops.size()) {
 763     bool DeletedAdd = false;
 764     while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
 765       // If we have an add, expand the add operands onto the end of the operands
 766       // list.
 767       Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
 768       Ops.erase(Ops.begin()+Idx);
 769       DeletedAdd = true;
 770     }
 771
 772     // If we deleted at least one add, we added operands to the end of the list,
 773     // and they are not necessarily sorted.  Recurse to resort and resimplify
 774     // any operands we just aquired.
 775     if (DeletedAdd)
 776       return getAddExpr(Ops);
 777   }
 778
 779   // Skip over the add expression until we get to a multiply.
 780   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
 781     ++Idx;
 782
 783   // If we are adding something to a multiply expression, make sure the
 784   // something is not already an operand of the multiply.  If so, merge it into
 785   // the multiply.
 786   for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
 787     SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
 788     for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
 789       SCEV *MulOpSCEV = Mul->getOperand(MulOp);
 790       for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
 791         if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
 792           // Fold W + X + (X * Y * Z)  -->  W + (X * ((Y*Z)+1))
 793           SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
 794           if (Mul->getNumOperands() != 2) {
 795             // If the multiply has more than two operands, we must get the
 796             // Y*Z term.
 797             std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
 798             MulOps.erase(MulOps.begin()+MulOp);
 799             InnerMul = getMulExpr(MulOps);
 800           }
 801           SCEVHandle One = getIntegerSCEV(1, Ty);
 802           SCEVHandle AddOne = getAddExpr(InnerMul, One);
 803           SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
 804           if (Ops.size() == 2) return OuterMul;
 805           if (AddOp < Idx) {
 806             Ops.erase(Ops.begin()+AddOp);
 807             Ops.erase(Ops.begin()+Idx-1);
 808           } else {
 809             Ops.erase(Ops.begin()+Idx);
 810             Ops.erase(Ops.begin()+AddOp-1);
 811           }
 812           Ops.push_back(OuterMul);
 813           return getAddExpr(Ops);
 814         }
 815
 816       // Check this multiply against other multiplies being added together.
 817       for (unsigned OtherMulIdx = Idx+1;
 818            OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
 819            ++OtherMulIdx) {
 820         SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
 821         // If MulOp occurs in OtherMul, we can fold the two multiplies
 822         // together.
 823         for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
 824              OMulOp != e; ++OMulOp)
 825           if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
 826             // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
 827             SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
 828             if (Mul->getNumOperands() != 2) {
 829               std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
 830               MulOps.erase(MulOps.begin()+MulOp);
 831               InnerMul1 = getMulExpr(MulOps);
 832             }
 833             SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
 834             if (OtherMul->getNumOperands() != 2) {
 835               std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
 836                                              OtherMul->op_end());
 837               MulOps.erase(MulOps.begin()+OMulOp);
 838               InnerMul2 = getMulExpr(MulOps);
 839             }
 840             SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
 841             SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
 842             if (Ops.size() == 2) return OuterMul;
 843             Ops.erase(Ops.begin()+Idx);
 844             Ops.erase(Ops.begin()+OtherMulIdx-1);
 845             Ops.push_back(OuterMul);
 846             return getAddExpr(Ops);
 847           }
 848       }
 849     }
 850   }
 851
 852   // If there are any add recurrences in the operands list, see if any other
 853   // added values are loop invariant.  If so, we can fold them into the
 854   // recurrence.
 855   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
 856     ++Idx;
 857
 858   // Scan over all recurrences, trying to fold loop invariants into them.
 859   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
 860     // Scan all of the other operands to this add and add them to the vector if
 861     // they are loop invariant w.r.t. the recurrence.
 862     std::vector<SCEVHandle> LIOps;
 863     SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
 864     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
 865       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
 866         LIOps.push_back(Ops[i]);
 867         Ops.erase(Ops.begin()+i);
 868         --i; --e;
 869       }
 870
 871     // If we found some loop invariants, fold them into the recurrence.
 872     if (!LIOps.empty()) {
 873       //  NLI + LI + { Start,+,Step}  -->  NLI + { LI+Start,+,Step }
 874       LIOps.push_back(AddRec->getStart());
 875
 876       std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
 877       AddRecOps[0] = getAddExpr(LIOps);
 878
 879       SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
 880       // If all of the other operands were loop invariant, we are done.
 881       if (Ops.size() == 1) return NewRec;
 882
 883       // Otherwise, add the folded AddRec by the non-liv parts.
 884       for (unsigned i = 0;; ++i)
 885         if (Ops[i] == AddRec) {
 886           Ops[i] = NewRec;
 887           break;
 888         }
 889       return getAddExpr(Ops);
 890     }
 891
 892     // Okay, if there weren't any loop invariants to be folded, check to see if
 893     // there are multiple AddRec's with the same loop induction variable being
 894     // added together.  If so, we can fold them.
 895     for (unsigned OtherIdx = Idx+1;
 896          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
 897       if (OtherIdx != Idx) {
 898         SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
 899         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
 900           // Other + {A,+,B} + {C,+,D}  -->  Other + {A+C,+,B+D}
 901           std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
 902           for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
 903             if (i >= NewOps.size()) {
 904               NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
 905                             OtherAddRec->op_end());
 906               break;
 907             }
 908             NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
 909           }
 910           SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
 911
 912           if (Ops.size() == 2) return NewAddRec;
 913
 914           Ops.erase(Ops.begin()+Idx);
 915           Ops.erase(Ops.begin()+OtherIdx-1);
 916           Ops.push_back(NewAddRec);
 917           return getAddExpr(Ops);
 918         }
 919       }
 920
 921     // Otherwise couldn't fold anything into this recurrence.  Move onto the
 922     // next one.
 923   }
 924
 925   // Okay, it looks like we really DO need an add expr.  Check to see if we
 926   // already have one, otherwise create a new one.
 927   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
 928   SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
 929                                                                  SCEVOps)];
 930   if (Result == 0) Result = new SCEVAddExpr(Ops);
 931   return Result;
 932 }
 933
 934
 935 SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
 936   assert(!Ops.empty() && "Cannot get empty mul!");
 937
 938   // Sort by complexity, this groups all similar expression types together.
 939   GroupByComplexity(Ops);
 940
 941   // If there are any constants, fold them together.
 942   unsigned Idx = 0;
 943   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 944
 945     // C1*(C2+V) -> C1*C2 + C1*V
 946     if (Ops.size() == 2)
 947       if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
 948         if (Add->getNumOperands() == 2 &&
 949             isa<SCEVConstant>(Add->getOperand(0)))
 950           return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
 951                             getMulExpr(LHSC, Add->getOperand(1)));
 952
 953
 954     ++Idx;
 955     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
 956       // We found two constants, fold them together!
 957       ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
 958                                            RHSC->getValue()->getValue());
 959       Ops[0] = getConstant(Fold);
 960       Ops.erase(Ops.begin()+1);  // Erase the folded element
 961       if (Ops.size() == 1) return Ops[0];
 962       LHSC = cast<SCEVConstant>(Ops[0]);
 963     }
 964
 965     // If we are left with a constant one being multiplied, strip it off.
 966     if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
 967       Ops.erase(Ops.begin());
 968       --Idx;
 969     } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
 970       // If we have a multiply of zero, it will always be zero.
 971       return Ops[0];
 972     }
 973   }
 974
 975   // Skip over the add expression until we get to a multiply.
 976   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
 977     ++Idx;
 978
 979   if (Ops.size() == 1)
 980     return Ops[0];
 981
 982   // If there are mul operands inline them all into this expression.
 983   if (Idx < Ops.size()) {
 984     bool DeletedMul = false;
 985     while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
 986       // If we have an mul, expand the mul operands onto the end of the operands
 987       // list.
 988       Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
 989       Ops.erase(Ops.begin()+Idx);
 990       DeletedMul = true;
 991     }
 992
 993     // If we deleted at least one mul, we added operands to the end of the list,
 994     // and they are not necessarily sorted.  Recurse to resort and resimplify
 995     // any operands we just aquired.
 996     if (DeletedMul)
 997       return getMulExpr(Ops);
 998   }
 999
1000   // If there are any add recurrences in the operands list, see if any other
1001   // added values are loop invariant.  If so, we can fold them into the
1002   // recurrence.
1003   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
1004     ++Idx;
1005
1006   // Scan over all recurrences, trying to fold loop invariants into them.
1007   for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1008     // Scan all of the other operands to this mul and add them to the vector if
1009     // they are loop invariant w.r.t. the recurrence.
1010     std::vector<SCEVHandle> LIOps;
1011     SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
1012     for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1013       if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1014         LIOps.push_back(Ops[i]);
1015         Ops.erase(Ops.begin()+i);
1016         --i; --e;
1017       }
1018
1019     // If we found some loop invariants, fold them into the recurrence.
1020     if (!LIOps.empty()) {
1021       //  NLI * LI * { Start,+,Step}  -->  NLI * { LI*Start,+,LI*Step }
1022       std::vector<SCEVHandle> NewOps;
1023       NewOps.reserve(AddRec->getNumOperands());
1024       if (LIOps.size() == 1) {
1025         SCEV *Scale = LIOps[0];
1026         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
1027           NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
1028       } else {
1029         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
1030           std::vector<SCEVHandle> MulOps(LIOps);
1031           MulOps.push_back(AddRec->getOperand(i));
1032           NewOps.push_back(getMulExpr(MulOps));
1033         }
1034       }
1035
1036       SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
1037
1038       // If all of the other operands were loop invariant, we are done.
1039       if (Ops.size() == 1) return NewRec;
1040
1041       // Otherwise, multiply the folded AddRec by the non-liv parts.
1042       for (unsigned i = 0;; ++i)
1043         if (Ops[i] == AddRec) {
1044           Ops[i] = NewRec;
1045           break;
1046         }
1047       return getMulExpr(Ops);
1048     }
1049
1050     // Okay, if there weren't any loop invariants to be folded, check to see if
1051     // there are multiple AddRec's with the same loop induction variable being
1052     // multiplied together.  If so, we can fold them.
1053     for (unsigned OtherIdx = Idx+1;
1054          OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1055       if (OtherIdx != Idx) {
1056         SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1057         if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1058           // F * G  -->  {A,+,B} * {C,+,D}  -->  {A*C,+,F*D + G*B + B*D}
1059           SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
1060           SCEVHandle NewStart = getMulExpr(F->getStart(),
1061                                                  G->getStart());
1062           SCEVHandle B = F->getStepRecurrence(*this);
1063           SCEVHandle D = G->getStepRecurrence(*this);
1064           SCEVHandle NewStep = getAddExpr(getMulExpr(F, D),
1065                                           getMulExpr(G, B),
1066                                           getMulExpr(B, D));
1067           SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep,
1068                                                F->getLoop());
1069           if (Ops.size() == 2) return NewAddRec;
1070
1071           Ops.erase(Ops.begin()+Idx);
1072           Ops.erase(Ops.begin()+OtherIdx-1);
1073           Ops.push_back(NewAddRec);
1074           return getMulExpr(Ops);
1075         }
1076       }
1077
1078     // Otherwise couldn't fold anything into this recurrence.  Move onto the
1079     // next one.
1080   }
1081
1082   // Okay, it looks like we really DO need an mul expr.  Check to see if we
1083   // already have one, otherwise create a new one.
1084   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1085   SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
1086                                                                  SCEVOps)];
1087   if (Result == 0)
1088     Result = new SCEVMulExpr(Ops);
1089   return Result;
1090 }
1091
1092 SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
1093   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
1094     if (RHSC->getValue()->equalsInt(1))
1095       return LHS;                            // X udiv 1 --> x
1096
1097     if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1098       Constant *LHSCV = LHSC->getValue();
1099       Constant *RHSCV = RHSC->getValue();
1100       return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
1101     }
1102   }
1103
1104   // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
1105
1106   SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
1107   if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
1108   return Result;
1109 }
1110
1111
1112 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
1113 /// specified loop.  Simplify the expression as much as possible.
1114 SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
1115                                const SCEVHandle &Step, const Loop *L) {
1116   std::vector<SCEVHandle> Operands;
1117   Operands.push_back(Start);
1118   if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
1119     if (StepChrec->getLoop() == L) {
1120       Operands.insert(Operands.end(), StepChrec->op_begin(),
1121                       StepChrec->op_end());
1122       return getAddRecExpr(Operands, L);
1123     }
1124
1125   Operands.push_back(Step);
1126   return getAddRecExpr(Operands, L);
1127 }
1128
1129 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
1130 /// specified loop.  Simplify the expression as much as possible.
1131 SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
1132                                const Loop *L) {
1133   if (Operands.size() == 1) return Operands[0];
1134
1135   if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back()))
1136     if (StepC->getValue()->isZero()) {
1137       Operands.pop_back();
1138       return getAddRecExpr(Operands, L);             // { X,+,0 }  -->  X
1139     }
1140
1141   SCEVAddRecExpr *&Result =
1142     (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
1143                                                             Operands.end()))];
1144   if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
1145   return Result;
1146 }
1147
1148 SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
1149                                         const SCEVHandle &RHS) {
1150   std::vector<SCEVHandle> Ops;
1151   Ops.push_back(LHS);
1152   Ops.push_back(RHS);
1153   return getSMaxExpr(Ops);
1154 }
1155
1156 SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
1157   assert(!Ops.empty() && "Cannot get empty smax!");
1158   if (Ops.size() == 1) return Ops[0];
1159
1160   // Sort by complexity, this groups all similar expression types together.
1161   GroupByComplexity(Ops);
1162
1163   // If there are any constants, fold them together.
1164   unsigned Idx = 0;
1165   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1166     ++Idx;
1167     assert(Idx < Ops.size());
1168     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1169       // We found two constants, fold them together!
1170       ConstantInt *Fold = ConstantInt::get(
1171                               APIntOps::smax(LHSC->getValue()->getValue(),
1172                                              RHSC->getValue()->getValue()));
1173       Ops[0] = getConstant(Fold);
1174       Ops.erase(Ops.begin()+1);  // Erase the folded element
1175       if (Ops.size() == 1) return Ops[0];
1176       LHSC = cast<SCEVConstant>(Ops[0]);
1177     }
1178
1179     // If we are left with a constant -inf, strip it off.
1180     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
1181       Ops.erase(Ops.begin());
1182       --Idx;
1183     }
1184   }
1185
1186   if (Ops.size() == 1) return Ops[0];
1187
1188   // Find the first SMax
1189   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
1190     ++Idx;
1191
1192   // Check to see if one of the operands is an SMax. If so, expand its operands
1193   // onto our operand list, and recurse to simplify.
1194   if (Idx < Ops.size()) {
1195     bool DeletedSMax = false;
1196     while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
1197       Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
1198       Ops.erase(Ops.begin()+Idx);
1199       DeletedSMax = true;
1200     }
1201
1202     if (DeletedSMax)
1203       return getSMaxExpr(Ops);
1204   }
1205
1206   // Okay, check to see if the same value occurs in the operand list twice.  If
1207   // so, delete one.  Since we sorted the list, these values are required to
1208   // be adjacent.
1209   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1210     if (Ops[i] == Ops[i+1]) {      //  X smax Y smax Y  -->  X smax Y
1211       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1212       --i; --e;
1213     }
1214
1215   if (Ops.size() == 1) return Ops[0];
1216
1217   assert(!Ops.empty() && "Reduced smax down to nothing!");
1218
1219   // Okay, it looks like we really DO need an smax expr.  Check to see if we
1220   // already have one, otherwise create a new one.
1221   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1222   SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
1223                                                                  SCEVOps)];
1224   if (Result == 0) Result = new SCEVSMaxExpr(Ops);
1225   return Result;
1226 }
1227
1228 SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
1229                                         const SCEVHandle &RHS) {
1230   std::vector<SCEVHandle> Ops;
1231   Ops.push_back(LHS);
1232   Ops.push_back(RHS);
1233   return getUMaxExpr(Ops);
1234 }
1235
1236 SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
1237   assert(!Ops.empty() && "Cannot get empty umax!");
1238   if (Ops.size() == 1) return Ops[0];
1239
1240   // Sort by complexity, this groups all similar expression types together.
1241   GroupByComplexity(Ops);
1242
1243   // If there are any constants, fold them together.
1244   unsigned Idx = 0;
1245   if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1246     ++Idx;
1247     assert(Idx < Ops.size());
1248     while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1249       // We found two constants, fold them together!
1250       ConstantInt *Fold = ConstantInt::get(
1251                               APIntOps::umax(LHSC->getValue()->getValue(),
1252                                              RHSC->getValue()->getValue()));
1253       Ops[0] = getConstant(Fold);
1254       Ops.erase(Ops.begin()+1);  // Erase the folded element
1255       if (Ops.size() == 1) return Ops[0];
1256       LHSC = cast<SCEVConstant>(Ops[0]);
1257     }
1258
1259     // If we are left with a constant zero, strip it off.
1260     if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
1261       Ops.erase(Ops.begin());
1262       --Idx;
1263     }
1264   }
1265
1266   if (Ops.size() == 1) return Ops[0];
1267
1268   // Find the first UMax
1269   while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
1270     ++Idx;
1271
1272   // Check to see if one of the operands is a UMax. If so, expand its operands
1273   // onto our operand list, and recurse to simplify.
1274   if (Idx < Ops.size()) {
1275     bool DeletedUMax = false;
1276     while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
1277       Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
1278       Ops.erase(Ops.begin()+Idx);
1279       DeletedUMax = true;
1280     }
1281
1282     if (DeletedUMax)
1283       return getUMaxExpr(Ops);
1284   }
1285
1286   // Okay, check to see if the same value occurs in the operand list twice.  If
1287   // so, delete one.  Since we sorted the list, these values are required to
1288   // be adjacent.
1289   for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1290     if (Ops[i] == Ops[i+1]) {      //  X umax Y umax Y  -->  X umax Y
1291       Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1292       --i; --e;
1293     }
1294
1295   if (Ops.size() == 1) return Ops[0];
1296
1297   assert(!Ops.empty() && "Reduced umax down to nothing!");
1298
1299   // Okay, it looks like we really DO need a umax expr.  Check to see if we
1300   // already have one, otherwise create a new one.
1301   std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1302   SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
1303                                                                  SCEVOps)];
1304   if (Result == 0) Result = new SCEVUMaxExpr(Ops);
1305   return Result;
1306 }
1307
1308 SCEVHandle ScalarEvolution::getUnknown(Value *V) {
1309   if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
1310     return getConstant(CI);
1311   SCEVUnknown *&Result = (*SCEVUnknowns)[V];
1312   if (Result == 0) Result = new SCEVUnknown(V);
1313   return Result;
1314 }
1315
1316
1317 //===----------------------------------------------------------------------===//
1318 //             ScalarEvolutionsImpl Definition and Implementation
1319 //===----------------------------------------------------------------------===//
1320 //
1321 /// ScalarEvolutionsImpl - This class implements the main driver for the scalar
1322 /// evolution code.
1323 ///
1324 namespace {
1325   struct VISIBILITY_HIDDEN ScalarEvolutionsImpl {
1326     /// SE - A reference to the public ScalarEvolution object.
1327     ScalarEvolution &SE;
1328
1329     /// F - The function we are analyzing.
1330     ///
1331     Function &F;
1332
1333     /// LI - The loop information for the function we are currently analyzing.
1334     ///
1335     LoopInfo &LI;
1336
1337     /// UnknownValue - This SCEV is used to represent unknown trip counts and
1338     /// things.
1339     SCEVHandle UnknownValue;
1340
1341     /// Scalars - This is a cache of the scalars we have analyzed so far.
1342     ///
1343     std::map<Value*, SCEVHandle> Scalars;
1344
1345     /// IterationCounts - Cache the iteration count of the loops for this
1346     /// function as they are computed.
1347     std::map<const Loop*, SCEVHandle> IterationCounts;
1348
1349     /// ConstantEvolutionLoopExitValue - This map contains entries for all of
1350     /// the PHI instructions that we attempt to compute constant evolutions for.
1351     /// This allows us to avoid potentially expensive recomputation of these
1352     /// properties.  An instruction maps to null if we are unable to compute its
1353     /// exit value.
1354     std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
1355
1356   public:
1357     ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li)
1358       : SE(se), F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
1359
1360     /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1361     /// expression and create a new one.
1362     SCEVHandle getSCEV(Value *V);
1363
1364     /// hasSCEV - Return true if the SCEV for this value has already been
1365     /// computed.
1366     bool hasSCEV(Value *V) const {
1367       return Scalars.count(V);
1368     }
1369
1370     /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
1371     /// the specified value.
1372     void setSCEV(Value *V, const SCEVHandle &H) {
1373       bool isNew = Scalars.insert(std::make_pair(V, H)).second;
1374       assert(isNew && "This entry already existed!");
1375     }
1376
1377
1378     /// getSCEVAtScope - Compute the value of the specified expression within
1379     /// the indicated loop (which may be null to indicate in no loop).  If the
1380     /// expression cannot be evaluated, return UnknownValue itself.
1381     SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
1382
1383
1384     /// hasLoopInvariantIterationCount - Return true if the specified loop has
1385     /// an analyzable loop-invariant iteration count.
1386     bool hasLoopInvariantIterationCount(const Loop *L);
1387
1388     /// getIterationCount - If the specified loop has a predictable iteration
1389     /// count, return it.  Note that it is not valid to call this method on a
1390     /// loop without a loop-invariant iteration count.
1391     SCEVHandle getIterationCount(const Loop *L);
1392
1393     /// deleteValueFromRecords - This method should be called by the
1394     /// client before it removes a value from the program, to make sure
1395     /// that no dangling references are left around.
1396     void deleteValueFromRecords(Value *V);
1397
1398   private:
1399     /// createSCEV - We know that there is no SCEV for the specified value.
1400     /// Analyze the expression.
1401     SCEVHandle createSCEV(Value *V);
1402
1403     /// createNodeForPHI - Provide the special handling we need to analyze PHI
1404     /// SCEVs.
1405     SCEVHandle createNodeForPHI(PHINode *PN);
1406
1407     /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
1408     /// for the specified instruction and replaces any references to the
1409     /// symbolic value SymName with the specified value.  This is used during
1410     /// PHI resolution.
1411     void ReplaceSymbolicValueWithConcrete(Instruction *I,
1412                                           const SCEVHandle &SymName,
1413                                           const SCEVHandle &NewVal);
1414
1415     /// ComputeIterationCount - Compute the number of times the specified loop
1416     /// will iterate.
1417     SCEVHandle ComputeIterationCount(const Loop *L);
1418
1419     /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
1420     /// 'icmp op load X, cst', try to see if we can compute the trip count.
1421     SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI,
1422                                                         Constant *RHS,
1423                                                         const Loop *L,
1424                                                         ICmpInst::Predicate p);
1425
1426     /// ComputeIterationCountExhaustively - If the trip is known to execute a
1427     /// constant number of times (the condition evolves only from constants),
1428     /// try to evaluate a few iterations of the loop until we get the exit
1429     /// condition gets a value of ExitWhen (true or false).  If we cannot
1430     /// evaluate the trip count of the loop, return UnknownValue.
1431     SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond,
1432                                                  bool ExitWhen);
1433
1434     /// HowFarToZero - Return the number of times a backedge comparing the
1435     /// specified value to zero will execute.  If not computable, return
1436     /// UnknownValue.
1437     SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
1438
1439     /// HowFarToNonZero - Return the number of times a backedge checking the
1440     /// specified value for nonzero will execute.  If not computable, return
1441     /// UnknownValue.
1442     SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
1443
1444     /// HowManyLessThans - Return the number of times a backedge containing the
1445     /// specified less-than comparison will execute.  If not computable, return
1446     /// UnknownValue. isSigned specifies whether the less-than is signed.
1447     SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
1448                                 bool isSigned);
1449
1450     /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
1451     /// in the header of its containing loop, we know the loop executes a
1452     /// constant number of times, and the PHI node is just a recurrence
1453     /// involving constants, fold it.
1454     Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its,
1455                                                 const Loop *L);
1456   };
1457 }
1458
1459 //===----------------------------------------------------------------------===//
1460 //            Basic SCEV Analysis and PHI Idiom Recognition Code
1461 //
1462
1463 /// deleteValueFromRecords - This method should be called by the
1464 /// client before it removes an instruction from the program, to make sure
1465 /// that no dangling references are left around.
1466 void ScalarEvolutionsImpl::deleteValueFromRecords(Value *V) {
1467   SmallVector<Value *, 16> Worklist;
1468
1469   if (Scalars.erase(V)) {
1470     if (PHINode *PN = dyn_cast<PHINode>(V))
1471       ConstantEvolutionLoopExitValue.erase(PN);
1472     Worklist.push_back(V);
1473   }
1474
1475   while (!Worklist.empty()) {
1476     Value *VV = Worklist.back();
1477     Worklist.pop_back();
1478
1479     for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
1480          UI != UE; ++UI) {
1481       Instruction *Inst = cast<Instruction>(*UI);
1482       if (Scalars.erase(Inst)) {
1483         if (PHINode *PN = dyn_cast<PHINode>(VV))
1484           ConstantEvolutionLoopExitValue.erase(PN);
1485         Worklist.push_back(Inst);
1486       }
1487     }
1488   }
1489 }
1490
1491
1492 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1493 /// expression and create a new one.
1494 SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
1495   assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
1496
1497   std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
1498   if (I != Scalars.end()) return I->second;
1499   SCEVHandle S = createSCEV(V);
1500   Scalars.insert(std::make_pair(V, S));
1501   return S;
1502 }
1503
1504 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
1505 /// the specified instruction and replaces any references to the symbolic value
1506 /// SymName with the specified value.  This is used during PHI resolution.
1507 void ScalarEvolutionsImpl::
1508 ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
1509                                  const SCEVHandle &NewVal) {
1510   std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
1511   if (SI == Scalars.end()) return;
1512
1513   SCEVHandle NV =
1514     SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, SE);
1515   if (NV == SI->second) return;  // No change.
1516
1517   SI->second = NV;       // Update the scalars map!
1518
1519   // Any instruction values that use this instruction might also need to be
1520   // updated!
1521   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1522        UI != E; ++UI)
1523     ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
1524 }
1525
1526 /// createNodeForPHI - PHI nodes have two cases.  Either the PHI node exists in
1527 /// a loop header, making it a potential recurrence, or it doesn't.
1528 ///
1529 SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
1530   if (PN->getNumIncomingValues() == 2)  // The loops have been canonicalized.
1531     if (const Loop *L = LI.getLoopFor(PN->getParent()))
1532       if (L->getHeader() == PN->getParent()) {
1533         // If it lives in the loop header, it has two incoming values, one
1534         // from outside the loop, and one from inside.
1535         unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
1536         unsigned BackEdge     = IncomingEdge^1;
1537
1538         // While we are analyzing this PHI node, handle its value symbolically.
1539         SCEVHandle SymbolicName = SE.getUnknown(PN);
1540         assert(Scalars.find(PN) == Scalars.end() &&
1541                "PHI node already processed?");
1542         Scalars.insert(std::make_pair(PN, SymbolicName));
1543
1544         // Using this symbolic name for the PHI, analyze the value coming around
1545         // the back-edge.
1546         SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
1547
1548         // NOTE: If BEValue is loop invariant, we know that the PHI node just
1549         // has a special value for the first iteration of the loop.
1550
1551         // If the value coming around the backedge is an add with the symbolic
1552         // value we just inserted, then we found a simple induction variable!
1553         if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
1554           // If there is a single occurrence of the symbolic value, replace it
1555           // with a recurrence.
1556           unsigned FoundIndex = Add->getNumOperands();
1557           for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1558             if (Add->getOperand(i) == SymbolicName)
1559               if (FoundIndex == e) {
1560                 FoundIndex = i;
1561                 break;
1562               }
1563
1564           if (FoundIndex != Add->getNumOperands()) {
1565             // Create an add with everything but the specified operand.
1566             std::vector<SCEVHandle> Ops;
1567             for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1568               if (i != FoundIndex)
1569                 Ops.push_back(Add->getOperand(i));
1570             SCEVHandle Accum = SE.getAddExpr(Ops);
1571
1572             // This is not a valid addrec if the step amount is varying each
1573             // loop iteration, but is not itself an addrec in this loop.
1574             if (Accum->isLoopInvariant(L) ||
1575                 (isa<SCEVAddRecExpr>(Accum) &&
1576                  cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
1577               SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1578               SCEVHandle PHISCEV  = SE.getAddRecExpr(StartVal, Accum, L);
1579
1580               // Okay, for the entire analysis of this edge we assumed the PHI
1581               // to be symbolic.  We now need to go back and update all of the
1582               // entries for the scalars that use the PHI (except for the PHI
1583               // itself) to use the new analyzed value instead of the "symbolic"
1584               // value.
1585               ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
1586               return PHISCEV;
1587             }
1588           }
1589         } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
1590           // Otherwise, this could be a loop like this:
1591           //     i = 0;  for (j = 1; ..; ++j) { ....  i = j; }
1592           // In this case, j = {1,+,1}  and BEValue is j.
1593           // Because the other in-value of i (0) fits the evolution of BEValue
1594           // i really is an addrec evolution.
1595           if (AddRec->getLoop() == L && AddRec->isAffine()) {
1596             SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1597
1598             // If StartVal = j.start - j.stride, we can use StartVal as the
1599             // initial step of the addrec evolution.
1600             if (StartVal == SE.getMinusSCEV(AddRec->getOperand(0),
1601                                             AddRec->getOperand(1))) {
1602               SCEVHandle PHISCEV =
1603                  SE.getAddRecExpr(StartVal, AddRec->getOperand(1), L);
1604
1605               // Okay, for the entire analysis of this edge we assumed the PHI
1606               // to be symbolic.  We now need to go back and update all of the
1607               // entries for the scalars that use the PHI (except for the PHI
1608               // itself) to use the new analyzed value instead of the "symbolic"
1609               // value.
1610               ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
1611               return PHISCEV;
1612             }
1613           }
1614         }
1615
1616         return SymbolicName;
1617       }
1618
1619   // If it's not a loop phi, we can't handle it yet.
1620   return SE.getUnknown(PN);
1621 }
1622
1623 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
1624 /// guaranteed to end in (at every loop iteration).  It is, at the same time,
1625 /// the minimum number of times S is divisible by 2.  For example, given {4,+,8}
1626 /// it returns 2.  If S is guaranteed to be 0, it returns the bitwidth of S.
1627 static uint32_t GetMinTrailingZeros(SCEVHandle S) {
1628   if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
1629     return C->getValue()->getValue().countTrailingZeros();
1630
1631   if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
1632     return std::min(GetMinTrailingZeros(T->getOperand()), T->getBitWidth());
1633
1634   if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
1635     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1636     return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1637   }
1638
1639   if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
1640     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1641     return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1642   }
1643
1644   if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
1645     // The result is the min of all operands results.
1646     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1647     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1648       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1649     return MinOpRes;
1650   }
1651
1652   if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
1653     // The result is the sum of all operands results.
1654     uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
1655     uint32_t BitWidth = M->getBitWidth();
1656     for (unsigned i = 1, e = M->getNumOperands();
1657          SumOpRes != BitWidth && i != e; ++i)
1658       SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
1659                           BitWidth);
1660     return SumOpRes;
1661   }
1662
1663   if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
1664     // The result is the min of all operands results.
1665     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1666     for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1667       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1668     return MinOpRes;
1669   }
1670
1671   if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
1672     // The result is the min of all operands results.
1673     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1674     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1675       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1676     return MinOpRes;
1677   }
1678
1679   if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
1680     // The result is the min of all operands results.
1681     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1682     for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1683       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1684     return MinOpRes;
1685   }
1686
1687   // SCEVUDivExpr, SCEVUnknown
1688   return 0;
1689 }
1690
1691 /// createSCEV - We know that there is no SCEV for the specified value.
1692 /// Analyze the expression.
1693 ///
1694 SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
1695   if (!isa<IntegerType>(V->getType()))
1696     return SE.getUnknown(V);
1697
1698   if (Instruction *I = dyn_cast<Instruction>(V)) {
1699     switch (I->getOpcode()) {
1700     case Instruction::Add:
1701       return SE.getAddExpr(getSCEV(I->getOperand(0)),
1702                            getSCEV(I->getOperand(1)));
1703     case Instruction::Mul:
1704       return SE.getMulExpr(getSCEV(I->getOperand(0)),
1705                            getSCEV(I->getOperand(1)));
1706     case Instruction::UDiv:
1707       return SE.getUDivExpr(getSCEV(I->getOperand(0)),
1708                             getSCEV(I->getOperand(1)));
1709     case Instruction::Sub:
1710       return SE.getMinusSCEV(getSCEV(I->getOperand(0)),
1711                              getSCEV(I->getOperand(1)));
1712     case Instruction::Or:
1713       // If the RHS of the Or is a constant, we may have something like:
1714       // X*4+1 which got turned into X*4|1.  Handle this as an Add so loop
1715       // optimizations will transparently handle this case.
1716       //
1717       // In order for this transformation to be safe, the LHS must be of the
1718       // form X*(2^n) and the Or constant must be less than 2^n.
1719       if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
1720         SCEVHandle LHS = getSCEV(I->getOperand(0));
1721         const APInt &CIVal = CI->getValue();
1722         if (GetMinTrailingZeros(LHS) >=
1723             (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
1724           return SE.getAddExpr(LHS, getSCEV(I->getOperand(1)));
1725       }
1726       break;
1727     case Instruction::Xor:
1728       // If the RHS of the xor is a signbit, then this is just an add.
1729       // Instcombine turns add of signbit into xor as a strength reduction step.
1730       if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
1731         if (CI->getValue().isSignBit())
1732           return SE.getAddExpr(getSCEV(I->getOperand(0)),
1733                                getSCEV(I->getOperand(1)));
1734         else if (CI->isAllOnesValue())
1735           return SE.getNotSCEV(getSCEV(I->getOperand(0)));
1736       }
1737       break;
1738
1739     case Instruction::Shl:
1740       // Turn shift left of a constant amount into a multiply.
1741       if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
1742         uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1743         Constant *X = ConstantInt::get(
1744           APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
1745         return SE.getMulExpr(getSCEV(I->getOperand(0)), getSCEV(X));
1746       }
1747       break;
1748
1749     case Instruction::Trunc:
1750       return SE.getTruncateExpr(getSCEV(I->getOperand(0)), I->getType());
1751
1752     case Instruction::ZExt:
1753       return SE.getZeroExtendExpr(getSCEV(I->getOperand(0)), I->getType());
1754
1755     case Instruction::SExt:
1756       return SE.getSignExtendExpr(getSCEV(I->getOperand(0)), I->getType());
1757
1758     case Instruction::BitCast:
1759       // BitCasts are no-op casts so we just eliminate the cast.
1760       if (I->getType()->isInteger() &&
1761           I->getOperand(0)->getType()->isInteger())
1762         return getSCEV(I->getOperand(0));
1763       break;
1764
1765     case Instruction::PHI:
1766       return createNodeForPHI(cast<PHINode>(I));
1767
1768     case Instruction::Select:
1769       // This could be a smax or umax that was lowered earlier.
1770       // Try to recover it.
1771       if (ICmpInst *ICI = dyn_cast<ICmpInst>(I->getOperand(0))) {
1772         Value *LHS = ICI->getOperand(0);
1773         Value *RHS = ICI->getOperand(1);
1774         switch (ICI->getPredicate()) {
1775         case ICmpInst::ICMP_SLT:
1776         case ICmpInst::ICMP_SLE:
1777           std::swap(LHS, RHS);
1778           // fall through
1779         case ICmpInst::ICMP_SGT:
1780         case ICmpInst::ICMP_SGE:
1781           if (LHS == I->getOperand(1) && RHS == I->getOperand(2))
1782             return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
1783           else if (LHS == I->getOperand(2) && RHS == I->getOperand(1))
1784             // -smax(-x, -y) == smin(x, y).
1785             return SE.getNegativeSCEV(SE.getSMaxExpr(
1786                                           SE.getNegativeSCEV(getSCEV(LHS)),
1787                                           SE.getNegativeSCEV(getSCEV(RHS))));
1788           break;
1789         case ICmpInst::ICMP_ULT:
1790         case ICmpInst::ICMP_ULE:
1791           std::swap(LHS, RHS);
1792           // fall through
1793         case ICmpInst::ICMP_UGT:
1794         case ICmpInst::ICMP_UGE:
1795           if (LHS == I->getOperand(1) && RHS == I->getOperand(2))
1796             return SE.getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
1797           else if (LHS == I->getOperand(2) && RHS == I->getOperand(1))
1798             // ~umax(~x, ~y) == umin(x, y)
1799             return SE.getNotSCEV(SE.getUMaxExpr(SE.getNotSCEV(getSCEV(LHS)),
1800                                                 SE.getNotSCEV(getSCEV(RHS))));
1801           break;
1802         default:
1803           break;
1804         }
1805       }
1806
1807     default: // We cannot analyze this expression.
1808       break;
1809     }
1810   }
1811
1812   return SE.getUnknown(V);
1813 }
1814
1815
1816
1817 //===----------------------------------------------------------------------===//
1818 //                   Iteration Count Computation Code
1819 //
1820
1821 /// getIterationCount - If the specified loop has a predictable iteration
1822 /// count, return it.  Note that it is not valid to call this method on a
1823 /// loop without a loop-invariant iteration count.
1824 SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
1825   std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
1826   if (I == IterationCounts.end()) {
1827     SCEVHandle ItCount = ComputeIterationCount(L);
1828     I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
1829     if (ItCount != UnknownValue) {
1830       assert(ItCount->isLoopInvariant(L) &&
1831              "Computed trip count isn't loop invariant for loop!");
1832       ++NumTripCountsComputed;
1833     } else if (isa<PHINode>(L->getHeader()->begin())) {
1834       // Only count loops that have phi nodes as not being computable.
1835       ++NumTripCountsNotComputed;
1836     }
1837   }
1838   return I->second;
1839 }
1840
1841 /// ComputeIterationCount - Compute the number of times the specified loop
1842 /// will iterate.
1843 SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
1844   // If the loop has a non-one exit block count, we can't analyze it.
1845   SmallVector<BasicBlock*, 8> ExitBlocks;
1846   L->getExitBlocks(ExitBlocks);
1847   if (ExitBlocks.size() != 1) return UnknownValue;
1848
1849   // Okay, there is one exit block.  Try to find the condition that causes the
1850   // loop to be exited.
1851   BasicBlock *ExitBlock = ExitBlocks[0];
1852
1853   BasicBlock *ExitingBlock = 0;
1854   for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
1855        PI != E; ++PI)
1856     if (L->contains(*PI)) {
1857       if (ExitingBlock == 0)
1858         ExitingBlock = *PI;
1859       else
1860         return UnknownValue;   // More than one block exiting!
1861     }
1862   assert(ExitingBlock && "No exits from loop, something is broken!");
1863
1864   // Okay, we've computed the exiting block.  See what condition causes us to
1865   // exit.
1866   //
1867   // FIXME: we should be able to handle switch instructions (with a single exit)
1868   BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1869   if (ExitBr == 0) return UnknownValue;
1870   assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
1871
1872   // At this point, we know we have a conditional branch that determines whether
1873   // the loop is exited.  However, we don't know if the branch is executed each
1874   // time through the loop.  If not, then the execution count of the branch will
1875   // not be equal to the trip count of the loop.
1876   //
1877   // Currently we check for this by checking to see if the Exit branch goes to
1878   // the loop header.  If so, we know it will always execute the same number of
1879   // times as the loop.  We also handle the case where the exit block *is* the
1880   // loop header.  This is common for un-rotated loops.  More extensive analysis
1881   // could be done to handle more cases here.
1882   if (ExitBr->getSuccessor(0) != L->getHeader() &&
1883       ExitBr->getSuccessor(1) != L->getHeader() &&
1884       ExitBr->getParent() != L->getHeader())
1885     return UnknownValue;
1886
1887   ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
1888
1889   // If it's not an integer comparison then compute it the hard way.
1890   // Note that ICmpInst deals with pointer comparisons too so we must check
1891   // the type of the operand.
1892   if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
1893     return ComputeIterationCountExhaustively(L, ExitBr->getCondition(),
1894                                           ExitBr->getSuccessor(0) == ExitBlock);
1895
1896   // If the condition was exit on true, convert the condition to exit on false
1897   ICmpInst::Predicate Cond;
1898   if (ExitBr->getSuccessor(1) == ExitBlock)
1899     Cond = ExitCond->getPredicate();
1900   else
1901     Cond = ExitCond->getInversePredicate();
1902
1903   // Handle common loops like: for (X = "string"; *X; ++X)
1904   if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
1905     if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
1906       SCEVHandle ItCnt =
1907         ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
1908       if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
1909     }
1910
1911   SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
1912   SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
1913
1914   // Try to evaluate any dependencies out of the loop.
1915   SCEVHandle Tmp = getSCEVAtScope(LHS, L);
1916   if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
1917   Tmp = getSCEVAtScope(RHS, L);
1918   if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
1919
1920   // At this point, we would like to compute how many iterations of the
1921   // loop the predicate will return true for these inputs.
1922   if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
1923     // If there is a loop-invariant, force it into the RHS.
1924     std::swap(LHS, RHS);
1925     Cond = ICmpInst::getSwappedPredicate(Cond);
1926   }
1927
1928   // FIXME: think about handling pointer comparisons!  i.e.:
1929   // while (P != P+100) ++P;
1930
1931   // If we have a comparison of a chrec against a constant, try to use value
1932   // ranges to answer this query.
1933   if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
1934     if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
1935       if (AddRec->getLoop() == L) {
1936         // Form the comparison range using the constant of the correct type so
1937         // that the ConstantRange class knows to do a signed or unsigned
1938         // comparison.
1939         ConstantInt *CompVal = RHSC->getValue();
1940         const Type *RealTy = ExitCond->getOperand(0)->getType();
1941         CompVal = dyn_cast<ConstantInt>(
1942           ConstantExpr::getBitCast(CompVal, RealTy));
1943         if (CompVal) {
1944           // Form the constant range.
1945           ConstantRange CompRange(
1946               ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
1947
1948           SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, SE);
1949           if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
1950         }
1951       }
1952
1953   switch (Cond) {
1954   case ICmpInst::ICMP_NE: {                     // while (X != Y)
1955     // Convert to: while (X-Y != 0)
1956     SCEVHandle TC = HowFarToZero(SE.getMinusSCEV(LHS, RHS), L);
1957     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1958     break;
1959   }
1960   case ICmpInst::ICMP_EQ: {
1961     // Convert to: while (X-Y == 0)           // while (X == Y)
1962     SCEVHandle TC = HowFarToNonZero(SE.getMinusSCEV(LHS, RHS), L);
1963     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1964     break;
1965   }
1966   case ICmpInst::ICMP_SLT: {
1967     SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
1968     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1969     break;
1970   }
1971   case ICmpInst::ICMP_SGT: {
1972     SCEVHandle TC = HowManyLessThans(SE.getNegativeSCEV(LHS),
1973                                      SE.getNegativeSCEV(RHS), L, true);
1974     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1975     break;
1976   }
1977   case ICmpInst::ICMP_ULT: {
1978     SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false);
1979     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1980     break;
1981   }
1982   case ICmpInst::ICMP_UGT: {
1983     SCEVHandle TC = HowManyLessThans(SE.getNegativeSCEV(LHS),
1984                                      SE.getNegativeSCEV(RHS), L, false);
1985     if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1986     break;
1987   }
1988   default:
1989 #if 0
1990     cerr << "ComputeIterationCount ";
1991     if (ExitCond->getOperand(0)->getType()->isUnsigned())
1992       cerr << "[unsigned] ";
1993     cerr << *LHS << "   "
1994          << Instruction::getOpcodeName(Instruction::ICmp)
1995          << "   " << *RHS << "\n";
1996 #endif
1997     break;
1998   }
1999   return ComputeIterationCountExhaustively(L, ExitCond,
2000                                        ExitBr->getSuccessor(0) == ExitBlock);
2001 }
2002
2003 static ConstantInt *
2004 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
2005                                 ScalarEvolution &SE) {
2006   SCEVHandle InVal = SE.getConstant(C);
2007   SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE);
2008   assert(isa<SCEVConstant>(Val) &&
2009          "Evaluation of SCEV at constant didn't fold correctly?");
2010   return cast<SCEVConstant>(Val)->getValue();
2011 }
2012
2013 /// GetAddressedElementFromGlobal - Given a global variable with an initializer
2014 /// and a GEP expression (missing the pointer index) indexing into it, return
2015 /// the addressed element of the initializer or null if the index expression is
2016 /// invalid.
2017 static Constant *
2018 GetAddressedElementFromGlobal(GlobalVariable *GV,
2019                               const std::vector<ConstantInt*> &Indices) {
2020   Constant *Init = GV->getInitializer();
2021   for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
2022     uint64_t Idx = Indices[i]->getZExtValue();
2023     if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
2024       assert(Idx < CS->getNumOperands() && "Bad struct index!");
2025       Init = cast<Constant>(CS->getOperand(Idx));
2026     } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
2027       if (Idx >= CA->getNumOperands()) return 0;  // Bogus program
2028       Init = cast<Constant>(CA->getOperand(Idx));
2029     } else if (isa<ConstantAggregateZero>(Init)) {
2030       if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
2031         assert(Idx < STy->getNumElements() && "Bad struct index!");
2032         Init = Constant::getNullValue(STy->getElementType(Idx));
2033       } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
2034         if (Idx >= ATy->getNumElements()) return 0;  // Bogus program
2035         Init = Constant::getNullValue(ATy->getElementType());
2036       } else {
2037         assert(0 && "Unknown constant aggregate type!");
2038       }
2039       return 0;
2040     } else {
2041       return 0; // Unknown initializer type
2042     }
2043   }
2044   return Init;
2045 }
2046
2047 /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
2048 /// 'icmp op load X, cst', try to se if we can compute the trip count.
2049 SCEVHandle ScalarEvolutionsImpl::
2050 ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
2051                                          const Loop *L,
2052                                          ICmpInst::Predicate predicate) {
2053   if (LI->isVolatile()) return UnknownValue;
2054
2055   // Check to see if the loaded pointer is a getelementptr of a global.
2056   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
2057   if (!GEP) return UnknownValue;
2058
2059   // Make sure that it is really a constant global we are gepping, with an
2060   // initializer, and make sure the first IDX is really 0.
2061   GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
2062   if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
2063       GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
2064       !cast<Constant>(GEP->getOperand(1))->isNullValue())
2065     return UnknownValue;
2066
2067   // Okay, we allow one non-constant index into the GEP instruction.
2068   Value *VarIdx = 0;
2069   std::vector<ConstantInt*> Indexes;
2070   unsigned VarIdxNum = 0;
2071   for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
2072     if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
2073       Indexes.push_back(CI);
2074     } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
2075       if (VarIdx) return UnknownValue;  // Multiple non-constant idx's.
2076       VarIdx = GEP->getOperand(i);
2077       VarIdxNum = i-2;
2078       Indexes.push_back(0);
2079     }
2080
2081   // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
2082   // Check to see if X is a loop variant variable value now.
2083   SCEVHandle Idx = getSCEV(VarIdx);
2084   SCEVHandle Tmp = getSCEVAtScope(Idx, L);
2085   if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
2086
2087   // We can only recognize very limited forms of loop index expressions, in
2088   // particular, only affine AddRec's like {C1,+,C2}.
2089   SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
2090   if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
2091       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
2092       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
2093     return UnknownValue;
2094
2095   unsigned MaxSteps = MaxBruteForceIterations;
2096   for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
2097     ConstantInt *ItCst =
2098       ConstantInt::get(IdxExpr->getType(), IterationNum);
2099     ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, SE);
2100
2101     // Form the GEP offset.
2102     Indexes[VarIdxNum] = Val;
2103
2104     Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
2105     if (Result == 0) break;  // Cannot compute!
2106
2107     // Evaluate the condition for this iteration.
2108     Result = ConstantExpr::getICmp(predicate, Result, RHS);
2109     if (!isa<ConstantInt>(Result)) break;  // Couldn't decide for sure
2110     if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
2111 #if 0
2112       cerr << "\n***\n*** Computed loop count " << *ItCst
2113            << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
2114            << "***\n";
2115 #endif
2116       ++NumArrayLenItCounts;
2117       return SE.getConstant(ItCst);   // Found terminating iteration!
2118     }
2119   }
2120   return UnknownValue;
2121 }
2122
2123
2124 /// CanConstantFold - Return true if we can constant fold an instruction of the
2125 /// specified type, assuming that all operands were constants.
2126 static bool CanConstantFold(const Instruction *I) {
2127   if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
2128       isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
2129     return true;
2130
2131   if (const CallInst *CI = dyn_cast<CallInst>(I))
2132     if (const Function *F = CI->getCalledFunction())
2133       return canConstantFoldCallTo(F);
2134   return false;
2135 }
2136
2137 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
2138 /// in the loop that V is derived from.  We allow arbitrary operations along the
2139 /// way, but the operands of an operation must either be constants or a value
2140 /// derived from a constant PHI.  If this expression does not fit with these
2141 /// constraints, return null.
2142 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
2143   // If this is not an instruction, or if this is an instruction outside of the
2144   // loop, it can't be derived from a loop PHI.
2145   Instruction *I = dyn_cast<Instruction>(V);
2146   if (I == 0 || !L->contains(I->getParent())) return 0;
2147
2148   if (PHINode *PN = dyn_cast<PHINode>(I)) {
2149     if (L->getHeader() == I->getParent())
2150       return PN;
2151     else
2152       // We don't currently keep track of the control flow needed to evaluate
2153       // PHIs, so we cannot handle PHIs inside of loops.
2154       return 0;
2155   }
2156
2157   // If we won't be able to constant fold this expression even if the operands
2158   // are constants, return early.
2159   if (!CanConstantFold(I)) return 0;
2160
2161   // Otherwise, we can evaluate this instruction if all of its operands are
2162   // constant or derived from a PHI node themselves.
2163   PHINode *PHI = 0;
2164   for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
2165     if (!(isa<Constant>(I->getOperand(Op)) ||
2166           isa<GlobalValue>(I->getOperand(Op)))) {
2167       PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
2168       if (P == 0) return 0;  // Not evolving from PHI
2169       if (PHI == 0)
2170         PHI = P;
2171       else if (PHI != P)
2172         return 0;  // Evolving from multiple different PHIs.
2173     }
2174
2175   // This is a expression evolving from a constant PHI!
2176   return PHI;
2177 }
2178
2179 /// EvaluateExpression - Given an expression that passes the
2180 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
2181 /// in the loop has the value PHIVal.  If we can't fold this expression for some
2182 /// reason, return null.
2183 static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
2184   if (isa<PHINode>(V)) return PHIVal;
2185   if (Constant *C = dyn_cast<Constant>(V)) return C;
2186   Instruction *I = cast<Instruction>(V);
2187
2188   std::vector<Constant*> Operands;
2189   Operands.resize(I->getNumOperands());
2190
2191   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2192     Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
2193     if (Operands[i] == 0) return 0;
2194   }
2195
2196   if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2197     return ConstantFoldCompareInstOperands(CI->getPredicate(),
2198                                            &Operands[0], Operands.size());
2199   else
2200     return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2201                                     &Operands[0], Operands.size());
2202 }
2203
2204 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
2205 /// in the header of its containing loop, we know the loop executes a
2206 /// constant number of times, and the PHI node is just a recurrence
2207 /// involving constants, fold it.
2208 Constant *ScalarEvolutionsImpl::
2209 getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){
2210   std::map<PHINode*, Constant*>::iterator I =
2211     ConstantEvolutionLoopExitValue.find(PN);
2212   if (I != ConstantEvolutionLoopExitValue.end())
2213     return I->second;
2214
2215   if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations)))
2216     return ConstantEvolutionLoopExitValue[PN] = 0;  // Not going to evaluate it.
2217
2218   Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
2219
2220   // Since the loop is canonicalized, the PHI node must have two entries.  One
2221   // entry must be a constant (coming in from outside of the loop), and the
2222   // second must be derived from the same PHI.
2223   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2224   Constant *StartCST =
2225     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2226   if (StartCST == 0)
2227     return RetVal = 0;  // Must be a constant.
2228
2229   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2230   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2231   if (PN2 != PN)
2232     return RetVal = 0;  // Not derived from same PHI.
2233
2234   // Execute the loop symbolically to determine the exit value.
2235   if (Its.getActiveBits() >= 32)
2236     return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
2237
2238   unsigned NumIterations = Its.getZExtValue(); // must be in range
2239   unsigned IterationNum = 0;
2240   for (Constant *PHIVal = StartCST; ; ++IterationNum) {
2241     if (IterationNum == NumIterations)
2242       return RetVal = PHIVal;  // Got exit value!
2243
2244     // Compute the value of the PHI node for the next iteration.
2245     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2246     if (NextPHI == PHIVal)
2247       return RetVal = NextPHI;  // Stopped evolving!
2248     if (NextPHI == 0)
2249       return 0;        // Couldn't evaluate!
2250     PHIVal = NextPHI;
2251   }
2252 }
2253
2254 /// ComputeIterationCountExhaustively - If the trip is known to execute a
2255 /// constant number of times (the condition evolves only from constants),
2256 /// try to evaluate a few iterations of the loop until we get the exit
2257 /// condition gets a value of ExitWhen (true or false).  If we cannot
2258 /// evaluate the trip count of the loop, return UnknownValue.
2259 SCEVHandle ScalarEvolutionsImpl::
2260 ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
2261   PHINode *PN = getConstantEvolvingPHI(Cond, L);
2262   if (PN == 0) return UnknownValue;
2263
2264   // Since the loop is canonicalized, the PHI node must have two entries.  One
2265   // entry must be a constant (coming in from outside of the loop), and the
2266   // second must be derived from the same PHI.
2267   bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2268   Constant *StartCST =
2269     dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2270   if (StartCST == 0) return UnknownValue;  // Must be a constant.
2271
2272   Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2273   PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2274   if (PN2 != PN) return UnknownValue;  // Not derived from same PHI.
2275
2276   // Okay, we find a PHI node that defines the trip count of this loop.  Execute
2277   // the loop symbolically to determine when the condition gets a value of
2278   // "ExitWhen".
2279   unsigned IterationNum = 0;
2280   unsigned MaxIterations = MaxBruteForceIterations;   // Limit analysis.
2281   for (Constant *PHIVal = StartCST;
2282        IterationNum != MaxIterations; ++IterationNum) {
2283     ConstantInt *CondVal =
2284       dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
2285
2286     // Couldn't symbolically evaluate.
2287     if (!CondVal) return UnknownValue;
2288
2289     if (CondVal->getValue() == uint64_t(ExitWhen)) {
2290       ConstantEvolutionLoopExitValue[PN] = PHIVal;
2291       ++NumBruteForceTripCountsComputed;
2292       return SE.getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
2293     }
2294
2295     // Compute the value of the PHI node for the next iteration.
2296     Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2297     if (NextPHI == 0 || NextPHI == PHIVal)
2298       return UnknownValue;  // Couldn't evaluate or not making progress...
2299     PHIVal = NextPHI;
2300   }
2301
2302   // Too many iterations were needed to evaluate.
2303   return UnknownValue;
2304 }
2305
2306 /// getSCEVAtScope - Compute the value of the specified expression within the
2307 /// indicated loop (which may be null to indicate in no loop).  If the
2308 /// expression cannot be evaluated, return UnknownValue.
2309 SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
2310   // FIXME: this should be turned into a virtual method on SCEV!
2311
2312   if (isa<SCEVConstant>(V)) return V;
2313
2314   // If this instruction is evolved from a constant-evolving PHI, compute the
2315   // exit value from the loop without using SCEVs.
2316   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
2317     if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
2318       const Loop *LI = this->LI[I->getParent()];
2319       if (LI && LI->getParentLoop() == L)  // Looking for loop exit value.
2320         if (PHINode *PN = dyn_cast<PHINode>(I))
2321           if (PN->getParent() == LI->getHeader()) {
2322             // Okay, there is no closed form solution for the PHI node.  Check
2323             // to see if the loop that contains it has a known iteration count.
2324             // If so, we may be able to force computation of the exit value.
2325             SCEVHandle IterationCount = getIterationCount(LI);
2326             if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) {
2327               // Okay, we know how many times the containing loop executes.  If
2328               // this is a constant evolving PHI node, get the final value at
2329               // the specified iteration number.
2330               Constant *RV = getConstantEvolutionLoopExitValue(PN,
2331                                                     ICC->getValue()->getValue(),
2332                                                                LI);
2333               if (RV) return SE.getUnknown(RV);
2334             }
2335           }
2336
2337       // Okay, this is an expression that we cannot symbolically evaluate
2338       // into a SCEV.  Check to see if it's possible to symbolically evaluate
2339       // the arguments into constants, and if so, try to constant propagate the
2340       // result.  This is particularly useful for computing loop exit values.
2341       if (CanConstantFold(I)) {
2342         std::vector<Constant*> Operands;
2343         Operands.reserve(I->getNumOperands());
2344         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2345           Value *Op = I->getOperand(i);
2346           if (Constant *C = dyn_cast<Constant>(Op)) {
2347             Operands.push_back(C);
2348           } else {
2349             // If any of the operands is non-constant and if they are
2350             // non-integer, don't even try to analyze them with scev techniques.
2351             if (!isa<IntegerType>(Op->getType()))
2352               return V;
2353
2354             SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
2355             if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
2356               Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(),
2357                                                               Op->getType(),
2358                                                               false));
2359             else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
2360               if (Constant *C = dyn_cast<Constant>(SU->getValue()))
2361                 Operands.push_back(ConstantExpr::getIntegerCast(C,
2362                                                                 Op->getType(),
2363                                                                 false));
2364               else
2365                 return V;
2366             } else {
2367               return V;
2368             }
2369           }
2370         }
2371
2372         Constant *C;
2373         if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2374           C = ConstantFoldCompareInstOperands(CI->getPredicate(),
2375                                               &Operands[0], Operands.size());
2376         else
2377           C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2378                                        &Operands[0], Operands.size());
2379         return SE.getUnknown(C);
2380       }
2381     }
2382
2383     // This is some other type of SCEVUnknown, just return it.
2384     return V;
2385   }
2386
2387   if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
2388     // Avoid performing the look-up in the common case where the specified
2389     // expression has no loop-variant portions.
2390     for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
2391       SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2392       if (OpAtScope != Comm->getOperand(i)) {
2393         if (OpAtScope == UnknownValue) return UnknownValue;
2394         // Okay, at least one of these operands is loop variant but might be
2395         // foldable.  Build a new instance of the folded commutative expression.
2396         std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
2397         NewOps.push_back(OpAtScope);
2398
2399         for (++i; i != e; ++i) {
2400           OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2401           if (OpAtScope == UnknownValue) return UnknownValue;
2402           NewOps.push_back(OpAtScope);
2403         }
2404         if (isa<SCEVAddExpr>(Comm))
2405           return SE.getAddExpr(NewOps);
2406         if (isa<SCEVMulExpr>(Comm))
2407           return SE.getMulExpr(NewOps);
2408         if (isa<SCEVSMaxExpr>(Comm))
2409           return SE.getSMaxExpr(NewOps);
2410         if (isa<SCEVUMaxExpr>(Comm))
2411           return SE.getUMaxExpr(NewOps);
2412         assert(0 && "Unknown commutative SCEV type!");
2413       }
2414     }
2415     // If we got here, all operands are loop invariant.
2416     return Comm;
2417   }
2418
2419   if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
2420     SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
2421     if (LHS == UnknownValue) return LHS;
2422     SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
2423     if (RHS == UnknownValue) return RHS;
2424     if (LHS == Div->getLHS() && RHS == Div->getRHS())
2425       return Div;   // must be loop invariant
2426     return SE.getUDivExpr(LHS, RHS);
2427   }
2428
2429   // If this is a loop recurrence for a loop that does not contain L, then we
2430   // are dealing with the final value computed by the loop.
2431   if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
2432     if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
2433       // To evaluate this recurrence, we need to know how many times the AddRec
2434       // loop iterates.  Compute this now.
2435       SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
2436       if (IterationCount == UnknownValue) return UnknownValue;
2437       IterationCount = getTruncateOrZeroExtend(IterationCount,
2438                                                AddRec->getType(), SE);
2439
2440       // If the value is affine, simplify the expression evaluation to just
2441       // Start + Step*IterationCount.
2442       if (AddRec->isAffine())
2443         return SE.getAddExpr(AddRec->getStart(),
2444                              SE.getMulExpr(IterationCount,
2445                                            AddRec->getOperand(1)));
2446
2447       // Otherwise, evaluate it the hard way.
2448       return AddRec->evaluateAtIteration(IterationCount, SE);
2449     }
2450     return UnknownValue;
2451   }
2452
2453   //assert(0 && "Unknown SCEV type!");
2454   return UnknownValue;
2455 }
2456
2457
2458 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
2459 /// given quadratic chrec {L,+,M,+,N}.  This returns either the two roots (which
2460 /// might be the same) or two SCEVCouldNotCompute objects.
2461 ///
2462 static std::pair<SCEVHandle,SCEVHandle>
2463 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
2464   assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
2465   SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
2466   SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
2467   SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
2468
2469   // We currently can only solve this if the coefficients are constants.
2470   if (!LC || !MC || !NC) {
2471     SCEV *CNC = new SCEVCouldNotCompute();
2472     return std::make_pair(CNC, CNC);
2473   }
2474
2475   uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
2476   const APInt &L = LC->getValue()->getValue();
2477   const APInt &M = MC->getValue()->getValue();
2478   const APInt &N = NC->getValue()->getValue();
2479   APInt Two(BitWidth, 2);
2480   APInt Four(BitWidth, 4);
2481
2482   {
2483     using namespace APIntOps;
2484     const APInt& C = L;
2485     // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
2486     // The B coefficient is M-N/2
2487     APInt B(M);
2488     B -= sdiv(N,Two);
2489
2490     // The A coefficient is N/2
2491     APInt A(N.sdiv(Two));
2492
2493     // Compute the B^2-4ac term.
2494     APInt SqrtTerm(B);
2495     SqrtTerm *= B;
2496     SqrtTerm -= Four * (A * C);
2497
2498     // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
2499     // integer value or else APInt::sqrt() will assert.
2500     APInt SqrtVal(SqrtTerm.sqrt());
2501
2502     // Compute the two solutions for the quadratic formula.
2503     // The divisions must be performed as signed divisions.
2504     APInt NegB(-B);
2505     APInt TwoA( A << 1 );
2506     ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
2507     ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
2508
2509     return std::make_pair(SE.getConstant(Solution1),
2510                           SE.getConstant(Solution2));
2511     } // end APIntOps namespace
2512 }
2513
2514 /// HowFarToZero - Return the number of times a backedge comparing the specified
2515 /// value to zero will execute.  If not computable, return UnknownValue
2516 SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
2517   // If the value is a constant
2518   if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2519     // If the value is already zero, the branch will execute zero times.
2520     if (C->getValue()->isZero()) return C;
2521     return UnknownValue;  // Otherwise it will loop infinitely.
2522   }
2523
2524   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
2525   if (!AddRec || AddRec->getLoop() != L)
2526     return UnknownValue;
2527
2528   if (AddRec->isAffine()) {
2529     // If this is an affine expression the execution count of this branch is
2530     // equal to:
2531     //
2532     //     (0 - Start/Step)    iff   Start % Step == 0
2533     //
2534     // Get the initial value for the loop.
2535     SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
2536     if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue;
2537     SCEVHandle Step = AddRec->getOperand(1);
2538
2539     Step = getSCEVAtScope(Step, L->getParentLoop());
2540
2541     // Figure out if Start % Step == 0.
2542     // FIXME: We should add DivExpr and RemExpr operations to our AST.
2543     if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
2544       if (StepC->getValue()->equalsInt(1))      // N % 1 == 0
2545         return SE.getNegativeSCEV(Start);  // 0 - Start/1 == -Start
2546       if (StepC->getValue()->isAllOnesValue())  // N % -1 == 0
2547         return Start;                   // 0 - Start/-1 == Start
2548
2549       // Check to see if Start is divisible by SC with no remainder.
2550       if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) {
2551         ConstantInt *StartCC = StartC->getValue();
2552         Constant *StartNegC = ConstantExpr::getNeg(StartCC);
2553         Constant *Rem = ConstantExpr::getSRem(StartNegC, StepC->getValue());
2554         if (Rem->isNullValue()) {
2555           Constant *Result =ConstantExpr::getSDiv(StartNegC,StepC->getValue());
2556           return SE.getUnknown(Result);
2557         }
2558       }
2559     }
2560   } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
2561     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
2562     // the quadratic equation to solve it.
2563     std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec, SE);
2564     SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2565     SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2566     if (R1) {
2567 #if 0
2568       cerr << "HFTZ: " << *V << " - sol#1: " << *R1
2569            << "  sol#2: " << *R2 << "\n";
2570 #endif
2571       // Pick the smallest positive root value.
2572       if (ConstantInt *CB =
2573           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
2574                                    R1->getValue(), R2->getValue()))) {
2575         if (CB->getZExtValue() == false)
2576           std::swap(R1, R2);   // R1 is the minimum root now.
2577
2578         // We can only use this value if the chrec ends up with an exact zero
2579         // value at this index.  When solving for "X*X != 5", for example, we
2580         // should not accept a root of 2.
2581         SCEVHandle Val = AddRec->evaluateAtIteration(R1, SE);
2582         if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val))
2583           if (EvalVal->getValue()->isZero())
2584             return R1;  // We found a quadratic root!
2585       }
2586     }
2587   }
2588
2589   return UnknownValue;
2590 }
2591
2592 /// HowFarToNonZero - Return the number of times a backedge checking the
2593 /// specified value for nonzero will execute.  If not computable, return
2594 /// UnknownValue
2595 SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
2596   // Loops that look like: while (X == 0) are very strange indeed.  We don't
2597   // handle them yet except for the trivial case.  This could be expanded in the
2598   // future as needed.
2599
2600   // If the value is a constant, check to see if it is known to be non-zero
2601   // already.  If so, the backedge will execute zero times.
2602   if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2603     if (!C->getValue()->isNullValue())
2604       return SE.getIntegerSCEV(0, C->getType());
2605     return UnknownValue;  // Otherwise it will loop infinitely.
2606   }
2607
2608   // We could implement others, but I really doubt anyone writes loops like
2609   // this, and if they did, they would already be constant folded.
2610   return UnknownValue;
2611 }
2612
2613 /// HowManyLessThans - Return the number of times a backedge containing the
2614 /// specified less-than comparison will execute.  If not computable, return
2615 /// UnknownValue.
2616 SCEVHandle ScalarEvolutionsImpl::
2617 HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
2618   // Only handle:  "ADDREC < LoopInvariant".
2619   if (!RHS->isLoopInvariant(L)) return UnknownValue;
2620
2621   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
2622   if (!AddRec || AddRec->getLoop() != L)
2623     return UnknownValue;
2624
2625   if (AddRec->isAffine()) {
2626     // FORNOW: We only support unit strides.
2627     SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
2628     if (AddRec->getOperand(1) != One)
2629       return UnknownValue;
2630
2631     // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant
2632     // m.  So, we count the number of iterations in which {n,+,1} < m is true.
2633     // Note that we cannot simply return max(m-n,0) because it's not safe to
2634     // treat m-n as signed nor unsigned due to overflow possibility.
2635
2636     // First, we get the value of the LHS in the first iteration: n
2637     SCEVHandle Start = AddRec->getOperand(0);
2638
2639     // Then, we get the value of the LHS in the first iteration in which the
2640     // above condition doesn't hold.  This equals to max(m,n).
2641     SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
2642                               : SE.getUMaxExpr(RHS, Start);
2643
2644     // Finally, we subtract these two values to get the number of times the
2645     // backedge is executed: max(m,n)-n.
2646     return SE.getMinusSCEV(End, Start);
2647   }
2648
2649   return UnknownValue;
2650 }
2651
2652 /// getNumIterationsInRange - Return the number of iterations of this loop that
2653 /// produce values in the specified constant range.  Another way of looking at
2654 /// this is that it returns the first iteration number where the value is not in
2655 /// the condition, thus computing the exit count. If the iteration count can't
2656 /// be computed, an instance of SCEVCouldNotCompute is returned.
2657 SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
2658                                                    ScalarEvolution &SE) const {
2659   if (Range.isFullSet())  // Infinite loop.
2660     return new SCEVCouldNotCompute();
2661
2662   // If the start is a non-zero constant, shift the range to simplify things.
2663   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
2664     if (!SC->getValue()->isZero()) {
2665       std::vector<SCEVHandle> Operands(op_begin(), op_end());
2666       Operands[0] = SE.getIntegerSCEV(0, SC->getType());
2667       SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
2668       if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
2669         return ShiftedAddRec->getNumIterationsInRange(
2670                            Range.subtract(SC->getValue()->getValue()), SE);
2671       // This is strange and shouldn't happen.
2672       return new SCEVCouldNotCompute();
2673     }
2674
2675   // The only time we can solve this is when we have all constant indices.
2676   // Otherwise, we cannot determine the overflow conditions.
2677   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2678     if (!isa<SCEVConstant>(getOperand(i)))
2679       return new SCEVCouldNotCompute();
2680
2681
2682   // Okay at this point we know that all elements of the chrec are constants and
2683   // that the start element is zero.
2684
2685   // First check to see if the range contains zero.  If not, the first
2686   // iteration exits.
2687   if (!Range.contains(APInt(getBitWidth(),0)))
2688     return SE.getConstant(ConstantInt::get(getType(),0));
2689
2690   if (isAffine()) {
2691     // If this is an affine expression then we have this situation:
2692     //   Solve {0,+,A} in Range  ===  Ax in Range
2693
2694     // We know that zero is in the range.  If A is positive then we know that
2695     // the upper value of the range must be the first possible exit value.
2696     // If A is negative then the lower of the range is the last possible loop
2697     // value.  Also note that we already checked for a full range.
2698     APInt One(getBitWidth(),1);
2699     APInt A     = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
2700     APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
2701
2702     // The exit value should be (End+A)/A.
2703     APInt ExitVal = (End + A).udiv(A);
2704     ConstantInt *ExitValue = ConstantInt::get(ExitVal);
2705
2706     // Evaluate at the exit value.  If we really did fall out of the valid
2707     // range, then we computed our trip count, otherwise wrap around or other
2708     // things must have happened.
2709     ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
2710     if (Range.contains(Val->getValue()))
2711       return new SCEVCouldNotCompute();  // Something strange happened
2712
2713     // Ensure that the previous value is in the range.  This is a sanity check.
2714     assert(Range.contains(
2715            EvaluateConstantChrecAtConstant(this,
2716            ConstantInt::get(ExitVal - One), SE)->getValue()) &&
2717            "Linear scev computation is off in a bad way!");
2718     return SE.getConstant(ExitValue);
2719   } else if (isQuadratic()) {
2720     // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
2721     // quadratic equation to solve it.  To do this, we must frame our problem in
2722     // terms of figuring out when zero is crossed, instead of when
2723     // Range.getUpper() is crossed.
2724     std::vector<SCEVHandle> NewOps(op_begin(), op_end());
2725     NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
2726     SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
2727
2728     // Next, solve the constructed addrec
2729     std::pair<SCEVHandle,SCEVHandle> Roots =
2730       SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
2731     SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2732     SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2733     if (R1) {
2734       // Pick the smallest positive root value.
2735       if (ConstantInt *CB =
2736           dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
2737                                    R1->getValue(), R2->getValue()))) {
2738         if (CB->getZExtValue() == false)
2739           std::swap(R1, R2);   // R1 is the minimum root now.
2740
2741         // Make sure the root is not off by one.  The returned iteration should
2742         // not be in the range, but the previous one should be.  When solving
2743         // for "X*X < 5", for example, we should not return a root of 2.
2744         ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
2745                                                              R1->getValue(),
2746                                                              SE);
2747         if (Range.contains(R1Val->getValue())) {
2748           // The next iteration must be out of the range...
2749           ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1);
2750
2751           R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
2752           if (!Range.contains(R1Val->getValue()))
2753             return SE.getConstant(NextVal);
2754           return new SCEVCouldNotCompute();  // Something strange happened
2755         }
2756
2757         // If R1 was not in the range, then it is a good return value.  Make
2758         // sure that R1-1 WAS in the range though, just in case.
2759         ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1);
2760         R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
2761         if (Range.contains(R1Val->getValue()))
2762           return R1;
2763         return new SCEVCouldNotCompute();  // Something strange happened
2764       }
2765     }
2766   }
2767
2768   // Fallback, if this is a general polynomial, figure out the progression
2769   // through brute force: evaluate until we find an iteration that fails the
2770   // test.  This is likely to be slow, but getting an accurate trip count is
2771   // incredibly important, we will be able to simplify the exit test a lot, and
2772   // we are almost guaranteed to get a trip count in this case.
2773   ConstantInt *TestVal = ConstantInt::get(getType(), 0);
2774   ConstantInt *EndVal  = TestVal;  // Stop when we wrap around.
2775   do {
2776     ++NumBruteForceEvaluations;
2777     SCEVHandle Val = evaluateAtIteration(SE.getConstant(TestVal), SE);
2778     if (!isa<SCEVConstant>(Val))  // This shouldn't happen.
2779       return new SCEVCouldNotCompute();
2780
2781     // Check to see if we found the value!
2782     if (!Range.contains(cast<SCEVConstant>(Val)->getValue()->getValue()))
2783       return SE.getConstant(TestVal);
2784
2785     // Increment to test the next index.
2786     TestVal = ConstantInt::get(TestVal->getValue()+1);
2787   } while (TestVal != EndVal);
2788
2789   return new SCEVCouldNotCompute();
2790 }
2791
2792
2793
2794 //===----------------------------------------------------------------------===//
2795 //                   ScalarEvolution Class Implementation
2796 //===----------------------------------------------------------------------===//
2797
2798 bool ScalarEvolution::runOnFunction(Function &F) {
2799   Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
2800   return false;
2801 }
2802
2803 void ScalarEvolution::releaseMemory() {
2804   delete (ScalarEvolutionsImpl*)Impl;
2805   Impl = 0;
2806 }
2807
2808 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
2809   AU.setPreservesAll();
2810   AU.addRequiredTransitive<LoopInfo>();
2811 }
2812
2813 SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
2814   return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
2815 }
2816
2817 /// hasSCEV - Return true if the SCEV for this value has already been
2818 /// computed.
2819 bool ScalarEvolution::hasSCEV(Value *V) const {
2820   return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V);
2821 }
2822
2823
2824 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
2825 /// the specified value.
2826 void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) {
2827   ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H);
2828 }
2829
2830
2831 SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
2832   return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
2833 }
2834
2835 bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
2836   return !isa<SCEVCouldNotCompute>(getIterationCount(L));
2837 }
2838
2839 SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
2840   return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
2841 }
2842
2843 void ScalarEvolution::deleteValueFromRecords(Value *V) const {
2844   return ((ScalarEvolutionsImpl*)Impl)->deleteValueFromRecords(V);
2845 }
2846
2847 static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
2848                           const Loop *L) {
2849   // Print all inner loops first
2850   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
2851     PrintLoopInfo(OS, SE, *I);
2852
2853   OS << "Loop " << L->getHeader()->getName() << ": ";
2854
2855   SmallVector<BasicBlock*, 8> ExitBlocks;
2856   L->getExitBlocks(ExitBlocks);
2857   if (ExitBlocks.size() != 1)
2858     OS << "<multiple exits> ";
2859
2860   if (SE->hasLoopInvariantIterationCount(L)) {
2861     OS << *SE->getIterationCount(L) << " iterations! ";
2862   } else {
2863     OS << "Unpredictable iteration count. ";
2864   }
2865
2866   OS << "\n";
2867 }
2868
2869 void ScalarEvolution::print(std::ostream &OS, const Module* ) const {
2870   Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
2871   LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
2872
2873   OS << "Classifying expressions for: " << F.getName() << "\n";
2874   for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
2875     if (I->getType()->isInteger()) {
2876       OS << *I;
2877       OS << "  --> ";
2878       SCEVHandle SV = getSCEV(&*I);
2879       SV->print(OS);
2880       OS << "\t\t";
2881
2882       if ((*I).getType()->isInteger()) {
2883         ConstantRange Bounds = SV->getValueRange();
2884         if (!Bounds.isFullSet())
2885           OS << "Bounds: " << Bounds << " ";
2886       }
2887
2888       if (const Loop *L = LI.getLoopFor((*I).getParent())) {
2889         OS << "Exits: ";
2890         SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop());
2891         if (isa<SCEVCouldNotCompute>(ExitValue)) {
2892           OS << "<<Unknown>>";
2893         } else {
2894           OS << *ExitValue;
2895         }
2896       }
2897
2898
2899       OS << "\n";
2900     }
2901
2902   OS << "Determining loop execution counts for: " << F.getName() << "\n";
2903   for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
2904     PrintLoopInfo(OS, this, *I);
2905 }