SLPVectorizer.cpp File Reference

#include "llvm/Transforms/Vectorize/SLPVectorizer.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/DemandedBits.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/DOTGraphTraits.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Vectorize.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
class	llvm::slpvectorizer::BoUpSLP
	Bottom Up SLP Vectorizer. More...
struct	llvm::slpvectorizer::BoUpSLP::EdgeInfo
	This structure holds any data we need about the edges being traversed during buildTree_rec(). More...
class	llvm::slpvectorizer::BoUpSLP::VLOperands
	A helper data structure to hold the operands of a vector of instructions. More...
struct	llvm::slpvectorizer::BoUpSLP::BlockScheduling::ReadyList
struct	llvm::GraphTraits< BoUpSLP * >
struct	llvm::GraphTraits< GraphType >::ChildIteratorType
	Add the VectorizableTree to the index iterator to be able to return TreeEntry pointers. More...
class	llvm::GraphTraits< GraphType >::nodes_iterator
	For the node iterator we just need to turn the TreeEntry iterator into a TreeEntry* iterator so that it dereferences to NodeRef. More...
struct	llvm::DOTGraphTraits< BoUpSLP * >

Namespaces
	llvm
	This class represents lattice values for constants.
	llvm::slpvectorizer
	A private "module" namespace for types and utilities used by this pass.

Macros
#define	SV_NAME   "slp-vectorizer"
#define	DEBUG_TYPE   "SLP"

Functions
	STATISTIC (NumVectorInstructions, "Number of vector instructions generated")
static bool	isValidElementType (Type *Ty)
	Predicate for the element types that the SLP vectorizer supports. More...
static bool	allSameBlock (ArrayRef< Value *> VL)
static bool	allConstant (ArrayRef< Value *> VL)
static bool	isSplat (ArrayRef< Value *> VL)
static bool	isCommutative (Instruction *I)
static Optional< TargetTransformInfo::ShuffleKind >	isShuffle (ArrayRef< Value *> VL)
	Checks if the vector of instructions can be represented as a shuffle, like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 x0x0 = mul i8 x0, x0 x3x3 = mul i8 x3, x3 y1y1 = mul i8 y1, y1 y2y2 = mul i8 y2, y2 ins1 = insertelement <4 x i8> undef, i8 x0x0, i32 0 ins2 = insertelement <4 x i8> ins1, i8 x3x3, i32 1 ins3 = insertelement <4 x i8> ins2, i8 y1y1, i32 2 ins4 = insertelement <4 x i8> ins3, i8 y2y2, i32 3 ret <4 x i8> ins4 can be transformed into: %1 = shufflevector <4 x i8> x, <4 x i8> y, <4 x i32> <i32 0, i32 3, i32 5, i32 6> %2 = mul <4 x i8> %1, %1 ret <4 x i8> %2 We convert this initially to something like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 %1 = insertelement <4 x i8> undef, i8 x0, i32 0 %2 = insertelement <4 x i8> %1, i8 x3, i32 1 %3 = insertelement <4 x i8> %2, i8 y1, i32 2 %4 = insertelement <4 x i8> %3, i8 y2, i32 3 %5 = mul <4 x i8> %4, %4 %6 = extractelement <4 x i8> %5, i32 0 ins1 = insertelement <4 x i8> undef, i8 %6, i32 0 %7 = extractelement <4 x i8> %5, i32 1 ins2 = insertelement <4 x i8> ins1, i8 %7, i32 1 %8 = extractelement <4 x i8> %5, i32 2 ins3 = insertelement <4 x i8> ins2, i8 %8, i32 2 %9 = extractelement <4 x i8> %5, i32 3 ins4 = insertelement <4 x i8> ins3, i8 %9, i32 3 ret <4 x i8> ins4 InstCombiner transforms this into a shuffle and vector mul TODO: Can we split off and reuse the shuffle mask detection from TargetTransformInfo::getInstructionThroughput? More...
static Value *	isOneOf (const InstructionsState &S, Value *Op)
	Chooses the correct key for scheduling data. More...
static InstructionsState	getSameOpcode (ArrayRef< Value *> VL, unsigned BaseIndex=0)
static bool	allSameType (ArrayRef< Value *> VL)
static Optional< unsigned >	getExtractIndex (Instruction *E)
static bool	InTreeUserNeedToExtract (Value *Scalar, Instruction *UserInst, TargetLibraryInfo *TLI)
static MemoryLocation	getLocation (Instruction *I, AliasAnalysis *AA)
static bool	isSimple (Instruction *I)
static void	inversePermutation (ArrayRef< unsigned > Indices, SmallVectorImpl< unsigned > &Mask)
static bool	collectValuesToDemote (Value *V, SmallPtrSetImpl< Value *> &Expr, SmallVectorImpl< Value *> &ToDemote, SmallVectorImpl< Value *> &Roots)
static bool	hasValueBeenRAUWed (ArrayRef< Value *> VL, ArrayRef< WeakTrackingVH > VH, unsigned SliceBegin, unsigned SliceSize)
	Check that the Values in the slice in VL array are still existent in the WeakTrackingVH array. More...
static Value *	createRdxShuffleMask (unsigned VecLen, unsigned NumEltsToRdx, bool IsPairwise, bool IsLeft, IRBuilder<> &Builder)
	Generate a shuffle mask to be used in a reduction tree. More...
static bool	findBuildVector (InsertElementInst *LastInsertElem, TargetTransformInfo *TTI, SmallVectorImpl< Value *> &BuildVectorOpds, int &UserCost)
	Recognize construction of vectors like ra = insertelement <4 x float> undef, float s0, i32 0 rb = insertelement <4 x float> ra, float s1, i32 1 rc = insertelement <4 x float> rb, float s2, i32 2 rd = insertelement <4 x float> rc, float s3, i32 3 starting from the last insertelement instruction. More...
static bool	findBuildAggregate (InsertValueInst *IV, SmallVectorImpl< Value *> &BuildVectorOpds)
	Like findBuildVector, but looks for construction of aggregate. More...
static bool	PhiTypeSorterFunc (Value *V, Value *V2)
static Value *	getReductionValue (const DominatorTree *DT, PHINode *P, BasicBlock *ParentBB, LoopInfo *LI)
	Try and get a reduction value from a phi node. More...
static bool	tryToVectorizeHorReductionOrInstOperands (PHINode *P, Instruction *Root, BasicBlock *BB, BoUpSLP &R, TargetTransformInfo *TTI, const function_ref< bool(Instruction *, BoUpSLP &)> Vectorize)
	Attempt to reduce a horizontal reduction. More...

Variables
static cl::opt< int >	SLPCostThreshold ("slp-threshold", cl::init(0), cl::Hidden, cl::desc("Only vectorize if you gain more than this " "number "))
static cl::opt< bool >	ShouldVectorizeHor ("slp-vectorize-hor", cl::init(true), cl::Hidden, cl::desc("Attempt to vectorize horizontal reductions"))
static cl::opt< bool >	ShouldStartVectorizeHorAtStore ("slp-vectorize-hor-store", cl::init(false), cl::Hidden, cl::desc("Attempt to vectorize horizontal reductions feeding into a store"))
static cl::opt< int >	MaxVectorRegSizeOption ("slp-max-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits"))
static cl::opt< int >	ScheduleRegionSizeBudget ("slp-schedule-budget", cl::init(100000), cl::Hidden, cl::desc("Limit the size of the SLP scheduling region per block"))
	Limits the size of scheduling regions in a block. More...
static cl::opt< int >	MinVectorRegSizeOption ("slp-min-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits"))
static cl::opt< unsigned >	RecursionMaxDepth ("slp-recursion-max-depth", cl::init(12), cl::Hidden, cl::desc("Limit the recursion depth when building a vectorizable tree"))
static cl::opt< unsigned >	MinTreeSize ("slp-min-tree-size", cl::init(3), cl::Hidden, cl::desc("Only vectorize small trees if they are fully vectorizable"))
static cl::opt< bool >	ViewSLPTree ("view-slp-tree", cl::Hidden, cl::desc("Display the SLP trees with Graphviz"))
static const unsigned	AliasedCheckLimit = 10
static const unsigned	MaxMemDepDistance = 160
static const int	MinScheduleRegionSize = 16
	If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling regions to be handled. More...
static const char	lv_name [] = "SLP Vectorizer"

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "SLP"

Definition at line 104 of file SLPVectorizer.cpp.

SV_NAME

#define SV_NAME   "slp-vectorizer"

Definition at line 103 of file SLPVectorizer.cpp.

Referenced by hasValueBeenRAUWed().

Function Documentation

allConstant()

static bool allConstant ( ArrayRef< Value *>  VL )

static

Returns

True if all of the values in VL are constants.

Definition at line 198 of file SLPVectorizer.cpp.

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), and llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes().

allSameBlock()

static bool allSameBlock ( ArrayRef< Value *>  VL )

static

Returns

true if all of the instructions in VL are in the same block or false otherwise.

Definition at line 181 of file SLPVectorizer.cpp.

References llvm::dyn_cast(), llvm::Instruction::getParent(), I, and llvm::ArrayRef< T >::size().

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), and llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes().

allSameType()

static bool allSameType ( ArrayRef< Value *>  VL )

static

Returns

true if all of the values in VL have the same type or false otherwise.

Definition at line 407 of file SLPVectorizer.cpp.

References getType(), and llvm::ArrayRef< T >::size().

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), and llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes().

collectValuesToDemote()

static bool collectValuesToDemote ( Value *  V, SmallPtrSetImpl< Value *> &  Expr, SmallVectorImpl< Value *> &  ToDemote, SmallVectorImpl< Value *> &  Roots  )

static

Definition at line 4692 of file SLPVectorizer.cpp.

References llvm::MCID::Add, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dyn_cast(), llvm::SelectInst::getFalseValue(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::SelectInst::getTrueValue(), llvm::Value::hasOneUse(), I, llvm::PHINode::incoming_values(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MCID::Select, and SI.

Referenced by llvm::slpvectorizer::BoUpSLP::computeMinimumValueSizes().

createRdxShuffleMask()

static Value* createRdxShuffleMask ( unsigned  VecLen, unsigned  NumEltsToRdx, bool  IsPairwise, bool  IsLeft, IRBuilder<> &  Builder  )

static

Generate a shuffle mask to be used in a reduction tree.

Parameters

VecLen	The length of the vector to be reduced.
NumEltsToRdx	The number of elements that should be reduced in the vector.
IsPairwise	Whether the reduction is a pairwise or splitting reduction. A pairwise reduction will generate a mask of <0,2,...> or <1,3,..> while a splitting reduction will generate <2,3, undef,undef> for a vector of 4 and NumElts = 2.
IsLeft	True will generate a mask of even elements, odd otherwise.

Definition at line 5409 of file SLPVectorizer.cpp.

References llvm::MCID::Add, assert(), clear(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::count(), llvm::IRBuilder< T, Inserter >::CreateBinOp(), llvm::IRBuilder< T, Inserter >::CreateFCmpOGT(), llvm::IRBuilder< T, Inserter >::CreateFCmpOLT(), llvm::IRBuilder< T, Inserter >::CreateICmpSGT(), llvm::IRBuilder< T, Inserter >::CreateICmpSLT(), llvm::IRBuilder< T, Inserter >::CreateICmpUGT(), llvm::IRBuilder< T, Inserter >::CreateICmpULT(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::ConstantVector::get(), llvm::UndefValue::get(), llvm::IRBuilderBase::getInt32(), llvm::IRBuilderBase::getInt32Ty(), llvm::Instruction::getOpcode(), getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Value::getType(), llvm::Value::hasNUses(), llvm::Value::hasOneUse(), I, llvm::Instruction::isAssociative(), isAssociative(), llvm::TargetTransformInfo::ReductionFlags::IsMaxOp, llvm::TargetTransformInfo::ReductionFlags::IsSigned, llvm_unreachable, llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_OrdFMax(), llvm::PatternMatch::m_OrdFMin(), llvm::PatternMatch::m_SMax(), llvm::PatternMatch::m_SMin(), llvm::PatternMatch::m_UMax(), llvm::PatternMatch::m_UMin(), llvm::PatternMatch::m_UnordFMax(), llvm::PatternMatch::m_UnordFMin(), llvm::PatternMatch::m_Value(), llvm::CmpInst::makeCmpResultType(), llvm::PatternMatch::match(), Name, llvm::TargetTransformInfo::ReductionFlags::NoNaN, llvm::operator!=(), llvm::operator==(), P, llvm::propagateIRFlags(), llvm::MCID::Select, and SI.

findBuildAggregate()

static bool findBuildAggregate ( InsertValueInst *  IV, SmallVectorImpl< Value *> &  BuildVectorOpds  )

static

Like findBuildVector, but looks for construction of aggregate.

Returns

true if it matches.

Definition at line 6362 of file SLPVectorizer.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::InsertValueInst::getAggregateOperand(), llvm::InsertValueInst::getInsertedValueOperand(), llvm::Value::hasOneUse(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by tryToVectorizeHorReductionOrInstOperands().

findBuildVector()

static bool findBuildVector ( InsertElementInst *  LastInsertElem, TargetTransformInfo *  TTI, SmallVectorImpl< Value *> &  BuildVectorOpds, int &  UserCost  )

static

Recognize construction of vectors like ra = insertelement <4 x float> undef, float s0, i32 0 rb = insertelement <4 x float> ra, float s1, i32 1 rc = insertelement <4 x float> rb, float s2, i32 2 rd = insertelement <4 x float> rc, float s3, i32 3 starting from the last insertelement instruction.

Returns true if it matches

Definition at line 6335 of file SLPVectorizer.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::User::getOperand(), llvm::InsertElementInst::getType(), llvm::TargetTransformInfo::getVectorInstrCost(), llvm::Value::hasOneUse(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by tryToVectorizeHorReductionOrInstOperands().

getExtractIndex()

static Optional<unsigned> getExtractIndex ( Instruction *  E )

static

Returns

True if Extract{Value,Element} instruction extracts element Idx.

Definition at line 417 of file SLPVectorizer.cpp.

References assert(), llvm::dyn_cast(), E, llvm::ExtractValueInst::getNumIndices(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::ExtractValueInst::idx_begin(), and llvm::None.

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector().

getLocation()

static MemoryLocation getLocation ( Instruction *  I, AliasAnalysis *  AA  )

static

Returns

the AA location that is being access by the instruction.

Definition at line 463 of file SLPVectorizer.cpp.

References llvm::MemoryLocation::get(), and SI.

Referenced by llvm::slpvectorizer::BoUpSLP::VLOperands::dump(), llvm::DiagnosticInfoWithLocationBase::getLocationStr(), llvm::DiagnosticInfoWithLocationBase::isLocationAvailable(), llvm::StackMapParser< Endianness >::RecordAccessor::location_begin(), llvm::StackMapParser< Endianness >::RecordAccessor::location_end(), and llvm::slpvectorizer::BoUpSLP::optimizeGatherSequence().

getReductionValue()

static Value* getReductionValue ( const DominatorTree *  DT, PHINode *  P, BasicBlock *  ParentBB, LoopInfo *  LI  )

static

Try and get a reduction value from a phi node.

Given a phi node P in a block ParentBB, consider possible reductions if they come from either ParentBB or a containing loop latch.

Returns

A candidate reduction value if possible, or

nullptr 

if not possible.

Definition at line 6389 of file SLPVectorizer.cpp.

References llvm::DominatorTree::dominates(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getParent(), and getParent().

Referenced by tryToVectorizeHorReductionOrInstOperands().

getSameOpcode()

static InstructionsState getSameOpcode ( ArrayRef< Value *>  VL, unsigned  BaseIndex = 0  )

static

Returns

analysis of the Instructions in VL described in InstructionsState, the Opcode that we suppose the whole list could be vectorized even if its structure is diverse.

Definition at line 360 of file SLPVectorizer.cpp.

References llvm::any_of(), E, getOpcode(), and llvm::ArrayRef< T >::size().

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes(), llvm::slpvectorizer::BoUpSLP::getTreeCost(), hasValueBeenRAUWed(), and inversePermutation().

hasValueBeenRAUWed()

static bool hasValueBeenRAUWed ( ArrayRef< Value *>  VL, ArrayRef< WeakTrackingVH >  VH, unsigned  SliceBegin, unsigned  SliceSize  )

static

Check that the Values in the slice in VL array are still existent in the WeakTrackingVH array.

Vectorization of part of the VL array may cause later values in the VL array to become invalid. We track when this has happened in the WeakTrackingVH array.

Definition at line 5046 of file SLPVectorizer.cpp.

References assert(), B, llvm::ArrayRef< T >::begin(), llvm::dbgs(), llvm::dyn_cast(), llvm::ArrayRef< T >::end(), llvm::lltok::equal, F(), GEP, llvm::VectorType::get(), llvm::User::getOperand(), llvm::Instruction::getParent(), getSameOpcode(), getType(), llvm::Value::getType(), llvm::GetUnderlyingObject(), llvm::Value::hasOneUse(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::isConsecutiveAccess(), llvm::isPowerOf2_32(), isValidElementType(), LLVM_DEBUG, llvm::max(), llvm::None, P, llvm::PowerOf2Floor(), llvm::Type::print(), llvm::reverse(), SI, Size, llvm::SmallVectorBase::size(), llvm::ArrayRef< T >::size(), llvm::ArrayRef< T >::slice(), SLPCostThreshold, llvm::raw_string_ostream::str(), and SV_NAME.

InTreeUserNeedToExtract()

static bool InTreeUserNeedToExtract ( Value *  Scalar, Instruction *  UserInst, TargetLibraryInfo *  TLI  )

static

Returns

True if in-tree use also needs extract. This refers to possible scalar operand in vectorized instruction.

Definition at line 436 of file SLPVectorizer.cpp.

References llvm::MCID::Call, llvm::CallBase::getArgOperand(), llvm::CallBase::getNumArgOperands(), llvm::Instruction::getOpcode(), llvm::LoadInst::getPointerOperand(), llvm::StoreInst::getPointerOperand(), llvm::getVectorIntrinsicIDForCall(), llvm::hasVectorInstrinsicScalarOpd(), LLVM_FALLTHROUGH, llvm::SPII::Load, llvm::NVPTX::PTXLdStInstCode::Scalar, SI, and llvm::SPII::Store.

Referenced by llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes().

inversePermutation()

static void inversePermutation ( ArrayRef< unsigned >  Indices, SmallVectorImpl< unsigned > &  Mask  )

static

Definition at line 3443 of file SLPVectorizer.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::SmallVectorImpl< T >::clear(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::VectorType::get(), llvm::PointerType::get(), llvm::UndefValue::get(), llvm::LoadInst::getAlignment(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getFirstNonPHI(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::PHINode::getNumIncomingValues(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::LoadInst::getPointerAddressSpace(), llvm::PPC::getPredicate(), getSameOpcode(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::BitmaskEnumDetail::Mask(), llvm::propagateIRFlags(), llvm::propagateMetadata(), llvm::RISCVFenceField::R, llvm::SmallVectorImpl< T >::resize(), llvm::MCID::Select, SI, and llvm::ArrayRef< T >::size().

isCommutative()

static bool isCommutative ( Instruction *  I )

static

Returns

True if I is commutative, handles CmpInst as well as Instruction.

Definition at line 214 of file SLPVectorizer.cpp.

References llvm::Instruction::isCommutative().

Referenced by llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes(), llvm::CmpInst::getNonStrictPredicate(), llvm::InlineAsm::ConstraintInfo::Parse(), and llvm::FastISel::selectBinaryOp().

isOneOf()

static Value* isOneOf ( const InstructionsState &  S, Value *  Op  )

static

Chooses the correct key for scheduling data.

If Op has the same (or alternate) opcode as OpValue, the key is Op. Otherwise the key is OpValue.

Definition at line 350 of file SLPVectorizer.cpp.

References llvm::dyn_cast(), and I.

Referenced by llvm::slpvectorizer::BoUpSLP::getTreeCost(), and llvm::slpvectorizer::BoUpSLP::optimizeGatherSequence().

isShuffle()

static Optional<TargetTransformInfo::ShuffleKind> isShuffle ( ArrayRef< Value *>  VL )

static

Checks if the vector of instructions can be represented as a shuffle, like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 x0x0 = mul i8 x0, x0 x3x3 = mul i8 x3, x3 y1y1 = mul i8 y1, y1 y2y2 = mul i8 y2, y2 ins1 = insertelement <4 x i8> undef, i8 x0x0, i32 0 ins2 = insertelement <4 x i8> ins1, i8 x3x3, i32 1 ins3 = insertelement <4 x i8> ins2, i8 y1y1, i32 2 ins4 = insertelement <4 x i8> ins3, i8 y2y2, i32 3 ret <4 x i8> ins4 can be transformed into: %1 = shufflevector <4 x i8> x, <4 x i8> y, <4 x i32> <i32 0, i32 3, i32 5, i32 6> %2 = mul <4 x i8> %1, %1 ret <4 x i8> %2 We convert this initially to something like: x0 = extractelement <4 x i8> x, i32 0 x3 = extractelement <4 x i8> x, i32 3 y1 = extractelement <4 x i8> y, i32 1 y2 = extractelement <4 x i8> y, i32 2 %1 = insertelement <4 x i8> undef, i8 x0, i32 0 %2 = insertelement <4 x i8> %1, i8 x3, i32 1 %3 = insertelement <4 x i8> %2, i8 y1, i32 2 %4 = insertelement <4 x i8> %3, i8 y2, i32 3 %5 = mul <4 x i8> %4, %4 %6 = extractelement <4 x i8> %5, i32 0 ins1 = insertelement <4 x i8> undef, i8 %6, i32 0 %7 = extractelement <4 x i8> %5, i32 1 ins2 = insertelement <4 x i8> ins1, i8 %7, i32 1 %8 = extractelement <4 x i8> %5, i32 2 ins3 = insertelement <4 x i8> ins2, i8 %8, i32 2 %9 = extractelement <4 x i8> %5, i32 3 ins4 = insertelement <4 x i8> ins3, i8 %9, i32 3 ret <4 x i8> ins4 InstCombiner transforms this into a shuffle and vector mul TODO: Can we split off and reuse the shuffle mask detection from TargetTransformInfo::getInstructionThroughput?

Definition at line 262 of file SLPVectorizer.cpp.

References llvm::dyn_cast(), E, llvm::Instruction::getOpcode(), getOpcode(), I, llvm::None, llvm::MCID::Select, Size, llvm::ArrayRef< T >::size(), llvm::TargetTransformInfo::SK_PermuteSingleSrc, llvm::TargetTransformInfo::SK_PermuteTwoSrc, and llvm::TargetTransformInfo::SK_Select.

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), and tryToVectorizeHorReductionOrInstOperands().

isSimple()

static bool isSimple ( Instruction *  I )

static

Returns

True if the instruction is not a volatile or atomic load/store.

Definition at line 472 of file SLPVectorizer.cpp.

References MI, and SI.

Referenced by llvm::slpvectorizer::BoUpSLP::VLOperands::dump(), getMemSetPatternValue(), llvm::DOTGraphTraits< const Function * >::getNodeLabel(), llvm::codeview::TypeIndex::getSimpleKind(), llvm::codeview::TypeIndex::getSimpleMode(), llvm::RegionBase< RegionTraits< Function > >::isTopLevelRegion(), llvm::BranchFolder::MBFIWrapper::MBFIWrapper(), and llvm::codeview::TypeIndex::toArrayIndex().

isSplat()

static bool isSplat ( ArrayRef< Value *>  VL )

static

Returns

True if all of the values in VL are identical.

Definition at line 206 of file SLPVectorizer.cpp.

References llvm::ArrayRef< T >::size().

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), llvm::PPC::get_VSPLTI_elt(), llvm::APInt::getLimitedValue(), llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes(), llvm::DOTGraphTraits< BoUpSLP * >::getNodeLabel(), llvm::ShuffleVectorSDNode::getSplatIndex(), llvm::ConstantDataVector::getSplatValue(), and llvm::InstCombiner::visitShuffleVectorInst().

isValidElementType()

static bool isValidElementType ( Type *  Ty )

static

Predicate for the element types that the SLP vectorizer supports.

The most important thing to filter here are types which are invalid in LLVM vectors. We also filter target specific types which have absolutely no meaningful vectorization path such as x86_fp80 and ppc_f128. This just avoids spending time checking the cost model and realizing that they will be inevitably scalarized.

Definition at line 174 of file SLPVectorizer.cpp.

References llvm::Type::isPPC_FP128Ty(), llvm::VectorType::isValidElementType(), and llvm::Type::isX86_FP80Ty().

Referenced by llvm::slpvectorizer::BoUpSLP::canMapToVector(), llvm::ArrayType::get(), llvm::VectorType::get(), llvm::PointerType::get(), llvm::VectorType::getDoubleElementsVectorType(), llvm::PointerType::getElementType(), llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes(), hasValueBeenRAUWed(), llvm::PointerType::isLoadableOrStorableType(), and llvm::StructType::setBody().

PhiTypeSorterFunc()

static bool PhiTypeSorterFunc ( Value *  V, Value *  V2  )

static

Definition at line 6378 of file SLPVectorizer.cpp.

References llvm::Value::getType().

Referenced by tryToVectorizeHorReductionOrInstOperands().

STATISTIC()

STATISTIC	(	NumVectorInstructions	,
		"Number of vector instructions generated"
	)

tryToVectorizeHorReductionOrInstOperands()

static bool tryToVectorizeHorReductionOrInstOperands ( PHINode *  P, Instruction *  Root, BasicBlock *  BB, BoUpSLP &  R, TargetTransformInfo *  TTI, const function_ref< bool(Instruction *, BoUpSLP &)>  Vectorize  )

static

Attempt to reduce a horizontal reduction.

If it is legal to match a horizontal reduction feeding the phi node P with reduction operators Root (or one of its operands) in a basic block BB, then check if it can be done. If horizontal reduction is not found and root instruction is a binary operation, vectorization of the operands is attempted.

Returns

true if a horizontal reduction was matched and reduced or operands of one of the binary instruction were vectorized.

false if a horizontal reduction was not matched (or not possible) or no vectorization of any binary operation feeding Root instruction was performed.

Definition at line 6444 of file SLPVectorizer.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::ArrayRef< T >::begin(), llvm::BasicBlock::begin(), llvm::SmallPtrSetImplBase::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::SmallVectorTemplateCommon< T >::end(), llvm::ArrayRef< T >::end(), llvm::BasicBlock::end(), findBuildAggregate(), findBuildVector(), GEP, llvm::Module::getDataLayout(), llvm::ScalarEvolution::getMinusSCEV(), llvm::BasicBlock::getModule(), llvm::PHINode::getNumIncomingValues(), llvm::User::getOperand(), llvm::Instruction::getParent(), getReductionValue(), llvm::ScalarEvolution::getSCEV(), llvm::Value::getType(), I, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, InlineBuckets, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::insert(), isShuffle(), LLVM_DEBUG, llvm::makeArrayRef(), PhiTypeSorterFunc(), llvm::SmallVectorTemplateBase< T >::push_back(), RecursionMaxDepth, llvm::SetVector< T, Vector, Set >::remove(), llvm::reverse(), ShouldStartVectorizeHorAtStore, ShouldVectorizeHor, SI, and llvm::stable_sort().

Variable Documentation

AliasedCheckLimit

const unsigned AliasedCheckLimit = 10

static

Definition at line 156 of file SLPVectorizer.cpp.

lv_name

const char lv_name[] = "SLP Vectorizer"

static

Definition at line 6843 of file SLPVectorizer.cpp.

MaxMemDepDistance

const unsigned MaxMemDepDistance = 160

static

Definition at line 161 of file SLPVectorizer.cpp.

MaxVectorRegSizeOption

cl::opt<int> MaxVectorRegSizeOption("slp-max-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits"))

static

Referenced by llvm::slpvectorizer::BoUpSLP::BoUpSLP().

MinScheduleRegionSize

const int MinScheduleRegionSize = 16

static

If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling regions to be handled.

Definition at line 165 of file SLPVectorizer.cpp.

MinTreeSize

cl::opt<unsigned> MinTreeSize("slp-min-tree-size", cl::init(3), cl::Hidden, cl::desc("Only vectorize small trees if they are fully vectorizable"))

static

Referenced by llvm::slpvectorizer::BoUpSLP::isTreeTinyAndNotFullyVectorizable().

MinVectorRegSizeOption

cl::opt<int> MinVectorRegSizeOption("slp-min-reg-size", cl::init(128), cl::Hidden, cl::desc("Attempt to vectorize for this register size in bits"))

static

Referenced by llvm::slpvectorizer::BoUpSLP::BoUpSLP().

RecursionMaxDepth

cl::opt<unsigned> RecursionMaxDepth("slp-recursion-max-depth", cl::init(12), cl::Hidden, cl::desc("Limit the recursion depth when building a vectorizable tree"))

static

Referenced by llvm::DOTGraphTraits< BoUpSLP * >::getNodeAttributes(), and tryToVectorizeHorReductionOrInstOperands().

ScheduleRegionSizeBudget

cl::opt<int> ScheduleRegionSizeBudget("slp-schedule-budget", cl::init(100000), cl::Hidden, cl::desc("Limit the size of the SLP scheduling region per block"))

static

Limits the size of scheduling regions in a block.

It avoid long compile times for very large blocks where vector instructions are spread over a wide range. This limit is way higher than needed by real-world functions.

Referenced by llvm::slpvectorizer::BoUpSLP::BlockScheduling::ReadyList::insert().

ShouldStartVectorizeHorAtStore

cl::opt<bool> ShouldStartVectorizeHorAtStore("slp-vectorize-hor-store", cl::init(false), cl::Hidden, cl::desc( "Attempt to vectorize horizontal reductions feeding into a store"))

static

Referenced by tryToVectorizeHorReductionOrInstOperands().

ShouldVectorizeHor

cl::opt<bool> ShouldVectorizeHor("slp-vectorize-hor", cl::init(true), cl::Hidden, cl::desc("Attempt to vectorize horizontal reductions"))

static

Referenced by tryToVectorizeHorReductionOrInstOperands().

SLPCostThreshold

cl::opt<int> SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden, cl::desc("Only vectorize if you gain more than this " "number "))

static

Referenced by hasValueBeenRAUWed().

ViewSLPTree

cl::opt<bool> ViewSLPTree("view-slp-tree", cl::Hidden, cl::desc("Display the SLP trees with Graphviz"))

static

Referenced by llvm::slpvectorizer::BoUpSLP::getTreeCost().