diff options
Diffstat (limited to 'clang-r353983/include/llvm/Transforms/Vectorize')
4 files changed, 777 insertions, 0 deletions
diff --git a/clang-r353983/include/llvm/Transforms/Vectorize/LoadStoreVectorizer.h b/clang-r353983/include/llvm/Transforms/Vectorize/LoadStoreVectorizer.h new file mode 100644 index 00000000..f72c76c6 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/Vectorize/LoadStoreVectorizer.h @@ -0,0 +1,26 @@ +//===- LoadStoreVectorizer.cpp - GPU Load & Store Vectorizer --------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_LOADSTOREVECTORIZER_H +#define LLVM_TRANSFORMS_VECTORIZE_LOADSTOREVECTORIZER_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LoadStoreVectorizerPass : public PassInfoMixin<LoadStoreVectorizerPass> { +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); +}; + +/// Create a legacy pass manager instance of the LoadStoreVectorizer pass +Pass *createLoadStoreVectorizerPass(); + +} + +#endif /* LLVM_TRANSFORMS_VECTORIZE_LOADSTOREVECTORIZER_H */ diff --git a/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h b/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h new file mode 100644 index 00000000..ea0a1c26 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h @@ -0,0 +1,483 @@ +//===- 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/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Transforms/Utils/LoopUtils.h" + +namespace llvm { + +/// Create an analysis remark that explains why vectorization failed +/// +/// \p PassName is the name of the pass (e.g. can be AlwaysPrint). \p +/// RemarkName is the identifier for the remark. If \p I is passed it is an +/// instruction that prevents vectorization. Otherwise \p TheLoop is used for +/// the location of the remark. \return the remark object that can be +/// streamed to. +OptimizationRemarkAnalysis createLVMissedAnalysis(const char *PassName, + StringRef RemarkName, + Loop *TheLoop, + Instruction *I = nullptr); + +/// 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_UNROLL, HK_FORCE, 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) {} + + bool validate(unsigned Val); + }; + + /// Vectorization width. + Hint Width; + + /// Vectorization interleave factor. + Hint Interleave; + + /// Vectorization forced + Hint Force; + + /// Already Vectorized + Hint IsVectorized; + + /// 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. + }; + + LoopVectorizeHints(const Loop *L, bool InterleaveOnlyWhenForced, + OptimizationRemarkEmitter &ORE); + + /// 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; + + unsigned getWidth() const { return Width.Value; } + unsigned getInterleave() const { return Interleave.Value; } + unsigned getIsVectorized() const { return IsVectorized.Value; } + enum ForceKind getForce() const { + if ((ForceKind)Force.Value == FK_Undefined && + hasDisableAllTransformsHint(TheLoop)) + return FK_Disabled; + return (ForceKind)Force.Value; + } + + /// If hints are provided that force vectorization, use the AlwaysPrint + /// pass name to force the frontend to print the diagnostic. + const char *vectorizeAnalysisPassName() const; + + bool allowReordering() 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. + return getForce() == LoopVectorizeHints::FK_Enabled || getWidth() > 1; + } + + 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: + LoopVectorizationRequirements(OptimizationRemarkEmitter &ORE) : ORE(ORE) {} + + void addUnsafeAlgebraInst(Instruction *I) { + // First unsafe algebra instruction. + if (!UnsafeAlgebraInst) + UnsafeAlgebraInst = I; + } + + void addRuntimePointerChecks(unsigned Num) { NumRuntimePointerChecks = Num; } + + bool doesNotMeet(Function *F, Loop *L, const LoopVectorizeHints &Hints); + +private: + unsigned NumRuntimePointerChecks = 0; + Instruction *UnsafeAlgebraInst = nullptr; + + /// Interface to emit optimization remarks. + OptimizationRemarkEmitter &ORE; +}; + +/// 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, + TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F, + std::function<const LoopAccessInfo &(Loop &)> *GetLAA, LoopInfo *LI, + OptimizationRemarkEmitter *ORE, LoopVectorizationRequirements *R, + LoopVectorizeHints *H, DemandedBits *DB, AssumptionCache *AC) + : TheLoop(L), LI(LI), PSE(PSE), TLI(TLI), DT(DT), GetLAA(GetLAA), + ORE(ORE), Requirements(R), Hints(H), DB(DB), AC(AC) {} + + /// ReductionList contains the reduction descriptors for all + /// of the reductions that were found in the loop. + using ReductionList = DenseMap<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); + + /// Return true if we can vectorize this loop while folding its tail by + /// masking. + bool canFoldTailByMasking(); + + /// Returns the primary induction variable. + PHINode *getPrimaryInduction() { return PrimaryInduction; } + + /// Returns the reduction variables found in the loop. + ReductionList *getReductionVars() { return &Reductions; } + + /// Returns the induction variables found in the loop. + InductionList *getInductionVars() { return &Inductions; } + + /// Return the first-order recurrences found in the loop. + RecurrenceSet *getFirstOrderRecurrences() { return &FirstOrderRecurrences; } + + /// Return the set of instructions to sink to handle first-order recurrences. + DenseMap<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; } + + /// Returns the widest induction type. + Type *getWidestInductionType() { return WidestIndTy; } + + /// Returns True if V is a Phi node of an induction variable in this loop. + bool isInductionPhi(const Value *V); + + /// 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); + + /// 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); + + /// Returns True if PN is a reduction variable in this loop. + bool isReductionVariable(PHINode *PN) { return Reductions.count(PN); } + + /// Returns True if Phi is a first-order recurrence in this loop. + bool isFirstOrderRecurrence(const PHINode *Phi); + + /// Return true if the block BB needs to be predicated in order for the loop + /// to be vectorized. + bool blockNeedsPredication(BasicBlock *BB); + + /// 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(Value *Ptr); + + /// Returns true if the value V is uniform within the loop. + bool isUniform(Value *V); + + /// Returns the information that we collected about runtime memory check. + const RuntimePointerChecking *getRuntimePointerChecking() const { + return LAI->getRuntimePointerChecking(); + } + + const LoopAccessInfo *getLAI() const { return LAI; } + + unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); } + + uint64_t getMaxSafeRegisterWidth() const { + return LAI->getDepChecker().getMaxSafeRegisterWidth(); + } + + 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) { return (MaskedOp.count(I) != 0); } + + unsigned getNumStores() const { return LAI->getNumStores(); } + unsigned getNumLoads() const { return LAI->getNumLoads(); } + + // Returns true if the NoNaN attribute is set on the function. + bool hasFunNoNaNAttr() const { return HasFunNoNaNAttr; } + +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. \p SafePtrs is a list of addresses that are known to be legal + /// and we know that we can read from them without segfault. + bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs); + + /// 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); + + /// Create an analysis remark that explains why vectorization failed + /// + /// \p RemarkName is the identifier for the remark. If \p I is passed it is + /// an instruction that prevents vectorization. Otherwise the loop is used + /// for the location of the remark. \return the remark object that can be + /// streamed to. + OptimizationRemarkAnalysis + createMissedAnalysis(StringRef RemarkName, Instruction *I = nullptr) const { + return createLVMissedAnalysis(Hints->vectorizeAnalysisPassName(), + RemarkName, TheLoop, I); + } + + /// If an access has a symbolic strides, this maps the pointer value to + /// the stride symbol. + const ValueToValueMap *getSymbolicStrides() { + // 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 Library Info. + TargetLibraryInfo *TLI; + + /// Dominator Tree. + DominatorTree *DT; + + // LoopAccess analysis. + std::function<const LoopAccessInfo &(Loop &)> *GetLAA; + + // And the loop-accesses info corresponding to this loop. This pointer is + // null until canVectorizeMemory sets it up. + 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 first-order recurrences. + RecurrenceSet FirstOrderRecurrences; + + /// Holds instructions that need to sink past other instructions to handle + /// first-order recurrences. + DenseMap<Instruction *, Instruction *> SinkAfter; + + /// Holds the widest induction type encountered. + Type *WidestIndTy = nullptr; + + /// Allowed outside users. This holds the induction and reduction + /// vars which can be accessed from outside the loop. + SmallPtrSet<Value *, 4> AllowedExit; + + /// Can we assume the absence of NaNs. + bool HasFunNoNaNAttr = false; + + /// Vectorization requirements that will go through late-evaluation. + LoopVectorizationRequirements *Requirements; + + /// Used to emit an analysis of any legality issues. + LoopVectorizeHints *Hints; + + /// The demanded bits analsyis 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; +}; + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONLEGALITY_H diff --git a/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorize.h b/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorize.h new file mode 100644 index 00000000..cdbe5f63 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/Vectorize/LoopVectorize.h @@ -0,0 +1,115 @@ +//===- LoopVectorize.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 +// +//===----------------------------------------------------------------------===// +// +// This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops +// and generates target-independent LLVM-IR. +// The vectorizer uses the TargetTransformInfo analysis to estimate the costs +// of instructions in order to estimate the profitability of vectorization. +// +// The loop vectorizer combines consecutive loop iterations into a single +// 'wide' iteration. After this transformation the index is incremented +// by the SIMD vector width, and not by one. +// +// This pass has three parts: +// 1. The main loop pass that drives the different parts. +// 2. LoopVectorizationLegality - A unit that checks for the legality +// of the vectorization. +// 3. InnerLoopVectorizer - A unit that performs the actual +// widening of instructions. +// 4. LoopVectorizationCostModel - A unit that checks for the profitability +// of vectorization. It decides on the optimal vector width, which +// can be one, if vectorization is not profitable. +// +// There is a development effort going on to migrate loop vectorizer to the +// VPlan infrastructure and to introduce outer loop vectorization support (see +// docs/Proposal/VectorizationPlan.rst and +// http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html). For this +// purpose, we temporarily introduced the VPlan-native vectorization path: an +// alternative vectorization path that is natively implemented on top of the +// VPlan infrastructure. See EnableVPlanNativePath for enabling. +// +//===----------------------------------------------------------------------===// +// +// The reduction-variable vectorization is based on the paper: +// D. Nuzman and R. Henderson. Multi-platform Auto-vectorization. +// +// Variable uniformity checks are inspired by: +// Karrenberg, R. and Hack, S. Whole Function Vectorization. +// +// The interleaved access vectorization is based on the paper: +// Dorit Nuzman, Ira Rosen and Ayal Zaks. Auto-Vectorization of Interleaved +// Data for SIMD +// +// Other ideas/concepts are from: +// A. Zaks and D. Nuzman. Autovectorization in GCC-two years later. +// +// S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua. An Evaluation of +// Vectorizing Compilers. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H +#define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/PassManager.h" +#include <functional> + +namespace llvm { + +class AssumptionCache; +class BlockFrequencyInfo; +class DemandedBits; +class DominatorTree; +class Function; +class Loop; +class LoopAccessInfo; +class LoopInfo; +class OptimizationRemarkEmitter; +class ScalarEvolution; +class TargetLibraryInfo; +class TargetTransformInfo; + +/// The LoopVectorize Pass. +struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> { + /// If false, consider all loops for interleaving. + /// If true, only loops that explicitly request interleaving are considered. + bool InterleaveOnlyWhenForced = false; + + /// If false, consider all loops for vectorization. + /// If true, only loops that explicitly request vectorization are considered. + bool VectorizeOnlyWhenForced = false; + + ScalarEvolution *SE; + LoopInfo *LI; + TargetTransformInfo *TTI; + DominatorTree *DT; + BlockFrequencyInfo *BFI; + TargetLibraryInfo *TLI; + DemandedBits *DB; + AliasAnalysis *AA; + AssumptionCache *AC; + std::function<const LoopAccessInfo &(Loop &)> *GetLAA; + OptimizationRemarkEmitter *ORE; + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Shim for old PM. + bool runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_, + TargetTransformInfo &TTI_, DominatorTree &DT_, + BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_, + DemandedBits &DB_, AliasAnalysis &AA_, AssumptionCache &AC_, + std::function<const LoopAccessInfo &(Loop &)> &GetLAA_, + OptimizationRemarkEmitter &ORE); + + bool processLoop(Loop *L); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H diff --git a/clang-r353983/include/llvm/Transforms/Vectorize/SLPVectorizer.h b/clang-r353983/include/llvm/Transforms/Vectorize/SLPVectorizer.h new file mode 100644 index 00000000..9be70557 --- /dev/null +++ b/clang-r353983/include/llvm/Transforms/Vectorize/SLPVectorizer.h @@ -0,0 +1,153 @@ +//===- SLPVectorizer.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 +// +//===----------------------------------------------------------------------===// +// This pass implements the Bottom Up SLP vectorizer. It detects consecutive +// stores that can be put together into vector-stores. Next, it attempts to +// construct vectorizable tree using the use-def chains. If a profitable tree +// was found, the SLP vectorizer performs vectorization on the tree. +// +// The pass is inspired by the work described in the paper: +// "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H +#define LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/ValueHandle.h" + +namespace llvm { + +class AssumptionCache; +class BasicBlock; +class CmpInst; +class DataLayout; +class DemandedBits; +class DominatorTree; +class Function; +class InsertElementInst; +class InsertValueInst; +class Instruction; +class LoopInfo; +class OptimizationRemarkEmitter; +class PHINode; +class ScalarEvolution; +class StoreInst; +class TargetLibraryInfo; +class TargetTransformInfo; +class Value; + +/// A private "module" namespace for types and utilities used by this pass. +/// These are implementation details and should not be used by clients. +namespace slpvectorizer { + +class BoUpSLP; + +} // end namespace slpvectorizer + +struct SLPVectorizerPass : public PassInfoMixin<SLPVectorizerPass> { + using StoreList = SmallVector<StoreInst *, 8>; + using StoreListMap = MapVector<Value *, StoreList>; + using WeakTrackingVHList = SmallVector<WeakTrackingVH, 8>; + using WeakTrackingVHListMap = MapVector<Value *, WeakTrackingVHList>; + + ScalarEvolution *SE = nullptr; + TargetTransformInfo *TTI = nullptr; + TargetLibraryInfo *TLI = nullptr; + AliasAnalysis *AA = nullptr; + LoopInfo *LI = nullptr; + DominatorTree *DT = nullptr; + AssumptionCache *AC = nullptr; + DemandedBits *DB = nullptr; + const DataLayout *DL = nullptr; + +public: + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + + // Glue for old PM. + bool runImpl(Function &F, ScalarEvolution *SE_, TargetTransformInfo *TTI_, + TargetLibraryInfo *TLI_, AliasAnalysis *AA_, LoopInfo *LI_, + DominatorTree *DT_, AssumptionCache *AC_, DemandedBits *DB_, + OptimizationRemarkEmitter *ORE_); + +private: + /// Collect store and getelementptr instructions and organize them + /// according to the underlying object of their pointer operands. We sort the + /// instructions by their underlying objects to reduce the cost of + /// consecutive access queries. + /// + /// TODO: We can further reduce this cost if we flush the chain creation + /// every time we run into a memory barrier. + void collectSeedInstructions(BasicBlock *BB); + + /// Try to vectorize a chain that starts at two arithmetic instrs. + bool tryToVectorizePair(Value *A, Value *B, slpvectorizer::BoUpSLP &R); + + /// Try to vectorize a list of operands. + /// \param UserCost Cost of the user operations of \p VL if they may affect + /// the cost of the vectorization. + /// \returns true if a value was vectorized. + bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R, + int UserCost = 0, bool AllowReorder = false); + + /// Try to vectorize a chain that may start at the operands of \p I. + bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R); + + /// Vectorize the store instructions collected in Stores. + bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R); + + /// Vectorize the index computations of the getelementptr instructions + /// collected in GEPs. + bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + /// Try to find horizontal reduction or otherwise vectorize a chain of binary + /// operators. + bool vectorizeRootInstruction(PHINode *P, Value *V, BasicBlock *BB, + slpvectorizer::BoUpSLP &R, + TargetTransformInfo *TTI); + + /// Try to vectorize trees that start at insertvalue instructions. + bool vectorizeInsertValueInst(InsertValueInst *IVI, BasicBlock *BB, + slpvectorizer::BoUpSLP &R); + + /// Try to vectorize trees that start at insertelement instructions. + bool vectorizeInsertElementInst(InsertElementInst *IEI, BasicBlock *BB, + slpvectorizer::BoUpSLP &R); + + /// Try to vectorize trees that start at compare instructions. + bool vectorizeCmpInst(CmpInst *CI, BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + /// Tries to vectorize constructs started from CmpInst, InsertValueInst or + /// InsertElementInst instructions. + bool vectorizeSimpleInstructions(SmallVectorImpl<WeakVH> &Instructions, + BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + /// Scan the basic block and look for patterns that are likely to start + /// a vectorization chain. + bool vectorizeChainsInBlock(BasicBlock *BB, slpvectorizer::BoUpSLP &R); + + bool vectorizeStoreChain(ArrayRef<Value *> Chain, slpvectorizer::BoUpSLP &R, + unsigned VecRegSize); + + bool vectorizeStores(ArrayRef<StoreInst *> Stores, slpvectorizer::BoUpSLP &R); + + /// The store instructions in a basic block organized by base pointer. + StoreListMap Stores; + + /// The getelementptr instructions in a basic block organized by base pointer. + WeakTrackingVHListMap GEPs; +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_VECTORIZE_SLPVECTORIZER_H |