Lines Matching refs:SCEV
29 // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however
133 typedef DenseMap<const SCEV *, RegSortData> RegUsesTy;
136 SmallVector<const SCEV *, 16> RegSequence;
139 void CountRegister(const SCEV *Reg, size_t LUIdx);
140 void DropRegister(const SCEV *Reg, size_t LUIdx);
143 bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
145 const SmallBitVector &getUsedByIndices(const SCEV *Reg) const;
149 typedef SmallVectorImpl<const SCEV *>::iterator iterator;
150 typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator;
160 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) {
171 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) {
196 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
207 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const {
230 SmallVector<const SCEV *, 2> BaseRegs;
234 const SCEV *ScaledReg;
243 void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE);
248 void DeleteBaseReg(const SCEV *&S);
250 bool referencesReg(const SCEV *S) const;
261 static void DoInitialMatch(const SCEV *S, Loop *L,
262 SmallVectorImpl<const SCEV *> &Good,
263 SmallVectorImpl<const SCEV *> &Bad,
286 AR->getLoop(), SCEV::FlagAnyWrap),
294 SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end());
295 const SCEV *NewMul = SE.getMulExpr(Ops);
297 SmallVector<const SCEV *, 4> MyGood;
298 SmallVector<const SCEV *, 4> MyBad;
300 const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue(
302 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(),
305 for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(),
319 void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) {
320 SmallVector<const SCEV *, 4> Good;
321 SmallVector<const SCEV *, 4> Bad;
324 const SCEV *Sum = SE.getAddExpr(Good);
330 const SCEV *Sum = SE.getAddExpr(Bad);
354 void Formula::DeleteBaseReg(const SCEV *&S) {
361 bool Formula::referencesReg(const SCEV *S) const {
373 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
390 for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
452 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
455 SCEV type.
486 const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
489 const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
494 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
495 return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
503 SmallVector<const SCEV *, 8> Ops;
506 const SCEV *Op = getExactSDiv(*I, RHS, SE,
519 SmallVector<const SCEV *, 4> Ops;
523 const SCEV *S = *I;
525 if (const SCEV *Q = getExactSDiv(S, RHS, SE,
542 /// return that integer value, and mutate S to point to a new SCEV with that
544 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) {
551 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
557 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
561 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
562 SCEV::FlagAnyWrap);
569 /// return that symbol, and mutate S to point to a new SCEV with that
571 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) {
578 SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
584 SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
588 // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
589 SCEV::FlagAnyWrap);
662 /// is tricky because SCEV doesn't track which expressions are actually computed
670 static bool isHighCostExpansion(const SCEV *S,
671 SmallPtrSet<const SCEV*, 8> &Processed,
798 SmallPtrSet<const SCEV *, 16> &Regs,
799 const DenseSet<const SCEV *> &VisitedRegs,
803 SmallPtrSet<const SCEV *, 16> *LoserRegs = 0);
809 void RateRegister(const SCEV *Reg,
810 SmallPtrSet<const SCEV *, 16> &Regs,
813 void RatePrimaryRegister(const SCEV *Reg,
814 SmallPtrSet<const SCEV *, 16> &Regs,
817 SmallPtrSet<const SCEV *, 16> *LoserRegs);
823 void Cost::RateRegister(const SCEV *Reg,
824 SmallPtrSet<const SCEV *, 16> &Regs,
871 void Cost::RatePrimaryRegister(const SCEV *Reg,
872 SmallPtrSet<const SCEV *, 16> &Regs,
875 SmallPtrSet<const SCEV *, 16> *LoserRegs) {
888 SmallPtrSet<const SCEV *, 16> &Regs,
889 const DenseSet<const SCEV *> &VisitedRegs,
893 SmallPtrSet<const SCEV *, 16> *LoserRegs) {
895 if (const SCEV *ScaledReg = F.ScaledReg) {
904 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
906 const SCEV *BaseReg = *I;
1069 /// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*.
1071 static SmallVector<const SCEV *, 2> getEmptyKey() {
1072 SmallVector<const SCEV *, 2> V;
1073 V.push_back(reinterpret_cast<const SCEV *>(-1));
1077 static SmallVector<const SCEV *, 2> getTombstoneKey() {
1078 SmallVector<const SCEV *, 2> V;
1079 V.push_back(reinterpret_cast<const SCEV *>(-2));
1083 static unsigned getHashValue(const SmallVector<const SCEV *, 2> &V) {
1085 for (SmallVectorImpl<const SCEV *>::const_iterator I = V.begin(),
1087 Result ^= DenseMapInfo<const SCEV *>::getHashValue(*I);
1091 static bool isEqual(const SmallVector<const SCEV *, 2> &LHS,
1092 const SmallVector<const SCEV *, 2> &RHS) {
1103 DenseSet<SmallVector<const SCEV *, 2>, UniquifierDenseMapInfo> Uniquifier;
1140 SmallPtrSet<const SCEV *, 4> Regs;
1162 SmallVector<const SCEV *, 2> Key = F.BaseRegs;
1172 SmallVector<const SCEV *, 2> Key = F.BaseRegs;
1184 for (SmallVectorImpl<const SCEV *>::const_iterator I =
1208 SmallPtrSet<const SCEV *, 4> OldRegs = Regs;
1218 for (SmallPtrSet<const SCEV *, 4>::iterator I = OldRegs.begin(),
1365 static bool isAlwaysFoldable(const SCEV *S,
1399 /// DenseMaps and DenseSets of pairs of const SCEV* and LSRUse::Kind.
1401 SCEV *, LSRUse::KindType> getEmptyKey() {
1402 return std::make_pair(reinterpret_cast<const SCEV *>(-1), LSRUse::Basic);
1405 static std::pair<const SCEV *, LSRUse::KindType> getTombstoneKey() {
1406 return std::make_pair(reinterpret_cast<const SCEV *>(-2), LSRUse::Basic);
1410 getHashValue(const std::pair<const SCEV *, LSRUse::KindType> &V) {
1411 unsigned Result = DenseMapInfo<const SCEV *>::getHashValue(V.first);
1416 static bool isEqual(const std::pair<const SCEV *, LSRUse::KindType> &LHS,
1417 const std::pair<const SCEV *, LSRUse::KindType> &RHS) {
1426 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
1434 const SCEV *IncExpr;
1436 IVInc(Instruction *U, Value *O, const SCEV *E):
1516 typedef DenseMap<std::pair<const SCEV *, LSRUse::KindType>,
1524 std::pair<size_t, int64_t> getUse(const SCEV *&Expr,
1532 void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1533 void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1563 const SmallPtrSet<const SCEV *, 16> &CurRegs,
1564 DenseSet<const SCEV *> &VisitedRegs) const;
1611 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1794 const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1797 const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1);
1800 const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount);
1827 const SCEV *MaxLHS = Max->getOperand(0);
1828 const SCEV *MaxRHS = Max->getOperand(1);
1838 const SCEV *IV = SE.getSCEV(Cond->getOperand(0));
1951 const SCEV *A = IU.getStride(*CondUse, L);
1952 const SCEV *B = IU.getStride(*UI, L);
2082 LSRInstance::getUse(const SCEV *&Expr,
2084 const SCEV *Copy = Expr;
2175 SmallSetVector<const SCEV *, 4> Strides;
2178 SmallVector<const SCEV *, 4> Worklist;
2180 const SCEV *Expr = IU.getExpr(*UI);
2188 const SCEV *S = Worklist.pop_back_val();
2200 for (SmallSetVector<const SCEV *, 4>::const_iterator
2202 for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
2204 const SCEV *OldStride = *I;
2205 const SCEV *NewStride = *NewStrideIter;
2274 /// getExprBase - Return an approximation of this SCEV expression's "base", or
2283 /// SCEVUnknown, we simply return the rightmost SCEV operand.
2284 static const SCEV *getExprBase(const SCEV *S) {
2303 const SCEV *SubExpr = *I;
2322 static const SCEV *
2329 // avoids creating extra SCEV expressions.
2330 const SCEV *OperExpr = SE.getSCEV(NextIV);
2331 const SCEV *PrevExpr = SE.getSCEV(PrevIV);
2335 const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
2347 const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Chain[0].IVOperand));
2352 SmallPtrSet<const SCEV*, 8> Processed;
2398 const SCEV *LastIncExpr = 0;
2454 const SCEV *LastIncExpr = 0;
2465 if (const SCEV *IncExpr =
2509 // We currently ignore intermediate values within SCEV expressions, assuming
2574 // Ignore users that are part of a SCEV expression. This way we only
2639 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst,
2693 const SCEV *LeftOverExpr = 0;
2707 const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy);
2715 const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc),
2785 const SCEV *S = IU.getExpr(*UI);
2806 const SCEV *N = SE.getSCEV(NV);
2849 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) {
2859 LSRInstance::InsertSupplementalFormula(const SCEV *S,
2873 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
2895 SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
2896 SmallPtrSet<const SCEV *, 8> Inserted;
2899 const SCEV *S = Worklist.pop_back_val();
2934 // Ignore uses which are part of other SCEV expressions, to avoid
2937 const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
2977 static void CollectSubexprs(const SCEV *S, const SCEVConstant *C,
2978 SmallVectorImpl<const SCEV *> &Ops,
2993 //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
2994 SCEV::FlagAnyWrap),
3024 const SCEV *BaseReg = Base.BaseRegs[i];
3026 SmallVector<const SCEV *, 8> AddOps;
3031 for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
3047 SmallVector<const SCEV *, 8> InnerAddOps
3048 (((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J);
3050 (llvm::next(J), ((const SmallVector<const SCEV *, 8> &)AddOps).end());
3060 const SCEV *InnerSum = SE.getAddExpr(InnerAddOps);
3104 SmallVector<const SCEV *, 4> Ops;
3105 for (SmallVectorImpl<const SCEV *>::const_iterator
3107 const SCEV *BaseReg = *I;
3115 const SCEV *Sum = SE.getAddExpr(Ops);
3133 const SCEV *G = Base.BaseRegs[i];
3158 const SCEV *G = Base.BaseRegs[i];
3167 const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), *I), G);
3238 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3308 const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3313 if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) {
3344 for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(),
3366 const SCEV *OrigReg;
3368 WorkItem(size_t LI, int64_t I, const SCEV *R)
3390 typedef std::map<int64_t, const SCEV *> ImmMapTy;
3391 typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy;
3393 DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap;
3394 SmallVector<const SCEV *, 8> Sequence;
3397 const SCEV *Reg = *I;
3412 for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(),
3414 const SCEV *Reg = *I;
3430 const SCEV *OrigReg = J->second;
3474 const SCEV *OrigReg = WI.OrigReg;
3477 const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm));
3513 const SCEV *BaseReg = F.BaseRegs[N];
3531 for (SmallVectorImpl<const SCEV *>::const_iterator
3591 DenseSet<const SCEV *> VisitedRegs;
3592 SmallPtrSet<const SCEV *, 16> Regs;
3593 SmallPtrSet<const SCEV *, 16> LoserRegs;
3600 typedef DenseMap<SmallVector<const SCEV *, 2>, size_t, UniquifierDenseMapInfo>
3635 SmallVector<const SCEV *, 2> Key;
3636 for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(),
3638 const SCEV *Reg = *J;
3733 for (SmallVectorImpl<const SCEV *>::const_iterator
3885 SmallPtrSet<const SCEV *, 4> Taken;
3893 const SCEV *Best = 0;
3897 const SCEV *Reg = *I;
3960 const SmallPtrSet<const SCEV *, 16> &CurRegs,
3961 DenseSet<const SCEV *> &VisitedRegs) const {
3978 SmallSetVector<const SCEV *, 4> ReqRegs;
3979 for (SmallPtrSet<const SCEV *, 16>::const_iterator I = CurRegs.begin(),
3984 SmallPtrSet<const SCEV *, 16> NewRegs;
3992 for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(),
3994 const SCEV *Reg = *J;
4023 for (SmallPtrSet<const SCEV *, 16>::const_iterator
4043 SmallPtrSet<const SCEV *, 16> CurRegs;
4044 DenseSet<const SCEV *> VisitedRegs;
4222 SmallVector<const SCEV *, 8> Ops;
4225 for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
4227 const SCEV *Reg = *I;
4249 const SCEV *ScaledS = F.ScaledReg;
4317 const SCEV *FullS = Ops.empty() ?
