LLVM 18.0.0git
|
#include "llvm/Transforms/Vectorize/SLPVectorizer.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/IVDescriptors.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/DOTGraphTraits.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/InstructionCost.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/InjectTLIMappings.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <optional>
#include <set>
#include <string>
#include <tuple>
#include <utility>
Go to the source code of this file.
Classes | |
class | llvm::slpvectorizer::BoUpSLP |
Bottom Up SLP Vectorizer. More... | |
struct | llvm::slpvectorizer::BoUpSLP::EdgeInfo |
This structure holds any data we need about the edges being traversed during buildTree_rec(). More... | |
class | llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics |
A helper class used for scoring candidates for two consecutive lanes. More... | |
class | llvm::slpvectorizer::BoUpSLP::VLOperands |
A helper data structure to hold the operands of a vector of instructions. More... | |
struct | llvm::GraphTraits< BoUpSLP * > |
struct | llvm::GraphTraits< BoUpSLP * >::ChildIteratorType |
Add the VectorizableTree to the index iterator to be able to return TreeEntry pointers. More... | |
class | llvm::GraphTraits< BoUpSLP * >::nodes_iterator |
For the node iterator we just need to turn the TreeEntry iterator into a TreeEntry* iterator so that it dereferences to NodeRef. More... | |
struct | llvm::DOTGraphTraits< BoUpSLP * > |
class | llvm::slpvectorizer::BoUpSLP::ShuffleCostEstimator |
Merges shuffle masks and emits final shuffle instruction, if required. More... | |
class | llvm::slpvectorizer::BoUpSLP::ShuffleInstructionBuilder |
Merges shuffle masks and emits final shuffle instruction, if required. More... | |
Namespaces | |
namespace | llvm |
This is an optimization pass for GlobalISel generic memory operations. | |
namespace | llvm::slpvectorizer |
A private "module" namespace for types and utilities used by this pass. | |
Macros | |
#define | SV_NAME "slp-vectorizer" |
#define | DEBUG_TYPE "SLP" |
Functions | |
STATISTIC (NumVectorInstructions, "Number of vector instructions generated") | |
static bool | isValidElementType (Type *Ty) |
Predicate for the element types that the SLP vectorizer supports. | |
static bool | isConstant (Value *V) |
static bool | isVectorLikeInstWithConstOps (Value *V) |
Checks if V is one of vector-like instructions, i.e. | |
static std::string | shortBundleName (ArrayRef< Value * > VL) |
Print a short descriptor of the instruction bundle suitable for debug output. | |
static bool | allSameBlock (ArrayRef< Value * > VL) |
static bool | allConstant (ArrayRef< Value * > VL) |
static bool | isSplat (ArrayRef< Value * > VL) |
static bool | isCommutative (Instruction *I) |
static std::optional< unsigned > | getInsertIndex (const Value *InsertInst, unsigned Offset=0) |
static SmallBitVector | buildUseMask (int VF, ArrayRef< int > Mask, UseMask MaskArg) |
Prepares a use bitset for the given mask either for the first argument or for the second. | |
template<bool IsPoisonOnly = false> | |
static SmallBitVector | isUndefVector (const Value *V, const SmallBitVector &UseMask={}) |
Checks if the given value is actually an undefined constant vector. | |
static std::optional< TargetTransformInfo::ShuffleKind > | isFixedVectorShuffle (ArrayRef< Value * > VL, SmallVectorImpl< int > &Mask) |
Checks if the vector of instructions can be represented as a shuffle, like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 x0x0 = mul i8 x0, x0 x3x3 = mul i8 x3, x3 y1y1 = mul i8 y1, y1 y2y2 = mul i8 y2, y2 ins1 = insertelement <4 x i8> poison, i8 x0x0, i32 0 ins2 = insertelement <4 x i8> ins1, i8 x3x3, i32 1 ins3 = insertelement <4 x i8> ins2, i8 y1y1, i32 2 ins4 = insertelement <4 x i8> ins3, i8 y2y2, i32 3 ret <4 x i8> ins4 can be transformed into: %1 = shufflevector <4 x i8> x, <4 x i8> y, <4 x i32> <i32 0, i32 3, i32 5, i32 6> %2 = mul <4 x i8> %1, %1 ret <4 x i8> %2 We convert this initially to something like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 %1 = insertelement <4 x i8> poison, i8 x0, i32 0 %2 = insertelement <4 x i8> %1, i8 x3, i32 1 %3 = insertelement <4 x i8> %2, i8 y1, i32 2 %4 = insertelement <4 x i8> %3, i8 y2, i32 3 %5 = mul <4 x i8> %4, %4 %6 = extractelement <4 x i8> %5, i32 0 ins1 = insertelement <4 x i8> poison, i8 %6, i32 0 %7 = extractelement <4 x i8> %5, i32 1 ins2 = insertelement <4 x i8> ins1, i8 %7, i32 1 %8 = extractelement <4 x i8> %5, i32 2 ins3 = insertelement <4 x i8> ins2, i8 %8, i32 2 %9 = extractelement <4 x i8> %5, i32 3 ins4 = insertelement <4 x i8> ins3, i8 %9, i32 3 ret <4 x i8> ins4 InstCombiner transforms this into a shuffle and vector mul Mask will return the Shuffle Mask equivalent to the extracted elements. | |
static std::optional< unsigned > | getExtractIndex (Instruction *E) |
static Value * | isOneOf (const InstructionsState &S, Value *Op) |
Chooses the correct key for scheduling data. | |
static bool | isValidForAlternation (unsigned Opcode) |
static InstructionsState | getSameOpcode (ArrayRef< Value * > VL, const TargetLibraryInfo &TLI, unsigned BaseIndex=0) |
static bool | areCompatibleCmpOps (Value *BaseOp0, Value *BaseOp1, Value *Op0, Value *Op1, const TargetLibraryInfo &TLI) |
Checks if the provided operands of 2 cmp instructions are compatible, i.e. | |
static bool | isCmpSameOrSwapped (const CmpInst *BaseCI, const CmpInst *CI, const TargetLibraryInfo &TLI) |
static bool | allSameType (ArrayRef< Value * > VL) |
static bool | InTreeUserNeedToExtract (Value *Scalar, Instruction *UserInst, TargetLibraryInfo *TLI) |
static MemoryLocation | getLocation (Instruction *I) |
static bool | isSimple (Instruction *I) |
static void | addMask (SmallVectorImpl< int > &Mask, ArrayRef< int > SubMask, bool ExtendingManyInputs=false) |
Shuffles Mask in accordance with the given SubMask . | |
static void | fixupOrderingIndices (SmallVectorImpl< unsigned > &Order) |
Order may have elements assigned special value (size) which is out of bounds. | |
static void | llvm::inversePermutation (ArrayRef< unsigned > Indices, SmallVectorImpl< int > &Mask) |
static void | llvm::reorderScalars (SmallVectorImpl< Value * > &Scalars, ArrayRef< int > Mask) |
Reorders the list of scalars in accordance with the given Mask . | |
static bool | llvm::areAllOperandsNonInsts (Value *V) |
Checks if the provided value does not require scheduling. | |
static bool | llvm::isUsedOutsideBlock (Value *V) |
Checks if the provided value does not require scheduling. | |
static bool | llvm::doesNotNeedToBeScheduled (Value *V) |
Checks if the specified value does not require scheduling. | |
static bool | llvm::doesNotNeedToSchedule (ArrayRef< Value * > VL) |
Checks if the specified array of instructions does not require scheduling. | |
static void | reorderReuses (SmallVectorImpl< int > &Reuses, ArrayRef< int > Mask) |
Reorders the given Reuses mask according to the given Mask . | |
static void | reorderOrder (SmallVectorImpl< unsigned > &Order, ArrayRef< int > Mask) |
Reorders the given Order according to the given Mask . | |
static bool | arePointersCompatible (Value *Ptr1, Value *Ptr2, const TargetLibraryInfo &TLI, bool CompareOpcodes=true) |
static LoadsState | canVectorizeLoads (ArrayRef< Value * > VL, const Value *VL0, const TargetTransformInfo &TTI, const DataLayout &DL, ScalarEvolution &SE, LoopInfo &LI, const TargetLibraryInfo &TLI, SmallVectorImpl< unsigned > &Order, SmallVectorImpl< Value * > &PointerOps) |
Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather. | |
static bool | clusterSortPtrAccesses (ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices) |
static bool | areTwoInsertFromSameBuildVector (InsertElementInst *VU, InsertElementInst *V, function_ref< Value *(InsertElementInst *)> GetBaseOperand) |
Check if two insertelement instructions are from the same buildvector. | |
static bool | isRepeatedNonIdentityClusteredMask (ArrayRef< int > Mask, unsigned Sz) |
Checks if the given mask is a "clustered" mask with the same clusters of size Sz , which are not identity submasks. | |
static LLVM_DUMP_METHOD void | dumpOrder (const BoUpSLP::OrdersType &Order) |
static bool | needToScheduleSingleInstruction (ArrayRef< Value * > VL) |
static std::pair< size_t, size_t > | generateKeySubkey (Value *V, const TargetLibraryInfo *TLI, function_ref< hash_code(size_t, LoadInst *)> LoadsSubkeyGenerator, bool AllowAlternate) |
Generates key/subkey pair for the given value to provide effective sorting of the values and better detection of the vectorizable values sequences. | |
static bool | isAlternateInstruction (const Instruction *I, const Instruction *MainOp, const Instruction *AltOp, const TargetLibraryInfo &TLI) |
Checks if the specified instruction I is an alternate operation for the given MainOp and AltOp instructions. | |
static std::pair< InstructionCost, InstructionCost > | getVectorCallCosts (CallInst *CI, FixedVectorType *VecTy, TargetTransformInfo *TTI, TargetLibraryInfo *TLI) |
static bool | isLoadCombineCandidateImpl (Value *Root, unsigned NumElts, TargetTransformInfo *TTI, bool MustMatchOrInst) |
static bool | isFirstInsertElement (const InsertElementInst *IE1, const InsertElementInst *IE2) |
Checks if the IE1 instructions is followed by IE2 instruction in the buildvector sequence. | |
template<typename T > | |
static T * | performExtractsShuffleAction (MutableArrayRef< std::pair< T *, SmallVector< int > > > ShuffleMask, Value *Base, function_ref< unsigned(T *)> GetVF, function_ref< std::pair< T *, bool >(T *, ArrayRef< int >, bool)> ResizeAction, function_ref< T *(ArrayRef< int >, ArrayRef< T * >)> Action) |
Does the analysis of the provided shuffle masks and performs the requested actions on the vectors with the given shuffle masks. | |
static std::optional< unsigned > | getAggregateSize (Instruction *InsertInst) |
static void | findBuildAggregate_rec (Instruction *LastInsertInst, TargetTransformInfo *TTI, SmallVectorImpl< Value * > &BuildVectorOpds, SmallVectorImpl< Value * > &InsertElts, unsigned OperandOffset) |
static bool | findBuildAggregate (Instruction *LastInsertInst, TargetTransformInfo *TTI, SmallVectorImpl< Value * > &BuildVectorOpds, SmallVectorImpl< Value * > &InsertElts) |
Recognize construction of vectors like ra = insertelement <4 x float> poison, float s0, i32 0 rb = insertelement <4 x float> ra, float s1, i32 1 rc = insertelement <4 x float> rb, float s2, i32 2 rd = insertelement <4 x float> rc, float s3, i32 3 starting from the last insertelement or insertvalue instruction. | |
static Instruction * | getReductionInstr (const DominatorTree *DT, PHINode *P, BasicBlock *ParentBB, LoopInfo *LI) |
Try and get a reduction instruction from a phi node. | |
static bool | matchRdxBop (Instruction *I, Value *&V0, Value *&V1) |
static Instruction * | tryGetSecondaryReductionRoot (PHINode *Phi, Instruction *Root) |
We could have an initial reduction that is not an add. | |
static Instruction * | getNonPhiOperand (Instruction *I, PHINode *Phi) |
Returns the first operand of I that does not match Phi . | |
static bool | isReductionCandidate (Instruction *I) |
\Returns true if I is a candidate instruction for reduction vectorization. | |
template<typename T > | |
static bool | tryToVectorizeSequence (SmallVectorImpl< T * > &Incoming, function_ref< bool(T *, T *)> Comparator, function_ref< bool(T *, T *)> AreCompatible, function_ref< bool(ArrayRef< T * >, bool)> TryToVectorizeHelper, bool MaxVFOnly, BoUpSLP &R) |
template<bool IsCompatibility> | |
static bool | compareCmp (Value *V, Value *V2, TargetLibraryInfo &TLI, const DominatorTree &DT) |
Compare two cmp instructions. | |
Variables | |
static cl::opt< bool > | RunSLPVectorization ("vectorize-slp", cl::init(true), cl::Hidden, cl::desc("Run the SLP vectorization passes")) |
static cl::opt< int > | SLPCostThreshold ("slp-threshold", cl::init(0), cl::Hidden, cl::desc("Only vectorize if you gain more than this " "number ")) |
static cl::opt< bool > | ShouldVectorizeHor ("slp-vectorize-hor", cl::init(true), cl::Hidden, cl::desc("Attempt to vectorize horizontal reductions")) |
static cl::opt< bool > | ShouldStartVectorizeHorAtStore ("slp-vectorize-hor-store", cl::init(false), cl::Hidden, cl::desc("Attempt to vectorize horizontal reductions feeding into a store")) |
static cl::opt< bool > | AllowHorRdxIdenityOptimization ("slp-optimize-identity-hor-reduction-ops", cl::init(true), cl::Hidden, cl::desc("Allow optimization of original scalar identity operations on " "matched horizontal reductions.")) |
static cl::opt< int > | MaxVectorRegSizeOption ("slp-max-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits")) |
static cl::opt< unsigned > | MaxVFOption ("slp-max-vf", cl::init(0), cl::Hidden, cl::desc("Maximum SLP vectorization factor (0=unlimited)")) |
static cl::opt< int > | ScheduleRegionSizeBudget ("slp-schedule-budget", cl::init(100000), cl::Hidden, cl::desc("Limit the size of the SLP scheduling region per block")) |
Limits the size of scheduling regions in a block. | |
static cl::opt< int > | MinVectorRegSizeOption ("slp-min-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits")) |
static cl::opt< unsigned > | RecursionMaxDepth ("slp-recursion-max-depth", cl::init(12), cl::Hidden, cl::desc("Limit the recursion depth when building a vectorizable tree")) |
static cl::opt< unsigned > | MinTreeSize ("slp-min-tree-size", cl::init(3), cl::Hidden, cl::desc("Only vectorize small trees if they are fully vectorizable")) |
static cl::opt< int > | LookAheadMaxDepth ("slp-max-look-ahead-depth", cl::init(2), cl::Hidden, cl::desc("The maximum look-ahead depth for operand reordering scores")) |
static cl::opt< int > | RootLookAheadMaxDepth ("slp-max-root-look-ahead-depth", cl::init(2), cl::Hidden, cl::desc("The maximum look-ahead depth for searching best rooting option")) |
static cl::opt< bool > | ViewSLPTree ("view-slp-tree", cl::Hidden, cl::desc("Display the SLP trees with Graphviz")) |
static const unsigned | AliasedCheckLimit = 10 |
static const unsigned | MaxMemDepDistance = 160 |
static const int | MinScheduleRegionSize = 16 |
If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling regions to be handled. | |
#define DEBUG_TYPE "SLP" |
Definition at line 106 of file SLPVectorizer.cpp.
#define SV_NAME "slp-vectorizer" |
Definition at line 105 of file SLPVectorizer.cpp.
|
static |
Shuffles Mask
in accordance with the given SubMask
.
ExtendingManyInputs | Supports reshuffling of the mask with not only one but two input vectors. |
Definition at line 842 of file SLPVectorizer.cpp.
References assert(), llvm::ArrayRef< T >::begin(), E, llvm::ArrayRef< T >::empty(), llvm::ArrayRef< T >::end(), I, Idx, llvm::PoisonMaskElem, and llvm::ArrayRef< T >::size().
Referenced by llvm::slpvectorizer::BoUpSLP::reorderTopToBottom().
VL
are constants (but not globals/constant expressions). Definition at line 265 of file SLPVectorizer.cpp.
References llvm::all_of(), and isConstant().
Referenced by llvm::slpvectorizer::BoUpSLP::getReorderingData(), and llvm::slpvectorizer::BoUpSLP::isTreeTinyAndNotFullyVectorizable().
VL
are in the same block or false otherwise. Definition at line 244 of file SLPVectorizer.cpp.
References llvm::all_of(), E, llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), I, isVectorLikeInstWithConstOps(), and llvm::ArrayRef< T >::size().
VL
have the same type or false otherwise. Definition at line 787 of file SLPVectorizer.cpp.
References llvm::all_of(), llvm::ArrayRef< T >::drop_front(), and llvm::ArrayRef< T >::front().
Referenced by llvm::slpvectorizer::BoUpSLP::buildTree(), and llvm::slpvectorizer::BoUpSLP::getReorderingData().
|
static |
Checks if the provided operands of 2 cmp instructions are compatible, i.e.
compatible instructions or constants, or just some other regular values.
Definition at line 612 of file SLPVectorizer.cpp.
References getOpcode(), getSameOpcode(), and isConstant().
Referenced by isCmpSameOrSwapped().
|
static |
Definition at line 3837 of file SLPVectorizer.cpp.
References getOpcode(), getSameOpcode(), llvm::getUnderlyingObject(), and isConstant().
Referenced by canVectorizeLoads().
|
static |
Check if two insertelement instructions are from the same buildvector.
Definition at line 4029 of file SLPVectorizer.cpp.
References getInsertIndex(), llvm::Instruction::getParent(), llvm::InsertElementInst::getType(), llvm::Value::hasOneUse(), llvm::SmallBitVector::set(), and llvm::SmallBitVector::test().
Referenced by llvm::slpvectorizer::BoUpSLP::getReorderingData(), llvm::slpvectorizer::BoUpSLP::getTreeCost(), and llvm::slpvectorizer::BoUpSLP::vectorizeTree().
|
static |
Prepares a use bitset for the given mask either for the first argument or for the second.
Definition at line 355 of file SLPVectorizer.cpp.
References llvm::enumerate(), Idx, and llvm::PoisonMaskElem.
Referenced by performExtractsShuffleAction().
|
static |
Checks if the given array of loads can be represented as a vectorized, scatter or just simple gather.
Definition at line 3858 of file SLPVectorizer.cpp.
References llvm::all_of(), arePointersCompatible(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::count_if(), DL, llvm::doesNotNeedToBeScheduled(), llvm::SmallVectorBase< Size_T >::empty(), llvm::TargetTransformInfo::forceScalarizeMaskedGather(), llvm::SmallVectorTemplateCommon< T, typename >::front(), GEP, llvm::FixedVectorType::get(), llvm::getAlign(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::getPointersDiff(), llvm::Value::getType(), llvm::TargetTransformInfo::isLegalMaskedGather(), P, llvm::SmallVectorImpl< T >::resize(), llvm::ArrayRef< T >::size(), and llvm::sortPtrAccesses().
|
static |
Definition at line 3941 of file SLPVectorizer.cpp.
References llvm::all_of(), llvm::any_of(), assert(), llvm::sampleprof::Base, llvm::SmallVectorImpl< T >::clear(), DL, llvm::ArrayRef< T >::drop_front(), llvm::enumerate(), llvm::getPointersDiff(), P, Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::ArrayRef< T >::size(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::stable_sort(), X, and Y.
Referenced by llvm::slpvectorizer::BoUpSLP::findPartiallyOrderedLoads().
|
static |
Compare two cmp instructions.
If IsCompatibility is true, function returns true if 2 cmps have same/swapped predicates and mos compatible corresponding operands. If IsCompatibility is false, function implements strict weak ordering relation between two cmp instructions, returning true if the first instruction is "less" than the second, i.e. its predicate is less than the predicate of the second or the operands IDs are less than the operands IDs of the second cmp instruction.
Definition at line 15704 of file SLPVectorizer.cpp.
References assert(), E, llvm::DomTreeNodeBase< NodeT >::getDFSNumIn(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::User::getOperand(), getSameOpcode(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), llvm::Type::getTypeID(), llvm::Value::getValueID(), I, and isValidElementType().
|
static |
Definition at line 5076 of file SLPVectorizer.cpp.
References llvm::dbgs(), and Idx.
|
static |
Recognize construction of vectors like ra = insertelement <4 x float> poison, float s0, i32 0 rb = insertelement <4 x float> ra, float s1, i32 1 rc = insertelement <4 x float> rb, float s2, i32 2 rd = insertelement <4 x float> rc, float s3, i32 3 starting from the last insertelement or insertvalue instruction.
Also recognize homogeneous aggregates like {<2 x float>, <2 x float>}, {{float, float}, {float, float}}, [2 x {float, float}] and so on. See llvm/test/Transforms/SLPVectorizer/X86/pr42022.ll for examples.
Assume LastInsertInst is of InsertElementInst or InsertValueInst type.
Definition at line 15333 of file SLPVectorizer.cpp.
References assert(), llvm::SmallVectorBase< Size_T >::empty(), llvm::erase(), findBuildAggregate_rec(), getAggregateSize(), llvm::SmallVectorImpl< T >::resize(), and llvm::SmallVectorBase< Size_T >::size().
|
static |
Definition at line 15294 of file SLPVectorizer.cpp.
References findBuildAggregate_rec(), getInsertIndex(), llvm::User::getOperand(), and llvm::Value::hasOneUse().
Referenced by findBuildAggregate(), and findBuildAggregate_rec().
|
static |
Order may have elements assigned special value (size) which is out of bounds.
Such indices only appear on places which correspond to undef values (see canReuseExtract for details) and used in order to avoid undef values have effect on operands ordering. The first loop below simply finds all unused indices and then the next loop nest assigns these indices for undef values positions. As an example below Order has two undef positions and they have assigned values 3 and 7 respectively: before: 6 9 5 4 9 2 1 0 after: 6 3 5 4 7 2 1 0
Definition at line 879 of file SLPVectorizer.cpp.
References assert(), llvm::SmallBitVector::count(), llvm::SmallBitVector::find_first(), llvm::SmallBitVector::find_next(), I, Idx, llvm::SmallBitVector::none(), llvm::SmallBitVector::reset(), llvm::SmallBitVector::set(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by llvm::slpvectorizer::BoUpSLP::getReorderingData(), llvm::slpvectorizer::BoUpSLP::reorderBottomToTop(), reorderOrder(), and llvm::slpvectorizer::BoUpSLP::reorderTopToBottom().
|
static |
Generates key/subkey pair for the given value to provide effective sorting of the values and better detection of the vectorizable values sequences.
The keys/subkeys can be used for better sorting of the values themselves (keys) and in values subgroups (subkeys).
Definition at line 5153 of file SLPVectorizer.cpp.
References llvm::SmallBitVector::all(), generateKeySubkey(), llvm::CmpInst::getInversePredicate(), llvm::VFDatabase::getMappings(), llvm::CmpInst::getSwappedPredicate(), llvm::getVectorIntrinsicIDForCall(), llvm::hash_combine(), llvm::hash_value(), I, llvm::Instruction::isIntDivRem(), llvm::isTriviallyVectorizable(), isUndefVector(), isValidForAlternation(), and isVectorLikeInstWithConstOps().
Referenced by generateKeySubkey().
|
static |
Definition at line 15266 of file SLPVectorizer.cpp.
References llvm::Type::isSingleValueType(), and IV.
Referenced by findBuildAggregate().
|
static |
Definition at line 532 of file SLPVectorizer.cpp.
References assert(), E, and Opcode.
Referenced by llvm::slpvectorizer::BoUpSLP::getReorderingData().
|
static |
Definition at line 302 of file SLPVectorizer.cpp.
References I, IV, and llvm::Offset.
Referenced by areTwoInsertFromSameBuildVector(), findBuildAggregate_rec(), llvm::slpvectorizer::BoUpSLP::getReorderingData(), llvm::slpvectorizer::BoUpSLP::getTreeCost(), isFirstInsertElement(), and llvm::slpvectorizer::BoUpSLP::vectorizeTree().
|
static |
Definition at line 820 of file SLPVectorizer.cpp.
References llvm::MemoryLocation::get(), and I.
|
static |
Returns
the first operand of I
that does not match Phi
.
If operand is not an instruction it returns nullptr.
Definition at line 15455 of file SLPVectorizer.cpp.
References I, and matchRdxBop().
|
static |
Try and get a reduction instruction from a phi node.
Given a phi node P
in a block ParentBB
, consider possible reductions if they come from either ParentBB
or a containing loop latch.
Definition at line 15367 of file SLPVectorizer.cpp.
References llvm::DominatorTree::dominates(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), and P.
|
static |
VL
described in InstructionsState, the Opcode that we suppose the whole list could be vectorized even if its structure is diverse. Definition at line 648 of file SLPVectorizer.cpp.
References llvm::any_of(), assert(), llvm::CmpInst::BAD_ICMP_PREDICATE, E, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::CallBase::getBundleOperandsStartIndex(), llvm::CallBase::getCalledFunction(), llvm::VFDatabase::getMappings(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), llvm::getVectorIntrinsicIDForCall(), I, isCmpSameOrSwapped(), llvm::isTriviallyVectorizable(), isValidForAlternation(), isVectorLikeInstWithConstOps(), llvm::User::op_begin(), Opcode, llvm::ArrayRef< T >::size(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by areCompatibleCmpOps(), arePointersCompatible(), compareCmp(), llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getShallowScore(), and llvm::slpvectorizer::BoUpSLP::VLOperands::reorder().
|
static |
Definition at line 6459 of file SLPVectorizer.cpp.
References llvm::CallBase::args(), Arguments, llvm::VFShape::get(), llvm::FixedVectorType::get(), llvm::TargetTransformInfo::getCallInstrCost(), llvm::ElementCount::getFixed(), llvm::TargetTransformInfo::getIntrinsicInstrCost(), llvm::FixedVectorType::getNumElements(), llvm::getVectorIntrinsicIDForCall(), llvm::VFDatabase::getVectorizedFunction(), llvm::CallBase::isNoBuiltin(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::TargetTransformInfo::TCK_RecipThroughput.
|
static |
Definition at line 794 of file SLPVectorizer.cpp.
References llvm::any_of(), llvm::CallBase::args(), llvm::enumerate(), llvm::Instruction::getOpcode(), llvm::LoadInst::getPointerOperand(), llvm::getVectorIntrinsicIDForCall(), and Opcode.
Referenced by llvm::slpvectorizer::BoUpSLP::buildExternalUses().
|
static |
Checks if the specified instruction I
is an alternate operation for the given MainOp
and AltOp
instructions.
Definition at line 6524 of file SLPVectorizer.cpp.
References assert(), llvm::Instruction::getOpcode(), llvm::CmpInst::getSwappedPredicate(), I, isCmpSameOrSwapped(), and P.
|
static |
CI
has similar "look" and same predicate as BaseCI
, "as is" or with its operands and predicate swapped, false otherwise. Definition at line 626 of file SLPVectorizer.cpp.
References areCompatibleCmpOps(), assert(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::CmpInst::getSwappedPredicate(), and llvm::Value::getType().
Referenced by getSameOpcode(), and isAlternateInstruction().
|
static |
I
is commutative, handles CmpInst and BinaryOperator. Definition at line 289 of file SLPVectorizer.cpp.
References I.
Referenced by llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getScoreAtLevelRec(), and llvm::FastISel::selectBinaryOp().
Definition at line 209 of file SLPVectorizer.cpp.
Referenced by allConstant(), areCompatibleCmpOps(), and isVectorLikeInstWithConstOps().
|
static |
Checks if the IE1
instructions is followed by IE2
instruction in the buildvector sequence.
Definition at line 8745 of file SLPVectorizer.cpp.
References getInsertIndex(), llvm::Value::hasOneUse(), and llvm_unreachable.
Referenced by llvm::slpvectorizer::BoUpSLP::getTreeCost(), and llvm::slpvectorizer::BoUpSLP::vectorizeTree().
|
static |
Checks if the vector of instructions can be represented as a shuffle, like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 x0x0 = mul i8 x0, x0 x3x3 = mul i8 x3, x3 y1y1 = mul i8 y1, y1 y2y2 = mul i8 y2, y2 ins1 = insertelement <4 x i8> poison, i8 x0x0, i32 0 ins2 = insertelement <4 x i8> ins1, i8 x3x3, i32 1 ins3 = insertelement <4 x i8> ins2, i8 y1y1, i32 2 ins4 = insertelement <4 x i8> ins3, i8 y2y2, i32 3 ret <4 x i8> ins4 can be transformed into: %1 = shufflevector <4 x i8> x, <4 x i8> y, <4 x i32> <i32 0, i32 3, i32 5, i32 6> %2 = mul <4 x i8> %1, %1 ret <4 x i8> %2 We convert this initially to something like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 %1 = insertelement <4 x i8> poison, i8 x0, i32 0 %2 = insertelement <4 x i8> %1, i8 x3, i32 1 %3 = insertelement <4 x i8> %2, i8 y1, i32 2 %4 = insertelement <4 x i8> %3, i8 y2, i32 3 %5 = mul <4 x i8> %4, %4 %6 = extractelement <4 x i8> %5, i32 0 ins1 = insertelement <4 x i8> poison, i8 %6, i32 0 %7 = extractelement <4 x i8> %5, i32 1 ins2 = insertelement <4 x i8> ins1, i8 %7, i32 1 %8 = extractelement <4 x i8> %5, i32 2 ins3 = insertelement <4 x i8> ins2, i8 %8, i32 2 %9 = extractelement <4 x i8> %5, i32 3 ins4 = insertelement <4 x i8> ins3, i8 %9, i32 3 ret <4 x i8> ins4 InstCombiner transforms this into a shuffle and vector mul Mask will return the Shuffle Mask equivalent to the extracted elements.
TODO: Can we split off and reuse the shuffle mask detection from ShuffleVectorInst/getShuffleCost?
Definition at line 463 of file SLPVectorizer.cpp.
References E, llvm::ArrayRef< T >::end(), llvm::find_if(), I, Idx, isUndefVector(), llvm::PoisonMaskElem, Select, llvm::ArrayRef< T >::size(), Size, llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_PermuteTwoSrc, llvm::TargetTransformInfo::SK_Select, and Unknown.
|
static |
Definition at line 8517 of file SLPVectorizer.cpp.
References llvm::dbgs(), llvm::IntegerType::get(), llvm::Value::getContext(), llvm::Type::getIntegerBitWidth(), llvm::TargetTransformInfo::isTypeLegal(), LLVM_DEBUG, llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), and llvm::APInt::urem().
Referenced by llvm::slpvectorizer::BoUpSLP::isLoadCombineCandidate(), and llvm::slpvectorizer::BoUpSLP::isLoadCombineReductionCandidate().
Chooses the correct key for scheduling data.
If Op
has the same (or alternate) opcode as OpValue
, the key is Op
. Otherwise the key is OpValue
.
Definition at line 587 of file SLPVectorizer.cpp.
References I.
|
static |
\Returns true if I
is a candidate instruction for reduction vectorization.
Definition at line 15464 of file SLPVectorizer.cpp.
References I, llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and matchRdxBop().
Checks if the given mask is a "clustered" mask with the same clusters of size Sz
, which are not identity submasks.
Definition at line 4273 of file SLPVectorizer.cpp.
References E, I, and llvm::ShuffleVectorInst::isIdentityMask().
|
static |
Definition at line 829 of file SLPVectorizer.cpp.
Referenced by llvm::DOTGraphTraits< DOTFuncInfo * >::getNodeLabel(), llvm::DOTGraphTraits< MachineBlockFrequencyInfo * >::getNodeLabel(), llvm::DOTGraphTraits< const MachineFunction * >::getNodeLabel(), llvm::DOTGraphTraits< DOTMachineFuncInfo * >::getNodeLabel(), llvm::DOTGraphTraits< DomTreeNode * >::getNodeLabel(), llvm::DOTGraphTraits< RegionNode * >::getNodeLabel(), llvm::X86TargetLowering::shouldReduceLoadWidth(), tryToFoldExtOfMaskedLoad(), llvm::MBFIWrapper::view(), and llvm::MachineBlockFrequencyInfo::view().
VL
are identical or some of them are UndefValue. Definition at line 273 of file SLPVectorizer.cpp.
|
static |
Checks if the given value is actually an undefined constant vector.
Also, if the UseMask
is not empty, tries to check if the non-masked elements actually mask the insertelement buildvector, if any.
Definition at line 376 of file SLPVectorizer.cpp.
Referenced by generateKeySubkey(), llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getShallowScore(), isFixedVectorShuffle(), and performExtractsShuffleAction().
Predicate for the element types that the SLP vectorizer supports.
The most important thing to filter here are types which are invalid in LLVM vectors. We also filter target specific types which have absolutely no meaningful vectorization path such as x86_fp80 and ppc_f128. This just avoids spending time checking the cost model and realizing that they will be inevitably scalarized.
Definition at line 202 of file SLPVectorizer.cpp.
References llvm::Type::isPPC_FP128Ty(), and llvm::Type::isX86_FP80Ty().
Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), compareCmp(), and llvm::slpvectorizer::BoUpSLP::LookAheadHeuristics::getShallowScore().
Opcode
is allowed as part of the main/alternate instruction for SLP vectorization.Example of unsupported opcode is SDIV that can potentially cause UB if the "shuffled out" lane would result in division by zero.
Definition at line 599 of file SLPVectorizer.cpp.
References llvm::Instruction::isIntDivRem(), and Opcode.
Referenced by generateKeySubkey(), and getSameOpcode().
Checks if V
is one of vector-like instructions, i.e.
undef, insertelement/extractelement with constant indices for fixed vector type or extractvalue instruction.
Definition at line 216 of file SLPVectorizer.cpp.
References assert(), I, and isConstant().
Referenced by allSameBlock(), generateKeySubkey(), and getSameOpcode().
|
static |
Definition at line 15411 of file SLPVectorizer.cpp.
References I, llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().
Referenced by getNonPhiOperand(), and isReductionCandidate().
Definition at line 5134 of file SLPVectorizer.cpp.
References llvm::doesNotNeedToBeScheduled().
|
static |
Does the analysis of the provided shuffle masks and performs the requested actions on the vectors with the given shuffle masks.
It tries to do it in several steps.
Definition at line 8800 of file SLPVectorizer.cpp.
References llvm::SmallBitVector::all(), assert(), llvm::sampleprof::Base, buildUseMask(), E, I, Idx, isUndefVector(), llvm::PoisonMaskElem, and llvm::SmallBitVector::test().
|
static |
Reorders the given Order
according to the given Mask
.
Order
- is the original order of the scalars. Procedure transforms the provided order in accordance with the given Mask
. If the resulting Order
is just an identity order, Order
is cleared.
Definition at line 3742 of file SLPVectorizer.cpp.
References assert(), llvm::SmallVectorImpl< T >::assign(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), E, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), fixupOrderingIndices(), I, llvm::inversePermutation(), llvm::ShuffleVectorInst::isIdentityMask(), llvm::PoisonMaskElem, reorderReuses(), llvm::SmallVectorImpl< T >::resize(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by llvm::slpvectorizer::BoUpSLP::getReorderingData(), llvm::slpvectorizer::BoUpSLP::reorderBottomToTop(), and llvm::slpvectorizer::BoUpSLP::reorderTopToBottom().
|
static |
Reorders the given Reuses
mask according to the given Mask
.
Reuses
contains original mask for the scalars reused in the node. Procedure transform this mask in accordance with the given Mask
.
Definition at line 3728 of file SLPVectorizer.cpp.
References assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), E, llvm::SmallVectorTemplateCommon< T, typename >::end(), I, llvm::PoisonMaskElem, llvm::SmallVectorBase< Size_T >::size(), and llvm::SmallVectorImpl< T >::swap().
Referenced by llvm::slpvectorizer::BoUpSLP::reorderBottomToTop(), and reorderOrder().
Print a short descriptor of the instruction bundle suitable for debug output.
Definition at line 233 of file SLPVectorizer.cpp.
References llvm::raw_ostream::flush(), llvm::ArrayRef< T >::front(), OS, and llvm::ArrayRef< T >::size().
Referenced by llvm::slpvectorizer::BoUpSLP::getTreeCost().
STATISTIC | ( | NumVectorInstructions | , |
"Number of vector instructions generated" | |||
) |
|
static |
We could have an initial reduction that is not an add.
r *= v1 + v2 + v3 + v4 In such a case start looking for a tree rooted in the first '+'. \Returns the new root if found, which may be nullptr if not an instruction.
Definition at line 15437 of file SLPVectorizer.cpp.
References assert(), llvm::User::getOperand(), LHS, and RHS.
|
static |
\Returns the minimum number of elements that we will attempt to vectorize.
Definition at line 15619 of file SLPVectorizer.cpp.
References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), E, llvm::SmallVectorBase< Size_T >::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), End, llvm::SmallVectorTemplateCommon< T, typename >::front(), LLVM_DEBUG, llvm::SmallVectorBase< Size_T >::size(), and llvm::stable_sort().
Definition at line 184 of file SLPVectorizer.cpp.
|
static |
|
static |
Definition at line 189 of file SLPVectorizer.cpp.
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::BoUpSLP().
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::getMaximumVF().
|
static |
If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling regions to be handled.
Definition at line 193 of file SLPVectorizer.cpp.
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::BoUpSLP().
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::reorderTopToBottom().
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::findBestRootPair().
|
static |
Referenced by llvm::SLPVectorizerPass::runImpl().
|
static |
Limits the size of scheduling regions in a block.
It avoid long compile times for very large blocks where vector instructions are spread over a wide range. This limit is way higher than needed by real-world functions.
|
static |
|
static |
|
static |
Referenced by llvm::slpvectorizer::BoUpSLP::getTreeCost().