13 #ifndef LLVM_ANALYSIS_VECTORUTILS_H 14 #define LLVM_ANALYSIS_VECTORUTILS_H 22 class TargetLibraryInfo;
118 return {EC.getKnownMinValue(), EC.isScalable(),
Parameters};
140 static constexpr
char const *
_LLVM_ =
"_LLVM_";
194 unsigned numArgs,
unsigned VF);
226 static void getVFABIMappings(
const CallInst &CI,
237 if (ListOfStrings.
empty())
239 for (
const auto &MangledName : ListOfStrings) {
248 "Vector function is missing.");
260 getVFABIMappings(CI,
Ret);
269 : M(CI.getModule()), CI(CI),
279 for (
const auto &
Info : ScalarToVectorMappings)
280 if (
Info.Shape == Shape)
281 return M->getFunction(
Info.VectorName);
288 template <
typename T>
class ArrayRef;
290 class GetElementPtrInst;
299 namespace Intrinsic {
307 if (
Scalar->isVoidTy() || EC.isScalar())
329 const TargetLibraryInfo *TLI);
383 SmallVectorImpl<int> &ScaledMask);
401 SmallVectorImpl<int> &ScaledMask);
437 MapVector<Instruction*, uint64_t>
440 const TargetTransformInfo *
TTI=
nullptr);
455 const Instruction *Inst2);
479 const InterleaveGroup<Instruction> &Group);
587 template <
typename InstTy>
class InterleaveGroup {
590 : Factor(Factor), Reverse(Reverse), Alignment(Alignment),
591 InsertPos(nullptr) {}
594 : Alignment(Alignment), InsertPos(Instr) {
596 assert(Factor > 1 &&
"Invalid interleave factor");
598 Reverse = Stride < 0;
605 "Use getAlign instead.") {
606 return Alignment.
value();
621 int32_t
Key = *MaybeKey;
627 if (
Key > LargestKey) {
629 if (
Index >= static_cast<int32_t>(Factor))
633 }
else if (
Key < SmallestKey) {
637 if (!MaybeLargestIndex)
641 if (*MaybeLargestIndex >= static_cast<int64_t>(Factor))
648 Alignment =
std::min(Alignment, NewAlign);
649 Members[
Key] = Instr;
664 for (
auto I : Members) {
665 if (
I.second == Instr)
666 return I.first - SmallestKey;
693 "Group should have been invalidated");
705 int32_t SmallestKey = 0;
706 int32_t LargestKey = 0;
735 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
751 if (InterleaveGroups.empty()) {
753 !RequiresScalarEpilogue &&
754 "RequiresScalarEpilog should not be set without interleave groups");
758 InterleaveGroupMap.clear();
759 for (
auto *Ptr : InterleaveGroups)
761 InterleaveGroups.clear();
762 RequiresScalarEpilogue =
false;
768 return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
776 return InterleaveGroupMap.lookup(Instr);
781 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
808 bool RequiresScalarEpilogue =
false;
820 struct StrideDescriptor {
821 StrideDescriptor() =
default;
822 StrideDescriptor(int64_t Stride,
const SCEV *Scev, uint64_t
Size,
824 : Stride(Stride), Scev(Scev),
Size(
Size), Alignment(Alignment) {}
830 const SCEV *Scev =
nullptr;
840 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
846 InterleaveGroup<Instruction> *
847 createInterleaveGroup(Instruction *Instr,
int Stride,
Align Alignment) {
849 "Already in an interleaved access group");
850 InterleaveGroupMap[Instr] =
851 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
852 InterleaveGroups.
insert(InterleaveGroupMap[Instr]);
853 return InterleaveGroupMap[Instr];
857 void releaseGroup(InterleaveGroup<Instruction> *Group) {
858 for (
unsigned i = 0; i < Group->getFactor(); i++)
859 if (Instruction *Member = Group->getMember(i))
860 InterleaveGroupMap.erase(Member);
862 InterleaveGroups.
erase(Group);
867 void collectConstStrideAccesses(
868 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
872 static bool isStrided(
int Stride);
880 bool areDependencesValid()
const {
889 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
890 StrideEntry *
B)
const {
906 auto *Src =
A->first;
907 auto SrcDes =
A->second;
910 auto *
Sink =
B->first;
911 auto SinkDes =
B->second;
915 if (!Src->mayWriteToMemory())
919 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
924 if (!areDependencesValid())
929 return Dependences.
find(Src) == Dependences.
end() ||
937 void collectDependences() {
938 if (!areDependencesValid())
941 for (
auto Dep : *Deps)
942 Dependences[Dep.getSource(*LAI)].
insert(Dep.getDestination(*LAI));
Value * getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
Get the stride of a pointer access in a loop.
Common base class shared among various IRBuilders.
iterator_range< SmallPtrSetIterator< llvm::InterleaveGroup< Instruction > * > > getInterleaveGroups()
bool hasValidParameterList() const
Sanity check on the Parameters in the VFShape.
Value * stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp)
If the argument is a GEP, then returns the operand identified by getGEPInductionOperand.
static VFShape getScalarShape(const CallInst &CI)
void setInsertPos(InstTy *Inst)
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
llvm::SmallVector< int, 16 > createStrideMask(unsigned Start, unsigned Stride, unsigned VF)
Create a stride shuffle mask.
The Vector Function Database.
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...
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register,...
This class represents lattice values for constants.
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...
A Module instance is used to store all the information related to an LLVM module.
VFDatabase(CallInst &CI)
Constructor, requires a CallInst instance.
LLVM_NODISCARD bool empty() const
int getSplatIndex(ArrayRef< int > Mask)
If all non-negative Mask elements are the same value, return that value.
The main scalar evolution driver.
bool isInterleaved(Instruction *Instr) const
Check if Instr belongs to any interleave group.
This class represents a function call, abstracting a target machine's calling convention.
Contains the information about the kind of vectorization available.
static constexpr char const * _LLVM_
LLVM Internal VFABI ISA token for vector functions.
std::string VectorName
Scalar Function Name.
Holds the VFShape for a specific scalar to vector function mapping.
bool insertMember(InstTy *Instr, int32_t Index, Align NewAlign)
Try to insert a new member Instr with index Index and alignment NewAlign.
Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI)
Returns intrinsic ID for call.
Value * concatenateVectors(IRBuilderBase &Builder, ArrayRef< Value * > Vecs)
Concatenate a list of vectors.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
static uint32_t getAlignment(const MCSectionCOFF &Sec)
SmallVector< VFParameter, 8 > Parameters
bool operator==(const VFInfo &Other) const
Instruction Set Architecture.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
InterleaveGroup(InstTy *Instr, int32_t Stride, Align Alignment)
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Drive the analysis of interleaved memory accesses in the loop.
static constexpr char const * MappingsAttrName
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
The group of interleaved loads/stores sharing the same stride and close to each other.
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 ...
uint64_t value() const
This is a hole in the type system and should not be abused.
VFISAKind
Describes the type of Instruction Set Architecture.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void invalidateGroupsRequiringScalarEpilogue()
Invalidate groups that require a scalar epilogue (due to gaps).
Analysis containing CSE Info
MDNode * intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2)
Compute the access-group list of access groups that Inst1 and Inst2 are both in.
InstTy * getMember(uint32_t Index) const
Get the member with the given index Index.
iterator find(const_arg_type_t< KeyT > Val)
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...
llvm::SmallVector< int, 16 > createInterleaveMask(unsigned VF, unsigned NumVecs)
Create an interleave shuffle mask.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned arg_size() const
The instances of the Type class are immutable: once they are created, they are never changed.
InterleaveGroup< Instruction > * getInterleaveGroup(const Instruction *Instr) const
Get the interleave group that Instr belongs to.
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.
Encapsulates information needed to describe a parameter.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool operator==(const VFShape &Other) const
void updateParam(VFParameter P)
Update the parameter in position P.ParamPos to P.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
uint32_t getIndex(const InstTy *Instr) const
Get the index for the given member.
std::enable_if_t< std::is_signed< T >::value, llvm::Optional< T > > checkedSub(T LHS, T RHS)
Subtract two signed integers LHS and RHS.
bool requiresScalarEpilogue() const
Returns true if an interleaved group that may access memory out-of-bounds requires a scalar epilogue ...
InterleaveGroup(uint32_t Factor, bool Reverse, Align Alignment)
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 ...
MDNode * uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2)
Compute the union of two access-group lists.
InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L, DominatorTree *DT, LoopInfo *LI, const LoopAccessInfo *LAI)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This struct is a compact representation of a valid (non-zero power of two) alignment.
llvm::SmallVector< int, 16 > createSequentialMask(unsigned Start, unsigned NumInts, unsigned NumUndefs)
Create a sequential shuffle mask.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static VFShape get(const CallInst &CI, ElementCount EC, bool HasGlobalPred)
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
static SmallVector< VFInfo, 8 > getMappings(const CallInst &CI)
Retrieve all the VFInfo instances associated to the CallInst CI.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
DenseMap< const Value *, Value * > ValueToValueMap
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Type * ToVectorTy(Type *Scalar, ElementCount EC)
A helper function for converting Scalar types to vector types.
std::enable_if_t< std::is_signed< T >::value, llvm::Optional< T > > checkedAdd(T LHS, T RHS)
Add two signed integers LHS and RHS.
constexpr bool hasValue() const
Drive the analysis of memory accesses in the loop.
bool hasVectorInstrinsicScalarOpd(Intrinsic::ID ID, unsigned ScalarOpdIdx)
Identifies if the vector form of the intrinsic has a scalar operand.
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
A range adaptor for a pair of iterators.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
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...
VFParamKind
Describes the type of Parameters.
Value * getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty)
If a value has only one user that is a CastInst, return it.
unsigned getGEPInductionOperand(const GetElementPtrInst *Gep)
Find the operand of the GEP that should be checked for consecutive stores.
void analyzeInterleaving(bool EnableMaskedInterleavedGroup)
Analyze the interleaved accesses and collect them in interleave groups.
APInt possiblyDemandedEltsInMask(Value *Mask)
Given a mask vector of the form <Y x="" i1>="">, return an APInt (of bitwidth Y) for each lane which ...
LLVM_ATTRIBUTE_DEPRECATED(uint32_t getAlignment() const, "Use getAlign instead.")
This class represents an analyzed expression in the program.
Represents a single loop in the control flow graph.
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
StringRef getName() const
Return a constant reference to the value's name.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
APFloat abs(APFloat X)
Returns the absolute value of the argument.
uint32_t getFactor() const
std::string ScalarName
Classification of the vector function.
bool invalidateGroups()
Invalidate groups, e.g., in case all blocks in loop will be predicated contrary to original assumptio...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Function * getVectorizedFunction(const VFShape &Shape) const
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...
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.
VFParamKind getVFParamKindFromString(const StringRef Token)
Retrieve the VFParamKind from a string token.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
InstTy * getInsertPos() const
LLVM Value Representation.
VFISAKind ISA
Vector Function Name associated to this VFInfo.
std::string mangleTLIVectorName(StringRef VectorName, StringRef ScalarName, unsigned numArgs, unsigned VF)
This routine mangles the given VectorName according to the LangRef specification for vector-function-...
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.
static constexpr char const * _LLVM_Scalarize_
Prefix for internal name redirection for vector function that tells the compiler to scalarize the cal...
StringRef - Represent a constant reference to a string, i.e.
Optional< VFInfo > tryDemangleForVFABI(StringRef MangledName, const Module &M)
Function to construct a VFInfo out of a mangled names in the following format:
void addMetadata(InstTy *NewInst) const
Add metadata (e.g.
uint32_t getNumMembers() const
static ElementCount getFixed(ScalarTy MinVal)
Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)
Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...
bool requiresScalarEpilogue() const
Returns true if this Group requires a scalar iteration to handle gaps.
bool operator==(const VFParameter &Other) const
bool isTriviallyVectorizable(Intrinsic::ID ID)
Identify if the intrinsic is trivially vectorizable.