llvm/llvm/lib/Analysis/ScalarEvolution.cpp

//===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains the implementation of the scalar evolution analysis
// engine, which is used primarily to analyze expressions involving induction
// variables in loops.
//
// There are several aspects to this library.  First is the representation of
// scalar expressions, which are represented as subclasses of the SCEV class.
// These classes are used to represent certain types of subexpressions that we
// can handle. We only create one SCEV of a particular shape, so
// pointer-comparisons for equality are legal.
//
// One important aspect of the SCEV objects is that they are never cyclic, even
// if there is a cycle in the dataflow for an expression (ie, a PHI node).  If
// the PHI node is one of the idioms that we can represent (e.g., a polynomial
// recurrence) then we represent it directly as a recurrence node, otherwise we
// represent it as a SCEVUnknown node.
//
// In addition to being able to represent expressions of various types, we also
// have folders that are used to build the *canonical* representation for a
// particular expression.  These folders are capable of using a variety of
// rewrite rules to simplify the expressions.
//
// Once the folders are defined, we can implement the more interesting
// higher-level code, such as the code that recognizes PHI nodes of various
// types, computes the execution count of a loop, etc.
//
// TODO: We should use these routines and value representations to implement
// dependence analysis!
//
//===----------------------------------------------------------------------===//
//
// There are several good references for the techniques used in this analysis.
//
//  Chains of recurrences -- a method to expedite the evaluation
//  of closed-form functions
//  Olaf Bachmann, Paul S. Wang, Eugene V. Zima
//
//  On computational properties of chains of recurrences
//  Eugene V. Zima
//
//  Symbolic Evaluation of Chains of Recurrences for Loop Optimization
//  Robert A. van Engelen
//
//  Efficient Symbolic Analysis for Optimizing Compilers
//  Robert A. van Engelen
//
//  Using the chains of recurrences algebra for data dependence testing and
//  induction variable substitution
//  MS Thesis, Johnie Birch
//
//===----------------------------------------------------------------------===//

#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));

//===----------------------------------------------------------------------===//
//                           SCEV class definitions
//===----------------------------------------------------------------------===//

//===----------------------------------------------------------------------===//
// Implementation of the SCEV class.
//

#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) { … }

//===----------------------------------------------------------------------===//
//                               SCEV Utilities
//===----------------------------------------------------------------------===//

/// Compare the two values \p LV and \p RV in terms of their "complexity" where
/// "complexity" is a partial (and somewhat ad-hoc) relation used to order
/// operands in SCEV expressions.
static int CompareValueComplexity(const LoopInfo *const LI, Value *LV,
                                  Value *RV, unsigned Depth) { … }

// Return negative, zero, or positive, if LHS is less than, equal to, or greater
// than RHS, respectively. A three-way result allows recursive comparisons to be
// more efficient.
// If the max analysis depth was reached, return std::nullopt, assuming we do
// not know if they are equivalent for sure.
static std::optional<int>
CompareSCEVComplexity(EquivalenceClasses<const SCEV *> &EqCacheSCEV,
                      const LoopInfo *const LI, const SCEV *LHS,
                      const SCEV *RHS, DominatorTree &DT, unsigned Depth = 0) { … }

/// 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
/// this to depend on where the addresses of various SCEV objects happened to
/// land in memory.
static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops,
                              LoopInfo *LI, DominatorTree &DT) { … }

/// Returns true if \p Ops contains a huge SCEV (the subtree of S contains at
/// least HugeExprThreshold nodes).
static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { … }

/// Performs a number of common optimizations on the passed \p Ops. If the
/// whole expression reduces down to a single operand, it will be returned.
///
/// The following optimizations are performed:
///  * Fold constants using the \p Fold function.
///  * Remove identity constants satisfying \p IsIdentity.
///  * If a constant satisfies \p IsAbsorber, return it.
///  * Sort operands by complexity.
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) { … }

//===----------------------------------------------------------------------===//
//                      Simple SCEV method implementations
//===----------------------------------------------------------------------===//

/// 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) { … }

/// 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)
///
/// where BC(It, k) stands for binomial coefficient.
const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It,
                                                ScalarEvolution &SE) const { … }

const SCEV *
SCEVAddRecExpr::evaluateAtIteration(ArrayRef<const SCEV *> Operands,
                                    const SCEV *It, ScalarEvolution &SE) { … }

//===----------------------------------------------------------------------===//
//                    SCEV Expression folder implementations
//===----------------------------------------------------------------------===//

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) { … }

// Get the limit of a recurrence such that incrementing by Step cannot cause
// signed overflow as long as the value of the recurrence within the
// loop does not exceed this limit before incrementing.
static const SCEV *getSignedOverflowLimitForStep(const SCEV *Step,
                                                 ICmpInst::Predicate *Pred,
                                                 ScalarEvolution *SE) { … }

// Get the limit of a recurrence such that incrementing by Step cannot cause
// unsigned overflow as long as the value of the recurrence within the loop does
// not exceed this limit before incrementing.
static const SCEV *getUnsignedOverflowLimitForStep(const SCEV *Step,
                                                   ICmpInst::Predicate *Pred,
                                                   ScalarEvolution *SE) { … }

namespace {

struct ExtendOpTraitsBase { … };

// Used to make code generic over signed and unsigned overflow.
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 = …;

} // end anonymous namespace

// The recurrence AR has been shown to have no signed/unsigned wrap or something
// close to it. Typically, if we can prove NSW/NUW for AR, then we can just as
// easily prove NSW/NUW for its preincrement or postincrement sibling. This
// allows normalizing a sign/zero extended AddRec as such: {sext/zext(Step +
// Start),+,Step} => {(Step + sext/zext(Start),+,Step} As a result, the
// expression "Step + sext/zext(PreIncAR)" is congruent with
// "sext/zext(PostIncAR)"
template <typename ExtendOpTy>
static const SCEV *getPreStartForExtend(const SCEVAddRecExpr *AR, Type *Ty,
                                        ScalarEvolution *SE, unsigned Depth) { … }

// Get the normalized zero or sign extended expression for this AddRec's Start.
template <typename ExtendOpTy>
static const SCEV *getExtendAddRecStart(const SCEVAddRecExpr *AR, Type *Ty,
                                        ScalarEvolution *SE,
                                        unsigned Depth) { … }

// Try to prove away overflow by looking at "nearby" add recurrences.  A
// motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
// does not itself wrap then we can conclude that `{1,+,4}` is `nuw`.
//
// Formally:
//
//     {S,+,X} == {S-T,+,X} + T
//  => Ext({S,+,X}) == Ext({S-T,+,X} + T)
//
// If ({S-T,+,X} + T) does not overflow  ... (1)
//
//  RHS == Ext({S-T,+,X} + T) == Ext({S-T,+,X}) + Ext(T)
//
// If {S-T,+,X} does not overflow  ... (2)
//
//  RHS == Ext({S-T,+,X}) + Ext(T) == {Ext(S-T),+,Ext(X)} + Ext(T)
//      == {Ext(S-T)+Ext(T),+,Ext(X)}
//
// If (S-T)+T does not overflow  ... (3)
//
//  RHS == {Ext(S-T)+Ext(T),+,Ext(X)} == {Ext(S-T+T),+,Ext(X)}
//      == {Ext(S),+,Ext(X)} == LHS
//
// Thus, if (1), (2) and (3) are true for some T, then
//   Ext({S,+,X}) == {Ext(S),+,Ext(X)}
//
// (3) is implied by (1) -- "(S-T)+T does not overflow" is simply "({S-T,+,X}+T)
// does not overflow" restricted to the 0th iteration.  Therefore we only need
// to check for (1) and (2).
//
// In the current context, S is `Start`, X is `Step`, Ext is `ExtendOpTy` and T
// is `Delta` (defined below).
template <typename ExtendOpTy>
bool ScalarEvolution::proveNoWrapByVaryingStart(const SCEV *Start,
                                                const SCEV *Step,
                                                const Loop *L) { … }

// Finds an integer D for an expression (C + x + y + ...) such that the top
// level addition in (D + (C - D + x + y + ...)) would not wrap (signed or
// unsigned) and the number of trailing zeros of (C - D + x + y + ...) is
// maximized, where C is the \p ConstantTerm, x, y, ... are arbitrary SCEVs, and
// the (C + x + y + ...) expression is \p WholeAddExpr.
static APInt extractConstantWithoutWrapping(ScalarEvolution &SE,
                                            const SCEVConstant *ConstantTerm,
                                            const SCEVAddExpr *WholeAddExpr) { … }

// Finds an integer D for an affine AddRec expression {C,+,x} such that the top
// level addition in (D + {C-D,+,x}) would not wrap (signed or unsigned) and the
// number of trailing zeros of (C - D + x * n) is maximized, where C is the \p
// ConstantStart, x is an arbitrary \p Step, and n is the loop trip count.
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) { … }

/// getAnyExtendExpr - Return a SCEV for the given operand extended with
/// unspecified bits out to the given type.
const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op,
                                              Type *Ty) { … }

/// 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)
///
/// where A and B are constants, update the map with these values:
///
///    (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0)
///
/// and add 13 + A*B*29 to AccumulatedConstant.
/// This will allow getAddRecExpr to produce this:
///
///    13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B)
///
/// This form often exposes folding opportunities that are hidden in
/// the original operand list.
///
/// Return true iff it appears that any interesting folding opportunities
/// may be exposed. This helps getAddRecExpr short-circuit extra work in
/// the common case where no interesting opportunities are present, and
/// is also used as a check to avoid infinite recursion.
static bool
CollectAddOperandsWithScales(SmallDenseMap<const SCEV *, APInt, 16> &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) { … }

// We're trying to construct a SCEV of type `Type' with `Ops' as operands and
// `OldFlags' as can't-wrap behavior.  Infer a more aggressive set of
// can't-overflow flags for the operation if possible.
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) { … }

/// Get a canonical add expression, or something simpler if possible.
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) { … }

/// Compute the result of "n choose k", the binomial coefficient.  If an
/// intermediate computation overflows, Overflow will be set and the return will
/// be garbage. Overflow is not cleared on absence of overflow.
static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) { … }

/// Determine if any of the operands in this SCEV are a constant or if
/// any of the add or multiply expressions in this SCEV contain a constant.
static bool containsConstantInAddMulChain(const SCEV *StartExpr) { … }

/// Get a canonical multiply expression, or something simpler if possible.
const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
                                        SCEV::NoWrapFlags OrigFlags,
                                        unsigned Depth) { … }

/// Represents an unsigned remainder expression based on unsigned division.
const SCEV *ScalarEvolution::getURemExpr(const SCEV *LHS,
                                         const SCEV *RHS) { … }

/// Get a canonical unsigned division expression, or something simpler if
/// possible.
const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS,
                                         const SCEV *RHS) { … }

APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

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 *>> { … };

} // namespace

static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind) { … }

namespace {
// The only way poison may be introduced in a SCEV expression is from a
// poison SCEVUnknown (ConstantExprs are also represented as SCEVUnknown,
// not SCEVConstant). Notably, nowrap flags in SCEV nodes can *not*
// introduce poison -- they encode guaranteed, non-speculated knowledge.
//
// Additionally, all SCEV nodes propagate poison from inputs to outputs,
// with the notable exception of umin_seq, where only poison from the first
// operand is (unconditionally) propagated.
struct SCEVPoisonCollector { … };
} // namespace

/// Return true if V is poison given that AssumedPoison is already poison.
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) { … }

//===----------------------------------------------------------------------===//
//            Basic SCEV Analysis and PHI Idiom Recognition Code
//

/// 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 { … }

/// Return the size in bits of the specified type, for which isSCEVable must
/// return true.
uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { … }

/// 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 index sized integer type.
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) { … }

/// Return the ValueOffsetPair set for \p S. \p S can be represented
/// by the value and offset from any ValueOffsetPair in the set.
ArrayRef<Value *> ScalarEvolution::getSCEVValues(const SCEV *S) { … }

/// Erase Value from ValueExprMap and ExprValueMap. ValueExprMap.erase(V)
/// cannot be used separately. eraseValueFromMap should be used to remove
/// V from ValueExprMap and ExprValueMap at the same time.
void ScalarEvolution::eraseValueFromMap(Value *V) { … }

void ScalarEvolution::insertValueToMap(Value *V, const SCEV *S) { … }

/// Return an existing SCEV if it exists, otherwise analyze the expression and
/// create a new one.
const SCEV *ScalarEvolution::getSCEV(Value *V) { … }

const SCEV *ScalarEvolution::getExistingSCEV(Value *V) { … }

/// Return a SCEV corresponding to -V = -1*V
const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
                                             SCEV::NoWrapFlags Flags) { … }

/// If Expr computes ~A, return A else return nullptr
static const SCEV *MatchNotExpr(const SCEV *Expr) { … }

/// Return a SCEV corresponding to ~V = -1-V
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) { … }

/// Push users of the given Instruction onto the given Worklist.
static void PushDefUseChildren(Instruction *I,
                               SmallVectorImpl<Instruction *> &Worklist,
                               SmallPtrSetImpl<Instruction *> &Visited) { … }

namespace {

/// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
/// expression in case its Loop is L. If it is not L then
/// if IgnoreOtherLoops is true then use AddRec itself
/// otherwise rewrite cannot be done.
/// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
class SCEVInitRewriter : public SCEVRewriteVisitor<SCEVInitRewriter> { … };

/// Takes SCEV S and Loop L. For each AddRec sub-expression, use its post
/// increment expression in case its Loop is L. If it is not L then
/// use AddRec itself.
/// If SCEV contains non-invariant unknown SCEV rewrite cannot be done.
class SCEVPostIncRewriter : public SCEVRewriteVisitor<SCEVPostIncRewriter> { … };

/// This class evaluates the compare condition by matching it against the
/// condition of loop latch. If there is a match we assume a true value
/// for the condition while building SCEV nodes.
class SCEVBackedgeConditionFolder
    : public SCEVRewriteVisitor<SCEVBackedgeConditionFolder> { … };

std::optional<const SCEV *>
SCEVBackedgeConditionFolder::compareWithBackedgeCondition(Value *IC) { … }

class SCEVShiftRewriter : public SCEVRewriteVisitor<SCEVShiftRewriter> { … };

} // end anonymous namespace

SCEV::NoWrapFlags
ScalarEvolution::proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR) { … }

SCEV::NoWrapFlags
ScalarEvolution::proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR) { … }
SCEV::NoWrapFlags
ScalarEvolution::proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR) { … }

namespace {

/// Represents an abstract binary operation.  This may exist as a
/// normal instruction or constant expression, or may have been
/// derived from an expression tree.
struct BinaryOp { … };

} // end anonymous namespace

/// Try to map \p V into a BinaryOp, and return \c std::nullopt on failure.
static std::optional<BinaryOp> MatchBinaryOp(Value *V, const DataLayout &DL,
                                             AssumptionCache &AC,
                                             const DominatorTree &DT,
                                             const Instruction *CxtI) { … }

/// Helper function to createAddRecFromPHIWithCasts. We have a phi
/// node whose symbolic (unknown) SCEV is \p SymbolicPHI, which is updated via
/// the loop backedge by a SCEVAddExpr, possibly also with a few casts on the
/// way. This function checks if \p Op, an operand of this SCEVAddExpr,
/// follows one of the following patterns:
/// Op == (SExt ix (Trunc iy (%SymbolicPHI) to ix) to iy)
/// Op == (ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy)
/// If the SCEV expression of \p Op conforms with one of the expected patterns
/// we return the type of the truncation operation, and indicate whether the
/// truncated type should be treated as signed/unsigned by setting
/// \p Signed to true/false, respectively.
static Type *isSimpleCastedPHI(const SCEV *Op, const SCEVUnknown *SymbolicPHI,
                               bool &Signed, ScalarEvolution &SE) { … }

static const Loop *isIntegerLoopHeaderPHI(const PHINode *PN, LoopInfo &LI) { … }

// Analyze \p SymbolicPHI, a SCEV expression of a phi node, and check if the
// computation that updates the phi follows the following pattern:
//   (SExt/ZExt ix (Trunc iy (%SymbolicPHI) to ix) to iy) + InvariantAccum
// which correspond to a phi->trunc->sext/zext->add->phi update chain.
// If so, try to see if it can be rewritten as an AddRecExpr under some
// Predicates. If successful, return them as a pair. Also cache the results
// of the analysis.
//
// Example usage scenario:
//    Say the Rewriter is called for the following SCEV:
//         8 * ((sext i32 (trunc i64 %X to i32) to i64) + %Step)
//    where:
//         %X = phi i64 (%Start, %BEValue)
//    It will visitMul->visitAdd->visitSExt->visitTrunc->visitUnknown(%X),
//    and call this function with %SymbolicPHI = %X.
//
//    The analysis will find that the value coming around the backedge has
//    the following SCEV:
//         BEValue = ((sext i32 (trunc i64 %X to i32) to i64) + %Step)
//    Upon concluding that this matches the desired pattern, the function
//    will return the pair {NewAddRec, SmallPredsVec} where:
//         NewAddRec = {%Start,+,%Step}
//         SmallPredsVec = {P1, P2, P3} as follows:
//           P1(WrapPred): AR: {trunc(%Start),+,(trunc %Step)}<nsw> Flags: <nssw>
//           P2(EqualPred): %Start == (sext i32 (trunc i64 %Start to i32) to i64)
//           P3(EqualPred): %Step == (sext i32 (trunc i64 %Step to i32) to i64)
//    The returned pair means that SymbolicPHI can be rewritten into NewAddRec
//    under the predicates {P1,P2,P3}.
//    This predicated rewrite will be cached in PredicatedSCEVRewrites:
//         PredicatedSCEVRewrites[{%X,L}] = {NewAddRec, {P1,P2,P3)}
//
// TODO's:
//
// 1) Extend the Induction descriptor to also support inductions that involve
//    casts: When needed (namely, when we are called in the context of the
//    vectorizer induction analysis), a Set of cast instructions will be
//    populated by this method, and provided back to isInductionPHI. This is
//    needed to allow the vectorizer to properly record them to be ignored by
//    the cost model and to avoid vectorizing them (otherwise these casts,
//    which are redundant under the runtime overflow checks, will be
//    vectorized, which can be costly).
//
// 2) Support additional induction/PHISCEV patterns: We also want to support
//    inductions where the sext-trunc / zext-trunc operations (partly) occur
//    after the induction update operation (the induction increment):
//
//      (Trunc iy (SExt/ZExt ix (%SymbolicPHI + InvariantAccum) to iy) to ix)
//    which correspond to a phi->add->trunc->sext/zext->phi update chain.
//
//      (Trunc iy ((SExt/ZExt ix (%SymbolicPhi) to iy) + InvariantAccum) to ix)
//    which correspond to a phi->trunc->add->sext/zext->phi update chain.
//
// 3) Outline common code with createAddRecFromPHI to avoid duplication.
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) { … }

// FIXME: This utility is currently required because the Rewriter currently
// does not rewrite this expression:
// {0, +, (sext ix (trunc iy to ix) to iy)}
// into {0, +, %step},
// even when the following Equal predicate exists:
// "%step == (sext ix (trunc iy to ix) to iy)".
bool PredicatedScalarEvolution::areAddRecsEqualWithPreds(
    const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const { … }

/// A helper function for createAddRecFromPHI to handle simple cases.
///
/// This function tries to find an AddRec expression for the simplest (yet most
/// common) cases: PN = PHI(Start, OP(Self, LoopInvariant)).
/// If it fails, createAddRecFromPHI will use a more general, but slow,
/// technique for finding the AddRec expression.
const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN,
                                                      Value *BEValueV,
                                                      Value *StartValueV) { … }

const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) { … }

// Try to match a control flow sequence that branches out at BI and merges back
// at Merge into a "C ? LHS : RHS" select pattern.  Return true on a successful
// match.
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) { … }

/// Expand GEP instructions into add and multiply operations. This allows them
/// to be analyzed by regular SCEV code.
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) { … }

/// Helper method to assign a range to V from metadata present in the IR.
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) { … }

/// 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.
const ConstantRange &ScalarEvolution::getRangeRef(
    const SCEV *S, ScalarEvolution::RangeSignHint SignHint, unsigned Depth) { … }

// Given a StartRange, Step and MaxBECount for an expression compute a range of
// values that the expression can take. Initially, the expression has a value
// from StartRange and then is changed by Step up to MaxBECount times. Signed
// argument defines if we treat Step as signed or unsigned.
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) { … }

//===----------------------------------------------------------------------===//
//                   Iteration Count Computation Code
//

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, SmallVectorImpl<const SCEVPredicate *> *Predicates) { … }

unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L) { … }

unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
                                                       const SCEV *ExitCount) { … }

/// 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
/// constant, use getSmallConstantTripCount for that case), Will also return 1
/// if the trip count is very large (>= 2^32).
///
/// As explained in the comments for getSmallConstantTripCount, this assumes
/// that control exits the loop via ExitingBlock.
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) { … }

const SCEV *ScalarEvolution::getPredicatedConstantMaxBackedgeTakenCount(
    const Loop *L, SmallVectorImpl<const SCEVPredicate *> &Preds) { … }

bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { … }

/// Push PHI nodes in the header of the given loop onto the given Worklist.
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) { … }

/// Get the exact loop backedge taken count considering all loop exits. A
/// computable result can only be returned for loops with all exiting blocks
/// dominating the latch. 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 exiting block using getExact(ExitingBlock, SE).
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 { … }

/// getConstantMax - Get the constant max backedge taken count for the loop.
const SCEV *ScalarEvolution::BackedgeTakenInfo::getConstantMax(
    ScalarEvolution *SE,
    SmallVectorImpl<const SCEVPredicate *> *Predicates) 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<ArrayRef<const SCEVPredicate *>> PredLists)
    : … { … }

ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E,
                                      const SCEV *ConstantMaxNotTaken,
                                      const SCEV *SymbolicMaxNotTaken,
                                      bool MaxOrZero,
                                      ArrayRef<const SCEVPredicate *> PredList)
    : … { … }

/// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
/// computable exit into a persistent ExitNotTakenInfo array.
ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
    ArrayRef<ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo> ExitCounts,
    bool IsComplete, const SCEV *ConstantMax, bool MaxOrZero)
    : … { … }

/// Compute the number of times the backedge of the specified loop will execute.
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) { … }

/// 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) { … }

/// Determine whether this instruction can constant evolve within this loop
/// assuming its operands can all constant evolve.
static bool canConstantEvolve(Instruction *I, const Loop *L) { … }

/// getConstantEvolvingPHIOperands - Implement getConstantEvolvingPHI by
/// recursing through each instruction operand until reaching a loop header phi.
static PHINode *
getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
                               DenseMap<Instruction *, PHINode *> &PHIMap,
                               unsigned Depth) { … }

/// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
/// in the loop that V is derived from.  We allow arbitrary operations along the
/// way, but the operands of an operation must either be constants or a value
/// derived from a constant PHI.  If this expression does not fit with these
/// constraints, return null.
static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { … }

/// EvaluateExpression - Given an expression that passes the
/// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node
/// in the loop has the value PHIVal.  If we can't fold this expression for some
/// reason, return null.
static Constant *EvaluateExpression(Value *V, const Loop *L,
                                    DenseMap<Instruction *, Constant *> &Vals,
                                    const DataLayout &DL,
                                    const TargetLibraryInfo *TLI) { … }


// If every incoming value to PN except the one for BB is a specific Constant,
// return that, else return nullptr.
static Constant *getOtherIncomingValue(PHINode *PN, BasicBlock *BB) { … }

/// 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
/// involving constants, fold it.
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) { … }

/// This builds up a Constant using the ConstantExpr interface.  That way, we
/// will return Constants for objects which aren't represented by a
/// SCEVConstant, because SCEVConstant is restricted to ConstantInt.
/// Returns NULL if the SCEV isn't representable as a Constant.
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 { … }

/// Finds the minimum unsigned root of the following equation:
///
///     A * X = B (mod N)
///
/// where N = 2^BW and BW is the common bit width of A and B. The signedness of
/// A and B isn't important.
///
/// If the equation does not have a solution, SCEVCouldNotCompute is returned.
static const SCEV *
SolveLinEquationWithOverflow(const APInt &A, const SCEV *B,
                             SmallVectorImpl<const SCEVPredicate *> *Predicates,

                             ScalarEvolution &SE) { … }

/// For a given quadratic addrec, generate coefficients of the corresponding
/// quadratic equation, multiplied by a common value to ensure that they are
/// integers.
/// The returned value is a tuple { A, B, C, M, BitWidth }, where
/// Ax^2 + Bx + C is the quadratic function, M is the value that A, B and C
/// were multiplied by, and BitWidth is the bit width of the original addrec
/// coefficients.
/// This function returns std::nullopt if the addrec coefficients are not
/// compile- time constants.
static std::optional<std::tuple<APInt, APInt, APInt, APInt, unsigned>>
GetQuadraticEquation(const SCEVAddRecExpr *AddRec) { … }

/// Helper function to compare optional APInts:
/// (a) if X and Y both exist, return min(X, Y),
/// (b) if neither X nor Y exist, return std::nullopt,
/// (c) if exactly one of X and Y exists, return that value.
static std::optional<APInt> MinOptional(std::optional<APInt> X,
                                        std::optional<APInt> Y) { … }

/// Helper function to truncate an optional APInt to a given BitWidth.
/// When solving addrec-related equations, it is preferable to return a value
/// that has the same bit width as the original addrec's coefficients. If the
/// solution fits in the original bit width, truncate it (except for i1).
/// Returning a value of a different bit width may inhibit some optimizations.
///
/// In general, a solution to a quadratic equation generated from an addrec
/// may require BW+1 bits, where BW is the bit width of the addrec's
/// coefficients. The reason is that the coefficients of the quadratic
/// equation are BW+1 bits wide (to avoid truncation when converting from
/// the addrec to the equation).
static std::optional<APInt> TruncIfPossible(std::optional<APInt> X,
                                            unsigned BitWidth) { … }

/// Let c(n) be the value of the quadratic chrec {L,+,M,+,N} after n
/// iterations. The values L, M, N are assumed to be signed, and they
/// should all have the same bit widths.
/// Find the least n >= 0 such that c(n) = 0 in the arithmetic modulo 2^BW,
/// where BW is the bit width of the addrec's coefficients.
/// If the calculated value is a BW-bit integer (for BW > 1), it will be
/// returned as such, otherwise the bit width of the returned value may
/// be greater than BW.
///
/// This function returns std::nullopt if
/// (a) the addrec coefficients are not constant, or
/// (b) SolveQuadraticEquationWrap was unable to find a solution. For cases
///     like x^2 = 5, no integer solutions exist, in other cases an integer
///     solution may exist, but SolveQuadraticEquationWrap may fail to find it.
static std::optional<APInt>
SolveQuadraticAddRecExact(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { … }

/// Let c(n) be the value of the quadratic chrec {0,+,M,+,N} after n
/// iterations. The values M, N are assumed to be signed, and they
/// should all have the same bit widths.
/// Find the least n such that c(n) does not belong to the given range,
/// while c(n-1) does.
///
/// This function returns std::nullopt if
/// (a) the addrec coefficients are not constant, or
/// (b) SolveQuadraticEquationWrap was unable to find a solution for the
///     bounds of the range.
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 { … }

/// 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) { … }

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) { … }

/// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
/// protected by a conditional between LHS and RHS.  This is used to
/// to eliminate casts.
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) { … }

/// Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values?
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) { … }

/// Is LHS `Pred` RHS true on the virtue of LHS or RHS being a Min or Max
/// expression?
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 { … }

// Return true when S contains at least an undef value.
bool ScalarEvolution::containsUndefs(const SCEV *S) const { … }

// Return true when S contains a value that is a nullptr.
bool ScalarEvolution::containsErasedValue(const SCEV *S) const { … }

/// Return the size of an element read or written by Inst.
const SCEV *ScalarEvolution::getElementSize(Instruction *Inst) { … }

//===----------------------------------------------------------------------===//
//                   SCEVCallbackVH Class Implementation
//===----------------------------------------------------------------------===//

void ScalarEvolution::SCEVCallbackVH::deleted() { … }

void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) { … }

ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
  : … { … }

//===----------------------------------------------------------------------===//
//                   ScalarEvolution Class Implementation
//===----------------------------------------------------------------------===//

ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
                                 AssumptionCache &AC, DominatorTree &DT,
                                 LoopInfo &LI)
    : … { … }

ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
    : … { … }

ScalarEvolution::~ScalarEvolution() { … }

bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) { … }

/// When printing a top-level SCEV for trip counts, it's helpful to include
/// a type for constants which are otherwise hard to disambiguate.
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) { … }
} // namespace llvm

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> { … };

} // end anonymous namespace

const SCEV *
ScalarEvolution::rewriteUsingPredicate(const SCEV *S, const Loop *L,
                                       const SCEVPredicate &Preds) { … }

const SCEVAddRecExpr *ScalarEvolution::convertSCEVToAddRecWithPredicates(
    const SCEV *S, const Loop *L,
    SmallVectorImpl<const SCEVPredicate *> &Preds) { … }

/// SCEV predicates
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) { … }

/// Union predicates don't get cached so create a dummy set ID for it.
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() { … }

unsigned PredicatedScalarEvolution::getSmallConstantMaxTripCount() { … }

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 { … }

// Match the mathematical pattern A - (A / B) * B, where A and B can be
// arbitrary expressions. Also match zext (trunc A to iB) to iY, which is used
// for URem with constant power-of-2 second operands.
// It's not always easy, as A and B can be folded (imagine A is X / 2, and B is
// 4, A / B becomes X / 8).
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) { … }