namespace llvm {
class APInt;
+ class AssumptionCache;
class Constant;
class ConstantInt;
class DominatorTree;
class LoopInfo;
class Operator;
class SCEVUnknown;
+ class SCEVAddRecExpr;
class SCEV;
template<> struct FoldingSetTrait<SCEV>;
unsigned short SubclassData;
private:
- SCEV(const SCEV &) LLVM_DELETED_FUNCTION;
- void operator=(const SCEV &) LLVM_DELETED_FUNCTION;
+ SCEV(const SCEV &) = delete;
+ void operator=(const SCEV &) = delete;
public:
/// NoWrapFlags are bitfield indices into SubclassData.
/// operator. NSW is a misnomer that we use to mean no signed overflow or
/// underflow.
///
- /// AddRec expression may have a no-self-wraparound <NW> property if the
- /// result can never reach the start value. This property is independent of
- /// the actual start value and step direction. Self-wraparound is defined
- /// purely in terms of the recurrence's loop, step size, and
- /// bitwidth. Formally, a recurrence with no self-wraparound satisfies:
- /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth).
+ /// AddRec expressions may have a no-self-wraparound <NW> property if, in
+ /// the integer domain, abs(step) * max-iteration(loop) <=
+ /// unsigned-max(bitwidth). This means that the recurrence will never reach
+ /// its start value if the step is non-zero. Computing the same value on
+ /// each iteration is not considered wrapping, and recurrences with step = 0
+ /// are trivially <NW>. <NW> is independent of the sign of step and the
+ /// value the add recurrence starts with.
///
/// Note that NUW and NSW are also valid properties of a recurrence, and
/// either implies NW. For convenience, NW will be set for a recurrence
/// purposes.
void print(raw_ostream &OS) const;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
/// dump - This method is used for debugging.
///
void dump() const;
+#endif
};
// Specialize FoldingSetTrait for SCEV to avoid needing to compute
private:
/// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be
/// notified whenever a Value is deleted.
- class SCEVCallbackVH : public CallbackVH {
+ class SCEVCallbackVH final : public CallbackVH {
ScalarEvolution *SE;
void deleted() override;
void allUsesReplacedWith(Value *New) override;
///
Function *F;
+ /// The tracker for @llvm.assume intrinsics in this function.
+ AssumptionCache *AC;
+
/// LI - The loop information for the function we are currently analyzing.
///
LoopInfo *LI;
- /// The DataLayout information for the target we are targeting.
- ///
- const DataLayout *DL;
-
/// TLI - The target library information for the target we are targeting.
///
TargetLibraryInfo *TLI;
/// Mark predicate values currently being processed by isImpliedCond.
DenseSet<Value*> PendingLoopPredicates;
+ /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
+ /// conditions dominating the backedge of a loop.
+ bool WalkingBEDominatingConds;
+
/// ExitLimit - Information about the number of loop iterations for which a
/// loop exit's branch condition evaluates to the not-taken path. This is a
/// temporary pair of exact and max expressions that are eventually
/// summarized in ExitNotTakenInfo and BackedgeTakenInfo.
- ///
- /// If MustExit is true, then the exit must be taken when the BECount
- /// reaches Exact (and before surpassing Max). If MustExit is false, then
- /// BECount may exceed Exact or Max if the loop exits via another branch. In
- /// either case, the loop may exit early via another branch.
- ///
- /// MustExit is true for most cases. However, an exit guarded by an
- /// (in)equality on a nonunit stride may be skipped.
struct ExitLimit {
const SCEV *Exact;
const SCEV *Max;
- bool MustExit;
- /*implicit*/ ExitLimit(const SCEV *E)
- : Exact(E), Max(E), MustExit(true) {}
+ /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
- ExitLimit(const SCEV *E, const SCEV *M, bool MustExit)
- : Exact(E), Max(M), MustExit(MustExit) {}
+ ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
/// hasAnyInfo - Test whether this ExitLimit contains any computed
/// information, or whether it's all SCEVCouldNotCompute values.
/// LoopDispositions - Memoized computeLoopDisposition results.
DenseMap<const SCEV *,
- SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions;
+ SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
+ LoopDispositions;
/// computeLoopDisposition - Compute a LoopDisposition value.
LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
/// BlockDispositions - Memoized computeBlockDisposition results.
- DenseMap<const SCEV *,
- SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions;
+ DenseMap<
+ const SCEV *,
+ SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
+ BlockDispositions;
/// computeBlockDisposition - Compute a BlockDisposition value.
BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB);
- /// UnsignedRanges - Memoized results from getUnsignedRange
+ /// UnsignedRanges - Memoized results from getRange
DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
- /// SignedRanges - Memoized results from getSignedRange
+ /// SignedRanges - Memoized results from getRange
DenseMap<const SCEV *, ConstantRange> SignedRanges;
- /// setUnsignedRange - Set the memoized unsigned range for the given SCEV.
- const ConstantRange &setUnsignedRange(const SCEV *S,
- const ConstantRange &CR) {
- std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
- UnsignedRanges.insert(std::make_pair(S, CR));
- if (!Pair.second)
- Pair.first->second = CR;
- return Pair.first->second;
- }
+ /// RangeSignHint - Used to parameterize getRange
+ enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
+
+ /// setRange - Set the memoized range for the given SCEV.
+ const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint,
+ const ConstantRange &CR) {
+ DenseMap<const SCEV *, ConstantRange> &Cache =
+ Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
- /// setUnsignedRange - Set the memoized signed range for the given SCEV.
- const ConstantRange &setSignedRange(const SCEV *S,
- const ConstantRange &CR) {
std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair =
- SignedRanges.insert(std::make_pair(S, CR));
+ Cache.insert(std::make_pair(S, CR));
if (!Pair.second)
Pair.first->second = CR;
return Pair.first->second;
}
+ /// getRange - Determine the range for a particular SCEV.
+ ConstantRange getRange(const SCEV *S, RangeSignHint Hint);
+
/// createSCEV - We know that there is no SCEV for the specified value.
/// Analyze the expression.
const SCEV *createSCEV(Value *V);
const SCEV *FoundLHS,
const SCEV *FoundRHS);
+ /// isImpliedCondOperandsViaRanges - 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.
+ bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
+ const SCEV *LHS, const SCEV *RHS,
+ const SCEV *FoundLHS,
+ const SCEV *FoundRHS);
+
/// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
/// in the header of its containing loop, we know the loop executes a
/// constant number of times, and the PHI node is just a recurrence
/// forgetMemoizedResults - Drop memoized information computed for S.
void forgetMemoizedResults(const SCEV *S);
+ /// Return an existing SCEV for V if there is one, otherwise return nullptr.
+ const SCEV *getExistingSCEV(Value *V);
+
/// Return false iff given SCEV contains a SCEVUnknown with NULL value-
/// pointer.
bool checkValidity(const SCEV *S) const;
+ /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
+ /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is
+ /// equivalent to proving no signed (resp. unsigned) wrap in
+ /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
+ /// (resp. `SCEVZeroExtendExpr`).
+ ///
+ template<typename ExtendOpTy>
+ bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
+ const Loop *L);
+
+ bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS,
+ ICmpInst::Predicate Pred, bool &Increasing);
+
+ /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X"
+ /// is monotonically increasing or decreasing. In the former case set
+ /// `Increasing` to true and in the latter case set `Increasing` to false.
+ ///
+ /// A predicate is said to be monotonically increasing if may go from being
+ /// false to being true as the loop iterates, but never the other way
+ /// around. A predicate is said to be monotonically decreasing if may go
+ /// from being true to being false as the loop iterates, but never the other
+ /// way around.
+ bool isMonotonicPredicate(const SCEVAddRecExpr *LHS,
+ ICmpInst::Predicate Pred, bool &Increasing);
+
+ // Return SCEV no-wrap flags that can be proven based on reasoning
+ // about how poison produced from no-wrap flags on this value
+ // (e.g. a nuw add) would trigger undefined behavior on overflow.
+ SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V);
+
public:
static char ID; // Pass identification, replacement for typeid
ScalarEvolution();
SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());
return getAddRecExpr(NewOp, L, Flags);
}
+ /// \brief Returns an expression for a GEP
+ ///
+ /// \p PointeeType The type used as the basis for the pointer arithmetics
+ /// \p BaseExpr The expression for the pointer operand.
+ /// \p IndexExprs The expressions for the indices.
+ /// \p InBounds Whether the GEP is in bounds.
+ const SCEV *getGEPExpr(Type *PointeeType, const SCEV *BaseExpr,
+ const SmallVectorImpl<const SCEV *> &IndexExprs,
+ bool InBounds = false);
const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);
const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);
const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);
bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS);
+ /// \brief Returns the maximum trip count of the loop if it is a single-exit
+ /// loop and we can compute a small maximum for that loop.
+ ///
+ /// Implemented in terms of the \c getSmallConstantTripCount overload with
+ /// the single exiting block passed to it. See that routine for details.
+ unsigned getSmallConstantTripCount(Loop *L);
+
/// 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. This "trip count" assumes that control exits via
/// the loop exits prematurely via another branch.
unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock);
+ /// \brief Returns the largest constant divisor of the trip count of the
+ /// loop if it is a single-exit loop and we can compute a small maximum for
+ /// that loop.
+ ///
+ /// Implemented in terms of the \c getSmallConstantTripMultiple overload with
+ /// the single exiting block passed to it. See that routine for details.
+ unsigned getSmallConstantTripMultiple(Loop *L);
+
/// 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
/// 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.
+ /// compute a trip count, or if the loop is deleted. This call is
+ /// potentially expensive for large loop bodies.
void forgetLoop(const Loop *L);
/// forgetValue - This method should be called by the client when it has
/// getUnsignedRange - Determine the unsigned range for a particular SCEV.
///
- ConstantRange getUnsignedRange(const SCEV *S);
+ ConstantRange getUnsignedRange(const SCEV *S) {
+ return getRange(S, HINT_RANGE_UNSIGNED);
+ }
/// getSignedRange - Determine the signed range for a particular SCEV.
///
- ConstantRange getSignedRange(const SCEV *S);
+ ConstantRange getSignedRange(const SCEV *S) {
+ return getRange(S, HINT_RANGE_SIGNED);
+ }
/// isKnownNegative - Test if the given expression is known to be negative.
///
bool isKnownPredicate(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS);
+ /// Return true if the result of the predicate LHS `Pred` RHS is loop
+ /// invariant with respect to L. Set InvariantPred, InvariantLHS and
+ /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the
+ /// loop invariant form of LHS `Pred` RHS.
+ bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
+ const SCEV *RHS, const Loop *L,
+ ICmpInst::Predicate &InvariantPred,
+ const SCEV *&InvariantLHS,
+ const SCEV *&InvariantRHS);
+
/// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
/// predicate Pred. Return true iff any changes were made. If the
/// operands are provably equal or unequal, LHS and RHS are set to
/// indirect operand.
bool hasOperand(const SCEV *S, const SCEV *Op) const;
+ /// Return the size of an element read or written by Inst.
+ const SCEV *getElementSize(Instruction *Inst);
+
/// Compute the array dimensions Sizes from the set of Terms extracted from
/// the memory access function of this SCEVAddRecExpr.
void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms,
- SmallVectorImpl<const SCEV *> &Sizes) const;
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize) const;
bool runOnFunction(Function &F) override;
void releaseMemory() override;
void print(raw_ostream &OS, const Module* = nullptr) const override;
void verifyAnalysis() const override;
+ /// Collect parametric terms occurring in step expressions.
+ void collectParametricTerms(const SCEV *Expr,
+ SmallVectorImpl<const SCEV *> &Terms);
+
+
+
+ /// Return in Subscripts the access functions for each dimension in Sizes.
+ void computeAccessFunctions(const SCEV *Expr,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes);
+
+ /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the
+ /// subscripts and sizes of an array access.
+ ///
+ /// The delinearization is a 3 step process: the first two steps compute the
+ /// sizes of each subscript and the third step computes the access functions
+ /// for the delinearized array:
+ ///
+ /// 1. Find the terms in the step functions
+ /// 2. Compute the array size
+ /// 3. Compute the access function: divide the SCEV by the array size
+ /// starting with the innermost dimensions found in step 2. The Quotient
+ /// is the SCEV to be divided in the next step of the recursion. The
+ /// Remainder is the subscript of the innermost dimension. Loop over all
+ /// array dimensions computed in step 2.
+ ///
+ /// To compute a uniform array size for several memory accesses to the same
+ /// object, one can collect in step 1 all the step terms for all the memory
+ /// accesses, and compute in step 2 a unique array shape. This guarantees
+ /// that the array shape will be the same across all memory accesses.
+ ///
+ /// FIXME: We could derive the result of steps 1 and 2 from a description of
+ /// the array shape given in metadata.
+ ///
+ /// Example:
+ ///
+ /// A[][n][m]
+ ///
+ /// for i
+ /// for j
+ /// for k
+ /// A[j+k][2i][5i] =
+ ///
+ /// The initial SCEV:
+ ///
+ /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k]
+ ///
+ /// 1. Find the different terms in the step functions:
+ /// -> [2*m, 5, n*m, n*m]
+ ///
+ /// 2. Compute the array size: sort and unique them
+ /// -> [n*m, 2*m, 5]
+ /// find the GCD of all the terms = 1
+ /// divide by the GCD and erase constant terms
+ /// -> [n*m, 2*m]
+ /// GCD = m
+ /// divide by GCD -> [n, 2]
+ /// remove constant terms
+ /// -> [n]
+ /// size of the array is A[unknown][n][m]
+ ///
+ /// 3. Compute the access function
+ /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m
+ /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k
+ /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k
+ /// The remainder is the subscript of the innermost array dimension: [5i].
+ ///
+ /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n
+ /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k
+ /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k
+ /// The Remainder is the subscript of the next array dimension: [2i].
+ ///
+ /// The subscript of the outermost dimension is the Quotient: [j+k].
+ ///
+ /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
+ void delinearize(const SCEV *Expr,
+ SmallVectorImpl<const SCEV *> &Subscripts,
+ SmallVectorImpl<const SCEV *> &Sizes,
+ const SCEV *ElementSize);
+
private:
/// Compute the backedge taken count knowing the interval difference, the
/// stride and presence of the equality in the comparison.
projects / oota-llvm.git / blobdiff