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/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 &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)

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 87 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 938 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(), 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::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 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 573 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 504 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 1516 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 2681 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 391 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 1632 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 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 1861 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 1691 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().