Lines Matching defs:SCEV
28 // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however
141 /// Limit the size of expression that SCEV-based salvaging will attempt to
329 const SCEV *getSCEV(ScalarEvolution &SE, Type *Ty) const {
330 const SCEV *S = SE.getConstant(Ty, Quantity);
336 const SCEV *getNegativeSCEV(ScalarEvolution &SE, Type *Ty) const {
337 const SCEV *NegS = SE.getConstant(Ty, -(uint64_t)Quantity);
343 const SCEV *getUnknownSCEV(ScalarEvolution &SE, Type *Ty) const {
344 const SCEV *SU = SE.getUnknown(ConstantInt::getSigned(Ty, Quantity));
394 using RegUsesTy = DenseMap<const SCEV *, RegSortData>;
397 SmallVector<const SCEV *, 16> RegSequence;
400 void countRegister(const SCEV *Reg, size_t LUIdx);
401 void dropRegister(const SCEV *Reg, size_t LUIdx);
404 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
406 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const;
410 using iterator = SmallVectorImpl<const SCEV *>::iterator;
411 using const_iterator = SmallVectorImpl<const SCEV *>::const_iterator;
422 RegUseTracker::countRegister(const SCEV *Reg, size_t LUIdx) {
433 RegUseTracker::dropRegister(const SCEV *Reg, size_t LUIdx) {
457 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
468 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const {
510 SmallVector<const SCEV *, 4> BaseRegs;
514 const SCEV *ScaledReg = nullptr;
523 void initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE);
536 void deleteBaseReg(const SCEV *&S);
538 bool referencesReg(const SCEV *S) const;
549 static void DoInitialMatch(const SCEV *S, Loop *L,
550 SmallVectorImpl<const SCEV *> &Good,
551 SmallVectorImpl<const SCEV *> &Bad,
561 for (const SCEV *S : Add->operands())
573 AR->getLoop(), SCEV::FlagAnyWrap),
581 SmallVector<const SCEV *, 4> Ops(drop_begin(Mul->operands()));
582 const SCEV *NewMul = SE.getMulExpr(Ops);
584 SmallVector<const SCEV *, 4> MyGood;
585 SmallVector<const SCEV *, 4> MyBad;
587 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue(
589 for (const SCEV *S : MyGood)
591 for (const SCEV *S : MyBad)
603 void Formula::initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) {
604 SmallVector<const SCEV *, 4> Good;
605 SmallVector<const SCEV *, 4> Bad;
608 const SCEV *Sum = SE.getAddExpr(Good);
614 const SCEV *Sum = SE.getAddExpr(Bad);
622 static bool containsAddRecDependentOnLoop(const SCEV *S, const Loop &L) {
623 return SCEVExprContains(S, [&L](const SCEV *S) {
647 return none_of(BaseRegs, [&L](const SCEV *S) {
682 auto I = find_if(BaseRegs, [&L](const SCEV *S) {
728 void Formula::deleteBaseReg(const SCEV *&S) {
735 bool Formula::referencesReg(const SCEV *S) const {
746 for (const SCEV *BaseReg : BaseRegs)
763 for (const SCEV *BaseReg : BaseRegs) {
824 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
827 // Handle the trivial case, which works for any SCEV type.
861 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
864 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
869 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
870 return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
878 SmallVector<const SCEV *, 8> Ops;
879 for (const SCEV *S : Add->operands()) {
880 const SCEV *Op = getExactSDiv(S, RHS, SE, IgnoreSignificantBits);
899 SmallVector<const SCEV *, 4> LOps(drop_begin(Mul->operands()));
900 SmallVector<const SCEV *, 4> ROps(drop_begin(MulRHS->operands()));
907 SmallVector<const SCEV *, 4> Ops;
909 for (const SCEV *S : Mul->operands()) {
911 if (const SCEV *Q = getExactSDiv(S, RHS, SE,
928 /// value, and mutate S to point to a new SCEV with that value excluded.
929 static Immediate ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) {
936 SmallVector<const SCEV *, 8> NewOps(Add->operands());
942 SmallVector<const SCEV *, 8> NewOps(AR->operands());
946 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
947 SCEV::FlagAnyWrap);
962 /// mutate S to point to a new SCEV with that value excluded.
963 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) {
970 SmallVector<const SCEV *, 8> NewOps(Add->operands());
976 SmallVector<const SCEV *, 8> NewOps(AR->operands());
980 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
981 SCEV::FlagAnyWrap);
1099 /// is tricky because SCEV doesn't track which expressions are actually computed
1107 static bool isHighCostExpansion(const SCEV *S,
1108 SmallPtrSetImpl<const SCEV*> &Processed,
1133 for (const SCEV *S : Add->operands()) {
1239 SmallPtrSetImpl<const SCEV *> &Regs,
1240 const DenseSet<const SCEV *> &VisitedRegs,
1242 SmallPtrSetImpl<const SCEV *> *LoserRegs = nullptr);
1248 void RateRegister(const Formula &F, const SCEV *Reg,
1249 SmallPtrSetImpl<const SCEV *> &Regs);
1250 void RatePrimaryRegister(const Formula &F, const SCEV *Reg,
1251 SmallPtrSetImpl<const SCEV *> &Regs,
1252 SmallPtrSetImpl<const SCEV *> *LoserRegs);
1284 /// SmallVectors of const SCEV*.
1286 static SmallVector<const SCEV *, 4> getEmptyKey() {
1287 SmallVector<const SCEV *, 4> V;
1288 V.push_back(reinterpret_cast<const SCEV *>(-1));
1292 static SmallVector<const SCEV *, 4> getTombstoneKey() {
1293 SmallVector<const SCEV *, 4> V;
1294 V.push_back(reinterpret_cast<const SCEV *>(-2));
1298 static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) {
1302 static bool isEqual(const SmallVector<const SCEV *, 4> &LHS,
1303 const SmallVector<const SCEV *, 4> &RHS) {
1314 DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
1327 using SCEVUseKindPair = PointerIntPair<const SCEV *, 2, KindType>;
1344 /// with a single formula--the one that initially matched. Some SCEV
1362 SmallPtrSet<const SCEV *, 4> Regs;
1380 float getNotSelectedProbability(const SCEV *Reg) const;
1397 static unsigned getSetupCost(const SCEV *Reg, unsigned Depth) {
1408 [&](unsigned i, const SCEV *Reg) {
1418 void Cost::RateRegister(const Formula &F, const SCEV *Reg,
1419 SmallPtrSetImpl<const SCEV *> &Regs) {
1452 const SCEV *LoopStep = AR->getStepRecurrence(*SE);
1454 const SCEV *LoopStart = AR->getStart();
1488 void Cost::RatePrimaryRegister(const Formula &F, const SCEV *Reg,
1489 SmallPtrSetImpl<const SCEV *> &Regs,
1490 SmallPtrSetImpl<const SCEV *> *LoserRegs) {
1503 SmallPtrSetImpl<const SCEV *> &Regs,
1504 const DenseSet<const SCEV *> &VisitedRegs,
1506 SmallPtrSetImpl<const SCEV *> *LoserRegs) {
1514 if (const SCEV *ScaledReg = F.ScaledReg) {
1523 for (const SCEV *BaseReg : F.BaseRegs) {
1702 SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1710 float LSRUse::getNotSelectedProbability(const SCEV *Reg) const {
1726 SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1738 for (const SCEV *BaseReg : F.BaseRegs)
1763 SmallPtrSet<const SCEV *, 4> OldRegs = std::move(Regs);
1771 for (const SCEV *S : OldRegs)
2048 MemAccessTy AccessTy, const SCEV *S,
2082 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
2090 const SCEV *IncExpr;
2092 IVInc(Instruction *U, Value *O, const SCEV *E)
2100 const SCEV *ExprBase = nullptr;
2103 IVChain(const IVInc &Head, const SCEV *Base)
2127 bool isProfitableIncrement(const SCEV *OperExpr,
2128 const SCEV *IncExpr,
2169 /// The cost of the current SCEV, the best solution by LSR will be dropped if
2193 /// Induction variables that were generated and inserted by the SCEV Expander.
2218 std::pair<size_t, Immediate> getUse(const SCEV *&Expr, LSRUse::KindType Kind,
2225 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
2226 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
2270 const SmallPtrSet<const SCEV *, 16> &CurRegs,
2271 DenseSet<const SCEV *> &VisitedRegs) const;
2313 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
2501 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
2504 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1);
2507 const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount);
2534 const SCEV *MaxLHS = Max->getOperand(0);
2535 const SCEV *MaxRHS = Max->getOperand(1);
2545 const SCEV *IV = SE.getSCEV(Cond->getOperand(0));
2672 const SCEV *A = IU.getStride(*CondUse, L);
2673 const SCEV *B = IU.getStride(*UI, L);
2808 std::pair<size_t, Immediate> LSRInstance::getUse(const SCEV *&Expr,
2811 const SCEV *Copy = Expr;
2895 SmallSetVector<const SCEV *, 4> Strides;
2898 SmallVector<const SCEV *, 4> Worklist;
2900 const SCEV *Expr = IU.getExpr(U);
2910 const SCEV *S = Worklist.pop_back_val();
2922 for (SmallSetVector<const SCEV *, 4>::const_iterator
2924 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
2926 const SCEV *OldStride = *I;
2927 const SCEV *NewStride = *NewStrideIter;
2988 /// Return an approximation of this SCEV expression's "base", or NULL for any
2997 /// SCEVUnknown, we simply return the rightmost SCEV operand.
2998 static const SCEV *getExprBase(const SCEV *S) {
3016 for (const SCEV *SubExpr : reverse(Add->operands())) {
3028 llvm_unreachable("Unknown SCEV kind!");
3036 bool IVChain::isProfitableIncrement(const SCEV *OperExpr,
3037 const SCEV *IncExpr,
3046 const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand));
3051 SmallPtrSet<const SCEV*, 8> Processed;
3093 const SCEV *LastIncExpr = nullptr;
3149 const SCEV *const OperExpr = SE.getSCEV(NextIV);
3150 const SCEV *const OperExprBase = getExprBase(OperExpr);
3155 const SCEV *LastIncExpr = nullptr;
3162 // first avoids creating extra SCEV expressions.
3175 const SCEV *PrevExpr = SE.getSCEV(PrevIV);
3176 const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
3223 // We currently ignore intermediate values within SCEV expressions, assuming
3296 // Ignore users that are part of a SCEV expression. This way we only
3358 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst,
3428 const SCEV *LeftOverExpr = nullptr;
3429 const SCEV *Accum = SE.getZero(IntTy);
3430 SmallVector<std::pair<const SCEV *, Value *>> Bases;
3444 const SCEV *IncExpr = SE.getNoopOrSignExtend(Inc.IncExpr, IntTy);
3453 const SCEV *Remainder = SE.getMinusSCEV(Accum, MapScev);
3458 const SCEV *IVOperExpr =
3473 const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc),
3525 SmallPtrSet<const SCEV *, 16> Regs;
3526 DenseSet<const SCEV *> VisitedRegs;
3547 const SCEV *S = IU.getExpr(U);
3575 const SCEV *N = SE.getSCEV(NV);
3595 // SCEV can't compute the difference of two unknown pointers.
3628 // Create SCEV as Formula for calculating baseline cost
3653 void LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU,
3668 LSRInstance::InsertSupplementalFormula(const SCEV *S,
3681 for (const SCEV *BaseReg : F.BaseRegs)
3706 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
3707 SmallPtrSet<const SCEV *, 32> Visited;
3715 const SCEV *S = Worklist.pop_back_val();
3717 // Don't process the same SCEV twice
3786 // Ignore uses which are part of other SCEV expressions, to avoid
3789 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
3834 static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C,
3835 SmallVectorImpl<const SCEV *> &Ops,
3845 for (const SCEV *S : Add->operands()) {
3846 const SCEV *Remainder = CollectSubexprs(S, C, Ops, L, SE, Depth+1);
3856 const SCEV *Remainder = CollectSubexprs(AR->getStart(),
3870 //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
3871 SCEV::FlagAnyWrap);
3880 const SCEV *Remainder =
3890 /// Return true if the SCEV represents a value that may end up as a
3893 LSRUse &LU, const SCEV *S, const Loop *L,
3901 const SCEV *LoopStep = AR->getStepRecurrence(SE);
3907 const SCEV *LoopStart = AR->getStart();
3919 const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
3926 SmallVector<const SCEV *, 8> AddOps;
3927 const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE);
3934 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
3949 SmallVector<const SCEV *, 8> InnerAddOps(
3950 ((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J);
3952 ((const SmallVector<const SCEV *, 8> &)AddOps).end());
3961 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps);
4041 SmallVector<const SCEV *, 4> Ops;
4045 for (const SCEV *BaseReg : Base.BaseRegs) {
4062 auto GenerateFormula = [&](const SCEV *Sum) {
4078 SmallVector<const SCEV *, 4> OpsCopy(Ops); // Don't let SE modify Ops.
4097 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
4130 auto GenerateOffset = [&](const SCEV *G, Immediate Offset) {
4138 const SCEV *NewOffset = Offset.getSCEV(SE, G->getType());
4139 const SCEV *NewG = SE.getAddExpr(NewOffset, G);
4157 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
4240 for (const SCEV *BaseReg : Base.BaseRegs)
4288 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
4364 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
4369 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true))
4397 static const SCEV *
4399 const SCEV *Expr, Type *ToTy,
4401 const SCEV *Result = nullptr;
4404 const SCEV *NewDenormExpr = SE.getAnyExtendExpr(DenormExpr, ToTy);
4405 const SCEV *New = normalizeForPostIncUse(NewDenormExpr, L, SE);
4431 [](const SCEV *S) { return S->getType()->isPointerTy(); }))
4442 // Sometimes SCEV is able to prove zero during ext transform. It may
4443 // happen if SCEV did not do all possible transforms while creating the
4447 const SCEV *NewScaledReg =
4454 for (const SCEV *&BaseReg : F.BaseRegs) {
4455 const SCEV *NewBaseReg =
4485 const SCEV *OrigReg;
4487 WorkItem(size_t LI, Immediate I, const SCEV *R)
4511 using ImmMapTy = std::map<Immediate, const SCEV *, KeyOrderTargetImmediate>;
4513 DenseMap<const SCEV *, ImmMapTy> Map;
4514 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap;
4515 SmallVector<const SCEV *, 8> Sequence;
4516 for (const SCEV *Use : RegUses) {
4517 const SCEV *Reg = Use; // Make a copy for ExtractImmediate to modify.
4532 for (const SCEV *Reg : Sequence) {
4548 const SCEV *OrigReg = J->second;
4608 const SCEV *OrigReg = WI.OrigReg;
4611 const SCEV *NegImmS = Imm.getNegativeSCEV(SE, IntTy);
4628 const SCEV *S = Offset.getNegativeSCEV(SE, IntTy);
4643 // A scalable SCEV won't be constant, but we might still have
4660 const SCEV *BaseReg = F.BaseRegs[N];
4685 for (const SCEV *NewReg : NewF.BaseRegs)
4749 DenseSet<const SCEV *> VisitedRegs;
4750 SmallPtrSet<const SCEV *, 16> Regs;
4751 SmallPtrSet<const SCEV *, 16> LoserRegs;
4759 DenseMap<SmallVector<const SCEV *, 4>, size_t, UniquifierDenseMapInfo>;
4794 SmallVector<const SCEV *, 4> Key;
4795 for (const SCEV *Reg : F.BaseRegs) {
4886 for (SmallVectorImpl<const SCEV *>::const_iterator
5035 using BestFormulaeTy = DenseMap<std::pair<const SCEV *, int64_t>, size_t>;
5041 DenseSet<const SCEV *> VisitedRegs;
5042 SmallPtrSet<const SCEV *, 16> Regs;
5056 for (const SCEV *Reg : FA.BaseRegs) {
5061 for (const SCEV *Reg : FB.BaseRegs) {
5217 SmallPtrSet<const SCEV *, 4> UniqRegs;
5221 DenseMap <const SCEV *, float> RegNumMap;
5222 for (const SCEV *Reg : RegUses) {
5257 for (const SCEV *BaseReg : F.BaseRegs) {
5265 if (const SCEV *ScaledReg = F.ScaledReg) {
5306 ScalarEvolution &SE, const SCEV *Best,
5307 const SCEV *Reg,
5334 SmallPtrSet<const SCEV *, 4> Taken;
5342 const SCEV *Best = nullptr;
5344 for (const SCEV *Reg : RegUses) {
5427 const SmallPtrSet<const SCEV *, 16> &CurRegs,
5428 DenseSet<const SCEV *> &VisitedRegs) const {
5445 SmallSetVector<const SCEV *, 4> ReqRegs;
5446 for (const SCEV *S : CurRegs)
5450 SmallPtrSet<const SCEV *, 16> NewRegs;
5461 for (const SCEV *Reg : ReqRegs) {
5491 for (const SCEV *S : NewRegs) dbgs()
5510 SmallPtrSet<const SCEV *, 16> CurRegs;
5511 DenseSet<const SCEV *> VisitedRegs;
5713 SmallVector<const SCEV *, 8> Ops;
5716 for (const SCEV *Reg : F.BaseRegs) {
5727 const SCEV *ScaledS = F.ScaledReg;
5786 // out at this point, or should we generate a SCEV adding together mixed
5818 const SCEV *FullS = Ops.empty() ?
6391 /// The DIExpression as we translate the SCEV.
6433 /// Several SCEV types are sequences of the same arithmetic operator applied
6438 "Expected arithmetic SCEV type");
6453 const llvm::SCEV *Inner = C->getOperand(0);
6466 bool pushSCEV(const llvm::SCEV *S) {
6488 "Unexpected cast type in SCEV.");
6506 /// SCEV constant value is an identity function.
6507 bool isIdentityFunction(uint64_t Op, const SCEV *S) {
6524 /// Convert a SCEV of a value to a DIExpression that is pushed onto the
6531 assert(SAR.isAffine() && "Expected affine SCEV");
6536 const SCEV *Start = SAR.getStart();
6537 const SCEV *Stride = SAR.getStepRecurrence(SE);
6562 /// Combine a translation of the SCEV and the IV to create an expression that
6565 bool createIterCountExpr(const SCEV *S,
6576 LLVM_DEBUG(dbgs() << "scev-salvage: Location to salvage SCEV: " << *S
6587 // combination with the value's SCEV this enables recovery.
6595 /// Convert a SCEV of a value to a DIExpression that is pushed onto the
6602 assert(SAR.isAffine() && "Expected affine SCEV");
6604 LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV. Unsupported nested AddRec: "
6608 const SCEV *Start = SAR.getStart();
6609 const SCEV *Stride = SAR.getStepRecurrence(SE);
6659 // `DW_OP_LLVM_arg n` represents the nth LocationOp in this SCEV,
6680 SmallVector<const llvm::SCEV *, 2> SCEVs;
6823 const SCEV *SCEVInductionVar,
6857 // It's possible that a value referred to in the SCEV may have been
6861 LLVM_DEBUG(dbgs() << "scev-salvage: SCEV for location at index: " << i
6868 << " with SCEV: " << *DVIRec.SCEVs[i] << "\n");
6938 const llvm::SCEV *SCEVInductionVar = SE.getSCEV(LSRInductionVar);
6940 "Anticipated a SCEV for the post-LSR induction variable");
6957 LLVM_DEBUG(dbgs() << "scev-salvage: IV SCEV: " << *SCEVInductionVar
6968 /// corresponding SCEV(s). Also ensure that the DVI is not deleted between
6993 const SCEV *S = SE.getSCEV(LocOp);
7065 static std::optional<std::tuple<PHINode *, PHINode *, const SCEV *, bool>>
7134 const SCEV *BECount = SE.getBackedgeTakenCount(L);
7139 const SCEV *TermValueS = nullptr;
7148 << "' is not SCEV-able, not qualified for the "
7155 LLVM_DEBUG(dbgs() << "SCEV of phi '" << PN
7175 const SCEV *TermValueSLocal = PostInc->evaluateAtIteration(BECount, SE);
7234 << " BECount (SCEV): " << *SE.getBackedgeTakenCount(L) << "\n"
7288 // SCEV, we can replace the exit block PHI with the final value of the IV and
7390 LLVM_DEBUG(dbgs() << "scev-salvage: SCEV salvaging not possible. An IV "