#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/ValueTracking.h"
#include "llvm/Analysis/ValueLattice.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/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
#include "llvm/Support/raw_ostream.h"
#include <map>

Include dependency graph for LazyValueInfo.cpp:

Namespaces
	llvm
	This class represents lattice values for constants.

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 bool	InstructionDereferencesPointer (Instruction I, Value Ptr)

static bool	isObjectDereferencedInBlock (Value Val, BasicBlock BB)
	Return true if the allocation associated with Val is ever dereferenced within the given basic block. More...

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

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

static ValueLatticeElement	getValueFromCondition (Value Val, Value Cond, bool isTrueDest, DenseMap< Value *, ValueLatticeElement > &Visited)

static ValueLatticeElement	getValueFromConditionImpl (Value Val, Value Cond, bool isTrueDest, DenseMap< Value *, ValueLatticeElement > &Visited)

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 bool	getEdgeValueLocal (Value Val, BasicBlock BBFrom, BasicBlock *BBTo, ValueLatticeElement &Result)
	Compute the value of Val on the edge BBFrom -> BBTo. More...

static LazyValueInfoImpl &	getImpl (void &PImpl, AssumptionCache AC, const DataLayout DL, DominatorTree DT=nullptr)
	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

◆ constantFoldUser()

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

static

Definition at line 1204 of file LazyValueInfo.cpp.

References assert(), C, llvm::CastInst::getDestTy(), llvm::Constant::getIntegerValue(), llvm::BinaryOperator::getOpcode(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), llvm::Value::getType(), isOperationFoldable(), llvm::SimplifyBinOp(), and llvm::SimplifyCastInst().

Referenced by getEdgeValueLocal().

◆ getEdgeValueLocal()

static bool getEdgeValueLocal	(	Value *	Val,
		BasicBlock *	BBFrom,
		BasicBlock *	BBTo,
		ValueLatticeElement &	Result
	)

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 1235 of file LazyValueInfo.cpp.

References llvm::ValueLatticeElement::asConstantInteger(), assert(), C, constantFoldUser(), llvm::dbgs(), llvm::ConstantRange::difference(), llvm::ConstantInt::get(), llvm::ValueLatticeElement::get(), llvm::SelectInst::getCondition(), llvm::ValueLatticeElement::getConstantRange(), llvm::Value::getContext(), llvm::Module::getDataLayout(), getFromRangeMetadata(), llvm::Type::getInt1Ty(), llvm::Type::getIntegerBitWidth(), llvm::BasicBlock::getModule(), llvm::Value::getName(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), getValueFromCondition(), hasSingleValue(), InBlock(), intersect(), isOperationFoldable(), llvm::ValueLatticeElement::isOverdefined(), LLVM_DEBUG, llvm::PBQP::RegAlloc::solve(), llvm::ConstantRange::unionWith(), usesOperand(), and llvm::AArch64CC::VC.

◆ getFromRangeMetadata()

static ValueLatticeElement getFromRangeMetadata ( Instruction * BBI )

static

◆ getImpl()

static LazyValueInfoImpl& getImpl	(	void *&	PImpl,
		AssumptionCache *	AC,
		const DataLayout *	DL,
		DominatorTree *	DT = `nullptr`
	)

static

This lazily constructs the LazyValueInfoImpl.

Definition at line 1469 of file LazyValueInfo.cpp.

References assert().

◆ getPredicateResult()

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

static

Definition at line 1628 of file LazyValueInfo.cpp.

References C, llvm::ConstantFoldCompareInstOperands(), llvm::ConstantRange::contains(), llvm::dyn_cast(), 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() [1/2]

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

static

Definition at line 1180 of file LazyValueInfo.cpp.

References assert().

Referenced by getEdgeValueLocal(), getValueFromConditionImpl(), getValueFromICmpCondition(), and isObjectDereferencedInBlock().

◆ getValueFromCondition() [2/2]

static ValueLatticeElement getValueFromCondition	(	Value *	Val,
		Value *	Cond,
		bool	isTrueDest,
		DenseMap< Value *, ValueLatticeElement > &	Visited
	)

static

Definition at line 1169 of file LazyValueInfo.cpp.

References llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), and getValueFromConditionImpl().

◆ getValueFromConditionImpl()

static ValueLatticeElement getValueFromConditionImpl	(	Value *	Val,
		Value *	Cond,
		bool	isTrueDest,
		DenseMap< Value *, ValueLatticeElement > &	Visited
	)

static

Definition at line 1141 of file LazyValueInfo.cpp.

References llvm::ARCISD::BL, llvm::ISD::BR, llvm::dyn_cast(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), getValueFromCondition(), getValueFromICmpCondition(), and intersect().

Referenced by getValueFromCondition().

◆ getValueFromICmpCondition()

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

static

Definition at line 1073 of file LazyValueInfo.cpp.

References llvm::ValueLatticeElement::get(), llvm::getConstantRangeFromMetadata(), llvm::Type::getIntegerBitWidth(), llvm::CmpInst::getInversePredicate(), llvm::Instruction::getMetadata(), llvm::ValueLatticeElement::getNot(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), llvm::CmpInst::getPredicate(), llvm::ValueLatticeElement::getRange(), llvm::CmpInst::getSwappedPredicate(), llvm::Value::getType(), llvm::ConstantInt::getValue(), getValueFromCondition(), llvm::CmpInst::ICMP_EQ, llvm::ICmpInst::isEquality(), llvm::Type::isIntegerTy(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Specific(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::PatternMatch::match(), llvm::LLVMContext::MD_range, llvm::ConstantRange::subtract(), and std::swap().

Referenced by getValueFromConditionImpl().

◆ 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 67 of file LazyValueInfo.cpp.

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

Referenced by getEdgeValueLocal(), and intersect().

◆ INITIALIZE_PASS_BEGIN() [1/2]

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

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

◆ INITIALIZE_PASS_BEGIN() [2/2]

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

◆ InstructionDereferencesPointer()

static bool InstructionDereferencesPointer	(	Instruction *	I,
		Value *	Ptr
	)

static

Definition at line 650 of file LazyValueInfo.cpp.

References llvm::dyn_cast(), llvm::GetUnderlyingObject(), llvm::ConstantInt::isZero(), and MI.

Referenced by isObjectDereferencedInBlock().

◆ 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 92 of file LazyValueInfo.cpp.

References assert(), llvm::BasicBlock::back(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::clear(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::clear(), clear(), llvm::dbgs(), E, llvm::SmallPtrSetImplBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::end(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::erase(), llvm::SmallPtrSetImpl< PtrType >::erase(), F(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find_as(), llvm::ValueLatticeElement::get(), llvm::ValueLatticeElement::getConstantRange(), llvm::ValueLatticeElement::getOverdefined(), llvm::ValueLatticeElement::getRange(), hasSingleValue(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, ValueInfoT, detail::DenseSetPair< ValueT > >, ValueInfoT >::insert(), llvm::ConstantRange::intersectWith(), llvm::ValueLatticeElement::isConstantRange(), llvm::ValueLatticeElement::isOverdefined(), llvm::ValueLatticeElement::isUndefined(), LLVM_DEBUG, P, llvm::Function::print(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::PBQP::RegAlloc::solve(), llvm::succ_begin(), llvm::succ_end(), std::swap(), and llvm::AArch64CC::VC.

Referenced by adjustDown(), llvm::MDNode::classof(), llvm::rdf::Liveness::computeLiveIns(), getEdgeValueLocal(), getValueFromConditionImpl(), llvm::rdf::RegisterAggr::intersect(), llvm::rdf::RegisterAggr::isCoverOf(), and isObjectDereferencedInBlock().

◆ 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 1542 of file LazyValueInfo.cpp.

References llvm::Value::stripPointerCasts().

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

◆ isObjectDereferencedInBlock()

static bool isObjectDereferencedInBlock	(	Value *	Val,
		BasicBlock *	BB
	)

static

Return true if the allocation associated with Val is ever dereferenced within the given basic block.

This establishes the fact Val is not null, but does not imply that the memory at Val is dereferenceable. (Val may point off the end of the dereferenceable part of the object.)

Definition at line 685 of file LazyValueInfo.cpp.

References llvm::MCID::Add, assert(), B, llvm::ConstantRange::binaryOp(), llvm::ConstantRange::castOp(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::Intrinsic::experimental_guard, llvm::SelectPatternResult::Flavor, llvm::ConstantInt::get(), llvm::ConstantPointerNull::get(), llvm::GlobalValue::getAddressSpace(), llvm::PointerType::getAddressSpace(), llvm::SelectInst::getCondition(), llvm::ValueLatticeElement::getConstantRange(), llvm::Module::getDataLayout(), llvm::Function::getEntryBlock(), llvm::SelectInst::getFalseValue(), llvm::Module::getFunction(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::Type::getIntegerBitWidth(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getModule(), llvm::BasicBlock::getModule(), llvm::Intrinsic::getName(), llvm::Value::getName(), llvm::ValueLatticeElement::getNot(), llvm::PHINode::getNumIncomingValues(), llvm::BinaryOperator::getOpcode(), llvm::CastInst::getOpcode(), llvm::User::getOperand(), llvm::ValueLatticeElement::getOverdefined(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::ValueLatticeElement::getRange(), llvm::ilist_iterator< OptionsT, IsReverse, IsConst >::getReverse(), llvm::SelectInst::getTrueValue(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::GetUnderlyingObject(), llvm::ConstantInt::getValue(), llvm::Optional< T >::getValue(), getValueFromCondition(), llvm::Optional< T >::hasValue(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, InstructionDereferencesPointer(), intersect(), llvm::ValueLatticeElement::isConstantRange(), llvm::isKnownNonZero(), llvm::SelectPatternResult::isMinOrMax(), llvm::ValueLatticeElement::isOverdefined(), llvm::Type::isPointerTy(), llvm::Type::isSized(), llvm::isValidAssumeForContext(), LLVM_DEBUG, llvm_unreachable, llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Specific(), llvm::PatternMatch::m_Value(), llvm::make_range(), llvm::PatternMatch::match(), llvm::matchSelectPattern(), llvm::ValueLatticeElement::mergeIn(), llvm::None, llvm::NullPointerIsDefined(), llvm::pred_begin(), llvm::pred_end(), llvm::BasicBlock::rend(), SI, llvm::ConstantRange::smax(), llvm::ConstantRange::smin(), llvm::SPF_SMAX, llvm::SPF_SMIN, llvm::SPF_UMAX, llvm::SPF_UMIN, llvm::ConstantRange::umax(), and llvm::ConstantRange::umin().

◆ isOperationFoldable()

static bool isOperationFoldable ( User * Usr )

static

Definition at line 1196 of file LazyValueInfo.cpp.

Referenced by constantFoldUser(), and getEdgeValueLocal().

◆ usesOperand()

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

static

Definition at line 1188 of file LazyValueInfo.cpp.

References llvm::find(), llvm::User::op_end(), and llvm::User::operands().

Referenced by getEdgeValueLocal().

Variable Documentation

◆ Analysis

lazy value Lazy Value Information Analysis

Definition at line 55 of file LazyValueInfo.cpp.

◆ false

print lazy value Lazy Value Info Printer false

Definition at line 55 of file LazyValueInfo.cpp.

◆ info

print lazy value info

Definition at line 55 of file LazyValueInfo.cpp.

Referenced by llvm::DependenceAnalysisWrapperPass::DependenceAnalysisWrapperPass(), findLiveReferences(), llvm::AVRTargetLowering::getCmpLibcallReturnType(), llvm::DependenceAnalysisWrapperPass::getDI(), getEstimate(), llvm::CCState::getInRegsParamInfo(), llvm::X86TargetLowering::getMemcmpEqZeroLoadsPerBlock(), getMemCmpLoad(), llvm::SystemZTargetLowering::getPreferredVectorAction(), insertParsePoints(), llvm::LTOModule::makeBuffer(), llvm::OProfileWrapper::OProfileWrapper(), llvm::DependenceAnalysisWrapperPass::print(), recomputeLiveInValues(), llvm::DependenceAnalysisWrapperPass::releaseMemory(), llvm::DependenceAnalysisWrapperPass::runOnFunction(), llvm::PPCTargetLowering::shouldInsertFencesForAtomic(), llvm::AArch64TargetLowering::supportSwiftError(), and UnpackFromArgumentSlot().

◆ 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 1922 of file LazyValueInfo.cpp.

Referenced by llvm::legacy::FunctionPassManagerImpl::getContainedManager(), RedzoneSizeForScale(), llvm::PassManager< Function >::run(), llvm::FunctionToLoopPassAdaptor< LoopPassT >::run(), llvm::ModuleToPostOrderCGSCCPassAdaptor< CGSCCPassT >::run(), llvm::CGSCCToFunctionPassAdaptor< FunctionPassT >::run(), llvm::DevirtSCCRepeatedPass< PassT >::run(), and llvm::ModuleToFunctionPassAdaptor< FunctionPassT >::run().

Namespaces

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ constantFoldUser()

◆ getEdgeValueLocal()

◆ getFromRangeMetadata()

◆ getImpl()

◆ getPredicateResult()

◆ getValueFromCondition() [1/2]

◆ getValueFromCondition() [2/2]

◆ getValueFromConditionImpl()

◆ getValueFromICmpCondition()

◆ hasSingleValue()

◆ INITIALIZE_PASS_BEGIN() [1/2]

◆ INITIALIZE_PASS_BEGIN() [2/2]

◆ InstructionDereferencesPointer()

◆ intersect()

◆ isKnownNonConstant()

◆ isObjectDereferencedInBlock()

◆ isOperationFoldable()

◆ usesOperand()

Variable Documentation

◆ Analysis

◆ false

◆ info

◆ MaxProcessedPerValue

◆ Pass