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/SmallVectorExtras.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/IR/ProfDataUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.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<Value *, 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	isEquivBitcast (Value *X, Value *Y)
	Helper to peek through bitcasts to the same 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, const SimplifyQuery &SQ)
	Check if it is legal to scalarize a memory access to VecTy at index Idx.
static IntegerType *	getScalarizedGEPIndexInfo (VectorType *VecTy, Value *Idx, Type *PtrTy, const DataLayout &DL)
	Return the GEP index type if the unsigned vector index Idx can be represented by an inbounds GEP.
static Value *	materializeScalarizedGEPIndex (Value *Idx, IntegerType *GEPIndexTy, IRBuilderBase &Builder)
	Materialize an index for a scalarized GEP after profitability is known.
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 (Value *V, 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, Use *From, const DenseSet< std::pair< Value *, Use * > > &IdentityLeafs, const DenseSet< std::pair< Value *, Use * > > &SplatLeafs, const DenseSet< std::pair< Value *, Use * > > &ConcatLeafs, IRBuilderBase &Builder, InstructionWorklist &WorkList, const TargetTransformInfo *TTI)
static bool	isKnownNonPositive (const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
	Used by foldReduceAddCmpZero to check if we can prove that a value is non-positive.
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).
static unsigned	getAlignedNumElements (unsigned MaxIdx, FixedVectorType *LoadTy, const TargetTransformInfo &TTI, const DataLayout &DL)
	Given the maximum shuffle index and load vector type, compute the number of elements for the shrunk load, rounding up to the next full vector register boundary to avoid scalar remainders that legalize poorly.

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 47 of file VectorCombine.cpp.

Typedef Documentation

InstLane

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

Definition at line 3624 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 1596 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, const SimplifyQuery & SQ )

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 1792 of file VectorCombine.cpp.

References llvm::SimplifyQuery::AC, llvm::ConstantRange::binaryAnd(), C(), llvm::computeConstantRange(), llvm::ConstantRange::contains(), llvm::SimplifyQuery::CxtI, llvm::SimplifyQuery::DT, 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(), uint64_t, and llvm::ConstantRange::urem().

canWidenLoad()

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

static

Definition at line 230 of file VectorCombine.cpp.

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

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 1915 of file VectorCombine.cpp.

References 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 591 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 5399 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 3645 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, Use * From, const DenseSet< std::pair< Value *, Use * > > & IdentityLeafs, const DenseSet< std::pair< Value *, Use * > > & SplatLeafs, const DenseSet< std::pair< Value *, Use * > > & ConcatLeafs, IRBuilderBase & Builder, InstructionWorklist & WorkList, const TargetTransformInfo * TTI )

static

Definition at line 3693 of file VectorCombine.cpp.

References AbstractManglingParser< Derived, Alloc >::NumOps, AbstractManglingParser< Derived, Alloc >::Ops, llvm::SmallVectorImpl< T >::append(), assert(), llvm::cast(), llvm::dyn_cast(), E(), llvm::ArrayRef< T >::front(), generateInstLaneVectorFromOperand(), generateNewInstTree(), llvm::FixedVectorType::get(), I, II, llvm::isa(), llvm::isVectorIntrinsicWithScalarOpAtArg(), lookThroughShuffles(), llvm::PoisonMaskElem, llvm::propagateIRFlags(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::InstructionWorklist::pushValue(), llvm::ArrayRef< T >::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::Values.

Referenced by generateNewInstTree().

getAlignedNumElements()

unsigned getAlignedNumElements ( unsigned MaxIdx, FixedVectorType * LoadTy, const TargetTransformInfo & TTI, const DataLayout & DL )

static

Given the maximum shuffle index and load vector type, compute the number of elements for the shrunk load, rounding up to the next full vector register boundary to avoid scalar remainders that legalize poorly.

Definition at line 6601 of file VectorCombine.cpp.

References llvm::alignTo(), DL, llvm::VectorType::getElementType(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isZero(), RegSize, and llvm::TargetTransformInfo::RGK_FixedWidthVector.

getScalarizedGEPIndexInfo()

IntegerType * getScalarizedGEPIndexInfo ( VectorType * VecTy, Value * Idx, Type * PtrTy, const DataLayout & DL )

static

Return the GEP index type if the unsigned vector index Idx can be represented by an inbounds GEP.

A null result means that the maximum byte offset cannot be represented by the pointer's signed GEP index type.

unsigned lane range | v MaxByteOffset = MaxLane * element store size | +– unavailable or outside signed GEP range --> reject | v valid range --> use the pointer's GEP index type

Definition at line 1850 of file VectorCombine.cpp.

References C(), llvm::cast(), DL, llvm::dyn_cast(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::getFixedValue(), llvm::APInt::getSignedMaxValue(), llvm::details::FixedOrScalableQuantity< LeafTy, ValueTy >::isScalable(), llvm::APInt::sext(), llvm::APInt::ugt(), and uint64_t.

isEquivBitcast()

bool isEquivBitcast ( Value * X, Value * Y )

static

Helper to peek through bitcasts to the same value.

Definition at line 225 of file VectorCombine.cpp.

References llvm::peekThroughBitcasts(), X, and Y.

isFreeConcat()

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

static

Detect concat of multiple values into a vector.

Definition at line 3658 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.

isKnownNonPositive()

bool isKnownNonPositive ( const Value * V, const SimplifyQuery & SQ, unsigned Depth = 0 )

static

Used by foldReduceAddCmpZero to check if we can prove that a value is non-positive.

KnownBits cannot see sext <? x i1> as non-positive: each top bit equals a single unknown input bit, which a per-bit lattice cannot track. The fold's target shape is popcount-style sums of <N x i1> valid/invalid masks (e.g. ray-intersection hits) tested for any-hit. Previous attempts to approximate the known bits of such expressions were using a fully recursive value tracking approach to infer a constant range but ultimately turned to be too expensive in compile time.

Definition at line 5287 of file VectorCombine.cpp.

References A(), llvm::SimplifyQuery::AC, B(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::SimplifyQuery::CxtI, llvm::Depth, llvm::SimplifyQuery::DL, llvm::SimplifyQuery::DT, isKnownNonPositive(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.

Referenced by isKnownNonPositive().

isMemModifiedBetween()

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

static

Definition at line 1718 of file VectorCombine.cpp.

References llvm::isModSet(), MaxInstrsToScan, and llvm::willNotFreeBetween().

lookThroughShuffles()

InstLane lookThroughShuffles ( Value * V, int Lane )

static

Definition at line 3626 of file VectorCombine.cpp.

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

Referenced by generateInstLaneVectorFromOperand(), and generateNewInstTree().

materializeScalarizedGEPIndex()

Value * materializeScalarizedGEPIndex ( Value * Idx, IntegerType * GEPIndexTy, IRBuilderBase & Builder )

static

Materialize an index for a scalarized GEP after profitability is known.

Vector element indices are unsigned, but GEP sign-extends narrow integer indices. Widen a narrow index explicitly so its unsigned value is retained.

Definition at line 1901 of file VectorCombine.cpp.

References llvm::IntegerType::getBitWidth(), llvm::Type::getIntegerBitWidth(), llvm::Value::getName(), and llvm::Value::getType().

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 218 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 606 of file VectorCombine.cpp.

References assert(), 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 74 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