ConstraintElimination.cpp File Reference

#include "llvm/Transforms/Scalar/ConstraintElimination.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/CommandLine.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>

Go to the source code of this file.

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 OffsetResult	collectOffsets (GEPOperator &GEP, const DataLayout &DL)
static Decomposition	decompose (Value *V, const ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static bool	canUseSExt (ConstantInt *CI)
static bool	preconditionHolds (const ConstraintInfo &Info, CmpInst::Predicate Pred, Value *Op, int64_t RHS)
	Returns true if the pre-condition Op Pred RHS, required to look through an expression while decomposing it, is known to hold given Info.
static Decomposition	decomposeGEP (GEPOperator &GEP, const ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static void	dumpConstraint (ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
static bool	getConstraintFromMemoryAccess (GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value *&A, Value *&B, const DataLayout &DL, const TargetLibraryInfo &TLI)
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 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	replaceSubOverflowUses (IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool	tryToSimplifyOverflowMath (IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static bool	eliminateConstraints (Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)

Variables
static cl::opt< unsigned >	MaxRows ("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))
static cl::opt< bool >	DumpReproducers ("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
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 54 of file ConstraintElimination.cpp.

Function Documentation

canUseSExt()

bool canUseSExt ( ConstantInt * CI )

static

Definition at line 448 of file ConstraintElimination.cpp.

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

Referenced by decompose().

checkAndReplaceCmp()

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

static

Definition at line 1703 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

Definition at line 1619 of file ConstraintElimination.cpp.

References A(), B(), Changed, checkCondition(), llvm::dyn_cast(), llvm::findDbgUsers(), generateReproducer(), llvm::ConstantInt::getBool(), getContextInstForUse(), llvm::DomTreeNodeBase< NodeT >::getDFSNumIn(), llvm::DomTreeNodeBase< NodeT >::getDFSNumOut(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::ICmpInst::getSignedPredicate(), llvm::Value::getType(), II, llvm::CmpInst::isSigned(), llvm::CmpInst::isUnsigned(), llvm::CmpInst::makeCmpResultType(), llvm::Value::replaceUsesWithIf(), ToRemove, and llvm::Value::use_empty().

checkAndReplaceMinMax()

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

static

Definition at line 1683 of file ConstraintElimination.cpp.

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

checkCondition()

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

static

Definition at line 1557 of file ConstraintElimination.cpp.

References A(), B(), 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(), 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 1743 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 415 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, const ConstraintInfo & Info, bool IsSigned, const DataLayout & DL )

static

Definition at line 507 of file ConstraintElimination.cpp.

References A(), assert(), B(), canUseSExt(), llvm::cast(), decompose(), decomposeGEP(), DL, llvm::dyn_cast(), GEP, llvm::APInt::getLimitedValue(), llvm::Type::getScalarSizeInBits(), llvm::Type::getScalarType(), llvm::ConstantInt::getSExtValue(), llvm::Value::getType(), llvm::ConstantInt::getValue(), hasNoUnsignedWrap(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_ULE, llvm::isa(), llvm::isKnownNonNegative(), llvm::ConstantInt::isNegative(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_DisjointOr(), llvm::PatternMatch::m_NNegZExt(), llvm::MIPatternMatch::m_Not(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_NSWMul(), llvm::PatternMatch::m_NSWShl(), llvm::PatternMatch::m_NSWSub(), llvm::PatternMatch::m_NSWTrunc(), llvm::PatternMatch::m_NUWAdd(), llvm::PatternMatch::m_NUWMul(), llvm::PatternMatch::m_NUWShl(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Sub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::SCEVPatternMatch::match(), MaxConstraintValue, and preconditionHolds().

Referenced by decompose(), and decomposeGEP().

decomposeGEP()

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

static

Definition at line 460 of file ConstraintElimination.cpp.

References assert(), collectOffsets(), decompose(), DL, GEP, llvm::CmpInst::ICMP_SGE, llvm::isKnownNonNegative(), llvm::GEPNoWrapFlags::none(), and preconditionHolds().

Referenced by decompose().

dumpConstraint()

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

static

Definition at line 960 of file ConstraintElimination.cpp.

References C(), and llvm::sampleprof::CS.

dumpUnpackedICmp()

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

static

Definition at line 1398 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 1990 of file ConstraintElimination.cpp.

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

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

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 1429 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 1166 of file ConstraintElimination.cpp.

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

getContextInstForUse()

Instruction * getContextInstForUse ( Use & U )

static

Definition at line 71 of file ConstraintElimination.cpp.

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

Referenced by checkAndReplaceCondition().

preconditionHolds()

bool preconditionHolds ( const ConstraintInfo & Info, CmpInst::Predicate Pred, Value * Op, int64_t RHS )

static

Returns true if the pre-condition Op Pred RHS, required to look through an expression while decomposing it, is known to hold given Info.

Definition at line 455 of file ConstraintElimination.cpp.

References RHS.

Referenced by decompose(), and decomposeGEP().

removeEntryFromStack()

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

static

Definition at line 1726 of file ConstraintElimination.cpp.

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

Referenced by checkOrAndOpImpliedByOther().

replaceSubOverflowUses()

bool replaceSubOverflowUses ( IntrinsicInst * II, Value * A, Value * B, SmallVectorImpl< Instruction * > & ToRemove )

static

Definition at line 1927 of file ConstraintElimination.cpp.

References A(), B(), 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::Sub, and ToRemove.

Referenced by tryToSimplifyOverflowMath().

STATISTIC()

STATISTIC	(	NumCondsRemoved	,
		"Number of instructions removed"	)

tryToSimplifyOverflowMath()

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

static

Definition at line 1963 of file ConstraintElimination.cpp.

References A(), B(), Changed, llvm::CmpInst::ICMP_SGE, II, replaceSubOverflowUses(), and ToRemove.

Variable Documentation

DumpReproducers

cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations.")) ( "constraint-elimination-dump-reproducers" , cl::init(false) , cl::Hidden , cl::desc("Dump IR to reproduce successful transformations.")  )

static

Referenced by eliminateConstraints().

MaxConstraintValue

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

static

Definition at line 68 of file ConstraintElimination.cpp.

Referenced by canUseSExt(), and decompose().

MaxRows

cl::opt< unsigned > MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system")) ( "constraint-elimination-max-rows" , cl::init(500) , cl::Hidden , cl::desc("Maximum number of rows to keep in constraint system")  )

static

MinSignedConstraintValue

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

static

Definition at line 69 of file ConstraintElimination.cpp.

Referenced by canUseSExt().