Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//

//

// 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

//

//===----------------------------------------------------------------------===//

//

// The ScalarEvolution class is an LLVM pass which can be used to analyze and

// categorize scalar expressions in loops.  It specializes in recognizing

// general induction variables, representing them with the abstract and opaque

// SCEV class.  Given this analysis, trip counts of loops and other important

// properties can be obtained.

//

// This analysis is primarily useful for induction variable substitution and

// strength reduction.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H

#define LLVM_ANALYSIS_SCALAREVOLUTION_H

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/DenseMapInfo.h"

#include "llvm/ADT/FoldingSet.h"

#include "llvm/ADT/PointerIntPair.h"

#include "llvm/ADT/SetVector.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/IR/ConstantRange.h"

#include "llvm/IR/InstrTypes.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/IR/ValueMap.h"

#include "llvm/Pass.h"

#include <cassert>

#include <cstdint>

#include <memory>

#include <optional>

#include <utility>

namespace llvm {

class OverflowingBinaryOperator;

class AssumptionCache;

class BasicBlock;

class Constant;

class ConstantInt;

class DataLayout;

class DominatorTree;

class Function;

class GEPOperator;

class Instruction;

class LLVMContext;

class Loop;

class LoopInfo;

class raw_ostream;

class ScalarEvolution;

class SCEVAddRecExpr;

class SCEVUnknown;

class StructType;

class TargetLibraryInfo;

class Type;

class Value;

enum SCEVTypes : unsigned short;

extern bool VerifySCEV;

/// This class represents an analyzed expression in the program.  These are

/// opaque objects that the client is not allowed to do much with directly.

///

class SCEV : public FoldingSetNode {

  friend struct FoldingSetTrait<SCEV>;

  /// A reference to an Interned FoldingSetNodeID for this node.  The

  /// ScalarEvolution's BumpPtrAllocator holds the data.

  FoldingSetNodeIDRef FastID;

  // The SCEV baseclass this node corresponds to

  const SCEVTypes SCEVType;

protected:

  // Estimated complexity of this node's expression tree size.

  const unsigned short ExpressionSize;

  /// This field is initialized to zero and may be used in subclasses to store

  /// miscellaneous information.

  unsigned short SubclassData = 0;

public:

  /// NoWrapFlags are bitfield indices into SubclassData.

  ///

  /// Add and Mul expressions may have no-unsigned-wrap <NUW> or

  /// no-signed-wrap <NSW> properties, which are derived from the IR

  /// operator. NSW is a misnomer that we use to mean no signed overflow or

  /// underflow.

  ///

  /// AddRec expressions may have a no-self-wraparound <NW> property if, in

  /// the integer domain, abs(step) * max-iteration(loop) <=

  /// unsigned-max(bitwidth).  This means that the recurrence will never reach

  /// its start value if the step is non-zero.  Computing the same value on

  /// each iteration is not considered wrapping, and recurrences with step = 0

  /// are trivially <NW>.  <NW> is independent of the sign of step and the

  /// value the add recurrence starts with.

  ///

  /// Note that NUW and NSW are also valid properties of a recurrence, and

  /// either implies NW. For convenience, NW will be set for a recurrence

  /// whenever either NUW or NSW are set.

  ///

  /// We require that the flag on a SCEV apply to the entire scope in which

  /// that SCEV is defined.  A SCEV's scope is set of locations dominated by

  /// a defining location, which is in turn described by the following rules:

  /// * A SCEVUnknown is at the point of definition of the Value.

  /// * A SCEVConstant is defined at all points.

  /// * A SCEVAddRec is defined starting with the header of the associated

  ///   loop.

  /// * All other SCEVs are defined at the earlest point all operands are

  ///   defined.

  ///

  /// The above rules describe a maximally hoisted form (without regards to

  /// potential control dependence).  A SCEV is defined anywhere a

  /// corresponding instruction could be defined in said maximally hoisted

  /// form.  Note that SCEVUDivExpr (currently the only expression type which

  /// can trap) can be defined per these rules in regions where it would trap

  /// at runtime.  A SCEV being defined does not require the existence of any

  /// instruction within the defined scope.

  enum NoWrapFlags {

    FlagAnyWrap = 0,    // No guarantee.

    FlagNW = (1 << 0),  // No self-wrap.

    FlagNUW = (1 << 1), // No unsigned wrap.

    FlagNSW = (1 << 2), // No signed wrap.

    NoWrapMask = (1 << 3) - 1

  };

  explicit SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy,

                unsigned short ExpressionSize)

      : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {}

  SCEV(const SCEV &) = delete;

  SCEV &operator=(const SCEV &) = delete;

  SCEVTypes getSCEVType() const { return SCEVType; }

  /// Return the LLVM type of this SCEV expression.

  Type *getType() const;

  /// Return operands of this SCEV expression.

  ArrayRef<const SCEV *> operands() const;

  /// Return true if the expression is a constant zero.

  bool isZero() const;

  /// Return true if the expression is a constant one.

  bool isOne() const;

  /// Return true if the expression is a constant all-ones value.

  bool isAllOnesValue() const;

  /// Return true if the specified scev is negated, but not a constant.

  bool isNonConstantNegative() const;

  // Returns estimated size of the mathematical expression represented by this

  // SCEV. The rules of its calculation are following:

  // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1;

  // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula:

  //    (1 + Size(Op1) + ... + Size(OpN)).

  // This value gives us an estimation of time we need to traverse through this

  // SCEV and all its operands recursively. We may use it to avoid performing

  // heavy transformations on SCEVs of excessive size for sake of saving the

  // compilation time.

  unsigned short getExpressionSize() const {

    return ExpressionSize;

  }

  /// Print out the internal representation of this scalar to the specified

  /// stream.  This should really only be used for debugging purposes.

  void print(raw_ostream &OS) const;

  /// This method is used for debugging.

  void dump() const;

};

// Specialize FoldingSetTrait for SCEV to avoid needing to compute

// temporary FoldingSetNodeID values.

template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {

  static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; }

  static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash,

                     FoldingSetNodeID &TempID) {

    return ID == X.FastID;

  }

  static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {

    return X.FastID.ComputeHash();

  }

};

inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {

  S.print(OS);

  return OS;

}

/// An object of this class is returned by queries that could not be answered.

/// For example, if you ask for the number of iterations of a linked-list

/// traversal loop, you will get one of these.  None of the standard SCEV

/// operations are valid on this class, it is just a marker.

struct SCEVCouldNotCompute : public SCEV {

  SCEVCouldNotCompute();

  /// Methods for support type inquiry through isa, cast, and dyn_cast:

  static bool classof(const SCEV *S);

};

/// This class represents an assumption made using SCEV expressions which can

/// be checked at run-time.

class SCEVPredicate : public FoldingSetNode {

  friend struct FoldingSetTrait<SCEVPredicate>;

  /// A reference to an Interned FoldingSetNodeID for this node.  The

  /// ScalarEvolution's BumpPtrAllocator holds the data.

  FoldingSetNodeIDRef FastID;

public:

  enum SCEVPredicateKind { P_Union, P_Compare, P_Wrap };

protected:

  SCEVPredicateKind Kind;

  ~SCEVPredicate() = default;

  SCEVPredicate(const SCEVPredicate &) = default;

  SCEVPredicate &operator=(const SCEVPredicate &) = default;

public:

  SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind);

  SCEVPredicateKind getKind() const { return Kind; }

  /// Returns the estimated complexity of this predicate.  This is roughly

  /// measured in the number of run-time checks required.

  virtual unsigned getComplexity() const { return 1; }

  /// Returns true if the predicate is always true. This means that no

  /// assumptions were made and nothing needs to be checked at run-time.

  virtual bool isAlwaysTrue() const = 0;

  /// Returns true if this predicate implies \p N.

  virtual bool implies(const SCEVPredicate *N) const = 0;

  /// Prints a textual representation of this predicate with an indentation of

  /// \p Depth.

  virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0;

};

inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) {

  P.print(OS);

  return OS;

}

// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute

// temporary FoldingSetNodeID values.

template <>

struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> {

  static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) {

    ID = X.FastID;

  }

  static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID,

                     unsigned IDHash, FoldingSetNodeID &TempID) {

    return ID == X.FastID;

  }

  static unsigned ComputeHash(const SCEVPredicate &X,

                              FoldingSetNodeID &TempID) {

    return X.FastID.ComputeHash();

  }

};

/// This class represents an assumption that the expression LHS Pred RHS

/// evaluates to true, and this can be checked at run-time.

class SCEVComparePredicate final : public SCEVPredicate {

  /// We assume that LHS Pred RHS is true.

  const ICmpInst::Predicate Pred;

  const SCEV *LHS;

  const SCEV *RHS;

public:

  SCEVComparePredicate(const FoldingSetNodeIDRef ID,

                       const ICmpInst::Predicate Pred,

                       const SCEV *LHS, const SCEV *RHS);

  /// Implementation of the SCEVPredicate interface

  bool implies(const SCEVPredicate *N) const override;

  void print(raw_ostream &OS, unsigned Depth = 0) const override;

  bool isAlwaysTrue() const override;

  ICmpInst::Predicate getPredicate() const { return Pred; }

  /// Returns the left hand side of the predicate.

  const SCEV *getLHS() const { return LHS; }

  /// Returns the right hand side of the predicate.

  const SCEV *getRHS() const { return RHS; }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:

  static bool classof(const SCEVPredicate *P) {

    return P->getKind() == P_Compare;

  }

};

/// This class represents an assumption made on an AddRec expression. Given an

/// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw

/// flags (defined below) in the first X iterations of the loop, where X is a

/// SCEV expression returned by getPredicatedBackedgeTakenCount).

///

/// Note that this does not imply that X is equal to the backedge taken

/// count. This means that if we have a nusw predicate for i32 {0,+,1} with a

/// predicated backedge taken count of X, we only guarantee that {0,+,1} has

/// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we

/// have more than X iterations.

class SCEVWrapPredicate final : public SCEVPredicate {

public:

  /// Similar to SCEV::NoWrapFlags, but with slightly different semantics

  /// for FlagNUSW. The increment is considered to be signed, and a + b

  /// (where b is the increment) is considered to wrap if:

  ///    zext(a + b) != zext(a) + sext(b)

  ///

  /// If Signed is a function that takes an n-bit tuple and maps to the

  /// integer domain as the tuples value interpreted as twos complement,

  /// and Unsigned a function that takes an n-bit tuple and maps to the

  /// integer domain as as the base two value of input tuple, then a + b

  /// has IncrementNUSW iff:

  ///

  /// 0 <= Unsigned(a) + Signed(b) < 2^n

  ///

  /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW.

  ///

  /// Note that the IncrementNUSW flag is not commutative: if base + inc

  /// has IncrementNUSW, then inc + base doesn't neccessarily have this

  /// property. The reason for this is that this is used for sign/zero

  /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is

  /// assumed. A {base,+,inc} expression is already non-commutative with

  /// regards to base and inc, since it is interpreted as:

  ///     (((base + inc) + inc) + inc) ...

  enum IncrementWrapFlags {

    IncrementAnyWrap = 0,     // No guarantee.

    IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap.

    IncrementNSSW = (1 << 1), // No signed with signed increment wrap

                              // (equivalent with SCEV::NSW)

    IncrementNoWrapMask = (1 << 2) - 1

  };

  /// Convenient IncrementWrapFlags manipulation methods.

  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags

  clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,

             SCEVWrapPredicate::IncrementWrapFlags OffFlags) {

    assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");

    assert((OffFlags & IncrementNoWrapMask) == OffFlags &&

           "Invalid flags value!");

    return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags);

  }

  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags

  maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) {

    assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");

    assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!");

    return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask);

  }

  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags

  setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags,

           SCEVWrapPredicate::IncrementWrapFlags OnFlags) {

    assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!");

    assert((OnFlags & IncrementNoWrapMask) == OnFlags &&

           "Invalid flags value!");

    return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags);

  }

  /// Returns the set of SCEVWrapPredicate no wrap flags implied by a

  /// SCEVAddRecExpr.

  [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags

  getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE);

private:

  const SCEVAddRecExpr *AR;

  IncrementWrapFlags Flags;

public:

  explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID,

                             const SCEVAddRecExpr *AR,

                             IncrementWrapFlags Flags);

  /// Returns the set assumed no overflow flags.

  IncrementWrapFlags getFlags() const { return Flags; }

  /// Implementation of the SCEVPredicate interface

  const SCEVAddRecExpr *getExpr() const;

  bool implies(const SCEVPredicate *N) const override;

  void print(raw_ostream &OS, unsigned Depth = 0) const override;

  bool isAlwaysTrue() const override;

  /// Methods for support type inquiry through isa, cast, and dyn_cast:

  static bool classof(const SCEVPredicate *P) {

    return P->getKind() == P_Wrap;

  }

};

/// This class represents a composition of other SCEV predicates, and is the

/// class that most clients will interact with.  This is equivalent to a

/// logical "AND" of all the predicates in the union.

///

/// NB! Unlike other SCEVPredicate sub-classes this class does not live in the

/// ScalarEvolution::Preds folding set.  This is why the \c add function is sound.

class SCEVUnionPredicate final : public SCEVPredicate {

private:

  using PredicateMap =

      DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>;

  /// Vector with references to all predicates in this union.

  SmallVector<const SCEVPredicate *, 16> Preds;

  /// Adds a predicate to this union.

  void add(const SCEVPredicate *N);

public:

  SCEVUnionPredicate(ArrayRef<const SCEVPredicate *> Preds);

  const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const {

    return Preds;

  }

  /// Implementation of the SCEVPredicate interface

  bool isAlwaysTrue() const override;

  bool implies(const SCEVPredicate *N) const override;

  void print(raw_ostream &OS, unsigned Depth) const override;

  /// We estimate the complexity of a union predicate as the size number of

  /// predicates in the union.

  unsigned getComplexity() const override { return Preds.size(); }

  /// Methods for support type inquiry through isa, cast, and dyn_cast:

  static bool classof(const SCEVPredicate *P) {

    return P->getKind() == P_Union;

  }

};

/// The main scalar evolution driver. Because client code (intentionally)

/// can't do much with the SCEV objects directly, they must ask this class

/// for services.

class ScalarEvolution {

  friend class ScalarEvolutionsTest;

public:

  /// An enum describing the relationship between a SCEV and a loop.

  enum LoopDisposition {

    LoopVariant,   ///< The SCEV is loop-variant (unknown).

    LoopInvariant, ///< The SCEV is loop-invariant.

    LoopComputable ///< The SCEV varies predictably with the loop.

  };

  /// An enum describing the relationship between a SCEV and a basic block.

  enum BlockDisposition {

    DoesNotDominateBlock,  ///< The SCEV does not dominate the block.

    DominatesBlock,        ///< The SCEV dominates the block.

    ProperlyDominatesBlock ///< The SCEV properly dominates the block.

  };

  /// Convenient NoWrapFlags manipulation that hides enum casts and is

  /// visible in the ScalarEvolution name space.

  [[nodiscard]] static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags,

                                                   int Mask) {

    return (SCEV::NoWrapFlags)(Flags & Mask);

  }

  [[nodiscard]] static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags,

                                                  SCEV::NoWrapFlags OnFlags) {

    return (SCEV::NoWrapFlags)(Flags | OnFlags);

  }

  [[nodiscard]] static SCEV::NoWrapFlags

  clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {

    return (SCEV::NoWrapFlags)(Flags & ~OffFlags);

  }

  [[nodiscard]] static bool hasFlags(SCEV::NoWrapFlags Flags,

                                     SCEV::NoWrapFlags TestFlags) {

    return TestFlags == maskFlags(Flags, TestFlags);

  };

  ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,

                  DominatorTree &DT, LoopInfo &LI);

  ScalarEvolution(ScalarEvolution &&Arg);

  ~ScalarEvolution();

  LLVMContext &getContext() const { return F.getContext(); }

  /// 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 isSCEVable(Type *Ty) const;

  /// Return the size in bits of the specified type, for which isSCEVable must

  /// return true.

  uint64_t 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-sized integer type.

  Type *getEffectiveSCEVType(Type *Ty) const;

  // Returns a wider type among {Ty1, Ty2}.

  Type *getWiderType(Type *Ty1, Type *Ty2) const;

  /// Return true if there exists a point in the program at which both

  /// A and B could be operands to the same instruction.

  /// SCEV expressions are generally assumed to correspond to instructions

  /// which could exists in IR.  In general, this requires that there exists

  /// a use point in the program where all operands dominate the use.

  ///

  /// Example:

  /// loop {

  ///   if

  ///     loop { v1 = load @global1; }

  ///   else

  ///     loop { v2 = load @global2; }

  /// }

  /// No SCEV with operand V1, and v2 can exist in this program.

  bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B);

  /// Return true if the SCEV is a scAddRecExpr or it contains

  /// scAddRecExpr. The result will be cached in HasRecMap.

  bool containsAddRecurrence(const SCEV *S);

  /// Is operation \p BinOp between \p LHS and \p RHS provably does not have

  /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the

  /// no-overflow fact should be true in the context of this instruction.

  bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,

                       const SCEV *LHS, const SCEV *RHS,

                       const Instruction *CtxI = nullptr);

  /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into

  /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet.

  /// Does not mutate the original instruction. Returns std::nullopt if it could

  /// not deduce more precise flags than the instruction already has, otherwise

  /// returns proven flags.

  std::optional<SCEV::NoWrapFlags>

  getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO);

  /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops.

  void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops);

  /// Return true if the SCEV expression contains an undef value.

  bool containsUndefs(const SCEV *S) const;

  /// Return true if the SCEV expression contains a Value that has been

  /// optimised out and is now a nullptr.

  bool containsErasedValue(const SCEV *S) const;

  /// Return a SCEV expression for the full generality of the specified

  /// expression.

  const SCEV *getSCEV(Value *V);

  const SCEV *getConstant(ConstantInt *V);

  const SCEV *getConstant(const APInt &Val);

  const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);

  const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);

  const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);

  const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);

  const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);

  const SCEV *getZeroExtendExprImpl(const SCEV *Op, Type *Ty,

                                    unsigned Depth = 0);

  const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);

  const SCEV *getSignExtendExprImpl(const SCEV *Op, Type *Ty,

                                    unsigned Depth = 0);

  const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);

  const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);

  const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0);

  const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0) {

    SmallVector<const SCEV *, 2> Ops = {LHS, RHS};

    return getAddExpr(Ops, Flags, Depth);

  }

  const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0) {

    SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};

    return getAddExpr(Ops, Flags, Depth);

  }

  const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0);

  const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0) {

    SmallVector<const SCEV *, 2> Ops = {LHS, RHS};

    return getMulExpr(Ops, Flags, Depth);

  }

  const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,

                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                         unsigned Depth = 0) {

    SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};

    return getMulExpr(Ops, Flags, Depth);

  }

  const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,

                            SCEV::NoWrapFlags Flags);

  const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,

                            const Loop *L, SCEV::NoWrapFlags Flags);

  const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,

                            const Loop *L, SCEV::NoWrapFlags Flags) {

    SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end());

    return getAddRecExpr(NewOp, L, Flags);

  }

  /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some

  /// Predicates. If successful return these <AddRecExpr, Predicates>;

  /// The function is intended to be called from PSCEV (the caller will decide

  /// whether to actually add the predicates and carry out the rewrites).

  std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>

  createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI);

  /// Returns an expression for a GEP

  ///

  /// \p GEP The GEP. The indices contained in the GEP itself are ignored,

  /// instead we use IndexExprs.

  /// \p IndexExprs The expressions for the indices.

  const SCEV *getGEPExpr(GEPOperator *GEP,

                         const SmallVectorImpl<const SCEV *> &IndexExprs);

  const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW);

  const SCEV *getMinMaxExpr(SCEVTypes Kind,

                            SmallVectorImpl<const SCEV *> &Operands);

  const SCEV *getSequentialMinMaxExpr(SCEVTypes Kind,

                                      SmallVectorImpl<const SCEV *> &Operands);

  const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands);

  const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands);

  const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS);

  const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands);

  const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS,

                          bool Sequential = false);

  const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands,

                          bool Sequential = false);

  const SCEV *getUnknown(Value *V);

  const SCEV *getCouldNotCompute();

  /// Return a SCEV for the constant 0 of a specific type.

  const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); }

  /// Return a SCEV for the constant 1 of a specific type.

  const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }

  /// Return a SCEV for the constant -1 of a specific type.

  const SCEV *getMinusOne(Type *Ty) {

    return getConstant(Ty, -1, /*isSigned=*/true);

  }

  /// Return an expression for sizeof ScalableTy that is type IntTy, where

  /// ScalableTy is a scalable vector type.

  const SCEV *getSizeOfScalableVectorExpr(Type *IntTy,

                                          ScalableVectorType *ScalableTy);

  /// Return an expression for the alloc size of AllocTy that is type IntTy

  const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);

  /// Return an expression for the store size of StoreTy that is type IntTy

  const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);

  /// Return an expression for offsetof on the given field with type IntTy

  const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo);

  /// Return the SCEV object corresponding to -V.

  const SCEV *getNegativeSCEV(const SCEV *V,

                              SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);

  /// Return the SCEV object corresponding to ~V.

  const SCEV *getNotSCEV(const SCEV *V);

  /// Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.

  ///

  /// If the LHS and RHS are pointers which don't share a common base

  /// (according to getPointerBase()), this returns a SCEVCouldNotCompute.

  /// To compute the difference between two unrelated pointers, you can

  /// explicitly convert the arguments using getPtrToIntExpr(), for pointer

  /// types that support it.

  const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,

                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,

                           unsigned Depth = 0);

  /// Compute ceil(N / D). N and D are treated as unsigned values.

  ///

  /// Since SCEV doesn't have native ceiling division, this generates a

  /// SCEV expression of the following form:

  ///

  /// umin(N, 1) + floor((N - umin(N, 1)) / D)

  ///

  /// A denominator of zero or poison is handled the same way as getUDivExpr().

  const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type.  If the type must be extended, it is zero extended.

  const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty,

                                      unsigned Depth = 0);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type.  If the type must be extended, it is sign extended.

  const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty,

                                      unsigned Depth = 0);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type.  If the type must be extended, it is zero extended.  The

  /// conversion must not be narrowing.

  const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type.  If the type must be extended, it is sign extended.  The

  /// conversion must not be narrowing.

  const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type. If the type must be extended, it is extended with

  /// unspecified bits. The conversion must not be narrowing.

  const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty);

  /// Return a SCEV corresponding to a conversion of the input value to the

  /// specified type.  The conversion must not be widening.

  const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty);

  /// Promote the operands to the wider of the types using zero-extension, and

  /// then perform a umax operation with them.

  const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS);

  /// Promote the operands to the wider of the types using zero-extension, and

  /// then perform a umin operation with them.

  const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS,

                                         bool Sequential = false);

  /// Promote the operands to the wider of the types using zero-extension, and

  /// then perform a umin operation with them. N-ary function.

  const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops,

                                         bool Sequential = false);

  /// Transitively follow the chain of pointer-type operands until reaching a

  /// SCEV that does not have a single pointer operand. This returns a

  /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner

  /// cases do exist.

  const SCEV *getPointerBase(const SCEV *V);

  /// Compute an expression equivalent to S - getPointerBase(S).

  const SCEV *removePointerBase(const SCEV *S);

  /// Return a SCEV expression for the specified value at the specified scope

  /// in the program.  The L value specifies a loop nest to evaluate the

  /// expression at, where null is the top-level or a specified loop is

  /// immediately inside of the loop.

  ///

  /// This method can be used to compute the exit value for a variable defined

  /// in a loop by querying what the value will hold in the parent loop.

  ///

  /// In the case that a relevant loop exit value cannot be computed, the

  /// original value V is returned.

  const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L);

  /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L).

  const SCEV *getSCEVAtScope(Value *V, const Loop *L);

  /// Test whether entry to the loop is protected by a conditional between LHS

  /// and RHS.  This is used to help avoid max expressions in loop trip

  /// counts, and to eliminate casts.

  bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,

                                const SCEV *LHS, const SCEV *RHS);

  /// Test whether entry to the basic block is protected by a conditional

  /// between LHS and RHS.

  bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB,

                                      ICmpInst::Predicate Pred, const SCEV *LHS,

                                      const SCEV *RHS);

  /// Test whether the backedge of the loop is protected by a conditional

  /// between LHS and RHS.  This is used to eliminate casts.

  bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred,

                                   const SCEV *LHS, const SCEV *RHS);

  /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip

  /// count".  A "trip count" is the number of times the header of the loop

  /// will execute if an exit is taken after the specified number of backedges

  /// have been taken.  (e.g. TripCount = ExitCount + 1).  Note that the

  /// expression can overflow if ExitCount = UINT_MAX.  \p Extend controls

  /// how potential overflow is handled.  If true, a wider result type is

  /// returned. ex: EC = 255 (i8), TC = 256 (i9).  If false, result unsigned

  /// wraps with 2s-complement semantics.  ex: EC = 255 (i8), TC = 0 (i8)

  const SCEV *getTripCountFromExitCount(const SCEV *ExitCount,

                                        bool Extend = true);

  /// Returns the exact trip count of the loop if we can compute it, and

  /// the result is a small constant.  '0' is used to represent an unknown

  /// or non-constant trip count.  Note that a trip count is simply one more

  /// than the backedge taken count for the loop.

  unsigned getSmallConstantTripCount(const Loop *L);

  /// Return the exact trip count for this loop if we exit through ExitingBlock.

  /// '0' is used to represent an unknown or non-constant trip count.  Note

  /// that a trip count is simply one more than the backedge taken count for