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 ConstantInt::get(Op0->
getType(), 0));
566 return MergeResults(Op0, Op1, IsSigned);
571 ConstantInt::get(Op0->
getType(), 0));
574 ConstantInt::get(Op1->
getType(), 0));
576 return MergeResults(Op0, Op1, IsSigned);
584 return MergeResults(Op0, CI,
true);
589 return MergeResults(Op0, CI, IsSigned);
593 return {V, IsKnownNonNegative};
594 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
601 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
607 auto ResA =
decompose(Op0, Preconditions, IsSigned,
DL);
608 auto ResB =
decompose(Op1, Preconditions, IsSigned,
DL);
613 return {V, IsKnownNonNegative};
619 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
660 auto &Value2Index = getValue2Index(IsSigned);
662 Preconditions, IsSigned,
DL);
664 Preconditions, IsSigned,
DL);
665 int64_t Offset1 = ADec.Offset;
666 int64_t Offset2 = BDec.Offset;
669 auto &VariablesA = ADec.Vars;
670 auto &VariablesB = BDec.Vars;
675 auto GetOrAddIndex = [&Value2Index, &NewVariables,
676 &NewIndexMap](
Value *
V) ->
unsigned {
677 auto V2I = Value2Index.
find(V);
678 if (V2I != Value2Index.end())
681 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
683 NewVariables.push_back(V);
684 return Insert.first->second;
688 for (
const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
689 GetOrAddIndex(KV.Variable);
695 IsSigned, IsEq, IsNe);
699 auto &
R = Res.Coefficients;
700 for (
const auto &KV : VariablesA) {
701 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
703 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
704 I.first->second &= KV.IsKnownNonNegative;
707 for (
const auto &KV : VariablesB) {
708 if (
SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
709 R[GetOrAddIndex(KV.Variable)]))
712 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
713 I.first->second &= KV.IsKnownNonNegative;
720 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
723 Res.Preconditions = std::move(Preconditions);
727 while (!NewVariables.empty()) {
728 int64_t
Last =
R.back();
732 Value *RemovedV = NewVariables.pop_back_val();
733 NewIndexMap.
erase(RemovedV);
737 for (
auto &KV : KnownNonNegativeVariables) {
739 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
742 C[GetOrAddIndex(KV.first)] = -1;
743 Res.ExtraInfo.push_back(
C);
756 auto &Value2Index = getValue2Index(
false);
771 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
772 if (!NewVariables.
empty())
777bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const {
778 return Coefficients.
size() > 0 &&
779 all_of(Preconditions, [&Info](
const ConditionTy &
C) {
780 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
790 bool IsNegatedOrEqualImplied =
796 if (IsConditionImplied && IsNegatedOrEqualImplied)
803 bool IsStrictLessThanImplied =
810 if (IsNegatedImplied || IsStrictLessThanImplied)
816 if (IsConditionImplied)
821 if (IsNegatedImplied)
830 auto R = getConstraintForSolving(Pred,
A,
B);
831 return R.isValid(*
this) &&
832 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
835void ConstraintInfo::transferToOtherSystem(
838 auto IsKnownNonNegative = [
this](
Value *
V) {
844 if (!
A->getType()->isIntegerTy())
855 if (IsKnownNonNegative(
B)) {
865 if (IsKnownNonNegative(
A)) {
873 if (IsKnownNonNegative(
A))
880 if (IsKnownNonNegative(
B))
886 if (IsKnownNonNegative(
B))
902void State::addInfoForInductions(
BasicBlock &BB) {
904 if (!L ||
L->getHeader() != &BB)
918 PN = dyn_cast<PHINode>(
A);
927 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(0);
929 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(1);
933 if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB) || InLoopSucc == &BB)
936 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.
getSCEV(PN));
938 if (!AR || AR->getLoop() != L || !LoopPred)
941 const SCEV *StartSCEV = AR->getStart();
942 Value *StartValue =
nullptr;
943 if (
auto *
C = dyn_cast<SCEVConstant>(StartSCEV)) {
944 StartValue =
C->getValue();
947 assert(SE.
getSCEV(StartValue) == StartSCEV &&
"inconsistent start value");
953 bool MonotonicallyIncreasingUnsigned =
955 bool MonotonicallyIncreasingSigned =
959 if (MonotonicallyIncreasingUnsigned)
962 if (MonotonicallyIncreasingSigned)
967 if (
auto *
C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
968 StepOffset =
C->getAPInt();
973 if (!
L->isLoopInvariant(
B))
979 if (!(-StepOffset).isOne())
985 WorkList.
push_back(FactOrCheck::getConditionFact(
988 WorkList.
push_back(FactOrCheck::getConditionFact(
993 WorkList.
push_back(FactOrCheck::getConditionFact(
996 WorkList.
push_back(FactOrCheck::getConditionFact(
1008 if (!StepOffset.
isOne()) {
1011 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1019 if (!MonotonicallyIncreasingUnsigned)
1020 WorkList.
push_back(FactOrCheck::getConditionFact(
1023 if (!MonotonicallyIncreasingSigned)
1024 WorkList.
push_back(FactOrCheck::getConditionFact(
1028 WorkList.
push_back(FactOrCheck::getConditionFact(
1031 WorkList.
push_back(FactOrCheck::getConditionFact(
1037 addInfoForInductions(BB);
1040 bool GuaranteedToExecute =
true;
1043 if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
1044 for (
Use &U :
Cmp->uses()) {
1046 auto *DTN = DT.
getNode(UserI->getParent());
1049 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
1054 auto *
II = dyn_cast<IntrinsicInst>(&
I);
1057 case Intrinsic::assume: {
1062 if (GuaranteedToExecute) {
1069 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1074 case Intrinsic::ssub_with_overflow:
1076 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1079 case Intrinsic::umin:
1080 case Intrinsic::umax:
1081 case Intrinsic::smin:
1082 case Intrinsic::smax:
1085 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1091 case Intrinsic::abs:
1099 if (
auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1100 for (
auto &Case :
Switch->cases()) {
1102 Value *
V = Case.getCaseValue();
1103 if (!canAddSuccessor(BB, Succ))
1111 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
1112 if (!Br || !Br->isConditional())
1133 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1134 if (SeenCond.
insert(V).second)
1139 while (!CondWorkList.
empty()) {
1141 if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1145 :
Cmp->getPredicate(),
1146 Cmp->getOperand(0),
Cmp->getOperand(1)));
1164 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1167 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1169 DT.
getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1170 CmpI->getOperand(0), CmpI->getOperand(1)));
1171 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1173 DT.
getNode(Br->getSuccessor(1)),
1175 CmpI->getOperand(1)));
1181 OS <<
"icmp " << Pred <<
' ';
1193struct ReproducerEntry {
1229 auto &Value2Index =
Info.getValue2Index(IsSigned);
1231 while (!WorkList.
empty()) {
1233 if (!Seen.
insert(V).second)
1235 if (Old2New.
find(V) != Old2New.
end())
1237 if (isa<Constant>(V))
1240 auto *
I = dyn_cast<Instruction>(V);
1241 if (Value2Index.contains(V) || !
I ||
1242 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1252 for (
auto &Entry : Stack)
1253 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1254 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1255 CollectArguments(
Cond, ICmpInst::isSigned(
Cond->getPredicate()));
1258 for (
auto *
P : Args)
1264 Cond->getModule()->getName() +
1265 Cond->getFunction()->getName() +
"repro",
1268 for (
unsigned I = 0;
I < Args.size(); ++
I) {
1270 Old2New[Args[
I]] =
F->getArg(
I);
1285 auto &Value2Index =
Info.getValue2Index(IsSigned);
1286 while (!WorkList.
empty()) {
1288 if (Old2New.
find(V) != Old2New.
end())
1291 auto *
I = dyn_cast<Instruction>(V);
1292 if (!Value2Index.contains(V) &&
I) {
1293 Old2New[V] =
nullptr;
1303 Old2New[
I] = Cloned;
1304 Old2New[
I]->setName(
I->getName());
1316 for (
auto &Entry : Stack) {
1317 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1325 auto *Cmp = Builder.
CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1332 Entry->getTerminator()->setOperand(0,
Cond);
1340 ConstraintInfo &Info) {
1343 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1344 if (R.empty() || !R.isValid(
Info)){
1346 return std::nullopt;
1349 auto &CSToUse =
Info.getCS(R.IsSigned);
1354 for (
auto &Row : R.ExtraInfo)
1355 CSToUse.addVariableRow(Row);
1357 for (
unsigned I = 0;
I < R.ExtraInfo.size(); ++
I)
1358 CSToUse.popLastConstraint();
1361 if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1363 return std::nullopt;
1366 dbgs() <<
"Condition ";
1370 dbgs() <<
" implied by dominating constraints\n";
1373 return ImpliedCondition;
1376 return std::nullopt;
1380 CmpInst *Cmp, ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
1384 auto ReplaceCmpWithConstant = [&](
CmpInst *Cmp,
bool IsTrue) {
1388 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1389 ContextInst](
Use &U) {
1391 auto *DTN = DT.
getNode(UserI->getParent());
1394 if (UserI->getParent() == ContextInst->
getParent() &&
1395 UserI->comesBefore(ContextInst))
1400 auto *
II = dyn_cast<IntrinsicInst>(U.getUser());
1401 return !
II ||
II->getIntrinsicID() != Intrinsic::assume;
1404 if (Cmp->use_empty())
1409 if (
auto ImpliedCondition =
1411 Cmp->getOperand(1), Cmp,
Info))
1412 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1420 MinMax->replaceAllUsesWith(
MinMax->getOperand(UseLHS ? 0 : 1));
1426 ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1429 return ReplaceMinMaxWithOperand(
MinMax, *ImpliedCondition);
1432 return ReplaceMinMaxWithOperand(
MinMax, !*ImpliedCondition);
1438 Module *ReproducerModule,
1441 Info.popLastConstraint(E.IsSigned);
1443 auto &Mapping =
Info.getValue2Index(E.IsSigned);
1444 for (
Value *V : E.ValuesToRelease)
1446 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1448 if (ReproducerModule)
1455 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
1462 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
1463 unsigned OtherOpIdx = JoinOp->
getOperand(0) == CmpToCheck ? 1 : 0;
1468 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
1481 unsigned OldSize = DFSInStack.
size();
1482 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1483 if (OldSize == DFSInStack.
size())
1486 bool Changed =
false;
1488 if (
auto ImpliedCondition =
1491 if (IsOr && isa<SelectInst>(JoinOp)) {
1493 OtherOpIdx == 0 ? 2 : 0,
1504 while (OldSize < DFSInStack.
size()) {
1505 StackEntry E = DFSInStack.
back();
1513 unsigned NumIn,
unsigned NumOut,
1518 auto R = getConstraint(Pred,
A,
B, NewVariables);
1521 if (!
R.isValid(*
this) ||
R.isNe())
1527 auto &CSToUse = getCS(
R.IsSigned);
1528 if (
R.Coefficients.empty())
1531 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
1537 auto &Value2Index = getValue2Index(
R.IsSigned);
1538 for (
Value *V : NewVariables) {
1539 Value2Index.insert({
V, Value2Index.size() + 1});
1544 dbgs() <<
" constraint: ";
1550 std::move(ValuesToRelease));
1553 for (
Value *V : NewVariables) {
1555 false,
false,
false);
1556 VarPos.Coefficients[Value2Index[
V]] = -1;
1557 CSToUse.addVariableRow(VarPos.Coefficients);
1565 for (
auto &Coeff :
R.Coefficients)
1567 CSToUse.addVariableRowFill(
R.Coefficients);
1577 bool Changed =
false;
1579 Value *Sub =
nullptr;
1584 U->replaceAllUsesWith(Sub);
1587 U->replaceAllUsesWith(Builder.
getFalse());
1592 if (U->use_empty()) {
1593 auto *
I = cast<Instruction>(U);
1600 if (
II->use_empty()) {
1601 II->eraseFromParent();
1611 ConstraintInfo &
Info) {
1612 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1613 if (R.size() < 2 || !R.isValid(
Info))
1616 auto &CSToUse =
Info.getCS(R.IsSigned);
1617 return CSToUse.isConditionImplied(R.Coefficients);
1620 bool Changed =
false;
1621 if (
II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
1628 ConstantInt::get(
A->getType(), 0),
Info))
1638 bool Changed =
false;
1641 for (
Value &Arg :
F.args())
1643 ConstraintInfo
Info(
F.getDataLayout(), FunctionArgs);
1644 State S(DT, LI, SE);
1645 std::unique_ptr<Module> ReproducerModule(
1664 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1665 auto HasNoConstOp = [](const FactOrCheck &B) {
1666 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1667 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1668 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1672 if (
A.NumIn ==
B.NumIn) {
1673 if (A.isConditionFact() && B.isConditionFact()) {
1674 bool NoConstOpA = HasNoConstOp(A);
1675 bool NoConstOpB = HasNoConstOp(B);
1676 return NoConstOpA < NoConstOpB;
1678 if (
A.isConditionFact())
1680 if (
B.isConditionFact())
1682 auto *InstA =
A.getContextInst();
1683 auto *InstB =
B.getContextInst();
1684 return InstA->comesBefore(InstB);
1686 return A.NumIn <
B.NumIn;
1694 for (FactOrCheck &CB : S.WorkList) {
1697 while (!DFSInStack.
empty()) {
1698 auto &E = DFSInStack.
back();
1699 LLVM_DEBUG(
dbgs() <<
"Top of stack : " << E.NumIn <<
" " << E.NumOut
1701 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1702 assert(E.NumIn <= CB.NumIn);
1703 if (CB.NumOut <= E.NumOut)
1706 dbgs() <<
"Removing ";
1708 Info.getValue2Index(E.IsSigned));
1718 Instruction *Inst = CB.getInstructionToSimplify();
1721 LLVM_DEBUG(
dbgs() <<
"Processing condition to simplify: " << *Inst
1723 if (
auto *
II = dyn_cast<WithOverflowInst>(Inst)) {
1725 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1727 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1728 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
1733 ReproducerCondStack, DFSInStack);
1736 }
else if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1748 <<
"Skip adding constraint because system has too many rows.\n");
1752 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1753 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1756 Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1757 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1760 for (
unsigned I = 0,
1761 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1763 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
1770 if (!CB.isConditionFact()) {
1772 if (
match(CB.Inst, m_Intrinsic<Intrinsic::abs>(
m_Value(
X)))) {
1774 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1776 ConstantInt::get(CB.Inst->getType(), 0));
1781 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1782 Pred = ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1789 Value *
A =
nullptr, *
B =
nullptr;
1790 if (CB.isConditionFact()) {
1791 Pred = CB.Cond.Pred;
1795 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
1797 dbgs() <<
"Not adding fact ";
1799 dbgs() <<
" because precondition ";
1802 dbgs() <<
" does not hold.\n";
1807 bool Matched =
match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1810 assert(Matched &&
"Must have an assume intrinsic with a icmp operand");
1812 AddFact(Pred,
A,
B);
1815 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1818 ReproducerModule->print(StringS,
nullptr);
1821 Rem <<
ore::NV(
"module") << S;
1826 unsigned SignedEntries =
1827 count_if(DFSInStack, [](
const StackEntry &E) {
return E.IsSigned; });
1828 assert(
Info.getCS(
false).size() - FunctionArgs.size() ==
1829 DFSInStack.
size() - SignedEntries &&
1830 "updates to CS and DFSInStack are out of sync");
1831 assert(
Info.getCS(
true).size() == SignedEntries &&
1832 "updates to CS and DFSInStack are out of sync");
1836 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.
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 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.
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.
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.
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.
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.
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.