1//===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
--- 96 unchanged lines hidden (view full) ---
105
106//===----------------------------------------------------------------------===//
107// SCEV class definitions
108//===----------------------------------------------------------------------===//
109
110//===----------------------------------------------------------------------===//
111// Implementation of the SCEV class.
112//
113
114SCEV::~SCEV() {}
115
116void SCEV::dump() const {
117 print(errs());
118 errs() << '\n';
119}
120
121void SCEV::print(std::ostream &o) const {
122 raw_os_ostream OS(o);
123 print(OS);
--- 15 unchanged lines hidden (view full) ---
139 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
140 return SC->getValue()->isAllOnesValue();
141 return false;
142}
143
144SCEVCouldNotCompute::SCEVCouldNotCompute() :
145 SCEV(scCouldNotCompute) {}
146
147void SCEVCouldNotCompute::Profile(FoldingSetNodeID &ID) const {
148 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
149}
150
151bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
152 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
153 return false;
154}
155
156const Type *SCEVCouldNotCompute::getType() const {
157 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
158 return 0;
--- 16 unchanged lines hidden (view full) ---
175 OS << "***COULDNOTCOMPUTE***";
176}
177
178bool SCEVCouldNotCompute::classof(const SCEV *S) {
179 return S->getSCEVType() == scCouldNotCompute;
180}
181
182const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
183 FoldingSetNodeID ID;
184 ID.AddInteger(scConstant);
185 ID.AddPointer(V);
186 void *IP = 0;
187 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
188 SCEV *S = SCEVAllocator.Allocate<SCEVConstant>();
189 new (S) SCEVConstant(V);
190 UniqueSCEVs.InsertNode(S, IP);
191 return S;
192}
193
194const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
195 return getConstant(ConstantInt::get(Val));
196}
197
198const SCEV*
199ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
200 return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
201}
202
203void SCEVConstant::Profile(FoldingSetNodeID &ID) const {
204 ID.AddInteger(scConstant);
205 ID.AddPointer(V);
206}
207
208const Type *SCEVConstant::getType() const { return V->getType(); }
209
210void SCEVConstant::print(raw_ostream &OS) const {
211 WriteAsOperand(OS, V, false);
212}
213
214SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
215 const SCEV* op, const Type *ty)
216 : SCEV(SCEVTy), Op(op), Ty(ty) {}
217
218void SCEVCastExpr::Profile(FoldingSetNodeID &ID) const {
219 ID.AddInteger(getSCEVType());
220 ID.AddPointer(Op);
221 ID.AddPointer(Ty);
222}
223
224bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
225 return Op->dominates(BB, DT);
226}
227
228SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
229 : SCEVCastExpr(scTruncate, op, ty) {
230 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
231 (Ty->isInteger() || isa<PointerType>(Ty)) &&
--- 63 unchanged lines hidden (view full) ---
295 return SE.getUMaxExpr(NewOps);
296 else
297 assert(0 && "Unknown commutative expr!");
298 }
299 }
300 return this;
301}
302
303void SCEVNAryExpr::Profile(FoldingSetNodeID &ID) const {
304 ID.AddInteger(getSCEVType());
305 ID.AddInteger(Operands.size());
306 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
307 ID.AddPointer(Operands[i]);
308}
309
310bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
311 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
312 if (!getOperand(i)->dominates(BB, DT))
313 return false;
314 }
315 return true;
316}
317
318void SCEVUDivExpr::Profile(FoldingSetNodeID &ID) const {
319 ID.AddInteger(scUDivExpr);
320 ID.AddPointer(LHS);
321 ID.AddPointer(RHS);
322}
323
324bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
325 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
326}
327
328void SCEVUDivExpr::print(raw_ostream &OS) const {
329 OS << "(" << *LHS << " /u " << *RHS << ")";
330}
331
332const Type *SCEVUDivExpr::getType() const {
333 // In most cases the types of LHS and RHS will be the same, but in some
334 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
335 // depend on the type for correctness, but handling types carefully can
336 // avoid extra casts in the SCEVExpander. The LHS is more likely to be
337 // a pointer type than the RHS, so use the RHS' type here.
338 return RHS->getType();
339}
340
341void SCEVAddRecExpr::Profile(FoldingSetNodeID &ID) const {
342 ID.AddInteger(scAddRecExpr);
343 ID.AddInteger(Operands.size());
344 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
345 ID.AddPointer(Operands[i]);
346 ID.AddPointer(L);
347}
348
349const SCEV *
350SCEVAddRecExpr::replaceSymbolicValuesWithConcrete(const SCEV *Sym,
351 const SCEV *Conc,
352 ScalarEvolution &SE) const {
353 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
354 const SCEV* H =
355 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
356 if (H != getOperand(i)) {
--- 27 unchanged lines hidden (view full) ---
384 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
385 if (!getOperand(i)->isLoopInvariant(QueryLoop))
386 return false;
387
388 // Otherwise it's loop-invariant.
389 return true;
390}
391
392void SCEVAddRecExpr::print(raw_ostream &OS) const {
393 OS << "{" << *Operands[0];
394 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
395 OS << ",+," << *Operands[i];
396 OS << "}<" << L->getHeader()->getName() + ">";
397}
398
399void SCEVUnknown::Profile(FoldingSetNodeID &ID) const {
400 ID.AddInteger(scUnknown);
401 ID.AddPointer(V);
402}
403
404bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
405 // All non-instruction values are loop invariant. All instructions are loop
406 // invariant if they are not contained in the specified loop.
407 // Instructions are never considered invariant in the function body
408 // (null loop) because they are defined within the "loop".
409 if (Instruction *I = dyn_cast<Instruction>(V))
410 return L && !L->contains(I->getParent());
411 return true;
--- 327 unchanged lines hidden (view full) ---
739const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
740 const Type *Ty) {
741 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
742 "This is not a truncating conversion!");
743 assert(isSCEVable(Ty) &&
744 "This is not a conversion to a SCEVable type!");
745 Ty = getEffectiveSCEVType(Ty);
746
747 // Fold if the operand is constant.
748 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
749 return getConstant(
750 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
751
752 // trunc(trunc(x)) --> trunc(x)
753 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
754 return getTruncateExpr(ST->getOperand(), Ty);
755
--- 8 unchanged lines hidden (view full) ---
764 // If the input value is a chrec scev, truncate the chrec's operands.
765 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
766 SmallVector<const SCEV*, 4> Operands;
767 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
768 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
769 return getAddRecExpr(Operands, AddRec->getLoop());
770 }
771
772 FoldingSetNodeID ID;
773 ID.AddInteger(scTruncate);
774 ID.AddPointer(Op);
775 ID.AddPointer(Ty);
776 void *IP = 0;
777 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
778 SCEV *S = SCEVAllocator.Allocate<SCEVTruncateExpr>();
779 new (S) SCEVTruncateExpr(Op, Ty);
780 UniqueSCEVs.InsertNode(S, IP);
781 return S;
782}
783
784const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
785 const Type *Ty) {
786 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
787 "This is not an extending conversion!");
788 assert(isSCEVable(Ty) &&
789 "This is not a conversion to a SCEVable type!");
790 Ty = getEffectiveSCEVType(Ty);
791
792 // Fold if the operand is constant.
793 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
794 const Type *IntTy = getEffectiveSCEVType(Ty);
795 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
796 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
797 return getConstant(cast<ConstantInt>(C));
798 }
799
800 // zext(zext(x)) --> zext(x)
--- 59 unchanged lines hidden (view full) ---
860 // Return the expression with the addrec on the outside.
861 return getAddRecExpr(getZeroExtendExpr(Start, Ty),
862 getSignExtendExpr(Step, Ty),
863 AR->getLoop());
864 }
865 }
866 }
867
868 FoldingSetNodeID ID;
869 ID.AddInteger(scZeroExtend);
870 ID.AddPointer(Op);
871 ID.AddPointer(Ty);
872 void *IP = 0;
873 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
874 SCEV *S = SCEVAllocator.Allocate<SCEVZeroExtendExpr>();
875 new (S) SCEVZeroExtendExpr(Op, Ty);
876 UniqueSCEVs.InsertNode(S, IP);
877 return S;
878}
879
880const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
881 const Type *Ty) {
882 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
883 "This is not an extending conversion!");
884 assert(isSCEVable(Ty) &&
885 "This is not a conversion to a SCEVable type!");
886 Ty = getEffectiveSCEVType(Ty);
887
888 // Fold if the operand is constant.
889 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
890 const Type *IntTy = getEffectiveSCEVType(Ty);
891 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
892 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
893 return getConstant(cast<ConstantInt>(C));
894 }
895
896 // sext(sext(x)) --> sext(x)
--- 43 unchanged lines hidden (view full) ---
940 // Return the expression with the addrec on the outside.
941 return getAddRecExpr(getSignExtendExpr(Start, Ty),
942 getSignExtendExpr(Step, Ty),
943 AR->getLoop());
944 }
945 }
946 }
947
948 FoldingSetNodeID ID;
949 ID.AddInteger(scSignExtend);
950 ID.AddPointer(Op);
951 ID.AddPointer(Ty);
952 void *IP = 0;
953 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
954 SCEV *S = SCEVAllocator.Allocate<SCEVSignExtendExpr>();
955 new (S) SCEVSignExtendExpr(Op, Ty);
956 UniqueSCEVs.InsertNode(S, IP);
957 return S;
958}
959
960/// getAnyExtendExpr - Return a SCEV for the given operand extended with
961/// unspecified bits out to the given type.
962///
963const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* Op,
964 const Type *Ty) {
965 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
--- 81 unchanged lines hidden (view full) ---
1047 ->getOperands(),
1048 NewScale, SE);
1049 } else {
1050 // A multiplication of a constant with some other value. Update
1051 // the map.
1052 SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
1053 const SCEV* Key = SE.getMulExpr(MulOps);
1054 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
1055 M.insert(std::make_pair(Key, NewScale));
1056 if (Pair.second) {
1057 NewOps.push_back(Pair.first->first);
1058 } else {
1059 Pair.first->second += NewScale;
1060 // The map already had an entry for this value, which may indicate
1061 // a folding opportunity.
1062 Interesting = true;
1063 }
1064 }
1065 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1066 // Pull a buried constant out to the outside.
1067 if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
1068 Interesting = true;
1069 AccumulatedConstant += Scale * C->getValue()->getValue();
1070 } else {
1071 // An ordinary operand. Update the map.
1072 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
1073 M.insert(std::make_pair(Ops[i], Scale));
1074 if (Pair.second) {
1075 NewOps.push_back(Pair.first->first);
1076 } else {
1077 Pair.first->second += Scale;
1078 // The map already had an entry for this value, which may indicate
1079 // a folding opportunity.
1080 Interesting = true;
1081 }
1082 }
--- 325 unchanged lines hidden (view full) ---
1408 }
1409
1410 // Otherwise couldn't fold anything into this recurrence. Move onto the
1411 // next one.
1412 }
1413
1414 // Okay, it looks like we really DO need an add expr. Check to see if we
1415 // already have one, otherwise create a new one.
1416 FoldingSetNodeID ID;
1417 ID.AddInteger(scAddExpr);
1418 ID.AddInteger(Ops.size());
1419 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1420 ID.AddPointer(Ops[i]);
1421 void *IP = 0;
1422 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1423 SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>();
1424 new (S) SCEVAddExpr(Ops);
1425 UniqueSCEVs.InsertNode(S, IP);
1426 return S;
1427}
1428
1429
1430/// getMulExpr - Get a canonical multiply expression, or something simpler if
1431/// possible.
1432const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
1433 assert(!Ops.empty() && "Cannot get empty mul!");
1434#ifndef NDEBUG
--- 144 unchanged lines hidden (view full) ---
1579 }
1580
1581 // Otherwise couldn't fold anything into this recurrence. Move onto the
1582 // next one.
1583 }
1584
1585 // Okay, it looks like we really DO need an mul expr. Check to see if we
1586 // already have one, otherwise create a new one.
1587 FoldingSetNodeID ID;
1588 ID.AddInteger(scMulExpr);
1589 ID.AddInteger(Ops.size());
1590 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1591 ID.AddPointer(Ops[i]);
1592 void *IP = 0;
1593 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1594 SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>();
1595 new (S) SCEVMulExpr(Ops);
1596 UniqueSCEVs.InsertNode(S, IP);
1597 return S;
1598}
1599
1600/// getUDivExpr - Get a canonical multiply expression, or something simpler if
1601/// possible.
1602const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
1603 const SCEV *RHS) {
1604 assert(getEffectiveSCEVType(LHS->getType()) ==
1605 getEffectiveSCEVType(RHS->getType()) &&
--- 73 unchanged lines hidden (view full) ---
1679 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1680 Constant *LHSCV = LHSC->getValue();
1681 Constant *RHSCV = RHSC->getValue();
1682 return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
1683 RHSCV)));
1684 }
1685 }
1686
1687 FoldingSetNodeID ID;
1688 ID.AddInteger(scUDivExpr);
1689 ID.AddPointer(LHS);
1690 ID.AddPointer(RHS);
1691 void *IP = 0;
1692 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1693 SCEV *S = SCEVAllocator.Allocate<SCEVUDivExpr>();
1694 new (S) SCEVUDivExpr(LHS, RHS);
1695 UniqueSCEVs.InsertNode(S, IP);
1696 return S;
1697}
1698
1699
1700/// getAddRecExpr - Get an add recurrence expression for the specified loop.
1701/// Simplify the expression as much as possible.
1702const SCEV* ScalarEvolution::getAddRecExpr(const SCEV* Start,
1703 const SCEV* Step, const Loop *L) {
1704 SmallVector<const SCEV*, 4> Operands;
--- 55 unchanged lines hidden (view full) ---
1760 // Ok, both add recurrences are valid after the transformation.
1761 return getAddRecExpr(NestedOperands, NestedLoop);
1762 }
1763 // Reset Operands to its original state.
1764 Operands[0] = NestedAR;
1765 }
1766 }
1767
1768 FoldingSetNodeID ID;
1769 ID.AddInteger(scAddRecExpr);
1770 ID.AddInteger(Operands.size());
1771 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
1772 ID.AddPointer(Operands[i]);
1773 ID.AddPointer(L);
1774 void *IP = 0;
1775 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1776 SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
1777 new (S) SCEVAddRecExpr(Operands, L);
1778 UniqueSCEVs.InsertNode(S, IP);
1779 return S;
1780}
1781
1782const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
1783 const SCEV *RHS) {
1784 SmallVector<const SCEV*, 2> Ops;
1785 Ops.push_back(LHS);
1786 Ops.push_back(RHS);
1787 return getSMaxExpr(Ops);
--- 70 unchanged lines hidden (view full) ---
1858 }
1859
1860 if (Ops.size() == 1) return Ops[0];
1861
1862 assert(!Ops.empty() && "Reduced smax down to nothing!");
1863
1864 // Okay, it looks like we really DO need an smax expr. Check to see if we
1865 // already have one, otherwise create a new one.
1866 FoldingSetNodeID ID;
1867 ID.AddInteger(scSMaxExpr);
1868 ID.AddInteger(Ops.size());
1869 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1870 ID.AddPointer(Ops[i]);
1871 void *IP = 0;
1872 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1873 SCEV *S = SCEVAllocator.Allocate<SCEVSMaxExpr>();
1874 new (S) SCEVSMaxExpr(Ops);
1875 UniqueSCEVs.InsertNode(S, IP);
1876 return S;
1877}
1878
1879const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
1880 const SCEV *RHS) {
1881 SmallVector<const SCEV*, 2> Ops;
1882 Ops.push_back(LHS);
1883 Ops.push_back(RHS);
1884 return getUMaxExpr(Ops);
--- 70 unchanged lines hidden (view full) ---
1955 }
1956
1957 if (Ops.size() == 1) return Ops[0];
1958
1959 assert(!Ops.empty() && "Reduced umax down to nothing!");
1960
1961 // Okay, it looks like we really DO need a umax expr. Check to see if we
1962 // already have one, otherwise create a new one.
1963 FoldingSetNodeID ID;
1964 ID.AddInteger(scUMaxExpr);
1965 ID.AddInteger(Ops.size());
1966 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1967 ID.AddPointer(Ops[i]);
1968 void *IP = 0;
1969 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1970 SCEV *S = SCEVAllocator.Allocate<SCEVUMaxExpr>();
1971 new (S) SCEVUMaxExpr(Ops);
1972 UniqueSCEVs.InsertNode(S, IP);
1973 return S;
1974}
1975
1976const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
1977 const SCEV *RHS) {
1978 // ~smax(~x, ~y) == smin(x, y).
1979 return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
1980}
1981
--- 4 unchanged lines hidden (view full) ---
1986}
1987
1988const SCEV* ScalarEvolution::getUnknown(Value *V) {
1989 // Don't attempt to do anything other than create a SCEVUnknown object
1990 // here. createSCEV only calls getUnknown after checking for all other
1991 // interesting possibilities, and any other code that calls getUnknown
1992 // is doing so in order to hide a value from SCEV canonicalization.
1993
1994 FoldingSetNodeID ID;
1995 ID.AddInteger(scUnknown);
1996 ID.AddPointer(V);
1997 void *IP = 0;
1998 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1999 SCEV *S = SCEVAllocator.Allocate<SCEVUnknown>();
2000 new (S) SCEVUnknown(V);
2001 UniqueSCEVs.InsertNode(S, IP);
2002 return S;
2003}
2004
2005//===----------------------------------------------------------------------===//
2006// Basic SCEV Analysis and PHI Idiom Recognition Code
2007//
2008
2009/// isSCEVable - Test if values of the given type are analyzable within
2010/// the SCEV framework. This primarily includes integer types, and it
--- 37 unchanged lines hidden (view full) ---
2048 if (Ty->isInteger())
2049 return Ty;
2050
2051 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
2052 return TD->getIntPtrType();
2053}
2054
2055const SCEV* ScalarEvolution::getCouldNotCompute() {
2056 return &CouldNotCompute;
2057}
2058
2059/// hasSCEV - Return true if the SCEV for this value has already been
2060/// computed.
2061bool ScalarEvolution::hasSCEV(Value *V) const {
2062 return Scalars.count(V);
2063}
2064
--- 794 unchanged lines hidden (view full) ---
2859 // succeeds, procede to actually compute a backedge-taken count and
2860 // update the value. The temporary CouldNotCompute value tells SCEV
2861 // code elsewhere that it shouldn't attempt to request a new
2862 // backedge-taken count, which could result in infinite recursion.
2863 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2864 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2865 if (Pair.second) {
2866 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
2867 if (ItCount.Exact != getCouldNotCompute()) {
2868 assert(ItCount.Exact->isLoopInvariant(L) &&
2869 ItCount.Max->isLoopInvariant(L) &&
2870 "Computed trip count isn't loop invariant for loop!");
2871 ++NumTripCountsComputed;
2872
2873 // Update the value in the map.
2874 Pair.first->second = ItCount;
2875 } else {
2876 if (ItCount.Max != getCouldNotCompute())
2877 // Update the value in the map.
2878 Pair.first->second = ItCount;
2879 if (isa<PHINode>(L->getHeader()->begin()))
2880 // Only count loops that have phi nodes as not being computable.
2881 ++NumTripCountsNotComputed;
2882 }
2883
2884 // Now that we know more about the trip count for this loop, forget any
--- 49 unchanged lines hidden (view full) ---
2934/// ComputeBackedgeTakenCount - Compute the number of times the backedge
2935/// of the specified loop will execute.
2936ScalarEvolution::BackedgeTakenInfo
2937ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2938 SmallVector<BasicBlock*, 8> ExitingBlocks;
2939 L->getExitingBlocks(ExitingBlocks);
2940
2941 // Examine all exits and pick the most conservative values.
2942 const SCEV* BECount = getCouldNotCompute();
2943 const SCEV* MaxBECount = getCouldNotCompute();
2944 bool CouldNotComputeBECount = false;
2945 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2946 BackedgeTakenInfo NewBTI =
2947 ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
2948
2949 if (NewBTI.Exact == getCouldNotCompute()) {
2950 // We couldn't compute an exact value for this exit, so
2951 // we won't be able to compute an exact value for the loop.
2952 CouldNotComputeBECount = true;
2953 BECount = getCouldNotCompute();
2954 } else if (!CouldNotComputeBECount) {
2955 if (BECount == getCouldNotCompute())
2956 BECount = NewBTI.Exact;
2957 else
2958 BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
2959 }
2960 if (MaxBECount == getCouldNotCompute())
2961 MaxBECount = NewBTI.Max;
2962 else if (NewBTI.Max != getCouldNotCompute())
2963 MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
2964 }
2965
2966 return BackedgeTakenInfo(BECount, MaxBECount);
2967}
2968
2969/// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
2970/// of the specified loop will execute if it exits via the specified block.
2971ScalarEvolution::BackedgeTakenInfo
2972ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
2973 BasicBlock *ExitingBlock) {
2974
2975 // Okay, we've chosen an exiting block. See what condition causes us to
2976 // exit at this block.
2977 //
2978 // FIXME: we should be able to handle switch instructions (with a single exit)
2979 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2980 if (ExitBr == 0) return getCouldNotCompute();
2981 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2982
2983 // At this point, we know we have a conditional branch that determines whether
2984 // the loop is exited. However, we don't know if the branch is executed each
2985 // time through the loop. If not, then the execution count of the branch will
2986 // not be equal to the trip count of the loop.
2987 //
2988 // Currently we check for this by checking to see if the Exit branch goes to
--- 12 unchanged lines hidden (view full) ---
3001 ExitBr->getSuccessor(1) != L->getHeader() &&
3002 ExitBr->getParent() != L->getHeader()) {
3003 // The simple checks failed, try climbing the unique predecessor chain
3004 // up to the header.
3005 bool Ok = false;
3006 for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
3007 BasicBlock *Pred = BB->getUniquePredecessor();
3008 if (!Pred)
3009 return getCouldNotCompute();
3010 TerminatorInst *PredTerm = Pred->getTerminator();
3011 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
3012 BasicBlock *PredSucc = PredTerm->getSuccessor(i);
3013 if (PredSucc == BB)
3014 continue;
3015 // If the predecessor has a successor that isn't BB and isn't
3016 // outside the loop, assume the worst.
3017 if (L->contains(PredSucc))
3018 return getCouldNotCompute();
3019 }
3020 if (Pred == L->getHeader()) {
3021 Ok = true;
3022 break;
3023 }
3024 BB = Pred;
3025 }
3026 if (!Ok)
3027 return getCouldNotCompute();
3028 }
3029
3030 // Procede to the next level to examine the exit condition expression.
3031 return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
3032 ExitBr->getSuccessor(0),
3033 ExitBr->getSuccessor(1));
3034}
3035
--- 8 unchanged lines hidden (view full) ---
3044 // Check if the controlling expression for this loop is an And or Or.
3045 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
3046 if (BO->getOpcode() == Instruction::And) {
3047 // Recurse on the operands of the and.
3048 BackedgeTakenInfo BTI0 =
3049 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3050 BackedgeTakenInfo BTI1 =
3051 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3052 const SCEV* BECount = getCouldNotCompute();
3053 const SCEV* MaxBECount = getCouldNotCompute();
3054 if (L->contains(TBB)) {
3055 // Both conditions must be true for the loop to continue executing.
3056 // Choose the less conservative count.
3057 if (BTI0.Exact == getCouldNotCompute() ||
3058 BTI1.Exact == getCouldNotCompute())
3059 BECount = getCouldNotCompute();
3060 else
3061 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3062 if (BTI0.Max == getCouldNotCompute())
3063 MaxBECount = BTI1.Max;
3064 else if (BTI1.Max == getCouldNotCompute())
3065 MaxBECount = BTI0.Max;
3066 else
3067 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3068 } else {
3069 // Both conditions must be true for the loop to exit.
3070 assert(L->contains(FBB) && "Loop block has no successor in loop!");
3071 if (BTI0.Exact != getCouldNotCompute() &&
3072 BTI1.Exact != getCouldNotCompute())
3073 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3074 if (BTI0.Max != getCouldNotCompute() &&
3075 BTI1.Max != getCouldNotCompute())
3076 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3077 }
3078
3079 return BackedgeTakenInfo(BECount, MaxBECount);
3080 }
3081 if (BO->getOpcode() == Instruction::Or) {
3082 // Recurse on the operands of the or.
3083 BackedgeTakenInfo BTI0 =
3084 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3085 BackedgeTakenInfo BTI1 =
3086 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3087 const SCEV* BECount = getCouldNotCompute();
3088 const SCEV* MaxBECount = getCouldNotCompute();
3089 if (L->contains(FBB)) {
3090 // Both conditions must be false for the loop to continue executing.
3091 // Choose the less conservative count.
3092 if (BTI0.Exact == getCouldNotCompute() ||
3093 BTI1.Exact == getCouldNotCompute())
3094 BECount = getCouldNotCompute();
3095 else
3096 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3097 if (BTI0.Max == getCouldNotCompute())
3098 MaxBECount = BTI1.Max;
3099 else if (BTI1.Max == getCouldNotCompute())
3100 MaxBECount = BTI0.Max;
3101 else
3102 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3103 } else {
3104 // Both conditions must be false for the loop to exit.
3105 assert(L->contains(TBB) && "Loop block has no successor in loop!");
3106 if (BTI0.Exact != getCouldNotCompute() &&
3107 BTI1.Exact != getCouldNotCompute())
3108 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3109 if (BTI0.Max != getCouldNotCompute() &&
3110 BTI1.Max != getCouldNotCompute())
3111 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3112 }
3113
3114 return BackedgeTakenInfo(BECount, MaxBECount);
3115 }
3116 }
3117
3118 // With an icmp, it may be feasible to compute an exact backedge-taken count.
--- 160 unchanged lines hidden (view full) ---
3279/// 'icmp op load X, cst', try to see if we can compute the backedge
3280/// execution count.
3281const SCEV *
3282ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
3283 LoadInst *LI,
3284 Constant *RHS,
3285 const Loop *L,
3286 ICmpInst::Predicate predicate) {
3287 if (LI->isVolatile()) return getCouldNotCompute();
3288
3289 // Check to see if the loaded pointer is a getelementptr of a global.
3290 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3291 if (!GEP) return getCouldNotCompute();
3292
3293 // Make sure that it is really a constant global we are gepping, with an
3294 // initializer, and make sure the first IDX is really 0.
3295 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
3296 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
3297 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
3298 !cast<Constant>(GEP->getOperand(1))->isNullValue())
3299 return getCouldNotCompute();
3300
3301 // Okay, we allow one non-constant index into the GEP instruction.
3302 Value *VarIdx = 0;
3303 std::vector<ConstantInt*> Indexes;
3304 unsigned VarIdxNum = 0;
3305 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
3306 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
3307 Indexes.push_back(CI);
3308 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
3309 if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's.
3310 VarIdx = GEP->getOperand(i);
3311 VarIdxNum = i-2;
3312 Indexes.push_back(0);
3313 }
3314
3315 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
3316 // Check to see if X is a loop variant variable value now.
3317 const SCEV* Idx = getSCEV(VarIdx);
3318 Idx = getSCEVAtScope(Idx, L);
3319
3320 // We can only recognize very limited forms of loop index expressions, in
3321 // particular, only affine AddRec's like {C1,+,C2}.
3322 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
3323 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
3324 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
3325 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
3326 return getCouldNotCompute();
3327
3328 unsigned MaxSteps = MaxBruteForceIterations;
3329 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
3330 ConstantInt *ItCst =
3331 ConstantInt::get(cast<IntegerType>(IdxExpr->getType()), IterationNum);
3332 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
3333
3334 // Form the GEP offset.
--- 10 unchanged lines hidden (view full) ---
3345 errs() << "\n***\n*** Computed loop count " << *ItCst
3346 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
3347 << "***\n";
3348#endif
3349 ++NumArrayLenItCounts;
3350 return getConstant(ItCst); // Found terminating iteration!
3351 }
3352 }
3353 return getCouldNotCompute();
3354}
3355
3356
3357/// CanConstantFold - Return true if we can constant fold an instruction of the
3358/// specified type, assuming that all operands were constants.
3359static bool CanConstantFold(const Instruction *I) {
3360 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
3361 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
--- 124 unchanged lines hidden (view full) ---
3486 PHIVal = NextPHI;
3487 }
3488}
3489
3490/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
3491/// constant number of times (the condition evolves only from constants),
3492/// try to evaluate a few iterations of the loop until we get the exit
3493/// condition gets a value of ExitWhen (true or false). If we cannot
3494/// evaluate the trip count of the loop, return getCouldNotCompute().
3495const SCEV *
3496ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
3497 Value *Cond,
3498 bool ExitWhen) {
3499 PHINode *PN = getConstantEvolvingPHI(Cond, L);
3500 if (PN == 0) return getCouldNotCompute();
3501
3502 // Since the loop is canonicalized, the PHI node must have two entries. One
3503 // entry must be a constant (coming in from outside of the loop), and the
3504 // second must be derived from the same PHI.
3505 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
3506 Constant *StartCST =
3507 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
3508 if (StartCST == 0) return getCouldNotCompute(); // Must be a constant.
3509
3510 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3511 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3512 if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI.
3513
3514 // Okay, we find a PHI node that defines the trip count of this loop. Execute
3515 // the loop symbolically to determine when the condition gets a value of
3516 // "ExitWhen".
3517 unsigned IterationNum = 0;
3518 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
3519 for (Constant *PHIVal = StartCST;
3520 IterationNum != MaxIterations; ++IterationNum) {
3521 ConstantInt *CondVal =
3522 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
3523
3524 // Couldn't symbolically evaluate.
3525 if (!CondVal) return getCouldNotCompute();
3526
3527 if (CondVal->getValue() == uint64_t(ExitWhen)) {
3528 ++NumBruteForceTripCountsComputed;
3529 return getConstant(Type::Int32Ty, IterationNum);
3530 }
3531
3532 // Compute the value of the PHI node for the next iteration.
3533 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
3534 if (NextPHI == 0 || NextPHI == PHIVal)
3535 return getCouldNotCompute();// Couldn't evaluate or not making progress...
3536 PHIVal = NextPHI;
3537 }
3538
3539 // Too many iterations were needed to evaluate.
3540 return getCouldNotCompute();
3541}
3542
3543/// getSCEVAtScope - Return a SCEV expression handle for the specified value
3544/// at the specified scope in the program. The L value specifies a loop
3545/// nest to evaluate the expression at, where null is the top-level or a
3546/// specified loop is immediately inside of the loop.
3547///
3548/// This method can be used to compute the exit value for a variable defined
--- 22 unchanged lines hidden (view full) ---
3571 if (const SCEVConstant *BTCC =
3572 dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
3573 // Okay, we know how many times the containing loop executes. If
3574 // this is a constant evolving PHI node, get the final value at
3575 // the specified iteration number.
3576 Constant *RV = getConstantEvolutionLoopExitValue(PN,
3577 BTCC->getValue()->getValue(),
3578 LI);
3579 if (RV) return getSCEV(RV);
3580 }
3581 }
3582
3583 // Okay, this is an expression that we cannot symbolically evaluate
3584 // into a SCEV. Check to see if it's possible to symbolically evaluate
3585 // the arguments into constants, and if so, try to constant propagate the
3586 // result. This is particularly useful for computing loop exit values.
3587 if (CanConstantFold(I)) {
3588 // Check to see if we've folded this instruction at this loop before.
3589 std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
3590 std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
3591 Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
3592 if (!Pair.second)
3593 return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
3594
3595 std::vector<Constant*> Operands;
3596 Operands.reserve(I->getNumOperands());
3597 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3598 Value *Op = I->getOperand(i);
3599 if (Constant *C = dyn_cast<Constant>(Op)) {
3600 Operands.push_back(C);
3601 } else {
--- 32 unchanged lines hidden (view full) ---
3634 Constant *C;
3635 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
3636 C = ConstantFoldCompareInstOperands(CI->getPredicate(),
3637 &Operands[0], Operands.size());
3638 else
3639 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
3640 &Operands[0], Operands.size());
3641 Pair.first->second = C;
3642 return getSCEV(C);
3643 }
3644 }
3645
3646 // This is some other type of SCEVUnknown, just return it.
3647 return V;
3648 }
3649
3650 if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
--- 37 unchanged lines hidden (view full) ---
3688
3689 // If this is a loop recurrence for a loop that does not contain L, then we
3690 // are dealing with the final value computed by the loop.
3691 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3692 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3693 // To evaluate this recurrence, we need to know how many times the AddRec
3694 // loop iterates. Compute this now.
3695 const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
3696 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
3697
3698 // Then, evaluate the AddRec.
3699 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3700 }
3701 return AddRec;
3702 }
3703
3704 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
--- 138 unchanged lines hidden (view full) ---
3843
3844/// HowFarToZero - Return the number of times a backedge comparing the specified
3845/// value to zero will execute. If not computable, return CouldNotCompute.
3846const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3847 // If the value is a constant
3848 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3849 // If the value is already zero, the branch will execute zero times.
3850 if (C->getValue()->isZero()) return C;
3851 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3852 }
3853
3854 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3855 if (!AddRec || AddRec->getLoop() != L)
3856 return getCouldNotCompute();
3857
3858 if (AddRec->isAffine()) {
3859 // If this is an affine expression, the execution count of this branch is
3860 // the minimum unsigned root of the following equation:
3861 //
3862 // Start + Step*N = 0 (mod 2^BW)
3863 //
3864 // equivalent to:
--- 47 unchanged lines hidden (view full) ---
3912 // should not accept a root of 2.
3913 const SCEV* Val = AddRec->evaluateAtIteration(R1, *this);
3914 if (Val->isZero())
3915 return R1; // We found a quadratic root!
3916 }
3917 }
3918 }
3919
3920 return getCouldNotCompute();
3921}
3922
3923/// HowFarToNonZero - Return the number of times a backedge checking the
3924/// specified value for nonzero will execute. If not computable, return
3925/// CouldNotCompute
3926const SCEV* ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3927 // Loops that look like: while (X == 0) are very strange indeed. We don't
3928 // handle them yet except for the trivial case. This could be expanded in the
3929 // future as needed.
3930
3931 // If the value is a constant, check to see if it is known to be non-zero
3932 // already. If so, the backedge will execute zero times.
3933 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3934 if (!C->getValue()->isNullValue())
3935 return getIntegerSCEV(0, C->getType());
3936 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3937 }
3938
3939 // We could implement others, but I really doubt anyone writes loops like
3940 // this, and if they did, they would already be constant folded.
3941 return getCouldNotCompute();
3942}
3943
3944/// getLoopPredecessor - If the given loop's header has exactly one unique
3945/// predecessor outside the loop, return it. Otherwise return null.
3946///
3947BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3948 BasicBlock *Header = L->getHeader();
3949 BasicBlock *Pred = 0;
--- 201 unchanged lines hidden (view full) ---
4151
4152 // Check Add for unsigned overflow.
4153 // TODO: More sophisticated things could be done here.
4154 const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
4155 const SCEV* OperandExtendedAdd =
4156 getAddExpr(getZeroExtendExpr(Diff, WideTy),
4157 getZeroExtendExpr(RoundUp, WideTy));
4158 if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
4159 return getCouldNotCompute();
4160
4161 return getUDivExpr(Add, Step);
4162}
4163
4164/// HowManyLessThans - Return the number of times a backedge containing the
4165/// specified less-than comparison will execute. If not computable, return
4166/// CouldNotCompute.
4167ScalarEvolution::BackedgeTakenInfo
4168ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
4169 const Loop *L, bool isSigned) {
4170 // Only handle: "ADDREC < LoopInvariant".
4171 if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
4172
4173 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
4174 if (!AddRec || AddRec->getLoop() != L)
4175 return getCouldNotCompute();
4176
4177 if (AddRec->isAffine()) {
4178 // FORNOW: We only support unit strides.
4179 unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
4180 const SCEV* Step = AddRec->getStepRecurrence(*this);
4181
4182 // TODO: handle non-constant strides.
4183 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
4184 if (!CStep || CStep->isZero())
4185 return getCouldNotCompute();
4186 if (CStep->isOne()) {
4187 // With unit stride, the iteration never steps past the limit value.
4188 } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
4189 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
4190 // Test whether a positive iteration iteration can step past the limit
4191 // value and past the maximum value for its type in a single step.
4192 if (isSigned) {
4193 APInt Max = APInt::getSignedMaxValue(BitWidth);
4194 if ((Max - CStep->getValue()->getValue())
4195 .slt(CLimit->getValue()->getValue()))
4196 return getCouldNotCompute();
4197 } else {
4198 APInt Max = APInt::getMaxValue(BitWidth);
4199 if ((Max - CStep->getValue()->getValue())
4200 .ult(CLimit->getValue()->getValue()))
4201 return getCouldNotCompute();
4202 }
4203 } else
4204 // TODO: handle non-constant limit values below.
4205 return getCouldNotCompute();
4206 } else
4207 // TODO: handle negative strides below.
4208 return getCouldNotCompute();
4209
4210 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
4211 // m. So, we count the number of iterations in which {n,+,s} < m is true.
4212 // Note that we cannot simply return max(m-n,0)/s because it's not safe to
4213 // treat m-n as signed nor unsigned due to overflow possibility.
4214
4215 // First, we get the value of the LHS in the first iteration: n
4216 const SCEV* Start = AddRec->getOperand(0);
--- 23 unchanged lines hidden (view full) ---
4240 .lshr(GetMinLeadingZeros(End)));
4241
4242 // Finally, we subtract these two values and divide, rounding up, to get
4243 // the number of times the backedge is executed.
4244 const SCEV* BECount = getBECount(Start, End, Step);
4245
4246 // The maximum backedge count is similar, except using the minimum start
4247 // value and the maximum end value.
4248 const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);
4249
4250 return BackedgeTakenInfo(BECount, MaxBECount);
4251 }
4252
4253 return getCouldNotCompute();
4254}
4255
4256/// getNumIterationsInRange - Return the number of iterations of this loop that
4257/// produce values in the specified constant range. Another way of looking at
4258/// this is that it returns the first iteration number where the value is not in
4259/// the condition, thus computing the exit count. If the iteration count can't
4260/// be computed, an instance of SCEVCouldNotCompute is returned.
4261const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
--- 171 unchanged lines hidden (view full) ---
4433ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
4434 : CallbackVH(V), SE(se) {}
4435
4436//===----------------------------------------------------------------------===//
4437// ScalarEvolution Class Implementation
4438//===----------------------------------------------------------------------===//
4439
4440ScalarEvolution::ScalarEvolution()
4441 : FunctionPass(&ID) {
4442}
4443
4444bool ScalarEvolution::runOnFunction(Function &F) {
4445 this->F = &F;
4446 LI = &getAnalysis<LoopInfo>();
4447 TD = getAnalysisIfAvailable<TargetData>();
4448 return false;
4449}
4450
4451void ScalarEvolution::releaseMemory() {
4452 Scalars.clear();
4453 BackedgeTakenCounts.clear();
4454 ConstantEvolutionLoopExitValue.clear();
4455 ValuesAtScopes.clear();
4456 UniqueSCEVs.clear();
4457 SCEVAllocator.Reset();
4458}
4459
4460void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
4461 AU.setPreservesAll();
4462 AU.addRequiredTransitive<LoopInfo>();
4463}
4464
4465bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
--- 81 unchanged lines hidden ---
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
--- 96 unchanged lines hidden (view full) ---
105
106//===----------------------------------------------------------------------===//
107// SCEV class definitions
108//===----------------------------------------------------------------------===//
109
110//===----------------------------------------------------------------------===//
111// Implementation of the SCEV class.
112//
113
114SCEV::~SCEV() {}
115
116void SCEV::dump() const {
117 print(errs());
118 errs() << '\n';
119}
120
121void SCEV::print(std::ostream &o) const {
122 raw_os_ostream OS(o);
123 print(OS);
--- 15 unchanged lines hidden (view full) ---
139 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
140 return SC->getValue()->isAllOnesValue();
141 return false;
142}
143
144SCEVCouldNotCompute::SCEVCouldNotCompute() :
145 SCEV(scCouldNotCompute) {}
146
147void SCEVCouldNotCompute::Profile(FoldingSetNodeID &ID) const {
148 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
149}
150
151bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
152 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
153 return false;
154}
155
156const Type *SCEVCouldNotCompute::getType() const {
157 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
158 return 0;
--- 16 unchanged lines hidden (view full) ---
175 OS << "***COULDNOTCOMPUTE***";
176}
177
178bool SCEVCouldNotCompute::classof(const SCEV *S) {
179 return S->getSCEVType() == scCouldNotCompute;
180}
181
182const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
183 FoldingSetNodeID ID;
184 ID.AddInteger(scConstant);
185 ID.AddPointer(V);
186 void *IP = 0;
187 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
188 SCEV *S = SCEVAllocator.Allocate<SCEVConstant>();
189 new (S) SCEVConstant(V);
190 UniqueSCEVs.InsertNode(S, IP);
191 return S;
192}
193
194const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
195 return getConstant(ConstantInt::get(Val));
196}
197
198const SCEV*
199ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
200 return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
201}
202
203void SCEVConstant::Profile(FoldingSetNodeID &ID) const {
204 ID.AddInteger(scConstant);
205 ID.AddPointer(V);
206}
207
208const Type *SCEVConstant::getType() const { return V->getType(); }
209
210void SCEVConstant::print(raw_ostream &OS) const {
211 WriteAsOperand(OS, V, false);
212}
213
214SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
215 const SCEV* op, const Type *ty)
216 : SCEV(SCEVTy), Op(op), Ty(ty) {}
217
218void SCEVCastExpr::Profile(FoldingSetNodeID &ID) const {
219 ID.AddInteger(getSCEVType());
220 ID.AddPointer(Op);
221 ID.AddPointer(Ty);
222}
223
224bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
225 return Op->dominates(BB, DT);
226}
227
228SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
229 : SCEVCastExpr(scTruncate, op, ty) {
230 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
231 (Ty->isInteger() || isa<PointerType>(Ty)) &&
--- 63 unchanged lines hidden (view full) ---
295 return SE.getUMaxExpr(NewOps);
296 else
297 assert(0 && "Unknown commutative expr!");
298 }
299 }
300 return this;
301}
302
303void SCEVNAryExpr::Profile(FoldingSetNodeID &ID) const {
304 ID.AddInteger(getSCEVType());
305 ID.AddInteger(Operands.size());
306 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
307 ID.AddPointer(Operands[i]);
308}
309
310bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
311 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
312 if (!getOperand(i)->dominates(BB, DT))
313 return false;
314 }
315 return true;
316}
317
318void SCEVUDivExpr::Profile(FoldingSetNodeID &ID) const {
319 ID.AddInteger(scUDivExpr);
320 ID.AddPointer(LHS);
321 ID.AddPointer(RHS);
322}
323
324bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
325 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
326}
327
328void SCEVUDivExpr::print(raw_ostream &OS) const {
329 OS << "(" << *LHS << " /u " << *RHS << ")";
330}
331
332const Type *SCEVUDivExpr::getType() const {
333 // In most cases the types of LHS and RHS will be the same, but in some
334 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
335 // depend on the type for correctness, but handling types carefully can
336 // avoid extra casts in the SCEVExpander. The LHS is more likely to be
337 // a pointer type than the RHS, so use the RHS' type here.
338 return RHS->getType();
339}
340
341void SCEVAddRecExpr::Profile(FoldingSetNodeID &ID) const {
342 ID.AddInteger(scAddRecExpr);
343 ID.AddInteger(Operands.size());
344 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
345 ID.AddPointer(Operands[i]);
346 ID.AddPointer(L);
347}
348
349const SCEV *
350SCEVAddRecExpr::replaceSymbolicValuesWithConcrete(const SCEV *Sym,
351 const SCEV *Conc,
352 ScalarEvolution &SE) const {
353 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
354 const SCEV* H =
355 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
356 if (H != getOperand(i)) {
--- 27 unchanged lines hidden (view full) ---
384 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
385 if (!getOperand(i)->isLoopInvariant(QueryLoop))
386 return false;
387
388 // Otherwise it's loop-invariant.
389 return true;
390}
391
392void SCEVAddRecExpr::print(raw_ostream &OS) const {
393 OS << "{" << *Operands[0];
394 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
395 OS << ",+," << *Operands[i];
396 OS << "}<" << L->getHeader()->getName() + ">";
397}
398
399void SCEVUnknown::Profile(FoldingSetNodeID &ID) const {
400 ID.AddInteger(scUnknown);
401 ID.AddPointer(V);
402}
403
404bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
405 // All non-instruction values are loop invariant. All instructions are loop
406 // invariant if they are not contained in the specified loop.
407 // Instructions are never considered invariant in the function body
408 // (null loop) because they are defined within the "loop".
409 if (Instruction *I = dyn_cast<Instruction>(V))
410 return L && !L->contains(I->getParent());
411 return true;
--- 327 unchanged lines hidden (view full) ---
739const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
740 const Type *Ty) {
741 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
742 "This is not a truncating conversion!");
743 assert(isSCEVable(Ty) &&
744 "This is not a conversion to a SCEVable type!");
745 Ty = getEffectiveSCEVType(Ty);
746
747 // Fold if the operand is constant.
748 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
749 return getConstant(
750 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
751
752 // trunc(trunc(x)) --> trunc(x)
753 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
754 return getTruncateExpr(ST->getOperand(), Ty);
755
--- 8 unchanged lines hidden (view full) ---
764 // If the input value is a chrec scev, truncate the chrec's operands.
765 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
766 SmallVector<const SCEV*, 4> Operands;
767 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
768 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
769 return getAddRecExpr(Operands, AddRec->getLoop());
770 }
771
772 FoldingSetNodeID ID;
773 ID.AddInteger(scTruncate);
774 ID.AddPointer(Op);
775 ID.AddPointer(Ty);
776 void *IP = 0;
777 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
778 SCEV *S = SCEVAllocator.Allocate<SCEVTruncateExpr>();
779 new (S) SCEVTruncateExpr(Op, Ty);
780 UniqueSCEVs.InsertNode(S, IP);
781 return S;
782}
783
784const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
785 const Type *Ty) {
786 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
787 "This is not an extending conversion!");
788 assert(isSCEVable(Ty) &&
789 "This is not a conversion to a SCEVable type!");
790 Ty = getEffectiveSCEVType(Ty);
791
792 // Fold if the operand is constant.
793 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
794 const Type *IntTy = getEffectiveSCEVType(Ty);
795 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
796 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
797 return getConstant(cast<ConstantInt>(C));
798 }
799
800 // zext(zext(x)) --> zext(x)
--- 59 unchanged lines hidden (view full) ---
860 // Return the expression with the addrec on the outside.
861 return getAddRecExpr(getZeroExtendExpr(Start, Ty),
862 getSignExtendExpr(Step, Ty),
863 AR->getLoop());
864 }
865 }
866 }
867
868 FoldingSetNodeID ID;
869 ID.AddInteger(scZeroExtend);
870 ID.AddPointer(Op);
871 ID.AddPointer(Ty);
872 void *IP = 0;
873 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
874 SCEV *S = SCEVAllocator.Allocate<SCEVZeroExtendExpr>();
875 new (S) SCEVZeroExtendExpr(Op, Ty);
876 UniqueSCEVs.InsertNode(S, IP);
877 return S;
878}
879
880const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
881 const Type *Ty) {
882 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
883 "This is not an extending conversion!");
884 assert(isSCEVable(Ty) &&
885 "This is not a conversion to a SCEVable type!");
886 Ty = getEffectiveSCEVType(Ty);
887
888 // Fold if the operand is constant.
889 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
890 const Type *IntTy = getEffectiveSCEVType(Ty);
891 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
892 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
893 return getConstant(cast<ConstantInt>(C));
894 }
895
896 // sext(sext(x)) --> sext(x)
--- 43 unchanged lines hidden (view full) ---
940 // Return the expression with the addrec on the outside.
941 return getAddRecExpr(getSignExtendExpr(Start, Ty),
942 getSignExtendExpr(Step, Ty),
943 AR->getLoop());
944 }
945 }
946 }
947
948 FoldingSetNodeID ID;
949 ID.AddInteger(scSignExtend);
950 ID.AddPointer(Op);
951 ID.AddPointer(Ty);
952 void *IP = 0;
953 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
954 SCEV *S = SCEVAllocator.Allocate<SCEVSignExtendExpr>();
955 new (S) SCEVSignExtendExpr(Op, Ty);
956 UniqueSCEVs.InsertNode(S, IP);
957 return S;
958}
959
960/// getAnyExtendExpr - Return a SCEV for the given operand extended with
961/// unspecified bits out to the given type.
962///
963const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* Op,
964 const Type *Ty) {
965 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
--- 81 unchanged lines hidden (view full) ---
1047 ->getOperands(),
1048 NewScale, SE);
1049 } else {
1050 // A multiplication of a constant with some other value. Update
1051 // the map.
1052 SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
1053 const SCEV* Key = SE.getMulExpr(MulOps);
1054 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
1055 M.insert(std::make_pair(Key, NewScale));
1056 if (Pair.second) {
1057 NewOps.push_back(Pair.first->first);
1058 } else {
1059 Pair.first->second += NewScale;
1060 // The map already had an entry for this value, which may indicate
1061 // a folding opportunity.
1062 Interesting = true;
1063 }
1064 }
1065 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
1066 // Pull a buried constant out to the outside.
1067 if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
1068 Interesting = true;
1069 AccumulatedConstant += Scale * C->getValue()->getValue();
1070 } else {
1071 // An ordinary operand. Update the map.
1072 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
1073 M.insert(std::make_pair(Ops[i], Scale));
1074 if (Pair.second) {
1075 NewOps.push_back(Pair.first->first);
1076 } else {
1077 Pair.first->second += Scale;
1078 // The map already had an entry for this value, which may indicate
1079 // a folding opportunity.
1080 Interesting = true;
1081 }
1082 }
--- 325 unchanged lines hidden (view full) ---
1408 }
1409
1410 // Otherwise couldn't fold anything into this recurrence. Move onto the
1411 // next one.
1412 }
1413
1414 // Okay, it looks like we really DO need an add expr. Check to see if we
1415 // already have one, otherwise create a new one.
1416 FoldingSetNodeID ID;
1417 ID.AddInteger(scAddExpr);
1418 ID.AddInteger(Ops.size());
1419 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1420 ID.AddPointer(Ops[i]);
1421 void *IP = 0;
1422 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1423 SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>();
1424 new (S) SCEVAddExpr(Ops);
1425 UniqueSCEVs.InsertNode(S, IP);
1426 return S;
1427}
1428
1429
1430/// getMulExpr - Get a canonical multiply expression, or something simpler if
1431/// possible.
1432const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
1433 assert(!Ops.empty() && "Cannot get empty mul!");
1434#ifndef NDEBUG
--- 144 unchanged lines hidden (view full) ---
1579 }
1580
1581 // Otherwise couldn't fold anything into this recurrence. Move onto the
1582 // next one.
1583 }
1584
1585 // Okay, it looks like we really DO need an mul expr. Check to see if we
1586 // already have one, otherwise create a new one.
1587 FoldingSetNodeID ID;
1588 ID.AddInteger(scMulExpr);
1589 ID.AddInteger(Ops.size());
1590 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1591 ID.AddPointer(Ops[i]);
1592 void *IP = 0;
1593 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1594 SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>();
1595 new (S) SCEVMulExpr(Ops);
1596 UniqueSCEVs.InsertNode(S, IP);
1597 return S;
1598}
1599
1600/// getUDivExpr - Get a canonical multiply expression, or something simpler if
1601/// possible.
1602const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
1603 const SCEV *RHS) {
1604 assert(getEffectiveSCEVType(LHS->getType()) ==
1605 getEffectiveSCEVType(RHS->getType()) &&
--- 73 unchanged lines hidden (view full) ---
1679 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1680 Constant *LHSCV = LHSC->getValue();
1681 Constant *RHSCV = RHSC->getValue();
1682 return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
1683 RHSCV)));
1684 }
1685 }
1686
1687 FoldingSetNodeID ID;
1688 ID.AddInteger(scUDivExpr);
1689 ID.AddPointer(LHS);
1690 ID.AddPointer(RHS);
1691 void *IP = 0;
1692 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1693 SCEV *S = SCEVAllocator.Allocate<SCEVUDivExpr>();
1694 new (S) SCEVUDivExpr(LHS, RHS);
1695 UniqueSCEVs.InsertNode(S, IP);
1696 return S;
1697}
1698
1699
1700/// getAddRecExpr - Get an add recurrence expression for the specified loop.
1701/// Simplify the expression as much as possible.
1702const SCEV* ScalarEvolution::getAddRecExpr(const SCEV* Start,
1703 const SCEV* Step, const Loop *L) {
1704 SmallVector<const SCEV*, 4> Operands;
--- 55 unchanged lines hidden (view full) ---
1760 // Ok, both add recurrences are valid after the transformation.
1761 return getAddRecExpr(NestedOperands, NestedLoop);
1762 }
1763 // Reset Operands to its original state.
1764 Operands[0] = NestedAR;
1765 }
1766 }
1767
1768 FoldingSetNodeID ID;
1769 ID.AddInteger(scAddRecExpr);
1770 ID.AddInteger(Operands.size());
1771 for (unsigned i = 0, e = Operands.size(); i != e; ++i)
1772 ID.AddPointer(Operands[i]);
1773 ID.AddPointer(L);
1774 void *IP = 0;
1775 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1776 SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>();
1777 new (S) SCEVAddRecExpr(Operands, L);
1778 UniqueSCEVs.InsertNode(S, IP);
1779 return S;
1780}
1781
1782const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
1783 const SCEV *RHS) {
1784 SmallVector<const SCEV*, 2> Ops;
1785 Ops.push_back(LHS);
1786 Ops.push_back(RHS);
1787 return getSMaxExpr(Ops);
--- 70 unchanged lines hidden (view full) ---
1858 }
1859
1860 if (Ops.size() == 1) return Ops[0];
1861
1862 assert(!Ops.empty() && "Reduced smax down to nothing!");
1863
1864 // Okay, it looks like we really DO need an smax expr. Check to see if we
1865 // already have one, otherwise create a new one.
1866 FoldingSetNodeID ID;
1867 ID.AddInteger(scSMaxExpr);
1868 ID.AddInteger(Ops.size());
1869 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1870 ID.AddPointer(Ops[i]);
1871 void *IP = 0;
1872 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1873 SCEV *S = SCEVAllocator.Allocate<SCEVSMaxExpr>();
1874 new (S) SCEVSMaxExpr(Ops);
1875 UniqueSCEVs.InsertNode(S, IP);
1876 return S;
1877}
1878
1879const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
1880 const SCEV *RHS) {
1881 SmallVector<const SCEV*, 2> Ops;
1882 Ops.push_back(LHS);
1883 Ops.push_back(RHS);
1884 return getUMaxExpr(Ops);
--- 70 unchanged lines hidden (view full) ---
1955 }
1956
1957 if (Ops.size() == 1) return Ops[0];
1958
1959 assert(!Ops.empty() && "Reduced umax down to nothing!");
1960
1961 // Okay, it looks like we really DO need a umax expr. Check to see if we
1962 // already have one, otherwise create a new one.
1963 FoldingSetNodeID ID;
1964 ID.AddInteger(scUMaxExpr);
1965 ID.AddInteger(Ops.size());
1966 for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1967 ID.AddPointer(Ops[i]);
1968 void *IP = 0;
1969 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1970 SCEV *S = SCEVAllocator.Allocate<SCEVUMaxExpr>();
1971 new (S) SCEVUMaxExpr(Ops);
1972 UniqueSCEVs.InsertNode(S, IP);
1973 return S;
1974}
1975
1976const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
1977 const SCEV *RHS) {
1978 // ~smax(~x, ~y) == smin(x, y).
1979 return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
1980}
1981
--- 4 unchanged lines hidden (view full) ---
1986}
1987
1988const SCEV* ScalarEvolution::getUnknown(Value *V) {
1989 // Don't attempt to do anything other than create a SCEVUnknown object
1990 // here. createSCEV only calls getUnknown after checking for all other
1991 // interesting possibilities, and any other code that calls getUnknown
1992 // is doing so in order to hide a value from SCEV canonicalization.
1993
1994 FoldingSetNodeID ID;
1995 ID.AddInteger(scUnknown);
1996 ID.AddPointer(V);
1997 void *IP = 0;
1998 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
1999 SCEV *S = SCEVAllocator.Allocate<SCEVUnknown>();
2000 new (S) SCEVUnknown(V);
2001 UniqueSCEVs.InsertNode(S, IP);
2002 return S;
2003}
2004
2005//===----------------------------------------------------------------------===//
2006// Basic SCEV Analysis and PHI Idiom Recognition Code
2007//
2008
2009/// isSCEVable - Test if values of the given type are analyzable within
2010/// the SCEV framework. This primarily includes integer types, and it
--- 37 unchanged lines hidden (view full) ---
2048 if (Ty->isInteger())
2049 return Ty;
2050
2051 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
2052 return TD->getIntPtrType();
2053}
2054
2055const SCEV* ScalarEvolution::getCouldNotCompute() {
2056 return &CouldNotCompute;
2057}
2058
2059/// hasSCEV - Return true if the SCEV for this value has already been
2060/// computed.
2061bool ScalarEvolution::hasSCEV(Value *V) const {
2062 return Scalars.count(V);
2063}
2064
--- 794 unchanged lines hidden (view full) ---
2859 // succeeds, procede to actually compute a backedge-taken count and
2860 // update the value. The temporary CouldNotCompute value tells SCEV
2861 // code elsewhere that it shouldn't attempt to request a new
2862 // backedge-taken count, which could result in infinite recursion.
2863 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2864 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2865 if (Pair.second) {
2866 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
2867 if (ItCount.Exact != getCouldNotCompute()) {
2868 assert(ItCount.Exact->isLoopInvariant(L) &&
2869 ItCount.Max->isLoopInvariant(L) &&
2870 "Computed trip count isn't loop invariant for loop!");
2871 ++NumTripCountsComputed;
2872
2873 // Update the value in the map.
2874 Pair.first->second = ItCount;
2875 } else {
2876 if (ItCount.Max != getCouldNotCompute())
2877 // Update the value in the map.
2878 Pair.first->second = ItCount;
2879 if (isa<PHINode>(L->getHeader()->begin()))
2880 // Only count loops that have phi nodes as not being computable.
2881 ++NumTripCountsNotComputed;
2882 }
2883
2884 // Now that we know more about the trip count for this loop, forget any
--- 49 unchanged lines hidden (view full) ---
2934/// ComputeBackedgeTakenCount - Compute the number of times the backedge
2935/// of the specified loop will execute.
2936ScalarEvolution::BackedgeTakenInfo
2937ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2938 SmallVector<BasicBlock*, 8> ExitingBlocks;
2939 L->getExitingBlocks(ExitingBlocks);
2940
2941 // Examine all exits and pick the most conservative values.
2942 const SCEV* BECount = getCouldNotCompute();
2943 const SCEV* MaxBECount = getCouldNotCompute();
2944 bool CouldNotComputeBECount = false;
2945 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2946 BackedgeTakenInfo NewBTI =
2947 ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
2948
2949 if (NewBTI.Exact == getCouldNotCompute()) {
2950 // We couldn't compute an exact value for this exit, so
2951 // we won't be able to compute an exact value for the loop.
2952 CouldNotComputeBECount = true;
2953 BECount = getCouldNotCompute();
2954 } else if (!CouldNotComputeBECount) {
2955 if (BECount == getCouldNotCompute())
2956 BECount = NewBTI.Exact;
2957 else
2958 BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
2959 }
2960 if (MaxBECount == getCouldNotCompute())
2961 MaxBECount = NewBTI.Max;
2962 else if (NewBTI.Max != getCouldNotCompute())
2963 MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
2964 }
2965
2966 return BackedgeTakenInfo(BECount, MaxBECount);
2967}
2968
2969/// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
2970/// of the specified loop will execute if it exits via the specified block.
2971ScalarEvolution::BackedgeTakenInfo
2972ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
2973 BasicBlock *ExitingBlock) {
2974
2975 // Okay, we've chosen an exiting block. See what condition causes us to
2976 // exit at this block.
2977 //
2978 // FIXME: we should be able to handle switch instructions (with a single exit)
2979 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2980 if (ExitBr == 0) return getCouldNotCompute();
2981 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2982
2983 // At this point, we know we have a conditional branch that determines whether
2984 // the loop is exited. However, we don't know if the branch is executed each
2985 // time through the loop. If not, then the execution count of the branch will
2986 // not be equal to the trip count of the loop.
2987 //
2988 // Currently we check for this by checking to see if the Exit branch goes to
--- 12 unchanged lines hidden (view full) ---
3001 ExitBr->getSuccessor(1) != L->getHeader() &&
3002 ExitBr->getParent() != L->getHeader()) {
3003 // The simple checks failed, try climbing the unique predecessor chain
3004 // up to the header.
3005 bool Ok = false;
3006 for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
3007 BasicBlock *Pred = BB->getUniquePredecessor();
3008 if (!Pred)
3009 return getCouldNotCompute();
3010 TerminatorInst *PredTerm = Pred->getTerminator();
3011 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
3012 BasicBlock *PredSucc = PredTerm->getSuccessor(i);
3013 if (PredSucc == BB)
3014 continue;
3015 // If the predecessor has a successor that isn't BB and isn't
3016 // outside the loop, assume the worst.
3017 if (L->contains(PredSucc))
3018 return getCouldNotCompute();
3019 }
3020 if (Pred == L->getHeader()) {
3021 Ok = true;
3022 break;
3023 }
3024 BB = Pred;
3025 }
3026 if (!Ok)
3027 return getCouldNotCompute();
3028 }
3029
3030 // Procede to the next level to examine the exit condition expression.
3031 return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
3032 ExitBr->getSuccessor(0),
3033 ExitBr->getSuccessor(1));
3034}
3035
--- 8 unchanged lines hidden (view full) ---
3044 // Check if the controlling expression for this loop is an And or Or.
3045 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
3046 if (BO->getOpcode() == Instruction::And) {
3047 // Recurse on the operands of the and.
3048 BackedgeTakenInfo BTI0 =
3049 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3050 BackedgeTakenInfo BTI1 =
3051 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3052 const SCEV* BECount = getCouldNotCompute();
3053 const SCEV* MaxBECount = getCouldNotCompute();
3054 if (L->contains(TBB)) {
3055 // Both conditions must be true for the loop to continue executing.
3056 // Choose the less conservative count.
3057 if (BTI0.Exact == getCouldNotCompute() ||
3058 BTI1.Exact == getCouldNotCompute())
3059 BECount = getCouldNotCompute();
3060 else
3061 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3062 if (BTI0.Max == getCouldNotCompute())
3063 MaxBECount = BTI1.Max;
3064 else if (BTI1.Max == getCouldNotCompute())
3065 MaxBECount = BTI0.Max;
3066 else
3067 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3068 } else {
3069 // Both conditions must be true for the loop to exit.
3070 assert(L->contains(FBB) && "Loop block has no successor in loop!");
3071 if (BTI0.Exact != getCouldNotCompute() &&
3072 BTI1.Exact != getCouldNotCompute())
3073 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3074 if (BTI0.Max != getCouldNotCompute() &&
3075 BTI1.Max != getCouldNotCompute())
3076 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3077 }
3078
3079 return BackedgeTakenInfo(BECount, MaxBECount);
3080 }
3081 if (BO->getOpcode() == Instruction::Or) {
3082 // Recurse on the operands of the or.
3083 BackedgeTakenInfo BTI0 =
3084 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
3085 BackedgeTakenInfo BTI1 =
3086 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
3087 const SCEV* BECount = getCouldNotCompute();
3088 const SCEV* MaxBECount = getCouldNotCompute();
3089 if (L->contains(FBB)) {
3090 // Both conditions must be false for the loop to continue executing.
3091 // Choose the less conservative count.
3092 if (BTI0.Exact == getCouldNotCompute() ||
3093 BTI1.Exact == getCouldNotCompute())
3094 BECount = getCouldNotCompute();
3095 else
3096 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3097 if (BTI0.Max == getCouldNotCompute())
3098 MaxBECount = BTI1.Max;
3099 else if (BTI1.Max == getCouldNotCompute())
3100 MaxBECount = BTI0.Max;
3101 else
3102 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
3103 } else {
3104 // Both conditions must be false for the loop to exit.
3105 assert(L->contains(TBB) && "Loop block has no successor in loop!");
3106 if (BTI0.Exact != getCouldNotCompute() &&
3107 BTI1.Exact != getCouldNotCompute())
3108 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3109 if (BTI0.Max != getCouldNotCompute() &&
3110 BTI1.Max != getCouldNotCompute())
3111 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
3112 }
3113
3114 return BackedgeTakenInfo(BECount, MaxBECount);
3115 }
3116 }
3117
3118 // With an icmp, it may be feasible to compute an exact backedge-taken count.
--- 160 unchanged lines hidden (view full) ---
3279/// 'icmp op load X, cst', try to see if we can compute the backedge
3280/// execution count.
3281const SCEV *
3282ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
3283 LoadInst *LI,
3284 Constant *RHS,
3285 const Loop *L,
3286 ICmpInst::Predicate predicate) {
3287 if (LI->isVolatile()) return getCouldNotCompute();
3288
3289 // Check to see if the loaded pointer is a getelementptr of a global.
3290 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3291 if (!GEP) return getCouldNotCompute();
3292
3293 // Make sure that it is really a constant global we are gepping, with an
3294 // initializer, and make sure the first IDX is really 0.
3295 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
3296 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
3297 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
3298 !cast<Constant>(GEP->getOperand(1))->isNullValue())
3299 return getCouldNotCompute();
3300
3301 // Okay, we allow one non-constant index into the GEP instruction.
3302 Value *VarIdx = 0;
3303 std::vector<ConstantInt*> Indexes;
3304 unsigned VarIdxNum = 0;
3305 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
3306 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
3307 Indexes.push_back(CI);
3308 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
3309 if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's.
3310 VarIdx = GEP->getOperand(i);
3311 VarIdxNum = i-2;
3312 Indexes.push_back(0);
3313 }
3314
3315 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
3316 // Check to see if X is a loop variant variable value now.
3317 const SCEV* Idx = getSCEV(VarIdx);
3318 Idx = getSCEVAtScope(Idx, L);
3319
3320 // We can only recognize very limited forms of loop index expressions, in
3321 // particular, only affine AddRec's like {C1,+,C2}.
3322 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
3323 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
3324 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
3325 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
3326 return getCouldNotCompute();
3327
3328 unsigned MaxSteps = MaxBruteForceIterations;
3329 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
3330 ConstantInt *ItCst =
3331 ConstantInt::get(cast<IntegerType>(IdxExpr->getType()), IterationNum);
3332 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
3333
3334 // Form the GEP offset.
--- 10 unchanged lines hidden (view full) ---
3345 errs() << "\n***\n*** Computed loop count " << *ItCst
3346 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
3347 << "***\n";
3348#endif
3349 ++NumArrayLenItCounts;
3350 return getConstant(ItCst); // Found terminating iteration!
3351 }
3352 }
3353 return getCouldNotCompute();
3354}
3355
3356
3357/// CanConstantFold - Return true if we can constant fold an instruction of the
3358/// specified type, assuming that all operands were constants.
3359static bool CanConstantFold(const Instruction *I) {
3360 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
3361 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))
--- 124 unchanged lines hidden (view full) ---
3486 PHIVal = NextPHI;
3487 }
3488}
3489
3490/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
3491/// constant number of times (the condition evolves only from constants),
3492/// try to evaluate a few iterations of the loop until we get the exit
3493/// condition gets a value of ExitWhen (true or false). If we cannot
3494/// evaluate the trip count of the loop, return getCouldNotCompute().
3495const SCEV *
3496ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
3497 Value *Cond,
3498 bool ExitWhen) {
3499 PHINode *PN = getConstantEvolvingPHI(Cond, L);
3500 if (PN == 0) return getCouldNotCompute();
3501
3502 // Since the loop is canonicalized, the PHI node must have two entries. One
3503 // entry must be a constant (coming in from outside of the loop), and the
3504 // second must be derived from the same PHI.
3505 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
3506 Constant *StartCST =
3507 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
3508 if (StartCST == 0) return getCouldNotCompute(); // Must be a constant.
3509
3510 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3511 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3512 if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI.
3513
3514 // Okay, we find a PHI node that defines the trip count of this loop. Execute
3515 // the loop symbolically to determine when the condition gets a value of
3516 // "ExitWhen".
3517 unsigned IterationNum = 0;
3518 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
3519 for (Constant *PHIVal = StartCST;
3520 IterationNum != MaxIterations; ++IterationNum) {
3521 ConstantInt *CondVal =
3522 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
3523
3524 // Couldn't symbolically evaluate.
3525 if (!CondVal) return getCouldNotCompute();
3526
3527 if (CondVal->getValue() == uint64_t(ExitWhen)) {
3528 ++NumBruteForceTripCountsComputed;
3529 return getConstant(Type::Int32Ty, IterationNum);
3530 }
3531
3532 // Compute the value of the PHI node for the next iteration.
3533 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
3534 if (NextPHI == 0 || NextPHI == PHIVal)
3535 return getCouldNotCompute();// Couldn't evaluate or not making progress...
3536 PHIVal = NextPHI;
3537 }
3538
3539 // Too many iterations were needed to evaluate.
3540 return getCouldNotCompute();
3541}
3542
3543/// getSCEVAtScope - Return a SCEV expression handle for the specified value
3544/// at the specified scope in the program. The L value specifies a loop
3545/// nest to evaluate the expression at, where null is the top-level or a
3546/// specified loop is immediately inside of the loop.
3547///
3548/// This method can be used to compute the exit value for a variable defined
--- 22 unchanged lines hidden (view full) ---
3571 if (const SCEVConstant *BTCC =
3572 dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
3573 // Okay, we know how many times the containing loop executes. If
3574 // this is a constant evolving PHI node, get the final value at
3575 // the specified iteration number.
3576 Constant *RV = getConstantEvolutionLoopExitValue(PN,
3577 BTCC->getValue()->getValue(),
3578 LI);
3579 if (RV) return getSCEV(RV);
3580 }
3581 }
3582
3583 // Okay, this is an expression that we cannot symbolically evaluate
3584 // into a SCEV. Check to see if it's possible to symbolically evaluate
3585 // the arguments into constants, and if so, try to constant propagate the
3586 // result. This is particularly useful for computing loop exit values.
3587 if (CanConstantFold(I)) {
3588 // Check to see if we've folded this instruction at this loop before.
3589 std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
3590 std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
3591 Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
3592 if (!Pair.second)
3593 return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
3594
3595 std::vector<Constant*> Operands;
3596 Operands.reserve(I->getNumOperands());
3597 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3598 Value *Op = I->getOperand(i);
3599 if (Constant *C = dyn_cast<Constant>(Op)) {
3600 Operands.push_back(C);
3601 } else {
--- 32 unchanged lines hidden (view full) ---
3634 Constant *C;
3635 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
3636 C = ConstantFoldCompareInstOperands(CI->getPredicate(),
3637 &Operands[0], Operands.size());
3638 else
3639 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
3640 &Operands[0], Operands.size());
3641 Pair.first->second = C;
3642 return getSCEV(C);
3643 }
3644 }
3645
3646 // This is some other type of SCEVUnknown, just return it.
3647 return V;
3648 }
3649
3650 if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {
--- 37 unchanged lines hidden (view full) ---
3688
3689 // If this is a loop recurrence for a loop that does not contain L, then we
3690 // are dealing with the final value computed by the loop.
3691 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3692 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3693 // To evaluate this recurrence, we need to know how many times the AddRec
3694 // loop iterates. Compute this now.
3695 const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
3696 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
3697
3698 // Then, evaluate the AddRec.
3699 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3700 }
3701 return AddRec;
3702 }
3703
3704 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {
--- 138 unchanged lines hidden (view full) ---
3843
3844/// HowFarToZero - Return the number of times a backedge comparing the specified
3845/// value to zero will execute. If not computable, return CouldNotCompute.
3846const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3847 // If the value is a constant
3848 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3849 // If the value is already zero, the branch will execute zero times.
3850 if (C->getValue()->isZero()) return C;
3851 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3852 }
3853
3854 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3855 if (!AddRec || AddRec->getLoop() != L)
3856 return getCouldNotCompute();
3857
3858 if (AddRec->isAffine()) {
3859 // If this is an affine expression, the execution count of this branch is
3860 // the minimum unsigned root of the following equation:
3861 //
3862 // Start + Step*N = 0 (mod 2^BW)
3863 //
3864 // equivalent to:
--- 47 unchanged lines hidden (view full) ---
3912 // should not accept a root of 2.
3913 const SCEV* Val = AddRec->evaluateAtIteration(R1, *this);
3914 if (Val->isZero())
3915 return R1; // We found a quadratic root!
3916 }
3917 }
3918 }
3919
3920 return getCouldNotCompute();
3921}
3922
3923/// HowFarToNonZero - Return the number of times a backedge checking the
3924/// specified value for nonzero will execute. If not computable, return
3925/// CouldNotCompute
3926const SCEV* ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3927 // Loops that look like: while (X == 0) are very strange indeed. We don't
3928 // handle them yet except for the trivial case. This could be expanded in the
3929 // future as needed.
3930
3931 // If the value is a constant, check to see if it is known to be non-zero
3932 // already. If so, the backedge will execute zero times.
3933 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3934 if (!C->getValue()->isNullValue())
3935 return getIntegerSCEV(0, C->getType());
3936 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3937 }
3938
3939 // We could implement others, but I really doubt anyone writes loops like
3940 // this, and if they did, they would already be constant folded.
3941 return getCouldNotCompute();
3942}
3943
3944/// getLoopPredecessor - If the given loop's header has exactly one unique
3945/// predecessor outside the loop, return it. Otherwise return null.
3946///
3947BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3948 BasicBlock *Header = L->getHeader();
3949 BasicBlock *Pred = 0;
--- 201 unchanged lines hidden (view full) ---
4151
4152 // Check Add for unsigned overflow.
4153 // TODO: More sophisticated things could be done here.
4154 const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
4155 const SCEV* OperandExtendedAdd =
4156 getAddExpr(getZeroExtendExpr(Diff, WideTy),
4157 getZeroExtendExpr(RoundUp, WideTy));
4158 if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
4159 return getCouldNotCompute();
4160
4161 return getUDivExpr(Add, Step);
4162}
4163
4164/// HowManyLessThans - Return the number of times a backedge containing the
4165/// specified less-than comparison will execute. If not computable, return
4166/// CouldNotCompute.
4167ScalarEvolution::BackedgeTakenInfo
4168ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
4169 const Loop *L, bool isSigned) {
4170 // Only handle: "ADDREC < LoopInvariant".
4171 if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
4172
4173 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
4174 if (!AddRec || AddRec->getLoop() != L)
4175 return getCouldNotCompute();
4176
4177 if (AddRec->isAffine()) {
4178 // FORNOW: We only support unit strides.
4179 unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
4180 const SCEV* Step = AddRec->getStepRecurrence(*this);
4181
4182 // TODO: handle non-constant strides.
4183 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
4184 if (!CStep || CStep->isZero())
4185 return getCouldNotCompute();
4186 if (CStep->isOne()) {
4187 // With unit stride, the iteration never steps past the limit value.
4188 } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
4189 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
4190 // Test whether a positive iteration iteration can step past the limit
4191 // value and past the maximum value for its type in a single step.
4192 if (isSigned) {
4193 APInt Max = APInt::getSignedMaxValue(BitWidth);
4194 if ((Max - CStep->getValue()->getValue())
4195 .slt(CLimit->getValue()->getValue()))
4196 return getCouldNotCompute();
4197 } else {
4198 APInt Max = APInt::getMaxValue(BitWidth);
4199 if ((Max - CStep->getValue()->getValue())
4200 .ult(CLimit->getValue()->getValue()))
4201 return getCouldNotCompute();
4202 }
4203 } else
4204 // TODO: handle non-constant limit values below.
4205 return getCouldNotCompute();
4206 } else
4207 // TODO: handle negative strides below.
4208 return getCouldNotCompute();
4209
4210 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
4211 // m. So, we count the number of iterations in which {n,+,s} < m is true.
4212 // Note that we cannot simply return max(m-n,0)/s because it's not safe to
4213 // treat m-n as signed nor unsigned due to overflow possibility.
4214
4215 // First, we get the value of the LHS in the first iteration: n
4216 const SCEV* Start = AddRec->getOperand(0);
--- 23 unchanged lines hidden (view full) ---
4240 .lshr(GetMinLeadingZeros(End)));
4241
4242 // Finally, we subtract these two values and divide, rounding up, to get
4243 // the number of times the backedge is executed.
4244 const SCEV* BECount = getBECount(Start, End, Step);
4245
4246 // The maximum backedge count is similar, except using the minimum start
4247 // value and the maximum end value.
4248 const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);
4249
4250 return BackedgeTakenInfo(BECount, MaxBECount);
4251 }
4252
4253 return getCouldNotCompute();
4254}
4255
4256/// getNumIterationsInRange - Return the number of iterations of this loop that
4257/// produce values in the specified constant range. Another way of looking at
4258/// this is that it returns the first iteration number where the value is not in
4259/// the condition, thus computing the exit count. If the iteration count can't
4260/// be computed, an instance of SCEVCouldNotCompute is returned.
4261const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,
--- 171 unchanged lines hidden (view full) ---
4433ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
4434 : CallbackVH(V), SE(se) {}
4435
4436//===----------------------------------------------------------------------===//
4437// ScalarEvolution Class Implementation
4438//===----------------------------------------------------------------------===//
4439
4440ScalarEvolution::ScalarEvolution()
4441 : FunctionPass(&ID) {
4442}
4443
4444bool ScalarEvolution::runOnFunction(Function &F) {
4445 this->F = &F;
4446 LI = &getAnalysis<LoopInfo>();
4447 TD = getAnalysisIfAvailable<TargetData>();
4448 return false;
4449}
4450
4451void ScalarEvolution::releaseMemory() {
4452 Scalars.clear();
4453 BackedgeTakenCounts.clear();
4454 ConstantEvolutionLoopExitValue.clear();
4455 ValuesAtScopes.clear();
4456 UniqueSCEVs.clear();
4457 SCEVAllocator.Reset();
4458}
4459
4460void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
4461 AU.setPreservesAll();
4462 AU.addRequiredTransitive<LoopInfo>();
4463}
4464
4465bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
--- 81 unchanged lines hidden ---