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_";
235 static void getVFABIMappings(
const CallInst &CI,
246 if (ListOfStrings.
empty())
248 for (
const auto &MangledName : ListOfStrings) {
249 const std::optional<VFInfo> Shape =
255 if (Shape && (Shape->ScalarName == ScalarName)) {
257 "Vector function is missing.");
269 getVFABIMappings(CI, Ret);
278 : M(CI.getModule()), CI(CI),
288 for (
const auto &
Info : ScalarToVectorMappings)
289 if (
Info.Shape == Shape)
290 return M->getFunction(
Info.VectorName);
297template <
typename T>
class ArrayRef;
299class GetElementPtrInst;
300template <
typename InstTy>
class InterleaveGroup;
303class ScalarEvolution;
304class TargetTransformInfo;
316 if (Scalar->isVoidTy() || Scalar->isMetadataTy() || EC.isScalar())
333 unsigned ScalarOpdIdx);
343 const TargetLibraryInfo *TLI);
390 const APInt &DemandedElts, APInt &DemandedLHS,
391 APInt &DemandedRHS,
bool AllowUndefElts =
false);
405 SmallVectorImpl<int> &ScaledMask);
423 SmallVectorImpl<int> &ScaledMask);
428 SmallVectorImpl<int> &ScaledMask);
443 ArrayRef<int> Mask,
unsigned NumOfSrcRegs,
unsigned NumOfDestRegs,
444 unsigned NumOfUsedRegs, function_ref<
void()> NoInputAction,
445 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned)> SingleInputAction,
446 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned)> ManyInputsAction);
482MapVector<Instruction*, uint64_t>
485 const TargetTransformInfo *
TTI=
nullptr);
500 const Instruction *Inst2);
524 const InterleaveGroup<Instruction> &Group);
641 : Factor(Factor), Reverse(Reverse), Alignment(Alignment),
642 InsertPos(nullptr) {}
645 : Alignment(Alignment), InsertPos(Instr) {
646 Factor = std::abs(Stride);
647 assert(Factor > 1 &&
"Invalid interleave factor");
649 Reverse = Stride < 0;
668 int32_t Key = *MaybeKey;
676 if (Members.
find(Key) != Members.
end())
679 if (Key > LargestKey) {
681 if (
Index >=
static_cast<int32_t
>(Factor))
685 }
else if (Key < SmallestKey) {
688 std::optional<int32_t> MaybeLargestIndex =
checkedSub(LargestKey, Key);
689 if (!MaybeLargestIndex)
693 if (*MaybeLargestIndex >=
static_cast<int64_t
>(Factor))
700 Alignment = std::min(Alignment, NewAlign);
701 Members[Key] = Instr;
709 int32_t Key = SmallestKey +
Index;
710 return Members.
lookup(Key);
716 for (
auto I : Members) {
717 if (
I.second == Instr)
718 return I.first - SmallestKey;
755 int32_t SmallestKey = 0;
756 int32_t LargestKey = 0;
785 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
801 if (InterleaveGroups.empty()) {
803 !RequiresScalarEpilogue &&
804 "RequiresScalarEpilog should not be set without interleave groups");
808 InterleaveGroupMap.clear();
809 for (
auto *
Ptr : InterleaveGroups)
811 InterleaveGroups.clear();
812 RequiresScalarEpilogue =
false;
818 return InterleaveGroupMap.contains(Instr);
826 return InterleaveGroupMap.lookup(Instr);
831 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
844 bool hasGroups()
const {
return !InterleaveGroups.empty(); }
861 bool RequiresScalarEpilogue =
false;
873 struct StrideDescriptor {
874 StrideDescriptor() =
default;
875 StrideDescriptor(int64_t Stride,
const SCEV *Scev,
uint64_t Size,
877 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}
883 const SCEV *Scev =
nullptr;
893 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
899 InterleaveGroup<Instruction> *
900 createInterleaveGroup(Instruction *Instr,
int Stride, Align Alignment) {
902 "Already in an interleaved access group");
903 InterleaveGroupMap[Instr] =
904 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
905 InterleaveGroups.
insert(InterleaveGroupMap[Instr]);
906 return InterleaveGroupMap[Instr];
910 void releaseGroup(InterleaveGroup<Instruction> *Group) {
911 for (
unsigned i = 0; i < Group->getFactor(); i++)
912 if (Instruction *Member = Group->getMember(i))
913 InterleaveGroupMap.
erase(Member);
915 InterleaveGroups.
erase(Group);
920 void collectConstStrideAccesses(
921 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
925 static bool isStrided(
int Stride);
928 bool isPredicated(BasicBlock *BB)
const {
933 bool areDependencesValid()
const {
942 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *
A,
943 StrideEntry *
B)
const {
959 auto *Src =
A->first;
960 auto SrcDes =
A->second;
963 auto *
Sink =
B->first;
964 auto SinkDes =
B->second;
968 if (!Src->mayWriteToMemory())
972 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
977 if (!areDependencesValid())
982 return !Dependences.
contains(Src) || !Dependences.
lookup(Src).count(Sink);
989 void collectDependences() {
990 if (!areDependencesValid())
993 for (
auto Dep : *Deps)
994 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
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...
iterator find(const_arg_type_t< KeyT > Val)
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...
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 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...
std::string mangleTLIVectorName(StringRef VectorName, StringRef ScalarName, unsigned numArgs, ElementCount VF)
This routine mangles the given VectorName according to the LangRef specification for vector-function-...
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.
static constexpr char const * _LLVM_
LLVM Internal VFABI ISA token for vector functions.
This is an optimization pass for GlobalISel generic memory operations.
bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, unsigned OpdIdx)
Identifies if the vector form of the intrinsic has a operand that has an overloaded type.
Value * stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
DenseMap< const Value *, Value * > ValueToValueMap
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 ...
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.
Value * getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
Get the stride of a pointer access in a loop.
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.
Value * getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty)
If a value has only one user that is a CastInst, return it.
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.
unsigned getGEPInductionOperand(const GetElementPtrInst *Gep)
Find the operand of the GEP that should be checked for consecutive stores.
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 ...
void getShuffleMaskWithWidestElts(ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Repetitively apply widenShuffleMaskElts() for as long as it succeeds, to get the shuffle mask with wi...
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.
std::enable_if_t< std::is_signed< T >::value, std::optional< T > > checkedSub(T LHS, T RHS)
Subtract two signed integers LHS and RHS.
std::enable_if_t< std::is_signed< T >::value, std::optional< T > > checkedAdd(T LHS, T RHS)
Add two signed integers LHS and RHS.
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