LLVM API Documentation

Typedefs | Functions | Variables
ValueTracking.cpp File Reference
#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:

Go to the source code of this file.

Typedefs

typedef SmallPtrSet< const
Value *, 8 > 
ExclInvsSet

Functions

static unsigned getBitWidth (Type *Ty, const DataLayout *TD)
static const InstructionsafeCxtI (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 bool rangeMetadataExcludesValue (MDNode *Ranges, const APInt &Value)
static ValueBuildSubAggregate (Value *From, Value *To, Type *IndexedType, SmallVectorImpl< unsigned > &Idxs, unsigned IdxSkip, Instruction *InsertBefore)
static ValueBuildSubAggregate (Value *From, ArrayRef< unsigned > idx_range, Instruction *InsertBefore)
static uint64_t GetStringLengthH (Value *V, SmallPtrSetImpl< PHINode * > &PHIs)

Variables

const unsigned MaxDepth = 6

Typedef Documentation

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]
static Value* BuildSubAggregate ( Value From,
ArrayRef< unsigned idx_range,
Instruction InsertBefore 
) [static]
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 749 of file ValueTracking.cpp.

References llvm::ARM_PROC::A, llvm::APInt::abs(), llvm::Add, 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::Sub, 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]
static void computeKnownBitsFromAssume ( Value V,
APInt KnownZero,
APInt KnownOne,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]
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]
unsigned ComputeNumSignBits ( Value V,
const DataLayout TD,
unsigned  Depth,
const Query &  Q 
) [static]

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 1698 of file ValueTracking.cpp.

References llvm::Add, 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::Sub, llvm::Trunc, and llvm::APIntOps::Xor().

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

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]
static uint64_t GetStringLengthH ( Value V,
SmallPtrSetImpl< PHINode * > &  PHIs 
) [static]

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 2405 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 365 of file ValueTracking.cpp.

References F().

Referenced by isValidAssumeForContext().

static bool isEphemeralValueOf ( Instruction I,
const Value E 
) [static]
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]
bool isKnownToBeAPowerOfTwo ( Value V,
bool  OrZero,
unsigned  Depth,
const Query &  Q 
) [static]
static bool isValidAssumeForContext ( Value V,
const Query &  Q,
const DataLayout DL 
) [static]
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]
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]
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]
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]
bool MaskedValueIsZero ( Value V,
const APInt Mask,
const DataLayout TD,
unsigned  Depth,
const Query &  Q 
) [static]

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 1680 of file ValueTracking.cpp.

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

static bool rangeMetadataExcludesValue ( MDNode Ranges,
const APInt Value 
) [static]

Does the 'Range' metadata (which must be a valid MD_range operand list) ensure that the value it's attached to is never Value? 'RangeType' is is the type of the value described by the range.

Definition at line 1507 of file ValueTracking.cpp.

References llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), and llvm::ConstantInt::getValue().

Referenced by isKnownNonZero().

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

Variable Documentation