LLVM 19.0.0git
Macros | Functions | Variables
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/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 InstructiongetContextInstForUse (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< boolcheckCondition (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< unsignedMaxRows ("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))
 
static cl::opt< boolDumpReproducers ("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 49 of file ConstraintElimination.cpp.

Function Documentation

◆ addWithOverflow()

static int64_t addWithOverflow ( int64_t  A,
int64_t  B 
)
static

Definition at line 74 of file ConstraintElimination.cpp.

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

◆ canUseSExt()

static bool canUseSExt ( ConstantInt CI)
static

◆ 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

◆ checkAndReplaceMinMax()

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

Definition at line 1416 of file ConstraintElimination.cpp.

References checkCondition(), Info, and ToRemove.

◆ checkCondition()

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

◆ checkOrAndOpImpliedByOther()

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

◆ collectOffsets()

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

◆ 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

◆ decomposeGEP()

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

◆ dumpConstraint()

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

◆ dumpUnpackedICmp()

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

Definition at line 1179 of file ConstraintElimination.cpp.

References LHS, OS, llvm::Value::printAsOperand(), and RHS.

Referenced by checkCondition(), and generateReproducer().

◆ eliminateConstraints()

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

◆ 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 1210 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().

◆ getContextInstForUse()

static Instruction * getContextInstForUse ( Use U)
static

Definition at line 80 of file ConstraintElimination.cpp.

Referenced by checkAndReplaceCondition().

◆ multiplyWithOverflow()

static int64_t multiplyWithOverflow ( int64_t  A,
int64_t  B 
)
static

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

◆ replaceSubOverflowUses()

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

◆ STATISTIC()

STATISTIC ( NumCondsRemoved  ,
"Number of instructions removed"   
)

◆ tryToSimplifyOverflowMath()

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

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

Referenced by canUseSExt().