61 #define DEBUG_TYPE "scalar-evolution"
94 "Number of trip counts computed with array length");
96 "Number of loops with predictable loop counts");
98 "Number of loops without predictable loop counts");
99 STATISTIC(NumBruteForceTripCountsComputed,
100 "Number of loops with trip counts computed by force");
104 cl::desc(
"Maximum number of iterations SCEV will "
105 "symbolically execute a constant "
112 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
115 "Scalar Evolution Analysis",
false,
true)
121 char ScalarEvolution::
ID = 0;
131 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
146 OS <<
"(trunc " << *Op->getType() <<
" " << *Op <<
" to "
153 OS <<
"(zext " << *Op->getType() <<
" " << *Op <<
" to "
160 OS <<
"(sext " << *Op->getType() <<
" " << *Op <<
" to "
186 const char *OpStr = 0;
213 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
220 OS <<
"sizeof(" << *AllocTy <<
")";
224 OS <<
"alignof(" << *AllocTy <<
")";
231 OS <<
"offsetof(" << *CTy <<
", ";
242 OS <<
"***COULDNOTCOMPUTE***";
252 return cast<SCEVConstant>(
this)->
getType();
256 return cast<SCEVCastExpr>(
this)->
getType();
261 return cast<SCEVNAryExpr>(
this)->
getType();
263 return cast<SCEVAddExpr>(
this)->
getType();
265 return cast<SCEVUDivExpr>(
this)->
getType();
267 return cast<SCEVUnknown>(
this)->
getType();
277 return SC->getValue()->isZero();
283 return SC->getValue()->isOne();
289 return SC->getValue()->isAllOnesValue();
297 if (!Mul)
return false;
301 if (!SC)
return false;
319 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
321 UniqueSCEVs.InsertNode(S, IP);
336 unsigned SCEVTy,
const SCEV *op,
Type *ty)
337 :
SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
344 "Cannot truncate non-integer value!");
352 "Cannot zero extend non-integer value!");
360 "Cannot sign extend non-integer value!");
363 void SCEVUnknown::deleted() {
365 SE->forgetMemoizedResults(
this);
368 SE->UniqueSCEVs.RemoveNode(
this);
374 void SCEVUnknown::allUsesReplacedWith(
Value *New) {
376 SE->forgetMemoizedResults(
this);
379 SE->UniqueSCEVs.RemoveNode(
this);
389 if (VCE->getOpcode() == Instruction::PtrToInt)
390 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
391 if (CE->getOpcode() == Instruction::GetElementPtr &&
392 CE->getOperand(0)->isNullValue() &&
393 CE->getNumOperands() == 2)
394 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(1)))
396 AllocTy = cast<PointerType>(CE->getOperand(0)->getType())
406 if (VCE->getOpcode() == Instruction::PtrToInt)
407 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
408 if (CE->getOpcode() == Instruction::GetElementPtr &&
409 CE->getOperand(0)->isNullValue()) {
411 cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
412 if (
StructType *STy = dyn_cast<StructType>(Ty))
413 if (!STy->isPacked() &&
414 CE->getNumOperands() == 3 &&
415 CE->getOperand(1)->isNullValue()) {
416 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(2)))
418 STy->getNumElements() == 2 &&
419 STy->getElementType(0)->isIntegerTy(1)) {
420 AllocTy = STy->getElementType(1);
431 if (VCE->getOpcode() == Instruction::PtrToInt)
432 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
433 if (CE->getOpcode() == Instruction::GetElementPtr &&
434 CE->getNumOperands() == 3 &&
435 CE->getOperand(0)->isNullValue() &&
436 CE->getOperand(1)->isNullValue()) {
438 cast<PointerType>(CE->getOperand(0)->getType())->getElementType();
459 class SCEVComplexityCompare {
462 explicit SCEVComplexityCompare(
const LoopInfo *li) :
LI(li) {}
465 bool operator()(
const SCEV *LHS,
const SCEV *RHS)
const {
466 return compare(LHS, RHS) < 0;
472 int compare(
const SCEV *LHS,
const SCEV *RHS)
const {
480 return (
int)LType - (int)RType;
497 RIsPointer = RV->getType()->isPointerTy();
498 if (LIsPointer != RIsPointer)
499 return (
int)LIsPointer - (int)RIsPointer;
502 unsigned LID = LV->getValueID(),
503 RID = RV->getValueID();
505 return (
int)LID - (int)RID;
508 if (
const Argument *LA = dyn_cast<Argument>(LV)) {
509 const Argument *RA = cast<Argument>(RV);
511 return (
int)LArgNo - (int)RArgNo;
516 if (
const Instruction *LInst = dyn_cast<Instruction>(LV)) {
522 if (LParent != RParent) {
523 unsigned LDepth =
LI->getLoopDepth(LParent),
524 RDepth =
LI->getLoopDepth(RParent);
525 if (LDepth != RDepth)
526 return (
int)LDepth - (int)RDepth;
530 unsigned LNumOps = LInst->getNumOperands(),
532 return (
int)LNumOps - (int)RNumOps;
544 const APInt &RA = RC->getValue()->getValue();
545 unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.
getBitWidth();
546 if (LBitWidth != RBitWidth)
547 return (
int)LBitWidth - (int)RBitWidth;
548 return LA.ult(RA) ? -1 : 1;
556 const Loop *LLoop = LA->
getLoop(), *RLoop = RA->getLoop();
557 if (LLoop != RLoop) {
558 unsigned LDepth = LLoop->getLoopDepth(),
559 RDepth = RLoop->getLoopDepth();
560 if (LDepth != RDepth)
561 return (
int)LDepth - (int)RDepth;
565 unsigned LNumOps = LA->
getNumOperands(), RNumOps = RA->getNumOperands();
566 if (LNumOps != RNumOps)
567 return (
int)LNumOps - (int)RNumOps;
570 for (
unsigned i = 0; i != LNumOps; ++i) {
571 long X = compare(LA->
getOperand(i), RA->getOperand(i));
587 unsigned LNumOps = LC->
getNumOperands(), RNumOps = RC->getNumOperands();
588 if (LNumOps != RNumOps)
589 return (
int)LNumOps - (int)RNumOps;
591 for (
unsigned i = 0; i != LNumOps; ++i) {
594 long X = compare(LC->
getOperand(i), RC->getOperand(i));
598 return (
int)LNumOps - (int)RNumOps;
606 long X = compare(LC->
getLHS(), RC->getLHS());
609 return compare(LC->
getRHS(), RC->getRHS());
619 return compare(LC->
getOperand(), RC->getOperand());
641 if (Ops.
size() < 2)
return;
642 if (Ops.
size() == 2) {
645 const SCEV *&LHS = Ops[0], *&RHS = Ops[1];
646 if (SCEVComplexityCompare(LI)(RHS, LHS))
652 std::stable_sort(Ops.
begin(), Ops.
end(), SCEVComplexityCompare(LI));
658 for (
unsigned i = 0, e = Ops.
size(); i != e-2; ++i) {
659 const SCEV *S = Ops[i];
664 for (
unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) {
669 if (i == e-2)
return;
750 APInt OddFactorial(W, 1);
752 for (
unsigned i = 3; i <= K; ++i) {
756 Mult = Mult.
lshr(TwoFactors);
757 OddFactorial *=
Mult;
761 unsigned CalculationBits = W +
T;
770 APInt MultiplyFactor = OddFactorial.
zext(W+1);
772 MultiplyFactor = MultiplyFactor.
trunc(W);
778 for (
unsigned i = 1; i != K; ++i) {
803 ScalarEvolution &SE)
const {
810 if (isa<SCEVCouldNotCompute>(Coeff))
825 "This is not a truncating conversion!");
827 "This is not a conversion to a SCEVable type!");
835 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
856 if (
const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Op)) {
858 bool hasTrunc =
false;
859 for (
unsigned i = 0, e = SA->getNumOperands(); i != e && !hasTrunc; ++i) {
861 hasTrunc = isa<SCEVTruncateExpr>(S);
866 UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
871 if (
const SCEVMulExpr *SM = dyn_cast<SCEVMulExpr>(Op)) {
873 bool hasTrunc =
false;
874 for (
unsigned i = 0, e = SM->getNumOperands(); i != e && !hasTrunc; ++i) {
876 hasTrunc = isa<SCEVTruncateExpr>(S);
881 UniqueSCEVs.FindNodeOrInsertPos(ID, IP);
885 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
887 for (
unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
897 UniqueSCEVs.InsertNode(S, IP);
904 "This is not an extending conversion!");
906 "This is not a conversion to a SCEVable type!");
925 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
931 const SCEV *X =
ST->getOperand();
945 if (AR->isAffine()) {
946 const SCEV *Start = AR->getStart();
947 const SCEV *Step = AR->getStepRecurrence(*
this);
949 const Loop *L = AR->getLoop();
956 L, AR->getNoWrapFlags());
967 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
973 const SCEV *CastedMaxBECount =
975 const SCEV *RecastedMaxBECount =
977 if (MaxBECount == RecastedMaxBECount) {
983 const SCEV *WideMaxBECount =
985 const SCEV *OperandExtendedAdd =
989 if (ZAdd == OperandExtendedAdd) {
995 L, AR->getNoWrapFlags());
1003 if (ZAdd == OperandExtendedAdd) {
1010 L, AR->getNoWrapFlags());
1024 AR->getPostIncExpr(*
this),
N))) {
1030 L, AR->getNoWrapFlags());
1038 AR->getPostIncExpr(*
this),
N))) {
1045 L, AR->getNoWrapFlags());
1053 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1056 UniqueSCEVs.InsertNode(S, IP);
1065 ScalarEvolution *SE) {
1088 ScalarEvolution *SE) {
1124 const SCEV *OperandExtendedStart =
1132 DEBUG(
dbgs() <<
"SCEV: untested prestart overflow check\n");
1140 if (OverflowLimit &&
1150 ScalarEvolution *SE) {
1162 "This is not an extending conversion!");
1164 "This is not a conversion to a SCEVable type!");
1187 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1197 const SCEV *X =
ST->getOperand();
1211 if (AR->isAffine()) {
1212 const SCEV *Start = AR->getStart();
1213 const SCEV *Step = AR->getStepRecurrence(*
this);
1215 const Loop *L = AR->getLoop();
1233 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
1239 const SCEV *CastedMaxBECount =
1241 const SCEV *RecastedMaxBECount =
1243 if (MaxBECount == RecastedMaxBECount) {
1249 const SCEV *WideMaxBECount =
1251 const SCEV *OperandExtendedAdd =
1255 if (SAdd == OperandExtendedAdd) {
1261 L, AR->getNoWrapFlags());
1265 OperandExtendedAdd =
1269 if (SAdd == OperandExtendedAdd) {
1275 L, AR->getNoWrapFlags());
1285 if (OverflowLimit &&
1294 L, AR->getNoWrapFlags());
1301 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
1304 UniqueSCEVs.InsertNode(S, IP);
1314 "This is not an extending conversion!");
1316 "This is not a conversion to a SCEVable type!");
1321 if (
SC->getValue()->getValue().isNegative())
1326 const SCEV *NewOp =
T->getOperand();
1334 if (!isa<SCEVZeroExtendExpr>(ZExt))
1339 if (!isa<SCEVSignExtendExpr>(SExt))
1352 if (isa<SCEVSMaxExpr>(Op))
1387 APInt &AccumulatedConstant,
1388 const SCEV *
const *Ops,
size_t NumOperands,
1390 ScalarEvolution &SE) {
1391 bool Interesting =
false;
1395 while (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
1398 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->isZero())
1400 AccumulatedConstant += Scale *
C->getValue()->getValue();
1405 for (; i != NumOperands; ++i) {
1407 if (Mul && isa<SCEVConstant>(Mul->
getOperand(0))) {
1409 Scale * cast<SCEVConstant>(Mul->
getOperand(0))->getValue()->getValue();
1422 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
1423 M.
insert(std::make_pair(Key, NewScale));
1427 Pair.first->second += NewScale;
1435 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
1436 M.
insert(std::make_pair(Ops[i], Scale));
1440 Pair.first->second += Scale;
1452 struct APIntCompare {
1453 bool operator()(
const APInt &LHS,
const APInt &RHS)
const {
1454 return LHS.
ult(RHS);
1464 "only nuw or nsw allowed");
1465 assert(!Ops.
empty() &&
"Cannot get empty add!");
1466 if (Ops.
size() == 1)
return Ops[0];
1469 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
1471 "SCEVAddExpr operand types don't match!");
1478 if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
1481 E = Ops.
end();
I != E; ++
I)
1494 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1496 assert(Idx < Ops.
size());
1497 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1499 Ops[0] =
getConstant(LHSC->getValue()->getValue() +
1500 RHSC->getValue()->getValue());
1501 if (Ops.
size() == 2)
return Ops[0];
1503 LHSC = cast<SCEVConstant>(Ops[0]);
1507 if (LHSC->getValue()->isZero()) {
1512 if (Ops.
size() == 1)
return Ops[0];
1518 Type *Ty = Ops[0]->getType();
1519 bool FoundMatch =
false;
1520 for (
unsigned i = 0, e = Ops.
size(); i != e-1; ++i)
1521 if (Ops[i] == Ops[i+1]) {
1524 while (i+Count != e && Ops[i+Count] == Ops[i])
1529 if (Ops.
size() == Count)
1533 --i; e -= Count - 1;
1543 for (; Idx < Ops.
size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) {
1551 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i) {
1553 if (
T->getOperand()->getType() != SrcType) {
1558 }
else if (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[i])) {
1560 }
else if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) {
1562 for (
unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) {
1564 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) {
1565 if (
T->getOperand()->getType() != SrcType) {
1571 dyn_cast<SCEVConstant>(M->getOperand(j))) {
1589 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
1595 while (Idx < Ops.
size() && Ops[Idx]->getSCEVType() <
scAddExpr)
1599 if (Idx < Ops.
size()) {
1600 bool DeletedAdd =
false;
1601 while (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
1605 Ops.
append(Add->op_begin(), Add->op_end());
1617 while (Idx < Ops.
size() && Ops[Idx]->getSCEVType() <
scMulExpr)
1622 if (Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[Idx])) {
1626 APInt AccumulatedConstant(BitWidth, 0);
1629 APInt(BitWidth, 1), *
this)) {
1633 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
1635 E = NewOps.
end();
I != E; ++
I)
1636 MulOpLists[M.
find(*I)->second].push_back(*
I);
1639 if (AccumulatedConstant != 0)
1642 I = MulOpLists.begin(), E = MulOpLists.end();
I != E; ++
I)
1648 if (Ops.
size() == 1)
1657 for (; Idx < Ops.
size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
1658 const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]);
1659 for (
unsigned MulOp = 0, e = Mul->
getNumOperands(); MulOp != e; ++MulOp) {
1661 if (isa<SCEVConstant>(MulOpSCEV))
1663 for (
unsigned AddOp = 0, e = Ops.
size(); AddOp != e; ++AddOp)
1664 if (MulOpSCEV == Ops[AddOp]) {
1678 if (Ops.
size() == 2)
return OuterMul;
1691 for (
unsigned OtherMulIdx = Idx+1;
1692 OtherMulIdx < Ops.
size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
1694 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
1698 OMulOp != e; ++OMulOp)
1699 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
1717 if (Ops.
size() == 2)
return OuterMul;
1734 for (; Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1740 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
1748 if (!LIOps.
empty()) {
1763 if (Ops.
size() == 1)
return NewRec;
1766 for (
unsigned i = 0;; ++i)
1767 if (Ops[i] == AddRec) {
1777 for (
unsigned OtherIdx = Idx+1;
1778 OtherIdx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
1780 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
1784 for (; OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
1787 dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]))
1788 if (OtherAddRec->getLoop() == AddRecLoop) {
1789 for (
unsigned i = 0, e = OtherAddRec->getNumOperands();
1791 if (i >= AddRecOps.size()) {
1792 AddRecOps.
append(OtherAddRec->op_begin()+i,
1793 OtherAddRec->op_end());
1797 OtherAddRec->getOperand(i));
1799 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
1814 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
1818 static_cast<SCEVAddExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
1821 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
1824 UniqueSCEVs.InsertNode(S, IP);
1830 static uint64_t
umul_ov(uint64_t i, uint64_t j,
bool &Overflow) {
1832 if (j > 1 && k / j != i) Overflow =
true;
1839 static uint64_t
Choose(uint64_t n, uint64_t k,
bool &Overflow) {
1848 if (n == 0 || n == k)
return 1;
1849 if (k > n)
return 0;
1855 for (uint64_t i = 1; i <= k; ++i) {
1856 r =
umul_ov(r, n-(i-1), Overflow);
1867 "only nuw or nsw allowed");
1868 assert(!Ops.
empty() &&
"Cannot get empty mul!");
1869 if (Ops.
size() == 1)
return Ops[0];
1872 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
1874 "SCEVMulExpr operand types don't match!");
1881 if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
1884 E = Ops.
end();
I != E; ++
I)
1897 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
1900 if (Ops.
size() == 2)
1901 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
1902 if (Add->getNumOperands() == 2 &&
1903 isa<SCEVConstant>(Add->getOperand(0)))
1908 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
1911 LHSC->getValue()->getValue() *
1912 RHSC->getValue()->getValue());
1914 Ops.erase(Ops.begin()+1);
1915 if (Ops.size() == 1)
return Ops[0];
1916 LHSC = cast<SCEVConstant>(Ops[0]);
1920 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
1923 }
else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
1926 }
else if (Ops[0]->isAllOnesValue()) {
1929 if (Ops.
size() == 2) {
1930 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
1932 bool AnyFolded =
false;
1934 E = Add->op_end();
I != E; ++
I) {
1936 if (!isa<SCEVMulExpr>(Mul)) AnyFolded =
true;
1943 AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
1947 E = AddRec->op_end();
I != E; ++
I) {
1956 if (Ops.
size() == 1)
1961 while (Idx < Ops.
size() && Ops[Idx]->getSCEVType() <
scMulExpr)
1965 if (Idx < Ops.
size()) {
1966 bool DeletedMul =
false;
1967 while (
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
1971 Ops.
append(Mul->op_begin(), Mul->op_end());
1989 for (; Idx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
1995 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2003 if (!LIOps.
empty()) {
2020 if (Ops.
size() == 1)
return NewRec;
2023 for (
unsigned i = 0;; ++i)
2024 if (Ops[i] == AddRec) {
2034 for (
unsigned OtherIdx = Idx+1;
2035 OtherIdx < Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2037 if (AddRecLoop != cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop())
2050 bool OpsModified =
false;
2051 for (; OtherIdx != Ops.
size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2055 if (!OtherAddRec || OtherAddRec->
getLoop() != AddRecLoop)
2058 bool Overflow =
false;
2065 for (
int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
2066 uint64_t Coeff1 =
Choose(x, 2*x - y, Overflow);
2069 z < ze && !Overflow; ++z) {
2070 uint64_t Coeff2 =
Choose(2*x - y, x-z, Overflow);
2072 if (LargerThan64Bits)
2073 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
2075 Coeff = Coeff1*Coeff2;
2087 if (Ops.
size() == 2)
return NewAddRec;
2088 Ops[Idx] = NewAddRec;
2089 Ops.
erase(Ops.
begin() + OtherIdx); --OtherIdx;
2108 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2112 static_cast<SCEVMulExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
2115 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
2118 UniqueSCEVs.InsertNode(S, IP);
2130 "SCEVUDivExpr operand types don't match!");
2132 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
2133 if (RHSC->getValue()->equalsInt(1))
2138 if (!RHSC->getValue()->isZero()) {
2143 unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros();
2147 if (!RHSC->getValue()->getValue().isPowerOf2())
2153 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*
this))) {
2155 const APInt &StepInt = Step->getValue()->getValue();
2156 const APInt &DivInt = RHSC->getValue()->getValue();
2157 if (!StepInt.
urem(DivInt) &&
2163 for (
unsigned i = 0, e = AR->getNumOperands(); i != e; ++i)
2172 if (StartC && !DivInt.
urem(StepInt) &&
2178 const APInt &StartRem = StartInt.
urem(StepInt);
2185 if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) {
2187 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i)
2191 for (
unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
2192 const SCEV *Op = M->getOperand(i);
2194 if (!isa<SCEVUDivExpr>(Div) &&
getMulExpr(Div, RHSC) == Op) {
2203 if (
const SCEVAddExpr *
A = dyn_cast<SCEVAddExpr>(LHS)) {
2205 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i)
2209 for (
unsigned i = 0, e =
A->getNumOperands(); i != e; ++i) {
2211 if (isa<SCEVUDivExpr>(Op) ||
2216 if (Operands.
size() ==
A->getNumOperands())
2222 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
2223 Constant *LHSCV = LHSC->getValue();
2224 Constant *RHSCV = RHSC->getValue();
2236 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2239 UniqueSCEVs.InsertNode(S, IP);
2251 if (
const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
2252 if (StepChrec->getLoop() == L) {
2253 Operands.
append(StepChrec->op_begin(), StepChrec->op_end());
2266 if (Operands.
size() == 1)
return Operands[0];
2269 for (
unsigned i = 1, e = Operands.
size(); i != e; ++i)
2271 "SCEVAddRecExpr operand types don't match!");
2272 for (
unsigned i = 0, e = Operands.
size(); i != e; ++i)
2274 "SCEVAddRecExpr operand is not loop-invariant!");
2292 if (SignOrUnsignWrap && (SignOrUnsignWrap != SignOrUnsignMask)) {
2295 E = Operands.
end();
I != E; ++
I)
2304 if (
const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) {
2305 const Loop *NestedLoop = NestedAR->getLoop();
2311 NestedAR->op_end());
2312 Operands[0] = NestedAR->getStart();
2316 bool AllInvariant =
true;
2317 for (
unsigned i = 0, e = Operands.
size(); i != e; ++i)
2319 AllInvariant =
false;
2331 AllInvariant =
true;
2332 for (
unsigned i = 0, e = NestedOperands.size(); i != e; ++i)
2334 AllInvariant =
false;
2344 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
2348 Operands[0] = NestedAR;
2356 for (
unsigned i = 0, e = Operands.
size(); i != e; ++i)
2361 static_cast<SCEVAddRecExpr *
>(UniqueSCEVs.FindNodeOrInsertPos(ID, IP));
2364 std::uninitialized_copy(Operands.
begin(), Operands.
end(), O);
2366 O, Operands.
size(), L);
2367 UniqueSCEVs.InsertNode(S, IP);
2383 assert(!Ops.
empty() &&
"Cannot get empty smax!");
2384 if (Ops.
size() == 1)
return Ops[0];
2387 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
2389 "SCEVSMaxExpr operand types don't match!");
2397 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2399 assert(Idx < Ops.
size());
2400 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
2404 RHSC->getValue()->getValue()));
2407 if (Ops.
size() == 1)
return Ops[0];
2408 LHSC = cast<SCEVConstant>(Ops[0]);
2412 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(
true)) {
2415 }
else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(
true)) {
2421 if (Ops.
size() == 1)
return Ops[0];
2430 if (Idx < Ops.
size()) {
2431 bool DeletedSMax =
false;
2432 while (
const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) {
2434 Ops.
append(SMax->op_begin(), SMax->op_end());
2445 for (
unsigned i = 0, e = Ops.
size()-1; i != e; ++i)
2448 if (Ops[i] == Ops[i+1] ||
2457 if (Ops.
size() == 1)
return Ops[0];
2459 assert(!Ops.
empty() &&
"Reduced smax down to nothing!");
2465 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2466 ID.AddPointer(Ops[i]);
2468 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2470 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
2473 UniqueSCEVs.InsertNode(S, IP);
2487 assert(!Ops.
empty() &&
"Cannot get empty umax!");
2488 if (Ops.
size() == 1)
return Ops[0];
2491 for (
unsigned i = 1, e = Ops.
size(); i != e; ++i)
2493 "SCEVUMaxExpr operand types don't match!");
2501 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2503 assert(Idx < Ops.
size());
2504 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
2508 RHSC->getValue()->getValue()));
2511 if (Ops.
size() == 1)
return Ops[0];
2512 LHSC = cast<SCEVConstant>(Ops[0]);
2516 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(
false)) {
2519 }
else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(
false)) {
2525 if (Ops.
size() == 1)
return Ops[0];
2534 if (Idx < Ops.
size()) {
2535 bool DeletedUMax =
false;
2536 while (
const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
2538 Ops.
append(UMax->op_begin(), UMax->op_end());
2549 for (
unsigned i = 0, e = Ops.
size()-1; i != e; ++i)
2552 if (Ops[i] == Ops[i+1] ||
2561 if (Ops.
size() == 1)
return Ops[0];
2563 assert(!Ops.
empty() &&
"Reduced umax down to nothing!");
2569 for (
unsigned i = 0, e = Ops.
size(); i != e; ++i)
2570 ID.AddPointer(Ops[i]);
2572 if (
const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
return S;
2574 std::uninitialized_copy(Ops.
begin(), Ops.
end(), O);
2577 UniqueSCEVs.InsertNode(S, IP);
2605 assert(Ty == IntTy &&
"Effective SCEV type doesn't match");
2639 if (
SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) {
2640 assert(cast<SCEVUnknown>(S)->getValue() == V &&
2641 "Stale SCEVUnknown in uniquing map!");
2646 FirstUnknown = cast<SCEVUnknown>(S);
2647 UniqueSCEVs.InsertNode(S, IP);
2667 assert(
isSCEVable(Ty) &&
"Type is not SCEVable!");
2679 assert(Ty->
isPointerTy() &&
"isSCEVable permitted a non-SCEVable type!");
2688 assert(
isSCEVable(Ty) &&
"Type is not SCEVable!");
2695 assert(Ty->
isPointerTy() &&
"Unexpected non-pointer non-integer type!");
2705 return &CouldNotCompute;
2713 struct FindInvalidSCEVUnknown {
2715 FindInvalidSCEVUnknown() { FindOne =
false; }
2716 bool follow(
const SCEV *S) {
2721 if (!cast<SCEVUnknown>(S)->getValue())
2728 bool isDone()
const {
return FindOne; }
2732 bool ScalarEvolution::checkValidity(
const SCEV *S)
const {
2733 FindInvalidSCEVUnknown F;
2746 if (I != ValueExprMap.
end()) {
2747 const SCEV *S = I->second;
2748 if (checkValidity(S))
2751 ValueExprMap.
erase(I);
2753 const SCEV *S = createSCEV(V);
2784 const SCEV *AllOnes =
2810 "Cannot truncate or zero extend with non-integer arguments!");
2827 "Cannot truncate or zero extend with non-integer arguments!");
2843 "Cannot noop or zero extend with non-integer arguments!");
2845 "getNoopOrZeroExtend cannot truncate!");
2859 "Cannot noop or sign extend with non-integer arguments!");
2861 "getNoopOrSignExtend cannot truncate!");
2876 "Cannot noop or any extend with non-integer arguments!");
2878 "getNoopOrAnyExtend cannot truncate!");
2891 "Cannot truncate or noop with non-integer arguments!");
2893 "getTruncateOrNoop cannot extend!");
2904 const SCEV *PromotedLHS = LHS;
2905 const SCEV *PromotedRHS = RHS;
2920 const SCEV *PromotedLHS = LHS;
2921 const SCEV *PromotedRHS = RHS;
2940 if (
const SCEVCastExpr *Cast = dyn_cast<SCEVCastExpr>(V)) {
2943 else if (
const SCEVNAryExpr *NAry = dyn_cast<SCEVNAryExpr>(V)) {
2944 const SCEV *PtrOp = 0;
2947 if ((*I)->getType()->isPointerTy()) {
2969 Worklist.
push_back(cast<Instruction>(*UI));
2977 ScalarEvolution::ForgetSymbolicName(
Instruction *PN,
const SCEV *SymName) {
2983 while (!Worklist.
empty()) {
2985 if (!Visited.
insert(I))
continue;
2988 ValueExprMap.
find_as(static_cast<Value *>(I));
2989 if (It != ValueExprMap.
end()) {
2990 const SCEV *Old = It->second;
2994 if (Old != SymName && !
hasOperand(Old, SymName))
3004 if (!isa<PHINode>(I) ||
3005 !isa<SCEVUnknown>(Old) ||
3006 (I != PN && Old == SymName)) {
3007 forgetMemoizedResults(Old);
3008 ValueExprMap.
erase(It);
3019 const SCEV *ScalarEvolution::createNodeForPHI(
PHINode *PN) {
3021 if (L->getHeader() == PN->
getParent()) {
3025 Value *BEValueV = 0, *StartValueV = 0;
3031 }
else if (BEValueV != V) {
3035 }
else if (!StartValueV) {
3037 }
else if (StartValueV != V) {
3042 if (BEValueV && StartValueV) {
3045 assert(ValueExprMap.
find_as(PN) == ValueExprMap.
end() &&
3046 "PHI node already processed?");
3058 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) {
3061 unsigned FoundIndex = Add->getNumOperands();
3062 for (
unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
3063 if (Add->getOperand(i) == SymbolicName)
3064 if (FoundIndex == e) {
3069 if (FoundIndex != Add->getNumOperands()) {
3072 for (
unsigned i = 0, e = Add->getNumOperands(); i != e; ++i)
3073 if (i != FoundIndex)
3080 (isa<SCEVAddRecExpr>(Accum) &&
3081 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) {
3086 if (
const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
3087 if (OBO->hasNoUnsignedWrap())
3089 if (OBO->hasNoSignedWrap())
3091 }
else if (
GEPOperator *GEP = dyn_cast<GEPOperator>(BEValueV)) {
3098 if (GEP->isInBounds()) {
3101 const SCEV *Ptr =
getSCEV(GEP->getPointerOperand());
3106 dyn_cast<SubOperator>(BEValueV)) {
3107 if (OBO->hasNoUnsignedWrap())
3109 if (OBO->hasNoSignedWrap())
3125 ForgetSymbolicName(PN, SymbolicName);
3131 dyn_cast<SCEVAddRecExpr>(BEValue)) {
3137 if (AddRec->getLoop() == L && AddRec->isAffine()) {
3143 AddRec->getOperand(1))) {
3146 const SCEV *PHISCEV =
3153 ForgetSymbolicName(PN, SymbolicName);
3181 if (!Base->getType()->getPointerElementType()->isSized())
3197 if (
StructType *STy = dyn_cast<StructType>(*GTI++)) {
3199 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
3203 TotalOffset =
getAddExpr(TotalOffset, FieldOffset);
3215 TotalOffset =
getAddExpr(TotalOffset, LocalOffset);
3233 return C->getValue()->getValue().countTrailingZeros();
3254 for (
unsigned i = 1, e =
A->getNumOperands(); MinOpRes && i != e; ++i)
3259 if (
const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
3263 for (
unsigned i = 1, e = M->getNumOperands();
3264 SumOpRes != BitWidth && i != e; ++i)
3273 for (
unsigned i = 1, e =
A->getNumOperands(); MinOpRes && i != e; ++i)
3278 if (
const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
3281 for (
unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
3286 if (
const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
3289 for (
unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
3294 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
3297 APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
3299 return Zeros.countTrailingOnes();
3312 if (I != UnsignedRanges.end())
3325 ConservativeResult =
3329 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
3331 for (
unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
3333 return setUnsignedRange(Add, ConservativeResult.intersectWith(X));
3336 if (
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
3338 for (
unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
3340 return setUnsignedRange(Mul, ConservativeResult.intersectWith(X));
3343 if (
const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
3345 for (
unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
3347 return setUnsignedRange(SMax, ConservativeResult.intersectWith(X));
3350 if (
const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
3352 for (
unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
3354 return setUnsignedRange(UMax, ConservativeResult.intersectWith(X));
3357 if (
const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
3360 return setUnsignedRange(UDiv, ConservativeResult.intersectWith(X.
udiv(Y)));
3365 return setUnsignedRange(ZExt,
3366 ConservativeResult.intersectWith(X.
zeroExtend(BitWidth)));
3371 return setUnsignedRange(SExt,
3372 ConservativeResult.intersectWith(X.
signExtend(BitWidth)));
3377 return setUnsignedRange(Trunc,
3378 ConservativeResult.intersectWith(X.
truncate(BitWidth)));
3381 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
3385 if (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(AddRec->getStart()))
3386 if (!
C->getValue()->isZero())
3387 ConservativeResult =
3388 ConservativeResult.intersectWith(
3392 if (AddRec->isAffine()) {
3393 Type *Ty = AddRec->getType();
3395 if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
3399 const SCEV *Start = AddRec->getStart();
3400 const SCEV *Step = AddRec->getStepRecurrence(*
this);
3406 StartRange.
add(MaxBECountRange.
multiply(StepRange));
3416 if (ExtStartRange.
add(ExtMaxBECountRange.
multiply(ExtStepRange)) !=
3418 return setUnsignedRange(AddRec, ConservativeResult);
3425 return setUnsignedRange(AddRec, ConservativeResult);
3426 return setUnsignedRange(AddRec,
3427 ConservativeResult.intersectWith(
ConstantRange(Min, Max+1)));
3431 return setUnsignedRange(AddRec, ConservativeResult);
3434 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
3436 APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
3438 if (Ones == ~Zeros + 1)
3439 return setUnsignedRange(U, ConservativeResult);
3440 return setUnsignedRange(U,
3441 ConservativeResult.intersectWith(
ConstantRange(Ones, ~Zeros + 1)));
3444 return setUnsignedRange(S, ConservativeResult);
3453 if (I != SignedRanges.end())
3466 ConservativeResult =
3470 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
3472 for (
unsigned i = 1, e = Add->getNumOperands(); i != e; ++i)
3474 return setSignedRange(Add, ConservativeResult.intersectWith(X));
3477 if (
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
3479 for (
unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i)
3481 return setSignedRange(Mul, ConservativeResult.intersectWith(X));
3484 if (
const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) {
3486 for (
unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i)
3488 return setSignedRange(SMax, ConservativeResult.intersectWith(X));
3491 if (
const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) {
3493 for (
unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i)
3495 return setSignedRange(UMax, ConservativeResult.intersectWith(X));
3498 if (
const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) {
3501 return setSignedRange(UDiv, ConservativeResult.intersectWith(X.
udiv(Y)));
3506 return setSignedRange(ZExt,
3507 ConservativeResult.intersectWith(X.
zeroExtend(BitWidth)));
3512 return setSignedRange(SExt,
3513 ConservativeResult.intersectWith(X.
signExtend(BitWidth)));
3518 return setSignedRange(Trunc,
3519 ConservativeResult.intersectWith(X.
truncate(BitWidth)));
3522 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
3526 bool AllNonNeg =
true;
3527 bool AllNonPos =
true;
3528 for (
unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
3533 ConservativeResult = ConservativeResult.intersectWith(
3537 ConservativeResult = ConservativeResult.intersectWith(
3539 APInt(BitWidth, 1)));
3543 if (AddRec->isAffine()) {
3544 Type *Ty = AddRec->getType();
3546 if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
3550 const SCEV *Start = AddRec->getStart();
3551 const SCEV *Step = AddRec->getStepRecurrence(*
this);
3557 StartRange.
add(MaxBECountRange.
multiply(StepRange));
3567 if (ExtStartRange.
add(ExtMaxBECountRange.
multiply(ExtStepRange)) !=
3569 return setSignedRange(AddRec, ConservativeResult);
3576 return setSignedRange(AddRec, ConservativeResult);
3577 return setSignedRange(AddRec,
3578 ConservativeResult.intersectWith(
ConstantRange(Min, Max+1)));
3582 return setSignedRange(AddRec, ConservativeResult);
3585 if (
const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
3587 if (!U->getValue()->getType()->isIntegerTy() && !TD)
3588 return setSignedRange(U, ConservativeResult);
3591 return setSignedRange(U, ConservativeResult);
3592 return setSignedRange(U, ConservativeResult.intersectWith(
3597 return setSignedRange(S, ConservativeResult);
3603 const SCEV *ScalarEvolution::createSCEV(
Value *V) {
3607 unsigned Opcode = Instruction::UserOp1;
3617 }
else if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
3618 Opcode = CE->getOpcode();
3619 else if (
ConstantInt *CI = dyn_cast<ConstantInt>(V))
3621 else if (isa<ConstantPointerNull>(V))
3623 else if (
GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
3630 case Instruction::Add: {
3647 if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
3649 U = cast<Operator>(Op);
3651 if (Opcode == Instruction::Sub)
3659 case Instruction::Mul: {
3666 U = cast<Operator>(Op);
3672 case Instruction::UDiv:
3675 case Instruction::Sub:
3682 if (CI->isNullValue())
3684 if (CI->isAllOnesValue())
3686 const APInt &
A = CI->getValue();
3694 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
3699 if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask))
3716 const APInt &CIVal = CI->getValue();
3718 (CIVal.getBitWidth() - CIVal.countLeadingZeros())) {
3736 if (CI->getValue().isSignBit())
3741 if (CI->isAllOnesValue())
3749 if (
ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1)))
3751 LCI->getValue() == CI->getValue())
3755 const SCEV *Z0 = Z->getOperand();
3768 APInt Trunc = CI->getValue().
trunc(Z0TySize);
3777 case Instruction::Shl:
3786 if (SA->getValue().uge(BitWidth))
3795 case Instruction::LShr:
3804 if (SA->getValue().uge(BitWidth))
3813 case Instruction::AShr:
3817 if (L->getOpcode() == Instruction::Shl &&
3825 if (CI->getValue().uge(BitWidth))
3828 uint64_t Amt = BitWidth - CI->getZExtValue();
3829 if (Amt == BitWidth)
3830 return getSCEV(L->getOperand(0));
3839 case Instruction::Trunc:
3842 case Instruction::ZExt:
3845 case Instruction::SExt:
3848 case Instruction::BitCast:
3859 case Instruction::GetElementPtr:
3860 return createNodeForGEP(cast<GEPOperator>(U));
3863 return createNodeForPHI(cast<PHINode>(U));
3869 Value *LHS = ICI->getOperand(0);
3870 Value *RHS = ICI->getOperand(1);
3871 switch (ICI->getPredicate()) {
3921 isa<ConstantInt>(RHS) &&
3922 cast<ConstantInt>(RHS)->isZero()) {
3936 isa<ConstantInt>(RHS) &&
3937 cast<ConstantInt>(RHS)->isZero()) {
4025 if (
const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(TCMul))
4026 TCMul = Mul->getOperand(0);
4048 return getBackedgeTakenInfo(L).getExact(ExitingBlock,
this);
4063 return getBackedgeTakenInfo(L).getExact(
this);
4070 return getBackedgeTakenInfo(L).getMax(
this);
4085 const ScalarEvolution::BackedgeTakenInfo &
4086 ScalarEvolution::getBackedgeTakenInfo(
const Loop *L) {
4092 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator,
bool> Pair =
4093 BackedgeTakenCounts.insert(std::make_pair(L, BackedgeTakenInfo()));
4095 return Pair.first->second;
4100 BackedgeTakenInfo Result = ComputeBackedgeTakenCount(L);
4105 "Computed backedge-taken count isn't loop invariant for loop!");
4106 ++NumTripCountsComputed;
4109 isa<PHINode>(L->
getHeader()->begin())) {
4111 ++NumTripCountsNotComputed;
4119 if (Result.hasAnyInfo()) {
4124 while (!Worklist.
empty()) {
4126 if (!Visited.
insert(I))
continue;
4129 ValueExprMap.
find_as(static_cast<Value *>(I));
4130 if (It != ValueExprMap.
end()) {
4131 const SCEV *Old = It->second;
4139 if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
4140 forgetMemoizedResults(Old);
4141 ValueExprMap.
erase(It);
4143 if (
PHINode *PN = dyn_cast<PHINode>(I))
4144 ConstantEvolutionLoopExitValue.erase(PN);
4156 return BackedgeTakenCounts.find(L)->second = Result;
4165 BackedgeTakenCounts.find(L);
4166 if (BTCPos != BackedgeTakenCounts.end()) {
4167 BTCPos->second.clear();
4168 BackedgeTakenCounts.erase(BTCPos);
4176 while (!Worklist.
empty()) {
4178 if (!Visited.
insert(I))
continue;
4181 ValueExprMap.
find_as(static_cast<Value *>(I));
4182 if (It != ValueExprMap.
end()) {
4183 forgetMemoizedResults(It->second);
4184 ValueExprMap.
erase(It);
4185 if (
PHINode *PN = dyn_cast<PHINode>(I))
4186 ConstantEvolutionLoopExitValue.erase(PN);
4210 while (!Worklist.
empty()) {
4212 if (!Visited.
insert(I))
continue;
4215 ValueExprMap.
find_as(static_cast<Value *>(I));
4216 if (It != ValueExprMap.
end()) {
4217 forgetMemoizedResults(It->second);
4218 ValueExprMap.
erase(It);
4219 if (
PHINode *PN = dyn_cast<PHINode>(I))
4220 ConstantEvolutionLoopExitValue.erase(PN);
4236 ScalarEvolution::BackedgeTakenInfo::getExact(ScalarEvolution *SE)
const {
4242 assert(ExitNotTaken.ExactNotTaken &&
"uninitialized not-taken info");
4244 const SCEV *BECount = 0;
4245 for (
const ExitNotTakenInfo *ENT = &ExitNotTaken;
4246 ENT != 0; ENT = ENT->getNextExit()) {
4251 BECount = ENT->ExactNotTaken;
4252 else if (BECount != ENT->ExactNotTaken)
4255 assert(BECount &&
"Invalid not taken count for loop exit");
4261 ScalarEvolution::BackedgeTakenInfo::getExact(
BasicBlock *ExitingBlock,
4262 ScalarEvolution *SE)
const {
4263 for (
const ExitNotTakenInfo *ENT = &ExitNotTaken;
4264 ENT != 0; ENT = ENT->getNextExit()) {
4266 if (ENT->ExitingBlock == ExitingBlock)
4267 return ENT->ExactNotTaken;
4274 ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE)
const {
4278 bool ScalarEvolution::BackedgeTakenInfo::hasOperand(
const SCEV *S,
4279 ScalarEvolution *SE)
const {
4283 if (!ExitNotTaken.ExitingBlock)
4286 for (
const ExitNotTakenInfo *ENT = &ExitNotTaken;
4287 ENT != 0; ENT = ENT->getNextExit()) {
4299 ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
4301 bool Complete,
const SCEV *MaxCount) : Max(MaxCount) {
4304 ExitNotTaken.setIncomplete();
4306 unsigned NumExits = ExitCounts.size();
4307 if (NumExits == 0)
return;
4309 ExitNotTaken.ExitingBlock = ExitCounts[0].first;
4310 ExitNotTaken.ExactNotTaken = ExitCounts[0].second;
4311 if (NumExits == 1)
return;
4314 ExitNotTakenInfo *ENT =
new ExitNotTakenInfo[NumExits-1];
4316 ExitNotTakenInfo *PrevENT = &ExitNotTaken;
4317 for (
unsigned i = 1; i < NumExits; ++i, PrevENT = ENT, ++ENT) {
4318 PrevENT->setNextExit(ENT);
4319 ENT->ExitingBlock = ExitCounts[i].first;
4320 ENT->ExactNotTaken = ExitCounts[i].second;
4325 void ScalarEvolution::BackedgeTakenInfo::clear() {
4326 ExitNotTaken.ExitingBlock = 0;
4327 ExitNotTaken.ExactNotTaken = 0;
4328 delete[] ExitNotTaken.getNextExit();
4333 ScalarEvolution::BackedgeTakenInfo
4334 ScalarEvolution::ComputeBackedgeTakenCount(
const Loop *L) {
4340 bool CouldComputeBECount =
true;
4342 for (
unsigned i = 0, e = ExitingBlocks.
size(); i != e; ++i) {
4343 ExitLimit EL = ComputeExitLimit(L, ExitingBlocks[i]);
4347 CouldComputeBECount =
false;
4349 ExitCounts.
push_back(std::make_pair(ExitingBlocks[i], EL.Exact));
4352 MaxBECount = EL.Max;
4364 return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
4369 ScalarEvolution::ExitLimit
4370 ScalarEvolution::ComputeExitLimit(
const Loop *L,
BasicBlock *ExitingBlock) {
4378 assert(ExitBr->
isConditional() &&
"If unconditional, it can't be in loop!");
4428 return ComputeExitLimitFromCond(L, ExitBr->
getCondition(),
4442 ScalarEvolution::ExitLimit
4443 ScalarEvolution::ComputeExitLimitFromCond(
const Loop *L,
4452 bool EitherMayExit = L->
contains(TBB);
4453 ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
4454 IsSubExpr || EitherMayExit);
4455 ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
4456 IsSubExpr || EitherMayExit);
4459 if (EitherMayExit) {
4468 MaxBECount = EL1.Max;
4470 MaxBECount = EL0.Max;
4476 assert(L->
contains(FBB) &&
"Loop block has no successor in loop!");
4477 if (EL0.Max == EL1.Max)
4478 MaxBECount = EL0.Max;
4479 if (EL0.Exact == EL1.Exact)
4480 BECount = EL0.Exact;
4483 return ExitLimit(BECount, MaxBECount);
4487 bool EitherMayExit = L->
contains(FBB);
4488 ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
4489 IsSubExpr || EitherMayExit);
4490 ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
4491 IsSubExpr || EitherMayExit);
4494 if (EitherMayExit) {
4503 MaxBECount = EL1.Max;
4505 MaxBECount = EL0.Max;
4511 assert(L->
contains(TBB) &&
"Loop block has no successor in loop!");
4512 if (EL0.Max == EL1.Max)
4513 MaxBECount = EL0.Max;
4514 if (EL0.Exact == EL1.Exact)
4515 BECount = EL0.Exact;
4518 return ExitLimit(BECount, MaxBECount);
4524 if (
ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
4525 return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, IsSubExpr);
4531 if (
ConstantInt *CI = dyn_cast<ConstantInt>(ExitCond)) {
4532 if (L->
contains(FBB) == !CI->getZExtValue())
4541 return ComputeExitCountExhaustively(L, ExitCond, !L->
contains(TBB));
4547 ScalarEvolution::ExitLimit
4548 ScalarEvolution::ComputeExitLimitFromICmp(
const Loop *L,
4565 ComputeLoadConstantCompareExitLimit(LI, RHS, L, Cond);
4566 if (ItCnt.hasAnyInfo())
4590 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
4591 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
4592 if (AddRec->getLoop() == L) {
4597 const SCEV *
Ret = AddRec->getNumIterationsInRange(CompRange, *
this);
4598 if (!isa<SCEVCouldNotCompute>(Ret))
return Ret;
4604 ExitLimit EL = HowFarToZero(
getMinusSCEV(LHS, RHS), L, IsSubExpr);
4605 if (EL.hasAnyInfo())
return EL;
4610 ExitLimit EL = HowFarToNonZero(
getMinusSCEV(LHS, RHS), L);
4611 if (EL.hasAnyInfo())
return EL;
4617 ExitLimit EL = HowManyLessThans(LHS, RHS, L, IsSigned, IsSubExpr);
4618 if (EL.hasAnyInfo())
return EL;
4624 ExitLimit EL = HowManyGreaterThans(LHS, RHS, L, IsSigned, IsSubExpr);
4625 if (EL.hasAnyInfo())
return EL;
4630 dbgs() <<
"ComputeBackedgeTakenCount ";
4632 dbgs() <<
"[unsigned] ";
4633 dbgs() << *LHS <<
" "
4635 <<
" " << *RHS <<
"\n";
4639 return ComputeExitCountExhaustively(L, ExitCond, !L->
contains(TBB));
4644 ScalarEvolution &SE) {
4647 assert(isa<SCEVConstant>(Val) &&
4648 "Evaluation of SCEV at constant didn't fold correctly?");
4649 return cast<SCEVConstant>(Val)->getValue();
4655 ScalarEvolution::ExitLimit
4656 ScalarEvolution::ComputeLoadConstantCompareExitLimit(
4674 !cast<Constant>(GEP->
getOperand(1))->isNullValue())
4679 std::vector<Constant*> Indexes;
4680 unsigned VarIdxNum = 0;
4683 Indexes.push_back(CI);
4684 }
else if (!isa<ConstantInt>(GEP->
getOperand(i))) {
4688 Indexes.push_back(0);
4704 !isa<SCEVConstant>(IdxExpr->
getOperand(0)) ||
4709 for (
unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
4711 cast<IntegerType>(IdxExpr->
getType()), IterationNum);
4715 Indexes[VarIdxNum] = Val;
4719 if (Result == 0)
break;
4723 if (!isa<ConstantInt>(Result))
break;
4724 if (cast<ConstantInt>(Result)->getValue().isMinValue()) {
4726 dbgs() <<
"\n***\n*** Computed loop count " << *ItCst
4727 <<
"\n*** From global " << *GV <<
"*** BB: " << *L->
getHeader()
4730 ++NumArrayLenItCounts;
4741 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
4742 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) ||
4746 if (
const CallInst *CI = dyn_cast<CallInst>(I))
4747 if (
const Function *F = CI->getCalledFunction())
4758 if (isa<PHINode>(I)) {
4782 OpE = UseInst->
op_end(); OpI != OpE; ++OpI) {
4784 if (isa<Constant>(*OpI))
continue;
4794 P = PHIMap.
lookup(OpInst);
4801 if (P == 0)
return 0;
4802 if (PHI && PHI != P)
return 0;
4818 if (
PHINode *PN = dyn_cast<PHINode>(I)) {
4836 if (
Constant *
C = dyn_cast<Constant>(V))
return C;
4849 if (isa<PHINode>(I))
return 0;
4857 if (!Operands[i])
return 0;
4866 if (
CmpInst *CI = dyn_cast<CmpInst>(I))
4868 Operands[1],
TD, TLI);
4869 if (
LoadInst *LI = dyn_cast<LoadInst>(I)) {
4882 ScalarEvolution::getConstantEvolutionLoopExitValue(
PHINode *PN,
4886 ConstantEvolutionLoopExitValue.find(PN);
4887 if (I != ConstantEvolutionLoopExitValue.end())
4891 return ConstantEvolutionLoopExitValue[PN] = 0;
4893 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN];
4897 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
4908 if (StartCST == 0)
continue;
4909 CurrentIterVals[
PHI] = StartCST;
4911 if (!CurrentIterVals.
count(PN))
4921 unsigned IterationNum = 0;
4922 for (; ; ++IterationNum) {
4923 if (IterationNum == NumIterations)
4924 return RetVal = CurrentIterVals[PN];
4933 NextIterVals[PN] = NextPHI;
4935 bool StoppedEvolving = NextPHI == CurrentIterVals[PN];
4942 I = CurrentIterVals.
begin(), E = CurrentIterVals.
end(); I != E; ++
I){
4944 if (!PHI || PHI == PN || PHI->
getParent() != Header)
continue;
4945 PHIsToCompute.
push_back(std::make_pair(PHI, I->second));
4949 for (
SmallVectorImpl<std::pair<PHINode *, Constant*> >::const_iterator
4950 I = PHIsToCompute.
begin(), E = PHIsToCompute.
end(); I != E; ++
I) {
4957 if (NextPHI != I->second)
4958 StoppedEvolving =
false;
4963 if (StoppedEvolving)
4964 return RetVal = CurrentIterVals[PN];
4966 CurrentIterVals.
swap(NextIterVals);
4975 const SCEV *ScalarEvolution::ComputeExitCountExhaustively(
const Loop *L,
4987 assert(PN->
getParent() == Header &&
"Can't evaluate PHI not in loop header!");
4997 if (StartCST == 0)
continue;
4998 CurrentIterVals[
PHI] = StartCST;
5000 if (!CurrentIterVals.
count(PN))
5008 for (
unsigned IterationNum = 0; IterationNum !=
MaxIterations;++IterationNum){
5016 if (CondVal->
getValue() == uint64_t(ExitWhen)) {
5017 ++NumBruteForceTripCountsComputed;
5029 I = CurrentIterVals.
begin(), E = CurrentIterVals.
end(); I != E; ++
I){
5031 if (!PHI || PHI->
getParent() != Header)
continue;
5035 E = PHIsToCompute.
end(); I != E; ++
I) {
5038 if (NextPHI)
continue;
5043 CurrentIterVals.
swap(NextIterVals);
5063 for (
unsigned u = 0; u < Values.
size(); u++) {
5064 if (Values[u].first == L)
5065 return Values[u].second ? Values[u].second : V;
5067 Values.
push_back(std::make_pair(L, static_cast<const SCEV *>(0)));
5069 const SCEV *
C = computeSCEVAtScope(V, L);
5071 for (
unsigned u = Values2.
size(); u > 0; u--) {
5072 if (Values2[u - 1].first == L) {
5073 Values2[u - 1].second =
C;
5091 return cast<SCEVConstant>(V)->getValue();
5115 if (
PointerType *PTy = dyn_cast<PointerType>(
C->getType())) {
5116 unsigned AS = PTy->getAddressSpace();
5139 if (
PointerType *PTy = dyn_cast<PointerType>(
C->getType())) {
5140 if (PTy->getElementType()->isStructTy())
5155 if (
C->getType()->isPointerTy())
return 0;
5169 if (LHS->getType() == RHS->
getType())
5177 const SCEV *ScalarEvolution::computeSCEVAtScope(
const SCEV *V,
const Loop *L) {
5178 if (isa<SCEVConstant>(V))
return V;
5182 if (
const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
5183 if (
Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
5184 const Loop *LI = (*this->LI)[I->getParent()];
5186 if (
PHINode *PN = dyn_cast<PHINode>(I))
5194 dyn_cast<SCEVConstant>(BackedgeTakenCount)) {
5198 Constant *RV = getConstantEvolutionLoopExitValue(PN,
5199 BTCC->getValue()->getValue(),
5211 bool MadeImprovement =
false;
5212 for (
unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
5213 Value *Op = I->getOperand(i);
5214 if (
Constant *
C = dyn_cast<Constant>(Op)) {
5227 MadeImprovement |= OrigV != OpV;
5240 if (MadeImprovement) {
5242 if (
const CmpInst *CI = dyn_cast<CmpInst>(I))
5244 Operands[0], Operands[1], TD,
5246 else if (
const LoadInst *LI = dyn_cast<LoadInst>(I)) {
5247 if (!LI->isVolatile())
5265 for (
unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) {
5267 if (OpAtScope != Comm->getOperand(i)) {
5271 Comm->op_begin()+i);
5274 for (++i; i != e; ++i) {
5276 NewOps.push_back(OpAtScope);
5278 if (isa<SCEVAddExpr>(Comm))
5280 if (isa<SCEVMulExpr>(Comm))
5282 if (isa<SCEVSMaxExpr>(Comm))
5284 if (isa<SCEVUMaxExpr>(Comm))
5293 if (
const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) {
5296 if (LHS == Div->getLHS() && RHS == Div->getRHS())
5303 if (
const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) {
5307 for (
unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) {
5309 if (OpAtScope == AddRec->getOperand(i))
5315 AddRec->op_begin()+i);
5317 for (++i; i != e; ++i)
5320 const SCEV *FoldedRec =
5334 if (!AddRec->getLoop()->contains(L)) {
5341 return AddRec->evaluateAtIteration(BackedgeTakenCount, *
this);
5349 if (Op == Cast->getOperand())
5356 if (Op == Cast->getOperand())
5363 if (Op == Cast->getOperand())
5387 ScalarEvolution &SE) {
5389 assert(BW == B.
getBitWidth() &&
"Bit widths must be the same.");
5390 assert(A != 0 &&
"A must be non-zero.");
5412 APInt Mod(BW + 1, 0);
5429 static std::pair<const SCEV *,const SCEV *>
5431 assert(AddRec->
getNumOperands() == 3 &&
"This is not a quadratic chrec!");
5437 if (!LC || !MC || !NC) {
5439 return std::make_pair(CNC, CNC);
5442 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth();
5443 const APInt &L = LC->getValue()->getValue();
5444 const APInt &M = MC->getValue()->getValue();
5445 const APInt &
N = NC->getValue()->getValue();
5446 APInt Two(BitWidth, 2);
5447 APInt Four(BitWidth, 4);
5450 using namespace APIntOps;
5463 SqrtTerm -= Four * (A *
C);
5465 if (SqrtTerm.isNegative()) {
5468 return std::make_pair(CNC, CNC);
5473 APInt SqrtVal(SqrtTerm.sqrt());
5481 return std::make_pair(CNC, CNC);
5503 ScalarEvolution::ExitLimit
5504 ScalarEvolution::HowFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr) {
5506 if (
const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
5508 if (C->getValue()->isZero())
return C;
5513 if (!AddRec || AddRec->
getLoop() != L)
5519 std::pair<const SCEV *,const SCEV *> Roots =
5525 dbgs() <<
"HFTZ: " << *V <<
" - sol#1: " << *R1
5526 <<
" sol#2: " << *R2 <<
"\n";
5533 if (CB->getZExtValue() ==
false)
5573 if (StepC == 0 || StepC->getValue()->equalsInt(0))
5581 bool CountDown = StepC->getValue()->getValue().isNegative();
5587 if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) {
5589 const SCEV *MaxBECount;
5598 return ExitLimit(Distance, MaxBECount);
5617 if (
const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
5619 -StartC->getValue()->getValue(),
5627 ScalarEvolution::ExitLimit
5628 ScalarEvolution::HowFarToNonZero(
const SCEV *V,
const Loop *L) {
5635 if (
const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
5651 std::pair<BasicBlock *, BasicBlock *>
5652 ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(
BasicBlock *BB) {
5657 return std::make_pair(Pred, BB);
5662 if (
Loop *L = LI->getLoopFor(BB))
5665 return std::pair<BasicBlock *, BasicBlock *>();
5676 if (A == B)
return true;
5680 if (
const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A))
5681 if (
const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
5682 if (
const Instruction *AI = dyn_cast<Instruction>(AU->getValue()))
5683 if (
const Instruction *BI = dyn_cast<Instruction>(BU->getValue()))
5684 if (AI->isIdenticalTo(BI) && !AI->mayReadFromMemory())
5695 const SCEV *&LHS,
const SCEV *&RHS,
5697 bool Changed =
false;
5704 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) {
5706 if (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) {
5709 RHSC->getValue())->isNullValue())
5710 goto trivially_false;
5712 goto trivially_true;
5724 const Loop *L = AR->getLoop();
5734 if (
const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS)) {
5735 const APInt &RA = RC->getValue()->getValue();
5742 if (
const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(LHS))
5743 if (
const SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(AE->getOperand(0)))
5744 if (AE->getNumOperands() == 2 && ME->getNumOperands() == 2 &&
5745 ME->getOperand(0)->isAllOnesValue()) {
5746 RHS = AE->getOperand(1);
5747 LHS = ME->getOperand(1);
5752 if ((RA - 1).isMinValue()) {
5770 if ((RA + 1).isMaxValue()) {
5788 if ((RA - 1).isMinSignedValue()) {
5806 if ((RA + 1).isMaxSignedValue()) {
5829 if ((RA + 1).isMaxValue()) {
5843 if ((RA - 1).isMinValue()) {
5857 if ((RA + 1).isMaxSignedValue()) {
5871 if ((RA - 1).isMinSignedValue()) {
5885 goto trivially_true;
5887 goto trivially_false;
5899 }
else if (!
getSignedRange(LHS).getSignedMin().isMinSignedValue()) {
5992 const SCEV *LHS,
const SCEV *RHS) {
6000 AR->getLoop(), Pred, AR->getStart(), RHS) &&
6002 AR->getLoop(), Pred, AR->getPostIncExpr(*
this), RHS))
6006 AR->getLoop(), Pred, LHS, AR->getStart()) &&
6008 AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*
this)))
6012 return isKnownPredicateWithRanges(Pred, LHS, RHS);
6017 const SCEV *LHS,
const SCEV *RHS) {
6099 const SCEV *LHS,
const SCEV *RHS) {
6102 if (!L)
return true;
6110 if (!LoopContinuePredicate ||
6114 return isImpliedCond(Pred, LHS, RHS,
6125 const SCEV *LHS,
const SCEV *RHS) {
6128 if (!L)
return false;
6133 for (std::pair<BasicBlock *, BasicBlock *>
6136 Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) {
6140 if (!LoopEntryPredicate ||
6144 if (isImpliedCond(Pred, LHS, RHS,
6162 : Cond(C), LoopPreds(LP) {
6163 Pending = !LoopPreds.insert(Cond).second;
6167 LoopPreds.erase(Cond);
6175 Value *FoundCondValue,
6182 if (
BinaryOperator *BO = dyn_cast<BinaryOperator>(FoundCondValue)) {
6185 return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
6186 isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
6189 return isImpliedCond(Pred, LHS, RHS, BO->getOperand(0), Inverse) ||
6190 isImpliedCond(Pred, LHS, RHS, BO->getOperand(1), Inverse);
6195 if (!ICI)
return false;
6236 if (FoundLHS == FoundRHS)
6240 if (LHS == FoundRHS || RHS == FoundLHS) {
6241 if (isa<SCEVConstant>(RHS)) {
6251 if (FoundPred == Pred)
6252 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS);
6257 if (isa<SCEVConstant>(RHS))
6258 return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS);
6261 RHS, LHS, FoundLHS, FoundRHS);
6267 if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS))
6271 if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS))
6283 const SCEV *FoundLHS,
6284 const SCEV *FoundRHS) {
6285 return isImpliedCondOperandsHelper(Pred, LHS, RHS,
6286 FoundLHS, FoundRHS) ||
6288 isImpliedCondOperandsHelper(Pred, LHS, RHS,
6299 const SCEV *FoundLHS,
6300 const SCEV *FoundRHS) {
6340 bool ScalarEvolution::doesIVOverflowOnLT(
const SCEV *RHS,
const SCEV *Stride,
6341 bool IsSigned,
bool NoWrap) {
6342 if (NoWrap)
return false;
6354 return (MaxValue - MaxStrideMinusOne).
slt(MaxRHS);
6363 return (MaxValue - MaxStrideMinusOne).
ult(MaxRHS);
6369 bool ScalarEvolution::doesIVOverflowOnGT(
const SCEV *RHS,
const SCEV *Stride,
6370 bool IsSigned,
bool NoWrap) {
6371 if (NoWrap)
return false;
6383 return (MinValue + MaxStrideMinusOne).
sgt(MinRHS);
6392 return (MinValue + MaxStrideMinusOne).
ugt(MinRHS);
6397 const SCEV *ScalarEvolution::computeBECount(
const SCEV *Delta,
const SCEV *Step,
6412 ScalarEvolution::ExitLimit
6413 ScalarEvolution::HowManyLessThans(
const SCEV *LHS,
const SCEV *RHS,
6414 const Loop *L,
bool IsSigned,
6426 bool NoWrap = !IsSubExpr &&
6439 if (!Stride->
isOne() && doesIVOverflowOnLT(RHS, Stride, IsSigned, NoWrap))
6445 const SCEV *End = RHS;
6450 const SCEV *BECount = computeBECount(
getMinusSCEV(End, Start), Stride,
false);
6470 if (isa<SCEVConstant>(BECount))
6471 MaxBECount = BECount;
6473 MaxBECount = computeBECount(
getConstant(MaxEnd - MinStart),
6476 if (isa<SCEVCouldNotCompute>(MaxBECount))
6477 MaxBECount = BECount;
6479 return ExitLimit(BECount, MaxBECount);
6482 ScalarEvolution::ExitLimit
6483 ScalarEvolution::HowManyGreaterThans(
const SCEV *LHS,
const SCEV *RHS,
6484 const Loop *L,
bool IsSigned,
6496 bool NoWrap = !IsSubExpr &&
6509 if (!Stride->
isOne() && doesIVOverflowOnGT(RHS, Stride, IsSigned, NoWrap))
6516 const SCEV *End = RHS;
6521 const SCEV *BECount = computeBECount(
getMinusSCEV(Start, End), Stride,
false);
6542 if (isa<SCEVConstant>(BECount))
6543 MaxBECount = BECount;
6545 MaxBECount = computeBECount(
getConstant(MaxStart - MinEnd),
6548 if (isa<SCEVCouldNotCompute>(MaxBECount))
6549 MaxBECount = BECount;
6551 return ExitLimit(BECount, MaxBECount);
6560 ScalarEvolution &SE)
const {
6566 if (!
SC->getValue()->isZero()) {
6572 dyn_cast<SCEVAddRecExpr>(Shifted))
6573 return ShiftedAddRec->getNumIterationsInRange(
6574 Range.
subtract(
SC->getValue()->getValue()), SE);
6603 APInt One(BitWidth,1);
6615 if (Range.
contains(Val->getValue()))
6622 "Linear scev computation is off in a bad way!");
6636 std::pair<const SCEV *,const SCEV *> Roots =
6645 if (CB->getZExtValue() ==
false)
6660 if (!Range.
contains(R1Val->getValue()))
6670 if (Range.
contains(R1Val->getValue()))
6723 struct SCEVGCD :
public SCEVVisitor<SCEVGCD, const SCEV *> {
6730 const SCEV *Step,
const SCEV **Remainder) {
6731 assert(Remainder &&
"Remainder should not be NULL");
6733 const SCEV *Res = R.visit(Start);
6734 *Remainder = R.Remainder;
6738 SCEVGCD(ScalarEvolution &S,
const SCEV *
G,
const SCEV *R)
6739 : SE(S), GCD(G), Remainder(R) {
6745 if (GCD == Constant || Constant == Zero)
6748 if (
const SCEVConstant *CGCD = dyn_cast<SCEVConstant>(GCD)) {
6754 Constant = cast<SCEVConstant>(SE.
getMinusSCEV(Constant, Remainder));
6762 const SCEV *Rem = Zero;
6763 const SCEV *Res =
findGCD(SE, GCD, Constant, &Rem);
6765 if (Res == One || Rem != Zero) {
6770 assert(isa<SCEVConstant>(Res) &&
"Res should be a constant");
6798 const SCEV *Rem = Zero;
6824 const SCEV *PartialGCD = One;
6826 const SCEV *Rem = Zero;
6835 if (PartialGCD == GCD)
6839 if (PartialGCD != One)
6851 const SCEV *Rem = Zero;
6877 const SCEV *Rem = Zero;
6915 ScalarEvolution &SE;
6916 const SCEV *GCD, *Remainder, *Zero, *One;
6919 struct SCEVDivision :
public SCEVVisitor<SCEVDivision, const SCEV *> {
6922 static const SCEV *divide(ScalarEvolution &SE,
const SCEV *Start,
6924 SCEVDivision D(SE, Step);
6925 const SCEV *Rem = D.Zero;
6930 "Step should divide Start with no remainder.");
6931 return D.visit(Start);
6934 SCEVDivision(ScalarEvolution &S,
const SCEV *G) : SE(S), GCD(G) {
6940 if (GCD == Constant)
6943 if (
const SCEVConstant *CGCD = dyn_cast<SCEVConstant>(GCD))
6974 if (Operands.
size() == 1)
6983 bool FoundGCDTerm =
false;
6986 FoundGCDTerm =
true;
6990 FoundGCDTerm =
false;
6995 FoundGCDTerm =
true;
7000 FoundGCDTerm =
false;
7001 const SCEV *PartialGCD = One;
7003 if (PartialGCD == GCD) {
7008 const SCEV *Rem = Zero;
7019 if (Operands.
size() == 1)
7034 assert(Expr->
isAffine() &&
"Expr should be affine");
7066 ScalarEvolution &SE;
7067 const SCEV *GCD, *Zero, *One;
7138 DEBUG(
dbgs() <<
"(delinearize: " << *
this <<
"\n");
7144 DEBUG(
dbgs() <<
"failed to delinearize " << *
this <<
"\n)\n");
7149 const SCEV *Remainder = NULL;
7152 DEBUG(
dbgs() <<
"GCD: " << *GCD <<
"\n");
7153 DEBUG(
dbgs() <<
"Remainder: " << *Remainder <<
"\n");
7158 DEBUG(
dbgs() <<
"failed to delinearize " << *
this <<
"\n)\n");
7165 const SCEV *Quotient =
7166 SCEVDivision::divide(SE, SE.
getMinusSCEV(Start, Remainder), GCD);
7167 DEBUG(
dbgs() <<
"Quotient: " << *Quotient <<
"\n");
7170 if (
const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Quotient))
7173 Rem = AR->delinearize(SE, Subscripts, Sizes);
7180 Step = SCEVDivision::divide(SE, Step, GCD);
7193 int Size = Sizes.
size();
7194 DEBUG(
dbgs() <<
"succeeded to delinearize " << *
this <<
"\n");
7195 DEBUG(
dbgs() <<
"ArrayDecl[UnknownSize]");
7196 for (
int i = 0; i < Size - 1; i++)
7197 DEBUG(
dbgs() <<
"[" << *Sizes[i] <<
"]");
7198 DEBUG(
dbgs() <<
" with elements of " << *Sizes[Size - 1] <<
" bytes.\n");
7201 for (
int i = 0; i < Size; i++)
7202 DEBUG(
dbgs() <<
"[" << *Subscripts[i] <<
"]");
7213 void ScalarEvolution::SCEVCallbackVH::deleted() {
7214 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
7215 if (
PHINode *PN = dyn_cast<PHINode>(getValPtr()))
7216 SE->ConstantEvolutionLoopExitValue.erase(PN);
7217 SE->ValueExprMap.
erase(getValPtr());
7221 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(
Value *V) {
7222 assert(SE &&
"SCEVCallbackVH called with a null ScalarEvolution!");
7227 Value *Old = getValPtr();
7233 while (!Worklist.
empty()) {
7241 if (
PHINode *PN = dyn_cast<PHINode>(U))
7242 SE->ConstantEvolutionLoopExitValue.erase(PN);
7243 SE->ValueExprMap.
erase(U);
7249 if (
PHINode *PN = dyn_cast<PHINode>(Old))
7250 SE->ConstantEvolutionLoopExitValue.erase(PN);
7251 SE->ValueExprMap.
erase(Old);
7255 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(
Value *V, ScalarEvolution *se)
7263 :
FunctionPass(ID), ValuesAtScopes(64), LoopDispositions(64), BlockDispositions(64), FirstUnknown(0) {
7269 LI = &getAnalysis<LoopInfo>();
7270 TD = getAnalysisIfAvailable<DataLayout>();
7271 TLI = &getAnalysis<TargetLibraryInfo>();
7272 DT = &getAnalysis<DominatorTree>();
7279 for (
SCEVUnknown *U = FirstUnknown; U; U = U->Next)
7283 ValueExprMap.
clear();
7288 BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end();
7293 assert(PendingLoopPredicates.
empty() &&
"isImpliedCond garbage");
7295 BackedgeTakenCounts.clear();
7296 ConstantEvolutionLoopExitValue.clear();
7297 ValuesAtScopes.clear();
7298 LoopDispositions.clear();
7299 BlockDispositions.clear();
7300 UnsignedRanges.clear();
7301 SignedRanges.clear();
7302 UniqueSCEVs.clear();
7303 SCEVAllocator.
Reset();
7329 if (ExitBlocks.
size() != 1)
7330 OS <<
"<multiple exits> ";
7335 OS <<
"Unpredictable backedge-taken count. ";
7346 OS <<
"Unpredictable max backedge-taken count. ";
7359 ScalarEvolution &SE = *
const_cast<ScalarEvolution *
>(
this);
7361 OS <<
"Classifying expressions for: ";
7365 if (
isSCEVable(I->getType()) && !isa<CmpInst>(*I)) {
7371 const Loop *L = LI->getLoopFor((*I).getParent());
7380 OS <<
"\t\t" "Exits: ";
7383 OS <<
"<<Unknown>>";
7392 OS <<
"Determining loop execution counts for: ";
7402 for (
unsigned u = 0; u < Values.
size(); u++) {
7403 if (Values[u].first == L)
7404 return Values[u].second;
7409 for (
unsigned u = Values2.
size(); u > 0; u--) {
7410 if (Values2[u - 1].first == L) {
7411 Values2[u - 1].second = D;
7419 ScalarEvolution::computeLoopDisposition(
const SCEV *S,
const Loop *L) {
7461 bool HasVarying =
false;
7488 if (
Instruction *I = dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue()))
7508 for (
unsigned u = 0; u < Values.
size(); u++) {
7509 if (Values[u].first == BB)
7510 return Values[u].second;
7515 for (
unsigned u = Values2.
size(); u > 0; u--) {
7516 if (Values2[u - 1].first == BB) {
7517 Values2[u - 1].second = D;
7525 ScalarEvolution::computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB) {
7573 dyn_cast<Instruction>(cast<SCEVUnknown>(S)->getValue())) {
7574 if (I->getParent() == BB)
7603 SCEVSearch(
const SCEV *
N): Node(N), IsFound(false) {}
7605 bool follow(
const SCEV *S) {
7606 IsFound |= (S == Node);
7609 bool isDone()
const {
return IsFound; }
7614 SCEVSearch Search(Op);
7616 return Search.IsFound;
7619 void ScalarEvolution::forgetMemoizedResults(
const SCEV *S) {
7620 ValuesAtScopes.erase(S);
7621 LoopDispositions.erase(S);
7622 BlockDispositions.erase(S);
7623 UnsignedRanges.erase(S);
7624 SignedRanges.erase(S);
7627 BackedgeTakenCounts.begin(), E = BackedgeTakenCounts.end(); I != E; ) {
7628 BackedgeTakenInfo &BEInfo = I->second;
7629 if (BEInfo.hasOperand(S,
this)) {
7631 BackedgeTakenCounts.erase(I++);
7643 while ((Pos = Str.find(From, Pos)) != std::string::npos) {
7655 std::string &S = Map[L];
7675 ScalarEvolution &SE = *
const_cast<ScalarEvolution *
>(
this);
7680 VerifyMap BackedgeDumpsOld, BackedgeDumpsNew;
7692 assert(BackedgeDumpsOld.
size() == BackedgeDumpsNew.
size() &&
7693 "New loops suddenly appeared!");
7696 OldE = BackedgeDumpsOld.
end(),
7697 NewI = BackedgeDumpsNew.
begin();
7698 OldI != OldE; ++OldI, ++NewI) {
7699 assert(OldI->first == NewI->first &&
"Loop order changed!");
7706 if (OldI->second != NewI->second &&
7707 OldI->second.find(
"undef") == std::string::npos &&
7708 NewI->second.find(
"undef") == std::string::npos &&
7709 OldI->second !=
"***COULDNOTCOMPUTE***" &&
7710 NewI->second !=
"***COULDNOTCOMPUTE***") {
7711 dbgs() <<
"SCEVValidator: SCEV for loop '"
7712 << OldI->first->getHeader()->getName()
7713 <<
"' changed from '" << OldI->second
7714 <<
"' to '" << NewI->second <<
"'!\n";
NoWrapFlags getNoWrapFlags(NoWrapFlags Mask=NoWrapMask) const
static const SCEV * getSignExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE)
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
void AddPointer(const void *Ptr)
APInt multiplicativeInverse(const APInt &modulo) const
void push_back(const T &Elt)
APInt getSignedMin() const
static cl::opt< bool > VerifySCEV("verify-scev", cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"))
static ConstantInt * getFalse(LLVMContext &Context)
Abstract base class of comparison instructions.
The SCEV properly dominates the block.
BasicBlock * getUniquePredecessor()
Return this block if it has a unique predecessor block. Otherwise return a null pointer.
APInt LLVM_ATTRIBUTE_UNUSED_RESULT abs() const
Get the absolute value;.
static const SCEV * SolveLinEquationWithOverflow(const APInt &A, const APInt &B, ScalarEvolution &SE)
static PassRegistry * getPassRegistry()
virtual void verifyAnalysis() const
SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy, const SCEV *op, Type *ty)
LLVM Argument representation.
uint64_t getZExtValue() const
Get zero extended value.
const SCEV * getExitCount(Loop *L, BasicBlock *ExitingBlock)
const SCEV * getConstant(ConstantInt *V)
size_t size() const
size - Get the string size.
ConstantRange sextOrTrunc(uint32_t BitWidth) const
APInt GreatestCommonDivisor(const APInt &Val1, const APInt &Val2)
Compute GCD of two APInt values.
bool canConstantFoldCallTo(const Function *F)
The main container class for the LLVM Intermediate Representation.
LLVMContext & getContext() const
LoopInfoBase< BasicBlock, Loop >::iterator iterator
static void PushDefUseChildren(Instruction *I, SmallVectorImpl< Instruction * > &Worklist)
bool isReachableFromEntry(const BasicBlock *A) const
void setBit(unsigned bitPosition)
Set a given bit to 1.
enable_if_c<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
unsigned getNumOperands() const
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow)
static Constant * getGetElementPtr(Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false)
const SCEV * getPointerBase(const SCEV *V)
STATISTIC(NumArrayLenItCounts,"Number of trip counts computed with array length")
uint32_t getBitWidth() const
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Predicate getInversePredicate() const
Return the inverse of the instruction's predicate.
scalar Scalar Evolution false
bool isKnownNonNegative(const SCEV *S)
bool isSigned() const
Determine if this instruction is using a signed comparison.
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
static void PushLoopPHIs(const Loop *L, SmallVectorImpl< Instruction * > &Worklist)
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const
uint32_t GetMinTrailingZeros(const SCEV *S)
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
virtual void print(raw_ostream &OS, const Module *=0) const
APInt getSignedMax() const
bool isMask(unsigned numBits, const APInt &APIVal)
bool isLoopInvariant(const SCEV *S, const Loop *L)
static ConstantInt * EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, ScalarEvolution &SE)
LoopT * getParentLoop() const
const Function * getParent() const
Return the enclosing method, or null if none.
ConstantRange getUnsignedRange(const SCEV *S)
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV *const * Operands
static IntegerType * getInt64Ty(LLVMContext &C)
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static bool HasSameValue(const SCEV *A, const SCEV *B)
const Constant * getInitializer() const
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
BlockT * getHeader() const
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
LoopInfoBase< BlockT, LoopT > * LI
ConstantRange smax(const ConstantRange &Other) const
bool isOffsetOf(Type *&STy, Constant *&FieldNo) const
virtual bool runOnFunction(Function &F)
const SCEV * getStart() const
BlockT * getLoopLatch() const
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
bool isKnownNonPositive(const SCEV *S)
static void getLoopBackedgeTakenCounts(Loop *L, VerifyMap &Map, ScalarEvolution &SE)
getLoopBackedgeTakenCounts - Helper method for verifyAnalysis.
bool isNegative() const
Determine sign of this APInt.
The SCEV is loop-invariant.
void WriteAsOperand(raw_ostream &, const Value *, bool PrintTy=true, const Module *Context=0)
APInt LLVM_ATTRIBUTE_UNUSED_RESULT urem(const APInt &RHS) const
Unsigned remainder operation.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
bool isUnconditional() const
static Constant * getIntegerCast(Constant *C, Type *Ty, bool isSigned)
Create a ZExt, Bitcast or Trunc for integer -> integer casts.
static unsigned getBitWidth(Type *Ty, const DataLayout *TD)
bool isAlignOf(Type *&AllocTy) const
inst_iterator inst_begin(Function *F)
MarkPendingLoopPredicate(Value *C, DenseSet< Value * > &LP)
ConstantRange truncate(uint32_t BitWidth) const
const StructLayout * getStructLayout(StructType *Ty) const
APInt urem(const APInt &LHS, const APInt &RHS)
Function for unsigned remainder operation.
const APInt & getValue() const
Return the constant's value.
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
#define llvm_unreachable(msg)
APInt LLVM_ATTRIBUTE_UNUSED_RESULT lshr(unsigned shiftAmt) const
Logical right-shift function.
const SCEV *const * op_iterator
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
iterator find_as(const LookupKeyT &Val)
void getExitingBlocks(SmallVectorImpl< BlockT * > &ExitingBlocks) const
static bool findGCD(unsigned Bits, APInt AM, APInt BM, APInt Delta, APInt &G, APInt &X, APInt &Y)
uint64_t getTypeSizeInBits(Type *Ty) const
void AddInteger(signed I)
APInt umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
ID
LLVM Calling Convention Representation.
ConstantRange signExtend(uint32_t BitWidth) const
op_iterator op_begin() const
virtual void getAnalysisUsage(AnalysisUsage &AU) const
void setNoWrapFlags(NoWrapFlags Flags)
Set flags for a non-recurrence without clearing previously set flags.
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
ConstantRange multiply(const ConstantRange &Other) const
APInt lshr(const APInt &LHS, unsigned shiftAmt)
Logical right-shift function.
void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const
uint64_t getZExtValue() const
Return the zero extended value.
static const APInt srem(const SCEVConstant *C1, const SCEVConstant *C2)
static const SCEV * BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy)
bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
reverse_iterator rbegin() const
static Constant * getSizeOf(Type *Ty)
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
bool contains(const APInt &Val) const
unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock)
const char * data() const
APInt udiv(const APInt &LHS, const APInt &RHS)
Unsigned division function for APInt.
Constant * ConstantFoldConstantExpression(const ConstantExpr *CE, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0)
static Constant * getICmp(unsigned short pred, Constant *LHS, Constant *RHS)
bool sgt(const APInt &RHS) const
Signed greather than comparison.
BasicBlock * getSuccessor(unsigned i) const
const SCEV * getSizeOfExpr(Type *IntTy, Type *AllocTy)
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt sdiv(const APInt &LHS, const APInt &RHS)
Signed division function for APInt.
Loop * getLoopFor(const BasicBlock *BB) const
static cl::opt< unsigned > MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, cl::desc("Maximum number of iterations SCEV will ""symbolically execute a constant ""derived loop"), cl::init(100))
bool hasDefinitiveInitializer() const
static Constant * getUDiv(Constant *C1, Constant *C2, bool isExact=false)
APInt ashr(const APInt &LHS, unsigned shiftAmt)
Arithmetic right-shift function.
Type * getEffectiveSCEVType(Type *Ty) const
ConstantRange subtract(const APInt &CI) const
const char * getOpcodeName() const
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
static std::pair< const SCEV *, const SCEV * > SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE)
size_t getNumOperands() const
void ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout *TD=0, unsigned Depth=0)
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static cl::opt< unsigned > MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4))
unsigned getNumIncomingValues() const
std::vector< LoopT * >::const_reverse_iterator reverse_iterator
uint64_t getElementOffset(unsigned Idx) const
static Constant * EvaluateExpression(Value *V, const Loop *L, DenseMap< Instruction *, Constant * > &Vals, const DataLayout *TD, const TargetLibraryInfo *TLI)
bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNumIterationsInRange(ConstantRange Range, ScalarEvolution &SE) const
unsigned getNumSuccessors() const
const SCEV * getCouldNotCompute()
initializer< Ty > init(const Ty &Val)
bool isSCEVable(Type *Ty) const
* if(!EatIfPresent(lltok::kw_thread_local)) return false
APInt srem(const APInt &LHS, const APInt &RHS)
Function for signed remainder operation.
ConstantRange intersectWith(const ConstantRange &CR) const
bool isSizeOf(Type *&AllocTy) const
APInt LLVM_ATTRIBUTE_UNUSED_RESULT trunc(unsigned width) const
Truncate to new width.
LLVM Basic Block Representation.
BasicBlock * getSuccessor(unsigned idx) const
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
static void GroupByComplexity(SmallVectorImpl< const SCEV * > &Ops, LoopInfo *LI)
bool sge(const APInt &RHS) const
Signed greather or equal comparison.
LLVM Constant Representation.
bool isMaxSignedValue() const
Determine if this is the largest signed value.
const SCEV * getOperand(unsigned i) const
APInt Or(const APInt &LHS, const APInt &RHS)
Bitwise OR function for APInt.
APInt Xor(const APInt &LHS, const APInt &RHS)
Bitwise XOR function for APInt.
static bool canConstantEvolve(Instruction *I, const Loop *L)
static const SCEV * getPreStartForSignExtend(const SCEVAddRecExpr *AR, Type *Ty, ScalarEvolution *SE)
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
APInt LLVM_ATTRIBUTE_UNUSED_RESULT sext(unsigned width) const
Sign extend to a new width.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
ConstantRange udiv(const ConstantRange &Other) const
BasicBlock * getIncomingBlock(unsigned i) const
ItTy next(ItTy it, Dist n)
bool contains(const LoopT *L) const
bool isFalseWhenEqual() const
Determine if this is false when both operands are the same.
bool hasOperand(const SCEV *S, const SCEV *Op) const
Represent an integer comparison operator.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
const SCEV * getMaxBackedgeTakenCount(const Loop *L)
unsigned getBitWidth() const
Return the number of bits in the APInt.
unsigned getValueID() const
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
bool isMaxValue() const
Determine if this is the largest unsigned value.
APInt LLVM_ATTRIBUTE_UNUSED_RESULT sdiv(const APInt &RHS) const
Signed division function for APInt.
Value * getOperand(unsigned i) const
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0)
Integer representation type.
Predicate getPredicate() const
Return the predicate for this instruction.
ConstantRange zeroExtend(uint32_t BitWidth) const
bool isKnownNegative(const SCEV *S)
bool count(const KeyT &Val) const
count - Return true if the specified key is in the map.
static Constant * getNot(Constant *C)
void forgetValue(Value *V)
Constant * ConstantFoldLoadFromConstPtr(Constant *C, const DataLayout *TD=0)
void setNoWrapFlags(NoWrapFlags Flags)
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
static Constant * getAllOnesValue(Type *Ty)
Get the all ones value.
const SCEV * getLHS() const
bool dominates(const DomTreeNode *A, const DomTreeNode *B) const
void append(in_iter in_start, in_iter in_end)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
iterator erase(iterator I)
Value * SimplifyInstruction(Instruction *I, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0, const DominatorTree *DT=0)
bool isNonConstantNegative() const
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
ConstantRange add(const ConstantRange &Other) const
const SCEV * getRHS() const
The SCEV is loop-variant (unknown).
static const APInt sdiv(const SCEVConstant *C1, const SCEVConstant *C2)
LoopInfoBase< BasicBlock, Loop >::reverse_iterator reverse_iterator
bool isConditional() const
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
static IntegerType * get(LLVMContext &C, unsigned NumBits)
Get or create an IntegerType instance.
static Constant * getBitCast(Constant *C, Type *Ty)
static PHINode * getConstantEvolvingPHI(Value *V, const Loop *L)
static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2)
static PointerType * getUnqual(Type *ElementType)
Class for constant integers.
bool isKnownPositive(const SCEV *S)
bool slt(const APInt &RHS) const
Signed less than comparison.
Value * getIncomingValue(unsigned i) const
uint64_t getTypeAllocSize(Type *Ty) const
reverse_iterator rend() const
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty)
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty)
DenseSet< Value * > & LoopPreds
bool isAllOnesValue() const
The SCEV dominates the block.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
const APInt & getLower() const
bool erase(const KeyT &Val)
bool isTrueWhenEqual() const
Determine if this is true when both operands are the same.
ConstantRange getSignedRange(const SCEV *S)
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
Predicate getSwappedPredicate() const
Return the predicate as if the operands were swapped.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
ConstantInt * getValue() const
static Constant * getTrunc(Constant *C, Type *Ty)
const SCEV * delinearize(ScalarEvolution &SE, SmallVectorImpl< const SCEV * > &Subscripts, SmallVectorImpl< const SCEV * > &Sizes) const
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
APInt umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT maskFlags(SCEV::NoWrapFlags Flags, int Mask)
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
scalar Scalar Evolution Analysis
APInt smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Class for arbitrary precision integers.
void * Allocate(size_t Size, size_t Alignment)
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty)
BasicBlock * getSinglePredecessor()
Return this block if it has a single predecessor block. Otherwise return a null pointer.
unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock)
DenseMap< const Loop *, std::string > VerifyMap
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
static const SCEV * getOverflowLimitForStep(const SCEV *Step, ICmpInst::Predicate *Pred, ScalarEvolution *SE)
void visitAll(const SCEV *Root, SV &Visitor)
Use SCEVTraversal to visit all nodes in the givien expression tree.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
bool isMinValue() const
Determine if this is the smallest unsigned value.
APInt And(const APInt &LHS, const APInt &RHS)
Bitwise AND function for APInt.
static Constant * BuildConstantFromSCEV(const SCEV *V)
ConstantRange umax(const ConstantRange &Other) const
DenseMapIterator< KeyT, ValueT, KeyInfoT > iterator
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
static void replaceSubString(std::string &Str, StringRef From, StringRef To)
replaceSubString - Replaces all occurences of From in Str with To.
Value * getCondition() const
static Constant * getSExt(Constant *C, Type *Ty)
The SCEV does not dominate the block.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
void forgetLoop(const Loop *L)
pointer data()
data - Return a pointer to the vector's buffer, even if empty().
static IntegerType * getInt32Ty(LLVMContext &C)
static Constant * getZExt(Constant *C, Type *Ty)
static Constant * getOffsetOf(StructType *STy, unsigned FieldNo)
unsigned greater or equal
static PHINode * getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L, DenseMap< Instruction *, PHINode * > &PHIMap)
static Instruction::CastOps getCastOpcode(const Value *Val, bool SrcIsSigned, Type *Ty, bool DstIsSigned)
Infer the opcode for cast operand and type.
TerminatorInst * getTerminator()
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static Constant * AddOne(Constant *C)
AddOne - Add one to a ConstantInt.
bool isSignBit() const
Check if the APInt's value is returned by getSignBit.
bool isKnownNonZero(const SCEV *S)
BlockT * getLoopPredecessor() const
APInt smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
static ConstantRange makeConstantRange(Predicate pred, const APInt &C)
Make a ConstantRange for a relation with a constant value.
static bool CollectAddOperandsWithScales(DenseMap< const SCEV *, APInt > &M, SmallVectorImpl< const SCEV * > &NewOps, APInt &AccumulatedConstant, const SCEV *const *Ops, size_t NumOperands, const APInt &Scale, ScalarEvolution &SE)
AnalysisUsage & addRequiredTransitive()
unsigned getPrimitiveSizeInBits() const
const Loop * getLoop() const
INITIALIZE_PASS_BEGIN(ScalarEvolution,"scalar-evolution","Scalar Evolution Analysis", false, true) INITIALIZE_PASS_END(ScalarEvolution
unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD=0, unsigned Depth=0)
const SCEV * getBackedgeTakenCount(const Loop *L)
const APInt & getUpper() const
virtual void releaseMemory()
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
void initializeScalarEvolutionPass(PassRegistry &)
unsigned getSCEVType() const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS)
~MarkPendingLoopPredicate()
void print(raw_ostream &OS) const
LLVM Value Representation.
ValueT lookup(const KeyT &Val) const
const SCEV * getSCEV(Value *V)
unsigned getOpcode() const
getOpcode() returns a member of one of the enums like Instruction::Add.
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, const Loop *L)
unsigned getArgNo() const
Return the index of this formal argument in its containing function.
APInt shl(const APInt &LHS, unsigned shiftAmt)
Left-shift function.
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Constant * ConstantFoldInstOperands(unsigned Opcode, Type *DestTy, ArrayRef< Constant * > Ops, const DataLayout *TD=0, const TargetLibraryInfo *TLI=0)
uint64_t getTypeSizeInBits(Type *Ty) const
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
const SCEV * getUnknown(Value *V)
FoldingSetNodeIDRef Intern(BumpPtrAllocator &Allocator) const
The SCEV varies predictably with the loop.
bool dominates(const SCEV *S, const BasicBlock *BB)
op_iterator op_end() const
inst_iterator inst_end(Function *F)
APInt LLVM_ATTRIBUTE_UNUSED_RESULT zext(unsigned width) const
Zero extend to a new width.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty)
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml","ocaml 3.10-compatible collector")
std::vector< LoopT * >::const_iterator iterator
const SCEV * getNegativeSCEV(const SCEV *V)
static bool CanConstantFold(const Instruction *I)
Constant * ConstantFoldLoadThroughGEPIndices(Constant *C, ArrayRef< Constant * > Indices)
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty)
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
static Constant * getMul(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
APInt getUnsignedMax() const
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
friend class SCEVCallbackVH
iterator find(const KeyT &Val)
const SCEV * getOperand() const
static Constant * getCast(unsigned ops, Constant *C, Type *Ty)
unsigned getLoopDepth() const
const SCEV * getNotSCEV(const SCEV *V)
getNotSCEV - Return a SCEV corresponding to ~V = -1-V
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
static RegisterPass< NVPTXAllocaHoisting > X("alloca-hoisting","Hoisting alloca instructions in non-entry ""blocks to the entry block")
const BasicBlock * getParent() const
INITIALIZE_PASS(GlobalMerge,"global-merge","Global Merge", false, false) bool GlobalMerge const DataLayout * TD
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
gep_type_iterator gep_type_begin(const User *GEP)
APInt getUnsignedMin() const