1//===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// Eliminate conditions based on constraints collected from dominating 12//===----------------------------------------------------------------------===// 48using namespacePatternMatch;
50#define DEBUG_TYPE "constraint-elimination" 52STATISTIC(NumCondsRemoved,
"Number of instructions removed");
54"Controls which conditions are eliminated");
58cl::desc(
"Maximum number of rows to keep in constraint system"));
62cl::desc(
"Dump IR to reproduce successful transformations."));
67// A helper to multiply 2 signed integers where overflowing is allowed. 74// A helper to add 2 signed integers where overflowing is allowed. 83if (
auto *Phi = dyn_cast<PHINode>(UserI))
84 UserI = Phi->getIncomingBlock(U)->getTerminator();
89/// Struct to express a condition of the form %Op0 Pred %Op1. 97 : Pred(Pred), Op0(Op0), Op1(Op1) {}
101/// * a condition that holds on entry to a block (=condition fact) 102/// * an assume (=assume fact) 103/// * a use of a compare instruction to simplify. 104/// It also tracks the Dominator DFS in and out numbers for each entry. 107 ConditionFact,
/// A condition that holds on entry to a block. 108 InstFact,
/// A fact that holds after Inst executed (e.g. an assume or 109 /// min/mix intrinsic. 110 InstCheck,
/// An instruction to simplify (e.g. an overflow math 112 UseCheck
/// An use of a compare instruction to simplify. 121 /// A pre-condition that must hold for the current fact to be added to the 130 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
134 :
U(
U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
135 Ty(EntryTy::UseCheck) {}
138 ConditionTy Precond = {})
140 NumOut(DTN->
getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
144 ConditionTy Precond = {}) {
145return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
149return FactOrCheck(EntryTy::InstFact, DTN, Inst);
153return FactOrCheck(DTN, U);
157return FactOrCheck(EntryTy::InstCheck, DTN, CI);
161return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
165assert(!isConditionFact());
166if (Ty == EntryTy::UseCheck)
173if (Ty == EntryTy::InstCheck)
175// The use may have been simplified to a constant already. 176return dyn_cast<Instruction>(*U);
179bool isConditionFact()
const{
return Ty == EntryTy::ConditionFact; }
182/// Keep state required to build worklist. 190 : DT(DT), LI(LI), SE(SE) {}
192 /// Process block \p BB and add known facts to work-list. 195 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares 196 /// controlling the loop header. 199 /// Returns true if we can add a known condition from BB to its successor 212 /// Variables that can be removed from the system once the stack entry gets 216 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
218 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
219 ValuesToRelease(
std::
move(ValuesToRelease)) {}
230 ConstraintTy() =
default;
234 : Coefficients(
std::
move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),
237unsignedsize()
const{
return Coefficients.
size(); }
239unsigned empty()
const{
return Coefficients.
empty(); }
241 /// Returns true if all preconditions for this list of constraints are 242 /// satisfied given \p CS and the corresponding \p Value2Index mapping. 243boolisValid(
const ConstraintInfo &Info)
const;
245bool isEq()
const{
return IsEq; }
247bool isNe()
const{
return IsNe; }
249 /// Check if the current constraint is implied by the given ConstraintSystem. 251 /// \return true or false if the constraint is proven to be respectively true, 252 /// or false. When the constraint cannot be proven to be either true or false, 253 /// std::nullopt is returned. 261/// Wrapper encapsulating separate constraint systems and corresponding value 262/// mappings for both unsigned and signed information. Facts are added to and 263/// conditions are checked against the corresponding system depending on the 264/// signed-ness of their predicates. While the information is kept separate 265/// based on signed-ness, certain conditions can be transferred between the two 276 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs),
DL(
DL) {
277auto &Value2Index = getValue2Index(
false);
278// Add Arg > -1 constraints to unsigned system for all function arguments. 279for (
Value *Arg : FunctionArgs) {
282 VarPos.Coefficients[Value2Index[Arg]] = -1;
295returnSigned ? SignedCS : UnsignedCS;
298returnSigned ? SignedCS : UnsignedCS;
302void popLastNVariables(
boolSigned,
unsignedN) {
303 getCS(
Signed).popLastNVariables(
N);
311 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 312 /// constraints, using indices from the corresponding constraint system. 313 /// New variables that need to be added to the system are collected in 317bool ForceSignedSystem =
false)
const;
319 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of 320 /// constraints using getConstraint. Returns an empty constraint if the result 321 /// cannot be used to query the existing constraint system, e.g. because it 322 /// would require adding new variables. Also tries to convert signed 323 /// predicates to unsigned ones if possible to allow using the unsigned system 324 /// which increases the effectiveness of the signed <-> unsigned transfer 329 /// Try to add information from \p A \p Pred \p B to the unsigned/signed 330 /// system if \p Pred is signed/unsigned. 332unsigned NumIn,
unsigned NumOut,
336 /// Adds facts into constraint system. \p ForceSignedSystem can be set when 337 /// the \p Pred is eq/ne, and signed constraint system is used when it's 341bool ForceSignedSystem);
344/// Represents a (Coefficient * Variable) entry after IR decomposition. 348 /// True if the variable is known positive in the current constraint. 349bool IsKnownNonNegative;
351 DecompEntry(int64_t Coefficient,
Value *Variable,
352bool IsKnownNonNegative =
false)
353 : Coefficient(Coefficient), Variable(Variable),
354 IsKnownNonNegative(IsKnownNonNegative) {}
357/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition. 363 Decomposition(
Value *V,
bool IsKnownNonNegative =
false) {
369voidadd(int64_t OtherOffset) {
373voidadd(
const Decomposition &
Other) {
378voidsub(
const Decomposition &
Other) {
379 Decomposition Tmp =
Other;
385void mul(int64_t Factor) {
387for (
auto &Var : Vars)
392// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr. 403 ConstantOffset =
APInt(
DL.getIndexTypeSizeInBits(
BasePtr->getType()), 0);
408// Try to collect variable and constant offsets for \p GEP, partly traversing 409// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting 412 OffsetResult Result(
GEP,
DL);
413unsignedBitWidth = Result.ConstantOffset.getBitWidth();
415 Result.ConstantOffset))
418// If we have a nested GEP, check if we can combine the constant offset of the 419// inner GEP with the outer GEP. 420if (
auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {
423bool CanCollectInner = InnerGEP->collectOffset(
424DL,
BitWidth, VariableOffsets2, ConstantOffset2);
425// TODO: Support cases with more than 1 variable offset. 426if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
427 VariableOffsets2.
size() > 1 ||
428 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.
size() >= 1)) {
429// More than 1 variable index, use outer result. 432 Result.BasePtr = InnerGEP->getPointerOperand();
433 Result.ConstantOffset += ConstantOffset2;
434if (Result.VariableOffsets.size() == 0 && VariableOffsets2.
size() == 1)
435 Result.VariableOffsets = VariableOffsets2;
436 Result.NW &= InnerGEP->getNoWrapFlags();
453// Do not reason about pointers where the index size is larger than 64 bits, 454// as the coefficients used to encode constraints are 64 bit integers. 455if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
458assert(!IsSigned &&
"The logic below only supports decomposition for " 459"unsigned predicates at the moment.");
460constauto &[BasePtr, ConstantOffset, VariableOffsets, NW] =
462// We support either plain gep nuw, or gep nusw with non-negative offset, 463// which implies gep nuw. 467 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
468for (
auto [Index, Scale] : VariableOffsets) {
469auto IdxResult =
decompose(Index, Preconditions, IsSigned,
DL);
470 IdxResult.mul(Scale.getSExtValue());
471 Result.add(IdxResult);
473if (!NW.hasNoUnsignedWrap()) {
474// Try to prove nuw from nusw and nneg. 475assert(NW.hasNoUnsignedSignedWrap() &&
"Must have nusw flag");
478 ConstantInt::get(Index->getType(), 0));
484// Decomposes \p V into a constant offset + list of pairs { Coefficient, 485// Variable } where Coefficient * Variable. The sum of the constant offset and 491auto MergeResults = [&Preconditions, IsSigned, &
DL](
Value *
A,
Value *
B,
499Type *Ty = V->getType()->getScalarType();
501if (
auto *
GEP = dyn_cast<GEPOperator>(V))
503if (isa<ConstantPointerNull>(V))
509// Don't handle integers > 64 bit. Our coefficients are 64-bit large, so 510// coefficient add/mul may wrap, while the operation in the full bit width 515bool IsKnownNonNegative =
false;
517// Decompose \p V used with a signed predicate. 519if (
auto *CI = dyn_cast<ConstantInt>(V)) {
521return CI->getSExtValue();
530 IsKnownNonNegative =
true;
537return MergeResults(Op0, Op1, IsSigned);
540auto ResA =
decompose(Op0, Preconditions, IsSigned,
DL);
541auto ResB =
decompose(Op1, Preconditions, IsSigned,
DL);
548auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
553// (shl nsw x, shift) is (mul nsw x, (1<<shift)), with the exception of 557if (Shift < Ty->getIntegerBitWidth() - 1) {
558assert(Shift < 64 &&
"Would overflow");
559auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
560 Result.mul(int64_t(1) << Shift);
565return {V, IsKnownNonNegative};
568if (
auto *CI = dyn_cast<ConstantInt>(V)) {
571return int64_t(CI->getZExtValue());
576 IsKnownNonNegative =
true;
581 ConstantInt::get(Op0->
getType(), 0));
582 }
elseif (
auto *Trunc = dyn_cast<TruncInst>(V)) {
583if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64) {
584if (Trunc->hasNoUnsignedWrap() || Trunc->hasNoSignedWrap()) {
585 V = Trunc->getOperand(0);
586if (!Trunc->hasNoUnsignedWrap())
588 ConstantInt::get(V->getType(), 0));
596return MergeResults(Op0, Op1, IsSigned);
601 ConstantInt::get(Op0->
getType(), 0));
604 ConstantInt::get(Op1->
getType(), 0));
606return MergeResults(Op0, Op1, IsSigned);
614return MergeResults(Op0, CI,
true);
617// Decompose or as an add if there are no common bits between the operands. 619return MergeResults(Op0, CI, IsSigned);
623return {V, IsKnownNonNegative};
624auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
631auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
637auto ResA =
decompose(Op0, Preconditions, IsSigned,
DL);
638auto ResB =
decompose(Op1, Preconditions, IsSigned,
DL);
643return {V, IsKnownNonNegative};
649bool ForceSignedSystem)
const{
650assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
652"signed system can only be forced on eq/ne");
657// Try to convert Pred to one of ULE/SLT/SLE/SLT. 694auto &Value2Index = getValue2Index(IsSigned);
696 Preconditions, IsSigned,
DL);
698 Preconditions, IsSigned,
DL);
699 int64_t Offset1 = ADec.Offset;
700 int64_t Offset2 = BDec.Offset;
703auto &VariablesA = ADec.Vars;
704auto &VariablesB = BDec.Vars;
706// First try to look up \p V in Value2Index and NewVariables. Otherwise add a 707// new entry to NewVariables. 709auto GetOrAddIndex = [&Value2Index, &NewVariables,
710 &NewIndexMap](
Value *
V) ->
unsigned {
711auto V2I = Value2Index.
find(V);
712if (V2I != Value2Index.end())
715 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
717 NewVariables.push_back(V);
718returnInsert.first->second;
721// Make sure all variables have entries in Value2Index or NewVariables. 722for (
constauto &KV : concat<DecompEntry>(VariablesA, VariablesB))
723 GetOrAddIndex(KV.Variable);
725// Build result constraint, by first adding all coefficients from A and then 726// subtracting all coefficients from B. 729 IsSigned, IsEq, IsNe);
730// Collect variables that are known to be positive in all uses in the 733auto &
R = Res.Coefficients;
734for (
constauto &KV : VariablesA) {
735R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
737 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
738I.first->second &= KV.IsKnownNonNegative;
741for (
constauto &KV : VariablesB) {
742auto &Coeff =
R[GetOrAddIndex(KV.Variable)];
746 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
747I.first->second &= KV.IsKnownNonNegative;
757 Res.Preconditions = std::move(Preconditions);
759// Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new 761while (!NewVariables.empty()) {
762 int64_t
Last =
R.back();
766Value *RemovedV = NewVariables.pop_back_val();
767 NewIndexMap.
erase(RemovedV);
770// Add extra constraints for variables that are known positive. 771for (
auto &KV : KnownNonNegativeVariables) {
773 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
775auto &
C = Res.ExtraInfo.emplace_back(
776 Value2Index.size() + NewVariables.size() + 1, 0);
777C[GetOrAddIndex(KV.first)] = -1;
786// Handle trivially true compares directly to avoid adding V UGE 0 constraints 787// for all variables in the unsigned system. 790auto &Value2Index = getValue2Index(
false);
791// Return constraint that's trivially true. 796// If both operands are known to be non-negative, change signed predicates to 797// unsigned ones. This increases the reasoning effectiveness in combination 798// with the signed <-> unsigned transfer logic. 805 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
806if (!NewVariables.
empty())
811bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const{
812return Coefficients.
size() > 0 &&
813all_of(Preconditions, [&Info](
const ConditionTy &
C) {
814returnInfo.doesHold(
C.Pred,
C.Op0,
C.Op1);
824bool IsNegatedOrEqualImplied =
827// In order to check that `%a == %b` is true (equality), both conditions `%a 828// >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq` 829// is true), we return true if they both hold, false in the other cases. 830if (IsConditionImplied && IsNegatedOrEqualImplied)
837bool IsStrictLessThanImplied =
840// In order to check that `%a != %b` is true (non-equality), either 841// condition `%a > %b` or `%a < %b` must hold true. When checking for 842// non-equality (`IsNe` is true), we return true if one of the two holds, 843// false in the other cases. 844if (IsNegatedImplied || IsStrictLessThanImplied)
850if (IsConditionImplied)
858// Neither the condition nor its negated holds, did not prove anything. 864autoR = getConstraintForSolving(Pred,
A,
B);
865returnR.isValid(*
this) &&
866 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
869void ConstraintInfo::transferToOtherSystem(
872auto IsKnownNonNegative = [
this](
Value *
V) {
876// Check if we can combine facts from the signed and unsigned systems to 877// derive additional facts. 878if (!
A->getType()->isIntegerTy())
880// FIXME: This currently depends on the order we add facts. Ideally we 881// would first add all known facts and only then try to add additional 888// If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B. 889if (IsKnownNonNegative(
B)) {
898// If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B. 899if (IsKnownNonNegative(
A)) {
907if (IsKnownNonNegative(
A))
914if (IsKnownNonNegative(
B))
920if (IsKnownNonNegative(
B))
936void State::addInfoForInductions(
BasicBlock &BB) {
938if (!L ||
L->getHeader() != &BB)
952 PN = dyn_cast<PHINode>(
A);
961 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(0);
963 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(1);
967if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB) || InLoopSucc == &BB)
970auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.
getSCEV(PN));
972if (!AR || AR->getLoop() != L || !LoopPred)
975constSCEV *StartSCEV = AR->getStart();
976Value *StartValue =
nullptr;
977if (
auto *
C = dyn_cast<SCEVConstant>(StartSCEV)) {
978 StartValue =
C->getValue();
981assert(SE.
getSCEV(StartValue) == StartSCEV &&
"inconsistent start value");
987bool MonotonicallyIncreasingUnsigned =
989bool MonotonicallyIncreasingSigned =
991// If SCEV guarantees that AR does not wrap, PN >= StartValue can be added 993if (MonotonicallyIncreasingUnsigned)
996if (MonotonicallyIncreasingSigned)
1001if (
auto *
C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
1002 StepOffset =
C->getAPInt();
1006// Make sure the bound B is loop-invariant. 1007if (!
L->isLoopInvariant(
B))
1010// Handle negative steps. 1012// TODO: Extend to allow steps > -1. 1013if (!(-StepOffset).isOne())
1017// Add StartValue >= PN conditional on B <= StartValue which guarantees that 1018// the loop exits before wrapping with a step of -1. 1019 WorkList.
push_back(FactOrCheck::getConditionFact(
1022 WorkList.
push_back(FactOrCheck::getConditionFact(
1025// Add PN > B conditional on B <= StartValue which guarantees that the loop 1026// exits when reaching B with a step of -1. 1027 WorkList.
push_back(FactOrCheck::getConditionFact(
1030 WorkList.
push_back(FactOrCheck::getConditionFact(
1036// Make sure AR either steps by 1 or that the value we compare against is a 1037// GEP based on the same start value and all offsets are a multiple of the 1038// step size, to guarantee that the induction will reach the value. 1042if (!StepOffset.
isOne()) {
1043// Check whether B-Start is known to be a multiple of StepOffset. 1045if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1050// AR may wrap. Add PN >= StartValue conditional on StartValue <= B which 1051// guarantees that the loop exits before wrapping in combination with the 1052// restrictions on B and the step above. 1053if (!MonotonicallyIncreasingUnsigned)
1054 WorkList.
push_back(FactOrCheck::getConditionFact(
1057if (!MonotonicallyIncreasingSigned)
1058 WorkList.
push_back(FactOrCheck::getConditionFact(
1062 WorkList.
push_back(FactOrCheck::getConditionFact(
1065 WorkList.
push_back(FactOrCheck::getConditionFact(
1069// Try to add condition from header to the dedicated exit blocks. When exiting 1070// either with EQ or NE in the header, we know that the induction value must 1071// be u<= B, as other exits may only exit earlier. 1074"unsupported predicate");
1077L->getExitBlocks(ExitBBs);
1079// Bail out on non-dedicated exits. 1088 addInfoForInductions(BB);
1090// True as long as long as the current instruction is guaranteed to execute. 1091bool GuaranteedToExecute =
true;
1092// Queue conditions and assumes. 1094if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
1095for (
Use &U :
Cmp->uses()) {
1097auto *DTN = DT.
getNode(UserI->getParent());
1100 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
1105auto *
II = dyn_cast<IntrinsicInst>(&
I);
1108case Intrinsic::assume: {
1113if (GuaranteedToExecute) {
1114// The assume is guaranteed to execute when BB is entered, hence Cond 1115// holds on entry to BB. 1120 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1124// Enqueue ssub_with_overflow for simplification. 1125case Intrinsic::ssub_with_overflow:
1126case Intrinsic::ucmp:
1127case Intrinsic::scmp:
1129 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1131// Enqueue the intrinsics to add extra info. 1132case Intrinsic::umin:
1133case Intrinsic::umax:
1134case Intrinsic::smin:
1135case Intrinsic::smax:
1136// TODO: handle llvm.abs as well 1138 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1139// TODO: Check if it is possible to instead only added the min/max facts 1140// when simplifying uses of the min/max intrinsics. 1152if (
auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1153for (
auto &Case :
Switch->cases()) {
1155Value *
V = Case.getCaseValue();
1156if (!canAddSuccessor(BB, Succ))
1164auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
1165if (!Br || !Br->isConditional())
1170// If the condition is a chain of ORs/AND and the successor only has the 1171// current block as predecessor, queue conditions for the successor. 1177// If there's a select that matches both AND and OR, we need to commit to 1178// one of the options. Arbitrarily pick OR. 1186auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1187if (SeenCond.
insert(V).second)
1192while (!CondWorkList.
empty()) {
1194if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1197 IsOr ?
Cmp->getInverseCmpPredicate() :
Cmp->getCmpPredicate(),
1198Cmp->getOperand(0),
Cmp->getOperand(1)));
1216auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1219if (canAddSuccessor(BB, Br->getSuccessor(0)))
1221 DT.
getNode(Br->getSuccessor(0)), CmpI->getCmpPredicate(),
1222 CmpI->getOperand(0), CmpI->getOperand(1)));
1223if (canAddSuccessor(BB, Br->getSuccessor(1)))
1225 DT.
getNode(Br->getSuccessor(1)), CmpI->getInverseCmpPredicate(),
1226 CmpI->getOperand(0), CmpI->getOperand(1)));
1232OS <<
"icmp " << Pred <<
' ';
1240/// Helper to keep track of a condition and if it should be treated as negated 1241/// for reproducer construction. 1242/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a 1243/// placeholder to keep the ReproducerCondStack in sync with DFSInStack. 1244structReproducerEntry {
1254/// Helper function to generate a reproducer function for simplifying \p Cond. 1255/// The reproducer function contains a series of @llvm.assume calls, one for 1256/// each condition in \p Stack. For each condition, the operand instruction are 1257/// cloned until we reach operands that have an entry in \p Value2Index. Those 1258/// will then be added as function arguments. \p DT is used to order cloned 1259/// instructions. The reproducer function will get added to \p M, if it is 1260/// non-null. Otherwise no reproducer function is generated. 1274// Traverse Cond and its operands recursively until we reach a value that's in 1275// Value2Index or not an instruction, or not a operation that 1276// ConstraintElimination can decompose. Such values will be considered as 1277// external inputs to the reproducer, they are collected and added as function 1280auto &Value2Index =
Info.getValue2Index(IsSigned);
1282while (!WorkList.
empty()) {
1284if (!Seen.
insert(V).second)
1286if (Old2New.
find(V) != Old2New.
end())
1288if (isa<Constant>(V))
1291auto *
I = dyn_cast<Instruction>(V);
1292if (Value2Index.contains(V) || !
I ||
1293 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1303for (
auto &Entry : Stack)
1304if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1305 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1306 CollectArguments(
Cond, ICmpInst::isSigned(
Cond->getPredicate()));
1315Cond->getModule()->getName() +
1316Cond->getFunction()->getName() +
"repro",
1318// Add arguments to the reproducer function for each external value collected. 1319for (
unsignedI = 0;
I < Args.size(); ++
I) {
1321 Old2New[Args[
I]] =
F->getArg(
I);
1329// Clone instructions in \p Ops and their operands recursively until reaching 1330// an value in Value2Index (external input to the reproducer). Update Old2New 1331// mapping for the original and cloned instructions. Sort instructions to 1332// clone by dominance, then insert the cloned instructions in the function. 1336auto &Value2Index =
Info.getValue2Index(IsSigned);
1337while (!WorkList.
empty()) {
1339if (Old2New.
find(V) != Old2New.
end())
1342auto *
I = dyn_cast<Instruction>(V);
1343if (!Value2Index.contains(V) &&
I) {
1344 Old2New[V] =
nullptr;
1354 Old2New[
I] = Cloned;
1355 Old2New[
I]->setName(
I->getName());
1362// Materialize the assumptions for the reproducer using the entries in Stack. 1363// That is, first clone the operands of the condition recursively until we 1364// reach an external input to the reproducer and add them to the reproducer 1365// function. Then add an ICmp for the condition (with the inverse predicate if 1366// the entry is negated) and an assert using the ICmp. 1367for (
auto &Entry : Stack) {
1368if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1376auto *Cmp = Builder.
CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1380// Finally, clone the condition to reproduce and remap instruction operands in 1381// the reproducer using Old2New. 1383 Entry->getTerminator()->setOperand(0,
Cond);
1391 ConstraintInfo &Info) {
1394auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1395if (R.empty() || !R.isValid(
Info)){
1400auto &CSToUse =
Info.getCS(R.IsSigned);
1402// If there was extra information collected during decomposition, apply 1403// it now and remove it immediately once we are done with reasoning 1404// about the constraint. 1405for (
auto &Row : R.ExtraInfo)
1406 CSToUse.addVariableRow(Row);
1408for (
unsignedI = 0;
I < R.ExtraInfo.size(); ++
I)
1409 CSToUse.popLastConstraint();
1412if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1417dbgs() <<
"Condition ";
1421dbgs() <<
" implied by dominating constraints\n";
1424return ImpliedCondition;
1431CmpInst *Cmp, ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
1435auto ReplaceCmpWithConstant = [&](
CmpInst *Cmp,
bool IsTrue) {
1439 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1440 ContextInst](
Use &U) {
1442auto *DTN = DT.
getNode(UserI->getParent());
1445if (UserI->getParent() == ContextInst->
getParent() &&
1446 UserI->comesBefore(ContextInst))
1449// Conditions in an assume trivially simplify to true. Skip uses 1450// in assume calls to not destroy the available information. 1451auto *
II = dyn_cast<IntrinsicInst>(U.getUser());
1452return !
II ||
II->getIntrinsicID() != Intrinsic::assume;
1455if (Cmp->use_empty())
1460if (
auto ImpliedCondition =
1462 Cmp->getOperand(1), Cmp,
Info))
1463return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1470// TODO: generate reproducer for min/max. 1471MinMax->replaceAllUsesWith(
MinMax->getOperand(UseLHS ? 0 : 1));
1477 ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1480return ReplaceMinMaxWithOperand(
MinMax, *ImpliedCondition);
1483return ReplaceMinMaxWithOperand(
MinMax, !*ImpliedCondition);
1492I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 1));
1502I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 0));
1514Info.popLastConstraint(E.IsSigned);
1515// Remove variables in the system that went out of scope. 1516auto &Mapping =
Info.getValue2Index(E.IsSigned);
1517for (
Value *V : E.ValuesToRelease)
1519Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1521if (ReproducerModule)
1525/// Check if either the first condition of an AND or OR is implied by the 1526/// (negated in case of OR) second condition or vice versa. 1528 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
1532CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
1533unsigned OtherOpIdx = JoinOp->
getOperand(0) == CmpToCheck ? 1 : 0;
1535// Don't try to simplify the first condition of a select by the second, as 1536// this may make the select more poisonous than the original one. 1537// TODO: check if the first operand may be poison. 1538if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
1541unsigned OldSize = DFSInStack.
size();
1543// Remove entries again. 1544while (OldSize < DFSInStack.
size()) {
1545 StackEntry E = DFSInStack.back();
1546 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
1552// Do a traversal of the AND/OR tree to add facts from leaf compares. 1553while (!Worklist.empty()) {
1554Value *Val = Worklist.pop_back_val();
1558// For OR, check if the negated condition implies CmpToCheck. 1561// Optimistically add fact from the other compares in the AND/OR. 1562Info.addFact(Pred,
LHS,
RHS, CB.NumIn, CB.NumOut, DFSInStack);
1567 Worklist.push_back(
LHS);
1568 Worklist.push_back(
RHS);
1571if (OldSize == DFSInStack.
size())
1574// Check if the second condition can be simplified now. 1575if (
auto ImpliedCondition =
1578if (IsOr && isa<SelectInst>(JoinOp)) {
1580 OtherOpIdx == 0 ? 2 : 0,
1594unsigned NumIn,
unsigned NumOut,
1596 addFactImpl(Pred,
A,
B, NumIn, NumOut, DFSInStack,
false);
1597// If the Pred is eq/ne, also add the fact to signed system. 1599 addFactImpl(Pred,
A,
B, NumIn, NumOut, DFSInStack,
true);
1603unsigned NumIn,
unsigned NumOut,
1605bool ForceSignedSystem) {
1606// If the constraint has a pre-condition, skip the constraint if it does not 1609autoR = getConstraint(Pred,
A,
B, NewVariables, ForceSignedSystem);
1611// TODO: Support non-equality for facts as well. 1612if (!
R.isValid(*
this) ||
R.isNe())
1617auto &CSToUse = getCS(
R.IsSigned);
1618if (
R.Coefficients.empty())
1621boolAdded = CSToUse.addVariableRowFill(
R.Coefficients);
1625// If R has been added to the system, add the new variables and queue it for 1626// removal once it goes out-of-scope. 1628auto &Value2Index = getValue2Index(
R.IsSigned);
1629for (
Value *V : NewVariables) {
1630 Value2Index.insert({
V, Value2Index.size() + 1});
1635dbgs() <<
" constraint: ";
1641 std::move(ValuesToRelease));
1644for (
Value *V : NewVariables) {
1647 VarPos.Coefficients[Value2Index[
V]] = -1;
1648 CSToUse.addVariableRow(VarPos.Coefficients);
1655// Also add the inverted constraint for equality constraints. 1656for (
auto &Coeff :
R.Coefficients)
1658 CSToUse.addVariableRowFill(
R.Coefficients);
1674 U->replaceAllUsesWith(Sub);
1677 U->replaceAllUsesWith(Builder.
getFalse());
1682if (U->use_empty()) {
1683auto *
I = cast<Instruction>(U);
1690if (
II->use_empty()) {
1691II->eraseFromParent();
1701 ConstraintInfo &
Info) {
1702auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1703if (R.size() < 2 || !R.isValid(
Info))
1706auto &CSToUse =
Info.getCS(R.IsSigned);
1707return CSToUse.isConditionImplied(R.Coefficients);
1711if (
II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
1712// If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and 1713// can be simplified to a regular sub. 1718 ConstantInt::get(
A->getType(), 0),
Info))
1731for (
Value &Arg :
F.args())
1733 ConstraintInfo
Info(
F.getDataLayout(), FunctionArgs);
1734 State S(DT, LI, SE);
1735 std::unique_ptr<Module> ReproducerModule(
1738// First, collect conditions implied by branches and blocks with their 1739// Dominator DFS in and out numbers. 1746// Next, sort worklist by dominance, so that dominating conditions to check 1747// and facts come before conditions and facts dominated by them. If a 1748// condition to check and a fact have the same numbers, conditional facts come 1749// first. Assume facts and checks are ordered according to their relative 1750// order in the containing basic block. Also make sure conditions with 1751// constant operands come before conditions without constant operands. This 1752// increases the effectiveness of the current signed <-> unsigned fact 1754stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1755 auto HasNoConstOp = [](const FactOrCheck &B) {
1756 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1757 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1758 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1760// If both entries have the same In numbers, conditional facts come first. 1761// Otherwise use the relative order in the basic block. 1762if (
A.NumIn ==
B.NumIn) {
1763 if (A.isConditionFact() && B.isConditionFact()) {
1764 bool NoConstOpA = HasNoConstOp(A);
1765 bool NoConstOpB = HasNoConstOp(B);
1766 return NoConstOpA < NoConstOpB;
1768if (
A.isConditionFact())
1770if (
B.isConditionFact())
1772auto *InstA =
A.getContextInst();
1773auto *InstB =
B.getContextInst();
1774return InstA->comesBefore(InstB);
1776returnA.NumIn <
B.NumIn;
1781// Finally, process ordered worklist and eliminate implied conditions. 1784for (FactOrCheck &CB : S.WorkList) {
1785// First, pop entries from the stack that are out-of-scope for CB. Remove 1786// the corresponding entry from the constraint system. 1787while (!DFSInStack.
empty()) {
1788auto &E = DFSInStack.
back();
1789LLVM_DEBUG(
dbgs() <<
"Top of stack : " << E.NumIn <<
" " << E.NumOut
1791LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1792assert(E.NumIn <= CB.NumIn);
1793if (CB.NumOut <= E.NumOut)
1796dbgs() <<
"Removing ";
1798Info.getValue2Index(E.IsSigned));
1805// For a block, check if any CmpInsts become known based on the current set 1813if (
auto *
II = dyn_cast<WithOverflowInst>(Inst)) {
1815 }
elseif (
auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1817 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1818 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
1823 ReproducerCondStack, DFSInStack);
1826 }
elseif (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1828 }
elseif (
auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {
1840 <<
"Skip adding constraint because system has too many rows.\n");
1844Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1845if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1849// If samesign is present on the ICmp, simply flip the sign of the 1850// predicate, transferring the information from the signed system to the 1851// unsigned system, and viceversa. 1854 CB.NumIn, CB.NumOut, DFSInStack);
1856Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut,
1860if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1861// Add dummy entries to ReproducerCondStack to keep it in sync with 1864 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1866 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
1873if (!CB.isConditionFact()) {
1875if (
match(CB.Inst, m_Intrinsic<Intrinsic::abs>(
m_Value(
X)))) {
1876// If is_int_min_poison is true then we may assume llvm.abs >= 0. 1877if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1879 ConstantInt::get(CB.Inst->getType(), 0));
1884if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1885 Pred = ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1892Value *
A =
nullptr, *
B =
nullptr;
1893if (CB.isConditionFact()) {
1894 Pred = CB.Cond.Pred;
1898 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
1900dbgs() <<
"Not adding fact ";
1902dbgs() <<
" because precondition ";
1905dbgs() <<
" does not hold.\n";
1910bool Matched =
match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1913assert(Matched &&
"Must have an assume intrinsic with a icmp operand");
1918if (ReproducerModule && !ReproducerModule->functions().empty()) {
1921 ReproducerModule->print(StringS,
nullptr);
1928unsigned SignedEntries =
1929count_if(DFSInStack, [](
const StackEntry &E) {
return E.IsSigned; });
1930assert(
Info.getCS(
false).size() - FunctionArgs.size() ==
1931 DFSInStack.
size() - SignedEntries &&
1932"updates to CS and DFSInStack are out of sync");
1933assert(
Info.getCS(
true).size() == SignedEntries &&
1934"updates to CS and DFSInStack are out of sync");
1938I->eraseFromParent();
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
std::pair< ICmpInst *, unsigned > ConditionTy
static int64_t MaxConstraintValue
static int64_t MinSignedConstraintValue
static Instruction * getContextInstForUse(Use &U)
static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
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 void removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
static std::optional< bool > checkCondition(CmpInst::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info)
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 bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE)
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 OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL)
static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
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 void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
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 ...
static Decomposition decompose(Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
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 checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
std::optional< std::vector< StOtherPiece > > Other
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is the interface for a simple mod/ref and alias analysis over globals.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
static StringRef getName(Value *V)
const SmallVectorImpl< MachineOperand > & Cond
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 contains some templates that are useful if you are working with the STL at all.
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 isZero() const
Determine if this value is zero, i.e. all bits are clear.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
bool isNegative() const
Determine sign of this APInt.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
bool slt(const APInt &RHS) const
Signed less than comparison.
bool isOne() const
Determine if this is a value of 1.
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.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
bool isEquality() const
Determine if this is an equals/not equals predicate.
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 getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
This class represents a ucmp/scmp intrinsic.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
bool hasSameSign() const
Query samesign information, for optimizations.
This is the shared class of boolean and integer constants.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
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.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This is an important base class in LLVM.
static Constant * getAllOnesValue(Type *Ty)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)
Converts the given vector to form a strict less than inequality.
bool addVariableRow(ArrayRef< int64_t > R)
static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)
Multiplies each coefficient in the given vector by -1.
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)
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
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)
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags none()
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles={})
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
ConstantInt * getTrue()
Get the constant value for i1 true.
BasicBlock::iterator GetInsertPoint() const
ReturnInst * CreateRet(Value *V)
Create a 'ret <val>' instruction.
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
ConstantInt * getFalse()
Get the constant value for i1 false.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
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.
void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
The optimization diagnostic interface.
Diagnostic information for applied optimization remarks.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
unsigned getNumIncomingValues() const
Return the number of incoming edges.
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.
This class represents an analyzed expression in the program.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
@ MonotonicallyIncreasing
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
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.
unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
iterator find(const KeyT &Val)
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
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)
auto m_LogicalOp()
Matches either L && R or L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
NoWrapTrunc_match< OpTy, TruncInst::NoSignedWrap > m_NSWTrunc(const OpTy &Op)
Matches trunc nsw.
NNegZExt_match< OpTy > m_NNegZExt(const OpTy &Op)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
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)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
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)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
std::enable_if_t< std::is_signed_v< T >, 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 stable_sort(R &&Range)
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 range R to container C.
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...
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
constexpr unsigned MaxAnalysisRecursionDepth
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
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_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
bool isGuaranteedNotToBePoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Returns true if V cannot be poison, but may be undef.
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A MapVector that performs no allocations if smaller than a certain size.
