49using namespace PatternMatch;
51#define DEBUG_TYPE "constraint-elimination"
53STATISTIC(NumCondsRemoved,
"Number of instructions removed");
55 "Controls which conditions are eliminated");
59 cl::desc(
"Maximum number of rows to keep in constraint system"));
63 cl::desc(
"Dump IR to reproduce successful transformations."));
83 Instruction *UserI = cast<Instruction>(U.getUser());
84 if (
auto *Phi = dyn_cast<PHINode>(UserI))
85 UserI = Phi->getIncomingBlock(U)->getTerminator();
97 : Pred(
CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {}
99 : Pred(Pred), Op0(Op0), Op1(Op1) {}
132 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
136 :
U(
U), DoesHold(
CmpInst::BAD_ICMP_PREDICATE, nullptr, nullptr),
137 NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
138 Ty(EntryTy::UseCheck) {}
142 :
Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
143 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
148 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
152 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
156 return FactOrCheck(DTN, U);
160 return FactOrCheck(EntryTy::InstCheck, DTN, CI);
163 bool isCheck()
const {
164 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
168 if (Ty == EntryTy::UseCheck)
175 if (Ty == EntryTy::InstCheck)
178 return dyn_cast<Instruction>(*U);
181 bool isConditionFact()
const {
return Ty == EntryTy::ConditionFact; }
192 : DT(DT), LI(LI), SE(SE) {}
213 bool IsSigned =
false;
218 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
220 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
221 ValuesToRelease(ValuesToRelease) {}
230 bool IsSigned =
false;
232 ConstraintTy() =
default;
236 : Coefficients(Coefficients), IsSigned(IsSigned), IsEq(IsEq), IsNe(IsNe) {
239 unsigned size()
const {
return Coefficients.
size(); }
241 unsigned empty()
const {
return Coefficients.
empty(); }
245 bool isValid(
const ConstraintInfo &Info)
const;
247 bool isEq()
const {
return IsEq; }
249 bool isNe()
const {
return IsNe; }
269class ConstraintInfo {
278 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs),
DL(
DL) {}
288 return Signed ? SignedCS : UnsignedCS;
291 return Signed ? SignedCS : UnsignedCS;
295 void popLastNVariables(
bool Signed,
unsigned N) {
296 getCS(
Signed).popLastNVariables(
N);
324 unsigned NumIn,
unsigned NumOut,
333 bool IsKnownNonNegative;
335 DecompEntry(int64_t Coefficient,
Value *Variable,
336 bool IsKnownNonNegative =
false)
337 : Coefficient(Coefficient), Variable(Variable),
338 IsKnownNonNegative(IsKnownNonNegative) {}
342struct Decomposition {
347 Decomposition(
Value *V,
bool IsKnownNonNegative =
false) {
353 void add(int64_t OtherOffset) {
357 void add(
const Decomposition &
Other) {
362 void mul(int64_t Factor) {
364 for (
auto &Var : Vars)
385 if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
388 if (!
GEP.isInBounds())
391 assert(!IsSigned &&
"The logic below only supports decomposition for "
392 "unsinged predicates at the moment.");
393 Type *PtrTy =
GEP.getType()->getScalarType();
394 unsigned BitWidth =
DL.getIndexTypeSizeInBits(PtrTy);
397 if (!
GEP.collectOffset(
DL,
BitWidth, VariableOffsets, ConstantOffset))
402 auto *InnerGEP = dyn_cast<GEPOperator>(
GEP.getPointerOperand());
403 if (VariableOffsets.
empty() && InnerGEP && InnerGEP->getNumOperands() == 2) {
404 auto Result =
decompose(InnerGEP, Preconditions, IsSigned,
DL);
408 unsigned Scale =
DL.getTypeAllocSize(InnerGEP->getResultElementType());
409 int64_t ConstantOffsetI = ConstantOffset.
getSExtValue();
410 if (ConstantOffsetI % Scale != 0)
418 -1 * (ConstantOffsetI / Scale)));
424 DecompEntry(1,
GEP.getPointerOperand()));
425 for (
auto [
Index, Scale] : VariableOffsets) {
427 IdxResult.mul(Scale.getSExtValue());
428 Result.add(IdxResult);
446 auto MergeResults = [&Preconditions, IsSigned, &
DL](
Value *
A,
Value *
B,
456 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
458 return CI->getSExtValue();
463 return MergeResults(Op0, Op1, IsSigned);
467 auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
475 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
478 return int64_t(CI->getZExtValue());
481 if (
auto *
GEP = dyn_cast<GEPOperator>(V))
485 bool IsKnownNonNegative =
false;
487 IsKnownNonNegative =
true;
494 return MergeResults(Op0, Op1, IsSigned);
504 return MergeResults(Op0, Op1, IsSigned);
512 return MergeResults(Op0, CI,
true);
518 return MergeResults(Op0, CI, IsSigned);
523 return {V, IsKnownNonNegative};
524 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
531 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
539 return {0, {{1, Op0}, {-1, Op1}}};
541 return {V, IsKnownNonNegative};
547 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
588 auto &Value2Index = getValue2Index(IsSigned);
590 Preconditions, IsSigned,
DL);
592 Preconditions, IsSigned,
DL);
593 int64_t Offset1 = ADec.Offset;
594 int64_t Offset2 = BDec.Offset;
597 auto &VariablesA = ADec.Vars;
598 auto &VariablesB = BDec.Vars;
603 auto GetOrAddIndex = [&Value2Index, &NewVariables,
604 &NewIndexMap](
Value *
V) ->
unsigned {
605 auto V2I = Value2Index.
find(V);
606 if (V2I != Value2Index.end())
609 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
611 NewVariables.push_back(V);
612 return Insert.first->second;
616 for (
const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
617 GetOrAddIndex(KV.Variable);
623 IsSigned, IsEq, IsNe);
627 auto &
R = Res.Coefficients;
628 for (
const auto &KV : VariablesA) {
629 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
631 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
632 I.first->second &= KV.IsKnownNonNegative;
635 for (
const auto &KV : VariablesB) {
636 if (
SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
637 R[GetOrAddIndex(KV.Variable)]))
640 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
641 I.first->second &= KV.IsKnownNonNegative;
648 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
651 Res.Preconditions = std::move(Preconditions);
655 while (!NewVariables.empty()) {
656 int64_t
Last =
R.back();
660 Value *RemovedV = NewVariables.pop_back_val();
661 NewIndexMap.
erase(RemovedV);
665 for (
auto &KV : KnownNonNegativeVariables) {
667 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
670 C[GetOrAddIndex(KV.first)] = -1;
671 Res.ExtraInfo.push_back(
C);
684 auto &Value2Index = getValue2Index(
false);
699 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
700 if (!NewVariables.
empty())
705bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const {
706 return Coefficients.
size() > 0 &&
707 all_of(Preconditions, [&Info](
const ConditionTy &
C) {
708 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
718 bool IsNegatedOrEqualImplied =
724 if (IsConditionImplied && IsNegatedOrEqualImplied)
731 bool IsStrictLessThanImplied =
738 if (IsNegatedImplied || IsStrictLessThanImplied)
744 if (IsConditionImplied)
749 if (IsNegatedImplied)
758 auto R = getConstraintForSolving(Pred,
A,
B);
759 return R.isValid(*
this) &&
760 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
763void ConstraintInfo::transferToOtherSystem(
768 if (!
A->getType()->isIntegerTy())
827void State::addInfoForInductions(
BasicBlock &BB) {
829 if (!L ||
L->getHeader() != &BB)
843 PN = dyn_cast<PHINode>(
A);
852 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(0);
854 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(1);
858 if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB) || InLoopSucc == &BB)
861 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.
getSCEV(PN));
863 if (!AR || !LoopPred)
866 const SCEV *StartSCEV = AR->getStart();
867 Value *StartValue =
nullptr;
868 if (
auto *
C = dyn_cast<SCEVConstant>(StartSCEV)) {
869 StartValue =
C->getValue();
872 assert(SE.
getSCEV(StartValue) == StartSCEV &&
"inconsistent start value");
877 bool MonotonicallyIncreasing =
879 if (MonotonicallyIncreasing) {
887 if (
auto *
C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
888 StepOffset =
C->getAPInt();
898 if (!StepOffset.
isOne()) {
899 auto *UpperGEP = dyn_cast<GetElementPtrInst>(
B);
900 if (!UpperGEP || UpperGEP->getPointerOperand() != StartValue ||
901 !UpperGEP->isInBounds())
908 UpperVariableOffsets, UpperConstantOffset))
912 if (!UpperConstantOffset.urem(StepOffset).isZero() ||
913 any_of(UpperVariableOffsets, [&StepOffset](
const auto &
P) {
914 return !
P.second.urem(StepOffset).
isZero();
922 if (!MonotonicallyIncreasing) {
923 WorkList.
push_back(FactOrCheck::getConditionFact(
927 WorkList.
push_back(FactOrCheck::getConditionFact(
933 addInfoForInductions(BB);
936 bool GuaranteedToExecute =
true;
939 if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
940 for (
Use &U :
Cmp->uses()) {
942 auto *DTN = DT.
getNode(UserI->getParent());
945 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
950 if (
match(&
I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
952 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
956 if (isa<MinMaxIntrinsic>(&
I)) {
964 if (
match(&
I, m_Intrinsic<Intrinsic::assume>(
966 if (GuaranteedToExecute) {
973 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
979 if (
auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
980 for (
auto &Case :
Switch->cases()) {
982 Value *
V = Case.getCaseValue();
983 if (!canAddSuccessor(BB, Succ))
991 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
992 if (!Br || !Br->isConditional())
1013 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1014 if (SeenCond.
insert(V).second)
1019 while (!CondWorkList.
empty()) {
1021 if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1025 :
Cmp->getPredicate(),
1026 Cmp->getOperand(0),
Cmp->getOperand(1)));
1044 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1047 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1049 DT.
getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1050 CmpI->getOperand(0), CmpI->getOperand(1)));
1051 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1053 DT.
getNode(Br->getSuccessor(1)),
1055 CmpI->getOperand(1)));
1063struct ReproducerEntry {
1099 auto &Value2Index =
Info.getValue2Index(IsSigned);
1101 while (!WorkList.
empty()) {
1103 if (!Seen.
insert(V).second)
1105 if (Old2New.
find(V) != Old2New.
end())
1107 if (isa<Constant>(V))
1110 auto *
I = dyn_cast<Instruction>(V);
1111 if (Value2Index.contains(V) || !
I ||
1112 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1122 for (
auto &Entry : Stack)
1123 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1124 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1125 CollectArguments(
Cond, ICmpInst::isSigned(
Cond->getPredicate()));
1128 for (
auto *
P : Args)
1134 Cond->getModule()->getName() +
1135 Cond->getFunction()->getName() +
"repro",
1138 for (
unsigned I = 0;
I < Args.size(); ++
I) {
1140 Old2New[Args[
I]] =
F->getArg(
I);
1146 Builder.SetInsertPoint(Entry->getTerminator());
1155 auto &Value2Index =
Info.getValue2Index(IsSigned);
1156 while (!WorkList.
empty()) {
1158 if (Old2New.
find(V) != Old2New.
end())
1161 auto *
I = dyn_cast<Instruction>(V);
1162 if (!Value2Index.contains(V) &&
I) {
1163 Old2New[V] =
nullptr;
1173 Old2New[
I] = Cloned;
1174 Old2New[
I]->setName(
I->getName());
1186 for (
auto &Entry : Stack) {
1187 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1191 dbgs() <<
" Materializing assumption icmp " << Entry.Pred <<
' ';
1192 Entry.LHS->printAsOperand(
dbgs(),
true);
dbgs() <<
", ";
1193 Entry.RHS->printAsOperand(
dbgs(),
false);
dbgs() <<
"\n");
1196 auto *Cmp =
Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1197 Builder.CreateAssumption(Cmp);
1203 Entry->getTerminator()->setOperand(0,
Cond);
1210 unsigned NumIn,
unsigned NumOut,
1215 Value *
A = Cmp->getOperand(0);
1216 Value *
B = Cmp->getOperand(1);
1218 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1219 if (R.empty() || !R.isValid(
Info)){
1221 return std::nullopt;
1224 auto &CSToUse =
Info.getCS(R.IsSigned);
1229 for (
auto &Row : R.ExtraInfo)
1230 CSToUse.addVariableRow(Row);
1232 for (
unsigned I = 0;
I < R.ExtraInfo.size(); ++
I)
1233 CSToUse.popLastConstraint();
1236 if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1238 return std::nullopt;
1241 if (*ImpliedCondition) {
1242 dbgs() <<
"Condition " << *Cmp;
1244 auto InversePred = Cmp->getInversePredicate();
1246 << *
A <<
", " << *
B;
1248 dbgs() <<
" implied by dominating constraints\n";
1251 return ImpliedCondition;
1254 return std::nullopt;
1258 CmpInst *Cmp, ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
1262 auto ReplaceCmpWithConstant = [&](
CmpInst *Cmp,
bool IsTrue) {
1266 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1267 ContextInst](
Use &U) {
1269 auto *DTN = DT.
getNode(UserI->getParent());
1272 if (UserI->getParent() == ContextInst->
getParent() &&
1273 UserI->comesBefore(ContextInst))
1278 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
1279 return !II || II->getIntrinsicID() != Intrinsic::assume;
1282 if (Cmp->use_empty())
1287 if (
auto ImpliedCondition =
1289 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1295 Module *ReproducerModule,
1298 Info.popLastConstraint(
E.IsSigned);
1300 auto &Mapping =
Info.getValue2Index(
E.IsSigned);
1301 for (
Value *V :
E.ValuesToRelease)
1303 Info.popLastNVariables(
E.IsSigned,
E.ValuesToRelease.size());
1305 if (ReproducerModule)
1311 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
1322 unsigned OldSize = DFSInStack.
size();
1323 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1324 if (OldSize == DFSInStack.
size())
1327 bool Changed =
false;
1329 if (
auto ImpliedCondition =
1331 CB.NumOut, CB.getContextInst())) {
1337 while (OldSize < DFSInStack.
size()) {
1338 StackEntry
E = DFSInStack.
back();
1346 unsigned NumIn,
unsigned NumOut,
1351 auto R = getConstraint(Pred,
A,
B, NewVariables);
1354 if (!
R.isValid(*
this) ||
R.isNe())
1358 A->printAsOperand(
dbgs(),
false);
dbgs() <<
", ";
1359 B->printAsOperand(
dbgs(),
false);
dbgs() <<
"'\n");
1361 auto &CSToUse = getCS(
R.IsSigned);
1362 if (
R.Coefficients.empty())
1365 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
1371 auto &Value2Index = getValue2Index(
R.IsSigned);
1372 for (
Value *V : NewVariables) {
1373 Value2Index.insert({
V, Value2Index.size() + 1});
1378 dbgs() <<
" constraint: ";
1384 std::move(ValuesToRelease));
1388 for (
auto &Coeff :
R.Coefficients)
1390 CSToUse.addVariableRowFill(
R.Coefficients);
1400 bool Changed =
false;
1402 Value *Sub =
nullptr;
1407 U->replaceAllUsesWith(Sub);
1410 U->replaceAllUsesWith(
Builder.getFalse());
1415 if (U->use_empty()) {
1416 auto *
I = cast<Instruction>(U);
1434 ConstraintInfo &
Info) {
1435 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1436 if (R.size() < 2 || !R.isValid(
Info))
1439 auto &CSToUse =
Info.getCS(R.IsSigned);
1440 return CSToUse.isConditionImplied(R.Coefficients);
1443 bool Changed =
false;
1461 bool Changed =
false;
1464 for (
Value &Arg :
F.args())
1466 ConstraintInfo
Info(
F.getParent()->getDataLayout(), FunctionArgs);
1467 State S(DT, LI, SE);
1468 std::unique_ptr<Module> ReproducerModule(
1487 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1488 auto HasNoConstOp = [](const FactOrCheck &B) {
1489 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1490 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1491 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1495 if (
A.NumIn ==
B.NumIn) {
1496 if (A.isConditionFact() && B.isConditionFact()) {
1497 bool NoConstOpA = HasNoConstOp(A);
1498 bool NoConstOpB = HasNoConstOp(B);
1499 return NoConstOpA < NoConstOpB;
1501 if (
A.isConditionFact())
1503 if (
B.isConditionFact())
1505 auto *InstA =
A.getContextInst();
1506 auto *InstB =
B.getContextInst();
1507 return InstA->comesBefore(InstB);
1509 return A.NumIn <
B.NumIn;
1517 for (FactOrCheck &CB : S.WorkList) {
1520 while (!DFSInStack.
empty()) {
1521 auto &
E = DFSInStack.
back();
1524 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1526 if (CB.NumOut <=
E.NumOut)
1529 dbgs() <<
"Removing ";
1531 Info.getValue2Index(
E.IsSigned));
1543 Instruction *Inst = CB.getInstructionToSimplify();
1546 LLVM_DEBUG(
dbgs() <<
"condition to simplify: " << *Inst <<
"\n");
1547 if (
auto *II = dyn_cast<WithOverflowInst>(Inst)) {
1549 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1551 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1552 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
1553 if (!Simplified &&
match(CB.getContextInst(),
1557 ReproducerCondStack, DFSInStack);
1567 A->printAsOperand(
dbgs());
dbgs() <<
", ";
1568 B->printAsOperand(
dbgs());
dbgs() <<
"\n");
1572 <<
"Skip adding constraint because system has too many rows.\n");
1577 dbgs() <<
"Processing fact to add to the system: " << Pred <<
" ";
1578 A->printAsOperand(
dbgs());
1580 B->printAsOperand(
dbgs(),
false);
1584 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1585 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1588 Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1589 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1592 for (
unsigned I = 0,
1593 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1595 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
1602 if (!CB.isConditionFact()) {
1603 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1604 Pred = ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1611 Value *
A =
nullptr, *
B =
nullptr;
1612 if (CB.isConditionFact()) {
1613 Pred = CB.Cond.Pred;
1617 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1))
1620 bool Matched =
match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1623 assert(Matched &&
"Must have an assume intrinsic with a icmp operand");
1625 AddFact(Pred,
A,
B);
1628 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1631 ReproducerModule->print(StringS,
nullptr);
1634 Rem <<
ore::NV(
"module") << S;
1639 unsigned SignedEntries =
1640 count_if(DFSInStack, [](
const StackEntry &
E) {
return E.IsSigned; });
1641 assert(
Info.getCS(
false).size() == DFSInStack.
size() - SignedEntries &&
1642 "updates to CS and DFSInStack are out of sync");
1643 assert(
Info.getCS(
true).size() == SignedEntries &&
1644 "updates to CS and DFSInStack are out of sync");
1648 I->eraseFromParent();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
ReachingDefAnalysis InstSet & ToRemove
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
std::pair< ICmpInst *, unsigned > ConditionTy
static int64_t MaxConstraintValue
static int64_t MinSignedConstraintValue
static Instruction * getContextInstForUse(Use &U)
static bool checkAndSecondOpImpliedByFirst(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
Check if the first condition for an AND implies the second.
static 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 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 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< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static std::optional< bool > checkCondition(CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst)
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)
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 bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
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 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.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool isNegative() const
Determine sign of this APInt.
bool slt(const APInt &RHS) const
Signed less than comparison.
bool isOne() const
Determine if this is a value of 1.
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.
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...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Represents analyses that only rely on functions' control flow.
Value * getArgOperand(unsigned i) const
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.
Predicate getSignedPredicate()
For example, ULT->SLT, ULE->SLE, UGT->SGT, UGE->SGE, SLT->Failed assert.
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,...
static StringRef getPredicateName(Predicate P)
This is the shared class of boolean and integer constants.
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.
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 * 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.
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)
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.
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 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.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
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.
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
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.
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)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
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)
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)
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.
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 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...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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.
@ And
Bitwise or logical AND of integers.
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_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...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.