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()
513 const SCEV *op, Type *ty) in SCEVCastExpr()
514 : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {} in SCEVCastExpr()
516 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op, in SCEVPtrToIntExpr()
524 SCEVTypes SCEVTy, const SCEV *op, in SCEVIntegralCastExpr()
528 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, in SCEVTruncateExpr()
536 const SCEV *op, Type *ty) in SCEVZeroExtendExpr()
543 const SCEV *op, Type *ty) in SCEVSignExtendExpr()
674 CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV, in CompareSCEVComplexity()
676 const LoopInfo *const LI, const SCEV *LHS, in CompareSCEVComplexity()
677 const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) { in CompareSCEVComplexity()
760 ArrayRef<const SCEV *> LOps = LHS->operands(); in CompareSCEVComplexity()
761 ArrayRef<const SCEV *> ROps = RHS->operands(); in CompareSCEVComplexity()
793 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, in GroupByComplexity()
797 EquivalenceClasses<const SCEV *> EqCacheSCEV; in GroupByComplexity()
801 auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
809 const SCEV *&LHS = Ops[0], *&RHS = Ops[1]; in GroupByComplexity()
816 llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) { in GroupByComplexity()
825 const SCEV *S = Ops[i]; in GroupByComplexity()
843 static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { in hasHugeExpression()
844 return any_of(Ops, [](const SCEV *S) { in hasHugeExpression()
854 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, in BinomialCoefficient()
948 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); in BinomialCoefficient()
950 const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i)); in BinomialCoefficient()
956 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); in BinomialCoefficient()
972 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, in evaluateAtIteration()
977 const SCEV *
978 SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands, in evaluateAtIteration()
979 const SCEV *It, ScalarEvolution &SE) { in evaluateAtIteration()
981 const SCEV *Result = Operands[0]; in evaluateAtIteration()
986 const SCEV *Coeff = BinomialCoefficient(It, i, SE, Result->getType()); in evaluateAtIteration()
999 const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op, in getLosslessPtrToIntExpr()
1017 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getLosslessPtrToIntExpr()
1047 SCEV *S = new (SCEVAllocator) in getLosslessPtrToIntExpr()
1074 static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE) { in getLosslessPtrToIntExpr()
1079 const SCEV *visit(const SCEV *S) { in getLosslessPtrToIntExpr()
1088 const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { in getLosslessPtrToIntExpr()
1089 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1098 const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { in getLosslessPtrToIntExpr()
1099 SmallVector<const SCEV *, 2> Operands; in getLosslessPtrToIntExpr()
1108 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in getLosslessPtrToIntExpr()
1116 const SCEV *IntOp = SCEVPtrToIntSinkingRewriter::rewrite(Op, *this); in getLosslessPtrToIntExpr()
1123 const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) { in getPtrToIntExpr()
1126 const SCEV *IntOp = getLosslessPtrToIntExpr(Op); in getPtrToIntExpr()
1133 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty, in getTruncateExpr()
1147 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getTruncateExpr()
1167 SCEV *S = in getTruncateExpr()
1180 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1184 const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1); in getTruncateExpr()
1200 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getTruncateExpr()
1206 SmallVector<const SCEV *, 4> Operands; in getTruncateExpr()
1207 for (const SCEV *Op : AddRec->operands()) in getTruncateExpr()
1209 return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); in getTruncateExpr()
1220 SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), in getTruncateExpr()
1230 static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step, in getSignedOverflowLimitForStep()
1250 static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step, in getUnsignedOverflowLimitForStep()
1263 typedef const SCEV *(ScalarEvolution::*GetExtendExprTy)(const SCEV *, Type *,
1282 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNSW;
1286 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1298 static const SCEV::NoWrapFlags WrapType = SCEV::FlagNUW;
1302 static const SCEV *getOverflowLimitForStep(const SCEV *Step, in getOverflowLimitForStep()
1322 static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty, in getPreStartForExtend()
1328 const SCEV *Start = AR->getStart(); in getPreStartForExtend()
1329 const SCEV *Step = AR->getStepRecurrence(*SE); in getPreStartForExtend()
1340 SmallVector<const SCEV *, 4> DiffOps(SA->operands()); in getPreStartForExtend()
1355 ScalarEvolution::maskFlags(SA->getNoWrapFlags(), SCEV::FlagNUW); in getPreStartForExtend()
1356 const SCEV *PreStart = SE->getAddExpr(DiffOps, PreStartFlags); in getPreStartForExtend()
1358 SE->getAddRecExpr(PreStart, Step, L, SCEV::FlagAnyWrap)); in getPreStartForExtend()
1364 const SCEV *BECount = SE->getBackedgeTakenCount(L); in getPreStartForExtend()
1372 const SCEV *OperandExtendedStart = in getPreStartForExtend()
1387 const SCEV *OverflowLimit = in getPreStartForExtend()
1399 static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty, in getExtendAddRecStart()
1404 const SCEV *PreStart = getPreStartForExtend<ExtendOpTy>(AR, Ty, SE, Depth); in getExtendAddRecStart()
1446 bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start, in proveNoWrapByVaryingStart()
1447 const SCEV *Step, in proveNoWrapByVaryingStart()
1462 const SCEV *PreStart = getConstant(StartAI - Delta); in proveNoWrapByVaryingStart()
1476 const SCEV *DeltaS = getConstant(StartC->getType(), Delta); in proveNoWrapByVaryingStart()
1478 const SCEV *Limit = ExtendOpTraits<ExtendOpTy>::getOverflowLimitForStep( in proveNoWrapByVaryingStart()
1516 const SCEV *Step) { in extractConstantWithoutWrapping()
1526 const ScalarEvolution::FoldID &ID, const SCEV *S, in insertFoldCacheEntry()
1527 DenseMap<ScalarEvolution::FoldID, const SCEV *> &FoldCache, in insertFoldCacheEntry()
1528 DenseMap<const SCEV *, SmallVector<ScalarEvolution::FoldID, 2>> in insertFoldCacheEntry() argument
1548 const SCEV *
1549 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getZeroExtendExpr()
1562 const SCEV *S = getZeroExtendExprImpl(Op, Ty, Depth); in getZeroExtendExpr()
1568 const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty, in getZeroExtendExprImpl()
1590 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExprImpl()
1592 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExprImpl()
1603 const SCEV *X = ST->getOperand(); in getZeroExtendExprImpl()
1618 const SCEV *Start = AR->getStart(); in getZeroExtendExprImpl()
1619 const SCEV *Step = AR->getStepRecurrence(*this); in getZeroExtendExprImpl()
1640 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getZeroExtendExprImpl()
1646 const SCEV *CastedMaxBECount = in getZeroExtendExprImpl()
1648 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getZeroExtendExprImpl()
1653 const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step, in getZeroExtendExprImpl()
1654 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1655 const SCEV *ZAdd = getZeroExtendExpr(getAddExpr(Start, ZMul, in getZeroExtendExprImpl()
1656 SCEV::FlagAnyWrap, in getZeroExtendExprImpl()
1659 const SCEV *WideStart = getZeroExtendExpr(Start, WideTy, Depth + 1); in getZeroExtendExprImpl()
1660 const SCEV *WideMaxBECount = in getZeroExtendExprImpl()
1662 const SCEV *OperandExtendedAdd = in getZeroExtendExprImpl()
1666 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExprImpl()
1667 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1670 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExprImpl()
1683 SCEV::FlagAnyWrap, Depth + 1), in getZeroExtendExprImpl()
1684 SCEV::FlagAnyWrap, Depth + 1); in getZeroExtendExprImpl()
1688 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExprImpl()
1724 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - in getZeroExtendExprImpl()
1731 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getZeroExtendExprImpl()
1748 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExprImpl()
1749 const SCEV *SResidual = in getZeroExtendExprImpl()
1751 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExprImpl()
1753 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExprImpl()
1759 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNUW); in getZeroExtendExprImpl()
1769 const SCEV *LHS; in getZeroExtendExprImpl()
1770 const SCEV *RHS; in getZeroExtendExprImpl()
1786 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExprImpl()
1789 return getAddExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1803 const SCEV *SZExtD = getZeroExtendExpr(getConstant(D), Ty, Depth); in getZeroExtendExprImpl()
1804 const SCEV *SResidual = in getZeroExtendExprImpl()
1805 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getZeroExtendExprImpl()
1806 const SCEV *SZExtR = getZeroExtendExpr(SResidual, Ty, Depth + 1); in getZeroExtendExprImpl()
1808 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getZeroExtendExprImpl()
1819 SmallVector<const SCEV *, 4> Ops; in getZeroExtendExprImpl()
1822 return getMulExpr(Ops, SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1848 SCEV::FlagNUW, Depth + 1); in getZeroExtendExprImpl()
1856 SmallVector<const SCEV *, 4> Operands; in getZeroExtendExprImpl()
1867 SmallVector<const SCEV *, 4> Operands; in getZeroExtendExprImpl()
1875 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getZeroExtendExprImpl()
1876 SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), in getZeroExtendExprImpl()
1883 const SCEV *
1884 ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { in getSignExtendExpr()
1897 const SCEV *S = getSignExtendExprImpl(Op, Ty, Depth); in getSignExtendExpr()
1903 const SCEV *ScalarEvolution::getSignExtendExprImpl(const SCEV *Op, Type *Ty, in getSignExtendExprImpl()
1930 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExprImpl()
1933 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExprImpl()
1944 const SCEV *X = ST->getOperand(); in getSignExtendExprImpl()
1958 SmallVector<const SCEV *, 4> Ops; in getSignExtendExprImpl()
1961 return getAddExpr(Ops, SCEV::FlagNSW, Depth + 1); in getSignExtendExprImpl()
1976 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExprImpl()
1977 const SCEV *SResidual = in getSignExtendExprImpl()
1978 getAddExpr(getConstant(-D), SA, SCEV::FlagAnyWrap, Depth); in getSignExtendExprImpl()
1979 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExprImpl()
1981 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExprImpl()
1992 const SCEV *Start = AR->getStart(); in getSignExtendExprImpl()
1993 const SCEV *Step = AR->getStepRecurrence(*this); in getSignExtendExprImpl()
2003 return getAddRecExpr(Start, Step, L, SCEV::FlagNSW); in getSignExtendExprImpl()
2014 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in getSignExtendExprImpl()
2021 const SCEV *CastedMaxBECount = in getSignExtendExprImpl()
2023 const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( in getSignExtendExprImpl()
2028 const SCEV *SMul = getMulExpr(CastedMaxBECount, Step, in getSignExtendExprImpl()
2029 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2030 const SCEV *SAdd = getSignExtendExpr(getAddExpr(Start, SMul, in getSignExtendExprImpl()
2031 SCEV::FlagAnyWrap, in getSignExtendExprImpl()
2034 const SCEV *WideStart = getSignExtendExpr(Start, WideTy, Depth + 1); in getSignExtendExprImpl()
2035 const SCEV *WideMaxBECount = in getSignExtendExprImpl()
2037 const SCEV *OperandExtendedAdd = in getSignExtendExprImpl()
2041 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExprImpl()
2042 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2045 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExprImpl()
2058 SCEV::FlagAnyWrap, Depth + 1), in getSignExtendExprImpl()
2059 SCEV::FlagAnyWrap, Depth + 1); in getSignExtendExprImpl()
2069 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNW); in getSignExtendExprImpl()
2100 const SCEV *SSExtD = getSignExtendExpr(getConstant(D), Ty, Depth); in getSignExtendExprImpl()
2101 const SCEV *SResidual = in getSignExtendExprImpl()
2103 const SCEV *SSExtR = getSignExtendExpr(SResidual, Ty, Depth + 1); in getSignExtendExprImpl()
2105 (SCEV::NoWrapFlags)(SCEV::FlagNSW | SCEV::FlagNUW), in getSignExtendExprImpl()
2111 setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), SCEV::FlagNSW); in getSignExtendExprImpl()
2128 SmallVector<const SCEV *, 4> Operands; in getSignExtendExprImpl()
2138 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getSignExtendExprImpl()
2139 SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), in getSignExtendExprImpl()
2146 const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op, in getCastExpr()
2164 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, in getAnyExtendExpr()
2179 const SCEV *NewOp = T->getOperand(); in getAnyExtendExpr()
2186 const SCEV *ZExt = getZeroExtendExpr(Op, Ty); in getAnyExtendExpr()
2191 const SCEV *SExt = getSignExtendExpr(Op, Ty); in getAnyExtendExpr()
2197 SmallVector<const SCEV *, 4> Ops; in getAnyExtendExpr()
2198 for (const SCEV *Op : AR->operands()) in getAnyExtendExpr()
2200 return getAddRecExpr(Ops, AR->getLoop(), SCEV::FlagNW); in getAnyExtendExpr()
2235 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, in CollectAddOperandsWithScales() argument
2236 SmallVectorImpl<const SCEV *> &NewOps, in CollectAddOperandsWithScales()
2238 ArrayRef<const SCEV *> Ops, const APInt &Scale, in CollectAddOperandsWithScales()
2268 SmallVector<const SCEV *, 4> MulOps(drop_begin(Mul->operands())); in CollectAddOperandsWithScales()
2269 const SCEV *Key = SE.getMulExpr(MulOps); in CollectAddOperandsWithScales()
2282 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = in CollectAddOperandsWithScales()
2299 const SCEV *LHS, const SCEV *RHS, in willNotOverflow()
2301 const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *, in willNotOverflow()
2302 SCEV::NoWrapFlags, unsigned); in willNotOverflow()
2317 const SCEV *(ScalarEvolution::*Extension)(const SCEV *, Type *, unsigned) = in willNotOverflow()
2326 const SCEV *A = (this->*Extension)( in willNotOverflow()
2327 (this->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0), WideTy, 0); in willNotOverflow()
2328 const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0); in willNotOverflow()
2329 const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0); in willNotOverflow()
2330 const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0); in willNotOverflow()
2374 std::optional<SCEV::NoWrapFlags>
2381 SCEV::NoWrapFlags Flags = SCEV::NoWrapFlags::FlagAnyWrap; in getStrengthenedNoWrapFlagsFromBinOp()
2384 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2386 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2395 const SCEV *LHS = getSCEV(OBO->getOperand(0)); in getStrengthenedNoWrapFlagsFromBinOp()
2396 const SCEV *RHS = getSCEV(OBO->getOperand(1)); in getStrengthenedNoWrapFlagsFromBinOp()
2403 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getStrengthenedNoWrapFlagsFromBinOp()
2410 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getStrengthenedNoWrapFlagsFromBinOp()
2422 static SCEV::NoWrapFlags
2424 const ArrayRef<const SCEV *> Ops, in StrengthenNoWrapFlags()
2425 SCEV::NoWrapFlags Flags) { in StrengthenNoWrapFlags()
2435 int SignOrUnsignMask = SCEV::FlagNUW | SCEV::FlagNSW; in StrengthenNoWrapFlags()
2436 SCEV::NoWrapFlags SignOrUnsignWrap = in StrengthenNoWrapFlags()
2440 auto IsKnownNonNegative = [&](const SCEV *S) { in StrengthenNoWrapFlags()
2444 if (SignOrUnsignWrap == SCEV::FlagNSW && all_of(Ops, IsKnownNonNegative)) in StrengthenNoWrapFlags()
2446 ScalarEvolution::setFlags(Flags, (SCEV::NoWrapFlags)SignOrUnsignMask); in StrengthenNoWrapFlags()
2468 if (!(SignOrUnsignWrap & SCEV::FlagNSW)) { in StrengthenNoWrapFlags()
2472 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in StrengthenNoWrapFlags()
2476 if (!(SignOrUnsignWrap & SCEV::FlagNUW)) { in StrengthenNoWrapFlags()
2480 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2486 if (Type == scAddRecExpr && ScalarEvolution::hasFlags(Flags, SCEV::FlagNW) && in StrengthenNoWrapFlags()
2487 !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && Ops.size() == 2 && in StrengthenNoWrapFlags()
2489 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2492 if (Type == scMulExpr && !ScalarEvolution::hasFlags(Flags, SCEV::FlagNUW) && in StrengthenNoWrapFlags()
2496 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2499 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in StrengthenNoWrapFlags()
2505 bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) { in isAvailableAtLoopEntry()
2510 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, in getAddExpr()
2511 SCEV::NoWrapFlags OrigFlags, in getAddExpr()
2513 assert(!(OrigFlags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && in getAddExpr()
2523 Ops, [](const SCEV *Op) { return Op->getType()->isPointerTy(); }); in getAddExpr()
2553 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getAddExpr()
2561 if (SCEV *S = findExistingSCEVInCache(scAddExpr, Ops)) { in getAddExpr()
2581 const SCEV *Scale = getConstant(Ty, Count); in getAddExpr()
2582 const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2612 SmallVector<const SCEV *, 8> LargeOps; in getAddExpr()
2626 SmallVector<const SCEV *, 8> LargeMulOps; in getAddExpr()
2643 LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2651 const SCEV *Fold = getAddExpr(LargeOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2662 const SCEV *A = Ops[0]; in getAddExpr()
2663 const SCEV *B = Ops[1]; in getAddExpr()
2669 SCEV::NoWrapFlags PreservedFlags = SCEV::FlagAnyWrap; in getAddExpr()
2674 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNUW) && in getAddExpr()
2677 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNUW); in getAddExpr()
2682 if (ScalarEvolution::hasFlags(AddFlags, SCEV::FlagNSW) && in getAddExpr()
2686 ScalarEvolution::setFlags(PreservedFlags, SCEV::FlagNSW); in getAddExpr()
2689 if (PreservedFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2690 SmallVector<const SCEV *, 4> NewOps(AddExpr->operands()); in getAddExpr()
2702 const SCEV *X; in getAddExpr()
2703 const SCEV *Y; in getAddExpr()
2720 SCEV::NoWrapFlags CommonFlags = maskFlags(OrigFlags, SCEV::FlagNUW); in getAddExpr()
2748 DenseMap<const SCEV *, APInt> M; in getAddExpr()
2749 SmallVector<const SCEV *, 8> NewOps; in getAddExpr()
2762 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists; in getAddExpr()
2763 for (const SCEV *NewOp : NewOps) in getAddExpr()
2771 Ops.push_back(getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2775 getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1), in getAddExpr()
2776 SCEV::FlagAnyWrap, Depth + 1)); in getAddExpr()
2783 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2793 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); in getAddExpr()
2799 const SCEV *InnerMul = Mul->getOperand(MulOp == 0); in getAddExpr()
2803 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2806 InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2808 SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul}; in getAddExpr()
2809 const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2810 const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV, in getAddExpr()
2811 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2821 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2835 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); in getAddExpr()
2837 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2840 InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2842 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); in getAddExpr()
2844 SmallVector<const SCEV *, 4> MulOps( in getAddExpr()
2847 InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2849 SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2}; in getAddExpr()
2850 const SCEV *InnerMulSum = in getAddExpr()
2851 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2852 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum, in getAddExpr()
2853 SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2858 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2874 SmallVector<const SCEV *, 8> LIOps; in getAddExpr()
2890 SCEV::NoWrapFlags Flags = ComputeFlags(LIOps); in getAddExpr()
2896 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2908 SCEV::NoWrapFlags AddFlags = Flags; in getAddExpr()
2909 if (AddFlags != SCEV::FlagAnyWrap) { in getAddExpr()
2913 AddFlags = SCEV::FlagAnyWrap; in getAddExpr()
2920 Flags = AddRec->getNoWrapFlags(setFlags(Flags, SCEV::FlagNW)); in getAddExpr()
2921 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, Flags); in getAddExpr()
2932 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2949 SmallVector<const SCEV *, 4> AddRecOps(AddRec->operands()); in getAddExpr()
2960 SmallVector<const SCEV *, 2> TwoOps = { in getAddExpr()
2962 AddRecOps[i] = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2968 Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); in getAddExpr()
2969 return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getAddExpr()
2982 const SCEV *
2983 ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddExpr()
2984 SCEV::NoWrapFlags Flags) { in getOrCreateAddExpr()
2987 for (const SCEV *Op : Ops) in getOrCreateAddExpr()
2993 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddExpr()
3004 const SCEV *
3005 ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, in getOrCreateAddRecExpr()
3006 const Loop *L, SCEV::NoWrapFlags Flags) { in getOrCreateAddRecExpr()
3009 for (const SCEV *Op : Ops) in getOrCreateAddRecExpr()
3016 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateAddRecExpr()
3028 const SCEV *
3029 ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, in getOrCreateMulExpr()
3030 SCEV::NoWrapFlags Flags) { in getOrCreateMulExpr()
3033 for (const SCEV *Op : Ops) in getOrCreateMulExpr()
3039 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getOrCreateMulExpr()
3084 static bool containsConstantInAddMulChain(const SCEV *StartExpr) { in containsConstantInAddMulChain()
3088 bool follow(const SCEV *S) { in containsConstantInAddMulChain()
3105 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, in getMulExpr()
3106 SCEV::NoWrapFlags OrigFlags, in getMulExpr()
3108 assert(OrigFlags == maskFlags(OrigFlags, SCEV::FlagNUW | SCEV::FlagNSW) && in getMulExpr()
3151 auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) { in getMulExpr()
3159 if (SCEV *S = findExistingSCEVInCache(scMulExpr, Ops)) { in getMulExpr()
3178 const SCEV *LHS = getMulExpr(LHSC, Add->getOperand(0), in getMulExpr()
3179 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3180 const SCEV *RHS = getMulExpr(LHSC, Add->getOperand(1), in getMulExpr()
3181 SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3182 return getAddExpr(LHS, RHS, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3189 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3191 for (const SCEV *AddOp : Add->operands()) { in getMulExpr()
3192 const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap, in getMulExpr()
3198 return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3201 SmallVector<const SCEV *, 4> Operands; in getMulExpr()
3202 for (const SCEV *AddRecOp : AddRec->operands()) in getMulExpr()
3203 Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap, in getMulExpr()
3210 auto FlagsMask = SCEV::FlagNW; in getMulExpr()
3211 if (hasFlags(AddRec->getNoWrapFlags(), SCEV::FlagNSW)) { in getMulExpr()
3215 FlagsMask = setFlags(FlagsMask, SCEV::FlagNSW); in getMulExpr()
3245 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3258 SmallVector<const SCEV *, 8> LIOps; in getMulExpr()
3270 SmallVector<const SCEV *, 4> NewOps; in getMulExpr()
3272 const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3278 SCEV::NoWrapFlags Flags = in getMulExpr()
3283 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3285 if (hasFlags(Flags, SCEV::FlagNSW) && !hasFlags(Flags, SCEV::FlagNUW)) { in getMulExpr()
3290 Flags = clearFlags(Flags, SCEV::FlagNSW); in getMulExpr()
3294 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), Flags); in getMulExpr()
3305 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3340 SmallVector<const SCEV*, 7> AddRecOps; in getMulExpr()
3343 SmallVector <const SCEV *, 7> SumOps; in getMulExpr()
3355 const SCEV *CoeffTerm = getConstant(Ty, Coeff); in getMulExpr()
3356 const SCEV *Term1 = AddRec->getOperand(y-z); in getMulExpr()
3357 const SCEV *Term2 = OtherAddRec->getOperand(z); in getMulExpr()
3359 SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3364 AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1)); in getMulExpr()
3367 const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(), in getMulExpr()
3368 SCEV::FlagAnyWrap); in getMulExpr()
3379 return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1); in getMulExpr()
3391 const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS, in getURemExpr()
3392 const SCEV *RHS) { in getURemExpr()
3413 const SCEV *UDiv = getUDivExpr(LHS, RHS); in getURemExpr()
3414 const SCEV *Mult = getMulExpr(UDiv, RHS, SCEV::FlagNUW); in getURemExpr()
3415 return getMinusSCEV(LHS, Mult, SCEV::FlagNUW); in getURemExpr()
3420 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, in getUDivExpr()
3421 const SCEV *RHS) { in getUDivExpr()
3432 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3469 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3470 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3471 for (const SCEV *Op : AR->operands()) in getUDivExpr()
3473 return getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3483 AR->getLoop(), SCEV::FlagAnyWrap)) { in getUDivExpr()
3487 const SCEV *NewLHS = in getUDivExpr()
3489 AR->getLoop(), SCEV::FlagNW); in getUDivExpr()
3500 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) in getUDivExpr()
3508 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3509 for (const SCEV *Op : M->operands()) in getUDivExpr()
3514 const SCEV *Op = M->getOperand(i); in getUDivExpr()
3515 const SCEV *Div = getUDivExpr(Op, RHSC); in getUDivExpr()
3517 Operands = SmallVector<const SCEV *, 4>(M->operands()); in getUDivExpr()
3540 SmallVector<const SCEV *, 4> Operands; in getUDivExpr()
3541 for (const SCEV *Op : A->operands()) in getUDivExpr()
3546 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); in getUDivExpr()
3566 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; in getUDivExpr()
3567 SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), in getUDivExpr()
3592 const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS, in getUDivExactExpr()
3593 const SCEV *RHS) { in getUDivExactExpr()
3607 SmallVector<const SCEV *, 2> Operands(drop_begin(Mul->operands())); in getUDivExactExpr()
3620 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3634 SmallVector<const SCEV *, 2> Operands; in getUDivExactExpr()
3646 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, in getAddRecExpr()
3648 SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3649 SmallVector<const SCEV *, 4> Operands; in getAddRecExpr()
3654 return getAddRecExpr(Operands, L, maskFlags(Flags, SCEV::FlagNW)); in getAddRecExpr()
3663 const SCEV *
3664 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, in getAddRecExpr()
3665 const Loop *L, SCEV::NoWrapFlags Flags) { in getAddRecExpr()
3681 return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X in getAddRecExpr()
3699 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->operands()); in getAddRecExpr()
3705 Operands, [&](const SCEV *Op) { return isLoopInvariant(Op, L); }); in getAddRecExpr()
3712 SCEV::NoWrapFlags OuterFlags = in getAddRecExpr()
3713 maskFlags(Flags, SCEV::FlagNW | NestedAR->getNoWrapFlags()); in getAddRecExpr()
3716 AllInvariant = all_of(NestedOperands, [&](const SCEV *Op) { in getAddRecExpr()
3725 SCEV::NoWrapFlags InnerFlags = in getAddRecExpr()
3726 maskFlags(NestedAR->getNoWrapFlags(), SCEV::FlagNW | Flags); in getAddRecExpr()
3740 const SCEV *
3742 const SmallVectorImpl<const SCEV *> &IndexExprs) { in getGEPExpr()
3743 const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); in getGEPExpr()
3760 SCEV::NoWrapFlags OffsetWrap = in getGEPExpr()
3761 AssumeInBoundsFlags ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getGEPExpr()
3765 SmallVector<const SCEV *, 4> Offsets; in getGEPExpr()
3766 for (const SCEV *IndexExpr : IndexExprs) { in getGEPExpr()
3772 const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); in getGEPExpr()
3788 const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); in getGEPExpr()
3793 const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, OffsetWrap); in getGEPExpr()
3803 const SCEV *Offset = getAddExpr(Offsets, OffsetWrap); in getGEPExpr()
3807 SCEV::NoWrapFlags BaseWrap = AssumeInBoundsFlags && isKnownNonNegative(Offset) in getGEPExpr()
3808 ? SCEV::FlagNUW : SCEV::FlagAnyWrap; in getGEPExpr()
3815 SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType, in findExistingSCEVInCache()
3816 ArrayRef<const SCEV *> Ops) { in findExistingSCEVInCache()
3819 for (const SCEV *Op : Ops) in findExistingSCEVInCache()
3825 const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) { in getAbsExpr()
3826 SCEV::NoWrapFlags Flags = IsNSW ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getAbsExpr()
3830 const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind, in getMinMaxExpr()
3831 SmallVectorImpl<const SCEV *> &Ops) { in getMinMaxExpr()
3853 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) { in getMinMaxExpr()
3959 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getMinMaxExpr()
3962 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getMinMaxExpr()
3964 SCEV *S = new (SCEVAllocator) in getMinMaxExpr()
3976 std::optional<const SCEV *>> {
3977 using RetVal = std::optional<const SCEV *>;
3983 SmallPtrSet<const SCEV *, 16> SeenOps;
3991 RetVal visitAnyMinMaxExpr(const SCEV *S) { in visitAnyMinMaxExpr()
4000 SmallVector<const SCEV *> NewOps; in visitAnyMinMaxExpr()
4013 RetVal visit(const SCEV *S) { in visit()
4028 bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps, in visit()
4029 SmallVectorImpl<const SCEV *> &NewOps) { in visit()
4031 SmallVector<const SCEV *> Ops; in visit()
4034 for (const SCEV *Op : OrigOps) { in visit()
4137 bool follow(const SCEV *S) { in follow()
4153 static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) { in impliesPoison()
4180 SmallPtrSetImpl<const Value *> &Result, const SCEV *S) { in getPoisonGeneratingValues()
4188 const SCEV *S, Instruction *I, in canReuseInstruction()
4249 const SCEV *
4251 SmallVectorImpl<const SCEV *> &Ops) { in getSequentialMinMaxExpr()
4272 if (const SCEV *S = findExistingSCEVInCache(Kind, Ops)) in getSequentialMinMaxExpr()
4306 const SCEV *SaturationPoint; in getSequentialMinMaxExpr()
4324 SmallVector<const SCEV *> SeqOps = {Ops[i - 1], Ops[i]}; in getSequentialMinMaxExpr()
4346 const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP); in getSequentialMinMaxExpr()
4350 const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); in getSequentialMinMaxExpr()
4352 SCEV *S = new (SCEVAllocator) in getSequentialMinMaxExpr()
4360 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getSMaxExpr()
4361 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getSMaxExpr()
4365 const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMaxExpr()
4369 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) { in getUMaxExpr()
4370 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; in getUMaxExpr()
4374 const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { in getUMaxExpr()
4378 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, in getSMinExpr()
4379 const SCEV *RHS) { in getSMinExpr()
4380 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getSMinExpr()
4384 const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) { in getSMinExpr()
4388 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS, in getUMinExpr()
4390 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinExpr()
4394 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops, in getUMinExpr()
4400 const SCEV *
4402 const SCEV *Res = getConstant(IntTy, Size.getKnownMinValue()); in getSizeOfExpr()
4408 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) { in getSizeOfExpr()
4412 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) { in getStoreSizeOfExpr()
4416 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy, in getOffsetOfExpr()
4428 const SCEV *ScalarEvolution::getUnknown(Value *V) { in getUnknown()
4438 if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) { in getUnknown()
4443 SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V, this, in getUnknown()
4490 bool ScalarEvolution::instructionCouldExistWithOperands(const SCEV *A, in instructionCouldExistWithOperands()
4491 const SCEV *B) { in instructionCouldExistWithOperands()
4504 const SCEV *ScalarEvolution::getCouldNotCompute() { in getCouldNotCompute()
4508 bool ScalarEvolution::checkValidity(const SCEV *S) const { in checkValidity()
4509 bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) { in checkValidity()
4517 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { in containsAddRecurrence()
4523 SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); }); in containsAddRecurrence()
4530 ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) { in getSCEVValues()
4551 void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) { in insertValueToMap()
4564 const SCEV *ScalarEvolution::getSCEV(Value *V) { in getSCEV()
4567 if (const SCEV *S = getExistingSCEV(V)) in getSCEV()
4572 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { in getExistingSCEV()
4577 const SCEV *S = I->second; in getExistingSCEV()
4586 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, in getNegativeSCEV()
4587 SCEV::NoWrapFlags Flags) { in getNegativeSCEV()
4598 static const SCEV *MatchNotExpr(const SCEV *Expr) { in MatchNotExpr()
4613 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { in getNotSCEV()
4623 SmallVector<const SCEV *, 2> MatchedOperands; in getNotSCEV()
4624 for (const SCEV *Operand : MME->operands()) { in getNotSCEV()
4625 const SCEV *Matched = MatchNotExpr(Operand); in getNotSCEV()
4627 return (const SCEV *)nullptr; in getNotSCEV()
4633 if (const SCEV *Replaced = MatchMinMaxNegation(MME)) in getNotSCEV()
4642 const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) { in removePointerBase()
4647 SmallVector<const SCEV *> Ops{AddRec->operands()}; in removePointerBase()
4651 return getAddRecExpr(Ops, AddRec->getLoop(), SCEV::FlagAnyWrap); in removePointerBase()
4655 SmallVector<const SCEV *> Ops{Add->operands()}; in removePointerBase()
4656 const SCEV **PtrOp = nullptr; in removePointerBase()
4657 for (const SCEV *&AddOp : Ops) { in removePointerBase()
4672 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, in getMinusSCEV()
4673 SCEV::NoWrapFlags Flags, in getMinusSCEV()
4692 auto AddFlags = SCEV::FlagAnyWrap; in getMinusSCEV()
4695 if (hasFlags(Flags, SCEV::FlagNSW)) { in getMinusSCEV()
4706 AddFlags = SCEV::FlagNSW; in getMinusSCEV()
4717 auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap; in getMinusSCEV()
4722 const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty, in getTruncateOrZeroExtend()
4734 const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty, in getTruncateOrSignExtend()
4746 const SCEV *
4747 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { in getNoopOrZeroExtend()
4758 const SCEV *
4759 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { in getNoopOrSignExtend()
4770 const SCEV *
4771 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { in getNoopOrAnyExtend()
4782 const SCEV *
4783 ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { in getTruncateOrNoop()
4794 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, in getUMaxFromMismatchedTypes()
4795 const SCEV *RHS) { in getUMaxFromMismatchedTypes()
4796 const SCEV *PromotedLHS = LHS; in getUMaxFromMismatchedTypes()
4797 const SCEV *PromotedRHS = RHS; in getUMaxFromMismatchedTypes()
4807 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, in getUMinFromMismatchedTypes()
4808 const SCEV *RHS, in getUMinFromMismatchedTypes()
4810 SmallVector<const SCEV *, 2> Ops = { LHS, RHS }; in getUMinFromMismatchedTypes()
4814 const SCEV *
4815 ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops, in getUMinFromMismatchedTypes()
4832 SmallVector<const SCEV *, 2> PromotedOps; in getUMinFromMismatchedTypes()
4840 const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { in getPointerBase()
4849 const SCEV *PtrOp = nullptr; in getPointerBase()
4850 for (const SCEV *AddOp : Add->operands()) { in getPointerBase()
4884 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
4887 const SCEV *Result = Rewriter.visit(S); in rewrite()
4895 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4901 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4928 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE) { in rewrite()
4930 const SCEV *Result = Rewriter.visit(S); in rewrite()
4936 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4942 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
4969 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
4988 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
4989 const SCEV *Result = Expr; in visitUnknown()
4997 std::optional<const SCEV *> Res = in visitUnknown()
5006 std::optional<const SCEV *> Res = compareWithBackedgeCondition(I); in visitUnknown()
5022 std::optional<const SCEV *> compareWithBackedgeCondition(Value *IC);
5031 std::optional<const SCEV *>
5045 static const SCEV *rewrite(const SCEV *S, const Loop *L, in rewrite()
5048 const SCEV *Result = Rewriter.visit(S); in rewrite()
5052 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
5059 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { in visitAddRecExpr()
5078 SCEV::NoWrapFlags
5081 return SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
5085 SCEV::NoWrapFlags Result = SCEV::FlagAnyWrap; in proveNoWrapViaConstantRanges()
5088 const SCEV *BECount = getConstantMaxBackedgeTakenCount(AR->getLoop()); in proveNoWrapViaConstantRanges()
5095 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNW); in proveNoWrapViaConstantRanges()
5106 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNSW); in proveNoWrapViaConstantRanges()
5116 Result = ScalarEvolution::setFlags(Result, SCEV::FlagNUW); in proveNoWrapViaConstantRanges()
5122 SCEV::NoWrapFlags
5124 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoSignedWrapViaInduction()
5136 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoSignedWrapViaInduction()
5147 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoSignedWrapViaInduction()
5166 const SCEV *OverflowLimit = in proveNoSignedWrapViaInduction()
5171 Result = setFlags(Result, SCEV::FlagNSW); in proveNoSignedWrapViaInduction()
5175 SCEV::NoWrapFlags
5177 SCEV::NoWrapFlags Result = AR->getNoWrapFlags(); in proveNoUnsignedWrapViaInduction()
5189 const SCEV *Step = AR->getStepRecurrence(*this); in proveNoUnsignedWrapViaInduction()
5201 const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); in proveNoUnsignedWrapViaInduction()
5220 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - in proveNoUnsignedWrapViaInduction()
5224 Result = setFlags(Result, SCEV::FlagNUW); in proveNoUnsignedWrapViaInduction()
5370 static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI, in isSimpleCastedPHI()
5399 const SCEV *X = Trunc->getOperand(); in isSimpleCastedPHI()
5468 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5502 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHIWithCastsImpl()
5528 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHIWithCastsImpl()
5532 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHIWithCastsImpl()
5590 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHIWithCastsImpl()
5591 const SCEV *PHISCEV = in createAddRecFromPHIWithCastsImpl()
5593 getTruncateExpr(Accum, TruncTy), L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5618 auto getExtendedExpr = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5619 bool CreateSignExtend) -> const SCEV * { in createAddRecFromPHIWithCastsImpl()
5621 const SCEV *TruncatedExpr = getTruncateExpr(Expr, TruncTy); in createAddRecFromPHIWithCastsImpl()
5622 const SCEV *ExtendedExpr = in createAddRecFromPHIWithCastsImpl()
5633 auto PredIsKnownFalse = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5634 const SCEV *ExtendedExpr) -> bool { in createAddRecFromPHIWithCastsImpl()
5639 const SCEV *StartExtended = getExtendedExpr(StartVal, Signed); in createAddRecFromPHIWithCastsImpl()
5647 const SCEV *AccumExtended = getExtendedExpr(Accum, /*CreateSignExtend=*/true); in createAddRecFromPHIWithCastsImpl()
5653 auto AppendPredicate = [&](const SCEV *Expr, in createAddRecFromPHIWithCastsImpl()
5654 const SCEV *ExtendedExpr) -> void { in createAddRecFromPHIWithCastsImpl()
5670 auto *NewAR = getAddRecExpr(StartVal, Accum, L, SCEV::FlagAnyWrap); in createAddRecFromPHIWithCastsImpl()
5672 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> PredRewrite = in createAddRecFromPHIWithCastsImpl()
5679 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
5689 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>> Rewrite = in createAddRecFromPHIWithCasts()
5701 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in createAddRecFromPHIWithCasts()
5725 auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool { in areAddRecsEqualWithPreds()
5744 const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN, in createSimpleAffineAddRec()
5758 const SCEV *Accum = nullptr; in createSimpleAffineAddRec()
5767 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSimpleAffineAddRec()
5769 Flags = setFlags(Flags, SCEV::FlagNUW); in createSimpleAffineAddRec()
5771 Flags = setFlags(Flags, SCEV::FlagNSW); in createSimpleAffineAddRec()
5773 const SCEV *StartVal = getSCEV(StartValueV); in createSimpleAffineAddRec()
5774 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createSimpleAffineAddRec()
5779 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() | in createSimpleAffineAddRec()
5796 const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { in createAddRecFromPHI()
5833 const SCEV *SymbolicName = getUnknown(PN); in createAddRecFromPHI()
5838 const SCEV *BEValue = getSCEV(BEValueV); in createAddRecFromPHI()
5858 SmallVector<const SCEV *, 8> Ops; in createAddRecFromPHI()
5863 const SCEV *Accum = getAddExpr(Ops); in createAddRecFromPHI()
5870 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createAddRecFromPHI()
5875 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5877 Flags = setFlags(Flags, SCEV::FlagNSW); in createAddRecFromPHI()
5887 Flags = setFlags(Flags, SCEV::FlagNW); in createAddRecFromPHI()
5889 Flags = setFlags(Flags, SCEV::FlagNUW); in createAddRecFromPHI()
5897 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5898 const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); in createAddRecFromPHI()
5908 (SCEV::NoWrapFlags)(AR->getNoWrapFlags() | in createAddRecFromPHI()
5932 const SCEV *Shifted = SCEVShiftRewriter::rewrite(BEValue, L, *this); in createAddRecFromPHI()
5933 const SCEV *Start = SCEVInitRewriter::rewrite(Shifted, L, *this, false); in createAddRecFromPHI()
5936 const SCEV *StartVal = getSCEV(StartValueV); in createAddRecFromPHI()
5990 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { in createNodeFromSelectLikePHI()
6022 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { in createNodeForPHI()
6023 if (const SCEV *S = createAddRecFromPHI(PN)) in createNodeForPHI()
6029 if (const SCEV *S = createNodeFromSelectLikePHI(PN)) in createNodeForPHI()
6036 bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind, in SCEVMinMaxExprContains()
6039 const SCEV *OperandToFind; in SCEVMinMaxExprContains()
6052 FindClosure(const SCEV *OperandToFind, SCEVTypes RootKind) in SCEVMinMaxExprContains()
6058 bool follow(const SCEV *S) { in SCEVMinMaxExprContains()
6072 std::optional<const SCEV *>
6098 const SCEV *LA = getSCEV(TrueVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6099 const SCEV *RA = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6100 const SCEV *LS = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6101 const SCEV *RS = getSCEV(RHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6111 auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * { in createNodeForSelectOrPHIInstWithICmpInstCond()
6127 const SCEV *LDiff = getMinusSCEV(LA, LS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6128 const SCEV *RDiff = getMinusSCEV(RA, RS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6147 const SCEV *X = getNoopOrZeroExtend(getSCEV(LHS), Ty); in createNodeForSelectOrPHIInstWithICmpInstCond()
6148 const SCEV *TrueValExpr = getSCEV(TrueVal); // C+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6149 const SCEV *FalseValExpr = getSCEV(FalseVal); // x+y in createNodeForSelectOrPHIInstWithICmpInstCond()
6150 const SCEV *Y = getMinusSCEV(FalseValExpr, X); // y = (x+y)-x in createNodeForSelectOrPHIInstWithICmpInstCond()
6151 const SCEV *C = getMinusSCEV(TrueValExpr, Y); // C = (C+y)-y in createNodeForSelectOrPHIInstWithICmpInstCond()
6161 const SCEV *X = getSCEV(LHS); in createNodeForSelectOrPHIInstWithICmpInstCond()
6165 const SCEV *FalseValExpr = getSCEV(FalseVal); in createNodeForSelectOrPHIInstWithICmpInstCond()
6179 static std::optional<const SCEV *>
6180 createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr, in createNodeForSelectViaUMinSeq()
6181 const SCEV *TrueExpr, const SCEV *FalseExpr) { in createNodeForSelectViaUMinSeq()
6199 const SCEV *X, *C; in createNodeForSelectViaUMinSeq()
6212 static std::optional<const SCEV *>
6224 const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq( in createNodeForSelectOrPHIViaUMinSeq()
6235 if (std::optional<const SCEV *> S = in createNodeForSelectOrPHIViaUMinSeq()
6242 const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond, in createNodeForSelectOrPHI()
6252 if (std::optional<const SCEV *> S = in createNodeForSelectOrPHI()
6264 const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { in createNodeForGEP()
6268 SmallVector<const SCEV *, 4> IndexExprs; in createNodeForGEP()
6274 APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) { in getConstantMultipleImpl()
6317 for (const SCEV *Operand : M->operands().drop_front()) in getConstantMultipleImpl()
6325 for (const SCEV *Operand : M->operands()) in getConstantMultipleImpl()
6336 for (const SCEV *Operand : N->operands().drop_front()) in getConstantMultipleImpl()
6360 APInt ScalarEvolution::getConstantMultiple(const SCEV *S) { in getConstantMultiple()
6371 APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) { in getNonZeroConstantMultiple()
6376 uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) { in getMinTrailingZeros()
6391 SCEV::NoWrapFlags Flags) { in setNoWrapFlags()
6520 ScalarEvolution::getRangeRefIter(const SCEV *S, in getRangeRefIter()
6522 DenseMap<const SCEV *, ConstantRange> &Cache = in getRangeRefIter()
6525 SmallVector<const SCEV *> WorkList; in getRangeRefIter()
6526 SmallPtrSet<const SCEV *, 8> Seen; in getRangeRefIter()
6530 auto AddToWorklist = [&WorkList, &Seen, &Cache](const SCEV *Expr) { in getRangeRefIter()
6565 const SCEV *P = WorkList[I]; in getRangeRefIter()
6569 for (const SCEV *Op : P->operands()) in getRangeRefIter()
6586 for (const SCEV *P : reverse(drop_begin(WorkList))) { in getRangeRefIter()
6602 const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) { in getRangeRef()
6603 DenseMap<const SCEV *, ConstantRange> &Cache = in getRangeRef()
6611 DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S); in getRangeRef()
6746 const SCEV *MaxBEScev = in getRangeRef()
6774 const SCEV *SymbolicMaxBECount = in getRangeRef()
7005 ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, in getRangeForAffineAR()
7006 const SCEV *Step, in getRangeForAffineAR()
7035 const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth, in getRangeForAffineNoSelfWrappingAR()
7041 const SCEV *Step = AddRec->getStepRecurrence(*this); in getRangeForAffineNoSelfWrappingAR()
7054 const SCEV *RangeWidth = getMinusOne(AddRec->getType()); in getRangeForAffineNoSelfWrappingAR()
7055 const SCEV *StepAbs = getUMinExpr(Step, getNegativeSCEV(Step)); in getRangeForAffineNoSelfWrappingAR()
7056 const SCEV *MaxItersWithoutWrap = getUDivExpr(RangeWidth, StepAbs); in getRangeForAffineNoSelfWrappingAR()
7065 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); in getRangeForAffineNoSelfWrappingAR()
7079 const SCEV *Start = applyLoopGuards(AddRec->getStart(), AddRec->getLoop()); in getRangeForAffineNoSelfWrappingAR()
7102 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, in getRangeViaFactoring()
7103 const SCEV *Step, in getRangeViaFactoring()
7119 const SCEV *S) { in getRangeViaFactoring()
7208 const SCEV *TrueStart = this->getConstant(StartPattern.TrueValue); in getRangeViaFactoring()
7209 const SCEV *TrueStep = this->getConstant(StepPattern.TrueValue); in getRangeViaFactoring()
7210 const SCEV *FalseStart = this->getConstant(StartPattern.FalseValue); in getRangeViaFactoring()
7211 const SCEV *FalseStep = this->getConstant(StepPattern.FalseValue); in getRangeViaFactoring()
7221 SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) { in getNoWrapFlagsFromUB()
7222 if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7226 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7228 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW); in getNoWrapFlagsFromUB()
7230 Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW); in getNoWrapFlagsFromUB()
7231 if (Flags == SCEV::FlagAnyWrap) in getNoWrapFlagsFromUB()
7232 return SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7234 return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap; in getNoWrapFlagsFromUB()
7238 ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) { in getNonTrivialDefiningScopeBound()
7248 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops, in getDefiningScopeBound()
7252 SmallSet<const SCEV *, 16> Visited; in getDefiningScopeBound()
7253 SmallVector<const SCEV *> Worklist; in getDefiningScopeBound()
7254 auto pushOp = [&](const SCEV *S) { in getDefiningScopeBound()
7283 ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) { in getDefiningScopeBound()
7323 SmallVector<const SCEV *> SCEVOps; in isSCEVExprNeverPoison()
7419 const SCEV *ScalarEvolution::createSCEVIter(Value *V) { in createSCEVIter()
7435 const SCEV *CreatedSCEV = nullptr; in createSCEVIter()
7460 const SCEV *
7647 const SCEV *ScalarEvolution::createSCEV(Value *V) { in createSCEV()
7665 const SCEV *LHS; in createSCEV()
7666 const SCEV *RHS; in createSCEV()
7679 SmallVector<const SCEV *, 4> AddOps; in createSCEV()
7694 const SCEV *RHS = getSCEV(BO->RHS); in createSCEV()
7695 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7696 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7697 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7725 SmallVector<const SCEV *, 4> MulOps; in createSCEV()
7733 SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); in createSCEV()
7734 if (Flags != SCEV::FlagAnyWrap) { in createSCEV()
7763 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; in createSCEV()
7794 const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ)); in createSCEV()
7795 const SCEV *LHS = getSCEV(BO->LHS); in createSCEV()
7796 const SCEV *ShiftedLHS = nullptr; in createSCEV()
7803 SmallVector<const SCEV*, 4> MulOps; in createSCEV()
7854 const SCEV *Z0 = Z->getOperand(); in createSCEV()
7892 auto Flags = SCEV::FlagAnyWrap; in createSCEV()
7895 if ((MulFlags & SCEV::FlagNSW) && in createSCEV()
7896 ((MulFlags & SCEV::FlagNUW) || SA->getValue().ult(BitWidth - 1))) in createSCEV()
7897 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNSW); in createSCEV()
7898 if (MulFlags & SCEV::FlagNUW) in createSCEV()
7899 Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW); in createSCEV()
7930 const SCEV *AddTruncateExpr = nullptr; in createSCEV()
7932 const SCEV *AddConstant = nullptr; in createSCEV()
7944 const SCEV *ShlOp0SCEV = getSCEV(LShift->getOperand(0)); in createSCEV()
7962 const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0)); in createSCEV()
7983 const SCEV *CompositeExpr = in createSCEV()
8016 return getMinusSCEV(V1, V2, SCEV::FlagNSW); in createSCEV()
8029 const SCEV *Op = getSCEV(U->getOperand(0)); in createSCEV()
8033 const SCEV *IntOp = getPtrToIntExpr(Op, DstIntTy); in createSCEV()
8094 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
8095 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
8096 const SCEV *ClampedY = getUMinExpr(X, Y); in createSCEV()
8097 return getMinusSCEV(X, ClampedY, SCEV::FlagNUW); in createSCEV()
8100 const SCEV *X = getSCEV(II->getArgOperand(0)); in createSCEV()
8101 const SCEV *Y = getSCEV(II->getArgOperand(1)); in createSCEV()
8102 const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y)); in createSCEV()
8103 return getAddExpr(ClampedX, Y, SCEV::FlagNUW); in createSCEV()
8127 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount) { in getTripCountFromExitCount()
8138 const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount, in getTripCountFromExitCount()
8219 const SCEV *ExitCount) { in getSmallConstantTripMultiple()
8224 const SCEV *TCExpr = getTripCountFromExitCount(applyLoopGuards(ExitCount, L)); in getSmallConstantTripMultiple()
8252 const SCEV *ExitCount = getExitCount(L, ExitingBlock); in getSmallConstantTripMultiple()
8256 const SCEV *ScalarEvolution::getExitCount(const Loop *L, in getExitCount()
8270 const SCEV *
8276 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, in getBackedgeTakenCount()
8346 SmallVector<const SCEV *, 8> ToForget; in getBackedgeTakenInfo()
8393 SmallVectorImpl<const SCEV *> &ToForget) { in visitAndClearUsers()
8416 SmallVector<const SCEV *, 16> ToForget; in forgetLoop()
8429 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetLoop()
8465 SmallVector<const SCEV *, 8> ToForget; in forgetValue()
8481 if (const SCEV *S = getExistingSCEV(V)) { in forgetLcssaPhiWithNewPredecessor()
8484 SmallVector<const SCEV *, 8> Roots; in forgetLcssaPhiWithNewPredecessor()
8488 bool follow(const SCEV *S) { in forgetLcssaPhiWithNewPredecessor()
8525 const SCEV *S = getExistingSCEV(V); in forgetBlockAndLoopDispositions()
8533 SmallVector<const SCEV *, 8> Worklist = {S}; in forgetBlockAndLoopDispositions()
8534 SmallPtrSet<const SCEV *, 8> Seen = {S}; in forgetBlockAndLoopDispositions()
8536 const SCEV *Curr = Worklist.pop_back_val(); in forgetBlockAndLoopDispositions()
8555 const SCEV *
8569 SmallVector<const SCEV *, 2> Ops; in getExact()
8571 const SCEV *BECount = ENT.ExactNotTaken; in getExact()
8594 const SCEV *
8604 const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax( in getConstantMax()
8613 const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax( in getSymbolicMax()
8623 const SCEV *
8638 const SCEV *
8654 ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E) in ExitLimit()
8658 const SCEV *E, const SCEV *ConstantMaxNotTaken, in ExitLimit()
8659 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero, in ExitLimit()
8694 const SCEV *E, const SCEV *ConstantMaxNotTaken, in ExitLimit()
8695 const SCEV *SymbolicMaxNotTaken, bool MaxOrZero, in ExitLimit()
8704 bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero) in BackedgeTakenInfo()
8735 const SCEV *MustExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8736 const SCEV *MayExitMaxBECount = nullptr; in computeBackedgeTakenCount()
8807 const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount : in computeBackedgeTakenCount()
9017 const SCEV *BECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9018 const SCEV *ConstantMaxBECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9019 const SCEV *SymbolicMaxBECount = getCouldNotCompute(); in computeExitLimitFromCondFromBinOp()
9077 const SCEV *LHS = getSCEV(ExitCond->getOperand(0)); in computeExitLimitFromICmp()
9078 const SCEV *RHS = getSCEV(ExitCond->getOperand(1)); in computeExitLimitFromICmp()
9095 const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in computeExitLimitFromICmp()
9124 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this); in computeExitLimitFromICmp()
9144 Flags = setFlags(Flags, SCEV::FlagNW); in computeExitLimitFromICmp()
9145 SmallVector<const SCEV*> Operands{AR->operands()}; in computeExitLimitFromICmp()
9243 const SCEV *LHS = getSCEVAtScope(Switch->getCondition(), L); in computeExitLimitFromSingleExitSwitch()
9244 const SCEV *RHS = getConstant(Switch->findCaseDest(ExitingBlock)); in computeExitLimitFromSingleExitSwitch()
9257 const SCEV *InVal = SE.getConstant(C); in EvaluateConstantChrecAtConstant()
9258 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE); in EvaluateConstantChrecAtConstant()
9399 const SCEV *UpperBound = in computeShiftCompareExitLimit()
9648 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L, in computeExitCountExhaustively()
9715 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { in getSCEVAtScope()
9716 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values = in getSCEVAtScope()
9726 const SCEV *C = computeSCEVAtScope(V, L); in getSCEVAtScope()
9741 static Constant *BuildConstantFromSCEV(const SCEV *V) { in BuildConstantFromSCEV()
9767 for (const SCEV *Op : SA->operands()) { in BuildConstantFromSCEV()
9802 const SCEV *
9803 ScalarEvolution::getWithOperands(const SCEV *S, in getWithOperands()
9804 SmallVectorImpl<const SCEV *> &NewOps) { in getWithOperands()
9838 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { in computeSCEVAtScope()
9851 const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); in computeSCEVAtScope()
9857 SmallVector<const SCEV *, 8> NewOps; in computeSCEVAtScope()
9864 const SCEV *FoldedRec = getAddRecExpr( in computeSCEVAtScope()
9865 NewOps, AddRec->getLoop(), AddRec->getNoWrapFlags(SCEV::FlagNW)); in computeSCEVAtScope()
9880 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); in computeSCEVAtScope()
9902 ArrayRef<const SCEV *> Ops = V->operands(); in computeSCEVAtScope()
9906 const SCEV *OpAtScope = getSCEVAtScope(Ops[i], L); in computeSCEVAtScope()
9910 SmallVector<const SCEV *, 8> NewOps; in computeSCEVAtScope()
9943 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(CurrLoop); in computeSCEVAtScope()
10008 const SCEV *OrigV = getSCEV(Op); in computeSCEVAtScope()
10009 const SCEV *OpV = getSCEVAtScope(OrigV, L); in computeSCEVAtScope()
10036 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { in getSCEVAtScope()
10040 const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const { in stripInjectiveFunctions()
10056 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B, in SolveLinEquationWithOverflow()
10091 const SCEV *D = SE.getConstant(APInt::getOneBitSet(BW, Mult2)); in SolveLinEquationWithOverflow()
10368 ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V, in howFarToZero()
10427 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); in howFarToZero()
10428 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); in howFarToZero()
10446 const SCEV *Distance = CountDown ? Start : getNegativeSCEV(Start); in howFarToZero()
10462 const SCEV *Zero = getZero(Distance->getType()); in howFarToZero()
10463 const SCEV *One = getOne(Distance->getType()); in howFarToZero()
10464 const SCEV *DistancePlusOne = getAddExpr(Distance, One); in howFarToZero()
10482 const SCEV *Exact = in howFarToZero()
10484 const SCEV *ConstantMax = getCouldNotCompute(); in howFarToZero()
10490 const SCEV *SymbolicMax = in howFarToZero()
10496 const SCEV *E = SolveLinEquationWithOverflow(StepC->getAPInt(), in howFarToZero()
10499 const SCEV *M = E; in howFarToZero()
10509 ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { in howFarToNonZero()
10549 static bool HasSameValue(const SCEV *A, const SCEV *B) { in HasSameValue()
10574 const SCEV *&LHS, const SCEV *&RHS, in SimplifyICmpOperands()
10708 SCEV::FlagNSW); in SimplifyICmpOperands()
10713 SCEV::FlagNSW); in SimplifyICmpOperands()
10721 SCEV::FlagNSW); in SimplifyICmpOperands()
10726 SCEV::FlagNSW); in SimplifyICmpOperands()
10734 SCEV::FlagNUW); in SimplifyICmpOperands()
10750 SCEV::FlagNUW); in SimplifyICmpOperands()
10769 bool ScalarEvolution::isKnownNegative(const SCEV *S) { in isKnownNegative()
10773 bool ScalarEvolution::isKnownPositive(const SCEV *S) { in isKnownPositive()
10777 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) { in isKnownNonNegative()
10781 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) { in isKnownNonPositive()
10785 bool ScalarEvolution::isKnownNonZero(const SCEV *S) { in isKnownNonZero()
10793 std::pair<const SCEV *, const SCEV *>
10794 ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) { in SplitIntoInitAndPostInc()
10796 const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10800 const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this); in SplitIntoInitAndPostInc()
10806 const SCEV *LHS, const SCEV *RHS) { in isKnownViaInduction()
10857 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicate()
10872 const SCEV *LHS, in evaluatePredicate()
10873 const SCEV *RHS) { in evaluatePredicate()
10882 const SCEV *LHS, const SCEV *RHS, in isKnownPredicateAt()
10890 ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, in evaluatePredicateAt()
10891 const SCEV *RHS, const Instruction *CtxI) { in evaluatePredicateAt()
10907 const SCEV *RHS) { in isKnownOnEveryIteration()
10965 const SCEV *Step = LHS->getStepRecurrence(*this); in getMonotonicPredicateTypeImpl()
10978 const SCEV *LHS, const SCEV *RHS, in getLoopInvariantPredicate()
11064 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, in getLoopInvariantExitCondDuringFirstIterations()
11065 const Instruction *CtxI, const SCEV *MaxIter) { in getLoopInvariantExitCondDuringFirstIterations()
11084 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, in getLoopInvariantExitCondDuringFirstIterationsImpl()
11085 const Instruction *CtxI, const SCEV *MaxIter) { in getLoopInvariantExitCondDuringFirstIterationsImpl()
11112 const SCEV *Step = AR->getStepRecurrence(*this); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11125 const SCEV *Last = AR->evaluateAtIteration(MaxIter, *this); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11138 const SCEV *Start = AR->getStart(); in getLoopInvariantExitCondDuringFirstIterationsImpl()
11147 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateViaConstantRanges()
11189 const SCEV *LHS, in isKnownPredicateViaNoOverflow()
11190 const SCEV *RHS) { in isKnownPredicateViaNoOverflow()
11195 auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y, in isKnownPredicateViaNoOverflow()
11197 SCEV::NoWrapFlags ExpectedFlags) { in isKnownPredicateViaNoOverflow()
11198 const SCEV *XNonConstOp, *XConstOp; in isKnownPredicateViaNoOverflow()
11199 const SCEV *YNonConstOp, *YConstOp; in isKnownPredicateViaNoOverflow()
11200 SCEV::NoWrapFlags XFlagsPresent; in isKnownPredicateViaNoOverflow()
11201 SCEV::NoWrapFlags YFlagsPresent; in isKnownPredicateViaNoOverflow()
11243 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.sle(C2)) in isKnownPredicateViaNoOverflow()
11253 if (MatchBinaryAddToConst(LHS, RHS, C1, C2, SCEV::FlagNSW) && C1.slt(C2)) in isKnownPredicateViaNoOverflow()
11263 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ule(C2)) in isKnownPredicateViaNoOverflow()
11273 if (MatchBinaryAddToConst(RHS, LHS, C2, C1, SCEV::FlagNUW) && C1.ult(C2)) in isKnownPredicateViaNoOverflow()
11282 const SCEV *LHS, in isKnownPredicateViaSplitting()
11283 const SCEV *RHS) { in isKnownPredicateViaSplitting()
11305 const SCEV *LHS, const SCEV *RHS) { in isImpliedViaGuard()
11326 const SCEV *LHS, const SCEV *RHS) { in isLoopBackedgeGuardedByCond()
11362 const SCEV *LatchBECount = BETakenInfo.getExact(Latch, this); in isLoopBackedgeGuardedByCond()
11368 auto NoWrapFlags = SCEV::NoWrapFlags(SCEV::FlagNUW | SCEV::FlagNW); in isLoopBackedgeGuardedByCond()
11369 const SCEV *LoopCounter = in isLoopBackedgeGuardedByCond()
11431 const SCEV *LHS, in isBasicBlockEntryGuardedByCond()
11432 const SCEV *RHS) { in isBasicBlockEntryGuardedByCond()
11531 const SCEV *LHS, in isLoopEntryGuardedByCond()
11532 const SCEV *RHS) { in isLoopEntryGuardedByCond()
11550 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11551 const SCEV *RHS, in isImpliedCond()
11588 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0)); in isImpliedCond()
11589 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1)); in isImpliedCond()
11594 bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, in isImpliedCond()
11595 const SCEV *RHS, in isImpliedCond()
11597 const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCond()
11610 const SCEV *MaxValue = getZeroExtendExpr( in isImpliedCond()
11616 const SCEV *TruncFoundLHS = getTruncateExpr(FoundLHS, NarrowType); in isImpliedCond()
11617 const SCEV *TruncFoundRHS = getTruncateExpr(FoundRHS, NarrowType); in isImpliedCond()
11650 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondBalancedTypes()
11651 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS, in isImpliedCondBalancedTypes()
11730 const SCEV *CanonicalLHS = LHS, *CanonicalRHS = RHS, in isImpliedCondBalancedTypes()
11764 const SCEV *V = nullptr; in isImpliedCondBalancedTypes()
11853 bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr, in splitBinaryAdd()
11854 const SCEV *&L, const SCEV *&R, in splitBinaryAdd()
11855 SCEV::NoWrapFlags &Flags) { in splitBinaryAdd()
11867 ScalarEvolution::computeConstantDifference(const SCEV *More, const SCEV *Less) { in computeConstantDifference()
11902 SCEV::NoWrapFlags Flags; in computeConstantDifference()
11903 const SCEV *LLess = nullptr, *RLess = nullptr; in computeConstantDifference()
11904 const SCEV *LMore = nullptr, *RMore = nullptr; in computeConstantDifference()
11926 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaAddRecStart()
11927 const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) { in isImpliedCondOperandsViaAddRecStart()
11971 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsViaNoOverflow()
11972 const SCEV *FoundLHS, const SCEV *FoundRHS) { in isImpliedCondOperandsViaNoOverflow()
12048 const SCEV *LHS, const SCEV *RHS, in isImpliedViaMerge()
12049 const SCEV *FoundLHS, in isImpliedViaMerge()
12050 const SCEV *FoundRHS, unsigned Depth) { in isImpliedViaMerge()
12104 auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaMerge()
12116 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12117 const SCEV *R = getSCEV(RPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12132 const SCEV *L1 = getSCEV(LPhi->getIncomingValueForBlock(Predecessor)); in isImpliedViaMerge()
12137 const SCEV *L2 = getSCEV(LPhi->getIncomingValueForBlock(Latch)); in isImpliedViaMerge()
12149 const SCEV *L = getSCEV(LPhi->getIncomingValueForBlock(IncBB)); in isImpliedViaMerge()
12162 const SCEV *LHS, in isImpliedCondOperandsViaShift()
12163 const SCEV *RHS, in isImpliedCondOperandsViaShift()
12164 const SCEV *FoundLHS, in isImpliedCondOperandsViaShift()
12165 const SCEV *FoundRHS) { in isImpliedCondOperandsViaShift()
12204 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperands()
12205 const SCEV *FoundLHS, in isImpliedCondOperands()
12206 const SCEV *FoundRHS, in isImpliedCondOperands()
12227 static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, in IsMinMaxConsistingOf()
12228 const SCEV *Candidate) { in IsMinMaxConsistingOf()
12238 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaAddRecStart()
12260 SCEV::NoWrapFlags NW = ICmpInst::isSigned(Pred) ? in IsKnownPredicateViaAddRecStart()
12261 SCEV::FlagNSW : SCEV::FlagNUW; in IsKnownPredicateViaAddRecStart()
12272 const SCEV *LHS, const SCEV *RHS) { in IsKnownPredicateViaMinOrMax()
12303 const SCEV *LHS, const SCEV *RHS, in isImpliedViaOperations()
12304 const SCEV *FoundLHS, in isImpliedViaOperations()
12305 const SCEV *FoundRHS, in isImpliedViaOperations()
12333 const SCEV *MinusOne = getMinusOne(LHS->getType()); in isImpliedViaOperations()
12344 auto GetOpFromSExt = [&](const SCEV *S) { in isImpliedViaOperations()
12359 auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12383 auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) { in isImpliedViaOperations()
12471 const SCEV *LHS, const SCEV *RHS) { in isKnownPredicateExtendIdiom()
12504 const SCEV *LHS, const SCEV *RHS) { in isKnownViaNonRecursiveReasoning()
12514 const SCEV *LHS, const SCEV *RHS, in isImpliedCondOperandsHelper()
12515 const SCEV *FoundLHS, in isImpliedCondOperandsHelper()
12516 const SCEV *FoundRHS) { in isImpliedCondOperandsHelper()
12558 const SCEV *LHS, in isImpliedCondOperandsViaRanges()
12559 const SCEV *RHS, in isImpliedCondOperandsViaRanges()
12561 const SCEV *FoundLHS, in isImpliedCondOperandsViaRanges()
12562 const SCEV *FoundRHS) { in isImpliedCondOperandsViaRanges()
12590 bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnLT()
12595 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnLT()
12614 bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, in canIVOverflowOnGT()
12618 const SCEV *One = getOne(Stride->getType()); in canIVOverflowOnGT()
12637 const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) { in getUDivCeilSCEV()
12641 const SCEV *MinNOne = getUMinExpr(N, getOne(N->getType())); in getUDivCeilSCEV()
12642 const SCEV *NMinusOne = getMinusSCEV(N, MinNOne); in getUDivCeilSCEV()
12646 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start, in computeMaxBECountForLT()
12647 const SCEV *Stride, in computeMaxBECountForLT()
12648 const SCEV *End, in computeMaxBECountForLT()
12696 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, in howManyLessThans()
12764 if (!hasFlags(Flags, SCEV::FlagNUW) && canProveNUW()) in howManyLessThans()
12765 Flags = setFlags(Flags, SCEV::FlagNUW); in howManyLessThans()
12771 const SCEV *Step = AR->getStepRecurrence(*this); in howManyLessThans()
12805 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyLessThans()
12809 const SCEV *Stride = IV->getStepRecurrence(*this); in howManyLessThans()
12909 const SCEV *Start = IV->getStart(); in howManyLessThans()
12915 const SCEV *OrigStart = Start; in howManyLessThans()
12916 const SCEV *OrigRHS = RHS; in howManyLessThans()
12934 const SCEV *MaxBECount = computeMaxBECountForLT( in howManyLessThans()
12944 const SCEV *BECount = nullptr; in howManyLessThans()
12970 const SCEV *MinusOne = getMinusOne(Stride->getType()); in howManyLessThans()
12971 const SCEV *Numerator = in howManyLessThans()
12976 const SCEV *BECountIfBackedgeTaken = nullptr; in howManyLessThans()
12980 const SCEV *GuardedRHS = applyLoopGuards(OrigRHS, L); in howManyLessThans()
12981 const SCEV *GuardedStart = applyLoopGuards(OrigStart, L); in howManyLessThans()
13004 const SCEV *End; in howManyLessThans()
13034 const SCEV *One = getOne(Stride->getType()); in howManyLessThans()
13093 const SCEV *Delta = getMinusSCEV(End, Start); in howManyLessThans()
13104 const SCEV *ConstantMaxBECount; in howManyLessThans()
13124 const SCEV *SymbolicMaxBECount = in howManyLessThans()
13131 const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned, in howManyGreaterThans()
13149 auto WrapType = IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW; in howManyGreaterThans()
13153 const SCEV *Stride = getNegativeSCEV(IV->getStepRecurrence(*this)); in howManyGreaterThans()
13167 const SCEV *Start = IV->getStart(); in howManyGreaterThans()
13168 const SCEV *End = RHS; in howManyGreaterThans()
13193 const SCEV *One = getOne(Stride->getType()); in howManyGreaterThans()
13194 const SCEV *BECount = getUDivExpr( in howManyGreaterThans()
13214 const SCEV *ConstantMaxBECount = in howManyGreaterThans()
13222 const SCEV *SymbolicMaxBECount = in howManyGreaterThans()
13229 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range, in getNumIterationsInRange()
13237 SmallVector<const SCEV *, 4> Operands(operands()); in getNumIterationsInRange()
13239 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop(), in getNumIterationsInRange()
13250 if (any_of(operands(), [](const SCEV *Op) { return !isa<SCEVConstant>(Op); })) in getNumIterationsInRange()
13309 SmallVector<const SCEV *, 3> Ops; in getPostIncExpr()
13318 const SCEV *Last = getOperand(getNumOperands() - 1); in getPostIncExpr()
13322 SCEV::FlagAnyWrap)); in getPostIncExpr()
13326 bool ScalarEvolution::containsUndefs(const SCEV *S) const { in containsUndefs()
13327 return SCEVExprContains(S, [](const SCEV *S) { in containsUndefs()
13335 bool ScalarEvolution::containsErasedValue(const SCEV *S) const { in containsErasedValue()
13336 return SCEVExprContains(S, [](const SCEV *S) { in containsErasedValue()
13344 const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { in getElementSize()
13598 const SCEV *SV = SE.getSCEV(&I); in print()
13609 const SCEV *AtUse = SE.getSCEVAtScope(SV, L); in print()
13623 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); in print()
13672 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { in getLoopDisposition()
13691 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { in computeLoopDisposition()
13762 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { in isLoopInvariant()
13766 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { in hasComputableLoopEvolution()
13771 ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { in getBlockDisposition()
13790 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { in computeBlockDisposition()
13820 for (const SCEV *NAryOp : S->operands()) { in computeBlockDisposition()
13845 bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) { in dominates()
13849 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { in properlyDominates()
13853 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { in hasOperand()
13854 return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; }); in hasOperand()
13864 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) { in forgetBackedgeTakenCounts()
13876 void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) { in forgetMemoizedResults()
13877 SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end()); in forgetMemoizedResults()
13878 SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end()); in forgetMemoizedResults()
13881 const SCEV *Curr = Worklist.pop_back_val(); in forgetMemoizedResults()
13894 std::pair<const SCEV *, const Loop *> Entry = I->first; in forgetMemoizedResults()
13902 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) { in forgetMemoizedResultsImpl()
13958 ScalarEvolution::getUsedLoops(const SCEV *S, in getUsedLoops()
13964 bool follow(const SCEV *S) { in getUsedLoops()
13996 const SCEV *L = getSCEV(Cmp->getOperand(0)); in getReachableBlocks()
13997 const SCEV *R = getSCEV(Cmp->getOperand(1)); in getReachableBlocks()
14024 const SCEV *visitConstant(const SCEVConstant *Constant) { in verify()
14028 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in verify()
14032 const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { in verify()
14041 auto GetDelta = [&](const SCEV *Old, const SCEV *New) -> const SCEV * { in verify()
14052 const SCEV *Delta = SE2.getMinusSCEV(Old, New); in verify()
14095 const SCEV *Delta = GetDelta(CurBECount, NewBECount); in verify()
14133 const SCEV *OldSCEV = SCM.visit(KV.second); in verify()
14134 const SCEV *NewSCEV = SE2.getSCEV(I); in verify()
14135 const SCEV *Delta = GetDelta(OldSCEV, NewSCEV); in verify()
14179 const SCEV *Value = ValueAndVec.first; in verify()
14182 const SCEV *ValueAtScope = LoopAndValueAtScope.second; in verify()
14196 const SCEV *ValueAtScope = ValueAtScopeAndVec.first; in verify()
14199 const SCEV *Value = LoopAndValue.second; in verify()
14217 for (const SCEV *S : {ENT.ExactNotTaken, ENT.SymbolicMaxNotTaken}) { in verify()
14392 const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS, in getEqualPredicate()
14393 const SCEV *RHS) { in getEqualPredicate()
14399 const SCEV *LHS, const SCEV *RHS) { in getComparePredicate()
14447 static const SCEV *rewrite(const SCEV *S, const Loop *L, ScalarEvolution &SE, in rewrite()
14454 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
14471 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in visitZeroExtendExpr()
14472 const SCEV *Operand = visit(Expr->getOperand()); in visitZeroExtendExpr()
14477 const SCEV *Step = AR->getStepRecurrence(SE); in visitZeroExtendExpr()
14487 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { in visitSignExtendExpr()
14488 const SCEV *Operand = visit(Expr->getOperand()); in visitSignExtendExpr()
14493 const SCEV *Step = AR->getStepRecurrence(SE); in visitSignExtendExpr()
14530 const SCEV *convertToAddRecWithPreds(const SCEVUnknown *Expr) { in convertToAddRecWithPreds()
14534 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> in convertToAddRecWithPreds()
14557 const SCEV *
14558 ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L, in rewriteUsingPredicate()
14564 const SCEV *S, const Loop *L, in convertSCEVToAddRecWithPredicates()
14588 const SCEV *LHS, const SCEV *RHS) in SCEVComparePredicate()
14631 SCEV::NoWrapFlags ScevFlags = AR->getNoWrapFlags(); in isAlwaysTrue()
14634 if (ScalarEvolution::setFlags(ScevFlags, SCEV::FlagNSW) == ScevFlags) in isAlwaysTrue()
14653 SCEV::NoWrapFlags StaticFlags = AR->getNoWrapFlags(); in getImpliedFlags()
14656 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNSW) == StaticFlags) in getImpliedFlags()
14659 if (ScalarEvolution::setFlags(StaticFlags, SCEV::FlagNUW) == StaticFlags) { in getImpliedFlags()
14713 void ScalarEvolution::registerUser(const SCEV *User, in registerUser()
14714 ArrayRef<const SCEV *> Ops) { in registerUser()
14723 const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) { in getSCEV()
14724 const SCEV *Expr = SE.getSCEV(V); in getSCEV()
14736 const SCEV *NewSCEV = SE.rewriteUsingPredicate(Expr, &L, *Preds); in getSCEV()
14742 const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() { in getBackedgeTakenCount()
14771 const SCEV *Rewritten = II.second.second; in updateGeneration()
14779 const SCEV *Expr = getSCEV(V); in setNoOverflow()
14795 const SCEV *Expr = getSCEV(V); in hasNoOverflow()
14810 const SCEV *Expr = this->getSCEV(V); in getAsAddRec()
14861 bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS, in matchURem()
14862 const SCEV *&RHS) { in matchURem()
14884 const SCEV *A = Add->getOperand(1); in matchURem()
14890 const auto MatchURemWithDivisor = [&](const SCEV *B) { in matchURem()
14914 const SCEV *
14922 SmallVector<const SCEV*, 4> ExitCounts; in computeSymbolicMaxBackedgeTakenCount()
14924 const SCEV *ExitCount = in computeSymbolicMaxBackedgeTakenCount()
14942 const DenseMap<const SCEV *, const SCEV *> ⤅
14946 DenseMap<const SCEV *, const SCEV *> &M) in SCEVLoopGuardRewriter() argument
14949 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { return Expr; } in visitAddRecExpr()
14951 const SCEV *visitUnknown(const SCEVUnknown *Expr) { in visitUnknown()
14958 const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { in visitZeroExtendExpr()
14964 const SCEV *Op = Expr->getOperand(0); in visitZeroExtendExpr()
14982 const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { in visitSignExtendExpr()
14990 const SCEV *visitUMinExpr(const SCEVUMinExpr *Expr) { in visitUMinExpr()
14997 const SCEV *visitSMinExpr(const SCEVSMinExpr *Expr) { in visitSMinExpr()
15005 const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) { in applyLoopGuards()
15006 SmallVector<const SCEV *> ExprsToRewrite; in applyLoopGuards()
15007 auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS, in applyLoopGuards()
15008 const SCEV *RHS, in applyLoopGuards()
15009 DenseMap<const SCEV *, const SCEV *> in applyLoopGuards()
15045 const SCEV *RewrittenLHS = I != RewriteMap.end() ? I->second : LHSUnknown; in applyLoopGuards()
15059 [&](const SCEV *Expr, SCEVTypes &SCTy, const SCEV *&LHS, in applyLoopGuards()
15060 const SCEV *&RHS) { in applyLoopGuards()
15078 auto GetNonNegExprAndPosDivisor = [&](const SCEV *Expr, const SCEV *Divisor, in applyLoopGuards()
15092 auto GetNextSCEVDividesByDivisor = [&](const SCEV *Expr, in applyLoopGuards()
15093 const SCEV *Divisor) { in applyLoopGuards()
15108 auto GetPreviousSCEVDividesByDivisor = [&](const SCEV *Expr, in applyLoopGuards()
15109 const SCEV *Divisor) { in applyLoopGuards()
15122 std::function<const SCEV *(const SCEV *, const SCEV *)> in applyLoopGuards()
15123 ApplyDivisibiltyOnMinMaxExpr = [&](const SCEV *MinMaxExpr, in applyLoopGuards()
15124 const SCEV *Divisor) { in applyLoopGuards()
15125 const SCEV *MinMaxLHS = nullptr, *MinMaxRHS = nullptr; in applyLoopGuards()
15137 SmallVector<const SCEV *> Ops = { in applyLoopGuards()
15149 const SCEV *URemLHS = nullptr; in applyLoopGuards()
15150 const SCEV *URemRHS = nullptr; in applyLoopGuards()
15154 const SCEV *RewrittenLHS = in applyLoopGuards()
15180 auto AddRewrite = [&](const SCEV *From, const SCEV *FromRewritten, in applyLoopGuards()
15181 const SCEV *To) { in applyLoopGuards()
15190 auto GetMaybeRewritten = [&](const SCEV *S) { in applyLoopGuards()
15202 std::function<bool(const SCEV *, const SCEV *&)> HasDivisibiltyInfo = in applyLoopGuards()
15203 [&](const SCEV *Expr, const SCEV *&DividesBy) { in applyLoopGuards()
15224 std::function<bool(const SCEV *, const SCEV *&)> IsKnownToDivideBy = in applyLoopGuards()
15225 [&](const SCEV *Expr, const SCEV *DividesBy) { in applyLoopGuards()
15234 const SCEV *RewrittenLHS = GetMaybeRewritten(LHS); in applyLoopGuards()
15235 const SCEV *DividesBy = nullptr; in applyLoopGuards()
15252 const SCEV *One = getOne(RHS->getType()); in applyLoopGuards()
15281 SmallVector<const SCEV *, 16> Worklist(1, LHS); in applyLoopGuards()
15282 SmallPtrSet<const SCEV *, 16> Visited; in applyLoopGuards()
15289 const SCEV *From = Worklist.pop_back_val(); in applyLoopGuards()
15294 const SCEV *FromRewritten = GetMaybeRewritten(From); in applyLoopGuards()
15295 const SCEV *To = nullptr; in applyLoopGuards()
15329 const SCEV *OneAlignedUp = in applyLoopGuards()
15386 DenseMap<const SCEV *, const SCEV *> RewriteMap; in applyLoopGuards()
15421 for (const SCEV *Expr : ExprsToRewrite) { in applyLoopGuards()
15422 const SCEV *RewriteTo = RewriteMap[Expr]; in applyLoopGuards()