#include "InstCombineInternal.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"

Include dependency graph for InstCombineLoadStoreAlloca.cpp:

Macros
#define	DEBUG_TYPE "instcombine"

Functions
	STATISTIC (NumDeadStore, "Number of dead stores eliminated")

	STATISTIC (NumGlobalCopies, "Number of allocas copied from constant global")

static bool	pointsToConstantGlobal (Value *V)
	pointsToConstantGlobal - Return true if V (possibly indirectly) points to some part of a constant global variable. More...

static bool	isOnlyCopiedFromConstantGlobal (Value V, MemTransferInst &TheCopy, SmallVectorImpl< Instruction *> &ToDelete)
	isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) pointer to an alloca. More...

static MemTransferInst *	isOnlyCopiedFromConstantGlobal (AllocaInst AI, SmallVectorImpl< Instruction > &ToDelete)
	isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only modified by a copy from a constant global. More...

static bool	isDereferenceableForAllocaSize (const Value V, const AllocaInst AI, const DataLayout &DL)
	Returns true if V is dereferenceable for size of alloca. More...

static Instruction *	simplifyAllocaArraySize (InstCombiner &IC, AllocaInst &AI)

static bool	isSupportedAtomicType (Type *Ty)

static LoadInst *	combineLoadToNewType (InstCombiner &IC, LoadInst &LI, Type *NewTy, const Twine &Suffix="")
	Helper to combine a load to a new type. More...

static StoreInst *	combineStoreToNewValue (InstCombiner &IC, StoreInst &SI, Value *V)
	Combine a store to a new type. More...

static bool	isMinMaxWithLoads (Value *V)
	Returns true if instruction represent minmax pattern like: select ((cmp load V1, load V2), V1, V2). More...

static Instruction *	combineLoadToOperationType (InstCombiner &IC, LoadInst &LI)
	Combine loads to match the type of their uses' value after looking through intervening bitcasts. More...

static Instruction *	unpackLoadToAggregate (InstCombiner &IC, LoadInst &LI)

static bool	isObjectSizeLessThanOrEq (Value *V, uint64_t MaxSize, const DataLayout &DL)

static bool	canReplaceGEPIdxWithZero (InstCombiner &IC, GetElementPtrInst GEPI, Instruction MemI, unsigned &Idx)

template<typename T >
static Instruction *	replaceGEPIdxWithZero (InstCombiner &IC, Value *Ptr, T &MemI)

static bool	canSimplifyNullStoreOrGEP (StoreInst &SI)

static bool	canSimplifyNullLoadOrGEP (LoadInst &LI, Value *Op)

static Value *	likeBitCastFromVector (InstCombiner &IC, Value *V)
	Look for extractelement/insertvalue sequence that acts like a bitcast. More...

static bool	combineStoreToValueType (InstCombiner &IC, StoreInst &SI)
	Combine stores to match the type of value being stored. More...

static bool	unpackStoreToAggregate (InstCombiner &IC, StoreInst &SI)

static bool	equivalentAddressValues (Value A, Value B)
	equivalentAddressValues - Test if A and B will obviously have the same value. More...

static bool	removeBitcastsFromLoadStoreOnMinMax (InstCombiner &IC, StoreInst &SI)
	Converts store (bitcast (load (bitcast (select ...)))) to store (load (select ...)), where select is minmax: select ((cmp load V1, load V2), V1, V2). More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "instcombine"

Definition at line 31 of file InstCombineLoadStoreAlloca.cpp.

Function Documentation

◆ canReplaceGEPIdxWithZero()

static bool canReplaceGEPIdxWithZero	(	InstCombiner &	IC,
		GetElementPtrInst *	GEPI,
		Instruction *	MemI,
		unsigned &	Idx
	)

static

Definition at line 880 of file InstCombineLoadStoreAlloca.cpp.

References llvm::InstCombiner::computeKnownBits(), llvm::InstCombiner::getDataLayout(), llvm::GetElementPtrInst::getIndexedType(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::GetElementPtrInst::getSourceElementType(), llvm::DataLayout::getTypeAllocSize(), I, llvm::GetElementPtrInst::idx_begin(), llvm::ARM_PROC::IE, llvm::GetElementPtrInst::isInBounds(), llvm::KnownBits::isNonNegative(), and isObjectSizeLessThanOrEq().

Referenced by replaceGEPIdxWithZero().

◆ canSimplifyNullLoadOrGEP()

static bool canSimplifyNullLoadOrGEP	(	LoadInst &	LI,
		Value *	Op
	)

static

Definition at line 978 of file InstCombineLoadStoreAlloca.cpp.

References llvm::Instruction::getFunction(), llvm::LoadInst::getPointerAddressSpace(), and llvm::NullPointerIsDefined().

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

◆ canSimplifyNullStoreOrGEP()

static bool canSimplifyNullStoreOrGEP ( StoreInst & SI )

static

Definition at line 967 of file InstCombineLoadStoreAlloca.cpp.

References llvm::Instruction::getFunction(), llvm::StoreInst::getPointerAddressSpace(), llvm::StoreInst::getPointerOperand(), and llvm::NullPointerIsDefined().

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

◆ combineLoadToNewType()

static LoadInst* combineLoadToNewType	(	InstCombiner &	IC,
		LoadInst &	LI,
		Type *	NewTy,
		const Twine &	Suffix = `""`
	)

static

Helper to combine a load to a new type.

This just does the work of combining a load to a new type. It handles metadata, etc., and returns the new instruction. The NewTy should be the loaded value type. This will convert it to a pointer, cast the operand to that pointer type, load it, etc.

Note that this will create all of the instructions with whatever insert point the InstCombiner currently is using.

Definition at line 452 of file InstCombineLoadStoreAlloca.cpp.

Referenced by combineLoadToOperationType(), removeBitcastsFromLoadStoreOnMinMax(), and unpackLoadToAggregate().

◆ combineLoadToOperationType()

static Instruction* combineLoadToOperationType	(	InstCombiner &	IC,
		LoadInst &	LI
	)

static

Combine loads to match the type of their uses' value after looking through intervening bitcasts.

The core idea here is that if the result of a load is used in an operation, we should load the type most conducive to that operation. For example, when loading an integer and converting that immediately to a pointer, we should instead directly load a pointer.

However, this routine must never change the width of a load or the number of loads as that would introduce a semantic change. This combine is expected to be a semantic no-op which just allows loads to more closely model the types of their consuming operations.

Currently, we also refuse to change the precise type used for an atomic load or a volatile load. This is debatable, and might be reasonable to change later. However, it is risky in case some backend or other part of LLVM is relying on the exact type loaded to select appropriate atomic operations.

Definition at line 610 of file InstCombineLoadStoreAlloca.cpp.

References llvm::all_of(), assert(), llvm::InstCombiner::Builder, combineLoadToNewType(), combineStoreToNewValue(), llvm::dyn_cast(), llvm::InstCombiner::eraseInstFromFunction(), llvm::Value::getContext(), llvm::InstCombiner::getDataLayout(), llvm::Type::getIntNTy(), llvm::LoadInst::getPointerOperand(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::DataLayout::getTypeStoreSizeInBits(), llvm::Value::hasOneUse(), llvm::Instruction::isAtomic(), llvm::Type::isIntegerTy(), llvm::DataLayout::isLegalInteger(), isMinMaxWithLoads(), llvm::DataLayout::isNonIntegralPointerType(), llvm::Type::isSized(), isSupportedAtomicType(), llvm::Value::isSwiftError(), llvm::LoadInst::isUnordered(), llvm::peekThroughBitcast(), llvm::Value::replaceAllUsesWith(), llvm::IRBuilderBase::SetInsertPoint(), SI, llvm::Value::use_empty(), llvm::Instruction::user_back(), llvm::Value::user_begin(), llvm::Value::user_end(), and llvm::Value::users().

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

◆ combineStoreToNewValue()

static StoreInst* combineStoreToNewValue	(	InstCombiner &	IC,
		StoreInst &	SI,
		Value *	V
	)

static

Combine a store to a new type.

Returns the newly created store instruction.

Definition at line 519 of file InstCombineLoadStoreAlloca.cpp.

Referenced by combineLoadToOperationType(), combineStoreToValueType(), removeBitcastsFromLoadStoreOnMinMax(), and unpackStoreToAggregate().

◆ combineStoreToValueType()

static bool combineStoreToValueType	(	InstCombiner &	IC,
		StoreInst &	SI
	)

static

Combine stores to match the type of value being stored.

The core idea here is that the memory does not have any intrinsic type and where we can we should match the type of a store to the type of value being stored.

However, this routine must never change the width of a store or the number of stores as that would introduce a semantic change. This combine is expected to be a semantic no-op which just allows stores to more closely model the types of their incoming values.

Currently, we also refuse to change the precise type used for an atomic or volatile store. This is debatable, and might be reasonable to change later. However, it is risky in case some backend or other part of LLVM is relying on the exact type stored to select appropriate atomic operations.

Returns: true if the store was successfully combined away. This indicates the caller must erase the store instruction. We have to let the caller erase the store instruction as otherwise there is no way to signal whether it was combined or not: IC.EraseInstFromFunction returns a null pointer.

Definition at line 1176 of file InstCombineLoadStoreAlloca.cpp.

References combineStoreToNewValue(), llvm::StoreInst::getPointerOperand(), llvm::Value::getType(), llvm::StoreInst::getValueOperand(), llvm::Instruction::isAtomic(), isSupportedAtomicType(), llvm::Value::isSwiftError(), llvm::StoreInst::isUnordered(), and likeBitCastFromVector().

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

◆ equivalentAddressValues()

static bool equivalentAddressValues	(	Value *	A,
		Value *	B
	)

static

equivalentAddressValues - Test if A and B will obviously have the same value.

This includes recognizing that t0 and t1 will have the same value in code like this: t0 = getelementptr @a, 0, 3 store i32 0, i32* t0 t1 = getelementptr @a, 0, 3 t2 = load i32* t1

Definition at line 1328 of file InstCombineLoadStoreAlloca.cpp.

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

◆ isDereferenceableForAllocaSize()

static bool isDereferenceableForAllocaSize	(	const Value *	V,
		const AllocaInst *	AI,
		const DataLayout &	DL
	)

static

Returns true if V is dereferenceable for size of alloca.

Definition at line 172 of file InstCombineLoadStoreAlloca.cpp.

References llvm::AllocaInst::getAlignment(), llvm::AllocaInst::getAllocatedType(), llvm::DataLayout::getTypeStoreSize(), llvm::AllocaInst::isArrayAllocation(), and llvm::isDereferenceableAndAlignedPointer().

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

◆ isMinMaxWithLoads()

static bool isMinMaxWithLoads ( Value * V )

static

Returns true if instruction represent minmax pattern like: select ((cmp load V1, load V2), V1, V2).

Definition at line 573 of file InstCombineLoadStoreAlloca.cpp.

References assert(), llvm::Value::getType(), llvm::Type::isPointerTy(), llvm::PatternMatch::m_Cmp(), llvm::PatternMatch::m_Instruction(), llvm::PatternMatch::m_Load(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::peekThroughBitcast().

Referenced by combineLoadToOperationType(), and removeBitcastsFromLoadStoreOnMinMax().

◆ isObjectSizeLessThanOrEq()

static bool isObjectSizeLessThanOrEq	(	Value *	V,
		uint64_t	MaxSize,
		const DataLayout &	DL
	)

static

Definition at line 800 of file InstCombineLoadStoreAlloca.cpp.

References llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::DataLayout::getTypeAllocSize(), llvm::ConstantInt::getValue(), llvm::SmallPtrSetImpl< PtrType >::insert(), P, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), SI, llvm::Value::stripPointerCasts(), and llvm::APInt::zextOrSelf().

Referenced by canReplaceGEPIdxWithZero().

◆ isOnlyCopiedFromConstantGlobal() [1/2]

static bool isOnlyCopiedFromConstantGlobal	(	Value *	V,
		MemTransferInst *&	TheCopy,
		SmallVectorImpl< Instruction *> &	ToDelete
	)

static

isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived) pointer to an alloca.

Ignore any reads of the pointer, return false if we see any stores or other unknown uses. If we see pointer arithmetic, keep track of whether it moves the pointer (with IsOffset) but otherwise traverse the uses. If we see a memcpy/memmove that targets an unoffseted pointer to the alloca, and if the source pointer is a pointer to a constant global, we can optimize this.

Definition at line 60 of file InstCombineLoadStoreAlloca.cpp.

References assert(), llvm::dyn_cast(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase::empty(), GEP, llvm::MemTransferBase< BaseCL >::getSource(), I, llvm::MemIntrinsic::isVolatile(), MI, pointsToConstantGlobal(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by isOnlyCopiedFromConstantGlobal(), and llvm::InstCombiner::visitAllocaInst().

◆ isOnlyCopiedFromConstantGlobal() [2/2]

static MemTransferInst* isOnlyCopiedFromConstantGlobal	(	AllocaInst *	AI,
		SmallVectorImpl< Instruction *> &	ToDelete
	)

static

isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only modified by a copy from a constant global.

If we can prove this, we can replace any uses of the alloca with uses of the global directly.

Definition at line 163 of file InstCombineLoadStoreAlloca.cpp.

References isOnlyCopiedFromConstantGlobal().

◆ isSupportedAtomicType()

static bool isSupportedAtomicType ( Type * Ty )

static

Definition at line 439 of file InstCombineLoadStoreAlloca.cpp.

References llvm::Type::isFloatingPointTy(), and llvm::Type::isIntOrPtrTy().

Referenced by combineLoadToNewType(), combineLoadToOperationType(), combineStoreToNewValue(), and combineStoreToValueType().

◆ likeBitCastFromVector()

static Value* likeBitCastFromVector	(	InstCombiner &	IC,
		Value *	V
	)

static

Look for extractelement/insertvalue sequence that acts like a bitcast.

Returns: underlying value that was "cast", or nullptr otherwise.

For example, if we have:

%E0 = extractelement <2 x double> %U, i32 0
%V0 = insertvalue [2 x double] undef, double %E0, 0
%E1 = extractelement <2 x double> %U, i32 1
%V1 = insertvalue [2 x double] %V0, double %E1, 1

and the layout of a <2 x double> is isomorphic to a [2 x double], then V1 can be safely approximated by a conceptual "bitcast" of U. Note that U may contain non-undef values where V1 has undef.

Definition at line 1115 of file InstCombineLoadStoreAlloca.cpp.

References llvm::dyn_cast(), E, llvm::InstCombiner::getDataLayout(), llvm::Value::getType(), llvm::ARM_MB::ST, and llvm::RISCVFenceField::W.

Referenced by combineStoreToValueType().