Lines Matching refs:SCEV
261 LLVM_DUMP_METHOD void SCEV::dump() const { in dump()
267 void SCEV::print(raw_ostream &OS) const { in print()
277 const SCEV *Op = PtrToInt->getOperand(); in print()
284 const SCEV *Op = Trunc->getOperand(); in print()
291 const SCEV *Op = ZExt->getOperand(); in print()
298 const SCEV *Op = SExt->getOperand(); in print()
348 for (const SCEV *Op : NAry->operands()) in print()
380 Type *SCEV::getType() const { in getType()
414 ArrayRef<const SCEV *> SCEV::operands() const { in operands()
442 bool SCEV::isZero() const { in isZero()
448 bool SCEV::isOne() const { in isOne()
454 bool SCEV::isAllOnesValue() const { in isAllOnesValue()
460 bool SCEV::isNonConstantNegative() const { in isNonConstantNegative()
473 SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} in SCEVCouldNotCompute()
475 bool SCEVCouldNotCompute::classof(const SCEV *S) { in classof()
479 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { in getConstant()
484 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getConstant()
485 SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V); in getConstant()
490 const SCEV *ScalarEvolution::getConstant(const APInt &Val) { in getConstant()
494 const SCEV *
500 const SCEV *ScalarEvolution::getVScale(Type *Ty) { in getVScale()
505 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getVScale()
507 SCEV *S = new (SCEVAllocator) SCEVVScale(ID.Intern(SCEVAllocator), Ty); in getVScale()
512 const SCEV *ScalarEvolution::getElementCount(Type *Ty, ElementCount EC) { in getElementCount()
513 const SCEV *Res = getConstant(Ty, EC.getKnownMinValue()); in getElementCount()
520 const SCEV *op, Type *ty) in SCEVCastExpr()
521 : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {} in SCEVCastExpr()
523 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, in SCEVPtrToIntExpr()
531 SCEVTypes SCEVTy, const SCEV *op, in SCEVIntegralCastExpr()
535 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, in SCEVTruncateExpr()
543 const SCEV *op, Type *ty) in SCEVZeroExtendExpr()
550 const SCEV *op, Type *ty) in SCEVSignExtendExpr()
681 CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV, in CompareSCEVComplexity()
683 const LoopInfo *const LI, const SCEV *LHS, in CompareSCEVComplexity()
684 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) { in CompareSCEVComplexity()
767 ArrayRef<const SCEV *> LOps = LHS->operands(); in CompareSCEVComplexity()
768 ArrayRef<const SCEV *> ROps = RHS->operands(); in CompareSCEVComplexity()
800 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, in GroupByComplexity()
804 EquivalenceClasses<const SCEV *> EqCacheSCEV; in GroupByComplexity()
808 auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
816 const SCEV *&LHS = Ops[0], *&RHS = Ops[1]; in GroupByComplexity()
823 llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
832 const SCEV *S = Ops[i]; in GroupByComplexity()
850 static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { in hasHugeExpression()
851 return any_of(Ops, [](const SCEV *S) { in hasHugeExpression()
861 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, in BinomialCoefficient()
950 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); in BinomialCoefficient()
952 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i)); in BinomialCoefficient()
958 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); in BinomialCoefficient()
974 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, in evaluateAtIteration()
979 const SCEV *
980 SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands, in evaluateAtIteration()
981 const SCEV *It, ScalarEvolution &SE) { in evaluateAtIteration()
983 const SCEV *Result = Operands[0]; in evaluateAtIteration()
988 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType()); in evaluateAtIteration()
1001 const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op, in getLosslessPtrToIntExpr()
1019 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getLosslessPtrToIntExpr()
1049 SCEV *S = new (SCEVAllocator) in getLosslessPtrToIntExpr()
1076 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE) { in getLosslessPtrToIntExpr()
1081 const SCEV *visit(const SCEV *S) { in getLosslessPtrToIntExpr()
1090 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { in getLosslessPtrToIntExpr()
1091 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1100 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { in getLosslessPtrToIntExpr()
1101 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1110 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in getLosslessPtrToIntExpr()
1118 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(Op, *this); in getLosslessPtrToIntExpr()
1125 const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) { in getPtrToIntExpr()
1128 const SCEV *IntOp = getLosslessPtrToIntExpr(Op); in getPtrToIntExpr()
1135 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty, in getTruncateExpr()
1149 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getTruncateExpr()
1169 SCEV *S = in getTruncateExpr()
1182 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1186 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1); in getTruncateExpr()
1202 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getTruncateExpr()
1208 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1209 for (const SCEV *Op : AddRec->operands()) in getTruncateExpr()
1211 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); in getTruncateExpr()
1222 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), in getTruncateExpr()
1232 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step, in getSignedOverflowLimitForStep()
1252 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step, in getUnsignedOverflowLimitForStep()
1265 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *,
1284 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
1288 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1300 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
1304 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1324 static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, in getPreStartForExtend()
1330 const SCEV *Start = AR->getStart(); in getPreStartForExtend()
1331 const SCEV *Step = AR->getStepRecurrence(*SE); in getPreStartForExtend()
1342 SmallVector<const SCEV *, 4> DiffOps(SA->operands()); in getPreStartForExtend()
1357 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW); in getPreStartForExtend()
1358 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags); in getPreStartForExtend()
1360 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap)); in getPreStartForExtend()
1366 const SCEV *BECount = SE->getBackedgeTakenCount(L); in getPreStartForExtend()
1374 const SCEV *OperandExtendedStart = in getPreStartForExtend()
1389 const SCEV *OverflowLimit = in getPreStartForExtend()
1401 static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, in getExtendAddRecStart()
1406 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth); in getExtendAddRecStart()
1448 bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start, in proveNoWrapByVaryingStart()
1449 const SCEV *Step, in proveNoWrapByVaryingStart()
1464 const SCEV *PreStart = getConstant(StartAI - Delta); in proveNoWrapByVaryingStart()
1478 const SCEV *DeltaS = getConstant(StartC->getType(), Delta); in proveNoWrapByVaryingStart()
1480 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep( in proveNoWrapByVaryingStart()
1518 const SCEV *Step) { in extractConstantWithoutWrapping()
1528 const ScalarEvolution::FoldID &ID, const SCEV *S, in insertFoldCacheEntry()
1529 DenseMap<ScalarEvolution::FoldID, const SCEV *> &FoldCache, in insertFoldCacheEntry()
1530 DenseMap<const SCEV *, SmallVector<ScalarEvolution::FoldID, 2>> in insertFoldCacheEntry() argument
1550 const SCEV *
1551 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getZeroExtendExpr()
1564 const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth); in getZeroExtendExpr()
1570 const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty, in getZeroExtendExprImpl()
1592 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExprImpl()
1594 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExprImpl()
1605 const SCEV *X = ST->getOperand(); in getZeroExtendExprImpl()
1620 const SCEV *Start = AR->getStart(); in getZeroExtendExprImpl()
1621 const SCEV *Step = AR->getStepRecurrence(*this); in getZeroExtendExprImpl()
1642 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getZeroExtendExprImpl()
1648 const SCEV *CastedMaxBECount = in getZeroExtendExprImpl()
1650 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getZeroExtendExprImpl()
1655 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step, in getZeroExtendExprImpl()
1656 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1657 const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul, in getZeroExtendExprImpl()
1658 SCEV::FlagAnyWrap, in getZeroExtendExprImpl()
1661 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1); in getZeroExtendExprImpl()
1662 const SCEV *WideMaxBECount = in getZeroExtendExprImpl()
1664 const SCEV *OperandExtendedAdd = in getZeroExtendExprImpl()
1668 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExprImpl()
1669 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1672 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExprImpl()
1685 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExprImpl()
1686 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1690 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExprImpl()
1726 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - in getZeroExtendExprImpl()
1733 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExprImpl()
1750 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExprImpl()
1751 const SCEV *SResidual = in getZeroExtendExprImpl()
1753 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExprImpl()
1755 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExprImpl()
1761 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExprImpl()
1771 const SCEV *LHS; in getZeroExtendExprImpl()
1772 const SCEV *RHS; in getZeroExtendExprImpl()
1788 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExprImpl()
1791 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1805 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExprImpl()
1806 const SCEV *SResidual = in getZeroExtendExprImpl()
1807 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getZeroExtendExprImpl()
1808 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExprImpl()
1810 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExprImpl()
1821 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExprImpl()
1824 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1850 SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1858 SmallVector<const SCEV *, 4> Operands; in getZeroExtendExprImpl()
1869 SmallVector<const SCEV *, 4> Operands; in getZeroExtendExprImpl()
1877 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExprImpl()
1878 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExprImpl()
1885 const SCEV *
1886 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getSignExtendExpr()
1899 const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth); in getSignExtendExpr()
1905 const SCEV *ScalarEvolution::getSignExtendExprImpl(const SCEV *Op, Type *Ty, in getSignExtendExprImpl()
1932 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExprImpl()
1935 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExprImpl()
1946 const SCEV *X = ST->getOperand(); in getSignExtendExprImpl()
1960 SmallVector<const SCEV *, 4> Ops; in getSignExtendExprImpl()
1963 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1); in getSignExtendExprImpl()
1978 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExprImpl()
1979 const SCEV *SResidual = in getSignExtendExprImpl()
1980 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getSignExtendExprImpl()
1981 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExprImpl()
1983 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExprImpl()
1994 const SCEV *Start = AR->getStart(); in getSignExtendExprImpl()
1995 const SCEV *Step = AR->getStepRecurrence(*this); in getSignExtendExprImpl()
2005 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW); in getSignExtendExprImpl()
2016 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getSignExtendExprImpl()
2023 const SCEV *CastedMaxBECount = in getSignExtendExprImpl()
2025 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getSignExtendExprImpl()
2030 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step, in getSignExtendExprImpl()
2031 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2032 const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul, in getSignExtendExprImpl()
2033 SCEV::FlagAnyWrap, in getSignExtendExprImpl()
2036 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1); in getSignExtendExprImpl()
2037 const SCEV *WideMaxBECount = in getSignExtendExprImpl()
2039 const SCEV *OperandExtendedAdd = in getSignExtendExprImpl()
2043 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExprImpl()
2044 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2047 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExprImpl()
2060 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExprImpl()
2061 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2071 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getSignExtendExprImpl()
2102 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExprImpl()
2103 const SCEV *SResidual = in getSignExtendExprImpl()
2105 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExprImpl()
2107 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExprImpl()
2113 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExprImpl()
2130 SmallVector<const SCEV *, 4> Operands; in getSignExtendExprImpl()
2140 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExprImpl()
2141 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExprImpl()
2148 const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op, in getCastExpr()
2166 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, in getAnyExtendExpr()
2181 const SCEV *NewOp = T->getOperand(); in getAnyExtendExpr()
2188 const SCEV *ZExt = getZeroExtendExpr(Op, Ty); in getAnyExtendExpr()
2193 const SCEV *SExt = getSignExtendExpr(Op, Ty); in getAnyExtendExpr()
2199 SmallVector<const SCEV *, 4> Ops; in getAnyExtendExpr()
2200 for (const SCEV *Op : AR->operands()) in getAnyExtendExpr()
2202 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW); in getAnyExtendExpr()
2237 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, in CollectAddOperandsWithScales() argument
2238 SmallVectorImpl<const SCEV *> &NewOps, in CollectAddOperandsWithScales()
2240 ArrayRef<const SCEV *> Ops, const APInt &Scale, in CollectAddOperandsWithScales()
2270 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands())); in CollectAddOperandsWithScales()
2271 const SCEV *Key = SE.getMulExpr(MulOps); in CollectAddOperandsWithScales()
2284 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = in CollectAddOperandsWithScales()
2301 const SCEV *LHS, const SCEV *RHS, in willNotOverflow()
2303 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *, in willNotOverflow()
2304 SCEV::NoWrapFlags, unsigned); in willNotOverflow()
2319 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) = in willNotOverflow()
2328 const SCEV *A = (this->*Extension)( in willNotOverflow()
2329 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0); in willNotOverflow()
2330 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0); in willNotOverflow()
2331 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0); in willNotOverflow()
2332 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0); in willNotOverflow()
2376 std::optional<SCEV::NoWrapFlags>
2383 SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap; in getStrengthenedNoWrapFlagsFromBinOp()
2386 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2388 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2397 const SCEV *LHS = getSCEV(OBO->getOperand(0)); in getStrengthenedNoWrapFlagsFromBinOp()
2398 const SCEV *RHS = getSCEV(OBO->getOperand(1)); in getStrengthenedNoWrapFlagsFromBinOp()
2405 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2412 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2424 static SCEV::NoWrapFlags
2426 const ArrayRef<const SCEV *> Ops, in StrengthenNoWrapFlags()
2427 SCEV::NoWrapFlags Flags) { in StrengthenNoWrapFlags()
2437 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; in StrengthenNoWrapFlags()
2438 SCEV::NoWrapFlags SignOrUnsignWrap = in StrengthenNoWrapFlags()
2442 auto IsKnownNonNegative = [&](const SCEV *S) { in StrengthenNoWrapFlags()
2446 if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative)) in StrengthenNoWrapFlags()
2448 ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); in StrengthenNoWrapFlags()
2470 if (!(SignOrUnsignWrap & SCEV::FlagNSW)) { in StrengthenNoWrapFlags()
2474 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in StrengthenNoWrapFlags()
2478 if (!(SignOrUnsignWrap & SCEV::FlagNUW)) { in StrengthenNoWrapFlags()
2482 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2488 if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) && in StrengthenNoWrapFlags()
2489 !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 && in StrengthenNoWrapFlags()
2491 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2494 if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && in StrengthenNoWrapFlags()
2498 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2501 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2507 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) { in isAvailableAtLoopEntry()
2512 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, in getAddExpr()
2513 SCEV::NoWrapFlags OrigFlags, in getAddExpr()
2515 assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && in getAddExpr()
2525 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); }); in getAddExpr()
2555 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getAddExpr()
2563 if (SCEV *S = findExistingSCEVInCache(scAddExpr, Ops)) { in getAddExpr()
2583 const SCEV *Scale = getConstant(Ty, Count); in getAddExpr()
2584 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2614 SmallVector<const SCEV *, 8> LargeOps; in getAddExpr()
2618 for (const SCEV *Op : Ops) { in getAddExpr()
2628 SmallVector<const SCEV *, 8> LargeMulOps; in getAddExpr()
2645 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2653 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2664 const SCEV *A = Ops[0]; in getAddExpr()
2665 const SCEV *B = Ops[1]; in getAddExpr()
2671 SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap; in getAddExpr()
2676 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNUW) && in getAddExpr()
2679 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW); in getAddExpr()
2684 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNSW) && in getAddExpr()
2688 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW); in getAddExpr()
2691 if (PreservedFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2692 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands()); in getAddExpr()
2704 const SCEV *X; in getAddExpr()
2705 const SCEV *Y; in getAddExpr()
2722 SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW); in getAddExpr()
2750 DenseMap<const SCEV *, APInt> M; in getAddExpr()
2751 SmallVector<const SCEV *, 8> NewOps; in getAddExpr()
2764 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists; in getAddExpr()
2765 for (const SCEV *NewOp : NewOps) in getAddExpr()
2773 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2777 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1), in getAddExpr()
2778 SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2785 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2795 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); in getAddExpr()
2801 const SCEV *InnerMul = Mul->getOperand(MulOp == 0); in getAddExpr()
2805 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2808 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2810 SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul}; in getAddExpr()
2811 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2812 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV, in getAddExpr()
2813 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2823 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2837 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); in getAddExpr()
2839 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2842 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2844 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); in getAddExpr()
2846 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2849 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2851 SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2}; in getAddExpr()
2852 const SCEV *InnerMulSum = in getAddExpr()
2853 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2854 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum, in getAddExpr()
2855 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2860 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2876 SmallVector<const SCEV *, 8> LIOps; in getAddExpr()
2892 SCEV::NoWrapFlags Flags = ComputeFlags(LIOps); in getAddExpr()
2898 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2910 SCEV::NoWrapFlags AddFlags = Flags; in getAddExpr()
2911 if (AddFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2915 AddFlags = SCEV::FlagAnyWrap; in getAddExpr()
2922 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); in getAddExpr()
2923 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); in getAddExpr()
2934 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2951 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2962 SmallVector<const SCEV *, 2> TwoOps = { in getAddExpr()
2964 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2970 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); in getAddExpr()
2971 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2984 const SCEV *
2985 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddExpr()
2986 SCEV::NoWrapFlags Flags) { in getOrCreateAddExpr()
2989 for (const SCEV *Op : Ops) in getOrCreateAddExpr()
2995 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddExpr()
3006 const SCEV *
3007 ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddRecExpr()
3008 const Loop *L, SCEV::NoWrapFlags Flags) { in getOrCreateAddRecExpr()
3011 for (const SCEV *Op : Ops) in getOrCreateAddRecExpr()
3018 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddRecExpr()
3030 const SCEV *
3031 ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, in getOrCreateMulExpr()
3032 SCEV::NoWrapFlags Flags) { in getOrCreateMulExpr()
3035 for (const SCEV *Op : Ops) in getOrCreateMulExpr()
3041 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateMulExpr()
3086 static bool containsConstantInAddMulChain(const SCEV *StartExpr) { in containsConstantInAddMulChain()
3090 bool follow(const SCEV *S) { in containsConstantInAddMulChain()
3107 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, in getMulExpr()
3108 SCEV::NoWrapFlags OrigFlags, in getMulExpr()
3110 assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) && in getMulExpr()
3153 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getMulExpr()
3161 if (SCEV *S = findExistingSCEVInCache(scMulExpr, Ops)) { in getMulExpr()
3180 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0), in getMulExpr()
3181 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3182 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1), in getMulExpr()
3183 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3184 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3191 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3193 for (const SCEV *AddOp : Add->operands()) { in getMulExpr()
3194 const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap, in getMulExpr()
3200 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3203 SmallVector<const SCEV *, 4> Operands; in getMulExpr()
3204 for (const SCEV *AddRecOp : AddRec->operands()) in getMulExpr()
3205 Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap, in getMulExpr()
3212 auto FlagsMask = SCEV::FlagNW; in getMulExpr()
3213 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) { in getMulExpr()
3217 FlagsMask = setFlags(FlagsMask, SCEV::FlagNSW); in getMulExpr()
3247 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3260 SmallVector<const SCEV *, 8> LIOps; in getMulExpr()
3272 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3274 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3280 SCEV::NoWrapFlags Flags = in getMulExpr()
3285 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3287 if (hasFlags(Flags, SCEV::FlagNSW) && !hasFlags(Flags, SCEV::FlagNUW)) { in getMulExpr()
3292 Flags = clearFlags(Flags, SCEV::FlagNSW); in getMulExpr()
3296 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags); in getMulExpr()
3307 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3342 SmallVector<const SCEV*, 7> AddRecOps; in getMulExpr()
3345 SmallVector <const SCEV *, 7> SumOps; in getMulExpr()
3357 const SCEV *CoeffTerm = getConstant(Ty, Coeff); in getMulExpr()
3358 const SCEV *Term1 = AddRec->getOperand(y-z); in getMulExpr()
3359 const SCEV *Term2 = OtherAddRec->getOperand(z); in getMulExpr()
3361 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3366 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3369 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(), in getMulExpr()
3370 SCEV::FlagAnyWrap); in getMulExpr()
3381 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3393 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, in getURemExpr()
3394 const SCEV *RHS) { in getURemExpr()
3415 const SCEV *UDiv = getUDivExpr(LHS, RHS); in getURemExpr()
3416 const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW); in getURemExpr()
3417 return getMinusSCEV(LHS, Mult, SCEV::FlagNUW); in getURemExpr()
3422 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, in getUDivExpr()
3423 const SCEV *RHS) { in getUDivExpr()
3434 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3471 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3472 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3473 for (const SCEV *Op : AR->operands()) in getUDivExpr()
3475 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3485 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3489 const SCEV *NewLHS = in getUDivExpr()
3491 AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3502 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3510 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3511 for (const SCEV *Op : M->operands()) in getUDivExpr()
3516 const SCEV *Op = M->getOperand(i); in getUDivExpr()
3517 const SCEV *Div = getUDivExpr(Op, RHSC); in getUDivExpr()
3519 Operands = SmallVector<const SCEV *, 4>(M->operands()); in getUDivExpr()
3542 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3543 for (const SCEV *Op : A->operands()) in getUDivExpr()
3548 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); in getUDivExpr()
3568 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getUDivExpr()
3569 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), in getUDivExpr()
3594 const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS, in getUDivExactExpr()
3595 const SCEV *RHS) { in getUDivExactExpr()
3609 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands())); in getUDivExactExpr()
3622 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3636 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3648 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, in getAddRecExpr()
3650 SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3651 SmallVector<const SCEV *, 4> Operands; in getAddRecExpr()
3656 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW)); in getAddRecExpr()
3665 const SCEV *
3666 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, in getAddRecExpr()
3667 const Loop *L, SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3671 for (const SCEV *Op : llvm::drop_begin(Operands)) { in getAddRecExpr()
3676 for (const SCEV *Op : Operands) in getAddRecExpr()
3683 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X in getAddRecExpr()
3701 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands()); in getAddRecExpr()
3707 Operands, [&](const SCEV *Op) { return isLoopInvariant(Op, L); }); in getAddRecExpr()
3714 SCEV::NoWrapFlags OuterFlags = in getAddRecExpr()
3715 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); in getAddRecExpr()
3718 AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) { in getAddRecExpr()
3727 SCEV::NoWrapFlags InnerFlags = in getAddRecExpr()
3728 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); in getAddRecExpr()
3742 const SCEV *
3744 const SmallVectorImpl<const SCEV *> &IndexExprs) { in getGEPExpr()
3745 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); in getGEPExpr()
3761 SCEV::NoWrapFlags OffsetWrap = SCEV::FlagAnyWrap; in getGEPExpr()
3763 OffsetWrap = setFlags(OffsetWrap, SCEV::FlagNSW); in getGEPExpr()
3765 OffsetWrap = setFlags(OffsetWrap, SCEV::FlagNUW); in getGEPExpr()
3769 SmallVector<const SCEV *, 4> Offsets; in getGEPExpr()
3770 for (const SCEV *IndexExpr : IndexExprs) { in getGEPExpr()
3776 const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); in getGEPExpr()
3792 const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); in getGEPExpr()
3797 const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, OffsetWrap); in getGEPExpr()
3807 const SCEV *Offset = getAddExpr(Offsets, OffsetWrap); in getGEPExpr()
3813 SCEV::NoWrapFlags BaseWrap = NUW ? SCEV::FlagNUW : SCEV::FlagAnyWrap; in getGEPExpr()
3820 SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType, in findExistingSCEVInCache()
3821 ArrayRef<const SCEV *> Ops) { in findExistingSCEVInCache()
3824 for (const SCEV *Op : Ops) in findExistingSCEVInCache()
3830 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) { in getAbsExpr()
3831 SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getAbsExpr()
3835 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind, in getMinMaxExpr()
3836 SmallVectorImpl<const SCEV *> &Ops) { in getMinMaxExpr()
3858 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) { in getMinMaxExpr()
3961 for (const SCEV *Op : Ops) in getMinMaxExpr()
3964 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getMinMaxExpr()
3967 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getMinMaxExpr()
3969 SCEV *S = new (SCEVAllocator) in getMinMaxExpr()
3981 std::optional<const SCEV *>> {
3982 using RetVal = std::optional<const SCEV *>;
3988 SmallPtrSet<const SCEV *, 16> SeenOps;
3996 RetVal visitAnyMinMaxExpr(const SCEV *S) { in visitAnyMinMaxExpr()
4005 SmallVector<const SCEV *> NewOps; in visitAnyMinMaxExpr()
4018 RetVal visit(const SCEV *S) { in visit()
4033 bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps, in visit()
4034 SmallVectorImpl<const SCEV *> &NewOps) { in visit()
4036 SmallVector<const SCEV *> Ops; in visit()
4039 for (const SCEV *Op : OrigOps) { in visit()
4142 bool follow(const SCEV *S) { in follow()
4158 static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) { in impliesPoison()
4185 SmallPtrSetImpl<const Value *> &Result, const SCEV *S) { in getPoisonGeneratingValues()
4193 const SCEV *S, Instruction *I, in canReuseInstruction()
4254 const SCEV *
4256 SmallVectorImpl<const SCEV *> &Ops) { in getSequentialMinMaxExpr()
4277 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) in getSequentialMinMaxExpr()
4311 const SCEV *SaturationPoint; in getSequentialMinMaxExpr()
4329 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]}; in getSequentialMinMaxExpr()
4348 for (const SCEV *Op : Ops) in getSequentialMinMaxExpr()
4351 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getSequentialMinMaxExpr()
4355 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getSequentialMinMaxExpr()
4357 SCEV *S = new (SCEVAllocator) in getSequentialMinMaxExpr()
4365 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getSMaxExpr()
4366 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getSMaxExpr()
4370 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMaxExpr()
4374 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getUMaxExpr()
4375 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getUMaxExpr()
4379 const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getUMaxExpr()
4383 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, in getSMinExpr()
4384 const SCEV *RHS) { in getSMinExpr()
4385 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getSMinExpr()
4389 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMinExpr()
4393 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS, in getUMinExpr()
4395 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinExpr()
4399 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops, in getUMinExpr()
4405 const SCEV *
4407 const SCEV *Res = getConstant(IntTy, Size.getKnownMinValue()); in getSizeOfExpr()
4413 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) { in getSizeOfExpr()
4417 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) { in getStoreSizeOfExpr()
4421 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy, in getOffsetOfExpr()
4433 const SCEV *ScalarEvolution::getUnknown(Value *V) { in getUnknown()
4443 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) { in getUnknown()
4448 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this, in getUnknown()
4495 bool ScalarEvolution::instructionCouldExistWithOperands(const SCEV *A, in instructionCouldExistWithOperands()
4496 const SCEV *B) { in instructionCouldExistWithOperands()
4509 const SCEV *ScalarEvolution::getCouldNotCompute() { in getCouldNotCompute()
4513 bool ScalarEvolution::checkValidity(const SCEV *S) const { in checkValidity()
4514 bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) { in checkValidity()
4522 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { in containsAddRecurrence()
4528 SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); }); in containsAddRecurrence()
4535 ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) { in getSCEVValues()
4556 void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) { in insertValueToMap()
4569 const SCEV *ScalarEvolution::getSCEV(Value *V) { in getSCEV()
4572 if (const SCEV *S = getExistingSCEV(V)) in getSCEV()
4577 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { in getExistingSCEV()
4582 const SCEV *S = I->second; in getExistingSCEV()
4591 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, in getNegativeSCEV()
4592 SCEV::NoWrapFlags Flags) { in getNegativeSCEV()
4603 static const SCEV *MatchNotExpr(const SCEV *Expr) { in MatchNotExpr()
4618 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { in getNotSCEV()
4628 SmallVector<const SCEV *, 2> MatchedOperands; in getNotSCEV()
4629 for (const SCEV *Operand : MME->operands()) { in getNotSCEV()
4630 const SCEV *Matched = MatchNotExpr(Operand); in getNotSCEV()
4632 return (const SCEV *)nullptr; in getNotSCEV()
4638 if (const SCEV *Replaced = MatchMinMaxNegation(MME)) in getNotSCEV()
4647 const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) { in removePointerBase()
4652 SmallVector<const SCEV *> Ops{AddRec->operands()}; in removePointerBase()
4656 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap); in removePointerBase()
4660 SmallVector<const SCEV *> Ops{Add->operands()}; in removePointerBase()
4661 const SCEV **PtrOp = nullptr; in removePointerBase()
4662 for (const SCEV *&AddOp : Ops) { in removePointerBase()
4677 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, in getMinusSCEV()
4678 SCEV::NoWrapFlags Flags, in getMinusSCEV()
4697 auto AddFlags = SCEV::FlagAnyWrap; in getMinusSCEV()
4700 if (hasFlags(Flags, SCEV::FlagNSW)) { in getMinusSCEV()
4711 AddFlags = SCEV::FlagNSW; in getMinusSCEV()
4722 auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getMinusSCEV()
4727 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty, in getTruncateOrZeroExtend()
4739 const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty, in getTruncateOrSignExtend()
4751 const SCEV *
4752 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { in getNoopOrZeroExtend()
4763 const SCEV *
4764 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { in getNoopOrSignExtend()
4775 const SCEV *
4776 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { in getNoopOrAnyExtend()
4787 const SCEV *
4788 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { in getTruncateOrNoop()
4799 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, in getUMaxFromMismatchedTypes()
4800 const SCEV *RHS) { in getUMaxFromMismatchedTypes()
4801 const SCEV *PromotedLHS = LHS; in getUMaxFromMismatchedTypes()
4802 const SCEV *PromotedRHS = RHS; in getUMaxFromMismatchedTypes()
4812 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, in getUMinFromMismatchedTypes()
4813 const SCEV *RHS, in getUMinFromMismatchedTypes()
4815 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinFromMismatchedTypes()
4819 const SCEV *
4820 ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops, in getUMinFromMismatchedTypes()
4837 SmallVector<const SCEV *, 2> PromotedOps; in getUMinFromMismatchedTypes()
4845 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { in getPointerBase()
4854 const SCEV *PtrOp = nullptr; in getPointerBase()
4855 for (const SCEV *AddOp : Add->operands()) { in getPointerBase()
4889 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
4892 const SCEV *Result = Rewriter.visit(S); in rewrite()
4900 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4906 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4933 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) { in rewrite()
4935 const SCEV *Result = Rewriter.visit(S); in rewrite()
4941 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4947 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4974 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
4993 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4994 const SCEV *Result = Expr; in visitUnknown()
5002 std::optional<const SCEV *> Res = in visitUnknown()
5011 std::optional<const SCEV *> Res = compareWithBackedgeCondition(I); in visitUnknown()
5027 std::optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
5036 std::optional<const SCEV *>
5050 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
5053 const SCEV *Result = Rewriter.visit(S); in rewrite()
5057 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
5064 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
5083 SCEV::NoWrapFlags
5086 return SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
5090 SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
5093 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop()); in proveNoWrapViaConstantRanges()
5100 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNW); in proveNoWrapViaConstantRanges()
5111 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW); in proveNoWrapViaConstantRanges()
5121 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW); in proveNoWrapViaConstantRanges()
5127 SCEV::NoWrapFlags
5129 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoSignedWrapViaInduction()
5141 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoSignedWrapViaInduction()
5152 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoSignedWrapViaInduction()
5171 const SCEV *OverflowLimit = in proveNoSignedWrapViaInduction()
5176 Result = setFlags(Result, SCEV::FlagNSW); in proveNoSignedWrapViaInduction()
5180 SCEV::NoWrapFlags
5182 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoUnsignedWrapViaInduction()
5194 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoUnsignedWrapViaInduction()
5206 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoUnsignedWrapViaInduction()
5225 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - in proveNoUnsignedWrapViaInduction()
5229 Result = setFlags(Result, SCEV::FlagNUW); in proveNoUnsignedWrapViaInduction()
5375 static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, in isSimpleCastedPHI()
5404 const SCEV *X = Trunc->getOperand(); in isSimpleCastedPHI()
5473 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5507 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHIWithCastsImpl()
5533 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHIWithCastsImpl()
5537 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHIWithCastsImpl()
5595 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHIWithCastsImpl()
5596 const SCEV *PHISCEV = in createAddRecFromPHIWithCastsImpl()
5598 getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5623 auto getExtendedExpr = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5624 bool CreateSignExtend) -> const SCEV * { in createAddRecFromPHIWithCastsImpl()
5626 const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy); in createAddRecFromPHIWithCastsImpl()
5627 const SCEV *ExtendedExpr = in createAddRecFromPHIWithCastsImpl()
5638 auto PredIsKnownFalse = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5639 const SCEV *ExtendedExpr) -> bool { in createAddRecFromPHIWithCastsImpl()
5644 const SCEV *StartExtended = getExtendedExpr(StartVal, Signed); in createAddRecFromPHIWithCastsImpl()
5652 const SCEV *AccumExtended = getExtendedExpr(Accum, /*CreateSignExtend=*/true); in createAddRecFromPHIWithCastsImpl()
5658 auto AppendPredicate = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5659 const SCEV *ExtendedExpr) -> void { in createAddRecFromPHIWithCastsImpl()
5675 auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5677 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite = in createAddRecFromPHIWithCastsImpl()
5684 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5694 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite = in createAddRecFromPHIWithCasts()
5706 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in createAddRecFromPHIWithCasts()
5730 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool { in areAddRecsEqualWithPreds()
5749 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN, in createSimpleAffineAddRec()
5763 const SCEV *Accum = nullptr; in createSimpleAffineAddRec()
5772 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSimpleAffineAddRec()
5774 Flags = setFlags(Flags, SCEV::FlagNUW); in createSimpleAffineAddRec()
5776 Flags = setFlags(Flags, SCEV::FlagNSW); in createSimpleAffineAddRec()
5778 const SCEV *StartVal = getSCEV(StartValueV); in createSimpleAffineAddRec()
5779 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createSimpleAffineAddRec()
5784 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() | in createSimpleAffineAddRec()
5801 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { in createAddRecFromPHI()
5838 const SCEV *SymbolicName = getUnknown(PN); in createAddRecFromPHI()
5843 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHI()
5863 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHI()
5868 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHI()
5875 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createAddRecFromPHI()
5880 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5882 Flags = setFlags(Flags, SCEV::FlagNSW); in createAddRecFromPHI()
5890 Flags = setFlags(Flags, SCEV::FlagNW); in createAddRecFromPHI()
5896 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5904 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5905 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createAddRecFromPHI()
5915 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() | in createAddRecFromPHI()
5939 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this); in createAddRecFromPHI()
5940 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false); in createAddRecFromPHI()
5943 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5997 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { in createNodeFromSelectLikePHI()
6029 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { in createNodeForPHI()
6030 if (const SCEV *S = createAddRecFromPHI(PN)) in createNodeForPHI()
6036 if (const SCEV *S = createNodeFromSelectLikePHI(PN)) in createNodeForPHI()
6043 bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, in SCEVMinMaxExprContains()
6046 const SCEV *OperandToFind; in SCEVMinMaxExprContains()
6059 FindClosure(const SCEV *OperandToFind, SCEVTypes RootKind) in SCEVMinMaxExprContains()
6065 bool follow(const SCEV *S) { in SCEVMinMaxExprContains()
6079 std::optional<const SCEV *>
6105 const SCEV *LA = getSCEV(TrueVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6106 const SCEV *RA = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6107 const SCEV *LS = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6108 const SCEV *RS = getSCEV(RHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6118 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * { in createNodeForSelectOrPHIInstWithICmpInstCond()
6134 const SCEV *LDiff = getMinusSCEV(LA, LS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6135 const SCEV *RDiff = getMinusSCEV(RA, RS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6154 const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), Ty); in createNodeForSelectOrPHIInstWithICmpInstCond()
6155 const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6156 const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6157 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x in createNodeForSelectOrPHIInstWithICmpInstCond()
6158 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y in createNodeForSelectOrPHIInstWithICmpInstCond()
6168 const SCEV *X = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6172 const SCEV *FalseValExpr = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6186 static std::optional<const SCEV *>
6187 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, in createNodeForSelectViaUMinSeq()
6188 const SCEV *TrueExpr, const SCEV *FalseExpr) { in createNodeForSelectViaUMinSeq()
6206 const SCEV *X, *C; in createNodeForSelectViaUMinSeq()
6219 static std::optional<const SCEV *>
6231 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq( in createNodeForSelectOrPHIViaUMinSeq()
6242 if (std::optional<const SCEV *> S = in createNodeForSelectOrPHIViaUMinSeq()
6249 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond, in createNodeForSelectOrPHI()
6259 if (std::optional<const SCEV *> S = in createNodeForSelectOrPHI()
6271 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { in createNodeForGEP()
6275 SmallVector<const SCEV *, 4> IndexExprs; in createNodeForGEP()
6281 APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) { in getConstantMultipleImpl()
6326 for (const SCEV *Operand : M->operands().drop_front()) in getConstantMultipleImpl()
6334 for (const SCEV *Operand : M->operands()) in getConstantMultipleImpl()
6345 for (const SCEV *Operand : N->operands().drop_front()) in getConstantMultipleImpl()
6369 APInt ScalarEvolution::getConstantMultiple(const SCEV *S) { in getConstantMultiple()
6380 APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) { in getNonZeroConstantMultiple()
6385 uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) { in getMinTrailingZeros()
6407 SCEV::NoWrapFlags Flags) { in setNoWrapFlags()
6536 ScalarEvolution::getRangeRefIter(const SCEV *S, in getRangeRefIter()
6538 DenseMap<const SCEV *, ConstantRange> &Cache = in getRangeRefIter()
6541 SmallVector<const SCEV *> WorkList; in getRangeRefIter()
6542 SmallPtrSet<const SCEV *, 8> Seen; in getRangeRefIter()
6546 auto AddToWorklist = [&WorkList, &Seen, &Cache](const SCEV *Expr) { in getRangeRefIter()
6581 const SCEV *P = WorkList[I]; in getRangeRefIter()
6585 for (const SCEV *Op : P->operands()) in getRangeRefIter()
6602 for (const SCEV *P : reverse(drop_begin(WorkList))) { in getRangeRefIter()
6618 const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) { in getRangeRef()
6619 DenseMap<const SCEV *, ConstantRange> &Cache = in getRangeRef()
6627 DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S); in getRangeRef()
6762 const SCEV *MaxBEScev = in getRangeRef()
6790 const SCEV *SymbolicMaxBECount = in getRangeRef()
7021 ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, in getRangeForAffineAR()
7022 const SCEV *Step, in getRangeForAffineAR()
7051 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth, in getRangeForAffineNoSelfWrappingAR()
7057 const SCEV *Step = AddRec->getStepRecurrence(*this); in getRangeForAffineNoSelfWrappingAR()
7070 const SCEV *RangeWidth = getMinusOne(AddRec->getType()); in getRangeForAffineNoSelfWrappingAR()
7071 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step)); in getRangeForAffineNoSelfWrappingAR()
7072 const SCEV *MaxItersWithoutWrap = getUDivExpr(RangeWidth, StepAbs); in getRangeForAffineNoSelfWrappingAR()
7081 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); in getRangeForAffineNoSelfWrappingAR()
7095 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop()); in getRangeForAffineNoSelfWrappingAR()
7118 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, in getRangeViaFactoring()
7119 const SCEV *Step, in getRangeViaFactoring()
7135 const SCEV *S) { in getRangeViaFactoring()
7224 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue); in getRangeViaFactoring()
7225 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue); in getRangeViaFactoring()
7226 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue); in getRangeViaFactoring()
7227 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue); in getRangeViaFactoring()
7237 SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) { in getNoWrapFlagsFromUB()
7238 if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7242 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7244 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getNoWrapFlagsFromUB()
7246 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getNoWrapFlagsFromUB()
7247 if (Flags == SCEV::FlagAnyWrap) in getNoWrapFlagsFromUB()
7248 return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7250 return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7254 ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) { in getNonTrivialDefiningScopeBound()
7264 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops, in getDefiningScopeBound()
7268 SmallSet<const SCEV *, 16> Visited; in getDefiningScopeBound()
7269 SmallVector<const SCEV *> Worklist; in getDefiningScopeBound()
7270 auto pushOp = [&](const SCEV *S) { in getDefiningScopeBound()
7299 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) { in getDefiningScopeBound()
7339 SmallVector<const SCEV *> SCEVOps; in isSCEVExprNeverPoison()
7435 const SCEV *ScalarEvolution::createSCEVIter(Value *V) { in createSCEVIter()
7451 const SCEV *CreatedSCEV = nullptr; in createSCEVIter()
7476 const SCEV *
7663 const SCEV *ScalarEvolution::createSCEV(Value *V) { in createSCEV()
7681 const SCEV *LHS; in createSCEV()
7682 const SCEV *RHS; in createSCEV()
7695 SmallVector<const SCEV *, 4> AddOps; in createSCEV()
7710 const SCEV *RHS = getSCEV(BO->RHS); in createSCEV()
7711 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7712 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7713 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7741 SmallVector<const SCEV *, 4> MulOps; in createSCEV()
7749 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7750 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7779 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSCEV()
7810 const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ)); in createSCEV()
7811 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7812 const SCEV *ShiftedLHS = nullptr; in createSCEV()
7819 SmallVector<const SCEV*, 4> MulOps; in createSCEV()
7870 const SCEV *Z0 = Z->getOperand(); in createSCEV()
7908 auto Flags = SCEV::FlagAnyWrap; in createSCEV()
7911 if ((MulFlags & SCEV::FlagNSW) && in createSCEV()
7912 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1))) in createSCEV()
7913 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW); in createSCEV()
7914 if (MulFlags & SCEV::FlagNUW) in createSCEV()
7915 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW); in createSCEV()
7946 const SCEV *AddTruncateExpr = nullptr; in createSCEV()
7948 const SCEV *AddConstant = nullptr; in createSCEV()
7960 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0)); in createSCEV()
7978 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0)); in createSCEV()
7999 const SCEV *CompositeExpr = in createSCEV()
8032 return getMinusSCEV(V1, V2, SCEV::FlagNSW); in createSCEV()
8045 const SCEV *Op = getSCEV(U->getOperand(0)); in createSCEV()
8049 const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy); in createSCEV()
8110 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
8111 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
8112 const SCEV *ClampedY = getUMinExpr(X, Y); in createSCEV()
8113 return getMinusSCEV(X, ClampedY, SCEV::FlagNUW); in createSCEV()
8116 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
8117 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
8118 const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y)); in createSCEV()
8119 return getAddExpr(ClampedX, Y, SCEV::FlagNUW); in createSCEV()
8143 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount) { in getTripCountFromExitCount()
8154 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount, in getTripCountFromExitCount()
8235 const SCEV *ExitCount) { in getSmallConstantTripMultiple()
8240 const SCEV *TCExpr = getTripCountFromExitCount(applyLoopGuards(ExitCount, L)); in getSmallConstantTripMultiple()
8268 const SCEV *ExitCount = getExitCount(L, ExitingBlock); in getSmallConstantTripMultiple()
8272 const SCEV *ScalarEvolution::getExitCount(const Loop *L, in getExitCount()
8286 const SCEV *
8292 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, in getBackedgeTakenCount()
8305 const SCEV *ScalarEvolution::getPredicatedSymbolicMaxBackedgeTakenCount( in getPredicatedSymbolicMaxBackedgeTakenCount()
8367 SmallVector<const SCEV *, 8> ToForget; in getBackedgeTakenInfo()
8414 SmallVectorImpl<const SCEV *> &ToForget) { in visitAndClearUsers()
8437 SmallVector<const SCEV *, 16> ToForget; in forgetLoop()
8450 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetLoop()
8486 SmallVector<const SCEV *, 8> ToForget; in forgetValue()
8502 if (const SCEV *S = getExistingSCEV(V)) { in forgetLcssaPhiWithNewPredecessor()
8505 SmallVector<const SCEV *, 8> Roots; in forgetLcssaPhiWithNewPredecessor()
8509 bool follow(const SCEV *S) { in forgetLcssaPhiWithNewPredecessor()
8546 const SCEV *S = getExistingSCEV(V); in forgetBlockAndLoopDispositions()
8554 SmallVector<const SCEV *, 8> Worklist = {S}; in forgetBlockAndLoopDispositions()
8555 SmallPtrSet<const SCEV *, 8> Seen = {S}; in forgetBlockAndLoopDispositions()
8557 const SCEV *Curr = Worklist.pop_back_val(); in forgetBlockAndLoopDispositions()
8576 const SCEV *
8590 SmallVector<const SCEV *, 2> Ops; in getExact()
8592 const SCEV *BECount = ENT.ExactNotTaken; in getExact()
8615 const SCEV *
8625 const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax( in getConstantMax()
8634 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax( in getSymbolicMax()
8644 const SCEV *
8659 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax( in getSymbolicMax()
8667 SmallVector<const SCEV *, 4> ExitCounts; in getSymbolicMax()
8670 const SCEV *ExitCount = ENT.SymbolicMaxNotTaken; in getSymbolicMax()
8701 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) in ExitLimit()
8705 const SCEV *E, const SCEV *ConstantMaxNotTaken, in ExitLimit()
8706 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero, in ExitLimit()
8741 const SCEV *E, const SCEV *ConstantMaxNotTaken, in ExitLimit()
8742 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero, in ExitLimit()
8751 bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero) in BackedgeTakenInfo()
8782 const SCEV *MustExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8783 const SCEV *MayExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8853 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : in computeBackedgeTakenCount()
9061 const SCEV *BECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9062 const SCEV *ConstantMaxBECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9063 const SCEV *SymbolicMaxBECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9121 const SCEV *LHS = getSCEV(ExitCond->getOperand(0)); in computeExitLimitFromICmp()
9122 const SCEV *RHS = getSCEV(ExitCond->getOperand(1)); in computeExitLimitFromICmp()
9139 const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in computeExitLimitFromICmp()
9168 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this); in computeExitLimitFromICmp()
9188 Flags = setFlags(Flags, SCEV::FlagNW); in computeExitLimitFromICmp()
9189 SmallVector<const SCEV*> Operands{AR->operands()}; in computeExitLimitFromICmp()
9304 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L); in computeExitLimitFromSingleExitSwitch()
9305 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock)); in computeExitLimitFromSingleExitSwitch()
9318 const SCEV *InVal = SE.getConstant(C); in EvaluateConstantChrecAtConstant()
9319 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE); in EvaluateConstantChrecAtConstant()
9460 const SCEV *UpperBound = in computeShiftCompareExitLimit()
9710 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L, in computeExitCountExhaustively()
9777 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { in getSCEVAtScope()
9778 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values = in getSCEVAtScope()
9788 const SCEV *C = computeSCEVAtScope(V, L); in getSCEVAtScope()
9803 static Constant *BuildConstantFromSCEV(const SCEV *V) { in BuildConstantFromSCEV()
9829 for (const SCEV *Op : SA->operands()) { in BuildConstantFromSCEV()
9864 const SCEV *
9865 ScalarEvolution::getWithOperands(const SCEV *S, in getWithOperands()
9866 SmallVectorImpl<const SCEV *> &NewOps) { in getWithOperands()
9900 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { in computeSCEVAtScope()
9913 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); in computeSCEVAtScope()
9919 SmallVector<const SCEV *, 8> NewOps; in computeSCEVAtScope()
9926 const SCEV *FoldedRec = getAddRecExpr( in computeSCEVAtScope()
9927 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW)); in computeSCEVAtScope()
9942 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); in computeSCEVAtScope()
9964 ArrayRef<const SCEV *> Ops = V->operands(); in computeSCEVAtScope()
9968 const SCEV *OpAtScope = getSCEVAtScope(Ops[i], L); in computeSCEVAtScope()
9972 SmallVector<const SCEV *, 8> NewOps; in computeSCEVAtScope()
10005 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(CurrLoop); in computeSCEVAtScope()
10070 const SCEV *OrigV = getSCEV(Op); in computeSCEVAtScope()
10071 const SCEV *OpV = getSCEVAtScope(OrigV, L); in computeSCEVAtScope()
10099 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { in getSCEVAtScope()
10103 const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const { in stripInjectiveFunctions()
10119 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, in SolveLinEquationWithOverflow()
10152 const SCEV *D = SE.getConstant(APInt::getOneBitSet(BW, Mult2)); in SolveLinEquationWithOverflow()
10429 ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V, in howFarToZero()
10488 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); in howFarToZero()
10489 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); in howFarToZero()
10497 const SCEV *StepWLG = applyLoopGuards(Step, Guards); in howFarToZero()
10508 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start); in howFarToZero()
10524 const SCEV *Zero = getZero(Distance->getType()); in howFarToZero()
10525 const SCEV *One = getOne(Distance->getType()); in howFarToZero()
10526 const SCEV *DistancePlusOne = getAddExpr(Distance, One); in howFarToZero()
10551 const SCEV *Exact = in howFarToZero()
10553 const SCEV *ConstantMax = getCouldNotCompute(); in howFarToZero()
10559 const SCEV *SymbolicMax = in howFarToZero()
10567 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(), in howFarToZero()
10570 const SCEV *M = E; in howFarToZero()
10580 ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { in howFarToNonZero()
10620 static bool HasSameValue(const SCEV *A, const SCEV *B) { in HasSameValue()
10644 static bool MatchBinarySub(const SCEV *S, const SCEV *&LHS, const SCEV *&RHS) { in MatchBinarySub()
10664 const SCEV *&LHS, const SCEV *&RHS, in SimplifyICmpOperands()
10787 SCEV::FlagNSW); in SimplifyICmpOperands()
10792 SCEV::FlagNSW); in SimplifyICmpOperands()
10800 SCEV::FlagNSW); in SimplifyICmpOperands()
10805 SCEV::FlagNSW); in SimplifyICmpOperands()
10813 SCEV::FlagNUW); in SimplifyICmpOperands()
10829 SCEV::FlagNUW); in SimplifyICmpOperands()
10848 bool ScalarEvolution::isKnownNegative(const SCEV *S) { in isKnownNegative()
10852 bool ScalarEvolution::isKnownPositive(const SCEV *S) { in isKnownPositive()
10856 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) { in isKnownNonNegative()
10860 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) { in isKnownNonPositive()
10864 bool ScalarEvolution::isKnownNonZero(const SCEV *S) { in isKnownNonZero()
10872 std::pair<const SCEV *, const SCEV *>
10873 ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) { in SplitIntoInitAndPostInc()
10875 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10879 const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10885 const SCEV *LHS, const SCEV *RHS) { in isKnownViaInduction()
10935 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicate()
10950 const SCEV *LHS, in evaluatePredicate()
10951 const SCEV *RHS) { in evaluatePredicate()
10960 const SCEV *LHS, const SCEV *RHS, in isKnownPredicateAt()
10968 ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, in evaluatePredicateAt()
10969 const SCEV *RHS, const Instruction *CtxI) { in evaluatePredicateAt()
10985 const SCEV *RHS) { in isKnownOnEveryIteration()
11043 const SCEV *Step = LHS->getStepRecurrence(*this); in getMonotonicPredicateTypeImpl()
11056 const SCEV *LHS, const SCEV *RHS, in getLoopInvariantPredicate()
11142 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, in getLoopInvariantExitCondDuringFirstIterations()
11143 const Instruction *CtxI, const SCEV *MaxIter) { in getLoopInvariantExitCondDuringFirstIterations()
11162 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, in getLoopInvariantExitCondDuringFirstIterationsImpl()
11163 const Instruction *CtxI, const SCEV *MaxIter) { in getLoopInvariantExitCondDuringFirstIterationsImpl()
11190 const SCEV *Step = AR->getStepRecurrence(*this); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11203 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11216 const SCEV *Start = AR->getStart(); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11225 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateViaConstantRanges()
11267 const SCEV *LHS, in isKnownPredicateViaNoOverflow()
11268 const SCEV *RHS) { in isKnownPredicateViaNoOverflow()
11273 auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y, in isKnownPredicateViaNoOverflow()
11275 SCEV::NoWrapFlags ExpectedFlags) { in isKnownPredicateViaNoOverflow()
11276 const SCEV *XNonConstOp, *XConstOp; in isKnownPredicateViaNoOverflow()
11277 const SCEV *YNonConstOp, *YConstOp; in isKnownPredicateViaNoOverflow()
11278 SCEV::NoWrapFlags XFlagsPresent; in isKnownPredicateViaNoOverflow()
11279 SCEV::NoWrapFlags YFlagsPresent; in isKnownPredicateViaNoOverflow()
11321 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2)) in isKnownPredicateViaNoOverflow()
11331 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2)) in isKnownPredicateViaNoOverflow()
11341 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNUW) && C1.ule(C2)) in isKnownPredicateViaNoOverflow()
11351 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNUW) && C1.ult(C2)) in isKnownPredicateViaNoOverflow()
11360 const SCEV *LHS, in isKnownPredicateViaSplitting()
11361 const SCEV *RHS) { in isKnownPredicateViaSplitting()
11383 const SCEV *LHS, const SCEV *RHS) { in isImpliedViaGuard()
11404 const SCEV *LHS, const SCEV *RHS) { in isLoopBackedgeGuardedByCond()
11440 const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this); in isLoopBackedgeGuardedByCond()
11446 auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW); in isLoopBackedgeGuardedByCond()
11447 const SCEV *LoopCounter = in isLoopBackedgeGuardedByCond()
11509 const SCEV *LHS, in isBasicBlockEntryGuardedByCond()
11510 const SCEV *RHS) { in isBasicBlockEntryGuardedByCond()
11609 const SCEV *LHS, in isLoopEntryGuardedByCond()
11610 const SCEV *RHS) { in isLoopEntryGuardedByCond()
11628 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11629 const SCEV *RHS, in isImpliedCond()
11666 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0)); in isImpliedCond()
11667 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1)); in isImpliedCond()
11672 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11673 const SCEV *RHS, in isImpliedCond()
11675 const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCond()
11688 const SCEV *MaxValue = getZeroExtendExpr( in isImpliedCond()
11694 const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType); in isImpliedCond()
11695 const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType); in isImpliedCond()
11728 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondBalancedTypes()
11729 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCondBalancedTypes()
11808 const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS, in isImpliedCondBalancedTypes()
11842 const SCEV *V = nullptr; in isImpliedCondBalancedTypes()
11931 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr, in splitBinaryAdd()
11932 const SCEV *&L, const SCEV *&R, in splitBinaryAdd()
11933 SCEV::NoWrapFlags &Flags) { in splitBinaryAdd()
11945 ScalarEvolution::computeConstantDifference(const SCEV *More, const SCEV *Less) { in computeConstantDifference()
11980 SCEV::NoWrapFlags Flags; in computeConstantDifference()
11981 const SCEV *LLess = nullptr, *RLess = nullptr; in computeConstantDifference()
11982 const SCEV *LMore = nullptr, *RMore = nullptr; in computeConstantDifference()
12004 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaAddRecStart()
12005 const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) { in isImpliedCondOperandsViaAddRecStart()
12049 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaNoOverflow()
12050 const SCEV *FoundLHS, const SCEV *FoundRHS) { in isImpliedCondOperandsViaNoOverflow()
12126 const SCEV *LHS, const SCEV *RHS, in isImpliedViaMerge()
12127 const SCEV *FoundLHS, in isImpliedViaMerge()
12128 const SCEV *FoundRHS, unsigned Depth) { in isImpliedViaMerge()
12182 auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaMerge()
12194 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12195 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12210 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor)); in isImpliedViaMerge()
12215 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch)); in isImpliedViaMerge()
12227 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12240 const SCEV *LHS, in isImpliedCondOperandsViaShift()
12241 const SCEV *RHS, in isImpliedCondOperandsViaShift()
12242 const SCEV *FoundLHS, in isImpliedCondOperandsViaShift()
12243 const SCEV *FoundRHS) { in isImpliedCondOperandsViaShift()
12282 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperands()
12283 const SCEV *FoundLHS, in isImpliedCondOperands()
12284 const SCEV *FoundRHS, in isImpliedCondOperands()
12305 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, in IsMinMaxConsistingOf()
12306 const SCEV *Candidate) { in IsMinMaxConsistingOf()
12316 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaAddRecStart()
12338 SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ? in IsKnownPredicateViaAddRecStart()
12339 SCEV::FlagNSW : SCEV::FlagNUW; in IsKnownPredicateViaAddRecStart()
12350 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaMinOrMax()
12381 const SCEV *LHS, const SCEV *RHS, in isImpliedViaOperations()
12382 const SCEV *FoundLHS, in isImpliedViaOperations()
12383 const SCEV *FoundRHS, in isImpliedViaOperations()
12411 const SCEV *MinusOne = getMinusOne(LHS->getType()); in isImpliedViaOperations()
12422 auto GetOpFromSExt = [&](const SCEV *S) { in isImpliedViaOperations()
12437 auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12461 auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12549 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateExtendIdiom()
12582 const SCEV *LHS, const SCEV *RHS) { in isKnownViaNonRecursiveReasoning()
12592 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsHelper()
12593 const SCEV *FoundLHS, in isImpliedCondOperandsHelper()
12594 const SCEV *FoundRHS) { in isImpliedCondOperandsHelper()
12636 const SCEV *LHS, in isImpliedCondOperandsViaRanges()
12637 const SCEV *RHS, in isImpliedCondOperandsViaRanges()
12639 const SCEV *FoundLHS, in isImpliedCondOperandsViaRanges()
12640 const SCEV *FoundRHS) { in isImpliedCondOperandsViaRanges()
12668 bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnLT()
12673 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnLT()
12692 bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnGT()
12696 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnGT()
12715 const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) { in getUDivCeilSCEV()
12719 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType())); in getUDivCeilSCEV()
12720 const SCEV *NMinusOne = getMinusSCEV(N, MinNOne); in getUDivCeilSCEV()
12724 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start, in computeMaxBECountForLT()
12725 const SCEV *Stride, in computeMaxBECountForLT()
12726 const SCEV *End, in computeMaxBECountForLT()
12774 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, in howManyLessThans()
12842 if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW()) in howManyLessThans()
12843 Flags = setFlags(Flags, SCEV::FlagNUW); in howManyLessThans()
12849 const SCEV *Step = AR->getStepRecurrence(*this); in howManyLessThans()
12883 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyLessThans()
12887 const SCEV *Stride = IV->getStepRecurrence(*this); in howManyLessThans()
12987 const SCEV *Start = IV->getStart(); in howManyLessThans()
12993 const SCEV *OrigStart = Start; in howManyLessThans()
12994 const SCEV *OrigRHS = RHS; in howManyLessThans()
13006 const SCEV *End = nullptr, *BECount = nullptr, in howManyLessThans()
13024 const SCEV *RHSStart = RHSAddRec->getStart(); in howManyLessThans()
13025 const SCEV *RHSStride = RHSAddRec->getStepRecurrence(*this); in howManyLessThans()
13037 const SCEV *Denominator = getMinusSCEV(Stride, RHSStride); in howManyLessThans()
13043 const SCEV *Delta = getMinusSCEV(End, Start); in howManyLessThans()
13056 const SCEV *MaxBECount = computeMaxBECountForLT( in howManyLessThans()
13092 const SCEV *MinusOne = getMinusOne(Stride->getType()); in howManyLessThans()
13093 const SCEV *Numerator = in howManyLessThans()
13101 const SCEV *GuardedRHS = applyLoopGuards(OrigRHS, L); in howManyLessThans()
13102 const SCEV *GuardedStart = applyLoopGuards(OrigStart, L); in howManyLessThans()
13155 const SCEV *One = getOne(Stride->getType()); in howManyLessThans()
13217 const SCEV *Delta = getMinusSCEV(End, Start); in howManyLessThans()
13230 const SCEV *ConstantMaxBECount; in howManyLessThans()
13250 const SCEV *SymbolicMaxBECount = in howManyLessThans()
13257 const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned, in howManyGreaterThans()
13275 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyGreaterThans()
13279 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this)); in howManyGreaterThans()
13293 const SCEV *Start = IV->getStart(); in howManyGreaterThans()
13294 const SCEV *End = RHS; in howManyGreaterThans()
13319 const SCEV *One = getOne(Stride->getType()); in howManyGreaterThans()
13320 const SCEV *BECount = getUDivExpr( in howManyGreaterThans()
13340 const SCEV *ConstantMaxBECount = in howManyGreaterThans()
13348 const SCEV *SymbolicMaxBECount = in howManyGreaterThans()
13355 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range, in getNumIterationsInRange()
13363 SmallVector<const SCEV *, 4> Operands(operands()); in getNumIterationsInRange()
13365 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(), in getNumIterationsInRange()
13376 if (any_of(operands(), [](const SCEV *Op) { return !isa<SCEVConstant>(Op); })) in getNumIterationsInRange()
13435 SmallVector<const SCEV *, 3> Ops; in getPostIncExpr()
13444 const SCEV *Last = getOperand(getNumOperands() - 1); in getPostIncExpr()
13448 SCEV::FlagAnyWrap)); in getPostIncExpr()
13452 bool ScalarEvolution::containsUndefs(const SCEV *S) const { in containsUndefs()
13453 return SCEVExprContains(S, [](const SCEV *S) { in containsUndefs()
13461 bool ScalarEvolution::containsErasedValue(const SCEV *S) const { in containsErasedValue()
13462 return SCEVExprContains(S, [](const SCEV *S) { in containsErasedValue()
13470 const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { in getElementSize()
13593 static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV* S) { in PrintSCEVWithTypeHint()
13760 const SCEV *SV = SE.getSCEV(&I); in print()
13771 const SCEV *AtUse = SE.getSCEVAtScope(SV, L); in print()
13785 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); in print()
13834 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { in getLoopDisposition()
13853 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { in computeLoopDisposition()
13924 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { in isLoopInvariant()
13928 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { in hasComputableLoopEvolution()
13933 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { in getBlockDisposition()
13952 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { in computeBlockDisposition()
13982 for (const SCEV *NAryOp : S->operands()) { in computeBlockDisposition()
14007 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) { in dominates()
14011 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { in properlyDominates()
14015 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { in hasOperand()
14016 return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; }); in hasOperand()
14026 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) { in forgetBackedgeTakenCounts()
14038 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) { in forgetMemoizedResults()
14039 SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end()); in forgetMemoizedResults()
14040 SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end()); in forgetMemoizedResults()
14043 const SCEV *Curr = Worklist.pop_back_val(); in forgetMemoizedResults()
14056 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetMemoizedResults()
14064 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) { in forgetMemoizedResultsImpl()
14120 ScalarEvolution::getUsedLoops(const SCEV *S, in getUsedLoops()
14126 bool follow(const SCEV *S) { in getUsedLoops()
14158 const SCEV *L = getSCEV(Cmp->getOperand(0)); in getReachableBlocks()
14159 const SCEV *R = getSCEV(Cmp->getOperand(1)); in getReachableBlocks()
14186 const SCEV *visitConstant(const SCEVConstant *Constant) { in verify()
14190 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in verify()
14194 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { in verify()
14203 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * { in verify()
14214 const SCEV *Delta = SE2.getMinusSCEV(Old, New); in verify()
14257 const SCEV *Delta = GetDelta(CurBECount, NewBECount); in verify()
14295 const SCEV *OldSCEV = SCM.visit(KV.second); in verify()
14296 const SCEV *NewSCEV = SE2.getSCEV(I); in verify()
14297 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV); in verify()
14341 const SCEV *Value = ValueAndVec.first; in verify()
14344 const SCEV *ValueAtScope = LoopAndValueAtScope.second; in verify()
14358 const SCEV *ValueAtScope = ValueAtScopeAndVec.first; in verify()
14361 const SCEV *Value = LoopAndValue.second; in verify()
14379 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) { in verify()
14554 const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS, in getEqualPredicate()
14555 const SCEV *RHS) { in getEqualPredicate()
14561 const SCEV *LHS, const SCEV *RHS) { in getComparePredicate()
14609 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
14616 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
14633 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in visitZeroExtendExpr()
14634 const SCEV *Operand = visit(Expr->getOperand()); in visitZeroExtendExpr()
14639 const SCEV *Step = AR->getStepRecurrence(SE); in visitZeroExtendExpr()
14649 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { in visitSignExtendExpr()
14650 const SCEV *Operand = visit(Expr->getOperand()); in visitSignExtendExpr()
14655 const SCEV *Step = AR->getStepRecurrence(SE); in visitSignExtendExpr()
14692 const SCEV *convertToAddRecWithPreds(const SCEVUnknown *Expr) { in convertToAddRecWithPreds()
14696 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in convertToAddRecWithPreds()
14719 const SCEV *
14720 ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L, in rewriteUsingPredicate()
14726 const SCEV *S, const Loop *L, in convertSCEVToAddRecWithPredicates()
14750 const SCEV *LHS, const SCEV *RHS) in SCEVComparePredicate()
14793 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags(); in isAlwaysTrue()
14796 if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags) in isAlwaysTrue()
14815 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags(); in getImpliedFlags()
14818 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags) in getImpliedFlags()
14821 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) { in getImpliedFlags()
14877 void ScalarEvolution::registerUser(const SCEV *User, in registerUser()
14878 ArrayRef<const SCEV *> Ops) { in registerUser()
14887 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) { in getSCEV()
14888 const SCEV *Expr = SE.getSCEV(V); in getSCEV()
14900 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds); in getSCEV()
14906 const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() { in getBackedgeTakenCount()
14916 const SCEV *PredicatedScalarEvolution::getSymbolicMaxBackedgeTakenCount() { in getSymbolicMaxBackedgeTakenCount()
14946 const SCEV *Rewritten = II.second.second; in updateGeneration()
14954 const SCEV *Expr = getSCEV(V); in setNoOverflow()
14970 const SCEV *Expr = getSCEV(V); in hasNoOverflow()
14985 const SCEV *Expr = this->getSCEV(V); in getAsAddRec()
15036 bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS, in matchURem()
15037 const SCEV *&RHS) { in matchURem()
15062 const SCEV *A = Add->getOperand(1); in matchURem()
15068 const auto MatchURemWithDivisor = [&](const SCEV *B) { in matchURem()
15095 SmallVector<const SCEV *> ExprsToRewrite; in collect()
15096 auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS, in collect()
15097 const SCEV *RHS, in collect()
15098 DenseMap<const SCEV *, const SCEV *> in collect()
15134 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown; in collect()
15149 [&](const SCEV *Expr, SCEVTypes &SCTy, const SCEV *&LHS, in collect()
15150 const SCEV *&RHS) { in collect()
15168 auto GetNonNegExprAndPosDivisor = [&](const SCEV *Expr, const SCEV *Divisor, in collect()
15182 auto GetNextSCEVDividesByDivisor = [&](const SCEV *Expr, in collect()
15183 const SCEV *Divisor) { in collect()
15198 auto GetPreviousSCEVDividesByDivisor = [&](const SCEV *Expr, in collect()
15199 const SCEV *Divisor) { in collect()
15212 std::function<const SCEV *(const SCEV *, const SCEV *)> in collect()
15213 ApplyDivisibiltyOnMinMaxExpr = [&](const SCEV *MinMaxExpr, in collect()
15214 const SCEV *Divisor) { in collect()
15215 const SCEV *MinMaxLHS = nullptr, *MinMaxRHS = nullptr; in collect()
15227 SmallVector<const SCEV *> Ops = { in collect()
15239 const SCEV *URemLHS = nullptr; in collect()
15240 const SCEV *URemRHS = nullptr; in collect()
15244 const SCEV *RewrittenLHS = in collect()
15270 auto AddRewrite = [&](const SCEV *From, const SCEV *FromRewritten, in collect()
15271 const SCEV *To) { in collect()
15280 auto GetMaybeRewritten = [&](const SCEV *S) { in collect()
15292 std::function<bool(const SCEV *, const SCEV *&)> HasDivisibiltyInfo = in collect()
15293 [&](const SCEV *Expr, const SCEV *&DividesBy) { in collect()
15314 std::function<bool(const SCEV *, const SCEV *&)> IsKnownToDivideBy = in collect()
15315 [&](const SCEV *Expr, const SCEV *DividesBy) { in collect()
15324 const SCEV *RewrittenLHS = GetMaybeRewritten(LHS); in collect()
15325 const SCEV *DividesBy = nullptr; in collect()
15342 const SCEV *One = SE.getOne(RHS->getType()); in collect()
15371 SmallVector<const SCEV *, 16> Worklist(1, LHS); in collect()
15372 SmallPtrSet<const SCEV *, 16> Visited; in collect()
15379 const SCEV *From = Worklist.pop_back_val(); in collect()
15384 const SCEV *FromRewritten = GetMaybeRewritten(From); in collect()
15385 const SCEV *To = nullptr; in collect()
15419 const SCEV *OneAlignedUp = in collect()
15510 for (const SCEV *Expr : ExprsToRewrite) { in collect()
15511 const SCEV *RewriteTo = Guards.RewriteMap[Expr]; in collect()
15522 for (const SCEV *Expr : ExprsToRewrite) { in collect()
15523 const SCEV *RewriteTo = Guards.RewriteMap[Expr]; in collect()
15531 const SCEV *ScalarEvolution::LoopGuards::rewrite(const SCEV *Expr) const { in rewrite()
15537 const DenseMap<const SCEV *, const SCEV *> ⤅ in rewrite()
15539 SCEV::NoWrapFlags FlagMask = SCEV::FlagAnyWrap; in rewrite()
15546 FlagMask = ScalarEvolution::setFlags(FlagMask, SCEV::FlagNUW); in rewrite()
15548 FlagMask = ScalarEvolution::setFlags(FlagMask, SCEV::FlagNSW); in rewrite()
15551 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { return Expr; } in rewrite()
15553 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in rewrite()
15560 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in rewrite()
15566 const SCEV *Op = Expr->getOperand(0); in rewrite()
15584 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { in rewrite()
15592 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) { in rewrite()
15599 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) { in rewrite()
15606 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { in rewrite()
15607 SmallVector<const SCEV *, 2> Operands; in rewrite()
15622 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { in rewrite()
15623 SmallVector<const SCEV *, 2> Operands; in rewrite()
15646 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) { in applyLoopGuards()
15650 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, in applyLoopGuards()