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/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.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/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <cmath>
#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 int64_t	multiplyWithOverflow (int64_t A, int64_t B)
static int64_t	addWithOverflow (int64_t A, int64_t B)
static Instruction *	getContextInstForUse (Use &U)
static OffsetResult	collectOffsets (GEPOperator &GEP, const DataLayout &DL)
static Decomposition	decompose (Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool	canUseSExt (ConstantInt *CI)
static Decomposition	decomposeGEP (GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static void	dumpConstraint (ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
static void	generateReproducer (CmpInst *Cond, 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 *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst)
static bool	checkAndReplaceCondition (CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)
static void	removeEntryFromStack (const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
static bool	checkAndSecondOpImpliedByFirst (FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
	Check if the first condition for an AND implies the second.
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)

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

Function Documentation

addWithOverflow()

static int64_t addWithOverflow ( int64_t  A, int64_t  B  )

static

Definition at line 76 of file ConstraintElimination.cpp.

References A, llvm::AddOverflow(), and B.

canUseSExt()

static bool canUseSExt ( ConstantInt *  CI )

static

Definition at line 422 of file ConstraintElimination.cpp.

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

Referenced by decompose().

checkAndReplaceCondition()

static bool checkAndReplaceCondition ( CmpInst *  Cmp, ConstraintInfo &  Info, unsigned  NumIn, unsigned  NumOut, Instruction *  ContextInst, Module *  ReproducerModule, ArrayRef< ReproducerEntry >  ReproducerCondStack, DominatorTree &  DT, SmallVectorImpl< Instruction * > &  ToRemove  )

static

Definition at line 1313 of file ConstraintElimination.cpp.

References checkCondition(), generateReproducer(), llvm::ConstantInt::getBool(), getContextInstForUse(), llvm::DomTreeNodeBase< NodeT >::getDFSNumIn(), llvm::DomTreeNodeBase< NodeT >::getDFSNumOut(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), Info, llvm::CmpInst::makeCmpResultType(), and ToRemove.

checkAndSecondOpImpliedByFirst()

static bool checkAndSecondOpImpliedByFirst ( FactOrCheck &  CB, ConstraintInfo &  Info, Module *  ReproducerModule, SmallVectorImpl< ReproducerEntry > &  ReproducerCondStack, SmallVectorImpl< StackEntry > &  DFSInStack  )

static

Check if the first condition for an AND implies the second.

Definition at line 1366 of file ConstraintElimination.cpp.

References A, llvm::And, B, llvm::SmallVectorTemplateCommon< T, typename >::back(), checkCondition(), E, llvm::ConstantInt::getBool(), Info, llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), removeEntryFromStack(), and llvm::SmallVectorBase< Size_T >::size().

checkCondition()

static std::optional< bool > checkCondition ( CmpInst *  Cmp, ConstraintInfo &  Info, unsigned  NumIn, unsigned  NumOut, Instruction *  ContextInst  )

static

Definition at line 1265 of file ConstraintElimination.cpp.

References A, B, llvm::dbgs(), llvm::CmpInst::getPredicateName(), I, Info, LLVM_DEBUG, llvm::make_scope_exit(), and llvm::DebugCounter::shouldExecute().

Referenced by checkAndReplaceCondition(), and checkAndSecondOpImpliedByFirst().

collectOffsets()

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

static

Definition at line 388 of file ConstraintElimination.cpp.

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

Referenced by decomposeGEP().

DEBUG_COUNTER()

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

decompose()

static Decomposition decompose ( Value *  V, SmallVectorImpl< ConditionTy > &  Preconditions, bool  IsSigned, const DataLayout &  DL  )

static

Definition at line 460 of file ConstraintElimination.cpp.

References A, B, canUseSExt(), decompose(), decomposeGEP(), DL, llvm::SmallVectorImpl< T >::emplace_back(), GEP, llvm::ConstantInt::get(), llvm::Type::getIntegerBitWidth(), llvm::ConstantInt::getSExtValue(), llvm::Value::getType(), llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_UGE, llvm::Type::isIntegerTy(), llvm::isKnownNonNegative(), llvm::ConstantInt::isNegative(), llvm::Type::isPointerTy(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_ConstantInt(), llvm::PatternMatch::m_DisjointOr(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_NSWMul(), llvm::PatternMatch::m_NUWAdd(), llvm::PatternMatch::m_NUWMul(), llvm::PatternMatch::m_NUWShl(), llvm::PatternMatch::m_NUWSub(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), llvm::MaxAnalysisRecursionDepth, and MaxConstraintValue.

Referenced by decompose(), and decomposeGEP().

decomposeGEP()

static Decomposition decomposeGEP ( GEPOperator &  GEP, SmallVectorImpl< ConditionTy > &  Preconditions, bool  IsSigned, const DataLayout &  DL  )

static

Definition at line 427 of file ConstraintElimination.cpp.

References assert(), collectOffsets(), decompose(), DL, llvm::SmallVectorImpl< T >::emplace_back(), GEP, llvm::ConstantInt::get(), llvm::CmpInst::ICMP_SGE, llvm::isKnownNonNegative(), and llvm::MaxAnalysisRecursionDepth.

Referenced by decompose().

dumpConstraint()

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

static

Definition at line 851 of file ConstraintElimination.cpp.

References llvm::ConstraintSystem::addVariableRowFill(), llvm::CallingConv::C, and llvm::ConstraintSystem::dump().

eliminateConstraints()

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

static

Definition at line 1514 of file ConstraintElimination.cpp.

References A, B, DumpReproducers, F, llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), if(), Info, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::stable_sort(), and llvm::DominatorTreeBase< NodeT, IsPostDom >::updateDFSNumbers().

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

generateReproducer()

static void generateReproducer ( CmpInst *  Cond, 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 1136 of file ConstraintElimination.cpp.

References A, llvm::append_range(), assert(), B, Cond, llvm::Function::Create(), llvm::BasicBlock::Create(), llvm::IRBuilderBase::CreateAssumption(), llvm::IRBuilderBase::CreateICmp(), llvm::IRBuilderBase::CreateRet(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::Instruction::dropUnknownNonDebugMetadata(), llvm::SmallVectorBase< Size_T >::empty(), llvm::ValueMap< KeyT, ValueT, Config >::end(), F, llvm::ValueMap< KeyT, ValueT, Config >::find(), llvm::IRBuilderBase::GetInsertPoint(), getName(), llvm::IRBuilderBase::getTrue(), I, Info, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::insertBefore(), llvm::CmpInst::isSigned(), LLVM_DEBUG, P, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::remapInstructionsInBlocks(), llvm::Instruction::setDebugLoc(), llvm::IRBuilderBase::SetInsertPoint(), llvm::sort(), and llvm::verifyFunction().

Referenced by checkAndReplaceCondition().

getContextInstForUse()

static Instruction * getContextInstForUse ( Use &  U )

static

Definition at line 82 of file ConstraintElimination.cpp.

Referenced by checkAndReplaceCondition().

multiplyWithOverflow()

static int64_t multiplyWithOverflow ( int64_t  A, int64_t  B  )

static

Definition at line 69 of file ConstraintElimination.cpp.

References A, B, and llvm::MulOverflow().

removeEntryFromStack()

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

static

Definition at line 1350 of file ConstraintElimination.cpp.

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

Referenced by checkAndSecondOpImpliedByFirst().

replaceSubOverflowUses()

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

static

Definition at line 1454 of file ConstraintElimination.cpp.

References A, B, llvm::IRBuilderBase::CreateSub(), llvm::Instruction::eraseFromParent(), llvm::PoisonValue::get(), llvm::IRBuilderBase::getFalse(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::Value::getType(), I, llvm::PatternMatch::m_Value(), llvm::make_early_inc_range(), llvm::PatternMatch::match(), ToRemove, llvm::Value::use_empty(), and llvm::Value::users().

Referenced by tryToSimplifyOverflowMath().

STATISTIC()

STATISTIC	(	NumCondsRemoved	,
		"Number of instructions removed"
	)

tryToSimplifyOverflowMath()

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

static

Definition at line 1487 of file ConstraintElimination.cpp.

References A, B, llvm::ConstantInt::get(), llvm::CallBase::getArgOperand(), llvm::IntrinsicInst::getIntrinsicID(), llvm::CmpInst::ICMP_SGE, Info, 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 65 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 66 of file ConstraintElimination.cpp.

Referenced by canUseSExt().