LLVM 19.0.0git
|
#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/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/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 | dumpUnpackedICmp (raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS) |
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::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info) |
static bool | checkAndReplaceCondition (CmpInst *Cmp, 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 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) |
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) |
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() |
#define DEBUG_TYPE "constraint-elimination" |
Definition at line 49 of file ConstraintElimination.cpp.
|
static |
Definition at line 74 of file ConstraintElimination.cpp.
References A, llvm::AddOverflow(), and B.
|
static |
Definition at line 436 of file ConstraintElimination.cpp.
References llvm::ConstantInt::getValue(), MaxConstraintValue, MinSignedConstraintValue, llvm::APInt::sgt(), and llvm::APInt::slt().
Referenced by decompose().
|
static |
Definition at line 1373 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.
|
static |
Definition at line 1410 of file ConstraintElimination.cpp.
References checkCondition(), Info, and ToRemove.
|
static |
Definition at line 1332 of file ConstraintElimination.cpp.
References A, B, llvm::dbgs(), dumpUnpackedICmp(), llvm::CmpInst::getInversePredicate(), I, Info, LLVM_DEBUG, llvm::make_scope_exit(), and llvm::DebugCounter::shouldExecute().
Referenced by checkAndReplaceCondition(), checkAndReplaceMinMax(), and checkOrAndOpImpliedByOther().
|
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 1448 of file ConstraintElimination.cpp.
References A, B, llvm::SmallVectorTemplateCommon< T, typename >::back(), checkCondition(), llvm::ConstantInt::getBool(), llvm::CmpInst::getInversePredicate(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::Value::getType(), Info, llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_LogicalOr(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), removeEntryFromStack(), llvm::User::setOperand(), and llvm::SmallVectorBase< Size_T >::size().
|
static |
Definition at line 402 of file ConstraintElimination.cpp.
References llvm::BitWidth, DL, GEP, and llvm::MapVector< KeyT, ValueT, MapType, VectorType >::size().
Referenced by decomposeGEP().
DEBUG_COUNTER | ( | EliminatedCounter | , |
"conds-eliminated" | , | ||
"Controls which conditions are eliminated" | |||
) |
|
static |
Definition at line 474 of file ConstraintElimination.cpp.
References A, assert(), B, canUseSExt(), decompose(), decomposeGEP(), DL, llvm::SmallVectorImpl< T >::emplace_back(), GEP, llvm::Type::getIntegerBitWidth(), llvm::APInt::getLimitedValue(), llvm::ConstantInt::getSExtValue(), llvm::Value::getType(), llvm::ConstantInt::getValue(), 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_NNegZExt(), llvm::PatternMatch::m_NSWAdd(), llvm::PatternMatch::m_NSWMul(), llvm::PatternMatch::m_NSWShl(), llvm::PatternMatch::m_NUWAdd(), llvm::PatternMatch::m_NUWMul(), llvm::PatternMatch::m_NUWShl(), llvm::PatternMatch::m_NUWSub(), llvm::PatternMatch::m_SExt(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), and MaxConstraintValue.
Referenced by decompose(), and decomposeGEP().
|
static |
Definition at line 441 of file ConstraintElimination.cpp.
References assert(), collectOffsets(), decompose(), DL, llvm::SmallVectorImpl< T >::emplace_back(), GEP, llvm::CmpInst::ICMP_SGE, and llvm::isKnownNonNegative().
Referenced by decompose().
|
static |
Definition at line 888 of file ConstraintElimination.cpp.
References llvm::ConstraintSystem::addVariableRowFill(), llvm::CallingConv::C, and llvm::ConstraintSystem::dump().
|
static |
Definition at line 1173 of file ConstraintElimination.cpp.
References LHS, OS, llvm::Value::printAsOperand(), and RHS.
Referenced by checkCondition(), and generateReproducer().
|
static |
Definition at line 1629 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().
|
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 1204 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(), dumpUnpackedICmp(), 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().
|
static |
Definition at line 80 of file ConstraintElimination.cpp.
Referenced by checkAndReplaceCondition().
|
static |
Definition at line 67 of file ConstraintElimination.cpp.
References A, B, and llvm::MulOverflow().
|
static |
Definition at line 1431 of file ConstraintElimination.cpp.
References Info, and llvm::SmallVectorTemplateBase< T, bool >::pop_back().
Referenced by checkOrAndOpImpliedByOther().
|
static |
Definition at line 1569 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 | ( | NumCondsRemoved | , |
"Number of instructions removed" | |||
) |
|
static |
Definition at line 1602 of file ConstraintElimination.cpp.
References A, B, llvm::CallBase::getArgOperand(), llvm::IntrinsicInst::getIntrinsicID(), llvm::CmpInst::ICMP_SGE, Info, replaceSubOverflowUses(), and ToRemove.
|
static |
Referenced by eliminateConstraints().
|
static |
Definition at line 63 of file ConstraintElimination.cpp.
Referenced by canUseSExt(), and decompose().
|
static |
|
static |
Definition at line 64 of file ConstraintElimination.cpp.
Referenced by canUseSExt().