13#ifndef LLVM_ANALYSIS_VECTORUTILS_H
14#define LLVM_ANALYSIS_VECTORUTILS_H
25class TargetLibraryInfo;
42 static void getVFABIMappings(
const CallInst &CI,
53 if (ListOfStrings.
empty())
55 for (
const auto &MangledName : ListOfStrings) {
56 const std::optional<VFInfo> Shape =
62 if (Shape && (Shape->ScalarName == ScalarName)) {
64 "Vector function is missing.");
76 getVFABIMappings(CI, Ret);
84 std::optional<ElementCount> VF = std::nullopt) {
90 if (!VF ||
Info.Shape.VF == *VF)
99 : M(CI.getModule()), CI(CI),
110 for (
const auto &
Info : ScalarToVectorMappings)
111 if (
Info.Shape == Shape)
112 return M->getFunction(
Info.VectorName);
119template <
typename T>
class ArrayRef;
121template <
typename InstTy>
class InterleaveGroup;
124class TargetTransformInfo;
153 const TargetTransformInfo *
TTI);
160 const TargetTransformInfo *
TTI);
173 const TargetLibraryInfo *TLI);
203 const APInt &DemandedElts, APInt &DemandedLHS,
204 APInt &DemandedRHS,
bool AllowUndefElts =
false);
218 SmallVectorImpl<int> &ScaledMask);
236 SmallVectorImpl<int> &ScaledMask);
250 SmallVectorImpl<int> &ScaledMask);
255 SmallVectorImpl<int> &ScaledMask);
270 ArrayRef<int> Mask,
unsigned NumOfSrcRegs,
unsigned NumOfDestRegs,
271 unsigned NumOfUsedRegs, function_ref<
void()> NoInputAction,
272 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned)> SingleInputAction,
273 function_ref<
void(ArrayRef<int>,
unsigned,
unsigned,
bool)>
289 const APInt &DemandedElts,
327MapVector<Instruction*, uint64_t>
330 const TargetTransformInfo *
TTI=
nullptr);
345 const Instruction *Inst2);
369 const InterleaveGroup<Instruction> &Group);
492 InsertPos(nullptr) {}
495 : Alignment(Alignment), InsertPos(Instr) {
496 Factor = std::abs(Stride);
497 assert(Factor > 1 &&
"Invalid interleave factor");
499 Reverse = Stride < 0;
518 int32_t Key = *MaybeKey;
529 if (Key > LargestKey) {
531 if (
Index >=
static_cast<int32_t
>(Factor))
535 }
else if (Key < SmallestKey) {
538 std::optional<int32_t> MaybeLargestIndex =
checkedSub(LargestKey, Key);
539 if (!MaybeLargestIndex)
543 if (*MaybeLargestIndex >=
static_cast<int64_t
>(Factor))
550 Alignment = std::min(Alignment, NewAlign);
551 Members[Key] = Instr;
559 int32_t Key = SmallestKey +
Index;
560 return Members.
lookup(Key);
566 for (
auto I : Members) {
567 if (
I.second == Instr)
568 return I.first - SmallestKey;
605 int32_t SmallestKey = 0;
606 int32_t LargestKey = 0;
635 : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
651 if (InterleaveGroups.empty()) {
653 !RequiresScalarEpilogue &&
654 "RequiresScalarEpilog should not be set without interleave groups");
658 InterleaveGroupMap.clear();
659 for (
auto *
Ptr : InterleaveGroups)
661 InterleaveGroups.clear();
662 RequiresScalarEpilogue =
false;
668 return InterleaveGroupMap.contains(Instr);
676 return InterleaveGroupMap.lookup(Instr);
681 return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
694 bool hasGroups()
const {
return !InterleaveGroups.empty(); }
711 bool RequiresScalarEpilogue =
false;
723 struct StrideDescriptor {
724 StrideDescriptor() =
default;
725 StrideDescriptor(int64_t Stride,
const SCEV *Scev,
uint64_t Size,
727 : Stride(Stride), Scev(Scev), Size(Size), Alignment(Alignment) {}
733 const SCEV *Scev =
nullptr;
743 using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
749 InterleaveGroup<Instruction> *
750 createInterleaveGroup(Instruction *Instr,
int Stride, Align Alignment) {
752 "Already in an interleaved access group");
753 InterleaveGroupMap[
Instr] =
754 new InterleaveGroup<Instruction>(Instr, Stride, Alignment);
755 InterleaveGroups.
insert(InterleaveGroupMap[Instr]);
756 return InterleaveGroupMap[
Instr];
760 void releaseGroup(InterleaveGroup<Instruction> *Group) {
761 InterleaveGroups.
erase(Group);
762 releaseGroupWithoutRemovingFromSet(Group);
767 void releaseGroupWithoutRemovingFromSet(InterleaveGroup<Instruction> *Group) {
768 for (
unsigned i = 0; i < Group->getFactor(); i++)
769 if (Instruction *Member = Group->getMember(i))
770 InterleaveGroupMap.
erase(Member);
776 void collectConstStrideAccesses(
777 MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
778 const DenseMap<Value *, const SCEV *> &Strides);
781 static bool isStrided(
int Stride);
784 bool isPredicated(BasicBlock *BB)
const {
789 bool areDependencesValid()
const {
798 bool canReorderMemAccessesForInterleavedGroups(StrideEntry *
A,
799 StrideEntry *
B)
const {
815 auto *Src =
A->first;
816 auto SrcDes =
A->second;
819 auto *
Sink =
B->first;
820 auto SinkDes =
B->second;
824 if (!Src->mayWriteToMemory())
828 if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
833 if (!areDependencesValid())
838 return !Dependences.
contains(Src) || !Dependences.
lookup(Src).count(Sink);
845 void collectDependences() {
846 if (!areDependencesValid())
850 for (
auto Dep : *Deps)
851 Dependences[Dep.getSource(DepChecker)].
insert(
852 Dep.getDestination(DepChecker));
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
Module.h This file contains the declarations for the Module class.
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...
FunctionType * getFunctionType() 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.
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)
Remove pointer from the set.
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 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.
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.
std::optional< VFInfo > tryDemangleForVFABI(StringRef MangledName, const FunctionType *FTy)
Function to construct a VFInfo out of a mangled names in the following format:
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...
NodeAddr< InstrNode * > Instr
This is an optimization pass for GlobalISel generic memory operations.
bool isTriviallyScalarizable(Intrinsic::ID ID, const TargetTransformInfo *TTI)
Identify if the intrinsic is trivially scalarizable.
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 ...
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.
void getHorizDemandedEltsForFirstOperand(unsigned VectorBitWidth, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS)
Compute the demanded elements mask of horizontal binary operations.
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 ...
bool isVectorIntrinsicWithStructReturnOverloadAtField(Intrinsic::ID ID, int RetIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic that returns a struct is overloaded at the struct elem...
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.
bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic has a scalar operand.
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.
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.
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, bool)> ManyInputsAction)
Splits and processes shuffle mask depending on the number of input and output registers.
bool maskContainsAllOneOrUndef(Value *Mask)
Given a mask vector of i1, Return true if any of the elements of this predicate mask are known to be ...
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.
bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx, const TargetTransformInfo *TTI)
Identifies if the vector form of the intrinsic is overloaded on the type of the operand at index OpdI...
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.
bool scaleShuffleMaskElts(unsigned NumDstElts, ArrayRef< int > Mask, SmallVectorImpl< int > &ScaledMask)
Attempt to narrow/widen the Mask shuffle mask to the NumDstElts target width.
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.
Contains the information about the kind of vectorization available.
static VFShape getScalarShape(const FunctionType *FTy)
Retrieve the VFShape that can be used to map a scalar function to itself, with VF = 1.