LLVM  6.0.0svn
Functions | Variables
ValueTracking.cpp File Reference
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

Go to the source code of this file.

Functions

static unsigned getBitWidth (Type *Ty, const DataLayout &DL)
 Returns the bitwidth of the given scalar or pointer type. More...
 
static const InstructionsafeCxtI (const Value *V, const Instruction *CxtI)
 
static void computeKnownBits (const Value *V, KnownBits &Known, unsigned Depth, const Query &Q)
 Determine which bits of V are known to be either zero or one and return them in the Known bit set. More...
 
static KnownBits computeKnownBits (const Value *V, unsigned Depth, const Query &Q)
 Determine which bits of V are known to be either zero or one and return them. More...
 
static bool isKnownToBeAPowerOfTwo (const Value *V, bool OrZero, unsigned Depth, const Query &Q)
 Return true if the given value is known to have exactly one bit set when defined. More...
 
static bool isKnownNonZero (const Value *V, unsigned Depth, const Query &Q)
 Return true if the given value is known to be non-zero when defined. More...
 
static bool isKnownNonEqual (const Value *V1, const Value *V2, const Query &Q)
 Return true if it is known that V1 != V2. More...
 
static bool MaskedValueIsZero (const Value *V, const APInt &Mask, unsigned Depth, const Query &Q)
 Return true if 'V & Mask' is known to be zero. More...
 
static unsigned ComputeNumSignBits (const Value *V, unsigned Depth, const Query &Q)
 
static void computeKnownBitsAddSub (bool Add, const Value *Op0, const Value *Op1, bool NSW, KnownBits &KnownOut, KnownBits &Known2, unsigned Depth, const Query &Q)
 
static void computeKnownBitsMul (const Value *Op0, const Value *Op1, bool NSW, KnownBits &Known, KnownBits &Known2, unsigned Depth, const Query &Q)
 
static bool isEphemeralValueOf (const Instruction *I, const Value *E)
 
static bool isAssumeLikeIntrinsic (const Instruction *I)
 
static void computeKnownBitsFromAssume (const Value *V, KnownBits &Known, unsigned Depth, const Query &Q)
 
static void computeKnownBitsFromShiftOperator (const Operator *I, KnownBits &Known, KnownBits &Known2, unsigned Depth, const Query &Q, function_ref< APInt(const APInt &, unsigned)> KZF, function_ref< APInt(const APInt &, unsigned)> KOF)
 Compute known bits from a shift operator, including those with a non-constant shift amount. More...
 
static void computeKnownBitsFromOperator (const Operator *I, KnownBits &Known, unsigned Depth, const Query &Q)
 
static bool isGEPKnownNonNull (const GEPOperator *GEP, unsigned Depth, const Query &Q)
 Test whether a GEP's result is known to be non-null. More...
 
static bool isKnownNonNullFromDominatingCondition (const Value *V, const Instruction *CtxI, const DominatorTree *DT)
 
static bool rangeMetadataExcludesValue (const 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. More...
 
static bool isAddOfNonZero (const Value *V1, const Value *V2, const Query &Q)
 Return true if V2 == V1 + X, where X is known non-zero. More...
 
static unsigned computeNumSignBitsVectorConstant (const Value *V, unsigned TyBits)
 For vector constants, loop over the elements and find the constant with the minimum number of sign bits. More...
 
static unsigned ComputeNumSignBitsImpl (const Value *V, unsigned Depth, const Query &Q)
 Return the number of times the sign bit of the register is replicated into the other bits. More...
 
static bool cannotBeOrderedLessThanZeroImpl (const Value *V, const TargetLibraryInfo *TLI, bool SignBitOnly, unsigned Depth)
 If SignBitOnly is true, test for a known 0 sign bit rather than a standard ordered compare. More...
 
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 (const Value *V, SmallPtrSetImpl< const PHINode *> &PHIs, unsigned CharSize)
 If we can compute the length of the string pointed to by the specified pointer, return 'len+1'. More...
 
static bool isSameUnderlyingObjectInLoop (const PHINode *PN, const LoopInfo *LI)
 PN defines a loop-variant pointer to an object. More...
 
static const ValuegetUnderlyingObjectFromInt (const Value *V)
 This is the function that does the work of looking through basic ptrtoint+arithmetic+inttoptr sequences. More...
 
static bool checkRippleForSignedAdd (const KnownBits &LHSKnown, const KnownBits &RHSKnown)
 Return true if we can prove that adding the two values of the knownbits will not overflow. More...
 
static OverflowResult computeOverflowForSignedAdd (const Value *LHS, const Value *RHS, const AddOperator *Add, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
 
static bool isKnownNonNaN (const Value *V, FastMathFlags FMF)
 
static bool isKnownNonZero (const Value *V)
 
static SelectPatternResult matchFastFloatClamp (CmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS)
 Match clamp pattern for float types without care about NaNs or signed zeros. More...
 
static SelectPatternResult matchMinMax (CmpInst::Predicate Pred, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS)
 Match non-obvious integer minimum and maximum sequences. More...
 
static SelectPatternResult matchSelectPattern (CmpInst::Predicate Pred, FastMathFlags FMF, Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS)
 
static ValuelookThroughCast (CmpInst *CmpI, Value *V1, Value *V2, Instruction::CastOps *CastOp)
 Helps to match a select pattern in case of a type mismatch. More...
 
static bool isTruePredicate (CmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const DataLayout &DL, unsigned Depth)
 Return true if "icmp Pred LHS RHS" is always true. More...
 
static Optional< boolisImpliedCondOperands (CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS, const DataLayout &DL, unsigned Depth)
 Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred ALHS ARHS" is true. More...
 
static bool isMatchingOps (const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS, bool &IsSwappedOps)
 Return true if the operands of the two compares match. More...
 
static Optional< boolisImpliedCondMatchingOperands (CmpInst::Predicate APred, const Value *ALHS, const Value *ARHS, CmpInst::Predicate BPred, const Value *BLHS, const Value *BRHS, bool IsSwappedOps)
 Return true if "icmp1 APred ALHS ARHS" implies "icmp2 BPred BLHS BRHS" is true. More...
 
static Optional< boolisImpliedCondMatchingImmOperands (CmpInst::Predicate APred, const Value *ALHS, const ConstantInt *C1, CmpInst::Predicate BPred, const Value *BLHS, const ConstantInt *C2)
 Return true if "icmp1 APred ALHS C1" implies "icmp2 BPred BLHS C2" is true. More...
 
static Optional< boolisImpliedCondICmps (const ICmpInst *LHS, const ICmpInst *RHS, const DataLayout &DL, bool LHSIsTrue, unsigned Depth)
 Return true if LHS implies RHS is true. More...
 
static Optional< boolisImpliedCondAndOr (const BinaryOperator *LHS, const ICmpInst *RHS, const DataLayout &DL, bool LHSIsTrue, unsigned Depth)
 Return true if LHS implies RHS is true. More...
 

Variables

const unsigned MaxDepth = 6
 
static cl::opt< unsignedDomConditionsMaxUses ("dom-conditions-max-uses", cl::Hidden, cl::init(20))
 

Function Documentation

◆ BuildSubAggregate() [1/2]

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

◆ BuildSubAggregate() [2/2]

static Value* BuildSubAggregate ( Value From,
ArrayRef< unsigned idx_range,
Instruction InsertBefore 
)
static

◆ cannotBeOrderedLessThanZeroImpl()

static bool cannotBeOrderedLessThanZeroImpl ( const Value V,
const TargetLibraryInfo TLI,
bool  SignBitOnly,
unsigned  Depth 
)
static

If SignBitOnly is true, test for a known 0 sign bit rather than a standard ordered compare.

e.g. make -0.0 olt 0.0 be true because of the sign bit despite comparing equal.

Definition at line 2647 of file ValueTracking.cpp.

References llvm::MCID::Call, llvm::CannotBeNegativeZero(), llvm::dyn_cast(), llvm::Exponent, llvm::getIntrinsicForCallSite(), llvm::Operator::getOpcode(), llvm::User::getOperand(), I, LLVM_FALLTHROUGH, llvm::maxnum(), llvm::minnum(), and llvm::MCID::Select.

Referenced by llvm::CannotBeOrderedLessThanZero(), and llvm::SignBitMustBeZero().

◆ checkRippleForSignedAdd()

static bool checkRippleForSignedAdd ( const KnownBits LHSKnown,
const KnownBits RHSKnown 
)
static

Return true if we can prove that adding the two values of the knownbits will not overflow.

Otherwise return false.

Definition at line 3635 of file ValueTracking.cpp.

References llvm::APInt::clearSignBit(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::APInt::isSignBitClear(), llvm::APInt::isSignBitSet(), llvm::KnownBits::One, and llvm::KnownBits::Zero.

Referenced by computeOverflowForSignedAdd().

◆ computeKnownBits() [1/2]

void computeKnownBits ( const Value V,
KnownBits Known,
unsigned  Depth,
const Query Q 
)
static

Determine which bits of V are known to be either zero or one and return them in the Known bit set.

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

References llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Align, assert(), C, llvm::computeKnownBits(), computeKnownBitsFromAssume(), computeKnownBitsFromOperator(), llvm::countTrailingZeros(), llvm::Constant::getAggregateElement(), llvm::KnownBits::getBitWidth(), llvm::Value::getPointerAlignment(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::Type::isIntOrIntVectorTy(), llvm::Type::isPointerTy(), llvm::Type::isPtrOrPtrVectorTy(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), llvm::KnownBits::One, llvm::KnownBits::resetAll(), llvm::APInt::setAllBits(), llvm::KnownBits::setAllZero(), llvm::APInt::setLowBits(), and llvm::KnownBits::Zero.

Referenced by llvm::computeKnownBits().

◆ computeKnownBits() [2/2]

KnownBits computeKnownBits ( const Value V,
unsigned  Depth,
const Query Q 
)
static

Determine which bits of V are known to be either zero or one and return them.

Definition at line 1458 of file ValueTracking.cpp.

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

◆ computeKnownBitsAddSub()

static void computeKnownBitsAddSub ( bool  Add,
const Value Op0,
const Value Op1,
bool  NSW,
KnownBits KnownOut,
KnownBits Known2,
unsigned  Depth,
const Query Q 
)
static

◆ computeKnownBitsFromAssume()

static void computeKnownBitsFromAssume ( const Value V,
KnownBits Known,
unsigned  Depth,
const Query Q 
)
static

Definition at line 498 of file ValueTracking.cpp.

References Arg, assert(), B, C, llvm::computeKnownBits(), llvm::KnownBits::countMinLeadingZeros(), llvm::CallInst::getArgOperand(), llvm::KnownBits::getBitWidth(), llvm::CallInst::getCalledFunction(), llvm::Function::getIntrinsicID(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), 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::intersects(), llvm::KnownBits::isAllOnes(), llvm::isKnownToBeAPowerOfTwo(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::isValidAssumeForContext(), llvm::KnownBits::isZero(), llvm::APInt::lshrInPlace(), llvm::PatternMatch::m_BitCast(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_c_ICmp(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_c_Xor(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_PtrToInt(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Shr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::KnownBits::makeNegative(), llvm::KnownBits::makeNonNegative(), llvm::PatternMatch::match(), llvm::KnownBits::One, Query(), llvm::KnownBits::resetAll(), llvm::KnownBits::setAllOnes(), llvm::KnownBits::setAllZero(), llvm::APInt::setHighBits(), and llvm::KnownBits::Zero.

Referenced by computeKnownBits().

◆ computeKnownBitsFromOperator()

static void computeKnownBitsFromOperator ( const Operator I,
KnownBits Known,
unsigned  Depth,
const Query Q 
)
static

Definition at line 881 of file ValueTracking.cpp.

References llvm::MCID::Add, llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Align, llvm::APInt::ashr(), assert(), llvm::APInt::byteSwap(), llvm::MCID::Call, llvm::computeKnownBits(), computeKnownBitsAddSub(), llvm::computeKnownBitsFromRangeMetadata(), computeKnownBitsFromShiftOperator(), computeKnownBitsMul(), llvm::APInt::countLeadingZeros(), llvm::KnownBits::countMaxLeadingZeros(), llvm::KnownBits::countMaxPopulation(), llvm::KnownBits::countMinLeadingOnes(), llvm::KnownBits::countMinLeadingZeros(), llvm::KnownBits::countMinTrailingOnes(), llvm::KnownBits::countMinTrailingZeros(), llvm::countTrailingZeros(), llvm::APInt::countTrailingZeros(), llvm::Depth, llvm::dyn_cast(), llvm::SelectPatternResult::Flavor, llvm::gep_type_begin(), llvm::AllocaInst::getAlignment(), llvm::AllocaInst::getAllocatedType(), llvm::KnownBits::getBitWidth(), llvm::StructLayout::getElementOffset(), llvm::PHINode::getIncomingValue(), llvm::generic_gep_type_iterator< ItTy >::getIndexedType(), llvm::ExtractValueInst::getIndices(), llvm::PHINode::getNumIncomingValues(), llvm::ExtractValueInst::getNumIndices(), llvm::User::getNumOperands(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Constant::getSplatValue(), llvm::generic_gep_type_iterator< ItTy >::getStructTypeOrNull(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::PHINode::hasConstantValue(), I, if(), llvm::PHINode::incoming_values(), llvm::APInt::intersects(), llvm::Type::isIntegerTy(), llvm::SelectPatternResult::isMinOrMax(), llvm::KnownBits::isNegative(), llvm::KnownBits::isNonNegative(), llvm::Type::isPointerTy(), llvm::APInt::isPowerOf2(), llvm::APInt::isSignBitSet(), llvm::Type::isSized(), llvm::APInt::isSubsetOf(), llvm::Type::isVectorTy(), llvm::Constant::isZeroValue(), LLVM_FALLTHROUGH, llvm::SPII::Load, llvm::Log2_32(), llvm::APInt::lshr(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::KnownBits::makeNegative(), llvm::KnownBits::makeNonNegative(), llvm::PatternMatch::match(), llvm::matchSelectPattern(), llvm::max(), llvm::LLVMContext::MD_range, llvm::KnownBits::One, P, RA, llvm::KnownBits::resetAll(), llvm::APInt::reverseBits(), llvm::MCID::Select, llvm::APInt::setAllBits(), llvm::APInt::setBit(), llvm::APInt::setBitsFrom(), llvm::APInt::setHighBits(), llvm::APInt::setLowBits(), llvm::APInt::setSignBit(), llvm::KnownBits::sext(), llvm::SPF_SMAX, llvm::SPF_SMIN, llvm::SPF_UMAX, llvm::SPF_UMIN, llvm::KnownBits::trunc(), Y, llvm::KnownBits::Zero, and llvm::KnownBits::zextOrTrunc().

Referenced by computeKnownBits().

◆ computeKnownBitsFromShiftOperator()

static void computeKnownBitsFromShiftOperator ( const Operator I,
KnownBits Known,
KnownBits Known2,
unsigned  Depth,
const Query Q,
function_ref< APInt(const APInt &, unsigned)>  KZF,
function_ref< APInt(const APInt &, unsigned)>  KOF 
)
static

Compute known bits from a shift operator, including those with a non-constant shift amount.

Known is the output of this function. Known2 is a pre-allocated temporary with the same bit width as Known. KZF and KOF are operator-specific functors that, given the known-zero or known-one bits respectively, and a shift amount, compute the implied known-zero or known-one bits of the shift operator's result respectively for that shift amount. The results from calling KZF and KOF are conservatively combined for all permitted shift amounts.

Definition at line 794 of file ValueTracking.cpp.

References llvm::computeKnownBits(), llvm::KnownBits::getBitWidth(), llvm::User::getOperand(), llvm::APInt::getZExtValue(), llvm::KnownBits::hasConflict(), llvm::Optional< T >::hasValue(), llvm::isKnownNonZero(), llvm::KnownBits::One, llvm::PowerOf2Ceil(), llvm::KnownBits::resetAll(), llvm::APInt::setAllBits(), llvm::KnownBits::setAllZero(), llvm::KnownBits::Zero, and llvm::APInt::zextOrTrunc().

Referenced by computeKnownBitsFromOperator().

◆ computeKnownBitsMul()

static void computeKnownBitsMul ( const Value Op0,
const Value Op1,
bool  NSW,
KnownBits Known,
KnownBits Known2,
unsigned  Depth,
const Query Q 
)
static

◆ ComputeNumSignBits()

static unsigned ComputeNumSignBits ( const Value V,
unsigned  Depth,
const Query Q 
)
static

Definition at line 2115 of file ValueTracking.cpp.

References assert(), and ComputeNumSignBitsImpl().

Referenced by llvm::ComputeNumSignBits().

◆ ComputeNumSignBitsImpl()

static unsigned ComputeNumSignBitsImpl ( const Value V,
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. For vectors, return the number of sign bits for the vector element with the mininum number of known sign bits.

Definition at line 2128 of file ValueTracking.cpp.

References llvm::MCID::Add, assert(), llvm::APInt::ceilLogBase2(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), computeNumSignBitsVectorConstant(), llvm::KnownBits::countMinSignBits(), llvm::dyn_cast(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Operator::getOpcode(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::APInt::getZExtValue(), llvm::KnownBits::isNonNegative(), llvm::APInt::isStrictlyPositive(), llvm::APInt::logBase2(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::match(), llvm::max(), llvm::MCID::Select, and llvm::KnownBits::Zero.

Referenced by ComputeNumSignBits(), and computeNumSignBitsVectorConstant().

◆ computeNumSignBitsVectorConstant()

static unsigned computeNumSignBitsVectorConstant ( const Value V,
unsigned  TyBits 
)
static

For vector constants, loop over the elements and find the constant with the minimum number of sign bits.

Return 0 if the value is not a vector constant or if any element was not analyzed; otherwise, return the count for the element with the minimum number of sign bits.

Definition at line 2088 of file ValueTracking.cpp.

References ComputeNumSignBitsImpl(), llvm::APInt::countLeadingZeros(), llvm::dyn_cast(), llvm::APInt::isNegative(), and Query().

Referenced by ComputeNumSignBitsImpl().

◆ computeOverflowForSignedAdd()

static OverflowResult computeOverflowForSignedAdd ( const Value LHS,
const Value RHS,
const AddOperator Add,
const DataLayout DL,
AssumptionCache AC,
const Instruction CxtI,
const DominatorTree DT 
)
static

◆ getBitWidth()

static unsigned getBitWidth ( Type Ty,
const DataLayout DL 
)
static

Returns the bitwidth of the given scalar or pointer type.

For vector types, returns the element type's bitwidth.

Definition at line 88 of file ValueTracking.cpp.

References assert(), llvm::WebAssembly::End, llvm::find(), llvm::DataLayout::getPointerTypeSizeInBits(), llvm::Type::getScalarSizeInBits(), and Query().

Referenced by CanBeMax(), CanBeMin(), llvm::ARMTargetLowering::canCombineStoreAndExtract(), canConvertValue(), llvm::FunctionComparator::cmpTypes(), collectBitParts(), computeKnownBits(), llvm::ConstantFoldCastInstruction(), llvm::createSeparateConstOffsetFromGEPPass(), DecodeFixedType(), llvm::NVPTXAsmPrinter::doFinalization(), emitX86MaskSelect(), ExtractConstantBytes(), foldICmpWithMinMax(), getAttrKindEncoding(), llvm::ExecutionEngine::getConstantValue(), llvm::EVT::getEVT(), GetLoopInvariantInsertPosition(), llvm::IntegerType::getMask(), getNoopInput(), getOpenCLAlignment(), llvm::Type::getPrimitiveSizeInBits(), llvm::NVPTXTargetLowering::getPrototype(), getRangeForAffineARHelper(), llvm::SCEVExpander::getRelatedExistingExpansion(), llvm::MVT::getVT(), getX86MaskVec(), INITIALIZE_PASS(), isBroadcastShuffle(), isGEPFoldable(), IsIncrementNSW(), IsIncrementNUW(), llvm::Type::isIntegerTy(), isKnownNonZero(), IsNonLocalValue(), llvm::IntegerType::isPowerOf2ByteWidth(), LLVMCreateGenericValueOfInt(), LLVMGetIntTypeWidth(), llvm::ExecutionEngine::LoadValueFromMemory(), MatchBinaryOp(), llvm::APInt::operator[](), PrintLLVMName(), readWideAPInt(), llvm::MCJIT::runFunction(), llvm::orc::OrcMCJITReplacement::runFunction(), shouldMergeGEPs(), SumCanReachMax(), SumCanReachMin(), UnpackFromArgumentSlot(), llvm::UnrollRuntimeLoopRemainder(), UpgradeMaskedLoad(), UpgradeMaskedStore(), llvm::sroa::AllocaSliceRewriter::visit(), llvm::Interpreter::visitAllocaInst(), llvm::Interpreter::visitAShr(), and llvm::InstCombiner::visitCallInst().

◆ GetStringLengthH()

static uint64_t GetStringLengthH ( const Value V,
SmallPtrSetImpl< const PHINode *> &  PHIs,
unsigned  CharSize 
)
static

◆ getUnderlyingObjectFromInt()

static const Value* getUnderlyingObjectFromInt ( const Value V)
static

This is the function that does the work of looking through basic ptrtoint+arithmetic+inttoptr sequences.

Definition at line 3393 of file ValueTracking.cpp.

References llvm::MCID::Add, assert(), llvm::Operator::getOpcode(), llvm::Value::getType(), and llvm::Type::isIntegerTy().

Referenced by llvm::getUnderlyingObjectsForCodeGen().

◆ isAddOfNonZero()

static bool isAddOfNonZero ( const Value V1,
const Value V2,
const Query Q 
)
static

Return true if V2 == V1 + X, where X is known non-zero.

Definition at line 2031 of file ValueTracking.cpp.

References llvm::MCID::Add, llvm::dyn_cast(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), and llvm::isKnownNonZero().

Referenced by isKnownNonEqual().

◆ isAssumeLikeIntrinsic()

static bool isAssumeLikeIntrinsic ( const Instruction I)
static

Definition at line 429 of file ValueTracking.cpp.

References F().

Referenced by llvm::isValidAssumeForContext().

◆ isEphemeralValueOf()

static bool isEphemeralValueOf ( const Instruction I,
const Value E 
)
static

◆ isGEPKnownNonNull()

static bool isGEPKnownNonNull ( const GEPOperator GEP,
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 1686 of file ValueTracking.cpp.

References assert(), llvm::Depth, llvm::gep_type_begin(), llvm::gep_type_end(), llvm::StructLayout::getElementOffset(), llvm::GEPOperator::getPointerAddressSpace(), llvm::GEPOperator::getPointerOperand(), llvm::Value::getType(), llvm::ConstantInt::getZExtValue(), llvm::GEPOperator::isInBounds(), llvm::isKnownNonZero(), and llvm::Type::isPointerTy().

Referenced by isKnownNonZero().

◆ isImpliedCondAndOr()

static Optional<bool> isImpliedCondAndOr ( const BinaryOperator LHS,
const ICmpInst RHS,
const DataLayout DL,
bool  LHSIsTrue,
unsigned  Depth 
)
static

Return true if LHS implies RHS is true.

Return false if LHS implies RHS is false. Otherwise, return None if we can't infer anything. We expect the RHS to be an icmp and the LHS to be an 'and' or an 'or' instruction.

Definition at line 4625 of file ValueTracking.cpp.

References assert(), llvm::BinaryOperator::getOpcode(), llvm::isImpliedCondition(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::None.

Referenced by llvm::isImpliedCondition().

◆ isImpliedCondICmps()

static Optional<bool> isImpliedCondICmps ( const ICmpInst LHS,
const ICmpInst RHS,
const DataLayout DL,
bool  LHSIsTrue,
unsigned  Depth 
)
static

Return true if LHS implies RHS is true.

Return false if LHS implies RHS is false. Otherwise, return None if we can't infer anything.

Definition at line 4579 of file ValueTracking.cpp.

References llvm::ARCCC::BRHS, llvm::CmpInst::getInversePredicate(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), isImpliedCondMatchingImmOperands(), isImpliedCondMatchingOperands(), isImpliedCondOperands(), isMatchingOps(), and llvm::None.

Referenced by llvm::isImpliedCondition().

◆ isImpliedCondMatchingImmOperands()

static Optional<bool> isImpliedCondMatchingImmOperands ( CmpInst::Predicate  APred,
const Value ALHS,
const ConstantInt C1,
CmpInst::Predicate  BPred,
const Value BLHS,
const ConstantInt C2 
)
static

Return true if "icmp1 APred ALHS C1" implies "icmp2 BPred BLHS C2" is true.

Return false if "icmp1 APred ALHS C1" implies "icmp2 BPred BLHS C2" is false. Otherwise, return None if we can't infer anything.

Definition at line 4559 of file ValueTracking.cpp.

References assert(), llvm::ConstantRange::difference(), llvm::ConstantInt::getValue(), llvm::ConstantRange::intersectWith(), llvm::ConstantRange::isEmptySet(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::ConstantRange::makeExactICmpRegion(), and llvm::None.

Referenced by isImpliedCondICmps().

◆ isImpliedCondMatchingOperands()

static Optional<bool> isImpliedCondMatchingOperands ( CmpInst::Predicate  APred,
const Value ALHS,
const Value ARHS,
CmpInst::Predicate  BPred,
const Value BLHS,
const Value BRHS,
bool  IsSwappedOps 
)
static

Return true if "icmp1 APred ALHS ARHS" implies "icmp2 BPred BLHS BRHS" is true.

Return false if "icmp1 APred ALHS ARHS" implies "icmp2 BPred BLHS BRHS" is false. Otherwise, return None if we can't infer anything.

Definition at line 4535 of file ValueTracking.cpp.

References llvm::CmpInst::getSwappedPredicate(), llvm::CmpInst::isImpliedFalseByMatchingCmp(), llvm::CmpInst::isImpliedTrueByMatchingCmp(), llvm::None, and std::swap().

Referenced by isImpliedCondICmps().

◆ isImpliedCondOperands()

static Optional<bool> isImpliedCondOperands ( CmpInst::Predicate  Pred,
const Value ALHS,
const Value ARHS,
const Value BLHS,
const Value BRHS,
const DataLayout DL,
unsigned  Depth 
)
static

Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred ALHS ARHS" is true.

Otherwise, return None.

Definition at line 4498 of file ValueTracking.cpp.

References llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, isTruePredicate(), and llvm::None.

Referenced by isImpliedCondICmps(), and llvm::ScalarEvolution::isLoopEntryGuardedByCond().

◆ isKnownNonEqual()

static bool isKnownNonEqual ( const Value V1,
const Value V2,
const Query Q 
)
static

◆ isKnownNonNaN()

static bool isKnownNonNaN ( const Value V,
FastMathFlags  FMF 
)
static

Definition at line 4001 of file ValueTracking.cpp.

References C, and llvm::FastMathFlags::noNaNs().

Referenced by matchSelectPattern().

◆ isKnownNonNullFromDominatingCondition()

static bool isKnownNonNullFromDominatingCondition ( const Value V,
const Instruction CtxI,
const DominatorTree DT 
)
static

◆ isKnownNonZero() [1/2]

bool isKnownNonZero ( const Value V,
unsigned  Depth,
const Query Q 
)
static

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. For pointers, if the context instruction and dominator tree are specified, perform context-sensitive analysis and return true if the pointer couldn't possibly be null at the specified instruction. Supports values with integer or pointer type and vectors of integers.

Definition at line 1818 of file ValueTracking.cpp.

References llvm::all_of(), C, llvm::computeKnownBits(), llvm::KnownBits::countMaxLeadingZeros(), llvm::KnownBits::countMinTrailingZeros(), llvm::Depth, GEP, getBitWidth(), llvm::Type::getScalarType(), llvm::APInt::getSignedMaxValue(), llvm::Value::getType(), llvm::OverflowingBinaryOperator::hasNoSignedWrap(), llvm::OverflowingBinaryOperator::hasNoUnsignedWrap(), llvm::APInt::intersects(), llvm::PossiblyExactOperator::isExact(), isGEPKnownNonNull(), isKnownNonNullFromDominatingCondition(), llvm::isKnownNonZero(), llvm::isKnownToBeAPowerOfTwo(), llvm::KnownBits::isNegative(), llvm::ConstantInt::isNegative(), llvm::KnownBits::isNonNegative(), llvm::Constant::isNullValue(), llvm::Type::isPointerTy(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Exact(), llvm::PatternMatch::m_IDiv(), llvm::PatternMatch::m_Mul(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_NUWAdd(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Shr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::LLVMContext::MD_nonnull, llvm::LLVMContext::MD_range, llvm::KnownBits::One, rangeMetadataExcludesValue(), SI, std::swap(), X, and Y.

Referenced by llvm::isKnownNonZero().

◆ isKnownNonZero() [2/2]

static bool isKnownNonZero ( const Value V)
static

Definition at line 4010 of file ValueTracking.cpp.

References C.

◆ isKnownToBeAPowerOfTwo()

bool isKnownToBeAPowerOfTwo ( const Value V,
bool  OrZero,
unsigned  Depth,
const Query Q 
)
static

◆ isMatchingOps()

static bool isMatchingOps ( const Value ALHS,
const Value ARHS,
const Value BLHS,
const Value BRHS,
bool IsSwappedOps 
)
static

Return true if the operands of the two compares match.

IsSwappedOps is true when the operands match, but are swapped.

Definition at line 4523 of file ValueTracking.cpp.

References llvm::ARCCC::BRHS.

Referenced by isImpliedCondICmps().

◆ isSameUnderlyingObjectInLoop()

static bool isSameUnderlyingObjectInLoop ( const PHINode PN,
const 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 3286 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().

◆ isTruePredicate()

static bool isTruePredicate ( CmpInst::Predicate  Pred,
const Value LHS,
const Value RHS,
const DataLayout DL,
unsigned  Depth 
)
static

◆ lookThroughCast()

static Value* lookThroughCast ( CmpInst CmpI,
Value V1,
Value V2,
Instruction::CastOps CastOp 
)
static

Helps to match a select pattern in case of a type mismatch.

The function processes the case when type of true and false values of a select instruction differs from type of the cmp instruction operands because of a cast instructon. The function checks if it is legal to move the cast operation after "select". If yes, it returns the new second value of "select" (with the assumption that cast is moved):

  1. As operand of cast instruction when both values of "select" are same cast instructions.
  2. As restored constant (by applying reverse cast operation) when the first value of the "select" is a cast operation and the second value is a constant. NOTE: We return only the new second value because the first value could be accessed as operand of cast instruction.

Definition at line 4307 of file ValueTracking.cpp.

References C, llvm::dyn_cast(), llvm::ConstantExpr::getCast(), llvm::ConstantExpr::getFPExtend(), llvm::ConstantExpr::getFPToSI(), llvm::ConstantExpr::getFPToUI(), llvm::ConstantExpr::getFPTrunc(), llvm::ConstantExpr::getIntegerCast(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::ConstantExpr::getSIToFP(), llvm::ConstantExpr::getTrunc(), llvm::Value::getType(), llvm::ConstantExpr::getUIToFP(), llvm::CmpInst::isSigned(), llvm::CmpInst::isUnsigned(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::match(), and llvm::NVPTX::PTXLdStInstCode::V2.

Referenced by llvm::matchSelectPattern().

◆ MaskedValueIsZero()

bool MaskedValueIsZero ( const Value V,
const APInt Mask,
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 2077 of file ValueTracking.cpp.

References llvm::computeKnownBits(), llvm::APInt::getBitWidth(), llvm::APInt::isSubsetOf(), and llvm::KnownBits::Zero.

Referenced by llvm::MaskedValueIsZero().

◆ matchFastFloatClamp()

static SelectPatternResult matchFastFloatClamp ( CmpInst::Predicate  Pred,
Value CmpLHS,
Value CmpRHS,
Value TrueVal,
Value FalseVal,
Value *&  LHS,
Value *&  RHS 
)
static

◆ matchMinMax()

static SelectPatternResult matchMinMax ( CmpInst::Predicate  Pred,
Value CmpLHS,
Value CmpRHS,
Value TrueVal,
Value FalseVal,
Value *&  LHS,
Value *&  RHS 
)
static

◆ matchSelectPattern()

static SelectPatternResult matchSelectPattern ( CmpInst::Predicate  Pred,
FastMathFlags  FMF,
Value CmpLHS,
Value CmpRHS,
Value TrueVal,
Value FalseVal,
Value *&  LHS,
Value *&  RHS 
)
static

◆ rangeMetadataExcludesValue()

static bool rangeMetadataExcludesValue ( const 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 1797 of file ValueTracking.cpp.

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

Referenced by isKnownNonZero().

◆ safeCxtI()

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

Variable Documentation

◆ DomConditionsMaxUses

cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses", cl::Hidden, cl::init(20))
static

◆ MaxDepth

const unsigned MaxDepth = 6