#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;
- /// TD - The target data information for the target we are targeting.
+ /// The DataLayout information for the target we are targeting.
///
- DataLayout *TD;
+ const DataLayout *DL;
/// TLI - The target library information for the target we are targeting.
///
/// Mark predicate values currently being processed by isImpliedCond.
DenseSet<Value*> PendingLoopPredicates;
- /// 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.
+ /// 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.
struct ExitLimit {
const SCEV *Exact;
const SCEV *Max;
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);
BasicBlock *FBB,
bool IsSubExpr);
+ /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the
+ /// backedge of the specified loop will execute if its exit condition were a
+ /// switch with a single exiting case to ExitingBB.
+ ExitLimit
+ ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch,
+ BasicBlock *ExitingBB, bool IsSubExpr);
+
/// ComputeLoadConstantCompareExitLimit - Given an exit condition
/// of 'icmp op load X, cst', try to see if we can compute the
/// backedge-taken count.
return getMulExpr(Ops, Flags);
}
const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
+ const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step,
const Loop *L, SCEV::NoWrapFlags Flags);
const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
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
/// disconnect it from a def-use chain linking it to a loop.
void forgetValue(Value *V);
+ /// \brief Called when the client has changed the disposition of values in
+ /// this loop.
+ ///
+ /// We don't have a way to invalidate per-loop dispositions. Clear and
+ /// recompute is simpler.
+ void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
+
/// 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,
/// 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
const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
bool Equality);
- /// Verify if an linear IV with positive stride can overflow when in a
+ /// 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 doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
bool IsSigned, bool NoWrap);
- /// Verify if an linear IV with negative stride can overflow when in a
+ /// 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 doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,