55#define DEBUG_TYPE "constraint-elimination"
57STATISTIC(NumCondsRemoved,
"Number of instructions removed");
59 "Controls which conditions are eliminated");
67 UserI = Phi->getIncomingBlock(U)->getTerminator();
76 for (
Use &U :
I.uses()) {
140 FactOrCheck(EntryTy Ty,
DomTreeNode *DTN, Instruction *Inst,
141 Instruction *ContextInst =
nullptr)
142 : Inst(Inst), ContextInst(ContextInst ? ContextInst : Inst),
143 NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), Ty(Ty) {}
146 :
U(
U), ContextInst(nullptr), NumIn(DTN->getDFSNumIn()),
147 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::UseCheck) {}
151 :
Cond(
Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
152 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
154 static FactOrCheck getConditionFact(
DomTreeNode *DTN, CmpPredicate
Pred,
157 return FactOrCheck(DTN,
Pred, Op0, Op1, Precond);
160 static FactOrCheck getInstFact(
DomTreeNode *DTN, Instruction *Inst) {
161 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
164 static FactOrCheck getCheck(
DomTreeNode *DTN, Use *U) {
165 return FactOrCheck(DTN, U);
168 static FactOrCheck getCheck(
DomTreeNode *DTN, Instruction *
I,
169 Instruction *ContextInst =
nullptr) {
171 "anchoring instruction must be in DTN's block");
172 return FactOrCheck(EntryTy::InstCheck, DTN,
I, ContextInst);
175 bool isCheck()
const {
176 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
180 assert(!isConditionFact());
181 if (Ty == EntryTy::UseCheck)
188 if (Ty == EntryTy::InstCheck)
194 bool isConditionFact()
const {
return Ty == EntryTy::ConditionFact; }
199struct MonotonicInfo {
201 bool Decreasing =
false;
203 bool Unsigned =
false;
214 TargetLibraryInfo &TLI;
217 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE,
218 TargetLibraryInfo &TLI)
219 : DT(DT), LI(LI), SE(SE), TLI(TLI) {}
222 void addInfoFor(BasicBlock &BB);
226 void addBoundsForHeaderInductions(BasicBlock &BB);
230 void addInfoForInductions(BasicBlock &BB);
234 MonotonicInfo getMonotonicityInfo(PHINode &PN,
Value *Step);
238 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ)
const {
239 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
248 bool IsSigned =
false;
251 SmallVector<Value *, 2> ValuesToRelease;
253 StackEntry(
unsigned NumIn,
unsigned NumOut,
bool IsSigned,
254 SmallVector<Value *, 2> ValuesToRelease)
255 : NumIn(NumIn), NumOut(NumOut), IsSigned(IsSigned),
256 ValuesToRelease(std::
move(ValuesToRelease)) {}
263 unsigned NumVars = 0;
265 bool IsSigned =
false;
267 ConstraintTy() =
default;
269 ConstraintTy(RowTy Coefficients,
unsigned NumVars,
bool IsSigned,
bool IsEq,
271 : Coefficients(std::
move(Coefficients)), NumVars(NumVars),
272 IsSigned(IsSigned), IsEq(IsEq), IsNe(IsNe) {}
274 bool empty()
const {
return Coefficients.empty(); }
276 bool isEq()
const {
return IsEq; }
278 bool isNe()
const {
return IsNe; }
285 std::optional<bool> isImpliedBy(
const ConstraintSystem &CS)
const;
297 DecompEntry(int64_t Coefficient,
Value *Variable)
298 : Coefficient(Coefficient), Variable(Variable) {}
302struct Decomposition {
306 Decomposition(int64_t Offset) : Offset(Offset) {}
307 Decomposition(
Value *
V) { Vars.emplace_back(1,
V); }
309 : Offset(Offset), Vars(Vars) {}
313 [[nodiscard]]
bool add(int64_t OtherOffset) {
319 [[nodiscard]]
bool add(
const Decomposition &
Other) {
328 [[nodiscard]]
bool sub(
const Decomposition &
Other) {
329 Decomposition Tmp =
Other;
340 [[nodiscard]]
bool mul(int64_t Factor) {
343 for (
auto &Var : Vars)
344 if (
MulOverflow(Var.Coefficient, Factor, Var.Coefficient))
356class ConstraintInfo {
358 ConstraintSystem UnsignedCS;
359 ConstraintSystem SignedCS;
361 const DataLayout &DL;
365 DenseMap<PointerIntPair<Value *, 1, bool>, Decomposition> DecomposeCache;
368 DenseMap<PointerIntPair<Value *, 1, bool>, Decomposition> &
369 getDecomposeCache() {
370 return DecomposeCache;
374 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {
375 auto &Value2Index = getValue2Index(
false);
377 for (
Value *Arg : FunctionArgs)
378 UnsignedCS.addRow({
Entry(0, 0),
Entry(-1, Value2Index.at(Arg))},
382 DenseMap<Value *, unsigned> &getValue2Index(
bool Signed) {
383 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
385 const DenseMap<Value *, unsigned> &getValue2Index(
bool Signed)
const {
386 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
389 ConstraintSystem &getCS(
bool Signed) {
390 return Signed ? SignedCS : UnsignedCS;
392 const ConstraintSystem &getCS(
bool Signed)
const {
393 return Signed ? SignedCS : UnsignedCS;
396 void popLastConstraint(
bool Signed) {
397 assert(DecomposeCache.empty() &&
"Cache must be cleared");
398 getCS(
Signed).popLastConstraint();
400 void popLastNVariables(
bool Signed,
unsigned N) {
401 assert(DecomposeCache.empty() &&
"Cache must be cleared");
402 getCS(
Signed).popLastNVariables(
N);
412 function_ref<std::optional<bool>()> Solve);
428 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
435 SmallVectorImpl<Value *> &NewVariables,
436 bool ForceSignedSystem =
false);
451 unsigned NumIn,
unsigned NumOut,
452 SmallVectorImpl<StackEntry> &DFSInStack);
459 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,
460 bool ForceSignedSystem);
464 void tightenBoundUsingNe(
Value *
A,
Value *
B,
unsigned NumIn,
unsigned NumOut,
465 SmallVectorImpl<StackEntry> &DFSInStack);
471 APInt ConstantOffset;
472 SmallMapVector<Value *, APInt, 4> VariableOffsets;
477 OffsetResult(GEPOperator &
GEP,
const DataLayout &
DL)
479 ConstantOffset = APInt(
DL.getIndexTypeSizeInBits(
BasePtr->getType()), 0);
489 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
491 Result.ConstantOffset))
499 bool CanCollectInner = InnerGEP->collectOffset(
500 DL,
BitWidth, VariableOffsets2, ConstantOffset2);
502 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
503 VariableOffsets2.
size() > 1 ||
504 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.
size() >= 1)) {
510 bool Overflow =
false;
511 APInt CombinedOffset =
512 Result.ConstantOffset.sadd_ov(ConstantOffset2, Overflow);
516 Result.BasePtr = InnerGEP->getPointerOperand();
517 Result.ConstantOffset = CombinedOffset;
518 if (Result.VariableOffsets.size() == 0 && VariableOffsets2.
size() == 1)
519 Result.VariableOffsets = std::move(VariableOffsets2);
520 Result.NW &= InnerGEP->getNoWrapFlags();
525static Decomposition
decompose(
Value *
V, ConstraintInfo &Info,
bool IsSigned,
541 int64_t RequiredOffset = -
static_cast<int64_t
>(Slack.
getZExtValue());
543 const auto &Value2Index = Info.getValue2Index(
Signed);
544 unsigned OpIdx = Value2Index.lookup(
Op);
548 int64_t OpCoefficient =
Upper ? 1 : -1;
549 unsigned OpSize =
Op->getType()->getScalarSizeInBits();
553 if (Row.size() != 3 || Row[0].Id != 0 ||
554 Row[0].Coefficient > RequiredOffset)
556 bool OpFirst = Row[1].Id == OpIdx;
557 const Entry &OpE = Row[OpFirst ? 1 : 2];
558 const Entry &WitnessE = Row[OpFirst ? 2 : 1];
559 if (OpE.Id != OpIdx || OpE.Coefficient != OpCoefficient ||
560 WitnessE.Coefficient != -OpCoefficient)
564 Value2Index, [&](
const auto &KV) {
return KV.second == WitnessE.Id; });
565 assert(Witness != Value2Index.end() &&
"row variables must be mapped");
566 Type *WitnessTy = Witness->first->getType();
577 if (R.isEmptySet() || (
Signed ? R.isSignWrappedSet() : R.isWrappedSet()))
583 unsigned BitWidth = R.getBitWidth();
584 APInt Min =
Signed ? R.getSignedMin() : R.getUnsignedMin();
585 APInt Max =
Signed ? R.getSignedMax() : R.getUnsignedMax();
591 APInt UpperSlack = MaxVal - Max;
599 ConstantInt::get(Ty, Min)) &&
604 ConstantInt::get(Ty, Max)) &&
613 unsigned NoWrapFlags, ConstraintInfo &Info,
617 if (NoWrapFlags & (
Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap))
620 if (Opcode == Instruction::Sub) {
626 if (Info.isKnownNonNegative(Op1) &&
631 if (!
Signed && (NoWrapFlags & OBO::NoSignedWrap) &&
632 (Opcode == Instruction::Shl || Info.isKnownNonNegative(Op1)) &&
633 Info.isKnownNonNegative(Op0))
644 Opcode,
C->getValue(),
645 Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap),
656 return isKnownNoWrap(WO->getBinaryOp(), WO->getLHS(), WO->getRHS(),
661 return Trunc->hasNoSignedWrap();
665 return Trunc->hasNoUnsignedWrap() ||
666 (Trunc->hasNoSignedWrap() &&
667 Info.isKnownNonNegative(Trunc->getOperand(0)));
673 BO->getOperand(0), BO->getOperand(1),
674 BO->getNoWrapKind(), Info,
Signed);
681 if (
DL.getIndexTypeSizeInBits(
GEP.getPointerOperand()->getType()) > 64)
684 assert(!IsSigned &&
"The logic below only supports decomposition for "
685 "unsigned predicates at the moment.");
686 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =
695 if (!NW.hasNoUnsignedSignedWrap() && ConstantOffset.isNegative())
698 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
699 for (
auto [Index, Scale] : VariableOffsets) {
702 if (Index->getType()->getScalarSizeInBits() != Scale.getBitWidth())
704 if (!NW.hasNoUnsignedWrap()) {
707 assert(NW.hasNoUnsignedSignedWrap() &&
"Must have nusw flag");
708 if (!Info.isKnownNonNegative(Index))
710 }
else if (!NW.hasNoUnsignedSignedWrap()) {
713 if (Scale.isNegative())
717 auto IdxResult =
decompose(Index, Info, IsSigned,
DL);
718 if (IdxResult.mul(Scale.getSExtValue()))
720 if (Result.add(IdxResult))
740 switch (
Op->getOpcode()) {
741 case Instruction::GetElementPtr:
742 case Instruction::Add:
743 case Instruction::Sub:
744 case Instruction::Mul:
745 case Instruction::Shl:
746 case Instruction::LShr:
747 case Instruction::AShr:
748 case Instruction::ZExt:
749 case Instruction::SExt:
750 case Instruction::Trunc:
751 case Instruction::Or:
752 case Instruction::Xor:
765 auto &Cache = Info.getDecomposeCache();
766 auto It = Cache.find(
Key);
767 if (It != Cache.end())
771 Info.getDecomposeCache().insert({
Key, Result});
777 auto MergeResults = [&Info, IsSigned,
779 bool IsSignedB) -> std::optional<Decomposition> {
787 Type *Ty =
V->getType()->getScalarType();
788 if (Ty->isPointerTy() && !IsSigned) {
800 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)
806 return CI->getSExtValue();
808 return int64_t(CI->getZExtValue());
824 if (!IsSigned && !Info.isKnownNonNegative(Op0))
828 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64 &&
830 V = Trunc->getOperand(0);
835 if (
auto Decomp = MergeResults(Op0, Op1, IsSigned))
845 if (
auto Decomp = MergeResults(Op0, CI,
true))
852 Decomposition Result(-1);
853 if (!Result.sub(
decompose(Op0, Info, IsSigned,
DL)))
883 (IsSigned == IsAShr || Info.isKnownNonNegative(Op0))) {
886 if (Result.Offset % Factor == 0 &&
887 all_of(Result.Vars, [Factor](
const DecompEntry &
E) {
888 return E.Coefficient % Factor == 0;
890 Result.Offset /= Factor;
891 for (
auto &
E : Result.Vars)
892 E.Coefficient /= Factor;
903 int64_t MaxShift = IsSigned ? Ty->getIntegerBitWidth() - 1 : 63;
921 const Decomposition &BDec,
927 if (
SubOverflow(BDec.Offset, ADec.Offset, OffsetSum))
929 RowTy R(1, Entry(OffsetSum, 0));
930 auto GetCoefficient = [&R](
unsigned Idx) -> int64_t & {
935 if (
I == R.end() ||
I->Id != Idx)
936 I = R.insert(
I, Entry(0, Idx));
937 return I->Coefficient;
941 auto GetOrAddIndex = [&Value2Index, &NewVariables](
Value *
V) ->
unsigned {
942 auto V2I = Value2Index.
find(
V);
943 if (V2I != Value2Index.
end())
945 unsigned Idx =
find(NewVariables,
V) - NewVariables.
begin();
946 if (Idx == NewVariables.
size())
948 return Value2Index.
size() + Idx + 1;
950 for (
const DecompEntry &KV : ADec.Vars)
951 GetCoefficient(GetOrAddIndex(KV.Variable)) += KV.Coefficient;
953 for (
const DecompEntry &KV : BDec.Vars) {
954 auto &Coeff = GetCoefficient(GetOrAddIndex(KV.Variable));
960 erase_if(R, [](
const Entry &
E) {
return E.Id != 0 &&
E.Coefficient == 0; });
967 bool ForceSignedSystem) {
968 assert(NewVariables.
empty() &&
"NewVariables must be empty when passed in");
970 "signed system can only be forced on eq/ne");
1011 auto &Value2Index = getValue2Index(IsSigned);
1021 if (
AddOverflow(R[0].Coefficient, int64_t(-1), R[0].Coefficient))
1025 unsigned NumV2I = Value2Index.size();
1026 NewVariables.
truncate(
R.back().Id > NumV2I ?
R.back().Id - NumV2I : 0);
1028 return ConstraintTy(std::move(R), Value2Index.size() + NewVariables.
size(),
1029 IsSigned, IsEq, IsNe);
1040 return ConstraintTy(RowTy(1,
Entry(0, 0)), 0,
1041 false,
false,
false);
1053 ConstraintTy
R = getConstraint(
Pred, Op0, Op1, NewVariables);
1054 if (!NewVariables.
empty())
1060ConstraintTy::isImpliedBy(
const ConstraintSystem &CS)
const {
1061 const auto &[SubCS, NewCoefficients] = CS.
getSubSystem(Coefficients);
1062 bool IsConditionImplied = SubCS.isConditionImplied(NewCoefficients);
1066 bool IsNegatedOrEqualImplied =
1067 !NegatedOrEqual.empty() && SubCS.isConditionImplied(NegatedOrEqual);
1072 if (IsConditionImplied && IsNegatedOrEqualImplied)
1076 bool IsNegatedImplied =
1077 !Negated.empty() && SubCS.isConditionImplied(Negated);
1080 bool IsStrictLessThanImplied =
1081 !StrictLessThan.empty() && SubCS.isConditionImplied(StrictLessThan);
1087 if (IsNegatedImplied || IsStrictLessThanImplied)
1090 return std::nullopt;
1093 if (IsConditionImplied)
1097 auto IsNegatedImplied = !Negated.empty() && SubCS.isConditionImplied(Negated);
1098 if (IsNegatedImplied)
1102 return std::nullopt;
1106 ConstraintInfo &Info,
1107 const DataLayout &
DL);
1110ConstraintInfo::tryWithLinkRows(
Value *
A,
Value *
B,
const ConstraintTy &
C,
1111 function_ref<std::optional<bool>()> Solve) {
1112 if (std::optional<bool> Res = Solve())
1115 return std::nullopt;
1117 auto &CS = getCS(
C.IsSigned);
1118 unsigned NumVars = getValue2Index(
C.IsSigned).size();
1119 unsigned NumPushed = 0;
1123 if (Row.empty() || Negated.empty())
1125 NumPushed += CS.
addRow(Row, NumVars);
1126 NumPushed += CS.
addRow(Negated, NumVars);
1129 return std::nullopt;
1131 unsigned NumRows = CS.
size();
1133 std::optional<bool> Res = Solve();
1134 assert(CS.
size() == NumRows &&
"rows added while link rows are pushed");
1141 auto R = getConstraintForSolving(
Pred,
A,
B);
1144 auto &CS = getCS(
R.IsSigned);
1145 return tryWithLinkRows(
A,
B, R,
1146 [&]() -> std::optional<bool> {
1149 return std::nullopt;
1154bool ConstraintInfo::isKnownNonNegative(
Value *
V) {
1156 return !CI->isNegative();
1157 return ::isKnownNonNegative(
V,
DL) ||
1161bool ConstraintInfo::isKnownPositive(
Value *
V) {
1163 return CI->getValue().isStrictlyPositive();
1164 return ::isKnownPositive(
V,
DL) ||
1168std::optional<bool> ConstraintInfo::getKnownSign(
Value *
V) {
1170 if (
Known.isNonNegative())
1172 if (
Known.isNegative())
1179 return std::nullopt;
1182void ConstraintInfo::transferToOtherSystem(
1184 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
1187 if (!
A->getType()->isIntegerTy())
1200 NumOut, DFSInStack);
1210 NumOut, DFSInStack);
1224 NumOut, DFSInStack);
1250static std::pair<Value *, Value *>
1253 "LoopPred must be a predecessor of the phi's block");
1255 return {
nullptr,
nullptr};
1262template <
typename PhiMatchTy>
1271MonotonicInfo State::getMonotonicityInfo(PHINode &PN,
Value *Step) {
1273 const APInt *StepOffset =
nullptr;
1277 Info.Unsigned = !
Info.Decreasing &&
Add->hasNoUnsignedWrap();
1278 Info.Signed =
Add->hasNoSignedWrap();
1284 APInt GEPOffset(
DL.getIndexTypeSizeInBits(
GEP->getType()), 0);
1285 Info.Unsigned =
GEP->getPointerOperand() == &PN &&
1286 (
GEP->hasNoUnsignedWrap() ||
1287 ((
GEP->hasNoUnsignedSignedWrap() &&
1288 GEP->accumulateConstantOffset(
DL, GEPOffset) &&
1289 !GEPOffset.isNegative())));
1294 if (
Info.Unsigned ||
Info.Signed || !StepOffset)
1311void State::addBoundsForHeaderInductions(BasicBlock &BB) {
1313 if (!L ||
L->getHeader() != &BB)
1320 for (PHINode &PN : BB.
phis()) {
1328 MonotonicInfo
Info = getMonotonicityInfo(PN, Step);
1332 Info.Unsigned =
false;
1333 if (!
Info.Unsigned && !
Info.Signed)
1339 if (
Info.Decreasing)
1347void State::addInfoForInductions(BasicBlock &BB) {
1354 if (Header != &BB && Latch != &BB)
1361 PHINode *PN =
nullptr;
1362 const APInt *IncStep =
nullptr;
1372 std::optional<bool> PeeledOnEdge;
1373 if (!
match(Br->getCondition(), CountingCmp)) {
1377 PeeledOnEdge =
true;
1379 PeeledOnEdge =
false;
1388 bool ContinueOnTrue =
1392 BasicBlock *InLoopSucc = Br->getSuccessor(ContinueOnTrue ? 0 : 1);
1396 if (PeeledOnEdge && *PeeledOnEdge != ContinueOnTrue)
1399 if (!
L->contains(InLoopSucc) || !
L->isLoopExiting(&BB))
1403 if (!LoopPred || !
L->isLoopInvariant(
B))
1415 bool HasHeaderBound =
1419 if (HasHeaderBound) {
1421 WorkList.
push_back(FactOrCheck::getConditionFact(
1422 HeaderDTN, BoundPred, PN,
B,
ConditionTy(BoundPred, StartValue,
B)));
1431 if (&BB == Latch && !IncStep)
1441 WorkList.
push_back(FactOrCheck::getConditionFact(
1442 HeaderDTN, ContinuePred, PN,
B,
1448 if (ICmpInst::isSigned(ContinuePred)) {
1451 "Expected a signed less-than continuation predicate");
1452 MonotonicInfo
Info = getMonotonicityInfo(*PN, Backedge);
1453 if (
Info.Signed && !
Info.Decreasing) {
1455 WorkList.
push_back(FactOrCheck::getConditionFact(
1456 HeaderDTN, UPred, PN,
B,
ConditionTy(UPred, StartValue,
B)));
1465 const APInt *StepOffset =
nullptr;
1466 const SCEV *StartSCEV =
nullptr;
1468 if (StepOffset->
isZero())
1471 const SCEV *Expr = SE->
getSCEV(PN);
1480 if (IncStep && *IncStep != *StepOffset)
1483 MonotonicInfo
Info = getMonotonicityInfo(*PN, Backedge);
1488 if (!(-*StepOffset).isOne())
1498 ConditionTy BBeforeStartUnsigned = {UPrecond,
B, StartValue};
1504 WorkList.
push_back(FactOrCheck::getConditionFact(
1506 if (!(
Info.Decreasing &&
Info.Signed))
1507 WorkList.
push_back(FactOrCheck::getConditionFact(
1511 B, BBeforeStartUnsigned));
1513 B, BBeforeStartSigned));
1523 if (!StepOffset->
isOne()) {
1526 StartSCEV = SE->
getSCEV(StartValue);
1540 ConditionTy StartBeforeBoundUnsigned = {UPrecond, StartValue,
B};
1546 WorkList.
push_back(FactOrCheck::getConditionFact(
1549 WorkList.
push_back(FactOrCheck::getConditionFact(
1554 if (!HasHeaderBound || !canAddSuccessor(BB, InLoopSucc)) {
1555 WorkList.
push_back(FactOrCheck::getConditionFact(
1557 WorkList.
push_back(FactOrCheck::getConditionFact(
1570 L->getExitBlocks(ExitBBs);
1571 for (BasicBlock *EB : ExitBBs) {
1585 if (!
GEP.hasNoUnsignedWrap())
1590 Base = InnerGEP->getPointerOperand();
1606 if (
Offset.VariableOffsets.size() != 1)
1610 auto &[Index, Scale] =
Offset.VariableOffsets.front();
1612 if (Index->getType()->getScalarSizeInBits() !=
BitWidth)
1625 B = ConstantInt::get(Index->getType(), MaxIndex);
1633 return Trunc->getType()->isIntegerTy() && Trunc->hasNoSignedWrap() &&
1634 !Trunc->hasNoUnsignedWrap();
1637 if (!BO || !BO->getType()->isIntegerTy())
1640 switch (BO->getOpcode()) {
1641 case Instruction::Sub:
1642 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1647 case Instruction::Add:
1648 case Instruction::Mul:
1649 case Instruction::Shl:
1650 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1669 I->setHasNoSignedWrap();
1674 I->setHasNoUnsignedWrap();
1680void State::addInfoFor(BasicBlock &BB) {
1681 addBoundsForHeaderInductions(BB);
1682 addInfoForInductions(BB);
1688 bool GuaranteedToExecute =
true;
1690 for (Instruction &
I : BB) {
1692 for (Use &U :
I.uses()) {
1694 auto *DTN = DT.
getNode(UserI->getParent());
1697 WorkList.
push_back(FactOrCheck::getCheck(DTN, &U));
1702 auto AddFactFromMemoryAccess = [&](
Value *Ptr,
Type *AccessType) {
1706 TypeSize AccessSize =
DL.getTypeStoreSize(AccessType);
1709 if (GuaranteedToExecute) {
1719 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1724 if (!LI->isVolatile())
1725 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());
1728 if (!
SI->isVolatile())
1729 AddFactFromMemoryAccess(
SI->getPointerOperand(),
SI->getAccessType());
1735 case Intrinsic::assume: {
1738 if (GuaranteedToExecute) {
1745 FactOrCheck::getInstFact(DT.
getNode(
I.getParent()), &
I));
1750 case Intrinsic::uadd_with_overflow:
1751 case Intrinsic::sadd_with_overflow:
1752 case Intrinsic::usub_with_overflow:
1753 case Intrinsic::ssub_with_overflow:
1754 case Intrinsic::umul_with_overflow:
1755 case Intrinsic::smul_with_overflow:
1756 case Intrinsic::ucmp:
1757 case Intrinsic::scmp:
1762 case Intrinsic::umin:
1763 case Intrinsic::umax:
1764 case Intrinsic::smin:
1765 case Intrinsic::smax:
1766 case Intrinsic::usub_sat:
1771 case Intrinsic::uadd_sat:
1777 case Intrinsic::abs:
1792 if ((BO->getOpcode() == Instruction::URem ||
1793 BO->getOpcode() == Instruction::UDiv ||
1794 BO->getOpcode() == Instruction::LShr ||
1795 BO->getOpcode() == Instruction::SRem ||
1796 BO->getOpcode() == Instruction::SDiv) &&
1805 WorkList.
push_back(FactOrCheck::getCheck(
1813 for (
auto &Case :
Switch->cases()) {
1815 Value *
V = Case.getCaseValue();
1816 if (!canAddSuccessor(BB, Succ))
1845 SmallPtrSet<Value *, 8> SeenCond;
1846 auto QueueValue = [&CondWorkList, &SeenCond](
Value *
V) {
1847 if (SeenCond.
insert(
V).second)
1852 while (!CondWorkList.
empty()) {
1877 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1880 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1888 OS <<
"icmp " <<
Pred <<
' ';
1889 LHS->printAsOperand(OS,
true);
1891 RHS->printAsOperand(OS,
false);
1900struct ReproducerEntry {
1901 ICmpInst::Predicate
Pred;
1936 auto &Value2Index = Info.getValue2Index(IsSigned);
1938 while (!WorkList.
empty()) {
1942 if (Old2New.
find(
V) != Old2New.
end())
1948 if (Value2Index.contains(
V) || !
I ||
1959 for (
auto &Entry : Stack)
1962 CollectArguments(
Cond, IsSigned);
1965 for (
auto *
P : Args)
1971 Cond->getModule()->getName() +
1972 Cond->getFunction()->getName() +
"repro",
1975 for (
unsigned I = 0;
I < Args.size(); ++
I) {
1977 Old2New[Args[
I]] =
F->getArg(
I);
1982 Builder.CreateRet(Builder.getTrue());
1983 Builder.SetInsertPoint(Entry->getTerminator());
1992 auto &Value2Index = Info.getValue2Index(IsSigned);
1993 while (!WorkList.
empty()) {
1995 if (Old2New.
find(
V) != Old2New.
end())
1999 if (!Value2Index.contains(
V) &&
I) {
2000 Old2New[
V] =
nullptr;
2010 Old2New[
I] = Cloned;
2011 Old2New[
I]->setName(
I->getName());
2023 for (
auto &Entry : Stack) {
2032 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
2033 Builder.CreateAssumption(Cmp);
2038 CloneInstructions(
Cond, IsSigned);
2039 Entry->getTerminator()->setOperand(0,
Cond);
2050 ConstraintInfo &Info,
2052 const auto &Value2Index = Info.getValue2Index(
C.IsSigned);
2053 auto It = Value2Index.find(
V);
2054 if (It == Value2Index.end() ||
2056 [Id = It->second](
const Entry &
E) { return E.Id == Id; }))
2062 Value2Index, NewVariables);
2063 return NewVariables.
empty() ? Row : RowTy();
2068 ConstraintInfo &Info) {
2071 auto TryWithConstraint = [&](
const ConstraintTy &R) -> std::optional<bool> {
2074 return std::nullopt;
2077 auto &CSToUse = Info.getCS(R.IsSigned);
2078 if (
auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
2080 return std::nullopt;
2082 dbgs() <<
"Condition ";
2084 *ImpliedCondition ?
Pred
2087 dbgs() <<
" implied by dominating constraints\n";
2090 return ImpliedCondition;
2092 return std::nullopt;
2097 auto TryWithLinkedDecomposition =
2098 [&](
const ConstraintTy &
C) -> std::optional<bool> {
2099 return Info.tryWithLinkRows(
A,
B,
C, [&] {
return TryWithConstraint(
C); });
2102 auto R = Info.getConstraintForSolving(
Pred,
A,
B);
2103 if (
auto ImpliedCondition = TryWithLinkedDecomposition(R))
2104 return ImpliedCondition;
2112 if (NewVariables.
empty() && !SR.empty() && Info.isKnownNonNegative(
A) &&
2113 Info.isKnownNonNegative(
B))
2114 if (
auto ImpliedCondition = TryWithConstraint(SR))
2115 return ImpliedCondition;
2121 const auto &Value2Index = Info.getValue2Index(
true);
2122 if (!Value2Index.contains(
A) && !Value2Index.contains(
B))
2123 return std::nullopt;
2126 auto SR = Info.getConstraint(
Pred,
A,
B, NewVariables,
2128 if (NewVariables.
empty()) {
2129 if (
auto ImpliedCondition = TryWithLinkedDecomposition(SR))
2130 return ImpliedCondition;
2133 return std::nullopt;
2138 ConstraintInfo &Info,
unsigned NumIn,
unsigned NumOut,
2142 auto ReplaceCmpWithConstant = [&](
Instruction *CheckInst,
bool IsTrue) {
2144 ReproducerCondStack, Info, DT);
2149 auto *DTN = DT.
getNode(UserI->getParent());
2152 if (UserI->getParent() == ContextInst->
getParent() &&
2153 UserI->comesBefore(ContextInst))
2159 return !
II ||
II->getIntrinsicID() != Intrinsic::assume;
2168 for (
auto *DVR : DVRUsers) {
2169 auto *DTN = DT.
getNode(DVR->getParent());
2173 auto *MarkedI = DVR->getInstruction();
2174 if (MarkedI->getParent() == ContextInst->
getParent() &&
2175 MarkedI->comesBefore(ContextInst))
2178 DVR->replaceVariableLocationOp(CheckInst, ConstantC);
2188 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2195 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2204 MinMax->replaceAllUsesWith(
MinMax->getOperand(UseLHS ? 0 : 1));
2213 return ReplaceMinMaxWithOperand(
MinMax, *ImpliedCondition);
2216 return ReplaceMinMaxWithOperand(
MinMax, !*ImpliedCondition);
2225 I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 1));
2235 I->replaceAllUsesWith(ConstantInt::get(
I->getType(), 0));
2253 Value *
Sub = Builder.CreateSub(
A,
B,
"",
true,
2254 Info.isKnownNonNegative(
A));
2256 Sub->takeName(USub);
2263 Module *ReproducerModule,
2266 Info.getDecomposeCache().clear();
2267 Info.popLastConstraint(
E.IsSigned);
2269 auto &Mapping = Info.getValue2Index(
E.IsSigned);
2270 for (
Value *
V :
E.ValuesToRelease)
2272 Info.popLastNVariables(
E.IsSigned,
E.ValuesToRelease.size());
2274 if (ReproducerModule)
2281 FactOrCheck &CB, ConstraintInfo &Info,
Module *ReproducerModule,
2290 unsigned OtherOpIdx = JoinOp->
getOperand(0) == CmpToCheck ? 1 : 0;
2298 unsigned OldSize = DFSInStack.
size();
2301 while (OldSize < DFSInStack.
size()) {
2302 StackEntry
E = DFSInStack.
back();
2310 while (!Worklist.empty()) {
2311 Value *Val = Worklist.pop_back_val();
2319 Info.addFact(
Pred,
LHS,
RHS, CB.NumIn, CB.NumOut, DFSInStack);
2324 Worklist.push_back(
LHS);
2325 Worklist.push_back(
RHS);
2328 if (OldSize == DFSInStack.
size())
2333 [[maybe_unused]]
bool Matched =
2335 assert(Matched &&
"expected icmp-like match");
2338 if (IsOr == *ImpliedCondition)
2351 unsigned NumIn,
unsigned NumOut,
2352 SmallVectorImpl<StackEntry> &DFSInStack) {
2353 addFactImpl(
Pred,
A,
B, NumIn, NumOut, DFSInStack,
false);
2356 addFactImpl(
Pred,
A,
B, NumIn, NumOut, DFSInStack,
true);
2358 tightenBoundUsingNe(
A,
B, NumIn, NumOut, DFSInStack);
2361void ConstraintInfo::tightenBoundUsingNe(
2363 SmallVectorImpl<StackEntry> &DFSInStack) {
2364 if (!
A->getType()->isIntOrPtrTy())
2367 for (
bool IsSigned : {
false,
true}) {
2374 const auto &Value2Index = getValue2Index(IsSigned);
2376 [&Value2Index](
const DecompEntry &
E) {
2377 return !Value2Index.contains(
E.Variable);
2388 if (!doesHold(NonStrict,
A,
B))
2394 dbgs() <<
"' using inequality\n");
2395 addFactImpl(
Strict,
A,
B, NumIn, NumOut, DFSInStack,
2403 unsigned NumIn,
unsigned NumOut,
2404 SmallVectorImpl<StackEntry> &DFSInStack,
2405 bool ForceSignedSystem) {
2407 auto R = getConstraint(
Pred,
A,
B, NewVariables, ForceSignedSystem);
2410 if (
R.empty() ||
R.isNe())
2413 auto &CSToUse = getCS(
R.IsSigned);
2417 if (!
R.isEq() && NewVariables.
empty()) {
2419 if (CSToUse.isImpliedBySingleRow(
R.Coefficients))
2424 bool Added = CSToUse.addRow(
R.Coefficients,
R.NumVars);
2428 DecomposeCache.
clear();
2432 SmallVector<Value *, 2> ValuesToRelease;
2433 auto &Value2Index = getValue2Index(
R.IsSigned);
2434 for (
Value *
V : NewVariables) {
2435 Value2Index.try_emplace(
V, Value2Index.size() + 1);
2440 dbgs() <<
" constraint: ";
2446 std::move(ValuesToRelease));
2449 for (
Value *
V : NewVariables) {
2451 CSToUse.addRow({
Entry(0, 0),
Entry(-1, Value2Index.at(
V))},
2452 Value2Index.size());
2454 SmallVector<Value *, 2>());
2460 for (Entry &
E :
R.Coefficients)
2463 CSToUse.addRow(
R.Coefficients,
R.NumVars);
2466 SmallVector<Value *, 2>());
2476 Value *Res =
nullptr;
2480 Res = Builder.CreateNoWrapBinOp(
II->getBinaryOp(),
II->getLHS(),
2487 U->replaceAllUsesWith(Builder.getFalse());
2492 if (U->use_empty()) {
2500 if (
II->use_empty()) {
2502 for (
Use &Arg :
II->args())
2526 ConstraintInfo Info(
F.getDataLayout(), FunctionArgs);
2527 State S(DT, LI, SE,
TLI);
2528 std::unique_ptr<Module> ReproducerModule(
2529 Opts.constraint_elimination_dump_reproducers
2530 ?
new Module(
F.getName(),
F.getContext())
2549 stable_sort(S.WorkList, [](
const FactOrCheck &
A,
const FactOrCheck &
B) {
2550 auto HasNoConstOp = [](const FactOrCheck &B) {
2551 Value *V0 = B.isConditionFact() ? B.Cond.Op0 : B.Inst->getOperand(0);
2552 Value *V1 = B.isConditionFact() ? B.Cond.Op1 : B.Inst->getOperand(1);
2553 return !isa<ConstantInt>(V0) && !isa<ConstantInt>(V1);
2557 if (
A.NumIn ==
B.NumIn) {
2558 if (A.isConditionFact() && B.isConditionFact()) {
2559 bool NoConstOpA = HasNoConstOp(A);
2560 bool NoConstOpB = HasNoConstOp(B);
2561 return NoConstOpA < NoConstOpB;
2563 if (
A.isConditionFact())
2565 if (
B.isConditionFact())
2567 auto *InstA =
A.getContextInst();
2568 auto *InstB =
B.getContextInst();
2569 return InstA->comesBefore(InstB);
2571 return A.NumIn <
B.NumIn;
2574 SmallVector<Instruction *>
ToRemove;
2579 for (FactOrCheck &CB : S.WorkList) {
2582 while (!DFSInStack.
empty()) {
2583 auto &
E = DFSInStack.
back();
2586 LLVM_DEBUG(
dbgs() <<
"CB: " << CB.NumIn <<
" " << CB.NumOut <<
"\n");
2588 if (CB.NumOut <=
E.NumOut)
2591 dbgs() <<
"Removing ";
2593 Info.getValue2Index(
E.IsSigned));
2605 Instruction *Inst = CB.getInstructionToSimplify();
2612 LLVM_DEBUG(
dbgs() <<
"Processing condition to simplify: " << *Inst
2618 Pred,
A,
B, Inst, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
2619 ReproducerModule.get(), ReproducerCondStack, S.DT,
ToRemove);
2623 CB, Info, ReproducerModule.get(), ReproducerCondStack, DFSInStack,
2642 Opts.constraint_elimination_max_rows) {
2645 <<
"Skip adding constraint because system has too many rows.\n");
2649 Info.addFact(
Pred,
A,
B, CB.NumIn, CB.NumOut, DFSInStack);
2650 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size())
2657 if (
Pred.hasSameSign()) {
2659 CB.NumIn, CB.NumOut, DFSInStack);
2662 if (
A->getType()->isIntegerTy()) {
2663 std::optional<bool> ASign =
Info.getKnownSign(
A);
2664 std::optional<bool> BSign =
Info.getKnownSign(
B);
2665 if (ASign.has_value() != BSign.has_value()) {
2666 bool IsNegative = ASign ? *ASign : *BSign;
2667 Value *OtherOp = ASign ?
B :
A;
2670 CB.NumIn, CB.NumOut, DFSInStack);
2674 Info.transferToOtherSystem(
Pred,
A,
B, CB.NumIn, CB.NumOut,
2689 SmallPtrSet<Value *, 4> Seen;
2690 while (!Worklist.
empty()) {
2693 if (!BO || BO->getOpcode() !=
Opc)
2695 for (
Value *
Op : {BO->getOperand(0), BO->getOperand(1)}) {
2699 Info.addFact(
Pred,
Op,
B, CB.NumIn, CB.NumOut, DFSInStack);
2704 if (ReproducerModule && DFSInStack.
size() > ReproducerCondStack.
size()) {
2707 for (
unsigned I = 0,
2708 E = (DFSInStack.
size() - ReproducerCondStack.
size());
2710 ReproducerCondStack.
emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
2716 if (!CB.isConditionFact()) {
2722 ConstantInt::get(CB.Inst->getType(), 0));
2728 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
2729 AddFact(
Pred, MinMax, MinMax->getLHS());
2730 AddFact(
Pred, MinMax, MinMax->getRHS());
2734 switch (USatI->getIntrinsicID()) {
2737 case Intrinsic::uadd_sat:
2738 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());
2739 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());
2741 case Intrinsic::usub_sat:
2742 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());
2749 if (BO->getOpcode() == Instruction::URem) {
2756 if (BO->getOpcode() == Instruction::UDiv) {
2761 if (BO->getOpcode() == Instruction::LShr) {
2766 if (BO->getOpcode() == Instruction::SRem) {
2767 Value *
X = BO->getOperand(0);
2768 Value *
N = BO->getOperand(1);
2786 if (BO->getOpcode() == Instruction::SDiv) {
2787 Value *
X = BO->getOperand(0);
2788 Value *
N = BO->getOperand(1);
2789 if (!
Info.isKnownNonNegative(
X) || !
Info.isKnownPositive(
N))
2792 bool IsStrict =
Info.isKnownPositive(
X) &&
2794 ConstantInt::get(
N->getType(), 1));
2801 auto &
DL =
F.getDataLayout();
2802 auto AddFactsAboutIndices = [&](
Value *Ptr,
Type *AccessType) {
2807 DL.getTypeStoreSize(AccessType).getFixedValue(),
Pred,
A,
B,
DL,
2813 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());
2817 AddFactsAboutIndices(
SI->getPointerOperand(),
SI->getAccessType());
2822 if (CB.isConditionFact()) {
2823 Pred = CB.Cond.Pred;
2827 !
Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
2829 dbgs() <<
"Not adding fact ";
2831 dbgs() <<
" because precondition ";
2834 dbgs() <<
" does not hold.\n";
2839 [[maybe_unused]]
bool Matched =
2843 "Must have an assume intrinsic with a icmp like operand");
2848 if (ReproducerModule && !ReproducerModule->functions().empty()) {
2850 raw_string_ostream StringS(S);
2851 ReproducerModule->print(StringS,
nullptr);
2852 OptimizationRemark Rem(
DEBUG_TYPE,
"Reproducer", &
F);
2853 Rem <<
ore::NV(
"module") << S;
2858 unsigned SignedEntries =
2859 count_if(DFSInStack, [](
const StackEntry &
E) {
return E.IsSigned; });
2860 assert(
Info.getCS(
false).size() - FunctionArgs.size() ==
2861 DFSInStack.
size() - SignedEntries &&
2862 "updates to CS and DFSInStack are out of sync");
2863 assert(
Info.getCS(
true).size() == SignedEntries &&
2864 "updates to CS and DFSInStack are out of sync");
2868 I->eraseFromParent();
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
ReachingDefInfo InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
std::pair< ICmpInst *, unsigned > ConditionTy
static int64_t MaxConstraintValue
static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, OptimizationRemarkEmitter &ORE, TargetLibraryInfo &TLI)
static bool canStrengthenFlags(Instruction *I)
Returns true if I is a candidate whose poison-generating flags may be strengthened using the constrai...
static bool doesHoldInRange(ConstraintInfo &Info, Value *Op, const ConstantRange &R, bool Signed)
Returns true if Info implies that Op is in R, interpreting R as a signed range if Signed is set and a...
static RowTy getDecompositionLinkRow(Value *V, const ConstraintTy &C, ConstraintInfo &Info, const DataLayout &DL)
If V is a variable in the system and constraint C does not contain V, we managed to decompose V at th...
static int64_t MinSignedConstraintValue
static bool tryToSimplifyOverflowMath(WithOverflowInst *II, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static auto m_IncrementOf(const PhiMatchTy &PhiM, const APInt *&Off)
Matches an increment of PhiM by a constant offset, captured in Off.
static Instruction * getContextInstForUse(Use &U)
static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1, unsigned NoWrapFlags, ConstraintInfo &Info, bool Signed)
Returns true if Opcode applied to Op0 and Op1 with NoWrapFlags is known to not wrap in signed or unsi...
static bool mayLookThrough(Value *V)
Returns true if V is an operation decomposeImpl can look through.
static bool canUseSExt(ConstantInt *CI)
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 Decomposition decompose(Value *V, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static bool checkOrAndOpImpliedByOther(FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule, SmallVectorImpl< ReproducerEntry > &ReproducerCondStack, SmallVectorImpl< StackEntry > &DFSInStack, SmallVectorImpl< Instruction * > &ToRemove)
Check if either the first condition of an AND or OR is implied by the (negated in case of OR) second ...
static OffsetResult collectOffsets(GEPOperator &GEP, const DataLayout &DL)
static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static bool tryToStrengthenFlags(Instruction *I, ConstraintInfo &Info)
Try to strengthen I's poison generating flags using Info.
static RowTy getRowForLessEqual(const Decomposition &ADec, const Decomposition &BDec, const DenseMap< Value *, unsigned > &Value2Index, SmallVectorImpl< Value * > &NewVariables)
Build the row for 'ADec <= BDec', using the indices from Value2Index.
static void dumpConstraint(ArrayRef< Entry > C, const DenseMap< Value *, unsigned > &Value2Index)
static bool replaceOverflowUses(WithOverflowInst *II, SmallVectorImpl< Instruction * > &ToRemove)
Replace the uses of II, which is known not to overflow, by the corresponding plain binary operation a...
static bool getConstraintFromMemoryAccess(GetElementPtrInst &GEP, uint64_t AccessSize, CmpPredicate &Pred, Value *&A, Value *&B, const DataLayout &DL, const TargetLibraryInfo &TLI)
static void dumpUnpackedICmp(raw_ostream &OS, ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
static void generateReproducer(Instruction *Cond, bool IsSigned, Module *M, ArrayRef< ReproducerEntry > Stack, ConstraintInfo &Info, DominatorTree &DT)
Helper function to generate a reproducer function for simplifying Cond.
static bool checkAndReplaceUSubSat(SaturatingInst *USub, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
Try to replace USub by a plain subtract, if Info proves it cannot saturate.
static bool hasLimitWitness(const ConstraintInfo &Info, Value *Op, const APInt &Slack, bool Signed, bool Upper)
Returns true if Op <= MaxVal - Slack holds in the system for Signed, by scanning it for a row of the ...
static bool checkAndReplaceCondition(CmpPredicate Pred, Value *A, Value *B, Instruction *CheckInst, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, Instruction *ContextInst, Module *ReproducerModule, ArrayRef< ReproducerEntry > ReproducerCondStack, DominatorTree &DT, SmallVectorImpl< Instruction * > &ToRemove)
static Instruction * findCommonDominatorOfUses(Instruction &I, DominatorTree &DT)
Returns the closest program point dominating all uses of I.
static Decomposition decomposeImpl(Value *V, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info, SmallVectorImpl< Instruction * > &ToRemove)
static std::pair< Value *, Value * > getStartAndBackedgeValue(const PHINode &PN, const BasicBlock *LoopPred)
Splits the induction phi PN into the start value, coming from the loop predecessor LoopPred,...
static Decomposition decomposeGEP(GEPOperator &GEP, ConstraintInfo &Info, bool IsSigned, const DataLayout &DL)
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
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.
static std::optional< bool > getKnownSign(Value *Op, const SimplifyQuery &SQ)
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
uint64_t IntrinsicInst * II
This file defines the PointerIntPair class.
static StringRef getName(Value *V)
SmallVector< MachineOperand, 4 > Cond
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
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.
uint64_t getZExtValue() const
Get zero extended value.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
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.
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool slt(const APInt &RHS) const
Signed less than comparison.
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
bool isOne() const
Determine if this is a value of 1.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Represents analyses that only rely on functions' control flow.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate getStrictPredicate() const
For example, SGE -> SGT, SLE -> SLT, ULE -> ULT, UGE -> UGT.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
static LLVM_ABI bool isEquality(Predicate pred)
Determine if this is an equals/not equals predicate.
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
This class represents a ucmp/scmp intrinsic.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
static LLVM_ABI CmpPredicate getInverse(CmpPredicate P)
Get the inverse predicate of a CmpPredicate.
This is the shared class of boolean and integer constants.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
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 ...
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
const APInt & getValue() const
Return the constant as an APInt value reference.
static LLVM_ABI ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
static LLVM_ABI ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
This is an important base class in LLVM.
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &)
bool addRow(ArrayRef< Entry > R, size_t NumVars)
static RowTy negate(RowTy R)
unsigned size() const
Returns the number of rows in the constraint system.
LLVM_ABI std::pair< ConstraintSystem, RowTy > getSubSystem(ArrayRef< Entry > R) const
Build and return a sub-system of constraints connected (transitively) to query R, with variables comp...
static RowTy toStrictLessThan(RowTy R)
Converts the given row to form a strict less than inequality.
static LLVM_ABI void normalizeByGCD(MutableArrayRef< Entry > R)
Divide the variable coefficients of R by their greatest common divisor G and round the constant down ...
LLVM_ABI bool isConditionImpliedInSubSystem(ArrayRef< Entry > R) const
SmallVector< Entry, 8 > RowTy
A single constraint of the form 'c >= v1 * c1 + ... + vn * cn'.
static RowTy negateOrEqual(RowTy R)
Multiplies each coefficient in the given row by -1.
LLVM_ABI 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(CounterInfo &Counter)
iterator find(const_arg_type_t< KeyT > Val)
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.
LLVM_ABI Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
static GEPNoWrapFlags none()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
@ ExternalLinkage
Externally visible function.
static bool isLT(Predicate P)
Return true if the predicate is SLT or ULT.
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
static bool isLE(Predicate P)
Return true if the predicate is SLE or ULE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI 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.
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Represents a saturating add/sub intrinsic.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getMinusSCEV(SCEVUse LHS, SCEVUse RHS, SCEVFlags Flags=SCEV::FlagNone, unsigned Depth=0)
Return LHS-RHS.
LLVM_ABI const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
LLVM_ABI bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
LLVM_ABI APInt getConstantMultiple(const SCEV *S, const Instruction *CtxI=nullptr)
Returns the max constant multiple of S.
LLVM_ABI 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 truncate(size_type N)
Like resize, but requires that N is less than size().
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI 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.
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.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
LLVM_ABI bool replaceUsesWithIf(Value *New, llvm::function_ref< bool(Use &U)> ShouldReplace)
Go through the uses list for this definition and make each use point to "V" if the callback ShouldRep...
Represents an op.with.overflow intrinsic.
constexpr ScalarTy getFixedValue() const
constexpr bool isFixed() const
Returns true if the quantity is not scaled by vscale.
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ BasicBlock
Various leaf nodes.
AllOnesConstantMatch m_AllOnes()
BinaryOp_match< SrcTy, SpecificConstantMatch, TargetOpcode::G_XOR, true > m_Not(const SrcTy &&Src)
Matches a register not-ed by a G_XOR.
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
match_bind< PHINode > m_Phi(PHINode *&PN)
Match a PHI node, capturing it if we match.
auto m_LogicalOp()
Matches either L && R or L || R where L and R are arbitrary values.
CommutativeBinaryIntrinsic_match< IntrID, T0, T1 > m_c_Intrinsic(const T0 &Op0, const T1 &Op1)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
DisjointOr_match< LHS, RHS > m_DisjointOr(const LHS &L, const RHS &R)
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
CmpClass_match< LHS, RHS, ICmpInst, true > m_c_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
ICmpLike_match< LHS, RHS > m_ICmpLike(CmpPredicate &Pred, const LHS &L, const RHS &R)
auto m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
is_zero< true > m_Zero()
Match any null constant or a vector with all elements equal to 0.
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
Exact_match< T > m_Exact(const T &SubPattern)
LogicalOp_match< LHS, RHS, Instruction::And, true > m_c_LogicalAnd(const LHS &L, const RHS &R)
Matches L && R with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(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.
LogicalOp_match< LHS, RHS, Instruction::Or, true > m_c_LogicalOr(const LHS &L, const RHS &R)
Matches L || R with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
bind_cst_ty m_scev_APInt(const APInt *&C)
Match an SCEV constant and bind it to an APInt.
specificloop_ty m_SpecificLoop(const Loop *L)
bool match(const SCEV *S, const Pattern &P)
SCEVAffineAddRec_match< Op0_t, Op1_t, match_isa< const Loop > > m_scev_AffineAddRec(const Op0_t &Op0, const Op1_t &Op1)
@ Switch
The "resume-switch" lowering, where there are separate resume and destroy functions that are shared b...
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< UseNode * > Use
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void stable_sort(R &&Range)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
@ Known
Known to have no common set bits.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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...
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
constexpr std::enable_if_t< std::is_signed_v< T >, std::pair< T, bool > > AddOverflow(T X, T Y)
Add two signed integers, computing the two's complement truncated result, returning a pair {result,...
const ScalarOptions & getScalarOptions(const LLVMContext &C)
LLVM_ABI std::optional< TypeSize > getBaseObjectSize(const Value *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Like getObjectSize(), but only returns the size of base objects (like allocas, global variables and a...
const Value * getPointerOperand(const Value *V)
A helper function that returns the pointer operand of a load, store or GEP instruction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
DomTreeNodeBase< BasicBlock > DomTreeNode
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
constexpr std::enable_if_t< std::is_signed_v< T >, std::pair< T, bool > > SubOverflow(T X, T Y)
Subtract two signed integers, computing the two's complement truncated result, returning a pair {resu...
constexpr unsigned MaxAnalysisRecursionDepth
LLVM_ABI bool isKnownPositive(const WithCache< const Value * > &V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the given value is known be positive (i.e.
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
@ Sub
Subtraction of integers.
DWARFExpression::Operation Op
LLVM_ABI void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)
Remaps instructions in Blocks using the mapping in VMap.
ArrayRef(const T &OneElt) -> ArrayRef< T >
constexpr unsigned BitWidth
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI 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...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
constexpr std::enable_if_t< std::is_signed_v< T >, std::pair< T, bool > > MulOverflow(T X, T Y)
Multiply two signed integers, computing the two's complement truncated result, returning a pair {resu...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI 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.
LLVM_ABI bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
LLVM_ABI void findDbgUsers(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the debug info records describing a value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.
A MapVector that performs no allocations if smaller than a certain size.