diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp | 372 |
1 files changed, 258 insertions, 114 deletions
diff --git a/contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp b/contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp index bc2cfd6fcc42..26a9a5ddf1ea 100644 --- a/contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/contrib/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp @@ -112,6 +112,7 @@ #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/Verifier.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -148,6 +149,7 @@ STATISTIC(NumBruteForceTripCountsComputed, static cl::opt<unsigned> MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, + cl::ZeroOrMore, cl::desc("Maximum number of iterations SCEV will " "symbolically execute a constant " "derived loop"), @@ -157,6 +159,9 @@ MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, static cl::opt<bool> VerifySCEV( "verify-scev", cl::Hidden, cl::desc("Verify ScalarEvolution's backedge taken counts (slow)")); +static cl::opt<bool> VerifySCEVStrict( + "verify-scev-strict", cl::Hidden, + cl::desc("Enable stricter verification with -verify-scev is passed")); static cl::opt<bool> VerifySCEVMap("verify-scev-maps", cl::Hidden, cl::desc("Verify no dangling value in ScalarEvolution's " @@ -216,6 +221,12 @@ static cl::opt<unsigned> cl::desc("Size of the expression which is considered huge"), cl::init(4096)); +static cl::opt<bool> +ClassifyExpressions("scalar-evolution-classify-expressions", + cl::Hidden, cl::init(true), + cl::desc("When printing analysis, include information on every instruction")); + + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -1707,7 +1718,7 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { // in infinite recursion. In the later case, the analysis code will // cope with a conservative value, and it will take care to purge // that value once it has finished. - const SCEV *MaxBECount = getMaxBackedgeTakenCount(L); + const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); if (!isa<SCEVCouldNotCompute>(MaxBECount)) { // Manually compute the final value for AR, checking for // overflow. @@ -2051,7 +2062,7 @@ ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { // in infinite recursion. In the later case, the analysis code will // cope with a conservative value, and it will take care to purge // that value once it has finished. - const SCEV *MaxBECount = getMaxBackedgeTakenCount(L); + const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(L); if (!isa<SCEVCouldNotCompute>(MaxBECount)) { // Manually compute the final value for AR, checking for // overflow. @@ -3421,7 +3432,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, return getAddRecExpr(Operands, L, SCEV::FlagAnyWrap); // {X,+,0} --> X } - // It's tempting to want to call getMaxBackedgeTakenCount count here and + // It's tempting to want to call getConstantMaxBackedgeTakenCount count here and // use that information to infer NUW and NSW flags. However, computing a // BE count requires calling getAddRecExpr, so we may not yet have a // meaningful BE count at this point (and if we don't, we'd be stuck @@ -3484,7 +3495,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); // getSCEV(Base)->getType() has the same address space as Base->getType() // because SCEV::getType() preserves the address space. - Type *IntPtrTy = getEffectiveSCEVType(BaseExpr->getType()); + Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType()); // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP // instruction to its SCEV, because the Instruction may be guarded by control // flow and the no-overflow bits may not be valid for the expression in any @@ -3493,7 +3504,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap; - const SCEV *TotalOffset = getZero(IntPtrTy); + const SCEV *TotalOffset = getZero(IntIdxTy); // The array size is unimportant. The first thing we do on CurTy is getting // its element type. Type *CurTy = ArrayType::get(GEP->getSourceElementType(), 0); @@ -3503,7 +3514,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // For a struct, add the member offset. ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue(); unsigned FieldNo = Index->getZExtValue(); - const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo); + const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); // Add the field offset to the running total offset. TotalOffset = getAddExpr(TotalOffset, FieldOffset); @@ -3514,9 +3525,9 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // Update CurTy to its element type. CurTy = cast<SequentialType>(CurTy)->getElementType(); // For an array, add the element offset, explicitly scaled. - const SCEV *ElementSize = getSizeOfExpr(IntPtrTy, CurTy); + const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); // Getelementptr indices are signed. - IndexExpr = getTruncateOrSignExtend(IndexExpr, IntPtrTy); + IndexExpr = getTruncateOrSignExtend(IndexExpr, IntIdxTy); // Multiply the index by the element size to compute the element offset. const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap); @@ -3775,7 +3786,7 @@ uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { /// Return a type with the same bitwidth as the given type and which represents /// how SCEV will treat the given type, for which isSCEVable must return -/// true. For pointer types, this is the pointer-sized integer type. +/// true. For pointer types, this is the pointer index sized integer type. Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { assert(isSCEVable(Ty) && "Type is not SCEVable!"); @@ -3784,7 +3795,7 @@ Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { // The only other support type is pointer. assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!"); - return getDataLayout().getIntPtrType(Ty); + return getDataLayout().getIndexType(Ty); } Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const { @@ -4564,6 +4575,12 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { break; } + // Recognise intrinsic loop.decrement.reg, and as this has exactly the same + // semantics as a Sub, return a binary sub expression. + if (auto *II = dyn_cast<IntrinsicInst>(V)) + if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg) + return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1)); + return None; } @@ -4991,7 +5008,7 @@ const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN, // overflow. if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L)) - (void)getAddRecExpr(getAddExpr(StartVal, Accum, Flags), Accum, L, Flags); + (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags); return PHISCEV; } @@ -5549,6 +5566,7 @@ ScalarEvolution::getRangeRef(const SCEV *S, unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); + using OBO = OverflowingBinaryOperator; // If the value has known zeros, the maximum value will have those known zeros // as well. @@ -5566,8 +5584,14 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); + unsigned WrapType = OBO::AnyWrap; + if (Add->hasNoSignedWrap()) + WrapType |= OBO::NoSignedWrap; + if (Add->hasNoUnsignedWrap()) + WrapType |= OBO::NoUnsignedWrap; for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + WrapType, RangeType); return setRange(Add, SignHint, ConservativeResult.intersectWith(X, RangeType)); } @@ -5596,6 +5620,22 @@ ScalarEvolution::getRangeRef(const SCEV *S, ConservativeResult.intersectWith(X, RangeType)); } + if (const SCEVSMinExpr *SMin = dyn_cast<SCEVSMinExpr>(S)) { + ConstantRange X = getRangeRef(SMin->getOperand(0), SignHint); + for (unsigned i = 1, e = SMin->getNumOperands(); i != e; ++i) + X = X.smin(getRangeRef(SMin->getOperand(i), SignHint)); + return setRange(SMin, SignHint, + ConservativeResult.intersectWith(X, RangeType)); + } + + if (const SCEVUMinExpr *UMin = dyn_cast<SCEVUMinExpr>(S)) { + ConstantRange X = getRangeRef(UMin->getOperand(0), SignHint); + for (unsigned i = 1, e = UMin->getNumOperands(); i != e; ++i) + X = X.umin(getRangeRef(UMin->getOperand(i), SignHint)); + return setRange(UMin, SignHint, + ConservativeResult.intersectWith(X, RangeType)); + } + if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint); ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint); @@ -5627,34 +5667,43 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { // If there's no unsigned wrap, the value will never be less than its // initial value. - if (AddRec->hasNoUnsignedWrap()) - if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) - if (!C->getValue()->isZero()) - ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(C->getAPInt(), APInt(BitWidth, 0)), RangeType); - - // If there's no signed wrap, and all the operands have the same sign or - // zero, the value won't ever change sign. + if (AddRec->hasNoUnsignedWrap()) { + APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart()); + if (!UnsignedMinValue.isNullValue()) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(UnsignedMinValue, APInt(BitWidth, 0)), RangeType); + } + + // If there's no signed wrap, and all the operands except initial value have + // the same sign or zero, the value won't ever be: + // 1: smaller than initial value if operands are non negative, + // 2: bigger than initial value if operands are non positive. + // For both cases, value can not cross signed min/max boundary. if (AddRec->hasNoSignedWrap()) { bool AllNonNeg = true; bool AllNonPos = true; - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { - if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false; - if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false; + for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) { + if (!isKnownNonNegative(AddRec->getOperand(i))) + AllNonNeg = false; + if (!isKnownNonPositive(AddRec->getOperand(i))) + AllNonPos = false; } if (AllNonNeg) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt(BitWidth, 0), - APInt::getSignedMinValue(BitWidth)), RangeType); + ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()), + APInt::getSignedMinValue(BitWidth)), + RangeType); else if (AllNonPos) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt(BitWidth, 1)), RangeType); + ConstantRange::getNonEmpty( + APInt::getSignedMinValue(BitWidth), + getSignedRangeMax(AddRec->getStart()) + 1), + RangeType); } // TODO: non-affine addrec if (AddRec->isAffine()) { - const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop()); + const SCEV *MaxBECount = getConstantMaxBackedgeTakenCount(AddRec->getLoop()); if (!isa<SCEVCouldNotCompute>(MaxBECount) && getTypeSizeInBits(MaxBECount->getType()) <= BitWidth) { auto RangeFromAffine = getRangeForAffineAR( @@ -5690,14 +5739,26 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) { // For a SCEVUnknown, ask ValueTracking. KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT); - if (Known.One != ~Known.Zero + 1) - ConservativeResult = - ConservativeResult.intersectWith( - ConstantRange(Known.One, ~Known.Zero + 1), RangeType); + if (Known.getBitWidth() != BitWidth) + Known = Known.zextOrTrunc(BitWidth, true); + // If Known does not result in full-set, intersect with it. + if (Known.getMinValue() != Known.getMaxValue() + 1) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1), + RangeType); } else { assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED && "generalize as needed!"); unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT); + // If the pointer size is larger than the index size type, this can cause + // NS to be larger than BitWidth. So compensate for this. + if (U->getType()->isPointerTy()) { + unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType()); + int ptrIdxDiff = ptrSize - BitWidth; + if (ptrIdxDiff > 0 && ptrSize > BitWidth && NS > (unsigned)ptrIdxDiff) + NS -= ptrIdxDiff; + } + if (NS > 1) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), @@ -6523,7 +6584,7 @@ unsigned ScalarEvolution::getSmallConstantTripCount(const Loop *L, unsigned ScalarEvolution::getSmallConstantMaxTripCount(const Loop *L) { const auto *MaxExitCount = - dyn_cast<SCEVConstant>(getMaxBackedgeTakenCount(L)); + dyn_cast<SCEVConstant>(getConstantMaxBackedgeTakenCount(L)); return getConstantTripCount(MaxExitCount); } @@ -6579,12 +6640,16 @@ ScalarEvolution::getSmallConstantTripMultiple(const Loop *L, return (unsigned)Result->getZExtValue(); } -/// Get the expression for the number of loop iterations for which this loop is -/// guaranteed not to exit via ExitingBlock. Otherwise return -/// SCEVCouldNotCompute. const SCEV *ScalarEvolution::getExitCount(const Loop *L, - BasicBlock *ExitingBlock) { - return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + BasicBlock *ExitingBlock, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(ExitingBlock, this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } const SCEV * @@ -6593,14 +6658,15 @@ ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L, return getPredicatedBackedgeTakenInfo(L).getExact(L, this, &Preds); } -const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getExact(L, this); -} - -/// Similar to getBackedgeTakenCount, except return the least SCEV value that is -/// known never to be less than the actual backedge taken count. -const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getMax(this); +const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(L, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { @@ -6909,6 +6975,16 @@ ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock, return SE->getCouldNotCompute(); } +const SCEV * +ScalarEvolution::BackedgeTakenInfo::getMax(BasicBlock *ExitingBlock, + ScalarEvolution *SE) const { + for (auto &ENT : ExitNotTaken) + if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate()) + return ENT.MaxNotTaken; + + return SE->getCouldNotCompute(); +} + /// getMax - Get the max backedge taken count for the loop. const SCEV * ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { @@ -7000,13 +7076,15 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( BasicBlock *ExitBB = EEI.first; const ExitLimit &EL = EEI.second; if (EL.Predicates.empty()) - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, nullptr); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + nullptr); std::unique_ptr<SCEVUnionPredicate> Predicate(new SCEVUnionPredicate); for (auto *Pred : EL.Predicates) Predicate->add(Pred); - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + std::move(Predicate)); }); assert((isa<SCEVCouldNotCompute>(MaxCount) || isa<SCEVConstant>(MaxCount)) && "No point in having a non-constant max backedge taken count!"); @@ -7038,6 +7116,17 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L, // Do a union of all the predicates here. for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { BasicBlock *ExitBB = ExitingBlocks[i]; + + // We canonicalize untaken exits to br (constant), ignore them so that + // proving an exit untaken doesn't negatively impact our ability to reason + // about the loop as whole. + if (auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator())) + if (auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) { + bool ExitIfTrue = !L->contains(BI->getSuccessor(0)); + if ((ExitIfTrue && CI->isZero()) || (!ExitIfTrue && CI->isOne())) + continue; + } + ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates); assert((AllowPredicates || EL.Predicates.empty()) && @@ -7197,6 +7286,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "and i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isOne() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isOne() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -7245,6 +7339,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "or i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isZero() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isZero() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -9833,6 +9932,10 @@ Optional<APInt> ScalarEvolution::computeConstantDifference(const SCEV *More, // We avoid subtracting expressions here because this function is usually // fairly deep in the call stack (i.e. is called many times). + // X - X = 0. + if (More == Less) + return APInt(getTypeSizeInBits(More->getType()), 0); + if (isa<SCEVAddRecExpr>(Less) && isa<SCEVAddRecExpr>(More)) { const auto *LAR = cast<SCEVAddRecExpr>(Less); const auto *MAR = cast<SCEVAddRecExpr>(More); @@ -10314,10 +10417,43 @@ bool ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred, return false; } +static bool isKnownPredicateExtendIdiom(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS) { + // zext x u<= sext x, sext x s<= zext x + switch (Pred) { + case ICmpInst::ICMP_SGE: + std::swap(LHS, RHS); + LLVM_FALLTHROUGH; + case ICmpInst::ICMP_SLE: { + // If operand >=s 0 then ZExt == SExt. If operand <s 0 then SExt <s ZExt. + const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(LHS); + const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(RHS); + if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand()) + return true; + break; + } + case ICmpInst::ICMP_UGE: + std::swap(LHS, RHS); + LLVM_FALLTHROUGH; + case ICmpInst::ICMP_ULE: { + // If operand >=s 0 then ZExt == SExt. If operand <s 0 then ZExt <u SExt. + const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS); + const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(RHS); + if (SExt && ZExt && SExt->getOperand() == ZExt->getOperand()) + return true; + break; + } + default: + break; + }; + return false; +} + bool ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { - return isKnownPredicateViaConstantRanges(Pred, LHS, RHS) || + return isKnownPredicateExtendIdiom(Pred, LHS, RHS) || + isKnownPredicateViaConstantRanges(Pred, LHS, RHS) || IsKnownPredicateViaMinOrMax(*this, Pred, LHS, RHS) || IsKnownPredicateViaAddRecStart(*this, Pred, LHS, RHS) || isKnownPredicateViaNoOverflow(Pred, LHS, RHS); @@ -10919,7 +11055,7 @@ struct SCEVCollectAddRecMultiplies { } else if (Unknown) { HasAddRec = true; } else { - bool ContainsAddRec; + bool ContainsAddRec = false; SCEVHasAddRec ContiansAddRec(ContainsAddRec); visitAll(Op, ContiansAddRec); HasAddRec |= ContainsAddRec; @@ -11434,8 +11570,8 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, L->getHeader()->printAsOperand(OS, /*PrintType=*/false); OS << ": "; - if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) { - OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L); + if (!isa<SCEVCouldNotCompute>(SE->getConstantMaxBackedgeTakenCount(L))) { + OS << "max backedge-taken count is " << *SE->getConstantMaxBackedgeTakenCount(L); if (SE->isBackedgeTakenCountMaxOrZero(L)) OS << ", actual taken count either this or zero."; } else { @@ -11487,77 +11623,79 @@ void ScalarEvolution::print(raw_ostream &OS) const { // const isn't dangerous. ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this); - OS << "Classifying expressions for: "; - F.printAsOperand(OS, /*PrintType=*/false); - OS << "\n"; - for (Instruction &I : instructions(F)) - if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { - OS << I << '\n'; - OS << " --> "; - const SCEV *SV = SE.getSCEV(&I); - SV->print(OS); - if (!isa<SCEVCouldNotCompute>(SV)) { - OS << " U: "; - SE.getUnsignedRange(SV).print(OS); - OS << " S: "; - SE.getSignedRange(SV).print(OS); - } - - const Loop *L = LI.getLoopFor(I.getParent()); - - const SCEV *AtUse = SE.getSCEVAtScope(SV, L); - if (AtUse != SV) { + if (ClassifyExpressions) { + OS << "Classifying expressions for: "; + F.printAsOperand(OS, /*PrintType=*/false); + OS << "\n"; + for (Instruction &I : instructions(F)) + if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { + OS << I << '\n'; OS << " --> "; - AtUse->print(OS); - if (!isa<SCEVCouldNotCompute>(AtUse)) { + const SCEV *SV = SE.getSCEV(&I); + SV->print(OS); + if (!isa<SCEVCouldNotCompute>(SV)) { OS << " U: "; - SE.getUnsignedRange(AtUse).print(OS); + SE.getUnsignedRange(SV).print(OS); OS << " S: "; - SE.getSignedRange(AtUse).print(OS); + SE.getSignedRange(SV).print(OS); } - } - if (L) { - OS << "\t\t" "Exits: "; - const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); - if (!SE.isLoopInvariant(ExitValue, L)) { - OS << "<<Unknown>>"; - } else { - OS << *ExitValue; + const Loop *L = LI.getLoopFor(I.getParent()); + + const SCEV *AtUse = SE.getSCEVAtScope(SV, L); + if (AtUse != SV) { + OS << " --> "; + AtUse->print(OS); + if (!isa<SCEVCouldNotCompute>(AtUse)) { + OS << " U: "; + SE.getUnsignedRange(AtUse).print(OS); + OS << " S: "; + SE.getSignedRange(AtUse).print(OS); + } } - bool First = true; - for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; + if (L) { + OS << "\t\t" "Exits: "; + const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); + if (!SE.isLoopInvariant(ExitValue, L)) { + OS << "<<Unknown>>"; } else { - OS << ", "; + OS << *ExitValue; } - Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); - } + bool First = true; + for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } - for (auto *InnerL : depth_first(L)) { - if (InnerL == L) - continue; - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; - } else { - OS << ", "; + Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); + } + + for (auto *InnerL : depth_first(L)) { + if (InnerL == L) + continue; + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } + + InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); } - InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + OS << " }"; } - OS << " }"; + OS << "\n"; } - - OS << "\n"; - } + } OS << "Determining loop execution counts for: "; F.printAsOperand(OS, /*PrintType=*/false); @@ -11901,14 +12039,14 @@ void ScalarEvolution::verify() const { SE.getTypeSizeInBits(NewBECount->getType())) CurBECount = SE2.getZeroExtendExpr(CurBECount, NewBECount->getType()); - auto *ConstantDelta = - dyn_cast<SCEVConstant>(SE2.getMinusSCEV(CurBECount, NewBECount)); + const SCEV *Delta = SE2.getMinusSCEV(CurBECount, NewBECount); - if (ConstantDelta && ConstantDelta->getAPInt() != 0) { - dbgs() << "Trip Count Changed!\n"; + // Unless VerifySCEVStrict is set, we only compare constant deltas. + if ((VerifySCEVStrict || isa<SCEVConstant>(Delta)) && !Delta->isZero()) { + dbgs() << "Trip Count for " << *L << " Changed!\n"; dbgs() << "Old: " << *CurBECount << "\n"; dbgs() << "New: " << *NewBECount << "\n"; - dbgs() << "Delta: " << *ConstantDelta << "\n"; + dbgs() << "Delta: " << *Delta << "\n"; std::abort(); } } @@ -11937,6 +12075,12 @@ ScalarEvolution ScalarEvolutionAnalysis::run(Function &F, } PreservedAnalyses +ScalarEvolutionVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { + AM.getResult<ScalarEvolutionAnalysis>(F).verify(); + return PreservedAnalyses::all(); +} + +PreservedAnalyses ScalarEvolutionPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { AM.getResult<ScalarEvolutionAnalysis>(F).print(OS); return PreservedAnalyses::all(); @@ -11959,7 +12103,7 @@ ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass() : FunctionPass(ID) { bool ScalarEvolutionWrapperPass::runOnFunction(Function &F) { SE.reset(new ScalarEvolution( - F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(), + F, getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F), getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F), getAnalysis<DominatorTreeWrapperPass>().getDomTree(), getAnalysis<LoopInfoWrapperPass>().getLoopInfo())); @@ -12405,7 +12549,7 @@ PredicatedScalarEvolution::PredicatedScalarEvolution( const PredicatedScalarEvolution &Init) : RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), Preds(Init.Preds), Generation(Init.Generation), BackedgeCount(Init.BackedgeCount) { - for (const auto &I : Init.FlagsMap) + for (auto I : Init.FlagsMap) FlagsMap.insert(I); } |