47using namespace PatternMatch;
49#define DEBUG_TYPE "constraint-elimination"
51STATISTIC(NumCondsRemoved,
"Number of instructions removed");
53 "Controls which conditions are eliminated");
57 cl::desc(
"Maximum number of rows to keep in constraint system"));
61 cl::desc(
"Dump IR to reproduce successful transformations."));
81 Instruction *UserI = cast<Instruction>(U.getUser());
82 if (
auto *Phi = dyn_cast<PHINode>(UserI))
83 UserI = Phi->getIncomingBlock(U)->getTerminator();
95 : Pred(
CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {}
97 : Pred(Pred), Op0(Op0), Op1(Op1) {}
130 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
134 :
U(
U), DoesHold(
CmpInst::BAD_ICMP_PREDICATE, nullptr, nullptr),
135 NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
136 Ty(EntryTy::UseCheck) {}
140 :
Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
141 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
146 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
150 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
154 return FactOrCheck(DTN, U);
158 return FactOrCheck(EntryTy::InstCheck, DTN, CI);
161 bool isCheck()
const {
162 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
166 if (Ty == EntryTy::UseCheck)
173 if (Ty == EntryTy::InstCheck)
176 return dyn_cast<Instruction>(*U);
179 bool isConditionFact()
const {
return Ty == EntryTy::ConditionFact; }
190 : DT(DT), LI(LI), SE(SE) {}
211 bool IsSigned =
false;
216 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
218 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
219 ValuesToRelease(ValuesToRelease) {}
228 bool IsSigned =
false;
230 ConstraintTy() =
default;
234 : Coefficients(
std::
move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),
237 unsigned size()
const {
return Coefficients.
size(); }
239 unsigned empty()
const {
return Coefficients.
empty(); }
243 bool isValid(
const ConstraintInfo &Info)
const;
245 bool isEq()
const {
return IsEq; }
247 bool isNe()
const {
return IsNe; }
267class ConstraintInfo {
276 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs),
DL(
DL) {
277 auto &Value2Index = getValue2Index(
false);
279 for (
Value *Arg : FunctionArgs) {
281 false,
false,
false);
282 VarPos.Coefficients[Value2Index[Arg]] = -1;
295 return Signed ? SignedCS : UnsignedCS;
298 return Signed ? SignedCS : UnsignedCS;
302 void popLastNVariables(
bool Signed,
unsigned N) {
303 getCS(
Signed).popLastNVariables(
N);
331 unsigned NumIn,
unsigned NumOut,
340 bool IsKnownNonNegative;
342 DecompEntry(int64_t Coefficient,
Value *Variable,
343 bool IsKnownNonNegative =
false)
344 : Coefficient(Coefficient), Variable(Variable),
345 IsKnownNonNegative(IsKnownNonNegative) {}
349struct Decomposition {
354 Decomposition(
Value *V,
bool IsKnownNonNegative =
false) {
360 void add(int64_t OtherOffset) {
364 void add(
const Decomposition &
Other) {
369 void sub(
const Decomposition &
Other) {
370 Decomposition Tmp =
Other;
376 void mul(int64_t Factor) {
378 for (
auto &Var : Vars)
386 APInt ConstantOffset;
394 ConstantOffset =
APInt(
DL.getIndexTypeSizeInBits(
BasePtr->getType()), 0);
403 OffsetResult Result(
GEP,
DL);
404 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
406 Result.ConstantOffset))
411 if (
auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {
414 bool CanCollectInner = InnerGEP->collectOffset(
415 DL,
BitWidth, VariableOffsets2, ConstantOffset2);
417 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
418 VariableOffsets2.
size() > 1 ||
419 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.
size() >= 1)) {
423 Result.BasePtr = InnerGEP->getPointerOperand();
424 Result.ConstantOffset += ConstantOffset2;
425 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.
size() == 1)
426 Result.VariableOffsets = VariableOffsets2;
427 Result.AllInbounds &= InnerGEP->isInBounds();
446 if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
449 assert(!IsSigned &&
"The logic below only supports decomposition for "
450 "unsigned predicates at the moment.");
451 const auto &[BasePtr, ConstantOffset, VariableOffsets, AllInbounds] =
453 if (!BasePtr || !AllInbounds)
456 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
457 for (
auto [
Index, Scale] : VariableOffsets) {
459 IdxResult.mul(Scale.getSExtValue());
460 Result.add(IdxResult);
466 ConstantInt::get(
Index->getType(), 0));
478 auto MergeResults = [&Preconditions, IsSigned, &
DL](
Value *
A,
Value *
B,
486 Type *Ty = V->getType()->getScalarType();
488 if (
auto *
GEP = dyn_cast<GEPOperator>(V))
490 if (isa<ConstantPointerNull>(V))
502 bool IsKnownNonNegative =
false;
506 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
508 return CI->getSExtValue();
517 IsKnownNonNegative =
true;
521 return MergeResults(Op0, Op1, IsSigned);
525 auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
534 if (Shift < Ty->getIntegerBitWidth() - 1) {
535 assert(Shift < 64 &&
"Would overflow");
536 auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
537 Result.mul(int64_t(1) << Shift);
542 return {V, IsKnownNonNegative};
545 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
548 return int64_t(CI->getZExtValue());
553 IsKnownNonNegative =
true;
560 return MergeResults(Op0, Op1, IsSigned);
565 ConstantInt::get(Op0->
getType(), 0));
568 ConstantInt::get(Op1->
getType(), 0));
570 return MergeResults(Op0, Op1, IsSigned);
578 return MergeResults(Op0, CI,
true);
583 return MergeResults(Op0, CI, IsSigned);
587 return {V, IsKnownNonNegative};
588 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
595 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
601 auto ResA =
decompose(Op0, Preconditions, IsSigned,
DL);
602 auto ResB =
decompose(Op1, Preconditions, IsSigned,
DL);
607 return {V, IsKnownNonNegative};
613 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
654 auto &Value2Index = getValue2Index(IsSigned);
656 Preconditions, IsSigned,
DL);
658 Preconditions, IsSigned,
DL);
659 int64_t Offset1 = ADec.Offset;
660 int64_t Offset2 = BDec.Offset;
663 auto &VariablesA = ADec.Vars;
664 auto &VariablesB = BDec.Vars;
669 auto GetOrAddIndex = [&Value2Index, &NewVariables,
670 &NewIndexMap](
Value *
V) ->
unsigned {
671 auto V2I = Value2Index.
find(V);
672 if (V2I != Value2Index.end())
675 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
677 NewVariables.push_back(V);
678 return Insert.first->second;
682 for (
const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
683 GetOrAddIndex(KV.Variable);
689 IsSigned, IsEq, IsNe);
693 auto &
R = Res.Coefficients;
694 for (
const auto &KV : VariablesA) {
695 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
697 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
698 I.first->second &= KV.IsKnownNonNegative;
701 for (
const auto &KV : VariablesB) {
702 if (
SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
703 R[GetOrAddIndex(KV.Variable)]))
706 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
707 I.first->second &= KV.IsKnownNonNegative;
714 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
717 Res.Preconditions = std::move(Preconditions);
721 while (!NewVariables.empty()) {
722 int64_t
Last =
R.back();
726 Value *RemovedV = NewVariables.pop_back_val();
727 NewIndexMap.
erase(RemovedV);
731 for (
auto &KV : KnownNonNegativeVariables) {
733 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
736 C[GetOrAddIndex(KV.first)] = -1;
737 Res.ExtraInfo.push_back(
C);
750 auto &Value2Index = getValue2Index(
false);
765 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
766 if (!NewVariables.
empty())
771bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const {
772 return Coefficients.
size() > 0 &&
773 all_of(Preconditions, [&Info](
const ConditionTy &
C) {
774 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
784 bool IsNegatedOrEqualImplied =
790 if (IsConditionImplied && IsNegatedOrEqualImplied)
797 bool IsStrictLessThanImplied =
804 if (IsNegatedImplied || IsStrictLessThanImplied)
810 if (IsConditionImplied)
815 if (IsNegatedImplied)
824 auto R = getConstraintForSolving(Pred,
A,
B);
825 return R.isValid(*
this) &&
826 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
829void ConstraintInfo::transferToOtherSystem(
832 auto IsKnownNonNegative = [
this](
Value *
V) {
838 if (!
A->getType()->isIntegerTy())
849 if (IsKnownNonNegative(
B)) {
859 if (IsKnownNonNegative(
A)) {
867 if (IsKnownNonNegative(
A))
874 if (IsKnownNonNegative(
B))
880 if (IsKnownNonNegative(
B))
896void State::addInfoForInductions(
BasicBlock &BB) {
898 if (!L ||
L->getHeader() != &BB)
912 PN = dyn_cast<PHINode>(
A);
921 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(0);
923 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(1);
927 if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB) || InLoopSucc == &BB)
930 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.
getSCEV(PN));
932 if (!AR || AR->getLoop() != L || !LoopPred)
935 const SCEV *StartSCEV = AR->getStart();
936 Value *StartValue =
nullptr;
937 if (
auto *
C = dyn_cast<SCEVConstant>(StartSCEV)) {
938 StartValue =
C->getValue();
941 assert(SE.
getSCEV(StartValue) == StartSCEV &&
"inconsistent start value");
947 bool MonotonicallyIncreasingUnsigned =
949 bool MonotonicallyIncreasingSigned =
953 if (MonotonicallyIncreasingUnsigned)
956 if (MonotonicallyIncreasingSigned)
961 if (
auto *
C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
962 StepOffset =
C->getAPInt();
967 if (!
L->isLoopInvariant(
B))
973 if (!(-StepOffset).isOne())
979 WorkList.
push_back(FactOrCheck::getConditionFact(
982 WorkList.
push_back(FactOrCheck::getConditionFact(
987 WorkList.
push_back(FactOrCheck::getConditionFact(
990 WorkList.
push_back(FactOrCheck::getConditionFact(
1002 if (!StepOffset.
isOne()) {
1005 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1013 if (!MonotonicallyIncreasingUnsigned)
1014 WorkList.
push_back(FactOrCheck::getConditionFact(
1017 if (!MonotonicallyIncreasingSigned)
1018 WorkList.
push_back(FactOrCheck::getConditionFact(
1022 WorkList.
push_back(FactOrCheck::getConditionFact(
1025 WorkList.
push_back(FactOrCheck::getConditionFact(
1031 addInfoForInductions(BB);
1034 bool GuaranteedToExecute =
true;
1037 if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
1038 for (
Use &U :
Cmp->uses()) {
1040 auto *DTN = DT.
getNode(UserI->getParent());
1043 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
1048 auto *II = dyn_cast<IntrinsicInst>(&
I);
1051 case Intrinsic::assume: {
1056 if (GuaranteedToExecute) {
1063 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1068 case Intrinsic::ssub_with_overflow:
1070 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1073 case Intrinsic::umin:
1074 case Intrinsic::umax:
1075 case Intrinsic::smin:
1076 case Intrinsic::smax:
1079 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1085 case Intrinsic::abs:
1093 if (
auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1094 for (
auto &Case :
Switch->cases()) {
1096 Value *
V = Case.getCaseValue();
1097 if (!canAddSuccessor(BB, Succ))
1105 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
1106 if (!Br || !Br->isConditional())
1127 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1128 if (SeenCond.
insert(V).second)
1133 while (!CondWorkList.
empty()) {
1135 if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1139 :
Cmp->getPredicate(),
1140 Cmp->getOperand(0),
Cmp->getOperand(1)));
1158 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1161 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1163 DT.
getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1164 CmpI->getOperand(0), CmpI->getOperand(1)));
1165 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1167 DT.
getNode(Br->getSuccessor(1)),
1169 CmpI->getOperand(1)));
1175 OS <<
"icmp " << Pred <<
' ';
1187struct ReproducerEntry {
1223 auto &Value2Index =
Info.getValue2Index(IsSigned);
1225 while (!WorkList.
empty()) {
1227 if (!Seen.
insert(V).second)
1229 if (Old2New.
find(V) != Old2New.
end())
1231 if (isa<Constant>(V))
1234 auto *
I = dyn_cast<Instruction>(V);
1235 if (Value2Index.contains(V) || !
I ||
1236 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1246 for (
auto &Entry : Stack)
1247 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1248 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1249 CollectArguments(
Cond, ICmpInst::isSigned(
Cond->getPredicate()));
1252 for (
auto *
P : Args)
1258 Cond->getModule()->getName() +
1259 Cond->getFunction()->getName() +
"repro",
1262 for (
unsigned I = 0;
I < Args.size(); ++
I) {
1264 Old2New[Args[
I]] =
F->getArg(
I);
1279 auto &Value2Index =
Info.getValue2Index(IsSigned);
1280 while (!WorkList.
empty()) {
1282 if (Old2New.
find(V) != Old2New.
end())
1285 auto *
I = dyn_cast<Instruction>(V);
1286 if (!Value2Index.contains(V) &&
I) {
1287 Old2New[V] =
nullptr;
1297 Old2New[
I] = Cloned;
1298 Old2New[
I]->setName(
I->getName());
1310 for (
auto &Entry : Stack) {
1311 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1319 auto *Cmp = Builder.
CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1326 Entry->getTerminator()->setOperand(0,
Cond);
1334 ConstraintInfo &Info) {
1337 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1338 if (R.empty() || !R.isValid(
Info)){
1340 return std::nullopt;
1343 auto &CSToUse =
Info.getCS(R.IsSigned);
1348 for (
auto &Row : R.ExtraInfo)
1349 CSToUse.addVariableRow(Row);
1351 for (
unsigned I = 0;
I < R.ExtraInfo.size(); ++
I)
1352 CSToUse.popLastConstraint();
1355 if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1357 return std::nullopt;
1360 dbgs() <<
"Condition ";
1364 dbgs() <<
" implied by dominating constraints\n";
1367 return ImpliedCondition;
1370 return std::nullopt;
1374 CmpInst *Cmp, ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
1378 auto ReplaceCmpWithConstant = [&](
CmpInst *Cmp,
bool IsTrue) {
1382 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1383 ContextInst](
Use &U) {
1385 auto *DTN = DT.
getNode(UserI->getParent());
1388 if (UserI->getParent() == ContextInst->
getParent() &&
1389 UserI->comesBefore(ContextInst))
1394 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
1395 return !II || II->getIntrinsicID() != Intrinsic::assume;
1398 if (Cmp->use_empty())
1403 if (
auto ImpliedCondition =
1405 Cmp->getOperand(1), Cmp,
Info))
1406 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1414 MinMax->replaceAllUsesWith(
MinMax->getOperand(UseLHS ? 0 : 1));
1420 ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1423 return ReplaceMinMaxWithOperand(
MinMax, *ImpliedCondition);
1426 return ReplaceMinMaxWithOperand(
MinMax, !*ImpliedCondition);
1432 Module *ReproducerModule,
1435 Info.popLastConstraint(E.IsSigned);
1437 auto &Mapping =
Info.getValue2Index(E.IsSigned);
1438 for (
Value *V : E.ValuesToRelease)
1440 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1442 if (ReproducerModule)
1449 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
1456 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
1457 unsigned OtherOpIdx = JoinOp->
getOperand(0) == CmpToCheck ? 1 : 0;
1462 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
1475 unsigned OldSize = DFSInStack.
size();
1476 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1477 if (OldSize == DFSInStack.
size())
1480 bool Changed =
false;
1482 if (
auto ImpliedCondition =
1485 if (IsOr && isa<SelectInst>(JoinOp)) {
1487 OtherOpIdx == 0 ? 2 : 0,
1498 while (OldSize < DFSInStack.
size()) {
1499 StackEntry E = DFSInStack.
back();
1507 unsigned NumIn,
unsigned NumOut,
1512 auto R = getConstraint(Pred,
A,
B, NewVariables);
1515 if (!
R.isValid(*
this) ||
R.isNe())
1521 auto &CSToUse = getCS(
R.IsSigned);
1522 if (
R.Coefficients.empty())
1525 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
1531 auto &Value2Index = getValue2Index(
R.IsSigned);
1532 for (
Value *V : NewVariables) {
1533 Value2Index.insert({
V, Value2Index.size() + 1});
1538 dbgs() <<
" constraint: ";
1544 std::move(ValuesToRelease));
1547 for (
Value *V : NewVariables) {
1549 false,
false,
false);
1550 VarPos.Coefficients[Value2Index[
V]] = -1;
1551 CSToUse.addVariableRow(VarPos.Coefficients);
1559 for (
auto &Coeff :
R.Coefficients)
1561 CSToUse.addVariableRowFill(
R.Coefficients);
1571 bool Changed =
false;
1573 Value *Sub =
nullptr;
1578 U->replaceAllUsesWith(Sub);
1581 U->replaceAllUsesWith(Builder.
getFalse());
1586 if (U->use_empty()) {
1587 auto *
I = cast<Instruction>(U);
1605 ConstraintInfo &
Info) {
1606 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1607 if (R.size() < 2 || !R.isValid(
Info))
1610 auto &CSToUse =
Info.getCS(R.IsSigned);
1611 return CSToUse.isConditionImplied(R.Coefficients);
1614 bool Changed =
false;
1622 ConstantInt::get(
A->getType(), 0),
Info))
1632 bool Changed =
false;
1635 for (
Value &Arg :
F.args())
1637 ConstraintInfo
Info(
F.getParent()->getDataLayout(), FunctionArgs);
1638 State S(DT, LI, SE);
1639 std::unique_ptr<Module> ReproducerModule(
1658 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1659 auto HasNoConstOp = [](const FactOrCheck &B) {
1660 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1661 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1662 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1666 if (
A.NumIn ==
B.NumIn) {
1667 if (A.isConditionFact() && B.isConditionFact()) {
1668 bool NoConstOpA = HasNoConstOp(A);
1669 bool NoConstOpB = HasNoConstOp(B);
1670 return NoConstOpA < NoConstOpB;
1672 if (
A.isConditionFact())
1674 if (
B.isConditionFact())
1676 auto *InstA =
A.getContextInst();
1677 auto *InstB =
B.getContextInst();
1678 return InstA->comesBefore(InstB);
1680 return A.NumIn <
B.NumIn;
1688 for (FactOrCheck &CB : S.WorkList) {
1691 while (!DFSInStack.
empty()) {
1692 auto &E = DFSInStack.
back();
1693 LLVM_DEBUG(
dbgs() <<
"Top of stack : " << E.NumIn <<
" " << E.NumOut
1695 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1696 assert(E.NumIn <= CB.NumIn);
1697 if (CB.NumOut <= E.NumOut)
1700 dbgs() <<
"Removing ";
1702 Info.getValue2Index(E.IsSigned));
1712 Instruction *Inst = CB.getInstructionToSimplify();
1715 LLVM_DEBUG(
dbgs() <<
"Processing condition to simplify: " << *Inst
1717 if (
auto *II = dyn_cast<WithOverflowInst>(Inst)) {
1719 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1721 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1722 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
1727 ReproducerCondStack, DFSInStack);
1730 }
else if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1742 <<
"Skip adding constraint because system has too many rows.\n");
1746 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1747 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1750 Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1751 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1754 for (
unsigned I = 0,
1755 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1757 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
1764 if (!CB.isConditionFact()) {
1766 if (
match(CB.Inst, m_Intrinsic<Intrinsic::abs>(
m_Value(
X)))) {
1768 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1770 ConstantInt::get(CB.Inst->getType(), 0));
1775 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1776 Pred = ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1783 Value *
A =
nullptr, *
B =
nullptr;
1784 if (CB.isConditionFact()) {
1785 Pred = CB.Cond.Pred;
1789 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
1791 dbgs() <<
"Not adding fact ";
1793 dbgs() <<
" because precondition ";
1796 dbgs() <<
" does not hold.\n";
1801 bool Matched =
match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1804 assert(Matched &&
"Must have an assume intrinsic with a icmp operand");
1806 AddFact(Pred,
A,
B);
1809 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1812 ReproducerModule->print(StringS,
nullptr);
1815 Rem <<
ore::NV(
"module") << S;
1820 unsigned SignedEntries =
1821 count_if(DFSInStack, [](
const StackEntry &E) {
return E.IsSigned; });
1822 assert(
Info.getCS(
false).size() - FunctionArgs.size() ==
1823 DFSInStack.
size() - SignedEntries &&
1824 "updates to CS and DFSInStack are out of sync");
1825 assert(
Info.getCS(
true).size() == SignedEntries &&
1826 "updates to CS and DFSInStack are out of sync");
1830 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")
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)
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.
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.
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.
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,...
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
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.
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)
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)
CallInst * CreateAssumption(Value *Cond, ArrayRef< OperandBundleDef > OpBundles=std::nullopt)
Create an assume intrinsic call that allows the optimizer to assume that the provided condition will ...
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.
const BasicBlock * getParent() const
InstListType::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.
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
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.
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.
iterator_range< user_iterator > users()
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 ...
self_iterator getIterator()
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.
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.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
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)
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.