13#ifndef LLVM_ANALYSIS_VECTORUTILS_H
14#define LLVM_ANALYSIS_VECTORUTILS_H
22class TargetLibraryInfo;
133 for (
unsigned i = 0; i < ParamCount; ++i)
147static constexpr char const *
_LLVM_ =
"_LLVM_";
204 bool Masked =
false);
236 static void getVFABIMappings(
const CallInst &CI,
247 if (ListOfStrings.
empty())
249 for (
const auto &MangledName : ListOfStrings) {
250 const std::optional<VFInfo> Shape =
256 if (Shape && (Shape->ScalarName == ScalarName)) {
258 "Vector function is missing.");
270 getVFABIMappings(CI, Ret);
278 std::optional<ElementCount> VF = std::nullopt) {
284 if (!VF ||
Info.Shape.VF == *VF)
293 : M(CI.getModule()), CI(CI),
303 for (
const auto &
Info : ScalarToVectorMappings)
304 if (
Info.Shape == Shape)
305 return M->getFunction(
Info.VectorName);
312template <
typename T>
class ArrayRef;
314template <
typename InstTy>
class InterleaveGroup;
317class ScalarEvolution;
318class TargetTransformInfo;
330 if (Scalar->isVoidTy() || Scalar->isMetadataTy() || EC.isScalar())
347 unsigned ScalarOpdIdx);
357 const TargetLibraryInfo *TLI);
387 const APInt &DemandedElts, APInt &DemandedLHS,
388 APInt &DemandedRHS,
bool AllowUndefElts =
false);
402 SmallVectorImpl<int> &ScaledMask);
420 SmallVectorImpl<int> &ScaledMask);
425 SmallVectorImpl<int> &ScaledMask);
440 ArrayRef<int> Mask,
unsigned NumOfSrcRegs,
unsigned NumOfDestRegs,
441 unsigned NumOfUsedRegs, function_ref<
void()> NoInputAction,
442 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned)> SingleInputAction,
443 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned)> ManyInputsAction);
479MapVector<Instruction*, uint64_t>
482 const TargetTransformInfo *
TTI=
nullptr);
497 const Instruction *Inst2);
521 const InterleaveGroup<Instruction> &Group);
639 InsertPos(nullptr) {}
642 : Alignment(Alignment), InsertPos(Instr) {
643 Factor = std::abs(Stride);
644 assert(Factor > 1 &&
"Invalid interleave factor");
646 Reverse = Stride < 0;
665 int32_t Key = *MaybeKey;
676 if (Key > LargestKey) {
678 if (
Index >=
static_cast<int32_t
>(Factor))
682 }
else if (Key < SmallestKey) {
685 std::optional<int32_t> MaybeLargestIndex =
checkedSub(LargestKey, Key);
686 if (!MaybeLargestIndex)
690 if (*MaybeLargestIndex >=
static_cast<int64_t
>(Factor))
697 Alignment = std::min(Alignment, NewAlign);
698 Members[Key] = Instr;
706 int32_t Key = SmallestKey +
Index;
707 return Members.
lookup(Key);
713 for (
auto I : Members) {
714 if (
I.second == Instr)
715 return I.first - SmallestKey;
752 int32_t SmallestKey = 0;
753 int32_t LargestKey = 0;
782 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
798 if (InterleaveGroups.empty()) {
800 !RequiresScalarEpilogue &&
801 "RequiresScalarEpilog should not be set without interleave groups");
805 InterleaveGroupMap.clear();
806 for (
auto *
Ptr : InterleaveGroups)
808 InterleaveGroups.clear();
809 RequiresScalarEpilogue =
false;
815 return InterleaveGroupMap.contains(Instr);
823 return InterleaveGroupMap.lookup(Instr);
828 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
841 bool hasGroups()
const {
return !InterleaveGroups.empty(); }
858 bool RequiresScalarEpilogue =
false;
870 struct StrideDescriptor {
871 StrideDescriptor() =
default;
872 StrideDescriptor(int64_t Stride,
const SCEV *Scev,
uint64_t Size,
874 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}
880 const SCEV *Scev =
nullptr;
890 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
896 InterleaveGroup<Instruction> *
897 createInterleaveGroup(Instruction *Instr,
int Stride, Align Alignment) {
899 "Already in an interleaved access group");
900 InterleaveGroupMap[
Instr] =
901 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
902 InterleaveGroups.
insert(InterleaveGroupMap[Instr]);
903 return InterleaveGroupMap[
Instr];
907 void releaseGroup(InterleaveGroup<Instruction> *Group) {
908 for (
unsigned i = 0; i < Group->getFactor(); i++)
909 if (Instruction *Member = Group->getMember(i))
910 InterleaveGroupMap.
erase(Member);
912 InterleaveGroups.
erase(Group);
917 void collectConstStrideAccesses(
918 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
919 const DenseMap<Value *, const SCEV *> &Strides);
922 static bool isStrided(
int Stride);
925 bool isPredicated(BasicBlock *BB)
const {
930 bool areDependencesValid()
const {
939 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *
A,
940 StrideEntry *
B)
const {
956 auto *Src =
A->first;
957 auto SrcDes =
A->second;
960 auto *
Sink =
B->first;
961 auto SinkDes =
B->second;
965 if (!Src->mayWriteToMemory())
969 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
974 if (!areDependencesValid())
979 return !Dependences.
contains(Src) || !Dependences.
lookup(Src).count(Sink);
986 void collectDependences() {
987 if (!areDependencesValid())
990 for (
auto Dep : *Deps)
991 Dependences[Dep.getSource(*LAI)].
insert(Dep.getDestination(*LAI));
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
DenseMap< Block *, BlockRelaxAux > Blocks
This file implements a map that provides insertion order iteration.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
unsigned arg_size() const
This class represents a function call, abstracting a target machine's calling convention.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
static constexpr ElementCount getFixed(ScalarTy MinVal)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
The group of interleaved loads/stores sharing the same stride and close to each other.
bool requiresScalarEpilogue() const
Returns true if this Group requires a scalar iteration to handle gaps.
uint32_t getFactor() const
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
InterleaveGroup(uint32_t Factor, bool Reverse, Align Alignment)
uint32_t getIndex(const InstTy *Instr) const
Get the index for the given member.
void setInsertPos(InstTy *Inst)
InstTy * getInsertPos() const
void addMetadata(InstTy *NewInst) const
Add metadata (e.g.
InterleaveGroup(InstTy *Instr, int32_t Stride, Align Alignment)
bool insertMember(InstTy *Instr, int32_t Index, Align NewAlign)
Try to insert a new member Instr with index Index and alignment NewAlign.
uint32_t getNumMembers() const
Drive the analysis of interleaved memory accesses in the loop.
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
bool requiresScalarEpilogue() const
Returns true if an interleaved group that may access memory out-of-bounds requires a scalar epilogue ...
bool hasGroups() const
Returns true if we have any interleave groups.
bool isInterleaved(Instruction *Instr) const
Check if Instr belongs to any interleave group.
bool invalidateGroups()
Invalidate groups, e.g., in case all blocks in loop will be predicated contrary to original assumptio...
iterator_range< SmallPtrSetIterator< llvm::InterleaveGroup< Instruction > * > > getInterleaveGroups()
void analyzeInterleaving(bool EnableMaskedInterleavedGroup)
Analyze the interleaved accesses and collect them in interleave groups.
void invalidateGroupsRequiringScalarEpilogue()
Invalidate groups that require a scalar epilogue (due to gaps).
InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L, DominatorTree *DT, LoopInfo *LI, const LoopAccessInfo *LAI)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
Represents a single loop in the control flow graph.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
A Module instance is used to store all the information related to an LLVM module.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
This class represents an analyzed expression in the program.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
The instances of the Type class are immutable: once they are created, they are never changed.
The Vector Function Database.
VFDatabase(CallInst &CI)
Constructor, requires a CallInst instance.
static bool hasMaskedVariant(const CallInst &CI, std::optional< ElementCount > VF=std::nullopt)
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
StringRef getName() const
Return a constant reference to the value's name.
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
A range adaptor for a pair of iterators.
Function * getVectorizedFunction(const VFShape &Shape) const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static constexpr char const * MappingsAttrName
std::optional< VFInfo > tryDemangleForVFABI(StringRef MangledName, const Module &M)
Function to construct a VFInfo out of a mangled names in the following format:
static constexpr char const * _LLVM_Scalarize_
Prefix for internal name redirection for vector function that tells the compiler to scalarize the cal...
void getVectorVariantNames(const CallInst &CI, SmallVectorImpl< std::string > &VariantMappings)
Populates a set of strings representing the Vector Function ABI variants associated to the CallInst C...
VFParamKind getVFParamKindFromString(const StringRef Token)
Retrieve the VFParamKind from a string token.
std::string mangleTLIVectorName(StringRef VectorName, StringRef ScalarName, unsigned numArgs, ElementCount VF, bool Masked=false)
This routine mangles the given VectorName according to the LangRef specification for vector-function-...
static constexpr char const * _LLVM_
LLVM Internal VFABI ISA token for vector functions.
NodeAddr< InstrNode * > Instr
This is an optimization pass for GlobalISel generic memory operations.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
APInt possiblyDemandedEltsInMask(Value *Mask)
Given a mask vector of the form <Y x i1>, return an APInt (of bitwidth Y) for each lane which may be ...
bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx)
Identifies if the vector form of the intrinsic is overloaded on the type of the operand at index OpdI...
llvm::SmallVector< int, 16 > createUnaryMask(ArrayRef< int > Mask, unsigned NumElts)
Given a shuffle mask for a binary shuffle, create the equivalent shuffle mask assuming both operands ...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Value * concatenateVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vecs)
Concatenate a list of vectors.
bool widenShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Try to transform a shuffle mask by replacing elements with the scaled index for an equivalent mask of...
Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)
Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)
Compute the access-group list of access groups that Inst1 and Inst2 are both in.
bool getShuffleDemandedElts(int SrcWidth, ArrayRef< int > Mask, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS, bool AllowUndefElts=false)
Transform a shuffle mask's output demanded element mask into demanded element masks for the 2 operand...
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
Constant * createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF, const InterleaveGroup< Instruction > &Group)
Create a mask that filters the members of an interleave group where there are gaps.
llvm::SmallVector< int, 16 > createStrideMask(unsigned Start, unsigned Stride, unsigned VF)
Create a stride shuffle mask.
llvm::SmallVector< int, 16 > createReplicatedMask(unsigned ReplicationFactor, unsigned VF)
Create a mask with replicated elements.
bool maskIsAllOneOrUndef(Value *Mask)
Given a mask vector of i1, Return true if all of the elements of this predicate mask are known to be ...
Type * ToVectorTy(Type *Scalar, ElementCount EC)
A helper function for converting Scalar types to vector types.
void processShuffleMasks(ArrayRef< int > Mask, unsigned NumOfSrcRegs, unsigned NumOfDestRegs, unsigned NumOfUsedRegs, function_ref< void()> NoInputAction, function_ref< void(ArrayRef< int >, unsigned, unsigned)> SingleInputAction, function_ref< void(ArrayRef< int >, unsigned, unsigned)> ManyInputsAction)
Splits and processes shuffle mask depending on the number of input and output registers.
void narrowShuffleMaskElts(int Scale, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Replace each shuffle mask index with the scaled sequential indices for an equivalent mask of narrowed...
llvm::SmallVector< int, 16 > createInterleaveMask(unsigned VF, unsigned NumVecs)
Create an interleave shuffle mask.
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register,...
MDNode * uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2)
Compute the union of two access-group lists.
VFISAKind
Describes the type of Instruction Set Architecture.
bool maskIsAllZeroOrUndef(Value *Mask)
Given a mask vector of i1, Return true if all of the elements of this predicate mask are known to be ...
std::enable_if_t< std::is_signed_v< T >, std::optional< T > > checkedSub(T LHS, T RHS)
Subtract two signed integers LHS and RHS.
void getShuffleMaskWithWidestElts(ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Repetitively apply widenShuffleMaskElts() for as long as it succeeds, to get the shuffle mask with wi...
std::enable_if_t< std::is_signed_v< T >, std::optional< T > > checkedAdd(T LHS, T RHS)
Add two signed integers LHS and RHS.
bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx)
Identifies if the vector form of the intrinsic has a scalar operand.
VFParamKind
Describes the type of Parameters.
bool isTriviallyVectorizable(Intrinsic::ID ID)
Identify if the intrinsic is trivially vectorizable.
llvm::SmallVector< int, 16 > createSequentialMask(unsigned Start, unsigned NumInts, unsigned NumUndefs)
Create a sequential shuffle mask.
MapVector< Instruction *, uint64_t > computeMinimumValueSizes(ArrayRef< BasicBlock * > Blocks, DemandedBits &DB, const TargetTransformInfo *TTI=nullptr)
Compute a map of integer instructions to their minimum legal type size.
int getSplatIndex(ArrayRef< int > Mask)
If all non-negative Mask elements are the same value, return that value.
This struct is a compact representation of a valid (non-zero power of two) alignment.
An information struct used to provide DenseMap with the various necessary components for a given valu...
Holds the VFShape for a specific scalar to vector function mapping.
bool isMasked() const
Returns true if at least one of the operands to the vectorized function has the kind 'GlobalPredicate...
std::string VectorName
Scalar Function Name.
std::optional< unsigned > getParamIndexForOptionalMask() const
Instruction Set Architecture.
VFISAKind ISA
Vector Function Name associated to this VFInfo.
std::string ScalarName
Classification of the vector function.
Encapsulates information needed to describe a parameter.
bool operator==(const VFParameter &Other) const
Contains the information about the kind of vectorization available.
static VFShape getScalarShape(const CallInst &CI)
static VFShape get(const CallInst &CI, ElementCount EC, bool HasGlobalPred)
bool hasValidParameterList() const
Validation check on the Parameters in the VFShape.
void updateParam(VFParameter P)
Update the parameter in position P.ParamPos to P.
SmallVector< VFParameter, 8 > Parameters
bool operator==(const VFShape &Other) const