Deleted Added
sdiff udiff text old ( 195098 ) new ( 195340 )
full compact
ScalarEvolution.cpp (195098) ScalarEvolution.cpp (195340)
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//
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
113SCEV::~SCEV() {}
114SCEV::~SCEV() {}
115
114void SCEV::dump() const {
115 print(errs());
116 errs() << '\n';
117}
118
119void SCEV::print(std::ostream &o) const {
120 raw_os_ostream OS(o);
121 print(OS);

--- 15 unchanged lines hidden (view full) ---

137 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
138 return SC->getValue()->isAllOnesValue();
139 return false;
140}
141
142SCEVCouldNotCompute::SCEVCouldNotCompute() :
143 SCEV(scCouldNotCompute) {}
144
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
145bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const {
146 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
147 return false;
148}
149
150const Type *SCEVCouldNotCompute::getType() const {
151 assert(0 && "Attempt to use a SCEVCouldNotCompute object!");
152 return 0;

--- 16 unchanged lines hidden (view full) ---

169 OS << "***COULDNOTCOMPUTE***";
170}
171
172bool SCEVCouldNotCompute::classof(const SCEV *S) {
173 return S->getSCEVType() == scCouldNotCompute;
174}
175
176const SCEV* ScalarEvolution::getConstant(ConstantInt *V) {
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) {
177 SCEVConstant *&R = SCEVConstants[V];
178 if (R == 0) R = new SCEVConstant(V);
179 return R;
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;
180}
181
182const SCEV* ScalarEvolution::getConstant(const APInt& Val) {
183 return getConstant(ConstantInt::get(Val));
184}
185
186const SCEV*
187ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) {
188 return getConstant(ConstantInt::get(cast<IntegerType>(Ty), V, isSigned));
189}
190
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
191const Type *SCEVConstant::getType() const { return V->getType(); }
192
193void SCEVConstant::print(raw_ostream &OS) const {
194 WriteAsOperand(OS, V, false);
195}
196
197SCEVCastExpr::SCEVCastExpr(unsigned SCEVTy,
198 const SCEV* op, const Type *ty)
199 : SCEV(SCEVTy), Op(op), Ty(ty) {}
200
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
201bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
202 return Op->dominates(BB, DT);
203}
204
205SCEVTruncateExpr::SCEVTruncateExpr(const SCEV* op, const Type *ty)
206 : SCEVCastExpr(scTruncate, op, ty) {
207 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) &&
208 (Ty->isInteger() || isa<PointerType>(Ty)) &&

--- 63 unchanged lines hidden (view full) ---

272 return SE.getUMaxExpr(NewOps);
273 else
274 assert(0 && "Unknown commutative expr!");
275 }
276 }
277 return this;
278}
279
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
280bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
281 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
282 if (!getOperand(i)->dominates(BB, DT))
283 return false;
284 }
285 return true;
286}
287
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
288bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const {
289 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT);
290}
291
292void SCEVUDivExpr::print(raw_ostream &OS) const {
293 OS << "(" << *LHS << " /u " << *RHS << ")";
294}
295
296const Type *SCEVUDivExpr::getType() const {
297 // In most cases the types of LHS and RHS will be the same, but in some
298 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
299 // depend on the type for correctness, but handling types carefully can
300 // avoid extra casts in the SCEVExpander. The LHS is more likely to be
301 // a pointer type than the RHS, so use the RHS' type here.
302 return RHS->getType();
303}
304
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
305const SCEV *
306SCEVAddRecExpr::replaceSymbolicValuesWithConcrete(const SCEV *Sym,
307 const SCEV *Conc,
308 ScalarEvolution &SE) const {
309 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
310 const SCEV* H =
311 getOperand(i)->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
312 if (H != getOperand(i)) {

--- 27 unchanged lines hidden (view full) ---

340 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
341 if (!getOperand(i)->isLoopInvariant(QueryLoop))
342 return false;
343
344 // Otherwise it's loop-invariant.
345 return true;
346}
347
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
348
349void SCEVAddRecExpr::print(raw_ostream &OS) const {
350 OS << "{" << *Operands[0];
351 for (unsigned i = 1, e = Operands.size(); i != e; ++i)
352 OS << ",+," << *Operands[i];
353 OS << "}<" << L->getHeader()->getName() + ">";
354}
355
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
356bool SCEVUnknown::isLoopInvariant(const Loop *L) const {
357 // All non-instruction values are loop invariant. All instructions are loop
358 // invariant if they are not contained in the specified loop.
359 // Instructions are never considered invariant in the function body
360 // (null loop) because they are defined within the "loop".
361 if (Instruction *I = dyn_cast<Instruction>(V))
362 return L && !L->contains(I->getParent());
363 return true;

--- 327 unchanged lines hidden (view full) ---

691const SCEV* ScalarEvolution::getTruncateExpr(const SCEV* Op,
692 const Type *Ty) {
693 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) &&
694 "This is not a truncating conversion!");
695 assert(isSCEVable(Ty) &&
696 "This is not a conversion to a SCEVable type!");
697 Ty = getEffectiveSCEVType(Ty);
698
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.
699 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
700 return getConstant(
701 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty)));
702
703 // trunc(trunc(x)) --> trunc(x)
704 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op))
705 return getTruncateExpr(ST->getOperand(), Ty);
706

--- 8 unchanged lines hidden (view full) ---

715 // If the input value is a chrec scev, truncate the chrec's operands.
716 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
717 SmallVector<const SCEV*, 4> Operands;
718 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
719 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty));
720 return getAddRecExpr(Operands, AddRec->getLoop());
721 }
722
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
723 SCEVTruncateExpr *&Result = SCEVTruncates[std::make_pair(Op, Ty)];
724 if (Result == 0) Result = new SCEVTruncateExpr(Op, Ty);
725 return Result;
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;
726}
727
728const SCEV* ScalarEvolution::getZeroExtendExpr(const SCEV* Op,
729 const Type *Ty) {
730 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
731 "This is not an extending conversion!");
732 assert(isSCEVable(Ty) &&
733 "This is not a conversion to a SCEVable type!");
734 Ty = getEffectiveSCEVType(Ty);
735
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.
736 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
737 const Type *IntTy = getEffectiveSCEVType(Ty);
738 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy);
739 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
740 return getConstant(cast<ConstantInt>(C));
741 }
742
743 // zext(zext(x)) --> zext(x)

--- 59 unchanged lines hidden (view full) ---

803 // Return the expression with the addrec on the outside.
804 return getAddRecExpr(getZeroExtendExpr(Start, Ty),
805 getSignExtendExpr(Step, Ty),
806 AR->getLoop());
807 }
808 }
809 }
810
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
811 SCEVZeroExtendExpr *&Result = SCEVZeroExtends[std::make_pair(Op, Ty)];
812 if (Result == 0) Result = new SCEVZeroExtendExpr(Op, Ty);
813 return Result;
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;
814}
815
816const SCEV* ScalarEvolution::getSignExtendExpr(const SCEV* Op,
817 const Type *Ty) {
818 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
819 "This is not an extending conversion!");
820 assert(isSCEVable(Ty) &&
821 "This is not a conversion to a SCEVable type!");
822 Ty = getEffectiveSCEVType(Ty);
823
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.
824 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) {
825 const Type *IntTy = getEffectiveSCEVType(Ty);
826 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy);
827 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty);
828 return getConstant(cast<ConstantInt>(C));
829 }
830
831 // sext(sext(x)) --> sext(x)

--- 43 unchanged lines hidden (view full) ---

875 // Return the expression with the addrec on the outside.
876 return getAddRecExpr(getSignExtendExpr(Start, Ty),
877 getSignExtendExpr(Step, Ty),
878 AR->getLoop());
879 }
880 }
881 }
882
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
883 SCEVSignExtendExpr *&Result = SCEVSignExtends[std::make_pair(Op, Ty)];
884 if (Result == 0) Result = new SCEVSignExtendExpr(Op, Ty);
885 return Result;
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;
886}
887
888/// getAnyExtendExpr - Return a SCEV for the given operand extended with
889/// unspecified bits out to the given type.
890///
891const SCEV* ScalarEvolution::getAnyExtendExpr(const SCEV* Op,
892 const Type *Ty) {
893 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&

--- 81 unchanged lines hidden (view full) ---

975 ->getOperands(),
976 NewScale, SE);
977 } else {
978 // A multiplication of a constant with some other value. Update
979 // the map.
980 SmallVector<const SCEV*, 4> MulOps(Mul->op_begin()+1, Mul->op_end());
981 const SCEV* Key = SE.getMulExpr(MulOps);
982 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
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 =
983 M.insert(std::make_pair(Key, APInt()));
1055 M.insert(std::make_pair(Key, NewScale));
984 if (Pair.second) {
1056 if (Pair.second) {
985 Pair.first->second = NewScale;
986 NewOps.push_back(Pair.first->first);
987 } else {
988 Pair.first->second += NewScale;
989 // The map already had an entry for this value, which may indicate
990 // a folding opportunity.
991 Interesting = true;
992 }
993 }
994 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) {
995 // Pull a buried constant out to the outside.
996 if (Scale != 1 || AccumulatedConstant != 0 || C->isZero())
997 Interesting = true;
998 AccumulatedConstant += Scale * C->getValue()->getValue();
999 } else {
1000 // An ordinary operand. Update the map.
1001 std::pair<DenseMap<const SCEV*, APInt>::iterator, bool> Pair =
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 =
1002 M.insert(std::make_pair(Ops[i], APInt()));
1073 M.insert(std::make_pair(Ops[i], Scale));
1003 if (Pair.second) {
1074 if (Pair.second) {
1004 Pair.first->second = Scale;
1005 NewOps.push_back(Pair.first->first);
1006 } else {
1007 Pair.first->second += Scale;
1008 // The map already had an entry for this value, which may indicate
1009 // a folding opportunity.
1010 Interesting = true;
1011 }
1012 }

--- 325 unchanged lines hidden (view full) ---

1338 }
1339
1340 // Otherwise couldn't fold anything into this recurrence. Move onto the
1341 // next one.
1342 }
1343
1344 // Okay, it looks like we really DO need an add expr. Check to see if we
1345 // already have one, otherwise create a new one.
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.
1346 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1347 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scAddExpr,
1348 SCEVOps)];
1349 if (Result == 0) Result = new SCEVAddExpr(Ops);
1350 return Result;
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;
1351}
1352
1353
1354/// getMulExpr - Get a canonical multiply expression, or something simpler if
1355/// possible.
1356const SCEV* ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV*> &Ops) {
1357 assert(!Ops.empty() && "Cannot get empty mul!");
1358#ifndef NDEBUG

--- 144 unchanged lines hidden (view full) ---

1503 }
1504
1505 // Otherwise couldn't fold anything into this recurrence. Move onto the
1506 // next one.
1507 }
1508
1509 // Okay, it looks like we really DO need an mul expr. Check to see if we
1510 // already have one, otherwise create a new one.
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.
1511 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1512 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scMulExpr,
1513 SCEVOps)];
1514 if (Result == 0)
1515 Result = new SCEVMulExpr(Ops);
1516 return Result;
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;
1517}
1518
1519/// getUDivExpr - Get a canonical multiply expression, or something simpler if
1520/// possible.
1521const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
1522 const SCEV *RHS) {
1523 assert(getEffectiveSCEVType(LHS->getType()) ==
1524 getEffectiveSCEVType(RHS->getType()) &&

--- 73 unchanged lines hidden (view full) ---

1598 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
1599 Constant *LHSCV = LHSC->getValue();
1600 Constant *RHSCV = RHSC->getValue();
1601 return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV,
1602 RHSCV)));
1603 }
1604 }
1605
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
1606 SCEVUDivExpr *&Result = SCEVUDivs[std::make_pair(LHS, RHS)];
1607 if (Result == 0) Result = new SCEVUDivExpr(LHS, RHS);
1608 return Result;
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;
1609}
1610
1611
1612/// getAddRecExpr - Get an add recurrence expression for the specified loop.
1613/// Simplify the expression as much as possible.
1614const SCEV* ScalarEvolution::getAddRecExpr(const SCEV* Start,
1615 const SCEV* Step, const Loop *L) {
1616 SmallVector<const SCEV*, 4> Operands;

--- 55 unchanged lines hidden (view full) ---

1672 // Ok, both add recurrences are valid after the transformation.
1673 return getAddRecExpr(NestedOperands, NestedLoop);
1674 }
1675 // Reset Operands to its original state.
1676 Operands[0] = NestedAR;
1677 }
1678 }
1679
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
1680 std::vector<const SCEV*> SCEVOps(Operands.begin(), Operands.end());
1681 SCEVAddRecExpr *&Result = SCEVAddRecExprs[std::make_pair(L, SCEVOps)];
1682 if (Result == 0) Result = new SCEVAddRecExpr(Operands, L);
1683 return Result;
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;
1684}
1685
1686const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS,
1687 const SCEV *RHS) {
1688 SmallVector<const SCEV*, 2> Ops;
1689 Ops.push_back(LHS);
1690 Ops.push_back(RHS);
1691 return getSMaxExpr(Ops);

--- 70 unchanged lines hidden (view full) ---

1762 }
1763
1764 if (Ops.size() == 1) return Ops[0];
1765
1766 assert(!Ops.empty() && "Reduced smax down to nothing!");
1767
1768 // Okay, it looks like we really DO need an smax expr. Check to see if we
1769 // already have one, otherwise create a new one.
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.
1770 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1771 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scSMaxExpr,
1772 SCEVOps)];
1773 if (Result == 0) Result = new SCEVSMaxExpr(Ops);
1774 return Result;
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;
1775}
1776
1777const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS,
1778 const SCEV *RHS) {
1779 SmallVector<const SCEV*, 2> Ops;
1780 Ops.push_back(LHS);
1781 Ops.push_back(RHS);
1782 return getUMaxExpr(Ops);

--- 70 unchanged lines hidden (view full) ---

1853 }
1854
1855 if (Ops.size() == 1) return Ops[0];
1856
1857 assert(!Ops.empty() && "Reduced umax down to nothing!");
1858
1859 // Okay, it looks like we really DO need a umax expr. Check to see if we
1860 // already have one, otherwise create a new one.
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.
1861 std::vector<const SCEV*> SCEVOps(Ops.begin(), Ops.end());
1862 SCEVCommutativeExpr *&Result = SCEVCommExprs[std::make_pair(scUMaxExpr,
1863 SCEVOps)];
1864 if (Result == 0) Result = new SCEVUMaxExpr(Ops);
1865 return Result;
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;
1866}
1867
1868const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
1869 const SCEV *RHS) {
1870 // ~smax(~x, ~y) == smin(x, y).
1871 return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS)));
1872}
1873

--- 4 unchanged lines hidden (view full) ---

1878}
1879
1880const SCEV* ScalarEvolution::getUnknown(Value *V) {
1881 // Don't attempt to do anything other than create a SCEVUnknown object
1882 // here. createSCEV only calls getUnknown after checking for all other
1883 // interesting possibilities, and any other code that calls getUnknown
1884 // is doing so in order to hide a value from SCEV canonicalization.
1885
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
1886 SCEVUnknown *&Result = SCEVUnknowns[V];
1887 if (Result == 0) Result = new SCEVUnknown(V);
1888 return Result;
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;
1889}
1890
1891//===----------------------------------------------------------------------===//
1892// Basic SCEV Analysis and PHI Idiom Recognition Code
1893//
1894
1895/// isSCEVable - Test if values of the given type are analyzable within
1896/// the SCEV framework. This primarily includes integer types, and it

--- 37 unchanged lines hidden (view full) ---

1934 if (Ty->isInteger())
1935 return Ty;
1936
1937 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!");
1938 return TD->getIntPtrType();
1939}
1940
1941const SCEV* ScalarEvolution::getCouldNotCompute() {
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() {
1942 return CouldNotCompute;
2056 return &CouldNotCompute;
1943}
1944
1945/// hasSCEV - Return true if the SCEV for this value has already been
1946/// computed.
1947bool ScalarEvolution::hasSCEV(Value *V) const {
1948 return Scalars.count(V);
1949}
1950

--- 794 unchanged lines hidden (view full) ---

2745 // succeeds, procede to actually compute a backedge-taken count and
2746 // update the value. The temporary CouldNotCompute value tells SCEV
2747 // code elsewhere that it shouldn't attempt to request a new
2748 // backedge-taken count, which could result in infinite recursion.
2749 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair =
2750 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute()));
2751 if (Pair.second) {
2752 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L);
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);
2753 if (ItCount.Exact != CouldNotCompute) {
2867 if (ItCount.Exact != getCouldNotCompute()) {
2754 assert(ItCount.Exact->isLoopInvariant(L) &&
2755 ItCount.Max->isLoopInvariant(L) &&
2756 "Computed trip count isn't loop invariant for loop!");
2757 ++NumTripCountsComputed;
2758
2759 // Update the value in the map.
2760 Pair.first->second = ItCount;
2761 } else {
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 {
2762 if (ItCount.Max != CouldNotCompute)
2876 if (ItCount.Max != getCouldNotCompute())
2763 // Update the value in the map.
2764 Pair.first->second = ItCount;
2765 if (isa<PHINode>(L->getHeader()->begin()))
2766 // Only count loops that have phi nodes as not being computable.
2767 ++NumTripCountsNotComputed;
2768 }
2769
2770 // Now that we know more about the trip count for this loop, forget any

--- 49 unchanged lines hidden (view full) ---

2820/// ComputeBackedgeTakenCount - Compute the number of times the backedge
2821/// of the specified loop will execute.
2822ScalarEvolution::BackedgeTakenInfo
2823ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
2824 SmallVector<BasicBlock*, 8> ExitingBlocks;
2825 L->getExitingBlocks(ExitingBlocks);
2826
2827 // Examine all exits and pick the most conservative values.
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.
2828 const SCEV* BECount = CouldNotCompute;
2829 const SCEV* MaxBECount = CouldNotCompute;
2942 const SCEV* BECount = getCouldNotCompute();
2943 const SCEV* MaxBECount = getCouldNotCompute();
2830 bool CouldNotComputeBECount = false;
2831 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2832 BackedgeTakenInfo NewBTI =
2833 ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
2834
2944 bool CouldNotComputeBECount = false;
2945 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
2946 BackedgeTakenInfo NewBTI =
2947 ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]);
2948
2835 if (NewBTI.Exact == CouldNotCompute) {
2949 if (NewBTI.Exact == getCouldNotCompute()) {
2836 // We couldn't compute an exact value for this exit, so
2837 // we won't be able to compute an exact value for the loop.
2838 CouldNotComputeBECount = true;
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;
2839 BECount = CouldNotCompute;
2953 BECount = getCouldNotCompute();
2840 } else if (!CouldNotComputeBECount) {
2954 } else if (!CouldNotComputeBECount) {
2841 if (BECount == CouldNotCompute)
2955 if (BECount == getCouldNotCompute())
2842 BECount = NewBTI.Exact;
2843 else
2844 BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
2845 }
2956 BECount = NewBTI.Exact;
2957 else
2958 BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact);
2959 }
2846 if (MaxBECount == CouldNotCompute)
2960 if (MaxBECount == getCouldNotCompute())
2847 MaxBECount = NewBTI.Max;
2961 MaxBECount = NewBTI.Max;
2848 else if (NewBTI.Max != CouldNotCompute)
2962 else if (NewBTI.Max != getCouldNotCompute())
2849 MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max);
2850 }
2851
2852 return BackedgeTakenInfo(BECount, MaxBECount);
2853}
2854
2855/// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge
2856/// of the specified loop will execute if it exits via the specified block.
2857ScalarEvolution::BackedgeTakenInfo
2858ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L,
2859 BasicBlock *ExitingBlock) {
2860
2861 // Okay, we've chosen an exiting block. See what condition causes us to
2862 // exit at this block.
2863 //
2864 // FIXME: we should be able to handle switch instructions (with a single exit)
2865 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
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());
2866 if (ExitBr == 0) return CouldNotCompute;
2980 if (ExitBr == 0) return getCouldNotCompute();
2867 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!");
2868
2869 // At this point, we know we have a conditional branch that determines whether
2870 // the loop is exited. However, we don't know if the branch is executed each
2871 // time through the loop. If not, then the execution count of the branch will
2872 // not be equal to the trip count of the loop.
2873 //
2874 // Currently we check for this by checking to see if the Exit branch goes to

--- 12 unchanged lines hidden (view full) ---

2887 ExitBr->getSuccessor(1) != L->getHeader() &&
2888 ExitBr->getParent() != L->getHeader()) {
2889 // The simple checks failed, try climbing the unique predecessor chain
2890 // up to the header.
2891 bool Ok = false;
2892 for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
2893 BasicBlock *Pred = BB->getUniquePredecessor();
2894 if (!Pred)
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)
2895 return CouldNotCompute;
3009 return getCouldNotCompute();
2896 TerminatorInst *PredTerm = Pred->getTerminator();
2897 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
2898 BasicBlock *PredSucc = PredTerm->getSuccessor(i);
2899 if (PredSucc == BB)
2900 continue;
2901 // If the predecessor has a successor that isn't BB and isn't
2902 // outside the loop, assume the worst.
2903 if (L->contains(PredSucc))
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))
2904 return CouldNotCompute;
3018 return getCouldNotCompute();
2905 }
2906 if (Pred == L->getHeader()) {
2907 Ok = true;
2908 break;
2909 }
2910 BB = Pred;
2911 }
2912 if (!Ok)
3019 }
3020 if (Pred == L->getHeader()) {
3021 Ok = true;
3022 break;
3023 }
3024 BB = Pred;
3025 }
3026 if (!Ok)
2913 return CouldNotCompute;
3027 return getCouldNotCompute();
2914 }
2915
2916 // Procede to the next level to examine the exit condition expression.
2917 return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
2918 ExitBr->getSuccessor(0),
2919 ExitBr->getSuccessor(1));
2920}
2921

--- 8 unchanged lines hidden (view full) ---

2930 // Check if the controlling expression for this loop is an And or Or.
2931 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
2932 if (BO->getOpcode() == Instruction::And) {
2933 // Recurse on the operands of the and.
2934 BackedgeTakenInfo BTI0 =
2935 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
2936 BackedgeTakenInfo BTI1 =
2937 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
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);
2938 const SCEV* BECount = CouldNotCompute;
2939 const SCEV* MaxBECount = CouldNotCompute;
3052 const SCEV* BECount = getCouldNotCompute();
3053 const SCEV* MaxBECount = getCouldNotCompute();
2940 if (L->contains(TBB)) {
2941 // Both conditions must be true for the loop to continue executing.
2942 // Choose the less conservative count.
3054 if (L->contains(TBB)) {
3055 // Both conditions must be true for the loop to continue executing.
3056 // Choose the less conservative count.
2943 if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
2944 BECount = CouldNotCompute;
3057 if (BTI0.Exact == getCouldNotCompute() ||
3058 BTI1.Exact == getCouldNotCompute())
3059 BECount = getCouldNotCompute();
2945 else
2946 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3060 else
3061 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2947 if (BTI0.Max == CouldNotCompute)
3062 if (BTI0.Max == getCouldNotCompute())
2948 MaxBECount = BTI1.Max;
3063 MaxBECount = BTI1.Max;
2949 else if (BTI1.Max == CouldNotCompute)
3064 else if (BTI1.Max == getCouldNotCompute())
2950 MaxBECount = BTI0.Max;
2951 else
2952 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
2953 } else {
2954 // Both conditions must be true for the loop to exit.
2955 assert(L->contains(FBB) && "Loop block has no successor in loop!");
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!");
2956 if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
3071 if (BTI0.Exact != getCouldNotCompute() &&
3072 BTI1.Exact != getCouldNotCompute())
2957 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3073 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2958 if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
3074 if (BTI0.Max != getCouldNotCompute() &&
3075 BTI1.Max != getCouldNotCompute())
2959 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
2960 }
2961
2962 return BackedgeTakenInfo(BECount, MaxBECount);
2963 }
2964 if (BO->getOpcode() == Instruction::Or) {
2965 // Recurse on the operands of the or.
2966 BackedgeTakenInfo BTI0 =
2967 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
2968 BackedgeTakenInfo BTI1 =
2969 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
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);
2970 const SCEV* BECount = CouldNotCompute;
2971 const SCEV* MaxBECount = CouldNotCompute;
3087 const SCEV* BECount = getCouldNotCompute();
3088 const SCEV* MaxBECount = getCouldNotCompute();
2972 if (L->contains(FBB)) {
2973 // Both conditions must be false for the loop to continue executing.
2974 // Choose the less conservative count.
3089 if (L->contains(FBB)) {
3090 // Both conditions must be false for the loop to continue executing.
3091 // Choose the less conservative count.
2975 if (BTI0.Exact == CouldNotCompute || BTI1.Exact == CouldNotCompute)
2976 BECount = CouldNotCompute;
3092 if (BTI0.Exact == getCouldNotCompute() ||
3093 BTI1.Exact == getCouldNotCompute())
3094 BECount = getCouldNotCompute();
2977 else
2978 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3095 else
3096 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2979 if (BTI0.Max == CouldNotCompute)
3097 if (BTI0.Max == getCouldNotCompute())
2980 MaxBECount = BTI1.Max;
3098 MaxBECount = BTI1.Max;
2981 else if (BTI1.Max == CouldNotCompute)
3099 else if (BTI1.Max == getCouldNotCompute())
2982 MaxBECount = BTI0.Max;
2983 else
2984 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
2985 } else {
2986 // Both conditions must be false for the loop to exit.
2987 assert(L->contains(TBB) && "Loop block has no successor in loop!");
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!");
2988 if (BTI0.Exact != CouldNotCompute && BTI1.Exact != CouldNotCompute)
3106 if (BTI0.Exact != getCouldNotCompute() &&
3107 BTI1.Exact != getCouldNotCompute())
2989 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
3108 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
2990 if (BTI0.Max != CouldNotCompute && BTI1.Max != CouldNotCompute)
3109 if (BTI0.Max != getCouldNotCompute() &&
3110 BTI1.Max != getCouldNotCompute())
2991 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
2992 }
2993
2994 return BackedgeTakenInfo(BECount, MaxBECount);
2995 }
2996 }
2997
2998 // With an icmp, it may be feasible to compute an exact backedge-taken count.

--- 160 unchanged lines hidden (view full) ---

3159/// 'icmp op load X, cst', try to see if we can compute the backedge
3160/// execution count.
3161const SCEV *
3162ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount(
3163 LoadInst *LI,
3164 Constant *RHS,
3165 const Loop *L,
3166 ICmpInst::Predicate predicate) {
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) {
3167 if (LI->isVolatile()) return CouldNotCompute;
3287 if (LI->isVolatile()) return getCouldNotCompute();
3168
3169 // Check to see if the loaded pointer is a getelementptr of a global.
3170 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3288
3289 // Check to see if the loaded pointer is a getelementptr of a global.
3290 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
3171 if (!GEP) return CouldNotCompute;
3291 if (!GEP) return getCouldNotCompute();
3172
3173 // Make sure that it is really a constant global we are gepping, with an
3174 // initializer, and make sure the first IDX is really 0.
3175 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
3176 if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
3177 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
3178 !cast<Constant>(GEP->getOperand(1))->isNullValue())
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())
3179 return CouldNotCompute;
3299 return getCouldNotCompute();
3180
3181 // Okay, we allow one non-constant index into the GEP instruction.
3182 Value *VarIdx = 0;
3183 std::vector<ConstantInt*> Indexes;
3184 unsigned VarIdxNum = 0;
3185 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
3186 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
3187 Indexes.push_back(CI);
3188 } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
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))) {
3189 if (VarIdx) return CouldNotCompute; // Multiple non-constant idx's.
3309 if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's.
3190 VarIdx = GEP->getOperand(i);
3191 VarIdxNum = i-2;
3192 Indexes.push_back(0);
3193 }
3194
3195 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
3196 // Check to see if X is a loop variant variable value now.
3197 const SCEV* Idx = getSCEV(VarIdx);
3198 Idx = getSCEVAtScope(Idx, L);
3199
3200 // We can only recognize very limited forms of loop index expressions, in
3201 // particular, only affine AddRec's like {C1,+,C2}.
3202 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
3203 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
3204 !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
3205 !isa<SCEVConstant>(IdxExpr->getOperand(1)))
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)))
3206 return CouldNotCompute;
3326 return getCouldNotCompute();
3207
3208 unsigned MaxSteps = MaxBruteForceIterations;
3209 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
3210 ConstantInt *ItCst =
3211 ConstantInt::get(cast<IntegerType>(IdxExpr->getType()), IterationNum);
3212 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this);
3213
3214 // Form the GEP offset.

--- 10 unchanged lines hidden (view full) ---

3225 errs() << "\n***\n*** Computed loop count " << *ItCst
3226 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
3227 << "***\n";
3228#endif
3229 ++NumArrayLenItCounts;
3230 return getConstant(ItCst); // Found terminating iteration!
3231 }
3232 }
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 }
3233 return CouldNotCompute;
3353 return getCouldNotCompute();
3234}
3235
3236
3237/// CanConstantFold - Return true if we can constant fold an instruction of the
3238/// specified type, assuming that all operands were constants.
3239static bool CanConstantFold(const Instruction *I) {
3240 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
3241 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I))

--- 124 unchanged lines hidden (view full) ---

3366 PHIVal = NextPHI;
3367 }
3368}
3369
3370/// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute a
3371/// constant number of times (the condition evolves only from constants),
3372/// try to evaluate a few iterations of the loop until we get the exit
3373/// condition gets a value of ExitWhen (true or false). If we cannot
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
3374/// evaluate the trip count of the loop, return CouldNotCompute.
3494/// evaluate the trip count of the loop, return getCouldNotCompute().
3375const SCEV *
3376ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
3377 Value *Cond,
3378 bool ExitWhen) {
3379 PHINode *PN = getConstantEvolvingPHI(Cond, L);
3495const SCEV *
3496ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L,
3497 Value *Cond,
3498 bool ExitWhen) {
3499 PHINode *PN = getConstantEvolvingPHI(Cond, L);
3380 if (PN == 0) return CouldNotCompute;
3500 if (PN == 0) return getCouldNotCompute();
3381
3382 // Since the loop is canonicalized, the PHI node must have two entries. One
3383 // entry must be a constant (coming in from outside of the loop), and the
3384 // second must be derived from the same PHI.
3385 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1));
3386 Constant *StartCST =
3387 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge));
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));
3388 if (StartCST == 0) return CouldNotCompute; // Must be a constant.
3508 if (StartCST == 0) return getCouldNotCompute(); // Must be a constant.
3389
3390 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3391 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3509
3510 Value *BEValue = PN->getIncomingValue(SecondIsBackedge);
3511 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L);
3392 if (PN2 != PN) return CouldNotCompute; // Not derived from same PHI.
3512 if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI.
3393
3394 // Okay, we find a PHI node that defines the trip count of this loop. Execute
3395 // the loop symbolically to determine when the condition gets a value of
3396 // "ExitWhen".
3397 unsigned IterationNum = 0;
3398 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis.
3399 for (Constant *PHIVal = StartCST;
3400 IterationNum != MaxIterations; ++IterationNum) {
3401 ConstantInt *CondVal =
3402 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal));
3403
3404 // Couldn't symbolically evaluate.
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.
3405 if (!CondVal) return CouldNotCompute;
3525 if (!CondVal) return getCouldNotCompute();
3406
3407 if (CondVal->getValue() == uint64_t(ExitWhen)) {
3526
3527 if (CondVal->getValue() == uint64_t(ExitWhen)) {
3408 ConstantEvolutionLoopExitValue[PN] = PHIVal;
3409 ++NumBruteForceTripCountsComputed;
3410 return getConstant(Type::Int32Ty, IterationNum);
3411 }
3412
3413 // Compute the value of the PHI node for the next iteration.
3414 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal);
3415 if (NextPHI == 0 || NextPHI == PHIVal)
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)
3416 return CouldNotCompute; // Couldn't evaluate or not making progress...
3535 return getCouldNotCompute();// Couldn't evaluate or not making progress...
3417 PHIVal = NextPHI;
3418 }
3419
3420 // Too many iterations were needed to evaluate.
3536 PHIVal = NextPHI;
3537 }
3538
3539 // Too many iterations were needed to evaluate.
3421 return CouldNotCompute;
3540 return getCouldNotCompute();
3422}
3423
3424/// getSCEVAtScope - Return a SCEV expression handle for the specified value
3425/// at the specified scope in the program. The L value specifies a loop
3426/// nest to evaluate the expression at, where null is the top-level or a
3427/// specified loop is immediately inside of the loop.
3428///
3429/// This method can be used to compute the exit value for a variable defined

--- 22 unchanged lines hidden (view full) ---

3452 if (const SCEVConstant *BTCC =
3453 dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
3454 // Okay, we know how many times the containing loop executes. If
3455 // this is a constant evolving PHI node, get the final value at
3456 // the specified iteration number.
3457 Constant *RV = getConstantEvolutionLoopExitValue(PN,
3458 BTCC->getValue()->getValue(),
3459 LI);
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);
3460 if (RV) return getUnknown(RV);
3579 if (RV) return getSCEV(RV);
3461 }
3462 }
3463
3464 // Okay, this is an expression that we cannot symbolically evaluate
3465 // into a SCEV. Check to see if it's possible to symbolically evaluate
3466 // the arguments into constants, and if so, try to constant propagate the
3467 // result. This is particularly useful for computing loop exit values.
3468 if (CanConstantFold(I)) {
3469 // Check to see if we've folded this instruction at this loop before.
3470 std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I];
3471 std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair =
3472 Values.insert(std::make_pair(L, static_cast<Constant *>(0)));
3473 if (!Pair.second)
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)
3474 return Pair.first->second ? &*getUnknown(Pair.first->second) : V;
3593 return Pair.first->second ? &*getSCEV(Pair.first->second) : V;
3475
3476 std::vector<Constant*> Operands;
3477 Operands.reserve(I->getNumOperands());
3478 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
3479 Value *Op = I->getOperand(i);
3480 if (Constant *C = dyn_cast<Constant>(Op)) {
3481 Operands.push_back(C);
3482 } else {

--- 32 unchanged lines hidden (view full) ---

3515 Constant *C;
3516 if (const CmpInst *CI = dyn_cast<CmpInst>(I))
3517 C = ConstantFoldCompareInstOperands(CI->getPredicate(),
3518 &Operands[0], Operands.size());
3519 else
3520 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(),
3521 &Operands[0], Operands.size());
3522 Pair.first->second = C;
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;
3523 return getUnknown(C);
3642 return getSCEV(C);
3524 }
3525 }
3526
3527 // This is some other type of SCEVUnknown, just return it.
3528 return V;
3529 }
3530
3531 if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) {

--- 37 unchanged lines hidden (view full) ---

3569
3570 // If this is a loop recurrence for a loop that does not contain L, then we
3571 // are dealing with the final value computed by the loop.
3572 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
3573 if (!L || !AddRec->getLoop()->contains(L->getHeader())) {
3574 // To evaluate this recurrence, we need to know how many times the AddRec
3575 // loop iterates. Compute this now.
3576 const SCEV* BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop());
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());
3577 if (BackedgeTakenCount == CouldNotCompute) return AddRec;
3696 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec;
3578
3579 // Then, evaluate the AddRec.
3580 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this);
3581 }
3582 return AddRec;
3583 }
3584
3585 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) {

--- 138 unchanged lines hidden (view full) ---

3724
3725/// HowFarToZero - Return the number of times a backedge comparing the specified
3726/// value to zero will execute. If not computable, return CouldNotCompute.
3727const SCEV* ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) {
3728 // If the value is a constant
3729 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3730 // If the value is already zero, the branch will execute zero times.
3731 if (C->getValue()->isZero()) return C;
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;
3732 return CouldNotCompute; // Otherwise it will loop infinitely.
3851 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3733 }
3734
3735 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3736 if (!AddRec || AddRec->getLoop() != L)
3852 }
3853
3854 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
3855 if (!AddRec || AddRec->getLoop() != L)
3737 return CouldNotCompute;
3856 return getCouldNotCompute();
3738
3739 if (AddRec->isAffine()) {
3740 // If this is an affine expression, the execution count of this branch is
3741 // the minimum unsigned root of the following equation:
3742 //
3743 // Start + Step*N = 0 (mod 2^BW)
3744 //
3745 // equivalent to:

--- 47 unchanged lines hidden (view full) ---

3793 // should not accept a root of 2.
3794 const SCEV* Val = AddRec->evaluateAtIteration(R1, *this);
3795 if (Val->isZero())
3796 return R1; // We found a quadratic root!
3797 }
3798 }
3799 }
3800
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
3801 return CouldNotCompute;
3920 return getCouldNotCompute();
3802}
3803
3804/// HowFarToNonZero - Return the number of times a backedge checking the
3805/// specified value for nonzero will execute. If not computable, return
3806/// CouldNotCompute
3807const SCEV* ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
3808 // Loops that look like: while (X == 0) are very strange indeed. We don't
3809 // handle them yet except for the trivial case. This could be expanded in the
3810 // future as needed.
3811
3812 // If the value is a constant, check to see if it is known to be non-zero
3813 // already. If so, the backedge will execute zero times.
3814 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
3815 if (!C->getValue()->isNullValue())
3816 return getIntegerSCEV(0, C->getType());
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());
3817 return CouldNotCompute; // Otherwise it will loop infinitely.
3936 return getCouldNotCompute(); // Otherwise it will loop infinitely.
3818 }
3819
3820 // We could implement others, but I really doubt anyone writes loops like
3821 // this, and if they did, they would already be constant folded.
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.
3822 return CouldNotCompute;
3941 return getCouldNotCompute();
3823}
3824
3825/// getLoopPredecessor - If the given loop's header has exactly one unique
3826/// predecessor outside the loop, return it. Otherwise return null.
3827///
3828BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) {
3829 BasicBlock *Header = L->getHeader();
3830 BasicBlock *Pred = 0;

--- 201 unchanged lines hidden (view full) ---

4032
4033 // Check Add for unsigned overflow.
4034 // TODO: More sophisticated things could be done here.
4035 const Type *WideTy = IntegerType::get(getTypeSizeInBits(Ty) + 1);
4036 const SCEV* OperandExtendedAdd =
4037 getAddExpr(getZeroExtendExpr(Diff, WideTy),
4038 getZeroExtendExpr(RoundUp, WideTy));
4039 if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd)
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)
4040 return CouldNotCompute;
4159 return getCouldNotCompute();
4041
4042 return getUDivExpr(Add, Step);
4043}
4044
4045/// HowManyLessThans - Return the number of times a backedge containing the
4046/// specified less-than comparison will execute. If not computable, return
4047/// CouldNotCompute.
4048ScalarEvolution::BackedgeTakenInfo
4049ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
4050 const Loop *L, bool isSigned) {
4051 // Only handle: "ADDREC < LoopInvariant".
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".
4052 if (!RHS->isLoopInvariant(L)) return CouldNotCompute;
4171 if (!RHS->isLoopInvariant(L)) return getCouldNotCompute();
4053
4054 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
4055 if (!AddRec || AddRec->getLoop() != L)
4172
4173 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS);
4174 if (!AddRec || AddRec->getLoop() != L)
4056 return CouldNotCompute;
4175 return getCouldNotCompute();
4057
4058 if (AddRec->isAffine()) {
4059 // FORNOW: We only support unit strides.
4060 unsigned BitWidth = getTypeSizeInBits(AddRec->getType());
4061 const SCEV* Step = AddRec->getStepRecurrence(*this);
4062
4063 // TODO: handle non-constant strides.
4064 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step);
4065 if (!CStep || CStep->isZero())
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())
4066 return CouldNotCompute;
4185 return getCouldNotCompute();
4067 if (CStep->isOne()) {
4068 // With unit stride, the iteration never steps past the limit value.
4069 } else if (CStep->getValue()->getValue().isStrictlyPositive()) {
4070 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) {
4071 // Test whether a positive iteration iteration can step past the limit
4072 // value and past the maximum value for its type in a single step.
4073 if (isSigned) {
4074 APInt Max = APInt::getSignedMaxValue(BitWidth);
4075 if ((Max - CStep->getValue()->getValue())
4076 .slt(CLimit->getValue()->getValue()))
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()))
4077 return CouldNotCompute;
4196 return getCouldNotCompute();
4078 } else {
4079 APInt Max = APInt::getMaxValue(BitWidth);
4080 if ((Max - CStep->getValue()->getValue())
4081 .ult(CLimit->getValue()->getValue()))
4197 } else {
4198 APInt Max = APInt::getMaxValue(BitWidth);
4199 if ((Max - CStep->getValue()->getValue())
4200 .ult(CLimit->getValue()->getValue()))
4082 return CouldNotCompute;
4201 return getCouldNotCompute();
4083 }
4084 } else
4085 // TODO: handle non-constant limit values below.
4202 }
4203 } else
4204 // TODO: handle non-constant limit values below.
4086 return CouldNotCompute;
4205 return getCouldNotCompute();
4087 } else
4088 // TODO: handle negative strides below.
4206 } else
4207 // TODO: handle negative strides below.
4089 return CouldNotCompute;
4208 return getCouldNotCompute();
4090
4091 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant
4092 // m. So, we count the number of iterations in which {n,+,s} < m is true.
4093 // Note that we cannot simply return max(m-n,0)/s because it's not safe to
4094 // treat m-n as signed nor unsigned due to overflow possibility.
4095
4096 // First, we get the value of the LHS in the first iteration: n
4097 const SCEV* Start = AddRec->getOperand(0);

--- 23 unchanged lines hidden (view full) ---

4121 .lshr(GetMinLeadingZeros(End)));
4122
4123 // Finally, we subtract these two values and divide, rounding up, to get
4124 // the number of times the backedge is executed.
4125 const SCEV* BECount = getBECount(Start, End, Step);
4126
4127 // The maximum backedge count is similar, except using the minimum start
4128 // value and the maximum end value.
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.
4129 const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);;
4248 const SCEV* MaxBECount = getBECount(MinStart, MaxEnd, Step);
4130
4131 return BackedgeTakenInfo(BECount, MaxBECount);
4132 }
4133
4249
4250 return BackedgeTakenInfo(BECount, MaxBECount);
4251 }
4252
4134 return CouldNotCompute;
4253 return getCouldNotCompute();
4135}
4136
4137/// getNumIterationsInRange - Return the number of iterations of this loop that
4138/// produce values in the specified constant range. Another way of looking at
4139/// this is that it returns the first iteration number where the value is not in
4140/// the condition, thus computing the exit count. If the iteration count can't
4141/// be computed, an instance of SCEVCouldNotCompute is returned.
4142const SCEV* SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,

--- 171 unchanged lines hidden (view full) ---

4314ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
4315 : CallbackVH(V), SE(se) {}
4316
4317//===----------------------------------------------------------------------===//
4318// ScalarEvolution Class Implementation
4319//===----------------------------------------------------------------------===//
4320
4321ScalarEvolution::ScalarEvolution()
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()
4322 : FunctionPass(&ID), CouldNotCompute(new SCEVCouldNotCompute()) {
4441 : FunctionPass(&ID) {
4323}
4324
4325bool ScalarEvolution::runOnFunction(Function &F) {
4326 this->F = &F;
4327 LI = &getAnalysis<LoopInfo>();
4328 TD = getAnalysisIfAvailable<TargetData>();
4329 return false;
4330}
4331
4332void ScalarEvolution::releaseMemory() {
4333 Scalars.clear();
4334 BackedgeTakenCounts.clear();
4335 ConstantEvolutionLoopExitValue.clear();
4336 ValuesAtScopes.clear();
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();
4337
4338 for (std::map<ConstantInt*, SCEVConstant*>::iterator
4339 I = SCEVConstants.begin(), E = SCEVConstants.end(); I != E; ++I)
4340 delete I->second;
4341 for (std::map<std::pair<const SCEV*, const Type*>,
4342 SCEVTruncateExpr*>::iterator I = SCEVTruncates.begin(),
4343 E = SCEVTruncates.end(); I != E; ++I)
4344 delete I->second;
4345 for (std::map<std::pair<const SCEV*, const Type*>,
4346 SCEVZeroExtendExpr*>::iterator I = SCEVZeroExtends.begin(),
4347 E = SCEVZeroExtends.end(); I != E; ++I)
4348 delete I->second;
4349 for (std::map<std::pair<unsigned, std::vector<const SCEV*> >,
4350 SCEVCommutativeExpr*>::iterator I = SCEVCommExprs.begin(),
4351 E = SCEVCommExprs.end(); I != E; ++I)
4352 delete I->second;
4353 for (std::map<std::pair<const SCEV*, const SCEV*>, SCEVUDivExpr*>::iterator
4354 I = SCEVUDivs.begin(), E = SCEVUDivs.end(); I != E; ++I)
4355 delete I->second;
4356 for (std::map<std::pair<const SCEV*, const Type*>,
4357 SCEVSignExtendExpr*>::iterator I = SCEVSignExtends.begin(),
4358 E = SCEVSignExtends.end(); I != E; ++I)
4359 delete I->second;
4360 for (std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
4361 SCEVAddRecExpr*>::iterator I = SCEVAddRecExprs.begin(),
4362 E = SCEVAddRecExprs.end(); I != E; ++I)
4363 delete I->second;
4364 for (std::map<Value*, SCEVUnknown*>::iterator I = SCEVUnknowns.begin(),
4365 E = SCEVUnknowns.end(); I != E; ++I)
4366 delete I->second;
4367
4368 SCEVConstants.clear();
4369 SCEVTruncates.clear();
4370 SCEVZeroExtends.clear();
4371 SCEVCommExprs.clear();
4372 SCEVUDivs.clear();
4373 SCEVSignExtends.clear();
4374 SCEVAddRecExprs.clear();
4375 SCEVUnknowns.clear();
4456 UniqueSCEVs.clear();
4457 SCEVAllocator.Reset();
4376}
4377
4378void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const {
4379 AU.setPreservesAll();
4380 AU.addRequiredTransitive<LoopInfo>();
4381}
4382
4383bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {

--- 81 unchanged lines hidden --- 		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 ---