diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/ScalarEvolution.h | 38 | ||||
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 326 |
2 files changed, 114 insertions, 250 deletions
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index b3c9eea2f9f..98a3fcf711f 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -891,13 +891,20 @@ namespace llvm { /// Compute the number of times the backedge of the specified loop will /// execute if its exit condition were a conditional branch of ExitCond, - /// TBB, and FBB. If AllowPredicates is set, this call will try to use a - /// minimal set of SCEV predicates in order to return an exact answer. + /// TBB, and FBB. + /// + /// \p ControlsExit is true if ExitCond directly controls the exit + /// branch. In this case, we can assume that the loop exits only if the + /// condition is true and can infer that failing to meet the condition prior + /// to integer wraparound results in undefined behavior. + /// + /// If \p AllowPredicates is set, this call will try to use a minimal set of + /// SCEV predicates in order to return an exact answer. ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, BasicBlock *TBB, BasicBlock *FBB, - bool IsSubExpr, + bool ControlsExit, bool AllowPredicates = false); /// Compute the number of times the backedge of the specified loop will @@ -960,11 +967,18 @@ namespace llvm { /// Return the number of times an exit condition containing the specified /// less-than comparison will execute. If not computable, return - /// CouldNotCompute. isSigned specifies whether the less-than is signed. - /// If AllowPredicates is set, this call will try to use a minimal set of + /// CouldNotCompute. + /// + /// \p isSigned specifies whether the less-than is signed. + /// + /// \p ControlsExit is true when the LHS < RHS condition directly controls + /// the branch (loops exits only if condition is true). In this case, we can + /// use NoWrapFlags to skip overflow checks. + /// + /// If \p AllowPredicates is set, this call will try to use a minimal set of /// SCEV predicates in order to return an exact answer. ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, - bool isSigned, bool IsSubExpr, + bool isSigned, bool ControlsExit, bool AllowPredicates = false); ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, @@ -1008,7 +1022,8 @@ namespace llvm { /// Test whether the condition described by Pred, LHS, and RHS is true /// whenever the condition described by Pred, FoundLHS, and FoundRHS is - /// true. Utility function used by isImpliedCondOperands. + /// true. Utility function used by isImpliedCondOperands. Tries to get + /// cases like "X `sgt` 0 => X - 1 `sgt` -1". bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const SCEV *FoundLHS, @@ -1505,7 +1520,8 @@ namespace llvm { const SCEV *getElementSize(Instruction *Inst); /// Compute the array dimensions Sizes from the set of Terms extracted from - /// the memory access function of this SCEVAddRecExpr. + /// the memory access function of this SCEVAddRecExpr (second step of + /// delinearization). void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize) const; @@ -1513,13 +1529,15 @@ namespace llvm { void print(raw_ostream &OS) const; void verify() const; - /// Collect parametric terms occurring in step expressions. + /// Collect parametric terms occurring in step expressions (first step of + /// delinearization). void collectParametricTerms(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Terms); - /// Return in Subscripts the access functions for each dimension in Sizes. + /// Return in Subscripts the access functions for each dimension in Sizes + /// (third step of delinearization). void computeAccessFunctions(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, SmallVectorImpl<const SCEV *> &Sizes); diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 60fbe9ac210..d76b0f30490 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -287,8 +287,6 @@ bool SCEV::isAllOnesValue() const { return false; } -/// isNonConstantNegative - Return true if the specified scev is negated, but -/// not a constant. bool SCEV::isNonConstantNegative() const { const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(this); if (!Mul) return false; @@ -624,10 +622,10 @@ public: }; } // end anonymous namespace -/// GroupByComplexity - Given a list of SCEV objects, order them by their -/// complexity, and group objects of the same complexity together by value. -/// When this routine is finished, we know that any duplicates in the vector are -/// consecutive and that complexity is monotonically increasing. +/// Given a list of SCEV objects, order them by their complexity, and group +/// objects of the same complexity together by value. When this routine is +/// finished, we know that any duplicates in the vector are consecutive and that +/// complexity is monotonically increasing. /// /// Note that we go take special precautions to ensure that we get deterministic /// results from this routine. In other words, we don't want the results of @@ -926,8 +924,7 @@ private: // Simple SCEV method implementations //===----------------------------------------------------------------------===// -/// BinomialCoefficient - Compute BC(It, K). The result has width W. -/// Assume, K > 0. +/// Compute BC(It, K). The result has width W. Assume, K > 0. static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, ScalarEvolution &SE, Type *ResultTy) { @@ -1038,10 +1035,10 @@ static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, SE.getTruncateOrZeroExtend(DivResult, ResultTy)); } -/// evaluateAtIteration - Return the value of this chain of recurrences at -/// the specified iteration number. We can evaluate this recurrence by -/// multiplying each element in the chain by the binomial coefficient -/// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: +/// Return the value of this chain of recurrences at the specified iteration +/// number. We can evaluate this recurrence by multiplying each element in the +/// chain by the binomial coefficient corresponding to it. In other words, we +/// can evaluate {A,+,B,+,C,+,D} as: /// /// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3) /// @@ -1877,11 +1874,10 @@ const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, return ZExt; } -/// CollectAddOperandsWithScales - Process the given Ops list, which is -/// a list of operands to be added under the given scale, update the given -/// map. This is a helper function for getAddRecExpr. As an example of -/// what it does, given a sequence of operands that would form an add -/// expression like this: +/// Process the given Ops list, which is a list of operands to be added under +/// the given scale, update the given map. This is a helper function for +/// getAddRecExpr. As an example of what it does, given a sequence of operands +/// that would form an add expression like this: /// /// m + n + 13 + (A * (o + p + (B * (q + m + 29)))) + r + (-1 * r) /// @@ -2022,8 +2018,7 @@ StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, return Flags; } -/// getAddExpr - Get a canonical add expression, or something simpler if -/// possible. +/// Get a canonical add expression, or something simpler if possible. const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, SCEV::NoWrapFlags Flags) { assert(!(Flags & ~(SCEV::FlagNUW | SCEV::FlagNSW)) && @@ -2434,8 +2429,7 @@ static bool containsConstantSomewhere(const SCEV *StartExpr) { return false; } -/// getMulExpr - Get a canonical multiply expression, or something simpler if -/// possible. +/// Get a canonical multiply expression, or something simpler if possible. const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, SCEV::NoWrapFlags Flags) { assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) && @@ -2675,8 +2669,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, return S; } -/// getUDivExpr - Get a canonical unsigned division expression, or something -/// simpler if possible. +/// Get a canonical unsigned division expression, or something simpler if +/// possible. const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, const SCEV *RHS) { assert(getEffectiveSCEVType(LHS->getType()) == @@ -2807,10 +2801,10 @@ static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) { return APIntOps::GreatestCommonDivisor(A, B); } -/// getUDivExactExpr - Get a canonical unsigned division expression, or -/// something simpler if possible. There is no representation for an exact udiv -/// in SCEV IR, but we can attempt to remove factors from the LHS and RHS. -/// We can't do this when it's not exact because the udiv may be clearing bits. +/// Get a canonical unsigned division expression, or something simpler if +/// possible. There is no representation for an exact udiv in SCEV IR, but we +/// can attempt to remove factors from the LHS and RHS. We can't do this when +/// it's not exact because the udiv may be clearing bits. const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS, const SCEV *RHS) { // TODO: we could try to find factors in all sorts of things, but for now we @@ -2864,8 +2858,8 @@ const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS, return getUDivExpr(LHS, RHS); } -/// getAddRecExpr - Get an add recurrence expression for the specified loop. -/// Simplify the expression as much as possible. +/// Get an add recurrence expression for the specified loop. Simplify the +/// expression as much as possible. const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags) { @@ -2881,8 +2875,8 @@ const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step, return getAddRecExpr(Operands, L, Flags); } -/// getAddRecExpr - Get an add recurrence expression for the specified loop. -/// Simplify the expression as much as possible. +/// Get an add recurrence expression for the specified loop. Simplify the +/// expression as much as possible. const SCEV * ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, const Loop *L, SCEV::NoWrapFlags Flags) { @@ -3287,26 +3281,25 @@ const SCEV *ScalarEvolution::getUnknown(Value *V) { // Basic SCEV Analysis and PHI Idiom Recognition Code // -/// isSCEVable - Test if values of the given type are analyzable within -/// the SCEV framework. This primarily includes integer types, and it -/// can optionally include pointer types if the ScalarEvolution class -/// has access to target-specific information. +/// Test if values of the given type are analyzable within the SCEV +/// framework. This primarily includes integer types, and it can optionally +/// include pointer types if the ScalarEvolution class has access to +/// target-specific information. bool ScalarEvolution::isSCEVable(Type *Ty) const { // Integers and pointers are always SCEVable. return Ty->isIntegerTy() || Ty->isPointerTy(); } -/// getTypeSizeInBits - Return the size in bits of the specified type, -/// for which isSCEVable must return true. +/// Return the size in bits of the specified type, for which isSCEVable must +/// return true. uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { assert(isSCEVable(Ty) && "Type is not SCEVable!"); return getDataLayout().getTypeSizeInBits(Ty); } -/// getEffectiveSCEVType - 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. +/// 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. Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { assert(isSCEVable(Ty) && "Type is not SCEVable!"); @@ -3389,7 +3382,7 @@ bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { return F.FoundOne; } -/// getSCEVValues - Return the Value set from S. +/// Return the Value set from S. SetVector<Value *> *ScalarEvolution::getSCEVValues(const SCEV *S) { ExprValueMapType::iterator SI = ExprValueMap.find_as(S); if (SI == ExprValueMap.end()) @@ -3404,10 +3397,10 @@ SetVector<Value *> *ScalarEvolution::getSCEVValues(const SCEV *S) { return &SI->second; } -/// eraseValueFromMap - Erase Value from ValueExprMap and ExprValueMap. -/// If ValueExprMap.erase(V) is not used together with forgetMemoizedResults(S), -/// eraseValueFromMap should be used instead to ensure whenever V->S is removed -/// from ValueExprMap, V is also removed from the set of ExprValueMap[S]. +/// Erase Value from ValueExprMap and ExprValueMap. If ValueExprMap.erase(V) is +/// not used together with forgetMemoizedResults(S), eraseValueFromMap should be +/// used instead to ensure whenever V->S is removed from ValueExprMap, V is also +/// removed from the set of ExprValueMap[S]. void ScalarEvolution::eraseValueFromMap(Value *V) { ValueExprMapType::iterator I = ValueExprMap.find_as(V); if (I != ValueExprMap.end()) { @@ -3420,8 +3413,8 @@ void ScalarEvolution::eraseValueFromMap(Value *V) { } } -/// getSCEV - Return an existing SCEV if it exists, otherwise analyze the -/// expression and create a new one. +/// Return an existing SCEV if it exists, otherwise analyze the expression and +/// create a new one. const SCEV *ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); @@ -3453,7 +3446,7 @@ const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { return nullptr; } -/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V +/// Return a SCEV corresponding to -V = -1*V /// const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags) { @@ -3467,7 +3460,7 @@ const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, V, getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))), Flags); } -/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V +/// Return a SCEV corresponding to ~V = -1-V const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) return getConstant( @@ -3480,7 +3473,6 @@ const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { return getMinusSCEV(AllOnes, V); } -/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags) { // Fast path: X - X --> 0. @@ -3519,9 +3511,6 @@ const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags); } -/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. If the type must be extended, it is zero -/// extended. const SCEV * ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); @@ -3535,9 +3524,6 @@ ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) { return getZeroExtendExpr(V, Ty); } -/// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. If the type must be extended, it is sign -/// extended. const SCEV * ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty) { @@ -3552,9 +3538,6 @@ ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, return getSignExtendExpr(V, Ty); } -/// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. If the type must be extended, it is zero -/// extended. The conversion must not be narrowing. const SCEV * ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); @@ -3568,9 +3551,6 @@ ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { return getZeroExtendExpr(V, Ty); } -/// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. If the type must be extended, it is sign -/// extended. The conversion must not be narrowing. const SCEV * ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); @@ -3584,10 +3564,6 @@ ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { return getSignExtendExpr(V, Ty); } -/// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of -/// the input value to the specified type. If the type must be extended, -/// it is extended with unspecified bits. The conversion must not be -/// narrowing. const SCEV * ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); @@ -3601,8 +3577,6 @@ ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { return getAnyExtendExpr(V, Ty); } -/// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the -/// input value to the specified type. The conversion must not be widening. const SCEV * ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { Type *SrcTy = V->getType(); @@ -3616,9 +3590,6 @@ ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { return getTruncateExpr(V, Ty); } -/// getUMaxFromMismatchedTypes - Promote the operands to the wider of -/// the types using zero-extension, and then perform a umax operation -/// with them. const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS) { const SCEV *PromotedLHS = LHS; @@ -3632,9 +3603,6 @@ const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, return getUMaxExpr(PromotedLHS, PromotedRHS); } -/// getUMinFromMismatchedTypes - Promote the operands to the wider of -/// the types using zero-extension, and then perform a umin operation -/// with them. const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS) { const SCEV *PromotedLHS = LHS; @@ -3648,10 +3616,6 @@ const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, return getUMinExpr(PromotedLHS, PromotedRHS); } -/// getPointerBase - Transitively follow the chain of pointer-type operands -/// until reaching a SCEV that does not have a single pointer operand. This -/// returns a SCEVUnknown pointer for well-formed pointer-type expressions, -/// but corner cases do exist. const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { // A pointer operand may evaluate to a nonpointer expression, such as null. if (!V->getType()->isPointerTy()) @@ -3676,8 +3640,7 @@ const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { return V; } -/// PushDefUseChildren - Push users of the given Instruction -/// onto the given Worklist. +/// Push users of the given Instruction onto the given Worklist. static void PushDefUseChildren(Instruction *I, SmallVectorImpl<Instruction *> &Worklist) { @@ -3686,10 +3649,6 @@ PushDefUseChildren(Instruction *I, Worklist.push_back(cast<Instruction>(U)); } -/// ForgetSymbolicValue - This looks up computed SCEV values for all -/// instructions that depend on the given instruction and removes them from -/// the ValueExprMapType map if they reference SymName. This is used during PHI -/// resolution. void ScalarEvolution::forgetSymbolicName(Instruction *PN, const SCEV *SymName) { SmallVector<Instruction *, 16> Worklist; PushDefUseChildren(PN, Worklist); @@ -4367,9 +4326,8 @@ const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Instruction *I, return getUnknown(I); } -/// createNodeForGEP - Expand GEP instructions into add and multiply -/// operations. This allows them to be analyzed by regular SCEV code. -/// +/// Expand GEP instructions into add and multiply operations. This allows them +/// to be analyzed by regular SCEV code. const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { // Don't attempt to analyze GEPs over unsized objects. if (!GEP->getSourceElementType()->isSized()) @@ -4383,10 +4341,6 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { IndexExprs, GEP->isInBounds()); } -/// GetMinTrailingZeros - Determine the minimum number of zero bits that S is -/// guaranteed to end in (at every loop iteration). It is, at the same time, -/// the minimum number of times S is divisible by 2. For example, given {4,+,8} -/// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. uint32_t ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) @@ -4464,8 +4418,7 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { return 0; } -/// GetRangeFromMetadata - Helper method to assign a range to V from -/// metadata present in the IR. +/// Helper method to assign a range to V from metadata present in the IR. static Optional<ConstantRange> GetRangeFromMetadata(Value *V) { if (Instruction *I = dyn_cast<Instruction>(V)) if (MDNode *MD = I->getMetadata(LLVMContext::MD_range)) @@ -4474,10 +4427,9 @@ static Optional<ConstantRange> GetRangeFromMetadata(Value *V) { return None; } -/// getRange - Determine the range for a particular SCEV. If SignHint is +/// Determine the range for a particular SCEV. If SignHint is /// HINT_RANGE_UNSIGNED (resp. HINT_RANGE_SIGNED) then getRange prefers ranges /// with a "cleaner" unsigned (resp. signed) representation. -/// ConstantRange ScalarEvolution::getRange(const SCEV *S, ScalarEvolution::RangeSignHint SignHint) { @@ -4976,9 +4928,6 @@ bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) { return !Itr->second; } -/// createSCEV - We know that there is no SCEV for the specified value. Analyze -/// the expression. -/// const SCEV *ScalarEvolution::createSCEV(Value *V) { if (!isSCEVable(V->getType())) return getUnknown(V); @@ -5300,16 +5249,6 @@ unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L) { return 0; } -/// getSmallConstantTripCount - Returns the maximum trip count of this loop as a -/// normal unsigned value. Returns 0 if the trip count is unknown or not -/// constant. Will also return 0 if the maximum trip count is very large (>= -/// 2^32). -/// -/// This "trip count" assumes that control exits via ExitingBlock. More -/// precisely, it is the number of times that control may reach ExitingBlock -/// before taking the branch. For loops with multiple exits, it may not be the -/// number times that the loop header executes because the loop may exit -/// prematurely via another branch. unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock) { assert(ExitingBlock && "Must pass a non-null exiting block!"); @@ -5338,10 +5277,10 @@ unsigned ScalarEvolution::getSmallConstantTripMultiple(Loop *L) { return 0; } -/// getSmallConstantTripMultiple - Returns the largest constant divisor of the -/// trip count of this loop as a normal unsigned value, if possible. This -/// means that the actual trip count is always a multiple of the returned -/// value (don't forget the trip count could very well be zero as well!). +/// Returns the largest constant divisor of the trip count of this loop as a +/// normal unsigned value, if possible. This means that the actual trip count is +/// always a multiple of the returned value (don't forget the trip count could +/// very well be zero as well!). /// /// Returns 1 if the trip count is unknown or not guaranteed to be the /// multiple of a constant (which is also the case if the trip count is simply @@ -5383,9 +5322,9 @@ ScalarEvolution::getSmallConstantTripMultiple(Loop *L, return (unsigned)Result->getZExtValue(); } -// getExitCount - Get the expression for the number of loop iterations for which -// this loop is guaranteed not to exit via ExitingBlock. Otherwise return -// SCEVCouldNotCompute. +/// 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(Loop *L, BasicBlock *ExitingBlock) { return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); } @@ -5396,30 +5335,17 @@ ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L, return getPredicatedBackedgeTakenInfo(L).getExact(this, &Preds); } -/// getBackedgeTakenCount - If the specified loop has a predictable -/// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute -/// object. The backedge-taken count is the number of times the loop header -/// will be branched to from within the loop. This is one less than the -/// trip count of the loop, since it doesn't count the first iteration, -/// when the header is branched to from outside the loop. -/// -/// Note that it is not valid to call this method on a loop without a -/// loop-invariant backedge-taken count (see -/// hasLoopInvariantBackedgeTakenCount). -/// const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) { return getBackedgeTakenInfo(L).getExact(this); } -/// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except -/// return the least SCEV value that is known never to be less than the -/// actual backedge taken count. +/// 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); } -/// PushLoopPHIs - Push PHI nodes in the header of the given loop -/// onto the given Worklist. +/// Push PHI nodes in the header of the given loop onto the given Worklist. static void PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) { BasicBlock *Header = L->getHeader(); @@ -5522,9 +5448,6 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { return BackedgeTakenCounts.find(L)->second = Result; } -/// forgetLoop - This method should be called by the client when it has -/// changed a loop in a way that may effect ScalarEvolution's ability to -/// compute a trip count, or if the loop is deleted. void ScalarEvolution::forgetLoop(const Loop *L) { // Drop any stored trip count value. auto RemoveLoopFromBackedgeMap = @@ -5569,9 +5492,6 @@ void ScalarEvolution::forgetLoop(const Loop *L) { LoopMayThrow.erase(L); } -/// forgetValue - This method should be called by the client when it has -/// changed a value in a way that may effect its value, or which may -/// disconnect it from a def-use chain linking it to a loop. void ScalarEvolution::forgetValue(Value *V) { Instruction *I = dyn_cast<Instruction>(V); if (!I) return; @@ -5599,13 +5519,13 @@ void ScalarEvolution::forgetValue(Value *V) { } } -/// getExact - Get the exact loop backedge taken count considering all loop -/// exits. A computable result can only be returned for loops with a single -/// exit. Returning the minimum taken count among all exits is incorrect -/// because one of the loop's exit limit's may have been skipped. howFarToZero -/// assumes that the limit of each loop test is never skipped. This is a valid -/// assumption as long as the loop exits via that test. For precise results, it -/// is the caller's responsibility to specify the relevant loop exit using +/// Get the exact loop backedge taken count considering all loop exits. A +/// computable result can only be returned for loops with a single exit. +/// Returning the minimum taken count among all exits is incorrect because one +/// of the loop's exit limit's may have been skipped. howFarToZero assumes that +/// the limit of each loop test is never skipped. This is a valid assumption as +/// long as the loop exits via that test. For precise results, it is the +/// caller's responsibility to specify the relevant loop exit using /// getExact(ExitingBlock, SE). const SCEV * ScalarEvolution::BackedgeTakenInfo::getExact( @@ -5636,7 +5556,7 @@ ScalarEvolution::BackedgeTakenInfo::getExact( return BECount; } -/// getExact - Get the exact not taken count for this loop exit. +/// Get the exact not taken count for this loop exit. const SCEV * ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const { @@ -5727,15 +5647,14 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( } } -/// clear - Invalidate this result and free the ExitNotTakenInfo array. +/// Invalidate this result and free the ExitNotTakenInfo array. void ScalarEvolution::BackedgeTakenInfo::clear() { ExitNotTaken.ExitingBlock = nullptr; ExitNotTaken.ExactNotTaken = nullptr; delete[] ExitNotTaken.ExtraInfo; } -/// computeBackedgeTakenCount - Compute the number of times the backedge -/// of the specified loop will execute. +/// Compute the number of times the backedge of the specified loop will execute. ScalarEvolution::BackedgeTakenInfo ScalarEvolution::computeBackedgeTakenCount(const Loop *L, bool AllowPredicates) { @@ -5877,14 +5796,6 @@ ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, return getCouldNotCompute(); } -/// computeExitLimitFromCond - Compute the number of times the -/// backedge of the specified loop will execute if its exit condition -/// were a conditional branch of ExitCond, TBB, and FBB. -/// -/// @param ControlsExit is true if ExitCond directly controls the exit -/// branch. In this case, we can assume that the loop exits only if the -/// condition is true and can infer that failing to meet the condition prior to -/// integer wraparound results in undefined behavior. ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond(const Loop *L, Value *ExitCond, @@ -6145,9 +6056,8 @@ EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, return cast<SCEVConstant>(Val)->getValue(); } -/// computeLoadConstantCompareExitLimit - Given an exit condition of -/// 'icmp op load X, cst', try to see if we can compute the backedge -/// execution count. +/// Given an exit condition of 'icmp op load X, cst', try to see if we can +/// compute the backedge execution count. ScalarEvolution::ExitLimit ScalarEvolution::computeLoadConstantCompareExitLimit( LoadInst *LI, @@ -6370,8 +6280,8 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit( return getCouldNotCompute(); } -/// CanConstantFold - Return true if we can constant fold an instruction of the -/// specified type, assuming that all operands were constants. +/// Return true if we can constant fold an instruction of the specified type, +/// assuming that all operands were constants. static bool CanConstantFold(const Instruction *I) { if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) || @@ -6689,16 +6599,6 @@ const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L, return getCouldNotCompute(); } -/// getSCEVAtScope - Return a SCEV expression for the specified value -/// at the specified scope in the program. The L value specifies a loop -/// nest to evaluate the expression at, where null is the top-level or a -/// specified loop is immediately inside of the loop. -/// -/// This method can be used to compute the exit value for a variable defined -/// in a loop by querying what the value will hold in the parent loop. -/// -/// In the case that a relevant loop exit value cannot be computed, the -/// original value V is returned. const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values = ValuesAtScopes[V]; @@ -7009,14 +6909,11 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { llvm_unreachable("Unknown SCEV type!"); } -/// getSCEVAtScope - This is a convenience function which does -/// getSCEVAtScope(getSCEV(V), L). const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { return getSCEVAtScope(getSCEV(V), L); } -/// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the -/// following equation: +/// Finds the minimum unsigned root of the following equation: /// /// A * X = B (mod N) /// @@ -7063,9 +6960,9 @@ static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B, return SE.getConstant(Result.trunc(BW)); } -/// SolveQuadraticEquation - Find the roots of the quadratic equation for the -/// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which -/// might be the same) or two SCEVCouldNotCompute objects. +/// Find the roots of the quadratic equation for the given quadratic chrec +/// {L,+,M,+,N}. This returns either the two roots (which might be the same) or +/// two SCEVCouldNotCompute objects. /// static std::pair<const SCEV *,const SCEV *> SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { @@ -7133,16 +7030,15 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { } // end APIntOps namespace } -/// howFarToZero - Return the number of times a backedge comparing the specified -/// value to zero will execute. If not computable, return CouldNotCompute. -/// -/// This is only used for loops with a "x != y" exit test. The exit condition is -/// now expressed as a single expression, V = x-y. So the exit test is -/// effectively V != 0. We know and take advantage of the fact that this -/// expression only being used in a comparison by zero context. ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, bool AllowPredicates) { + + // This is only used for loops with a "x != y" exit test. The exit condition + // is now expressed as a single expression, V = x-y. So the exit test is + // effectively V != 0. We know and take advantage of the fact that this + // expression only being used in a comparison by zero context. + SCEVUnionPredicate P; // If the value is a constant if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { @@ -7318,9 +7214,6 @@ ScalarEvolution::howFarToZero(const SCEV *V, const Loop *L, bool ControlsExit, return getCouldNotCompute(); } -/// howFarToNonZero - Return the number of times a backedge checking the -/// specified value for nonzero will execute. If not computable, return -/// CouldNotCompute ScalarEvolution::ExitLimit ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { // Loops that look like: while (X == 0) are very strange indeed. We don't @@ -7340,11 +7233,6 @@ ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { return getCouldNotCompute(); } -/// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB -/// (which may not be an immediate predecessor) which has exactly one -/// successor from which BB is reachable, or null if no such block is -/// found. -/// std::pair<BasicBlock *, BasicBlock *> ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { // If the block has a unique predecessor, then there is no path from the @@ -7362,11 +7250,10 @@ ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { return {nullptr, nullptr}; } -/// HasSameValue - SCEV structural equivalence is usually sufficient for -/// testing whether two expressions are equal, however for the purposes of -/// looking for a condition guarding a loop, it can be useful to be a little -/// more general, since a front-end may have replicated the controlling -/// expression. +/// SCEV structural equivalence is usually sufficient for testing whether two +/// expressions are equal, however for the purposes of looking for a condition +/// guarding a loop, it can be useful to be a little more general, since a +/// front-end may have replicated the controlling expression. /// static bool HasSameValue(const SCEV *A, const SCEV *B) { // Quick check to see if they are the same SCEV. @@ -7392,9 +7279,6 @@ static bool HasSameValue(const SCEV *A, const SCEV *B) { return false; } -/// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with -/// predicate Pred. Return true iff any changes were made. -/// bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth) { @@ -8090,9 +7974,6 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, return false; } -/// isLoopEntryGuardedByCond - Test whether entry to the loop is protected -/// by a conditional between LHS and RHS. This is used to help avoid max -/// expressions in loop trip counts, and to eliminate casts. bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, @@ -8162,8 +8043,6 @@ struct MarkPendingLoopPredicate { }; } // end anonymous namespace -/// isImpliedCond - Test whether the condition described by Pred, LHS, -/// and RHS is true whenever the given Cond value evaluates to true. bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, Value *FoundCondValue, @@ -8486,9 +8365,6 @@ bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow( getConstant(FoundRHSLimit)); } -/// isImpliedCondOperands - Test whether the condition described by Pred, -/// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, -/// and FoundRHS is true. bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const SCEV *FoundLHS, @@ -8613,9 +8489,6 @@ static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, llvm_unreachable("covered switch fell through?!"); } -/// isImpliedCondOperandsHelper - Test whether the condition described by -/// Pred, LHS, and RHS is true whenever the condition described by Pred, -/// FoundLHS, and FoundRHS is true. bool ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, @@ -8665,8 +8538,6 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, return false; } -/// isImpliedCondOperandsViaRanges - helper function for isImpliedCondOperands. -/// Tries to get cases like "X `sgt` 0 => X - 1 `sgt` -1". bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, @@ -8705,9 +8576,6 @@ bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, return SatisfyingLHSRange.contains(LHSRange); } -// Verify if an linear IV with positive stride can overflow when in a -// less-than comparison, knowing the invariant term of the comparison, the -// stride and the knowledge of NSW/NUW flags on the recurrence. bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, bool NoWrap) { if (NoWrap) return false; @@ -8734,9 +8602,6 @@ bool ScalarEvolution::doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, return (MaxValue - MaxStrideMinusOne).ult(MaxRHS); } -// Verify if an linear IV with negative stride can overflow when in a -// greater-than comparison, knowing the invariant term of the comparison, -// the stride and the knowledge of NSW/NUW flags on the recurrence. bool ScalarEvolution::doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, bool NoWrap) { if (NoWrap) return false; @@ -8763,8 +8628,6 @@ bool ScalarEvolution::doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, return (MinValue + MaxStrideMinusOne).ugt(MinRHS); } -// Compute the backedge taken count knowing the interval difference, the -// stride and presence of the equality in the comparison. const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta, const SCEV *Step, bool Equality) { const SCEV *One = getOne(Step->getType()); @@ -8773,13 +8636,6 @@ const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta, const SCEV *Step, return getUDivExpr(Delta, Step); } -/// howManyLessThans - Return the number of times a backedge containing the -/// specified less-than comparison will execute. If not computable, return -/// CouldNotCompute. -/// -/// @param ControlsExit is true when the LHS < RHS condition directly controls -/// the branch (loops exits only if condition is true). In this case, we can use -/// NoWrapFlags to skip overflow checks. ScalarEvolution::ExitLimit ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned, @@ -8954,11 +8810,6 @@ ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, return ExitLimit(BECount, MaxBECount, P); } -/// getNumIterationsInRange - Return the number of iterations of this loop that -/// produce values in the specified constant range. Another way of looking at -/// this is that it returns the first iteration number where the value is not in -/// the condition, thus computing the exit count. If the iteration count can't -/// be computed, an instance of SCEVCouldNotCompute is returned. const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, ScalarEvolution &SE) const { if (Range.isFullSet()) // Infinite loop. @@ -9377,12 +9228,9 @@ const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { return getSizeOfExpr(ETy, Ty); } -/// Second step of delinearization: compute the array dimensions Sizes from the -/// set of Terms extracted from the memory access function of this SCEVAddRec. void ScalarEvolution::findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, SmallVectorImpl<const SCEV *> &Sizes, const SCEV *ElementSize) const { - if (Terms.size() < 1 || !ElementSize) return; @@ -9446,8 +9294,6 @@ void ScalarEvolution::findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, }); } -/// Third step of delinearization: compute the access functions for the -/// Subscripts based on the dimensions in Sizes. void ScalarEvolution::computeAccessFunctions( const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, SmallVectorImpl<const SCEV *> &Sizes) { |
