VectorCombine.cpp File Reference

#include "llvm/Transforms/Vectorize/VectorCombine.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstSimplifyFolder.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include "llvm/Transforms/Utils/InstructionWorklist.h"

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "vector-combine"

Typedefs
using	InstLane = std::pair<Use *, int>

Functions
	STATISTIC (NumVecLoad, "Number of vector loads formed")
	STATISTIC (NumVecCmp, "Number of vector compares formed")
	STATISTIC (NumVecBO, "Number of vector binops formed")
	STATISTIC (NumVecCmpBO, "Number of vector compare + binop formed")
	STATISTIC (NumShufOfBitcast, "Number of shuffles moved after bitcast")
	STATISTIC (NumScalarOps, "Number of scalar unary + binary ops formed")
	STATISTIC (NumScalarCmp, "Number of scalar compares formed")
	STATISTIC (NumScalarIntrinsic, "Number of scalar intrinsic calls formed")
static Value *	peekThroughBitcasts (Value *V)
	Return the source operand of a potentially bitcasted value.
static bool	canWidenLoad (LoadInst *Load, const TargetTransformInfo &TTI)
static Value *	createShiftShuffle (Value *Vec, unsigned OldIndex, unsigned NewIndex, IRBuilderBase &Builder)
	Create a shuffle that translates (shifts) 1 element from the input vector to a new element location.
static Value *	translateExtract (ExtractElementInst *ExtElt, unsigned NewIndex, IRBuilderBase &Builder)
	Given an extract element instruction with constant index operand, shuffle the source vector (shift the scalar element) to a NewIndex for extraction.
static void	analyzeCostOfVecReduction (const IntrinsicInst &II, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI, InstructionCost &CostBeforeReduction, InstructionCost &CostAfterReduction)
static bool	isMemModifiedBetween (BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation &Loc, AAResults &AA)
static ScalarizationResult	canScalarizeAccess (VectorType *VecTy, Value *Idx, Instruction *CtxI, AssumptionCache &AC, const DominatorTree &DT)
	Check if it is legal to scalarize a memory access to VecTy at index Idx.
static Align	computeAlignmentAfterScalarization (Align VectorAlignment, Type *ScalarType, Value *Idx, const DataLayout &DL)
	The memory operation on a vector of ScalarType had alignment of VectorAlignment.
static InstLane	lookThroughShuffles (Use *U, int Lane)
static SmallVector< InstLane >	generateInstLaneVectorFromOperand (ArrayRef< InstLane > Item, int Op)
static bool	isFreeConcat (ArrayRef< InstLane > Item, TTI::TargetCostKind CostKind, const TargetTransformInfo &TTI)
	Detect concat of multiple values into a vector.
static Value *	generateNewInstTree (ArrayRef< InstLane > Item, FixedVectorType *Ty, const SmallPtrSet< Use *, 4 > &IdentityLeafs, const SmallPtrSet< Use *, 4 > &SplatLeafs, const SmallPtrSet< Use *, 4 > &ConcatLeafs, IRBuilderBase &Builder, const TargetTransformInfo *TTI)
static bool	feedsIntoVectorReduction (ShuffleVectorInst *SVI)
	Returns true if this ShuffleVectorInst eventually feeds into a vector reduction intrinsic (e.g., vector_reduce_add) by only following chains of shuffles and binary operators (in any combination/order).

Variables
static cl::opt< bool >	DisableVectorCombine ("disable-vector-combine", cl::init(false), cl::Hidden, cl::desc("Disable all vector combine transforms"))
static cl::opt< bool >	DisableBinopExtractShuffle ("disable-binop-extract-shuffle", cl::init(false), cl::Hidden, cl::desc("Disable binop extract to shuffle transforms"))
static cl::opt< unsigned >	MaxInstrsToScan ("vector-combine-max-scan-instrs", cl::init(30), cl::Hidden, cl::desc("Max number of instructions to scan for vector combining."))
static const unsigned	InvalidIndex = std::numeric_limits<unsigned>::max()

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "vector-combine"

Definition at line 43 of file VectorCombine.cpp.

Typedef Documentation

InstLane

using InstLane = std::pair<Use *, int>

Definition at line 2833 of file VectorCombine.cpp.

Function Documentation

analyzeCostOfVecReduction()

void analyzeCostOfVecReduction ( const IntrinsicInst & II, TTI::TargetCostKind CostKind, const TargetTransformInfo & TTI, InstructionCost & CostBeforeReduction, InstructionCost & CostAfterReduction )

static

Definition at line 1528 of file VectorCombine.cpp.

References llvm::cast(), CostKind, llvm::dyn_cast(), llvm::VectorType::get(), llvm::getArithmeticReductionInstruction(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), II, llvm::isa(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExtOrSExt(), llvm::PatternMatch::match(), and llvm::TargetTransformInfo::None.

canScalarizeAccess()

ScalarizationResult canScalarizeAccess ( VectorType * VecTy, Value * Idx, Instruction * CtxI, AssumptionCache & AC, const DominatorTree & DT )

static

Check if it is legal to scalarize a memory access to VecTy at index Idx.

Idx must access a valid vector element.

Definition at line 1714 of file VectorCombine.cpp.

References llvm::ConstantRange::binaryAnd(), llvm::CallingConv::C, llvm::computeConstantRange(), llvm::ConstantRange::contains(), llvm::dyn_cast(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::isGuaranteedNotToBePoison(), llvm::isUIntN(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_URem(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::ConstantRange::urem().

canWidenLoad()

bool canWidenLoad ( LoadInst * Load, const TargetTransformInfo & TTI )

static

Definition at line 207 of file VectorCombine.cpp.

References llvm::Type::getPrimitiveSizeInBits(), and llvm::mustSuppressSpeculation().

computeAlignmentAfterScalarization()

Align computeAlignmentAfterScalarization ( Align VectorAlignment, Type * ScalarType, Value * Idx, const DataLayout & DL )

static

The memory operation on a vector of ScalarType had alignment of VectorAlignment.

Compute the maximal, but conservatively correct, alignment that will be valid for the memory operation on a single scalar element of the same type with index Idx.

Definition at line 1765 of file VectorCombine.cpp.

References llvm::CallingConv::C, llvm::commonAlignment(), DL, and llvm::dyn_cast().

createShiftShuffle()

Value * createShiftShuffle ( Value * Vec, unsigned OldIndex, unsigned NewIndex, IRBuilderBase & Builder )

static

Create a shuffle that translates (shifts) 1 element from the input vector to a new element location.

Definition at line 563 of file VectorCombine.cpp.

References llvm::cast(), llvm::Value::getType(), and llvm::PoisonMaskElem.

Referenced by translateExtract().

feedsIntoVectorReduction()

bool feedsIntoVectorReduction ( ShuffleVectorInst * SVI )

static

Returns true if this ShuffleVectorInst eventually feeds into a vector reduction intrinsic (e.g., vector_reduce_add) by only following chains of shuffles and binary operators (in any combination/order).

The search does not go deeper than the given Depth.

Definition at line 3604 of file VectorCombine.cpp.

References llvm::cast(), llvm::dyn_cast(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), I, II, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallPtrSetImplBase::size().

generateInstLaneVectorFromOperand()

SmallVector< InstLane > generateInstLaneVectorFromOperand ( ArrayRef< InstLane > Item, int Op )

static

Definition at line 2854 of file VectorCombine.cpp.

References llvm::cast(), llvm::SmallVectorImpl< T >::emplace_back(), lookThroughShuffles(), and llvm::PoisonMaskElem.

Referenced by generateNewInstTree().

generateNewInstTree()

Value * generateNewInstTree ( ArrayRef< InstLane > Item, FixedVectorType * Ty, const SmallPtrSet< Use *, 4 > & IdentityLeafs, const SmallPtrSet< Use *, 4 > & SplatLeafs, const SmallPtrSet< Use *, 4 > & ConcatLeafs, IRBuilderBase & Builder, const TargetTransformInfo * TTI )

static

Definition at line 2902 of file VectorCombine.cpp.

References AbstractManglingParser< Derived, Alloc >::NumOps, AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::cast(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dyn_cast(), llvm::ArrayRef< T >::front(), generateInstLaneVectorFromOperand(), generateNewInstTree(), llvm::FixedVectorType::get(), I, II, llvm::isa(), llvm::isVectorIntrinsicWithScalarOpAtArg(), llvm::propagateIRFlags(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::ArrayRef< T >::size(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by generateNewInstTree().

isFreeConcat()

bool isFreeConcat ( ArrayRef< InstLane > Item, TTI::TargetCostKind CostKind, const TargetTransformInfo & TTI )

static

Detect concat of multiple values into a vector.

Definition at line 2868 of file VectorCombine.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::cast(), CostKind, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::ArrayRef< T >::front(), llvm::FixedVectorType::get(), llvm::Value::getType(), llvm::isPowerOf2_32(), llvm::ArrayRef< T >::size(), and llvm::TargetTransformInfo::SK_PermuteTwoSrc.

isMemModifiedBetween()

bool isMemModifiedBetween ( BasicBlock::iterator Begin, BasicBlock::iterator End, const MemoryLocation & Loc, AAResults & AA )

static

Definition at line 1645 of file VectorCombine.cpp.

References llvm::isModSet(), and MaxInstrsToScan.

lookThroughShuffles()

InstLane lookThroughShuffles ( Use * U, int Lane )

static

Definition at line 2835 of file VectorCombine.cpp.

References llvm::cast(), llvm::dyn_cast(), and llvm::PoisonMaskElem.

Referenced by generateInstLaneVectorFromOperand().

peekThroughBitcasts()

Value * peekThroughBitcasts ( Value * V )

static

Return the source operand of a potentially bitcasted value.

If there is no bitcast, return the input value itself.

Definition at line 201 of file VectorCombine.cpp.

References llvm::dyn_cast(), and llvm::SDNode::getOperand().

STATISTIC() [1/8]

STATISTIC	(	NumScalarCmp	,
		"Number of scalar compares formed"	)

STATISTIC() [2/8]

STATISTIC	(	NumScalarIntrinsic	,
		"Number of scalar intrinsic calls formed"	)

STATISTIC() [3/8]

STATISTIC	(	NumScalarOps	,
		"Number of scalar unary + binary ops formed"	)

STATISTIC() [4/8]

STATISTIC	(	NumShufOfBitcast	,
		"Number of shuffles moved after bitcast"	)

STATISTIC() [5/8]

STATISTIC	(	NumVecBO	,
		"Number of vector binops formed"	)

STATISTIC() [6/8]

STATISTIC	(	NumVecCmp	,
		"Number of vector compares formed"	)

STATISTIC() [7/8]

STATISTIC	(	NumVecCmpBO	,
		"Number of vector compare + binop formed"	)

STATISTIC() [8/8]

STATISTIC	(	NumVecLoad	,
		"Number of vector loads formed"	)

translateExtract()

Value * translateExtract ( ExtractElementInst * ExtElt, unsigned NewIndex, IRBuilderBase & Builder )

static

Given an extract element instruction with constant index operand, shuffle the source vector (shift the scalar element) to a NewIndex for extraction.

Return null if the input can be constant folded, so that we are not creating unnecessary instructions.

Definition at line 578 of file VectorCombine.cpp.

References assert(), llvm::CallingConv::C, llvm::cast(), createShiftShuffle(), llvm::ExtractElementInst::getIndexOperand(), llvm::ExtractElementInst::getVectorOperand(), llvm::isa(), and X.

Variable Documentation

DisableBinopExtractShuffle

cl::opt< bool > DisableBinopExtractShuffle("disable-binop-extract-shuffle", cl::init(false), cl::Hidden, cl::desc("Disable binop extract to shuffle transforms")) ( "disable-binop-extract-shuffle" , cl::init(false) , cl::Hidden , cl::desc("Disable binop extract to shuffle transforms")  )

static

DisableVectorCombine

cl::opt< bool > DisableVectorCombine("disable-vector-combine", cl::init(false), cl::Hidden, cl::desc("Disable all vector combine transforms")) ( "disable-vector-combine" , cl::init(false) , cl::Hidden , cl::desc("Disable all vector combine transforms")  )

static

InvalidIndex

const unsigned InvalidIndex = std::numeric_limits<unsigned>::max()

static

Definition at line 70 of file VectorCombine.cpp.

MaxInstrsToScan

cl::opt< unsigned > MaxInstrsToScan("vector-combine-max-scan-instrs", cl::init(30), cl::Hidden, cl::desc("Max number of instructions to scan for vector combining.")) ( "vector-combine-max-scan-instrs" , cl::init(30) , cl::Hidden , cl::desc("Max number of instructions to scan for vector combining.")  )

static