#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/FoldingSet.h"
+#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
+#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
-#include "llvm/Support/ConstantRange.h"
#include "llvm/Support/DataTypes.h"
-#include "llvm/Support/ValueHandle.h"
#include <map>
namespace llvm {
class APInt;
+ class AssumptionCache;
class Constant;
class ConstantInt;
class DominatorTree;
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
/// notified whenever a Value is deleted.
class SCEVCallbackVH : public CallbackVH {
ScalarEvolution *SE;
- virtual void deleted();
- virtual void allUsesReplacedWith(Value *New);
+ void deleted() override;
+ void allUsesReplacedWith(Value *New) override;
public:
- SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0);
+ SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr);
};
friend class SCEVCallbackVH;
///
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.
///
- DataLayout *DL;
+ const DataLayout *DL;
/// TLI - The target library information for the target we are targeting.
///
/// 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.
const SCEV *ExactNotTaken;
PointerIntPair<ExitNotTakenInfo*, 1> NextExit;
- ExitNotTakenInfo() : ExitingBlock(0), ExactNotTaken(0) {}
+ ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {}
/// isCompleteList - Return true if all loop exits are computable.
bool isCompleteList() const {
const SCEV *Max;
public:
- BackedgeTakenInfo() : Max(0) {}
+ BackedgeTakenInfo() : Max(nullptr) {}
/// Initialize BackedgeTakenInfo from a list of exact exit counts.
BackedgeTakenInfo(
/// 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);
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
/// indirect operand.
bool hasOperand(const SCEV *S, const SCEV *Op) const;
- virtual bool runOnFunction(Function &F);
- virtual void releaseMemory();
- virtual void getAnalysisUsage(AnalysisUsage &AU) const;
- virtual void print(raw_ostream &OS, const Module* = 0) const;
- virtual void verifyAnalysis() 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 SCEV *ElementSize) const;
+
+ bool runOnFunction(Function &F) override;
+ void releaseMemory() override;
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
+ void print(raw_ostream &OS, const Module* = nullptr) const override;
+ void verifyAnalysis() const override;
private:
/// Compute the backedge taken count knowing the interval difference, the