LLVM  15.0.0git
Namespaces | Macros | Functions | Variables
LazyValueInfo.cpp File Reference
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueLattice.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/AssemblyAnnotationWriter.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
Include dependency graph for LazyValueInfo.cpp:

Go to the source code of this file.

Namespaces

 llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Macros

#define DEBUG_TYPE   "lazy-value-info"
 

Functions

 INITIALIZE_PASS_BEGIN (LazyValueInfoWrapperPass, "lazy-value-info", "Lazy Value Information Analysis", false, true) INITIALIZE_PASS_END(LazyValueInfoWrapperPass
 
FunctionPass * llvm::createLazyValueInfoPass ()
 createLazyValueInfoPass - This creates an instance of the LazyValueInfo pass. More...
 
static bool hasSingleValue (const ValueLatticeElement &Val)
 Returns true if this lattice value represents at most one possible value. More...
 
static ValueLatticeElement intersect (const ValueLatticeElement &A, const ValueLatticeElement &B)
 Combine two sets of facts about the same value into a single set of facts. More...
 
static ValueLatticeElement getFromRangeMetadata (Instruction *BBI)
 
static void AddNonNullPointer (Value *Ptr, NonNullPointerSet &PtrSet)
 
static void AddNonNullPointersByInstruction (Instruction *I, NonNullPointerSet &PtrSet)
 
static ValueLatticeElement getValueFromCondition (Value *Val, Value *Cond, bool isTrueDest=true)
 
static ConstantRange getConstantRangeOrFull (const ValueLatticeElement &Val, Type *Ty, const DataLayout &DL)
 
static bool matchICmpOperand (APInt &Offset, Value *LHS, Value *Val, ICmpInst::Predicate Pred)
 
static ValueLatticeElement getValueFromSimpleICmpCondition (CmpInst::Predicate Pred, Value *RHS, const APInt &Offset)
 Get value range for a "(Val + Offset) Pred RHS" condition. More...
 
static ValueLatticeElement getValueFromICmpCondition (Value *Val, ICmpInst *ICI, bool isTrueDest)
 
static ValueLatticeElement getValueFromOverflowCondition (Value *Val, WithOverflowInst *WO, bool IsTrueDest)
 
static Optional< ValueLatticeElement > getValueFromConditionImpl (Value *Val, Value *Cond, bool isTrueDest, bool isRevisit, SmallDenseMap< Value *, ValueLatticeElement > &Visited, SmallVectorImpl< Value * > &Worklist)
 
static bool usesOperand (User *Usr, Value *Op)
 
static bool isOperationFoldable (User *Usr)
 
static ValueLatticeElement constantFoldUser (User *Usr, Value *Op, const APInt &OpConstVal, const DataLayout &DL)
 
static Optional< ValueLatticeElement > getEdgeValueLocal (Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo)
 Compute the value of Val on the edge BBFrom -> BBTo. More...
 
static LazyValueInfoImpl & getImpl (void *&PImpl, AssumptionCache *AC, const Module *M)
 This lazily constructs the LazyValueInfoImpl. More...
 
static bool isKnownNonConstant (Value *V)
 Returns true if we can statically tell that this value will never be a "useful" constant. More...
 
static LazyValueInfo::Tristate getPredicateResult (unsigned Pred, Constant *C, const ValueLatticeElement &Val, const DataLayout &DL, TargetLibraryInfo *TLI)
 
 INITIALIZE_PASS_BEGIN (LazyValueInfoPrinter, "print-lazy-value-info", "Lazy Value Info Printer Pass", false, false) INITIALIZE_PASS_END(LazyValueInfoPrinter
 

Variables

static const unsigned MaxProcessedPerValue = 500
 
lazy value info
 
lazy value Lazy Value Information Analysis
 
lazy value Lazy Value Information false
 
print lazy value Lazy Value Info Printer Pass
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "lazy-value-info"

Definition at line 44 of file LazyValueInfo.cpp.

Function Documentation

◆ AddNonNullPointer()

static void AddNonNullPointer ( Value *  Ptr,
NonNullPointerSet &  PtrSet 
)
static

Definition at line 633 of file LazyValueInfo.cpp.

References llvm::Type::getPointerAddressSpace(), llvm::Value::getType(), and llvm::getUnderlyingObject().

Referenced by AddNonNullPointersByInstruction().

◆ AddNonNullPointersByInstruction()

static void AddNonNullPointersByInstruction ( Instruction *  I,
NonNullPointerSet &  PtrSet 
)
static

Definition at line 639 of file LazyValueInfo.cpp.

References AddNonNullPointer(), I, llvm::ConstantInt::isZero(), MI, and S.

◆ constantFoldUser()

static ValueLatticeElement constantFoldUser ( User *  Usr,
Value *  Op,
const APInt &  OpConstVal,
const DataLayout &  DL 
)
static

Definition at line 1264 of file LazyValueInfo.cpp.

References assert(), DL, llvm::CastInst::getDestTy(), llvm::Constant::getIntegerValue(), llvm::BinaryOperator::getOpcode(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), isOperationFoldable(), LHS, RHS, llvm::SimplifyBinOp(), and llvm::SimplifyCastInst().

Referenced by getEdgeValueLocal().

◆ getConstantRangeOrFull()

static ConstantRange getConstantRangeOrFull ( const ValueLatticeElement &  Val,
Type *  Ty,
const DataLayout &  DL 
)
static

Definition at line 797 of file LazyValueInfo.cpp.

References DL, llvm::ValueLatticeElement::getConstantRange(), and llvm::ValueLatticeElement::isConstantRange().

◆ getEdgeValueLocal()

static Optional<ValueLatticeElement> getEdgeValueLocal ( Value *  Val,
BasicBlock *  BBFrom,
BasicBlock *  BBTo 
)
static

Compute the value of Val on the edge BBFrom -> BBTo.

Returns false if Val is not constrained on the edge. Result is unspecified if return value is false.

Definition at line 1298 of file LazyValueInfo.cpp.

References llvm::ValueLatticeElement::asConstantInteger(), assert(), llvm::BitWidth, constantFoldUser(), llvm::ConstantRange::difference(), DL, llvm::ConstantInt::get(), llvm::ValueLatticeElement::get(), llvm::ValueLatticeElement::getConstantRange(), llvm::Value::getContext(), llvm::Module::getDataLayout(), llvm::Type::getInt1Ty(), llvm::Type::getIntegerBitWidth(), llvm::BasicBlock::getModule(), llvm::ValueLatticeElement::getRange(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), getValueFromCondition(), i, isOperationFoldable(), llvm::ValueLatticeElement::isOverdefined(), move, llvm::None, SI, llvm::ConstantRange::unionWith(), and usesOperand().

◆ getFromRangeMetadata()

static ValueLatticeElement getFromRangeMetadata ( Instruction *  BBI)
static

Definition at line 556 of file LazyValueInfo.cpp.

References llvm::MCID::Call, llvm::getConstantRangeFromMetadata(), llvm::Instruction::getMetadata(), llvm::Instruction::getOpcode(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), llvm::Value::getType(), and llvm::SPII::Load.

◆ getImpl()

static LazyValueInfoImpl& getImpl ( void *&  PImpl,
AssumptionCache *  AC,
const Module *  M 
)
static

This lazily constructs the LazyValueInfoImpl.

Definition at line 1514 of file LazyValueInfo.cpp.

References assert(), DL, llvm::Intrinsic::getName(), and M.

Referenced by llvm::AttributeList::addParamAttribute(), llvm::LazyValueInfo::clear(), llvm::LazyValueInfo::eraseBlock(), llvm::ConstantArray::get(), llvm::AttributeList::get(), llvm::ConstantVector::get(), llvm::MDTuple::get(), llvm::LazyValueInfo::getConstant(), llvm::LazyValueInfo::getConstantOnEdge(), llvm::LazyValueInfo::getConstantRange(), llvm::LazyValueInfo::getConstantRangeOnEdge(), llvm::MDTuple::getDistinct(), llvm::MDTuple::getIfExists(), llvm::LazyValueInfo::getPredicateAt(), llvm::LazyValueInfo::getPredicateOnEdge(), llvm::MDTuple::getTemporary(), llvm::LazyValueInfo::printLVI(), llvm::LazyValueInfo::releaseMemory(), llvm::AttributeList::removeAttributeAtIndex(), llvm::AttributeList::removeAttributesAtIndex(), llvm::LazyValueInfoWrapperPass::runOnFunction(), and llvm::LazyValueInfo::threadEdge().

◆ getPredicateResult()

static LazyValueInfo::Tristate getPredicateResult ( unsigned  Pred,
Constant *  C,
const ValueLatticeElement &  Val,
const DataLayout &  DL,
TargetLibraryInfo *  TLI 
)
static

Definition at line 1667 of file LazyValueInfo.cpp.

References llvm::ConstantFoldCompareInstOperands(), llvm::ConstantRange::contains(), DL, llvm::LazyValueInfo::False, llvm::ValueLatticeElement::getConstant(), llvm::ValueLatticeElement::getConstantRange(), llvm::ValueLatticeElement::getNotConstant(), llvm::ConstantInt::getValue(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::ConstantRange::inverse(), llvm::ValueLatticeElement::isConstant(), llvm::ValueLatticeElement::isConstantRange(), llvm::ValueLatticeElement::isNotConstant(), llvm::Constant::isNullValue(), llvm::ConstantRange::isSingleElement(), llvm::ConstantRange::makeExactICmpRegion(), llvm::LazyValueInfo::True, and llvm::LazyValueInfo::Unknown.

Referenced by llvm::LazyValueInfo::getPredicateAt(), and llvm::LazyValueInfo::getPredicateOnEdge().

◆ getValueFromCondition()

ValueLatticeElement getValueFromCondition ( Value *  Val,
Value *  Cond,
bool  isTrueDest = true 
)
static

Definition at line 1217 of file LazyValueInfo.cpp.

References assert(), Cond, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::ValueLatticeElement::getOverdefined(), getValueFromConditionImpl(), and llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::try_emplace().

Referenced by getEdgeValueLocal().

◆ getValueFromConditionImpl()

static Optional<ValueLatticeElement> getValueFromConditionImpl ( Value *  Val,
Value *  Cond,
bool  isTrueDest,
bool  isRevisit,
SmallDenseMap< Value *, ValueLatticeElement > &  Visited,
SmallVectorImpl< Value * > &  Worklist 
)
static

Definition at line 1165 of file LazyValueInfo.cpp.

References assert(), Cond, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::ExtractValueInst::getAggregateOperand(), llvm::ExtractValueInst::getNumIndices(), llvm::ValueLatticeElement::getOverdefined(), getValueFromICmpCondition(), getValueFromOverflowCondition(), llvm::ExtractValueInst::idx_begin(), intersect(), llvm::ValueLatticeElement::isOverdefined(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::ValueLatticeElement::mergeIn(), and llvm::None.

Referenced by getValueFromCondition().

◆ getValueFromICmpCondition()

static ValueLatticeElement getValueFromICmpCondition ( Value *  Val,
ICmpInst *  ICI,
bool  isTrueDest 
)
static

Definition at line 1074 of file LazyValueInfo.cpp.

References llvm::BitWidth, llvm::ConstantRange::fromKnownBits(), llvm::ValueLatticeElement::get(), llvm::CmpInst::getInversePredicate(), llvm::ConstantRange::getNonEmpty(), llvm::ValueLatticeElement::getNot(), llvm::APInt::getOneBitSet(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), llvm::CmpInst::getPredicate(), llvm::ValueLatticeElement::getRange(), llvm::Type::getScalarSizeInBits(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), llvm::ConstantRange::getUnsignedMin(), getValueFromSimpleICmpCondition(), llvm::APInt::getZero(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::ConstantRange::isEmptySet(), llvm::ICmpInst::isEquality(), llvm::Type::isIntegerTy(), LHS, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_URem(), llvm::PatternMatch::m_Value(), llvm::ConstantRange::makeExactICmpRegion(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), matchICmpOperand(), llvm::KnownBits::One, RHS, llvm::KnownBits::Zero, and llvm::APInt::zext().

Referenced by getValueFromConditionImpl().

◆ getValueFromOverflowCondition()

static ValueLatticeElement getValueFromOverflowCondition ( Value *  Val,
WithOverflowInst *  WO,
bool  IsTrueDest 
)
static

Definition at line 1144 of file LazyValueInfo.cpp.

References llvm::BinaryOpIntrinsic::getBinaryOp(), llvm::BinaryOpIntrinsic::getLHS(), llvm::BinaryOpIntrinsic::getNoWrapKind(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), llvm::BinaryOpIntrinsic::getRHS(), llvm::ConstantRange::inverse(), llvm::PatternMatch::m_APInt(), llvm::ConstantRange::makeExactNoWrapRegion(), and llvm::PatternMatch::match().

Referenced by getValueFromConditionImpl().

◆ getValueFromSimpleICmpCondition()

static ValueLatticeElement getValueFromSimpleICmpCondition ( CmpInst::Predicate  Pred,
Value *  RHS,
const APInt &  Offset 
)
static

Get value range for a "(Val + Offset) Pred RHS" condition.

Definition at line 1059 of file LazyValueInfo.cpp.

References llvm::getConstantRangeFromMetadata(), llvm::Type::getIntegerBitWidth(), llvm::ValueLatticeElement::getRange(), llvm::Value::getType(), I, llvm::ConstantRange::makeAllowedICmpRegion(), RHS, and llvm::ConstantRange::subtract().

Referenced by getValueFromICmpCondition().

◆ hasSingleValue()

static bool hasSingleValue ( const ValueLatticeElement &  Val)
static

Returns true if this lattice value represents at most one possible value.

This is as precise as any lattice value can get while still representing reachable code.

Definition at line 70 of file LazyValueInfo.cpp.

References llvm::ValueLatticeElement::getConstantRange(), llvm::ValueLatticeElement::isConstant(), llvm::ValueLatticeElement::isConstantRange(), and llvm::ConstantRange::isSingleElement().

Referenced by intersect().

◆ INITIALIZE_PASS_BEGIN() [1/2]

INITIALIZE_PASS_BEGIN ( LazyValueInfoPrinter  ,
"print-lazy-value-info"  ,
"Lazy Value Info Printer Pass"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN ( LazyValueInfoWrapperPass  ,
"lazy-value-info"  ,
"Lazy Value Information Analysis"  ,
false  ,
true   
)

◆ intersect()

static ValueLatticeElement intersect ( const ValueLatticeElement &  A,
const ValueLatticeElement &  B 
)
static

Combine two sets of facts about the same value into a single set of facts.

Note that this method is not suitable for merging facts along different paths in a CFG; that's what the mergeIn function is for. This is for merging facts gathered about the same value at the same location through two independent means. Notes:

  • This method does not promise to return the most precise possible lattice value implied by A and B. It is allowed to return any lattice element which is at least as strong as either A or B (unless our facts conflict, see below).
  • Due to unreachable code, the intersection of two lattice values could be contradictory. If this happens, we return some valid lattice value so as not confuse the rest of LVI. Ideally, we'd always return Undefined, but we do not make this guarantee. TODO: This would be a useful enhancement.

Definition at line 95 of file LazyValueInfo.cpp.

References B, llvm::ValueLatticeElement::getRange(), hasSingleValue(), and move.

Referenced by getValueFromConditionImpl().

◆ isKnownNonConstant()

static bool isKnownNonConstant ( Value *  V)
static

Returns true if we can statically tell that this value will never be a "useful" constant.

In practice, this means we've got something like an alloca or a malloc call for which a comparison against a constant can only be guarding dead code. Note that we are potentially giving up some precision in dead code (a constant result) in favour of avoiding a expensive search for a easily answered common query.

Definition at line 1582 of file LazyValueInfo.cpp.

References llvm::Value::stripPointerCasts().

Referenced by llvm::LazyValueInfo::getConstant().

◆ isOperationFoldable()

static bool isOperationFoldable ( User *  Usr)
static

Definition at line 1256 of file LazyValueInfo.cpp.

Referenced by constantFoldUser(), and getEdgeValueLocal().

◆ matchICmpOperand()

static bool matchICmpOperand ( APInt &  Offset,
Value *  LHS,
Value *  Val,
ICmpInst::Predicate  Pred 
)
static

Definition at line 1025 of file LazyValueInfo.cpp.

References llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, llvm::CmpInst::ICMP_ULT, LHS, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_And(), llvm::PatternMatch::m_c_Or(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), and llvm::PatternMatch::match().

Referenced by getValueFromICmpCondition().

◆ usesOperand()

static bool usesOperand ( User *  Usr,
Value *  Op 
)
static

Definition at line 1248 of file LazyValueInfo.cpp.

References llvm::is_contained(), and llvm::User::operands().

Referenced by getEdgeValueLocal().

Variable Documentation

◆ Analysis

lazy value Lazy Value Information Analysis

Definition at line 59 of file LazyValueInfo.cpp.

◆ false

print lazy value Lazy Value Info Printer false

Definition at line 59 of file LazyValueInfo.cpp.

◆ info

print lazy value info

Definition at line 58 of file LazyValueInfo.cpp.

Referenced by ARM64EmitRuntimeFunction(), ARM64EmitUnwindInfo(), checkPackedEpilog(), EmitRuntimeFunction(), llvm::Win64EH::UnwindEmitter::EmitUnwindInfo(), llvm::Win64EH::ARM64UnwindEmitter::EmitUnwindInfo(), EmitUnwindInfo(), findLiveReferences(), FindMatchingEpilog(), llvm::CCState::getInRegsParamInfo(), llvm::TargetLowering::getMultipleConstraintMatchWeight(), llvm::SparcTargetLowering::getSingleConstraintMatchWeight(), llvm::AVRTargetLowering::getSingleConstraintMatchWeight(), llvm::SystemZTargetLowering::getSingleConstraintMatchWeight(), llvm::ARMTargetLowering::getSingleConstraintMatchWeight(), llvm::PPCTargetLowering::getSingleConstraintMatchWeight(), llvm::X86TargetLowering::getSingleConstraintMatchWeight(), llvm::TargetLowering::getSingleConstraintMatchWeight(), insertParsePoints(), recomputeLiveInValues(), llvm::MachO::swapStruct(), and tryPackedUnwind().

◆ MaxProcessedPerValue

const unsigned MaxProcessedPerValue = 500
static

Definition at line 48 of file LazyValueInfo.cpp.

◆ Pass

print lazy value Lazy Value Info Printer Pass

Definition at line 1978 of file LazyValueInfo.cpp.

Referenced by llvm::PreservedCFGCheckerInstrumentation::registerCallbacks(), llvm::slpvectorizer::BoUpSLP::VLOperands::reorder(), llvm::PassManager< LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, CGSCCUpdateResult & >::run(), llvm::PassManager< Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, LPMUpdater & >::runSinglePass(), and llvm::MIRProfileLoader::setFSPass().

Generated on Tue May 24 2022 06:39:26 for LLVM by   doxygen 1.8.17