1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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.
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.
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.
36 // TODO: We should use these routines and value representations to implement
37 // dependence analysis!
39 //===----------------------------------------------------------------------===//
41 // There are several good references for the techniques used in this analysis.
43 // Chains of recurrences -- a method to expedite the evaluation
44 // of closed-form functions
45 // Olaf Bachmann, Paul S. Wang, Eugene V. Zima
47 // On computational properties of chains of recurrences
50 // Symbolic Evaluation of Chains of Recurrences for Loop Optimization
51 // Robert A. van Engelen
53 // Efficient Symbolic Analysis for Optimizing Compilers
54 // Robert A. van Engelen
56 // Using the chains of recurrences algebra for data dependence testing and
57 // induction variable substitution
58 // MS Thesis, Johnie Birch
60 //===----------------------------------------------------------------------===//
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"
82 #include "llvm/Support/Debug.h"
88 STATISTIC(NumBruteForceEvaluations,
89 "Number of brute force evaluations needed to "
90 "calculate high-order polynomial exit values");
91 STATISTIC(NumArrayLenItCounts,
92 "Number of trip counts computed with array length");
93 STATISTIC(NumTripCountsComputed,
94 "Number of loops with predictable loop counts");
95 STATISTIC(NumTripCountsNotComputed,
96 "Number of loops without predictable loop counts");
97 STATISTIC(NumBruteForceTripCountsComputed,
98 "Number of loops with trip counts computed by force");
100 static cl::opt<unsigned>
101 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
102 cl::desc("Maximum number of iterations SCEV will "
103 "symbolically execute a constant derived loop"),
106 static RegisterPass<ScalarEvolution>
107 R("scalar-evolution", "Scalar Evolution Analysis", false, true);
108 char ScalarEvolution::ID = 0;
110 //===----------------------------------------------------------------------===//
111 // SCEV class definitions
112 //===----------------------------------------------------------------------===//
114 //===----------------------------------------------------------------------===//
115 // Implementation of the SCEV class.
118 void SCEV::dump() const {
122 uint32_t SCEV::getBitWidth() const {
123 if (const IntegerType* ITy = dyn_cast<IntegerType>(getType()))
124 return ITy->getBitWidth();
128 bool SCEV::isZero() const {
129 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
130 return SC->getValue()->isZero();
135 SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
137 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
138 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
142 const Type *SCEVCouldNotCompute::getType() const {
143 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
147 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
148 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
152 SCEVHandle SCEVCouldNotCompute::
153 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
154 const SCEVHandle &Conc,
155 ScalarEvolution &SE) const {
159 void SCEVCouldNotCompute::print(std::ostream &OS) const {
160 OS << "***COULDNOTCOMPUTE***";
163 bool SCEVCouldNotCompute::classof(const SCEV *S) {
164 return S->getSCEVType() == scCouldNotCompute;
168 // SCEVConstants - Only allow the creation of one SCEVConstant for any
169 // particular value. Don't use a SCEVHandle here, or else the object will
171 static ManagedStatic<std::map<ConstantInt*, SCEVConstant*> > SCEVConstants;
174 SCEVConstant::~SCEVConstant() {
175 SCEVConstants->erase(V);
178 SCEVHandle ScalarEvolution::getConstant(ConstantInt *V) {
179 SCEVConstant *&R = (*SCEVConstants)[V];
180 if (R == 0) R = new SCEVConstant(V);
184 SCEVHandle ScalarEvolution::getConstant(const APInt& Val) {
185 return getConstant(ConstantInt::get(Val));
188 const Type *SCEVConstant::getType() const { return V->getType(); }
190 void SCEVConstant::print(std::ostream &OS) const {
191 WriteAsOperand(OS, V, false);
194 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
195 // particular input. Don't use a SCEVHandle here, or else the object will
197 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
198 SCEVTruncateExpr*> > SCEVTruncates;
200 SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
201 : SCEV(scTruncate), Op(op), Ty(ty) {
202 assert(Op->getType()->isInteger() && Ty->isInteger() &&
203 "Cannot truncate non-integer value!");
204 assert(Op->getType()->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits()
205 && "This is not a truncating conversion!");
208 SCEVTruncateExpr::~SCEVTruncateExpr() {
209 SCEVTruncates->erase(std::make_pair(Op, Ty));
212 void SCEVTruncateExpr::print(std::ostream &OS) const {
213 OS << "(truncate " << *Op << " to " << *Ty << ")";
216 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
217 // particular input. Don't use a SCEVHandle here, or else the object will never
219 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
220 SCEVZeroExtendExpr*> > SCEVZeroExtends;
222 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
223 : SCEV(scZeroExtend), Op(op), Ty(ty) {
224 assert(Op->getType()->isInteger() && Ty->isInteger() &&
225 "Cannot zero extend non-integer value!");
226 assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
227 && "This is not an extending conversion!");
230 SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
231 SCEVZeroExtends->erase(std::make_pair(Op, Ty));
234 void SCEVZeroExtendExpr::print(std::ostream &OS) const {
235 OS << "(zeroextend " << *Op << " to " << *Ty << ")";
238 // SCEVSignExtends - Only allow the creation of one SCEVSignExtendExpr for any
239 // particular input. Don't use a SCEVHandle here, or else the object will never
241 static ManagedStatic<std::map<std::pair<SCEV*, const Type*>,
242 SCEVSignExtendExpr*> > SCEVSignExtends;
244 SCEVSignExtendExpr::SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty)
245 : SCEV(scSignExtend), Op(op), Ty(ty) {
246 assert(Op->getType()->isInteger() && Ty->isInteger() &&
247 "Cannot sign extend non-integer value!");
248 assert(Op->getType()->getPrimitiveSizeInBits() < Ty->getPrimitiveSizeInBits()
249 && "This is not an extending conversion!");
252 SCEVSignExtendExpr::~SCEVSignExtendExpr() {
253 SCEVSignExtends->erase(std::make_pair(Op, Ty));
256 void SCEVSignExtendExpr::print(std::ostream &OS) const {
257 OS << "(signextend " << *Op << " to " << *Ty << ")";
260 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
261 // particular input. Don't use a SCEVHandle here, or else the object will never
263 static ManagedStatic<std::map<std::pair<unsigned, std::vector<SCEV*> >,
264 SCEVCommutativeExpr*> > SCEVCommExprs;
266 SCEVCommutativeExpr::~SCEVCommutativeExpr() {
267 SCEVCommExprs->erase(std::make_pair(getSCEVType(),
268 std::vector<SCEV*>(Operands.begin(),
272 void SCEVCommutativeExpr::print(std::ostream &OS) const {
273 assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
274 const char *OpStr = getOperationStr();
275 OS << "(" << *Operands[0];
276 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
277 OS << OpStr << *Operands[i];
281 SCEVHandle SCEVCommutativeExpr::
282 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
283 const SCEVHandle &Conc,
284 ScalarEvolution &SE) const {
285 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
287 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
288 if (H != getOperand(i)) {
289 std::vector<SCEVHandle> NewOps;
290 NewOps.reserve(getNumOperands());
291 for (unsigned j = 0; j != i; ++j)
292 NewOps.push_back(getOperand(j));
294 for (++i; i != e; ++i)
295 NewOps.push_back(getOperand(i)->
296 replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
298 if (isa<SCEVAddExpr>(this))
299 return SE.getAddExpr(NewOps);
300 else if (isa<SCEVMulExpr>(this))
301 return SE.getMulExpr(NewOps);
302 else if (isa<SCEVSMaxExpr>(this))
303 return SE.getSMaxExpr(NewOps);
304 else if (isa<SCEVUMaxExpr>(this))
305 return SE.getUMaxExpr(NewOps);
307 assert(0 && "Unknown commutative expr!");
314 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
315 // input. Don't use a SCEVHandle here, or else the object will never be
317 static ManagedStatic<std::map<std::pair<SCEV*, SCEV*>,
318 SCEVUDivExpr*> > SCEVUDivs;
320 SCEVUDivExpr::~SCEVUDivExpr() {
321 SCEVUDivs->erase(std::make_pair(LHS, RHS));
324 void SCEVUDivExpr::print(std::ostream &OS) const {
325 OS << "(" << *LHS << " /u " << *RHS << ")";
328 const Type *SCEVUDivExpr::getType() const {
329 return LHS->getType();
332 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
333 // particular input. Don't use a SCEVHandle here, or else the object will never
335 static ManagedStatic<std::map<std::pair<const Loop *, std::vector<SCEV*> >,
336 SCEVAddRecExpr*> > SCEVAddRecExprs;
338 SCEVAddRecExpr::~SCEVAddRecExpr() {
339 SCEVAddRecExprs->erase(std::make_pair(L,
340 std::vector<SCEV*>(Operands.begin(),
344 SCEVHandle SCEVAddRecExpr::
345 replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
346 const SCEVHandle &Conc,
347 ScalarEvolution &SE) const {
348 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
350 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
351 if (H != getOperand(i)) {
352 std::vector<SCEVHandle> NewOps;
353 NewOps.reserve(getNumOperands());
354 for (unsigned j = 0; j != i; ++j)
355 NewOps.push_back(getOperand(j));
357 for (++i; i != e; ++i)
358 NewOps.push_back(getOperand(i)->
359 replaceSymbolicValuesWithConcrete(Sym, Conc, SE));
361 return SE.getAddRecExpr(NewOps, L);
368 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
369 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
370 // contain L and if the start is invariant.
371 return !QueryLoop->contains(L->getHeader()) &&
372 getOperand(0)->isLoopInvariant(QueryLoop);
376 void SCEVAddRecExpr::print(std::ostream &OS) const {
377 OS << "{" << *Operands[0];
378 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
379 OS << ",+," << *Operands[i];
380 OS << "}<" << L->getHeader()->getName() + ">";
383 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
384 // value. Don't use a SCEVHandle here, or else the object will never be
386 static ManagedStatic<std::map<Value*, SCEVUnknown*> > SCEVUnknowns;
388 SCEVUnknown::~SCEVUnknown() { SCEVUnknowns->erase(V); }
390 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
391 // All non-instruction values are loop invariant. All instructions are loop
392 // invariant if they are not contained in the specified loop.
393 if (Instruction *I = dyn_cast<Instruction>(V))
394 return !L->contains(I->getParent());
398 const Type *SCEVUnknown::getType() const {
402 void SCEVUnknown::print(std::ostream &OS) const {
403 WriteAsOperand(OS, V, false);
406 //===----------------------------------------------------------------------===//
408 //===----------------------------------------------------------------------===//
411 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
412 /// than the complexity of the RHS. This comparator is used to canonicalize
414 struct VISIBILITY_HIDDEN SCEVComplexityCompare {
415 bool operator()(const SCEV *LHS, const SCEV *RHS) const {
416 return LHS->getSCEVType() < RHS->getSCEVType();
421 /// GroupByComplexity - Given a list of SCEV objects, order them by their
422 /// complexity, and group objects of the same complexity together by value.
423 /// When this routine is finished, we know that any duplicates in the vector are
424 /// consecutive and that complexity is monotonically increasing.
426 /// Note that we go take special precautions to ensure that we get determinstic
427 /// results from this routine. In other words, we don't want the results of
428 /// this to depend on where the addresses of various SCEV objects happened to
431 static void GroupByComplexity(std::vector<SCEVHandle> &Ops) {
432 if (Ops.size() < 2) return; // Noop
433 if (Ops.size() == 2) {
434 // This is the common case, which also happens to be trivially simple.
436 if (SCEVComplexityCompare()(Ops[1], Ops[0]))
437 std::swap(Ops[0], Ops[1]);
441 // Do the rough sort by complexity.
442 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
444 // Now that we are sorted by complexity, group elements of the same
445 // complexity. Note that this is, at worst, N^2, but the vector is likely to
446 // be extremely short in practice. Note that we take this approach because we
447 // do not want to depend on the addresses of the objects we are grouping.
448 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) {
450 unsigned Complexity = S->getSCEVType();
452 // If there are any objects of the same complexity and same value as this
454 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
455 if (Ops[j] == S) { // Found a duplicate.
456 // Move it to immediately after i'th element.
457 std::swap(Ops[i+1], Ops[j]);
458 ++i; // no need to rescan it.
459 if (i == e-2) return; // Done!
467 //===----------------------------------------------------------------------===//
468 // Simple SCEV method implementations
469 //===----------------------------------------------------------------------===//
471 /// getIntegerSCEV - Given an integer or FP type, create a constant for the
472 /// specified signed integer value and return a SCEV for the constant.
473 SCEVHandle ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) {
476 C = Constant::getNullValue(Ty);
477 else if (Ty->isFloatingPoint())
478 C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
479 APFloat::IEEEdouble, Val));
481 C = ConstantInt::get(Ty, Val);
482 return getUnknown(C);
485 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
487 SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
488 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
489 return getUnknown(ConstantExpr::getNeg(VC->getValue()));
491 return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
494 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
495 SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
496 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
497 return getUnknown(ConstantExpr::getNot(VC->getValue()));
499 SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
500 return getMinusSCEV(AllOnes, V);
503 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
505 SCEVHandle ScalarEvolution::getMinusSCEV(const SCEVHandle &LHS,
506 const SCEVHandle &RHS) {
508 return getAddExpr(LHS, getNegativeSCEV(RHS));
512 /// BinomialCoefficient - Compute BC(It, K). The result is of the same type as
513 /// It. Assume, K > 0.
514 static SCEVHandle BinomialCoefficient(SCEVHandle It, unsigned K,
515 ScalarEvolution &SE) {
516 // We are using the following formula for BC(It, K):
518 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K!
520 // Suppose, W is the bitwidth of It (and of the return value as well). We
521 // must be prepared for overflow. Hence, we must assure that the result of
522 // our computation is equal to the accurate one modulo 2^W. Unfortunately,
523 // division isn't safe in modular arithmetic. This means we must perform the
524 // whole computation accurately and then truncate the result to W bits.
526 // The dividend of the formula is a multiplication of K integers of bitwidth
527 // W. K*W bits suffice to compute it accurately.
529 // FIXME: We assume the divisor can be accurately computed using 16-bit
530 // unsigned integer type. It is true up to K = 8 (AddRecs of length 9). In
531 // future we may use APInt to use the minimum number of bits necessary to
532 // compute it accurately.
534 // It is safe to use unsigned division here: the dividend is nonnegative and
535 // the divisor is positive.
537 // Handle the simplest case efficiently.
541 assert(K < 9 && "We cannot handle such long AddRecs yet.");
543 // FIXME: A temporary hack to remove in future. Arbitrary precision integers
544 // aren't supported by the code generator yet. For the dividend, the bitwidth
545 // we use is the smallest power of 2 greater or equal to K*W and less or equal
546 // to 64. Note that setting the upper bound for bitwidth may still lead to
547 // miscompilation in some cases.
548 unsigned DividendBits = 1U << Log2_32_Ceil(K * It->getBitWidth());
549 if (DividendBits > 64)
551 #if 0 // Waiting for the APInt support in the code generator...
552 unsigned DividendBits = K * It->getBitWidth();
555 const IntegerType *DividendTy = IntegerType::get(DividendBits);
556 const SCEVHandle ExIt = SE.getTruncateOrZeroExtend(It, DividendTy);
558 // The final number of bits we need to perform the division is the maximum of
559 // dividend and divisor bitwidths.
560 const IntegerType *DivisionTy =
561 IntegerType::get(std::max(DividendBits, 16U));
563 // Compute K! We know K >= 2 here.
565 for (unsigned i = 3; i <= K; ++i)
567 APInt Divisor(DivisionTy->getBitWidth(), F);
569 // Handle this case efficiently, it is common to have constant iteration
570 // counts while computing loop exit values.
571 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(ExIt)) {
572 const APInt& N = SC->getValue()->getValue();
573 APInt Dividend(N.getBitWidth(), 1);
576 if (DividendTy != DivisionTy)
577 Dividend = Dividend.zext(DivisionTy->getBitWidth());
579 APInt Result = Dividend.udiv(Divisor);
580 if (Result.getBitWidth() != It->getBitWidth())
581 Result = Result.trunc(It->getBitWidth());
583 return SE.getConstant(Result);
586 SCEVHandle Dividend = ExIt;
587 for (unsigned i = 1; i != K; ++i)
589 SE.getMulExpr(Dividend,
590 SE.getMinusSCEV(ExIt, SE.getIntegerSCEV(i, DividendTy)));
592 return SE.getTruncateOrZeroExtend(
594 SE.getTruncateOrZeroExtend(Dividend, DivisionTy),
595 SE.getConstant(Divisor)
599 /// evaluateAtIteration - Return the value of this chain of recurrences at
600 /// the specified iteration number. We can evaluate this recurrence by
601 /// multiplying each element in the chain by the binomial coefficient
602 /// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as:
604 /// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3)
606 /// where BC(It, k) stands for binomial coefficient.
608 SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It,
609 ScalarEvolution &SE) const {
610 SCEVHandle Result = getStart();
611 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
612 // The computation is correct in the face of overflow provided that the
613 // multiplication is performed _after_ the evaluation of the binomial
615 SCEVHandle Val = SE.getMulExpr(getOperand(i),
616 BinomialCoefficient(It, i, SE));
617 Result = SE.getAddExpr(Result, Val);
622 //===----------------------------------------------------------------------===//
623 // SCEV Expression folder implementations
624 //===----------------------------------------------------------------------===//
626 SCEVHandle ScalarEvolution::getTruncateExpr(const SCEVHandle &Op, const Type *Ty) {
627 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
629 ConstantExpr::getTrunc(SC->getValue(), Ty));
631 // If the input value is a chrec scev made out of constants, truncate
632 // all of the constants.
633 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
634 std::vector<SCEVHandle> Operands;
635 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
636 // FIXME: This should allow truncation of other expression types!
637 if (isa<SCEVConstant>(AddRec->getOperand(i)))
638 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
641 if (Operands.size() == AddRec->getNumOperands())
642 return getAddRecExpr(Operands, AddRec->getLoop());
645 SCEVTruncateExpr *&Result = (*SCEVTruncates)[std::make_pair(Op, Ty)];
646 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
650 SCEVHandle ScalarEvolution::getZeroExtendExpr(const SCEVHandle &Op, const Type *Ty) {
651 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
653 ConstantExpr::getZExt(SC->getValue(), Ty));
655 // FIXME: If the input value is a chrec scev, and we can prove that the value
656 // did not overflow the old, smaller, value, we can zero extend all of the
657 // operands (often constants). This would allow analysis of something like
658 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
660 SCEVZeroExtendExpr *&Result = (*SCEVZeroExtends)[std::make_pair(Op, Ty)];
661 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
665 SCEVHandle ScalarEvolution::getSignExtendExpr(const SCEVHandle &Op, const Type *Ty) {
666 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
668 ConstantExpr::getSExt(SC->getValue(), Ty));
670 // FIXME: If the input value is a chrec scev, and we can prove that the value
671 // did not overflow the old, smaller, value, we can sign extend all of the
672 // operands (often constants). This would allow analysis of something like
673 // this: for (signed char X = 0; X < 100; ++X) { int Y = X; }
675 SCEVSignExtendExpr *&Result = (*SCEVSignExtends)[std::make_pair(Op, Ty)];
676 if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
680 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
681 /// of the input value to the specified type. If the type must be
682 /// extended, it is zero extended.
683 SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
685 const Type *SrcTy = V->getType();
686 assert(SrcTy->isInteger() && Ty->isInteger() &&
687 "Cannot truncate or zero extend with non-integer arguments!");
688 if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
689 return V; // No conversion
690 if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
691 return getTruncateExpr(V, Ty);
692 return getZeroExtendExpr(V, Ty);
695 // get - Get a canonical add expression, or something simpler if possible.
696 SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
697 assert(!Ops.empty() && "Cannot get empty add!");
698 if (Ops.size() == 1) return Ops[0];
700 // Sort by complexity, this groups all similar expression types together.
701 GroupByComplexity(Ops);
703 // If there are any constants, fold them together.
705 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
707 assert(Idx < Ops.size());
708 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
709 // We found two constants, fold them together!
710 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
711 RHSC->getValue()->getValue());
712 Ops[0] = getConstant(Fold);
713 Ops.erase(Ops.begin()+1); // Erase the folded element
714 if (Ops.size() == 1) return Ops[0];
715 LHSC = cast<SCEVConstant>(Ops[0]);
718 // If we are left with a constant zero being added, strip it off.
719 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
720 Ops.erase(Ops.begin());
725 if (Ops.size() == 1) return Ops[0];
727 // Okay, check to see if the same value occurs in the operand list twice. If
728 // so, merge them together into an multiply expression. Since we sorted the
729 // list, these values are required to be adjacent.
730 const Type *Ty = Ops[0]->getType();
731 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
732 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
733 // Found a match, merge the two values into a multiply, and add any
734 // remaining values to the result.
735 SCEVHandle Two = getIntegerSCEV(2, Ty);
736 SCEVHandle Mul = getMulExpr(Ops[i], Two);
739 Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
741 return getAddExpr(Ops);
744 // Now we know the first non-constant operand. Skip past any cast SCEVs.
745 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr)
748 // If there are add operands they would be next.
749 if (Idx < Ops.size()) {
750 bool DeletedAdd = false;
751 while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
752 // If we have an add, expand the add operands onto the end of the operands
754 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
755 Ops.erase(Ops.begin()+Idx);
759 // If we deleted at least one add, we added operands to the end of the list,
760 // and they are not necessarily sorted. Recurse to resort and resimplify
761 // any operands we just aquired.
763 return getAddExpr(Ops);
766 // Skip over the add expression until we get to a multiply.
767 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
770 // If we are adding something to a multiply expression, make sure the
771 // something is not already an operand of the multiply. If so, merge it into
773 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
774 SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
775 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
776 SCEV *MulOpSCEV = Mul->getOperand(MulOp);
777 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
778 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(MulOpSCEV)) {
779 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
780 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
781 if (Mul->getNumOperands() != 2) {
782 // If the multiply has more than two operands, we must get the
784 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
785 MulOps.erase(MulOps.begin()+MulOp);
786 InnerMul = getMulExpr(MulOps);
788 SCEVHandle One = getIntegerSCEV(1, Ty);
789 SCEVHandle AddOne = getAddExpr(InnerMul, One);
790 SCEVHandle OuterMul = getMulExpr(AddOne, Ops[AddOp]);
791 if (Ops.size() == 2) return OuterMul;
793 Ops.erase(Ops.begin()+AddOp);
794 Ops.erase(Ops.begin()+Idx-1);
796 Ops.erase(Ops.begin()+Idx);
797 Ops.erase(Ops.begin()+AddOp-1);
799 Ops.push_back(OuterMul);
800 return getAddExpr(Ops);
803 // Check this multiply against other multiplies being added together.
804 for (unsigned OtherMulIdx = Idx+1;
805 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
807 SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
808 // If MulOp occurs in OtherMul, we can fold the two multiplies
810 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
811 OMulOp != e; ++OMulOp)
812 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
813 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
814 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
815 if (Mul->getNumOperands() != 2) {
816 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
817 MulOps.erase(MulOps.begin()+MulOp);
818 InnerMul1 = getMulExpr(MulOps);
820 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
821 if (OtherMul->getNumOperands() != 2) {
822 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
824 MulOps.erase(MulOps.begin()+OMulOp);
825 InnerMul2 = getMulExpr(MulOps);
827 SCEVHandle InnerMulSum = getAddExpr(InnerMul1,InnerMul2);
828 SCEVHandle OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
829 if (Ops.size() == 2) return OuterMul;
830 Ops.erase(Ops.begin()+Idx);
831 Ops.erase(Ops.begin()+OtherMulIdx-1);
832 Ops.push_back(OuterMul);
833 return getAddExpr(Ops);
839 // If there are any add recurrences in the operands list, see if any other
840 // added values are loop invariant. If so, we can fold them into the
842 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
845 // Scan over all recurrences, trying to fold loop invariants into them.
846 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
847 // Scan all of the other operands to this add and add them to the vector if
848 // they are loop invariant w.r.t. the recurrence.
849 std::vector<SCEVHandle> LIOps;
850 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
851 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
852 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
853 LIOps.push_back(Ops[i]);
854 Ops.erase(Ops.begin()+i);
858 // If we found some loop invariants, fold them into the recurrence.
859 if (!LIOps.empty()) {
860 // NLI + LI + { Start,+,Step} --> NLI + { LI+Start,+,Step }
861 LIOps.push_back(AddRec->getStart());
863 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
864 AddRecOps[0] = getAddExpr(LIOps);
866 SCEVHandle NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop());
867 // If all of the other operands were loop invariant, we are done.
868 if (Ops.size() == 1) return NewRec;
870 // Otherwise, add the folded AddRec by the non-liv parts.
871 for (unsigned i = 0;; ++i)
872 if (Ops[i] == AddRec) {
876 return getAddExpr(Ops);
879 // Okay, if there weren't any loop invariants to be folded, check to see if
880 // there are multiple AddRec's with the same loop induction variable being
881 // added together. If so, we can fold them.
882 for (unsigned OtherIdx = Idx+1;
883 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
884 if (OtherIdx != Idx) {
885 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
886 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
887 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
888 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
889 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
890 if (i >= NewOps.size()) {
891 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
892 OtherAddRec->op_end());
895 NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i));
897 SCEVHandle NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop());
899 if (Ops.size() == 2) return NewAddRec;
901 Ops.erase(Ops.begin()+Idx);
902 Ops.erase(Ops.begin()+OtherIdx-1);
903 Ops.push_back(NewAddRec);
904 return getAddExpr(Ops);
908 // Otherwise couldn't fold anything into this recurrence. Move onto the
912 // Okay, it looks like we really DO need an add expr. Check to see if we
913 // already have one, otherwise create a new one.
914 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
915 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scAddExpr,
917 if (Result == 0) Result = new SCEVAddExpr(Ops);
922 SCEVHandle ScalarEvolution::getMulExpr(std::vector<SCEVHandle> &Ops) {
923 assert(!Ops.empty() && "Cannot get empty mul!");
925 // Sort by complexity, this groups all similar expression types together.
926 GroupByComplexity(Ops);
928 // If there are any constants, fold them together.
930 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
932 // C1*(C2+V) -> C1*C2 + C1*V
934 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
935 if (Add->getNumOperands() == 2 &&
936 isa<SCEVConstant>(Add->getOperand(0)))
937 return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
938 getMulExpr(LHSC, Add->getOperand(1)));
942 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
943 // We found two constants, fold them together!
944 ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
945 RHSC->getValue()->getValue());
946 Ops[0] = getConstant(Fold);
947 Ops.erase(Ops.begin()+1); // Erase the folded element
948 if (Ops.size() == 1) return Ops[0];
949 LHSC = cast<SCEVConstant>(Ops[0]);
952 // If we are left with a constant one being multiplied, strip it off.
953 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
954 Ops.erase(Ops.begin());
956 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
957 // If we have a multiply of zero, it will always be zero.
962 // Skip over the add expression until we get to a multiply.
963 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
969 // If there are mul operands inline them all into this expression.
970 if (Idx < Ops.size()) {
971 bool DeletedMul = false;
972 while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
973 // If we have an mul, expand the mul operands onto the end of the operands
975 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
976 Ops.erase(Ops.begin()+Idx);
980 // If we deleted at least one mul, we added operands to the end of the list,
981 // and they are not necessarily sorted. Recurse to resort and resimplify
982 // any operands we just aquired.
984 return getMulExpr(Ops);
987 // If there are any add recurrences in the operands list, see if any other
988 // added values are loop invariant. If so, we can fold them into the
990 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
993 // Scan over all recurrences, trying to fold loop invariants into them.
994 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
995 // Scan all of the other operands to this mul and add them to the vector if
996 // they are loop invariant w.r.t. the recurrence.
997 std::vector<SCEVHandle> LIOps;
998 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
999 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1000 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
1001 LIOps.push_back(Ops[i]);
1002 Ops.erase(Ops.begin()+i);
1006 // If we found some loop invariants, fold them into the recurrence.
1007 if (!LIOps.empty()) {
1008 // NLI * LI * { Start,+,Step} --> NLI * { LI*Start,+,LI*Step }
1009 std::vector<SCEVHandle> NewOps;
1010 NewOps.reserve(AddRec->getNumOperands());
1011 if (LIOps.size() == 1) {
1012 SCEV *Scale = LIOps[0];
1013 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
1014 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
1016 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
1017 std::vector<SCEVHandle> MulOps(LIOps);
1018 MulOps.push_back(AddRec->getOperand(i));
1019 NewOps.push_back(getMulExpr(MulOps));
1023 SCEVHandle NewRec = getAddRecExpr(NewOps, AddRec->getLoop());
1025 // If all of the other operands were loop invariant, we are done.
1026 if (Ops.size() == 1) return NewRec;
1028 // Otherwise, multiply the folded AddRec by the non-liv parts.
1029 for (unsigned i = 0;; ++i)
1030 if (Ops[i] == AddRec) {
1034 return getMulExpr(Ops);
1037 // Okay, if there weren't any loop invariants to be folded, check to see if
1038 // there are multiple AddRec's with the same loop induction variable being
1039 // multiplied together. If so, we can fold them.
1040 for (unsigned OtherIdx = Idx+1;
1041 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
1042 if (OtherIdx != Idx) {
1043 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
1044 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
1045 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
1046 SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
1047 SCEVHandle NewStart = getMulExpr(F->getStart(),
1049 SCEVHandle B = F->getStepRecurrence(*this);
1050 SCEVHandle D = G->getStepRecurrence(*this);
1051 SCEVHandle NewStep = getAddExpr(getMulExpr(F, D),
1054 SCEVHandle NewAddRec = getAddRecExpr(NewStart, NewStep,
1056 if (Ops.size() == 2) return NewAddRec;
1058 Ops.erase(Ops.begin()+Idx);
1059 Ops.erase(Ops.begin()+OtherIdx-1);
1060 Ops.push_back(NewAddRec);
1061 return getMulExpr(Ops);
1065 // Otherwise couldn't fold anything into this recurrence. Move onto the
1069 // Okay, it looks like we really DO need an mul expr. Check to see if we
1070 // already have one, otherwise create a new one.
1071 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1072 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scMulExpr,
1075 Result = new SCEVMulExpr(Ops);
1079 SCEVHandle ScalarEvolution::getUDivExpr(const SCEVHandle &LHS, const SCEVHandle &RHS) {
1080 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
1081 if (RHSC->getValue()->equalsInt(1))
1082 return LHS; // X udiv 1 --> x
1084 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1085 Constant *LHSCV = LHSC->getValue();
1086 Constant *RHSCV = RHSC->getValue();
1087 return getUnknown(ConstantExpr::getUDiv(LHSCV, RHSCV));
1091 // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
1093 SCEVUDivExpr *&Result = (*SCEVUDivs)[std::make_pair(LHS, RHS)];
1094 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
1099 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
1100 /// specified loop. Simplify the expression as much as possible.
1101 SCEVHandle ScalarEvolution::getAddRecExpr(const SCEVHandle &Start,
1102 const SCEVHandle &Step, const Loop *L) {
1103 std::vector<SCEVHandle> Operands;
1104 Operands.push_back(Start);
1105 if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
1106 if (StepChrec->getLoop() == L) {
1107 Operands.insert(Operands.end(), StepChrec->op_begin(),
1108 StepChrec->op_end());
1109 return getAddRecExpr(Operands, L);
1112 Operands.push_back(Step);
1113 return getAddRecExpr(Operands, L);
1116 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
1117 /// specified loop. Simplify the expression as much as possible.
1118 SCEVHandle ScalarEvolution::getAddRecExpr(std::vector<SCEVHandle> &Operands,
1120 if (Operands.size() == 1) return Operands[0];
1122 if (Operands.back()->isZero()) {
1123 Operands.pop_back();
1124 return getAddRecExpr(Operands, L); // { X,+,0 } --> X
1127 SCEVAddRecExpr *&Result =
1128 (*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
1130 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
1134 SCEVHandle ScalarEvolution::getSMaxExpr(const SCEVHandle &LHS,
1135 const SCEVHandle &RHS) {
1136 std::vector<SCEVHandle> Ops;
1139 return getSMaxExpr(Ops);
1142 SCEVHandle ScalarEvolution::getSMaxExpr(std::vector<SCEVHandle> Ops) {
1143 assert(!Ops.empty() && "Cannot get empty smax!");
1144 if (Ops.size() == 1) return Ops[0];
1146 // Sort by complexity, this groups all similar expression types together.
1147 GroupByComplexity(Ops);
1149 // If there are any constants, fold them together.
1151 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1153 assert(Idx < Ops.size());
1154 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1155 // We found two constants, fold them together!
1156 ConstantInt *Fold = ConstantInt::get(
1157 APIntOps::smax(LHSC->getValue()->getValue(),
1158 RHSC->getValue()->getValue()));
1159 Ops[0] = getConstant(Fold);
1160 Ops.erase(Ops.begin()+1); // Erase the folded element
1161 if (Ops.size() == 1) return Ops[0];
1162 LHSC = cast<SCEVConstant>(Ops[0]);
1165 // If we are left with a constant -inf, strip it off.
1166 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) {
1167 Ops.erase(Ops.begin());
1172 if (Ops.size() == 1) return Ops[0];
1174 // Find the first SMax
1175 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr)
1178 // Check to see if one of the operands is an SMax. If so, expand its operands
1179 // onto our operand list, and recurse to simplify.
1180 if (Idx < Ops.size()) {
1181 bool DeletedSMax = false;
1182 while (SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
1183 Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end());
1184 Ops.erase(Ops.begin()+Idx);
1189 return getSMaxExpr(Ops);
1192 // Okay, check to see if the same value occurs in the operand list twice. If
1193 // so, delete one. Since we sorted the list, these values are required to
1195 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1196 if (Ops[i] == Ops[i+1]) { // X smax Y smax Y --> X smax Y
1197 Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1201 if (Ops.size() == 1) return Ops[0];
1203 assert(!Ops.empty() && "Reduced smax down to nothing!");
1205 // Okay, it looks like we really DO need an smax expr. Check to see if we
1206 // already have one, otherwise create a new one.
1207 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1208 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
1210 if (Result == 0) Result = new SCEVSMaxExpr(Ops);
1214 SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
1215 const SCEVHandle &RHS) {
1216 std::vector<SCEVHandle> Ops;
1219 return getUMaxExpr(Ops);
1222 SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
1223 assert(!Ops.empty() && "Cannot get empty umax!");
1224 if (Ops.size() == 1) return Ops[0];
1226 // Sort by complexity, this groups all similar expression types together.
1227 GroupByComplexity(Ops);
1229 // If there are any constants, fold them together.
1231 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1233 assert(Idx < Ops.size());
1234 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1235 // We found two constants, fold them together!
1236 ConstantInt *Fold = ConstantInt::get(
1237 APIntOps::umax(LHSC->getValue()->getValue(),
1238 RHSC->getValue()->getValue()));
1239 Ops[0] = getConstant(Fold);
1240 Ops.erase(Ops.begin()+1); // Erase the folded element
1241 if (Ops.size() == 1) return Ops[0];
1242 LHSC = cast<SCEVConstant>(Ops[0]);
1245 // If we are left with a constant zero, strip it off.
1246 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
1247 Ops.erase(Ops.begin());
1252 if (Ops.size() == 1) return Ops[0];
1254 // Find the first UMax
1255 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
1258 // Check to see if one of the operands is a UMax. If so, expand its operands
1259 // onto our operand list, and recurse to simplify.
1260 if (Idx < Ops.size()) {
1261 bool DeletedUMax = false;
1262 while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
1263 Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
1264 Ops.erase(Ops.begin()+Idx);
1269 return getUMaxExpr(Ops);
1272 // Okay, check to see if the same value occurs in the operand list twice. If
1273 // so, delete one. Since we sorted the list, these values are required to
1275 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
1276 if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y
1277 Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
1281 if (Ops.size() == 1) return Ops[0];
1283 assert(!Ops.empty() && "Reduced umax down to nothing!");
1285 // Okay, it looks like we really DO need a umax expr. Check to see if we
1286 // already have one, otherwise create a new one.
1287 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
1288 SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
1290 if (Result == 0) Result = new SCEVUMaxExpr(Ops);
1294 SCEVHandle ScalarEvolution::getUnknown(Value *V) {
1295 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
1296 return getConstant(CI);
1297 SCEVUnknown *&Result = (*SCEVUnknowns)[V];
1298 if (Result == 0) Result = new SCEVUnknown(V);
1303 //===----------------------------------------------------------------------===//
1304 // ScalarEvolutionsImpl Definition and Implementation
1305 //===----------------------------------------------------------------------===//
1307 /// ScalarEvolutionsImpl - This class implements the main driver for the scalar
1311 struct VISIBILITY_HIDDEN ScalarEvolutionsImpl {
1312 /// SE - A reference to the public ScalarEvolution object.
1313 ScalarEvolution &SE;
1315 /// F - The function we are analyzing.
1319 /// LI - The loop information for the function we are currently analyzing.
1323 /// UnknownValue - This SCEV is used to represent unknown trip counts and
1325 SCEVHandle UnknownValue;
1327 /// Scalars - This is a cache of the scalars we have analyzed so far.
1329 std::map<Value*, SCEVHandle> Scalars;
1331 /// IterationCounts - Cache the iteration count of the loops for this
1332 /// function as they are computed.
1333 std::map<const Loop*, SCEVHandle> IterationCounts;
1335 /// ConstantEvolutionLoopExitValue - This map contains entries for all of
1336 /// the PHI instructions that we attempt to compute constant evolutions for.
1337 /// This allows us to avoid potentially expensive recomputation of these
1338 /// properties. An instruction maps to null if we are unable to compute its
1340 std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
1343 ScalarEvolutionsImpl(ScalarEvolution &se, Function &f, LoopInfo &li)
1344 : SE(se), F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
1346 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1347 /// expression and create a new one.
1348 SCEVHandle getSCEV(Value *V);
1350 /// hasSCEV - Return true if the SCEV for this value has already been
1352 bool hasSCEV(Value *V) const {
1353 return Scalars.count(V);
1356 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
1357 /// the specified value.
1358 void setSCEV(Value *V, const SCEVHandle &H) {
1359 bool isNew = Scalars.insert(std::make_pair(V, H)).second;
1360 assert(isNew && "This entry already existed!");
1364 /// getSCEVAtScope - Compute the value of the specified expression within
1365 /// the indicated loop (which may be null to indicate in no loop). If the
1366 /// expression cannot be evaluated, return UnknownValue itself.
1367 SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
1370 /// hasLoopInvariantIterationCount - Return true if the specified loop has
1371 /// an analyzable loop-invariant iteration count.
1372 bool hasLoopInvariantIterationCount(const Loop *L);
1374 /// getIterationCount - If the specified loop has a predictable iteration
1375 /// count, return it. Note that it is not valid to call this method on a
1376 /// loop without a loop-invariant iteration count.
1377 SCEVHandle getIterationCount(const Loop *L);
1379 /// deleteValueFromRecords - This method should be called by the
1380 /// client before it removes a value from the program, to make sure
1381 /// that no dangling references are left around.
1382 void deleteValueFromRecords(Value *V);
1385 /// createSCEV - We know that there is no SCEV for the specified value.
1386 /// Analyze the expression.
1387 SCEVHandle createSCEV(Value *V);
1389 /// createNodeForPHI - Provide the special handling we need to analyze PHI
1391 SCEVHandle createNodeForPHI(PHINode *PN);
1393 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value
1394 /// for the specified instruction and replaces any references to the
1395 /// symbolic value SymName with the specified value. This is used during
1397 void ReplaceSymbolicValueWithConcrete(Instruction *I,
1398 const SCEVHandle &SymName,
1399 const SCEVHandle &NewVal);
1401 /// ComputeIterationCount - Compute the number of times the specified loop
1403 SCEVHandle ComputeIterationCount(const Loop *L);
1405 /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
1406 /// 'icmp op load X, cst', try to see if we can compute the trip count.
1407 SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI,
1410 ICmpInst::Predicate p);
1412 /// ComputeIterationCountExhaustively - If the trip is known to execute a
1413 /// constant number of times (the condition evolves only from constants),
1414 /// try to evaluate a few iterations of the loop until we get the exit
1415 /// condition gets a value of ExitWhen (true or false). If we cannot
1416 /// evaluate the trip count of the loop, return UnknownValue.
1417 SCEVHandle ComputeIterationCountExhaustively(const Loop *L, Value *Cond,
1420 /// HowFarToZero - Return the number of times a backedge comparing the
1421 /// specified value to zero will execute. If not computable, return
1423 SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
1425 /// HowFarToNonZero - Return the number of times a backedge checking the
1426 /// specified value for nonzero will execute. If not computable, return
1428 SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
1430 /// HowManyLessThans - Return the number of times a backedge containing the
1431 /// specified less-than comparison will execute. If not computable, return
1432 /// UnknownValue. isSigned specifies whether the less-than is signed.
1433 SCEVHandle HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L,
1436 /// executesAtLeastOnce - Test whether entry to the loop is protected by
1437 /// a conditional between LHS and RHS.
1438 bool executesAtLeastOnce(const Loop *L, bool isSigned, SCEV *LHS, SCEV *RHS);
1440 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
1441 /// in the header of its containing loop, we know the loop executes a
1442 /// constant number of times, and the PHI node is just a recurrence
1443 /// involving constants, fold it.
1444 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its,
1449 //===----------------------------------------------------------------------===//
1450 // Basic SCEV Analysis and PHI Idiom Recognition Code
1453 /// deleteValueFromRecords - This method should be called by the
1454 /// client before it removes an instruction from the program, to make sure
1455 /// that no dangling references are left around.
1456 void ScalarEvolutionsImpl::deleteValueFromRecords(Value *V) {
1457 SmallVector<Value *, 16> Worklist;
1459 if (Scalars.erase(V)) {
1460 if (PHINode *PN = dyn_cast<PHINode>(V))
1461 ConstantEvolutionLoopExitValue.erase(PN);
1462 Worklist.push_back(V);
1465 while (!Worklist.empty()) {
1466 Value *VV = Worklist.back();
1467 Worklist.pop_back();
1469 for (Instruction::use_iterator UI = VV->use_begin(), UE = VV->use_end();
1471 Instruction *Inst = cast<Instruction>(*UI);
1472 if (Scalars.erase(Inst)) {
1473 if (PHINode *PN = dyn_cast<PHINode>(VV))
1474 ConstantEvolutionLoopExitValue.erase(PN);
1475 Worklist.push_back(Inst);
1482 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1483 /// expression and create a new one.
1484 SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
1485 assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
1487 std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
1488 if (I != Scalars.end()) return I->second;
1489 SCEVHandle S = createSCEV(V);
1490 Scalars.insert(std::make_pair(V, S));
1494 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value for
1495 /// the specified instruction and replaces any references to the symbolic value
1496 /// SymName with the specified value. This is used during PHI resolution.
1497 void ScalarEvolutionsImpl::
1498 ReplaceSymbolicValueWithConcrete(Instruction *I, const SCEVHandle &SymName,
1499 const SCEVHandle &NewVal) {
1500 std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
1501 if (SI == Scalars.end()) return;
1504 SI->second->replaceSymbolicValuesWithConcrete(SymName, NewVal, SE);
1505 if (NV == SI->second) return; // No change.
1507 SI->second = NV; // Update the scalars map!
1509 // Any instruction values that use this instruction might also need to be
1511 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1513 ReplaceSymbolicValueWithConcrete(cast<Instruction>(*UI), SymName, NewVal);
1516 /// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in
1517 /// a loop header, making it a potential recurrence, or it doesn't.
1519 SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
1520 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized.
1521 if (const Loop *L = LI.getLoopFor(PN->getParent()))
1522 if (L->getHeader() == PN->getParent()) {
1523 // If it lives in the loop header, it has two incoming values, one
1524 // from outside the loop, and one from inside.
1525 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
1526 unsigned BackEdge = IncomingEdge^1;
1528 // While we are analyzing this PHI node, handle its value symbolically.
1529 SCEVHandle SymbolicName = SE.getUnknown(PN);
1530 assert(Scalars.find(PN) == Scalars.end() &&
1531 "PHI node already processed?");
1532 Scalars.insert(std::make_pair(PN, SymbolicName));
1534 // Using this symbolic name for the PHI, analyze the value coming around
1536 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
1538 // NOTE: If BEValue is loop invariant, we know that the PHI node just
1539 // has a special value for the first iteration of the loop.
1541 // If the value coming around the backedge is an add with the symbolic
1542 // value we just inserted, then we found a simple induction variable!
1543 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
1544 // If there is a single occurrence of the symbolic value, replace it
1545 // with a recurrence.
1546 unsigned FoundIndex = Add->getNumOperands();
1547 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1548 if (Add->getOperand(i) == SymbolicName)
1549 if (FoundIndex == e) {
1554 if (FoundIndex != Add->getNumOperands()) {
1555 // Create an add with everything but the specified operand.
1556 std::vector<SCEVHandle> Ops;
1557 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1558 if (i != FoundIndex)
1559 Ops.push_back(Add->getOperand(i));
1560 SCEVHandle Accum = SE.getAddExpr(Ops);
1562 // This is not a valid addrec if the step amount is varying each
1563 // loop iteration, but is not itself an addrec in this loop.
1564 if (Accum->isLoopInvariant(L) ||
1565 (isa<SCEVAddRecExpr>(Accum) &&
1566 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
1567 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1568 SCEVHandle PHISCEV = SE.getAddRecExpr(StartVal, Accum, L);
1570 // Okay, for the entire analysis of this edge we assumed the PHI
1571 // to be symbolic. We now need to go back and update all of the
1572 // entries for the scalars that use the PHI (except for the PHI
1573 // itself) to use the new analyzed value instead of the "symbolic"
1575 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
1579 } else if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(BEValue)) {
1580 // Otherwise, this could be a loop like this:
1581 // i = 0; for (j = 1; ..; ++j) { .... i = j; }
1582 // In this case, j = {1,+,1} and BEValue is j.
1583 // Because the other in-value of i (0) fits the evolution of BEValue
1584 // i really is an addrec evolution.
1585 if (AddRec->getLoop() == L && AddRec->isAffine()) {
1586 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1588 // If StartVal = j.start - j.stride, we can use StartVal as the
1589 // initial step of the addrec evolution.
1590 if (StartVal == SE.getMinusSCEV(AddRec->getOperand(0),
1591 AddRec->getOperand(1))) {
1592 SCEVHandle PHISCEV =
1593 SE.getAddRecExpr(StartVal, AddRec->getOperand(1), L);
1595 // Okay, for the entire analysis of this edge we assumed the PHI
1596 // to be symbolic. We now need to go back and update all of the
1597 // entries for the scalars that use the PHI (except for the PHI
1598 // itself) to use the new analyzed value instead of the "symbolic"
1600 ReplaceSymbolicValueWithConcrete(PN, SymbolicName, PHISCEV);
1606 return SymbolicName;
1609 // If it's not a loop phi, we can't handle it yet.
1610 return SE.getUnknown(PN);
1613 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
1614 /// guaranteed to end in (at every loop iteration). It is, at the same time,
1615 /// the minimum number of times S is divisible by 2. For example, given {4,+,8}
1616 /// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S.
1617 static uint32_t GetMinTrailingZeros(SCEVHandle S) {
1618 if (SCEVConstant *C = dyn_cast<SCEVConstant>(S))
1619 return C->getValue()->getValue().countTrailingZeros();
1621 if (SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
1622 return std::min(GetMinTrailingZeros(T->getOperand()), T->getBitWidth());
1624 if (SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
1625 uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1626 return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1629 if (SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
1630 uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
1631 return OpRes == E->getOperand()->getBitWidth() ? E->getBitWidth() : OpRes;
1634 if (SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
1635 // The result is the min of all operands results.
1636 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1637 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1638 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1642 if (SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
1643 // The result is the sum of all operands results.
1644 uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
1645 uint32_t BitWidth = M->getBitWidth();
1646 for (unsigned i = 1, e = M->getNumOperands();
1647 SumOpRes != BitWidth && i != e; ++i)
1648 SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)),
1653 if (SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
1654 // The result is the min of all operands results.
1655 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
1656 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
1657 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
1661 if (SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
1662 // The result is the min of all operands results.
1663 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1664 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1665 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1669 if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
1670 // The result is the min of all operands results.
1671 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
1672 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
1673 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
1677 // SCEVUDivExpr, SCEVUnknown
1681 /// createSCEV - We know that there is no SCEV for the specified value.
1682 /// Analyze the expression.
1684 SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
1685 if (!isa<IntegerType>(V->getType()))
1686 return SE.getUnknown(V);
1688 unsigned Opcode = Instruction::UserOp1;
1689 if (Instruction *I = dyn_cast<Instruction>(V))
1690 Opcode = I->getOpcode();
1691 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
1692 Opcode = CE->getOpcode();
1694 return SE.getUnknown(V);
1696 User *U = cast<User>(V);
1698 case Instruction::Add:
1699 return SE.getAddExpr(getSCEV(U->getOperand(0)),
1700 getSCEV(U->getOperand(1)));
1701 case Instruction::Mul:
1702 return SE.getMulExpr(getSCEV(U->getOperand(0)),
1703 getSCEV(U->getOperand(1)));
1704 case Instruction::UDiv:
1705 return SE.getUDivExpr(getSCEV(U->getOperand(0)),
1706 getSCEV(U->getOperand(1)));
1707 case Instruction::Sub:
1708 return SE.getMinusSCEV(getSCEV(U->getOperand(0)),
1709 getSCEV(U->getOperand(1)));
1710 case Instruction::Or:
1711 // If the RHS of the Or is a constant, we may have something like:
1712 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
1713 // optimizations will transparently handle this case.
1715 // In order for this transformation to be safe, the LHS must be of the
1716 // form X*(2^n) and the Or constant must be less than 2^n.
1717 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
1718 SCEVHandle LHS = getSCEV(U->getOperand(0));
1719 const APInt &CIVal = CI->getValue();
1720 if (GetMinTrailingZeros(LHS) >=
1721 (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
1722 return SE.getAddExpr(LHS, getSCEV(U->getOperand(1)));
1725 case Instruction::Xor:
1726 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
1727 // If the RHS of the xor is a signbit, then this is just an add.
1728 // Instcombine turns add of signbit into xor as a strength reduction step.
1729 if (CI->getValue().isSignBit())
1730 return SE.getAddExpr(getSCEV(U->getOperand(0)),
1731 getSCEV(U->getOperand(1)));
1733 // If the RHS of xor is -1, then this is a not operation.
1734 else if (CI->isAllOnesValue())
1735 return SE.getNotSCEV(getSCEV(U->getOperand(0)));
1739 case Instruction::Shl:
1740 // Turn shift left of a constant amount into a multiply.
1741 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->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(U->getOperand(0)), getSCEV(X));
1749 case Instruction::LShr:
1750 // Turn logical shift right of a constant into a unsigned divide.
1751 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
1752 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
1753 Constant *X = ConstantInt::get(
1754 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
1755 return SE.getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X));
1759 case Instruction::Trunc:
1760 return SE.getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
1762 case Instruction::ZExt:
1763 return SE.getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
1765 case Instruction::SExt:
1766 return SE.getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
1768 case Instruction::BitCast:
1769 // BitCasts are no-op casts so we just eliminate the cast.
1770 if (U->getType()->isInteger() &&
1771 U->getOperand(0)->getType()->isInteger())
1772 return getSCEV(U->getOperand(0));
1775 case Instruction::PHI:
1776 return createNodeForPHI(cast<PHINode>(U));
1778 case Instruction::Select:
1779 // This could be a smax or umax that was lowered earlier.
1780 // Try to recover it.
1781 if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
1782 Value *LHS = ICI->getOperand(0);
1783 Value *RHS = ICI->getOperand(1);
1784 switch (ICI->getPredicate()) {
1785 case ICmpInst::ICMP_SLT:
1786 case ICmpInst::ICMP_SLE:
1787 std::swap(LHS, RHS);
1789 case ICmpInst::ICMP_SGT:
1790 case ICmpInst::ICMP_SGE:
1791 if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
1792 return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
1793 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
1794 // -smax(-x, -y) == smin(x, y).
1795 return SE.getNegativeSCEV(SE.getSMaxExpr(
1796 SE.getNegativeSCEV(getSCEV(LHS)),
1797 SE.getNegativeSCEV(getSCEV(RHS))));
1799 case ICmpInst::ICMP_ULT:
1800 case ICmpInst::ICMP_ULE:
1801 std::swap(LHS, RHS);
1803 case ICmpInst::ICMP_UGT:
1804 case ICmpInst::ICMP_UGE:
1805 if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
1806 return SE.getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
1807 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
1808 // ~umax(~x, ~y) == umin(x, y)
1809 return SE.getNotSCEV(SE.getUMaxExpr(SE.getNotSCEV(getSCEV(LHS)),
1810 SE.getNotSCEV(getSCEV(RHS))));
1817 default: // We cannot analyze this expression.
1821 return SE.getUnknown(V);
1826 //===----------------------------------------------------------------------===//
1827 // Iteration Count Computation Code
1830 /// getIterationCount - If the specified loop has a predictable iteration
1831 /// count, return it. Note that it is not valid to call this method on a
1832 /// loop without a loop-invariant iteration count.
1833 SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
1834 std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
1835 if (I == IterationCounts.end()) {
1836 SCEVHandle ItCount = ComputeIterationCount(L);
1837 I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
1838 if (ItCount != UnknownValue) {
1839 assert(ItCount->isLoopInvariant(L) &&
1840 "Computed trip count isn't loop invariant for loop!");
1841 ++NumTripCountsComputed;
1842 } else if (isa<PHINode>(L->getHeader()->begin())) {
1843 // Only count loops that have phi nodes as not being computable.
1844 ++NumTripCountsNotComputed;
1850 /// ComputeIterationCount - Compute the number of times the specified loop
1852 SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
1853 // If the loop has a non-one exit block count, we can't analyze it.
1854 SmallVector<BasicBlock*, 8> ExitBlocks;
1855 L->getExitBlocks(ExitBlocks);
1856 if (ExitBlocks.size() != 1) return UnknownValue;
1858 // Okay, there is one exit block. Try to find the condition that causes the
1859 // loop to be exited.
1860 BasicBlock *ExitBlock = ExitBlocks[0];
1862 BasicBlock *ExitingBlock = 0;
1863 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
1865 if (L->contains(*PI)) {
1866 if (ExitingBlock == 0)
1869 return UnknownValue; // More than one block exiting!
1871 assert(ExitingBlock && "No exits from loop, something is broken!");
1873 // Okay, we've computed the exiting block. See what condition causes us to
1876 // FIXME: we should be able to handle switch instructions (with a single exit)
1877 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1878 if (ExitBr == 0) return UnknownValue;
1879 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
1881 // At this point, we know we have a conditional branch that determines whether
1882 // the loop is exited. However, we don't know if the branch is executed each
1883 // time through the loop. If not, then the execution count of the branch will
1884 // not be equal to the trip count of the loop.
1886 // Currently we check for this by checking to see if the Exit branch goes to
1887 // the loop header. If so, we know it will always execute the same number of
1888 // times as the loop. We also handle the case where the exit block *is* the
1889 // loop header. This is common for un-rotated loops. More extensive analysis
1890 // could be done to handle more cases here.
1891 if (ExitBr->getSuccessor(0) != L->getHeader() &&
1892 ExitBr->getSuccessor(1) != L->getHeader() &&
1893 ExitBr->getParent() != L->getHeader())
1894 return UnknownValue;
1896 ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
1898 // If it's not an integer comparison then compute it the hard way.
1899 // Note that ICmpInst deals with pointer comparisons too so we must check
1900 // the type of the operand.
1901 if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
1902 return ComputeIterationCountExhaustively(L, ExitBr->getCondition(),
1903 ExitBr->getSuccessor(0) == ExitBlock);
1905 // If the condition was exit on true, convert the condition to exit on false
1906 ICmpInst::Predicate Cond;
1907 if (ExitBr->getSuccessor(1) == ExitBlock)
1908 Cond = ExitCond->getPredicate();
1910 Cond = ExitCond->getInversePredicate();
1912 // Handle common loops like: for (X = "string"; *X; ++X)
1913 if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
1914 if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
1916 ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
1917 if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
1920 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
1921 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
1923 // Try to evaluate any dependencies out of the loop.
1924 SCEVHandle Tmp = getSCEVAtScope(LHS, L);
1925 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
1926 Tmp = getSCEVAtScope(RHS, L);
1927 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
1929 // At this point, we would like to compute how many iterations of the
1930 // loop the predicate will return true for these inputs.
1931 if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) {
1932 // If there is a constant, force it into the RHS.
1933 std::swap(LHS, RHS);
1934 Cond = ICmpInst::getSwappedPredicate(Cond);
1937 // FIXME: think about handling pointer comparisons! i.e.:
1938 // while (P != P+100) ++P;
1940 // If we have a comparison of a chrec against a constant, try to use value
1941 // ranges to answer this query.
1942 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
1943 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
1944 if (AddRec->getLoop() == L) {
1945 // Form the comparison range using the constant of the correct type so
1946 // that the ConstantRange class knows to do a signed or unsigned
1948 ConstantInt *CompVal = RHSC->getValue();
1949 const Type *RealTy = ExitCond->getOperand(0)->getType();
1950 CompVal = dyn_cast<ConstantInt>(
1951 ConstantExpr::getBitCast(CompVal, RealTy));
1953 // Form the constant range.
1954 ConstantRange CompRange(
1955 ICmpInst::makeConstantRange(Cond, CompVal->getValue()));
1957 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange, SE);
1958 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
1963 case ICmpInst::ICMP_NE: { // while (X != Y)
1964 // Convert to: while (X-Y != 0)
1965 SCEVHandle TC = HowFarToZero(SE.getMinusSCEV(LHS, RHS), L);
1966 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1969 case ICmpInst::ICMP_EQ: {
1970 // Convert to: while (X-Y == 0) // while (X == Y)
1971 SCEVHandle TC = HowFarToNonZero(SE.getMinusSCEV(LHS, RHS), L);
1972 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1975 case ICmpInst::ICMP_SLT: {
1976 SCEVHandle TC = HowManyLessThans(LHS, RHS, L, true);
1977 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1980 case ICmpInst::ICMP_SGT: {
1981 SCEVHandle TC = HowManyLessThans(SE.getNegativeSCEV(LHS),
1982 SE.getNegativeSCEV(RHS), L, true);
1983 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1986 case ICmpInst::ICMP_ULT: {
1987 SCEVHandle TC = HowManyLessThans(LHS, RHS, L, false);
1988 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1991 case ICmpInst::ICMP_UGT: {
1992 SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
1993 SE.getNotSCEV(RHS), L, false);
1994 if (!isa<SCEVCouldNotCompute>(TC)) return TC;
1999 cerr << "ComputeIterationCount ";
2000 if (ExitCond->getOperand(0)->getType()->isUnsigned())
2001 cerr << "[unsigned] ";
2003 << Instruction::getOpcodeName(Instruction::ICmp)
2004 << " " << *RHS << "\n";
2008 return ComputeIterationCountExhaustively(L, ExitCond,
2009 ExitBr->getSuccessor(0) == ExitBlock);
2012 static ConstantInt *
2013 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
2014 ScalarEvolution &SE) {
2015 SCEVHandle InVal = SE.getConstant(C);
2016 SCEVHandle Val = AddRec->evaluateAtIteration(InVal, SE);
2017 assert(isa<SCEVConstant>(Val) &&
2018 "Evaluation of SCEV at constant didn't fold correctly?");
2019 return cast<SCEVConstant>(Val)->getValue();
2022 /// GetAddressedElementFromGlobal - Given a global variable with an initializer
2023 /// and a GEP expression (missing the pointer index) indexing into it, return
2024 /// the addressed element of the initializer or null if the index expression is
2027 GetAddressedElementFromGlobal(GlobalVariable *GV,
2028 const std::vector<ConstantInt*> &Indices) {
2029 Constant *Init = GV->getInitializer();
2030 for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
2031 uint64_t Idx = Indices[i]->getZExtValue();
2032 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
2033 assert(Idx < CS->getNumOperands() && "Bad struct index!");
2034 Init = cast<Constant>(CS->getOperand(Idx));
2035 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
2036 if (Idx >= CA->getNumOperands()) return 0; // Bogus program
2037 Init = cast<Constant>(CA->getOperand(Idx));
2038 } else if (isa<ConstantAggregateZero>(Init)) {
2039 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
2040 assert(Idx < STy->getNumElements() && "Bad struct index!");
2041 Init = Constant::getNullValue(STy->getElementType(Idx));
2042 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
2043 if (Idx >= ATy->getNumElements()) return 0; // Bogus program
2044 Init = Constant::getNullValue(ATy->getElementType());
2046 assert(0 && "Unknown constant aggregate type!");
2050 return 0; // Unknown initializer type
2056 /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
2057 /// 'icmp op load X, cst', try to see if we can compute the trip count.
2058 SCEVHandle ScalarEvolutionsImpl::
2059 ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
2061 ICmpInst::Predicate predicate) {
2062 if (LI->isVolatile()) return UnknownValue;
2064 // Check to see if the loaded pointer is a getelementptr of a global.
2065 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
2066 if (!GEP) return UnknownValue;
2068 // Make sure that it is really a constant global we are gepping, with an
2069 // initializer, and make sure the first IDX is really 0.
2070 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
2071 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
2072 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
2073 !cast<Constant>(GEP->getOperand(1))->isNullValue())
2074 return UnknownValue;
2076 // Okay, we allow one non-constant index into the GEP instruction.
2078 std::vector<ConstantInt*> Indexes;
2079 unsigned VarIdxNum = 0;
2080 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
2081 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
2082 Indexes.push_back(CI);
2083 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
2084 if (VarIdx) return UnknownValue; // Multiple non-constant idx's.
2085 VarIdx = GEP->getOperand(i);
2087 Indexes.push_back(0);
2090 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
2091 // Check to see if X is a loop variant variable value now.
2092 SCEVHandle Idx = getSCEV(VarIdx);
2093 SCEVHandle Tmp = getSCEVAtScope(Idx, L);
2094 if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
2096 // We can only recognize very limited forms of loop index expressions, in
2097 // particular, only affine AddRec's like {C1,+,C2}.
2098 SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
2099 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
2100 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
2101 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
2102 return UnknownValue;
2104 unsigned MaxSteps = MaxBruteForceIterations;
2105 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
2106 ConstantInt *ItCst =
2107 ConstantInt::get(IdxExpr->getType(), IterationNum);
2108 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, SE);
2110 // Form the GEP offset.
2111 Indexes[VarIdxNum] = Val;
2113 Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
2114 if (Result == 0) break; // Cannot compute!
2116 // Evaluate the condition for this iteration.
2117 Result = ConstantExpr::getICmp(predicate, Result, RHS);
2118 if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure
2119 if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
2121 cerr << "\n***\n*** Computed loop count " << *ItCst
2122 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
2125 ++NumArrayLenItCounts;
2126 return SE.getConstant(ItCst); // Found terminating iteration!
2129 return UnknownValue;
2133 /// CanConstantFold - Return true if we can constant fold an instruction of the
2134 /// specified type, assuming that all operands were constants.
2135 static bool CanConstantFold(const Instruction *I) {
2136 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
2137 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
2140 if (const CallInst *CI = dyn_cast<CallInst>(I))
2141 if (const Function *F = CI->getCalledFunction())
2142 return canConstantFoldCallTo(F);
2146 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
2147 /// in the loop that V is derived from. We allow arbitrary operations along the
2148 /// way, but the operands of an operation must either be constants or a value
2149 /// derived from a constant PHI. If this expression does not fit with these
2150 /// constraints, return null.
2151 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
2152 // If this is not an instruction, or if this is an instruction outside of the
2153 // loop, it can't be derived from a loop PHI.
2154 Instruction *I = dyn_cast<Instruction>(V);
2155 if (I == 0 || !L->contains(I->getParent())) return 0;
2157 if (PHINode *PN = dyn_cast<PHINode>(I)) {
2158 if (L->getHeader() == I->getParent())
2161 // We don't currently keep track of the control flow needed to evaluate
2162 // PHIs, so we cannot handle PHIs inside of loops.
2166 // If we won't be able to constant fold this expression even if the operands
2167 // are constants, return early.
2168 if (!CanConstantFold(I)) return 0;
2170 // Otherwise, we can evaluate this instruction if all of its operands are
2171 // constant or derived from a PHI node themselves.
2173 for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op)
2174 if (!(isa<Constant>(I->getOperand(Op)) ||
2175 isa<GlobalValue>(I->getOperand(Op)))) {
2176 PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L);
2177 if (P == 0) return 0; // Not evolving from PHI
2181 return 0; // Evolving from multiple different PHIs.
2184 // This is a expression evolving from a constant PHI!
2188 /// EvaluateExpression - Given an expression that passes the
2189 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
2190 /// in the loop has the value PHIVal. If we can't fold this expression for some
2191 /// reason, return null.
2192 static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
2193 if (isa<PHINode>(V)) return PHIVal;
2194 if (Constant *C = dyn_cast<Constant>(V)) return C;
2195 Instruction *I = cast<Instruction>(V);
2197 std::vector<Constant*> Operands;
2198 Operands.resize(I->getNumOperands());
2200 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2201 Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal);
2202 if (Operands[i] == 0) return 0;
2205 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2206 return ConstantFoldCompareInstOperands(CI->getPredicate(),
2207 &Operands[0], Operands.size());
2209 return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2210 &Operands[0], Operands.size());
2213 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
2214 /// in the header of its containing loop, we know the loop executes a
2215 /// constant number of times, and the PHI node is just a recurrence
2216 /// involving constants, fold it.
2217 Constant *ScalarEvolutionsImpl::
2218 getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& Its, const Loop *L){
2219 std::map<PHINode*, Constant*>::iterator I =
2220 ConstantEvolutionLoopExitValue.find(PN);
2221 if (I != ConstantEvolutionLoopExitValue.end())
2224 if (Its.ugt(APInt(Its.getBitWidth(),MaxBruteForceIterations)))
2225 return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it.
2227 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
2229 // Since the loop is canonicalized, the PHI node must have two entries. One
2230 // entry must be a constant (coming in from outside of the loop), and the
2231 // second must be derived from the same PHI.
2232 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2233 Constant *StartCST =
2234 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2236 return RetVal = 0; // Must be a constant.
2238 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2239 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2241 return RetVal = 0; // Not derived from same PHI.
2243 // Execute the loop symbolically to determine the exit value.
2244 if (Its.getActiveBits() >= 32)
2245 return RetVal = 0; // More than 2^32-1 iterations?? Not doing it!
2247 unsigned NumIterations = Its.getZExtValue(); // must be in range
2248 unsigned IterationNum = 0;
2249 for (Constant *PHIVal = StartCST; ; ++IterationNum) {
2250 if (IterationNum == NumIterations)
2251 return RetVal = PHIVal; // Got exit value!
2253 // Compute the value of the PHI node for the next iteration.
2254 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2255 if (NextPHI == PHIVal)
2256 return RetVal = NextPHI; // Stopped evolving!
2258 return 0; // Couldn't evaluate!
2263 /// ComputeIterationCountExhaustively - If the trip is known to execute a
2264 /// constant number of times (the condition evolves only from constants),
2265 /// try to evaluate a few iterations of the loop until we get the exit
2266 /// condition gets a value of ExitWhen (true or false). If we cannot
2267 /// evaluate the trip count of the loop, return UnknownValue.
2268 SCEVHandle ScalarEvolutionsImpl::
2269 ComputeIterationCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen) {
2270 PHINode *PN = getConstantEvolvingPHI(Cond, L);
2271 if (PN == 0) return UnknownValue;
2273 // Since the loop is canonicalized, the PHI node must have two entries. One
2274 // entry must be a constant (coming in from outside of the loop), and the
2275 // second must be derived from the same PHI.
2276 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
2277 Constant *StartCST =
2278 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
2279 if (StartCST == 0) return UnknownValue; // Must be a constant.
2281 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
2282 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
2283 if (PN2 != PN) return UnknownValue; // Not derived from same PHI.
2285 // Okay, we find a PHI node that defines the trip count of this loop. Execute
2286 // the loop symbolically to determine when the condition gets a value of
2288 unsigned IterationNum = 0;
2289 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
2290 for (Constant *PHIVal = StartCST;
2291 IterationNum != MaxIterations; ++IterationNum) {
2292 ConstantInt *CondVal =
2293 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
2295 // Couldn't symbolically evaluate.
2296 if (!CondVal) return UnknownValue;
2298 if (CondVal->getValue() == uint64_t(ExitWhen)) {
2299 ConstantEvolutionLoopExitValue[PN] = PHIVal;
2300 ++NumBruteForceTripCountsComputed;
2301 return SE.getConstant(ConstantInt::get(Type::Int32Ty, IterationNum));
2304 // Compute the value of the PHI node for the next iteration.
2305 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
2306 if (NextPHI == 0 || NextPHI == PHIVal)
2307 return UnknownValue; // Couldn't evaluate or not making progress...
2311 // Too many iterations were needed to evaluate.
2312 return UnknownValue;
2315 /// getSCEVAtScope - Compute the value of the specified expression within the
2316 /// indicated loop (which may be null to indicate in no loop). If the
2317 /// expression cannot be evaluated, return UnknownValue.
2318 SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
2319 // FIXME: this should be turned into a virtual method on SCEV!
2321 if (isa<SCEVConstant>(V)) return V;
2323 // If this instruction is evolved from a constant-evolving PHI, compute the
2324 // exit value from the loop without using SCEVs.
2325 if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
2326 if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
2327 const Loop *LI = this->LI[I->getParent()];
2328 if (LI && LI->getParentLoop() == L) // Looking for loop exit value.
2329 if (PHINode *PN = dyn_cast<PHINode>(I))
2330 if (PN->getParent() == LI->getHeader()) {
2331 // Okay, there is no closed form solution for the PHI node. Check
2332 // to see if the loop that contains it has a known iteration count.
2333 // If so, we may be able to force computation of the exit value.
2334 SCEVHandle IterationCount = getIterationCount(LI);
2335 if (SCEVConstant *ICC = dyn_cast<SCEVConstant>(IterationCount)) {
2336 // Okay, we know how many times the containing loop executes. If
2337 // this is a constant evolving PHI node, get the final value at
2338 // the specified iteration number.
2339 Constant *RV = getConstantEvolutionLoopExitValue(PN,
2340 ICC->getValue()->getValue(),
2342 if (RV) return SE.getUnknown(RV);
2346 // Okay, this is an expression that we cannot symbolically evaluate
2347 // into a SCEV. Check to see if it's possible to symbolically evaluate
2348 // the arguments into constants, and if so, try to constant propagate the
2349 // result. This is particularly useful for computing loop exit values.
2350 if (CanConstantFold(I)) {
2351 std::vector<Constant*> Operands;
2352 Operands.reserve(I->getNumOperands());
2353 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
2354 Value *Op = I->getOperand(i);
2355 if (Constant *C = dyn_cast<Constant>(Op)) {
2356 Operands.push_back(C);
2358 // If any of the operands is non-constant and if they are
2359 // non-integer, don't even try to analyze them with scev techniques.
2360 if (!isa<IntegerType>(Op->getType()))
2363 SCEVHandle OpV = getSCEVAtScope(getSCEV(Op), L);
2364 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV))
2365 Operands.push_back(ConstantExpr::getIntegerCast(SC->getValue(),
2368 else if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) {
2369 if (Constant *C = dyn_cast<Constant>(SU->getValue()))
2370 Operands.push_back(ConstantExpr::getIntegerCast(C,
2382 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
2383 C = ConstantFoldCompareInstOperands(CI->getPredicate(),
2384 &Operands[0], Operands.size());
2386 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
2387 &Operands[0], Operands.size());
2388 return SE.getUnknown(C);
2392 // This is some other type of SCEVUnknown, just return it.
2396 if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
2397 // Avoid performing the look-up in the common case where the specified
2398 // expression has no loop-variant portions.
2399 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
2400 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2401 if (OpAtScope != Comm->getOperand(i)) {
2402 if (OpAtScope == UnknownValue) return UnknownValue;
2403 // Okay, at least one of these operands is loop variant but might be
2404 // foldable. Build a new instance of the folded commutative expression.
2405 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i);
2406 NewOps.push_back(OpAtScope);
2408 for (++i; i != e; ++i) {
2409 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
2410 if (OpAtScope == UnknownValue) return UnknownValue;
2411 NewOps.push_back(OpAtScope);
2413 if (isa<SCEVAddExpr>(Comm))
2414 return SE.getAddExpr(NewOps);
2415 if (isa<SCEVMulExpr>(Comm))
2416 return SE.getMulExpr(NewOps);
2417 if (isa<SCEVSMaxExpr>(Comm))
2418 return SE.getSMaxExpr(NewOps);
2419 if (isa<SCEVUMaxExpr>(Comm))
2420 return SE.getUMaxExpr(NewOps);
2421 assert(0 && "Unknown commutative SCEV type!");
2424 // If we got here, all operands are loop invariant.
2428 if (SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
2429 SCEVHandle LHS = getSCEVAtScope(Div->getLHS(), L);
2430 if (LHS == UnknownValue) return LHS;
2431 SCEVHandle RHS = getSCEVAtScope(Div->getRHS(), L);
2432 if (RHS == UnknownValue) return RHS;
2433 if (LHS == Div->getLHS() && RHS == Div->getRHS())
2434 return Div; // must be loop invariant
2435 return SE.getUDivExpr(LHS, RHS);
2438 // If this is a loop recurrence for a loop that does not contain L, then we
2439 // are dealing with the final value computed by the loop.
2440 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
2441 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
2442 // To evaluate this recurrence, we need to know how many times the AddRec
2443 // loop iterates. Compute this now.
2444 SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
2445 if (IterationCount == UnknownValue) return UnknownValue;
2446 IterationCount = SE.getTruncateOrZeroExtend(IterationCount,
2449 // If the value is affine, simplify the expression evaluation to just
2450 // Start + Step*IterationCount.
2451 if (AddRec->isAffine())
2452 return SE.getAddExpr(AddRec->getStart(),
2453 SE.getMulExpr(IterationCount,
2454 AddRec->getOperand(1)));
2456 // Otherwise, evaluate it the hard way.
2457 return AddRec->evaluateAtIteration(IterationCount, SE);
2459 return UnknownValue;
2462 //assert(0 && "Unknown SCEV type!");
2463 return UnknownValue;
2466 /// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the
2467 /// following equation:
2469 /// A * X = B (mod N)
2471 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of
2472 /// A and B isn't important.
2474 /// If the equation does not have a solution, SCEVCouldNotCompute is returned.
2475 static SCEVHandle SolveLinEquationWithOverflow(const APInt &A, const APInt &B,
2476 ScalarEvolution &SE) {
2477 uint32_t BW = A.getBitWidth();
2478 assert(BW == B.getBitWidth() && "Bit widths must be the same.");
2479 assert(A != 0 && "A must be non-zero.");
2483 // The gcd of A and N may have only one prime factor: 2. The number of
2484 // trailing zeros in A is its multiplicity
2485 uint32_t Mult2 = A.countTrailingZeros();
2488 // 2. Check if B is divisible by D.
2490 // B is divisible by D if and only if the multiplicity of prime factor 2 for B
2491 // is not less than multiplicity of this prime factor for D.
2492 if (B.countTrailingZeros() < Mult2)
2493 return new SCEVCouldNotCompute();
2495 // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
2498 // (N / D) may need BW+1 bits in its representation. Hence, we'll use this
2499 // bit width during computations.
2500 APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D
2501 APInt Mod(BW + 1, 0);
2502 Mod.set(BW - Mult2); // Mod = N / D
2503 APInt I = AD.multiplicativeInverse(Mod);
2505 // 4. Compute the minimum unsigned root of the equation:
2506 // I * (B / D) mod (N / D)
2507 APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod);
2509 // The result is guaranteed to be less than 2^BW so we may truncate it to BW
2511 return SE.getConstant(Result.trunc(BW));
2514 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
2515 /// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which
2516 /// might be the same) or two SCEVCouldNotCompute objects.
2518 static std::pair<SCEVHandle,SCEVHandle>
2519 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) {
2520 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
2521 SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
2522 SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
2523 SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
2525 // We currently can only solve this if the coefficients are constants.
2526 if (!LC || !MC || !NC) {
2527 SCEV *CNC = new SCEVCouldNotCompute();
2528 return std::make_pair(CNC, CNC);
2531 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
2532 const APInt &L = LC->getValue()->getValue();
2533 const APInt &M = MC->getValue()->getValue();
2534 const APInt &N = NC->getValue()->getValue();
2535 APInt Two(BitWidth, 2);
2536 APInt Four(BitWidth, 4);
2539 using namespace APIntOps;
2541 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
2542 // The B coefficient is M-N/2
2546 // The A coefficient is N/2
2547 APInt A(N.sdiv(Two));
2549 // Compute the B^2-4ac term.
2552 SqrtTerm -= Four * (A * C);
2554 // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest
2555 // integer value or else APInt::sqrt() will assert.
2556 APInt SqrtVal(SqrtTerm.sqrt());
2558 // Compute the two solutions for the quadratic formula.
2559 // The divisions must be performed as signed divisions.
2561 APInt TwoA( A << 1 );
2562 ConstantInt *Solution1 = ConstantInt::get((NegB + SqrtVal).sdiv(TwoA));
2563 ConstantInt *Solution2 = ConstantInt::get((NegB - SqrtVal).sdiv(TwoA));
2565 return std::make_pair(SE.getConstant(Solution1),
2566 SE.getConstant(Solution2));
2567 } // end APIntOps namespace
2570 /// HowFarToZero - Return the number of times a backedge comparing the specified
2571 /// value to zero will execute. If not computable, return UnknownValue
2572 SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
2573 // If the value is a constant
2574 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2575 // If the value is already zero, the branch will execute zero times.
2576 if (C->getValue()->isZero()) return C;
2577 return UnknownValue; // Otherwise it will loop infinitely.
2580 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
2581 if (!AddRec || AddRec->getLoop() != L)
2582 return UnknownValue;
2584 if (AddRec->isAffine()) {
2585 // If this is an affine expression, the execution count of this branch is
2586 // the minimum unsigned root of the following equation:
2588 // Start + Step*N = 0 (mod 2^BW)
2592 // Step*N = -Start (mod 2^BW)
2594 // where BW is the common bit width of Start and Step.
2596 // Get the initial value for the loop.
2597 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
2598 if (isa<SCEVCouldNotCompute>(Start)) return UnknownValue;
2600 SCEVHandle Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop());
2602 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
2603 // For now we handle only constant steps.
2605 // First, handle unitary steps.
2606 if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so:
2607 return SE.getNegativeSCEV(Start); // N = -Start (as unsigned)
2608 if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so:
2609 return Start; // N = Start (as unsigned)
2611 // Then, try to solve the above equation provided that Start is constant.
2612 if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
2613 return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
2614 -StartC->getValue()->getValue(),SE);
2616 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
2617 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
2618 // the quadratic equation to solve it.
2619 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec, SE);
2620 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2621 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2624 cerr << "HFTZ: " << *V << " - sol#1: " << *R1
2625 << " sol#2: " << *R2 << "\n";
2627 // Pick the smallest positive root value.
2628 if (ConstantInt *CB =
2629 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
2630 R1->getValue(), R2->getValue()))) {
2631 if (CB->getZExtValue() == false)
2632 std::swap(R1, R2); // R1 is the minimum root now.
2634 // We can only use this value if the chrec ends up with an exact zero
2635 // value at this index. When solving for "X*X != 5", for example, we
2636 // should not accept a root of 2.
2637 SCEVHandle Val = AddRec->evaluateAtIteration(R1, SE);
2639 return R1; // We found a quadratic root!
2644 return UnknownValue;
2647 /// HowFarToNonZero - Return the number of times a backedge checking the
2648 /// specified value for nonzero will execute. If not computable, return
2650 SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
2651 // Loops that look like: while (X == 0) are very strange indeed. We don't
2652 // handle them yet except for the trivial case. This could be expanded in the
2653 // future as needed.
2655 // If the value is a constant, check to see if it is known to be non-zero
2656 // already. If so, the backedge will execute zero times.
2657 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
2658 if (!C->getValue()->isNullValue())
2659 return SE.getIntegerSCEV(0, C->getType());
2660 return UnknownValue; // Otherwise it will loop infinitely.
2663 // We could implement others, but I really doubt anyone writes loops like
2664 // this, and if they did, they would already be constant folded.
2665 return UnknownValue;
2668 /// executesAtLeastOnce - Test whether entry to the loop is protected by
2669 /// a conditional between LHS and RHS.
2670 bool ScalarEvolutionsImpl::executesAtLeastOnce(const Loop *L, bool isSigned,
2671 SCEV *LHS, SCEV *RHS) {
2672 BasicBlock *Preheader = L->getLoopPreheader();
2673 BasicBlock *PreheaderDest = L->getHeader();
2674 if (Preheader == 0) return false;
2676 BranchInst *LoopEntryPredicate =
2677 dyn_cast<BranchInst>(Preheader->getTerminator());
2678 if (!LoopEntryPredicate) return false;
2680 // This might be a critical edge broken out. If the loop preheader ends in
2681 // an unconditional branch to the loop, check to see if the preheader has a
2682 // single predecessor, and if so, look for its terminator.
2683 while (LoopEntryPredicate->isUnconditional()) {
2684 PreheaderDest = Preheader;
2685 Preheader = Preheader->getSinglePredecessor();
2686 if (!Preheader) return false; // Multiple preds.
2688 LoopEntryPredicate =
2689 dyn_cast<BranchInst>(Preheader->getTerminator());
2690 if (!LoopEntryPredicate) return false;
2693 ICmpInst *ICI = dyn_cast<ICmpInst>(LoopEntryPredicate->getCondition());
2694 if (!ICI) return false;
2696 // Now that we found a conditional branch that dominates the loop, check to
2697 // see if it is the comparison we are looking for.
2698 Value *PreCondLHS = ICI->getOperand(0);
2699 Value *PreCondRHS = ICI->getOperand(1);
2700 ICmpInst::Predicate Cond;
2701 if (LoopEntryPredicate->getSuccessor(0) == PreheaderDest)
2702 Cond = ICI->getPredicate();
2704 Cond = ICI->getInversePredicate();
2707 case ICmpInst::ICMP_UGT:
2708 if (isSigned) return false;
2709 std::swap(PreCondLHS, PreCondRHS);
2710 Cond = ICmpInst::ICMP_ULT;
2712 case ICmpInst::ICMP_SGT:
2713 if (!isSigned) return false;
2714 std::swap(PreCondLHS, PreCondRHS);
2715 Cond = ICmpInst::ICMP_SLT;
2717 case ICmpInst::ICMP_ULT:
2718 if (isSigned) return false;
2720 case ICmpInst::ICMP_SLT:
2721 if (!isSigned) return false;
2727 if (!PreCondLHS->getType()->isInteger()) return false;
2729 return LHS == getSCEV(PreCondLHS) && RHS == getSCEV(PreCondRHS);
2732 /// HowManyLessThans - Return the number of times a backedge containing the
2733 /// specified less-than comparison will execute. If not computable, return
2735 SCEVHandle ScalarEvolutionsImpl::
2736 HowManyLessThans(SCEV *LHS, SCEV *RHS, const Loop *L, bool isSigned) {
2737 // Only handle: "ADDREC < LoopInvariant".
2738 if (!RHS->isLoopInvariant(L)) return UnknownValue;
2740 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
2741 if (!AddRec || AddRec->getLoop() != L)
2742 return UnknownValue;
2744 if (AddRec->isAffine()) {
2745 // FORNOW: We only support unit strides.
2746 SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
2747 if (AddRec->getOperand(1) != One)
2748 return UnknownValue;
2750 // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant
2751 // m. So, we count the number of iterations in which {n,+,1} < m is true.
2752 // Note that we cannot simply return max(m-n,0) because it's not safe to
2753 // treat m-n as signed nor unsigned due to overflow possibility.
2755 // First, we get the value of the LHS in the first iteration: n
2756 SCEVHandle Start = AddRec->getOperand(0);
2758 if (executesAtLeastOnce(L, isSigned,
2759 SE.getMinusSCEV(AddRec->getOperand(0), One), RHS)) {
2760 // Since we know that the condition is true in order to enter the loop,
2761 // we know that it will run exactly m-n times.
2762 return SE.getMinusSCEV(RHS, Start);
2764 // Then, we get the value of the LHS in the first iteration in which the
2765 // above condition doesn't hold. This equals to max(m,n).
2766 SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
2767 : SE.getUMaxExpr(RHS, Start);
2769 // Finally, we subtract these two values to get the number of times the
2770 // backedge is executed: max(m,n)-n.
2771 return SE.getMinusSCEV(End, Start);
2775 return UnknownValue;
2778 /// getNumIterationsInRange - Return the number of iterations of this loop that
2779 /// produce values in the specified constant range. Another way of looking at
2780 /// this is that it returns the first iteration number where the value is not in
2781 /// the condition, thus computing the exit count. If the iteration count can't
2782 /// be computed, an instance of SCEVCouldNotCompute is returned.
2783 SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
2784 ScalarEvolution &SE) const {
2785 if (Range.isFullSet()) // Infinite loop.
2786 return new SCEVCouldNotCompute();
2788 // If the start is a non-zero constant, shift the range to simplify things.
2789 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
2790 if (!SC->getValue()->isZero()) {
2791 std::vector<SCEVHandle> Operands(op_begin(), op_end());
2792 Operands[0] = SE.getIntegerSCEV(0, SC->getType());
2793 SCEVHandle Shifted = SE.getAddRecExpr(Operands, getLoop());
2794 if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
2795 return ShiftedAddRec->getNumIterationsInRange(
2796 Range.subtract(SC->getValue()->getValue()), SE);
2797 // This is strange and shouldn't happen.
2798 return new SCEVCouldNotCompute();
2801 // The only time we can solve this is when we have all constant indices.
2802 // Otherwise, we cannot determine the overflow conditions.
2803 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
2804 if (!isa<SCEVConstant>(getOperand(i)))
2805 return new SCEVCouldNotCompute();
2808 // Okay at this point we know that all elements of the chrec are constants and
2809 // that the start element is zero.
2811 // First check to see if the range contains zero. If not, the first
2813 if (!Range.contains(APInt(getBitWidth(),0)))
2814 return SE.getConstant(ConstantInt::get(getType(),0));
2817 // If this is an affine expression then we have this situation:
2818 // Solve {0,+,A} in Range === Ax in Range
2820 // We know that zero is in the range. If A is positive then we know that
2821 // the upper value of the range must be the first possible exit value.
2822 // If A is negative then the lower of the range is the last possible loop
2823 // value. Also note that we already checked for a full range.
2824 APInt One(getBitWidth(),1);
2825 APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
2826 APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();
2828 // The exit value should be (End+A)/A.
2829 APInt ExitVal = (End + A).udiv(A);
2830 ConstantInt *ExitValue = ConstantInt::get(ExitVal);
2832 // Evaluate at the exit value. If we really did fall out of the valid
2833 // range, then we computed our trip count, otherwise wrap around or other
2834 // things must have happened.
2835 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE);
2836 if (Range.contains(Val->getValue()))
2837 return new SCEVCouldNotCompute(); // Something strange happened
2839 // Ensure that the previous value is in the range. This is a sanity check.
2840 assert(Range.contains(
2841 EvaluateConstantChrecAtConstant(this,
2842 ConstantInt::get(ExitVal - One), SE)->getValue()) &&
2843 "Linear scev computation is off in a bad way!");
2844 return SE.getConstant(ExitValue);
2845 } else if (isQuadratic()) {
2846 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
2847 // quadratic equation to solve it. To do this, we must frame our problem in
2848 // terms of figuring out when zero is crossed, instead of when
2849 // Range.getUpper() is crossed.
2850 std::vector<SCEVHandle> NewOps(op_begin(), op_end());
2851 NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper()));
2852 SCEVHandle NewAddRec = SE.getAddRecExpr(NewOps, getLoop());
2854 // Next, solve the constructed addrec
2855 std::pair<SCEVHandle,SCEVHandle> Roots =
2856 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE);
2857 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
2858 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
2860 // Pick the smallest positive root value.
2861 if (ConstantInt *CB =
2862 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT,
2863 R1->getValue(), R2->getValue()))) {
2864 if (CB->getZExtValue() == false)
2865 std::swap(R1, R2); // R1 is the minimum root now.
2867 // Make sure the root is not off by one. The returned iteration should
2868 // not be in the range, but the previous one should be. When solving
2869 // for "X*X < 5", for example, we should not return a root of 2.
2870 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
2873 if (Range.contains(R1Val->getValue())) {
2874 // The next iteration must be out of the range...
2875 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()+1);
2877 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
2878 if (!Range.contains(R1Val->getValue()))
2879 return SE.getConstant(NextVal);
2880 return new SCEVCouldNotCompute(); // Something strange happened
2883 // If R1 was not in the range, then it is a good return value. Make
2884 // sure that R1-1 WAS in the range though, just in case.
2885 ConstantInt *NextVal = ConstantInt::get(R1->getValue()->getValue()-1);
2886 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE);
2887 if (Range.contains(R1Val->getValue()))
2889 return new SCEVCouldNotCompute(); // Something strange happened
2894 // Fallback, if this is a general polynomial, figure out the progression
2895 // through brute force: evaluate until we find an iteration that fails the
2896 // test. This is likely to be slow, but getting an accurate trip count is
2897 // incredibly important, we will be able to simplify the exit test a lot, and
2898 // we are almost guaranteed to get a trip count in this case.
2899 ConstantInt *TestVal = ConstantInt::get(getType(), 0);
2900 ConstantInt *EndVal = TestVal; // Stop when we wrap around.
2902 ++NumBruteForceEvaluations;
2903 SCEVHandle Val = evaluateAtIteration(SE.getConstant(TestVal), SE);
2904 if (!isa<SCEVConstant>(Val)) // This shouldn't happen.
2905 return new SCEVCouldNotCompute();
2907 // Check to see if we found the value!
2908 if (!Range.contains(cast<SCEVConstant>(Val)->getValue()->getValue()))
2909 return SE.getConstant(TestVal);
2911 // Increment to test the next index.
2912 TestVal = ConstantInt::get(TestVal->getValue()+1);
2913 } while (TestVal != EndVal);
2915 return new SCEVCouldNotCompute();
2920 //===----------------------------------------------------------------------===//
2921 // ScalarEvolution Class Implementation
2922 //===----------------------------------------------------------------------===//
2924 bool ScalarEvolution::runOnFunction(Function &F) {
2925 Impl = new ScalarEvolutionsImpl(*this, F, getAnalysis<LoopInfo>());
2929 void ScalarEvolution::releaseMemory() {
2930 delete (ScalarEvolutionsImpl*)Impl;
2934 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
2935 AU.setPreservesAll();
2936 AU.addRequiredTransitive<LoopInfo>();
2939 SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
2940 return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
2943 /// hasSCEV - Return true if the SCEV for this value has already been
2945 bool ScalarEvolution::hasSCEV(Value *V) const {
2946 return ((ScalarEvolutionsImpl*)Impl)->hasSCEV(V);
2950 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
2951 /// the specified value.
2952 void ScalarEvolution::setSCEV(Value *V, const SCEVHandle &H) {
2953 ((ScalarEvolutionsImpl*)Impl)->setSCEV(V, H);
2957 SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
2958 return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
2961 bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
2962 return !isa<SCEVCouldNotCompute>(getIterationCount(L));
2965 SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
2966 return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
2969 void ScalarEvolution::deleteValueFromRecords(Value *V) const {
2970 return ((ScalarEvolutionsImpl*)Impl)->deleteValueFromRecords(V);
2973 static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
2975 // Print all inner loops first
2976 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
2977 PrintLoopInfo(OS, SE, *I);
2979 OS << "Loop " << L->getHeader()->getName() << ": ";
2981 SmallVector<BasicBlock*, 8> ExitBlocks;
2982 L->getExitBlocks(ExitBlocks);
2983 if (ExitBlocks.size() != 1)
2984 OS << "<multiple exits> ";
2986 if (SE->hasLoopInvariantIterationCount(L)) {
2987 OS << *SE->getIterationCount(L) << " iterations! ";
2989 OS << "Unpredictable iteration count. ";
2995 void ScalarEvolution::print(std::ostream &OS, const Module* ) const {
2996 Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
2997 LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
2999 OS << "Classifying expressions for: " << F.getName() << "\n";
3000 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
3001 if (I->getType()->isInteger()) {
3004 SCEVHandle SV = getSCEV(&*I);
3008 if (const Loop *L = LI.getLoopFor((*I).getParent())) {
3010 SCEVHandle ExitValue = getSCEVAtScope(&*I, L->getParentLoop());
3011 if (isa<SCEVCouldNotCompute>(ExitValue)) {
3012 OS << "<<Unknown>>";
3022 OS << "Determining loop execution counts for: " << F.getName() << "\n";
3023 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
3024 PrintLoopInfo(OS, this, *I);