#include "InstCombineInternal.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

Include dependency graph for InstCombineVectorOps.cpp:

Classes
struct	BinopElts
	These are the ingredients in an alternate form binary operator as described below. More...

Macros
#define	DEBUG_TYPE "instcombine"

Typedefs
using	ShuffleOps = std::pair< Value , Value >
	We are building a shuffle to create V, which is a sequence of insertelement, extractelement pairs. More...

Functions
static bool	cheapToScalarize (Value *V, bool IsConstantExtractIndex)
	Return true if the value is cheaper to scalarize than it is to leave as a vector operation. More...

static Instruction *	foldBitcastExtElt (ExtractElementInst &Ext, InstCombiner::BuilderTy &Builder, bool IsBigEndian)

static bool	collectSingleShuffleElements (Value V, Value LHS, Value RHS, SmallVectorImpl< Constant > &Mask)
	If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mask and true. More...

static void	replaceExtractElements (InsertElementInst InsElt, ExtractElementInst ExtElt, InstCombiner &IC)
	If we have insertion into a vector that is wider than the vector that we are extracting from, try to widen the source vector to allow a single shufflevector to replace one or more insert/extract pairs. More...

static ShuffleOps	collectShuffleElements (Value V, SmallVectorImpl< Constant > &Mask, Value *PermittedRHS, InstCombiner &IC)

static bool	isShuffleEquivalentToSelect (ShuffleVectorInst &Shuf)

static Instruction *	foldInsSequenceIntoBroadcast (InsertElementInst &InsElt)

static Instruction *	hoistInsEltConst (InsertElementInst &InsElt2, InstCombiner::BuilderTy &Builder)
	If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a constant into the vector, canonicalize that constant insertion before the insertion of a variable: More...

static Instruction *	foldConstantInsEltIntoShuffle (InsertElementInst &InsElt)
	insertelt (shufflevector X, CVec, Mask\|insertelt X, C1, CIndex1), C, CIndex –> shufflevector X, CVec', Mask' More...

static bool	canEvaluateShuffled (Value *V, ArrayRef< int > Mask, unsigned Depth=5)
	Return true if we can evaluate the specified expression tree if the vector elements were shuffled in a different order. More...

static Value *	buildNew (Instruction I, ArrayRef< Value > NewOps)
	Rebuild a new instruction just like 'I' but with the new operands given. More...

static Value *	evaluateInDifferentElementOrder (Value *V, ArrayRef< int > Mask)

static void	recognizeIdentityMask (const SmallVectorImpl< int > &Mask, bool &isLHSID, bool &isRHSID)

static bool	isShuffleExtractingFromLHS (ShuffleVectorInst &SVI, SmallVector< int, 16 > &Mask)

static BinopElts	getAlternateBinop (BinaryOperator *BO, const DataLayout &DL)
	Binops may be transformed into binops with different opcodes and operands. More...

static Instruction *	foldSelectShuffleWith1Binop (ShuffleVectorInst &Shuf)

static Instruction *	foldSelectShuffle (ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
	Try to fold shuffles that are the equivalent of a vector select. More...

static Instruction *	narrowVectorSelect (ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder)
	Match a shuffle-select-shuffle pattern where the shuffles are widening and narrowing (concatenating with undef and extracting back to the original length). More...

static Instruction *	foldIdentityExtractShuffle (ShuffleVectorInst &Shuf)
	Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask. More...

static Instruction *	foldShuffleWithInsert (ShuffleVectorInst &Shuf)
	Try to replace a shuffle with an insertelement. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "instcombine"

Definition at line 46 of file InstCombineVectorOps.cpp.

Typedef Documentation

◆ ShuffleOps

using ShuffleOps = std::pair<Value *, Value *>

We are building a shuffle to create V, which is a sequence of insertelement, extractelement pairs.

If PermittedRHS is set, then we must either use it or not rely on the second vector source. Return a std::pair containing the left and right vectors of the proposed shuffle (or 0), and set the Mask parameter as required.

Note: we intentionally don't try to fold earlier shuffles since they have often been chosen carefully to be efficiently implementable on the target.

Definition at line 526 of file InstCombineVectorOps.cpp.

Function Documentation

◆ buildNew()

static Value* buildNew	(	Instruction *	I,
		ArrayRef< Value *>	NewOps
	)

static

Rebuild a new instruction just like 'I' but with the new operands given.

In the event of type mismatch, the type of the operands is correct.

Definition at line 1039 of file InstCombineVectorOps.cpp.

References llvm::MCID::Add, assert(), llvm::BinaryOperator::Create(), llvm::CastInst::Create(), llvm::GetElementPtrInst::Create(), GEP, llvm::VectorType::get(), llvm::Instruction::getOpcode(), getOpcode(), llvm::PPC::getPredicate(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::Instruction::hasNoSignedWrap(), llvm::Instruction::hasNoUnsignedWrap(), I, llvm::Instruction::isExact(), llvm_unreachable, llvm::GetElementPtrInst::setIsInBounds(), llvm::ArrayRef< T >::size(), and llvm::ArrayRef< T >::slice().

Referenced by evaluateInDifferentElementOrder().

◆ canEvaluateShuffled()

static bool canEvaluateShuffled	(	Value *	V,
		ArrayRef< int >	Mask,
		unsigned	Depth = `5`
	)

static

Return true if we can evaluate the specified expression tree if the vector elements were shuffled in a different order.

Definition at line 956 of file InstCombineVectorOps.cpp.

References llvm::MCID::Add, llvm::Depth, llvm::dyn_cast(), llvm::ConstantInt::getLimitedValue(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::Value::hasOneUse(), I, llvm::Type::isVectorTy(), llvm::BitmaskEnumDetail::Mask(), llvm::User::operands(), and llvm::ArrayRef< T >::size().

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ cheapToScalarize()

static bool cheapToScalarize	(	Value *	V,
		bool	IsConstantExtractIndex
	)

static

Return true if the value is cheaper to scalarize than it is to leave as a vector operation.

IsConstantExtractIndex indicates whether we are extracting one known element from a vector constant.

FIXME: It's possible to create more instructions than previously existed.

Definition at line 53 of file InstCombineVectorOps.cpp.

Referenced by llvm::InstCombiner::visitExtractElementInst().

◆ collectShuffleElements()

static ShuffleOps collectShuffleElements	(	Value *	V,
		SmallVectorImpl< Constant *> &	Mask,
		Value *	PermittedRHS,
		InstCombiner &	IC
	)

static

Definition at line 528 of file InstCombineVectorOps.cpp.

References assert(), llvm::SmallVectorImpl< T >::assign(), collectSingleShuffleElements(), llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::Type::getInt32Ty(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::Type::isVectorTy(), llvm::BitmaskEnumDetail::Mask(), llvm::SmallVectorTemplateBase< T >::push_back(), and replaceExtractElements().

Referenced by llvm::InstCombiner::visitInsertElementInst().

◆ collectSingleShuffleElements()

static bool collectSingleShuffleElements	(	Value *	V,
		Value *	LHS,
		Value *	RHS,
		SmallVectorImpl< Constant *> &	Mask
	)

static

If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mask and true.

Otherwise, return false.

Definition at line 367 of file InstCombineVectorOps.cpp.

References assert(), llvm::SmallVectorImpl< T >::assign(), llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::Type::getInt32Ty(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by collectShuffleElements().

◆ evaluateInDifferentElementOrder()

static Value* evaluateInDifferentElementOrder	(	Value *	V,
		ArrayRef< int >	Mask
	)

static

◆ foldBitcastExtElt()

static Instruction* foldBitcastExtElt	(	ExtractElementInst &	Ext,
		InstCombiner::BuilderTy &	Builder,
		bool	IsBigEndian
	)

static

Definition at line 163 of file InstCombineVectorOps.cpp.

References llvm::IRBuilder< T, Inserter >::CreateBitCast(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::findScalarElement(), llvm::Value::getContext(), llvm::ExtractElementInst::getIndexOperand(), llvm::Type::getIntNTy(), llvm::SequentialType::getNumElements(), llvm::Type::getPrimitiveSizeInBits(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::ExtractElementInst::getVectorOperand(), llvm::ExtractElementInst::getVectorOperandType(), llvm::Value::hasOneUse(), llvm::Type::isFloatingPointTy(), llvm::Type::isVectorTy(), llvm::PatternMatch::m_BitCast(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_InsertElement(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::NVPTX::PTXLdStInstCode::Scalar, and X.

Referenced by llvm::InstCombiner::visitExtractElementInst().

◆ foldConstantInsEltIntoShuffle()

static Instruction* foldConstantInsEltIntoShuffle ( InsertElementInst & InsElt )

static

insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex –> shufflevector X, CVec', Mask'

Definition at line 761 of file InstCombineVectorOps.cpp.

References assert(), llvm::sys::path::begin(), llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ConstantVector::get(), llvm::UndefValue::get(), llvm::Constant::getAggregateElement(), llvm::Value::getContext(), llvm::SequentialType::getElementType(), llvm::Type::getInt32Ty(), llvm::SequentialType::getNumElements(), llvm::User::getOperand(), llvm::Value::getType(), llvm::InsertElementInst::getType(), llvm::Type::getVectorNumElements(), I, Int32Ty, isShuffleEquivalentToSelect(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_ConstantInt(), llvm::BitmaskEnumDetail::Mask(), and llvm::PatternMatch::match().

Referenced by llvm::InstCombiner::visitInsertElementInst().

◆ foldIdentityExtractShuffle()

static Instruction* foldIdentityExtractShuffle ( ShuffleVectorInst & Shuf )

static

Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.

Definition at line 1492 of file InstCombineVectorOps.cpp.

References assert(), llvm::ConstantVector::get(), llvm::Constant::getAggregateElement(), llvm::ShuffleVectorInst::getMask(), llvm::User::getOperand(), getType(), llvm::ShuffleVectorInst::getType(), llvm::Type::getVectorNumElements(), llvm::ShuffleVectorInst::isIdentityWithExtract(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_ShuffleVector(), llvm::PatternMatch::m_Value(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ foldInsSequenceIntoBroadcast()

static Instruction* foldInsSequenceIntoBroadcast ( InsertElementInst & InsElt )

static

Definition at line 670 of file InstCombineVectorOps.cpp.

References llvm::any_of(), llvm::InsertElementInst::Create(), llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ConstantAggregateZero::get(), llvm::VectorType::get(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::Type::getInt32Ty(), llvm::SequentialType::getNumElements(), llvm::User::getOperand(), llvm::InsertElementInst::getType(), llvm::Value::hasOneUse(), isZero(), and llvm::Instruction::user_back().

Referenced by llvm::InstCombiner::visitInsertElementInst().

◆ foldSelectShuffle()

static Instruction* foldSelectShuffle	(	ShuffleVectorInst &	Shuf,
		InstCombiner::BuilderTy &	Builder,
		const DataLayout &	DL
	)

static

Try to fold shuffles that are the equivalent of a vector select.

Definition at line 1341 of file InstCombineVectorOps.cpp.

References llvm::Instruction::andIRFlags(), assert(), llvm::Constant::containsUndefElement(), llvm::Instruction::copyIRFlags(), llvm::BinaryOperator::Create(), llvm::IRBuilder< T, Inserter >::CreateShuffleVector(), llvm::Instruction::dropPoisonGeneratingFlags(), foldSelectShuffleWith1Binop(), getAlternateBinop(), llvm::ShuffleVectorInst::getMask(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::getSafeVectorConstantForBinop(), llvm::ConstantExpr::getShuffleVector(), llvm::Value::hasOneUse(), I, llvm::Instruction::isIntDivRem(), llvm::ShuffleVectorInst::isSelect(), llvm::Instruction::isShift(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_Value(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::Instruction::setHasNoSignedWrap(), X, and Y.

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ foldSelectShuffleWith1Binop()

static Instruction* foldSelectShuffleWith1Binop ( ShuffleVectorInst & Shuf )

static

◆ foldShuffleWithInsert()

static Instruction* foldShuffleWithInsert ( ShuffleVectorInst & Shuf )

static

Try to replace a shuffle with an insertelement.

Definition at line 1527 of file InstCombineVectorOps.cpp.

References assert(), llvm::ShuffleVectorInst::commuteShuffleMask(), llvm::InsertElementInst::Create(), llvm::ConstantInt::get(), llvm::User::getOperand(), llvm::ShuffleVectorInst::getShuffleMask(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_InsertElement(), llvm::PatternMatch::m_Value(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::NVPTX::PTXLdStInstCode::Scalar, llvm::SmallVectorBase::size(), and std::swap().

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ getAlternateBinop()

static BinopElts getAlternateBinop	(	BinaryOperator *	BO,
		const DataLayout &	DL
	)

static

Binops may be transformed into binops with different opcodes and operands.

Reverse the usual canonicalization to enable folds with the non-canonical form of the binop. If a transform is possible, return the elements of the new binop. If not, return invalid elements.

Definition at line 1262 of file InstCombineVectorOps.cpp.

References llvm::MCID::Add, C, llvm::ConstantInt::get(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::ConstantExpr::getShl(), llvm::Value::getType(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Constant(), llvm::MaskedValueIsZero(), and llvm::PatternMatch::match().

Referenced by foldSelectShuffle().

◆ hoistInsEltConst()

static Instruction* hoistInsEltConst	(	InsertElementInst &	InsElt2,
		InstCombiner::BuilderTy &	Builder
	)

static

If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a constant into the vector, canonicalize that constant insertion before the insertion of a variable:

insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 –> insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1

This has the potential of eliminating the 2nd insertelement instruction via constant folding of the scalar constant into a vector constant.

Definition at line 738 of file InstCombineVectorOps.cpp.

References llvm::InsertElementInst::Create(), llvm::IRBuilder< T, Inserter >::CreateInsertElement(), llvm::dyn_cast(), llvm::User::getOperand(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), X, and Y.

Referenced by llvm::InstCombiner::visitInsertElementInst().

◆ isShuffleEquivalentToSelect()

static bool isShuffleEquivalentToSelect ( ShuffleVectorInst & Shuf )

static

Definition at line 647 of file InstCombineVectorOps.cpp.

References llvm::ShuffleVectorInst::getMask(), llvm::ShuffleVectorInst::getMaskValue(), llvm::User::getOperand(), llvm::Value::getType(), and llvm::Type::getVectorNumElements().

Referenced by foldConstantInsEltIntoShuffle().

◆ isShuffleExtractingFromLHS()

static bool isShuffleExtractingFromLHS	(	ShuffleVectorInst &	SVI,
		SmallVector< int, 16 > &	Mask
	)

static

Definition at line 1232 of file InstCombineVectorOps.cpp.

References llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::front(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::getVectorNumElements(), I, and llvm::SmallVectorBase::size().

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ narrowVectorSelect()

static Instruction* narrowVectorSelect	(	ShuffleVectorInst &	Shuf,
		InstCombiner::BuilderTy &	Builder
	)

static

Match a shuffle-select-shuffle pattern where the shuffles are widening and narrowing (concatenating with undef and extracting back to the original length).

This allows replacing the wide select with a narrow select.

Definition at line 1459 of file InstCombineVectorOps.cpp.

References llvm::SelectInst::Create(), llvm::IRBuilder< T, Inserter >::CreateShuffleVector(), llvm::UndefValue::get(), llvm::ShuffleVectorInst::getMask(), llvm::User::getOperand(), llvm::Value::getType(), llvm::ShuffleVectorInst::getType(), llvm::Type::getVectorNumElements(), llvm::ShuffleVectorInst::isIdentityWithExtract(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_OneUse(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_ShuffleVector(), llvm::PatternMatch::m_Undef(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::RegState::Undef, X, and Y.

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ recognizeIdentityMask()

static void recognizeIdentityMask	(	const SmallVectorImpl< int > &	Mask,
		bool &	isLHSID,
		bool &	isRHSID
	)

static

Definition at line 1212 of file InstCombineVectorOps.cpp.

References llvm::SmallVectorBase::size().

Referenced by llvm::InstCombiner::visitShuffleVectorInst().

◆ replaceExtractElements()

static void replaceExtractElements	(	InsertElementInst *	InsElt,
		ExtractElementInst *	ExtElt,
		InstCombiner &	IC
	)

static

If we have insertion into a vector that is wider than the vector that we are extracting from, try to widen the source vector to allow a single shufflevector to replace one or more insert/extract pairs.

Definition at line 444 of file InstCombineVectorOps.cpp.

References llvm::ExtractElementInst::Create(), llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ConstantVector::get(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::SequentialType::getElementType(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Type::getInt32Ty(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::InsertElementInst::getType(), llvm::Type::getVectorNumElements(), llvm::ExtractElementInst::getVectorOperand(), llvm::ExtractElementInst::getVectorOperandType(), llvm::Value::hasOneUse(), llvm::Instruction::insertAfter(), llvm::InstCombiner::InsertNewInstWith(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::InstCombiner::replaceInstUsesWith(), llvm::Instruction::user_back(), and llvm::Value::users().

Referenced by collectShuffleElements().

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ ShuffleOps

Function Documentation

◆ buildNew()

◆ canEvaluateShuffled()

◆ cheapToScalarize()

◆ collectShuffleElements()

◆ collectSingleShuffleElements()

◆ evaluateInDifferentElementOrder()

◆ foldBitcastExtElt()

◆ foldConstantInsEltIntoShuffle()

◆ foldIdentityExtractShuffle()

◆ foldInsSequenceIntoBroadcast()

◆ foldSelectShuffle()

◆ foldSelectShuffleWith1Binop()

◆ foldShuffleWithInsert()

◆ getAlternateBinop()

◆ hoistInsEltConst()

◆ isShuffleEquivalentToSelect()

◆ isShuffleExtractingFromLHS()

◆ narrowVectorSelect()

◆ recognizeIdentityMask()

◆ replaceExtractElements()