48using namespace PatternMatch;
50#define DEBUG_TYPE "constraint-elimination"
52STATISTIC(NumCondsRemoved,
"Number of instructions removed");
54 "Controls which conditions are eliminated");
58 cl::desc(
"Maximum number of rows to keep in constraint system"));
62 cl::desc(
"Dump IR to reproduce successful transformations."));
82 Instruction *UserI = cast<Instruction>(U.getUser());
83 if (
auto *Phi = dyn_cast<PHINode>(UserI))
84 UserI = Phi->getIncomingBlock(U)->getTerminator();
96 : Pred(
CmpInst::BAD_ICMP_PREDICATE), Op0(nullptr), Op1(nullptr) {}
98 : Pred(Pred), Op0(Op0), Op1(Op1) {}
131 : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
135 :
U(
U), DoesHold(
CmpInst::BAD_ICMP_PREDICATE, nullptr, nullptr),
136 NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
137 Ty(EntryTy::UseCheck) {}
141 :
Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
142 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
147 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
151 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
155 return FactOrCheck(DTN, U);
159 return FactOrCheck(EntryTy::InstCheck, DTN, CI);
162 bool isCheck()
const {
163 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
167 if (Ty == EntryTy::UseCheck)
174 if (Ty == EntryTy::InstCheck)
177 return dyn_cast<Instruction>(*U);
180 bool isConditionFact()
const {
return Ty == EntryTy::ConditionFact; }
191 : DT(DT), LI(LI), SE(SE) {}
212 bool IsSigned =
false;
217 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
219 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
220 ValuesToRelease(ValuesToRelease) {}
229 bool IsSigned =
false;
231 ConstraintTy() =
default;
235 : Coefficients(
std::
move(Coefficients)), IsSigned(IsSigned), IsEq(IsEq),
238 unsigned size()
const {
return Coefficients.
size(); }
240 unsigned empty()
const {
return Coefficients.
empty(); }
244 bool isValid(
const ConstraintInfo &Info)
const;
246 bool isEq()
const {
return IsEq; }
248 bool isNe()
const {
return IsNe; }
268class ConstraintInfo {
277 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs),
DL(
DL) {
278 auto &Value2Index = getValue2Index(
false);
280 for (
Value *Arg : FunctionArgs) {
282 false,
false,
false);
283 VarPos.Coefficients[Value2Index[Arg]] = -1;
296 return Signed ? SignedCS : UnsignedCS;
299 return Signed ? SignedCS : UnsignedCS;
303 void popLastNVariables(
bool Signed,
unsigned N) {
304 getCS(
Signed).popLastNVariables(
N);
332 unsigned NumIn,
unsigned NumOut,
341 bool IsKnownNonNegative;
343 DecompEntry(int64_t Coefficient,
Value *Variable,
344 bool IsKnownNonNegative =
false)
345 : Coefficient(Coefficient), Variable(Variable),
346 IsKnownNonNegative(IsKnownNonNegative) {}
350struct Decomposition {
355 Decomposition(
Value *V,
bool IsKnownNonNegative =
false) {
361 void add(int64_t OtherOffset) {
365 void add(
const Decomposition &
Other) {
370 void sub(
const Decomposition &
Other) {
371 Decomposition Tmp =
Other;
377 void mul(int64_t Factor) {
379 for (
auto &Var : Vars)
387 APInt ConstantOffset;
395 ConstantOffset =
APInt(
DL.getIndexTypeSizeInBits(
BasePtr->getType()), 0);
404 OffsetResult Result(
GEP,
DL);
405 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
407 Result.ConstantOffset))
412 if (
auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {
415 bool CanCollectInner = InnerGEP->collectOffset(
416 DL,
BitWidth, VariableOffsets2, ConstantOffset2);
418 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
419 VariableOffsets2.
size() > 1 ||
420 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.
size() >= 1)) {
424 Result.BasePtr = InnerGEP->getPointerOperand();
425 Result.ConstantOffset += ConstantOffset2;
426 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.
size() == 1)
427 Result.VariableOffsets = VariableOffsets2;
428 Result.AllInbounds &= InnerGEP->isInBounds();
447 if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
450 assert(!IsSigned &&
"The logic below only supports decomposition for "
451 "unsigned predicates at the moment.");
452 const auto &[BasePtr, ConstantOffset, VariableOffsets, AllInbounds] =
454 if (!BasePtr || !AllInbounds)
457 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
458 for (
auto [
Index, Scale] : VariableOffsets) {
460 IdxResult.mul(Scale.getSExtValue());
461 Result.add(IdxResult);
467 ConstantInt::get(
Index->getType(), 0));
479 auto MergeResults = [&Preconditions, IsSigned, &
DL](
Value *
A,
Value *
B,
487 Type *Ty = V->getType()->getScalarType();
489 if (
auto *
GEP = dyn_cast<GEPOperator>(V))
491 if (isa<ConstantPointerNull>(V))
503 bool IsKnownNonNegative =
false;
507 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
509 return CI->getSExtValue();
518 IsKnownNonNegative =
true;
522 return MergeResults(Op0, Op1, IsSigned);
526 auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
535 if (Shift < Ty->getIntegerBitWidth() - 1) {
536 assert(Shift < 64 &&
"Would overflow");
537 auto Result =
decompose(Op0, Preconditions, IsSigned,
DL);
538 Result.mul(int64_t(1) << Shift);
543 return {V, IsKnownNonNegative};
546 if (
auto *CI = dyn_cast<ConstantInt>(V)) {
549 return int64_t(CI->getZExtValue());
554 IsKnownNonNegative =
true;
561 ConstantInt::get(Op0->
getType(), 0));
567 return MergeResults(Op0, Op1, IsSigned);
572 ConstantInt::get(Op0->
getType(), 0));
575 ConstantInt::get(Op1->
getType(), 0));
577 return MergeResults(Op0, Op1, IsSigned);
585 return MergeResults(Op0, CI,
true);
590 return MergeResults(Op0, CI, IsSigned);
594 return {V, IsKnownNonNegative};
595 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
602 auto Result =
decompose(Op1, Preconditions, IsSigned,
DL);
608 auto ResA =
decompose(Op0, Preconditions, IsSigned,
DL);
609 auto ResB =
decompose(Op1, Preconditions, IsSigned,
DL);
614 return {V, IsKnownNonNegative};
620 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
661 auto &Value2Index = getValue2Index(IsSigned);
663 Preconditions, IsSigned,
DL);
665 Preconditions, IsSigned,
DL);
666 int64_t Offset1 = ADec.Offset;
667 int64_t Offset2 = BDec.Offset;
670 auto &VariablesA = ADec.Vars;
671 auto &VariablesB = BDec.Vars;
676 auto GetOrAddIndex = [&Value2Index, &NewVariables,
677 &NewIndexMap](
Value *
V) ->
unsigned {
678 auto V2I = Value2Index.
find(V);
679 if (V2I != Value2Index.end())
682 NewIndexMap.
insert({V, Value2Index.size() + NewVariables.size() + 1});
684 NewVariables.push_back(V);
685 return Insert.first->second;
689 for (
const auto &KV : concat<DecompEntry>(VariablesA, VariablesB))
690 GetOrAddIndex(KV.Variable);
696 IsSigned, IsEq, IsNe);
700 auto &
R = Res.Coefficients;
701 for (
const auto &KV : VariablesA) {
702 R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
704 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
705 I.first->second &= KV.IsKnownNonNegative;
708 for (
const auto &KV : VariablesB) {
709 if (
SubOverflow(R[GetOrAddIndex(KV.Variable)], KV.Coefficient,
710 R[GetOrAddIndex(KV.Variable)]))
713 KnownNonNegativeVariables.
insert({KV.Variable, KV.IsKnownNonNegative});
714 I.first->second &= KV.IsKnownNonNegative;
721 if (
AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
724 Res.Preconditions = std::move(Preconditions);
728 while (!NewVariables.empty()) {
729 int64_t
Last =
R.back();
733 Value *RemovedV = NewVariables.pop_back_val();
734 NewIndexMap.
erase(RemovedV);
738 for (
auto &KV : KnownNonNegativeVariables) {
740 (!Value2Index.contains(KV.first) && !NewIndexMap.
contains(KV.first)))
743 C[GetOrAddIndex(KV.first)] = -1;
744 Res.ExtraInfo.push_back(
C);
757 auto &Value2Index = getValue2Index(
false);
772 ConstraintTy
R = getConstraint(Pred, Op0, Op1, NewVariables);
773 if (!NewVariables.
empty())
778bool ConstraintTy::isValid(
const ConstraintInfo &Info)
const {
779 return Coefficients.
size() > 0 &&
780 all_of(Preconditions, [&Info](
const ConditionTy &
C) {
781 return Info.doesHold(
C.Pred,
C.Op0,
C.Op1);
791 bool IsNegatedOrEqualImplied =
797 if (IsConditionImplied && IsNegatedOrEqualImplied)
804 bool IsStrictLessThanImplied =
811 if (IsNegatedImplied || IsStrictLessThanImplied)
817 if (IsConditionImplied)
822 if (IsNegatedImplied)
831 auto R = getConstraintForSolving(Pred,
A,
B);
832 return R.isValid(*
this) &&
833 getCS(
R.IsSigned).isConditionImplied(
R.Coefficients);
836void ConstraintInfo::transferToOtherSystem(
839 auto IsKnownNonNegative = [
this](
Value *
V) {
845 if (!
A->getType()->isIntegerTy())
856 if (IsKnownNonNegative(
B)) {
866 if (IsKnownNonNegative(
A)) {
874 if (IsKnownNonNegative(
A))
881 if (IsKnownNonNegative(
B))
887 if (IsKnownNonNegative(
B))
903void State::addInfoForInductions(
BasicBlock &BB) {
905 if (!L ||
L->getHeader() != &BB)
919 PN = dyn_cast<PHINode>(
A);
928 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(0);
930 InLoopSucc = cast<BranchInst>(BB.
getTerminator())->getSuccessor(1);
934 if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB) || InLoopSucc == &BB)
937 auto *AR = dyn_cast_or_null<SCEVAddRecExpr>(SE.
getSCEV(PN));
939 if (!AR || AR->getLoop() != L || !LoopPred)
942 const SCEV *StartSCEV = AR->getStart();
943 Value *StartValue =
nullptr;
944 if (
auto *
C = dyn_cast<SCEVConstant>(StartSCEV)) {
945 StartValue =
C->getValue();
948 assert(SE.
getSCEV(StartValue) == StartSCEV &&
"inconsistent start value");
954 bool MonotonicallyIncreasingUnsigned =
956 bool MonotonicallyIncreasingSigned =
960 if (MonotonicallyIncreasingUnsigned)
963 if (MonotonicallyIncreasingSigned)
968 if (
auto *
C = dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE)))
969 StepOffset =
C->getAPInt();
974 if (!
L->isLoopInvariant(
B))
980 if (!(-StepOffset).isOne())
986 WorkList.
push_back(FactOrCheck::getConditionFact(
989 WorkList.
push_back(FactOrCheck::getConditionFact(
994 WorkList.
push_back(FactOrCheck::getConditionFact(
997 WorkList.
push_back(FactOrCheck::getConditionFact(
1009 if (!StepOffset.
isOne()) {
1012 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1020 if (!MonotonicallyIncreasingUnsigned)
1021 WorkList.
push_back(FactOrCheck::getConditionFact(
1024 if (!MonotonicallyIncreasingSigned)
1025 WorkList.
push_back(FactOrCheck::getConditionFact(
1029 WorkList.
push_back(FactOrCheck::getConditionFact(
1032 WorkList.
push_back(FactOrCheck::getConditionFact(
1041 "unsupported predicate");
1044 L->getExitBlocks(ExitBBs);
1052 addInfoForInductions(BB);
1055 bool GuaranteedToExecute =
true;
1058 if (
auto Cmp = dyn_cast<ICmpInst>(&
I)) {
1059 for (
Use &U :
Cmp->uses()) {
1061 auto *DTN = DT.
getNode(UserI->getParent());
1064 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
1069 auto *
II = dyn_cast<IntrinsicInst>(&
I);
1072 case Intrinsic::assume: {
1077 if (GuaranteedToExecute) {
1084 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1089 case Intrinsic::ssub_with_overflow:
1090 case Intrinsic::ucmp:
1091 case Intrinsic::scmp:
1093 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1096 case Intrinsic::umin:
1097 case Intrinsic::umax:
1098 case Intrinsic::smin:
1099 case Intrinsic::smax:
1102 FactOrCheck::getCheck(DT.
getNode(&BB), cast<CallInst>(&
I)));
1108 case Intrinsic::abs:
1116 if (
auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1117 for (
auto &Case :
Switch->cases()) {
1119 Value *
V = Case.getCaseValue();
1120 if (!canAddSuccessor(BB, Succ))
1128 auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
1129 if (!Br || !Br->isConditional())
1150 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1151 if (SeenCond.
insert(V).second)
1156 while (!CondWorkList.
empty()) {
1158 if (
auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
1162 :
Cmp->getPredicate(),
1163 Cmp->getOperand(0),
Cmp->getOperand(1)));
1181 auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
1184 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1186 DT.
getNode(Br->getSuccessor(0)), CmpI->getPredicate(),
1187 CmpI->getOperand(0), CmpI->getOperand(1)));
1188 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1190 DT.
getNode(Br->getSuccessor(1)),
1192 CmpI->getOperand(1)));
1198 OS <<
"icmp " << Pred <<
' ';
1210struct ReproducerEntry {
1246 auto &Value2Index =
Info.getValue2Index(IsSigned);
1248 while (!WorkList.
empty()) {
1250 if (!Seen.
insert(V).second)
1252 if (Old2New.
find(V) != Old2New.
end())
1254 if (isa<Constant>(V))
1257 auto *
I = dyn_cast<Instruction>(V);
1258 if (Value2Index.contains(V) || !
I ||
1259 !isa<CmpInst, BinaryOperator, GEPOperator, CastInst>(V)) {
1269 for (
auto &Entry : Stack)
1270 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1271 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1272 CollectArguments(
Cond, ICmpInst::isSigned(
Cond->getPredicate()));
1275 for (
auto *
P : Args)
1281 Cond->getModule()->getName() +
1282 Cond->getFunction()->getName() +
"repro",
1285 for (
unsigned I = 0;
I < Args.size(); ++
I) {
1287 Old2New[Args[
I]] =
F->getArg(
I);
1302 auto &Value2Index =
Info.getValue2Index(IsSigned);
1303 while (!WorkList.
empty()) {
1305 if (Old2New.
find(V) != Old2New.
end())
1308 auto *
I = dyn_cast<Instruction>(V);
1309 if (!Value2Index.contains(V) &&
I) {
1310 Old2New[V] =
nullptr;
1320 Old2New[
I] = Cloned;
1321 Old2New[
I]->setName(
I->getName());
1333 for (
auto &Entry : Stack) {
1334 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
1342 auto *Cmp = Builder.
CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
1349 Entry->getTerminator()->setOperand(0,
Cond);
1357 ConstraintInfo &Info) {
1360 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1361 if (R.empty() || !R.isValid(
Info)){
1363 return std::nullopt;
1366 auto &CSToUse =
Info.getCS(R.IsSigned);
1371 for (
auto &Row : R.ExtraInfo)
1372 CSToUse.addVariableRow(Row);
1374 for (
unsigned I = 0;
I < R.ExtraInfo.size(); ++
I)
1375 CSToUse.popLastConstraint();
1378 if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
1380 return std::nullopt;
1383 dbgs() <<
"Condition ";
1387 dbgs() <<
" implied by dominating constraints\n";
1390 return ImpliedCondition;
1393 return std::nullopt;
1397 CmpInst *Cmp, ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
1401 auto ReplaceCmpWithConstant = [&](
CmpInst *Cmp,
bool IsTrue) {
1405 Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut,
1406 ContextInst](
Use &U) {
1408 auto *DTN = DT.
getNode(UserI->getParent());
1411 if (UserI->getParent() == ContextInst->
getParent() &&
1412 UserI->comesBefore(ContextInst))
1417 auto *
II = dyn_cast<IntrinsicInst>(U.getUser());
1418 return !
II ||
II->getIntrinsicID() != Intrinsic::assume;
1421 if (Cmp->use_empty())
1426 if (
auto ImpliedCondition =
1428 Cmp->getOperand(1), Cmp,
Info))
1429 return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
1437 MinMax->replaceAllUsesWith(
MinMax->getOperand(UseLHS ? 0 : 1));
1443 ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1446 return ReplaceMinMaxWithOperand(
MinMax, *ImpliedCondition);
1449 return ReplaceMinMaxWithOperand(
MinMax, !*ImpliedCondition);
1458 I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 1));
1468 I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 0));
1477 Module *ReproducerModule,
1480 Info.popLastConstraint(E.IsSigned);
1482 auto &Mapping =
Info.getValue2Index(E.IsSigned);
1483 for (
Value *V : E.ValuesToRelease)
1485 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
1487 if (ReproducerModule)
1494 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
1501 CmpInst *CmpToCheck = cast<CmpInst>(CB.getInstructionToSimplify());
1502 unsigned OtherOpIdx = JoinOp->
getOperand(0) == CmpToCheck ? 1 : 0;
1507 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
1520 unsigned OldSize = DFSInStack.
size();
1521 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1522 if (OldSize == DFSInStack.
size())
1525 bool Changed =
false;
1527 if (
auto ImpliedCondition =
1530 if (IsOr && isa<SelectInst>(JoinOp)) {
1532 OtherOpIdx == 0 ? 2 : 0,
1543 while (OldSize < DFSInStack.
size()) {
1544 StackEntry E = DFSInStack.
back();
1552 unsigned NumIn,
unsigned NumOut,
1557 auto R = getConstraint(Pred,
A,
B, NewVariables);
1560 if (!
R.isValid(*
this) ||
R.isNe())
1566 auto &CSToUse = getCS(
R.IsSigned);
1567 if (
R.Coefficients.empty())
1570 Added |= CSToUse.addVariableRowFill(
R.Coefficients);
1576 auto &Value2Index = getValue2Index(
R.IsSigned);
1577 for (
Value *V : NewVariables) {
1578 Value2Index.insert({
V, Value2Index.size() + 1});
1583 dbgs() <<
" constraint: ";
1589 std::move(ValuesToRelease));
1592 for (
Value *V : NewVariables) {
1594 false,
false,
false);
1595 VarPos.Coefficients[Value2Index[
V]] = -1;
1596 CSToUse.addVariableRow(VarPos.Coefficients);
1604 for (
auto &Coeff :
R.Coefficients)
1606 CSToUse.addVariableRowFill(
R.Coefficients);
1616 bool Changed =
false;
1618 Value *Sub =
nullptr;
1623 U->replaceAllUsesWith(Sub);
1626 U->replaceAllUsesWith(Builder.
getFalse());
1631 if (U->use_empty()) {
1632 auto *
I = cast<Instruction>(U);
1639 if (
II->use_empty()) {
1640 II->eraseFromParent();
1650 ConstraintInfo &
Info) {
1651 auto R =
Info.getConstraintForSolving(Pred,
A,
B);
1652 if (R.size() < 2 || !R.isValid(
Info))
1655 auto &CSToUse =
Info.getCS(R.IsSigned);
1656 return CSToUse.isConditionImplied(R.Coefficients);
1659 bool Changed =
false;
1660 if (
II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
1667 ConstantInt::get(
A->getType(), 0),
Info))
1677 bool Changed =
false;
1680 for (
Value &Arg :
F.args())
1682 ConstraintInfo
Info(
F.getDataLayout(), FunctionArgs);
1683 State S(DT, LI, SE);
1684 std::unique_ptr<Module> ReproducerModule(
1703 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
1704 auto HasNoConstOp = [](const FactOrCheck &B) {
1705 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
1706 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
1707 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
1711 if (
A.NumIn ==
B.NumIn) {
1712 if (A.isConditionFact() && B.isConditionFact()) {
1713 bool NoConstOpA = HasNoConstOp(A);
1714 bool NoConstOpB = HasNoConstOp(B);
1715 return NoConstOpA < NoConstOpB;
1717 if (
A.isConditionFact())
1719 if (
B.isConditionFact())
1721 auto *InstA =
A.getContextInst();
1722 auto *InstB =
B.getContextInst();
1723 return InstA->comesBefore(InstB);
1725 return A.NumIn <
B.NumIn;
1733 for (FactOrCheck &CB : S.WorkList) {
1736 while (!DFSInStack.
empty()) {
1737 auto &E = DFSInStack.
back();
1738 LLVM_DEBUG(
dbgs() <<
"Top of stack : " << E.NumIn <<
" " << E.NumOut
1740 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
1741 assert(E.NumIn <= CB.NumIn);
1742 if (CB.NumOut <= E.NumOut)
1745 dbgs() <<
"Removing ";
1747 Info.getValue2Index(E.IsSigned));
1757 Instruction *Inst = CB.getInstructionToSimplify();
1760 LLVM_DEBUG(
dbgs() <<
"Processing condition to simplify: " << *Inst
1762 if (
auto *
II = dyn_cast<WithOverflowInst>(Inst)) {
1764 }
else if (
auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
1766 Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
1767 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
1772 ReproducerCondStack, DFSInStack);
1775 }
else if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
1777 }
else if (
auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {
1789 <<
"Skip adding constraint because system has too many rows.\n");
1793 Info.addFact(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1794 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
1797 Info.transferToOtherSystem(Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
1798 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
1801 for (
unsigned I = 0,
1802 E = (DFSInStack.
size() - ReproducerCondStack.
size());
1804 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
1811 if (!CB.isConditionFact()) {
1813 if (
match(CB.Inst, m_Intrinsic<Intrinsic::abs>(
m_Value(
X)))) {
1815 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
1817 ConstantInt::get(CB.Inst->getType(), 0));
1822 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
1823 Pred = ICmpInst::getNonStrictPredicate(
MinMax->getPredicate());
1830 Value *
A =
nullptr, *
B =
nullptr;
1831 if (CB.isConditionFact()) {
1832 Pred = CB.Cond.Pred;
1836 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
1838 dbgs() <<
"Not adding fact ";
1840 dbgs() <<
" because precondition ";
1843 dbgs() <<
" does not hold.\n";
1848 bool Matched =
match(CB.Inst, m_Intrinsic<Intrinsic::assume>(
1851 assert(Matched &&
"Must have an assume intrinsic with a icmp operand");
1853 AddFact(Pred,
A,
B);
1856 if (ReproducerModule && !ReproducerModule->functions().empty()) {
1859 ReproducerModule->print(StringS,
nullptr);
1862 Rem <<
ore::NV(
"module") << S;
1867 unsigned SignedEntries =
1868 count_if(DFSInStack, [](
const StackEntry &E) {
return E.IsSigned; });
1869 assert(
Info.getCS(
false).size() - FunctionArgs.size() ==
1870 DFSInStack.
size() - SignedEntries &&
1871 "updates to CS and DFSInStack are out of sync");
1872 assert(
Info.getCS(
true).size() == SignedEntries &&
1873 "updates to CS and DFSInStack are out of sync");
1877 I->eraseFromParent();
ReachingDefAnalysis InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
std::pair< ICmpInst *, unsigned > ConditionTy
static int64_t MaxConstraintValue
static int64_t MinSignedConstraintValue
static Instruction * getContextInstForUse(Use &U)
static Decomposition decomposeGEP(GEPOperator &GEP, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool canUseSExt(ConstantInt *CI)
static int64_t multiplyWithOverflow(int64_t A, int64_t B)
static void dumpConstraint(ArrayRef< int64_t > C, const DenseMap< Value *, unsigned > &Value2Index)
static void removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
static std::optional< bool > checkCondition(CmpInst::Predicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info)
static cl::opt< unsigned > MaxRows("constraint-elimination-max-rows", cl::init(500), cl::Hidden, cl::desc("Maximum number of rows to keep in constraint system"))
static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, OptimizationRemarkEmitter &ORE)
static int64_t addWithOverflow(int64_t A, int64_t B)
static cl::opt< bool > DumpReproducers("constraint-elimination-dump-reproducers", cl::init(false), cl::Hidden, cl::desc("Dump IR to reproduce successful transformations."))
static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL)
static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static void generateReproducer(CmpInst *Cond, Module *M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)
Helper function to generate a reproducer function for simplifying Cond.
static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
static bool checkOrAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack)
Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second ...
static Decomposition decompose(Value *V, SmallVectorImpl< ConditionTy > &Preconditions, bool IsSigned, const DataLayout &DL)
static bool replaceSubOverflowUses(IntrinsicInst *II, Value *A, Value *B, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)
static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
std::optional< std::vector< StOtherPiece > > Other
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This is the interface for a simple mod/ref and alias analysis over globals.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
static StringRef getName(Value *V)
const SmallVectorImpl< MachineOperand > & Cond
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file 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 class represents a ucmp/scmp intrinsic.
This is the shared class of boolean and integer constants.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This is an important base class in LLVM.
static Constant * getAllOnesValue(Type *Ty)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
DenseMap< Value *, unsigned > & getValue2Index()
static SmallVector< int64_t, 8 > negate(SmallVector< int64_t, 8 > R)
bool isConditionImplied(SmallVector< int64_t, 8 > R) const
static SmallVector< int64_t, 8 > toStrictLessThan(SmallVector< int64_t, 8 > R)
Converts the given vector to form a strict less than inequality.
bool addVariableRow(ArrayRef< int64_t > R)
static SmallVector< int64_t, 8 > negateOrEqual(SmallVector< int64_t, 8 > R)
Multiplies each coefficient in the given vector by -1.
bool addVariableRowFill(ArrayRef< int64_t > R)
void dump() const
Print the constraints in the system.
A parsed version of the target data layout string in and methods for querying it.
static bool shouldExecute(unsigned CounterName)
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
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 dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs=std::nullopt)
Drop all unknown metadata except for debug locations.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class 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.