//===- llvm/Analysis/VectorUtils.h - Vector utilities -----------*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This file defines some vectorizer utilities. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_VECTORUTILS_H #define LLVM_ANALYSIS_VECTORUTILS_H #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopAccessAnalysis.h" #include "llvm/IR/Module.h" #include "llvm/IR/VFABIDemangler.h" #include "llvm/Support/CheckedArithmetic.h" namespace llvm { class TargetLibraryInfo; /// The Vector Function Database. /// /// Helper class used to find the vector functions associated to a /// scalar CallInst. class VFDatabase { … }; template <typename T> class ArrayRef; class DemandedBits; template <typename InstTy> class InterleaveGroup; class IRBuilderBase; class Loop; class TargetTransformInfo; class Value; namespace Intrinsic { ID; } /// A helper function for converting Scalar types to vector types. If /// the incoming type is void, we return void. If the EC represents a /// scalar, we return the scalar type. inline Type *ToVectorTy(Type *Scalar, ElementCount EC) { … } inline Type *ToVectorTy(Type *Scalar, unsigned VF) { … } /// Identify if the intrinsic is trivially vectorizable. /// This method returns true if the intrinsic's argument types are all scalars /// for the scalar form of the intrinsic and all vectors (or scalars handled by /// isVectorIntrinsicWithScalarOpAtArg) for the vector form of the intrinsic. bool isTriviallyVectorizable(Intrinsic::ID ID); /// Identifies if the vector form of the intrinsic has a scalar operand. bool isVectorIntrinsicWithScalarOpAtArg(Intrinsic::ID ID, unsigned ScalarOpdIdx); /// Identifies if the vector form of the intrinsic is overloaded on the type of /// the operand at index \p OpdIdx, or on the return type if \p OpdIdx is -1. bool isVectorIntrinsicWithOverloadTypeAtArg(Intrinsic::ID ID, int OpdIdx); /// Returns intrinsic ID for call. /// For the input call instruction it finds mapping intrinsic and returns /// its intrinsic ID, in case it does not found it return not_intrinsic. Intrinsic::ID getVectorIntrinsicIDForCall(const CallInst *CI, const TargetLibraryInfo *TLI); /// Given a vector and an element number, see if the scalar value is /// already around as a register, for example if it were inserted then extracted /// from the vector. Value *findScalarElement(Value *V, unsigned EltNo); /// If all non-negative \p Mask elements are the same value, return that value. /// If all elements are negative (undefined) or \p Mask contains different /// non-negative values, return -1. int getSplatIndex(ArrayRef<int> Mask); /// Get splat value if the input is a splat vector or return nullptr. /// The value may be extracted from a splat constants vector or from /// a sequence of instructions that broadcast a single value into a vector. Value *getSplatValue(const Value *V); /// Return true if each element of the vector value \p V is poisoned or equal to /// every other non-poisoned element. If an index element is specified, either /// every element of the vector is poisoned or the element at that index is not /// poisoned and equal to every other non-poisoned element. /// This may be more powerful than the related getSplatValue() because it is /// not limited by finding a scalar source value to a splatted vector. bool isSplatValue(const Value *V, int Index = -1, unsigned Depth = 0); /// Transform a shuffle mask's output demanded element mask into demanded /// element masks for the 2 operands, returns false if the mask isn't valid. /// Both \p DemandedLHS and \p DemandedRHS are initialised to [SrcWidth]. /// \p AllowUndefElts permits "-1" indices to be treated as undef. bool getShuffleDemandedElts(int SrcWidth, ArrayRef<int> Mask, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS, bool AllowUndefElts = false); /// Replace each shuffle mask index with the scaled sequential indices for an /// equivalent mask of narrowed elements. Mask elements that are less than 0 /// (sentinel values) are repeated in the output mask. /// /// Example with Scale = 4: /// <4 x i32> <3, 2, 0, -1> --> /// <16 x i8> <12, 13, 14, 15, 8, 9, 10, 11, 0, 1, 2, 3, -1, -1, -1, -1> /// /// This is the reverse process of widening shuffle mask elements, but it always /// succeeds because the indexes can always be multiplied (scaled up) to map to /// narrower vector elements. void narrowShuffleMaskElts(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 widened elements. If all mask elements that would /// map to a wider element of the new mask are the same negative number /// (sentinel value), that element of the new mask is the same value. If any /// element in a given slice is negative and some other element in that slice is /// not the same value, return false (partial matches with sentinel values are /// not allowed). /// /// Example with Scale = 4: /// <16 x i8> <12, 13, 14, 15, 8, 9, 10, 11, 0, 1, 2, 3, -1, -1, -1, -1> --> /// <4 x i32> <3, 2, 0, -1> /// /// This is the reverse process of narrowing shuffle mask elements if it /// succeeds. This transform is not always possible because indexes may not /// divide evenly (scale down) to map to wider vector elements. bool widenShuffleMaskElts(int Scale, ArrayRef<int> Mask, SmallVectorImpl<int> &ScaledMask); /// Attempt to narrow/widen the \p Mask shuffle mask to the \p NumDstElts target /// width. Internally this will call narrowShuffleMaskElts/widenShuffleMaskElts. /// This will assert unless NumDstElts is a multiple of Mask.size (or vice-versa). /// Returns false on failure, and ScaledMask will be in an undefined state. bool scaleShuffleMaskElts(unsigned NumDstElts, ArrayRef<int> Mask, SmallVectorImpl<int> &ScaledMask); /// Repetitively apply `widenShuffleMaskElts()` for as long as it succeeds, /// to get the shuffle mask with widest possible elements. void getShuffleMaskWithWidestElts(ArrayRef<int> Mask, SmallVectorImpl<int> &ScaledMask); /// Splits and processes shuffle mask depending on the number of input and /// output registers. The function does 2 main things: 1) splits the /// source/destination vectors into real registers; 2) do the mask analysis to /// identify which real registers are permuted. Then the function processes /// resulting registers mask using provided action items. If no input register /// is defined, \p NoInputAction action is used. If only 1 input register is /// used, \p SingleInputAction is used, otherwise \p ManyInputsAction is used to /// process > 2 input registers and masks. /// \param Mask Original shuffle mask. /// \param NumOfSrcRegs Number of source registers. /// \param NumOfDestRegs Number of destination registers. /// \param NumOfUsedRegs Number of actually used destination registers. 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); /// Compute the demanded elements mask of horizontal binary operations. A /// horizontal operation combines two adjacent elements in a vector operand. /// This function returns a mask for the elements that correspond to the first /// operand of this horizontal combination. For example, for two vectors /// [X1, X2, X3, X4] and [Y1, Y2, Y3, Y4], the resulting mask can include the /// elements X1, X3, Y1, and Y3. To get the other operands, simply shift the /// result of this function to the left by 1. /// /// \param VectorBitWidth the total bit width of the vector /// \param DemandedElts the demanded elements mask for the operation /// \param DemandedLHS the demanded elements mask for the left operand /// \param DemandedRHS the demanded elements mask for the right operand void getHorizDemandedEltsForFirstOperand(unsigned VectorBitWidth, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS); /// Compute a map of integer instructions to their minimum legal type /// size. /// /// C semantics force sub-int-sized values (e.g. i8, i16) to be promoted to int /// type (e.g. i32) whenever arithmetic is performed on them. /// /// For targets with native i8 or i16 operations, usually InstCombine can shrink /// the arithmetic type down again. However InstCombine refuses to create /// illegal types, so for targets without i8 or i16 registers, the lengthening /// and shrinking remains. /// /// Most SIMD ISAs (e.g. NEON) however support vectors of i8 or i16 even when /// their scalar equivalents do not, so during vectorization it is important to /// remove these lengthens and truncates when deciding the profitability of /// vectorization. /// /// This function analyzes the given range of instructions and determines the /// minimum type size each can be converted to. It attempts to remove or /// minimize type size changes across each def-use chain, so for example in the /// following code: /// /// %1 = load i8, i8* /// %2 = add i8 %1, 2 /// %3 = load i16, i16* /// %4 = zext i8 %2 to i32 /// %5 = zext i16 %3 to i32 /// %6 = add i32 %4, %5 /// %7 = trunc i32 %6 to i16 /// /// Instruction %6 must be done at least in i16, so computeMinimumValueSizes /// will return: {%1: 16, %2: 16, %3: 16, %4: 16, %5: 16, %6: 16, %7: 16}. /// /// If the optional TargetTransformInfo is provided, this function tries harder /// to do less work by only looking at illegal types. MapVector<Instruction*, uint64_t> computeMinimumValueSizes(ArrayRef<BasicBlock*> Blocks, DemandedBits &DB, const TargetTransformInfo *TTI=nullptr); /// Compute the union of two access-group lists. /// /// If the list contains just one access group, it is returned directly. If the /// list is empty, returns nullptr. MDNode *uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2); /// Compute the access-group list of access groups that @p Inst1 and @p Inst2 /// are both in. If either instruction does not access memory at all, it is /// considered to be in every list. /// /// If the list contains just one access group, it is returned directly. If the /// list is empty, returns nullptr. MDNode *intersectAccessGroups(const Instruction *Inst1, const Instruction *Inst2); /// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, /// MD_nontemporal, MD_access_group, MD_mmra]. /// For K in Kinds, we get the MDNode for K from each of the /// elements of VL, compute their "intersection" (i.e., the most generic /// metadata value that covers all of the individual values), and set I's /// metadata for M equal to the intersection value. /// /// This function always sets a (possibly null) value for each K in Kinds. Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL); /// Create a mask that filters the members of an interleave group where there /// are gaps. /// /// For example, the mask for \p Group with interleave-factor 3 /// and \p VF 4, that has only its first member present is: /// /// <1,0,0,1,0,0,1,0,0,1,0,0> /// /// Note: The result is a mask of 0's and 1's, as opposed to the other /// create[*]Mask() utilities which create a shuffle mask (mask that /// consists of indices). Constant *createBitMaskForGaps(IRBuilderBase &Builder, unsigned VF, const InterleaveGroup<Instruction> &Group); /// Create a mask with replicated elements. /// /// This function creates a shuffle mask for replicating each of the \p VF /// elements in a vector \p ReplicationFactor times. It can be used to /// transform a mask of \p VF elements into a mask of /// \p VF * \p ReplicationFactor elements used by a predicated /// interleaved-group of loads/stores whose Interleaved-factor == /// \p ReplicationFactor. /// /// For example, the mask for \p ReplicationFactor=3 and \p VF=4 is: /// /// <0,0,0,1,1,1,2,2,2,3,3,3> llvm::SmallVector<int, 16> createReplicatedMask(unsigned ReplicationFactor, unsigned VF); /// Create an interleave shuffle mask. /// /// This function creates a shuffle mask for interleaving \p NumVecs vectors of /// vectorization factor \p VF into a single wide vector. The mask is of the /// form: /// /// <0, VF, VF * 2, ..., VF * (NumVecs - 1), 1, VF + 1, VF * 2 + 1, ...> /// /// For example, the mask for VF = 4 and NumVecs = 2 is: /// /// <0, 4, 1, 5, 2, 6, 3, 7>. llvm::SmallVector<int, 16> createInterleaveMask(unsigned VF, unsigned NumVecs); /// Create a stride shuffle mask. /// /// This function creates a shuffle mask whose elements begin at \p Start and /// are incremented by \p Stride. The mask can be used to deinterleave an /// interleaved vector into separate vectors of vectorization factor \p VF. The /// mask is of the form: /// /// <Start, Start + Stride, ..., Start + Stride * (VF - 1)> /// /// For example, the mask for Start = 0, Stride = 2, and VF = 4 is: /// /// <0, 2, 4, 6> llvm::SmallVector<int, 16> createStrideMask(unsigned Start, unsigned Stride, unsigned VF); /// Create a sequential shuffle mask. /// /// This function creates shuffle mask whose elements are sequential and begin /// at \p Start. The mask contains \p NumInts integers and is padded with \p /// NumUndefs undef values. The mask is of the form: /// /// <Start, Start + 1, ... Start + NumInts - 1, undef_1, ... undef_NumUndefs> /// /// For example, the mask for Start = 0, NumInsts = 4, and NumUndefs = 4 is: /// /// <0, 1, 2, 3, undef, undef, undef, undef> llvm::SmallVector<int, 16> createSequentialMask(unsigned Start, unsigned NumInts, unsigned NumUndefs); /// Given a shuffle mask for a binary shuffle, create the equivalent shuffle /// mask assuming both operands are identical. This assumes that the unary /// shuffle will use elements from operand 0 (operand 1 will be unused). llvm::SmallVector<int, 16> createUnaryMask(ArrayRef<int> Mask, unsigned NumElts); /// Concatenate a list of vectors. /// /// This function generates code that concatenate the vectors in \p Vecs into a /// single large vector. The number of vectors should be greater than one, and /// their element types should be the same. The number of elements in the /// vectors should also be the same; however, if the last vector has fewer /// elements, it will be padded with undefs. Value *concatenateVectors(IRBuilderBase &Builder, ArrayRef<Value *> Vecs); /// Given a mask vector of i1, Return true if all of the elements of this /// predicate mask are known to be false or undef. That is, return true if all /// lanes can be assumed inactive. 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 true or undef. That is, return true if all /// lanes can be assumed active. bool maskIsAllOneOrUndef(Value *Mask); /// Given a mask vector of i1, Return true if any of the elements of this /// predicate mask are known to be true or undef. That is, return true if at /// least one lane can be assumed active. bool maskContainsAllOneOrUndef(Value *Mask); /// Given a mask vector of the form <Y x i1>, return an APInt (of bitwidth Y) /// for each lane which may be active. APInt possiblyDemandedEltsInMask(Value *Mask); /// The group of interleaved loads/stores sharing the same stride and /// close to each other. /// /// Each member in this group has an index starting from 0, and the largest /// index should be less than interleaved factor, which is equal to the absolute /// value of the access's stride. /// /// E.g. An interleaved load group of factor 4: /// for (unsigned i = 0; i < 1024; i+=4) { /// a = A[i]; // Member of index 0 /// b = A[i+1]; // Member of index 1 /// d = A[i+3]; // Member of index 3 /// ... /// } /// /// An interleaved store group of factor 4: /// for (unsigned i = 0; i < 1024; i+=4) { /// ... /// A[i] = a; // Member of index 0 /// A[i+1] = b; // Member of index 1 /// A[i+2] = c; // Member of index 2 /// A[i+3] = d; // Member of index 3 /// } /// /// Note: the interleaved load group could have gaps (missing members), but /// the interleaved store group doesn't allow gaps. template <typename InstTy> class InterleaveGroup { … }; /// Drive the analysis of interleaved memory accesses in the loop. /// /// Use this class to analyze interleaved accesses only when we can vectorize /// a loop. Otherwise it's meaningless to do analysis as the vectorization /// on interleaved accesses is unsafe. /// /// The analysis collects interleave groups and records the relationships /// between the member and the group in a map. class InterleavedAccessInfo { … }; } // llvm namespace #endif
Codebase Browser
llvm