LoopVectorizationLegality.h

Go to the documentation of this file.

//===- llvm/Transforms/Vectorize/LoopVectorizationLegality.h ----*- 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
//
//===----------------------------------------------------------------------===//
//
/// \file
/// This file defines the LoopVectorizationLegality class. Original code
/// in Loop Vectorizer has been moved out to its own file for modularity
/// and reusability.
///
/// Currently, it works for innermost loop vectorization. Extending this to
/// outer loop vectorization is a TODO item.
///
/// Also provides:
/// 1) LoopVectorizeHints class which keeps a number of loop annotations
/// locally for easy look up. It has the ability to write them back as
/// loop metadata, upon request.
/// 2) LoopVectorizationRequirements class for lazy bail out for the purpose
/// of reporting useful failure to vectorize message.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H
#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H
 
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/TypeSize.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
 
namespace llvm {
class AssumptionCache;
class BasicBlock;
class DemandedBits;
class DominatorTree;
class Function;
class Loop;
class LoopInfo;
class Metadata;
class OptimizationRemarkEmitter;
class PredicatedScalarEvolution;
class TargetLibraryInfo;
class TargetTransformInfo;
class Type;
struct VectorizeOptions;
 
/// Utility class for getting and setting loop vectorizer hints in the form
/// of loop metadata.
/// This class keeps a number of loop annotations locally (as member variables)
/// and can, upon request, write them back as metadata on the loop. It will
/// initially scan the loop for existing metadata, and will update the local
/// values based on information in the loop.
/// We cannot write all values to metadata, as the mere presence of some info,
/// for example 'force', means a decision has been made. So, we need to be
/// careful NOT to add them if the user hasn't specifically asked so.
class LoopVectorizeHints {
  enum HintKind { HK_WIDTH, HK_INTERLEAVE, HK_ISVECTORIZED };
 
  /// Hint - associates name and validation with the hint value.
  struct Hint {
    const char *Name;
    unsigned Value; // This may have to change for non-numeric values.
    HintKind Kind;
 
    Hint(const char *Name, unsigned Value, HintKind Kind)
        : Name(Name), Value(Value), Kind(Kind) {}
 
    LLVM_ABI bool validate(unsigned Val);
  };
 
  const VectorizeOptions &Opts;
 
  /// Vectorization width.
  Hint Width;
 
  /// Vectorization interleave factor.
  Hint Interleave;
 
  /// Vectorization forced; one of ForceKind. Carried as a plain value because
  /// the enable/disable pair is a standalone tag with no operand to validate.
  unsigned Force;
 
  /// Already Vectorized
  Hint IsVectorized;
 
  /// Vector Predicate; one of ForceKind, carried as a plain value like Force.
  unsigned Predicate;
 
  /// Scalable vs fixed-width preference; one of ScalableForceKind. Carried as
  /// a plain value because the enable/disable pair has no operand to validate.
  unsigned Scalable;
 
  /// Return the loop metadata prefix.
  static StringRef Prefix() { return "llvm.loop."; }
 
  /// True if there is any unsafe math in the loop.
  bool PotentiallyUnsafe = false;
 
public:
  enum ForceKind {
    FK_Undefined = -1, ///< Not selected.
    FK_Disabled = 0,   ///< Forcing disabled.
    FK_Enabled = 1,    ///< Forcing enabled.
  };
 
  enum ScalableForceKind {
    /// Not selected.
    SK_Unspecified = -1,
    /// Disables vectorization with scalable vectors.
    SK_FixedWidthOnly = 0,
    /// Vectorize loops using scalable vectors or fixed-width vectors, but favor
    /// scalable vectors when the cost-model is inconclusive. This is the
    /// default when the scalable.enable hint is enabled through a pragma.
    SK_PreferScalable = 1,
    /// Always vectorize loops using scalable vectors if feasible (i.e. the plan
    /// has a valid cost and is not restricted by fixed-length dependence
    /// distances).
    SK_AlwaysScalable = 2
  };
 
  LLVM_ABI LoopVectorizeHints(const VectorizeOptions &Opts, const Loop *L,
                              bool InterleaveOnlyWhenForced,
                              OptimizationRemarkEmitter &ORE,
                              const TargetTransformInfo *TTI = nullptr);
 
  /// Mark the loop L as already vectorized by setting the width to 1.
  LLVM_ABI void setAlreadyVectorized();
 
  LLVM_ABI bool allowVectorization(Loop *L, bool VectorizeOnlyWhenForced) const;
 
  /// Dumps all the hint information.
  LLVM_ABI void emitRemarkWithHints() const;
 
  ElementCount getWidth() const {
    return ElementCount::get(
        Width.Value, (ScalableForceKind)Scalable == SK_PreferScalable ||
                         (ScalableForceKind)Scalable == SK_AlwaysScalable);
  }
 
  unsigned getInterleave() const {
    if (Interleave.Value)
      return Interleave.Value;
    // If interleaving is not explicitly set, assume that if we do not want
    // unrolling, we also don't want any interleaving.
    if (llvm::hasUnrollTransformation(TheLoop) & TM_Disable)
      return 1;
    return 0;
  }
  unsigned getIsVectorized() const { return IsVectorized.Value; }
  unsigned getPredicate() const { return Predicate; }
  enum ForceKind getForce() const {
    if ((ForceKind)Force == FK_Undefined &&
        hasDisableAllTransformsHint(TheLoop))
      return FK_Disabled;
    return (ForceKind)Force;
  }
 
  /// \return true if scalable vectorization has been explicitly disabled.
  bool isScalableVectorizationDisabled() const {
    return (ScalableForceKind)Scalable == SK_FixedWidthOnly;
  }
 
  /// \return true if scalable vectorization is always preferred over
  /// fixed-length when feasible, regardless of cost.
  bool isScalableVectorizationAlwaysPreferred() const {
    return (ScalableForceKind)Scalable == SK_AlwaysScalable;
  }
 
  /// When enabling loop hints are provided we allow the vectorizer to change
  /// the order of operations that is given by the scalar loop. This is not
  /// enabled by default because can be unsafe or inefficient. For example,
  /// reordering floating-point operations will change the way round-off
  /// error accumulates in the loop.
  LLVM_ABI bool allowReordering() const;
 
  bool isPotentiallyUnsafe() const {
    // Avoid FP vectorization if the target is unsure about proper support.
    // This may be related to the SIMD unit in the target not handling
    // IEEE 754 FP ops properly, or bad single-to-double promotions.
    // Otherwise, a sequence of vectorized loops, even without reduction,
    // could lead to different end results on the destination vectors.
    return getForce() != LoopVectorizeHints::FK_Enabled && PotentiallyUnsafe;
  }
 
  void setPotentiallyUnsafe() { PotentiallyUnsafe = true; }
 
private:
  /// Find hints specified in the loop metadata and update local values.
  void getHintsFromMetadata();
 
  /// Checks string hint with one operand and set value if valid.
  void setHint(StringRef Name, Metadata *Arg);
 
  /// The loop these hints belong to.
  const Loop *TheLoop;
 
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter &ORE;
 
  /// Reports a condition where loop vectorization is disallowed: prints
  /// \p DebugMsg for debugging purposes along with the corresponding
  /// optimization remark \p RemarkName, with \p RemarkMsg as the user-facing
  /// message. The loop \p L is used for the location of the remark.
  void reportDisallowedVectorization(const StringRef DebugMsg,
                                     const StringRef RemarkName,
                                     const StringRef RemarkMsg,
                                     const Loop *L) const;
};
 
/// This holds vectorization requirements that must be verified late in
/// the process. The requirements are set by legalize and costmodel. Once
/// vectorization has been determined to be possible and profitable the
/// requirements can be verified by looking for metadata or compiler options.
/// For example, some loops require FP commutativity which is only allowed if
/// vectorization is explicitly specified or if the fast-math compiler option
/// has been provided.
/// Late evaluation of these requirements allows helpful diagnostics to be
/// composed that tells the user what need to be done to vectorize the loop. For
/// example, by specifying #pragma clang loop vectorize or -ffast-math. Late
/// evaluation should be used only when diagnostics can generated that can be
/// followed by a non-expert user.
class LoopVectorizationRequirements {
public:
  /// Track the 1st floating-point instruction that can not be reassociated.
  void addExactFPMathInst(Instruction *I) {
    if (I && !ExactFPMathInst)
      ExactFPMathInst = I;
  }
 
  Instruction *getExactFPInst() { return ExactFPMathInst; }
 
private:
  Instruction *ExactFPMathInst = nullptr;
};
 
/// This holds details about a histogram operation -- a load -> update -> store
/// sequence where each lane in a vector might be updating the same element as
/// another lane.
struct HistogramInfo {
  LoadInst *Load;
  Instruction *Update;
  StoreInst *Store;
  /// The update operation applied to the histogram buckets.
  HistogramUpdateKind UpdateKind;
 
  HistogramInfo(LoadInst *Load, Instruction *Update, StoreInst *Store,
                HistogramUpdateKind UpdateKind)
      : Load(Load), Update(Update), Store(Store), UpdateKind(UpdateKind) {}
};
 
/// Holds details about a "compressed" pointer: the conditional induction PHI
/// used to derive the pointer and the SCEV expression for the pointer.
struct CompressedPtrInfo {
  PHINode *ConditionalInductionPHI;
  const SCEVAddRecExpr *PtrSCEV;
};
 
/// Indicates the characteristics of a loop with an uncountable exit.
/// * None      -- No uncountable exit present.
/// * ReadOnly  -- At least one uncountable exit in a readonly loop.
/// * ReadWrite -- At least one uncountable exit in a loop with side effects
///                that may require masking.
enum class UncountableExitTrait { None, ReadOnly, ReadWrite };
 
/// LoopVectorizationLegality checks if it is legal to vectorize a loop, and
/// to what vectorization factor.
/// This class does not look at the profitability of vectorization, only the
/// legality. This class has two main kinds of checks:
/// * Memory checks - The code in canVectorizeMemory checks if vectorization
///   will change the order of memory accesses in a way that will change the
///   correctness of the program.
/// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
/// checks for a number of different conditions, such as the availability of a
/// single induction variable, that all types are supported and vectorize-able,
/// etc. It also identifies the induction and reduction variables of the loop.
class LoopVectorizationLegality {
public:
  LoopVectorizationLegality(const VectorizeOptions &Opts, Loop *L,
                            PredicatedScalarEvolution &PSE, DominatorTree *DT,
                            TargetTransformInfo *TTI, TargetLibraryInfo *TLI,
                            Function *F, LoopAccessInfoManager &LAIs,
                            LoopInfo *LI, OptimizationRemarkEmitter *ORE,
                            LoopVectorizationRequirements *R,
                            LoopVectorizeHints *H, DemandedBits *DB,
                            AssumptionCache *AC, bool AllowRuntimeSCEVChecks,
                            AAResults *AA)
      : Opts(Opts), TheLoop(L), LI(LI), PSE(PSE), TTI(TTI), TLI(TLI), DT(DT),
        LAIs(LAIs), ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC),
        AllowRuntimeSCEVChecks(AllowRuntimeSCEVChecks), AA(AA) {}
 
  /// ReductionList contains the reduction descriptors for all
  /// of the reductions that were found in the loop.
  using ReductionList = MapVector<PHINode *, RecurrenceDescriptor>;
 
  /// InductionList saves induction variables and maps them to the
  /// induction descriptor.
  using InductionList = MapVector<PHINode *, InductionDescriptor>;
 
  /// ConditionalInductionList saves conditional inductions and maps them to
  /// their descriptors.
  using ConditionalInductionList =
      MapVector<PHINode *, ConditionalInductionDescriptor>;
 
  /// RecurrenceSet contains the phi nodes that are recurrences other than
  /// inductions and reductions.
  using RecurrenceSet = SmallPtrSet<const PHINode *, 8>;
 
  /// Returns true if it is legal to vectorize this loop.
  /// This does not mean that it is profitable to vectorize this
  /// loop, only that it is legal to do so.
  /// Temporarily taking UseVPlanNativePath parameter. If true, take
  /// the new code path being implemented for outer loop vectorization
  /// (should be functional for inner loop vectorization) based on VPlan.
  /// If false, good old LV code.
  LLVM_ABI bool canVectorize(bool UseVPlanNativePath);
 
  /// Returns true if it is legal to vectorize the FP math operations in this
  /// loop. Vectorizing is legal if we allow reordering of FP operations, or if
  /// we can use in-order reductions.
  LLVM_ABI bool canVectorizeFPMath(bool EnableStrictReductions);
 
  /// Return true if we can vectorize this loop while folding its tail by
  /// masking.
  LLVM_ABI bool canFoldTailByMasking() const;
 
  /// Mark all respective loads/stores for masking. Must only be called when
  /// tail-folding is possible.
  LLVM_ABI void prepareToFoldTailByMasking();
 
  /// Returns the primary induction variable.
  PHINode *getPrimaryInduction() { return PrimaryInduction; }
 
  /// Returns the reduction variables found in the loop.
  const ReductionList &getReductionVars() const { return Reductions; }
 
  /// Returns the recurrence descriptor associated with a given phi node \p PN,
  /// expecting one to exist.
  const RecurrenceDescriptor &getRecurrenceDescriptor(PHINode *PN) const {
    assert(isReductionVariable(PN) &&
           "only reductions have recurrence descriptors");
    return Reductions.find(PN)->second;
  }
 
  /// Returns the induction variables found in the loop.
  const InductionList &getInductionVars() const { return Inductions; }
 
  /// Returns the conditional inductions found in the loop.
  const ConditionalInductionList &getConditionalInductions() const {
    return ConditionalInductions;
  }
 
  bool hasConditionalInductions() const {
    return !ConditionalInductions.empty();
  }
 
  /// Return the fixed-order recurrences found in the loop.
  RecurrenceSet &getFixedOrderRecurrences() { return FixedOrderRecurrences; }
 
  /// Returns the widest induction type.
  IntegerType *getWidestInductionType() { return WidestIndTy; }
 
  /// Returns True if given store is a final invariant store of one of the
  /// reductions found in the loop.
  LLVM_ABI bool isInvariantStoreOfReduction(StoreInst *SI);
 
  /// Returns True if given address is invariant and is used to store recurrent
  /// expression
  LLVM_ABI bool isInvariantAddressOfReduction(Value *V);
 
  /// Returns True if V is a Phi node of an induction variable in this loop.
  LLVM_ABI bool isInductionPhi(const Value *V) const;
 
  /// Returns True if PN is a reduction variable in this loop.
  bool isReductionVariable(PHINode *PN) const { return Reductions.count(PN); }
 
  /// Returns True if Phi is a fixed-order recurrence in this loop.
  LLVM_ABI bool isFixedOrderRecurrence(const PHINode *Phi) const;
 
  /// Return true if the block BB needs to be predicated in order for the loop
  /// to be vectorized.
  LLVM_ABI bool blockNeedsPredication(const BasicBlock *BB) const;
 
  /// Add unit stride predicates for memory accesses to PSE, if runtime checks
  /// are allowed and an inner loop is vectorized.
  LLVM_ABI void collectUnitStridePredicates() const;
 
  /// Check if this pointer is consecutive when vectorizing. This happens
  /// when the last index of the GEP is the induction variable, or that the
  /// pointer itself is an induction variable.
  /// This check allows us to vectorize A[idx] into a wide load/store.
  /// Returns:
  /// 0 - Stride is unknown or non-consecutive.
  /// 1 - Address is consecutive.
  /// -1 - Address is consecutive, and decreasing.
  /// NOTE: This method must only be used before modifying the original scalar
  /// loop. Do not use after executing a VPlan (PR34965).
  LLVM_ABI int isConsecutivePtr(Type *AccessTy, Value *Ptr) const;
 
  /// Returns true if \p V is invariant across all loop iterations according to
  /// SCEV.
  LLVM_ABI bool isInvariant(Value *V) const;
 
  /// Returns true if value V is uniform across \p VF lanes, when \p VF is
  /// provided, and otherwise if \p V is invariant across all loop iterations.
  LLVM_ABI bool isUniform(Value *V, std::optional<ElementCount> VF) const;
 
  /// A uniform memory op is a load or store which accesses the same memory
  /// location on all \p VF lanes, if \p VF is provided and otherwise if the
  /// memory location is invariant.
  LLVM_ABI bool isUniformMemOp(Instruction &I,
                               std::optional<ElementCount> VF) const;
 
  /// Returns the information that we collected about runtime memory check.
  const RuntimePointerChecking *getRuntimePointerChecking() const {
    return LAI->getRuntimePointerChecking();
  }
 
  const LoopAccessInfo *getLAI() const { return LAI; }
 
  bool isSafeForAnyVectorWidth() const {
    return LAI->getDepChecker().isSafeForAnyVectorWidth() &&
           LAI->getDepChecker().isSafeForAnyStoreLoadForwardDistances();
  }
 
  uint64_t getMaxSafeVectorWidthInBits() const {
    return LAI->getDepChecker().getMaxSafeVectorWidthInBits();
  }
 
  /// Returns information about whether this loop contains at least one
  /// uncountable early exit, and if so, if it also contains instructions (such
  /// as stores) that cause side-effects.
  UncountableExitTrait getUncountableExitTrait() const {
    return UncountableExitType;
  }
 
  /// Returns true if the loop has uncountable early exits, i.e. uncountable
  /// exits that aren't the latch block.
  bool hasUncountableEarlyExit() const {
    return getUncountableExitTrait() != UncountableExitTrait::None;
  }
 
  /// Returns true if this is an early exit loop with state-changing or
  /// potentially-faulting operations and the condition for the uncountable
  /// exit must be determined before any of the state changes or potentially
  /// faulting operations take place.
  bool hasUncountableExitWithSideEffects() const {
    return getUncountableExitTrait() == UncountableExitTrait::ReadWrite;
  }
 
  /// If Cond is a combined exit condition featuring uncountable and countable
  /// comparisons, returns the countable comparison. Otherwise returns nullptr.
  LLVM_ABI Instruction *
  findCountableComparisonInCombinedCondition(Value *Cond) const;
 
  /// Return true if there is store-load forwarding dependencies.
  bool isSafeForAnyStoreLoadForwardDistances() const {
    return LAI->getDepChecker().isSafeForAnyStoreLoadForwardDistances();
  }
 
  /// Return safe power-of-2 number of elements, which do not prevent store-load
  /// forwarding and safe to operate simultaneously.
  uint64_t getMaxStoreLoadForwardSafeDistanceInBits() const {
    return LAI->getDepChecker().getStoreLoadForwardSafeDistanceInBits();
  }
 
  /// Returns true if instruction \p I requires a mask for vectorization.
  /// This accounts for both control flow masking (conditionally executed
  /// blocks) and tail-folding masking (predicated loop vectorization).
  bool isMaskRequired(const Instruction *I, bool TailFolded) const {
    if (TailFolded)
      return TailFoldedMaskedOp.contains(I);
    return ConditionallyExecutedOps.contains(I);
  }
 
  /// Returns true if there is at least one function call in the loop which
  /// has a vectorized variant available.
  bool hasVectorCallVariants() const { return VecCallVariantsFound; }
 
  /// Returns a HistogramInfo* for the given instruction if it was determined
  /// to be part of a load -> update -> store sequence where multiple lanes
  /// may be working on the same memory address.
  const HistogramInfo *getHistogramInfo(Instruction *I) const {
    for (const HistogramInfo &HGram : Histograms)
      if (HGram.Load == I || HGram.Update == I || HGram.Store == I)
        return &HGram;
 
    return nullptr;
  }
 
  /// Returns a list of all known histogram operations in the loop.
  bool hasHistograms() const { return !Histograms.empty(); }
 
  /// Returns the CompressedPtrInfo for \p Ptr if the pointer is defined via
  /// a conditional induction PHI, otherwise std::nullopt.
  std::optional<CompressedPtrInfo> getCompressedPtrInfo(Value *Ptr) const {
    auto It = CompressedPtrs.find(Ptr);
    if (It != CompressedPtrs.end())
      return It->second;
    return std::nullopt;
  }
 
  /// Returns true for \p I if it corresponds to a compressed load or store
  /// (which can map to an llvm.masked.expandload or llvm.masked.compressstore).
  bool isCompressedLoadOrStore(Instruction *I) {
    return isa<LoadInst, StoreInst>(I) &&
           getCompressedPtrInfo(getLoadStorePointerOperand(I)).has_value();
  }
 
  PredicatedScalarEvolution *getPredicatedScalarEvolution() const {
    return &PSE;
  }
 
  Loop *getLoop() const { return TheLoop; }
 
  LoopInfo *getLoopInfo() const { return LI; }
 
  AssumptionCache *getAssumptionCache() const { return AC; }
 
  ScalarEvolution *getScalarEvolution() const { return PSE.getSE(); }
 
  DominatorTree *getDominatorTree() const { return DT; }
 
  AAResults *getAA() const { return AA; }
 
  /// Returns all exiting blocks with a countable exit, i.e. the
  /// exit-not-taken count is known exactly at compile time.
  const SmallVector<BasicBlock *, 4> &getCountableExitingBlocks() const {
    return CountableExitingBlocks;
  }
 
private:
  /// Return true if the pre-header, exiting and latch blocks of \p Lp and all
  /// its nested loops are considered legal for vectorization. These legal
  /// checks are common for inner and outer loop vectorization.
  /// Temporarily taking UseVPlanNativePath parameter. If true, take
  /// the new code path being implemented for outer loop vectorization
  /// (should be functional for inner loop vectorization) based on VPlan.
  /// If false, good old LV code.
  bool canVectorizeLoopNestCFG(Loop *Lp, bool UseVPlanNativePath);
 
  /// Set up outer loop inductions by checking Phis in outer loop header for
  /// supported inductions (int and pointer inductions). Return false if any of
  /// these Phis is not a supported induction or if we fail to find any
  /// induction.
  bool setupOuterLoopInductions();
 
  /// Return true if the widest induction type, used for the canonical IV and
  /// trip count, can be determined, i.e. there is at least one integer or
  /// pointer induction. Otherwise report the reason and return false.
  bool canDetermineWidestInductionType();
 
  /// Return true if the pre-header, exiting and latch blocks of \p Lp
  /// (non-recursive) are considered legal for vectorization.
  /// Temporarily taking UseVPlanNativePath parameter. If true, take
  /// the new code path being implemented for outer loop vectorization
  /// (should be functional for inner loop vectorization) based on VPlan.
  /// If false, good old LV code.
  bool canVectorizeLoopCFG(Loop *Lp, bool UseVPlanNativePath) const;
 
  /// Check if a single basic block loop is vectorizable.
  /// At this point we know that this is a loop with a constant trip count
  /// and we only need to check individual instructions.
  bool canVectorizeInstrs();
 
  /// Check if an individual instruction is vectorizable.
  bool canVectorizeInstr(Instruction &I);
 
  /// When we vectorize loops we may change the order in which
  /// we read and write from memory. This method checks if it is
  /// legal to vectorize the code, considering only memory constrains.
  /// Returns true if the loop is vectorizable
  bool canVectorizeMemory();
 
  /// If LAA cannot determine whether all dependences are safe, we may be able
  /// to further analyse some IndirectUnsafe dependences and if they match a
  /// certain pattern (like a histogram) then we may still be able to vectorize.
  bool canVectorizeIndirectUnsafeDependences();
 
  /// Return true if we can vectorize this loop using the IF-conversion
  /// transformation.
  bool canVectorizeWithIfConvert();
 
  /// Return true if we can vectorize this outer loop. The method performs
  /// specific checks for outer loop vectorization.
  bool canVectorizeOuterLoop();
 
  /// Returns true if this is an early exit loop that can be vectorized.
  /// Currently, a loop with an uncountable early exit is considered
  /// vectorizable if:
  ///   1. Writes to memory will access different underlying objects than
  ///      any load used as part of the uncountable exit condition.
  ///   2. The loop has only one early uncountable exit
  ///   3. The early exit block dominates the latch block.
  ///   4. The latch block has an exact exit count.
  ///   5. The loop does not contain fixed-order recurrences or reductions where
  ///   the live-out value is used from a non-latch exit..
  ///   6. We can prove at compile-time that loops will not contain faulting
  ///      loads, or that any faulting loads would also occur in a purely
  ///      scalar loop.
  ///   7. It is safe to speculatively execute instructions such as divide or
  ///      call instructions.
  /// The list above is not based on theoretical limitations of vectorization,
  /// but simply a statement that more work is needed to support these
  /// additional cases safely.
  bool isVectorizableEarlyExitLoop();
 
  /// When vectorizing an early exit loop containing side effects, we need to
  /// determine whether an uncounted exit will be taken before any operation
  /// that has side effects.
  ///
  /// Consider a loop like the following:
  /// for (int i = 0; i < N; ++i) {
  ///   a[i] = b[i];
  ///   if (c[i] == 0)
  ///     break;
  /// }
  ///
  /// We have both a load and a store operation occurring before the condition
  /// is checked for early termination. We could potentially restrict
  /// vectorization to cases where we know all addresses are guaranteed to be
  /// dereferenceable, which would allow the load before the condition check to
  /// be vectorized.
  ///
  /// The store, however, should not execute across all lanes if early
  /// termination occurs before the end of the vector. We must only store to the
  /// locations that would have been stored to by a scalar loop. So we need to
  /// know what the result of 'c[i] == 0' is before performing the vector store,
  /// with or without masking.
  ///
  /// We can either do this by moving the condition load to the top of the
  /// vector body and using the comparison to create masks for other operations
  /// in the loop, or by looking ahead one vector iteration and bailing out to
  /// the scalar loop if an exit would occur.
  ///
  /// Using the latter approach (applicable to more targets), we need to hoist
  /// the first load (of c[0]) out of the loop then rotate the load within the
  /// loop to the next iteration, remembering to adjust the vector trip count.
  /// Something like the following:
  ///
  /// vec.ph:
  ///   %ci.0 = load <4 x i32>, ptr %c
  ///   %cmp.0 = icmp eq <4 x i32> %ci.0, zeroinitializer
  ///   %any.of.0 = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %cmp.0)
  ///   br i1 %any.of.0, label %scalar.ph, label %vec.body
  /// vec.body:
  ///   %iv = phi...
  ///   phi for c[i] if used elsewhere in the loop...
  ///   other operations in the loop...
  ///   %iv.next = add i64 %iv, 4
  ///   %addr.next = getelementptr i32, ptr %c, i64 %iv.next
  ///   %ci.next = load <4 x i32>, ptr %addr.next
  ///   %cmp.next = icmp eq <4 x i32> %ci.next, zeroinitializer
  ///   %any.of.next = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %cmp.next)
  ///   iv.next compared with shortened vector tripcount...
  ///   uncountable condition combined with counted condition...
  ///   br...
  ///
  /// Doing this means the last few iterations will always be performed by a
  /// scalar loop regardless of which exit is taken, and so vector iterations
  /// will never execute a memory operation to a location that the scalar loop
  /// would not have.
  ///
  /// This means we must ensure that it is safe to move the load for 'c[i]'
  /// before other memory operations (or any other observable side effects) in
  /// the loop.
  ///
  /// Currently, c[i] must have only one user (the comparison used for the
  /// uncountable exit) since we would otherwise need to introduce a PHI node
  /// for it.
  bool canUncountableExitConditionLoadBeMoved(BasicBlock *ExitingBlock);
 
  struct SafeAccessInfo {
    uint64_t MaxSizeInBytes = 0;
    Align MaxAlign = Align(1);
  };
 
  /// Maps a pointer to its maximum fixed access size and safe alignment.
  using SafeAccessesTy = SmallDenseMap<Value *, SafeAccessInfo, 8>;
 
  /// Return true if all of the instructions in the block can be speculatively
  /// executed, and record the loads/stores that require masking.
  /// \p SafeAccesses records pointers that can be accessed unconditionally,
  /// together with the fixed access sizes and alignments justified for each
  /// pointer.
  /// \p MaskedOp is a list of instructions that have to be transformed into
  /// calls to the appropriate masked intrinsic when the loop is vectorized
  /// or dropped if the instruction is a conditional assume intrinsic.
  bool
  blockCanBePredicated(BasicBlock *BB, SafeAccessesTy &SafeAccesses,
                       SmallPtrSetImpl<const Instruction *> &MaskedOp) const;
 
  /// Updates the vectorization state by adding \p Phi to the inductions list.
  /// This can set \p Phi as the main induction of the loop if \p Phi is a
  /// better choice for the main induction than the existing one.
  void addInductionPhi(PHINode *Phi, const InductionDescriptor &ID);
 
  /// Adds \p Phi to the conditional induction list and collects load/store
  /// users of the PHI. Returns true if all users of \p Phi are legal for
  /// vectorization.
  bool addConditionalInduction(PHINode *Phi,
                               const ConditionalInductionDescriptor &CondID);
 
  const VectorizeOptions &Opts;
 
  /// The loop that we evaluate.
  Loop *TheLoop;
 
  /// Loop Info analysis.
  LoopInfo *LI;
 
  /// A wrapper around ScalarEvolution used to add runtime SCEV checks.
  /// Applies dynamic knowledge to simplify SCEV expressions in the context
  /// of existing SCEV assumptions. The analysis will also add a minimal set
  /// of new predicates if this is required to enable vectorization and
  /// unrolling.
  PredicatedScalarEvolution &PSE;
 
  /// Target Transform Info.
  TargetTransformInfo *TTI;
 
  /// Target Library Info.
  TargetLibraryInfo *TLI;
 
  /// Dominator Tree.
  DominatorTree *DT;
 
  // LoopAccess analysis.
  LoopAccessInfoManager &LAIs;
 
  const LoopAccessInfo *LAI = nullptr;
 
  /// Interface to emit optimization remarks.
  OptimizationRemarkEmitter *ORE;
 
  //  ---  vectorization state --- //
 
  /// Holds the primary induction variable. This is the counter of the
  /// loop.
  PHINode *PrimaryInduction = nullptr;
 
  /// Holds the reduction variables.
  ReductionList Reductions;
 
  /// Holds all of the induction variables that we found in the loop.
  /// Notice that inductions don't need to start at zero and that induction
  /// variables can be pointers.
  InductionList Inductions;
 
  /// Holds all of the conditional inductions found in the loop.
  ConditionalInductionList ConditionalInductions;
 
  /// Holds the phi nodes that are fixed-order recurrences.
  RecurrenceSet FixedOrderRecurrences;
 
  /// Holds the widest induction type encountered.
  IntegerType *WidestIndTy = nullptr;
 
  /// Vectorization requirements that will go through late-evaluation.
  LoopVectorizationRequirements *Requirements;
 
  /// Used to emit an analysis of any legality issues.
  LoopVectorizeHints *Hints;
 
  /// The demanded bits analysis is used to compute the minimum type size in
  /// which a reduction can be computed.
  DemandedBits *DB;
 
  /// The assumption cache analysis is used to compute the minimum type size in
  /// which a reduction can be computed.
  AssumptionCache *AC;
 
  /// Instructions that require masking because they are in source-level
  /// conditionally executed blocks.
  SmallPtrSet<const Instruction *, 8> ConditionallyExecutedOps;
  /// Instructions that require masking only due to tail-folding predication.
  SmallPtrSet<const Instruction *, 8> TailFoldedMaskedOp;
 
  /// Contains all identified histogram operations, which are sequences of
  /// load -> update -> store instructions where multiple lanes in a vector
  /// may work on the same memory location.
  SmallVector<HistogramInfo, 1> Histograms;
 
  /// Contains all pointers used in the loop that are defined using an index
  /// derived from a conditional induction PHI. Loads/stores to these pointers
  /// map to expandloads or compressstores.
  SmallDenseMap<const Value *, CompressedPtrInfo> CompressedPtrs;
 
  /// Whether or not creating SCEV predicates is allowed.
  bool AllowRuntimeSCEVChecks;
 
  // Alias Analysis results used to check for possible aliasing with loads
  // used in uncountable exit conditions.
  AAResults *AA;
 
  /// If we discover function calls within the loop which have a valid
  /// vectorized variant, record that fact so that LoopVectorize can
  /// (potentially) make a better decision on the maximum VF and enable
  /// the use of those function variants.
  bool VecCallVariantsFound = false;
 
  /// Keep track of all the countable and uncountable exiting blocks if
  /// the exact backedge taken count is not computable.
  SmallVector<BasicBlock *, 4> CountableExitingBlocks;
 
  /// Records whether we have an uncountable early exit in a loop that's
  /// either read-only or read-write.
  UncountableExitTrait UncountableExitType = UncountableExitTrait::None;
};
 
} // namespace llvm
 
#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H