Lines Matching refs:SCEV
254 LLVM_DUMP_METHOD void SCEV::dump() const { in dump()
260 void SCEV::print(raw_ostream &OS) const { in print()
267 const SCEV *Op = PtrToInt->getOperand(); in print()
274 const SCEV *Op = Trunc->getOperand(); in print()
281 const SCEV *Op = ZExt->getOperand(); in print()
288 const SCEV *Op = SExt->getOperand(); in print()
338 for (const SCEV *Op : NAry->operands()) in print()
392 Type *SCEV::getType() const { in getType()
424 bool SCEV::isZero() const { in isZero()
430 bool SCEV::isOne() const { in isOne()
436 bool SCEV::isAllOnesValue() const { in isAllOnesValue()
442 bool SCEV::isNonConstantNegative() const { in isNonConstantNegative()
455 SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} in SCEVCouldNotCompute()
457 bool SCEVCouldNotCompute::classof(const SCEV *S) { in classof()
461 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { in getConstant()
466 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getConstant()
467 SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V); in getConstant()
472 const SCEV *ScalarEvolution::getConstant(const APInt &Val) { in getConstant()
476 const SCEV *
483 const SCEV *op, Type *ty) in SCEVCastExpr()
484 : SCEV(ID, SCEVTy, computeExpressionSize(op)), Ty(ty) { in SCEVCastExpr()
488 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, in SCEVPtrToIntExpr()
496 SCEVTypes SCEVTy, const SCEV *op, in SCEVIntegralCastExpr()
500 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, in SCEVTruncateExpr()
508 const SCEV *op, Type *ty) in SCEVZeroExtendExpr()
515 const SCEV *op, Type *ty) in SCEVSignExtendExpr()
707 CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV, in CompareSCEVComplexity()
709 const LoopInfo *const LI, const SCEV *LHS, in CompareSCEVComplexity()
710 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) { in CompareSCEVComplexity()
863 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, in GroupByComplexity()
867 EquivalenceClasses<const SCEV *> EqCacheSCEV; in GroupByComplexity()
871 auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
879 const SCEV *&LHS = Ops[0], *&RHS = Ops[1]; in GroupByComplexity()
886 llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
895 const SCEV *S = Ops[i]; in GroupByComplexity()
913 static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { in hasHugeExpression()
914 return any_of(Ops, [](const SCEV *S) { in hasHugeExpression()
924 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, in BinomialCoefficient()
1018 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); in BinomialCoefficient()
1020 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i)); in BinomialCoefficient()
1026 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); in BinomialCoefficient()
1042 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, in evaluateAtIteration()
1047 const SCEV *
1048 SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands, in evaluateAtIteration()
1049 const SCEV *It, ScalarEvolution &SE) { in evaluateAtIteration()
1051 const SCEV *Result = Operands[0]; in evaluateAtIteration()
1056 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType()); in evaluateAtIteration()
1069 const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op, in getLosslessPtrToIntExpr()
1087 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getLosslessPtrToIntExpr()
1117 SCEV *S = new (SCEVAllocator) in getLosslessPtrToIntExpr()
1144 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE) { in getLosslessPtrToIntExpr()
1149 const SCEV *visit(const SCEV *S) { in getLosslessPtrToIntExpr()
1158 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { in getLosslessPtrToIntExpr()
1159 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1168 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { in getLosslessPtrToIntExpr()
1169 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1178 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in getLosslessPtrToIntExpr()
1186 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(Op, *this); in getLosslessPtrToIntExpr()
1193 const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) { in getPtrToIntExpr()
1196 const SCEV *IntOp = getLosslessPtrToIntExpr(Op); in getPtrToIntExpr()
1203 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty, in getTruncateExpr()
1217 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getTruncateExpr()
1237 SCEV *S = in getTruncateExpr()
1250 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1254 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1); in getTruncateExpr()
1271 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getTruncateExpr()
1277 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1278 for (const SCEV *Op : AddRec->operands()) in getTruncateExpr()
1280 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); in getTruncateExpr()
1291 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), in getTruncateExpr()
1301 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step, in getSignedOverflowLimitForStep()
1321 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step, in getUnsignedOverflowLimitForStep()
1334 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *,
1353 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
1357 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1369 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
1373 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1393 static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, in getPreStartForExtend()
1399 const SCEV *Start = AR->getStart(); in getPreStartForExtend()
1400 const SCEV *Step = AR->getStepRecurrence(*SE); in getPreStartForExtend()
1410 SmallVector<const SCEV *, 4> DiffOps; in getPreStartForExtend()
1411 for (const SCEV *Op : SA->operands()) in getPreStartForExtend()
1423 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW); in getPreStartForExtend()
1424 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags); in getPreStartForExtend()
1426 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap)); in getPreStartForExtend()
1432 const SCEV *BECount = SE->getBackedgeTakenCount(L); in getPreStartForExtend()
1440 const SCEV *OperandExtendedStart = in getPreStartForExtend()
1455 const SCEV *OverflowLimit = in getPreStartForExtend()
1467 static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, in getExtendAddRecStart()
1472 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth); in getExtendAddRecStart()
1514 bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start, in proveNoWrapByVaryingStart()
1515 const SCEV *Step, in proveNoWrapByVaryingStart()
1530 const SCEV *PreStart = getConstant(StartAI - Delta); in proveNoWrapByVaryingStart()
1544 const SCEV *DeltaS = getConstant(StartC->getType(), Delta); in proveNoWrapByVaryingStart()
1546 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep( in proveNoWrapByVaryingStart()
1584 const SCEV *Step) { in extractConstantWithoutWrapping()
1593 const SCEV *
1594 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getZeroExtendExpr()
1618 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExpr()
1620 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExpr()
1631 const SCEV *X = ST->getOperand(); in getZeroExtendExpr()
1646 const SCEV *Start = AR->getStart(); in getZeroExtendExpr()
1647 const SCEV *Step = AR->getStepRecurrence(*this); in getZeroExtendExpr()
1673 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getZeroExtendExpr()
1679 const SCEV *CastedMaxBECount = in getZeroExtendExpr()
1681 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getZeroExtendExpr()
1686 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step, in getZeroExtendExpr()
1687 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExpr()
1688 const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul, in getZeroExtendExpr()
1689 SCEV::FlagAnyWrap, in getZeroExtendExpr()
1692 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1); in getZeroExtendExpr()
1693 const SCEV *WideMaxBECount = in getZeroExtendExpr()
1695 const SCEV *OperandExtendedAdd = in getZeroExtendExpr()
1699 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExpr()
1700 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExpr()
1703 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExpr()
1716 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExpr()
1717 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExpr()
1721 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExpr()
1757 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - in getZeroExtendExpr()
1764 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExpr()
1781 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExpr()
1782 const SCEV *SResidual = in getZeroExtendExpr()
1784 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExpr()
1786 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExpr()
1792 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExpr()
1802 const SCEV *LHS; in getZeroExtendExpr()
1803 const SCEV *RHS; in getZeroExtendExpr()
1819 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExpr()
1822 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExpr()
1836 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExpr()
1837 const SCEV *SResidual = in getZeroExtendExpr()
1838 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getZeroExtendExpr()
1839 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExpr()
1841 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExpr()
1852 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExpr()
1855 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExpr()
1881 SCEV::FlagNUW, Depth + 1); in getZeroExtendExpr()
1887 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExpr()
1888 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExpr()
1895 const SCEV *
1896 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getSignExtendExpr()
1924 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExpr()
1927 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExpr()
1938 const SCEV *X = ST->getOperand(); in getSignExtendExpr()
1952 SmallVector<const SCEV *, 4> Ops; in getSignExtendExpr()
1955 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1); in getSignExtendExpr()
1970 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExpr()
1971 const SCEV *SResidual = in getSignExtendExpr()
1972 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getSignExtendExpr()
1973 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExpr()
1975 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExpr()
1986 const SCEV *Start = AR->getStart(); in getSignExtendExpr()
1987 const SCEV *Step = AR->getStepRecurrence(*this); in getSignExtendExpr()
2002 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW); in getSignExtendExpr()
2013 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getSignExtendExpr()
2020 const SCEV *CastedMaxBECount = in getSignExtendExpr()
2022 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getSignExtendExpr()
2027 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step, in getSignExtendExpr()
2028 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExpr()
2029 const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul, in getSignExtendExpr()
2030 SCEV::FlagAnyWrap, in getSignExtendExpr()
2033 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1); in getSignExtendExpr()
2034 const SCEV *WideMaxBECount = in getSignExtendExpr()
2036 const SCEV *OperandExtendedAdd = in getSignExtendExpr()
2040 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExpr()
2041 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExpr()
2044 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExpr()
2057 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExpr()
2058 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExpr()
2068 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getSignExtendExpr()
2099 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExpr()
2100 const SCEV *SResidual = in getSignExtendExpr()
2102 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExpr()
2104 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExpr()
2110 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExpr()
2125 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExpr()
2126 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExpr()
2133 const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op, in getCastExpr()
2151 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, in getAnyExtendExpr()
2166 const SCEV *NewOp = T->getOperand(); in getAnyExtendExpr()
2173 const SCEV *ZExt = getZeroExtendExpr(Op, Ty); in getAnyExtendExpr()
2178 const SCEV *SExt = getSignExtendExpr(Op, Ty); in getAnyExtendExpr()
2184 SmallVector<const SCEV *, 4> Ops; in getAnyExtendExpr()
2185 for (const SCEV *Op : AR->operands()) in getAnyExtendExpr()
2187 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW); in getAnyExtendExpr()
2222 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, in CollectAddOperandsWithScales() argument
2223 SmallVectorImpl<const SCEV *> &NewOps, in CollectAddOperandsWithScales()
2225 const SCEV *const *Ops, size_t NumOperands, in CollectAddOperandsWithScales()
2257 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands())); in CollectAddOperandsWithScales()
2258 const SCEV *Key = SE.getMulExpr(MulOps); in CollectAddOperandsWithScales()
2271 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = in CollectAddOperandsWithScales()
2288 const SCEV *LHS, const SCEV *RHS) { in willNotOverflow()
2289 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *, in willNotOverflow()
2290 SCEV::NoWrapFlags, unsigned); in willNotOverflow()
2305 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) = in willNotOverflow()
2314 const SCEV *A = (this->*Extension)( in willNotOverflow()
2315 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0); in willNotOverflow()
2316 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0); in willNotOverflow()
2317 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0); in willNotOverflow()
2318 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0); in willNotOverflow()
2322 Optional<SCEV::NoWrapFlags>
2329 SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap; in getStrengthenedNoWrapFlagsFromBinOp()
2332 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2334 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2343 const SCEV *LHS = getSCEV(OBO->getOperand(0)); in getStrengthenedNoWrapFlagsFromBinOp()
2344 const SCEV *RHS = getSCEV(OBO->getOperand(1)); in getStrengthenedNoWrapFlagsFromBinOp()
2349 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2356 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2368 static SCEV::NoWrapFlags
2370 const ArrayRef<const SCEV *> Ops, in StrengthenNoWrapFlags()
2371 SCEV::NoWrapFlags Flags) { in StrengthenNoWrapFlags()
2381 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; in StrengthenNoWrapFlags()
2382 SCEV::NoWrapFlags SignOrUnsignWrap = in StrengthenNoWrapFlags()
2386 auto IsKnownNonNegative = [&](const SCEV *S) { in StrengthenNoWrapFlags()
2390 if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative)) in StrengthenNoWrapFlags()
2392 ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); in StrengthenNoWrapFlags()
2414 if (!(SignOrUnsignWrap & SCEV::FlagNSW)) { in StrengthenNoWrapFlags()
2418 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in StrengthenNoWrapFlags()
2422 if (!(SignOrUnsignWrap & SCEV::FlagNUW)) { in StrengthenNoWrapFlags()
2426 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2432 if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) && in StrengthenNoWrapFlags()
2433 !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 && in StrengthenNoWrapFlags()
2435 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2438 if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && in StrengthenNoWrapFlags()
2442 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2445 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2451 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) { in isAvailableAtLoopEntry()
2456 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, in getAddExpr()
2457 SCEV::NoWrapFlags OrigFlags, in getAddExpr()
2459 assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && in getAddExpr()
2469 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); }); in getAddExpr()
2499 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getAddExpr()
2507 if (SCEV *S = findExistingSCEVInCache(scAddExpr, Ops)) { in getAddExpr()
2527 const SCEV *Scale = getConstant(Ty, Count); in getAddExpr()
2528 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2558 SmallVector<const SCEV *, 8> LargeOps; in getAddExpr()
2572 SmallVector<const SCEV *, 8> LargeMulOps; in getAddExpr()
2589 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2597 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2608 const SCEV *A = Ops[0]; in getAddExpr()
2609 const SCEV *B = Ops[1]; in getAddExpr()
2615 SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap; in getAddExpr()
2620 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNUW) && in getAddExpr()
2623 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW); in getAddExpr()
2628 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNSW) && in getAddExpr()
2632 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW); in getAddExpr()
2635 if (PreservedFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2636 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands()); in getAddExpr()
2648 const SCEV *X; in getAddExpr()
2649 const SCEV *Y; in getAddExpr()
2666 SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW); in getAddExpr()
2694 DenseMap<const SCEV *, APInt> M; in getAddExpr()
2695 SmallVector<const SCEV *, 8> NewOps; in getAddExpr()
2709 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists; in getAddExpr()
2710 for (const SCEV *NewOp : NewOps) in getAddExpr()
2718 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2722 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1), in getAddExpr()
2723 SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2730 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2740 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); in getAddExpr()
2746 const SCEV *InnerMul = Mul->getOperand(MulOp == 0); in getAddExpr()
2750 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(), in getAddExpr()
2753 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2755 SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul}; in getAddExpr()
2756 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2757 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV, in getAddExpr()
2758 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2768 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2782 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); in getAddExpr()
2784 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(), in getAddExpr()
2787 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2789 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); in getAddExpr()
2791 SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(), in getAddExpr()
2794 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2796 SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2}; in getAddExpr()
2797 const SCEV *InnerMulSum = in getAddExpr()
2798 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2799 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum, in getAddExpr()
2800 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2805 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2821 SmallVector<const SCEV *, 8> LIOps; in getAddExpr()
2837 SCEV::NoWrapFlags Flags = ComputeFlags(LIOps); in getAddExpr()
2843 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2855 SCEV::NoWrapFlags AddFlags = Flags; in getAddExpr()
2856 if (AddFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2860 AddFlags = SCEV::FlagAnyWrap; in getAddExpr()
2867 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); in getAddExpr()
2868 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); in getAddExpr()
2879 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2896 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2908 SmallVector<const SCEV *, 2> TwoOps = { in getAddExpr()
2910 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2916 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); in getAddExpr()
2917 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2930 const SCEV *
2931 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddExpr()
2932 SCEV::NoWrapFlags Flags) { in getOrCreateAddExpr()
2935 for (const SCEV *Op : Ops) in getOrCreateAddExpr()
2941 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddExpr()
2952 const SCEV *
2953 ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddRecExpr()
2954 const Loop *L, SCEV::NoWrapFlags Flags) { in getOrCreateAddRecExpr()
2957 for (const SCEV *Op : Ops) in getOrCreateAddRecExpr()
2964 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddRecExpr()
2976 const SCEV *
2977 ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, in getOrCreateMulExpr()
2978 SCEV::NoWrapFlags Flags) { in getOrCreateMulExpr()
2981 for (const SCEV *Op : Ops) in getOrCreateMulExpr()
2987 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateMulExpr()
3032 static bool containsConstantInAddMulChain(const SCEV *StartExpr) { in containsConstantInAddMulChain()
3036 bool follow(const SCEV *S) { in containsConstantInAddMulChain()
3053 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, in getMulExpr()
3054 SCEV::NoWrapFlags OrigFlags, in getMulExpr()
3056 assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) && in getMulExpr()
3099 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getMulExpr()
3107 if (SCEV *S = findExistingSCEVInCache(scMulExpr, Ops)) { in getMulExpr()
3126 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0), in getMulExpr()
3127 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3128 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1), in getMulExpr()
3129 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3130 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3137 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3139 for (const SCEV *AddOp : Add->operands()) { in getMulExpr()
3140 const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap, in getMulExpr()
3146 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3149 SmallVector<const SCEV *, 4> Operands; in getMulExpr()
3150 for (const SCEV *AddRecOp : AddRec->operands()) in getMulExpr()
3151 Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap, in getMulExpr()
3155 AddRec->getNoWrapFlags(SCEV::FlagNW)); in getMulExpr()
3182 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3195 SmallVector<const SCEV *, 8> LIOps; in getMulExpr()
3208 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3210 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3213 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3220 SCEV::NoWrapFlags Flags = ComputeFlags({Scale, AddRec}); in getMulExpr()
3221 const SCEV *NewRec = getAddRecExpr( in getMulExpr()
3233 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3268 SmallVector<const SCEV*, 7> AddRecOps; in getMulExpr()
3271 SmallVector <const SCEV *, 7> SumOps; in getMulExpr()
3283 const SCEV *CoeffTerm = getConstant(Ty, Coeff); in getMulExpr()
3284 const SCEV *Term1 = AddRec->getOperand(y-z); in getMulExpr()
3285 const SCEV *Term2 = OtherAddRec->getOperand(z); in getMulExpr()
3287 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3292 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3295 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRecLoop, in getMulExpr()
3296 SCEV::FlagAnyWrap); in getMulExpr()
3307 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3319 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, in getURemExpr()
3320 const SCEV *RHS) { in getURemExpr()
3341 const SCEV *UDiv = getUDivExpr(LHS, RHS); in getURemExpr()
3342 const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW); in getURemExpr()
3343 return getMinusSCEV(LHS, Mult, SCEV::FlagNUW); in getURemExpr()
3348 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, in getUDivExpr()
3349 const SCEV *RHS) { in getUDivExpr()
3360 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3397 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3398 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3399 for (const SCEV *Op : AR->operands()) in getUDivExpr()
3401 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3411 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3415 const SCEV *NewLHS = in getUDivExpr()
3417 AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3428 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3436 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3437 for (const SCEV *Op : M->operands()) in getUDivExpr()
3442 const SCEV *Op = M->getOperand(i); in getUDivExpr()
3443 const SCEV *Div = getUDivExpr(Op, RHSC); in getUDivExpr()
3445 Operands = SmallVector<const SCEV *, 4>(M->operands()); in getUDivExpr()
3468 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3469 for (const SCEV *Op : A->operands()) in getUDivExpr()
3474 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); in getUDivExpr()
3494 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getUDivExpr()
3495 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), in getUDivExpr()
3520 const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS, in getUDivExactExpr()
3521 const SCEV *RHS) { in getUDivExactExpr()
3535 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands())); in getUDivExactExpr()
3548 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3562 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3574 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, in getAddRecExpr()
3576 SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3577 SmallVector<const SCEV *, 4> Operands; in getAddRecExpr()
3582 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW)); in getAddRecExpr()
3591 const SCEV *
3592 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, in getAddRecExpr()
3593 const Loop *L, SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3609 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X in getAddRecExpr()
3627 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands()); in getAddRecExpr()
3633 Operands, [&](const SCEV *Op) { return isLoopInvariant(Op, L); }); in getAddRecExpr()
3640 SCEV::NoWrapFlags OuterFlags = in getAddRecExpr()
3641 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); in getAddRecExpr()
3644 AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) { in getAddRecExpr()
3653 SCEV::NoWrapFlags InnerFlags = in getAddRecExpr()
3654 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); in getAddRecExpr()
3668 const SCEV *
3670 const SmallVectorImpl<const SCEV *> &IndexExprs) { in getGEPExpr()
3671 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); in getGEPExpr()
3688 SCEV::NoWrapFlags OffsetWrap = in getGEPExpr()
3689 AssumeInBoundsFlags ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getGEPExpr()
3693 SmallVector<const SCEV *, 4> Offsets; in getGEPExpr()
3694 for (const SCEV *IndexExpr : IndexExprs) { in getGEPExpr()
3700 const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); in getGEPExpr()
3716 const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); in getGEPExpr()
3721 const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, OffsetWrap); in getGEPExpr()
3731 const SCEV *Offset = getAddExpr(Offsets, OffsetWrap); in getGEPExpr()
3735 SCEV::NoWrapFlags BaseWrap = AssumeInBoundsFlags && isKnownNonNegative(Offset) in getGEPExpr()
3736 ? SCEV::FlagNUW : SCEV::FlagAnyWrap; in getGEPExpr()
3743 SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType, in findExistingSCEVInCache()
3744 ArrayRef<const SCEV *> Ops) { in findExistingSCEVInCache()
3747 for (const SCEV *Op : Ops) in findExistingSCEVInCache()
3753 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) { in getAbsExpr()
3754 SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getAbsExpr()
3758 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind, in getMinMaxExpr()
3759 SmallVectorImpl<const SCEV *> &Ops) { in getMinMaxExpr()
3781 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) { in getMinMaxExpr()
3884 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getMinMaxExpr()
3887 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getMinMaxExpr()
3889 SCEV *S = new (SCEVAllocator) in getMinMaxExpr()
3901 Optional<const SCEV *>> {
3902 using RetVal = Optional<const SCEV *>;
3908 SmallPtrSet<const SCEV *, 16> SeenOps;
3916 RetVal visitAnyMinMaxExpr(const SCEV *S) { in visitAnyMinMaxExpr()
3925 SmallVector<const SCEV *> NewOps; in visitAnyMinMaxExpr()
3939 RetVal visit(const SCEV *S) { in visit()
3954 bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps, in visit()
3955 SmallVectorImpl<const SCEV *> &NewOps) { in visit()
3957 SmallVector<const SCEV *> Ops; in visit()
3960 for (const SCEV *Op : OrigOps) { in visit()
4019 static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) { in impliesPoison()
4030 SmallPtrSet<const SCEV *, 4> MaybePoison; in impliesPoison()
4033 bool follow(const SCEV *S) { in impliesPoison()
4068 [&](const SCEV *S) { return PC2.MaybePoison.contains(S); }); in impliesPoison()
4071 const SCEV *
4073 SmallVectorImpl<const SCEV *> &Ops) { in getSequentialMinMaxExpr()
4094 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) in getSequentialMinMaxExpr()
4127 const SCEV *SaturationPoint; in getSequentialMinMaxExpr()
4145 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]}; in getSequentialMinMaxExpr()
4167 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getSequentialMinMaxExpr()
4171 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getSequentialMinMaxExpr()
4173 SCEV *S = new (SCEVAllocator) in getSequentialMinMaxExpr()
4181 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getSMaxExpr()
4182 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getSMaxExpr()
4186 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMaxExpr()
4190 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getUMaxExpr()
4191 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getUMaxExpr()
4195 const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getUMaxExpr()
4199 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, in getSMinExpr()
4200 const SCEV *RHS) { in getSMinExpr()
4201 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getSMinExpr()
4205 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMinExpr()
4209 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS, in getUMinExpr()
4211 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinExpr()
4215 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops, in getUMinExpr()
4221 const SCEV *
4233 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) { in getSizeOfExpr()
4242 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) { in getStoreSizeOfExpr()
4251 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy, in getOffsetOfExpr()
4261 const SCEV *ScalarEvolution::getUnknown(Value *V) { in getUnknown()
4271 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) { in getUnknown()
4276 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this, in getUnknown()
4323 bool ScalarEvolution::instructionCouldExistWitthOperands(const SCEV *A, in instructionCouldExistWitthOperands()
4324 const SCEV *B) { in instructionCouldExistWitthOperands()
4338 const SCEV *ScalarEvolution::getCouldNotCompute() { in getCouldNotCompute()
4342 bool ScalarEvolution::checkValidity(const SCEV *S) const { in checkValidity()
4343 bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) { in checkValidity()
4351 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { in containsAddRecurrence()
4357 SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); }); in containsAddRecurrence()
4364 ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) { in getSCEVValues()
4392 void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) { in insertValueToMap()
4405 const SCEV *ScalarEvolution::getSCEV(Value *V) { in getSCEV()
4408 if (const SCEV *S = getExistingSCEV(V)) in getSCEV()
4413 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { in getExistingSCEV()
4418 const SCEV *S = I->second; in getExistingSCEV()
4427 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, in getNegativeSCEV()
4428 SCEV::NoWrapFlags Flags) { in getNegativeSCEV()
4439 static const SCEV *MatchNotExpr(const SCEV *Expr) { in MatchNotExpr()
4454 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { in getNotSCEV()
4464 SmallVector<const SCEV *, 2> MatchedOperands; in getNotSCEV()
4465 for (const SCEV *Operand : MME->operands()) { in getNotSCEV()
4466 const SCEV *Matched = MatchNotExpr(Operand); in getNotSCEV()
4468 return (const SCEV *)nullptr; in getNotSCEV()
4474 if (const SCEV *Replaced = MatchMinMaxNegation(MME)) in getNotSCEV()
4483 const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) { in removePointerBase()
4488 SmallVector<const SCEV *> Ops{AddRec->operands()}; in removePointerBase()
4492 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap); in removePointerBase()
4496 SmallVector<const SCEV *> Ops{Add->operands()}; in removePointerBase()
4497 const SCEV **PtrOp = nullptr; in removePointerBase()
4498 for (const SCEV *&AddOp : Ops) { in removePointerBase()
4513 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, in getMinusSCEV()
4514 SCEV::NoWrapFlags Flags, in getMinusSCEV()
4533 auto AddFlags = SCEV::FlagAnyWrap; in getMinusSCEV()
4536 if (hasFlags(Flags, SCEV::FlagNSW)) { in getMinusSCEV()
4547 AddFlags = SCEV::FlagNSW; in getMinusSCEV()
4558 auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getMinusSCEV()
4563 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty, in getTruncateOrZeroExtend()
4575 const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty, in getTruncateOrSignExtend()
4587 const SCEV *
4588 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { in getNoopOrZeroExtend()
4599 const SCEV *
4600 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { in getNoopOrSignExtend()
4611 const SCEV *
4612 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { in getNoopOrAnyExtend()
4623 const SCEV *
4624 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { in getTruncateOrNoop()
4635 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, in getUMaxFromMismatchedTypes()
4636 const SCEV *RHS) { in getUMaxFromMismatchedTypes()
4637 const SCEV *PromotedLHS = LHS; in getUMaxFromMismatchedTypes()
4638 const SCEV *PromotedRHS = RHS; in getUMaxFromMismatchedTypes()
4648 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, in getUMinFromMismatchedTypes()
4649 const SCEV *RHS, in getUMinFromMismatchedTypes()
4651 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinFromMismatchedTypes()
4655 const SCEV *
4656 ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops, in getUMinFromMismatchedTypes()
4673 SmallVector<const SCEV *, 2> PromotedOps; in getUMinFromMismatchedTypes()
4681 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { in getPointerBase()
4690 const SCEV *PtrOp = nullptr; in getPointerBase()
4691 for (const SCEV *AddOp : Add->operands()) { in getPointerBase()
4725 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
4728 const SCEV *Result = Rewriter.visit(S); in rewrite()
4736 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4742 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4769 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) { in rewrite()
4771 const SCEV *Result = Rewriter.visit(S); in rewrite()
4777 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4783 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4810 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
4829 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4830 const SCEV *Result = Expr; in visitUnknown()
4838 Optional<const SCEV *> Res = in visitUnknown()
4847 Optional<const SCEV *> Res = compareWithBackedgeCondition(I); in visitUnknown()
4863 Optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
4872 Optional<const SCEV *>
4886 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
4889 const SCEV *Result = Rewriter.visit(S); in rewrite()
4893 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4900 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4919 SCEV::NoWrapFlags
4922 return SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
4926 SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
4935 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW); in proveNoWrapViaConstantRanges()
4945 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW); in proveNoWrapViaConstantRanges()
4951 SCEV::NoWrapFlags
4953 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoSignedWrapViaInduction()
4961 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoSignedWrapViaInduction()
4972 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoSignedWrapViaInduction()
4991 const SCEV *OverflowLimit = in proveNoSignedWrapViaInduction()
4996 Result = setFlags(Result, SCEV::FlagNSW); in proveNoSignedWrapViaInduction()
5000 SCEV::NoWrapFlags
5002 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoUnsignedWrapViaInduction()
5010 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoUnsignedWrapViaInduction()
5022 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoUnsignedWrapViaInduction()
5041 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - in proveNoUnsignedWrapViaInduction()
5045 Result = setFlags(Result, SCEV::FlagNUW); in proveNoUnsignedWrapViaInduction()
5181 static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, in isSimpleCastedPHI()
5210 const SCEV *X = Trunc->getOperand(); in isSimpleCastedPHI()
5279 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5313 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHIWithCastsImpl()
5339 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHIWithCastsImpl()
5343 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHIWithCastsImpl()
5401 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHIWithCastsImpl()
5402 const SCEV *PHISCEV = in createAddRecFromPHIWithCastsImpl()
5404 getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5429 auto getExtendedExpr = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5430 bool CreateSignExtend) -> const SCEV * { in createAddRecFromPHIWithCastsImpl()
5432 const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy); in createAddRecFromPHIWithCastsImpl()
5433 const SCEV *ExtendedExpr = in createAddRecFromPHIWithCastsImpl()
5444 auto PredIsKnownFalse = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5445 const SCEV *ExtendedExpr) -> bool { in createAddRecFromPHIWithCastsImpl()
5450 const SCEV *StartExtended = getExtendedExpr(StartVal, Signed); in createAddRecFromPHIWithCastsImpl()
5458 const SCEV *AccumExtended = getExtendedExpr(Accum, /*CreateSignExtend=*/true); in createAddRecFromPHIWithCastsImpl()
5464 auto AppendPredicate = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5465 const SCEV *ExtendedExpr) -> void { in createAddRecFromPHIWithCastsImpl()
5481 auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5483 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite = in createAddRecFromPHIWithCastsImpl()
5490 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5500 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite = in createAddRecFromPHIWithCasts()
5512 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in createAddRecFromPHIWithCasts()
5536 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool { in areAddRecsEqualWithPreds()
5555 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN, in createSimpleAffineAddRec()
5569 const SCEV *Accum = nullptr; in createSimpleAffineAddRec()
5578 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSimpleAffineAddRec()
5580 Flags = setFlags(Flags, SCEV::FlagNUW); in createSimpleAffineAddRec()
5582 Flags = setFlags(Flags, SCEV::FlagNSW); in createSimpleAffineAddRec()
5584 const SCEV *StartVal = getSCEV(StartValueV); in createSimpleAffineAddRec()
5585 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createSimpleAffineAddRec()
5601 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { in createAddRecFromPHI()
5638 const SCEV *SymbolicName = getUnknown(PN); in createAddRecFromPHI()
5643 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHI()
5663 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHI()
5668 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHI()
5675 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createAddRecFromPHI()
5680 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5682 Flags = setFlags(Flags, SCEV::FlagNSW); in createAddRecFromPHI()
5692 Flags = setFlags(Flags, SCEV::FlagNW); in createAddRecFromPHI()
5694 const SCEV *Ptr = getSCEV(GEP->getPointerOperand()); in createAddRecFromPHI()
5696 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5704 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5705 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createAddRecFromPHI()
5733 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this); in createAddRecFromPHI()
5734 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false); in createAddRecFromPHI()
5737 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5760 static bool IsAvailableOnEntry(const Loop *L, DominatorTree &DT, const SCEV *S, in IsAvailableOnEntry()
5779 bool follow(const SCEV *S) { in IsAvailableOnEntry()
5874 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { in createNodeFromSelectLikePHI()
5913 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { in createNodeForPHI()
5914 if (const SCEV *S = createAddRecFromPHI(PN)) in createNodeForPHI()
5917 if (const SCEV *S = createNodeFromSelectLikePHI(PN)) in createNodeForPHI()
5932 bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, in SCEVMinMaxExprContains()
5935 const SCEV *OperandToFind; in SCEVMinMaxExprContains()
5948 FindClosure(const SCEV *OperandToFind, SCEVTypes RootKind) in SCEVMinMaxExprContains()
5954 bool follow(const SCEV *S) { in SCEVMinMaxExprContains()
5968 const SCEV *ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond( in createNodeForSelectOrPHIInstWithICmpInstCond()
5991 const SCEV *LA = getSCEV(TrueVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
5992 const SCEV *RA = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
5993 const SCEV *LS = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
5994 const SCEV *RS = getSCEV(RHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6004 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * { in createNodeForSelectOrPHIInstWithICmpInstCond()
6020 const SCEV *LDiff = getMinusSCEV(LA, LS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6021 const SCEV *RDiff = getMinusSCEV(RA, RS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6040 const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), I->getType()); in createNodeForSelectOrPHIInstWithICmpInstCond()
6041 const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6042 const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6043 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x in createNodeForSelectOrPHIInstWithICmpInstCond()
6044 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y in createNodeForSelectOrPHIInstWithICmpInstCond()
6054 const SCEV *X = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6058 const SCEV *FalseValExpr = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6072 static Optional<const SCEV *>
6073 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, in createNodeForSelectViaUMinSeq()
6074 const SCEV *TrueExpr, const SCEV *FalseExpr) { in createNodeForSelectViaUMinSeq()
6092 const SCEV *X, *C; in createNodeForSelectViaUMinSeq()
6105 static Optional<const SCEV *> createNodeForSelectViaUMinSeq(ScalarEvolution *SE, in createNodeForSelectViaUMinSeq()
6118 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq( in createNodeForSelectOrPHIViaUMinSeq()
6129 if (Optional<const SCEV *> S = in createNodeForSelectOrPHIViaUMinSeq()
6136 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond, in createNodeForSelectOrPHI()
6146 const SCEV *S = createNodeForSelectOrPHIInstWithICmpInstCond( in createNodeForSelectOrPHI()
6158 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { in createNodeForGEP()
6162 SmallVector<const SCEV *, 4> IndexExprs; in createNodeForGEP()
6168 uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) { in GetMinTrailingZerosImpl()
6246 uint32_t ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { in GetMinTrailingZeros()
6267 SCEV::NoWrapFlags Flags) { in setNoWrapFlags()
6398 ScalarEvolution::getRangeRef(const SCEV *S, in getRangeRef()
6400 DenseMap<const SCEV *, ConstantRange> &Cache = in getRangeRef()
6408 DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S); in getRangeRef()
6555 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop()); in getRangeRef()
6573 const SCEV *SymbolicMaxBECount = in getRangeRef()
6736 ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, in getRangeForAffineAR()
6737 const SCEV *Step, in getRangeForAffineAR()
6738 const SCEV *MaxBECount, in getRangeForAffineAR()
6770 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth, in getRangeForAffineNoSelfWrappingAR()
6776 const SCEV *Step = AddRec->getStepRecurrence(*this); in getRangeForAffineNoSelfWrappingAR()
6789 const SCEV *RangeWidth = getMinusOne(AddRec->getType()); in getRangeForAffineNoSelfWrappingAR()
6790 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step)); in getRangeForAffineNoSelfWrappingAR()
6791 const SCEV *MaxItersWithoutWrap = getUDivExpr(RangeWidth, StepAbs); in getRangeForAffineNoSelfWrappingAR()
6800 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); in getRangeForAffineNoSelfWrappingAR()
6814 const SCEV *Start = AddRec->getStart(); in getRangeForAffineNoSelfWrappingAR()
6837 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, in getRangeViaFactoring()
6838 const SCEV *Step, in getRangeViaFactoring()
6839 const SCEV *MaxBECount, in getRangeViaFactoring()
6850 const SCEV *S) { in getRangeViaFactoring()
6939 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue); in getRangeViaFactoring()
6940 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue); in getRangeViaFactoring()
6941 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue); in getRangeViaFactoring()
6942 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue); in getRangeViaFactoring()
6952 SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) { in getNoWrapFlagsFromUB()
6953 if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
6957 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
6959 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getNoWrapFlagsFromUB()
6961 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getNoWrapFlagsFromUB()
6962 if (Flags == SCEV::FlagAnyWrap) in getNoWrapFlagsFromUB()
6963 return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
6965 return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
6969 ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) { in getNonTrivialDefiningScopeBound()
6980 static void collectUniqueOps(const SCEV *S, in collectUniqueOps()
6981 SmallVectorImpl<const SCEV *> &Ops) { in collectUniqueOps()
6982 SmallPtrSet<const SCEV *, 4> Unique; in collectUniqueOps()
6983 auto InsertUnique = [&](const SCEV *S) { in collectUniqueOps()
6999 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops, in getDefiningScopeBound()
7003 SmallSet<const SCEV *, 16> Visited; in getDefiningScopeBound()
7004 SmallVector<const SCEV *> Worklist; in getDefiningScopeBound()
7005 auto pushOp = [&](const SCEV *S) { in getDefiningScopeBound()
7026 SmallVector<const SCEV *, 4> Ops; in getDefiningScopeBound()
7036 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) { in getDefiningScopeBound()
7076 SmallVector<const SCEV *> SCEVOps; in isSCEVExprNeverPoison()
7190 const SCEV *ScalarEvolution::createSCEVIter(Value *V) { in createSCEVIter()
7206 const SCEV *CreatedSCEV = nullptr; in createSCEVIter()
7231 const SCEV *
7425 const SCEV *ScalarEvolution::createSCEV(Value *V) { in createSCEV()
7443 const SCEV *LHS; in createSCEV()
7444 const SCEV *RHS; in createSCEV()
7456 SmallVector<const SCEV *, 4> AddOps; in createSCEV()
7471 const SCEV *RHS = getSCEV(BO->RHS); in createSCEV()
7472 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7473 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7474 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7501 SmallVector<const SCEV *, 4> MulOps; in createSCEV()
7509 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7510 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7538 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSCEV()
7569 const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ)); in createSCEV()
7570 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7571 const SCEV *ShiftedLHS = nullptr; in createSCEV()
7578 SmallVector<const SCEV*, 4> MulOps; in createSCEV()
7611 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7617 (SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNSW)); in createSCEV()
7645 const SCEV *Z0 = Z->getOperand(); in createSCEV()
7683 auto Flags = SCEV::FlagAnyWrap; in createSCEV()
7686 if ((MulFlags & SCEV::FlagNSW) && in createSCEV()
7687 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1))) in createSCEV()
7688 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW); in createSCEV()
7689 if (MulFlags & SCEV::FlagNUW) in createSCEV()
7690 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW); in createSCEV()
7726 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0)); in createSCEV()
7774 return getMinusSCEV(V1, V2, SCEV::FlagNSW); in createSCEV()
7787 const SCEV *Op = getSCEV(U->getOperand(0)); in createSCEV()
7791 const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy); in createSCEV()
7852 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
7853 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
7854 const SCEV *ClampedY = getUMinExpr(X, Y); in createSCEV()
7855 return getMinusSCEV(X, ClampedY, SCEV::FlagNUW); in createSCEV()
7858 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
7859 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
7860 const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y)); in createSCEV()
7861 return getAddExpr(ClampedX, Y, SCEV::FlagNUW); in createSCEV()
7883 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount, in getTripCountFromExitCount()
7936 const SCEV *ScalarEvolution::getConstantMaxTripCountFromArray(const Loop *L) { in getConstantMaxTripCountFromArray()
7952 SmallVector<const SCEV *> InferCountColl; in getConstantMaxTripCountFromArray()
8029 const SCEV *MemSize = in getConstantMaxTripCountFromArray()
8071 const SCEV *ExitCount) { in getSmallConstantTripMultiple()
8076 const SCEV *TCExpr = getTripCountFromExitCount(ExitCount); in getSmallConstantTripMultiple()
8116 const SCEV *ExitCount = getExitCount(L, ExitingBlock); in getSmallConstantTripMultiple()
8120 const SCEV *ScalarEvolution::getExitCount(const Loop *L, in getExitCount()
8133 const SCEV *
8139 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, in getBackedgeTakenCount()
8206 const SCEV *BEExact = Result.getExact(L, this); in getBackedgeTakenInfo()
8226 SmallVector<const SCEV *, 8> ToForget; in getBackedgeTakenInfo()
8273 SmallVector<const SCEV *, 16> ToForget; in forgetLoop()
8286 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetLoop()
8336 SmallVector<const SCEV *, 8> ToForget; in forgetValue()
8366 const SCEV *
8380 SmallVector<const SCEV *, 2> Ops; in getExact()
8382 const SCEV *BECount = ENT.ExactNotTaken; in getExact()
8405 const SCEV *
8415 const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax( in getConstantMax()
8425 const SCEV *
8440 const SCEV *
8456 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) in ExitLimit()
8461 const SCEV *E, const SCEV *M, bool MaxOrZero, in ExitLimit()
8486 const SCEV *E, const SCEV *M, bool MaxOrZero, in ExitLimit()
8491 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M, in ExitLimit()
8500 bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero) in BackedgeTakenInfo()
8530 const SCEV *MustExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8531 const SCEV *MayExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8592 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : in computeBackedgeTakenCount()
8795 const SCEV *BECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
8796 const SCEV *MaxBECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
8846 const SCEV *LHS = getSCEV(ExitCond->getOperand(0)); in computeExitLimitFromICmp()
8847 const SCEV *RHS = getSCEV(ExitCond->getOperand(1)); in computeExitLimitFromICmp()
8865 const SCEV *LHS, const SCEV *RHS, in computeExitLimitFromICmp()
8897 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this); in computeExitLimitFromICmp()
8917 Flags = setFlags(Flags, SCEV::FlagNW); in computeExitLimitFromICmp()
8918 SmallVector<const SCEV*> Operands{AR->operands()}; in computeExitLimitFromICmp()
8996 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L); in computeExitLimitFromSingleExitSwitch()
8997 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock)); in computeExitLimitFromSingleExitSwitch()
9010 const SCEV *InVal = SE.getConstant(C); in EvaluateConstantChrecAtConstant()
9011 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE); in EvaluateConstantChrecAtConstant()
9152 const SCEV *UpperBound = in computeShiftCompareExitLimit()
9401 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L, in computeExitCountExhaustively()
9468 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { in getSCEVAtScope()
9469 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values = in getSCEVAtScope()
9479 const SCEV *C = computeSCEVAtScope(V, L); in getSCEVAtScope()
9494 static Constant *BuildConstantFromSCEV(const SCEV *V) { in BuildConstantFromSCEV()
9531 for (const SCEV *Op : SA->operands()) { in BuildConstantFromSCEV()
9558 for (const SCEV *Op : SM->operands()) { in BuildConstantFromSCEV()
9578 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { in computeSCEVAtScope()
9594 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(CurrLoop); in computeSCEVAtScope()
9638 const SCEV *Input = getSCEV(PN->getOperand(0)); in computeSCEVAtScope()
9639 const SCEV *InputAtScope = getSCEVAtScope(Input, L); in computeSCEVAtScope()
9665 const SCEV *OrigV = getSCEV(Op); in computeSCEVAtScope()
9666 const SCEV *OpV = getSCEVAtScope(OrigV, L); in computeSCEVAtScope()
9699 const SCEV *OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); in computeSCEVAtScope()
9703 SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(), in computeSCEVAtScope()
9727 const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L); in computeSCEVAtScope()
9728 const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L); in computeSCEVAtScope()
9741 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); in computeSCEVAtScope()
9747 SmallVector<const SCEV *, 8> NewOps(AddRec->op_begin(), in computeSCEVAtScope()
9753 const SCEV *FoldedRec = in computeSCEVAtScope()
9755 AddRec->getNoWrapFlags(SCEV::FlagNW)); in computeSCEVAtScope()
9770 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); in computeSCEVAtScope()
9781 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L); in computeSCEVAtScope()
9790 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { in getSCEVAtScope()
9794 const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const { in stripInjectiveFunctions()
9810 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, in SolveLinEquationWithOverflow()
9845 const SCEV *D = SE.getConstant(APInt::getOneBitSet(BW, Mult2)); in SolveLinEquationWithOverflow()
10119 ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, in howFarToZero()
10176 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); in howFarToZero()
10177 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); in howFarToZero()
10195 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start); in howFarToZero()
10211 const SCEV *Zero = getZero(Distance->getType()); in howFarToZero()
10212 const SCEV *One = getOne(Distance->getType()); in howFarToZero()
10213 const SCEV *DistancePlusOne = getAddExpr(Distance, One); in howFarToZero()
10230 const SCEV *Exact = in howFarToZero()
10232 const SCEV *Max = getCouldNotCompute(); in howFarToZero()
10241 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(), in howFarToZero()
10244 const SCEV *M = E; in howFarToZero()
10253 ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { in howFarToNonZero()
10293 static bool HasSameValue(const SCEV *A, const SCEV *B) { in HasSameValue()
10318 const SCEV *&LHS, const SCEV *&RHS, in SimplifyICmpOperands()
10459 SCEV::FlagNSW); in SimplifyICmpOperands()
10464 SCEV::FlagNSW); in SimplifyICmpOperands()
10472 SCEV::FlagNSW); in SimplifyICmpOperands()
10477 SCEV::FlagNSW); in SimplifyICmpOperands()
10485 SCEV::FlagNUW); in SimplifyICmpOperands()
10501 SCEV::FlagNUW); in SimplifyICmpOperands()
10521 bool ScalarEvolution::isKnownNegative(const SCEV *S) { in isKnownNegative()
10525 bool ScalarEvolution::isKnownPositive(const SCEV *S) { in isKnownPositive()
10529 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) { in isKnownNonNegative()
10533 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) { in isKnownNonPositive()
10537 bool ScalarEvolution::isKnownNonZero(const SCEV *S) { in isKnownNonZero()
10541 std::pair<const SCEV *, const SCEV *>
10542 ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) { in SplitIntoInitAndPostInc()
10544 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10548 const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10554 const SCEV *LHS, const SCEV *RHS) { in isKnownViaInduction()
10605 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicate()
10620 const SCEV *LHS, in evaluatePredicate()
10621 const SCEV *RHS) { in evaluatePredicate()
10630 const SCEV *LHS, const SCEV *RHS, in isKnownPredicateAt()
10638 const SCEV *LHS, in evaluatePredicateAt()
10639 const SCEV *RHS, in evaluatePredicateAt()
10656 const SCEV *RHS) { in isKnownOnEveryIteration()
10715 const SCEV *Step = LHS->getStepRecurrence(*this); in getMonotonicPredicateTypeImpl()
10729 const SCEV *LHS, const SCEV *RHS, in getLoopInvariantPredicate()
10776 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, in getLoopInvariantExitCondDuringFirstIterations()
10777 const Instruction *CtxI, const SCEV *MaxIter) { in getLoopInvariantExitCondDuringFirstIterations()
10804 const SCEV *Step = AR->getStepRecurrence(*this); in getLoopInvariantExitCondDuringFirstIterations()
10817 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this); in getLoopInvariantExitCondDuringFirstIterations()
10830 const SCEV *Start = AR->getStart(); in getLoopInvariantExitCondDuringFirstIterations()
10839 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateViaConstantRanges()
10881 const SCEV *LHS, in isKnownPredicateViaNoOverflow()
10882 const SCEV *RHS) { in isKnownPredicateViaNoOverflow()
10887 auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y, in isKnownPredicateViaNoOverflow()
10889 SCEV::NoWrapFlags ExpectedFlags) { in isKnownPredicateViaNoOverflow()
10890 const SCEV *XNonConstOp, *XConstOp; in isKnownPredicateViaNoOverflow()
10891 const SCEV *YNonConstOp, *YConstOp; in isKnownPredicateViaNoOverflow()
10892 SCEV::NoWrapFlags XFlagsPresent; in isKnownPredicateViaNoOverflow()
10893 SCEV::NoWrapFlags YFlagsPresent; in isKnownPredicateViaNoOverflow()
10935 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2)) in isKnownPredicateViaNoOverflow()
10945 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2)) in isKnownPredicateViaNoOverflow()
10955 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ule(C2)) in isKnownPredicateViaNoOverflow()
10965 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ult(C2)) in isKnownPredicateViaNoOverflow()
10974 const SCEV *LHS, in isKnownPredicateViaSplitting()
10975 const SCEV *RHS) { in isKnownPredicateViaSplitting()
10997 const SCEV *LHS, const SCEV *RHS) { in isImpliedViaGuard()
11018 const SCEV *LHS, const SCEV *RHS) { in isLoopBackedgeGuardedByCond()
11054 const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this); in isLoopBackedgeGuardedByCond()
11060 auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW); in isLoopBackedgeGuardedByCond()
11061 const SCEV *LoopCounter = in isLoopBackedgeGuardedByCond()
11123 const SCEV *LHS, in isBasicBlockEntryGuardedByCond()
11124 const SCEV *RHS) { in isBasicBlockEntryGuardedByCond()
11223 const SCEV *LHS, in isLoopEntryGuardedByCond()
11224 const SCEV *RHS) { in isLoopEntryGuardedByCond()
11242 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11243 const SCEV *RHS, in isImpliedCond()
11280 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0)); in isImpliedCond()
11281 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1)); in isImpliedCond()
11286 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11287 const SCEV *RHS, in isImpliedCond()
11289 const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCond()
11302 const SCEV *MaxValue = getZeroExtendExpr( in isImpliedCond()
11308 const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType); in isImpliedCond()
11309 const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType); in isImpliedCond()
11342 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondBalancedTypes()
11343 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCondBalancedTypes()
11422 const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS, in isImpliedCondBalancedTypes()
11456 const SCEV *V = nullptr; in isImpliedCondBalancedTypes()
11542 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr, in splitBinaryAdd()
11543 const SCEV *&L, const SCEV *&R, in splitBinaryAdd()
11544 SCEV::NoWrapFlags &Flags) { in splitBinaryAdd()
11555 Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More, in computeConstantDifference()
11556 const SCEV *Less) { in computeConstantDifference()
11591 SCEV::NoWrapFlags Flags; in computeConstantDifference()
11592 const SCEV *LLess = nullptr, *RLess = nullptr; in computeConstantDifference()
11593 const SCEV *LMore = nullptr, *RMore = nullptr; in computeConstantDifference()
11615 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaAddRecStart()
11616 const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) { in isImpliedCondOperandsViaAddRecStart()
11660 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaNoOverflow()
11661 const SCEV *FoundLHS, const SCEV *FoundRHS) { in isImpliedCondOperandsViaNoOverflow()
11737 const SCEV *LHS, const SCEV *RHS, in isImpliedViaMerge()
11738 const SCEV *FoundLHS, in isImpliedViaMerge()
11739 const SCEV *FoundRHS, unsigned Depth) { in isImpliedViaMerge()
11793 auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaMerge()
11805 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
11806 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
11821 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor)); in isImpliedViaMerge()
11826 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch)); in isImpliedViaMerge()
11838 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
11851 const SCEV *LHS, in isImpliedCondOperandsViaShift()
11852 const SCEV *RHS, in isImpliedCondOperandsViaShift()
11853 const SCEV *FoundLHS, in isImpliedCondOperandsViaShift()
11854 const SCEV *FoundRHS) { in isImpliedCondOperandsViaShift()
11893 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperands()
11894 const SCEV *FoundLHS, in isImpliedCondOperands()
11895 const SCEV *FoundRHS, in isImpliedCondOperands()
11916 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, in IsMinMaxConsistingOf()
11917 const SCEV *Candidate) { in IsMinMaxConsistingOf()
11927 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaAddRecStart()
11949 SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ? in IsKnownPredicateViaAddRecStart()
11950 SCEV::FlagNSW : SCEV::FlagNUW; in IsKnownPredicateViaAddRecStart()
11961 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaMinOrMax()
11992 const SCEV *LHS, const SCEV *RHS, in isImpliedViaOperations()
11993 const SCEV *FoundLHS, in isImpliedViaOperations()
11994 const SCEV *FoundRHS, in isImpliedViaOperations()
12022 const SCEV *MinusOne = getMinusOne(LHS->getType()); in isImpliedViaOperations()
12033 auto GetOpFromSExt = [&](const SCEV *S) { in isImpliedViaOperations()
12048 auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12072 auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12160 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateExtendIdiom()
12193 const SCEV *LHS, const SCEV *RHS) { in isKnownViaNonRecursiveReasoning()
12203 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsHelper()
12204 const SCEV *FoundLHS, in isImpliedCondOperandsHelper()
12205 const SCEV *FoundRHS) { in isImpliedCondOperandsHelper()
12247 const SCEV *LHS, in isImpliedCondOperandsViaRanges()
12248 const SCEV *RHS, in isImpliedCondOperandsViaRanges()
12249 const SCEV *FoundLHS, in isImpliedCondOperandsViaRanges()
12250 const SCEV *FoundRHS) { in isImpliedCondOperandsViaRanges()
12278 bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnLT()
12283 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnLT()
12302 bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnGT()
12306 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnGT()
12325 const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) { in getUDivCeilSCEV()
12329 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType())); in getUDivCeilSCEV()
12330 const SCEV *NMinusOne = getMinusSCEV(N, MinNOne); in getUDivCeilSCEV()
12334 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start, in computeMaxBECountForLT()
12335 const SCEV *Stride, in computeMaxBECountForLT()
12336 const SCEV *End, in computeMaxBECountForLT()
12384 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, in howManyLessThans()
12447 if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW()) in howManyLessThans()
12448 Flags = setFlags(Flags, SCEV::FlagNUW); in howManyLessThans()
12454 const SCEV *Step = AR->getStepRecurrence(*this); in howManyLessThans()
12488 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyLessThans()
12492 const SCEV *Stride = IV->getStepRecurrence(*this); in howManyLessThans()
12599 const SCEV *Start = IV->getStart(); in howManyLessThans()
12605 const SCEV *OrigStart = Start; in howManyLessThans()
12606 const SCEV *OrigRHS = RHS; in howManyLessThans()
12624 const SCEV *MaxBECount = computeMaxBECountForLT( in howManyLessThans()
12634 const SCEV *BECount = nullptr; in howManyLessThans()
12660 const SCEV *MinusOne = getMinusOne(Stride->getType()); in howManyLessThans()
12661 const SCEV *Numerator = in howManyLessThans()
12666 const SCEV *BECountIfBackedgeTaken = nullptr; in howManyLessThans()
12690 const SCEV *End; in howManyLessThans()
12720 const SCEV *One = getOne(Stride->getType()); in howManyLessThans()
12779 const SCEV *Delta = getMinusSCEV(End, Start); in howManyLessThans()
12790 const SCEV *MaxBECount; in howManyLessThans()
12814 ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, in howManyGreaterThans()
12833 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyGreaterThans()
12837 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this)); in howManyGreaterThans()
12851 const SCEV *Start = IV->getStart(); in howManyGreaterThans()
12852 const SCEV *End = RHS; in howManyGreaterThans()
12877 const SCEV *One = getOne(Stride->getType()); in howManyGreaterThans()
12878 const SCEV *BECount = getUDivExpr( in howManyGreaterThans()
12898 const SCEV *MaxBECount = isa<SCEVConstant>(BECount) in howManyGreaterThans()
12909 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range, in getNumIterationsInRange()
12917 SmallVector<const SCEV *, 4> Operands(operands()); in getNumIterationsInRange()
12919 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(), in getNumIterationsInRange()
12930 if (any_of(operands(), [](const SCEV *Op) { return !isa<SCEVConstant>(Op); })) in getNumIterationsInRange()
12989 SmallVector<const SCEV *, 3> Ops; in getPostIncExpr()
12998 const SCEV *Last = getOperand(getNumOperands() - 1); in getPostIncExpr()
13002 SCEV::FlagAnyWrap)); in getPostIncExpr()
13006 bool ScalarEvolution::containsUndefs(const SCEV *S) const { in containsUndefs()
13007 return SCEVExprContains(S, [](const SCEV *S) { in containsUndefs()
13015 bool ScalarEvolution::containsErasedValue(const SCEV *S) const { in containsErasedValue()
13016 return SCEVExprContains(S, [](const SCEV *S) { in containsErasedValue()
13024 const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { in getElementSize()
13256 const SCEV *SV = SE.getSCEV(&I); in print()
13267 const SCEV *AtUse = SE.getSCEVAtScope(SV, L); in print()
13281 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); in print()
13330 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { in getLoopDisposition()
13349 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { in computeLoopDisposition()
13430 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { in isLoopInvariant()
13434 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { in hasComputableLoopEvolution()
13439 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { in getBlockDisposition()
13458 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { in computeBlockDisposition()
13488 for (const SCEV *NAryOp : NAry->operands()) { in computeBlockDisposition()
13499 const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS(); in computeBlockDisposition()
13525 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) { in dominates()
13529 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { in properlyDominates()
13533 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { in hasOperand()
13534 return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; }); in hasOperand()
13554 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) { in forgetMemoizedResults()
13555 SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end()); in forgetMemoizedResults()
13556 SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end()); in forgetMemoizedResults()
13559 const SCEV *Curr = Worklist.pop_back_val(); in forgetMemoizedResults()
13572 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetMemoizedResults()
13580 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) { in forgetMemoizedResultsImpl()
13625 ScalarEvolution::getUsedLoops(const SCEV *S, in getUsedLoops()
13631 bool follow(const SCEV *S) { in getUsedLoops()
13663 const SCEV *L = getSCEV(Cmp->getOperand(0)); in getReachableBlocks()
13664 const SCEV *R = getSCEV(Cmp->getOperand(1)); in getReachableBlocks()
13691 const SCEV *visitConstant(const SCEVConstant *Constant) { in verify()
13695 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in verify()
13699 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { in verify()
13708 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * { in verify()
13719 const SCEV *Delta = SE2.getMinusSCEV(Old, New); in verify()
13762 const SCEV *Delta = GetDelta(CurBECount, NewBECount); in verify()
13800 const SCEV *OldSCEV = SCM.visit(KV.second); in verify()
13801 const SCEV *NewSCEV = SE2.getSCEV(I); in verify()
13802 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV); in verify()
13831 SmallVector<const SCEV *, 4> Ops; in verify()
13848 const SCEV *Value = ValueAndVec.first; in verify()
13851 const SCEV *ValueAtScope = LoopAndValueAtScope.second; in verify()
13865 const SCEV *ValueAtScope = ValueAtScopeAndVec.first; in verify()
13868 const SCEV *Value = LoopAndValue.second; in verify()
13986 const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS, in getEqualPredicate()
13987 const SCEV *RHS) { in getEqualPredicate()
13993 const SCEV *LHS, const SCEV *RHS) { in getComparePredicate()
14041 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
14048 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
14065 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in visitZeroExtendExpr()
14066 const SCEV *Operand = visit(Expr->getOperand()); in visitZeroExtendExpr()
14071 const SCEV *Step = AR->getStepRecurrence(SE); in visitZeroExtendExpr()
14081 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { in visitSignExtendExpr()
14082 const SCEV *Operand = visit(Expr->getOperand()); in visitSignExtendExpr()
14087 const SCEV *Step = AR->getStepRecurrence(SE); in visitSignExtendExpr()
14124 const SCEV *convertToAddRecWithPreds(const SCEVUnknown *Expr) { in convertToAddRecWithPreds()
14127 Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in convertToAddRecWithPreds()
14150 const SCEV *
14151 ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L, in rewriteUsingPredicate()
14157 const SCEV *S, const Loop *L, in convertSCEVToAddRecWithPredicates()
14181 const SCEV *LHS, const SCEV *RHS) in SCEVComparePredicate()
14225 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags(); in isAlwaysTrue()
14228 if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags) in isAlwaysTrue()
14247 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags(); in getImpliedFlags()
14250 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags) in getImpliedFlags()
14253 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) { in getImpliedFlags()
14307 void ScalarEvolution::registerUser(const SCEV *User, in registerUser()
14308 ArrayRef<const SCEV *> Ops) { in registerUser()
14317 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) { in getSCEV()
14318 const SCEV *Expr = SE.getSCEV(V); in getSCEV()
14330 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds); in getSCEV()
14336 const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() { in getBackedgeTakenCount()
14365 const SCEV *Rewritten = II.second.second; in updateGeneration()
14373 const SCEV *Expr = getSCEV(V); in setNoOverflow()
14389 const SCEV *Expr = getSCEV(V); in hasNoOverflow()
14404 const SCEV *Expr = this->getSCEV(V); in getAsAddRec()
14455 bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS, in matchURem()
14456 const SCEV *&RHS) { in matchURem()
14478 const SCEV *A = Add->getOperand(1); in matchURem()
14484 const auto MatchURemWithDivisor = [&](const SCEV *B) { in matchURem()
14508 const SCEV *
14516 SmallVector<const SCEV*, 4> ExitCounts; in computeSymbolicMaxBackedgeTakenCount()
14518 const SCEV *ExitCount = getExitCount(L, ExitingBB); in computeSymbolicMaxBackedgeTakenCount()
14541 const DenseMap<const SCEV *, const SCEV *> ⤅
14545 DenseMap<const SCEV *, const SCEV *> &M) in SCEVLoopGuardRewriter() argument
14548 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { return Expr; } in visitAddRecExpr()
14550 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
14557 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in visitZeroExtendExpr()
14566 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) { in applyLoopGuards()
14567 SmallVector<const SCEV *> ExprsToRewrite; in applyLoopGuards()
14568 auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS, in applyLoopGuards()
14569 const SCEV *RHS, in applyLoopGuards()
14570 DenseMap<const SCEV *, const SCEV *> in applyLoopGuards()
14606 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown; in applyLoopGuards()
14623 const SCEV *URemLHS = nullptr; in applyLoopGuards()
14624 const SCEV *URemRHS = nullptr; in applyLoopGuards()
14652 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHS; in applyLoopGuards()
14654 const SCEV *RewrittenRHS = nullptr; in applyLoopGuards()
14737 DenseMap<const SCEV *, const SCEV *> RewriteMap; in applyLoopGuards()
14773 for (const SCEV *Expr : ExprsToRewrite) { in applyLoopGuards()
14774 const SCEV *RewriteTo = RewriteMap[Expr]; in applyLoopGuards()