#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#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"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/SaveAndRestore.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <tuple>
#include <utility>
#include <vector>
usingnamespacellvm;
usingnamespacePatternMatch;
#define DEBUG_TYPE …
STATISTIC(NumExitCountsComputed,
"Number of loop exits with predictable exit counts");
STATISTIC(NumExitCountsNotComputed,
"Number of loop exits without predictable exit counts");
STATISTIC(NumBruteForceTripCountsComputed,
"Number of loops with trip counts computed by force");
#ifdef EXPENSIVE_CHECKS
bool llvm::VerifySCEV = true;
#else
bool llvm::VerifySCEV = …;
#endif
static cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
cl::desc("Maximum number of iterations SCEV will "
"symbolically execute a constant "
"derived loop"),
cl::init(100));
static cl::opt<bool, true> VerifySCEVOpt(
"verify-scev", cl::Hidden, cl::location(VerifySCEV),
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> VerifyIR(
"scev-verify-ir", cl::Hidden,
cl::desc("Verify IR correctness when making sensitive SCEV queries (slow)"),
cl::init(false));
static cl::opt<unsigned> MulOpsInlineThreshold(
"scev-mulops-inline-threshold", cl::Hidden,
cl::desc("Threshold for inlining multiplication operands into a SCEV"),
cl::init(32));
static cl::opt<unsigned> AddOpsInlineThreshold(
"scev-addops-inline-threshold", cl::Hidden,
cl::desc("Threshold for inlining addition operands into a SCEV"),
cl::init(500));
static cl::opt<unsigned> MaxSCEVCompareDepth(
"scalar-evolution-max-scev-compare-depth", cl::Hidden,
cl::desc("Maximum depth of recursive SCEV complexity comparisons"),
cl::init(32));
static cl::opt<unsigned> MaxSCEVOperationsImplicationDepth(
"scalar-evolution-max-scev-operations-implication-depth", cl::Hidden,
cl::desc("Maximum depth of recursive SCEV operations implication analysis"),
cl::init(2));
static cl::opt<unsigned> MaxValueCompareDepth(
"scalar-evolution-max-value-compare-depth", cl::Hidden,
cl::desc("Maximum depth of recursive value complexity comparisons"),
cl::init(2));
static cl::opt<unsigned>
MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden,
cl::desc("Maximum depth of recursive arithmetics"),
cl::init(32));
static cl::opt<unsigned> MaxConstantEvolvingDepth(
"scalar-evolution-max-constant-evolving-depth", cl::Hidden,
cl::desc("Maximum depth of recursive constant evolving"), cl::init(32));
static cl::opt<unsigned>
MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden,
cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"),
cl::init(8));
static cl::opt<unsigned>
MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden,
cl::desc("Max coefficients in AddRec during evolving"),
cl::init(8));
static cl::opt<unsigned>
HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden,
cl::desc("Size of the expression which is considered huge"),
cl::init(4096));
static cl::opt<unsigned> RangeIterThreshold(
"scev-range-iter-threshold", cl::Hidden,
cl::desc("Threshold for switching to iteratively computing SCEV ranges"),
cl::init(32));
static cl::opt<bool>
ClassifyExpressions("scalar-evolution-classify-expressions",
cl::Hidden, cl::init(true),
cl::desc("When printing analysis, include information on every instruction"));
static cl::opt<bool> UseExpensiveRangeSharpening(
"scalar-evolution-use-expensive-range-sharpening", cl::Hidden,
cl::init(false),
cl::desc("Use more powerful methods of sharpening expression ranges. May "
"be costly in terms of compile time"));
static cl::opt<unsigned> MaxPhiSCCAnalysisSize(
"scalar-evolution-max-scc-analysis-depth", cl::Hidden,
cl::desc("Maximum amount of nodes to process while searching SCEVUnknown "
"Phi strongly connected components"),
cl::init(8));
static cl::opt<bool>
EnableFiniteLoopControl("scalar-evolution-finite-loop", cl::Hidden,
cl::desc("Handle <= and >= in finite loops"),
cl::init(true));
static cl::opt<bool> UseContextForNoWrapFlagInference(
"scalar-evolution-use-context-for-no-wrap-flag-strenghening", cl::Hidden,
cl::desc("Infer nuw/nsw flags using context where suitable"),
cl::init(true));
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void SCEV::dump() const {
print(dbgs());
dbgs() << '\n';
}
#endif
void SCEV::print(raw_ostream &OS) const { … }
Type *SCEV::getType() const { … }
ArrayRef<const SCEV *> SCEV::operands() const { … }
bool SCEV::isZero() const { … }
bool SCEV::isOne() const { … }
bool SCEV::isAllOnesValue() const { … }
bool SCEV::isNonConstantNegative() const { … }
SCEVCouldNotCompute::SCEVCouldNotCompute() : … { … }
bool SCEVCouldNotCompute::classof(const SCEV *S) { … }
const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { … }
const SCEV *ScalarEvolution::getConstant(const APInt &Val) { … }
const SCEV *
ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) { … }
const SCEV *ScalarEvolution::getVScale(Type *Ty) { … }
const SCEV *ScalarEvolution::getElementCount(Type *Ty, ElementCount EC) { … }
SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy,
const SCEV *op, Type *ty)
: … { … }
SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op,
Type *ITy)
: … { … }
SCEVIntegralCastExpr::SCEVIntegralCastExpr(const FoldingSetNodeIDRef ID,
SCEVTypes SCEVTy, const SCEV *op,
Type *ty)
: … { … }
SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op,
Type *ty)
: … { … }
SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, Type *ty)
: … { … }
SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
const SCEV *op, Type *ty)
: … { … }
void SCEVUnknown::deleted() { … }
void SCEVUnknown::allUsesReplacedWith(Value *New) { … }
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV,
Value *RV, unsigned Depth) { … }
static std::optional<int>
CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV,
const LoopInfo *const LI, const SCEV *LHS,
const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) { … }
static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
LoopInfo *LI, DominatorTree &DT) { … }
static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { … }
template <typename FoldT, typename IsIdentityT, typename IsAbsorberT>
static const SCEV *
constantFoldAndGroupOps(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT,
SmallVectorImpl<const SCEV *> &Ops, FoldT Fold,
IsIdentityT IsIdentity, IsAbsorberT IsAbsorber) { … }
static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K,
ScalarEvolution &SE,
Type *ResultTy) { … }
const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
ScalarEvolution &SE) const { … }
const SCEV *
SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands,
const SCEV *It, ScalarEvolution &SE) { … }
const SCEV *ScalarEvolution::getLosslessPtrToIntExpr(const SCEV *Op,
unsigned Depth) { … }
const SCEV *ScalarEvolution::getPtrToIntExpr(const SCEV *Op, Type *Ty) { … }
const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
unsigned Depth) { … }
static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
ICmpInst::Predicate *Pred,
ScalarEvolution *SE) { … }
static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
ICmpInst::Predicate *Pred,
ScalarEvolution *SE) { … }
namespace {
struct ExtendOpTraitsBase { … };
template <typename ExtendOp> struct ExtendOpTraits { … };
template <>
struct ExtendOpTraits<SCEVSignExtendExpr> : public ExtendOpTraitsBase { … };
const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
SCEVSignExtendExpr>::GetExtendExpr = …;
template <>
struct ExtendOpTraits<SCEVZeroExtendExpr> : public ExtendOpTraitsBase { … };
const ExtendOpTraitsBase::GetExtendExprTy ExtendOpTraits<
SCEVZeroExtendExpr>::GetExtendExpr = …;
}
template <typename ExtendOpTy>
static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty,
ScalarEvolution *SE, unsigned Depth) { … }
template <typename ExtendOpTy>
static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty,
ScalarEvolution *SE,
unsigned Depth) { … }
template <typename ExtendOpTy>
bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start,
const SCEV *Step,
const Loop *L) { … }
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE,
const SCEVConstant *ConstantTerm,
const SCEVAddExpr *WholeAddExpr) { … }
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE,
const APInt &ConstantStart,
const SCEV *Step) { … }
static void insertFoldCacheEntry(
const ScalarEvolution::FoldID &ID, const SCEV *S,
DenseMap<ScalarEvolution::FoldID, const SCEV *> &FoldCache,
DenseMap<const SCEV *, SmallVector<ScalarEvolution::FoldID, 2>>
&FoldCacheUser) { … }
const SCEV *
ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { … }
const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
unsigned Depth) { … }
const SCEV *
ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { … }
const SCEV *ScalarEvolution::getSignExtendExprImpl(const SCEV *Op, Type *Ty,
unsigned Depth) { … }
const SCEV *ScalarEvolution::getCastExpr(SCEVTypes Kind, const SCEV *Op,
Type *Ty) { … }
const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
Type *Ty) { … }
static bool
CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M,
SmallVectorImpl<const SCEV *> &NewOps,
APInt &AccumulatedConstant,
ArrayRef<const SCEV *> Ops, const APInt &Scale,
ScalarEvolution &SE) { … }
bool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
const SCEV *LHS, const SCEV *RHS,
const Instruction *CtxI) { … }
std::optional<SCEV::NoWrapFlags>
ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(
const OverflowingBinaryOperator *OBO) { … }
static SCEV::NoWrapFlags
StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type,
const ArrayRef<const SCEV *> Ops,
SCEV::NoWrapFlags Flags) { … }
bool ScalarEvolution::isAvailableAtLoopEntry(const SCEV *S, const Loop *L) { … }
const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
SCEV::NoWrapFlags OrigFlags,
unsigned Depth) { … }
const SCEV *
ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
SCEV::NoWrapFlags Flags) { … }
const SCEV *
ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
const Loop *L, SCEV::NoWrapFlags Flags) { … }
const SCEV *
ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
SCEV::NoWrapFlags Flags) { … }
static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) { … }
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) { … }
static bool containsConstantInAddMulChain(const SCEV *StartExpr) { … }
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
SCEV::NoWrapFlags OrigFlags,
unsigned Depth) { … }
const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
const SCEV *RHS) { … }
APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) { … }
const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS,
const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, const SCEV *Step,
const Loop *L,
SCEV::NoWrapFlags Flags) { … }
const SCEV *
ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
const Loop *L, SCEV::NoWrapFlags Flags) { … }
const SCEV *
ScalarEvolution::getGEPExpr(GEPOperator *GEP,
const SmallVectorImpl<const SCEV *> &IndexExprs) { … }
SCEV *ScalarEvolution::findExistingSCEVInCache(SCEVTypes SCEVType,
ArrayRef<const SCEV *> Ops) { … }
const SCEV *ScalarEvolution::getAbsExpr(const SCEV *Op, bool IsNSW) { … }
const SCEV *ScalarEvolution::getMinMaxExpr(SCEVTypes Kind,
SmallVectorImpl<const SCEV *> &Ops) { … }
namespace {
class SCEVSequentialMinMaxDeduplicatingVisitor final
: public SCEVVisitor<SCEVSequentialMinMaxDeduplicatingVisitor,
std::optional<const SCEV *>> { … };
}
static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind) { … }
namespace {
struct SCEVPoisonCollector { … };
}
static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) { … }
void ScalarEvolution::getPoisonGeneratingValues(
SmallPtrSetImpl<const Value *> &Result, const SCEV *S) { … }
bool ScalarEvolution::canReuseInstruction(
const SCEV *S, Instruction *I,
SmallVectorImpl<Instruction *> &DropPoisonGeneratingInsts) { … }
const SCEV *
ScalarEvolution::getSequentialMinMaxExpr(SCEVTypes Kind,
SmallVectorImpl<const SCEV *> &Ops) { … }
const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { … }
const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { … }
const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS,
const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) { … }
const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, const SCEV *RHS,
bool Sequential) { … }
const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
bool Sequential) { … }
const SCEV *
ScalarEvolution::getSizeOfExpr(Type *IntTy, TypeSize Size) { … }
const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) { … }
const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) { … }
const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy,
StructType *STy,
unsigned FieldNo) { … }
const SCEV *ScalarEvolution::getUnknown(Value *V) { … }
bool ScalarEvolution::isSCEVable(Type *Ty) const { … }
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { … }
Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { … }
Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const { … }
bool ScalarEvolution::instructionCouldExistWithOperands(const SCEV *A,
const SCEV *B) { … }
const SCEV *ScalarEvolution::getCouldNotCompute() { … }
bool ScalarEvolution::checkValidity(const SCEV *S) const { … }
bool ScalarEvolution::containsAddRecurrence(const SCEV *S) { … }
ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) { … }
void ScalarEvolution::eraseValueFromMap(Value *V) { … }
void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) { … }
const SCEV *ScalarEvolution::getSCEV(Value *V) { … }
const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { … }
const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
SCEV::NoWrapFlags Flags) { … }
static const SCEV *MatchNotExpr(const SCEV *Expr) { … }
const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { … }
const SCEV *ScalarEvolution::removePointerBase(const SCEV *P) { … }
const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
SCEV::NoWrapFlags Flags,
unsigned Depth) { … }
const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty,
unsigned Depth) { … }
const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty,
unsigned Depth) { … }
const SCEV *
ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, Type *Ty) { … }
const SCEV *
ScalarEvolution::getNoopOrSignExtend(const SCEV *V, Type *Ty) { … }
const SCEV *
ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, Type *Ty) { … }
const SCEV *
ScalarEvolution::getTruncateOrNoop(const SCEV *V, Type *Ty) { … }
const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS,
const SCEV *RHS) { … }
const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS,
const SCEV *RHS,
bool Sequential) { … }
const SCEV *
ScalarEvolution::getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,
bool Sequential) { … }
const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) { … }
static void PushDefUseChildren(Instruction *I,
SmallVectorImpl<Instruction *> &Worklist,
SmallPtrSetImpl<Instruction *> &Visited) { … }
namespace {
class SCEVInitRewriter : public SCEVRewriteVisitor<SCEVInitRewriter> { … };
class SCEVPostIncRewriter : public SCEVRewriteVisitor<SCEVPostIncRewriter> { … };
class SCEVBackedgeConditionFolder
: public SCEVRewriteVisitor<SCEVBackedgeConditionFolder> { … };
std::optional<const SCEV *>
SCEVBackedgeConditionFolder::compareWithBackedgeCondition(Value *IC) { … }
class SCEVShiftRewriter : public SCEVRewriteVisitor<SCEVShiftRewriter> { … };
}
SCEV::NoWrapFlags
ScalarEvolution::proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR) { … }
SCEV::NoWrapFlags
ScalarEvolution::proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR) { … }
SCEV::NoWrapFlags
ScalarEvolution::proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR) { … }
namespace {
struct BinaryOp { … };
}
static std::optional<BinaryOp> MatchBinaryOp(Value *V, const DataLayout &DL,
AssumptionCache &AC,
const DominatorTree &DT,
const Instruction *CxtI) { … }
static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI,
bool &Signed, ScalarEvolution &SE) { … }
static const Loop *isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI) { … }
std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
ScalarEvolution::createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI) { … }
std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
ScalarEvolution::createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI) { … }
bool PredicatedScalarEvolution::areAddRecsEqualWithPreds(
const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const { … }
const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
Value *BEValueV,
Value *StartValueV) { … }
const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { … }
static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge,
Value *&C, Value *&LHS, Value *&RHS) { … }
const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) { … }
const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { … }
bool SCEVMinMaxExprContains(const SCEV *Root, const SCEV *OperandToFind,
SCEVTypes RootKind) { … }
std::optional<const SCEV *>
ScalarEvolution::createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty,
ICmpInst *Cond,
Value *TrueVal,
Value *FalseVal) { … }
static std::optional<const SCEV *>
createNodeForSelectViaUMinSeq(ScalarEvolution *SE, const SCEV *CondExpr,
const SCEV *TrueExpr, const SCEV *FalseExpr) { … }
static std::optional<const SCEV *>
createNodeForSelectViaUMinSeq(ScalarEvolution *SE, Value *Cond, Value *TrueVal,
Value *FalseVal) { … }
const SCEV *ScalarEvolution::createNodeForSelectOrPHIViaUMinSeq(
Value *V, Value *Cond, Value *TrueVal, Value *FalseVal) { … }
const SCEV *ScalarEvolution::createNodeForSelectOrPHI(Value *V, Value *Cond,
Value *TrueVal,
Value *FalseVal) { … }
const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { … }
APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) { … }
APInt ScalarEvolution::getConstantMultiple(const SCEV *S) { … }
APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) { … }
uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) { … }
static std::optional<ConstantRange> GetRangeFromMetadata(Value *V) { … }
void ScalarEvolution::setNoWrapFlags(SCEVAddRecExpr *AddRec,
SCEV::NoWrapFlags Flags) { … }
ConstantRange ScalarEvolution::
getRangeForUnknownRecurrence(const SCEVUnknown *U) { … }
const ConstantRange &
ScalarEvolution::getRangeRefIter(const SCEV *S,
ScalarEvolution::RangeSignHint SignHint) { … }
const ConstantRange &ScalarEvolution::getRangeRef(
const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) { … }
static ConstantRange getRangeForAffineARHelper(APInt Step,
const ConstantRange &StartRange,
const APInt &MaxBECount,
bool Signed) { … }
ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
const SCEV *Step,
const APInt &MaxBECount) { … }
ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
ScalarEvolution::RangeSignHint SignHint) { … }
ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start,
const SCEV *Step,
const APInt &MaxBECount) { … }
SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) { … }
const Instruction *
ScalarEvolution::getNonTrivialDefiningScopeBound(const SCEV *S) { … }
const Instruction *
ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
bool &Precise) { … }
const Instruction *
ScalarEvolution::getDefiningScopeBound(ArrayRef<const SCEV *> Ops) { … }
bool ScalarEvolution::isGuaranteedToTransferExecutionTo(const Instruction *A,
const Instruction *B) { … }
bool ScalarEvolution::isSCEVExprNeverPoison(const Instruction *I) { … }
bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) { … }
ScalarEvolution::LoopProperties
ScalarEvolution::getLoopProperties(const Loop *L) { … }
bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) { … }
const SCEV *ScalarEvolution::createSCEVIter(Value *V) { … }
const SCEV *
ScalarEvolution::getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops) { … }
const SCEV *ScalarEvolution::createSCEV(Value *V) { … }
const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount) { … }
const SCEV *ScalarEvolution::getTripCountFromExitCount(const SCEV *ExitCount,
Type *EvalTy,
const Loop *L) { … }
static unsigned getConstantTripCount(const SCEVConstant *ExitCount) { … }
unsigned ScalarEvolution::getSmallConstantTripCount(const Loop *L) { … }
unsigned
ScalarEvolution::getSmallConstantTripCount(const Loop *L,
const BasicBlock *ExitingBlock) { … }
unsigned ScalarEvolution::getSmallConstantMaxTripCount(const Loop *L) { … }
unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L) { … }
unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
const SCEV *ExitCount) { … }
unsigned
ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
const BasicBlock *ExitingBlock) { … }
const SCEV *ScalarEvolution::getExitCount(const Loop *L,
const BasicBlock *ExitingBlock,
ExitCountKind Kind) { … }
const SCEV *ScalarEvolution::getPredicatedExitCount(
const Loop *L, const BasicBlock *ExitingBlock,
SmallVectorImpl<const SCEVPredicate *> *Predicates, ExitCountKind Kind) { … }
const SCEV *ScalarEvolution::getPredicatedBackedgeTakenCount(
const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Preds) { … }
const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L,
ExitCountKind Kind) { … }
const SCEV *ScalarEvolution::getPredicatedSymbolicMaxBackedgeTakenCount(
const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Preds) { … }
bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { … }
static void PushLoopPHIs(const Loop *L,
SmallVectorImpl<Instruction *> &Worklist,
SmallPtrSetImpl<Instruction *> &Visited) { … }
ScalarEvolution::BackedgeTakenInfo &
ScalarEvolution::getPredicatedBackedgeTakenInfo(const Loop *L) { … }
ScalarEvolution::BackedgeTakenInfo &
ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { … }
void ScalarEvolution::forgetAllLoops() { … }
void ScalarEvolution::visitAndClearUsers(
SmallVectorImpl<Instruction *> &Worklist,
SmallPtrSetImpl<Instruction *> &Visited,
SmallVectorImpl<const SCEV *> &ToForget) { … }
void ScalarEvolution::forgetLoop(const Loop *L) { … }
void ScalarEvolution::forgetTopmostLoop(const Loop *L) { … }
void ScalarEvolution::forgetValue(Value *V) { … }
void ScalarEvolution::forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V) { … }
void ScalarEvolution::forgetLoopDispositions() { … }
void ScalarEvolution::forgetBlockAndLoopDispositions(Value *V) { … }
const SCEV *ScalarEvolution::BackedgeTakenInfo::getExact(
const Loop *L, ScalarEvolution *SE,
SmallVectorImpl<const SCEVPredicate *> *Preds) const { … }
const ScalarEvolution::ExitNotTakenInfo *
ScalarEvolution::BackedgeTakenInfo::getExitNotTaken(
const BasicBlock *ExitingBlock,
SmallVectorImpl<const SCEVPredicate *> *Predicates) const { … }
const SCEV *
ScalarEvolution::BackedgeTakenInfo::getConstantMax(ScalarEvolution *SE) const { … }
const SCEV *ScalarEvolution::BackedgeTakenInfo::getSymbolicMax(
const Loop *L, ScalarEvolution *SE,
SmallVectorImpl<const SCEVPredicate *> *Predicates) { … }
bool ScalarEvolution::BackedgeTakenInfo::isConstantMaxOrZero(
ScalarEvolution *SE) const { … }
ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E)
: … { … }
ScalarEvolution::ExitLimit::ExitLimit(
const SCEV *E, const SCEV *ConstantMaxNotTaken,
const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList)
: … { … }
ScalarEvolution::ExitLimit::ExitLimit(
const SCEV *E, const SCEV *ConstantMaxNotTaken,
const SCEV *SymbolicMaxNotTaken, bool MaxOrZero,
const SmallPtrSetImpl<const SCEVPredicate *> &PredSet)
: … { … }
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
ArrayRef<ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo> ExitCounts,
bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero)
: … { … }
ScalarEvolution::BackedgeTakenInfo
ScalarEvolution::computeBackedgeTakenCount(const Loop *L,
bool AllowPredicates) { … }
ScalarEvolution::ExitLimit
ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock,
bool IsOnlyExit, bool AllowPredicates) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCond(
const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit,
bool AllowPredicates) { … }
std::optional<ScalarEvolution::ExitLimit>
ScalarEvolution::ExitLimitCache::find(const Loop *L, Value *ExitCond,
bool ExitIfTrue, bool ControlsOnlyExit,
bool AllowPredicates) { … }
void ScalarEvolution::ExitLimitCache::insert(const Loop *L, Value *ExitCond,
bool ExitIfTrue,
bool ControlsOnlyExit,
bool AllowPredicates,
const ExitLimit &EL) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondCached(
ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
bool ControlsOnlyExit, bool AllowPredicates) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
bool ControlsOnlyExit, bool AllowPredicates) { … }
std::optional<ScalarEvolution::ExitLimit>
ScalarEvolution::computeExitLimitFromCondFromBinOp(
ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
bool ControlsOnlyExit, bool AllowPredicates) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit,
bool AllowPredicates) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromICmp(
const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
bool ControlsOnlyExit, bool AllowPredicates) { … }
ScalarEvolution::ExitLimit
ScalarEvolution::computeExitLimitFromSingleExitSwitch(const Loop *L,
SwitchInst *Switch,
BasicBlock *ExitingBlock,
bool ControlsOnlyExit) { … }
static ConstantInt *
EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C,
ScalarEvolution &SE) { … }
ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
Value *LHS, Value *RHSV, const Loop *L, ICmpInst::Predicate Pred) { … }
static bool CanConstantFold(const Instruction *I) { … }
static bool canConstantEvolve(Instruction *I, const Loop *L) { … }
static PHINode *
getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
DenseMap<Instruction *, PHINode *> &PHIMap,
unsigned Depth) { … }
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { … }
static Constant *EvaluateExpression(Value *V, const Loop *L,
DenseMap<Instruction *, Constant *> &Vals,
const DataLayout &DL,
const TargetLibraryInfo *TLI) { … }
static Constant *getOtherIncomingValue(PHINode *PN, BasicBlock *BB) { … }
Constant *
ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
const Loop *L) { … }
const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L,
Value *Cond,
bool ExitWhen) { … }
const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { … }
static Constant *BuildConstantFromSCEV(const SCEV *V) { … }
const SCEV *
ScalarEvolution::getWithOperands(const SCEV *S,
SmallVectorImpl<const SCEV *> &NewOps) { … }
const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { … }
const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { … }
const SCEV *ScalarEvolution::stripInjectiveFunctions(const SCEV *S) const { … }
static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B,
ScalarEvolution &SE) { … }
static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
GetQuadraticEquation(const SCEVAddRecExpr *AddRec) { … }
static std::optional<APInt> MinOptional(std::optional<APInt> X,
std::optional<APInt> Y) { … }
static std::optional<APInt> TruncIfPossible(std::optional<APInt> X,
unsigned BitWidth) { … }
static std::optional<APInt>
SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { … }
static std::optional<APInt>
SolveQuadraticAddRecRange(const SCEVAddRecExpr *AddRec,
const ConstantRange &Range, ScalarEvolution &SE) { … }
ScalarEvolution::ExitLimit ScalarEvolution::howFarToZero(const SCEV *V,
const Loop *L,
bool ControlsOnlyExit,
bool AllowPredicates) { … }
ScalarEvolution::ExitLimit
ScalarEvolution::howFarToNonZero(const SCEV *V, const Loop *L) { … }
std::pair<const BasicBlock *, const BasicBlock *>
ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB)
const { … }
static bool HasSameValue(const SCEV *A, const SCEV *B) { … }
static bool MatchBinarySub(const SCEV *S, const SCEV *&LHS, const SCEV *&RHS) { … }
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
const SCEV *&LHS, const SCEV *&RHS,
unsigned Depth) { … }
bool ScalarEvolution::isKnownNegative(const SCEV *S) { … }
bool ScalarEvolution::isKnownPositive(const SCEV *S) { … }
bool ScalarEvolution::isKnownNonNegative(const SCEV *S) { … }
bool ScalarEvolution::isKnownNonPositive(const SCEV *S) { … }
bool ScalarEvolution::isKnownNonZero(const SCEV *S) { … }
bool ScalarEvolution::isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero,
bool OrNegative) { … }
std::pair<const SCEV *, const SCEV *>
ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) { … }
bool ScalarEvolution::isKnownViaInduction(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
std::optional<bool> ScalarEvolution::evaluatePredicate(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) { … }
bool ScalarEvolution::isKnownPredicateAt(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const Instruction *CtxI) { … }
std::optional<bool>
ScalarEvolution::evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS,
const SCEV *RHS, const Instruction *CtxI) { … }
bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
const SCEVAddRecExpr *LHS,
const SCEV *RHS) { … }
std::optional<ScalarEvolution::MonotonicPredicateType>
ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS,
ICmpInst::Predicate Pred) { … }
std::optional<ScalarEvolution::MonotonicPredicateType>
ScalarEvolution::getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS,
ICmpInst::Predicate Pred) { … }
std::optional<ScalarEvolution::LoopInvariantPredicate>
ScalarEvolution::getLoopInvariantPredicate(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const Loop *L,
const Instruction *CtxI) { … }
std::optional<ScalarEvolution::LoopInvariantPredicate>
ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
const Instruction *CtxI, const SCEV *MaxIter) { … }
std::optional<ScalarEvolution::LoopInvariantPredicate>
ScalarEvolution::getLoopInvariantExitCondDuringFirstIterationsImpl(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
const Instruction *CtxI, const SCEV *MaxIter) { … }
bool ScalarEvolution::isKnownPredicateViaConstantRanges(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { … }
bool ScalarEvolution::isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) { … }
bool ScalarEvolution::isKnownPredicateViaSplitting(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) { … }
bool ScalarEvolution::isImpliedViaGuard(const BasicBlock *BB,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool
ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool ScalarEvolution::isBasicBlockEntryGuardedByCond(const BasicBlock *BB,
ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) { … }
bool ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS) { … }
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
const SCEV *RHS,
const Value *FoundCondValue, bool Inverse,
const Instruction *CtxI) { … }
bool ScalarEvolution::isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS,
const SCEV *RHS,
ICmpInst::Predicate FoundPred,
const SCEV *FoundLHS, const SCEV *FoundRHS,
const Instruction *CtxI) { … }
bool ScalarEvolution::isImpliedCondBalancedTypes(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, const SCEV *FoundRHS,
const Instruction *CtxI) { … }
bool ScalarEvolution::splitBinaryAdd(const SCEV *Expr,
const SCEV *&L, const SCEV *&R,
SCEV::NoWrapFlags &Flags) { … }
std::optional<APInt>
ScalarEvolution::computeConstantDifference(const SCEV *More, const SCEV *Less) { … }
bool ScalarEvolution::isImpliedCondOperandsViaAddRecStart(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS, const SCEV *FoundRHS, const Instruction *CtxI) { … }
bool ScalarEvolution::isImpliedCondOperandsViaNoOverflow(
ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS, const SCEV *FoundRHS) { … }
bool ScalarEvolution::isImpliedViaMerge(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS, unsigned Depth) { … }
bool ScalarEvolution::isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS) { … }
bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS,
const Instruction *CtxI) { … }
template <typename MinMaxExprType>
static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr,
const SCEV *Candidate) { … }
static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE,
ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool ScalarEvolution::isImpliedViaOperations(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS,
unsigned Depth) { … }
static bool isKnownPredicateExtendIdiom(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool
ScalarEvolution::isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
bool
ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS,
const SCEV *FoundLHS,
const SCEV *FoundRHS) { … }
bool ScalarEvolution::isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred,
const SCEV *LHS,
const SCEV *RHS,
ICmpInst::Predicate FoundPred,
const SCEV *FoundLHS,
const SCEV *FoundRHS) { … }
bool ScalarEvolution::canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
bool IsSigned) { … }
bool ScalarEvolution::canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
bool IsSigned) { … }
const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) { … }
const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
const SCEV *Stride,
const SCEV *End,
unsigned BitWidth,
bool IsSigned) { … }
ScalarEvolution::ExitLimit
ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
const Loop *L, bool IsSigned,
bool ControlsOnlyExit, bool AllowPredicates) { … }
ScalarEvolution::ExitLimit ScalarEvolution::howManyGreaterThans(
const SCEV *LHS, const SCEV *RHS, const Loop *L, bool IsSigned,
bool ControlsOnlyExit, bool AllowPredicates) { … }
const SCEV *SCEVAddRecExpr::getNumIterationsInRange(const ConstantRange &Range,
ScalarEvolution &SE) const { … }
const SCEVAddRecExpr *
SCEVAddRecExpr::getPostIncExpr(ScalarEvolution &SE) const { … }
bool ScalarEvolution::containsUndefs(const SCEV *S) const { … }
bool ScalarEvolution::containsErasedValue(const SCEV *S) const { … }
const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { … }
void ScalarEvolution::SCEVCallbackVH::deleted() { … }
void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) { … }
ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
: … { … }
ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
AssumptionCache &AC, DominatorTree &DT,
LoopInfo &LI)
: … { … }
ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
: … { … }
ScalarEvolution::~ScalarEvolution() { … }
bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) { … }
static void PrintSCEVWithTypeHint(raw_ostream &OS, const SCEV* S) { … }
static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE,
const Loop *L) { … }
namespace llvm {
raw_ostream &operator<<(raw_ostream &OS, ScalarEvolution::LoopDisposition LD) { … }
raw_ostream &operator<<(raw_ostream &OS, ScalarEvolution::BlockDisposition BD) { … }
}
void ScalarEvolution::print(raw_ostream &OS) const { … }
ScalarEvolution::LoopDisposition
ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { … }
ScalarEvolution::LoopDisposition
ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { … }
bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { … }
bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { … }
ScalarEvolution::BlockDisposition
ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { … }
ScalarEvolution::BlockDisposition
ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { … }
bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) { … }
bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { … }
bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { … }
void ScalarEvolution::forgetBackedgeTakenCounts(const Loop *L,
bool Predicated) { … }
void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) { … }
void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) { … }
void
ScalarEvolution::getUsedLoops(const SCEV *S,
SmallPtrSetImpl<const Loop *> &LoopsUsed) { … }
void ScalarEvolution::getReachableBlocks(
SmallPtrSetImpl<BasicBlock *> &Reachable, Function &F) { … }
void ScalarEvolution::verify() const { … }
bool ScalarEvolution::invalidate(
Function &F, const PreservedAnalyses &PA,
FunctionAnalysisManager::Invalidator &Inv) { … }
AnalysisKey ScalarEvolutionAnalysis::Key;
ScalarEvolution ScalarEvolutionAnalysis::run(Function &F,
FunctionAnalysisManager &AM) { … }
PreservedAnalyses
ScalarEvolutionVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { … }
PreservedAnalyses
ScalarEvolutionPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { … }
INITIALIZE_PASS_BEGIN(ScalarEvolutionWrapperPass, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_END(ScalarEvolutionWrapperPass, "scalar-evolution",
"Scalar Evolution Analysis", false, true)
char ScalarEvolutionWrapperPass::ID = …;
ScalarEvolutionWrapperPass::ScalarEvolutionWrapperPass() : … { … }
bool ScalarEvolutionWrapperPass::runOnFunction(Function &F) { … }
void ScalarEvolutionWrapperPass::releaseMemory() { … }
void ScalarEvolutionWrapperPass::print(raw_ostream &OS, const Module *) const { … }
void ScalarEvolutionWrapperPass::verifyAnalysis() const { … }
void ScalarEvolutionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … }
const SCEVPredicate *ScalarEvolution::getEqualPredicate(const SCEV *LHS,
const SCEV *RHS) { … }
const SCEVPredicate *
ScalarEvolution::getComparePredicate(const ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS) { … }
const SCEVPredicate *ScalarEvolution::getWrapPredicate(
const SCEVAddRecExpr *AR,
SCEVWrapPredicate::IncrementWrapFlags AddedFlags) { … }
namespace {
class SCEVPredicateRewriter : public SCEVRewriteVisitor<SCEVPredicateRewriter> { … };
}
const SCEV *
ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L,
const SCEVPredicate &Preds) { … }
const SCEVAddRecExpr *ScalarEvolution::convertSCEVToAddRecWithPredicates(
const SCEV *S, const Loop *L,
SmallPtrSetImpl<const SCEVPredicate *> &Preds) { … }
SCEVPredicate::SCEVPredicate(const FoldingSetNodeIDRef ID,
SCEVPredicateKind Kind)
: … { … }
SCEVComparePredicate::SCEVComparePredicate(const FoldingSetNodeIDRef ID,
const ICmpInst::Predicate Pred,
const SCEV *LHS, const SCEV *RHS)
: … { … }
bool SCEVComparePredicate::implies(const SCEVPredicate *N) const { … }
bool SCEVComparePredicate::isAlwaysTrue() const { … }
void SCEVComparePredicate::print(raw_ostream &OS, unsigned Depth) const { … }
SCEVWrapPredicate::SCEVWrapPredicate(const FoldingSetNodeIDRef ID,
const SCEVAddRecExpr *AR,
IncrementWrapFlags Flags)
: … { … }
const SCEVAddRecExpr *SCEVWrapPredicate::getExpr() const { … }
bool SCEVWrapPredicate::implies(const SCEVPredicate *N) const { … }
bool SCEVWrapPredicate::isAlwaysTrue() const { … }
void SCEVWrapPredicate::print(raw_ostream &OS, unsigned Depth) const { … }
SCEVWrapPredicate::IncrementWrapFlags
SCEVWrapPredicate::getImpliedFlags(const SCEVAddRecExpr *AR,
ScalarEvolution &SE) { … }
SCEVUnionPredicate::SCEVUnionPredicate(ArrayRef<const SCEVPredicate *> Preds)
: … { … }
bool SCEVUnionPredicate::isAlwaysTrue() const { … }
bool SCEVUnionPredicate::implies(const SCEVPredicate *N) const { … }
void SCEVUnionPredicate::print(raw_ostream &OS, unsigned Depth) const { … }
void SCEVUnionPredicate::add(const SCEVPredicate *N) { … }
PredicatedScalarEvolution::PredicatedScalarEvolution(ScalarEvolution &SE,
Loop &L)
: … { … }
void ScalarEvolution::registerUser(const SCEV *User,
ArrayRef<const SCEV *> Ops) { … }
const SCEV *PredicatedScalarEvolution::getSCEV(Value *V) { … }
const SCEV *PredicatedScalarEvolution::getBackedgeTakenCount() { … }
const SCEV *PredicatedScalarEvolution::getSymbolicMaxBackedgeTakenCount() { … }
void PredicatedScalarEvolution::addPredicate(const SCEVPredicate &Pred) { … }
const SCEVPredicate &PredicatedScalarEvolution::getPredicate() const { … }
void PredicatedScalarEvolution::updateGeneration() { … }
void PredicatedScalarEvolution::setNoOverflow(
Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags) { … }
bool PredicatedScalarEvolution::hasNoOverflow(
Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags) { … }
const SCEVAddRecExpr *PredicatedScalarEvolution::getAsAddRec(Value *V) { … }
PredicatedScalarEvolution::PredicatedScalarEvolution(
const PredicatedScalarEvolution &Init)
: … { … }
void PredicatedScalarEvolution::print(raw_ostream &OS, unsigned Depth) const { … }
bool ScalarEvolution::matchURem(const SCEV *Expr, const SCEV *&LHS,
const SCEV *&RHS) { … }
ScalarEvolution::LoopGuards
ScalarEvolution::LoopGuards::collect(const Loop *L, ScalarEvolution &SE) { … }
const SCEV *ScalarEvolution::LoopGuards::rewrite(const SCEV *Expr) const { … }
const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr, const Loop *L) { … }
const SCEV *ScalarEvolution::applyLoopGuards(const SCEV *Expr,
const LoopGuards &Guards) { … }