Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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/MapVector.h"

#include "llvm/Analysis/LoopAccessAnalysis.h"

#include "llvm/Support/TypeSize.h"

#include "llvm/Transforms/Utils/LoopUtils.h"

namespace llvm {

class AAResults;

class AssumptionCache;

class BasicBlock;

class BlockFrequencyInfo;

class DemandedBits;

class DominatorTree;

class Function;

class Loop;

class LoopInfo;

class Metadata;

class OptimizationRemarkEmitter;

class PredicatedScalarEvolution;

class ProfileSummaryInfo;

class TargetLibraryInfo;

class TargetTransformInfo;

class Type;

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

    HK_ISVECTORIZED,

    HK_PREDICATE,

    HK_SCALABLE

  };

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

    bool validate(unsigned Val);

  };

  /// Vectorization width.

  Hint Width;

  /// Vectorization interleave factor.

  Hint Interleave;

  /// Vectorization forced

  Hint Force;

  /// Already Vectorized

  Hint IsVectorized;

  /// Vector Predicate

  Hint Predicate;

  /// Says whether we should use fixed width or scalable vectorization.

  Hint 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

  };

  LoopVectorizeHints(const Loop *L, bool InterleaveOnlyWhenForced,

                     OptimizationRemarkEmitter &ORE,

                     const TargetTransformInfo *TTI = nullptr);

  /// Mark the loop L as already vectorized by setting the width to 1.

  void setAlreadyVectorized();

  bool allowVectorization(Function *F, Loop *L,

                          bool VectorizeOnlyWhenForced) const;

  /// Dumps all the hint information.

  void emitRemarkWithHints() const;

  ElementCount getWidth() const {

    return ElementCount::get(Width.Value, (ScalableForceKind)Scalable.Value ==

                                              SK_PreferScalable);

  }

  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.Value; }

  enum ForceKind getForce() const {

    if ((ForceKind)Force.Value == FK_Undefined &&

        hasDisableAllTransformsHint(TheLoop))

      return FK_Disabled;

    return (ForceKind)Force.Value;

  }

  /// \return true if scalable vectorization has been explicitly disabled.

  bool isScalableVectorizationDisabled() const {

    return (ScalableForceKind)Scalable.Value == SK_FixedWidthOnly;

  }

  /// If hints are provided that force vectorization, use the AlwaysPrint

  /// pass name to force the frontend to print the diagnostic.

  const char *vectorizeAnalysisPassName() const;

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

  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;

};

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

};

/// 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. This code reflects the capabilities of InnerLoopVectorizer.

/// This class is also used by InnerLoopVectorizer for identifying

/// induction variable and the different reduction variables.

class LoopVectorizationLegality {

public:

  LoopVectorizationLegality(

      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, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI)

      : TheLoop(L), LI(LI), PSE(PSE), TTI(TTI), TLI(TLI), DT(DT), LAIs(LAIs),

        ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC), BFI(BFI),

        PSI(PSI) {}

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

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

  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.

  bool canVectorizeFPMath(bool EnableStrictReductions);

  /// Return true if we can vectorize this loop while folding its tail by

  /// masking, and mark all respective loads/stores for masking.

  /// This object's state is only modified iff this function returns true.

  bool 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 induction variables found in the loop.

  const InductionList &getInductionVars() const { return Inductions; }

  /// Return the fixed-order recurrences found in the loop.

  RecurrenceSet &getFixedOrderRecurrences() { return FixedOrderRecurrences; }

  /// Return the set of instructions to sink to handle fixed-order recurrences.

  MapVector<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; }

  /// Returns the widest induction type.

  Type *getWidestInductionType() { return WidestIndTy; }

  /// Returns True if given store is a final invariant store of one of the

  /// reductions found in the loop.

  bool isInvariantStoreOfReduction(StoreInst *SI);

  /// Returns True if given address is invariant and is used to store recurrent

  /// expression

  bool isInvariantAddressOfReduction(Value *V);

  /// Returns True if V is a Phi node of an induction variable in this loop.

  bool isInductionPhi(const Value *V) const;

  /// Returns a pointer to the induction descriptor, if \p Phi is an integer or

  /// floating point induction.

  const InductionDescriptor *getIntOrFpInductionDescriptor(PHINode *Phi) const;

  /// Returns a pointer to the induction descriptor, if \p Phi is pointer

  /// induction.

  const InductionDescriptor *getPointerInductionDescriptor(PHINode *Phi) const;

  /// Returns True if V is a cast that is part of an induction def-use chain,

  /// and had been proven to be redundant under a runtime guard (in other

  /// words, the cast has the same SCEV expression as the induction phi).

  bool isCastedInductionVariable(const Value *V) const;

  /// Returns True if V can be considered as an induction variable in this

  /// loop. V can be the induction phi, or some redundant cast in the def-use

  /// chain of the inducion phi.

  bool isInductionVariable(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.

  bool isFixedOrderRecurrence(const PHINode *Phi) const;

  /// Return true if the block BB needs to be predicated in order for the loop

  /// to be vectorized.

  bool blockNeedsPredication(BasicBlock *BB) 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 invoking 'createVectorizedLoopSkeleton' (PR34965).

  int isConsecutivePtr(Type *AccessTy, Value *Ptr) const;

  /// Returns true if the value V is uniform within the loop.

  bool isUniform(Value *V) const;

  /// A uniform memory op is a load or store which accesses the same memory

  /// location on all lanes.

  bool isUniformMemOp(Instruction &I) 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();

  }

  unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }

  uint64_t getMaxSafeVectorWidthInBits() const {

    return LAI->getDepChecker().getMaxSafeVectorWidthInBits();

  }

  bool hasStride(Value *V) { return LAI->hasStride(V); }

  /// Returns true if vector representation of the instruction \p I

  /// requires mask.

  bool isMaskRequired(const Instruction *I) const {

    return MaskedOp.contains(I);

  }

  unsigned getNumStores() const { return LAI->getNumStores(); }

  unsigned getNumLoads() const { return LAI->getNumLoads(); }

  /// Returns all assume calls in predicated blocks. They need to be dropped

  /// when flattening the CFG.

  const SmallPtrSetImpl<Instruction *> &getConditionalAssumes() const {

    return ConditionalAssumes;

  }

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 inductions). Return false if any of these Phis

  /// is not a supported induction or if we fail to find an induction.

  bool setupOuterLoopInductions();

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

  /// 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();

  /// 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();

  /// 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();

  /// Return true if all of the instructions in the block can be speculatively

  /// executed, and record the loads/stores that require masking.

  /// \p SafePtrs is a list of addresses that are known to be legal and we know

  /// that we can read from them without segfault.

  /// \p MaskedOp is a list of instructions that have to be transformed into

  /// calls to the appropriate masked intrinsic when the loop is vectorized.

  /// \p ConditionalAssumes is a list of assume instructions in predicated

  /// blocks that must be dropped if the CFG gets flattened.

  bool blockCanBePredicated(

      BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs,

      SmallPtrSetImpl<const Instruction *> &MaskedOp,

      SmallPtrSetImpl<Instruction *> &ConditionalAssumes) 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,

                       SmallPtrSetImpl<Value *> &AllowedExit);

  /// If an access has a symbolic strides, this maps the pointer value to

  /// the stride symbol.

  const ValueToValueMap *getSymbolicStrides() const {

    // FIXME: Currently, the set of symbolic strides is sometimes queried before

    // it's collected.  This happens from canVectorizeWithIfConvert, when the

    // pointer is checked to reference consecutive elements suitable for a

    // masked access.

    return LAI ? &LAI->getSymbolicStrides() : nullptr;

  }

  /// 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 the casts that participate in the update chain of the induction

  /// variables, and that have been proven to be redundant (possibly under a

  /// runtime guard). These casts can be ignored when creating the vectorized

  /// loop body.

  SmallPtrSet<Instruction *, 4> InductionCastsToIgnore;

  /// Holds the phi nodes that are fixed-order recurrences.

  RecurrenceSet FixedOrderRecurrences;

  /// Holds instructions that need to sink past other instructions to handle

  /// fixed-order recurrences.

  MapVector<Instruction *, Instruction *> SinkAfter;

  /// Holds the widest induction type encountered.

  Type *WidestIndTy = nullptr;

  /// Allowed outside users. This holds the variables that can be accessed from

  /// outside the loop.

  SmallPtrSet<Value *, 4> AllowedExit;

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

  /// While vectorizing these instructions we have to generate a

  /// call to the appropriate masked intrinsic

  SmallPtrSet<const Instruction *, 8> MaskedOp;

  /// Assume instructions in predicated blocks must be dropped if the CFG gets

  /// flattened.

  SmallPtrSet<Instruction *, 8> ConditionalAssumes;

  /// BFI and PSI are used to check for profile guided size optimizations.

  BlockFrequencyInfo *BFI;

  ProfileSummaryInfo *PSI;

};

} // namespace llvm

#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H