1 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
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 // Orthogonal to the analysis of code above, this file also implements the
37 // ScalarEvolutionRewriter class, which is used to emit code that represents the
38 // various recurrences present in a loop, in canonical forms.
40 // TODO: We should use these routines and value representations to implement
41 // dependence analysis!
43 //===----------------------------------------------------------------------===//
45 // There are several good references for the techniques used in this analysis.
47 // Chains of recurrences -- a method to expedite the evaluation
48 // of closed-form functions
49 // Olaf Bachmann, Paul S. Wang, Eugene V. Zima
51 // On computational properties of chains of recurrences
54 // Symbolic Evaluation of Chains of Recurrences for Loop Optimization
55 // Robert A. van Engelen
57 // Efficient Symbolic Analysis for Optimizing Compilers
58 // Robert A. van Engelen
60 // Using the chains of recurrences algebra for data dependence testing and
61 // induction variable substitution
62 // MS Thesis, Johnie Birch
64 //===----------------------------------------------------------------------===//
66 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
67 #include "llvm/Constants.h"
68 #include "llvm/DerivedTypes.h"
69 #include "llvm/Instructions.h"
70 #include "llvm/Type.h"
71 #include "llvm/Value.h"
72 #include "llvm/Analysis/LoopInfo.h"
73 #include "llvm/Assembly/Writer.h"
74 #include "llvm/Transforms/Scalar.h"
75 #include "llvm/Support/CFG.h"
76 #include "llvm/Support/ConstantRange.h"
77 #include "llvm/Support/InstIterator.h"
78 #include "Support/Statistic.h"
83 RegisterAnalysis<ScalarEvolution>
84 R("scalar-evolution", "Scalar Evolution Analysis Printer");
87 NumBruteForceEvaluations("scalar-evolution",
88 "Number of brute force evaluations needed to calculate high-order polynomial exit values");
90 NumTripCountsComputed("scalar-evolution",
91 "Number of loops with predictable loop counts");
93 NumTripCountsNotComputed("scalar-evolution",
94 "Number of loops without predictable loop counts");
97 //===----------------------------------------------------------------------===//
98 // SCEV class definitions
99 //===----------------------------------------------------------------------===//
101 //===----------------------------------------------------------------------===//
102 // Implementation of the SCEV class.
105 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less
106 /// than the complexity of the RHS. If the SCEVs have identical complexity,
107 /// order them by their addresses. This comparator is used to canonicalize
109 struct SCEVComplexityCompare {
110 bool operator()(SCEV *LHS, SCEV *RHS) {
111 if (LHS->getSCEVType() < RHS->getSCEVType())
113 if (LHS->getSCEVType() == RHS->getSCEVType())
121 void SCEV::dump() const {
125 /// getValueRange - Return the tightest constant bounds that this value is
126 /// known to have. This method is only valid on integer SCEV objects.
127 ConstantRange SCEV::getValueRange() const {
128 const Type *Ty = getType();
129 assert(Ty->isInteger() && "Can't get range for a non-integer SCEV!");
130 Ty = Ty->getUnsignedVersion();
131 // Default to a full range if no better information is available.
132 return ConstantRange(getType());
136 SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
138 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
139 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
143 const Type *SCEVCouldNotCompute::getType() const {
144 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
148 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const {
149 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
153 Value *SCEVCouldNotCompute::expandCodeFor(ScalarEvolutionRewriter &SER,
154 Instruction *InsertPt) {
155 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
160 void SCEVCouldNotCompute::print(std::ostream &OS) const {
161 OS << "***COULDNOTCOMPUTE***";
164 bool SCEVCouldNotCompute::classof(const SCEV *S) {
165 return S->getSCEVType() == scCouldNotCompute;
169 // SCEVConstants - Only allow the creation of one SCEVConstant for any
170 // particular value. Don't use a SCEVHandle here, or else the object will
172 static std::map<ConstantInt*, SCEVConstant*> SCEVConstants;
175 SCEVConstant::~SCEVConstant() {
176 SCEVConstants.erase(V);
179 SCEVHandle SCEVConstant::get(ConstantInt *V) {
180 // Make sure that SCEVConstant instances are all unsigned.
181 if (V->getType()->isSigned()) {
182 const Type *NewTy = V->getType()->getUnsignedVersion();
183 V = cast<ConstantUInt>(ConstantExpr::getCast(V, NewTy));
186 SCEVConstant *&R = SCEVConstants[V];
187 if (R == 0) R = new SCEVConstant(V);
191 ConstantRange SCEVConstant::getValueRange() const {
192 return ConstantRange(V);
195 const Type *SCEVConstant::getType() const { return V->getType(); }
197 void SCEVConstant::print(std::ostream &OS) const {
198 WriteAsOperand(OS, V, false);
201 // SCEVTruncates - Only allow the creation of one SCEVTruncateExpr for any
202 // particular input. Don't use a SCEVHandle here, or else the object will
204 static std::map<std::pair<SCEV*, const Type*>, SCEVTruncateExpr*> SCEVTruncates;
206 SCEVTruncateExpr::SCEVTruncateExpr(const SCEVHandle &op, const Type *ty)
207 : SCEV(scTruncate), Op(op), Ty(ty) {
208 assert(Op->getType()->isInteger() && Ty->isInteger() &&
210 "Cannot truncate non-integer value!");
211 assert(Op->getType()->getPrimitiveSize() > Ty->getPrimitiveSize() &&
212 "This is not a truncating conversion!");
215 SCEVTruncateExpr::~SCEVTruncateExpr() {
216 SCEVTruncates.erase(std::make_pair(Op, Ty));
219 ConstantRange SCEVTruncateExpr::getValueRange() const {
220 return getOperand()->getValueRange().truncate(getType());
223 void SCEVTruncateExpr::print(std::ostream &OS) const {
224 OS << "(truncate " << *Op << " to " << *Ty << ")";
227 // SCEVZeroExtends - Only allow the creation of one SCEVZeroExtendExpr for any
228 // particular input. Don't use a SCEVHandle here, or else the object will never
230 static std::map<std::pair<SCEV*, const Type*>,
231 SCEVZeroExtendExpr*> SCEVZeroExtends;
233 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty)
234 : SCEV(scTruncate), Op(Op), Ty(ty) {
235 assert(Op->getType()->isInteger() && Ty->isInteger() &&
237 "Cannot zero extend non-integer value!");
238 assert(Op->getType()->getPrimitiveSize() < Ty->getPrimitiveSize() &&
239 "This is not an extending conversion!");
242 SCEVZeroExtendExpr::~SCEVZeroExtendExpr() {
243 SCEVZeroExtends.erase(std::make_pair(Op, Ty));
246 ConstantRange SCEVZeroExtendExpr::getValueRange() const {
247 return getOperand()->getValueRange().zeroExtend(getType());
250 void SCEVZeroExtendExpr::print(std::ostream &OS) const {
251 OS << "(zeroextend " << *Op << " to " << *Ty << ")";
254 // SCEVCommExprs - Only allow the creation of one SCEVCommutativeExpr for any
255 // particular input. Don't use a SCEVHandle here, or else the object will never
257 static std::map<std::pair<unsigned, std::vector<SCEV*> >,
258 SCEVCommutativeExpr*> SCEVCommExprs;
260 SCEVCommutativeExpr::~SCEVCommutativeExpr() {
261 SCEVCommExprs.erase(std::make_pair(getSCEVType(),
262 std::vector<SCEV*>(Operands.begin(),
266 void SCEVCommutativeExpr::print(std::ostream &OS) const {
267 assert(Operands.size() > 1 && "This plus expr shouldn't exist!");
268 const char *OpStr = getOperationStr();
269 OS << "(" << *Operands[0];
270 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
271 OS << OpStr << *Operands[i];
275 // SCEVUDivs - Only allow the creation of one SCEVUDivExpr for any particular
276 // input. Don't use a SCEVHandle here, or else the object will never be
278 static std::map<std::pair<SCEV*, SCEV*>, SCEVUDivExpr*> SCEVUDivs;
280 SCEVUDivExpr::~SCEVUDivExpr() {
281 SCEVUDivs.erase(std::make_pair(LHS, RHS));
284 void SCEVUDivExpr::print(std::ostream &OS) const {
285 OS << "(" << *LHS << " /u " << *RHS << ")";
288 const Type *SCEVUDivExpr::getType() const {
289 const Type *Ty = LHS->getType();
290 if (Ty->isSigned()) Ty = Ty->getUnsignedVersion();
294 // SCEVAddRecExprs - Only allow the creation of one SCEVAddRecExpr for any
295 // particular input. Don't use a SCEVHandle here, or else the object will never
297 static std::map<std::pair<const Loop *, std::vector<SCEV*> >,
298 SCEVAddRecExpr*> SCEVAddRecExprs;
300 SCEVAddRecExpr::~SCEVAddRecExpr() {
301 SCEVAddRecExprs.erase(std::make_pair(L,
302 std::vector<SCEV*>(Operands.begin(),
306 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const {
307 // This recurrence is invariant w.r.t to QueryLoop iff QueryLoop doesn't
309 return !QueryLoop->contains(L->getHeader());
313 void SCEVAddRecExpr::print(std::ostream &OS) const {
314 OS << "{" << *Operands[0];
315 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
316 OS << ",+," << *Operands[i];
317 OS << "}<" << L->getHeader()->getName() + ">";
320 // SCEVUnknowns - Only allow the creation of one SCEVUnknown for any particular
321 // value. Don't use a SCEVHandle here, or else the object will never be
323 static std::map<Value*, SCEVUnknown*> SCEVUnknowns;
325 SCEVUnknown::~SCEVUnknown() { SCEVUnknowns.erase(V); }
327 bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
328 // All non-instruction values are loop invariant. All instructions are loop
329 // invariant if they are not contained in the specified loop.
330 if (Instruction *I = dyn_cast<Instruction>(V))
331 return !L->contains(I->getParent());
335 const Type *SCEVUnknown::getType() const {
339 void SCEVUnknown::print(std::ostream &OS) const {
340 WriteAsOperand(OS, V, false);
345 //===----------------------------------------------------------------------===//
346 // Simple SCEV method implementations
347 //===----------------------------------------------------------------------===//
349 /// getIntegerSCEV - Given an integer or FP type, create a constant for the
350 /// specified signed integer value and return a SCEV for the constant.
351 static SCEVHandle getIntegerSCEV(int Val, const Type *Ty) {
354 C = Constant::getNullValue(Ty);
355 else if (Ty->isFloatingPoint())
356 C = ConstantFP::get(Ty, Val);
357 else if (Ty->isSigned())
358 C = ConstantSInt::get(Ty, Val);
360 C = ConstantSInt::get(Ty->getSignedVersion(), Val);
361 C = ConstantExpr::getCast(C, Ty);
363 return SCEVUnknown::get(C);
366 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
367 /// input value to the specified type. If the type must be extended, it is zero
369 static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty) {
370 const Type *SrcTy = V->getType();
371 assert(SrcTy->isInteger() && Ty->isInteger() &&
372 "Cannot truncate or zero extend with non-integer arguments!");
373 if (SrcTy->getPrimitiveSize() == Ty->getPrimitiveSize())
374 return V; // No conversion
375 if (SrcTy->getPrimitiveSize() > Ty->getPrimitiveSize())
376 return SCEVTruncateExpr::get(V, Ty);
377 return SCEVZeroExtendExpr::get(V, Ty);
380 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
382 static SCEVHandle getNegativeSCEV(const SCEVHandle &V) {
383 if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
384 return SCEVUnknown::get(ConstantExpr::getNeg(VC->getValue()));
386 return SCEVMulExpr::get(V, getIntegerSCEV(-1, V->getType()));
389 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
391 static SCEVHandle getMinusSCEV(const SCEVHandle &LHS, const SCEVHandle &RHS) {
393 return SCEVAddExpr::get(LHS, getNegativeSCEV(RHS));
397 /// Binomial - Evaluate N!/((N-M)!*M!) . Note that N is often large and M is
398 /// often very small, so we try to reduce the number of N! terms we need to
399 /// evaluate by evaluating this as (N!/(N-M)!)/M!
400 static ConstantInt *Binomial(ConstantInt *N, unsigned M) {
401 uint64_t NVal = N->getRawValue();
402 uint64_t FirstTerm = 1;
403 for (unsigned i = 0; i != M; ++i)
406 unsigned MFactorial = 1;
410 Constant *Result = ConstantUInt::get(Type::ULongTy, FirstTerm/MFactorial);
411 Result = ConstantExpr::getCast(Result, N->getType());
412 assert(isa<ConstantInt>(Result) && "Cast of integer not folded??");
413 return cast<ConstantInt>(Result);
416 /// PartialFact - Compute V!/(V-NumSteps)!
417 static SCEVHandle PartialFact(SCEVHandle V, unsigned NumSteps) {
418 // Handle this case efficiently, it is common to have constant iteration
419 // counts while computing loop exit values.
420 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
421 uint64_t Val = SC->getValue()->getRawValue();
423 for (; NumSteps; --NumSteps)
424 Result *= Val-(NumSteps-1);
425 Constant *Res = ConstantUInt::get(Type::ULongTy, Result);
426 return SCEVUnknown::get(ConstantExpr::getCast(Res, V->getType()));
429 const Type *Ty = V->getType();
431 return getIntegerSCEV(1, Ty);
433 SCEVHandle Result = V;
434 for (unsigned i = 1; i != NumSteps; ++i)
435 Result = SCEVMulExpr::get(Result, getMinusSCEV(V, getIntegerSCEV(i, Ty)));
440 /// evaluateAtIteration - Return the value of this chain of recurrences at
441 /// the specified iteration number. We can evaluate this recurrence by
442 /// multiplying each element in the chain by the binomial coefficient
443 /// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as:
445 /// A*choose(It, 0) + B*choose(It, 1) + C*choose(It, 2) + D*choose(It, 3)
447 /// FIXME/VERIFY: I don't trust that this is correct in the face of overflow.
448 /// Is the binomial equation safe using modular arithmetic??
450 SCEVHandle SCEVAddRecExpr::evaluateAtIteration(SCEVHandle It) const {
451 SCEVHandle Result = getStart();
453 const Type *Ty = It->getType();
454 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
455 SCEVHandle BC = PartialFact(It, i);
457 SCEVHandle Val = SCEVUDivExpr::get(SCEVMulExpr::get(BC, getOperand(i)),
458 getIntegerSCEV(Divisor, Ty));
459 Result = SCEVAddExpr::get(Result, Val);
465 //===----------------------------------------------------------------------===//
466 // SCEV Expression folder implementations
467 //===----------------------------------------------------------------------===//
469 SCEVHandle SCEVTruncateExpr::get(const SCEVHandle &Op, const Type *Ty) {
470 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
471 return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
473 // If the input value is a chrec scev made out of constants, truncate
474 // all of the constants.
475 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
476 std::vector<SCEVHandle> Operands;
477 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
478 // FIXME: This should allow truncation of other expression types!
479 if (isa<SCEVConstant>(AddRec->getOperand(i)))
480 Operands.push_back(get(AddRec->getOperand(i), Ty));
483 if (Operands.size() == AddRec->getNumOperands())
484 return SCEVAddRecExpr::get(Operands, AddRec->getLoop());
487 SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
488 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
492 SCEVHandle SCEVZeroExtendExpr::get(const SCEVHandle &Op, const Type *Ty) {
493 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
494 return SCEVUnknown::get(ConstantExpr::getCast(SC->getValue(), Ty));
496 // FIXME: If the input value is a chrec scev, and we can prove that the value
497 // did not overflow the old, smaller, value, we can zero extend all of the
498 // operands (often constants). This would allow analysis of something like
499 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; }
501 SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
502 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
506 // get - Get a canonical add expression, or something simpler if possible.
507 SCEVHandle SCEVAddExpr::get(std::vector<SCEVHandle> &Ops) {
508 assert(!Ops.empty() && "Cannot get empty add!");
509 if (Ops.size() == 1) return Ops[0];
511 // Sort by complexity, this groups all similar expression types together.
512 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
514 // If there are any constants, fold them together.
516 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
518 assert(Idx < Ops.size());
519 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
520 // We found two constants, fold them together!
521 Constant *Fold = ConstantExpr::getAdd(LHSC->getValue(), RHSC->getValue());
522 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
523 Ops[0] = SCEVConstant::get(CI);
524 Ops.erase(Ops.begin()+1); // Erase the folded element
525 if (Ops.size() == 1) return Ops[0];
527 // If we couldn't fold the expression, move to the next constant. Note
528 // that this is impossible to happen in practice because we always
529 // constant fold constant ints to constant ints.
534 // If we are left with a constant zero being added, strip it off.
535 if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) {
536 Ops.erase(Ops.begin());
541 if (Ops.size() == 1) return Ops[0];
543 // Okay, check to see if the same value occurs in the operand list twice. If
544 // so, merge them together into an multiply expression. Since we sorted the
545 // list, these values are required to be adjacent.
546 const Type *Ty = Ops[0]->getType();
547 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
548 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2
549 // Found a match, merge the two values into a multiply, and add any
550 // remaining values to the result.
551 SCEVHandle Two = getIntegerSCEV(2, Ty);
552 SCEVHandle Mul = SCEVMulExpr::get(Ops[i], Two);
555 Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
557 return SCEVAddExpr::get(Ops);
560 // Okay, now we know the first non-constant operand. If there are add
561 // operands they would be next.
562 if (Idx < Ops.size()) {
563 bool DeletedAdd = false;
564 while (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
565 // If we have an add, expand the add operands onto the end of the operands
567 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end());
568 Ops.erase(Ops.begin()+Idx);
572 // If we deleted at least one add, we added operands to the end of the list,
573 // and they are not necessarily sorted. Recurse to resort and resimplify
574 // any operands we just aquired.
579 // Skip over the add expression until we get to a multiply.
580 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
583 // If we are adding something to a multiply expression, make sure the
584 // something is not already an operand of the multiply. If so, merge it into
586 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
587 SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
588 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
589 SCEV *MulOpSCEV = Mul->getOperand(MulOp);
590 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp)
591 if (MulOpSCEV == Ops[AddOp] &&
592 (Mul->getNumOperands() != 2 || !isa<SCEVConstant>(MulOpSCEV))) {
593 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1))
594 SCEVHandle InnerMul = Mul->getOperand(MulOp == 0);
595 if (Mul->getNumOperands() != 2) {
596 // If the multiply has more than two operands, we must get the
598 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
599 MulOps.erase(MulOps.begin()+MulOp);
600 InnerMul = SCEVMulExpr::get(MulOps);
602 SCEVHandle One = getIntegerSCEV(1, Ty);
603 SCEVHandle AddOne = SCEVAddExpr::get(InnerMul, One);
604 SCEVHandle OuterMul = SCEVMulExpr::get(AddOne, Ops[AddOp]);
605 if (Ops.size() == 2) return OuterMul;
607 Ops.erase(Ops.begin()+AddOp);
608 Ops.erase(Ops.begin()+Idx-1);
610 Ops.erase(Ops.begin()+Idx);
611 Ops.erase(Ops.begin()+AddOp-1);
613 Ops.push_back(OuterMul);
614 return SCEVAddExpr::get(Ops);
617 // Check this multiply against other multiplies being added together.
618 for (unsigned OtherMulIdx = Idx+1;
619 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
621 SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
622 // If MulOp occurs in OtherMul, we can fold the two multiplies
624 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands();
625 OMulOp != e; ++OMulOp)
626 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
627 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
628 SCEVHandle InnerMul1 = Mul->getOperand(MulOp == 0);
629 if (Mul->getNumOperands() != 2) {
630 std::vector<SCEVHandle> MulOps(Mul->op_begin(), Mul->op_end());
631 MulOps.erase(MulOps.begin()+MulOp);
632 InnerMul1 = SCEVMulExpr::get(MulOps);
634 SCEVHandle InnerMul2 = OtherMul->getOperand(OMulOp == 0);
635 if (OtherMul->getNumOperands() != 2) {
636 std::vector<SCEVHandle> MulOps(OtherMul->op_begin(),
638 MulOps.erase(MulOps.begin()+OMulOp);
639 InnerMul2 = SCEVMulExpr::get(MulOps);
641 SCEVHandle InnerMulSum = SCEVAddExpr::get(InnerMul1,InnerMul2);
642 SCEVHandle OuterMul = SCEVMulExpr::get(MulOpSCEV, InnerMulSum);
643 if (Ops.size() == 2) return OuterMul;
644 Ops.erase(Ops.begin()+Idx);
645 Ops.erase(Ops.begin()+OtherMulIdx-1);
646 Ops.push_back(OuterMul);
647 return SCEVAddExpr::get(Ops);
653 // If there are any add recurrences in the operands list, see if any other
654 // added values are loop invariant. If so, we can fold them into the
656 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
659 // Scan over all recurrences, trying to fold loop invariants into them.
660 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
661 // Scan all of the other operands to this add and add them to the vector if
662 // they are loop invariant w.r.t. the recurrence.
663 std::vector<SCEVHandle> LIOps;
664 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
665 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
666 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
667 LIOps.push_back(Ops[i]);
668 Ops.erase(Ops.begin()+i);
672 // If we found some loop invariants, fold them into the recurrence.
673 if (!LIOps.empty()) {
674 // NLI + LI + { Start,+,Step} --> NLI + { LI+Start,+,Step }
675 LIOps.push_back(AddRec->getStart());
677 std::vector<SCEVHandle> AddRecOps(AddRec->op_begin(), AddRec->op_end());
678 AddRecOps[0] = SCEVAddExpr::get(LIOps);
680 SCEVHandle NewRec = SCEVAddRecExpr::get(AddRecOps, AddRec->getLoop());
681 // If all of the other operands were loop invariant, we are done.
682 if (Ops.size() == 1) return NewRec;
684 // Otherwise, add the folded AddRec by the non-liv parts.
685 for (unsigned i = 0;; ++i)
686 if (Ops[i] == AddRec) {
690 return SCEVAddExpr::get(Ops);
693 // Okay, if there weren't any loop invariants to be folded, check to see if
694 // there are multiple AddRec's with the same loop induction variable being
695 // added together. If so, we can fold them.
696 for (unsigned OtherIdx = Idx+1;
697 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
698 if (OtherIdx != Idx) {
699 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
700 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
701 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D}
702 std::vector<SCEVHandle> NewOps(AddRec->op_begin(), AddRec->op_end());
703 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) {
704 if (i >= NewOps.size()) {
705 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i,
706 OtherAddRec->op_end());
709 NewOps[i] = SCEVAddExpr::get(NewOps[i], OtherAddRec->getOperand(i));
711 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop());
713 if (Ops.size() == 2) return NewAddRec;
715 Ops.erase(Ops.begin()+Idx);
716 Ops.erase(Ops.begin()+OtherIdx-1);
717 Ops.push_back(NewAddRec);
718 return SCEVAddExpr::get(Ops);
722 // Otherwise couldn't fold anything into this recurrence. Move onto the
726 // Okay, it looks like we really DO need an add expr. Check to see if we
727 // already have one, otherwise create a new one.
728 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
729 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
731 if (Result == 0) Result = new SCEVAddExpr(Ops);
736 SCEVHandle SCEVMulExpr::get(std::vector<SCEVHandle> &Ops) {
737 assert(!Ops.empty() && "Cannot get empty mul!");
739 // Sort by complexity, this groups all similar expression types together.
740 std::sort(Ops.begin(), Ops.end(), SCEVComplexityCompare());
742 // If there are any constants, fold them together.
744 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
746 // C1*(C2+V) -> C1*C2 + C1*V
748 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
749 if (Add->getNumOperands() == 2 &&
750 isa<SCEVConstant>(Add->getOperand(0)))
751 return SCEVAddExpr::get(SCEVMulExpr::get(LHSC, Add->getOperand(0)),
752 SCEVMulExpr::get(LHSC, Add->getOperand(1)));
756 while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
757 // We found two constants, fold them together!
758 Constant *Fold = ConstantExpr::getMul(LHSC->getValue(), RHSC->getValue());
759 if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
760 Ops[0] = SCEVConstant::get(CI);
761 Ops.erase(Ops.begin()+1); // Erase the folded element
762 if (Ops.size() == 1) return Ops[0];
764 // If we couldn't fold the expression, move to the next constant. Note
765 // that this is impossible to happen in practice because we always
766 // constant fold constant ints to constant ints.
771 // If we are left with a constant one being multiplied, strip it off.
772 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
773 Ops.erase(Ops.begin());
775 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isNullValue()) {
776 // If we have a multiply of zero, it will always be zero.
781 // Skip over the add expression until we get to a multiply.
782 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
788 // If there are mul operands inline them all into this expression.
789 if (Idx < Ops.size()) {
790 bool DeletedMul = false;
791 while (SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
792 // If we have an mul, expand the mul operands onto the end of the operands
794 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end());
795 Ops.erase(Ops.begin()+Idx);
799 // If we deleted at least one mul, we added operands to the end of the list,
800 // and they are not necessarily sorted. Recurse to resort and resimplify
801 // any operands we just aquired.
806 // If there are any add recurrences in the operands list, see if any other
807 // added values are loop invariant. If so, we can fold them into the
809 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
812 // Scan over all recurrences, trying to fold loop invariants into them.
813 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
814 // Scan all of the other operands to this mul and add them to the vector if
815 // they are loop invariant w.r.t. the recurrence.
816 std::vector<SCEVHandle> LIOps;
817 SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
818 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
819 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) {
820 LIOps.push_back(Ops[i]);
821 Ops.erase(Ops.begin()+i);
825 // If we found some loop invariants, fold them into the recurrence.
826 if (!LIOps.empty()) {
827 // NLI * LI * { Start,+,Step} --> NLI * { LI*Start,+,LI*Step }
828 std::vector<SCEVHandle> NewOps;
829 NewOps.reserve(AddRec->getNumOperands());
830 if (LIOps.size() == 1) {
831 SCEV *Scale = LIOps[0];
832 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
833 NewOps.push_back(SCEVMulExpr::get(Scale, AddRec->getOperand(i)));
835 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
836 std::vector<SCEVHandle> MulOps(LIOps);
837 MulOps.push_back(AddRec->getOperand(i));
838 NewOps.push_back(SCEVMulExpr::get(MulOps));
842 SCEVHandle NewRec = SCEVAddRecExpr::get(NewOps, AddRec->getLoop());
844 // If all of the other operands were loop invariant, we are done.
845 if (Ops.size() == 1) return NewRec;
847 // Otherwise, multiply the folded AddRec by the non-liv parts.
848 for (unsigned i = 0;; ++i)
849 if (Ops[i] == AddRec) {
853 return SCEVMulExpr::get(Ops);
856 // Okay, if there weren't any loop invariants to be folded, check to see if
857 // there are multiple AddRec's with the same loop induction variable being
858 // multiplied together. If so, we can fold them.
859 for (unsigned OtherIdx = Idx+1;
860 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx)
861 if (OtherIdx != Idx) {
862 SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
863 if (AddRec->getLoop() == OtherAddRec->getLoop()) {
864 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D}
865 SCEVAddRecExpr *F = AddRec, *G = OtherAddRec;
866 SCEVHandle NewStart = SCEVMulExpr::get(F->getStart(),
868 SCEVHandle B = F->getStepRecurrence();
869 SCEVHandle D = G->getStepRecurrence();
870 SCEVHandle NewStep = SCEVAddExpr::get(SCEVMulExpr::get(F, D),
871 SCEVMulExpr::get(G, B),
872 SCEVMulExpr::get(B, D));
873 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewStart, NewStep,
875 if (Ops.size() == 2) return NewAddRec;
877 Ops.erase(Ops.begin()+Idx);
878 Ops.erase(Ops.begin()+OtherIdx-1);
879 Ops.push_back(NewAddRec);
880 return SCEVMulExpr::get(Ops);
884 // Otherwise couldn't fold anything into this recurrence. Move onto the
888 // Okay, it looks like we really DO need an mul expr. Check to see if we
889 // already have one, otherwise create a new one.
890 std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
891 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
893 if (Result == 0) Result = new SCEVMulExpr(Ops);
897 SCEVHandle SCEVUDivExpr::get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
898 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
899 if (RHSC->getValue()->equalsInt(1))
900 return LHS; // X /u 1 --> x
901 if (RHSC->getValue()->isAllOnesValue())
902 return getNegativeSCEV(LHS); // X /u -1 --> -x
904 if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
905 Constant *LHSCV = LHSC->getValue();
906 Constant *RHSCV = RHSC->getValue();
907 if (LHSCV->getType()->isSigned())
908 LHSCV = ConstantExpr::getCast(LHSCV,
909 LHSCV->getType()->getUnsignedVersion());
910 if (RHSCV->getType()->isSigned())
911 RHSCV = ConstantExpr::getCast(RHSCV, LHSCV->getType());
912 return SCEVUnknown::get(ConstantExpr::getDiv(LHSCV, RHSCV));
916 // FIXME: implement folding of (X*4)/4 when we know X*4 doesn't overflow.
918 SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
919 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
924 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
925 /// specified loop. Simplify the expression as much as possible.
926 SCEVHandle SCEVAddRecExpr::get(const SCEVHandle &Start,
927 const SCEVHandle &Step, const Loop *L) {
928 std::vector<SCEVHandle> Operands;
929 Operands.push_back(Start);
930 if (SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
931 if (StepChrec->getLoop() == L) {
932 Operands.insert(Operands.end(), StepChrec->op_begin(),
933 StepChrec->op_end());
934 return get(Operands, L);
937 Operands.push_back(Step);
938 return get(Operands, L);
941 /// SCEVAddRecExpr::get - Get a add recurrence expression for the
942 /// specified loop. Simplify the expression as much as possible.
943 SCEVHandle SCEVAddRecExpr::get(std::vector<SCEVHandle> &Operands,
945 if (Operands.size() == 1) return Operands[0];
947 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back()))
948 if (StepC->getValue()->isNullValue()) {
950 return get(Operands, L); // { X,+,0 } --> X
953 SCEVAddRecExpr *&Result =
954 SCEVAddRecExprs[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
956 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
960 SCEVHandle SCEVUnknown::get(Value *V) {
961 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
962 return SCEVConstant::get(CI);
963 SCEVUnknown *&Result = SCEVUnknowns[V];
964 if (Result == 0) Result = new SCEVUnknown(V);
969 //===----------------------------------------------------------------------===//
970 // Non-trivial closed-form SCEV Expanders
971 //===----------------------------------------------------------------------===//
973 Value *SCEVTruncateExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
974 Instruction *InsertPt) {
975 Value *V = SER.ExpandCodeFor(getOperand(), InsertPt);
976 return new CastInst(V, getType(), "tmp.", InsertPt);
979 Value *SCEVZeroExtendExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
980 Instruction *InsertPt) {
981 Value *V = SER.ExpandCodeFor(getOperand(), InsertPt,
982 getOperand()->getType()->getUnsignedVersion());
983 return new CastInst(V, getType(), "tmp.", InsertPt);
986 Value *SCEVAddExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
987 Instruction *InsertPt) {
988 const Type *Ty = getType();
989 Value *V = SER.ExpandCodeFor(getOperand(getNumOperands()-1), InsertPt, Ty);
991 // Emit a bunch of add instructions
992 for (int i = getNumOperands()-2; i >= 0; --i)
993 V = BinaryOperator::create(Instruction::Add, V,
994 SER.ExpandCodeFor(getOperand(i), InsertPt, Ty),
999 Value *SCEVMulExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1000 Instruction *InsertPt) {
1001 const Type *Ty = getType();
1002 int FirstOp = 0; // Set if we should emit a subtract.
1003 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getOperand(0)))
1004 if (SC->getValue()->isAllOnesValue())
1007 int i = getNumOperands()-2;
1008 Value *V = SER.ExpandCodeFor(getOperand(i+1), InsertPt, Ty);
1010 // Emit a bunch of multiply instructions
1011 for (; i >= FirstOp; --i)
1012 V = BinaryOperator::create(Instruction::Mul, V,
1013 SER.ExpandCodeFor(getOperand(i), InsertPt, Ty),
1015 // -1 * ... ---> 0 - ...
1017 V = BinaryOperator::create(Instruction::Sub, Constant::getNullValue(Ty), V,
1022 Value *SCEVUDivExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1023 Instruction *InsertPt) {
1024 const Type *Ty = getType();
1025 Value *LHS = SER.ExpandCodeFor(getLHS(), InsertPt, Ty);
1026 Value *RHS = SER.ExpandCodeFor(getRHS(), InsertPt, Ty);
1027 return BinaryOperator::create(Instruction::Div, LHS, RHS, "tmp.", InsertPt);
1030 Value *SCEVAddRecExpr::expandCodeFor(ScalarEvolutionRewriter &SER,
1031 Instruction *InsertPt) {
1032 const Type *Ty = getType();
1033 // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F}
1034 assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!");
1036 // {X,+,F} --> X + {0,+,F}
1037 if (!isa<SCEVConstant>(getStart()) ||
1038 !cast<SCEVConstant>(getStart())->getValue()->isNullValue()) {
1039 Value *Start = SER.ExpandCodeFor(getStart(), InsertPt, Ty);
1040 std::vector<SCEVHandle> NewOps(op_begin(), op_end());
1041 NewOps[0] = getIntegerSCEV(0, getType());
1042 Value *Rest = SER.ExpandCodeFor(SCEVAddRecExpr::get(NewOps, getLoop()),
1043 InsertPt, getType());
1045 // FIXME: look for an existing add to use.
1046 return BinaryOperator::create(Instruction::Add, Rest, Start, "tmp.",
1050 // {0,+,1} --> Insert a canonical induction variable into the loop!
1051 if (getNumOperands() == 2 && getOperand(1) == getIntegerSCEV(1, getType())) {
1052 // Create and insert the PHI node for the induction variable in the
1054 BasicBlock *Header = getLoop()->getHeader();
1055 PHINode *PN = new PHINode(Ty, "indvar", Header->begin());
1056 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader());
1058 pred_iterator HPI = pred_begin(Header);
1059 assert(HPI != pred_end(Header) && "Loop with zero preds???");
1060 if (!getLoop()->contains(*HPI)) ++HPI;
1061 assert(HPI != pred_end(Header) && getLoop()->contains(*HPI) &&
1062 "No backedge in loop?");
1064 // Insert a unit add instruction right before the terminator corresponding
1065 // to the back-edge.
1066 Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0)
1067 : (Constant*)ConstantInt::get(Ty, 1);
1068 Instruction *Add = BinaryOperator::create(Instruction::Add, PN, One,
1070 (*HPI)->getTerminator());
1072 pred_iterator PI = pred_begin(Header);
1073 if (*PI == L->getLoopPreheader())
1075 PN->addIncoming(Add, *PI);
1079 // Get the canonical induction variable I for this loop.
1080 Value *I = SER.GetOrInsertCanonicalInductionVariable(getLoop(), Ty);
1082 if (getNumOperands() == 2) { // {0,+,F} --> i*F
1083 Value *F = SER.ExpandCodeFor(getOperand(1), InsertPt, Ty);
1084 return BinaryOperator::create(Instruction::Mul, I, F, "tmp.", InsertPt);
1087 // If this is a chain of recurrences, turn it into a closed form, using the
1088 // folders, then expandCodeFor the closed form. This allows the folders to
1089 // simplify the expression without having to build a bunch of special code
1090 // into this folder.
1091 SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV.
1093 SCEVHandle V = evaluateAtIteration(IH);
1094 //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n";
1096 return SER.ExpandCodeFor(V, InsertPt, Ty);
1100 //===----------------------------------------------------------------------===//
1101 // ScalarEvolutionsImpl Definition and Implementation
1102 //===----------------------------------------------------------------------===//
1104 /// ScalarEvolutionsImpl - This class implements the main driver for the scalar
1108 struct ScalarEvolutionsImpl {
1109 /// F - The function we are analyzing.
1113 /// LI - The loop information for the function we are currently analyzing.
1117 /// UnknownValue - This SCEV is used to represent unknown trip counts and
1119 SCEVHandle UnknownValue;
1121 /// Scalars - This is a cache of the scalars we have analyzed so far.
1123 std::map<Value*, SCEVHandle> Scalars;
1125 /// IterationCounts - Cache the iteration count of the loops for this
1126 /// function as they are computed.
1127 std::map<const Loop*, SCEVHandle> IterationCounts;
1130 ScalarEvolutionsImpl(Function &f, LoopInfo &li)
1131 : F(f), LI(li), UnknownValue(new SCEVCouldNotCompute()) {}
1133 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1134 /// expression and create a new one.
1135 SCEVHandle getSCEV(Value *V);
1137 /// getSCEVAtScope - Compute the value of the specified expression within
1138 /// the indicated loop (which may be null to indicate in no loop). If the
1139 /// expression cannot be evaluated, return UnknownValue itself.
1140 SCEVHandle getSCEVAtScope(SCEV *V, const Loop *L);
1143 /// hasLoopInvariantIterationCount - Return true if the specified loop has
1144 /// an analyzable loop-invariant iteration count.
1145 bool hasLoopInvariantIterationCount(const Loop *L);
1147 /// getIterationCount - If the specified loop has a predictable iteration
1148 /// count, return it. Note that it is not valid to call this method on a
1149 /// loop without a loop-invariant iteration count.
1150 SCEVHandle getIterationCount(const Loop *L);
1152 /// deleteInstructionFromRecords - This method should be called by the
1153 /// client before it removes an instruction from the program, to make sure
1154 /// that no dangling references are left around.
1155 void deleteInstructionFromRecords(Instruction *I);
1158 /// createSCEV - We know that there is no SCEV for the specified value.
1159 /// Analyze the expression.
1160 SCEVHandle createSCEV(Value *V);
1161 SCEVHandle createNodeForCast(CastInst *CI);
1163 /// createNodeForPHI - Provide the special handling we need to analyze PHI
1165 SCEVHandle createNodeForPHI(PHINode *PN);
1166 void UpdatePHIUserScalarEntries(Instruction *I, PHINode *PN,
1167 std::set<Instruction*> &UpdatedInsts);
1169 /// ComputeIterationCount - Compute the number of times the specified loop
1171 SCEVHandle ComputeIterationCount(const Loop *L);
1173 /// HowFarToZero - Return the number of times a backedge comparing the
1174 /// specified value to zero will execute. If not computable, return
1176 SCEVHandle HowFarToZero(SCEV *V, const Loop *L);
1178 /// HowFarToNonZero - Return the number of times a backedge checking the
1179 /// specified value for nonzero will execute. If not computable, return
1181 SCEVHandle HowFarToNonZero(SCEV *V, const Loop *L);
1185 //===----------------------------------------------------------------------===//
1186 // Basic SCEV Analysis and PHI Idiom Recognition Code
1189 /// deleteInstructionFromRecords - This method should be called by the
1190 /// client before it removes an instruction from the program, to make sure
1191 /// that no dangling references are left around.
1192 void ScalarEvolutionsImpl::deleteInstructionFromRecords(Instruction *I) {
1197 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the
1198 /// expression and create a new one.
1199 SCEVHandle ScalarEvolutionsImpl::getSCEV(Value *V) {
1200 assert(V->getType() != Type::VoidTy && "Can't analyze void expressions!");
1202 std::map<Value*, SCEVHandle>::iterator I = Scalars.find(V);
1203 if (I != Scalars.end()) return I->second;
1204 SCEVHandle S = createSCEV(V);
1205 Scalars.insert(std::make_pair(V, S));
1210 /// UpdatePHIUserScalarEntries - After PHI node analysis, we have a bunch of
1211 /// entries in the scalar map that refer to the "symbolic" PHI value instead of
1212 /// the recurrence value. After we resolve the PHI we must loop over all of the
1213 /// using instructions that have scalar map entries and update them.
1214 void ScalarEvolutionsImpl::UpdatePHIUserScalarEntries(Instruction *I,
1216 std::set<Instruction*> &UpdatedInsts) {
1217 std::map<Value*, SCEVHandle>::iterator SI = Scalars.find(I);
1218 if (SI == Scalars.end()) return; // This scalar wasn't previous processed.
1219 if (UpdatedInsts.insert(I).second) {
1220 Scalars.erase(SI); // Remove the old entry
1221 getSCEV(I); // Calculate the new entry
1223 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
1225 UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN, UpdatedInsts);
1230 /// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in
1231 /// a loop header, making it a potential recurrence, or it doesn't.
1233 SCEVHandle ScalarEvolutionsImpl::createNodeForPHI(PHINode *PN) {
1234 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized.
1235 if (const Loop *L = LI.getLoopFor(PN->getParent()))
1236 if (L->getHeader() == PN->getParent()) {
1237 // If it lives in the loop header, it has two incoming values, one
1238 // from outside the loop, and one from inside.
1239 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
1240 unsigned BackEdge = IncomingEdge^1;
1242 // While we are analyzing this PHI node, handle its value symbolically.
1243 SCEVHandle SymbolicName = SCEVUnknown::get(PN);
1244 assert(Scalars.find(PN) == Scalars.end() &&
1245 "PHI node already processed?");
1246 Scalars.insert(std::make_pair(PN, SymbolicName));
1248 // Using this symbolic name for the PHI, analyze the value coming around
1250 SCEVHandle BEValue = getSCEV(PN->getIncomingValue(BackEdge));
1252 // NOTE: If BEValue is loop invariant, we know that the PHI node just
1253 // has a special value for the first iteration of the loop.
1255 // If the value coming around the backedge is an add with the symbolic
1256 // value we just inserted, then we found a simple induction variable!
1257 if (SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
1258 // If there is a single occurrence of the symbolic value, replace it
1259 // with a recurrence.
1260 unsigned FoundIndex = Add->getNumOperands();
1261 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1262 if (Add->getOperand(i) == SymbolicName)
1263 if (FoundIndex == e) {
1268 if (FoundIndex != Add->getNumOperands()) {
1269 // Create an add with everything but the specified operand.
1270 std::vector<SCEVHandle> Ops;
1271 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
1272 if (i != FoundIndex)
1273 Ops.push_back(Add->getOperand(i));
1274 SCEVHandle Accum = SCEVAddExpr::get(Ops);
1276 // This is not a valid addrec if the step amount is varying each
1277 // loop iteration, but is not itself an addrec in this loop.
1278 if (Accum->isLoopInvariant(L) ||
1279 (isa<SCEVAddRecExpr>(Accum) &&
1280 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
1281 SCEVHandle StartVal = getSCEV(PN->getIncomingValue(IncomingEdge));
1282 SCEVHandle PHISCEV = SCEVAddRecExpr::get(StartVal, Accum, L);
1284 // Okay, for the entire analysis of this edge we assumed the PHI
1285 // to be symbolic. We now need to go back and update all of the
1286 // entries for the scalars that use the PHI (except for the PHI
1287 // itself) to use the new analyzed value instead of the "symbolic"
1289 Scalars.find(PN)->second = PHISCEV; // Update the PHI value
1290 std::set<Instruction*> UpdatedInsts;
1291 UpdatedInsts.insert(PN);
1292 for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end();
1294 UpdatePHIUserScalarEntries(cast<Instruction>(*UI), PN,
1301 return SymbolicName;
1304 // If it's not a loop phi, we can't handle it yet.
1305 return SCEVUnknown::get(PN);
1308 /// createNodeForCast - Handle the various forms of casts that we support.
1310 SCEVHandle ScalarEvolutionsImpl::createNodeForCast(CastInst *CI) {
1311 const Type *SrcTy = CI->getOperand(0)->getType();
1312 const Type *DestTy = CI->getType();
1314 // If this is a noop cast (ie, conversion from int to uint), ignore it.
1315 if (SrcTy->isLosslesslyConvertibleTo(DestTy))
1316 return getSCEV(CI->getOperand(0));
1318 if (SrcTy->isInteger() && DestTy->isInteger()) {
1319 // Otherwise, if this is a truncating integer cast, we can represent this
1321 if (SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize())
1322 return SCEVTruncateExpr::get(getSCEV(CI->getOperand(0)),
1323 CI->getType()->getUnsignedVersion());
1324 if (SrcTy->isUnsigned() &&
1325 SrcTy->getPrimitiveSize() > DestTy->getPrimitiveSize())
1326 return SCEVZeroExtendExpr::get(getSCEV(CI->getOperand(0)),
1327 CI->getType()->getUnsignedVersion());
1330 // If this is an sign or zero extending cast and we can prove that the value
1331 // will never overflow, we could do similar transformations.
1333 // Otherwise, we can't handle this cast!
1334 return SCEVUnknown::get(CI);
1338 /// createSCEV - We know that there is no SCEV for the specified value.
1339 /// Analyze the expression.
1341 SCEVHandle ScalarEvolutionsImpl::createSCEV(Value *V) {
1342 if (Instruction *I = dyn_cast<Instruction>(V)) {
1343 switch (I->getOpcode()) {
1344 case Instruction::Add:
1345 return SCEVAddExpr::get(getSCEV(I->getOperand(0)),
1346 getSCEV(I->getOperand(1)));
1347 case Instruction::Mul:
1348 return SCEVMulExpr::get(getSCEV(I->getOperand(0)),
1349 getSCEV(I->getOperand(1)));
1350 case Instruction::Div:
1351 if (V->getType()->isInteger() && V->getType()->isUnsigned())
1352 return SCEVUDivExpr::get(getSCEV(I->getOperand(0)),
1353 getSCEV(I->getOperand(1)));
1356 case Instruction::Sub:
1357 return getMinusSCEV(getSCEV(I->getOperand(0)), getSCEV(I->getOperand(1)));
1359 case Instruction::Shl:
1360 // Turn shift left of a constant amount into a multiply.
1361 if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
1362 Constant *X = ConstantInt::get(V->getType(), 1);
1363 X = ConstantExpr::getShl(X, SA);
1364 return SCEVMulExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
1368 case Instruction::Shr:
1369 if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
1370 if (V->getType()->isUnsigned()) {
1371 Constant *X = ConstantInt::get(V->getType(), 1);
1372 X = ConstantExpr::getShl(X, SA);
1373 return SCEVUDivExpr::get(getSCEV(I->getOperand(0)), getSCEV(X));
1377 case Instruction::Cast:
1378 return createNodeForCast(cast<CastInst>(I));
1380 case Instruction::PHI:
1381 return createNodeForPHI(cast<PHINode>(I));
1383 default: // We cannot analyze this expression.
1388 return SCEVUnknown::get(V);
1393 //===----------------------------------------------------------------------===//
1394 // Iteration Count Computation Code
1397 /// getIterationCount - If the specified loop has a predictable iteration
1398 /// count, return it. Note that it is not valid to call this method on a
1399 /// loop without a loop-invariant iteration count.
1400 SCEVHandle ScalarEvolutionsImpl::getIterationCount(const Loop *L) {
1401 std::map<const Loop*, SCEVHandle>::iterator I = IterationCounts.find(L);
1402 if (I == IterationCounts.end()) {
1403 SCEVHandle ItCount = ComputeIterationCount(L);
1404 I = IterationCounts.insert(std::make_pair(L, ItCount)).first;
1405 if (ItCount != UnknownValue) {
1406 assert(ItCount->isLoopInvariant(L) &&
1407 "Computed trip count isn't loop invariant for loop!");
1408 ++NumTripCountsComputed;
1409 } else if (isa<PHINode>(L->getHeader()->begin())) {
1410 // Only count loops that have phi nodes as not being computable.
1411 ++NumTripCountsNotComputed;
1417 /// ComputeIterationCount - Compute the number of times the specified loop
1419 SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
1420 // If the loop has a non-one exit block count, we can't analyze it.
1421 if (L->getExitBlocks().size() != 1) return UnknownValue;
1423 // Okay, there is one exit block. Try to find the condition that causes the
1424 // loop to be exited.
1425 BasicBlock *ExitBlock = L->getExitBlocks()[0];
1427 BasicBlock *ExitingBlock = 0;
1428 for (pred_iterator PI = pred_begin(ExitBlock), E = pred_end(ExitBlock);
1430 if (L->contains(*PI)) {
1431 if (ExitingBlock == 0)
1434 return UnknownValue; // More than one block exiting!
1436 assert(ExitingBlock && "No exits from loop, something is broken!");
1438 // Okay, we've computed the exiting block. See what condition causes us to
1441 // FIXME: we should be able to handle switch instructions (with a single exit)
1442 // FIXME: We should handle cast of int to bool as well
1443 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1444 if (ExitBr == 0) return UnknownValue;
1445 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
1446 SetCondInst *ExitCond = dyn_cast<SetCondInst>(ExitBr->getCondition());
1447 if (ExitCond == 0) return UnknownValue;
1449 SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
1450 SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
1452 // Try to evaluate any dependencies out of the loop.
1453 SCEVHandle Tmp = getSCEVAtScope(LHS, L);
1454 if (!isa<SCEVCouldNotCompute>(Tmp)) LHS = Tmp;
1455 Tmp = getSCEVAtScope(RHS, L);
1456 if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
1458 // If the condition was exit on true, convert the condition to exit on false.
1459 Instruction::BinaryOps Cond;
1460 if (ExitBr->getSuccessor(1) == ExitBlock)
1461 Cond = ExitCond->getOpcode();
1463 Cond = ExitCond->getInverseCondition();
1465 // At this point, we would like to compute how many iterations of the loop the
1466 // predicate will return true for these inputs.
1467 if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) {
1468 // If there is a constant, force it into the RHS.
1469 std::swap(LHS, RHS);
1470 Cond = SetCondInst::getSwappedCondition(Cond);
1473 // FIXME: think about handling pointer comparisons! i.e.:
1474 // while (P != P+100) ++P;
1476 // If we have a comparison of a chrec against a constant, try to use value
1477 // ranges to answer this query.
1478 if (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
1479 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
1480 if (AddRec->getLoop() == L) {
1481 // Form the comparison range using the constant of the correct type so
1482 // that the ConstantRange class knows to do a signed or unsigned
1484 ConstantInt *CompVal = RHSC->getValue();
1485 const Type *RealTy = ExitCond->getOperand(0)->getType();
1486 CompVal = dyn_cast<ConstantInt>(ConstantExpr::getCast(CompVal, RealTy));
1488 // Form the constant range.
1489 ConstantRange CompRange(Cond, CompVal);
1491 // Now that we have it, if it's signed, convert it to an unsigned
1493 if (CompRange.getLower()->getType()->isSigned()) {
1494 const Type *NewTy = RHSC->getValue()->getType();
1495 Constant *NewL = ConstantExpr::getCast(CompRange.getLower(), NewTy);
1496 Constant *NewU = ConstantExpr::getCast(CompRange.getUpper(), NewTy);
1497 CompRange = ConstantRange(NewL, NewU);
1500 SCEVHandle Ret = AddRec->getNumIterationsInRange(CompRange);
1501 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
1506 case Instruction::SetNE: // while (X != Y)
1507 // Convert to: while (X-Y != 0)
1508 if (LHS->getType()->isInteger())
1509 return HowFarToZero(getMinusSCEV(LHS, RHS), L);
1511 case Instruction::SetEQ:
1512 // Convert to: while (X-Y == 0) // while (X == Y)
1513 if (LHS->getType()->isInteger())
1514 return HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
1518 std::cerr << "ComputeIterationCount ";
1519 if (ExitCond->getOperand(0)->getType()->isUnsigned())
1520 std::cerr << "[unsigned] ";
1521 std::cerr << *LHS << " "
1522 << Instruction::getOpcodeName(Cond) << " " << *RHS << "\n";
1526 return UnknownValue;
1529 /// getSCEVAtScope - Compute the value of the specified expression within the
1530 /// indicated loop (which may be null to indicate in no loop). If the
1531 /// expression cannot be evaluated, return UnknownValue.
1532 SCEVHandle ScalarEvolutionsImpl::getSCEVAtScope(SCEV *V, const Loop *L) {
1533 // FIXME: this should be turned into a virtual method on SCEV!
1535 if (isa<SCEVConstant>(V) || isa<SCEVUnknown>(V)) return V;
1536 if (SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
1537 // Avoid performing the look-up in the common case where the specified
1538 // expression has no loop-variant portions.
1539 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
1540 SCEVHandle OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
1541 if (OpAtScope != Comm->getOperand(i)) {
1542 if (OpAtScope == UnknownValue) return UnknownValue;
1543 // Okay, at least one of these operands is loop variant but might be
1544 // foldable. Build a new instance of the folded commutative expression.
1545 std::vector<SCEVHandle> NewOps(Comm->op_begin(), Comm->op_begin()+i-1);
1546 NewOps.push_back(OpAtScope);
1548 for (++i; i != e; ++i) {
1549 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L);
1550 if (OpAtScope == UnknownValue) return UnknownValue;
1551 NewOps.push_back(OpAtScope);
1553 if (isa<SCEVAddExpr>(Comm))
1554 return SCEVAddExpr::get(NewOps);
1555 assert(isa<SCEVMulExpr>(Comm) && "Only know about add and mul!");
1556 return SCEVMulExpr::get(NewOps);
1559 // If we got here, all operands are loop invariant.
1563 if (SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(V)) {
1564 SCEVHandle LHS = getSCEVAtScope(UDiv->getLHS(), L);
1565 if (LHS == UnknownValue) return LHS;
1566 SCEVHandle RHS = getSCEVAtScope(UDiv->getRHS(), L);
1567 if (RHS == UnknownValue) return RHS;
1568 if (LHS == UDiv->getLHS() && RHS == UDiv->getRHS())
1569 return UDiv; // must be loop invariant
1570 return SCEVUDivExpr::get(LHS, RHS);
1573 // If this is a loop recurrence for a loop that does not contain L, then we
1574 // are dealing with the final value computed by the loop.
1575 if (SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
1576 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
1577 // To evaluate this recurrence, we need to know how many times the AddRec
1578 // loop iterates. Compute this now.
1579 SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
1580 if (IterationCount == UnknownValue) return UnknownValue;
1581 IterationCount = getTruncateOrZeroExtend(IterationCount,
1584 // If the value is affine, simplify the expression evaluation to just
1585 // Start + Step*IterationCount.
1586 if (AddRec->isAffine())
1587 return SCEVAddExpr::get(AddRec->getStart(),
1588 SCEVMulExpr::get(IterationCount,
1589 AddRec->getOperand(1)));
1591 // Otherwise, evaluate it the hard way.
1592 return AddRec->evaluateAtIteration(IterationCount);
1594 return UnknownValue;
1597 //assert(0 && "Unknown SCEV type!");
1598 return UnknownValue;
1602 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the
1603 /// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which
1604 /// might be the same) or two SCEVCouldNotCompute objects.
1606 static std::pair<SCEVHandle,SCEVHandle>
1607 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec) {
1608 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!");
1609 SCEVConstant *L = dyn_cast<SCEVConstant>(AddRec->getOperand(0));
1610 SCEVConstant *M = dyn_cast<SCEVConstant>(AddRec->getOperand(1));
1611 SCEVConstant *N = dyn_cast<SCEVConstant>(AddRec->getOperand(2));
1613 // We currently can only solve this if the coefficients are constants.
1614 if (!L || !M || !N) {
1615 SCEV *CNC = new SCEVCouldNotCompute();
1616 return std::make_pair(CNC, CNC);
1619 Constant *Two = ConstantInt::get(L->getValue()->getType(), 2);
1621 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C
1622 Constant *C = L->getValue();
1623 // The B coefficient is M-N/2
1624 Constant *B = ConstantExpr::getSub(M->getValue(),
1625 ConstantExpr::getDiv(N->getValue(),
1627 // The A coefficient is N/2
1628 Constant *A = ConstantExpr::getDiv(N->getValue(), Two);
1630 // Compute the B^2-4ac term.
1631 Constant *SqrtTerm =
1632 ConstantExpr::getMul(ConstantInt::get(C->getType(), 4),
1633 ConstantExpr::getMul(A, C));
1634 SqrtTerm = ConstantExpr::getSub(ConstantExpr::getMul(B, B), SqrtTerm);
1636 // Compute floor(sqrt(B^2-4ac))
1637 ConstantUInt *SqrtVal =
1638 cast<ConstantUInt>(ConstantExpr::getCast(SqrtTerm,
1639 SqrtTerm->getType()->getUnsignedVersion()));
1640 uint64_t SqrtValV = SqrtVal->getValue();
1641 uint64_t SqrtValV2 = (uint64_t)sqrt(SqrtValV);
1642 // The square root might not be precise for arbitrary 64-bit integer
1643 // values. Do some sanity checks to ensure it's correct.
1644 if (SqrtValV2*SqrtValV2 > SqrtValV ||
1645 (SqrtValV2+1)*(SqrtValV2+1) <= SqrtValV) {
1646 SCEV *CNC = new SCEVCouldNotCompute();
1647 return std::make_pair(CNC, CNC);
1650 SqrtVal = ConstantUInt::get(Type::ULongTy, SqrtValV2);
1651 SqrtTerm = ConstantExpr::getCast(SqrtVal, SqrtTerm->getType());
1653 Constant *NegB = ConstantExpr::getNeg(B);
1654 Constant *TwoA = ConstantExpr::getMul(A, Two);
1656 // The divisions must be performed as signed divisions.
1657 const Type *SignedTy = NegB->getType()->getSignedVersion();
1658 NegB = ConstantExpr::getCast(NegB, SignedTy);
1659 TwoA = ConstantExpr::getCast(TwoA, SignedTy);
1660 SqrtTerm = ConstantExpr::getCast(SqrtTerm, SignedTy);
1662 Constant *Solution1 =
1663 ConstantExpr::getDiv(ConstantExpr::getAdd(NegB, SqrtTerm), TwoA);
1664 Constant *Solution2 =
1665 ConstantExpr::getDiv(ConstantExpr::getSub(NegB, SqrtTerm), TwoA);
1666 return std::make_pair(SCEVUnknown::get(Solution1),
1667 SCEVUnknown::get(Solution2));
1670 /// HowFarToZero - Return the number of times a backedge comparing the specified
1671 /// value to zero will execute. If not computable, return UnknownValue
1672 SCEVHandle ScalarEvolutionsImpl::HowFarToZero(SCEV *V, const Loop *L) {
1673 // If the value is a constant
1674 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
1675 // If the value is already zero, the branch will execute zero times.
1676 if (C->getValue()->isNullValue()) return C;
1677 return UnknownValue; // Otherwise it will loop infinitely.
1680 SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
1681 if (!AddRec || AddRec->getLoop() != L)
1682 return UnknownValue;
1684 if (AddRec->isAffine()) {
1685 // If this is an affine expression the execution count of this branch is
1688 // (0 - Start/Step) iff Start % Step == 0
1690 // Get the initial value for the loop.
1691 SCEVHandle Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop());
1692 SCEVHandle Step = AddRec->getOperand(1);
1694 Step = getSCEVAtScope(Step, L->getParentLoop());
1696 // Figure out if Start % Step == 0.
1697 // FIXME: We should add DivExpr and RemExpr operations to our AST.
1698 if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) {
1699 if (StepC->getValue()->equalsInt(1)) // N % 1 == 0
1700 return getNegativeSCEV(Start); // 0 - Start/1 == -Start
1701 if (StepC->getValue()->isAllOnesValue()) // N % -1 == 0
1702 return Start; // 0 - Start/-1 == Start
1704 // Check to see if Start is divisible by SC with no remainder.
1705 if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) {
1706 ConstantInt *StartCC = StartC->getValue();
1707 Constant *StartNegC = ConstantExpr::getNeg(StartCC);
1708 Constant *Rem = ConstantExpr::getRem(StartNegC, StepC->getValue());
1709 if (Rem->isNullValue()) {
1710 Constant *Result =ConstantExpr::getDiv(StartNegC,StepC->getValue());
1711 return SCEVUnknown::get(Result);
1715 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) {
1716 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
1717 // the quadratic equation to solve it.
1718 std::pair<SCEVHandle,SCEVHandle> Roots = SolveQuadraticEquation(AddRec);
1719 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
1720 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
1723 std::cerr << "HFTZ: " << *V << " - sol#1: " << *R1
1724 << " sol#2: " << *R2 << "\n";
1726 // Pick the smallest positive root value.
1727 assert(R1->getType()->isUnsigned()&&"Didn't canonicalize to unsigned?");
1728 if (ConstantBool *CB =
1729 dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
1731 if (CB != ConstantBool::True)
1732 std::swap(R1, R2); // R1 is the minimum root now.
1734 // We can only use this value if the chrec ends up with an exact zero
1735 // value at this index. When solving for "X*X != 5", for example, we
1736 // should not accept a root of 2.
1737 SCEVHandle Val = AddRec->evaluateAtIteration(R1);
1738 if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val))
1739 if (EvalVal->getValue()->isNullValue())
1740 return R1; // We found a quadratic root!
1745 return UnknownValue;
1748 /// HowFarToNonZero - Return the number of times a backedge checking the
1749 /// specified value for nonzero will execute. If not computable, return
1751 SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
1752 // Loops that look like: while (X == 0) are very strange indeed. We don't
1753 // handle them yet except for the trivial case. This could be expanded in the
1754 // future as needed.
1756 // If the value is a constant, check to see if it is known to be non-zero
1757 // already. If so, the backedge will execute zero times.
1758 if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
1759 Constant *Zero = Constant::getNullValue(C->getValue()->getType());
1760 Constant *NonZero = ConstantExpr::getSetNE(C->getValue(), Zero);
1761 if (NonZero == ConstantBool::True)
1762 return getSCEV(Zero);
1763 return UnknownValue; // Otherwise it will loop infinitely.
1766 // We could implement others, but I really doubt anyone writes loops like
1767 // this, and if they did, they would already be constant folded.
1768 return UnknownValue;
1771 static ConstantInt *
1772 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) {
1773 SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C));
1774 SCEVHandle Val = AddRec->evaluateAtIteration(InVal);
1775 assert(isa<SCEVConstant>(Val) &&
1776 "Evaluation of SCEV at constant didn't fold correctly?");
1777 return cast<SCEVConstant>(Val)->getValue();
1781 /// getNumIterationsInRange - Return the number of iterations of this loop that
1782 /// produce values in the specified constant range. Another way of looking at
1783 /// this is that it returns the first iteration number where the value is not in
1784 /// the condition, thus computing the exit count. If the iteration count can't
1785 /// be computed, an instance of SCEVCouldNotCompute is returned.
1786 SCEVHandle SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range) const {
1787 if (Range.isFullSet()) // Infinite loop.
1788 return new SCEVCouldNotCompute();
1790 // If the start is a non-zero constant, shift the range to simplify things.
1791 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart()))
1792 if (!SC->getValue()->isNullValue()) {
1793 std::vector<SCEVHandle> Operands(op_begin(), op_end());
1794 Operands[0] = getIntegerSCEV(0, SC->getType());
1795 SCEVHandle Shifted = SCEVAddRecExpr::get(Operands, getLoop());
1796 if (SCEVAddRecExpr *ShiftedAddRec = dyn_cast<SCEVAddRecExpr>(Shifted))
1797 return ShiftedAddRec->getNumIterationsInRange(
1798 Range.subtract(SC->getValue()));
1799 // This is strange and shouldn't happen.
1800 return new SCEVCouldNotCompute();
1803 // The only time we can solve this is when we have all constant indices.
1804 // Otherwise, we cannot determine the overflow conditions.
1805 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1806 if (!isa<SCEVConstant>(getOperand(i)))
1807 return new SCEVCouldNotCompute();
1810 // Okay at this point we know that all elements of the chrec are constants and
1811 // that the start element is zero.
1813 // First check to see if the range contains zero. If not, the first
1815 ConstantInt *Zero = ConstantInt::get(getType(), 0);
1816 if (!Range.contains(Zero)) return SCEVConstant::get(Zero);
1819 // If this is an affine expression then we have this situation:
1820 // Solve {0,+,A} in Range === Ax in Range
1822 // Since we know that zero is in the range, we know that the upper value of
1823 // the range must be the first possible exit value. Also note that we
1824 // already checked for a full range.
1825 ConstantInt *Upper = cast<ConstantInt>(Range.getUpper());
1826 ConstantInt *A = cast<SCEVConstant>(getOperand(1))->getValue();
1827 ConstantInt *One = ConstantInt::get(getType(), 1);
1829 // The exit value should be (Upper+A-1)/A.
1830 Constant *ExitValue = Upper;
1832 ExitValue = ConstantExpr::getSub(ConstantExpr::getAdd(Upper, A), One);
1833 ExitValue = ConstantExpr::getDiv(ExitValue, A);
1835 assert(isa<ConstantInt>(ExitValue) &&
1836 "Constant folding of integers not implemented?");
1838 // Evaluate at the exit value. If we really did fall out of the valid
1839 // range, then we computed our trip count, otherwise wrap around or other
1840 // things must have happened.
1841 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue);
1842 if (Range.contains(Val))
1843 return new SCEVCouldNotCompute(); // Something strange happened
1845 // Ensure that the previous value is in the range. This is a sanity check.
1846 assert(Range.contains(EvaluateConstantChrecAtConstant(this,
1847 ConstantExpr::getSub(ExitValue, One))) &&
1848 "Linear scev computation is off in a bad way!");
1849 return SCEVConstant::get(cast<ConstantInt>(ExitValue));
1850 } else if (isQuadratic()) {
1851 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the
1852 // quadratic equation to solve it. To do this, we must frame our problem in
1853 // terms of figuring out when zero is crossed, instead of when
1854 // Range.getUpper() is crossed.
1855 std::vector<SCEVHandle> NewOps(op_begin(), op_end());
1856 NewOps[0] = getNegativeSCEV(SCEVUnknown::get(Range.getUpper()));
1857 SCEVHandle NewAddRec = SCEVAddRecExpr::get(NewOps, getLoop());
1859 // Next, solve the constructed addrec
1860 std::pair<SCEVHandle,SCEVHandle> Roots =
1861 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec));
1862 SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first);
1863 SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second);
1865 // Pick the smallest positive root value.
1866 assert(R1->getType()->isUnsigned() && "Didn't canonicalize to unsigned?");
1867 if (ConstantBool *CB =
1868 dyn_cast<ConstantBool>(ConstantExpr::getSetLT(R1->getValue(),
1870 if (CB != ConstantBool::True)
1871 std::swap(R1, R2); // R1 is the minimum root now.
1873 // Make sure the root is not off by one. The returned iteration should
1874 // not be in the range, but the previous one should be. When solving
1875 // for "X*X < 5", for example, we should not return a root of 2.
1876 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this,
1878 if (Range.contains(R1Val)) {
1879 // The next iteration must be out of the range...
1881 ConstantExpr::getAdd(R1->getValue(),
1882 ConstantInt::get(R1->getType(), 1));
1884 R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
1885 if (!Range.contains(R1Val))
1886 return SCEVUnknown::get(NextVal);
1887 return new SCEVCouldNotCompute(); // Something strange happened
1890 // If R1 was not in the range, then it is a good return value. Make
1891 // sure that R1-1 WAS in the range though, just in case.
1893 ConstantExpr::getSub(R1->getValue(),
1894 ConstantInt::get(R1->getType(), 1));
1895 R1Val = EvaluateConstantChrecAtConstant(this, NextVal);
1896 if (Range.contains(R1Val))
1898 return new SCEVCouldNotCompute(); // Something strange happened
1903 // Fallback, if this is a general polynomial, figure out the progression
1904 // through brute force: evaluate until we find an iteration that fails the
1905 // test. This is likely to be slow, but getting an accurate trip count is
1906 // incredibly important, we will be able to simplify the exit test a lot, and
1907 // we are almost guaranteed to get a trip count in this case.
1908 ConstantInt *TestVal = ConstantInt::get(getType(), 0);
1909 ConstantInt *One = ConstantInt::get(getType(), 1);
1910 ConstantInt *EndVal = TestVal; // Stop when we wrap around.
1912 ++NumBruteForceEvaluations;
1913 SCEVHandle Val = evaluateAtIteration(SCEVConstant::get(TestVal));
1914 if (!isa<SCEVConstant>(Val)) // This shouldn't happen.
1915 return new SCEVCouldNotCompute();
1917 // Check to see if we found the value!
1918 if (!Range.contains(cast<SCEVConstant>(Val)->getValue()))
1919 return SCEVConstant::get(TestVal);
1921 // Increment to test the next index.
1922 TestVal = cast<ConstantInt>(ConstantExpr::getAdd(TestVal, One));
1923 } while (TestVal != EndVal);
1925 return new SCEVCouldNotCompute();
1930 //===----------------------------------------------------------------------===//
1931 // ScalarEvolution Class Implementation
1932 //===----------------------------------------------------------------------===//
1934 bool ScalarEvolution::runOnFunction(Function &F) {
1935 Impl = new ScalarEvolutionsImpl(F, getAnalysis<LoopInfo>());
1939 void ScalarEvolution::releaseMemory() {
1940 delete (ScalarEvolutionsImpl*)Impl;
1944 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
1945 AU.setPreservesAll();
1946 AU.addRequiredID(LoopSimplifyID);
1947 AU.addRequiredTransitive<LoopInfo>();
1950 SCEVHandle ScalarEvolution::getSCEV(Value *V) const {
1951 return ((ScalarEvolutionsImpl*)Impl)->getSCEV(V);
1954 SCEVHandle ScalarEvolution::getIterationCount(const Loop *L) const {
1955 return ((ScalarEvolutionsImpl*)Impl)->getIterationCount(L);
1958 bool ScalarEvolution::hasLoopInvariantIterationCount(const Loop *L) const {
1959 return !isa<SCEVCouldNotCompute>(getIterationCount(L));
1962 SCEVHandle ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) const {
1963 return ((ScalarEvolutionsImpl*)Impl)->getSCEVAtScope(getSCEV(V), L);
1966 void ScalarEvolution::deleteInstructionFromRecords(Instruction *I) const {
1967 return ((ScalarEvolutionsImpl*)Impl)->deleteInstructionFromRecords(I);
1971 /// shouldSubstituteIndVar - Return true if we should perform induction variable
1972 /// substitution for this variable. This is a hack because we don't have a
1973 /// strength reduction pass yet. When we do we will promote all vars, because
1974 /// we can strength reduce them later as desired.
1975 bool ScalarEvolution::shouldSubstituteIndVar(const SCEV *S) const {
1976 // Don't substitute high degree polynomials.
1977 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
1978 if (AddRec->getNumOperands() > 3) return false;
1983 static void PrintLoopInfo(std::ostream &OS, const ScalarEvolution *SE,
1985 // Print all inner loops first
1986 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
1987 PrintLoopInfo(OS, SE, *I);
1989 std::cerr << "Loop " << L->getHeader()->getName() << ": ";
1990 if (L->getExitBlocks().size() != 1)
1991 std::cerr << "<multiple exits> ";
1993 if (SE->hasLoopInvariantIterationCount(L)) {
1994 std::cerr << *SE->getIterationCount(L) << " iterations! ";
1996 std::cerr << "Unpredictable iteration count. ";
2002 void ScalarEvolution::print(std::ostream &OS) const {
2003 Function &F = ((ScalarEvolutionsImpl*)Impl)->F;
2004 LoopInfo &LI = ((ScalarEvolutionsImpl*)Impl)->LI;
2006 OS << "Classifying expressions for: " << F.getName() << "\n";
2007 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
2008 if ((*I)->getType()->isInteger()) {
2011 SCEVHandle SV = getSCEV(*I);
2015 if ((*I)->getType()->isIntegral()) {
2016 ConstantRange Bounds = SV->getValueRange();
2017 if (!Bounds.isFullSet())
2018 OS << "Bounds: " << Bounds << " ";
2021 if (const Loop *L = LI.getLoopFor((*I)->getParent())) {
2023 SCEVHandle ExitValue = getSCEVAtScope(*I, L->getParentLoop());
2024 if (isa<SCEVCouldNotCompute>(ExitValue)) {
2025 OS << "<<Unknown>>";
2035 OS << "Determining loop execution counts for: " << F.getName() << "\n";
2036 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I)
2037 PrintLoopInfo(OS, this, *I);
2040 //===----------------------------------------------------------------------===//
2041 // ScalarEvolutionRewriter Class Implementation
2042 //===----------------------------------------------------------------------===//
2044 Value *ScalarEvolutionRewriter::
2045 GetOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty) {
2046 assert((Ty->isInteger() || Ty->isFloatingPoint()) &&
2047 "Can only insert integer or floating point induction variables!");
2049 // Check to see if we already inserted one.
2050 SCEVHandle H = SCEVAddRecExpr::get(getIntegerSCEV(0, Ty),
2051 getIntegerSCEV(1, Ty), L);
2052 return ExpandCodeFor(H, 0, Ty);
2055 /// ExpandCodeFor - Insert code to directly compute the specified SCEV
2056 /// expression into the program. The inserted code is inserted into the
2057 /// specified block.
2058 Value *ScalarEvolutionRewriter::ExpandCodeFor(SCEVHandle SH,
2059 Instruction *InsertPt,
2061 std::map<SCEVHandle, Value*>::iterator ExistVal =InsertedExpressions.find(SH);
2063 if (ExistVal != InsertedExpressions.end()) {
2064 V = ExistVal->second;
2066 // Ask the recurrence object to expand the code for itself.
2067 V = SH->expandCodeFor(*this, InsertPt);
2068 // Cache the generated result.
2069 InsertedExpressions.insert(std::make_pair(SH, V));
2072 if (Ty == 0 || V->getType() == Ty)
2074 if (Constant *C = dyn_cast<Constant>(V))
2075 return ConstantExpr::getCast(C, Ty);
2076 else if (Instruction *I = dyn_cast<Instruction>(V)) {
2077 // Check to see if there is already a cast. If there is, use it.
2078 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
2080 if ((*UI)->getType() == Ty)
2081 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) {
2082 BasicBlock::iterator It = I; ++It;
2083 while (isa<PHINode>(It)) ++It;
2084 if (It != BasicBlock::iterator(CI)) {
2085 // Splice the cast immediately after the operand in question.
2086 I->getParent()->getInstList().splice(It,
2087 CI->getParent()->getInstList(),
2093 BasicBlock::iterator IP = I; ++IP;
2094 if (InvokeInst *II = dyn_cast<InvokeInst>(I))
2095 IP = II->getNormalDest()->begin();
2096 while (isa<PHINode>(IP)) ++IP;
2097 return new CastInst(V, Ty, V->getName(), IP);
2099 // FIXME: check to see if there is already a cast!
2100 return new CastInst(V, Ty, V->getName(), InsertPt);