LLVM  mainline
Typedefs | Functions | Variables
ValueTracking.cpp File Reference
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/LoopInfo.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/IR/Statepoint.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 &DL)
 Returns the bitwidth of the given scalar or pointer type (if unknown returns 0).
static const InstructionsafeCxtI (const Value *V, const Instruction *CxtI)
static void computeKnownBits (Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
 Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOne bit sets.
static void ComputeSignBit (Value *V, bool &KnownZero, bool &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
 Determine whether the sign bit is known to be zero or one.
static bool isKnownToBeAPowerOfTwo (Value *V, bool OrZero, unsigned Depth, const Query &Q, const DataLayout &DL)
 Return true if the given value is known to have exactly one bit set when defined.
static bool isKnownNonZero (Value *V, const DataLayout &DL, unsigned Depth, const Query &Q)
 Return true if the given value is known to be non-zero when defined.
static bool MaskedValueIsZero (Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth, const Query &Q)
 Return true if 'V & Mask' is known to be zero.
static unsigned ComputeNumSignBits (Value *V, const DataLayout &DL, unsigned Depth, const Query &Q)
 Return the number of times the sign bit of the register is replicated into the other bits.
static void computeKnownBitsAddSub (bool Add, Value *Op0, Value *Op1, bool NSW, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2, APInt &KnownOne2, const DataLayout &DL, unsigned Depth, const Query &Q)
static void computeKnownBitsMul (Value *Op0, Value *Op1, bool NSW, APInt &KnownZero, APInt &KnownOne, APInt &KnownZero2, APInt &KnownOne2, const DataLayout &DL, 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)
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 computeKnownBitsFromTrueCondition (Value *V, ICmpInst *Cmp, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
 Compute known bits in 'V' under the assumption that the condition 'Cmp' is true (at the context instruction.) This is mostly a utility function for the prototype dominating conditions reasoning below.
static void computeKnownBitsFromDominatingCondition (Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
 Compute known bits in 'V' from conditions which are known to be true along all paths leading to the context instruction.
static void computeKnownBitsFromAssume (Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
static void computeKnownBitsFromOperator (Operator *I, 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)
 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.
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)
 If we can compute the length of the string pointed to by the specified pointer, return 'len+1'.
static bool isSameUnderlyingObjectInLoop (PHINode *PN, LoopInfo *LI)
 PN defines a loop-variant pointer to an object.
static bool isDereferenceableFromAttribute (const Value *BV, APInt Offset, Type *Ty, const DataLayout &DL, const Instruction *CtxI, const DominatorTree *DT, const TargetLibraryInfo *TLI)
static bool isDereferenceableFromAttribute (const Value *V, const DataLayout &DL, const Instruction *CtxI, const DominatorTree *DT, const TargetLibraryInfo *TLI)
static bool isDereferenceablePointer (const Value *V, const DataLayout &DL, const Instruction *CtxI, const DominatorTree *DT, const TargetLibraryInfo *TLI, SmallPtrSetImpl< const Value * > &Visited)
 Return true if Value is always a dereferenceable pointer.
static bool isKnownNonNullFromDominatingCondition (const Value *V, const Instruction *CtxI, const DominatorTree *DT)
static SelectPatternFlavor matchSelectPattern (ICmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS)
static ConstantlookThroughCast (ICmpInst *CmpI, Value *V1, Value *V2, Instruction::CastOps *CastOp)

Variables

const unsigned MaxDepth = 6
static cl::opt< boolEnableDomConditions ("value-tracking-dom-conditions", cl::Hidden, cl::init(false))
 Enable an experimental feature to leverage information about dominating conditions to compute known bits.
static cl::opt< unsignedDomConditionsMaxDepth ("dom-conditions-max-depth", cl::Hidden, cl::init(1))
static cl::opt< unsignedDomConditionsMaxDomBlocks ("dom-conditions-dom-blocks", cl::Hidden, cl::init(20000))
 How many dominating blocks should be scanned looking for dominating conditions?
static cl::opt< unsignedDomConditionsMaxUses ("dom-conditions-max-uses", cl::Hidden, cl::init(2000))
static cl::opt< boolDomConditionsSingleCmpUse ("dom-conditions-single-cmp-use", cl::Hidden, cl::init(false))

Typedef Documentation

Definition at line 89 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 DL,
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, 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 1412 of file ValueTracking.cpp.

References llvm::ARM_PROC::A, Align(), llvm::APInt::clearAllBits(), llvm::computeKnownBits(), computeKnownBitsFromAssume(), computeKnownBitsFromDominatingCondition(), computeKnownBitsFromOperator(), llvm::countTrailingZeros(), llvm::DL, DomConditionsMaxDepth, EnableDomConditions, llvm::DataLayout::getABITypeAlignment(), llvm::APInt::getAllOnesValue(), llvm::APInt::getBitWidth(), llvm::APInt::getLowBitsSet(), llvm::DataLayout::getPreferredAlignment(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::DataLayout::getTypeSizeInBits(), I, llvm::Type::isIntOrIntVectorTy(), llvm::Type::isPointerTy(), llvm::Type::isSized(), MaxDepth, and llvm::APInt::setAllBits().

static void computeKnownBitsAddSub ( bool  Add,
Value Op0,
Value Op1,
bool  NSW,
APInt KnownZero,
APInt KnownOne,
APInt KnownZero2,
APInt KnownOne2,
const DataLayout DL,
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 computeKnownBitsFromDominatingCondition ( Value V,
APInt KnownZero,
APInt KnownOne,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]

Compute known bits in 'V' from conditions which are known to be true along all paths leading to the context instruction.

In particular, look for cases where one branch of an interesting condition dominates the context instruction. This does not do general dataflow. NOTE: This code is EXPERIMENTAL and currently off by default.

Definition at line 595 of file ValueTracking.cpp.

References computeKnownBitsFromTrueCondition(), DomConditionsMaxDomBlocks, DomConditionsMaxUses, DomConditionsSingleCmpUse, llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUse(), llvm::BranchInst::isUnconditional(), llvm::Value::users(), and VI.

Referenced by computeKnownBits().

static void computeKnownBitsFromOperator ( Operator I,
APInt KnownZero,
APInt KnownOne,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]

Definition at line 944 of file ValueTracking.cpp.

References llvm::APInt::abs(), llvm::AddrSpaceCast, Align(), llvm::Alloca, llvm::APIntOps::And(), llvm::Call, llvm::computeKnownBits(), computeKnownBitsAddSub(), llvm::computeKnownBitsFromRangeMetadata(), computeKnownBitsMul(), llvm::APInt::countLeadingOnes(), llvm::countTrailingZeros(), llvm::DL, llvm::dyn_cast(), llvm::ExtractValue, llvm::FPExt, llvm::FPToSI, llvm::gep_type_begin(), 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::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Constant::getSplatValue(), getTrue(), llvm::AllocaInst::getType(), llvm::Value::getType(), llvm::PHINode::hasConstantValue(), I, llvm::PHINode::incoming_values(), llvm::IntToPtr, llvm::Type::isIntegerTy(), 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, fuzzer::min(), llvm::APIntOps::Or(), P, llvm::TargetOpcode::PHI, llvm::MCID::Select, llvm::APInt::setBit(), llvm::SExt, llvm::SIToFP, llvm::Trunc, llvm::APInt::trunc(), llvm::APIntOps::Xor(), llvm::APInt::zext(), and llvm::APInt::zextOrTrunc().

Referenced by computeKnownBits().

static void computeKnownBitsFromTrueCondition ( Value V,
ICmpInst Cmp,
APInt KnownZero,
APInt KnownOne,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]

Compute known bits in 'V' under the assumption that the condition 'Cmp' is true (at the context instruction.) This is mostly a utility function for the prototype dominating conditions reasoning below.

Definition at line 521 of file ValueTracking.cpp.

References llvm::computeKnownBits(), llvm::APInt::getBitWidth(), llvm::APInt::getHighBitsSet(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::APInt::getSignBit(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, llvm::APInt::isAllOnesValue(), llvm::isKnownToBeAPowerOfTwo(), and llvm_unreachable.

Referenced by computeKnownBitsFromDominatingCondition().

static void computeKnownBitsMul ( Value Op0,
Value Op1,
bool  NSW,
APInt KnownZero,
APInt KnownOne,
APInt KnownZero2,
APInt KnownOne2,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]
unsigned ComputeNumSignBits ( Value V,
const DataLayout DL,
unsigned  Depth,
const Query &  Q 
) [static]
void ComputeSignBit ( Value V,
bool KnownZero,
bool KnownOne,
const DataLayout DL,
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 1546 of file ValueTracking.cpp.

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

static unsigned getBitWidth ( Type Ty,
const DataLayout DL 
) [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 2711 of file ValueTracking.cpp.

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

Referenced by llvm::GetStringLength().

static bool isAssumeLikeIntrinsic ( const Instruction I) [static]

Definition at line 408 of file ValueTracking.cpp.

References F().

Referenced by isValidAssumeForContext().

static bool isDereferenceableFromAttribute ( const Value BV,
APInt  Offset,
Type Ty,
const DataLayout DL,
const Instruction CtxI,
const DominatorTree DT,
const TargetLibraryInfo TLI 
) [static]
static bool isDereferenceablePointer ( const Value V,
const DataLayout DL,
const Instruction CtxI,
const DominatorTree DT,
const TargetLibraryInfo TLI,
SmallPtrSetImpl< const Value * > &  Visited 
) [static]
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 1662 of file ValueTracking.cpp.

References llvm::DL, 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 DL,
unsigned  Depth,
const Query &  Q 
) [static]
bool isKnownToBeAPowerOfTwo ( Value V,
bool  OrZero,
unsigned  Depth,
const Query &  Q,
const DataLayout DL 
) [static]
static bool isSameUnderlyingObjectInLoop ( PHINode PN,
LoopInfo LI 
) [static]

PN defines a loop-variant pointer to an object.

Check if the previous iteration of the loop was referring to the same object as PN.

Definition at line 2772 of file ValueTracking.cpp.

References llvm::dyn_cast(), llvm::PHINode::getIncomingValue(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::Loop::isLoopInvariant(), and llvm::SPII::Load.

Referenced by llvm::GetUnderlyingObjects().

static bool isValidAssumeForContext ( Value V,
const Query &  Q 
) [static]
static Constant* lookThroughCast ( ICmpInst CmpI,
Value V1,
Value V2,
Instruction::CastOps CastOp 
) [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 DL,
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, 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 1891 of file ValueTracking.cpp.

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

static SelectPatternFlavor matchSelectPattern ( ICmpInst::Predicate  Pred,
Value CmpLHS,
Value CmpRHS,
Value TrueVal,
Value FalseVal,
Value *&  LHS,
Value *&  RHS 
) [static]
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 1721 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

cl::opt<unsigned> DomConditionsMaxDepth("dom-conditions-max-depth", cl::Hidden, cl::init(1)) [static]

Referenced by computeKnownBits().

cl::opt<unsigned> DomConditionsMaxDomBlocks("dom-conditions-dom-blocks", cl::Hidden, cl::init(20000)) [static]

How many dominating blocks should be scanned looking for dominating conditions?

Referenced by computeKnownBitsFromDominatingCondition().

cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses", cl::Hidden, cl::init(2000)) [static]
cl::opt<bool> DomConditionsSingleCmpUse("dom-conditions-single-cmp-use", cl::Hidden, cl::init(false)) [static]
cl::opt<bool> EnableDomConditions("value-tracking-dom-conditions", cl::Hidden, cl::init(false)) [static]

Enable an experimental feature to leverage information about dominating conditions to compute known bits.

The individual options below control how hard we search. The defaults are choosen to be fairly aggressive. If you run into compile time problems when testing, scale them back and report your findings.

Referenced by computeKnownBits().