diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1599,6 +1599,8 @@ /// We know that there is no SCEV for the specified value. Analyze the /// expression. const SCEV *createSCEV(Value *V); + const SCEV *createSCEVIter(Value *V); + void getOperandsToCreate(Value *V, SmallVectorImpl &Ops); /// Provide the special handling we need to analyze PHI SCEVs. const SCEV *createNodeForPHI(PHINode *PN); diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -3655,7 +3655,7 @@ const SCEV * ScalarEvolution::getGEPExpr(GEPOperator *GEP, const SmallVectorImpl &IndexExprs) { - const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); + const SCEV *BaseExpr = getExistingSCEV(GEP->getPointerOperand()); // getSCEV(Base)->getType() has the same address space as Base->getType() // because SCEV::getType() preserves the address space. Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType()); @@ -4339,33 +4339,9 @@ const SCEV *ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); - const SCEV *S = getExistingSCEV(V); - if (S == nullptr) { - S = createSCEV(V); - // During PHI resolution, it is possible to create two SCEVs for the same - // V, so it is needed to double check whether V->S is inserted into - // ValueExprMap before insert S->{V, 0} into ExprValueMap. - std::pair Pair = - ValueExprMap.insert({SCEVCallbackVH(V, this), S}); - if (Pair.second) { - ExprValueMap[S].insert({V, nullptr}); - - // If S == Stripped + Offset, add Stripped -> {V, Offset} into - // ExprValueMap. - const SCEV *Stripped = S; - ConstantInt *Offset = nullptr; - std::tie(Stripped, Offset) = splitAddExpr(S); - // If stripped is SCEVUnknown, don't bother to save - // Stripped -> {V, offset}. It doesn't simplify and sometimes even - // increase the complexity of the expansion code. - // If V is GetElementPtrInst, don't save Stripped -> {V, offset} - // because it may generate add/sub instead of GEP in SCEV expansion. - if (Offset != nullptr && !isa(Stripped) && - !isa(V)) - ExprValueMap[Stripped].insert({V, Offset}); - } - } - return S; + if (const SCEV *S = getExistingSCEV(V)) + return S; + return createSCEVIter(V); } const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { @@ -5522,10 +5498,13 @@ return nullptr; const SCEV *Accum = nullptr; - if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) - Accum = getSCEV(BO->RHS); - else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) - Accum = getSCEV(BO->LHS); + if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) { + Accum = getExistingSCEV(BO->RHS); + assert(Accum); + } else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) { + Accum = getExistingSCEV(BO->LHS); + assert(Accum); + } if (!Accum) return nullptr; @@ -5536,7 +5515,7 @@ if (BO->IsNSW) Flags = setFlags(Flags, SCEV::FlagNSW); - const SCEV *StartVal = getSCEV(StartValueV); + const SCEV *StartVal = getExistingSCEV(StartValueV); const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, Flags); insertValueToMap(PN, PHISCEV); @@ -5553,10 +5532,10 @@ return PHISCEV; } -const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { - const Loop *L = LI.getLoopFor(PN->getParent()); +static std::pair classifyPhiValues(PHINode *PN, + const Loop *L) { if (!L || L->getHeader() != PN->getParent()) - return nullptr; + return {nullptr, nullptr}; // The loop may have multiple entrances or multiple exits; we can analyze // this phi as an addrec if it has a unique entry value and a unique @@ -5578,6 +5557,13 @@ break; } } + return {StartValueV, BEValueV}; +} + +const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { + const Loop *L = LI.getLoopFor(PN->getParent()); + Value *BEValueV, *StartValueV; + std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L); if (!BEValueV || !StartValueV) return nullptr; @@ -5826,11 +5812,12 @@ return false; } -const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { +static BranchInst *getSelectPhiBr(PHINode *PN, const Loop *L, DominatorTree &DT, + LoopInfo &LI) { auto IsReachable = [&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); }; + if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) { - const Loop *L = LI.getLoopFor(PN->getParent()); // We don't want to break LCSSA, even in a SCEV expression tree. for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) @@ -5852,15 +5839,19 @@ BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock(); assert(IDom && "At least the entry block should dominate PN"); - auto *BI = dyn_cast(IDom->getTerminator()); - Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr; - - if (BI && BI->isConditional() && - BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) && - IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) && - IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent())) - return createNodeForSelectOrPHI(PN, Cond, LHS, RHS); + return dyn_cast(IDom->getTerminator()); } + return nullptr; +} + +const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { + const Loop *L = LI.getLoopFor(PN->getParent()); + BranchInst *BI = getSelectPhiBr(PN, L, DT, LI); + Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr; + if (BI && BI->isConditional() && BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) && + IsAvailableOnEntry(L, DT, getExistingSCEV(LHS), PN->getParent()) && + IsAvailableOnEntry(L, DT, getExistingSCEV(RHS), PN->getParent())) + return createNodeForSelectOrPHI(PN, Cond, LHS, RHS); return nullptr; } @@ -5891,7 +5882,7 @@ // Handle "constant" branch or select. This can occur for instance when a // loop pass transforms an inner loop and moves on to process the outer loop. if (auto *CI = dyn_cast(Cond)) - return getSCEV(CI->isOne() ? TrueVal : FalseVal); + return getExistingSCEV(CI->isOne() ? TrueVal : FalseVal); // Try to match some simple smax or umax patterns. auto *ICI = dyn_cast(Cond); @@ -5916,6 +5907,7 @@ // a > b ? b+x : a+x -> min(a, b)+x if (getTypeSizeInBits(LHS->getType()) <= getTypeSizeInBits(I->getType())) { bool Signed = ICI->isSigned(); + // TODO: Use getExistingSCEV! const SCEV *LA = getSCEV(TrueVal); const SCEV *RA = getSCEV(FalseVal); const SCEV *LS = getSCEV(LHS); @@ -6001,7 +5993,7 @@ SmallVector IndexExprs; for (Value *Index : GEP->indices()) - IndexExprs.push_back(getSCEV(Index)); + IndexExprs.push_back(getExistingSCEV(Index)); return getGEPExpr(GEP, IndexExprs); } @@ -7020,6 +7012,200 @@ return isMustProgress(L) && loopHasNoSideEffects(L); } +const SCEV *ScalarEvolution::createSCEVIter(Value *V) { + SmallVector> Stack; + SmallVector Worklist; + SmallPtrSet Visited; + + Stack.emplace_back(V, true); + Stack.emplace_back(V, false); + while (!Stack.empty()) { + std::pair E = Stack.pop_back_val(); + if (E.second) { + auto *S = getExistingSCEV(E.first); + if (!S) { + S = createSCEV(E.first); + // During PHI resolution, it is possible to create two SCEVs for the + // same V, so it is needed to double check whether V->S is inserted into + // ValueExprMap before insert S->{V, 0} into ExprValueMap. + std::pair Pair = + ValueExprMap.insert({SCEVCallbackVH(E.first, this), S}); + if (Pair.second) { + ExprValueMap[S].insert({E.first, nullptr}); + + // If S == Stripped + Offset, add Stripped -> {V, Offset} into + // ExprValueMap. + const SCEV *Stripped = S; + ConstantInt *Offset = nullptr; + std::tie(Stripped, Offset) = splitAddExpr(S); + // If stripped is SCEVUnknown, don't bother to save + // Stripped -> {V, offset}. It doesn't simplify and sometimes even + // increase the complexity of the expansion code. + // If V is GetElementPtrInst, don't save Stripped -> {V, offset} + // because it may generate add/sub instead of GEP in SCEV expansion. + if (Offset != nullptr && !isa(Stripped) && + !isa(E.first)) + ExprValueMap[Stripped].insert({E.first, Offset}); + } + } + } else { + if (!Visited.insert(E.first).second || getExistingSCEV(E.first)) + continue; + SmallVector Ops; + getOperandsToCreate(E.first, Ops); + Stack.emplace_back(E.first, true); + for (Value *Op : Ops) { + Stack.emplace_back(Op, false); + } + } + } + + return getExistingSCEV(V); +} +void ScalarEvolution::getOperandsToCreate(Value *V, + SmallVectorImpl &Ops) { + if (!isSCEVable(V->getType())) + return; + + if (Instruction *I = dyn_cast(V)) { + // Don't attempt to analyze instructions in blocks that aren't + // reachable. Such instructions don't matter, and they aren't required + // to obey basic rules for definitions dominating uses which this + // analysis depends on. + if (!DT.isReachableFromEntry(I->getParent())) + return; + } else if (ConstantInt *CI = dyn_cast(V)) + return; + else if (GlobalAlias *GA = dyn_cast(V)) { + if (!GA->isInterposable()) + Ops.push_back(GA->getAliasee()); + return; + } else if (!isa(V)) + return; + + Operator *U = cast(V); + if (auto BO = MatchBinaryOp(U, DT)) { + Ops.push_back(BO->LHS); + Ops.push_back(BO->RHS); + return; + } + + switch (U->getOpcode()) { + case Instruction::Trunc: + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::PtrToInt: + Ops.push_back(U->getOperand(0)); + return; + + case Instruction::BitCast: + if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) { + Ops.push_back(U->getOperand(0)); + return; + } + break; + + case Instruction::SDiv: + case Instruction::SRem: + Ops.push_back(U->getOperand(0)); + Ops.push_back(U->getOperand(1)); + return; + + case Instruction::GetElementPtr: + if (cast(U)->getSourceElementType()->isSized()) { + for (Value *Index : U->operands()) + Ops.push_back(Index); + } + return; + + case Instruction::IntToPtr: + return; + + case Instruction::PHI: { + auto *PN = cast(U); + const Loop *L = LI.getLoopFor(PN->getParent()); + Value *BEValueV, *StartValueV; + std::tie(StartValueV, BEValueV) = classifyPhiValues(PN, L); + + auto GetFoo = [&]() -> Value * { + if (!BEValueV || !StartValueV) + return nullptr; + auto BO = MatchBinaryOp(BEValueV, DT); + if (!BO) + return nullptr; + + if (BO->Opcode != Instruction::Add) + return nullptr; + + if (BO->LHS == PN && L->isLoopInvariant(BO->RHS)) + return BO->RHS; + else if (BO->RHS == PN && L->isLoopInvariant(BO->LHS)) + return BO->LHS; + return nullptr; + }; + + if (auto *Acc = GetFoo()) { + Ops.push_back(StartValueV); + Ops.push_back(Acc); + return; + } + BranchInst *BI = getSelectPhiBr(PN, L, DT, LI); + Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr; + if (BI && BI->isConditional() && + BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS)) { + Ops.push_back(LHS); + Ops.push_back(RHS); + return; + } + return; + } + + case Instruction::Select: + // U can also be a select constant expr, which let fall through. Since + // createNodeForSelect only works for a condition that is an `ICmpInst`, and + // constant expressions cannot have instructions as operands, we'd have + // returned getUnknown for a select constant expressions anyway. + if (isa(U)) { + for (Value *Inc : cast(U)->operands()) + Ops.push_back(Inc); + return; + } + break; + + case Instruction::Call: + case Instruction::Invoke: + if (Value *RV = cast(U)->getReturnedArgOperand()) { + Ops.push_back(RV); + return; + } + + if (auto *II = dyn_cast(U)) { + switch (II->getIntrinsicID()) { + case Intrinsic::abs: + Ops.push_back(II->getArgOperand(0)); + return; + case Intrinsic::umax: + case Intrinsic::umin: + case Intrinsic::smax: + case Intrinsic::smin: + case Intrinsic::usub_sat: + case Intrinsic::uadd_sat: + Ops.push_back(II->getArgOperand(0)); + Ops.push_back(II->getArgOperand(1)); + return; + case Intrinsic::start_loop_iterations: + Ops.push_back(II->getArgOperand(0)); + return; + default: + break; + } + } + break; + } + + return; +} + const SCEV *ScalarEvolution::createSCEV(Value *V) { if (!isSCEVable(V->getType())) return getUnknown(V); @@ -7034,7 +7220,8 @@ } else if (ConstantInt *CI = dyn_cast(V)) return getConstant(CI); else if (GlobalAlias *GA = dyn_cast(V)) - return GA->isInterposable() ? getUnknown(V) : getSCEV(GA->getAliasee()); + return GA->isInterposable() ? getUnknown(V) + : getExistingSCEV(GA->getAliasee()); else if (!isa(V)) return getUnknown(V); @@ -7063,10 +7250,10 @@ // since the flags are only known to apply to this particular // addition - they may not apply to other additions that can be // formed with operands from AddOps. - const SCEV *RHS = getSCEV(BO->RHS); + const SCEV *RHS = getExistingSCEV(BO->RHS); SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); if (Flags != SCEV::FlagAnyWrap) { - const SCEV *LHS = getSCEV(BO->LHS); + const SCEV *LHS = getExistingSCEV(BO->LHS); if (BO->Opcode == Instruction::Sub) AddOps.push_back(getMinusSCEV(LHS, RHS, Flags)); else @@ -7076,14 +7263,14 @@ } if (BO->Opcode == Instruction::Sub) - AddOps.push_back(getNegativeSCEV(getSCEV(BO->RHS))); + AddOps.push_back(getNegativeSCEV(getExistingSCEV(BO->RHS))); else - AddOps.push_back(getSCEV(BO->RHS)); + AddOps.push_back(getExistingSCEV(BO->RHS)); auto NewBO = MatchBinaryOp(BO->LHS, DT); if (!NewBO || (NewBO->Opcode != Instruction::Add && NewBO->Opcode != Instruction::Sub)) { - AddOps.push_back(getSCEV(BO->LHS)); + AddOps.push_back(getExistingSCEV(BO->LHS)); break; } BO = NewBO; @@ -7103,16 +7290,16 @@ SCEV::NoWrapFlags Flags = getNoWrapFlagsFromUB(BO->Op); if (Flags != SCEV::FlagAnyWrap) { - MulOps.push_back( - getMulExpr(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags)); + MulOps.push_back(getMulExpr(getExistingSCEV(BO->LHS), + getExistingSCEV(BO->RHS), Flags)); break; } } - MulOps.push_back(getSCEV(BO->RHS)); + MulOps.push_back(getExistingSCEV(BO->RHS)); auto NewBO = MatchBinaryOp(BO->LHS, DT); if (!NewBO || NewBO->Opcode != Instruction::Mul) { - MulOps.push_back(getSCEV(BO->LHS)); + MulOps.push_back(getExistingSCEV(BO->LHS)); break; } BO = NewBO; @@ -7121,23 +7308,24 @@ return getMulExpr(MulOps); } case Instruction::UDiv: - return getUDivExpr(getSCEV(BO->LHS), getSCEV(BO->RHS)); + return getUDivExpr(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS)); case Instruction::URem: - return getURemExpr(getSCEV(BO->LHS), getSCEV(BO->RHS)); + return getURemExpr(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS)); case Instruction::Sub: { SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap; if (BO->Op) Flags = getNoWrapFlagsFromUB(BO->Op); - return getMinusSCEV(getSCEV(BO->LHS), getSCEV(BO->RHS), Flags); + return getMinusSCEV(getExistingSCEV(BO->LHS), getExistingSCEV(BO->RHS), + Flags); } case Instruction::And: // For an expression like x&255 that merely masks off the high bits, // use zext(trunc(x)) as the SCEV expression. if (ConstantInt *CI = dyn_cast(BO->RHS)) { if (CI->isZero()) - return getSCEV(BO->RHS); + return getExistingSCEV(BO->RHS); if (CI->isMinusOne()) - return getSCEV(BO->LHS); + return getExistingSCEV(BO->LHS); const APInt &A = CI->getValue(); // Instcombine's ShrinkDemandedConstant may strip bits out of @@ -7155,7 +7343,7 @@ APInt::getLowBitsSet(BitWidth, BitWidth - LZ - TZ).shl(TZ); if ((LZ != 0 || TZ != 0) && !((~A & ~Known.Zero) & EffectiveMask)) { const SCEV *MulCount = getConstant(APInt::getOneBitSet(BitWidth, TZ)); - const SCEV *LHS = getSCEV(BO->LHS); + const SCEV *LHS = getExistingSCEV(BO->LHS); const SCEV *ShiftedLHS = nullptr; if (auto *LHSMul = dyn_cast(LHS)) { if (auto *OpC = dyn_cast(LHSMul->getOperand(0))) { @@ -7190,12 +7378,12 @@ // In order for this transformation to be safe, the LHS must be of the // form X*(2^n) and the Or constant must be less than 2^n. if (ConstantInt *CI = dyn_cast(BO->RHS)) { - const SCEV *LHS = getSCEV(BO->LHS); + const SCEV *LHS = getExistingSCEV(BO->LHS); const APInt &CIVal = CI->getValue(); if (GetMinTrailingZeros(LHS) >= (CIVal.getBitWidth() - CIVal.countLeadingZeros())) { // Build a plain add SCEV. - return getAddExpr(LHS, getSCEV(CI), + return getAddExpr(LHS, getExistingSCEV(CI), (SCEV::NoWrapFlags)(SCEV::FlagNUW | SCEV::FlagNSW)); } } @@ -7205,7 +7393,7 @@ if (ConstantInt *CI = dyn_cast(BO->RHS)) { // If the RHS of xor is -1, then this is a not operation. if (CI->isMinusOne()) - return getNotSCEV(getSCEV(BO->LHS)); + return getNotSCEV(getExistingSCEV(BO->LHS)); // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask. // This is a variant of the check for xor with -1, and it handles @@ -7216,7 +7404,7 @@ if (LBO->getOpcode() == Instruction::And && LCI->getValue() == CI->getValue()) if (const SCEVZeroExtendExpr *Z = - dyn_cast(getSCEV(BO->LHS))) { + dyn_cast(getExistingSCEV(BO->LHS))) { Type *UTy = BO->LHS->getType(); const SCEV *Z0 = Z->getOperand(); Type *Z0Ty = Z0->getType(); @@ -7266,9 +7454,9 @@ Flags = (SCEV::NoWrapFlags)(Flags | SCEV::FlagNUW); } - Constant *X = ConstantInt::get( + ConstantInt *X = ConstantInt::get( getContext(), APInt::getOneBitSet(BitWidth, SA->getZExtValue())); - return getMulExpr(getSCEV(BO->LHS), getSCEV(X), Flags); + return getMulExpr(getExistingSCEV(BO->LHS), getConstant(X), Flags); } break; @@ -7288,7 +7476,7 @@ break; if (CI->isZero()) - return getSCEV(BO->LHS); // shift by zero --> noop + return getExistingSCEV(BO->LHS); // shift by zero --> noop uint64_t AShrAmt = CI->getZExtValue(); Type *TruncTy = IntegerType::get(getContext(), BitWidth - AShrAmt); @@ -7299,7 +7487,7 @@ // Y = AShr X, m // Both n and m are constant. - const SCEV *ShlOp0SCEV = getSCEV(L->getOperand(0)); + const SCEV *ShlOp0SCEV = getExistingSCEV(L->getOperand(0)); if (L->getOperand(1) == BO->RHS) // For a two-shift sext-inreg, i.e. n = m, // use sext(trunc(x)) as the SCEV expression. @@ -7329,10 +7517,10 @@ switch (U->getOpcode()) { case Instruction::Trunc: - return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType()); + return getTruncateExpr(getExistingSCEV(U->getOperand(0)), U->getType()); case Instruction::ZExt: - return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType()); + return getZeroExtendExpr(getExistingSCEV(U->getOperand(0)), U->getType()); case Instruction::SExt: if (auto BO = MatchBinaryOp(U->getOperand(0), DT)) { @@ -7345,22 +7533,22 @@ // but by that point the NSW information has potentially been lost. if (BO->Opcode == Instruction::Sub && BO->IsNSW) { Type *Ty = U->getType(); - auto *V1 = getSignExtendExpr(getSCEV(BO->LHS), Ty); - auto *V2 = getSignExtendExpr(getSCEV(BO->RHS), Ty); + auto *V1 = getSignExtendExpr(getExistingSCEV(BO->LHS), Ty); + auto *V2 = getSignExtendExpr(getExistingSCEV(BO->RHS), Ty); return getMinusSCEV(V1, V2, SCEV::FlagNSW); } } - return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType()); + return getSignExtendExpr(getExistingSCEV(U->getOperand(0)), U->getType()); case Instruction::BitCast: // BitCasts are no-op casts so we just eliminate the cast. if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) - return getSCEV(U->getOperand(0)); + return getExistingSCEV(U->getOperand(0)); break; case Instruction::PtrToInt: { // Pointer to integer cast is straight-forward, so do model it. - const SCEV *Op = getSCEV(U->getOperand(0)); + const SCEV *Op = getExistingSCEV(U->getOperand(0)); Type *DstIntTy = U->getType(); // But only if effective SCEV (integer) type is wide enough to represent // all possible pointer values. @@ -7375,16 +7563,18 @@ case Instruction::SDiv: // If both operands are non-negative, this is just an udiv. - if (isKnownNonNegative(getSCEV(U->getOperand(0))) && - isKnownNonNegative(getSCEV(U->getOperand(1)))) - return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); + if (isKnownNonNegative(getExistingSCEV(U->getOperand(0))) && + isKnownNonNegative(getExistingSCEV(U->getOperand(1)))) + return getUDivExpr(getExistingSCEV(U->getOperand(0)), + getExistingSCEV(U->getOperand(1))); break; case Instruction::SRem: // If both operands are non-negative, this is just an urem. - if (isKnownNonNegative(getSCEV(U->getOperand(0))) && - isKnownNonNegative(getSCEV(U->getOperand(1)))) - return getURemExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); + if (isKnownNonNegative(getExistingSCEV(U->getOperand(0))) && + isKnownNonNegative(getExistingSCEV(U->getOperand(1)))) + return getURemExpr(getExistingSCEV(U->getOperand(0)), + getExistingSCEV(U->getOperand(1))); break; case Instruction::GetElementPtr: @@ -7406,42 +7596,42 @@ case Instruction::Call: case Instruction::Invoke: if (Value *RV = cast(U)->getReturnedArgOperand()) - return getSCEV(RV); + return getExistingSCEV(RV); if (auto *II = dyn_cast(U)) { switch (II->getIntrinsicID()) { case Intrinsic::abs: return getAbsExpr( - getSCEV(II->getArgOperand(0)), + getExistingSCEV(II->getArgOperand(0)), /*IsNSW=*/cast(II->getArgOperand(1))->isOne()); case Intrinsic::umax: - return getUMaxExpr(getSCEV(II->getArgOperand(0)), - getSCEV(II->getArgOperand(1))); + return getUMaxExpr(getExistingSCEV(II->getArgOperand(0)), + getExistingSCEV(II->getArgOperand(1))); case Intrinsic::umin: - return getUMinExpr(getSCEV(II->getArgOperand(0)), - getSCEV(II->getArgOperand(1))); + return getUMinExpr(getExistingSCEV(II->getArgOperand(0)), + getExistingSCEV(II->getArgOperand(1))); case Intrinsic::smax: - return getSMaxExpr(getSCEV(II->getArgOperand(0)), - getSCEV(II->getArgOperand(1))); + return getSMaxExpr(getExistingSCEV(II->getArgOperand(0)), + getExistingSCEV(II->getArgOperand(1))); case Intrinsic::smin: - return getSMinExpr(getSCEV(II->getArgOperand(0)), - getSCEV(II->getArgOperand(1))); + return getSMinExpr(getExistingSCEV(II->getArgOperand(0)), + getExistingSCEV(II->getArgOperand(1))); case Intrinsic::usub_sat: { - const SCEV *X = getSCEV(II->getArgOperand(0)); - const SCEV *Y = getSCEV(II->getArgOperand(1)); + const SCEV *X = getExistingSCEV(II->getArgOperand(0)); + const SCEV *Y = getExistingSCEV(II->getArgOperand(1)); const SCEV *ClampedY = getUMinExpr(X, Y); return getMinusSCEV(X, ClampedY, SCEV::FlagNUW); } case Intrinsic::uadd_sat: { - const SCEV *X = getSCEV(II->getArgOperand(0)); - const SCEV *Y = getSCEV(II->getArgOperand(1)); + const SCEV *X = getExistingSCEV(II->getArgOperand(0)); + const SCEV *Y = getExistingSCEV(II->getArgOperand(1)); const SCEV *ClampedX = getUMinExpr(X, getNotSCEV(Y)); return getAddExpr(ClampedX, Y, SCEV::FlagNUW); } case Intrinsic::start_loop_iterations: // A start_loop_iterations is just equivalent to the first operand for // SCEV purposes. - return getSCEV(II->getArgOperand(0)); + return getExistingSCEV(II->getArgOperand(0)); default: break; } @@ -7797,6 +7987,7 @@ } #endif // LLVM_ENABLE_STATS || !defined(NDEBUG) + SmallVector Recompute; // Now that we know more about the trip count for this loop, forget any // existing SCEV values for PHI nodes in this loop since they are only // conservative estimates made without the benefit of trip count @@ -7806,8 +7997,9 @@ // Invalidate any expression using an addrec in this loop. SmallVector ToForget; auto LoopUsersIt = LoopUsers.find(L); - if (LoopUsersIt != LoopUsers.end()) + if (LoopUsersIt != LoopUsers.end()) { append_range(ToForget, LoopUsersIt->second); + } forgetMemoizedResults(ToForget); // Invalidate constant-evolved loop header phis. @@ -7820,7 +8012,13 @@ // recusive call to getBackedgeTakenInfo (on a different // loop), which would invalidate the iterator computed // earlier. - return BackedgeTakenCounts.find(L)->second = std::move(Result); + auto R = BackedgeTakenCounts.find(L); + R->second = std::move(Result); + for (Value *V : Recompute) { + getSCEV(V); + } + + return BackedgeTakenCounts.find(L)->second; } void ScalarEvolution::forgetAllLoops() { diff --git a/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp b/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp --- a/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp +++ b/llvm/lib/Transforms/Scalar/StraightLineStrengthReduce.cpp @@ -546,6 +546,7 @@ // The base of this candidate is GEP's base plus the offsets of all // indices except this current one. + SE->getSCEV(GEP); const SCEV *BaseExpr = SE->getGEPExpr(cast(GEP), IndexExprs); Value *ArrayIdx = GEP->getOperand(I); uint64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());