#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/ADT/DenseSet.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/InstrTypes.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 <optional>

Classes
class	llvm::LazyValueInfoImpl

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

Macros
#define	DEBUG_TYPE "lazy-value-info"

Typedefs
typedef PointerIntPair< Value *, 1, bool >	CondValue

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.

static bool	hasSingleValue (const ValueLatticeElement &Val)
	Returns true if this lattice value represents at most one possible value.

static ValueLatticeElement	intersect (const ValueLatticeElement &A, const ValueLatticeElement &B)
	Combine two sets of facts about the same value into a single set of facts.

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.

static std::optional< ConstantRange >	getRangeViaSLT (CmpInst::Predicate Pred, APInt RHS, function_ref< std::optional< ConstantRange >(const APInt &)> Fn)

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

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

static std::optional< ValueLatticeElement >	getValueFromConditionImpl (Value *Val, CondValue CondVal, bool isRevisit, SmallDenseMap< CondValue, ValueLatticeElement > &Visited, SmallVectorImpl< CondValue > &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 std::optional< ValueLatticeElement >	getEdgeValueLocal (Value Val, BasicBlock BBFrom, BasicBlock *BBTo)
	Compute the value of Val on the edge BBFrom -> BBTo.

static bool	isKnownNonConstant (Value *V)
	Returns true if we can statically tell that this value will never be a "useful" constant.

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

Variables
static const unsigned	MaxProcessedPerValue = 500

lazy value	info

lazy value Lazy Value Information	Analysis

lazy value Lazy Value Information	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "lazy-value-info"

Definition at line 45 of file LazyValueInfo.cpp.

Typedef Documentation

◆ CondValue

typedef PointerIntPair<Value *, 1, bool> CondValue

Definition at line 1217 of file LazyValueInfo.cpp.

Function Documentation

◆ AddNonNullPointer()

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

static

Definition at line 638 of file LazyValueInfo.cpp.

References llvm::getUnderlyingObject(), and Ptr.

Referenced by AddNonNullPointersByInstruction().

◆ AddNonNullPointersByInstruction()

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

static

Definition at line 644 of file LazyValueInfo.cpp.

References AddNonNullPointer(), I, and MI.

◆ constantFoldUser()

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

static

Definition at line 1333 of file LazyValueInfo.cpp.

References assert(), llvm::CallingConv::C, 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 803 of file LazyValueInfo.cpp.

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

◆ getEdgeValueLocal()

static std::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 1367 of file LazyValueInfo.cpp.

References llvm::ValueLatticeElement::asConstantInteger(), assert(), llvm::BitWidth, constantFoldUser(), llvm::ConstantRange::difference(), DL, llvm::ValueLatticeElement::get(), llvm::ConstantInt::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(), isOperationFoldable(), llvm::ValueLatticeElement::isOverdefined(), llvm::ConstantRange::unionWith(), and usesOperand().

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

◆ getFromRangeMetadata()

static ValueLatticeElement getFromRangeMetadata ( Instruction * BBI )

static

Definition at line 561 of file LazyValueInfo.cpp.

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

Referenced by llvm::LazyValueInfoImpl::getValueAt().

◆ getPredicateResult()

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

static

Definition at line 1792 of file LazyValueInfo.cpp.

References llvm::CallingConv::C, 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().

◆ getRangeViaSLT()

static std::optional< ConstantRange > getRangeViaSLT	(	CmpInst::Predicate	Pred,
		APInt	RHS,
		function_ref< std::optional< ConstantRange >(const APInt &)>	Fn
	)

static

Definition at line 1088 of file LazyValueInfo.cpp.

References assert(), llvm::CmpInst::getInversePredicate(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, and RHS.

Referenced by getValueFromICmpCondition().

◆ getValueFromCondition()

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

static

Definition at line 1285 of file LazyValueInfo.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), Cond, llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::ValueLatticeElement::getOverdefined(), getValueFromConditionImpl(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by llvm::LazyValueInfo::getConstantRangeAtUse(), and getEdgeValueLocal().

◆ getValueFromConditionImpl()

static std::optional< ValueLatticeElement > getValueFromConditionImpl	(	Value *	Val,
		CondValue	CondVal,
		bool	isRevisit,
		SmallDenseMap< CondValue, ValueLatticeElement > &	Visited,
		SmallVectorImpl< CondValue > &	Worklist
	)

static

Definition at line 1219 of file LazyValueInfo.cpp.

References assert(), Cond, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::ExtractValueInst::getAggregateOperand(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getInt(), llvm::ExtractValueInst::getNumIndices(), llvm::ValueLatticeElement::getOverdefined(), llvm::PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info >::getPointer(), getValueFromICmpCondition(), getValueFromOverflowCondition(), llvm::ExtractValueInst::idx_begin(), intersect(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), N, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by getValueFromCondition().

◆ getValueFromICmpCondition()

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

static

Definition at line 1107 of file LazyValueInfo.cpp.

Referenced by getValueFromConditionImpl().

◆ getValueFromOverflowCondition()

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

static

Definition at line 1196 of file LazyValueInfo.cpp.

References llvm::CallingConv::C, 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 1072 of file LazyValueInfo.cpp.

References llvm::getConstantRangeFromMetadata(), llvm::Type::getIntegerBitWidth(), llvm::ValueLatticeElement::getRange(), llvm::Value::getType(), I, llvm::ConstantRange::makeAllowedICmpRegion(), llvm::Offset, 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 71 of file LazyValueInfo.cpp.

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

Referenced by intersect().

◆ INITIALIZE_PASS_BEGIN()

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

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

Referenced by getValueFromConditionImpl(), and llvm::msf::MappedBlockStream::readBytes().

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

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

◆ isOperationFoldable()

static bool isOperationFoldable ( User * Usr )

static

Definition at line 1325 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 1038 of file LazyValueInfo.cpp.

References llvm::CallingConv::C, 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(), llvm::PatternMatch::match(), and llvm::Offset.

Referenced by getValueFromICmpCondition().

◆ usesOperand()

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

static

Definition at line 1317 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 60 of file LazyValueInfo.cpp.

◆ false

lazy value Lazy Value Information false

Definition at line 60 of file LazyValueInfo.cpp.

◆ info

lazy value info

Definition at line 59 of file LazyValueInfo.cpp.

Referenced by ARM64EmitRuntimeFunction(), ARM64EmitUnwindInfo(), ARM64EmitUnwindInfoForSegment(), ARM64FindSegmentsInFunction(), ARM64ProcessEpilogs(), ARMEmitRuntimeFunction(), ARMEmitUnwindInfo(), checkARM64PackedEpilog(), checkARMPackedEpilog(), EmitRuntimeFunction(), llvm::Win64EH::UnwindEmitter::EmitUnwindInfo(), llvm::Win64EH::ARMUnwindEmitter::EmitUnwindInfo(), llvm::Win64EH::ARM64UnwindEmitter::EmitUnwindInfo(), EmitUnwindInfo(), findLiveReferences(), FindMatchingEpilog(), llvm::CCState::getInRegsParamInfo(), llvm::TargetLowering::getMultipleConstraintMatchWeight(), llvm::TargetLowering::getSingleConstraintMatchWeight(), llvm::ARMTargetLowering::getSingleConstraintMatchWeight(), llvm::AVRTargetLowering::getSingleConstraintMatchWeight(), llvm::PPCTargetLowering::getSingleConstraintMatchWeight(), llvm::SparcTargetLowering::getSingleConstraintMatchWeight(), llvm::SystemZTargetLowering::getSingleConstraintMatchWeight(), insertParsePoints(), recomputeLiveInValues(), llvm::MachO::swapStruct(), tryARM64PackedUnwind(), and tryARMPackedUnwind().

◆ MaxProcessedPerValue

const unsigned MaxProcessedPerValue = 500

static

Definition at line 49 of file LazyValueInfo.cpp.

Classes

Namespaces

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ CondValue

Function Documentation

◆ AddNonNullPointer()

◆ AddNonNullPointersByInstruction()

◆ constantFoldUser()

◆ getConstantRangeOrFull()

◆ getEdgeValueLocal()

◆ getFromRangeMetadata()

◆ getPredicateResult()

◆ getRangeViaSLT()

◆ getValueFromCondition()

◆ getValueFromConditionImpl()

◆ getValueFromICmpCondition()

◆ getValueFromOverflowCondition()

◆ getValueFromSimpleICmpCondition()

◆ hasSingleValue()

◆ INITIALIZE_PASS_BEGIN()

◆ intersect()

◆ isKnownNonConstant()

◆ isOperationFoldable()

◆ matchICmpOperand()

◆ usesOperand()

Variable Documentation

◆ Analysis

◆ false

◆ info

◆ MaxProcessedPerValue