#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/AssumptionTracker.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include <cstring>

Include dependency graph for ValueTracking.cpp:

Typedefs
typedef SmallPtrSet< const Value *, 8 >	ExclInvsSet
Functions
static unsigned	getBitWidth (Type Ty, const DataLayout TD)
static const Instruction *	safeCxtI (const Value V, const Instruction CxtI)
static void	computeKnownBits (Value V, APInt &KnownZero, APInt &KnownOne, const DataLayout TD, unsigned Depth, const Query &Q)
static void	ComputeSignBit (Value V, bool &KnownZero, bool &KnownOne, const DataLayout TD, unsigned Depth, const Query &Q)
static bool	isKnownToBeAPowerOfTwo (Value *V, bool OrZero, unsigned Depth, const Query &Q)
static bool	isKnownNonZero (Value V, const DataLayout TD, unsigned Depth, const Query &Q)
static bool	MaskedValueIsZero (Value V, const APInt &Mask, const DataLayout TD, unsigned Depth, const Query &Q)
static unsigned	ComputeNumSignBits (Value V, const DataLayout TD, unsigned Depth, const Query &Q)
static void	computeKnownBitsAddSub (bool Add, Value Op0, Value Op1, bool NSW, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2, APInt &KnownOne2, const DataLayout *TD, unsigned Depth, const Query &Q)
static void	computeKnownBitsMul (Value Op0, Value Op1, bool NSW, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2, APInt &KnownOne2, const DataLayout *TD, unsigned Depth, const Query &Q)
static bool	isEphemeralValueOf (Instruction I, const Value E)
static bool	isAssumeLikeIntrinsic (const Instruction *I)
static bool	isValidAssumeForContext (Value V, const Query &Q, const DataLayout DL)
template<typename LHS , typename RHS >
match_combine_or < CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > , CmpClass_match< RHS, LHS, ICmpInst, ICmpInst::Predicate > >	m_c_ICmp (ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
template<typename LHS , typename RHS >
match_combine_or < BinaryOp_match< LHS, RHS, Instruction::And > , BinaryOp_match< RHS, LHS, Instruction::And > >	m_c_And (const LHS &L, const RHS &R)
template<typename LHS , typename RHS >
match_combine_or < BinaryOp_match< LHS, RHS, Instruction::Or > , BinaryOp_match< RHS, LHS, Instruction::Or > >	m_c_Or (const LHS &L, const RHS &R)
template<typename LHS , typename RHS >
match_combine_or < BinaryOp_match< LHS, RHS, Instruction::Xor > , BinaryOp_match< RHS, LHS, Instruction::Xor > >	m_c_Xor (const LHS &L, const RHS &R)
static void	computeKnownBitsFromAssume (Value V, APInt &KnownZero, APInt &KnownOne, const DataLayout DL, unsigned Depth, const Query &Q)
static bool	isGEPKnownNonNull (GEPOperator GEP, const DataLayout DL, unsigned Depth, const Query &Q)
	Test whether a GEP's result is known to be non-null.
static Value *	BuildSubAggregate (Value From, Value To, Type IndexedType, SmallVectorImpl< unsigned > &Idxs, unsigned IdxSkip, Instruction InsertBefore)
static Value *	BuildSubAggregate (Value From, ArrayRef< unsigned > idx_range, Instruction InsertBefore)
static uint64_t	GetStringLengthH (Value V, SmallPtrSetImpl< PHINode > &PHIs)
Variables
const unsigned	MaxDepth = 6

Typedef Documentation

typedef SmallPtrSet<const Value *, 8> ExclInvsSet

Definition at line 59 of file ValueTracking.cpp.

Function Documentation

static Value* BuildSubAggregate	(	Value *	From,
		Value *	To,
		Type *	IndexedType,
		SmallVectorImpl< unsigned > &	Idxs,
		unsigned	IdxSkip,
		Instruction *	InsertBefore
	)		`[static]`

Definition at line 2087 of file ValueTracking.cpp.

References llvm::InsertValueInst::Create(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::FindInsertedValue(), llvm::InsertValueInst::getAggregateOperand(), llvm::StructType::getElementType(), llvm::StructType::getNumElements(), llvm::makeArrayRef(), llvm::SmallVectorTemplateBase< T, isPodLike >::pop_back(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

Referenced by BuildSubAggregate(), and llvm::FindInsertedValue().

static Value* BuildSubAggregate	(	Value *	From,
		ArrayRef< unsigned >	idx_range,
		Instruction *	InsertBefore
	)		`[static]`

Definition at line 2146 of file ValueTracking.cpp.

References llvm::ArrayRef< T >::begin(), BuildSubAggregate(), llvm::ArrayRef< T >::end(), llvm::UndefValue::get(), llvm::ExtractValueInst::getIndexedType(), llvm::Value::getType(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

void computeKnownBits	(	Value *	V,
		APInt &	KnownZero,
		APInt &	KnownOne,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOne bit sets.

NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that we cannot optimize based on the assumption that it is zero without changing it to be an explicit zero. If we don't change it to zero, other code could optimized based on the contradictory assumption that it is non-zero. Because instcombine aggressively folds operations with undef args anyway, this won't lose us code quality.

This function is defined on values with integer type, values with pointer type (but only if TD is non-null), and vectors of integers. In the case where V is a vector, known zero, and known one values are the same width as the vector element, and the bit is set only if it is true for all of the elements in the vector.

Definition at line 746 of file ValueTracking.cpp.

References llvm::ARM_PROC::A, llvm::APInt::abs(), llvm::AddrSpaceCast, Align(), llvm::Alloca, llvm::APIntOps::And(), llvm::Call, llvm::APInt::clearAllBits(), llvm::computeKnownBits(), computeKnownBitsAddSub(), computeKnownBitsFromAssume(), llvm::computeKnownBitsFromRangeMetadata(), computeKnownBitsMul(), llvm::APInt::countLeadingOnes(), llvm::countTrailingZeros(), llvm::dyn_cast(), llvm::ExtractValue, llvm::FPExt, llvm::FPToSI, llvm::gep_type_begin(), llvm::DataLayout::getABITypeAlignment(), llvm::AllocaInst::getAlignment(), llvm::APInt::getAllOnesValue(), llvm::APInt::getBitWidth(), llvm::StructLayout::getElementOffset(), llvm::SequentialType::getElementType(), llvm::APInt::getHighBitsSet(), llvm::PHINode::getIncomingValue(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::ExtractValueInst::getIndices(), llvm::APInt::getLowBitsSet(), llvm::PHINode::getNumIncomingValues(), llvm::ExtractValueInst::getNumIndices(), llvm::User::getNumOperands(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::DataLayout::getPreferredAlignment(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Constant::getSplatValue(), getTrue(), llvm::AllocaInst::getType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::PHINode::hasConstantValue(), I, llvm::IntToPtr, llvm::Type::isIntegerTy(), llvm::Type::isIntOrIntVectorTy(), llvm::APInt::isNonNegative(), llvm::Type::isPointerTy(), llvm::APInt::isPowerOf2(), llvm::Type::isSized(), llvm::Type::isVectorTy(), llvm::Constant::isZeroValue(), llvm::SPII::Load, llvm::Log2_32(), llvm::LShr, llvm::APIntOps::lshr(), MaxDepth, llvm::LLVMContext::MD_range, llvm::APIntOps::Or(), P, llvm::TargetOpcode::PHI, llvm::MCID::Select, llvm::APInt::setAllBits(), llvm::APInt::setBit(), llvm::SExt, llvm::SIToFP, llvm::Trunc, llvm::APInt::trunc(), llvm::APIntOps::Xor(), llvm::APInt::zext(), and llvm::APInt::zextOrTrunc().

static void computeKnownBitsAddSub	(	bool	Add,
		Value *	Op0,
		Value *	Op1,
		bool	NSW,
		APInt &	KnownZero,
		APInt &	KnownOne,
		APInt &	KnownZero2,
		APInt &	KnownOne2,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

Definition at line 165 of file ValueTracking.cpp.

References llvm::computeKnownBits(), llvm::countLeadingZeros(), llvm::APInt::getBitWidth(), llvm::APInt::getHighBitsSet(), llvm::APInt::getSignBit(), llvm::APInt::isNegative(), llvm::APInt::setBit(), and std::swap().

Referenced by computeKnownBits().

static void computeKnownBitsFromAssume	(	Value *	V,
		APInt &	KnownZero,
		APInt &	KnownOne,
		const DataLayout *	DL,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

Definition at line 477 of file ValueTracking.cpp.

References llvm::ARM_PROC::A, llvm::CallingConv::C, llvm::APInt::clearAllBits(), llvm::computeKnownBits(), F(), llvm::APInt::getBitWidth(), llvm::APInt::getHighBitsSet(), llvm::APInt::getSignBit(), llvm::ConstantInt::getZExtValue(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::APInt::isAllOnesValue(), llvm::isKnownToBeAPowerOfTwo(), llvm::APInt::isNegative(), llvm::isValidAssumeForContext(), llvm::APInt::lshr(), llvm::PatternMatch::m_AShr(), llvm::PatternMatch::m_BitCast(), m_c_And(), m_c_ICmp(), m_c_Or(), m_c_Xor(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_LShr(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_PtrToInt(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::APInt::setAllBits().

Referenced by computeKnownBits().

static void computeKnownBitsMul	(	Value *	Op0,
		Value *	Op1,
		bool	NSW,
		APInt &	KnownZero,
		APInt &	KnownOne,
		APInt &	KnownZero2,
		APInt &	KnownOne2,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

Definition at line 245 of file ValueTracking.cpp.

References llvm::APInt::clearAllBits(), llvm::computeKnownBits(), llvm::APInt::countLeadingOnes(), llvm::APInt::countTrailingOnes(), llvm::APInt::getBitWidth(), llvm::APInt::getHighBitsSet(), llvm::APInt::getLowBitsSet(), llvm::isKnownNonZero(), llvm::APInt::isNegative(), and llvm::APInt::setBit().

Referenced by computeKnownBits().

unsigned ComputeNumSignBits	(	Value *	V,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

ComputeNumSignBits - Return the number of times the sign bit of the register is replicated into the other bits. We know that at least 1 bit is always equal to the sign bit (itself), but other cases can give us information. For example, immediately after an "ashr X, 2", we know that the top 3 bits are all equal to each other, so we return 3.

'Op' must have a scalar integer type.

Definition at line 1667 of file ValueTracking.cpp.

References llvm::APIntOps::And(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::APInt::countLeadingZeros(), llvm::dyn_cast(), llvm::APInt::getBitWidth(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), llvm::APInt::getZExtValue(), llvm::Type::isIntOrIntVectorTy(), llvm::APInt::isNegative(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), llvm::APIntOps::Or(), llvm::TargetOpcode::PHI, llvm::MCID::Select, llvm::SExt, llvm::Trunc, and llvm::APIntOps::Xor().

void ComputeSignBit	(	Value *	V,
		bool &	KnownZero,
		bool &	KnownOne,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

ComputeSignBit - Determine whether the sign bit is known to be zero or one. Convenience wrapper around computeKnownBits.

Definition at line 1326 of file ValueTracking.cpp.

References llvm::computeKnownBits(), getBitWidth(), and llvm::Value::getType().

static unsigned getBitWidth	(	Type *	Ty,
		const DataLayout *	TD
	)		`[static]`

getBitWidth - Returns the bitwidth of the given scalar or pointer type (if unknown returns 0). For vector types, returns the element type's bitwidth.

Definition at line 44 of file ValueTracking.cpp.

References llvm::DataLayout::getPointerTypeSizeInBits(), and llvm::Type::getScalarSizeInBits().

Referenced by canFoldZeroCheckIntoBranch(), ComputeSignBit(), llvm::ConstantFoldCastInstruction(), DecodeFixedType(), dyn_castZExtVal(), ExtractConstantBytes(), llvm::ExecutionEngine::getConstantValue(), llvm::EVT::getEVT(), llvm::Type::getIntegerBitWidth(), getNoopInput(), llvm::Type::getPrimitiveSizeInBits(), llvm::NVPTXTargetLowering::getPrototype(), getTypePrefix(), llvm::MVT::getVT(), llvm::Type::isIntegerTy(), isKnownNonZero(), llvm::isSafeToSpeculativelyExecute(), LLVMCreateGenericValueOfInt(), LLVMGetIntTypeWidth(), llvm::ExecutionEngine::LoadValueFromMemory(), llvm::TypePrinting::print(), llvm::MCJIT::runFunction(), llvm::InstCombiner::visitCallInst(), llvm::InstCombiner::visitICmpInst(), llvm::InstCombiner::visitICmpInstWithInstAndIntCst(), llvm::WriteMDNodeComment(), and WriteTypeTable().

static uint64_t GetStringLengthH	(	Value *	V,
		SmallPtrSetImpl< PHINode * > &	PHIs
	)		`[static]`

GetStringLengthH - If we can compute the length of the string pointed to by the specified pointer, return 'len+1'. If we can't, return 0.

Definition at line 2375 of file ValueTracking.cpp.

References llvm::getConstantStringInfo(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::StringRef::size(), and llvm::Value::stripPointerCasts().

Referenced by llvm::GetStringLength().

static bool isAssumeLikeIntrinsic ( const Instruction * I ) [static]

Definition at line 363 of file ValueTracking.cpp.

References F().

Referenced by isValidAssumeForContext().

static bool isEphemeralValueOf	(	Instruction *	I,
		const Value *	E
	)		`[static]`

Definition at line 327 of file ValueTracking.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isSafeToSpeculativelyExecute(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::Value::users().

Referenced by isValidAssumeForContext().

static bool isGEPKnownNonNull	(	GEPOperator *	GEP,
		const DataLayout *	DL,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

Test whether a GEP's result is known to be non-null.

Uses properties inherent in a GEP to try to determine whether it is known to be non-null.

Currently this routine does not support vector GEPs.

Definition at line 1444 of file ValueTracking.cpp.

References llvm::gep_type_begin(), llvm::gep_type_end(), llvm::StructLayout::getElementOffset(), llvm::GEPOperator::getPointerAddressSpace(), llvm::GEPOperator::getPointerOperand(), llvm::DataLayout::getStructLayout(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::ConstantInt::getZExtValue(), llvm::GEPOperator::isInBounds(), llvm::isKnownNonZero(), llvm::Type::isPointerTy(), and MaxDepth.

Referenced by isKnownNonZero().

bool isKnownNonZero	(	Value *	V,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

isKnownNonZero - Return true if the given value is known to be non-zero when defined. For vectors return true if every element is known to be non-zero when defined. Supports values with integer or pointer type and vectors of integers.

Definition at line 1508 of file ValueTracking.cpp.

bool isKnownToBeAPowerOfTwo	(	Value *	V,
		bool	OrZero,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

isKnownToBeAPowerOfTwo - Return true if the given value is known to have exactly one bit set when defined. For vectors return true if every element is known to be a power of two when defined. Supports values with integer or pointer types and vectors of integers.

Definition at line 1346 of file ValueTracking.cpp.

static bool isValidAssumeForContext	(	Value *	V,
		const Query &	Q,
		const DataLayout *	DL
	)		`[static]`

Definition at line 385 of file ValueTracking.cpp.

References llvm::BasicBlock::end(), llvm::Instruction::getParent(), I, llvm::ARM_PROC::IE, isAssumeLikeIntrinsic(), isEphemeralValueOf(), and llvm::isSafeToSpeculativelyExecute().

template<typename LHS , typename RHS >

match_combine_or<BinaryOp_match<LHS, RHS, Instruction::And>, BinaryOp_match<RHS, LHS, Instruction::And> > m_c_And	(	const LHS &	L,
		const RHS &	R
	)		`[inline]`

Definition at line 459 of file ValueTracking.cpp.

References llvm::PatternMatch::m_And(), and llvm::PatternMatch::m_CombineOr().

Referenced by computeKnownBitsFromAssume().

template<typename LHS , typename RHS >

match_combine_or<CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>, CmpClass_match<RHS, LHS, ICmpInst, ICmpInst::Predicate> > m_c_ICmp	(	ICmpInst::Predicate &	Pred,
		const LHS &	L,
		const RHS &	R
	)		`[inline]`

Definition at line 452 of file ValueTracking.cpp.

References llvm::PatternMatch::m_CombineOr(), and llvm::PatternMatch::m_ICmp().

Referenced by computeKnownBitsFromAssume().

template<typename LHS , typename RHS >

match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Or>, BinaryOp_match<RHS, LHS, Instruction::Or> > m_c_Or	(	const LHS &	L,
		const RHS &	R
	)		`[inline]`

Definition at line 466 of file ValueTracking.cpp.

References llvm::PatternMatch::m_CombineOr(), and llvm::PatternMatch::m_Or().

Referenced by computeKnownBitsFromAssume().

template<typename LHS , typename RHS >

match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>, BinaryOp_match<RHS, LHS, Instruction::Xor> > m_c_Xor	(	const LHS &	L,
		const RHS &	R
	)		`[inline]`

Definition at line 473 of file ValueTracking.cpp.

References llvm::PatternMatch::m_CombineOr(), and llvm::PatternMatch::m_Xor().

Referenced by computeKnownBitsFromAssume().

bool MaskedValueIsZero	(	Value *	V,
		const APInt &	Mask,
		const DataLayout *	TD,
		unsigned	Depth,
		const Query &	Q
	)		`[static]`

MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use this predicate to simplify operations downstream. Mask is known to be zero for bits that V cannot have.

This function is defined on values with integer type, values with pointer type (but only if TD is non-null), and vectors of integers. In the case where V is a vector, the mask, known zero, and known one values are the same width as the vector element, and the bit is set only if it is true for all of the elements in the vector.

Definition at line 1649 of file ValueTracking.cpp.

References llvm::computeKnownBits(), and llvm::APInt::getBitWidth().

static const Instruction* safeCxtI	(	const Value *	V,
		const Instruction *	CxtI
	)		`[static]`

Definition at line 85 of file ValueTracking.cpp.

References llvm::dyn_cast(), and llvm::Instruction::getParent().

Referenced by llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::ComputeSignBit(), llvm::isKnownNonZero(), llvm::isKnownToBeAPowerOfTwo(), and llvm::MaskedValueIsZero().

Variable Documentation

const unsigned MaxDepth = 6

Definition at line 40 of file ValueTracking.cpp.

Referenced by llvm::SUnit::biasCriticalPath(), computeKnownBits(), llvm::ComputeMultiple(), isGEPKnownNonNull(), isKnownNonZero(), isKnownToBeAPowerOfTwo(), and visitUDivOperand().

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation