44using namespace PatternMatch;
46#define DEBUG_TYPE "constraint-elimination"
48STATISTIC(NumCondsRemoved,
"Number of instructions removed");
50 "Controls which conditions are eliminated");
54 cl::desc(
"Maximum number of rows to keep in constraint system"));
58 cl::desc(
"Dump IR to reproduce successful transformations."));
84 bool IsSigned =
false;
89 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
91 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
92 ValuesToRelease(ValuesToRelease) {}
96struct PreconditionTy {
102 : Pred(Pred), Op0(Op0), Op1(Op1) {}
111 bool IsSigned =
false;
114 ConstraintTy() =
default;
117 : Coefficients(Coefficients), IsSigned(IsSigned) {}
119 unsigned size()
const {
return Coefficients.
size(); }
121 unsigned empty()
const {
return Coefficients.
empty(); }
125 bool isValid(
const ConstraintInfo &Info)
const;
134class ConstraintInfo {
152 return Signed ? SignedCS : UnsignedCS;
155 return Signed ? SignedCS : UnsignedCS;
159 void popLastNVariables(
bool Signed,
unsigned N) {
160 getCS(
Signed).popLastNVariables(
N);
188 unsigned NumIn,
unsigned NumOut,
197 bool IsKnownNonNegative;
199 DecompEntry(int64_t Coefficient,
Value *Variable,
200 bool IsKnownNonNegative =
false)
201 : Coefficient(Coefficient), Variable(Variable),
202 IsKnownNonNegative(IsKnownNonNegative) {}
206struct Decomposition {
211 Decomposition(
Value *V,
bool IsKnownNonNegative =
false) {
217 void add(int64_t OtherOffset) {
221 void add(
const Decomposition &
Other) {
226 void mul(int64_t Factor) {
228 for (
auto &Var : Vars)
249 if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
252 if (!
GEP.isInBounds())
255 assert(!IsSigned &&
"The logic below only supports decomposition for "
256 "unsinged predicates at the moment.");
257 Type *PtrTy =
GEP.getType()->getScalarType();
258 unsigned BitWidth =
DL.getIndexTypeSizeInBits(PtrTy);
261 if (!
GEP.collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
266 auto *InnerGEP = dyn_cast<GEPOperator>(
GEP.getPointerOperand());
267 if (VariableOffsets.
empty() && InnerGEP && InnerGEP->getNumOperands() == 2) {
268 auto Result =
decompose(InnerGEP, Preconditions, IsSigned,
DL);
272 unsigned Scale =
DL.getTypeAllocSize(InnerGEP->getResultElementType());
273 int64_t ConstantOffsetI = ConstantOffset.
getSExtValue();
274 if (ConstantOffsetI % Scale != 0)
282 -1 * (ConstantOffsetI / Scale)));
288 DecompEntry(1,
GEP.getPointerOperand()));
289 for (
auto [
Index, Scale] : VariableOffsets) {
291 IdxResult.mul(Scale.getSExtValue());
292 Result.add(IdxResult);
310 auto MergeResults = [&Preconditions, IsSigned, &
DL](
Value *
A,
Value *
B,
320 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
322 return CI->getSExtValue();
327 return MergeResults(Op0, Op1, IsSigned);
332 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
335 return int64_t(CI->getZExtValue());
338 if (
auto *
GEP = dyn_cast<GEPOperator>(V))
342 bool IsKnownNonNegative =
false;
344 IsKnownNonNegative =
true;
351 return MergeResults(Op0, Op1, IsSigned);
361 return MergeResults(Op0, Op1, IsSigned);
369 return MergeResults(Op0, CI,
true);
375 return MergeResults(Op0, CI, IsSigned);
380 return {V, IsKnownNonNegative};
381 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
388 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
396 return {0, {{1, Op0}, {-1, Op1}}};
398 return {V, IsKnownNonNegative};
404 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
440 auto &Value2Index = getValue2Index(IsSigned);
442 Preconditions, IsSigned,
DL);
444 Preconditions, IsSigned,
DL);
445 int64_t Offset1 = ADec.Offset;
446 int64_t Offset2 = BDec.Offset;
449 auto &VariablesA = ADec.Vars;
450 auto &VariablesB = BDec.Vars;
455 auto GetOrAddIndex = [&Value2Index, &NewVariables,
456 &NewIndexMap](
Value *
V) ->
unsigned {
457 auto V2I = Value2Index.
find(V);
458 if (V2I != Value2Index.end())
461 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
463 NewVariables.push_back(V);
464 return Insert.first->second;
468 for (
const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
469 GetOrAddIndex(KV.Variable);
480 auto &
R = Res.Coefficients;
481 for (
const auto &KV : VariablesA) {
482 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
484 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
485 I.first->second &= KV.IsKnownNonNegative;
488 for (
const auto &KV : VariablesB) {
489 R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
491 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
492 I.first->second &= KV.IsKnownNonNegative;
499 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
502 Res.Preconditions = std::move(Preconditions);
506 while (!NewVariables.empty()) {
507 int64_t
Last =
R.back();
511 Value *RemovedV = NewVariables.pop_back_val();
512 NewIndexMap.
erase(RemovedV);
516 for (
auto &KV : KnownNonNegativeVariables) {
518 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
521 C[GetOrAddIndex(KV.first)] = -1;
522 Res.ExtraInfo.push_back(
C);
539 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
540 if (
R.IsEq || !NewVariables.
empty())
545bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const {
546 return Coefficients.
size() > 0 &&
547 all_of(Preconditions, [&Info](
const PreconditionTy &
C) {
548 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
554 auto R = getConstraintForSolving(Pred,
A,
B);
555 return R.Preconditions.empty() && !
R.empty() &&
556 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
559void ConstraintInfo::transferToOtherSystem(
564 if (!
A->getType()->isIntegerTy())
611 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
612 IsCheck(IsCheck), Not(Not) {}
616 return FactOrCheck(DTN, Inst,
false, Not);
620 return FactOrCheck(DTN, Inst,
true,
false);
623 bool isAssumeFact()
const {
624 if (!IsCheck && isa<IntrinsicInst>(Inst)) {
625 assert(
match(Inst, m_Intrinsic<Intrinsic::assume>()));
631 bool isConditionFact()
const {
return !IsCheck && isa<CmpInst>(Inst); }
665 bool GuaranteedToExecute =
true;
668 if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
673 if (
match(&
I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
681 isa<ICmpInst>(
Cond)) {
682 if (GuaranteedToExecute) {
686 cast<Instruction>(
Cond)));
689 FactOrCheck::getFact(DT.
getNode(
I.getParent()), &
I));
695 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
696 if (!Br || !Br->isConditional())
717 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
718 if (SeenCond.
insert(V).second)
723 while (!CondWorkList.
empty()) {
725 if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
745 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
748 if (canAddSuccessor(BB, Br->getSuccessor(0)))
750 FactOrCheck::getFact(DT.
getNode(Br->getSuccessor(0)), CmpI));
751 if (canAddSuccessor(BB, Br->getSuccessor(1)))
753 FactOrCheck::getFact(DT.
getNode(Br->getSuccessor(1)), CmpI,
true));
759struct ReproducerEntry {
763 ReproducerEntry(
CmpInst *Cond,
bool IsNot) :
Cond(
Cond), IsNot(IsNot) {}
799 while (!WorkList.
empty()) {
801 if (!Seen.
insert(V).second)
803 if (Old2New.
find(V) != Old2New.
end())
805 if (isa<Constant>(V))
808 auto *
I = dyn_cast<Instruction>(V);
809 if (Value2Index.contains(V) || !
I ||
810 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
820 for (
auto &Entry : Stack)
821 CollectArguments(Entry.Cond);
822 CollectArguments(
Cond);
831 Cond->getModule()->getName() +
832 Cond->getFunction()->getName() +
"repro",
835 for (
unsigned I = 0;
I < Args.size(); ++
I) {
837 Old2New[Args[
I]] =
F->getArg(
I);
843 Builder.SetInsertPoint(Entry->getTerminator());
852 auto &Value2Index =
Info.getValue2Index(IsSigned);
853 while (!WorkList.
empty()) {
855 if (Old2New.
find(V) != Old2New.
end())
858 auto *
I = dyn_cast<Instruction>(V);
859 if (!Value2Index.contains(V) &&
I) {
860 Old2New[V] =
nullptr;
871 Old2New[
I]->setName(
I->getName());
883 for (
auto &Entry : Stack) {
887 LLVM_DEBUG(
dbgs() <<
" Materializing assumption " << *Entry.Cond <<
"\n");
892 CloneInstructions({Entry.Cond->getOperand(0), Entry.Cond->getOperand(1)},
895 auto *Cmp =
Builder.CreateICmp(Pred, Entry.Cond->getOperand(0),
896 Entry.Cond->getOperand(1));
903 Entry->getTerminator()->setOperand(0,
Cond);
910 CmpInst *Cmp, ConstraintInfo &Info,
Module *ReproducerModule,
915 Value *
A = Cmp->getOperand(0);
916 Value *
B = Cmp->getOperand(1);
918 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
919 if (R.empty() || !R.isValid(
Info)){
924 auto &CSToUse =
Info.getCS(R.IsSigned);
929 for (
auto &Row : R.ExtraInfo)
930 CSToUse.addVariableRow(Row);
932 for (
unsigned I = 0;
I < R.ExtraInfo.size(); ++
I)
933 CSToUse.popLastConstraint();
936 bool Changed =
false;
937 if (CSToUse.isConditionImplied(R.Coefficients)) {
942 dbgs() <<
"Condition " << *Cmp <<
" implied by dominating constraints\n";
948 Cmp->replaceUsesWithIf(TrueC, [](
Use &U) {
951 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
952 return !II || II->getIntrinsicID() != Intrinsic::assume;
962 dbgs() <<
"Condition !" << *Cmp <<
" implied by dominating constraints\n";
968 Cmp->replaceAllUsesWith(FalseC);
976 unsigned NumIn,
unsigned NumOut,
981 auto R = getConstraint(Pred,
A,
B, NewVariables);
982 if (!
R.isValid(*
this))
986 A->printAsOperand(
dbgs(),
false);
dbgs() <<
", ";
987 B->printAsOperand(
dbgs(),
false);
dbgs() <<
"'\n");
989 auto &CSToUse = getCS(
R.IsSigned);
990 if (
R.Coefficients.empty())
993 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
999 auto &Value2Index = getValue2Index(
R.IsSigned);
1000 for (
Value *V : NewVariables) {
1001 Value2Index.insert({
V, Value2Index.size() + 1});
1006 dbgs() <<
" constraint: ";
1012 std::move(ValuesToRelease));
1016 for (
auto &Coeff :
R.Coefficients)
1018 CSToUse.addVariableRowFill(
R.Coefficients);
1028 bool Changed =
false;
1030 Value *Sub =
nullptr;
1035 U->replaceAllUsesWith(Sub);
1038 U->replaceAllUsesWith(
Builder.getFalse());
1043 if (U->use_empty()) {
1044 auto *
I = cast<Instruction>(U);
1062 ConstraintInfo &
Info) {
1063 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1064 if (R.size() < 2 || !R.isValid(
Info))
1067 auto &CSToUse =
Info.getCS(R.IsSigned);
1068 return CSToUse.isConditionImplied(R.Coefficients);
1071 bool Changed =
false;
1088 bool Changed =
false;
1091 ConstraintInfo
Info(
F.getParent()->getDataLayout());
1093 std::unique_ptr<Module> ReproducerModule(
1112 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1113 auto HasNoConstOp = [](const FactOrCheck &B) {
1114 return !isa<ConstantInt>(B.Inst->getOperand(0)) &&
1115 !isa<ConstantInt>(B.Inst->getOperand(1));
1119 if (
A.NumIn ==
B.NumIn) {
1120 if (A.isConditionFact() && B.isConditionFact()) {
1121 bool NoConstOpA = HasNoConstOp(A);
1122 bool NoConstOpB = HasNoConstOp(B);
1123 return NoConstOpA < NoConstOpB;
1125 if (
A.isConditionFact())
1127 if (
B.isConditionFact())
1129 return A.Inst->comesBefore(
B.Inst);
1131 return A.NumIn <
B.NumIn;
1139 for (FactOrCheck &CB : S.WorkList) {
1142 while (!DFSInStack.
empty()) {
1143 auto &
E = DFSInStack.
back();
1146 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1148 if (CB.NumOut <=
E.NumOut)
1151 dbgs() <<
"Removing ";
1153 Info.getValue2Index(
E.IsSigned));
1157 Info.popLastConstraint(
E.IsSigned);
1159 auto &Mapping =
Info.getValue2Index(
E.IsSigned);
1160 for (
Value *V :
E.ValuesToRelease)
1162 Info.popLastNVariables(
E.IsSigned,
E.ValuesToRelease.size());
1164 if (ReproducerModule)
1169 dbgs() <<
"Processing ";
1171 dbgs() <<
"condition to simplify: " << *CB.Inst;
1173 dbgs() <<
"fact to add to the system: " << *CB.Inst;
1180 if (
auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
1182 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
1184 ReproducerCondStack, S.DT);
1192 match(Cmp, m_Intrinsic<Intrinsic::assume>(
m_Value(Cmp)));
1197 <<
"Skip adding constraint because system has too many rows.\n");
1205 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1206 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1207 ReproducerCondStack.
emplace_back(cast<CmpInst>(Cmp), CB.Not);
1209 Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1210 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1213 for (
unsigned I = 0,
1214 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1222 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1225 ReproducerModule->print(StringS,
nullptr);
1228 Rem <<
ore::NV(
"module") << S;
1233 unsigned SignedEntries =
1234 count_if(DFSInStack, [](
const StackEntry &
E) {
return E.IsSigned; });
1235 assert(
Info.getCS(
false).size() == DFSInStack.
size() - SignedEntries &&
1236 "updates to CS and DFSInStack are out of sync");
1237 assert(
Info.getCS(
true).size() == SignedEntries &&
1238 "updates to CS and DFSInStack are out of sync");
1242 I->eraseFromParent();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
SmallVector< MachineOperand, 4 > Cond
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
static int64_t MaxConstraintValue
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT)
static int64_t MinSignedConstraintValue
static bool canUseSExt(ConstantInt *CI)
static int64_t multiplyWithOverflow(int64_t A, int64_t B)
static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
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 int64_t addWithOverflow(int64_t A, int64_t B)
static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
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 Decomposition decompose(Value *V, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool eliminateConstraints(Function &F, DominatorTree &DT, OptimizationRemarkEmitter &ORE)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< PreconditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
std::optional< std::vector< StOtherPiece > > Other
This is the interface for a simple mod/ref and alias analysis over globals.
static StringRef getName(Value *V)
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isNegative() const
Determine sign of this APInt.
bool slt(const APInt &RHS) const
Signed less than comparison.
int64_t getSExtValue() const
Get sign extended value.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Represents analyses that only rely on functions' control flow.
Value * getArgOperand(unsigned i) const
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getUnsignedPredicate()
For example, SLT->ULT, SLE->ULE, SGT->UGT, SGE->UGE, ULT->Failed assert.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
static ConstantInt * getFalse(LLVMContext &Context)
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
const APInt & getValue() const
Return the constant as an APInt value reference.
This is an important base class in LLVM.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool addVariableRowFill(ArrayRef< int64_t > R)
void dump() const
Print the constraints in the system.
A parsed version of the target data layout string in and methods for querying it.
static bool shouldExecute(unsigned CounterName)
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const BasicBlock * getParent() const
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs)
Drop all unknown metadata except for debug locations.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
This class implements a map that also provides access to all stored values in a deterministic order.
A Module instance is used to store all the information related to an LLVM module.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
A Use represents the edge between a Value definition and its users.
iterator find(const KeyT &Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
iterator_range< user_iterator > users()
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
self_iterator getIterator()
A raw_ostream that writes to an std::string.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
bool match(Val *V, const Pattern &P)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
void stable_sort(R &&Range)
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
constexpr unsigned MaxAnalysisRecursionDepth
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.