85 #include "llvm/Config/llvm-config.h"
133 using namespace llvm;
134 using namespace PatternMatch;
136 #define DEBUG_TYPE "scalar-evolution"
139 "Number of loops with predictable loop counts");
141 "Number of loops without predictable loop counts");
142 STATISTIC(NumBruteForceTripCountsComputed,
143 "Number of loops with trip counts computed by force");
145 #ifdef EXPENSIVE_CHECKS
146 bool llvm::VerifySCEV =
true;
148 bool llvm::VerifySCEV =
false;
154 cl::desc(
"Maximum number of iterations SCEV will "
155 "symbolically execute a constant "
161 cl::desc(
"Verify ScalarEvolution's backedge taken counts (slow)"));
164 cl::desc(
"Enable stricter verification with -verify-scev is passed"));
167 cl::desc(
"Verify no dangling value in ScalarEvolution's "
168 "ExprValueMap (slow)"));
172 cl::desc(
"Verify IR correctness when making sensitive SCEV queries (slow)"),
177 cl::desc(
"Threshold for inlining multiplication operands into a SCEV"),
182 cl::desc(
"Threshold for inlining addition operands into a SCEV"),
186 "scalar-evolution-max-scev-compare-depth",
cl::Hidden,
187 cl::desc(
"Maximum depth of recursive SCEV complexity comparisons"),
191 "scalar-evolution-max-scev-operations-implication-depth",
cl::Hidden,
192 cl::desc(
"Maximum depth of recursive SCEV operations implication analysis"),
196 "scalar-evolution-max-value-compare-depth",
cl::Hidden,
197 cl::desc(
"Maximum depth of recursive value complexity comparisons"),
202 cl::desc(
"Maximum depth of recursive arithmetics"),
206 "scalar-evolution-max-constant-evolving-depth",
cl::Hidden,
211 cl::desc(
"Maximum depth of recursive SExt/ZExt/Trunc"),
216 cl::desc(
"Max coefficients in AddRec during evolving"),
221 cl::desc(
"Size of the expression which is considered huge"),
227 cl::desc(
"When printing analysis, include information on every instruction"));
230 "scalar-evolution-use-expensive-range-sharpening",
cl::Hidden,
232 cl::desc(
"Use more powerful methods of sharpening expression ranges. May "
233 "be costly in terms of compile time"));
236 "scalar-evolution-max-scc-analysis-depth",
cl::Hidden,
237 cl::desc(
"Maximum amount of nodes to process while searching SCEVUnknown "
238 "Phi strongly connected components"),
243 cl::desc(
"Handle <= and >= in finite loops"),
254 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
262 switch (getSCEVType()) {
264 cast<SCEVConstant>(
this)->getValue()->printAsOperand(OS,
false);
269 OS <<
"(ptrtoint " << *
Op->getType() <<
" " << *
Op <<
" to "
270 << *PtrToInt->
getType() <<
")";
276 OS <<
"(trunc " << *
Op->getType() <<
" " << *
Op <<
" to "
283 OS <<
"(zext " << *
Op->getType() <<
" " << *
Op <<
" to "
290 OS <<
"(sext " << *
Op->getType() <<
" " << *
Op <<
" to "
319 const char *OpStr =
nullptr;
332 OpStr =
" umin_seq ";
338 ListSeparator
LS(OpStr);
358 OS <<
"(" << *UDiv->
getLHS() <<
" /u " << *UDiv->
getRHS() <<
")";
365 OS <<
"sizeof(" << *AllocTy <<
")";
369 OS <<
"alignof(" << *AllocTy <<
")";
376 OS <<
"offsetof(" << *CTy <<
", ";
387 OS <<
"***COULDNOTCOMPUTE***";
394 switch (getSCEVType()) {
396 return cast<SCEVConstant>(
this)->getType();
401 return cast<SCEVCastExpr>(
this)->getType();
403 return cast<SCEVAddRecExpr>(
this)->getType();
405 return cast<SCEVMulExpr>(
this)->getType();
410 return cast<SCEVMinMaxExpr>(
this)->getType();
412 return cast<SCEVSequentialMinMaxExpr>(
this)->getType();
414 return cast<SCEVAddExpr>(
this)->getType();
416 return cast<SCEVUDivExpr>(
this)->getType();
418 return cast<SCEVUnknown>(
this)->getType();
427 return SC->getValue()->isZero();
433 return SC->getValue()->isOne();
439 return SC->getValue()->isMinusOne();
445 if (!
Mul)
return false;
449 if (!
SC)
return false;
452 return SC->getAPInt().isNegative();
467 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
469 UniqueSCEVs.InsertNode(
S,
IP);
493 "Must be a non-bit-width-changing pointer-to-integer cast!");
505 "Cannot truncate non-integer value!");
512 "Cannot zero extend non-integer value!");
519 "Cannot sign extend non-integer value!");
522 void SCEVUnknown::deleted() {
524 SE->forgetMemoizedResults(
this);
527 SE->UniqueSCEVs.RemoveNode(
this);
533 void SCEVUnknown::allUsesReplacedWith(
Value *New) {
535 SE->forgetMemoizedResults(
this);
538 SE->UniqueSCEVs.RemoveNode(
this);
546 if (VCE->getOpcode() == Instruction::PtrToInt)
547 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
548 if (CE->getOpcode() == Instruction::GetElementPtr &&
549 CE->getOperand(0)->isNullValue() &&
550 CE->getNumOperands() == 2)
551 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(1)))
553 AllocTy = cast<GEPOperator>(CE)->getSourceElementType();
562 if (VCE->getOpcode() == Instruction::PtrToInt)
563 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
564 if (CE->getOpcode() == Instruction::GetElementPtr &&
565 CE->getOperand(0)->isNullValue()) {
566 Type *Ty = cast<GEPOperator>(CE)->getSourceElementType();
567 if (
StructType *STy = dyn_cast<StructType>(Ty))
568 if (!STy->isPacked() &&
569 CE->getNumOperands() == 3 &&
570 CE->getOperand(1)->isNullValue()) {
571 if (
ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(2)))
573 STy->getNumElements() == 2 &&
574 STy->getElementType(0)->isIntegerTy(1)) {
575 AllocTy = STy->getElementType(1);
586 if (VCE->getOpcode() == Instruction::PtrToInt)
587 if (
ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
588 if (CE->getOpcode() == Instruction::GetElementPtr &&
589 CE->getNumOperands() == 3 &&
590 CE->getOperand(0)->isNullValue() &&
591 CE->getOperand(1)->isNullValue()) {
592 Type *Ty = cast<GEPOperator>(CE)->getSourceElementType();
597 FieldNo = CE->getOperand(2);
638 if (LIsPointer != RIsPointer)
639 return (
int)LIsPointer - (
int)RIsPointer;
644 return (
int)LID - (
int)RID;
647 if (
const auto *LA = dyn_cast<Argument>(LV)) {
648 const auto *
RA = cast<Argument>(RV);
649 unsigned LArgNo = LA->getArgNo(), RArgNo =
RA->getArgNo();
650 return (
int)LArgNo - (
int)RArgNo;
653 if (
const auto *LGV = dyn_cast<GlobalValue>(LV)) {
654 const auto *RGV = cast<GlobalValue>(RV);
656 const auto IsGVNameSemantic = [&](
const GlobalValue *GV) {
657 auto LT = GV->getLinkage();
664 if (IsGVNameSemantic(LGV) && IsGVNameSemantic(RGV))
665 return LGV->getName().compare(RGV->getName());
670 if (
const auto *LInst = dyn_cast<Instruction>(LV)) {
671 const auto *RInst = cast<Instruction>(RV);
676 if (LParent != RParent) {
679 if (LDepth != RDepth)
680 return (
int)LDepth - (
int)RDepth;
684 unsigned LNumOps = LInst->getNumOperands(),
685 RNumOps = RInst->getNumOperands();
686 if (LNumOps != RNumOps)
687 return (
int)LNumOps - (
int)RNumOps;
689 for (
unsigned Idx :
seq(0u, LNumOps)) {
692 RInst->getOperand(Idx),
Depth + 1);
719 return (
int)LType - (
int)RType;
749 unsigned LBitWidth = LA.
getBitWidth(), RBitWidth =
RA.getBitWidth();
750 if (LBitWidth != RBitWidth)
751 return (
int)LBitWidth - (
int)RBitWidth;
752 return LA.
ult(
RA) ? -1 : 1;
763 if (LLoop != RLoop) {
765 assert(LHead != RHead &&
"Two loops share the same header?");
770 "No dominance between recurrences used by one SCEV?");
776 if (LNumOps != RNumOps)
777 return (
int)LNumOps - (
int)RNumOps;
780 for (
unsigned i = 0;
i != LNumOps; ++
i) {
803 if (LNumOps != RNumOps)
804 return (
int)LNumOps - (
int)RNumOps;
806 for (
unsigned i = 0;
i != LNumOps; ++
i) {
866 if (Ops.size() < 2)
return;
875 return Complexity && *Complexity < 0;
877 if (Ops.size() == 2) {
881 if (IsLessComplex(
RHS,
LHS))
888 return IsLessComplex(
LHS,
RHS);
895 for (
unsigned i = 0,
e = Ops.size();
i !=
e-2; ++
i) {
897 unsigned Complexity =
S->getSCEVType();
901 for (
unsigned j =
i+1;
j !=
e && Ops[
j]->getSCEVType() == Complexity; ++
j) {
906 if (
i ==
e-2)
return;
994 for (
unsigned i = 3;
i <= K; ++
i) {
996 unsigned TwoFactors =
Mult.countTrailingZeros();
998 Mult.lshrInPlace(TwoFactors);
999 OddFactorial *=
Mult;
1003 unsigned CalculationBits =
W +
T;
1012 APInt MultiplyFactor = OddFactorial.
zext(
W+1);
1014 MultiplyFactor = MultiplyFactor.
trunc(
W);
1020 for (
unsigned i = 1;
i != K; ++
i) {
1058 if (isa<SCEVCouldNotCompute>(Coeff))
1073 "getLosslessPtrToIntExpr() should self-recurse at most once.");
1077 if (!
Op->getType()->isPointerTy())
1088 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
1107 if (
auto *U = dyn_cast<SCEVUnknown>(
Op)) {
1112 if (isa<ConstantPointerNull>(U->getValue()))
1118 SCEV *
S =
new (SCEVAllocator)
1120 UniqueSCEVs.InsertNode(
S,
IP);
1125 assert(
Depth == 0 &&
"getLosslessPtrToIntExpr() should not self-recurse for "
1126 "non-SCEVUnknown's.");
1138 class SCEVPtrToIntSinkingRewriter
1146 SCEVPtrToIntSinkingRewriter
Rewriter(SE);
1151 Type *STy =
S->getType();
1156 return Base::visit(
S);
1161 bool Changed =
false;
1171 bool Changed =
false;
1181 "Should only reach pointer-typed SCEVUnknown's.");
1189 "We must have succeeded in sinking the cast, "
1190 "and ending up with an integer-typed expression!");
1198 if (isa<SCEVCouldNotCompute>(IntOp))
1207 "This is not a truncating conversion!");
1209 "This is not a conversion to a SCEVable type!");
1210 assert(!
Op->getType()->isPointerTy() &&
"Can't truncate pointer!");
1218 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
1240 UniqueSCEVs.InsertNode(
S,
IP);
1249 if (isa<SCEVAddExpr>(
Op) || isa<SCEVMulExpr>(
Op)) {
1250 auto *CommOp = cast<SCEVCommutativeExpr>(
Op);
1252 unsigned numTruncs = 0;
1253 for (
unsigned i = 0,
e = CommOp->getNumOperands();
i !=
e && numTruncs < 2;
1256 if (!isa<SCEVIntegralCastExpr>(CommOp->getOperand(
i)) &&
1257 isa<SCEVTruncateExpr>(
S))
1261 if (numTruncs < 2) {
1262 if (isa<SCEVAddExpr>(
Op))
1264 else if (isa<SCEVMulExpr>(
Op))
1272 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
1279 for (
const SCEV *
Op : AddRec->operands())
1294 UniqueSCEVs.InsertNode(
S,
IP);
1334 struct ExtendOpTraitsBase {
1340 template <
typename ExtendOp>
struct ExtendOpTraits {
1356 static const GetExtendExprTy GetExtendExpr;
1358 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1365 const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1372 static const GetExtendExprTy GetExtendExpr;
1374 static const SCEV *getOverflowLimitForStep(
const SCEV *Step,
1381 const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
1393 template <
typename ExtendOpTy>
1396 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1397 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1404 const SCEVAddExpr *SA = dyn_cast<SCEVAddExpr>(Start);
1414 DiffOps.push_back(
Op);
1423 auto PreStartFlags =
1441 const SCEV *OperandExtendedStart =
1443 (SE->*GetExtendExpr)(Step, WideTy,
Depth));
1444 if ((SE->*GetExtendExpr)(Start, WideTy,
Depth) == OperandExtendedStart) {
1456 const SCEV *OverflowLimit =
1457 ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(Step, &Pred, SE);
1459 if (OverflowLimit &&
1467 template <
typename ExtendOpTy>
1471 auto GetExtendExpr = ExtendOpTraits<ExtendOpTy>::GetExtendExpr;
1473 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE,
Depth);
1479 (SE->*GetExtendExpr)(PreStart, Ty,
Depth));
1514 template <
typename ExtendOpTy>
1515 bool ScalarEvolution::proveNoWrapByVaryingStart(
const SCEV *Start,
1518 auto WrapType = ExtendOpTraits<ExtendOpTy>::WrapType;
1524 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start);
1530 for (
unsigned Delta : {-2, -1, 1, 2}) {
1535 ID.AddPointer(PreStart);
1536 ID.AddPointer(Step);
1544 if (PreAR && PreAR->getNoWrapFlags(WrapType)) {
1547 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep(
1548 DeltaS, &Pred,
this);
1566 const unsigned BitWidth =
C.getBitWidth();
1584 const APInt &ConstantStart,
1597 "This is not an extending conversion!");
1599 "This is not a conversion to a SCEVable type!");
1600 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1619 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
1623 UniqueSCEVs.InsertNode(
S,
IP);
1632 const SCEV *
X =
ST->getOperand();
1646 if (AR->isAffine()) {
1647 const SCEV *Start = AR->getStart();
1648 const SCEV *Step = AR->getStepRecurrence(*
this);
1650 const Loop *L = AR->getLoop();
1652 if (!AR->hasNoUnsignedWrap()) {
1653 auto NewFlags = proveNoWrapViaConstantRanges(AR);
1659 if (AR->hasNoUnsignedWrap())
1661 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1),
1673 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
1678 const SCEV *CastedMaxBECount =
1682 if (MaxBECount == RecastedMaxBECount) {
1692 const SCEV *WideMaxBECount =
1694 const SCEV *OperandExtendedAdd =
1700 if (ZAdd == OperandExtendedAdd) {
1704 return getAddRecExpr(getExtendAddRecStart<SCEVZeroExtendExpr>(
1705 AR, Ty,
this,
Depth + 1),
1707 AR->getNoWrapFlags());
1711 OperandExtendedAdd =
1717 if (ZAdd == OperandExtendedAdd) {
1722 return getAddRecExpr(getExtendAddRecStart<SCEVZeroExtendExpr>(
1723 AR, Ty,
this,
Depth + 1),
1725 AR->getNoWrapFlags());
1737 if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
1740 auto NewFlags = proveNoUnsignedWrapViaInduction(AR);
1742 if (AR->hasNoUnsignedWrap()) {
1748 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1),
1764 return getAddRecExpr(getExtendAddRecStart<SCEVZeroExtendExpr>(
1765 AR, Ty,
this,
Depth + 1),
1767 AR->getNoWrapFlags());
1775 if (
const auto *
SC = dyn_cast<SCEVConstant>(Start)) {
1780 const SCEV *SResidual =
1789 if (proveNoWrapByVaryingStart<SCEVZeroExtendExpr>(Start, Step, L)) {
1792 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty,
this,
Depth + 1),
1807 if (
auto *Div = dyn_cast<SCEVUDivExpr>(
Op))
1811 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1813 if (SA->hasNoUnsignedWrap()) {
1817 for (
const auto *
Op : SA->operands())
1830 if (
const auto *
SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1834 const SCEV *SResidual =
1844 if (
auto *SM = dyn_cast<SCEVMulExpr>(
Op)) {
1846 if (SM->hasNoUnsignedWrap()) {
1850 for (
const auto *
Op : SM->operands())
1867 if (SM->getNumOperands() == 2)
1868 if (
auto *MulLHS = dyn_cast<SCEVConstant>(SM->getOperand(0)))
1869 if (MulLHS->getAPInt().isPowerOf2())
1870 if (
auto *TruncRHS = dyn_cast<SCEVTruncateExpr>(SM->getOperand(1))) {
1872 MulLHS->getAPInt().logBase2();
1884 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
1887 UniqueSCEVs.InsertNode(
S,
IP);
1895 "This is not an extending conversion!");
1897 "This is not a conversion to a SCEVable type!");
1898 assert(!
Op->getType()->isPointerTy() &&
"Can't extend pointer!");
1921 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
1926 UniqueSCEVs.InsertNode(
S,
IP);
1935 const SCEV *
X =
ST->getOperand();
1944 if (
auto *SA = dyn_cast<SCEVAddExpr>(
Op)) {
1946 if (SA->hasNoSignedWrap()) {
1950 for (
const auto *
Op : SA->operands())
1964 if (
const auto *
SC = dyn_cast<SCEVConstant>(SA->getOperand(0))) {
1968 const SCEV *SResidual =
1982 if (AR->isAffine()) {
1983 const SCEV *Start = AR->getStart();
1984 const SCEV *Step = AR->getStepRecurrence(*
this);
1986 const Loop *L = AR->getLoop();
1988 if (!AR->hasNoSignedWrap()) {
1989 auto NewFlags = proveNoWrapViaConstantRanges(AR);
1995 if (AR->hasNoSignedWrap())
1997 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1),
2009 if (!isa<SCEVCouldNotCompute>(MaxBECount)) {
2015 const SCEV *CastedMaxBECount =
2019 if (MaxBECount == RecastedMaxBECount) {
2029 const SCEV *WideMaxBECount =
2031 const SCEV *OperandExtendedAdd =
2037 if (SAdd == OperandExtendedAdd) {
2041 return getAddRecExpr(getExtendAddRecStart<SCEVSignExtendExpr>(
2042 AR, Ty,
this,
Depth + 1),
2044 AR->getNoWrapFlags());
2048 OperandExtendedAdd =
2054 if (SAdd == OperandExtendedAdd) {
2066 return getAddRecExpr(getExtendAddRecStart<SCEVSignExtendExpr>(
2067 AR, Ty,
this,
Depth + 1),
2069 AR->getNoWrapFlags());
2074 auto NewFlags = proveNoSignedWrapViaInduction(AR);
2076 if (AR->hasNoSignedWrap()) {
2082 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1),
2089 if (
const auto *
SC = dyn_cast<SCEVConstant>(Start)) {
2094 const SCEV *SResidual =
2103 if (proveNoWrapByVaryingStart<SCEVSignExtendExpr>(Start, Step, L)) {
2106 getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty,
this,
Depth + 1),
2118 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
2121 UniqueSCEVs.InsertNode(
S,
IP);
2147 "This is not an extending conversion!");
2149 "This is not a conversion to a SCEVable type!");
2154 if (
SC->getAPInt().isNegative())
2159 const SCEV *NewOp =
T->getOperand();
2167 if (!isa<SCEVZeroExtendExpr>(ZExt))
2172 if (!isa<SCEVSignExtendExpr>(SExt))
2178 for (
const SCEV *
Op : AR->operands())
2184 if (isa<SCEVSMaxExpr>(
Op))
2217 APInt &AccumulatedConstant,
2218 const SCEV *
const *Ops,
size_t NumOperands,
2221 bool Interesting =
false;
2228 if (Scale != 1 || AccumulatedConstant != 0 ||
C->getValue()->
isZero())
2230 AccumulatedConstant += Scale *
C->getAPInt();
2235 for (;
i != NumOperands; ++
i) {
2245 Add->op_begin(), Add->getNumOperands(),
2252 auto Pair =
M.insert({
Key, NewScale});
2254 NewOps.push_back(Pair.first->first);
2256 Pair.first->second += NewScale;
2264 std::pair<DenseMap<const SCEV *, APInt>::iterator,
bool> Pair =
2265 M.insert({Ops[
i], Scale});
2267 NewOps.push_back(Pair.first->first);
2269 Pair.first->second += Scale;
2290 case Instruction::Sub:
2303 auto *NarrowTy = cast<IntegerType>(
LHS->
getType());
2325 bool Deduced =
false;
2328 return {Flags, Deduced};
2333 return {Flags, Deduced};
2352 return {Flags, Deduced};
2362 using namespace std::placeholders;
2369 assert(CanAnalyze &&
"don't call from other places!");
2376 auto IsKnownNonNegative = [&](
const SCEV *
S) {
2386 if (SignOrUnsignWrap != SignOrUnsignMask &&
2388 isa<SCEVConstant>(Ops[0])) {
2401 const APInt &
C = cast<SCEVConstant>(Ops[0])->getAPInt();
2406 Opcode,
C, OBO::NoSignedWrap);
2414 Opcode,
C, OBO::NoUnsignedWrap);
2424 Ops[0]->isZero() && IsKnownNonNegative(Ops[1]))
2430 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[0]))
2431 if (UDiv->getOperand(1) == Ops[1])
2433 if (
auto *UDiv = dyn_cast<SCEVUDivExpr>(Ops[1]))
2434 if (UDiv->getOperand(1) == Ops[0])
2450 "only nuw or nsw allowed");
2451 assert(!Ops.empty() &&
"Cannot get empty add!");
2452 if (Ops.size() == 1)
return Ops[0];
2455 for (
unsigned i = 1,
e = Ops.size();
i !=
e; ++
i)
2457 "SCEVAddExpr operand types don't match!");
2459 Ops, [](
const SCEV *
Op) {
return Op->getType()->isPointerTy(); });
2460 assert(NumPtrs <= 1 &&
"add has at most one pointer operand");
2468 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
2470 assert(Idx < Ops.size());
2471 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
2473 Ops[0] =
getConstant(LHSC->getAPInt() + RHSC->getAPInt());
2474 if (Ops.size() == 2)
return Ops[0];
2475 Ops.
erase(Ops.begin()+1);
2476 LHSC = cast<SCEVConstant>(Ops[0]);
2480 if (LHSC->getValue()->isZero()) {
2481 Ops.
erase(Ops.begin());
2485 if (Ops.size() == 1)
return Ops[0];
2495 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2500 if (Add->getNoWrapFlags(OrigFlags) != OrigFlags)
2501 Add->setNoWrapFlags(ComputeFlags(Ops));
2508 Type *Ty = Ops[0]->getType();
2509 bool FoundMatch =
false;
2510 for (
unsigned i = 0,
e = Ops.size();
i !=
e-1; ++
i)
2511 if (Ops[
i] == Ops[
i+1]) {
2514 while (
i+Count !=
e && Ops[
i+Count] == Ops[
i])
2519 if (Ops.size() == Count)
2522 Ops.
erase(Ops.begin()+
i+1, Ops.begin()+
i+Count);
2523 --
i;
e -= Count - 1;
2533 auto FindTruncSrcType = [&]() ->
Type * {
2538 if (
auto *
T = dyn_cast<SCEVTruncateExpr>(Ops[Idx]))
2539 return T->getOperand()->getType();
2540 if (
const auto *
Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
2542 if (
const auto *
T = dyn_cast<SCEVTruncateExpr>(LastOp))
2543 return T->getOperand()->getType();
2547 if (
auto *SrcType = FindTruncSrcType()) {
2552 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i) {
2554 if (
T->getOperand()->getType() != SrcType) {
2558 LargeOps.push_back(
T->getOperand());
2559 }
else if (
const SCEVConstant *
C = dyn_cast<SCEVConstant>(Ops[
i])) {
2561 }
else if (
const SCEVMulExpr *
M = dyn_cast<SCEVMulExpr>(Ops[
i])) {
2563 for (
unsigned j = 0,
f =
M->getNumOperands();
j !=
f && Ok; ++
j) {
2565 dyn_cast<SCEVTruncateExpr>(
M->getOperand(
j))) {
2566 if (
T->getOperand()->getType() != SrcType) {
2570 LargeMulOps.push_back(
T->getOperand());
2571 }
else if (
const auto *
C = dyn_cast<SCEVConstant>(
M->getOperand(
j))) {
2589 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold))
2594 if (Ops.size() == 2) {
2598 const SCEV *A = Ops[0];
2599 const SCEV *
B = Ops[1];
2600 auto *AddExpr = dyn_cast<SCEVAddExpr>(
B);
2601 auto *
C = dyn_cast<SCEVConstant>(A);
2602 if (AddExpr &&
C && isa<SCEVConstant>(AddExpr->getOperand(0))) {
2603 auto C1 = cast<SCEVConstant>(AddExpr->getOperand(0))->getAPInt();
2604 auto C2 =
C->getAPInt();
2608 auto AddFlags = AddExpr->getNoWrapFlags();
2634 if (Ops.size() == 2) {
2647 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
scAddExpr)
2651 if (Idx < Ops.size()) {
2652 bool DeletedAdd =
false;
2657 while (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) {
2663 Ops.
erase(Ops.begin()+Idx);
2664 Ops.
append(Add->op_begin(), Add->op_end());
2666 CommonFlags =
maskFlags(CommonFlags, Add->getNoWrapFlags());
2677 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
scMulExpr)
2682 if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) {
2688 Ops.data(), Ops.size(),
2690 struct APIntCompare {
2699 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists;
2700 for (
const SCEV *NewOp : NewOps)
2701 MulOpLists[
M.find(NewOp)->second].push_back(NewOp);
2704 if (AccumulatedConstant != 0)
2706 for (
auto &MulOp : MulOpLists) {
2707 if (MulOp.first == 1) {
2709 }
else if (MulOp.first != 0) {
2718 if (Ops.size() == 1)
2727 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) {
2731 if (isa<SCEVConstant>(MulOpSCEV))
2733 for (
unsigned AddOp = 0,
e = Ops.size(); AddOp !=
e; ++AddOp)
2734 if (MulOpSCEV == Ops[AddOp]) {
2749 if (Ops.size() == 2)
return OuterMul;
2751 Ops.
erase(Ops.begin()+AddOp);
2752 Ops.
erase(Ops.begin()+Idx-1);
2754 Ops.
erase(Ops.begin()+Idx);
2755 Ops.
erase(Ops.begin()+AddOp-1);
2757 Ops.push_back(OuterMul);
2762 for (
unsigned OtherMulIdx = Idx+1;
2763 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]);
2765 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]);
2769 OMulOp !=
e; ++OMulOp)
2770 if (OtherMul->
getOperand(OMulOp) == MulOpSCEV) {
2787 const SCEV *InnerMulSum =
2791 if (Ops.size() == 2)
return OuterMul;
2792 Ops.
erase(Ops.begin()+Idx);
2793 Ops.
erase(Ops.begin()+OtherMulIdx-1);
2794 Ops.push_back(OuterMul);
2804 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
scAddRecExpr)
2808 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
2814 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
2816 LIOps.push_back(Ops[
i]);
2817 Ops.
erase(Ops.begin()+
i);
2822 if (!LIOps.empty()) {
2826 LIOps.push_back(AddRec);
2831 LIOps.push_back(AddRec->
getStart());
2847 auto *DefI = getDefiningScopeBound(LIOps);
2849 if (!isGuaranteedToTransferExecutionTo(DefI, ReachI))
2861 if (Ops.size() == 1)
return NewRec;
2864 for (
unsigned i = 0;; ++
i)
2865 if (Ops[
i] == AddRec) {
2875 for (
unsigned OtherIdx = Idx+1;
2876 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2881 cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()->getHeader(),
2883 "AddRecExprs are not sorted in reverse dominance order?");
2884 if (AddRecLoop == cast<SCEVAddRecExpr>(Ops[OtherIdx])->getLoop()) {
2887 for (; OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
2889 const auto *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]);
2890 if (OtherAddRec->getLoop() == AddRecLoop) {
2891 for (
unsigned i = 0,
e = OtherAddRec->getNumOperands();
2893 if (
i >= AddRecOps.size()) {
2894 AddRecOps.
append(OtherAddRec->op_begin()+
i,
2895 OtherAddRec->op_end());
2899 AddRecOps[
i], OtherAddRec->getOperand(
i)};
2902 Ops.
erase(Ops.begin() + OtherIdx); --OtherIdx;
2917 return getOrCreateAddExpr(Ops, ComputeFlags(Ops));
2925 for (
const SCEV *
Op : Ops)
2932 std::uninitialized_copy(Ops.begin(), Ops.end(),
O);
2933 S =
new (SCEVAllocator)
2935 UniqueSCEVs.InsertNode(
S,
IP);
2938 S->setNoWrapFlags(Flags);
2947 for (
const SCEV *
Op : Ops)
2955 std::uninitialized_copy(Ops.begin(), Ops.end(),
O);
2956 S =
new (SCEVAllocator)
2958 UniqueSCEVs.InsertNode(
S,
IP);
2959 LoopUsers[L].push_back(
S);
2971 for (
const SCEV *
Op : Ops)
2978 std::uninitialized_copy(Ops.begin(), Ops.end(),
O);
2981 UniqueSCEVs.InsertNode(
S,
IP);
2984 S->setNoWrapFlags(Flags);
2990 if (
j > 1 && k /
j !=
i) Overflow =
true;
3006 if (
n == 0 ||
n == k)
return 1;
3007 if (k >
n)
return 0;
3023 struct FindConstantInAddMulChain {
3024 bool FoundConstant =
false;
3026 bool follow(
const SCEV *
S) {
3027 FoundConstant |= isa<SCEVConstant>(
S);
3028 return isa<SCEVAddExpr>(
S) || isa<SCEVMulExpr>(
S);
3031 bool isDone()
const {
3032 return FoundConstant;
3036 FindConstantInAddMulChain
F;
3038 ST.visitAll(StartExpr);
3039 return F.FoundConstant;
3047 "only nuw or nsw allowed");
3048 assert(!Ops.empty() &&
"Cannot get empty mul!");
3049 if (Ops.size() == 1)
return Ops[0];
3051 Type *ETy = Ops[0]->getType();
3053 for (
unsigned i = 1,
e = Ops.size();
i !=
e; ++
i)
3055 "SCEVMulExpr operand types don't match!");
3063 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3065 assert(Idx < Ops.size());
3066 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
3068 Ops[0] =
getConstant(LHSC->getAPInt() * RHSC->getAPInt());
3069 if (Ops.size() == 2)
return Ops[0];
3070 Ops.
erase(Ops.begin()+1);
3071 LHSC = cast<SCEVConstant>(Ops[0]);
3075 if (LHSC->getValue()->isZero())
3079 if (LHSC->getValue()->isOne()) {
3080 Ops.
erase(Ops.begin());
3084 if (Ops.size() == 1)
3095 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3100 if (
Mul->getNoWrapFlags(OrigFlags) != OrigFlags)
3101 Mul->setNoWrapFlags(ComputeFlags(Ops));
3105 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3106 if (Ops.size() == 2) {
3108 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
3122 if (Ops[0]->isAllOnesValue()) {
3125 if (
const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
3127 bool AnyFolded =
false;
3128 for (
const SCEV *AddOp : Add->operands()) {
3131 if (!isa<SCEVMulExpr>(
Mul)) AnyFolded =
true;
3132 NewOps.push_back(
Mul);
3136 }
else if (
const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
3139 for (
const SCEV *AddRecOp : AddRec->operands())
3151 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
scMulExpr)
3155 if (Idx < Ops.size()) {
3156 bool DeletedMul =
false;
3157 while (
const SCEVMulExpr *
Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
3162 Ops.
erase(Ops.begin()+Idx);
3177 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
scAddRecExpr)
3181 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
3187 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
3189 LIOps.push_back(Ops[
i]);
3190 Ops.
erase(Ops.begin()+
i);
3195 if (!LIOps.empty()) {
3214 if (Ops.size() == 1)
return NewRec;
3217 for (
unsigned i = 0;; ++
i)
3218 if (Ops[
i] == AddRec) {
3239 bool OpsModified =
false;
3240 for (
unsigned OtherIdx = Idx+1;
3241 OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
3244 dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
3245 if (!OtherAddRec || OtherAddRec->
getLoop() != AddRecLoop)
3254 bool Overflow =
false;
3261 for (
int y =
x, ye = 2*
x+1;
y != ye && !Overflow; ++
y) {
3265 z < ze && !Overflow; ++
z) {
3268 if (LargerThan64Bits)
3269 Coeff =
umul_ov(Coeff1, Coeff2, Overflow);
3271 Coeff = Coeff1*Coeff2;
3275 SumOps.push_back(
getMulExpr(CoeffTerm, Term1, Term2,
3280 SumOps.push_back(
getZero(Ty));
3286 if (Ops.size() == 2)
return NewAddRec;
3287 Ops[Idx] = NewAddRec;
3288 Ops.
erase(Ops.begin() + OtherIdx); --OtherIdx;
3290 AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
3304 return getOrCreateMulExpr(Ops, ComputeFlags(Ops));
3312 "SCEVURemExpr operand types don't match!");
3317 if (RHSC->getValue()->isOne())
3321 if (RHSC->getAPInt().isPowerOf2()) {
3340 "SCEVUDivExpr operand can't be pointer!");
3342 "SCEVUDivExpr operand types don't match!");
3349 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
3354 if (LHSC->getValue()->isZero())
3358 if (RHSC->getValue()->isOne())
3363 if (!RHSC->getValue()->isZero()) {
3368 unsigned LZ = RHSC->getAPInt().countLeadingZeros();
3372 if (!RHSC->getAPInt().isPowerOf2())
3378 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*
this))) {
3380 const APInt &StepInt = Step->getAPInt();
3381 const APInt &DivInt = RHSC->getAPInt();
3382 if (!StepInt.
urem(DivInt) &&
3388 for (
const SCEV *
Op : AR->operands())
3395 const SCEVConstant *StartC = dyn_cast<SCEVConstant>(AR->getStart());
3396 if (StartC && !DivInt.
urem(StepInt) &&
3402 const APInt &StartRem = StartInt.
urem(StepInt);
3403 if (StartRem != 0) {
3404 const SCEV *NewLHS =
3407 if (
LHS != NewLHS) {
3417 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
3426 for (
const SCEV *
Op :
M->operands())
3430 for (
unsigned i = 0,
e =
M->getNumOperands();
i !=
e; ++
i) {
3433 if (!isa<SCEVUDivExpr>(Div) &&
getMulExpr(Div, RHSC) ==
Op) {
3443 if (
auto *DivisorConstant =
3444 dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
3445 bool Overflow =
false;
3447 DivisorConstant->getAPInt().
umul_ov(RHSC->getAPInt(), Overflow);
3458 for (
const SCEV *
Op : A->operands())
3462 for (
unsigned i = 0,
e = A->getNumOperands();
i !=
e; ++
i) {
3464 if (isa<SCEVUDivExpr>(
Op) ||
3469 if (
Operands.size() == A->getNumOperands())
3476 Constant *LHSCV = LHSC->getValue();
3477 Constant *RHSCV = RHSC->getValue();
3487 if (
const SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP))
return S;
3490 UniqueSCEVs.InsertNode(
S,
IP);
3496 APInt A =
C1->getAPInt().abs();
3526 if (
const auto *LHSCst = dyn_cast<SCEVConstant>(
Mul->
getOperand(0))) {
3527 if (LHSCst == RHSCst) {
3535 APInt Factor =
gcd(LHSCst, RHSCst);
3538 cast<SCEVConstant>(
getConstant(LHSCst->getAPInt().udiv(Factor)));
3540 cast<SCEVConstant>(
getConstant(RHSCst->getAPInt().udiv(Factor)));
3546 Mul = dyn_cast<SCEVMulExpr>(
LHS);
3572 if (
const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step))
3573 if (StepChrec->getLoop() == L) {
3574 Operands.append(StepChrec->op_begin(), StepChrec->op_end());
3592 "SCEVAddRecExpr operand types don't match!");
3597 "SCEVAddRecExpr operand is not loop-invariant!");
3615 const Loop *NestedLoop = NestedAR->getLoop();
3621 Operands[0] = NestedAR->getStart();
3625 bool AllInvariant =
all_of(
3637 AllInvariant =
all_of(NestedOperands, [&](
const SCEV *
Op) {
3648 return getAddRecExpr(NestedOperands, NestedLoop, InnerFlags);
3658 return getOrCreateAddRecExpr(
Operands, L, Flags);
3668 const bool AssumeInBoundsFlags = [&]() {
3669 if (!
GEP->isInBounds())
3675 auto *GEPI = dyn_cast<Instruction>(
GEP);
3678 return GEPI && isSCEVExprNeverPoison(GEPI);
3685 bool FirstIter =
true;
3687 for (
const SCEV *IndexExpr : IndexExprs) {
3689 if (
StructType *STy = dyn_cast<StructType>(CurTy)) {
3691 ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue();
3692 unsigned FieldNo = Index->getZExtValue();
3694 Offsets.push_back(FieldOffset);
3697 CurTy = STy->getTypeAtIndex(Index);
3701 assert(isa<PointerType>(CurTy) &&
3702 "The first index of a GEP indexes a pointer");
3703 CurTy =
GEP->getSourceElementType();
3714 const SCEV *LocalOffset =
getMulExpr(IndexExpr, ElementSize, OffsetWrap);
3715 Offsets.push_back(LocalOffset);
3730 auto *GEPExpr =
getAddExpr(BaseExpr, Offset, BaseWrap);
3732 "GEP should not change type mid-flight.");
3736 SCEV *ScalarEvolution::findExistingSCEVInCache(
SCEVTypes SCEVType,
3739 ID.AddInteger(SCEVType);
3740 for (
const SCEV *
Op : Ops)
3743 return UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP);
3753 assert(SCEVMinMaxExpr::isMinMaxType(
Kind) &&
"Not a SCEVMinMaxExpr!");
3754 assert(!Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
3755 if (Ops.size() == 1)
return Ops[0];
3758 for (
unsigned i = 1,
e = Ops.size();
i !=
e; ++
i) {
3760 "Operand types don't match!");
3762 Ops[
i]->
getType()->isPointerTy() &&
3763 "min/max should be consistently pointerish");
3774 if (
const SCEV *
S = findExistingSCEVInCache(
Kind, Ops)) {
3780 if (
const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
3782 assert(Idx < Ops.size());
3795 while (
const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
3798 getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt()));
3800 Ops.
erase(Ops.begin()+1);
3801 if (Ops.size() == 1)
return Ops[0];
3802 LHSC = cast<SCEVConstant>(Ops[0]);
3805 bool IsMinV = LHSC->getValue()->isMinValue(IsSigned);
3806 bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned);
3808 if (IsMax ? IsMinV : IsMaxV) {
3810 Ops.
erase(Ops.begin());
3812 }
else if (IsMax ? IsMaxV : IsMinV) {
3818 if (Ops.size() == 1)
return Ops[0];
3822 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() <
Kind)
3827 if (Idx < Ops.size()) {
3828 bool DeletedAny =
false;
3829 while (Ops[Idx]->getSCEVType() ==
Kind) {
3831 Ops.
erase(Ops.begin()+Idx);
3849 for (
unsigned i = 0,
e = Ops.size() - 1;
i !=
e; ++
i) {
3850 if (Ops[
i] == Ops[
i + 1] ||
3851 isKnownViaNonRecursiveReasoning(FirstPred, Ops[
i], Ops[
i + 1])) {
3854 Ops.
erase(Ops.begin() +
i + 1, Ops.begin() +
i + 2);
3857 }
else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[
i],
3860 Ops.
erase(Ops.begin() +
i, Ops.begin() +
i + 1);
3866 if (Ops.size() == 1)
return Ops[0];
3868 assert(!Ops.empty() &&
"Reduced smax down to nothing!");
3874 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
3875 ID.AddPointer(Ops[
i]);
3877 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP);
3879 return ExistingSCEV;
3881 std::uninitialized_copy(Ops.begin(), Ops.end(),
O);
3882 SCEV *
S =
new (SCEVAllocator)
3885 UniqueSCEVs.InsertNode(
S,
IP);
3892 class SCEVSequentialMinMaxDeduplicatingVisitor final
3893 :
public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
3894 Optional<const SCEV *>> {
3906 return RootKind ==
Kind || NonSequentialRootKind ==
Kind;
3909 RetVal visitAnyMinMaxExpr(
const SCEV *
S) {
3910 assert((isa<SCEVMinMaxExpr>(
S) || isa<SCEVSequentialMinMaxExpr>(
S)) &&
3911 "Only for min/max expressions.");
3914 if (!canRecurseInto(
Kind))
3917 auto *NAry = cast<SCEVNAryExpr>(
S);
3927 return isa<SCEVSequentialMinMaxExpr>(
S)
3932 RetVal visit(
const SCEV *
S) {
3934 if (!SeenOps.
insert(
S).second)
3936 return Base::visit(
S);
3942 : SE(SE), RootKind(RootKind),
3943 NonSequentialRootKind(
3949 bool Changed =
false;
3953 for (
const SCEV *
Op : OrigOps) {
3954 RetVal NewOp = visit(
Op);
3976 RetVal visitAddExpr(
const SCEVAddExpr *Expr) {
return Expr; }
3978 RetVal visitMulExpr(
const SCEVMulExpr *Expr) {
return Expr; }
3980 RetVal visitUDivExpr(
const SCEVUDivExpr *Expr) {
return Expr; }
3982 RetVal visitAddRecExpr(
const SCEVAddRecExpr *Expr) {
return Expr; }
3985 return visitAnyMinMaxExpr(Expr);
3989 return visitAnyMinMaxExpr(Expr);
3993 return visitAnyMinMaxExpr(Expr);
3997 return visitAnyMinMaxExpr(Expr);
4001 return visitAnyMinMaxExpr(Expr);
4004 RetVal visitUnknown(
const SCEVUnknown *Expr) {
return Expr; }
4021 struct SCEVPoisonCollector {
4022 bool LookThroughSeq;
4024 SCEVPoisonCollector(
bool LookThroughSeq) : LookThroughSeq(LookThroughSeq) {}
4026 bool follow(
const SCEV *
S) {
4029 if (!LookThroughSeq && isa<SCEVSequentialMinMaxExpr>(
S))
4032 if (
auto *SU = dyn_cast<SCEVUnknown>(
S)) {
4038 bool isDone()
const {
return false; }
4044 SCEVPoisonCollector PC1(
true);
4049 if (PC1.MaybePoison.empty())
4055 SCEVPoisonCollector PC2(
false);
4060 return all_of(PC1.MaybePoison,
4061 [&](
const SCEV *
S) { return PC2.MaybePoison.contains(S); });
4067 assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(
Kind) &&
4068 "Not a SCEVSequentialMinMaxExpr!");
4069 assert(!Ops.empty() &&
"Cannot get empty (u|s)(min|max)!");
4070 if (Ops.size() == 1)
4074 for (
unsigned i = 1,
e = Ops.size();
i !=
e; ++
i) {
4076 "Operand types don't match!");
4078 Ops[
i]->
getType()->isPointerTy() &&
4079 "min/max should be consistently pointerish");
4087 if (
const SCEV *
S = findExistingSCEVInCache(
Kind, Ops))
4094 SCEVSequentialMinMaxDeduplicatingVisitor Deduplicator(*
this,
Kind);
4095 bool Changed = Deduplicator.visit(
Kind, Ops, Ops);
4104 bool DeletedAny =
false;
4105 while (Idx < Ops.size()) {
4106 if (Ops[Idx]->getSCEVType() !=
Kind) {
4110 const auto *SMME = cast<SCEVSequentialMinMaxExpr>(Ops[Idx]);
4111 Ops.
erase(Ops.begin() + Idx);
4112 Ops.
insert(Ops.begin() + Idx, SMME->op_begin(), SMME->op_end());
4120 const SCEV *SaturationPoint;
4131 for (
unsigned i = 1,
e = Ops.size();
i !=
e; ++
i) {
4142 Ops.
erase(Ops.begin() +
i);
4147 if (isKnownViaNonRecursiveReasoning(Pred, Ops[
i - 1], Ops[
i])) {
4148 Ops.
erase(Ops.begin() +
i);
4157 for (
unsigned i = 0,
e = Ops.size();
i !=
e; ++
i)
4158 ID.AddPointer(Ops[
i]);
4160 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP);
4162 return ExistingSCEV;
4165 std::uninitialized_copy(Ops.begin(), Ops.end(),
O);
4166 SCEV *
S =
new (SCEVAllocator)
4169 UniqueSCEVs.InsertNode(
S,
IP);
4227 if (
auto *ScalableAllocTy = dyn_cast<ScalableVectorType>(AllocTy))
4236 if (
auto *ScalableStoreTy = dyn_cast<ScalableVectorType>(StoreTy))
4251 IntTy,
getDataLayout().getStructLayout(STy)->getElementOffset(FieldNo));
4264 if (
SCEV *
S = UniqueSCEVs.FindNodeOrInsertPos(
ID,
IP)) {
4265 assert(cast<SCEVUnknown>(
S)->getValue() == V &&
4266 "Stale SCEVUnknown in uniquing map!");
4271 FirstUnknown = cast<SCEVUnknown>(
S);
4272 UniqueSCEVs.InsertNode(
S,
IP);
4320 bool PreciseA, PreciseB;
4321 auto *ScopeA = getDefiningScopeBound({A}, PreciseA);
4322 auto *ScopeB = getDefiningScopeBound({
B}, PreciseB);
4323 if (!PreciseA || !PreciseB)
4326 return (ScopeA == ScopeB) || DT.
dominates(ScopeA, ScopeB) ||
4332 return CouldNotCompute.get();
4335 bool ScalarEvolution::checkValidity(
const SCEV *
S)
const {
4337 auto *SU = dyn_cast<SCEVUnknown>(
S);
4338 return SU && SU->getValue() ==
nullptr;
4341 return !ContainsNulls;
4346 if (
I != HasRecMap.
end())
4351 HasRecMap.
insert({
S, FoundAddRec});
4359 if (
SI == ExprValueMap.
end())
4368 return SI->second.getArrayRef();
4374 void ScalarEvolution::eraseValueFromMap(
Value *V) {
4376 if (
I != ValueExprMap.
end()) {
4377 auto EVIt = ExprValueMap.
find(
I->second);
4378 bool Removed = EVIt->second.remove(V);
4380 assert(Removed &&
"Value not in ExprValueMap?");
4385 void ScalarEvolution::insertValueToMap(
Value *V,
const SCEV *
S) {
4389 auto It = ValueExprMap.
find_as(V);
4390 if (It == ValueExprMap.
end()) {
4401 const SCEV *
S = getExistingSCEV(V);
4407 std::pair<ValueExprMapType::iterator, bool> Pair =
4415 const SCEV *ScalarEvolution::getExistingSCEV(
Value *V) {
4419 if (
I != ValueExprMap.
end()) {
4420 const SCEV *
S =
I->second;
4422 "existing SCEV has not been properly invalidated");
4442 const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr);
4443 if (!Add || Add->getNumOperands() != 2 ||
4444 !Add->getOperand(0)->isAllOnesValue())
4447 const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1));
4467 for (
const SCEV *Operand : MME->operands()) {
4470 return (
const SCEV *)
nullptr;
4471 MatchedOperands.push_back(Matched);
4476 if (
const SCEV *Replaced = MatchMinMaxNegation(MME))
4486 assert(
P->getType()->isPointerTy());
4488 if (
auto *AddRec = dyn_cast<SCEVAddRecExpr>(
P)) {
4496 if (
auto *Add = dyn_cast<SCEVAddExpr>(
P)) {
4499 const SCEV **PtrOp =
nullptr;
4500 for (
const SCEV *&AddOp : Ops) {
4501 if (AddOp->getType()->isPointerTy()) {
4502 assert(!PtrOp &&
"Cannot have multiple pointer ops");
4536 const bool RHSIsNotMinSigned =
4569 "Cannot truncate or zero extend with non-integer arguments!");
4581 "Cannot truncate or zero extend with non-integer arguments!");
4593 "Cannot noop or zero extend with non-integer arguments!");
4595 "getNoopOrZeroExtend cannot truncate!");
4605 "Cannot noop or sign extend with non-integer arguments!");
4607 "getNoopOrSignExtend cannot truncate!");