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)
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)
static void ComputeSignBit (Value *V, bool &KnownZero, bool &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
static bool isKnownToBeAPowerOfTwo (Value *V, bool OrZero, unsigned Depth, const Query &Q, const DataLayout &DL)
static bool isKnownNonZero (Value *V, const DataLayout &DL, unsigned Depth, const Query &Q)
static bool MaskedValueIsZero (Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth, const Query &Q)
static unsigned ComputeNumSignBits (Value *V, const DataLayout &DL, 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 &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)
static void computeKnownBitsFromDominatingCondition (Value *V, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q)
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)
static bool isSameUnderlyingObjectInLoop (PHINode *PN, LoopInfo *LI)
 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.
static bool isDereferenceableFromAttribute (const Value *BV, APInt Offset, Type *Ty, const DataLayout &DL)
static bool isDereferenceableFromAttribute (const Value *V, const DataLayout &DL)
static bool isDereferenceablePointer (const Value *V, const DataLayout &DL, SmallPtrSetImpl< const Value * > &Visited)

Variables

const unsigned MaxDepth = 6
static cl::opt< boolEnableDomConditions ("value-tracking-dom-conditions", cl::Hidden, cl::init(false))
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))
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 939 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(), computeKnownBitsFromDominatingCondition(), llvm::computeKnownBitsFromRangeMetadata(), computeKnownBitsMul(), llvm::APInt::countLeadingOnes(), llvm::countTrailingZeros(), llvm::DL, DomConditionsMaxDepth, llvm::dyn_cast(), EnableDomConditions, 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 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 575 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 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 506 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 1517 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 2682 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 393 of file ValueTracking.cpp.

References F().

Referenced by isValidAssumeForContext().

static bool isDereferenceableFromAttribute ( const Value BV,
APInt  Offset,
Type Ty,
const DataLayout DL 
) [static]
static bool isDereferenceableFromAttribute ( const Value V,
const DataLayout DL 
) [static]
static bool isDereferenceablePointer ( const Value V,
const DataLayout DL,
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 1633 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 2743 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]
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 1862 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 1692 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().