LLVM 24.0.0git
ConstraintElimination.cpp
Go to the documentation of this file.
1//===-- ConstraintElimination.cpp - Eliminate conds using constraints. ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Eliminate conditions based on constraints collected from dominating
10// conditions.
11//
12//===----------------------------------------------------------------------===//
13
15#include "ScalarOptions.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/ScopeExit.h"
20#include "llvm/ADT/Statistic.h"
31#include "llvm/IR/DataLayout.h"
32#include "llvm/IR/DebugInfo.h"
33#include "llvm/IR/Dominators.h"
34#include "llvm/IR/Function.h"
35#include "llvm/IR/IRBuilder.h"
36#include "llvm/IR/InstrTypes.h"
38#include "llvm/IR/Module.h"
40#include "llvm/IR/Verifier.h"
41#include "llvm/Pass.h"
42#include "llvm/Support/Debug.h"
47
48#include <optional>
49#include <string>
50
51using namespace llvm;
52using namespace PatternMatch;
53using namespace SCEVPatternMatch;
54
55#define DEBUG_TYPE "constraint-elimination"
56
57STATISTIC(NumCondsRemoved, "Number of instructions removed");
58DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
59 "Controls which conditions are eliminated");
60
61static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
62static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
63
65 Instruction *UserI = cast<Instruction>(U.getUser());
66 if (auto *Phi = dyn_cast<PHINode>(UserI))
67 UserI = Phi->getIncomingBlock(U)->getTerminator();
68 return UserI;
69}
70
71/// Returns the closest program point dominating all uses of \p I.
73 DominatorTree &DT) {
74 Instruction *CommonDom = nullptr;
75 unsigned NumUses = 0;
76 for (Use &U : I.uses()) {
77 // Conservatively use original instruction, if there are too many uses.
78 if (++NumUses == 16)
79 return &I;
81 CommonDom =
82 CommonDom ? DT.findNearestCommonDominator(CommonDom, UserI) : UserI;
83 }
84 if (!CommonDom)
85 return &I;
86 // Uses in unreachable blocks are not in the dominator tree.
87 return DT.getNode(CommonDom->getParent()) ? CommonDom : &I;
88}
89
90namespace {
91using Entry = ConstraintSystem::Entry;
92using RowTy = ConstraintSystem::RowTy;
93
94/// Struct to express a condition of the form %Op0 Pred %Op1.
95struct ConditionTy {
96 CmpPredicate Pred;
97 Value *Op0 = nullptr;
98 Value *Op1 = nullptr;
99
100 ConditionTy() = default;
101 ConditionTy(CmpPredicate Pred, Value *Op0, Value *Op1)
102 : Pred(Pred), Op0(Op0), Op1(Op1) {}
103};
104
105/// Represents either
106/// * a condition that holds on entry to a block (=condition fact)
107/// * an assume (=assume fact)
108/// * a use of a compare instruction to simplify.
109/// It also tracks the Dominator DFS in and out numbers for each entry.
110struct FactOrCheck {
111 enum class EntryTy {
112 ConditionFact, /// A condition that holds on entry to a block.
113 InstFact, /// A fact that holds after Inst executed (e.g. an assume or
114 /// min/mix intrinsic.
115 InstCheck, /// An instruction to simplify (e.g. an overflow math
116 /// intrinsics) or whose flags may be strengthened.
117 UseCheck /// An use of a compare instruction to simplify.
118 };
119
120 union {
121 Instruction *Inst;
122 Use *U;
124 };
125
126 union {
127 /// A pre-condition that must hold for the current fact to be added to the
128 /// system. Only used by condition facts.
129 ConditionTy DoesHold;
130
131 /// Context instruction for the point where conditions are checked for
132 /// InstCheck simplifications.
133 Instruction *ContextInst;
134 };
135
136 unsigned NumIn;
137 unsigned NumOut;
138 EntryTy Ty;
139
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) {}
144
145 FactOrCheck(DomTreeNode *DTN, Use *U)
146 : U(U), ContextInst(nullptr), NumIn(DTN->getDFSNumIn()),
147 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::UseCheck) {}
148
149 FactOrCheck(DomTreeNode *DTN, CmpPredicate Pred, Value *Op0, Value *Op1,
150 ConditionTy Precond = {})
151 : Cond(Pred, Op0, Op1), DoesHold(Precond), NumIn(DTN->getDFSNumIn()),
152 NumOut(DTN->getDFSNumOut()), Ty(EntryTy::ConditionFact) {}
153
154 static FactOrCheck getConditionFact(DomTreeNode *DTN, CmpPredicate Pred,
155 Value *Op0, Value *Op1,
156 ConditionTy Precond = {}) {
157 return FactOrCheck(DTN, Pred, Op0, Op1, Precond);
158 }
159
160 static FactOrCheck getInstFact(DomTreeNode *DTN, Instruction *Inst) {
161 return FactOrCheck(EntryTy::InstFact, DTN, Inst);
162 }
163
164 static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) {
165 return FactOrCheck(DTN, U);
166 }
167
168 static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *I,
169 Instruction *ContextInst = nullptr) {
170 assert((ContextInst ? ContextInst : I)->getParent() == DTN->getBlock() &&
171 "anchoring instruction must be in DTN's block");
172 return FactOrCheck(EntryTy::InstCheck, DTN, I, ContextInst);
173 }
174
175 bool isCheck() const {
176 return Ty == EntryTy::InstCheck || Ty == EntryTy::UseCheck;
177 }
178
179 Instruction *getContextInst() const {
180 assert(!isConditionFact());
181 if (Ty == EntryTy::UseCheck)
182 return getContextInstForUse(*U);
183 return ContextInst;
184 }
185
186 Instruction *getInstructionToSimplify() const {
187 assert(isCheck());
188 if (Ty == EntryTy::InstCheck)
189 return Inst;
190 // The use may have been simplified to a constant already.
191 return dyn_cast<Instruction>(*U);
192 }
193
194 bool isConditionFact() const { return Ty == EntryTy::ConditionFact; }
195};
196
197/// The senses in which an induction phi is monotonic, together with the
198/// direction it moves in.
199struct MonotonicInfo {
200 /// True if the phi steps by a negative constant.
201 bool Decreasing = false;
202 /// True if the phi is monotonic in the unsigned sense.
203 bool Unsigned = false;
204 /// True if the phi is monotonic in the signed sense.
205 bool Signed = false;
206};
207
208/// Keep state required to build worklist.
209struct State {
210 DominatorTree &DT;
211 LoopInfo &LI;
212 /// Only available for functions with loops.
213 ScalarEvolution *SE;
214 TargetLibraryInfo &TLI;
216
217 State(DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE,
218 TargetLibraryInfo &TLI)
219 : DT(DT), LI(LI), SE(SE), TLI(TLI) {}
220
221 /// Process block \p BB and add known facts to work-list.
222 void addInfoFor(BasicBlock &BB);
223
224 /// If \p BB is a loop header, bound each induction phi in it by its start
225 /// value.
226 void addBoundsForHeaderInductions(BasicBlock &BB);
227
228 /// Try to add facts for loop inductions (AddRecs) in EQ/NE compares
229 /// controlling the loop header.
230 void addInfoForInductions(BasicBlock &BB);
231
232 /// Returns the direction the induction phi \p PN with backedge value \p Step
233 /// moves in, and the senses in which it is monotonic in that direction.
234 MonotonicInfo getMonotonicityInfo(PHINode &PN, Value *Step);
235
236 /// Returns true if we can add a known condition from BB to its successor
237 /// block Succ.
238 bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
239 return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
240 }
241};
242
243class ConstraintInfo;
244
245struct StackEntry {
246 unsigned NumIn;
247 unsigned NumOut;
248 bool IsSigned = false;
249 /// Variables that can be removed from the system once the stack entry gets
250 /// removed.
251 SmallVector<Value *, 2> ValuesToRelease;
252
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)) {}
257};
258
259struct ConstraintTy {
260 RowTy Coefficients;
261
262 /// Number of variables the constraint is defined over.
263 unsigned NumVars = 0;
264
265 bool IsSigned = false;
266
267 ConstraintTy() = default;
268
269 ConstraintTy(RowTy Coefficients, unsigned NumVars, bool IsSigned, bool IsEq,
270 bool IsNe)
271 : Coefficients(std::move(Coefficients)), NumVars(NumVars),
272 IsSigned(IsSigned), IsEq(IsEq), IsNe(IsNe) {}
273
274 bool empty() const { return Coefficients.empty(); }
275
276 bool isEq() const { return IsEq; }
277
278 bool isNe() const { return IsNe; }
279
280 /// Check if the current constraint is implied by the given ConstraintSystem.
281 ///
282 /// \return true or false if the constraint is proven to be respectively true,
283 /// or false. When the constraint cannot be proven to be either true or false,
284 /// std::nullopt is returned.
285 std::optional<bool> isImpliedBy(const ConstraintSystem &CS) const;
286
287private:
288 bool IsEq = false;
289 bool IsNe = false;
290};
291
292/// Represents a (Coefficient * Variable) entry after IR decomposition.
293struct DecompEntry {
294 int64_t Coefficient;
295 Value *Variable;
296
297 DecompEntry(int64_t Coefficient, Value *Variable)
298 : Coefficient(Coefficient), Variable(Variable) {}
299};
300
301/// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
302struct Decomposition {
303 int64_t Offset = 0;
305
306 Decomposition(int64_t Offset) : Offset(Offset) {}
307 Decomposition(Value *V) { Vars.emplace_back(1, V); }
308 Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
309 : Offset(Offset), Vars(Vars) {}
310
311 /// Add \p OtherOffset and return true if the operation overflows, i.e. the
312 /// new decomposition is invalid.
313 [[nodiscard]] bool add(int64_t OtherOffset) {
314 return AddOverflow(Offset, OtherOffset, Offset);
315 }
316
317 /// Add \p Other and return true if the operation overflows, i.e. the new
318 /// decomposition is invalid.
319 [[nodiscard]] bool add(const Decomposition &Other) {
320 if (add(Other.Offset))
321 return true;
322 append_range(Vars, Other.Vars);
323 return false;
324 }
325
326 /// Subtract \p Other and return true if the operation overflows, i.e. the new
327 /// decomposition is invalid.
328 [[nodiscard]] bool sub(const Decomposition &Other) {
329 Decomposition Tmp = Other;
330 if (Tmp.mul(-1))
331 return true;
332 if (add(Tmp.Offset))
333 return true;
334 append_range(Vars, Tmp.Vars);
335 return false;
336 }
337
338 /// Multiply all coefficients by \p Factor and return true if the operation
339 /// overflows, i.e. the new decomposition is invalid.
340 [[nodiscard]] bool mul(int64_t Factor) {
341 if (MulOverflow(Offset, Factor, Offset))
342 return true;
343 for (auto &Var : Vars)
344 if (MulOverflow(Var.Coefficient, Factor, Var.Coefficient))
345 return true;
346 return false;
347 }
348};
349
350/// Wrapper encapsulating separate constraint systems and corresponding value
351/// mappings for both unsigned and signed information. Facts are added to and
352/// conditions are checked against the corresponding system depending on the
353/// signed-ness of their predicates. While the information is kept separate
354/// based on signed-ness, certain conditions can be transferred between the two
355/// systems.
356class ConstraintInfo {
357
358 ConstraintSystem UnsignedCS;
359 ConstraintSystem SignedCS;
360
361 const DataLayout &DL;
362
363 /// Decompositions computed against the current state of the systems. Must be
364 /// cleared when the system changes.
365 DenseMap<PointerIntPair<Value *, 1, bool>, Decomposition> DecomposeCache;
366
367public:
368 DenseMap<PointerIntPair<Value *, 1, bool>, Decomposition> &
369 getDecomposeCache() {
370 return DecomposeCache;
371 }
372
373 ConstraintInfo(const DataLayout &DL, ArrayRef<Value *> FunctionArgs)
374 : UnsignedCS(FunctionArgs), SignedCS(FunctionArgs), DL(DL) {
375 auto &Value2Index = getValue2Index(false);
376 // Add Arg > -1 constraints to unsigned system for all function arguments.
377 for (Value *Arg : FunctionArgs)
378 UnsignedCS.addRow({Entry(0, 0), Entry(-1, Value2Index.at(Arg))},
379 Value2Index.size());
380 }
381
382 DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
383 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
384 }
385 const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
386 return Signed ? SignedCS.getValue2Index() : UnsignedCS.getValue2Index();
387 }
388
389 ConstraintSystem &getCS(bool Signed) {
390 return Signed ? SignedCS : UnsignedCS;
391 }
392 const ConstraintSystem &getCS(bool Signed) const {
393 return Signed ? SignedCS : UnsignedCS;
394 }
395
396 void popLastConstraint(bool Signed) {
397 assert(DecomposeCache.empty() && "Cache must be cleared");
398 getCS(Signed).popLastConstraint();
399 }
400 void popLastNVariables(bool Signed, unsigned N) {
401 assert(DecomposeCache.empty() && "Cache must be cleared");
402 getCS(Signed).popLastNVariables(N);
403 }
404
405 bool doesHold(CmpInst::Predicate Pred, Value *A, Value *B);
406
407 /// Returns the result of \p Solve. If it does not return a value, retries
408 /// after adding A == decompose(A) and B == decompose(B) to the system of \p
409 /// C, if needed, and removes them afterwards.
410 std::optional<bool>
411 tryWithLinkRows(Value *A, Value *B, const ConstraintTy &C,
412 function_ref<std::optional<bool>()> Solve);
413
414 /// Returns true if \p V is known to be non-negative, either because the
415 /// signed system implies it or because ValueTracking can prove it.
417
418 /// Returns true if \p V is known to be positive, either because the signed
419 /// system implies it or because ValueTracking can prove it.
420 bool isKnownPositive(Value *V);
421
422 /// Returns true if \p V is known to be negative, false if \p V is known to be
423 /// nonnegative, or std::nullopt if neither the signed system nor
424 /// ValueTracking can prove it.
425 std::optional<bool> getKnownSign(Value *V);
426
427 void addFact(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
428 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack);
429
430 /// Turn a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
431 /// constraints, using indices from the corresponding constraint system.
432 /// New variables that need to be added to the system are collected in
433 /// \p NewVariables.
434 ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
435 SmallVectorImpl<Value *> &NewVariables,
436 bool ForceSignedSystem = false);
437
438 /// Turns a comparison of the form \p Op0 \p Pred \p Op1 into a vector of
439 /// constraints using getConstraint. Returns an empty constraint if the result
440 /// cannot be used to query the existing constraint system, e.g. because it
441 /// would require adding new variables. Also tries to convert signed
442 /// predicates to unsigned ones if possible to allow using the unsigned system
443 /// which increases the effectiveness of the signed <-> unsigned transfer
444 /// logic.
445 ConstraintTy getConstraintForSolving(CmpInst::Predicate Pred, Value *Op0,
446 Value *Op1);
447
448 /// Try to add information from \p A \p Pred \p B to the unsigned/signed
449 /// system if \p Pred is signed/unsigned.
450 void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
451 unsigned NumIn, unsigned NumOut,
452 SmallVectorImpl<StackEntry> &DFSInStack);
453
454private:
455 /// Adds facts into constraint system. \p ForceSignedSystem can be set when
456 /// the \p Pred is eq/ne, and signed constraint system is used when it's
457 /// specified.
458 void addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
459 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack,
460 bool ForceSignedSystem);
461
462 /// Try to use the inequality \p A != \p B to tighten a non-strict bound the
463 /// system already implies to the corresponding strict bound.
464 void tightenBoundUsingNe(Value *A, Value *B, unsigned NumIn, unsigned NumOut,
465 SmallVectorImpl<StackEntry> &DFSInStack);
466};
467
468// Variable and constant offsets for a chain of GEPs, with base pointer BasePtr.
469struct OffsetResult {
470 Value *BasePtr;
471 APInt ConstantOffset;
472 SmallMapVector<Value *, APInt, 4> VariableOffsets;
473 GEPNoWrapFlags NW;
474
475 OffsetResult() : BasePtr(nullptr), ConstantOffset(0, uint64_t(0)) {}
476
477 OffsetResult(GEPOperator &GEP, const DataLayout &DL)
478 : BasePtr(GEP.getPointerOperand()), NW(GEP.getNoWrapFlags()) {
479 ConstantOffset = APInt(DL.getIndexTypeSizeInBits(BasePtr->getType()), 0);
480 }
481};
482} // namespace
483
484// Try to collect variable and constant offsets for \p GEP, partly traversing
485// nested GEPs. Returns an OffsetResult with nullptr as BasePtr of collecting
486// the offset fails.
488 OffsetResult Result(GEP, DL);
489 unsigned BitWidth = Result.ConstantOffset.getBitWidth();
490 if (!GEP.collectOffset(DL, BitWidth, Result.VariableOffsets,
491 Result.ConstantOffset))
492 return {};
493
494 // If we have a nested GEP, check if we can combine the constant offset of the
495 // inner GEP with the outer GEP.
496 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Result.BasePtr)) {
497 SmallMapVector<Value *, APInt, 4> VariableOffsets2;
498 APInt ConstantOffset2(BitWidth, 0);
499 bool CanCollectInner = InnerGEP->collectOffset(
500 DL, BitWidth, VariableOffsets2, ConstantOffset2);
501 // TODO: Support cases with more than 1 variable offset.
502 if (!CanCollectInner || Result.VariableOffsets.size() > 1 ||
503 VariableOffsets2.size() > 1 ||
504 (Result.VariableOffsets.size() >= 1 && VariableOffsets2.size() >= 1)) {
505 // More than 1 variable index, use outer result.
506 return Result;
507 }
508 // The GEPs' wrap flags do not prevent the sum of the offsets from
509 // sign-wrapping.
510 bool Overflow = false;
511 APInt CombinedOffset =
512 Result.ConstantOffset.sadd_ov(ConstantOffset2, Overflow);
513 if (Overflow)
514 return Result;
515
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();
521 }
522 return Result;
523}
524
525static Decomposition decompose(Value *V, ConstraintInfo &Info, bool IsSigned,
526 const DataLayout &DL);
527
528static bool canUseSExt(ConstantInt *CI) {
529 const APInt &Val = CI->getValue();
531}
532
533/// Returns true if `Op <= MaxVal - Slack` holds in the system for \p Signed, by
534/// scanning it for a row of the form `Op - W <= -Slack`, where W is an integer
535/// variable no wider than \p Op. If \p Upper is false, returns true if
536/// `Op >= MinVal + Slack` holds, using rows of the form `W - Op <= -Slack`.
537static bool hasLimitWitness(const ConstraintInfo &Info, Value *Op,
538 const APInt &Slack, bool Signed, bool Upper) {
539 if (!Slack.isIntN(63))
540 return false;
541 int64_t RequiredOffset = -static_cast<int64_t>(Slack.getZExtValue());
542
543 const auto &Value2Index = Info.getValue2Index(Signed);
544 unsigned OpIdx = Value2Index.lookup(Op);
545 if (!OpIdx)
546 return false;
547
548 int64_t OpCoefficient = Upper ? 1 : -1;
549 unsigned OpSize = Op->getType()->getScalarSizeInBits();
550
551 for (ArrayRef<Entry> Row : Info.getCS(Signed).getConstraints()) {
552 // Match `OpCoefficient * (Op - W) <= C` with C <= -Slack.
553 if (Row.size() != 3 || Row[0].Id != 0 ||
554 Row[0].Coefficient > RequiredOffset)
555 continue;
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)
561 continue;
562
563 auto Witness = find_if(
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();
567 if (WitnessTy->isIntegerTy() && WitnessTy->getIntegerBitWidth() <= OpSize)
568 return true;
569 }
570 return false;
571}
572
573/// Returns true if \p Info implies that \p Op is in \p R, interpreting \p R as
574/// a signed range if \p Signed is set and as an unsigned range otherwise.
575static bool doesHoldInRange(ConstraintInfo &Info, Value *Op,
576 const ConstantRange &R, bool Signed) {
577 if (R.isEmptySet() || (Signed ? R.isSignWrappedSet() : R.isWrappedSet()))
578 return false;
579
580 if (R.isFullSet())
581 return true;
582
583 unsigned BitWidth = R.getBitWidth();
584 APInt Min = Signed ? R.getSignedMin() : R.getUnsignedMin();
585 APInt Max = Signed ? R.getSignedMax() : R.getUnsignedMax();
590 // What a witness has to bridge; computed before Max is clamped below.
591 APInt UpperSlack = MaxVal - Max;
592 // Replace bound too large to be decomposed by the largest usable one.
593 if (!Signed && Max.uge(MaxConstraintValue))
595
596 Type *Ty = Op->getType();
597 if (Min != MinVal &&
598 !Info.doesHold(Signed ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE, Op,
599 ConstantInt::get(Ty, Min)) &&
600 !hasLimitWitness(Info, Op, Min - MinVal, Signed, /*Upper=*/false))
601 return false;
602 if (Max != MaxVal &&
603 !Info.doesHold(Signed ? CmpInst::ICMP_SLE : CmpInst::ICMP_ULE, Op,
604 ConstantInt::get(Ty, Max)) &&
605 !hasLimitWitness(Info, Op, UpperSlack, Signed, /*Upper=*/true))
606 return false;
607 return true;
608}
609
610/// Returns true if \p Opcode applied to \p Op0 and \p Op1 with \p NoWrapFlags
611/// is known to not wrap in signed or unsigned, depending on \p Signed.
612static bool isKnownNoWrap(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
613 unsigned NoWrapFlags, ConstraintInfo &Info,
614 bool Signed) {
615 using OBO = OverflowingBinaryOperator;
616
617 if (NoWrapFlags & (Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap))
618 return true;
619
620 if (Opcode == Instruction::Sub) {
621 // Op0 - Op1 does not wrap unsigned if Op0 >=u Op1.
622 if (!Signed)
623 return Info.doesHold(CmpInst::ICMP_UGE, Op0, Op1);
624
625 // Op0 - Op1 does not wrap signed if 0 <=s Op1 <=s Op0.
626 if (Info.isKnownNonNegative(Op1) &&
627 Info.doesHold(CmpInst::ICMP_SGE, Op0, Op1))
628 return true;
629 }
630
631 if (!Signed && (NoWrapFlags & OBO::NoSignedWrap) &&
632 (Opcode == Instruction::Shl || Info.isKnownNonNegative(Op1)) &&
633 Info.isKnownNonNegative(Op0))
634 return true;
635
636 // For a constant Op1, the ranges of Op0 for which the operation does not
637 // wrap are known exactly; check if the systems imply one of them.
638 auto *C = dyn_cast<ConstantInt>(Op1);
639 if (!C)
640 return false;
641
642 return doesHoldInRange(Info, Op0,
644 Opcode, C->getValue(),
645 Signed ? OBO::NoSignedWrap : OBO::NoUnsignedWrap),
646 Signed);
647}
648
649/// Returns true if \p V is known to not wrap in signed or unsigned, depending
650/// on \p Signed.
651static bool isKnownNoWrap(Value *V, ConstraintInfo &Info, bool Signed) {
652 if (match(V, m_DisjointOr(m_Value(), m_Value())))
653 return true;
654
655 if (auto *WO = dyn_cast<WithOverflowInst>(V))
656 return isKnownNoWrap(WO->getBinaryOp(), WO->getLHS(), WO->getRHS(),
657 /*NoWrapFlags=*/0, Info, Signed);
658
659 if (auto *Trunc = dyn_cast<TruncInst>(V)) {
660 if (Signed)
661 return Trunc->hasNoSignedWrap();
662
663 // A trunc nsw only truncates without unsigned wrap if its operand is
664 // non-negative.
665 return Trunc->hasNoUnsignedWrap() ||
666 (Trunc->hasNoSignedWrap() &&
667 Info.isKnownNonNegative(Trunc->getOperand(0)));
668 }
669
671 return BO &&
672 isKnownNoWrap(static_cast<Instruction::BinaryOps>(BO->getOpcode()),
673 BO->getOperand(0), BO->getOperand(1),
674 BO->getNoWrapKind(), Info, Signed);
675}
676
677static Decomposition decomposeGEP(GEPOperator &GEP, ConstraintInfo &Info,
678 bool IsSigned, const DataLayout &DL) {
679 // Do not reason about pointers where the index size is larger than 64 bits,
680 // as the coefficients used to encode constraints are 64 bit integers.
681 if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
682 return &GEP;
683
684 assert(!IsSigned && "The logic below only supports decomposition for "
685 "unsigned predicates at the moment.");
686 const auto &[BasePtr, ConstantOffset, VariableOffsets, NW] =
688 // We support either plain gep nuw, or gep nusw with non-negative offset,
689 // which implies gep nuw.
690 if (!BasePtr || NW == GEPNoWrapFlags::none())
691 return &GEP;
692
693 // For a nuw-only GEP (nuw without nusw/inbounds), the offset must be
694 // interpreted as unsigned.
695 if (!NW.hasNoUnsignedSignedWrap() && ConstantOffset.isNegative())
696 return &GEP;
697
698 Decomposition Result(ConstantOffset.getSExtValue(), DecompEntry(1, BasePtr));
699 for (auto [Index, Scale] : VariableOffsets) {
700 // Indices narrower or wider than the index type are implicitly
701 // sign-extended or truncated. Don't reason about them.
702 if (Index->getType()->getScalarSizeInBits() != Scale.getBitWidth())
703 return &GEP;
704 if (!NW.hasNoUnsignedWrap()) {
705 // Try to prove nuw from nusw and nneg. If the index cannot be proven
706 // non-negative, keep the GEP as-is instead of decomposing it.
707 assert(NW.hasNoUnsignedSignedWrap() && "Must have nusw flag");
708 if (!Info.isKnownNonNegative(Index))
709 return &GEP;
710 } else if (!NW.hasNoUnsignedSignedWrap()) {
711 // For a nuw-only GEP, the scale is unsigned and must fit in the signed
712 // coefficient.
713 if (Scale.isNegative())
714 return &GEP;
715 }
716
717 auto IdxResult = decompose(Index, Info, IsSigned, DL);
718 if (IdxResult.mul(Scale.getSExtValue()))
719 return &GEP;
720 if (Result.add(IdxResult))
721 return &GEP;
722 }
723 return Result;
724}
725
726// Decomposes \p V into a constant offset + list of pairs { Coefficient,
727// Variable } where Coefficient * Variable. The sum of the constant offset and
728// pairs equals \p V.
729//
730// Looking through certain expressions is only valid if a pre-condition holds.
731// Pre-conditions are checked against \p Info as needed.
732static Decomposition decomposeImpl(Value *V, ConstraintInfo &Info,
733 bool IsSigned, const DataLayout &DL);
734
735/// Returns true if \p V is an operation decomposeImpl can look through.
736static bool mayLookThrough(Value *V) {
737 auto *Op = dyn_cast<Operator>(V);
738 if (!Op)
739 return false;
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:
753 return true;
754 default:
755 return false;
756 }
757}
758
759static Decomposition decompose(Value *V, ConstraintInfo &Info, bool IsSigned,
760 const DataLayout &DL) {
761 if (!mayLookThrough(V))
762 return decomposeImpl(V, Info, IsSigned, DL);
763
765 auto &Cache = Info.getDecomposeCache();
766 auto It = Cache.find(Key);
767 if (It != Cache.end())
768 return It->second;
769
770 Decomposition Result = decomposeImpl(V, Info, IsSigned, DL);
771 Info.getDecomposeCache().insert({Key, Result});
772 return Result;
773}
774
775static Decomposition decomposeImpl(Value *V, ConstraintInfo &Info,
776 bool IsSigned, const DataLayout &DL) {
777 auto MergeResults = [&Info, IsSigned,
778 &DL](Value *A, Value *B,
779 bool IsSignedB) -> std::optional<Decomposition> {
780 auto ResA = decompose(A, Info, IsSigned, DL);
781 auto ResB = decompose(B, Info, IsSignedB, DL);
782 if (ResA.add(ResB))
783 return std::nullopt;
784 return ResA;
785 };
786
787 Type *Ty = V->getType()->getScalarType();
788 if (Ty->isPointerTy() && !IsSigned) {
789 if (auto *GEP = dyn_cast<GEPOperator>(V))
790 return decomposeGEP(*GEP, Info, IsSigned, DL);
792 return int64_t(0);
793
794 return V;
795 }
796
797 // Don't handle integers > 64 bit. Our coefficients are 64-bit large, so
798 // coefficient add/mul may wrap, while the operation in the full bit width
799 // would not.
800 if (!Ty->isIntegerTy() || Ty->getIntegerBitWidth() > 64)
801 return V;
802
803 if (auto *CI = dyn_cast<ConstantInt>(V)) {
804 if (IsSigned) {
805 if (canUseSExt(CI))
806 return CI->getSExtValue();
807 } else if (!CI->uge(MaxConstraintValue)) {
808 return int64_t(CI->getZExtValue());
809 }
810 return V;
811 }
812
813 Value *Op0;
814 Value *Op1;
815 ConstantInt *CI;
816
817 if (match(V, m_ZExt(m_Value(Op0)))) {
818 // In the signed system, the ZExt must be non-negative.
819 if (IsSigned && !cast<ZExtInst>(V)->hasNonNeg())
820 return V;
821 V = Op0;
822 } else if (match(V, m_SExt(m_Value(Op0)))) {
823 // In the unsigned system, the SExt operand must be non-negative.
824 if (!IsSigned && !Info.isKnownNonNegative(Op0))
825 return V;
826 V = Op0;
827 } else if (auto *Trunc = dyn_cast<TruncInst>(V)) {
828 if (Trunc->getSrcTy()->getScalarSizeInBits() <= 64 &&
829 isKnownNoWrap(Trunc, Info, IsSigned))
830 V = Trunc->getOperand(0);
831 }
832
833 if (match(V, m_AddLike(m_Value(Op0), m_Value(Op1)))) {
834 if (isKnownNoWrap(V, Info, IsSigned)) {
835 if (auto Decomp = MergeResults(Op0, Op1, IsSigned))
836 return *Decomp;
837 return V;
838 }
839 // In the unsigned system, adding a negative constant only wraps if Op0 is
840 // smaller than it.
841 if (!IsSigned && match(Op1, m_ConstantInt(CI)) && CI->isNegative() &&
842 canUseSExt(CI) &&
843 Info.doesHold(CmpInst::ICMP_UGE, Op0,
844 ConstantInt::get(Op0->getType(), -CI->getSExtValue())))
845 if (auto Decomp = MergeResults(Op0, CI, /*IsSignedB=*/true))
846 return *Decomp;
847 return V;
848 }
849
850 // `xor %x, -1` is equivalent to `sub nsw -1, %x`.
851 if (IsSigned && match(V, m_Not(m_Value(Op0)))) {
852 Decomposition Result(-1);
853 if (!Result.sub(decompose(Op0, Info, IsSigned, DL)))
854 return Result;
855 return V;
856 }
857
858 if (match(V, m_Sub(m_Value(Op0), m_Value(Op1)))) {
859 if (isKnownNoWrap(V, Info, IsSigned)) {
860 auto ResA = decompose(Op0, Info, IsSigned, DL);
861 auto ResB = decompose(Op1, Info, IsSigned, DL);
862 if (!ResA.sub(ResB))
863 return ResA;
864 }
865 return V;
866 }
867
868 if (match(V, m_Mul(m_Value(Op0), m_ConstantInt(CI)))) {
869 // A negative constant is only a valid coefficient in the signed system; in
870 // the unsigned system the multiplier is the constant's unsigned value.
871 if (canUseSExt(CI) && (IsSigned || !CI->isNegative()) &&
872 isKnownNoWrap(V, Info, IsSigned)) {
873 auto Result = decompose(Op0, Info, IsSigned, DL);
874 if (!Result.mul(CI->getSExtValue()))
875 return Result;
876 }
877 return V;
878 }
879
880 if (match(V, m_Exact(m_Shr(m_Value(Op0), m_ConstantInt(CI))))) {
881 bool IsAShr = cast<Operator>(V)->getOpcode() == Instruction::AShr;
882 if (CI->getValue().ult(std::min(63u, CI->getBitWidth())) &&
883 (IsSigned == IsAShr || Info.isKnownNonNegative(Op0))) {
884 int64_t Factor = int64_t(1) << CI->getZExtValue();
885 auto Result = decompose(Op0, Info, IsSigned, DL);
886 if (Result.Offset % Factor == 0 &&
887 all_of(Result.Vars, [Factor](const DecompEntry &E) {
888 return E.Coefficient % Factor == 0;
889 })) {
890 Result.Offset /= Factor;
891 for (auto &E : Result.Vars)
892 E.Coefficient /= Factor;
893 return Result;
894 }
895 }
896 return V;
897 }
898
899 if (match(V, m_Shl(m_Value(Op0), m_ConstantInt(CI)))) {
900 // (shl x, shift) is (mul x, 1 << shift). The scale must fit in the signed
901 // coefficient, so reject shifts >= 63. Also reject a shift of bw-1, for
902 // which the product is not representable.
903 int64_t MaxShift = IsSigned ? Ty->getIntegerBitWidth() - 1 : 63;
904 if (!CI->isNegative() && CI->getSExtValue() < MaxShift &&
905 isKnownNoWrap(V, Info, IsSigned)) {
906 auto Result = decompose(Op0, Info, IsSigned, DL);
907 if (!Result.mul(int64_t{1} << CI->getSExtValue()))
908 return Result;
909 }
910 return V;
911 }
912
913 return V;
914}
915
916/// Build the row for 'ADec <= BDec', using the indices from \p Value2Index.
917/// Variables not in \p Value2Index are appended to \p NewVariables and get the
918/// indices following the ones in \p Value2Index. Returns an empty row if the
919/// coefficients overflow.
920static RowTy getRowForLessEqual(const Decomposition &ADec,
921 const Decomposition &BDec,
922 const DenseMap<Value *, unsigned> &Value2Index,
923 SmallVectorImpl<Value *> &NewVariables) {
924 // Build the row, by first adding all coefficients from A and then subtracting
925 // all coefficients from B.
926 int64_t OffsetSum;
927 if (SubOverflow(BDec.Offset, ADec.Offset, OffsetSum))
928 return {};
929 RowTy R(1, Entry(OffsetSum, 0));
930 auto GetCoefficient = [&R](unsigned Idx) -> int64_t & {
931 // The entry for Idx, or the place to insert it at, is the first entry with
932 // an index >= Idx.
933 Entry *I =
934 find_if(drop_begin(R), [Idx](const Entry &E) { return E.Id >= Idx; });
935 if (I == R.end() || I->Id != Idx)
936 I = R.insert(I, Entry(0, Idx));
937 return I->Coefficient;
938 };
939 // First try to look up \p V in Value2Index and NewVariables. Otherwise add a
940 // new entry to NewVariables.
941 auto GetOrAddIndex = [&Value2Index, &NewVariables](Value *V) -> unsigned {
942 auto V2I = Value2Index.find(V);
943 if (V2I != Value2Index.end())
944 return V2I->second;
945 unsigned Idx = find(NewVariables, V) - NewVariables.begin();
946 if (Idx == NewVariables.size())
947 NewVariables.push_back(V);
948 return Value2Index.size() + Idx + 1;
949 };
950 for (const DecompEntry &KV : ADec.Vars)
951 GetCoefficient(GetOrAddIndex(KV.Variable)) += KV.Coefficient;
952
953 for (const DecompEntry &KV : BDec.Vars) {
954 auto &Coeff = GetCoefficient(GetOrAddIndex(KV.Variable));
955 if (SubOverflow(Coeff, KV.Coefficient, Coeff))
956 return {};
957 }
958
959 // Drop coefficients that cancelled out.
960 erase_if(R, [](const Entry &E) { return E.Id != 0 && E.Coefficient == 0; });
961 return R;
962}
963
964ConstraintTy
965ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
966 SmallVectorImpl<Value *> &NewVariables,
967 bool ForceSignedSystem) {
968 assert(NewVariables.empty() && "NewVariables must be empty when passed in");
969 assert((!ForceSignedSystem || CmpInst::isEquality(Pred)) &&
970 "signed system can only be forced on eq/ne");
971
972 bool IsEq = false;
973 bool IsNe = false;
974
975 // Try to convert Pred to one of ULE/ULT/SLE/SLT.
976 switch (Pred) {
980 case CmpInst::ICMP_SGE: {
982 std::swap(Op0, Op1);
983 break;
984 }
985 case CmpInst::ICMP_EQ:
986 if (!ForceSignedSystem && match(Op1, m_Zero())) {
988 } else {
989 IsEq = true;
991 }
992 break;
993 case CmpInst::ICMP_NE:
994 if (!ForceSignedSystem && match(Op1, m_Zero())) {
996 std::swap(Op0, Op1);
997 } else {
998 IsNe = true;
1000 }
1001 break;
1002 default:
1003 break;
1004 }
1005
1008 return {};
1009
1010 bool IsSigned = ForceSignedSystem || CmpInst::isSigned(Pred);
1011 auto &Value2Index = getValue2Index(IsSigned);
1012 auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(), *this,
1013 IsSigned, DL);
1014 auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(), *this,
1015 IsSigned, DL);
1016 RowTy R = getRowForLessEqual(ADec, BDec, Value2Index, NewVariables);
1017 if (R.empty())
1018 return {};
1019
1021 if (AddOverflow(R[0].Coefficient, int64_t(-1), R[0].Coefficient))
1022 return {};
1023
1024 // Remove any new variable without a coefficient in the row.
1025 unsigned NumV2I = Value2Index.size();
1026 NewVariables.truncate(R.back().Id > NumV2I ? R.back().Id - NumV2I : 0);
1027
1028 return ConstraintTy(std::move(R), Value2Index.size() + NewVariables.size(),
1029 IsSigned, IsEq, IsNe);
1030}
1031
1032ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
1033 Value *Op0, Value *Op1) {
1034 Constant *NullC = Constant::getNullValue(Op0->getType());
1035 // Handle trivially true compares directly to avoid adding V UGE 0 constraints
1036 // for all variables in the unsigned system.
1037 if ((Pred == CmpInst::ICMP_ULE && Op0 == NullC) ||
1038 (Pred == CmpInst::ICMP_UGE && Op1 == NullC)) {
1039 // Return constraint that's trivially true.
1040 return ConstraintTy(RowTy(1, Entry(0, 0)), /*NumVars=*/0,
1041 /*IsSigned=*/false, /*IsEq=*/false, /*IsNe=*/false);
1042 }
1043
1044 // If both operands are known to be non-negative, change signed predicates to
1045 // unsigned ones. This increases the reasoning effectiveness in combination
1046 // with the signed <-> unsigned transfer logic.
1047 if (CmpInst::isSigned(Pred) &&
1048 ::isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1) &&
1051
1052 SmallVector<Value *> NewVariables;
1053 ConstraintTy R = getConstraint(Pred, Op0, Op1, NewVariables);
1054 if (!NewVariables.empty())
1055 return {};
1056 return R;
1057}
1058
1059std::optional<bool>
1060ConstraintTy::isImpliedBy(const ConstraintSystem &CS) const {
1061 const auto &[SubCS, NewCoefficients] = CS.getSubSystem(Coefficients);
1062 bool IsConditionImplied = SubCS.isConditionImplied(NewCoefficients);
1063
1064 if (IsEq || IsNe) {
1065 auto NegatedOrEqual = ConstraintSystem::negateOrEqual(NewCoefficients);
1066 bool IsNegatedOrEqualImplied =
1067 !NegatedOrEqual.empty() && SubCS.isConditionImplied(NegatedOrEqual);
1068
1069 // In order to check that `%a == %b` is true (equality), both conditions `%a
1070 // >= %b` and `%a <= %b` must hold true. When checking for equality (`IsEq`
1071 // is true), we return true if they both hold, false in the other cases.
1072 if (IsConditionImplied && IsNegatedOrEqualImplied)
1073 return IsEq;
1074
1075 auto Negated = ConstraintSystem::negate(NewCoefficients);
1076 bool IsNegatedImplied =
1077 !Negated.empty() && SubCS.isConditionImplied(Negated);
1078
1079 auto StrictLessThan = ConstraintSystem::toStrictLessThan(NewCoefficients);
1080 bool IsStrictLessThanImplied =
1081 !StrictLessThan.empty() && SubCS.isConditionImplied(StrictLessThan);
1082
1083 // In order to check that `%a != %b` is true (non-equality), either
1084 // condition `%a > %b` or `%a < %b` must hold true. When checking for
1085 // non-equality (`IsNe` is true), we return true if one of the two holds,
1086 // false in the other cases.
1087 if (IsNegatedImplied || IsStrictLessThanImplied)
1088 return IsNe;
1089
1090 return std::nullopt;
1091 }
1092
1093 if (IsConditionImplied)
1094 return true;
1095
1096 auto Negated = ConstraintSystem::negate(NewCoefficients);
1097 auto IsNegatedImplied = !Negated.empty() && SubCS.isConditionImplied(Negated);
1098 if (IsNegatedImplied)
1099 return false;
1100
1101 // Neither the condition nor its negated holds, did not prove anything.
1102 return std::nullopt;
1103}
1104
1105static RowTy getDecompositionLinkRow(Value *V, const ConstraintTy &C,
1106 ConstraintInfo &Info,
1107 const DataLayout &DL);
1108
1109std::optional<bool>
1110ConstraintInfo::tryWithLinkRows(Value *A, Value *B, const ConstraintTy &C,
1111 function_ref<std::optional<bool>()> Solve) {
1112 if (std::optional<bool> Res = Solve())
1113 return Res;
1114 if (C.empty())
1115 return std::nullopt;
1116
1117 auto &CS = getCS(C.IsSigned);
1118 unsigned NumVars = getValue2Index(C.IsSigned).size();
1119 unsigned NumPushed = 0;
1120 for (Value *V : {A, B}) {
1121 RowTy Row = getDecompositionLinkRow(V, C, *this, DL);
1122 RowTy Negated = ConstraintSystem::negateOrEqual(Row);
1123 if (Row.empty() || Negated.empty())
1124 continue;
1125 NumPushed += CS.addRow(Row, NumVars);
1126 NumPushed += CS.addRow(Negated, NumVars);
1127 }
1128 if (NumPushed == 0)
1129 return std::nullopt;
1130#ifndef NDEBUG
1131 unsigned NumRows = CS.size();
1132#endif
1133 std::optional<bool> Res = Solve();
1134 assert(CS.size() == NumRows && "rows added while link rows are pushed");
1135 while (NumPushed--)
1136 CS.popLastConstraint();
1137 return Res;
1138}
1139
1140bool ConstraintInfo::doesHold(CmpInst::Predicate Pred, Value *A, Value *B) {
1141 auto R = getConstraintForSolving(Pred, A, B);
1142 if (R.empty())
1143 return false;
1144 auto &CS = getCS(R.IsSigned);
1145 return tryWithLinkRows(A, B, R,
1146 [&]() -> std::optional<bool> {
1147 if (CS.isConditionImpliedInSubSystem(R.Coefficients))
1148 return true;
1149 return std::nullopt;
1150 })
1151 .value_or(false);
1152}
1153
1154bool ConstraintInfo::isKnownNonNegative(Value *V) {
1155 if (auto *CI = dyn_cast<ConstantInt>(V))
1156 return !CI->isNegative();
1157 return ::isKnownNonNegative(V, DL) ||
1158 doesHold(CmpInst::ICMP_SGE, V, ConstantInt::get(V->getType(), 0));
1159}
1160
1161bool ConstraintInfo::isKnownPositive(Value *V) {
1162 if (auto *CI = dyn_cast<ConstantInt>(V))
1163 return CI->getValue().isStrictlyPositive();
1164 return ::isKnownPositive(V, DL) ||
1165 doesHold(CmpInst::ICMP_SGT, V, ConstantInt::get(V->getType(), 0));
1166}
1167
1168std::optional<bool> ConstraintInfo::getKnownSign(Value *V) {
1169 KnownBits Known = computeKnownBits(V, DL);
1170 if (Known.isNonNegative())
1171 return false;
1172 if (Known.isNegative())
1173 return true;
1174 Constant *Zero = ConstantInt::get(V->getType(), 0);
1175 if (doesHold(CmpInst::ICMP_SGE, V, Zero))
1176 return false;
1177 if (doesHold(CmpInst::ICMP_SLT, V, Zero))
1178 return true;
1179 return std::nullopt;
1180}
1181
1182void ConstraintInfo::transferToOtherSystem(
1183 CmpInst::Predicate Pred, Value *A, Value *B, unsigned NumIn,
1184 unsigned NumOut, SmallVectorImpl<StackEntry> &DFSInStack) {
1185 // Check if we can combine facts from the signed and unsigned systems to
1186 // derive additional facts.
1187 if (!A->getType()->isIntegerTy())
1188 return;
1189 // FIXME: This currently depends on the order we add facts. Ideally we
1190 // would first add all known facts and only then try to add additional
1191 // facts.
1192 switch (Pred) {
1193 default:
1194 break;
1195 case CmpInst::ICMP_ULT:
1196 case CmpInst::ICMP_ULE:
1197 // If B is a signed positive constant, then A >=s 0 and A <s (or <=s) B.
1198 if (isKnownNonNegative(B)) {
1199 addFact(CmpInst::ICMP_SGE, A, ConstantInt::get(B->getType(), 0), NumIn,
1200 NumOut, DFSInStack);
1201 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
1202 DFSInStack);
1203 }
1204 break;
1205 case CmpInst::ICMP_UGE:
1206 case CmpInst::ICMP_UGT:
1207 // If A is a signed positive constant, then B >=s 0 and A >s (or >=s) B.
1208 if (isKnownNonNegative(A)) {
1209 addFact(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0), NumIn,
1210 NumOut, DFSInStack);
1211 addFact(ICmpInst::getSignedPredicate(Pred), A, B, NumIn, NumOut,
1212 DFSInStack);
1213 }
1214 break;
1215 case CmpInst::ICMP_SLT:
1216 case CmpInst::ICMP_SLE:
1217 if (isKnownNonNegative(A))
1218 addFact(ICmpInst::getUnsignedPredicate(Pred), A, B, NumIn, NumOut,
1219 DFSInStack);
1220 break;
1221 case CmpInst::ICMP_SGT: {
1222 if (doesHold(CmpInst::ICMP_SGE, B, Constant::getAllOnesValue(B->getType())))
1223 addFact(CmpInst::ICMP_UGE, A, ConstantInt::get(B->getType(), 0), NumIn,
1224 NumOut, DFSInStack);
1225 if (isKnownNonNegative(B))
1226 addFact(CmpInst::ICMP_UGT, A, B, NumIn, NumOut, DFSInStack);
1227
1228 break;
1229 }
1230 case CmpInst::ICMP_SGE:
1231 if (isKnownNonNegative(B))
1232 addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
1233 break;
1234 }
1235}
1236
1237#ifndef NDEBUG
1238
1240 const DenseMap<Value *, unsigned> &Value2Index) {
1241 ConstraintSystem CS(Value2Index);
1242 CS.addRow(C, Value2Index.size());
1243 CS.dump();
1244}
1245#endif
1246
1247/// Splits the induction phi \p PN into the start value, coming from the loop
1248/// predecessor \p LoopPred, and the backedge value, coming from inside the
1249/// loop. Returns {nullptr, nullptr} if \p PN has other incoming values.
1250static std::pair<Value *, Value *>
1251getStartAndBackedgeValue(const PHINode &PN, const BasicBlock *LoopPred) {
1252 assert(PN.getBasicBlockIndex(LoopPred) >= 0 &&
1253 "LoopPred must be a predecessor of the phi's block");
1254 if (PN.getNumIncomingValues() != 2)
1255 return {nullptr, nullptr};
1256 unsigned StartIdx = PN.getIncomingBlock(0) == LoopPred ? 0 : 1;
1257 return {PN.getIncomingValue(StartIdx), PN.getIncomingValue(1 - StartIdx)};
1258}
1259
1260/// Matches an increment of \p PhiM by a constant offset, captured in \p Off.
1261/// The increment must be a plain IR add or [u|s]add.with.overflow.
1262template <typename PhiMatchTy>
1263static auto m_IncrementOf(const PhiMatchTy &PhiM, const APInt *&Off) {
1264 return m_CombineOr(
1265 m_c_Add(PhiM, m_APInt(Off)),
1269}
1270
1271MonotonicInfo State::getMonotonicityInfo(PHINode &PN, Value *Step) {
1272 MonotonicInfo Info;
1273 const APInt *StepOffset = nullptr;
1274 if (match(Step, m_IncrementOf(m_Specific(&PN), StepOffset))) {
1275 Info.Decreasing = StepOffset->isNegative();
1276 if (const auto *Add = dyn_cast<OverflowingBinaryOperator>(Step)) {
1277 Info.Unsigned = !Info.Decreasing && Add->hasNoUnsignedWrap();
1278 Info.Signed = Add->hasNoSignedWrap();
1279 }
1280 } else if (const auto *GEP = dyn_cast<GEPOperator>(Step)) {
1281 // TODO: Handle the non-increasing direction, which needs a nusw GEP with a
1282 // negative constant offset.
1283 const DataLayout &DL = PN.getDataLayout();
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())));
1290 }
1291
1292 // Forming the SCEV of a phi is expensive, so only consult it for a PN + C
1293 // step whose no-wrap flags prove nothing.
1294 if (Info.Unsigned || Info.Signed || !StepOffset)
1295 return Info;
1296
1297 const auto *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(&PN));
1298 if (!AR)
1299 return Info;
1303 auto IsMonotonic = [&](CmpInst::Predicate Pred) {
1304 return SE->getMonotonicPredicateType(AR, Pred) == Expected;
1305 };
1306 Info.Signed = IsMonotonic(CmpInst::ICMP_SGT);
1307 Info.Unsigned = !Info.Decreasing && IsMonotonic(CmpInst::ICMP_UGT);
1308 return Info;
1309}
1310
1311void State::addBoundsForHeaderInductions(BasicBlock &BB) {
1312 Loop *L = LI.getLoopFor(&BB);
1313 if (!L || L->getHeader() != &BB)
1314 return;
1315 BasicBlock *LoopPred = L->getLoopPredecessor();
1316 if (!LoopPred)
1317 return;
1318
1319 DomTreeNode *DTN = DT.getNode(&BB);
1320 for (PHINode &PN : BB.phis()) {
1321 if (!PN.getType()->isIntegerTy() && !PN.getType()->isPointerTy())
1322 continue;
1323
1324 auto [Start, Step] = getStartAndBackedgeValue(PN, LoopPred);
1325 if (!Start)
1326 continue;
1327
1328 MonotonicInfo Info = getMonotonicityInfo(PN, Step);
1329 // Every variable in the unsigned system already has a `V >= 0` row, so a
1330 // zero start value would just duplicate it.
1331 if (match(Start, m_Zero()))
1332 Info.Unsigned = false;
1333 if (!Info.Unsigned && !Info.Signed)
1334 continue;
1335
1336 // A non-decreasing induction cannot step below its start value, and a
1337 // non-increasing one cannot step above it.
1338 Value *LHS = &PN, *RHS = Start;
1339 if (Info.Decreasing)
1340 std::swap(LHS, RHS);
1341 CmpPredicate Pred(Info.Unsigned ? CmpInst::ICMP_UGE : CmpInst::ICMP_SGE,
1342 /*HasSameSign=*/Info.Unsigned && Info.Signed);
1343 WorkList.push_back(FactOrCheck::getConditionFact(DTN, Pred, LHS, RHS));
1344 }
1345}
1346
1347void State::addInfoForInductions(BasicBlock &BB) {
1348 auto *L = LI.getLoopFor(&BB);
1349 if (!L)
1350 return;
1351
1352 BasicBlock *Header = L->getHeader();
1353 BasicBlock *Latch = L->getLoopLatch();
1354 if (Header != &BB && Latch != &BB)
1355 return;
1356
1357 // A is either a phi or a post-increment PN + C with constant step. For the
1358 // latter, extract the constant IncStep.
1359 Value *A;
1360 Value *B;
1361 PHINode *PN = nullptr;
1362 const APInt *IncStep = nullptr;
1363 CmpPredicate Pred;
1364 auto IndValue =
1365 m_Value(A, m_CombineOr(m_Phi(PN), m_IncrementOf(m_Phi(PN), IncStep)));
1366
1367 auto *Br = dyn_cast<CondBrInst>(BB.getTerminator());
1368 if (!Br)
1369 return;
1370
1371 auto CountingCmp = m_c_ICmp(Pred, IndValue, m_Value(B));
1372 std::optional<bool> PeeledOnEdge;
1373 if (!match(Br->getCondition(), CountingCmp)) {
1374 // Look through AND/OR, and remember which edge requires all operands to be
1375 // true.
1376 if (match(Br->getCondition(), m_c_LogicalAnd(CountingCmp, m_Value())))
1377 PeeledOnEdge = true;
1378 else if (match(Br->getCondition(), m_c_LogicalOr(CountingCmp, m_Value())))
1379 PeeledOnEdge = false;
1380 else
1381 return;
1382 }
1383
1384 if (PN->getParent() != Header || PN->getNumIncomingValues() != 2 ||
1385 !SE->isSCEVable(PN->getType()))
1386 return;
1387
1388 bool ContinueOnTrue =
1390 CmpInst::Predicate ContinuePred =
1391 ContinueOnTrue ? Pred.dropSameSign() : CmpInst::getInversePredicate(Pred);
1392 BasicBlock *InLoopSucc = Br->getSuccessor(ContinueOnTrue ? 0 : 1);
1393
1394 // The peeled condition only implies the compare on the edge where the
1395 // combined condition forces its operands, which must be the in-loop edge.
1396 if (PeeledOnEdge && *PeeledOnEdge != ContinueOnTrue)
1397 return;
1398
1399 if (!L->contains(InLoopSucc) || !L->isLoopExiting(&BB))
1400 return;
1401
1402 BasicBlock *LoopPred = L->getLoopPredecessor();
1403 if (!LoopPred || !L->isLoopInvariant(B))
1404 return;
1405
1406 auto [StartValue, Backedge] = getStartAndBackedgeValue(*PN, LoopPred);
1407 DomTreeNode *DTN = DT.getNode(InLoopSucc);
1408 DomTreeNode *HeaderDTN = DT.getNode(Header);
1409
1410 // BB is the header or the latch, so every iteration taking the backedge
1411 // checked PN ContinuePred B, which guarantees PN != B for NE and LT
1412 // predicates. For an increment by one, PN != B together with StartValue <= B
1413 // (added precondition) imply PN <= B.
1414 const APInt *Step;
1415 bool HasHeaderBound =
1416 !IncStep && match(Backedge, m_IncrementOf(m_Specific(PN), Step)) &&
1417 Step->isOne() &&
1418 (ContinuePred == CmpInst::ICMP_NE || ICmpInst::isLT(ContinuePred));
1419 if (HasHeaderBound) {
1421 WorkList.push_back(FactOrCheck::getConditionFact(
1422 HeaderDTN, BoundPred, PN, B, ConditionTy(BoundPred, StartValue, B)));
1423 }
1424
1425 // For latch conditions, we need to inject the condition that holds for the
1426 // next iteration into the header. We limit to post-inc conditions, for which
1427 // an original PN + Step != B condition results in a PN < B constraint in the
1428 // header, which also holds for the next loop iteration. This would no longer
1429 // be correct if the post-inc handling would inject a more precise PN + Step <
1430 // B constraint instead.
1431 if (&BB == Latch && !IncStep)
1432 return;
1433
1434 if (ICmpInst::isRelational(ContinuePred)) {
1435 if (A != Backedge)
1436 return;
1437
1438 // The condition ensures ContinuePred holds in the header on each iteration
1439 // other than the first. Together with a precondition on the start value
1440 // (StartValue ContinuePred B), we can add B as bound of PN.
1441 WorkList.push_back(FactOrCheck::getConditionFact(
1442 HeaderDTN, ContinuePred, PN, B,
1443 ConditionTy(ContinuePred, StartValue, B)));
1444
1445 // A signed bound can be translated to the unsigned system if PN is signed
1446 // non-decreasing (StartValue s<= PN s< B) and StartValue u< B holds.
1447 // Then StartValue, PN and B must all have the same sign.
1448 if (ICmpInst::isSigned(ContinuePred)) {
1449 assert((ContinuePred == CmpInst::ICMP_SLT ||
1450 ContinuePred == CmpInst::ICMP_SLE) &&
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)));
1457 }
1458 }
1459
1460 // A relational latch steps past B rather than landing on it, so none of the
1461 // reasoning below applies.
1462 return;
1463 }
1464
1465 const APInt *StepOffset = nullptr;
1466 const SCEV *StartSCEV = nullptr;
1467 if (match(Backedge, m_c_Add(m_Specific(PN), m_APInt(StepOffset)))) {
1468 if (StepOffset->isZero())
1469 return;
1470 } else {
1471 const SCEV *Expr = SE->getSCEV(PN);
1472 if (!match(Expr,
1473 m_scev_AffineAddRec(m_SCEV(StartSCEV), m_scev_APInt(StepOffset),
1474 m_SpecificLoop(L))))
1475 return;
1476 }
1477
1478 // If we looked through `PN + C`, only derive facts when that add is
1479 // really the induction's post-increment or post-decrement.
1480 if (IncStep && *IncStep != *StepOffset)
1481 return;
1482
1483 MonotonicInfo Info = getMonotonicityInfo(*PN, Backedge);
1484
1485 // Handle negative steps.
1486 if (StepOffset->isNegative()) {
1487 // TODO: Extend to allow steps > -1.
1488 if (!(-*StepOffset).isOne())
1489 return;
1490
1491 // AR may wrap.
1492 // The loop exits once the compared value reaches B, that is at PN == B when
1493 // comparing the phi, and at PN == B + 1 for a post-decrement. Use
1494 // non-strict predicate for the former, and a strict one for the latter to
1495 // ensure the loop exits before wrapping.
1496 CmpInst::Predicate UPrecond =
1498 ConditionTy BBeforeStartUnsigned = {UPrecond, B, StartValue};
1499 ConditionTy BBeforeStartSigned = {ICmpInst::getSignedPredicate(UPrecond), B,
1500 StartValue};
1501
1502 // AR may wrap, so both facts are conditional on B being below StartValue.
1503 // Add StartValue >= PN, which holds as the loop exits before wrapping.
1504 WorkList.push_back(FactOrCheck::getConditionFact(
1505 DTN, CmpInst::ICMP_UGE, StartValue, PN, BBeforeStartUnsigned));
1506 if (!(Info.Decreasing && Info.Signed))
1507 WorkList.push_back(FactOrCheck::getConditionFact(
1508 DTN, CmpInst::ICMP_SGE, StartValue, PN, BBeforeStartSigned));
1509 // Add PN > B, which holds as the loop exits when reaching B.
1510 WorkList.push_back(FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_UGT, PN,
1511 B, BBeforeStartUnsigned));
1512 WorkList.push_back(FactOrCheck::getConditionFact(DTN, CmpInst::ICMP_SGT, PN,
1513 B, BBeforeStartSigned));
1514 return;
1515 }
1516
1517 // Make sure AR either steps by 1 or that the value we compare against is a
1518 // GEP based on the same start value and all offsets are a multiple of the
1519 // step size, to guarantee that the induction will reach the value.
1520 if (StepOffset->isZero() || StepOffset->isNegative())
1521 return;
1522
1523 if (!StepOffset->isOne()) {
1524 // Check whether B-Start is known to be a multiple of StepOffset.
1525 if (!StartSCEV)
1526 StartSCEV = SE->getSCEV(StartValue);
1527 const SCEV *BMinusStart = SE->getMinusSCEV(SE->getSCEV(B), StartSCEV);
1528 if (isa<SCEVCouldNotCompute>(BMinusStart) ||
1529 !SE->getConstantMultiple(BMinusStart).urem(*StepOffset).isZero())
1530 return;
1531 }
1532
1533 // We already established that B - Start is a multiple of Step above. The loop
1534 // exits once the compared value reaches B, that is at PN == B when comparing
1535 // the phi, and at PN + Step == B for a post-increment. Together with the
1536 // added precondition StartValue <= B for the former and the strict
1537 // StartValue < B for the latter (which implies StartValue + Step <= B),
1538 // neither PN nor the increment can wrap.
1540 ConditionTy StartBeforeBoundUnsigned = {UPrecond, StartValue, B};
1541 ConditionTy StartBeforeBoundSigned = {ICmpInst::getSignedPredicate(UPrecond),
1542 StartValue, B};
1543
1544 // Add PN >= StartValue, as the loop exits before wrapping.
1545 if (!Info.Unsigned)
1546 WorkList.push_back(FactOrCheck::getConditionFact(
1547 DTN, CmpInst::ICMP_UGE, PN, StartValue, StartBeforeBoundUnsigned));
1548 if (!Info.Signed)
1549 WorkList.push_back(FactOrCheck::getConditionFact(
1550 DTN, CmpInst::ICMP_SGE, PN, StartValue, StartBeforeBoundSigned));
1551 // Add PN < B, as the loop exits once the compared value reaches B. With a
1552 // header bound, the PN != B condition fact in InLoopSucc already tightens it
1553 // to PN < B.
1554 if (!HasHeaderBound || !canAddSuccessor(BB, InLoopSucc)) {
1555 WorkList.push_back(FactOrCheck::getConditionFact(
1556 DTN, CmpInst::ICMP_SLT, PN, B, StartBeforeBoundSigned));
1557 WorkList.push_back(FactOrCheck::getConditionFact(
1558 DTN, CmpInst::ICMP_ULT, PN, B, StartBeforeBoundUnsigned));
1559 }
1560
1561 // Try to add condition from the header or latch to the dedicated exit
1562 // blocks. When exiting either with EQ or NE, we know that the induction value
1563 // must be u<= B, as other exits may only exit earlier.
1564 assert(!StepOffset->isNegative() && "induction must be increasing");
1565 assert(ContinuePred == CmpInst::ICMP_NE && "unsupported predicate");
1566 // The header bound already implies PN u<= B in the exits.
1567 if (HasHeaderBound)
1568 return;
1570 L->getExitBlocks(ExitBBs);
1571 for (BasicBlock *EB : ExitBBs) {
1572 // Bail out on non-dedicated exits.
1573 if (DT.dominates(&BB, EB)) {
1574 WorkList.emplace_back(FactOrCheck::getConditionFact(
1575 DT.getNode(EB), CmpInst::ICMP_ULE, A, B, StartBeforeBoundUnsigned));
1576 }
1577 }
1578}
1579
1581 uint64_t AccessSize,
1583 Value *&B, const DataLayout &DL,
1584 const TargetLibraryInfo &TLI) {
1585 if (!GEP.hasNoUnsignedWrap())
1586 return false;
1587
1588 Value *Base = GEP.getPointerOperand();
1589 if (auto *InnerGEP = dyn_cast<GetElementPtrInst>(Base))
1590 Base = InnerGEP->getPointerOperand();
1591
1592 ObjectSizeOpts Opts;
1593 // Workaround for gep inbounds, ptr null, idx.
1594 Opts.NullIsUnknownSize = true;
1595 // Be conservative since we are not clear on whether an out of bounds access
1596 // to the padding is UB or not.
1597 Opts.RoundToAlign = true;
1598 std::optional<TypeSize> Size = getBaseObjectSize(Base, DL, &TLI, Opts);
1599 if (!Size || Size->isScalable())
1600 return false;
1601
1603 if (Offset.BasePtr != Base || !Offset.NW.hasNoUnsignedWrap())
1604 return false;
1605
1606 if (Offset.VariableOffsets.size() != 1)
1607 return false;
1608
1609 uint64_t BitWidth = Offset.ConstantOffset.getBitWidth();
1610 auto &[Index, Scale] = Offset.VariableOffsets.front();
1611 // Bail out on non-canonical GEPs.
1612 if (Index->getType()->getScalarSizeInBits() != BitWidth)
1613 return false;
1614
1615 // Index * Scale + ConstOffset + AccessSize <= AllocSize
1616 // With nuw flag, we know that the index addition doesn't have unsigned wrap.
1617 // If (AllocSize - (ConstOffset + AccessSize)) wraps around, there is no valid
1618 // value for Index.
1619 APInt MaxIndex = (APInt(BitWidth, Size->getFixedValue() - AccessSize,
1620 /*isSigned=*/false, /*implicitTrunc=*/true) -
1621 Offset.ConstantOffset)
1622 .udiv(Scale);
1624 A = Index;
1625 B = ConstantInt::get(Index->getType(), MaxIndex);
1626 return true;
1627}
1628
1629/// Returns true if \p I is a candidate whose poison-generating flags may be
1630/// strengthened using the constraint systems.
1632 if (auto *Trunc = dyn_cast<TruncInst>(I))
1633 return Trunc->getType()->isIntegerTy() && Trunc->hasNoSignedWrap() &&
1634 !Trunc->hasNoUnsignedWrap();
1635
1636 auto *BO = dyn_cast<BinaryOperator>(I);
1637 if (!BO || !BO->getType()->isIntegerTy())
1638 return false;
1639
1640 switch (BO->getOpcode()) {
1641 case Instruction::Sub:
1642 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1643 return false;
1644 // A - B does not wrap unsigned if A >=u B, and does not wrap signed if
1645 // 0 <=s B <=s A. With a constant B, bounds on A can refine both flags.
1646 return true;
1647 case Instruction::Add:
1648 case Instruction::Mul:
1649 case Instruction::Shl:
1650 if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
1651 return false;
1652 // With a constant second operand, we can use bounds on the first operand to
1653 // refine no-wrap flags. Independently, nuw can be added for nsw if the
1654 // operands are non-negative.
1655 return isa<ConstantInt>(BO->getOperand(1)) || BO->hasNoSignedWrap();
1656 default:
1657 return false;
1658 }
1659}
1660
1661/// Try to strengthen \p I's poison generating flags using \p Info. Returns
1662/// true if \p I was modified.
1663static bool tryToStrengthenFlags(Instruction *I, ConstraintInfo &Info) {
1664 assert(canStrengthenFlags(I) && "not a candidate for flag strengthening");
1665
1666 bool Changed = false;
1667 if (!I->hasNoSignedWrap() && isKnownNoWrap(I, Info, /*Signed=*/true)) {
1668 LLVM_DEBUG(dbgs() << "Adding nsw to " << *I << "\n");
1669 I->setHasNoSignedWrap();
1670 Changed = true;
1671 }
1672 if (!I->hasNoUnsignedWrap() && isKnownNoWrap(I, Info, /*Signed=*/false)) {
1673 LLVM_DEBUG(dbgs() << "Adding nuw to " << *I << "\n");
1674 I->setHasNoUnsignedWrap();
1675 Changed = true;
1676 }
1677 return Changed;
1678}
1679
1680void State::addInfoFor(BasicBlock &BB) {
1681 addBoundsForHeaderInductions(BB);
1682 addInfoForInductions(BB);
1683 auto &DL = BB.getDataLayout();
1684
1685 Value *A, *B;
1686 CmpPredicate Pred;
1687 // True as long as the current instruction is guaranteed to execute.
1688 bool GuaranteedToExecute = true;
1689 // Queue conditions and assumes.
1690 for (Instruction &I : BB) {
1691 if (match(&I, m_ICmpLike(Pred, m_Value(), m_Value()))) {
1692 for (Use &U : I.uses()) {
1693 auto *UserI = getContextInstForUse(U);
1694 auto *DTN = DT.getNode(UserI->getParent());
1695 if (!DTN)
1696 continue;
1697 WorkList.push_back(FactOrCheck::getCheck(DTN, &U));
1698 }
1699 continue;
1700 }
1701
1702 auto AddFactFromMemoryAccess = [&](Value *Ptr, Type *AccessType) {
1703 auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
1704 if (!GEP)
1705 return;
1706 TypeSize AccessSize = DL.getTypeStoreSize(AccessType);
1707 if (!AccessSize.isFixed())
1708 return;
1709 if (GuaranteedToExecute) {
1711 Pred, A, B, DL, TLI)) {
1712 // The memory access is guaranteed to execute when BB is entered,
1713 // hence the constraint holds on entry to BB.
1714 WorkList.emplace_back(FactOrCheck::getConditionFact(
1715 DT.getNode(I.getParent()), Pred, A, B));
1716 }
1717 } else {
1718 WorkList.emplace_back(
1719 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
1720 }
1721 };
1722
1723 if (auto *LI = dyn_cast<LoadInst>(&I)) {
1724 if (!LI->isVolatile())
1725 AddFactFromMemoryAccess(LI->getPointerOperand(), LI->getAccessType());
1726 }
1727 if (auto *SI = dyn_cast<StoreInst>(&I)) {
1728 if (!SI->isVolatile())
1729 AddFactFromMemoryAccess(SI->getPointerOperand(), SI->getAccessType());
1730 }
1731
1732 auto *II = dyn_cast<IntrinsicInst>(&I);
1733 Intrinsic::ID ID = II ? II->getIntrinsicID() : Intrinsic::not_intrinsic;
1734 switch (ID) {
1735 case Intrinsic::assume: {
1736 if (!match(I.getOperand(0), m_ICmpLike(Pred, m_Value(A), m_Value(B))))
1737 break;
1738 if (GuaranteedToExecute) {
1739 // The assume is guaranteed to execute when BB is entered, hence Cond
1740 // holds on entry to BB.
1741 WorkList.emplace_back(FactOrCheck::getConditionFact(
1742 DT.getNode(I.getParent()), Pred, A, B));
1743 } else {
1744 WorkList.emplace_back(
1745 FactOrCheck::getInstFact(DT.getNode(I.getParent()), &I));
1746 }
1747 break;
1748 }
1749 // Enqueue intrinsics for simplification.
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:
1758 WorkList.push_back(
1759 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
1760 break;
1761 // Enqueue the intrinsics to add extra info.
1762 case Intrinsic::umin:
1763 case Intrinsic::umax:
1764 case Intrinsic::smin:
1765 case Intrinsic::smax:
1766 case Intrinsic::usub_sat:
1767 // TODO: handle llvm.abs as well
1768 WorkList.push_back(
1769 FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
1770 [[fallthrough]];
1771 case Intrinsic::uadd_sat:
1772 // TODO: Check if it is possible to instead only added the min/max facts
1773 // when simplifying uses of the min/max intrinsics.
1775 break;
1776 [[fallthrough]];
1777 case Intrinsic::abs:
1778 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), &I));
1779 break;
1780 }
1781
1782 // Add facts from unsigned division, remainder and logical shift right, and
1783 // from signed division and remainder.
1784 // urem x, n: result < n and result <= x
1785 // udiv x, n: result <= x
1786 // lshr x, n: result <= x
1787 // srem x, n: result >= 0 and result <= x, if x >= 0
1788 // result < n, if n > 0
1789 // sdiv x, n: result >= 0 and result <= x, if x >= 0 and n > 0
1790 // result >= 0 and result < x, if x > 0 and n > 1
1791 if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
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) &&
1798 WorkList.push_back(FactOrCheck::getInstFact(DT.getNode(&BB), BO));
1799 }
1800
1801 // Queue instructions whose flags may be strengthened, checked at the
1802 // closest point dominating all uses.
1803 if (canStrengthenFlags(&I)) {
1804 Instruction *CommonDom = findCommonDominatorOfUses(I, DT);
1805 WorkList.push_back(FactOrCheck::getCheck(
1806 DT.getNode(CommonDom->getParent()), &I, CommonDom));
1807 }
1808
1809 GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
1810 }
1811
1812 if (auto *Switch = dyn_cast<SwitchInst>(BB.getTerminator())) {
1813 for (auto &Case : Switch->cases()) {
1814 BasicBlock *Succ = Case.getCaseSuccessor();
1815 Value *V = Case.getCaseValue();
1816 if (!canAddSuccessor(BB, Succ))
1817 continue;
1818 WorkList.emplace_back(FactOrCheck::getConditionFact(
1819 DT.getNode(Succ), CmpInst::ICMP_EQ, Switch->getCondition(), V));
1820 }
1821 return;
1822 }
1823
1824 auto *Br = dyn_cast<CondBrInst>(BB.getTerminator());
1825 if (!Br)
1826 return;
1827
1828 Value *Cond = Br->getCondition();
1829
1830 // If the condition is a chain of ORs/AND and the successor only has the
1831 // current block as predecessor, queue conditions for the successor.
1832 Value *Op0, *Op1;
1833 if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
1834 match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1835 bool IsOr = match(Cond, m_LogicalOr());
1836 bool IsAnd = match(Cond, m_LogicalAnd());
1837 // If there's a select that matches both AND and OR, we need to commit to
1838 // one of the options. Arbitrarily pick OR.
1839 if (IsOr && IsAnd)
1840 IsAnd = false;
1841
1842 BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
1843 if (canAddSuccessor(BB, Successor)) {
1844 SmallVector<Value *> CondWorkList;
1845 SmallPtrSet<Value *, 8> SeenCond;
1846 auto QueueValue = [&CondWorkList, &SeenCond](Value *V) {
1847 if (SeenCond.insert(V).second)
1848 CondWorkList.push_back(V);
1849 };
1850 QueueValue(Op1);
1851 QueueValue(Op0);
1852 while (!CondWorkList.empty()) {
1853 Value *Cur = CondWorkList.pop_back_val();
1854 if (match(Cur, m_ICmpLike(Pred, m_Value(A), m_Value(B)))) {
1855 WorkList.emplace_back(FactOrCheck::getConditionFact(
1856 DT.getNode(Successor),
1857 IsOr ? CmpPredicate::getInverse(Pred) : Pred, A, B));
1858 continue;
1859 }
1860 if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
1861 QueueValue(Op1);
1862 QueueValue(Op0);
1863 continue;
1864 }
1865 if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
1866 QueueValue(Op1);
1867 QueueValue(Op0);
1868 continue;
1869 }
1870 }
1871 }
1872 return;
1873 }
1874
1875 if (!match(Br->getCondition(), m_ICmpLike(Pred, m_Value(A), m_Value(B))))
1876 return;
1877 if (canAddSuccessor(BB, Br->getSuccessor(0)))
1878 WorkList.emplace_back(FactOrCheck::getConditionFact(
1879 DT.getNode(Br->getSuccessor(0)), Pred, A, B));
1880 if (canAddSuccessor(BB, Br->getSuccessor(1)))
1881 WorkList.emplace_back(FactOrCheck::getConditionFact(
1882 DT.getNode(Br->getSuccessor(1)), CmpPredicate::getInverse(Pred), A, B));
1883}
1884
1885#ifndef NDEBUG
1887 Value *LHS, Value *RHS) {
1888 OS << "icmp " << Pred << ' ';
1889 LHS->printAsOperand(OS, /*PrintType=*/true);
1890 OS << ", ";
1891 RHS->printAsOperand(OS, /*PrintType=*/false);
1892}
1893#endif
1894
1895namespace {
1896/// Helper to keep track of a condition and if it should be treated as negated
1897/// for reproducer construction.
1898/// Pred == Predicate::BAD_ICMP_PREDICATE indicates that this entry is a
1899/// placeholder to keep the ReproducerCondStack in sync with DFSInStack.
1900struct ReproducerEntry {
1901 ICmpInst::Predicate Pred;
1902 Value *LHS;
1903 Value *RHS;
1904
1905 ReproducerEntry(ICmpInst::Predicate Pred, Value *LHS, Value *RHS)
1906 : Pred(Pred), LHS(LHS), RHS(RHS) {}
1907};
1908} // namespace
1909
1910/// Helper function to generate a reproducer function for simplifying \p Cond.
1911/// The reproducer function contains a series of @llvm.assume calls, one for
1912/// each condition in \p Stack. For each condition, the operand instruction are
1913/// cloned until we reach operands that have an entry in \p Value2Index. Those
1914/// will then be added as function arguments. \p DT is used to order cloned
1915/// instructions. The reproducer function will get added to \p M, if it is
1916/// non-null. Otherwise no reproducer function is generated.
1917static void generateReproducer(Instruction *Cond, bool IsSigned, Module *M,
1919 ConstraintInfo &Info, DominatorTree &DT) {
1920 if (!M)
1921 return;
1922
1923 LLVMContext &Ctx = Cond->getContext();
1924
1925 LLVM_DEBUG(dbgs() << "Creating reproducer for " << *Cond << "\n");
1926
1927 ValueToValueMapTy Old2New;
1930 // Traverse Cond and its operands recursively until we reach a value that's in
1931 // Value2Index or not an instruction, or not a operation that
1932 // ConstraintElimination can decompose. Such values will be considered as
1933 // external inputs to the reproducer, they are collected and added as function
1934 // arguments later.
1935 auto CollectArguments = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1936 auto &Value2Index = Info.getValue2Index(IsSigned);
1937 SmallVector<Value *, 4> WorkList(Ops);
1938 while (!WorkList.empty()) {
1939 Value *V = WorkList.pop_back_val();
1940 if (!Seen.insert(V).second)
1941 continue;
1942 if (Old2New.find(V) != Old2New.end())
1943 continue;
1944 if (isa<Constant>(V))
1945 continue;
1946
1947 auto *I = dyn_cast<Instruction>(V);
1948 if (Value2Index.contains(V) || !I ||
1950 Old2New[V] = V;
1951 Args.push_back(V);
1952 LLVM_DEBUG(dbgs() << " found external input " << *V << "\n");
1953 } else {
1954 append_range(WorkList, I->operands());
1955 }
1956 }
1957 };
1958
1959 for (auto &Entry : Stack)
1960 if (Entry.Pred != ICmpInst::BAD_ICMP_PREDICATE)
1961 CollectArguments({Entry.LHS, Entry.RHS}, ICmpInst::isSigned(Entry.Pred));
1962 CollectArguments(Cond, IsSigned);
1963
1964 SmallVector<Type *> ParamTys;
1965 for (auto *P : Args)
1966 ParamTys.push_back(P->getType());
1967
1968 FunctionType *FTy = FunctionType::get(Cond->getType(), ParamTys,
1969 /*isVarArg=*/false);
1971 Cond->getModule()->getName() +
1972 Cond->getFunction()->getName() + "repro",
1973 M);
1974 // Add arguments to the reproducer function for each external value collected.
1975 for (unsigned I = 0; I < Args.size(); ++I) {
1976 F->getArg(I)->setName(Args[I]->getName());
1977 Old2New[Args[I]] = F->getArg(I);
1978 }
1979
1980 BasicBlock *Entry = BasicBlock::Create(Ctx, "entry", F);
1981 IRBuilder<> Builder(Entry);
1982 Builder.CreateRet(Builder.getTrue());
1983 Builder.SetInsertPoint(Entry->getTerminator());
1984
1985 // Clone instructions in \p Ops and their operands recursively until reaching
1986 // an value in Value2Index (external input to the reproducer). Update Old2New
1987 // mapping for the original and cloned instructions. Sort instructions to
1988 // clone by dominance, then insert the cloned instructions in the function.
1989 auto CloneInstructions = [&](ArrayRef<Value *> Ops, bool IsSigned) {
1990 SmallVector<Value *, 4> WorkList(Ops);
1992 auto &Value2Index = Info.getValue2Index(IsSigned);
1993 while (!WorkList.empty()) {
1994 Value *V = WorkList.pop_back_val();
1995 if (Old2New.find(V) != Old2New.end())
1996 continue;
1997
1998 auto *I = dyn_cast<Instruction>(V);
1999 if (!Value2Index.contains(V) && I) {
2000 Old2New[V] = nullptr;
2001 ToClone.push_back(I);
2002 append_range(WorkList, I->operands());
2003 }
2004 }
2005
2006 sort(ToClone,
2007 [&DT](Instruction *A, Instruction *B) { return DT.dominates(A, B); });
2008 for (Instruction *I : ToClone) {
2009 Instruction *Cloned = I->clone();
2010 Old2New[I] = Cloned;
2011 Old2New[I]->setName(I->getName());
2012 Cloned->insertBefore(Builder.GetInsertPoint());
2014 Cloned->setDebugLoc({});
2015 }
2016 };
2017
2018 // Materialize the assumptions for the reproducer using the entries in Stack.
2019 // That is, first clone the operands of the condition recursively until we
2020 // reach an external input to the reproducer and add them to the reproducer
2021 // function. Then add an ICmp for the condition (with the inverse predicate if
2022 // the entry is negated) and an assert using the ICmp.
2023 for (auto &Entry : Stack) {
2024 if (Entry.Pred == ICmpInst::BAD_ICMP_PREDICATE)
2025 continue;
2026
2027 LLVM_DEBUG(dbgs() << " Materializing assumption ";
2028 dumpUnpackedICmp(dbgs(), Entry.Pred, Entry.LHS, Entry.RHS);
2029 dbgs() << "\n");
2030 CloneInstructions({Entry.LHS, Entry.RHS}, CmpInst::isSigned(Entry.Pred));
2031
2032 auto *Cmp = Builder.CreateICmp(Entry.Pred, Entry.LHS, Entry.RHS);
2033 Builder.CreateAssumption(Cmp);
2034 }
2035
2036 // Finally, clone the condition to reproduce and remap instruction operands in
2037 // the reproducer using Old2New.
2038 CloneInstructions(Cond, IsSigned);
2039 Entry->getTerminator()->setOperand(0, Cond);
2040 remapInstructionsInBlocks({Entry}, Old2New);
2041
2042 assert(!verifyFunction(*F, &dbgs()));
2043}
2044
2045/// If \p V is a variable in the system and constraint \p C does not contain \p
2046/// V, we managed to decompose \p V at this point, but likely not earlier when
2047/// the fact involving \p V was added. In that case, return a new row for
2048/// V <= decompose(V) to link the variable with the decomposition result.
2049static RowTy getDecompositionLinkRow(Value *V, const ConstraintTy &C,
2050 ConstraintInfo &Info,
2051 const DataLayout &DL) {
2052 const auto &Value2Index = Info.getValue2Index(C.IsSigned);
2053 auto It = Value2Index.find(V);
2054 if (It == Value2Index.end() ||
2055 any_of(C.Coefficients,
2056 [Id = It->second](const Entry &E) { return E.Id == Id; }))
2057 return {};
2058
2059 SmallVector<Value *> NewVariables;
2060 RowTy Row =
2061 getRowForLessEqual(Decomposition(V), decompose(V, Info, C.IsSigned, DL),
2062 Value2Index, NewVariables);
2063 return NewVariables.empty() ? Row : RowTy();
2064}
2065
2066static std::optional<bool> checkCondition(CmpInst::Predicate Pred, Value *A,
2067 Value *B, Instruction *CheckInst,
2068 ConstraintInfo &Info) {
2069 LLVM_DEBUG(dbgs() << "Checking " << *CheckInst << "\n");
2070
2071 auto TryWithConstraint = [&](const ConstraintTy &R) -> std::optional<bool> {
2072 if (R.empty()) {
2073 LLVM_DEBUG(dbgs() << " failed to decompose condition\n");
2074 return std::nullopt;
2075 }
2076
2077 auto &CSToUse = Info.getCS(R.IsSigned);
2078 if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
2079 if (!DebugCounter::shouldExecute(EliminatedCounter))
2080 return std::nullopt;
2081 LLVM_DEBUG({
2082 dbgs() << "Condition ";
2084 *ImpliedCondition ? Pred
2086 A, B);
2087 dbgs() << " implied by dominating constraints\n";
2088 CSToUse.dump();
2089 });
2090 return ImpliedCondition;
2091 }
2092 return std::nullopt;
2093 };
2094
2095 // Retry the query after adding additional facts for A == decompose(A) and B
2096 // == decompose(B), if needed.
2097 auto TryWithLinkedDecomposition =
2098 [&](const ConstraintTy &C) -> std::optional<bool> {
2099 return Info.tryWithLinkRows(A, B, C, [&] { return TryWithConstraint(C); });
2100 };
2101
2102 auto R = Info.getConstraintForSolving(Pred, A, B);
2103 if (auto ImpliedCondition = TryWithLinkedDecomposition(R))
2104 return ImpliedCondition;
2105
2106 // For non-negative operands unsigned queries can also be checked against the
2107 // signed system.
2108 if (CmpInst::isUnsigned(Pred) && A->getType()->isIntegerTy()) {
2109 SmallVector<Value *> NewVariables;
2110 auto SR = Info.getConstraint(ICmpInst::getSignedPredicate(Pred), A, B,
2111 NewVariables);
2112 if (NewVariables.empty() && !SR.empty() && Info.isKnownNonNegative(A) &&
2113 Info.isKnownNonNegative(B))
2114 if (auto ImpliedCondition = TryWithConstraint(SR))
2115 return ImpliedCondition;
2116 }
2117
2118 // Additionally, query the signed system for eq/ne predicates if we know about
2119 // A or B.
2121 const auto &Value2Index = Info.getValue2Index(/*Signed=*/true);
2122 if (!Value2Index.contains(A) && !Value2Index.contains(B))
2123 return std::nullopt;
2124
2125 SmallVector<Value *> NewVariables;
2126 auto SR = Info.getConstraint(Pred, A, B, NewVariables,
2127 /*ForceSignedSystem=*/true);
2128 if (NewVariables.empty()) {
2129 if (auto ImpliedCondition = TryWithLinkedDecomposition(SR))
2130 return ImpliedCondition;
2131 }
2132 }
2133 return std::nullopt;
2134}
2135
2137 CmpPredicate Pred, Value *A, Value *B, Instruction *CheckInst,
2138 ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
2139 Instruction *ContextInst, Module *ReproducerModule,
2140 ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT,
2142 auto ReplaceCmpWithConstant = [&](Instruction *CheckInst, bool IsTrue) {
2143 generateReproducer(CheckInst, ICmpInst::isSigned(Pred), ReproducerModule,
2144 ReproducerCondStack, Info, DT);
2145 Constant *ConstantC = ConstantInt::getBool(
2146 CmpInst::makeCmpResultType(CheckInst->getType()), IsTrue);
2147 bool Changed = CheckInst->replaceUsesWithIf(ConstantC, [&](Use &U) {
2148 auto *UserI = getContextInstForUse(U);
2149 auto *DTN = DT.getNode(UserI->getParent());
2150 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
2151 return false;
2152 if (UserI->getParent() == ContextInst->getParent() &&
2153 UserI->comesBefore(ContextInst))
2154 return false;
2155
2156 // Conditions in an assume trivially simplify to true. Skip uses
2157 // in assume calls to not destroy the available information.
2158 auto *II = dyn_cast<IntrinsicInst>(U.getUser());
2159 return !II || II->getIntrinsicID() != Intrinsic::assume;
2160 });
2161 NumCondsRemoved++;
2162
2163 // Update the debug value records that satisfy the same condition used
2164 // in replaceUsesWithIf.
2166 findDbgUsers(CheckInst, DVRUsers);
2167
2168 for (auto *DVR : DVRUsers) {
2169 auto *DTN = DT.getNode(DVR->getParent());
2170 if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut)
2171 continue;
2172
2173 auto *MarkedI = DVR->getInstruction();
2174 if (MarkedI->getParent() == ContextInst->getParent() &&
2175 MarkedI->comesBefore(ContextInst))
2176 continue;
2177
2178 DVR->replaceVariableLocationOp(CheckInst, ConstantC);
2179 }
2180
2181 if (CheckInst->use_empty())
2182 ToRemove.push_back(CheckInst);
2183
2184 return Changed;
2185 };
2186
2187 if (auto ImpliedCondition = checkCondition(Pred, A, B, CheckInst, Info))
2188 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2189
2190 // When the predicate is samesign and unsigned, we can also make use of the
2191 // signed predicate information.
2192 if (Pred.hasSameSign() && ICmpInst::isUnsigned(Pred))
2193 if (auto ImpliedCondition = checkCondition(
2194 ICmpInst::getSignedPredicate(Pred), A, B, CheckInst, Info))
2195 return ReplaceCmpWithConstant(CheckInst, *ImpliedCondition);
2196
2197 return false;
2198}
2199
2200static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
2202 auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
2203 // TODO: generate reproducer for min/max.
2204 MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));
2205 ToRemove.push_back(MinMax);
2206 return true;
2207 };
2208
2210 ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
2211 if (auto ImpliedCondition = checkCondition(
2212 Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))
2213 return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
2214 if (auto ImpliedCondition = checkCondition(
2215 Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))
2216 return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);
2217 return false;
2218}
2219
2220static bool checkAndReplaceCmp(CmpIntrinsic *I, ConstraintInfo &Info,
2222 Value *LHS = I->getOperand(0);
2223 Value *RHS = I->getOperand(1);
2224 if (checkCondition(I->getGTPredicate(), LHS, RHS, I, Info).value_or(false)) {
2225 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 1));
2226 ToRemove.push_back(I);
2227 return true;
2228 }
2229 if (checkCondition(I->getLTPredicate(), LHS, RHS, I, Info).value_or(false)) {
2230 I->replaceAllUsesWith(ConstantInt::getSigned(I->getType(), -1));
2231 ToRemove.push_back(I);
2232 return true;
2233 }
2234 if (checkCondition(ICmpInst::ICMP_EQ, LHS, RHS, I, Info).value_or(false)) {
2235 I->replaceAllUsesWith(ConstantInt::get(I->getType(), 0));
2236 ToRemove.push_back(I);
2237 return true;
2238 }
2239 return false;
2240}
2241
2242/// Try to replace \p USub by a plain subtract, if \p Info proves it cannot
2243/// saturate. Returns true if \p USub was replaced.
2244static bool checkAndReplaceUSubSat(SaturatingInst *USub, ConstraintInfo &Info,
2246 // usub.sat(A, B) is A - B exactly when A >=u B.
2247 Value *A = USub->getLHS();
2248 Value *B = USub->getRHS();
2249 if (!checkCondition(CmpInst::ICMP_UGE, A, B, USub, Info).value_or(false))
2250 return false;
2251
2252 IRBuilder<> Builder(USub);
2253 Value *Sub = Builder.CreateSub(A, B, "", /*HasNUW=*/true,
2254 /*HasNSW=*/Info.isKnownNonNegative(A));
2255 USub->replaceAllUsesWith(Sub);
2256 Sub->takeName(USub);
2257 ToRemove.push_back(USub);
2258 return true;
2259}
2260
2261static void
2262removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
2263 Module *ReproducerModule,
2264 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
2265 SmallVectorImpl<StackEntry> &DFSInStack) {
2266 Info.getDecomposeCache().clear();
2267 Info.popLastConstraint(E.IsSigned);
2268 // Remove variables in the system that went out of scope.
2269 auto &Mapping = Info.getValue2Index(E.IsSigned);
2270 for (Value *V : E.ValuesToRelease)
2271 Mapping.erase(V);
2272 Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
2273 DFSInStack.pop_back();
2274 if (ReproducerModule)
2275 ReproducerCondStack.pop_back();
2276}
2277
2278/// Check if either the first condition of an AND or OR is implied by the
2279/// (negated in case of OR) second condition or vice versa.
2281 FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
2282 SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
2283 SmallVectorImpl<StackEntry> &DFSInStack,
2285 Instruction *JoinOp = CB.getContextInst();
2286 if (JoinOp->use_empty())
2287 return false;
2288
2289 Instruction *CmpToCheck = cast<Instruction>(CB.getInstructionToSimplify());
2290 unsigned OtherOpIdx = JoinOp->getOperand(0) == CmpToCheck ? 1 : 0;
2291
2292 // Don't try to simplify the first condition of a select by the second, as
2293 // this may make the select more poisonous than the original one.
2294 // TODO: check if the first operand may be poison.
2295 if (OtherOpIdx != 0 && isa<SelectInst>(JoinOp))
2296 return false;
2297
2298 unsigned OldSize = DFSInStack.size();
2299 llvm::scope_exit InfoRestorer([&]() {
2300 // Remove entries again.
2301 while (OldSize < DFSInStack.size()) {
2302 StackEntry E = DFSInStack.back();
2303 removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
2304 DFSInStack);
2305 }
2306 });
2307 bool IsOr = match(JoinOp, m_LogicalOr());
2308 SmallVector<Value *, 4> Worklist({JoinOp->getOperand(OtherOpIdx)});
2309 // Do a traversal of the AND/OR tree to add facts from leaf compares.
2310 while (!Worklist.empty()) {
2311 Value *Val = Worklist.pop_back_val();
2312 Value *LHS, *RHS;
2314 if (match(Val, m_ICmpLike(Pred, m_Value(LHS), m_Value(RHS)))) {
2315 // For OR, check if the negated condition implies CmpToCheck.
2316 if (IsOr)
2318 // Optimistically add fact from the other compares in the AND/OR.
2319 Info.addFact(Pred, LHS, RHS, CB.NumIn, CB.NumOut, DFSInStack);
2320 continue;
2321 }
2322 if (IsOr ? match(Val, m_LogicalOr(m_Value(LHS), m_Value(RHS)))
2323 : match(Val, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) {
2324 Worklist.push_back(LHS);
2325 Worklist.push_back(RHS);
2326 }
2327 }
2328 if (OldSize == DFSInStack.size())
2329 return false;
2330
2331 Value *A, *B;
2333 [[maybe_unused]] bool Matched =
2334 match(CmpToCheck, m_ICmpLike(Pred, m_Value(A), m_Value(B)));
2335 assert(Matched && "expected icmp-like match");
2336 // Check if the second condition can be simplified now.
2337 if (auto ImpliedCondition = checkCondition(Pred, A, B, CmpToCheck, Info)) {
2338 if (IsOr == *ImpliedCondition)
2339 JoinOp->replaceAllUsesWith(
2340 ConstantInt::getBool(JoinOp->getType(), *ImpliedCondition));
2341 else
2342 JoinOp->replaceAllUsesWith(JoinOp->getOperand(OtherOpIdx));
2343 ToRemove.push_back(JoinOp);
2344 return true;
2345 }
2346
2347 return false;
2348}
2349
2350void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
2351 unsigned NumIn, unsigned NumOut,
2352 SmallVectorImpl<StackEntry> &DFSInStack) {
2353 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, false);
2354 // If the Pred is eq/ne, also add the fact to signed system.
2356 addFactImpl(Pred, A, B, NumIn, NumOut, DFSInStack, true);
2357 if (Pred == CmpInst::ICMP_NE)
2358 tightenBoundUsingNe(A, B, NumIn, NumOut, DFSInStack);
2359}
2360
2361void ConstraintInfo::tightenBoundUsingNe(
2362 Value *A, Value *B, unsigned NumIn, unsigned NumOut,
2363 SmallVectorImpl<StackEntry> &DFSInStack) {
2364 if (!A->getType()->isIntOrPtrTy())
2365 return;
2366
2367 for (bool IsSigned : {false, true}) {
2368 // In the unsigned system `A u>= 0` holds for every A, so getConstraint
2369 // already turned `A != 0` into `A u> 0`.
2370 if (!IsSigned && match(B, m_Zero()))
2371 continue;
2372
2373 // Skip if there are any unknown variables.
2374 const auto &Value2Index = getValue2Index(IsSigned);
2375 if (any_of(decompose(A, *this, IsSigned, DL).Vars,
2376 [&Value2Index](const DecompEntry &E) {
2377 return !Value2Index.contains(E.Variable);
2378 }))
2379 continue;
2380
2381 // If the system implies `A >= B` then together with `A != B` we get the
2382 // strict `A > B`; symmetrically `A <= B` becomes `A < B`.
2383 CmpInst::Predicate GEPred =
2385 CmpInst::Predicate LEPred =
2387 for (CmpInst::Predicate NonStrict : {GEPred, LEPred}) {
2388 if (!doesHold(NonStrict, A, B))
2389 continue;
2391 LLVM_DEBUG(dbgs() << "Tightening '";
2392 dumpUnpackedICmp(dbgs(), NonStrict, A, B); dbgs() << "' to '";
2394 dbgs() << "' using inequality\n");
2395 addFactImpl(Strict, A, B, NumIn, NumOut, DFSInStack,
2396 /*ForceSignedSystem=*/false);
2397 break;
2398 }
2399 }
2400}
2401
2402void ConstraintInfo::addFactImpl(CmpInst::Predicate Pred, Value *A, Value *B,
2403 unsigned NumIn, unsigned NumOut,
2404 SmallVectorImpl<StackEntry> &DFSInStack,
2405 bool ForceSignedSystem) {
2406 SmallVector<Value *> NewVariables;
2407 auto R = getConstraint(Pred, A, B, NewVariables, ForceSignedSystem);
2408
2409 // TODO: Support non-equality for facts as well.
2410 if (R.empty() || R.isNe())
2411 return;
2412
2413 auto &CSToUse = getCS(R.IsSigned);
2414 // A row implied by a single existing row adds no information. Rows in the
2415 // system are removed in reverse order, so the existing row outlives R. Rows
2416 // in the system are normalized, so normalize R before comparing.
2417 if (!R.isEq() && NewVariables.empty()) {
2418 ConstraintSystem::normalizeByGCD(R.Coefficients);
2419 if (CSToUse.isImpliedBySingleRow(R.Coefficients))
2420 return;
2421 }
2422 LLVM_DEBUG(dbgs() << "Adding '"; dumpUnpackedICmp(dbgs(), Pred, A, B);
2423 dbgs() << "'\n");
2424 bool Added = CSToUse.addRow(R.Coefficients, R.NumVars);
2425 if (!Added)
2426 return;
2427
2428 DecomposeCache.clear();
2429
2430 // If R has been added to the system, add the new variables and queue it for
2431 // removal once it goes out-of-scope.
2432 SmallVector<Value *, 2> ValuesToRelease;
2433 auto &Value2Index = getValue2Index(R.IsSigned);
2434 for (Value *V : NewVariables) {
2435 Value2Index.try_emplace(V, Value2Index.size() + 1);
2436 ValuesToRelease.push_back(V);
2437 }
2438
2439 LLVM_DEBUG({
2440 dbgs() << " constraint: ";
2441 dumpConstraint(R.Coefficients, getValue2Index(R.IsSigned));
2442 dbgs() << "\n";
2443 });
2444
2445 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
2446 std::move(ValuesToRelease));
2447
2448 if (!R.IsSigned) {
2449 for (Value *V : NewVariables) {
2450 // Add V > -1 constraints for all new variables.
2451 CSToUse.addRow({Entry(0, 0), Entry(-1, Value2Index.at(V))},
2452 Value2Index.size());
2453 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
2454 SmallVector<Value *, 2>());
2455 }
2456 }
2457
2458 if (R.isEq()) {
2459 // Also add the inverted constraint for equality constraints.
2460 for (Entry &E : R.Coefficients)
2461 if (MulOverflow(E.Coefficient, int64_t(-1), E.Coefficient))
2462 return;
2463 CSToUse.addRow(R.Coefficients, R.NumVars);
2464
2465 DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
2466 SmallVector<Value *, 2>());
2467 }
2468}
2469
2470/// Replace the uses of \p II, which is known not to overflow, by the
2471/// corresponding plain binary operation and a false overflow flag.
2474 bool Changed = false;
2475 IRBuilder<> Builder(II->getIterator());
2476 Value *Res = nullptr;
2477 for (User *U : make_early_inc_range(II->users())) {
2478 if (match(U, m_ExtractValue<0>(m_Value()))) {
2479 if (!Res)
2480 Res = Builder.CreateNoWrapBinOp(II->getBinaryOp(), II->getLHS(),
2481 II->getRHS(),
2482 /*IsNUW=*/!II->isSigned(),
2483 /*IsNSW=*/II->isSigned());
2484 U->replaceAllUsesWith(Res);
2485 Changed = true;
2486 } else if (match(U, m_ExtractValue<1>(m_Value()))) {
2487 U->replaceAllUsesWith(Builder.getFalse());
2488 Changed = true;
2489 } else
2490 continue;
2491
2492 if (U->use_empty()) {
2493 auto *I = cast<Instruction>(U);
2494 ToRemove.push_back(I);
2495 I->setOperand(0, PoisonValue::get(II->getType()));
2496 Changed = true;
2497 }
2498 }
2499
2500 if (II->use_empty()) {
2501 // Do not erase II here: the worklist may still hold Uses of II's operands.
2502 for (Use &Arg : II->args())
2503 Arg.set(PoisonValue::get(Arg->getType()));
2504 ToRemove.push_back(II);
2505 Changed = true;
2506 }
2507 return Changed;
2508}
2509
2510static bool
2513 if (!isKnownNoWrap(II, Info, II->isSigned()))
2514 return false;
2516}
2517
2519 ScalarEvolution *SE,
2522 const ScalarOptions &Opts = getScalarOptions(F);
2523 bool Changed = false;
2524 DT.updateDFSNumbers();
2525 SmallVector<Value *> FunctionArgs(llvm::make_pointer_range(F.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())
2531 : nullptr);
2532
2533 // First, collect conditions implied by branches and blocks with their
2534 // Dominator DFS in and out numbers.
2535 for (BasicBlock &BB : F) {
2536 if (!DT.getNode(&BB))
2537 continue;
2538 S.addInfoFor(BB);
2539 }
2540
2541 // Next, sort worklist by dominance, so that dominating conditions to check
2542 // and facts come before conditions and facts dominated by them. If a
2543 // condition to check and a fact have the same numbers, conditional facts come
2544 // first. Assume facts and checks are ordered according to their relative
2545 // order in the containing basic block. Also make sure conditions with
2546 // constant operands come before conditions without constant operands. This
2547 // increases the effectiveness of the current signed <-> unsigned fact
2548 // transfer logic.
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);
2554 };
2555 // If both entries have the same In numbers, conditional facts come first.
2556 // Otherwise use the relative order in the basic block.
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;
2562 }
2563 if (A.isConditionFact())
2564 return true;
2565 if (B.isConditionFact())
2566 return false;
2567 auto *InstA = A.getContextInst();
2568 auto *InstB = B.getContextInst();
2569 return InstA->comesBefore(InstB);
2570 }
2571 return A.NumIn < B.NumIn;
2572 });
2573
2574 SmallVector<Instruction *> ToRemove;
2575
2576 // Finally, process ordered worklist and eliminate implied conditions.
2577 SmallVector<StackEntry, 16> DFSInStack;
2578 SmallVector<ReproducerEntry> ReproducerCondStack;
2579 for (FactOrCheck &CB : S.WorkList) {
2580 // First, pop entries from the stack that are out-of-scope for CB. Remove
2581 // the corresponding entry from the constraint system.
2582 while (!DFSInStack.empty()) {
2583 auto &E = DFSInStack.back();
2584 LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
2585 << "\n");
2586 LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
2587 assert(E.NumIn <= CB.NumIn);
2588 if (CB.NumOut <= E.NumOut)
2589 break;
2590 LLVM_DEBUG({
2591 dbgs() << "Removing ";
2592 dumpConstraint(Info.getCS(E.IsSigned).getLastConstraint(),
2593 Info.getValue2Index(E.IsSigned));
2594 dbgs() << "\n";
2595 });
2596 removeEntryFromStack(E, Info, ReproducerModule.get(), ReproducerCondStack,
2597 DFSInStack);
2598 }
2599
2600 CmpPredicate Pred;
2601 Value *A, *B;
2602 // For a block, check if any CmpInsts become known based on the current set
2603 // of constraints.
2604 if (CB.isCheck()) {
2605 Instruction *Inst = CB.getInstructionToSimplify();
2606 if (!Inst)
2607 continue;
2608 if (canStrengthenFlags(Inst)) {
2609 Changed |= tryToStrengthenFlags(Inst, Info);
2610 continue;
2611 }
2612 LLVM_DEBUG(dbgs() << "Processing condition to simplify: " << *Inst
2613 << "\n");
2614 if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {
2616 } else if (match(Inst, m_ICmpLike(Pred, m_Value(A), m_Value(B)))) {
2618 Pred, A, B, Inst, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
2619 ReproducerModule.get(), ReproducerCondStack, S.DT, ToRemove);
2620 if (!Simplified &&
2621 match(CB.getContextInst(), m_LogicalOp(m_Value(), m_Value()))) {
2623 CB, Info, ReproducerModule.get(), ReproducerCondStack, DFSInStack,
2624 ToRemove);
2625 }
2627 } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
2628 Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);
2629 } else if (auto *CmpIntr = dyn_cast<CmpIntrinsic>(Inst)) {
2630 Changed |= checkAndReplaceCmp(CmpIntr, Info, ToRemove);
2631 } else if (match(Inst, m_Intrinsic<Intrinsic::usub_sat>())) {
2632 Changed |=
2634 }
2635 continue;
2636 }
2637
2638 auto AddFact = [&](CmpPredicate Pred, Value *A, Value *B) {
2639 LLVM_DEBUG(dbgs() << "Processing fact to add to the system: ";
2640 dumpUnpackedICmp(dbgs(), Pred, A, B); dbgs() << "\n");
2641 if (Info.getCS(CmpInst::isSigned(Pred)).size() >
2642 Opts.constraint_elimination_max_rows) {
2643 LLVM_DEBUG(
2644 dbgs()
2645 << "Skip adding constraint because system has too many rows.\n");
2646 return;
2647 }
2648
2649 Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
2650 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size())
2651 ReproducerCondStack.emplace_back(Pred, A, B);
2652
2654 // If samesign is present on the ICmp, simply flip the sign of the
2655 // predicate, transferring the information from the signed system to the
2656 // unsigned system, and viceversa.
2657 if (Pred.hasSameSign()) {
2659 CB.NumIn, CB.NumOut, DFSInStack);
2660 // The operands also have the same sign: if one of them is known to
2661 // be non-negative (or negative), so is the other.
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;
2668 Info.addFact(IsNegative ? CmpInst::ICMP_SLT : CmpInst::ICMP_SGE,
2669 OtherOp, Constant::getNullValue(A->getType()),
2670 CB.NumIn, CB.NumOut, DFSInStack);
2671 }
2672 }
2673 } else {
2674 Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut,
2675 DFSInStack);
2676 }
2677 }
2678
2679 // (X | Y) >s -1 implies X >s -1 and Y >s -1, because the sign bit of an
2680 // OR is the OR of the operand sign bits. Similarly, (X & Y) <s 0 implies
2681 // X <s 0 and Y <s 0. Look through these canonical forms produced by
2682 // InstCombine so the sign facts on the operands are available to the
2683 // solver.
2684 if ((Pred == CmpInst::ICMP_SGT && match(B, m_AllOnes())) ||
2685 (Pred == CmpInst::ICMP_SLT && match(B, m_Zero()))) {
2686 unsigned Opc =
2687 Pred == CmpInst::ICMP_SGT ? Instruction::Or : Instruction::And;
2688 SmallVector<Value *> Worklist = {A};
2689 SmallPtrSet<Value *, 4> Seen;
2690 while (!Worklist.empty()) {
2691 Value *Cur = Worklist.pop_back_val();
2692 auto *BO = dyn_cast<BinaryOperator>(Cur);
2693 if (!BO || BO->getOpcode() != Opc)
2694 continue;
2695 for (Value *Op : {BO->getOperand(0), BO->getOperand(1)}) {
2696 if (!Seen.insert(Op).second)
2697 continue;
2698 Worklist.push_back(Op);
2699 Info.addFact(Pred, Op, B, CB.NumIn, CB.NumOut, DFSInStack);
2700 }
2701 }
2702 }
2703
2704 if (ReproducerModule && DFSInStack.size() > ReproducerCondStack.size()) {
2705 // Add dummy entries to ReproducerCondStack to keep it in sync with
2706 // DFSInStack.
2707 for (unsigned I = 0,
2708 E = (DFSInStack.size() - ReproducerCondStack.size());
2709 I < E; ++I) {
2710 ReproducerCondStack.emplace_back(ICmpInst::BAD_ICMP_PREDICATE,
2711 nullptr, nullptr);
2712 }
2713 }
2714 };
2715
2716 if (!CB.isConditionFact()) {
2717 Value *X;
2718 if (match(CB.Inst, m_Intrinsic<Intrinsic::abs>(m_Value(X)))) {
2719 // If is_int_min_poison is true then we may assume llvm.abs >= 0.
2720 if (cast<ConstantInt>(CB.Inst->getOperand(1))->isOne())
2721 AddFact(CmpInst::ICMP_SGE, CB.Inst,
2722 ConstantInt::get(CB.Inst->getType(), 0));
2723 AddFact(CmpInst::ICMP_SGE, CB.Inst, X);
2724 continue;
2725 }
2726
2727 if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(CB.Inst)) {
2728 Pred = ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
2729 AddFact(Pred, MinMax, MinMax->getLHS());
2730 AddFact(Pred, MinMax, MinMax->getRHS());
2731 continue;
2732 }
2733 if (auto *USatI = dyn_cast<SaturatingInst>(CB.Inst)) {
2734 switch (USatI->getIntrinsicID()) {
2735 default:
2736 llvm_unreachable("Unexpected intrinsic.");
2737 case Intrinsic::uadd_sat:
2738 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getLHS());
2739 AddFact(ICmpInst::ICMP_UGE, USatI, USatI->getRHS());
2740 break;
2741 case Intrinsic::usub_sat:
2742 AddFact(ICmpInst::ICMP_ULE, USatI, USatI->getLHS());
2743 break;
2744 }
2745 continue;
2746 }
2747
2748 if (auto *BO = dyn_cast<BinaryOperator>(CB.Inst)) {
2749 if (BO->getOpcode() == Instruction::URem) {
2750 // urem x, n: result < n (remainder is always less than divisor)
2751 AddFact(CmpInst::ICMP_ULT, BO, BO->getOperand(1));
2752 // urem x, n: result <= x (remainder is at most the dividend)
2753 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(0));
2754 continue;
2755 }
2756 if (BO->getOpcode() == Instruction::UDiv) {
2757 // udiv x, n: result <= x (quotient is at most the dividend)
2758 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(0));
2759 continue;
2760 }
2761 if (BO->getOpcode() == Instruction::LShr) {
2762 // lshr x, n: result <= x (right shift cannot increase the value)
2763 AddFact(CmpInst::ICMP_ULE, BO, BO->getOperand(0));
2764 continue;
2765 }
2766 if (BO->getOpcode() == Instruction::SRem) {
2767 Value *X = BO->getOperand(0);
2768 Value *N = BO->getOperand(1);
2769 Constant *Zero = Constant::getNullValue(BO->getType());
2770 if (Info.doesHold(CmpInst::ICMP_SGE, X, Zero) ||
2771 isKnownNonNegative(X, F.getDataLayout())) {
2772 // srem x, n: result >= 0, if x >= 0 (result has the sign of x)
2773 AddFact(CmpInst::ICMP_SGE, BO, Zero);
2774 // srem x, n: result <= x, if x >= 0 (|result| <= |x| and both are
2775 // non-negative)
2776 AddFact(CmpInst::ICMP_SLE, BO, X);
2777 }
2778 if (Info.doesHold(CmpInst::ICMP_SGE, N, Zero) ||
2779 isKnownPositive(N, F.getDataLayout())) {
2780 // srem x, n: result <= n, if n >= 0 (|result| < n, so result <= n -
2781 // 1
2782 AddFact(CmpInst::ICMP_SLT, BO, N);
2783 }
2784 continue;
2785 }
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))
2790 continue;
2791
2792 bool IsStrict = Info.isKnownPositive(X) &&
2793 Info.doesHold(CmpInst::ICMP_SGT, N,
2794 ConstantInt::get(N->getType(), 1));
2795 AddFact(CmpInst::ICMP_SGE, BO, Constant::getNullValue(BO->getType()));
2796 AddFact(IsStrict ? CmpInst::ICMP_SLT : CmpInst::ICMP_SLE, BO, X);
2797 continue;
2798 }
2799 }
2800
2801 auto &DL = F.getDataLayout();
2802 auto AddFactsAboutIndices = [&](Value *Ptr, Type *AccessType) {
2803 CmpPredicate Pred;
2804 Value *A, *B;
2807 DL.getTypeStoreSize(AccessType).getFixedValue(), Pred, A, B, DL,
2808 TLI))
2809 AddFact(Pred, A, B);
2810 };
2811
2812 if (auto *LI = dyn_cast<LoadInst>(CB.Inst)) {
2813 AddFactsAboutIndices(LI->getPointerOperand(), LI->getAccessType());
2814 continue;
2815 }
2816 if (auto *SI = dyn_cast<StoreInst>(CB.Inst)) {
2817 AddFactsAboutIndices(SI->getPointerOperand(), SI->getAccessType());
2818 continue;
2819 }
2820 }
2821
2822 if (CB.isConditionFact()) {
2823 Pred = CB.Cond.Pred;
2824 A = CB.Cond.Op0;
2825 B = CB.Cond.Op1;
2826 if (CB.DoesHold.Pred != CmpInst::BAD_ICMP_PREDICATE &&
2827 !Info.doesHold(CB.DoesHold.Pred, CB.DoesHold.Op0, CB.DoesHold.Op1)) {
2828 LLVM_DEBUG({
2829 dbgs() << "Not adding fact ";
2831 dbgs() << " because precondition ";
2832 dumpUnpackedICmp(dbgs(), CB.DoesHold.Pred, CB.DoesHold.Op0,
2833 CB.DoesHold.Op1);
2834 dbgs() << " does not hold.\n";
2835 });
2836 continue;
2837 }
2838 } else {
2839 [[maybe_unused]] bool Matched =
2842 assert(Matched &&
2843 "Must have an assume intrinsic with a icmp like operand");
2844 }
2845 AddFact(Pred, A, B);
2846 }
2847
2848 if (ReproducerModule && !ReproducerModule->functions().empty()) {
2849 std::string S;
2850 raw_string_ostream StringS(S);
2851 ReproducerModule->print(StringS, nullptr);
2852 OptimizationRemark Rem(DEBUG_TYPE, "Reproducer", &F);
2853 Rem << ore::NV("module") << S;
2854 ORE.emit(Rem);
2855 }
2856
2857#ifndef NDEBUG
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");
2865#endif
2866
2867 for (Instruction *I : ToRemove)
2868 I->eraseFromParent();
2869 return Changed;
2870}
2871
2874 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
2875 auto &LI = AM.getResult<LoopAnalysis>(F);
2876 // SCEV is only used for loops, only construct it if there are some.
2877 auto *SE = LI.empty() ? nullptr : &AM.getResult<ScalarEvolutionAnalysis>(F);
2879 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
2880 if (!eliminateConstraints(F, DT, LI, SE, ORE, TLI))
2881 return PreservedAnalyses::all();
2882
2886 return PA;
2887}
const TargetLowering & TLI
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
uint64_t uint64_t
ReachingDefInfo InstSet & ToRemove
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
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)
#define DEBUG_TYPE
This is the interface for a simple mod/ref and alias analysis over globals.
Hexagon Common GEP
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[]
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
uint64_t IntrinsicInst * II
#define P(N)
if(PassOpts->AAPipeline)
This file defines the PointerIntPair class.
static StringRef getName(Value *V)
SmallVector< MachineOperand, 4 > Cond
This file contains some templates that are useful if you are working with the STL at all.
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)
Definition Statistic.h:171
#define LLVM_DEBUG(...)
Definition Debug.h:119
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition APInt.h:78
uint64_t getZExtValue() const
Get zero extended value.
Definition APInt.h:1560
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition APInt.h:202
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition APInt.h:1205
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition APInt.h:376
LLVM_ABI APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition APInt.cpp:1695
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition APInt.h:1115
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition APInt.h:205
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition APInt.h:212
bool isNegative() const
Determine sign of this APInt.
Definition APInt.h:325
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition APInt.h:215
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition APInt.h:1134
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
Definition APInt.h:428
bool isOne() const
Determine if this is a value of 1.
Definition APInt.h:385
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),...
Definition ArrayRef.h:40
LLVM Basic Block Representation.
Definition BasicBlock.h:62
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition BasicBlock.h:509
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition BasicBlock.h:206
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.
Definition BasicBlock.h:237
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
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.
Definition InstrTypes.h:921
bool isEquality() const
Determine if this is an equals/not equals predicate.
Definition InstrTypes.h:978
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition InstrTypes.h:740
@ ICMP_SLT
signed less than
Definition InstrTypes.h:769
@ ICMP_SLE
signed less or equal
Definition InstrTypes.h:770
@ ICMP_UGE
unsigned greater or equal
Definition InstrTypes.h:764
@ ICMP_UGT
unsigned greater than
Definition InstrTypes.h:763
@ ICMP_SGT
signed greater than
Definition InstrTypes.h:767
@ ICMP_ULT
unsigned less than
Definition InstrTypes.h:765
@ ICMP_NE
not equal
Definition InstrTypes.h:762
@ ICMP_SGE
signed greater or equal
Definition InstrTypes.h:768
@ ICMP_ULE
unsigned less or equal
Definition InstrTypes.h:766
bool isSigned() const
Definition InstrTypes.h:993
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.
Definition InstrTypes.h:890
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Definition InstrTypes.h:934
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition InstrTypes.h:852
bool isUnsigned() const
Definition InstrTypes.h:999
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.
Definition Constants.h:87
bool isNegative() const
Definition Constants.h:214
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
Definition Constants.h:135
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
Definition Constants.h:174
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
Definition Constants.h:162
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition Constants.h:168
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition Constants.h:159
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.
Definition Constant.h:44
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.
Definition DataLayout.h:64
static bool shouldExecute(CounterInfo &Counter)
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:766
iterator end()
Definition DenseMap.h:686
unsigned size() const
Definition DenseMap.h:717
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
NodeT * getBlock() const
unsigned getDFSNumOut() const
Analysis pass which computes a DominatorTree.
Definition Dominators.h:241
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.
Definition Dominators.h:122
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)
Definition Function.h:169
static GEPNoWrapFlags none()
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
@ ExternalLinkage
Externally visible function.
Definition GlobalValue.h:53
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...
Definition IRBuilder.h:2987
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.
Definition LLVMContext.h:76
Analysis pass that exposes the LoopInfo for a function.
Definition LoopInfo.h:598
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
size_type size() const
Definition MapVector.h:59
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
Definition Module.h:68
The optimization diagnostic interface.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Definition Operator.h:78
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.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
Definition Analysis.h:151
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Definition Analysis.h:132
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...
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.
Definition Type.h:46
LLVM_ABI unsigned getIntegerBitWidth() const
bool isPointerTy() const
True if this is an instance of PointerType.
Definition Type.h:277
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition Type.h:252
A Use represents the edge between a Value definition and its users.
Definition Use.h:35
Value * getOperand(unsigned i) const
Definition User.h:207
iterator find(const KeyT &Val)
Definition ValueMap.h:160
iterator end()
Definition ValueMap.h:139
LLVM Value Representation.
Definition Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition Value.h:257
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition Value.cpp:548
LLVM_ABI const Value * stripPointerCastsSameRepresentation() const
Strip off pointer casts, all-zero GEPs and address space casts but ensures the representation of the ...
Definition Value.cpp:715
bool use_empty() const
Definition Value.h:348
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...
Definition Value.cpp:556
Represents an op.with.overflow intrinsic.
constexpr ScalarTy getFixedValue() const
Definition TypeSize.h:201
constexpr bool isFixed() const
Returns true if the quantity is not scaled by vscale.
Definition TypeSize.h:172
const ParentTy * getParent() const
Definition ilist_node.h:34
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Entry
Definition COFF.h:862
@ BasicBlock
Various leaf nodes.
Definition ISDOpcodes.h:83
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...
Definition CoroShape.h:32
DiagnosticInfoOptimizationBase::Argument NV
NodeAddr< UseNode * > Use
Definition RDFGraph.h:385
bool empty() const
Definition BasicBlock.h:101
friend class Instruction
Iterator for Instructions in a `BasicBlock.
Definition BasicBlock.h:73
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.
Definition STLExtras.h:316
@ Offset
Definition DWP.cpp:577
void stable_sort(R &&Range)
Definition STLExtras.h:2132
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1781
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1755
@ 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.
Definition Casting.h:643
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.
Definition STLExtras.h:2224
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...
Definition STLExtras.h:649
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,...
Definition MathExtras.h:703
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
Definition InstrProf.h:143
DomTreeNodeBase< BasicBlock > DomTreeNode
Definition Dominators.h:65
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1762
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...
Definition MathExtras.h:740
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)
Definition STLExtras.h:1652
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
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...
Definition Casting.h:547
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
@ Other
Any other memory.
Definition ModRef.h:68
@ Sub
Subtraction of integers.
@ Add
Sum 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.
Definition STLExtras.h:1933
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...
Definition STLExtras.h:2035
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1788
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition STLExtras.h:2208
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition iterator.h:368
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...
Definition MathExtras.h:777
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.
Definition BitVector.h:881
#define N
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.
Definition MapVector.h:344