Lines Matching defs:SCEV
29 // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however
137 typedef DenseMap<const SCEV *, RegSortData> RegUsesTy;
140 SmallVector<const SCEV *, 16> RegSequence;
143 void CountRegister(const SCEV *Reg, size_t LUIdx);
144 void DropRegister(const SCEV *Reg, size_t LUIdx);
147 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
149 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const;
153 typedef SmallVectorImpl<const SCEV *>::iterator iterator;
154 typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator;
164 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) {
175 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) {
200 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
211 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const {
250 SmallVector<const SCEV *, 4> BaseRegs;
254 const SCEV *ScaledReg;
265 void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE);
276 void DeleteBaseReg(const SCEV *&S);
278 bool referencesReg(const SCEV *S) const;
289 static void DoInitialMatch(const SCEV *S, Loop *L,
290 SmallVectorImpl<const SCEV *> &Good,
291 SmallVectorImpl<const SCEV *> &Bad,
314 AR->getLoop(), SCEV::FlagAnyWrap),
322 SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end());
323 const SCEV *NewMul = SE.getMulExpr(Ops);
325 SmallVector<const SCEV *, 4> MyGood;
326 SmallVector<const SCEV *, 4> MyBad;
328 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue(
330 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(),
333 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(),
347 void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) {
348 SmallVector<const SCEV *, 4> Good;
349 SmallVector<const SCEV *, 4> Bad;
352 const SCEV *Sum = SE.getAddExpr(Good);
358 const SCEV *Sum = SE.getAddExpr(Bad);
428 void Formula::DeleteBaseReg(const SCEV *&S) {
435 bool Formula::referencesReg(const SCEV *S) const {
447 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
464 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
528 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
531 // Handle the trivial case, which works for any SCEV type.
562 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
565 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
570 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
571 return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
579 SmallVector<const SCEV *, 8> Ops;
582 const SCEV *Op = getExactSDiv(*I, RHS, SE,
595 SmallVector<const SCEV *, 4> Ops;
599 const SCEV *S = *I;
601 if (const SCEV *Q = getExactSDiv(S, RHS, SE,
618 /// return that integer value, and mutate S to point to a new SCEV with that
620 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) {
627 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
633 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
637 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
638 SCEV::FlagAnyWrap);
645 /// return that symbol, and mutate S to point to a new SCEV with that
647 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) {
654 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
660 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
664 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
665 SCEV::FlagAnyWrap);
738 /// is tricky because SCEV doesn't track which expressions are actually computed
746 static bool isHighCostExpansion(const SCEV *S,
747 SmallPtrSet<const SCEV*, 8> &Processed,
895 SmallPtrSet<const SCEV *, 16> &Regs,
896 const DenseSet<const SCEV *> &VisitedRegs,
901 SmallPtrSet<const SCEV *, 16> *LoserRegs = nullptr);
907 void RateRegister(const SCEV *Reg,
908 SmallPtrSet<const SCEV *, 16> &Regs,
911 void RatePrimaryRegister(const SCEV *Reg,
912 SmallPtrSet<const SCEV *, 16> &Regs,
915 SmallPtrSet<const SCEV *, 16> *LoserRegs);
921 void Cost::RateRegister(const SCEV *Reg,
922 SmallPtrSet<const SCEV *, 16> &Regs,
969 void Cost::RatePrimaryRegister(const SCEV *Reg,
970 SmallPtrSet<const SCEV *, 16> &Regs,
973 SmallPtrSet<const SCEV *, 16> *LoserRegs) {
987 SmallPtrSet<const SCEV *, 16> &Regs,
988 const DenseSet<const SCEV *> &VisitedRegs,
993 SmallPtrSet<const SCEV *, 16> *LoserRegs) {
996 if (const SCEV *ScaledReg = F.ScaledReg) {
1005 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
1007 const SCEV *BaseReg = *I;
1177 /// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*.
1179 static SmallVector<const SCEV *, 4> getEmptyKey() {
1180 SmallVector<const SCEV *, 4> V;
1181 V.push_back(reinterpret_cast<const SCEV *>(-1));
1185 static SmallVector<const SCEV *, 4> getTombstoneKey() {
1186 SmallVector<const SCEV *, 4> V;
1187 V.push_back(reinterpret_cast<const SCEV *>(-2));
1191 static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) {
1195 static bool isEqual(const SmallVector<const SCEV *, 4> &LHS,
1196 const SmallVector<const SCEV *, 4> &RHS) {
1207 DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
1220 typedef PointerIntPair<const SCEV *, 2, KindType> SCEVUseKindPair;
1235 /// with a single formula--the one that initially matched. Some SCEV
1253 SmallPtrSet<const SCEV *, 4> Regs;
1276 SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1292 SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1304 for (SmallVectorImpl<const SCEV *>::const_iterator I =
1330 SmallPtrSet<const SCEV *, 4> OldRegs = Regs;
1340 for (SmallPtrSet<const SCEV *, 4>::iterator I = OldRegs.begin(),
1565 Type *AccessTy, const SCEV *S, bool HasBaseReg) {
1594 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
1602 const SCEV *IncExpr;
1604 IVInc(Instruction *U, Value *O, const SCEV *E):
1612 const SCEV *ExprBase;
1616 IVChain(const IVInc &Head, const SCEV *Base)
1641 bool isProfitableIncrement(const SCEV *OperExpr,
1642 const SCEV *IncExpr,
1724 std::pair<size_t, int64_t> getUse(const SCEV *&Expr,
1732 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1733 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1774 const SmallPtrSet<const SCEV *, 16> &CurRegs,
1775 DenseSet<const SCEV *> &VisitedRegs) const;
1822 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
2002 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
2005 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1);
2008 const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount);
2035 const SCEV *MaxLHS = Max->getOperand(0);
2036 const SCEV *MaxRHS = Max->getOperand(1);
2046 const SCEV *IV = SE.getSCEV(Cond->getOperand(0));
2157 const SCEV *A = IU.getStride(*CondUse, L);
2158 const SCEV *B = IU.getStride(*UI, L);
2289 LSRInstance::getUse(const SCEV *&Expr,
2291 const SCEV *Copy = Expr;
2383 SmallSetVector<const SCEV *, 4> Strides;
2386 SmallVector<const SCEV *, 4> Worklist;
2388 const SCEV *Expr = IU.getExpr(*UI);
2396 const SCEV *S = Worklist.pop_back_val();
2408 for (SmallSetVector<const SCEV *, 4>::const_iterator
2410 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
2412 const SCEV *OldStride = *I;
2413 const SCEV *NewStride = *NewStrideIter;
2482 /// getExprBase - Return an approximation of this SCEV expression's "base", or
2491 /// SCEVUnknown, we simply return the rightmost SCEV operand.
2492 static const SCEV *getExprBase(const SCEV *S) {
2511 const SCEV *SubExpr = *I;
2530 bool IVChain::isProfitableIncrement(const SCEV *OperExpr,
2531 const SCEV *IncExpr,
2540 const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand));
2545 SmallPtrSet<const SCEV*, 8> Processed;
2588 const SCEV *LastIncExpr = nullptr;
2641 const SCEV *const OperExpr = SE.getSCEV(NextIV);
2642 const SCEV *const OperExprBase = getExprBase(OperExpr);
2647 const SCEV *LastIncExpr = nullptr;
2654 // first avoids creating extra SCEV expressions.
2667 const SCEV *PrevExpr = SE.getSCEV(PrevIV);
2668 const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
2715 // We currently ignore intermediate values within SCEV expressions, assuming
2791 // Ignore users that are part of a SCEV expression. This way we only
2856 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst,
2912 const SCEV *LeftOverExpr = nullptr;
2926 const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy);
2934 const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc),
3004 const SCEV *S = IU.getExpr(*UI);
3025 const SCEV *N = SE.getSCEV(NV);
3068 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) {
3082 LSRInstance::InsertSupplementalFormula(const SCEV *S,
3096 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
3121 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
3122 SmallPtrSet<const SCEV *, 8> Inserted;
3125 const SCEV *S = Worklist.pop_back_val();
3159 // Ignore uses which are part of other SCEV expressions, to avoid
3162 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
3205 static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C,
3206 SmallVectorImpl<const SCEV *> &Ops,
3218 const SCEV *Remainder = CollectSubexprs(*I, C, Ops, L, SE, Depth+1);
3228 const SCEV *Remainder = CollectSubexprs(AR->getStart(),
3242 //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
3243 SCEV::FlagAnyWrap);
3252 const SCEV *Remainder =
3267 const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
3268 SmallVector<const SCEV *, 8> AddOps;
3269 const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE);
3276 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
3292 SmallVector<const SCEV *, 8> InnerAddOps(
3293 ((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J);
3295 ((const SmallVector<const SCEV *, 8> &)AddOps).end());
3304 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps);
3375 SmallVector<const SCEV *, 4> Ops;
3376 for (SmallVectorImpl<const SCEV *>::const_iterator
3378 const SCEV *BaseReg = *I;
3386 const SCEV *Sum = SE.getAddExpr(Ops);
3402 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
3434 const SCEV *G = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
3443 const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), *I), G);
3546 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3624 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3629 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) {
3662 for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(),
3684 const SCEV *OrigReg;
3686 WorkItem(size_t LI, int64_t I, const SCEV *R)
3710 typedef std::map<int64_t, const SCEV *> ImmMapTy;
3711 typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy;
3713 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap;
3714 SmallVector<const SCEV *, 8> Sequence;
3717 const SCEV *Reg = *I;
3732 for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(),
3734 const SCEV *Reg = *I;
3750 const SCEV *OrigReg = J->second;
3795 const SCEV *OrigReg = WI.OrigReg;
3798 const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm));
3839 const SCEV *BaseReg = F.BaseRegs[N];
3856 for (SmallVectorImpl<const SCEV *>::const_iterator
3917 DenseSet<const SCEV *> VisitedRegs;
3918 SmallPtrSet<const SCEV *, 16> Regs;
3919 SmallPtrSet<const SCEV *, 16> LoserRegs;
3926 typedef DenseMap<SmallVector<const SCEV *, 4>, size_t, UniquifierDenseMapInfo>
3961 SmallVector<const SCEV *, 4> Key;
3962 for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(),
3964 const SCEV *Reg = *J;
4060 for (SmallVectorImpl<const SCEV *>::const_iterator
4211 SmallPtrSet<const SCEV *, 4> Taken;
4219 const SCEV *Best = nullptr;
4223 const SCEV *Reg = *I;
4286 const SmallPtrSet<const SCEV *, 16> &CurRegs,
4287 DenseSet<const SCEV *> &VisitedRegs) const {
4304 SmallSetVector<const SCEV *, 4> ReqRegs;
4305 for (SmallPtrSet<const SCEV *, 16>::const_iterator I = CurRegs.begin(),
4310 SmallPtrSet<const SCEV *, 16> NewRegs;
4320 for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(),
4322 const SCEV *Reg = *J;
4353 for (SmallPtrSet<const SCEV *, 16>::const_iterator
4373 SmallPtrSet<const SCEV *, 16> CurRegs;
4374 DenseSet<const SCEV *> VisitedRegs;
4554 SmallVector<const SCEV *, 8> Ops;
4557 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
4559 const SCEV *Reg = *I;
4574 const SCEV *ScaledS = F.ScaledReg;
4662 const SCEV *FullS = Ops.empty() ?