#include "llvm/Transforms/Scalar/ConstraintElimination.h"
#include "ScalarOptions.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstraintSystem.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionPatternMatch.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <optional>
#include <string>

Macros
#define	DEBUG_TYPE "constraint-elimination"

Functions
	STATISTIC (NumCondsRemoved, "Number of instructions removed")
	DEBUG_COUNTER (EliminatedCounter, "conds-eliminated", "Controls which conditions are eliminated")
static Instruction *	getContextInstForUse (Use &U)
static Instruction *	findCommonDominatorOfUses (Instruction &I, DominatorTree &DT)
	Returns the closest program point dominating all uses of `I`.
static OffsetResult	collectOffsets (GEPOperator &GEP, const DataLayout &DL)
static Decomposition	decompose (Value *V, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static bool	canUseSExt (ConstantInt *CI)
static bool	hasLimitWitness (const ConstraintInfo &Info, Value *Op, const APInt &Slack, bool Signed, bool Upper)
	Returns true if Op <= MaxVal - Slack holds in the system for `Signed`, by scanning it for a row of the form Op - W <= -Slack, where W is an integer variable no wider than `Op`.
static bool	doesHoldInRange (ConstraintInfo &Info, Value *Op, const ConstantRange &R, bool Signed)
	Returns true if `Info` implies that `Op` is in `R`, interpreting `R` as a signed range if `Signed` is set and as an unsigned range otherwise.
static bool	isKnownNoWrap (Instruction::BinaryOps Opcode, Value Op0, Value Op1, unsigned NoWrapFlags, ConstraintInfo &Info, bool Signed)
	Returns true if `Opcode` applied to `Op0` and `Op1` with `NoWrapFlags` is known to not wrap in signed or unsigned, depending on `Signed`.
static bool	isKnownNoWrap (Value *V, ConstraintInfo &Info, bool Signed)
	Returns true if `V` is known to not wrap in signed or unsigned, depending on `Signed`.
static Decomposition	decomposeGEP (GEPOperator &GEP, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static Decomposition	decomposeImpl (Value *V, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static bool	mayLookThrough (Value *V)
	Returns true if `V` is an operation decomposeImpl can look through.
static RowTy	getRowForLessEqual (const Decomposition &ADec, const Decomposition &BDec, const DenseMap< Value , unsigned > &Value2Index, SmallVectorImpl< Value > &NewVariables)
	Build the row for 'ADec <= BDec', using the indices from `Value2Index`.
static RowTy	getDecompositionLinkRow (Value *V, const ConstraintTy &C, ConstraintInfo &Info, const DataLayout &DL)
	If `V` is a variable in the system and constraint `C` does not contain `V`, we managed to decompose `V` at this point, but likely not earlier when the fact involving `V` was added.
static void	dumpConstraint (ArrayRef< Entry > C, const DenseMap< Value *, unsigned > &Value2Index)
static std::pair< Value , Value >	getStartAndBackedgeValue (const PHINode &PN, const BasicBlock *LoopPred)
	Splits the induction phi `PN` into the start value, coming from the loop predecessor `LoopPred`, and the backedge value, coming from inside the loop.
template<typename PhiMatchTy>
static auto	m_IncrementOf (const PhiMatchTy &PhiM, const APInt *&Off)
	Matches an increment of `PhiM` by a constant offset, captured in `Off`.
static bool	getConstraintFromMemoryAccess (GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value &A, Value &B, const DataLayout &DL, const TargetLibraryInfo &TLI)
static bool	canStrengthenFlags (Instruction *I)
	Returns true if `I` is a candidate whose poison-generating flags may be strengthened using the constraint systems.
static bool	tryToStrengthenFlags (Instruction *I, ConstraintInfo &Info)
	Try to strengthen `I's` poison generating flags using `Info`.
static void	dumpUnpackedICmp (raw_ostream &OS, ICmpInst::Predicate Pred, Value LHS, Value RHS)
static void	generateReproducer (Instruction Cond, bool IsSigned, Module M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)
	Helper function to generate a reproducer function for simplifying `Cond`.
static std::optional< bool >	checkCondition (CmpInst::Predicate Pred, Value A, Value B, Instruction *CheckInst, ConstraintInfo &Info)
static bool	checkAndReplaceCondition (CmpPredicate Pred, Value A, Value B, Instruction CheckInst, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction ContextInst, Module ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction > &ToRemove)
static bool	checkAndReplaceMinMax (MinMaxIntrinsic MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction > &ToRemove)
static bool	checkAndReplaceCmp (CmpIntrinsic I, ConstraintInfo &Info, SmallVectorImpl< Instruction > &ToRemove)
static bool	checkAndReplaceUSubSat (SaturatingInst USub, ConstraintInfo &Info, SmallVectorImpl< Instruction > &ToRemove)
	Try to replace `USub` by a plain subtract, if `Info` proves it cannot saturate.
static void	removeEntryFromStack (const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
static bool	checkOrAndOpImpliedByOther (FactOrCheck &CB, ConstraintInfo &Info, Module ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack, SmallVectorImpl< Instruction > &ToRemove)
	Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second condition or vice versa.
static bool	replaceOverflowUses (WithOverflowInst II, SmallVectorImpl< Instruction > &ToRemove)
	Replace the uses of `II`, which is known not to overflow, by the corresponding plain binary operation and a false overflow flag.
static bool	tryToSimplifyOverflowMath (WithOverflowInst II, ConstraintInfo &Info, SmallVectorImpl< Instruction > &ToRemove)
static bool	eliminateConstraints (Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)

Variables
static int64_t	MaxConstraintValue = std::numeric_limits<int64_t>::max()
static int64_t	MinSignedConstraintValue = std::numeric_limits<int64_t>::min()

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "constraint-elimination"

Definition at line 55 of file ConstraintElimination.cpp.

Function Documentation

◆ canStrengthenFlags()

bool canStrengthenFlags ( Instruction * I )

static

Returns true if I is a candidate whose poison-generating flags may be strengthened using the constraint systems.

Definition at line 1612 of file ConstraintElimination.cpp.

References llvm::dyn_cast(), I, and llvm::isa().

Referenced by tryToStrengthenFlags().

◆ canUseSExt()

bool canUseSExt ( ConstantInt * CI )

static

Definition at line 523 of file ConstraintElimination.cpp.

References llvm::ConstantInt::getValue(), MaxConstraintValue, MinSignedConstraintValue, llvm::APInt::sgt(), and llvm::APInt::slt().

Referenced by decomposeImpl().

◆ checkAndReplaceCmp()

bool checkAndReplaceCmp	(	CmpIntrinsic *	I,
		ConstraintInfo &	Info,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Definition at line 2201 of file ConstraintElimination.cpp.

References checkCondition(), llvm::ConstantInt::getSigned(), I, llvm::CmpInst::ICMP_EQ, LHS, RHS, and ToRemove.

◆ checkAndReplaceCondition()

bool checkAndReplaceCondition	(	CmpPredicate	Pred,
		Value *	A,
		Value *	B,
		Instruction *	CheckInst,
		ConstraintInfo &	Info,
		unsigned	NumIn,
		unsigned	NumOut,
		Instruction *	ContextInst,
		Module *	ReproducerModule,
		ArrayRef< ReproducerEntry >	ReproducerCondStack,
		DominatorTree &	DT,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

◆ checkAndReplaceMinMax()

bool checkAndReplaceMinMax	(	MinMaxIntrinsic *	MinMax,
		ConstraintInfo &	Info,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Definition at line 2181 of file ConstraintElimination.cpp.

References checkCondition(), llvm::CmpInst::getNonStrictPredicate(), and ToRemove.

◆ checkAndReplaceUSubSat()

bool checkAndReplaceUSubSat	(	SaturatingInst *	USub,
		ConstraintInfo &	Info,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Try to replace USub by a plain subtract, if Info proves it cannot saturate.

Returns true if USub was replaced.

Definition at line 2225 of file ConstraintElimination.cpp.

References A(), B(), checkCondition(), llvm::BinaryOpIntrinsic::getLHS(), llvm::BinaryOpIntrinsic::getRHS(), llvm::CmpInst::ICMP_UGE, llvm::Value::replaceAllUsesWith(), llvm::Sub, and ToRemove.

◆ checkCondition()

std::optional< bool > checkCondition	(	CmpInst::Predicate	Pred,
		Value *	A,
		Value *	B,
		Instruction *	CheckInst,
		ConstraintInfo &	Info )

static

Definition at line 2047 of file ConstraintElimination.cpp.

References A(), B(), C(), llvm::dbgs(), dumpUnpackedICmp(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::CmpInst::getInversePredicate(), llvm::ICmpInst::getSignedPredicate(), llvm::CmpInst::isEquality(), llvm::CmpInst::isUnsigned(), LLVM_DEBUG, and llvm::DebugCounter::shouldExecute().

Referenced by checkAndReplaceCmp(), checkAndReplaceCondition(), checkAndReplaceMinMax(), checkAndReplaceUSubSat(), and checkOrAndOpImpliedByOther().

◆ checkOrAndOpImpliedByOther()

bool checkOrAndOpImpliedByOther	(	FactOrCheck &	CB,
		ConstraintInfo &	Info,
		Module *	ReproducerModule,
		SmallVectorImpl< ReproducerEntry > &	ReproducerCondStack,
		SmallVectorImpl< StackEntry > &	DFSInStack,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second condition or vice versa.

Definition at line 2261 of file ConstraintElimination.cpp.

References A(), assert(), B(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::cast(), checkCondition(), E(), llvm::ConstantInt::getBool(), llvm::CmpInst::getInversePredicate(), llvm::User::getOperand(), llvm::Value::getType(), llvm::isa(), LHS, llvm::PatternMatch::m_ICmpLike(), llvm::PatternMatch::m_LogicalAnd(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_Value(), llvm::SCEVPatternMatch::match(), removeEntryFromStack(), llvm::Value::replaceAllUsesWith(), RHS, llvm::SmallVectorTemplateCommon< T, typename >::size(), ToRemove, and llvm::Value::use_empty().

◆ collectOffsets()

OffsetResult collectOffsets	(	GEPOperator &	GEP,
		const DataLayout &	DL )

static

Definition at line 482 of file ConstraintElimination.cpp.

References llvm::BitWidth, DL, llvm::dyn_cast(), GEP, and llvm::MapVector< KeyT, ValueT, MapType, VectorType, N >::size().

Referenced by decomposeGEP(), and getConstraintFromMemoryAccess().

◆ DEBUG_COUNTER()

DEBUG_COUNTER	(	EliminatedCounter	,
		"conds-eliminated"	,
		"Controls which conditions are eliminated"	)

◆ decompose()

Decomposition decompose	(	Value *	V,
		ConstraintInfo &	Info,
		bool	IsSigned,
		const DataLayout &	DL )

static

Definition at line 754 of file ConstraintElimination.cpp.

References decomposeImpl(), DL, llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key, and mayLookThrough().

Referenced by decomposeGEP(), decomposeImpl(), and getDecompositionLinkRow().

◆ decomposeGEP()

Decomposition decomposeGEP	(	GEPOperator &	GEP,
		ConstraintInfo &	Info,
		bool	IsSigned,
		const DataLayout &	DL )

static

Definition at line 672 of file ConstraintElimination.cpp.

References assert(), collectOffsets(), decompose(), DL, GEP, and llvm::GEPNoWrapFlags::none().

Referenced by decomposeImpl().

◆ decomposeImpl()

Decomposition decomposeImpl	(	Value *	V,
		ConstraintInfo &	Info,
		bool	IsSigned,
		const DataLayout &	DL )

static

Definition at line 770 of file ConstraintElimination.cpp.

References A(), llvm::all_of(), B(), canUseSExt(), llvm::cast(), decompose(), decomposeGEP(), DL, llvm::dyn_cast(), E(), GEP, llvm::ConstantInt::getBitWidth(), llvm::Type::getScalarType(), llvm::ConstantInt::getSExtValue(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::ConstantInt::getZExtValue(), llvm::CmpInst::ICMP_UGE, llvm::isa(), isKnownNoWrap(), llvm::ConstantInt::isNegative(), llvm::PatternMatch::m_AddLike(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_Exact(), llvm::PatternMatch::m_Mul(), llvm::MIPatternMatch::m_Not(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Shl(), llvm::PatternMatch::m_Shr(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::SCEVPatternMatch::match(), MaxConstraintValue, and llvm::APInt::ult().

Referenced by decompose().

◆ doesHoldInRange()

bool doesHoldInRange	(	ConstraintInfo &	Info,
		Value *	Op,
		const ConstantRange &	R,
		bool	Signed )

static

Returns true if Info implies that Op is in R, interpreting R as a signed range if Signed is set and as an unsigned range otherwise.

Definition at line 570 of file ConstraintElimination.cpp.

References llvm::BitWidth, llvm::APInt::getMaxValue(), llvm::APInt::getMinValue(), llvm::APInt::getSignedMaxValue(), llvm::APInt::getSignedMinValue(), hasLimitWitness(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, MaxConstraintValue, and llvm::Signed.

Referenced by isKnownNoWrap().

◆ dumpConstraint()

void dumpConstraint	(	ArrayRef< Entry >	C,
		const DenseMap< Value *, unsigned > &	Value2Index )

static

Definition at line 1220 of file ConstraintElimination.cpp.

References llvm::ConstraintSystem::addRow(), C(), llvm::ConstraintSystem::dump(), and llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::size().

◆ dumpUnpackedICmp()

void dumpUnpackedICmp	(	raw_ostream &	OS,
		ICmpInst::Predicate	Pred,
		Value *	LHS,
		Value *	RHS )

static

Definition at line 1867 of file ConstraintElimination.cpp.

References LHS, and RHS.

Referenced by checkCondition(), and generateReproducer().

◆ eliminateConstraints()

bool eliminateConstraints	(	Function &	F,
		DominatorTree &	DT,
		LoopInfo &	LI,
		ScalarEvolution *	SE,
		OptimizationRemarkEmitter &	ORE,
		TargetLibraryInfo &	TLI )

static

Definition at line 2499 of file ConstraintElimination.cpp.

References A(), B(), Changed, F, llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::getScalarOptions(), if(), llvm::make_pointer_range(), llvm::stable_sort(), and llvm::DominatorTreeBase< NodeT, IsPostDom >::updateDFSNumbers().

Referenced by llvm::ConstraintEliminationPass::run().

◆ findCommonDominatorOfUses()

Instruction * findCommonDominatorOfUses	(	Instruction &	I,
		DominatorTree &	DT )

static

Returns the closest program point dominating all uses of I.

Definition at line 72 of file ConstraintElimination.cpp.

References llvm::DominatorTree::findNearestCommonDominator(), getContextInstForUse(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and I.

◆ generateReproducer()

void generateReproducer	(	Instruction *	Cond,
		bool	IsSigned,
		Module *	M,
		ArrayRef< ReproducerEntry >	Stack,
		ConstraintInfo &	Info,
		DominatorTree &	DT )

static

Helper function to generate a reproducer function for simplifying Cond.

The reproducer function contains a series of @llvm.assume calls, one for each condition in Stack. For each condition, the operand instruction are cloned until we reach operands that have an entry in Value2Index. Those will then be added as function arguments. DT is used to order cloned instructions. The reproducer function will get added to M, if it is non-null. Otherwise no reproducer function is generated.

Definition at line 1898 of file ConstraintElimination.cpp.

References A(), AbstractManglingParser< Derived, Alloc >::Ops, llvm::append_range(), assert(), B(), llvm::CmpInst::BAD_ICMP_PREDICATE, Cond, llvm::BasicBlock::Create(), llvm::Function::Create(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::Instruction::dropUnknownNonDebugMetadata(), dumpUnpackedICmp(), llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::ValueMap< KeyT, ValueT, Config >::end(), llvm::GlobalValue::ExternalLinkage, F, llvm::ValueMap< KeyT, ValueT, Config >::find(), llvm::FunctionType::get(), getName(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::insertBefore(), llvm::isa(), llvm::CmpInst::isSigned(), LLVM_DEBUG, P, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::remapInstructionsInBlocks(), llvm::Instruction::setDebugLoc(), llvm::sort(), and llvm::verifyFunction().

Referenced by checkAndReplaceCondition().

◆ getConstraintFromMemoryAccess()

bool getConstraintFromMemoryAccess	(	GetElementPtrInst &	GEP,
		uint64_t	AccessSize,
		CmpPredicate &	Pred,
		Value *&	A,
		Value *&	B,
		const DataLayout &	DL,
		const TargetLibraryInfo &	TLI )

static

Definition at line 1561 of file ConstraintElimination.cpp.

References A(), B(), llvm::sampleprof::Base, llvm::BitWidth, llvm::cast(), collectOffsets(), DL, llvm::dyn_cast(), GEP, llvm::getBaseObjectSize(), llvm::CmpInst::ICMP_ULE, llvm::ObjectSizeOpts::NullIsUnknownSize, llvm::Offset, llvm::ObjectSizeOpts::RoundToAlign, llvm::Size, and uint64_t.

◆ getContextInstForUse()

Instruction * getContextInstForUse ( Use & U )

static

Definition at line 64 of file ConstraintElimination.cpp.

References llvm::cast(), and llvm::dyn_cast().

Referenced by checkAndReplaceCondition(), and findCommonDominatorOfUses().

◆ getDecompositionLinkRow()

RowTy getDecompositionLinkRow	(	Value *	V,
		const ConstraintTy &	C,
		ConstraintInfo &	Info,
		const DataLayout &	DL )

static

If V is a variable in the system and constraint C does not contain V, we managed to decompose V at this point, but likely not earlier when the fact involving V was added.

In that case, return a new row for V <= decompose(V) to link the variable with the decomposition result.

Definition at line 2030 of file ConstraintElimination.cpp.

References llvm::any_of(), C(), decompose(), DL, E(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), and getRowForLessEqual().

◆ getRowForLessEqual()

RowTy getRowForLessEqual	(	const Decomposition &	ADec,
		const Decomposition &	BDec,
		const DenseMap< Value *, unsigned > &	Value2Index,
		SmallVectorImpl< Value * > &	NewVariables )

static

Build the row for 'ADec <= BDec', using the indices from Value2Index.

Variables not in Value2Index are appended to NewVariables and get the indices following the ones in Value2Index. Returns an empty row if the coefficients overflow.

Definition at line 915 of file ConstraintElimination.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::drop_begin(), E(), llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::erase_if(), llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find(), llvm::find_if(), I, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::DenseMapBase< StorageT, KeyT, ValueT, KeyInfoT, BucketT >::size(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::SubOverflow().

Referenced by getDecompositionLinkRow().

◆ getStartAndBackedgeValue()

std::pair< Value , Value > getStartAndBackedgeValue	(	const PHINode &	PN,
		const BasicBlock *	LoopPred )

static

Splits the induction phi PN into the start value, coming from the loop predecessor LoopPred, and the backedge value, coming from inside the loop.

Returns {nullptr, nullptr} if PN has other incoming values.

Definition at line 1232 of file ConstraintElimination.cpp.

References assert(), llvm::PHINode::getBasicBlockIndex(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), and llvm::PHINode::getNumIncomingValues().

◆ hasLimitWitness()

bool hasLimitWitness	(	const ConstraintInfo &	Info,
		Value *	Op,
		const APInt &	Slack,
		bool	Signed,
		bool	Upper )

static

Returns true if Op <= MaxVal - Slack holds in the system for Signed, by scanning it for a row of the form Op - W <= -Slack, where W is an integer variable no wider than Op.

If Upper is false, returns true if Op >= MinVal + Slack holds, using rows of the form W - Op <= -Slack.

Definition at line 532 of file ConstraintElimination.cpp.

References assert(), llvm::find_if(), llvm::Type::getIntegerBitWidth(), llvm::APInt::getZExtValue(), llvm::Type::isIntegerTy(), llvm::APInt::isIntN(), llvm::Signed, and llvm::Upper.

Referenced by doesHoldInRange().

◆ isKnownNoWrap() [1/2]

bool isKnownNoWrap	(	Instruction::BinaryOps	Opcode,
		Value *	Op0,
		Value *	Op1,
		unsigned	NoWrapFlags,
		ConstraintInfo &	Info,
		bool	Signed )

static

Returns true if Opcode applied to Op0 and Op1 with NoWrapFlags is known to not wrap in signed or unsigned, depending on Signed.

Definition at line 607 of file ConstraintElimination.cpp.

References C(), doesHoldInRange(), llvm::dyn_cast(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_UGE, llvm::ConstantRange::makeExactNoWrapRegion(), and llvm::Signed.

Referenced by decomposeImpl(), isKnownNoWrap(), tryToSimplifyOverflowMath(), and tryToStrengthenFlags().

◆ isKnownNoWrap() [2/2]

bool isKnownNoWrap	(	Value *	V,
		ConstraintInfo &	Info,
		bool	Signed )

static

Returns true if V is known to not wrap in signed or unsigned, depending on Signed.

Definition at line 646 of file ConstraintElimination.cpp.

References llvm::dyn_cast(), isKnownNoWrap(), llvm::PatternMatch::m_DisjointOr(), llvm::PatternMatch::m_Value(), llvm::SCEVPatternMatch::match(), and llvm::Signed.

◆ m_IncrementOf()

template<typename PhiMatchTy>

auto m_IncrementOf	(	const PhiMatchTy &	PhiM,
		const APInt *&	Off )

static

Matches an increment of PhiM by a constant offset, captured in Off.

The increment must be a plain IR add or [u|s]add.with.overflow.

Definition at line 1244 of file ConstraintElimination.cpp.

References llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_c_Add(), llvm::PatternMatch::m_c_Intrinsic(), llvm::PatternMatchHelpers::m_CombineOr(), llvm::PatternMatch::m_ExtractValue(), and llvm::Off.

◆ mayLookThrough()

bool mayLookThrough ( Value * V )

static

Returns true if V is an operation decomposeImpl can look through.

Definition at line 731 of file ConstraintElimination.cpp.

References llvm::dyn_cast().

Referenced by decompose().

◆ removeEntryFromStack()

void removeEntryFromStack	(	const StackEntry &	E,
		ConstraintInfo &	Info,
		Module *	ReproducerModule,
		SmallVectorImpl< ReproducerEntry > &	ReproducerCondStack,
		SmallVectorImpl< StackEntry > &	DFSInStack )

static

Definition at line 2243 of file ConstraintElimination.cpp.

References E(), and llvm::SmallVectorTemplateBase< T, bool >::pop_back().

Referenced by checkOrAndOpImpliedByOther().

◆ replaceOverflowUses()

bool replaceOverflowUses	(	WithOverflowInst *	II,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Replace the uses of II, which is known not to overflow, by the corresponding plain binary operation and a false overflow flag.

Definition at line 2453 of file ConstraintElimination.cpp.

References llvm::cast(), Changed, llvm::PoisonValue::get(), I, II, llvm::PatternMatch::m_ExtractValue(), llvm::PatternMatch::m_Value(), llvm::make_early_inc_range(), llvm::SCEVPatternMatch::match(), llvm::Value::replaceAllUsesWith(), and ToRemove.

Referenced by tryToSimplifyOverflowMath().

◆ STATISTIC()

STATISTIC	(	NumCondsRemoved	,
		"Number of instructions removed"	)

◆ tryToSimplifyOverflowMath()

bool tryToSimplifyOverflowMath	(	WithOverflowInst *	II,
		ConstraintInfo &	Info,
		SmallVectorImpl< Instruction * > &	ToRemove )

static

Definition at line 2492 of file ConstraintElimination.cpp.

References II, isKnownNoWrap(), replaceOverflowUses(), and ToRemove.

◆ tryToStrengthenFlags()

bool tryToStrengthenFlags	(	Instruction *	I,
		ConstraintInfo &	Info )

static

Try to strengthen I's poison generating flags using Info.

Returns true if I was modified.

Definition at line 1644 of file ConstraintElimination.cpp.

References assert(), canStrengthenFlags(), Changed, llvm::dbgs(), I, isKnownNoWrap(), and LLVM_DEBUG.

Variable Documentation

◆ MaxConstraintValue

int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max()

static

Definition at line 61 of file ConstraintElimination.cpp.

Referenced by canUseSExt(), decomposeImpl(), and doesHoldInRange().

◆ MinSignedConstraintValue

int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min()

static

Definition at line 62 of file ConstraintElimination.cpp.

Referenced by canUseSExt().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ canStrengthenFlags()

◆ canUseSExt()

◆ checkAndReplaceCmp()

◆ checkAndReplaceCondition()

◆ checkAndReplaceMinMax()

◆ checkAndReplaceUSubSat()

◆ checkCondition()

◆ checkOrAndOpImpliedByOther()

◆ collectOffsets()

◆ DEBUG_COUNTER()

◆ decompose()

◆ decomposeGEP()

◆ decomposeImpl()

◆ doesHoldInRange()

◆ dumpConstraint()

◆ dumpUnpackedICmp()

◆ eliminateConstraints()

◆ findCommonDominatorOfUses()

◆ generateReproducer()

◆ getConstraintFromMemoryAccess()

◆ getContextInstForUse()

◆ getDecompositionLinkRow()

◆ getRowForLessEqual()

◆ getStartAndBackedgeValue()

◆ hasLimitWitness()

◆ isKnownNoWrap() [1/2]

◆ isKnownNoWrap() [2/2]

◆ m_IncrementOf()

◆ mayLookThrough()

◆ removeEntryFromStack()

◆ replaceOverflowUses()

◆ STATISTIC()

◆ tryToSimplifyOverflowMath()

◆ tryToStrengthenFlags()

Variable Documentation

◆ MaxConstraintValue

◆ MinSignedConstraintValue